HDTenEightyP/NetNews huggingface dataset:
From: bart@cs.uoregon.edu (Barton Christopher Massey)
Subject: Re: IEEE arithmetic handling
Reply-To: bart@cs.uoregon.edu (Barton Christopher Massey)
Organization: University of Oregon Computer and Information Sciences Dept.
Date: Thu, 19 Nov 1992 07:55:41 GMT
Keywords: Fortran, arithmetic

eggert@twinsun.com (Paul Eggert) writes:
> But that conflicts with IEEE Std 754-1985, section 5.6, which requires
> that converting a number from binary to decimal and back be the identity
> if the proper precision and rounding is used.  The Fortran standard says
> -0.0 must be output as 0.0; this loses information.

This and other recent similar comments about compilers and IEEE reminded
me of this note from the back of a recent technical report here (How To
Read Floating Point Numbers Accurately, William D. Clinger, University of
Oregon CIS-TR-90-01, June 1990)

	The IEEE standard explicitly states that, in high level
	languages, the destination of an arithmetic operation
	may be determined by the compiler, and hence may be
	beyond the control of programmers.  In other words, the
	compiler -- not the programmer who uses the compiler --
	is regarded as the client of the standard.  Thus the
	error bounds guaranteed by the IEEE standard may not be
	relied upon by programmers who work in high level
	languages.
	
Modulo arguments about whether FORTRAN is a high-level language :-), it
seems to me that this pretty much answers the question of whether FORTRAN
arithmetic is IEEE compliant.  It's not, but it needn't be, and it may be
unrealistic to expect it to be, given the goals of HLL design.

				Bart Massey
				bart@cs.uoregon.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: sasdrf@unx.sas.com (Dave Frederick)
Newsgroups: comp.compilers
Subject: Re: And speaking of fast compilers...
Keywords: performance, Ada, design, comment
Date: 16 Nov 92 16:03:07 GMT
Article-I.D.: comp.92-11-084
Reply-To: sasdrf@unx.sas.com (Dave Frederick)
Organization: SAS Institute Inc.

pardo@cs.washington.edu (David Keppel) writes:
|[comparing Ada compilers, compiler X was faster than compilers Y and Z
|even though X used C as an intermediate language.]

Not knowing any details of the compilers being used, but knowing a bit
about Ada from my previous job working on the global optimizer for an Ada
compiler (now there's an oxymoron :-), let me pose the following:

You say Compiler X is an Ada preprocessor for a C compiler. Has it passed
an Ada validation suite? Certainly, C does not perform the rigorous type
checking that Ada requires. Declaring i as a range (1..10) could make i
incompatible with an integer type. If the preprocessor simply checks
syntax, and then declares i as an integer in the C program, one loses
whatever power the Ada language offers. If C implements i as an integer,
but inserts code to test i at every assignment to determine if it is
within range, then the compile may be fast, but the runtime of the program
would be unendureable. 

Most of the optimizations an Ada compiler performs are compile-time range
and bounds checking. If it can be determined during the compile that i
will always be in range, all assertion tests can safely be removed. If no
range errors are possible within the scope of an exception handler, this
code is dead and can be removed, as well.  Similarly, if the compiler can
determine that a particular assignment will cause an exception, the
compiler can replace the assignment with a jump directly to the exception
handler. When performing such tests for all ranges, subranges, and array
indices, one can see how an explosion in compile time can occur.

One of the hot topics when I last worked on an Ada compiler was doing the
above range and bounds checking optimization across procedures in a
package. Interprocedural analysis is quite helpful for determining the
possibility of these errors on var parameters. Of course, with a 7000-line
package of page-sized procedures, we could be talking about 200-300
procedures on which to perform inter-procedural analysis. This could be a
week's worth of work.

Then again, perhaps the Brand X compiler was written in C, and Brand Y in
Ada. This could explain the difference, as well :-)

