1 /*
2 * Copyright 2016-2018 ARM Limited
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "spirv_cfg.hpp"
18 #include "spirv_cross.hpp"
19 #include <algorithm>
20 #include <assert.h>
21
22 using namespace std;
23
24 namespace spirv_cross
25 {
CFG(Compiler & compiler_,const SPIRFunction & func_)26 CFG::CFG(Compiler &compiler_, const SPIRFunction &func_)
27 : compiler(compiler_)
28 , func(func_)
29 {
30 preceding_edges.resize(compiler.get_current_id_bound());
31 succeeding_edges.resize(compiler.get_current_id_bound());
32 visit_order.resize(compiler.get_current_id_bound());
33 immediate_dominators.resize(compiler.get_current_id_bound());
34
35 build_post_order_visit_order();
36 build_immediate_dominators();
37 }
38
find_common_dominator(uint32_t a,uint32_t b) const39 uint32_t CFG::find_common_dominator(uint32_t a, uint32_t b) const
40 {
41 while (a != b)
42 {
43 if (visit_order[a] < visit_order[b])
44 a = immediate_dominators[a];
45 else
46 b = immediate_dominators[b];
47 }
48 return a;
49 }
50
build_immediate_dominators()51 void CFG::build_immediate_dominators()
52 {
53 // Traverse the post-order in reverse and build up the immediate dominator tree.
54 fill(begin(immediate_dominators), end(immediate_dominators), 0);
55 immediate_dominators[func.entry_block] = func.entry_block;
56
57 for (auto i = post_order.size(); i; i--)
58 {
59 uint32_t block = post_order[i - 1];
60 auto &pred = preceding_edges[block];
61 if (pred.empty()) // This is for the entry block, but we've already set up the dominators.
62 continue;
63
64 for (auto &edge : pred)
65 {
66 if (immediate_dominators[block])
67 {
68 assert(immediate_dominators[edge]);
69 immediate_dominators[block] = find_common_dominator(block, edge);
70 }
71 else
72 immediate_dominators[block] = edge;
73 }
74 }
75 }
76
is_back_edge(uint32_t to) const77 bool CFG::is_back_edge(uint32_t to) const
78 {
79 // We have a back edge if the visit order is set with the temporary magic value 0.
80 // Crossing edges will have already been recorded with a visit order.
81 return visit_order[to] == 0;
82 }
83
post_order_visit(uint32_t block_id)84 bool CFG::post_order_visit(uint32_t block_id)
85 {
86 // If we have already branched to this block (back edge), stop recursion.
87 // If our branches are back-edges, we do not record them.
88 // We have to record crossing edges however.
89 if (visit_order[block_id] >= 0)
90 return !is_back_edge(block_id);
91
92 // Block back-edges from recursively revisiting ourselves.
93 visit_order[block_id] = 0;
94
95 // First visit our branch targets.
96 auto &block = compiler.get<SPIRBlock>(block_id);
97 switch (block.terminator)
98 {
99 case SPIRBlock::Direct:
100 if (post_order_visit(block.next_block))
101 add_branch(block_id, block.next_block);
102 break;
103
104 case SPIRBlock::Select:
105 if (post_order_visit(block.true_block))
106 add_branch(block_id, block.true_block);
107 if (post_order_visit(block.false_block))
108 add_branch(block_id, block.false_block);
109 break;
110
111 case SPIRBlock::MultiSelect:
112 for (auto &target : block.cases)
113 {
114 if (post_order_visit(target.block))
115 add_branch(block_id, target.block);
116 }
117 if (block.default_block && post_order_visit(block.default_block))
118 add_branch(block_id, block.default_block);
119 break;
120
121 default:
122 break;
123 }
124
125 // If this is a loop header, add an implied branch to the merge target.
126 // This is needed to avoid annoying cases with do { ... } while(false) loops often generated by inliners.
127 // To the CFG, this is linear control flow, but we risk picking the do/while scope as our dominating block.
128 // This makes sure that if we are accessing a variable outside the do/while, we choose the loop header as dominator.
129 if (block.merge == SPIRBlock::MergeLoop)
130 add_branch(block_id, block.merge_block);
131
132 // Then visit ourselves. Start counting at one, to let 0 be a magic value for testing back vs. crossing edges.
133 visit_order[block_id] = ++visit_count;
134 post_order.push_back(block_id);
135 return true;
136 }
137
build_post_order_visit_order()138 void CFG::build_post_order_visit_order()
139 {
140 uint32_t block = func.entry_block;
141 visit_count = 0;
142 fill(begin(visit_order), end(visit_order), -1);
143 post_order.clear();
144 post_order_visit(block);
145 }
146
add_branch(uint32_t from,uint32_t to)147 void CFG::add_branch(uint32_t from, uint32_t to)
148 {
149 const auto add_unique = [](vector<uint32_t> &l, uint32_t value) {
150 auto itr = find(begin(l), end(l), value);
151 if (itr == end(l))
152 l.push_back(value);
153 };
154 add_unique(preceding_edges[to], from);
155 add_unique(succeeding_edges[from], to);
156 }
157
DominatorBuilder(const CFG & cfg_)158 DominatorBuilder::DominatorBuilder(const CFG &cfg_)
159 : cfg(cfg_)
160 {
161 }
162
add_block(uint32_t block)163 void DominatorBuilder::add_block(uint32_t block)
164 {
165 if (!cfg.get_immediate_dominator(block))
166 {
167 // Unreachable block via the CFG, we will never emit this code anyways.
168 return;
169 }
170
171 if (!dominator)
172 {
173 dominator = block;
174 return;
175 }
176
177 if (block != dominator)
178 dominator = cfg.find_common_dominator(block, dominator);
179 }
180
lift_continue_block_dominator()181 void DominatorBuilder::lift_continue_block_dominator()
182 {
183 // It is possible for a continue block to be the dominator of a variable is only accessed inside the while block of a do-while loop.
184 // We cannot safely declare variables inside a continue block, so move any variable declared
185 // in a continue block to the entry block to simplify.
186 // It makes very little sense for a continue block to ever be a dominator, so fall back to the simplest
187 // solution.
188
189 if (!dominator)
190 return;
191
192 auto &block = cfg.get_compiler().get<SPIRBlock>(dominator);
193 auto post_order = cfg.get_visit_order(dominator);
194
195 // If we are branching to a block with a higher post-order traversal index (continue blocks), we have a problem
196 // since we cannot create sensible GLSL code for this, fallback to entry block.
197 bool back_edge_dominator = false;
198 switch (block.terminator)
199 {
200 case SPIRBlock::Direct:
201 if (cfg.get_visit_order(block.next_block) > post_order)
202 back_edge_dominator = true;
203 break;
204
205 case SPIRBlock::Select:
206 if (cfg.get_visit_order(block.true_block) > post_order)
207 back_edge_dominator = true;
208 if (cfg.get_visit_order(block.false_block) > post_order)
209 back_edge_dominator = true;
210 break;
211
212 case SPIRBlock::MultiSelect:
213 for (auto &target : block.cases)
214 {
215 if (cfg.get_visit_order(target.block) > post_order)
216 back_edge_dominator = true;
217 }
218 if (block.default_block && cfg.get_visit_order(block.default_block) > post_order)
219 back_edge_dominator = true;
220 break;
221
222 default:
223 break;
224 }
225
226 if (back_edge_dominator)
227 dominator = cfg.get_function().entry_block;
228 }
229 } // namespace spirv_cross
230