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 1986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil#include "bytecode_utils.h" 2090b936ddda63139ff46a6755c3b83ad6e4ab4ac5Andreas Gampe#include "mirror/class-inl.h" 21c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray#include "nodes.h" 224833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil#include "reference_type_propagation.h" 2390b936ddda63139ff46a6755c3b83ad6e4ab4ac5Andreas Gampe#include "scoped_thread_state_change-inl.h" 243159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray#include "ssa_phi_elimination.h" 25c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 26c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffraynamespace art { 27c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 28a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravlevoid SsaBuilder::FixNullConstantType() { 29a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // The order doesn't matter here. 302c45bc9137c29f886e69923535aff31a74d90829Vladimir Marko for (HBasicBlock* block : graph_->GetReversePostOrder()) { 312c45bc9137c29f886e69923535aff31a74d90829Vladimir Marko for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 32a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HInstruction* equality_instr = it.Current(); 33a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle if (!equality_instr->IsEqual() && !equality_instr->IsNotEqual()) { 34a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle continue; 35a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 36a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HInstruction* left = equality_instr->InputAt(0); 37a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HInstruction* right = equality_instr->InputAt(1); 3851d400d4ebd41b9fb4d67ac3179f8fb66a090fddNicolas Geoffray HInstruction* int_operand = nullptr; 39a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 4051d400d4ebd41b9fb4d67ac3179f8fb66a090fddNicolas Geoffray if ((left->GetType() == Primitive::kPrimNot) && (right->GetType() == Primitive::kPrimInt)) { 4151d400d4ebd41b9fb4d67ac3179f8fb66a090fddNicolas Geoffray int_operand = right; 4251d400d4ebd41b9fb4d67ac3179f8fb66a090fddNicolas Geoffray } else if ((right->GetType() == Primitive::kPrimNot) 4351d400d4ebd41b9fb4d67ac3179f8fb66a090fddNicolas Geoffray && (left->GetType() == Primitive::kPrimInt)) { 4451d400d4ebd41b9fb4d67ac3179f8fb66a090fddNicolas Geoffray int_operand = left; 45a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } else { 46a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle continue; 47a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 48a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 49a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // If we got here, we are comparing against a reference and the int constant 50a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // should be replaced with a null constant. 5151d400d4ebd41b9fb4d67ac3179f8fb66a090fddNicolas Geoffray // Both type propagation and redundant phi elimination ensure `int_operand` 5251d400d4ebd41b9fb4d67ac3179f8fb66a090fddNicolas Geoffray // can only be the 0 constant. 5315bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray DCHECK(int_operand->IsIntConstant()) << int_operand->DebugName(); 5451d400d4ebd41b9fb4d67ac3179f8fb66a090fddNicolas Geoffray DCHECK_EQ(0, int_operand->AsIntConstant()->GetValue()); 55dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil equality_instr->ReplaceInput(graph_->GetNullConstant(), int_operand == right ? 1 : 0); 56a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 57a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 58a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle} 59a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 60a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravlevoid SsaBuilder::EquivalentPhisCleanup() { 61a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle // The order doesn't matter here. 622c45bc9137c29f886e69923535aff31a74d90829Vladimir Marko for (HBasicBlock* block : graph_->GetReversePostOrder()) { 632c45bc9137c29f886e69923535aff31a74d90829Vladimir Marko for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 64a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HPhi* phi = it.Current()->AsPhi(); 65a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle HPhi* next = phi->GetNextEquivalentPhiWithSameType(); 66a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle if (next != nullptr) { 674833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Make sure we do not replace a live phi with a dead phi. A live phi 684833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // has been handled by the type propagation phase, unlike a dead phi. 694230e1895b915a22363452823b0e51eabe92cb60Nicolas Geoffray if (next->IsLive()) { 704230e1895b915a22363452823b0e51eabe92cb60Nicolas Geoffray phi->ReplaceWith(next); 714833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil phi->SetDead(); 724230e1895b915a22363452823b0e51eabe92cb60Nicolas Geoffray } else { 734230e1895b915a22363452823b0e51eabe92cb60Nicolas Geoffray next->ReplaceWith(phi); 744230e1895b915a22363452823b0e51eabe92cb60Nicolas Geoffray } 75a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle DCHECK(next->GetNextEquivalentPhiWithSameType() == nullptr) 76a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle << "More then one phi equivalent with type " << phi->GetType() 77a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle << " found for phi" << phi->GetId(); 78a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 79a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 80a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle } 81a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle} 82a4f8831d6533e4fe5aed18433099e1130d95a877Calin Juravle 834833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilvoid SsaBuilder::FixEnvironmentPhis() { 842c45bc9137c29f886e69923535aff31a74d90829Vladimir Marko for (HBasicBlock* block : graph_->GetReversePostOrder()) { 852bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil for (HInstructionIterator it_phis(block->GetPhis()); !it_phis.Done(); it_phis.Advance()) { 862bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil HPhi* phi = it_phis.Current()->AsPhi(); 872bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil // If the phi is not dead, or has no environment uses, there is nothing to do. 882bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil if (!phi->IsDead() || !phi->HasEnvironmentUses()) continue; 892bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil HInstruction* next = phi->GetNext(); 902bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil if (!phi->IsVRegEquivalentOf(next)) continue; 912bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil if (next->AsPhi()->IsDead()) { 922bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil // If the phi equivalent is dead, check if there is another one. 932bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil next = next->GetNext(); 942bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil if (!phi->IsVRegEquivalentOf(next)) continue; 952bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil // There can be at most two phi equivalents. 962bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil DCHECK(!phi->IsVRegEquivalentOf(next->GetNext())); 972bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil if (next->AsPhi()->IsDead()) continue; 982bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil } 992bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil // We found a live phi equivalent. Update the environment uses of `phi` with it. 1002bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil phi->ReplaceWith(next); 1012bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil } 1022bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil } 1034833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 1042bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil 1054833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilstatic void AddDependentInstructionsToWorklist(HInstruction* instruction, 1064833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil ArenaVector<HPhi*>* worklist) { 1074833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // If `instruction` is a dead phi, type conflict was just identified. All its 1084833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // live phi users, and transitively users of those users, therefore need to be 1094833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // marked dead/conflicting too, so we add them to the worklist. Otherwise we 1104833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // add users whose type does not match and needs to be updated. 1114833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil bool add_all_live_phis = instruction->IsPhi() && instruction->AsPhi()->IsDead(); 11246817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 11346817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko HInstruction* user = use.GetUser(); 1144833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (user->IsPhi() && user->AsPhi()->IsLive()) { 1154833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (add_all_live_phis || user->GetType() != instruction->GetType()) { 1164833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil worklist->push_back(user->AsPhi()); 1174833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 1184833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 1192bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil } 1204833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 1214833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 1224833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil// Find a candidate primitive type for `phi` by merging the type of its inputs. 1234833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil// Return false if conflict is identified. 1244833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilstatic bool TypePhiFromInputs(HPhi* phi) { 1254833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil Primitive::Type common_type = phi->GetType(); 1262bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil 127372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko for (HInstruction* input : phi->GetInputs()) { 1284833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (input->IsPhi() && input->AsPhi()->IsDead()) { 1294833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Phis are constructed live so if an input is a dead phi, it must have 1304833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // been made dead due to type conflict. Mark this phi conflicting too. 1314833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return false; 1324833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 1334833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 1344833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil Primitive::Type input_type = HPhi::ToPhiType(input->GetType()); 1354833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (common_type == input_type) { 1364833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // No change in type. 137d87f3eaa80139564969433fd47c0f6abf8dc46baDavid Brazdil } else if (Primitive::Is64BitType(common_type) != Primitive::Is64BitType(input_type)) { 1384833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Types are of different sizes, e.g. int vs. long. Must be a conflict. 1394833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return false; 1404833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } else if (Primitive::IsIntegralType(common_type)) { 1414833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Previous inputs were integral, this one is not but is of the same size. 1424833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // This does not imply conflict since some bytecode instruction types are 1434833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // ambiguous. TypeInputsOfPhi will either type them or detect a conflict. 1444833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(Primitive::IsFloatingPointType(input_type) || input_type == Primitive::kPrimNot); 1454833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil common_type = input_type; 1464833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } else if (Primitive::IsIntegralType(input_type)) { 1474833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Input is integral, common type is not. Same as in the previous case, if 1484833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // there is a conflict, it will be detected during TypeInputsOfPhi. 1494833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(Primitive::IsFloatingPointType(common_type) || common_type == Primitive::kPrimNot); 1504833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } else { 1514833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Combining float and reference types. Clearly a conflict. 1524833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK((common_type == Primitive::kPrimFloat && input_type == Primitive::kPrimNot) || 1534833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil (common_type == Primitive::kPrimNot && input_type == Primitive::kPrimFloat)); 1544833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return false; 1554833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 1564833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 1574833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 1584833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // We have found a candidate type for the phi. Set it and return true. We may 1594833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // still discover conflict whilst typing the individual inputs in TypeInputsOfPhi. 1604833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil phi->SetType(common_type); 1614833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return true; 1624833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 1634833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 1644833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil// Replace inputs of `phi` to match its type. Return false if conflict is identified. 1654833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilbool SsaBuilder::TypeInputsOfPhi(HPhi* phi, ArenaVector<HPhi*>* worklist) { 1664833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil Primitive::Type common_type = phi->GetType(); 16750a9ed014e3b4dec67246ea07727d7bec89bfb17Nicolas Geoffray if (Primitive::IsIntegralType(common_type)) { 16850a9ed014e3b4dec67246ea07727d7bec89bfb17Nicolas Geoffray // We do not need to retype ambiguous inputs because they are always constructed 16950a9ed014e3b4dec67246ea07727d7bec89bfb17Nicolas Geoffray // with the integral type candidate. 1704833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (kIsDebugBuild) { 171372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko for (HInstruction* input : phi->GetInputs()) { 17250a9ed014e3b4dec67246ea07727d7bec89bfb17Nicolas Geoffray DCHECK(HPhi::ToPhiType(input->GetType()) == common_type); 1734833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 1744833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 1754833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Inputs did not need to be replaced, hence no conflict. Report success. 1764833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return true; 1774833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } else { 1784833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(common_type == Primitive::kPrimNot || Primitive::IsFloatingPointType(common_type)); 179e90049140fdfb89080e5cc9b000b0c9be8c18bcdVladimir Marko HInputsRef inputs = phi->GetInputs(); 180372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko for (size_t i = 0; i < inputs.size(); ++i) { 181372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko HInstruction* input = inputs[i]; 1824833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (input->GetType() != common_type) { 1834833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Input type does not match phi's type. Try to retype the input or 1844833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // generate a suitably typed equivalent. 1854833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HInstruction* equivalent = (common_type == Primitive::kPrimNot) 1864833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil ? GetReferenceTypeEquivalent(input) 1874833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil : GetFloatOrDoubleEquivalent(input, common_type); 1884833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (equivalent == nullptr) { 1894833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Input could not be typed. Report conflict. 1904833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return false; 1914833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 1924833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Make sure the input did not change its type and we do not need to 1934833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // update its users. 1944833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK_NE(input, equivalent); 1954833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 1964833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil phi->ReplaceInput(equivalent, i); 1974833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (equivalent->IsPhi()) { 1984833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil worklist->push_back(equivalent->AsPhi()); 1994833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2004833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2014833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2024833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // All inputs either matched the type of the phi or we successfully replaced 2034833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // them with a suitable equivalent. Report success. 2044833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return true; 2054833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2064833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 2074833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2084833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil// Attempt to set the primitive type of `phi` to match its inputs. Return whether 2094833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil// it was changed by the algorithm or not. 2104833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilbool SsaBuilder::UpdatePrimitiveType(HPhi* phi, ArenaVector<HPhi*>* worklist) { 2114833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(phi->IsLive()); 2124833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil Primitive::Type original_type = phi->GetType(); 2134833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2144833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Try to type the phi in two stages: 2154833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // (1) find a candidate type for the phi by merging types of all its inputs, 2164833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // (2) try to type the phi's inputs to that candidate type. 2174833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Either of these stages may detect a type conflict and fail, in which case 2184833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // we immediately abort. 2194833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (!TypePhiFromInputs(phi) || !TypeInputsOfPhi(phi, worklist)) { 2204833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Conflict detected. Mark the phi dead and return true because it changed. 2214833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil phi->SetDead(); 2224833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return true; 2234833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2244833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2254833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Return true if the type of the phi has changed. 2264833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return phi->GetType() != original_type; 2274833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 2284833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2294833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilvoid SsaBuilder::RunPrimitiveTypePropagation() { 2303ea5a97d27468cec846d958c38d0d706ef7ec67eVladimir Marko ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter(kArenaAllocGraphBuilder)); 2314833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2322c45bc9137c29f886e69923535aff31a74d90829Vladimir Marko for (HBasicBlock* block : graph_->GetReversePostOrder()) { 2334833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (block->IsLoopHeader()) { 2344833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 2354833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HPhi* phi = phi_it.Current()->AsPhi(); 2364833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (phi->IsLive()) { 2374833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil worklist.push_back(phi); 2384833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2394833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2404833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } else { 2414833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil for (HInstructionIterator phi_it(block->GetPhis()); !phi_it.Done(); phi_it.Advance()) { 2424833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Eagerly compute the type of the phi, for quicker convergence. Note 2434833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // that we don't need to add users to the worklist because we are 2444833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // doing a reverse post-order visit, therefore either the phi users are 2454833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // non-loop phi and will be visited later in the visit, or are loop-phis, 2464833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // and they are already in the work list. 2474833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HPhi* phi = phi_it.Current()->AsPhi(); 2484833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (phi->IsLive()) { 2494833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil UpdatePrimitiveType(phi, &worklist); 2504833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2514833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2524833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2534833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2544833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2554833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil ProcessPrimitiveTypePropagationWorklist(&worklist); 2564833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil EquivalentPhisCleanup(); 2574833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 2584833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2594833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilvoid SsaBuilder::ProcessPrimitiveTypePropagationWorklist(ArenaVector<HPhi*>* worklist) { 2604833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Process worklist 2614833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil while (!worklist->empty()) { 2624833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HPhi* phi = worklist->back(); 2634833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil worklist->pop_back(); 2644833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // The phi could have been made dead as a result of conflicts while in the 2654833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // worklist. If it is now dead, there is no point in updating its type. 2664833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (phi->IsLive() && UpdatePrimitiveType(phi, worklist)) { 2674833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil AddDependentInstructionsToWorklist(phi, worklist); 2684833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2694833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 2704833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 2714833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2724833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilstatic HArrayGet* FindFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { 2734833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil Primitive::Type type = aget->GetType(); 2744833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(Primitive::IsIntOrLongType(type)); 275dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil HInstruction* next = aget->GetNext(); 276dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil if (next != nullptr && next->IsArrayGet()) { 277dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil HArrayGet* next_aget = next->AsArrayGet(); 278dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil if (next_aget->IsEquivalentOf(aget)) { 279dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil return next_aget; 280dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil } 281dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil } 282dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil return nullptr; 2834833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 2844833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2854833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilstatic HArrayGet* CreateFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { 2864833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil Primitive::Type type = aget->GetType(); 2874833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(Primitive::IsIntOrLongType(type)); 2884833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(FindFloatOrDoubleEquivalentOfArrayGet(aget) == nullptr); 2894833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 2904833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HArrayGet* equivalent = new (aget->GetBlock()->GetGraph()->GetArena()) HArrayGet( 2914833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil aget->GetArray(), 2924833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil aget->GetIndex(), 2934833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil type == Primitive::kPrimInt ? Primitive::kPrimFloat : Primitive::kPrimDouble, 2944833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil aget->GetDexPc()); 2954833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil aget->GetBlock()->InsertInstructionAfter(equivalent, aget); 2964833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return equivalent; 2974833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 2984833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 29915693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdilstatic Primitive::Type GetPrimitiveArrayComponentType(HInstruction* array) 300bdf7f1c3ab65ccb70f62db5ab31dba060632d458Andreas Gampe REQUIRES_SHARED(Locks::mutator_lock_) { 30115693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil ReferenceTypeInfo array_type = array->GetReferenceTypeInfo(); 3024833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(array_type.IsPrimitiveArrayClass()); 30315693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil return array_type.GetTypeHandle()->GetComponentType()->GetPrimitiveType(); 3044833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 3054833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 30615693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdilbool SsaBuilder::FixAmbiguousArrayOps() { 30715693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil if (ambiguous_agets_.empty() && ambiguous_asets_.empty()) { 3084833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return true; 3094833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 3104833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 3114833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // The wrong ArrayGet equivalent may still have Phi uses coming from ArraySet 3124833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // uses (because they are untyped) and environment uses (if --debuggable). 3134833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // After resolving all ambiguous ArrayGets, we will re-run primitive type 3144833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // propagation on the Phis which need to be updated. 3153ea5a97d27468cec846d958c38d0d706ef7ec67eVladimir Marko ArenaVector<HPhi*> worklist(graph_->GetArena()->Adapter(kArenaAllocGraphBuilder)); 3164833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 3174833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil { 3184833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil ScopedObjectAccess soa(Thread::Current()); 3194833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 3204833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil for (HArrayGet* aget_int : ambiguous_agets_) { 32115693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil HInstruction* array = aget_int->GetArray(); 32215693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { 3234833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // RTP did not type the input array. Bail. 3244833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return false; 3254833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 3264833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 3274833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HArrayGet* aget_float = FindFloatOrDoubleEquivalentOfArrayGet(aget_int); 32815693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil Primitive::Type array_type = GetPrimitiveArrayComponentType(array); 32915693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil DCHECK_EQ(Primitive::Is64BitType(aget_int->GetType()), Primitive::Is64BitType(array_type)); 33015693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil 33115693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil if (Primitive::IsIntOrLongType(array_type)) { 3324833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (aget_float != nullptr) { 3334833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // There is a float/double equivalent. We must replace it and re-run 3344833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // primitive type propagation on all dependent instructions. 3354833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil aget_float->ReplaceWith(aget_int); 3364833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil aget_float->GetBlock()->RemoveInstruction(aget_float); 3374833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil AddDependentInstructionsToWorklist(aget_int, &worklist); 3384833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 3394833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } else { 34015693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil DCHECK(Primitive::IsFloatingPointType(array_type)); 3414833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (aget_float == nullptr) { 3424833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // This is a float/double ArrayGet but there were no typed uses which 3434833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // would create the typed equivalent. Create it now. 3444833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil aget_float = CreateFloatOrDoubleEquivalentOfArrayGet(aget_int); 3454833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 3464833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Replace the original int/long instruction. Note that it may have phi 3474833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // uses, environment uses, as well as real uses (from untyped ArraySets). 3484833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // We need to re-run primitive type propagation on its dependent instructions. 3494833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil aget_int->ReplaceWith(aget_float); 3504833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil aget_int->GetBlock()->RemoveInstruction(aget_int); 3514833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil AddDependentInstructionsToWorklist(aget_float, &worklist); 3524833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 3534833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 3544833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 35515693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // Set a flag stating that types of ArrayGets have been resolved. Requesting 35615693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // equivalent of the wrong type with GetFloatOrDoubleEquivalentOfArrayGet 35715693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // will fail from now on. 35815693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil agets_fixed_ = true; 35915693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil 36015693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil for (HArraySet* aset : ambiguous_asets_) { 36115693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil HInstruction* array = aset->GetArray(); 36215693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil if (!array->GetReferenceTypeInfo().IsPrimitiveArrayClass()) { 36315693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // RTP did not type the input array. Bail. 36415693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil return false; 36515693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil } 36615693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil 36715693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil HInstruction* value = aset->GetValue(); 36815693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil Primitive::Type value_type = value->GetType(); 36915693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil Primitive::Type array_type = GetPrimitiveArrayComponentType(array); 37015693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil DCHECK_EQ(Primitive::Is64BitType(value_type), Primitive::Is64BitType(array_type)); 37115693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil 37215693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil if (Primitive::IsFloatingPointType(array_type)) { 37315693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil if (!Primitive::IsFloatingPointType(value_type)) { 37415693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil DCHECK(Primitive::IsIntegralType(value_type)); 37515693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // Array elements are floating-point but the value has not been replaced 37615693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // with its floating-point equivalent. The replacement must always 37715693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // succeed in code validated by the verifier. 37815693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil HInstruction* equivalent = GetFloatOrDoubleEquivalent(value, array_type); 37915693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil DCHECK(equivalent != nullptr); 38015693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil aset->ReplaceInput(equivalent, /* input_index */ 2); 38115693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil if (equivalent->IsPhi()) { 38215693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // Returned equivalent is a phi which may not have had its inputs 38315693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // replaced yet. We need to run primitive type propagation on it. 38415693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil worklist.push_back(equivalent->AsPhi()); 38515693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil } 38615693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil } 38718b36abc7cc03076fe1c399c0bb8ec8793cc6806Aart Bik // Refine the side effects of this floating point aset. Note that we do this even if 38818b36abc7cc03076fe1c399c0bb8ec8793cc6806Aart Bik // no replacement occurs, since the right-hand-side may have been corrected already. 38918b36abc7cc03076fe1c399c0bb8ec8793cc6806Aart Bik aset->ComputeSideEffects(); 39015693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil } else { 39115693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // Array elements are integral and the value assigned to it initially 39215693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil // was integral too. Nothing to do. 39315693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil DCHECK(Primitive::IsIntegralType(array_type)); 39415693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil DCHECK(Primitive::IsIntegralType(value_type)); 39515693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil } 39615693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil } 39715693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil } 3984833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 3994833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (!worklist.empty()) { 4004833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil ProcessPrimitiveTypePropagationWorklist(&worklist); 4014833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil EquivalentPhisCleanup(); 4024833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 4034833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 4044833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return true; 4054833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 4064833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 40798e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffraystatic bool HasAliasInEnvironments(HInstruction* instruction) { 40846817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko HEnvironment* last_user = nullptr; 40946817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) { 41046817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko DCHECK(use.GetUser() != nullptr); 41146817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko // Note: The first comparison (== null) always fails. 41246817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko if (use.GetUser() == last_user) { 41398e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray return true; 41498e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray } 41546817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko last_user = use.GetUser(); 41698e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray } 41798e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray 41898e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray if (kIsDebugBuild) { 41998e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray // Do a quadratic search to ensure same environment uses are next 42098e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray // to each other. 42146817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses(); 42246817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko for (auto current = env_uses.begin(), end = env_uses.end(); current != end; ++current) { 42346817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko auto next = current; 42446817b876ab00d6b78905b80ed12b4344c522b6cVladimir Marko for (++next; next != end; ++next) { 42598e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray DCHECK(next->GetUser() != current->GetUser()); 42698e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray } 42798e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray } 42898e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray } 42998e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray return false; 43098e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray} 43198e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray 43265902e86b91f984061657bd8cacf239edb53c39dDavid Brazdilvoid SsaBuilder::RemoveRedundantUninitializedStrings() { 433dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil if (graph_->IsDebuggable()) { 43465902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil // Do not perform the optimization for consistency with the interpreter 43565902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil // which always allocates an object for new-instance of String. 43665902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil return; 43765902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil } 43865902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil 43965902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil for (HNewInstance* new_instance : uninitialized_strings_) { 440eda3140656dafa03dc7fd4b3f90246a8522f0c1bAart Bik DCHECK(new_instance->IsInBlock()); 441dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil DCHECK(new_instance->IsStringAlloc()); 442dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil 44365902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil // Replace NewInstance of String with NullConstant if not used prior to 44465902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil // calling StringFactory. In case of deoptimization, the interpreter is 44565902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil // expected to skip null check on the `this` argument of the StringFactory call. 44698e6ce44c700abd9375fe17f0aa31fea1e1e938bNicolas Geoffray if (!new_instance->HasNonEnvironmentUses() && !HasAliasInEnvironments(new_instance)) { 447dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil new_instance->ReplaceWith(graph_->GetNullConstant()); 44865902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil new_instance->GetBlock()->RemoveInstruction(new_instance); 44965902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil 45065902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil // Remove LoadClass if not needed any more. 4515e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray HInstruction* input = new_instance->InputAt(0); 4525e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray HLoadClass* load_class = nullptr; 4535e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray 4545e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray // If the class was not present in the dex cache at the point of building 4555e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray // the graph, the builder inserted a HClinitCheck in between. Since the String 4565e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray // class is always initialized at the point of running Java code, we can remove 4575e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray // that check. 4585e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray if (input->IsClinitCheck()) { 4595e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray load_class = input->InputAt(0)->AsLoadClass(); 4605e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray input->ReplaceWith(load_class); 4615e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray input->GetBlock()->RemoveInstruction(input); 4625e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray } else { 4635e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray load_class = input->AsLoadClass(); 4645e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray DCHECK(new_instance->IsStringAlloc()); 4655e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray DCHECK(!load_class->NeedsAccessCheck()) << "String class is always accessible"; 4665e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray } 46765902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil DCHECK(load_class != nullptr); 46865902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil if (!load_class->HasUses()) { 4695e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray // Even if the HLoadClass needs access check, we can remove it, as we know the 4705e08e3643230ff89f3d7e9b5d7660db6fd94bec9Nicolas Geoffray // String class does not need it. 47165902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil load_class->GetBlock()->RemoveInstruction(load_class); 47265902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil } 47365902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil } 47465902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil } 47565902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil} 47665902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil 47715bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas GeoffrayGraphAnalysisResult SsaBuilder::BuildSsa() { 478dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil DCHECK(!graph_->IsInSsaForm()); 479badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 480dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // 1) Propagate types of phis. At this point, phis are typed void in the general 4814833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // case, or float/double/reference if we created an equivalent phi. So we need 4824833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // to propagate the types across phis to give them a correct type. If a type 4834833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // conflict is detected in this stage, the phi is marked dead. 4844833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil RunPrimitiveTypePropagation(); 4854833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 486dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // 2) Now that the correct primitive types have been assigned, we can get rid 4874833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // of redundant phis. Note that we cannot do this phase before type propagation, 4884833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // otherwise we could get rid of phi equivalents, whose presence is a requirement 4894833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // for the type propagation phase. Note that this is to satisfy statement (a) 4904833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // of the SsaBuilder (see ssa_builder.h). 491dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil SsaRedundantPhiElimination(graph_).Run(); 4924833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 493dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // 3) Fix the type for null constants which are part of an equality comparison. 4944833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // We need to do this after redundant phi elimination, to ensure the only cases 4954833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // that we can see are reference comparison against 0. The redundant phi 4964833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // elimination ensures we do not see a phi taking two 0 constants in a HEqual 4974833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // or HNotEqual. 4984833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil FixNullConstantType(); 4994833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 500dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // 4) Compute type of reference type instructions. The pass assumes that 5014833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // NullConstant has been fixed up. 5028d6768d47b66a688d35399d524ad5a5450e9d9d4Vladimir Marko ReferenceTypePropagation(graph_, 5038d6768d47b66a688d35399d524ad5a5450e9d9d4Vladimir Marko class_loader_, 5048d6768d47b66a688d35399d524ad5a5450e9d9d4Vladimir Marko dex_cache_, 5058d6768d47b66a688d35399d524ad5a5450e9d9d4Vladimir Marko handles_, 5068d6768d47b66a688d35399d524ad5a5450e9d9d4Vladimir Marko /* is_first_run */ true).Run(); 5074833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 508dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // 5) HInstructionBuilder duplicated ArrayGet instructions with ambiguous type 509dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // (int/float or long/double) and marked ArraySets with ambiguous input type. 510dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // Now that RTP computed the type of the array input, the ambiguity can be 511dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // resolved and the correct equivalents kept. 51215693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil if (!FixAmbiguousArrayOps()) { 51315bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray return kAnalysisFailAmbiguousArrayOp; 5144833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 5154833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 516dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // 6) Mark dead phis. This will mark phis which are not used by instructions 5174833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // or other live phis. If compiling as debuggable code, phis will also be kept 5184833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // live if they have an environment use. 519dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil SsaDeadPhiElimination dead_phi_elimimation(graph_); 5204833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil dead_phi_elimimation.MarkDeadPhis(); 5214833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 522dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // 7) Make sure environments use the right phi equivalent: a phi marked dead 5234833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // can have a phi equivalent that is not dead. In that case we have to replace 5244833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // it with the live equivalent because deoptimization and try/catch rely on 5254833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // environments containing values of all live vregs at that point. Note that 5264833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // there can be multiple phis for the same Dex register that are live 5274833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // (for example when merging constants), in which case it is okay for the 5284833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // environments to just reference one. 5294833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil FixEnvironmentPhis(); 5304833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 531dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // 8) Now that the right phis are used for the environments, we can eliminate 5324833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // phis we do not need. Regardless of the debuggable status, this phase is 5334833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil /// necessary for statement (b) of the SsaBuilder (see ssa_builder.h), as well 5344833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // as for the code generation, which does not deal with phis of conflicting 5352bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil // input types. 5364833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil dead_phi_elimimation.EliminateDeadPhis(); 5372bd4c5c1b704be8a81d9b7a94b3e828afa2b0963David Brazdil 538dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // 9) HInstructionBuidler replaced uses of NewInstances of String with the 539dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // results of their corresponding StringFactory calls. Unless the String 540dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // objects are used before they are initialized, they can be replaced with 541dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // NullConstant. Note that this optimization is valid only if unsimplified 542dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // code does not use the uninitialized value because we assume execution can 543dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // be deoptimized at any safepoint. We must therefore perform it before any 544dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil // other optimizations. 54565902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil RemoveRedundantUninitializedStrings(); 54665902e86b91f984061657bd8cacf239edb53c39dDavid Brazdil 547dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil graph_->SetInSsaForm(); 54815bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray return kAnalysisSuccess; 549c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} 550c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray 551102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray/** 552102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * Constants in the Dex format are not typed. So the builder types them as 553102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * integers, but when doing the SSA form, we might realize the constant 554102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * is used for floating point operations. We create a floating-point equivalent 555102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * constant to make the operations correctly typed. 556102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray */ 5578d5b8b295930aaa43255c4f0b74ece3ee8b43a47David BrazdilHFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) { 558102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // We place the floating point constant next to this constant. 559102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HFloatConstant* result = constant->GetNext()->AsFloatConstant(); 560102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (result == nullptr) { 561dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil float value = bit_cast<float, int32_t>(constant->GetValue()); 562dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil result = new (graph_->GetArena()) HFloatConstant(value); 563102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 564dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil graph_->CacheFloatConstant(result); 565102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 566102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // If there is already a constant with the expected type, we know it is 567102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // the floating point equivalent of this constant. 568da4d79bc9a4aeb9da7c6259ce4c9c1c3bf545eb8Roland Levillain DCHECK_EQ((bit_cast<int32_t, float>(result->GetValue())), constant->GetValue()); 569102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 570102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return result; 571102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray} 572102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 573102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray/** 574102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * Wide constants in the Dex format are not typed. So the builder types them as 575102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * longs, but when doing the SSA form, we might realize the constant 576102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * is used for floating point operations. We create a floating-point equivalent 577102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * constant to make the operations correctly typed. 578102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray */ 5798d5b8b295930aaa43255c4f0b74ece3ee8b43a47David BrazdilHDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { 580102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // We place the floating point constant next to this constant. 581102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HDoubleConstant* result = constant->GetNext()->AsDoubleConstant(); 582102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (result == nullptr) { 583dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil double value = bit_cast<double, int64_t>(constant->GetValue()); 584dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil result = new (graph_->GetArena()) HDoubleConstant(value); 585102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); 586dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil graph_->CacheDoubleConstant(result); 587102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 588102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // If there is already a constant with the expected type, we know it is 589102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray // the floating point equivalent of this constant. 590da4d79bc9a4aeb9da7c6259ce4c9c1c3bf545eb8Roland Levillain DCHECK_EQ((bit_cast<int64_t, double>(result->GetValue())), constant->GetValue()); 591102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 592102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return result; 593102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray} 594102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 595102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray/** 596102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * Because of Dex format, we might end up having the same phi being 597d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray * used for non floating point operations and floating point / reference operations. 598d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray * Because we want the graph to be correctly typed (and thereafter avoid moves between 599102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray * floating point registers and core registers), we need to create a copy of the 600d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray * phi with a floating point / reference type. 601102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray */ 6028d5b8b295930aaa43255c4f0b74ece3ee8b43a47David BrazdilHPhi* SsaBuilder::GetFloatDoubleOrReferenceEquivalentOfPhi(HPhi* phi, Primitive::Type type) { 6034833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(phi->IsLive()) << "Cannot get equivalent of a dead phi since it would create a live one."; 6044833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 605d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray // We place the floating point /reference phi next to this phi. 606102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray HInstruction* next = phi->GetNext(); 607d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (next != nullptr 608d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray && next->AsPhi()->GetRegNumber() == phi->GetRegNumber() 609d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray && next->GetType() != type) { 610d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray // Move to the next phi to see if it is the one we are looking for. 611d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray next = next->GetNext(); 612d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 613d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray 614d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray if (next == nullptr 615d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray || (next->AsPhi()->GetRegNumber() != phi->GetRegNumber()) 616d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray || (next->GetType() != type)) { 617dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil ArenaAllocator* allocator = graph_->GetArena(); 618e90049140fdfb89080e5cc9b000b0c9be8c18bcdVladimir Marko HInputsRef inputs = phi->GetInputs(); 619372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko HPhi* new_phi = 620372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko new (allocator) HPhi(allocator, phi->GetRegNumber(), inputs.size(), type); 621372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko // Copy the inputs. Note that the graph may not be correctly typed 622372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko // by doing this copy, but the type propagation phase will fix it. 623372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko ArrayRef<HUserRecord<HInstruction*>> new_input_records = new_phi->GetInputRecords(); 624372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko for (size_t i = 0; i < inputs.size(); ++i) { 625372f10e5b0b34e2bb6e2b79aeba6c441e14afd1fVladimir Marko new_input_records[i] = HUserRecord<HInstruction*>(inputs[i]); 626102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 627102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray phi->GetBlock()->InsertPhiAfter(new_phi, phi); 6284833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(new_phi->IsLive()); 629102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return new_phi; 630102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 6314833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // An existing equivalent was found. If it is dead, conflict was previously 6324833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // identified and we return nullptr instead. 633809d70f5b268227dbd59432dc038c74d8351be29David Brazdil HPhi* next_phi = next->AsPhi(); 634809d70f5b268227dbd59432dc038c74d8351be29David Brazdil DCHECK_EQ(next_phi->GetType(), type); 6354833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return next_phi->IsLive() ? next_phi : nullptr; 6364833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 6374833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil} 6384833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 6394833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilHArrayGet* SsaBuilder::GetFloatOrDoubleEquivalentOfArrayGet(HArrayGet* aget) { 6404833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(Primitive::IsIntegralType(aget->GetType())); 6414833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 6424833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (!Primitive::IsIntOrLongType(aget->GetType())) { 6434833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // Cannot type boolean, char, byte, short to float/double. 6444833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return nullptr; 6454833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } 6464833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 6474833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil DCHECK(ContainsElement(ambiguous_agets_, aget)); 6484833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (agets_fixed_) { 6494833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // This used to be an ambiguous ArrayGet but its type has been resolved to 6504833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // int/long. Requesting a float/double equivalent should lead to a conflict. 6514833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil if (kIsDebugBuild) { 6524833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil ScopedObjectAccess soa(Thread::Current()); 65315693bfdf9fa3ec79327a77b7e10315614d716ccDavid Brazdil DCHECK(Primitive::IsIntOrLongType(GetPrimitiveArrayComponentType(aget->GetArray()))); 654809d70f5b268227dbd59432dc038c74d8351be29David Brazdil } 6554833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return nullptr; 6564833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil } else { 6574833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // This is an ambiguous ArrayGet which has not been resolved yet. Return an 6584833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil // equivalent float/double instruction to use until it is resolved. 6594833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil HArrayGet* equivalent = FindFloatOrDoubleEquivalentOfArrayGet(aget); 6604833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return (equivalent == nullptr) ? CreateFloatOrDoubleEquivalentOfArrayGet(aget) : equivalent; 661102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 662102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray} 663102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 6644833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilHInstruction* SsaBuilder::GetFloatOrDoubleEquivalent(HInstruction* value, Primitive::Type type) { 665102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (value->IsArrayGet()) { 6664833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return GetFloatOrDoubleEquivalentOfArrayGet(value->AsArrayGet()); 667102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else if (value->IsLongConstant()) { 668102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return GetDoubleEquivalent(value->AsLongConstant()); 669102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else if (value->IsIntConstant()) { 670102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return GetFloatEquivalent(value->AsIntConstant()); 671102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else if (value->IsPhi()) { 672d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), type); 673102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 6744833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil return nullptr; 675102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 676102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray} 677102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 678d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas GeoffrayHInstruction* SsaBuilder::GetReferenceTypeEquivalent(HInstruction* value) { 679e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray if (value->IsIntConstant() && value->AsIntConstant()->GetValue() == 0) { 680dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil return graph_->GetNullConstant(); 681e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else if (value->IsPhi()) { 682d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray return GetFloatDoubleOrReferenceEquivalentOfPhi(value->AsPhi(), Primitive::kPrimNot); 683e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray } else { 684e0fe7ae36180863e45cbb9d1e6e9c30b1b1a949cNicolas Geoffray return nullptr; 685d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray } 686d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray} 687d6138ef1ea13d07ae555542f8898b30d89e9ac9aNicolas Geoffray 688c32e770f21540e4e9eda6dc7f770e745d33f1b9fNicolas Geoffray} // namespace art 689