Induction variable range analysis.
Rationale: by computing an upper bound on the trip count of each
loop after induction var analysis has completed, a
simple range analysis yields lower and upper bounds on
all induced expressions in a loop; this analysis
plugs directly into BCE (follow-up CL).
Change-Id: I46a3fe48721ca372547199b39a3498c47992597d
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 300ffbe..3f5a6e7 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -98,6 +98,9 @@
DCHECK(stack_.empty());
map_.clear();
+
+ // Determine the loop's trip count.
+ VisitControl(loop);
}
void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) {
@@ -346,7 +349,7 @@
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(InductionInfo* a,
InductionInfo* b,
- Primitive::Type t) {
+ Primitive::Type type) {
// Transfer over a shift left: treat shift by restricted constant as equivalent multiplication.
int64_t value = -1;
if (a != nullptr && IsIntAndGet(b, &value)) {
@@ -355,10 +358,9 @@
// The restriction on the shift factor avoids generating a negative constant
// (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that generalization
// for shift factors outside [0,32) and [0,64) ranges is done by earlier simplification.
- if (t == Primitive::kPrimInt && 0 <= value && value < 31) {
- return TransferMul(a, CreateInvariantFetch(graph_->GetIntConstant(1 << value)));
- } else if (t == Primitive::kPrimLong && 0 <= value && value < 63) {
- return TransferMul(a, CreateInvariantFetch(graph_->GetLongConstant(1L << value)));
+ if ((type == Primitive::kPrimInt && 0 <= value && value < 31) ||
+ (type == Primitive::kPrimLong && 0 <= value && value < 63)) {
+ return TransferMul(a, CreateConstant(1 << value, type));
}
}
return nullptr;
@@ -458,6 +460,111 @@
return nullptr;
}
+void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) {
+ HInstruction* control = loop->GetHeader()->GetLastInstruction();
+ if (control->IsIf()) {
+ HIf* ifs = control->AsIf();
+ HBasicBlock* if_true = ifs->IfTrueSuccessor();
+ HBasicBlock* if_false = ifs->IfFalseSuccessor();
+ HInstruction* if_expr = ifs->InputAt(0);
+ // Determine if loop has following structure in header.
+ // loop-header: ....
+ // if (condition) goto X
+ if (if_expr->IsCondition()) {
+ HCondition* condition = if_expr->AsCondition();
+ InductionInfo* a = LookupInfo(loop, condition->InputAt(0));
+ InductionInfo* b = LookupInfo(loop, condition->InputAt(1));
+ Primitive::Type type = condition->InputAt(0)->GetType();
+ // Determine if the loop control uses integral arithmetic and an if-exit (X outside) or an
+ // if-iterate (X inside), always expressed as if-iterate when passing into VisitCondition().
+ if (type != Primitive::kPrimInt && type != Primitive::kPrimLong) {
+ // Loop control is not 32/64-bit integral.
+ } else if (a == nullptr || b == nullptr) {
+ // Loop control is not a sequence.
+ } else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) {
+ VisitCondition(loop, a, b, type, condition->GetOppositeCondition());
+ } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) {
+ VisitCondition(loop, a, b, type, condition->GetCondition());
+ }
+ }
+ }
+}
+
+void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop,
+ InductionInfo* a,
+ InductionInfo* b,
+ Primitive::Type type,
+ IfCondition cmp) {
+ if (a->induction_class == kInvariant && b->induction_class == kLinear) {
+ // Swap conditions (e.g. U > i is same as i < U).
+ switch (cmp) {
+ case kCondLT: VisitCondition(loop, b, a, type, kCondGT); break;
+ case kCondLE: VisitCondition(loop, b, a, type, kCondGE); break;
+ case kCondGT: VisitCondition(loop, b, a, type, kCondLT); break;
+ case kCondGE: VisitCondition(loop, b, a, type, kCondLE); break;
+ default: break;
+ }
+ } else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
+ // Normalize a linear loop control with a constant, nonzero stride:
+ // stride > 0, either i < U or i <= U
+ // stride < 0, either i > U or i >= U
+ InductionInfo* stride = a->op_a;
+ InductionInfo* lo_val = a->op_b;
+ InductionInfo* hi_val = b;
+ int64_t value = -1;
+ if (IsIntAndGet(stride, &value)) {
+ if ((value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
+ (value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
+ bool is_strict = cmp == kCondLT || cmp == kCondGT;
+ VisitTripCount(loop, lo_val, hi_val, stride, value, type, is_strict);
+ }
+ }
+ }
+}
+
+void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop,
+ InductionInfo* lo_val,
+ InductionInfo* hi_val,
+ InductionInfo* stride,
+ int32_t stride_value,
+ Primitive::Type type,
+ bool is_strict) {
+ // Any loop of the general form:
+ //
+ // for (i = L; i <= U; i += S) // S > 0
+ // or for (i = L; i >= U; i += S) // S < 0
+ // .. i ..
+ //
+ // can be normalized into:
+ //
+ // for (n = 0; n < TC; n++) // where TC = (U + S - L) / S
+ // .. L + S * n ..
+ //
+ // NOTE: The TC (trip-count) expression is only valid if the top-test path is taken at
+ // least once. Otherwise TC is 0. Also, the expression assumes the loop does not
+ // have any early-exits. Otherwise, TC is an upper bound.
+ //
+ bool cancels = is_strict && abs(stride_value) == 1; // compensation cancels conversion?
+ if (!cancels) {
+ // Convert exclusive integral inequality into inclusive integral inequality,
+ // viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1.
+ if (is_strict) {
+ const InductionOp op = stride_value > 0 ? kSub : kAdd;
+ hi_val = CreateInvariantOp(op, hi_val, CreateConstant(1, type));
+ }
+ // Compensate for stride.
+ hi_val = CreateInvariantOp(kAdd, hi_val, stride);
+ }
+
+ // Assign the trip-count expression to the loop control. Clients that use the information
+ // should be aware that due to the L <= U assumption, the expression is only valid in the
+ // loop-body proper, and not yet in the loop-header. If the loop has any early exits, the
+ // trip-count forms a conservative upper bound on the number of loop iterations.
+ InductionInfo* trip_count =
+ CreateInvariantOp(kDiv, CreateInvariantOp(kSub, hi_val, lo_val), stride);
+ AssignInfo(loop, loop->GetHeader()->GetLastInstruction(), trip_count);
+}
+
void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
HInstruction* instruction,
InductionInfo* info) {
@@ -487,6 +594,15 @@
return nullptr;
}
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateConstant(int64_t value,
+ Primitive::Type type) {
+ if (type == Primitive::kPrimInt) {
+ return CreateInvariantFetch(graph_->GetIntConstant(value));
+ }
+ DCHECK_EQ(type, Primitive::kPrimLong);
+ return CreateInvariantFetch(graph_->GetLongConstant(value));
+}
+
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant(
InductionOp op,
InductionInfo* a,
@@ -504,30 +620,44 @@
} else if (op == kMul) {
return a;
}
- } else if (value == 1 && op == kMul) {
- // Simplify 1 * b = b.
- return b;
+ } else if (op == kMul) {
+ // Simplify 1 * b = b, -1 * b = -b
+ if (value == 1) {
+ return b;
+ } else if (value == -1) {
+ op = kNeg;
+ a = nullptr;
+ }
}
}
if (IsIntAndGet(b, &value)) {
if (value == 0) {
- // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, - 0 = 0.
+ // Simplify a + 0 = a, a - 0 = a, a * 0 = 0, -0 = 0.
if (op == kAdd || op == kSub) {
return a;
} else if (op == kMul || op == kNeg) {
return b;
}
- } else if (value == 1 && (op == kMul || op == kDiv)) {
- // Simplify a * 1 = a, a / 1 = a.
- return a;
+ } else if (op == kMul || op == kDiv) {
+ // Simplify a * 1 = a, a / 1 = a, a * -1 = -a, a / -1 = -a
+ if (value == 1) {
+ return a;
+ } else if (value == -1) {
+ op = kNeg;
+ b = a;
+ a = nullptr;
+ }
}
} else if (b->operation == kNeg) {
- // Simplify a + (-b) = a - b, a - (-b) = a + b, - (-b) = b.
- switch (op) {
- case kAdd: op = kSub; b = b->op_b; break;
- case kSub: op = kAdd; b = b->op_b; break;
- case kNeg: return b->op_b;
- default: break;
+ // Simplify a + (-b) = a - b, a - (-b) = a + b, -(-b) = b.
+ if (op == kAdd) {
+ op = kSub;
+ b = b->op_b;
+ } else if (op == kSub) {
+ op = kAdd;
+ b = b->op_b;
+ } else if (op == kNeg) {
+ return b->op_b;
}
}
return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 180d1f7..8eccf92 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -126,7 +126,7 @@
InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b);
InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
- InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type t);
+ InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
InductionInfo* TransferNeg(InductionInfo* a);
// Solvers.
@@ -142,9 +142,25 @@
bool is_first_call);
InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
+ // Trip count information.
+ void VisitControl(HLoopInformation* loop);
+ void VisitCondition(HLoopInformation* loop,
+ InductionInfo* a,
+ InductionInfo* b,
+ Primitive::Type type,
+ IfCondition cmp);
+ void VisitTripCount(HLoopInformation* loop,
+ InductionInfo* lo_val,
+ InductionInfo* hi_val,
+ InductionInfo* stride,
+ int32_t stride_value,
+ Primitive::Type type,
+ bool is_strict);
+
// Assign and lookup.
void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
+ InductionInfo* CreateConstant(int64_t value, Primitive::Type type);
InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
// Helpers.
@@ -168,6 +184,8 @@
ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
friend class InductionVarAnalysisTest;
+ friend class InductionVarRange;
+ friend class InductionVarRangeTest;
DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
};
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index cfd0b16..fca1ca5 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -99,7 +99,7 @@
loop_preheader_[d]->AddInstruction(new (&allocator_) HStoreLocal(basic_[d], constant0_));
HInstruction* load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt);
loop_header_[d]->AddInstruction(load);
- HInstruction* compare = new (&allocator_) HGreaterThanOrEqual(load, constant100_);
+ HInstruction* compare = new (&allocator_) HLessThan(load, constant100_);
loop_header_[d]->AddInstruction(compare);
loop_header_[d]->AddInstruction(new (&allocator_) HIf(compare));
load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt);
@@ -231,6 +231,9 @@
EXPECT_STREQ("((1) * i + (0))", GetInductionInfo(store->InputAt(1), 0).c_str());
EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[0], 0).c_str());
+
+ // Trip-count.
+ EXPECT_STREQ("(100)", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindDerivedInduction) {
@@ -546,6 +549,8 @@
EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str());
}
EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[d], d).c_str());
+ // Trip-count.
+ EXPECT_STREQ("(100)", GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str());
}
}
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
new file mode 100644
index 0000000..bd90334
--- /dev/null
+++ b/compiler/optimizing/induction_var_range.cc
@@ -0,0 +1,343 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <limits.h>
+
+#include "induction_var_range.h"
+
+namespace art {
+
+static bool IsValidConstant32(int32_t c) {
+ return INT_MIN < c && c < INT_MAX;
+}
+
+static bool IsValidConstant64(int64_t c) {
+ return INT_MIN < c && c < INT_MAX;
+}
+
+/** Returns true if 32-bit addition can be done safely (and is not an unknown range). */
+static bool IsSafeAdd(int32_t c1, int32_t c2) {
+ if (IsValidConstant32(c1) && IsValidConstant32(c2)) {
+ return IsValidConstant64(static_cast<int64_t>(c1) + static_cast<int64_t>(c2));
+ }
+ return false;
+}
+
+/** Returns true if 32-bit subtraction can be done safely (and is not an unknown range). */
+static bool IsSafeSub(int32_t c1, int32_t c2) {
+ if (IsValidConstant32(c1) && IsValidConstant32(c2)) {
+ return IsValidConstant64(static_cast<int64_t>(c1) - static_cast<int64_t>(c2));
+ }
+ return false;
+}
+
+/** Returns true if 32-bit multiplication can be done safely (and is not an unknown range). */
+static bool IsSafeMul(int32_t c1, int32_t c2) {
+ if (IsValidConstant32(c1) && IsValidConstant32(c2)) {
+ return IsValidConstant64(static_cast<int64_t>(c1) * static_cast<int64_t>(c2));
+ }
+ return false;
+}
+
+/** Returns true if 32-bit division can be done safely (and is not an unknown range). */
+static bool IsSafeDiv(int32_t c1, int32_t c2) {
+ if (IsValidConstant32(c1) && IsValidConstant32(c2) && c2 != 0) {
+ return IsValidConstant64(static_cast<int64_t>(c1) / static_cast<int64_t>(c2));
+ }
+ return false;
+}
+
+/** Returns true for 32/64-bit integral constant within known range. */
+static bool IsIntAndGet(HInstruction* instruction, int32_t* value) {
+ if (instruction->IsIntConstant()) {
+ const int32_t c = instruction->AsIntConstant()->GetValue();
+ if (IsValidConstant32(c)) {
+ *value = c;
+ return true;
+ }
+ } else if (instruction->IsLongConstant()) {
+ const int64_t c = instruction->AsLongConstant()->GetValue();
+ if (IsValidConstant64(c)) {
+ *value = c;
+ return true;
+ }
+ }
+ return false;
+}
+
+//
+// Public class methods.
+//
+
+InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis)
+ : induction_analysis_(induction_analysis) {
+}
+
+InductionVarRange::Value InductionVarRange::GetMinInduction(HInstruction* context,
+ HInstruction* instruction) {
+ HLoopInformation* loop = context->GetBlock()->GetLoopInformation();
+ if (loop != nullptr && induction_analysis_ != nullptr) {
+ return GetMin(induction_analysis_->LookupInfo(loop, instruction), GetTripCount(loop, context));
+ }
+ return Value(INT_MIN);
+}
+
+InductionVarRange::Value InductionVarRange::GetMaxInduction(HInstruction* context,
+ HInstruction* instruction) {
+ HLoopInformation* loop = context->GetBlock()->GetLoopInformation();
+ if (loop != nullptr && induction_analysis_ != nullptr) {
+ return GetMax(induction_analysis_->LookupInfo(loop, instruction), GetTripCount(loop, context));
+ }
+ return Value(INT_MAX);
+}
+
+//
+// Private class methods.
+//
+
+HInductionVarAnalysis::InductionInfo* InductionVarRange::GetTripCount(HLoopInformation* loop,
+ HInstruction* context) {
+ // The trip-count expression is only valid when the top-test is taken at least once,
+ // that means, when the analyzed context appears outside the loop header itself.
+ // Early-exit loops are okay, since in those cases, the trip-count is conservative.
+ if (context->GetBlock() != loop->GetHeader()) {
+ HInductionVarAnalysis::InductionInfo* trip =
+ induction_analysis_->LookupInfo(loop, loop->GetHeader()->GetLastInstruction());
+ if (trip != nullptr) {
+ // Wrap the trip-count representation in its own unusual NOP node, so that range analysis
+ // is able to determine the [0, TC - 1] interval without having to construct constants.
+ return induction_analysis_->CreateInvariantOp(HInductionVarAnalysis::kNop, trip, trip);
+ }
+ }
+ return nullptr;
+}
+
+InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
+ int32_t fail_value) {
+ // Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes
+ // more likely range analysis will compare the same instructions as terminal nodes.
+ int32_t value;
+ if (IsIntAndGet(instruction, &value)) {
+ return Value(value);
+ } else if (instruction->IsAdd()) {
+ if (IsIntAndGet(instruction->InputAt(0), &value)) {
+ return AddValue(Value(value), GetFetch(instruction->InputAt(1), fail_value), fail_value);
+ } else if (IsIntAndGet(instruction->InputAt(1), &value)) {
+ return AddValue(GetFetch(instruction->InputAt(0), fail_value), Value(value), fail_value);
+ }
+ }
+ return Value(instruction, 1, 0);
+}
+
+InductionVarRange::Value InductionVarRange::GetMin(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip) {
+ if (info != nullptr) {
+ switch (info->induction_class) {
+ case HInductionVarAnalysis::kInvariant:
+ // Invariants.
+ switch (info->operation) {
+ case HInductionVarAnalysis::kNop: // normalized: 0
+ DCHECK_EQ(info->op_a, info->op_b);
+ return Value(0);
+ case HInductionVarAnalysis::kAdd:
+ return AddValue(GetMin(info->op_a, trip), GetMin(info->op_b, trip), INT_MIN);
+ case HInductionVarAnalysis::kSub: // second max!
+ return SubValue(GetMin(info->op_a, trip), GetMax(info->op_b, trip), INT_MIN);
+ case HInductionVarAnalysis::kNeg: // second max!
+ return SubValue(Value(0), GetMax(info->op_b, trip), INT_MIN);
+ case HInductionVarAnalysis::kMul:
+ return GetMul(info->op_a, info->op_b, trip, INT_MIN);
+ case HInductionVarAnalysis::kDiv:
+ return GetDiv(info->op_a, info->op_b, trip, INT_MIN);
+ case HInductionVarAnalysis::kFetch:
+ return GetFetch(info->fetch, INT_MIN);
+ }
+ break;
+ case HInductionVarAnalysis::kLinear:
+ // Minimum over linear induction a * i + b, for normalized 0 <= i < TC.
+ return AddValue(GetMul(info->op_a, trip, trip, INT_MIN),
+ GetMin(info->op_b, trip), INT_MIN);
+ case HInductionVarAnalysis::kWrapAround:
+ case HInductionVarAnalysis::kPeriodic:
+ // Minimum over all values in the wrap-around/periodic.
+ return MinValue(GetMin(info->op_a, trip), GetMin(info->op_b, trip));
+ }
+ }
+ return Value(INT_MIN);
+}
+
+InductionVarRange::Value InductionVarRange::GetMax(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip) {
+ if (info != nullptr) {
+ switch (info->induction_class) {
+ case HInductionVarAnalysis::kInvariant:
+ // Invariants.
+ switch (info->operation) {
+ case HInductionVarAnalysis::kNop: // normalized: TC - 1
+ DCHECK_EQ(info->op_a, info->op_b);
+ return SubValue(GetMax(info->op_b, trip), Value(1), INT_MAX);
+ case HInductionVarAnalysis::kAdd:
+ return AddValue(GetMax(info->op_a, trip), GetMax(info->op_b, trip), INT_MAX);
+ case HInductionVarAnalysis::kSub: // second min!
+ return SubValue(GetMax(info->op_a, trip), GetMin(info->op_b, trip), INT_MAX);
+ case HInductionVarAnalysis::kNeg: // second min!
+ return SubValue(Value(0), GetMin(info->op_b, trip), INT_MAX);
+ case HInductionVarAnalysis::kMul:
+ return GetMul(info->op_a, info->op_b, trip, INT_MAX);
+ case HInductionVarAnalysis::kDiv:
+ return GetDiv(info->op_a, info->op_b, trip, INT_MAX);
+ case HInductionVarAnalysis::kFetch:
+ return GetFetch(info->fetch, INT_MAX);
+ }
+ break;
+ case HInductionVarAnalysis::kLinear:
+ // Maximum over linear induction a * i + b, for normalized 0 <= i < TC.
+ return AddValue(GetMul(info->op_a, trip, trip, INT_MAX),
+ GetMax(info->op_b, trip), INT_MAX);
+ case HInductionVarAnalysis::kWrapAround:
+ case HInductionVarAnalysis::kPeriodic:
+ // Maximum over all values in the wrap-around/periodic.
+ return MaxValue(GetMax(info->op_a, trip), GetMax(info->op_b, trip));
+ }
+ }
+ return Value(INT_MAX);
+}
+
+InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1,
+ HInductionVarAnalysis::InductionInfo* info2,
+ HInductionVarAnalysis::InductionInfo* trip,
+ int32_t fail_value) {
+ Value v1_min = GetMin(info1, trip);
+ Value v1_max = GetMax(info1, trip);
+ Value v2_min = GetMin(info2, trip);
+ Value v2_max = GetMax(info2, trip);
+ if (v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
+ // Positive range vs. positive or negative range.
+ if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
+ return (fail_value < 0) ? MulValue(v1_min, v2_min, fail_value)
+ : MulValue(v1_max, v2_max, fail_value);
+ } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
+ return (fail_value < 0) ? MulValue(v1_max, v2_min, fail_value)
+ : MulValue(v1_min, v2_max, fail_value);
+ }
+ } else if (v1_min.a_constant == 0 && v1_min.b_constant <= 0) {
+ // Negative range vs. positive or negative range.
+ if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
+ return (fail_value < 0) ? MulValue(v1_min, v2_max, fail_value)
+ : MulValue(v1_max, v2_min, fail_value);
+ } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
+ return (fail_value < 0) ? MulValue(v1_max, v2_max, fail_value)
+ : MulValue(v1_min, v2_min, fail_value);
+ }
+ }
+ return Value(fail_value);
+}
+
+InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1,
+ HInductionVarAnalysis::InductionInfo* info2,
+ HInductionVarAnalysis::InductionInfo* trip,
+ int32_t fail_value) {
+ Value v1_min = GetMin(info1, trip);
+ Value v1_max = GetMax(info1, trip);
+ Value v2_min = GetMin(info2, trip);
+ Value v2_max = GetMax(info2, trip);
+ if (v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
+ // Positive range vs. positive or negative range.
+ if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
+ return (fail_value < 0) ? DivValue(v1_min, v2_max, fail_value)
+ : DivValue(v1_max, v2_min, fail_value);
+ } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
+ return (fail_value < 0) ? DivValue(v1_max, v2_max, fail_value)
+ : DivValue(v1_min, v2_min, fail_value);
+ }
+ } else if (v1_min.a_constant == 0 && v1_min.b_constant <= 0) {
+ // Negative range vs. positive or negative range.
+ if (v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
+ return (fail_value < 0) ? DivValue(v1_min, v2_min, fail_value)
+ : DivValue(v1_max, v2_max, fail_value);
+ } else if (v2_max.a_constant == 0 && v2_max.b_constant <= 0) {
+ return (fail_value < 0) ? DivValue(v1_max, v2_min, fail_value)
+ : DivValue(v1_min, v2_max, fail_value);
+ }
+ }
+ return Value(fail_value);
+}
+
+InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2, int32_t fail_value) {
+ if (IsSafeAdd(v1.b_constant, v2.b_constant)) {
+ const int32_t b = v1.b_constant + v2.b_constant;
+ if (v1.a_constant == 0) {
+ return Value(v2.instruction, v2.a_constant, b);
+ } else if (v2.a_constant == 0) {
+ return Value(v1.instruction, v1.a_constant, b);
+ } else if (v1.instruction == v2.instruction && IsSafeAdd(v1.a_constant, v2.a_constant)) {
+ return Value(v1.instruction, v1.a_constant + v2.a_constant, b);
+ }
+ }
+ return Value(fail_value);
+}
+
+InductionVarRange::Value InductionVarRange::SubValue(Value v1, Value v2, int32_t fail_value) {
+ if (IsSafeSub(v1.b_constant, v2.b_constant)) {
+ const int32_t b = v1.b_constant - v2.b_constant;
+ if (v1.a_constant == 0 && IsSafeSub(0, v2.a_constant)) {
+ return Value(v2.instruction, -v2.a_constant, b);
+ } else if (v2.a_constant == 0) {
+ return Value(v1.instruction, v1.a_constant, b);
+ } else if (v1.instruction == v2.instruction && IsSafeSub(v1.a_constant, v2.a_constant)) {
+ return Value(v1.instruction, v1.a_constant - v2.a_constant, b);
+ }
+ }
+ return Value(fail_value);
+}
+
+InductionVarRange::Value InductionVarRange::MulValue(Value v1, Value v2, int32_t fail_value) {
+ if (v1.a_constant == 0) {
+ if (IsSafeMul(v1.b_constant, v2.a_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
+ return Value(v2.instruction, v1.b_constant * v2.a_constant, v1.b_constant * v2.b_constant);
+ }
+ } else if (v2.a_constant == 0) {
+ if (IsSafeMul(v1.a_constant, v2.b_constant) && IsSafeMul(v1.b_constant, v2.b_constant)) {
+ return Value(v1.instruction, v1.a_constant * v2.b_constant, v1.b_constant * v2.b_constant);
+ }
+ }
+ return Value(fail_value);
+}
+
+InductionVarRange::Value InductionVarRange::DivValue(Value v1, Value v2, int32_t fail_value) {
+ if (v1.a_constant == 0 && v2.a_constant == 0) {
+ if (IsSafeDiv(v1.b_constant, v2.b_constant)) {
+ return Value(v1.b_constant / v2.b_constant);
+ }
+ }
+ return Value(fail_value);
+}
+
+InductionVarRange::Value InductionVarRange::MinValue(Value v1, Value v2) {
+ if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) {
+ return Value(v1.instruction, v1.a_constant, std::min(v1.b_constant, v2.b_constant));
+ }
+ return Value(INT_MIN);
+}
+
+InductionVarRange::Value InductionVarRange::MaxValue(Value v1, Value v2) {
+ if (v1.instruction == v2.instruction && v1.a_constant == v2.a_constant) {
+ return Value(v1.instruction, v1.a_constant, std::max(v1.b_constant, v2.b_constant));
+ }
+ return Value(INT_MAX);
+}
+
+} // namespace art
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
new file mode 100644
index 0000000..b079076
--- /dev/null
+++ b/compiler/optimizing/induction_var_range.h
@@ -0,0 +1,103 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_
+#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_
+
+#include "induction_var_analysis.h"
+
+namespace art {
+
+/**
+ * This class implements induction variable based range analysis on expressions within loops.
+ * It takes the results of induction variable analysis in the constructor and provides a public
+ * API to obtain a conservative lower and upper bound value on each instruction in the HIR.
+ *
+ * For example, given a linear induction 2 * i + x where 0 <= i <= 10, range analysis yields lower
+ * bound value x and upper bound value x + 20 for the expression, thus, the range [0, x + 20].
+ */
+class InductionVarRange {
+ public:
+ /*
+ * A value that can be represented as "a * instruction + b" for 32-bit constants, where
+ * Value(INT_MIN) and Value(INT_MAX) denote an unknown lower and upper bound, respectively.
+ * Although range analysis could yield more complex values, the format is sufficiently powerful
+ * to represent useful cases and feeds directly into optimizations like bounds check elimination.
+ */
+ struct Value {
+ Value(HInstruction* i, int32_t a, int32_t b)
+ : instruction(a ? i : nullptr),
+ a_constant(a),
+ b_constant(b) {}
+ explicit Value(int32_t b) : Value(nullptr, 0, b) {}
+ HInstruction* instruction;
+ int32_t a_constant;
+ int32_t b_constant;
+ };
+
+ explicit InductionVarRange(HInductionVarAnalysis* induction);
+
+ /**
+ * Given a context denoted by the first instruction, returns a,
+ * possibly conservative, lower bound on the instruction's value.
+ */
+ Value GetMinInduction(HInstruction* context, HInstruction* instruction);
+
+ /**
+ * Given a context denoted by the first instruction, returns a,
+ * possibly conservative, upper bound on the instruction's value.
+ */
+ Value GetMaxInduction(HInstruction* context, HInstruction* instruction);
+
+ private:
+ //
+ // Private helper methods.
+ //
+
+ HInductionVarAnalysis::InductionInfo* GetTripCount(HLoopInformation* loop,
+ HInstruction* context);
+
+ static Value GetFetch(HInstruction* instruction, int32_t fail_value);
+
+ static Value GetMin(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip);
+ static Value GetMax(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip);
+ static Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
+ HInductionVarAnalysis::InductionInfo* info2,
+ HInductionVarAnalysis::InductionInfo* trip, int32_t fail_value);
+ static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
+ HInductionVarAnalysis::InductionInfo* info2,
+ HInductionVarAnalysis::InductionInfo* trip, int32_t fail_value);
+
+ static Value AddValue(Value v1, Value v2, int32_t fail_value);
+ static Value SubValue(Value v1, Value v2, int32_t fail_value);
+ static Value MulValue(Value v1, Value v2, int32_t fail_value);
+ static Value DivValue(Value v1, Value v2, int32_t fail_value);
+ static Value MinValue(Value v1, Value v2);
+ static Value MaxValue(Value v1, Value v2);
+
+ /** Results of prior induction variable analysis. */
+ HInductionVarAnalysis *induction_analysis_;
+
+ friend class InductionVarRangeTest;
+
+ DISALLOW_COPY_AND_ASSIGN(InductionVarRange);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
new file mode 100644
index 0000000..d3c3518
--- /dev/null
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -0,0 +1,341 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <limits.h>
+
+#include "base/arena_allocator.h"
+#include "builder.h"
+#include "gtest/gtest.h"
+#include "induction_var_analysis.h"
+#include "induction_var_range.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+
+namespace art {
+
+using Value = InductionVarRange::Value;
+
+/**
+ * Fixture class for the InductionVarRange tests.
+ */
+class InductionVarRangeTest : public testing::Test {
+ public:
+ InductionVarRangeTest() : pool_(), allocator_(&pool_) {
+ graph_ = CreateGraph(&allocator_);
+ iva_ = new (&allocator_) HInductionVarAnalysis(graph_);
+ BuildGraph();
+ }
+
+ ~InductionVarRangeTest() { }
+
+ void ExpectEqual(Value v1, Value v2) {
+ EXPECT_EQ(v1.instruction, v2.instruction);
+ EXPECT_EQ(v1.a_constant, v2.a_constant);
+ EXPECT_EQ(v1.b_constant, v2.b_constant);
+ }
+
+ /** Constructs bare minimum graph. */
+ void BuildGraph() {
+ graph_->SetNumberOfVRegs(1);
+ HBasicBlock* entry_block = new (&allocator_) HBasicBlock(graph_);
+ HBasicBlock* exit_block = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry_block);
+ graph_->AddBlock(exit_block);
+ graph_->SetEntryBlock(entry_block);
+ graph_->SetExitBlock(exit_block);
+ }
+
+ /** Constructs an invariant. */
+ HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc,
+ HInductionVarAnalysis::InductionInfo* a,
+ HInductionVarAnalysis::InductionInfo* b) {
+ HInductionVarAnalysis::InductionOp op;
+ switch (opc) {
+ case '+': op = HInductionVarAnalysis::kAdd; break;
+ case '-': op = HInductionVarAnalysis::kSub; break;
+ case 'n': op = HInductionVarAnalysis::kNeg; break;
+ case '*': op = HInductionVarAnalysis::kMul; break;
+ case '/': op = HInductionVarAnalysis::kDiv; break;
+ default: op = HInductionVarAnalysis::kNop; break;
+ }
+ return iva_->CreateInvariantOp(op, a, b);
+ }
+
+ /** Constructs a fetch. */
+ HInductionVarAnalysis::InductionInfo* CreateFetch(HInstruction* fetch) {
+ return iva_->CreateInvariantFetch(fetch);
+ }
+
+ /** Constructs a constant. */
+ HInductionVarAnalysis::InductionInfo* CreateConst(int32_t c) {
+ return CreateFetch(graph_->GetIntConstant(c));
+ }
+
+ /** Constructs a trip-count. */
+ HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc) {
+ HInductionVarAnalysis::InductionInfo* trip = CreateConst(tc);
+ return CreateInvariant('@', trip, trip);
+ }
+
+ /** Constructs a linear a * i + b induction. */
+ HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) {
+ return iva_->CreateInduction(HInductionVarAnalysis::kLinear, CreateConst(a), CreateConst(b));
+ }
+
+ /** Constructs a range [lo, hi] using a periodic induction. */
+ HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) {
+ return iva_->CreateInduction(
+ HInductionVarAnalysis::kPeriodic, CreateConst(lo), CreateConst(hi));
+ }
+
+ /** Constructs a wrap-around induction consisting of a constant, followed by a range. */
+ HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) {
+ return iva_->CreateInduction(
+ HInductionVarAnalysis::kWrapAround, CreateConst(initial), CreateRange(lo, hi));
+ }
+
+ //
+ // Relay methods.
+ //
+
+ Value GetMin(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* induc) {
+ return InductionVarRange::GetMin(info, induc);
+ }
+
+ Value GetMax(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* induc) {
+ return InductionVarRange::GetMax(info, induc);
+ }
+
+ Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
+ HInductionVarAnalysis::InductionInfo* info2, int32_t fail_value) {
+ return InductionVarRange::GetMul(info1, info2, nullptr, fail_value);
+ }
+
+ Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
+ HInductionVarAnalysis::InductionInfo* info2, int32_t fail_value) {
+ return InductionVarRange::GetDiv(info1, info2, nullptr, fail_value);
+ }
+
+ Value AddValue(Value v1, Value v2) { return InductionVarRange::AddValue(v1, v2, INT_MIN); }
+ Value SubValue(Value v1, Value v2) { return InductionVarRange::SubValue(v1, v2, INT_MIN); }
+ Value MulValue(Value v1, Value v2) { return InductionVarRange::MulValue(v1, v2, INT_MIN); }
+ Value DivValue(Value v1, Value v2) { return InductionVarRange::DivValue(v1, v2, INT_MIN); }
+ Value MinValue(Value v1, Value v2) { return InductionVarRange::MinValue(v1, v2); }
+ Value MaxValue(Value v1, Value v2) { return InductionVarRange::MaxValue(v1, v2); }
+
+ // General building fields.
+ ArenaPool pool_;
+ ArenaAllocator allocator_;
+ HGraph* graph_;
+ HInductionVarAnalysis* iva_;
+
+ // Two dummy instructions.
+ HReturnVoid x_;
+ HReturnVoid y_;
+};
+
+//
+// The actual InductionVarRange tests.
+//
+
+TEST_F(InductionVarRangeTest, GetMinMaxNull) {
+ ExpectEqual(Value(INT_MIN), GetMin(nullptr, nullptr));
+ ExpectEqual(Value(INT_MAX), GetMax(nullptr, nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxAdd) {
+ ExpectEqual(Value(12),
+ GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
+ ExpectEqual(Value(22),
+ GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr));
+ ExpectEqual(Value(&x_, 1, -20),
+ GetMin(CreateInvariant('+', CreateFetch(&x_), CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(&x_, 1, -10),
+ GetMax(CreateInvariant('+', CreateFetch(&x_), CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(&x_, 1, 10),
+ GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(&x_)), nullptr));
+ ExpectEqual(Value(&x_, 1, 20),
+ GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(&x_)), nullptr));
+ ExpectEqual(Value(5),
+ GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
+ ExpectEqual(Value(19),
+ GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxSub) {
+ ExpectEqual(Value(-18),
+ GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
+ ExpectEqual(Value(-8),
+ GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr));
+ ExpectEqual(Value(&x_, 1, 10),
+ GetMin(CreateInvariant('-', CreateFetch(&x_), CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(&x_, 1, 20),
+ GetMax(CreateInvariant('-', CreateFetch(&x_), CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(&x_, -1, 10),
+ GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(&x_)), nullptr));
+ ExpectEqual(Value(&x_, -1, 20),
+ GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(&x_)), nullptr));
+ ExpectEqual(Value(-25),
+ GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
+ ExpectEqual(Value(-11),
+ GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxNeg) {
+ ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr));
+ ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr));
+ ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr));
+ ExpectEqual(Value(&x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(&x_)), nullptr));
+ ExpectEqual(Value(&x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(&x_)), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxMul) {
+ ExpectEqual(Value(20),
+ GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr));
+ ExpectEqual(Value(40),
+ GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxDiv) {
+ ExpectEqual(Value(3),
+ GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr));
+ ExpectEqual(Value(5),
+ GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxConstant) {
+ ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr));
+ ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxFetch) {
+ ExpectEqual(Value(&x_, 1, 0), GetMin(CreateFetch(&x_), nullptr));
+ ExpectEqual(Value(&x_, 1, 0), GetMax(CreateFetch(&x_), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxLinear) {
+ ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100)));
+ ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100)));
+ ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100)));
+ ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100)));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) {
+ ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr));
+ ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr));
+ ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr));
+ ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr));
+ ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr));
+ ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) {
+ ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr));
+ ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr));
+}
+
+TEST_F(InductionVarRangeTest, GetMulMin) {
+ ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), INT_MIN));
+ ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), INT_MIN));
+ ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), INT_MIN));
+ ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), INT_MIN));
+}
+
+TEST_F(InductionVarRangeTest, GetMulMax) {
+ ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), INT_MAX));
+ ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), INT_MAX));
+ ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), INT_MAX));
+ ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), INT_MAX));
+}
+
+TEST_F(InductionVarRangeTest, GetDivMin) {
+ ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), INT_MIN));
+ ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), INT_MIN));
+ ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), INT_MIN));
+ ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), INT_MIN));
+}
+
+TEST_F(InductionVarRangeTest, GetDivMax) {
+ ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), INT_MAX));
+ ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), INT_MAX));
+ ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), INT_MAX));
+ ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), INT_MAX));
+}
+
+TEST_F(InductionVarRangeTest, AddValue) {
+ ExpectEqual(Value(110), AddValue(Value(10), Value(100)));
+ ExpectEqual(Value(-5), AddValue(Value(&x_, 1, -4), Value(&x_, -1, -1)));
+ ExpectEqual(Value(&x_, 3, -5), AddValue(Value(&x_, 2, -4), Value(&x_, 1, -1)));
+ ExpectEqual(Value(INT_MIN), AddValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(&x_, 1, 23), AddValue(Value(&x_, 1, 20), Value(3)));
+ ExpectEqual(Value(&y_, 1, 5), AddValue(Value(55), Value(&y_, 1, -50)));
+ // Unsafe.
+ ExpectEqual(Value(INT_MIN), AddValue(Value(INT_MAX - 5), Value(6)));
+}
+
+TEST_F(InductionVarRangeTest, SubValue) {
+ ExpectEqual(Value(-90), SubValue(Value(10), Value(100)));
+ ExpectEqual(Value(-3), SubValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
+ ExpectEqual(Value(&x_, 2, -3), SubValue(Value(&x_, 3, -4), Value(&x_, 1, -1)));
+ ExpectEqual(Value(INT_MIN), SubValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(&x_, 1, 17), SubValue(Value(&x_, 1, 20), Value(3)));
+ ExpectEqual(Value(&y_, -4, 105), SubValue(Value(55), Value(&y_, 4, -50)));
+ // Unsafe.
+ ExpectEqual(Value(INT_MIN), SubValue(Value(INT_MIN + 5), Value(6)));
+}
+
+TEST_F(InductionVarRangeTest, MulValue) {
+ ExpectEqual(Value(1000), MulValue(Value(10), Value(100)));
+ ExpectEqual(Value(INT_MIN), MulValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
+ ExpectEqual(Value(INT_MIN), MulValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(&x_, 9, 60), MulValue(Value(&x_, 3, 20), Value(3)));
+ ExpectEqual(Value(&y_, 55, -110), MulValue(Value(55), Value(&y_, 1, -2)));
+ // Unsafe.
+ ExpectEqual(Value(INT_MIN), MulValue(Value(90000), Value(-90000)));
+}
+
+TEST_F(InductionVarRangeTest, DivValue) {
+ ExpectEqual(Value(25), DivValue(Value(100), Value(4)));
+ ExpectEqual(Value(INT_MIN), DivValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
+ ExpectEqual(Value(INT_MIN), DivValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(INT_MIN), DivValue(Value(&x_, 12, 24), Value(3)));
+ ExpectEqual(Value(INT_MIN), DivValue(Value(55), Value(&y_, 1, -50)));
+ // Unsafe.
+ ExpectEqual(Value(INT_MIN), DivValue(Value(1), Value(0)));
+}
+
+TEST_F(InductionVarRangeTest, MinValue) {
+ ExpectEqual(Value(10), MinValue(Value(10), Value(100)));
+ ExpectEqual(Value(&x_, 1, -4), MinValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
+ ExpectEqual(Value(&x_, 4, -4), MinValue(Value(&x_, 4, -4), Value(&x_, 4, -1)));
+ ExpectEqual(Value(INT_MIN), MinValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(INT_MIN), MinValue(Value(&x_, 1, 20), Value(3)));
+ ExpectEqual(Value(INT_MIN), MinValue(Value(55), Value(&y_, 1, -50)));
+}
+
+TEST_F(InductionVarRangeTest, MaxValue) {
+ ExpectEqual(Value(100), MaxValue(Value(10), Value(100)));
+ ExpectEqual(Value(&x_, 1, -1), MaxValue(Value(&x_, 1, -4), Value(&x_, 1, -1)));
+ ExpectEqual(Value(&x_, 4, -1), MaxValue(Value(&x_, 4, -4), Value(&x_, 4, -1)));
+ ExpectEqual(Value(INT_MAX), MaxValue(Value(&x_, 1, 5), Value(&y_, 1, -7)));
+ ExpectEqual(Value(INT_MAX), MaxValue(Value(&x_, 1, 20), Value(3)));
+ ExpectEqual(Value(INT_MAX), MaxValue(Value(55), Value(&y_, 1, -50)));
+}
+
+} // namespace art