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
SimplifyFunction(Function * function)35 bool SimplificationPass::SimplifyFunction(Function* function) {
36 bool modified = false;
37 // Phase 1: Traverse all instructions in dominance order.
38 // The second phase will only be on the instructions whose inputs have changed
39 // after being processed during phase 1. Since OpPhi instructions are the
40 // only instructions whose inputs do not necessarily dominate the use, we keep
41 // track of the OpPhi instructions already seen, and add them to the work list
42 // for phase 2 when needed.
43 std::vector<Instruction*> work_list;
44 std::unordered_set<Instruction*> process_phis;
45 std::unordered_set<Instruction*> inst_to_kill;
46 std::unordered_set<Instruction*> in_work_list;
47 const InstructionFolder& folder = context()->get_instruction_folder();
48
49 cfg()->ForEachBlockInReversePostOrder(
50 function->entry().get(),
51 [&modified, &process_phis, &work_list, &in_work_list, &inst_to_kill,
52 folder, this](BasicBlock* bb) {
53 for (Instruction* inst = &*bb->begin(); inst; inst = inst->NextNode()) {
54 if (inst->opcode() == SpvOpPhi) {
55 process_phis.insert(inst);
56 }
57
58 if (inst->opcode() == SpvOpCopyObject ||
59 folder.FoldInstruction(inst)) {
60 modified = true;
61 context()->AnalyzeUses(inst);
62 get_def_use_mgr()->ForEachUser(inst, [&work_list, &process_phis,
63 &in_work_list](
64 Instruction* use) {
65 if (process_phis.count(use) && in_work_list.insert(use).second) {
66 work_list.push_back(use);
67 }
68 });
69 if (inst->opcode() == SpvOpCopyObject) {
70 context()->ReplaceAllUsesWith(inst->result_id(),
71 inst->GetSingleWordInOperand(0));
72 inst_to_kill.insert(inst);
73 in_work_list.insert(inst);
74 } else if (inst->opcode() == SpvOpNop) {
75 inst_to_kill.insert(inst);
76 in_work_list.insert(inst);
77 }
78 }
79 }
80 });
81
82 // Phase 2: process the instructions in the work list until all of the work is
83 // done. This time we add all users to the work list because phase 1
84 // has already finished.
85 for (size_t i = 0; i < work_list.size(); ++i) {
86 Instruction* inst = work_list[i];
87 in_work_list.erase(inst);
88 if (inst->opcode() == SpvOpCopyObject || folder.FoldInstruction(inst)) {
89 modified = true;
90 context()->AnalyzeUses(inst);
91 get_def_use_mgr()->ForEachUser(
92 inst, [&work_list, &in_work_list](Instruction* use) {
93 if (!use->IsDecoration() && use->opcode() != SpvOpName &&
94 in_work_list.insert(use).second) {
95 work_list.push_back(use);
96 }
97 });
98
99 if (inst->opcode() == SpvOpCopyObject) {
100 context()->ReplaceAllUsesWith(inst->result_id(),
101 inst->GetSingleWordInOperand(0));
102 inst_to_kill.insert(inst);
103 in_work_list.insert(inst);
104 } else if (inst->opcode() == SpvOpNop) {
105 inst_to_kill.insert(inst);
106 in_work_list.insert(inst);
107 }
108 }
109 }
110
111 // Phase 3: Kill instructions we know are no longer needed.
112 for (Instruction* inst : inst_to_kill) {
113 context()->KillInst(inst);
114 }
115
116 return modified;
117 }
118
119 } // namespace opt
120 } // namespace spvtools
121