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 #include "source/opt/local_single_block_elim_pass.h"
18
19 #include <vector>
20
21 #include "source/opt/iterator.h"
22
23 namespace spvtools {
24 namespace opt {
25 namespace {
26
27 const uint32_t kStoreValIdInIdx = 1;
28
29 } // anonymous namespace
30
HasOnlySupportedRefs(uint32_t ptrId)31 bool LocalSingleBlockLoadStoreElimPass::HasOnlySupportedRefs(uint32_t ptrId) {
32 if (supported_ref_ptrs_.find(ptrId) != supported_ref_ptrs_.end()) return true;
33 if (get_def_use_mgr()->WhileEachUser(ptrId, [this](Instruction* user) {
34 auto dbg_op = user->GetCommonDebugOpcode();
35 if (dbg_op == CommonDebugInfoDebugDeclare ||
36 dbg_op == CommonDebugInfoDebugValue) {
37 return true;
38 }
39 SpvOp op = user->opcode();
40 if (IsNonPtrAccessChain(op) || op == SpvOpCopyObject) {
41 if (!HasOnlySupportedRefs(user->result_id())) {
42 return false;
43 }
44 } else if (op != SpvOpStore && op != SpvOpLoad && op != SpvOpName &&
45 !IsNonTypeDecorate(op)) {
46 return false;
47 }
48 return true;
49 })) {
50 supported_ref_ptrs_.insert(ptrId);
51 return true;
52 }
53 return false;
54 }
55
LocalSingleBlockLoadStoreElim(Function * func)56 bool LocalSingleBlockLoadStoreElimPass::LocalSingleBlockLoadStoreElim(
57 Function* func) {
58 // Perform local store/load, load/load and store/store elimination
59 // on each block
60 bool modified = false;
61 std::vector<Instruction*> instructions_to_kill;
62 std::unordered_set<Instruction*> instructions_to_save;
63 for (auto bi = func->begin(); bi != func->end(); ++bi) {
64 var2store_.clear();
65 var2load_.clear();
66 auto next = bi->begin();
67 for (auto ii = next; ii != bi->end(); ii = next) {
68 ++next;
69 switch (ii->opcode()) {
70 case SpvOpStore: {
71 // Verify store variable is target type
72 uint32_t varId;
73 Instruction* ptrInst = GetPtr(&*ii, &varId);
74 if (!IsTargetVar(varId)) continue;
75 if (!HasOnlySupportedRefs(varId)) continue;
76 // If a store to the whole variable, remember it for succeeding
77 // loads and stores. Otherwise forget any previous store to that
78 // variable.
79 if (ptrInst->opcode() == SpvOpVariable) {
80 // If a previous store to same variable, mark the store
81 // for deletion if not still used. Don't delete store
82 // if debugging; let ssa-rewrite and DCE handle it
83 auto prev_store = var2store_.find(varId);
84 if (prev_store != var2store_.end() &&
85 instructions_to_save.count(prev_store->second) == 0 &&
86 !context()->get_debug_info_mgr()->IsVariableDebugDeclared(
87 varId)) {
88 instructions_to_kill.push_back(prev_store->second);
89 modified = true;
90 }
91
92 bool kill_store = false;
93 auto li = var2load_.find(varId);
94 if (li != var2load_.end()) {
95 if (ii->GetSingleWordInOperand(kStoreValIdInIdx) ==
96 li->second->result_id()) {
97 // We are storing the same value that already exists in the
98 // memory location. The store does nothing.
99 kill_store = true;
100 }
101 }
102
103 if (!kill_store) {
104 var2store_[varId] = &*ii;
105 var2load_.erase(varId);
106 } else {
107 instructions_to_kill.push_back(&*ii);
108 modified = true;
109 }
110 } else {
111 assert(IsNonPtrAccessChain(ptrInst->opcode()));
112 var2store_.erase(varId);
113 var2load_.erase(varId);
114 }
115 } break;
116 case SpvOpLoad: {
117 // Verify store variable is target type
118 uint32_t varId;
119 Instruction* ptrInst = GetPtr(&*ii, &varId);
120 if (!IsTargetVar(varId)) continue;
121 if (!HasOnlySupportedRefs(varId)) continue;
122 uint32_t replId = 0;
123 if (ptrInst->opcode() == SpvOpVariable) {
124 // If a load from a variable, look for a previous store or
125 // load from that variable and use its value.
126 auto si = var2store_.find(varId);
127 if (si != var2store_.end()) {
128 replId = si->second->GetSingleWordInOperand(kStoreValIdInIdx);
129 } else {
130 auto li = var2load_.find(varId);
131 if (li != var2load_.end()) {
132 replId = li->second->result_id();
133 }
134 }
135 } else {
136 // If a partial load of a previously seen store, remember
137 // not to delete the store.
138 auto si = var2store_.find(varId);
139 if (si != var2store_.end()) instructions_to_save.insert(si->second);
140 }
141 if (replId != 0) {
142 // replace load's result id and delete load
143 context()->KillNamesAndDecorates(&*ii);
144 context()->ReplaceAllUsesWith(ii->result_id(), replId);
145 instructions_to_kill.push_back(&*ii);
146 modified = true;
147 } else {
148 if (ptrInst->opcode() == SpvOpVariable)
149 var2load_[varId] = &*ii; // register load
150 }
151 } break;
152 case SpvOpFunctionCall: {
153 // Conservatively assume all locals are redefined for now.
154 // TODO(): Handle more optimally
155 var2store_.clear();
156 var2load_.clear();
157 } break;
158 default:
159 break;
160 }
161 }
162 }
163
164 for (Instruction* inst : instructions_to_kill) {
165 context()->KillInst(inst);
166 }
167
168 return modified;
169 }
170
Initialize()171 void LocalSingleBlockLoadStoreElimPass::Initialize() {
172 // Initialize Target Type Caches
173 seen_target_vars_.clear();
174 seen_non_target_vars_.clear();
175
176 // Clear collections
177 supported_ref_ptrs_.clear();
178
179 // Initialize extensions allowlist
180 InitExtensions();
181 }
182
AllExtensionsSupported() const183 bool LocalSingleBlockLoadStoreElimPass::AllExtensionsSupported() const {
184 // If any extension not in allowlist, return false
185 for (auto& ei : get_module()->extensions()) {
186 const char* extName =
187 reinterpret_cast<const char*>(&ei.GetInOperand(0).words[0]);
188 if (extensions_allowlist_.find(extName) == extensions_allowlist_.end())
189 return false;
190 }
191 // only allow NonSemantic.Shader.DebugInfo.100, we cannot safely optimise
192 // around unknown extended
193 // instruction sets even if they are non-semantic
194 for (auto& inst : context()->module()->ext_inst_imports()) {
195 assert(inst.opcode() == SpvOpExtInstImport &&
196 "Expecting an import of an extension's instruction set.");
197 const char* extension_name =
198 reinterpret_cast<const char*>(&inst.GetInOperand(0).words[0]);
199 if (0 == std::strncmp(extension_name, "NonSemantic.", 12) &&
200 0 != std::strncmp(extension_name, "NonSemantic.Shader.DebugInfo.100",
201 32)) {
202 return false;
203 }
204 }
205 return true;
206 }
207
ProcessImpl()208 Pass::Status LocalSingleBlockLoadStoreElimPass::ProcessImpl() {
209 // Assumes relaxed logical addressing only (see instruction.h).
210 if (context()->get_feature_mgr()->HasCapability(SpvCapabilityAddresses))
211 return Status::SuccessWithoutChange;
212
213 // Do not process if module contains OpGroupDecorate. Additional
214 // support required in KillNamesAndDecorates().
215 // TODO(greg-lunarg): Add support for OpGroupDecorate
216 for (auto& ai : get_module()->annotations())
217 if (ai.opcode() == SpvOpGroupDecorate) return Status::SuccessWithoutChange;
218 // If any extensions in the module are not explicitly supported,
219 // return unmodified.
220 if (!AllExtensionsSupported()) return Status::SuccessWithoutChange;
221 // Process all entry point functions
222 ProcessFunction pfn = [this](Function* fp) {
223 return LocalSingleBlockLoadStoreElim(fp);
224 };
225
226 bool modified = context()->ProcessReachableCallTree(pfn);
227 return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
228 }
229
230 LocalSingleBlockLoadStoreElimPass::LocalSingleBlockLoadStoreElimPass() =
231 default;
232
Process()233 Pass::Status LocalSingleBlockLoadStoreElimPass::Process() {
234 Initialize();
235 return ProcessImpl();
236 }
237
InitExtensions()238 void LocalSingleBlockLoadStoreElimPass::InitExtensions() {
239 extensions_allowlist_.clear();
240 extensions_allowlist_.insert({
241 "SPV_AMD_shader_explicit_vertex_parameter",
242 "SPV_AMD_shader_trinary_minmax",
243 "SPV_AMD_gcn_shader",
244 "SPV_KHR_shader_ballot",
245 "SPV_AMD_shader_ballot",
246 "SPV_AMD_gpu_shader_half_float",
247 "SPV_KHR_shader_draw_parameters",
248 "SPV_KHR_subgroup_vote",
249 "SPV_KHR_8bit_storage",
250 "SPV_KHR_16bit_storage",
251 "SPV_KHR_device_group",
252 "SPV_KHR_multiview",
253 "SPV_NVX_multiview_per_view_attributes",
254 "SPV_NV_viewport_array2",
255 "SPV_NV_stereo_view_rendering",
256 "SPV_NV_sample_mask_override_coverage",
257 "SPV_NV_geometry_shader_passthrough",
258 "SPV_AMD_texture_gather_bias_lod",
259 "SPV_KHR_storage_buffer_storage_class",
260 "SPV_KHR_variable_pointers",
261 "SPV_AMD_gpu_shader_int16",
262 "SPV_KHR_post_depth_coverage",
263 "SPV_KHR_shader_atomic_counter_ops",
264 "SPV_EXT_shader_stencil_export",
265 "SPV_EXT_shader_viewport_index_layer",
266 "SPV_AMD_shader_image_load_store_lod",
267 "SPV_AMD_shader_fragment_mask",
268 "SPV_EXT_fragment_fully_covered",
269 "SPV_AMD_gpu_shader_half_float_fetch",
270 "SPV_GOOGLE_decorate_string",
271 "SPV_GOOGLE_hlsl_functionality1",
272 "SPV_GOOGLE_user_type",
273 "SPV_NV_shader_subgroup_partitioned",
274 "SPV_EXT_demote_to_helper_invocation",
275 "SPV_EXT_descriptor_indexing",
276 "SPV_NV_fragment_shader_barycentric",
277 "SPV_NV_compute_shader_derivatives",
278 "SPV_NV_shader_image_footprint",
279 "SPV_NV_shading_rate",
280 "SPV_NV_mesh_shader",
281 "SPV_NV_ray_tracing",
282 "SPV_KHR_ray_tracing",
283 "SPV_KHR_ray_query",
284 "SPV_EXT_fragment_invocation_density",
285 "SPV_EXT_physical_storage_buffer",
286 "SPV_KHR_terminate_invocation",
287 "SPV_KHR_subgroup_uniform_control_flow",
288 "SPV_KHR_integer_dot_product",
289 "SPV_EXT_shader_image_int64",
290 "SPV_KHR_non_semantic_info",
291 });
292 }
293
294 } // namespace opt
295 } // namespace spvtools
296