1 // Copyright (c) 2021 Alastair F. Donaldson
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_construct_to_block_reduction_opportunity.h"
16
17 namespace spvtools {
18 namespace reduce {
19
PreconditionHolds()20 bool StructuredConstructToBlockReductionOpportunity::PreconditionHolds() {
21 return context_->get_def_use_mgr()->GetDef(construct_header_) != nullptr;
22 }
23
Apply()24 void StructuredConstructToBlockReductionOpportunity::Apply() {
25 auto header_block = context_->cfg()->block(construct_header_);
26 auto merge_block = context_->cfg()->block(header_block->MergeBlockId());
27
28 auto* enclosing_function = header_block->GetParent();
29
30 // A region of blocks is defined in terms of dominators and post-dominators,
31 // so we compute these for the enclosing function.
32 auto* dominators = context_->GetDominatorAnalysis(enclosing_function);
33 auto* postdominators = context_->GetPostDominatorAnalysis(enclosing_function);
34
35 // For each block in the function, determine whether it is inside the region.
36 // If it is, delete it.
37 for (auto block_it = enclosing_function->begin();
38 block_it != enclosing_function->end();) {
39 if (header_block != &*block_it && merge_block != &*block_it &&
40 dominators->Dominates(header_block, &*block_it) &&
41 postdominators->Dominates(merge_block, &*block_it)) {
42 block_it = block_it.Erase();
43 } else {
44 ++block_it;
45 }
46 }
47 // Having removed some blocks from the module it is necessary to invalidate
48 // analyses, since the remaining patch-up work depends on various analyses
49 // which will otherwise reference blocks that have been deleted.
50 context_->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
51
52 // We demote the header of the region to a regular block by deleting its merge
53 // instruction.
54 context_->KillInst(header_block->GetMergeInst());
55
56 // The terminator for the header block is changed to be an unconditional
57 // branch to the merge block.
58 header_block->terminator()->SetOpcode(SpvOpBranch);
59 header_block->terminator()->SetInOperands(
60 {{SPV_OPERAND_TYPE_ID, {merge_block->id()}}});
61
62 // This is an intrusive change, so we invalidate all analyses.
63 context_->InvalidateAnalysesExceptFor(opt::IRContext::kAnalysisNone);
64 }
65
66 } // namespace reduce
67 } // namespace spvtools
68