/* * 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 "nodes.h" #include "optimization.h" namespace art { /** * 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, const char* name = kInductionPassName); bool Run() override; static constexpr const char* kInductionPassName = "induction_var_analysis"; private: struct NodeInfo { explicit NodeInfo(uint32_t d) : depth(d), done(false) {} uint32_t depth; bool done; }; 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 }; bool IsVisitedNode(HInstruction* instruction) const { return map_.find(instruction) != map_.end(); } InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) { DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr); return CreateSimplifiedInvariant(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(HLoopInformation* loop); void VisitNode(HLoopInformation* loop, HInstruction* instruction); uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction); void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction); void ClassifyNonTrivial(HLoopInformation* loop); InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last); // Transfer operations. InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index, size_t adjust_input_size); InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op); InductionInfo* TransferNeg(InductionInfo* a); InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b); InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to); // Solvers. InductionInfo* SolvePhi(HInstruction* phi, size_t input_index, size_t adjust_input_size); InductionInfo* SolvePhiAllInputs(HLoopInformation* loop, HInstruction* entry_phi, HInstruction* phi); InductionInfo* SolveAddSub(HLoopInformation* loop, HInstruction* entry_phi, HInstruction* instruction, HInstruction* x, HInstruction* y, InductionOp op, bool is_first_call); // possibly swaps x and y to try again InductionInfo* SolveOp(HLoopInformation* loop, HInstruction* entry_phi, HInstruction* instruction, HInstruction* x, HInstruction* y, InductionOp op); InductionInfo* SolveTest(HLoopInformation* loop, HInstruction* entry_phi, HInstruction* instruction, int64_t oppositive_value); InductionInfo* SolveConversion(HLoopInformation* loop, HInstruction* entry_phi, HTypeConversion* conversion); // // Loop trip count analysis methods. // // Trip count information. void VisitControl(HLoopInformation* loop); void VisitCondition(HLoopInformation* loop, HBasicBlock* body, InductionInfo* a, InductionInfo* b, DataType::Type type, IfCondition cmp); void VisitTripCount(HLoopInformation* loop, InductionInfo* lower_expr, InductionInfo* upper_expr, InductionInfo* stride, int64_t stride_value, DataType::Type type, IfCondition cmp); bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp); bool IsFinite(InductionInfo* upper_expr, int64_t stride_value, DataType::Type type, IfCondition cmp); bool FitsNarrowerControl(InductionInfo* lower_expr, InductionInfo* upper_expr, int64_t stride_value, DataType::Type type, IfCondition cmp); bool RewriteBreakLoop(HLoopInformation* loop, HBasicBlock* body, int64_t stride_value, DataType::Type type); // // Helper methods. // // Assign and lookup. void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction); InductionInfo* CreateConstant(int64_t value, DataType::Type type); InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b); HInstruction* GetShiftConstant(HLoopInformation* loop, HInstruction* instruction, InductionInfo* initial); void AssignCycle(HPhi* phi); ArenaSet* LookupCycle(HPhi* phi); // Constants. bool IsExact(InductionInfo* info, /*out*/ int64_t* value); bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value); bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value); // 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); // TODO: fine tune the following data structures, only keep relevant data. // Temporary book-keeping during the analysis. uint32_t global_depth_; ArenaVector stack_; ArenaSafeMap map_; ArenaVector scc_; ArenaSafeMap cycle_; DataType::Type type_; /** * 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_