Re: redirect_edge_and_branch questions

[Jan Hubicka <jh at suse dot cz>]

> On Fri, 2004-10-01 at 15:32, Jan Hubicka wrote:
> > edirect_edge_and_branch() do whatever
> > > dominator updates are required. It has exactly the same information I
> > > have if I wanted to update them.
> > 
> > No, it doesn't.
> > It is dificult to effectivly update dominator tree when you know just
> > that you are redirecting edge from block A to B, while it is trivial
> > when you know, for instance, that you are splitting block into two.
> > So updating dominators relies on higher level knowledge of what is going
> > on.
> > > 
> 
> Well, all I know is that I am redirecting some arbitrary incoming edges
> to some other block which is a predecessor to this block. I don't know

Yes, your highlevel knowledge in this case is that the block is a
predecessor specially created for this particular edge redirection.
While this case is quite easy to detect inside the edge redirection
code, it is just one of many posibilities what user may intent to do by
calling the edge redirect.

> where they came form or how they relate to each other.  Before I have to
> figure this all out, does anyone use dominators after SSA->normal? I
> don't want to update them if I don't have to.

I don't think anyone uses them and yet dominators are resonably cheap to
recompute from the scratch, so it don't make sense to investigate too
much effort into it.

In general it seems to me that it makes sense to update dominators only
if your pass needs them up-to-date afterwards (ie recomputing them on
demand would result in nonconstant amount of recomputation within the
pass)
> 
> 
> > > So my next question is why doesn't redirect_edge_and_branch() also
> > > update the block frequencies?   Again, it has the same information I
> > > have...
> > 
> > It does not again.  For instance if you are moving edge to skip
> > forwarder block, it is trivial to walk the path and update, but for
> > instance when you are doing jump threading, it is already nontrivial
> > issue, so again you have to know why you are redirecting the edge and
> > how.
> > 
> 
> ??
> 
> Given an edge, don't you know either the percentage taken or edge count
> for that edge?  So if its being redirected, you deduct that edges count
> from the original destination block, redirect it, and add it in at the
> new destination's block. 
> 
> OR am I missing something about our implementation?

This will go wrong in everything except for trivial cases.  Imagine that
you have edge A->B, B->C, C->D and D->E all blocks and edges with count
1 and you figured out that blocks B C D are noop, so you want to
redirect A->B to A->E and you know that this don't change program
behaviour.

Now you should have count of A and E 1 and counts of B C D 0, while the
local updating in redirect_edge would result in C D being still set to
1.

Instead of doing part of update in the CFG manipulation API and leaving
out to users to catch where it goes wrong, it seems more consistent to
not attempt to do the job and leave it to users.

Even for your trivial case it is not clear whether the edge redirection
should decrease original destination frequency or keep it is it is.  In
your case it should be kept, in edge forwarding it should be decreased.

Also you should look into the function Zdenek mentioned.

Honza
> 
> Andrew
>