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" |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 20 | #include "reference_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 | |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 25 | void SsaBuilder::SetLoopHeaderPhiInputs() { |
| 26 | for (size_t i = loop_headers_.size(); i > 0; --i) { |
| 27 | HBasicBlock* block = loop_headers_[i - 1]; |
| 28 | for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { |
| 29 | HPhi* phi = it.Current()->AsPhi(); |
| 30 | size_t vreg = phi->GetRegNumber(); |
| 31 | for (HBasicBlock* predecessor : block->GetPredecessors()) { |
| 32 | HInstruction* value = ValueOfLocal(predecessor, vreg); |
| 33 | if (value == nullptr) { |
| 34 | // Vreg is undefined at this predecessor. Mark it dead and leave with |
| 35 | // fewer inputs than predecessors. SsaChecker will fail if not removed. |
| 36 | phi->SetDead(); |
| 37 | break; |
| 38 | } else { |
| 39 | phi->AddInput(value); |
| 40 | } |
| 41 | } |
| 42 | } |
| 43 | } |
| 44 | } |
| 45 | |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 46 | void SsaBuilder::FixNullConstantType() { |
| 47 | // The order doesn't matter here. |
| 48 | for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) { |
| 49 | for (HInstructionIterator it(itb.Current()->GetInstructions()); !it.Done(); it.Advance()) { |
| 50 | HInstruction* equality_instr = it.Current(); |
| 51 | if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) { |
| 52 | continue; |
| 53 | } |
| 54 | HInstruction* left = equality_instr->InputAt(0); |
| 55 | HInstruction* right = equality_instr->InputAt(1); |
Nicolas Geoffray | 51d400d | 2015-06-15 09:01:08 +0100 | [diff] [blame] | 56 | HInstruction* int_operand = nullptr; |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 57 | |
Nicolas Geoffray | 51d400d | 2015-06-15 09:01:08 +0100 | [diff] [blame] | 58 | if ((left->GetType() == Primitive::kPrimNot) && (right->GetType() == Primitive::kPrimInt)) { |
| 59 | int_operand = right; |
| 60 | } else if ((right->GetType() == Primitive::kPrimNot) |
| 61 | && (left->GetType() == Primitive::kPrimInt)) { |
| 62 | int_operand = left; |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 63 | } else { |
| 64 | continue; |
| 65 | } |
| 66 | |
| 67 | // If we got here, we are comparing against a reference and the int constant |
| 68 | // should be replaced with a null constant. |
Nicolas Geoffray | 51d400d | 2015-06-15 09:01:08 +0100 | [diff] [blame] | 69 | // Both type propagation and redundant phi elimination ensure `int_operand` |
| 70 | // can only be the 0 constant. |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 71 | DCHECK(int_operand->IsIntConstant()) << int_operand->DebugName(); |
Nicolas Geoffray | 51d400d | 2015-06-15 09:01:08 +0100 | [diff] [blame] | 72 | DCHECK_EQ(0, int_operand->AsIntConstant()->GetValue()); |
| 73 | equality_instr->ReplaceInput(GetGraph()->GetNullConstant(), int_operand == right ? 1 : 0); |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 74 | } |
| 75 | } |
| 76 | } |
| 77 | |
| 78 | void SsaBuilder::EquivalentPhisCleanup() { |
| 79 | // The order doesn't matter here. |
| 80 | for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) { |
| 81 | for (HInstructionIterator it(itb.Current()->GetPhis()); !it.Done(); it.Advance()) { |
| 82 | HPhi* phi = it.Current()->AsPhi(); |
| 83 | HPhi* next = phi->GetNextEquivalentPhiWithSameType(); |
| 84 | if (next != nullptr) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 85 | // Make sure we do not replace a live phi with a dead phi. A live phi |
| 86 | // has been handled by the type propagation phase, unlike a dead phi. |
Nicolas Geoffray | 4230e18 | 2015-06-29 14:34:46 +0100 | [diff] [blame] | 87 | if (next->IsLive()) { |
| 88 | phi->ReplaceWith(next); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 89 | phi->SetDead(); |
Nicolas Geoffray | 4230e18 | 2015-06-29 14:34:46 +0100 | [diff] [blame] | 90 | } else { |
| 91 | next->ReplaceWith(phi); |
| 92 | } |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 93 | DCHECK(next->GetNextEquivalentPhiWithSameType() == nullptr) |
| 94 | << "More then one phi equivalent with type " << phi->GetType() |
| 95 | << " found for phi" << phi->GetId(); |
| 96 | } |
| 97 | } |
| 98 | } |
| 99 | } |
| 100 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 101 | void SsaBuilder::FixEnvironmentPhis() { |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 102 | for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { |
| 103 | HBasicBlock* block = it.Current(); |
| 104 | for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { |
| 105 | HPhi* phi = it_phis.Current()->AsPhi(); |
| 106 | // If the phi is not dead, or has no environment uses, there is nothing to do. |
| 107 | if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue; |
| 108 | HInstruction* next = phi->GetNext(); |
David Brazdil | d0180f9 | 2015-09-22 14:39:58 +0100 | [diff] [blame] | 109 | if (!phi->IsVRegEquivalentOf(next)) continue; |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 110 | if (next->AsPhi()->IsDead()) { |
| 111 | // If the phi equivalent is dead, check if there is another one. |
| 112 | next = next->GetNext(); |
David Brazdil | d0180f9 | 2015-09-22 14:39:58 +0100 | [diff] [blame] | 113 | if (!phi->IsVRegEquivalentOf(next)) continue; |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 114 | // There can be at most two phi equivalents. |
David Brazdil | d0180f9 | 2015-09-22 14:39:58 +0100 | [diff] [blame] | 115 | DCHECK(!phi->IsVRegEquivalentOf(next->GetNext())); |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 116 | if (next->AsPhi()->IsDead()) continue; |
| 117 | } |
| 118 | // We found a live phi equivalent. Update the environment uses of `phi` with it. |
| 119 | phi->ReplaceWith(next); |
| 120 | } |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 121 | } |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 122 | } |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 123 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 124 | static void AddDependentInstructionsToWorklist(HInstruction* instruction, |
| 125 | ArenaVector<HPhi*>* worklist) { |
| 126 | // If `instruction` is a dead phi, type conflict was just identified. All its |
| 127 | // live phi users, and transitively users of those users, therefore need to be |
| 128 | // marked dead/conflicting too, so we add them to the worklist. Otherwise we |
| 129 | // add users whose type does not match and needs to be updated. |
| 130 | bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead(); |
| 131 | for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { |
| 132 | HInstruction* user = it.Current()->GetUser(); |
| 133 | if (user->IsPhi() && user->AsPhi()->IsLive()) { |
| 134 | if (add_all_live_phis || user->GetType() != instruction->GetType()) { |
| 135 | worklist->push_back(user->AsPhi()); |
| 136 | } |
| 137 | } |
| 138 | } |
| 139 | } |
| 140 | |
| 141 | // Find a candidate primitive type for `phi` by merging the type of its inputs. |
| 142 | // Return false if conflict is identified. |
| 143 | static bool TypePhiFromInputs(HPhi* phi) { |
| 144 | Primitive::Type common_type = phi->GetType(); |
| 145 | |
| 146 | for (HInputIterator it(phi); !it.Done(); it.Advance()) { |
| 147 | HInstruction* input = it.Current(); |
| 148 | if (input->IsPhi() && input->AsPhi()->IsDead()) { |
| 149 | // Phis are constructed live so if an input is a dead phi, it must have |
| 150 | // been made dead due to type conflict. Mark this phi conflicting too. |
| 151 | return false; |
| 152 | } |
| 153 | |
| 154 | Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); |
| 155 | if (common_type == input_type) { |
| 156 | // No change in type. |
David Brazdil | d87f3ea | 2016-01-04 15:55:10 +0000 | [diff] [blame] | 157 | } else if (Primitive::Is64BitType(common_type) != Primitive::Is64BitType(input_type)) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 158 | // Types are of different sizes, e.g. int vs. long. Must be a conflict. |
| 159 | return false; |
| 160 | } else if (Primitive::IsIntegralType(common_type)) { |
| 161 | // Previous inputs were integral, this one is not but is of the same size. |
| 162 | // This does not imply conflict since some bytecode instruction types are |
| 163 | // ambiguous. TypeInputsOfPhi will either type them or detect a conflict. |
| 164 | DCHECK(Primitive::IsFloatingPointType(input_type) || input_type == Primitive::kPrimNot); |
| 165 | common_type = input_type; |
| 166 | } else if (Primitive::IsIntegralType(input_type)) { |
| 167 | // Input is integral, common type is not. Same as in the previous case, if |
| 168 | // there is a conflict, it will be detected during TypeInputsOfPhi. |
| 169 | DCHECK(Primitive::IsFloatingPointType(common_type) || common_type == Primitive::kPrimNot); |
| 170 | } else { |
| 171 | // Combining float and reference types. Clearly a conflict. |
| 172 | DCHECK((common_type == Primitive::kPrimFloat && input_type == Primitive::kPrimNot) || |
| 173 | (common_type == Primitive::kPrimNot && input_type == Primitive::kPrimFloat)); |
| 174 | return false; |
| 175 | } |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 176 | } |
| 177 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 178 | // We have found a candidate type for the phi. Set it and return true. We may |
| 179 | // still discover conflict whilst typing the individual inputs in TypeInputsOfPhi. |
| 180 | phi->SetType(common_type); |
| 181 | return true; |
| 182 | } |
David Brazdil | d9510df | 2015-11-04 23:30:22 +0000 | [diff] [blame] | 183 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 184 | // Replace inputs of `phi` to match its type. Return false if conflict is identified. |
| 185 | bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) { |
| 186 | Primitive::Type common_type = phi->GetType(); |
| 187 | if (common_type == Primitive::kPrimVoid || Primitive::IsIntegralType(common_type)) { |
| 188 | // Phi either contains only other untyped phis (common_type == kPrimVoid), |
| 189 | // or `common_type` is integral and we do not need to retype ambiguous inputs |
| 190 | // because they are always constructed with the integral type candidate. |
| 191 | if (kIsDebugBuild) { |
| 192 | for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { |
| 193 | HInstruction* input = phi->InputAt(i); |
| 194 | if (common_type == Primitive::kPrimVoid) { |
| 195 | DCHECK(input->IsPhi() && input->GetType() == Primitive::kPrimVoid); |
| 196 | } else { |
| 197 | DCHECK((input->IsPhi() && input->GetType() == Primitive::kPrimVoid) || |
| 198 | HPhi::ToPhiType(input->GetType()) == common_type); |
| 199 | } |
| 200 | } |
| 201 | } |
| 202 | // Inputs did not need to be replaced, hence no conflict. Report success. |
| 203 | return true; |
| 204 | } else { |
| 205 | DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type)); |
| 206 | for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { |
| 207 | HInstruction* input = phi->InputAt(i); |
| 208 | if (input->GetType() != common_type) { |
| 209 | // Input type does not match phi's type. Try to retype the input or |
| 210 | // generate a suitably typed equivalent. |
| 211 | HInstruction* equivalent = (common_type == Primitive::kPrimNot) |
| 212 | ? GetReferenceTypeEquivalent(input) |
| 213 | : GetFloatOrDoubleEquivalent(input, common_type); |
| 214 | if (equivalent == nullptr) { |
| 215 | // Input could not be typed. Report conflict. |
| 216 | return false; |
| 217 | } |
| 218 | // Make sure the input did not change its type and we do not need to |
| 219 | // update its users. |
| 220 | DCHECK_NE(input, equivalent); |
| 221 | |
| 222 | phi->ReplaceInput(equivalent, i); |
| 223 | if (equivalent->IsPhi()) { |
| 224 | worklist->push_back(equivalent->AsPhi()); |
| 225 | } |
| 226 | } |
| 227 | } |
| 228 | // All inputs either matched the type of the phi or we successfully replaced |
| 229 | // them with a suitable equivalent. Report success. |
| 230 | return true; |
| 231 | } |
| 232 | } |
| 233 | |
| 234 | // Attempt to set the primitive type of `phi` to match its inputs. Return whether |
| 235 | // it was changed by the algorithm or not. |
| 236 | bool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist) { |
| 237 | DCHECK(phi->IsLive()); |
| 238 | Primitive::Type original_type = phi->GetType(); |
| 239 | |
| 240 | // Try to type the phi in two stages: |
| 241 | // (1) find a candidate type for the phi by merging types of all its inputs, |
| 242 | // (2) try to type the phi's inputs to that candidate type. |
| 243 | // Either of these stages may detect a type conflict and fail, in which case |
| 244 | // we immediately abort. |
| 245 | if (!TypePhiFromInputs(phi) || !TypeInputsOfPhi(phi, worklist)) { |
| 246 | // Conflict detected. Mark the phi dead and return true because it changed. |
| 247 | phi->SetDead(); |
| 248 | return true; |
| 249 | } |
| 250 | |
| 251 | // Return true if the type of the phi has changed. |
| 252 | return phi->GetType() != original_type; |
| 253 | } |
| 254 | |
| 255 | void SsaBuilder::RunPrimitiveTypePropagation() { |
| 256 | ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter()); |
| 257 | |
| 258 | for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { |
| 259 | HBasicBlock* block = it.Current(); |
| 260 | if (block->IsLoopHeader()) { |
| 261 | for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { |
| 262 | HPhi* phi = phi_it.Current()->AsPhi(); |
| 263 | if (phi->IsLive()) { |
| 264 | worklist.push_back(phi); |
| 265 | } |
| 266 | } |
| 267 | } else { |
| 268 | for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { |
| 269 | // Eagerly compute the type of the phi, for quicker convergence. Note |
| 270 | // that we don't need to add users to the worklist because we are |
| 271 | // doing a reverse post-order visit, therefore either the phi users are |
| 272 | // non-loop phi and will be visited later in the visit, or are loop-phis, |
| 273 | // and they are already in the work list. |
| 274 | HPhi* phi = phi_it.Current()->AsPhi(); |
| 275 | if (phi->IsLive()) { |
| 276 | UpdatePrimitiveType(phi, &worklist); |
| 277 | } |
| 278 | } |
| 279 | } |
| 280 | } |
| 281 | |
| 282 | ProcessPrimitiveTypePropagationWorklist(&worklist); |
| 283 | EquivalentPhisCleanup(); |
| 284 | } |
| 285 | |
| 286 | void SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist) { |
| 287 | // Process worklist |
| 288 | while (!worklist->empty()) { |
| 289 | HPhi* phi = worklist->back(); |
| 290 | worklist->pop_back(); |
| 291 | // The phi could have been made dead as a result of conflicts while in the |
| 292 | // worklist. If it is now dead, there is no point in updating its type. |
| 293 | if (phi->IsLive() && UpdatePrimitiveType(phi, worklist)) { |
| 294 | AddDependentInstructionsToWorklist(phi, worklist); |
| 295 | } |
| 296 | } |
| 297 | } |
| 298 | |
| 299 | static HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { |
| 300 | Primitive::Type type = aget->GetType(); |
| 301 | DCHECK(Primitive::IsIntOrLongType(type)); |
| 302 | HArrayGet* next = aget->GetNext()->AsArrayGet(); |
| 303 | return (next != nullptr && next->IsEquivalentOf(aget)) ? next : nullptr; |
| 304 | } |
| 305 | |
| 306 | static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { |
| 307 | Primitive::Type type = aget->GetType(); |
| 308 | DCHECK(Primitive::IsIntOrLongType(type)); |
| 309 | DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr); |
| 310 | |
| 311 | HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetArena()) HArrayGet( |
| 312 | aget->GetArray(), |
| 313 | aget->GetIndex(), |
| 314 | type == Primitive::kPrimInt ? Primitive::kPrimFloat : Primitive::kPrimDouble, |
| 315 | aget->GetDexPc()); |
| 316 | aget->GetBlock()->InsertInstructionAfter(equivalent, aget); |
| 317 | return equivalent; |
| 318 | } |
| 319 | |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 320 | static Primitive::Type GetPrimitiveArrayComponentType(HInstruction* array) |
| 321 | SHARED_REQUIRES(Locks::mutator_lock_) { |
| 322 | ReferenceTypeInfo array_type = array->GetReferenceTypeInfo(); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 323 | DCHECK(array_type.IsPrimitiveArrayClass()); |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 324 | return array_type.GetTypeHandle()->GetComponentType()->GetPrimitiveType(); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 325 | } |
| 326 | |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 327 | bool SsaBuilder::FixAmbiguousArrayOps() { |
| 328 | if (ambiguous_agets_.empty() && ambiguous_asets_.empty()) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 329 | return true; |
| 330 | } |
| 331 | |
| 332 | // The wrong ArrayGet equivalent may still have Phi uses coming from ArraySet |
| 333 | // uses (because they are untyped) and environment uses (if --debuggable). |
| 334 | // After resolving all ambiguous ArrayGets, we will re-run primitive type |
| 335 | // propagation on the Phis which need to be updated. |
| 336 | ArenaVector<HPhi*> worklist(GetGraph()->GetArena()->Adapter()); |
| 337 | |
| 338 | { |
| 339 | ScopedObjectAccess soa(Thread::Current()); |
| 340 | |
| 341 | for (HArrayGet* aget_int : ambiguous_agets_) { |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 342 | HInstruction* array = aget_int->GetArray(); |
| 343 | if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 344 | // RTP did not type the input array. Bail. |
| 345 | return false; |
| 346 | } |
| 347 | |
| 348 | HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int); |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 349 | Primitive::Type array_type = GetPrimitiveArrayComponentType(array); |
| 350 | DCHECK_EQ(Primitive::Is64BitType(aget_int->GetType()), Primitive::Is64BitType(array_type)); |
| 351 | |
| 352 | if (Primitive::IsIntOrLongType(array_type)) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 353 | if (aget_float != nullptr) { |
| 354 | // There is a float/double equivalent. We must replace it and re-run |
| 355 | // primitive type propagation on all dependent instructions. |
| 356 | aget_float->ReplaceWith(aget_int); |
| 357 | aget_float->GetBlock()->RemoveInstruction(aget_float); |
| 358 | AddDependentInstructionsToWorklist(aget_int, &worklist); |
| 359 | } |
| 360 | } else { |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 361 | DCHECK(Primitive::IsFloatingPointType(array_type)); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 362 | if (aget_float == nullptr) { |
| 363 | // This is a float/double ArrayGet but there were no typed uses which |
| 364 | // would create the typed equivalent. Create it now. |
| 365 | aget_float = CreateFloatOrDoubleEquivalentOfArrayGet(aget_int); |
| 366 | } |
| 367 | // Replace the original int/long instruction. Note that it may have phi |
| 368 | // uses, environment uses, as well as real uses (from untyped ArraySets). |
| 369 | // We need to re-run primitive type propagation on its dependent instructions. |
| 370 | aget_int->ReplaceWith(aget_float); |
| 371 | aget_int->GetBlock()->RemoveInstruction(aget_int); |
| 372 | AddDependentInstructionsToWorklist(aget_float, &worklist); |
| 373 | } |
| 374 | } |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 375 | |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 376 | // Set a flag stating that types of ArrayGets have been resolved. Requesting |
| 377 | // equivalent of the wrong type with GetFloatOrDoubleEquivalentOfArrayGet |
| 378 | // will fail from now on. |
| 379 | agets_fixed_ = true; |
| 380 | |
| 381 | for (HArraySet* aset : ambiguous_asets_) { |
| 382 | HInstruction* array = aset->GetArray(); |
| 383 | if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { |
| 384 | // RTP did not type the input array. Bail. |
| 385 | return false; |
| 386 | } |
| 387 | |
| 388 | HInstruction* value = aset->GetValue(); |
| 389 | Primitive::Type value_type = value->GetType(); |
| 390 | Primitive::Type array_type = GetPrimitiveArrayComponentType(array); |
| 391 | DCHECK_EQ(Primitive::Is64BitType(value_type), Primitive::Is64BitType(array_type)); |
| 392 | |
| 393 | if (Primitive::IsFloatingPointType(array_type)) { |
| 394 | if (!Primitive::IsFloatingPointType(value_type)) { |
| 395 | DCHECK(Primitive::IsIntegralType(value_type)); |
| 396 | // Array elements are floating-point but the value has not been replaced |
| 397 | // with its floating-point equivalent. The replacement must always |
| 398 | // succeed in code validated by the verifier. |
| 399 | HInstruction* equivalent = GetFloatOrDoubleEquivalent(value, array_type); |
| 400 | DCHECK(equivalent != nullptr); |
| 401 | aset->ReplaceInput(equivalent, /* input_index */ 2); |
| 402 | if (equivalent->IsPhi()) { |
| 403 | // Returned equivalent is a phi which may not have had its inputs |
| 404 | // replaced yet. We need to run primitive type propagation on it. |
| 405 | worklist.push_back(equivalent->AsPhi()); |
| 406 | } |
| 407 | } |
| 408 | } else { |
| 409 | // Array elements are integral and the value assigned to it initially |
| 410 | // was integral too. Nothing to do. |
| 411 | DCHECK(Primitive::IsIntegralType(array_type)); |
| 412 | DCHECK(Primitive::IsIntegralType(value_type)); |
| 413 | } |
| 414 | } |
| 415 | } |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 416 | |
| 417 | if (!worklist.empty()) { |
| 418 | ProcessPrimitiveTypePropagationWorklist(&worklist); |
| 419 | EquivalentPhisCleanup(); |
| 420 | } |
| 421 | |
| 422 | return true; |
| 423 | } |
| 424 | |
Nicolas Geoffray | 98e6ce4 | 2016-02-16 18:42:15 +0000 | [diff] [blame] | 425 | static bool HasAliasInEnvironments(HInstruction* instruction) { |
| 426 | for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses()); |
| 427 | !use_it.Done(); |
| 428 | use_it.Advance()) { |
| 429 | HEnvironment* use = use_it.Current()->GetUser(); |
| 430 | HUseListNode<HEnvironment*>* next = use_it.Current()->GetNext(); |
| 431 | if (next != nullptr && next->GetUser() == use) { |
| 432 | return true; |
| 433 | } |
| 434 | } |
| 435 | |
| 436 | if (kIsDebugBuild) { |
| 437 | // Do a quadratic search to ensure same environment uses are next |
| 438 | // to each other. |
| 439 | for (HUseIterator<HEnvironment*> use_it(instruction->GetEnvUses()); |
| 440 | !use_it.Done(); |
| 441 | use_it.Advance()) { |
| 442 | HUseListNode<HEnvironment*>* current = use_it.Current(); |
| 443 | HUseListNode<HEnvironment*>* next = current->GetNext(); |
| 444 | while (next != nullptr) { |
| 445 | DCHECK(next->GetUser() != current->GetUser()); |
| 446 | next = next->GetNext(); |
| 447 | } |
| 448 | } |
| 449 | } |
| 450 | return false; |
| 451 | } |
| 452 | |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 453 | void SsaBuilder::RemoveRedundantUninitializedStrings() { |
| 454 | if (GetGraph()->IsDebuggable()) { |
| 455 | // Do not perform the optimization for consistency with the interpreter |
| 456 | // which always allocates an object for new-instance of String. |
| 457 | return; |
| 458 | } |
| 459 | |
| 460 | for (HNewInstance* new_instance : uninitialized_strings_) { |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 461 | // Replace NewInstance of String with NullConstant if not used prior to |
| 462 | // calling StringFactory. In case of deoptimization, the interpreter is |
| 463 | // expected to skip null check on the `this` argument of the StringFactory call. |
Nicolas Geoffray | 98e6ce4 | 2016-02-16 18:42:15 +0000 | [diff] [blame] | 464 | if (!new_instance->HasNonEnvironmentUses() && !HasAliasInEnvironments(new_instance)) { |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 465 | new_instance->ReplaceWith(GetGraph()->GetNullConstant()); |
| 466 | new_instance->GetBlock()->RemoveInstruction(new_instance); |
| 467 | |
| 468 | // Remove LoadClass if not needed any more. |
Nicolas Geoffray | 5e08e36 | 2016-02-15 15:56:11 +0000 | [diff] [blame] | 469 | HInstruction* input = new_instance->InputAt(0); |
| 470 | HLoadClass* load_class = nullptr; |
| 471 | |
| 472 | // If the class was not present in the dex cache at the point of building |
| 473 | // the graph, the builder inserted a HClinitCheck in between. Since the String |
| 474 | // class is always initialized at the point of running Java code, we can remove |
| 475 | // that check. |
| 476 | if (input->IsClinitCheck()) { |
| 477 | load_class = input->InputAt(0)->AsLoadClass(); |
| 478 | input->ReplaceWith(load_class); |
| 479 | input->GetBlock()->RemoveInstruction(input); |
| 480 | } else { |
| 481 | load_class = input->AsLoadClass(); |
| 482 | DCHECK(new_instance->IsStringAlloc()); |
| 483 | DCHECK(!load_class->NeedsAccessCheck()) << "String class is always accessible"; |
| 484 | } |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 485 | DCHECK(load_class != nullptr); |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 486 | if (!load_class->HasUses()) { |
Nicolas Geoffray | 5e08e36 | 2016-02-15 15:56:11 +0000 | [diff] [blame] | 487 | // Even if the HLoadClass needs access check, we can remove it, as we know the |
| 488 | // String class does not need it. |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 489 | load_class->GetBlock()->RemoveInstruction(load_class); |
| 490 | } |
| 491 | } |
| 492 | } |
| 493 | } |
| 494 | |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 495 | GraphAnalysisResult SsaBuilder::BuildSsa() { |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 496 | DCHECK(!GetGraph()->IsInSsaForm()); |
| 497 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 498 | // 1) Visit in reverse post order. We need to have all predecessors of a block |
| 499 | // visited (with the exception of loops) in order to create the right environment |
| 500 | // for that block. For loops, we create phis whose inputs will be set in 2). |
| 501 | for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { |
| 502 | VisitBasicBlock(it.Current()); |
| 503 | } |
| 504 | |
| 505 | // 2) Set inputs of loop header phis. |
| 506 | SetLoopHeaderPhiInputs(); |
| 507 | |
| 508 | // 3) Propagate types of phis. At this point, phis are typed void in the general |
| 509 | // case, or float/double/reference if we created an equivalent phi. So we need |
| 510 | // to propagate the types across phis to give them a correct type. If a type |
| 511 | // conflict is detected in this stage, the phi is marked dead. |
| 512 | RunPrimitiveTypePropagation(); |
| 513 | |
| 514 | // 4) Now that the correct primitive types have been assigned, we can get rid |
| 515 | // of redundant phis. Note that we cannot do this phase before type propagation, |
| 516 | // otherwise we could get rid of phi equivalents, whose presence is a requirement |
| 517 | // for the type propagation phase. Note that this is to satisfy statement (a) |
| 518 | // of the SsaBuilder (see ssa_builder.h). |
| 519 | SsaRedundantPhiElimination(GetGraph()).Run(); |
| 520 | |
| 521 | // 5) Fix the type for null constants which are part of an equality comparison. |
| 522 | // We need to do this after redundant phi elimination, to ensure the only cases |
| 523 | // that we can see are reference comparison against 0. The redundant phi |
| 524 | // elimination ensures we do not see a phi taking two 0 constants in a HEqual |
| 525 | // or HNotEqual. |
| 526 | FixNullConstantType(); |
| 527 | |
| 528 | // 6) Compute type of reference type instructions. The pass assumes that |
| 529 | // NullConstant has been fixed up. |
Nicolas Geoffray | d9994f0 | 2016-02-11 17:35:55 +0000 | [diff] [blame] | 530 | ReferenceTypePropagation(GetGraph(), handles_, /* is_first_run */ true).Run(); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 531 | |
| 532 | // 7) Step 1) duplicated ArrayGet instructions with ambiguous type (int/float |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 533 | // or long/double) and marked ArraySets with ambiguous input type. Now that RTP |
| 534 | // computed the type of the array input, the ambiguity can be resolved and the |
| 535 | // correct equivalents kept. |
| 536 | if (!FixAmbiguousArrayOps()) { |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 537 | return kAnalysisFailAmbiguousArrayOp; |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 538 | } |
| 539 | |
| 540 | // 8) Mark dead phis. This will mark phis which are not used by instructions |
| 541 | // or other live phis. If compiling as debuggable code, phis will also be kept |
| 542 | // live if they have an environment use. |
| 543 | SsaDeadPhiElimination dead_phi_elimimation(GetGraph()); |
| 544 | dead_phi_elimimation.MarkDeadPhis(); |
| 545 | |
| 546 | // 9) Make sure environments use the right phi equivalent: a phi marked dead |
| 547 | // can have a phi equivalent that is not dead. In that case we have to replace |
| 548 | // it with the live equivalent because deoptimization and try/catch rely on |
| 549 | // environments containing values of all live vregs at that point. Note that |
| 550 | // there can be multiple phis for the same Dex register that are live |
| 551 | // (for example when merging constants), in which case it is okay for the |
| 552 | // environments to just reference one. |
| 553 | FixEnvironmentPhis(); |
| 554 | |
| 555 | // 10) Now that the right phis are used for the environments, we can eliminate |
| 556 | // phis we do not need. Regardless of the debuggable status, this phase is |
| 557 | /// necessary for statement (b) of the SsaBuilder (see ssa_builder.h), as well |
| 558 | // as for the code generation, which does not deal with phis of conflicting |
| 559 | // input types. |
| 560 | dead_phi_elimimation.EliminateDeadPhis(); |
| 561 | |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 562 | // 11) Step 1) replaced uses of NewInstances of String with the results of |
| 563 | // their corresponding StringFactory calls. Unless the String objects are used |
| 564 | // before they are initialized, they can be replaced with NullConstant. |
| 565 | // Note that this optimization is valid only if unsimplified code does not use |
| 566 | // the uninitialized value because we assume execution can be deoptimized at |
| 567 | // any safepoint. We must therefore perform it before any other optimizations. |
| 568 | RemoveRedundantUninitializedStrings(); |
| 569 | |
| 570 | // 12) Clear locals. |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 571 | for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 572 | !it.Done(); |
| 573 | it.Advance()) { |
| 574 | HInstruction* current = it.Current(); |
Roland Levillain | 476df55 | 2014-10-09 17:51:36 +0100 | [diff] [blame] | 575 | if (current->IsLocal()) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 576 | current->GetBlock()->RemoveInstruction(current); |
| 577 | } |
| 578 | } |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 579 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 580 | GetGraph()->SetInSsaForm(); |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 581 | return kAnalysisSuccess; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 582 | } |
| 583 | |
David Brazdil | eead071 | 2015-09-18 14:58:57 +0100 | [diff] [blame] | 584 | ArenaVector<HInstruction*>* SsaBuilder::GetLocalsFor(HBasicBlock* block) { |
David Brazdil | eead071 | 2015-09-18 14:58:57 +0100 | [diff] [blame] | 585 | ArenaVector<HInstruction*>* locals = &locals_for_[block->GetBlockId()]; |
| 586 | const size_t vregs = GetGraph()->GetNumberOfVRegs(); |
| 587 | if (locals->empty() && vregs != 0u) { |
| 588 | locals->resize(vregs, nullptr); |
| 589 | |
| 590 | if (block->IsCatchBlock()) { |
| 591 | ArenaAllocator* arena = GetGraph()->GetArena(); |
| 592 | // We record incoming inputs of catch phis at throwing instructions and |
| 593 | // must therefore eagerly create the phis. Phis for undefined vregs will |
| 594 | // be deleted when the first throwing instruction with the vreg undefined |
| 595 | // is encountered. Unused phis will be removed by dead phi analysis. |
| 596 | for (size_t i = 0; i < vregs; ++i) { |
| 597 | // No point in creating the catch phi if it is already undefined at |
| 598 | // the first throwing instruction. |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 599 | HInstruction* current_local_value = (*current_locals_)[i]; |
| 600 | if (current_local_value != nullptr) { |
| 601 | HPhi* phi = new (arena) HPhi( |
| 602 | arena, |
| 603 | i, |
| 604 | 0, |
| 605 | current_local_value->GetType()); |
David Brazdil | eead071 | 2015-09-18 14:58:57 +0100 | [diff] [blame] | 606 | block->AddPhi(phi); |
| 607 | (*locals)[i] = phi; |
| 608 | } |
| 609 | } |
| 610 | } |
| 611 | } |
| 612 | return locals; |
| 613 | } |
| 614 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 615 | HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) { |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 616 | ArenaVector<HInstruction*>* locals = GetLocalsFor(block); |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 617 | return (*locals)[local]; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 618 | } |
| 619 | |
| 620 | void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { |
| 621 | current_locals_ = GetLocalsFor(block); |
| 622 | |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 623 | if (block->IsCatchBlock()) { |
| 624 | // Catch phis were already created and inputs collected from throwing sites. |
David Brazdil | d0180f9 | 2015-09-22 14:39:58 +0100 | [diff] [blame] | 625 | if (kIsDebugBuild) { |
| 626 | // Make sure there was at least one throwing instruction which initialized |
| 627 | // locals (guaranteed by HGraphBuilder) and that all try blocks have been |
| 628 | // visited already (from HTryBoundary scoping and reverse post order). |
| 629 | bool throwing_instruction_found = false; |
| 630 | bool catch_block_visited = false; |
| 631 | for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { |
| 632 | HBasicBlock* current = it.Current(); |
| 633 | if (current == block) { |
| 634 | catch_block_visited = true; |
| 635 | } else if (current->IsTryBlock() && |
| 636 | current->GetTryCatchInformation()->GetTryEntry().HasExceptionHandler(*block)) { |
| 637 | DCHECK(!catch_block_visited) << "Catch block visited before its try block."; |
| 638 | throwing_instruction_found |= current->HasThrowingInstructions(); |
| 639 | } |
| 640 | } |
| 641 | DCHECK(throwing_instruction_found) << "No instructions throwing into a live catch block."; |
| 642 | } |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 643 | } else if (block->IsLoopHeader()) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 644 | // 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] | 645 | // 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] | 646 | // locals from the pre header. Their inputs will be populated at the end of |
| 647 | // the analysis. |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 648 | for (size_t local = 0; local < current_locals_->size(); ++local) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 649 | HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local); |
| 650 | if (incoming != nullptr) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 651 | HPhi* phi = new (GetGraph()->GetArena()) HPhi( |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 652 | GetGraph()->GetArena(), |
| 653 | local, |
| 654 | 0, |
| 655 | incoming->GetType()); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 656 | block->AddPhi(phi); |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 657 | (*current_locals_)[local] = phi; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 658 | } |
| 659 | } |
| 660 | // Save the loop header so that the last phase of the analysis knows which |
| 661 | // blocks need to be updated. |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 662 | loop_headers_.push_back(block); |
Vladimir Marko | 6058455 | 2015-09-03 13:35:12 +0000 | [diff] [blame] | 663 | } else if (block->GetPredecessors().size() > 0) { |
Nicolas Geoffray | 804d093 | 2014-05-02 08:46:00 +0100 | [diff] [blame] | 664 | // 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] | 665 | // We merge the values of all locals, creating phis if those values differ. |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 666 | for (size_t local = 0; local < current_locals_->size(); ++local) { |
Nicolas Geoffray | 7c3560f | 2014-06-04 12:12:08 +0100 | [diff] [blame] | 667 | bool one_predecessor_has_no_value = false; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 668 | bool is_different = false; |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 669 | HInstruction* value = ValueOfLocal(block->GetPredecessors()[0], local); |
Nicolas Geoffray | 7c3560f | 2014-06-04 12:12:08 +0100 | [diff] [blame] | 670 | |
Vladimir Marko | 6058455 | 2015-09-03 13:35:12 +0000 | [diff] [blame] | 671 | for (HBasicBlock* predecessor : block->GetPredecessors()) { |
| 672 | HInstruction* current = ValueOfLocal(predecessor, local); |
Nicolas Geoffray | 7c3560f | 2014-06-04 12:12:08 +0100 | [diff] [blame] | 673 | if (current == nullptr) { |
Nicolas Geoffray | ec7e472 | 2014-06-06 11:24:33 +0100 | [diff] [blame] | 674 | one_predecessor_has_no_value = true; |
| 675 | break; |
Nicolas Geoffray | 7c3560f | 2014-06-04 12:12:08 +0100 | [diff] [blame] | 676 | } else if (current != value) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 677 | is_different = true; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 678 | } |
| 679 | } |
Nicolas Geoffray | 7c3560f | 2014-06-04 12:12:08 +0100 | [diff] [blame] | 680 | |
| 681 | if (one_predecessor_has_no_value) { |
| 682 | // If one predecessor has no value for this local, we trust the verifier has |
| 683 | // successfully checked that there is a store dominating any read after this block. |
| 684 | continue; |
| 685 | } |
| 686 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 687 | if (is_different) { |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 688 | HInstruction* first_input = ValueOfLocal(block->GetPredecessors()[0], local); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 689 | HPhi* phi = new (GetGraph()->GetArena()) HPhi( |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 690 | GetGraph()->GetArena(), |
| 691 | local, |
| 692 | block->GetPredecessors().size(), |
| 693 | first_input->GetType()); |
Vladimir Marko | 6058455 | 2015-09-03 13:35:12 +0000 | [diff] [blame] | 694 | for (size_t i = 0; i < block->GetPredecessors().size(); i++) { |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 695 | HInstruction* pred_value = ValueOfLocal(block->GetPredecessors()[i], local); |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 696 | phi->SetRawInputAt(i, pred_value); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 697 | } |
| 698 | block->AddPhi(phi); |
| 699 | value = phi; |
| 700 | } |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 701 | (*current_locals_)[local] = value; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 702 | } |
| 703 | } |
| 704 | |
| 705 | // Visit all instructions. The instructions of interest are: |
| 706 | // - HLoadLocal: replace them with the current value of the local. |
| 707 | // - HStoreLocal: update current value of the local and remove the instruction. |
| 708 | // - Instructions that require an environment: populate their environment |
| 709 | // with the current values of the locals. |
Nicolas Geoffray | f635e63 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 710 | for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 711 | it.Current()->Accept(this); |
| 712 | } |
| 713 | } |
| 714 | |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 715 | /** |
| 716 | * Constants in the Dex format are not typed. So the builder types them as |
| 717 | * integers, but when doing the SSA form, we might realize the constant |
| 718 | * is used for floating point operations. We create a floating-point equivalent |
| 719 | * constant to make the operations correctly typed. |
| 720 | */ |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 721 | HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 722 | // We place the floating point constant next to this constant. |
| 723 | HFloatConstant* result = constant->GetNext()->AsFloatConstant(); |
| 724 | if (result == nullptr) { |
| 725 | HGraph* graph = constant->GetBlock()->GetGraph(); |
| 726 | ArenaAllocator* allocator = graph->GetArena(); |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 727 | result = new (allocator) HFloatConstant(bit_cast<float, int32_t>(constant->GetValue())); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 728 | constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); |
Nicolas Geoffray | f213e05 | 2015-04-27 08:53:46 +0000 | [diff] [blame] | 729 | graph->CacheFloatConstant(result); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 730 | } else { |
| 731 | // If there is already a constant with the expected type, we know it is |
| 732 | // the floating point equivalent of this constant. |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 733 | DCHECK_EQ((bit_cast<int32_t, float>(result->GetValue())), constant->GetValue()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 734 | } |
| 735 | return result; |
| 736 | } |
| 737 | |
| 738 | /** |
| 739 | * Wide constants in the Dex format are not typed. So the builder types them as |
| 740 | * longs, but when doing the SSA form, we might realize the constant |
| 741 | * is used for floating point operations. We create a floating-point equivalent |
| 742 | * constant to make the operations correctly typed. |
| 743 | */ |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 744 | HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 745 | // We place the floating point constant next to this constant. |
| 746 | HDoubleConstant* result = constant->GetNext()->AsDoubleConstant(); |
| 747 | if (result == nullptr) { |
| 748 | HGraph* graph = constant->GetBlock()->GetGraph(); |
| 749 | ArenaAllocator* allocator = graph->GetArena(); |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 750 | result = new (allocator) HDoubleConstant(bit_cast<double, int64_t>(constant->GetValue())); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 751 | constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); |
Nicolas Geoffray | f213e05 | 2015-04-27 08:53:46 +0000 | [diff] [blame] | 752 | graph->CacheDoubleConstant(result); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 753 | } else { |
| 754 | // If there is already a constant with the expected type, we know it is |
| 755 | // the floating point equivalent of this constant. |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 756 | DCHECK_EQ((bit_cast<int64_t, double>(result->GetValue())), constant->GetValue()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 757 | } |
| 758 | return result; |
| 759 | } |
| 760 | |
| 761 | /** |
| 762 | * 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] | 763 | * used for non floating point operations and floating point / reference operations. |
| 764 | * 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] | 765 | * 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] | 766 | * phi with a floating point / reference type. |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 767 | */ |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 768 | HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 769 | DCHECK(phi->IsLive()) << "Cannot get equivalent of a dead phi since it would create a live one."; |
| 770 | |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 771 | // We place the floating point /reference phi next to this phi. |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 772 | HInstruction* next = phi->GetNext(); |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 773 | if (next != nullptr |
| 774 | && next->AsPhi()->GetRegNumber() == phi->GetRegNumber() |
| 775 | && next->GetType() != type) { |
| 776 | // Move to the next phi to see if it is the one we are looking for. |
| 777 | next = next->GetNext(); |
| 778 | } |
| 779 | |
| 780 | if (next == nullptr |
| 781 | || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber()) |
| 782 | || (next->GetType() != type)) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 783 | ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena(); |
| 784 | HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type); |
| 785 | for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 786 | // Copy the inputs. Note that the graph may not be correctly typed |
| 787 | // by doing this copy, but the type propagation phase will fix it. |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 788 | new_phi->SetRawInputAt(i, phi->InputAt(i)); |
| 789 | } |
| 790 | phi->GetBlock()->InsertPhiAfter(new_phi, phi); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 791 | DCHECK(new_phi->IsLive()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 792 | return new_phi; |
| 793 | } else { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 794 | // An existing equivalent was found. If it is dead, conflict was previously |
| 795 | // identified and we return nullptr instead. |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 796 | HPhi* next_phi = next->AsPhi(); |
| 797 | DCHECK_EQ(next_phi->GetType(), type); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 798 | return next_phi->IsLive() ? next_phi : nullptr; |
David Brazdil | d9510df | 2015-11-04 23:30:22 +0000 | [diff] [blame] | 799 | } |
| 800 | } |
| 801 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 802 | HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { |
| 803 | DCHECK(Primitive::IsIntegralType(aget->GetType())); |
| 804 | |
| 805 | if (!Primitive::IsIntOrLongType(aget->GetType())) { |
| 806 | // Cannot type boolean, char, byte, short to float/double. |
| 807 | return nullptr; |
| 808 | } |
| 809 | |
| 810 | DCHECK(ContainsElement(ambiguous_agets_, aget)); |
| 811 | if (agets_fixed_) { |
| 812 | // This used to be an ambiguous ArrayGet but its type has been resolved to |
| 813 | // int/long. Requesting a float/double equivalent should lead to a conflict. |
| 814 | if (kIsDebugBuild) { |
| 815 | ScopedObjectAccess soa(Thread::Current()); |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 816 | DCHECK(Primitive::IsIntOrLongType(GetPrimitiveArrayComponentType(aget->GetArray()))); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 817 | } |
| 818 | return nullptr; |
| 819 | } else { |
| 820 | // This is an ambiguous ArrayGet which has not been resolved yet. Return an |
| 821 | // equivalent float/double instruction to use until it is resolved. |
| 822 | HArrayGet* equivalent = FindFloatOrDoubleEquivalentOfArrayGet(aget); |
| 823 | return (equivalent == nullptr) ? CreateFloatOrDoubleEquivalentOfArrayGet(aget) : equivalent; |
| 824 | } |
| 825 | } |
| 826 | |
| 827 | HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primitive::Type type) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 828 | if (value->IsArrayGet()) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 829 | return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 830 | } else if (value->IsLongConstant()) { |
| 831 | return GetDoubleEquivalent(value->AsLongConstant()); |
| 832 | } else if (value->IsIntConstant()) { |
| 833 | return GetFloatEquivalent(value->AsIntConstant()); |
| 834 | } else if (value->IsPhi()) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 835 | return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 836 | } else { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 837 | return nullptr; |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 838 | } |
| 839 | } |
| 840 | |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 841 | HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 842 | if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 843 | return value->GetBlock()->GetGraph()->GetNullConstant(); |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 844 | } else if (value->IsPhi()) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 845 | return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot); |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 846 | } else { |
| 847 | return nullptr; |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 848 | } |
| 849 | } |
| 850 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 851 | void SsaBuilder::VisitLoadLocal(HLoadLocal* load) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 852 | Primitive::Type load_type = load->GetType(); |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 853 | HInstruction* value = (*current_locals_)[load->GetLocal()->GetRegNumber()]; |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 854 | // If the operation requests a specific type, we make sure its input is of that type. |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 855 | if (load_type != value->GetType()) { |
| 856 | if (load_type == Primitive::kPrimFloat || load_type == Primitive::kPrimDouble) { |
| 857 | value = GetFloatOrDoubleEquivalent(value, load_type); |
| 858 | } else if (load_type == Primitive::kPrimNot) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 859 | value = GetReferenceTypeEquivalent(value); |
| 860 | } |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 861 | } |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 862 | |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 863 | load->ReplaceWith(value); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 864 | load->GetBlock()->RemoveInstruction(load); |
| 865 | } |
| 866 | |
| 867 | void SsaBuilder::VisitStoreLocal(HStoreLocal* store) { |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 868 | uint32_t reg_number = store->GetLocal()->GetRegNumber(); |
| 869 | HInstruction* stored_value = store->InputAt(1); |
| 870 | Primitive::Type stored_type = stored_value->GetType(); |
| 871 | DCHECK_NE(stored_type, Primitive::kPrimVoid); |
| 872 | |
| 873 | // Storing into vreg `reg_number` may implicitly invalidate the surrounding |
| 874 | // registers. Consider the following cases: |
| 875 | // (1) Storing a wide value must overwrite previous values in both `reg_number` |
| 876 | // and `reg_number+1`. We store `nullptr` in `reg_number+1`. |
| 877 | // (2) If vreg `reg_number-1` holds a wide value, writing into `reg_number` |
| 878 | // must invalidate it. We store `nullptr` in `reg_number-1`. |
| 879 | // Consequently, storing a wide value into the high vreg of another wide value |
| 880 | // will invalidate both `reg_number-1` and `reg_number+1`. |
| 881 | |
| 882 | if (reg_number != 0) { |
| 883 | HInstruction* local_low = (*current_locals_)[reg_number - 1]; |
| 884 | if (local_low != nullptr && Primitive::Is64BitType(local_low->GetType())) { |
| 885 | // The vreg we are storing into was previously the high vreg of a pair. |
| 886 | // We need to invalidate its low vreg. |
| 887 | DCHECK((*current_locals_)[reg_number] == nullptr); |
| 888 | (*current_locals_)[reg_number - 1] = nullptr; |
| 889 | } |
| 890 | } |
| 891 | |
| 892 | (*current_locals_)[reg_number] = stored_value; |
| 893 | if (Primitive::Is64BitType(stored_type)) { |
| 894 | // We are storing a pair. Invalidate the instruction in the high vreg. |
| 895 | (*current_locals_)[reg_number + 1] = nullptr; |
| 896 | } |
| 897 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 898 | store->GetBlock()->RemoveInstruction(store); |
| 899 | } |
| 900 | |
| 901 | void SsaBuilder::VisitInstruction(HInstruction* instruction) { |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 902 | if (instruction->NeedsEnvironment()) { |
| 903 | HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment( |
| 904 | GetGraph()->GetArena(), |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 905 | current_locals_->size(), |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 906 | GetGraph()->GetDexFile(), |
| 907 | GetGraph()->GetMethodIdx(), |
| 908 | instruction->GetDexPc(), |
| 909 | GetGraph()->GetInvokeType(), |
| 910 | instruction); |
| 911 | environment->CopyFrom(*current_locals_); |
| 912 | instruction->SetRawEnvironment(environment); |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 913 | } |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 914 | |
| 915 | // If in a try block, propagate values of locals into catch blocks. |
David Brazdil | ec16f79 | 2015-08-19 15:04:01 +0100 | [diff] [blame] | 916 | if (instruction->CanThrowIntoCatchBlock()) { |
| 917 | const HTryBoundary& try_entry = |
| 918 | instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry(); |
David Brazdil | d26a411 | 2015-11-10 11:07:31 +0000 | [diff] [blame] | 919 | for (HBasicBlock* catch_block : try_entry.GetExceptionHandlers()) { |
David Brazdil | 3eaa32f | 2015-09-18 10:58:32 +0100 | [diff] [blame] | 920 | ArenaVector<HInstruction*>* handler_locals = GetLocalsFor(catch_block); |
Vladimir Marko | 71bf809 | 2015-09-15 15:33:14 +0100 | [diff] [blame] | 921 | DCHECK_EQ(handler_locals->size(), current_locals_->size()); |
David Brazdil | 3eaa32f | 2015-09-18 10:58:32 +0100 | [diff] [blame] | 922 | for (size_t vreg = 0, e = current_locals_->size(); vreg < e; ++vreg) { |
| 923 | HInstruction* handler_value = (*handler_locals)[vreg]; |
| 924 | if (handler_value == nullptr) { |
| 925 | // Vreg was undefined at a previously encountered throwing instruction |
| 926 | // and the catch phi was deleted. Do not record the local value. |
| 927 | continue; |
| 928 | } |
| 929 | DCHECK(handler_value->IsPhi()); |
| 930 | |
| 931 | HInstruction* local_value = (*current_locals_)[vreg]; |
| 932 | if (local_value == nullptr) { |
| 933 | // This is the first instruction throwing into `catch_block` where |
| 934 | // `vreg` is undefined. Delete the catch phi. |
| 935 | catch_block->RemovePhi(handler_value->AsPhi()); |
| 936 | (*handler_locals)[vreg] = nullptr; |
| 937 | } else { |
| 938 | // Vreg has been defined at all instructions throwing into `catch_block` |
| 939 | // encountered so far. Record the local value in the catch phi. |
| 940 | handler_value->AsPhi()->AddInput(local_value); |
David Brazdil | ffee3d3 | 2015-07-06 11:48:53 +0100 | [diff] [blame] | 941 | } |
| 942 | } |
| 943 | } |
| 944 | } |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 945 | } |
| 946 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 947 | void SsaBuilder::VisitArrayGet(HArrayGet* aget) { |
| 948 | Primitive::Type type = aget->GetType(); |
| 949 | DCHECK(!Primitive::IsFloatingPointType(type)); |
| 950 | if (Primitive::IsIntOrLongType(type)) { |
| 951 | ambiguous_agets_.push_back(aget); |
| 952 | } |
| 953 | VisitInstruction(aget); |
| 954 | } |
| 955 | |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 956 | void SsaBuilder::VisitArraySet(HArraySet* aset) { |
| 957 | Primitive::Type type = aset->GetValue()->GetType(); |
| 958 | if (Primitive::IsIntOrLongType(type)) { |
| 959 | ambiguous_asets_.push_back(aset); |
| 960 | } |
| 961 | VisitInstruction(aset); |
| 962 | } |
| 963 | |
David Brazdil | 6de1938 | 2016-01-08 17:37:10 +0000 | [diff] [blame] | 964 | void SsaBuilder::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { |
| 965 | VisitInstruction(invoke); |
| 966 | |
| 967 | if (invoke->IsStringInit()) { |
| 968 | // This is a StringFactory call which acts as a String constructor. Its |
| 969 | // result replaces the empty String pre-allocated by NewInstance. |
David Brazdil | bc9ab16 | 2016-01-20 14:50:19 +0000 | [diff] [blame] | 970 | HInstruction* arg_this = invoke->GetAndRemoveThisArgumentOfStringInit(); |
David Brazdil | 6de1938 | 2016-01-08 17:37:10 +0000 | [diff] [blame] | 971 | |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 972 | // Replacing the NewInstance might render it redundant. Keep a list of these |
| 973 | // to be visited once it is clear whether it is has remaining uses. |
David Brazdil | bc9ab16 | 2016-01-20 14:50:19 +0000 | [diff] [blame] | 974 | if (arg_this->IsNewInstance()) { |
| 975 | uninitialized_strings_.push_back(arg_this->AsNewInstance()); |
| 976 | } else { |
David Brazdil | c047d94 | 2016-01-20 17:00:19 +0000 | [diff] [blame] | 977 | DCHECK(arg_this->IsPhi()); |
David Brazdil | bc9ab16 | 2016-01-20 14:50:19 +0000 | [diff] [blame] | 978 | // NewInstance is not the direct input of the StringFactory call. It might |
| 979 | // be redundant but optimizing this case is not worth the effort. |
| 980 | } |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 981 | |
David Brazdil | bc9ab16 | 2016-01-20 14:50:19 +0000 | [diff] [blame] | 982 | // Walk over all vregs and replace any occurrence of `arg_this` with `invoke`. |
David Brazdil | 6de1938 | 2016-01-08 17:37:10 +0000 | [diff] [blame] | 983 | for (size_t vreg = 0, e = current_locals_->size(); vreg < e; ++vreg) { |
David Brazdil | bc9ab16 | 2016-01-20 14:50:19 +0000 | [diff] [blame] | 984 | if ((*current_locals_)[vreg] == arg_this) { |
David Brazdil | 6de1938 | 2016-01-08 17:37:10 +0000 | [diff] [blame] | 985 | (*current_locals_)[vreg] = invoke; |
| 986 | } |
| 987 | } |
| 988 | } |
| 989 | } |
| 990 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 991 | } // namespace art |