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
22namespace panda::compiler {
23class Cleanup final : public Optimization {
24public:
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
49    const char *GetPassName() const override
50    {
51        return "Cleanup";
52    }
53
54    void InvalidateAnalyses() override;
55
56private:
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
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     */
103    void SetIdom(Inst *inst, Inst *idom)
104    {
105        idoms_[GetInstId(inst)] = idom;
106    }
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     */
115    void SetAncestor(Inst *inst, Inst *anc)
116    {
117        ancestors_[GetInstId(inst)] = anc;
118    }
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     */
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     */
135    void SetLabel(Inst *inst, Inst *label)
136    {
137        labels_[GetInstId(inst)] = label;
138    }
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     */
147    void SetParent(Inst *inst, Inst *parent)
148    {
149        parents_[GetInstId(inst)] = parent;
150    }
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     */
159    void SetSemi(Inst *inst, int32_t value)
160    {
161        semi_[GetInstId(inst)] = value;
162    }
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     */
171    void SetVertex(size_t index, Inst *inst)
172    {
173        vertices_[index] = inst;
174    }
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