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
|
// Copyright (c) 2018 Google LLC.
//
// 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.
#ifndef SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_
#define SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_
#include <unordered_map>
#include <unordered_set>
#include "source/opt/function.h"
#include "source/util/bit_vector.h"
namespace spvtools {
namespace opt {
class IRContext;
// An analysis that, for each basic block, finds the constructs in which it is
// contained, so we can easily get headers and merge nodes.
class StructuredCFGAnalysis {
public:
explicit StructuredCFGAnalysis(IRContext* ctx);
// Returns the id of the header of the innermost merge construct
// that contains |bb_id|. Returns |0| if |bb_id| is not contained in any
// merge construct.
uint32_t ContainingConstruct(uint32_t bb_id) {
auto it = bb_to_construct_.find(bb_id);
if (it == bb_to_construct_.end()) {
return 0;
}
return it->second.containing_construct;
}
// Returns the id of the header of the innermost merge construct
// that contains |inst|. Returns |0| if |inst| is not contained in any
// merge construct.
uint32_t ContainingConstruct(Instruction* inst);
// Returns the id of the merge block of the innermost merge construct
// that contains |bb_id|. Returns |0| if |bb_id| is not contained in any
// merge construct.
uint32_t MergeBlock(uint32_t bb_id);
// Returns the nesting depth of the given block, i.e. the number of merge
// constructs containing it. Headers and merge blocks are not considered part
// of the corresponding merge constructs.
uint32_t NestingDepth(uint32_t block_id);
// Returns the id of the header of the innermost loop construct
// that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop
// construct.
uint32_t ContainingLoop(uint32_t bb_id) {
auto it = bb_to_construct_.find(bb_id);
if (it == bb_to_construct_.end()) {
return 0;
}
return it->second.containing_loop;
}
// Returns the id of the merge block of the innermost loop construct
// that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop
// construct.
uint32_t LoopMergeBlock(uint32_t bb_id);
// Returns the id of the continue block of the innermost loop construct
// that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop
// construct.
uint32_t LoopContinueBlock(uint32_t bb_id);
// Returns the loop nesting depth of |bb_id| within its function, i.e. the
// number of loop constructs in which |bb_id| is contained. As per other
// functions in StructuredCFGAnalysis, a loop header is not regarded as being
// part of the loop that it heads, so that e.g. the nesting depth of an
// outer-most loop header is 0.
uint32_t LoopNestingDepth(uint32_t bb_id);
// Returns the id of the header of the innermost switch construct
// that contains |bb_id| as long as there is no intervening loop. Returns |0|
// if no such construct exists.
uint32_t ContainingSwitch(uint32_t bb_id) {
auto it = bb_to_construct_.find(bb_id);
if (it == bb_to_construct_.end()) {
return 0;
}
return it->second.containing_switch;
}
// Returns the id of the merge block of the innermost switch construct
// that contains |bb_id| as long as there is no intervening loop. Return |0|
// if no such block exists.
uint32_t SwitchMergeBlock(uint32_t bb_id);
// Returns true if |bb_id| is the continue block for a loop.
bool IsContinueBlock(uint32_t bb_id);
// Returns true if |bb_id| is in the continue construct for its inner most
// containing loop.
bool IsInContainingLoopsContinueConstruct(uint32_t bb_id);
// Returns true if |bb_id| is in the continue construct for any loop in its
// function.
bool IsInContinueConstruct(uint32_t bb_id);
// Return true if |bb_id| is the merge block for a construct.
bool IsMergeBlock(uint32_t bb_id);
// Returns the set of function ids that are called directly or indirectly from
// a continue construct.
std::unordered_set<uint32_t> FindFuncsCalledFromContinue();
private:
// Struct used to hold the information for a basic block.
// |containing_construct| is the header for the innermost containing
// construct, or 0 if no such construct exists. It could be a selection
// construct or a loop construct.
//
// |containing_loop| is the innermost containing loop construct, or 0 if the
// basic bloc is not in a loop. If the basic block is in a selection
// construct that is contained in a loop construct, then these two values will
// not be the same.
//
// |containing_switch| is the innermost contain selection construct with an
// |OpSwitch| for the branch, as long as there is not intervening loop. This
// is used to identify the selection construct from which it can break.
//
// |in_continue| is true of the block is in the continue construct for its
// innermost containing loop.
struct ConstructInfo {
uint32_t containing_construct;
uint32_t containing_loop;
uint32_t containing_switch;
bool in_continue;
};
// Populates |bb_to_construct_| with the innermost containing merge and loop
// constructs for each basic block in |func|.
void AddBlocksInFunction(Function* func);
IRContext* context_;
// A map from a basic block to the headers of its inner most containing
// constructs.
std::unordered_map<uint32_t, ConstructInfo> bb_to_construct_;
utils::BitVector merge_blocks_;
};
} // namespace opt
} // namespace spvtools
#endif // SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_
|
