Optimize Sub/Sub and Sub/Add operations
Handles cases like:
* y - (x + y) = -x
* x - (x + y) = -y.
* (x - y) - x = -y.
* x - (x - y) = y.
Bug: 301612598
Fixes: 301612598
Test: art/test/testrunner/testrunner.py --host --64 -b --optimizing
Change-Id: I2f506b4a4903774baf39e8d2c681db6a59efeb2c
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index e13c8ea..4a18132 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -2242,6 +2242,7 @@
}
if (left->IsAdd()) {
+ // Cases (x + y) - y = x, and (x + y) - x = y.
// Replace code patterns looking like
// ADD dst1, x, y ADD dst1, x, y
// SUB dst2, dst1, y SUB dst2, dst1, x
@@ -2250,14 +2251,75 @@
// SUB instruction is not needed in this case, we may use
// one of inputs of ADD instead.
// It is applicable to integral types only.
+ HAdd* add = left->AsAdd();
DCHECK(DataType::IsIntegralType(type));
- if (left->InputAt(1) == right) {
- instruction->ReplaceWith(left->InputAt(0));
+ if (add->GetRight() == right) {
+ instruction->ReplaceWith(add->GetLeft());
RecordSimplification();
instruction->GetBlock()->RemoveInstruction(instruction);
return;
- } else if (left->InputAt(0) == right) {
- instruction->ReplaceWith(left->InputAt(1));
+ } else if (add->GetLeft() == right) {
+ instruction->ReplaceWith(add->GetRight());
+ RecordSimplification();
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ return;
+ }
+ } else if (right->IsAdd()) {
+ // Cases y - (x + y) = -x, and x - (x + y) = -y.
+ // Replace code patterns looking like
+ // ADD dst1, x, y ADD dst1, x, y
+ // SUB dst2, y, dst1 SUB dst2, x, dst1
+ // with
+ // ADD dst1, x, y ADD dst1, x, y
+ // NEG x NEG y
+ // SUB instruction is not needed in this case, we may use
+ // one of inputs of ADD instead with a NEG.
+ // It is applicable to integral types only.
+ HAdd* add = right->AsAdd();
+ DCHECK(DataType::IsIntegralType(type));
+ if (add->GetRight() == left) {
+ HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(add->GetType(), add->GetLeft());
+ instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, neg);
+ RecordSimplification();
+ return;
+ } else if (add->GetLeft() == left) {
+ HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(add->GetType(), add->GetRight());
+ instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, neg);
+ RecordSimplification();
+ return;
+ }
+ } else if (left->IsSub()) {
+ // Case (x - y) - x = -y.
+ // Replace code patterns looking like
+ // SUB dst1, x, y
+ // SUB dst2, dst1, x
+ // with
+ // SUB dst1, x, y
+ // NEG y
+ // The second SUB is not needed in this case, we may use the second input of the first SUB
+ // instead with a NEG.
+ // It is applicable to integral types only.
+ HSub* sub = left->AsSub();
+ DCHECK(DataType::IsIntegralType(type));
+ if (sub->GetLeft() == right) {
+ HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(sub->GetType(), sub->GetRight());
+ instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, neg);
+ RecordSimplification();
+ return;
+ }
+ } else if (right->IsSub()) {
+ // Case x - (x - y) = y.
+ // Replace code patterns looking like
+ // SUB dst1, x, y
+ // SUB dst2, x, dst1
+ // with
+ // SUB dst1, x, y
+ // The second SUB is not needed in this case, we may use the second input of the first SUB.
+ // It is applicable to integral types only.
+ HSub* sub = right->AsSub();
+ DCHECK(DataType::IsIntegralType(type));
+ if (sub->GetLeft() == left) {
+ instruction->ReplaceWith(sub->GetRight());
RecordSimplification();
instruction->GetBlock()->RemoveInstruction(instruction);
return;
diff --git a/test/458-checker-instruct-simplification/src/Main.java b/test/458-checker-instruct-simplification/src/Main.java
index 8ab059d..46ac7f0 100644
--- a/test/458-checker-instruct-simplification/src/Main.java
+++ b/test/458-checker-instruct-simplification/src/Main.java
@@ -2155,6 +2155,194 @@
return y + sub;
}
+ // Sub/Add and Sub/Sub simplifications
+
+ /// CHECK-START: int Main.$noinline$testSubAddInt(int, int) instruction_simplifier (before)
+ /// CHECK: <<x:i\d+>> ParameterValue
+ /// CHECK: <<y:i\d+>> ParameterValue
+ /// CHECK: <<add:i\d+>> Add [<<x>>,<<y>>]
+ /// CHECK: <<sub:i\d+>> Sub [<<y>>,<<add>>]
+ /// CHECK: Return [<<sub>>]
+
+ /// CHECK-START: int Main.$noinline$testSubAddInt(int, int) instruction_simplifier (after)
+ /// CHECK: <<x:i\d+>> ParameterValue
+ /// CHECK: <<y:i\d+>> ParameterValue
+ /// CHECK: <<add:i\d+>> Add [<<x>>,<<y>>]
+ /// CHECK: <<neg:i\d+>> Neg [<<x>>]
+ /// CHECK: Return [<<neg>>]
+
+ /// CHECK-START: int Main.$noinline$testSubAddInt(int, int) instruction_simplifier (after)
+ /// CHECK-NOT: Sub
+
+ /// CHECK-START: int Main.$noinline$testSubAddInt(int, int) dead_code_elimination$initial (after)
+ /// CHECK-NOT: Add
+ static int $noinline$testSubAddInt(int x, int y) {
+ return y - (x + y);
+ }
+
+ /// CHECK-START: int Main.$noinline$testSubAddOtherVersionInt(int, int) instruction_simplifier (before)
+ /// CHECK: <<x:i\d+>> ParameterValue
+ /// CHECK: <<y:i\d+>> ParameterValue
+ /// CHECK: <<add:i\d+>> Add [<<x>>,<<y>>]
+ /// CHECK: <<sub:i\d+>> Sub [<<x>>,<<add>>]
+ /// CHECK: Return [<<sub>>]
+
+ /// CHECK-START: int Main.$noinline$testSubAddOtherVersionInt(int, int) instruction_simplifier (after)
+ /// CHECK: <<x:i\d+>> ParameterValue
+ /// CHECK: <<y:i\d+>> ParameterValue
+ /// CHECK: <<add:i\d+>> Add [<<x>>,<<y>>]
+ /// CHECK: <<neg:i\d+>> Neg [<<y>>]
+ /// CHECK: Return [<<neg>>]
+
+ /// CHECK-START: int Main.$noinline$testSubAddOtherVersionInt(int, int) instruction_simplifier (after)
+ /// CHECK-NOT: Sub
+
+ /// CHECK-START: int Main.$noinline$testSubAddOtherVersionInt(int, int) dead_code_elimination$initial (after)
+ /// CHECK-NOT: Add
+ static int $noinline$testSubAddOtherVersionInt(int x, int y) {
+ return x - (x + y);
+ }
+
+ /// CHECK-START: int Main.$noinline$testSubSubInt(int, int) instruction_simplifier (before)
+ /// CHECK: <<x:i\d+>> ParameterValue
+ /// CHECK: <<y:i\d+>> ParameterValue
+ /// CHECK: <<sub1:i\d+>> Sub [<<x>>,<<y>>]
+ /// CHECK: <<sub2:i\d+>> Sub [<<sub1>>,<<x>>]
+ /// CHECK: Return [<<sub2>>]
+
+ /// CHECK-START: int Main.$noinline$testSubSubInt(int, int) instruction_simplifier (after)
+ /// CHECK: <<x:i\d+>> ParameterValue
+ /// CHECK: <<y:i\d+>> ParameterValue
+ /// CHECK: <<sub1:i\d+>> Sub [<<x>>,<<y>>]
+ /// CHECK: <<neg:i\d+>> Neg [<<y>>]
+ /// CHECK: Return [<<neg>>]
+
+ /// CHECK-START: int Main.$noinline$testSubSubInt(int, int) instruction_simplifier (after)
+ /// CHECK: Sub
+ /// CHECK-NOT: Sub
+
+ /// CHECK-START: int Main.$noinline$testSubSubInt(int, int) dead_code_elimination$initial (after)
+ /// CHECK-NOT: Sub
+ static int $noinline$testSubSubInt(int x, int y) {
+ return (x - y) - x;
+ }
+
+ /// CHECK-START: int Main.$noinline$testSubSubOtherVersionInt(int, int) instruction_simplifier (before)
+ /// CHECK: <<x:i\d+>> ParameterValue
+ /// CHECK: <<y:i\d+>> ParameterValue
+ /// CHECK: <<sub1:i\d+>> Sub [<<x>>,<<y>>]
+ /// CHECK: <<sub2:i\d+>> Sub [<<x>>,<<sub1>>]
+ /// CHECK: Return [<<sub2>>]
+
+ /// CHECK-START: int Main.$noinline$testSubSubOtherVersionInt(int, int) instruction_simplifier (after)
+ /// CHECK: <<x:i\d+>> ParameterValue
+ /// CHECK: <<y:i\d+>> ParameterValue
+ /// CHECK: <<sub1:i\d+>> Sub [<<x>>,<<y>>]
+ /// CHECK: Return [<<y>>]
+
+ /// CHECK-START: int Main.$noinline$testSubSubOtherVersionInt(int, int) instruction_simplifier (after)
+ /// CHECK: Sub
+ /// CHECK-NOT: Sub
+
+ /// CHECK-START: int Main.$noinline$testSubSubOtherVersionInt(int, int) dead_code_elimination$initial (after)
+ /// CHECK-NOT: Sub
+ static int $noinline$testSubSubOtherVersionInt(int x, int y) {
+ return x - (x - y);
+ }
+
+ /// CHECK-START: long Main.$noinline$testSubAddLong(long, long) instruction_simplifier (before)
+ /// CHECK: <<x:j\d+>> ParameterValue
+ /// CHECK: <<y:j\d+>> ParameterValue
+ /// CHECK: <<add:j\d+>> Add [<<x>>,<<y>>]
+ /// CHECK: <<sub:j\d+>> Sub [<<y>>,<<add>>]
+ /// CHECK: Return [<<sub>>]
+
+ /// CHECK-START: long Main.$noinline$testSubAddLong(long, long) instruction_simplifier (after)
+ /// CHECK: <<x:j\d+>> ParameterValue
+ /// CHECK: <<y:j\d+>> ParameterValue
+ /// CHECK: <<add:j\d+>> Add [<<x>>,<<y>>]
+ /// CHECK: <<neg:j\d+>> Neg [<<x>>]
+ /// CHECK: Return [<<neg>>]
+
+ /// CHECK-START: long Main.$noinline$testSubAddLong(long, long) instruction_simplifier (after)
+ /// CHECK-NOT: Sub
+
+ /// CHECK-START: long Main.$noinline$testSubAddLong(long, long) dead_code_elimination$initial (after)
+ /// CHECK-NOT: Add
+ static long $noinline$testSubAddLong(long x, long y) {
+ return y - (x + y);
+ }
+
+ /// CHECK-START: long Main.$noinline$testSubAddOtherVersionLong(long, long) instruction_simplifier (before)
+ /// CHECK: <<x:j\d+>> ParameterValue
+ /// CHECK: <<y:j\d+>> ParameterValue
+ /// CHECK: <<add:j\d+>> Add [<<x>>,<<y>>]
+ /// CHECK: <<sub:j\d+>> Sub [<<x>>,<<add>>]
+ /// CHECK: Return [<<sub>>]
+
+ /// CHECK-START: long Main.$noinline$testSubAddOtherVersionLong(long, long) instruction_simplifier (after)
+ /// CHECK: <<x:j\d+>> ParameterValue
+ /// CHECK: <<y:j\d+>> ParameterValue
+ /// CHECK: <<add:j\d+>> Add [<<x>>,<<y>>]
+ /// CHECK: <<neg:j\d+>> Neg [<<y>>]
+ /// CHECK: Return [<<neg>>]
+
+ /// CHECK-START: long Main.$noinline$testSubAddOtherVersionLong(long, long) instruction_simplifier (after)
+ /// CHECK-NOT: Sub
+
+ /// CHECK-START: long Main.$noinline$testSubAddOtherVersionLong(long, long) dead_code_elimination$initial (after)
+ /// CHECK-NOT: Add
+ static long $noinline$testSubAddOtherVersionLong(long x, long y) {
+ return x - (x + y);
+ }
+
+ /// CHECK-START: long Main.$noinline$testSubSubLong(long, long) instruction_simplifier (before)
+ /// CHECK: <<x:j\d+>> ParameterValue
+ /// CHECK: <<y:j\d+>> ParameterValue
+ /// CHECK: <<sub1:j\d+>> Sub [<<x>>,<<y>>]
+ /// CHECK: <<sub2:j\d+>> Sub [<<sub1>>,<<x>>]
+ /// CHECK: Return [<<sub2>>]
+
+ /// CHECK-START: long Main.$noinline$testSubSubLong(long, long) instruction_simplifier (after)
+ /// CHECK: <<x:j\d+>> ParameterValue
+ /// CHECK: <<y:j\d+>> ParameterValue
+ /// CHECK: <<sub1:j\d+>> Sub [<<x>>,<<y>>]
+ /// CHECK: <<neg:j\d+>> Neg [<<y>>]
+ /// CHECK: Return [<<neg>>]
+
+ /// CHECK-START: long Main.$noinline$testSubSubLong(long, long) instruction_simplifier (after)
+ /// CHECK: Sub
+ /// CHECK-NOT: Sub
+
+ /// CHECK-START: long Main.$noinline$testSubSubLong(long, long) dead_code_elimination$initial (after)
+ /// CHECK-NOT: Sub
+ static long $noinline$testSubSubLong(long x, long y) {
+ return (x - y) - x;
+ }
+
+ /// CHECK-START: long Main.$noinline$testSubSubOtherVersionLong(long, long) instruction_simplifier (before)
+ /// CHECK: <<x:j\d+>> ParameterValue
+ /// CHECK: <<y:j\d+>> ParameterValue
+ /// CHECK: <<sub1:j\d+>> Sub [<<x>>,<<y>>]
+ /// CHECK: <<sub2:j\d+>> Sub [<<x>>,<<sub1>>]
+ /// CHECK: Return [<<sub2>>]
+
+ /// CHECK-START: long Main.$noinline$testSubSubOtherVersionLong(long, long) instruction_simplifier (after)
+ /// CHECK: <<x:j\d+>> ParameterValue
+ /// CHECK: <<y:j\d+>> ParameterValue
+ /// CHECK: <<sub1:j\d+>> Sub [<<x>>,<<y>>]
+ /// CHECK: Return [<<y>>]
+
+ /// CHECK-START: long Main.$noinline$testSubSubOtherVersionLong(long, long) instruction_simplifier (after)
+ /// CHECK: Sub
+ /// CHECK-NOT: Sub
+
+ /// CHECK-START: long Main.$noinline$testSubSubOtherVersionLong(long, long) dead_code_elimination$initial (after)
+ /// CHECK-NOT: Sub
+ static long $noinline$testSubSubOtherVersionLong(long x, long y) {
+ return x - (x - y);
+ }
+
/// CHECK-START: int Main.$noinline$getUint8FromInstanceByteField(Main) instruction_simplifier (before)
/// CHECK-DAG: <<Const255:i\d+>> IntConstant 255
/// CHECK-DAG: <<Get:b\d+>> InstanceFieldGet
@@ -3005,6 +3193,36 @@
assertFloatEquals(floatArg, $noinline$floatSubAddSimplifyLeft(floatArg, 654321.125f));
assertFloatEquals(floatArg, $noinline$floatSubAddSimplifyRight(floatArg, 654321.125f));
+ // Sub/Add and Sub/Sub simplifications
+ int[] int_inputs = {0, 1, -1, Integer.MIN_VALUE, Integer.MAX_VALUE, 42, -9000};
+ for (int x : int_inputs) {
+ for (int y : int_inputs) {
+ // y - (x + y) = -x
+ assertIntEquals(-x, $noinline$testSubAddInt(x, y));
+ // x - (x + y) = -y.
+ assertIntEquals(-y, $noinline$testSubAddOtherVersionInt(x, y));
+ // (x - y) - x = -y.
+ assertIntEquals(-y, $noinline$testSubSubInt(x, y));
+ // x - (x - y) = y.
+ assertIntEquals(y, $noinline$testSubSubOtherVersionInt(x, y));
+ }
+ }
+
+ long[] long_inputs = {0L, 1L, -1L, Long.MIN_VALUE, Long.MAX_VALUE, 0x100000000L, 0x100000001L,
+ -9000L, 0x0123456789ABCDEFL};
+ for (long x : long_inputs) {
+ for (long y : long_inputs) {
+ // y - (x + y) = -x
+ assertLongEquals(-x, $noinline$testSubAddLong(x, y));
+ // x - (x + y) = -y.
+ assertLongEquals(-y, $noinline$testSubAddOtherVersionLong(x, y));
+ // (x - y) - x = -y.
+ assertLongEquals(-y, $noinline$testSubSubLong(x, y));
+ // x - (x - y) = y.
+ assertLongEquals(y, $noinline$testSubSubOtherVersionLong(x, y));
+ }
+ }
+
Main m = new Main();
m.instanceByteField = -1;
assertIntEquals(0xff, $noinline$getUint8FromInstanceByteField(m));