1 /* 2 * Copyright (c) 2021-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 COMPILER_OPTIMIZER_OPTIMIZATIONS_CLEANUP_H 17 #define COMPILER_OPTIMIZER_OPTIMIZATIONS_CLEANUP_H 18 19 #include "optimizer/ir/graph.h" 20 #include "optimizer/pass.h" 21 22 namespace ark::compiler { 23 class PANDA_PUBLIC_API Cleanup final : public Optimization { 24 public: 25 explicit Cleanup(Graph *graph, bool lightMode = true) Optimization(graph)26 : Optimization(graph), 27 empty1_(graph->GetLocalAllocator()->Adapter()), 28 empty2_(graph->GetLocalAllocator()->Adapter()), 29 savedPreds_(graph->GetLocalAllocator()->Adapter()), 30 dead_(graph->GetLocalAllocator()->Adapter()), 31 temp_(graph->GetLocalAllocator()->Adapter()), 32 ancestors_(graph->GetLocalAllocator()->Adapter()), 33 buckets_(graph->GetLocalAllocator()->Adapter()), 34 idoms_(graph->GetLocalAllocator()->Adapter()), 35 labels_(graph->GetLocalAllocator()->Adapter()), 36 parents_(graph->GetLocalAllocator()->Adapter()), 37 semi_(graph->GetLocalAllocator()->Adapter()), 38 vertices_(graph->GetLocalAllocator()->Adapter()), 39 map_(graph->GetLocalAllocator()->Adapter()), 40 lightMode_(lightMode) 41 { 42 } 43 44 NO_MOVE_SEMANTIC(Cleanup); 45 NO_COPY_SEMANTIC(Cleanup); 46 ~Cleanup() override = default; 47 48 bool RunImpl() override; 49 GetPassName()50 const char *GetPassName() const override 51 { 52 return "Cleanup"; 53 } 54 55 void InvalidateAnalyses() override; 56 static bool SkipBasicBlock(BasicBlock *bb); 57 58 private: 59 bool CanBeMerged(BasicBlock *bb); 60 61 bool RunOnce(ArenaSet<BasicBlock *> *emptyBlocks, ArenaSet<BasicBlock *> *newEmptyBlocks, bool simpleDce); 62 void RemoveDeadPhi(BasicBlock *bb, ArenaSet<BasicBlock *> *newEmptyBlocks); 63 bool ProcessBB(BasicBlock *bb, Marker deadMrk, ArenaSet<BasicBlock *> *newEmptyBlocks); 64 bool CheckSpecialTriangle(BasicBlock *bb); 65 66 void MarkInlinedCaller(Marker liveMrk, Inst *saveState); 67 bool IsRemovableCall(Inst *inst); 68 template <bool LIGHT_MODE> 69 void MarkLiveRec(Marker liveMrk, Inst *inst); 70 template <bool LIGHT_MODE> 71 void MarkLiveInstructions(Marker deadMrk, Marker liveMrk); 72 template <bool LIGHT_MODE> 73 void MarkOneLiveInst(Marker deadMrk, Marker liveMrk, Inst *inst); 74 template <bool LIGHT_MODE> 75 bool Dce(Marker deadMrk, ArenaSet<BasicBlock *> *newEmptyBlocks); 76 template <bool LIGHT_MODE> 77 bool TryToRemoveNonLiveInst(Inst *inst, BasicBlock *bb, ArenaSet<BasicBlock *> *newEmptyBlocks, Marker liveMrk); 78 79 void SetLiveRec(Inst *inst, Marker mrk, Marker liveMrk); 80 void LiveUserSearchRec(Inst *inst, Marker mrk, Marker liveMrk, Marker deadMrk); 81 bool SimpleDce(Marker deadMrk, ArenaSet<BasicBlock *> *newEmptyBlocks); 82 void Marking(Marker deadMrk, Marker mrk, Marker liveMrk); 83 void TryMarkInstIsDead(Inst *inst, Marker deadMrk, Marker mrk, Marker liveMrk); 84 85 bool Removal(ArenaSet<BasicBlock *> *newEmptyBlocks); 86 void RemovalPhi(BasicBlock *bb, ArenaSet<BasicBlock *> *newEmptyBlocks); 87 88 bool PhiChecker(); 89 bool PhiCheckerLight() const; 90 void BuildDominators(); 91 void BuildDominatorsVisitPhi(Inst *inst, size_t &amount); 92 93 ArenaSet<BasicBlock *> empty1_; 94 ArenaSet<BasicBlock *> empty2_; 95 ArenaVector<BasicBlock *> savedPreds_; 96 InstVector dead_; 97 InstVector temp_; 98 99 InstVector ancestors_; 100 ArenaVector<InstVector> buckets_; 101 InstVector idoms_; 102 InstVector labels_; 103 InstVector parents_; 104 ArenaVector<int32_t> semi_; 105 InstVector vertices_; 106 ArenaUnorderedMap<Inst *, uint32_t> map_; 107 108 Inst *fakeRoot_ {nullptr}; 109 static constexpr int32_t DEFAULT_DFS_VAL = 0; 110 // number of the inst according to the order it is reached during the DFS 111 int32_t dfsNum_ {DEFAULT_DFS_VAL}; 112 113 bool lightMode_ {true}; 114 GetInstId(Inst * inst)115 inline uint32_t GetInstId(Inst *inst) const 116 { 117 ASSERT(map_.count(inst) > 0); 118 return map_.at(inst); 119 } 120 121 /* 122 * The immediate dominator of 'inst' 123 */ SetIdom(Inst * inst,Inst * idom)124 void SetIdom(Inst *inst, Inst *idom) 125 { 126 idoms_[GetInstId(inst)] = idom; 127 } GetIdom(Inst * inst)128 Inst *GetIdom(Inst *inst) const 129 { 130 return idoms_[GetInstId(inst)]; 131 } 132 133 /* 134 * The ancestor of 'inst', fake_root_ for non-phi 135 */ SetAncestor(Inst * inst,Inst * anc)136 void SetAncestor(Inst *inst, Inst *anc) 137 { 138 ancestors_[GetInstId(inst)] = anc; 139 } GetAncestor(Inst * inst)140 Inst *GetAncestor(Inst *inst) const 141 { 142 return ancestors_[GetInstId(inst)]; 143 } 144 145 /* 146 * A set of instructions whose semidominator is 'inst' 147 */ GetBucket(Inst * inst)148 InstVector &GetBucket(Inst *inst) 149 { 150 return buckets_[GetInstId(inst)]; 151 } 152 153 /* 154 * The inst in the ancestors chain with the minimal semidominator DFS-number for 'inst' 155 */ SetLabel(Inst * inst,Inst * label)156 void SetLabel(Inst *inst, Inst *label) 157 { 158 labels_[GetInstId(inst)] = label; 159 } GetLabel(Inst * inst)160 Inst *GetLabel(Inst *inst) const 161 { 162 return labels_[GetInstId(inst)]; 163 } 164 165 /* 166 * The parent of 'inst' in the spanning tree generated by DFS 167 */ SetParent(Inst * inst,Inst * parent)168 void SetParent(Inst *inst, Inst *parent) 169 { 170 parents_[GetInstId(inst)] = parent; 171 } GetParent(Inst * inst)172 Inst *GetParent(Inst *inst) const 173 { 174 return parents_[GetInstId(inst)]; 175 } 176 177 /* 178 * The DFS-number of the semidominator of 'inst' 179 */ SetSemi(Inst * inst,int32_t value)180 void SetSemi(Inst *inst, int32_t value) 181 { 182 semi_[GetInstId(inst)] = value; 183 } GetSemi(Inst * inst)184 int32_t GetSemi(Inst *inst) const 185 { 186 return semi_[GetInstId(inst)]; 187 } 188 189 /* 190 * The inst whose DFS-number is 'index' 191 */ SetVertex(size_t index,Inst * inst)192 void SetVertex(size_t index, Inst *inst) 193 { 194 vertices_[index] = inst; 195 } GetVertex(size_t index)196 Inst *GetVertex(size_t index) const 197 { 198 return vertices_[index]; 199 } 200 201 void AdjustImmediateDominators(Inst *inst); 202 void ComputeImmediateDominators(Inst *inst); 203 void Compress(Inst *inst); 204 void DfsNumbering(Inst *inst); 205 Inst *Eval(Inst *inst); 206 void Init(size_t count); 207 #ifndef NDEBUG 208 void CheckBBPhisUsers(BasicBlock *succ, BasicBlock *bb); 209 #endif 210 }; 211 } // namespace ark::compiler 212 213 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_CLEANUP_H 214