Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +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_builder.h" |
Nicolas Geoffray | 184d640 | 2014-06-09 14:06:02 +0100 | [diff] [blame] | 18 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 19 | #include "nodes.h" |
Calin Juravle | 10e244f | 2015-01-26 18:54:32 +0000 | [diff] [blame] | 20 | #include "primitive_type_propagation.h" |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 21 | #include "ssa_phi_elimination.h" |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 22 | |
| 23 | namespace art { |
| 24 | |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 25 | /** |
| 26 | * A debuggable application may require to reviving phis, to ensure their |
| 27 | * associated DEX register is available to a debugger. This class implements |
| 28 | * the logic for statement (c) of the SsaBuilder (see ssa_builder.h). It |
| 29 | * also makes sure that phis with incompatible input types are not revived |
| 30 | * (statement (b) of the SsaBuilder). |
| 31 | * |
| 32 | * This phase must be run after detecting dead phis through the |
| 33 | * DeadPhiElimination phase, and before deleting the dead phis. |
| 34 | */ |
| 35 | class DeadPhiHandling : public ValueObject { |
| 36 | public: |
| 37 | explicit DeadPhiHandling(HGraph* graph) |
| 38 | : graph_(graph), worklist_(graph->GetArena(), kDefaultWorklistSize) {} |
| 39 | |
| 40 | void Run(); |
| 41 | |
| 42 | private: |
| 43 | void VisitBasicBlock(HBasicBlock* block); |
| 44 | void ProcessWorklist(); |
| 45 | void AddToWorklist(HPhi* phi); |
| 46 | void AddDependentInstructionsToWorklist(HPhi* phi); |
| 47 | bool UpdateType(HPhi* phi); |
| 48 | |
| 49 | HGraph* const graph_; |
| 50 | GrowableArray<HPhi*> worklist_; |
| 51 | |
| 52 | static constexpr size_t kDefaultWorklistSize = 8; |
| 53 | |
| 54 | DISALLOW_COPY_AND_ASSIGN(DeadPhiHandling); |
| 55 | }; |
| 56 | |
| 57 | bool DeadPhiHandling::UpdateType(HPhi* phi) { |
| 58 | Primitive::Type existing = phi->GetType(); |
| 59 | DCHECK(phi->IsLive()); |
| 60 | |
| 61 | bool conflict = false; |
| 62 | Primitive::Type new_type = existing; |
| 63 | for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { |
| 64 | HInstruction* input = phi->InputAt(i); |
| 65 | if (input->IsPhi() && input->AsPhi()->IsDead()) { |
| 66 | // We are doing a reverse post order visit of the graph, reviving |
| 67 | // phis that have environment uses and updating their types. If an |
| 68 | // input is a phi, and it is dead (because its input types are |
| 69 | // conflicting), this phi must be marked dead as well. |
| 70 | conflict = true; |
| 71 | break; |
| 72 | } |
| 73 | Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); |
| 74 | |
| 75 | // The only acceptable transitions are: |
| 76 | // - From void to typed: first time we update the type of this phi. |
| 77 | // - From int to reference (or reference to int): the phi has to change |
| 78 | // to reference type. If the integer input cannot be converted to a |
| 79 | // reference input, the phi will remain dead. |
| 80 | if (new_type == Primitive::kPrimVoid) { |
| 81 | new_type = input_type; |
| 82 | } else if (new_type == Primitive::kPrimNot && input_type == Primitive::kPrimInt) { |
| 83 | HInstruction* equivalent = SsaBuilder::GetReferenceTypeEquivalent(input); |
| 84 | if (equivalent == nullptr) { |
| 85 | conflict = true; |
| 86 | break; |
| 87 | } else { |
| 88 | phi->ReplaceInput(equivalent, i); |
| 89 | if (equivalent->IsPhi()) { |
| 90 | DCHECK_EQ(equivalent->GetType(), Primitive::kPrimNot); |
| 91 | // We created a new phi, but that phi has the same inputs as the old phi. We |
| 92 | // add it to the worklist to ensure its inputs can also be converted to reference. |
| 93 | // If not, it will remain dead, and the algorithm will make the current phi dead |
| 94 | // as well. |
| 95 | equivalent->AsPhi()->SetLive(); |
| 96 | AddToWorklist(equivalent->AsPhi()); |
| 97 | } |
| 98 | } |
| 99 | } else if (new_type == Primitive::kPrimInt && input_type == Primitive::kPrimNot) { |
| 100 | new_type = Primitive::kPrimNot; |
| 101 | // Start over, we may request reference equivalents for the inputs of the phi. |
| 102 | i = -1; |
| 103 | } else if (new_type != input_type) { |
| 104 | conflict = true; |
| 105 | break; |
| 106 | } |
| 107 | } |
| 108 | |
| 109 | if (conflict) { |
| 110 | phi->SetType(Primitive::kPrimVoid); |
| 111 | phi->SetDead(); |
| 112 | return true; |
| 113 | } else { |
| 114 | DCHECK(phi->IsLive()); |
| 115 | phi->SetType(new_type); |
| 116 | return existing != new_type; |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | void DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) { |
| 121 | for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { |
| 122 | HPhi* phi = it.Current()->AsPhi(); |
| 123 | if (phi->IsDead() && phi->HasEnvironmentUses()) { |
| 124 | phi->SetLive(); |
| 125 | if (block->IsLoopHeader()) { |
| 126 | // Give a type to the loop phi, to guarantee convergence of the algorithm. |
| 127 | phi->SetType(phi->InputAt(0)->GetType()); |
| 128 | AddToWorklist(phi); |
| 129 | } else { |
| 130 | // Because we are doing a reverse post order visit, all inputs of |
| 131 | // this phi have been visited and therefore had their (initial) type set. |
| 132 | UpdateType(phi); |
| 133 | } |
| 134 | } |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | void DeadPhiHandling::ProcessWorklist() { |
| 139 | while (!worklist_.IsEmpty()) { |
| 140 | HPhi* instruction = worklist_.Pop(); |
| 141 | // Note that the same equivalent phi can be added multiple times in the work list, if |
| 142 | // used by multiple phis. The first call to `UpdateType` will know whether the phi is |
| 143 | // dead or live. |
| 144 | if (instruction->IsLive() && UpdateType(instruction)) { |
| 145 | AddDependentInstructionsToWorklist(instruction); |
| 146 | } |
| 147 | } |
| 148 | } |
| 149 | |
| 150 | void DeadPhiHandling::AddToWorklist(HPhi* instruction) { |
| 151 | DCHECK(instruction->IsLive()); |
| 152 | worklist_.Add(instruction); |
| 153 | } |
| 154 | |
| 155 | void DeadPhiHandling::AddDependentInstructionsToWorklist(HPhi* instruction) { |
| 156 | for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { |
| 157 | HPhi* phi = it.Current()->GetUser()->AsPhi(); |
| 158 | if (phi != nullptr && !phi->IsDead()) { |
| 159 | AddToWorklist(phi); |
| 160 | } |
| 161 | } |
| 162 | } |
| 163 | |
| 164 | void DeadPhiHandling::Run() { |
| 165 | for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { |
| 166 | VisitBasicBlock(it.Current()); |
| 167 | } |
| 168 | ProcessWorklist(); |
| 169 | } |
| 170 | |
| 171 | static bool IsPhiEquivalentOf(HInstruction* instruction, HPhi* phi) { |
| 172 | return instruction != nullptr |
| 173 | && instruction->IsPhi() |
| 174 | && instruction->AsPhi()->GetRegNumber() == phi->GetRegNumber(); |
| 175 | } |
| 176 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 177 | void SsaBuilder::BuildSsa() { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 178 | // 1) Visit in reverse post order. We need to have all predecessors of a block visited |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 179 | // (with the exception of loops) in order to create the right environment for that |
| 180 | // block. For loops, we create phis whose inputs will be set in 2). |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 181 | for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { |
| 182 | VisitBasicBlock(it.Current()); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 183 | } |
| 184 | |
| 185 | // 2) Set inputs of loop phis. |
| 186 | for (size_t i = 0; i < loop_headers_.Size(); i++) { |
| 187 | HBasicBlock* block = loop_headers_.Get(i); |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 188 | for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 189 | HPhi* phi = it.Current()->AsPhi(); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 190 | for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) { |
Nicolas Geoffray | a7062e0 | 2014-05-22 12:50:17 +0100 | [diff] [blame] | 191 | HInstruction* input = ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber()); |
| 192 | phi->AddInput(input); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 193 | } |
| 194 | } |
| 195 | } |
| 196 | |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 197 | // 3) Mark dead phis. This will mark phis that are only used by environments: |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 198 | // at the DEX level, the type of these phis does not need to be consistent, but |
| 199 | // our code generator will complain if the inputs of a phi do not have the same |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 200 | // type. The marking allows the type propagation to know which phis it needs |
| 201 | // to handle. We mark but do not eliminate: the elimination will be done in |
Nicolas Geoffray | b59dba0 | 2015-03-11 18:13:21 +0000 | [diff] [blame] | 202 | // step 9). |
| 203 | SsaDeadPhiElimination dead_phis_for_type_propagation(GetGraph()); |
| 204 | dead_phis_for_type_propagation.MarkDeadPhis(); |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 205 | |
| 206 | // 4) Propagate types of phis. At this point, phis are typed void in the general |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 207 | // case, or float/double/reference when we created an equivalent phi. So we |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 208 | // need to propagate the types across phis to give them a correct type. |
Calin Juravle | 10e244f | 2015-01-26 18:54:32 +0000 | [diff] [blame] | 209 | PrimitiveTypePropagation type_propagation(GetGraph()); |
Nicolas Geoffray | 184d640 | 2014-06-09 14:06:02 +0100 | [diff] [blame] | 210 | type_propagation.Run(); |
| 211 | |
Nicolas Geoffray | b59dba0 | 2015-03-11 18:13:21 +0000 | [diff] [blame] | 212 | // 5) Mark dead phis again. Steph 4) may have introduced new phis. |
| 213 | SsaDeadPhiElimination dead_phis(GetGraph()); |
| 214 | dead_phis.MarkDeadPhis(); |
| 215 | |
| 216 | // 6) Now that the graph is correclty typed, we can get rid of redundant phis. |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 217 | // Note that we cannot do this phase before type propagation, otherwise |
| 218 | // we could get rid of phi equivalents, whose presence is a requirement for the |
| 219 | // type propagation phase. Note that this is to satisfy statement (a) of the |
| 220 | // SsaBuilder (see ssa_builder.h). |
| 221 | SsaRedundantPhiElimination redundant_phi(GetGraph()); |
| 222 | redundant_phi.Run(); |
| 223 | |
Nicolas Geoffray | b59dba0 | 2015-03-11 18:13:21 +0000 | [diff] [blame] | 224 | // 7) Make sure environments use the right phi "equivalent": a phi marked dead |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 225 | // can have a phi equivalent that is not dead. We must therefore update |
| 226 | // all environment uses of the dead phi to use its equivalent. Note that there |
| 227 | // can be multiple phis for the same Dex register that are live (for example |
| 228 | // when merging constants), in which case it is OK for the environments |
| 229 | // to just reference one. |
| 230 | for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { |
| 231 | HBasicBlock* block = it.Current(); |
| 232 | for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { |
| 233 | HPhi* phi = it_phis.Current()->AsPhi(); |
| 234 | // If the phi is not dead, or has no environment uses, there is nothing to do. |
| 235 | if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue; |
| 236 | HInstruction* next = phi->GetNext(); |
| 237 | if (!IsPhiEquivalentOf(next, phi)) continue; |
| 238 | if (next->AsPhi()->IsDead()) { |
| 239 | // If the phi equivalent is dead, check if there is another one. |
| 240 | next = next->GetNext(); |
| 241 | if (!IsPhiEquivalentOf(next, phi)) continue; |
| 242 | // There can be at most two phi equivalents. |
| 243 | DCHECK(!IsPhiEquivalentOf(next->GetNext(), phi)); |
| 244 | if (next->AsPhi()->IsDead()) continue; |
| 245 | } |
| 246 | // We found a live phi equivalent. Update the environment uses of `phi` with it. |
| 247 | phi->ReplaceWith(next); |
| 248 | } |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 249 | } |
| 250 | |
Nicolas Geoffray | b59dba0 | 2015-03-11 18:13:21 +0000 | [diff] [blame] | 251 | // 8) Deal with phis to guarantee liveness of phis in case of a debuggable |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 252 | // application. This is for satisfying statement (c) of the SsaBuilder |
| 253 | // (see ssa_builder.h). |
| 254 | if (GetGraph()->IsDebuggable()) { |
| 255 | DeadPhiHandling dead_phi_handler(GetGraph()); |
| 256 | dead_phi_handler.Run(); |
| 257 | } |
| 258 | |
Nicolas Geoffray | b59dba0 | 2015-03-11 18:13:21 +0000 | [diff] [blame] | 259 | // 9) Now that the right phis are used for the environments, and we |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 260 | // have potentially revive dead phis in case of a debuggable application, |
| 261 | // we can eliminate phis we do not need. Regardless of the debuggable status, |
| 262 | // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h), |
| 263 | // as well as for the code generation, which does not deal with phis of conflicting |
| 264 | // input types. |
| 265 | dead_phis.EliminateDeadPhis(); |
| 266 | |
Nicolas Geoffray | b59dba0 | 2015-03-11 18:13:21 +0000 | [diff] [blame] | 267 | // 10) Clear locals. |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 268 | for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 269 | !it.Done(); |
| 270 | it.Advance()) { |
| 271 | HInstruction* current = it.Current(); |
Roland Levillain | 476df55 | 2014-10-09 17:51:36 +0100 | [diff] [blame] | 272 | if (current->IsLocal()) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 273 | current->GetBlock()->RemoveInstruction(current); |
| 274 | } |
| 275 | } |
| 276 | } |
| 277 | |
| 278 | HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) { |
David Brazdil | ed59619 | 2015-01-23 10:39:45 +0000 | [diff] [blame] | 279 | return GetLocalsFor(block)->GetInstructionAt(local); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 280 | } |
| 281 | |
| 282 | void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { |
| 283 | current_locals_ = GetLocalsFor(block); |
| 284 | |
| 285 | if (block->IsLoopHeader()) { |
| 286 | // If the block is a loop header, we know we only have visited the pre header |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 287 | // because we are visiting in reverse post order. We create phis for all initialized |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 288 | // locals from the pre header. Their inputs will be populated at the end of |
| 289 | // the analysis. |
| 290 | for (size_t local = 0; local < current_locals_->Size(); local++) { |
| 291 | HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local); |
| 292 | if (incoming != nullptr) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 293 | HPhi* phi = new (GetGraph()->GetArena()) HPhi( |
| 294 | GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid); |
| 295 | block->AddPhi(phi); |
David Brazdil | ed59619 | 2015-01-23 10:39:45 +0000 | [diff] [blame] | 296 | current_locals_->SetRawEnvAt(local, phi); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 297 | } |
| 298 | } |
| 299 | // Save the loop header so that the last phase of the analysis knows which |
| 300 | // blocks need to be updated. |
| 301 | loop_headers_.Add(block); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 302 | } else if (block->GetPredecessors().Size() > 0) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 303 | // All predecessors have already been visited because we are visiting in reverse post order. |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 304 | // We merge the values of all locals, creating phis if those values differ. |
| 305 | for (size_t local = 0; local < current_locals_->Size(); local++) { |
Nicolas Geoffray | 7c3560f | 2014-06-04 12:12:08 +0100 | [diff] [blame] | 306 | bool one_predecessor_has_no_value = false; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 307 | bool is_different = false; |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 308 | HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(0), local); |
Nicolas Geoffray | 7c3560f | 2014-06-04 12:12:08 +0100 | [diff] [blame] | 309 | |
| 310 | for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { |
| 311 | HInstruction* current = ValueOfLocal(block->GetPredecessors().Get(i), local); |
| 312 | if (current == nullptr) { |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 313 | one_predecessor_has_no_value = true; |
| 314 | break; |
Nicolas Geoffray | 7c3560f | 2014-06-04 12:12:08 +0100 | [diff] [blame] | 315 | } else if (current != value) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 316 | is_different = true; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 317 | } |
| 318 | } |
Nicolas Geoffray | 7c3560f | 2014-06-04 12:12:08 +0100 | [diff] [blame] | 319 | |
| 320 | if (one_predecessor_has_no_value) { |
| 321 | // If one predecessor has no value for this local, we trust the verifier has |
| 322 | // successfully checked that there is a store dominating any read after this block. |
| 323 | continue; |
| 324 | } |
| 325 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 326 | if (is_different) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 327 | HPhi* phi = new (GetGraph()->GetArena()) HPhi( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 328 | GetGraph()->GetArena(), local, block->GetPredecessors().Size(), Primitive::kPrimVoid); |
| 329 | for (size_t i = 0; i < block->GetPredecessors().Size(); i++) { |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 330 | HInstruction* pred_value = ValueOfLocal(block->GetPredecessors().Get(i), local); |
| 331 | phi->SetRawInputAt(i, pred_value); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 332 | } |
| 333 | block->AddPhi(phi); |
| 334 | value = phi; |
| 335 | } |
David Brazdil | ed59619 | 2015-01-23 10:39:45 +0000 | [diff] [blame] | 336 | current_locals_->SetRawEnvAt(local, value); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 337 | } |
| 338 | } |
| 339 | |
| 340 | // Visit all instructions. The instructions of interest are: |
| 341 | // - HLoadLocal: replace them with the current value of the local. |
| 342 | // - HStoreLocal: update current value of the local and remove the instruction. |
| 343 | // - Instructions that require an environment: populate their environment |
| 344 | // with the current values of the locals. |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 345 | for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 346 | it.Current()->Accept(this); |
| 347 | } |
| 348 | } |
| 349 | |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 350 | /** |
| 351 | * Constants in the Dex format are not typed. So the builder types them as |
| 352 | * integers, but when doing the SSA form, we might realize the constant |
| 353 | * is used for floating point operations. We create a floating-point equivalent |
| 354 | * constant to make the operations correctly typed. |
| 355 | */ |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 356 | HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 357 | // We place the floating point constant next to this constant. |
| 358 | HFloatConstant* result = constant->GetNext()->AsFloatConstant(); |
| 359 | if (result == nullptr) { |
| 360 | HGraph* graph = constant->GetBlock()->GetGraph(); |
| 361 | ArenaAllocator* allocator = graph->GetArena(); |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 362 | result = new (allocator) HFloatConstant(bit_cast<float, int32_t>(constant->GetValue())); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 363 | constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); |
| 364 | } else { |
| 365 | // If there is already a constant with the expected type, we know it is |
| 366 | // the floating point equivalent of this constant. |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 367 | DCHECK_EQ((bit_cast<int32_t, float>(result->GetValue())), constant->GetValue()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 368 | } |
| 369 | return result; |
| 370 | } |
| 371 | |
| 372 | /** |
| 373 | * Wide constants in the Dex format are not typed. So the builder types them as |
| 374 | * longs, but when doing the SSA form, we might realize the constant |
| 375 | * is used for floating point operations. We create a floating-point equivalent |
| 376 | * constant to make the operations correctly typed. |
| 377 | */ |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 378 | HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 379 | // We place the floating point constant next to this constant. |
| 380 | HDoubleConstant* result = constant->GetNext()->AsDoubleConstant(); |
| 381 | if (result == nullptr) { |
| 382 | HGraph* graph = constant->GetBlock()->GetGraph(); |
| 383 | ArenaAllocator* allocator = graph->GetArena(); |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 384 | result = new (allocator) HDoubleConstant(bit_cast<double, int64_t>(constant->GetValue())); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 385 | constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); |
| 386 | } else { |
| 387 | // If there is already a constant with the expected type, we know it is |
| 388 | // the floating point equivalent of this constant. |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 389 | DCHECK_EQ((bit_cast<int64_t, double>(result->GetValue())), constant->GetValue()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 390 | } |
| 391 | return result; |
| 392 | } |
| 393 | |
| 394 | /** |
| 395 | * Because of Dex format, we might end up having the same phi being |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 396 | * used for non floating point operations and floating point / reference operations. |
| 397 | * Because we want the graph to be correctly typed (and thereafter avoid moves between |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 398 | * floating point registers and core registers), we need to create a copy of the |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 399 | * phi with a floating point / reference type. |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 400 | */ |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 401 | HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 402 | // We place the floating point /reference phi next to this phi. |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 403 | HInstruction* next = phi->GetNext(); |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 404 | if (next != nullptr |
| 405 | && next->AsPhi()->GetRegNumber() == phi->GetRegNumber() |
| 406 | && next->GetType() != type) { |
| 407 | // Move to the next phi to see if it is the one we are looking for. |
| 408 | next = next->GetNext(); |
| 409 | } |
| 410 | |
| 411 | if (next == nullptr |
| 412 | || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber()) |
| 413 | || (next->GetType() != type)) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 414 | ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena(); |
| 415 | HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type); |
| 416 | for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { |
| 417 | // Copy the inputs. Note that the graph may not be correctly typed by doing this copy, |
| 418 | // but the type propagation phase will fix it. |
| 419 | new_phi->SetRawInputAt(i, phi->InputAt(i)); |
| 420 | } |
| 421 | phi->GetBlock()->InsertPhiAfter(new_phi, phi); |
| 422 | return new_phi; |
| 423 | } else { |
Nicolas Geoffray | 21cc798 | 2014-11-17 17:50:33 +0000 | [diff] [blame] | 424 | DCHECK_EQ(next->GetType(), type); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 425 | return next->AsPhi(); |
| 426 | } |
| 427 | } |
| 428 | |
| 429 | HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user, |
| 430 | HInstruction* value, |
| 431 | Primitive::Type type) { |
| 432 | if (value->IsArrayGet()) { |
| 433 | // The verifier has checked that values in arrays cannot be used for both |
| 434 | // floating point and non-floating point operations. It is therefore safe to just |
| 435 | // change the type of the operation. |
| 436 | value->AsArrayGet()->SetType(type); |
| 437 | return value; |
| 438 | } else if (value->IsLongConstant()) { |
| 439 | return GetDoubleEquivalent(value->AsLongConstant()); |
| 440 | } else if (value->IsIntConstant()) { |
| 441 | return GetFloatEquivalent(value->AsIntConstant()); |
| 442 | } else if (value->IsPhi()) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 443 | return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 444 | } else { |
| 445 | // For other instructions, we assume the verifier has checked that the dex format is correctly |
| 446 | // typed and the value in a dex register will not be used for both floating point and |
| 447 | // non-floating point operations. So the only reason an instruction would want a floating |
| 448 | // point equivalent is for an unused phi that will be removed by the dead phi elimination phase. |
| 449 | DCHECK(user->IsPhi()); |
| 450 | return value; |
| 451 | } |
| 452 | } |
| 453 | |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 454 | HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 455 | if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 456 | return value->GetBlock()->GetGraph()->GetNullConstant(); |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 457 | } else if (value->IsPhi()) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 458 | return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot); |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 459 | } else { |
| 460 | return nullptr; |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 461 | } |
| 462 | } |
| 463 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 464 | void SsaBuilder::VisitLoadLocal(HLoadLocal* load) { |
David Brazdil | ed59619 | 2015-01-23 10:39:45 +0000 | [diff] [blame] | 465 | HInstruction* value = current_locals_->GetInstructionAt(load->GetLocal()->GetRegNumber()); |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 466 | // If the operation requests a specific type, we make sure its input is of that type. |
| 467 | if (load->GetType() != value->GetType()) { |
| 468 | if (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble) { |
| 469 | value = GetFloatOrDoubleEquivalent(load, value, load->GetType()); |
| 470 | } else if (load->GetType() == Primitive::kPrimNot) { |
| 471 | value = GetReferenceTypeEquivalent(value); |
| 472 | } |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 473 | } |
| 474 | load->ReplaceWith(value); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 475 | load->GetBlock()->RemoveInstruction(load); |
| 476 | } |
| 477 | |
| 478 | void SsaBuilder::VisitStoreLocal(HStoreLocal* store) { |
David Brazdil | ed59619 | 2015-01-23 10:39:45 +0000 | [diff] [blame] | 479 | current_locals_->SetRawEnvAt(store->GetLocal()->GetRegNumber(), store->InputAt(1)); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 480 | store->GetBlock()->RemoveInstruction(store); |
| 481 | } |
| 482 | |
| 483 | void SsaBuilder::VisitInstruction(HInstruction* instruction) { |
| 484 | if (!instruction->NeedsEnvironment()) { |
| 485 | return; |
| 486 | } |
| 487 | HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment( |
| 488 | GetGraph()->GetArena(), current_locals_->Size()); |
David Brazdil | ed59619 | 2015-01-23 10:39:45 +0000 | [diff] [blame] | 489 | environment->CopyFrom(current_locals_); |
Nicolas Geoffray | 3dcd58c | 2015-04-03 11:02:38 +0100 | [diff] [blame] | 490 | instruction->SetRawEnvironment(environment); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 491 | } |
| 492 | |
Nicolas Geoffray | 421e9f9 | 2014-11-11 18:21:53 +0000 | [diff] [blame] | 493 | void SsaBuilder::VisitTemporary(HTemporary* temp) { |
| 494 | // Temporaries are only used by the baseline register allocator. |
| 495 | temp->GetBlock()->RemoveInstruction(temp); |
| 496 | } |
| 497 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 498 | } // namespace art |