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_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