Re: flow_d_f_o_compute misnamed? (was: if-conversion a performance...)

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi,

On Fri, 5 May 2000, Jeffrey A Law wrote:

> > Right now the worklist is filled in natural order, which couldn't be worse
> > for a Žbackward' problem (post dominators) ;) Reversing this already helps
> > alot.
> Yea, that was exactly what I was asking.  The cost is almost non-existent
> with notable benefits.

But why restrict ourself when we can do better ;) Note that the time for
sorting the worklist in any way (may be even randomly ;)) is by far
outweighted (sp?) by the time it takes to do all the bitvectors
intersections, which are mostly useless, in the sense that some components
of the intersection didn't contribute to the result.

E.g. I measured the number of sbitmap_a_and_b's which didn't result in any
change, and my finding was horrible: of around 5 millions intersections
4.8 million were effectless. But the algorithm must try it anyway, so the
bitvector based approach leads to horrors and slowness :)

> > Filling it in an intelligent way again reduces the blocks which get
> > reevaluated, and additionally checking for changes minimizes that number.
> > I'm now down to only 386 blocks reinserted into the worklist out of ca.
> > 5000 bb in Brads testcase (originally there were around 15000
> > reinsertions).
> Right.  This is typical behavior when we're looking at stuff in the opposite
> of the intended order.
> 
> How many reinsertions do we get by just reversing the order of insertion
> into the worklist?

Quick rundown of number of reinserted blocks:
8523 with simple reverse
7003 with more intelligent "topological" sort
386  with avoiding insert as much as possible

The last one I implement with before actually reinserting a block I test,
if the block forcing the reinsert has any effect on the BB in question.
That again squeezed some minutes out of that stuff on my slow machine ;)
But it comes with the price that it now is obvious how many intersections
are done without use. With the other cases it is hidden in
intersection_of_succs (and _preds), and only noticable by the fact that it
is painfully slow ;)

> > So may be it's only misnamed? But then again, it's used in
> > flow_loops_find() to find outer loops before inner ones. I don't see right
> > now where a normal DFS would help that, may be I'm too tired :)
> A DFS numbering will detect inner loops first, I haven't worked through
> whether or not a BFS would detect outer loops first or not.

If DFS first detects inner loops (after some thinking I see that too :))
then some comments in flow_loops_find() are wrong (some say, they are
searching for outer first), and flow_depth_first_order_compute() should be
corrected to do what the name promises ;) Or do I miss something obvious?
I mean it works somehow right now, I'm not really sure if I can believe
that such a central function is incorrect and nobody noticed.

> > >From Alstrup/Lauridsen/Thorup (http://www.diku.dk/research-groups/topps/,
> > I think report 320 or so). Do you have any other accessible? I haven't
> > found more (well, I only searched the net).
> Are they based on the Lengauer & Tarjan algorithm?  That's the one I hear
> the most about in papers & texts for fast dominator computations.

Indeed they based on work from the god of linear graph algorithms, but
while L&T is O(m*alpha(m,n)) (n=nodes, m=edges, alpha a more than
const-function) the A&L&T one is truly linear O(m+n).


Ciao,
Michael.