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