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