Merge "[optimizing] Replace FP divide by power of 2"

4 files changed, 137 insertions, 8 deletions

diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 2df7c166d8..8f949a5353 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -39,6 +39,7 @@ class InstructionSimplifierVisitor : public HGraphVisitor {
   }
 
   bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop);
+  bool IsExactFPPowerOfTwo(HConstant* constant);
   void VisitShift(HBinaryOperation* shift);
 
   void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
@@ -387,6 +388,72 @@ void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) {
         instruction, (new (GetGraph()->GetArena()) HNeg(type, input_other)));
     RecordSimplification();
   }
+
+  // FP Handle division by powers of 2.
+  if ((input_cst != nullptr) && Primitive::IsFloatingPointType(type) &&
+        IsExactFPPowerOfTwo(input_cst)) {
+    // We can replace this by a multiplication by the reciprocal.
+    // We know that since the value is an exact power of 2, there is no precision lost.
+    HConstant *recip;
+    if (type == Primitive::Primitive::kPrimDouble) {
+      double recip_value = 1.0 / input_cst->AsDoubleConstant()->GetValue();
+      recip = GetGraph()->GetDoubleConstant(recip_value);
+    } else {
+      DCHECK_EQ(type, Primitive::kPrimFloat);
+      float recip_value = 1.0f / input_cst->AsFloatConstant()->GetValue();
+      recip = GetGraph()->GetFloatConstant(recip_value);
+    }
+    instruction->GetBlock()->ReplaceAndRemoveInstructionWith(
+        instruction, (new (GetGraph()->GetArena()) HMul(type, input_other, recip)));
+    RecordSimplification();
+  }
+}
+
+
+bool InstructionSimplifierVisitor::IsExactFPPowerOfTwo(HConstant* constant) {
+  if (constant->IsDoubleConstant()) {
+    // We will examine the value as an unsigned value.
+    uint64_t value = bit_cast<uint64_t, double>(constant->AsDoubleConstant()->GetValue());
+
+    // Make sure the double constant is power of 2.0, so that we can have the
+    // exact result after converting value to 1.0/value.
+    // The uint64_t value is 0 from bit 51 to bit 0.
+    if ((value & INT64_C(0x000FFFFFFFFFFFFF)) != 0) {
+      return false;
+    }
+
+    // For the double constant, we support the range 2.0^-1022 to 2.0^1022
+    // or -(2.0^-1022) to -(2.0^1022)
+    // The uint64_t value is from 0x0010000000000000 to 0x7FD0000000000000 or
+    // from 0x8010000000000000 to 0xFFD0000000000000.
+    if ((value < INT64_C(0x0010000000000000) || value > INT64_C(0x7FD0000000000000)) &&
+        (value < INT64_C(0x8010000000000000) || value > INT64_C(0xFFD0000000000000))) {
+      return false;
+    }
+  } else {
+    DCHECK(constant->IsFloatConstant());
+    // We will examine the value as an unsigned value.
+    uint32_t value = bit_cast<uint32_t, float>(constant->AsFloatConstant()->GetValue());
+
+    // Make sure the float constant is power of 2.0, so that we can have the
+    // exact result after converting value to 1.0/value.
+    // The uint32_t value is 0 from bit 22 to bit 0.
+    if ((value & 0x007FFFFF) != 0) {
+      return false;
+    }
+
+    // For the float constant, we support the range 2.0^-126 to 2.0^126
+    // or -(2.0^-126) to -(2.0^126)
+    // The uint32_t value is from 0x00800000 to 0x7E800000 or
+    // from 0x80800000 to 0xFE800000.
+    if ((value < 0x00800000 || value > 0x7E800000) &&
+        (value < 0x80800000 || value > 0xFE800000)) {
+      return false;
+    }
+  }
+
+  // This is a proper FP power of two.
+  return true;
 }
 
 void InstructionSimplifierVisitor::VisitMul(HMul* instruction) {
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index c158ddf4ee..0bc7fada9d 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -343,6 +343,18 @@ HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value) {
   }
 }
 
+HFloatConstant* HGraph::GetFloatConstant(float value) {
+  HFloatConstant *constant = new (arena_) HFloatConstant(value);
+  InsertConstant(constant);
+  return constant;
+}
+
+HDoubleConstant* HGraph::GetDoubleConstant(double value) {
+  HDoubleConstant *constant = new (arena_) HDoubleConstant(value);
+  InsertConstant(constant);
+  return constant;
+}
+
 void HLoopInformation::Add(HBasicBlock* block) {
   blocks_.SetBit(block->GetBlockId());
 }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 938d6fcd64..5ce0b8efdd 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -242,7 +242,7 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
 
   // Returns a constant of the given type and value. If it does not exist
   // already, it is created and inserted into the graph. Only integral types
