| // 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 |