summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compiler/optimizing/induction_var_range.cc29
-rw-r--r--test/623-checker-loop-regressions/src/Main.java121
2 files changed, 139 insertions, 11 deletions
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 3973985338..5539413aad 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -57,14 +57,18 @@ static bool IsIntAndGet(HInstruction* instruction, int64_t* value) {
return false;
}
-/** Returns b^e for b,e >= 1. */
-static int64_t IntPow(int64_t b, int64_t e) {
+/** Returns b^e for b,e >= 1. Sets overflow if arithmetic wrap-around occurred. */
+static int64_t IntPow(int64_t b, int64_t e, /*out*/ bool* overflow) {
DCHECK_GE(b, 1);
DCHECK_GE(e, 1);
int64_t pow = 1;
while (e) {
if (e & 1) {
+ int64_t oldpow = pow;
pow *= b;
+ if (pow < oldpow) {
+ *overflow = true;
+ }
}
e >>= 1;
b *= b;
@@ -1020,20 +1024,27 @@ bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::Induct
HInstruction* opb = nullptr;
if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) &&
GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) {
- // Compute f ^ m for known maximum index value m.
- int64_t fpow = IntPow(f, m);
if (graph != nullptr) {
- DCHECK(info->operation == HInductionVarAnalysis::kMul ||
- info->operation == HInductionVarAnalysis::kDiv);
Primitive::Type type = info->type;
+ // Compute f ^ m for known maximum index value m.
+ bool overflow = false;
+ int64_t fpow = IntPow(f, m, &overflow);
+ if (info->operation == HInductionVarAnalysis::kDiv) {
+ // For division, any overflow truncates to zero.
+ if (overflow || (type != Primitive::kPrimLong && !CanLongValueFitIntoInt(fpow))) {
+ fpow = 0;
+ }
+ } else if (type != Primitive::kPrimLong) {
+ // For multiplication, okay to truncate to required precision.
+ DCHECK(info->operation == HInductionVarAnalysis::kMul);
+ fpow = static_cast<int32_t>(fpow);
+ }
+ // Generate code.
if (fpow == 0) {
// Special case: repeated mul/div always yields zero.
*result = graph->GetConstant(type, 0);
} else {
// Last value: a * f ^ m + b or a * f ^ -m + b.
- if (type != Primitive::kPrimLong) {
- fpow = static_cast<int32_t>(fpow); // okay to truncate
- }
HInstruction* e = nullptr;
if (info->operation == HInductionVarAnalysis::kMul) {
e = new (graph->GetArena()) HMul(type, opa, graph->GetConstant(type, fpow));
diff --git a/test/623-checker-loop-regressions/src/Main.java b/test/623-checker-loop-regressions/src/Main.java
index 7cc0b8b652..7509d9b4f3 100644
--- a/test/623-checker-loop-regressions/src/Main.java
+++ b/test/623-checker-loop-regressions/src/Main.java
@@ -154,8 +154,8 @@ public class Main {
/// CHECK-NOT: Phi
//
/// CHECK-START: int Main.polynomialInt() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant -45 loop:none
- /// CHECK-DAG: Return [<<Int>>] loop:none
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant -45 loop:none
+ /// CHECK-DAG: Return [<<Int>>] loop:none
static int polynomialInt() {
int x = 0;
for (int i = 0; i < 10; i++) {
@@ -164,6 +164,81 @@ public class Main {
return x;
}
+ // Regression test for b/34779592 (found with fuzz testing): overflow for last value
+ // of division truncates to zero, for multiplication it simply truncates.
+ //
+ /// CHECK-START: int Main.geoIntDivLastValue(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: int Main.geoIntDivLastValue(int) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ //
+ /// CHECK-START: int Main.geoIntDivLastValue(int) instruction_simplifier$after_bce (after)
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: Return [<<Int>>] loop:none
+ static int geoIntDivLastValue(int x) {
+ for (int i = 0; i < 2; i++) {
+ x /= 1081788608;
+ }
+ return x;
+ }
+
+ /// CHECK-START: int Main.geoIntMulLastValue(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: int Main.geoIntMulLastValue(int) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ //
+ /// CHECK-START: int Main.geoIntMulLastValue(int) instruction_simplifier$after_bce (after)
+ /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant -194211840 loop:none
+ /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Par>>,<<Int>>] loop:none
+ /// CHECK-DAG: Return [<<Mul>>] loop:none
+ static int geoIntMulLastValue(int x) {
+ for (int i = 0; i < 2; i++) {
+ x *= 1081788608;
+ }
+ return x;
+ }
+
+ /// CHECK-START: long Main.geoLongDivLastValue(long) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: long Main.geoLongDivLastValue(long) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ //
+ /// CHECK-START: long Main.geoLongDivLastValue(long) instruction_simplifier$after_bce (after)
+ /// CHECK-DAG: <<Long:j\d+>> LongConstant 0 loop:none
+ /// CHECK-DAG: Return [<<Long>>] loop:none
+ static long geoLongDivLastValue(long x) {
+ for (int i = 0; i < 10; i++) {
+ x /= 1081788608;
+ }
+ return x;
+ }
+
+ /// CHECK-START: long Main.geoLongMulLastValue(long) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: long Main.geoLongMulLastValue(long) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ //
+ /// CHECK-START: long Main.geoLongMulLastValue(long) instruction_simplifier$after_bce (after)
+ /// CHECK-DAG: <<Par:j\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Long:j\d+>> LongConstant -8070450532247928832 loop:none
+ /// CHECK-DAG: <<Mul:j\d+>> Mul [<<Par>>,<<Long>>] loop:none
+ /// CHECK-DAG: Return [<<Mul>>] loop:none
+ static long geoLongMulLastValue(long x) {
+ for (int i = 0; i < 10; i++) {
+ x *= 1081788608;
+ }
+ return x;
+ }
+
public static void main(String[] args) {
expectEquals(10, earlyExitFirst(-1));
for (int i = 0; i <= 10; i++) {
@@ -185,6 +260,42 @@ public class Main {
expectEquals(-45, polynomialIntFromLong());
expectEquals(-45, polynomialInt());
+ expectEquals(0, geoIntDivLastValue(0));
+ expectEquals(0, geoIntDivLastValue(1));
+ expectEquals(0, geoIntDivLastValue(2));
+ expectEquals(0, geoIntDivLastValue(1081788608));
+ expectEquals(0, geoIntDivLastValue(-1081788608));
+ expectEquals(0, geoIntDivLastValue(2147483647));
+ expectEquals(0, geoIntDivLastValue(-2147483648));
+
+ expectEquals( 0, geoIntMulLastValue(0));
+ expectEquals( -194211840, geoIntMulLastValue(1));
+ expectEquals( -388423680, geoIntMulLastValue(2));
+ expectEquals(-1041498112, geoIntMulLastValue(1081788608));
+ expectEquals( 1041498112, geoIntMulLastValue(-1081788608));
+ expectEquals( 194211840, geoIntMulLastValue(2147483647));
+ expectEquals( 0, geoIntMulLastValue(-2147483648));
+
+ expectEquals(0L, geoLongDivLastValue(0L));
+ expectEquals(0L, geoLongDivLastValue(1L));
+ expectEquals(0L, geoLongDivLastValue(2L));
+ expectEquals(0L, geoLongDivLastValue(1081788608L));
+ expectEquals(0L, geoLongDivLastValue(-1081788608L));
+ expectEquals(0L, geoLongDivLastValue(2147483647L));
+ expectEquals(0L, geoLongDivLastValue(-2147483648L));
+ expectEquals(0L, geoLongDivLastValue(9223372036854775807L));
+ expectEquals(0L, geoLongDivLastValue(-9223372036854775808L));
+
+ expectEquals( 0L, geoLongMulLastValue(0L));
+ expectEquals(-8070450532247928832L, geoLongMulLastValue(1L));
+ expectEquals( 2305843009213693952L, geoLongMulLastValue(2L));
+ expectEquals( 0L, geoLongMulLastValue(1081788608L));
+ expectEquals( 0L, geoLongMulLastValue(-1081788608L));
+ expectEquals( 8070450532247928832L, geoLongMulLastValue(2147483647L));
+ expectEquals( 0L, geoLongMulLastValue(-2147483648L));
+ expectEquals( 8070450532247928832L, geoLongMulLastValue(9223372036854775807L));
+ expectEquals( 0L, geoLongMulLastValue(-9223372036854775808L));
+
System.out.println("passed");
}
@@ -193,4 +304,10 @@ public class Main {
throw new Error("Expected: " + expected + ", found: " + result);
}
}
+
+ private static void expectEquals(long expected, long result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
}
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-20 01:54:10 +0000