1 /** 2 * Copyright (c) 2021-2022 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 #ifndef PHI_RESOLVER_H 16 #define PHI_RESOLVER_H 17 18 #include "inst_builder.h" 19 #include "compiler_logger.h" 20 21 namespace panda::compiler { 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(Graph * graph)29 explicit PhiResolver(Graph *graph) 30 : graph_(graph), 31 real_inputs_(graph->GetLocalAllocator()->Adapter()), 32 phi_users_(graph->GetLocalAllocator()->Adapter()), 33 real_users_(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() != 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 (has_save_state_inst_only_) { 55 // Remove virtual registers of SafePoint instructions which input phis to be removed. 56 for (auto user : real_users_) { 57 ASSERT(user->IsSaveState()); 58 auto save_state = static_cast<SaveStateInst *>(user); 59 size_t idx = 0; 60 size_t inputs_count = save_state->GetInputsCount(); 61 while (idx < inputs_count) { 62 auto input_inst = save_state->GetInput(idx).GetInst(); 63 if (input_inst->IsMarked(marker_)) { 64 save_state->RemoveInput(idx); 65 inputs_count--; 66 } else { 67 idx++; 68 } 69 } 70 } 71 // Phi has only SafePoint in users, we can remove this phi and all phi in collected list. 72 inst->RemoveUsers<true>(); 73 inst->GetBasicBlock()->RemoveInst(inst); 74 for (auto phi : phi_users_) { 75 phi->RemoveUsers<true>(); 76 phi->GetBasicBlock()->RemoveInst(phi); 77 } 78 } else { 79 SetTypeByInputs(inst); 80 ASSERT(inst->HasType() || (inst->IsCatchPhi() && !inst->CastToCatchPhi()->IsAcc())); 81 } 82 graph_->EraseMarker(marker_); 83 } 84 } 85 } 86 87 private: CleanUp()88 void CleanUp() 89 { 90 phi_users_.clear(); 91 real_users_.clear(); 92 has_save_state_inst_only_ = true; 93 marker_ = graph_->NewMarker(); 94 } SetTypeByInputs(Inst * inst)95 static void SetTypeByInputs(Inst *inst) 96 { 97 if (inst->IsCatchPhi() && inst->CastToCatchPhi()->IsAcc()) { 98 inst->SetType(DataType::REFERENCE); 99 return; 100 } 101 for (auto input : inst->GetInputs()) { 102 auto input_type = input.GetInst()->GetType(); 103 if (input_type != DataType::NO_TYPE) { 104 inst->SetType(input_type); 105 break; 106 } 107 } 108 } FindUsersRec(Inst * inst)109 void FindUsersRec(Inst *inst) 110 { 111 for (auto &user : inst->GetUsers()) { 112 if (user.GetInst()->SetMarker(marker_)) { 113 continue; 114 } 115 if (user.GetInst()->IsPhi() || user.GetInst()->GetOpcode() == Opcode::CatchPhi) { 116 phi_users_.push_back(user.GetInst()); 117 FindUsersRec(user.GetInst()); 118 } else { 119 if (!user.GetInst()->IsSaveState()) { 120 has_save_state_inst_only_ = false; 121 break; 122 } 123 real_users_.push_back(user.GetInst()); 124 } 125 } 126 } 127 FindInputsRec(Inst * inst)128 void FindInputsRec(Inst *inst) 129 { 130 ASSERT(inst->IsPhi() || inst->GetOpcode() == Opcode::CatchPhi); 131 // We can't set real type if there aren't inputs from Phi/CathPhi 132 // We add the Phi/CathPhi in the list and return false from CheckPhiInputs 133 if (inst->GetInputs().Empty()) { 134 real_inputs_.push_back(inst); 135 return; 136 } 137 for (auto &input : inst->GetInputs()) { 138 auto input_inst = input.GetInst(); 139 if (input_inst->SetMarker(marker_)) { 140 continue; 141 } 142 if (input_inst->IsPhi() || input_inst->GetOpcode() == Opcode::CatchPhi) { 143 if (input_inst->GetType() != DataType::NO_TYPE) { 144 real_inputs_.push_back(input_inst); 145 continue; 146 } 147 FindInputsRec(input_inst); 148 } else { 149 real_inputs_.push_back(input_inst); 150 } 151 } 152 } 153 // Returns false if block with input instruction doesn't dominate the predecessor of the PHI block CheckPhiInputs(Inst * phi_inst)154 bool CheckPhiInputs(Inst *phi_inst) 155 { 156 ASSERT(phi_inst->GetOpcode() == Opcode::Phi || phi_inst->GetOpcode() == Opcode::CatchPhi); 157 if (phi_inst->GetOpcode() == Opcode::Phi) { 158 if (phi_inst->GetInputsCount() != phi_inst->GetBasicBlock()->GetPredsBlocks().size()) { 159 return false; 160 } 161 for (size_t index = 0; index < phi_inst->GetInputsCount(); ++index) { 162 auto pred = phi_inst->GetBasicBlock()->GetPredBlockByIndex(index); 163 auto input_bb = phi_inst->GetInput(index).GetInst()->GetBasicBlock(); 164 if (!input_bb->IsDominate(pred)) { 165 return false; 166 } 167 } 168 } 169 DataType::Type type = DataType::NO_TYPE; 170 real_inputs_.clear(); 171 marker_ = graph_->NewMarker(); 172 phi_inst->SetMarker(marker_); 173 FindInputsRec(phi_inst); 174 graph_->EraseMarker(marker_); 175 176 bool has_constant_input = false; 177 for (auto input_inst : real_inputs_) { 178 auto input_type = input_inst->GetType(); 179 if (input_type == DataType::NO_TYPE) { 180 return false; 181 } 182 if (input_inst->IsConst() && input_type == DataType::INT64) { 183 if (type != DataType::NO_TYPE && DataType::GetCommonType(type) != DataType::INT64) { 184 return false; 185 } 186 has_constant_input = true; 187 continue; 188 } 189 if (type == DataType::NO_TYPE) { 190 if (has_constant_input && DataType::GetCommonType(input_type) != DataType::INT64) { 191 return false; 192 } 193 type = input_type; 194 } else if (type != input_type) { 195 return false; 196 } 197 } 198 199 if (type == DataType::NO_TYPE) { 200 // Do not remove phi with constants-only inputs. 201 if (!has_constant_input) { 202 return false; 203 } 204 type = DataType::INT64; 205 } 206 phi_inst->SetType(type); 207 return true; 208 } 209 210 private: 211 Graph *graph_ {nullptr}; 212 InstVector real_inputs_; 213 InstVector phi_users_; 214 InstVector real_users_; 215 Marker marker_ {UNDEF_MARKER}; 216 bool has_save_state_inst_only_ {true}; 217 }; 218 } // namespace panda::compiler 219 220 #endif // PHI_RESOLVER_H 221