blob: 45b95285eafb39f2c858e2417562a8f096f956fd [file] [log] [blame]
// Copyright (c) 2018 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 "source/reduce/structured_loop_to_selection_reduction_opportunity.h"
#include "source/opt/aggressive_dead_code_elim_pass.h"
#include "source/opt/ir_context.h"
#include "source/reduce/reduction_util.h"
namespace spvtools {
namespace reduce {
namespace {
const uint32_t kMergeNodeIndex = 0;
} // namespace
bool StructuredLoopToSelectionReductionOpportunity::PreconditionHolds() {
// Is the loop header reachable?
return loop_construct_header_->GetLabel()->context()->IsReachable(
*loop_construct_header_);
}
void StructuredLoopToSelectionReductionOpportunity::Apply() {
// Force computation of dominator analysis, CFG and structured CFG analysis
// before we start to mess with edges in the function.
context_->GetDominatorAnalysis(loop_construct_header_->GetParent());
context_->cfg();
context_->GetStructuredCFGAnalysis();
// (1) Redirect edges that point to the loop's continue target to their
// closest merge block.
RedirectToClosestMergeBlock(loop_construct_header_->ContinueBlockId());
// (2) Redirect edges that point to the loop's merge block to their closest
// merge block (which might be that of an enclosing selection, for instance).
RedirectToClosestMergeBlock(loop_construct_header_->MergeBlockId());
// (3) Turn the loop construct header into a selection.
ChangeLoopToSelection();
// We have made control flow changes that do not preserve the analyses that
// were performed.
context_->InvalidateAnalysesExceptFor(
opt::IRContext::Analysis::kAnalysisNone);
// (4) By changing CFG edges we may have created scenarios where ids are used
// without being dominated; we fix instances of this.
FixNonDominatedIdUses();
// Invalidate the analyses we just used.
context_->InvalidateAnalysesExceptFor(
opt::IRContext::Analysis::kAnalysisNone);
}
void StructuredLoopToSelectionReductionOpportunity::RedirectToClosestMergeBlock(
uint32_t original_target_id) {
// Consider every predecessor of the node with respect to which edges should
// be redirected.
std::set<uint32_t> already_seen;
for (auto pred : context_->cfg()->preds(original_target_id)) {
if (already_seen.find(pred) != already_seen.end()) {
// We have already handled this predecessor (this scenario can arise if
// there are multiple edges from a block b to original_target_id).
continue;
}
already_seen.insert(pred);
if (!context_->IsReachable(*context_->cfg()->block(pred))) {
// We do not care about unreachable predecessors (and dominance
// information, and thus the notion of structured control flow, makes
// little sense for unreachable blocks).
continue;
}
// Find the merge block of the structured control construct that most
// tightly encloses the predecessor.
uint32_t new_merge_target;
// The structured CFG analysis deliberately does not regard a header as
// belonging to the structure that it heads. We want it to, so handle this
// case specially.
if (context_->cfg()->block(pred)->MergeBlockIdIfAny()) {
new_merge_target = context_->cfg()->block(pred)->MergeBlockIdIfAny();
} else {
new_merge_target = context_->GetStructuredCFGAnalysis()->MergeBlock(pred);
}
assert(new_merge_target != pred);
if (!new_merge_target) {
// If the loop being transformed is outermost, and the predecessor is
// part of that loop's continue construct, there will be no such
// enclosing control construct. In this case, the continue construct
// will become unreachable anyway, so it is fine not to redirect the
// edge.
continue;
}
if (new_merge_target != original_target_id) {
// Redirect the edge if it doesn't already point to the desired block.
RedirectEdge(pred, original_target_id, new_merge_target);
}
}
}
void StructuredLoopToSelectionReductionOpportunity::RedirectEdge(
uint32_t source_id, uint32_t original_target_id, uint32_t new_target_id) {
// Redirect edge source_id->original_target_id to edge
// source_id->new_target_id, where the blocks involved are all different.
assert(source_id != original_target_id);
assert(source_id != new_target_id);
assert(original_target_id != new_target_id);
// original_target_id must either be the merge target or continue construct
// for the loop being operated on.
assert(original_target_id == loop_construct_header_->MergeBlockId() ||
original_target_id == loop_construct_header_->ContinueBlockId());
auto terminator = context_->cfg()->block(source_id)->terminator();
// Figure out which operands of the terminator need to be considered for
// redirection.
std::vector<uint32_t> operand_indices;
if (terminator->opcode() == spv::Op::OpBranch) {
operand_indices = {0};
} else if (terminator->opcode() == spv::Op::OpBranchConditional) {
operand_indices = {1, 2};
} else {
assert(terminator->opcode() == spv::Op::OpSwitch);
for (uint32_t label_index = 1; label_index < terminator->NumOperands();
label_index += 2) {
operand_indices.push_back(label_index);
}
}
// Redirect the relevant operands, asserting that at least one redirection is
// made.
bool redirected = false;
for (auto operand_index : operand_indices) {
if (terminator->GetSingleWordOperand(operand_index) == original_target_id) {
terminator->SetOperand(operand_index, {new_target_id});
redirected = true;
}
}
(void)(redirected);
assert(redirected);
// The old and new targets may have phi instructions; these will need to
// respect the change in edges.
AdaptPhiInstructionsForRemovedEdge(
source_id, context_->cfg()->block(original_target_id));
AdaptPhiInstructionsForAddedEdge(source_id,
context_->cfg()->block(new_target_id));
}
void StructuredLoopToSelectionReductionOpportunity::
AdaptPhiInstructionsForAddedEdge(uint32_t from_id,
opt::BasicBlock* to_block) {
to_block->ForEachPhiInst([this, &from_id](opt::Instruction* phi_inst) {
// Add to the phi operand an (undef, from_id) pair to reflect the added
// edge.
auto undef_id = FindOrCreateGlobalUndef(context_, phi_inst->type_id());
phi_inst->AddOperand(opt::Operand(SPV_OPERAND_TYPE_ID, {undef_id}));
phi_inst->AddOperand(opt::Operand(SPV_OPERAND_TYPE_ID, {from_id}));
});
}
void StructuredLoopToSelectionReductionOpportunity::ChangeLoopToSelection() {
// Change the merge instruction from OpLoopMerge to OpSelectionMerge, with
// the same merge block.
auto loop_merge_inst = loop_construct_header_->GetLoopMergeInst();
auto const loop_merge_block_id =
loop_merge_inst->GetSingleWordOperand(kMergeNodeIndex);
loop_merge_inst->SetOpcode(spv::Op::OpSelectionMerge);
loop_merge_inst->ReplaceOperands(
{{loop_merge_inst->GetOperand(kMergeNodeIndex).type,
{loop_merge_block_id}},
{SPV_OPERAND_TYPE_SELECTION_CONTROL,
{uint32_t(spv::SelectionControlMask::MaskNone)}}});
// The loop header either finishes with OpBranch or OpBranchConditional.
// The latter is fine for a selection. In the former case we need to turn
// it into OpBranchConditional. We use "true" as the condition, and make
// the "else" branch be the merge block.
auto terminator = loop_construct_header_->terminator();
if (terminator->opcode() == spv::Op::OpBranch) {
opt::analysis::Bool temp;
const opt::analysis::Bool* bool_type =
context_->get_type_mgr()->GetRegisteredType(&temp)->AsBool();
auto const_mgr = context_->get_constant_mgr();
auto true_const = const_mgr->GetConstant(bool_type, {1});
auto true_const_result_id =
const_mgr->GetDefiningInstruction(true_const)->result_id();
auto original_branch_id = terminator->GetSingleWordOperand(0);
terminator->SetOpcode(spv::Op::OpBranchConditional);
terminator->ReplaceOperands({{SPV_OPERAND_TYPE_ID, {true_const_result_id}},
{SPV_OPERAND_TYPE_ID, {original_branch_id}},
{SPV_OPERAND_TYPE_ID, {loop_merge_block_id}}});
if (original_branch_id != loop_merge_block_id) {
AdaptPhiInstructionsForAddedEdge(
loop_construct_header_->id(),
context_->cfg()->block(loop_merge_block_id));
}
}
}
void StructuredLoopToSelectionReductionOpportunity::FixNonDominatedIdUses() {
// Consider each instruction in the function.
for (auto& block : *loop_construct_header_->GetParent()) {
for (auto& def : block) {
if (def.opcode() == spv::Op::OpVariable) {
// Variables are defined at the start of the function, and can be
// accessed by all blocks, even by unreachable blocks that have no
// dominators, so we do not need to worry about them.
continue;
}
context_->get_def_use_mgr()->ForEachUse(&def, [this, &block, &def](
opt::Instruction* use,
uint32_t index) {
// Ignore uses outside of blocks, such as in OpDecorate.
if (context_->get_instr_block(use) == nullptr) {
return;
}
// If a use is not appropriately dominated by its definition,
// replace the use with an OpUndef, unless the definition is an
// access chain, in which case replace it with some (possibly fresh)
// variable (as we cannot load from / store to OpUndef).
if (!DefinitionSufficientlyDominatesUse(&def, use, index, block)) {
if (def.opcode() == spv::Op::OpAccessChain) {
auto pointer_type =
context_->get_type_mgr()->GetType(def.type_id())->AsPointer();
switch (pointer_type->storage_class()) {
case spv::StorageClass::Function:
use->SetOperand(
index, {FindOrCreateFunctionVariable(
context_, loop_construct_header_->GetParent(),
context_->get_type_mgr()->GetId(pointer_type))});
break;
default:
// TODO(2183) Need to think carefully about whether it makes
// sense to add new variables for all storage classes; it's
// fine for Private but might not be OK for input/output
// storage classes for example.
use->SetOperand(
index, {FindOrCreateGlobalVariable(
context_,
context_->get_type_mgr()->GetId(pointer_type))});
break;
break;
}
} else {
use->SetOperand(index,
{FindOrCreateGlobalUndef(context_, def.type_id())});
}
}
});
}
}
}
bool StructuredLoopToSelectionReductionOpportunity::
DefinitionSufficientlyDominatesUse(opt::Instruction* def,
opt::Instruction* use,
uint32_t use_index,
opt::BasicBlock& def_block) {
if (use->opcode() == spv::Op::OpPhi) {
// A use in a phi doesn't need to be dominated by its definition, but the
// associated parent block does need to be dominated by the definition.
return context_->GetDominatorAnalysis(loop_construct_header_->GetParent())
->Dominates(def_block.id(), use->GetSingleWordOperand(use_index + 1));
}
// In non-phi cases, a use needs to be dominated by its definition.
return context_->GetDominatorAnalysis(loop_construct_header_->GetParent())
->Dominates(def, use);
}
} // namespace reduce
} // namespace spvtools