------- Comment #26 from steven at gcc dot gnu dot org 2007-12-16 01:50 ------- For Eric's second test case, pr24400-2.c, I have on cygwin in tree-ssa 1006 basic blocks, 2044 edges and "only" 840 DFS back edges. After expanding to RTL we have 1046 basic blocks, 78005 edges, and 38760 DFS back edges.
In terms of Muchnick's text on worklist dataflow solvers (section 8.4, p. 233 in my copy) we have A >> |N|, where A is the number of back edges on any acyclic path in the flow graph. The test case has no cyclic paths, so A is 38760 and the expected number of passes in an iterative solver is A + 2 = 38760 if the blocks are presented in reverse post order. Measurements show that for the LR problem df_worklist_dataflow needs 39902 iterations to converge, and for the LIVE problem it also needs 39902 iterations without df_hack2.diff, and 11442 with that patch applied. I counted the number of iterations in the "while (!bitmap_empty_p (pending))" loop. My conclusion must be that df_worklist_dataflow really doesn't behave unreasonably for the test case. df_iterative_dataflow needs at most 5 iterations, counting the number of times we loop in the "while (1)" main loop. That is, 5 times visiting all basic blocks, so in total 5*1046=5230 basic block visits. Optimistically assuming one block visted per iteration in df_worklist_dataflow, 39902 basic block visits. What are the reasons for not just *always* using the hybrid search solver? The comment before df_worklist_dataflow says that "measurements shows worklist algorithm beats iterative algorithm by some margin overall". Which measurements are this? And which iterative algorithm, i.e. the classic iterative algorithm or the hybrid search?? -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34400