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