/* * 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. */ #ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ #define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ #include #include "base/arena_containers.h" #include "base/array_ref.h" #include "base/macros.h" #include "base/scoped_arena_containers.h" #include "nodes.h" #include "optimization.h" namespace art HIDDEN { /** * Induction variable analysis. This class does not have a direct public API. * Instead, the results of induction variable analysis can be queried through * friend classes, such as InductionVarRange. * * The analysis implementation is based on the paper by M. Gerlek et al. * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form" * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995). */ class HInductionVarAnalysis : public HOptimization { public: explicit HInductionVarAnalysis(HGraph* graph, OptimizingCompilerStats* stats = nullptr, const char* name = kInductionPassName); bool Run() override; static constexpr const char* kInductionPassName = "induction_var_analysis"; private: struct NodeInfo; struct StackEntry; enum InductionClass { kInvariant, kLinear, kPolynomial, kGeometric, kWrapAround, kPeriodic }; enum InductionOp { // Operations. kNop, kAdd, kSub, kNeg, kMul, kDiv, kRem, kXor, kFetch, // Trip-counts. kTripCountInLoop, // valid in full loop; loop is finite kTripCountInBody, // valid in body only; loop is finite kTripCountInLoopUnsafe, // valid in full loop; loop may be infinite kTripCountInBodyUnsafe, // valid in body only; loop may be infinite // Comparisons for trip-count tests. kLT, kLE, kGT, kGE }; /** * Defines a detected induction as: * (1) invariant: * op: a + b, a - b, -b, a * b, a / b, a % b, a ^ b, fetch * (2) linear: * nop: a * i + b * (3) polynomial: * nop: sum_lt(a) + b, for linear a * (4) geometric: * op: a * fetch^i + b, a * fetch^-i + b * (5) wrap-around * nop: a, then defined by b * (6) periodic * nop: a, then defined by b (repeated when exhausted) * (7) trip-count: * tc: defined by a, taken-test in b */ struct InductionInfo : public ArenaObject { InductionInfo(InductionClass ic, InductionOp op, InductionInfo* a, InductionInfo* b, HInstruction* f, DataType::Type t) : induction_class(ic), operation(op), op_a(a), op_b(b), fetch(f), type(t) {} InductionClass induction_class; InductionOp operation; InductionInfo* op_a; InductionInfo* op_b; HInstruction* fetch; DataType::Type type; // precision of operation }; InductionInfo* CreateInvariantOp(const HBasicBlock* context, const HLoopInformation* loop, InductionOp op, InductionInfo* a, InductionInfo* b) { DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr); return CreateSimplifiedInvariant(context, loop, op, a, b); } InductionInfo* CreateInvariantFetch(HInstruction* f) { DCHECK(f != nullptr); return new (graph_->GetAllocator()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType()); } InductionInfo* CreateTripCount(InductionOp op, InductionInfo* a, InductionInfo* b, DataType::Type type) { DCHECK(a != nullptr && b != nullptr); return new (graph_->GetAllocator()) InductionInfo(kInvariant, op, a, b, nullptr, type); } InductionInfo* CreateInduction(InductionClass ic, InductionOp op, InductionInfo* a, InductionInfo* b, HInstruction* f, DataType::Type type) { DCHECK(a != nullptr && b != nullptr); return new (graph_->GetAllocator()) InductionInfo(ic, op, a, b, f, type); } // Methods for analysis. void VisitLoop(const HLoopInformation* loop); size_t TryVisitNodes(const HLoopInformation* loop, HInstruction* start_instruction, size_t global_depth, /*inout*/ ScopedArenaSafeMap* visited_instructions); void ExtractScc(ArrayRef stack_tail, ScopedArenaVector* scc); void ClassifyTrivial(const HLoopInformation* loop, HInstruction* instruction); void ClassifyNonTrivial(const HLoopInformation* loop, ArrayRef stack_tail); InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last, DataType::Type type); // Transfer operations. InductionInfo* TransferPhi(const HLoopInformation* loop, HInstruction* phi, size_t input_index, size_t adjust_input_size); InductionInfo* TransferAddSub(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* a, InductionInfo* b, InductionOp op, DataType::Type type); InductionInfo* TransferNeg(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* a, DataType::Type type); InductionInfo* TransferMul(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* a, InductionInfo* b, DataType::Type type); InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to); // Solvers. InductionInfo* SolvePhi(HInstruction* phi, size_t input_index, size_t adjust_input_size, const ScopedArenaSafeMap& cycle); InductionInfo* SolvePhiAllInputs(const HLoopInformation* loop, HInstruction* entry_phi, HInstruction* phi, const ScopedArenaSafeMap& cycle, DataType::Type type); InductionInfo* SolveAddSub(const HLoopInformation* loop, HInstruction* entry_phi, HInstruction* instruction, HInstruction* x, HInstruction* y, InductionOp op, const ScopedArenaSafeMap& cycle, DataType::Type type); InductionInfo* SolveOp(const HLoopInformation* loop, HInstruction* entry_phi, HInstruction* instruction, HInstruction* x, HInstruction* y, InductionOp op, DataType::Type type); InductionInfo* SolveTest(const HLoopInformation* loop, HInstruction* entry_phi, HInstruction* instruction, int64_t opposite_value, DataType::Type type); InductionInfo* SolveConversion(const HLoopInformation* loop, HInstruction* entry_phi, HTypeConversion* conversion, const ScopedArenaSafeMap& cycle, /*inout*/ DataType::Type* type); // // Loop trip count analysis methods. // // Trip count information. void VisitControl(const HLoopInformation* loop); void VisitCondition(const HBasicBlock* context, const HLoopInformation* loop, HBasicBlock* body, InductionInfo* a, InductionInfo* b, DataType::Type type, IfCondition cmp); void VisitTripCount(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* lower_expr, InductionInfo* upper_expr, InductionInfo* stride, int64_t stride_value, DataType::Type type, IfCondition cmp); bool IsTaken(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp); bool IsFinite(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* upper_expr, int64_t stride_value, DataType::Type type, IfCondition cmp); bool FitsNarrowerControl(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* lower_expr, InductionInfo* upper_expr, int64_t stride_value, DataType::Type type, IfCondition cmp); bool RewriteBreakLoop(const HBasicBlock* context, const HLoopInformation* loop, HBasicBlock* body, int64_t stride_value, DataType::Type type); // // Helper methods. // // Assign and lookup. void AssignInfo(const HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); InductionInfo* LookupInfo(const HLoopInformation* loop, HInstruction* instruction); InductionInfo* CreateConstant(int64_t value, DataType::Type type); InductionInfo* CreateSimplifiedInvariant(const HBasicBlock* context, const HLoopInformation* loop, InductionOp op, InductionInfo* a, InductionInfo* b); HInstruction* GetShiftConstant(const HLoopInformation* loop, HInstruction* instruction, InductionInfo* initial); void AssignCycle(HPhi* phi, ArrayRef scc); ArenaSet* LookupCycle(HPhi* phi); // Constants. bool IsExact(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* info, /*out*/int64_t* value); bool IsAtMost(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* info, /*out*/int64_t* value); bool IsAtLeast(const HBasicBlock* context, const HLoopInformation* loop, InductionInfo* info, /*out*/int64_t* value); // Helpers. static bool IsNarrowingLinear(InductionInfo* info); static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); static std::string FetchToString(HInstruction* fetch); static std::string InductionToString(InductionInfo* info); // Returns true if we have a pathological case we don't want to analyze. bool IsPathologicalCase(); // Starting with initial_phi, it calculates how many loop header phis in a row we have. To do // this, we count the loop header phi which are used as an input of other loop header phis. It // uses `cached_values` to avoid recomputing results. void CalculateLoopHeaderPhisInARow(HPhi* initial_phi, ScopedArenaSafeMap& cached_values, ScopedArenaAllocator& allocator); /** * Maintains the results of the analysis as a mapping from loops to a mapping from instructions * to the induction information for that instruction in that loop. */ ArenaSafeMap> induction_; /** * Preserves induction cycle information for each loop-phi. */ ArenaSafeMap> cycles_; friend class InductionVarAnalysisTest; friend class InductionVarRange; friend class InductionVarRangeTest; DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis); }; } // namespace art #endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_