diff options
Diffstat (limited to 'compiler/optimizing/induction_var_analysis.cc')
| -rw-r--r-- | compiler/optimizing/induction_var_analysis.cc | 312 |
1 files changed, 182 insertions, 130 deletions
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) { |