Re: [tree-ssa, RFC] CFG transparent RTL expansion

[Jan Hubicka <hubicka at ucw dot cz>]

> > > simplistic example, but lets say profiling indicates that we ought to
> > > inline a(z) when we are processing b. How does that profile information
> > > from a() get propagated into the code which is inlined into b? There is
> > > no CFG for a(), just the trees. Do you have to read the info for a() in
> > > from the profile source each time its inlined or how does that work?
> > 
> > The inlining problem is not dealt with this particular patch, it solves
> > just SSA<->RTL interface, but you know what is my longer term plan, but
> > lets try to not run into very deep details with the inlining interface
> > right now.
> > 
> 
> I realize this. The main purpose of this patch is to enable other
> things, so I think we need to discuss those other things in order to
> make decisions on whether this is the best approach.

Sure, just wanted to point out that the scope of current patch is
limited, so we won't run into missunderstandings like with Zdenek's edge
redirection patch.
> 
> 
> > This is common problem with updating profile (not only after inlining
> > but after any code specialization - unrolling, tracing or whatever). 
> > 
> > The idea is when such conflict is noticed, the profile gets updates
> > somehow partly incorrectly (such that all basic block directly dominated
> > by edge being removed gets their frequencies subtracted).  The
> > optimizations expect such partially invalided profiles and must behave
> > sanely in presence of them.
> 
> 
> 
> Clearly, as long as the CFG exists, thats where the information ought to
> be stored. The only real question I want to deal with is should the CFG
> be kept after SSA right through to RTL, or when the CFG is destroyed,
> should the information be attached to the trees somehow and then used
> during expansion to annotate the new CFG rtl creates, and/or used to
> annotate the CFG for trees when the function is inlined. I think thats
> fundamentally where we have decisions to make, so I would like to work
> through the various differences. Im also about to go on vacation, so the

Yes, I got your plan.  I was considering this too, but it seemed like
serious effort as we need to develop alternate way to store profile
information in both tree and RTL form and to correctly update the
profile after expansion one needs to know almost everything present in
the CFG (original basic blocks, edges and their frequencies).

This is why I felt somewhat pleased when I run first into idea of simply
preserving the CFG.  Orignaly I didn't think about it and I din't
expected it to be easy.

> more I have to think about the better :-)
> 
> If we annotate the trees with profiling info when we are done with them,
> reasonably correct branch information can be propagated into the inlined
> code. If the CFG is the only place the information is stored, we'd also
> have to keep the CFG for a() around in order to put its information into
> into b() when its inlined. So we wouldn't just be keeping the trees for
> inlineable functions around, we'd have to keep objectified CFG's as
> well. Dont read that as me saying Im religously opposed to keeping CFGs
> right through to RTL. Its merely an observation.

I still tend to think about interface to inliner and interface to RTL
expansion as two different things (but would preffer to see common
answer to these :).  RTL expansion is definitly more complicated
operation when one comes to control flow changes and CFG has very great
utility here.

Basic inlining is easier.  If one thinks about what is needed, one needs
to be able to figure out count/frequency of call expression one is
inlining into and scale counts/frequencies in inlined function
accordingly.  For this one needs GIMPLE representation of basic block
and edge counts/frequencies/probabilities, but in other words, this is
CFG again.

I also believe that CFG will serve more utility once we get into more
complicated partial inlining.  For instance loop unrolling looks like
optimization that don't need CFG as well (you simply copy loop body
around) but you start need it later when you want to do more smart
tricks.  I think inlining is just the same.

Main issue here is the memory footprint.  Definitly CFG needs to be
built before inlining for early optimizations so we save some CPU cycles
but saving CFG for all inline functions can be expensive.
I did some testing once Steven put CFG into GGC and the footprint is
about 3-5% of overall GGC allocation.  This is not too disasterous
especially accounting the fact that profile is much more bloated than it
needs to be (I will work on this shortly) and that it is built 4 times
during compilation of single function.
> 
> 
> > The profile becomes less exact during optimization process, but overall
> > most of compilers (ORC, IMPACT for instance) are able to keep it by such
> > simplistics methods in good shape to bring benefits on BB reordering.
> > Most questions about the profile are easy, like "is this loop executed
> > insanily many times" or "is this basic block hot?"
> > these questions are relatively stable WRT slight degenerations.
> > 
> 
> Sure, but if we don't bring an inlinable function's profile into the new
> function when we inline it, we are throwing away reasonably correct
> information right off the bat. If you have all the probilities for a()'s
> branches, you ought to bring those into the code you create when you
> inline a() into b(). I'd like to make sure we do that.
> 
> Yes, The degenerations dont affect loop stuff so much as it does the
> lower level bits like register allocation and branch reversal/prediction
> at the rtl level, which will be the farthest away consumers of this
> information, the side effects of which we cant predict, just measure :-)
> 
> So we presumably have to read the information back in during the second
> compilation at the same point the information was written out during the
> first one, or we dont get a good mapping of block execution counts
> right? And thats somewhere in the SSA optimizer.

