Added ability to generate last-value of linear induction.
Also added utility to update fetches in induction nodes.
Rationale:
This is a first step towards the larger CL that introduces
a new loop optimization framework in the optimizing compiler
(see https://android-review.googlesource.com/#/c/271392/3).
Change-Id: Ibecd674c8146d9665340e68718c498555646129a
Tests: induction_var_range_test
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 8aefd9e..994d394 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -887,7 +887,7 @@
bool needs_finite_test = false;
bool needs_taken_test = false;
if (DynamicBCESeemsProfitable(loop, bounds_check->GetBlock()) &&
- induction_range_.CanGenerateCode(
+ induction_range_.CanGenerateRange(
bounds_check, index, &needs_finite_test, &needs_taken_test) &&
CanHandleInfiniteLoop(loop, index, needs_finite_test) &&
// Do this test last, since it may generate code.
@@ -1403,10 +1403,10 @@
// whether code generation on the original and, thus, related bounds check was possible.
// It handles either loop invariants (lower is not set) or unit strides.
if (other_c == max_c) {
- induction_range_.GenerateRangeCode(
+ induction_range_.GenerateRange(
other_bounds_check, other_index, GetGraph(), block, &max_lower, &max_upper);
} else if (other_c == min_c && base != nullptr) {
- induction_range_.GenerateRangeCode(
+ induction_range_.GenerateRange(
other_bounds_check, other_index, GetGraph(), block, &min_lower, &min_upper);
}
ReplaceInstruction(other_bounds_check, other_index);
@@ -1699,11 +1699,8 @@
// Insert the taken-test to see if the loop body is entered. If the
// loop isn't entered at all, it jumps around the deoptimization block.
if_block->AddInstruction(new (GetGraph()->GetArena()) HGoto()); // placeholder
- HInstruction* condition = nullptr;
- induction_range_.GenerateTakenTest(header->GetLastInstruction(),
- GetGraph(),
- if_block,
- &condition);
+ HInstruction* condition = induction_range_.GenerateTakenTest(
+ header->GetLastInstruction(), GetGraph(), if_block);
DCHECK(condition != nullptr);
if_block->RemoveInstruction(if_block->GetLastInstruction());
if_block->AddInstruction(new (GetGraph()->GetArena()) HIf(condition));
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 5e587e0..18e6f5c 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -143,42 +143,129 @@
// Find range.
chase_hint_ = chase_hint;
bool in_body = context->GetBlock() != loop->GetHeader();
+ int64_t stride_value = 0;
*min_val = GetVal(info, trip, in_body, /* is_min */ true);
*max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min */ false));
- *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
+ *needs_finite_test = NeedsTripCount(info, &stride_value) && IsUnsafeTripCount(trip);
return true;
}
-bool InductionVarRange::CanGenerateCode(HInstruction* context,
- HInstruction* instruction,
- /*out*/bool* needs_finite_test,
- /*out*/bool* needs_taken_test) {
+bool InductionVarRange::CanGenerateRange(HInstruction* context,
+ HInstruction* instruction,
+ /*out*/bool* needs_finite_test,
+ /*out*/bool* needs_taken_test) {
+ bool is_last_value = false;
+ int64_t stride_value = 0;
return GenerateCode(context,
instruction,
- nullptr, nullptr, nullptr, nullptr, nullptr, // nothing generated yet
+ is_last_value,
+ nullptr,
+ nullptr,
+ nullptr,
+ nullptr,
+ nullptr, // nothing generated yet
+ &stride_value,
needs_finite_test,
- needs_taken_test);
+ needs_taken_test)
+ && (stride_value == -1 ||
+ stride_value == 0 ||
+ stride_value == 1); // avoid wrap-around anomalies.
}
-void InductionVarRange::GenerateRangeCode(HInstruction* context,
- HInstruction* instruction,
- HGraph* graph,
- HBasicBlock* block,
- /*out*/HInstruction** lower,
- /*out*/HInstruction** upper) {
+void InductionVarRange::GenerateRange(HInstruction* context,
+ HInstruction* instruction,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** lower,
+ /*out*/HInstruction** upper) {
+ bool is_last_value = false;
+ int64_t s = 0;
bool b1, b2; // unused
- if (!GenerateCode(context, instruction, graph, block, lower, upper, nullptr, &b1, &b2)) {
- LOG(FATAL) << "Failed precondition: GenerateCode()";
+ if (!GenerateCode(context,
+ instruction,
+ is_last_value,
+ graph,
+ block,
+ lower,
+ upper,
+ nullptr,
+ &s,
+ &b1,
+ &b2)) {
+ LOG(FATAL) << "Failed precondition: CanGenerateRange()";
}
}
-void InductionVarRange::GenerateTakenTest(HInstruction* context,
- HGraph* graph,
- HBasicBlock* block,
- /*out*/HInstruction** taken_test) {
+HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context,
+ HGraph* graph,
+ HBasicBlock* block) {
+ HInstruction* taken_test = nullptr;
+ bool is_last_value = false;
+ int64_t stride_value = 0;
bool b1, b2; // unused
- if (!GenerateCode(context, context, graph, block, nullptr, nullptr, taken_test, &b1, &b2)) {
- LOG(FATAL) << "Failed precondition: GenerateCode()";
+ if (!GenerateCode(context,
+ context,
+ is_last_value,
+ graph,
+ block,
+ nullptr,
+ nullptr,
+ &taken_test,
+ &stride_value,
+ &b1,
+ &b2)) {
+ LOG(FATAL) << "Failed precondition: CanGenerateRange()";
+ }
+ return taken_test;
+}
+
+bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) {
+ bool is_last_value = true;
+ int64_t stride_value = 0;
+ bool needs_finite_test = false;
+ bool needs_taken_test = false;
+ return GenerateCode(instruction,
+ instruction,
+ is_last_value,
+ nullptr,
+ nullptr,
+ nullptr,
+ nullptr,
+ nullptr, // nothing generated yet
+ &stride_value, &needs_finite_test, &needs_taken_test)
+ && !needs_finite_test && !needs_taken_test;
+}
+
+HInstruction* InductionVarRange::GenerateLastValue(HInstruction* instruction,
+ HGraph* graph,
+ HBasicBlock* block) {
+ HInstruction* last_value = nullptr;
+ bool is_last_value = true;
+ int64_t stride_value = 0;
+ bool b1, b2; // unused
+ if (!GenerateCode(instruction,
+ instruction,
+ is_last_value,
+ graph,
+ block,
+ &last_value,
+ &last_value,
+ nullptr,
+ &stride_value,
+ &b1,
+ &b2)) {
+ LOG(FATAL) << "Failed precondition: CanGenerateLastValue()";
+ }
+ return last_value;
+}
+
+void InductionVarRange::Replace(HInstruction* instruction,
+ HInstruction* fetch,
+ HInstruction* replacement) {
+ for (HLoopInformation* lp = instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop
+ lp != nullptr;
+ lp = lp->GetPreHeader()->GetLoopInformation()) {
+ ReplaceInduction(induction_analysis_->LookupInfo(lp, instruction), fetch, replacement);
}
}
@@ -260,12 +347,13 @@
return false;
}
-bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const {
+bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info,
+ int64_t* stride_value) const {
if (info != nullptr) {
if (info->induction_class == HInductionVarAnalysis::kLinear) {
- return true;
+ return IsConstant(info->op_a, kExact, stride_value);
} else if (info->induction_class == HInductionVarAnalysis::kWrapAround) {
- return NeedsTripCount(info->op_b);
+ return NeedsTripCount(info->op_b, stride_value);
}
}
return false;
@@ -618,11 +706,13 @@
bool InductionVarRange::GenerateCode(HInstruction* context,
HInstruction* instruction,
+ bool is_last_value,
HGraph* graph,
HBasicBlock* block,
/*out*/HInstruction** lower,
/*out*/HInstruction** upper,
/*out*/HInstruction** taken_test,
+ /*out*/int64_t* stride_value,
/*out*/bool* needs_finite_test,
/*out*/bool* needs_taken_test) const {
HLoopInformation* loop = nullptr;
@@ -637,8 +727,19 @@
// code does not use the trip-count explicitly (since there could be an implicit relation
// between e.g. an invariant subscript and a not-taken condition).
bool in_body = context->GetBlock() != loop->GetHeader();
- *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
+ *stride_value = 0;
+ *needs_finite_test = NeedsTripCount(info, stride_value) && IsUnsafeTripCount(trip);
*needs_taken_test = IsBodyTripCount(trip);
+ // Handle last value request.
+ if (is_last_value) {
+ if (info->induction_class != HInductionVarAnalysis::kLinear) {
+ return false;
+ } else if (*stride_value > 0) {
+ lower = nullptr;
+ } else {
+ upper = nullptr;
+ }
+ }
// Code generation for taken test: generate the code when requested or otherwise analyze
// if code generation is feasible when taken test is needed.
if (taken_test != nullptr) {
@@ -666,6 +767,10 @@
bool in_body,
bool is_min) const {
if (info != nullptr) {
+ // If during codegen, the result is not needed (nullptr), simply return success.
+ if (graph != nullptr && result == nullptr) {
+ return true;
+ }
// Verify type safety.
Primitive::Type type = Primitive::kPrimInt;
if (info->type != type) {
@@ -757,25 +862,28 @@
}
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.
+ // Linear induction a * i + b, for normalized 0 <= i < TC. For ranges, this should
+ // be restricted to a unit stride to avoid arithmetic wrap-around situations that
+ // are harder to guard against. For a last value, requesting min/max based on any
+ // stride yields right value.
int64_t stride_value = 0;
if (IsConstant(info->op_a, kExact, &stride_value)) {
- if (stride_value == 1 || stride_value == -1) {
- const bool is_min_a = stride_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) {
- HInstruction* oper;
- if (stride_value == 1) {
- oper = new (graph->GetArena()) HAdd(type, opa, opb);
- } else {
- oper = new (graph->GetArena()) HSub(type, opb, opa);
- }
- *result = Insert(block, oper);
+ const bool is_min_a = stride_value >= 0 ? 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) {
+ HInstruction* oper;
+ if (stride_value == 1) {
+ oper = new (graph->GetArena()) HAdd(type, opa, opb);
+ } else if (stride_value == -1) {
+ oper = new (graph->GetArena()) HSub(type, opb, opa);
+ } else {
+ HInstruction* mul = new (graph->GetArena()) HMul(type, graph->GetIntConstant(stride_value), opa);
+ oper = new (graph->GetArena()) HAdd(type, Insert(block, mul), opb);
}
- return true;
+ *result = Insert(block, oper);
}
+ return true;
}
}
break;
@@ -800,4 +908,18 @@
return false;
}
+void InductionVarRange::ReplaceInduction(HInductionVarAnalysis::InductionInfo* info,
+ HInstruction* fetch,
+ HInstruction* replacement) {
+ if (info != nullptr) {
+ if (info->induction_class == HInductionVarAnalysis::kInvariant &&
+ info->operation == HInductionVarAnalysis::kFetch &&
+ info->fetch == fetch) {
+ info->fetch = replacement;
+ }
+ ReplaceInduction(info->op_a, fetch, replacement);
+ ReplaceInduction(info->op_b, fetch, replacement);
+ }
+}
+
} // namespace art
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 00aaa16..63850b3 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -76,10 +76,10 @@
* and need_taken test flags denote if an additional finite-test and/or taken-test
* are needed to protect the range evaluation inside its loop.
*/
- bool CanGenerateCode(HInstruction* context,
- HInstruction* instruction,
- /*out*/ bool* needs_finite_test,
- /*out*/ bool* needs_taken_test);
+ bool CanGenerateRange(HInstruction* context,
+ HInstruction* instruction,
+ /*out*/ bool* needs_finite_test,
+ /*out*/ bool* needs_taken_test);
/**
* Generates the actual code in the HIR for the lower and upper bound expressions on the
@@ -94,25 +94,42 @@
* lower: add x, 0
* upper: add x, 5
*
- * Precondition: CanGenerateCode() returns true.
+ * Precondition: CanGenerateRange() returns true.
*/
- void GenerateRangeCode(HInstruction* context,
- HInstruction* instruction,
- HGraph* graph,
- HBasicBlock* block,
- /*out*/ HInstruction** lower,
- /*out*/ HInstruction** upper);
+ void GenerateRange(HInstruction* context,
+ HInstruction* instruction,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/ HInstruction** lower,
+ /*out*/ HInstruction** upper);
/**
* Generates explicit taken-test for the loop in the given context. Code is generated in
- * given block and graph. The taken-test is returned in parameter test.
+ * given block and graph. Returns generated taken-test.
*
- * Precondition: CanGenerateCode() returns true and needs_taken_test is set.
+ * Precondition: CanGenerateRange() returns true and needs_taken_test is set.
*/
- void GenerateTakenTest(HInstruction* context,
- HGraph* graph,
- HBasicBlock* block,
- /*out*/ HInstruction** taken_test);
+ HInstruction* GenerateTakenTest(HInstruction* context, HGraph* graph, HBasicBlock* block);
+
+ /**
+ * Returns true if induction analysis is able to generate code for last value of
+ * the given instruction inside the closest enveloping loop.
+ */
+ bool CanGenerateLastValue(HInstruction* instruction);
+
+ /**
+ * Generates last value of the given instruction in the closest enveloping loop.
+ * Code is generated in given block and graph. Returns generated last value.
+ *
+ * Precondition: CanGenerateLastValue() returns true.
+ */
+ HInstruction* GenerateLastValue(HInstruction* instruction, HGraph* graph, HBasicBlock* block);
+
+ /**
+ * Updates all matching fetches with the given replacement in all induction information
+ * that is associated with the given instruction.
+ */
+ void Replace(HInstruction* instruction, HInstruction* fetch, HInstruction* replacement);
private:
/*
@@ -140,7 +157,8 @@
/*out*/ HInductionVarAnalysis::InductionInfo** trip) const;
bool HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const;
- bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const;
+ bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info,
+ /*out*/ int64_t* stride_value) const;
bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
bool IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
@@ -186,17 +204,19 @@
Value MergeVal(Value v1, Value v2, bool is_min) const;
/**
- * Generates code for lower/upper/taken-test in the HIR. Returns true on success.
- * With values nullptr, the method can be used to determine if code generation
+ * Generates code for lower/upper/taken-test or last value in the HIR. Returns true on
+ * success. With values 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,
+ bool is_last_val,
HGraph* graph,
HBasicBlock* block,
/*out*/ HInstruction** lower,
/*out*/ HInstruction** upper,
/*out*/ HInstruction** taken_test,
+ /*out*/ int64_t* stride_value,
/*out*/ bool* needs_finite_test,
/*out*/ bool* needs_taken_test) const;
@@ -208,6 +228,10 @@
bool in_body,
bool is_min) const;
+ void ReplaceInduction(HInductionVarAnalysis::InductionInfo* info,
+ HInstruction* fetch,
+ HInstruction* replacement);
+
/** 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 4ea170f..8bbdd4a 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -75,34 +75,34 @@
// 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);
+ loop_header_ = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(loop_header_);
+ loop_body_ = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(loop_body_);
HBasicBlock* return_block = new (&allocator_) HBasicBlock(graph_);
graph_->AddBlock(return_block);
entry_block_->AddSuccessor(loop_preheader_);
- loop_preheader_->AddSuccessor(loop_header);
- loop_header->AddSuccessor(loop_body);
- loop_header->AddSuccessor(return_block);
- loop_body->AddSuccessor(loop_header);
+ loop_preheader_->AddSuccessor(loop_header_);
+ loop_header_->AddSuccessor(loop_body_);
+ loop_header_->AddSuccessor(return_block);
+ loop_body_->AddSuccessor(loop_header_);
return_block->AddSuccessor(exit_block_);
// Instructions.
loop_preheader_->AddInstruction(new (&allocator_) HGoto());
HPhi* phi = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
- loop_header->AddPhi(phi);
+ loop_header_->AddPhi(phi);
phi->AddInput(graph_->GetIntConstant(lower)); // i = l
if (stride > 0) {
condition_ = new (&allocator_) HLessThan(phi, upper); // i < u
} else {
condition_ = new (&allocator_) HGreaterThan(phi, upper); // i > u
}
- loop_header->AddInstruction(condition_);
- loop_header->AddInstruction(new (&allocator_) HIf(condition_));
+ loop_header_->AddInstruction(condition_);
+ loop_header_->AddInstruction(new (&allocator_) HIf(condition_));
increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, phi, graph_->GetIntConstant(stride));
- loop_body->AddInstruction(increment_); // i += s
+ loop_body_->AddInstruction(increment_); // i += s
phi->AddInput(increment_);
- loop_body->AddInstruction(new (&allocator_) HGoto());
+ loop_body_->AddInstruction(new (&allocator_) HGoto());
return_block->AddInstruction(new (&allocator_) HReturnVoid());
exit_block_->AddInstruction(new (&allocator_) HExit());
}
@@ -192,7 +192,8 @@
//
bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
- return range_.NeedsTripCount(info);
+ int64_t s = 0;
+ return range_.NeedsTripCount(info, &s);
}
bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
@@ -251,6 +252,8 @@
HBasicBlock* entry_block_;
HBasicBlock* exit_block_;
HBasicBlock* loop_preheader_;
+ HBasicBlock* loop_header_;
+ HBasicBlock* loop_body_;
HInductionVarAnalysis* iva_;
InductionVarRange range_;
@@ -600,15 +603,19 @@
Value v1, v2;
bool needs_finite_test = true;
+ bool needs_taken_test = true;
+
+ HInstruction* phi = condition_->InputAt(0);
+ HInstruction* exit = exit_block_->GetLastInstruction();
// In context of header: known.
- range_.GetInductionRange(condition_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(1000), v2);
// In context of loop-body: known.
- range_.GetInductionRange(increment_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(999), v2);
@@ -616,6 +623,20 @@
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(1000), v2);
+
+ // Induction vs. no-induction.
+ EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test));
+ EXPECT_TRUE(range_.CanGenerateLastValue(phi));
+ EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test));
+ EXPECT_FALSE(range_.CanGenerateLastValue(exit));
+
+ // Last value (unsimplified).
+ HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_);
+ ASSERT_TRUE(last->IsAdd());
+ ASSERT_TRUE(last->InputAt(0)->IsIntConstant());
+ EXPECT_EQ(1000, last->InputAt(0)->AsIntConstant()->GetValue());
+ ASSERT_TRUE(last->InputAt(1)->IsIntConstant());
+ EXPECT_EQ(0, last->InputAt(1)->AsIntConstant()->GetValue());
}
TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
@@ -624,15 +645,19 @@
Value v1, v2;
bool needs_finite_test = true;
+ bool needs_taken_test = true;
+
+ HInstruction* phi = condition_->InputAt(0);
+ HInstruction* exit = exit_block_->GetLastInstruction();
// In context of header: known.
- range_.GetInductionRange(condition_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(1000), v2);
// In context of loop-body: known.
- range_.GetInductionRange(increment_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(1000), v2);
@@ -640,6 +665,25 @@
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(999), v2);
+
+ // Induction vs. no-induction.
+ EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test));
+ EXPECT_TRUE(range_.CanGenerateLastValue(phi));
+ EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test));
+ EXPECT_FALSE(range_.CanGenerateLastValue(exit));
+
+ // Last value (unsimplified).
+ HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_);
+ ASSERT_TRUE(last->IsSub());
+ ASSERT_TRUE(last->InputAt(0)->IsIntConstant());
+ EXPECT_EQ(1000, last->InputAt(0)->AsIntConstant()->GetValue());
+ ASSERT_TRUE(last->InputAt(1)->IsNeg());
+ last = last->InputAt(1)->InputAt(0);
+ ASSERT_TRUE(last->IsSub());
+ ASSERT_TRUE(last->InputAt(0)->IsIntConstant());
+ EXPECT_EQ(0, last->InputAt(0)->AsIntConstant()->GetValue());
+ ASSERT_TRUE(last->InputAt(1)->IsIntConstant());
+ EXPECT_EQ(1000, last->InputAt(1)->AsIntConstant()->GetValue());
}
TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
@@ -650,14 +694,16 @@
bool needs_finite_test = true;
bool needs_taken_test = true;
+ HInstruction* phi = condition_->InputAt(0);
+
// In context of header: upper unknown.
- range_.GetInductionRange(condition_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(), v2);
// In context of loop-body: known.
- range_.GetInductionRange(increment_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(x_, 1, -1), v2);
@@ -668,19 +714,15 @@
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;
- HInstruction* taken = nullptr;
// Can generate code in context of loop-body only.
- EXPECT_FALSE(range_.CanGenerateCode(
- condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
- ASSERT_TRUE(range_.CanGenerateCode(
- increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
+ EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test));
+ ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test));
EXPECT_FALSE(needs_finite_test);
EXPECT_TRUE(needs_taken_test);
- // Generates code.
- range_.GenerateRangeCode(
- increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
+ // Generates code (unsimplified).
+ range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper);
// Verify lower is 0+0.
ASSERT_TRUE(lower != nullptr);
@@ -701,12 +743,19 @@
EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
// Verify taken-test is 0<V.
- range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
+ HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_);
ASSERT_TRUE(taken != nullptr);
ASSERT_TRUE(taken->IsLessThan());
ASSERT_TRUE(taken->InputAt(0)->IsIntConstant());
EXPECT_EQ(0, taken->InputAt(0)->AsIntConstant()->GetValue());
EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
+
+ // Replacement.
+ range_.Replace(loop_header_->GetLastInstruction(), x_, y_);
+ range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(1), v1);
+ ExpectEqual(Value(y_, 1, 0), v2);
}
TEST_F(InductionVarRangeTest, SymbolicTripCountDown) {
@@ -717,14 +766,16 @@
bool needs_finite_test = true;
bool needs_taken_test = true;
+ HInstruction* phi = condition_->InputAt(0);
+
// In context of header: lower unknown.
- range_.GetInductionRange(condition_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(), v1);
ExpectEqual(Value(1000), v2);
// In context of loop-body: known.
- range_.GetInductionRange(increment_, condition_->InputAt(0), x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(x_, 1, 1), v1);
ExpectEqual(Value(1000), v2);
@@ -735,19 +786,15 @@
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;
- HInstruction* taken = nullptr;
// Can generate code in context of loop-body only.
- EXPECT_FALSE(range_.CanGenerateCode(
- condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
- ASSERT_TRUE(range_.CanGenerateCode(
- increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test));
+ EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test));
+ ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test));
EXPECT_FALSE(needs_finite_test);
EXPECT_TRUE(needs_taken_test);
- // Generates code.
- range_.GenerateRangeCode(
- increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
+ // Generates code (unsimplified).
+ range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper);
// Verify lower is 1000-((1000-V)-1).
ASSERT_TRUE(lower != nullptr);
@@ -773,12 +820,19 @@
EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
// Verify taken-test is 1000>V.
- range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
+ HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_);
ASSERT_TRUE(taken != nullptr);
ASSERT_TRUE(taken->IsGreaterThan());
ASSERT_TRUE(taken->InputAt(0)->IsIntConstant());
EXPECT_EQ(1000, taken->InputAt(0)->AsIntConstant()->GetValue());
EXPECT_TRUE(taken->InputAt(1)->IsParameterValue());
+
+ // Replacement.
+ range_.Replace(loop_header_->GetLastInstruction(), x_, y_);
+ range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(y_, 1, 0), v1);
+ ExpectEqual(Value(999), v2);
}
} // namespace art