ssa_builder.cc revision a4f8831d6533e4fe5aed18433099e1130d95a877
1c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray/* 2c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * 4c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * you may not use this file except in compliance with the License. 6c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * You may obtain a copy of the License at 7c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * 8c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * 10c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * See the License for the specific language governing permissions and 14c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray * limitations under the License. 15c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray */ 16c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 17c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray#include "ssa_builder.h" 18184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 19c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray#include "nodes.h" 2010e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravle#include "primitive_type_propagation.h" 213159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray#include "ssa_phi_elimination.h" 22c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 23c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffraynamespace art { 24c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 25e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray/** 26e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * A debuggable application may require to reviving phis, to ensure their 27e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * associated DEX register is available to a debugger. This class implements 28e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * the logic for statement (c) of the SsaBuilder (see ssa_builder.h). It 29e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * also makes sure that phis with incompatible input types are not revived 30e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * (statement (b) of the SsaBuilder). 31e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * 32e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * This phase must be run after detecting dead phis through the 33e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray * DeadPhiElimination phase, and before deleting the dead phis. 34e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray */ 35e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffrayclass DeadPhiHandling : public ValueObject { 36e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray public: 37e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray explicit DeadPhiHandling(HGraph* graph) 38e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray : graph_(graph), worklist_(graph->GetArena(), kDefaultWorklistSize) {} 39e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 40e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray void Run(); 41e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 42e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray private: 43e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray void VisitBasicBlock(HBasicBlock* block); 44e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray void ProcessWorklist(); 45e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray void AddToWorklist(HPhi* phi); 46e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray void AddDependentInstructionsToWorklist(HPhi* phi); 47e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray bool UpdateType(HPhi* phi); 48e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 49e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray HGraph* const graph_; 50e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray GrowableArray<HPhi*> worklist_; 51e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 52e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray static constexpr size_t kDefaultWorklistSize = 8; 53e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 54e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(DeadPhiHandling); 55e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray}; 56e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 57e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffraybool DeadPhiHandling::UpdateType(HPhi* phi) { 58e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray Primitive::Type existing = phi->GetType(); 59e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray DCHECK(phi->IsLive()); 60e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 61e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray bool conflict = false; 62e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray Primitive::Type new_type = existing; 63e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 64e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray HInstruction* input = phi->InputAt(i); 65e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (input->IsPhi() && input->AsPhi()->IsDead()) { 66e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // We are doing a reverse post order visit of the graph, reviving 67e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // phis that have environment uses and updating their types. If an 68e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // input is a phi, and it is dead (because its input types are 69e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // conflicting), this phi must be marked dead as well. 70e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray conflict = true; 71e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray break; 72e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 73e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); 74e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 75e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // The only acceptable transitions are: 76e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // - From void to typed: first time we update the type of this phi. 77e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // - From int to reference (or reference to int): the phi has to change 78e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // to reference type. If the integer input cannot be converted to a 79e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // reference input, the phi will remain dead. 80e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (new_type == Primitive::kPrimVoid) { 81e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray new_type = input_type; 82e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else if (new_type == Primitive::kPrimNot && input_type == Primitive::kPrimInt) { 83e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray HInstruction* equivalent = SsaBuilder::GetReferenceTypeEquivalent(input); 84e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (equivalent == nullptr) { 85e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray conflict = true; 86e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray break; 87e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else { 88e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray phi->ReplaceInput(equivalent, i); 89e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (equivalent->IsPhi()) { 90e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray DCHECK_EQ(equivalent->GetType(), Primitive::kPrimNot); 91e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // We created a new phi, but that phi has the same inputs as the old phi. We 92e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // add it to the worklist to ensure its inputs can also be converted to reference. 93e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // If not, it will remain dead, and the algorithm will make the current phi dead 94e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // as well. 95e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray equivalent->AsPhi()->SetLive(); 96e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray AddToWorklist(equivalent->AsPhi()); 97e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 98e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 99e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else if (new_type == Primitive::kPrimInt && input_type == Primitive::kPrimNot) { 100e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray new_type = Primitive::kPrimNot; 101e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // Start over, we may request reference equivalents for the inputs of the phi. 102e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray i = -1; 103e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else if (new_type != input_type) { 104e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray conflict = true; 105e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray break; 106e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 107e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 108e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 109e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (conflict) { 110e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray phi->SetType(Primitive::kPrimVoid); 111e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray phi->SetDead(); 112e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray return true; 113e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else { 114e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray DCHECK(phi->IsLive()); 115e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray phi->SetType(new_type); 116e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray return existing != new_type; 117e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 118e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray} 119e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 120e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffrayvoid DeadPhiHandling::VisitBasicBlock(HBasicBlock* block) { 121e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 122e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray HPhi* phi = it.Current()->AsPhi(); 123e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (phi->IsDead() && phi->HasEnvironmentUses()) { 124e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray phi->SetLive(); 125e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (block->IsLoopHeader()) { 126e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // Give a type to the loop phi, to guarantee convergence of the algorithm. 127e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray phi->SetType(phi->InputAt(0)->GetType()); 128e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray AddToWorklist(phi); 129e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else { 130e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // Because we are doing a reverse post order visit, all inputs of 131e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // this phi have been visited and therefore had their (initial) type set. 132e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray UpdateType(phi); 133e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 134e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 135e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 136e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray} 137e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 138e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffrayvoid DeadPhiHandling::ProcessWorklist() { 139e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray while (!worklist_.IsEmpty()) { 140e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray HPhi* instruction = worklist_.Pop(); 141e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // Note that the same equivalent phi can be added multiple times in the work list, if 142e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // used by multiple phis. The first call to `UpdateType` will know whether the phi is 143e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // dead or live. 144e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (instruction->IsLive() && UpdateType(instruction)) { 145e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray AddDependentInstructionsToWorklist(instruction); 146e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 147e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 148e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray} 149e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 150e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffrayvoid DeadPhiHandling::AddToWorklist(HPhi* instruction) { 151e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray DCHECK(instruction->IsLive()); 152e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray worklist_.Add(instruction); 153e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray} 154e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 155e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffrayvoid DeadPhiHandling::AddDependentInstructionsToWorklist(HPhi* instruction) { 156e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 157e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray HPhi* phi = it.Current()->GetUser()->AsPhi(); 158e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (phi != nullptr && !phi->IsDead()) { 159e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray AddToWorklist(phi); 160e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 161e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 162e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray} 163e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 164e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffrayvoid DeadPhiHandling::Run() { 165e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 166e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray VisitBasicBlock(it.Current()); 167e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 168e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray ProcessWorklist(); 169e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray} 170e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 171e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffraystatic bool IsPhiEquivalentOf(HInstruction* instruction, HPhi* phi) { 172e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray return instruction != nullptr 173e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray && instruction->IsPhi() 174e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray && instruction->AsPhi()->GetRegNumber() == phi->GetRegNumber(); 175e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray} 176e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 177a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravlevoid SsaBuilder::FixNullConstantType() { 178a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // The order doesn't matter here. 179a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) { 180a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle for (HInstructionIterator it(itb.Current()->GetInstructions()); !it.Done(); it.Advance()) { 181a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HInstruction* equality_instr = it.Current(); 182a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) { 183a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle continue; 184a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 185a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HInstruction* left = equality_instr->InputAt(0); 186a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HInstruction* right = equality_instr->InputAt(1); 187a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HInstruction* null_instr = nullptr; 188a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 189a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle if ((left->GetType() == Primitive::kPrimNot) 190a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle && (right->IsNullConstant() || right->IsIntConstant())) { 191a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle null_instr = right; 192a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } else if ((right->GetType() == Primitive::kPrimNot) 193a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle && (left->IsNullConstant() || left->IsIntConstant())) { 194a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle null_instr = left; 195a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } else { 196a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle continue; 197a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 198a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 199a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // If we got here, we are comparing against a reference and the int constant 200a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // should be replaced with a null constant. 201a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle if (null_instr->IsIntConstant()) { 202a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle DCHECK_EQ(0, null_instr->AsIntConstant()->GetValue()); 203a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle equality_instr->ReplaceInput(GetGraph()->GetNullConstant(), null_instr == right ? 1 : 0); 204a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 205a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 206a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 207a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle} 208a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 209a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravlevoid SsaBuilder::EquivalentPhisCleanup() { 210a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // The order doesn't matter here. 211a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle for (HReversePostOrderIterator itb(*GetGraph()); !itb.Done(); itb.Advance()) { 212a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle for (HInstructionIterator it(itb.Current()->GetPhis()); !it.Done(); it.Advance()) { 213a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HPhi* phi = it.Current()->AsPhi(); 214a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HPhi* next = phi->GetNextEquivalentPhiWithSameType(); 215a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle if (next != nullptr) { 216a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle phi->ReplaceWith(next); 217a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle DCHECK(next->GetNextEquivalentPhiWithSameType() == nullptr) 218a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle << "More then one phi equivalent with type " << phi->GetType() 219a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle << " found for phi" << phi->GetId(); 220a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 221a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 222a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 223a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle} 224a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 225c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffrayvoid SsaBuilder::BuildSsa() { 226804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // 1) Visit in reverse post order. We need to have all predecessors of a block visited 227c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // (with the exception of loops) in order to create the right environment for that 228c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // block. For loops, we create phis whose inputs will be set in 2). 229804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 230804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray VisitBasicBlock(it.Current()); 231c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 232c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 233c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // 2) Set inputs of loop phis. 234c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray for (size_t i = 0; i < loop_headers_.Size(); i++) { 235c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray HBasicBlock* block = loop_headers_.Get(i); 236f635e63318447ca04731b265a86a573c9ed1737cNicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 237c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray HPhi* phi = it.Current()->AsPhi(); 238622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffray for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) { 239a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray HInstruction* input = ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber()); 240a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray phi->AddInput(input); 241c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 242c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 243c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 244c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 245d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray // 3) Mark dead phis. This will mark phis that are only used by environments: 2463159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray // at the DEX level, the type of these phis does not need to be consistent, but 2473159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray // our code generator will complain if the inputs of a phi do not have the same 248d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray // type. The marking allows the type propagation to know which phis it needs 249d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray // to handle. We mark but do not eliminate: the elimination will be done in 250b59dba05697b4ac6c86cb4f45c9222c9c6ad852bNicolas Geoffray // step 9). 251b59dba05697b4ac6c86cb4f45c9222c9c6ad852bNicolas Geoffray SsaDeadPhiElimination dead_phis_for_type_propagation(GetGraph()); 252b59dba05697b4ac6c86cb4f45c9222c9c6ad852bNicolas Geoffray dead_phis_for_type_propagation.MarkDeadPhis(); 2533159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray 2543159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray // 4) Propagate types of phis. At this point, phis are typed void in the general 255d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray // case, or float/double/reference when we created an equivalent phi. So we 2563159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray // need to propagate the types across phis to give them a correct type. 25710e244f9e7f6d96a95c910a2bedef5bd3810c637Calin Juravle PrimitiveTypePropagation type_propagation(GetGraph()); 258184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray type_propagation.Run(); 259184d640d2a3ac86d871dab58386a50cc9bb973f9Nicolas Geoffray 260a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // 5) Fix the type for null constants which are part of an equality comparison. 261a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle FixNullConstantType(); 262a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 263a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // 6) When creating equivalent phis we copy the inputs of the original phi which 264a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // may be improperly typed. This will be fixed during the type propagation but 265a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // as a result we may end up with two equivalent phis with the same type for 266a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // the same dex register. This pass cleans them up. 267a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle EquivalentPhisCleanup(); 268a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 269a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // 7) Mark dead phis again. Step 4) may have introduced new phis. 270a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // Step 6) might enable the death of new phis. 271b59dba05697b4ac6c86cb4f45c9222c9c6ad852bNicolas Geoffray SsaDeadPhiElimination dead_phis(GetGraph()); 272b59dba05697b4ac6c86cb4f45c9222c9c6ad852bNicolas Geoffray dead_phis.MarkDeadPhis(); 273b59dba05697b4ac6c86cb4f45c9222c9c6ad852bNicolas Geoffray 274a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // 8) Now that the graph is correctly typed, we can get rid of redundant phis. 275e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // Note that we cannot do this phase before type propagation, otherwise 276e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // we could get rid of phi equivalents, whose presence is a requirement for the 277e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // type propagation phase. Note that this is to satisfy statement (a) of the 278e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // SsaBuilder (see ssa_builder.h). 279e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray SsaRedundantPhiElimination redundant_phi(GetGraph()); 280e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray redundant_phi.Run(); 281e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 282a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // 9) Make sure environments use the right phi "equivalent": a phi marked dead 283e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // can have a phi equivalent that is not dead. We must therefore update 284e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // all environment uses of the dead phi to use its equivalent. Note that there 285e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // can be multiple phis for the same Dex register that are live (for example 286e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // when merging constants), in which case it is OK for the environments 287e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // to just reference one. 288e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { 289e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray HBasicBlock* block = it.Current(); 290e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { 291e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray HPhi* phi = it_phis.Current()->AsPhi(); 292e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // If the phi is not dead, or has no environment uses, there is nothing to do. 293e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue; 294e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray HInstruction* next = phi->GetNext(); 295e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (!IsPhiEquivalentOf(next, phi)) continue; 296e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (next->AsPhi()->IsDead()) { 297e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // If the phi equivalent is dead, check if there is another one. 298e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray next = next->GetNext(); 299e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (!IsPhiEquivalentOf(next, phi)) continue; 300e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // There can be at most two phi equivalents. 301e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray DCHECK(!IsPhiEquivalentOf(next->GetNext(), phi)); 302e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (next->AsPhi()->IsDead()) continue; 303e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 304e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // We found a live phi equivalent. Update the environment uses of `phi` with it. 305e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray phi->ReplaceWith(next); 306e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 307d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 308d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray 309a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // 10) Deal with phis to guarantee liveness of phis in case of a debuggable 310e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // application. This is for satisfying statement (c) of the SsaBuilder 311e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // (see ssa_builder.h). 312e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (GetGraph()->IsDebuggable()) { 313e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray DeadPhiHandling dead_phi_handler(GetGraph()); 314e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray dead_phi_handler.Run(); 315e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } 316e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 317a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // 11) Now that the right phis are used for the environments, and we 318e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // have potentially revive dead phis in case of a debuggable application, 319e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // we can eliminate phis we do not need. Regardless of the debuggable status, 320e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // this phase is necessary for statement (b) of the SsaBuilder (see ssa_builder.h), 321e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // as well as for the code generation, which does not deal with phis of conflicting 322e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray // input types. 323e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray dead_phis.EliminateDeadPhis(); 324e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray 325a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // 12) Clear locals. 326f635e63318447ca04731b265a86a573c9ed1737cNicolas Geoffray for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions()); 327c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray !it.Done(); 328c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray it.Advance()) { 329c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray HInstruction* current = it.Current(); 330476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (current->IsLocal()) { 331c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray current->GetBlock()->RemoveInstruction(current); 332c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 333c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 334c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} 335c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 336c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas GeoffrayHInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) { 337ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil return GetLocalsFor(block)->GetInstructionAt(local); 338c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} 339c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 340c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffrayvoid SsaBuilder::VisitBasicBlock(HBasicBlock* block) { 341c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray current_locals_ = GetLocalsFor(block); 342c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 343c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray if (block->IsLoopHeader()) { 344c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // If the block is a loop header, we know we only have visited the pre header 345804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // because we are visiting in reverse post order. We create phis for all initialized 346c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // locals from the pre header. Their inputs will be populated at the end of 347c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // the analysis. 348c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray for (size_t local = 0; local < current_locals_->Size(); local++) { 349c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local); 350c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray if (incoming != nullptr) { 351c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray HPhi* phi = new (GetGraph()->GetArena()) HPhi( 352c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid); 353c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray block->AddPhi(phi); 354ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil current_locals_->SetRawEnvAt(local, phi); 355c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 356c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 357c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // Save the loop header so that the last phase of the analysis knows which 358c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // blocks need to be updated. 359c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray loop_headers_.Add(block); 360622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffray } else if (block->GetPredecessors().Size() > 0) { 361804d09372cc3d80d537da1489da4a45e0e19aa5dNicolas Geoffray // All predecessors have already been visited because we are visiting in reverse post order. 362c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // We merge the values of all locals, creating phis if those values differ. 363c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray for (size_t local = 0; local < current_locals_->Size(); local++) { 3647c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray bool one_predecessor_has_no_value = false; 365c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray bool is_different = false; 366622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffray HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(0), local); 3677c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray 3687c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 3697c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray HInstruction* current = ValueOfLocal(block->GetPredecessors().Get(i), local); 3707c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray if (current == nullptr) { 371ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray one_predecessor_has_no_value = true; 372ec7e4727e99aa1416398ac5a684f5024817a25c7Nicolas Geoffray break; 3737c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray } else if (current != value) { 374c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray is_different = true; 375c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 376c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 3777c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray 3787c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray if (one_predecessor_has_no_value) { 3797c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray // If one predecessor has no value for this local, we trust the verifier has 3807c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray // successfully checked that there is a store dominating any read after this block. 3817c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray continue; 3827c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray } 3837c3560f2ce0ec9484004d05a94bfaa6e02f5a96aNicolas Geoffray 384c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray if (is_different) { 385c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray HPhi* phi = new (GetGraph()->GetArena()) HPhi( 386622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffray GetGraph()->GetArena(), local, block->GetPredecessors().Size(), Primitive::kPrimVoid); 387622d9c31febd950255b36a48b47e1f630197c5feNicolas Geoffray for (size_t i = 0; i < block->GetPredecessors().Size(); i++) { 388277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HInstruction* pred_value = ValueOfLocal(block->GetPredecessors().Get(i), local); 389277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe phi->SetRawInputAt(i, pred_value); 390c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 391c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray block->AddPhi(phi); 392c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray value = phi; 393c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 394ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil current_locals_->SetRawEnvAt(local, value); 395c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 396c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 397c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 398c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // Visit all instructions. The instructions of interest are: 399c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // - HLoadLocal: replace them with the current value of the local. 400c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // - HStoreLocal: update current value of the local and remove the instruction. 401c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // - Instructions that require an environment: populate their environment 402c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray // with the current values of the locals. 403f635e63318447ca04731b265a86a573c9ed1737cNicolas Geoffray for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 404c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray it.Current()->Accept(this); 405c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 406c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} 407c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 408102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray/** 409102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * Constants in the Dex format are not typed. So the builder types them as 410102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * integers, but when doing the SSA form, we might realize the constant 411102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * is used for floating point operations. We create a floating-point equivalent 412102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * constant to make the operations correctly typed. 413102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray */ 4148d5b8b295930aaa43255c4f0b74ece3ee8b43a47David BrazdilHFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) { 415102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // We place the floating point constant next to this constant. 416102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HFloatConstant* result = constant->GetNext()->AsFloatConstant(); 417102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (result == nullptr) { 418102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HGraph* graph = constant->GetBlock()->GetGraph(); 419102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ArenaAllocator* allocator = graph->GetArena(); 420da4d79bc9a4aeb9da7c6259ce4c9c1c3bf545eb8Roland Levillain result = new (allocator) HFloatConstant(bit_cast<float, int32_t>(constant->GetValue())); 421102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 422102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 423102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // If there is already a constant with the expected type, we know it is 424102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // the floating point equivalent of this constant. 425da4d79bc9a4aeb9da7c6259ce4c9c1c3bf545eb8Roland Levillain DCHECK_EQ((bit_cast<int32_t, float>(result->GetValue())), constant->GetValue()); 426102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 427102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return result; 428102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray} 429102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 430102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray/** 431102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * Wide constants in the Dex format are not typed. So the builder types them as 432102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * longs, but when doing the SSA form, we might realize the constant 433102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * is used for floating point operations. We create a floating-point equivalent 434102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * constant to make the operations correctly typed. 435102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray */ 4368d5b8b295930aaa43255c4f0b74ece3ee8b43a47David BrazdilHDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { 437102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // We place the floating point constant next to this constant. 438102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HDoubleConstant* result = constant->GetNext()->AsDoubleConstant(); 439102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (result == nullptr) { 440102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HGraph* graph = constant->GetBlock()->GetGraph(); 441102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ArenaAllocator* allocator = graph->GetArena(); 442da4d79bc9a4aeb9da7c6259ce4c9c1c3bf545eb8Roland Levillain result = new (allocator) HDoubleConstant(bit_cast<double, int64_t>(constant->GetValue())); 443102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 444102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 445102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // If there is already a constant with the expected type, we know it is 446102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // the floating point equivalent of this constant. 447da4d79bc9a4aeb9da7c6259ce4c9c1c3bf545eb8Roland Levillain DCHECK_EQ((bit_cast<int64_t, double>(result->GetValue())), constant->GetValue()); 448102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 449102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return result; 450102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray} 451102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 452102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray/** 453102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * Because of Dex format, we might end up having the same phi being 454d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray * used for non floating point operations and floating point / reference operations. 455d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray * Because we want the graph to be correctly typed (and thereafter avoid moves between 456102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * floating point registers and core registers), we need to create a copy of the 457d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray * phi with a floating point / reference type. 458102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray */ 4598d5b8b295930aaa43255c4f0b74ece3ee8b43a47David BrazdilHPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) { 460d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray // We place the floating point /reference phi next to this phi. 461102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HInstruction* next = phi->GetNext(); 462d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (next != nullptr 463d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray && next->AsPhi()->GetRegNumber() == phi->GetRegNumber() 464d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray && next->GetType() != type) { 465d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray // Move to the next phi to see if it is the one we are looking for. 466d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray next = next->GetNext(); 467d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 468d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray 469d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (next == nullptr 470d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber()) 471d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray || (next->GetType() != type)) { 472102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ArenaAllocator* allocator = phi->GetBlock()->GetGraph()->GetArena(); 473102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HPhi* new_phi = new (allocator) HPhi(allocator, phi->GetRegNumber(), phi->InputCount(), type); 474102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 475102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // Copy the inputs. Note that the graph may not be correctly typed by doing this copy, 476102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // but the type propagation phase will fix it. 477102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray new_phi->SetRawInputAt(i, phi->InputAt(i)); 478102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 479102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray phi->GetBlock()->InsertPhiAfter(new_phi, phi); 480102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return new_phi; 481102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 48221cc798cd56a069a3d51a0215020676065780939Nicolas Geoffray DCHECK_EQ(next->GetType(), type); 483102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return next->AsPhi(); 484102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 485102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray} 486102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 487102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas GeoffrayHInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* user, 488102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HInstruction* value, 489102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray Primitive::Type type) { 490102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (value->IsArrayGet()) { 491102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // The verifier has checked that values in arrays cannot be used for both 492102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // floating point and non-floating point operations. It is therefore safe to just 493102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // change the type of the operation. 494102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray value->AsArrayGet()->SetType(type); 495102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return value; 496102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else if (value->IsLongConstant()) { 497102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return GetDoubleEquivalent(value->AsLongConstant()); 498102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else if (value->IsIntConstant()) { 499102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return GetFloatEquivalent(value->AsIntConstant()); 500102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else if (value->IsPhi()) { 501d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); 502102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 503102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // For other instructions, we assume the verifier has checked that the dex format is correctly 504102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // typed and the value in a dex register will not be used for both floating point and 505102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // non-floating point operations. So the only reason an instruction would want a floating 506102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // point equivalent is for an unused phi that will be removed by the dead phi elimination phase. 507102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(user->IsPhi()); 508102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return value; 509102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 510102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray} 511102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 512d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas GeoffrayHInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { 513e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) { 514d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray return value->GetBlock()->GetGraph()->GetNullConstant(); 515e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else if (value->IsPhi()) { 516d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot); 517e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else { 518e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray return nullptr; 519d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 520d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray} 521d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray 522c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffrayvoid SsaBuilder::VisitLoadLocal(HLoadLocal* load) { 523ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil HInstruction* value = current_locals_->GetInstructionAt(load->GetLocal()->GetRegNumber()); 524d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray // If the operation requests a specific type, we make sure its input is of that type. 525d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (load->GetType() != value->GetType()) { 526d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (load->GetType() == Primitive::kPrimFloat || load->GetType() == Primitive::kPrimDouble) { 527d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray value = GetFloatOrDoubleEquivalent(load, value, load->GetType()); 528d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } else if (load->GetType() == Primitive::kPrimNot) { 529d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray value = GetReferenceTypeEquivalent(value); 530d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 531102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 532102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray load->ReplaceWith(value); 533c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray load->GetBlock()->RemoveInstruction(load); 534c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} 535c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 536c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffrayvoid SsaBuilder::VisitStoreLocal(HStoreLocal* store) { 537ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil current_locals_->SetRawEnvAt(store->GetLocal()->GetRegNumber(), store->InputAt(1)); 538c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray store->GetBlock()->RemoveInstruction(store); 539c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} 540c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 541c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffrayvoid SsaBuilder::VisitInstruction(HInstruction* instruction) { 542c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray if (!instruction->NeedsEnvironment()) { 543c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray return; 544c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray } 545c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment( 546c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray GetGraph()->GetArena(), current_locals_->Size()); 547ed59619b370ef23ffbb25d1d01f615e60a9262b6David Brazdil environment->CopyFrom(current_locals_); 5483dcd58cd54a922b864494fb7fff4a7f7a8562db9Nicolas Geoffray instruction->SetRawEnvironment(environment); 549c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} 550c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 551421e9f9088b51e9680a3dfcae6965fc1854d3ee4Nicolas Geoffrayvoid SsaBuilder::VisitTemporary(HTemporary* temp) { 552421e9f9088b51e9680a3dfcae6965fc1854d3ee4Nicolas Geoffray // Temporaries are only used by the baseline register allocator. 553421e9f9088b51e9680a3dfcae6965fc1854d3ee4Nicolas Geoffray temp->GetBlock()->RemoveInstruction(temp); 554421e9f9088b51e9680a3dfcae6965fc1854d3ee4Nicolas Geoffray} 555421e9f9088b51e9680a3dfcae6965fc1854d3ee4Nicolas Geoffray 556c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} // namespace art 557