1/*
2 * Copyright 2016-2021 Arm Limited
3 * SPDX-License-Identifier: Apache-2.0 OR MIT
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18/*
19 * At your option, you may choose to accept this material under either:
20 * 1. The Apache License, Version 2.0, found at <http://www.apache.org/licenses/LICENSE-2.0>, or
21 * 2. The MIT License, found at <http://opensource.org/licenses/MIT>.
22 */
23
24#ifndef SPIRV_CROSS_CFG_HPP
25#define SPIRV_CROSS_CFG_HPP
26
27#include "spirv_common.hpp"
28#include <assert.h>
29
30namespace SPIRV_CROSS_NAMESPACE
31{
32class Compiler;
33class CFG
34{
35public:
36 CFG(Compiler &compiler, const SPIRFunction &function);
37
38 Compiler &get_compiler()
39 {
40 return compiler;
41 }
42
43 const Compiler &get_compiler() const
44 {
45 return compiler;
46 }
47
48 const SPIRFunction &get_function() const
49 {
50 return func;
51 }
52
53 uint32_t get_immediate_dominator(uint32_t block) const
54 {
55 auto itr = immediate_dominators.find(x: block);
56 if (itr != std::end(cont: immediate_dominators))
57 return itr->second;
58 else
59 return 0;
60 }
61
62 bool is_reachable(uint32_t block) const
63 {
64 return visit_order.count(x: block) != 0;
65 }
66
67 uint32_t get_visit_order(uint32_t block) const
68 {
69 auto itr = visit_order.find(x: block);
70 assert(itr != std::end(visit_order));
71 int v = itr->second.get();
72 assert(v > 0);
73 return uint32_t(v);
74 }
75
76 uint32_t find_common_dominator(uint32_t a, uint32_t b) const;
77
78 const SmallVector<uint32_t> &get_preceding_edges(uint32_t block) const
79 {
80 auto itr = preceding_edges.find(x: block);
81 if (itr != std::end(cont: preceding_edges))
82 return itr->second;
83 else
84 return empty_vector;
85 }
86
87 const SmallVector<uint32_t> &get_succeeding_edges(uint32_t block) const
88 {
89 auto itr = succeeding_edges.find(x: block);
90 if (itr != std::end(cont: succeeding_edges))
91 return itr->second;
92 else
93 return empty_vector;
94 }
95
96 template <typename Op>
97 void walk_from(std::unordered_set<uint32_t> &seen_blocks, uint32_t block, const Op &op) const
98 {
99 if (seen_blocks.count(x: block))
100 return;
101 seen_blocks.insert(x: block);
102
103 if (op(block))
104 {
105 for (auto b : get_succeeding_edges(block))
106 walk_from(seen_blocks, b, op);
107 }
108 }
109
110 uint32_t find_loop_dominator(uint32_t block) const;
111
112 bool node_terminates_control_flow_in_sub_graph(BlockID from, BlockID to) const;
113
114private:
115 struct VisitOrder
116 {
117 int &get()
118 {
119 return v;
120 }
121
122 const int &get() const
123 {
124 return v;
125 }
126
127 int v = -1;
128 };
129
130 Compiler &compiler;
131 const SPIRFunction &func;
132 std::unordered_map<uint32_t, SmallVector<uint32_t>> preceding_edges;
133 std::unordered_map<uint32_t, SmallVector<uint32_t>> succeeding_edges;
134 std::unordered_map<uint32_t, uint32_t> immediate_dominators;
135 std::unordered_map<uint32_t, VisitOrder> visit_order;
136 SmallVector<uint32_t> post_order;
137 SmallVector<uint32_t> empty_vector;
138
139 void add_branch(uint32_t from, uint32_t to);
140 void build_post_order_visit_order();
141 void build_immediate_dominators();
142 bool post_order_visit(uint32_t block);
143 uint32_t visit_count = 0;
144
145 bool is_back_edge(uint32_t to) const;
146 bool has_visited_forward_edge(uint32_t to) const;
147};
148
149class DominatorBuilder
150{
151public:
152 DominatorBuilder(const CFG &cfg);
153
154 void add_block(uint32_t block);
155 uint32_t get_dominator() const
156 {
157 return dominator;
158 }
159
160 void lift_continue_block_dominator();
161
162private:
163 const CFG &cfg;
164 uint32_t dominator = 0;
165};
166} // namespace SPIRV_CROSS_NAMESPACE
167
168#endif
169

source code of qtshadertools/src/3rdparty/SPIRV-Cross/spirv_cfg.hpp