This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Fix PR43571
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 16 Apr 2010 16:05:51 +0200 (CEST)
- Subject: [PATCH] Fix PR43571
This fixes the dominator walker to walk dominator children in an
order that tries to ensure all predecessors have already been
visited. Otherwise for a CFG like
A
/ \
B C
\ /
D
we visit the dominator children of A which are B, C and D in
random order while we should make sure to visit B and C before
visiting D. That is important if the worker can for example
merge PHI args in D or can record information from B and C
that needs not be invalidated when leaving the blocks (like
SSA constants or copies in DOM).
Thus, the patch ensures that DOM can do its work properly
without iterating.
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
2010-04-16 Richard Guenther <rguenther@suse.de>
PR tree-optimization/43571
* domwalk.c (walk_dominator_tree): Walk the dominator
sons in more optimal order.
Index: gcc/domwalk.c
===================================================================
*** gcc/domwalk.c.orig 2010-04-16 15:59:40.000000000 +0200
--- gcc/domwalk.c 2010-04-16 16:05:35.000000000 +0200
*************** walk_dominator_tree (struct dom_walk_dat
*** 144,149 ****
--- 144,152 ----
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)
{
*************** walk_dominator_tree (struct dom_walk_dat
*** 184,189 ****
--- 187,194 ----
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;
*************** walk_dominator_tree (struct dom_walk_dat
*** 213,223 ****
}
}
if (sp)
! bb = worklist[--sp];
else
break;
}
free (worklist);
}
void
--- 218,261 ----
}
}
if (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