primitive_type_propagation.cc revision e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949c
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()); 68102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 69102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 70102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 71102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 72102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 73184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray return existing != new_type; 74184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 75184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 7610e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::Run() { 77184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 78184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray VisitBasicBlock(it.Current()); 79184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 80184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray ProcessWorklist(); 81184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 82184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 8310e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) { 84184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray if (block->IsLoopHeader()) { 85184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 86184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray HPhi* phi = it.Current()->AsPhi(); 87d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (phi->IsLive()) { 88d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray AddToWorklist(phi); 89d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 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. 98d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray HPhi* phi = it.Current()->AsPhi(); 99d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (phi->IsLive()) { 100d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray UpdateType(phi); 101d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 102184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 103184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 104184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 105184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 10610e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::ProcessWorklist() { 107184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray while (!worklist_.IsEmpty()) { 108184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray HPhi* instruction = worklist_.Pop(); 109184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray if (UpdateType(instruction)) { 110184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray AddDependentInstructionsToWorklist(instruction); 111184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 112184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 113184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 114184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 11510e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) { 116d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray DCHECK(instruction->IsLive()); 117184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray worklist_.Add(instruction); 118184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 119184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 12010e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravlevoid PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HPhi* instruction) { 121ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 122184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray HPhi* phi = it.Current()->GetUser()->AsPhi(); 123d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (phi != nullptr && phi->IsLive()) { 124184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray AddToWorklist(phi); 125184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 126184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray } 127184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} 128184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 129184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray} // namespace art 130