| /* |
| * 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 "induction_var_range.h" |
| |
| namespace art { |
| |
| /** |
| * 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. |
| */ |
| static void RotateEntryPhiFirst(HLoopInformation* loop, |
| ArenaVector<HInstruction*>* scc, |
| ArenaVector<HInstruction*>* new_scc) { |
| // Find very first loop-phi. |
| const HInstructionList& phis = loop->GetHeader()->GetPhis(); |
| HInstruction* phi = nullptr; |
| size_t phi_pos = -1; |
| const size_t size = scc->size(); |
| for (size_t i = 0; i < size; i++) { |
| HInstruction* other = (*scc)[i]; |
| if (other->IsLoopHeaderPhi() && (phi == nullptr || phis.FoundBefore(other, phi))) { |
| phi = other; |
| phi_pos = i; |
| } |
| } |
| |
| // If found, bring that loop-phi to front. |
| if (phi != nullptr) { |
| new_scc->clear(); |
| for (size_t i = 0; i < size; i++) { |
| new_scc->push_back((*scc)[phi_pos]); |
| if (++phi_pos >= size) phi_pos = 0; |
| } |
| DCHECK_EQ(size, new_scc->size()); |
| scc->swap(*new_scc); |
| } |
| } |
| |
| /** |
| * 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::kInt8 || to == DataType::Type::kInt16 |
| || to == DataType::Type::kUint16 || to == DataType::Type::kInt32; |
| case DataType::Type::kInt32: |
| return to == DataType::Type::kInt8 || to == DataType::Type::kInt16 |
| || to == DataType::Type::kUint16; |
| case DataType::Type::kUint16: |
| case DataType::Type::kInt16: |
| return 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::kInt16: |
| case DataType::Type::kUint16: |
| case DataType::Type::kInt8: |
| case DataType::Type::kBool: |
| return DataType::Type::kInt32; |
| default: |
| return type; |
| } |
| } |
| |
| // |
| // Class methods. |
| // |
| |
| HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph) |
| : HOptimization(graph, kInductionPassName), |
| global_depth_(0), |
| stack_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
| map_(std::less<HInstruction*>(), |
| graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
| scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
| cycle_(std::less<HInstruction*>(), |
| graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
| type_(DataType::Type::kVoid), |
| induction_(std::less<HLoopInformation*>(), |
| graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
| cycles_(std::less<HPhi*>(), |
| graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)) { |
| } |
| |
| void 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. |
| for (HBasicBlock* graph_block : graph_->GetReversePostOrder()) { |
| // Don't analyze irreducible loops. |
| if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) { |
| VisitLoop(graph_block->GetLoopInformation()); |
| } |
| } |
| } |
| |
| void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) { |
| // 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". |
| global_depth_ = 0; |
| DCHECK(stack_.empty()); |
| map_.clear(); |
| |
| 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()) { |
| HInstruction* instruction = it.Current(); |
| if (!IsVisitedNode(instruction)) { |
| VisitNode(loop, instruction); |
| } |
| } |
| for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) { |
| HInstruction* instruction = it.Current(); |
| if (!IsVisitedNode(instruction)) { |
| VisitNode(loop, instruction); |
| } |
| } |
| } |
| |
| DCHECK(stack_.empty()); |
| map_.clear(); |
| |
| // Determine the loop's trip-count. |
| VisitControl(loop); |
| } |
| |
| void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) { |
| const uint32_t d1 = ++global_depth_; |
| map_.Put(instruction, NodeInfo(d1)); |
| stack_.push_back(instruction); |
| |
| // Visit all descendants. |
| uint32_t low = d1; |
| for (HInstruction* input : instruction->GetInputs()) { |
| low = std::min(low, VisitDescendant(loop, input)); |
| } |
| |
| // Lower or found SCC? |
| if (low < d1) { |
| map_.find(instruction)->second.depth = low; |
| } else { |
| scc_.clear(); |
| cycle_.clear(); |
| |
| // Pop the stack to build the SCC for classification. |
| while (!stack_.empty()) { |
| HInstruction* x = stack_.back(); |
| scc_.push_back(x); |
| stack_.pop_back(); |
| map_.find(x)->second.done = true; |
| if (x == instruction) { |
| break; |
| } |
| } |
| |
| // Type of induction. |
| type_ = scc_[0]->GetType(); |
| |
| // Classify the SCC. |
| if (scc_.size() == 1 && !scc_[0]->IsLoopHeaderPhi()) { |
| ClassifyTrivial(loop, scc_[0]); |
| } else { |
| ClassifyNonTrivial(loop); |
| } |
| |
| scc_.clear(); |
| cycle_.clear(); |
| } |
| } |
| |
| uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) { |
| // If the definition is either outside the loop (loop invariant entry value) |
| // or assigned in inner loop (inner exit value), the traversal stops. |
| HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation(); |
| if (otherLoop != loop) { |
| return global_depth_; |
| } |
| |
| // Inspect descendant node. |
| if (!IsVisitedNode(instruction)) { |
| VisitNode(loop, instruction); |
| return map_.find(instruction)->second.depth; |
| } else { |
| auto it = map_.find(instruction); |
| return it->second.done ? global_depth_ : it->second.depth; |
| } |
| } |
| |
| void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) { |
| 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)), |
| LookupInfo(loop, instruction->InputAt(1)), kAdd); |
| } else if (instruction->IsSub()) { |
| info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)), |
| LookupInfo(loop, instruction->InputAt(1)), kSub); |
| } else if (instruction->IsNeg()) { |
| info = TransferNeg(LookupInfo(loop, instruction->InputAt(0))); |
| } else if (instruction->IsMul()) { |
| info = TransferMul(LookupInfo(loop, instruction->InputAt(0)), |
| LookupInfo(loop, instruction->InputAt(1))); |
| } else if (instruction->IsShl()) { |
| HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr); |
| if (mulc != nullptr) { |
| info = TransferMul(LookupInfo(loop, instruction->InputAt(0)), |
| LookupInfo(loop, mulc)); |
| } |
| } 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(HLoopInformation* loop) { |
| const size_t size = scc_.size(); |
| DCHECK_GE(size, 1u); |
| |
| // Rotate proper loop-phi to front. |
| if (size > 1) { |
| ArenaVector<HInstruction*> other(graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)); |
| RotateEntryPhiFirst(loop, &scc_, &other); |
| } |
| |
| // 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()); |
| } |
| } |
| |
| // 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. |
| for (size_t i = 1; i < size; i++) { |
| HInstruction* instruction = scc_[i]; |
| InductionInfo* update = nullptr; |
| if (instruction->IsPhi()) { |
| update = SolvePhiAllInputs(loop, phi, instruction); |
| } else if (instruction->IsAdd()) { |
| update = SolveAddSub( |
| loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true); |
| } else if (instruction->IsSub()) { |
| update = SolveAddSub( |
| loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true); |
| } else if (instruction->IsMul()) { |
| update = SolveOp( |
| loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kMul); |
| } else if (instruction->IsDiv()) { |
| update = SolveOp( |
| loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kDiv); |
| } else if (instruction->IsRem()) { |
| update = SolveOp( |
| loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kRem); |
| } else if (instruction->IsShl()) { |
| HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr); |
| if (mulc != nullptr) { |
| update = SolveOp(loop, phi, instruction, instruction->InputAt(0), mulc, kMul); |
| } |
| } 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); |
| } |
| } else if (instruction->IsXor()) { |
| update = SolveOp( |
| loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kXor); |
| } else if (instruction->IsEqual()) { |
| update = SolveTest(loop, phi, instruction, 0); |
| } else if (instruction->IsNotEqual()) { |
| update = SolveTest(loop, phi, instruction, 1); |
| } else if (instruction->IsSelect()) { |
| update = SolvePhi(instruction, /*input_index*/ 0, /*adjust_input_size*/ 1); // acts like Phi |
| } else if (instruction->IsTypeConversion()) { |
| update = SolveConversion(loop, phi, instruction->AsTypeConversion()); |
| } |
| 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); |
| 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); |
| } |
| AssignInfo(loop, phi, induction); |
| break; |
| default: |
| break; |
| } |
| } |
| } |
| |
| HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction( |
| InductionInfo* induction, |
| InductionInfo* last) { |
| // 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), |
| /*fetch*/ nullptr, |
| type_); |
| } |
| |
| HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(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(InductionInfo* a, |
| InductionInfo* b, |
| InductionOp op) { |
| // 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(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); |
| InductionInfo* new_b = TransferAddSub(a->op_b, b->op_b, op); |
| 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); |
| if (b->induction_class == kWrapAround || b->induction_class == kPeriodic) { |
| new_a = TransferAddSub(a, new_a, op); |
| } else if (op == kSub) { // Negation required. |
| new_a = TransferNeg(new_a); |
| } |
| 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(a->op_b, b, op); |
| if (a->induction_class == kWrapAround || a->induction_class == kPeriodic) { |
| new_a = TransferAddSub(new_a, b, op); |
| } |
| 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(InductionInfo* a) { |
| // 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 |
| } else if (a->induction_class != kGeometric || a->operation == kMul) { |
| // Rule - induc(a, b) -> induc(-a, -b). |
| InductionInfo* new_a = TransferNeg(a->op_a); |
| InductionInfo* new_b = TransferNeg(a->op_b); |
| 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(InductionInfo* a, |
| InductionInfo* b) { |
| // 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(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); |
| InductionInfo* new_b = TransferMul(a, b->op_b); |
| 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); |
| InductionInfo* new_b = TransferMul(a->op_b, b); |
| 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) { |
| // 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( |
| HLoopInformation* loop, |
| HInstruction* entry_phi, |
| HInstruction* phi) { |
| // Match all phi inputs. |
| InductionInfo* match = SolvePhi(phi, /*input_index*/ 0, /*adjust_input_size*/ 0); |
| 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); |
| if (b != nullptr && b->induction_class == kPeriodic) { |
| return CreateInduction(kPeriodic, kNop, a, b, /*fetch*/ nullptr, type_); |
| } |
| } |
| } |
| return nullptr; |
| } |
| |
| HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop, |
| HInstruction* entry_phi, |
| HInstruction* instruction, |
| HInstruction* x, |
| HInstruction* y, |
| InductionOp op, |
| bool is_first_call) { |
| // 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(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); |
| } |
| } |
| } 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(b); |
| if (new_a != nullptr) { |
| return CreateInduction(kPolynomial, kNop, new_a, initial, /*fetch*/ nullptr, type_); |
| } |
| } |
| } |
| } |
| |
| // Try some alternatives before failing. |
| if (op == kAdd) { |
| // Try the other way around for an addition if considered for first time. |
| if (is_first_call) { |
| return SolveAddSub(loop, entry_phi, instruction, y, x, op, false); |
| } |
| } 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)); |
| return CreateInduction(kPeriodic, |
| kNop, |
| CreateInvariantOp(kSub, a, initial), |
| initial, |
| /*fetch*/ nullptr, |
| type_); |
| } |
| } |
| } |
| return nullptr; |
| } |
| |
| HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInformation* loop, |
| HInstruction* entry_phi, |
| HInstruction* instruction, |
| HInstruction* x, |
| HInstruction* y, |
| InductionOp op) { |
| // 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) { |
| 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(kRem, initial, c), |
| /*fetch*/ nullptr, |
| type_); |
| case kXor: |
| // Idiomatic XOR periodic induction. |
| return CreateInduction(kPeriodic, |
| kNop, |
| CreateInvariantOp(kXor, initial, c), |
| initial, |
| /*fetch*/ nullptr, |
| type_); |
| default: |
| LOG(FATAL) << op; |
| UNREACHABLE(); |
| } |
| } |
| } |
| return nullptr; |
| } |
| |
| HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveTest(HLoopInformation* loop, |
| HInstruction* entry_phi, |
| HInstruction* instruction, |
| int64_t opposite_value) { |
| // Detect hidden XOR construction in x = (x == false) or x = (x != true). |
| int64_t value = -1; |
| HInstruction* x = instruction->InputAt(0); |
| HInstruction* y = instruction->InputAt(1); |
| if (IsExact(LookupInfo(loop, x), &value) && value == opposite_value) { |
| return SolveOp(loop, entry_phi, instruction, graph_->GetIntConstant(1), y, kXor); |
| } else if (IsExact(LookupInfo(loop, y), &value) && value == opposite_value) { |
| return SolveOp(loop, entry_phi, instruction, x, graph_->GetIntConstant(1), kXor); |
| } |
| return nullptr; |
| } |
| |
| HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveConversion( |
| HLoopInformation* loop, |
| HInstruction* entry_phi, |
| HTypeConversion* conversion) { |
| 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; |
| InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); |
| if (IsNarrowingIntegralConversion(from, to) && |
| IsAtLeast(initial, &value) && value >= min && |
| IsAtMost(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; |
| } |
| |
| void HInductionVarAnalysis::VisitControl(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(); |
| 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(loop, a, b, type, condition->GetOppositeCondition()); |
| } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) { |
| VisitCondition(loop, a, b, type, condition->GetCondition()); |
| } |
| } |
| } |
| } |
| |
| void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, |
| 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(loop, b, a, type, kCondGT); break; |
| case kCondLE: VisitCondition(loop, b, a, type, kCondGE); break; |
| case kCondGT: VisitCondition(loop, b, a, type, kCondLT); break; |
| case kCondGE: VisitCondition(loop, b, a, type, kCondLE); break; |
| case kCondNE: VisitCondition(loop, 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; |
| // Constant stride? |
| int64_t stride_value = 0; |
| if (!IsExact(stride_expr, &stride_value)) { |
| return; |
| } |
| // 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)))) { |
| cmp = stride_value > 0 ? kCondLT : kCondGT; |
| } |
| // Only accept integral condition. 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 != DataType::Type::kInt32 && type != DataType::Type::kInt64) { |
| return; // not integral |
| } else if (type != a->type && |
| !FitsNarrowerControl(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(loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp); |
| } |
| } |
| } |
| |
| void HInductionVarAnalysis::VisitTripCount(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(lower_expr, upper_expr, cmp); |
| const bool is_finite = IsFinite(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)); |
| } else if (cmp == kCondGT) { |
| trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type)); |
| } |
| // Compensate for stride. |
| trip_count = CreateInvariantOp(kAdd, trip_count, stride_expr); |
| } |
| trip_count = CreateInvariantOp( |
| kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), 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(op, lower_expr, upper_expr); |
| DCHECK(control->IsIf()); |
| AssignInfo(loop, control, CreateTripCount(tcKind, trip_count, taken_test, type)); |
| } |
| |
| bool HInductionVarAnalysis::IsTaken(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) |
| && lower_value < upper_value; |
| case kCondLE: |
| return IsAtMost(lower_expr, &lower_value) |
| && IsAtLeast(upper_expr, &upper_value) |
| && lower_value <= upper_value; |
| case kCondGT: |
| return IsAtLeast(lower_expr, &lower_value) |
| && IsAtMost(upper_expr, &upper_value) |
| && lower_value > upper_value; |
| case kCondGE: |
| return IsAtLeast(lower_expr, &lower_value) |
| && IsAtMost(upper_expr, &upper_value) |
| && lower_value >= upper_value; |
| default: |
| LOG(FATAL) << "CONDITION UNREACHABLE"; |
| } |
| return false; // not certain, may be untaken |
| } |
| |
| bool HInductionVarAnalysis::IsFinite(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(upper_expr, &value) && value <= (max - stride_value + 1)); |
| case kCondLE: |
| return (IsAtMost(upper_expr, &value) && value <= (max - stride_value)); |
| case kCondGT: |
| return stride_value == -1 || |
| (IsAtLeast(upper_expr, &value) && value >= (min - stride_value - 1)); |
| case kCondGE: |
| return (IsAtLeast(upper_expr, &value) && value >= (min - stride_value)); |
| default: |
| LOG(FATAL) << "CONDITION UNREACHABLE"; |
| } |
| return false; // not certain, may be infinite |
| } |
| |
| bool HInductionVarAnalysis::FitsNarrowerControl(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(lower_expr, &value) && value >= min && |
| IsAtMost(lower_expr, &value) && value <= max && |
| IsAtLeast(upper_expr, &value) && value >= min && |
| IsAtMost(upper_expr, &value) && value <= max; |
| } |
| |
| void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop, |
| HInstruction* instruction, |
| InductionInfo* info) { |
| auto it = induction_.find(loop); |
| if (it == induction_.end()) { |
| it = induction_.Put(loop, |
| ArenaSafeMap<HInstruction*, InductionInfo*>( |
| std::less<HInstruction*>(), |
| graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis))); |
| } |
| it->second.Put(instruction, info); |
| } |
| |
| HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(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( |
| 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(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(kNeg, nullptr, b); |
| } |
| } |
| } |
| if (IsExact(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(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); |
| } else if (op == kSub) { |
| return CreateSimplifiedInvariant(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 new (graph_->GetArena()) InductionInfo( |
| kInvariant, op, a, b, nullptr, ImplicitConversion(b->type)); |
| } |
| |
| HInstruction* HInductionVarAnalysis::GetShiftConstant(HLoopInformation* loop, |
| HInstruction* instruction, |
| InductionInfo* initial) { |
| DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); |
| // 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) { |
| 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(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) { |
| ArenaSet<HInstruction*>* set = &cycles_.Put(phi, ArenaSet<HInstruction*>( |
| graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)))->second; |
| for (HInstruction* i : scc_) { |
| set->insert(i); |
| } |
| } |
| |
| ArenaSet<HInstruction*>* HInductionVarAnalysis::LookupCycle(HPhi* phi) { |
| auto it = cycles_.find(phi); |
| if (it != cycles_.end()) { |
| return &it->second; |
| } |
| return nullptr; |
| } |
| |
| bool HInductionVarAnalysis::IsExact(InductionInfo* info, int64_t* value) { |
| return InductionVarRange(this).IsConstant(info, InductionVarRange::kExact, value); |
| } |
| |
| bool HInductionVarAnalysis::IsAtMost(InductionInfo* info, int64_t* value) { |
| return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtMost, value); |
| } |
| |
| bool HInductionVarAnalysis::IsAtLeast(InductionInfo* info, int64_t* value) { |
| return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtLeast, value); |
| } |
| |
| bool HInductionVarAnalysis::IsNarrowingLinear(InductionInfo* info) { |
| return info != nullptr && |
| info->induction_class == kLinear && |
| (info->type == DataType::Type::kInt8 || |
| info->type == DataType::Type::kInt16 || |
| info->type == DataType::Type::kUint16 || |
| (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 ""; |
| } |
| |
| } // namespace art |