ART: Simplify more bool operations
Now that we have the HBooleanNot instruction, the instruction
simplifier can optimize out more conditions comparing a boolean
against a constant, as well as sequences of Boolean negations.
Change-Id: I7f634f6428a3984dd97b27b3d6362491346f1ff6
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index afbc490..b8ae1f6 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -43,6 +43,8 @@
void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
void VisitEqual(HEqual* equal) OVERRIDE;
+ void VisitNotEqual(HNotEqual* equal) OVERRIDE;
+ void VisitBooleanNot(HBooleanNot* bool_not) OVERRIDE;
void VisitArraySet(HArraySet* equal) OVERRIDE;
void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE;
void VisitNullCheck(HNullCheck* instruction) OVERRIDE;
@@ -195,21 +197,62 @@
}
void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) {
- HInstruction* input1 = equal->InputAt(0);
- HInstruction* input2 = equal->InputAt(1);
- if (input1->GetType() == Primitive::kPrimBoolean && input2->IsIntConstant()) {
- if (input2->AsIntConstant()->GetValue() == 1) {
- // Replace (bool_value == 1) with bool_value
- equal->ReplaceWith(equal->InputAt(0));
- equal->GetBlock()->RemoveInstruction(equal);
- } else {
- // We should replace (bool_value == 0) with !bool_value, but we unfortunately
- // do not have such instruction.
- DCHECK_EQ(input2->AsIntConstant()->GetValue(), 0);
+ HInstruction* input_const = equal->GetConstantRight();
+ if (input_const != nullptr) {
+ HInstruction* input_value = equal->GetLeastConstantLeft();
+ if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) {
+ HBasicBlock* block = equal->GetBlock();
+ if (input_const->AsIntConstant()->IsOne()) {
+ // Replace (bool_value == true) with bool_value
+ equal->ReplaceWith(input_value);
+ block->RemoveInstruction(equal);
+ RecordSimplification();
+ } else {
+ // Replace (bool_value == false) with !bool_value
+ DCHECK(input_const->AsIntConstant()->IsZero());
+ block->ReplaceAndRemoveInstructionWith(
+ equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value));
+ RecordSimplification();
+ }
}
}
}
+void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) {
+ HInstruction* input_const = not_equal->GetConstantRight();
+ if (input_const != nullptr) {
+ HInstruction* input_value = not_equal->GetLeastConstantLeft();
+ if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) {
+ HBasicBlock* block = not_equal->GetBlock();
+ if (input_const->AsIntConstant()->IsOne()) {
+ // Replace (bool_value != true) with !bool_value
+ block->ReplaceAndRemoveInstructionWith(
+ not_equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value));
+ RecordSimplification();
+ } else {
+ // Replace (bool_value != false) with bool_value
+ DCHECK(input_const->AsIntConstant()->IsZero());
+ not_equal->ReplaceWith(input_value);
+ block->RemoveInstruction(not_equal);
+ RecordSimplification();
+ }
+ }
+ }
+}
+
+void InstructionSimplifierVisitor::VisitBooleanNot(HBooleanNot* bool_not) {
+ HInstruction* parent = bool_not->InputAt(0);
+ if (parent->IsBooleanNot()) {
+ HInstruction* value = parent->InputAt(0);
+ // Replace (!(!bool_value)) with bool_value
+ bool_not->ReplaceWith(value);
+ bool_not->GetBlock()->RemoveInstruction(bool_not);
+ // It is possible that `parent` is dead at this point but we leave
+ // its removal to DCE for simplicity.
+ RecordSimplification();
+ }
+}
+
void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) {
HInstruction* input = instruction->InputAt(0);
// If the array is a NewArray with constant size, replace the array length
diff --git a/compiler/optimizing/reference_type_propagation.cc b/compiler/optimizing/reference_type_propagation.cc
index 479b87f..31ddbb7 100644
--- a/compiler/optimizing/reference_type_propagation.cc
+++ b/compiler/optimizing/reference_type_propagation.cc
@@ -102,14 +102,17 @@
if (!lastInstruction->IsIf()) {
return;
}
+
HInstruction* ifInput = lastInstruction->InputAt(0);
- // TODO: Handle more patterns here: HIf(bool) HIf(HNotEqual).
- if (!ifInput->IsEqual()) {
- return;
- }
- HInstruction* instanceOf = ifInput->InputAt(0);
- HInstruction* comp_value = ifInput->InputAt(1);
- if (!instanceOf->IsInstanceOf() || !comp_value->IsIntConstant()) {
+ HInstruction* instanceOf;
+ HBasicBlock* instanceOfTrueBlock;
+ if (ifInput->IsInstanceOf()) {
+ instanceOf = ifInput;
+ instanceOfTrueBlock = lastInstruction->AsIf()->IfTrueSuccessor();
+ } else if (ifInput->IsBooleanNot() && ifInput->InputAt(0)->IsInstanceOf()) {
+ instanceOf = ifInput->InputAt(0);
+ instanceOfTrueBlock = lastInstruction->AsIf()->IfFalseSuccessor();
+ } else {
return;
}
@@ -132,11 +135,6 @@
}
block->InsertInstructionBefore(bound_type, lastInstruction);
- // Pick the right successor based on the value we compare against.
- HIntConstant* comp_value_int = comp_value->AsIntConstant();
- HBasicBlock* instanceOfTrueBlock = comp_value_int->GetValue() == 0
- ? lastInstruction->AsIf()->IfFalseSuccessor()
- : lastInstruction->AsIf()->IfTrueSuccessor();
for (HUseIterator<HInstruction*> it(obj->GetUses()); !it.Done(); it.Advance()) {
HInstruction* user = it.Current()->GetUser();
diff --git a/test/458-checker-instruction-simplification/src/Main.java b/test/458-checker-instruction-simplification/src/Main.java
index 3cbcebb..65be6cb 100644
--- a/test/458-checker-instruction-simplification/src/Main.java
+++ b/test/458-checker-instruction-simplification/src/Main.java
@@ -16,6 +16,12 @@
public class Main {
+ public static void assertBooleanEquals(boolean expected, boolean result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+
public static void assertIntEquals(int expected, int result) {
if (expected != result) {
throw new Error("Expected: " + expected + ", found: " + result);
@@ -41,7 +47,7 @@
// CHECK-START: long Main.Add0(long) instruction_simplifier (after)
// CHECK-DAG: [[Arg:j\d+]] ParameterValue
// CHECK-DAG: Return [ [[Arg]] ]
- //
+
// CHECK-START: long Main.Add0(long) instruction_simplifier (after)
// CHECK-NOT: Add
@@ -760,6 +766,147 @@
return res;
}
+ // CHECK-START: int Main.EqualTrueRhs(boolean) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[Const1:i\d+]] IntConstant 1
+ // CHECK-DAG: [[Cond:z\d+]] Equal [ [[Arg]] [[Const1]] ]
+ // CHECK-DAG: If [ [[Cond]] ]
+
+ // CHECK-START: int Main.EqualTrueRhs(boolean) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: If [ [[Arg]] ]
+
+ public static int EqualTrueRhs(boolean arg) {
+ return (arg != true) ? 3 : 5;
+ }
+
+ // CHECK-START: int Main.EqualTrueLhs(boolean) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[Const1:i\d+]] IntConstant 1
+ // CHECK-DAG: [[Cond:z\d+]] Equal [ [[Const1]] [[Arg]] ]
+ // CHECK-DAG: If [ [[Cond]] ]
+
+ // CHECK-START: int Main.EqualTrueLhs(boolean) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: If [ [[Arg]] ]
+
+ public static int EqualTrueLhs(boolean arg) {
+ return (true != arg) ? 3 : 5;
+ }
+
+ // CHECK-START: int Main.EqualFalseRhs(boolean) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[Const0:i\d+]] IntConstant 0
+ // CHECK-DAG: [[Cond:z\d+]] Equal [ [[Arg]] [[Const0]] ]
+ // CHECK-DAG: If [ [[Cond]] ]
+
+ // CHECK-START: int Main.EqualFalseRhs(boolean) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[NotArg:z\d+]] BooleanNot [ [[Arg]] ]
+ // CHECK-DAG: If [ [[NotArg]] ]
+
+ public static int EqualFalseRhs(boolean arg) {
+ return (arg != false) ? 3 : 5;
+ }
+
+ // CHECK-START: int Main.EqualFalseLhs(boolean) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[Const0:i\d+]] IntConstant 0
+ // CHECK-DAG: [[Cond:z\d+]] Equal [ [[Const0]] [[Arg]] ]
+ // CHECK-DAG: If [ [[Cond]] ]
+
+ // CHECK-START: int Main.EqualFalseLhs(boolean) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[NotArg:z\d+]] BooleanNot [ [[Arg]] ]
+ // CHECK-DAG: If [ [[NotArg]] ]
+
+ public static int EqualFalseLhs(boolean arg) {
+ return (false != arg) ? 3 : 5;
+ }
+
+ // CHECK-START: int Main.NotEqualTrueRhs(boolean) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[Const1:i\d+]] IntConstant 1
+ // CHECK-DAG: [[Cond:z\d+]] NotEqual [ [[Arg]] [[Const1]] ]
+ // CHECK-DAG: If [ [[Cond]] ]
+
+ // CHECK-START: int Main.NotEqualTrueRhs(boolean) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[NotArg:z\d+]] BooleanNot [ [[Arg]] ]
+ // CHECK-DAG: If [ [[NotArg]] ]
+
+ public static int NotEqualTrueRhs(boolean arg) {
+ return (arg == true) ? 3 : 5;
+ }
+
+ // CHECK-START: int Main.NotEqualTrueLhs(boolean) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[Const1:i\d+]] IntConstant 1
+ // CHECK-DAG: [[Cond:z\d+]] NotEqual [ [[Const1]] [[Arg]] ]
+ // CHECK-DAG: If [ [[Cond]] ]
+
+ // CHECK-START: int Main.NotEqualTrueLhs(boolean) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[NotArg:z\d+]] BooleanNot [ [[Arg]] ]
+ // CHECK-DAG: If [ [[NotArg]] ]
+
+ public static int NotEqualTrueLhs(boolean arg) {
+ return (true == arg) ? 3 : 5;
+ }
+
+ // CHECK-START: int Main.NotEqualFalseRhs(boolean) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[Const0:i\d+]] IntConstant 0
+ // CHECK-DAG: [[Cond:z\d+]] NotEqual [ [[Arg]] [[Const0]] ]
+ // CHECK-DAG: If [ [[Cond]] ]
+
+ // CHECK-START: int Main.NotEqualFalseRhs(boolean) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: If [ [[Arg]] ]
+
+ public static int NotEqualFalseRhs(boolean arg) {
+ return (arg == false) ? 3 : 5;
+ }
+
+ // CHECK-START: int Main.NotEqualFalseLhs(boolean) instruction_simplifier (before)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[Const0:i\d+]] IntConstant 0
+ // CHECK-DAG: [[Cond:z\d+]] NotEqual [ [[Const0]] [[Arg]] ]
+ // CHECK-DAG: If [ [[Cond]] ]
+
+ // CHECK-START: int Main.NotEqualFalseLhs(boolean) instruction_simplifier (after)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: If [ [[Arg]] ]
+
+ public static int NotEqualFalseLhs(boolean arg) {
+ return (false == arg) ? 3 : 5;
+ }
+
+ /*
+ * Test simplification of double Boolean negation. Note that sometimes
+ * both negations can be removed but we only expect the simplifier to
+ * remove the second.
+ */
+
+ // CHECK-START: boolean Main.NotNotBool(boolean) instruction_simplifier_after_types (before)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: [[NotArg:z\d+]] BooleanNot [ [[Arg]] ]
+ // CHECK-DAG: [[NotNotArg:z\d+]] BooleanNot [ [[NotArg]] ]
+ // CHECK-DAG: Return [ [[NotNotArg]] ]
+
+ // CHECK-START: boolean Main.NotNotBool(boolean) instruction_simplifier_after_types (after)
+ // CHECK-DAG: [[Arg:z\d+]] ParameterValue
+ // CHECK-DAG: BooleanNot [ [[Arg]] ]
+ // CHECK-DAG: Return [ [[Arg]] ]
+
+ // CHECK-START: boolean Main.NotNotBool(boolean) instruction_simplifier_after_types (after)
+ // CHECK: BooleanNot
+ // CHECK-NOT: BooleanNot
+
+ public static boolean NotNotBool(boolean arg) {
+ return !(!arg);
+ }
+
public static void main(String[] args) {
int arg = 123456;
@@ -794,5 +941,16 @@
assertIntEquals(SubNeg1(arg, arg + 1), -(arg + arg + 1));
assertIntEquals(SubNeg2(arg, arg + 1), -(arg + arg + 1));
assertLongEquals(SubNeg3(arg, arg + 1), -(2 * arg + 1));
+
+ assertIntEquals(EqualTrueRhs(true), 5);
+ assertIntEquals(EqualTrueLhs(true), 5);
+ assertIntEquals(EqualFalseRhs(true), 3);
+ assertIntEquals(EqualFalseLhs(true), 3);
+ assertIntEquals(NotEqualTrueRhs(true), 3);
+ assertIntEquals(NotEqualTrueLhs(true), 3);
+ assertIntEquals(NotEqualFalseRhs(true), 5);
+ assertIntEquals(NotEqualFalseLhs(true), 5);
+ assertBooleanEquals(NotNotBool(true), true);
+ assertBooleanEquals(NotNotBool(false), false);
}
}
diff --git a/test/463-checker-boolean-simplifier/src/Main.java b/test/463-checker-boolean-simplifier/src/Main.java
index efe0d3f..3daf693 100644
--- a/test/463-checker-boolean-simplifier/src/Main.java
+++ b/test/463-checker-boolean-simplifier/src/Main.java
@@ -27,16 +27,15 @@
}
/*
- * Elementary test negating a boolean. Verifies that the condition is replaced,
- * blocks merged and empty branches removed.
+ * Elementary test negating a boolean. Verifies that blocks are merged and
+ * empty branches removed.
*/
// CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (before)
// CHECK-DAG: [[Param:z\d+]] ParameterValue
// CHECK-DAG: [[Const0:i\d+]] IntConstant 0
// CHECK-DAG: [[Const1:i\d+]] IntConstant 1
- // CHECK-DAG: [[NotEq:z\d+]] NotEqual [ [[Param]] [[Const0]] ]
- // CHECK-DAG: If [ [[NotEq]] ]
+ // CHECK-DAG: If [ [[Param]] ]
// CHECK-DAG: [[Phi:i\d+]] Phi [ [[Const1]] [[Const0]] ]
// CHECK-DAG: Return [ [[Phi]] ]
@@ -49,11 +48,10 @@
// CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (after)
// CHECK-DAG: [[Param:z\d+]] ParameterValue
// CHECK-DAG: [[Const0:i\d+]] IntConstant 0
- // CHECK-DAG: [[Eq:z\d+]] Equal [ [[Param]] [[Const0]] ]
- // CHECK-DAG: Return [ [[Eq]] ]
+ // CHECK-DAG: [[NotParam:z\d+]] BooleanNot [ [[Param]] ]
+ // CHECK-DAG: Return [ [[NotParam]] ]
// CHECK-START: boolean Main.BooleanNot(boolean) boolean_simplifier (after)
- // CHECK-NOT: NotEqual
// CHECK-NOT: If
// CHECK-NOT: Phi
@@ -115,6 +113,9 @@
// CHECK-DAG: [[Cond:z\d+]] LessThan [ [[ParamX]] [[ParamY]] ]
// CHECK-DAG: Return [ [[Cond]] ]
+ // CHECK-START: boolean Main.LessThan(int, int) boolean_simplifier (after)
+ // CHECK-NOT: GreaterThanOrEqual
+
public static boolean LessThan(int x, int y) {
return (x < y) ? true : false;
}