Fix last value generation in loop optimization.
Instead of `in_body`, propagate the context block and loop
information to make better decisions for trip count if the
context is outside the loop.
In particular, fix `InductionVarRange::IsConstant()` to take
and use this information instead of assuming that we are
asking about values in the loop body.
For trip count with context outside the loop, we know that
the value shall be the maximum trip count if the context
is dominated by the loop control exit block.
Test: Enable run-test 835-b216762268.
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 216762268
Change-Id: Id564ba75c812d54abdd9b229e643cc8ab4701c52
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 2d02e9f..dad3c81 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -911,7 +911,7 @@
bool needs_taken_test = false;
if (DynamicBCESeemsProfitable(loop, bounds_check->GetBlock()) &&
induction_range_.CanGenerateRange(
- bounds_check, index, &needs_finite_test, &needs_taken_test) &&
+ bounds_check->GetBlock(), index, &needs_finite_test, &needs_taken_test) &&
CanHandleInfiniteLoop(loop, index, needs_finite_test) &&
// Do this test last, since it may generate code.
CanHandleLength(loop, array_length, needs_taken_test)) {
@@ -1495,7 +1495,8 @@
bool needs_finite_test = false;
HInstruction* index = context->InputAt(0);
HInstruction* hint = HuntForDeclaration(context->InputAt(1));
- if (induction_range_.GetInductionRange(context, index, hint, &v1, &v2, &needs_finite_test)) {
+ if (induction_range_.GetInductionRange(
+ context->GetBlock(), index, hint, &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);
@@ -1547,7 +1548,8 @@
if (array_length == other_array_length && base == other_value.GetInstruction()) {
// Ensure every candidate could be picked for code generation.
bool b1 = false, b2 = false;
- if (!induction_range_.CanGenerateRange(other_bounds_check, other_index, &b1, &b2)) {
+ if (!induction_range_.CanGenerateRange(
+ other_bounds_check->GetBlock(), other_index, &b1, &b2)) {
continue;
}
// Does the current basic block dominate all back edges? If not,
@@ -1592,11 +1594,19 @@
// 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_.GenerateRange(
- other_bounds_check, other_index, GetGraph(), block, &max_lower, &max_upper);
+ induction_range_.GenerateRange(other_bounds_check->GetBlock(),
+ other_index,
+ GetGraph(),
+ block,
+ &max_lower,
+ &max_upper);
} else if (other_c == min_c && base != nullptr) {
- induction_range_.GenerateRange(
- other_bounds_check, other_index, GetGraph(), block, &min_lower, &min_upper);
+ induction_range_.GenerateRange(other_bounds_check->GetBlock(),
+ other_index,
+ GetGraph(),
+ block,
+ &min_lower,
+ &min_upper);
}
ReplaceInstruction(other_bounds_check, other_index);
}
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index e6d9079..3b5a2f1 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -63,7 +63,7 @@
/**
* Returns true if loop is guarded by "a cmp b" on entry.
*/
-static bool IsGuardedBy(HLoopInformation* loop,
+static bool IsGuardedBy(const HLoopInformation* loop,
IfCondition cmp,
HInstruction* a,
HInstruction* b) {
@@ -110,7 +110,7 @@
}
/* Finds first loop header phi use. */
-HInstruction* FindFirstLoopHeaderPhiUse(HLoopInformation* loop, HInstruction* instruction) {
+HInstruction* FindFirstLoopHeaderPhiUse(const HLoopInformation* loop, HInstruction* instruction) {
for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
if (use.GetUser()->GetBlock() == loop->GetHeader() &&
use.GetUser()->IsPhi() &&
@@ -124,7 +124,7 @@
/**
* Relinks the Phi structure after break-loop rewriting.
*/
-static bool FixOutsideUse(HLoopInformation* loop,
+static bool FixOutsideUse(const HLoopInformation* loop,
HInstruction* instruction,
HInstruction* replacement,
bool rewrite) {
@@ -162,7 +162,7 @@
/**
* Test and rewrite the loop body of a break-loop. Returns true on success.
*/
-static bool RewriteBreakLoopBody(HLoopInformation* loop,
+static bool RewriteBreakLoopBody(const HLoopInformation* loop,
HBasicBlock* body,
HInstruction* cond,
HInstruction* index,
@@ -216,7 +216,7 @@
HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph, const char* name)
: HOptimization(graph, name),
- induction_(std::less<HLoopInformation*>(),
+ induction_(std::less<const HLoopInformation*>(),
graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)),
cycles_(std::less<HPhi*>(),
graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)) {
@@ -235,7 +235,7 @@
return !induction_.empty();
}
-void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) {
+void HInductionVarAnalysis::VisitLoop(const HLoopInformation* loop) {
ScopedArenaAllocator local_allocator(graph_->GetArenaStack());
ScopedArenaSafeMap<HInstruction*, NodeInfo> visited_instructions(
std::less<HInstruction*>(), local_allocator.Adapter(kArenaAllocInductionVarAnalysis));
@@ -263,7 +263,7 @@
}
size_t HInductionVarAnalysis::TryVisitNodes(
- HLoopInformation* loop,
+ const HLoopInformation* loop,
HInstruction* start_instruction,
size_t global_depth,
/*inout*/ ScopedArenaSafeMap<HInstruction*, NodeInfo>* visited_instructions) {
@@ -386,31 +386,41 @@
DCHECK_EQ(scc->size(), stack_tail.size());
}
-void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) {
+void HInductionVarAnalysis::ClassifyTrivial(const HLoopInformation* loop,
+ HInstruction* instruction) {
+ const HBasicBlock* context = instruction->GetBlock();
DataType::Type type = instruction->GetType();
InductionInfo* info = nullptr;
if (instruction->IsPhi()) {
info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 0);
} else if (instruction->IsAdd()) {
- info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
+ info = TransferAddSub(context,
+ loop,
+ LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, instruction->InputAt(1)),
kAdd,
type);
} else if (instruction->IsSub()) {
- info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)),
+ info = TransferAddSub(context,
+ loop,
+ LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, instruction->InputAt(1)),
kSub,
type);
} else if (instruction->IsNeg()) {
- info = TransferNeg(LookupInfo(loop, instruction->InputAt(0)), type);
+ info = TransferNeg(context, loop, LookupInfo(loop, instruction->InputAt(0)), type);
} else if (instruction->IsMul()) {
- info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
+ info = TransferMul(context,
+ loop,
+ LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, instruction->InputAt(1)),
type);
} else if (instruction->IsShl()) {
HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr);
if (mulc != nullptr) {
- info = TransferMul(LookupInfo(loop, instruction->InputAt(0)),
+ info = TransferMul(context,
+ loop,
+ LookupInfo(loop, instruction->InputAt(0)),
LookupInfo(loop, mulc),
type);
}
@@ -430,7 +440,7 @@
}
}
-void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop,
+void HInductionVarAnalysis::ClassifyNonTrivial(const HLoopInformation* loop,
ArrayRef<const StackEntry> stack_tail) {
const size_t size = stack_tail.size();
DCHECK_GE(size, 1u);
@@ -597,10 +607,11 @@
type);
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop,
- HInstruction* phi,
- size_t input_index,
- size_t adjust_input_size) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(
+ const HLoopInformation* loop,
+ HInstruction* phi,
+ size_t input_index,
+ size_t adjust_input_size) {
// Match all phi inputs from input_index onwards exactly.
HInputsRef inputs = phi->GetInputs();
DCHECK_LT(input_index, inputs.size());
@@ -614,10 +625,13 @@
return a;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a,
- InductionInfo* b,
- InductionOp op,
- DataType::Type type) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(
+ const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* a,
+ InductionInfo* b,
+ InductionOp op,
+ DataType::Type type) {
// Transfer over an addition or subtraction: any invariant, linear, polynomial, geometric,
// wrap-around, or periodic can be combined with an invariant to yield a similar result.
// Two linear or two polynomial inputs can be combined too. Other combinations fail.
@@ -625,23 +639,23 @@
if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) {
return nullptr; // no transfer
} else if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
- return CreateInvariantOp(op, a, b); // direct invariant
+ return CreateInvariantOp(context, loop, op, a, b); // direct invariant
} else if ((a->induction_class == kLinear && b->induction_class == kLinear) ||
(a->induction_class == kPolynomial && b->induction_class == kPolynomial)) {
// Rule induc(a, b) + induc(a', b') -> induc(a + a', b + b').
- InductionInfo* new_a = TransferAddSub(a->op_a, b->op_a, op, type);
- InductionInfo* new_b = TransferAddSub(a->op_b, b->op_b, op, type);
+ InductionInfo* new_a = TransferAddSub(context, loop, a->op_a, b->op_a, op, type);
+ InductionInfo* new_b = TransferAddSub(context, loop, a->op_b, b->op_b, op, type);
if (new_a != nullptr && new_b != nullptr) {
return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type);
}
} else if (a->induction_class == kInvariant) {
// Rule a + induc(a', b') -> induc(a', a + b') or induc(a + a', a + b').
InductionInfo* new_a = b->op_a;
- InductionInfo* new_b = TransferAddSub(a, b->op_b, op, type);
+ InductionInfo* new_b = TransferAddSub(context, loop, a, b->op_b, op, type);
if (b->induction_class == kWrapAround || b->induction_class == kPeriodic) {
- new_a = TransferAddSub(a, new_a, op, type);
+ new_a = TransferAddSub(context, loop, a, new_a, op, type);
} else if (op == kSub) { // Negation required.
- new_a = TransferNeg(new_a, type);
+ new_a = TransferNeg(context, loop, new_a, type);
}
if (new_a != nullptr && new_b != nullptr) {
return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type);
@@ -649,9 +663,9 @@
} else if (b->induction_class == kInvariant) {
// Rule induc(a, b) + b' -> induc(a, b + b') or induc(a + b', b + b').
InductionInfo* new_a = a->op_a;
- InductionInfo* new_b = TransferAddSub(a->op_b, b, op, type);
+ InductionInfo* new_b = TransferAddSub(context, loop, a->op_b, b, op, type);
if (a->induction_class == kWrapAround || a->induction_class == kPeriodic) {
- new_a = TransferAddSub(new_a, b, op, type);
+ new_a = TransferAddSub(context, loop, new_a, b, op, type);
}
if (new_a != nullptr && new_b != nullptr) {
return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type);
@@ -661,19 +675,22 @@
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a,
- DataType::Type type) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(
+ const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* a,
+ DataType::Type type) {
// Transfer over a unary negation: an invariant, linear, polynomial, geometric (mul),
// wrap-around, or periodic input yields a similar but negated induction as result.
if (a != nullptr) {
if (IsNarrowingLinear(a)) {
return nullptr; // no transfer
} else if (a->induction_class == kInvariant) {
- return CreateInvariantOp(kNeg, nullptr, a); // direct invariant
+ return CreateInvariantOp(context, loop, kNeg, nullptr, a); // direct invariant
} else if (a->induction_class != kGeometric || a->operation == kMul) {
// Rule - induc(a, b) -> induc(-a, -b).
- InductionInfo* new_a = TransferNeg(a->op_a, type);
- InductionInfo* new_b = TransferNeg(a->op_b, type);
+ InductionInfo* new_a = TransferNeg(context, loop, a->op_a, type);
+ InductionInfo* new_b = TransferNeg(context, loop, a->op_b, type);
if (new_a != nullptr && new_b != nullptr) {
return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type);
}
@@ -682,9 +699,12 @@
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a,
- InductionInfo* b,
- DataType::Type type) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(
+ const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* a,
+ InductionInfo* b,
+ DataType::Type type) {
// Transfer over a multiplication: any invariant, linear, polynomial, geometric (mul),
// wrap-around, or periodic can be multiplied with an invariant to yield a similar
// but multiplied result. Two non-invariant inputs cannot be multiplied, however.
@@ -692,20 +712,20 @@
if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) {
return nullptr; // no transfer
} else if (a->induction_class == kInvariant && b->induction_class == kInvariant) {
- return CreateInvariantOp(kMul, a, b); // direct invariant
+ return CreateInvariantOp(context, loop, kMul, a, b); // direct invariant
} else if (a->induction_class == kInvariant && (b->induction_class != kGeometric ||
b->operation == kMul)) {
// Rule a * induc(a', b') -> induc(a * a', b * b').
- InductionInfo* new_a = TransferMul(a, b->op_a, type);
- InductionInfo* new_b = TransferMul(a, b->op_b, type);
+ InductionInfo* new_a = TransferMul(context, loop, a, b->op_a, type);
+ InductionInfo* new_b = TransferMul(context, loop, a, b->op_b, type);
if (new_a != nullptr && new_b != nullptr) {
return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type);
}
} else if (b->induction_class == kInvariant && (a->induction_class != kGeometric ||
a->operation == kMul)) {
// Rule induc(a, b) * b' -> induc(a * b', b * b').
- InductionInfo* new_a = TransferMul(a->op_a, b, type);
- InductionInfo* new_b = TransferMul(a->op_b, b, type);
+ InductionInfo* new_a = TransferMul(context, loop, a->op_a, b, type);
+ InductionInfo* new_b = TransferMul(context, loop, a->op_b, b, type);
if (new_a != nullptr && new_b != nullptr) {
return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type);
}
@@ -753,7 +773,7 @@
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs(
- HLoopInformation* loop,
+ const HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* phi,
const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
@@ -784,7 +804,7 @@
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(
- HLoopInformation* loop,
+ const HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
@@ -792,6 +812,7 @@
InductionOp op,
const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
DataType::Type type) {
+ const HBasicBlock* context = instruction->GetBlock();
auto main_solve_add_sub = [&]() -> HInductionVarAnalysis::InductionInfo* {
// Solve within a cycle over an addition or subtraction.
InductionInfo* b = LookupInfo(loop, y);
@@ -800,13 +821,13 @@
// Adding or subtracting an invariant value, seeded from phi,
// keeps adding to the stride of the linear induction.
if (x == entry_phi) {
- return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b);
+ return (op == kAdd) ? b : CreateInvariantOp(context, loop, kNeg, nullptr, b);
}
auto it = cycle.find(x);
if (it != cycle.end()) {
InductionInfo* a = it->second;
if (a->induction_class == kInvariant) {
- return CreateInvariantOp(op, a, b);
+ return CreateInvariantOp(context, loop, op, a, b);
}
}
} else if (b->induction_class == kLinear && b->type == type) {
@@ -816,7 +837,7 @@
entry_phi->InputCount() == 2 &&
instruction == entry_phi->InputAt(1)) {
InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
- InductionInfo* new_a = op == kAdd ? b : TransferNeg(b, type);
+ InductionInfo* new_a = op == kAdd ? b : TransferNeg(context, loop, b, type);
if (new_a != nullptr) {
return CreateInduction(kPolynomial, kNop, new_a, initial, /*fetch*/ nullptr, type);
}
@@ -841,7 +862,7 @@
InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
result = CreateInduction(kPeriodic,
kNop,
- CreateInvariantOp(kSub, a, initial),
+ CreateInvariantOp(context, loop, kSub, a, initial),
initial,
/*fetch*/ nullptr,
type);
@@ -852,13 +873,13 @@
return result;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInformation* loop,
- HInstruction* entry_phi,
- HInstruction* instruction,
- HInstruction* x,
- HInstruction* y,
- InductionOp op,
- DataType::Type type) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(const HLoopInformation* loop,
+ HInstruction* entry_phi,
+ HInstruction* instruction,
+ HInstruction* x,
+ HInstruction* y,
+ InductionOp op,
+ DataType::Type type) {
// Solve within a tight cycle for a binary operation k = k op c or, for some op, k = c op k.
if (entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) {
InductionInfo* c = nullptr;
@@ -873,6 +894,7 @@
}
// Found suitable operand left or right?
if (c != nullptr) {
+ const HBasicBlock* context = instruction->GetBlock();
InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
switch (op) {
case kMul:
@@ -892,14 +914,14 @@
return CreateInduction(kWrapAround,
kNop,
initial,
- CreateInvariantOp(kRem, initial, c),
+ CreateInvariantOp(context, loop, kRem, initial, c),
/*fetch*/ nullptr,
type);
case kXor:
// Idiomatic XOR periodic induction.
return CreateInduction(kPeriodic,
kNop,
- CreateInvariantOp(kXor, initial, c),
+ CreateInvariantOp(context, loop, kXor, initial, c),
initial,
/*fetch*/ nullptr,
type);
@@ -912,25 +934,26 @@
return nullptr;
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveTest(HLoopInformation* loop,
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveTest(const HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* instruction,
int64_t opposite_value,
DataType::Type type) {
// Detect hidden XOR construction in x = (x == false) or x = (x != true).
- int64_t value = -1;
+ const HBasicBlock* context = instruction->GetBlock();
HInstruction* x = instruction->InputAt(0);
HInstruction* y = instruction->InputAt(1);
- if (IsExact(LookupInfo(loop, x), &value) && value == opposite_value) {
+ int64_t value = -1;
+ if (IsExact(context, loop, LookupInfo(loop, x), &value) && value == opposite_value) {
return SolveOp(loop, entry_phi, instruction, graph_->GetIntConstant(1), y, kXor, type);
- } else if (IsExact(LookupInfo(loop, y), &value) && value == opposite_value) {
+ } else if (IsExact(context, loop, LookupInfo(loop, y), &value) && value == opposite_value) {
return SolveOp(loop, entry_phi, instruction, x, graph_->GetIntConstant(1), kXor, type);
}
return nullptr;
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveConversion(
- HLoopInformation* loop,
+ const HLoopInformation* loop,
HInstruction* entry_phi,
HTypeConversion* conversion,
const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
@@ -945,10 +968,11 @@
int64_t min = DataType::MinValueOfIntegralType(to);
int64_t max = DataType::MaxValueOfIntegralType(to);
int64_t value = 0;
+ const HBasicBlock* context = conversion->GetBlock();
InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0));
if (IsNarrowingIntegralConversion(from, to) &&
- IsAtLeast(initial, &value) && value >= min &&
- IsAtMost(initial, &value) && value <= max) {
+ IsAtLeast(context, loop, initial, &value) && value >= min &&
+ IsAtMost(context, loop, initial, &value) && value <= max) {
auto it = cycle.find(conversion->GetInput());
if (it != cycle.end() && it->second->induction_class == kInvariant) {
*type = to;
@@ -963,7 +987,7 @@
// Loop trip count analysis methods.
//
-void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) {
+void HInductionVarAnalysis::VisitControl(const HLoopInformation* loop) {
HInstruction* control = loop->GetHeader()->GetLastInstruction();
if (control->IsIf()) {
HIf* ifs = control->AsIf();
@@ -975,6 +999,7 @@
// if (condition) goto X
if (if_expr->IsCondition()) {
HCondition* condition = if_expr->AsCondition();
+ const HBasicBlock* context = condition->GetBlock();
InductionInfo* a = LookupInfo(loop, condition->InputAt(0));
InductionInfo* b = LookupInfo(loop, condition->InputAt(1));
DataType::Type type = ImplicitConversion(condition->InputAt(0)->GetType());
@@ -983,15 +1008,16 @@
if (a == nullptr || b == nullptr) {
return; // Loop control is not a sequence.
} else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) {
- VisitCondition(loop, if_false, a, b, type, condition->GetOppositeCondition());
+ VisitCondition(context, loop, if_false, a, b, type, condition->GetOppositeCondition());
} else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) {
- VisitCondition(loop, if_true, a, b, type, condition->GetCondition());
+ VisitCondition(context, loop, if_true, a, b, type, condition->GetCondition());
}
}
}
}
-void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop,
+void HInductionVarAnalysis::VisitCondition(const HBasicBlock* context,
+ const HLoopInformation* loop,
HBasicBlock* body,
InductionInfo* a,
InductionInfo* b,
@@ -1000,11 +1026,11 @@
if (a->induction_class == kInvariant && b->induction_class == kLinear) {
// Swap condition if induction is at right-hand-side (e.g. U > i is same as i < U).
switch (cmp) {
- case kCondLT: VisitCondition(loop, body, b, a, type, kCondGT); break;
- case kCondLE: VisitCondition(loop, body, b, a, type, kCondGE); break;
- case kCondGT: VisitCondition(loop, body, b, a, type, kCondLT); break;
- case kCondGE: VisitCondition(loop, body, b, a, type, kCondLE); break;
- case kCondNE: VisitCondition(loop, body, b, a, type, kCondNE); break;
+ case kCondLT: VisitCondition(context, loop, body, b, a, type, kCondGT); break;
+ case kCondLE: VisitCondition(context, loop, body, b, a, type, kCondGE); break;
+ case kCondGT: VisitCondition(context, loop, body, b, a, type, kCondLT); break;
+ case kCondGE: VisitCondition(context, loop, body, b, a, type, kCondLE); break;
+ case kCondNE: VisitCondition(context, loop, body, b, a, type, kCondNE); break;
default: break;
}
} else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
@@ -1014,7 +1040,7 @@
InductionInfo* stride_expr = a->op_a;
// Test for constant stride and integral condition.
int64_t stride_value = 0;
- if (!IsExact(stride_expr, &stride_value)) {
+ if (!IsExact(context, loop, stride_expr, &stride_value)) {
return; // unknown stride
} else if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) {
return; // not integral
@@ -1022,20 +1048,21 @@
// Since loops with a i != U condition will not be normalized by the method below, first
// try to rewrite a break-loop with terminating condition i != U into an equivalent loop
// with non-strict end condition i <= U or i >= U if such a rewriting is possible and safe.
- if (cmp == kCondNE && RewriteBreakLoop(loop, body, stride_value, type)) {
+ if (cmp == kCondNE && RewriteBreakLoop(context, loop, body, stride_value, type)) {
cmp = stride_value > 0 ? kCondLE : kCondGE;
}
// If this rewriting failed, try to rewrite condition i != U into strict end condition i < U
// or i > U if this end condition is reached exactly (tested by verifying if the loop has a
// unit stride and the non-strict condition would be always taken).
- if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLE)) ||
- (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGE)))) {
+ if (cmp == kCondNE &&
+ ((stride_value == +1 && IsTaken(context, loop, lower_expr, upper_expr, kCondLE)) ||
+ (stride_value == -1 && IsTaken(context, loop, lower_expr, upper_expr, kCondGE)))) {
cmp = stride_value > 0 ? kCondLT : kCondGT;
}
// A mismatch between the type of condition and the induction is only allowed if the,
// necessarily narrower, induction range fits the narrower control.
if (type != a->type &&
- !FitsNarrowerControl(lower_expr, upper_expr, stride_value, a->type, cmp)) {
+ !FitsNarrowerControl(context, loop, lower_expr, upper_expr, stride_value, a->type, cmp)) {
return; // mismatched type
}
// Normalize a linear loop control with a nonzero stride:
@@ -1043,12 +1070,13 @@
// stride < 0, either i > U or i >= U
if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
(stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
- VisitTripCount(loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp);
+ VisitTripCount(context, loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp);
}
}
}
-void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop,
+void HInductionVarAnalysis::VisitTripCount(const HBasicBlock* context,
+ const HLoopInformation* loop,
InductionInfo* lower_expr,
InductionInfo* upper_expr,
InductionInfo* stride_expr,
@@ -1082,22 +1110,22 @@
// (4) For loops which early-exits, the TC forms an upper bound, as in:
// for (int i = 0; i < 10 && ....; i++) // TC <= 10
InductionInfo* trip_count = upper_expr;
- const bool is_taken = IsTaken(lower_expr, upper_expr, cmp);
- const bool is_finite = IsFinite(upper_expr, stride_value, type, cmp);
+ const bool is_taken = IsTaken(context, loop, lower_expr, upper_expr, cmp);
+ const bool is_finite = IsFinite(context, loop, upper_expr, stride_value, type, cmp);
const bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1;
if (!cancels) {
// Convert exclusive integral inequality into inclusive integral inequality,
// viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1.
if (cmp == kCondLT) {
- trip_count = CreateInvariantOp(kSub, trip_count, CreateConstant(1, type));
+ trip_count = CreateInvariantOp(context, loop, kSub, trip_count, CreateConstant(1, type));
} else if (cmp == kCondGT) {
- trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type));
+ trip_count = CreateInvariantOp(context, loop, kAdd, trip_count, CreateConstant(1, type));
}
// Compensate for stride.
- trip_count = CreateInvariantOp(kAdd, trip_count, stride_expr);
+ trip_count = CreateInvariantOp(context, loop, kAdd, trip_count, stride_expr);
}
- trip_count = CreateInvariantOp(
- kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride_expr);
+ trip_count = CreateInvariantOp(context, loop, kSub, trip_count, lower_expr);
+ trip_count = CreateInvariantOp(context, loop, kDiv, trip_count, stride_expr);
// Assign the trip-count expression to the loop control. Clients that use the information
// should be aware that the expression is only valid under the conditions listed above.
InductionOp tcKind = kTripCountInBodyUnsafe; // needs both tests
@@ -1119,32 +1147,34 @@
// Associate trip count with control instruction, rather than the condition (even
// though it's its use) since former provides a convenient use-free placeholder.
HInstruction* control = loop->GetHeader()->GetLastInstruction();
- InductionInfo* taken_test = CreateInvariantOp(op, lower_expr, upper_expr);
+ InductionInfo* taken_test = CreateInvariantOp(context, loop, op, lower_expr, upper_expr);
DCHECK(control->IsIf());
AssignInfo(loop, control, CreateTripCount(tcKind, trip_count, taken_test, type));
}
-bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr,
+bool HInductionVarAnalysis::IsTaken(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* lower_expr,
InductionInfo* upper_expr,
IfCondition cmp) {
int64_t lower_value;
int64_t upper_value;
switch (cmp) {
case kCondLT:
- return IsAtMost(lower_expr, &lower_value)
- && IsAtLeast(upper_expr, &upper_value)
+ return IsAtMost(context, loop, lower_expr, &lower_value)
+ && IsAtLeast(context, loop, upper_expr, &upper_value)
&& lower_value < upper_value;
case kCondLE:
- return IsAtMost(lower_expr, &lower_value)
- && IsAtLeast(upper_expr, &upper_value)
+ return IsAtMost(context, loop, lower_expr, &lower_value)
+ && IsAtLeast(context, loop, upper_expr, &upper_value)
&& lower_value <= upper_value;
case kCondGT:
- return IsAtLeast(lower_expr, &lower_value)
- && IsAtMost(upper_expr, &upper_value)
+ return IsAtLeast(context, loop, lower_expr, &lower_value)
+ && IsAtMost(context, loop, upper_expr, &upper_value)
&& lower_value > upper_value;
case kCondGE:
- return IsAtLeast(lower_expr, &lower_value)
- && IsAtMost(upper_expr, &upper_value)
+ return IsAtLeast(context, loop, lower_expr, &lower_value)
+ && IsAtMost(context, loop, upper_expr, &upper_value)
&& lower_value >= upper_value;
default:
LOG(FATAL) << "CONDITION UNREACHABLE";
@@ -1152,7 +1182,9 @@
}
}
-bool HInductionVarAnalysis::IsFinite(InductionInfo* upper_expr,
+bool HInductionVarAnalysis::IsFinite(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* upper_expr,
int64_t stride_value,
DataType::Type type,
IfCondition cmp) {
@@ -1163,21 +1195,23 @@
switch (cmp) {
case kCondLT:
return stride_value == 1 ||
- (IsAtMost(upper_expr, &value) && value <= (max - stride_value + 1));
+ (IsAtMost(context, loop, upper_expr, &value) && value <= (max - stride_value + 1));
case kCondLE:
- return (IsAtMost(upper_expr, &value) && value <= (max - stride_value));
+ return (IsAtMost(context, loop, upper_expr, &value) && value <= (max - stride_value));
case kCondGT:
return stride_value == -1 ||
- (IsAtLeast(upper_expr, &value) && value >= (min - stride_value - 1));
+ (IsAtLeast(context, loop, upper_expr, &value) && value >= (min - stride_value - 1));
case kCondGE:
- return (IsAtLeast(upper_expr, &value) && value >= (min - stride_value));
+ return (IsAtLeast(context, loop, upper_expr, &value) && value >= (min - stride_value));
default:
LOG(FATAL) << "CONDITION UNREACHABLE";
UNREACHABLE();
}
}
-bool HInductionVarAnalysis::FitsNarrowerControl(InductionInfo* lower_expr,
+bool HInductionVarAnalysis::FitsNarrowerControl(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* lower_expr,
InductionInfo* upper_expr,
int64_t stride_value,
DataType::Type type,
@@ -1194,13 +1228,14 @@
}
// Do both bounds fit the range?
int64_t value = 0;
- return IsAtLeast(lower_expr, &value) && value >= min &&
- IsAtMost(lower_expr, &value) && value <= max &&
- IsAtLeast(upper_expr, &value) && value >= min &&
- IsAtMost(upper_expr, &value) && value <= max;
+ return IsAtLeast(context, loop, lower_expr, &value) && value >= min &&
+ IsAtMost(context, loop, lower_expr, &value) && value <= max &&
+ IsAtLeast(context, loop, upper_expr, &value) && value >= min &&
+ IsAtMost(context, loop, upper_expr, &value) && value <= max;
}
-bool HInductionVarAnalysis::RewriteBreakLoop(HLoopInformation* loop,
+bool HInductionVarAnalysis::RewriteBreakLoop(const HBasicBlock* context,
+ const HLoopInformation* loop,
HBasicBlock* body,
int64_t stride_value,
DataType::Type type) {
@@ -1219,7 +1254,8 @@
HInstruction* upper = cond->InputAt(1 - c);
// Safe to rewrite into i <= U?
IfCondition cmp = stride_value > 0 ? kCondLE : kCondGE;
- if (!index->IsPhi() || !IsFinite(LookupInfo(loop, upper), stride_value, type, cmp)) {
+ if (!index->IsPhi() ||
+ !IsFinite(context, loop, LookupInfo(loop, upper), stride_value, type, cmp)) {
return false;
}
// Body consists of update to index i only, used nowhere else.
@@ -1233,7 +1269,7 @@
return false;
}
// Always taken or guarded by enclosing condition.
- if (!IsTaken(LookupInfo(loop, index)->op_b, LookupInfo(loop, upper), cmp) &&
+ if (!IsTaken(context, loop, LookupInfo(loop, index)->op_b, LookupInfo(loop, upper), cmp) &&
!IsGuardedBy(loop, cmp, index->InputAt(0), upper)) {
return false;
}
@@ -1263,7 +1299,7 @@
// Helper methods.
//
-void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
+void HInductionVarAnalysis::AssignInfo(const HLoopInformation* loop,
HInstruction* instruction,
InductionInfo* info) {
auto it = induction_.find(loop);
@@ -1276,8 +1312,9 @@
it->second.Put(instruction, info);
}
-HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop,
- HInstruction* instruction) {
+HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(
+ const HLoopInformation* loop,
+ HInstruction* instruction) {
auto it = induction_.find(loop);
if (it != induction_.end()) {
auto loop_it = it->second.find(instruction);
@@ -1306,6 +1343,8 @@
}
HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant(
+ const HBasicBlock* context,
+ const HLoopInformation* loop,
InductionOp op,
InductionInfo* a,
InductionInfo* b) {
@@ -1314,7 +1353,7 @@
// More exhaustive simplifications are done by later phases once induction nodes are
// translated back into HIR code (e.g. by loop optimizations or BCE).
int64_t value = -1;
- if (IsExact(a, &value)) {
+ if (IsExact(context, loop, a, &value)) {
if (value == 0) {
// Simplify 0 + b = b, 0 ^ b = b, 0 * b = 0.
if (op == kAdd || op == kXor) {
@@ -1327,11 +1366,11 @@
if (value == 1) {
return b;
} else if (value == -1) {
- return CreateSimplifiedInvariant(kNeg, nullptr, b);
+ return CreateSimplifiedInvariant(context, loop, kNeg, nullptr, b);
}
}
}
- if (IsExact(b, &value)) {
+ if (IsExact(context, loop, b, &value)) {
if (value == 0) {
// Simplify a + 0 = a, a - 0 = a, a ^ 0 = a, a * 0 = 0, -0 = 0.
if (op == kAdd || op == kSub || op == kXor) {
@@ -1344,37 +1383,38 @@
if (value == 1) {
return a;
} else if (value == -1) {
- return CreateSimplifiedInvariant(kNeg, nullptr, a);
+ return CreateSimplifiedInvariant(context, loop, kNeg, nullptr, a);
}
}
} else if (b->operation == kNeg) {
// Simplify a + (-b) = a - b, a - (-b) = a + b, -(-b) = b.
if (op == kAdd) {
- return CreateSimplifiedInvariant(kSub, a, b->op_b);
+ return CreateSimplifiedInvariant(context, loop, kSub, a, b->op_b);
} else if (op == kSub) {
- return CreateSimplifiedInvariant(kAdd, a, b->op_b);
+ return CreateSimplifiedInvariant(context, loop, kAdd, a, b->op_b);
} else if (op == kNeg) {
return b->op_b;
}
} else if (b->operation == kSub) {
// Simplify - (a - b) = b - a.
if (op == kNeg) {
- return CreateSimplifiedInvariant(kSub, b->op_b, b->op_a);
+ return CreateSimplifiedInvariant(context, loop, kSub, b->op_b, b->op_a);
}
}
return new (graph_->GetAllocator()) InductionInfo(
kInvariant, op, a, b, nullptr, ImplicitConversion(b->type));
}
-HInstruction* HInductionVarAnalysis::GetShiftConstant(HLoopInformation* loop,
+HInstruction* HInductionVarAnalysis::GetShiftConstant(const HLoopInformation* loop,
HInstruction* instruction,
InductionInfo* initial) {
DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
+ const HBasicBlock* context = instruction->GetBlock();
// Shift-rights are only the same as division for non-negative initial inputs.
// Otherwise we would round incorrectly.
if (initial != nullptr) {
int64_t value = -1;
- if (!IsAtLeast(initial, &value) || value < 0) {
+ if (!IsAtLeast(context, loop, initial, &value) || value < 0) {
return nullptr;
}
}
@@ -1385,7 +1425,7 @@
// generalization for shift factors outside [0,32) and [0,64) ranges is done earlier.
InductionInfo* b = LookupInfo(loop, instruction->InputAt(1));
int64_t value = -1;
- if (IsExact(b, &value)) {
+ if (IsExact(context, loop, b, &value)) {
DataType::Type type = instruction->InputAt(0)->GetType();
if (type == DataType::Type::kInt32 && 0 <= value && value < 31) {
return graph_->GetIntConstant(1 << value);
@@ -1413,16 +1453,28 @@
return nullptr;
}
-bool HInductionVarAnalysis::IsExact(InductionInfo* info, int64_t* value) {
- return InductionVarRange(this).IsConstant(info, InductionVarRange::kExact, value);
+bool HInductionVarAnalysis::IsExact(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* info,
+ /*out*/int64_t* value) {
+ InductionVarRange range(this);
+ return range.IsConstant(context, loop, info, InductionVarRange::kExact, value);
}
-bool HInductionVarAnalysis::IsAtMost(InductionInfo* info, int64_t* value) {
- return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtMost, value);
+bool HInductionVarAnalysis::IsAtMost(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* info,
+ /*out*/int64_t* value) {
+ InductionVarRange range(this);
+ return range.IsConstant(context, loop, info, InductionVarRange::kAtMost, value);
}
-bool HInductionVarAnalysis::IsAtLeast(InductionInfo* info, int64_t* value) {
- return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtLeast, value);
+bool HInductionVarAnalysis::IsAtLeast(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* info,
+ /*out*/int64_t* value) {
+ InductionVarRange range(this);
+ return range.IsConstant(context, loop, info, InductionVarRange::kAtLeast, value);
}
bool HInductionVarAnalysis::IsNarrowingLinear(InductionInfo* info) {
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 616100b..0941772 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -119,9 +119,13 @@
};
- InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
+ InductionInfo* CreateInvariantOp(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionOp op,
+ InductionInfo* a,
+ InductionInfo* b) {
DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
- return CreateSimplifiedInvariant(op, a, b);
+ return CreateSimplifiedInvariant(context, loop, op, a, b);
}
InductionInfo* CreateInvariantFetch(HInstruction* f) {
@@ -149,29 +153,38 @@
}
// Methods for analysis.
- void VisitLoop(HLoopInformation* loop);
- size_t TryVisitNodes(HLoopInformation* loop,
+ void VisitLoop(const HLoopInformation* loop);
+ size_t TryVisitNodes(const HLoopInformation* loop,
HInstruction* start_instruction,
size_t global_depth,
/*inout*/ ScopedArenaSafeMap<HInstruction*, NodeInfo>* visited_instructions);
void ExtractScc(ArrayRef<const StackEntry> stack_tail, ScopedArenaVector<HInstruction*>* scc);
- void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
- void ClassifyNonTrivial(HLoopInformation* loop, ArrayRef<const StackEntry> stack_tail);
+ void ClassifyTrivial(const HLoopInformation* loop, HInstruction* instruction);
+ void ClassifyNonTrivial(const HLoopInformation* loop, ArrayRef<const StackEntry> stack_tail);
InductionInfo* RotatePeriodicInduction(InductionInfo* induction,
InductionInfo* last,
DataType::Type type);
// Transfer operations.
- InductionInfo* TransferPhi(HLoopInformation* loop,
+ InductionInfo* TransferPhi(const HLoopInformation* loop,
HInstruction* phi,
size_t input_index,
size_t adjust_input_size);
- InductionInfo* TransferAddSub(InductionInfo* a,
+ InductionInfo* TransferAddSub(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* a,
InductionInfo* b,
InductionOp op,
DataType::Type type);
- InductionInfo* TransferNeg(InductionInfo* a, DataType::Type type);
- InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b, DataType::Type type);
+ InductionInfo* TransferNeg(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* a,
+ DataType::Type type);
+ InductionInfo* TransferMul(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* a,
+ InductionInfo* b,
+ DataType::Type type);
InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to);
// Solvers.
@@ -179,12 +192,12 @@
size_t input_index,
size_t adjust_input_size,
const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle);
- InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
+ InductionInfo* SolvePhiAllInputs(const HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* phi,
const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
DataType::Type type);
- InductionInfo* SolveAddSub(HLoopInformation* loop,
+ InductionInfo* SolveAddSub(const HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
@@ -192,19 +205,19 @@
InductionOp op,
const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
DataType::Type type);
- InductionInfo* SolveOp(HLoopInformation* loop,
+ InductionInfo* SolveOp(const HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* instruction,
HInstruction* x,
HInstruction* y,
InductionOp op,
DataType::Type type);
- InductionInfo* SolveTest(HLoopInformation* loop,
+ InductionInfo* SolveTest(const HLoopInformation* loop,
HInstruction* entry_phi,
HInstruction* instruction,
int64_t opposite_value,
DataType::Type type);
- InductionInfo* SolveConversion(HLoopInformation* loop,
+ InductionInfo* SolveConversion(const HLoopInformation* loop,
HInstruction* entry_phi,
HTypeConversion* conversion,
const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
@@ -215,31 +228,42 @@
//
// Trip count information.
- void VisitControl(HLoopInformation* loop);
- void VisitCondition(HLoopInformation* loop,
+ void VisitControl(const HLoopInformation* loop);
+ void VisitCondition(const HBasicBlock* context,
+ const HLoopInformation* loop,
HBasicBlock* body,
InductionInfo* a,
InductionInfo* b,
DataType::Type type,
IfCondition cmp);
- void VisitTripCount(HLoopInformation* loop,
+ void VisitTripCount(const HBasicBlock* context,
+ const HLoopInformation* loop,
InductionInfo* lower_expr,
InductionInfo* upper_expr,
InductionInfo* stride,
int64_t stride_value,
DataType::Type type,
IfCondition cmp);
- bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp);
- bool IsFinite(InductionInfo* upper_expr,
+ bool IsTaken(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* lower_expr,
+ InductionInfo* upper_expr,
+ IfCondition cmp);
+ bool IsFinite(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* upper_expr,
int64_t stride_value,
DataType::Type type,
IfCondition cmp);
- bool FitsNarrowerControl(InductionInfo* lower_expr,
+ bool FitsNarrowerControl(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* lower_expr,
InductionInfo* upper_expr,
int64_t stride_value,
DataType::Type type,
IfCondition cmp);
- bool RewriteBreakLoop(HLoopInformation* loop,
+ bool RewriteBreakLoop(const HBasicBlock* context,
+ const HLoopInformation* loop,
HBasicBlock* body,
int64_t stride_value,
DataType::Type type);
@@ -249,20 +273,33 @@
//
// Assign and lookup.
- void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
- InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
+ void AssignInfo(const HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
+ InductionInfo* LookupInfo(const HLoopInformation* loop, HInstruction* instruction);
InductionInfo* CreateConstant(int64_t value, DataType::Type type);
- InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
- HInstruction* GetShiftConstant(HLoopInformation* loop,
+ InductionInfo* CreateSimplifiedInvariant(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionOp op,
+ InductionInfo* a,
+ InductionInfo* b);
+ HInstruction* GetShiftConstant(const HLoopInformation* loop,
HInstruction* instruction,
InductionInfo* initial);
void AssignCycle(HPhi* phi, ArrayRef<HInstruction* const> scc);
ArenaSet<HInstruction*>* LookupCycle(HPhi* phi);
// Constants.
- bool IsExact(InductionInfo* info, /*out*/ int64_t* value);
- bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value);
- bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value);
+ bool IsExact(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* info,
+ /*out*/int64_t* value);
+ bool IsAtMost(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* info,
+ /*out*/int64_t* value);
+ bool IsAtLeast(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ InductionInfo* info,
+ /*out*/int64_t* value);
// Helpers.
static bool IsNarrowingLinear(InductionInfo* info);
@@ -274,7 +311,7 @@
* Maintains the results of the analysis as a mapping from loops to a mapping from instructions
* to the induction information for that instruction in that loop.
*/
- ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
+ ArenaSafeMap<const HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
/**
* Preserves induction cycle information for each loop-phi.
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 72c2064..ad3d1a9 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -150,11 +150,44 @@
}
/** Obtains loop's control instruction. */
-static HInstruction* GetLoopControl(HLoopInformation* loop) {
+static HInstruction* GetLoopControl(const HLoopInformation* loop) {
DCHECK(loop != nullptr);
return loop->GetHeader()->GetLastInstruction();
}
+/** Determines whether the `context` is in the body of the `loop`. */
+static bool IsContextInBody(const HBasicBlock* context, const HLoopInformation* loop) {
+ DCHECK(loop != nullptr);
+ // We're currently classifying trip count only for the exit condition from loop header.
+ // All other blocks in the loop are considered loop body.
+ return context != loop->GetHeader() && loop->Contains(*context);
+}
+
+/** Determines whether to use the full trip count for given `context`, `loop` and `is_min`. */
+bool UseFullTripCount(const HBasicBlock* context, const HLoopInformation* loop, bool is_min) {
+ // We're currently classifying trip count only for the exit condition from loop header.
+ // So, we should call this helper function only if the loop control is an `HIf` with
+ // one edge leaving the loop. The loop header is the only block that's both inside
+ // the loop and not in the loop body.
+ DCHECK(GetLoopControl(loop)->IsIf());
+ DCHECK_NE(loop->Contains(*GetLoopControl(loop)->AsIf()->IfTrueSuccessor()),
+ loop->Contains(*GetLoopControl(loop)->AsIf()->IfFalseSuccessor()));
+ if (loop->Contains(*context)) {
+ // Use the full trip count if determining the maximum and context is not in the loop body.
+ DCHECK_NE(context == loop->GetHeader(), IsContextInBody(context, loop));
+ return !is_min && context == loop->GetHeader();
+ } else {
+ // Trip count after the loop is always the maximum (ignoring `is_min`),
+ // as long as the `context` is dominated by the loop control exit block.
+ // If there are additional exit edges, the value is unknown on those paths.
+ HInstruction* loop_control = GetLoopControl(loop);
+ HBasicBlock* then_block = loop_control->AsIf()->IfTrueSuccessor();
+ HBasicBlock* else_block = loop_control->AsIf()->IfFalseSuccessor();
+ HBasicBlock* loop_exit_block = loop->Contains(*then_block) ? else_block : then_block;
+ return loop_exit_block->Dominates(context);
+ }
+}
+
//
// Public class methods.
//
@@ -165,13 +198,13 @@
DCHECK(induction_analysis != nullptr);
}
-bool InductionVarRange::GetInductionRange(HInstruction* context,
+bool InductionVarRange::GetInductionRange(const HBasicBlock* context,
HInstruction* instruction,
HInstruction* chase_hint,
/*out*/Value* min_val,
/*out*/Value* max_val,
/*out*/bool* needs_finite_test) {
- HLoopInformation* loop = nullptr;
+ const HLoopInformation* loop = nullptr;
HInductionVarAnalysis::InductionInfo* info = nullptr;
HInductionVarAnalysis::InductionInfo* trip = nullptr;
if (!HasInductionInfo(context, instruction, &loop, &info, &trip)) {
@@ -192,20 +225,20 @@
}
// Find range.
chase_hint_ = chase_hint;
- bool in_body = context->GetBlock() != loop->GetHeader();
int64_t stride_value = 0;
- *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min= */ true));
- *max_val = SimplifyMax(GetVal(info, trip, in_body, /* is_min= */ false), chase_hint);
- *needs_finite_test = NeedsTripCount(info, &stride_value) && IsUnsafeTripCount(trip);
+ *min_val = SimplifyMin(GetVal(context, loop, info, trip, /*is_min=*/ true));
+ *max_val = SimplifyMax(GetVal(context, loop, info, trip, /*is_min=*/ false), chase_hint);
+ *needs_finite_test =
+ NeedsTripCount(context, loop, info, &stride_value) && IsUnsafeTripCount(trip);
chase_hint_ = nullptr;
// Retry chasing constants for wrap-around (merge sensitive).
if (!min_val->is_known && info->induction_class == HInductionVarAnalysis::kWrapAround) {
- *min_val = SimplifyMin(GetVal(info, trip, in_body, /* is_min= */ true));
+ *min_val = SimplifyMin(GetVal(context, loop, info, trip, /*is_min=*/ true));
}
return true;
}
-bool InductionVarRange::CanGenerateRange(HInstruction* context,
+bool InductionVarRange::CanGenerateRange(const HBasicBlock* context,
HInstruction* instruction,
/*out*/bool* needs_finite_test,
/*out*/bool* needs_taken_test) {
@@ -227,7 +260,7 @@
stride_value == 1); // avoid arithmetic wrap-around anomalies.
}
-void InductionVarRange::GenerateRange(HInstruction* context,
+void InductionVarRange::GenerateRange(const HBasicBlock* context,
HInstruction* instruction,
HGraph* graph,
HBasicBlock* block,
@@ -251,15 +284,16 @@
}
}
-HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context,
+HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* loop_control,
HGraph* graph,
HBasicBlock* block) {
+ const HBasicBlock* context = loop_control->GetBlock();
HInstruction* taken_test = nullptr;
bool is_last_value = false;
int64_t stride_value = 0;
bool b1, b2; // unused
if (!GenerateRangeOrLastValue(context,
- context,
+ loop_control,
is_last_value,
graph,
block,
@@ -275,11 +309,12 @@
}
bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) {
+ const HBasicBlock* context = instruction->GetBlock();
bool is_last_value = true;
int64_t stride_value = 0;
bool needs_finite_test = false;
bool needs_taken_test = false;
- return GenerateRangeOrLastValue(instruction,
+ return GenerateRangeOrLastValue(context,
instruction,
is_last_value,
nullptr,
@@ -296,11 +331,12 @@
HInstruction* InductionVarRange::GenerateLastValue(HInstruction* instruction,
HGraph* graph,
HBasicBlock* block) {
+ const HBasicBlock* context = instruction->GetBlock();
HInstruction* last_value = nullptr;
bool is_last_value = true;
int64_t stride_value = 0;
bool b1, b2; // unused
- if (!GenerateRangeOrLastValue(instruction,
+ if (!GenerateRangeOrLastValue(context,
instruction,
is_last_value,
graph,
@@ -329,32 +365,32 @@
}
}
-bool InductionVarRange::IsFinite(HLoopInformation* loop, /*out*/ int64_t* trip_count) const {
+bool InductionVarRange::IsFinite(const HLoopInformation* loop, /*out*/ int64_t* trip_count) const {
bool is_constant_unused = false;
return CheckForFiniteAndConstantProps(loop, &is_constant_unused, trip_count);
}
-bool InductionVarRange::HasKnownTripCount(HLoopInformation* loop,
+bool InductionVarRange::HasKnownTripCount(const HLoopInformation* loop,
/*out*/ int64_t* trip_count) const {
bool is_constant = false;
CheckForFiniteAndConstantProps(loop, &is_constant, trip_count);
return is_constant;
}
-bool InductionVarRange::IsUnitStride(HInstruction* context,
+bool InductionVarRange::IsUnitStride(const HBasicBlock* context,
HInstruction* instruction,
HGraph* graph,
/*out*/ HInstruction** offset) const {
- HLoopInformation* loop = nullptr;
+ const HLoopInformation* loop = nullptr;
HInductionVarAnalysis::InductionInfo* info = nullptr;
HInductionVarAnalysis::InductionInfo* trip = nullptr;
if (HasInductionInfo(context, instruction, &loop, &info, &trip)) {
if (info->induction_class == HInductionVarAnalysis::kLinear &&
!HInductionVarAnalysis::IsNarrowingLinear(info)) {
int64_t stride_value = 0;
- if (IsConstant(info->op_a, kExact, &stride_value) && stride_value == 1) {
+ if (IsConstant(context, loop, info->op_a, kExact, &stride_value) && stride_value == 1) {
int64_t off_value = 0;
- if (IsConstant(info->op_b, kExact, &off_value)) {
+ if (IsConstant(context, loop, info->op_b, kExact, &off_value)) {
*offset = graph->GetConstant(info->op_b->type, off_value);
} else if (info->op_b->operation == HInductionVarAnalysis::kFetch) {
*offset = info->op_b->fetch;
@@ -368,20 +404,35 @@
return false;
}
-HInstruction* InductionVarRange::GenerateTripCount(HLoopInformation* loop,
+HInstruction* InductionVarRange::GenerateTripCount(const HLoopInformation* loop,
HGraph* graph,
HBasicBlock* block) {
- HInductionVarAnalysis::InductionInfo *trip =
- induction_analysis_->LookupInfo(loop, GetLoopControl(loop));
+ HInstruction* loop_control = GetLoopControl(loop);
+ HInductionVarAnalysis::InductionInfo *trip = induction_analysis_->LookupInfo(loop, loop_control);
if (trip != nullptr && !IsUnsafeTripCount(trip)) {
+ const HBasicBlock* context = loop_control->GetBlock();
HInstruction* taken_test = nullptr;
HInstruction* trip_expr = nullptr;
if (IsBodyTripCount(trip)) {
- if (!GenerateCode(trip->op_b, nullptr, graph, block, &taken_test, false, false)) {
+ if (!GenerateCode(context,
+ loop,
+ trip->op_b,
+ /*trip=*/ nullptr,
+ graph,
+ block,
+ /*is_min=*/ false,
+ &taken_test)) {
return nullptr;
}
}
- if (GenerateCode(trip->op_a, nullptr, graph, block, &trip_expr, false, false)) {
+ if (GenerateCode(context,
+ loop,
+ trip->op_a,
+ /*trip=*/ nullptr,
+ graph,
+ block,
+ /*is_min=*/ false,
+ &trip_expr)) {
if (taken_test != nullptr) {
HInstruction* zero = graph->GetConstant(trip->type, 0);
ArenaAllocator* allocator = graph->GetAllocator();
@@ -397,19 +448,22 @@
// Private class methods.
//
-bool InductionVarRange::CheckForFiniteAndConstantProps(HLoopInformation* loop,
+bool InductionVarRange::CheckForFiniteAndConstantProps(const HLoopInformation* loop,
/*out*/ bool* is_constant,
/*out*/ int64_t* trip_count) const {
- HInductionVarAnalysis::InductionInfo *trip =
- induction_analysis_->LookupInfo(loop, GetLoopControl(loop));
+ HInstruction* loop_control = GetLoopControl(loop);
+ HInductionVarAnalysis::InductionInfo *trip = induction_analysis_->LookupInfo(loop, loop_control);
if (trip != nullptr && !IsUnsafeTripCount(trip)) {
- *is_constant = IsConstant(trip->op_a, kExact, trip_count);
+ const HBasicBlock* context = loop_control->GetBlock();
+ *is_constant = IsConstant(context, loop, trip->op_a, kExact, trip_count);
return true;
}
return false;
}
-bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info,
+bool InductionVarRange::IsConstant(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
ConstantRequest request,
/*out*/ int64_t* value) const {
if (info != nullptr) {
@@ -423,8 +477,8 @@
}
// Try range analysis on the invariant, only accept a proper range
// to avoid arithmetic wrap-around anomalies.
- Value min_val = GetVal(info, nullptr, /* in_body= */ true, /* is_min= */ true);
- Value max_val = GetVal(info, nullptr, /* in_body= */ true, /* is_min= */ false);
+ Value min_val = GetVal(context, loop, info, /*trip=*/ nullptr, /*is_min=*/ true);
+ Value max_val = GetVal(context, loop, info, /*trip=*/ nullptr, /*is_min=*/ false);
if (IsConstantValue(min_val) &&
IsConstantValue(max_val) && min_val.b_constant <= max_val.b_constant) {
if ((request == kExact && min_val.b_constant == max_val.b_constant) || request == kAtMost) {
@@ -440,14 +494,13 @@
}
bool InductionVarRange::HasInductionInfo(
- HInstruction* context,
+ const HBasicBlock* context,
HInstruction* instruction,
- /*out*/ HLoopInformation** loop,
+ /*out*/ const HLoopInformation** loop,
/*out*/ HInductionVarAnalysis::InductionInfo** info,
/*out*/ HInductionVarAnalysis::InductionInfo** trip) const {
DCHECK(context != nullptr);
- DCHECK(context->GetBlock() != nullptr);
- HLoopInformation* lp = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
+ HLoopInformation* lp = context->GetLoopInformation(); // closest enveloping loop
if (lp != nullptr) {
HInductionVarAnalysis::InductionInfo* i = induction_analysis_->LookupInfo(lp, instruction);
if (i != nullptr) {
@@ -460,7 +513,9 @@
return false;
}
-bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionInfo* trip) const {
+bool InductionVarRange::IsWellBehavedTripCount(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* trip) const {
if (trip != nullptr) {
// Both bounds that define a trip-count are well-behaved if they either are not defined
// in any loop, or are contained in a proper interval. This allows finding the min/max
@@ -469,8 +524,9 @@
HInductionVarAnalysis::InductionInfo* lower = trip->op_b->op_a;
HInductionVarAnalysis::InductionInfo* upper = trip->op_b->op_b;
int64_t not_used = 0;
- return (!HasFetchInLoop(lower) || range.IsConstant(lower, kAtLeast, ¬_used)) &&
- (!HasFetchInLoop(upper) || range.IsConstant(upper, kAtLeast, ¬_used));
+ return
+ (!HasFetchInLoop(lower) || range.IsConstant(context, loop, lower, kAtLeast, ¬_used)) &&
+ (!HasFetchInLoop(upper) || range.IsConstant(context, loop, upper, kAtLeast, ¬_used));
}
return true;
}
@@ -486,15 +542,17 @@
return false;
}
-bool InductionVarRange::NeedsTripCount(HInductionVarAnalysis::InductionInfo* info,
+bool InductionVarRange::NeedsTripCount(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
int64_t* stride_value) const {
if (info != nullptr) {
if (info->induction_class == HInductionVarAnalysis::kLinear) {
- return IsConstant(info->op_a, kExact, stride_value);
+ return IsConstant(context, loop, info->op_a, kExact, stride_value);
} else if (info->induction_class == HInductionVarAnalysis::kPolynomial) {
- return NeedsTripCount(info->op_a, stride_value);
+ return NeedsTripCount(context, loop, info->op_a, stride_value);
} else if (info->induction_class == HInductionVarAnalysis::kWrapAround) {
- return NeedsTripCount(info->op_b, stride_value);
+ return NeedsTripCount(context, loop, info->op_b, stride_value);
}
}
return false;
@@ -520,9 +578,10 @@
return false;
}
-InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::InductionInfo* info,
+InductionVarRange::Value InductionVarRange::GetLinear(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const {
DCHECK(info != nullptr);
DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kLinear);
@@ -534,7 +593,7 @@
HInductionVarAnalysis::InductionInfo* trip_expr = trip->op_a;
if (trip_expr->type == info->type && trip_expr->operation == HInductionVarAnalysis::kSub) {
int64_t stride_value = 0;
- if (IsConstant(info->op_a, kExact, &stride_value)) {
+ if (IsConstant(context, loop, info->op_a, kExact, &stride_value)) {
if (!is_min && stride_value == 1) {
// Test original trip's negative operand (trip_expr->op_b) against offset of induction.
if (HInductionVarAnalysis::InductionEqual(trip_expr->op_b, info->op_b)) {
@@ -546,7 +605,7 @@
trip->op_b,
nullptr,
trip->type);
- return GetVal(&cancelled_trip, trip, in_body, is_min);
+ return GetVal(context, loop, &cancelled_trip, trip, is_min);
}
} else if (is_min && stride_value == -1) {
// Test original trip's positive operand (trip_expr->op_a) against offset of induction.
@@ -561,72 +620,81 @@
trip->type);
HInductionVarAnalysis::InductionInfo cancelled_trip(
trip->induction_class, trip->operation, &neg, trip->op_b, nullptr, trip->type);
- return SubValue(Value(0), GetVal(&cancelled_trip, trip, in_body, !is_min));
+ return SubValue(Value(0), GetVal(context, loop, &cancelled_trip, trip, !is_min));
}
}
}
}
}
// General rule of linear induction a * i + b, for normalized 0 <= i < TC.
- return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min),
- GetVal(info->op_b, trip, in_body, is_min));
+ return AddValue(GetMul(context, loop, info->op_a, trip, trip, is_min),
+ GetVal(context, loop, info->op_b, trip, is_min));
}
-InductionVarRange::Value InductionVarRange::GetPolynomial(HInductionVarAnalysis::InductionInfo* info,
- HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
- bool is_min) const {
+InductionVarRange::Value InductionVarRange::GetPolynomial(
+ const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip,
+ bool is_min) const {
DCHECK(info != nullptr);
DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kPolynomial);
int64_t a = 0;
int64_t b = 0;
- if (IsConstant(info->op_a->op_a, kExact, &a) && CanLongValueFitIntoInt(a) && a >= 0 &&
- IsConstant(info->op_a->op_b, kExact, &b) && CanLongValueFitIntoInt(b) && b >= 0) {
+ if (IsConstant(context, loop, info->op_a->op_a, kExact, &a) &&
+ CanLongValueFitIntoInt(a) &&
+ a >= 0 &&
+ IsConstant(context, loop, info->op_a->op_b, kExact, &b) &&
+ CanLongValueFitIntoInt(b) &&
+ b >= 0) {
// Evaluate bounds on sum_i=0^m-1(a * i + b) + c with a,b >= 0 for
// maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
- Value c = GetVal(info->op_b, trip, in_body, is_min);
- if (is_min) {
- return c;
- } else {
- Value m = GetVal(trip, trip, in_body, is_min);
- Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2));
- Value x = MulValue(Value(a), t);
- Value y = MulValue(Value(b), m);
- return AddValue(AddValue(x, y), c);
- }
+ // Do not simply return `c` as minimum because the trip count may be non-zero
+ // if the `context` is after the `loop` (and therefore ignoring `is_min`).
+ Value c = GetVal(context, loop, info->op_b, trip, is_min);
+ Value m = GetVal(context, loop, trip, trip, is_min);
+ Value t = DivValue(MulValue(m, SubValue(m, Value(1))), Value(2));
+ Value x = MulValue(Value(a), t);
+ Value y = MulValue(Value(b), m);
+ return AddValue(AddValue(x, y), c);
}
return Value();
}
-InductionVarRange::Value InductionVarRange::GetGeometric(HInductionVarAnalysis::InductionInfo* info,
+InductionVarRange::Value InductionVarRange::GetGeometric(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const {
DCHECK(info != nullptr);
DCHECK_EQ(info->induction_class, HInductionVarAnalysis::kGeometric);
int64_t a = 0;
int64_t f = 0;
- if (IsConstant(info->op_a, kExact, &a) &&
+ if (IsConstant(context, loop, info->op_a, kExact, &a) &&
CanLongValueFitIntoInt(a) &&
IsInt64AndGet(info->fetch, &f) && f >= 1) {
// Conservative bounds on a * f^-i + b with f >= 1 can be computed without
// trip count. Other forms would require a much more elaborate evaluation.
const bool is_min_a = a >= 0 ? is_min : !is_min;
if (info->operation == HInductionVarAnalysis::kDiv) {
- Value b = GetVal(info->op_b, trip, in_body, is_min);
+ Value b = GetVal(context, loop, info->op_b, trip, is_min);
return is_min_a ? b : AddValue(Value(a), b);
}
}
return Value();
}
-InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
+InductionVarRange::Value InductionVarRange::GetFetch(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInstruction* instruction,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const {
// Special case when chasing constants: single instruction that denotes trip count in the
// loop-body is minimal 1 and maximal, with safe trip-count, max int,
- if (chase_hint_ == nullptr && in_body && trip != nullptr && instruction == trip->op_a->fetch) {
+ if (chase_hint_ == nullptr &&
+ IsContextInBody(context, loop) &&
+ trip != nullptr &&
+ instruction == trip->op_a->fetch) {
if (is_min) {
return Value(1);
} else if (!instruction->IsConstant() && !IsUnsafeTripCount(trip)) {
@@ -646,18 +714,18 @@
// Incorporate suitable constants in the chased value.
if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) {
return AddValue(Value(static_cast<int32_t>(value)),
- GetFetch(instruction->InputAt(1), trip, in_body, is_min));
+ GetFetch(context, loop, instruction->InputAt(1), trip, is_min));
} else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) {
- return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min),
+ return AddValue(GetFetch(context, loop, instruction->InputAt(0), trip, is_min),
Value(static_cast<int32_t>(value)));
}
} else if (instruction->IsSub()) {
// Incorporate suitable constants in the chased value.
if (IsInt64AndGet(instruction->InputAt(0), &value) && CanLongValueFitIntoInt(value)) {
return SubValue(Value(static_cast<int32_t>(value)),
- GetFetch(instruction->InputAt(1), trip, in_body, !is_min));
+ GetFetch(context, loop, instruction->InputAt(1), trip, !is_min));
} else if (IsInt64AndGet(instruction->InputAt(1), &value) && CanLongValueFitIntoInt(value)) {
- return SubValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min),
+ return SubValue(GetFetch(context, loop, instruction->InputAt(0), trip, is_min),
Value(static_cast<int32_t>(value)));
}
} else if (instruction->IsArrayLength()) {
@@ -665,39 +733,45 @@
if (chase_hint_ == nullptr) {
return is_min ? Value(0) : Value(std::numeric_limits<int32_t>::max());
} else if (instruction->InputAt(0)->IsNewArray()) {
- return GetFetch(instruction->InputAt(0)->AsNewArray()->GetLength(), trip, in_body, is_min);
+ return GetFetch(
+ context, loop, instruction->InputAt(0)->AsNewArray()->GetLength(), trip, is_min);
}
} else if (instruction->IsTypeConversion()) {
// Since analysis is 32-bit (or narrower), chase beyond widening along the path.
// For example, this discovers the length in: for (long i = 0; i < a.length; i++);
if (instruction->AsTypeConversion()->GetInputType() == DataType::Type::kInt32 &&
instruction->AsTypeConversion()->GetResultType() == DataType::Type::kInt64) {
- return GetFetch(instruction->InputAt(0), trip, in_body, is_min);
+ return GetFetch(context, loop, instruction->InputAt(0), trip, is_min);
}
}
- // Chase an invariant fetch that is defined by an outer loop if the trip-count used
+ // Chase an invariant fetch that is defined by another loop if the trip-count used
// so far is well-behaved in both bounds and the next trip-count is safe.
// Example:
// for (int i = 0; i <= 100; i++) // safe
// for (int j = 0; j <= i; j++) // well-behaved
// j is in range [0, i ] (if i is chase hint)
// or in range [0, 100] (otherwise)
- HLoopInformation* next_loop = nullptr;
+ // Example:
+ // for (i = 0; i < 100; ++i)
+ // <some-code>
+ // for (j = 0; j < 10; ++j)
+ // sum += i; // The `i` is a "fetch" of a loop Phi from the previous loop.
+ const HLoopInformation* next_loop = nullptr;
HInductionVarAnalysis::InductionInfo* next_info = nullptr;
HInductionVarAnalysis::InductionInfo* next_trip = nullptr;
- bool next_in_body = true; // inner loop is always in body of outer loop
- if (HasInductionInfo(instruction, instruction, &next_loop, &next_info, &next_trip) &&
- IsWellBehavedTripCount(trip) &&
+ if (HasInductionInfo(instruction->GetBlock(), instruction, &next_loop, &next_info, &next_trip) &&
+ IsWellBehavedTripCount(context, next_loop, trip) &&
!IsUnsafeTripCount(next_trip)) {
- return GetVal(next_info, next_trip, next_in_body, is_min);
+ return GetVal(context, next_loop, next_info, next_trip, is_min);
}
// Fetch is represented by itself.
return Value(instruction, 1, 0);
}
-InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info,
+InductionVarRange::Value InductionVarRange::GetVal(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const {
if (info != nullptr) {
switch (info->induction_class) {
@@ -705,36 +779,37 @@
// Invariants.
switch (info->operation) {
case HInductionVarAnalysis::kAdd:
- return AddValue(GetVal(info->op_a, trip, in_body, is_min),
- GetVal(info->op_b, trip, in_body, is_min));
+ return AddValue(GetVal(context, loop, info->op_a, trip, is_min),
+ GetVal(context, loop, info->op_b, trip, is_min));
case HInductionVarAnalysis::kSub: // second reversed!
- return SubValue(GetVal(info->op_a, trip, in_body, is_min),
- GetVal(info->op_b, trip, in_body, !is_min));
+ return SubValue(GetVal(context, loop, info->op_a, trip, is_min),
+ GetVal(context, loop, info->op_b, trip, !is_min));
case HInductionVarAnalysis::kNeg: // second reversed!
return SubValue(Value(0),
- GetVal(info->op_b, trip, in_body, !is_min));
+ GetVal(context, loop, info->op_b, trip, !is_min));
case HInductionVarAnalysis::kMul:
- return GetMul(info->op_a, info->op_b, trip, in_body, is_min);
+ return GetMul(context, loop, info->op_a, info->op_b, trip, is_min);
case HInductionVarAnalysis::kDiv:
- return GetDiv(info->op_a, info->op_b, trip, in_body, is_min);
+ return GetDiv(context, loop, info->op_a, info->op_b, trip, is_min);
case HInductionVarAnalysis::kRem:
- return GetRem(info->op_a, info->op_b);
+ return GetRem(context, loop, info->op_a, info->op_b);
case HInductionVarAnalysis::kXor:
- return GetXor(info->op_a, info->op_b);
+ return GetXor(context, loop, info->op_a, info->op_b);
case HInductionVarAnalysis::kFetch:
- return GetFetch(info->fetch, trip, in_body, is_min);
+ return GetFetch(context, loop, info->fetch, trip, 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);
+ if (UseFullTripCount(context, loop, is_min)) {
+ // Return the full trip count (do not subtract 1 as we do in loop body).
+ return GetVal(context, loop, info->op_a, trip, /*is_min=*/ false);
}
FALLTHROUGH_INTENDED;
case HInductionVarAnalysis::kTripCountInBody:
case HInductionVarAnalysis::kTripCountInBodyUnsafe:
if (is_min) {
return Value(0);
- } else if (in_body) {
- return SubValue(GetVal(info->op_a, trip, in_body, is_min), Value(1));
+ } else if (IsContextInBody(context, loop)) {
+ return SubValue(GetVal(context, loop, info->op_a, trip, is_min), Value(1));
}
break;
default:
@@ -742,37 +817,39 @@
}
break;
case HInductionVarAnalysis::kLinear:
- return CorrectForType(GetLinear(info, trip, in_body, is_min), info->type);
+ return CorrectForType(GetLinear(context, loop, info, trip, is_min), info->type);
case HInductionVarAnalysis::kPolynomial:
- return GetPolynomial(info, trip, in_body, is_min);
+ return GetPolynomial(context, loop, info, trip, is_min);
case HInductionVarAnalysis::kGeometric:
- return GetGeometric(info, trip, in_body, is_min);
+ return GetGeometric(context, loop, info, trip, is_min);
case HInductionVarAnalysis::kWrapAround:
case HInductionVarAnalysis::kPeriodic:
- return MergeVal(GetVal(info->op_a, trip, in_body, is_min),
- GetVal(info->op_b, trip, in_body, is_min), is_min);
+ return MergeVal(GetVal(context, loop, info->op_a, trip, is_min),
+ GetVal(context, loop, info->op_b, trip, is_min),
+ is_min);
}
}
return Value();
}
-InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1,
+InductionVarRange::Value InductionVarRange::GetMul(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const {
// Constant times range.
int64_t value = 0;
- if (IsConstant(info1, kExact, &value)) {
- return MulRangeAndConstant(value, info2, trip, in_body, is_min);
- } else if (IsConstant(info2, kExact, &value)) {
- return MulRangeAndConstant(value, info1, trip, in_body, is_min);
+ if (IsConstant(context, loop, info1, kExact, &value)) {
+ return MulRangeAndConstant(context, loop, value, info2, trip, is_min);
+ } else if (IsConstant(context, loop, info2, kExact, &value)) {
+ return MulRangeAndConstant(context, loop, value, info1, trip, is_min);
}
// Interval ranges.
- Value v1_min = GetVal(info1, trip, in_body, /* is_min= */ true);
- Value v1_max = GetVal(info1, trip, in_body, /* is_min= */ false);
- Value v2_min = GetVal(info2, trip, in_body, /* is_min= */ true);
- Value v2_max = GetVal(info2, trip, in_body, /* is_min= */ false);
+ Value v1_min = GetVal(context, loop, info1, trip, /*is_min=*/ true);
+ Value v1_max = GetVal(context, loop, info1, trip, /*is_min=*/ false);
+ Value v2_min = GetVal(context, loop, info2, trip, /*is_min=*/ true);
+ Value v2_max = GetVal(context, loop, info2, trip, /*is_min=*/ false);
// Positive range vs. positive or negative range.
if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
@@ -792,21 +869,22 @@
return Value();
}
-InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1,
+InductionVarRange::Value InductionVarRange::GetDiv(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const {
// Range divided by constant.
int64_t value = 0;
- if (IsConstant(info2, kExact, &value)) {
- return DivRangeAndConstant(value, info1, trip, in_body, is_min);
+ if (IsConstant(context, loop, info2, kExact, &value)) {
+ return DivRangeAndConstant(context, loop, value, info1, trip, is_min);
}
// Interval ranges.
- Value v1_min = GetVal(info1, trip, in_body, /* is_min= */ true);
- Value v1_max = GetVal(info1, trip, in_body, /* is_min= */ false);
- Value v2_min = GetVal(info2, trip, in_body, /* is_min= */ true);
- Value v2_max = GetVal(info2, trip, in_body, /* is_min= */ false);
+ Value v1_min = GetVal(context, loop, info1, trip, /*is_min=*/ true);
+ Value v1_max = GetVal(context, loop, info1, trip, /*is_min=*/ false);
+ Value v2_min = GetVal(context, loop, info2, trip, /*is_min=*/ true);
+ Value v2_max = GetVal(context, loop, info2, trip, /*is_min=*/ false);
// Positive range vs. positive or negative range.
if (IsConstantValue(v1_min) && v1_min.b_constant >= 0) {
if (IsConstantValue(v2_min) && v2_min.b_constant >= 0) {
@@ -827,12 +905,16 @@
}
InductionVarRange::Value InductionVarRange::GetRem(
+ const HBasicBlock* context,
+ const HLoopInformation* loop,
HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2) const {
int64_t v1 = 0;
int64_t v2 = 0;
// Only accept exact values.
- if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2) && v2 != 0) {
+ if (IsConstant(context, loop, info1, kExact, &v1) &&
+ IsConstant(context, loop, info2, kExact, &v2) &&
+ v2 != 0) {
int64_t value = v1 % v2;
if (CanLongValueFitIntoInt(value)) {
return Value(static_cast<int32_t>(value));
@@ -842,12 +924,15 @@
}
InductionVarRange::Value InductionVarRange::GetXor(
+ const HBasicBlock* context,
+ const HLoopInformation* loop,
HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2) const {
int64_t v1 = 0;
int64_t v2 = 0;
// Only accept exact values.
- if (IsConstant(info1, kExact, &v1) && IsConstant(info2, kExact, &v2)) {
+ if (IsConstant(context, loop, info1, kExact, &v1) &&
+ IsConstant(context, loop, info2, kExact, &v2)) {
int64_t value = v1 ^ v2;
if (CanLongValueFitIntoInt(value)) {
return Value(static_cast<int32_t>(value));
@@ -857,27 +942,29 @@
}
InductionVarRange::Value InductionVarRange::MulRangeAndConstant(
+ const HBasicBlock* context,
+ const HLoopInformation* loop,
int64_t value,
HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const {
if (CanLongValueFitIntoInt(value)) {
Value c(static_cast<int32_t>(value));
- return MulValue(GetVal(info, trip, in_body, is_min == value >= 0), c);
+ return MulValue(GetVal(context, loop, info, trip, is_min == value >= 0), c);
}
return Value();
}
InductionVarRange::Value InductionVarRange::DivRangeAndConstant(
+ const HBasicBlock* context,
+ const HLoopInformation* loop,
int64_t value,
HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const {
if (CanLongValueFitIntoInt(value)) {
Value c(static_cast<int32_t>(value));
- return DivValue(GetVal(info, trip, in_body, is_min == value >= 0), c);
+ return DivValue(GetVal(context, loop, info, trip, is_min == value >= 0), c);
}
return Value();
}
@@ -945,7 +1032,7 @@
return Value();
}
-bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context,
+bool InductionVarRange::GenerateRangeOrLastValue(const HBasicBlock* context,
HInstruction* instruction,
bool is_last_value,
HGraph* graph,
@@ -956,7 +1043,7 @@
/*out*/int64_t* stride_value,
/*out*/bool* needs_finite_test,
/*out*/bool* needs_taken_test) const {
- HLoopInformation* loop = nullptr;
+ const HLoopInformation* loop = nullptr;
HInductionVarAnalysis::InductionInfo* info = nullptr;
HInductionVarAnalysis::InductionInfo* trip = nullptr;
if (!HasInductionInfo(context, instruction, &loop, &info, &trip) || trip == nullptr) {
@@ -967,13 +1054,12 @@
// the computed range). A taken test is needed for any unknown trip-count, even if evaluation
// 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();
*stride_value = 0;
- *needs_finite_test = NeedsTripCount(info, stride_value) && IsUnsafeTripCount(trip);
+ *needs_finite_test = NeedsTripCount(context, loop, info, stride_value) && IsUnsafeTripCount(trip);
*needs_taken_test = IsBodyTripCount(trip);
// Handle last value request.
if (is_last_value) {
- DCHECK(!in_body);
+ DCHECK(!IsContextInBody(context, loop));
switch (info->induction_class) {
case HInductionVarAnalysis::kLinear:
if (*stride_value > 0) {
@@ -983,13 +1069,14 @@
}
break;
case HInductionVarAnalysis::kPolynomial:
- return GenerateLastValuePolynomial(info, trip, graph, block, lower);
+ return GenerateLastValuePolynomial(context, loop, info, trip, graph, block, lower);
case HInductionVarAnalysis::kGeometric:
- return GenerateLastValueGeometric(info, trip, graph, block, lower);
+ return GenerateLastValueGeometric(context, loop, info, trip, graph, block, lower);
case HInductionVarAnalysis::kWrapAround:
- return GenerateLastValueWrapAround(info, trip, graph, block, lower);
+ return GenerateLastValueWrapAround(context, loop, info, trip, graph, block, lower);
case HInductionVarAnalysis::kPeriodic:
- return GenerateLastValuePeriodic(info, trip, graph, block, lower, needs_taken_test);
+ return GenerateLastValuePeriodic(
+ context, loop, info, trip, graph, block, lower, needs_taken_test);
default:
return false;
}
@@ -997,10 +1084,23 @@
// 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);
+ return GenerateCode(context,
+ loop,
+ trip->op_b,
+ /*trip=*/ nullptr,
+ graph,
+ block,
+ /*is_min=*/ false,
+ taken_test);
} else if (*needs_taken_test) {
- if (!GenerateCode(
- trip->op_b, nullptr, nullptr, nullptr, nullptr, in_body, /* is_min= */ false)) {
+ if (!GenerateCode(context,
+ loop,
+ trip->op_b,
+ /*trip=*/ nullptr,
+ /*graph=*/ nullptr,
+ /*block=*/ nullptr,
+ /*is_min=*/ false,
+ /*result=*/ nullptr)) {
return false;
}
}
@@ -1008,12 +1108,14 @@
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)) &&
+ GenerateCode(context, loop, info, trip, graph, block, /*is_min=*/ true, lower)) &&
// And success on upper.
- GenerateCode(info, trip, graph, block, upper, in_body, /* is_min= */ false);
+ GenerateCode(context, loop, info, trip, graph, block, /*is_min=*/ false, upper);
}
-bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info,
+bool InductionVarRange::GenerateLastValuePolynomial(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
@@ -1024,13 +1126,21 @@
int64_t a = 0;
int64_t b = 0;
int64_t m = 0;
- if (IsConstant(info->op_a->op_a, kExact, &a) &&
- IsConstant(info->op_a->op_b, kExact, &b) &&
- IsConstant(trip->op_a, kExact, &m) && m >= 1) {
+ if (IsConstant(context, loop, info->op_a->op_a, kExact, &a) &&
+ IsConstant(context, loop, info->op_a->op_b, kExact, &b) &&
+ IsConstant(context, loop, trip->op_a, kExact, &m) &&
+ m >= 1) {
// Evaluate bounds on sum_i=0^m-1(a * i + b) + c for known
// maximum index value m as a * (m * (m-1)) / 2 + b * m + c.
HInstruction* c = nullptr;
- if (GenerateCode(info->op_b, nullptr, graph, block, graph ? &c : nullptr, false, false)) {
+ if (GenerateCode(context,
+ loop,
+ info->op_b,
+ /*trip=*/ nullptr,
+ graph,
+ block,
+ /*is_min=*/ false,
+ graph ? &c : nullptr)) {
if (graph != nullptr) {
DataType::Type type = info->type;
int64_t sum = a * ((m * (m - 1)) / 2) + b * m;
@@ -1046,7 +1156,9 @@
return false;
}
-bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info,
+bool InductionVarRange::GenerateLastValueGeometric(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
@@ -1056,11 +1168,16 @@
// Detect known base and trip count (always taken).
int64_t f = 0;
int64_t m = 0;
- if (IsInt64AndGet(info->fetch, &f) && f >= 1 && IsConstant(trip->op_a, kExact, &m) && m >= 1) {
+ if (IsInt64AndGet(info->fetch, &f) &&
+ f >= 1 &&
+ IsConstant(context, loop, trip->op_a, kExact, &m) &&
+ m >= 1) {
HInstruction* opa = nullptr;
HInstruction* opb = nullptr;
- if (GenerateCode(info->op_a, nullptr, graph, block, &opa, false, false) &&
- GenerateCode(info->op_b, nullptr, graph, block, &opb, false, false)) {
+ if (GenerateCode(
+ context, loop, info->op_a, /*trip=*/ nullptr, graph, block, /*is_min=*/ false, &opa) &&
+ GenerateCode(
+ context, loop, info->op_b, /*trip=*/ nullptr, graph, block, /*is_min=*/ false, &opb)) {
if (graph != nullptr) {
DataType::Type type = info->type;
// Compute f ^ m for known maximum index value m.
@@ -1098,7 +1215,9 @@
return false;
}
-bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info,
+bool InductionVarRange::GenerateLastValueWrapAround(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
@@ -1113,13 +1232,17 @@
// TODO: generalize, but be careful to adjust the terminal.
int64_t m = 0;
if (info->induction_class == HInductionVarAnalysis::kInvariant &&
- IsConstant(trip->op_a, kExact, &m) && m >= depth) {
- return GenerateCode(info, nullptr, graph, block, result, false, false);
+ IsConstant(context, loop, trip->op_a, kExact, &m) &&
+ m >= depth) {
+ return GenerateCode(
+ context, loop, info, /*trip=*/ nullptr, graph, block, /*is_min=*/ false, result);
}
return false;
}
-bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
+bool InductionVarRange::GenerateLastValuePeriodic(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
@@ -1150,13 +1273,14 @@
}
// Handle any periodic(x, periodic(.., y)) for known maximum index value m.
int64_t m = 0;
- if (IsConstant(trip->op_a, kExact, &m) && m >= 1) {
+ if (IsConstant(context, loop, trip->op_a, kExact, &m) && m >= 1) {
int64_t li = m % period;
for (int64_t i = 0; i < li; info = info->op_b, i++) {}
if (info->induction_class == HInductionVarAnalysis::kPeriodic) {
info = info->op_a;
}
- return GenerateCode(info, nullptr, graph, block, result, false, false);
+ return GenerateCode(
+ context, loop, info, /*trip=*/ nullptr, graph, block, /*is_min=*/ false, result);
}
// Handle periodic(x, y) using even/odd-select on trip count. Enter trip count expression
// directly to obtain the maximum index value t even if taken test is needed.
@@ -1164,9 +1288,30 @@
HInstruction* y = nullptr;
HInstruction* t = nullptr;
if (period == 2 &&
- GenerateCode(info->op_a, nullptr, graph, block, graph ? &x : nullptr, false, false) &&
- GenerateCode(info->op_b, nullptr, graph, block, graph ? &y : nullptr, false, false) &&
- GenerateCode(trip->op_a, nullptr, graph, block, graph ? &t : nullptr, false, false)) {
+ GenerateCode(context,
+ loop,
+ info->op_a,
+ /*trip=*/ nullptr,
+ graph,
+ block,
+ /*is_min=*/ false,
+ graph ? &x : nullptr) &&
+ GenerateCode(context,
+ loop,
+ info->op_b,
+ /*trip=*/ nullptr,
+ graph,
+ block,
+ /*is_min=*/ false,
+ graph ? &y : nullptr) &&
+ GenerateCode(context,
+ loop,
+ trip->op_a,
+ /*trip=*/ nullptr,
+ graph,
+ block,
+ /*is_min=*/ false,
+ graph ? &t : nullptr)) {
// During actual code generation (graph != nullptr), generate is_even ? x : y.
if (graph != nullptr) {
DataType::Type type = trip->type;
@@ -1180,7 +1325,14 @@
// Guard select with taken test if needed.
if (*needs_taken_test) {
HInstruction* is_taken = nullptr;
- if (GenerateCode(trip->op_b, nullptr, graph, block, graph ? &is_taken : nullptr, false, false)) {
+ if (GenerateCode(context,
+ loop,
+ trip->op_b,
+ /*trip=*/ nullptr,
+ graph,
+ block,
+ /*is_min=*/ false,
+ graph ? &is_taken : nullptr)) {
if (graph != nullptr) {
ArenaAllocator* allocator = graph->GetAllocator();
*result = Insert(block, new (allocator) HSelect(is_taken, *result, x, kNoDexPc));
@@ -1195,13 +1347,14 @@
return false;
}
-bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info,
+bool InductionVarRange::GenerateCode(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph, // when set, code is generated
HBasicBlock* block,
- /*out*/HInstruction** result,
- bool in_body,
- bool is_min) const {
+ bool is_min,
+ /*out*/HInstruction** result) const {
if (info != nullptr) {
// If during codegen, the result is not needed (nullptr), simply return success.
if (graph != nullptr && result == nullptr) {
@@ -1226,8 +1379,8 @@
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 (GenerateCode(context, loop, info->op_a, trip, graph, block, is_min, &opa) &&
+ GenerateCode(context, loop, info->op_b, trip, graph, block, is_min, &opb)) {
if (graph != nullptr) {
HInstruction* operation = nullptr;
switch (info->operation) {
@@ -1260,7 +1413,7 @@
}
break;
case HInductionVarAnalysis::kNeg:
- if (GenerateCode(info->op_b, trip, graph, block, &opb, in_body, !is_min)) {
+ if (GenerateCode(context, loop, info->op_b, trip, graph, block, !is_min, &opb)) {
if (graph != nullptr) {
*result = Insert(block, new (graph->GetAllocator()) HNeg(type, opb));
}
@@ -1274,8 +1427,10 @@
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);
+ if (UseFullTripCount(context, loop, is_min)) {
+ // Generate the full trip count (do not subtract 1 as we do in loop body).
+ return GenerateCode(
+ context, loop, info->op_a, trip, graph, block, /*is_min=*/ false, result);
}
FALLTHROUGH_INTENDED;
case HInductionVarAnalysis::kTripCountInBody:
@@ -1285,8 +1440,8 @@
*result = graph->GetConstant(type, 0);
}
return true;
- } else if (in_body) {
- if (GenerateCode(info->op_a, trip, graph, block, &opb, in_body, is_min)) {
+ } else if (IsContextInBody(context, loop)) {
+ if (GenerateCode(context, loop, info->op_a, trip, graph, block, is_min, &opb)) {
if (graph != nullptr) {
ArenaAllocator* allocator = graph->GetAllocator();
*result =
@@ -1309,11 +1464,11 @@
// TODO: careful runtime type conversions could generalize this latter restriction.
if (!HInductionVarAnalysis::IsNarrowingLinear(info) && trip->type == type) {
int64_t stride_value = 0;
- if (IsConstant(info->op_a, kExact, &stride_value) &&
+ if (IsConstant(context, loop, info->op_a, kExact, &stride_value) &&
CanLongValueFitIntoInt(stride_value)) {
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 (GenerateCode(context, loop, trip, trip, graph, block, is_min_a, &opa) &&
+ GenerateCode(context, loop, info->op_b, trip, graph, block, is_min, &opb)) {
if (graph != nullptr) {
ArenaAllocator* allocator = graph->GetAllocator();
HInstruction* oper;
@@ -1341,7 +1496,7 @@
case HInductionVarAnalysis::kPeriodic: {
// Wrap-around and periodic inductions are restricted to constants only, so that extreme
// values are easy to test at runtime without complications of arithmetic wrap-around.
- Value extreme = GetVal(info, trip, in_body, is_min);
+ Value extreme = GetVal(context, loop, info, trip, is_min);
if (IsConstantValue(extreme)) {
if (graph != nullptr) {
*result = graph->GetConstant(type, extreme.b_constant);
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 906dc6b..552837c 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -58,13 +58,13 @@
explicit InductionVarRange(HInductionVarAnalysis* induction);
/**
- * Given a context denoted by the first instruction, returns a possibly conservative lower
+ * Given a context block, 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. The parameter chase_hint defines an
* instruction at which chasing may stop. Returns false on failure.
*/
- bool GetInductionRange(HInstruction* context,
+ bool GetInductionRange(const HBasicBlock* context,
HInstruction* instruction,
HInstruction* chase_hint,
/*out*/ Value* min_val,
@@ -77,7 +77,7 @@
* 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 CanGenerateRange(HInstruction* context,
+ bool CanGenerateRange(const HBasicBlock* context,
HInstruction* instruction,
/*out*/ bool* needs_finite_test,
/*out*/ bool* needs_taken_test);
@@ -97,7 +97,7 @@
*
* Precondition: CanGenerateRange() returns true.
*/
- void GenerateRange(HInstruction* context,
+ void GenerateRange(const HBasicBlock* context,
HInstruction* instruction,
HGraph* graph,
HBasicBlock* block,
@@ -105,12 +105,12 @@
/*out*/ HInstruction** upper);
/**
- * Generates explicit taken-test for the loop in the given context. Code is generated in
+ * Generates explicit taken-test for the given `loop_control` instruction. Code is generated in
* given block and graph. Returns generated taken-test.
*
* Precondition: CanGenerateRange() returns true and needs_taken_test is set.
*/
- HInstruction* GenerateTakenTest(HInstruction* context, HGraph* graph, HBasicBlock* block);
+ HInstruction* GenerateTakenTest(HInstruction* loop_control, HGraph* graph, HBasicBlock* block);
/**
* Returns true if induction analysis is able to generate code for last value of
@@ -135,7 +135,7 @@
/**
* Incrementally updates induction information for just the given loop.
*/
- void ReVisit(HLoopInformation* loop) {
+ void ReVisit(const HLoopInformation* loop) {
induction_analysis_->induction_.erase(loop);
for (HInstructionIterator it(loop->GetHeader()->GetPhis()); !it.Done(); it.Advance()) {
induction_analysis_->cycles_.erase(it.Current()->AsPhi());
@@ -164,12 +164,12 @@
* Checks if header logic of a loop terminates. If trip count is known sets 'trip_count' to its
* value.
*/
- bool IsFinite(HLoopInformation* loop, /*out*/ int64_t* trip_count) const;
+ bool IsFinite(const HLoopInformation* loop, /*out*/ int64_t* trip_count) const;
/**
* Checks if a trip count is known for the loop and sets 'trip_count' to its value in this case.
*/
- bool HasKnownTripCount(HLoopInformation* loop, /*out*/ int64_t* trip_count) const;
+ bool HasKnownTripCount(const HLoopInformation* loop, /*out*/ int64_t* trip_count) const;
/**
* Checks if the given instruction is a unit stride induction inside the closest enveloping
@@ -177,7 +177,7 @@
* as context and the index as instruction to make sure the stride is tested against the
* loop that envelops the reference the closest). Returns invariant offset on success.
*/
- bool IsUnitStride(HInstruction* context,
+ bool IsUnitStride(const HBasicBlock* context,
HInstruction* instruction,
HGraph* graph,
/*out*/ HInstruction** offset) const;
@@ -187,7 +187,7 @@
* and graph. The expression is guarded by a taken test if needed. Returns the trip count
* expression on success or null otherwise.
*/
- HInstruction* GenerateTripCount(HLoopInformation* loop, HGraph* graph, HBasicBlock* block);
+ HInstruction* GenerateTripCount(const HLoopInformation* loop, HGraph* graph, HBasicBlock* block);
private:
/*
@@ -203,7 +203,7 @@
* Checks if header logic of a loop terminates. If trip count is known (constant) sets
* 'is_constant' to true and 'trip_count' to the trip count value.
*/
- bool CheckForFiniteAndConstantProps(HLoopInformation* loop,
+ bool CheckForFiniteAndConstantProps(const HLoopInformation* loop,
/*out*/ bool* is_constant,
/*out*/ int64_t* trip_count) const;
@@ -211,68 +211,87 @@
* Returns true if exact or upper/lower bound on the given induction
* information is known as a 64-bit constant, which is returned in value.
*/
- bool IsConstant(HInductionVarAnalysis::InductionInfo* info,
+ bool IsConstant(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
ConstantRequest request,
/*out*/ int64_t* value) const;
/** Returns whether induction information can be obtained. */
- bool HasInductionInfo(HInstruction* context,
+ bool HasInductionInfo(const HBasicBlock* context,
HInstruction* instruction,
- /*out*/ HLoopInformation** loop,
+ /*out*/ const HLoopInformation** loop,
/*out*/ HInductionVarAnalysis::InductionInfo** info,
/*out*/ HInductionVarAnalysis::InductionInfo** trip) const;
bool HasFetchInLoop(HInductionVarAnalysis::InductionInfo* info) const;
- bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info,
+ bool NeedsTripCount(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ 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;
+ bool IsWellBehavedTripCount(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* trip) const;
- Value GetLinear(HInductionVarAnalysis::InductionInfo* info,
+ Value GetLinear(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const;
- Value GetPolynomial(HInductionVarAnalysis::InductionInfo* info,
+ Value GetPolynomial(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const;
- Value GetGeometric(HInductionVarAnalysis::InductionInfo* info,
+ Value GetGeometric(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const;
- Value GetFetch(HInstruction* instruction,
+ Value GetFetch(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInstruction* instruction,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const;
- Value GetVal(HInductionVarAnalysis::InductionInfo* info,
+ Value GetVal(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const;
- Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
+ Value GetMul(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const;
- Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
+ Value GetDiv(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const;
- Value GetRem(HInductionVarAnalysis::InductionInfo* info1,
+ Value GetRem(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2) const;
- Value GetXor(HInductionVarAnalysis::InductionInfo* info1,
+ Value GetXor(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2) const;
- Value MulRangeAndConstant(int64_t value,
+ Value MulRangeAndConstant(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ int64_t value,
HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const;
- Value DivRangeAndConstant(int64_t value,
+ Value DivRangeAndConstant(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ int64_t value,
HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
- bool in_body,
bool is_min) const;
Value AddValue(Value v1, Value v2) const;
@@ -286,7 +305,7 @@
* success. With values nullptr, the method can be used to determine if code generation
* would be successful without generating actual code yet.
*/
- bool GenerateRangeOrLastValue(HInstruction* context,
+ bool GenerateRangeOrLastValue(const HBasicBlock* context,
HInstruction* instruction,
bool is_last_val,
HGraph* graph,
@@ -298,38 +317,47 @@
/*out*/ bool* needs_finite_test,
/*out*/ bool* needs_taken_test) const;
- bool GenerateLastValuePolynomial(HInductionVarAnalysis::InductionInfo* info,
+ bool GenerateLastValuePolynomial(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
/*out*/HInstruction** result) const;
- bool GenerateLastValueGeometric(HInductionVarAnalysis::InductionInfo* info,
+ bool GenerateLastValueGeometric(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
/*out*/HInstruction** result) const;
- bool GenerateLastValueWrapAround(HInductionVarAnalysis::InductionInfo* info,
+ bool GenerateLastValueWrapAround(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
/*out*/HInstruction** result) const;
- bool GenerateLastValuePeriodic(HInductionVarAnalysis::InductionInfo* info,
+ bool GenerateLastValuePeriodic(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
/*out*/HInstruction** result,
/*out*/ bool* needs_taken_test) const;
- bool GenerateCode(HInductionVarAnalysis::InductionInfo* info,
+ bool GenerateCode(const HBasicBlock* context,
+ const HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
HGraph* graph,
HBasicBlock* block,
- /*out*/ HInstruction** result,
- bool in_body,
- bool is_min) const;
+ bool is_min,
+ /*out*/ HInstruction** result) const;
void ReplaceInduction(HInductionVarAnalysis::InductionInfo* info,
HInstruction* fetch,
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index f6af384..962123d 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -145,7 +145,10 @@
case '<': op = HInductionVarAnalysis::kLT; break;
default: op = HInductionVarAnalysis::kNop; break;
}
- return iva_->CreateInvariantOp(op, a, b);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return iva_->CreateInvariantOp(context, &loop, op, a, b);
}
/** Constructs a fetch. */
@@ -238,8 +241,11 @@
//
bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) {
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
int64_t s = 0;
- return range_.NeedsTripCount(info, &s);
+ return range_.NeedsTripCount(context, &loop, info, &s);
}
bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) {
@@ -252,46 +258,87 @@
Value GetMin(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip) {
- return range_.GetVal(info, trip, /* in_body= */ true, /* is_min= */ true);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return GetMin(context, &loop, info, trip);
+ }
+
+ Value GetMin(HBasicBlock* context,
+ HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip) {
+ return range_.GetVal(context, loop, info, trip, /*is_min=*/ true);
}
Value GetMax(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip) {
- return range_.GetVal(info, trip, /* in_body= */ true, /* is_min= */ false);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return GetMax(context, &loop, info, trip);
+ }
+
+ Value GetMax(HBasicBlock* context,
+ HLoopInformation* loop,
+ HInductionVarAnalysis::InductionInfo* info,
+ HInductionVarAnalysis::InductionInfo* trip) {
+ return range_.GetVal(context, loop, info, trip, /*is_min=*/ false);
}
Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
bool is_min) {
- return range_.GetMul(info1, info2, nullptr, /* in_body= */ true, is_min);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return range_.GetMul(context, &loop, info1, info2, nullptr, is_min);
}
Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
bool is_min) {
- return range_.GetDiv(info1, info2, nullptr, /* in_body= */ true, is_min);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return range_.GetDiv(context, &loop, info1, info2, nullptr, is_min);
}
Value GetRem(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2) {
- return range_.GetRem(info1, info2);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return range_.GetRem(context, &loop, info1, info2);
}
Value GetXor(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2) {
- return range_.GetXor(info1, info2);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return range_.GetXor(context, &loop, info1, info2);
}
bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
- return range_.IsConstant(info, InductionVarRange::kExact, value);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return range_.IsConstant(context, &loop, info, InductionVarRange::kExact, value);
}
bool IsAtMost(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
- return range_.IsConstant(info, InductionVarRange::kAtMost, value);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return range_.IsConstant(context, &loop, info, InductionVarRange::kAtMost, value);
}
bool IsAtLeast(HInductionVarAnalysis::InductionInfo* info, int64_t* value) {
- return range_.IsConstant(info, InductionVarRange::kAtLeast, value);
+ // Use bogus loop information and context out of the bogus loop.
+ HLoopInformation loop(exit_block_, graph_);
+ HBasicBlock* context = entry_block_;
+ return range_.IsConstant(context, &loop, info, InductionVarRange::kAtLeast, value);
}
Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); }
@@ -447,10 +494,44 @@
}
TEST_F(InductionVarRangeTest, GetMinMaxLinear) {
- 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)));
+ BuildLoop(0, graph_->GetIntConstant(100), 1);
+ PerformInductionVarAnalysis();
+ HLoopInformation* loop = loop_header_->GetLoopInformation();
+ ASSERT_TRUE(loop != nullptr);
+
+ ExpectEqual(Value(20),
+ GetMin(loop_header_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(1020),
+ GetMax(loop_header_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(20),
+ GetMin(loop_body_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(1010),
+ GetMax(loop_body_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(1020),
+ GetMin(exit_block_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(1020),
+ GetMax(exit_block_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(20),
+ GetMin(entry_block_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(),
+ GetMax(entry_block_, loop, CreateLinear(10, 20), CreateTripCount(100, true, true)));
+
+ ExpectEqual(Value(-980),
+ GetMin(loop_header_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(20),
+ GetMax(loop_header_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(-970),
+ GetMin(loop_body_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(20),
+ GetMax(loop_body_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(-980),
+ GetMin(exit_block_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(-980),
+ GetMax(exit_block_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(),
+ GetMin(entry_block_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
+ ExpectEqual(Value(20),
+ GetMax(entry_block_, loop, CreateLinear(-10, 20), CreateTripCount(100, true, true)));
}
TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) {
@@ -463,24 +544,163 @@
}
TEST_F(InductionVarRangeTest, GetMinMaxPolynomial) {
- ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), nullptr));
+ BuildLoop(0, graph_->GetIntConstant(100), 1);
+ PerformInductionVarAnalysis();
+ HLoopInformation* loop = loop_header_->GetLoopInformation();
+ ASSERT_TRUE(loop != nullptr);
+
+ ExpectEqual(Value(), GetMin(CreatePolynomial(3, 5, 7), nullptr));
ExpectEqual(Value(), GetMax(CreatePolynomial(3, 5, 7), nullptr));
- ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
- ExpectEqual(Value(45), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
- ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
- ExpectEqual(Value(160), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
- ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7),
- CreateTripCount(5, true, true)));
- ExpectEqual(Value(111), GetMax(CreatePolynomial(11, 13, -7),
- CreateTripCount(5, true, true)));
- ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7),
- CreateTripCount(10, true, true)));
- ExpectEqual(Value(506), GetMax(CreatePolynomial(11, 13, -7),
- CreateTripCount(10, true, true)));
- ExpectEqual(Value(), GetMin(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
- ExpectEqual(Value(), GetMax(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
- ExpectEqual(Value(), GetMin(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
- ExpectEqual(Value(), GetMax(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+
+ ExpectEqual(
+ Value(7),
+ GetMin(loop_header_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(62),
+ GetMax(loop_header_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(7),
+ GetMin(loop_body_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(45),
+ GetMax(loop_body_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(62),
+ GetMin(exit_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(62),
+ GetMax(exit_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(7),
+ GetMin(entry_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(entry_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true)));
+
+ ExpectEqual(
+ Value(7),
+ GetMin(loop_header_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(192),
+ GetMax(loop_header_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(7),
+ GetMin(loop_body_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(160),
+ GetMax(loop_body_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(192),
+ GetMin(exit_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(192),
+ GetMax(exit_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(7),
+ GetMin(entry_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(entry_block_, loop, CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true)));
+
+ ExpectEqual(
+ Value(-7),
+ GetMin(loop_header_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(168),
+ GetMax(loop_header_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(-7),
+ GetMin(loop_body_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(111),
+ GetMax(loop_body_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(168),
+ GetMin(exit_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(168),
+ GetMax(exit_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(-7),
+ GetMin(entry_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(entry_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(5, true, true)));
+
+ ExpectEqual(
+ Value(-7),
+ GetMin(loop_header_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(618),
+ GetMax(loop_header_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(-7),
+ GetMin(loop_body_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(506),
+ GetMax(loop_body_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(618),
+ GetMin(exit_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(618),
+ GetMax(exit_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(-7),
+ GetMin(entry_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(entry_block_, loop, CreatePolynomial(11, 13, -7), CreateTripCount(10, true, true)));
+
+ ExpectEqual(
+ Value(),
+ GetMin(loop_header_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(loop_header_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMin(loop_body_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(loop_body_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMin(exit_block_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(exit_block_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMin(entry_block_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(entry_block_, loop, CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true)));
+
+ ExpectEqual(
+ Value(),
+ GetMin(loop_header_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(loop_header_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMin(loop_body_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(loop_body_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMin(exit_block_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(exit_block_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMin(entry_block_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
+ ExpectEqual(
+ Value(),
+ GetMax(entry_block_, loop, CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true)));
}
TEST_F(InductionVarRangeTest, GetMinMaxGeometricMul) {
@@ -763,25 +983,27 @@
HInstruction* exit = exit_block_->GetLastInstruction();
// In context of header: known.
- range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_->GetBlock(), 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_, phi, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(999), v2);
- range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
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_.CanGenerateRange(increment_->GetBlock(), 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_.CanGenerateRange(exit->GetBlock(), exit, &needs_finite_test, &needs_taken_test));
EXPECT_FALSE(range_.CanGenerateLastValue(exit));
// Last value (unsimplified).
@@ -795,7 +1017,7 @@
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(1000, tc);
HInstruction* offset = nullptr;
- EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset));
+ EXPECT_TRUE(range_.IsUnitStride(phi->GetBlock(), phi, graph_, &offset));
ExpectInt(0, offset);
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
@@ -815,25 +1037,27 @@
HInstruction* exit = exit_block_->GetLastInstruction();
// In context of header: known.
- range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_->GetBlock(), 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_, phi, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(1000), v2);
- range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
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_.CanGenerateRange(increment_->GetBlock(), 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_.CanGenerateRange(exit->GetBlock(), exit, &needs_finite_test, &needs_taken_test));
EXPECT_FALSE(range_.CanGenerateLastValue(exit));
// Last value (unsimplified).
@@ -851,7 +1075,7 @@
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(1000, tc);
HInstruction* offset = nullptr;
- EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset));
+ EXPECT_FALSE(range_.IsUnitStride(phi->GetBlock(), phi, graph_, &offset));
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
@@ -873,17 +1097,17 @@
HInstruction* phi = condition_->InputAt(0);
// In context of header: upper unknown.
- range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_->GetBlock(), 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_, phi, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(x_, 1, -1), v2);
- range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(x_, 1, 0), v2);
@@ -892,13 +1116,15 @@
HInstruction* upper = nullptr;
// Can generate code in context of loop-body only.
- 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(
+ range_.CanGenerateRange(condition_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
+ ASSERT_TRUE(
+ range_.CanGenerateRange(increment_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
EXPECT_FALSE(needs_finite_test);
EXPECT_TRUE(needs_taken_test);
// Generates code (unsimplified).
- range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper);
+ range_.GenerateRange(increment_->GetBlock(), phi, graph_, loop_preheader_, &lower, &upper);
// Verify lower is 0+0.
ASSERT_TRUE(lower != nullptr);
@@ -923,7 +1149,7 @@
// Replacement.
range_.Replace(loop_header_->GetLastInstruction(), x_, y_);
- range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(y_, 1, 0), v2);
@@ -933,7 +1159,7 @@
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(0, tc); // unknown
HInstruction* offset = nullptr;
- EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset));
+ EXPECT_TRUE(range_.IsUnitStride(phi->GetBlock(), phi, graph_, &offset));
ExpectInt(0, offset);
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
@@ -955,17 +1181,17 @@
HInstruction* phi = condition_->InputAt(0);
// In context of header: lower unknown.
- range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(condition_->GetBlock(), 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_, phi, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), phi, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(x_, 1, 1), v1);
ExpectEqual(Value(1000), v2);
- range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(x_, 1, 0), v1);
ExpectEqual(Value(999), v2);
@@ -974,13 +1200,15 @@
HInstruction* upper = nullptr;
// Can generate code in context of loop-body only.
- 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(
+ range_.CanGenerateRange(condition_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
+ ASSERT_TRUE(
+ range_.CanGenerateRange(increment_->GetBlock(), phi, &needs_finite_test, &needs_taken_test));
EXPECT_FALSE(needs_finite_test);
EXPECT_TRUE(needs_taken_test);
// Generates code (unsimplified).
- range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper);
+ range_.GenerateRange(increment_->GetBlock(), phi, graph_, loop_preheader_, &lower, &upper);
// Verify lower is 1000-((1000-V)-1).
ASSERT_TRUE(lower != nullptr);
@@ -1009,7 +1237,7 @@
// Replacement.
range_.Replace(loop_header_->GetLastInstruction(), x_, y_);
- range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test);
+ range_.GetInductionRange(increment_->GetBlock(), increment_, x_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(y_, 1, 0), v1);
ExpectEqual(Value(999), v2);
@@ -1019,7 +1247,7 @@
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(0, tc); // unknown
HInstruction* offset = nullptr;
- EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset));
+ EXPECT_FALSE(range_.IsUnitStride(phi->GetBlock(), phi, graph_, &offset));
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 9e298a5..77dfe68 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -1331,7 +1331,7 @@
}
if (TrySetVectorType(type, &restrictions) &&
node->loop_info->IsDefinedOutOfTheLoop(base) &&
- induction_range_.IsUnitStride(instruction, index, graph_, &offset) &&
+ induction_range_.IsUnitStride(instruction->GetBlock(), index, graph_, &offset) &&
VectorizeUse(node, value, generate_code, type, restrictions)) {
if (generate_code) {
GenerateVecSub(index, offset);
@@ -1412,7 +1412,7 @@
HInstruction* offset = nullptr;
if (HVecOperation::ToSignedType(type) == HVecOperation::ToSignedType(instruction->GetType()) &&
node->loop_info->IsDefinedOutOfTheLoop(base) &&
- induction_range_.IsUnitStride(instruction, index, graph_, &offset)) {
+ induction_range_.IsUnitStride(instruction->GetBlock(), index, graph_, &offset)) {
if (generate_code) {
GenerateVecSub(index, offset);
GenerateVecMem(instruction, vector_map_->Get(index), nullptr, offset, type);
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 0018a5b..d35ed1c 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1110,10 +1110,10 @@
return false;
}
-bool HBasicBlock::Dominates(HBasicBlock* other) const {
+bool HBasicBlock::Dominates(const HBasicBlock* other) const {
// Walk up the dominator tree from `other`, to find out if `this`
// is an ancestor.
- HBasicBlock* current = other;
+ const HBasicBlock* current = other;
while (current != nullptr) {
if (current == this) {
return true;
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 42f03a0..7a0059f 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1417,7 +1417,7 @@
bool HasThrowingInstructions() const;
// Returns whether this block dominates the blocked passed as parameter.
- bool Dominates(HBasicBlock* block) const;
+ bool Dominates(const HBasicBlock* block) const;
size_t GetLifetimeStart() const { return lifetime_start_; }
size_t GetLifetimeEnd() const { return lifetime_end_; }
diff --git a/test/knownfailures.json b/test/knownfailures.json
index c5bad79..c258f0f 100644
--- a/test/knownfailures.json
+++ b/test/knownfailures.json
@@ -1478,12 +1478,6 @@
"description": ["jit-on-first-use disables jit GC but this test requires jit GC"]
},
{
- "tests": ["835-b216762268"],
- "variant": "jit | optimizing | jit-on-first-use",
- "bug": "b/216762268",
- "description": ["bug in the loop optimization"]
- },
- {
"tests": ["445-checker-licm",
"449-checker-bce",
"455-checker-gvn",