Dave Frederick                              sasdrf@unx.sas.com
[Compiling into C isn't any worse than compiling into assembler -- the Ada
compiler can do the same compile-time checking and emit run-time checking
either way. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: Christopher Traynor<traynorc@Phibro.COM>
Subject: Alignment of structures
Reply-To: Christopher Traynor<traynorc@Phibro.COM>
Organization: Compilers Central
Date: Wed, 18 Nov 1992 14:11:29 GMT
Keywords: C, question, storage, comment

	Could anyone tell me how the structure alignment mechanism works
in gcc?  Specifically, I am interested in knowing how to manipulate the
compiler to produce the smallest, but most efficient ending size and
alignment when a declaration like the following is being made:

struct test_struct
{
 double 	dDouble ;
 short     	siShort ;
 char      	szChar[10] ;
 int 		iInt ;
double	dAnotherDouble ;
} ;

	I have heard that a significant amount of padding is used to align
the struct against the first type - here the double.  This would cause a
lot of waste.  Is it really the case that you have to declare the elements
in an order that is aware of this fact and by its nature reduces the
padding in effect?  I need to know this because in the work that I am
doing I am allocating large amounts of memory and mapping structures into
it - I cannot afford to waste all of this space.

	Thanks in advance for your responses...

Cheers,
Chris
[The C standard requires that structure elements be allocated in the order
you declare them so that hacks with structures with common first parts work.
Some C compilers, particularly on machines that don't require operand
alignment, have ``#pragma pack'' or the like to tell it not to leave holes.
Usually if you put the fields largest first you can avoid padding, but if
you really want to save space there's still no substitute for knowing how
your particular computer works. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: coon@convex.com (Rich Coon)
Subject: RPG implementation?
Reply-To: coon@convex.com (Rich Coon)
Organization: CONVEX Computer Corporation, Richardson, Tx., USA
Date: Wed, 18 Nov 1992 17:51:12 GMT
Keywords: RPG, question, comment

Does any one know of a 'portable' implementation or some kind of 
parser for the venerable RPG II language??
[Given its fixed-column format, I wouldn't think that parsing RPG would be
a big challenge. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: jumper@garfield.catt.ncsu.edu (Michael Lanham)
Subject: Congratulations to John Levine
Reply-To: jumper@garfield.catt.ncsu.edu (Michael Lanham)
Organization: North Carolina State University
Date: Mon, 23 Nov 1992 04:10:54 GMT
Keywords: lex, yacc, books, comment

The new edition of Lex and Yacc by Levine and company published by O'Reilly
and Assoc is outstanding!!!

It has helped me tremendously and I only wish I had even heard of the
older version awhile back.  The 2nd edition is something John can and
should be justifibly proud of.

Michael Lanham       mjlanham@eos.ncsu.edu   &  jumper@catt.ncsu.edu
[Gee, thanks.  Blush. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: tve@crackle.CS.Berkeley.EDU (Thorsten von Eicken)
Subject: Re: Modulo n arithmetics
Reply-To: tve@crackle.CS.Berkeley.EDU (Thorsten von Eicken)
Organization: University of California, Berkeley
Date: Fri, 20 Nov 1992 00:55:35 GMT
Keywords: arithmetic

Christian Fabre <fabre@gr.osf.org> writes:
>I am wondering if any languages or application heavily rely on
>modulo arithmetics:

On parallel machines without hardware support for a global address space a
global pointer can be represented as a 64bit <proc,addr> pair (processor
and local address). If you want to interleave global memory, then pointer
arithmetic requires lots of (mod P), where P is the number of processors:
e.g. "ptr+5", where ptr is a global pointer, turns into

ptr.addr += (ptr.proc+5)/P; ptr.proc = (ptr.proc+5)%P;

Of course, if P is a power of two, you can use shifts and masks.

	Thorsten von Eicken
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: eggert@twinsun.com (Paul Eggert)
Subject: Re: IEEE arithmetic handling
Reply-To: eggert@twinsun.com (Paul Eggert)
Organization: Twin Sun, Inc
Date: Mon, 16 Nov 1992 20:19:55 GMT
Keywords: arithmetic, design

jim@meiko.co.uk (James Cownie) writes:

   (I've never seen this handled right in an optimising compilation),

	   IF (X .ne. X) THEN
	       print *,'X is a NaN'
	   ELSE
	       print *,'X is a number'
	   ENDIF

GCC 2.3.1 (sparc, -O2) handles this right, for C at least.  For example,

	int is_NaN(x) double x; { return x != x; }
	int iszero(x) int    x; { return x != x; }

works as it should: isNaN contains a runtime test, whereas zero yields
0 without a test.  Is it really true that most Fortran compilers get
this wrong?

tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

	An alternative approach ... is that it is an error to use the
	usual language primitives for arithmetic with NaN's....  You
	should have to use special IEEE primitives ("is_nan(x)",
	"ieee_less(x,y)") to get at the IEEE meanings when available.

The IEEE floating point standard recommends that the user be able to
request a trap whenever operations like .LT. are applied to NaNs, so
for operations like .LT., Breuel's ``alternative approach'' should
simply be a matter of enabling a trap handler.  However, .EQ. and .NE.
never trap, so (contra Breuel) Cownie's example still works even if
traps are enabled.  See IEEE Std 754-1985, page 13, table 4.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Subject: Re: IEEE arithmetic handling
Reply-To: tmb@arolla.idiap.ch (Thomas M. Breuel)
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle Perceptive)
Date: Wed, 18 Nov 1992 17:53:37 GMT
Keywords: arithmetic

eggert@twinsun.com (Paul Eggert) writes:

   The IEEE floating point standard recommends that the user be able to
   request a trap whenever operations like .LT. are applied to NaNs, so
   for operations like .LT., Breuel's ``alternative approach'' should
   simply be a matter of enabling a trap handler.  However, .EQ. and .NE.
   never trap, so (contra Breuel) Cownie's example still works even if
   traps are enabled.  See IEEE Std 754-1985, page 13, table 4.

I didn't say that they did trap. I said that I think it's a bad idea for a
language standard to make any guarantees about how the built-in operators
work with IEEE NaN's. I believe that built-in operators should have no
defined behavior for any IEEE-specific features, not after "enabling a
trap handler" nor in any other case. If you define such behavior, programs
written with IEEE semantics in mind will not be forced to clearly document
where they rely on IEEE-specific properties, and they will be very
difficult to port to non-IEEE machines.

The situation is analogous to the many unportable assumptions about
pointers and representations made in C programs: those assumptions are
true on many machines ("32bit workstations") but not all. They make
porting C programs to "unusual" architectures a major headache, since
there is no simple way to identify all the places in which such
assumptions are being made.

Fortunately, whether or not to adopt specific aspects of the IEEE floating
point standard is up to the individual language standards and can't be
mandated by the IEEE floating point standard. So, a C implementation that
chooses to optimize away "x != x" for "double x;" is still within the
current C standard, although it may not be truly "IEEE conforming" (I
believe the same is true for FORTRAN).

I would regret if my compiler gave up opportunities for optimization to
cater to some IEEE specific properties of operators like "!=", but I
suspect the overhead isn't all that large for workstation-class machines.
Ultimate, it is you yourself who pays the price when you use unportable
tricks like "x != x" instead of using self-documenting, clear interfaces
to implementation dependent floating point properties.

					Thomas.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: Jonathan.Bowen@prg.oxford.ac.uk (Jonathan Bowen)
Newsgroups: comp.compilers
Subject: Re: Code optimization questions
Keywords: optimize, performance
Date: 13 Nov 92 10:26:36 GMT
Article-I.D.: comp.92-11-072
Reply-To: Jonathan.Bowen@prg.oxford.ac.uk (Jonathan Bowen)
Organization: Programming Research Group, Oxford University, UK

cse264ce@cs.ucsd.edu (What Is) writes:
>[1] Is there any info on optimizers that take advantage of profiler
>    information?

Try looking at:

David W. Wall, Systems for Late Code Modification,
In R.\ Giegerich and S.L.\ Graham (eds.),
{\em Code Generation -- Concepts, Tools, Techniques},
Proceedings of the {\em International Workshop on Code
Generation}, Dagstuhl, Germany, 20--24 May 1991.
Springer-Verlag, Workshops in Computing, pp.~275-293, 1992.

-- 
Jonathan Bowen, <Jonathan.Bowen@comlab.ox.ac.uk>
Oxford University Computing Laboratory.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: brian@icsbelf.co.uk (Brian Morrow)
Subject: COBOL !
Reply-To: brian@icsbelf.co.uk (Brian Morrow)
Organization: ICS Computing Group Ltd., Belfast
Date: Wed, 18 Nov 1992 13:14:06 GMT
Keywords: Cobol, Pascal, question, comment

Does anyone out there know where I could get source for a COBOL compiler ?
Even if it only supported a subset it would be interesting.

Similarly for PASCAL... even a subset !
[Past requests for Cobol parsers have turned up nothing free.  Isn't there
some Pascal code in comp.sources.something? -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: bill@amber.csd.harris.com (Bill Leonard)
Subject: Re: IEEE arithmetic handling
Reply-To: bill@amber.csd.harris.com (Bill Leonard)
Organization: Harris CSD, Ft. Lauderdale, FL
Date: Fri, 20 Nov 1992 16:09:35 GMT
Keywords: arithmetic

> jlg@cochiti.lanl.gov (J. Giles) writes:
> This is easily accomplished.  Let `b' be the base of your floating point
> representation and let `p' be the number of digits in your significand.
> Then, output followed by input is the identity if:
> 
>         (m-1)     p
>       10      >= b  - 1
> 
> Where `m' is the number of decimal digits output.

This doesn't seem to work.  Take an example: let b=2, p=4.  Thus
 p
b  - 1 = 15, so m=3.  Now consider the binary number 1.001, which has
4 binary digits (as dicated by p=4).  This number, in decimal, is exactly
1.125, which requires 4 decimal digits, thus exceeding the number m.

I don't believe any formula like the above can work if b contains a factor
that is not also a factor of 10 -- for instance, a b of 3 would never
work, since there are fractions in base 3 that are non-terminating
decimals.  (Of course, a computer using base 3 would be pretty strange.
:-)

-- 
Bill Leonard
Harris Computer Systems Division
2101 W. Cypress Creek Road
Fort Lauderdale, FL  33309
bill@ssd.csd.harris.com
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: collberg@dna.lth.se (Christian S. Collberg)
Subject: Parallelizing Compilers for Distributed Memory
Reply-To: collberg@dna.lth.se (Christian S. Collberg)
Organization: Department of Computer Science, Lund University
Date: Fri, 20 Nov 1992 17:27:36 GMT
Keywords: parallel, architecture

I am aware of the work on vectorizing compilers. I have not, however, been
able to find any information on compilers which try to discover
parallelizable code and then attempt to map it to processes on a
distributed memory machine. Can someone help me to find the relevant
references?

Thanks!

Christian Collberg
-- 
Christian.Collberg@dna.lth.se
Department of Computer Science, Lund University
 BOX 118, S-221 00 LUND, Sweden
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: jfc@athena.mit.edu (John F Carr)
Subject: Re: Constant divisions, remainders
Reply-To: jfc@athena.mit.edu (John F Carr)
Organization: Massachusetts Institute of Technology
Date: Mon, 16 Nov 1992 02:02:53 GMT
Keywords: arithmetic

joe@babel.ho.att.com (Joseph M Orost) writes:

>The problem with this thinking is that you will get inconsistent results
>if you divide by a constant power-of-2 versus dividing by a variable with
>the same value.  And you will get LOTS of bug reports from the compiler
>users!

Only if there is a hardware divide instruction.  I modified gcc on the IBM
RT to use shift for division by a power of 2.  At the same time, I changed
the divide function to round down when dividing a negative number by a
positive number.  The divide function uses a series of divide-step
instructions; it takes about the same amount of code to implement either
rounding mode.

The IBM RS/6000 has an equally good solution to the problem: the divide
instructions rounds to zero, but the shift instruction sets the carry bit
if the result is negative so a shift follwed by an add-with-carry
instruction is equivalent to a round-to-zero divide.
--
    John Carr (jfc@athena.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: chased@rbbb.Eng.Sun.COM (David Chase)
Subject: Re: optimizing case-statement execution
Reply-To: chased@rbbb.Eng.Sun.COM (David Chase)
Organization: Sun Microsystems, Mt. View, Ca.
Date: Mon, 23 Nov 1992 20:44:07 GMT
Keywords: C, code, optimize

raymond@harp.ecn.purdue.edu (Ray Kamin) writes:
>How do compilers (in my case gcc v2.2.2) handle large switch statements?
>I have a 120 way switch in my code.  I looked at the sparc assembly code
>produced by gcc and it apparently doesn't use any sort of jump table, but
>merely does sequential comparisons and branches.

>With this in mind, I rewrote the code [with an array of function pointers].

>The code is working correctly, however, it is not any faster at all.  Does
>anyone have any insight into this, or how this should be written for speed?

Sure -- log N grows pretty slowly.  I'm pretty sure that 120 compact
cases go faster if you use a table lookup, but not by much.  Last time
I looked hard at this, break-even was somewhere around 32 (for
"binary" (*) search versus table lookup), but handling 128 cases is
only two compares and two branches more per switch execution.  You're
lucky your code didn't run slower, seeing as how you added parameter
movement, a return, and (possibly) a SAVE and RESTORE pair per switch
execution.

>[There are three general ways to generate code for a switch: a jump table,
>...a binary-compare and branch tree, ... a sequential compare and branch.

Don't forget hash tables, though they may not always be appropriate.

(*) "Binary" means that the appropriately weighted tree should be in
cost-balance.  This includes accounting both for case-frequency and
taken/not-taken branch costs.

David Chase
Sun
-- 
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@gallant.apple.com (Cheryl Lins)
Subject: Re: And speaking of fast compilers...
Reply-To: cheryl@gallant.apple.com (Cheryl Lins)
Organization: Apple Computer Inc, Cupertino, CA
Date: Tue, 17 Nov 1992 17:35:48 GMT
Summary: constant prop. and range value prop.
Keywords: performance, Ada, design, bibliography

sasdrf@unx.sas.com (Dave Frederick) writes:
>Most of the optimizations an Ada compiler performs are compile-time range
>and bounds checking. [other comments deleted]
>When performing such tests for all ranges, subranges, and array
>indices, one can see how an explosion in compile time can occur.

Range and bounds checking are variations on the constant propagation
problem.  If memory serves, this is doable in time linear to the number of
variables.  See [1] for how global constant propagation can be done
efficiently.

>One of the hot topics when I last worked on an Ada compiler was doing the
>above range and bounds checking optimization across procedures in a
>package. Interprocedural analysis is quite helpful for determining the
>possibility of these errors on var parameters. 

So presumably, you were also doing interprocedural alias analysis. I'm
curious about the algorithms used for this. Did you implement those of [2]
(for alias analysis)?

The same algorithms for value propagation mentioned above. In the inter-
procedural case, you may have a paritally constructed lattice with some
known values or ranges for some of the variables.

References
[1]
@inproceedings{cooper:89a,
	author		= "Keith D. Cooper and Ken Kennedy",
	title		= "Fast interprocedural alias analysis",
	booktitle	= popl89,
	pages		= "49--59",
	address		= "Austin, TX",
	month		= jan,
	year		= 1989}

[2]
@article{wegman:91,
	author		= "Mark N. Wegman and F. Kenneth Zadeck",
	title		= "Constant propagation with conditional branches",
	journal		= toplas,
	volume		= 13,
	number		= 2,
	pages		= "181--210",
	month		= apr,
	year		= 1991}


-- 
Cheryl Lins  Oberon Paladin  lins@apple.com
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers