Re: Tremendous performance regression in 1.1.2 -> mainline

[dan at cgsoftware dot com (Daniel Berlin+list.gcc)]

>>>>> "Michael" == Michael Matz <matzmich@cs.tu-berlin.de> writes:


    Michael> I somehow doubt that there exists a faster than O(N^2)
    Michael> algorithm. As dom is an NxN relation, we have to set (or
    Michael> clear) N^2 bits in the worst case. 

Just doing a google search on "flow dominators" turns up interesting
results.
Flow dominators aren't exactly my area of expertise, so you could be
right, but try this:
   http://www.acm.org/pubs/citations/proceedings/stoc/22145/p185-harel/

In particular, besides the paper title, this part of the abstract
seems relevant:
" In the second part of the paper we show how to use the new technique for
   speeding up the fastest known algorithm for finding dominators in flow
 graphs so that it runs in linear time."


    Michael> Nevertheless, can you
    Michael> please try the attached diff against flow.c with your
    Michael> testcase?

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


    Michael> Ciao, Michael.