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

[Steven Bosscher <s dot bosscher at student dot tudelft dot nl>]

On Friday 19 December 2003 18:00, Andrew MacLeod wrote:
> Clearly, as long as the CFG exists, thats where the information ought to
> be stored.

Of course.

> 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. 

When we annotate trees, the profile information is not "update-able" as in 
just the CFG.  I'd expect that profile-annotated trees also are more fragile: 
Propagating counts/probabilities during expanding or inlining would have to 
be done in unintuitive ways if you don't simply have the CFG available.  To 
propagate such information without the CFG available doesn't sound very sane 
to me.

Also, you would have to first have to annotate trees, then RTL, and then 
finally the RTL CFG.  The RTL CFG is not constructed during tree->RTL 
expansion, so you'd need alternative storage for profile information in both 
trees and RTL.  Where do you think the profile information could be stored in 
the phases between expanding and RTL CFG construction?


> 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.

Yes, we would need to remember the CFG for each useful function.  That's not 
very hard to do, and not very expensive in terms of memory usage, either.  It 
will be even less expensive after we've made basic_block_def a bit smaller by 
moving more things into (RTL-)bb annotations.

(It could be even less expensive if we'd lose GOTO_EXPRs hanging from 
COND_EXPRs, etc...  ;-)


> So we wouldn't just be keeping the trees for
> inlineable functions around, we'd have to keep objectified CFG's as
> well.

The CFG is not very hard to objectify.  You really only need to make the the 
entry and exit blocks reachable from, say, struct function.  We can do that 
now that the CFG is garbage collectable.  In fact, we could completely lose 
the function-as-tree representation as we have it now, and instead represent 
every function with just the CFG.


> 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.

Yes, probably.


> You also plan to create a CFG aware
> inliner and objectify the CFG, and do the inlining from that?

Yes.


> 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?

Inlining trees while in SSA form doesn't sound feasible at this point.  I 
think LLVM does this, but our representation is probably too heavy-weight, 
which makes having whole functions hanging around as trees in SSA form not a 
very attractive idea.  We could of course inline before going into SSA form. 
We have the CFG at that point, and we'd still be inlining optimized 
functions.

Gr.
Steven