[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>
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index b8ae1f6..0013b72 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -39,6 +39,7 @@
}
bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop);
+ bool IsExactFPPowerOfTwo(HConstant* constant);
void VisitShift(HBinaryOperation* shift);
void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE;
@@ -380,6 +381,72 @@
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 5fca4fa..6020196 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -343,6 +343,18 @@
}
}
+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 d9d15c4..3e922a0 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -234,7 +234,7 @@
// 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 @@
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 @@
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 @@
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 65be6cb..f26e0b1 100644
--- a/test/458-checker-instruction-simplification/src/Main.java
+++ b/test/458-checker-instruction-simplification/src/Main.java
@@ -34,6 +34,18 @@
}
}
+ 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.
*/
@@ -907,6 +919,43 @@
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;
@@ -941,7 +990,6 @@
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);
@@ -952,5 +1000,7 @@
assertIntEquals(NotEqualFalseLhs(true), 5);
assertBooleanEquals(NotNotBool(true), true);
assertBooleanEquals(NotNotBool(false), false);
+ assertFloatEquals(Div2(100.0f), 50.0f);
+ assertDoubleEquals(Div2(150.0), 75.0);
}
}
