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 | |
David Brazdil | 86ea7ee | 2016-02-16 09:26:07 +0000 | [diff] [blame] | 19 | #include "bytecode_utils.h" |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 20 | #include "nodes.h" |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 21 | #include "reference_type_propagation.h" |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 22 | #include "ssa_phi_elimination.h" |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 23 | |
| 24 | namespace art { |
| 25 | |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 26 | void SsaBuilder::FixNullConstantType() { |
| 27 | // The order doesn't matter here. |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 28 | for (HReversePostOrderIterator itb(*graph_); !itb.Done(); itb.Advance()) { |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 29 | for (HInstructionIterator it(itb.Current()->GetInstructions()); !it.Done(); it.Advance()) { |
| 30 | HInstruction* equality_instr = it.Current(); |
| 31 | if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) { |
| 32 | continue; |
| 33 | } |
| 34 | HInstruction* left = equality_instr->InputAt(0); |
| 35 | HInstruction* right = equality_instr->InputAt(1); |
Nicolas Geoffray | 51d400d | 2015-06-15 09:01:08 +0100 | [diff] [blame] | 36 | HInstruction* int_operand = nullptr; |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 37 | |
Nicolas Geoffray | 51d400d | 2015-06-15 09:01:08 +0100 | [diff] [blame] | 38 | if ((left->GetType() == Primitive::kPrimNot) && (right->GetType() == Primitive::kPrimInt)) { |
| 39 | int_operand = right; |
| 40 | } else if ((right->GetType() == Primitive::kPrimNot) |
| 41 | && (left->GetType() == Primitive::kPrimInt)) { |
| 42 | int_operand = left; |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 43 | } else { |
| 44 | continue; |
| 45 | } |
| 46 | |
| 47 | // If we got here, we are comparing against a reference and the int constant |
| 48 | // should be replaced with a null constant. |
Nicolas Geoffray | 51d400d | 2015-06-15 09:01:08 +0100 | [diff] [blame] | 49 | // Both type propagation and redundant phi elimination ensure `int_operand` |
| 50 | // can only be the 0 constant. |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 51 | DCHECK(int_operand->IsIntConstant()) << int_operand->DebugName(); |
Nicolas Geoffray | 51d400d | 2015-06-15 09:01:08 +0100 | [diff] [blame] | 52 | DCHECK_EQ(0, int_operand->AsIntConstant()->GetValue()); |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 53 | equality_instr->ReplaceInput(graph_->GetNullConstant(), int_operand == right ? 1 : 0); |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 54 | } |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | void SsaBuilder::EquivalentPhisCleanup() { |
| 59 | // The order doesn't matter here. |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 60 | for (HReversePostOrderIterator itb(*graph_); !itb.Done(); itb.Advance()) { |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 61 | for (HInstructionIterator it(itb.Current()->GetPhis()); !it.Done(); it.Advance()) { |
| 62 | HPhi* phi = it.Current()->AsPhi(); |
| 63 | HPhi* next = phi->GetNextEquivalentPhiWithSameType(); |
| 64 | if (next != nullptr) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 65 | // Make sure we do not replace a live phi with a dead phi. A live phi |
| 66 | // has been handled by the type propagation phase, unlike a dead phi. |
Nicolas Geoffray | 4230e18 | 2015-06-29 14:34:46 +0100 | [diff] [blame] | 67 | if (next->IsLive()) { |
| 68 | phi->ReplaceWith(next); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 69 | phi->SetDead(); |
Nicolas Geoffray | 4230e18 | 2015-06-29 14:34:46 +0100 | [diff] [blame] | 70 | } else { |
| 71 | next->ReplaceWith(phi); |
| 72 | } |
Calin Juravle | a4f8831 | 2015-04-16 12:57:19 +0100 | [diff] [blame] | 73 | DCHECK(next->GetNextEquivalentPhiWithSameType() == nullptr) |
| 74 | << "More then one phi equivalent with type " << phi->GetType() |
| 75 | << " found for phi" << phi->GetId(); |
| 76 | } |
| 77 | } |
| 78 | } |
| 79 | } |
| 80 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 81 | void SsaBuilder::FixEnvironmentPhis() { |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 82 | for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 83 | HBasicBlock* block = it.Current(); |
| 84 | for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { |
| 85 | HPhi* phi = it_phis.Current()->AsPhi(); |
| 86 | // If the phi is not dead, or has no environment uses, there is nothing to do. |
| 87 | if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue; |
| 88 | HInstruction* next = phi->GetNext(); |
David Brazdil | d0180f9 | 2015-09-22 14:39:58 +0100 | [diff] [blame] | 89 | if (!phi->IsVRegEquivalentOf(next)) continue; |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 90 | if (next->AsPhi()->IsDead()) { |
| 91 | // If the phi equivalent is dead, check if there is another one. |
| 92 | next = next->GetNext(); |
David Brazdil | d0180f9 | 2015-09-22 14:39:58 +0100 | [diff] [blame] | 93 | if (!phi->IsVRegEquivalentOf(next)) continue; |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 94 | // There can be at most two phi equivalents. |
David Brazdil | d0180f9 | 2015-09-22 14:39:58 +0100 | [diff] [blame] | 95 | DCHECK(!phi->IsVRegEquivalentOf(next->GetNext())); |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 96 | if (next->AsPhi()->IsDead()) continue; |
| 97 | } |
| 98 | // We found a live phi equivalent. Update the environment uses of `phi` with it. |
| 99 | phi->ReplaceWith(next); |
| 100 | } |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 101 | } |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 102 | } |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 103 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 104 | static void AddDependentInstructionsToWorklist(HInstruction* instruction, |
| 105 | ArenaVector<HPhi*>* worklist) { |
| 106 | // If `instruction` is a dead phi, type conflict was just identified. All its |
| 107 | // live phi users, and transitively users of those users, therefore need to be |
| 108 | // marked dead/conflicting too, so we add them to the worklist. Otherwise we |
| 109 | // add users whose type does not match and needs to be updated. |
| 110 | bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead(); |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 111 | for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { |
| 112 | HInstruction* user = use.GetUser(); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 113 | if (user->IsPhi() && user->AsPhi()->IsLive()) { |
| 114 | if (add_all_live_phis || user->GetType() != instruction->GetType()) { |
| 115 | worklist->push_back(user->AsPhi()); |
| 116 | } |
| 117 | } |
| 118 | } |
| 119 | } |
| 120 | |
| 121 | // Find a candidate primitive type for `phi` by merging the type of its inputs. |
| 122 | // Return false if conflict is identified. |
| 123 | static bool TypePhiFromInputs(HPhi* phi) { |
| 124 | Primitive::Type common_type = phi->GetType(); |
| 125 | |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame^] | 126 | for (HInstruction* input : phi->GetInputs()) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 127 | if (input->IsPhi() && input->AsPhi()->IsDead()) { |
| 128 | // Phis are constructed live so if an input is a dead phi, it must have |
| 129 | // been made dead due to type conflict. Mark this phi conflicting too. |
| 130 | return false; |
| 131 | } |
| 132 | |
| 133 | Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); |
| 134 | if (common_type == input_type) { |
| 135 | // No change in type. |
David Brazdil | d87f3ea | 2016-01-04 15:55:10 +0000 | [diff] [blame] | 136 | } else if (Primitive::Is64BitType(common_type) != Primitive::Is64BitType(input_type)) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 137 | // Types are of different sizes, e.g. int vs. long. Must be a conflict. |
| 138 | return false; |
| 139 | } else if (Primitive::IsIntegralType(common_type)) { |
| 140 | // Previous inputs were integral, this one is not but is of the same size. |
| 141 | // This does not imply conflict since some bytecode instruction types are |
| 142 | // ambiguous. TypeInputsOfPhi will either type them or detect a conflict. |
| 143 | DCHECK(Primitive::IsFloatingPointType(input_type) || input_type == Primitive::kPrimNot); |
| 144 | common_type = input_type; |
| 145 | } else if (Primitive::IsIntegralType(input_type)) { |
| 146 | // Input is integral, common type is not. Same as in the previous case, if |
| 147 | // there is a conflict, it will be detected during TypeInputsOfPhi. |
| 148 | DCHECK(Primitive::IsFloatingPointType(common_type) || common_type == Primitive::kPrimNot); |
| 149 | } else { |
| 150 | // Combining float and reference types. Clearly a conflict. |
| 151 | DCHECK((common_type == Primitive::kPrimFloat && input_type == Primitive::kPrimNot) || |
| 152 | (common_type == Primitive::kPrimNot && input_type == Primitive::kPrimFloat)); |
| 153 | return false; |
| 154 | } |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 155 | } |
| 156 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 157 | // We have found a candidate type for the phi. Set it and return true. We may |
| 158 | // still discover conflict whilst typing the individual inputs in TypeInputsOfPhi. |
| 159 | phi->SetType(common_type); |
| 160 | return true; |
| 161 | } |
David Brazdil | d9510df | 2015-11-04 23:30:22 +0000 | [diff] [blame] | 162 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 163 | // Replace inputs of `phi` to match its type. Return false if conflict is identified. |
| 164 | bool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) { |
| 165 | Primitive::Type common_type = phi->GetType(); |
| 166 | if (common_type == Primitive::kPrimVoid || Primitive::IsIntegralType(common_type)) { |
| 167 | // Phi either contains only other untyped phis (common_type == kPrimVoid), |
| 168 | // or `common_type` is integral and we do not need to retype ambiguous inputs |
| 169 | // because they are always constructed with the integral type candidate. |
| 170 | if (kIsDebugBuild) { |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame^] | 171 | for (HInstruction* input : phi->GetInputs()) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 172 | if (common_type == Primitive::kPrimVoid) { |
| 173 | DCHECK(input->IsPhi() && input->GetType() == Primitive::kPrimVoid); |
| 174 | } else { |
| 175 | DCHECK((input->IsPhi() && input->GetType() == Primitive::kPrimVoid) || |
| 176 | HPhi::ToPhiType(input->GetType()) == common_type); |
| 177 | } |
| 178 | } |
| 179 | } |
| 180 | // Inputs did not need to be replaced, hence no conflict. Report success. |
| 181 | return true; |
| 182 | } else { |
| 183 | DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type)); |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame^] | 184 | auto&& inputs = phi->GetInputs(); |
| 185 | for (size_t i = 0; i < inputs.size(); ++i) { |
| 186 | HInstruction* input = inputs[i]; |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 187 | if (input->GetType() != common_type) { |
| 188 | // Input type does not match phi's type. Try to retype the input or |
| 189 | // generate a suitably typed equivalent. |
| 190 | HInstruction* equivalent = (common_type == Primitive::kPrimNot) |
| 191 | ? GetReferenceTypeEquivalent(input) |
| 192 | : GetFloatOrDoubleEquivalent(input, common_type); |
| 193 | if (equivalent == nullptr) { |
| 194 | // Input could not be typed. Report conflict. |
| 195 | return false; |
| 196 | } |
| 197 | // Make sure the input did not change its type and we do not need to |
| 198 | // update its users. |
| 199 | DCHECK_NE(input, equivalent); |
| 200 | |
| 201 | phi->ReplaceInput(equivalent, i); |
| 202 | if (equivalent->IsPhi()) { |
| 203 | worklist->push_back(equivalent->AsPhi()); |
| 204 | } |
| 205 | } |
| 206 | } |
| 207 | // All inputs either matched the type of the phi or we successfully replaced |
| 208 | // them with a suitable equivalent. Report success. |
| 209 | return true; |
| 210 | } |
| 211 | } |
| 212 | |
| 213 | // Attempt to set the primitive type of `phi` to match its inputs. Return whether |
| 214 | // it was changed by the algorithm or not. |
| 215 | bool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist) { |
| 216 | DCHECK(phi->IsLive()); |
| 217 | Primitive::Type original_type = phi->GetType(); |
| 218 | |
| 219 | // Try to type the phi in two stages: |
| 220 | // (1) find a candidate type for the phi by merging types of all its inputs, |
| 221 | // (2) try to type the phi's inputs to that candidate type. |
| 222 | // Either of these stages may detect a type conflict and fail, in which case |
| 223 | // we immediately abort. |
| 224 | if (!TypePhiFromInputs(phi) || !TypeInputsOfPhi(phi, worklist)) { |
| 225 | // Conflict detected. Mark the phi dead and return true because it changed. |
| 226 | phi->SetDead(); |
| 227 | return true; |
| 228 | } |
| 229 | |
| 230 | // Return true if the type of the phi has changed. |
| 231 | return phi->GetType() != original_type; |
| 232 | } |
| 233 | |
| 234 | void SsaBuilder::RunPrimitiveTypePropagation() { |
Vladimir Marko | 3ea5a97 | 2016-05-09 20:23:34 +0100 | [diff] [blame] | 235 | ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter(kArenaAllocGraphBuilder)); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 236 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 237 | for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 238 | HBasicBlock* block = it.Current(); |
| 239 | if (block->IsLoopHeader()) { |
| 240 | for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { |
| 241 | HPhi* phi = phi_it.Current()->AsPhi(); |
| 242 | if (phi->IsLive()) { |
| 243 | worklist.push_back(phi); |
| 244 | } |
| 245 | } |
| 246 | } else { |
| 247 | for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { |
| 248 | // Eagerly compute the type of the phi, for quicker convergence. Note |
| 249 | // that we don't need to add users to the worklist because we are |
| 250 | // doing a reverse post-order visit, therefore either the phi users are |
| 251 | // non-loop phi and will be visited later in the visit, or are loop-phis, |
| 252 | // and they are already in the work list. |
| 253 | HPhi* phi = phi_it.Current()->AsPhi(); |
| 254 | if (phi->IsLive()) { |
| 255 | UpdatePrimitiveType(phi, &worklist); |
| 256 | } |
| 257 | } |
| 258 | } |
| 259 | } |
| 260 | |
| 261 | ProcessPrimitiveTypePropagationWorklist(&worklist); |
| 262 | EquivalentPhisCleanup(); |
| 263 | } |
| 264 | |
| 265 | void SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist) { |
| 266 | // Process worklist |
| 267 | while (!worklist->empty()) { |
| 268 | HPhi* phi = worklist->back(); |
| 269 | worklist->pop_back(); |
| 270 | // The phi could have been made dead as a result of conflicts while in the |
| 271 | // worklist. If it is now dead, there is no point in updating its type. |
| 272 | if (phi->IsLive() && UpdatePrimitiveType(phi, worklist)) { |
| 273 | AddDependentInstructionsToWorklist(phi, worklist); |
| 274 | } |
| 275 | } |
| 276 | } |
| 277 | |
| 278 | static HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { |
| 279 | Primitive::Type type = aget->GetType(); |
| 280 | DCHECK(Primitive::IsIntOrLongType(type)); |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 281 | HInstruction* next = aget->GetNext(); |
| 282 | if (next != nullptr && next->IsArrayGet()) { |
| 283 | HArrayGet* next_aget = next->AsArrayGet(); |
| 284 | if (next_aget->IsEquivalentOf(aget)) { |
| 285 | return next_aget; |
| 286 | } |
| 287 | } |
| 288 | return nullptr; |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 289 | } |
| 290 | |
| 291 | static HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { |
| 292 | Primitive::Type type = aget->GetType(); |
| 293 | DCHECK(Primitive::IsIntOrLongType(type)); |
| 294 | DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr); |
| 295 | |
| 296 | HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetArena()) HArrayGet( |
| 297 | aget->GetArray(), |
| 298 | aget->GetIndex(), |
| 299 | type == Primitive::kPrimInt ? Primitive::kPrimFloat : Primitive::kPrimDouble, |
| 300 | aget->GetDexPc()); |
| 301 | aget->GetBlock()->InsertInstructionAfter(equivalent, aget); |
| 302 | return equivalent; |
| 303 | } |
| 304 | |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 305 | static Primitive::Type GetPrimitiveArrayComponentType(HInstruction* array) |
| 306 | SHARED_REQUIRES(Locks::mutator_lock_) { |
| 307 | ReferenceTypeInfo array_type = array->GetReferenceTypeInfo(); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 308 | DCHECK(array_type.IsPrimitiveArrayClass()); |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 309 | return array_type.GetTypeHandle()->GetComponentType()->GetPrimitiveType(); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 310 | } |
| 311 | |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 312 | bool SsaBuilder::FixAmbiguousArrayOps() { |
| 313 | if (ambiguous_agets_.empty() && ambiguous_asets_.empty()) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 314 | return true; |
| 315 | } |
| 316 | |
| 317 | // The wrong ArrayGet equivalent may still have Phi uses coming from ArraySet |
| 318 | // uses (because they are untyped) and environment uses (if --debuggable). |
| 319 | // After resolving all ambiguous ArrayGets, we will re-run primitive type |
| 320 | // propagation on the Phis which need to be updated. |
Vladimir Marko | 3ea5a97 | 2016-05-09 20:23:34 +0100 | [diff] [blame] | 321 | ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter(kArenaAllocGraphBuilder)); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 322 | |
| 323 | { |
| 324 | ScopedObjectAccess soa(Thread::Current()); |
| 325 | |
| 326 | for (HArrayGet* aget_int : ambiguous_agets_) { |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 327 | HInstruction* array = aget_int->GetArray(); |
| 328 | if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 329 | // RTP did not type the input array. Bail. |
| 330 | return false; |
| 331 | } |
| 332 | |
| 333 | HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int); |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 334 | Primitive::Type array_type = GetPrimitiveArrayComponentType(array); |
| 335 | DCHECK_EQ(Primitive::Is64BitType(aget_int->GetType()), Primitive::Is64BitType(array_type)); |
| 336 | |
| 337 | if (Primitive::IsIntOrLongType(array_type)) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 338 | if (aget_float != nullptr) { |
| 339 | // There is a float/double equivalent. We must replace it and re-run |
| 340 | // primitive type propagation on all dependent instructions. |
| 341 | aget_float->ReplaceWith(aget_int); |
| 342 | aget_float->GetBlock()->RemoveInstruction(aget_float); |
| 343 | AddDependentInstructionsToWorklist(aget_int, &worklist); |
| 344 | } |
| 345 | } else { |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 346 | DCHECK(Primitive::IsFloatingPointType(array_type)); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 347 | if (aget_float == nullptr) { |
| 348 | // This is a float/double ArrayGet but there were no typed uses which |
| 349 | // would create the typed equivalent. Create it now. |
| 350 | aget_float = CreateFloatOrDoubleEquivalentOfArrayGet(aget_int); |
| 351 | } |
| 352 | // Replace the original int/long instruction. Note that it may have phi |
| 353 | // uses, environment uses, as well as real uses (from untyped ArraySets). |
| 354 | // We need to re-run primitive type propagation on its dependent instructions. |
| 355 | aget_int->ReplaceWith(aget_float); |
| 356 | aget_int->GetBlock()->RemoveInstruction(aget_int); |
| 357 | AddDependentInstructionsToWorklist(aget_float, &worklist); |
| 358 | } |
| 359 | } |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 360 | |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 361 | // Set a flag stating that types of ArrayGets have been resolved. Requesting |
| 362 | // equivalent of the wrong type with GetFloatOrDoubleEquivalentOfArrayGet |
| 363 | // will fail from now on. |
| 364 | agets_fixed_ = true; |
| 365 | |
| 366 | for (HArraySet* aset : ambiguous_asets_) { |
| 367 | HInstruction* array = aset->GetArray(); |
| 368 | if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { |
| 369 | // RTP did not type the input array. Bail. |
| 370 | return false; |
| 371 | } |
| 372 | |
| 373 | HInstruction* value = aset->GetValue(); |
| 374 | Primitive::Type value_type = value->GetType(); |
| 375 | Primitive::Type array_type = GetPrimitiveArrayComponentType(array); |
| 376 | DCHECK_EQ(Primitive::Is64BitType(value_type), Primitive::Is64BitType(array_type)); |
| 377 | |
| 378 | if (Primitive::IsFloatingPointType(array_type)) { |
| 379 | if (!Primitive::IsFloatingPointType(value_type)) { |
| 380 | DCHECK(Primitive::IsIntegralType(value_type)); |
| 381 | // Array elements are floating-point but the value has not been replaced |
| 382 | // with its floating-point equivalent. The replacement must always |
| 383 | // succeed in code validated by the verifier. |
| 384 | HInstruction* equivalent = GetFloatOrDoubleEquivalent(value, array_type); |
| 385 | DCHECK(equivalent != nullptr); |
| 386 | aset->ReplaceInput(equivalent, /* input_index */ 2); |
| 387 | if (equivalent->IsPhi()) { |
| 388 | // Returned equivalent is a phi which may not have had its inputs |
| 389 | // replaced yet. We need to run primitive type propagation on it. |
| 390 | worklist.push_back(equivalent->AsPhi()); |
| 391 | } |
| 392 | } |
Aart Bik | 18b36ab | 2016-04-13 16:41:35 -0700 | [diff] [blame] | 393 | // Refine the side effects of this floating point aset. Note that we do this even if |
| 394 | // no replacement occurs, since the right-hand-side may have been corrected already. |
| 395 | aset->ComputeSideEffects(); |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 396 | } else { |
| 397 | // Array elements are integral and the value assigned to it initially |
| 398 | // was integral too. Nothing to do. |
| 399 | DCHECK(Primitive::IsIntegralType(array_type)); |
| 400 | DCHECK(Primitive::IsIntegralType(value_type)); |
| 401 | } |
| 402 | } |
| 403 | } |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 404 | |
| 405 | if (!worklist.empty()) { |
| 406 | ProcessPrimitiveTypePropagationWorklist(&worklist); |
| 407 | EquivalentPhisCleanup(); |
| 408 | } |
| 409 | |
| 410 | return true; |
| 411 | } |
| 412 | |
Nicolas Geoffray | 98e6ce4 | 2016-02-16 18:42:15 +0000 | [diff] [blame] | 413 | static bool HasAliasInEnvironments(HInstruction* instruction) { |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 414 | HEnvironment* last_user = nullptr; |
| 415 | for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { |
| 416 | DCHECK(use.GetUser() != nullptr); |
| 417 | // Note: The first comparison (== null) always fails. |
| 418 | if (use.GetUser() == last_user) { |
Nicolas Geoffray | 98e6ce4 | 2016-02-16 18:42:15 +0000 | [diff] [blame] | 419 | return true; |
| 420 | } |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 421 | last_user = use.GetUser(); |
Nicolas Geoffray | 98e6ce4 | 2016-02-16 18:42:15 +0000 | [diff] [blame] | 422 | } |
| 423 | |
| 424 | if (kIsDebugBuild) { |
| 425 | // Do a quadratic search to ensure same environment uses are next |
| 426 | // to each other. |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 427 | const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses(); |
| 428 | for (auto current = env_uses.begin(), end = env_uses.end(); current != end; ++current) { |
| 429 | auto next = current; |
| 430 | for (++next; next != end; ++next) { |
Nicolas Geoffray | 98e6ce4 | 2016-02-16 18:42:15 +0000 | [diff] [blame] | 431 | DCHECK(next->GetUser() != current->GetUser()); |
Nicolas Geoffray | 98e6ce4 | 2016-02-16 18:42:15 +0000 | [diff] [blame] | 432 | } |
| 433 | } |
| 434 | } |
| 435 | return false; |
| 436 | } |
| 437 | |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 438 | void SsaBuilder::RemoveRedundantUninitializedStrings() { |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 439 | if (graph_->IsDebuggable()) { |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 440 | // Do not perform the optimization for consistency with the interpreter |
| 441 | // which always allocates an object for new-instance of String. |
| 442 | return; |
| 443 | } |
| 444 | |
| 445 | for (HNewInstance* new_instance : uninitialized_strings_) { |
Aart Bik | eda3140 | 2016-03-24 15:38:56 -0700 | [diff] [blame] | 446 | DCHECK(new_instance->IsInBlock()); |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 447 | DCHECK(new_instance->IsStringAlloc()); |
| 448 | |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 449 | // Replace NewInstance of String with NullConstant if not used prior to |
| 450 | // calling StringFactory. In case of deoptimization, the interpreter is |
| 451 | // 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] | 452 | if (!new_instance->HasNonEnvironmentUses() && !HasAliasInEnvironments(new_instance)) { |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 453 | new_instance->ReplaceWith(graph_->GetNullConstant()); |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 454 | new_instance->GetBlock()->RemoveInstruction(new_instance); |
| 455 | |
| 456 | // Remove LoadClass if not needed any more. |
Nicolas Geoffray | 5e08e36 | 2016-02-15 15:56:11 +0000 | [diff] [blame] | 457 | HInstruction* input = new_instance->InputAt(0); |
| 458 | HLoadClass* load_class = nullptr; |
| 459 | |
| 460 | // If the class was not present in the dex cache at the point of building |
| 461 | // the graph, the builder inserted a HClinitCheck in between. Since the String |
| 462 | // class is always initialized at the point of running Java code, we can remove |
| 463 | // that check. |
| 464 | if (input->IsClinitCheck()) { |
| 465 | load_class = input->InputAt(0)->AsLoadClass(); |
| 466 | input->ReplaceWith(load_class); |
| 467 | input->GetBlock()->RemoveInstruction(input); |
| 468 | } else { |
| 469 | load_class = input->AsLoadClass(); |
| 470 | DCHECK(new_instance->IsStringAlloc()); |
| 471 | DCHECK(!load_class->NeedsAccessCheck()) << "String class is always accessible"; |
| 472 | } |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 473 | DCHECK(load_class != nullptr); |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 474 | if (!load_class->HasUses()) { |
Nicolas Geoffray | 5e08e36 | 2016-02-15 15:56:11 +0000 | [diff] [blame] | 475 | // Even if the HLoadClass needs access check, we can remove it, as we know the |
| 476 | // String class does not need it. |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 477 | load_class->GetBlock()->RemoveInstruction(load_class); |
| 478 | } |
| 479 | } |
| 480 | } |
| 481 | } |
| 482 | |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 483 | GraphAnalysisResult SsaBuilder::BuildSsa() { |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 484 | DCHECK(!graph_->IsInSsaForm()); |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 485 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 486 | // 1) Propagate types of phis. At this point, phis are typed void in the general |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 487 | // case, or float/double/reference if we created an equivalent phi. So we need |
| 488 | // to propagate the types across phis to give them a correct type. If a type |
| 489 | // conflict is detected in this stage, the phi is marked dead. |
| 490 | RunPrimitiveTypePropagation(); |
| 491 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 492 | // 2) Now that the correct primitive types have been assigned, we can get rid |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 493 | // of redundant phis. Note that we cannot do this phase before type propagation, |
| 494 | // otherwise we could get rid of phi equivalents, whose presence is a requirement |
| 495 | // for the type propagation phase. Note that this is to satisfy statement (a) |
| 496 | // of the SsaBuilder (see ssa_builder.h). |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 497 | SsaRedundantPhiElimination(graph_).Run(); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 498 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 499 | // 3) Fix the type for null constants which are part of an equality comparison. |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 500 | // We need to do this after redundant phi elimination, to ensure the only cases |
| 501 | // that we can see are reference comparison against 0. The redundant phi |
| 502 | // elimination ensures we do not see a phi taking two 0 constants in a HEqual |
| 503 | // or HNotEqual. |
| 504 | FixNullConstantType(); |
| 505 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 506 | // 4) Compute type of reference type instructions. The pass assumes that |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 507 | // NullConstant has been fixed up. |
Vladimir Marko | 456307a | 2016-04-19 14:12:13 +0000 | [diff] [blame] | 508 | ReferenceTypePropagation(graph_, dex_cache_, handles_, /* is_first_run */ true).Run(); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 509 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 510 | // 5) HInstructionBuilder duplicated ArrayGet instructions with ambiguous type |
| 511 | // (int/float or long/double) and marked ArraySets with ambiguous input type. |
| 512 | // Now that RTP computed the type of the array input, the ambiguity can be |
| 513 | // resolved and the correct equivalents kept. |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 514 | if (!FixAmbiguousArrayOps()) { |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 515 | return kAnalysisFailAmbiguousArrayOp; |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 516 | } |
| 517 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 518 | // 6) Mark dead phis. This will mark phis which are not used by instructions |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 519 | // or other live phis. If compiling as debuggable code, phis will also be kept |
| 520 | // live if they have an environment use. |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 521 | SsaDeadPhiElimination dead_phi_elimimation(graph_); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 522 | dead_phi_elimimation.MarkDeadPhis(); |
| 523 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 524 | // 7) Make sure environments use the right phi equivalent: a phi marked dead |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 525 | // can have a phi equivalent that is not dead. In that case we have to replace |
| 526 | // it with the live equivalent because deoptimization and try/catch rely on |
| 527 | // environments containing values of all live vregs at that point. Note that |
| 528 | // there can be multiple phis for the same Dex register that are live |
| 529 | // (for example when merging constants), in which case it is okay for the |
| 530 | // environments to just reference one. |
| 531 | FixEnvironmentPhis(); |
| 532 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 533 | // 8) Now that the right phis are used for the environments, we can eliminate |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 534 | // phis we do not need. Regardless of the debuggable status, this phase is |
| 535 | /// necessary for statement (b) of the SsaBuilder (see ssa_builder.h), as well |
| 536 | // as for the code generation, which does not deal with phis of conflicting |
| 537 | // input types. |
| 538 | dead_phi_elimimation.EliminateDeadPhis(); |
| 539 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 540 | // 9) HInstructionBuidler replaced uses of NewInstances of String with the |
| 541 | // results of their corresponding StringFactory calls. Unless the String |
| 542 | // objects are used before they are initialized, they can be replaced with |
| 543 | // NullConstant. Note that this optimization is valid only if unsimplified |
| 544 | // code does not use the uninitialized value because we assume execution can |
| 545 | // be deoptimized at any safepoint. We must therefore perform it before any |
| 546 | // other optimizations. |
David Brazdil | 65902e8 | 2016-01-15 09:35:13 +0000 | [diff] [blame] | 547 | RemoveRedundantUninitializedStrings(); |
| 548 | |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 549 | graph_->SetInSsaForm(); |
Nicolas Geoffray | 15bd228 | 2016-01-05 15:55:41 +0000 | [diff] [blame] | 550 | return kAnalysisSuccess; |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 551 | } |
| 552 | |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 553 | /** |
| 554 | * Constants in the Dex format are not typed. So the builder types them as |
| 555 | * integers, but when doing the SSA form, we might realize the constant |
| 556 | * is used for floating point operations. We create a floating-point equivalent |
| 557 | * constant to make the operations correctly typed. |
| 558 | */ |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 559 | HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 560 | // We place the floating point constant next to this constant. |
| 561 | HFloatConstant* result = constant->GetNext()->AsFloatConstant(); |
| 562 | if (result == nullptr) { |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 563 | float value = bit_cast<float, int32_t>(constant->GetValue()); |
| 564 | result = new (graph_->GetArena()) HFloatConstant(value); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 565 | constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 566 | graph_->CacheFloatConstant(result); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 567 | } else { |
| 568 | // If there is already a constant with the expected type, we know it is |
| 569 | // the floating point equivalent of this constant. |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 570 | DCHECK_EQ((bit_cast<int32_t, float>(result->GetValue())), constant->GetValue()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 571 | } |
| 572 | return result; |
| 573 | } |
| 574 | |
| 575 | /** |
| 576 | * Wide constants in the Dex format are not typed. So the builder types them as |
| 577 | * longs, but when doing the SSA form, we might realize the constant |
| 578 | * is used for floating point operations. We create a floating-point equivalent |
| 579 | * constant to make the operations correctly typed. |
| 580 | */ |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 581 | HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 582 | // We place the floating point constant next to this constant. |
| 583 | HDoubleConstant* result = constant->GetNext()->AsDoubleConstant(); |
| 584 | if (result == nullptr) { |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 585 | double value = bit_cast<double, int64_t>(constant->GetValue()); |
| 586 | result = new (graph_->GetArena()) HDoubleConstant(value); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 587 | constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 588 | graph_->CacheDoubleConstant(result); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 589 | } else { |
| 590 | // If there is already a constant with the expected type, we know it is |
| 591 | // the floating point equivalent of this constant. |
Roland Levillain | da4d79b | 2015-03-24 14:36:11 +0000 | [diff] [blame] | 592 | DCHECK_EQ((bit_cast<int64_t, double>(result->GetValue())), constant->GetValue()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 593 | } |
| 594 | return result; |
| 595 | } |
| 596 | |
| 597 | /** |
| 598 | * 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] | 599 | * used for non floating point operations and floating point / reference operations. |
| 600 | * 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] | 601 | * 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] | 602 | * phi with a floating point / reference type. |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 603 | */ |
David Brazdil | 8d5b8b2 | 2015-03-24 10:51:52 +0000 | [diff] [blame] | 604 | HPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 605 | DCHECK(phi->IsLive()) << "Cannot get equivalent of a dead phi since it would create a live one."; |
| 606 | |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 607 | // We place the floating point /reference phi next to this phi. |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 608 | HInstruction* next = phi->GetNext(); |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 609 | if (next != nullptr |
| 610 | && next->AsPhi()->GetRegNumber() == phi->GetRegNumber() |
| 611 | && next->GetType() != type) { |
| 612 | // Move to the next phi to see if it is the one we are looking for. |
| 613 | next = next->GetNext(); |
| 614 | } |
| 615 | |
| 616 | if (next == nullptr |
| 617 | || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber()) |
| 618 | || (next->GetType() != type)) { |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 619 | ArenaAllocator* allocator = graph_->GetArena(); |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame^] | 620 | auto&& inputs = phi->GetInputs(); |
| 621 | HPhi* new_phi = |
| 622 | new (allocator) HPhi(allocator, phi->GetRegNumber(), inputs.size(), type); |
| 623 | // Copy the inputs. Note that the graph may not be correctly typed |
| 624 | // by doing this copy, but the type propagation phase will fix it. |
| 625 | ArrayRef<HUserRecord<HInstruction*>> new_input_records = new_phi->GetInputRecords(); |
| 626 | for (size_t i = 0; i < inputs.size(); ++i) { |
| 627 | new_input_records[i] = HUserRecord<HInstruction*>(inputs[i]); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 628 | } |
| 629 | phi->GetBlock()->InsertPhiAfter(new_phi, phi); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 630 | DCHECK(new_phi->IsLive()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 631 | return new_phi; |
| 632 | } else { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 633 | // An existing equivalent was found. If it is dead, conflict was previously |
| 634 | // identified and we return nullptr instead. |
David Brazdil | 809d70f | 2015-11-19 10:29:39 +0000 | [diff] [blame] | 635 | HPhi* next_phi = next->AsPhi(); |
| 636 | DCHECK_EQ(next_phi->GetType(), type); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 637 | return next_phi->IsLive() ? next_phi : nullptr; |
David Brazdil | d9510df | 2015-11-04 23:30:22 +0000 | [diff] [blame] | 638 | } |
| 639 | } |
| 640 | |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 641 | HArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { |
| 642 | DCHECK(Primitive::IsIntegralType(aget->GetType())); |
| 643 | |
| 644 | if (!Primitive::IsIntOrLongType(aget->GetType())) { |
| 645 | // Cannot type boolean, char, byte, short to float/double. |
| 646 | return nullptr; |
| 647 | } |
| 648 | |
| 649 | DCHECK(ContainsElement(ambiguous_agets_, aget)); |
| 650 | if (agets_fixed_) { |
| 651 | // This used to be an ambiguous ArrayGet but its type has been resolved to |
| 652 | // int/long. Requesting a float/double equivalent should lead to a conflict. |
| 653 | if (kIsDebugBuild) { |
| 654 | ScopedObjectAccess soa(Thread::Current()); |
David Brazdil | 15693bf | 2015-12-16 10:30:45 +0000 | [diff] [blame] | 655 | DCHECK(Primitive::IsIntOrLongType(GetPrimitiveArrayComponentType(aget->GetArray()))); |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 656 | } |
| 657 | return nullptr; |
| 658 | } else { |
| 659 | // This is an ambiguous ArrayGet which has not been resolved yet. Return an |
| 660 | // equivalent float/double instruction to use until it is resolved. |
| 661 | HArrayGet* equivalent = FindFloatOrDoubleEquivalentOfArrayGet(aget); |
| 662 | return (equivalent == nullptr) ? CreateFloatOrDoubleEquivalentOfArrayGet(aget) : equivalent; |
| 663 | } |
| 664 | } |
| 665 | |
| 666 | HInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primitive::Type type) { |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 667 | if (value->IsArrayGet()) { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 668 | return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet()); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 669 | } else if (value->IsLongConstant()) { |
| 670 | return GetDoubleEquivalent(value->AsLongConstant()); |
| 671 | } else if (value->IsIntConstant()) { |
| 672 | return GetFloatEquivalent(value->AsIntConstant()); |
| 673 | } else if (value->IsPhi()) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 674 | return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 675 | } else { |
David Brazdil | 4833f5a | 2015-12-16 10:37:39 +0000 | [diff] [blame] | 676 | return nullptr; |
Nicolas Geoffray | 102cbed | 2014-10-15 18:31:05 +0100 | [diff] [blame] | 677 | } |
| 678 | } |
| 679 | |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 680 | HInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 681 | if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) { |
David Brazdil | dee58d6 | 2016-04-07 09:54:26 +0000 | [diff] [blame] | 682 | return graph_->GetNullConstant(); |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 683 | } else if (value->IsPhi()) { |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 684 | return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot); |
Nicolas Geoffray | e0fe7ae | 2015-03-09 10:02:49 +0000 | [diff] [blame] | 685 | } else { |
| 686 | return nullptr; |
Nicolas Geoffray | d6138ef | 2015-02-18 14:48:53 +0000 | [diff] [blame] | 687 | } |
| 688 | } |
| 689 | |
Nicolas Geoffray | c32e770 | 2014-04-24 12:43:16 +0100 | [diff] [blame] | 690 | } // namespace art |