1 | // Copyright (c) 2017 The Khronos Group Inc. |
2 | // Copyright (c) 2017 Valve Corporation |
3 | // Copyright (c) 2017 LunarG Inc. |
4 | // Copyright (c) 2019 Google LLC |
5 | // |
6 | // Licensed under the Apache License, Version 2.0 (the "License"); |
7 | // you may not use this file except in compliance with the License. |
8 | // You may obtain a copy of the License at |
9 | // |
10 | // http://www.apache.org/licenses/LICENSE-2.0 |
11 | // |
12 | // Unless required by applicable law or agreed to in writing, software |
13 | // distributed under the License is distributed on an "AS IS" BASIS, |
14 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
15 | // See the License for the specific language governing permissions and |
16 | // limitations under the License. |
17 | |
18 | #include "block_merge_util.h" |
19 | |
20 | namespace spvtools { |
21 | namespace opt { |
22 | namespace blockmergeutil { |
23 | |
24 | namespace { |
25 | |
26 | // Returns true if |block| contains a merge instruction. |
27 | bool (BasicBlock* block) { return block->GetMergeInst() != nullptr; } |
28 | |
29 | // Returns true if |id| contains a merge instruction. |
30 | bool (IRContext* context, uint32_t id) { |
31 | return IsHeader( |
32 | context->get_instr_block(context->get_def_use_mgr()->GetDef(id))); |
33 | } |
34 | |
35 | // Returns true if |id| is the merge target of a merge instruction. |
36 | bool IsMerge(IRContext* context, uint32_t id) { |
37 | return !context->get_def_use_mgr()->WhileEachUse(id, [](Instruction* user, |
38 | uint32_t index) { |
39 | SpvOp op = user->opcode(); |
40 | if ((op == SpvOpLoopMerge || op == SpvOpSelectionMerge) && index == 0u) { |
41 | return false; |
42 | } |
43 | return true; |
44 | }); |
45 | } |
46 | |
47 | // Returns true if |block| is the merge target of a merge instruction. |
48 | bool IsMerge(IRContext* context, BasicBlock* block) { |
49 | return IsMerge(context, block->id()); |
50 | } |
51 | |
52 | // Returns true if |id| is the continue target of a merge instruction. |
53 | bool IsContinue(IRContext* context, uint32_t id) { |
54 | return !context->get_def_use_mgr()->WhileEachUse( |
55 | id, [](Instruction* user, uint32_t index) { |
56 | SpvOp op = user->opcode(); |
57 | if (op == SpvOpLoopMerge && index == 1u) { |
58 | return false; |
59 | } |
60 | return true; |
61 | }); |
62 | } |
63 | |
64 | // Removes any OpPhi instructions in |block|, which should have exactly one |
65 | // predecessor, replacing uses of OpPhi ids with the ids associated with the |
66 | // predecessor. |
67 | void EliminateOpPhiInstructions(IRContext* context, BasicBlock* block) { |
68 | block->ForEachPhiInst([context](Instruction* phi) { |
69 | assert(2 == phi->NumInOperands() && |
70 | "A block can only have one predecessor for block merging to make " |
71 | "sense." ); |
72 | context->ReplaceAllUsesWith(phi->result_id(), |
73 | phi->GetSingleWordInOperand(0)); |
74 | context->KillInst(phi); |
75 | }); |
76 | } |
77 | |
78 | } // Anonymous namespace |
79 | |
80 | bool CanMergeWithSuccessor(IRContext* context, BasicBlock* block) { |
81 | // Find block with single successor which has no other predecessors. |
82 | auto ii = block->end(); |
83 | --ii; |
84 | Instruction* br = &*ii; |
85 | if (br->opcode() != SpvOpBranch) { |
86 | return false; |
87 | } |
88 | |
89 | const uint32_t lab_id = br->GetSingleWordInOperand(0); |
90 | if (context->cfg()->preds(lab_id).size() != 1) { |
91 | return false; |
92 | } |
93 | |
94 | bool pred_is_merge = IsMerge(context, block); |
95 | bool succ_is_merge = IsMerge(context, lab_id); |
96 | if (pred_is_merge && succ_is_merge) { |
97 | // Cannot merge two merges together. |
98 | return false; |
99 | } |
100 | |
101 | if (pred_is_merge && IsContinue(context, lab_id)) { |
102 | // Cannot merge a continue target with a merge block. |
103 | return false; |
104 | } |
105 | |
106 | // Don't bother trying to merge unreachable blocks. |
107 | if (auto dominators = context->GetDominatorAnalysis(block->GetParent())) { |
108 | if (!dominators->IsReachable(block)) return false; |
109 | } |
110 | |
111 | Instruction* merge_inst = block->GetMergeInst(); |
112 | const bool = IsHeader(block); |
113 | if (pred_is_header && lab_id != merge_inst->GetSingleWordInOperand(0u)) { |
114 | bool = IsHeader(context, lab_id); |
115 | if (pred_is_header && succ_is_header) { |
116 | // Cannot merge two headers together when the successor is not the merge |
117 | // block of the predecessor. |
118 | return false; |
119 | } |
120 | |
121 | // If this is a header block and the successor is not its merge, we must |
122 | // be careful about which blocks we are willing to merge together. |
123 | // OpLoopMerge must be followed by a conditional or unconditional branch. |
124 | // The merge must be a loop merge because a selection merge cannot be |
125 | // followed by an unconditional branch. |
126 | BasicBlock* succ_block = context->get_instr_block(lab_id); |
127 | SpvOp succ_term_op = succ_block->terminator()->opcode(); |
128 | assert(merge_inst->opcode() == SpvOpLoopMerge); |
129 | if (succ_term_op != SpvOpBranch && succ_term_op != SpvOpBranchConditional) { |
130 | return false; |
131 | } |
132 | } |
133 | return true; |
134 | } |
135 | |
136 | void MergeWithSuccessor(IRContext* context, Function* func, |
137 | Function::iterator bi) { |
138 | assert(CanMergeWithSuccessor(context, &*bi) && |
139 | "Precondition failure for MergeWithSuccessor: it must be legal to " |
140 | "merge the block and its successor." ); |
141 | |
142 | auto ii = bi->end(); |
143 | --ii; |
144 | Instruction* br = &*ii; |
145 | const uint32_t lab_id = br->GetSingleWordInOperand(0); |
146 | Instruction* merge_inst = bi->GetMergeInst(); |
147 | bool = IsHeader(&*bi); |
148 | |
149 | // Merge blocks. |
150 | context->KillInst(br); |
151 | auto sbi = bi; |
152 | for (; sbi != func->end(); ++sbi) |
153 | if (sbi->id() == lab_id) break; |
154 | // If bi is sbi's only predecessor, it dominates sbi and thus |
155 | // sbi must follow bi in func's ordering. |
156 | assert(sbi != func->end()); |
157 | |
158 | // Update the inst-to-block mapping for the instructions in sbi. |
159 | for (auto& inst : *sbi) { |
160 | context->set_instr_block(&inst, &*bi); |
161 | } |
162 | |
163 | EliminateOpPhiInstructions(context, &*sbi); |
164 | |
165 | // Now actually move the instructions. |
166 | bi->AddInstructions(&*sbi); |
167 | |
168 | if (merge_inst) { |
169 | if (pred_is_header && lab_id == merge_inst->GetSingleWordInOperand(0u)) { |
170 | // Merging the header and merge blocks, so remove the structured control |
171 | // flow declaration. |
172 | context->KillInst(merge_inst); |
173 | } else { |
174 | // Move OpLine/OpNoLine information to merge_inst. This solves |
175 | // the validation error that OpLine is placed between OpLoopMerge |
176 | // and OpBranchConditional. |
177 | auto terminator = bi->terminator(); |
178 | auto& vec = terminator->dbg_line_insts(); |
179 | auto& new_vec = merge_inst->dbg_line_insts(); |
180 | new_vec.insert(new_vec.end(), vec.begin(), vec.end()); |
181 | terminator->clear_dbg_line_insts(); |
182 | |
183 | // Move the merge instruction to just before the terminator. |
184 | merge_inst->InsertBefore(terminator); |
185 | } |
186 | } |
187 | context->ReplaceAllUsesWith(lab_id, bi->id()); |
188 | context->KillInst(sbi->GetLabelInst()); |
189 | (void)sbi.Erase(); |
190 | } |
191 | |
192 | } // namespace blockmergeutil |
193 | } // namespace opt |
194 | } // namespace spvtools |
195 | |