HDTenEightyP/NetNews huggingface dataset:
From: smith@das.harvard.edu (Mike Smith)
Subject: Re: Optimizations for Pipelined Processors
Reply-To: smith@das.harvard.edu (Mike Smith)
Organization: Harvard University
Date: Fri, 22 Jan 1993 15:35:26 GMT
Keywords: optimize, parallel

s2861785@techst02.technion.ac.il (Alon Ziv) asks about implementing
compiler back-ends for pipelined processors and (basically) about
pipelining scheduling.

|> So, the question is: _is_ there any research going on for these ideas?  I
|> would assume that it has started, and---if so---would very much like to
|> have some references about progress so far, as it seems to be
|> (potentially, at least) VERY interesting.

Yes, lots.  In the mid-1980s (during the research on RISC processors),
there was considerable work done on pipeline scheduling to basically
handle load delay slots, branch delay slots, and FP latencies.  Today, the
work on pipeline scheduling has moved to the world of superscalar and
superpipelined processors (which require scheduling to get good
performance).  There has been a lot of work, especially from Universities
like U. of Illinois (Wen-mei Hwu's project called IMPACT) and Stanford
(the TORCH project) and from research centers like IBM Israel (Bernstein
et al.) and IBM Watson (Ebcioglu et al) to name a few.  A lot of this work
is similar to the VLIW work originally done by Fisher (Trace Scheduling)
and Nicolau (Percolation Scheduling).

You can find a lot of interesting papers by looking through the recent
proceedings from ASPLOS, ISCA, MICRO, and PLDI.

I just finished a Ph.D. dissertation that describes an architecture and
back-end scheduler for superscalar/superpipelined processors.  This thesis
has a large background section and bibliography which you might find
interesting.  My thesis is available via anonymous ftp from
velox.stanford.edu (36.22.0.168).  Once you are in,
  cd pub/papers
  get thesis.ps

Hope you find it useful,
Mike Smith
smith@das.harvard.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: Peter Cupit <qpit@werple.apana.org.au>
Subject: Micro C, Dunfield
Reply-To: Peter Cupit <qpit@werple.apana.org.au>
Organization: Compilers Central
Date: Tue, 26 Jan 1993 04:12:35 GMT
Keywords: C, question

I am interested in the Micro C compilers from Dunfield Development
Systems, these target the 6809, 6811, 68HC16, 8051/52, 8080/85/z80, 8086
and 8096.

P.O. Box 31044, Nepean, Ontario Canada.  Tel: (613) 256-5820, Fax/BBS
(613) 256-5821, in case anyone else is interested.

I would like to hear from anyone who has used this software (or info from
anyone who enquires as a result of this info) btw the add says just $99
for a complete development kit, but what does this mean?

Thanks for any info,

Peter Cupit.
qpit@werple.apana.org.au
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: rooi@duteca3.et.tudelft.nl (Mark de Rooi)
Subject: Re: Benefits of hand-coded bottom-up parsers
Reply-To: rooi@duteca3.et.tudelft.nl (Mark de Rooi)
Organization: Delft University of Technology, Dept. of Electrical Engineering
Date: Thu, 28 Jan 1993 10:40:43 GMT
Keywords: parse, courses

> I don't really want to fan the flame wars, but I must stress the benefits
> of hand-coding an LR parser if your goal is to understand parsing.

Another way to gain real insight into LR parsing is to write your own LR
parser generator. A few years ago I wrote a yacc-like parser generator. It
was an Aha-erlebnis.

Mark
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,comp.lang.fortran
From: dodd@mycenae.cchem.berkeley.edu (Lawrence R. Dodd)
Subject: Re: Wanted: folk theorems in Fortran Programming.
Reply-To: dodd@mycenae.cchem.berkeley.edu (Lawrence R. Dodd)
Organization: Dept of Chemical Engineering, Polytechnic Univ, NY, USA
Date: Wed, 27 Jan 1993 09:20:19 GMT
Keywords: Fortran

"Steve" Stevenson <steve@hubcap.clemson.edu> writes:
> I am trying to make a catalog of folk wisdom in fortran programming.

My personal favorite is the one discussed on page 137 of the 1st edition of
Numerical Recipes (Fortran edition, of course):

BAD

P = c(1) + c(2)*x + c(3)*x**2 + c(4)*x**3 + c(5)*x**4

GOOD

P = c(1) + x*(c(2) + x*(c(3) + x*(c(4) + x*c(5))))

It is a little harder to read but you won't be `summarily executed'
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,comp.lang.fortran
From: steve@hubcap.clemson.edu ("Steve" Stevenson)
Subject: Wanted: folk theorems in Fortran Programming.
Reply-To: steve@hubcap.clemson.edu ("Steve" Stevenson)
Organization: Clemson University
Date: Tue, 26 Jan 1993 16:45:55 GMT
Keywords: Fortran, question

I am trying to make a catalog of folk wisdom in fortran programming. I already
have a some theorems.  For example:

        BAD           GOOD
x = y/2.0          x=y*0.5
a**5               (a*a)*(a*a)*a
2.0*x              x+x

I would appreciate any such words of wisdom you might have.
I'll collect and broadcast a compilation.

Steve
--
Steve (really "D. E.") Stevenson           steve@hubcap.clemson.edu
Department of Computer Science,            (803)656-5880.mabell
Clemson University, Clemson, SC 29634-1906
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: swl26@cas.org (Steve Layten x3451)
Subject: justify use of flex vs lex
Reply-To: swl26@cas.org (Steve Layten x3451)
Organization: Compilers Central
Date: Mon, 25 Jan 1993 14:48:49 GMT
Keywords: flex, lex, question, comment

I need to use flex instead of lex for a job I have that exceeds capacities
of some lex features.  I want to put this into a "production" job stream,
and our current "standards" seem to discourage use of public-domain code
in production, the standard managment argument being that we should use
vendor-supported code so we don't have to spend time maintaing the code
ourselves.  I must justify the use of this "non-supported" code in
production.

I would appreciate hearing comments from this community regarding
arguments for or against the use of flex vs. the vendor-supplied lex.
Some additional considerations which I think are important are:

   Support across multiple platforms/environments - flex can be ported to
   all of the environments we use, and thus we would be sure to have a
   consistent environment.

   Fewer constraints or "limits" built in.

   I believe that support for flex is "better" than most vendors; how many
   in this list would say that UNIX vendors focus much time or effort in
   keeping their "lex" up to date and bug-free?

Feel free to respond via e-mail or to the group.  I'll summarize e-mail
esponses if appropriate, so please indicate in any private communication
if you wish that it not become public.

Thank you for your time.

Steve Layten
--
Steven W. Layten, Senior Engineer
Chemical Abstracts Service, PO Box 3012, Columbus, OH 43210    +1 614 447 3600
INET: swl26@cas.org         BITNET: swl26@cas      UUCP: osu-cis!chemabs!swl26
[The reality is that lex is still riddled with bugs after over 15 years of
alleged vendor support, while flex is nearly bug-free.  When revising
O'Reilly's lex&yacc, I found many lexers needed fiddling to work around lex
bugs, a few I couldn't get to work at all with lex.  They all work with flex.
-John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: tchannon@black.demon.co.uk (Tim Channon)
Newsgroups: comp.compilers
Subject: Re: Recursive descent parsing is better than LL(1)
Keywords: LL(1), parse
Date: 23 Jan 93 22:43:00 GMT
Article-I.D.: comp.93-01-172
Reply-To: tchannon@black.demon.co.uk (Tim Channon)
Organization: Compilers Central

> I present a simple contra-example:
> 
> Consider the language defined by the next CFG:
> 
> S -> A
> S -> B
> A -> `x' A `y'
> A -> `a'
> B -> `x' B `z'
> B -> `b'
> 
> SID uses elimination of left recursion, factorisation and substitution to
> search for a better grammar.

I assume it is a matter of what you ask SID and by the time you are at S
it is too late to branch or is it.

Is this a valid LL(1) solution? (diagnostics are too large to post but all
				is well)

S    =  'x' {   'x'
              | 'a'
              | 'b'
            }
            ('y' | 'z')
      | 'a'
      | 'b'.
      
producing this exact output

    IF (sym = XSym) THEN
      Get;
      WHILE (sym = XSym) OR
            (sym = ASym) OR
            (sym = BSym) DO
        IF (sym = XSym) THEN
          Get;
        ELSIF (sym = ASym) THEN
          Get;
        ELSE
          Get;
        END;
      END;
      IF (sym = YSym) THEN
        Get;
      ELSIF (sym = ZSym) THEN
        Get;
      ELSE Error(11);
      END;
    ELSIF (sym = ASym) THEN
      Get;
    ELSIF (sym = BSym) THEN
      Get;
    ELSE Error(12);
    END;

  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: Mayan Moudgill <moudgill@cs.cornell.EDU>
Subject: Looking for benchmarks/code with balanced branches
Reply-To: Mayan Moudgill <moudgill@cs.cornell.EDU>
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Sat, 23 Jan 1993 06:31:26 GMT
Keywords: optimize, question

I've been wondering what percentage of all branches are roughly balanced
i.e. are taken no more than say 75% of the time, but are taken at least
25% of the time. What are good references for this?

Also, has anybody got code that contains large numbers of these branches?

:)
Mayan
(moudgill@cs.cornell.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: kieron@root.co.uk (Kieron Drake)
Subject: Re: [TDR] Token-Based Compilers
Reply-To: kieron@root.co.uk (Kieron Drake)
Organization: UniSoft Ltd., London, England
Date: Mon, 25 Jan 1993 18:22:55 GMT
Keywords: C, interpreter

tdarcos@mcimail.com (Paul Robinson) writes:
>I'd like to ask what people think of the idea of Compilers that generate
>ficticious machine code, i.e. tokens for an optimized machine which is
>then interpreted on the target.

One of the classic early uses of this technique was by Martin Richards
when he used OCODE as the intermediate code for BCPL compilers. The first
issue (I think it's the first issue) of Software Practice & Experience has
a discussion of the portability issues. (actually it's a bit more complex
than that: he used two levels of intermediate code; intcode & OCODE with
intcode being amazingly simple to interpret so you could get the intcode
version of the compiler up a.s.a.p. and then take time to get your
OCODE-driven back end working). Another reference is "BCPL: The Language
and its Compiler", Richards & Whitby-Strevens.

OCODE is for a fairly simple stack based virtual machine. One can get
pretty good code generated for modern architectures, which have lots of
registers, by simulating register contents as long as possible and using
graph-colouring techniques for register allocation.  That gives a fairly
simple back-end which is reasonably configurable across machines of
similar architecture, produces reasonable code quickly and can be
implemented fairly fast. All my opinion/experience, of course.

	kieron
--
kieron@root.co.uk	Tel: +44 71 729 3773 (or 071 729 3773 in the UK)
Kieron Drake		Fax: +44 71 729 3273 (or 071 729 3273 in the UK)
Senior Consultant, UniSoft Ltd., Spa house, Chapel Place, Rivington Street,
London EC2A 3DQ, 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: paco@cs.rice.edu (Paul Havlak)
Subject: Re: Loop-carried dependence analysis for scalar variables
Reply-To: paco@cs.rice.edu (Paul Havlak)
Organization: Compilers Central
Date: Tue, 26 Jan 1993 16:27:02 GMT
Keywords: optimize, analysis, parallel, bibliography

    Someone asked in private mail:

> What do you do about arrays in the SSA form -- the treatment in the TOPLAS
> article was very unclear.

    I don't think that there's a definitive answer yet.  What one really
wants is a dataflow form for subarrays, so that definitions of disjoint
subarrays aren't ordered even if they reach the same use.
    What we do, and what the PTRAN group does [1] is treat all ambiguous
definitions -- ones that modify part of the object or that only possibly
modify the object -- as uses and killing defs.  Ambiguous definitions
include assignments to potential aliases, possible modifications at call
sites, and partial array assignments.  For the partial array assignments,
this approach can be viewed as replacing

	A[I] = foo();

with

	A = g(A);

	where g(A) reads in all of A and replaces A[I] with foo()

    I have implemented this method, but we're only just starting to use it
in array dependence analysis.  The next step would be to come up with an
algorithm using this form and a subscript tester to build a more
dataflow-like array dependence graph than is currently common.
    Rosene [2] and Pugh & Wonnacott [3] seem to be the best references so
far on building dependence graphs with fewer non-dataflow (redundant
transitive) edges.  Neither uses SSA form.
    Parsons Selke [3] has a PDG form for arrays that she found useful for
reasoning about abstract semantics.  I haven't had a chance to deeply
consider the integration of this form and SSA form for use in our system.

[1] according to a presentation by Michael Burke at the December 1990
    International Workshop on Compilers for Parallel Computers in
    Paris, France

[2] @phdthesis{Rose:Dissertation,
    Author={C. M. Rosene},
    Title={Incremental Dependence Analysis},
    Month={March},
    Year={1990},
    school={Rice University},
    Note={Available as Rice COMP TR90-112},
    ignore={  } }

[3] Bill Pugh, David Wonnacott, "Eliminating False Data Dependences
    using the Omega Test," SIGPLAN PLDI '92

[4] @phdthesis{Selke:Dissertation,
    Author={Rebecca Parsons Selke},
    Title={A Semantic Framework for Program Dependence},
    Year={1992},
    school={Rice University},
    ignore={  } }
----
Paul Havlak			Dept. of Computer Science
Graduate Student		Rice University, Houston TX 77251-1892
PFC/ParaScope projects		(713) 527-8101 x2738 	paco@cs.rice.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: dzabel@cs.tu-berlin.de (Dirk Zabel)
Subject: Re: current work on affix grammar code generators
Reply-To: dzabel@cs.tu-berlin.de (Dirk Zabel)
Organization: Technical University of Berlin, Germany
Date: Wed, 27 Jan 1993 14:04:58 GMT
Keywords: parse

Let me  add a reference to the ETA compiler generator, which was developed
over a quite long time at the TU Berlin and is based on the EAG formalism.

Cheers
        Dirk

-- 
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: parallel code optimization
Reply-To: sanjay@equalizer.cray.com (+Sanjay Krishnamurthy)
Organization: Compilers Central
Date: Thu, 21 Jan 1993 18:10:21 GMT
Keywords: parallel, optimize

>Does anyone have any references on parallelization of code optimization? 

You might want to look at:

Angelika Zobel
"Program structure as basis for parallelizing global compiler optimizations"
PhD thesis, CMU
Completed in 1992 or to be completed in 1993.

Actually, this is a reference from:
"Program structure as basis for parallelizing global register allocation"
but I have no idea  when and where it was published.

-Sanjay M. Krishnamurthy
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: haab@crhc.uiuc.edu (Grant Edward Haab)
Subject: Loop-carried dependence analysis for scalar variables
Reply-To: haab@crhc.uiuc.edu (Grant Edward Haab)
Organization: Center for Reliable and High-Performance Computing, UIUC
Date: Sat, 23 Jan 1993 23:37:12 GMT
Keywords: optimize, question


I am seeking information about implementations/research in the area of
loop-carried dependence analysis of scalar variables.  Many
loop-transforming optimizations including loop parallelization require
loop-carried dependence information for scalar variables as well as
arrays.  While there is a plethora of literature about loop-carried
dependence analysis for array variables, there seems to be very little
available regarding scalar variables.

If anyone has any pointers, contacts, or ideas, please send them via
e-mail.

Thank you.

Grant Haab - Center for Reliable and High-Performance Computing
work: 258 Computer & Systems Research Lab, MC-228, 	(217)244-1081
 	Univ. of Ill., 1308 W. Main, Urbana, IL 61801-2307 
 e-mail: g-haab@uiuc.edu -or- haab@crhc.uiuc.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: Paul Havlak <paco@cs.rice.edu>
Subject: Re: Loop-carried dependence analysis for scalar variables
Reply-To: Paul Havlak <paco@cs.rice.edu>
Organization: Center for Research on Parallel Computation
Date: Mon, 25 Jan 1993 17:50:44 GMT
Keywords: optimize, analysis, parallel, bibliography

haab@crhc.uiuc.edu (Grant Edward Haab) writes:
>I am seeking information about implementations/research in the area of
>loop-carried dependence analysis of scalar variables.  ...

In the PFC batch vectorizer/parallelizer, we built scalar dependences just
like array dependences, ignoring many dataflow issues (we built a separate
def-use graph for scalar optimizations).  This proved a mistake; the
scalar dependence edges required more space than the array dependence
edges.

In the ParaScope programming environment, we're now starting to use static
single-assignment (SSA) form [1] (I'm not sure what we used before).  The
advantages of SSA form for scalar dependence analysis are:

	* Building SSA form requires only linear time and space in
		extensive experiments.  It can be used to compute
		def-use (true dependence) and def-def (output
		dependence) edges.

	* A true or output dependence edge will be loop-carried with
		level L if and only if its sink is a pseudo-assignment
		(phi node) at a level-L loop header and its source is
		a definition in that loop.

The disadvantages of SSA form are:

	* Standard SSA form can have extraneous (dead, unuseful) phi
		nodes.  To prevent spurious (loop-carried or other)
		edges, you must delete these or never build them [2].

	* Use-def edges (anti-dependences) aren't part of SSA form.
		You can build them using the similar techniques of
		[2], or else use some conservative approximation,
		given that the anti-dependence successors of a use are
		a subset of the output-dependence successors of the
		use's true-dependence predecessor.

--Paul

[1]@article{CFRWZ:Efficient,
   Author={Ron Cytron and Jeanne Ferrante and
                Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck},
   Title={Efficiently computing static single assignment form
                and the control dependence graph},
   Journal=TOPLAS,
   Volume=13,
   Number=4,
   Pages={451-490},
   Month=Oct,
   Year={1991}}

[2] @inproceedings{CCF:Sparse,
    Author={Jong-Deok Choi and Ron Cytron and Jeanne Ferrante},
    Title={Automatic construction of sparse data flow evaluation graphs},
    BookTitle=POPL91,
    Pages={55--66},
    Month=Jan,
    Year={1991}}
--
Paul Havlak			Dept. of Computer Science
Graduate Student		Rice University, Houston TX 77251-1892
PFC/ParaScope projects		(713) 527-8101 x2738 	paco@cs.rice.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: brent@eng.uiowa.edu (Brent H. Pease)
Subject: Re: Architecture description languages for compilers?
Reply-To: brent@eng.uiowa.edu (Brent H. Pease)
Organization: Department of Elect. and Comp. Engr., University of Iowa, USA.
Date: Wed, 27 Jan 1993 04:14:14 GMT
Keywords: architecture, VHDL

> ... topics I'm interested in is machine descriptions--some vanilla way to
>  describe the architecture of a machine for purposes of code generation.

The obvious place to look is GCC which is probably the most successful
compiler to do this kind of thing. You will probably want to focus on RTL
and the "md" files(machine description).  brent.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: ssimmons@convex.com (Steve Simmons)
Subject: Re How many vector registers are useful?
Reply-To: ssimmons@convex.com (Steve Simmons)
Organization: Engineering, CONVEX Computer Corp., Richardson, Tx., USA
Date: Tue, 26 Jan 1993 13:22:15 GMT
Keywords: architecture, vector

On Convex, there are 8 vector registers of 128 elements which are 64 bits
in precision. Obviously, the question is not how many are useful but what
is the optimal number.  With 8 vector registers, we still do experience
vector register spills although that is dependent upon the code.  Needless
to say, a vector register spill is much worse than a scalar register
spill.

No, I do not know of any published studies that state the optimal number
of vector registers.  However, there are costs as more vector operators
are added.  These costs are expansion of instruction format, more complex
micro code within the vector unit, more complex chaining analysis in both
the compilers and vector unit, etc... Ultimately, this cost is paid for by
the custumer.

Thank you.

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