http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56113
--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-30 13:50:04 UTC --- All of the tree SSA incremental time is spent in computing the IDFs. With a patch to cache IDF on def-blocks nothing is gained. Unpatched, n = 10000: tree SSA incremental : 48.86 (51%) usr TOTAL : 94.88 I tried replacing the work-stack vector with a sparseset to avoid visiting a block twice (and thus avoid doing the EXECUTE_IF_AND_COMPL_IN_BITMAP twice which the 2nd time has no bits). To no avail - sparseset seems to have a higher overhead. tree SSA incremental : 52.25 (53%) usr TOTAL : 98.60 Also the phi-insertion-point update can be done with bitmap_ior_into (slows things down tremendously): tree SSA incremental : 75.56 (62%) usr TOTAL : 121.73 combined with using a sparse-set for iteration: tree SSA incremental : 78.28 (63%) usr TOTAL : 124.72 arranging for the work_stack to be large enough to hold 2*n_basic_blocks we can use quick_push in the inner loop. tree SSA incremental : 47.05 (51%) usr TOTAL : 91.60
