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