From 2b90475adda974b77287699beb1180d1cd6e286b Mon Sep 17 00:00:00 2001 From: Richard Guenther Date: Thu, 6 May 2010 09:08:57 +0000 Subject: [PATCH] re PR tree-optimization/43571 (domwalk sucks) 2010-05-06 Richard Guenther PR tree-optimization/43571 * domwalk.c (walk_dominator_tree): Walk the dominator sons in more optimal order. From-SVN: r159100 --- gcc/ChangeLog | 6 ++++++ gcc/domwalk.c | 40 +++++++++++++++++++++++++++++++++++++++- 2 files changed, 45 insertions(+), 1 deletion(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 5051eced3b2..aacaefe2fe7 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2010-05-06 Richard Guenther + + PR tree-optimization/43571 + * domwalk.c (walk_dominator_tree): Walk the dominator + sons in more optimal order. + 2010-05-06 Richard Guenther PR tree-optimization/43934 diff --git a/gcc/domwalk.c b/gcc/domwalk.c index 07764eb8047..4f0e9190c19 100644 --- a/gcc/domwalk.c +++ b/gcc/domwalk.c @@ -144,6 +144,9 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) basic_block dest; basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); int sp = 0; + sbitmap visited = sbitmap_alloc (last_basic_block + 1); + sbitmap_zero (visited); + SET_BIT (visited, ENTRY_BLOCK_PTR->index); while (true) { @@ -184,6 +187,8 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) if (walk_data->before_dom_children) (*walk_data->before_dom_children) (walk_data, bb); + SET_BIT (visited, bb->index); + /* Mark the current BB to be popped out of the recursion stack once children are processed. */ worklist[sp++] = bb; @@ -213,11 +218,44 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) } } if (sp) - bb = worklist[--sp]; + { + int spp; + spp = sp - 1; + if (walk_data->dom_direction == CDI_DOMINATORS) + /* Find the dominator son that has all its predecessors + visited and continue with that. */ + while (1) + { + edge_iterator ei; + edge e; + bool found = true; + bb = worklist[spp]; + FOR_EACH_EDGE (e, ei, bb->preds) + { + if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest) + && !TEST_BIT (visited, e->src->index)) + { + found = false; + break; + } + } + if (found) + break; + /* If we didn't find a dom child with all visited + predecessors just use the candidate we were checking. + This happens for candidates in irreducible loops. */ + if (!worklist[spp - 1]) + break; + --spp; + } + bb = worklist[spp]; + worklist[spp] = worklist[--sp]; + } else break; } free (worklist); + sbitmap_free (visited); } void -- 2.30.2