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 "base/arena_containers.h" 23 #include "base/array_ref.h" 24 #include "base/scoped_arena_containers.h" 25 #include "nodes.h" 26 #include "optimization.h" 27 28 namespace art { 29 30 /** 31 * Induction variable analysis. This class does not have a direct public API. 32 * Instead, the results of induction variable analysis can be queried through 33 * friend classes, such as InductionVarRange. 34 * 35 * The analysis implementation is based on the paper by M. Gerlek et al. 36 * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form" 37 * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995). 38 */ 39 class HInductionVarAnalysis : public HOptimization { 40 public: 41 explicit HInductionVarAnalysis(HGraph* graph, const char* name = kInductionPassName); 42 43 bool Run() override; 44 45 static constexpr const char* kInductionPassName = "induction_var_analysis"; 46 47 private: 48 struct NodeInfo; 49 struct StackEntry; 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> { InductionInfoInductionInfo101 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 CreateInvariantOp(const HBasicBlock * context,const HLoopInformation * loop,InductionOp op,InductionInfo * a,InductionInfo * b)122 InductionInfo* CreateInvariantOp(const HBasicBlock* context, 123 const HLoopInformation* loop, 124 InductionOp op, 125 InductionInfo* a, 126 InductionInfo* b) { 127 DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr); 128 return CreateSimplifiedInvariant(context, loop, op, a, b); 129 } 130 CreateInvariantFetch(HInstruction * f)131 InductionInfo* CreateInvariantFetch(HInstruction* f) { 132 DCHECK(f != nullptr); 133 return new (graph_->GetAllocator()) 134 InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType()); 135 } 136 CreateTripCount(InductionOp op,InductionInfo * a,InductionInfo * b,DataType::Type type)137 InductionInfo* CreateTripCount(InductionOp op, 138 InductionInfo* a, 139 InductionInfo* b, 140 DataType::Type type) { 141 DCHECK(a != nullptr && b != nullptr); 142 return new (graph_->GetAllocator()) InductionInfo(kInvariant, op, a, b, nullptr, type); 143 } 144 CreateInduction(InductionClass ic,InductionOp op,InductionInfo * a,InductionInfo * b,HInstruction * f,DataType::Type type)145 InductionInfo* CreateInduction(InductionClass ic, 146 InductionOp op, 147 InductionInfo* a, 148 InductionInfo* b, 149 HInstruction* f, 150 DataType::Type type) { 151 DCHECK(a != nullptr && b != nullptr); 152 return new (graph_->GetAllocator()) InductionInfo(ic, op, a, b, f, type); 153 } 154 155 // Methods for analysis. 156 void VisitLoop(const HLoopInformation* loop); 157 size_t TryVisitNodes(const HLoopInformation* loop, 158 HInstruction* start_instruction, 159 size_t global_depth, 160 /*inout*/ ScopedArenaSafeMap<HInstruction*, NodeInfo>* visited_instructions); 161 void ExtractScc(ArrayRef<const StackEntry> stack_tail, ScopedArenaVector<HInstruction*>* scc); 162 void ClassifyTrivial(const HLoopInformation* loop, HInstruction* instruction); 163 void ClassifyNonTrivial(const HLoopInformation* loop, ArrayRef<const StackEntry> stack_tail); 164 InductionInfo* RotatePeriodicInduction(InductionInfo* induction, 165 InductionInfo* last, 166 DataType::Type type); 167 168 // Transfer operations. 169 InductionInfo* TransferPhi(const HLoopInformation* loop, 170 HInstruction* phi, 171 size_t input_index, 172 size_t adjust_input_size); 173 InductionInfo* TransferAddSub(const HBasicBlock* context, 174 const HLoopInformation* loop, 175 InductionInfo* a, 176 InductionInfo* b, 177 InductionOp op, 178 DataType::Type type); 179 InductionInfo* TransferNeg(const HBasicBlock* context, 180 const HLoopInformation* loop, 181 InductionInfo* a, 182 DataType::Type type); 183 InductionInfo* TransferMul(const HBasicBlock* context, 184 const HLoopInformation* loop, 185 InductionInfo* a, 186 InductionInfo* b, 187 DataType::Type type); 188 InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to); 189 190 // Solvers. 191 InductionInfo* SolvePhi(HInstruction* phi, 192 size_t input_index, 193 size_t adjust_input_size, 194 const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle); 195 InductionInfo* SolvePhiAllInputs(const HLoopInformation* loop, 196 HInstruction* entry_phi, 197 HInstruction* phi, 198 const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle, 199 DataType::Type type); 200 InductionInfo* SolveAddSub(const HLoopInformation* loop, 201 HInstruction* entry_phi, 202 HInstruction* instruction, 203 HInstruction* x, 204 HInstruction* y, 205 InductionOp op, 206 const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle, 207 DataType::Type type); 208 InductionInfo* SolveOp(const HLoopInformation* loop, 209 HInstruction* entry_phi, 210 HInstruction* instruction, 211 HInstruction* x, 212 HInstruction* y, 213 InductionOp op, 214 DataType::Type type); 215 InductionInfo* SolveTest(const HLoopInformation* loop, 216 HInstruction* entry_phi, 217 HInstruction* instruction, 218 int64_t opposite_value, 219 DataType::Type type); 220 InductionInfo* SolveConversion(const HLoopInformation* loop, 221 HInstruction* entry_phi, 222 HTypeConversion* conversion, 223 const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle, 224 /*inout*/ DataType::Type* type); 225 226 // 227 // Loop trip count analysis methods. 228 // 229 230 // Trip count information. 231 void VisitControl(const HLoopInformation* loop); 232 void VisitCondition(const HBasicBlock* context, 233 const HLoopInformation* loop, 234 HBasicBlock* body, 235 InductionInfo* a, 236 InductionInfo* b, 237 DataType::Type type, 238 IfCondition cmp); 239 void VisitTripCount(const HBasicBlock* context, 240 const HLoopInformation* loop, 241 InductionInfo* lower_expr, 242 InductionInfo* upper_expr, 243 InductionInfo* stride, 244 int64_t stride_value, 245 DataType::Type type, 246 IfCondition cmp); 247 bool IsTaken(const HBasicBlock* context, 248 const HLoopInformation* loop, 249 InductionInfo* lower_expr, 250 InductionInfo* upper_expr, 251 IfCondition cmp); 252 bool IsFinite(const HBasicBlock* context, 253 const HLoopInformation* loop, 254 InductionInfo* upper_expr, 255 int64_t stride_value, 256 DataType::Type type, 257 IfCondition cmp); 258 bool FitsNarrowerControl(const HBasicBlock* context, 259 const HLoopInformation* loop, 260 InductionInfo* lower_expr, 261 InductionInfo* upper_expr, 262 int64_t stride_value, 263 DataType::Type type, 264 IfCondition cmp); 265 bool RewriteBreakLoop(const HBasicBlock* context, 266 const HLoopInformation* loop, 267 HBasicBlock* body, 268 int64_t stride_value, 269 DataType::Type type); 270 271 // 272 // Helper methods. 273 // 274 275 // Assign and lookup. 276 void AssignInfo(const HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); 277 InductionInfo* LookupInfo(const HLoopInformation* loop, HInstruction* instruction); 278 InductionInfo* CreateConstant(int64_t value, DataType::Type type); 279 InductionInfo* CreateSimplifiedInvariant(const HBasicBlock* context, 280 const HLoopInformation* loop, 281 InductionOp op, 282 InductionInfo* a, 283 InductionInfo* b); 284 HInstruction* GetShiftConstant(const HLoopInformation* loop, 285 HInstruction* instruction, 286 InductionInfo* initial); 287 void AssignCycle(HPhi* phi, ArrayRef<HInstruction* const> scc); 288 ArenaSet<HInstruction*>* LookupCycle(HPhi* phi); 289 290 // Constants. 291 bool IsExact(const HBasicBlock* context, 292 const HLoopInformation* loop, 293 InductionInfo* info, 294 /*out*/int64_t* value); 295 bool IsAtMost(const HBasicBlock* context, 296 const HLoopInformation* loop, 297 InductionInfo* info, 298 /*out*/int64_t* value); 299 bool IsAtLeast(const HBasicBlock* context, 300 const HLoopInformation* loop, 301 InductionInfo* info, 302 /*out*/int64_t* value); 303 304 // Helpers. 305 static bool IsNarrowingLinear(InductionInfo* info); 306 static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); 307 static std::string FetchToString(HInstruction* fetch); 308 static std::string InductionToString(InductionInfo* info); 309 310 /** 311 * Maintains the results of the analysis as a mapping from loops to a mapping from instructions 312 * to the induction information for that instruction in that loop. 313 */ 314 ArenaSafeMap<const HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_; 315 316 /** 317 * Preserves induction cycle information for each loop-phi. 318 */ 319 ArenaSafeMap<HPhi*, ArenaSet<HInstruction*>> cycles_; 320 321 friend class InductionVarAnalysisTest; 322 friend class InductionVarRange; 323 friend class InductionVarRangeTest; 324 325 DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis); 326 }; 327 328 } // namespace art 329 330 #endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 331