[optimizing] Replace FP divide by power of 2

Replace a floating point division by a power of two by a multiplication
of the reciprocal.  This is guarenteed to have the exact same result as
it is exactly representable.

Add routines to allow generation of float and double constants after the
SSA Builder.  I was unsure if float and double caches should be
implemented.  Under the assumption that there is probably not a lot of
repetition of FP values.  Please let me know.

Change-Id: I3a6c3847b49b4e747a7e7e8843ca32bb174b1584
Signed-off-by: Mark Mendell <mark.p.mendell@intel.com>

3 files changed, 86 insertions, 7 deletions

diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index b8ae1f6369..0013b72c43 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;
@@ -380,6 +381,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 5fca4fab22..6020196493 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 d9d15c4b18..3e922a0065 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -234,7 +234,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) {
@@ -243,6 +243,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);
 
  private:
   HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
@@ -2020,10 +2022,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);
 };
 
@@ -2057,10 +2058,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);
 };