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 36 namespace spvtools { 37 namespace opt { 38 39 // See optimizer.hpp for documentation. 40 class 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(bool preserve_interface = false) preserve_interface_(preserve_interface)48 : preserve_interface_(preserve_interface) {} 49 name()50 const char* name() const override { return "eliminate-dead-code-aggressive"; } 51 Status Process() override; 52 GetPreservedAnalyses()53 IRContext::Analysis GetPreservedAnalyses() override { 54 return IRContext::kAnalysisDefUse | 55 IRContext::kAnalysisInstrToBlockMapping | 56 IRContext::kAnalysisConstants | IRContext::kAnalysisTypes; 57 } 58 59 private: 60 // Preserve entry point interface if true. All variables in interface 61 // will be marked live and will not be eliminated. This mode is needed by 62 // GPU-Assisted Validation instrumentation where a change in the interface 63 // is not allowed. 64 bool preserve_interface_; 65 66 // Return true if |varId| is a variable of |storageClass|. |varId| must either 67 // be 0 or the result of an instruction. 68 bool IsVarOfStorage(uint32_t varId, uint32_t storageClass); 69 70 // Return true if the instance of the variable |varId| can only be access in 71 // |func|. For example, a function scope variable, or a private variable 72 // where |func| is an entry point with no function calls. 73 bool IsLocalVar(uint32_t varId, Function* func); 74 75 // Return true if |inst| is marked live. IsLive(const Instruction * inst)76 bool IsLive(const Instruction* inst) const { 77 return live_insts_.Get(inst->unique_id()); 78 } 79 80 // Adds entry points, execution modes and workgroup size decorations to the 81 // worklist for processing with the first function. 82 void InitializeModuleScopeLiveInstructions(); 83 84 // Add |inst| to worklist_ and live_insts_. AddToWorklist(Instruction * inst)85 void AddToWorklist(Instruction* inst) { 86 if (!live_insts_.Set(inst->unique_id())) { 87 worklist_.push(inst); 88 } 89 } 90 91 // Add all store instruction which use |ptrId|, directly or indirectly, 92 // to the live instruction worklist. 93 void AddStores(Function* func, uint32_t ptrId); 94 95 // Initialize extensions allowlist 96 void InitExtensions(); 97 98 // Return true if all extensions in this module are supported by this pass. 99 bool AllExtensionsSupported() const; 100 101 // Returns true if the target of |inst| is dead. An instruction is dead if 102 // its result id is used in decoration or debug instructions only. |inst| is 103 // assumed to be OpName, OpMemberName or an annotation instruction. 104 bool IsTargetDead(Instruction* inst); 105 106 // If |varId| is local, mark all stores of varId as live. 107 void ProcessLoad(Function* func, uint32_t varId); 108 109 // Add branch to |labelId| to end of block |bp|. 110 void AddBranch(uint32_t labelId, BasicBlock* bp); 111 112 // Add all break and continue branches in the construct associated with 113 // |mergeInst| to worklist if not already live 114 void AddBreaksAndContinuesToWorklist(Instruction* mergeInst); 115 116 // Eliminates dead debug2 and annotation instructions. Marks dead globals for 117 // removal (e.g. types, constants and variables). 118 bool ProcessGlobalValues(); 119 120 // Erases functions that are unreachable from the entry points of the module. 121 bool EliminateDeadFunctions(); 122 123 // For function |func|, mark all Stores to non-function-scope variables 124 // and block terminating instructions as live. Recursively mark the values 125 // they use. When complete, mark any non-live instructions to be deleted. 126 // Returns true if the function has been modified. 127 // 128 // Note: This function does not delete useless control structures. All 129 // existing control structures will remain. This can leave not-insignificant 130 // sequences of ultimately useless code. 131 // TODO(): Remove useless control constructs. 132 bool AggressiveDCE(Function* func); 133 134 Pass::Status ProcessImpl(); 135 136 // Adds instructions which must be kept because of they have side-effects 137 // that ADCE cannot model to the work list. 138 void InitializeWorkList(Function* func, 139 std::list<BasicBlock*>& structured_order); 140 141 // Process each instruction in the work list by marking any instruction that 142 // that it depends on as live, and adding it to the work list. The work list 143 // will be empty at the end. 144 void ProcessWorkList(Function* func); 145 146 // Kills any instructions in |func| that have not been marked as live. 147 bool KillDeadInstructions(const Function* func, 148 std::list<BasicBlock*>& structured_order); 149 150 // Adds the instructions that define the operands of |inst| to the work list. 151 void AddOperandsToWorkList(const Instruction* inst); 152 153 // Marks all of the labels and branch that inst requires as live. 154 void MarkBlockAsLive(Instruction* inst); 155 156 // Marks any variables from which |inst| may require data as live. 157 void MarkLoadedVariablesAsLive(Function* func, Instruction* inst); 158 159 // Returns the id of the variable that |ptr_id| point to. |ptr_id| must be a 160 // value whose type is a pointer. 161 uint32_t GetVariableId(uint32_t ptr_id); 162 163 // Returns all of the ids for the variables from which |inst| will load data. 164 std::vector<uint32_t> GetLoadedVariables(Instruction* inst); 165 166 // Returns all of the ids for the variables from which |inst| will load data. 167 // The opcode of |inst| must be OpFunctionCall. 168 std::vector<uint32_t> GetLoadedVariablesFromFunctionCall( 169 const Instruction* inst); 170 171 // Returns the id of the variable from which |inst| will load data. |inst| 172 // must not be an OpFunctionCall. Returns 0 if no data is read or the 173 // variable cannot be determined. Note that in logical addressing mode the 174 // latter is not possible for function and private storage class because there 175 // cannot be variable pointers pointing to those storage classes. 176 uint32_t GetLoadedVariableFromNonFunctionCalls(Instruction* inst); 177 178 // Adds all decorations of |inst| to the work list. 179 void AddDecorationsToWorkList(const Instruction* inst); 180 181 // Adds DebugScope instruction associated with |inst| to the work list. 182 void AddDebugScopeToWorkList(const Instruction* inst); 183 184 // Adds all debug instruction associated with |inst| to the work list. 185 void AddDebugInstructionsToWorkList(const Instruction* inst); 186 187 // Marks all of the OpFunctionParameter instructions in |func| as live. 188 void MarkFunctionParameterAsLive(const Function* func); 189 190 // Returns the terminator instruction in the header for the innermost 191 // construct that contains |blk|. Returns nullptr if no such header exists. 192 Instruction* GetHeaderBranch(BasicBlock* blk); 193 194 // Returns the header for the innermost construct that contains |blk|. A loop 195 // header will be its own header. Returns nullptr if no such header exists. 196 BasicBlock* GetHeaderBlock(BasicBlock* blk) const; 197 198 // Returns the same as |GetHeaderBlock| except if |blk| is a loop header it 199 // will return the header of the next enclosing construct. Returns nullptr if 200 // no such header exists. 201 Instruction* GetBranchForNextHeader(BasicBlock* blk); 202 203 // Returns the merge instruction in the same basic block as |inst|. Returns 204 // nullptr if one does not exist. 205 Instruction* GetMergeInstruction(Instruction* inst); 206 207 // Returns true if |bb| is in the construct with header |header_block|. 208 bool BlockIsInConstruct(BasicBlock* header_block, BasicBlock* bb); 209 210 // Returns true if |func| is an entry point that does not have any function 211 // calls. 212 bool IsEntryPointWithNoCalls(Function* func); 213 214 // Returns true if |func| is an entry point. 215 bool IsEntryPoint(Function* func); 216 217 // Returns true if |func| contains a function call. 218 bool HasCall(Function* func); 219 220 // Marks the first block, which is the entry block, in |func| as live. 221 void MarkFirstBlockAsLive(Function* func); 222 223 // Adds an OpUnreachable instruction at the end of |block|. 224 void AddUnreachable(BasicBlock*& block); 225 226 // Marks the OpLoopMerge and the terminator in |basic_block| as live if 227 // |basic_block| is a loop header. 228 void MarkLoopConstructAsLiveIfLoopHeader(BasicBlock* basic_block); 229 230 // The cached results for |IsEntryPointWithNoCalls|. It maps the function's 231 // result id to the return value. 232 std::unordered_map<uint32_t, bool> entry_point_with_no_calls_cache_; 233 234 // Live Instruction Worklist. An instruction is added to this list 235 // if it might have a side effect, either directly or indirectly. 236 // If we don't know, then add it to this list. Instructions are 237 // removed from this list as the algorithm traces side effects, 238 // building up the live instructions set |live_insts_|. 239 std::queue<Instruction*> worklist_; 240 241 // Live Instructions 242 utils::BitVector live_insts_; 243 244 // Live Local Variables 245 std::unordered_set<uint32_t> live_local_vars_; 246 247 // List of instructions to delete. Deletion is delayed until debug and 248 // annotation instructions are processed. 249 std::vector<Instruction*> to_kill_; 250 251 // Extensions supported by this pass. 252 std::unordered_set<std::string> extensions_allowlist_; 253 }; 254 255 } // namespace opt 256 } // namespace spvtools 257 258 #endif // SOURCE_OPT_AGGRESSIVE_DEAD_CODE_ELIM_PASS_H_ 259