HDTenEightyP/NetNews huggingface dataset:
From: sastdr@unx.sas.com (Thomas David Rivers)
Subject: Re: Strength reduction of constant multipliers
Reply-To: sastdr@unx.sas.com (Thomas David Rivers)
Organization: SAS Institute Inc.
Date: Wed, 14 Oct 1992 18:54:00 GMT
Keywords: arithmetic, optimize

Interestingly enough, Dr. Dobbs Journal gave a nice example program for
doing strength reduction of constant multipliers.

Also, I have implemented that in the SAS/C Mainframe compiler, versions
5.00 and greater.  My own testing indicated that for a simple algorithm,
sequences up to about 9/10 shift/add, shift/sub instructions beat a
multiply instruction hands down.  Actually, I could reasonably claim that
the sequence could be as long as 14 instructions, but we settled on 9,
because of possible timing problems in the test.  It's difficult to get
reliable numbers under MVS, and the timings can be vastly different for
the different IBM/370 implementations. 

An interesting twist to the problem is that for the IBM/370, two adds are
faster than faster than a shift by 4. Making the problem of optimal
sequences even more difficult.

My goal, however, was not to provide optimal sequences, just something
better than a multiply instruction.  The approach is to run a star chain
analysis, determining the length of the would-be sequence.  If it is
greater than some threshold; (the aforementioned '9') use a multiply,
otherwise you've found something better.

    - Dave Rivers -
    (sastdr@unx.sas.com)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: Dawson R. Engler <engler@cs.arizona.edu>
Subject: wanted: LL(1) grammar for C
Reply-To: Dawson R. Engler <engler@cs.arizona.edu>
Organization: Compilers Central
Date: Wed, 14 Oct 1992 01:59:57 GMT
Keywords: C, LL(1), question

Does anyone know where I can obtain a correct, free, LL(1) C grammar?

Thank you,
	Dawson
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: "Cheryl Lins" <Cheryl_Lins@gateway.qm.apple.com>
Subject: comp_bib.Z permissions fixed
Reply-To: "Cheryl Lins" <Cheryl_Lins@gateway.qm.apple.com>
Organization: Compilers Central
Date: Tue, 13 Oct 1992 18:08:09 GMT
Keywords: bibliography, FTP

Oops. Nothing more embarrassing than making a mistake and having a million
net readers tell you about it.  I've fixed the permissions on the file
comp_bib.Z so it's readable by everyone.

Also note that from the outside, the directory is simply seen as

/pub/oberon

Cheryl Lins, Oberon-2 Paladin. lins@apple.com
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: khattra@cs.sfu.ca (Taj Khattra)
Subject: Re: Functional Languages
Reply-To: khattra@cs.sfu.ca (Taj Khattra)
Organization: CSS, Simon Fraser University, Burnaby, B.C., Canada
Date: Sat, 10 Oct 1992 02:05:39 GMT
Keywords: functional

J.A. Eccleston <ecclesja@cs.aston.ac.uk> writes:
>[Is there a] G-Code compiler for either of the machines mentioned above.

Simon L. Peyton Jones (of the University of Glasgow) and David R. Lester
(of the University of Manchester) are supposed to be coming out with a new
book on implementing functional languages sometime in the near future. It
goes into considerable details of a G-machine compiler.  The
implementation language used is Miranda, but I'm sure you'll still find it
useful.

You may want to contact them at simonpj@dcs.glasgow.ac.uk or
dlester@dcs.manchester.ac.uk
--
Taj Khattra
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: sanjay@equalizer.cray.com (+Sanjay Krishnamurthy)
Subject: Re: Genetic algorithms and scheduling
Reply-To: sanjay@equalizer.cray.com (+Sanjay Krishnamurthy)
Organization: Compilers Central
Date: Mon, 12 Oct 1992 16:54:24 GMT
Keywords: optimize

>I am desperately seeking references and implementations on
>instruction scheduling using genetic algorithms.

Try...

