Add phis in SimplifyIfs to enable branch redirection
For example it turns:
if(cond)
/ \
B1 B2
\ /
if(cond)
/ \
B3 B4
into:
if(cond)
/ \
B1 B2
\ /
if(Phi(1, 0))
/ \
B3 B4
Following this, SimplifyIfs is able to connect B1->B3
and B2->B4 effectively skipping an if.
Locally, speed compiling on a Pixel 5:
* system server: -4.0KB (-0.01%)
* SystemUIGoogle: -8.0KB (-0.03%)
* AGSA: -17.75KB (-0.01%)
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: I3b2e6a986b4d5e162bec28d72e9b0e2a3de1a4c3
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 8e3010d..5437d9b 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -313,54 +313,45 @@
return false;
}
-// Simplify the pattern:
-//
-// B1 B2 ...
-// goto goto goto
-// \ | /
-// \ | /
-// B3
-// i1 = phi(input, input)
-// (i2 = condition on i1)
-// if i1 (or i2)
-// / \
-// / \
-// B4 B5
-//
-// Into:
-//
-// B1 B2 ...
-// | | |
-// B4 B5 B?
-//
-// Note that individual edges can be redirected (for example B2->B3
-// can be redirected as B2->B5) without applying this optimization
-// to other incoming edges.
-//
-// This simplification cannot be applied to catch blocks, because
-// exception handler edges do not represent normal control flow.
-// Though in theory this could still apply to normal control flow
-// going directly to a catch block, we cannot support it at the
-// moment because the catch Phi's inputs do not correspond to the
-// catch block's predecessors, so we cannot identify which
-// predecessor corresponds to a given statically evaluated input.
-//
-// We do not apply this optimization to loop headers as this could
-// create irreducible loops. We rely on the suspend check in the
-// loop header to prevent the pattern match.
-//
-// Note that we rely on the dead code elimination to get rid of B3.
bool HDeadCodeElimination::SimplifyIfs() {
bool simplified_one_or_more_ifs = false;
bool rerun_dominance_and_loop_analysis = false;
- for (HBasicBlock* block : graph_->GetReversePostOrder()) {
+ // Iterating in PostOrder it's better for MaybeAddPhi as it can add a Phi for multiple If
+ // instructions in a chain without updating the dominator chain. The branch redirection itself can
+ // work in PostOrder or ReversePostOrder without issues.
+ for (HBasicBlock* block : graph_->GetPostOrder()) {
+ if (block->IsCatchBlock()) {
+ // This simplification cannot be applied to catch blocks, because exception handler edges do
+ // not represent normal control flow. Though in theory this could still apply to normal
+ // control flow going directly to a catch block, we cannot support it at the moment because
+ // the catch Phi's inputs do not correspond to the catch block's predecessors, so we cannot
+ // identify which predecessor corresponds to a given statically evaluated input.
+ continue;
+ }
+
HInstruction* last = block->GetLastInstruction();
- HInstruction* first = block->GetFirstInstruction();
- if (!block->IsCatchBlock() &&
- last->IsIf() &&
- block->HasSinglePhi() &&
+ if (!last->IsIf()) {
+ continue;
+ }
+
+ if (block->IsLoopHeader()) {
+ // We do not apply this optimization to loop headers as this could create irreducible loops.
+ continue;
+ }
+
+ // We will add a Phi which allows the simplification to take place in cases where it wouldn't.
+ MaybeAddPhi(block);
+
+ // TODO(solanes): Investigate support for multiple phis in `block`. We can potentially "push
+ // downwards" existing Phis into the true/false branches. For example, let's say we have another
+ // Phi: Phi(x1,x2,x3,x4,x5,x6). This could turn into Phi(x1,x2) in the true branch, Phi(x3,x4)
+ // in the false branch, and remain as Phi(x5,x6) in `block` (for edges that we couldn't
+ // redirect). We might even be able to remove some phis altogether as they will have only one
+ // value.
+ if (block->HasSinglePhi() &&
block->GetFirstPhi()->HasOnlyOneNonEnvironmentUse()) {
+ HInstruction* first = block->GetFirstInstruction();
bool has_only_phi_and_if = (last == first) && (last->InputAt(0) == block->GetFirstPhi());
bool has_only_phi_condition_and_if =
!has_only_phi_and_if &&
@@ -371,7 +362,6 @@
first->HasOnlyOneNonEnvironmentUse();
if (has_only_phi_and_if || has_only_phi_condition_and_if) {
- DCHECK(!block->IsLoopHeader());
HPhi* phi = block->GetFirstPhi()->AsPhi();
bool phi_input_is_left = (first->InputAt(0) == phi);
@@ -456,6 +446,125 @@
return simplified_one_or_more_ifs;
}
+void HDeadCodeElimination::MaybeAddPhi(HBasicBlock* block) {
+ DCHECK(block->GetLastInstruction()->IsIf());
+ HIf* if_instruction = block->GetLastInstruction()->AsIf();
+ if (if_instruction->InputAt(0)->IsConstant()) {
+ // Constant values are handled in RemoveDeadBlocks.
+ return;
+ }
+
+ if (block->GetNumberOfPredecessors() < 2u) {
+ // Nothing to redirect.
+ return;
+ }
+
+ if (!block->GetPhis().IsEmpty()) {
+ // SimplifyIf doesn't currently work with multiple phis. Adding a phi here won't help that
+ // optimization.
+ return;
+ }
+
+ HBasicBlock* dominator = block->GetDominator();
+ if (!dominator->EndsWithIf()) {
+ return;
+ }
+
+ HInstruction* input = if_instruction->InputAt(0);
+ HInstruction* dominator_input = dominator->GetLastInstruction()->AsIf()->InputAt(0);
+ const bool same_input = dominator_input == input;
+ if (!same_input) {
+ // Try to see if the dominator has the opposite input (e.g. if(cond) and if(!cond)). If that's
+ // the case, we can perform the optimization with the false and true branches reversed.
+ if (!dominator_input->IsCondition() || !input->IsCondition()) {
+ return;
+ }
+
+ HCondition* block_cond = input->AsCondition();
+ HCondition* dominator_cond = dominator_input->AsCondition();
+
+ if (block_cond->GetLeft() != dominator_cond->GetLeft() ||
+ block_cond->GetRight() != dominator_cond->GetRight() ||
+ block_cond->GetOppositeCondition() != dominator_cond->GetCondition()) {
+ return;
+ }
+ }
+
+ if (kIsDebugBuild) {
+ // `block`'s successors should have only one predecessor. Otherwise, we have a critical edge in
+ // the graph.
+ for (HBasicBlock* succ : block->GetSuccessors()) {
+ DCHECK_EQ(succ->GetNumberOfPredecessors(), 1u);
+ }
+ }
+
+ const size_t pred_size = block->GetNumberOfPredecessors();
+ HPhi* new_phi = new (graph_->GetAllocator())
+ HPhi(graph_->GetAllocator(), kNoRegNumber, pred_size, DataType::Type::kInt32);
+
+ for (size_t index = 0; index < pred_size; index++) {
+ HBasicBlock* pred = block->GetPredecessors()[index];
+ const bool dominated_by_true =
+ dominator->GetLastInstruction()->AsIf()->IfTrueSuccessor()->Dominates(pred);
+ const bool dominated_by_false =
+ dominator->GetLastInstruction()->AsIf()->IfFalseSuccessor()->Dominates(pred);
+ if (dominated_by_true == dominated_by_false) {
+ // In this case, we can't know if we are coming from the true branch, or the false branch. It
+ // happens in cases like:
+ // 1 (outer if)
+ // / \
+ // 2 3 (inner if)
+ // | / \
+ // | 4 5
+ // \/ |
+ // 6 |
+ // \ |
+ // 7 (has the same if(cond) as 1)
+ // |
+ // 8
+ // `7` (which would be `block` in this example), and `6` will come from both the true path and
+ // the false path of `1`. We bumped into something similar in SelectGenerator. See
+ // HSelectGenerator::TryFixupDoubleDiamondPattern.
+ // TODO(solanes): Figure out if we can fix up the graph into a double diamond in a generic way
+ // so that DeadCodeElimination and SelectGenerator can take advantage of it.
+
+ if (!same_input) {
+ // `1` and `7` having the opposite condition is a case we are missing. We could potentially
+ // add a BooleanNot instruction to be able to add the Phi, but it seems like overkill since
+ // this case is not that common.
+ return;
+ }
+
+ // The Phi will have `0`, `1`, and `cond` as inputs. If SimplifyIf redirects 0s and 1s, we
+ // will end up with Phi(cond,...,cond) which will be replaced by `cond`. Effectively, we will
+ // redirect edges that we are able to redirect and the rest will remain as before (i.e. we
+ // won't have an extra Phi).
+ new_phi->SetRawInputAt(index, input);
+ } else {
+ // Redirect to either the true branch (1), or the false branch (0).
+ // Given that `dominated_by_true` is the exact opposite of `dominated_by_false`,
+ // `(same_input && dominated_by_true) || (!same_input && dominated_by_false)` is equivalent to
+ // `same_input == dominated_by_true`.
+ new_phi->SetRawInputAt(
+ index,
+ same_input == dominated_by_true ? graph_->GetIntConstant(1) : graph_->GetIntConstant(0));
+ }
+ }
+
+ block->AddPhi(new_phi);
+ if_instruction->ReplaceInput(new_phi, 0);
+
+ // Remove the old input now, if possible. This allows the branch redirection in SimplifyIf to
+ // work without waiting for another pass of DCE.
+ if (input->IsDeadAndRemovable()) {
+ DCHECK(!same_input)
+ << " if both blocks have the same condition, it shouldn't be dead and removable since the "
+ << "dominator block's If instruction would be using that condition.";
+ input->GetBlock()->RemoveInstruction(input);
+ }
+ MaybeRecordStat(stats_, MethodCompilationStat::kSimplifyIfAddedPhi);
+}
+
void HDeadCodeElimination::ConnectSuccessiveBlocks() {
// Order does not matter. Skip the entry block by starting at index 1 in reverse post order.
for (size_t i = 1u, size = graph_->GetReversePostOrder().size(); i != size; ++i) {