Add a new control flow simplifier.
Run it in the dead code elimination phase, as it relates to
creating dead branches.
From 0.04 to 0.07% less code size framework/gms/docs/fb (70K saved on fb)
3%-5% runtime performance improvements on Richards/DeltaBlue/Ritz.
Compile-time is mixed, so in the noise (from 2% slower to 1% faster).
test:611-checker-simplify-if
Change-Id: Ife8b7882d57b5481f5ca9dc163beba655d7e78bf
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 49cfff4..e1bde7c 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -88,13 +88,207 @@
}
}
-void HDeadCodeElimination::RemoveDeadBlocks() {
- if (graph_->HasIrreducibleLoops()) {
- // Do not eliminate dead blocks if the graph has irreducible loops. We could
- // support it, but that would require changes in our loop representation to handle
- // multiple entry points. We decided it was not worth the complexity.
- return;
+void HDeadCodeElimination::MaybeRecordSimplifyIf() {
+ if (stats_ != nullptr) {
+ stats_->RecordStat(MethodCompilationStat::kSimplifyIf);
}
+}
+
+static bool HasInput(HCondition* instruction, HInstruction* input) {
+ return (instruction->InputAt(0) == input) ||
+ (instruction->InputAt(1) == input);
+}
+
+static bool HasEquality(IfCondition condition) {
+ switch (condition) {
+ case kCondEQ:
+ case kCondLE:
+ case kCondGE:
+ case kCondBE:
+ case kCondAE:
+ return true;
+ case kCondNE:
+ case kCondLT:
+ case kCondGT:
+ case kCondB:
+ case kCondA:
+ return false;
+ }
+}
+
+static HConstant* Evaluate(HCondition* condition, HInstruction* left, HInstruction* right) {
+ if (left == right && !Primitive::IsFloatingPointType(left->GetType())) {
+ return condition->GetBlock()->GetGraph()->GetIntConstant(
+ HasEquality(condition->GetCondition()) ? 1 : 0);
+ }
+
+ if (!left->IsConstant() || !right->IsConstant()) {
+ return nullptr;
+ }
+
+ if (left->IsIntConstant()) {
+ return condition->Evaluate(left->AsIntConstant(), right->AsIntConstant());
+ } else if (left->IsNullConstant()) {
+ return condition->Evaluate(left->AsNullConstant(), right->AsNullConstant());
+ } else if (left->IsLongConstant()) {
+ return condition->Evaluate(left->AsLongConstant(), right->AsLongConstant());
+ } else if (left->IsFloatConstant()) {
+ return condition->Evaluate(left->AsFloatConstant(), right->AsFloatConstant());
+ } else {
+ DCHECK(left->IsDoubleConstant());
+ return condition->Evaluate(left->AsDoubleConstant(), right->AsDoubleConstant());
+ }
+}
+
+// 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?
+//
+// This simplification cannot be applied for loop headers, as they
+// contain a suspend check.
+//
+// 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 (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ HInstruction* last = block->GetLastInstruction();
+ HInstruction* first = block->GetFirstInstruction();
+ if (last->IsIf() &&
+ block->HasSinglePhi() &&
+ block->GetFirstPhi()->HasOnlyOneNonEnvironmentUse()) {
+ 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 &&
+ first->IsCondition() &&
+ HasInput(first->AsCondition(), block->GetFirstPhi()) &&
+ (first->GetNext() == last) &&
+ (last->InputAt(0) == first) &&
+ 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);
+
+ // Walk over all inputs of the phis and update the control flow of
+ // predecessors feeding constants to the phi.
+ // Note that phi->InputCount() may change inside the loop.
+ for (size_t i = 0; i < phi->InputCount();) {
+ HInstruction* input = phi->InputAt(i);
+ HInstruction* value_to_check = nullptr;
+ if (has_only_phi_and_if) {
+ if (input->IsIntConstant()) {
+ value_to_check = input;
+ }
+ } else {
+ DCHECK(has_only_phi_condition_and_if);
+ if (phi_input_is_left) {
+ value_to_check = Evaluate(first->AsCondition(), input, first->InputAt(1));
+ } else {
+ value_to_check = Evaluate(first->AsCondition(), first->InputAt(0), input);
+ }
+ }
+ if (value_to_check == nullptr) {
+ // Could not evaluate to a constant, continue iterating over the inputs.
+ ++i;
+ } else {
+ HBasicBlock* predecessor_to_update = block->GetPredecessors()[i];
+ HBasicBlock* successor_to_update = nullptr;
+ if (value_to_check->AsIntConstant()->IsTrue()) {
+ successor_to_update = last->AsIf()->IfTrueSuccessor();
+ } else {
+ DCHECK(value_to_check->AsIntConstant()->IsFalse())
+ << value_to_check->AsIntConstant()->GetValue();
+ successor_to_update = last->AsIf()->IfFalseSuccessor();
+ }
+ predecessor_to_update->ReplaceSuccessor(block, successor_to_update);
+ phi->RemoveInputAt(i);
+ simplified_one_or_more_ifs = true;
+ if (block->IsInLoop()) {
+ rerun_dominance_and_loop_analysis = true;
+ }
+ // For simplicity, don't create a dead block, let the dead code elimination
+ // pass deal with it.
+ if (phi->InputCount() == 1) {
+ break;
+ }
+ }
+ }
+ if (block->GetPredecessors().size() == 1) {
+ phi->ReplaceWith(phi->InputAt(0));
+ block->RemovePhi(phi);
+ if (has_only_phi_condition_and_if) {
+ // Evaluate here (and not wait for a constant folding pass) to open
+ // more opportunities for DCE.
+ HInstruction* result = first->AsCondition()->TryStaticEvaluation();
+ if (result != nullptr) {
+ first->ReplaceWith(result);
+ block->RemoveInstruction(first);
+ }
+ }
+ }
+ if (simplified_one_or_more_ifs) {
+ MaybeRecordSimplifyIf();
+ }
+ }
+ }
+ }
+ // We need to re-analyze the graph in order to run DCE afterwards.
+ if (simplified_one_or_more_ifs) {
+ if (rerun_dominance_and_loop_analysis) {
+ graph_->ClearLoopInformation();
+ graph_->ClearDominanceInformation();
+ graph_->BuildDominatorTree();
+ } else {
+ graph_->ClearDominanceInformation();
+ // We have introduced critical edges, remove them.
+ graph_->SimplifyCFG();
+ graph_->ComputeDominanceInformation();
+ graph_->ComputeTryBlockInformation();
+ }
+ }
+
+ return simplified_one_or_more_ifs;
+}
+
+void HDeadCodeElimination::ConnectSuccessiveBlocks() {
+ // Order does not matter.
+ for (HReversePostOrderIterator it(*graph_); !it.Done();) {
+ HBasicBlock* block = it.Current();
+ if (block->IsEntryBlock() || !block->GetLastInstruction()->IsGoto()) {
+ it.Advance();
+ continue;
+ }
+ HBasicBlock* successor = block->GetSingleSuccessor();
+ if (successor->IsExitBlock() || successor->GetPredecessors().size() != 1u) {
+ it.Advance();
+ continue;
+ }
+ block->MergeWith(successor);
+ // Reiterate on this block in case it can be merged with its new successor.
+ }
+}
+
+bool HDeadCodeElimination::RemoveDeadBlocks() {
// Classify blocks as reachable/unreachable.
ArenaAllocator* allocator = graph_->GetArena();
ArenaBitVector live_blocks(allocator, graph_->GetBlocks().size(), false, kArenaAllocDCE);
@@ -132,23 +326,7 @@
graph_->ComputeTryBlockInformation();
}
}
-
- // Connect successive blocks created by dead branches. Order does not matter.
- for (HReversePostOrderIterator it(*graph_); !it.Done();) {
- HBasicBlock* block = it.Current();
- if (block->IsEntryBlock() || !block->GetLastInstruction()->IsGoto()) {
- it.Advance();
- continue;
- }
- HBasicBlock* successor = block->GetSingleSuccessor();
- if (successor->IsExitBlock() || successor->GetPredecessors().size() != 1u) {
- it.Advance();
- continue;
- }
- block->MergeWith(successor);
-
- // Reiterate on this block in case it can be merged with its new successor.
- }
+ return removed_one_or_more_blocks;
}
void HDeadCodeElimination::RemoveDeadInstructions() {
@@ -181,7 +359,20 @@
}
void HDeadCodeElimination::Run() {
- RemoveDeadBlocks();
+ // Do not eliminate dead blocks if the graph has irreducible loops. We could
+ // support it, but that would require changes in our loop representation to handle
+ // multiple entry points. We decided it was not worth the complexity.
+ if (!graph_->HasIrreducibleLoops()) {
+ // Simplify graph to generate more dead block patterns.
+ ConnectSuccessiveBlocks();
+ bool did_any_simplification = false;
+ did_any_simplification |= SimplifyIfs();
+ did_any_simplification |= RemoveDeadBlocks();
+ if (did_any_simplification) {
+ // Connect successive blocks created by dead branches.
+ ConnectSuccessiveBlocks();
+ }
+ }
SsaRedundantPhiElimination(graph_).Run();
RemoveDeadInstructions();
}
diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h
index 8d6008b..0ce0ec1 100644
--- a/compiler/optimizing/dead_code_elimination.h
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -41,8 +41,11 @@
private:
void MaybeRecordDeadBlock(HBasicBlock* block);
- void RemoveDeadBlocks();
+ void MaybeRecordSimplifyIf();
+ bool RemoveDeadBlocks();
void RemoveDeadInstructions();
+ bool SimplifyIfs();
+ void ConnectSuccessiveBlocks();
DISALLOW_COPY_AND_ASSIGN(HDeadCodeElimination);
};
diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h
index 9cc6ea4..c8d1ce0 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -65,6 +65,7 @@
kInlinedInvokeVirtualOrInterface,
kImplicitNullCheckGenerated,
kExplicitNullCheckGenerated,
+ kSimplifyIf,
kLastStat
};
@@ -143,6 +144,7 @@
case kInlinedInvokeVirtualOrInterface: name = "InlinedInvokeVirtualOrInterface"; break;
case kImplicitNullCheckGenerated: name = "ImplicitNullCheckGenerated"; break;
case kExplicitNullCheckGenerated: name = "ExplicitNullCheckGenerated"; break;
+ case kSimplifyIf: name = "SimplifyIf"; break;
case kLastStat:
LOG(FATAL) << "invalid stat "
diff --git a/test/458-checker-instruction-simplification/src/Main.java b/test/458-checker-instruction-simplification/src/Main.java
index 359d521..040479e 100644
--- a/test/458-checker-instruction-simplification/src/Main.java
+++ b/test/458-checker-instruction-simplification/src/Main.java
@@ -1142,7 +1142,13 @@
public static boolean $noinline$EqualBoolVsIntConst(boolean arg) {
if (doThrow) { throw new Error(); }
- return (arg ? 0 : 1) != 2;
+ // Make calls that will be inlined to make sure the instruction simplifier
+ // sees the simplification (dead code elimination will also try to simplify it).
+ return (arg ? $inline$ReturnArg(0) : $inline$ReturnArg(1)) != 2;
+ }
+
+ public static int $inline$ReturnArg(int arg) {
+ return arg;
}
/// CHECK-START: boolean Main.$noinline$NotEqualBoolVsIntConst(boolean) instruction_simplifier_after_bce (before)
@@ -1161,7 +1167,9 @@
public static boolean $noinline$NotEqualBoolVsIntConst(boolean arg) {
if (doThrow) { throw new Error(); }
- return (arg ? 0 : 1) == 2;
+ // Make calls that will be inlined to make sure the instruction simplifier
+ // sees the simplification (dead code elimination will also try to simplify it).
+ return (arg ? $inline$ReturnArg(0) : $inline$ReturnArg(1)) == 2;
}
/*
diff --git a/test/611-checker-simplify-if/expected.txt b/test/611-checker-simplify-if/expected.txt
new file mode 100644
index 0000000..3083c4c
--- /dev/null
+++ b/test/611-checker-simplify-if/expected.txt
@@ -0,0 +1,7 @@
+54
+54
+54
+12
+12
+12
+33
diff --git a/test/611-checker-simplify-if/info.txt b/test/611-checker-simplify-if/info.txt
new file mode 100644
index 0000000..b090db8
--- /dev/null
+++ b/test/611-checker-simplify-if/info.txt
@@ -0,0 +1 @@
+Checker tests for the 'if' simplification in the compiler.
diff --git a/test/611-checker-simplify-if/src/Main.java b/test/611-checker-simplify-if/src/Main.java
new file mode 100644
index 0000000..21f4115
--- /dev/null
+++ b/test/611-checker-simplify-if/src/Main.java
@@ -0,0 +1,281 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class Main {
+
+ public static void main(String[] args) {
+ testNoInline(args);
+ System.out.println(staticField);
+ testInline(args);
+ System.out.println(staticField);
+ testNonConstantInputs(args);
+ System.out.println(staticField);
+ testNonConstantEqual(args);
+ System.out.println(staticField);
+ testGreaterCondition(args);
+ System.out.println(staticField);
+ testSwitch(args);
+ System.out.println(staticField);
+ testFP(args);
+ System.out.println(staticField);
+ }
+
+ // Test when a condition is the input of the if.
+
+ /// CHECK-START: void Main.testNoInline(java.lang.String[]) dead_code_elimination (before)
+ /// CHECK: <<Const0:i\d+>> IntConstant 0
+ /// CHECK: If
+ /// CHECK: <<Phi:i\d+>> Phi
+ /// CHECK: <<Equal:z\d+>> Equal [<<Phi>>,<<Const0>>]
+ /// CHECK: If [<<Equal>>]
+
+ /// CHECK-START: void Main.testNoInline(java.lang.String[]) dead_code_elimination (after)
+ /// CHECK: If
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: Equal
+ /// CHECK-NOT: If
+ public static void testNoInline(String[] args) {
+ boolean myVar = false;
+ if (args.length == 42) {
+ myVar = true;
+ } else {
+ staticField = 32;
+ myVar = false;
+ }
+ if (myVar) {
+ staticField = 12;
+ } else {
+ staticField = 54;
+ }
+ }
+
+ // Test when the phi is the input of the if.
+
+ /// CHECK-START: void Main.testInline(java.lang.String[]) dead_code_elimination_final (before)
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0
+ /// CHECK-DAG: If
+ /// CHECK-DAG: <<Phi:i\d+>> Phi
+ /// CHECK-DAG: If [<<Phi>>]
+
+ /// CHECK-START: void Main.testInline(java.lang.String[]) dead_code_elimination_final (after)
+ /// CHECK: If
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: If
+ public static void testInline(String[] args) {
+ boolean myVar = $inline$doTest(args);
+ if (myVar) {
+ staticField = 12;
+ } else {
+ staticField = 54;
+ }
+ }
+
+ public static boolean $inline$doTest(String[] args) {
+ boolean myVar;
+ if (args.length == 42) {
+ myVar = true;
+ } else {
+ staticField = 32;
+ myVar = false;
+ }
+ return myVar;
+ }
+
+ // Test when one input is not a constant. We can only optimize the constant input.
+
+ /// CHECK-START: void Main.testNonConstantInputs(java.lang.String[]) dead_code_elimination (before)
+ /// CHECK-DAG: <<Const34:i\d+>> IntConstant 34
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: If
+ /// CHECK-DAG: <<StaticFieldGet:i\d+>> StaticFieldGet
+ /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const34>>,<<StaticFieldGet>>]
+ /// CHECK-DAG: <<NotEqual:z\d+>> NotEqual [<<Phi>>,<<Const42>>]
+ /// CHECK-DAG: If [<<NotEqual>>]
+
+ /// CHECK-START: void Main.testNonConstantInputs(java.lang.String[]) dead_code_elimination (after)
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: If
+ /// CHECK-DAG: <<StaticFieldGet:i\d+>> StaticFieldGet
+ /// CHECK-NOT: Phi
+ /// CHECK-DAG: <<NotEqual:z\d+>> NotEqual [<<StaticFieldGet>>,<<Const42>>]
+ /// CHECK-DAG: If [<<NotEqual>>]
+ public static void testNonConstantInputs(String[] args) {
+ int a = 42;
+ if (args.length == 42) {
+ a = 34;
+ } else {
+ staticField = 32;
+ a = otherStaticField;
+ }
+ if (a == 42) {
+ staticField = 12;
+ } else {
+ staticField = 54;
+ }
+ }
+
+ // Test with a condition.
+
+ /// CHECK-START: void Main.testGreaterCondition(java.lang.String[]) dead_code_elimination (before)
+ /// CHECK-DAG: <<Const34:i\d+>> IntConstant 34
+ /// CHECK-DAG: <<Const22:i\d+>> IntConstant 22
+ /// CHECK-DAG: <<Const25:i\d+>> IntConstant 25
+ /// CHECK-DAG: If
+ /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const34>>,<<Const22>>]
+ /// CHECK-DAG: <<GE:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Const25>>]
+ /// CHECK-DAG: If [<<GE>>]
+
+ /// CHECK-START: void Main.testGreaterCondition(java.lang.String[]) dead_code_elimination (after)
+ /// CHECK-DAG: If
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: GreaterThanOrEqual
+ /// CHECK-NOT: If
+ public static void testGreaterCondition(String[] args) {
+ int a = 42;;
+ if (args.length == 42) {
+ a = 34;
+ } else {
+ staticField = 32;
+ a = 22;
+ }
+ if (a < 25) {
+ staticField = 12;
+ } else {
+ staticField = 54;
+ }
+ }
+
+ // Test when comparing non constants.
+
+ /// CHECK-START: void Main.testNonConstantEqual(java.lang.String[]) dead_code_elimination (before)
+ /// CHECK-DAG: <<Const34:i\d+>> IntConstant 34
+ /// CHECK-DAG: <<Const42:i\d+>> IntConstant 42
+ /// CHECK-DAG: If
+ /// CHECK-DAG: <<StaticFieldGet:i\d+>> StaticFieldGet
+ /// CHECK-DAG: <<Phi:i\d+>> Phi [<<Const34>>,<<StaticFieldGet>>]
+ /// CHECK-DAG: <<NotEqual:z\d+>> NotEqual [<<Phi>>,<<StaticFieldGet>>]
+ /// CHECK-DAG: If [<<NotEqual>>]
+
+ /// CHECK-START: void Main.testNonConstantEqual(java.lang.String[]) dead_code_elimination (after)
+ /// CHECK-DAG: <<Const34:i\d+>> IntConstant 34
+ /// CHECK-DAG: If
+ /// CHECK-DAG: <<StaticFieldGet:i\d+>> StaticFieldGet
+ /// CHECK-NOT: Phi
+ /// CHECK-DAG: <<NotEqual:z\d+>> NotEqual [<<Const34>>,<<StaticFieldGet>>]
+ /// CHECK-DAG: If [<<NotEqual>>]
+ public static void testNonConstantEqual(String[] args) {
+ int a = 42;
+ int b = otherStaticField;
+ if (args.length == 42) {
+ a = 34;
+ } else {
+ staticField = 32;
+ a = b;
+ }
+ if (a == b) {
+ staticField = 12;
+ } else {
+ staticField = 54;
+ }
+ }
+
+ // Make sure we don't "simplify" a loop and potentially turn it into
+ // an irreducible loop. The suspend check at the loop header prevents
+ // us from doing the simplification.
+
+ /// CHECK-START: void Main.testLoop(boolean) disassembly (after)
+ /// CHECK-DAG: SuspendCheck
+ /// CHECK: irreducible:false
+ /// CHECK-NOT: irreducible:true
+ public static void testLoop(boolean c) {
+ while (true) {
+ if (c) {
+ if ($noinline$foo()) return;
+ c = false;
+ } else {
+ $noinline$foo();
+ c = true;
+ }
+ }
+ }
+
+ static boolean $noinline$foo() {
+ if (doThrow) throw new Error("");
+ return true;
+ }
+
+ /// CHECK-START: void Main.testSwitch(java.lang.String[]) dead_code_elimination (before)
+ /// CHECK: If
+ /// CHECK: If
+ /// CHECK: If
+
+ /// CHECK-START: void Main.testSwitch(java.lang.String[]) dead_code_elimination (after)
+ /// CHECK: If
+ /// CHECK: If
+ /// CHECK-NOT: If
+ public static void testSwitch(String[] args) {
+ boolean cond = false;
+ switch (args.length) {
+ case 42:
+ staticField = 11;
+ cond = true;
+ break;
+ case 43:
+ staticField = 33;
+ cond = true;
+ break;
+ default:
+ cond = false;
+ break;
+ }
+ if (cond) {
+ // Redirect case 42 and 43 here.
+ staticField = 2;
+ }
+ // Redirect default here.
+ }
+
+ /// CHECK-START: void Main.testFP(java.lang.String[]) dead_code_elimination (before)
+ /// CHECK: If
+ /// CHECK: If
+
+ /// CHECK-START: void Main.testFP(java.lang.String[]) dead_code_elimination (after)
+ /// CHECK: If
+ /// CHECK: If
+ public static void testFP(String[] args) {
+ float f = 2.2f;
+ float nan = $noinline$getNaN();
+ if (args.length == 42) {
+ f = 4.3f;
+ } else {
+ staticField = 33;
+ f = nan;
+ }
+ if (f == nan) {
+ staticField = 5;
+ }
+ }
+
+ // No inline variant to avoid having the compiler see it's a NaN.
+ static float $noinline$getNaN() {
+ if (doThrow) throw new Error("");
+ return Float.NaN;
+ }
+
+ static boolean doThrow;
+ static int staticField;
+ static int otherStaticField;
+}
