From b0bd8915cb257cdaf46ba663c450a6543bca75af Mon Sep 17 00:00:00 2001 From: Mark Mendell Date: Wed, 15 Apr 2015 19:57:22 -0400 Subject: [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 --- compiler/optimizing/instruction_simplifier.cc | 67 ++++++++++++++++++++++ compiler/optimizing/nodes.cc | 12 ++++ compiler/optimizing/nodes.h | 14 ++--- .../src/Main.java | 52 ++++++++++++++++- 4 files changed, 137 insertions(+), 8 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(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(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 { // 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 { 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); }; diff --git a/test/458-checker-instruction-simplification/src/Main.java b/test/458-checker-instruction-simplification/src/Main.java index 65be6cb4c4..f26e0b1a8a 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. */ @@ -907,6 +919,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; @@ -941,7 +990,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); @@ -952,5 +1000,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); } } -- cgit v1.2.3-59-g8ed1b