Make linear loop optimization safe from overflow
In the calcuation of `a * i + b`, `a` itself is calculated by doing:
`(end - start) + (step - 1) / step`
(Note that we add `step - 1` as a way of doing `ceiling`).
This way of calculating `a` can overflow and produce the wrong result
if end and start are in opposite sides of the spectrum.
We can force `a` to be a constant to guarantee that the right result
will be generated when doing loop optimization.
Bug: 231415860
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: Ic056441f8d672b3c48cbbd2f3e4ebd7528e2c65b
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index ad3d1a9..cc62da8 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -17,6 +17,7 @@
#include "induction_var_range.h"
#include <limits>
+#include "optimizing/nodes.h"
namespace art {
@@ -1064,10 +1065,13 @@
case HInductionVarAnalysis::kLinear:
if (*stride_value > 0) {
lower = nullptr;
+ return GenerateLastValueLinear(
+ context, loop, info, trip, graph, block, /*is_min=*/false, upper);
} else {
upper = nullptr;
+ return GenerateLastValueLinear(
+ context, loop, info, trip, graph, block, /*is_min=*/true, lower);
}
- break;
case HInductionVarAnalysis::kPolynomial:
return GenerateLastValuePolynomial(context, loop, info, trip, graph, block, lower);
case HInductionVarAnalysis::kGeometric:
@@ -1113,6 +1117,54 @@
GenerateCode(context, loop, info, trip, graph, block, /*is_min=*/ false, upper);
}
+bool InductionVarRange::GenerateLastValueLinear(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ HGraph* graph,
+ HBasicBlock* block,
+ bool is_min,
+ /*out*/ HInstruction** result) const {
+ DataType::Type type = info->type;
+ // Avoid any narrowing linear induction or any type mismatch between the linear induction and the
+ // trip count expression.
+ if (HInductionVarAnalysis::IsNarrowingLinear(info) && trip->type == info->type) {
+ return false;
+ }
+
+ // Stride value must be a known constant that fits into int32.
+ int64_t stride_value = 0;
+ if (!IsConstant(context, loop, info->op_a, kExact, &stride_value) ||
+ !CanLongValueFitIntoInt(stride_value)) {
+ return false;
+ }
+
+ // We require `a` to be a constant value that didn't overflow.
+ const bool is_min_a = stride_value >= 0 ? is_min : !is_min;
+ Value val_a = GetVal(context, loop, trip, trip, is_min_a);
+ HInstruction* opb;
+ if (!IsConstantValue(val_a) ||
+ !GenerateCode(context, loop, info->op_b, trip, graph, block, is_min, &opb)) {
+ return false;
+ }
+
+ if (graph != nullptr) {
+ ArenaAllocator* allocator = graph->GetAllocator();
+ HInstruction* oper;
+ HInstruction* opa = graph->GetConstant(type, val_a.b_constant);
+ if (stride_value == 1) {
+ oper = new (allocator) HAdd(type, opa, opb);
+ } else if (stride_value == -1) {
+ oper = new (graph->GetAllocator()) HSub(type, opb, opa);
+ } else {
+ HInstruction* mul = new (allocator) HMul(type, graph->GetConstant(type, stride_value), opa);
+ oper = new (allocator) HAdd(type, Insert(block, mul), opb);
+ }
+ *result = Insert(block, oper);
+ }
+ return true;
+}
+
bool InductionVarRange::GenerateLastValuePolynomial(const HBasicBlock* context,
const HLoopInformation* loop,
HInductionVarAnalysis::InductionInfo* info,
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 552837c..6555bc2 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -317,6 +317,15 @@
/*out*/ bool* needs_finite_test,
/*out*/ bool* needs_taken_test) const;
+ bool GenerateLastValueLinear(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ HGraph* graph,
+ HBasicBlock* block,
+ bool is_min,
+ /*out*/ HInstruction** result) const;
+
bool GenerateLastValuePolynomial(const HBasicBlock* context,
const HLoopInformation* loop,
HInductionVarAnalysis::InductionInfo* info,
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index 962123d..a83246c 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -1064,10 +1064,6 @@
HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_);
ASSERT_TRUE(last->IsSub());
ExpectInt(1000, last->InputAt(0));
- ASSERT_TRUE(last->InputAt(1)->IsNeg());
- last = last->InputAt(1)->InputAt(0);
- ASSERT_TRUE(last->IsSub());
- ExpectInt(0, last->InputAt(0));
ExpectInt(1000, last->InputAt(1));
// Loop logic.
diff --git a/test/618-checker-induction/src/Main.java b/test/618-checker-induction/src/Main.java
index dd76e41..7f17f30 100644
--- a/test/618-checker-induction/src/Main.java
+++ b/test/618-checker-induction/src/Main.java
@@ -607,6 +607,61 @@
return closed;
}
+ // Checks that we do not loop optimize if the calculation of the trip count would overflow.
+ /// CHECK-START: int Main.closedLinearStepOverflow() loop_optimization (before)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ //
+ /// CHECK-START: int Main.closedLinearStepOverflow() loop_optimization (after)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ private static int closedLinearStepOverflow() {
+ int closed = 0;
+ // Note that this isn't a "one-off" error. We are using MIN and MAX to make sure we overflow.
+ for (int i = Integer.MIN_VALUE; i < (Integer.MAX_VALUE - 80); i += 79) {
+ closed++;
+ }
+ return closed;
+ }
+
+ // Since we cannot guarantee that the start/end wouldn't overflow we do not perform loop
+ // optimization.
+ /// CHECK-START: int Main.$inline$closedByParameters(int, int) loop_optimization (before)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ //
+ /// CHECK-START: int Main.$inline$closedByParameters(int, int) loop_optimization (after)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ private static int $inline$closedByParameters(int start, int end) {
+ int closed = 0;
+ for (int i = start; i < end; i++) {
+ closed++;
+ }
+ return closed;
+ }
+
+ // Since we are inlining `closedByParameters` we know that the parameters are fixed and
+ // therefore we can perform loop optimization.
+ /// CHECK-START: int Main.closedByParametersWithInline() loop_optimization (before)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ //
+ /// CHECK-START: int Main.closedByParametersWithInline() loop_optimization (after)
+ /// CHECK-NOT: Phi
+ //
+ /// CHECK-START: int Main.closedByParametersWithInline() instruction_simplifier$after_bce (after)
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none
+ /// CHECK-DAG: Return [<<Int>>] loop:none
+ private static int closedByParametersWithInline() {
+ return $inline$closedByParameters(0, 10);
+ }
+
/// CHECK-START: int Main.waterFall() loop_optimization (before)
/// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none
/// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none
@@ -896,6 +951,9 @@
expectEquals(20, closedFeed());
expectEquals(-10, closedLargeUp());
expectEquals(10, closedLargeDown());
+ expectEquals(54366674, closedLinearStepOverflow());
+ expectEquals(10, $inline$closedByParameters(0, 10));
+ expectEquals(10, closedByParametersWithInline());
expectEquals(50, waterFall());
expectEquals(false, periodicBoolIdiom1());