diff options
| -rw-r--r-- | compiler/optimizing/bounds_check_elimination.cc | 24 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_analysis.cc | 312 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_analysis.h | 97 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range.cc | 511 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range.h | 120 | ||||
| -rw-r--r-- | compiler/optimizing/induction_var_range_test.cc | 348 | ||||
| -rw-r--r-- | compiler/optimizing/loop_optimization.cc | 4 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.cc | 4 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.h | 2 | ||||
| -rw-r--r-- | test/knownfailures.json | 6 |
10 files changed, 966 insertions, 462 deletions
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc index 2d02e9f427..dad3c818fa 100644 --- a/compiler/optimizing/bounds_check_elimination.cc +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -911,7 +911,7 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { // 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 e6d90795a1..3b5a2f1f9d 100644 --- a/compiler/optimizing/induction_var_analysis.cc +++ b/compiler/optimizing/induction_var_analysis.cc @@ -63,7 +63,7 @@ static DataType::Type ImplicitConversion(DataType::Type type) { /** * 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 @@ static bool IsGuardedBy(HLoopInformation* loop, } /* 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 @@ HInstruction* FindFirstLoopHeaderPhiUse(HLoopInformation* loop, HInstruction* in /** * 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 @@ static bool FixOutsideUse(HLoopInformation* loop, /** * 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 @@ struct HInductionVarAnalysis::StackEntry { 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 @@ bool HInductionVarAnalysis::Run() { 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 @@ void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) { } 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 @@ void HInductionVarAnalysis::ExtractScc(ArrayRef<const StackEntry> stack_tail, 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::ClassifyTrivial(HLoopInformation* loop, HInstruction } } -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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduc 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopIn 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(Indu 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(Indu } 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(Indu 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(Inducti 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(Inducti 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::SolvePhi( } 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::SolvePhiAllInputs( } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub( - HLoopInformation* loop, + const HLoopInformation* loop, HInstruction* entry_phi, HInstruction* instruction, HInstruction* x, @@ -792,6 +812,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub( 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub( // 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub( 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub( 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub( 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInform } // 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInform 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInform 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveConversion( 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveConversion( // 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 @@ void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) { // 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 @@ void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) { 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 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, 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 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, 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 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, // 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 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, // 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 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, // (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 @@ void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, // 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::IsTaken(InductionInfo* lower_expr, } } -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 @@ bool HInductionVarAnalysis::IsFinite(InductionInfo* upper_expr, 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 @@ bool HInductionVarAnalysis::FitsNarrowerControl(InductionInfo* lower_expr, } // 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 @@ bool HInductionVarAnalysis::RewriteBreakLoop(HLoopInformation* loop, 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 @@ bool HInductionVarAnalysis::RewriteBreakLoop(HLoopInformation* loop, 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 @@ bool HInductionVarAnalysis::RewriteBreakLoop(HLoopInformation* loop, // 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 @@ void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop, 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::CreateConstant(int6 } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant( + const HBasicBlock* context, + const HLoopInformation* loop, InductionOp op, InductionInfo* a, InductionInfo* b) { @@ -1314,7 +1353,7 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv // 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv 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 @@ HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInv 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 @@ HInstruction* HInductionVarAnalysis::GetShiftConstant(HLoopInformation* loop, // 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 @@ ArenaSet<HInstruction*>* HInductionVarAnalysis::LookupCycle(HPhi* phi) { 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 616100b068..09417722da 100644 --- a/compiler/optimizing/induction_var_analysis.h +++ b/compiler/optimizing/induction_var_analysis.h @@ -119,9 +119,13 @@ class HInductionVarAnalysis : public HOptimization { }; - 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 @@ class HInductionVarAnalysis : public HOptimization { } // 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 @@ class HInductionVarAnalysis : public HOptimization { 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 @@ class HInductionVarAnalysis : public HOptimization { 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 @@ class HInductionVarAnalysis : public HOptimization { // // 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 @@ class HInductionVarAnalysis : public HOptimization { // // 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 @@ class HInductionVarAnalysis : public HOptimization { * 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 72c2064d89..ad3d1a9321 100644 --- a/compiler/optimizing/induction_var_range.cc +++ b/compiler/optimizing/induction_var_range.cc @@ -150,11 +150,44 @@ static HInstruction* Insert(HBasicBlock* block, HInstruction* instruction) { } /** 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 @@ InductionVarRange::InductionVarRange(HInductionVarAnalysis* induction_analysis) 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 @@ bool InductionVarRange::GetInductionRange(HInstruction* context, } // 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 @@ bool InductionVarRange::CanGenerateRange(HInstruction* context, 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 @@ void InductionVarRange::GenerateRange(HInstruction* context, } } -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 @@ HInstruction* InductionVarRange::GenerateTakenTest(HInstruction* context, } 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 @@ bool InductionVarRange::CanGenerateLastValue(HInstruction* instruction) { 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 @@ void InductionVarRange::Replace(HInstruction* instruction, } } -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 @@ bool InductionVarRange::IsUnitStride(HInstruction* context, 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 @@ HInstruction* InductionVarRange::GenerateTripCount(HLoopInformation* loop, // 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 @@ bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info, } // 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::IsConstant(HInductionVarAnalysis::InductionInfo* info, } 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 @@ bool InductionVarRange::HasInductionInfo( 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 @@ bool InductionVarRange::IsWellBehavedTripCount(HInductionVarAnalysis::InductionI 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 @@ bool InductionVarRange::HasFetchInLoop(HInductionVarAnalysis::InductionInfo* inf 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 @@ bool InductionVarRange::IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* 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 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind 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 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind 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 @@ InductionVarRange::Value InductionVarRange::GetLinear(HInductionVarAnalysis::Ind 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 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, // 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 @@ InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction, 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 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct // 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 @@ InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::Induct } 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 @@ InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::Induct 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::GetDiv(HInductionVarAnalysis::Induct } 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::GetRem( } 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::GetXor( } 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 @@ InductionVarRange::Value InductionVarRange::MergeVal(Value v1, Value v2, bool is 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 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, /*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 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, // 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 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, } 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 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, // 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 @@ bool InductionVarRange::GenerateRangeOrLastValue(HInstruction* context, 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 @@ bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::Induc 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 @@ bool InductionVarRange::GenerateLastValuePolynomial(HInductionVarAnalysis::Induc 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 @@ bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::Induct // 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 @@ bool InductionVarRange::GenerateLastValueGeometric(HInductionVarAnalysis::Induct 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 @@ bool InductionVarRange::GenerateLastValueWrapAround(HInductionVarAnalysis::Induc // 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 @@ bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::Inducti } // 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 @@ bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::Inducti 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 @@ bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::Inducti // 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 @@ bool InductionVarRange::GenerateLastValuePeriodic(HInductionVarAnalysis::Inducti 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 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, 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 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, } 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 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, 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 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, *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 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, // 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 @@ bool InductionVarRange::GenerateCode(HInductionVarAnalysis::InductionInfo* info, 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 906dc6bb7b..552837c044 100644 --- a/compiler/optimizing/induction_var_range.h +++ b/compiler/optimizing/induction_var_range.h @@ -58,13 +58,13 @@ class InductionVarRange { 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 @@ class InductionVarRange { * 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 @@ class InductionVarRange { * * Precondition: CanGenerateRange() returns true. */ - void GenerateRange(HInstruction* context, + void GenerateRange(const HBasicBlock* context, HInstruction* instruction, HGraph* graph, HBasicBlock* block, @@ -105,12 +105,12 @@ class InductionVarRange { /*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 @@ class InductionVarRange { /** * 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 @@ class InductionVarRange { * 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 @@ class InductionVarRange { * 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 @@ class InductionVarRange { * 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 @@ class InductionVarRange { * 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 @@ class InductionVarRange { * 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 @@ class InductionVarRange { * 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 @@ class InductionVarRange { /*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 f6af384af0..962123d948 100644 --- a/compiler/optimizing/induction_var_range_test.cc +++ b/compiler/optimizing/induction_var_range_test.cc @@ -145,7 +145,10 @@ class InductionVarRangeTest : public OptimizingUnitTest { 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 @@ class InductionVarRangeTest : public OptimizingUnitTest { // 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 @@ class InductionVarRangeTest : public OptimizingUnitTest { 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, GetMinMaxFetch) { } 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, GetMinMaxWrapAround) { } 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 @@ TEST_F(InductionVarRangeTest, ConstantTripCountUp) { 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 @@ TEST_F(InductionVarRangeTest, ConstantTripCountUp) { 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 @@ TEST_F(InductionVarRangeTest, ConstantTripCountDown) { 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 @@ TEST_F(InductionVarRangeTest, ConstantTripCountDown) { 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { // 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { // 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 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { 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 9e298a5418..77dfe68bf6 100644 --- a/compiler/optimizing/loop_optimization.cc +++ b/compiler/optimizing/loop_optimization.cc @@ -1331,7 +1331,7 @@ bool HLoopOptimization::VectorizeDef(LoopNode* node, } 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 @@ bool HLoopOptimization::VectorizeUse(LoopNode* node, 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 0018a5b970..d35ed1c543 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -1110,10 +1110,10 @@ bool HLoopInformation::HasExitEdge() const { 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 42f03a0bc7..7a0059f616 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -1417,7 +1417,7 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> { 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 c5bad79f71..c258f0f8a8 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", |