1 /** 2 * Copyright (c) 2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef LIBABCKIT_SRC_IR_BUILDER_DYNAMIC_PHI_RESOLVER_H 17 #define LIBABCKIT_SRC_IR_BUILDER_DYNAMIC_PHI_RESOLVER_H 18 19 #include "libabckit/src/irbuilder_dynamic/inst_builder_dyn.h" 20 21 namespace libabckit { 22 /** 23 * Resolve phi instructions in the given graph. Resolving phi is: 24 * - remove phi if it has only SafePoint in users 25 * - if phi has no type, then set type determined from its inputs 26 */ 27 class PhiResolver { 28 public: PhiResolver(ark::compiler::Graph * graph)29 explicit PhiResolver(ark::compiler::Graph *graph) 30 : graph_(graph), 31 realInputs_(graph->GetLocalAllocator()->Adapter()), 32 phiUsers_(graph->GetLocalAllocator()->Adapter()), 33 realUsers_(graph->GetLocalAllocator()->Adapter()) 34 { 35 } 36 37 NO_MOVE_SEMANTIC(PhiResolver); 38 NO_COPY_SEMANTIC(PhiResolver); 39 ~PhiResolver() = default; 40 Run()41 void Run() 42 { 43 for (auto bb : graph_->GetBlocksRPO()) { 44 for (auto inst : bb->AllInstsSafe()) { 45 if (!inst->IsPhi() && inst->GetOpcode() != ark::compiler::Opcode::CatchPhi) { 46 continue; 47 } 48 if (inst->HasType() || (!inst->GetUsers().Empty() && CheckPhiInputs(inst))) { 49 continue; 50 } 51 CleanUp(); 52 inst->SetMarker(marker_); 53 FindUsersRec(inst); 54 if (hasSaveStateInstOnly_) { 55 RemovePhi(inst); 56 } else { 57 SetTypeByInputs(inst); 58 ASSERT(inst->HasType() || (inst->IsCatchPhi() && !inst->CastToCatchPhi()->IsAcc())); 59 } 60 graph_->EraseMarker(marker_); 61 } 62 } 63 } 64 65 private: RemovePhi(ark::compiler::Inst * inst)66 void RemovePhi(ark::compiler::Inst *inst) 67 { 68 // Remove virtual registers of SafePoint instructions which input phis to be removed. 69 for (auto user : realUsers_) { 70 ASSERT(user->IsSaveState()); 71 auto saveState = static_cast<ark::compiler::SaveStateInst *>(user); 72 size_t idx = 0; 73 size_t inputsCount = saveState->GetInputsCount(); 74 while (idx < inputsCount) { 75 auto inputInst = saveState->GetInput(idx).GetInst(); 76 if (inputInst->IsMarked(marker_)) { 77 saveState->RemoveInput(idx); 78 inputsCount--; 79 } else { 80 idx++; 81 } 82 } 83 } 84 // Phi has only SafePoint in users, we can remove this phi and all phi in collected list. 85 inst->RemoveUsers<true>(); 86 inst->GetBasicBlock()->RemoveInst(inst); 87 for (auto phi : phiUsers_) { 88 phi->RemoveUsers<true>(); 89 phi->GetBasicBlock()->RemoveInst(phi); 90 } 91 } 92 CleanUp()93 void CleanUp() 94 { 95 phiUsers_.clear(); 96 realUsers_.clear(); 97 hasSaveStateInstOnly_ = true; 98 marker_ = graph_->NewMarker(); 99 } SetTypeByInputs(ark::compiler::Inst * inst)100 static void SetTypeByInputs(ark::compiler::Inst *inst) 101 { 102 if (inst->IsCatchPhi() && inst->CastToCatchPhi()->IsAcc()) { 103 inst->SetType(ark::compiler::DataType::REFERENCE); 104 return; 105 } 106 for (auto input : inst->GetInputs()) { 107 auto inputType = input.GetInst()->GetType(); 108 if (inputType != ark::compiler::DataType::NO_TYPE) { 109 inst->SetType(inputType); 110 break; 111 } 112 } 113 } FindUsersRec(ark::compiler::Inst * inst)114 void FindUsersRec(ark::compiler::Inst *inst) 115 { 116 for (auto &user : inst->GetUsers()) { 117 if (user.GetInst()->SetMarker(marker_)) { 118 continue; 119 } 120 if (user.GetInst()->IsPhi() || user.GetInst()->GetOpcode() == ark::compiler::Opcode::CatchPhi) { 121 phiUsers_.push_back(user.GetInst()); 122 FindUsersRec(user.GetInst()); 123 } else { 124 if (!user.GetInst()->IsSaveState()) { 125 hasSaveStateInstOnly_ = false; 126 break; 127 } 128 realUsers_.push_back(user.GetInst()); 129 } 130 } 131 } 132 FindInputsRec(ark::compiler::Inst * inst)133 void FindInputsRec(ark::compiler::Inst *inst) 134 { 135 ASSERT(inst->IsPhi() || inst->GetOpcode() == ark::compiler::Opcode::CatchPhi); 136 // We can't set real type if there aren't inputs from Phi/CathPhi 137 // We add the Phi/CathPhi in the list and return false from CheckPhiInputs 138 if (inst->GetInputs().Empty()) { 139 realInputs_.push_back(inst); 140 return; 141 } 142 for (auto &input : inst->GetInputs()) { 143 auto inputInst = input.GetInst(); 144 if (inputInst->SetMarker(marker_)) { 145 continue; 146 } 147 if (inputInst->IsPhi() || inputInst->GetOpcode() == ark::compiler::Opcode::CatchPhi) { 148 if (inputInst->GetType() != ark::compiler::DataType::NO_TYPE) { 149 realInputs_.push_back(inputInst); 150 continue; 151 } 152 FindInputsRec(inputInst); 153 } else { 154 realInputs_.push_back(inputInst); 155 } 156 } 157 } 158 CheckPhiRealInputs(ark::compiler::InstVector & realInputs,ark::compiler::DataType::Type * type,bool * hasConstantInput)159 static bool CheckPhiRealInputs(ark::compiler::InstVector &realInputs, ark::compiler::DataType::Type *type, 160 bool *hasConstantInput) 161 { 162 for (auto inputInst : realInputs) { 163 auto inputType = inputInst->GetType(); 164 if (inputType == ark::compiler::DataType::NO_TYPE) { 165 return false; 166 } 167 if (inputInst->IsConst() && inputType == ark::compiler::DataType::INT64) { 168 if (*type != ark::compiler::DataType::NO_TYPE && 169 ark::compiler::DataType::GetCommonType(*type) != ark::compiler::DataType::INT64) { 170 return false; 171 } 172 *hasConstantInput = true; 173 continue; 174 } 175 if (*type == ark::compiler::DataType::NO_TYPE) { 176 if (*hasConstantInput && 177 ark::compiler::DataType::GetCommonType(inputType) != ark::compiler::DataType::INT64) { 178 return false; 179 } 180 *type = inputType; 181 } else if (*type != inputType) { 182 return false; 183 } 184 } 185 return true; 186 } 187 188 // Returns false if block with input instruction doesn't dominate the predecessor of the PHI block CheckPhiInputs(ark::compiler::Inst * phiInst)189 bool CheckPhiInputs(ark::compiler::Inst *phiInst) 190 { 191 ASSERT(phiInst->GetOpcode() == ark::compiler::Opcode::Phi || 192 phiInst->GetOpcode() == ark::compiler::Opcode::CatchPhi); 193 if (phiInst->GetOpcode() == ark::compiler::Opcode::Phi) { 194 if (phiInst->GetInputsCount() != phiInst->GetBasicBlock()->GetPredsBlocks().size()) { 195 return false; 196 } 197 for (size_t index = 0; index < phiInst->GetInputsCount(); ++index) { 198 auto pred = phiInst->GetBasicBlock()->GetPredBlockByIndex(index); 199 auto inputBb = phiInst->GetInput(index).GetInst()->GetBasicBlock(); 200 if (!inputBb->IsDominate(pred)) { 201 return false; 202 } 203 } 204 } 205 ark::compiler::DataType::Type type = ark::compiler::DataType::NO_TYPE; 206 realInputs_.clear(); 207 marker_ = graph_->NewMarker(); 208 phiInst->SetMarker(marker_); 209 FindInputsRec(phiInst); 210 graph_->EraseMarker(marker_); 211 212 bool hasConstantInput = false; 213 if (!CheckPhiRealInputs(realInputs_, &type, &hasConstantInput)) { 214 return false; 215 } 216 if (type == ark::compiler::DataType::NO_TYPE) { 217 // Do not remove phi with constants-only inputs. 218 if (!hasConstantInput) { 219 return false; 220 } 221 type = ark::compiler::DataType::INT64; 222 } 223 phiInst->SetType(type); 224 return true; 225 } 226 227 private: 228 ark::compiler::Graph *graph_ {nullptr}; 229 ark::compiler::InstVector realInputs_; 230 ark::compiler::InstVector phiUsers_; 231 ark::compiler::InstVector realUsers_; 232 ark::compiler::Marker marker_ {ark::compiler::UNDEF_MARKER}; 233 bool hasSaveStateInstOnly_ {true}; 234 }; 235 236 } // namespace libabckit 237 238 #endif // LIBABCKIT_SRC_IR_BUILDER_DYNAMIC_PHI_RESOLVER_H 239