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