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.10005060022080.4463-100000@platon>you write:
  > Hi,
  > 
  > On Fri, 5 May 2000, Jeffrey A Law wrote:
  > > I didn't look at the code in any detail, it's entirely possible we're loa
  > ding
  > > up the worklist in a silly order right now, which can be easily resolved 
  > and
  > > may provide most of the benefit of your patch with lower cost.
  > 
  > 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.

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


  > >   > {(a,b),(a,c),(b,d),(c,d),(ENTRY,a),(d,EXIT)} (i.e. a simple if) it
  > >   > produces an order of [a,b,c,d] which is not according to any DF defin
  > ition
  > >   > I know of ;) which would result in e.g. [a,b,d,c].
  > > If that's what it's doing, then it certainly doesn't sound like DFS to me
  >  ;-)
  > 
  > 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.

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


  > > It would probably be useful for you to go ahead and get the legal paperwo
  > rk
  > > filed with the FSF so that we can use your new dominator code when it's
  > > ready.  http://gcc.gnu.org/contribute.html will provide you with the deta
  > ils
  > > you need for your copyright assignment and/or employer disclaimer.
  > 
  > I feared somebody would say that. Bloody bureaucracy ;)
:-)  For better or worse, legal paperwork is a requirement.
jeff