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

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

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

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


Ciao,
Michael.