Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2016 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 "loop_optimization.h" |
| 18 | |
Aart Bik | 9620230 | 2016-10-04 17:33:56 -0700 | [diff] [blame] | 19 | #include "linear_order.h" |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 20 | |
| 21 | namespace art { |
| 22 | |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 23 | // Remove the instruction from the graph. A bit more elaborate than the usual |
| 24 | // instruction removal, since there may be a cycle in the use structure. |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 25 | static void RemoveFromCycle(HInstruction* instruction) { |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 26 | instruction->RemoveAsUserOfAllInputs(); |
| 27 | instruction->RemoveEnvironmentUsers(); |
| 28 | instruction->GetBlock()->RemoveInstructionOrPhi(instruction, /*ensure_safety=*/ false); |
| 29 | } |
| 30 | |
Aart Bik | 807868e | 2016-11-03 17:51:43 -0700 | [diff] [blame] | 31 | // Detect a goto block and sets succ to the single successor. |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 32 | static bool IsGotoBlock(HBasicBlock* block, /*out*/ HBasicBlock** succ) { |
| 33 | if (block->GetPredecessors().size() == 1 && |
| 34 | block->GetSuccessors().size() == 1 && |
| 35 | block->IsSingleGoto()) { |
| 36 | *succ = block->GetSingleSuccessor(); |
| 37 | return true; |
| 38 | } |
| 39 | return false; |
| 40 | } |
| 41 | |
Aart Bik | 807868e | 2016-11-03 17:51:43 -0700 | [diff] [blame] | 42 | // Detect an early exit loop. |
| 43 | static bool IsEarlyExit(HLoopInformation* loop_info) { |
| 44 | HBlocksInLoopReversePostOrderIterator it_loop(*loop_info); |
| 45 | for (it_loop.Advance(); !it_loop.Done(); it_loop.Advance()) { |
| 46 | for (HBasicBlock* successor : it_loop.Current()->GetSuccessors()) { |
| 47 | if (!loop_info->Contains(*successor)) { |
| 48 | return true; |
| 49 | } |
| 50 | } |
| 51 | } |
| 52 | return false; |
| 53 | } |
| 54 | |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 55 | // |
| 56 | // Class methods. |
| 57 | // |
| 58 | |
| 59 | HLoopOptimization::HLoopOptimization(HGraph* graph, |
| 60 | HInductionVarAnalysis* induction_analysis) |
| 61 | : HOptimization(graph, kLoopOptimizationPassName), |
| 62 | induction_range_(induction_analysis), |
Aart Bik | 9620230 | 2016-10-04 17:33:56 -0700 | [diff] [blame] | 63 | loop_allocator_(nullptr), |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 64 | top_loop_(nullptr), |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 65 | last_loop_(nullptr), |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 66 | iset_(nullptr), |
| 67 | induction_simplication_count_(0) { |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 68 | } |
| 69 | |
| 70 | void HLoopOptimization::Run() { |
| 71 | // Well-behaved loops only. |
| 72 | // TODO: make this less of a sledgehammer. |
Aart Bik | 9620230 | 2016-10-04 17:33:56 -0700 | [diff] [blame] | 73 | if (graph_->HasTryCatch() || graph_->HasIrreducibleLoops()) { |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 74 | return; |
| 75 | } |
| 76 | |
Aart Bik | 9620230 | 2016-10-04 17:33:56 -0700 | [diff] [blame] | 77 | // Phase-local allocator that draws from the global pool. Since the allocator |
| 78 | // itself resides on the stack, it is destructed on exiting Run(), which |
| 79 | // implies its underlying memory is released immediately. |
Nicolas Geoffray | ebe1674 | 2016-10-05 09:55:42 +0100 | [diff] [blame] | 80 | ArenaAllocator allocator(graph_->GetArena()->GetArenaPool()); |
Aart Bik | 9620230 | 2016-10-04 17:33:56 -0700 | [diff] [blame] | 81 | loop_allocator_ = &allocator; |
Nicolas Geoffray | ebe1674 | 2016-10-05 09:55:42 +0100 | [diff] [blame] | 82 | |
Aart Bik | 9620230 | 2016-10-04 17:33:56 -0700 | [diff] [blame] | 83 | // Perform loop optimizations. |
| 84 | LocalRun(); |
| 85 | |
| 86 | // Detach. |
| 87 | loop_allocator_ = nullptr; |
| 88 | last_loop_ = top_loop_ = nullptr; |
| 89 | } |
| 90 | |
| 91 | void HLoopOptimization::LocalRun() { |
| 92 | // Build the linear order using the phase-local allocator. This step enables building |
| 93 | // a loop hierarchy that properly reflects the outer-inner and previous-next relation. |
| 94 | ArenaVector<HBasicBlock*> linear_order(loop_allocator_->Adapter(kArenaAllocLinearOrder)); |
| 95 | LinearizeGraph(graph_, loop_allocator_, &linear_order); |
| 96 | |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 97 | // Build the loop hierarchy. |
Aart Bik | 9620230 | 2016-10-04 17:33:56 -0700 | [diff] [blame] | 98 | for (HBasicBlock* block : linear_order) { |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 99 | if (block->IsLoopHeader()) { |
| 100 | AddLoop(block->GetLoopInformation()); |
| 101 | } |
| 102 | } |
Aart Bik | 9620230 | 2016-10-04 17:33:56 -0700 | [diff] [blame] | 103 | |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 104 | // Traverse the loop hierarchy inner-to-outer and optimize. Traversal can use |
| 105 | // a temporary set that stores instructions using the phase-local allocator. |
| 106 | if (top_loop_ != nullptr) { |
| 107 | ArenaSet<HInstruction*> iset(loop_allocator_->Adapter(kArenaAllocLoopOptimization)); |
| 108 | iset_ = &iset; |
| 109 | TraverseLoopsInnerToOuter(top_loop_); |
| 110 | iset_ = nullptr; // detach |
| 111 | } |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 112 | } |
| 113 | |
| 114 | void HLoopOptimization::AddLoop(HLoopInformation* loop_info) { |
| 115 | DCHECK(loop_info != nullptr); |
Nicolas Geoffray | ebe1674 | 2016-10-05 09:55:42 +0100 | [diff] [blame] | 116 | LoopNode* node = new (loop_allocator_) LoopNode(loop_info); // phase-local allocator |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 117 | if (last_loop_ == nullptr) { |
| 118 | // First loop. |
| 119 | DCHECK(top_loop_ == nullptr); |
| 120 | last_loop_ = top_loop_ = node; |
| 121 | } else if (loop_info->IsIn(*last_loop_->loop_info)) { |
| 122 | // Inner loop. |
| 123 | node->outer = last_loop_; |
| 124 | DCHECK(last_loop_->inner == nullptr); |
| 125 | last_loop_ = last_loop_->inner = node; |
| 126 | } else { |
| 127 | // Subsequent loop. |
| 128 | while (last_loop_->outer != nullptr && !loop_info->IsIn(*last_loop_->outer->loop_info)) { |
| 129 | last_loop_ = last_loop_->outer; |
| 130 | } |
| 131 | node->outer = last_loop_->outer; |
| 132 | node->previous = last_loop_; |
| 133 | DCHECK(last_loop_->next == nullptr); |
| 134 | last_loop_ = last_loop_->next = node; |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | void HLoopOptimization::RemoveLoop(LoopNode* node) { |
| 139 | DCHECK(node != nullptr); |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 140 | DCHECK(node->inner == nullptr); |
| 141 | if (node->previous != nullptr) { |
| 142 | // Within sequence. |
| 143 | node->previous->next = node->next; |
| 144 | if (node->next != nullptr) { |
| 145 | node->next->previous = node->previous; |
| 146 | } |
| 147 | } else { |
| 148 | // First of sequence. |
| 149 | if (node->outer != nullptr) { |
| 150 | node->outer->inner = node->next; |
| 151 | } else { |
| 152 | top_loop_ = node->next; |
| 153 | } |
| 154 | if (node->next != nullptr) { |
| 155 | node->next->outer = node->outer; |
| 156 | node->next->previous = nullptr; |
| 157 | } |
| 158 | } |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 159 | } |
| 160 | |
| 161 | void HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) { |
| 162 | for ( ; node != nullptr; node = node->next) { |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 163 | int current_induction_simplification_count = induction_simplication_count_; |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 164 | if (node->inner != nullptr) { |
| 165 | TraverseLoopsInnerToOuter(node->inner); |
| 166 | } |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 167 | // Visit loop after its inner loops have been visited. If the induction of any inner |
| 168 | // loop has been simplified, recompute the induction information of this loop first. |
| 169 | if (current_induction_simplification_count != induction_simplication_count_) { |
| 170 | induction_range_.ReVisit(node->loop_info); |
| 171 | } |
Aart Bik | 639cc8c | 2016-10-18 13:03:31 -0700 | [diff] [blame] | 172 | SimplifyBlocks(node); |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 173 | SimplifyInduction(node); |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 174 | SimplifyBlocks(node); |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 175 | if (node->inner == nullptr) { |
| 176 | RemoveIfEmptyInnerLoop(node); |
| 177 | } |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 178 | } |
| 179 | } |
| 180 | |
| 181 | void HLoopOptimization::SimplifyInduction(LoopNode* node) { |
| 182 | HBasicBlock* header = node->loop_info->GetHeader(); |
| 183 | HBasicBlock* preheader = node->loop_info->GetPreHeader(); |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 184 | // Scan the phis in the header to find opportunities to simplify an induction |
| 185 | // cycle that is only used outside the loop. Replace these uses, if any, with |
| 186 | // the last value and remove the induction cycle. |
| 187 | // Examples: for (int i = 0; x != null; i++) { .... no i .... } |
| 188 | // for (int i = 0; i < 10; i++, k++) { .... no k .... } return k; |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 189 | for (HInstructionIterator it(header->GetPhis()); !it.Done(); it.Advance()) { |
| 190 | HPhi* phi = it.Current()->AsPhi(); |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 191 | iset_->clear(); |
| 192 | int32_t use_count = 0; |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 193 | if (IsPhiInduction(phi) && |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 194 | IsOnlyUsedAfterLoop(node->loop_info, phi, &use_count) && |
Aart Bik | 807868e | 2016-11-03 17:51:43 -0700 | [diff] [blame] | 195 | // No uses, or no early-exit with proper replacement. |
| 196 | (use_count == 0 || |
| 197 | (!IsEarlyExit(node->loop_info) && TryReplaceWithLastValue(phi, preheader)))) { |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 198 | for (HInstruction* i : *iset_) { |
| 199 | RemoveFromCycle(i); |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 200 | } |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 201 | induction_simplication_count_++; |
| 202 | } |
| 203 | } |
| 204 | } |
| 205 | |
| 206 | void HLoopOptimization::SimplifyBlocks(LoopNode* node) { |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 207 | // Repeat the block simplifications until no more changes occur. Note that since |
| 208 | // each simplification consists of eliminating code (without introducing new code), |
| 209 | // this process is always finite. |
| 210 | bool changed; |
| 211 | do { |
| 212 | changed = false; |
| 213 | // Iterate over all basic blocks in the loop-body. |
| 214 | for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) { |
| 215 | HBasicBlock* block = it.Current(); |
| 216 | // Remove dead instructions from the loop-body. |
| 217 | for (HBackwardInstructionIterator i(block->GetInstructions()); !i.Done(); i.Advance()) { |
| 218 | HInstruction* instruction = i.Current(); |
| 219 | if (instruction->IsDeadAndRemovable()) { |
| 220 | changed = true; |
| 221 | block->RemoveInstruction(instruction); |
| 222 | } |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 223 | } |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 224 | // Remove trivial control flow blocks from the loop-body. |
| 225 | HBasicBlock* succ = nullptr; |
| 226 | if (IsGotoBlock(block, &succ) && succ->GetPredecessors().size() == 1) { |
| 227 | // Trivial goto block can be removed. |
| 228 | HBasicBlock* pred = block->GetSinglePredecessor(); |
| 229 | changed = true; |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 230 | pred->ReplaceSuccessor(block, succ); |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 231 | block->RemoveDominatedBlock(succ); |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 232 | block->DisconnectAndDelete(); |
| 233 | pred->AddDominatedBlock(succ); |
| 234 | succ->SetDominator(pred); |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 235 | } else if (block->GetSuccessors().size() == 2) { |
| 236 | // Trivial if block can be bypassed to either branch. |
| 237 | HBasicBlock* succ0 = block->GetSuccessors()[0]; |
| 238 | HBasicBlock* succ1 = block->GetSuccessors()[1]; |
| 239 | HBasicBlock* meet0 = nullptr; |
| 240 | HBasicBlock* meet1 = nullptr; |
| 241 | if (succ0 != succ1 && |
| 242 | IsGotoBlock(succ0, &meet0) && |
| 243 | IsGotoBlock(succ1, &meet1) && |
| 244 | meet0 == meet1 && // meets again |
| 245 | meet0 != block && // no self-loop |
| 246 | meet0->GetPhis().IsEmpty()) { // not used for merging |
| 247 | changed = true; |
| 248 | succ0->DisconnectAndDelete(); |
| 249 | if (block->Dominates(meet0)) { |
| 250 | block->RemoveDominatedBlock(meet0); |
| 251 | succ1->AddDominatedBlock(meet0); |
| 252 | meet0->SetDominator(succ1); |
| 253 | } |
| 254 | } |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 255 | } |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 256 | } |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 257 | } while (changed); |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 258 | } |
| 259 | |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 260 | void HLoopOptimization::RemoveIfEmptyInnerLoop(LoopNode* node) { |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 261 | HBasicBlock* header = node->loop_info->GetHeader(); |
| 262 | HBasicBlock* preheader = node->loop_info->GetPreHeader(); |
Aart Bik | 9abf894 | 2016-10-14 09:49:42 -0700 | [diff] [blame] | 263 | // Ensure loop header logic is finite. |
| 264 | if (!induction_range_.IsFinite(node->loop_info)) { |
| 265 | return; |
| 266 | } |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 267 | // Ensure there is only a single loop-body (besides the header). |
| 268 | HBasicBlock* body = nullptr; |
| 269 | for (HBlocksInLoopIterator it(*node->loop_info); !it.Done(); it.Advance()) { |
| 270 | if (it.Current() != header) { |
| 271 | if (body != nullptr) { |
| 272 | return; |
| 273 | } |
| 274 | body = it.Current(); |
| 275 | } |
| 276 | } |
| 277 | // Ensure there is only a single exit point. |
| 278 | if (header->GetSuccessors().size() != 2) { |
| 279 | return; |
| 280 | } |
| 281 | HBasicBlock* exit = (header->GetSuccessors()[0] == body) |
| 282 | ? header->GetSuccessors()[1] |
| 283 | : header->GetSuccessors()[0]; |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 284 | // Ensure exit can only be reached by exiting loop. |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 285 | if (exit->GetPredecessors().size() != 1) { |
| 286 | return; |
| 287 | } |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 288 | // Detect an empty loop: no side effects other than plain iteration. Replace |
| 289 | // subsequent index uses, if any, with the last value and remove the loop. |
| 290 | iset_->clear(); |
| 291 | int32_t use_count = 0; |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 292 | if (IsEmptyHeader(header) && |
| 293 | IsEmptyBody(body) && |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 294 | IsOnlyUsedAfterLoop(node->loop_info, header->GetFirstPhi(), &use_count) && |
Aart Bik | 807868e | 2016-11-03 17:51:43 -0700 | [diff] [blame] | 295 | // No uses, or proper replacement. |
| 296 | (use_count == 0 || TryReplaceWithLastValue(header->GetFirstPhi(), preheader))) { |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 297 | body->DisconnectAndDelete(); |
| 298 | exit->RemovePredecessor(header); |
| 299 | header->RemoveSuccessor(exit); |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 300 | header->RemoveDominatedBlock(exit); |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 301 | header->DisconnectAndDelete(); |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 302 | preheader->AddSuccessor(exit); |
| 303 | preheader->AddInstruction(new (graph_->GetArena()) HGoto()); // global allocator |
| 304 | preheader->AddDominatedBlock(exit); |
| 305 | exit->SetDominator(preheader); |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 306 | // Update hierarchy. |
| 307 | RemoveLoop(node); |
| 308 | } |
| 309 | } |
| 310 | |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 311 | bool HLoopOptimization::IsPhiInduction(HPhi* phi) { |
| 312 | ArenaSet<HInstruction*>* set = induction_range_.LookupCycle(phi); |
| 313 | if (set != nullptr) { |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 314 | DCHECK(iset_->empty()); |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 315 | for (HInstruction* i : *set) { |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 316 | // Check that, other than instructions that are no longer in the graph (removed earlier) |
| 317 | // each instruction is removable and, other than the phi, uses are contained in the cycle. |
| 318 | if (!i->IsInBlock()) { |
| 319 | continue; |
| 320 | } else if (!i->IsRemovable()) { |
| 321 | return false; |
| 322 | } else if (i != phi) { |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 323 | for (const HUseListNode<HInstruction*>& use : i->GetUses()) { |
| 324 | if (set->find(use.GetUser()) == set->end()) { |
| 325 | return false; |
| 326 | } |
| 327 | } |
| 328 | } |
Aart Bik | e3dedc5 | 2016-11-02 17:50:27 -0700 | [diff] [blame] | 329 | iset_->insert(i); // copy |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 330 | } |
Aart Bik | cc42be0 | 2016-10-20 16:14:16 -0700 | [diff] [blame] | 331 | return true; |
| 332 | } |
| 333 | return false; |
| 334 | } |
| 335 | |
| 336 | // Find: phi: Phi(init, addsub) |
| 337 | // s: SuspendCheck |
| 338 | // c: Condition(phi, bound) |
| 339 | // i: If(c) |
| 340 | // TODO: Find a less pattern matching approach? |
| 341 | bool HLoopOptimization::IsEmptyHeader(HBasicBlock* block) { |
| 342 | DCHECK(iset_->empty()); |
| 343 | HInstruction* phi = block->GetFirstPhi(); |
| 344 | if (phi != nullptr && phi->GetNext() == nullptr && IsPhiInduction(phi->AsPhi())) { |
| 345 | HInstruction* s = block->GetFirstInstruction(); |
| 346 | if (s != nullptr && s->IsSuspendCheck()) { |
| 347 | HInstruction* c = s->GetNext(); |
| 348 | if (c != nullptr && c->IsCondition() && c->GetUses().HasExactlyOneElement()) { |
| 349 | HInstruction* i = c->GetNext(); |
| 350 | if (i != nullptr && i->IsIf() && i->InputAt(0) == c) { |
| 351 | iset_->insert(c); |
| 352 | iset_->insert(s); |
| 353 | return true; |
| 354 | } |
| 355 | } |
| 356 | } |
| 357 | } |
| 358 | return false; |
| 359 | } |
| 360 | |
| 361 | bool HLoopOptimization::IsEmptyBody(HBasicBlock* block) { |
| 362 | if (block->GetFirstPhi() == nullptr) { |
| 363 | for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { |
| 364 | HInstruction* instruction = it.Current(); |
| 365 | if (!instruction->IsGoto() && iset_->find(instruction) == iset_->end()) { |
| 366 | return false; |
| 367 | } |
| 368 | } |
| 369 | return true; |
| 370 | } |
| 371 | return false; |
| 372 | } |
| 373 | |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 374 | bool HLoopOptimization::IsOnlyUsedAfterLoop(HLoopInformation* loop_info, |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 375 | HInstruction* instruction, |
| 376 | /*out*/ int32_t* use_count) { |
| 377 | for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { |
| 378 | HInstruction* user = use.GetUser(); |
| 379 | if (iset_->find(user) == iset_->end()) { // not excluded? |
| 380 | HLoopInformation* other_loop_info = user->GetBlock()->GetLoopInformation(); |
Aart Bik | 482095d | 2016-10-10 15:39:10 -0700 | [diff] [blame] | 381 | if (other_loop_info != nullptr && other_loop_info->IsIn(*loop_info)) { |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 382 | return false; |
| 383 | } |
| 384 | ++*use_count; |
| 385 | } |
| 386 | } |
| 387 | return true; |
| 388 | } |
| 389 | |
| 390 | void HLoopOptimization::ReplaceAllUses(HInstruction* instruction, HInstruction* replacement) { |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 391 | const HUseList<HInstruction*>& uses = instruction->GetUses(); |
| 392 | for (auto it = uses.begin(), end = uses.end(); it != end;) { |
| 393 | HInstruction* user = it->GetUser(); |
| 394 | size_t index = it->GetIndex(); |
| 395 | ++it; // increment before replacing |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 396 | if (iset_->find(user) == iset_->end()) { // not excluded? |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 397 | user->ReplaceInput(replacement, index); |
| 398 | induction_range_.Replace(user, instruction, replacement); // update induction |
| 399 | } |
| 400 | } |
| 401 | const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses(); |
| 402 | for (auto it = env_uses.begin(), end = env_uses.end(); it != end;) { |
| 403 | HEnvironment* user = it->GetUser(); |
| 404 | size_t index = it->GetIndex(); |
| 405 | ++it; // increment before replacing |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 406 | if (iset_->find(user->GetHolder()) == iset_->end()) { // not excluded? |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 407 | user->RemoveAsUserOfInput(index); |
| 408 | user->SetRawEnvAt(index, replacement); |
| 409 | replacement->AddEnvUseAt(user, index); |
| 410 | } |
| 411 | } |
| 412 | } |
| 413 | |
Aart Bik | 807868e | 2016-11-03 17:51:43 -0700 | [diff] [blame] | 414 | bool HLoopOptimization::TryReplaceWithLastValue(HInstruction* instruction, HBasicBlock* block) { |
| 415 | // Try to replace outside uses with the last value. Environment uses can consume this |
| 416 | // value too, since any first true use is outside the loop (although this may imply |
| 417 | // that de-opting may look "ahead" a bit on the phi value). If there are only environment |
| 418 | // uses, the value is dropped altogether, since the computations have no effect. |
| 419 | if (induction_range_.CanGenerateLastValue(instruction)) { |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 420 | ReplaceAllUses(instruction, induction_range_.GenerateLastValue(instruction, graph_, block)); |
Aart Bik | 807868e | 2016-11-03 17:51:43 -0700 | [diff] [blame] | 421 | return true; |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 422 | } |
Aart Bik | 807868e | 2016-11-03 17:51:43 -0700 | [diff] [blame] | 423 | return false; |
Aart Bik | 8c4a854 | 2016-10-06 11:36:57 -0700 | [diff] [blame] | 424 | } |
| 425 | |
Aart Bik | 281c681 | 2016-08-26 11:31:48 -0700 | [diff] [blame] | 426 | } // namespace art |