HDTenEightyP/NetNews huggingface dataset:
From: Richard Cownie <richard@meiko.com>
Subject: optimizing for caches
Reply-To: Richard Cownie <richard@meiko.com>
Organization: Compilers Central
Date: Tue, 17 Nov 1992 23:30:08 GMT
Keywords: optimize, architecture, 

From experiences tuning vector routines for i860's and SPARC's, I've come
to the conclusion that understanding and exploiting the memory hierarchy
is essential to obtain good performance on these kinds of problems.  But I
have yet to see a compiler which tackles this aspect of optimization.
Does anyone have references to research in this area ?  If so, please mail
me and I'll summarize.

With the way hardware is developing, this will be a big issue very soon.
Here are some approximate figures to illustrate the trend:

    Year     Machine      MIPS rate  Cache miss (DRAM access)

    1988    Sun-4/110        7        200ns ?
    1991    SS-2 Cypress    25        120-150ns ?      
    1993    SS-10 Viking    50        100-120ns ?
    1994    ?              150        80-100ns ?

So the relative cost of a cache miss has already risen from about 1.4
instructions to > 5 instructions, and the Viking clock speed is still only
40MHz; the technology exists now to build processors running at 150MHz
(e.g. Alpha), which will take the cost of a cache miss over 20
instructions.

It seems really important to get this right - if you get your instruction
scheduling wrong, you might still see 25% of optimum performance, but if
you don't exploit the memory hierarchy, you might see only 5% of optimum
performance ...  

Thanks in advance for all responses,
Richard Cownie (a.k.a. Tich), Meiko Scientific Corp 
email: richard@meiko.com
phone: 617-890-7676
fax:   617-890-5042       
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: jos@and.nl (Jos Horsmeier)
Subject: Re: Theoretical CFG question
Reply-To: jos@and.nl (Jos Horsmeier)
Organization: AND Software BV Rotterdam
Date: Tue, 17 Nov 1992 12:31:04 GMT
Keywords: parse

