Tremendous performance regression in 1.1.2 -> mainline

[Michael Matz]

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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: flow-mm.diff.gz
Type: application/x-gzip
Size: 1032 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20000406/4ad75fd4/attachment.bin>