Finalized all components of range analysis needed for dynamic bce.
Rationale: added ability to generate taken-test, prompt back need
for finite-test; cleaned up the API now that bounds
check needs are all known.
Change-Id: I3d09b249965d1a980c09381240de175ca4b2e455
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index bcc3240..cca0baf 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1169,8 +1169,10 @@
// Return the range resulting from induction variable analysis of "instruction" when the value
// is used from "context", for example, an index used from a bounds-check inside a loop body.
ValueRange* LookupInductionRange(HInstruction* context, HInstruction* instruction) {
- InductionVarRange::Value v1 = induction_range_.GetMinInduction(context, instruction);
- InductionVarRange::Value v2 = induction_range_.GetMaxInduction(context, instruction);
+ InductionVarRange::Value v1;
+ InductionVarRange::Value v2;
+ bool needs_finite_test = false;
+ induction_range_.GetInductionRange(context, instruction, &v1, &v2, &needs_finite_test);
if (v1.is_known && (v1.a_constant == 0 || v1.a_constant == 1) &&
v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) {
DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 5530d26..b40ef5a 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -75,10 +75,12 @@
return v;
}
-static HInstruction* Insert(HBasicBlock* preheader, HInstruction* instruction) {
- DCHECK(preheader != nullptr);
+/** Helper method to insert an instruction. */
+static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) {
+ DCHECK(block != nullptr);
+ DCHECK(block->GetLastInstruction() != nullptr) << block->GetBlockId();
DCHECK(instruction != nullptr);
- preheader->InsertInstructionBefore(instruction, preheader->GetLastInstruction());
+ block->InsertInstructionBefore(instruction, block->GetLastInstruction());
return instruction;
}
@@ -91,48 +93,98 @@
DCHECK(induction_analysis != nullptr);
}
-InductionVarRange::Value InductionVarRange::GetMinInduction(HInstruction* context,
- HInstruction* instruction) {
- return GetInduction(context, instruction, /* is_min */ true);
-}
-
-InductionVarRange::Value InductionVarRange::GetMaxInduction(HInstruction* context,
- HInstruction* instruction) {
- return SimplifyMax(GetInduction(context, instruction, /* is_min */ false));
+void InductionVarRange::GetInductionRange(HInstruction* context,
+ HInstruction* instruction,
+ /*out*/Value* min_val,
+ /*out*/Value* max_val,
+ /*out*/bool* needs_finite_test) {
+ HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
+ if (loop != nullptr) {
+ // Set up loop information.
+ 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());
+ // Find range.
+ *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);
+ } else {
+ // No loop to analyze.
+ *min_val = Value();
+ *max_val = Value();
+ *needs_finite_test = false;
+ }
}
bool InductionVarRange::CanGenerateCode(HInstruction* context,
HInstruction* instruction,
- /*out*/bool* top_test) {
- return GenerateCode(context, instruction, nullptr, nullptr, nullptr, nullptr, top_test);
+ /*out*/bool* needs_finite_test,
+ /*out*/bool* needs_taken_test) {
+ return GenerateCode(context,
+ instruction,
+ nullptr, nullptr, nullptr, nullptr, nullptr, // nothing generated yet
+ needs_finite_test,
+ needs_taken_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);
+void InductionVarRange::GenerateRangeCode(HInstruction* context,
+ HInstruction* instruction,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** lower,
+ /*out*/HInstruction** upper) {
+ bool b1, b2; // unused
+ if (!GenerateCode(context, instruction, graph, block, lower, upper, nullptr, &b1, &b2)) {
+ LOG(FATAL) << "Failed precondition: GenerateCode()";
+ }
+}
+
+void InductionVarRange::GenerateTakenTest(HInstruction* context,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** taken_test) {
+ bool b1, b2; // unused
+ if (!GenerateCode(context, context, graph, block, nullptr, nullptr, taken_test, &b1, &b2)) {
+ LOG(FATAL) << "Failed precondition: GenerateCode()";
+ }
}
//
// Private class methods.
//
-InductionVarRange::Value InductionVarRange::GetInduction(HInstruction* context,
- HInstruction* instruction,
- bool is_min) {
- HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
- if (loop != nullptr) {
- HBasicBlock* header = loop->GetHeader();
- bool in_body = context->GetBlock() != header;
- return GetVal(induction_analysis_->LookupInfo(loop, instruction),
- induction_analysis_->LookupInfo(loop, header->GetLastInstruction()),
- in_body,
- is_min);
+bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
+ if (info != nullptr) {
+ if (info->induction_class == HInductionVarAnalysis::kLinear) {
+ return true;
+ } else if (info->induction_class == HInductionVarAnalysis::kWrapAround) {
+ return NeedsTripCount(info->op_b);
+ }
}
- return Value();
+ return false;
+}
+
+bool InductionVarRange::IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+ if (trip != nullptr) {
+ if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
+ return trip->operation == HInductionVarAnalysis::kTripCountInBody ||
+ trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe;
+ }
+ }
+ return false;
+}
+
+bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+ if (trip != nullptr) {
+ if (trip->induction_class == HInductionVarAnalysis::kInvariant) {
+ return trip->operation == HInductionVarAnalysis::kTripCountInBodyUnsafe ||
+ trip->operation == HInductionVarAnalysis::kTripCountInLoopUnsafe;
+ }
+ }
+ return false;
}
InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
@@ -184,11 +236,13 @@
case HInductionVarAnalysis::kFetch:
return GetFetch(info->fetch, trip, in_body, is_min);
case HInductionVarAnalysis::kTripCountInLoop:
+ case HInductionVarAnalysis::kTripCountInLoopUnsafe:
if (!in_body && !is_min) { // one extra!
return GetVal(info->op_a, trip, in_body, is_min);
}
FALLTHROUGH_INTENDED;
case HInductionVarAnalysis::kTripCountInBody:
+ case HInductionVarAnalysis::kTripCountInBodyUnsafe:
if (is_min) {
return Value(0);
} else if (in_body) {
@@ -356,25 +410,42 @@
HBasicBlock* block,
/*out*/HInstruction** lower,
/*out*/HInstruction** upper,
- /*out*/bool* top_test) {
+ /*out*/HInstruction** taken_test,
+ /*out*/bool* needs_finite_test,
+ /*out*/bool* needs_taken_test) {
HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
if (loop != nullptr) {
+ // Set up loop information.
HBasicBlock* header = loop->GetHeader();
bool in_body = context->GetBlock() != header;
- HInductionVarAnalysis::InductionInfo* info = induction_analysis_->LookupInfo(loop, instruction);
+ HInductionVarAnalysis::InductionInfo* info =
+ induction_analysis_->LookupInfo(loop, instruction);
+ if (info == nullptr) {
+ return false; // nothing to analyze
+ }
HInductionVarAnalysis::InductionInfo* trip =
induction_analysis_->LookupInfo(loop, header->GetLastInstruction());
- if (info != nullptr && trip != nullptr) {
- if (top_test != nullptr) {
- *top_test = trip->operation != HInductionVarAnalysis::kTripCountInLoop;
+ // Determine what tests are needed.
+ *needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
+ *needs_taken_test = NeedsTripCount(info) && IsBodyTripCount(trip);
+ // 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) {
+ return GenerateCode(
+ trip->op_b, nullptr, graph, block, taken_test, in_body, /* is_min */ false);
+ } else if (*needs_taken_test) {
+ if (!GenerateCode(
+ trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min */ false)) {
+ return false;
}
- return
+ }
+ // Code generation for lower and upper.
+ 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;
}
@@ -387,19 +458,38 @@
bool in_body,
bool is_min) {
if (info != nullptr) {
+ // Handle current operation.
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:
+ case HInductionVarAnalysis::kLT:
+ case HInductionVarAnalysis::kLE:
+ case HInductionVarAnalysis::kGT:
+ case HInductionVarAnalysis::kGE:
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));
+ HInstruction* operation = nullptr;
+ switch (info->operation) {
+ case HInductionVarAnalysis::kAdd:
+ operation = new (graph->GetArena()) HAdd(type, opa, opb); break;
+ case HInductionVarAnalysis::kLT:
+ operation = new (graph->GetArena()) HLessThan(opa, opb); break;
+ case HInductionVarAnalysis::kLE:
+ operation = new (graph->GetArena()) HLessThanOrEqual(opa, opb); break;
+ case HInductionVarAnalysis::kGT:
+ operation = new (graph->GetArena()) HGreaterThan(opa, opb); break;
+ case HInductionVarAnalysis::kGE:
+ operation = new (graph->GetArena()) HGreaterThanOrEqual(opa, opb); break;
+ default:
+ LOG(FATAL) << "unknown operation";
+ }
+ *result = Insert(block, operation);
}
return true;
}
@@ -427,11 +517,13 @@
}
return true;
case HInductionVarAnalysis::kTripCountInLoop:
+ case HInductionVarAnalysis::kTripCountInLoopUnsafe:
if (!in_body && !is_min) { // one extra!
return GenerateCode(info->op_a, trip, graph, block, result, in_body, is_min);
}
FALLTHROUGH_INTENDED;
case HInductionVarAnalysis::kTripCountInBody:
+ case HInductionVarAnalysis::kTripCountInBodyUnsafe:
if (is_min) {
if (graph != nullptr) {
*result = graph->GetIntConstant(0);
@@ -452,23 +544,31 @@
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));
+ 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.
+ int32_t stride_value = 0;
+ if (GetConstant(info->op_a, &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);
+ }
+ return true;
}
- return true;
}
}
}
break;
- default: // TODO(ajcbik): add more cases
+ default:
break;
}
}
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 7fa5a26..7984871 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -57,29 +57,33 @@
explicit InductionVarRange(HInductionVarAnalysis* induction);
/**
- * Given a context denoted by the first instruction, returns a,
- * possibly conservative, lower bound on the instruction's value.
+ * Given a context denoted by the first instruction, returns a possibly conservative
+ * lower and upper bound on the instruction's value in the output parameters min_val
+ * and max_val, respectively. The need_finite_test flag denotes if an additional finite-test
+ * is needed to protect the range evaluation inside its loop.
*/
- Value GetMinInduction(HInstruction* context, HInstruction* instruction);
+ void GetInductionRange(HInstruction* context,
+ HInstruction* instruction,
+ /*out*/Value* min_val,
+ /*out*/Value* max_val,
+ /*out*/bool* needs_finite_test);
/**
- * Given a context denoted by the first instruction, returns a,
- * possibly conservative, upper bound on the instruction's value.
+ * Returns true if range analysis is able to generate code for the lower and upper
+ * bound expressions on the instruction in the given context. The need_finite_test
+ * 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.
*/
- 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);
+ bool CanGenerateCode(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
* 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.
+ * generated in given block and graph and are returned in the output parameters 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:
@@ -87,20 +91,35 @@
* block:
* lower: add x, 0
* upper: add x, 5
+ *
+ * Precondition: CanGenerateCode() returns true.
*/
- bool GenerateCode(HInstruction* context,
- HInstruction* instruction,
- HGraph* graph,
- HBasicBlock* block,
- /*out*/HInstruction** lower,
- /*out*/HInstruction** upper);
+ void GenerateRangeCode(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.
+ *
+ * Precondition: CanGenerateCode() returns true and needs_taken_test is set.
+ */
+ void GenerateTakenTest(HInstruction* context,
+ HGraph* graph,
+ HBasicBlock* block,
+ /*out*/HInstruction** taken_test);
private:
//
// Private helper methods.
//
- Value GetInduction(HInstruction* context, HInstruction* instruction, bool is_min);
+ static bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info);
+ static bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip);
+ static bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip);
static Value GetFetch(HInstruction* instruction,
HInductionVarAnalysis::InductionInfo* trip,
@@ -130,8 +149,8 @@
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
+ * 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
* would be successful without generating actual code yet.
*/
bool GenerateCode(HInstruction* context,
@@ -140,7 +159,9 @@
HBasicBlock* block,
/*out*/HInstruction** lower,
/*out*/HInstruction** upper,
- bool* top_test);
+ /*out*/HInstruction** taken_test,
+ /*out*/bool* needs_finite_test,
+ /*out*/bool* needs_taken_test);
static bool GenerateCode(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index ce8926a..fda5153 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -46,6 +46,10 @@
EXPECT_EQ(v1.is_known, v2.is_known);
}
+ //
+ // Construction methods.
+ //
+
/** Constructs bare minimum graph. */
void BuildGraph() {
graph_->SetNumberOfVRegs(1);
@@ -58,7 +62,7 @@
}
/** Constructs loop with given upper bound. */
- void BuildLoop(HInstruction* upper) {
+ void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) {
// Control flow.
loop_preheader_ = new (&allocator_) HBasicBlock(graph_);
graph_->AddBlock(loop_preheader_);
@@ -75,18 +79,22 @@
HLocal* induc = new (&allocator_) HLocal(0);
entry_block_->AddInstruction(induc);
loop_preheader_->AddInstruction(
- new (&allocator_) HStoreLocal(induc, graph_->GetIntConstant(0))); // i = 0
+ new (&allocator_) HStoreLocal(induc, graph_->GetIntConstant(lower))); // i = l
loop_preheader_->AddInstruction(new (&allocator_) HGoto());
HInstruction* load = new (&allocator_) HLoadLocal(induc, Primitive::kPrimInt);
loop_header->AddInstruction(load);
- condition_ = new (&allocator_) HLessThan(load, upper);
+ if (stride > 0) {
+ condition_ = new (&allocator_) HLessThan(load, upper); // i < u
+ } else {
+ condition_ = new (&allocator_) HGreaterThan(load, upper); // i > u
+ }
loop_header->AddInstruction(condition_);
- loop_header->AddInstruction(new (&allocator_) HIf(condition_)); // i < u
+ loop_header->AddInstruction(new (&allocator_) HIf(condition_));
load = new (&allocator_) HLoadLocal(induc, Primitive::kPrimInt);
loop_body->AddInstruction(load);
- increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, load, graph_->GetIntConstant(1));
+ increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, load, graph_->GetIntConstant(stride));
loop_body->AddInstruction(increment_);
- loop_body->AddInstruction(new (&allocator_) HStoreLocal(induc, increment_)); // i++
+ loop_body->AddInstruction(new (&allocator_) HStoreLocal(induc, increment_)); // i += s
loop_body->AddInstruction(new (&allocator_) HGoto());
exit_block_->AddInstruction(new (&allocator_) HReturnVoid());
}
@@ -124,8 +132,20 @@
}
/** Constructs a trip-count. */
- HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc) {
- return iva_->CreateTripCount(HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr);
+ HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) {
+ if (in_loop && safe) {
+ return iva_->CreateTripCount(
+ HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr);
+ } else if (in_loop) {
+ return iva_->CreateTripCount(
+ HInductionVarAnalysis::kTripCountInLoopUnsafe, CreateConst(tc), nullptr);
+ } else if (safe) {
+ return iva_->CreateTripCount(
+ HInductionVarAnalysis::kTripCountInBody, CreateConst(tc), nullptr);
+ } else {
+ return iva_->CreateTripCount(
+ HInductionVarAnalysis::kTripCountInBodyUnsafe, CreateConst(tc), nullptr);
+ }
}
/** Constructs a linear a * i + b induction. */
@@ -139,16 +159,34 @@
HInductionVarAnalysis::kPeriodic, CreateConst(lo), CreateConst(hi));
}
+ /** Constructs a wrap-around induction consisting of a constant, followed info */
+ HInductionVarAnalysis::InductionInfo* CreateWrapAround(
+ int32_t initial,
+ HInductionVarAnalysis::InductionInfo* info) {
+ return iva_->CreateInduction(HInductionVarAnalysis::kWrapAround, CreateConst(initial), info);
+ }
+
/** Constructs a wrap-around induction consisting of a constant, followed by a range. */
HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) {
- return iva_->CreateInduction(
- HInductionVarAnalysis::kWrapAround, CreateConst(initial), CreateRange(lo, hi));
+ return CreateWrapAround(initial, CreateRange(lo, hi));
}
//
// Relay methods.
//
+ bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
+ return InductionVarRange::NeedsTripCount(info);
+ }
+
+ bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+ return InductionVarRange::IsBodyTripCount(trip);
+ }
+
+ bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) {
+ return InductionVarRange::IsUnsafeTripCount(trip);
+ }
+
Value GetMin(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* induc) {
return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ true);
@@ -202,6 +240,26 @@
// Tests on static methods.
//
+TEST_F(InductionVarRangeTest, TripCountProperties) {
+ EXPECT_FALSE(NeedsTripCount(nullptr));
+ EXPECT_FALSE(NeedsTripCount(CreateConst(1)));
+ EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1)));
+ EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3)));
+ EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1))));
+
+ EXPECT_FALSE(IsBodyTripCount(nullptr));
+ EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true)));
+ EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false)));
+ EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true)));
+ EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false)));
+
+ EXPECT_FALSE(IsUnsafeTripCount(nullptr));
+ EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true)));
+ EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false)));
+ EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true)));
+ EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false)));
+}
+
TEST_F(InductionVarRangeTest, GetMinMaxNull) {
ExpectEqual(Value(), GetMin(nullptr, nullptr));
ExpectEqual(Value(), GetMax(nullptr, nullptr));
@@ -279,10 +337,10 @@
}
TEST_F(InductionVarRangeTest, GetMinMaxLinear) {
- ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100)));
- ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100)));
- ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100)));
- ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100)));
+ ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100, true, true)));
}
TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) {
@@ -398,61 +456,98 @@
// Tests on instance methods.
//
-TEST_F(InductionVarRangeTest, FindRangeConstantTripCount) {
- BuildLoop(graph_->GetIntConstant(1000));
+TEST_F(InductionVarRangeTest, ConstantTripCountUp) {
+ BuildLoop(0, graph_->GetIntConstant(1000), 1);
PerformInductionVarAnalysis();
InductionVarRange range(iva_);
+ Value v1, v2;
+ bool needs_finite_test = true;
+
// In context of header: known.
- ExpectEqual(Value(0), range.GetMinInduction(condition_, condition_->InputAt(0)));
- ExpectEqual(Value(1000), range.GetMaxInduction(condition_, condition_->InputAt(0)));
+ range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(0), v1);
+ ExpectEqual(Value(1000), v2);
// 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_));
+ range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(0), v1);
+ ExpectEqual(Value(999), v2);
+ range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(1), v1);
+ ExpectEqual(Value(1000), v2);
}
-TEST_F(InductionVarRangeTest, FindRangeSymbolicTripCount) {
- HInstruction* parameter = new (&allocator_) HParameterValue(
- graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
- entry_block_->AddInstruction(parameter);
- BuildLoop(parameter);
+TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
+ BuildLoop(1000, graph_->GetIntConstant(0), -1);
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)));
+ Value v1, v2;
+ bool needs_finite_test = true;
+
+ // In context of header: known.
+ range.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(0), v1);
+ ExpectEqual(Value(1000), v2);
// 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_));
+ range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(1), v1);
+ ExpectEqual(Value(1000), v2);
+ range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(0), v1);
+ ExpectEqual(Value(999), v2);
}
-TEST_F(InductionVarRangeTest, CodeGeneration) {
+TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
HInstruction* parameter = new (&allocator_) HParameterValue(
graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
entry_block_->AddInstruction(parameter);
- BuildLoop(parameter);
+ BuildLoop(0, parameter, 1);
PerformInductionVarAnalysis();
InductionVarRange range(iva_);
+ Value v1, v2;
+ bool needs_finite_test = true;
+ bool needs_taken_test = true;
+
+ // In context of header: upper unknown.
+ range.GetInductionRange(condition_, condition_->InputAt(0), &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), &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(0), v1);
+ ExpectEqual(Value(parameter, 1, -1), v2);
+ range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(1), v1);
+ ExpectEqual(Value(parameter, 1, 0), v2);
+
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;
- bool top_test = false;
+ HInstruction* taken = nullptr;
// 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);
+ 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(needs_finite_test);
+ EXPECT_TRUE(needs_taken_test);
// Generates code.
- EXPECT_TRUE(range.GenerateCode(
- increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper));
+ range.GenerateRangeCode(increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
// Verify lower is 0+0.
ASSERT_TRUE(lower != nullptr);
@@ -462,7 +557,7 @@
ASSERT_TRUE(lower->InputAt(1)->IsIntConstant());
EXPECT_EQ(0, lower->InputAt(1)->AsIntConstant()->GetValue());
- // Verify upper is (V-1)+0
+ // Verify upper is (V-1)+0.
ASSERT_TRUE(upper != nullptr);
ASSERT_TRUE(upper->IsAdd());
ASSERT_TRUE(upper->InputAt(0)->IsSub());
@@ -471,6 +566,91 @@
EXPECT_EQ(1, upper->InputAt(0)->InputAt(1)->AsIntConstant()->GetValue());
ASSERT_TRUE(upper->InputAt(1)->IsIntConstant());
EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
+
+ // Verify taken-test is 0<V.
+ range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
+ 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());
+}
+
+TEST_F(InductionVarRangeTest, SymbolicTripCountDown) {
+ HInstruction* parameter = new (&allocator_) HParameterValue(
+ graph_->GetDexFile(), 0, 0, Primitive::kPrimInt);
+ entry_block_->AddInstruction(parameter);
+ BuildLoop(1000, parameter, -1);
+ PerformInductionVarAnalysis();
+ InductionVarRange range(iva_);
+
+ Value v1, v2;
+ bool needs_finite_test = true;
+ bool needs_taken_test = true;
+
+ // In context of header: lower unknown.
+ range.GetInductionRange(condition_, condition_->InputAt(0), &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), &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(parameter, 1, 1), v1);
+ ExpectEqual(Value(1000), v2);
+ range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
+ EXPECT_FALSE(needs_finite_test);
+ ExpectEqual(Value(parameter, 1, 0), v1);
+ ExpectEqual(Value(999), v2);
+
+ 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(needs_finite_test);
+ EXPECT_TRUE(needs_taken_test);
+
+ // Generates code.
+ range.GenerateRangeCode(increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper);
+
+ // Verify lower is 1000-(-(V-1000)-1).
+ ASSERT_TRUE(lower != nullptr);
+ ASSERT_TRUE(lower->IsSub());
+ ASSERT_TRUE(lower->InputAt(0)->IsIntConstant());
+ EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue());
+ lower = lower->InputAt(1);
+ ASSERT_TRUE(lower->IsSub());
+ ASSERT_TRUE(lower->InputAt(1)->IsIntConstant());
+ EXPECT_EQ(1, lower->InputAt(1)->AsIntConstant()->GetValue());
+ lower = lower->InputAt(0);
+ ASSERT_TRUE(lower->IsNeg());
+ lower = lower->InputAt(0);
+ ASSERT_TRUE(lower->IsSub());
+ EXPECT_TRUE(lower->InputAt(0)->IsParameterValue());
+ ASSERT_TRUE(lower->InputAt(1)->IsIntConstant());
+ EXPECT_EQ(1000, lower->InputAt(1)->AsIntConstant()->GetValue());
+
+ // Verify upper is 1000-0.
+ ASSERT_TRUE(upper != nullptr);
+ ASSERT_TRUE(upper->IsSub());
+ ASSERT_TRUE(upper->InputAt(0)->IsIntConstant());
+ EXPECT_EQ(1000, upper->InputAt(0)->AsIntConstant()->GetValue());
+ ASSERT_TRUE(upper->InputAt(1)->IsIntConstant());
+ EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue());
+
+ // Verify taken-test is 1000>V.
+ range.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken);
+ 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());
}
} // namespace art