diff options
| -rw-r--r-- | compiler/optimizing/constant_folding.cc | 51 | ||||
| -rw-r--r-- | compiler/optimizing/inliner.cc | 15 | ||||
| -rw-r--r-- | test/2269-checker-constant-folding-instrinsics/src/Main.java | 111 |
3 files changed, 172 insertions, 5 deletions
diff --git a/compiler/optimizing/constant_folding.cc b/compiler/optimizing/constant_folding.cc index 29f5d5caee..66bbf548bb 100644 --- a/compiler/optimizing/constant_folding.cc +++ b/compiler/optimizing/constant_folding.cc @@ -60,6 +60,7 @@ class HConstantFoldingVisitor final : public HGraphDelegateVisitor { void FoldReverseIntrinsic(HInvoke* invoke); void FoldReverseBytesIntrinsic(HInvoke* invoke); void FoldBitCountIntrinsic(HInvoke* invoke); + void FoldDivideUnsignedIntrinsic(HInvoke* invoke); void FoldHighestOneBitIntrinsic(HInvoke* invoke); void FoldLowestOneBitIntrinsic(HInvoke* invoke); void FoldNumberOfLeadingZerosIntrinsic(HInvoke* invoke); @@ -379,6 +380,10 @@ void HConstantFoldingVisitor::VisitInvoke(HInvoke* inst) { case Intrinsics::kLongBitCount: FoldBitCountIntrinsic(inst); break; + case Intrinsics::kIntegerDivideUnsigned: + case Intrinsics::kLongDivideUnsigned: + FoldDivideUnsignedIntrinsic(inst); + break; case Intrinsics::kIntegerHighestOneBit: case Intrinsics::kLongHighestOneBit: FoldHighestOneBitIntrinsic(inst); @@ -467,6 +472,52 @@ void HConstantFoldingVisitor::FoldBitCountIntrinsic(HInvoke* inst) { inst->GetBlock()->RemoveInstruction(inst); } +void HConstantFoldingVisitor::FoldDivideUnsignedIntrinsic(HInvoke* inst) { + DCHECK(inst->GetIntrinsic() == Intrinsics::kIntegerDivideUnsigned || + inst->GetIntrinsic() == Intrinsics::kLongDivideUnsigned); + + HInstruction* divisor = inst->InputAt(1); + if (!divisor->IsConstant()) { + return; + } + DCHECK_IMPLIES(inst->GetIntrinsic() == Intrinsics::kIntegerDivideUnsigned, + divisor->IsIntConstant()); + DCHECK_IMPLIES(inst->GetIntrinsic() == Intrinsics::kLongDivideUnsigned, + divisor->IsLongConstant()); + const bool is_int_intrinsic = inst->GetIntrinsic() == Intrinsics::kIntegerDivideUnsigned; + if ((is_int_intrinsic && divisor->AsIntConstant()->IsArithmeticZero()) || + (!is_int_intrinsic && divisor->AsLongConstant()->IsArithmeticZero())) { + // We will be throwing, don't constant fold. + inst->SetAlwaysThrows(true); + GetGraph()->SetHasAlwaysThrowingInvokes(true); + return; + } + + HInstruction* dividend = inst->InputAt(0); + if (!dividend->IsConstant()) { + return; + } + DCHECK_IMPLIES(inst->GetIntrinsic() == Intrinsics::kIntegerDivideUnsigned, + dividend->IsIntConstant()); + DCHECK_IMPLIES(inst->GetIntrinsic() == Intrinsics::kLongDivideUnsigned, + dividend->IsLongConstant()); + + if (is_int_intrinsic) { + uint32_t dividend_val = + dchecked_integral_cast<uint32_t>(dividend->AsIntConstant()->GetValueAsUint64()); + uint32_t divisor_val = + dchecked_integral_cast<uint32_t>(divisor->AsIntConstant()->GetValueAsUint64()); + inst->ReplaceWith(GetGraph()->GetIntConstant(static_cast<int32_t>(dividend_val / divisor_val))); + } else { + uint64_t dividend_val = dividend->AsLongConstant()->GetValueAsUint64(); + uint64_t divisor_val = divisor->AsLongConstant()->GetValueAsUint64(); + inst->ReplaceWith( + GetGraph()->GetLongConstant(static_cast<int64_t>(dividend_val / divisor_val))); + } + + inst->GetBlock()->RemoveInstruction(inst); +} + void HConstantFoldingVisitor::FoldHighestOneBitIntrinsic(HInvoke* inst) { DCHECK(inst->GetIntrinsic() == Intrinsics::kIntegerHighestOneBit || inst->GetIntrinsic() == Intrinsics::kLongHighestOneBit); diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc index 9d80db0de0..f65941090d 100644 --- a/compiler/optimizing/inliner.cc +++ b/compiler/optimizing/inliner.cc @@ -144,11 +144,6 @@ bool HInliner::Run() { } bool did_inline = false; - // The inliner is the only phase that sets invokes as `always throwing`, and since we only run the - // inliner once per graph this value should always be false at the beginning of the inlining - // phase. This is important since we use `HasAlwaysThrowingInvokes` to know whether the inliner - // phase performed a relevant change in the graph. - DCHECK(!graph_->HasAlwaysThrowingInvokes()); // Initialize the number of instructions for the method being compiled. Recursive calls // to HInliner::Run have already updated the instruction count. @@ -210,6 +205,16 @@ bool HInliner::Run() { // We return true if we either inlined at least one method, or we marked one of our methods as // always throwing. + // To check if we added an always throwing method we can either: + // 1) Pass a boolean throughout the pipeline and get an accurate result, or + // 2) Just check that the `HasAlwaysThrowingInvokes()` flag is true now. This is not 100% + // accurate but the only other part where we set `HasAlwaysThrowingInvokes` is constant + // folding the DivideUnsigned intrinsics for when the divisor is known to be 0. This case is + // rare enough that changing the pipeline for this is not worth it. In the case of the false + // positive (i.e. A) we didn't inline at all, B) the graph already had an always throwing + // invoke, and C) we didn't set any new always throwing invokes), we will be running constant + // folding, instruction simplifier, and dead code elimination one more time even though it + // shouldn't change things. There's no false negative case. return did_inline || graph_->HasAlwaysThrowingInvokes(); } diff --git a/test/2269-checker-constant-folding-instrinsics/src/Main.java b/test/2269-checker-constant-folding-instrinsics/src/Main.java index 660bc6a903..0059db88f4 100644 --- a/test/2269-checker-constant-folding-instrinsics/src/Main.java +++ b/test/2269-checker-constant-folding-instrinsics/src/Main.java @@ -23,6 +23,8 @@ public class Main { $noinline$testReverseBytesShort(); $noinline$testBitCountInt(); $noinline$testBitCountLong(); + $noinline$testDivideUnsignedInt(); + $noinline$testDivideUnsignedLong(); $noinline$testHighestOneBitInt(); $noinline$testHighestOneBitLong(); $noinline$testLowestOneBitInt(); @@ -673,6 +675,115 @@ public class Main { $noinline$assertLongEquals(63L, Long.bitCount((1L << 63) - 1L)); } + /// CHECK-START: void Main.$noinline$testDivideUnsignedInt() constant_folding (before) + /// CHECK-DAG: InvokeStaticOrDirect intrinsic:IntegerDivideUnsigned + + /// CHECK-START: void Main.$noinline$testDivideUnsignedInt() constant_folding (after) + /// CHECK-NOT: InvokeStaticOrDirect intrinsic:IntegerDivideUnsigned + private static void $noinline$testDivideUnsignedInt() { + // Positive/Positive division is as normal. + $noinline$assertIntEquals(5, Integer.divideUnsigned(10, 2)); + $noinline$assertIntEquals(0, Integer.divideUnsigned(2, 10)); + $noinline$assertIntEquals(1, Integer.divideUnsigned(42, 42)); + + // Positive/Negative is 0, as negative numbers are bigger (if taking a look as unsigned). + $noinline$assertIntEquals(0, Integer.divideUnsigned(10, -2)); + $noinline$assertIntEquals(0, Integer.divideUnsigned(2, -10)); + $noinline$assertIntEquals(0, Integer.divideUnsigned(42, -42)); + $noinline$assertIntEquals(0, Integer.divideUnsigned(Integer.MAX_VALUE, -1)); + + // Negative/Positive + $noinline$assertIntEquals(2147483643, Integer.divideUnsigned(-10, 2)); + $noinline$assertIntEquals(429496729, Integer.divideUnsigned(-2, 10)); + $noinline$assertIntEquals(102261125, Integer.divideUnsigned(-42, 42)); + $noinline$assertIntEquals(1, Integer.divideUnsigned(Integer.MIN_VALUE, Integer.MAX_VALUE)); + $noinline$assertIntEquals(-1, Integer.divideUnsigned(-1, 1)); + + // Negative/Negative + $noinline$assertIntEquals(0, Integer.divideUnsigned(-2, -1)); + $noinline$assertIntEquals(1, Integer.divideUnsigned(-1, -2)); + $noinline$assertIntEquals(0, Integer.divideUnsigned(-10, -2)); + $noinline$assertIntEquals(1, Integer.divideUnsigned(-2, -10)); + + // Special cases where we don't constant fold the intrinsic + $noinline$testDivideUnsignedInt_divideByZero(); + } + + /// CHECK-START: void Main.$noinline$testDivideUnsignedInt_divideByZero() constant_folding (before) + /// CHECK: InvokeStaticOrDirect intrinsic:IntegerDivideUnsigned + /// CHECK: InvokeStaticOrDirect intrinsic:IntegerDivideUnsigned + + /// CHECK-START: void Main.$noinline$testDivideUnsignedInt_divideByZero() constant_folding (after) + /// CHECK: InvokeStaticOrDirect intrinsic:IntegerDivideUnsigned + /// CHECK: InvokeStaticOrDirect intrinsic:IntegerDivideUnsigned + private static void $noinline$testDivideUnsignedInt_divideByZero() { + try { + $noinline$assertIntEquals(0, Integer.divideUnsigned(1, 0)); + throw new Error("Tried to divide 1 and 0 but didn't get an exception"); + } catch (ArithmeticException expected) { + } + + try { + $noinline$assertIntEquals(0, Integer.divideUnsigned(-1, 0)); + throw new Error("Tried to divide -1 and 0 but didn't get an exception"); + } catch (ArithmeticException expected) { + } + } + + /// CHECK-START: void Main.$noinline$testDivideUnsignedLong() constant_folding (before) + /// CHECK-DAG: InvokeStaticOrDirect intrinsic:LongDivideUnsigned + + /// CHECK-START: void Main.$noinline$testDivideUnsignedLong() constant_folding (after) + /// CHECK-NOT: InvokeStaticOrDirect intrinsic:LongDivideUnsigned + private static void $noinline$testDivideUnsignedLong() { + // Positive/Positive division is as normal. + $noinline$assertLongEquals(5L, Long.divideUnsigned(10L, 2L)); + $noinline$assertLongEquals(0L, Long.divideUnsigned(2L, 10L)); + $noinline$assertLongEquals(1L, Long.divideUnsigned(42L, 42L)); + + // Positive/Negative is 0, as negative numbers are bigger (if taking a look as unsigned). + $noinline$assertLongEquals(0L, Long.divideUnsigned(10L, -2L)); + $noinline$assertLongEquals(0L, Long.divideUnsigned(2L, -10L)); + $noinline$assertLongEquals(0L, Long.divideUnsigned(42L, -42L)); + $noinline$assertLongEquals(0L, Long.divideUnsigned(Long.MAX_VALUE, -1L)); + + // Negative/Positive + $noinline$assertLongEquals(9223372036854775803L, Long.divideUnsigned(-10L, 2L)); + $noinline$assertLongEquals(1844674407370955161L, Long.divideUnsigned(-2L, 10L)); + $noinline$assertLongEquals(439208192231179799L, Long.divideUnsigned(-42L, 42L)); + $noinline$assertLongEquals(1L, Long.divideUnsigned(Long.MIN_VALUE, Long.MAX_VALUE)); + $noinline$assertLongEquals(-1L, Long.divideUnsigned(-1L, 1L)); + + // Negative/Negative + $noinline$assertLongEquals(0L, Long.divideUnsigned(-2L, -1L)); + $noinline$assertLongEquals(1L, Long.divideUnsigned(-1L, -2L)); + $noinline$assertLongEquals(0L, Long.divideUnsigned(-10L, -2L)); + $noinline$assertLongEquals(1L, Long.divideUnsigned(-2L, -10L)); + + // Special cases where we don't constant fold the intrinsic + $noinline$testDivideUnsignedLong_divideByZero(); + } + + /// CHECK-START: void Main.$noinline$testDivideUnsignedLong_divideByZero() constant_folding (before) + /// CHECK: InvokeStaticOrDirect intrinsic:LongDivideUnsigned + /// CHECK: InvokeStaticOrDirect intrinsic:LongDivideUnsigned + + /// CHECK-START: void Main.$noinline$testDivideUnsignedLong_divideByZero() constant_folding (after) + /// CHECK: InvokeStaticOrDirect intrinsic:LongDivideUnsigned + /// CHECK: InvokeStaticOrDirect intrinsic:LongDivideUnsigned + private static void $noinline$testDivideUnsignedLong_divideByZero() { + try { + $noinline$assertLongEquals(0L, Long.divideUnsigned(1L, 0L)); + throw new Error("Tried to divide 1 and 0 but didn't get an exception"); + } catch (ArithmeticException expected) { + } + + try { + $noinline$assertLongEquals(0L, Long.divideUnsigned(-1L, 0L)); + throw new Error("Tried to divide -1 and 0 but didn't get an exception"); + } catch (ArithmeticException expected) { + } + } /// CHECK-START: void Main.$noinline$testHighestOneBitInt() constant_folding (before) /// CHECK-DAG: InvokeStaticOrDirect intrinsic:IntegerHighestOneBit |