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(); name()48 const char* name() const override { return "eliminate-dead-code-aggressive"; } 49 Status Process() override; 50 GetPreservedAnalyses()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. IsLive(const Instruction * inst)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_. AddToWorklist(Instruction * inst)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(Function* func, uint32_t ptrId); 89 90 // Initialize extensions allowlist 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(Function* func, 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 // For function |func|, mark all Stores to non-function-scope variables 131 // and block terminating instructions as live. Recursively mark the values 132 // they use. When complete, mark any non-live instructions to be deleted. 133 // Returns true if the function has been modified. 134 // 135 // Note: This function does not delete useless control structures. All 136 // existing control structures will remain. This can leave not-insignificant 137 // sequences of ultimately useless code. 138 // TODO(): Remove useless control constructs. 139 bool AggressiveDCE(Function* func); 140 141 Pass::Status ProcessImpl(); 142 143 // True if current function has a call instruction contained in it 144 bool call_in_func_; 145 146 // True if current function is an entry point 147 bool func_is_entry_point_; 148 149 // True if current function is entry point and has no function calls. 150 bool private_like_local_; 151 152 // Live Instruction Worklist. An instruction is added to this list 153 // if it might have a side effect, either directly or indirectly. 154 // If we don't know, then add it to this list. Instructions are 155 // removed from this list as the algorithm traces side effects, 156 // building up the live instructions set |live_insts_|. 157 std::queue<Instruction*> worklist_; 158 159 // Map from block to the branch instruction in the header of the most 160 // immediate controlling structured if or loop. A loop header block points 161 // to its own branch instruction. An if-selection block points to the branch 162 // of an enclosing construct's header, if one exists. 163 std::unordered_map<BasicBlock*, Instruction*> block2headerBranch_; 164 165 // Map from header block to the branch instruction in the header of the 166 // structured construct enclosing it. 167 // The liveness algorithm is designed to iteratively mark as live all 168 // structured constructs enclosing a live instruction. 169 std::unordered_map<BasicBlock*, Instruction*> header2nextHeaderBranch_; 170 171 // Maps basic block to their index in the structured order traversal. 172 std::unordered_map<BasicBlock*, uint32_t> structured_order_index_; 173 174 // Map from branch to its associated merge instruction, if any 175 std::unordered_map<Instruction*, Instruction*> branch2merge_; 176 177 // Store instructions to variables of private storage 178 std::vector<Instruction*> private_stores_; 179 180 // Live Instructions 181 utils::BitVector live_insts_; 182 183 // Live Local Variables 184 std::unordered_set<uint32_t> live_local_vars_; 185 186 // List of instructions to delete. Deletion is delayed until debug and 187 // annotation instructions are processed. 188 std::vector<Instruction*> to_kill_; 189 190 // Extensions supported by this pass. 191 std::unordered_set<std::string> extensions_allowlist_; 192 }; 193 194 } // namespace opt 195 } // namespace spvtools 196 197 #endif // SOURCE_OPT_AGGRESSIVE_DEAD_CODE_ELIM_PASS_H_ 198