[Bug rtl-optimization/36365] [4.3/4.4 Regression] Hang in df_analyze

[steven at gcc dot gnu dot org]

------- Comment #9 from steven at gcc dot gnu dot org  2008-11-16 12:17 -------
Advice to folks caring about compiler stability instead of supposedly faster:
Always use double-queue instead of overeager.  The overeager solver is just not
reliable enough, and I have never found any proof for the speed benefit that
Seongbae claimed it has.

The theoretical worst-case time for the overeager algorithm is exponential in
the number of basic blocks, for densely connected CFGs.  I have argued before
that such an algorithm should *never* have been selected as the default for
GCC, even if it is, say, 0.5% faster for a GCC bootstrap (but I did the
comparison last year and I have never actually measured any benefits of
overeager over double queue).

For the double queue, and also for the hybrid search, the number of passes has
a reasonable proven upper bound for any CFG, so these algorithms are much more
reliable.

See also the discussion in PR34400, esp. comments 25-28:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34400#c25
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34400#c28


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36365