1 // Copyright (c) 2019 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/merge_blocks_reduction_opportunity.h"
16
17 #include "source/opt/block_merge_util.h"
18 #include "source/opt/ir_context.h"
19
20 namespace spvtools {
21 namespace reduce {
22
23 using opt::BasicBlock;
24 using opt::Function;
25 using opt::IRContext;
26
MergeBlocksReductionOpportunity(IRContext * context,Function * function,BasicBlock * block)27 MergeBlocksReductionOpportunity::MergeBlocksReductionOpportunity(
28 IRContext* context, Function* function, BasicBlock* block) {
29 // Precondition: the terminator has to be OpBranch.
30 assert(block->terminator()->opcode() == SpvOpBranch);
31 context_ = context;
32 function_ = function;
33 // Get the successor block associated with the OpBranch.
34 successor_block_ =
35 context->cfg()->block(block->terminator()->GetSingleWordInOperand(0));
36 }
37
PreconditionHolds()38 bool MergeBlocksReductionOpportunity::PreconditionHolds() {
39 // Merge block opportunities can disable each other.
40 // Example: Given blocks: A->B->C.
41 // A is a loop header; B and C are blocks in the loop; C ends with OpReturn.
42 // There are two opportunities: B and C can be merged with their predecessors.
43 // Merge C. B now ends with OpReturn. We now just have: A->B.
44 // Merge B is now disabled, as this would lead to A, a loop header, ending
45 // with an OpReturn, which is invalid.
46
47 const auto predecessors = context_->cfg()->preds(successor_block_->id());
48 assert(1 == predecessors.size() &&
49 "For a successor to be merged into its predecessor, exactly one "
50 "predecessor must be present.");
51 const uint32_t predecessor_id = predecessors[0];
52 BasicBlock* predecessor_block = context_->get_instr_block(predecessor_id);
53 return opt::blockmergeutil::CanMergeWithSuccessor(context_,
54 predecessor_block);
55 }
56
Apply()57 void MergeBlocksReductionOpportunity::Apply() {
58 // While the original block that targeted the successor may not exist anymore
59 // (it might have been merged with another block), some block must exist that
60 // targets the successor. Find it.
61
62 const auto predecessors = context_->cfg()->preds(successor_block_->id());
63 assert(1 == predecessors.size() &&
64 "For a successor to be merged into its predecessor, exactly one "
65 "predecessor must be present.");
66 const uint32_t predecessor_id = predecessors[0];
67
68 // We need an iterator pointing to the predecessor, hence the loop.
69 for (auto bi = function_->begin(); bi != function_->end(); ++bi) {
70 if (bi->id() == predecessor_id) {
71 opt::blockmergeutil::MergeWithSuccessor(context_, function_, bi);
72 // Block merging changes the control flow graph, so invalidate it.
73 context_->InvalidateAnalysesExceptFor(IRContext::Analysis::kAnalysisNone);
74 return;
75 }
76 }
77
78 assert(false &&
79 "Unreachable: we should have found a block with the desired id.");
80 }
81
82 } // namespace reduce
83 } // namespace spvtools
84