Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 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 | /** |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 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. |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 31 | * |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 32 | * The analysis implementation is based on the paper by M. Gerlek et al. |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 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 | |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 40 | void Run() OVERRIDE; |
| 41 | |
| 42 | private: |
| 43 | static constexpr const char* kInductionPassName = "induction_var_analysis"; |
| 44 | |
| 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 { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 52 | kInvariant, |
| 53 | kLinear, |
| 54 | kWrapAround, |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 55 | kPeriodic |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 56 | }; |
| 57 | |
| 58 | enum InductionOp { |
| 59 | kNop, // no-operation: a true induction |
| 60 | kAdd, |
| 61 | kSub, |
| 62 | kNeg, |
| 63 | kMul, |
| 64 | kDiv, |
| 65 | kFetch |
| 66 | }; |
| 67 | |
| 68 | /** |
| 69 | * Defines a detected induction as: |
| 70 | * (1) invariant: |
| 71 | * operation: a + b, a - b, -b, a * b, a / b |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 72 | * or: |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 73 | * fetch: fetch from HIR |
| 74 | * (2) linear: |
| 75 | * nop: a * i + b |
| 76 | * (3) wrap-around |
| 77 | * nop: a, then defined by b |
| 78 | * (4) periodic |
| 79 | * nop: a, then defined by b (repeated when exhausted) |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 80 | */ |
| 81 | struct InductionInfo : public ArenaObject<kArenaAllocMisc> { |
| 82 | InductionInfo(InductionClass ic, |
| 83 | InductionOp op, |
| 84 | InductionInfo* a, |
| 85 | InductionInfo* b, |
| 86 | HInstruction* f) |
| 87 | : induction_class(ic), |
| 88 | operation(op), |
| 89 | op_a(a), |
| 90 | op_b(b), |
| 91 | fetch(f) {} |
| 92 | InductionClass induction_class; |
| 93 | InductionOp operation; |
| 94 | InductionInfo* op_a; |
| 95 | InductionInfo* op_b; |
| 96 | HInstruction* fetch; |
| 97 | }; |
| 98 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 99 | bool IsVisitedNode(HInstruction* instruction) const { |
| 100 | return map_.find(instruction) != map_.end(); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 101 | } |
| 102 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 103 | InductionInfo* NewInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) { |
| 104 | DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr); |
| 105 | return new (graph_->GetArena()) InductionInfo(kInvariant, op, a, b, nullptr); |
| 106 | } |
| 107 | |
| 108 | InductionInfo* NewInvariantFetch(HInstruction* f) { |
| 109 | DCHECK(f != nullptr); |
| 110 | return new (graph_->GetArena()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f); |
| 111 | } |
| 112 | |
| 113 | InductionInfo* NewInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) { |
| 114 | DCHECK(a != nullptr && b != nullptr); |
| 115 | return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 116 | } |
| 117 | |
| 118 | // Methods for analysis. |
| 119 | void VisitLoop(HLoopInformation* loop); |
| 120 | void VisitNode(HLoopInformation* loop, HInstruction* instruction); |
| 121 | uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction); |
| 122 | void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction); |
| 123 | void ClassifyNonTrivial(HLoopInformation* loop); |
| 124 | |
| 125 | // Transfer operations. |
| 126 | InductionInfo* TransferPhi(InductionInfo* a, InductionInfo* b); |
| 127 | InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op); |
| 128 | InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 129 | InductionInfo* TransferShl(InductionInfo* a, InductionInfo* b, Primitive::Type t); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 130 | InductionInfo* TransferNeg(InductionInfo* a); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 131 | |
| 132 | // Solvers. |
| 133 | InductionInfo* SolvePhi(HLoopInformation* loop, |
| 134 | HInstruction* phi, |
| 135 | HInstruction* instruction); |
| 136 | InductionInfo* SolveAddSub(HLoopInformation* loop, |
| 137 | HInstruction* phi, |
| 138 | HInstruction* instruction, |
| 139 | HInstruction* x, |
| 140 | HInstruction* y, |
| 141 | InductionOp op, |
| 142 | bool is_first_call); |
| 143 | InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 144 | |
| 145 | // Assign and lookup. |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 146 | void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info); |
| 147 | InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 148 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 149 | // Helpers. |
| 150 | static bool InductionEqual(InductionInfo* info1, InductionInfo* info2); |
| 151 | static std::string InductionToString(InductionInfo* info); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 152 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 153 | // TODO: fine tune the following data structures, only keep relevant data. |
| 154 | |
| 155 | // Temporary book-keeping during the analysis. |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 156 | uint32_t global_depth_; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 157 | ArenaVector<HInstruction*> stack_; |
| 158 | ArenaVector<HInstruction*> scc_; |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 159 | ArenaSafeMap<HInstruction*, NodeInfo> map_; |
| 160 | ArenaSafeMap<HInstruction*, InductionInfo*> cycle_; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 161 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 162 | /** |
| 163 | * Maintains the results of the analysis as a mapping from loops to a mapping from instructions |
| 164 | * to the induction information for that instruction in that loop. |
| 165 | */ |
| 166 | ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 167 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame^] | 168 | friend class InductionVarAnalysisTest; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 169 | |
| 170 | DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis); |
| 171 | }; |
| 172 | |
| 173 | } // namespace art |
| 174 | |
| 175 | #endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_ |