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