"Genetic Algorithms and Instruction Scheduling," Steven J. Beaty in the
proceedings of the 24th Annual International Symposium on
Microarchitecture, November 1991. There are a number of relevant
references in this paper, the most significant being Beaty's dissertation
titled "A study of instruction scheduling using genetic algorithms," Dept.
of Mech.  Engg., Colorado State University, Fort Collins, Colorado, 1991.

[Hans Mulder at your university-Delft Univ., I presume, presented a paper
at the same conference on software pipelining for transport triggered
architectures. You should be able to get a copy of the proceedings from
him.]

Bartheeni guru......

-Sanjay M. Krishnamurthy
Cray Research Superservers
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,gnu.gcc.help
From: oner@paris.usc.edu (Koray Oner)
Subject: How can I change GCC to make it perform SOFTWARE PIPELINING.
Reply-To: oner@paris.usc.edu (Koray Oner)
Organization: Compilers Central
Date: Mon, 12 Oct 1992 19:58:01 GMT
Keywords: GCC, optimize

Hi Netters,

For my studies in cache memories I need a compiler which performs the
SOFTWARE PIPELINING transformation to the code. Since I couldn't find such
a compiler for Sun Sparc processors and since I couldn't convince anyone
in CS department to this for me, I have to do it myself. 

Instead of writing a compiler from scratch I decided to modify GCC
compiler.  Even though I took a compiler design course, I am no expert on
compiler design and I ask your advice on how to approach this problem and
how to solve it without too much hustle.

I appreciate your comments. Thanks.

Koray Oner
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:1717 comp.human-factors:2401
From: drw@euclid.mit.edu (Dale R. Worley)
Newsgroups: comp.compilers,comp.human-factors
Subject: Re: Syntax of Comments (was: language design tradeoffs)
Keywords: syntax, design
Date: 7 Oct 92 20:46:31 GMT
Article-I.D.: comp.92-10-032
Reply-To: drw@euclid.mit.edu (Dale R. Worley)
Organization: MIT Dept. of Tetrapilotomy, Cambridge, MA, USA

The moderator writes:
   [There are plenty of programs that highlight keywords and the like.  [but]
   highlighting the keywords is probably the worst possible way to format a
   program, since the keywords are the noise.  ...  But printing the keywords
   in bold is an ancient tradition, at least back to Algol 60. -John]

And the habits that you learn cause you to do things differently than
you would by default: Your attention focuses on the italicized words,
not the boldface ones.  Inverting the present conventions would
probably make a program unreadable!

Dale

Dale Worley		Dept. of Math., MIT		drw@math.mit.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: preston@dawn.cs.rice.edu (Preston Briggs)
Subject: Re: strength reduction of constant multiplication ?
Reply-To: preston@dawn.cs.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Date: Fri, 9 Oct 1992 03:10:09 GMT
Keywords: arithmetic, theory

Youfeng Wu <wu@sequent.com> writes:
>[discussion of converting integer multiply by constant into simpler
>instructions] 

I believe the problem of finding the optimal sequence of adds and left
shifts is NP-complete if we attempt to reuse intermediate results.  Adding
subtract and right shift doesn't simplify the problem, though it can lead
to shorter solutions.

For example, multiplication by 22 without reusing intermediates seems to
take 5 instructions (of a certain limited form)

	x4 = x1 << 2
	x5 = x4 + x1
	x10 = x5 << 1
	x11 = x10 + x1
	x22 = x11 << 1

If we allow the reuse of intermediates results (which will cost additional
registers), we can find a shorter solution:

	x2 = x1 << 1
	x3 = x2 + x1
	x24 = x3 << 3
	x22 = x24 - x2

I've only shown simple instructions.  Naturally, shorter solutions using
special shift and add instructions are possible.

In practice, it probably suffices to use any heuristic approach that works
well for small integers, especially if supplemented by an exception table.
The idea of the exception table is to record (in a hash table, for
instance) the cases for which your heuristic is non-optimal and their
optimal solution (derived once at great expense by the compiler writer
using some sort of branch-and-bound exponential searcher).

The following paper describes the approach used in the PL.8 compiler:

  title="Multiplication by Integer Constants",
  author="Robert Bernstein",
  journal="Software -- Practice and Experience",
  volume=16,
  number=7,
  month=jul,
  year=1986,
  pages="641--652"

