HDTenEightyP/NetNews huggingface dataset:
From: henry@zoo.toronto.edu (Henry Spencer)
Newsgroups: comp.compilers
Subject: constant folding vs exceptions
Keywords: parse, optimize
Date: 26 Aug 92 20:34:53 GMT
Reply-To: henry@zoo.toronto.edu (Henry Spencer)
Organization: U of Toronto Zoology

wjw@eb.ele.tue.nl (Willem Jan Withagen) writes:
>Now I don't want to open another tarpit again, but this certainly is going
>to have effects on the semantics of the used program...
>[This was for integer expressions in C, which traditionally haven't paid
>much attention to overflows...

In fact, ANSI C handed down a much stricter line on this: expressions
execute as written, with the only escape clause being the "as if" rule
(which says that the compiler can do anything it pleases if the user can't
legally tell the difference).  You can still do the things that old C
compilers do, but only if you are generating code that ignores integer
overflow.  Alternatively, you may still be able to do some optimization if
you generate code that catches the cases where overflow would matter --
ANSI C doesn't constrain what *happens* when overflow occurs, so the
program doesn't have to dump core in precisely the same way as the
unoptimized one would.  The only restriction is that if overflows are
visible, optimizations can't add or remove overflows.  This is for
integers, of course; for floating point, optimizations are a lot more
tightly constrained under "as if".

A subtle point worth mentioning here...  A *compiler* that ignores the
possibility of overflow might not generate *code* that ignores overflows.
On many machines, overflow is figured into how some of the conditional
branches work.  If the generated code is to truly ignore overflows, the
compiler has to be aware of the issue and be careful about the code it
generates.  The original Ritchie C compiler, for example, generated code
that could malfunction in peculiar ways in the presence of overflow.
Consider the following with 16-bit ints:

	int foo;

	foo = 32767;
	if ((foo += 200) < 0)
		printf("%d is negative\n", foo);
	else
		printf("%d is non-negative (!)\n", foo);

Guess which message you got out of code from the Ritchie compiler...
-- 
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.
From: dolf@toet.echo.tds.philips.nl (Dolf Grunbauer)
Newsgroups: comp.compilers
Subject: -O4 in SunOS compiler
Keywords: sparc, optimize, C
Date: 3 Sep 92 12:28:32 GMT
Reply-To: dolf@toet.echo.tds.philips.nl (Dolf Grunbauer)
Organization: Compilers Central

David Chase wrote:
>>  * The compiler may produce 'wrong' code ...
>>The last item is common to all optimizing compilers (at least for C),
>>since aliasing analysis relies on some assumptions that must hold for a
>>program, e.g.  the sequence 'p = &i; *(p+offset) = 123;' will access (a
>>component of) i, but no other variable. Of course, you cannot enforce this
>>in C.
>
>What you have there is a case of "undefined behavior" (as specified by the
>ANSI and ISO C language standards).  When this is the case, it is not
>"wrong" to produce code that has different results depending upon the
>optimization level.  Detecting such code is difficult, but not impossible.
>(Example implementation -- generate a map for all of memory, and check
>each instance of pointer arithmetic and dereferencing to ensure that it
>conforms to the C standard.  You may find this too costly, but it is not
>at all impossible.)

An interesting simple program might be the following C code.
Depending on the level of optimalisation the answer varies.
I tested this on Sun 4.1.1..
Options -g, -O and -O2 give a 1 while -O3 and -O4 give 2.
(This program has previously been dealt with in comp.lang.c):
--------------------------------------------------------------------------
/* What should the following program print ? */
/* (Don't mind about layout, I've done it to save space on your screen) */

#include <stdio.h>

typedef struct T { int (*func)(); int val; } T;

foo(x) T *x;      { return (0); }
bar(x) T *x;      { x->val++; x->func = foo; return (0); }
dum(x,y) int x,y; { return (0); }

main()
{  T x; x.func = bar; x.val = 0;
   dum (x.func(&x), x.func(&x));
   printf("The value is: %d\n", x.val);
}

/* 
Possible answers:
1 because on the first call to 'bar' (i.e. x.func in main) x.func will be
  set to 'foo', so x.val only increased once
2 because when calling 'dum' in main it is allowed (?) to determine the
  value of x.func only once, so two calls to 'bar'. This of course depends
  heavily on the evaluation of the arguments of dum.
*/
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: wismuell@Informatik.TU-Muenchen.DE (Roland Wismueller)
Newsgroups: comp.compilers
Subject: Re: -O4 in SunOS compiler
Keywords: sparc, optimize, C
Date: 31 Aug 92 14:59:35 GMT
Reply-To: wismuell@Informatik.TU-Muenchen.DE (Roland Wismueller)
Organization: Technische Universitaet Muenchen, Germany
Originator: wismuell@sunbode7.informatik.tu-muenchen.de

jb3o+@andrew.cmu.edu (Jon Allen Boone) writes:
|> What does the -O4 switch do to the SunOS compiler?...
|> "Same as -O3, but trace  the  effects  of pointer assignments."
|> Ok....what does it mean to trace the effects of pointer assignements?

To trace the effects of pointer assignements means to compute alias sets
for pointer assignments. Normally (i.e. with -O3 or lower) the compiler
assumes, that a pointer may write to any variable that can be accessed by
pointers. This includes all global and static variables, arrays and
variables whose address have been taken with the '&' operator.

With -O4 the compiler tries to figure out, to which of these variables a
pointer can actually point. For example, look at the following code:

	int i,j;
	int a[10],k;
	int *pi, *q = &k;

	if (...) {
		p = &i;
	}
	else {
		p = &j;
	}
	*p = 123;

Without -O4, the compiler assumes that the assignment '*p = 123' may write
to any variable of {i,j,k,a}. With -O4 the compiler recognizes that '*p =
123' can only affect the variables i and j.

So -O4 has several consequences:
  * The compiler must perform additional data flow analysis
  * There may be more chances for optimizations
  * The compiler may produce 'wrong' code

The last item is common to all optimizing compilers (at least for C),
since aliasing analysis relies on some assumptions that must hold for a
program, e.g.  the sequence 'p = &i; *(p+offset) = 123;' will access (a
component of) i, but no other variable. Of course, you cannot enforce this
in C.
--
wismuell@informatik.tu-muenchen.de
Munich University of Technology,
Department of Computer Science, FRG
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: markjan@cs.kun.nl (Mark-Jan Nederhof)
Newsgroups: comp.compilers
Subject: Query: Looking for natural language grammar
Keywords: LR(1), parse, question, comment
Date: 26 Aug 92 11:41:31 GMT
Reply-To: markjan@cs.kun.nl (Mark-Jan Nederhof)
Organization: University of Nijmegen, The Netherlands

For our research, we are looking for a large grammar for natural language;
this grammar should be a context-free grammar possibly extended with
parameters and features of any form. The parameters and features are not
important to us, nor is the language generated by the grammar or the
declarative "meaning". 

Our purpose is to measure the size of different (variants of) LR parsers
for natural language grammars. In particular, the influence of epsilon
rules (which sometimes make normal LR parsers or Tomita parsers loop) on
the size of LR tables is of great interest to us. The ``nastier'' the
grammar is for computational reasons the better it is for us. (We would
prefer a grammar which has been written without any regard for its
computational properties.)

We are looking for an appropriate grammar for a long time now.  If you
have one, then we would be extremely grateful if you would make it
available to us. If you would like to ``encode'' the grammar first such
that it can no longer be used for language recognition (e.g. by deleting
the parameters/features or giving the nonterminals dummy names) then it
would be fine with us.

Please mail to markjan@cs.kun.nl.

Mark-Jan Nederhof  and  Janos J. Sarbo
University of Nijmegen 
The Netherlands
[I thought people gave up trying to parse natural language using LR methods
in about 1966.  Does anyone still use transformational grammars, a la COMIT?
-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:1457 comp.compression:3121
From: markjan@cs.kun.nl (Mark-Jan Nederhof)
Newsgroups: comp.compilers,comp.compression
Subject: Representing unions of Cartesian products
Keywords: theory, design, question
Date: 26 Aug 92 15:29:02 GMT
Reply-To: markjan@cs.kun.nl (Mark-Jan Nederhof)
Organization: University of Nijmegen, The Netherlands

I am looking for an efficient way to store and manipulate unions of
Cartesian products. 

The application domain is abstract evaluation of certain programs (e.g.
datalog programs) and analysis of formal grammars (context-free grammars
extended with features/parameters over a finite domain).

Our goal is to determine the set of parameters with which a nonterminal
can generate a terminal string. If this is done by means of bottom-up
analysis then we need the following operations:

-For two or more sets of tuples of the form A_1 * A_2 * ... * A_n, for
fixed n, we have to compute the union in an efficient form.  (The operator
* denotes the Cartesian product.)  Here the sets A_i consist of atomic
values.

-For two unions of Cartesian products in such an efficient form, call them
C_1 and C_2, we have to compute a third set C_3 in the same form which
represents C_1 - C_2.  (The operator - denotes the subtraction of sets of
tuples.)

-Let us consider two unions of Cartesian products in such an efficient
form, call them again C_1 and C_2. We now have to compute the set C_3
which represents the set of tuples

{(a_1, a_2, ..., a_n) | (b_1, ..., b_m) <- C_1 AND
                        (c_1, ..., c_k) <- C_2 AND
                         R (a_1, ..., a_n, b_1, ..., b_m, c_1, ..., c_k)},

where R is some relation which for some fixed pairs of its arguments says
that they should have the same value. (The operator <- denotes inclusion.)
This operation would be needed in case of a grammar rule with two members
(with m and k parameters respectively; R is determined by ``consistent
substitution''). You can generalise this to arbitrary grammar rules.

This query is inspired by two things:

-The sets of atomic values are typically too big to represent sets of
tuples in a naive way by one element for every tuple.

-When the union of sets of the form A_1 * A_2 * ... * A_n is computed then
very often these sets overlap, and are even ``almost the same but not
quite''.

At this moment I am using a representation where a union of Cartesian
products is transformed into another such that the Cartesian products do
no longer overlap (i.e. they have no tuples in common).  If possible I
merge two Cartesian products into one.  These transformations are however
rather expensive.  Does anyone have a better suggestion? references to
papers?

I suggest follow-up at comp.compression.

Mark-Jan Nederhof
University of Nijmegen
The Netherlands
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: fjh@mundil.cs.mu.OZ.AU (Fergus James HENDERSON)
Newsgroups: comp.compilers
Subject: Re: -O4 in SunOS compiler
Keywords: sparc, optimize, C
Date: 2 Sep 92 08:38:37 GMT
Reply-To: fjh@mundil.cs.mu.OZ.AU (Fergus James HENDERSON)
Organization: Computer Science, University of Melbourne, Australia

chased@rbbb.Eng.Sun.COM (David Chase) writes:
>>The last item is common to all optimizing compilers (at least for C),
>>since aliasing analysis relies on some assumptions that must hold for a
>>program, e.g.  the sequence 'p = &i; *(p+offset) = 123;' will access (a
>>component of) i, but no other variable. Of course, you cannot enforce this
>>in C.
>
>What you have there is a case of "undefined behavior" (as specified by the
>ANSI and ISO C language standards).  When this is the case, it is not
>"wrong" to produce code that has different results depending upon the
>optimization level.  Detecting such code is difficult, but not impossible.
>(Example implementation -- generate a map for all of memory, and check
>each instance of pointer arithmetic and dereferencing to ensure that it
>conforms to the C standard.  You may find this too costly, but it is not
>at all impossible.)

No, it *is* impossible.
For example:

	int i = 1, j = 2;  /* &j == &i + 1 */
	int *p = &i;
	if (fermats_theorem_is_false()) *(p+1) = 3;
	printf("%d %d\n", i, j);

in this case, it is not possible for the compiler to determine whether the
statement *(p+1) = 3 will ever be executed or not.  The best the compiler
can do is issue a warning "execution of this statement would cause
undefined behaviour". Similarly it is easy to come up with examples where
the best the compiler can do is issue a warning "execution of this
statement *might* cause undefined behaviour", eg. something like
	*(p + somefunc()) = 3;
where the compiler cannot detect whether somefunc() will return 0, return 1,
or loop forever.
-- 
Fergus Henderson             fjh@munta.cs.mu.OZ.AU      
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: lka@lems.brown.edu (Lalit K. Agarwal)
Newsgroups: comp.compilers
Subject: Looking for literature on Control flow graph
Keywords: optimize, analysis
Date: 31 Aug 92 15:45:04 GMT
Reply-To: lka@lems.brown.edu (Lalit K. Agarwal)
Organization: Laboratory for Engineering Man/Machine Systems


I'm looking for any published article on how to construct Control Flow &
Control Dependence Graph of a C-program while compiling it. I've gone
through the "Dragon Book" (Aho, Sethi, Ullman : Compilers), but it doesn't
give any implementation techniques for the either of the two. What I'm
looking for is reference to any real implementation methodology and the
data structures involved. 

thanks in advance,

-Lalit K Agarwal ( lka@lems.brown.edu )
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: moss@cs.umass.edu (Eliot Moss)
Newsgroups: comp.compilers
Subject: Re: OOL & RISC references?
Keywords: OOP, bibliography
Date: 3 Sep 92 02:26:56 GMT
Reply-To: moss@cs.umass.edu (Eliot Moss)
Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst)

Take a look at the various papers on the Self language, by David Ungar,
Craig Chambers, and others. Look through the past number of years of
OOPSLA, SIGPLAN, etc. to find them; here are some fo the citations:

@INPROCEEDINGS{CU89,
  crossref =	"sigplan89",
	AUTHOR = "Craig Chambers and David Ungar",
	TITLE = "Customization: Optimizing Compiler Technology for {SELF},
                a Dynamically-Typed Object-Oriented Programming Language",
	PAGES = "146--160"
}
@InProceedings{CUL89,
  crossref =	"oopsla89",
  author = 	"Craig Chambers and David Ungar and Elgin Lee",
  title = 	"An Efficient Implementation of {\sc Self}, A
  Dynamically-Typed Object-Oriented Language Based on Prototypes",
  pages = 	"49--70"
}
@InProceedings{CU90,
  crossref =	"sigplan90",
  author = 	"Craig Chambers and David Ungar",
  title = 	"Iterative Type Analysis and Extended Message Splitting:
  Optimizing Dynamically-Typed Object-Oriented Programs",
  pages = 	"150--164"
}
@InProceedings{CU91,
  author = 	 "Craig Chambers and David Ungar",
  title = 	 "Making Pure Object Oriented Languages Practical",
  crossref =  "oopsla91",
  pages = 	 "1--15",
  annote = 	 "Self, Message Splitting"
}
--
		J. Eliot B. Moss, Associate Professor
		Department of Computer Science
		Lederle Graduate Research Center
		University of Massachusetts
		Amherst, MA  01003
		(413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:1495 comp.edu:1464 comp.lang.functional:1054 comp.lang.misc:2861 comp.parallel:2024
From: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Subject: Re: Parsing wars
Reply-To: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Organization: The Johns Hopkins University CS Department
Date: Tue, 1 Sep 1992 17:07:19 GMT
Keywords: parse, LR(1)

dww@inf.fu-berlin.de writes:
>The parsing is called shift-reduce parsing, and I thought I had understood
>that. What happens on a reduction though is, instead of pushing the
>nonterminal of the lhs of the reduced production onto a symbol stack and
>digging through the goto table for the appropriate state to push onto the
>state stack, the nonterminal is *prepended* to the input sequence of
>tokens and parsing resumes as normal. The other actions, shift, accept and
>error are as expected, an action shiftreduce combines the normal shift and
>the strange reduce.

The Moderator adds:

>[It sounds to me like a way to combine the shift and goto tables, since
>pushing the nonterminal and then shifting it would be equivalent to a
>goto.  -John]

	It's also a cheesy way of saving the parse tree.  Since nothing is
ever popped off of the parsing stack, the result of parsing is just the
input annotated with special non-terminal symbols.  This is basically the
parse tree written out by either a pre- or post-order traversal, depending
on whether you look at the stack from either the top or the bottom.

	There are better ways of making a parse tree, of course, since
this method gives one that is (1) difficult to traverse and (2) reflects
the _concrete_ rather than the _abstract_ syntax of the language, which is
usually more useful.  It is, however, relatively space efficient, the
entire stack being only a (small) constant factor larger than the input.
So it could be useful for some things, like printing error messages
including the offending portion of the input.
--
Jack Eifrig (eifrig@cs.jhu.edu)       The Johns Hopkins University, C.S. Dept.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: goer@midway.uchicago.edu (Richard L. Goerwitz)
Newsgroups: comp.compilers
Subject: Re: LR(0) vs. LALR, and the Great Parsing War
Keywords: parse
Date: 31 Aug 92 17:20:54 GMT
Reply-To: goer@midway.uchicago.edu (Richard L. Goerwitz)
Organization: University of Chicago Computing Organizations

Jonathan Eifrig writes:
>	This seems quite surprising to me, given that Tomita's algorithm
>basically has to spin off on the fly new parsing automatons to follow each
>possible path in a derivation.

Yes and no.  If this were true, then Tomita's algorithm would have a cubic
worst-case time factor.  He uses a graph-structured parse forest, though,
and claims polynomial time.
-- 
   -Richard L. Goerwitz              goer%midway@uchicago.bitnet
   goer@midway.uchicago.edu          rutgers!oddjob!ellis!goer
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: preston@helena.cs.rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Re: Dealing with Multiple Inheritence in an Object-Oriented Language
Keywords: OOP, design
Date: 2 Sep 92 03:24:21 GMT
Reply-To: preston@helena.cs.rice.edu (Preston Briggs)
Organization: Rice University, Houston

"Ed Cynwrig Dengler" <eadengle@watcgl.uwaterloo.ca> writes:
>I am trying to find references to articles that deal with the problems of
>dealing with and representing multiple inheritence in a compiled program.

There following paper talks about a tricky layout scheme that helps in
many cases.  It's from the ACM SIGPLAN '90 Conference on Programming
Language Design and Implementation.  The proceedings are published in
SIGPLAN Notices.

@article{pugh:90,
author="William Pugh and Grant Weddell",
title="Two-Directional Record Layout for Multiple Inheritance",
pages="85--91",
journal=sigplan,
year=1990,
month=jun,
volume=25,
number=6,
note=pldi90
}

Another important source would be past proceedings from OOPSLA, a major
conference on Object-Oriented Stuff.

Preston Briggs
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: robert@metropolis.com (Robert Munyer)
Newsgroups: comp.compilers
Subject: Re: Why is compiled basic slower than C? (Basic is the future)
Keywords: interpreter, performance, Lisp
Date: 25 Aug 92 08:29:01 GMT
Reply-To: robert@metropolis.com (Robert Munyer)
Organization: Metropolis Software, Inc.

macrakis@osf.org (Stavros Macrakis) writes:
> [...] There are a few cases where Lisp code generates code on the fly,
> then executes it.  This is handled by having an interpreter loaded along
> with the compiled code [...]

... or by having a COMPILER loaded along with the compiled code ...

Also, much of the kind of programming that people used to do by generating
and executing code on the fly, is now done instead by using functional
programming and closures.  In other words, using "lambda" instead of "eval".

Robert Munyer
robert@metropolis.com
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: bburshte@pyramid.com (Boris Burshteyn)
Newsgroups: comp.compilers
Subject: Re: Parsing wars
Keywords: parse, LR(1)
Date: 3 Sep 92 17:53:15 GMT
Reply-To: bburshte@pyramid.com (Boris Burshteyn)
Organization: Compilers Central

Andrew Bromage writes:
>Pushing nonterminals onto the token stream, however, is a new one to me.
>I suppose that this would optimise the GOTO tables a bit, but there are
>better ways of doing this, like creating distinct reduce and lookahead
>states (IMHO).

The USSA parser generator builds tables which make no distinction between
terminals and nonterminals. In most cases tables are better or comparable
with YACC. USSA also builds tables for a generator which produces sample
sentences from the described language, like 

	int ident() { int ident = function_call; }

These sentences can be accepted due to equivalent treatment of terminals
and nonterminals.

Thanks - Boris Burshteyn (bburshte@pyramid.com)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: khb@chiba.Eng.Sun.COM (Keith Bierman fpgroup)
Newsgroups: comp.compilers
Subject: Re: -O4 in SunOS compiler
Keywords: C, optimize
Date: 1 Sep 92 16:55:28 GMT
Reply-To: khb@chiba.Eng.Sun.COM (Keith Bierman fpgroup)
Organization: Sun MegaSystems

jb3o+@andrew.cmu.edu (Jon Allen Boone) writes:

   What does the -O4 switch do to the SunOS compiler?

Helps to be more precise about the version of the compiler in
question.

                    4    Same as -O3, but trace  the  effects  of
                         pointer   assignments,  gather  aliasing
                         information, do  parameter  propagation,
                         and perform inlining.

is the text in C1.1. 

By tracing the effects of pointer assignments it is sometimes
possible to perform "f77 style" optimizations.

The inlining works when the caller and the callee are in the same file
and a variety of heuristics regarding the expansion are satisfied.
--
Keith H. Bierman    keith.bierman@Sun.COM| khb@chiba.Eng.Sun.COM
SunPro 2550 Garcia MTV 12-33             | (415 336 2648) fax 964 0946
Mountain View, CA 94043
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.