From 4f18b94f4f8140644cabbfff5077178a19dd37e4 Mon Sep 17 00:00:00 2001
From: Santiago Aboy Solanes <solanes@google.com>
Date: Thu, 21 Jul 2022 10:31:21 +0100
Subject: 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
---
 compiler/optimizing/induction_var_range.cc | 54 +++++++++++++++++++++++++++++-
 1 file changed, 53 insertions(+), 1 deletion(-)

(limited to 'compiler/optimizing/induction_var_range.cc')

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,
-- 
cgit v1.2.3-59-g8ed1b