A second reference describes a similar approach used by HP

	Integer Multiplication and Division on the HP Precision
		Architecture
	Magenheimer, Peters, Pettis, and Zuras
	Proceedings of ASPLOS II

The mathematically inclined will resort to Knuth, Volume 2.

Preston Briggs
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: Youfeng Wu <wu@sequent.com>
Subject: strength reduction of constant multiplication ?
Reply-To: Youfeng Wu <wu@sequent.com>
Organization: Compilers Central
Date: Thu, 8 Oct 1992 22:20:58 GMT
Keywords: arithmetic, theory, question, comment

For superscalar processors, multiplication usually is more than ten times
slower than the simple instructions like add, sub, shift, or lea (shift by
1, 2, 3 and add) instructions.  It is beneficial to replace the
multiplication by a sequence of the simple instructions (to increase speed
and to provide more opportunity for instruction level parallelism).

For each integer constant, it can be represented as a binary sequence

	sum ( ai*2**i | i = 0, ..., k ) where ai = either 0 or 1.

I found an algorithm that can replace multiplication by any constant in
the range of [1, 2**32-1] by a sequence of simple instructions with the
average length no longer than 

	sum ( ai | i = 0, ..., k ) - 1

Examples.

1.	X * 136 = X * (2**3 + 2**7) 
can be replace by the following two instructions:

	reg = X shfit 7		*** X left shift 7 bits
	reg = lea ( reg, X, 3)	*** reg add ( X left shift 3 bits )

2. 	X * 1950 = X * (2 + 2**2 + 2**3 + 2**4 + 2**7 + 2**8 + 2**9 + 2**10)
can be replace by the following five instructions:

	reg = lea ( X, X, 1 )
	reg = reg shift 5
	reg = lea ( reg, X, 1 )
	reg1 = X shift 11
	reg = reg1 sub reg	*** reg1 minus reg

But I found out that for certain cases this algorithm is not optimal.  Do
anyone know a reference on this subject (with discuss on approachs,
complexity, and/or optimal solution or NP completeness, etc)?  

TIA,

