Re: [RFC/patch] Callgraph based inlining heuristics

[Jan Hubicka <jh at suse dot cz>]

> On Mon, 23 Jun 2003, Jan Hubicka wrote:
> 
> > > On Mon, 23 Jun 2003, Jan Hubicka wrote:
> > >
> > > > > Btw. - are you currently maintaining an explicit callgraph, so we can
> > > > > stick notes to its edges?
> > > > Yes.
> > >
> > > So in principle we can walk "down" the cfg of a leaf function marking all
> > > edges as to be inlined?
> >
> > This has the transitivity problem.  If your leaf function A calls B that
> > calls C, you mark flag "inline C into B" that may not be what you want
> > in other places you call B.
> 
> Ah - so the CFG "shares" edges, in this case we want to unshare these
> edges. Is such possible with the current infrastructure?
Not really.

An alternative would be to simply use somewhat different datastructure -
like list of all call sites that will be inlined at processing given
function, which may contain call sites from the inlined functions.

Problem of this is that it is more inconvenient to manage and analyse
than the simple flag on callgraph edge and I am not quite convienced it
worth the complexity.  Just for instance deciding whether all calls to
given function will be elliminated is nontrivial, as one has to check
not only all callers but also callers of these callers where callers may
be inlined into.

Another alternative may be to actually clone the function node when we
decide to inline it as it now becomes different clone of the function.
Last altenrative is to implement this as a special case instead -
managing flag whether given function is leafify and whether given
function will be inlined into some leaf function and take care of
these..

Perhaps the idea of cloning nodes is most consistent one actually.  It
would also make dataflow analysis over CFG more precise when dealing
with inline functions and the question whether out-of-line copy of
inline function is needed can be reduced to simple reachability
analysis.

Honza
> 
> Richard.