1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 18 #define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 19 20 #include <string> 21 22 #include "nodes.h" 23 #include "optimization.h" 24 25 namespace art { 26 27 /** 28 * Induction variable analysis. This class does not have a direct public API. 29 * Instead, the results of induction variable analysis can be queried through 30 * friend classes, such as InductionVarRange. 31 * 32 * The analysis implementation is based on the paper by M. Gerlek et al. 33 * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form" 34 * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995). 35 */ 36 class HInductionVarAnalysis : public HOptimization { 37 public: 38 explicit HInductionVarAnalysis(HGraph* graph); 39 40 void Run() OVERRIDE; 41 42 private: 43 static constexpr const char* kInductionPassName = "induction_var_analysis"; 44 45 struct NodeInfo { NodeInfoNodeInfo46 explicit NodeInfo(uint32_t d) : depth(d), done(false) {} 47 uint32_t depth; 48 bool done; 49 }; 50 51 enum InductionClass { 52 kInvariant, 53 kLinear, 54 kWrapAround, 55 kPeriodic 56 }; 57 58 enum InductionOp { 59 // No-operation: a true induction. 60 kNop, 61 // Various invariant operations. 62 kAdd, 63 kSub, 64 kNeg, 65 kMul, 66 kDiv, 67 kFetch, 68 // Trip-counts. 69 kTripCountInLoop, // valid in full loop; loop is finite 70 kTripCountInBody, // valid in body only; loop is finite 71 kTripCountInLoopUnsafe, // valid in full loop; loop may be infinite 72 kTripCountInBodyUnsafe, // valid in body only; loop may be infinite 73 // Comparisons for trip-count tests. 74 kLT, 75 kLE, 76 kGT, 77 kGE 78 }; 79 80 /** 81 * Defines a detected induction as: 82 * (1) invariant: 83 * operation: a + b, a - b, -b, a * b, a / b 84 * or: 85 * fetch: fetch from HIR 86 * (2) linear: 87 * nop: a * i + b 88 * (3) wrap-around 89 * nop: a, then defined by b 90 * (4) periodic 91 * nop: a, then defined by b (repeated when exhausted) 92 * (5) trip-count: 93 * tc: defined by a, taken-test in b 94 */ 95 struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> { InductionInfoInductionInfo96 InductionInfo(InductionClass ic, 97 InductionOp op, 98 InductionInfo* a, 99 InductionInfo* b, 100 HInstruction* f, 101 Primitive::Type t) 102 : induction_class(ic), 103 operation(op), 104 op_a(a), 105 op_b(b), 106 fetch(f), 107 type(t) {} 108 InductionClass induction_class; 109 InductionOp operation; 110 InductionInfo* op_a; 111 InductionInfo* op_b; 112 HInstruction* fetch; 113 Primitive::Type type; // precision of induction 114 }; 115 IsVisitedNode(HInstruction * instruction)116 bool IsVisitedNode(HInstruction* instruction) const { 117 return map_.find(instruction) != map_.end(); 118 } 119 CreateInvariantOp(InductionOp op,InductionInfo * a,InductionInfo * b)120 InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) { 121 DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr); 122 return CreateSimplifiedInvariant(op, a, b); 123 } 124 CreateInvariantFetch(HInstruction * f)125 InductionInfo* CreateInvariantFetch(HInstruction* f) { 126 DCHECK(f != nullptr); 127 return new (graph_->GetArena()) 128 InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType()); 129 } 130 CreateTripCount(InductionOp op,InductionInfo * a,InductionInfo * b,Primitive::Type type)131 InductionInfo* CreateTripCount(InductionOp op, 132 InductionInfo* a, 133 InductionInfo* b, 134 Primitive::Type type) { 135 DCHECK(a != nullptr); 136 return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr, type); 137 } 138 CreateInduction(InductionClass ic,InductionInfo * a,InductionInfo * b,Primitive::Type type)139 InductionInfo* CreateInduction(InductionClass ic, 140 InductionInfo* a, 141 InductionInfo* b, 142 Primitive::Type type) { 143 DCHECK(a != nullptr && b != nullptr); 144 return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr, type); 145 } 146 147 // Methods for analysis. 148 void VisitLoop(HLoopInformation* loop); 149 void VisitNode(HLoopInformation* loop, HInstruction* instruction); 150 uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction); 151 void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction); 152 void ClassifyNonTrivial(HLoopInformation* loop); 153 InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last); 154 155 // Transfer operations. 156 InductionInfo* TransferPhi(HLoopInformation* loop, HInstruction* phi, size_t input_index); 157 InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op); 158 InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b); 159 InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type type); 160 InductionInfo* TransferNeg(InductionInfo* a); 161 InductionInfo* TransferCnv(InductionInfo* a, Primitive::Type from, Primitive::Type to); 162 163 // Solvers. 164 InductionInfo* SolvePhi(HInstruction* phi, size_t input_index); 165 InductionInfo* SolvePhiAllInputs(HLoopInformation* loop, 166 HInstruction* entry_phi, 167 HInstruction* phi); 168 InductionInfo* SolveAddSub(HLoopInformation* loop, 169 HInstruction* entry_phi, 170 HInstruction* instruction, 171 HInstruction* x, 172 HInstruction* y, 173 InductionOp op, 174 bool is_first_call); 175 InductionInfo* SolveCnv(HTypeConversion* conversion); 176 177 // Trip count information. 178 void VisitControl(HLoopInformation* loop); 179 void VisitCondition(HLoopInformation* loop, 180 InductionInfo* a, 181 InductionInfo* b, 182 Primitive::Type type, 183 IfCondition cmp); 184 void VisitTripCount(HLoopInformation* loop, 185 InductionInfo* lower_expr, 186 InductionInfo* upper_expr, 187 InductionInfo* stride, 188 int64_t stride_value, 189 Primitive::Type type, 190 IfCondition cmp); 191 bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp); 192 bool IsFinite(InductionInfo* upper_expr, 193 int64_t stride_value, 194 Primitive::Type type, 195 IfCondition cmp); 196 bool FitsNarrowerControl(InductionInfo* lower_expr, 197 InductionInfo* upper_expr, 198 int64_t stride_value, 199 Primitive::Type type, 200 IfCondition cmp); 201 202 // Assign and lookup. 203 void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); 204 InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction); 205 InductionInfo* CreateConstant(int64_t value, Primitive::Type type); 206 InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b); 207 208 // Constants. 209 bool IsExact(InductionInfo* info, /*out*/ int64_t* value); 210 bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value); 211 bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value); 212 213 // Helpers. 214 static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); 215 static std::string InductionToString(InductionInfo* info); 216 217 // TODO: fine tune the following data structures, only keep relevant data. 218 219 // Temporary book-keeping during the analysis. 220 uint32_t global_depth_; 221 ArenaVector<HInstruction*> stack_; 222 ArenaVector<HInstruction*> scc_; 223 ArenaSafeMap<HInstruction*, NodeInfo> map_; 224 ArenaSafeMap<HInstruction*, InductionInfo*> cycle_; 225 Primitive::Type type_; 226 227 /** 228 * Maintains the results of the analysis as a mapping from loops to a mapping from instructions 229 * to the induction information for that instruction in that loop. 230 */ 231 ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_; 232 233 friend class InductionVarAnalysisTest; 234 friend class InductionVarRange; 235 friend class InductionVarRangeTest; 236 237 DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis); 238 }; 239 240 } // namespace art 241 242 #endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 243