Youfeng Wu, Ph.D.         15450 S.W. Koll Parkway
Compilers, D2-745         Beaverton, OR  97006-6063
Sequent Computer Systems  Tel: (503) 578-4273
wu@sequent.com            Fax: (503) 578-3228
[This can get pretty hairy, particularly if you allow subtraction as well
as addition.  I know it's been studied at some length; someone should have
references. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:1714 comp.lang.c++:14681
From: ethan@niwot.scd.ucar.EDU (Ethan Alpert)
Newsgroups: comp.compilers,comp.lang.c++
Subject: References for Compiler and Interpreter implementation in C++?
Keywords: C++, question
Date: 7 Oct 92 17:07:50 GMT
Reply-To: ethan@niwot.scd.ucar.EDU (Ethan Alpert)
Organization: Compilers Central

Hello,

	I've been learning C++ for a few months now and am interested in
studing compiler and interpreter implementations written in C++. It would
seem that there are lots of natural abstractions that can be made with
regard to source tree construction, garbage collection and code
generation. I can also envision the possiblity of building extensible type
systems so new primative data types can be added to the interpreter as
needed. 

	Any references to literature would be most appreciated.

	Thanks in advance,

	-ethan
-- 
Ethan Alpert  internet: ethan@ncar.ucar.edu
Scientific Visualization Group, Scientific Computing Division
National Center for Atmospheric Research, PO BOX 3000, Boulder Co, 80307-3000
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: roland@bruce.cs.monash.edu.au (Roland Yap)
Newsgroups: comp.compilers
Subject: New Release of Constraint Logic Programming language, CLP(R)
Keywords: logic, prolog, available
Date: 15 Oct 92 03:32:03 GMT
Article-I.D.: comp.92-10-064
Reply-To: roland@bruce.cs.monash.edu.au (Roland Yap)
Organization: Computer Science, Monash University, Australia

------------------
CLP(R) Version 1.2
------------------

We wish to announce the release of a new version of IBM's prototype
implementation of CLP(R).  This system is available for academic and
research purposes only, and is provided free of charge.  The system is
distributed with source code, manual, examples, etc..  Receipients of the
system should note that the system comes with a disclaimer and user
agreement embedded within the source code.  We are distributing CLP(R) in
order to help widen the use of constraint programming, and to solicit
feedback on the system.  Our preferred method of distribution is by
electronic mail in a number of uuencoded files.  Requests for the system
should be sent to:

     Joxan Jaffar, H1-D48
     IBM Thomas J. Watson Research Center
     P.O. Box 704
     Yorktown Heights, NY 10598
     U.S.A.
     (joxan@watson.ibm.com, joxan@yktvmh.bitnet)

CLP(R) is a constraint logic programming language with real-arithmetic
constraints.  The implementation contains a built-in constraint solver
which deals with linear arithmetic and contains a mechanism for delaying
nonlinear constraints until they become linear.  Since CLP(R) subsumes
PROLOG, the system is also usable as a general-purpose logic programming
language.  There are also powerful facilities for meta programming with
constraints.  Significant CLP(R) applications have been published in
diverse areas such as molecular biology, finance, physical modelling, etc.

The system, consisting of a compiler, byte-code emulator and constraint
solver, is written entirely in C.  It has been known to run on a number of
machines: Suns, Vaxen, MIPS-based machines (Decstations, Silicon
Graphics), IBM RS6000s and PS2s, PC's using a number of UNIX[tm]-based
operating systems: AIX, System 5, BSD, Mach and SunOS, as well as under
PC's (386's and 486's) running: MS/DOS and OS/2 2.0.

Version 1.2 replaces the previous version 1.1.  It contains a number of
new features which includes support for MS/DOS and OS/2 2.0, new
non-linear constraints for arc sin and arc cos, style checking, symbolic
constants, new system predicates and other enhancements.

* UNIX is a trade-mark of AT&T Bell Laboratories.

(enquiries may also be directed to roland@bruce.cs.monash.edu.au)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,comp.human-factors
From: kendall@centerline.com (Sam Kendall)
Subject: Re: Syntax of Comments (was: language design tradeoffs)
Reply-To: kendall@centerline.com (Sam Kendall)
Organization: CenterLine Software, Inc.
Date: Wed, 7 Oct 1992 07:25:33 GMT
Followup-To: comp.compilers,comp.human-factors
Keywords: design, syntax

I recommend R. Baecker and A. Marcus, "Human Factors and Typography for
More Readable Programs", ACM Press, 1990.  An entire book on
prettyprinting C programs.  The reasoning processes can be applied to
screen display, too.  Don't be put off by the incredibly ugly results; the
book is worth reading.  The authors themselves admit that tastes differ.
----
Sam Kendall
CenterLine Software, Inc. (formerly Saber Software)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: Cheryl_Lins@gateway.qm.apple.com (Cheryl Lins)
Newsgroups: comp.compilers
Subject: New Compilers bibliography available
Keywords: bibliography, FTP
Date: 12 Oct 92 22:23:10 GMT
Reply-To: Cheryl Lins <Cheryl_Lins@gateway.qm.apple.com>
Organization: Compilers Central

The compilers bibliography has been updated to version 1.2. The following
enhancements have been made:

1. Some corrections to names and spellings.
2. Merging in all of Preston Brigg's TOPLAS bibliography
3. Inclusion of all POPL 88-92 papers
4. Inclusion of all PLDI 88-92 papers
5. Removal of some funny Macintosh characters from the text.
6. Additions since the last release (whenever that was :-)

If you have corrections or additions, feel free to contact me at the email
address in the .sig.

The bibliography can be obtained via anonymous ftp from

host:      ftp.apple.com
directory: /ftp/pub/oberon
file name: comp_bib.Z

The file is about 300K uncompressed.

Cheryl Lins, Oberon-2 Paladin. lins@apple.com
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:1713 comp.arch:9872
From: henry@zoo.toronto.edu (Henry Spencer)
Newsgroups: comp.compilers,comp.arch
Subject: Re: Register Files
Keywords: registers, architecture
Date: 7 Oct 92 16:56:37 GMT
Reply-To: henry@zoo.toronto.edu (Henry Spencer)
Organization: U of Toronto Zoology

ssimmons@convex.com (Steve Simmons) writes:
>... Since the CPU can write (or read) to (or
>from) only one register file on a cycle, having both floating point and
>integers gprs in the same register file would prohibit simultaneous
>execution of both floating point and integer operations.

Actually, not so.  Or not necessarily so.  There is no fundamental
difficulty in building multi-port register files; they are common.
Indeed, I'd say it's almost a certainty that Alpha's register file (more
correctly, the register file of the current implementation) is
multi-ported.

