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

[Jeffrey A Law <law at cygnus dot com>]

  In message <Pine.SOL.4.10.10005060226560.4463-100000@platon>you write:
  > > > Right now the worklist is filled in natural order, which couldn't be wo
  > rse
  > > > for a Žbackward' problem (post dominators) ;) Reversing this already 
hel
  > ps
  > > > 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 ;)
I'm not necessarily restricting what we can/will do, only trying to
look at cost/benefit of the various possibilities.  A solution that
is less efficient in pathological cases, but more efficient in the
general case may be the preferred solution, it depends on a number of
factors -- and we need data to try and find reasonable tradeoff points.

  > 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 :)
Right.  The tradeoff is time/space vs code complexity -- choosing the right
tradeoff point is sometimes difficult.

Other approaches using "blocking factors" like in the null pointer check
elimination optimization may significantly improve this situaton.  Then
again, it may not.  Aside from being more memory efficient, the blocking
code _may_ ultimately result in significantly fewer bitvector ops than the
current implementation.  See the null pointer check code in gcse.c.  
Converting the rest of gcse to use the blocking code ought to be
reasonably easy and would be greatly appreciated.

  > > 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
OK.  Assuming the code to avoid reinsertions isn't too  expensive and
difficult to understand/maintain, then it probably makes sense.  One
way to get a feel for the expense of the code is to time a bootstrap
with and without your change.  Presumably the time to bootstrap should
be reduced.

Note you need to do bootstraps anyway for testing purposes :-)


  > 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.
Can you explain this in more detail?  I'm presuming that you only insert
a block if something in its bitvector changed?  I thought we already did that.


  > > 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 :))
No need to think about it -- just refer to literature and take it as the
gospel :-)

  > 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 don't think you've missed anything.  I think the code is wrong.  I'm not
sure of an algorithm to find the outermost loops first other than to find the
innermost loops and reverse the loop nest when we're done.

  > 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.
I suspect it "works" in the sense that even if it doesn't find the right loop
nest the results of an incorrect nest are merely less efficient code, not
incorrect code.  Regardless it needs to be fixed.

  > 
  > > > >From Alstrup/Lauridsen/Thorup (http://www.diku.dk/research-groups/topp
  > s/,
  > > > 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).
I certainly hope you document both the code and the algorithm well.  You might
also submit a patch to the readings.html web page to reference the paper you
mentioned above.  It would be greatly appreciated.

jeff