blob: 319b8d161c0bdc84c8da9062d426e7da52645c8e [file] [log] [blame]
// 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 "source/opt/dead_branch_elim_pass.h"
#include <list>
#include <memory>
#include <vector>
#include "source/cfa.h"
#include "source/opt/ir_context.h"
#include "source/opt/iterator.h"
#include "source/opt/struct_cfg_analysis.h"
#include "source/util/make_unique.h"
namespace spvtools {
namespace opt {
namespace {
constexpr uint32_t kBranchCondTrueLabIdInIdx = 1;
constexpr uint32_t kBranchCondFalseLabIdInIdx = 2;
} // namespace
bool DeadBranchElimPass::GetConstCondition(uint32_t condId, bool* condVal) {
bool condIsConst;
Instruction* cInst = get_def_use_mgr()->GetDef(condId);
switch (cInst->opcode()) {
case spv::Op::OpConstantNull:
case spv::Op::OpConstantFalse: {
*condVal = false;
condIsConst = true;
} break;
case spv::Op::OpConstantTrue: {
*condVal = true;
condIsConst = true;
} break;
case spv::Op::OpLogicalNot: {
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) {
Instruction* sInst = get_def_use_mgr()->GetDef(selId);
uint32_t typeId = sInst->type_id();
Instruction* typeInst = get_def_use_mgr()->GetDef(typeId);
if (!typeInst || (typeInst->opcode() != spv::Op::OpTypeInt)) return false;
// TODO(greg-lunarg): Support non-32 bit ints
if (typeInst->GetSingleWordInOperand(0) != 32) return false;
if (sInst->opcode() == spv::Op::OpConstant) {
*selVal = sInst->GetSingleWordInOperand(0);
return true;
} else if (sInst->opcode() == spv::Op::OpConstantNull) {
*selVal = 0;
return true;
}
return false;
}
void DeadBranchElimPass::AddBranch(uint32_t labelId, BasicBlock* bp) {
assert(get_def_use_mgr()->GetDef(labelId) != nullptr);
std::unique_ptr<Instruction> newBranch(
new Instruction(context(), spv::Op::OpBranch, 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));
}
BasicBlock* DeadBranchElimPass::GetParentBlock(uint32_t id) {
return context()->get_instr_block(get_def_use_mgr()->GetDef(id));
}
bool DeadBranchElimPass::MarkLiveBlocks(
Function* func, std::unordered_set<BasicBlock*>* live_blocks) {
std::vector<std::pair<BasicBlock*, uint32_t>> conditions_to_simplify;
std::unordered_set<BasicBlock*> blocks_with_backedge;
std::vector<BasicBlock*> stack;
stack.push_back(&*func->begin());
bool modified = false;
while (!stack.empty()) {
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) {
AddBlocksWithBackEdge(cont_id, block->id(), block->MergeBlockIdIfAny(),
&blocks_with_backedge);
}
Instruction* terminator = block->terminator();
uint32_t live_lab_id = 0;
// Check if the terminator has a single valid successor.
if (terminator->opcode() == spv::Op::OpBranchConditional) {
bool condVal;
if (GetConstCondition(terminator->GetSingleWordInOperand(0u), &condVal)) {
live_lab_id = terminator->GetSingleWordInOperand(
condVal ? kBranchCondTrueLabIdInIdx : kBranchCondFalseLabIdInIdx);
}
} else if (terminator->opcode() == spv::Op::OpSwitch) {
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 back edges unless it becomes a branch to the header. Every
// loop must have exactly one back edge to the loop header, so we cannot
// remove it.
bool simplify = false;
if (live_lab_id != 0) {
if (!blocks_with_backedge.count(block)) {
// This is not a back edge.
simplify = true;
} else {
const auto& struct_cfg_analysis = context()->GetStructuredCFGAnalysis();
uint32_t header_id = struct_cfg_analysis->ContainingLoop(block->id());
if (live_lab_id == header_id) {
// The new branch will be a branch to the header.
simplify = true;
}
}
}
if (simplify) {
conditions_to_simplify.push_back({block, live_lab_id});
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));
});
}
}
// Traverse |conditions_to_simplify| in reverse order. This is done so that
// we simplify nested constructs before simplifying the constructs that
// contain them.
for (auto b = conditions_to_simplify.rbegin();
b != conditions_to_simplify.rend(); ++b) {
modified |= SimplifyBranch(b->first, b->second);
}
return modified;
}
bool DeadBranchElimPass::SimplifyBranch(BasicBlock* block,
uint32_t live_lab_id) {
Instruction* merge_inst = block->GetMergeInst();
Instruction* terminator = block->terminator();
if (merge_inst && merge_inst->opcode() == spv::Op::OpSelectionMerge) {
if (merge_inst->NextNode()->opcode() == spv::Op::OpSwitch &&
SwitchHasNestedBreak(block->id())) {
if (terminator->NumInOperands() == 2) {
// We cannot remove the branch, and it already has a single case, so no
// work to do.
return false;
}
// We have to keep the switch because it has a nest break, so we
// remove all cases except for the live one.
Instruction::OperandList new_operands;
new_operands.push_back(terminator->GetInOperand(0));
new_operands.push_back({SPV_OPERAND_TYPE_ID, {live_lab_id}});
terminator->SetInOperands(std::move(new_operands));
context()->UpdateDefUse(terminator);
} else {
// Check if the merge instruction is still needed because of a
// non-nested break from the construct. Move the merge instruction if
// it is still needed.
StructuredCFGAnalysis* cfg_analysis =
context()->GetStructuredCFGAnalysis();
Instruction* first_break = FindFirstExitFromSelectionMerge(
live_lab_id, merge_inst->GetSingleWordInOperand(0),
cfg_analysis->LoopMergeBlock(live_lab_id),
cfg_analysis->LoopContinueBlock(live_lab_id),
cfg_analysis->SwitchMergeBlock(live_lab_id));
AddBranch(live_lab_id, block);
context()->KillInst(terminator);
if (first_break == nullptr) {
context()->KillInst(merge_inst);
} else {
merge_inst->RemoveFromList();
first_break->InsertBefore(std::unique_ptr<Instruction>(merge_inst));
context()->set_instr_block(merge_inst,
context()->get_instr_block(first_break));
}
}
} else {
AddBranch(live_lab_id, block);
context()->KillInst(terminator);
}
return true;
}
void DeadBranchElimPass::MarkUnreachableStructuredTargets(
const std::unordered_set<BasicBlock*>& live_blocks,
std::unordered_set<BasicBlock*>* unreachable_merges,
std::unordered_map<BasicBlock*, BasicBlock*>* unreachable_continues) {
for (auto block : live_blocks) {
if (auto merge_id = block->MergeBlockIdIfAny()) {
BasicBlock* merge_block = GetParentBlock(merge_id);
if (!live_blocks.count(merge_block)) {
unreachable_merges->insert(merge_block);
}
if (auto cont_id = block->ContinueBlockIdIfAny()) {
BasicBlock* cont_block = GetParentBlock(cont_id);
if (!live_blocks.count(cont_block)) {
(*unreachable_continues)[cont_block] = block;
}
}
}
}
}
bool DeadBranchElimPass::FixPhiNodesInLiveBlocks(
Function* func, const std::unordered_set<BasicBlock*>& live_blocks,
const std::unordered_map<BasicBlock*, 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() != spv::Op::OpPhi) {
break;
}
bool changed = false;
bool backedge_added = false;
Instruction* inst = &*iter;
std::vector<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) {
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() == spv::Op::OpUndef) {
// 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()->KillNamesAndDecorates(inst->result_id());
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(
Function* func, const std::unordered_set<BasicBlock*>& live_blocks,
const std::unordered_set<BasicBlock*>& unreachable_merges,
const std::unordered_map<BasicBlock*, BasicBlock*>& unreachable_continues) {
bool modified = false;
for (auto ebi = func->begin(); ebi != func->end();) {
if (unreachable_continues.count(&*ebi)) {
uint32_t cont_id = unreachable_continues.find(&*ebi)->second->id();
if (ebi->begin() != ebi->tail() ||
ebi->terminator()->opcode() != spv::Op::OpBranch ||
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<Instruction>(
context(), spv::Op::OpBranch, 0, 0,
std::initializer_list<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 (unreachable_merges.count(&*ebi)) {
if (ebi->begin() != ebi->tail() ||
ebi->terminator()->opcode() != spv::Op::OpUnreachable) {
// Make unreachable, but leave the label.
KillAllInsts(&*ebi, false);
// Add unreachable terminator.
ebi->AddInstruction(
MakeUnique<Instruction>(context(), spv::Op::OpUnreachable, 0, 0,
std::initializer_list<Operand>{}));
context()->AnalyzeUses(ebi->terminator());
context()->set_instr_block(ebi->terminator(), &*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(Function* func) {
if (func->IsDeclaration()) {
return false;
}
bool modified = false;
std::unordered_set<BasicBlock*> live_blocks;
modified |= MarkLiveBlocks(func, &live_blocks);
std::unordered_set<BasicBlock*> unreachable_merges;
std::unordered_map<BasicBlock*, 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::FixBlockOrder() {
context()->BuildInvalidAnalyses(IRContext::kAnalysisCFG |
IRContext::kAnalysisDominatorAnalysis);
// Reorders blocks according to DFS of dominator tree.
ProcessFunction reorder_dominators = [this](Function* function) {
DominatorAnalysis* dominators = context()->GetDominatorAnalysis(function);
std::vector<BasicBlock*> blocks;
for (auto iter = dominators->GetDomTree().begin();
iter != dominators->GetDomTree().end(); ++iter) {
if (iter->id() != 0) {
blocks.push_back(iter->bb_);
}
}
for (uint32_t i = 1; i < blocks.size(); ++i) {
function->MoveBasicBlockToAfter(blocks[i]->id(), blocks[i - 1]);
}
return true;
};
// Reorders blocks according to structured order.
ProcessFunction reorder_structured = [](Function* function) {
function->ReorderBasicBlocksInStructuredOrder();
return true;
};
// Structured order is more intuitive so use it where possible.
if (context()->get_feature_mgr()->HasCapability(spv::Capability::Shader)) {
context()->ProcessReachableCallTree(reorder_structured);
} else {
context()->ProcessReachableCallTree(reorder_dominators);
}
}
Pass::Status DeadBranchElimPass::Process() {
// 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() == spv::Op::OpGroupDecorate)
return Status::SuccessWithoutChange;
// Process all entry point functions
ProcessFunction pfn = [this](Function* fp) {
return EliminateDeadBranches(fp);
};
bool modified = context()->ProcessReachableCallTree(pfn);
if (modified) FixBlockOrder();
return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
}
Instruction* DeadBranchElimPass::FindFirstExitFromSelectionMerge(
uint32_t start_block_id, uint32_t merge_block_id, uint32_t loop_merge_id,
uint32_t loop_continue_id, uint32_t switch_merge_id) {
// To find the "first" exit, we follow branches looking for a conditional
// branch that is not in a nested construct and is not the header of a new
// construct. We follow the control flow from |start_block_id| to find the
// first one.
while (start_block_id != merge_block_id && start_block_id != loop_merge_id &&
start_block_id != loop_continue_id) {
BasicBlock* start_block = context()->get_instr_block(start_block_id);
Instruction* branch = start_block->terminator();
uint32_t next_block_id = 0;
switch (branch->opcode()) {
case spv::Op::OpBranchConditional:
next_block_id = start_block->MergeBlockIdIfAny();
if (next_block_id == 0) {
// If a possible target is the |loop_merge_id| or |loop_continue_id|,
// which are not the current merge node, then we continue the search
// with the other target.
for (uint32_t i = 1; i < 3; i++) {
if (branch->GetSingleWordInOperand(i) == loop_merge_id &&
loop_merge_id != merge_block_id) {
next_block_id = branch->GetSingleWordInOperand(3 - i);
break;
}
if (branch->GetSingleWordInOperand(i) == loop_continue_id &&
loop_continue_id != merge_block_id) {
next_block_id = branch->GetSingleWordInOperand(3 - i);
break;
}
if (branch->GetSingleWordInOperand(i) == switch_merge_id &&
switch_merge_id != merge_block_id) {
next_block_id = branch->GetSingleWordInOperand(3 - i);
break;
}
}
if (next_block_id == 0) {
return branch;
}
}
break;
case spv::Op::OpSwitch:
next_block_id = start_block->MergeBlockIdIfAny();
if (next_block_id == 0) {
// A switch with no merge instructions can have at most 5 targets:
// a. |merge_block_id|
// b. |loop_merge_id|
// c. |loop_continue_id|
// d. |switch_merge_id|
// e. 1 block inside the current region.
//
// Note that because this is a switch, |merge_block_id| must equal
// |switch_merge_id|.
//
// This leads to a number of cases of what to do.
//
// 1. Does not jump to a block inside of the current construct. In
// this case, there is not conditional break, so we should return
// |nullptr|.
//
// 2. Jumps to |merge_block_id| and a block inside the current
// construct. In this case, this branch conditionally break to the
// end of the current construct, so return the current branch.
//
// 3. Otherwise, this branch may break, but not to the current merge
// block. So we continue with the block that is inside the loop.
bool found_break = false;
for (uint32_t i = 1; i < branch->NumInOperands(); i += 2) {
uint32_t target = branch->GetSingleWordInOperand(i);
if (target == merge_block_id) {
found_break = true;
} else if (target != loop_merge_id && target != loop_continue_id) {
next_block_id = branch->GetSingleWordInOperand(i);
}
}
if (next_block_id == 0) {
// Case 1.
return nullptr;
}
if (found_break) {
// Case 2.
return branch;
}
// The fall through is case 3.
}
break;
case spv::Op::OpBranch:
// Need to check if this is the header of a loop nested in the
// selection construct.
next_block_id = start_block->MergeBlockIdIfAny();
if (next_block_id == 0) {
next_block_id = branch->GetSingleWordInOperand(0);
}
break;
default:
return nullptr;
}
start_block_id = next_block_id;
}
return nullptr;
}
void DeadBranchElimPass::AddBlocksWithBackEdge(
uint32_t cont_id, uint32_t header_id, uint32_t merge_id,
std::unordered_set<BasicBlock*>* blocks_with_back_edges) {
std::unordered_set<uint32_t> visited;
visited.insert(cont_id);
visited.insert(header_id);
visited.insert(merge_id);
std::vector<uint32_t> work_list;
work_list.push_back(cont_id);
while (!work_list.empty()) {
uint32_t bb_id = work_list.back();
work_list.pop_back();
BasicBlock* bb = context()->get_instr_block(bb_id);
bool has_back_edge = false;
bb->ForEachSuccessorLabel([header_id, &visited, &work_list,
&has_back_edge](uint32_t* succ_label_id) {
if (visited.insert(*succ_label_id).second) {
work_list.push_back(*succ_label_id);
}
if (*succ_label_id == header_id) {
has_back_edge = true;
}
});
if (has_back_edge) {
blocks_with_back_edges->insert(bb);
}
}
}
bool DeadBranchElimPass::SwitchHasNestedBreak(uint32_t switch_header_id) {
std::vector<BasicBlock*> block_in_construct;
BasicBlock* start_block = context()->get_instr_block(switch_header_id);
uint32_t merge_block_id = start_block->MergeBlockIdIfAny();
StructuredCFGAnalysis* cfg_analysis = context()->GetStructuredCFGAnalysis();
return !get_def_use_mgr()->WhileEachUser(
merge_block_id,
[this, cfg_analysis, switch_header_id](Instruction* inst) {
if (!inst->IsBranch()) {
return true;
}
BasicBlock* bb = context()->get_instr_block(inst);
if (bb->id() == switch_header_id) {
return true;
}
return (cfg_analysis->ContainingConstruct(inst) == switch_header_id &&
bb->GetMergeInst() == nullptr);
});
}
} // namespace opt
} // namespace spvtools