Convert And+Sub into bic if possible

Convert
 i1: AND a, b
     SUB a, i1
into:
     BIC a, a, b

Also works if `i1` is AND b, a.

Bug: 304972513
Fixes: 304972513
Test: art/test/testrunner/testrunner.py --host --64 --target
Change-Id: I22218c263f52b58d87431186588ac166dc93246a

5 files changed, 121 insertions, 2 deletions

diff --git a/compiler/optimizing/instruction_simplifier_arm.cc b/compiler/optimizing/instruction_simplifier_arm.cc
index be4371f734..aefa27628b 100644
--- a/compiler/optimizing/instruction_simplifier_arm.cc
+++ b/compiler/optimizing/instruction_simplifier_arm.cc
@@ -278,9 +278,15 @@ void InstructionSimplifierArmVisitor::VisitSub(HSub* instruction) {
   if (IsSubRightSubLeftShl(instruction)) {
     HInstruction* shl = instruction->GetRight()->InputAt(0);
     if (shl->InputAt(1)->IsConstant() && TryReplaceSubSubWithSubAdd(instruction)) {
-      TryMergeIntoUsersShifterOperand(shl);
+      if (TryMergeIntoUsersShifterOperand(shl)) {
+        return;
+      }
     }
   }
+
+  if (TryMergeWithAnd(instruction)) {
+    return;
+  }
 }
 
 void InstructionSimplifierArmVisitor::VisitTypeConversion(HTypeConversion* instruction) {
diff --git a/compiler/optimizing/instruction_simplifier_arm64.cc b/compiler/optimizing/instruction_simplifier_arm64.cc
index 2c191dc3f4..d0fbe1382b 100644
--- a/compiler/optimizing/instruction_simplifier_arm64.cc
+++ b/compiler/optimizing/instruction_simplifier_arm64.cc
@@ -249,9 +249,15 @@ void InstructionSimplifierArm64Visitor::VisitSub(HSub* instruction) {
   if (IsSubRightSubLeftShl(instruction)) {
     HInstruction* shl = instruction->GetRight()->InputAt(0);
     if (shl->InputAt(1)->IsConstant() && TryReplaceSubSubWithSubAdd(instruction)) {
-      TryMergeIntoUsersShifterOperand(shl);
+      if (TryMergeIntoUsersShifterOperand(shl)) {
+        return;
+      }
     }
   }
+
+  if (TryMergeWithAnd(instruction)) {
+    return;
+  }
 }
 
 void InstructionSimplifierArm64Visitor::VisitTypeConversion(HTypeConversion* instruction) {
diff --git a/compiler/optimizing/instruction_simplifier_shared.cc b/compiler/optimizing/instruction_simplifier_shared.cc
index 50ea2b929b..deb8f93492 100644
--- a/compiler/optimizing/instruction_simplifier_shared.cc
+++ b/compiler/optimizing/instruction_simplifier_shared.cc
@@ -18,6 +18,7 @@
 
 #include "code_generator.h"
 #include "mirror/array-inl.h"
+#include "nodes.h"
 
 namespace art HIDDEN {
 
@@ -229,6 +230,35 @@ bool TryMergeNegatedInput(HBinaryOperation* op) {
   return false;
 }
 
+bool TryMergeWithAnd(HSub* instruction) {
+  HAnd* and_instr = instruction->GetRight()->AsAndOrNull();
+  if (and_instr == nullptr) {
+    return false;
+  }
+
+  HInstruction* value = instruction->GetLeft();
+
+  HInstruction* left = and_instr->GetLeft();
+  const bool left_is_equal = left == value;
+  HInstruction* right = and_instr->GetRight();
+  const bool right_is_equal = right == value;
+  if (!left_is_equal && !right_is_equal) {
+    return false;
+  }
+
+  HBitwiseNegatedRight* bnr = new (instruction->GetBlock()->GetGraph()->GetAllocator())
+      HBitwiseNegatedRight(instruction->GetType(),
+                           HInstruction::InstructionKind::kAnd,
+                           value,
+                           left_is_equal ? right : left,
+                           instruction->GetDexPc());
+  instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bnr);
+  // Since we don't run DCE after this phase, try to manually remove the And instruction.
+  if (!and_instr->HasUses()) {
+    and_instr->GetBlock()->RemoveInstruction(and_instr);
+  }
+  return true;
+}
 
 bool TryExtractArrayAccessAddress(CodeGenerator* codegen,
                                   HInstruction* access,
diff --git a/compiler/optimizing/instruction_simplifier_shared.h b/compiler/optimizing/instruction_simplifier_shared.h
index 68148cff7e..ca6d5286c5 100644
--- a/compiler/optimizing/instruction_simplifier_shared.h
+++ b/compiler/optimizing/instruction_simplifier_shared.h
@@ -66,6 +66,15 @@ bool TryCombineMultiplyAccumulate(HMul* mul, InstructionSet isa);
 // a negated bitwise instruction.
 bool TryMergeNegatedInput(HBinaryOperation* op);
 
+// Convert
+// i1: AND a, b
+//     SUB a, i1
+// into:
+//     BIC a, a, b
+//
+// It also works if `i1` is AND b, a
+bool TryMergeWithAnd(HSub* instruction);
+
 bool TryExtractArrayAccessAddress(CodeGenerator* codegen,
                                   HInstruction* access,
                                   HInstruction* array,
diff --git a/test/564-checker-negbitwise/src/Main.java b/test/564-checker-negbitwise/src/Main.java
index 4f8242bd9e..0387af48e4 100644
--- a/test/564-checker-negbitwise/src/Main.java
+++ b/test/564-checker-negbitwise/src/Main.java
@@ -280,6 +280,72 @@ public class Main {
     return ~a | ~b;
   }
 
+  /**
+   * Check that we transform a And+Sub into a bic
+   */
+
+  /// CHECK-START-ARM: int Main.$noinline$AndSubIntoBic(int, int) instruction_simplifier_arm (before)
+  /// CHECK: <<HAnd:i\d+>> And [<<Left:i\d+>>,<<Right:i\d+>>]
+  /// CHECK:               Sub [<<Left>>,<<HAnd>>]
+
+  /// CHECK-START-ARM: int Main.$noinline$AndSubIntoBic(int, int) instruction_simplifier_arm (after)
+  /// CHECK-NOT: And
+
+  /// CHECK-START-ARM: int Main.$noinline$AndSubIntoBic(int, int) instruction_simplifier_arm (after)
+  /// CHECK-NOT: Sub
+
+  /// CHECK-START-ARM: int Main.$noinline$AndSubIntoBic(int, int) instruction_simplifier_arm (after)
+  /// CHECK:     BitwiseNegatedRight kind:And
+
+  /// CHECK-START-ARM64: int Main.$noinline$AndSubIntoBic(int, int) instruction_simplifier_arm64 (before)
+  /// CHECK: <<HAnd:i\d+>> And [<<Left:i\d+>>,<<Right:i\d+>>]
+  /// CHECK:               Sub [<<Left>>,<<HAnd>>]
+
+  /// CHECK-START-ARM64: int Main.$noinline$AndSubIntoBic(int, int) instruction_simplifier_arm64 (after)
+  /// CHECK-NOT: And
+
+  /// CHECK-START-ARM64: int Main.$noinline$AndSubIntoBic(int, int) instruction_simplifier_arm64 (after)
+  /// CHECK-NOT: Sub
+
+  /// CHECK-START-ARM64: int Main.$noinline$AndSubIntoBic(int, int) instruction_simplifier_arm64 (after)
+  /// CHECK:     BitwiseNegatedRight kind:And
+  public static int $noinline$AndSubIntoBic(int a, int b) {
+      return a - (a & b);
+  }
+
+  /**
+   * Check that we transform a And+Sub into a bic. Alternative version where the and is inverted.
+   */
+
+  /// CHECK-START-ARM: int Main.$noinline$AndSubIntoBic_v2(int, int) instruction_simplifier_arm (before)
+  /// CHECK: <<HAnd:i\d+>> And [<<Left:i\d+>>,<<Right:i\d+>>]
+  /// CHECK:               Sub [<<Right>>,<<HAnd>>]
+
+  /// CHECK-START-ARM: int Main.$noinline$AndSubIntoBic_v2(int, int) instruction_simplifier_arm (after)
+  /// CHECK-NOT: And
+
+  /// CHECK-START-ARM: int Main.$noinline$AndSubIntoBic_v2(int, int) instruction_simplifier_arm (after)
+  /// CHECK-NOT: Sub
+
+  /// CHECK-START-ARM: int Main.$noinline$AndSubIntoBic_v2(int, int) instruction_simplifier_arm (after)
+  /// CHECK:     BitwiseNegatedRight kind:And
+
+  /// CHECK-START-ARM64: int Main.$noinline$AndSubIntoBic_v2(int, int) instruction_simplifier_arm64 (before)
+  /// CHECK: <<HAnd:i\d+>> And [<<Left:i\d+>>,<<Right:i\d+>>]
+  /// CHECK:               Sub [<<Right>>,<<HAnd>>]
+
+  /// CHECK-START-ARM64: int Main.$noinline$AndSubIntoBic_v2(int, int) instruction_simplifier_arm64 (after)
+  /// CHECK-NOT: And
+
+  /// CHECK-START-ARM64: int Main.$noinline$AndSubIntoBic_v2(int, int) instruction_simplifier_arm64 (after)
+  /// CHECK-NOT: Sub
+
+  /// CHECK-START-ARM64: int Main.$noinline$AndSubIntoBic_v2(int, int) instruction_simplifier_arm64 (after)
+  /// CHECK:     BitwiseNegatedRight kind:And
+  public static int $noinline$AndSubIntoBic_v2(int a, int b) {
+      return b - (a & b);
+  }
+
   public static void main(String[] args) {
     assertIntEquals(0xe,   $opt$noinline$notAnd(0xf, 0x1));
     assertLongEquals(~0x0, $opt$noinline$notOr(0xf, 0x1));
@@ -287,5 +353,7 @@ public class Main {
     assertIntEquals(0xe,  $opt$noinline$notAndConstant(0x1));
     assertIntEquals(0xe,   $opt$noinline$notAndMultipleUses(0xf, 0x1));
     assertIntEquals(~0x1,  $opt$noinline$deMorganOr(0x3, 0x1));
+    assertIntEquals(0x2, $noinline$AndSubIntoBic(0x3, 0x1));
+    assertIntEquals(0x2, $noinline$AndSubIntoBic_v2(0x1, 0x3));
   }
 }