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 "source/opt/block_merge_pass.h"
18
19 #include <vector>
20
21 #include "source/opt/ir_context.h"
22 #include "source/opt/iterator.h"
23
24 namespace spvtools {
25 namespace opt {
26
MergeBlocks(Function * func)27 bool BlockMergePass::MergeBlocks(Function* func) {
28 bool modified = false;
29 for (auto bi = func->begin(); bi != func->end();) {
30 // Find block with single successor which has no other predecessors.
31 auto ii = bi->end();
32 --ii;
33 Instruction* br = &*ii;
34 if (br->opcode() != SpvOpBranch) {
35 ++bi;
36 continue;
37 }
38
39 const uint32_t lab_id = br->GetSingleWordInOperand(0);
40 if (cfg()->preds(lab_id).size() != 1) {
41 ++bi;
42 continue;
43 }
44
45 bool pred_is_merge = IsMerge(&*bi);
46 bool succ_is_merge = IsMerge(lab_id);
47 if (pred_is_merge && succ_is_merge) {
48 // Cannot merge two merges together.
49 ++bi;
50 continue;
51 }
52
53 Instruction* merge_inst = bi->GetMergeInst();
54 bool pred_is_header = IsHeader(&*bi);
55 if (pred_is_header && lab_id != merge_inst->GetSingleWordInOperand(0u)) {
56 bool succ_is_header = IsHeader(lab_id);
57 if (pred_is_header && succ_is_header) {
58 // Cannot merge two headers together when the successor is not the merge
59 // block of the predecessor.
60 ++bi;
61 continue;
62 }
63
64 // If this is a header block and the successor is not its merge, we must
65 // be careful about which blocks we are willing to merge together.
66 // OpLoopMerge must be followed by a conditional or unconditional branch.
67 // The merge must be a loop merge because a selection merge cannot be
68 // followed by an unconditional branch.
69 BasicBlock* succ_block = context()->get_instr_block(lab_id);
70 SpvOp succ_term_op = succ_block->terminator()->opcode();
71 assert(merge_inst->opcode() == SpvOpLoopMerge);
72 if (succ_term_op != SpvOpBranch &&
73 succ_term_op != SpvOpBranchConditional) {
74 ++bi;
75 continue;
76 }
77 }
78
79 // Merge blocks.
80 context()->KillInst(br);
81 auto sbi = bi;
82 for (; sbi != func->end(); ++sbi)
83 if (sbi->id() == lab_id) break;
84 // If bi is sbi's only predecessor, it dominates sbi and thus
85 // sbi must follow bi in func's ordering.
86 assert(sbi != func->end());
87
88 // Update the inst-to-block mapping for the instructions in sbi.
89 for (auto& inst : *sbi) {
90 context()->set_instr_block(&inst, &*bi);
91 }
92
93 // Now actually move the instructions.
94 bi->AddInstructions(&*sbi);
95
96 if (merge_inst) {
97 if (pred_is_header && lab_id == merge_inst->GetSingleWordInOperand(0u)) {
98 // Merging the header and merge blocks, so remove the structured control
99 // flow declaration.
100 context()->KillInst(merge_inst);
101 } else {
102 // Move the merge instruction to just before the terminator.
103 merge_inst->InsertBefore(bi->terminator());
104 }
105 }
106 context()->ReplaceAllUsesWith(lab_id, bi->id());
107 context()->KillInst(sbi->GetLabelInst());
108 (void)sbi.Erase();
109 // Reprocess block.
110 modified = true;
111 }
112 return modified;
113 }
114
IsHeader(BasicBlock * block)115 bool BlockMergePass::IsHeader(BasicBlock* block) {
116 return block->GetMergeInst() != nullptr;
117 }
118
IsHeader(uint32_t id)119 bool BlockMergePass::IsHeader(uint32_t id) {
120 return IsHeader(context()->get_instr_block(get_def_use_mgr()->GetDef(id)));
121 }
122
IsMerge(uint32_t id)123 bool BlockMergePass::IsMerge(uint32_t id) {
124 return !get_def_use_mgr()->WhileEachUse(id, [](Instruction* user,
125 uint32_t index) {
126 SpvOp op = user->opcode();
127 if ((op == SpvOpLoopMerge || op == SpvOpSelectionMerge) && index == 0u) {
128 return false;
129 }
130 return true;
131 });
132 }
133
IsMerge(BasicBlock * block)134 bool BlockMergePass::IsMerge(BasicBlock* block) { return IsMerge(block->id()); }
135
Process()136 Pass::Status BlockMergePass::Process() {
137 // Process all entry point functions.
138 ProcessFunction pfn = [this](Function* fp) { return MergeBlocks(fp); };
139 bool modified = context()->ProcessEntryPointCallTree(pfn);
140 return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
141 }
142
143 BlockMergePass::BlockMergePass() = default;
144
145 } // namespace opt
146 } // namespace spvtools
147