http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59802
--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> --- http://gcc.gnu.org/ml/gcc-patches/2014-01/msg00780.html Even better would be to get rid of the explicit maximum set (just ignore incoming edges with the maximum set, aka 'unvisited' edges during bitmap_intersection_of_preds). Basically follow what tree PRE does for antic-in compute. That would make using regular bitmaps possible (if that is a win - at least computing the changed bit is free). Also queuing succs at the end of the worklist messes up iteration order for everything but the first iteration. PRE uses a sbitmap that records whether a BB was changed. Anyway, the above simple patch dramatically improves the numbers for this testcase.