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 "structured_loop_to_selection_reduction_pass.h"
16 #include "structured_loop_to_selection_reduction_opportunity.h"
17
18 namespace spvtools {
19 namespace reduce {
20
21 using namespace opt;
22
23 namespace {
24 const uint32_t kMergeNodeIndex = 0;
25 const uint32_t kContinueNodeIndex = 1;
26 } // namespace
27
28 std::vector<std::unique_ptr<ReductionOpportunity>>
GetAvailableOpportunities(opt::IRContext * context) const29 StructuredLoopToSelectionReductionPass::GetAvailableOpportunities(
30 opt::IRContext* context) const {
31 std::vector<std::unique_ptr<ReductionOpportunity>> result;
32
33 std::set<uint32_t> merge_block_ids;
34 for (auto& function : *context->module()) {
35 for (auto& block : function) {
36 auto merge_inst = block.GetMergeInst();
37 if (merge_inst) {
38 merge_block_ids.insert(
39 merge_inst->GetSingleWordOperand(kMergeNodeIndex));
40 }
41 }
42 }
43
44 // Consider each loop construct header in the module.
45 for (auto& function : *context->module()) {
46 for (auto& block : function) {
47 auto loop_merge_inst = block.GetLoopMergeInst();
48 if (!loop_merge_inst) {
49 // This is not a loop construct header.
50 continue;
51 }
52
53 // Check whether the loop construct's continue target is the merge block
54 // of some structured control flow construct. If it is, we cautiously do
55 // not consider applying a transformation.
56 if (merge_block_ids.find(loop_merge_inst->GetSingleWordOperand(
57 kContinueNodeIndex)) != merge_block_ids.end()) {
58 continue;
59 }
60
61 // Check whether the loop construct header dominates its merge block.
62 // If not, the merge block must be unreachable in the control flow graph
63 // so we cautiously do not consider applying a transformation.
64 auto merge_block_id =
65 loop_merge_inst->GetSingleWordInOperand(kMergeNodeIndex);
66 if (!context->GetDominatorAnalysis(&function)->Dominates(
67 block.id(), merge_block_id)) {
68 continue;
69 }
70
71 // Check whether the loop construct merge block postdominates the loop
72 // construct header. If not (e.g. because the loop contains OpReturn,
73 // OpKill or OpUnreachable), we cautiously do not consider applying
74 // a transformation.
75 if (!context->GetPostDominatorAnalysis(&function)->Dominates(
76 merge_block_id, block.id())) {
77 continue;
78 }
79
80 // We can turn this structured loop into a selection, so add the
81 // opportunity to do so.
82 result.push_back(
83 MakeUnique<StructuredLoopToSelectionReductionOpportunity>(
84 context, &block, &function));
85 }
86 }
87 return result;
88 }
89
GetName() const90 std::string StructuredLoopToSelectionReductionPass::GetName() const {
91 return "StructuredLoopToSelectionReductionPass";
92 }
93
94 } // namespace reduce
95 } // namespace spvtools
96