Tremendous performance regression in 1.1.2 -> mainline

[Alexandre Oliva]

On Apr  7, 2000, dan@cgsoftware.com (Daniel Berlin+list.gcc) wrote:

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

Linear time in a graph is O(m+n).  When the graph is dense, m is
O(n^2).

-- 
Alexandre Oliva    Enjoy Guaraná, see http://www.ic.unicamp.br/~oliva/
Cygnus Solutions, a Red Hat company        aoliva@{redhat, cygnus}.com
Free Software Developer and Evangelist    CS PhD student at IC-Unicamp
oliva@{lsd.ic.unicamp.br, gnu.org}   Write to mailing lists, not to me