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

2 files changed, 284 insertions, 4 deletions

diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index e13c8eafaf..4a1813266e 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -2242,6 +2242,7 @@ void InstructionSimplifierVisitor::VisitSub(HSub* instruction) {
   }
 
   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 @@ void InstructionSimplifierVisitor::VisitSub(HSub* instruction) {
     // 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 (add->GetLeft() == right) {
+      instruction->ReplaceWith(add->GetRight());
       RecordSimplification();
       instruction->GetBlock()->RemoveInstruction(instruction);
       return;
-    } else if (left->InputAt(0) == right) {
-      instruction->ReplaceWith(left->InputAt(1));
+    }
+  } 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 8ab059dcbe..46ac7f04ba 100644
--- a/test/458-checker-instruct-simplification/src/Main.java
+++ b/test/458-checker-instruct-simplification/src/Main.java
@@ -2155,6 +2155,194 @@ public class Main {
     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 @@ public class Main {
     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));