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,