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, const char* name = kInductionPassName); 39 40 void Run() OVERRIDE; 41 42 static constexpr const char* kInductionPassName = "induction_var_analysis"; 43 44 private: 45 struct NodeInfo { 46 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 kPolynomial, 55 kGeometric, 56 kWrapAround, 57 kPeriodic 58 }; 59 60 enum InductionOp { 61 // Operations. 62 kNop, 63 kAdd, 64 kSub, 65 kNeg, 66 kMul, 67 kDiv, 68 kRem, 69 kXor, 70 kFetch, 71 // Trip-counts. 72 kTripCountInLoop, // valid in full loop; loop is finite 73 kTripCountInBody, // valid in body only; loop is finite 74 kTripCountInLoopUnsafe, // valid in full loop; loop may be infinite 75 kTripCountInBodyUnsafe, // valid in body only; loop may be infinite 76 // Comparisons for trip-count tests. 77 kLT, 78 kLE, 79 kGT, 80 kGE 81 }; 82 83 /** 84 * Defines a detected induction as: 85 * (1) invariant: 86 * op: a + b, a - b, -b, a * b, a / b, a % b, a ^ b, fetch 87 * (2) linear: 88 * nop: a * i + b 89 * (3) polynomial: 90 * nop: sum_lt(a) + b, for linear a 91 * (4) geometric: 92 * op: a * fetch^i + b, a * fetch^-i + b 93 * (5) wrap-around 94 * nop: a, then defined by b 95 * (6) periodic 96 * nop: a, then defined by b (repeated when exhausted) 97 * (7) trip-count: 98 * tc: defined by a, taken-test in b 99 */ 100 struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> { 101 InductionInfo(InductionClass ic, 102 InductionOp op, 103 InductionInfo* a, 104 InductionInfo* b, 105 HInstruction* f, 106 DataType::Type t) 107 : induction_class(ic), 108 operation(op), 109 op_a(a), 110 op_b(b), 111 fetch(f), 112 type(t) {} 113 InductionClass induction_class; 114 InductionOp operation; 115 InductionInfo* op_a; 116 InductionInfo* op_b; 117 HInstruction* fetch; 118 DataType::Type type; // precision of operation 119 }; 120 121 bool IsVisitedNode(HInstruction* instruction) const { 122 return map_.find(instruction) != map_.end(); 123 } 124 125 InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) { 126 DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr); 127 return CreateSimplifiedInvariant(op, a, b); 128 } 129 130 InductionInfo* CreateInvariantFetch(HInstruction* f) { 131 DCHECK(f != nullptr); 132 return new (graph_->GetAllocator()) 133 InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType()); 134 } 135 136 InductionInfo* CreateTripCount(InductionOp op, 137 InductionInfo* a, 138 InductionInfo* b, 139 DataType::Type type) { 140 DCHECK(a != nullptr && b != nullptr); 141 return new (graph_->GetAllocator()) InductionInfo(kInvariant, op, a, b, nullptr, type); 142 } 143 144 InductionInfo* CreateInduction(InductionClass ic, 145 InductionOp op, 146 InductionInfo* a, 147 InductionInfo* b, 148 HInstruction* f, 149 DataType::Type type) { 150 DCHECK(a != nullptr && b != nullptr); 151 return new (graph_->GetAllocator()) InductionInfo(ic, op, a, b, f, type); 152 } 153 154 // Methods for analysis. 155 void VisitLoop(HLoopInformation* loop); 156 void VisitNode(HLoopInformation* loop, HInstruction* instruction); 157 uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction); 158 void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction); 159 void ClassifyNonTrivial(HLoopInformation* loop); 160 InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last); 161 162 // Transfer operations. 163 InductionInfo* TransferPhi(HLoopInformation* loop, 164 HInstruction* phi, 165 size_t input_index, 166 size_t adjust_input_size); 167 InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op); 168 InductionInfo* TransferNeg(InductionInfo* a); 169 InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b); 170 InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to); 171 172 // Solvers. 173 InductionInfo* SolvePhi(HInstruction* phi, size_t input_index, size_t adjust_input_size); 174 InductionInfo* SolvePhiAllInputs(HLoopInformation* loop, 175 HInstruction* entry_phi, 176 HInstruction* phi); 177 InductionInfo* SolveAddSub(HLoopInformation* loop, 178 HInstruction* entry_phi, 179 HInstruction* instruction, 180 HInstruction* x, 181 HInstruction* y, 182 InductionOp op, 183 bool is_first_call); // possibly swaps x and y to try again 184 InductionInfo* SolveOp(HLoopInformation* loop, 185 HInstruction* entry_phi, 186 HInstruction* instruction, 187 HInstruction* x, 188 HInstruction* y, 189 InductionOp op); 190 InductionInfo* SolveTest(HLoopInformation* loop, 191 HInstruction* entry_phi, 192 HInstruction* instruction, 193 int64_t oppositive_value); 194 InductionInfo* SolveConversion(HLoopInformation* loop, 195 HInstruction* entry_phi, 196 HTypeConversion* conversion); 197 198 // 199 // Loop trip count analysis methods. 200 // 201 202 // Trip count information. 203 void VisitControl(HLoopInformation* loop); 204 void VisitCondition(HLoopInformation* loop, 205 HBasicBlock* body, 206 InductionInfo* a, 207 InductionInfo* b, 208 DataType::Type type, 209 IfCondition cmp); 210 void VisitTripCount(HLoopInformation* loop, 211 InductionInfo* lower_expr, 212 InductionInfo* upper_expr, 213 InductionInfo* stride, 214 int64_t stride_value, 215 DataType::Type type, 216 IfCondition cmp); 217 bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp); 218 bool IsFinite(InductionInfo* upper_expr, 219 int64_t stride_value, 220 DataType::Type type, 221 IfCondition cmp); 222 bool FitsNarrowerControl(InductionInfo* lower_expr, 223 InductionInfo* upper_expr, 224 int64_t stride_value, 225 DataType::Type type, 226 IfCondition cmp); 227 bool RewriteBreakLoop(HLoopInformation* loop, 228 HBasicBlock* body, 229 int64_t stride_value, 230 DataType::Type type); 231 232 // 233 // Helper methods. 234 // 235 236 // Assign and lookup. 237 void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); 238 InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction); 239 InductionInfo* CreateConstant(int64_t value, DataType::Type type); 240 InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b); 241 HInstruction* GetShiftConstant(HLoopInformation* loop, 242 HInstruction* instruction, 243 InductionInfo* initial); 244 void AssignCycle(HPhi* phi); 245 ArenaSet<HInstruction*>* LookupCycle(HPhi* phi); 246 247 // Constants. 248 bool IsExact(InductionInfo* info, /*out*/ int64_t* value); 249 bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value); 250 bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value); 251 252 // Helpers. 253 static bool IsNarrowingLinear(InductionInfo* info); 254 static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); 255 static std::string FetchToString(HInstruction* fetch); 256 static std::string InductionToString(InductionInfo* info); 257 258 // TODO: fine tune the following data structures, only keep relevant data. 259 260 // Temporary book-keeping during the analysis. 261 uint32_t global_depth_; 262 ArenaVector<HInstruction*> stack_; 263 ArenaSafeMap<HInstruction*, NodeInfo> map_; 264 ArenaVector<HInstruction*> scc_; 265 ArenaSafeMap<HInstruction*, InductionInfo*> cycle_; 266 DataType::Type type_; 267 268 /** 269 * Maintains the results of the analysis as a mapping from loops to a mapping from instructions 270 * to the induction information for that instruction in that loop. 271 */ 272 ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_; 273 274 /** 275 * Preserves induction cycle information for each loop-phi. 276 */ 277 ArenaSafeMap<HPhi*, ArenaSet<HInstruction*>> cycles_; 278 279 friend class InductionVarAnalysisTest; 280 friend class InductionVarRange; 281 friend class InductionVarRangeTest; 282 283 DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis); 284 }; 285 286 } // namespace art 287 288 #endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 289
