primitive_type_propagation.cc revision 10e244f9e7f6d96a95c910a2bedef5bd3810c637
1184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray/* 2184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * 4184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * you may not use this file except in compliance with the License. 6184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * You may obtain a copy of the License at 7184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * 8184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * 10184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * See the License for the specific language governing permissions and 14184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray * limitations under the License. 15184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray */ 16184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 1710e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravle#include "primitive_type_propagation.h" 18184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 19184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray#include "nodes.h" 2010e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravle#include "ssa_builder.h" 21184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 22184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffraynamespace art { 23184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 24184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffraystatic Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) { 25184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray // We trust the verifier has already done the necessary checking. 26184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray switch (existing) { 27184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray case Primitive::kPrimFloat: 28184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray case Primitive::kPrimDouble: 29184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray case Primitive::kPrimNot: 30184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray return existing; 31184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray default: 32b09aacb495dce2cb3e8469f056fdc2636ae393e6Nicolas Geoffray // Phis are initialized with a void type, so if we are asked 33b09aacb495dce2cb3e8469f056fdc2636ae393e6Nicolas Geoffray // to merge with a void type, we should use the existing one. 34b09aacb495dce2cb3e8469f056fdc2636ae393e6Nicolas Geoffray return new_type == Primitive::kPrimVoid 35b09aacb495dce2cb3e8469f056fdc2636ae393e6Nicolas Geoffray ? existing 36b09aacb495dce2cb3e8469f056fdc2636ae393e6Nicolas Geoffray : new_type; 37184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 38184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 39184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 40184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray// Re-compute and update the type of the instruction. Returns 41184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray// whether or not the type was changed. 4210e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlebool PrimitiveTypePropagation::UpdateType(HPhi* phi) { 43184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray Primitive::Type existing = phi->GetType(); 44184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 45102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray Primitive::Type new_type = existing; 46184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 47184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray Primitive::Type input_type = phi->InputAt(i)->GetType(); 48184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray new_type = MergeTypes(new_type, input_type); 49184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 50184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray phi->SetType(new_type); 51102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 52102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (new_type == Primitive::kPrimDouble || new_type == Primitive::kPrimFloat) { 53102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // If the phi is of floating point type, we need to update its inputs to that 54102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // type. For inputs that are phis, we need to recompute their types. 55102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 56102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HInstruction* input = phi->InputAt(i); 57102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (input->GetType() != new_type) { 58102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HInstruction* equivalent = SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, new_type); 59102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray phi->ReplaceInput(equivalent, i); 60102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (equivalent->IsPhi()) { 61102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray AddToWorklist(equivalent->AsPhi()); 62102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 63102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 64102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 65102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 66102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 67184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray return existing != new_type; 68184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 69184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 7010e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::Run() { 71184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 72184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray VisitBasicBlock(it.Current()); 73184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 74184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray ProcessWorklist(); 75184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 76184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 7710e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) { 78184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray if (block->IsLoopHeader()) { 79184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 80184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray HPhi* phi = it.Current()->AsPhi(); 81184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray // Set the initial type for the phi. Use the non back edge input for reaching 82184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray // a fixed point faster. 83102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray Primitive::Type phi_type = phi->GetType(); 84102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // We merge with the existing type, that has been set by the SSA builder. 85102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(phi_type == Primitive::kPrimVoid 86102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || phi_type == Primitive::kPrimFloat 87102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || phi_type == Primitive::kPrimDouble); 88102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray phi->SetType(MergeTypes(phi->InputAt(0)->GetType(), phi->GetType())); 89184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray AddToWorklist(phi); 90184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 91184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } else { 92184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 9321cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // Eagerly compute the type of the phi, for quicker convergence. Note 9421cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // that we don't need to add users to the worklist because we are 9521cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // doing a reverse post-order visit, therefore either the phi users are 9621cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // non-loop phi and will be visited later in the visit, or are loop-phis, 9721cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // and they are already in the work list. 9821cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray UpdateType(it.Current()->AsPhi()); 99184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 100184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 101184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 102184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 10310e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::ProcessWorklist() { 104184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray while (!worklist_.IsEmpty()) { 105184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray HPhi* instruction = worklist_.Pop(); 106184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray if (UpdateType(instruction)) { 107184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray AddDependentInstructionsToWorklist(instruction); 108184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 109184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 110184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 111184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 11210e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) { 113184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray worklist_.Add(instruction); 114184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 115184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 11610e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) { 117ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 118184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray HPhi* phi = it.Current()->GetUser()->AsPhi(); 119184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray if (phi != nullptr) { 120184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray AddToWorklist(phi); 121184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 122184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 123184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 124184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 125184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} // namespace art 126