1 // Copyright (c) 2017 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 #include "source/opt/dead_variable_elimination.h"
16
17 #include <vector>
18
19 #include "source/opt/ir_context.h"
20 #include "source/opt/reflect.h"
21
22 namespace spvtools {
23 namespace opt {
24
25 // This optimization removes global variables that are not needed because they
26 // are definitely not accessed.
Process()27 Pass::Status DeadVariableElimination::Process() {
28 // The algorithm will compute the reference count for every global variable.
29 // Anything with a reference count of 0 will then be deleted. For variables
30 // that might have references that are not explicit in this context, we use
31 // the value kMustKeep as the reference count.
32 std::vector<uint32_t> ids_to_remove;
33
34 // Get the reference count for all of the global OpVariable instructions.
35 for (auto& inst : context()->types_values()) {
36 if (inst.opcode() != SpvOp::SpvOpVariable) {
37 continue;
38 }
39
40 size_t count = 0;
41 uint32_t result_id = inst.result_id();
42
43 // Check the linkage. If it is exported, it could be reference somewhere
44 // else, so we must keep the variable around.
45 get_decoration_mgr()->ForEachDecoration(
46 result_id, SpvDecorationLinkageAttributes,
47 [&count](const Instruction& linkage_instruction) {
48 uint32_t last_operand = linkage_instruction.NumOperands() - 1;
49 if (linkage_instruction.GetSingleWordOperand(last_operand) ==
50 SpvLinkageTypeExport) {
51 count = kMustKeep;
52 }
53 });
54
55 if (count != kMustKeep) {
56 // If we don't have to keep the instruction for other reasons, then look
57 // at the uses and count the number of real references.
58 count = 0;
59 get_def_use_mgr()->ForEachUser(result_id, [&count](Instruction* user) {
60 if (!IsAnnotationInst(user->opcode()) && user->opcode() != SpvOpName) {
61 ++count;
62 }
63 });
64 }
65 reference_count_[result_id] = count;
66 if (count == 0) {
67 ids_to_remove.push_back(result_id);
68 }
69 }
70
71 // Remove all of the variables that have a reference count of 0.
72 bool modified = false;
73 if (!ids_to_remove.empty()) {
74 modified = true;
75 for (auto result_id : ids_to_remove) {
76 DeleteVariable(result_id);
77 }
78 }
79 return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
80 }
81
DeleteVariable(uint32_t result_id)82 void DeadVariableElimination::DeleteVariable(uint32_t result_id) {
83 Instruction* inst = get_def_use_mgr()->GetDef(result_id);
84 assert(inst->opcode() == SpvOpVariable &&
85 "Should not be trying to delete anything other than an OpVariable.");
86
87 // Look for an initializer that references another variable. We need to know
88 // if that variable can be deleted after the reference is removed.
89 if (inst->NumOperands() == 4) {
90 Instruction* initializer =
91 get_def_use_mgr()->GetDef(inst->GetSingleWordOperand(3));
92
93 // TODO: Handle OpSpecConstantOP which might be defined in terms of other
94 // variables. Will probably require a unified dead code pass that does all
95 // instruction types. (Issue 906)
96 if (initializer->opcode() == SpvOpVariable) {
97 uint32_t initializer_id = initializer->result_id();
98 size_t& count = reference_count_[initializer_id];
99 if (count != kMustKeep) {
100 --count;
101 }
102
103 if (count == 0) {
104 DeleteVariable(initializer_id);
105 }
106 }
107 }
108 context()->KillDef(result_id);
109 }
110 } // namespace opt
111 } // namespace spvtools
112