Induction variable analysis (with unit tests).
Rationale:
Induction variable analysis forms the basis of a wide
variety of compiler optimizations. This implementation
finds induction variables using the elegant SSA-based
algorithm defined by [Gerlek et al.].
Change-Id: I79b8dce33ffb8b283c179699a8dff5bd196f75b2
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
new file mode 100644
index 0000000..8aaec68
--- /dev/null
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -0,0 +1,479 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "induction_var_analysis.h"
+
+namespace art {
+
+/**
+ * Returns true if instruction is invariant within the given loop.
+ */
+static bool IsLoopInvariant(HLoopInformation* loop, HInstruction* instruction) {
+ HLoopInformation* other_loop = instruction->GetBlock()->GetLoopInformation();
+ if (other_loop != loop) {
+ // If instruction does not occur in same loop, it is invariant
+ // if it appears in an outer loop (including no loop at all).
+ return other_loop == nullptr || loop->IsIn(*other_loop);
+ }
+ return false;
+}
+
+/**
+ * Returns true if instruction is proper entry-phi-operation for given loop
+ * (referred to as mu-operation in Gerlek's paper).
+ */
+static bool IsEntryPhi(HLoopInformation* loop, HInstruction* instruction) {
+ return
+ instruction->IsPhi() &&
+ instruction->InputCount() == 2 &&
+ instruction->GetBlock() == loop->GetHeader();
+}
+
+//
+// Class methods.
+//
+
+HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph)
+ : HOptimization(graph, kInductionPassName),
+ 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()) {
+}
+
+void HInductionVarAnalysis::Run() {
+ // Detects sequence variables (generalized induction variables) during an
+ // inner-loop-first traversal of all loops using Gerlek's algorithm.
+ for (HPostOrderIterator it_graph(*graph_); !it_graph.Done(); it_graph.Advance()) {
+ HBasicBlock* graph_block = it_graph.Current();
+ if (graph_block->IsLoopHeader()) {
+ VisitLoop(graph_block->GetLoopInformation());
+ }
+ }
+}
+
+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());
+ map_.clear();
+
+ for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) {
+ HBasicBlock* loop_block = it_loop.Current();
+ CHECK(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())) {
+ VisitNode(loop, instruction);
+ }
+ }
+ for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) {
+ HInstruction* instruction = it.Current();
+ if (!IsVisitedNode(instruction->GetId())) {
+ VisitNode(loop, instruction);
+ }
+ }
+ }
+
+ CHECK(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));
+ stack_.push_back(instruction);
+
+ // Visit all descendants.
+ uint32_t low = d1;
+ for (size_t i = 0, count = instruction->InputCount(); i < count; ++i) {
+ low = std::min(low, VisitDescendant(loop, instruction->InputAt(i)));
+ }
+
+ // Lower or found SCC?
+ if (low < d1) {
+ map_.find(id)->second.depth = low;
+ } else {
+ scc_.clear();
+ cycle_.clear();
+
+ // Pop the stack to build the SCC for classification.
+ while (!stack_.empty()) {
+ HInstruction* x = stack_.back();
+ scc_.push_back(x);
+ stack_.pop_back();
+ map_.find(x->GetId())->second.done = true;
+ if (x == instruction) {
+ break;
+ }
+ }
+
+ // Classify the SCC.
+ if (scc_.size() == 1 && !IsEntryPhi(loop, scc_[0])) {
+ ClassifyTrivial(loop, scc_[0]);
+ } else {
+ ClassifyNonTrivial(loop);
+ }
+
+ scc_.clear();
+ cycle_.clear();
+ }
+}
+
+uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) {
+ // If the definition is either outside the loop (loop invariant entry value)
+ // or assigned in inner loop (inner exit value), the traversal stops.
+ HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation();
+ if (otherLoop != loop) {
+ return global_depth_;
+ }
+
+ // Inspect descendant node.
+ const int id = instruction->GetId();
+ if (!IsVisitedNode(id)) {
+ VisitNode(loop, instruction);
+ return map_.find(id)->second.depth;
+ } else {
+ auto it = map_.find(id);
+ return it->second.done ? global_depth_ : it->second.depth;
+ }
+}
+
+void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
+ InductionInfo* info = nullptr;
+ if (instruction->IsPhi()) {
+ for (size_t i = 1, count = instruction->InputCount(); i < count; i++) {
+ info = TransferPhi(LookupInfo(loop, instruction->InputAt(0)),
+ LookupInfo(loop, instruction->InputAt(i)));
+ }
+ } else if (instruction->IsAdd()) {
+ info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
+ LookupInfo(loop, instruction->InputAt(1)), kAdd);
+ } else if (instruction->IsSub()) {
+ info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
+ LookupInfo(loop, instruction->InputAt(1)), kSub);
+ } else if (instruction->IsMul()) {
+ info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
+ LookupInfo(loop, instruction->InputAt(1)));
+ } else if (instruction->IsNeg()) {
+ info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)));
+ }
+
+ // Successfully classified?
+ if (info != nullptr) {
+ AssignInfo(loop, instruction, info);
+ }
+}
+
+void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
+ const size_t size = scc_.size();
+ CHECK_GE(size, 1u);
+ HInstruction* phi = scc_[size - 1];
+ if (!IsEntryPhi(loop, phi)) {
+ return;
+ }
+ HInstruction* external = phi->InputAt(0);
+ HInstruction* internal = phi->InputAt(1);
+ InductionInfo* initial = LookupInfo(loop, external);
+ if (initial == nullptr || initial->induction_class != kInvariant) {
+ return;
+ }
+
+ // Singleton entry-phi-operation may be a wrap-around induction.
+ if (size == 1) {
+ InductionInfo* update = LookupInfo(loop, internal);
+ if (update != nullptr) {
+ AssignInfo(loop, phi, NewInductionInfo(kWrapAround, kNop, initial, update, nullptr));
+ }
+ return;
+ }
+
+ // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
+ // temporary meaning to its nodes.
+ cycle_.Overwrite(phi->GetId(), nullptr);
+ for (size_t i = 0; i < size - 1; i++) {
+ HInstruction* operation = 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 (update == nullptr) {
+ return;
+ }
+ cycle_.Overwrite(operation->GetId(), 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]);
+ }
+ }
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(InductionInfo* a,
+ InductionInfo* b) {
+ // Transfer over a phi: if both inputs are identical, result is input.
+ if (InductionEqual(a, b)) {
+ return a;
+ }
+ return nullptr;
+}
+
+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.
+ 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);
+ } 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 nullptr;
+}
+
+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.
+ 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 nullptr;
+}
+
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) {
+ // Transfer over a unary negation: invariant or linear input
+ // yields a similar, but negated 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 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());
+ 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)) {
+ 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);
+ }
+ 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;
+ }
+ }
+ 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);
+ }
+ return info;
+}
+
+bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1,
+ InductionInfo* info2) {
+ // Test structural equality only, without accounting for simplifications.
+ if (info1 != nullptr && info2 != nullptr) {
+ return
+ info1->induction_class == info2->induction_class &&
+ info1->operation == info2->operation &&
+ info1->fetch == info2->fetch &&
+ InductionEqual(info1->op_a, info2->op_a) &&
+ InductionEqual(info1->op_b, info2->op_b);
+ }
+ // Otherwise only two nullptrs are considered equal.
+ return info1 == info2;
+}
+
+std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) {
+ if (info != nullptr) {
+ if (info->induction_class == kInvariant) {
+ std::string inv = "(";
+ inv += InductionToString(info->op_a);
+ switch (info->operation) {
+ case kNop: inv += " ? "; break;
+ case kAdd: inv += " + "; break;
+ case kSub:
+ 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();
+ break;
+ }
+ inv += InductionToString(info->op_b);
+ return inv + ")";
+ } else {
+ CHECK(info->operation == kNop);
+ if (info->induction_class == kLinear) {
+ return "(" + InductionToString(info->op_a) + " * i + " +
+ InductionToString(info->op_b) + ")";
+ } else if (info->induction_class == kWrapAround) {
+ return "wrap(" + InductionToString(info->op_a) + ", " +
+ InductionToString(info->op_b) + ")";
+ } else if (info->induction_class == kPeriodic) {
+ return "periodic(" + InductionToString(info->op_a) + ", " +
+ InductionToString(info->op_b) + ")";
+ }
+ }
+ }
+ return "";
+}
+
+} // namespace art