Merge "Induction variable analysis (with unit tests)."
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 566d289..1db654a 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -247,6 +247,7 @@
compiler/optimizing/graph_checker_test.cc \
compiler/optimizing/graph_test.cc \
compiler/optimizing/gvn_test.cc \
+ compiler/optimizing/induction_var_analysis_test.cc \
compiler/optimizing/licm_test.cc \
compiler/optimizing/live_interval_test.cc \
compiler/optimizing/nodes_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 8b56880..ce9e367 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -71,6 +71,7 @@
optimizing/graph_checker.cc \
optimizing/graph_visualizer.cc \
optimizing/gvn.cc \
+ optimizing/induction_var_analysis.cc \
optimizing/inliner.cc \
optimizing/instruction_simplifier.cc \
optimizing/intrinsics.cc \
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
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
new file mode 100644
index 0000000..09a0a38
--- /dev/null
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -0,0 +1,171 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
+#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
+
+#include <string>
+
+#include "nodes.h"
+#include "optimization.h"
+
+namespace art {
+
+/**
+ * Induction variable analysis.
+ *
+ * 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).
+ */
+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:
+ static constexpr const char* kInductionPassName = "induction_var_analysis";
+
+ struct NodeInfo {
+ explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
+ uint32_t depth;
+ bool done;
+ };
+
+ enum InductionClass {
+ kNone,
+ kInvariant,
+ kLinear,
+ kWrapAround,
+ kPeriodic,
+ kMonotonic
+ };
+
+ enum InductionOp {
+ kNop, // no-operation: a true induction
+ kAdd,
+ kSub,
+ kNeg,
+ kMul,
+ kDiv,
+ kFetch
+ };
+
+ /**
+ * Defines a detected induction as:
+ * (1) invariant:
+ * operation: a + b, a - b, -b, a * b, a / b
+ * or
+ * fetch: fetch from HIR
+ * (2) linear:
+ * nop: a * i + b
+ * (3) wrap-around
+ * 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,
+ InductionOp op,
+ InductionInfo* a,
+ InductionInfo* b,
+ HInstruction* f)
+ : induction_class(ic),
+ operation(op),
+ op_a(a),
+ op_b(b),
+ fetch(f) {}
+ InductionClass induction_class;
+ InductionOp operation;
+ InductionInfo* op_a;
+ InductionInfo* op_b;
+ HInstruction* fetch;
+ };
+
+ inline bool IsVisitedNode(int id) const {
+ return map_.find(id) != 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);
+ }
+
+ // Methods for analysis.
+ void VisitLoop(HLoopInformation* loop);
+ void VisitNode(HLoopInformation* loop, HInstruction* instruction);
+ uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
+ void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
+ void ClassifyNonTrivial(HLoopInformation* loop);
+
+ // Transfer operations.
+ InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b);
+ InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
+ InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
+ InductionInfo* TransferNeg(InductionInfo* a);
+ InductionInfo* TransferCycleOverPhi(HInstruction* phi);
+ InductionInfo* TransferCycleOverAddSub(HLoopInformation* loop,
+ HInstruction* x,
+ HInstruction* y,
+ InductionOp op,
+ bool first);
+
+ // 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
+
+ uint32_t global_depth_;
+
+ ArenaVector<HInstruction*> stack_;
+ ArenaVector<HInstruction*> scc_;
+
+ // Mappings of instruction id to node and induction information.
+ ArenaSafeMap<int, NodeInfo> map_;
+ ArenaSafeMap<int, InductionInfo*> cycle_;
+
+ // Mapping from loop id to mapping of instruction id to induction information.
+ ArenaSafeMap<int, ArenaSafeMap<int, InductionInfo*>> induction_;
+
+ DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
new file mode 100644
index 0000000..2093e33
--- /dev/null
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -0,0 +1,514 @@
+/*
+ * 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 <regex>
+
+#include "base/arena_allocator.h"
+#include "builder.h"
+#include "gtest/gtest.h"
+#include "induction_var_analysis.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+
+namespace art {
+
+/**
+ * Fixture class for the InductionVarAnalysis tests.
+ */
+class InductionVarAnalysisTest : public testing::Test {
+ public:
+ InductionVarAnalysisTest() : pool_(), allocator_(&pool_) {
+ graph_ = CreateGraph(&allocator_);
+ }
+
+ ~InductionVarAnalysisTest() { }
+
+ // Builds single for-loop at depth d.
+ void BuildForLoop(int d, int n) {
+ ASSERT_LT(d, n);
+ loop_preheader_[d] = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(loop_preheader_[d]);
+ loop_header_[d] = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(loop_header_[d]);
+ loop_preheader_[d]->AddSuccessor(loop_header_[d]);
+ if (d < (n - 1)) {
+ BuildForLoop(d + 1, n);
+ }
+ loop_body_[d] = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(loop_body_[d]);
+ loop_body_[d]->AddSuccessor(loop_header_[d]);
+ if (d < (n - 1)) {
+ loop_header_[d]->AddSuccessor(loop_preheader_[d + 1]);
+ loop_header_[d + 1]->AddSuccessor(loop_body_[d]);
+ } else {
+ loop_header_[d]->AddSuccessor(loop_body_[d]);
+ }
+ }
+
+ // Builds a n-nested loop in CFG where each loop at depth 0 <= d < n
+ // is defined as "for (int i_d = 0; i_d < 100; i_d++)". Tests can further
+ // populate the loop with instructions to set up interesting scenarios.
+ void BuildLoopNest(int n) {
+ ASSERT_LE(n, 10);
+ graph_->SetNumberOfVRegs(n + 2);
+
+ // Build basic blocks with entry, nested loop, exit.
+ entry_ = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry_);
+ BuildForLoop(0, n);
+ exit_ = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(exit_);
+ entry_->AddSuccessor(loop_preheader_[0]);
+ loop_header_[0]->AddSuccessor(exit_);
+ graph_->SetEntryBlock(entry_);
+ 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);
+ 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());
+ 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_));
+
+ // 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_header_[d]->AddInstruction(load);
+ 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_);
+ loop_body_[d]->AddInstruction(increment_[d]);
+ loop_body_[d]->AddInstruction(
+ new (&allocator_) HStoreLocal(basic_[d], increment_[d]));
+ loop_body_[d]->AddInstruction(new (&allocator_) HGoto());
+ }
+ }
+
+ // Builds if-statement at depth d.
+ void BuildIf(int d, HBasicBlock** ifT, HBasicBlock **ifF) {
+ HBasicBlock* cond = new (&allocator_) HBasicBlock(graph_);
+ HBasicBlock* ifTrue = new (&allocator_) HBasicBlock(graph_);
+ HBasicBlock* ifFalse = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(cond);
+ graph_->AddBlock(ifTrue);
+ graph_->AddBlock(ifFalse);
+ // Conditional split.
+ loop_header_[d]->ReplaceSuccessor(loop_body_[d], cond);
+ cond->AddSuccessor(ifTrue);
+ cond->AddSuccessor(ifFalse);
+ ifTrue->AddSuccessor(loop_body_[d]);
+ ifFalse->AddSuccessor(loop_body_[d]);
+ cond->AddInstruction(new (&allocator_) HIf(parameter_));
+ *ifT = ifTrue;
+ *ifF = ifFalse;
+ }
+
+ // Inserts instruction right before increment at depth d.
+ HInstruction* InsertInstruction(HInstruction* instruction, int d) {
+ loop_body_[d]->InsertInstructionBefore(instruction, increment_[d]);
+ return instruction;
+ }
+
+ // Inserts local load at depth d.
+ HInstruction* InsertLocalLoad(HLocal* local, int d) {
+ return InsertInstruction(
+ new (&allocator_) HLoadLocal(local, Primitive::kPrimInt), d);
+ }
+
+ // Inserts local store at depth d.
+ HInstruction* InsertLocalStore(HLocal* local, HInstruction* rhs, int d) {
+ return InsertInstruction(new (&allocator_) HStoreLocal(local, rhs), d);
+ }
+
+ // Inserts an array store with given local as subscript at depth d to
+ // enable tests to inspect the computed induction at that point easily.
+ HInstruction* InsertArrayStore(HLocal* subscript, int d) {
+ HInstruction* load = InsertInstruction(
+ new (&allocator_) HLoadLocal(subscript, Primitive::kPrimInt), d);
+ return InsertInstruction(new (&allocator_) HArraySet(
+ parameter_, load, constant0_, Primitive::kPrimInt, 0), d);
+ }
+
+ // Returns loop information of loop at depth d.
+ HLoopInformation* GetLoopInfo(int d) {
+ return loop_body_[d]->GetLoopInformation();
+ }
+
+ // Performs InductionVarAnalysis (after proper set up).
+ void PerformInductionVarAnalysis() {
+ ASSERT_TRUE(graph_->TryBuildingSsa());
+ iva_ = new (&allocator_) HInductionVarAnalysis(graph_);
+ iva_->Run();
+ }
+
+ // General building fields.
+ ArenaPool pool_;
+ ArenaAllocator allocator_;
+ HGraph* graph_;
+ HInductionVarAnalysis* iva_;
+
+ // Fixed basic blocks and instructions.
+ HBasicBlock* entry_;
+ HBasicBlock* exit_;
+ HInstruction* parameter_; // "this"
+ HInstruction* constant0_;
+ HInstruction* constant1_;
+ HInstruction* constant100_;
+ HLocal* induc_; // "vreg_n", the "k"
+ HLocal* tmp_; // "vreg_n+1"
+
+ // Loop specifics.
+ HBasicBlock* loop_preheader_[10];
+ HBasicBlock* loop_header_[10];
+ HBasicBlock* loop_body_[10];
+ HInstruction* increment_[10];
+ HLocal* basic_[10]; // "vreg_d", the "i_d"
+};
+
+//
+// The actual InductionVarAnalysis tests.
+//
+
+TEST_F(InductionVarAnalysisTest, ProperLoopSetup) {
+ // Setup:
+ // for (int i_0 = 0; i_0 < 100; i_0++) {
+ // ..
+ // for (int i_9 = 0; i_9 < 100; i_9++) {
+ // }
+ // ..
+ // }
+ BuildLoopNest(10);
+ ASSERT_TRUE(graph_->TryBuildingSsa());
+ ASSERT_EQ(entry_->GetLoopInformation(), nullptr);
+ for (int d = 0; d < 1; d++) {
+ ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(),
+ (d == 0) ? nullptr
+ : loop_header_[d - 1]->GetLoopInformation());
+ ASSERT_NE(loop_header_[d]->GetLoopInformation(), nullptr);
+ ASSERT_NE(loop_body_[d]->GetLoopInformation(), nullptr);
+ ASSERT_EQ(loop_header_[d]->GetLoopInformation(),
+ loop_body_[d]->GetLoopInformation());
+ }
+ ASSERT_EQ(exit_->GetLoopInformation(), nullptr);
+}
+
+TEST_F(InductionVarAnalysisTest, FindBasicInductionVar) {
+ // Setup:
+ // for (int i = 0; i < 100; i++) {
+ // 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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindDerivedInductionVarAdd) {
+ // Setup:
+ // for (int i = 0; i < 100; i++) {
+ // k = 100 + i;
+ // a[k] = 0;
+ // }
+ BuildLoopNest(1);
+ HInstruction *add = InsertInstruction(
+ 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);
+ 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);
+ 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 *neg = InsertInstruction(
+ 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());
+}
+
+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;
+ // }
+ BuildLoopNest(1);
+ HInstruction *add = InsertInstruction(
+ 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);
+ 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());
+}
+
+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;
+ // }
+ BuildLoopNest(1);
+ HBasicBlock* ifTrue;
+ HBasicBlock* ifFalse;
+ BuildIf(0, &ifTrue, &ifFalse);
+ // True-branch.
+ HInstruction* load1 = new (&allocator_)
+ HLoadLocal(induc_, Primitive::kPrimInt);
+ ifTrue->AddInstruction(load1);
+ 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);
+ ifFalse->AddInstruction(load2);
+ 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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) {
+ // Setup:
+ // for (int i = 0; i < 100; i++) {
+ // 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);
+ ifTrue->AddInstruction(load1);
+ 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);
+ ifFalse->AddInstruction(load2);
+ 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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i = 0; i < 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);
+ 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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) {
+ // Setup:
+ // k = 0;
+ // t = 100;
+ // for (int i = 0; i < 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);
+ 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());
+}
+
+TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
+ // Setup:
+ // k = 0;
+ // for (int i_0 = 0; i_0 < 100; i_0++) {
+ // ..
+ // for (int i_9 = 0; i_9 < 100; i_9++) {
+ // k = 1 + k;
+ // a[k] = 0;
+ // }
+ // ..
+ // }
+ BuildLoopNest(10);
+ HInstruction *inc = InsertInstruction(
+ 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\\)\\)\\)");
+
+ for (int d = 0; d < 10; d++) {
+ if (d == 9) {
+ EXPECT_TRUE(std::regex_match(
+ iva_->InductionToString(GetLoopInfo(d), store->InputAt(1)), r));
+ } else {
+ EXPECT_STREQ(
+ "",
+ iva_->InductionToString(GetLoopInfo(d), store->InputAt(1)).c_str());
+ }
+ EXPECT_STREQ(
+ "((2:Constant) * i + ((1:Constant) + (2:Constant)))",
+ iva_->InductionToString(GetLoopInfo(d), increment_[d]).c_str());
+ }
+}
+
+} // namespace art