norlin@essex.ecn.uoknor.edu (Norman Lin) writes:
|For i>=1, let b(i) denote the string in  1(0+1)   that is the
|binary representation of i.  Construct a CFG generating
|          +
|   {0,1,#}    -   {b(1)#b(2)# ... #b(n) | n>=1}

I wrote:
|If you apply the pumping lemma, it would show that this language is _not_
|a context free language, so there exists no CFG that can generate this
|language. No word in this language can be written
|                      i  i
|as UVWXY, such that UV WX Y, for i >= 0 is an element of this language too.
|Or am I missing something here?

Well, I didn't miss just something, I missed it completely. The
_complement_ of the language is not a CFL. But this language is, as
someone else already pointed out in another reply. My apologies for the
confusion ...

kind regards,

Jos aka jos@and.nl
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: firth@sei.cmu.edu (Robert Firth)
Newsgroups: comp.compilers
Subject: Re: Is this a new idea?
Keywords: C, design
Date: 17 Nov 92 12:54:59 GMT
Article-I.D.: comp.92-11-092
Reply-To: firth@sei.cmu.edu (Robert Firth)
Organization: Software Engineering Institute

drw@euclid.mit.edu (Dale R. Worley) writes:
>Any language has this problem if it has tokens whose syntactic
>category can't be determined solely by the form of the token.

True.  The answer, I suppose, is not to design such languages.

>Almost any language with an extensible set of operators is going to
>run into this problem.

Why?  We have languages with extensible sets of identifiers, and none of
the well-designed ones runs into this problem.  It is simply a matter of
specifying the lexis of operators so that they can be distinguished.  As
an obvious cheap and ugly way, require all user-defined operators to be
delimited by $...$, or some other character not used elsewhere.

-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: johnl@iecc.cambridge.ma.us (John R. Levine)
Newsgroups: comp.compilers
Subject: New lex & yacc book from O'Reilly
Keywords: lex, yacc, books, tools
Date: 15 Nov 92 06:11:34 GMT
Article-I.D.: comp.92-11-070
Reply-To: John R. Levine <johnl@iecc.cambridge.ma.us>
Organization: Compilers Central

I'm pleased to report that the new version of the O'Reilly ``lex & yacc''
is now available:

Levine, Mason, and Brown, ``lex & yacc,'' 2nd edition, O'Reilly &
Associates, 1992, 366 pp., ISBN 1-56592-000-7, $29.95.

I think it's a big improvement, but since I wrote a lot of it, my opinion
is hardly unbiased.  Changes include:

-- Rewritten introductory chapters, with more detailed examples
-- New example chapter with a SQL parser
-- Greatly expanded reference sections, with details on grotty things like
   how to munge symbols in generated lexers with sed so you can include
   several of them in the same program.
-- Expanded section on ambigity, conflicts, and error handling
-- Exercises at the ends of the chapters for self-study and textbook use
-- All the examples actually work

It should be available at technical bookstores.  Outside North America,
Addison-Wesley distributes it.

Regards,
John Levine, johnl@iecc.cambridge.ma.us, {spdcc|ima|world}!iecc!johnl
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,misc.jobs.offered
From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Subject: Re: IEEE arithmetic handling
Reply-To: tmb@arolla.idiap.ch (Thomas M. Breuel)
Organization: IDIAP
Date: Mon, 16 Nov 1992 01:19:25 GMT
Keywords: arithmetic, design

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

   Another area where IEEE seems never to be implemented correctly by
   compilers is in the handling of Not a Numbers (NaNs). [...]

	   (.NOT. (X .LT. 2.0)) does NOT imply (X .GE 2.0)

   [...] Similarly (and 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

   should generate code which has a run time test. 

You are making the assumption that the usual language primitives for FP
("=", "<", ".ne.", etc.) should map directly on IEEE operations.  That is
certainly not mandated by most current language standards, and I have
serious doubts that it should be mandated.

An alternative approach, and one which I prefer, is that it is an error to
use the usual language primitives for arithmetic with NaN's (as usual, if
you compile for safety, this error should be detected at runtime, if you
compile for speed, you simply get undefined results).  You should have to
use special IEEE primitives ("is_nan(x)", "ieee_less(x,y)") to get at the
IEEE meanings when available.

Why do I prefer this? IEEE operations are implementation specific and
unportable, in the sense that not all implementations of a programming
language support them. When you rely on implementation specific and
unportable features, you should have to express that reliance explicitly
so that when I have to port your code, I can figure out what I have to
change.

Note that even if every computer in the universe supported IEEE floating
point, you would still want to make a clear distinction between the usual
numerical operations and IEEE-specific behavior. The reason is that you
might want to use your numerical code with software implementations of
other kinds of floating point numbers, implementations that may not be
able to support IEEE features.

					Thomas.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: jlg@cochiti.lanl.gov (J. Giles)
Subject: Re: IEEE arithmetic handling
Reply-To: jlg@cochiti.lanl.gov (J. Giles)
Organization: Los Alamos National Laboratory
Date: Tue, 17 Nov 1992 19:42:06 GMT
Keywords: arithmetic

jlg@cochiti.lanl.gov (J. Giles) writes:
> Unfortunately, the Fortran standard does not conform to
> IEEE (in fact, it conflicts with it in some places - like with regard
> to negative zero).  And the Fortran standard does not require the same
> conversion accuracy as the IEEE floating point standard.  

bill@amber.csd.harris.com (Bill Leonard) writes:
|> I have a couple of nits to pick with this.  First, Fortran does not
|> *conflict* with the IEEE vis-a-vis negative zero.  It merely says that the
|> processor must never *output* a negatively-signed zero.  That doesn't mean
|> that variables in the program cannot contain such a value.

Doesn't IEEE say that some form of output must be available for which
output followed by input returns the same value?  If the external
representation is not even *allowed* to have the minus sign, how do you
preserve it?

|> [...]
|> Were Fortran to require IEEE accuracy, then you would only see Fortran
|> implemented on IEEE machines (or machines that exceeded the IEEE
|> requirements).  That would make a lot of Fortran users unhappy.

Quite true.  But Fortran *could* make a more general requirement based on
Fortran 90's "model numbers" which could place *some* constraints on
conversion precision and other operations.  For example, it could state
the requirement I gave earlier: provided the external representation
carries enough digits, output followed by input of the same string should
return the original number.

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 is true whether
you truncate or round to `m' digits.  The Fortran standard could easily
have called for this precision - at a minimum - to be provided for
floating-point format conversions.  It could easily have required this to
be the precision used for list-directed output (with the allowance that
trailing zeros could be omitted).  It could easily have allowed minus
signs on numbers with only zero digits.  Etc..  The standard does none of
those things - thus allowing a standard conforming Fortran which has none
of these properties and which also is not required to conform to IEEE even
if the hardware *does*.

-- 
J. Giles
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: johnr@ee.uts.edu.au (John Reekie)
Subject: Re: Modulo n arithmetics
Reply-To: johnr@ee.uts.edu.au (John Reekie)
Organization: Compilers Central
Date: Tue, 17 Nov 1992 06:35:42 GMT
Keywords: arithmetic, DSP

>I am wondering if any languages or application heavily rely on
>modulo arithmetics

Realtime digital signal processing uses modulo addressing ranges a _lot_
for circular buffers and shift registers (for signal delays, digital
filters, convolution, correlation).  Most DSP chips have special hardware
and registers to support this addressing mode -- that is, an address
register that goes below a given base address or above a limit address is
"wrapped" back to the end or start of the range. Unfortunately, most
compilers do not at present support this hardware feature (0.5 of an
exception that I know of), mainly because the source language usually used
(i.e. C) has no way of expressing it.

Regards

John Reekie
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: andrewb@lynx.cs.washington.edu (Andrew Berg)
Subject: Re: Is this a new idea?
Reply-To: andrewb@lynx.cs.washington.edu (Andrew Berg)
Organization: Computer Science & Engineering Dept., Univ. of Washington, Seattle
Date: Mon, 16 Nov 1992 00:38:33 GMT
Keywords: lex, parse, performance

Pre-tokenization is probably a good idea, but one that Borland has used
since Borland C++ 2.0 is pre-compiled headers.  They have (needlessly)
strict rules on what the system will do, but since header files in C
typically only introduce information to the symbol table anyhow (at least
in my header files) this would seem to me to be a real advantage in any
large system.

--
andrewb@cs.washington.ed
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: tchannon@black.demon.co.uk
Subject: Re: optimizing for caches
Reply-To: tchannon@black.demon.co.uk
Organization: Compilers Central
Date: Sat, 21 Nov 1992 01:20:32 GMT
Keywords: architecture, performance

> So the relative cost of a cache miss has already risen from about 1.4
> instructions to > 5 instructions, and the Viking clock speed is still only
> 40MHz; the technology exists now to build processors running at 150MHz
> (e.g. Alpha), which will take the cost of a cache miss over 20
> instructions.
 
Ignoring the problems of very large memory arrays and other secondary
effects the access times of dy ram can with good design be rather faster
than you suggest. This is what page mode and static column mode are about.
Many accesses may be possible each with a 40ns or so cycle time and this
is quite different from the classic mode where the cycle time would be
100..120ns.

Wider data buses and possibly interleave can also help.

The trend to longer refresh times helps with being able to hold burst for
longer. I have no doubt that that are lot's of tricks I don't know about.

How close are we to being severely limited by physical size problems? (I
have in mind that a very fast systems cannot be physically large, inches
matter)

  TC. 
    E-mail: tchannon@black.demon.co.uk or tchannon@cix.compulink.co.uk
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Subject: Re: In lex, how do I begin in a state??
Reply-To: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Organization: The Johns Hopkins University CS Department
Date: Sun, 22 Nov 1992 22:25:44 GMT
Keywords: lex

James A. Cadwell <cadwell@seattleu.edu> writes:
>In lex, one uses BEGIN STATE-NAME in an action to place lex in a
>state.  My question is: how do I begin in a state?? That is, have
>a state in effect before any input is read.

The Moderator adds:
>[In short, you have to execute a BEGIN before the lexer starts scanning.
>Code put at the front of the rules section is run whenever you call yylex(),
>so you could do something like this:
>
>%%
>%{
>	static int first_time = 1;
>
>	if(first_time) {
>		BEGIN FOOSTATE;
>		first_time = 0;
>	}
>...
>
>The new version of O'Reilly's lex&yacc, much of which I wrote, explains this
>in more detail. -John]

	This is, of course, the right way to do things.  However, if
you're in a hurry, or are writing a lex-only program (using the _main in
the lex library), one can use the undocumented start state INITIAL.  This
is probably a Bad Idea as far as portability goes, but if you're doing
something simple like stripping comments with a two-line lexer, it's
probably sufficient.

	As far as the Moderator's suggestion goes, it's probably better to
put the lexer into a state by hand before calling yylex() by adding a
special initialization routine in the "user subroutines" section of the
lex file, after the rules:

<START>.....
...
%%
int
kick_start_lexer() { BEGIN FOOSTATE; }

and then manually initialize the lexer before calling yylex():

extern int kick_start_lexer();

int
main()
{
   ...
   kick_start_lexer();
   if (yyparse())) ...
   ...
}

	This way, the test to see if the lexer is being called for the
first time is eliminated.  Hey, it's only one instruction, but that's one
comparison _per_token_.  These things start to add up after a while!  :-)
--
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.
Newsgroups: comp.compilers
From: mareb@levels.unisa.edu.au
Subject: re: Grammar Algebras?
Reply-To: mareb@levels.unisa.edu.au
Organization: University of South Australia
Date: Tue, 17 Nov 1992 23:59:47 GMT
Keywords: parse, theory

Clearly you can't intersect CFGs - since the intersection may not be a
CFG. I have been playing with the intersection of CFGs lately for a couple
of reasons.

1. we wanted to know how to parse a^n b^n c^n d^n ... quickly.  Since we
can parse a^n b^n c^m d^m ... in time O(N) {does anyone have a reference
to a published proof that LR(k) parsing is O(N)?} and a^* b^i c^i d^j e^j
... we just run two parsers in parallel (or serially) and if they both
succeed, the string is in the above CSL.

Perhaps we are lucky that CFLs are not closed under intersection!

Another observation is that this method of producing any type of grammar
for the above CSL is probably easier and more intuitive than trying to
produce a CSG. I find that it takes quite a bit of experience to be able
to work effectively with CFGs; I know very few people who can look at a
CSG and have much of a idea what it does and doesn't `say'.

2. a second reason for wanting to parse a^n b^n c^n ... is that people
keep asking me about parsing 2D syntax. Mostly they mean tables. I tell
them to just linearise their language and build a parser. If they have the
above problem, parse a^* b^* c^* and check the lengths with semantic
rules. So far, they've all been happy. The above trick is nice theory but
hasn't proven of much practical significance for me.

	regards,
	Bob Buckley

School of Computer and Information Science
University of South Australia
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: sanjay@equalizer.cray.com (+Sanjay Krishnamurthy)
Newsgroups: comp.compilers
Subject: Re: Code Optimization questions
Keywords: optimize, performance
Date: 14 Nov 92 01:43:32 GMT
Article-I.D.: comp.92-11-074
Reply-To: sanjay@equalizer.cray.com (+Sanjay Krishnamurthy)
Organization: Compilers Central

Steve Boswell <whatis@ucsd.edu> asks:

>[1] Is there any info on optimizers that take advantage of profiler
>   information? 

You need to look at all the papers (~zillion) on the IMPACT compiler at
the University of Illinois. This compiler bases its optimizations on a
"Superblock" which is basically a special trace. I use "The Superblock: An
Effective Technique for VLIW and Superscalar compilation," Hwu et al, to
appear in Journal of Supercomputing, 1993, as my primary reference. You
should be able to get a bunch of tech. reports from hwu@crhc.uiuc.edu
describing the use of profiling info to do everything from procedure
inlining to scheduling.

>[2] Is there any info on optimizers that take advantage of runtime
>   assertions?  This can help with anti dependencies,......

There's a paper titled "Run time disambiguation" written by Alex Nicolau
which appeared in the IEEE Transactions on Computers sometime in the past
4 years (very helpful, eh??) You should look at this to find out how
static dependence analysis can be aided with runtime assertions. 

>[3] If statement A has a def-use chain to statement B, does it follow
>   that statement B has a use-def chain to statement A?  Is this an
>   "if and only if" relation?

You mean "Is this a symmetric relation?" Sure appears to me.

-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.
Xref: sparky comp.compilers:1882 comp.lang.modula2:1395 comp.lang.pascal:6618
From: pardo@cs.washington.edu (David Keppel)
Subject: Re: And speaking of fast compilers...
Reply-To: pardo@cs.washington.edu (David Keppel)
Organization: Computer Science & Engineering, U. of Washington, Seattle
Date: Mon, 23 Nov 1992 21:49:42 GMT
Keywords: performance, design, testing, comment

A while back I wrote about how the Brand X compiler took 6 minutes to
compile a 7,000-line program made up of one-page functions.  And how Brand
Y took 40 minutes; over 1.5 hours with optimization turned on.

Well, according to my conversational friend, the latest Brand Y is down to
10 minutes and 25 minutes with optimization on.  He's also had a chance to
test it on the latest and greatest from some other vendors and he found
(among other things):

  Brand I: 10 minutes with optimization off, fails with optimiation on.
  Brand J: Crashed the brand J hardware.
  Brand K: Based on the brand I front-end, fails during code generation.

All are validated Ada compilers.

I also heard from Vinod Grover <grover@Eng.Sun.COM> that he knows of an
Ada compiler front end that took 14 hours on a VAX 11/780 to parse and
semanticise a 3-line Ada program.  The problem was that the overload
resolution phase of the front end was a two-pass backtracking algorithm
and the 3-line program had 6 levels of overloading of every symbol.


To summarize: language design is tricky and correctness doubly so.

"A program that produces wrong answers twice as fast is infinitely
slower." -- John Ousterhout

	;-D on  ( Slowing the way to success )  Pardo
[Back when I was writing an F77 compiler, I also found that I could pass
a lot of validation tests with amazingly broken versions of the compiler.
-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:1900 comp.lang.c:16687 comp.lsi:698
From: jack@tequila.vlsi.auc.dk (Jack Bukholdt Andersen)
Newsgroups: comp.compilers,comp.lang.c,comp.lsi
Subject: Reconfigureable C-compiler for small microprocessors
Keywords: C, question
Date: 17 Nov 92 10:16:21 GMT
Article-I.D.: comp.92-11-090
Reply-To: jack@tequila.vlsi.auc.dk (Jack Bukholdt Andersen)
Organization: Aalborg University Center, Denmark

We are looking for a C-compiler, which allows the target instruction-set
to be reconfigured. Something like GNU gcc - but for much smaller
processors.

The compiler is to be used for a small customized processor, implemented
in an ASIC. About as powerful as a 8051/68HC11 - but maybe not quite as
"intelligent".

Please - can anybody help with references to companies marketing such a
beast - or perhaps a PD/ShareWare version available via FTP ?

And - for readers of comp.lsi - perhaps somebody have got pointers to a
parameterised processor as well, preferably - but not necessarily - to be
used in Mentor GDT ?

Answers by Email or follow-up. Anyway - we will summarise to the net.

Thank you !

Jack Andersen
Aalborg University, Denmark
jack@tequila.vlsi.auc.dk
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: umfinla5@ccu.umanitoba.ca (Doug Finlayson)
Subject: Re: Sources from J.P. Bennet's book
Reply-To: umfinla5@ccu.umanitoba.ca (Doug Finlayson)
Organization: University of Manitoba, Winnipeg, Canada
Date: Sat, 21 Nov 1992 18:18:06 GMT
Keywords: books

pwau@alcbel.be (Patrick de Wauters) writes:

>Is there an ftp-site from where I can download the sources from J.P.
>Bennet`s excellent book "Introduction to Compiling Techniques - A first
>Course Using Ansi C, Lex and Yacc"?

Hi , on page 234 there is information describing how to get the compiler
and assembler source code through email.

Doug Finlayson.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers