| Message ID | 87a8r0wqoe.fsf@e105548-lin.cambridge.arm.com |
|---|---|
| State | New |
| Headers | show |
On Fri, Oct 30, 2015 at 12:18 PM, Richard Sandiford <richard.sandiford@arm.com> wrote: > The pass would free the dominance info after making a change, but it > should be pretty easy to keep the information up-to-date when the call > has no EH edges. In a way the main hurdle was split_block, which seemed > to assume that the new block would postdominate the old one, and that > all blocks immediately dominated by the old block are now immediately > dominated by the new one. > > Tested on x86_64-linux-gnu, arm-linux-gnueabi and aarch64-linux-gnu. > OK to install? Hmm, I don't understand why split_block needs to be touched. The operation itself correctly updates dominator info. It is up to the pass to fix things up if it does further CFG modifications that make the new block no longer post-dominate the old one. So why do you need the split_block change? Richard. > Thanks, > Richard > > > gcc/ > * cfghooks.h (split_block): Add a flag to say whether all blocks > dominated by the old block are now dominated by the new one. > * cfghooks.c (split_block_1, split_block): Likewise, > (split_block_after_labels): Update accordingly. > * tree-call-cdce.c (shrink_wrap_one_built_in_call): Try to update > the dominance info; free it if we can't. > (pass_call_cdce::execute): Don't free the dominance info here. > > diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c > index 2c5c96c..82c427f 100644 > --- a/gcc/cfghooks.c > +++ b/gcc/cfghooks.c > @@ -483,12 +483,18 @@ redirect_edge_and_branch_force (edge e, basic_block dest) > return ret; > } > > -/* Splits basic block BB after the specified instruction I (but at least after > - the labels). If I is NULL, splits just after labels. The newly created edge > - is returned. The new basic block is created just after the old one. */ > +/* Splits basic block BB after the specified instruction I (but at least > + after the labels). If I is NULL, splits just after labels. > + > + The newly created edge is returned. The new basic block is created > + just after the old one. It is assumed that the old block will dominate > + the new one; the caller can use set_immediate_dominator if this > + assumption is wrong. If ASSUME_POSTDOM, it is further assumed that > + the new block will postdominate the old block, so that all blocks > + dominated by the old block are now also dominated by the new one. */ > > static edge > -split_block_1 (basic_block bb, void *i) > +split_block_1 (basic_block bb, void *i, bool assume_postdom) > { > basic_block new_bb; > edge res; > @@ -506,7 +512,8 @@ split_block_1 (basic_block bb, void *i) > > if (dom_info_available_p (CDI_DOMINATORS)) > { > - redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb); > + if (assume_postdom) > + redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb); > set_immediate_dominator (CDI_DOMINATORS, new_bb, bb); > } > > @@ -533,15 +540,15 @@ split_block_1 (basic_block bb, void *i) > } > > edge > -split_block (basic_block bb, gimple *i) > +split_block (basic_block bb, gimple *i, bool assume_postdom) > { > - return split_block_1 (bb, i); > + return split_block_1 (bb, i, assume_postdom); > } > > edge > -split_block (basic_block bb, rtx i) > +split_block (basic_block bb, rtx i, bool assume_postdom) > { > - return split_block_1 (bb, i); > + return split_block_1 (bb, i, assume_postdom); > } > > /* Splits block BB just after labels. The newly created edge is returned. */ > @@ -549,7 +556,7 @@ split_block (basic_block bb, rtx i) > edge > split_block_after_labels (basic_block bb) > { > - return split_block_1 (bb, NULL); > + return split_block_1 (bb, NULL, true); > } > > /* Moves block BB immediately after block AFTER. Returns false if the > diff --git a/gcc/cfghooks.h b/gcc/cfghooks.h > index a0cb6fd..8f6b465 100644 > --- a/gcc/cfghooks.h > +++ b/gcc/cfghooks.h > @@ -208,8 +208,8 @@ extern edge redirect_edge_succ_nodup (edge, basic_block); > extern bool can_remove_branch_p (const_edge); > extern void remove_branch (edge); > extern void remove_edge (edge); > -extern edge split_block (basic_block, rtx); > -extern edge split_block (basic_block, gimple *); > +extern edge split_block (basic_block, rtx, bool = true); > +extern edge split_block (basic_block, gimple *, bool = true); > extern edge split_block_after_labels (basic_block); > extern bool move_block_after (basic_block, basic_block); > extern void delete_basic_block (basic_block); > diff --git a/gcc/tree-call-cdce.c b/gcc/tree-call-cdce.c > index 57be8a4..72828dd 100644 > --- a/gcc/tree-call-cdce.c > +++ b/gcc/tree-call-cdce.c > @@ -735,6 +735,32 @@ shrink_wrap_one_built_in_call (gcall *bi_call) > if (nconds == 0) > return false; > > + /* The cfg we want to create looks like this: > + > + [guard n-1] <- guard_bb (old block) > + | \ > + | [guard n-2] } > + | / \ } > + | / ... } new blocks > + | / [guard 0] } > + | / / | } > + [ call ] | <- bi_call_bb } > + | \ | > + | \ | > + | [ join ] <- join_tgt_bb (old iff call must end bb) > + | > + possible EH edges (only if [join] is old) > + > + When [join] is new, the immediate dominators for these blocks are: > + > + 1. [guard n-1]: unchanged > + 2. [call]: [guard n-1] > + 3. [guard m]: [guard m+1] for 0 <= m <= n-2 > + 4. [join]: [guard n-1] > + > + We punt for the more complex case case of [join] being old and > + simply free the dominance info. We also punt on postdominators, > + which aren't expected to be available at this point anyway. */ > bi_call_bb = gimple_bb (bi_call); > > /* Now find the join target bb -- split bi_call_bb if needed. */ > @@ -745,9 +771,13 @@ shrink_wrap_one_built_in_call (gcall *bi_call) > join_tgt_in_edge_from_call = find_fallthru_edge (bi_call_bb->succs); > if (join_tgt_in_edge_from_call == NULL) > return false; > + free_dominance_info (CDI_DOMINATORS); > } > else > - join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call); > + /* The old block ([guard n-1], currently called bi_call_bb) is the > + immediate dominator of join_tgt_bb. join_tgt_bb will also > + postdominate the guard block. */ > + join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call, true); > > bi_call_bsi = gsi_for_stmt (bi_call); > > @@ -772,7 +802,10 @@ shrink_wrap_one_built_in_call (gcall *bi_call) > ci++; > gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND); > > - bi_call_in_edge0 = split_block (bi_call_bb, cond_expr); > + /* The old block (for [guard n-1]) is the immediate dominator of the > + new block (for the call). The call block does not postdominate > + the guard block. */ > + bi_call_in_edge0 = split_block (bi_call_bb, cond_expr, false); > bi_call_in_edge0->flags &= ~EDGE_FALLTHRU; > bi_call_in_edge0->flags |= EDGE_TRUE_VALUE; > guard_bb = bi_call_bb; > @@ -790,6 +823,7 @@ shrink_wrap_one_built_in_call (gcall *bi_call) > guard_bb->count - bi_call_in_edge0->count; > > /* Code generation for the rest of the conditions */ > + basic_block prev_guard_bb = NULL; > while (nconds > 0) > { > unsigned ci0; > @@ -809,7 +843,12 @@ shrink_wrap_one_built_in_call (gcall *bi_call) > nconds--; > ci++; > gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND); > - guard_bb_in_edge = split_block (guard_bb, cond_expr); > + > + /* The old block (for the guard we just added) is the immediate > + dominator of the new block (for the previous guard). The new > + block does not postdominate the old one; the immediate postdominator > + of the old block is still join_tgt_bb. */ > + guard_bb_in_edge = split_block (guard_bb, cond_expr, false); > guard_bb_in_edge->flags &= ~EDGE_FALLTHRU; > guard_bb_in_edge->flags |= EDGE_FALSE_VALUE; > > @@ -822,6 +861,13 @@ shrink_wrap_one_built_in_call (gcall *bi_call) > guard_bb_in_edge->probability = > inverse_probability (bi_call_in_edge->probability); > guard_bb_in_edge->count = guard_bb->count - bi_call_in_edge->count; > + > + /* If this is [guard m] for m >= 2, make [guard m-1] the immediate > + dominator of [guard m-2]. */ > + if (prev_guard_bb && dom_info_available_p (CDI_DOMINATORS)) > + set_immediate_dominator (CDI_DOMINATORS, prev_guard_bb, > + guard_bb_in_edge->dest); > + prev_guard_bb = guard_bb_in_edge->dest; > } > > if (dump_file && (dump_flags & TDF_DETAILS)) > @@ -931,7 +977,6 @@ pass_call_cdce::execute (function *fun) > > if (something_changed) > { > - free_dominance_info (CDI_DOMINATORS); > free_dominance_info (CDI_POST_DOMINATORS); > /* As we introduced new control-flow we need to insert PHI-nodes > for the call-clobbers of the remaining call. */ >
Richard Biener <richard.guenther@gmail.com> writes: > On Fri, Oct 30, 2015 at 12:18 PM, Richard Sandiford > <richard.sandiford@arm.com> wrote: >> The pass would free the dominance info after making a change, but it >> should be pretty easy to keep the information up-to-date when the call >> has no EH edges. In a way the main hurdle was split_block, which seemed >> to assume that the new block would postdominate the old one, and that >> all blocks immediately dominated by the old block are now immediately >> dominated by the new one. >> >> Tested on x86_64-linux-gnu, arm-linux-gnueabi and aarch64-linux-gnu. >> OK to install? > > Hmm, I don't understand why split_block needs to be touched. The > operation itself correctly updates dominator info. It is up to the > pass to fix things up if it does further CFG modifications that make > the new block no longer post-dominate the old one. > > So why do you need the split_block change? The updates we'd need here would be: redirect_immediate_dominators (CDI_DOMINATORS, call, guard_bb); which undoes the earlier: redirect_immediate_dominators (CDI_DOMINATORS, guard_bb, call); that split_block did. It just seemed wasteful to call redirect_immediate_dominators twice to get a no-op. In other words, there are going to be callers to split_block that know the second block isn't going to postdominate the first and where the calling; redirect_immediate_dominators (CDI_DOMINATORS, first_block, second_block); is taking us further from where we want to be. Thanks, Richard
On Fri, Oct 30, 2015 at 1:14 PM, Richard Sandiford <richard.sandiford@arm.com> wrote: > Richard Biener <richard.guenther@gmail.com> writes: >> On Fri, Oct 30, 2015 at 12:18 PM, Richard Sandiford >> <richard.sandiford@arm.com> wrote: >>> The pass would free the dominance info after making a change, but it >>> should be pretty easy to keep the information up-to-date when the call >>> has no EH edges. In a way the main hurdle was split_block, which seemed >>> to assume that the new block would postdominate the old one, and that >>> all blocks immediately dominated by the old block are now immediately >>> dominated by the new one. >>> >>> Tested on x86_64-linux-gnu, arm-linux-gnueabi and aarch64-linux-gnu. >>> OK to install? >> >> Hmm, I don't understand why split_block needs to be touched. The >> operation itself correctly updates dominator info. It is up to the >> pass to fix things up if it does further CFG modifications that make >> the new block no longer post-dominate the old one. >> >> So why do you need the split_block change? > > The updates we'd need here would be: > > redirect_immediate_dominators (CDI_DOMINATORS, call, guard_bb); > > which undoes the earlier: > > redirect_immediate_dominators (CDI_DOMINATORS, guard_bb, call); > > that split_block did. It just seemed wasteful to call > redirect_immediate_dominators twice to get a no-op. > > In other words, there are going to be callers to split_block that > know the second block isn't going to postdominate the first and > where the calling; > > redirect_immediate_dominators (CDI_DOMINATORS, first_block, > second_block); > > is taking us further from where we want to be. That's true. In an ideal world we'd have a CFG hook creating a (half) diamond directly. I wonder how other passes work around this issue? I suppose they are splitting the block to form the conditonal block and the joiner? If you have those and then only split the fallthru edge between them the redundant work done is minimal. Richard. > Thanks, > Richard >
Richard Biener <richard.guenther@gmail.com> writes: > On Fri, Oct 30, 2015 at 1:14 PM, Richard Sandiford > <richard.sandiford@arm.com> wrote: >> Richard Biener <richard.guenther@gmail.com> writes: >>> On Fri, Oct 30, 2015 at 12:18 PM, Richard Sandiford >>> <richard.sandiford@arm.com> wrote: >>>> The pass would free the dominance info after making a change, but it >>>> should be pretty easy to keep the information up-to-date when the call >>>> has no EH edges. In a way the main hurdle was split_block, which seemed >>>> to assume that the new block would postdominate the old one, and that >>>> all blocks immediately dominated by the old block are now immediately >>>> dominated by the new one. >>>> >>>> Tested on x86_64-linux-gnu, arm-linux-gnueabi and aarch64-linux-gnu. >>>> OK to install? >>> >>> Hmm, I don't understand why split_block needs to be touched. The >>> operation itself correctly updates dominator info. It is up to the >>> pass to fix things up if it does further CFG modifications that make >>> the new block no longer post-dominate the old one. >>> >>> So why do you need the split_block change? >> >> The updates we'd need here would be: >> >> redirect_immediate_dominators (CDI_DOMINATORS, call, guard_bb); >> >> which undoes the earlier: >> >> redirect_immediate_dominators (CDI_DOMINATORS, guard_bb, call); >> >> that split_block did. It just seemed wasteful to call >> redirect_immediate_dominators twice to get a no-op. >> >> In other words, there are going to be callers to split_block that >> know the second block isn't going to postdominate the first and >> where the calling; >> >> redirect_immediate_dominators (CDI_DOMINATORS, first_block, >> second_block); >> >> is taking us further from where we want to be. > > That's true. In an ideal world we'd have a CFG hook creating a > (half) diamond directly. > > I wonder how other passes work around this issue? I suppose > they are splitting the block to form the conditonal block and the > joiner? If you have those and then only split the fallthru edge > between them the redundant work done is minimal. Yeah, but that then makes the code more complicated because you still need to split the call block from the guard block rather than the joiner in the EH case. It also means that you need to do more set_immediate_dominators (the call is not the immediate dominator of the join block), whereas with the current code that falls out naturally. Is the split_block change really so bad? Thanks, Richard
On Fri, Oct 30, 2015 at 2:11 PM, Richard Sandiford
<richard.sandiford@arm.com> wrote:
> Is the split_block change really so bad?
IMHO: Yes.
split_block just splits some basic block B into two blocks B1/B2
somewhere in the middle of B. The dominance relations between B1 and
B2 are obvious and intuitive. The new flag to split_block is not. The
dominance info is not updated but the loops are? Confusing, if you ask
me...
Your situation, where a pass knows the dominance relations will
change, is unusual. The extra work to fix up the ET tree twice should
be negligible anyway.
Ciao!
Steven
diff --git a/gcc/cfghooks.c b/gcc/cfghooks.c index 2c5c96c..82c427f 100644 --- a/gcc/cfghooks.c +++ b/gcc/cfghooks.c @@ -483,12 +483,18 @@ redirect_edge_and_branch_force (edge e, basic_block dest) return ret; } -/* Splits basic block BB after the specified instruction I (but at least after - the labels). If I is NULL, splits just after labels. The newly created edge - is returned. The new basic block is created just after the old one. */ +/* Splits basic block BB after the specified instruction I (but at least + after the labels). If I is NULL, splits just after labels. + + The newly created edge is returned. The new basic block is created + just after the old one. It is assumed that the old block will dominate + the new one; the caller can use set_immediate_dominator if this + assumption is wrong. If ASSUME_POSTDOM, it is further assumed that + the new block will postdominate the old block, so that all blocks + dominated by the old block are now also dominated by the new one. */ static edge -split_block_1 (basic_block bb, void *i) +split_block_1 (basic_block bb, void *i, bool assume_postdom) { basic_block new_bb; edge res; @@ -506,7 +512,8 @@ split_block_1 (basic_block bb, void *i) if (dom_info_available_p (CDI_DOMINATORS)) { - redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb); + if (assume_postdom) + redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb); set_immediate_dominator (CDI_DOMINATORS, new_bb, bb); } @@ -533,15 +540,15 @@ split_block_1 (basic_block bb, void *i) } edge -split_block (basic_block bb, gimple *i) +split_block (basic_block bb, gimple *i, bool assume_postdom) { - return split_block_1 (bb, i); + return split_block_1 (bb, i, assume_postdom); } edge -split_block (basic_block bb, rtx i) +split_block (basic_block bb, rtx i, bool assume_postdom) { - return split_block_1 (bb, i); + return split_block_1 (bb, i, assume_postdom); } /* Splits block BB just after labels. The newly created edge is returned. */ @@ -549,7 +556,7 @@ split_block (basic_block bb, rtx i) edge split_block_after_labels (basic_block bb) { - return split_block_1 (bb, NULL); + return split_block_1 (bb, NULL, true); } /* Moves block BB immediately after block AFTER. Returns false if the diff --git a/gcc/cfghooks.h b/gcc/cfghooks.h index a0cb6fd..8f6b465 100644 --- a/gcc/cfghooks.h +++ b/gcc/cfghooks.h @@ -208,8 +208,8 @@ extern edge redirect_edge_succ_nodup (edge, basic_block); extern bool can_remove_branch_p (const_edge); extern void remove_branch (edge); extern void remove_edge (edge); -extern edge split_block (basic_block, rtx); -extern edge split_block (basic_block, gimple *); +extern edge split_block (basic_block, rtx, bool = true); +extern edge split_block (basic_block, gimple *, bool = true); extern edge split_block_after_labels (basic_block); extern bool move_block_after (basic_block, basic_block); extern void delete_basic_block (basic_block); diff --git a/gcc/tree-call-cdce.c b/gcc/tree-call-cdce.c index 57be8a4..72828dd 100644 --- a/gcc/tree-call-cdce.c +++ b/gcc/tree-call-cdce.c @@ -735,6 +735,32 @@ shrink_wrap_one_built_in_call (gcall *bi_call) if (nconds == 0) return false; + /* The cfg we want to create looks like this: + + [guard n-1] <- guard_bb (old block) + | \ + | [guard n-2] } + | / \ } + | / ... } new blocks + | / [guard 0] } + | / / | } + [ call ] | <- bi_call_bb } + | \ | + | \ | + | [ join ] <- join_tgt_bb (old iff call must end bb) + | + possible EH edges (only if [join] is old) + + When [join] is new, the immediate dominators for these blocks are: + + 1. [guard n-1]: unchanged + 2. [call]: [guard n-1] + 3. [guard m]: [guard m+1] for 0 <= m <= n-2 + 4. [join]: [guard n-1] + + We punt for the more complex case case of [join] being old and + simply free the dominance info. We also punt on postdominators, + which aren't expected to be available at this point anyway. */ bi_call_bb = gimple_bb (bi_call); /* Now find the join target bb -- split bi_call_bb if needed. */ @@ -745,9 +771,13 @@ shrink_wrap_one_built_in_call (gcall *bi_call) join_tgt_in_edge_from_call = find_fallthru_edge (bi_call_bb->succs); if (join_tgt_in_edge_from_call == NULL) return false; + free_dominance_info (CDI_DOMINATORS); } else - join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call); + /* The old block ([guard n-1], currently called bi_call_bb) is the + immediate dominator of join_tgt_bb. join_tgt_bb will also + postdominate the guard block. */ + join_tgt_in_edge_from_call = split_block (bi_call_bb, bi_call, true); bi_call_bsi = gsi_for_stmt (bi_call); @@ -772,7 +802,10 @@ shrink_wrap_one_built_in_call (gcall *bi_call) ci++; gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND); - bi_call_in_edge0 = split_block (bi_call_bb, cond_expr); + /* The old block (for [guard n-1]) is the immediate dominator of the + new block (for the call). The call block does not postdominate + the guard block. */ + bi_call_in_edge0 = split_block (bi_call_bb, cond_expr, false); bi_call_in_edge0->flags &= ~EDGE_FALLTHRU; bi_call_in_edge0->flags |= EDGE_TRUE_VALUE; guard_bb = bi_call_bb; @@ -790,6 +823,7 @@ shrink_wrap_one_built_in_call (gcall *bi_call) guard_bb->count - bi_call_in_edge0->count; /* Code generation for the rest of the conditions */ + basic_block prev_guard_bb = NULL; while (nconds > 0) { unsigned ci0; @@ -809,7 +843,12 @@ shrink_wrap_one_built_in_call (gcall *bi_call) nconds--; ci++; gcc_assert (cond_expr && gimple_code (cond_expr) == GIMPLE_COND); - guard_bb_in_edge = split_block (guard_bb, cond_expr); + + /* The old block (for the guard we just added) is the immediate + dominator of the new block (for the previous guard). The new + block does not postdominate the old one; the immediate postdominator + of the old block is still join_tgt_bb. */ + guard_bb_in_edge = split_block (guard_bb, cond_expr, false); guard_bb_in_edge->flags &= ~EDGE_FALLTHRU; guard_bb_in_edge->flags |= EDGE_FALSE_VALUE; @@ -822,6 +861,13 @@ shrink_wrap_one_built_in_call (gcall *bi_call) guard_bb_in_edge->probability = inverse_probability (bi_call_in_edge->probability); guard_bb_in_edge->count = guard_bb->count - bi_call_in_edge->count; + + /* If this is [guard m] for m >= 2, make [guard m-1] the immediate + dominator of [guard m-2]. */ + if (prev_guard_bb && dom_info_available_p (CDI_DOMINATORS)) + set_immediate_dominator (CDI_DOMINATORS, prev_guard_bb, + guard_bb_in_edge->dest); + prev_guard_bb = guard_bb_in_edge->dest; } if (dump_file && (dump_flags & TDF_DETAILS)) @@ -931,7 +977,6 @@ pass_call_cdce::execute (function *fun) if (something_changed) { - free_dominance_info (CDI_DOMINATORS); free_dominance_info (CDI_POST_DOMINATORS); /* As we introduced new control-flow we need to insert PHI-nodes for the call-clobbers of the remaining call. */