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/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) {