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/remove_selection_reduction_opportunity_finder.h"
16
17#include "source/opt/build_module.h"
18#include "source/reduce/reduction_opportunity.h"
19#include "test/reduce/reduce_test_util.h"
20
21namespace spvtools {
22namespace reduce {
23namespace {
24
25TEST(RemoveSelectionTest, OpportunityBecauseSameTargetBlock) {
26  // A test with the following structure. The OpSelectionMerge instruction
27  // should be removed.
28  //
29  // header
30  // ||
31  // block
32  // |
33  // merge
34
35  std::string shader = R"(
36               OpCapability Shader
37          %1 = OpExtInstImport "GLSL.std.450"
38               OpMemoryModel Logical GLSL450
39               OpEntryPoint Fragment %2 "main"
40               OpExecutionMode %2 OriginUpperLeft
41               OpSource ESSL 310
42               OpName %2 "main"
43          %3 = OpTypeVoid
44          %4 = OpTypeFunction %3
45          %5 = OpTypeInt 32 1
46          %6 = OpTypePointer Function %5
47          %7 = OpTypeBool
48          %8 = OpConstantTrue %7
49          %2 = OpFunction %3 None %4
50          %9 = OpLabel
51               OpSelectionMerge %10 None
52               OpBranchConditional %8 %11 %11
53         %11 = OpLabel
54               OpBranch %10
55         %10 = OpLabel
56               OpReturn
57               OpFunctionEnd
58    )";
59
60  const auto env = SPV_ENV_UNIVERSAL_1_3;
61  const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
62
63  auto ops =
64      RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
65          context.get(), 0);
66
67  ASSERT_EQ(1, ops.size());
68
69  ASSERT_TRUE(ops[0]->PreconditionHolds());
70  ops[0]->TryToApply();
71  CheckValid(env, context.get());
72
73  std::string after = R"(
74               OpCapability Shader
75          %1 = OpExtInstImport "GLSL.std.450"
76               OpMemoryModel Logical GLSL450
77               OpEntryPoint Fragment %2 "main"
78               OpExecutionMode %2 OriginUpperLeft
79               OpSource ESSL 310
80               OpName %2 "main"
81          %3 = OpTypeVoid
82          %4 = OpTypeFunction %3
83          %5 = OpTypeInt 32 1
84          %6 = OpTypePointer Function %5
85          %7 = OpTypeBool
86          %8 = OpConstantTrue %7
87          %2 = OpFunction %3 None %4
88          %9 = OpLabel
89               OpBranchConditional %8 %11 %11
90         %11 = OpLabel
91               OpBranch %10
92         %10 = OpLabel
93               OpReturn
94               OpFunctionEnd
95    )";
96  CheckEqual(env, after, context.get());
97
98  ops = RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
99      context.get(), 0);
100  ASSERT_EQ(0, ops.size());
101}
102
103TEST(RemoveSelectionTest, OpportunityBecauseSameTargetBlockMerge) {
104  // A test with the following structure. The OpSelectionMerge instruction
105  // should be removed.
106  //
107  // header
108  // ||
109  // merge
110
111  std::string shader = R"(
112               OpCapability Shader
113          %1 = OpExtInstImport "GLSL.std.450"
114               OpMemoryModel Logical GLSL450
115               OpEntryPoint Fragment %2 "main"
116               OpExecutionMode %2 OriginUpperLeft
117               OpSource ESSL 310
118               OpName %2 "main"
119          %3 = OpTypeVoid
120          %4 = OpTypeFunction %3
121          %5 = OpTypeInt 32 1
122          %6 = OpTypePointer Function %5
123          %7 = OpTypeBool
124          %8 = OpConstantTrue %7
125          %2 = OpFunction %3 None %4
126          %9 = OpLabel
127               OpSelectionMerge %10 None
128               OpBranchConditional %8 %10 %10
129         %10 = OpLabel
130               OpReturn
131               OpFunctionEnd
132    )";
133
134  const auto env = SPV_ENV_UNIVERSAL_1_3;
135  const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
136
137  auto ops =
138      RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
139          context.get(), 0);
140
141  ASSERT_EQ(1, ops.size());
142
143  ASSERT_TRUE(ops[0]->PreconditionHolds());
144  ops[0]->TryToApply();
145  CheckValid(env, context.get());
146
147  std::string after = R"(
148               OpCapability Shader
149          %1 = OpExtInstImport "GLSL.std.450"
150               OpMemoryModel Logical GLSL450
151               OpEntryPoint Fragment %2 "main"
152               OpExecutionMode %2 OriginUpperLeft
153               OpSource ESSL 310
154               OpName %2 "main"
155          %3 = OpTypeVoid
156          %4 = OpTypeFunction %3
157          %5 = OpTypeInt 32 1
158          %6 = OpTypePointer Function %5
159          %7 = OpTypeBool
160          %8 = OpConstantTrue %7
161          %2 = OpFunction %3 None %4
162          %9 = OpLabel
163               OpBranchConditional %8 %10 %10
164         %10 = OpLabel
165               OpReturn
166               OpFunctionEnd
167    )";
168  CheckEqual(env, after, context.get());
169
170  ops = RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
171      context.get(), 0);
172  ASSERT_EQ(0, ops.size());
173}
174
175TEST(RemoveSelectionTest, NoOpportunityBecauseDifferentTargetBlocksOneMerge) {
176  // A test with the following structure. The OpSelectionMerge instruction
177  // should NOT be removed.
178  //
179  // header
180  // |  |
181  // | block
182  // |  |
183  // merge
184
185  std::string shader = R"(
186               OpCapability Shader
187          %1 = OpExtInstImport "GLSL.std.450"
188               OpMemoryModel Logical GLSL450
189               OpEntryPoint Fragment %2 "main"
190               OpExecutionMode %2 OriginUpperLeft
191               OpSource ESSL 310
192               OpName %2 "main"
193          %3 = OpTypeVoid
194          %4 = OpTypeFunction %3
195          %5 = OpTypeInt 32 1
196          %6 = OpTypePointer Function %5
197          %7 = OpTypeBool
198          %8 = OpConstantTrue %7
199          %2 = OpFunction %3 None %4
200          %9 = OpLabel
201               OpSelectionMerge %10 None
202               OpBranchConditional %8 %10 %11
203         %11 = OpLabel
204               OpBranch %10
205         %10 = OpLabel
206               OpReturn
207               OpFunctionEnd
208    )";
209
210  const auto env = SPV_ENV_UNIVERSAL_1_3;
211  const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
212
213  auto ops =
214      RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
215          context.get(), 0);
216  ASSERT_EQ(0, ops.size());
217}
218
219TEST(RemoveSelectionTest, NoOpportunityBecauseDifferentTargetBlocks) {
220  // A test with the following structure. The OpSelectionMerge instruction
221  // should NOT be removed.
222  //
223  // header
224  // | |
225  // b b
226  // | |
227  // merge
228
229  std::string shader = R"(
230               OpCapability Shader
231          %1 = OpExtInstImport "GLSL.std.450"
232               OpMemoryModel Logical GLSL450
233               OpEntryPoint Fragment %2 "main"
234               OpExecutionMode %2 OriginUpperLeft
235               OpSource ESSL 310
236               OpName %2 "main"
237          %3 = OpTypeVoid
238          %4 = OpTypeFunction %3
239          %5 = OpTypeInt 32 1
240          %6 = OpTypePointer Function %5
241          %7 = OpTypeBool
242          %8 = OpConstantTrue %7
243          %2 = OpFunction %3 None %4
244          %9 = OpLabel
245               OpSelectionMerge %10 None
246               OpBranchConditional %8 %11 %12
247         %11 = OpLabel
248               OpBranch %10
249         %12 = OpLabel
250               OpBranch %10
251         %10 = OpLabel
252               OpReturn
253               OpFunctionEnd
254    )";
255
256  const auto env = SPV_ENV_UNIVERSAL_1_3;
257  const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
258
259  auto ops =
260      RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
261          context.get(), 0);
262  ASSERT_EQ(0, ops.size());
263}
264
265TEST(RemoveSelectionTest, NoOpportunityBecauseMergeUsed) {
266  // A test with the following structure. The OpSelectionMerge instruction
267  // should NOT be removed.
268  //
269  // header
270  // ||
271  // block
272  // |  |
273  // | block
274  // |  |
275  // merge
276
277  std::string shader = 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               OpSelectionMerge %10 None
294               OpBranchConditional %8 %11 %12
295         %11 = OpLabel
296               OpBranchConditional %8 %10 %12
297         %12 = OpLabel
298               OpBranch %10
299         %10 = OpLabel
300               OpReturn
301               OpFunctionEnd
302    )";
303
304  const auto env = SPV_ENV_UNIVERSAL_1_3;
305  const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
306
307  auto ops =
308      RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
309          context.get(), 0);
310  ASSERT_EQ(0, ops.size());
311}
312
313TEST(RemoveSelectionTest, OpportunityBecauseLoopMergeUsed) {
314  // A test with the following structure. The OpSelectionMerge instruction
315  // should be removed.
316  //
317  // loop header
318  //    |
319  //    |
320  //   s.header
321  //    ||
322  //   block
323  //    |    |
324  //    |     |
325  //    |      |    ^ (to loop header)
326  //   s.merge |    |
327  //    |     /   loop continue target (unreachable)
328  // loop merge
329  //
330  //
331  // which becomes:
332  //
333  // loop header
334  //    |
335  //    |
336  //   block
337  //    ||
338  //   block
339  //    |    |
340  //    |     |
341  //    |      |    ^ (to loop header)
342  //   block   |    |
343  //    |     /   loop continue target (unreachable)
344  // loop merge
345
346  std::string shader = R"(
347               OpCapability Shader
348          %1 = OpExtInstImport "GLSL.std.450"
349               OpMemoryModel Logical GLSL450
350               OpEntryPoint Fragment %2 "main"
351               OpExecutionMode %2 OriginUpperLeft
352               OpSource ESSL 310
353               OpName %2 "main"
354          %3 = OpTypeVoid
355          %4 = OpTypeFunction %3
356          %5 = OpTypeInt 32 1
357          %6 = OpTypePointer Function %5
358          %7 = OpTypeBool
359          %8 = OpConstantTrue %7
360          %2 = OpFunction %3 None %4
361          %9 = OpLabel
362               OpBranch %10
363         %10 = OpLabel
364               OpLoopMerge %11 %12 None
365               OpBranch %13
366         %13 = OpLabel
367               OpSelectionMerge %14 None
368               OpBranchConditional %8 %15 %15
369         %15 = OpLabel
370               OpBranchConditional %8 %14 %11
371         %14 = OpLabel
372               OpBranch %11
373         %12 = OpLabel
374               OpBranch %10
375         %11 = OpLabel
376               OpReturn
377               OpFunctionEnd
378    )";
379
380  const auto env = SPV_ENV_UNIVERSAL_1_3;
381  const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
382
383  CheckValid(env, context.get());
384
385  auto ops =
386      RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
387          context.get(), 0);
388
389  ASSERT_EQ(1, ops.size());
390
391  ASSERT_TRUE(ops[0]->PreconditionHolds());
392  ops[0]->TryToApply();
393  CheckValid(env, context.get());
394
395  std::string after = R"(
396               OpCapability Shader
397          %1 = OpExtInstImport "GLSL.std.450"
398               OpMemoryModel Logical GLSL450
399               OpEntryPoint Fragment %2 "main"
400               OpExecutionMode %2 OriginUpperLeft
401               OpSource ESSL 310
402               OpName %2 "main"
403          %3 = OpTypeVoid
404          %4 = OpTypeFunction %3
405          %5 = OpTypeInt 32 1
406          %6 = OpTypePointer Function %5
407          %7 = OpTypeBool
408          %8 = OpConstantTrue %7
409          %2 = OpFunction %3 None %4
410          %9 = OpLabel
411               OpBranch %10
412         %10 = OpLabel
413               OpLoopMerge %11 %12 None
414               OpBranch %13
415         %13 = OpLabel
416               OpBranchConditional %8 %15 %15
417         %15 = OpLabel
418               OpBranchConditional %8 %14 %11
419         %14 = OpLabel
420               OpBranch %11
421         %12 = OpLabel
422               OpBranch %10
423         %11 = OpLabel
424               OpReturn
425               OpFunctionEnd
426    )";
427  CheckEqual(env, after, context.get());
428
429  ops = RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
430      context.get(), 0);
431  ASSERT_EQ(0, ops.size());
432}
433
434TEST(RemoveSelectionTest, OpportunityBecauseLoopContinueUsed) {
435  // A test with the following structure. The OpSelectionMerge instruction
436  // should be removed.
437  //
438  // loop header
439  //    |
440  //    |
441  //   s.header
442  //    ||
443  //   block
444  //    |    |
445  //    |     |
446  //    |      |    ^ (to loop header)
447  //   s.merge |    |
448  //    |     loop continue target
449  // loop merge
450  //
451  //
452  // which becomes:
453  //
454  // loop header
455  //    |
456  //    |
457  //   block
458  //    ||
459  //   block
460  //    |    |
461  //    |     |
462  //    |      |    ^ (to loop header)
463  //   block   |    |
464  //    |     loop continue target
465  // loop merge
466
467  std::string shader = R"(
468               OpCapability Shader
469          %1 = OpExtInstImport "GLSL.std.450"
470               OpMemoryModel Logical GLSL450
471               OpEntryPoint Fragment %2 "main"
472               OpExecutionMode %2 OriginUpperLeft
473               OpSource ESSL 310
474               OpName %2 "main"
475          %3 = OpTypeVoid
476          %4 = OpTypeFunction %3
477          %5 = OpTypeInt 32 1
478          %6 = OpTypePointer Function %5
479          %7 = OpTypeBool
480          %8 = OpConstantTrue %7
481          %2 = OpFunction %3 None %4
482          %9 = OpLabel
483               OpBranch %10
484         %10 = OpLabel
485               OpLoopMerge %11 %12 None
486               OpBranch %13
487         %13 = OpLabel
488               OpSelectionMerge %14 None
489               OpBranchConditional %8 %15 %15
490         %15 = OpLabel
491               OpBranchConditional %8 %14 %12
492         %14 = OpLabel
493               OpBranch %11
494         %12 = OpLabel
495               OpBranch %10
496         %11 = OpLabel
497               OpReturn
498               OpFunctionEnd
499    )";
500
501  const auto env = SPV_ENV_UNIVERSAL_1_3;
502  const auto context = BuildModule(env, nullptr, shader, kReduceAssembleOption);
503
504  CheckValid(env, context.get());
505
506  auto ops =
507      RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
508          context.get(), 0);
509
510  ASSERT_EQ(1, ops.size());
511
512  ASSERT_TRUE(ops[0]->PreconditionHolds());
513  ops[0]->TryToApply();
514  CheckValid(env, context.get());
515
516  std::string after = R"(
517               OpCapability Shader
518          %1 = OpExtInstImport "GLSL.std.450"
519               OpMemoryModel Logical GLSL450
520               OpEntryPoint Fragment %2 "main"
521               OpExecutionMode %2 OriginUpperLeft
522               OpSource ESSL 310
523               OpName %2 "main"
524          %3 = OpTypeVoid
525          %4 = OpTypeFunction %3
526          %5 = OpTypeInt 32 1
527          %6 = OpTypePointer Function %5
528          %7 = OpTypeBool
529          %8 = OpConstantTrue %7
530          %2 = OpFunction %3 None %4
531          %9 = OpLabel
532               OpBranch %10
533         %10 = OpLabel
534               OpLoopMerge %11 %12 None
535               OpBranch %13
536         %13 = OpLabel
537               OpBranchConditional %8 %15 %15
538         %15 = OpLabel
539               OpBranchConditional %8 %14 %12
540         %14 = OpLabel
541               OpBranch %11
542         %12 = OpLabel
543               OpBranch %10
544         %11 = OpLabel
545               OpReturn
546               OpFunctionEnd
547    )";
548  CheckEqual(env, after, context.get());
549
550  ops = RemoveSelectionReductionOpportunityFinder().GetAvailableOpportunities(
551      context.get(), 0);
552  ASSERT_EQ(0, ops.size());
553}
554
555}  // namespace
556}  // namespace reduce
557}  // namespace spvtools
558