RE: [Open64-devel] PreOPT & WOPT

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

I forgot to mention that in our tutorial a few months back at PACT02, =
Fred Chow did a 2 hour presentation on internals of Wopt, where he =
covered a lot of the data structure and selected topics in the main =
optimizer. The slide should be posted in sourceforge soon, if not =
already.
Sun

> -----Original Message-----
> From: Chan, Sun C=20
> Sent: Thursday, October 31, 2002 8:54 AM
> To: lei...@cs...
> Cc: ope...@li...
> Subject: RE: [Open64-devel] PreOPT & WOPT
>=20
>=20
> I will be giving a tutorial on Micro-35. About 20-min of the=20
> tutorial will be used to cover more or less this area. The=20
> slides will be posted in sourceforge.
> Sun
>=20
> > -----Original Message-----
> > From: David Stephenson [mailto:dls...@sg...]
> > Sent: Wednesday, October 30, 2002 1:35 PM
> > To: lei...@cs...
> > Cc: ope...@li...
> > Subject: Re: [Open64-devel] PreOPT & WOPT
> >=20
> >=20
> > Lei Huang <lei...@cs...> wrote:
> >=20
> > > I am investigating the WOPT part in the Open64 now and I am a
> > > little confused about the PreOPT and WOPT. I appreciate=20
> if somebody
> > > could explain the differences between PreOPT & WOPT.
> >=20
> > The WHIRL Optimizer (WOPT) operates on code at a procedural level.
> > It handles one program unit at a time, and its analysis and code
> > transformation work on the entire procedure (as opposed to the more
> > local optimization performed by the code generator (CG), and to the
> > inter-procedural analysis handled by IPA).  In addition to=20
> performing
> > optimizing transformations to the code, WOPT computes def-use and
> > alias information for other phases of the compiler.
> >=20
> > For historic reasons, WOPT is sometimes called WOPT, OPT, SOPT,
> > PREOPT, the Global Optimizer, and Pre_Optimizer in the code files
> > and documentation.
> >=20
> > Depending on the level of optimization, WOPT may be invoked multiple
> > times on the same program unit during different compiler=20
> phases.  The
> > phases are enumerated as PREOPT_PHASES in the file=20
> be/opt/optimizer.h.
> >=20
> > At -O2 and above, the MAINOPT_PHASE of WOPT is invoked just=20
> before CG.
> > During MAINOPT, WOPT performs its full set of optimizations and
> > generates alias info for CG.
> >=20
> > At optimization levels higher than -O2, WOPT is also invoked for one
> > or more PREOPT phases.  During PREOPT phases WOPT generates def-use
> > and alias info for other parts of the compiler.  The various PREOPT
> > phases do not perform the full set of WOPT optimizations.  In
> > particular, the SSA partial redundancy elimination (SSAPRE)=20
> algorithm
> > is not run.
> >=20
> > For example, at -O3 (or -O2 -LNO), the loop nest optimizer (LNO)
> > invokes the PREOPT_LNO_PHASE of WOPT to generate the def-use info
> > needed to construct LNO's dependence graph.  If IPA is invoked
> > (often as -O2 -IPA, -O3 -IPA, or -Ofast), then IPA first invokes the
> > PREOPT_IPA1_PHASE of WOPT to generate procedure summary information
> > IPA requires.
> >=20
> >=20
> > > And as far as I understand, there are two kinds of data flow
> > > analyses in the Open64 based on bit-vector and SSA. Is it correct?
> >=20
> > WOPT uses SSA form for data flow analysis.  CG uses some bit-vector
> > analysis.  The other phases rely upon use-def info produced=20
> by PREOPT
> > phases of WOPT.
> >=20
> >=20
> > > If so, what kinds of analyses and optimizations have done for each
> > > kind of data flow analysis?
> >=20
> > The primary actions and optimizations performed by WOPT during
> > MAINOPT, roughly in order, are:
> >=20
> >   1.  WHIRL lowering, goto conversion and IVR loop canonicalization
> >=20
> >   2.  Conversion from WHIRL to hashed SSA form, including:
> >       Construction of WOPT's auxiliary symbol table, control flow
> >         graph, and SSA symbol version table
> >       Control flow analysis (dominance, loops)=20
> >       Alias classification and pointer analysis (both flow-free and
> >         flow-sensitive)
> >       Insertion of phi, chi, and mu nodes
> >       Dead store elimination
> >       Creation of hashed CODEMAP representation (including copy
> >         propagation)
> >=20
> >   3.  Induction variable recognition (IVR) and elimination, copy
> >       propagation, DCE (both unreachable code elimination and dead
> >       store elimination), and CFG transformations
> >=20
> >   4.  Partial redundancy elimination (SSAPRE), including:
> >       PRE of expressions (EPRE) including code hoisting, strength
> >         reduction, and linear function test replacement
> >       Value numbering full redundancy elimination (VNFRE)
> >       Dead code elimination
> >       Local register variable identification (RVI1)=20
> >       PRE of loads (LPRE) and stores (SPRE)
> >       Bitwise dead code elimination (BDCE)
> >=20
> >   5.  RVI and Emitter:
> >       Convert hashed SSA form back to WHIRL
> >       Register Variable Identification
> >       Emit WHIRL and alias info
> >=20
> > During the PREOPT phases, WOPT also emits def-use info but skips
> > SSAPRE (all of 4.) and RVI.
> >=20
> >=20
> > The Code Generator (CG) [with which I am less familiar -- consider
> > yourself warned] operates on a representation closer to machine
> > instructions (OPs), different from both WHIRL and from WOPT's hashed
> > SSA form.  CG's main phases are:
> >=20
> >   1.  CGEXP:  Construct CG's CFG, expand WHIRL into OP instructions.
> >=20
> >   2.  Various loop transformations, including if-conversion, partial
> >       and full unrolling, elimination of redundant loads and stores
> >       across iterations, and the software pipeliner (SWP)
> >=20
> >   3.  Instruction scheduling, including general code motion (GCM)
> >=20
> >   4.  General register allocation (GRA) -- allocation of registers
> >       that cross multiple blocks
> >=20
> >   5.  Local register allocation (LRA) -- allocation of registers
> >       localized to a single block
> >=20
> >   6.  More instruction scheduling
> >=20
> >   7.  CGEMIT -- Emit assembly code and elf/dwarf info
> >=20
> > In addition, two CG phases are each invoked several times=20
> intermingled
> > with the other phases:
> >=20
> >   A.  Control flow optimization (CFLOW) -- branch optimization, and
> >       the merging, reordering, cloning, and removal of basic blocks.
> >=20
> >   B.  Extended block optimizer (EBO) -- basically a peephole
> >       optimizer that also peeps around corners into nearby blocks
> >=20
> > Many of these phases are skipped or truncated if the optimization
> > level is -O0 or -O1.
> >=20
> >=20
> > The other compiler phases deserve mention:
> >=20
> >=20
> > The frontends [about which I know almost nothing] construct=20
> the symbol
> > table and WHIRL, perform some optimizations, and do other frontend-y
> > things.
> >=20
> >=20
> > The Loop Nest Optimizer (LNO) optimizes the memory=20
> performance of the
> > program's loop nests.  It performs dependency analysis,=20
> register/cache
> > blocking (tiling), loop fission and fusion, unrolling, automatic
> > prefetching, and array padding.
> >=20
> >=20
> > Inter Procedural Analyzer (IPA) works on the entire program, across
> > procedure and file boundaries.  It performs=20
> inter-procedural constant
> > propagation, inter-file inlining, dead function and variable
> > elimination, aliasing/address analysis, and more.
> >=20
> > The standalone inliner performs some inlining even when IPA is off.
> >=20
> > 							- David
> >=20
> > --=20
> > David Stephenson                http://reality.sgiweb.org/dlstephe/
> >=20
> >=20
> > -------------------------------------------------------
> > This sf.net email is sponsored by: Influence the future=20
> > of Java(TM) technology. Join the Java Community=20
> > Process(SM) (JCP(SM)) program now.=20
> > http://ads.sourceforge.net/cgi-bin/redirect.pl?sunm0004en
> > _______________________________________________
> > Open64-devel mailing list
> > Ope...@li...
> > https://lists.sourceforge.net/lists/listinfo/open64-devel
> >=20
>=20
>=20
> -------------------------------------------------------
> This sf.net email is sponsored by: Influence the future=20
> of Java(TM) technology. Join the Java Community=20
> Process(SM) (JCP(SM)) program now.=20
> http://ads.sourceforge.net/cgi-bin/redirect.pl?sunm0004en
> _______________________________________________
> Open64-devel mailing list
> Ope...@li...
> https://lists.sourceforge.net/lists/listinfo/open64-devel
>=20