diff options
| author | Richard Guenther <rguenther@suse.de> | 2010-05-06 09:08:57 +0000 |
|---|---|---|
| committer | Richard Biener <rguenth@gcc.gnu.org> | 2010-05-06 09:08:57 +0000 |
| commit | 2b90475adda974b77287699beb1180d1cd6e286b (patch) | |
| tree | 36bd69de4dd9b2ad158519b9ff7a45a395af7f70 /gcc/domwalk.c | |
| parent | e3bdfed62abe1c163b93162e53a377b21b5658dc (diff) | |
| download | gcc-2b90475adda974b77287699beb1180d1cd6e286b.tar.gz | |
re PR tree-optimization/43571 (domwalk sucks)
2010-05-06 Richard Guenther <rguenther@suse.de>
PR tree-optimization/43571
* domwalk.c (walk_dominator_tree): Walk the dominator
sons in more optimal order.
From-SVN: r159100
Diffstat (limited to 'gcc/domwalk.c')
| -rw-r--r-- | gcc/domwalk.c | 40 |
1 files changed, 39 insertions, 1 deletions
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 |