Yes.  While in theory you can read profile at different stages and
attempt to update it, in fact if you want to do that you need to do
exactly the same bookeeping you do to maintain the profile, just in
symbolic way so you know how to map read info to the CFG, so it does not
make things any better.
> 
> > > 
> > > 4- Does anyone other than me find the idea of inlining optimized trees
> > > appealing? I understand thats not on the table right now because there
> > > are difficulties with EH, at the very least. I would think we could
> > > encapsulate that info somehow, but clearly thats a problem that would
> > > need to be solved.
> > 
> > Sure it is appealing.  In order to do something sane, you need to do
> > some analysis that are not doable without CFG/early cleanups.
> > As pointed out already, the benefits of inlining estimate by time of
> > execution of the callee, while the costs is the size.  At the moment we
> > do have only the second information and our strategy is "do as many
> > inlinining as size constraint allows and lets hope that very fast
> > functions will get inlined too then"
> > 
> > For instance my current recursive inlining code would do much better job
> > if we are able to discover tail calls.  Another examples include partial
> > inlining if functions like
> > if (test)
> >    common fast path
> > else
> >    something large
> > 
> > can be inlined as
> > 
> > if (test)
> >   fast path
> > else
> >   do_something_large ()
> > 
> 
> OK, so we're on the same page there, someday we want to inline optimized
> functions :-)
> 
> 
> So where do you envision the inliner then? It would have to be done
> after the profiling information is read is in order to make use of it.
> Presumably immediately after.  You also plan to create a CFG aware
> inliner and objectify the CFG, and do the inlining from that? And then
> the inliner would work on SSA? right after DCE or somesuch place. SO the
> inliner will be an SSA inliner, or would we go out of SSA and back into
> SSA at that point?

While I don't have exact answer for all question about perfrect
construction of ideal compiler, the idea I do have in mind is:

1) parsing pass
   - parsing
   - production of function bodies
2) finalizing compilation unit pass
   - do reachability analysis and throw away unneeded functions, turn
     needed functions into generic and gimple in the progress.
   - read feedback
   - simple early optimization
   - callgraph production
   (all these steps needs to be done together)
   - collection of local properties
2b) possible saving info into file
3) global pass  (don't need function bodies, just local info collected
   in 2 so we fit in memory)
   - callgraph optimization
   - global dataflow
   - global optimization decisions  (inlining, cloning and such)
4) assembling pass
   - get function body
   - perform transformation worked out by global optimizers
     (expand_calls_inline and such)
   - SSA, tree optimization

This scheme is more or less implemented by cgraph.  I am missing
completely 2b of course :) and also early optimization pass.

In order to minimize code duplication it would be nice to share
framework in simple early optimization (that should subsume someting
like dom1+dce1+cfgcleanup) and it would be nice to avoid converting into
and out of SSA form.  I think it would be cool to go into SSA form right
in step 2 and stay in SSA until RTL expansion.  That would declare SSA
as the IL majority of passes are interested in.  It is more or less done
by Open64 but it also has some drawbacks (optimizations doing a lot of
CFG manipulation do have problems with updating SSA, jump threading is
first example of this, I hope to soon make tracer to work on trees, but
still these optimizations often can take advnatage of SSA so going out
and in SSA can happen in the subpass)

There are memory consumption implications of this, so I am not sure
about this plan.  It is probably impossible to save virtual operands for
all functions so perhaps we can do SSA only on registers, not on memory
locations at that form or do the fallback plan of either going out of
SSA at the end of 2) or doing just non-SSA optimizations in 2), but I
don't like these very much.

Honza
> 
> Andrew
> 
>