| 1 |
// Copyright (c) 2018 Google LLC |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 |
// you may not use this file except in compliance with the License. |
| 5 |
// You may obtain a copy of the License at |
| 6 |
// |
| 7 |
// http://www.apache.org/licenses/LICENSE-2.0 |
| 8 |
// |
| 9 |
// Unless required by applicable law or agreed to in writing, software |
| 10 |
// distributed under the License is distributed on an "AS IS" BASIS, |
| 11 |
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 |
// See the License for the specific language governing permissions and |
| 13 |
// limitations under the License. |
| 14 |
|
| 15 |
#include "source/reduce/structured_loop_to_selection_reduction_opportunity.h" |
| 16 |
|
| 17 |
#include "source/opt/aggressive_dead_code_elim_pass.h" |
| 18 |
#include "source/opt/ir_context.h" |
| 19 |
#include "source/reduce/reduction_util.h" |
| 20 |
|
| 21 |
namespace spvtools { |
| 22 |
namespace reduce { |
| 23 |
|
| 24 |
namespace { |
| 25 |
const uint32_t kMergeNodeIndex = 0; |
| 26 |
} // namespace |
| 27 |
|
| 28 |
bool StructuredLoopToSelectionReductionOpportunity::PreconditionHolds() { |
| 29 |
// Is the loop header reachable? |
| 30 |
return loop_construct_header_->GetLabel() |
| 31 |
->context() |
| 32 |
->GetDominatorAnalysis(enclosing_function_) |
| 33 |
->IsReachable(loop_construct_header_); |
| 34 |
} |
| 35 |
|
| 36 |
void StructuredLoopToSelectionReductionOpportunity::Apply() { |
| 37 |
// Force computation of dominator analysis, CFG and structured CFG analysis |
| 38 |
// before we start to mess with edges in the function. |
| 39 |
context_->GetDominatorAnalysis(enclosing_function_); |
| 40 |
context_->cfg(); |
| 41 |
context_->GetStructuredCFGAnalysis(); |
| 42 |
|
| 43 |
// (1) Redirect edges that point to the loop's continue target to their |
| 44 |
// closest merge block. |
| 45 |
RedirectToClosestMergeBlock(loop_construct_header_->ContinueBlockId()); |
| 46 |
|
| 47 |
// (2) Redirect edges that point to the loop's merge block to their closest |
| 48 |
// merge block (which might be that of an enclosing selection, for instance). |
| 49 |
RedirectToClosestMergeBlock(loop_construct_header_->MergeBlockId()); |
| 50 |
|
| 51 |
// (3) Turn the loop construct header into a selection. |
| 52 |
ChangeLoopToSelection(); |
| 53 |
|
| 54 |
// We have made control flow changes that do not preserve the analyses that |
| 55 |
// were performed. |
| 56 |
context_->InvalidateAnalysesExceptFor( |
| 57 |
opt::IRContext::Analysis::kAnalysisNone); |
| 58 |
|
| 59 |
// (4) By changing CFG edges we may have created scenarios where ids are used |
| 60 |
// without being dominated; we fix instances of this. |
| 61 |
FixNonDominatedIdUses(); |
| 62 |
|
| 63 |
// Invalidate the analyses we just used. |
| 64 |
context_->InvalidateAnalysesExceptFor( |
| 65 |
opt::IRContext::Analysis::kAnalysisNone); |
| 66 |
} |
| 67 |
|
| 68 |
void StructuredLoopToSelectionReductionOpportunity::RedirectToClosestMergeBlock( |
| 69 |
uint32_t original_target_id) { |
| 70 |
// Consider every predecessor of the node with respect to which edges should |
| 71 |
// be redirected. |
| 72 |
std::set<uint32_t> already_seen; |
| 73 |
for (auto pred : context_->cfg()->preds(original_target_id)) { |
| 74 |
if (already_seen.find(pred) != already_seen.end()) { |
| 75 |
// We have already handled this predecessor (this scenario can arise if |
| 76 |
// there are multiple edges from a block b to original_target_id). |
| 77 |
continue; |
| 78 |
} |
| 79 |
already_seen.insert(pred); |
| 80 |
|
| 81 |
if (!context_->GetDominatorAnalysis(enclosing_function_) |
| 82 |
->IsReachable(pred)) { |
| 83 |
// We do not care about unreachable predecessors (and dominance |
| 84 |
// information, and thus the notion of structured control flow, makes |
| 85 |
// little sense for unreachable blocks). |
| 86 |
continue; |
| 87 |
} |
| 88 |
// Find the merge block of the structured control construct that most |
| 89 |
// tightly encloses the predecessor. |
| 90 |
uint32_t new_merge_target; |
| 91 |
// The structured CFG analysis deliberately does not regard a header as |
| 92 |
// belonging to the structure that it heads. We want it to, so handle this |
| 93 |
// case specially. |
| 94 |
if (context_->cfg()->block(pred)->MergeBlockIdIfAny()) { |
| 95 |
new_merge_target = context_->cfg()->block(pred)->MergeBlockIdIfAny(); |
| 96 |
} else { |
| 97 |
new_merge_target = context_->GetStructuredCFGAnalysis()->MergeBlock(pred); |
| 98 |
} |
| 99 |
assert(new_merge_target != pred); |
| 100 |
|
| 101 |
if (!new_merge_target) { |
| 102 |
// If the loop being transformed is outermost, and the predecessor is |
| 103 |
// part of that loop's continue construct, there will be no such |
| 104 |
// enclosing control construct. In this case, the continue construct |
| 105 |
// will become unreachable anyway, so it is fine not to redirect the |
| 106 |
// edge. |
| 107 |
continue; |
| 108 |
} |
| 109 |
|
| 110 |
if (new_merge_target != original_target_id) { |
| 111 |
// Redirect the edge if it doesn't already point to the desired block. |
| 112 |
RedirectEdge(pred, original_target_id, new_merge_target); |
| 113 |
} |
| 114 |
} |
| 115 |
} |
| 116 |
|
| 117 |
void StructuredLoopToSelectionReductionOpportunity::RedirectEdge( |
| 118 |
uint32_t source_id, uint32_t original_target_id, uint32_t new_target_id) { |
| 119 |
// Redirect edge source_id->original_target_id to edge |
| 120 |
// source_id->new_target_id, where the blocks involved are all different. |
| 121 |
assert(source_id != original_target_id); |
| 122 |
assert(source_id != new_target_id); |
| 123 |
assert(original_target_id != new_target_id); |
| 124 |
|
| 125 |
// original_target_id must either be the merge target or continue construct |
| 126 |
// for the loop being operated on. |
| 127 |
assert(original_target_id == loop_construct_header_->MergeBlockId() || |
| 128 |
original_target_id == loop_construct_header_->ContinueBlockId()); |
| 129 |
|
| 130 |
auto terminator = context_->cfg()->block(source_id)->terminator(); |
| 131 |
|
| 132 |
// Figure out which operands of the terminator need to be considered for |
| 133 |
// redirection. |
| 134 |
std::vector<uint32_t> operand_indices; |
| 135 |
if (terminator->opcode() == SpvOpBranch) { |
| 136 |
operand_indices = {0}; |
| 137 |
} else if (terminator->opcode() == SpvOpBranchConditional) { |
| 138 |
operand_indices = {1, 2}; |
| 139 |
} else { |
| 140 |
assert(terminator->opcode() == SpvOpSwitch); |
| 141 |
for (uint32_t label_index = 1; label_index < terminator->NumOperands(); |
| 142 |
label_index += 2) { |
| 143 |
operand_indices.push_back(label_index); |
| 144 |
} |
| 145 |
} |
| 146 |
|
| 147 |
// Redirect the relevant operands, asserting that at least one redirection is |
| 148 |
// made. |
| 149 |
bool redirected = false; |
| 150 |
for (auto operand_index : operand_indices) { |
| 151 |
if (terminator->GetSingleWordOperand(operand_index) == original_target_id) { |
| 152 |
terminator->SetOperand(operand_index, {new_target_id}); |
| 153 |
redirected = true; |
| 154 |
} |
| 155 |
} |
| 156 |
(void)(redirected); |
| 157 |
assert(redirected); |
| 158 |
|
| 159 |
// The old and new targets may have phi instructions; these will need to |
| 160 |
// respect the change in edges. |
| 161 |
AdaptPhiInstructionsForRemovedEdge( |
| 162 |
source_id, context_->cfg()->block(original_target_id)); |
| 163 |
AdaptPhiInstructionsForAddedEdge(source_id, |
| 164 |
context_->cfg()->block(new_target_id)); |
| 165 |
} |
| 166 |
|
| 167 |
void StructuredLoopToSelectionReductionOpportunity:: |
| 168 |
AdaptPhiInstructionsForAddedEdge(uint32_t from_id, |
| 169 |
opt::BasicBlock* to_block) { |
| 170 |
to_block->ForEachPhiInst([this, &from_id](opt::Instruction* phi_inst) { |
| 171 |
// Add to the phi operand an (undef, from_id) pair to reflect the added |
| 172 |
// edge. |
| 173 |
auto undef_id = FindOrCreateGlobalUndef(context_, phi_inst->type_id()); |
| 174 |
phi_inst->AddOperand(opt::Operand(SPV_OPERAND_TYPE_ID, {undef_id})); |
| 175 |
phi_inst->AddOperand(opt::Operand(SPV_OPERAND_TYPE_ID, {from_id})); |
| 176 |
}); |
| 177 |
} |
| 178 |
|
| 179 |
void StructuredLoopToSelectionReductionOpportunity::ChangeLoopToSelection() { |
| 180 |
// Change the merge instruction from OpLoopMerge to OpSelectionMerge, with |
| 181 |
// the same merge block. |
| 182 |
auto loop_merge_inst = loop_construct_header_->GetLoopMergeInst(); |
| 183 |
auto const loop_merge_block_id = |
| 184 |
loop_merge_inst->GetSingleWordOperand(kMergeNodeIndex); |
| 185 |
loop_merge_inst->SetOpcode(SpvOpSelectionMerge); |
| 186 |
loop_merge_inst->ReplaceOperands( |
| 187 |
{{loop_merge_inst->GetOperand(kMergeNodeIndex).type, |
| 188 |
{loop_merge_block_id}}, |
| 189 |
{SPV_OPERAND_TYPE_SELECTION_CONTROL, {SpvSelectionControlMaskNone}}}); |
| 190 |
|
| 191 |
// The loop header either finishes with OpBranch or OpBranchConditional. |
| 192 |
// The latter is fine for a selection. In the former case we need to turn |
| 193 |
// it into OpBranchConditional. We use "true" as the condition, and make |
| 194 |
// the "else" branch be the merge block. |
| 195 |
auto terminator = loop_construct_header_->terminator(); |
| 196 |
if (terminator->opcode() == SpvOpBranch) { |
| 197 |
opt::analysis::Bool temp; |
| 198 |
const opt::analysis::Bool* bool_type = |
| 199 |
context_->get_type_mgr()->GetRegisteredType(&temp)->AsBool(); |
| 200 |
auto const_mgr = context_->get_constant_mgr(); |
| 201 |
auto true_const = const_mgr->GetConstant(bool_type, {1}); |
| 202 |
auto true_const_result_id = |
| 203 |
const_mgr->GetDefiningInstruction(true_const)->result_id(); |
| 204 |
auto original_branch_id = terminator->GetSingleWordOperand(0); |
| 205 |
terminator->SetOpcode(SpvOpBranchConditional); |
| 206 |
terminator->ReplaceOperands({{SPV_OPERAND_TYPE_ID, {true_const_result_id}}, |
| 207 |
{SPV_OPERAND_TYPE_ID, {original_branch_id}}, |
| 208 |
{SPV_OPERAND_TYPE_ID, {loop_merge_block_id}}}); |
| 209 |
if (original_branch_id != loop_merge_block_id) { |
| 210 |
AdaptPhiInstructionsForAddedEdge( |
| 211 |
loop_construct_header_->id(), |
| 212 |
context_->cfg()->block(loop_merge_block_id)); |
| 213 |
} |
| 214 |
} |
| 215 |
} |
| 216 |
|
| 217 |
void StructuredLoopToSelectionReductionOpportunity::FixNonDominatedIdUses() { |
| 218 |
// Consider each instruction in the function. |
| 219 |
for (auto& block : *enclosing_function_) { |
| 220 |
for (auto& def : block) { |
| 221 |
if (def.opcode() == SpvOpVariable) { |
| 222 |
// Variables are defined at the start of the function, and can be |
| 223 |
// accessed by all blocks, even by unreachable blocks that have no |
| 224 |
// dominators, so we do not need to worry about them. |
| 225 |
continue; |
| 226 |
} |
| 227 |
context_->get_def_use_mgr()->ForEachUse(&def, [this, &block, &def]( |
| 228 |
opt::Instruction* use, |
| 229 |
uint32_t index) { |
| 230 |
// Ignore uses outside of blocks, such as in OpDecorate. |
| 231 |
if (context_->get_instr_block(use) == nullptr) { |
| 232 |
return; |
| 233 |
} |
| 234 |
// If a use is not appropriately dominated by its definition, |
| 235 |
// replace the use with an OpUndef, unless the definition is an |
| 236 |
// access chain, in which case replace it with some (possibly fresh) |
| 237 |
// variable (as we cannot load from / store to OpUndef). |
| 238 |
if (!DefinitionSufficientlyDominatesUse(&def, use, index, block)) { |
| 239 |
if (def.opcode() == SpvOpAccessChain) { |
| 240 |
auto pointer_type = |
| 241 |
context_->get_type_mgr()->GetType(def.type_id())->AsPointer(); |
| 242 |
switch (pointer_type->storage_class()) { |
| 243 |
case SpvStorageClassFunction: |
| 244 |
use->SetOperand( |
| 245 |
index, {FindOrCreateFunctionVariable( |
| 246 |
context_, enclosing_function_, |
| 247 |
context_->get_type_mgr()->GetId(pointer_type))}); |
| 248 |
break; |
| 249 |
default: |
| 250 |
// TODO(2183) Need to think carefully about whether it makes |
| 251 |
// sense to add new variables for all storage classes; it's |
| 252 |
// fine for Private but might not be OK for input/output |
| 253 |
// storage classes for example. |
| 254 |
use->SetOperand( |
| 255 |
index, {FindOrCreateGlobalVariable( |
| 256 |
context_, |
| 257 |
context_->get_type_mgr()->GetId(pointer_type))}); |
| 258 |
break; |
| 259 |
break; |
| 260 |
} |
| 261 |
} else { |
| 262 |
use->SetOperand(index, |
| 263 |
{FindOrCreateGlobalUndef(context_, def.type_id())}); |
| 264 |
} |
| 265 |
} |
| 266 |
}); |
| 267 |
} |
| 268 |
} |
| 269 |
} |
| 270 |
|
| 271 |
bool StructuredLoopToSelectionReductionOpportunity:: |
| 272 |
DefinitionSufficientlyDominatesUse(opt::Instruction* def, |
| 273 |
opt::Instruction* use, |
| 274 |
uint32_t use_index, |
| 275 |
opt::BasicBlock& def_block) { |
| 276 |
if (use->opcode() == SpvOpPhi) { |
| 277 |
// A use in a phi doesn't need to be dominated by its definition, but the |
| 278 |
// associated parent block does need to be dominated by the definition. |
| 279 |
return context_->GetDominatorAnalysis(enclosing_function_) |
| 280 |
->Dominates(def_block.id(), use->GetSingleWordOperand(use_index + 1)); |
| 281 |
} |
| 282 |
// In non-phi cases, a use needs to be dominated by its definition. |
| 283 |
return context_->GetDominatorAnalysis(enclosing_function_) |
| 284 |
->Dominates(def, use); |
| 285 |
} |
| 286 |
|
| 287 |
} // namespace reduce |
| 288 |
} // namespace spvtools |