| // Copyright (c) 2017 The Khronos Group Inc. |
| // Copyright (c) 2017 Valve Corporation |
| // Copyright (c) 2017 LunarG Inc. |
| // Copyright (c) 2018 Google Inc. |
| // |
| // 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 "dead_branch_elim_pass.h" |
| |
| #include "cfa.h" |
| #include "ir_context.h" |
| #include "iterator.h" |
| #include "make_unique.h" |
| |
| namespace spvtools { |
| namespace opt { |
| |
| namespace { |
| |
| const uint32_t kBranchCondTrueLabIdInIdx = 1; |
| const uint32_t kBranchCondFalseLabIdInIdx = 2; |
| |
| } // anonymous namespace |
| |
| bool DeadBranchElimPass::GetConstCondition(uint32_t condId, bool* condVal) { |
| bool condIsConst; |
| opt::Instruction* cInst = get_def_use_mgr()->GetDef(condId); |
| switch (cInst->opcode()) { |
| case SpvOpConstantFalse: { |
| *condVal = false; |
| condIsConst = true; |
| } break; |
| case SpvOpConstantTrue: { |
| *condVal = true; |
| condIsConst = true; |
| } break; |
| case SpvOpLogicalNot: { |
| bool negVal; |
| condIsConst = |
| GetConstCondition(cInst->GetSingleWordInOperand(0), &negVal); |
| if (condIsConst) *condVal = !negVal; |
| } break; |
| default: { condIsConst = false; } break; |
| } |
| return condIsConst; |
| } |
| |
| bool DeadBranchElimPass::GetConstInteger(uint32_t selId, uint32_t* selVal) { |
| opt::Instruction* sInst = get_def_use_mgr()->GetDef(selId); |
| uint32_t typeId = sInst->type_id(); |
| opt::Instruction* typeInst = get_def_use_mgr()->GetDef(typeId); |
| if (!typeInst || (typeInst->opcode() != SpvOpTypeInt)) return false; |
| // TODO(greg-lunarg): Support non-32 bit ints |
| if (typeInst->GetSingleWordInOperand(0) != 32) return false; |
| if (sInst->opcode() == SpvOpConstant) { |
| *selVal = sInst->GetSingleWordInOperand(0); |
| return true; |
| } else if (sInst->opcode() == SpvOpConstantNull) { |
| *selVal = 0; |
| return true; |
| } |
| return false; |
| } |
| |
| void DeadBranchElimPass::AddBranch(uint32_t labelId, opt::BasicBlock* bp) { |
| assert(get_def_use_mgr()->GetDef(labelId) != nullptr); |
| std::unique_ptr<opt::Instruction> newBranch(new opt::Instruction( |
| context(), SpvOpBranch, 0, 0, |
| {{spv_operand_type_t::SPV_OPERAND_TYPE_ID, {labelId}}})); |
| context()->AnalyzeDefUse(&*newBranch); |
| context()->set_instr_block(&*newBranch, bp); |
| bp->AddInstruction(std::move(newBranch)); |
| } |
| |
| opt::BasicBlock* DeadBranchElimPass::GetParentBlock(uint32_t id) { |
| return context()->get_instr_block(get_def_use_mgr()->GetDef(id)); |
| } |
| |
| bool DeadBranchElimPass::MarkLiveBlocks( |
| opt::Function* func, std::unordered_set<opt::BasicBlock*>* live_blocks) { |
| std::unordered_set<opt::BasicBlock*> continues; |
| std::vector<opt::BasicBlock*> stack; |
| stack.push_back(&*func->begin()); |
| bool modified = false; |
| while (!stack.empty()) { |
| opt::BasicBlock* block = stack.back(); |
| stack.pop_back(); |
| |
| // Live blocks doubles as visited set. |
| if (!live_blocks->insert(block).second) continue; |
| |
| uint32_t cont_id = block->ContinueBlockIdIfAny(); |
| if (cont_id != 0) continues.insert(GetParentBlock(cont_id)); |
| |
| opt::Instruction* terminator = block->terminator(); |
| uint32_t live_lab_id = 0; |
| // Check if the terminator has a single valid successor. |
| if (terminator->opcode() == SpvOpBranchConditional) { |
| bool condVal; |
| if (GetConstCondition(terminator->GetSingleWordInOperand(0u), &condVal)) { |
| live_lab_id = terminator->GetSingleWordInOperand( |
| condVal ? kBranchCondTrueLabIdInIdx : kBranchCondFalseLabIdInIdx); |
| } |
| } else if (terminator->opcode() == SpvOpSwitch) { |
| uint32_t sel_val; |
| if (GetConstInteger(terminator->GetSingleWordInOperand(0u), &sel_val)) { |
| // Search switch operands for selector value, set live_lab_id to |
| // corresponding label, use default if not found. |
| uint32_t icnt = 0; |
| uint32_t case_val; |
| terminator->WhileEachInOperand( |
| [&icnt, &case_val, &sel_val, &live_lab_id](const uint32_t* idp) { |
| if (icnt == 1) { |
| // Start with default label. |
| live_lab_id = *idp; |
| } else if (icnt > 1) { |
| if (icnt % 2 == 0) { |
| case_val = *idp; |
| } else { |
| if (case_val == sel_val) { |
| live_lab_id = *idp; |
| return false; |
| } |
| } |
| } |
| ++icnt; |
| return true; |
| }); |
| } |
| } |
| |
| // Don't simplify branches of continue blocks. A path from the continue to |
| // the header is required. |
| // TODO(alan-baker): They can be simplified iff there remains a path to the |
| // backedge. Structured control flow should guarantee one path hits the |
| // backedge, but I've removed the requirement for structured control flow |
| // from this pass. |
| bool simplify = live_lab_id != 0 && !continues.count(block); |
| |
| if (simplify) { |
| modified = true; |
| // Replace with unconditional branch. |
| // Remove the merge instruction if it is a selection merge. |
| AddBranch(live_lab_id, block); |
| context()->KillInst(terminator); |
| opt::Instruction* mergeInst = block->GetMergeInst(); |
| if (mergeInst && mergeInst->opcode() == SpvOpSelectionMerge) { |
| context()->KillInst(mergeInst); |
| } |
| stack.push_back(GetParentBlock(live_lab_id)); |
| } else { |
| // All successors are live. |
| const auto* const_block = block; |
| const_block->ForEachSuccessorLabel([&stack, this](const uint32_t label) { |
| stack.push_back(GetParentBlock(label)); |
| }); |
| } |
| } |
| |
| return modified; |
| } |
| |
| void DeadBranchElimPass::MarkUnreachableStructuredTargets( |
| const std::unordered_set<opt::BasicBlock*>& live_blocks, |
| std::unordered_set<opt::BasicBlock*>* unreachable_merges, |
| std::unordered_map<opt::BasicBlock*, opt::BasicBlock*>* |
| unreachable_continues) { |
| for (auto block : live_blocks) { |
| if (auto merge_id = block->MergeBlockIdIfAny()) { |
| opt::BasicBlock* merge_block = GetParentBlock(merge_id); |
| if (!live_blocks.count(merge_block)) { |
| unreachable_merges->insert(merge_block); |
| } |
| if (auto cont_id = block->ContinueBlockIdIfAny()) { |
| opt::BasicBlock* cont_block = GetParentBlock(cont_id); |
| if (!live_blocks.count(cont_block)) { |
| (*unreachable_continues)[cont_block] = block; |
| } |
| } |
| } |
| } |
| } |
| |
| bool DeadBranchElimPass::FixPhiNodesInLiveBlocks( |
| opt::Function* func, |
| const std::unordered_set<opt::BasicBlock*>& live_blocks, |
| const std::unordered_map<opt::BasicBlock*, opt::BasicBlock*>& |
| unreachable_continues) { |
| bool modified = false; |
| for (auto& block : *func) { |
| if (live_blocks.count(&block)) { |
| for (auto iter = block.begin(); iter != block.end();) { |
| if (iter->opcode() != SpvOpPhi) { |
| break; |
| } |
| |
| bool changed = false; |
| bool backedge_added = false; |
| opt::Instruction* inst = &*iter; |
| std::vector<opt::Operand> operands; |
| // Build a complete set of operands (not just input operands). Start |
| // with type and result id operands. |
| operands.push_back(inst->GetOperand(0u)); |
| operands.push_back(inst->GetOperand(1u)); |
| // Iterate through the incoming labels and determine which to keep |
| // and/or modify. If there in an unreachable continue block, there will |
| // be an edge from that block to the header. We need to keep it to |
| // maintain the structured control flow. If the header has more that 2 |
| // incoming edges, then the OpPhi must have an entry for that edge. |
| // However, if there is only one other incoming edge, the OpPhi can be |
| // eliminated. |
| for (uint32_t i = 1; i < inst->NumInOperands(); i += 2) { |
| opt::BasicBlock* inc = |
| GetParentBlock(inst->GetSingleWordInOperand(i)); |
| auto cont_iter = unreachable_continues.find(inc); |
| if (cont_iter != unreachable_continues.end() && |
| cont_iter->second == &block && inst->NumInOperands() > 4) { |
| if (get_def_use_mgr() |
| ->GetDef(inst->GetSingleWordInOperand(i - 1)) |
| ->opcode() == SpvOpUndef) { |
| // Already undef incoming value, no change necessary. |
| operands.push_back(inst->GetInOperand(i - 1)); |
| operands.push_back(inst->GetInOperand(i)); |
| backedge_added = true; |
| } else { |
| // Replace incoming value with undef if this phi exists in the |
| // loop header. Otherwise, this edge is not live since the |
| // unreachable continue block will be replaced with an |
| // unconditional branch to the header only. |
| operands.emplace_back( |
| SPV_OPERAND_TYPE_ID, |
| std::initializer_list<uint32_t>{Type2Undef(inst->type_id())}); |
| operands.push_back(inst->GetInOperand(i)); |
| changed = true; |
| backedge_added = true; |
| } |
| } else if (live_blocks.count(inc) && inc->IsSuccessor(&block)) { |
| // Keep live incoming edge. |
| operands.push_back(inst->GetInOperand(i - 1)); |
| operands.push_back(inst->GetInOperand(i)); |
| } else { |
| // Remove incoming edge. |
| changed = true; |
| } |
| } |
| |
| if (changed) { |
| modified = true; |
| uint32_t continue_id = block.ContinueBlockIdIfAny(); |
| if (!backedge_added && continue_id != 0 && |
| unreachable_continues.count(GetParentBlock(continue_id)) && |
| operands.size() > 4) { |
| // Changed the backedge to branch from the continue block instead |
| // of a successor of the continue block. Add an entry to the phi to |
| // provide an undef for the continue block. Since the successor of |
| // the continue must also be unreachable (dominated by the continue |
| // block), any entry for the original backedge has been removed |
| // from the phi operands. |
| operands.emplace_back( |
| SPV_OPERAND_TYPE_ID, |
| std::initializer_list<uint32_t>{Type2Undef(inst->type_id())}); |
| operands.emplace_back(SPV_OPERAND_TYPE_ID, |
| std::initializer_list<uint32_t>{continue_id}); |
| } |
| |
| // Either replace the phi with a single value or rebuild the phi out |
| // of |operands|. |
| // |
| // We always have type and result id operands. So this phi has a |
| // single source if there are two more operands beyond those. |
| if (operands.size() == 4) { |
| // First input data operands is at index 2. |
| uint32_t replId = operands[2u].words[0]; |
| context()->ReplaceAllUsesWith(inst->result_id(), replId); |
| iter = context()->KillInst(&*inst); |
| } else { |
| // We've rewritten the operands, so first instruct the def/use |
| // manager to forget uses in the phi before we replace them. After |
| // replacing operands update the def/use manager by re-analyzing |
| // the used ids in this phi. |
| get_def_use_mgr()->EraseUseRecordsOfOperandIds(inst); |
| inst->ReplaceOperands(operands); |
| get_def_use_mgr()->AnalyzeInstUse(inst); |
| ++iter; |
| } |
| } else { |
| ++iter; |
| } |
| } |
| } |
| } |
| |
| return modified; |
| } |
| |
| bool DeadBranchElimPass::EraseDeadBlocks( |
| opt::Function* func, |
| const std::unordered_set<opt::BasicBlock*>& live_blocks, |
| const std::unordered_set<opt::BasicBlock*>& unreachable_merges, |
| const std::unordered_map<opt::BasicBlock*, opt::BasicBlock*>& |
| unreachable_continues) { |
| bool modified = false; |
| for (auto ebi = func->begin(); ebi != func->end();) { |
| if (unreachable_merges.count(&*ebi)) { |
| if (ebi->begin() != ebi->tail() || |
| ebi->terminator()->opcode() != SpvOpUnreachable) { |
| // Make unreachable, but leave the label. |
| KillAllInsts(&*ebi, false); |
| // Add unreachable terminator. |
| ebi->AddInstruction(MakeUnique<opt::Instruction>( |
| context(), SpvOpUnreachable, 0, 0, |
| std::initializer_list<opt::Operand>{})); |
| context()->set_instr_block(&*ebi->tail(), &*ebi); |
| modified = true; |
| } |
| ++ebi; |
| } else if (unreachable_continues.count(&*ebi)) { |
| uint32_t cont_id = unreachable_continues.find(&*ebi)->second->id(); |
| if (ebi->begin() != ebi->tail() || |
| ebi->terminator()->opcode() != SpvOpBranch || |
| ebi->terminator()->GetSingleWordInOperand(0u) != cont_id) { |
| // Make unreachable, but leave the label. |
| KillAllInsts(&*ebi, false); |
| // Add unconditional branch to header. |
| assert(unreachable_continues.count(&*ebi)); |
| ebi->AddInstruction(MakeUnique<opt::Instruction>( |
| context(), SpvOpBranch, 0, 0, |
| std::initializer_list<opt::Operand>{ |
| {SPV_OPERAND_TYPE_ID, {cont_id}}})); |
| get_def_use_mgr()->AnalyzeInstUse(&*ebi->tail()); |
| context()->set_instr_block(&*ebi->tail(), &*ebi); |
| modified = true; |
| } |
| ++ebi; |
| } else if (!live_blocks.count(&*ebi)) { |
| // Kill this block. |
| KillAllInsts(&*ebi); |
| ebi = ebi.Erase(); |
| modified = true; |
| } else { |
| ++ebi; |
| } |
| } |
| |
| return modified; |
| } |
| |
| bool DeadBranchElimPass::EliminateDeadBranches(opt::Function* func) { |
| bool modified = false; |
| std::unordered_set<opt::BasicBlock*> live_blocks; |
| modified |= MarkLiveBlocks(func, &live_blocks); |
| |
| std::unordered_set<opt::BasicBlock*> unreachable_merges; |
| std::unordered_map<opt::BasicBlock*, opt::BasicBlock*> unreachable_continues; |
| MarkUnreachableStructuredTargets(live_blocks, &unreachable_merges, |
| &unreachable_continues); |
| modified |= FixPhiNodesInLiveBlocks(func, live_blocks, unreachable_continues); |
| modified |= EraseDeadBlocks(func, live_blocks, unreachable_merges, |
| unreachable_continues); |
| |
| return modified; |
| } |
| |
| void DeadBranchElimPass::Initialize(opt::IRContext* c) { |
| InitializeProcessing(c); |
| } |
| |
| Pass::Status DeadBranchElimPass::ProcessImpl() { |
| // Do not process if module contains OpGroupDecorate. Additional |
| // support required in KillNamesAndDecorates(). |
| // TODO(greg-lunarg): Add support for OpGroupDecorate |
| for (auto& ai : get_module()->annotations()) |
| if (ai.opcode() == SpvOpGroupDecorate) return Status::SuccessWithoutChange; |
| // Process all entry point functions |
| ProcessFunction pfn = [this](opt::Function* fp) { |
| return EliminateDeadBranches(fp); |
| }; |
| bool modified = ProcessReachableCallTree(pfn, context()); |
| return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange; |
| } |
| |
| DeadBranchElimPass::DeadBranchElimPass() {} |
| |
| Pass::Status DeadBranchElimPass::Process(opt::IRContext* module) { |
| Initialize(module); |
| return ProcessImpl(); |
| } |
| |
| } // namespace opt |
| } // namespace spvtools |