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/fuzz/transformation_move_block_down.h"
16 
17 #include "gtest/gtest.h"
18 #include "source/fuzz/fuzzer_util.h"
19 #include "test/fuzz/fuzz_test_util.h"
20 
21 namespace spvtools {
22 namespace fuzz {
23 namespace {
24 
TEST(TransformationMoveBlockDownTest,NoMovePossible1)25 TEST(TransformationMoveBlockDownTest, NoMovePossible1) {
26   // Block 11 cannot be moved down as it dominates block 12.
27   std::string shader = R"(
28                OpCapability Shader
29           %1 = OpExtInstImport "GLSL.std.450"
30                OpMemoryModel Logical GLSL450
31                OpEntryPoint Fragment %4 "main"
32                OpExecutionMode %4 OriginUpperLeft
33                OpSource ESSL 310
34                OpDecorate %8 RelaxedPrecision
35           %2 = OpTypeVoid
36           %3 = OpTypeFunction %2
37           %6 = OpTypeInt 32 1
38           %7 = OpTypePointer Function %6
39           %9 = OpConstant %6 1
40          %10 = OpConstant %6 2
41           %4 = OpFunction %2 None %3
42           %5 = OpLabel
43           %8 = OpVariable %7 Function
44                OpBranch %11
45          %11 = OpLabel
46                OpStore %8 %9
47                OpBranch %12
48          %12 = OpLabel
49                OpStore %8 %10
50                OpReturn
51                OpFunctionEnd
52   )";
53 
54   const auto env = SPV_ENV_UNIVERSAL_1_3;
55   const auto consumer = nullptr;
56   const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
57 
58   spvtools::ValidatorOptions validator_options;
59   TransformationContext transformation_context(
60       MakeUnique<FactManager>(context.get()), validator_options);
61   auto transformation = TransformationMoveBlockDown(11);
62   ASSERT_FALSE(
63       transformation.IsApplicable(context.get(), transformation_context));
64 }
65 
TEST(TransformationMoveBlockDownTest,NoMovePossible2)66 TEST(TransformationMoveBlockDownTest, NoMovePossible2) {
67   // Block 5 cannot be moved down as it is the entry block.
68   std::string shader = R"(
69                OpCapability Shader
70           %1 = OpExtInstImport "GLSL.std.450"
71                OpMemoryModel Logical GLSL450
72                OpEntryPoint Fragment %4 "main"
73                OpExecutionMode %4 OriginUpperLeft
74                OpSource ESSL 310
75                OpDecorate %8 RelaxedPrecision
76           %2 = OpTypeVoid
77           %3 = OpTypeFunction %2
78           %6 = OpTypeInt 32 1
79           %7 = OpTypePointer Function %6
80           %9 = OpConstant %6 1
81          %10 = OpConstant %6 2
82           %4 = OpFunction %2 None %3
83           %5 = OpLabel
84           %8 = OpVariable %7 Function
85                OpStore %8 %9
86                OpStore %8 %10
87                OpReturn
88          %11 = OpLabel
89                OpReturn
90                OpFunctionEnd
91   )";
92 
93   const auto env = SPV_ENV_UNIVERSAL_1_3;
94   const auto consumer = nullptr;
95   const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
96 
97   spvtools::ValidatorOptions validator_options;
98   TransformationContext transformation_context(
99       MakeUnique<FactManager>(context.get()), validator_options);
100   auto transformation = TransformationMoveBlockDown(5);
101   ASSERT_FALSE(
102       transformation.IsApplicable(context.get(), transformation_context));
103 }
104 
TEST(TransformationMoveBlockDownTest,NoMovePossible3)105 TEST(TransformationMoveBlockDownTest, NoMovePossible3) {
106   // Block 100 does not exist, so cannot be moved down.
107   std::string shader = R"(
108                OpCapability Shader
109           %1 = OpExtInstImport "GLSL.std.450"
110                OpMemoryModel Logical GLSL450
111                OpEntryPoint Fragment %4 "main"
112                OpExecutionMode %4 OriginUpperLeft
113                OpSource ESSL 310
114                OpDecorate %8 RelaxedPrecision
115           %2 = OpTypeVoid
116           %3 = OpTypeFunction %2
117           %6 = OpTypeInt 32 1
118           %7 = OpTypePointer Function %6
119           %9 = OpConstant %6 1
120          %10 = OpConstant %6 2
121           %4 = OpFunction %2 None %3
122           %5 = OpLabel
123           %8 = OpVariable %7 Function
124                OpBranch %11
125          %11 = OpLabel
126                OpStore %8 %9
127                OpBranch %12
128          %12 = OpLabel
129                OpStore %8 %10
130                OpReturn
131                OpFunctionEnd
132   )";
133 
134   const auto env = SPV_ENV_UNIVERSAL_1_3;
135   const auto consumer = nullptr;
136   const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
137 
138   spvtools::ValidatorOptions validator_options;
139   TransformationContext transformation_context(
140       MakeUnique<FactManager>(context.get()), validator_options);
141   auto transformation = TransformationMoveBlockDown(100);
142   ASSERT_FALSE(
143       transformation.IsApplicable(context.get(), transformation_context));
144 }
145 
TEST(TransformationMoveBlockDownTest,NoMovePossible4)146 TEST(TransformationMoveBlockDownTest, NoMovePossible4) {
147   // Block 12 is the last block in its function, so cannot be moved down.
148   std::string shader = R"(
149                OpCapability Shader
150           %1 = OpExtInstImport "GLSL.std.450"
151                OpMemoryModel Logical GLSL450
152                OpEntryPoint Fragment %4 "main"
153                OpExecutionMode %4 OriginUpperLeft
154                OpSource ESSL 310
155                OpDecorate %8 RelaxedPrecision
156           %2 = OpTypeVoid
157           %3 = OpTypeFunction %2
158           %6 = OpTypeInt 32 1
159           %7 = OpTypePointer Function %6
160           %9 = OpConstant %6 1
161          %10 = OpConstant %6 2
162           %4 = OpFunction %2 None %3
163           %5 = OpLabel
164           %8 = OpVariable %7 Function
165                OpBranch %11
166          %11 = OpLabel
167                OpStore %8 %9
168                OpBranch %12
169          %12 = OpLabel
170                OpStore %8 %10
171                OpReturn
172                OpFunctionEnd
173          %13 = OpFunction %2 None %3
174          %14 = OpLabel
175                OpReturn
176                OpFunctionEnd
177   )";
178 
179   const auto env = SPV_ENV_UNIVERSAL_1_3;
180   const auto consumer = nullptr;
181   const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
182 
183   spvtools::ValidatorOptions validator_options;
184   TransformationContext transformation_context(
185       MakeUnique<FactManager>(context.get()), validator_options);
186   auto transformation = TransformationMoveBlockDown(12);
187   ASSERT_FALSE(
188       transformation.IsApplicable(context.get(), transformation_context));
189 }
190 
TEST(TransformationMoveBlockDownTest,ManyMovesPossible)191 TEST(TransformationMoveBlockDownTest, ManyMovesPossible) {
192   // The SPIR-V arising from this shader has lots of opportunities for moving
193   // blocks around.
194   //
195   // void main() {
196   //   int x;
197   //   int y;
198   //   if (x < y) {
199   //     x = 1;
200   //     if (y == x) {
201   //       x = 3;
202   //     } else {
203   //       x = 4;
204   //     }
205   //   } else {
206   //     if (y < x) {
207   //       x = 5;
208   //     } else {
209   //       x = 6;
210   //     }
211   //   }
212   // }
213 
214   std::string before_transformation = R"(
215                OpCapability Shader
216           %1 = OpExtInstImport "GLSL.std.450"
217                OpMemoryModel Logical GLSL450
218                OpEntryPoint Fragment %4 "main"
219                OpExecutionMode %4 OriginUpperLeft
220                OpSource ESSL 310
221                OpName %4 "main"
222                OpName %8 "x"
223                OpName %10 "y"
224                OpDecorate %8 RelaxedPrecision
225                OpDecorate %9 RelaxedPrecision
226                OpDecorate %10 RelaxedPrecision
227                OpDecorate %11 RelaxedPrecision
228                OpDecorate %17 RelaxedPrecision
229                OpDecorate %18 RelaxedPrecision
230                OpDecorate %26 RelaxedPrecision
231                OpDecorate %27 RelaxedPrecision
232           %2 = OpTypeVoid
233           %3 = OpTypeFunction %2
234           %6 = OpTypeInt 32 1
235           %7 = OpTypePointer Function %6
236          %12 = OpTypeBool
237          %16 = OpConstant %6 1
238          %22 = OpConstant %6 3
239          %24 = OpConstant %6 4
240          %31 = OpConstant %6 5
241          %33 = OpConstant %6 6
242           %4 = OpFunction %2 None %3
243           %5 = OpLabel
244           %8 = OpVariable %7 Function
245          %10 = OpVariable %7 Function
246           %9 = OpLoad %6 %8
247          %11 = OpLoad %6 %10
248          %13 = OpSLessThan %12 %9 %11
249                OpSelectionMerge %15 None
250                OpBranchConditional %13 %14 %25
251          %14 = OpLabel
252                OpStore %8 %16
253          %17 = OpLoad %6 %10
254          %18 = OpLoad %6 %8
255          %19 = OpIEqual %12 %17 %18
256                OpSelectionMerge %21 None
257                OpBranchConditional %19 %20 %23
258          %20 = OpLabel
259                OpStore %8 %22
260                OpBranch %21
261          %23 = OpLabel
262                OpStore %8 %24
263                OpBranch %21
264          %21 = OpLabel
265                OpBranch %15
266          %25 = OpLabel
267          %26 = OpLoad %6 %10
268          %27 = OpLoad %6 %8
269          %28 = OpSLessThan %12 %26 %27
270                OpSelectionMerge %30 None
271                OpBranchConditional %28 %29 %32
272          %29 = OpLabel
273                OpStore %8 %31
274                OpBranch %30
275          %32 = OpLabel
276                OpStore %8 %33
277                OpBranch %30
278          %30 = OpLabel
279                OpBranch %15
280          %15 = OpLabel
281                OpReturn
282                OpFunctionEnd
283   )";
284 
285   const auto env = SPV_ENV_UNIVERSAL_1_3;
286   const auto consumer = nullptr;
287   const auto context =
288       BuildModule(env, consumer, before_transformation, kFuzzAssembleOption);
289 
290   spvtools::ValidatorOptions validator_options;
291   TransformationContext transformation_context(
292       MakeUnique<FactManager>(context.get()), validator_options);
293   // The block ids are: 5 14 20 23 21 25 29 32 30 15
294   // We make a transformation to move each of them down, plus a transformation
295   // to move a non-block, 27, down.
296   auto move_down_5 = TransformationMoveBlockDown(5);
297   auto move_down_14 = TransformationMoveBlockDown(14);
298   auto move_down_20 = TransformationMoveBlockDown(20);
299   auto move_down_23 = TransformationMoveBlockDown(23);
300   auto move_down_21 = TransformationMoveBlockDown(21);
301   auto move_down_25 = TransformationMoveBlockDown(25);
302   auto move_down_29 = TransformationMoveBlockDown(29);
303   auto move_down_32 = TransformationMoveBlockDown(32);
304   auto move_down_30 = TransformationMoveBlockDown(30);
305   auto move_down_15 = TransformationMoveBlockDown(15);
306   auto move_down_27 = TransformationMoveBlockDown(27);
307 
308   // Dominance is as follows:
309   //  5 dominates everything else
310   // 14 dominates 20, 23, 21
311   // 20 dominates nothing
312   // 23 dominates nothing
313   // 21 dominates nothing
314   // 25 dominates 29, 32, 30
315   // 29 dominates nothing
316   // 32 dominates nothing
317   // 30 dominates nothing
318   // 15 dominates nothing
319 
320   // Current ordering: 5 14 20 23 21 25 29 32 30 15
321   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
322   ASSERT_FALSE(
323       move_down_14.IsApplicable(context.get(), transformation_context));
324   ASSERT_TRUE(move_down_20.IsApplicable(context.get(), transformation_context));
325   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
326   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
327   ASSERT_FALSE(
328       move_down_25.IsApplicable(context.get(), transformation_context));
329   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
330   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
331   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
332   ASSERT_FALSE(
333       move_down_15.IsApplicable(context.get(), transformation_context));
334 
335   // Let's bubble 20 all the way down.
336 
337   ApplyAndCheckFreshIds(move_down_20, context.get(), &transformation_context);
338   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
339                                                kConsoleMessageConsumer));
340 
341   // Current ordering: 5 14 23 20 21 25 29 32 30 15
342   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
343   ASSERT_FALSE(
344       move_down_14.IsApplicable(context.get(), transformation_context));
345   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
346   ASSERT_TRUE(move_down_20.IsApplicable(context.get(), transformation_context));
347   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
348   ASSERT_FALSE(
349       move_down_25.IsApplicable(context.get(), transformation_context));
350   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
351   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
352   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
353   ASSERT_FALSE(
354       move_down_15.IsApplicable(context.get(), transformation_context));
355 
356   ApplyAndCheckFreshIds(move_down_20, context.get(), &transformation_context);
357   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
358                                                kConsoleMessageConsumer));
359 
360   // Current ordering: 5 14 23 21 20 25 29 32 30 15
361   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
362   ASSERT_FALSE(
363       move_down_14.IsApplicable(context.get(), transformation_context));
364   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
365   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
366   ASSERT_TRUE(move_down_20.IsApplicable(context.get(), transformation_context));
367   ASSERT_FALSE(
368       move_down_25.IsApplicable(context.get(), transformation_context));
369   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
370   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
371   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
372   ASSERT_FALSE(
373       move_down_15.IsApplicable(context.get(), transformation_context));
374 
375   ApplyAndCheckFreshIds(move_down_20, context.get(), &transformation_context);
376   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
377                                                kConsoleMessageConsumer));
378 
379   // Current ordering: 5 14 23 21 25 20 29 32 30 15
380   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
381   ASSERT_FALSE(
382       move_down_14.IsApplicable(context.get(), transformation_context));
383   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
384   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
385   ASSERT_TRUE(move_down_25.IsApplicable(context.get(), transformation_context));
386   ASSERT_TRUE(move_down_20.IsApplicable(context.get(), transformation_context));
387   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
388   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
389   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
390   ASSERT_FALSE(
391       move_down_15.IsApplicable(context.get(), transformation_context));
392 
393   ApplyAndCheckFreshIds(move_down_20, context.get(), &transformation_context);
394   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
395                                                kConsoleMessageConsumer));
396 
397   // Current ordering: 5 14 23 21 25 29 20 32 30 15
398   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
399   ASSERT_FALSE(
400       move_down_14.IsApplicable(context.get(), transformation_context));
401   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
402   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
403   ASSERT_FALSE(
404       move_down_25.IsApplicable(context.get(), transformation_context));
405   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
406   ASSERT_TRUE(move_down_20.IsApplicable(context.get(), transformation_context));
407   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
408   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
409   ASSERT_FALSE(
410       move_down_15.IsApplicable(context.get(), transformation_context));
411 
412   ApplyAndCheckFreshIds(move_down_20, context.get(), &transformation_context);
413   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
414                                                kConsoleMessageConsumer));
415 
416   // Current ordering: 5 14 23 21 25 29 32 20 30 15
417   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
418   ASSERT_FALSE(
419       move_down_14.IsApplicable(context.get(), transformation_context));
420   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
421   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
422   ASSERT_FALSE(
423       move_down_25.IsApplicable(context.get(), transformation_context));
424   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
425   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
426   ASSERT_TRUE(move_down_20.IsApplicable(context.get(), transformation_context));
427   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
428   ASSERT_FALSE(
429       move_down_15.IsApplicable(context.get(), transformation_context));
430 
431   ApplyAndCheckFreshIds(move_down_20, context.get(), &transformation_context);
432   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
433                                                kConsoleMessageConsumer));
434 
435   // Current ordering: 5 14 23 21 25 29 32 30 20 15
436   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
437   ASSERT_FALSE(
438       move_down_14.IsApplicable(context.get(), transformation_context));
439   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
440   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
441   ASSERT_FALSE(
442       move_down_25.IsApplicable(context.get(), transformation_context));
443   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
444   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
445   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
446   ASSERT_TRUE(move_down_20.IsApplicable(context.get(), transformation_context));
447   ASSERT_FALSE(
448       move_down_15.IsApplicable(context.get(), transformation_context));
449 
450   ApplyAndCheckFreshIds(move_down_20, context.get(), &transformation_context);
451   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
452                                                kConsoleMessageConsumer));
453 
454   std::string after_bubbling_20_down = R"(
455                OpCapability Shader
456           %1 = OpExtInstImport "GLSL.std.450"
457                OpMemoryModel Logical GLSL450
458                OpEntryPoint Fragment %4 "main"
459                OpExecutionMode %4 OriginUpperLeft
460                OpSource ESSL 310
461                OpName %4 "main"
462                OpName %8 "x"
463                OpName %10 "y"
464                OpDecorate %8 RelaxedPrecision
465                OpDecorate %9 RelaxedPrecision
466                OpDecorate %10 RelaxedPrecision
467                OpDecorate %11 RelaxedPrecision
468                OpDecorate %17 RelaxedPrecision
469                OpDecorate %18 RelaxedPrecision
470                OpDecorate %26 RelaxedPrecision
471                OpDecorate %27 RelaxedPrecision
472           %2 = OpTypeVoid
473           %3 = OpTypeFunction %2
474           %6 = OpTypeInt 32 1
475           %7 = OpTypePointer Function %6
476          %12 = OpTypeBool
477          %16 = OpConstant %6 1
478          %22 = OpConstant %6 3
479          %24 = OpConstant %6 4
480          %31 = OpConstant %6 5
481          %33 = OpConstant %6 6
482           %4 = OpFunction %2 None %3
483           %5 = OpLabel
484           %8 = OpVariable %7 Function
485          %10 = OpVariable %7 Function
486           %9 = OpLoad %6 %8
487          %11 = OpLoad %6 %10
488          %13 = OpSLessThan %12 %9 %11
489                OpSelectionMerge %15 None
490                OpBranchConditional %13 %14 %25
491          %14 = OpLabel
492                OpStore %8 %16
493          %17 = OpLoad %6 %10
494          %18 = OpLoad %6 %8
495          %19 = OpIEqual %12 %17 %18
496                OpSelectionMerge %21 None
497                OpBranchConditional %19 %20 %23
498          %23 = OpLabel
499                OpStore %8 %24
500                OpBranch %21
501          %21 = OpLabel
502                OpBranch %15
503          %25 = OpLabel
504          %26 = OpLoad %6 %10
505          %27 = OpLoad %6 %8
506          %28 = OpSLessThan %12 %26 %27
507                OpSelectionMerge %30 None
508                OpBranchConditional %28 %29 %32
509          %29 = OpLabel
510                OpStore %8 %31
511                OpBranch %30
512          %32 = OpLabel
513                OpStore %8 %33
514                OpBranch %30
515          %30 = OpLabel
516                OpBranch %15
517          %15 = OpLabel
518                OpReturn
519          %20 = OpLabel
520                OpStore %8 %22
521                OpBranch %21
522                OpFunctionEnd
523   )";
524   ASSERT_TRUE(IsEqual(env, after_bubbling_20_down, context.get()));
525 
526   // Current ordering: 5 14 23 21 25 29 32 30 15 20
527   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
528   ASSERT_FALSE(
529       move_down_14.IsApplicable(context.get(), transformation_context));
530   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
531   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
532   ASSERT_FALSE(
533       move_down_25.IsApplicable(context.get(), transformation_context));
534   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
535   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
536   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
537   ASSERT_TRUE(move_down_15.IsApplicable(context.get(), transformation_context));
538   ASSERT_FALSE(
539       move_down_20.IsApplicable(context.get(), transformation_context));
540 
541   ApplyAndCheckFreshIds(move_down_23, context.get(), &transformation_context);
542   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
543                                                kConsoleMessageConsumer));
544 
545   // Current ordering: 5 14 21 23 25 29 32 30 15 20
546   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
547   ASSERT_FALSE(
548       move_down_14.IsApplicable(context.get(), transformation_context));
549   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
550   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
551   ASSERT_FALSE(
552       move_down_25.IsApplicable(context.get(), transformation_context));
553   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
554   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
555   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
556   ASSERT_TRUE(move_down_15.IsApplicable(context.get(), transformation_context));
557   ASSERT_FALSE(
558       move_down_20.IsApplicable(context.get(), transformation_context));
559 
560   ApplyAndCheckFreshIds(move_down_23, context.get(), &transformation_context);
561   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
562                                                kConsoleMessageConsumer));
563 
564   // Current ordering: 5 14 21 25 23 29 32 30 15 20
565   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
566   ASSERT_FALSE(
567       move_down_14.IsApplicable(context.get(), transformation_context));
568   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
569   ASSERT_TRUE(move_down_25.IsApplicable(context.get(), transformation_context));
570   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
571   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
572   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
573   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
574   ASSERT_TRUE(move_down_15.IsApplicable(context.get(), transformation_context));
575   ASSERT_FALSE(
576       move_down_20.IsApplicable(context.get(), transformation_context));
577 
578   ApplyAndCheckFreshIds(move_down_21, context.get(), &transformation_context);
579   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
580                                                kConsoleMessageConsumer));
581 
582   // Current ordering: 5 14 25 21 23 29 32 30 15 20
583   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
584   ASSERT_TRUE(move_down_14.IsApplicable(context.get(), transformation_context));
585   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
586   ASSERT_TRUE(move_down_25.IsApplicable(context.get(), transformation_context));
587   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
588   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
589   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
590   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
591   ASSERT_TRUE(move_down_15.IsApplicable(context.get(), transformation_context));
592   ASSERT_FALSE(
593       move_down_20.IsApplicable(context.get(), transformation_context));
594 
595   ApplyAndCheckFreshIds(move_down_14, context.get(), &transformation_context);
596   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
597                                                kConsoleMessageConsumer));
598 
599   std::string after_more_shuffling = R"(
600                OpCapability Shader
601           %1 = OpExtInstImport "GLSL.std.450"
602                OpMemoryModel Logical GLSL450
603                OpEntryPoint Fragment %4 "main"
604                OpExecutionMode %4 OriginUpperLeft
605                OpSource ESSL 310
606                OpName %4 "main"
607                OpName %8 "x"
608                OpName %10 "y"
609                OpDecorate %8 RelaxedPrecision
610                OpDecorate %9 RelaxedPrecision
611                OpDecorate %10 RelaxedPrecision
612                OpDecorate %11 RelaxedPrecision
613                OpDecorate %17 RelaxedPrecision
614                OpDecorate %18 RelaxedPrecision
615                OpDecorate %26 RelaxedPrecision
616                OpDecorate %27 RelaxedPrecision
617           %2 = OpTypeVoid
618           %3 = OpTypeFunction %2
619           %6 = OpTypeInt 32 1
620           %7 = OpTypePointer Function %6
621          %12 = OpTypeBool
622          %16 = OpConstant %6 1
623          %22 = OpConstant %6 3
624          %24 = OpConstant %6 4
625          %31 = OpConstant %6 5
626          %33 = OpConstant %6 6
627           %4 = OpFunction %2 None %3
628           %5 = OpLabel
629           %8 = OpVariable %7 Function
630          %10 = OpVariable %7 Function
631           %9 = OpLoad %6 %8
632          %11 = OpLoad %6 %10
633          %13 = OpSLessThan %12 %9 %11
634                OpSelectionMerge %15 None
635                OpBranchConditional %13 %14 %25
636          %25 = OpLabel
637          %26 = OpLoad %6 %10
638          %27 = OpLoad %6 %8
639          %28 = OpSLessThan %12 %26 %27
640                OpSelectionMerge %30 None
641                OpBranchConditional %28 %29 %32
642          %14 = OpLabel
643                OpStore %8 %16
644          %17 = OpLoad %6 %10
645          %18 = OpLoad %6 %8
646          %19 = OpIEqual %12 %17 %18
647                OpSelectionMerge %21 None
648                OpBranchConditional %19 %20 %23
649          %21 = OpLabel
650                OpBranch %15
651          %23 = OpLabel
652                OpStore %8 %24
653                OpBranch %21
654          %29 = OpLabel
655                OpStore %8 %31
656                OpBranch %30
657          %32 = OpLabel
658                OpStore %8 %33
659                OpBranch %30
660          %30 = OpLabel
661                OpBranch %15
662          %15 = OpLabel
663                OpReturn
664          %20 = OpLabel
665                OpStore %8 %22
666                OpBranch %21
667                OpFunctionEnd
668   )";
669   ASSERT_TRUE(IsEqual(env, after_more_shuffling, context.get()));
670 
671   // Final ordering: 5 25 14 21 23 29 32 30 15 20
672   ASSERT_FALSE(move_down_5.IsApplicable(context.get(), transformation_context));
673   ASSERT_TRUE(move_down_25.IsApplicable(context.get(), transformation_context));
674   ASSERT_FALSE(
675       move_down_14.IsApplicable(context.get(), transformation_context));
676   ASSERT_TRUE(move_down_21.IsApplicable(context.get(), transformation_context));
677   ASSERT_TRUE(move_down_23.IsApplicable(context.get(), transformation_context));
678   ASSERT_TRUE(move_down_29.IsApplicable(context.get(), transformation_context));
679   ASSERT_TRUE(move_down_32.IsApplicable(context.get(), transformation_context));
680   ASSERT_TRUE(move_down_30.IsApplicable(context.get(), transformation_context));
681   ASSERT_TRUE(move_down_15.IsApplicable(context.get(), transformation_context));
682   ASSERT_FALSE(
683       move_down_20.IsApplicable(context.get(), transformation_context));
684 }
685 
TEST(TransformationMoveBlockDownTest,DoNotMoveUnreachable)686 TEST(TransformationMoveBlockDownTest, DoNotMoveUnreachable) {
687   // Block 6 is unreachable, so cannot be moved down.
688   std::string shader = R"(
689                OpCapability Shader
690           %1 = OpExtInstImport "GLSL.std.450"
691                OpMemoryModel Logical GLSL450
692                OpEntryPoint Fragment %4 "main"
693                OpExecutionMode %4 OriginUpperLeft
694                OpSource ESSL 310
695                OpName %4 "main"
696           %2 = OpTypeVoid
697           %3 = OpTypeFunction %2
698          %10 = OpTypeInt 32 1
699           %4 = OpFunction %2 None %3
700           %5 = OpLabel
701                OpReturn
702           %6 = OpLabel
703           %7 = OpUndef %10
704                OpBranch %8
705           %8 = OpLabel
706           %9 = OpCopyObject %10 %7
707                OpReturn
708                OpFunctionEnd
709   )";
710 
711   const auto env = SPV_ENV_UNIVERSAL_1_3;
712   const auto consumer = nullptr;
713   const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
714   spvtools::ValidatorOptions validator_options;
715   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
716                                                kConsoleMessageConsumer));
717   TransformationContext transformation_context(
718       MakeUnique<FactManager>(context.get()), validator_options);
719   auto transformation = TransformationMoveBlockDown(6);
720   ASSERT_FALSE(
721       transformation.IsApplicable(context.get(), transformation_context));
722 }
723 
724 }  // namespace
725 }  // namespace fuzz
726 }  // namespace spvtools
727