1 // Copyright (c) 2016 Google Inc. 2 // 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 #ifndef SOURCE_OPT_DEF_USE_MANAGER_H_ 16 #define SOURCE_OPT_DEF_USE_MANAGER_H_ 17 18 #include <set> 19 #include <unordered_map> 20 #include <vector> 21 22 #include "source/opt/instruction.h" 23 #include "source/opt/module.h" 24 #include "spirv-tools/libspirv.hpp" 25 26 namespace spvtools { 27 namespace opt { 28 namespace analysis { 29 30 // Definition should never be null. User can be null, however, such an entry 31 // should be used only for searching (e.g. all users of a particular definition) 32 // and never stored in a container. 33 struct UserEntry { 34 Instruction* def; 35 Instruction* user; 36 }; 37 38 inline bool operator==(const UserEntry& lhs, const UserEntry& rhs) { 39 return lhs.def == rhs.def && lhs.user == rhs.user; 40 } 41 42 // Orders UserEntry for use in associative containers (i.e. less than ordering). 43 // 44 // The definition of an UserEntry is treated as the major key and the users as 45 // the minor key so that all the users of a particular definition are 46 // consecutive in a container. 47 // 48 // A null user always compares less than a real user. This is done to provide 49 // easy values to search for the beginning of the users of a particular 50 // definition (i.e. using {def, nullptr}). 51 struct UserEntryLess { operatorUserEntryLess52 bool operator()(const UserEntry& lhs, const UserEntry& rhs) const { 53 // If lhs.def and rhs.def are both null, fall through to checking the 54 // second entries. 55 if (!lhs.def && rhs.def) return true; 56 if (lhs.def && !rhs.def) return false; 57 58 // If neither definition is null, then compare unique ids. 59 if (lhs.def && rhs.def) { 60 if (lhs.def->unique_id() < rhs.def->unique_id()) return true; 61 if (rhs.def->unique_id() < lhs.def->unique_id()) return false; 62 } 63 64 // Return false on equality. 65 if (!lhs.user && !rhs.user) return false; 66 if (!lhs.user) return true; 67 if (!rhs.user) return false; 68 69 // If neither user is null then compare unique ids. 70 return lhs.user->unique_id() < rhs.user->unique_id(); 71 } 72 }; 73 74 // A class for analyzing and managing defs and uses in an Module. 75 class DefUseManager { 76 public: 77 using IdToDefMap = std::unordered_map<uint32_t, Instruction*>; 78 79 // Constructs a def-use manager from the given |module|. All internal messages 80 // will be communicated to the outside via the given message |consumer|. This 81 // instance only keeps a reference to the |consumer|, so the |consumer| should 82 // outlive this instance. DefUseManager(Module * module)83 DefUseManager(Module* module) { AnalyzeDefUse(module); } 84 85 DefUseManager(const DefUseManager&) = delete; 86 DefUseManager(DefUseManager&&) = delete; 87 DefUseManager& operator=(const DefUseManager&) = delete; 88 DefUseManager& operator=(DefUseManager&&) = delete; 89 90 // Analyzes the defs in the given |inst|. 91 void AnalyzeInstDef(Instruction* inst); 92 93 // Analyzes the uses in the given |inst|. 94 // 95 // All operands of |inst| must be analyzed as defs. 96 void AnalyzeInstUse(Instruction* inst); 97 98 // Analyzes the defs and uses in the given |inst|. 99 void AnalyzeInstDefUse(Instruction* inst); 100 101 // Returns the def instruction for the given |id|. If there is no instruction 102 // defining |id|, returns nullptr. 103 Instruction* GetDef(uint32_t id); 104 const Instruction* GetDef(uint32_t id) const; 105 106 // Runs the given function |f| on each unique user instruction of |def| (or 107 // |id|). 108 // 109 // If one instruction uses |def| in multiple operands, that instruction will 110 // only be visited once. 111 // 112 // |def| (or |id|) must be registered as a definition. 113 void ForEachUser(const Instruction* def, 114 const std::function<void(Instruction*)>& f) const; 115 void ForEachUser(uint32_t id, 116 const std::function<void(Instruction*)>& f) const; 117 118 // Runs the given function |f| on each unique user instruction of |def| (or 119 // |id|). If |f| returns false, iteration is terminated and this function 120 // returns false. 121 // 122 // If one instruction uses |def| in multiple operands, that instruction will 123 // be only be visited once. 124 // 125 // |def| (or |id|) must be registered as a definition. 126 bool WhileEachUser(const Instruction* def, 127 const std::function<bool(Instruction*)>& f) const; 128 bool WhileEachUser(uint32_t id, 129 const std::function<bool(Instruction*)>& f) const; 130 131 // Runs the given function |f| on each unique use of |def| (or 132 // |id|). 133 // 134 // If one instruction uses |def| in multiple operands, each operand will be 135 // visited separately. 136 // 137 // |def| (or |id|) must be registered as a definition. 138 void ForEachUse( 139 const Instruction* def, 140 const std::function<void(Instruction*, uint32_t operand_index)>& f) const; 141 void ForEachUse( 142 uint32_t id, 143 const std::function<void(Instruction*, uint32_t operand_index)>& f) const; 144 145 // Runs the given function |f| on each unique use of |def| (or 146 // |id|). If |f| returns false, iteration is terminated and this function 147 // returns false. 148 // 149 // If one instruction uses |def| in multiple operands, each operand will be 150 // visited separately. 151 // 152 // |def| (or |id|) must be registered as a definition. 153 bool WhileEachUse( 154 const Instruction* def, 155 const std::function<bool(Instruction*, uint32_t operand_index)>& f) const; 156 bool WhileEachUse( 157 uint32_t id, 158 const std::function<bool(Instruction*, uint32_t operand_index)>& f) const; 159 160 // Returns the number of users of |def| (or |id|). 161 uint32_t NumUsers(const Instruction* def) const; 162 uint32_t NumUsers(uint32_t id) const; 163 164 // Returns the number of uses of |def| (or |id|). 165 uint32_t NumUses(const Instruction* def) const; 166 uint32_t NumUses(uint32_t id) const; 167 168 // Returns the annotation instrunctions which are a direct use of the given 169 // |id|. This means when the decorations are applied through decoration 170 // group(s), this function will just return the OpGroupDecorate 171 // instruction(s) which refer to the given id as an operand. The OpDecorate 172 // instructions which decorate the decoration group will not be returned. 173 std::vector<Instruction*> GetAnnotations(uint32_t id) const; 174 175 // Returns the map from ids to their def instructions. id_to_defs()176 const IdToDefMap& id_to_defs() const { return id_to_def_; } 177 178 // Clear the internal def-use record of the given instruction |inst|. This 179 // method will update the use information of the operand ids of |inst|. The 180 // record: |inst| uses an |id|, will be removed from the use records of |id|. 181 // If |inst| defines an result id, the use record of this result id will also 182 // be removed. Does nothing if |inst| was not analyzed before. 183 void ClearInst(Instruction* inst); 184 185 // Erases the records that a given instruction uses its operand ids. 186 void EraseUseRecordsOfOperandIds(const Instruction* inst); 187 188 friend bool CompareAndPrintDifferences(const DefUseManager&, 189 const DefUseManager&); 190 191 // If |inst| has not already been analysed, then analyses its definition and 192 // uses. 193 void UpdateDefUse(Instruction* inst); 194 195 private: 196 using IdToUsersMap = std::set<UserEntry, UserEntryLess>; 197 using InstToUsedIdsMap = 198 std::unordered_map<const Instruction*, std::vector<uint32_t>>; 199 200 // Returns the first location that {|def|, nullptr} could be inserted into the 201 // users map without violating ordering. 202 IdToUsersMap::const_iterator UsersBegin(const Instruction* def) const; 203 204 // Returns true if |iter| has not reached the end of |def|'s users. 205 // 206 // In the first version |iter| is compared against the end of the map for 207 // validity before other checks. In the second version, |iter| is compared 208 // against |cached_end| for validity before other checks. This allows caching 209 // the map's end which is a performance improvement on some platforms. 210 bool UsersNotEnd(const IdToUsersMap::const_iterator& iter, 211 const Instruction* def) const; 212 bool UsersNotEnd(const IdToUsersMap::const_iterator& iter, 213 const IdToUsersMap::const_iterator& cached_end, 214 const Instruction* def) const; 215 216 // Analyzes the defs and uses in the given |module| and populates data 217 // structures in this class. Does nothing if |module| is nullptr. 218 void AnalyzeDefUse(Module* module); 219 220 IdToDefMap id_to_def_; // Mapping from ids to their definitions 221 IdToUsersMap id_to_users_; // Mapping from ids to their users 222 // Mapping from instructions to the ids used in the instruction. 223 InstToUsedIdsMap inst_to_used_ids_; 224 }; 225 226 } // namespace analysis 227 } // namespace opt 228 } // namespace spvtools 229 230 #endif // SOURCE_OPT_DEF_USE_MANAGER_H_ 231