Opt compiler: enhance gvn for commutative ops.

Change-Id: I415b50d58b30cab4ec38077be22373eb9598ec40

4 files changed, 53 insertions, 10 deletions

diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index cda5c1a99c..07cc41a8d5 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -988,7 +988,7 @@ void InstructionCodeGeneratorARM::VisitCondition(HCondition* comp) {
     __ cmp(left, ShifterOperand(locations->InAt(1).AsRegister<Register>()));
   } else {
     DCHECK(locations->InAt(1).IsConstant());
-    int32_t value = locations->InAt(1).GetConstant()->AsIntConstant()->GetValue();
+    int32_t value = CodeGenerator::GetInt32ValueOf(locations->InAt(1).GetConstant());
     ShifterOperand operand;
     if (GetAssembler()->ShifterOperandCanHold(R0, left, CMP, value, &operand)) {
       __ cmp(left, operand);
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index adc022a2ce..6365bca319 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -894,7 +894,7 @@ void InstructionCodeGeneratorX86_64::VisitCondition(HCondition* comp) {
     if (rhs.IsRegister()) {
       __ cmpl(lhs.AsRegister<CpuRegister>(), rhs.AsRegister<CpuRegister>());
     } else if (rhs.IsConstant()) {
-      int32_t constant = rhs.GetConstant()->AsIntConstant()->GetValue();
+      int32_t constant = CodeGenerator::GetInt32ValueOf(rhs.GetConstant());
       if (constant == 0) {
         __ testl(lhs.AsRegister<CpuRegister>(), lhs.AsRegister<CpuRegister>());
       } else {
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index cb448c883f..ea65dc0780 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -299,8 +299,17 @@ void GlobalValueNumberer::VisitBasicBlock(HBasicBlock* block) {
     // Save the next instruction in case `current` is removed from the graph.
     HInstruction* next = current->GetNext();
     if (current->CanBeMoved()) {
+      if (current->IsBinaryOperation() && current->AsBinaryOperation()->IsCommutative()) {
+        // For commutative ops, (x op y) will be treated the same as (y op x)
+        // after fixed ordering.
+        current->AsBinaryOperation()->OrderInputs();
+      }
       HInstruction* existing = set->Lookup(current);
       if (existing != nullptr) {
+        // This replacement doesn't make more OrderInputs() necessary since
+        // current is either used by an instruction that it dominates,
+        // which hasn't been visited yet due to the order we visit instructions.
+        // Or current is used by a phi, and we don't do OrderInputs() on a phi anyway.
         current->ReplaceWith(existing);
         current->GetBlock()->RemoveInstruction(current);
       } else {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 7e075644ef..98076a05f2 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1500,7 +1500,39 @@ class HBinaryOperation : public HExpression<2> {
   HInstruction* GetRight() const { return InputAt(1); }
   Primitive::Type GetResultType() const { return GetType(); }
 
-  virtual bool IsCommutative() { return false; }
+  virtual bool IsCommutative() const { return false; }
+
+  // Put constant on the right.
+  // Returns whether order is changed.
+  bool OrderInputsWithConstantOnTheRight() {
+    HInstruction* left = InputAt(0);
+    HInstruction* right = InputAt(1);
+    if (left->IsConstant() && !right->IsConstant()) {
+      ReplaceInput(right, 0);
+      ReplaceInput(left, 1);
+      return true;
+    }
+    return false;
+  }
+
+  // Order inputs by instruction id, but favor constant on the right side.
+  // This helps GVN for commutative ops.
+  void OrderInputs() {
+    DCHECK(IsCommutative());
+    HInstruction* left = InputAt(0);
+    HInstruction* right = InputAt(1);
+    if (left == right || (!left->IsConstant() && right->IsConstant())) {
+      return;
+    }
+    if (OrderInputsWithConstantOnTheRight()) {
+      return;
+    }
+    // Order according to instruction id.
+    if (left->GetId() > right->GetId()) {
+      ReplaceInput(right, 0);
+      ReplaceInput(left, 1);
+    }
+  }
 
   virtual bool CanBeMoved() const { return true; }
   virtual bool InstructionDataEquals(HInstruction* other) const {
@@ -1529,8 +1561,6 @@ class HCondition : public HBinaryOperation {
       : HBinaryOperation(Primitive::kPrimBoolean, first, second),
         needs_materialization_(true) {}
 
-  virtual bool IsCommutative() { return true; }
-
   bool NeedsMaterialization() const { return needs_materialization_; }
   void ClearNeedsMaterialization() { needs_materialization_ = false; }
 
@@ -1556,6 +1586,8 @@ class HEqual : public HCondition {
   HEqual(HInstruction* first, HInstruction* second)
       : HCondition(first, second) {}
 
+  bool IsCommutative() const OVERRIDE { return true; }
+
   virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
     return x == y ? 1 : 0;
   }
@@ -1578,6 +1610,8 @@ class HNotEqual : public HCondition {
   HNotEqual(HInstruction* first, HInstruction* second)
       : HCondition(first, second) {}
 
+  bool IsCommutative() const OVERRIDE { return true; }
+
   virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
     return x != y ? 1 : 0;
   }
@@ -2136,7 +2170,7 @@ class HAdd : public HBinaryOperation {
   HAdd(Primitive::Type result_type, HInstruction* left, HInstruction* right)
       : HBinaryOperation(result_type, left, right) {}
 
-  virtual bool IsCommutative() { return true; }
+  virtual bool IsCommutative() const OVERRIDE { return true; }
 
   virtual int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE {
     return x + y;
@@ -2174,7 +2208,7 @@ class HMul : public HBinaryOperation {
   HMul(Primitive::Type result_type, HInstruction* left, HInstruction* right)
       : HBinaryOperation(result_type, left, right) {}
 
-  virtual bool IsCommutative() { return true; }
+  virtual bool IsCommutative() const OVERRIDE { return true; }
 
   virtual int32_t Evaluate(int32_t x, int32_t y) const { return x * y; }
   virtual int64_t Evaluate(int64_t x, int64_t y) const { return x * y; }
@@ -2323,7 +2357,7 @@ class HAnd : public HBinaryOperation {
   HAnd(Primitive::Type result_type, HInstruction* left, HInstruction* right)
       : HBinaryOperation(result_type, left, right) {}
 
-  bool IsCommutative() OVERRIDE { return true; }
+  bool IsCommutative() const OVERRIDE { return true; }
 
   int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x & y; }
   int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x & y; }
@@ -2339,7 +2373,7 @@ class HOr : public HBinaryOperation {
   HOr(Primitive::Type result_type, HInstruction* left, HInstruction* right)
       : HBinaryOperation(result_type, left, right) {}
 
-  bool IsCommutative() OVERRIDE { return true; }
+  bool IsCommutative() const OVERRIDE { return true; }
 
   int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x | y; }
   int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x | y; }
@@ -2355,7 +2389,7 @@ class HXor : public HBinaryOperation {
   HXor(Primitive::Type result_type, HInstruction* left, HInstruction* right)
       : HBinaryOperation(result_type, left, right) {}
 
-  bool IsCommutative() OVERRIDE { return true; }
+  bool IsCommutative() const OVERRIDE { return true; }
 
   int32_t Evaluate(int32_t x, int32_t y) const OVERRIDE { return x ^ y; }
   int64_t Evaluate(int64_t x, int64_t y) const OVERRIDE { return x ^ y; }