Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 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 "ssa_phi_elimination.h" |
| 18 | |
Vladimir Marko | c9ef168 | 2016-05-10 13:31:23 +0100 | [diff] [blame] | 19 | #include "base/arena_bit_vector.h" |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 20 | #include "base/scoped_arena_allocator.h" |
| 21 | #include "base/scoped_arena_containers.h" |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 22 | #include "base/bit_vector-inl.h" |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 23 | |
Vladimir Marko | 0a51605 | 2019-10-14 13:00:44 +0000 | [diff] [blame] | 24 | namespace art { |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 25 | |
Aart Bik | 2477320 | 2018-04-26 10:28:51 -0700 | [diff] [blame] | 26 | bool SsaDeadPhiElimination::Run() { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 27 | MarkDeadPhis(); |
| 28 | EliminateDeadPhis(); |
Aart Bik | 2477320 | 2018-04-26 10:28:51 -0700 | [diff] [blame] | 29 | return true; |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 30 | } |
| 31 | |
| 32 | void SsaDeadPhiElimination::MarkDeadPhis() { |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 33 | // Use local allocator for allocating memory used by this optimization. |
| 34 | ScopedArenaAllocator allocator(graph_->GetArenaStack()); |
| 35 | |
| 36 | static constexpr size_t kDefaultWorklistSize = 8; |
| 37 | ScopedArenaVector<HPhi*> worklist(allocator.Adapter(kArenaAllocSsaPhiElimination)); |
| 38 | worklist.reserve(kDefaultWorklistSize); |
| 39 | |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 40 | // Phis are constructed live and should not be revived if previously marked |
| 41 | // dead. This algorithm temporarily breaks that invariant but we DCHECK that |
| 42 | // only phis which were initially live are revived. |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 43 | ScopedArenaSet<HPhi*> initially_live(allocator.Adapter(kArenaAllocSsaPhiElimination)); |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 44 | |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 45 | // Add to the worklist phis referenced by non-phi instructions. |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 46 | for (HBasicBlock* block : graph_->GetReversePostOrder()) { |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 47 | for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { |
| 48 | HPhi* phi = inst_it.Current()->AsPhi(); |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 49 | if (phi->IsDead()) { |
| 50 | continue; |
| 51 | } |
| 52 | |
David Brazdil | d9510df | 2015-11-04 23:30:22 +0000 | [diff] [blame] | 53 | bool keep_alive = (graph_->IsDebuggable() && phi->HasEnvironmentUses()); |
| 54 | if (!keep_alive) { |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 55 | for (const HUseListNode<HInstruction*>& use : phi->GetUses()) { |
| 56 | if (!use.GetUser()->IsPhi()) { |
David Brazdil | d9510df | 2015-11-04 23:30:22 +0000 | [diff] [blame] | 57 | keep_alive = true; |
| 58 | break; |
| 59 | } |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 60 | } |
| 61 | } |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 62 | |
David Brazdil | d9510df | 2015-11-04 23:30:22 +0000 | [diff] [blame] | 63 | if (keep_alive) { |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 64 | worklist.push_back(phi); |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 65 | } else { |
| 66 | phi->SetDead(); |
| 67 | if (kIsDebugBuild) { |
| 68 | initially_live.insert(phi); |
| 69 | } |
| 70 | } |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 71 | } |
| 72 | } |
| 73 | |
| 74 | // Process the worklist by propagating liveness to phi inputs. |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 75 | while (!worklist.empty()) { |
| 76 | HPhi* phi = worklist.back(); |
| 77 | worklist.pop_back(); |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 78 | for (HInstruction* raw_input : phi->GetInputs()) { |
| 79 | HPhi* input = raw_input->AsPhi(); |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 80 | if (input != nullptr && input->IsDead()) { |
| 81 | // Input is a dead phi. Revive it and add to the worklist. We make sure |
| 82 | // that the phi was not dead initially (see definition of `initially_live`). |
| 83 | DCHECK(ContainsElement(initially_live, input)); |
| 84 | input->SetLive(); |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 85 | worklist.push_back(input); |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 86 | } |
| 87 | } |
| 88 | } |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 89 | } |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 90 | |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 91 | void SsaDeadPhiElimination::EliminateDeadPhis() { |
Nicolas Geoffray | 3ac17fc | 2014-08-06 23:02:54 +0100 | [diff] [blame] | 92 | // Remove phis that are not live. Visit in post order so that phis |
| 93 | // that are not inputs of loop phis can be removed when they have |
| 94 | // no users left (dead phis might use dead phis). |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 95 | for (HBasicBlock* block : graph_->GetPostOrder()) { |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 96 | HInstruction* current = block->GetFirstPhi(); |
| 97 | HInstruction* next = nullptr; |
David Brazdil | 1abb419 | 2015-02-17 18:33:36 +0000 | [diff] [blame] | 98 | HPhi* phi; |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 99 | while (current != nullptr) { |
David Brazdil | 1abb419 | 2015-02-17 18:33:36 +0000 | [diff] [blame] | 100 | phi = current->AsPhi(); |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 101 | next = current->GetNext(); |
David Brazdil | 1abb419 | 2015-02-17 18:33:36 +0000 | [diff] [blame] | 102 | if (phi->IsDead()) { |
| 103 | // Make sure the phi is only used by other dead phis. |
| 104 | if (kIsDebugBuild) { |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 105 | for (const HUseListNode<HInstruction*>& use : phi->GetUses()) { |
| 106 | HInstruction* user = use.GetUser(); |
David Brazdil | d9510df | 2015-11-04 23:30:22 +0000 | [diff] [blame] | 107 | DCHECK(user->IsLoopHeaderPhi()); |
| 108 | DCHECK(user->AsPhi()->IsDead()); |
Nicolas Geoffray | 3ac17fc | 2014-08-06 23:02:54 +0100 | [diff] [blame] | 109 | } |
| 110 | } |
David Brazdil | 1abb419 | 2015-02-17 18:33:36 +0000 | [diff] [blame] | 111 | // Remove the phi from use lists of its inputs. |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 112 | phi->RemoveAsUserOfAllInputs(); |
David Brazdil | 1abb419 | 2015-02-17 18:33:36 +0000 | [diff] [blame] | 113 | // Remove the phi from environments that use it. |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 114 | for (const HUseListNode<HEnvironment*>& use : phi->GetEnvUses()) { |
| 115 | HEnvironment* user = use.GetUser(); |
| 116 | user->SetRawEnvAt(use.GetIndex(), nullptr); |
David Brazdil | 1abb419 | 2015-02-17 18:33:36 +0000 | [diff] [blame] | 117 | } |
| 118 | // Delete it from the instruction list. |
| 119 | block->RemovePhi(phi, /*ensure_safety=*/ false); |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 120 | } |
| 121 | current = next; |
| 122 | } |
| 123 | } |
| 124 | } |
| 125 | |
Aart Bik | 2477320 | 2018-04-26 10:28:51 -0700 | [diff] [blame] | 126 | bool SsaRedundantPhiElimination::Run() { |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 127 | // Use local allocator for allocating memory used by this optimization. |
| 128 | ScopedArenaAllocator allocator(graph_->GetArenaStack()); |
| 129 | |
| 130 | static constexpr size_t kDefaultWorklistSize = 8; |
| 131 | ScopedArenaVector<HPhi*> worklist(allocator.Adapter(kArenaAllocSsaPhiElimination)); |
| 132 | worklist.reserve(kDefaultWorklistSize); |
| 133 | |
David Brazdil | 77b022d | 2015-08-19 14:17:31 +0100 | [diff] [blame] | 134 | // Add all phis in the worklist. Order does not matter for correctness, and |
| 135 | // neither will necessarily converge faster. |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 136 | for (HBasicBlock* block : graph_->GetReversePostOrder()) { |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 137 | for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 138 | worklist.push_back(inst_it.Current()->AsPhi()); |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 139 | } |
| 140 | } |
| 141 | |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 142 | ArenaBitVector visited_phis_in_cycle(&allocator, |
Vladimir Marko | c9ef168 | 2016-05-10 13:31:23 +0100 | [diff] [blame] | 143 | graph_->GetCurrentInstructionId(), |
Andreas Gampe | 3db7068 | 2018-12-26 15:12:03 -0800 | [diff] [blame] | 144 | /* expandable= */ false, |
Vladimir Marko | c9ef168 | 2016-05-10 13:31:23 +0100 | [diff] [blame] | 145 | kArenaAllocSsaPhiElimination); |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 146 | visited_phis_in_cycle.ClearAllBits(); |
| 147 | ScopedArenaVector<HPhi*> cycle_worklist(allocator.Adapter(kArenaAllocSsaPhiElimination)); |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 148 | |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 149 | while (!worklist.empty()) { |
| 150 | HPhi* phi = worklist.back(); |
| 151 | worklist.pop_back(); |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 152 | |
| 153 | // If the phi has already been processed, continue. |
| 154 | if (!phi->IsInBlock()) { |
| 155 | continue; |
| 156 | } |
| 157 | |
Nicolas Geoffray | 05b3fa0 | 2016-05-04 12:05:56 +0100 | [diff] [blame] | 158 | // If the phi is dead, we know we won't revive it and it will be removed, |
| 159 | // so don't process it. |
| 160 | if (phi->IsDead()) { |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 161 | continue; |
| 162 | } |
| 163 | |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 164 | HInstruction* candidate = nullptr; |
Vladimir Marko | c9ef168 | 2016-05-10 13:31:23 +0100 | [diff] [blame] | 165 | visited_phis_in_cycle.ClearAllBits(); |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 166 | cycle_worklist.clear(); |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 167 | |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 168 | cycle_worklist.push_back(phi); |
Vladimir Marko | c9ef168 | 2016-05-10 13:31:23 +0100 | [diff] [blame] | 169 | visited_phis_in_cycle.SetBit(phi->GetId()); |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 170 | bool catch_phi_in_cycle = phi->IsCatchPhi(); |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 171 | bool irreducible_loop_phi_in_cycle = phi->IsIrreducibleLoopHeaderPhi(); |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 172 | |
| 173 | // First do a simple loop over inputs and check if they are all the same. |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 174 | for (HInstruction* input : phi->GetInputs()) { |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 175 | if (input == phi) { |
| 176 | continue; |
| 177 | } else if (candidate == nullptr) { |
| 178 | candidate = input; |
| 179 | } else if (candidate != input) { |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 180 | candidate = nullptr; |
| 181 | break; |
| 182 | } |
| 183 | } |
| 184 | |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 185 | // If we haven't found a candidate, check for a phi cycle. Note that we need to detect |
| 186 | // such cycles to avoid having reference and non-reference equivalents. We check this |
| 187 | // invariant in the graph checker. |
| 188 | if (candidate == nullptr) { |
| 189 | // We iterate over the array as long as it grows. |
| 190 | for (size_t i = 0; i < cycle_worklist.size(); ++i) { |
| 191 | HPhi* current = cycle_worklist[i]; |
| 192 | DCHECK(!current->IsLoopHeaderPhi() || |
| 193 | current->GetBlock()->IsLoopPreHeaderFirstPredecessor()); |
| 194 | |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 195 | for (HInstruction* input : current->GetInputs()) { |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 196 | if (input == current) { |
| 197 | continue; |
| 198 | } else if (input->IsPhi()) { |
Vladimir Marko | c9ef168 | 2016-05-10 13:31:23 +0100 | [diff] [blame] | 199 | if (!visited_phis_in_cycle.IsBitSet(input->GetId())) { |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 200 | cycle_worklist.push_back(input->AsPhi()); |
Vladimir Marko | c9ef168 | 2016-05-10 13:31:23 +0100 | [diff] [blame] | 201 | visited_phis_in_cycle.SetBit(input->GetId()); |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 202 | catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi(); |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 203 | irreducible_loop_phi_in_cycle |= input->IsIrreducibleLoopHeaderPhi(); |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 204 | } else { |
| 205 | // Already visited, nothing to do. |
| 206 | } |
| 207 | } else if (candidate == nullptr) { |
| 208 | candidate = input; |
| 209 | } else if (candidate != input) { |
| 210 | candidate = nullptr; |
| 211 | // Clear the cycle worklist to break out of the outer loop. |
| 212 | cycle_worklist.clear(); |
| 213 | break; |
| 214 | } |
| 215 | } |
| 216 | } |
| 217 | } |
| 218 | |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 219 | if (candidate == nullptr) { |
| 220 | continue; |
| 221 | } |
| 222 | |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 223 | if (irreducible_loop_phi_in_cycle && !candidate->IsConstant()) { |
| 224 | // For irreducible loops, we need to keep the phis to satisfy our linear scan |
| 225 | // algorithm. |
| 226 | // There is one exception for constants, as the type propagation requires redundant |
| 227 | // cyclic phis of a constant to be removed. This is ok for the linear scan as it |
| 228 | // has to deal with constants anyway, and they can trivially be rematerialized. |
| 229 | continue; |
| 230 | } |
| 231 | |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 232 | for (HPhi* current : cycle_worklist) { |
| 233 | // The candidate may not dominate a phi in a catch block: there may be non-throwing |
| 234 | // instructions at the beginning of a try range, that may be the first input of |
| 235 | // catch phis. |
| 236 | // TODO(dbrazdil): Remove this situation by moving those non-throwing instructions |
| 237 | // before the try entry. |
| 238 | if (catch_phi_in_cycle) { |
| 239 | if (!candidate->StrictlyDominates(current)) { |
| 240 | continue; |
| 241 | } |
| 242 | } else { |
| 243 | DCHECK(candidate->StrictlyDominates(current)); |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 244 | } |
David Brazdil | 77b022d | 2015-08-19 14:17:31 +0100 | [diff] [blame] | 245 | |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 246 | // Because we're updating the users of this phi, we may have new candidates |
| 247 | // for elimination. Add phis that use this phi to the worklist. |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 248 | for (const HUseListNode<HInstruction*>& use : current->GetUses()) { |
| 249 | HInstruction* user = use.GetUser(); |
Vladimir Marko | c9ef168 | 2016-05-10 13:31:23 +0100 | [diff] [blame] | 250 | if (user->IsPhi() && !visited_phis_in_cycle.IsBitSet(user->GetId())) { |
Vladimir Marko | f361267 | 2017-10-10 10:38:16 +0100 | [diff] [blame] | 251 | worklist.push_back(user->AsPhi()); |
Nicolas Geoffray | f5f64ef | 2015-12-15 14:11:59 +0000 | [diff] [blame] | 252 | } |
| 253 | } |
| 254 | DCHECK(candidate->StrictlyDominates(current)); |
| 255 | current->ReplaceWith(candidate); |
| 256 | current->GetBlock()->RemovePhi(current); |
| 257 | } |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 258 | } |
Aart Bik | 2477320 | 2018-04-26 10:28:51 -0700 | [diff] [blame] | 259 | return true; |
Nicolas Geoffray | 7dc206a | 2014-07-11 09:49:49 +0100 | [diff] [blame] | 260 | } |
| 261 | |
| 262 | } // namespace art |