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

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. 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). I doubt that I would get anywhere further with the
bitvector based algorithm. May be another representation of the bitvectors
would help (one which accounts for large blocks of same bits) in case of
_many_ basic blocks. I was going to implement these, but I decided that my
time is better spent in replacing the whole bitvector based algorithm.
It's also more interesting ;)

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

I also noticed in reading through the code, that there are many places,
where data flow is calculated in some way, that do slightly the same but
nevertheless do not reuse any code. It would be good to uniform that
middle end (I mean the language and machine independent things), but gcc
is such a huge thing ;)

>   > {(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 ;-)

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

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

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

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

I feared somebody would say that. Bloody bureaucracy ;)


Ciao,
Michael.