1 // Copyright (c) 2018 Google LLC
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/simplification_pass.h"
16
17 #include <set>
18 #include <unordered_set>
19 #include <vector>
20
21 #include "source/opt/fold.h"
22
23 namespace spvtools {
24 namespace opt {
25
Process()26 Pass::Status SimplificationPass::Process() {
27 bool modified = false;
28
29 for (Function& function : *get_module()) {
30 modified |= SimplifyFunction(&function);
31 }
32 return (modified ? Status::SuccessWithChange : Status::SuccessWithoutChange);
33 }
34
AddNewOperands(Instruction * folded_inst,std::unordered_set<Instruction * > * inst_seen,std::vector<Instruction * > * work_list)35 void SimplificationPass::AddNewOperands(
36 Instruction* folded_inst, std::unordered_set<Instruction*>* inst_seen,
37 std::vector<Instruction*>* work_list) {
38 analysis::DefUseManager* def_use_mgr = get_def_use_mgr();
39 folded_inst->ForEachInId(
40 [&inst_seen, &def_use_mgr, &work_list](uint32_t* iid) {
41 Instruction* iid_inst = def_use_mgr->GetDef(*iid);
42 if (!inst_seen->insert(iid_inst).second) return;
43 work_list->push_back(iid_inst);
44 });
45 }
46
SimplifyFunction(Function * function)47 bool SimplificationPass::SimplifyFunction(Function* function) {
48 if (function->IsDeclaration()) {
49 return false;
50 }
51
52 bool modified = false;
53 // Phase 1: Traverse all instructions in dominance order.
54 // The second phase will only be on the instructions whose inputs have changed
55 // after being processed during phase 1. Since OpPhi instructions are the
56 // only instructions whose inputs do not necessarily dominate the use, we keep
57 // track of the OpPhi instructions already seen, and add them to the work list
58 // for phase 2 when needed.
59 std::vector<Instruction*> work_list;
60 std::unordered_set<Instruction*> process_phis;
61 std::unordered_set<Instruction*> inst_to_kill;
62 std::unordered_set<Instruction*> in_work_list;
63 std::unordered_set<Instruction*> inst_seen;
64 const InstructionFolder& folder = context()->get_instruction_folder();
65
66 cfg()->ForEachBlockInReversePostOrder(
67 function->entry().get(),
68 [&modified, &process_phis, &work_list, &in_work_list, &inst_to_kill,
69 &folder, &inst_seen, this](BasicBlock* bb) {
70 for (Instruction* inst = &*bb->begin(); inst; inst = inst->NextNode()) {
71 inst_seen.insert(inst);
72 if (inst->opcode() == SpvOpPhi) {
73 process_phis.insert(inst);
74 }
75
76 bool is_foldable_copy =
77 inst->opcode() == SpvOpCopyObject &&
78 context()->get_decoration_mgr()->HaveSubsetOfDecorations(
79 inst->result_id(), inst->GetSingleWordInOperand(0));
80
81 if (is_foldable_copy || folder.FoldInstruction(inst)) {
82 modified = true;
83 context()->AnalyzeUses(inst);
84 get_def_use_mgr()->ForEachUser(inst, [&work_list, &process_phis,
85 &in_work_list](
86 Instruction* use) {
87 if (process_phis.count(use) && in_work_list.insert(use).second) {
88 work_list.push_back(use);
89 }
90 });
91
92 AddNewOperands(inst, &inst_seen, &work_list);
93
94 if (inst->opcode() == SpvOpCopyObject) {
95 context()->ReplaceAllUsesWithPredicate(
96 inst->result_id(), inst->GetSingleWordInOperand(0),
97 [](Instruction* user) {
98 const auto opcode = user->opcode();
99 if (!spvOpcodeIsDebug(opcode) &&
100 !spvOpcodeIsDecoration(opcode)) {
101 return true;
102 }
103 return false;
104 });
105 inst_to_kill.insert(inst);
106 in_work_list.insert(inst);
107 } else if (inst->opcode() == SpvOpNop) {
108 inst_to_kill.insert(inst);
109 in_work_list.insert(inst);
110 }
111 }
112 }
113 });
114
115 // Phase 2: process the instructions in the work list until all of the work is
116 // done. This time we add all users to the work list because phase 1
117 // has already finished.
118 for (size_t i = 0; i < work_list.size(); ++i) {
119 Instruction* inst = work_list[i];
120 in_work_list.erase(inst);
121 inst_seen.insert(inst);
122
123 bool is_foldable_copy =
124 inst->opcode() == SpvOpCopyObject &&
125 context()->get_decoration_mgr()->HaveSubsetOfDecorations(
126 inst->result_id(), inst->GetSingleWordInOperand(0));
127
128 if (is_foldable_copy || folder.FoldInstruction(inst)) {
129 modified = true;
130 context()->AnalyzeUses(inst);
131 get_def_use_mgr()->ForEachUser(
132 inst, [&work_list, &in_work_list](Instruction* use) {
133 if (!use->IsDecoration() && use->opcode() != SpvOpName &&
134 in_work_list.insert(use).second) {
135 work_list.push_back(use);
136 }
137 });
138
139 AddNewOperands(inst, &inst_seen, &work_list);
140
141 if (inst->opcode() == SpvOpCopyObject) {
142 context()->ReplaceAllUsesWithPredicate(
143 inst->result_id(), inst->GetSingleWordInOperand(0),
144 [](Instruction* user) {
145 const auto opcode = user->opcode();
146 if (!spvOpcodeIsDebug(opcode) && !spvOpcodeIsDecoration(opcode)) {
147 return true;
148 }
149 return false;
150 });
151 inst_to_kill.insert(inst);
152 in_work_list.insert(inst);
153 } else if (inst->opcode() == SpvOpNop) {
154 inst_to_kill.insert(inst);
155 in_work_list.insert(inst);
156 }
157 }
158 }
159
160 // Phase 3: Kill instructions we know are no longer needed.
161 for (Instruction* inst : inst_to_kill) {
162 context()->KillInst(inst);
163 }
164
165 return modified;
166 }
167
168 } // namespace opt
169 } // namespace spvtools
170