1// Copyright (c) 2017 The Khronos Group Inc.
2// Copyright (c) 2017 Valve Corporation
3// Copyright (c) 2017 LunarG Inc.
4// Copyright (c) 2018 Google LLC
5//
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18#include "source/opt/aggressive_dead_code_elim_pass.h"
19
20#include <memory>
21#include <stack>
22
23#include "source/cfa.h"
24#include "source/latest_version_glsl_std_450_header.h"
25#include "source/opt/iterator.h"
26#include "source/opt/reflect.h"
27#include "source/spirv_constant.h"
28
29namespace spvtools {
30namespace opt {
31
32namespace {
33
34const uint32_t kTypePointerStorageClassInIdx = 0;
35const uint32_t kEntryPointFunctionIdInIdx = 1;
36const uint32_t kSelectionMergeMergeBlockIdInIdx = 0;
37const uint32_t kLoopMergeMergeBlockIdInIdx = 0;
38const uint32_t kLoopMergeContinueBlockIdInIdx = 1;
39const uint32_t kCopyMemoryTargetAddrInIdx = 0;
40const uint32_t kCopyMemorySourceAddrInIdx = 1;
41
42// Sorting functor to present annotation instructions in an easy-to-process
43// order. The functor orders by opcode first and falls back on unique id
44// ordering if both instructions have the same opcode.
45//
46// Desired priority:
47// SpvOpGroupDecorate
48// SpvOpGroupMemberDecorate
49// SpvOpDecorate
50// SpvOpMemberDecorate
51// SpvOpDecorateId
52// SpvOpDecorateStringGOOGLE
53// SpvOpDecorationGroup
54struct DecorationLess {
55 bool operator()(const Instruction* lhs, const Instruction* rhs) const {
56 assert(lhs && rhs);
57 SpvOp lhsOp = lhs->opcode();
58 SpvOp rhsOp = rhs->opcode();
59 if (lhsOp != rhsOp) {
60#define PRIORITY_CASE(opcode) \
61 if (lhsOp == opcode && rhsOp != opcode) return true; \
62 if (rhsOp == opcode && lhsOp != opcode) return false;
63 // OpGroupDecorate and OpGroupMember decorate are highest priority to
64 // eliminate dead targets early and simplify subsequent checks.
65 PRIORITY_CASE(SpvOpGroupDecorate)
66 PRIORITY_CASE(SpvOpGroupMemberDecorate)
67 PRIORITY_CASE(SpvOpDecorate)
68 PRIORITY_CASE(SpvOpMemberDecorate)
69 PRIORITY_CASE(SpvOpDecorateId)
70 PRIORITY_CASE(SpvOpDecorateStringGOOGLE)
71 // OpDecorationGroup is lowest priority to ensure use/def chains remain
72 // usable for instructions that target this group.
73 PRIORITY_CASE(SpvOpDecorationGroup)
74#undef PRIORITY_CASE
75 }
76
77 // Fall back to maintain total ordering (compare unique ids).
78 return *lhs < *rhs;
79 }
80};
81
82} // namespace
83
84bool AggressiveDCEPass::IsVarOfStorage(uint32_t varId, uint32_t storageClass) {
85 if (varId == 0) return false;
86 const Instruction* varInst = get_def_use_mgr()->GetDef(varId);
87 const SpvOp op = varInst->opcode();
88 if (op != SpvOpVariable) return false;
89 const uint32_t varTypeId = varInst->type_id();
90 const Instruction* varTypeInst = get_def_use_mgr()->GetDef(varTypeId);
91 if (varTypeInst->opcode() != SpvOpTypePointer) return false;
92 return varTypeInst->GetSingleWordInOperand(kTypePointerStorageClassInIdx) ==
93 storageClass;
94}
95
96bool AggressiveDCEPass::IsLocalVar(uint32_t varId) {
97 if (IsVarOfStorage(varId, SpvStorageClassFunction)) {
98 return true;
99 }
100 if (!private_like_local_) {
101 return false;
102 }
103
104 return IsVarOfStorage(varId, SpvStorageClassPrivate) ||
105 IsVarOfStorage(varId, SpvStorageClassWorkgroup);
106}
107
108void AggressiveDCEPass::AddStores(uint32_t ptrId) {
109 get_def_use_mgr()->ForEachUser(ptrId, [this, ptrId](Instruction* user) {
110 switch (user->opcode()) {
111 case SpvOpAccessChain:
112 case SpvOpInBoundsAccessChain:
113 case SpvOpCopyObject:
114 this->AddStores(user->result_id());
115 break;
116 case SpvOpLoad:
117 break;
118 case SpvOpCopyMemory:
119 case SpvOpCopyMemorySized:
120 if (user->GetSingleWordInOperand(kCopyMemoryTargetAddrInIdx) == ptrId) {
121 AddToWorklist(user);
122 }
123 break;
124 // If default, assume it stores e.g. frexp, modf, function call
125 case SpvOpStore:
126 default:
127 AddToWorklist(user);
128 break;
129 }
130 });
131}
132
133bool AggressiveDCEPass::AllExtensionsSupported() const {
134 // If any extension not in whitelist, return false
135 for (auto& ei : get_module()->extensions()) {
136 const char* extName =
137 reinterpret_cast<const char*>(&ei.GetInOperand(0).words[0]);
138 if (extensions_whitelist_.find(extName) == extensions_whitelist_.end())
139 return false;
140 }
141 return true;
142}
143
144bool AggressiveDCEPass::IsDead(Instruction* inst) {
145 if (IsLive(inst)) return false;
146 if ((inst->IsBranch() || inst->opcode() == SpvOpUnreachable) &&
147 !IsStructuredHeader(context()->get_instr_block(inst), nullptr, nullptr,
148 nullptr))
149 return false;
150 return true;
151}
152
153bool AggressiveDCEPass::IsTargetDead(Instruction* inst) {
154 const uint32_t tId = inst->GetSingleWordInOperand(0);
155 Instruction* tInst = get_def_use_mgr()->GetDef(tId);
156 if (IsAnnotationInst(tInst->opcode())) {
157 // This must be a decoration group. We go through annotations in a specific
158 // order. So if this is not used by any group or group member decorates, it
159 // is dead.
160 assert(tInst->opcode() == SpvOpDecorationGroup);
161 bool dead = true;
162 get_def_use_mgr()->ForEachUser(tInst, [&dead](Instruction* user) {
163 if (user->opcode() == SpvOpGroupDecorate ||
164 user->opcode() == SpvOpGroupMemberDecorate)
165 dead = false;
166 });
167 return dead;
168 }
169 return IsDead(tInst);
170}
171
172void AggressiveDCEPass::ProcessLoad(uint32_t varId) {
173 // Only process locals
174 if (!IsLocalVar(varId)) return;
175 // Return if already processed
176 if (live_local_vars_.find(varId) != live_local_vars_.end()) return;
177 // Mark all stores to varId as live
178 AddStores(varId);
179 // Cache varId as processed
180 live_local_vars_.insert(varId);
181}
182
183bool AggressiveDCEPass::IsStructuredHeader(BasicBlock* bp,
184 Instruction** mergeInst,
185 Instruction** branchInst,
186 uint32_t* mergeBlockId) {
187 if (!bp) return false;
188 Instruction* mi = bp->GetMergeInst();
189 if (mi == nullptr) return false;
190 Instruction* bri = &*bp->tail();
191 if (branchInst != nullptr) *branchInst = bri;
192 if (mergeInst != nullptr) *mergeInst = mi;
193 if (mergeBlockId != nullptr) *mergeBlockId = mi->GetSingleWordInOperand(0);
194 return true;
195}
196
197void AggressiveDCEPass::ComputeBlock2HeaderMaps(
198 std::list<BasicBlock*>& structuredOrder) {
199 block2headerBranch_.clear();
200 header2nextHeaderBranch_.clear();
201 branch2merge_.clear();
202 structured_order_index_.clear();
203 std::stack<Instruction*> currentHeaderBranch;
204 currentHeaderBranch.push(nullptr);
205 uint32_t currentMergeBlockId = 0;
206 uint32_t index = 0;
207 for (auto bi = structuredOrder.begin(); bi != structuredOrder.end();
208 ++bi, ++index) {
209 structured_order_index_[*bi] = index;
210 // If this block is the merge block of the current control construct,
211 // we are leaving the current construct so we must update state
212 if ((*bi)->id() == currentMergeBlockId) {
213 currentHeaderBranch.pop();
214 Instruction* chb = currentHeaderBranch.top();
215 if (chb != nullptr)
216 currentMergeBlockId = branch2merge_[chb]->GetSingleWordInOperand(0);
217 }
218 Instruction* mergeInst;
219 Instruction* branchInst;
220 uint32_t mergeBlockId;
221 bool is_header =
222 IsStructuredHeader(*bi, &mergeInst, &branchInst, &mergeBlockId);
223 // Map header block to next enclosing header.
224 if (is_header) header2nextHeaderBranch_[*bi] = currentHeaderBranch.top();
225 // If this is a loop header, update state first so the block will map to
226 // itself.
227 if (is_header && mergeInst->opcode() == SpvOpLoopMerge) {
228 currentHeaderBranch.push(branchInst);
229 branch2merge_[branchInst] = mergeInst;
230 currentMergeBlockId = mergeBlockId;
231 }
232 // Map the block to the current construct.
233 block2headerBranch_[*bi] = currentHeaderBranch.top();
234 // If this is an if header, update state so following blocks map to the if.
235 if (is_header && mergeInst->opcode() == SpvOpSelectionMerge) {
236 currentHeaderBranch.push(branchInst);
237 branch2merge_[branchInst] = mergeInst;
238 currentMergeBlockId = mergeBlockId;
239 }
240 }
241}
242
243void AggressiveDCEPass::AddBranch(uint32_t labelId, BasicBlock* bp) {
244 std::unique_ptr<Instruction> newBranch(
245 new Instruction(context(), SpvOpBranch, 0, 0,
246 {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {labelId}}}));
247 context()->AnalyzeDefUse(&*newBranch);
248 context()->set_instr_block(&*newBranch, bp);
249 bp->AddInstruction(std::move(newBranch));
250}
251
252void AggressiveDCEPass::AddBreaksAndContinuesToWorklist(
253 Instruction* mergeInst) {
254 assert(mergeInst->opcode() == SpvOpSelectionMerge ||
255 mergeInst->opcode() == SpvOpLoopMerge);
256
257 BasicBlock* header = context()->get_instr_block(mergeInst);
258 uint32_t headerIndex = structured_order_index_[header];
259 const uint32_t mergeId = mergeInst->GetSingleWordInOperand(0);
260 BasicBlock* merge = context()->get_instr_block(mergeId);
261 uint32_t mergeIndex = structured_order_index_[merge];
262 get_def_use_mgr()->ForEachUser(
263 mergeId, [headerIndex, mergeIndex, this](Instruction* user) {
264 if (!user->IsBranch()) return;
265 BasicBlock* block = context()->get_instr_block(user);
266 uint32_t index = structured_order_index_[block];
267 if (headerIndex < index && index < mergeIndex) {
268 // This is a break from the loop.
269 AddToWorklist(user);
270 // Add branch's merge if there is one.
271 Instruction* userMerge = branch2merge_[user];
272 if (userMerge != nullptr) AddToWorklist(userMerge);
273 }
274 });
275
276 if (mergeInst->opcode() != SpvOpLoopMerge) {
277 return;
278 }
279
280 // For loops we need to find the continues as well.
281 const uint32_t contId =
282 mergeInst->GetSingleWordInOperand(kLoopMergeContinueBlockIdInIdx);
283 get_def_use_mgr()->ForEachUser(contId, [&contId, this](Instruction* user) {
284 SpvOp op = user->opcode();
285 if (op == SpvOpBranchConditional || op == SpvOpSwitch) {
286 // A conditional branch or switch can only be a continue if it does not
287 // have a merge instruction or its merge block is not the continue block.
288 Instruction* hdrMerge = branch2merge_[user];
289 if (hdrMerge != nullptr && hdrMerge->opcode() == SpvOpSelectionMerge) {
290 uint32_t hdrMergeId =
291 hdrMerge->GetSingleWordInOperand(kSelectionMergeMergeBlockIdInIdx);
292 if (hdrMergeId == contId) return;
293 // Need to mark merge instruction too
294 AddToWorklist(hdrMerge);
295 }
296 } else if (op == SpvOpBranch) {
297 // An unconditional branch can only be a continue if it is not
298 // branching to its own merge block.
299 BasicBlock* blk = context()->get_instr_block(user);
300 Instruction* hdrBranch = block2headerBranch_[blk];
301 if (hdrBranch == nullptr) return;
302 Instruction* hdrMerge = branch2merge_[hdrBranch];
303 if (hdrMerge->opcode() == SpvOpLoopMerge) return;
304 uint32_t hdrMergeId =
305 hdrMerge->GetSingleWordInOperand(kSelectionMergeMergeBlockIdInIdx);
306 if (contId == hdrMergeId) return;
307 } else {
308 return;
309 }
310 AddToWorklist(user);
311 });
312}
313
314bool AggressiveDCEPass::AggressiveDCE(Function* func) {
315 // Mark function parameters as live.
316 AddToWorklist(&func->DefInst());
317 func->ForEachParam(
318 [this](const Instruction* param) {
319 AddToWorklist(const_cast<Instruction*>(param));
320 },
321 false);
322
323 // Compute map from block to controlling conditional branch
324 std::list<BasicBlock*> structuredOrder;
325 cfg()->ComputeStructuredOrder(func, &*func->begin(), &structuredOrder);
326 ComputeBlock2HeaderMaps(structuredOrder);
327 bool modified = false;
328 // Add instructions with external side effects to worklist. Also add branches
329 // EXCEPT those immediately contained in an "if" selection construct or a loop
330 // or continue construct.
331 // TODO(greg-lunarg): Handle Frexp, Modf more optimally
332 call_in_func_ = false;
333 func_is_entry_point_ = false;
334 private_stores_.clear();
335 // Stacks to keep track of when we are inside an if- or loop-construct.
336 // When immediately inside an if- or loop-construct, we do not initially
337 // mark branches live. All other branches must be marked live.
338 std::stack<bool> assume_branches_live;
339 std::stack<uint32_t> currentMergeBlockId;
340 // Push sentinel values on stack for when outside of any control flow.
341 assume_branches_live.push(true);
342 currentMergeBlockId.push(0);
343 for (auto bi = structuredOrder.begin(); bi != structuredOrder.end(); ++bi) {
344 // If exiting if or loop, update stacks
345 if ((*bi)->id() == currentMergeBlockId.top()) {
346 assume_branches_live.pop();
347 currentMergeBlockId.pop();
348 }
349 for (auto ii = (*bi)->begin(); ii != (*bi)->end(); ++ii) {
350 SpvOp op = ii->opcode();
351 switch (op) {
352 case SpvOpStore: {
353 uint32_t varId;
354 (void)GetPtr(&*ii, &varId);
355 // Mark stores as live if their variable is not function scope
356 // and is not private scope. Remember private stores for possible
357 // later inclusion. We cannot call IsLocalVar at this point because
358 // private_like_local_ has not been set yet.
359 if (IsVarOfStorage(varId, SpvStorageClassPrivate) ||
360 IsVarOfStorage(varId, SpvStorageClassWorkgroup))
361 private_stores_.push_back(&*ii);
362 else if (!IsVarOfStorage(varId, SpvStorageClassFunction))
363 AddToWorklist(&*ii);
364 } break;
365 case SpvOpCopyMemory:
366 case SpvOpCopyMemorySized: {
367 uint32_t varId;
368 (void)GetPtr(ii->GetSingleWordInOperand(kCopyMemoryTargetAddrInIdx),
369 &varId);
370 if (IsVarOfStorage(varId, SpvStorageClassPrivate) ||
371 IsVarOfStorage(varId, SpvStorageClassWorkgroup))
372 private_stores_.push_back(&*ii);
373 else if (!IsVarOfStorage(varId, SpvStorageClassFunction))
374 AddToWorklist(&*ii);
375 } break;
376 case SpvOpLoopMerge: {
377 assume_branches_live.push(false);
378 currentMergeBlockId.push(
379 ii->GetSingleWordInOperand(kLoopMergeMergeBlockIdInIdx));
380 } break;
381 case SpvOpSelectionMerge: {
382 assume_branches_live.push(false);
383 currentMergeBlockId.push(
384 ii->GetSingleWordInOperand(kSelectionMergeMergeBlockIdInIdx));
385 } break;
386 case SpvOpSwitch:
387 case SpvOpBranch:
388 case SpvOpBranchConditional:
389 case SpvOpUnreachable: {
390 if (assume_branches_live.top()) {
391 AddToWorklist(&*ii);
392 }
393 } break;
394 default: {
395 // Function calls, atomics, function params, function returns, etc.
396 // TODO(greg-lunarg): function calls live only if write to non-local
397 if (!ii->IsOpcodeSafeToDelete()) {
398 AddToWorklist(&*ii);
399 }
400 // Remember function calls
401 if (op == SpvOpFunctionCall) call_in_func_ = true;
402 } break;
403 }
404 }
405 }
406 // See if current function is an entry point
407 for (auto& ei : get_module()->entry_points()) {
408 if (ei.GetSingleWordInOperand(kEntryPointFunctionIdInIdx) ==
409 func->result_id()) {
410 func_is_entry_point_ = true;
411 break;
412 }
413 }
414 // If the current function is an entry point and has no function calls,
415 // we can optimize private variables as locals
416 private_like_local_ = func_is_entry_point_ && !call_in_func_;
417 // If privates are not like local, add their stores to worklist
418 if (!private_like_local_)
419 for (auto& ps : private_stores_) AddToWorklist(ps);
420 // Perform closure on live instruction set.
421 while (!worklist_.empty()) {
422 Instruction* liveInst = worklist_.front();
423 // Add all operand instructions if not already live
424 liveInst->ForEachInId([&liveInst, this](const uint32_t* iid) {
425 Instruction* inInst = get_def_use_mgr()->GetDef(*iid);
426 // Do not add label if an operand of a branch. This is not needed
427 // as part of live code discovery and can create false live code,
428 // for example, the branch to a header of a loop.
429 if (inInst->opcode() == SpvOpLabel && liveInst->IsBranch()) return;
430 AddToWorklist(inInst);
431 });
432 if (liveInst->type_id() != 0) {
433 AddToWorklist(get_def_use_mgr()->GetDef(liveInst->type_id()));
434 }
435 // If in a structured if or loop construct, add the controlling
436 // conditional branch and its merge.
437 BasicBlock* blk = context()->get_instr_block(liveInst);
438 Instruction* branchInst = block2headerBranch_[blk];
439 if (branchInst != nullptr) {
440 AddToWorklist(branchInst);
441 Instruction* mergeInst = branch2merge_[branchInst];
442 AddToWorklist(mergeInst);
443 }
444 // If the block is a header, add the next outermost controlling
445 // conditional branch and its merge.
446 Instruction* nextBranchInst = header2nextHeaderBranch_[blk];
447 if (nextBranchInst != nullptr) {
448 AddToWorklist(nextBranchInst);
449 Instruction* mergeInst = branch2merge_[nextBranchInst];
450 AddToWorklist(mergeInst);
451 }
452 // If local load, add all variable's stores if variable not already live
453 if (liveInst->opcode() == SpvOpLoad || liveInst->IsAtomicWithLoad()) {
454 uint32_t varId;
455 (void)GetPtr(liveInst, &varId);
456 if (varId != 0) {
457 ProcessLoad(varId);
458 }
459 // Process memory copies like loads
460 } else if (liveInst->opcode() == SpvOpCopyMemory ||
461 liveInst->opcode() == SpvOpCopyMemorySized) {
462 uint32_t varId;
463 (void)GetPtr(liveInst->GetSingleWordInOperand(kCopyMemorySourceAddrInIdx),
464 &varId);
465 if (varId != 0) {
466 ProcessLoad(varId);
467 }
468 // If merge, add other branches that are part of its control structure
469 } else if (liveInst->opcode() == SpvOpLoopMerge ||
470 liveInst->opcode() == SpvOpSelectionMerge) {
471 AddBreaksAndContinuesToWorklist(liveInst);
472 // If function call, treat as if it loads from all pointer arguments
473 } else if (liveInst->opcode() == SpvOpFunctionCall) {
474 liveInst->ForEachInId([this](const uint32_t* iid) {
475 // Skip non-ptr args
476 if (!IsPtr(*iid)) return;
477 uint32_t varId;
478 (void)GetPtr(*iid, &varId);
479 ProcessLoad(varId);
480 });
481 // If function parameter, treat as if it's result id is loaded from
482 } else if (liveInst->opcode() == SpvOpFunctionParameter) {
483 ProcessLoad(liveInst->result_id());
484 // We treat an OpImageTexelPointer as a load of the pointer, and
485 // that value is manipulated to get the result.
486 } else if (liveInst->opcode() == SpvOpImageTexelPointer) {
487 uint32_t varId;
488 (void)GetPtr(liveInst, &varId);
489 if (varId != 0) {
490 ProcessLoad(varId);
491 }
492 }
493
494 // Add OpDecorateId instructions that apply to this instruction to the work
495 // list. We use the decoration manager to look through the group
496 // decorations to get to the OpDecorate* instructions themselves.
497 auto decorations =
498 get_decoration_mgr()->GetDecorationsFor(liveInst->result_id(), false);
499 for (Instruction* dec : decorations) {
500 // We only care about OpDecorateId instructions because the are the only
501 // decorations that will reference an id that will have to be kept live
502 // because of that use.
503 if (dec->opcode() != SpvOpDecorateId) {
504 continue;
505 }
506 if (dec->GetSingleWordInOperand(1) ==
507 SpvDecorationHlslCounterBufferGOOGLE) {
508 // These decorations should not force the use id to be live. It will be
509 // removed if either the target or the in operand are dead.
510 continue;
511 }
512 AddToWorklist(dec);
513 }
514
515 worklist_.pop();
516 }
517
518 // Kill dead instructions and remember dead blocks
519 for (auto bi = structuredOrder.begin(); bi != structuredOrder.end();) {
520 uint32_t mergeBlockId = 0;
521 (*bi)->ForEachInst([this, &modified, &mergeBlockId](Instruction* inst) {
522 if (!IsDead(inst)) return;
523 if (inst->opcode() == SpvOpLabel) return;
524 // If dead instruction is selection merge, remember merge block
525 // for new branch at end of block
526 if (inst->opcode() == SpvOpSelectionMerge ||
527 inst->opcode() == SpvOpLoopMerge)
528 mergeBlockId = inst->GetSingleWordInOperand(0);
529 to_kill_.push_back(inst);
530 modified = true;
531 });
532 // If a structured if or loop was deleted, add a branch to its merge
533 // block, and traverse to the merge block and continue processing there.
534 // We know the block still exists because the label is not deleted.
535 if (mergeBlockId != 0) {
536 AddBranch(mergeBlockId, *bi);
537 for (++bi; (*bi)->id() != mergeBlockId; ++bi) {
538 }
539
540 auto merge_terminator = (*bi)->terminator();
541 if (merge_terminator->opcode() == SpvOpUnreachable) {
542 // The merge was unreachable. This is undefined behaviour so just
543 // return (or return an undef). Then mark the new return as live.
544 auto func_ret_type_inst = get_def_use_mgr()->GetDef(func->type_id());
545 if (func_ret_type_inst->opcode() == SpvOpTypeVoid) {
546 merge_terminator->SetOpcode(SpvOpReturn);
547 } else {
548 // Find an undef for the return value and make sure it gets kept by
549 // the pass.
550 auto undef_id = Type2Undef(func->type_id());
551 auto undef = get_def_use_mgr()->GetDef(undef_id);
552 live_insts_.Set(undef->unique_id());
553 merge_terminator->SetOpcode(SpvOpReturnValue);
554 merge_terminator->SetInOperands({{SPV_OPERAND_TYPE_ID, {undef_id}}});
555 get_def_use_mgr()->AnalyzeInstUse(merge_terminator);
556 }
557 live_insts_.Set(merge_terminator->unique_id());
558 }
559 } else {
560 ++bi;
561 }
562 }
563
564 return modified;
565}
566
567void AggressiveDCEPass::InitializeModuleScopeLiveInstructions() {
568 // Keep all execution modes.
569 for (auto& exec : get_module()->execution_modes()) {
570 AddToWorklist(&exec);
571 }
572 // Keep all entry points.
573 for (auto& entry : get_module()->entry_points()) {
574 if (get_module()->version() >= SPV_SPIRV_VERSION_WORD(1, 4)) {
575 // In SPIR-V 1.4 and later, entry points must list all global variables
576 // used. DCE can still remove non-input/output variables and update the
577 // interface list. Mark the entry point as live and inputs and outputs as
578 // live, but defer decisions all other interfaces.
579 live_insts_.Set(entry.unique_id());
580 // The actual function is live always.
581 AddToWorklist(
582 get_def_use_mgr()->GetDef(entry.GetSingleWordInOperand(1u)));
583 for (uint32_t i = 3; i < entry.NumInOperands(); ++i) {
584 auto* var = get_def_use_mgr()->GetDef(entry.GetSingleWordInOperand(i));
585 auto storage_class = var->GetSingleWordInOperand(0u);
586 if (storage_class == SpvStorageClassInput ||
587 storage_class == SpvStorageClassOutput) {
588 AddToWorklist(var);
589 }
590 }
591 } else {
592 AddToWorklist(&entry);
593 }
594 }
595 for (auto& anno : get_module()->annotations()) {
596 if (anno.opcode() == SpvOpDecorate) {
597 // Keep workgroup size.
598 if (anno.GetSingleWordInOperand(1u) == SpvDecorationBuiltIn &&
599 anno.GetSingleWordInOperand(2u) == SpvBuiltInWorkgroupSize) {
600 AddToWorklist(&anno);
601 }
602
603 if (context()->preserve_bindings()) {
604 // Keep all bindings.
605 if ((anno.GetSingleWordInOperand(1u) == SpvDecorationDescriptorSet) ||
606 (anno.GetSingleWordInOperand(1u) == SpvDecorationBinding)) {
607 AddToWorklist(&anno);
608 }
609 }
610
611 if (context()->preserve_spec_constants()) {
612 // Keep all specialization constant instructions
613 if (anno.GetSingleWordInOperand(1u) == SpvDecorationSpecId) {
614 AddToWorklist(&anno);
615 }
616 }
617 }
618 }
619}
620
621Pass::Status AggressiveDCEPass::ProcessImpl() {
622 // Current functionality assumes shader capability
623 // TODO(greg-lunarg): Handle additional capabilities
624 if (!context()->get_feature_mgr()->HasCapability(SpvCapabilityShader))
625 return Status::SuccessWithoutChange;
626
627 // Current functionality assumes relaxed logical addressing (see
628 // instruction.h)
629 // TODO(greg-lunarg): Handle non-logical addressing
630 if (context()->get_feature_mgr()->HasCapability(SpvCapabilityAddresses))
631 return Status::SuccessWithoutChange;
632
633 // The variable pointer extension is no longer needed to use the capability,
634 // so we have to look for the capability.
635 if (context()->get_feature_mgr()->HasCapability(
636 SpvCapabilityVariablePointersStorageBuffer))
637 return Status::SuccessWithoutChange;
638
639 // If any extensions in the module are not explicitly supported,
640 // return unmodified.
641 if (!AllExtensionsSupported()) return Status::SuccessWithoutChange;
642
643 // Eliminate Dead functions.
644 bool modified = EliminateDeadFunctions();
645
646 InitializeModuleScopeLiveInstructions();
647
648 // Process all entry point functions.
649 ProcessFunction pfn = [this](Function* fp) { return AggressiveDCE(fp); };
650 modified |= context()->ProcessEntryPointCallTree(pfn);
651
652 // If the decoration manager is kept live then the context will try to keep it
653 // up to date. ADCE deals with group decorations by changing the operands in
654 // |OpGroupDecorate| instruction directly without informing the decoration
655 // manager. This can put it in an invalid state which will cause an error
656 // when the context tries to update it. To avoid this problem invalidate
657 // the decoration manager upfront.
658 //
659 // We kill it at now because it is used when processing the entry point
660 // functions.
661 context()->InvalidateAnalyses(IRContext::Analysis::kAnalysisDecorations);
662
663 // Process module-level instructions. Now that all live instructions have
664 // been marked, it is safe to remove dead global values.
665 modified |= ProcessGlobalValues();
666
667 // Sanity check.
668 assert(to_kill_.size() == 0 || modified);
669
670 // Kill all dead instructions.
671 for (auto inst : to_kill_) {
672 context()->KillInst(inst);
673 }
674
675 // Cleanup all CFG including all unreachable blocks.
676 ProcessFunction cleanup = [this](Function* f) { return CFGCleanup(f); };
677 modified |= context()->ProcessEntryPointCallTree(cleanup);
678
679 return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
680}
681
682bool AggressiveDCEPass::EliminateDeadFunctions() {
683 // Identify live functions first. Those that are not live
684 // are dead. ADCE is disabled for non-shaders so we do not check for exported
685 // functions here.
686 std::unordered_set<const Function*> live_function_set;
687 ProcessFunction mark_live = [&live_function_set](Function* fp) {
688 live_function_set.insert(fp);
689 return false;
690 };
691 context()->ProcessEntryPointCallTree(mark_live);
692
693 bool modified = false;
694 for (auto funcIter = get_module()->begin();
695 funcIter != get_module()->end();) {
696 if (live_function_set.count(&*funcIter) == 0) {
697 modified = true;
698 EliminateFunction(&*funcIter);
699 funcIter = funcIter.Erase();
700 } else {
701 ++funcIter;
702 }
703 }
704
705 return modified;
706}
707
708void AggressiveDCEPass::EliminateFunction(Function* func) {
709 // Remove all of the instruction in the function body
710 func->ForEachInst([this](Instruction* inst) { context()->KillInst(inst); },
711 true);
712}
713
714bool AggressiveDCEPass::ProcessGlobalValues() {
715 // Remove debug and annotation statements referencing dead instructions.
716 // This must be done before killing the instructions, otherwise there are
717 // dead objects in the def/use database.
718 bool modified = false;
719 Instruction* instruction = &*get_module()->debug2_begin();
720 while (instruction) {
721 if (instruction->opcode() != SpvOpName) {
722 instruction = instruction->NextNode();
723 continue;
724 }
725
726 if (IsTargetDead(instruction)) {
727 instruction = context()->KillInst(instruction);
728 modified = true;
729 } else {
730 instruction = instruction->NextNode();
731 }
732 }
733
734 // This code removes all unnecessary decorations safely (see #1174). It also
735 // does so in a more efficient manner than deleting them only as the targets
736 // are deleted.
737 std::vector<Instruction*> annotations;
738 for (auto& inst : get_module()->annotations()) annotations.push_back(&inst);
739 std::sort(annotations.begin(), annotations.end(), DecorationLess());
740 for (auto annotation : annotations) {
741 switch (annotation->opcode()) {
742 case SpvOpDecorate:
743 case SpvOpMemberDecorate:
744 case SpvOpDecorateStringGOOGLE:
745 case SpvOpMemberDecorateStringGOOGLE:
746 if (IsTargetDead(annotation)) {
747 context()->KillInst(annotation);
748 modified = true;
749 }
750 break;
751 case SpvOpDecorateId:
752 if (IsTargetDead(annotation)) {
753 context()->KillInst(annotation);
754 modified = true;
755 } else {
756 if (annotation->GetSingleWordInOperand(1) ==
757 SpvDecorationHlslCounterBufferGOOGLE) {
758 // HlslCounterBuffer will reference an id other than the target.
759 // If that id is dead, then the decoration can be removed as well.
760 uint32_t counter_buffer_id = annotation->GetSingleWordInOperand(2);
761 Instruction* counter_buffer_inst =
762 get_def_use_mgr()->GetDef(counter_buffer_id);
763 if (IsDead(counter_buffer_inst)) {
764 context()->KillInst(annotation);
765 modified = true;
766 }
767 }
768 }
769 break;
770 case SpvOpGroupDecorate: {
771 // Go through the targets of this group decorate. Remove each dead
772 // target. If all targets are dead, remove this decoration.
773 bool dead = true;
774 bool removed_operand = false;
775 for (uint32_t i = 1; i < annotation->NumOperands();) {
776 Instruction* opInst =
777 get_def_use_mgr()->GetDef(annotation->GetSingleWordOperand(i));
778 if (IsDead(opInst)) {
779 // Don't increment |i|.
780 annotation->RemoveOperand(i);
781 modified = true;
782 removed_operand = true;
783 } else {
784 i++;
785 dead = false;
786 }
787 }
788 if (dead) {
789 context()->KillInst(annotation);
790 modified = true;
791 } else if (removed_operand) {
792 context()->UpdateDefUse(annotation);
793 }
794 break;
795 }
796 case SpvOpGroupMemberDecorate: {
797 // Go through the targets of this group member decorate. Remove each
798 // dead target (and member index). If all targets are dead, remove this
799 // decoration.
800 bool dead = true;
801 bool removed_operand = false;
802 for (uint32_t i = 1; i < annotation->NumOperands();) {
803 Instruction* opInst =
804 get_def_use_mgr()->GetDef(annotation->GetSingleWordOperand(i));
805 if (IsDead(opInst)) {
806 // Don't increment |i|.
807 annotation->RemoveOperand(i + 1);
808 annotation->RemoveOperand(i);
809 modified = true;
810 removed_operand = true;
811 } else {
812 i += 2;
813 dead = false;
814 }
815 }
816 if (dead) {
817 context()->KillInst(annotation);
818 modified = true;
819 } else if (removed_operand) {
820 context()->UpdateDefUse(annotation);
821 }
822 break;
823 }
824 case SpvOpDecorationGroup:
825 // By the time we hit decoration groups we've checked everything that
826 // can target them. So if they have no uses they must be dead.
827 if (get_def_use_mgr()->NumUsers(annotation) == 0) {
828 context()->KillInst(annotation);
829 modified = true;
830 }
831 break;
832 default:
833 assert(false);
834 break;
835 }
836 }
837
838 // Since ADCE is disabled for non-shaders, we don't check for export linkage
839 // attributes here.
840 for (auto& val : get_module()->types_values()) {
841 if (IsDead(&val)) {
842 // Save forwarded pointer if pointer is live since closure does not mark
843 // this live as it does not have a result id. This is a little too
844 // conservative since it is not known if the structure type that needed
845 // it is still live. TODO(greg-lunarg): Only save if needed.
846 if (val.opcode() == SpvOpTypeForwardPointer) {
847 uint32_t ptr_ty_id = val.GetSingleWordInOperand(0);
848 Instruction* ptr_ty_inst = get_def_use_mgr()->GetDef(ptr_ty_id);
849 if (!IsDead(ptr_ty_inst)) continue;
850 }
851 to_kill_.push_back(&val);
852 modified = true;
853 }
854 }
855
856 if (get_module()->version() >= SPV_SPIRV_VERSION_WORD(1, 4)) {
857 // Remove the dead interface variables from the entry point interface list.
858 for (auto& entry : get_module()->entry_points()) {
859 std::vector<Operand> new_operands;
860 for (uint32_t i = 0; i < entry.NumInOperands(); ++i) {
861 if (i < 3) {
862 // Execution model, function id and name are always valid.
863 new_operands.push_back(entry.GetInOperand(i));
864 } else {
865 auto* var =
866 get_def_use_mgr()->GetDef(entry.GetSingleWordInOperand(i));
867 if (!IsDead(var)) {
868 new_operands.push_back(entry.GetInOperand(i));
869 }
870 }
871 }
872 if (new_operands.size() != entry.NumInOperands()) {
873 entry.SetInOperands(std::move(new_operands));
874 get_def_use_mgr()->UpdateDefUse(&entry);
875 }
876 }
877 }
878
879 return modified;
880}
881
882AggressiveDCEPass::AggressiveDCEPass() = default;
883
884Pass::Status AggressiveDCEPass::Process() {
885 // Initialize extensions whitelist
886 InitExtensions();
887 return ProcessImpl();
888}
889
890void AggressiveDCEPass::InitExtensions() {
891 extensions_whitelist_.clear();
892 extensions_whitelist_.insert({
893 "SPV_AMD_shader_explicit_vertex_parameter",
894 "SPV_AMD_shader_trinary_minmax",
895 "SPV_AMD_gcn_shader",
896 "SPV_KHR_shader_ballot",
897 "SPV_AMD_shader_ballot",
898 "SPV_AMD_gpu_shader_half_float",
899 "SPV_KHR_shader_draw_parameters",
900 "SPV_KHR_subgroup_vote",
901 "SPV_KHR_16bit_storage",
902 "SPV_KHR_device_group",
903 "SPV_KHR_multiview",
904 "SPV_NVX_multiview_per_view_attributes",
905 "SPV_NV_viewport_array2",
906 "SPV_NV_stereo_view_rendering",
907 "SPV_NV_sample_mask_override_coverage",
908 "SPV_NV_geometry_shader_passthrough",
909 "SPV_AMD_texture_gather_bias_lod",
910 "SPV_KHR_storage_buffer_storage_class",
911 // SPV_KHR_variable_pointers
912 // Currently do not support extended pointer expressions
913 "SPV_AMD_gpu_shader_int16",
914 "SPV_KHR_post_depth_coverage",
915 "SPV_KHR_shader_atomic_counter_ops",
916 "SPV_EXT_shader_stencil_export",
917 "SPV_EXT_shader_viewport_index_layer",
918 "SPV_AMD_shader_image_load_store_lod",
919 "SPV_AMD_shader_fragment_mask",
920 "SPV_EXT_fragment_fully_covered",
921 "SPV_AMD_gpu_shader_half_float_fetch",
922 "SPV_GOOGLE_decorate_string",
923 "SPV_GOOGLE_hlsl_functionality1",
924 "SPV_GOOGLE_user_type",
925 "SPV_NV_shader_subgroup_partitioned",
926 "SPV_EXT_demote_to_helper_invocation",
927 "SPV_EXT_descriptor_indexing",
928 "SPV_NV_fragment_shader_barycentric",
929 "SPV_NV_compute_shader_derivatives",
930 "SPV_NV_shader_image_footprint",
931 "SPV_NV_shading_rate",
932 "SPV_NV_mesh_shader",
933 "SPV_NV_ray_tracing",
934 "SPV_KHR_ray_tracing",
935 "SPV_EXT_fragment_invocation_density",
936 "SPV_EXT_physical_storage_buffer",
937 });
938}
939
940} // namespace opt
941} // namespace spvtools
942