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_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 panda::compiler { 23 class Cleanup final : public Optimization { 24 public: Cleanup(Graph * graph)25 explicit Cleanup(Graph *graph) 26 : Optimization(graph), 27 empty1_(graph->GetLocalAllocator()->Adapter()), 28 empty2_(graph->GetLocalAllocator()->Adapter()), 29 saved_preds_(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 { 41 } 42 43 NO_MOVE_SEMANTIC(Cleanup); 44 NO_COPY_SEMANTIC(Cleanup); 45 ~Cleanup() override = default; 46 47 bool RunImpl() override; 48 GetPassName()49 const char *GetPassName() const override 50 { 51 return "Cleanup"; 52 } 53 54 void InvalidateAnalyses() override; 55 56 private: 57 bool RunOnce(ArenaSet<BasicBlock *> *empty_blocks, ArenaSet<BasicBlock *> *new_empty_blocks, bool simple_dce); 58 void RemoveDeadPhi(BasicBlock *bb, ArenaSet<BasicBlock *> *new_empty_blocks); 59 bool ProcessBB(BasicBlock *bb, Marker dead_mrk, ArenaSet<BasicBlock *> *new_empty_blocks); 60 bool CheckSpecialTriangle(BasicBlock *bb); 61 62 void MarkLiveRec(Marker live_mrk, Inst *inst); 63 bool Dce(Marker dead_mrk, ArenaSet<BasicBlock *> *new_empty_blocks); 64 65 void SetLiveRec(Inst *inst, Marker mrk, Marker live_mrk); 66 void LiveUserSearchRec(Inst *inst, Marker mrk, Marker live_mrk, Marker dead_mrk); 67 bool SimpleDce(Marker dead_mrk, ArenaSet<BasicBlock *> *new_empty_blocks); 68 void Marking(Marker dead_mrk, Marker mrk, Marker live_mrk); 69 bool Removal(ArenaSet<BasicBlock *> *new_empty_blocks); 70 71 bool PhiChecker(); 72 void BuildDominators(); 73 74 ArenaSet<BasicBlock *> empty1_; 75 ArenaSet<BasicBlock *> empty2_; 76 ArenaVector<BasicBlock *> saved_preds_; 77 InstVector dead_; 78 InstVector temp_; 79 80 InstVector ancestors_; 81 ArenaVector<InstVector> buckets_; 82 InstVector idoms_; 83 InstVector labels_; 84 InstVector parents_; 85 ArenaVector<int32_t> semi_; 86 InstVector vertices_; 87 ArenaUnorderedMap<Inst *, uint32_t> map_; 88 89 Inst *fake_root_ {nullptr}; 90 static constexpr int32_t DEFAULT_DFS_VAL = 0; 91 // number of the inst according to the order it is reached during the DFS 92 int32_t dfs_num_ {DEFAULT_DFS_VAL}; 93 GetInstId(Inst * inst)94 inline uint32_t GetInstId(Inst *inst) const 95 { 96 ASSERT(map_.count(inst) > 0); 97 return map_.at(inst); 98 } 99 100 /* 101 * The immediate dominator of 'inst' 102 */ SetIdom(Inst * inst,Inst * idom)103 void SetIdom(Inst *inst, Inst *idom) 104 { 105 idoms_[GetInstId(inst)] = idom; 106 } GetIdom(Inst * inst)107 Inst *GetIdom(Inst *inst) const 108 { 109 return idoms_[GetInstId(inst)]; 110 } 111 112 /* 113 * The ancestor of 'inst', fake_root_ for non-phi 114 */ SetAncestor(Inst * inst,Inst * anc)115 void SetAncestor(Inst *inst, Inst *anc) 116 { 117 ancestors_[GetInstId(inst)] = anc; 118 } GetAncestor(Inst * inst)119 Inst *GetAncestor(Inst *inst) const 120 { 121 return ancestors_[GetInstId(inst)]; 122 } 123 124 /* 125 * A set of instructions whose semidominator is 'inst' 126 */ GetBucket(Inst * inst)127 InstVector &GetBucket(Inst *inst) 128 { 129 return buckets_[GetInstId(inst)]; 130 } 131 132 /* 133 * The inst in the ancestors chain with the minimal semidominator DFS-number for 'inst' 134 */ SetLabel(Inst * inst,Inst * label)135 void SetLabel(Inst *inst, Inst *label) 136 { 137 labels_[GetInstId(inst)] = label; 138 } GetLabel(Inst * inst)139 Inst *GetLabel(Inst *inst) const 140 { 141 return labels_[GetInstId(inst)]; 142 } 143 144 /* 145 * The parent of 'inst' in the spanning tree generated by DFS 146 */ SetParent(Inst * inst,Inst * parent)147 void SetParent(Inst *inst, Inst *parent) 148 { 149 parents_[GetInstId(inst)] = parent; 150 } GetParent(Inst * inst)151 Inst *GetParent(Inst *inst) const 152 { 153 return parents_[GetInstId(inst)]; 154 } 155 156 /* 157 * The DFS-number of the semidominator of 'inst' 158 */ SetSemi(Inst * inst,int32_t value)159 void SetSemi(Inst *inst, int32_t value) 160 { 161 semi_[GetInstId(inst)] = value; 162 } GetSemi(Inst * inst)163 int32_t GetSemi(Inst *inst) const 164 { 165 return semi_[GetInstId(inst)]; 166 } 167 168 /* 169 * The inst whose DFS-number is 'index' 170 */ SetVertex(size_t index,Inst * inst)171 void SetVertex(size_t index, Inst *inst) 172 { 173 vertices_[index] = inst; 174 } GetVertex(size_t index)175 Inst *GetVertex(size_t index) const 176 { 177 return vertices_[index]; 178 } 179 180 void AdjustImmediateDominators(Inst *inst); 181 void ComputeImmediateDominators(Inst *inst); 182 void Compress(Inst *inst); 183 void DfsNumbering(Inst *inst); 184 Inst *Eval(Inst *inst); 185 void Init(size_t count); 186 }; 187 } // namespace panda::compiler 188 189 #endif // COMPILER_OPTIMIZER_OPTIMIZATIONS_CLEANUP_H 190