[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

["steven at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>]

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