Opt compiler: Basic simplification for arithmetic operations.

The optimisations in this patch do not look further than the
inputs of each operation.

Change-Id: Iddd0ab6b360b9e7bb042db22086d51a31be85530

1 files changed, 180 insertions, 0 deletions

diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc
index fca9933872..ec0cc3e98b 100644
--- a/compiler/optimizing/constant_folding.cc
+++ b/compiler/optimizing/constant_folding.cc
@@ -18,7 +18,28 @@
 
 namespace art {
 
+// This visitor tries to simplify operations that yield a constant. For example
+// `input * 0` is replaced by a null constant.
+class InstructionWithAbsorbingInputSimplifier : public HGraphVisitor {
+ public:
+  explicit InstructionWithAbsorbingInputSimplifier(HGraph* graph) : HGraphVisitor(graph) {}
+
+ private:
+  void VisitShift(HBinaryOperation* shift);
+
+  void VisitAnd(HAnd* instruction) OVERRIDE;
+  void VisitMul(HMul* instruction) OVERRIDE;
+  void VisitOr(HOr* instruction) OVERRIDE;
+  void VisitRem(HRem* instruction) OVERRIDE;
+  void VisitShl(HShl* instruction) OVERRIDE;
+  void VisitShr(HShr* instruction) OVERRIDE;
+  void VisitSub(HSub* instruction) OVERRIDE;
+  void VisitUShr(HUShr* instruction) OVERRIDE;
+  void VisitXor(HXor* instruction) OVERRIDE;
+};
+
 void HConstantFolding::Run() {
+  InstructionWithAbsorbingInputSimplifier simplifier(graph_);
   // Process basic blocks in reverse post-order in the dominator tree,
   // so that an instruction turned into a constant, used as input of
   // another instruction, may possibly be used to turn that second
@@ -38,6 +59,8 @@ void HConstantFolding::Run() {
             inst->AsBinaryOperation()->TryStaticEvaluation();
         if (constant != nullptr) {
           inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant);
+        } else {
+          inst->Accept(&simplifier);
         }
       } else if (inst->IsUnaryOperation()) {
         // Constant folding: replace `op(a)' with a constant at compile
@@ -47,9 +70,166 @@ void HConstantFolding::Run() {
         if (constant != nullptr) {
           inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant);
         }
+      } else if (inst->IsDivZeroCheck()) {
+        // We can safely remove the check if the input is a non-null constant.
+        HDivZeroCheck* check = inst->AsDivZeroCheck();
+        HInstruction* check_input = check->InputAt(0);
+        if (check_input->IsConstant() && !check_input->AsConstant()->IsZero()) {
+          check->ReplaceWith(check_input);
+          check->GetBlock()->RemoveInstruction(check);
+        }
       }
     }
   }
 }
 
