RE: [Open64-devel] LNO+WOPT structure and interface

[Chan, S. C <sun...@in...>]

> -----Original Message-----
> From: Jason Eckhardt [mailto:jl...@ow...]
> Sent: Monday, September 09, 2002 8:34 AM
> To: ope...@li...
> Subject: [Open64-devel] LNO+WOPT structure and interface
> 
> 
> 
> At Rice University, we wish to build a restructuring optimizer for
> Co-Array Fortran, UPC, etc.  Of course, it is our hope to build on
> of the Open64 infrastructure to avoid re-writing an entire optimizer.
> 
> I've spent a few days familiarizing myself with the code of
> the LNO and WOPT components.  I now have some general questions
> about their overall structure.  Most of this will be obvious to the
> developers of the code -- but there is no real documentation on
> it (the published papers by SGI do not go into the kind
> of implementation detail I need, and I can't find any publications
> discussing the LNO or its interface with WOPT).
> 
> First, it appears that WOPT builds yet another IR (CODEREPs/STMTREPs)
> and then "throws away" the input WHIRL.  An SSA variant is 
> built and then
> analyses and transformations are performed on this representation.
> Finally, WOPT re-creates WHIRL for output.  Apparently, after WHIRL
> emission, SSA/CFG and the CRs/SRs are deleted.  Thus, from my newbie
> point of view, it seems SSA can only be exploited from within WOPT
> itself.  My first question, then, is there a way for newly developed
> components to easily utilize SSA from WOPT?  Is there an interface to
> it that I missed?

Your observation is true that WOPT builds yet another IR. The SSA is really
for this internal IR. If you look at IPA, we actually keep slices of SSA as
part of the summary info. This should partially answer your question about
utilizing SSA from WOPT. BTW, a bit of advertisement, Fred Chow will be
taking part in the tutorial coming up at PACT02. He will talk about Wopt
internals and data structure. If you are going, we can spend some time
discuss your issue in more depth.

> 
> This led me to wonder how does LNO utilize SSA in its operation?
> Apparently, it doesn't!  Instead, it appears to use "classic style"
> def-use information produced by WOPT (this information is created
> during the WHIRL emit phase, I believe).  By "classic" I mean
> an unfactored form where (for example) multiple definitions may
> reach a use.
> 
> So LNO first invokes WOPT (in preopt mode) to collect def-use
> and aliasing information.  LNO then performs its analyses and
> transformations based on these.
> 
> Am I correct about this structure?  Its surprising to discover
> that such a recently developed loop optimizer does not utilize
> WOPTs SSA -- especially in light of the large amount of effort put
> into making WOPT fully SSA-based.

You are correct about this structure. Main reason, my own interpretation, is
that when we started out (1995 or 6?), we don't really know enough about
SSA. Its just too  risky to have two major components to based on a
technology we don't know enough yet. Plus we have a very tight schedule. We
were given 18 months to ship a compiler (from scratch) that will beat the
existing compiler. Remember that the compiler was developed as a production
compiler first, and its the developers' desired to also make that a research
compiler. I believe the LNO folks see how to deal with uniform cost
model/transformation is more interesting. I'll leave Dror to give you some
insight into his decision (if he cares to reveal that).

> 
> A downside of this structure is that has led to a number of places
> in LNO that are far less efficient than they might otherwise be.

LNO is actually quite fast. In fact, I'll be surprised if you find that it
spends > 30% of the entire compile time given any program. I don't know of
such cases (other than degenerate ones).

> But more importantly, it leaves me wondering how I might leverage
> LNO+WOPT for our restructurer.
> 
> Ideally, we would like to just be part of LNO.  That is, we 
> wish wish to
> operate at a high-level and need the dependence analysis 
> information that
> is already available in LNO.  Furthermore, the elementary 
> transformations
> (fusion, blocking, etc) are there to build on.  However, we would
> also like the benefit of a sparse representation (like WOPTs SSA)
> and a control-flow graph (it wasn't mentioned above, but it also
> appears that LNO does not build a control-flow graph).

LNO only work on loops with classical loop bodies. OTOH, building one is
quite fast also.

> Some of our algorithms assume the existence of SSA.  It is possible
> that these algorithms can be adapted to work on standard use-def
> info (likely in a more cumbersome and/or inefficient form) like
> the rest of LNO, but obviously we'd prefer not.
> 
> Any comments on a sensible way to simultaneously "get" WOPTs SSA/CFG
> and LNOs infrastructure would be greatly appreciated.
> 
> Thanks, Jason Eckhardt.
> 
> 
> 
> 
> -------------------------------------------------------
> This sf.net email is sponsored by: OSDN - Tired of that same old
> cell phone?  Get a new here for FREE!
> https://www.inphonic.com/r.asp?r=sourceforge1&refcode1=vs3390
> _______________________________________________
> Open64-devel mailing list
> Ope...@li...
> https://lists.sourceforge.net/lists/listinfo/open64-devel
>