Re: Tremendous performance regression in 1.1.2 -> mainline

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi Brad,

On Thu, 6 Apr 2000, Brad Lucier wrote:
> > would be applied if some heuristic were met (e.g., flow graph edges, basic
> > blocks, loops, etc.); an additional flag would remove the heuristic limit
> > and always apply the optimization for that last bit of performance
> > improvement.
> 
> The problem in this case is simple: an O(N^2) algorithm is used to compute
> flow dominators instead of an available O(N) algorithm.  The fix is perhaps
> not so simple; I don't feel competent to rewrite the code.  But certainly
> no heuristic or clamp is necessary in this case.

I somehow doubt that there exists a faster than O(N^2) algorithm. As dom
is an NxN relation, we have to set (or clear) N^2 bits in the worst case.
Nevertheless, can you please try the attached diff against flow.c with
your testcase?

With a reduced version of your test I had an big improvement in speed:
(from 85 to 8 seconds in flow).


Ciao,
Michael.

flow-mm.diff.gz