summaryrefslogtreecommitdiff
path: root/compiler/optimizing
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/optimizing')
-rw-r--r--compiler/optimizing/induction_var_analysis.cc415
-rw-r--r--compiler/optimizing/induction_var_analysis.h94
-rw-r--r--compiler/optimizing/induction_var_analysis_test.cc385
3 files changed, 516 insertions, 378 deletions
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 8aaec6804d..8b38414de0 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -42,6 +42,33 @@ static bool IsEntryPhi(HLoopInformation* loop, HInstruction* instruction) {
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 @@ HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph)
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 @@ void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
// 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 @@ void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* inst
// 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 @@ void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* inst
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 @@ uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruc
}
// 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 @@ void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction
} 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::ClassifyTrivial(HLoopInformation* loop, HInstruction
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 @@ void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
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::TransferPhi(Inducti
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::TransferAddSub(Indu
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;
}
+
+ // 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 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);
- }
- return b;
- } else if (a->induction_class == kInvariant) {
- return NewInductionInfo(kInvariant, op, a, b, nullptr);
+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);
}
}
}
- // On failure, try alternatives.
+
+ // Try some alternatives before failing.
if (op == kAdd) {
- // Try the other way around for an addition.
- if (first) {
- return TransferCycleOverAddSub(loop, y, x, op, false);
+ // 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::PutInfo(int loop_id, int id, InductionInfo* info) {
- auto it = induction_.find(loop_id);
+void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
+ HInstruction* instruction,
+ InductionInfo* info) {
+ auto it = induction_.find(loop);
if (it == induction_.end()) {
- it = induction_.Put(
- loop_id, ArenaSafeMap<int, InductionInfo*>(std::less<int>(), graph_->GetArena()->Adapter()));
+ it = induction_.Put(loop,
+ ArenaSafeMap<HInstruction*, InductionInfo*>(
+ std::less<HInstruction*>(), graph_->GetArena()->Adapter()));
}
- it->second.Overwrite(id, info);
+ it->second.Put(instruction, info);
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::GetInfo(int loop_id, int id) {
- auto it = induction_.find(loop_id);
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
+ HInstruction* instruction) {
+ auto it = induction_.find(loop);
if (it != induction_.end()) {
- auto loop_it = it->second.find(id);
+ auto loop_it = it->second.find(instruction);
if (loop_it != it->second.end()) {
return loop_it->second;
}
}
- 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);
-}
-
-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);
+ if (IsLoopInvariant(loop, instruction)) {
+ InductionInfo* info = NewInvariantFetch(instruction);
+ AssignInfo(loop, instruction, info);
+ return info;
}
- return info;
+ return nullptr;
}
bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
@@ -446,21 +537,21 @@ std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
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 09a0a380a1..db00f58c7b 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 @@ class HInductionVarAnalysis : public HOptimization {
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 @@ class HInductionVarAnalysis : public HOptimization {
};
enum InductionClass {
- kNone,
kInvariant,
kLinear,
kWrapAround,
- kPeriodic,
- kMonotonic
+ kPeriodic
};
enum InductionOp {
@@ -79,7 +69,7 @@ class HInductionVarAnalysis : public HOptimization {
* 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 @@ class HInductionVarAnalysis : public HOptimization {
* 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 @@ class HInductionVarAnalysis : public HOptimization {
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();
+ }
+
+ 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);
}
- inline InductionInfo* NewInductionInfo(
- InductionClass c,
- InductionOp op,
- InductionInfo* a,
- InductionInfo* b,
- HInstruction* i) {
- return new (graph_->GetArena()) InductionInfo(c, op, a, b, i);
+ 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 @@ class HInductionVarAnalysis : public HOptimization {
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);
- uint32_t global_depth_;
+ // 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 2093e3355d..b569fbe53a 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -63,7 +63,7 @@ class InductionVarAnalysisTest : public testing::Test {
// 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 @@ class InductionVarAnalysisTest : public testing::Test {
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 @@ class InductionVarAnalysisTest : public testing::Test {
// 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 @@ class InductionVarAnalysisTest : public testing::Test {
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 @@ class InductionVarAnalysisTest : public testing::Test {
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 @@ TEST_F(InductionVarAnalysisTest, ProperLoopSetup) {
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 @@ TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) {
// 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 @@ TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
// }
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());
}
}
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-21 07:43:42 +0000