1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
// Copyright (c) 2021 Alastair F. Donaldson
//
// 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_construct_to_block_reduction_opportunity_finder.h"
#include <unordered_set>
#include "source/reduce/structured_construct_to_block_reduction_opportunity.h"
namespace spvtools {
namespace reduce {
std::vector<std::unique_ptr<ReductionOpportunity>>
StructuredConstructToBlockReductionOpportunityFinder::GetAvailableOpportunities(
opt::IRContext* context, uint32_t target_function) const {
std::vector<std::unique_ptr<ReductionOpportunity>> result;
// Consider every function in the module.
for (auto* function : GetTargetFunctions(context, target_function)) {
// For every header block in the function, there is potentially a region of
// blocks that could be collapsed.
std::unordered_map<opt::BasicBlock*, std::unordered_set<opt::BasicBlock*>>
regions;
// Regions are identified using dominators and postdominators, so we compute
// those for the function.
auto* dominators = context->GetDominatorAnalysis(function);
auto* postdominators = context->GetPostDominatorAnalysis(function);
// Consider every block in the function.
for (auto& block : *function) {
// If a block has an unreachable predecessor then folding away a region in
// which that block is contained gets complicated, so we ignore regions
// that contain such blocks. We note whether this block suffers from this
// problem.
bool has_unreachable_predecessor =
HasUnreachablePredecessor(block, context);
// Look through all the regions we have identified so far to see whether
// this block is part of a region, or spoils a region (by having an
// unreachable predecessor).
for (auto entry = regions.begin(); entry != regions.end();) {
// |block| is in this region if it is dominated by the header,
// post-dominated by the merge, and different from the merge.
assert(&block != entry->first &&
"The block should not be the region's header because we only "
"make a region when we encounter its header.");
if (entry->first->MergeBlockId() != block.id() &&
dominators->Dominates(entry->first, &block) &&
postdominators->Dominates(
entry->first->GetMergeInst()->GetSingleWordInOperand(0),
block.id())) {
if (has_unreachable_predecessor) {
// The block would be in this region, but it has an unreachable
// predecessor. This spoils the region, so we remove it.
entry = regions.erase(entry);
continue;
} else {
// Add the block to the region.
entry->second.insert(&block);
}
}
++entry;
}
if (block.MergeBlockIdIfAny() == 0) {
// The block isn't a header, so it doesn't constitute a new region.
continue;
}
if (!context->IsReachable(block)) {
// The block isn't reachable, so it doesn't constitute a new region.
continue;
}
auto* merge_block = context->cfg()->block(
block.GetMergeInst()->GetSingleWordInOperand(0));
if (!context->IsReachable(*merge_block)) {
// The block's merge is unreachable, so it doesn't constitute a new
// region.
continue;
}
assert(dominators->Dominates(&block, merge_block) &&
"The merge block is reachable, so the header must dominate it");
if (!postdominators->Dominates(merge_block, &block)) {
// The block is not post-dominated by its merge. This happens for
// instance when there is a break from a conditional, or an early exit.
// This also means that we don't add a region.
continue;
}
// We have a reachable header block with a reachable merge that
// postdominates the header: this means we have a new region.
regions.emplace(&block, std::unordered_set<opt::BasicBlock*>());
}
// Now that we have found all the regions and blocks within them, we check
// whether any region defines an id that is used outside the region. If this
// is *not* the case, then we have an opportunity to collapse the region
// down to its header block and merge block.
for (auto& entry : regions) {
if (DefinitionsRestrictedToRegion(*entry.first, entry.second, context)) {
result.emplace_back(
MakeUnique<StructuredConstructToBlockReductionOpportunity>(
context, entry.first->id()));
}
}
}
return result;
}
bool StructuredConstructToBlockReductionOpportunityFinder::
DefinitionsRestrictedToRegion(
const opt::BasicBlock& header,
const std::unordered_set<opt::BasicBlock*>& region,
opt::IRContext* context) {
// Consider every block in the region.
for (auto& block : region) {
// Consider every instruction in the block - this includes the label
// instruction
if (!block->WhileEachInst(
[context, &header, ®ion](opt::Instruction* inst) -> bool {
if (inst->result_id() == 0) {
// The instruction does not generate a result id, thus it cannot
// be referred to outside the region - this is fine.
return true;
}
// Consider every use of the instruction's result id.
if (!context->get_def_use_mgr()->WhileEachUse(
inst->result_id(),
[context, &header, ®ion](opt::Instruction* user,
uint32_t) -> bool {
auto user_block = context->get_instr_block(user);
if (user == header.GetMergeInst() ||
user == header.terminator()) {
// We are going to delete the header's merge
// instruction and rewrite its terminator, so it does
// not matter if the user is one of these
// instructions.
return true;
}
if (user_block == nullptr ||
region.count(user_block) == 0) {
// The user is either a global instruction, or an
// instruction in a block outside the region. Removing
// the region would invalidate this user.
return false;
}
return true;
})) {
return false;
}
return true;
})) {
return false;
}
}
return true;
}
bool StructuredConstructToBlockReductionOpportunityFinder::
HasUnreachablePredecessor(const opt::BasicBlock& block,
opt::IRContext* context) {
for (auto pred : context->cfg()->preds(block.id())) {
if (!context->IsReachable(*context->cfg()->block(pred))) {
return true;
}
}
return false;
}
std::string StructuredConstructToBlockReductionOpportunityFinder::GetName()
const {
return "StructuredConstructToBlockReductionOpportunityFinder";
}
} // namespace reduce
} // namespace spvtools
|
