Further development of induction variable analysis.
Various improvements:
(1) Introduced period sequences.
(2) Extended all transfer functions to deal with all cases;
also refactored these to read more compactly.
(3) Improved debugging output for constants for readability.
(4) Used direct pointer in mappings for clarify.
(5) Several induction info "constructors" for readability.
(6) Various other changes suggested in earlier code reviews.
Change-Id: I9d5381f1676b63d30cea6f5e304d4b7bda7acb96
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 8aaec68..8b38414 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -42,6 +42,33 @@
instruction->GetBlock() == loop->GetHeader();
}
+/**
+ * Returns true for 32/64-bit integral constant, passing its value as output parameter.
+ */
+static bool IsIntAndGet(HInstruction* instruction, int64_t* value) {
+ if (instruction->IsIntConstant()) {
+ *value = instruction->AsIntConstant()->GetValue();
+ return true;
+ } else if (instruction->IsLongConstant()) {
+ *value = instruction->AsLongConstant()->GetValue();
+ return true;
+ }
+ return false;
+}
+
+/**
+ * Returns a string representation of an instruction
+ * (for testing and debugging only).
+ */
+static std::string InstructionToString(HInstruction* instruction) {
+ if (instruction->IsIntConstant()) {
+ return std::to_string(instruction->AsIntConstant()->GetValue());
+ } else if (instruction->IsLongConstant()) {
+ return std::to_string(instruction->AsLongConstant()->GetValue()) + "L";
+ }
+ return std::to_string(instruction->GetId()) + ":" + instruction->DebugName();
+}
+
//
// Class methods.
//
@@ -51,14 +78,15 @@
global_depth_(0),
stack_(graph->GetArena()->Adapter()),
scc_(graph->GetArena()->Adapter()),
- map_(std::less<int>(), graph->GetArena()->Adapter()),
- cycle_(std::less<int>(), graph->GetArena()->Adapter()),
- induction_(std::less<int>(), graph->GetArena()->Adapter()) {
+ map_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
+ cycle_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
+ induction_(std::less<HLoopInformation*>(), graph->GetArena()->Adapter()) {
}
void HInductionVarAnalysis::Run() {
- // Detects sequence variables (generalized induction variables) during an
- // inner-loop-first traversal of all loops using Gerlek's algorithm.
+ // Detects sequence variables (generalized induction variables) during an inner-loop-first
+ // traversal of all loops using Gerlek's algorithm. The order is only relevant if outer
+ // loops would use induction information of inner loops (not currently done).
for (HPostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
HBasicBlock* graph_block = it_graph.Current();
if (graph_block->IsLoopHeader()) {
@@ -71,38 +99,37 @@
// Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's
// algorithm. Due to the descendant-first nature, classification happens "on-demand".
global_depth_ = 0;
- CHECK(stack_.empty());
+ DCHECK(stack_.empty());
map_.clear();
for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
HBasicBlock* loop_block = it_loop.Current();
- CHECK(loop_block->IsInLoop());
+ DCHECK(loop_block->IsInLoop());
if (loop_block->GetLoopInformation() != loop) {
continue; // Inner loops already visited.
}
// Visit phi-operations and instructions.
for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) {
HInstruction* instruction = it.Current();
- if (!IsVisitedNode(instruction->GetId())) {
+ if (!IsVisitedNode(instruction)) {
VisitNode(loop, instruction);
}
}
for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* instruction = it.Current();
- if (!IsVisitedNode(instruction->GetId())) {
+ if (!IsVisitedNode(instruction)) {
VisitNode(loop, instruction);
}
}
}
- CHECK(stack_.empty());
+ DCHECK(stack_.empty());
map_.clear();
}
void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) {
- const int id = instruction->GetId();
const uint32_t d1 = ++global_depth_;
- map_.Put(id, NodeInfo(d1));
+ map_.Put(instruction, NodeInfo(d1));
stack_.push_back(instruction);
// Visit all descendants.
@@ -113,7 +140,7 @@
// Lower or found SCC?
if (low < d1) {
- map_.find(id)->second.depth = low;
+ map_.find(instruction)->second.depth = low;
} else {
scc_.clear();
cycle_.clear();
@@ -123,7 +150,7 @@
HInstruction* x = stack_.back();
scc_.push_back(x);
stack_.pop_back();
- map_.find(x->GetId())->second.done = true;
+ map_.find(x)->second.done = true;
if (x == instruction) {
break;
}
@@ -150,12 +177,11 @@
}
// Inspect descendant node.
- const int id = instruction->GetId();
- if (!IsVisitedNode(id)) {
+ if (!IsVisitedNode(instruction)) {
VisitNode(loop, instruction);
- return map_.find(id)->second.depth;
+ return map_.find(instruction)->second.depth;
} else {
- auto it = map_.find(id);
+ auto it = map_.find(instruction);
return it->second.done ? global_depth_ : it->second.depth;
}
}
@@ -176,8 +202,20 @@
} else if (instruction->IsMul()) {
info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, instruction->InputAt(1)));
+ } else if (instruction->IsShl()) {
+ info = TransferShl(LookupInfo(loop, instruction->InputAt(0)),
+ LookupInfo(loop, instruction->InputAt(1)),
+ instruction->InputAt(0)->GetType());
} else if (instruction->IsNeg()) {
info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
+ } else if (instruction->IsBoundsCheck()) {
+ info = LookupInfo(loop, instruction->InputAt(0)); // Pass-through.
+ } else if (instruction->IsTypeConversion()) {
+ HTypeConversion* conversion = instruction->AsTypeConversion();
+ // TODO: accept different conversion scenarios.
+ if (conversion->GetResultType() == conversion->GetInputType()) {
+ info = LookupInfo(loop, conversion->GetInput());
+ }
}
// Successfully classified?
@@ -188,7 +226,7 @@
void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
const size_t size = scc_.size();
- CHECK_GE(size, 1u);
+ DCHECK_GE(size, 1u);
HInstruction* phi = scc_[size - 1];
if (!IsEntryPhi(loop, phi)) {
return;
@@ -204,41 +242,74 @@
if (size == 1) {
InductionInfo* update = LookupInfo(loop, internal);
if (update != nullptr) {
- AssignInfo(loop, phi, NewInductionInfo(kWrapAround, kNop, initial, update, nullptr));
+ AssignInfo(loop, phi, NewInduction(kWrapAround, initial, update));
}
return;
}
// Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
- // temporary meaning to its nodes.
- cycle_.Overwrite(phi->GetId(), nullptr);
+ // temporary meaning to its nodes, seeded from the phi instruction and back.
for (size_t i = 0; i < size - 1; i++) {
- HInstruction* operation = scc_[i];
+ HInstruction* instruction = scc_[i];
InductionInfo* update = nullptr;
- if (operation->IsPhi()) {
- update = TransferCycleOverPhi(operation);
- } else if (operation->IsAdd()) {
- update = TransferCycleOverAddSub(loop, operation->InputAt(0), operation->InputAt(1), kAdd, true);
- } else if (operation->IsSub()) {
- update = TransferCycleOverAddSub(loop, operation->InputAt(0), operation->InputAt(1), kSub, true);
+ if (instruction->IsPhi()) {
+ update = SolvePhi(loop, phi, instruction);
+ } else if (instruction->IsAdd()) {
+ update = SolveAddSub(
+ loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true);
+ } else if (instruction->IsSub()) {
+ update = SolveAddSub(
+ loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true);
}
if (update == nullptr) {
return;
}
- cycle_.Overwrite(operation->GetId(), update);
+ cycle_.Put(instruction, update);
}
- // Success if the internal link received accumulated nonzero update.
- auto it = cycle_.find(internal->GetId());
- if (it != cycle_.end() && it->second != nullptr) {
- // Classify header phi and feed the cycle "on-demand".
- AssignInfo(loop, phi, NewInductionInfo(kLinear, kNop, it->second, initial, nullptr));
- for (size_t i = 0; i < size - 1; i++) {
- ClassifyTrivial(loop, scc_[i]);
+ // Success if the internal link received a meaning.
+ auto it = cycle_.find(internal);
+ if (it != cycle_.end()) {
+ InductionInfo* induction = it->second;
+ switch (induction->induction_class) {
+ case kInvariant:
+ // Classify phi (last element in scc_) and then the rest of the cycle "on-demand".
+ // Statements are scanned in the Tarjan SCC order, with phi first.
+ AssignInfo(loop, phi, NewInduction(kLinear, induction, initial));
+ for (size_t i = 0; i < size - 1; i++) {
+ ClassifyTrivial(loop, scc_[i]);
+ }
+ break;
+ case kPeriodic:
+ // Classify all elements in the cycle with the found periodic induction while rotating
+ // each first element to the end. Lastly, phi (last element in scc_) is classified.
+ // Statements are scanned in the reverse Tarjan SCC order, with phi last.
+ for (size_t i = 2; i <= size; i++) {
+ AssignInfo(loop, scc_[size - i], induction);
+ induction = RotatePeriodicInduction(induction->op_b, induction->op_a);
+ }
+ AssignInfo(loop, phi, induction);
+ break;
+ default:
+ break;
}
}
}
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction(
+ InductionInfo* induction,
+ InductionInfo* last) {
+ // Rotates a periodic induction of the form
+ // (a, b, c, d, e)
+ // into
+ // (b, c, d, e, a)
+ // in preparation of assigning this to the previous variable in the sequence.
+ if (induction->induction_class == kInvariant) {
+ return NewInduction(kPeriodic, induction, last);
+ }
+ return NewInduction(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.
@@ -251,36 +322,33 @@
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
InductionInfo* b,
InductionOp op) {
- // Transfer over an addition or subtraction: invariant or linear
- // inputs combine into new invariant or linear result.
+ // Transfer over an addition or subtraction: any invariant, linear, wrap-around, or periodic
+ // can be combined with an invariant to yield a similar result. Even two linear inputs can
+ // be combined. All other combinations fail, however.
if (a != nullptr && b != nullptr) {
if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
- return NewInductionInfo(kInvariant, op, a, b, nullptr);
- } else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
- return NewInductionInfo(
- kLinear,
- kNop,
- a->op_a,
- NewInductionInfo(kInvariant, op, a->op_b, b, nullptr),
- nullptr);
- } else if (a->induction_class == kInvariant && b->induction_class == kLinear) {
- InductionInfo* ba = b->op_a;
- if (op == kSub) { // negation required
- ba = NewInductionInfo(kInvariant, kNeg, nullptr, ba, nullptr);
- }
- return NewInductionInfo(
- kLinear,
- kNop,
- ba,
- NewInductionInfo(kInvariant, op, a, b->op_b, nullptr),
- nullptr);
+ return NewInvariantOp(op, a, b);
} else if (a->induction_class == kLinear && b->induction_class == kLinear) {
- return NewInductionInfo(
- kLinear,
- kNop,
- NewInductionInfo(kInvariant, op, a->op_a, b->op_a, nullptr),
- NewInductionInfo(kInvariant, op, a->op_b, b->op_b, nullptr),
- nullptr);
+ return NewInduction(
+ kLinear, TransferAddSub(a->op_a, b->op_a, op), TransferAddSub(a->op_b, b->op_b, op));
+ } else if (a->induction_class == kInvariant) {
+ InductionInfo* new_a = b->op_a;
+ InductionInfo* new_b = TransferAddSub(a, b->op_b, op);
+ if (b->induction_class != kLinear) {
+ DCHECK(b->induction_class == kWrapAround || b->induction_class == kPeriodic);
+ new_a = TransferAddSub(a, new_a, op);
+ } else if (op == kSub) { // Negation required.
+ new_a = TransferNeg(new_a);
+ }
+ return NewInduction(b->induction_class, new_a, new_b);
+ } else if (b->induction_class == kInvariant) {
+ InductionInfo* new_a = a->op_a;
+ InductionInfo* new_b = TransferAddSub(a->op_b, b, op);
+ if (a->induction_class != kLinear) {
+ DCHECK(a->induction_class == kWrapAround || a->induction_class == kPeriodic);
+ new_a = TransferAddSub(new_a, b, op);
+ }
+ return NewInduction(a->induction_class, new_a, new_b);
}
}
return nullptr;
@@ -288,141 +356,164 @@
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a,
InductionInfo* b) {
- // Transfer over a multiplication: invariant or linear
- // inputs combine into new invariant or linear result.
- // Two linear inputs would become quadratic.
+ // Transfer over a multiplication: any invariant, linear, wrap-around, or periodic
+ // can be multiplied with an invariant to yield a similar but multiplied result.
+ // Two non-invariant inputs cannot be multiplied, however.
if (a != nullptr && b != nullptr) {
if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
- return NewInductionInfo(kInvariant, kMul, a, b, nullptr);
- } else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
- return NewInductionInfo(
- kLinear,
- kNop,
- NewInductionInfo(kInvariant, kMul, a->op_a, b, nullptr),
- NewInductionInfo(kInvariant, kMul, a->op_b, b, nullptr),
- nullptr);
- } else if (a->induction_class == kInvariant && b->induction_class == kLinear) {
- return NewInductionInfo(
- kLinear,
- kNop,
- NewInductionInfo(kInvariant, kMul, a, b->op_a, nullptr),
- NewInductionInfo(kInvariant, kMul, a, b->op_b, nullptr),
- nullptr);
+ return NewInvariantOp(kMul, a, b);
+ } else if (a->induction_class == kInvariant) {
+ return NewInduction(b->induction_class, TransferMul(a, b->op_a), TransferMul(a, b->op_b));
+ } else if (b->induction_class == kInvariant) {
+ return NewInduction(a->induction_class, TransferMul(a->op_a, b), TransferMul(a->op_b, b));
+ }
+ }
+ return nullptr;
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferShl(InductionInfo* a,
+ InductionInfo* b,
+ Primitive::Type t) {
+ // Transfer over a shift left: treat shift by restricted constant as equivalent multiplication.
+ if (a != nullptr && b != nullptr && b->induction_class == kInvariant && b->operation == kFetch) {
+ int64_t value = -1;
+ // Obtain the constant needed for the multiplication. This yields an existing instruction
+ // if the constants is already there. Otherwise, this has a side effect on the HIR.
+ // 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 (IsIntAndGet(b->fetch, &value)) {
+ if (t == Primitive::kPrimInt && 0 <= value && value < 31) {
+ return TransferMul(a, NewInvariantFetch(graph_->GetIntConstant(1 << value)));
+ } else if (t == Primitive::kPrimLong && 0 <= value && value < 63) {
+ return TransferMul(a, NewInvariantFetch(graph_->GetLongConstant(1L << value)));
+ }
}
}
return nullptr;
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
- // Transfer over a unary negation: invariant or linear input
- // yields a similar, but negated result.
+ // Transfer over a unary negation: an invariant, linear, wrap-around, or periodic input
+ // yields a similar but negated induction as result.
if (a != nullptr) {
if (a->induction_class == kInvariant) {
- return NewInductionInfo(kInvariant, kNeg, nullptr, a, nullptr);
- } else if (a->induction_class == kLinear) {
- return NewInductionInfo(
- kLinear,
- kNop,
- NewInductionInfo(kInvariant, kNeg, nullptr, a->op_a, nullptr),
- NewInductionInfo(kInvariant, kNeg, nullptr, a->op_b, nullptr),
- nullptr);
+ return NewInvariantOp(kNeg, nullptr, a);
}
+ return NewInduction(a->induction_class, TransferNeg(a->op_a), TransferNeg(a->op_b));
}
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCycleOverPhi(HInstruction* phi) {
- // Transfer within a cycle over a phi: only identical inputs
- // can be combined into that input as result.
- const size_t count = phi->InputCount();
- CHECK_GT(count, 0u);
- auto ita = cycle_.find(phi->InputAt(0)->GetId());
+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));
if (ita != cycle_.end()) {
InductionInfo* a = ita->second;
for (size_t i = 1; i < count; i++) {
- auto itb = cycle_.find(phi->InputAt(i)->GetId());
- if (itb == cycle_.end() ||!HInductionVarAnalysis::InductionEqual(a, itb->second)) {
+ auto itb = cycle_.find(instruction->InputAt(i));
+ if (itb == cycle_.end() || !HInductionVarAnalysis::InductionEqual(a, itb->second)) {
return nullptr;
}
}
return a;
}
- return nullptr;
-}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferCycleOverAddSub(
- HLoopInformation* loop,
- HInstruction* x,
- HInstruction* y,
- InductionOp op,
- bool first) {
- // Transfer within a cycle over an addition or subtraction: adding or
- // subtracting an invariant value adds to the stride of the induction,
- // starting with the phi value denoted by the unusual nullptr value.
- auto it = cycle_.find(x->GetId());
- if (it != cycle_.end()) {
- InductionInfo* a = it->second;
- InductionInfo* b = LookupInfo(loop, y);
- if (b != nullptr && b->induction_class == kInvariant) {
- if (a == nullptr) {
- if (op == kSub) { // negation required
- return NewInductionInfo(kInvariant, kNeg, nullptr, b, nullptr);
+ // Solve within a cycle over another entry-phi: add invariants into a periodic.
+ if (IsEntryPhi(loop, instruction)) {
+ InductionInfo* a = LookupInfo(loop, instruction->InputAt(0));
+ if (a != nullptr && a->induction_class == kInvariant) {
+ if (instruction->InputAt(1) == phi) {
+ InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
+ return NewInduction(kPeriodic, a, initial);
+ }
+ auto it = cycle_.find(instruction->InputAt(1));
+ if (it != cycle_.end()) {
+ InductionInfo* b = it->second;
+ if (b->induction_class == kPeriodic) {
+ return NewInduction(kPeriodic, a, b);
}
- return b;
- } else if (a->induction_class == kInvariant) {
- return NewInductionInfo(kInvariant, op, a, b, nullptr);
}
}
}
- // On failure, try alternatives.
- if (op == kAdd) {
- // Try the other way around for an addition.
- if (first) {
- return TransferCycleOverAddSub(loop, y, x, op, false);
- }
- }
+
return nullptr;
}
-void HInductionVarAnalysis::PutInfo(int loop_id, int id, InductionInfo* info) {
- auto it = induction_.find(loop_id);
- if (it == induction_.end()) {
- it = induction_.Put(
- loop_id, ArenaSafeMap<int, InductionInfo*>(std::less<int>(), graph_->GetArena()->Adapter()));
- }
- it->second.Overwrite(id, info);
-}
-
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::GetInfo(int loop_id, int id) {
- auto it = induction_.find(loop_id);
- if (it != induction_.end()) {
- auto loop_it = it->second.find(id);
- if (loop_it != it->second.end()) {
- return loop_it->second;
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop,
+ HInstruction* phi,
+ HInstruction* instruction,
+ HInstruction* x,
+ HInstruction* y,
+ InductionOp op,
+ bool is_first_call) {
+ // Solve within a cycle over an addition or subtraction: adding or subtracting an
+ // 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) {
+ return (op == kAdd) ? b : NewInvariantOp(kNeg, nullptr, b);
+ }
+ auto it = cycle_.find(x);
+ if (it != cycle_.end()) {
+ InductionInfo* a = it->second;
+ if (a->induction_class == kInvariant) {
+ return NewInvariantOp(op, a, b);
+ }
}
}
+
+ // Try some alternatives before failing.
+ 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);
+ }
+ } else if (op == kSub) {
+ // Solve within a tight cycle for a periodic idiom k = c - k;
+ if (y == phi && instruction == phi->InputAt(1)) {
+ InductionInfo* a = LookupInfo(loop, x);
+ if (a != nullptr && a->induction_class == kInvariant) {
+ InductionInfo* initial = LookupInfo(loop, phi->InputAt(0));
+ return NewInduction(kPeriodic, NewInvariantOp(kSub, a, initial), initial);
+ }
+ }
+ }
+
return nullptr;
}
void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
HInstruction* instruction,
InductionInfo* info) {
- const int loopId = loop->GetHeader()->GetBlockId();
- const int id = instruction->GetId();
- PutInfo(loopId, id, info);
+ auto it = induction_.find(loop);
+ if (it == induction_.end()) {
+ it = induction_.Put(loop,
+ ArenaSafeMap<HInstruction*, InductionInfo*>(
+ std::less<HInstruction*>(), graph_->GetArena()->Adapter()));
+ }
+ it->second.Put(instruction, info);
}
-HInductionVarAnalysis::InductionInfo*
-HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
- HInstruction* instruction) {
- const int loop_id = loop->GetHeader()->GetBlockId();
- const int id = instruction->GetId();
- InductionInfo* info = GetInfo(loop_id, id);
- if (info == nullptr && IsLoopInvariant(loop, instruction)) {
- info = NewInductionInfo(kInvariant, kFetch, nullptr, nullptr, instruction);
- PutInfo(loop_id, id, info);
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
+ HInstruction* instruction) {
+ auto it = induction_.find(loop);
+ if (it != induction_.end()) {
+ auto loop_it = it->second.find(instruction);
+ if (loop_it != it->second.end()) {
+ return loop_it->second;
+ }
}
- return info;
+ if (IsLoopInvariant(loop, instruction)) {
+ InductionInfo* info = NewInvariantFetch(instruction);
+ AssignInfo(loop, instruction, info);
+ return info;
+ }
+ return nullptr;
}
bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
@@ -446,21 +537,21 @@
std::string inv = "(";
inv += InductionToString(info->op_a);
switch (info->operation) {
- case kNop: inv += " ? "; break;
- case kAdd: inv += " + "; break;
+ case kNop: inv += " @ "; break;
+ case kAdd: inv += " + "; break;
case kSub:
- case kNeg: inv += " - "; break;
- case kMul: inv += " * "; break;
- case kDiv: inv += " / "; break;
+ case kNeg: inv += " - "; break;
+ case kMul: inv += " * "; break;
+ case kDiv: inv += " / "; break;
case kFetch:
- CHECK(info->fetch != nullptr);
- inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
+ DCHECK(info->fetch);
+ inv += InstructionToString(info->fetch);
break;
}
inv += InductionToString(info->op_b);
return inv + ")";
} else {
- CHECK(info->operation == kNop);
+ DCHECK(info->operation == kNop);
if (info->induction_class == kLinear) {
return "(" + InductionToString(info->op_a) + " * i + " +
InductionToString(info->op_b) + ")";
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 09a0a38..db00f58 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -25,9 +25,11 @@
namespace art {
/**
- * Induction variable analysis.
+ * Induction variable analysis. This class does not have a direct public API.
+ * Instead, the results of induction variable analysis can be queried through
+ * friend classes, such as InductionVarRange.
*
- * Based on the paper by M. Gerlek et al.
+ * The analysis implementation is based on the paper by M. Gerlek et al.
* "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form"
* (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995).
*/
@@ -35,16 +37,6 @@
public:
explicit HInductionVarAnalysis(HGraph* graph);
- // TODO: design public API useful in later phases
-
- /**
- * Returns string representation of induction found for the instruction
- * in the given loop (for testing and debugging only).
- */
- std::string InductionToString(HLoopInformation* loop, HInstruction* instruction) {
- return InductionToString(LookupInfo(loop, instruction));
- }
-
void Run() OVERRIDE;
private:
@@ -57,12 +49,10 @@
};
enum InductionClass {
- kNone,
kInvariant,
kLinear,
kWrapAround,
- kPeriodic,
- kMonotonic
+ kPeriodic
};
enum InductionOp {
@@ -79,7 +69,7 @@
* Defines a detected induction as:
* (1) invariant:
* operation: a + b, a - b, -b, a * b, a / b
- * or
+ * or:
* fetch: fetch from HIR
* (2) linear:
* nop: a * i + b
@@ -87,8 +77,6 @@
* nop: a, then defined by b
* (4) periodic
* nop: a, then defined by b (repeated when exhausted)
- * (5) monotonic
- * // TODO: determine representation
*/
struct InductionInfo : public ArenaObject<kArenaAllocMisc> {
InductionInfo(InductionClass ic,
@@ -108,17 +96,23 @@
HInstruction* fetch;
};
- inline bool IsVisitedNode(int id) const {
- return map_.find(id) != map_.end();
+ bool IsVisitedNode(HInstruction* instruction) const {
+ return map_.find(instruction) != map_.end();
}
- inline InductionInfo* NewInductionInfo(
- InductionClass c,
- InductionOp op,
- InductionInfo* a,
- InductionInfo* b,
- HInstruction* i) {
- return new (graph_->GetArena()) InductionInfo(c, op, a, b, i);
+ InductionInfo* NewInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
+ DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
+ return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr);
+ }
+
+ InductionInfo* NewInvariantFetch(HInstruction* f) {
+ DCHECK(f != nullptr);
+ return new (graph_->GetArena()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f);
+ }
+
+ InductionInfo* NewInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) {
+ DCHECK(a != nullptr && b != nullptr);
+ return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr);
}
// Methods for analysis.
@@ -132,36 +126,46 @@
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* TransferNeg(InductionInfo* a);
- InductionInfo* TransferCycleOverPhi(HInstruction* phi);
- InductionInfo* TransferCycleOverAddSub(HLoopInformation* loop,
- HInstruction* x,
- HInstruction* y,
- InductionOp op,
- bool first);
+
+ // Solvers.
+ InductionInfo* SolvePhi(HLoopInformation* loop,
+ HInstruction* phi,
+ HInstruction* instruction);
+ InductionInfo* SolveAddSub(HLoopInformation* loop,
+ HInstruction* phi,
+ HInstruction* instruction,
+ HInstruction* x,
+ HInstruction* y,
+ InductionOp op,
+ bool is_first_call);
+ InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
// Assign and lookup.
- void PutInfo(int loop_id, int id, InductionInfo* info);
- InductionInfo* GetInfo(int loop_id, int id);
void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
- bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
- std::string InductionToString(InductionInfo* info);
- // Bookkeeping during and after analysis.
- // TODO: fine tune data structures, only keep relevant data
+ // Helpers.
+ static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
+ static std::string InductionToString(InductionInfo* info);
+ // TODO: fine tune the following data structures, only keep relevant data.
+
+ // Temporary book-keeping during the analysis.
uint32_t global_depth_;
-
ArenaVector<HInstruction*> stack_;
ArenaVector<HInstruction*> scc_;
+ ArenaSafeMap<HInstruction*, NodeInfo> map_;
+ ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
- // Mappings of instruction id to node and induction information.
- ArenaSafeMap<int, NodeInfo> map_;
- ArenaSafeMap<int, InductionInfo*> cycle_;
+ /**
+ * Maintains the results of the analysis as a mapping from loops to a mapping from instructions
+ * to the induction information for that instruction in that loop.
+ */
+ ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
- // Mapping from loop id to mapping of instruction id to induction information.
- ArenaSafeMap<int, ArenaSafeMap<int, InductionInfo*>> induction_;
+ friend class InductionVarAnalysisTest;
DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
};
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 2093e33..b569fbe 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -63,7 +63,7 @@
// populate the loop with instructions to set up interesting scenarios.
void BuildLoopNest(int n) {
ASSERT_LE(n, 10);
- graph_->SetNumberOfVRegs(n + 2);
+ graph_->SetNumberOfVRegs(n + 3);
// Build basic blocks with entry, nested loop, exit.
entry_ = new (&allocator_) HBasicBlock(graph_);
@@ -77,47 +77,36 @@
graph_->SetExitBlock(exit_);
// Provide entry and exit instructions.
- // 0 : parameter
- // 1 : constant 0
- // 2 : constant 1
- // 3 : constant 100
- parameter_ = new (&allocator_)
- HParameterValue(0, Primitive::kPrimNot, true);
+ parameter_ = new (&allocator_) HParameterValue(0, Primitive::kPrimNot, true);
entry_->AddInstruction(parameter_);
- constant0_ = new (&allocator_) HConstant(Primitive::kPrimInt);
- entry_->AddInstruction(constant0_);
- constant1_ = new (&allocator_) HConstant(Primitive::kPrimInt);
- entry_->AddInstruction(constant1_);
- constant100_ = new (&allocator_) HConstant(Primitive::kPrimInt);
- entry_->AddInstruction(constant100_);
- exit_->AddInstruction(new (&allocator_) HExit());
+ constant0_ = graph_->GetIntConstant(0);
+ constant1_ = graph_->GetIntConstant(1);
+ constant100_ = graph_->GetIntConstant(100);
induc_ = new (&allocator_) HLocal(n);
entry_->AddInstruction(induc_);
entry_->AddInstruction(new (&allocator_) HStoreLocal(induc_, constant0_));
tmp_ = new (&allocator_) HLocal(n + 1);
entry_->AddInstruction(tmp_);
entry_->AddInstruction(new (&allocator_) HStoreLocal(tmp_, constant100_));
+ dum_ = new (&allocator_) HLocal(n + 2);
+ entry_->AddInstruction(dum_);
+ exit_->AddInstruction(new (&allocator_) HExit());
// Provide loop instructions.
for (int d = 0; d < n; d++) {
basic_[d] = new (&allocator_) HLocal(d);
entry_->AddInstruction(basic_[d]);
- loop_preheader_[d]->AddInstruction(
- new (&allocator_) HStoreLocal(basic_[d], constant0_));
- HInstruction* load = new (&allocator_)
- HLoadLocal(basic_[d], Primitive::kPrimInt);
+ 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_) HGreaterThanOrEqual(load, constant100_);
loop_header_[d]->AddInstruction(compare);
loop_header_[d]->AddInstruction(new (&allocator_) HIf(compare));
load = new (&allocator_) HLoadLocal(basic_[d], Primitive::kPrimInt);
loop_body_[d]->AddInstruction(load);
- increment_[d] = new (&allocator_)
- HAdd(Primitive::kPrimInt, load, constant1_);
+ increment_[d] = new (&allocator_) HAdd(Primitive::kPrimInt, load, constant1_);
loop_body_[d]->AddInstruction(increment_[d]);
- loop_body_[d]->AddInstruction(
- new (&allocator_) HStoreLocal(basic_[d], increment_[d]));
+ loop_body_[d]->AddInstruction(new (&allocator_) HStoreLocal(basic_[d], increment_[d]));
loop_body_[d]->AddInstruction(new (&allocator_) HGoto());
}
}
@@ -149,8 +138,7 @@
// Inserts local load at depth d.
HInstruction* InsertLocalLoad(HLocal* local, int d) {
- return InsertInstruction(
- new (&allocator_) HLoadLocal(local, Primitive::kPrimInt), d);
+ return InsertInstruction(new (&allocator_) HLoadLocal(local, Primitive::kPrimInt), d);
}
// Inserts local store at depth d.
@@ -167,9 +155,10 @@
parameter_, load, constant0_, Primitive::kPrimInt, 0), d);
}
- // Returns loop information of loop at depth d.
- HLoopInformation* GetLoopInfo(int d) {
- return loop_body_[d]->GetLoopInformation();
+ // Returns induction information of instruction in loop at depth d.
+ std::string GetInductionInfo(HInstruction* instruction, int d) {
+ return HInductionVarAnalysis::InductionToString(
+ iva_->LookupInfo(loop_body_[d]->GetLoopInformation(), instruction));
}
// Performs InductionVarAnalysis (after proper set up).
@@ -194,6 +183,7 @@
HInstruction* constant100_;
HLocal* induc_; // "vreg_n", the "k"
HLocal* tmp_; // "vreg_n+1"
+ HLocal* dum_; // "vreg_n+2"
// Loop specifics.
HBasicBlock* loop_preheader_[10];
@@ -230,222 +220,156 @@
ASSERT_EQ(exit_->GetLoopInformation(), nullptr);
}
-TEST_F(InductionVarAnalysisTest, FindBasicInductionVar) {
+TEST_F(InductionVarAnalysisTest, FindBasicInduction) {
// Setup:
// for (int i = 0; i < 100; i++) {
- // a[i] = 0;
+ // a[i] = 0;
// }
BuildLoopNest(1);
HInstruction* store = InsertArrayStore(basic_[0], 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ(
- "((2:Constant) * i + (1:Constant))",
- iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
- EXPECT_STREQ(
- "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
- iva_->InductionToString(GetLoopInfo(0), increment_[0]).c_str());
+ EXPECT_STREQ("((1) * i + (0))", GetInductionInfo(store->InputAt(1), 0).c_str());
+ EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(increment_[0], 0).c_str());
}
-TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarAdd) {
+TEST_F(InductionVarAnalysisTest, FindDerivedInduction) {
// Setup:
// for (int i = 0; i < 100; i++) {
- // k = 100 + i;
- // a[k] = 0;
+ // k = 100 + i;
+ // k = 100 - i;
+ // k = 100 * i;
+ // k = i << 1;
+ // k = - i;
// }
BuildLoopNest(1);
HInstruction *add = InsertInstruction(
- new (&allocator_) HAdd(
- Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+ new (&allocator_) HAdd(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
InsertLocalStore(induc_, add, 0);
- HInstruction* store = InsertArrayStore(induc_, 0);
- PerformInductionVarAnalysis();
-
- EXPECT_STREQ(
- "((2:Constant) * i + ((3:Constant) + (1:Constant)))",
- iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
-}
-
-TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarSub) {
- // Setup:
- // for (int i = 0; i < 100; i++) {
- // k = 100 - i;
- // a[k] = 0;
- // }
- BuildLoopNest(1);
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(induc_, sub, 0);
- HInstruction* store = InsertArrayStore(induc_, 0);
- PerformInductionVarAnalysis();
-
- EXPECT_STREQ(
- "(( - (2:Constant)) * i + ((3:Constant) - (1:Constant)))",
- iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
-}
-
-TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarMul) {
- // Setup:
- // for (int i = 0; i < 100; i++) {
- // k = 100 * i;
- // a[k] = 0;
- // }
- BuildLoopNest(1);
HInstruction *mul = InsertInstruction(
- new (&allocator_) HMul(
- Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
+ new (&allocator_) HMul(Primitive::kPrimInt, constant100_, InsertLocalLoad(basic_[0], 0)), 0);
InsertLocalStore(induc_, mul, 0);
- HInstruction* store = InsertArrayStore(induc_, 0);
- PerformInductionVarAnalysis();
-
- EXPECT_STREQ(
- "(((3:Constant) * (2:Constant)) * i + ((3:Constant) * (1:Constant)))",
- iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
-}
-
-TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarNeg) {
- // Setup:
- // for (int i = 0; i < 100; i++) {
- // k = - i;
- // a[k] = 0;
- // }
- BuildLoopNest(1);
+ HInstruction *shl = InsertInstruction(
+ new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0), constant1_), 0);
+ InsertLocalStore(induc_, shl, 0);
HInstruction *neg = InsertInstruction(
- new (&allocator_) HNeg(
- Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0)), 0);
+ new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0)), 0);
InsertLocalStore(induc_, neg, 0);
- HInstruction* store = InsertArrayStore(induc_, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ(
- "(( - (2:Constant)) * i + ( - (1:Constant)))",
- iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+ EXPECT_STREQ("((1) * i + ((100) + (0)))", GetInductionInfo(add, 0).c_str());
+ EXPECT_STREQ("(( - (1)) * i + ((100) - (0)))", GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("(((100) * (1)) * i + ((100) * (0)))", GetInductionInfo(mul, 0).c_str());
+ EXPECT_STREQ("(((1) * (2)) * i + ((0) * (2)))", GetInductionInfo(shl, 0).c_str());
+ EXPECT_STREQ("(( - (1)) * i + ( - (0)))", GetInductionInfo(neg, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindChainInduction) {
// Setup:
// k = 0;
// for (int i = 0; i < 100; i++) {
- // k = k + 100;
- // a[k] = 0;
- // k = k - 1;
- // a[k] = 0;
+ // k = k + 100;
+ // a[k] = 0;
+ // k = k - 1;
+ // a[k] = 0;
// }
BuildLoopNest(1);
HInstruction *add = InsertInstruction(
- new (&allocator_) HAdd(
- Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
+ new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant100_), 0);
InsertLocalStore(induc_, add, 0);
HInstruction* store1 = InsertArrayStore(induc_, 0);
HInstruction *sub = InsertInstruction(
- new (&allocator_) HSub(
- Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
+ new (&allocator_) HSub(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
InsertLocalStore(induc_, sub, 0);
HInstruction* store2 = InsertArrayStore(induc_, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ(
- "(((3:Constant) - (2:Constant)) * i + ((1:Constant) + (3:Constant)))",
- iva_->InductionToString(GetLoopInfo(0), store1->InputAt(1)).c_str());
- EXPECT_STREQ(
- "(((3:Constant) - (2:Constant)) * i + "
- "(((1:Constant) + (3:Constant)) - (2:Constant)))",
- iva_->InductionToString(GetLoopInfo(0), store2->InputAt(1)).c_str());
+ EXPECT_STREQ("(((100) - (1)) * i + ((0) + (100)))",
+ GetInductionInfo(store1->InputAt(1), 0).c_str());
+ EXPECT_STREQ("(((100) - (1)) * i + (((0) + (100)) - (1)))",
+ GetInductionInfo(store2->InputAt(1), 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindTwoWayBasicInduction) {
// Setup:
// k = 0;
// for (int i = 0; i < 100; i++) {
- // if () k = k + 1;
- // else k = k + 1;
- // a[k] = 0;
+ // if () k = k + 1;
+ // else k = k + 1;
+ // a[k] = 0;
// }
BuildLoopNest(1);
HBasicBlock* ifTrue;
HBasicBlock* ifFalse;
BuildIf(0, &ifTrue, &ifFalse);
// True-branch.
- HInstruction* load1 = new (&allocator_)
- HLoadLocal(induc_, Primitive::kPrimInt);
+ HInstruction* load1 = new (&allocator_) HLoadLocal(induc_, Primitive::kPrimInt);
ifTrue->AddInstruction(load1);
- HInstruction* inc1 = new (&allocator_)
- HAdd(Primitive::kPrimInt, load1, constant1_);
+ HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, load1, constant1_);
ifTrue->AddInstruction(inc1);
ifTrue->AddInstruction(new (&allocator_) HStoreLocal(induc_, inc1));
// False-branch.
- HInstruction* load2 = new (&allocator_)
- HLoadLocal(induc_, Primitive::kPrimInt);
+ HInstruction* load2 = new (&allocator_) HLoadLocal(induc_, Primitive::kPrimInt);
ifFalse->AddInstruction(load2);
- HInstruction* inc2 = new (&allocator_)
- HAdd(Primitive::kPrimInt, load2, constant1_);
+ HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, load2, constant1_);
ifFalse->AddInstruction(inc2);
ifFalse->AddInstruction(new (&allocator_) HStoreLocal(induc_, inc2));
// Merge over a phi.
HInstruction* store = InsertArrayStore(induc_, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ(
- "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
- iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+ EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(store->InputAt(1), 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) {
// Setup:
// for (int i = 0; i < 100; i++) {
- // if () k = i + 1;
- // else k = i + 1;
- // a[k] = 0;
+ // if () k = i + 1;
+ // else k = i + 1;
+ // a[k] = 0;
// }
BuildLoopNest(1);
HBasicBlock* ifTrue;
HBasicBlock* ifFalse;
BuildIf(0, &ifTrue, &ifFalse);
// True-branch.
- HInstruction* load1 = new (&allocator_)
- HLoadLocal(basic_[0], Primitive::kPrimInt);
+ HInstruction* load1 = new (&allocator_) HLoadLocal(basic_[0], Primitive::kPrimInt);
ifTrue->AddInstruction(load1);
- HInstruction* inc1 = new (&allocator_)
- HAdd(Primitive::kPrimInt, load1, constant1_);
+ HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, load1, constant1_);
ifTrue->AddInstruction(inc1);
ifTrue->AddInstruction(new (&allocator_) HStoreLocal(induc_, inc1));
// False-branch.
- HInstruction* load2 = new (&allocator_)
- HLoadLocal(basic_[0], Primitive::kPrimInt);
+ HInstruction* load2 = new (&allocator_) HLoadLocal(basic_[0], Primitive::kPrimInt);
ifFalse->AddInstruction(load2);
- HInstruction* inc2 = new (&allocator_)
- HAdd(Primitive::kPrimInt, load2, constant1_);
+ HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, load2, constant1_);
ifFalse->AddInstruction(inc2);
ifFalse->AddInstruction(new (&allocator_) HStoreLocal(induc_, inc2));
// Merge over a phi.
HInstruction* store = InsertArrayStore(induc_, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ(
- "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
- iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+ EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(store->InputAt(1), 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) {
// Setup:
// k = 0;
// for (int i = 0; i < 100; i++) {
- // a[k] = 0;
- // k = 100 - i;
+ // a[k] = 0;
+ // k = 100 - i;
// }
BuildLoopNest(1);
HInstruction* store = InsertArrayStore(induc_, 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(induc_, sub, 0);
PerformInductionVarAnalysis();
- EXPECT_STREQ(
- "wrap((1:Constant), "
- "(( - (2:Constant)) * i + ((3:Constant) - (1:Constant))))",
- iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+ EXPECT_STREQ("wrap((0), (( - (1)) * i + ((100) - (0))))",
+ GetInductionInfo(store->InputAt(1), 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) {
@@ -453,23 +377,149 @@
// k = 0;
// t = 100;
// for (int i = 0; i < 100; i++) {
- // a[k] = 0;
- // k = t;
- // t = 100 - i;
+ // a[k] = 0;
+ // k = t;
+ // t = 100 - i;
// }
BuildLoopNest(1);
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();
- EXPECT_STREQ(
- "wrap((1:Constant), wrap((3:Constant), "
- "(( - (2:Constant)) * i + ((3:Constant) - (1:Constant)))))",
- iva_->InductionToString(GetLoopInfo(0), store->InputAt(1)).c_str());
+ EXPECT_STREQ("wrap((0), wrap((100), (( - (1)) * i + ((100) - (0)))))",
+ GetInductionInfo(store->InputAt(1), 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i = 0; i < 100; i++) {
+ // t = k + 100;
+ // t = k - 100;
+ // t = k * 100;
+ // t = k << 1;
+ // t = - k;
+ // k = i << 1;
+ // }
+ BuildLoopNest(1);
+ HInstruction *add = InsertInstruction(
+ 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);
+ InsertLocalStore(tmp_, sub, 0);
+ HInstruction *mul = InsertInstruction(
+ 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);
+ InsertLocalStore(tmp_, shl, 0);
+ HInstruction *neg = InsertInstruction(
+ new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+ InsertLocalStore(tmp_, neg, 0);
+ InsertLocalStore(
+ induc_,
+ InsertInstruction(
+ new (&allocator_)
+ HShl(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0), constant1_), 0), 0);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("wrap(((0) + (100)), (((1) * (2)) * i + (((0) * (2)) + (100))))",
+ GetInductionInfo(add, 0).c_str());
+ EXPECT_STREQ("wrap(((0) - (100)), (((1) * (2)) * i + (((0) * (2)) - (100))))",
+ GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("wrap(((0) * (100)), ((((1) * (2)) * (100)) * i + (((0) * (2)) * (100))))",
+ GetInductionInfo(mul, 0).c_str());
+ EXPECT_STREQ("wrap(((0) * (2)), ((((1) * (2)) * (2)) * i + (((0) * (2)) * (2))))",
+ GetInductionInfo(shl, 0).c_str());
+ EXPECT_STREQ("wrap(( - (0)), (( - ((1) * (2))) * i + ( - ((0) * (2)))))",
+ GetInductionInfo(neg, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindPeriodicInduction) {
+ // Setup:
+ // k = 0;
+ // t = 100;
+ // for (int i = 0; i < 100; i++) {
+ // a[k] = 0;
+ // a[t] = 0;
+ // // Swap t <-> k.
+ // d = t;
+ // t = k;
+ // k = d;
+ // }
+ BuildLoopNest(1);
+ HInstruction* store1 = InsertArrayStore(induc_, 0);
+ HInstruction* store2 = InsertArrayStore(tmp_, 0);
+ InsertLocalStore(dum_, InsertLocalLoad(tmp_, 0), 0);
+ InsertLocalStore(tmp_, InsertLocalLoad(induc_, 0), 0);
+ InsertLocalStore(induc_, InsertLocalLoad(dum_, 0), 0);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic((0), (100))", GetInductionInfo(store1->InputAt(1), 0).c_str());
+ EXPECT_STREQ("periodic((100), (0))", GetInductionInfo(store2->InputAt(1), 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i = 0; i < 100; i++) {
+ // a[k] = 0;
+ // k = 1 - k;
+ // }
+ BuildLoopNest(1);
+ HInstruction* store = InsertArrayStore(induc_, 0);
+ HInstruction *sub = InsertInstruction(
+ new (&allocator_) HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0);
+ InsertLocalStore(induc_, sub, 0);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic((0), ((1) - (0)))", GetInductionInfo(store->InputAt(1), 0).c_str());
+ EXPECT_STREQ("periodic(((1) - (0)), (0))", GetInductionInfo(sub, 0).c_str());
+}
+
+TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i = 0; i < 100; i++) {
+ // k = 1 - k;
+ // t = k + 100;
+ // t = k - 100;
+ // t = k * 100;
+ // t = k << 1;
+ // t = - k;
+ // }
+ BuildLoopNest(1);
+ InsertLocalStore(
+ induc_,
+ InsertInstruction(new (&allocator_)
+ HSub(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 0)), 0), 0);
+ // Derived expressions.
+ HInstruction *add = InsertInstruction(
+ 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);
+ InsertLocalStore(tmp_, sub, 0);
+ HInstruction *mul = InsertInstruction(
+ 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);
+ InsertLocalStore(tmp_, shl, 0);
+ HInstruction *neg = InsertInstruction(
+ new (&allocator_) HNeg(Primitive::kPrimInt, InsertLocalLoad(induc_, 0)), 0);
+ InsertLocalStore(tmp_, neg, 0);
+ PerformInductionVarAnalysis();
+
+ EXPECT_STREQ("periodic((((1) - (0)) + (100)), ((0) + (100)))", GetInductionInfo(add, 0).c_str());
+ EXPECT_STREQ("periodic((((1) - (0)) - (100)), ((0) - (100)))", GetInductionInfo(sub, 0).c_str());
+ EXPECT_STREQ("periodic((((1) - (0)) * (100)), ((0) * (100)))", GetInductionInfo(mul, 0).c_str());
+ EXPECT_STREQ("periodic((((1) - (0)) * (2)), ((0) * (2)))", GetInductionInfo(shl, 0).c_str());
+ EXPECT_STREQ("periodic(( - ((1) - (0))), ( - (0)))", GetInductionInfo(neg, 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
@@ -485,29 +535,22 @@
// }
BuildLoopNest(10);
HInstruction *inc = InsertInstruction(
- new (&allocator_) HAdd(
- Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 9)), 9);
+ new (&allocator_) HAdd(Primitive::kPrimInt, constant1_, InsertLocalLoad(induc_, 9)), 9);
InsertLocalStore(induc_, inc, 9);
HInstruction* store = InsertArrayStore(induc_, 9);
PerformInductionVarAnalysis();
- // Match exact number of constants, but be less strict on phi number,
- // since that depends on the SSA building phase.
- std::regex r("\\(\\(2:Constant\\) \\* i \\+ "
- "\\(\\(2:Constant\\) \\+ \\(\\d+:Phi\\)\\)\\)");
+ // Avoid exact phi number, since that depends on the SSA building phase.
+ std::regex r("\\(\\(1\\) \\* i \\+ "
+ "\\(\\(1\\) \\+ \\(\\d+:Phi\\)\\)\\)");
for (int d = 0; d < 10; d++) {
if (d == 9) {
- EXPECT_TRUE(std::regex_match(
- iva_->InductionToString(GetLoopInfo(d), store->InputAt(1)), r));
+ EXPECT_TRUE(std::regex_match(GetInductionInfo(store->InputAt(1), d), r));
} else {
- EXPECT_STREQ(
- "",
- iva_->InductionToString(GetLoopInfo(d), store->InputAt(1)).c_str());
+ EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str());
}
- EXPECT_STREQ(
- "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
- iva_->InductionToString(GetLoopInfo(d), increment_[d]).c_str());
+ EXPECT_STREQ("((1) * i + ((0) + (1)))", GetInductionInfo(increment_[d], d).c_str());
}
}
