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 | #include "induction_var_analysis.h" |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 18 | #include "induction_var_range.h" |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 19 | |
| 20 | namespace art { |
| 21 | |
| 22 | /** |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 23 | * Since graph traversal may enter a SCC at any position, an initial representation may be rotated, |
| 24 | * along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming |
| 25 | * a chain of dependences (mutual independent items may occur in arbitrary order). For proper |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 26 | * classification, the lexicographically first loop-phi is rotated to the front. |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 27 | */ |
| 28 | static void RotateEntryPhiFirst(HLoopInformation* loop, |
| 29 | ArenaVector<HInstruction*>* scc, |
| 30 | ArenaVector<HInstruction*>* new_scc) { |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 31 | // Find very first loop-phi. |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 32 | const HInstructionList& phis = loop->GetHeader()->GetPhis(); |
| 33 | HInstruction* phi = nullptr; |
| 34 | size_t phi_pos = -1; |
| 35 | const size_t size = scc->size(); |
| 36 | for (size_t i = 0; i < size; i++) { |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 37 | HInstruction* other = (*scc)[i]; |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 38 | if (other->IsLoopHeaderPhi() && (phi == nullptr || phis.FoundBefore(other, phi))) { |
| 39 | phi = other; |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 40 | phi_pos = i; |
| 41 | } |
| 42 | } |
| 43 | |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 44 | // If found, bring that loop-phi to front. |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 45 | if (phi != nullptr) { |
| 46 | new_scc->clear(); |
| 47 | for (size_t i = 0; i < size; i++) { |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 48 | new_scc->push_back((*scc)[phi_pos]); |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 49 | if (++phi_pos >= size) phi_pos = 0; |
| 50 | } |
| 51 | DCHECK_EQ(size, new_scc->size()); |
| 52 | scc->swap(*new_scc); |
| 53 | } |
| 54 | } |
| 55 | |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 56 | /** |
| 57 | * Returns true if the from/to types denote a narrowing, integral conversion (precision loss). |
| 58 | */ |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 59 | static bool IsNarrowingIntegralConversion(DataType::Type from, DataType::Type to) { |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 60 | switch (from) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 61 | case DataType::Type::kInt64: |
Vladimir Marko | d5d2f2c | 2017-09-26 12:37:26 +0100 | [diff] [blame] | 62 | return to == DataType::Type::kUint8 || |
| 63 | to == DataType::Type::kInt8 || |
| 64 | to == DataType::Type::kUint16 || |
| 65 | to == DataType::Type::kInt16 || |
| 66 | to == DataType::Type::kInt32; |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 67 | case DataType::Type::kInt32: |
Vladimir Marko | d5d2f2c | 2017-09-26 12:37:26 +0100 | [diff] [blame] | 68 | return to == DataType::Type::kUint8 || |
| 69 | to == DataType::Type::kInt8 || |
| 70 | to == DataType::Type::kUint16 || |
| 71 | to == DataType::Type::kInt16; |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 72 | case DataType::Type::kUint16: |
| 73 | case DataType::Type::kInt16: |
Vladimir Marko | d5d2f2c | 2017-09-26 12:37:26 +0100 | [diff] [blame] | 74 | return to == DataType::Type::kUint8 || to == DataType::Type::kInt8; |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 75 | default: |
| 76 | return false; |
| 77 | } |
| 78 | } |
| 79 | |
| 80 | /** |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 81 | * Returns result of implicit widening type conversion done in HIR. |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 82 | */ |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 83 | static DataType::Type ImplicitConversion(DataType::Type type) { |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 84 | switch (type) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 85 | case DataType::Type::kBool: |
Vladimir Marko | d5d2f2c | 2017-09-26 12:37:26 +0100 | [diff] [blame] | 86 | case DataType::Type::kUint8: |
| 87 | case DataType::Type::kInt8: |
| 88 | case DataType::Type::kUint16: |
| 89 | case DataType::Type::kInt16: |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 90 | return DataType::Type::kInt32; |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 91 | default: |
| 92 | return type; |
| 93 | } |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 94 | } |
| 95 | |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 96 | // |
| 97 | // Class methods. |
| 98 | // |
| 99 | |
| 100 | HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph) |
| 101 | : HOptimization(graph, kInductionPassName), |
| 102 | global_depth_(0), |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 103 | stack_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 104 | map_(std::less<HInstruction*>(), |
| 105 | graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 106 | scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 107 | cycle_(std::less<HInstruction*>(), |
| 108 | graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 109 | type_(DataType::Type::kVoid), |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 110 | induction_(std::less<HLoopInformation*>(), |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 111 | graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)), |
| 112 | cycles_(std::less<HPhi*>(), |
| 113 | graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)) { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 114 | } |
| 115 | |
| 116 | void HInductionVarAnalysis::Run() { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 117 | // Detects sequence variables (generalized induction variables) during an outer to inner |
| 118 | // traversal of all loops using Gerlek's algorithm. The order is important to enable |
| 119 | // range analysis on outer loop while visiting inner loops. |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 120 | for (HBasicBlock* graph_block : graph_->GetReversePostOrder()) { |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 121 | // Don't analyze irreducible loops. |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 122 | if (graph_block->IsLoopHeader() && !graph_block->GetLoopInformation()->IsIrreducible()) { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 123 | VisitLoop(graph_block->GetLoopInformation()); |
| 124 | } |
| 125 | } |
| 126 | } |
| 127 | |
| 128 | void HInductionVarAnalysis::VisitLoop(HLoopInformation* loop) { |
| 129 | // Find strongly connected components (SSCs) in the SSA graph of this loop using Tarjan's |
| 130 | // algorithm. Due to the descendant-first nature, classification happens "on-demand". |
| 131 | global_depth_ = 0; |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 132 | DCHECK(stack_.empty()); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 133 | map_.clear(); |
| 134 | |
| 135 | for (HBlocksInLoopIterator it_loop(*loop); !it_loop.Done(); it_loop.Advance()) { |
| 136 | HBasicBlock* loop_block = it_loop.Current(); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 137 | DCHECK(loop_block->IsInLoop()); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 138 | if (loop_block->GetLoopInformation() != loop) { |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 139 | continue; // Inner loops visited later. |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 140 | } |
| 141 | // Visit phi-operations and instructions. |
| 142 | for (HInstructionIterator it(loop_block->GetPhis()); !it.Done(); it.Advance()) { |
| 143 | HInstruction* instruction = it.Current(); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 144 | if (!IsVisitedNode(instruction)) { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 145 | VisitNode(loop, instruction); |
| 146 | } |
| 147 | } |
| 148 | for (HInstructionIterator it(loop_block->GetInstructions()); !it.Done(); it.Advance()) { |
| 149 | HInstruction* instruction = it.Current(); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 150 | if (!IsVisitedNode(instruction)) { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 151 | VisitNode(loop, instruction); |
| 152 | } |
| 153 | } |
| 154 | } |
| 155 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 156 | DCHECK(stack_.empty()); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 157 | map_.clear(); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 158 | |
Aart Bik | 7829691 | 2016-03-25 13:14:53 -0700 | [diff] [blame] | 159 | // Determine the loop's trip-count. |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 160 | VisitControl(loop); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 161 | } |
| 162 | |
| 163 | void HInductionVarAnalysis::VisitNode(HLoopInformation* loop, HInstruction* instruction) { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 164 | const uint32_t d1 = ++global_depth_; |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 165 | map_.Put(instruction, NodeInfo(d1)); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 166 | stack_.push_back(instruction); |
| 167 | |
| 168 | // Visit all descendants. |
| 169 | uint32_t low = d1; |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 170 | for (HInstruction* input : instruction->GetInputs()) { |
| 171 | low = std::min(low, VisitDescendant(loop, input)); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 172 | } |
| 173 | |
| 174 | // Lower or found SCC? |
| 175 | if (low < d1) { |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 176 | map_.find(instruction)->second.depth = low; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 177 | } else { |
| 178 | scc_.clear(); |
| 179 | cycle_.clear(); |
| 180 | |
| 181 | // Pop the stack to build the SCC for classification. |
| 182 | while (!stack_.empty()) { |
| 183 | HInstruction* x = stack_.back(); |
| 184 | scc_.push_back(x); |
| 185 | stack_.pop_back(); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 186 | map_.find(x)->second.done = true; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 187 | if (x == instruction) { |
| 188 | break; |
| 189 | } |
| 190 | } |
| 191 | |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 192 | // Type of induction. |
| 193 | type_ = scc_[0]->GetType(); |
| 194 | |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 195 | // Classify the SCC. |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 196 | if (scc_.size() == 1 && !scc_[0]->IsLoopHeaderPhi()) { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 197 | ClassifyTrivial(loop, scc_[0]); |
| 198 | } else { |
| 199 | ClassifyNonTrivial(loop); |
| 200 | } |
| 201 | |
| 202 | scc_.clear(); |
| 203 | cycle_.clear(); |
| 204 | } |
| 205 | } |
| 206 | |
| 207 | uint32_t HInductionVarAnalysis::VisitDescendant(HLoopInformation* loop, HInstruction* instruction) { |
| 208 | // If the definition is either outside the loop (loop invariant entry value) |
| 209 | // or assigned in inner loop (inner exit value), the traversal stops. |
| 210 | HLoopInformation* otherLoop = instruction->GetBlock()->GetLoopInformation(); |
| 211 | if (otherLoop != loop) { |
| 212 | return global_depth_; |
| 213 | } |
| 214 | |
| 215 | // Inspect descendant node. |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 216 | if (!IsVisitedNode(instruction)) { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 217 | VisitNode(loop, instruction); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 218 | return map_.find(instruction)->second.depth; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 219 | } else { |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 220 | auto it = map_.find(instruction); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 221 | return it->second.done ? global_depth_ : it->second.depth; |
| 222 | } |
| 223 | } |
| 224 | |
| 225 | void HInductionVarAnalysis::ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction) { |
| 226 | InductionInfo* info = nullptr; |
| 227 | if (instruction->IsPhi()) { |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 228 | info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 0); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 229 | } else if (instruction->IsAdd()) { |
| 230 | info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)), |
| 231 | LookupInfo(loop, instruction->InputAt(1)), kAdd); |
| 232 | } else if (instruction->IsSub()) { |
| 233 | info = TransferAddSub(LookupInfo(loop, instruction->InputAt(0)), |
| 234 | LookupInfo(loop, instruction->InputAt(1)), kSub); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 235 | } else if (instruction->IsNeg()) { |
| 236 | info = TransferNeg(LookupInfo(loop, instruction->InputAt(0))); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 237 | } else if (instruction->IsMul()) { |
| 238 | info = TransferMul(LookupInfo(loop, instruction->InputAt(0)), |
| 239 | LookupInfo(loop, instruction->InputAt(1))); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 240 | } else if (instruction->IsShl()) { |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 241 | HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 242 | if (mulc != nullptr) { |
| 243 | info = TransferMul(LookupInfo(loop, instruction->InputAt(0)), |
| 244 | LookupInfo(loop, mulc)); |
| 245 | } |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 246 | } else if (instruction->IsSelect()) { |
| 247 | info = TransferPhi(loop, instruction, /*input_index*/ 0, /*adjust_input_size*/ 1); |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 248 | } else if (instruction->IsTypeConversion()) { |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 249 | info = TransferConversion(LookupInfo(loop, instruction->InputAt(0)), |
| 250 | instruction->AsTypeConversion()->GetInputType(), |
| 251 | instruction->AsTypeConversion()->GetResultType()); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 252 | } else if (instruction->IsBoundsCheck()) { |
| 253 | info = LookupInfo(loop, instruction->InputAt(0)); // Pass-through. |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 254 | } |
| 255 | |
| 256 | // Successfully classified? |
| 257 | if (info != nullptr) { |
| 258 | AssignInfo(loop, instruction, info); |
| 259 | } |
| 260 | } |
| 261 | |
| 262 | void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) { |
| 263 | const size_t size = scc_.size(); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 264 | DCHECK_GE(size, 1u); |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 265 | |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 266 | // Rotate proper loop-phi to front. |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 267 | if (size > 1) { |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 268 | ArenaVector<HInstruction*> other(graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)); |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 269 | RotateEntryPhiFirst(loop, &scc_, &other); |
| 270 | } |
| 271 | |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 272 | // Analyze from loop-phi onwards. |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 273 | HInstruction* phi = scc_[0]; |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 274 | if (!phi->IsLoopHeaderPhi()) { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 275 | return; |
| 276 | } |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 277 | |
| 278 | // External link should be loop invariant. |
| 279 | InductionInfo* initial = LookupInfo(loop, phi->InputAt(0)); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 280 | if (initial == nullptr || initial->induction_class != kInvariant) { |
| 281 | return; |
| 282 | } |
| 283 | |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 284 | // Store interesting cycle in each loop phi. |
| 285 | for (size_t i = 0; i < size; i++) { |
| 286 | if (scc_[i]->IsLoopHeaderPhi()) { |
| 287 | AssignCycle(scc_[i]->AsPhi()); |
| 288 | } |
| 289 | } |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 290 | |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 291 | // Singleton is wrap-around induction if all internal links have the same meaning. |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 292 | if (size == 1) { |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 293 | InductionInfo* update = TransferPhi(loop, phi, /*input_index*/ 1, /*adjust_input_size*/ 0); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 294 | if (update != nullptr) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 295 | AssignInfo(loop, phi, CreateInduction(kWrapAround, |
| 296 | kNop, |
| 297 | initial, |
| 298 | update, |
| 299 | /*fetch*/ nullptr, |
| 300 | type_)); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 301 | } |
| 302 | return; |
| 303 | } |
| 304 | |
| 305 | // Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 306 | // temporary meaning to its nodes, seeded from the phi instruction and back. |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 307 | for (size_t i = 1; i < size; i++) { |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 308 | HInstruction* instruction = scc_[i]; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 309 | InductionInfo* update = nullptr; |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 310 | if (instruction->IsPhi()) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 311 | update = SolvePhiAllInputs(loop, phi, instruction); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 312 | } else if (instruction->IsAdd()) { |
| 313 | update = SolveAddSub( |
| 314 | loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kAdd, true); |
| 315 | } else if (instruction->IsSub()) { |
| 316 | update = SolveAddSub( |
| 317 | loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kSub, true); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 318 | } else if (instruction->IsMul()) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 319 | update = SolveOp( |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 320 | loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kMul); |
| 321 | } else if (instruction->IsDiv()) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 322 | update = SolveOp( |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 323 | loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kDiv); |
| 324 | } else if (instruction->IsRem()) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 325 | update = SolveOp( |
| 326 | loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kRem); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 327 | } else if (instruction->IsShl()) { |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 328 | HInstruction* mulc = GetShiftConstant(loop, instruction, /*initial*/ nullptr); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 329 | if (mulc != nullptr) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 330 | update = SolveOp(loop, phi, instruction, instruction->InputAt(0), mulc, kMul); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 331 | } |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 332 | } else if (instruction->IsShr() || instruction->IsUShr()) { |
| 333 | HInstruction* divc = GetShiftConstant(loop, instruction, initial); |
| 334 | if (divc != nullptr) { |
| 335 | update = SolveOp(loop, phi, instruction, instruction->InputAt(0), divc, kDiv); |
| 336 | } |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 337 | } else if (instruction->IsXor()) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 338 | update = SolveOp( |
| 339 | loop, phi, instruction, instruction->InputAt(0), instruction->InputAt(1), kXor); |
Aart Bik | 639cc8c | 2016-10-18 13:03:31 -0700 | [diff] [blame] | 340 | } else if (instruction->IsEqual()) { |
| 341 | update = SolveTest(loop, phi, instruction, 0); |
| 342 | } else if (instruction->IsNotEqual()) { |
| 343 | update = SolveTest(loop, phi, instruction, 1); |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 344 | } else if (instruction->IsSelect()) { |
| 345 | update = SolvePhi(instruction, /*input_index*/ 0, /*adjust_input_size*/ 1); // acts like Phi |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 346 | } else if (instruction->IsTypeConversion()) { |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 347 | update = SolveConversion(loop, phi, instruction->AsTypeConversion()); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 348 | } |
| 349 | if (update == nullptr) { |
| 350 | return; |
| 351 | } |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 352 | cycle_.Put(instruction, update); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 353 | } |
| 354 | |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 355 | // Success if all internal links received the same temporary meaning. |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 356 | InductionInfo* induction = SolvePhi(phi, /*input_index*/ 1, /*adjust_input_size*/ 0); |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 357 | if (induction != nullptr) { |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 358 | switch (induction->induction_class) { |
| 359 | case kInvariant: |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 360 | // Construct combined stride of the linear induction. |
| 361 | induction = CreateInduction(kLinear, kNop, induction, initial, /*fetch*/ nullptr, type_); |
| 362 | FALLTHROUGH_INTENDED; |
| 363 | case kPolynomial: |
| 364 | case kGeometric: |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 365 | case kWrapAround: |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 366 | // Classify first phi and then the rest of the cycle "on-demand". |
| 367 | // Statements are scanned in order. |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 368 | AssignInfo(loop, phi, induction); |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 369 | for (size_t i = 1; i < size; i++) { |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 370 | ClassifyTrivial(loop, scc_[i]); |
| 371 | } |
| 372 | break; |
| 373 | case kPeriodic: |
Aart Bik | 22af3be | 2015-09-10 12:50:58 -0700 | [diff] [blame] | 374 | // Classify all elements in the cycle with the found periodic induction while |
| 375 | // rotating each first element to the end. Lastly, phi is classified. |
| 376 | // Statements are scanned in reverse order. |
| 377 | for (size_t i = size - 1; i >= 1; i--) { |
| 378 | AssignInfo(loop, scc_[i], induction); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 379 | induction = RotatePeriodicInduction(induction->op_b, induction->op_a); |
| 380 | } |
| 381 | AssignInfo(loop, phi, induction); |
| 382 | break; |
| 383 | default: |
| 384 | break; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 385 | } |
| 386 | } |
| 387 | } |
| 388 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 389 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::RotatePeriodicInduction( |
| 390 | InductionInfo* induction, |
| 391 | InductionInfo* last) { |
| 392 | // Rotates a periodic induction of the form |
| 393 | // (a, b, c, d, e) |
| 394 | // into |
| 395 | // (b, c, d, e, a) |
| 396 | // in preparation of assigning this to the previous variable in the sequence. |
| 397 | if (induction->induction_class == kInvariant) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 398 | return CreateInduction(kPeriodic, |
| 399 | kNop, |
| 400 | induction, |
| 401 | last, |
| 402 | /*fetch*/ nullptr, |
| 403 | type_); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 404 | } |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 405 | return CreateInduction(kPeriodic, |
| 406 | kNop, |
| 407 | induction->op_a, |
| 408 | RotatePeriodicInduction(induction->op_b, last), |
| 409 | /*fetch*/ nullptr, |
| 410 | type_); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 411 | } |
| 412 | |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 413 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferPhi(HLoopInformation* loop, |
| 414 | HInstruction* phi, |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 415 | size_t input_index, |
| 416 | size_t adjust_input_size) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 417 | // Match all phi inputs from input_index onwards exactly. |
Vladimir Marko | e900491 | 2016-06-16 16:50:52 +0100 | [diff] [blame] | 418 | HInputsRef inputs = phi->GetInputs(); |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 419 | DCHECK_LT(input_index, inputs.size()); |
| 420 | InductionInfo* a = LookupInfo(loop, inputs[input_index]); |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 421 | for (size_t i = input_index + 1, n = inputs.size() - adjust_input_size; i < n; i++) { |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 422 | InductionInfo* b = LookupInfo(loop, inputs[i]); |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 423 | if (!InductionEqual(a, b)) { |
| 424 | return nullptr; |
| 425 | } |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 426 | } |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 427 | return a; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 428 | } |
| 429 | |
| 430 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferAddSub(InductionInfo* a, |
| 431 | InductionInfo* b, |
| 432 | InductionOp op) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 433 | // Transfer over an addition or subtraction: any invariant, linear, polynomial, geometric, |
| 434 | // wrap-around, or periodic can be combined with an invariant to yield a similar result. |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 435 | // Two linear or two polynomial inputs can be combined too. Other combinations fail. |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 436 | if (a != nullptr && b != nullptr) { |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 437 | if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) { |
| 438 | return nullptr; // no transfer |
| 439 | } else if (a->induction_class == kInvariant && b->induction_class == kInvariant) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 440 | return CreateInvariantOp(op, a, b); // direct invariant |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 441 | } else if ((a->induction_class == kLinear && b->induction_class == kLinear) || |
| 442 | (a->induction_class == kPolynomial && b->induction_class == kPolynomial)) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 443 | // Rule induc(a, b) + induc(a', b') -> induc(a + a', b + b'). |
| 444 | InductionInfo* new_a = TransferAddSub(a->op_a, b->op_a, op); |
| 445 | InductionInfo* new_b = TransferAddSub(a->op_b, b->op_b, op); |
| 446 | if (new_a != nullptr && new_b != nullptr) { |
| 447 | return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_); |
| 448 | } |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 449 | } else if (a->induction_class == kInvariant) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 450 | // Rule a + induc(a', b') -> induc(a', a + b') or induc(a + a', a + b'). |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 451 | InductionInfo* new_a = b->op_a; |
| 452 | InductionInfo* new_b = TransferAddSub(a, b->op_b, op); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 453 | if (b->induction_class == kWrapAround || b->induction_class == kPeriodic) { |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 454 | new_a = TransferAddSub(a, new_a, op); |
| 455 | } else if (op == kSub) { // Negation required. |
| 456 | new_a = TransferNeg(new_a); |
| 457 | } |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 458 | if (new_a != nullptr && new_b != nullptr) { |
| 459 | return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type_); |
| 460 | } |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 461 | } else if (b->induction_class == kInvariant) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 462 | // Rule induc(a, b) + b' -> induc(a, b + b') or induc(a + b', b + b'). |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 463 | InductionInfo* new_a = a->op_a; |
| 464 | InductionInfo* new_b = TransferAddSub(a->op_b, b, op); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 465 | if (a->induction_class == kWrapAround || a->induction_class == kPeriodic) { |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 466 | new_a = TransferAddSub(new_a, b, op); |
| 467 | } |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 468 | if (new_a != nullptr && new_b != nullptr) { |
| 469 | return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_); |
| 470 | } |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 471 | } |
| 472 | } |
| 473 | return nullptr; |
| 474 | } |
| 475 | |
| 476 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferNeg(InductionInfo* a) { |
| 477 | // Transfer over a unary negation: an invariant, linear, polynomial, geometric (mul), |
| 478 | // wrap-around, or periodic input yields a similar but negated induction as result. |
| 479 | if (a != nullptr) { |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 480 | if (IsNarrowingLinear(a)) { |
| 481 | return nullptr; // no transfer |
| 482 | } else if (a->induction_class == kInvariant) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 483 | return CreateInvariantOp(kNeg, nullptr, a); // direct invariant |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 484 | } else if (a->induction_class != kGeometric || a->operation == kMul) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 485 | // Rule - induc(a, b) -> induc(-a, -b). |
| 486 | InductionInfo* new_a = TransferNeg(a->op_a); |
| 487 | InductionInfo* new_b = TransferNeg(a->op_b); |
| 488 | if (new_a != nullptr && new_b != nullptr) { |
| 489 | return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_); |
| 490 | } |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 491 | } |
| 492 | } |
| 493 | return nullptr; |
| 494 | } |
| 495 | |
| 496 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferMul(InductionInfo* a, |
| 497 | InductionInfo* b) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 498 | // Transfer over a multiplication: any invariant, linear, polynomial, geometric (mul), |
| 499 | // wrap-around, or periodic can be multiplied with an invariant to yield a similar |
| 500 | // but multiplied result. Two non-invariant inputs cannot be multiplied, however. |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 501 | if (a != nullptr && b != nullptr) { |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 502 | if (IsNarrowingLinear(a) || IsNarrowingLinear(b)) { |
| 503 | return nullptr; // no transfer |
| 504 | } else if (a->induction_class == kInvariant && b->induction_class == kInvariant) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 505 | return CreateInvariantOp(kMul, a, b); // direct invariant |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 506 | } else if (a->induction_class == kInvariant && (b->induction_class != kGeometric || |
| 507 | b->operation == kMul)) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 508 | // Rule a * induc(a', b') -> induc(a * a', b * b'). |
| 509 | InductionInfo* new_a = TransferMul(a, b->op_a); |
| 510 | InductionInfo* new_b = TransferMul(a, b->op_b); |
| 511 | if (new_a != nullptr && new_b != nullptr) { |
| 512 | return CreateInduction(b->induction_class, b->operation, new_a, new_b, b->fetch, type_); |
| 513 | } |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 514 | } else if (b->induction_class == kInvariant && (a->induction_class != kGeometric || |
| 515 | a->operation == kMul)) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 516 | // Rule induc(a, b) * b' -> induc(a * b', b * b'). |
| 517 | InductionInfo* new_a = TransferMul(a->op_a, b); |
| 518 | InductionInfo* new_b = TransferMul(a->op_b, b); |
| 519 | if (new_a != nullptr && new_b != nullptr) { |
| 520 | return CreateInduction(a->induction_class, a->operation, new_a, new_b, a->fetch, type_); |
| 521 | } |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 522 | } |
| 523 | } |
| 524 | return nullptr; |
| 525 | } |
| 526 | |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 527 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::TransferConversion( |
| 528 | InductionInfo* a, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 529 | DataType::Type from, |
| 530 | DataType::Type to) { |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 531 | if (a != nullptr) { |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 532 | // Allow narrowing conversion on linear induction in certain cases: |
| 533 | // induction is already at narrow type, or can be made narrower. |
| 534 | if (IsNarrowingIntegralConversion(from, to) && |
| 535 | a->induction_class == kLinear && |
| 536 | (a->type == to || IsNarrowingIntegralConversion(a->type, to))) { |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 537 | return CreateInduction(kLinear, kNop, a->op_a, a->op_b, a->fetch, to); |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 538 | } |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 539 | } |
| 540 | return nullptr; |
| 541 | } |
| 542 | |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 543 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhi(HInstruction* phi, |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 544 | size_t input_index, |
| 545 | size_t adjust_input_size) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 546 | // Match all phi inputs from input_index onwards exactly. |
Vladimir Marko | e900491 | 2016-06-16 16:50:52 +0100 | [diff] [blame] | 547 | HInputsRef inputs = phi->GetInputs(); |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 548 | DCHECK_LT(input_index, inputs.size()); |
| 549 | auto ita = cycle_.find(inputs[input_index]); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 550 | if (ita != cycle_.end()) { |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 551 | for (size_t i = input_index + 1, n = inputs.size() - adjust_input_size; i < n; i++) { |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 552 | auto itb = cycle_.find(inputs[i]); |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 553 | if (itb == cycle_.end() || |
| 554 | !HInductionVarAnalysis::InductionEqual(ita->second, itb->second)) { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 555 | return nullptr; |
| 556 | } |
| 557 | } |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 558 | return ita->second; |
| 559 | } |
| 560 | return nullptr; |
| 561 | } |
| 562 | |
| 563 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolvePhiAllInputs( |
| 564 | HLoopInformation* loop, |
| 565 | HInstruction* entry_phi, |
| 566 | HInstruction* phi) { |
| 567 | // Match all phi inputs. |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 568 | InductionInfo* match = SolvePhi(phi, /*input_index*/ 0, /*adjust_input_size*/ 0); |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 569 | if (match != nullptr) { |
| 570 | return match; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 571 | } |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 572 | |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 573 | // Otherwise, try to solve for a periodic seeded from phi onward. |
| 574 | // Only tight multi-statement cycles are considered in order to |
| 575 | // simplify rotating the periodic during the final classification. |
| 576 | if (phi->IsLoopHeaderPhi() && phi->InputCount() == 2) { |
| 577 | InductionInfo* a = LookupInfo(loop, phi->InputAt(0)); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 578 | if (a != nullptr && a->induction_class == kInvariant) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 579 | if (phi->InputAt(1) == entry_phi) { |
| 580 | InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 581 | return CreateInduction(kPeriodic, kNop, a, initial, /*fetch*/ nullptr, type_); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 582 | } |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 583 | InductionInfo* b = SolvePhi(phi, /*input_index*/ 1, /*adjust_input_size*/ 0); |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 584 | if (b != nullptr && b->induction_class == kPeriodic) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 585 | return CreateInduction(kPeriodic, kNop, a, b, /*fetch*/ nullptr, type_); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 586 | } |
| 587 | } |
| 588 | } |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 589 | return nullptr; |
| 590 | } |
| 591 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 592 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveAddSub(HLoopInformation* loop, |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 593 | HInstruction* entry_phi, |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 594 | HInstruction* instruction, |
| 595 | HInstruction* x, |
| 596 | HInstruction* y, |
| 597 | InductionOp op, |
| 598 | bool is_first_call) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 599 | // Solve within a cycle over an addition or subtraction. |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 600 | InductionInfo* b = LookupInfo(loop, y); |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 601 | if (b != nullptr) { |
| 602 | if (b->induction_class == kInvariant) { |
| 603 | // Adding or subtracting an invariant value, seeded from phi, |
| 604 | // keeps adding to the stride of the linear induction. |
| 605 | if (x == entry_phi) { |
| 606 | return (op == kAdd) ? b : CreateInvariantOp(kNeg, nullptr, b); |
| 607 | } |
| 608 | auto it = cycle_.find(x); |
| 609 | if (it != cycle_.end()) { |
| 610 | InductionInfo* a = it->second; |
| 611 | if (a->induction_class == kInvariant) { |
| 612 | return CreateInvariantOp(op, a, b); |
| 613 | } |
| 614 | } |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 615 | } else if (b->induction_class == kLinear && b->type == type_) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 616 | // Solve within a tight cycle that adds a term that is already classified as a linear |
| 617 | // induction for a polynomial induction k = k + i (represented as sum over linear terms). |
| 618 | if (x == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { |
| 619 | InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); |
Aart Bik | 74da529 | 2016-12-20 11:13:03 -0800 | [diff] [blame] | 620 | InductionInfo* new_a = op == kAdd ? b : TransferNeg(b); |
| 621 | if (new_a != nullptr) { |
| 622 | return CreateInduction(kPolynomial, kNop, new_a, initial, /*fetch*/ nullptr, type_); |
| 623 | } |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 624 | } |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 625 | } |
| 626 | } |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 627 | |
| 628 | // Try some alternatives before failing. |
| 629 | if (op == kAdd) { |
| 630 | // Try the other way around for an addition if considered for first time. |
| 631 | if (is_first_call) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 632 | return SolveAddSub(loop, entry_phi, instruction, y, x, op, false); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 633 | } |
| 634 | } else if (op == kSub) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 635 | // Solve within a tight cycle that is formed by exactly two instructions, |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 636 | // one phi and one update, for a periodic idiom of the form k = c - k. |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 637 | if (y == entry_phi && entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 638 | InductionInfo* a = LookupInfo(loop, x); |
| 639 | if (a != nullptr && a->induction_class == kInvariant) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 640 | InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 641 | return CreateInduction(kPeriodic, |
| 642 | kNop, |
| 643 | CreateInvariantOp(kSub, a, initial), |
| 644 | initial, |
| 645 | /*fetch*/ nullptr, |
| 646 | type_); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 647 | } |
| 648 | } |
| 649 | } |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 650 | return nullptr; |
| 651 | } |
| 652 | |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 653 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveOp(HLoopInformation* loop, |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 654 | HInstruction* entry_phi, |
| 655 | HInstruction* instruction, |
| 656 | HInstruction* x, |
| 657 | HInstruction* y, |
| 658 | InductionOp op) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 659 | // Solve within a tight cycle for a binary operation k = k op c or, for some op, k = c op k. |
Aart Bik | 639cc8c | 2016-10-18 13:03:31 -0700 | [diff] [blame] | 660 | if (entry_phi->InputCount() == 2 && instruction == entry_phi->InputAt(1)) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 661 | InductionInfo* c = nullptr; |
Aart Bik | 639cc8c | 2016-10-18 13:03:31 -0700 | [diff] [blame] | 662 | InductionInfo* b = LookupInfo(loop, y); |
| 663 | if (b != nullptr && b->induction_class == kInvariant && entry_phi == x) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 664 | c = b; |
| 665 | } else if (op != kDiv && op != kRem) { |
| 666 | InductionInfo* a = LookupInfo(loop, x); |
| 667 | if (a != nullptr && a->induction_class == kInvariant && entry_phi == y) { |
| 668 | c = a; |
| 669 | } |
| 670 | } |
| 671 | // Found suitable operand left or right? |
| 672 | if (c != nullptr) { |
| 673 | InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); |
| 674 | switch (op) { |
| 675 | case kMul: |
| 676 | case kDiv: |
| 677 | // Restrict base of geometric induction to direct fetch. |
| 678 | if (c->operation == kFetch) { |
| 679 | return CreateInduction(kGeometric, |
| 680 | op, |
| 681 | initial, |
| 682 | CreateConstant(0, type_), |
| 683 | c->fetch, |
| 684 | type_); |
| 685 | }; |
| 686 | break; |
| 687 | case kRem: |
| 688 | // Idiomatic MOD wrap-around induction. |
| 689 | return CreateInduction(kWrapAround, |
| 690 | kNop, |
| 691 | initial, |
| 692 | CreateInvariantOp(kRem, initial, c), |
| 693 | /*fetch*/ nullptr, |
| 694 | type_); |
| 695 | case kXor: |
| 696 | // Idiomatic XOR periodic induction. |
| 697 | return CreateInduction(kPeriodic, |
| 698 | kNop, |
| 699 | CreateInvariantOp(kXor, initial, c), |
| 700 | initial, |
| 701 | /*fetch*/ nullptr, |
| 702 | type_); |
| 703 | default: |
Andreas Gampe | f45d61c | 2017-06-07 10:29:33 -0700 | [diff] [blame] | 704 | LOG(FATAL) << op; |
| 705 | UNREACHABLE(); |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 706 | } |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 707 | } |
| 708 | } |
Aart Bik | 639cc8c | 2016-10-18 13:03:31 -0700 | [diff] [blame] | 709 | return nullptr; |
| 710 | } |
| 711 | |
| 712 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveTest(HLoopInformation* loop, |
| 713 | HInstruction* entry_phi, |
| 714 | HInstruction* instruction, |
| 715 | int64_t opposite_value) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 716 | // Detect hidden XOR construction in x = (x == false) or x = (x != true). |
Aart Bik | 639cc8c | 2016-10-18 13:03:31 -0700 | [diff] [blame] | 717 | int64_t value = -1; |
| 718 | HInstruction* x = instruction->InputAt(0); |
| 719 | HInstruction* y = instruction->InputAt(1); |
| 720 | if (IsExact(LookupInfo(loop, x), &value) && value == opposite_value) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 721 | return SolveOp(loop, entry_phi, instruction, graph_->GetIntConstant(1), y, kXor); |
Aart Bik | 639cc8c | 2016-10-18 13:03:31 -0700 | [diff] [blame] | 722 | } else if (IsExact(LookupInfo(loop, y), &value) && value == opposite_value) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 723 | return SolveOp(loop, entry_phi, instruction, x, graph_->GetIntConstant(1), kXor); |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 724 | } |
| 725 | return nullptr; |
| 726 | } |
| 727 | |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 728 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::SolveConversion( |
| 729 | HLoopInformation* loop, |
| 730 | HInstruction* entry_phi, |
| 731 | HTypeConversion* conversion) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 732 | DataType::Type from = conversion->GetInputType(); |
| 733 | DataType::Type to = conversion->GetResultType(); |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 734 | // A narrowing conversion is allowed as *last* operation of the cycle of a linear induction |
| 735 | // with an initial value that fits the type, provided that the narrowest encountered type is |
| 736 | // recorded with the induction to account for the precision loss. The narrower induction does |
| 737 | // *not* transfer to any wider operations, however, since these may yield out-of-type values |
| 738 | if (entry_phi->InputCount() == 2 && conversion == entry_phi->InputAt(1)) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 739 | int64_t min = DataType::MinValueOfIntegralType(to); |
| 740 | int64_t max = DataType::MaxValueOfIntegralType(to); |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 741 | int64_t value = 0; |
| 742 | InductionInfo* initial = LookupInfo(loop, entry_phi->InputAt(0)); |
| 743 | if (IsNarrowingIntegralConversion(from, to) && |
| 744 | IsAtLeast(initial, &value) && value >= min && |
| 745 | IsAtMost(initial, &value) && value <= max) { |
| 746 | auto it = cycle_.find(conversion->GetInput()); |
| 747 | if (it != cycle_.end() && it->second->induction_class == kInvariant) { |
| 748 | type_ = to; |
| 749 | return it->second; |
| 750 | } |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 751 | } |
| 752 | } |
| 753 | return nullptr; |
| 754 | } |
| 755 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 756 | void HInductionVarAnalysis::VisitControl(HLoopInformation* loop) { |
| 757 | HInstruction* control = loop->GetHeader()->GetLastInstruction(); |
| 758 | if (control->IsIf()) { |
| 759 | HIf* ifs = control->AsIf(); |
| 760 | HBasicBlock* if_true = ifs->IfTrueSuccessor(); |
| 761 | HBasicBlock* if_false = ifs->IfFalseSuccessor(); |
| 762 | HInstruction* if_expr = ifs->InputAt(0); |
| 763 | // Determine if loop has following structure in header. |
| 764 | // loop-header: .... |
| 765 | // if (condition) goto X |
| 766 | if (if_expr->IsCondition()) { |
| 767 | HCondition* condition = if_expr->AsCondition(); |
| 768 | InductionInfo* a = LookupInfo(loop, condition->InputAt(0)); |
| 769 | InductionInfo* b = LookupInfo(loop, condition->InputAt(1)); |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 770 | DataType::Type type = ImplicitConversion(condition->InputAt(0)->GetType()); |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 771 | // Determine if the loop control uses a known sequence on an if-exit (X outside) or on |
| 772 | // an if-iterate (X inside), expressed as if-iterate when passed into VisitCondition(). |
| 773 | if (a == nullptr || b == nullptr) { |
| 774 | return; // Loop control is not a sequence. |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 775 | } else if (if_true->GetLoopInformation() != loop && if_false->GetLoopInformation() == loop) { |
| 776 | VisitCondition(loop, a, b, type, condition->GetOppositeCondition()); |
| 777 | } else if (if_true->GetLoopInformation() == loop && if_false->GetLoopInformation() != loop) { |
| 778 | VisitCondition(loop, a, b, type, condition->GetCondition()); |
| 779 | } |
| 780 | } |
| 781 | } |
| 782 | } |
| 783 | |
| 784 | void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop, |
| 785 | InductionInfo* a, |
| 786 | InductionInfo* b, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 787 | DataType::Type type, |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 788 | IfCondition cmp) { |
| 789 | if (a->induction_class == kInvariant && b->induction_class == kLinear) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 790 | // Swap condition if induction is at right-hand-side (e.g. U > i is same as i < U). |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 791 | switch (cmp) { |
| 792 | case kCondLT: VisitCondition(loop, b, a, type, kCondGT); break; |
| 793 | case kCondLE: VisitCondition(loop, b, a, type, kCondGE); break; |
| 794 | case kCondGT: VisitCondition(loop, b, a, type, kCondLT); break; |
| 795 | case kCondGE: VisitCondition(loop, b, a, type, kCondLE); break; |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 796 | case kCondNE: VisitCondition(loop, b, a, type, kCondNE); break; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 797 | default: break; |
| 798 | } |
| 799 | } else if (a->induction_class == kLinear && b->induction_class == kInvariant) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 800 | // Analyze condition with induction at left-hand-side (e.g. i < U). |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 801 | InductionInfo* lower_expr = a->op_b; |
| 802 | InductionInfo* upper_expr = b; |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 803 | InductionInfo* stride_expr = a->op_a; |
| 804 | // Constant stride? |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 805 | int64_t stride_value = 0; |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 806 | if (!IsExact(stride_expr, &stride_value)) { |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 807 | return; |
| 808 | } |
Aart Bik | 358af83 | 2016-02-24 14:17:53 -0800 | [diff] [blame] | 809 | // Rewrite condition i != U into strict end condition i < U or i > U if this end condition |
| 810 | // is reached exactly (tested by verifying if the loop has a unit stride and the non-strict |
| 811 | // condition would be always taken). |
| 812 | if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLE)) || |
| 813 | (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGE)))) { |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 814 | cmp = stride_value > 0 ? kCondLT : kCondGT; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 815 | } |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 816 | // Only accept integral condition. A mismatch between the type of condition and the induction |
| 817 | // is only allowed if the, necessarily narrower, induction range fits the narrower control. |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 818 | if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) { |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 819 | return; // not integral |
| 820 | } else if (type != a->type && |
| 821 | !FitsNarrowerControl(lower_expr, upper_expr, stride_value, a->type, cmp)) { |
| 822 | return; // mismatched type |
| 823 | } |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 824 | // Normalize a linear loop control with a nonzero stride: |
| 825 | // stride > 0, either i < U or i <= U |
| 826 | // stride < 0, either i > U or i >= U |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 827 | if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) || |
| 828 | (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) { |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 829 | VisitTripCount(loop, lower_expr, upper_expr, stride_expr, stride_value, type, cmp); |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 830 | } |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 831 | } |
| 832 | } |
| 833 | |
| 834 | void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop, |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 835 | InductionInfo* lower_expr, |
| 836 | InductionInfo* upper_expr, |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 837 | InductionInfo* stride_expr, |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 838 | int64_t stride_value, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 839 | DataType::Type type, |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 840 | IfCondition cmp) { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 841 | // Any loop of the general form: |
| 842 | // |
| 843 | // for (i = L; i <= U; i += S) // S > 0 |
| 844 | // or for (i = L; i >= U; i += S) // S < 0 |
| 845 | // .. i .. |
| 846 | // |
| 847 | // can be normalized into: |
| 848 | // |
| 849 | // for (n = 0; n < TC; n++) // where TC = (U + S - L) / S |
| 850 | // .. L + S * n .. |
| 851 | // |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 852 | // taking the following into consideration: |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 853 | // |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 854 | // (1) Using the same precision, the TC (trip-count) expression should be interpreted as |
| 855 | // an unsigned entity, for example, as in the following loop that uses the full range: |
| 856 | // for (int i = INT_MIN; i < INT_MAX; i++) // TC = UINT_MAX |
| 857 | // (2) The TC is only valid if the loop is taken, otherwise TC = 0, as in: |
Aart Bik | d5cc683 | 2016-06-22 16:34:46 -0700 | [diff] [blame] | 858 | // for (int i = 12; i < U; i++) // TC = 0 when U <= 12 |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 859 | // If this cannot be determined at compile-time, the TC is only valid within the |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 860 | // loop-body proper, not the loop-header unless enforced with an explicit taken-test. |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 861 | // (3) The TC is only valid if the loop is finite, otherwise TC has no value, as in: |
| 862 | // for (int i = 0; i <= U; i++) // TC = Inf when U = INT_MAX |
| 863 | // If this cannot be determined at compile-time, the TC is only valid when enforced |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 864 | // with an explicit finite-test. |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 865 | // (4) For loops which early-exits, the TC forms an upper bound, as in: |
| 866 | // for (int i = 0; i < 10 && ....; i++) // TC <= 10 |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 867 | InductionInfo* trip_count = upper_expr; |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 868 | const bool is_taken = IsTaken(lower_expr, upper_expr, cmp); |
| 869 | const bool is_finite = IsFinite(upper_expr, stride_value, type, cmp); |
| 870 | const bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 871 | if (!cancels) { |
| 872 | // Convert exclusive integral inequality into inclusive integral inequality, |
| 873 | // viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1. |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 874 | if (cmp == kCondLT) { |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 875 | trip_count = CreateInvariantOp(kSub, trip_count, CreateConstant(1, type)); |
Aart Bik | f475bee | 2015-09-16 12:50:25 -0700 | [diff] [blame] | 876 | } else if (cmp == kCondGT) { |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 877 | trip_count = CreateInvariantOp(kAdd, trip_count, CreateConstant(1, type)); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 878 | } |
| 879 | // Compensate for stride. |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 880 | trip_count = CreateInvariantOp(kAdd, trip_count, stride_expr); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 881 | } |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 882 | trip_count = CreateInvariantOp( |
| 883 | kDiv, CreateInvariantOp(kSub, trip_count, lower_expr), stride_expr); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 884 | // Assign the trip-count expression to the loop control. Clients that use the information |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 885 | // should be aware that the expression is only valid under the conditions listed above. |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 886 | InductionOp tcKind = kTripCountInBodyUnsafe; // needs both tests |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 887 | if (is_taken && is_finite) { |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 888 | tcKind = kTripCountInLoop; // needs neither test |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 889 | } else if (is_finite) { |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 890 | tcKind = kTripCountInBody; // needs taken-test |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 891 | } else if (is_taken) { |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 892 | tcKind = kTripCountInLoopUnsafe; // needs finite-test |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 893 | } |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 894 | InductionOp op = kNop; |
| 895 | switch (cmp) { |
| 896 | case kCondLT: op = kLT; break; |
| 897 | case kCondLE: op = kLE; break; |
| 898 | case kCondGT: op = kGT; break; |
| 899 | case kCondGE: op = kGE; break; |
| 900 | default: LOG(FATAL) << "CONDITION UNREACHABLE"; |
| 901 | } |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 902 | // Associate trip count with control instruction, rather than the condition (even |
| 903 | // though it's its use) since former provides a convenient use-free placeholder. |
| 904 | HInstruction* control = loop->GetHeader()->GetLastInstruction(); |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 905 | InductionInfo* taken_test = CreateInvariantOp(op, lower_expr, upper_expr); |
Aart Bik | 009cace | 2016-09-16 10:15:19 -0700 | [diff] [blame] | 906 | DCHECK(control->IsIf()); |
| 907 | AssignInfo(loop, control, CreateTripCount(tcKind, trip_count, taken_test, type)); |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 908 | } |
| 909 | |
| 910 | bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr, |
| 911 | InductionInfo* upper_expr, |
| 912 | IfCondition cmp) { |
| 913 | int64_t lower_value; |
| 914 | int64_t upper_value; |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 915 | switch (cmp) { |
| 916 | case kCondLT: |
| 917 | return IsAtMost(lower_expr, &lower_value) |
| 918 | && IsAtLeast(upper_expr, &upper_value) |
| 919 | && lower_value < upper_value; |
| 920 | case kCondLE: |
| 921 | return IsAtMost(lower_expr, &lower_value) |
| 922 | && IsAtLeast(upper_expr, &upper_value) |
| 923 | && lower_value <= upper_value; |
| 924 | case kCondGT: |
| 925 | return IsAtLeast(lower_expr, &lower_value) |
| 926 | && IsAtMost(upper_expr, &upper_value) |
| 927 | && lower_value > upper_value; |
| 928 | case kCondGE: |
| 929 | return IsAtLeast(lower_expr, &lower_value) |
| 930 | && IsAtMost(upper_expr, &upper_value) |
| 931 | && lower_value >= upper_value; |
| 932 | default: |
| 933 | LOG(FATAL) << "CONDITION UNREACHABLE"; |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 934 | } |
| 935 | return false; // not certain, may be untaken |
| 936 | } |
| 937 | |
| 938 | bool HInductionVarAnalysis::IsFinite(InductionInfo* upper_expr, |
| 939 | int64_t stride_value, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 940 | DataType::Type type, |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 941 | IfCondition cmp) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 942 | int64_t min = DataType::MinValueOfIntegralType(type); |
| 943 | int64_t max = DataType::MaxValueOfIntegralType(type); |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 944 | // Some rules under which it is certain at compile-time that the loop is finite. |
| 945 | int64_t value; |
| 946 | switch (cmp) { |
| 947 | case kCondLT: |
| 948 | return stride_value == 1 || |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 949 | (IsAtMost(upper_expr, &value) && value <= (max - stride_value + 1)); |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 950 | case kCondLE: |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 951 | return (IsAtMost(upper_expr, &value) && value <= (max - stride_value)); |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 952 | case kCondGT: |
| 953 | return stride_value == -1 || |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 954 | (IsAtLeast(upper_expr, &value) && value >= (min - stride_value - 1)); |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 955 | case kCondGE: |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 956 | return (IsAtLeast(upper_expr, &value) && value >= (min - stride_value)); |
Aart Bik | e9f3760 | 2015-10-09 11:15:55 -0700 | [diff] [blame] | 957 | default: |
| 958 | LOG(FATAL) << "CONDITION UNREACHABLE"; |
Aart Bik | 9401f53 | 2015-09-28 16:25:56 -0700 | [diff] [blame] | 959 | } |
| 960 | return false; // not certain, may be infinite |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 961 | } |
| 962 | |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 963 | bool HInductionVarAnalysis::FitsNarrowerControl(InductionInfo* lower_expr, |
| 964 | InductionInfo* upper_expr, |
| 965 | int64_t stride_value, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 966 | DataType::Type type, |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 967 | IfCondition cmp) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 968 | int64_t min = DataType::MinValueOfIntegralType(type); |
| 969 | int64_t max = DataType::MaxValueOfIntegralType(type); |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 970 | // Inclusive test need one extra. |
| 971 | if (stride_value != 1 && stride_value != -1) { |
| 972 | return false; // non-unit stride |
| 973 | } else if (cmp == kCondLE) { |
| 974 | max--; |
| 975 | } else if (cmp == kCondGE) { |
| 976 | min++; |
| 977 | } |
| 978 | // Do both bounds fit the range? |
Vladimir Marko | 0e2f2ff | 2016-03-22 12:31:54 +0000 | [diff] [blame] | 979 | int64_t value = 0; |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 980 | return IsAtLeast(lower_expr, &value) && value >= min && |
| 981 | IsAtMost(lower_expr, &value) && value <= max && |
| 982 | IsAtLeast(upper_expr, &value) && value >= min && |
| 983 | IsAtMost(upper_expr, &value) && value <= max; |
| 984 | } |
| 985 | |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 986 | void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop, |
| 987 | HInstruction* instruction, |
| 988 | InductionInfo* info) { |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 989 | auto it = induction_.find(loop); |
| 990 | if (it == induction_.end()) { |
| 991 | it = induction_.Put(loop, |
| 992 | ArenaSafeMap<HInstruction*, InductionInfo*>( |
Vladimir Marko | 5233f93 | 2015-09-29 19:01:15 +0100 | [diff] [blame] | 993 | std::less<HInstruction*>(), |
| 994 | graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis))); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 995 | } |
| 996 | it->second.Put(instruction, info); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 997 | } |
| 998 | |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 999 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::LookupInfo(HLoopInformation* loop, |
| 1000 | HInstruction* instruction) { |
| 1001 | auto it = induction_.find(loop); |
| 1002 | if (it != induction_.end()) { |
| 1003 | auto loop_it = it->second.find(instruction); |
| 1004 | if (loop_it != it->second.end()) { |
| 1005 | return loop_it->second; |
| 1006 | } |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1007 | } |
Mingyao Yang | 4b467ed | 2015-11-19 17:04:22 -0800 | [diff] [blame] | 1008 | if (loop->IsDefinedOutOfTheLoop(instruction)) { |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1009 | InductionInfo* info = CreateInvariantFetch(instruction); |
Aart Bik | e609b7c | 2015-08-27 13:46:58 -0700 | [diff] [blame] | 1010 | AssignInfo(loop, instruction, info); |
| 1011 | return info; |
| 1012 | } |
| 1013 | return nullptr; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1014 | } |
| 1015 | |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1016 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateConstant(int64_t value, |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1017 | DataType::Type type) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1018 | HInstruction* constant; |
| 1019 | switch (type) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1020 | case DataType::Type::kFloat64: constant = graph_->GetDoubleConstant(value); break; |
| 1021 | case DataType::Type::kFloat32: constant = graph_->GetFloatConstant(value); break; |
| 1022 | case DataType::Type::kInt64: constant = graph_->GetLongConstant(value); break; |
| 1023 | default: constant = graph_->GetIntConstant(value); break; |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1024 | } |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1025 | return CreateInvariantFetch(constant); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1026 | } |
| 1027 | |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1028 | HInductionVarAnalysis::InductionInfo* HInductionVarAnalysis::CreateSimplifiedInvariant( |
| 1029 | InductionOp op, |
| 1030 | InductionInfo* a, |
| 1031 | InductionInfo* b) { |
| 1032 | // Perform some light-weight simplifications during construction of a new invariant. |
| 1033 | // This often safes memory and yields a more concise representation of the induction. |
| 1034 | // More exhaustive simplifications are done by later phases once induction nodes are |
| 1035 | // translated back into HIR code (e.g. by loop optimizations or BCE). |
| 1036 | int64_t value = -1; |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 1037 | if (IsExact(a, &value)) { |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1038 | if (value == 0) { |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 1039 | // Simplify 0 + b = b, 0 ^ b = b, 0 * b = 0. |
| 1040 | if (op == kAdd || op == kXor) { |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1041 | return b; |
| 1042 | } else if (op == kMul) { |
| 1043 | return a; |
| 1044 | } |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1045 | } else if (op == kMul) { |
| 1046 | // Simplify 1 * b = b, -1 * b = -b |
| 1047 | if (value == 1) { |
| 1048 | return b; |
| 1049 | } else if (value == -1) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 1050 | return CreateSimplifiedInvariant(kNeg, nullptr, b); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1051 | } |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1052 | } |
| 1053 | } |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 1054 | if (IsExact(b, &value)) { |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1055 | if (value == 0) { |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 1056 | // Simplify a + 0 = a, a - 0 = a, a ^ 0 = a, a * 0 = 0, -0 = 0. |
| 1057 | if (op == kAdd || op == kSub || op == kXor) { |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1058 | return a; |
| 1059 | } else if (op == kMul || op == kNeg) { |
| 1060 | return b; |
| 1061 | } |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1062 | } else if (op == kMul || op == kDiv) { |
| 1063 | // Simplify a * 1 = a, a / 1 = a, a * -1 = -a, a / -1 = -a |
| 1064 | if (value == 1) { |
| 1065 | return a; |
| 1066 | } else if (value == -1) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 1067 | return CreateSimplifiedInvariant(kNeg, nullptr, a); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1068 | } |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1069 | } |
| 1070 | } else if (b->operation == kNeg) { |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1071 | // Simplify a + (-b) = a - b, a - (-b) = a + b, -(-b) = b. |
| 1072 | if (op == kAdd) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 1073 | return CreateSimplifiedInvariant(kSub, a, b->op_b); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1074 | } else if (op == kSub) { |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 1075 | return CreateSimplifiedInvariant(kAdd, a, b->op_b); |
Aart Bik | d14c595 | 2015-09-08 15:25:15 -0700 | [diff] [blame] | 1076 | } else if (op == kNeg) { |
| 1077 | return b->op_b; |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1078 | } |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 1079 | } else if (b->operation == kSub) { |
| 1080 | // Simplify - (a - b) = b - a. |
| 1081 | if (op == kNeg) { |
| 1082 | return CreateSimplifiedInvariant(kSub, b->op_b, b->op_a); |
| 1083 | } |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1084 | } |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 1085 | return new (graph_->GetArena()) InductionInfo( |
| 1086 | kInvariant, op, a, b, nullptr, ImplicitConversion(b->type)); |
Aart Bik | 471a203 | 2015-09-04 18:22:11 -0700 | [diff] [blame] | 1087 | } |
| 1088 | |
Aart Bik | d0a022d | 2016-12-13 11:22:31 -0800 | [diff] [blame] | 1089 | HInstruction* HInductionVarAnalysis::GetShiftConstant(HLoopInformation* loop, |
| 1090 | HInstruction* instruction, |
| 1091 | InductionInfo* initial) { |
| 1092 | DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); |
| 1093 | // Shift-rights are only the same as division for non-negative initial inputs. |
| 1094 | // Otherwise we would round incorrectly. |
| 1095 | if (initial != nullptr) { |
| 1096 | int64_t value = -1; |
| 1097 | if (!IsAtLeast(initial, &value) || value < 0) { |
| 1098 | return nullptr; |
| 1099 | } |
| 1100 | } |
| 1101 | // Obtain the constant needed to treat shift as equivalent multiplication or division. |
| 1102 | // This yields an existing instruction if the constant is already there. Otherwise, this |
| 1103 | // has a side effect on the HIR. The restriction on the shift factor avoids generating a |
| 1104 | // negative constant (viz. 1 << 31 and 1L << 63 set the sign bit). The code assumes that |
| 1105 | // generalization for shift factors outside [0,32) and [0,64) ranges is done earlier. |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1106 | InductionInfo* b = LookupInfo(loop, instruction->InputAt(1)); |
| 1107 | int64_t value = -1; |
| 1108 | if (IsExact(b, &value)) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1109 | DataType::Type type = instruction->InputAt(0)->GetType(); |
| 1110 | if (type == DataType::Type::kInt32 && 0 <= value && value < 31) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1111 | return graph_->GetIntConstant(1 << value); |
| 1112 | } |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1113 | if (type == DataType::Type::kInt64 && 0 <= value && value < 63) { |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1114 | return graph_->GetLongConstant(1L << value); |
| 1115 | } |
| 1116 | } |
| 1117 | return nullptr; |
| 1118 | } |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 1119 | |
| 1120 | void HInductionVarAnalysis::AssignCycle(HPhi* phi) { |
| 1121 | ArenaSet<HInstruction*>* set = &cycles_.Put(phi, ArenaSet<HInstruction*>( |
| 1122 | graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)))->second; |
| 1123 | for (HInstruction* i : scc_) { |
| 1124 | set->insert(i); |
| 1125 | } |
| 1126 | } |
| 1127 | |
| 1128 | ArenaSet<HInstruction*>* HInductionVarAnalysis::LookupCycle(HPhi* phi) { |
| 1129 | auto it = cycles_.find(phi); |
| 1130 | if (it != cycles_.end()) { |
| 1131 | return &it->second; |
| 1132 | } |
| 1133 | return nullptr; |
| 1134 | } |
| 1135 | |
Aart Bik | 97412c9 | 2016-02-19 20:14:38 -0800 | [diff] [blame] | 1136 | bool HInductionVarAnalysis::IsExact(InductionInfo* info, int64_t* value) { |
| 1137 | return InductionVarRange(this).IsConstant(info, InductionVarRange::kExact, value); |
| 1138 | } |
| 1139 | |
| 1140 | bool HInductionVarAnalysis::IsAtMost(InductionInfo* info, int64_t* value) { |
| 1141 | return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtMost, value); |
| 1142 | } |
| 1143 | |
| 1144 | bool HInductionVarAnalysis::IsAtLeast(InductionInfo* info, int64_t* value) { |
| 1145 | return InductionVarRange(this).IsConstant(info, InductionVarRange::kAtLeast, value); |
Aart Bik | 7d57d7f | 2015-12-09 14:39:48 -0800 | [diff] [blame] | 1146 | } |
| 1147 | |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 1148 | bool HInductionVarAnalysis::IsNarrowingLinear(InductionInfo* info) { |
| 1149 | return info != nullptr && |
| 1150 | info->induction_class == kLinear && |
Vladimir Marko | d5d2f2c | 2017-09-26 12:37:26 +0100 | [diff] [blame] | 1151 | (info->type == DataType::Type::kUint8 || |
| 1152 | info->type == DataType::Type::kInt8 || |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1153 | info->type == DataType::Type::kUint16 || |
Vladimir Marko | d5d2f2c | 2017-09-26 12:37:26 +0100 | [diff] [blame] | 1154 | info->type == DataType::Type::kInt16 || |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1155 | (info->type == DataType::Type::kInt32 && (info->op_a->type == DataType::Type::kInt64 || |
| 1156 | info->op_b->type == DataType::Type::kInt64))); |
Aart Bik | e6bd027 | 2016-12-16 13:57:52 -0800 | [diff] [blame] | 1157 | } |
| 1158 | |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1159 | bool HInductionVarAnalysis::InductionEqual(InductionInfo* info1, |
| 1160 | InductionInfo* info2) { |
| 1161 | // Test structural equality only, without accounting for simplifications. |
| 1162 | if (info1 != nullptr && info2 != nullptr) { |
| 1163 | return |
| 1164 | info1->induction_class == info2->induction_class && |
| 1165 | info1->operation == info2->operation && |
| 1166 | info1->fetch == info2->fetch && |
Aart Bik | 7829691 | 2016-03-25 13:14:53 -0700 | [diff] [blame] | 1167 | info1->type == info2->type && |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1168 | InductionEqual(info1->op_a, info2->op_a) && |
| 1169 | InductionEqual(info1->op_b, info2->op_b); |
| 1170 | } |
| 1171 | // Otherwise only two nullptrs are considered equal. |
| 1172 | return info1 == info2; |
| 1173 | } |
| 1174 | |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1175 | std::string HInductionVarAnalysis::FetchToString(HInstruction* fetch) { |
| 1176 | DCHECK(fetch != nullptr); |
| 1177 | if (fetch->IsIntConstant()) { |
| 1178 | return std::to_string(fetch->AsIntConstant()->GetValue()); |
| 1179 | } else if (fetch->IsLongConstant()) { |
| 1180 | return std::to_string(fetch->AsLongConstant()->GetValue()); |
| 1181 | } |
| 1182 | return std::to_string(fetch->GetId()) + ":" + fetch->DebugName(); |
| 1183 | } |
| 1184 | |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1185 | std::string HInductionVarAnalysis::InductionToString(InductionInfo* info) { |
| 1186 | if (info != nullptr) { |
| 1187 | if (info->induction_class == kInvariant) { |
| 1188 | std::string inv = "("; |
| 1189 | inv += InductionToString(info->op_a); |
| 1190 | switch (info->operation) { |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 1191 | case kNop: inv += " @ "; break; |
| 1192 | case kAdd: inv += " + "; break; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1193 | case kSub: |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 1194 | case kNeg: inv += " - "; break; |
| 1195 | case kMul: inv += " * "; break; |
| 1196 | case kDiv: inv += " / "; break; |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 1197 | case kRem: inv += " % "; break; |
Aart Bik | 7dc9693 | 2016-10-12 10:01:05 -0700 | [diff] [blame] | 1198 | case kXor: inv += " ^ "; break; |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 1199 | case kLT: inv += " < "; break; |
| 1200 | case kLE: inv += " <= "; break; |
| 1201 | case kGT: inv += " > "; break; |
| 1202 | case kGE: inv += " >= "; break; |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1203 | case kFetch: inv += FetchToString(info->fetch); break; |
Aart Bik | 22f0587 | 2015-10-27 15:56:28 -0700 | [diff] [blame] | 1204 | case kTripCountInLoop: inv += " (TC-loop) "; break; |
| 1205 | case kTripCountInBody: inv += " (TC-body) "; break; |
| 1206 | case kTripCountInLoopUnsafe: inv += " (TC-loop-unsafe) "; break; |
| 1207 | case kTripCountInBodyUnsafe: inv += " (TC-body-unsafe) "; break; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1208 | } |
| 1209 | inv += InductionToString(info->op_b); |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 1210 | inv += ")"; |
| 1211 | return inv; |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1212 | } else { |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1213 | if (info->induction_class == kLinear) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 1214 | DCHECK(info->operation == kNop); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1215 | return "(" + InductionToString(info->op_a) + " * i + " + |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 1216 | InductionToString(info->op_b) + "):" + |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1217 | DataType::PrettyDescriptor(info->type); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1218 | } else if (info->induction_class == kPolynomial) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 1219 | DCHECK(info->operation == kNop); |
| 1220 | return "poly(sum_lt(" + InductionToString(info->op_a) + ") + " + |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1221 | InductionToString(info->op_b) + "):" + |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1222 | DataType::PrettyDescriptor(info->type); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1223 | } else if (info->induction_class == kGeometric) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 1224 | DCHECK(info->operation == kMul || info->operation == kDiv); |
Aart Bik | c071a01 | 2016-12-01 10:22:31 -0800 | [diff] [blame] | 1225 | DCHECK(info->fetch != nullptr); |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 1226 | return "geo(" + InductionToString(info->op_a) + " * " + |
| 1227 | FetchToString(info->fetch) + |
| 1228 | (info->operation == kMul ? " ^ i + " : " ^ -i + ") + |
| 1229 | InductionToString(info->op_b) + "):" + |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1230 | DataType::PrettyDescriptor(info->type); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1231 | } else if (info->induction_class == kWrapAround) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 1232 | DCHECK(info->operation == kNop); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1233 | return "wrap(" + InductionToString(info->op_a) + ", " + |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 1234 | InductionToString(info->op_b) + "):" + |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1235 | DataType::PrettyDescriptor(info->type); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1236 | } else if (info->induction_class == kPeriodic) { |
Aart Bik | df7822e | 2016-12-06 10:05:30 -0800 | [diff] [blame] | 1237 | DCHECK(info->operation == kNop); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1238 | return "periodic(" + InductionToString(info->op_a) + ", " + |
Aart Bik | 0d345cf | 2016-03-16 10:49:38 -0700 | [diff] [blame] | 1239 | InductionToString(info->op_b) + "):" + |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 1240 | DataType::PrettyDescriptor(info->type); |
Aart Bik | 30efb4e | 2015-07-30 12:14:31 -0700 | [diff] [blame] | 1241 | } |
| 1242 | } |
| 1243 | } |
| 1244 | return ""; |
| 1245 | } |
| 1246 | |
| 1247 | } // namespace art |