/* * Copyright (C) 2015 The Android Open Source Project * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #include "induction_var_analysis.h" #include "base/scoped_arena_containers.h" #include "induction_var_range.h" namespace art HIDDEN { /** * Returns true if the from/to types denote a narrowing, integral conversion (precision loss). */ static bool IsNarrowingIntegralConversion(DataType::Type from, DataType::Type to) { switch (from) { case DataType::Type::kInt64: return to == DataType::Type::kUint8 || to == DataType::Type::kInt8 || to == DataType::Type::kUint16 || to == DataType::Type::kInt16 || to == DataType::Type::kInt32; case DataType::Type::kInt32: return to == DataType::Type::kUint8 || to == DataType::Type::kInt8 || to == DataType::Type::kUint16 || to == DataType::Type::kInt16; case DataType::Type::kUint16: case DataType::Type::kInt16: return to == DataType::Type::kUint8 || to == DataType::Type::kInt8; default: return false; } } /** * Returns result of implicit widening type conversion done in HIR. */ static DataType::Type ImplicitConversion(DataType::Type type) { switch (type) { case DataType::Type::kBool: case DataType::Type::kUint8: case DataType::Type::kInt8: case DataType::Type::kUint16: case DataType::Type::kInt16: return DataType::Type::kInt32; default: return type; } } /** * Returns true if loop is guarded by "a cmp b" on entry. */ static bool IsGuardedBy(const HLoopInformation* loop, IfCondition cmp, HInstruction* a, HInstruction* b) { // Chase back through straightline code to the first potential // block that has a control dependence. // guard: if (x) bypass // | // entry: straightline code // | // preheader // | // header HBasicBlock* guard = loop->GetPreHeader(); HBasicBlock* entry = loop->GetHeader(); while (guard->GetPredecessors().size() == 1 && guard->GetSuccessors().size() == 1) { entry = guard; guard = guard->GetSinglePredecessor(); } // Find guard. HInstruction* control = guard->GetLastInstruction(); if (!control->IsIf()) { return false; } HIf* ifs = control->AsIf(); HInstruction* if_expr = ifs->InputAt(0); if (if_expr->IsCondition()) { IfCondition other_cmp = ifs->IfTrueSuccessor() == entry ? if_expr->AsCondition()->GetCondition() : if_expr->AsCondition()->GetOppositeCondition(); if (if_expr->InputAt(0) == a && if_expr->InputAt(1) == b) { return cmp == other_cmp; } else if (if_expr->InputAt(1) == a && if_expr->InputAt(0) == b) { switch (cmp) { case kCondLT: return other_cmp == kCondGT; case kCondLE: return other_cmp == kCondGE; case kCondGT: return other_cmp == kCondLT; case kCondGE: return other_cmp == kCondLE; default: LOG(FATAL) << "unexpected cmp: " << cmp; } } } return false; } /* Finds first loop header phi use. */ HInstruction* FindFirstLoopHeaderPhiUse(const HLoopInformation* loop, HInstruction* instruction) { for (const HUseListNode& use : instruction->GetUses()) { if (use.GetUser()->GetBlock() == loop->GetHeader() && use.GetUser()->IsPhi() && use.GetUser()->InputAt(1) == instruction) { return use.GetUser(); } } return nullptr; } /** * Relinks the Phi structure after break-loop rewriting. */ static bool FixOutsideUse(const HLoopInformation* loop, HInstruction* instruction, HInstruction* replacement, bool rewrite) { // Deal with regular uses. const HUseList& uses = instruction->GetUses(); for (auto it = uses.begin(), end = uses.end(); it != end; ) { HInstruction* user = it->GetUser(); size_t index = it->GetIndex(); ++it; // increment prior to potential removal if (user->GetBlock()->GetLoopInformation() != loop) { if (replacement == nullptr) { return false; } else if (rewrite) { user->ReplaceInput(replacement, index); } } } // Deal with environment uses. const HUseList& env_uses = instruction->GetEnvUses(); for (auto it = env_uses.begin(), end = env_uses.end(); it != end;) { HEnvironment* user = it->GetUser(); size_t index = it->GetIndex(); ++it; // increment prior to potential removal if (user->GetHolder()->GetBlock()->GetLoopInformation() != loop) { if (replacement == nullptr) { return false; } else if (rewrite) { user->ReplaceInput(replacement, index); } } } return true; } /** * Test and rewrite the loop body of a break-loop. Returns true on success. */ static bool RewriteBreakLoopBody(const HLoopInformation* loop, HBasicBlock* body, HInstruction* cond, HInstruction* index, HInstruction* upper, bool rewrite) { // Deal with Phis. Outside use prohibited, except for index (which gets exit value). for (HInstructionIterator it(loop->GetHeader()->GetPhis()); !it.Done(); it.Advance()) { HInstruction* exit_value = it.Current() == index ? upper : nullptr; if (!FixOutsideUse(loop, it.Current(), exit_value, rewrite)) { return false; } } // Deal with other statements in header. for (HInstruction* m = cond->GetPrevious(); m && !m->IsSuspendCheck();) { HInstruction* p = m->GetPrevious(); if (rewrite) { m->MoveBefore(body->GetFirstInstruction(), false); } if (!FixOutsideUse(loop, m, FindFirstLoopHeaderPhiUse(loop, m), rewrite)) { return false; } m = p; } return true; } // // Class members. // struct HInductionVarAnalysis::NodeInfo { explicit NodeInfo(uint32_t d) : depth(d), done(false) {} uint32_t depth; bool done; }; struct HInductionVarAnalysis::StackEntry { StackEntry(HInstruction* insn, NodeInfo* info, size_t link = std::numeric_limits::max()) : instruction(insn), node_info(info), user_link(link), num_visited_inputs(0u), low_depth(info->depth) {} HInstruction* instruction; NodeInfo* node_info; size_t user_link; // Stack index of the user that is visiting this input. size_t num_visited_inputs; size_t low_depth; }; HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph, OptimizingCompilerStats* stats, const char* name) : HOptimization(graph, name, stats), induction_(std::less(), graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)), cycles_(std::less(), graph->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)) { } bool HInductionVarAnalysis::Run() { // Detects sequence variables (generalized induction variables) during an outer to inner // traversal of all loops using Gerlek's algorithm. The order is important to enable // range analysis on outer loop while visiting inner loops. if (IsPathologicalCase()) { MaybeRecordStat(stats_, MethodCompilationStat::kNotVarAnalyzedPathological); return false; } for (HBasicBlock* graph_block : graph_->GetReversePostOrder()) { // Don't analyze irreducible loops. if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) { VisitLoop(graph_block->GetLoopInformation()); } } return !induction_.empty(); } void HInductionVarAnalysis::VisitLoop(const HLoopInformation* loop) { ScopedArenaAllocator local_allocator(graph_->GetArenaStack()); ScopedArenaSafeMap visited_instructions( std::less(), local_allocator.Adapter(kArenaAllocInductionVarAnalysis)); // Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's // algorithm. Due to the descendant-first nature, classification happens "on-demand". size_t global_depth = 0; for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) { HBasicBlock* loop_block = it_loop.Current(); DCHECK(loop_block->IsInLoop()); if (loop_block->GetLoopInformation() != loop) { continue; // Inner loops visited later. } // Visit phi-operations and instructions. for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) { global_depth = TryVisitNodes(loop, it.Current(), global_depth, &visited_instructions); } for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) { global_depth = TryVisitNodes(loop, it.Current(), global_depth, &visited_instructions); } } // Determine the loop's trip-count. VisitControl(loop); } size_t HInductionVarAnalysis::TryVisitNodes( const HLoopInformation* loop, HInstruction* start_instruction, size_t global_depth, /*inout*/ ScopedArenaSafeMap* visited_instructions) { // This is recursion-free version of the SCC search algorithm. We have limited stack space, // so recursion with the depth dependent on the input is undesirable as such depth is unlimited. auto [it, inserted] = visited_instructions->insert(std::make_pair(start_instruction, NodeInfo(global_depth + 1u))); if (!inserted) { return global_depth; } NodeInfo* start_info = &it->second; ++global_depth; DCHECK_EQ(global_depth, start_info->depth); ScopedArenaVector stack(visited_instructions->get_allocator()); stack.push_back({start_instruction, start_info}); size_t current_entry = 0u; while (!stack.empty()) { StackEntry& entry = stack[current_entry]; // Look for unvisited inputs (also known as "descentants"). bool visit_input = false; auto inputs = entry.instruction->GetInputs(); while (entry.num_visited_inputs != inputs.size()) { HInstruction* input = inputs[entry.num_visited_inputs]; ++entry.num_visited_inputs; // If the definition is either outside the loop (loop invariant entry value) // or assigned in inner loop (inner exit value), the input is not visited. if (input->GetBlock()->GetLoopInformation() != loop) { continue; } // Try visiting the input. If already visited, update `entry.low_depth`. auto [input_it, input_inserted] = visited_instructions->insert(std::make_pair(input, NodeInfo(global_depth + 1u))); NodeInfo* input_info = &input_it->second; if (input_inserted) { // Push the input on the `stack` and visit it now. ++global_depth; DCHECK_EQ(global_depth, input_info->depth); stack.push_back({input, input_info, current_entry}); current_entry = stack.size() - 1u; visit_input = true; break; } else if (!input_info->done && input_info->depth < entry.low_depth) { entry.low_depth = input_it->second.depth; } continue; } if (visit_input) { continue; // Process the new top of the stack. } // All inputs of the current node have been visited. // Check if we have found an input below this entry on the stack. DCHECK(!entry.node_info->done); size_t previous_entry = entry.user_link; if (entry.node_info->depth > entry.low_depth) { DCHECK_LT(previous_entry, current_entry) << entry.node_info->depth << " " << entry.low_depth; entry.node_info->depth = entry.low_depth; if (stack[previous_entry].low_depth > entry.low_depth) { stack[previous_entry].low_depth = entry.low_depth; } } else { // Classify the SCC we have just found. ArrayRef stack_tail = ArrayRef(stack).SubArray(current_entry); for (StackEntry& tail_entry : stack_tail) { tail_entry.node_info->done = true; } if (current_entry + 1u == stack.size() && !entry.instruction->IsLoopHeaderPhi()) { ClassifyTrivial(loop, entry.instruction); } else { ClassifyNonTrivial(loop, ArrayRef(stack_tail)); } stack.erase(stack.begin() + current_entry, stack.end()); } current_entry = previous_entry; } return global_depth; } /** * Since graph traversal may enter a SCC at any position, an initial representation may be rotated, * along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming * a chain of dependences (mutual independent items may occur in arbitrary order). For proper * classification, the lexicographically first loop-phi is rotated to the front. We do that * as we extract the SCC instructions. */ void HInductionVarAnalysis::ExtractScc(ArrayRef stack_tail, ScopedArenaVector* scc) { // Find very first loop-phi. HInstruction* phi = nullptr; size_t split_pos = 0; const size_t size = stack_tail.size(); for (size_t i = 0; i != size; ++i) { const StackEntry& entry = stack_tail[i]; HInstruction* instruction = entry.instruction; if (instruction->IsLoopHeaderPhi()) { // All loop Phis in SCC come from the same loop header. HBasicBlock* block = instruction->GetBlock(); DCHECK(block->GetLoopInformation()->GetHeader() == block); DCHECK(phi == nullptr || phi->GetBlock() == block); if (phi == nullptr || block->GetPhis().FoundBefore(instruction, phi)) { phi = instruction; split_pos = i + 1u; } } } // Extract SCC in two chunks. DCHECK(scc->empty()); scc->reserve(size); for (const StackEntry& entry : ReverseRange(stack_tail.SubArray(/*pos=*/ 0u, split_pos))) { scc->push_back(entry.instruction); } for (const StackEntry& entry : ReverseRange(stack_tail.SubArray(/*pos=*/ split_pos))) { scc->push_back(entry.instruction); } DCHECK_EQ(scc->size(), stack_tail.size()); } 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(context, loop, LookupInfo(loop, instruction->InputAt(0)), LookupInfo(loop, instruction->InputAt(1)), kAdd, type); } else if (instruction->IsSub()) { info = TransferAddSub(context, loop, LookupInfo(loop, instruction->InputAt(0)), LookupInfo(loop, instruction->InputAt(1)), kSub, type); } else if (instruction->IsNeg()) { info = TransferNeg(context, loop, LookupInfo(loop, instruction->InputAt(0)), type); } else if (instruction->IsMul()) { 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(context, loop, LookupInfo(loop, instruction->InputAt(0)), LookupInfo(loop, mulc), type); } } else if (instruction->IsSelect()) { info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 1); } else if (instruction->IsTypeConversion()) { info = TransferConversion(LookupInfo(loop, instruction->InputAt(0)), instruction->AsTypeConversion()->GetInputType(), instruction->AsTypeConversion()->GetResultType()); } else if (instruction->IsBoundsCheck()) { info = LookupInfo(loop, instruction->InputAt(0)); // Pass-through. } // Successfully classified? if (info != nullptr) { AssignInfo(loop, instruction, info); } } void HInductionVarAnalysis::ClassifyNonTrivial(const HLoopInformation* loop, ArrayRef stack_tail) { const size_t size = stack_tail.size(); DCHECK_GE(size, 1u); DataType::Type type = stack_tail.back().instruction->GetType(); ScopedArenaAllocator local_allocator(graph_->GetArenaStack()); ScopedArenaVector scc(local_allocator.Adapter(kArenaAllocInductionVarAnalysis)); ExtractScc(ArrayRef(stack_tail), &scc); // Analyze from loop-phi onwards. HInstruction* phi = scc[0]; if (!phi->IsLoopHeaderPhi()) { return; } // External link should be loop invariant. InductionInfo* initial = LookupInfo(loop, phi->InputAt(0)); if (initial == nullptr || initial->induction_class != kInvariant) { return; } // Store interesting cycle in each loop phi. for (size_t i = 0; i < size; i++) { if (scc[i]->IsLoopHeaderPhi()) { AssignCycle(scc[i]->AsPhi(), ArrayRef(scc)); } } // Singleton is wrap-around induction if all internal links have the same meaning. if (size == 1) { InductionInfo* update = TransferPhi(loop, phi, /*input_index*/ 1, /*adjust_input_size*/ 0); if (update != nullptr) { AssignInfo(loop, phi, CreateInduction(kWrapAround, kNop, initial, update, /*fetch*/ nullptr, type)); } return; } // Inspect remainder of the cycle that resides in `scc`. The `cycle` mapping assigns // temporary meaning to its nodes, seeded from the phi instruction and back. ScopedArenaSafeMap cycle( std::less(), local_allocator.Adapter(kArenaAllocInductionVarAnalysis)); for (size_t i = 1; i < size; i++) { HInstruction* instruction = scc[i]; InductionInfo* update = nullptr; if (instruction->IsPhi()) { update = SolvePhiAllInputs(loop, phi, instruction, cycle, type); } else if (instruction->IsAdd()) { update = SolveAddSub(loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, cycle, type); } else if (instruction->IsSub()) { update = SolveAddSub(loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, cycle, type); } else if (instruction->IsMul()) { update = SolveOp( loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kMul, type); } else if (instruction->IsDiv()) { update = SolveOp( loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kDiv, type); } else if (instruction->IsRem()) { update = SolveOp( loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kRem, type); } else if (instruction->IsShl()) { HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr); if (mulc != nullptr) { update = SolveOp(loop, phi, instruction, instruction->InputAt(0), mulc, kMul, type); } } else if (instruction->IsShr() || instruction->IsUShr()) { HInstruction* divc = GetShiftConstant(loop, instruction, initial); if (divc != nullptr) { update = SolveOp(loop, phi, instruction, instruction->InputAt(0), divc, kDiv, type); } } else if (instruction->IsXor()) { update = SolveOp( loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kXor, type); } else if (instruction->IsEqual()) { update = SolveTest(loop, phi, instruction, /*opposite_value=*/ 0, type); } else if (instruction->IsNotEqual()) { update = SolveTest(loop, phi, instruction, /*opposite_value=*/ 1, type); } else if (instruction->IsSelect()) { // Select acts like Phi. update = SolvePhi(instruction, /*input_index=*/ 0, /*adjust_input_size=*/ 1, cycle); } else if (instruction->IsTypeConversion()) { update = SolveConversion(loop, phi, instruction->AsTypeConversion(), cycle, &type); } if (update == nullptr) { return; } cycle.Put(instruction, update); } // Success if all internal links received the same temporary meaning. InductionInfo* induction = SolvePhi(phi, /*input_index=*/ 1, /*adjust_input_size=*/ 0, cycle); if (induction != nullptr) { switch (induction->induction_class) { case kInvariant: // Construct combined stride of the linear induction. induction = CreateInduction(kLinear, kNop, induction, initial, /*fetch*/ nullptr, type); FALLTHROUGH_INTENDED; case kPolynomial: case kGeometric: case kWrapAround: // Classify first phi and then the rest of the cycle "on-demand". // Statements are scanned in order. AssignInfo(loop, phi, induction); for (size_t i = 1; i < size; i++) { ClassifyTrivial(loop, scc[i]); } break; case kPeriodic: // Classify all elements in the cycle with the found periodic induction while // rotating each first element to the end. Lastly, phi is classified. // Statements are scanned in reverse order. for (size_t i = size - 1; i >= 1; i--) { AssignInfo(loop, scc[i], induction); induction = RotatePeriodicInduction(induction->op_b, induction->op_a, type); } AssignInfo(loop, phi, induction); break; default: break; } } } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction( InductionInfo* induction, InductionInfo* last, DataType::Type type) { // Rotates a periodic induction of the form // (a, b, c, d, e) // into // (b, c, d, e, a) // in preparation of assigning this to the previous variable in the sequence. if (induction->induction_class == kInvariant) { return CreateInduction(kPeriodic, kNop, induction, last, /*fetch*/ nullptr, type); } return CreateInduction(kPeriodic, kNop, induction->op_a, RotatePeriodicInduction(induction->op_b, last, type), /*fetch*/ nullptr, type); } 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()); InductionInfo* a = LookupInfo(loop, inputs[input_index]); for (size_t i = input_index + 1, n = inputs.size() - adjust_input_size; i < n; i++) { InductionInfo* b = LookupInfo(loop, inputs[i]); if (!InductionEqual(a, b)) { return nullptr; } } return a; } 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. if (a != nullptr && b != nullptr) { if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) { return nullptr; // no transfer } else if (a->induction_class == kInvariant && b->induction_class == kInvariant) { 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(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(context, loop, a, b->op_b, op, type); if (b->induction_class == kWrapAround || b->induction_class == kPeriodic) { new_a = TransferAddSub(context, loop, a, new_a, op, type); } else if (op == kSub) { // Negation required. 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); } } 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(context, loop, a->op_b, b, op, type); if (a->induction_class == kWrapAround || a->induction_class == kPeriodic) { 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); } } } return nullptr; } 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(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(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); } } } return nullptr; } 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. if (a != nullptr && b != nullptr) { if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) { return nullptr; // no transfer } else if (a->induction_class == kInvariant && b->induction_class == kInvariant) { 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(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(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); } } } return nullptr; } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferConversion( InductionInfo* a, DataType::Type from, DataType::Type to) { if (a != nullptr) { // Allow narrowing conversion on linear induction in certain cases: // induction is already at narrow type, or can be made narrower. if (IsNarrowingIntegralConversion(from, to) && a->induction_class == kLinear && (a->type == to || IsNarrowingIntegralConversion(a->type, to))) { return CreateInduction(kLinear, kNop, a->op_a, a->op_b, a->fetch, to); } } return nullptr; } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi( HInstruction* phi, size_t input_index, size_t adjust_input_size, const ScopedArenaSafeMap& cycle) { // Match all phi inputs from input_index onwards exactly. HInputsRef inputs = phi->GetInputs(); DCHECK_LT(input_index, inputs.size()); auto ita = cycle.find(inputs[input_index]); if (ita != cycle.end()) { for (size_t i = input_index + 1, n = inputs.size() - adjust_input_size; i < n; i++) { auto itb = cycle.find(inputs[i]); if (itb == cycle.end() || !HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) { return nullptr; } } return ita->second; } return nullptr; } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs( const HLoopInformation* loop, HInstruction* entry_phi, HInstruction* phi, const ScopedArenaSafeMap& cycle, DataType::Type type) { // Match all phi inputs. InductionInfo* match = SolvePhi(phi, /*input_index=*/ 0, /*adjust_input_size=*/ 0, cycle); if (match != nullptr) { return match; } // Otherwise, try to solve for a periodic seeded from phi onward. // Only tight multi-statement cycles are considered in order to // simplify rotating the periodic during the final classification. if (phi->IsLoopHeaderPhi() && phi->InputCount() == 2) { InductionInfo* a = LookupInfo(loop, phi->InputAt(0)); if (a != nullptr && a->induction_class == kInvariant) { if (phi->InputAt(1) == entry_phi) { InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); return CreateInduction(kPeriodic, kNop, a, initial, /*fetch*/ nullptr, type); } InductionInfo* b = SolvePhi(phi, /*input_index=*/ 1, /*adjust_input_size=*/ 0, cycle); if (b != nullptr && b->induction_class == kPeriodic) { return CreateInduction(kPeriodic, kNop, a, b, /*fetch*/ nullptr, type); } } } return nullptr; } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub( const HLoopInformation* loop, HInstruction* entry_phi, HInstruction* instruction, HInstruction* x, HInstruction* y, InductionOp op, const ScopedArenaSafeMap& 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); if (b != nullptr) { if (b->induction_class == kInvariant) { // 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(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(context, loop, op, a, b); } } } else if (b->induction_class == kLinear && b->type == type) { // Solve within a tight cycle that adds a term that is already classified as a linear // induction for a polynomial induction k = k + i (represented as sum over linear terms). if (x == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); 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); } } } } return nullptr; }; HInductionVarAnalysis::InductionInfo* result = main_solve_add_sub(); if (result == nullptr) { // Try some alternatives before failing. if (op == kAdd) { // Try the other way around for an addition. std::swap(x, y); result = main_solve_add_sub(); } else if (op == kSub) { // Solve within a tight cycle that is formed by exactly two instructions, // one phi and one update, for a periodic idiom of the form k = c - k. if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { InductionInfo* a = LookupInfo(loop, x); if (a != nullptr && a->induction_class == kInvariant) { InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); result = CreateInduction(kPeriodic, kNop, CreateInvariantOp(context, loop, kSub, a, initial), initial, /*fetch*/ nullptr, type); } } } } return result; } 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; InductionInfo* b = LookupInfo(loop, y); if (b != nullptr && b->induction_class == kInvariant && entry_phi == x) { c = b; } else if (op != kDiv && op != kRem) { InductionInfo* a = LookupInfo(loop, x); if (a != nullptr && a->induction_class == kInvariant && entry_phi == y) { c = a; } } // 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: case kDiv: // Restrict base of geometric induction to direct fetch. if (c->operation == kFetch) { return CreateInduction(kGeometric, op, initial, CreateConstant(0, type), c->fetch, type); } break; case kRem: // Idiomatic MOD wrap-around induction. return CreateInduction(kWrapAround, kNop, initial, CreateInvariantOp(context, loop, kRem, initial, c), /*fetch*/ nullptr, type); case kXor: // Idiomatic XOR periodic induction. return CreateInduction(kPeriodic, kNop, CreateInvariantOp(context, loop, kXor, initial, c), initial, /*fetch*/ nullptr, type); default: LOG(FATAL) << op; UNREACHABLE(); } } } return nullptr; } 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). const HBasicBlock* context = instruction->GetBlock(); HInstruction* x = instruction->InputAt(0); HInstruction* y = instruction->InputAt(1); 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(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( const HLoopInformation* loop, HInstruction* entry_phi, HTypeConversion* conversion, const ScopedArenaSafeMap& cycle, /*inout*/ DataType::Type* type) { DataType::Type from = conversion->GetInputType(); DataType::Type to = conversion->GetResultType(); // A narrowing conversion is allowed as *last* operation of the cycle of a linear induction // with an initial value that fits the type, provided that the narrowest encountered type is // recorded with the induction to account for the precision loss. The narrower induction does // *not* transfer to any wider operations, however, since these may yield out-of-type values if (entry_phi->InputCount() == 2 && conversion == entry_phi->InputAt(1)) { 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(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; return it->second; } } } return nullptr; } // // Loop trip count analysis methods. // void HInductionVarAnalysis::VisitControl(const HLoopInformation* loop) { HInstruction* control = loop->GetHeader()->GetLastInstruction(); if (control->IsIf()) { HIf* ifs = control->AsIf(); HBasicBlock* if_true = ifs->IfTrueSuccessor(); HBasicBlock* if_false = ifs->IfFalseSuccessor(); HInstruction* if_expr = ifs->InputAt(0); // Determine if loop has following structure in header. // loop-header: .... // 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()); // Determine if the loop control uses a known sequence on an if-exit (X outside) or on // an if-iterate (X inside), expressed as if-iterate when passed into VisitCondition(). if (a == nullptr || b == nullptr) { return; // Loop control is not a sequence. } else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) { VisitCondition(context, loop, if_false, a, b, type, condition->GetOppositeCondition()); } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) { VisitCondition(context, loop, if_true, a, b, type, condition->GetCondition()); } } } } void HInductionVarAnalysis::VisitCondition(const HBasicBlock* context, const HLoopInformation* loop, HBasicBlock* body, InductionInfo* a, InductionInfo* b, DataType::Type type, IfCondition cmp) { 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(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) { // Analyze condition with induction at left-hand-side (e.g. i < U). InductionInfo* lower_expr = a->op_b; InductionInfo* upper_expr = b; InductionInfo* stride_expr = a->op_a; // Test for constant stride and integral condition. int64_t stride_value = 0; if (!IsExact(context, loop, stride_expr, &stride_value)) { return; // unknown stride } else if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) { return; // not integral } // 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(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(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(context, loop, lower_expr, upper_expr, stride_value, a->type, cmp)) { return; // mismatched type } // Normalize a linear loop control with a nonzero stride: // stride > 0, either i < U or i <= U // stride < 0, either i > U or i >= U if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) || (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) { VisitTripCount(context, loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp); } } } void HInductionVarAnalysis::VisitTripCount(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* lower_expr, InductionInfo* upper_expr, InductionInfo* stride_expr, int64_t stride_value, DataType::Type type, IfCondition cmp) { // Any loop of the general form: // // for (i = L; i <= U; i += S) // S > 0 // or for (i = L; i >= U; i += S) // S < 0 // .. i .. // // can be normalized into: // // for (n = 0; n < TC; n++) // where TC = (U + S - L) / S // .. L + S * n .. // // taking the following into consideration: // // (1) Using the same precision, the TC (trip-count) expression should be interpreted as // an unsigned entity, for example, as in the following loop that uses the full range: // for (int i = INT_MIN; i < INT_MAX; i++) // TC = UINT_MAX // (2) The TC is only valid if the loop is taken, otherwise TC = 0, as in: // for (int i = 12; i < U; i++) // TC = 0 when U <= 12 // If this cannot be determined at compile-time, the TC is only valid within the // loop-body proper, not the loop-header unless enforced with an explicit taken-test. // (3) The TC is only valid if the loop is finite, otherwise TC has no value, as in: // for (int i = 0; i <= U; i++) // TC = Inf when U = INT_MAX // If this cannot be determined at compile-time, the TC is only valid when enforced // with an explicit finite-test. // (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(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(context, loop, kSub, trip_count, CreateConstant(1, type)); } else if (cmp == kCondGT) { trip_count = CreateInvariantOp(context, loop, kAdd, trip_count, CreateConstant(1, type)); } // Compensate for stride. trip_count = CreateInvariantOp(context, loop, kAdd, trip_count, 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 if (is_taken && is_finite) { tcKind = kTripCountInLoop; // needs neither test } else if (is_finite) { tcKind = kTripCountInBody; // needs taken-test } else if (is_taken) { tcKind = kTripCountInLoopUnsafe; // needs finite-test } InductionOp op = kNop; switch (cmp) { case kCondLT: op = kLT; break; case kCondLE: op = kLE; break; case kCondGT: op = kGT; break; case kCondGE: op = kGE; break; default: LOG(FATAL) << "CONDITION UNREACHABLE"; } // 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(context, loop, op, lower_expr, upper_expr); DCHECK(control->IsIf()); AssignInfo(loop, control, CreateTripCount(tcKind, trip_count, taken_test, type)); } 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(context, loop, lower_expr, &lower_value) && IsAtLeast(context, loop, upper_expr, &upper_value) && lower_value < upper_value; case kCondLE: return IsAtMost(context, loop, lower_expr, &lower_value) && IsAtLeast(context, loop, upper_expr, &upper_value) && lower_value <= upper_value; case kCondGT: return IsAtLeast(context, loop, lower_expr, &lower_value) && IsAtMost(context, loop, upper_expr, &upper_value) && lower_value > upper_value; case kCondGE: return IsAtLeast(context, loop, lower_expr, &lower_value) && IsAtMost(context, loop, upper_expr, &upper_value) && lower_value >= upper_value; default: LOG(FATAL) << "CONDITION UNREACHABLE"; UNREACHABLE(); } } bool HInductionVarAnalysis::IsFinite(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* upper_expr, int64_t stride_value, DataType::Type type, IfCondition cmp) { int64_t min = DataType::MinValueOfIntegralType(type); int64_t max = DataType::MaxValueOfIntegralType(type); // Some rules under which it is certain at compile-time that the loop is finite. int64_t value; switch (cmp) { case kCondLT: return stride_value == 1 || (IsAtMost(context, loop, upper_expr, &value) && value <= (max - stride_value + 1)); case kCondLE: return (IsAtMost(context, loop, upper_expr, &value) && value <= (max - stride_value)); case kCondGT: return stride_value == -1 || (IsAtLeast(context, loop, upper_expr, &value) && value >= (min - stride_value - 1)); case kCondGE: return (IsAtLeast(context, loop, upper_expr, &value) && value >= (min - stride_value)); default: LOG(FATAL) << "CONDITION UNREACHABLE"; UNREACHABLE(); } } bool HInductionVarAnalysis::FitsNarrowerControl(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* lower_expr, InductionInfo* upper_expr, int64_t stride_value, DataType::Type type, IfCondition cmp) { int64_t min = DataType::MinValueOfIntegralType(type); int64_t max = DataType::MaxValueOfIntegralType(type); // Inclusive test need one extra. if (stride_value != 1 && stride_value != -1) { return false; // non-unit stride } else if (cmp == kCondLE) { max--; } else if (cmp == kCondGE) { min++; } // Do both bounds fit the range? int64_t value = 0; 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(const HBasicBlock* context, const HLoopInformation* loop, HBasicBlock* body, int64_t stride_value, DataType::Type type) { // Only accept unit stride. if (std::abs(stride_value) != 1) { return false; } // Simple terminating i != U condition, used nowhere else. HIf* ifs = loop->GetHeader()->GetLastInstruction()->AsIf(); HInstruction* cond = ifs->InputAt(0); if (ifs->GetPrevious() != cond || !cond->HasOnlyOneNonEnvironmentUse()) { return false; } int c = LookupInfo(loop, cond->InputAt(0))->induction_class == kLinear ? 0 : 1; HInstruction* index = cond->InputAt(c); HInstruction* upper = cond->InputAt(1 - c); // Safe to rewrite into i <= U? IfCondition cmp = stride_value > 0 ? kCondLE : kCondGE; 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. if (body->GetSuccessors().size() != 1 || body->GetSingleSuccessor() != loop->GetHeader() || !body->GetPhis().IsEmpty() || body->GetInstructions().IsEmpty() || body->GetFirstInstruction() != index->InputAt(1) || !body->GetFirstInstruction()->HasOnlyOneNonEnvironmentUse() || !body->GetFirstInstruction()->GetNext()->IsGoto()) { return false; } // Always taken or guarded by enclosing condition. if (!IsTaken(context, loop, LookupInfo(loop, index)->op_b, LookupInfo(loop, upper), cmp) && !IsGuardedBy(loop, cmp, index->InputAt(0), upper)) { return false; } // Test if break-loop body can be written, and do so on success. if (RewriteBreakLoopBody(loop, body, cond, index, upper, /*rewrite*/ false)) { RewriteBreakLoopBody(loop, body, cond, index, upper, /*rewrite*/ true); } else { return false; } // Rewrite condition in HIR. if (ifs->IfTrueSuccessor() != body) { cmp = (cmp == kCondLE) ? kCondGT : kCondLT; } HInstruction* rep = nullptr; switch (cmp) { case kCondLT: rep = new (graph_->GetAllocator()) HLessThan(index, upper); break; case kCondGT: rep = new (graph_->GetAllocator()) HGreaterThan(index, upper); break; case kCondLE: rep = new (graph_->GetAllocator()) HLessThanOrEqual(index, upper); break; case kCondGE: rep = new (graph_->GetAllocator()) HGreaterThanOrEqual(index, upper); break; default: LOG(FATAL) << cmp; UNREACHABLE(); } loop->GetHeader()->ReplaceAndRemoveInstructionWith(cond, rep); return true; } // // Helper methods. // void HInductionVarAnalysis::AssignInfo(const HLoopInformation* loop, HInstruction* instruction, InductionInfo* info) { auto it = induction_.find(loop); if (it == induction_.end()) { it = induction_.Put(loop, ArenaSafeMap( std::less(), graph_->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis))); } it->second.Put(instruction, info); } 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); if (loop_it != it->second.end()) { return loop_it->second; } } if (loop->IsDefinedOutOfTheLoop(instruction)) { InductionInfo* info = CreateInvariantFetch(instruction); AssignInfo(loop, instruction, info); return info; } return nullptr; } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateConstant(int64_t value, DataType::Type type) { HInstruction* constant; switch (type) { case DataType::Type::kFloat64: constant = graph_->GetDoubleConstant(value); break; case DataType::Type::kFloat32: constant = graph_->GetFloatConstant(value); break; case DataType::Type::kInt64: constant = graph_->GetLongConstant(value); break; default: constant = graph_->GetIntConstant(value); break; } return CreateInvariantFetch(constant); } HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant( const HBasicBlock* context, const HLoopInformation* loop, InductionOp op, InductionInfo* a, InductionInfo* b) { // Perform some light-weight simplifications during construction of a new invariant. // This often safes memory and yields a more concise representation of the induction. // 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(context, loop, a, &value)) { if (value == 0) { // Simplify 0 + b = b, 0 ^ b = b, 0 * b = 0. if (op == kAdd || op == kXor) { return b; } else if (op == kMul) { return a; } } else if (op == kMul) { // Simplify 1 * b = b, -1 * b = -b if (value == 1) { return b; } else if (value == -1) { return CreateSimplifiedInvariant(context, loop, kNeg, nullptr, b); } } } 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) { return a; } else if (op == kMul || op == kNeg) { return b; } } else if (op == kMul || op == kDiv) { // Simplify a * 1 = a, a / 1 = a, a * -1 = -a, a / -1 = -a if (value == 1) { return a; } else if (value == -1) { 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(context, loop, kSub, a, b->op_b); } else if (op == kSub) { 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(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(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(context, loop, initial, &value) || value < 0) { return nullptr; } } // Obtain the constant needed to treat shift as equivalent multiplication or division. // This yields an existing instruction if the constant is already there. Otherwise, this // has a side effect on the HIR. The restriction on the shift factor avoids generating a // negative constant (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that // 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(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); } if (type == DataType::Type::kInt64 && 0 <= value && value < 63) { return graph_->GetLongConstant(1L << value); } } return nullptr; } void HInductionVarAnalysis::AssignCycle(HPhi* phi, ArrayRef scc) { ArenaSet* set = &cycles_.Put(phi, ArenaSet( graph_->GetAllocator()->Adapter(kArenaAllocInductionVarAnalysis)))->second; for (HInstruction* i : scc) { set->insert(i); } } ArenaSet* HInductionVarAnalysis::LookupCycle(HPhi* phi) { auto it = cycles_.find(phi); if (it != cycles_.end()) { return &it->second; } return nullptr; } 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(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(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) { return info != nullptr && info->induction_class == kLinear && (info->type == DataType::Type::kUint8 || info->type == DataType::Type::kInt8 || info->type == DataType::Type::kUint16 || info->type == DataType::Type::kInt16 || (info->type == DataType::Type::kInt32 && (info->op_a->type == DataType::Type::kInt64 || info->op_b->type == DataType::Type::kInt64))); } bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1, InductionInfo* info2) { // Test structural equality only, without accounting for simplifications. if (info1 != nullptr && info2 != nullptr) { return info1->induction_class == info2->induction_class && info1->operation == info2->operation && info1->fetch == info2->fetch && info1->type == info2->type && InductionEqual(info1->op_a, info2->op_a) && InductionEqual(info1->op_b, info2->op_b); } // Otherwise only two nullptrs are considered equal. return info1 == info2; } std::string HInductionVarAnalysis::FetchToString(HInstruction* fetch) { DCHECK(fetch != nullptr); if (fetch->IsIntConstant()) { return std::to_string(fetch->AsIntConstant()->GetValue()); } else if (fetch->IsLongConstant()) { return std::to_string(fetch->AsLongConstant()->GetValue()); } return std::to_string(fetch->GetId()) + ":" + fetch->DebugName(); } std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { if (info != nullptr) { if (info->induction_class == kInvariant) { std::string inv = "("; inv += InductionToString(info->op_a); switch (info->operation) { case kNop: inv += " @ "; break; case kAdd: inv += " + "; break; case kSub: case kNeg: inv += " - "; break; case kMul: inv += " * "; break; case kDiv: inv += " / "; break; case kRem: inv += " % "; break; case kXor: inv += " ^ "; break; case kLT: inv += " < "; break; case kLE: inv += " <= "; break; case kGT: inv += " > "; break; case kGE: inv += " >= "; break; case kFetch: inv += FetchToString(info->fetch); break; case kTripCountInLoop: inv += " (TC-loop) "; break; case kTripCountInBody: inv += " (TC-body) "; break; case kTripCountInLoopUnsafe: inv += " (TC-loop-unsafe) "; break; case kTripCountInBodyUnsafe: inv += " (TC-body-unsafe) "; break; } inv += InductionToString(info->op_b); inv += ")"; return inv; } else { if (info->induction_class == kLinear) { DCHECK(info->operation == kNop); return "(" + InductionToString(info->op_a) + " * i + " + InductionToString(info->op_b) + "):" + DataType::PrettyDescriptor(info->type); } else if (info->induction_class == kPolynomial) { DCHECK(info->operation == kNop); return "poly(sum_lt(" + InductionToString(info->op_a) + ") + " + InductionToString(info->op_b) + "):" + DataType::PrettyDescriptor(info->type); } else if (info->induction_class == kGeometric) { DCHECK(info->operation == kMul || info->operation == kDiv); DCHECK(info->fetch != nullptr); return "geo(" + InductionToString(info->op_a) + " * " + FetchToString(info->fetch) + (info->operation == kMul ? " ^ i + " : " ^ -i + ") + InductionToString(info->op_b) + "):" + DataType::PrettyDescriptor(info->type); } else if (info->induction_class == kWrapAround) { DCHECK(info->operation == kNop); return "wrap(" + InductionToString(info->op_a) + ", " + InductionToString(info->op_b) + "):" + DataType::PrettyDescriptor(info->type); } else if (info->induction_class == kPeriodic) { DCHECK(info->operation == kNop); return "periodic(" + InductionToString(info->op_a) + ", " + InductionToString(info->op_b) + "):" + DataType::PrettyDescriptor(info->type); } } } return ""; } void HInductionVarAnalysis::CalculateLoopHeaderPhisInARow( HPhi* initial_phi, ScopedArenaSafeMap& cached_values, ScopedArenaAllocator& allocator) { DCHECK(initial_phi->IsLoopHeaderPhi()); ScopedArenaQueue worklist(allocator.Adapter(kArenaAllocInductionVarAnalysis)); worklist.push(initial_phi); // Used to check which phis are in the current chain we are checking. ScopedArenaSet phis_in_chain(allocator.Adapter(kArenaAllocInductionVarAnalysis)); while (!worklist.empty()) { HPhi* current_phi = worklist.front(); DCHECK(current_phi->IsLoopHeaderPhi()); if (cached_values.find(current_phi) != cached_values.end()) { // Already processed. worklist.pop(); continue; } phis_in_chain.insert(current_phi); int max_value = 0; bool pushed_other_phis = false; for (size_t index = 0; index < current_phi->InputCount(); index++) { // If the input is not a loop header phi, we only have 1 (current_phi). int current_value = 1; if (current_phi->InputAt(index)->IsLoopHeaderPhi()) { HPhi* loop_header_phi = current_phi->InputAt(index)->AsPhi(); auto it = cached_values.find(loop_header_phi); if (it != cached_values.end()) { current_value += it->second; } else if (phis_in_chain.find(current_phi) == phis_in_chain.end()) { // Push phis which aren't in the chain already to be processed. pushed_other_phis = true; worklist.push(loop_header_phi); } // Phis in the chain will get processed later. We keep `current_value` as 1 to avoid // double counting `loop_header_phi`. } max_value = std::max(max_value, current_value); } if (!pushed_other_phis) { // Only finish processing after all inputs were processed. worklist.pop(); phis_in_chain.erase(current_phi); cached_values.FindOrAdd(current_phi, max_value); } } } bool HInductionVarAnalysis::IsPathologicalCase() { ScopedArenaAllocator local_allocator(graph_->GetArenaStack()); ScopedArenaSafeMap cached_values( std::less(), local_allocator.Adapter(kArenaAllocInductionVarAnalysis)); // Due to how our induction passes work, we will take a lot of time compiling if we have several // loop header phis in a row. If we have more than 15 different loop header phis in a row, we // don't perform the analysis. constexpr int kMaximumLoopHeaderPhisInARow = 15; for (HBasicBlock* block : graph_->GetReversePostOrder()) { if (!block->IsLoopHeader()) { continue; } for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { DCHECK(it.Current()->IsLoopHeaderPhi()); HPhi* phi = it.Current()->AsPhi(); CalculateLoopHeaderPhisInARow(phi, cached_values, local_allocator); DCHECK(cached_values.find(phi) != cached_values.end()) << " we should have a value for Phi " << phi->GetId() << " in block " << phi->GetBlock()->GetBlockId(); if (cached_values.find(phi)->second > kMaximumLoopHeaderPhisInARow) { return true; } } } return false; } } // namespace art