1 // Copyright (c) 2019 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 #include "source/reduce/simple_conditional_branch_to_branch_opportunity_finder.h"
16
17 #include "source/opt/build_module.h"
18 #include "source/reduce/reduction_opportunity.h"
19 #include "source/reduce/reduction_pass.h"
20 #include "test/reduce/reduce_test_util.h"
21
22 namespace spvtools {
23 namespace reduce {
24 namespace {
25
26 const spv_target_env kEnv = SPV_ENV_UNIVERSAL_1_3;
27
TEST(SimpleConditionalBranchToBranchTest,Diamond)28 TEST(SimpleConditionalBranchToBranchTest, Diamond) {
29 // A test with the following structure.
30 //
31 // selection header
32 // OpBranchConditional
33 // ||
34 // b b
35 // | |
36 // selection merge
37 //
38 // The conditional branch cannot be simplified because selection headers
39 // cannot end with OpBranch.
40
41 std::string shader = R"(
42 OpCapability Shader
43 %1 = OpExtInstImport "GLSL.std.450"
44 OpMemoryModel Logical GLSL450
45 OpEntryPoint Fragment %2 "main"
46 OpExecutionMode %2 OriginUpperLeft
47 OpSource ESSL 310
48 OpName %2 "main"
49 %3 = OpTypeVoid
50 %4 = OpTypeFunction %3
51 %5 = OpTypeInt 32 1
52 %6 = OpTypePointer Function %5
53 %7 = OpTypeBool
54 %8 = OpConstantTrue %7
55 %2 = OpFunction %3 None %4
56 %9 = OpLabel
57 OpBranch %10
58 %10 = OpLabel
59 OpSelectionMerge %11 None
60 OpBranchConditional %8 %12 %12
61 %12 = OpLabel
62 OpBranch %11
63 %13 = OpLabel
64 OpBranch %11
65 %11 = OpLabel
66 OpReturn
67 OpFunctionEnd
68
69 )";
70
71 auto context = BuildModule(kEnv, nullptr, shader, kReduceAssembleOption);
72
73 CheckValid(kEnv, context.get());
74
75 auto ops = SimpleConditionalBranchToBranchOpportunityFinder()
76 .GetAvailableOpportunities(context.get(), 0);
77
78 ASSERT_EQ(0, ops.size());
79 }
80
TEST(SimpleConditionalBranchToBranchTest,DiamondNoSelection)81 TEST(SimpleConditionalBranchToBranchTest, DiamondNoSelection) {
82 // A test with the following structure.
83 //
84 // OpBranchConditional
85 // ||
86 // b b
87 // | /
88 // b
89 //
90 // The conditional branch can be simplified.
91
92 std::string shader = R"(
93 OpCapability Shader
94 %1 = OpExtInstImport "GLSL.std.450"
95 OpMemoryModel Logical GLSL450
96 OpEntryPoint Fragment %2 "main"
97 OpExecutionMode %2 OriginUpperLeft
98 OpSource ESSL 310
99 OpName %2 "main"
100 %3 = OpTypeVoid
101 %4 = OpTypeFunction %3
102 %5 = OpTypeInt 32 1
103 %6 = OpTypePointer Function %5
104 %7 = OpTypeBool
105 %8 = OpConstantTrue %7
106 %2 = OpFunction %3 None %4
107 %9 = OpLabel
108 OpBranch %10
109 %10 = OpLabel
110 OpBranchConditional %8 %12 %12
111 %12 = OpLabel
112 OpBranch %11
113 %13 = OpLabel
114 OpBranch %11
115 %11 = OpLabel
116 OpReturn
117 OpFunctionEnd
118 )";
119
120 auto context = BuildModule(kEnv, nullptr, shader, kReduceAssembleOption);
121
122 CheckValid(kEnv, context.get());
123
124 auto ops = SimpleConditionalBranchToBranchOpportunityFinder()
125 .GetAvailableOpportunities(context.get(), 0);
126
127 ASSERT_EQ(1, ops.size());
128
129 ASSERT_TRUE(ops[0]->PreconditionHolds());
130 ops[0]->TryToApply();
131 CheckValid(kEnv, context.get());
132
133 std::string after = R"(
134 OpCapability Shader
135 %1 = OpExtInstImport "GLSL.std.450"
136 OpMemoryModel Logical GLSL450
137 OpEntryPoint Fragment %2 "main"
138 OpExecutionMode %2 OriginUpperLeft
139 OpSource ESSL 310
140 OpName %2 "main"
141 %3 = OpTypeVoid
142 %4 = OpTypeFunction %3
143 %5 = OpTypeInt 32 1
144 %6 = OpTypePointer Function %5
145 %7 = OpTypeBool
146 %8 = OpConstantTrue %7
147 %2 = OpFunction %3 None %4
148 %9 = OpLabel
149 OpBranch %10
150 %10 = OpLabel
151 OpBranch %12
152 %12 = OpLabel
153 OpBranch %11
154 %13 = OpLabel
155 OpBranch %11
156 %11 = OpLabel
157 OpReturn
158 OpFunctionEnd
159 )";
160
161 CheckEqual(kEnv, after, context.get());
162
163 ops = SimpleConditionalBranchToBranchOpportunityFinder()
164 .GetAvailableOpportunities(context.get(), 0);
165 ASSERT_EQ(0, ops.size());
166 }
167
TEST(SimpleConditionalBranchToBranchTest,ConditionalBranchesButNotSimple)168 TEST(SimpleConditionalBranchToBranchTest, ConditionalBranchesButNotSimple) {
169 // A test with the following structure.
170 //
171 // selection header
172 // OpBranchConditional
173 // | |
174 // b OpBranchConditional
175 // | | |
176 // | b |
177 // | | |
178 // selection merge
179 //
180 // None of the conditional branches can be simplified; the first is not simple
181 // AND part of a selection header; the second is just not simple (where
182 // "simple" means it only has one target).
183
184 std::string shader = R"(
185 OpCapability Shader
186 %1 = OpExtInstImport "GLSL.std.450"
187 OpMemoryModel Logical GLSL450
188 OpEntryPoint Fragment %2 "main"
189 OpExecutionMode %2 OriginUpperLeft
190 OpSource ESSL 310
191 OpName %2 "main"
192 %3 = OpTypeVoid
193 %4 = OpTypeFunction %3
194 %5 = OpTypeInt 32 1
195 %6 = OpTypePointer Function %5
196 %7 = OpTypeBool
197 %8 = OpConstantTrue %7
198 %2 = OpFunction %3 None %4
199 %9 = OpLabel
200 OpBranch %10
201 %10 = OpLabel
202 OpSelectionMerge %11 None
203 OpBranchConditional %8 %12 %13
204 %12 = OpLabel
205 OpBranch %11
206 %13 = OpLabel
207 OpBranchConditional %8 %14 %11
208 %14 = OpLabel
209 OpBranch %11
210 %11 = OpLabel
211 OpReturn
212 OpFunctionEnd
213 )";
214
215 auto context = BuildModule(kEnv, nullptr, shader, kReduceAssembleOption);
216
217 CheckValid(kEnv, context.get());
218
219 auto ops = SimpleConditionalBranchToBranchOpportunityFinder()
220 .GetAvailableOpportunities(context.get(), 0);
221
222 ASSERT_EQ(0, ops.size());
223 }
224
TEST(SimpleConditionalBranchToBranchTest,SimplifyBackEdge)225 TEST(SimpleConditionalBranchToBranchTest, SimplifyBackEdge) {
226 // A test with the following structure. The loop has a continue construct that
227 // ends with OpBranchConditional. The OpBranchConditional can be simplified.
228 //
229 // loop header
230 // |
231 // loop continue target and back-edge block
232 // OpBranchConditional
233 // ||
234 // loop merge (to loop header^)
235
236 std::string shader = R"(
237 OpCapability Shader
238 %1 = OpExtInstImport "GLSL.std.450"
239 OpMemoryModel Logical GLSL450
240 OpEntryPoint Fragment %2 "main"
241 OpExecutionMode %2 OriginUpperLeft
242 OpSource ESSL 310
243 OpName %2 "main"
244 %3 = OpTypeVoid
245 %4 = OpTypeFunction %3
246 %5 = OpTypeInt 32 1
247 %6 = OpTypePointer Function %5
248 %7 = OpTypeBool
249 %8 = OpConstantTrue %7
250 %2 = OpFunction %3 None %4
251 %9 = OpLabel
252 OpBranch %10
253 %10 = OpLabel
254 OpLoopMerge %11 %12 None
255 OpBranch %12
256 %12 = OpLabel
257 OpBranchConditional %8 %10 %10
258 %11 = OpLabel
259 OpReturn
260 OpFunctionEnd
261 )";
262
263 const auto context =
264 BuildModule(kEnv, nullptr, shader, kReduceAssembleOption);
265
266 CheckValid(kEnv, context.get());
267
268 auto ops = SimpleConditionalBranchToBranchOpportunityFinder()
269 .GetAvailableOpportunities(context.get(), 0);
270
271 ASSERT_EQ(1, ops.size());
272
273 ASSERT_TRUE(ops[0]->PreconditionHolds());
274 ops[0]->TryToApply();
275 CheckValid(kEnv, context.get());
276
277 std::string after = R"(
278 OpCapability Shader
279 %1 = OpExtInstImport "GLSL.std.450"
280 OpMemoryModel Logical GLSL450
281 OpEntryPoint Fragment %2 "main"
282 OpExecutionMode %2 OriginUpperLeft
283 OpSource ESSL 310
284 OpName %2 "main"
285 %3 = OpTypeVoid
286 %4 = OpTypeFunction %3
287 %5 = OpTypeInt 32 1
288 %6 = OpTypePointer Function %5
289 %7 = OpTypeBool
290 %8 = OpConstantTrue %7
291 %2 = OpFunction %3 None %4
292 %9 = OpLabel
293 OpBranch %10
294 %10 = OpLabel
295 OpLoopMerge %11 %12 None
296 OpBranch %12
297 %12 = OpLabel
298 OpBranch %10
299 %11 = OpLabel
300 OpReturn
301 OpFunctionEnd
302 )";
303 CheckEqual(kEnv, after, context.get());
304
305 ops = SimpleConditionalBranchToBranchOpportunityFinder()
306 .GetAvailableOpportunities(context.get(), 0);
307 ASSERT_EQ(0, ops.size());
308 }
309
TEST(SimpleConditionalBranchToBranchTest,DontRemoveBackEdgeCombinedHeaderContinue)310 TEST(SimpleConditionalBranchToBranchTest,
311 DontRemoveBackEdgeCombinedHeaderContinue) {
312 // A test with the following structure.
313 //
314 // loop header and continue target and back-edge block
315 // OpBranchConditional
316 // ||
317 // loop merge (to loop header^)
318 //
319 // The conditional branch can be simplified.
320
321 std::string shader = R"(
322 OpCapability Shader
323 %1 = OpExtInstImport "GLSL.std.450"
324 OpMemoryModel Logical GLSL450
325 OpEntryPoint Fragment %2 "main"
326 OpExecutionMode %2 OriginUpperLeft
327 OpSource ESSL 310
328 OpName %2 "main"
329 %3 = OpTypeVoid
330 %4 = OpTypeFunction %3
331 %5 = OpTypeInt 32 1
332 %6 = OpTypePointer Function %5
333 %7 = OpTypeBool
334 %8 = OpConstantTrue %7
335 %2 = OpFunction %3 None %4
336 %9 = OpLabel
337 OpBranch %10
338 %10 = OpLabel
339 OpLoopMerge %11 %10 None
340 OpBranchConditional %8 %10 %10
341 %11 = OpLabel
342 OpReturn
343 OpFunctionEnd
344 )";
345
346 const auto context =
347 BuildModule(kEnv, nullptr, shader, kReduceAssembleOption);
348
349 CheckValid(kEnv, context.get());
350
351 auto ops = SimpleConditionalBranchToBranchOpportunityFinder()
352 .GetAvailableOpportunities(context.get(), 0);
353
354 ASSERT_EQ(1, ops.size());
355
356 ASSERT_TRUE(ops[0]->PreconditionHolds());
357 ops[0]->TryToApply();
358 CheckValid(kEnv, context.get());
359
360 std::string after = R"(
361 OpCapability Shader
362 %1 = OpExtInstImport "GLSL.std.450"
363 OpMemoryModel Logical GLSL450
364 OpEntryPoint Fragment %2 "main"
365 OpExecutionMode %2 OriginUpperLeft
366 OpSource ESSL 310
367 OpName %2 "main"
368 %3 = OpTypeVoid
369 %4 = OpTypeFunction %3
370 %5 = OpTypeInt 32 1
371 %6 = OpTypePointer Function %5
372 %7 = OpTypeBool
373 %8 = OpConstantTrue %7
374 %2 = OpFunction %3 None %4
375 %9 = OpLabel
376 OpBranch %10
377 %10 = OpLabel
378 OpLoopMerge %11 %10 None
379 OpBranch %10
380 %11 = OpLabel
381 OpReturn
382 OpFunctionEnd
383 )";
384 CheckEqual(kEnv, after, context.get());
385
386 ops = SimpleConditionalBranchToBranchOpportunityFinder()
387 .GetAvailableOpportunities(context.get(), 0);
388 ASSERT_EQ(0, ops.size());
389 }
390
TEST(SimpleConditionalBranchToBranchTest,BackEdgeUnreachable)391 TEST(SimpleConditionalBranchToBranchTest, BackEdgeUnreachable) {
392 // A test with the following structure. I.e. a loop with an unreachable
393 // continue construct that ends with OpBranchConditional.
394 //
395 // loop header
396 // |
397 // | loop continue target (unreachable)
398 // | |
399 // | back-edge block (unreachable)
400 // | OpBranchConditional
401 // | ||
402 // loop merge (to loop header^)
403 //
404 // The conditional branch can be simplified.
405
406 std::string shader = R"(
407 OpCapability Shader
408 %1 = OpExtInstImport "GLSL.std.450"
409 OpMemoryModel Logical GLSL450
410 OpEntryPoint Fragment %2 "main"
411 OpExecutionMode %2 OriginUpperLeft
412 OpSource ESSL 310
413 OpName %2 "main"
414 %3 = OpTypeVoid
415 %4 = OpTypeFunction %3
416 %5 = OpTypeInt 32 1
417 %6 = OpTypePointer Function %5
418 %7 = OpTypeBool
419 %8 = OpConstantTrue %7
420 %2 = OpFunction %3 None %4
421 %9 = OpLabel
422 OpBranch %10
423 %10 = OpLabel
424 OpLoopMerge %11 %12 None
425 OpBranch %11
426 %12 = OpLabel
427 OpBranch %13
428 %13 = OpLabel
429 OpBranchConditional %8 %10 %10
430 %11 = OpLabel
431 OpReturn
432 OpFunctionEnd
433 )";
434
435 const auto context =
436 BuildModule(kEnv, nullptr, shader, kReduceAssembleOption);
437
438 CheckValid(kEnv, context.get());
439
440 auto ops = SimpleConditionalBranchToBranchOpportunityFinder()
441 .GetAvailableOpportunities(context.get(), 0);
442
443 ASSERT_EQ(1, ops.size());
444
445 ASSERT_TRUE(ops[0]->PreconditionHolds());
446 ops[0]->TryToApply();
447 CheckValid(kEnv, context.get());
448
449 std::string after = R"(
450 OpCapability Shader
451 %1 = OpExtInstImport "GLSL.std.450"
452 OpMemoryModel Logical GLSL450
453 OpEntryPoint Fragment %2 "main"
454 OpExecutionMode %2 OriginUpperLeft
455 OpSource ESSL 310
456 OpName %2 "main"
457 %3 = OpTypeVoid
458 %4 = OpTypeFunction %3
459 %5 = OpTypeInt 32 1
460 %6 = OpTypePointer Function %5
461 %7 = OpTypeBool
462 %8 = OpConstantTrue %7
463 %2 = OpFunction %3 None %4
464 %9 = OpLabel
465 OpBranch %10
466 %10 = OpLabel
467 OpLoopMerge %11 %12 None
468 OpBranch %11
469 %12 = OpLabel
470 OpBranch %13
471 %13 = OpLabel
472 OpBranch %10
473 %11 = OpLabel
474 OpReturn
475 OpFunctionEnd
476 )";
477 CheckEqual(kEnv, after, context.get());
478
479 ops = SimpleConditionalBranchToBranchOpportunityFinder()
480 .GetAvailableOpportunities(context.get(), 0);
481 ASSERT_EQ(0, ops.size());
482 }
483
484 } // namespace
485 } // namespace reduce
486 } // namespace spvtools
487