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