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