1 // Copyright (c) 2017 The Khronos Group Inc. 2 // Copyright (c) 2017 Valve Corporation 3 // Copyright (c) 2017 LunarG Inc. 4 // 5 // Licensed under the Apache License, Version 2.0 (the "License"); 6 // you may not use this file except in compliance with the License. 7 // You may obtain a copy of the License at 8 // 9 // http://www.apache.org/licenses/LICENSE-2.0 10 // 11 // Unless required by applicable law or agreed to in writing, software 12 // distributed under the License is distributed on an "AS IS" BASIS, 13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 // See the License for the specific language governing permissions and 15 // limitations under the License. 16 17 #include "block_merge_pass.h" 18 19 #include "iterator.h" 20 21 namespace spvtools { 22 namespace opt { 23 24 namespace { 25 26 const int kEntryPointFunctionIdInIdx = 1; 27 28 } // anonymous namespace 29 IsLoopHeader(ir::BasicBlock * block_ptr)30bool BlockMergePass::IsLoopHeader(ir::BasicBlock* block_ptr) { 31 auto iItr = block_ptr->tail(); 32 if (iItr == block_ptr->begin()) 33 return false; 34 --iItr; 35 return iItr->opcode() == SpvOpLoopMerge; 36 } 37 HasMultipleRefs(uint32_t labId)38bool BlockMergePass::HasMultipleRefs(uint32_t labId) { 39 const analysis::UseList* uses = def_use_mgr_->GetUses(labId); 40 int rcnt = 0; 41 for (const auto u : *uses) { 42 // Don't count OpName 43 if (u.inst->opcode() == SpvOpName) 44 continue; 45 if (rcnt == 1) 46 return true; 47 ++rcnt; 48 } 49 return false; 50 } 51 KillInstAndName(ir::Instruction * inst)52void BlockMergePass::KillInstAndName(ir::Instruction* inst) { 53 const uint32_t id = inst->result_id(); 54 if (id != 0) { 55 analysis::UseList* uses = def_use_mgr_->GetUses(id); 56 if (uses != nullptr) 57 for (auto u : *uses) 58 if (u.inst->opcode() == SpvOpName) { 59 def_use_mgr_->KillInst(u.inst); 60 break; 61 } 62 } 63 def_use_mgr_->KillInst(inst); 64 } 65 MergeBlocks(ir::Function * func)66bool BlockMergePass::MergeBlocks(ir::Function* func) { 67 bool modified = false; 68 for (auto bi = func->begin(); bi != func->end(); ) { 69 // Do not merge loop header blocks, at least for now. 70 if (IsLoopHeader(&*bi)) { 71 ++bi; 72 continue; 73 } 74 // Find block with single successor which has no other predecessors. 75 // Continue and Merge blocks are currently ruled out as second blocks. 76 // Happily any such candidate blocks will have >1 uses due to their 77 // LoopMerge instruction. 78 // TODO(): Deal with phi instructions that reference the 79 // second block. Happily, these references currently inhibit 80 // the merge. 81 auto ii = bi->end(); 82 --ii; 83 ir::Instruction* br = &*ii; 84 if (br->opcode() != SpvOpBranch) { 85 ++bi; 86 continue; 87 } 88 const uint32_t labId = br->GetSingleWordInOperand(0); 89 if (HasMultipleRefs(labId)) { 90 ++bi; 91 continue; 92 } 93 // Merge blocks 94 def_use_mgr_->KillInst(br); 95 auto sbi = bi; 96 for (; sbi != func->end(); ++sbi) 97 if (sbi->id() == labId) 98 break; 99 // If bi is sbi's only predecessor, it dominates sbi and thus 100 // sbi must follow bi in func's ordering. 101 assert(sbi != func->end()); 102 bi->AddInstructions(&*sbi); 103 KillInstAndName(sbi->GetLabelInst()); 104 (void) sbi.Erase(); 105 // reprocess block 106 modified = true; 107 } 108 return modified; 109 } 110 Initialize(ir::Module * module)111void BlockMergePass::Initialize(ir::Module* module) { 112 113 module_ = module; 114 115 // Initialize function and block maps 116 id2function_.clear(); 117 for (auto& fn : *module_) 118 id2function_[fn.result_id()] = &fn; 119 120 def_use_mgr_.reset(new analysis::DefUseManager(consumer(), module_)); 121 }; 122 ProcessImpl()123Pass::Status BlockMergePass::ProcessImpl() { 124 bool modified = false; 125 for (auto& e : module_->entry_points()) { 126 ir::Function* fn = 127 id2function_[e.GetSingleWordInOperand(kEntryPointFunctionIdInIdx)]; 128 modified = MergeBlocks(fn) || modified; 129 } 130 return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange; 131 } 132 BlockMergePass()133BlockMergePass::BlockMergePass() 134 : module_(nullptr), def_use_mgr_(nullptr) {} 135 Process(ir::Module * module)136Pass::Status BlockMergePass::Process(ir::Module* module) { 137 Initialize(module); 138 return ProcessImpl(); 139 } 140 141 } // namespace opt 142 } // namespace spvtools 143 144