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 "primitive_type_propagation.h" 18 19#include "nodes.h" 20#include "ssa_builder.h" 21 22namespace art { 23 24static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) { 25 // We trust the verifier has already done the necessary checking. 26 switch (existing) { 27 case Primitive::kPrimFloat: 28 case Primitive::kPrimDouble: 29 case Primitive::kPrimNot: 30 return existing; 31 default: 32 // Phis are initialized with a void type, so if we are asked 33 // to merge with a void type, we should use the existing one. 34 return new_type == Primitive::kPrimVoid 35 ? existing 36 : HPhi::ToPhiType(new_type); 37 } 38} 39 40// Re-compute and update the type of the instruction. Returns 41// whether or not the type was changed. 42bool PrimitiveTypePropagation::UpdateType(HPhi* phi) { 43 DCHECK(phi->IsLive()); 44 Primitive::Type existing = phi->GetType(); 45 46 Primitive::Type new_type = existing; 47 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 48 Primitive::Type input_type = phi->InputAt(i)->GetType(); 49 new_type = MergeTypes(new_type, input_type); 50 } 51 phi->SetType(new_type); 52 53 if (new_type == Primitive::kPrimDouble 54 || new_type == Primitive::kPrimFloat 55 || new_type == Primitive::kPrimNot) { 56 // If the phi is of floating point type, we need to update its inputs to that 57 // type. For inputs that are phis, we need to recompute their types. 58 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 59 HInstruction* input = phi->InputAt(i); 60 if (input->GetType() != new_type) { 61 HInstruction* equivalent = (new_type == Primitive::kPrimNot) 62 ? SsaBuilder::GetReferenceTypeEquivalent(input) 63 : SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, new_type); 64 phi->ReplaceInput(equivalent, i); 65 if (equivalent->IsPhi()) { 66 equivalent->AsPhi()->SetLive(); 67 AddToWorklist(equivalent->AsPhi()); 68 } else if (equivalent == input) { 69 // The input has changed its type. It can be an input of other phis, 70 // so we need to put phi users in the work list. 71 AddDependentInstructionsToWorklist(equivalent); 72 } 73 } 74 } 75 } 76 77 return existing != new_type; 78} 79 80void PrimitiveTypePropagation::Run() { 81 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 82 VisitBasicBlock(it.Current()); 83 } 84 ProcessWorklist(); 85} 86 87void PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) { 88 if (block->IsLoopHeader()) { 89 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 90 HPhi* phi = it.Current()->AsPhi(); 91 if (phi->IsLive()) { 92 AddToWorklist(phi); 93 } 94 } 95 } else { 96 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 97 // Eagerly compute the type of the phi, for quicker convergence. Note 98 // that we don't need to add users to the worklist because we are 99 // doing a reverse post-order visit, therefore either the phi users are 100 // non-loop phi and will be visited later in the visit, or are loop-phis, 101 // and they are already in the work list. 102 HPhi* phi = it.Current()->AsPhi(); 103 if (phi->IsLive()) { 104 UpdateType(phi); 105 } 106 } 107 } 108} 109 110void PrimitiveTypePropagation::ProcessWorklist() { 111 while (!worklist_.IsEmpty()) { 112 HPhi* instruction = worklist_.Pop(); 113 if (UpdateType(instruction)) { 114 AddDependentInstructionsToWorklist(instruction); 115 } 116 } 117} 118 119void PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) { 120 DCHECK(instruction->IsLive()); 121 worklist_.Add(instruction); 122} 123 124void PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) { 125 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 126 HPhi* phi = it.Current()->GetUser()->AsPhi(); 127 if (phi != nullptr && phi->IsLive() && phi->GetType() != instruction->GetType()) { 128 AddToWorklist(phi); 129 } 130 } 131} 132 133} // namespace art 134