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 36e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray : HPhi::ToPhiType(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) { 43d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray DCHECK(phi->IsLive()); 44184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray Primitive::Type existing = phi->GetType(); 45184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 46102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray Primitive::Type new_type = existing; 47184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 48184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray Primitive::Type input_type = phi->InputAt(i)->GetType(); 49184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray new_type = MergeTypes(new_type, input_type); 50184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 51184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray phi->SetType(new_type); 52102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 53d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (new_type == Primitive::kPrimDouble 54d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray || new_type == Primitive::kPrimFloat 55d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray || new_type == Primitive::kPrimNot) { 56102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // If the phi is of floating point type, we need to update its inputs to that 57102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // type. For inputs that are phis, we need to recompute their types. 58102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 59102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HInstruction* input = phi->InputAt(i); 60102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (input->GetType() != new_type) { 61d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray HInstruction* equivalent = (new_type == Primitive::kPrimNot) 62d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray ? SsaBuilder::GetReferenceTypeEquivalent(input) 63d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray : SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, new_type); 64102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray phi->ReplaceInput(equivalent, i); 65102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (equivalent->IsPhi()) { 66d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray equivalent->AsPhi()->SetLive(); 67102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray AddToWorklist(equivalent->AsPhi()); 685f4886aad49b48cdc6945e3094549145c0914fe8Nicolas Geoffray } else if (equivalent == input) { 695f4886aad49b48cdc6945e3094549145c0914fe8Nicolas Geoffray // The input has changed its type. It can be an input of other phis, 705f4886aad49b48cdc6945e3094549145c0914fe8Nicolas Geoffray // so we need to put phi users in the work list. 715f4886aad49b48cdc6945e3094549145c0914fe8Nicolas Geoffray AddDependentInstructionsToWorklist(equivalent); 72102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 73102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 74102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 75102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 76102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 77184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray return existing != new_type; 78184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 79184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 8010e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::Run() { 81184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 82184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray VisitBasicBlock(it.Current()); 83184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 84184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray ProcessWorklist(); 85184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 86184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 8710e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) { 88184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray if (block->IsLoopHeader()) { 89184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 90184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray HPhi* phi = it.Current()->AsPhi(); 91d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (phi->IsLive()) { 92d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray AddToWorklist(phi); 93d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 94184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 95184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } else { 96184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 9721cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // Eagerly compute the type of the phi, for quicker convergence. Note 9821cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // that we don't need to add users to the worklist because we are 9921cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // doing a reverse post-order visit, therefore either the phi users are 10021cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // non-loop phi and will be visited later in the visit, or are loop-phis, 10121cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray // and they are already in the work list. 102d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray HPhi* phi = it.Current()->AsPhi(); 103d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (phi->IsLive()) { 104d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray UpdateType(phi); 105d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 106184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 107184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 108184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 109184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 11010e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::ProcessWorklist() { 111184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray while (!worklist_.IsEmpty()) { 112184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray HPhi* instruction = worklist_.Pop(); 113184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray if (UpdateType(instruction)) { 114184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray AddDependentInstructionsToWorklist(instruction); 115184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 116184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 117184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 118184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 11910e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) { 120d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray DCHECK(instruction->IsLive()); 121184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray worklist_.Add(instruction); 122184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 123184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 1245f4886aad49b48cdc6945e3094549145c0914fe8Nicolas Geoffrayvoid PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) { 125ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 126184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray HPhi* phi = it.Current()->GetUser()->AsPhi(); 1275f4886aad49b48cdc6945e3094549145c0914fe8Nicolas Geoffray if (phi != nullptr && phi->IsLive() && phi->GetType() != instruction->GetType()) { 128184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray AddToWorklist(phi); 129184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 130184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 131184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 132184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 133184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} // namespace art 134