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