Added ability to generate induction range code.
Rationale: used by dynamic BCE (done in another CL).
Change-Id: Ia6ce75da57b5298fba74622822ae0bae69c74188
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 20492e7..fd1e334 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -20,7 +20,6 @@
#include "builder.h"
#include "gtest/gtest.h"
#include "induction_var_analysis.h"
-#include "induction_var_range.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
@@ -522,36 +521,6 @@
EXPECT_STREQ("periodic(( - (1)), (0))", GetInductionInfo(neg, 0).c_str());
}
-TEST_F(InductionVarAnalysisTest, FindRange) {
- // Setup:
- // for (int i = 0; i < 100; i++) {
- // k = i << 1;
- // k = k + 1;
- // a[k] = 0;
- // }
- BuildLoopNest(1);
- HInstruction *shl = InsertInstruction(
- new (&allocator_) HShl(Primitive::kPrimInt, InsertLocalLoad(basic_[0], 0), constant1_), 0);
- InsertLocalStore(induc_, shl, 0);
- HInstruction *add = InsertInstruction(
- new (&allocator_) HAdd(Primitive::kPrimInt, InsertLocalLoad(induc_, 0), constant1_), 0);
- InsertLocalStore(induc_, add, 0);
- HInstruction* store = InsertArrayStore(induc_, 0);
- PerformInductionVarAnalysis();
-
- EXPECT_STREQ("((2) * i + (1))", GetInductionInfo(store->InputAt(1), 0).c_str());
-
- InductionVarRange range(iva_);
- InductionVarRange::Value v_min = range.GetMinInduction(store, store->InputAt(1));
- InductionVarRange::Value v_max = range.GetMaxInduction(store, store->InputAt(1));
- ASSERT_TRUE(v_min.is_known);
- EXPECT_EQ(0, v_min.a_constant);
- EXPECT_EQ(1, v_min.b_constant);
- ASSERT_TRUE(v_max.is_known);
- EXPECT_EQ(0, v_max.a_constant);
- EXPECT_EQ(199, v_max.b_constant);
-}
-
TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) {
// Setup:
// k = 0;
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index db12819..f4842f9 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -75,6 +75,13 @@
return v;
}
+static HInstruction* Insert(HBasicBlock* preheader, HInstruction* instruction) {
+ DCHECK(preheader != nullptr);
+ DCHECK(instruction != nullptr);
+ preheader->InsertInstructionBefore(instruction, preheader->GetLastInstruction());
+ return instruction;
+}
+
//
// Public class methods.
//
@@ -94,6 +101,21 @@
return SimplifyMax(GetInduction(context, instruction, /* is_min */ false));
}
+bool InductionVarRange::CanGenerateCode(HInstruction* context,
+ HInstruction* instruction,
+ /*out*/bool* top_test) {
+ return GenerateCode(context, instruction, nullptr, nullptr, nullptr, nullptr, top_test);
+}
+
+bool InductionVarRange::GenerateCode(HInstruction* context,
+ HInstruction* instruction,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** lower,
+ /*out*/HInstruction** upper) {
+ return GenerateCode(context, instruction, graph, block, lower, upper, nullptr);
+}
+
//
// Private class methods.
//
@@ -162,15 +184,15 @@
case HInductionVarAnalysis::kFetch:
return GetFetch(info->fetch, trip, in_body, is_min);
case HInductionVarAnalysis::kTripCountInLoop:
- if (!in_body) {
- return is_min ? Value(0)
- : GetVal(info->op_b, trip, in_body, is_min); // one extra!
+ if (!in_body && !is_min) { // one extra!
+ return GetVal(info->op_b, trip, in_body, is_min);
}
FALLTHROUGH_INTENDED;
case HInductionVarAnalysis::kTripCountInBody:
- if (in_body) {
- return is_min ? Value(0)
- : SubValue(GetVal(info->op_b, trip, in_body, is_min), Value(1));
+ if (is_min) {
+ return Value(0);
+ } else if (in_body) {
+ return SubValue(GetVal(info->op_b, trip, in_body, is_min), Value(1));
}
break;
default:
@@ -256,9 +278,11 @@
bool InductionVarRange::GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t *value) {
Value v_min = GetVal(info, nullptr, false, /* is_min */ true);
Value v_max = GetVal(info, nullptr, false, /* is_min */ false);
- if (v_min.a_constant == 0 && v_max.a_constant == 0 && v_min.b_constant == v_max.b_constant) {
- *value = v_min.b_constant;
- return true;
+ if (v_min.is_known && v_max.is_known) {
+ if (v_min.a_constant == 0 && v_max.a_constant == 0 && v_min.b_constant == v_max.b_constant) {
+ *value = v_min.b_constant;
+ return true;
+ }
}
return false;
}
@@ -326,4 +350,129 @@
return Value();
}
+bool InductionVarRange::GenerateCode(HInstruction* context,
+ HInstruction* instruction,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** lower,
+ /*out*/HInstruction** upper,
+ /*out*/bool* top_test) {
+ HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
+ if (loop != nullptr) {
+ HBasicBlock* header = loop->GetHeader();
+ bool in_body = context->GetBlock() != header;
+ HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction);
+ HInductionVarAnalysis::InductionInfo* trip =
+ induction_analysis_->LookupInfo(loop, header->GetLastInstruction());
+ if (info != nullptr && trip != nullptr) {
+ if (top_test != nullptr) {
+ *top_test = trip->operation != HInductionVarAnalysis::kTripCountInLoop;
+ }
+ return
+ // Success on lower if invariant (not set), or code can be generated.
+ ((info->induction_class == HInductionVarAnalysis::kInvariant) ||
+ GenerateCode(info, trip, graph, block, lower, in_body, /* is_min */ true)) &&
+ // And success on upper.
+ GenerateCode(info, trip, graph, block, upper, in_body, /* is_min */ false);
+ }
+ }
+ return false;
+}
+
+bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ HGraph* graph, // when set, code is generated
+ HBasicBlock* block,
+ /*out*/HInstruction** result,
+ bool in_body,
+ bool is_min) {
+ if (info != nullptr) {
+ Primitive::Type type = Primitive::kPrimInt;
+ HInstruction* opa = nullptr;
+ HInstruction* opb = nullptr;
+ int32_t value = 0;
+ switch (info->induction_class) {
+ case HInductionVarAnalysis::kInvariant:
+ // Invariants.
+ switch (info->operation) {
+ case HInductionVarAnalysis::kAdd:
+ if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) &&
+ GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
+ if (graph != nullptr) {
+ *result = Insert(block, new (graph->GetArena()) HAdd(type, opa, opb));
+ }
+ return true;
+ }
+ break;
+ case HInductionVarAnalysis::kSub: // second reversed!
+ if (GenerateCode(info->op_a, trip, graph, block, &opa, in_body, is_min) &&
+ GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) {
+ if (graph != nullptr) {
+ *result = Insert(block, new (graph->GetArena()) HSub(type, opa, opb));
+ }
+ return true;
+ }
+ break;
+ case HInductionVarAnalysis::kNeg: // reversed!
+ if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) {
+ if (graph != nullptr) {
+ *result = Insert(block, new (graph->GetArena()) HNeg(type, opb));
+ }
+ return true;
+ }
+ break;
+ case HInductionVarAnalysis::kFetch:
+ if (graph != nullptr) {
+ *result = info->fetch; // already in HIR
+ }
+ return true;
+ case HInductionVarAnalysis::kTripCountInLoop:
+ if (!in_body && !is_min) { // one extra!
+ return GenerateCode(info->op_b, trip, graph, block, result, in_body, is_min);
+ }
+ FALLTHROUGH_INTENDED;
+ case HInductionVarAnalysis::kTripCountInBody:
+ if (is_min) {
+ if (graph != nullptr) {
+ *result = graph->GetIntConstant(0);
+ }
+ return true;
+ } else if (in_body) {
+ if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
+ if (graph != nullptr) {
+ *result = Insert(block,
+ new (graph->GetArena())
+ HSub(type, opb, graph->GetIntConstant(1)));
+ }
+ return true;
+ }
+ }
+ break;
+ default:
+ break;
+ }
+ break;
+ case HInductionVarAnalysis::kLinear:
+ // Linear induction a * i + b, for normalized 0 <= i < TC. Restrict to unit stride only
+ // to avoid arithmetic wrap-around situations that are hard to guard against.
+ if (GetConstant(info->op_a, &value)) {
+ if (value == 1 || value == -1) {
+ const bool is_min_a = value == 1 ? is_min : !is_min;
+ if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) &&
+ GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
+ if (graph != nullptr) {
+ *result = Insert(block, new (graph->GetArena()) HAdd(type, opa, opb));
+ }
+ return true;
+ }
+ }
+ }
+ break;
+ default: // TODO(ajcbik): add more cases
+ break;
+ }
+ }
+ return false;
+}
+
} // namespace art
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index dbdd2ee..7fa5a26 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -68,6 +68,33 @@
*/
Value GetMaxInduction(HInstruction* context, HInstruction* instruction);
+ /**
+ * Returns true if range analysis is able to generate code for the lower and upper bound
+ * expressions on the instruction in the given context. Output parameter top_test denotes
+ * whether a top test is needed to protect the trip-count expression evaluation.
+ */
+ bool CanGenerateCode(HInstruction* context, HInstruction* instruction, /*out*/bool* top_test);
+
+ /**
+ * Generates the actual code in the HIR for the lower and upper bound expressions on the
+ * instruction in the given context. Code for the lower and upper bound expression are
+ * generated in given block and graph and are returned in lower and upper, respectively.
+ * For a loop invariant, lower is not set.
+ *
+ * For example, given expression x+i with range [0, 5] for i, calling this method
+ * will generate the following sequence:
+ *
+ * block:
+ * lower: add x, 0
+ * upper: add x, 5
+ */
+ bool GenerateCode(HInstruction* context,
+ HInstruction* instruction,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** lower,
+ /*out*/HInstruction** upper);
+
private:
//
// Private helper methods.
@@ -102,6 +129,27 @@
static Value DivValue(Value v1, Value v2);
static Value MergeVal(Value v1, Value v2, bool is_min);
+ /**
+ * Generates code for lower/upper expression in the HIR. Returns true on success.
+ * With graph == nullptr, the method can be used to determine if code generation
+ * would be successful without generating actual code yet.
+ */
+ bool GenerateCode(HInstruction* context,
+ HInstruction* instruction,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** lower,
+ /*out*/HInstruction** upper,
+ bool* top_test);
+
+ static bool GenerateCode(HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** result,
+ bool in_body,
+ bool is_min);
+
/** Results of prior induction variable analysis. */
HInductionVarAnalysis *induction_analysis_;
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index 4497a88..56f661e 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -49,12 +49,52 @@
/** Constructs bare minimum graph. */
void BuildGraph() {
graph_->SetNumberOfVRegs(1);
- HBasicBlock* entry_block = new (&allocator_) HBasicBlock(graph_);
- HBasicBlock* exit_block = new (&allocator_) HBasicBlock(graph_);
- graph_->AddBlock(entry_block);
- graph_->AddBlock(exit_block);
- graph_->SetEntryBlock(entry_block);
- graph_->SetExitBlock(exit_block);
+ entry_block_ = new (&allocator_) HBasicBlock(graph_);
+ exit_block_ = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry_block_);
+ graph_->AddBlock(exit_block_);
+ graph_->SetEntryBlock(entry_block_);
+ graph_->SetExitBlock(exit_block_);
+ }
+
+ /** Constructs loop with given upper bound. */
+ void BuildLoop(HInstruction* upper) {
+ // Control flow.
+ loop_preheader_ = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(loop_preheader_);
+ HBasicBlock* loop_header = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(loop_header);
+ HBasicBlock* loop_body = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(loop_body);
+ entry_block_->AddSuccessor(loop_preheader_);
+ loop_preheader_->AddSuccessor(loop_header);
+ loop_header->AddSuccessor(loop_body);
+ loop_header->AddSuccessor(exit_block_);
+ loop_body->AddSuccessor(loop_header);
+ // Instructions.
+ HLocal* induc = new (&allocator_) HLocal(0);
+ entry_block_->AddInstruction(induc);
+ loop_preheader_->AddInstruction(
+ new (&allocator_) HStoreLocal(induc, graph_->GetIntConstant(0))); // i = 0
+ loop_preheader_->AddInstruction(new (&allocator_) HGoto());
+ HInstruction* load = new (&allocator_) HLoadLocal(induc, Primitive::kPrimInt);
+ loop_header->AddInstruction(load);
+ condition_ = new (&allocator_) HLessThan(load, upper);
+ loop_header->AddInstruction(condition_);
+ loop_header->AddInstruction(new (&allocator_) HIf(condition_)); // i < u
+ load = new (&allocator_) HLoadLocal(induc, Primitive::kPrimInt);
+ loop_body->AddInstruction(load);
+ increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, load, graph_->GetIntConstant(1));
+ loop_body->AddInstruction(increment_);
+ loop_body->AddInstruction(new (&allocator_) HStoreLocal(induc, increment_)); // i++
+ loop_body->AddInstruction(new (&allocator_) HGoto());
+ exit_block_->AddInstruction(new (&allocator_) HReturnVoid());
+ }
+
+ /** Performs induction variable analysis. */
+ void PerformInductionVarAnalysis() {
+ ASSERT_TRUE(graph_->TryBuildingSsa());
+ iva_->Run();
}
/** Constructs an invariant. */
@@ -146,15 +186,20 @@
ArenaPool pool_;
ArenaAllocator allocator_;
HGraph* graph_;
+ HBasicBlock* entry_block_;
+ HBasicBlock* exit_block_;
+ HBasicBlock* loop_preheader_;
HInductionVarAnalysis* iva_;
- // Two dummy instructions.
+ // Instructions.
+ HInstruction* condition_;
+ HInstruction* increment_;
HReturnVoid x_;
HReturnVoid y_;
};
//
-// The actual InductionVarRange tests.
+// Tests on static methods.
//
TEST_F(InductionVarRangeTest, GetMinMaxNull) {
@@ -349,4 +394,81 @@
ExpectEqual(Value(), MaxValue(Value(55), Value(&y_, 1, -50)));
}
+//
+// Tests on instance methods.
+//
+
+TEST_F(InductionVarRangeTest, FindRangeConstantTripCount) {
+ BuildLoop(graph_->GetIntConstant(1000));
+ PerformInductionVarAnalysis();
+ InductionVarRange range(iva_);
+
+ // In context of header: known.
+ ExpectEqual(Value(0), range.GetMinInduction(condition_, condition_->InputAt(0)));
+ ExpectEqual(Value(1000), range.GetMaxInduction(condition_, condition_->InputAt(0)));
+
+ // In context of loop-body: known.
+ ExpectEqual(Value(0), range.GetMinInduction(increment_, condition_->InputAt(0)));
+ ExpectEqual(Value(999), range.GetMaxInduction(increment_, condition_->InputAt(0)));
+ ExpectEqual(Value(1), range.GetMinInduction(increment_, increment_));
+ ExpectEqual(Value(1000), range.GetMaxInduction(increment_, increment_));
+}
+
+TEST_F(InductionVarRangeTest, FindRangeSymbolicTripCount) {
+ HInstruction* parameter = new (&allocator_) HParameterValue(0, Primitive::kPrimInt);
+ entry_block_->AddInstruction(parameter);
+ BuildLoop(parameter);
+ PerformInductionVarAnalysis();
+ InductionVarRange range(iva_);
+
+ // In context of header: full range unknown.
+ ExpectEqual(Value(0), range.GetMinInduction(condition_, condition_->InputAt(0)));
+ ExpectEqual(Value(), range.GetMaxInduction(condition_, condition_->InputAt(0)));
+
+ // In context of loop-body: known.
+ ExpectEqual(Value(0), range.GetMinInduction(increment_, condition_->InputAt(0)));
+ ExpectEqual(Value(parameter, 1, -1), range.GetMaxInduction(increment_, condition_->InputAt(0)));
+ ExpectEqual(Value(1), range.GetMinInduction(increment_, increment_));
+ ExpectEqual(Value(parameter, 1, 0), range.GetMaxInduction(increment_, increment_));
+}
+
+TEST_F(InductionVarRangeTest, CodeGeneration) {
+ HInstruction* parameter = new (&allocator_) HParameterValue(0, Primitive::kPrimInt);
+ entry_block_->AddInstruction(parameter);
+ BuildLoop(parameter);
+ PerformInductionVarAnalysis();
+ InductionVarRange range(iva_);
+
+ HInstruction* lower = nullptr;
+ HInstruction* upper = nullptr;
+ bool top_test = false;
+
+ // Can generate code in context of loop-body only.
+ EXPECT_FALSE(range.CanGenerateCode(condition_, condition_->InputAt(0), &top_test));
+ ASSERT_TRUE(range.CanGenerateCode(increment_, condition_->InputAt(0), &top_test));
+ EXPECT_TRUE(top_test);
+
+ // Generates code.
+ EXPECT_TRUE(range.GenerateCode(
+ increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper));
+
+ // Verify lower is 0+0.
+ ASSERT_TRUE(lower != nullptr);
+ ASSERT_TRUE(lower->IsAdd());
+ ASSERT_TRUE(lower->InputAt(0)->IsIntConstant());
+ EXPECT_EQ(0, lower->InputAt(0)->AsIntConstant()->GetValue());
+ ASSERT_TRUE(lower->InputAt(1)->IsIntConstant());
+ EXPECT_EQ(0, lower->InputAt(1)->AsIntConstant()->GetValue());
+
+ // Verify upper is (V-1)+0
+ ASSERT_TRUE(upper != nullptr);
+ ASSERT_TRUE(upper->IsAdd());
+ ASSERT_TRUE(upper->InputAt(0)->IsSub());
+ EXPECT_TRUE(upper->InputAt(0)->InputAt(0)->IsParameterValue());
+ ASSERT_TRUE(upper->InputAt(0)->InputAt(1)->IsIntConstant());
+ EXPECT_EQ(1, upper->InputAt(0)->InputAt(1)->AsIntConstant()->GetValue());
+ ASSERT_TRUE(upper->InputAt(1)->IsIntConstant());
+ EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
+}
+
} // namespace art
