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#ifndef SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_
16#define SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_
17
18#include <unordered_map>
19#include <unordered_set>
20
21#include "source/opt/function.h"
22#include "source/util/bit_vector.h"
23
24namespace spvtools {
25namespace opt {
26
27class IRContext;
28
29// An analysis that, for each basic block, finds the constructs in which it is
30// contained, so we can easily get headers and merge nodes.
31class StructuredCFGAnalysis {
32 public:
33 explicit StructuredCFGAnalysis(IRContext* ctx);
34
35 // Returns the id of the header of the innermost merge construct
36 // that contains |bb_id|. Returns |0| if |bb_id| is not contained in any
37 // merge construct.
38 uint32_t ContainingConstruct(uint32_t bb_id) {
39 auto it = bb_to_construct_.find(bb_id);
40 if (it == bb_to_construct_.end()) {
41 return 0;
42 }
43 return it->second.containing_construct;
44 }
45
46 // Returns the id of the header of the innermost merge construct
47 // that contains |inst|. Returns |0| if |inst| is not contained in any
48 // merge construct.
49 uint32_t ContainingConstruct(Instruction* inst);
50
51 // Returns the id of the merge block of the innermost merge construct
52 // that contains |bb_id|. Returns |0| if |bb_id| is not contained in any
53 // merge construct.
54 uint32_t MergeBlock(uint32_t bb_id);
55
56 // Returns the id of the header of the innermost loop construct
57 // that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop
58 // construct.
59 uint32_t ContainingLoop(uint32_t bb_id) {
60 auto it = bb_to_construct_.find(bb_id);
61 if (it == bb_to_construct_.end()) {
62 return 0;
63 }
64 return it->second.containing_loop;
65 }
66
67 // Returns the id of the merge block of the innermost loop construct
68 // that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop
69 // construct.
70 uint32_t LoopMergeBlock(uint32_t bb_id);
71
72 // Returns the id of the continue block of the innermost loop construct
73 // that contains |bb_id|. Return |0| if |bb_id| is not contained in any loop
74 // construct.
75 uint32_t LoopContinueBlock(uint32_t bb_id);
76
77 // Returns the id of the header of the innermost switch construct
78 // that contains |bb_id| as long as there is no intervening loop. Returns |0|
79 // if no such construct exists.
80 uint32_t ContainingSwitch(uint32_t bb_id) {
81 auto it = bb_to_construct_.find(bb_id);
82 if (it == bb_to_construct_.end()) {
83 return 0;
84 }
85 return it->second.containing_switch;
86 }
87 // Returns the id of the merge block of the innermost switch construct
88 // that contains |bb_id| as long as there is no intervening loop. Return |0|
89 // if no such block exists.
90 uint32_t SwitchMergeBlock(uint32_t bb_id);
91
92 // Returns true if |bb_id| is the continue block for a loop.
93 bool IsContinueBlock(uint32_t bb_id);
94
95 // Returns true if |bb_id| is in the continue construct for its inner most
96 // containing loop.
97 bool IsInContainingLoopsContinueConstruct(uint32_t bb_id);
98
99 // Returns true if |bb_id| is in the continue construct for any loop in its
100 // function.
101 bool IsInContinueConstruct(uint32_t bb_id);
102
103 // Return true if |bb_id| is the merge block for a construct.
104 bool IsMergeBlock(uint32_t bb_id);
105
106 // Returns the set of function ids that are called directly or indirectly from
107 // a continue construct.
108 std::unordered_set<uint32_t> FindFuncsCalledFromContinue();
109
110 private:
111 // Struct used to hold the information for a basic block.
112 // |containing_construct| is the header for the innermost containing
113 // construct, or 0 if no such construct exists. It could be a selection
114 // construct or a loop construct.
115 //
116 // |containing_loop| is the innermost containing loop construct, or 0 if the
117 // basic bloc is not in a loop. If the basic block is in a selection
118 // construct that is contained in a loop construct, then these two values will
119 // not be the same.
120 //
121 // |containing_switch| is the innermost contain selection construct with an
122 // |OpSwitch| for the branch, as long as there is not intervening loop. This
123 // is used to identify the selection construct from which it can break.
124 //
125 // |in_continue| is true of the block is in the continue construct for its
126 // innermost containing loop.
127 struct ConstructInfo {
128 uint32_t containing_construct;
129 uint32_t containing_loop;
130 uint32_t containing_switch;
131 bool in_continue;
132 };
133
134 // Populates |bb_to_construct_| with the innermost containing merge and loop
135 // constructs for each basic block in |func|.
136 void AddBlocksInFunction(Function* func);
137
138 IRContext* context_;
139
140 // A map from a basic block to the headers of its inner most containing
141 // constructs.
142 std::unordered_map<uint32_t, ConstructInfo> bb_to_construct_;
143 utils::BitVector merge_blocks_;
144};
145
146} // namespace opt
147} // namespace spvtools
148#endif // SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_
149