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