Various improvements in finding induction variables.
Rationale:
(1) Analyze multi-way phis (requested by Nicolas, Igor, and Mingyao).
(2) Analyze trip count for restricted != loops
(3) Added unit test for public API of range analysis (static methods
were already well-tested).
Change-Id: I9285d22d3bb927f141204cc4697ea6fe5120994d
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 92c732c..1ff6bbe 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -33,17 +33,6 @@
}
/**
- * Returns true if instruction is proper entry-phi-operation for given loop
- * (referred to as mu-operation in Gerlek's paper).
- */
-static bool IsEntryPhi(HLoopInformation* loop, HInstruction* instruction) {
- return
- instruction->IsPhi() &&
- instruction->InputCount() == 2 &&
- instruction->GetBlock() == loop->GetHeader();
-}
-
-/**
* Since graph traversal may enter a SCC at any position, an initial representation may be rotated,
* along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming
* a chain of dependences (mutual independent items may occur in arbitrary order). For proper
@@ -58,8 +47,9 @@
size_t phi_pos = -1;
const size_t size = scc->size();
for (size_t i = 0; i < size; i++) {
- if (IsEntryPhi(loop, scc->at(i)) && (phi == nullptr || phis.FoundBefore(scc->at(i), phi))) {
- phi = scc->at(i);
+ HInstruction* other = scc->at(i);
+ if (other->IsLoopHeaderPhi() && (phi == nullptr || phis.FoundBefore(other, phi))) {
+ phi = other;
phi_pos = i;
}
}
@@ -168,7 +158,7 @@
}
// Classify the SCC.
- if (scc_.size() == 1 && !IsEntryPhi(loop, scc_[0])) {
+ if (scc_.size() == 1 && !scc_[0]->IsLoopHeaderPhi()) {
ClassifyTrivial(loop, scc_[0]);
} else {
ClassifyNonTrivial(loop);
@@ -200,10 +190,7 @@
void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
InductionInfo* info = nullptr;
if (instruction->IsPhi()) {
- for (size_t i = 1, count = instruction->InputCount(); i < count; i++) {
- info = TransferPhi(LookupInfo(loop, instruction->InputAt(0)),
- LookupInfo(loop, instruction->InputAt(i)));
- }
+ info = TransferPhi(loop, instruction, /* input_index */ 0);
} else if (instruction->IsAdd()) {
info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, instruction->InputAt(1)), kAdd);
@@ -245,21 +232,21 @@
RotateEntryPhiFirst(loop, &scc_, &other);
}
- // Analyze from phi onwards.
+ // Analyze from entry-phi onwards.
HInstruction* phi = scc_[0];
- if (!IsEntryPhi(loop, phi)) {
+ if (!phi->IsLoopHeaderPhi()) {
return;
}
- HInstruction* external = phi->InputAt(0);
- HInstruction* internal = phi->InputAt(1);
- InductionInfo* initial = LookupInfo(loop, external);
+
+ // External link should be loop invariant.
+ InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
if (initial == nullptr || initial->induction_class != kInvariant) {
return;
}
- // Singleton entry-phi-operation may be a wrap-around induction.
+ // Singleton is wrap-around induction if all internal links have the same meaning.
if (size == 1) {
- InductionInfo* update = LookupInfo(loop, internal);
+ InductionInfo* update = TransferPhi(loop, phi, /* input_index */ 1);
if (update != nullptr) {
AssignInfo(loop, phi, CreateInduction(kWrapAround, initial, update));
}
@@ -272,7 +259,7 @@
HInstruction* instruction = scc_[i];
InductionInfo* update = nullptr;
if (instruction->IsPhi()) {
- update = SolvePhi(loop, phi, instruction);
+ update = SolvePhiAllInputs(loop, phi, instruction);
} else if (instruction->IsAdd()) {
update = SolveAddSub(
loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true);
@@ -286,10 +273,9 @@
cycle_.Put(instruction, update);
}
- // Success if the internal link received a meaning.
- auto it = cycle_.find(internal);
- if (it != cycle_.end()) {
- InductionInfo* induction = it->second;
+ // Success if all internal links received the same temporary meaning.
+ InductionInfo* induction = SolvePhi(phi, /* input_index */ 1);
+ if (induction != nullptr) {
switch (induction->induction_class) {
case kInvariant:
// Classify first phi and then the rest of the cycle "on-demand".
@@ -329,13 +315,20 @@
return CreateInduction(kPeriodic, induction->op_a, RotatePeriodicInduction(induction->op_b, last));
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(InductionInfo* a,
- InductionInfo* b) {
- // Transfer over a phi: if both inputs are identical, result is input.
- if (InductionEqual(a, b)) {
- return a;
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop,
+ HInstruction* phi,
+ size_t input_index) {
+ // Match all phi inputs from input_index onwards exactly.
+ const size_t count = phi->InputCount();
+ DCHECK_LT(input_index, count);
+ InductionInfo* a = LookupInfo(loop, phi->InputAt(input_index));
+ for (size_t i = input_index + 1; i < count; i++) {
+ InductionInfo* b = LookupInfo(loop, phi->InputAt(i));
+ if (!InductionEqual(a, b)) {
+ return nullptr;
+ }
}
- return nullptr;
+ return a;
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
@@ -421,47 +414,56 @@
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HLoopInformation* loop,
- HInstruction* phi,
- HInstruction* instruction) {
- // Solve within a cycle over a phi: identical inputs are combined into that input as result.
- const size_t count = instruction->InputCount();
- DCHECK_GT(count, 0u);
- auto ita = cycle_.find(instruction->InputAt(0));
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HInstruction* phi,
+ size_t input_index) {
+ // Match all phi inputs from input_index onwards exactly.
+ const size_t count = phi->InputCount();
+ DCHECK_LT(input_index, count);
+ auto ita = cycle_.find(phi->InputAt(input_index));
if (ita != cycle_.end()) {
- InductionInfo* a = ita->second;
- for (size_t i = 1; i < count; i++) {
- auto itb = cycle_.find(instruction->InputAt(i));
- if (itb == cycle_.end() || !HInductionVarAnalysis::InductionEqual(a, itb->second)) {
+ for (size_t i = input_index + 1; i < count; i++) {
+ auto itb = cycle_.find(phi->InputAt(i));
+ if (itb == cycle_.end() ||
+ !HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) {
return nullptr;
}
}
- return a;
+ return ita->second;
+ }
+ return nullptr;
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs(
+ HLoopInformation* loop,
+ HInstruction* entry_phi,
+ HInstruction* phi) {
+ // Match all phi inputs.
+ InductionInfo* match = SolvePhi(phi, /* input_index */ 0);
+ if (match != nullptr) {
+ return match;
}
- // Solve within a cycle over another entry-phi: add invariants into a periodic.
- if (IsEntryPhi(loop, instruction)) {
- InductionInfo* a = LookupInfo(loop, instruction->InputAt(0));
+ // Otherwise, try to solve for a periodic seeded from phi onward.
+ // Only tight multi-statement cycles are considered in order to
+ // simplify rotating the periodic during the final classification.
+ if (phi->IsLoopHeaderPhi() && phi->InputCount() == 2) {
+ InductionInfo* a = LookupInfo(loop, phi->InputAt(0));
if (a != nullptr && a->induction_class == kInvariant) {
- if (instruction->InputAt(1) == phi) {
- InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
+ if (phi->InputAt(1) == entry_phi) {
+ InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
return CreateInduction(kPeriodic, a, initial);
}
- auto it = cycle_.find(instruction->InputAt(1));
- if (it != cycle_.end()) {
- InductionInfo* b = it->second;
- if (b->induction_class == kPeriodic) {
- return CreateInduction(kPeriodic, a, b);
- }
+ InductionInfo* b = SolvePhi(phi, /* input_index */ 1);
+ if (b != nullptr && b->induction_class == kPeriodic) {
+ return CreateInduction(kPeriodic, a, b);
}
}
}
-
return nullptr;
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop,
- HInstruction* phi,
+ HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
HInstruction* y,
@@ -471,7 +473,7 @@
// invariant value, seeded from phi, keeps adding to the stride of the induction.
InductionInfo* b = LookupInfo(loop, y);
if (b != nullptr && b->induction_class == kInvariant) {
- if (x == phi) {
+ if (x == entry_phi) {
return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b);
}
auto it = cycle_.find(x);
@@ -487,14 +489,15 @@
if (op == kAdd) {
// Try the other way around for an addition if considered for first time.
if (is_first_call) {
- return SolveAddSub(loop, phi, instruction, y, x, op, false);
+ return SolveAddSub(loop, entry_phi, instruction, y, x, op, false);
}
} else if (op == kSub) {
- // Solve within a tight cycle for a periodic idiom k = c - k;
- if (y == phi && instruction == phi->InputAt(1)) {
+ // Solve within a tight cycle that is formed by exactly two instructions,
+ // one phi and one update, for a periodic idiom of the form k = c - k;
+ if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
InductionInfo* a = LookupInfo(loop, x);
if (a != nullptr && a->induction_class == kInvariant) {
- InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
+ InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
return CreateInduction(kPeriodic, CreateInvariantOp(kSub, a, initial), initial);
}
}
@@ -539,32 +542,47 @@
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).
+ // Swap condition if induction is at right-hand-side (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;
+ case kCondNE: VisitCondition(loop, b, a, type, kCondNE); 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
+ // Analyze condition with induction at left-hand-side (e.g. i < U).
InductionInfo* stride = a->op_a;
InductionInfo* lo_val = a->op_b;
InductionInfo* hi_val = b;
- // Analyze the stride thoroughly, since its representation may be compound at this point.
+ // Analyze stride (may be compound).
InductionVarRange::Value v1 = InductionVarRange::GetMin(stride, nullptr);
InductionVarRange::Value v2 = InductionVarRange::GetMax(stride, nullptr);
- if (v1.a_constant == 0 && v2.a_constant == 0 && v1.b_constant == v2.b_constant) {
- const int32_t stride_value = v1.b_constant;
- if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
- (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
- bool is_strict = cmp == kCondLT || cmp == kCondGT;
- VisitTripCount(loop, lo_val, hi_val, stride, stride_value, type, is_strict);
+ if (v1.a_constant != 0 || v2.a_constant != 0 || v1.b_constant != v2.b_constant) {
+ return;
+ }
+ // Rewrite safe condition i != U with unit stride into i < U or i > U
+ // (unit stride guarantees that the end condition is always reached).
+ const int32_t stride_value = v1.b_constant;
+ int64_t lo_value = 0;
+ int64_t hi_value = 0;
+ if (cmp == kCondNE && IsIntAndGet(lo_val, &lo_value) && IsIntAndGet(hi_val, &hi_value)) {
+ if ((stride_value == +1 && lo_value < hi_value) ||
+ (stride_value == -1 && lo_value > hi_value)) {
+ cmp = stride_value > 0 ? kCondLT : kCondGT;
}
}
+ // Normalize a linear loop control with a nonzero stride:
+ // stride > 0, either i < U or i <= U
+ // stride < 0, either i > U or i >= U
+ //
+ // TODO: construct conditions for constant/symbolic safety of trip-count
+ //
+ if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
+ (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
+ VisitTripCount(loop, lo_val, hi_val, stride, stride_value, type, cmp);
+ }
}
}
@@ -574,7 +592,7 @@
InductionInfo* stride,
int32_t stride_value,
Primitive::Type type,
- bool is_strict) {
+ IfCondition cmp) {
// Any loop of the general form:
//
// for (i = L; i <= U; i += S) // S > 0
@@ -586,26 +604,27 @@
// 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.
+ // NOTE: The TC (trip-count) expression is only valid when safe. Otherwise TC is 0
+ // (or possibly infinite). Also, the expression assumes the loop does not have
+ // early-exits. Otherwise, TC is an upper bound.
//
- bool cancels = is_strict && std::abs(stride_value) == 1; // compensation cancels conversion?
+ bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1;
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));
+ if (cmp == kCondLT) {
+ hi_val = CreateInvariantOp(kSub, hi_val, CreateConstant(1, type));
+ } else if (cmp == kCondGT) {
+ hi_val = CreateInvariantOp(kAdd, 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 top-test 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.
+ // should be aware that the expression is only valid in the loop-body proper (when symbolically
+ // safe), and not yet in the loop-header (unless constant safe). 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);
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 8eccf92..190a0db 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -121,26 +121,27 @@
uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
void ClassifyNonTrivial(HLoopInformation* loop);
+ InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
// Transfer operations.
- InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b);
+ InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index);
InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type);
InductionInfo* TransferNeg(InductionInfo* a);
// Solvers.
- InductionInfo* SolvePhi(HLoopInformation* loop,
- HInstruction* phi,
- HInstruction* instruction);
+ InductionInfo* SolvePhi(HInstruction* phi, size_t input_index);
+ InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
+ HInstruction* entry_phi,
+ HInstruction* phi);
InductionInfo* SolveAddSub(HLoopInformation* loop,
- HInstruction* phi,
+ HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
HInstruction* y,
InductionOp op,
bool is_first_call);
- InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
// Trip count information.
void VisitControl(HLoopInformation* loop);
@@ -155,7 +156,7 @@
InductionInfo* stride,
int32_t stride_value,
Primitive::Type type,
- bool is_strict);
+ IfCondition cmp);
// Assign and lookup.
void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index fca1ca5..e519e77 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -20,6 +20,7 @@
#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"
@@ -388,7 +389,7 @@
HInstruction* store = InsertArrayStore(induc_, 0);
InsertLocalStore(induc_, InsertLocalLoad(tmp_, 0), 0);
HInstruction *sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
InsertLocalStore(tmp_, sub, 0);
PerformInductionVarAnalysis();
@@ -412,16 +413,16 @@
new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, add, 0);
HInstruction *sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, sub, 0);
HInstruction *mul = InsertInstruction(
- new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, mul, 0);
HInstruction *shl = InsertInstruction(
- new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+ new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
InsertLocalStore(tmp_, shl, 0);
HInstruction *neg = InsertInstruction(
- new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+ new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
InsertLocalStore(tmp_, neg, 0);
InsertLocalStore(
induc_,
@@ -471,7 +472,7 @@
BuildLoopNest(1);
HInstruction* store = InsertArrayStore(induc_, 0);
HInstruction *sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0);
InsertLocalStore(induc_, sub, 0);
PerformInductionVarAnalysis();
@@ -497,19 +498,19 @@
HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0), 0);
// Derived expressions.
HInstruction *add = InsertInstruction(
- new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, add, 0);
HInstruction *sub = InsertInstruction(
- new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, sub, 0);
HInstruction *mul = InsertInstruction(
- new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HMul(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(tmp_, mul, 0);
HInstruction *shl = InsertInstruction(
- new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+ new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
InsertLocalStore(tmp_, shl, 0);
HInstruction *neg = InsertInstruction(
- new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+ new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
InsertLocalStore(tmp_, neg, 0);
PerformInductionVarAnalysis();
@@ -520,6 +521,34 @@
EXPECT_STREQ("periodic(( - (1)), (0))", GetInductionInfo(neg, 0).c_str());
}
+TEST_F(InductionVarAnalysisTest, FindRange) {
+ // Setup:
+ // for (int i = 0; i < 100; i++) {
+ // k = i << 1;
+ // k = k + 1;
+ // a[k] = 0;
+ // }
+ BuildLoopNest(1);
+ HInstruction *shl = InsertInstruction(
+ new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0), constant1_), 0);
+ InsertLocalStore(induc_, shl, 0);
+ HInstruction *add = InsertInstruction(
+ new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+ InsertLocalStore(induc_, add, 0);
+ HInstruction* store = InsertArrayStore(induc_, 0);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("((2) * i + (1))", GetInductionInfo(store->InputAt(1), 0).c_str());
+
+ InductionVarRange range(iva_);
+ InductionVarRange::Value v_min = range.GetMinInduction(store, store->InputAt(1));
+ InductionVarRange::Value v_max = range.GetMaxInduction(store, store->InputAt(1));
+ EXPECT_EQ(0, v_min.a_constant);
+ EXPECT_EQ(1, v_min.b_constant);
+ EXPECT_EQ(0, v_max.a_constant);
+ EXPECT_EQ(199, v_max.b_constant);
+}
+
TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
// Setup:
// k = 0;
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
index e518a61..1c5b5d6 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -62,6 +62,19 @@
return result;
}
+ /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearVeryObscure(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; i++) {
+ int k = (-i) + (i << 5) + i - (32 * i) + 5 + (int) i;
+ result += x[k - 5];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.linearWhile(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWhile(int[]) BCE (after)
@@ -75,6 +88,42 @@
return result;
}
+ /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearThreeWayPhi(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; ) {
+ if (x[i] == 5) {
+ i++;
+ continue;
+ }
+ result += x[i++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearFourWayPhi(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; ) {
+ if (x[i] == 5) {
+ i++;
+ continue;
+ } else if (x[i] == 6) {
+ i++;
+ result += 7;
+ continue;
+ }
+ result += x[i++];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after)
@@ -90,6 +139,25 @@
return result;
}
+ /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int wrapAroundThenLinearThreeWayPhi(int[] x) {
+ // Loop with wrap around (length - 1, 0, 1, 2, ..).
+ int w = x.length - 1;
+ int result = 0;
+ for (int i = 0; i < x.length; ) {
+ if (x[w] == 1) {
+ w = i++;
+ continue;
+ }
+ result += x[w];
+ w = i++;
+ }
+ return result;
+ }
+
/// CHECK-START: int[] Main.linearWithParameter(int) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int[] Main.linearWithParameter(int) BCE (after)
@@ -102,6 +170,19 @@
return x;
}
+ /// CHECK-START: int[] Main.linearCopy(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int[] Main.linearCopy(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int[] linearCopy(int x[]) {
+ int n = x.length;
+ int y[] = new int[n];
+ for (int i = 0; i < n; i++) {
+ y[i] = x[i];
+ }
+ return y;
+ }
+
/// CHECK-START: int Main.linearWithCompoundStride() BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWithCompoundStride() BCE (after)
@@ -126,7 +207,7 @@
int result = 0;
int k = 0;
// Range analysis has no problem with a trip-count defined by a
- // reasonably large positive stride.
+ // reasonably large positive stride far away from upper bound.
for (int i = 1; i <= 10 * 10000000 + 1; i += 10000000) {
result += x[k++];
}
@@ -143,7 +224,7 @@
int k = 0;
// Range analysis conservatively bails due to potential of wrap-around
// arithmetic while computing the trip-count for this very large stride.
- for (int i = 1; i < 2147483647; i += 195225786) {
+ for (int i = 1; i < Integer.MAX_VALUE; i += 195225786) {
result += x[k++];
}
return result;
@@ -158,7 +239,7 @@
int result = 0;
int k = 0;
// Range analysis has no problem with a trip-count defined by a
- // reasonably large negative stride.
+ // reasonably large negative stride far away from lower bound.
for (int i = -1; i >= -10 * 10000000 - 1; i -= 10000000) {
result += x[k++];
}
@@ -175,12 +256,54 @@
int k = 0;
// Range analysis conservatively bails due to potential of wrap-around
// arithmetic while computing the trip-count for this very large stride.
- for (int i = -2; i > -2147483648; i -= 195225786) {
+ for (int i = -2; i > Integer.MIN_VALUE; i -= 195225786) {
result += x[k++];
}
return result;
}
+ /// CHECK-START: int Main.linearForNE() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearForNE() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearForNE() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = 0; i != 10; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearDoWhile() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearDoWhile() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int linearDoWhile() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ int i = 0;
+ // TODO: make this work
+ do {
+ result += x[i++];
+ } while (i < 10);
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearShort() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearShort() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int linearShort() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ // TODO: make this work
+ for (short i = 0; i < 10; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.periodicIdiom(int) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.periodicIdiom(int) BCE (after)
@@ -242,6 +365,112 @@
return result;
}
+ /// CHECK-START: int Main.justRightUp1() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightUp1() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightUp1() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MAX_VALUE - 10, k = 0; i < Integer.MAX_VALUE; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightUp2() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightUp2() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightUp2() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MAX_VALUE - 10; i < Integer.MAX_VALUE; i++) {
+ result += x[i - Integer.MAX_VALUE + 10];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightUp3() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightUp3() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightUp3() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MAX_VALUE - 10, k = 0; i <= Integer.MAX_VALUE - 1; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justOOBUp() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justOOBUp() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int justOOBUp() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ // Infinite loop!
+ for (int i = Integer.MAX_VALUE - 9, k = 0; i <= Integer.MAX_VALUE; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightDown1() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightDown1() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightDown1() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MIN_VALUE + 10, k = 0; i > Integer.MIN_VALUE; i--) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightDown2() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightDown2() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightDown2() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MIN_VALUE + 10; i > Integer.MIN_VALUE; i--) {
+ result += x[Integer.MAX_VALUE + i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightDown3() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightDown3() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightDown3() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MIN_VALUE + 10, k = 0; i >= Integer.MIN_VALUE + 1; i--) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justOOBDown() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justOOBDown() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int justOOBDown() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ // Infinite loop!
+ for (int i = Integer.MIN_VALUE + 9, k = 0; i >= Integer.MIN_VALUE; i--) {
+ result += x[k++];
+ }
+ return result;
+ }
+
//
// Cases that actually go out of bounds. These test cases
// ensure the exceptions are thrown at the right places.
@@ -274,10 +503,18 @@
expectEquals(55, linearDown(x));
expectEquals(0, linearObscure(empty));
expectEquals(55, linearObscure(x));
+ expectEquals(0, linearVeryObscure(empty));
+ expectEquals(55, linearVeryObscure(x));
expectEquals(0, linearWhile(empty));
expectEquals(55, linearWhile(x));
+ expectEquals(0, linearThreeWayPhi(empty));
+ expectEquals(50, linearThreeWayPhi(x));
+ expectEquals(0, linearFourWayPhi(empty));
+ expectEquals(51, linearFourWayPhi(x));
expectEquals(0, wrapAroundThenLinear(empty));
expectEquals(55, wrapAroundThenLinear(x));
+ expectEquals(0, wrapAroundThenLinearThreeWayPhi(empty));
+ expectEquals(54, wrapAroundThenLinearThreeWayPhi(x));
// Linear with parameter.
sResult = 0;
@@ -295,6 +532,16 @@
}
}
+ // Linear copy.
+ expectEquals(0, linearCopy(empty).length);
+ {
+ int[] r = linearCopy(x);
+ expectEquals(x.length, r.length);
+ for (int i = 0; i < x.length; i++) {
+ expectEquals(x[i], r[i]);
+ }
+ }
+
// Linear with non-unit strides.
expectEquals(56, linearWithCompoundStride());
expectEquals(66, linearWithLargePositiveStride());
@@ -302,6 +549,11 @@
expectEquals(66, linearWithLargeNegativeStride());
expectEquals(66, linearWithVeryLargeNegativeStride());
+ // Special forms.
+ expectEquals(55, linearForNE());
+ expectEquals(55, linearDoWhile());
+ expectEquals(55, linearShort());
+
// Periodic adds (1, 3), one at the time.
expectEquals(0, periodicIdiom(-1));
for (int tc = 0; tc < 32; tc++) {
@@ -326,6 +578,28 @@
expectEquals(tc * 16, periodicSequence4(tc));
}
+ // Large bounds.
+ expectEquals(55, justRightUp1());
+ expectEquals(55, justRightUp2());
+ expectEquals(55, justRightUp3());
+ expectEquals(55, justRightDown1());
+ expectEquals(55, justRightDown2());
+ expectEquals(55, justRightDown3());
+ sResult = 0;
+ try {
+ justOOBUp();
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult = 1;
+ }
+ expectEquals(1, sResult);
+ sResult = 0;
+ try {
+ justOOBDown();
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult = 1;
+ }
+ expectEquals(1, sResult);
+
// Lower bound goes OOB.
sResult = 0;
try {
