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/macros.h" 25 #include "base/scoped_arena_containers.h" 26 #include "nodes.h" 27 #include "optimization.h" 28 29 namespace art HIDDEN { 30 31 /** 32 * Induction variable analysis. This class does not have a direct public API. 33 * Instead, the results of induction variable analysis can be queried through 34 * friend classes, such as InductionVarRange. 35 * 36 * The analysis implementation is based on the paper by M. Gerlek et al. 37 * "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form" 38 * (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995). 39 */ 40 class HInductionVarAnalysis : public HOptimization { 41 public: 42 explicit HInductionVarAnalysis(HGraph* graph, 43 OptimizingCompilerStats* stats = nullptr, 44 const char* name = kInductionPassName); 45 46 bool Run() override; 47 48 static constexpr const char* kInductionPassName = "induction_var_analysis"; 49 50 private: 51 struct NodeInfo; 52 struct StackEntry; 53 54 enum InductionClass { 55 kInvariant, 56 kLinear, 57 kPolynomial, 58 kGeometric, 59 kWrapAround, 60 kPeriodic 61 }; 62 63 enum InductionOp { 64 // Operations. 65 kNop, 66 kAdd, 67 kSub, 68 kNeg, 69 kMul, 70 kDiv, 71 kRem, 72 kXor, 73 kFetch, 74 // Trip-counts. 75 kTripCountInLoop, // valid in full loop; loop is finite 76 kTripCountInBody, // valid in body only; loop is finite 77 kTripCountInLoopUnsafe, // valid in full loop; loop may be infinite 78 kTripCountInBodyUnsafe, // valid in body only; loop may be infinite 79 // Comparisons for trip-count tests. 80 kLT, 81 kLE, 82 kGT, 83 kGE 84 }; 85 86 /** 87 * Defines a detected induction as: 88 * (1) invariant: 89 * op: a + b, a - b, -b, a * b, a / b, a % b, a ^ b, fetch 90 * (2) linear: 91 * nop: a * i + b 92 * (3) polynomial: 93 * nop: sum_lt(a) + b, for linear a 94 * (4) geometric: 95 * op: a * fetch^i + b, a * fetch^-i + b 96 * (5) wrap-around 97 * nop: a, then defined by b 98 * (6) periodic 99 * nop: a, then defined by b (repeated when exhausted) 100 * (7) trip-count: 101 * tc: defined by a, taken-test in b 102 */ 103 struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> { InductionInfoInductionInfo104 InductionInfo(InductionClass ic, 105 InductionOp op, 106 InductionInfo* a, 107 InductionInfo* b, 108 HInstruction* f, 109 DataType::Type t) 110 : induction_class(ic), 111 operation(op), 112 op_a(a), 113 op_b(b), 114 fetch(f), 115 type(t) {} 116 InductionClass induction_class; 117 InductionOp operation; 118 InductionInfo* op_a; 119 InductionInfo* op_b; 120 HInstruction* fetch; 121 DataType::Type type; // precision of operation 122 }; 123 124 CreateInvariantOp(const HBasicBlock * context,const HLoopInformation * loop,InductionOp op,InductionInfo * a,InductionInfo * b)125 InductionInfo* CreateInvariantOp(const HBasicBlock* context, 126 const HLoopInformation* loop, 127 InductionOp op, 128 InductionInfo* a, 129 InductionInfo* b) { 130 DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr); 131 return CreateSimplifiedInvariant(context, loop, op, a, b); 132 } 133 CreateInvariantFetch(HInstruction * f)134 InductionInfo* CreateInvariantFetch(HInstruction* f) { 135 DCHECK(f != nullptr); 136 return new (graph_->GetAllocator()) 137 InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType()); 138 } 139 CreateTripCount(InductionOp op,InductionInfo * a,InductionInfo * b,DataType::Type type)140 InductionInfo* CreateTripCount(InductionOp op, 141 InductionInfo* a, 142 InductionInfo* b, 143 DataType::Type type) { 144 DCHECK(a != nullptr && b != nullptr); 145 return new (graph_->GetAllocator()) InductionInfo(kInvariant, op, a, b, nullptr, type); 146 } 147 CreateInduction(InductionClass ic,InductionOp op,InductionInfo * a,InductionInfo * b,HInstruction * f,DataType::Type type)148 InductionInfo* CreateInduction(InductionClass ic, 149 InductionOp op, 150 InductionInfo* a, 151 InductionInfo* b, 152 HInstruction* f, 153 DataType::Type type) { 154 DCHECK(a != nullptr && b != nullptr); 155 return new (graph_->GetAllocator()) InductionInfo(ic, op, a, b, f, type); 156 } 157 158 // Methods for analysis. 159 void VisitLoop(const HLoopInformation* loop); 160 size_t TryVisitNodes(const HLoopInformation* loop, 161 HInstruction* start_instruction, 162 size_t global_depth, 163 /*inout*/ ScopedArenaSafeMap<HInstruction*, NodeInfo>* visited_instructions); 164 void ExtractScc(ArrayRef<const StackEntry> stack_tail, ScopedArenaVector<HInstruction*>* scc); 165 void ClassifyTrivial(const HLoopInformation* loop, HInstruction* instruction); 166 void ClassifyNonTrivial(const HLoopInformation* loop, ArrayRef<const StackEntry> stack_tail); 167 InductionInfo* RotatePeriodicInduction(InductionInfo* induction, 168 InductionInfo* last, 169 DataType::Type type); 170 171 // Transfer operations. 172 InductionInfo* TransferPhi(const HLoopInformation* loop, 173 HInstruction* phi, 174 size_t input_index, 175 size_t adjust_input_size); 176 InductionInfo* TransferAddSub(const HBasicBlock* context, 177 const HLoopInformation* loop, 178 InductionInfo* a, 179 InductionInfo* b, 180 InductionOp op, 181 DataType::Type type); 182 InductionInfo* TransferNeg(const HBasicBlock* context, 183 const HLoopInformation* loop, 184 InductionInfo* a, 185 DataType::Type type); 186 InductionInfo* TransferMul(const HBasicBlock* context, 187 const HLoopInformation* loop, 188 InductionInfo* a, 189 InductionInfo* b, 190 DataType::Type type); 191 InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to); 192 193 // Solvers. 194 InductionInfo* SolvePhi(HInstruction* phi, 195 size_t input_index, 196 size_t adjust_input_size, 197 const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle); 198 InductionInfo* SolvePhiAllInputs(const HLoopInformation* loop, 199 HInstruction* entry_phi, 200 HInstruction* phi, 201 const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle, 202 DataType::Type type); 203 InductionInfo* SolveAddSub(const HLoopInformation* loop, 204 HInstruction* entry_phi, 205 HInstruction* instruction, 206 HInstruction* x, 207 HInstruction* y, 208 InductionOp op, 209 const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle, 210 DataType::Type type); 211 InductionInfo* SolveOp(const HLoopInformation* loop, 212 HInstruction* entry_phi, 213 HInstruction* instruction, 214 HInstruction* x, 215 HInstruction* y, 216 InductionOp op, 217 DataType::Type type); 218 InductionInfo* SolveTest(const HLoopInformation* loop, 219 HInstruction* entry_phi, 220 HInstruction* instruction, 221 int64_t opposite_value, 222 DataType::Type type); 223 InductionInfo* SolveConversion(const HLoopInformation* loop, 224 HInstruction* entry_phi, 225 HTypeConversion* conversion, 226 const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle, 227 /*inout*/ DataType::Type* type); 228 229 // 230 // Loop trip count analysis methods. 231 // 232 233 // Trip count information. 234 void VisitControl(const HLoopInformation* loop); 235 void VisitCondition(const HBasicBlock* context, 236 const HLoopInformation* loop, 237 HBasicBlock* body, 238 InductionInfo* a, 239 InductionInfo* b, 240 DataType::Type type, 241 IfCondition cmp); 242 void VisitTripCount(const HBasicBlock* context, 243 const HLoopInformation* loop, 244 InductionInfo* lower_expr, 245 InductionInfo* upper_expr, 246 InductionInfo* stride, 247 int64_t stride_value, 248 DataType::Type type, 249 IfCondition cmp); 250 bool IsTaken(const HBasicBlock* context, 251 const HLoopInformation* loop, 252 InductionInfo* lower_expr, 253 InductionInfo* upper_expr, 254 IfCondition cmp); 255 bool IsFinite(const HBasicBlock* context, 256 const HLoopInformation* loop, 257 InductionInfo* upper_expr, 258 int64_t stride_value, 259 DataType::Type type, 260 IfCondition cmp); 261 bool FitsNarrowerControl(const HBasicBlock* context, 262 const HLoopInformation* loop, 263 InductionInfo* lower_expr, 264 InductionInfo* upper_expr, 265 int64_t stride_value, 266 DataType::Type type, 267 IfCondition cmp); 268 bool RewriteBreakLoop(const HBasicBlock* context, 269 const HLoopInformation* loop, 270 HBasicBlock* body, 271 int64_t stride_value, 272 DataType::Type type); 273 274 // 275 // Helper methods. 276 // 277 278 // Assign and lookup. 279 void AssignInfo(const HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); 280 InductionInfo* LookupInfo(const HLoopInformation* loop, HInstruction* instruction); 281 InductionInfo* CreateConstant(int64_t value, DataType::Type type); 282 InductionInfo* CreateSimplifiedInvariant(const HBasicBlock* context, 283 const HLoopInformation* loop, 284 InductionOp op, 285 InductionInfo* a, 286 InductionInfo* b); 287 HInstruction* GetShiftConstant(const HLoopInformation* loop, 288 HInstruction* instruction, 289 InductionInfo* initial); 290 void AssignCycle(HPhi* phi, ArrayRef<HInstruction* const> scc); 291 ArenaSet<HInstruction*>* LookupCycle(HPhi* phi); 292 293 // Constants. 294 bool IsExact(const HBasicBlock* context, 295 const HLoopInformation* loop, 296 InductionInfo* info, 297 /*out*/int64_t* value); 298 bool IsAtMost(const HBasicBlock* context, 299 const HLoopInformation* loop, 300 InductionInfo* info, 301 /*out*/int64_t* value); 302 bool IsAtLeast(const HBasicBlock* context, 303 const HLoopInformation* loop, 304 InductionInfo* info, 305 /*out*/int64_t* value); 306 307 // Helpers. 308 static bool IsNarrowingLinear(InductionInfo* info); 309 static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); 310 static std::string FetchToString(HInstruction* fetch); 311 static std::string InductionToString(InductionInfo* info); 312 313 // Returns true if we have a pathological case we don't want to analyze. 314 bool IsPathologicalCase(); 315 // Starting with initial_phi, it calculates how many loop header phis in a row we have. To do 316 // this, we count the loop header phi which are used as an input of other loop header phis. It 317 // uses `cached_values` to avoid recomputing results. 318 void CalculateLoopHeaderPhisInARow(HPhi* initial_phi, 319 ScopedArenaSafeMap<HPhi*, int>& cached_values, 320 ScopedArenaAllocator& allocator); 321 322 /** 323 * Maintains the results of the analysis as a mapping from loops to a mapping from instructions 324 * to the induction information for that instruction in that loop. 325 */ 326 ArenaSafeMap<const HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_; 327 328 /** 329 * Preserves induction cycle information for each loop-phi. 330 */ 331 ArenaSafeMap<HPhi*, ArenaSet<HInstruction*>> cycles_; 332 333 friend class InductionVarAnalysisTest; 334 friend class InductionVarRange; 335 friend class InductionVarRangeTest; 336 337 DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis); 338 }; 339 340 } // namespace art 341 342 #endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ 343