+void InstructionWithAbsorbingInputSimplifier::VisitShift(HBinaryOperation* instruction) {
+  DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
+  HInstruction* left = instruction->GetLeft();
+  if (left->IsConstant() && left->AsConstant()->IsZero()) {
+    // Replace code looking like
+    //    SHL dst, 0, shift_amount
+    // with
+    //    CONSTANT 0
+    instruction->ReplaceWith(left);
+    instruction->GetBlock()->RemoveInstruction(instruction);
+  }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitAnd(HAnd* instruction) {
+  HConstant* input_cst = instruction->GetConstantRight();
+  if ((input_cst != nullptr) && input_cst->IsZero()) {
+    // Replace code looking like
+    //    AND dst, src, 0
+    // with
+    //    CONSTANT 0
+    instruction->ReplaceWith(input_cst);
+    instruction->GetBlock()->RemoveInstruction(instruction);
+  }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitMul(HMul* instruction) {
+  HConstant* input_cst = instruction->GetConstantRight();
+  Primitive::Type type = instruction->GetType();
+  if (Primitive::IsIntOrLongType(type) &&
+      (input_cst != nullptr) && input_cst->IsZero()) {
+    // Replace code looking like
+    //    MUL dst, src, 0
+    // with
+    //    CONSTANT 0
+    // Integral multiplication by zero always yields zero, but floating-point
+    // multiplication by zero does not always do. For example `Infinity * 0.0`
+    // should yield a NaN.
+    instruction->ReplaceWith(input_cst);
+    instruction->GetBlock()->RemoveInstruction(instruction);
+  }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitOr(HOr* instruction) {
+  HConstant* input_cst = instruction->GetConstantRight();
+
+  if (input_cst == nullptr) {
+    return;
+  }
+
+  if (Int64FromConstant(input_cst) == -1) {
+    // Replace code looking like
+    //    OR dst, src, 0xFFF...FF
+    // with
+    //    CONSTANT 0xFFF...FF
+    instruction->ReplaceWith(input_cst);
+    instruction->GetBlock()->RemoveInstruction(instruction);
+  }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitRem(HRem* instruction) {
+  Primitive::Type type = instruction->GetType();
+
+  if (!Primitive::IsIntegralType(type)) {
+    return;
+  }
+
+  HBasicBlock* block = instruction->GetBlock();
+
+  if (instruction->GetLeft()->IsConstant() &&
+      instruction->GetLeft()->AsConstant()->IsZero()) {
+    // Replace code looking like
+    //    REM dst, 0, src
+    // with
+    //    CONSTANT 0
+    instruction->ReplaceWith(instruction->GetLeft());
+    block->RemoveInstruction(instruction);
+  }
+
+  HConstant* cst_right = instruction->GetRight()->AsConstant();
+  if (((cst_right != nullptr) &&
+       (cst_right->IsOne() || cst_right->IsMinusOne())) ||
+      (instruction->GetLeft() == instruction->GetRight())) {
+    // Replace code looking like
+    //    REM dst, src, 1
+    // or
+    //    REM dst, src, -1
+    // or
+    //    REM dst, src, src
+    // with
+    //    CONSTANT 0
+    ArenaAllocator* allocator = GetGraph()->GetArena();
+    block->ReplaceAndRemoveInstructionWith(instruction,
+                                           HConstant::NewConstant(allocator, type, 0));
+  }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitShl(HShl* instruction) {
+  VisitShift(instruction);
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitShr(HShr* instruction) {
+  VisitShift(instruction);
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitSub(HSub* instruction) {
+  Primitive::Type type = instruction->GetType();
+
+  if (!Primitive::IsIntegralType(type)) {
+    return;
+  }
+
+  HBasicBlock* block = instruction->GetBlock();
+  ArenaAllocator* allocator = GetGraph()->GetArena();
+
+  // We assume that GVN has run before, so we only perform a pointer
+  // comparison.  If for some reason the values are equal but the pointers are
+  // different, we are still correct and only miss an optimisation
+  // opportunity.
+  if (instruction->GetLeft() == instruction->GetRight()) {
+    // Replace code looking like
+    //    SUB dst, src, src
+    // with
+    //    CONSTANT 0
+    // Note that we cannot optimise `x - x` to `0` for floating-point. It does
+    // not work when `x` is an infinity.
+    block->ReplaceAndRemoveInstructionWith(instruction,
+                                           HConstant::NewConstant(allocator, type, 0));
+  }
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitUShr(HUShr* instruction) {
+  VisitShift(instruction);
+}
+
+void InstructionWithAbsorbingInputSimplifier::VisitXor(HXor* instruction) {
+  if (instruction->GetLeft() == instruction->GetRight()) {
+    // Replace code looking like
+    //    XOR dst, src, src
+    // with
+    //    CONSTANT 0
+    Primitive::Type type = instruction->GetType();
+    HBasicBlock* block = instruction->GetBlock();
+    ArenaAllocator* allocator = GetGraph()->GetArena();
+
+    block->ReplaceAndRemoveInstructionWith(instruction,
+                                           HConstant::NewConstant(allocator, type, 0));
+  }
+}
+
 }  // namespace art