| 1 |
// Copyright (c) 2017 The Khronos Group Inc. |
| 2 |
// Copyright (c) 2017 Valve Corporation |
| 3 |
// Copyright (c) 2017 LunarG Inc. |
| 4 |
// Copyright (c) 2018 Google Inc. |
| 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 "source/opt/dead_branch_elim_pass.h" |
| 19 |
|
| 20 |
#include <list> |
| 21 |
#include <memory> |
| 22 |
#include <vector> |
| 23 |
|
| 24 |
#include "source/cfa.h" |
| 25 |
#include "source/opt/ir_context.h" |
| 26 |
#include "source/opt/iterator.h" |
| 27 |
#include "source/opt/struct_cfg_analysis.h" |
| 28 |
#include "source/util/make_unique.h" |
| 29 |
|
| 30 |
namespace spvtools { |
| 31 |
namespace opt { |
| 32 |
|
| 33 |
namespace { |
| 34 |
|
| 35 |
const uint32_t kBranchCondTrueLabIdInIdx = 1; |
| 36 |
const uint32_t kBranchCondFalseLabIdInIdx = 2; |
| 37 |
|
| 38 |
} // anonymous namespace |
| 39 |
|
| 40 |
bool DeadBranchElimPass::GetConstCondition(uint32_t condId, bool* condVal) { |
| 41 |
bool condIsConst; |
| 42 |
Instruction* cInst = get_def_use_mgr()->GetDef(condId); |
| 43 |
switch (cInst->opcode()) { |
| 44 |
case SpvOpConstantNull: |
| 45 |
case SpvOpConstantFalse: { |
| 46 |
*condVal = false; |
| 47 |
condIsConst = true; |
| 48 |
} break; |
| 49 |
case SpvOpConstantTrue: { |
| 50 |
*condVal = true; |
| 51 |
condIsConst = true; |
| 52 |
} break; |
| 53 |
case SpvOpLogicalNot: { |
| 54 |
bool negVal; |
| 55 |
condIsConst = |
| 56 |
GetConstCondition(cInst->GetSingleWordInOperand(0), &negVal); |
| 57 |
if (condIsConst) *condVal = !negVal; |
| 58 |
} break; |
| 59 |
default: { condIsConst = false; } break; |
| 60 |
} |
| 61 |
return condIsConst; |
| 62 |
} |
| 63 |
|
| 64 |
bool DeadBranchElimPass::GetConstInteger(uint32_t selId, uint32_t* selVal) { |
| 65 |
Instruction* sInst = get_def_use_mgr()->GetDef(selId); |
| 66 |
uint32_t typeId = sInst->type_id(); |
| 67 |
Instruction* typeInst = get_def_use_mgr()->GetDef(typeId); |
| 68 |
if (!typeInst || (typeInst->opcode() != SpvOpTypeInt)) return false; |
| 69 |
// TODO(greg-lunarg): Support non-32 bit ints |
| 70 |
if (typeInst->GetSingleWordInOperand(0) != 32) return false; |
| 71 |
if (sInst->opcode() == SpvOpConstant) { |
| 72 |
*selVal = sInst->GetSingleWordInOperand(0); |
| 73 |
return true; |
| 74 |
} else if (sInst->opcode() == SpvOpConstantNull) { |
| 75 |
*selVal = 0; |
| 76 |
return true; |
| 77 |
} |
| 78 |
return false; |
| 79 |
} |
| 80 |
|
| 81 |
void DeadBranchElimPass::AddBranch(uint32_t labelId, BasicBlock* bp) { |
| 82 |
assert(get_def_use_mgr()->GetDef(labelId) != nullptr); |
| 83 |
std::unique_ptr<Instruction> newBranch( |
| 84 |
new Instruction(context(), SpvOpBranch, 0, 0, |
| 85 |
{{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {labelId}}})); |
| 86 |
context()->AnalyzeDefUse(&*newBranch); |
| 87 |
context()->set_instr_block(&*newBranch, bp); |
| 88 |
bp->AddInstruction(std::move(newBranch)); |
| 89 |
} |
| 90 |
|
| 91 |
BasicBlock* DeadBranchElimPass::GetParentBlock(uint32_t id) { |
| 92 |
return context()->get_instr_block(get_def_use_mgr()->GetDef(id)); |
| 93 |
} |
| 94 |
|
| 95 |
bool DeadBranchElimPass::MarkLiveBlocks( |
| 96 |
Function* func, std::unordered_set<BasicBlock*>* live_blocks) { |
| 97 |
std::vector<std::pair<BasicBlock*, uint32_t>> conditions_to_simplify; |
| 98 |
std::unordered_set<BasicBlock*> blocks_with_backedge; |
| 99 |
std::vector<BasicBlock*> stack; |
| 100 |
stack.push_back(&*func->begin()); |
| 101 |
bool modified = false; |
| 102 |
while (!stack.empty()) { |
| 103 |
BasicBlock* block = stack.back(); |
| 104 |
stack.pop_back(); |
| 105 |
|
| 106 |
// Live blocks doubles as visited set. |
| 107 |
if (!live_blocks->insert(block).second) continue; |
| 108 |
|
| 109 |
uint32_t cont_id = block->ContinueBlockIdIfAny(); |
| 110 |
if (cont_id != 0) { |
| 111 |
AddBlocksWithBackEdge(cont_id, block->id(), block->MergeBlockIdIfAny(), |
| 112 |
&blocks_with_backedge); |
| 113 |
} |
| 114 |
|
| 115 |
Instruction* terminator = block->terminator(); |
| 116 |
uint32_t live_lab_id = 0; |
| 117 |
// Check if the terminator has a single valid successor. |
| 118 |
if (terminator->opcode() == SpvOpBranchConditional) { |
| 119 |
bool condVal; |
| 120 |
if (GetConstCondition(terminator->GetSingleWordInOperand(0u), &condVal)) { |
| 121 |
live_lab_id = terminator->GetSingleWordInOperand( |
| 122 |
condVal ? kBranchCondTrueLabIdInIdx : kBranchCondFalseLabIdInIdx); |
| 123 |
} |
| 124 |
} else if (terminator->opcode() == SpvOpSwitch) { |
| 125 |
uint32_t sel_val; |
| 126 |
if (GetConstInteger(terminator->GetSingleWordInOperand(0u), &sel_val)) { |
| 127 |
// Search switch operands for selector value, set live_lab_id to |
| 128 |
// corresponding label, use default if not found. |
| 129 |
uint32_t icnt = 0; |
| 130 |
uint32_t case_val; |
| 131 |
terminator->WhileEachInOperand( |
| 132 |
[&icnt, &case_val, &sel_val, &live_lab_id](const uint32_t* idp) { |
| 133 |
if (icnt == 1) { |
| 134 |
// Start with default label. |
| 135 |
live_lab_id = *idp; |
| 136 |
} else if (icnt > 1) { |
| 137 |
if (icnt % 2 == 0) { |
| 138 |
case_val = *idp; |
| 139 |
} else { |
| 140 |
if (case_val == sel_val) { |
| 141 |
live_lab_id = *idp; |
| 142 |
return false; |
| 143 |
} |
| 144 |
} |
| 145 |
} |
| 146 |
++icnt; |
| 147 |
return true; |
| 148 |
}); |
| 149 |
} |
| 150 |
} |
| 151 |
|
| 152 |
// Don't simplify back edges unless it becomes a branch to the header. Every |
| 153 |
// loop must have exactly one back edge to the loop header, so we cannot |
| 154 |
// remove it. |
| 155 |
bool simplify = false; |
| 156 |
if (live_lab_id != 0) { |
| 157 |
if (!blocks_with_backedge.count(block)) { |
| 158 |
// This is not a back edge. |
| 159 |
simplify = true; |
| 160 |
} else { |
| 161 |
const auto& struct_cfg_analysis = context()->GetStructuredCFGAnalysis(); |
| 162 |
uint32_t header_id = struct_cfg_analysis->ContainingLoop(block->id()); |
| 163 |
if (live_lab_id == header_id) { |
| 164 |
// The new branch will be a branch to the header. |
| 165 |
simplify = true; |
| 166 |
} |
| 167 |
} |
| 168 |
} |
| 169 |
|
| 170 |
if (simplify) { |
| 171 |
conditions_to_simplify.push_back({block, live_lab_id}); |
| 172 |
stack.push_back(GetParentBlock(live_lab_id)); |
| 173 |
} else { |
| 174 |
// All successors are live. |
| 175 |
const auto* const_block = block; |
| 176 |
const_block->ForEachSuccessorLabel([&stack, this](const uint32_t label) { |
| 177 |
stack.push_back(GetParentBlock(label)); |
| 178 |
}); |
| 179 |
} |
| 180 |
} |
| 181 |
|
| 182 |
// Traverse |conditions_to_simplify| in reverse order. This is done so that |
| 183 |
// we simplify nested constructs before simplifying the constructs that |
| 184 |
// contain them. |
| 185 |
for (auto b = conditions_to_simplify.rbegin(); |
| 186 |
b != conditions_to_simplify.rend(); ++b) { |
| 187 |
modified |= SimplifyBranch(b->first, b->second); |
| 188 |
} |
| 189 |
|
| 190 |
return modified; |
| 191 |
} |
| 192 |
|
| 193 |
bool DeadBranchElimPass::SimplifyBranch(BasicBlock* block, |
| 194 |
uint32_t live_lab_id) { |
| 195 |
Instruction* merge_inst = block->GetMergeInst(); |
| 196 |
Instruction* terminator = block->terminator(); |
| 197 |
if (merge_inst && merge_inst->opcode() == SpvOpSelectionMerge) { |
| 198 |
if (merge_inst->NextNode()->opcode() == SpvOpSwitch && |
| 199 |
SwitchHasNestedBreak(block->id())) { |
| 200 |
if (terminator->NumInOperands() == 2) { |
| 201 |
// We cannot remove the branch, and it already has a single case, so no |
| 202 |
// work to do. |
| 203 |
return false; |
| 204 |
} |
| 205 |
// We have to keep the switch because it has a nest break, so we |
| 206 |
// remove all cases except for the live one. |
| 207 |
Instruction::OperandList new_operands; |
| 208 |
new_operands.push_back(terminator->GetInOperand(0)); |
| 209 |
new_operands.push_back({SPV_OPERAND_TYPE_ID, {live_lab_id}}); |
| 210 |
terminator->SetInOperands(move(new_operands)); |
| 211 |
context()->UpdateDefUse(terminator); |
| 212 |
} else { |
| 213 |
// Check if the merge instruction is still needed because of a |
| 214 |
// non-nested break from the construct. Move the merge instruction if |
| 215 |
// it is still needed. |
| 216 |
StructuredCFGAnalysis* cfg_analysis = |
| 217 |
context()->GetStructuredCFGAnalysis(); |
| 218 |
Instruction* first_break = FindFirstExitFromSelectionMerge( |
| 219 |
live_lab_id, merge_inst->GetSingleWordInOperand(0), |
| 220 |
cfg_analysis->LoopMergeBlock(live_lab_id), |
| 221 |
cfg_analysis->LoopContinueBlock(live_lab_id), |
| 222 |
cfg_analysis->SwitchMergeBlock(live_lab_id)); |
| 223 |
|
| 224 |
AddBranch(live_lab_id, block); |
| 225 |
context()->KillInst(terminator); |
| 226 |
if (first_break == nullptr) { |
| 227 |
context()->KillInst(merge_inst); |
| 228 |
} else { |
| 229 |
merge_inst->RemoveFromList(); |
| 230 |
first_break->InsertBefore(std::unique_ptr<Instruction>(merge_inst)); |
| 231 |
context()->set_instr_block(merge_inst, |
| 232 |
context()->get_instr_block(first_break)); |
| 233 |
} |
| 234 |
} |
| 235 |
} else { |
| 236 |
AddBranch(live_lab_id, block); |
| 237 |
context()->KillInst(terminator); |
| 238 |
} |
| 239 |
return true; |
| 240 |
} |
| 241 |
|
| 242 |
void DeadBranchElimPass::MarkUnreachableStructuredTargets( |
| 243 |
const std::unordered_set<BasicBlock*>& live_blocks, |
| 244 |
std::unordered_set<BasicBlock*>* unreachable_merges, |
| 245 |
std::unordered_map<BasicBlock*, BasicBlock*>* unreachable_continues) { |
| 246 |
for (auto block : live_blocks) { |
| 247 |
if (auto merge_id = block->MergeBlockIdIfAny()) { |
| 248 |
BasicBlock* merge_block = GetParentBlock(merge_id); |
| 249 |
if (!live_blocks.count(merge_block)) { |
| 250 |
unreachable_merges->insert(merge_block); |
| 251 |
} |
| 252 |
if (auto cont_id = block->ContinueBlockIdIfAny()) { |
| 253 |
BasicBlock* cont_block = GetParentBlock(cont_id); |
| 254 |
if (!live_blocks.count(cont_block)) { |
| 255 |
(*unreachable_continues)[cont_block] = block; |
| 256 |
} |
| 257 |
} |
| 258 |
} |
| 259 |
} |
| 260 |
} |
| 261 |
|
| 262 |
bool DeadBranchElimPass::FixPhiNodesInLiveBlocks( |
| 263 |
Function* func, const std::unordered_set<BasicBlock*>& live_blocks, |
| 264 |
const std::unordered_map<BasicBlock*, BasicBlock*>& unreachable_continues) { |
| 265 |
bool modified = false; |
| 266 |
for (auto& block : *func) { |
| 267 |
if (live_blocks.count(&block)) { |
| 268 |
for (auto iter = block.begin(); iter != block.end();) { |
| 269 |
if (iter->opcode() != SpvOpPhi) { |
| 270 |
break; |
| 271 |
} |
| 272 |
|
| 273 |
bool changed = false; |
| 274 |
bool backedge_added = false; |
| 275 |
Instruction* inst = &*iter; |
| 276 |
std::vector<Operand> operands; |
| 277 |
// Build a complete set of operands (not just input operands). Start |
| 278 |
// with type and result id operands. |
| 279 |
operands.push_back(inst->GetOperand(0u)); |
| 280 |
operands.push_back(inst->GetOperand(1u)); |
| 281 |
// Iterate through the incoming labels and determine which to keep |
| 282 |
// and/or modify. If there in an unreachable continue block, there will |
| 283 |
// be an edge from that block to the header. We need to keep it to |
| 284 |
// maintain the structured control flow. If the header has more that 2 |
| 285 |
// incoming edges, then the OpPhi must have an entry for that edge. |
| 286 |
// However, if there is only one other incoming edge, the OpPhi can be |
| 287 |
// eliminated. |
| 288 |
for (uint32_t i = 1; i < inst->NumInOperands(); i += 2) { |
| 289 |
BasicBlock* inc = GetParentBlock(inst->GetSingleWordInOperand(i)); |
| 290 |
auto cont_iter = unreachable_continues.find(inc); |
| 291 |
if (cont_iter != unreachable_continues.end() && |
| 292 |
cont_iter->second == &block && inst->NumInOperands() > 4) { |
| 293 |
if (get_def_use_mgr() |
| 294 |
->GetDef(inst->GetSingleWordInOperand(i - 1)) |
| 295 |
->opcode() == SpvOpUndef) { |
| 296 |
// Already undef incoming value, no change necessary. |
| 297 |
operands.push_back(inst->GetInOperand(i - 1)); |
| 298 |
operands.push_back(inst->GetInOperand(i)); |
| 299 |
backedge_added = true; |
| 300 |
} else { |
| 301 |
// Replace incoming value with undef if this phi exists in the |
| 302 |
// loop header. Otherwise, this edge is not live since the |
| 303 |
// unreachable continue block will be replaced with an |
| 304 |
// unconditional branch to the header only. |
| 305 |
operands.emplace_back( |
| 306 |
SPV_OPERAND_TYPE_ID, |
| 307 |
std::initializer_list<uint32_t>{Type2Undef(inst->type_id())}); |
| 308 |
operands.push_back(inst->GetInOperand(i)); |
| 309 |
changed = true; |
| 310 |
backedge_added = true; |
| 311 |
} |
| 312 |
} else if (live_blocks.count(inc) && inc->IsSuccessor(&block)) { |
| 313 |
// Keep live incoming edge. |
| 314 |
operands.push_back(inst->GetInOperand(i - 1)); |
| 315 |
operands.push_back(inst->GetInOperand(i)); |
| 316 |
} else { |
| 317 |
// Remove incoming edge. |
| 318 |
changed = true; |
| 319 |
} |
| 320 |
} |
| 321 |
|
| 322 |
if (changed) { |
| 323 |
modified = true; |
| 324 |
uint32_t continue_id = block.ContinueBlockIdIfAny(); |
| 325 |
if (!backedge_added && continue_id != 0 && |
| 326 |
unreachable_continues.count(GetParentBlock(continue_id)) && |
| 327 |
operands.size() > 4) { |
| 328 |
// Changed the backedge to branch from the continue block instead |
| 329 |
// of a successor of the continue block. Add an entry to the phi to |
| 330 |
// provide an undef for the continue block. Since the successor of |
| 331 |
// the continue must also be unreachable (dominated by the continue |
| 332 |
// block), any entry for the original backedge has been removed |
| 333 |
// from the phi operands. |
| 334 |
operands.emplace_back( |
| 335 |
SPV_OPERAND_TYPE_ID, |
| 336 |
std::initializer_list<uint32_t>{Type2Undef(inst->type_id())}); |
| 337 |
operands.emplace_back(SPV_OPERAND_TYPE_ID, |
| 338 |
std::initializer_list<uint32_t>{continue_id}); |
| 339 |
} |
| 340 |
|
| 341 |
// Either replace the phi with a single value or rebuild the phi out |
| 342 |
// of |operands|. |
| 343 |
// |
| 344 |
// We always have type and result id operands. So this phi has a |
| 345 |
// single source if there are two more operands beyond those. |
| 346 |
if (operands.size() == 4) { |
| 347 |
// First input data operands is at index 2. |
| 348 |
uint32_t replId = operands[2u].words[0]; |
| 349 |
context()->ReplaceAllUsesWith(inst->result_id(), replId); |
| 350 |
iter = context()->KillInst(&*inst); |
| 351 |
} else { |
| 352 |
// We've rewritten the operands, so first instruct the def/use |
| 353 |
// manager to forget uses in the phi before we replace them. After |
| 354 |
// replacing operands update the def/use manager by re-analyzing |
| 355 |
// the used ids in this phi. |
| 356 |
get_def_use_mgr()->EraseUseRecordsOfOperandIds(inst); |
| 357 |
inst->ReplaceOperands(operands); |
| 358 |
get_def_use_mgr()->AnalyzeInstUse(inst); |
| 359 |
++iter; |
| 360 |
} |
| 361 |
} else { |
| 362 |
++iter; |
| 363 |
} |
| 364 |
} |
| 365 |
} |
| 366 |
} |
| 367 |
|
| 368 |
return modified; |
| 369 |
} |
| 370 |
|
| 371 |
bool DeadBranchElimPass::EraseDeadBlocks( |
| 372 |
Function* func, const std::unordered_set<BasicBlock*>& live_blocks, |
| 373 |
const std::unordered_set<BasicBlock*>& unreachable_merges, |
| 374 |
const std::unordered_map<BasicBlock*, BasicBlock*>& unreachable_continues) { |
| 375 |
bool modified = false; |
| 376 |
for (auto ebi = func->begin(); ebi != func->end();) { |
| 377 |
if (unreachable_continues.count(&*ebi)) { |
| 378 |
uint32_t cont_id = unreachable_continues.find(&*ebi)->second->id(); |
| 379 |
if (ebi->begin() != ebi->tail() || |
| 380 |
ebi->terminator()->opcode() != SpvOpBranch || |
| 381 |
ebi->terminator()->GetSingleWordInOperand(0u) != cont_id) { |
| 382 |
// Make unreachable, but leave the label. |
| 383 |
KillAllInsts(&*ebi, false); |
| 384 |
// Add unconditional branch to header. |
| 385 |
assert(unreachable_continues.count(&*ebi)); |
| 386 |
ebi->AddInstruction(MakeUnique<Instruction>( |
| 387 |
context(), SpvOpBranch, 0, 0, |
| 388 |
std::initializer_list<Operand>{{SPV_OPERAND_TYPE_ID, {cont_id}}})); |
| 389 |
get_def_use_mgr()->AnalyzeInstUse(&*ebi->tail()); |
| 390 |
context()->set_instr_block(&*ebi->tail(), &*ebi); |
| 391 |
modified = true; |
| 392 |
} |
| 393 |
++ebi; |
| 394 |
} else if (unreachable_merges.count(&*ebi)) { |
| 395 |
if (ebi->begin() != ebi->tail() || |
| 396 |
ebi->terminator()->opcode() != SpvOpUnreachable) { |
| 397 |
// Make unreachable, but leave the label. |
| 398 |
KillAllInsts(&*ebi, false); |
| 399 |
// Add unreachable terminator. |
| 400 |
ebi->AddInstruction( |
| 401 |
MakeUnique<Instruction>(context(), SpvOpUnreachable, 0, 0, |
| 402 |
std::initializer_list<Operand>{})); |
| 403 |
context()->AnalyzeUses(ebi->terminator()); |
| 404 |
context()->set_instr_block(ebi->terminator(), &*ebi); |
| 405 |
modified = true; |
| 406 |
} |
| 407 |
++ebi; |
| 408 |
} else if (!live_blocks.count(&*ebi)) { |
| 409 |
// Kill this block. |
| 410 |
KillAllInsts(&*ebi); |
| 411 |
ebi = ebi.Erase(); |
| 412 |
modified = true; |
| 413 |
} else { |
| 414 |
++ebi; |
| 415 |
} |
| 416 |
} |
| 417 |
|
| 418 |
return modified; |
| 419 |
} |
| 420 |
|
| 421 |
bool DeadBranchElimPass::EliminateDeadBranches(Function* func) { |
| 422 |
bool modified = false; |
| 423 |
std::unordered_set<BasicBlock*> live_blocks; |
| 424 |
modified |= MarkLiveBlocks(func, &live_blocks); |
| 425 |
|
| 426 |
std::unordered_set<BasicBlock*> unreachable_merges; |
| 427 |
std::unordered_map<BasicBlock*, BasicBlock*> unreachable_continues; |
| 428 |
MarkUnreachableStructuredTargets(live_blocks, &unreachable_merges, |
| 429 |
&unreachable_continues); |
| 430 |
modified |= FixPhiNodesInLiveBlocks(func, live_blocks, unreachable_continues); |
| 431 |
modified |= EraseDeadBlocks(func, live_blocks, unreachable_merges, |
| 432 |
unreachable_continues); |
| 433 |
|
| 434 |
return modified; |
| 435 |
} |
| 436 |
|
| 437 |
void DeadBranchElimPass::FixBlockOrder() { |
| 438 |
context()->BuildInvalidAnalyses(IRContext::kAnalysisCFG | |
| 439 |
IRContext::kAnalysisDominatorAnalysis); |
| 440 |
// Reorders blocks according to DFS of dominator tree. |
| 441 |
ProcessFunction reorder_dominators = [this](Function* function) { |
| 442 |
DominatorAnalysis* dominators = context()->GetDominatorAnalysis(function); |
| 443 |
std::vector<BasicBlock*> blocks; |
| 444 |
for (auto iter = dominators->GetDomTree().begin(); |
| 445 |
iter != dominators->GetDomTree().end(); ++iter) { |
| 446 |
if (iter->id() != 0) { |
| 447 |
blocks.push_back(iter->bb_); |
| 448 |
} |
| 449 |
} |
| 450 |
for (uint32_t i = 1; i < blocks.size(); ++i) { |
| 451 |
function->MoveBasicBlockToAfter(blocks[i]->id(), blocks[i - 1]); |
| 452 |
} |
| 453 |
return true; |
| 454 |
}; |
| 455 |
|
| 456 |
// Reorders blocks according to structured order. |
| 457 |
ProcessFunction reorder_structured = [this](Function* function) { |
| 458 |
std::list<BasicBlock*> order; |
| 459 |
context()->cfg()->ComputeStructuredOrder(function, &*function->begin(), |
| 460 |
&order); |
| 461 |
std::vector<BasicBlock*> blocks; |
| 462 |
for (auto block : order) { |
| 463 |
blocks.push_back(block); |
| 464 |
} |
| 465 |
for (uint32_t i = 1; i < blocks.size(); ++i) { |
| 466 |
function->MoveBasicBlockToAfter(blocks[i]->id(), blocks[i - 1]); |
| 467 |
} |
| 468 |
return true; |
| 469 |
}; |
| 470 |
|
| 471 |
// Structured order is more intuitive so use it where possible. |
| 472 |
if (context()->get_feature_mgr()->HasCapability(SpvCapabilityShader)) { |
| 473 |
context()->ProcessReachableCallTree(reorder_structured); |
| 474 |
} else { |
| 475 |
context()->ProcessReachableCallTree(reorder_dominators); |
| 476 |
} |
| 477 |
} |
| 478 |
|
| 479 |
Pass::Status DeadBranchElimPass::Process() { |
| 480 |
// Do not process if module contains OpGroupDecorate. Additional |
| 481 |
// support required in KillNamesAndDecorates(). |
| 482 |
// TODO(greg-lunarg): Add support for OpGroupDecorate |
| 483 |
for (auto& ai : get_module()->annotations()) |
| 484 |
if (ai.opcode() == SpvOpGroupDecorate) return Status::SuccessWithoutChange; |
| 485 |
// Process all entry point functions |
| 486 |
ProcessFunction pfn = [this](Function* fp) { |
| 487 |
return EliminateDeadBranches(fp); |
| 488 |
}; |
| 489 |
bool modified = context()->ProcessReachableCallTree(pfn); |
| 490 |
if (modified) FixBlockOrder(); |
| 491 |
return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange; |
| 492 |
} |
| 493 |
|
| 494 |
Instruction* DeadBranchElimPass::FindFirstExitFromSelectionMerge( |
| 495 |
uint32_t start_block_id, uint32_t merge_block_id, uint32_t loop_merge_id, |
| 496 |
uint32_t loop_continue_id, uint32_t switch_merge_id) { |
| 497 |
// To find the "first" exit, we follow branches looking for a conditional |
| 498 |
// branch that is not in a nested construct and is not the header of a new |
| 499 |
// construct. We follow the control flow from |start_block_id| to find the |
| 500 |
// first one. |
| 501 |
|
| 502 |
while (start_block_id != merge_block_id && start_block_id != loop_merge_id && |
| 503 |
start_block_id != loop_continue_id) { |
| 504 |
BasicBlock* start_block = context()->get_instr_block(start_block_id); |
| 505 |
Instruction* branch = start_block->terminator(); |
| 506 |
uint32_t next_block_id = 0; |
| 507 |
switch (branch->opcode()) { |
| 508 |
case SpvOpBranchConditional: |
| 509 |
next_block_id = start_block->MergeBlockIdIfAny(); |
| 510 |
if (next_block_id == 0) { |
| 511 |
// If a possible target is the |loop_merge_id| or |loop_continue_id|, |
| 512 |
// which are not the current merge node, then we continue the search |
| 513 |
// with the other target. |
| 514 |
for (uint32_t i = 1; i < 3; i++) { |
| 515 |
if (branch->GetSingleWordInOperand(i) == loop_merge_id && |
| 516 |
loop_merge_id != merge_block_id) { |
| 517 |
next_block_id = branch->GetSingleWordInOperand(3 - i); |
| 518 |
break; |
| 519 |
} |
| 520 |
if (branch->GetSingleWordInOperand(i) == loop_continue_id && |
| 521 |
loop_continue_id != merge_block_id) { |
| 522 |
next_block_id = branch->GetSingleWordInOperand(3 - i); |
| 523 |
break; |
| 524 |
} |
| 525 |
if (branch->GetSingleWordInOperand(i) == switch_merge_id && |
| 526 |
switch_merge_id != merge_block_id) { |
| 527 |
next_block_id = branch->GetSingleWordInOperand(3 - i); |
| 528 |
break; |
| 529 |
} |
| 530 |
} |
| 531 |
|
| 532 |
if (next_block_id == 0) { |
| 533 |
return branch; |
| 534 |
} |
| 535 |
} |
| 536 |
break; |
| 537 |
case SpvOpSwitch: |
| 538 |
next_block_id = start_block->MergeBlockIdIfAny(); |
| 539 |
if (next_block_id == 0) { |
| 540 |
// A switch with no merge instructions can have at most 5 targets: |
| 541 |
// a. |merge_block_id| |
| 542 |
// b. |loop_merge_id| |
| 543 |
// c. |loop_continue_id| |
| 544 |
// d. |switch_merge_id| |
| 545 |
// e. 1 block inside the current region. |
| 546 |
// |
| 547 |
// Note that because this is a switch, |merge_block_id| must equal |
| 548 |
// |switch_merge_id|. |
| 549 |
// |
| 550 |
// This leads to a number of cases of what to do. |
| 551 |
// |
| 552 |
// 1. Does not jump to a block inside of the current construct. In |
| 553 |
// this case, there is not conditional break, so we should return |
| 554 |
// |nullptr|. |
| 555 |
// |
| 556 |
// 2. Jumps to |merge_block_id| and a block inside the current |
| 557 |
// construct. In this case, this branch conditionally break to the |
| 558 |
// end of the current construct, so return the current branch. |
| 559 |
// |
| 560 |
// 3. Otherwise, this branch may break, but not to the current merge |
| 561 |
// block. So we continue with the block that is inside the loop. |
| 562 |
bool found_break = false; |
| 563 |
for (uint32_t i = 1; i < branch->NumInOperands(); i += 2) { |
| 564 |
uint32_t target = branch->GetSingleWordInOperand(i); |
| 565 |
if (target == merge_block_id) { |
| 566 |
found_break = true; |
| 567 |
} else if (target != loop_merge_id && target != loop_continue_id) { |
| 568 |
next_block_id = branch->GetSingleWordInOperand(i); |
| 569 |
} |
| 570 |
} |
| 571 |
|
| 572 |
if (next_block_id == 0) { |
| 573 |
// Case 1. |
| 574 |
return nullptr; |
| 575 |
} |
| 576 |
|
| 577 |
if (found_break) { |
| 578 |
// Case 2. |
| 579 |
return branch; |
| 580 |
} |
| 581 |
|
| 582 |
// The fall through is case 3. |
| 583 |
} |
| 584 |
break; |
| 585 |
case SpvOpBranch: |
| 586 |
// Need to check if this is the header of a loop nested in the |
| 587 |
// selection construct. |
| 588 |
next_block_id = start_block->MergeBlockIdIfAny(); |
| 589 |
if (next_block_id == 0) { |
| 590 |
next_block_id = branch->GetSingleWordInOperand(0); |
| 591 |
} |
| 592 |
break; |
| 593 |
default: |
| 594 |
return nullptr; |
| 595 |
} |
| 596 |
start_block_id = next_block_id; |
| 597 |
} |
| 598 |
return nullptr; |
| 599 |
} |
| 600 |
|
| 601 |
void DeadBranchElimPass::AddBlocksWithBackEdge( |
| 602 |
uint32_t cont_id, uint32_t header_id, uint32_t merge_id, |
| 603 |
std::unordered_set<BasicBlock*>* blocks_with_back_edges) { |
| 604 |
std::unordered_set<uint32_t> visited; |
| 605 |
visited.insert(cont_id); |
| 606 |
visited.insert(header_id); |
| 607 |
visited.insert(merge_id); |
| 608 |
|
| 609 |
std::vector<uint32_t> work_list; |
| 610 |
work_list.push_back(cont_id); |
| 611 |
|
| 612 |
while (!work_list.empty()) { |
| 613 |
uint32_t bb_id = work_list.back(); |
| 614 |
work_list.pop_back(); |
| 615 |
|
| 616 |
BasicBlock* bb = context()->get_instr_block(bb_id); |
| 617 |
|
| 618 |
bool has_back_edge = false; |
| 619 |
bb->ForEachSuccessorLabel([header_id, &visited, &work_list, |
| 620 |
&has_back_edge](uint32_t* succ_label_id) { |
| 621 |
if (visited.insert(*succ_label_id).second) { |
| 622 |
work_list.push_back(*succ_label_id); |
| 623 |
} |
| 624 |
if (*succ_label_id == header_id) { |
| 625 |
has_back_edge = true; |
| 626 |
} |
| 627 |
}); |
| 628 |
|
| 629 |
if (has_back_edge) { |
| 630 |
blocks_with_back_edges->insert(bb); |
| 631 |
} |
| 632 |
} |
| 633 |
} |
| 634 |
|
| 635 |
bool DeadBranchElimPass::SwitchHasNestedBreak(uint32_t switch_header_id) { |
| 636 |
std::vector<BasicBlock*> block_in_construct; |
| 637 |
BasicBlock* start_block = context()->get_instr_block(switch_header_id); |
| 638 |
uint32_t merge_block_id = start_block->MergeBlockIdIfAny(); |
| 639 |
|
| 640 |
StructuredCFGAnalysis* cfg_analysis = context()->GetStructuredCFGAnalysis(); |
| 641 |
return !get_def_use_mgr()->WhileEachUser( |
| 642 |
merge_block_id, |
| 643 |
[this, cfg_analysis, switch_header_id](Instruction* inst) { |
| 644 |
if (!inst->IsBranch()) { |
| 645 |
return true; |
| 646 |
} |
| 647 |
|
| 648 |
BasicBlock* bb = context()->get_instr_block(inst); |
| 649 |
if (bb->id() == switch_header_id) { |
| 650 |
return true; |
| 651 |
} |
| 652 |
return (cfg_analysis->ContainingConstruct(inst) == switch_header_id && |
| 653 |
bb->GetMergeInst() == nullptr); |
| 654 |
}); |
| 655 |
} |
| 656 |
|
| 657 |
} // namespace opt |
| 658 |
} // namespace spvtools |