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.10005052304100.4463-100000@platon>you write:
  > Hi,
  > 
  > On Fri, 5 May 2000, Jeffrey A Law wrote:
  > > > post_dom the changes are propagating from the _end_). I then also
  > > > implemented a poor man's topological sort for cyclic graphs ;), which
  > > >
  > > Like Richard, I'd like to see you submit this as a function which can be
  > > called from multiple locations in the compiler.
  > 
  > Will do so on the weekend.
Great!


  > > We've got a number of routines that _might_ benefit from this code, but
  > > I'd also like to see some more general benchmarking.  I don't want to
  > > see us slow down the compiler for the common cases just to make Brad's
  > > one test run faster.
  > 
  > Yes, right now this sorting is linear with number of edges, while the
  > simple reverse filling of the worklist is linear with n_basic_blocks. May
  > be it would be worthwhile to make it
  > order_bb_for_backward_flow(basic_block *dest, int simple_reverse)
  > and if the arg is true, only fill dest backwards instead of trying to be
  > intelligent.
I didn't look at the code in any detail, it's entirely possible we're loading
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.

Most CFGs are relatively well behaved with fast convergence for iterative
dataflow equations -- convergence is bad typically when the CFG has a lot
of nested backedges, and even then those backedges have to enclose a large
number of blocks for iterative dataflow analysis to slow down significantly.

There are certainly other possibilities for speeding up the various dataflow
solvers, whether it's a better dominator algorithm or more efficient code
to solve the LCM dataflow equations.

  > Meanwhile I noticed a slight strangeness with
  > flow_depth_first_order_compute, in that it does not compute any DFS order
  > but more a width first one. E.g. if presented with a graph like
  > {(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 definition
  > 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 ;-)

  > In case anybody is interested, I'm currently trying to implement a linear
  > time dominator algorithm, and wanted to use some stuff already there. (As
  > I also need a backward DFS for post-dom, I anyway would have to implement
  > it myself, but for the beginning ...)
Which algorithm?  Improving dominator computation time is going to be more
important going forward as we use that information in more and more places.

It would probably be useful for you to go ahead and get the legal paperwork
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 details
you need for your copyright assignment and/or employer disclaimer.

jeff