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 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 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
