Merge "Optimizing: double-negated bitwise operations simplifications"

1 files changed, 87 insertions, 0 deletions

diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 49fc8c71b3..3f66c66ce0 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -46,6 +46,10 @@ class InstructionSimplifierVisitor : public HGraphDelegateVisitor {
   bool TryReplaceWithRotateRegisterSubPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl);
 
   bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop);
+  // `op` should be either HOr or HAnd.
+  // De Morgan's laws:
+  // ~a & ~b = ~(a | b)  and  ~a | ~b = ~(a & b)
+  bool TryApplyDeMorgan(HBinaryOperation* op);
   void VisitShift(HBinaryOperation* shift);
 
   void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
@@ -162,6 +166,64 @@ bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation
   return true;
 }
 
+bool InstructionSimplifierVisitor::TryApplyDeMorgan(HBinaryOperation* op) {
+  DCHECK(op->IsAnd() || op->IsOr());
+  Primitive::Type type = op->GetType();
+  HInstruction* left = op->GetLeft();
+  HInstruction* right = op->GetRight();
+
+  // We can apply De Morgan's laws if both inputs are Not's and are only used
+  // by `op`.
+  if (left->IsNot() &&
+      right->IsNot() &&
+      left->HasOnlyOneNonEnvironmentUse() &&
+      right->HasOnlyOneNonEnvironmentUse()) {
+    // Replace code looking like
+    //    NOT nota, a
+    //    NOT notb, b
+    //    AND dst, nota, notb (respectively OR)
+    // with
+    //    OR or, a, b         (respectively AND)
+    //    NOT dest, or
+    HInstruction* src_left = left->AsNot()->GetInput();
+    HInstruction* src_right = right->AsNot()->GetInput();
+    uint32_t dex_pc = op->GetDexPc();
+
+    HBinaryOperation* hbin;
+    if (op->IsAnd()) {
+      hbin = new (GetGraph()->GetArena()) HOr(type, src_left, src_right, dex_pc);
+    } else {
+      hbin = new (GetGraph()->GetArena()) HAnd(type, src_left, src_right, dex_pc);
+    }
+    // Step 1: replace left Not by new binary operation (this is arbitrary,
+    // the right one could have been used instead).
+    //  SL    SR       SL  SR
+    //  |     |        |  / |
+    // Not   Not    NewBin  Not
+    //  \    /   ->    \    /
+    //  OldBin         OldBin
+    //    |              |
+    left->GetBlock()->ReplaceAndRemoveInstructionWith(left, hbin);
+
+    HNot* hnot = new (GetGraph()->GetArena()) HNot(type, hbin, dex_pc);
+    // Step 2: replace old binary operation by a new Not, and remove
+    // the now disconnected right Not.
+    //    SL  SR         SL  SR
+    //    |  / |         |  / |
+    // NewBin  Not    NewBin  Not [removed]
+    //    \    /   ->    \    x
+    //    OldBin          Not
+    //      |              |
+    op->GetBlock()->ReplaceAndRemoveInstructionWith(op, hnot);
+    right->GetBlock()->RemoveInstruction(right);
+
+    RecordSimplification();
+    return true;
+  }
+
+  return false;
+}
+
 void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) {
   DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
   HConstant* input_cst = instruction->GetConstantRight();
@@ -739,7 +801,10 @@ void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) {
     //    src
     instruction->ReplaceWith(instruction->GetLeft());
     instruction->GetBlock()->RemoveInstruction(instruction);
+    return;
   }
+
+  TryApplyDeMorgan(instruction);
 }
 
 void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) {
@@ -1053,6 +1118,8 @@ void InstructionSimplifierVisitor::VisitOr(HOr* instruction) {
     return;
   }
 
+  if (TryApplyDeMorgan(instruction)) return;
+
   TryReplaceWithRotate(instruction);
 }
 
@@ -1175,6 +1242,26 @@ void InstructionSimplifierVisitor::VisitXor(HXor* instruction) {
     return;
   }
 
+  HInstruction* left = instruction->GetLeft();
+  HInstruction* right = instruction->GetRight();
+  if (left->IsNot() &&
+      right->IsNot() &&
+      left->HasOnlyOneNonEnvironmentUse() &&
+      right->HasOnlyOneNonEnvironmentUse()) {
+    // Replace code looking like
+    //    NOT nota, a
+    //    NOT notb, b
+    //    XOR dst, nota, notb
+    // with
+    //    XOR dst, a, b
+    instruction->ReplaceInput(left->AsNot()->GetInput(), 0);
+    instruction->ReplaceInput(right->AsNot()->GetInput(), 1);
+    left->GetBlock()->RemoveInstruction(left);
+    right->GetBlock()->RemoveInstruction(right);
+    RecordSimplification();
+    return;
+  }
+
   TryReplaceWithRotate(instruction);
 }