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 uint32_t get_visit_order(uint32_t block) const
63 {
64 auto itr = visit_order.find(x: block);
65 assert(itr != std::end(visit_order));
66 int v = itr->second.get();
67 assert(v > 0);
68 return uint32_t(v);
69 }
70
71 uint32_t find_common_dominator(uint32_t a, uint32_t b) const;
72
73 const SmallVector<uint32_t> &get_preceding_edges(uint32_t block) const
74 {
75 auto itr = preceding_edges.find(x: block);
76 if (itr != std::end(cont: preceding_edges))
77 return itr->second;
78 else
79 return empty_vector;
80 }
81
82 const SmallVector<uint32_t> &get_succeeding_edges(uint32_t block) const
83 {
84 auto itr = succeeding_edges.find(x: block);
85 if (itr != std::end(cont: succeeding_edges))
86 return itr->second;
87 else
88 return empty_vector;
89 }
90
91 template <typename Op>
92 void walk_from(std::unordered_set<uint32_t> &seen_blocks, uint32_t block, const Op &op) const
93 {
94 if (seen_blocks.count(x: block))
95 return;
96 seen_blocks.insert(x: block);
97
98 if (op(block))
99 {
100 for (auto b : get_succeeding_edges(block))
101 walk_from(seen_blocks, b, op);
102 }
103 }
104
105 uint32_t find_loop_dominator(uint32_t block) const;
106
107 bool node_terminates_control_flow_in_sub_graph(BlockID from, BlockID to) const;
108
109private:
110 struct VisitOrder
111 {
112 int &get()
113 {
114 return v;
115 }
116
117 const int &get() const
118 {
119 return v;
120 }
121
122 int v = -1;
123 };
124
125 Compiler &compiler;
126 const SPIRFunction &func;
127 std::unordered_map<uint32_t, SmallVector<uint32_t>> preceding_edges;
128 std::unordered_map<uint32_t, SmallVector<uint32_t>> succeeding_edges;
129 std::unordered_map<uint32_t, uint32_t> immediate_dominators;
130 std::unordered_map<uint32_t, VisitOrder> visit_order;
131 SmallVector<uint32_t> post_order;
132 SmallVector<uint32_t> empty_vector;
133
134 void add_branch(uint32_t from, uint32_t to);
135 void build_post_order_visit_order();
136 void build_immediate_dominators();
137 bool post_order_visit(uint32_t block);
138 uint32_t visit_count = 0;
139
140 bool is_back_edge(uint32_t to) const;
141 bool has_visited_forward_edge(uint32_t to) const;
142};
143
144class DominatorBuilder
145{
146public:
147 DominatorBuilder(const CFG &cfg);
148
149 void add_block(uint32_t block);
150 uint32_t get_dominator() const
151 {
152 return dominator;
153 }
154
155 void lift_continue_block_dominator();
156
157private:
158 const CFG &cfg;
159 uint32_t dominator = 0;
160};
161} // namespace SPIRV_CROSS_NAMESPACE
162
163#endif
164

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