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

3 files changed, 62 insertions, 5 deletions

diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index ad3d1a9321..cc62da848c 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 @@ bool InductionVarRange::GenerateRangeOrLastValue(const HBasicBlock* context,
       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 @@ bool InductionVarRange::GenerateRangeOrLastValue(const HBasicBlock* context,
       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 552837c044..6555bc2206 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -317,6 +317,15 @@ class InductionVarRange {
                                 /*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 962123d948..a83246cf13 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -1064,10 +1064,6 @@ TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
   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.