1// Copyright (c) 2017 The Khronos Group Inc.
2// Copyright (c) 2017 Valve Corporation
3// Copyright (c) 2017 LunarG Inc.
4//
5// Licensed under the Apache License, Version 2.0 (the "License");
6// you may not use this file except in compliance with the License.
7// You may obtain a copy of the License at
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the License is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// See the License for the specific language governing permissions and
15// limitations under the License.
16
17#ifndef SOURCE_OPT_AGGRESSIVE_DEAD_CODE_ELIM_PASS_H_
18#define SOURCE_OPT_AGGRESSIVE_DEAD_CODE_ELIM_PASS_H_
19
20#include <algorithm>
21#include <list>
22#include <map>
23#include <queue>
24#include <string>
25#include <unordered_map>
26#include <unordered_set>
27#include <utility>
28#include <vector>
29
30#include "source/opt/basic_block.h"
31#include "source/opt/def_use_manager.h"
32#include "source/opt/mem_pass.h"
33#include "source/opt/module.h"
34#include "source/util/bit_vector.h"
35
36namespace spvtools {
37namespace opt {
38
39// See optimizer.hpp for documentation.
40class AggressiveDCEPass : public MemPass {
41 using cbb_ptr = const BasicBlock*;
42
43 public:
44 using GetBlocksFunction =
45 std::function<std::vector<BasicBlock*>*(const BasicBlock*)>;
46
47 AggressiveDCEPass();
48 const char* name() const override { return "eliminate-dead-code-aggressive"; }
49 Status Process() override;
50
51 IRContext::Analysis GetPreservedAnalyses() override {
52 return IRContext::kAnalysisDefUse |
53 IRContext::kAnalysisInstrToBlockMapping |
54 IRContext::kAnalysisConstants | IRContext::kAnalysisTypes;
55 }
56
57 private:
58 // Return true if |varId| is a variable of |storageClass|. |varId| must either
59 // be 0 or the result of an instruction.
60 bool IsVarOfStorage(uint32_t varId, uint32_t storageClass);
61
62 // Return true if |varId| is variable of function storage class or is
63 // private variable and privates can be optimized like locals (see
64 // privates_like_local_).
65 bool IsLocalVar(uint32_t varId);
66
67 // Return true if |inst| is marked live.
68 bool IsLive(const Instruction* inst) const {
69 return live_insts_.Get(inst->unique_id());
70 }
71
72 // Returns true if |inst| is dead.
73 bool IsDead(Instruction* inst);
74
75 // Adds entry points, execution modes and workgroup size decorations to the
76 // worklist for processing with the first function.
77 void InitializeModuleScopeLiveInstructions();
78
79 // Add |inst| to worklist_ and live_insts_.
80 void AddToWorklist(Instruction* inst) {
81 if (!live_insts_.Set(inst->unique_id())) {
82 worklist_.push(inst);
83 }
84 }
85
86 // Add all store instruction which use |ptrId|, directly or indirectly,
87 // to the live instruction worklist.
88 void AddStores(uint32_t ptrId);
89
90 // Initialize extensions whitelist
91 void InitExtensions();
92
93 // Return true if all extensions in this module are supported by this pass.
94 bool AllExtensionsSupported() const;
95
96 // Returns true if the target of |inst| is dead. An instruction is dead if
97 // its result id is used in decoration or debug instructions only. |inst| is
98 // assumed to be OpName, OpMemberName or an annotation instruction.
99 bool IsTargetDead(Instruction* inst);
100
101 // If |varId| is local, mark all stores of varId as live.
102 void ProcessLoad(uint32_t varId);
103
104 // If |bp| is structured header block, returns true and sets |mergeInst| to
105 // the merge instruction, |branchInst| to the branch and |mergeBlockId| to the
106 // merge block if they are not nullptr. Any of |mergeInst|, |branchInst| or
107 // |mergeBlockId| may be a null pointer. Returns false if |bp| is a null
108 // pointer.
109 bool IsStructuredHeader(BasicBlock* bp, Instruction** mergeInst,
110 Instruction** branchInst, uint32_t* mergeBlockId);
111
112 // Initialize block2headerBranch_, header2nextHeaderBranch_, and
113 // branch2merge_ using |structuredOrder| to order blocks.
114 void ComputeBlock2HeaderMaps(std::list<BasicBlock*>& structuredOrder);
115
116 // Add branch to |labelId| to end of block |bp|.
117 void AddBranch(uint32_t labelId, BasicBlock* bp);
118
119 // Add all break and continue branches in the construct associated with
120 // |mergeInst| to worklist if not already live
121 void AddBreaksAndContinuesToWorklist(Instruction* mergeInst);
122
123 // Eliminates dead debug2 and annotation instructions. Marks dead globals for
124 // removal (e.g. types, constants and variables).
125 bool ProcessGlobalValues();
126
127 // Erases functions that are unreachable from the entry points of the module.
128 bool EliminateDeadFunctions();
129
130 // Removes |func| from the module and deletes all its instructions.
131 void EliminateFunction(Function* func);
132
133 // For function |func|, mark all Stores to non-function-scope variables
134 // and block terminating instructions as live. Recursively mark the values
135 // they use. When complete, mark any non-live instructions to be deleted.
136 // Returns true if the function has been modified.
137 //
138 // Note: This function does not delete useless control structures. All
139 // existing control structures will remain. This can leave not-insignificant
140 // sequences of ultimately useless code.
141 // TODO(): Remove useless control constructs.
142 bool AggressiveDCE(Function* func);
143
144 Pass::Status ProcessImpl();
145
146 // True if current function has a call instruction contained in it
147 bool call_in_func_;
148
149 // True if current function is an entry point
150 bool func_is_entry_point_;
151
152 // True if current function is entry point and has no function calls.
153 bool private_like_local_;
154
155 // Live Instruction Worklist. An instruction is added to this list
156 // if it might have a side effect, either directly or indirectly.
157 // If we don't know, then add it to this list. Instructions are
158 // removed from this list as the algorithm traces side effects,
159 // building up the live instructions set |live_insts_|.
160 std::queue<Instruction*> worklist_;
161
162 // Map from block to the branch instruction in the header of the most
163 // immediate controlling structured if or loop. A loop header block points
164 // to its own branch instruction. An if-selection block points to the branch
165 // of an enclosing construct's header, if one exists.
166 std::unordered_map<BasicBlock*, Instruction*> block2headerBranch_;
167
168 // Map from header block to the branch instruction in the header of the
169 // structured construct enclosing it.
170 // The liveness algorithm is designed to iteratively mark as live all
171 // structured constructs enclosing a live instruction.
172 std::unordered_map<BasicBlock*, Instruction*> header2nextHeaderBranch_;
173
174 // Maps basic block to their index in the structured order traversal.
175 std::unordered_map<BasicBlock*, uint32_t> structured_order_index_;
176
177 // Map from branch to its associated merge instruction, if any
178 std::unordered_map<Instruction*, Instruction*> branch2merge_;
179
180 // Store instructions to variables of private storage
181 std::vector<Instruction*> private_stores_;
182
183 // Live Instructions
184 utils::BitVector live_insts_;
185
186 // Live Local Variables
187 std::unordered_set<uint32_t> live_local_vars_;
188
189 // List of instructions to delete. Deletion is delayed until debug and
190 // annotation instructions are processed.
191 std::vector<Instruction*> to_kill_;
192
193 // Extensions supported by this pass.
194 std::unordered_set<std::string> extensions_whitelist_;
195};
196
197} // namespace opt
198} // namespace spvtools
199
200#endif // SOURCE_OPT_AGGRESSIVE_DEAD_CODE_ELIM_PASS_H_
201