From: preston@dawn.cs.rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Re: Monotone Dataflow problems....
Keywords: optimize, bibliography
Date: 4 Oct 92 16:26:57 GMT
Reply-To: preston@dawn.cs.rice.edu (Preston Briggs)
Organization: Rice University, Houston

V.C. Sreedhar writes:

>pointers to all the optimization problems that are very important for
>generating good code (for scalar, superscalar, and parallel machines)? 

For a scalar machine, I think the following optimizations are important

	partial redundancy elimination (includes elimination of
		common subexpressions and loop-invariant expressions)
	value numbering
	dead code elimination (unused expressions)
	constant propagation
	strength reduction
	instruction scheduling
	register allocation
	memory hierarchy management (scalar replacement, blocking for
		cache, loop interchange, unroll and jam)

Little different is required for a superscalar machine except (perhaps) a
more sophisticated instruction scheduling technique.

You asked for a classification in terms of forward, backward, and
bidirectional.  These terms usually apply to "problems" whereas I've
cleverly listed a bunch of "optimizations".  Typically, many "problems"
(e.g., live variables or reaching definitions) must be solved for a single
optimization.  Part of the interesting work in the area is discovering new
ways to accomplish a given optimization in terms of different data-flow
problems.  To me, interesting solutions are faster, smaller, or more
effective than earlier attempts.  Simpler solutions are also nice, but not
(in my opinion) at the cost of sped, space, or effectiveness.  Of course,
incorrect solutions need not apply.


>Swartz (?) and Cocke book and Dragon book are a
>good reference for many of the analysis. I feel these two books are not
>the best ref. for recent results based on SSA-form and Sparse Eval. Graph
>methods.

Schwartz.

Yes, these two books suffer somewhat in that the authors foolishly ignored
future results :-) The only references today are the papers.

  title="Detecting Equality of Variables in Programs",
  author="Bowen Alpern and Mark N. Wegman and F. Kenneth Zadeck",
  booktitle=popl15,
  year=1988,
  month=jan,
  pages="1--11"

		A form of global value numbering


  title="Global Value Numbers and Redundant Computations",
  author="Barry K. Rosen and Mark N. Wegman and F. Kenneth Zadeck",
  booktitle=popl15,
  year=1988,
  month=jan,
  pages="12--27"

		An aggressive form of partial redundancy elimination


  title="An Efficient Method of Computing Static Single Assignment Form",
  author="Ron Cytron and Jeanne Ferrante and Barry K. Rosen and
          Mark N. Wegman and F. Kenneth Zadeck",
  booktitle=popl16,
  year=1989,
  month=jan,
  pages="25--35"

		How to build SSA form efficiently


  title="Efficiently Computing Static Single Assignment Form and the
                 Control Dependence Graph",
  author="Ron Cytron and Jeanne Ferrante and Barry K. Rosen and Mark
                 N. Wegman and F. Kenneth Zadeck",
  pages="451--490",
  journal=toplas,
  year=1991,
  month=oct,
  volume=13,
  number=4

		Archival version of the POPL paper,
		more discussion


  title="Automatic Construction of Sparse Data Flow Evaluation Graphs",
  author="Jong-Deok Choi and Ron Cytron and Jeanne Ferrante",
  booktitle=popl18,
  year=1991,
  month=jan,
  pages="55--66"

		An SSA-like method to solve forward and backward
		problems


>Also can someone give me reference for dataflow/optimization performed on
>explicit parallel programs? Can we directly use traditional methods into
>the parallel world.

We can continue using traditional forms of analysis; however, some new
problems must be solved (e.g., laying out data across multiple
processors).  Note that I would include such things as dependence analysis
(developed to attack vectorization) as important for scalar machines.

You're asking very broad questions.  Your best move is probably to start
reading around in the proceedings from conferences such as PLDI, POPL,
Supercomputing, PPoPP, and all the other parallel conferences.  Or, if
you're a grad student, discuss all this with your advisor.

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