Also, unless your floating-point stuff is really fast, it can spend a lot
of its time doing things that don't require register access.  The AMD
29050 has a single register file and goes in quite extensively for
simultaneous integer and floating-point operations.

However, the general point is valid.  The more ports on a register file,
the harder it is to build, and the bigger a bottleneck wiring becomes in
its vicinity.  Ideally one would prefer lots of specialized register files
in specialized areas of the chip, making each one relatively small and
simple and minimizing wiring between the register file and the circuits
that use it.  You can also get better use out of instruction bits if you
use context (e.g. type of instruction) to decide which register file is
being referred to.

The problem with this is that it's a headache for the compiler people,
partly because a crucial resource has been sliced up into chunks that
can't be used interchangeably, and partly because you start needing
explicit code to move data from one register file to another.  So it's
mostly gone out of fashion... with one exception.

The exception, of course, is integer and floating point.  Those types of
data don't mix much; the penalty for this split is not high.  And it does
improve potential parallelism quite a bit, as well as doubling the
register count for a given instruction layout.  So it's popular.
-- 
Henry Spencer @ U of Toronto Zoology, henry@zoo.toronto.edu  utzoo!henry
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: D C McHugh <dcmchugh@dsg.cs.tcd.ie>
Subject: Request for Yacc description for Eiffel 2.3
Reply-To: D C McHugh <dcmchugh@dsg.cs.tcd.ie>
Organization: Compilers Central
Date: Tue, 13 Oct 1992 13:05:23 GMT
Keywords: yacc, Eiffel, question

About three months ago I posted here requesting a Yacc description of the
Eiffel grammar, and got a version for Eiffel 2.2., which saved me a LOT of
work:-) I'm now posting to request if anyone has got a Yacc description
for Eiffel 2.3!  (The reason being that I'm working with v.2.3 and the
Yacc parser I have throws up some errors when parsing some of the library
classes which, obviously, is down to sytactical differences between 2.2
and 2.3; so, is there anyone who can save me a bit more work?:-)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: wjw@eb.ele.tue.nl (Willem Jan Withagen)
Subject: Starting of the Cocktail mailing list
Reply-To: wjw@eb.ele.tue.nl (Willem Jan Withagen)
Organization: Compilers Central
Date: Mon, 12 Oct 1992 16:43:42 GMT
Keywords: tools

As promissed in a previous message:

The Cocktail Compiler Construction Tools discusion list.

Topics for discussion could be:
	-	Use of the tools
	-	Improvement of the tools
	-	Possible bugs in the tools
	-	Compilers make with Cocktail
	-	.......

The obtain infomation on the list server send a message containing 
	HELP 
		to listserv@eb.ele.tue.nl

To obtain the basic information about COCKTAIL send a message containing
INFORMATION COCKTAIL 
		to listserv@eb.ele.tue.nl
                                   
To subscribe send a message containing
SUBSCRIBE COCKTAIL <your full name>
		to listserv@eb.ele.tue.nl

		Willem Jan Withagen

Digital Information Systems Group, Room EH 10.35 
Eindhoven University of Technology   
P.O. 513                     		Tel: +31-40-473401,Fax: +31-40-448375
5600 MB Eindhoven            		The Netherlands
Internet:  wjw@eb.ele.tue.nl    
X400:      C=nl;ADMD=400net;PRMD=surf;O=tue;OU=ele;OU=eb;S=WJW;
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.