-  // are currently supported.
+  // are currently cached.
   HConstant* GetConstant(Primitive::Type type, int64_t value);
   HNullConstant* GetNullConstant();
   HIntConstant* GetIntConstant(int32_t value) {
@@ -251,6 +251,8 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
   HLongConstant* GetLongConstant(int64_t value) {
     return CreateConstant(value, &cached_long_constants_);
   }
+  HFloatConstant* GetFloatConstant(float value);
+  HDoubleConstant* GetDoubleConstant(double value);
 
   HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
 
@@ -2037,10 +2039,9 @@ class HFloatConstant : public HConstant {
 
   const float value_;
 
-  // Only the SsaBuilder can currently create floating-point constants. If we
-  // ever need to create them later in the pipeline, we will have to handle them
-  // the same way as integral constants.
+  // Only the SsaBuilder and HGraph can create floating-point constants.
   friend class SsaBuilder;
+  friend class HGraph;
   DISALLOW_COPY_AND_ASSIGN(HFloatConstant);
 };
 
@@ -2074,10 +2075,9 @@ class HDoubleConstant : public HConstant {
 
   const double value_;
 
-  // Only the SsaBuilder can currently create floating-point constants. If we
-  // ever need to create them later in the pipeline, we will have to handle them
-  // the same way as integral constants.
+  // Only the SsaBuilder and HGraph can create floating-point constants.
   friend class SsaBuilder;
+  friend class HGraph;
   DISALLOW_COPY_AND_ASSIGN(HDoubleConstant);
 };
 
diff --git a/test/458-checker-instruction-simplification/src/Main.java b/test/458-checker-instruction-simplification/src/Main.java
index f0578ef1ea..25b792356d 100644
--- a/test/458-checker-instruction-simplification/src/Main.java
+++ b/test/458-checker-instruction-simplification/src/Main.java
@@ -34,6 +34,18 @@ public class Main {
     }
   }
 
+  public static void assertFloatEquals(float expected, float result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+
+  public static void assertDoubleEquals(double expected, double result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+
   /**
    * Tiny programs exercising optimizations of arithmetic identities.
    */
@@ -922,6 +934,43 @@ public class Main {
     return !(!arg);
   }
 
+  // CHECK-START: float Main.Div2(float) instruction_simplifier (before)
+  // CHECK-DAG:     [[Arg:f\d+]]      ParameterValue
+  // CHECK-DAG:     [[Const2:f\d+]]   FloatConstant 2
+  // CHECK-DAG:     [[Div:f\d+]]      Div [ [[Arg]] [[Const2]] ]
+  // CHECK-DAG:                       Return [ [[Div]] ]
+
+  // CHECK-START: float Main.Div2(float) instruction_simplifier (after)
+  // CHECK-DAG:     [[Arg:f\d+]]      ParameterValue
+  // CHECK-DAG:     [[ConstP5:f\d+]]  FloatConstant 0.5
+  // CHECK-DAG:     [[Mul:f\d+]]      Mul [ [[Arg]] [[ConstP5]] ]
+  // CHECK-DAG:                       Return [ [[Mul]] ]
+
+  // CHECK-START: float Main.Div2(float) instruction_simplifier (after)
+  // CHECK-NOT:                       Div
+
+  public static float Div2(float arg) {
+    return arg / 2.0f;
+  }
+
+  // CHECK-START: double Main.Div2(double) instruction_simplifier (before)
+  // CHECK-DAG:     [[Arg:d\d+]]      ParameterValue
+  // CHECK-DAG:     [[Const2:d\d+]]   DoubleConstant 2
+  // CHECK-DAG:     [[Div:d\d+]]      Div [ [[Arg]] [[Const2]] ]
+  // CHECK-DAG:                       Return [ [[Div]] ]
+
+  // CHECK-START: double Main.Div2(double) instruction_simplifier (after)
+  // CHECK-DAG:     [[Arg:d\d+]]      ParameterValue
+  // CHECK-DAG:     [[ConstP5:d\d+]]  DoubleConstant 0.5
+  // CHECK-DAG:     [[Mul:d\d+]]      Mul [ [[Arg]] [[ConstP5]] ]
+  // CHECK-DAG:                       Return [ [[Mul]] ]
+
+  // CHECK-START: double Main.Div2(double) instruction_simplifier (after)
+  // CHECK-NOT:                       Div
+  public static double Div2(double arg) {
+    return arg / 2.0;
+  }
+
   public static void main(String[] args) {
     int arg = 123456;
 
@@ -956,7 +1005,6 @@ public class Main {
     assertIntEquals(SubNeg1(arg, arg + 1), -(arg + arg + 1));
     assertIntEquals(SubNeg2(arg, arg + 1), -(arg + arg + 1));
     assertLongEquals(SubNeg3(arg, arg + 1), -(2 * arg + 1));
-
     assertIntEquals(EqualTrueRhs(true), 5);
     assertIntEquals(EqualTrueLhs(true), 5);
     assertIntEquals(EqualFalseRhs(true), 3);
@@ -967,5 +1015,7 @@ public class Main {
     assertIntEquals(NotEqualFalseLhs(true), 5);
     assertBooleanEquals(NotNotBool(true), true);
     assertBooleanEquals(NotNotBool(false), false);
+    assertFloatEquals(Div2(100.0f), 50.0f);
+    assertDoubleEquals(Div2(150.0), 75.0);
   }
 }