1 // Copyright (c) 2020 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/fuzzer_pass_outline_functions.h"
16
17 #include "gtest/gtest.h"
18 #include "source/fuzz/fuzzer_util.h"
19 #include "source/fuzz/pseudo_random_generator.h"
20 #include "test/fuzz/fuzz_test_util.h"
21
22 namespace spvtools {
23 namespace fuzz {
24 namespace {
25
26 std::string shader = R"(
27 OpCapability Shader
28 %1 = OpExtInstImport "GLSL.std.450"
29 OpMemoryModel Logical GLSL450
30 OpEntryPoint Fragment %2 "main"
31 OpExecutionMode %2 OriginUpperLeft
32 OpSource ESSL 310
33 OpName %2 "main"
34 OpName %3 "a"
35 OpName %4 "b"
36 OpDecorate %3 RelaxedPrecision
37 OpDecorate %4 RelaxedPrecision
38 OpDecorate %5 RelaxedPrecision
39 OpDecorate %6 RelaxedPrecision
40 OpDecorate %7 RelaxedPrecision
41 OpDecorate %8 RelaxedPrecision
42 OpDecorate %9 RelaxedPrecision
43 %10 = OpTypeVoid
44 %11 = OpTypeFunction %10
45 %12 = OpTypeInt 32 1
46 %13 = OpTypePointer Function %12
47 %14 = OpConstant %12 8
48 %15 = OpConstant %12 23
49 %16 = OpTypeBool
50 %17 = OpConstantTrue %16
51 %18 = OpConstant %12 0
52 %19 = OpConstant %12 1
53 %2 = OpFunction %10 None %11
54 %20 = OpLabel
55 %3 = OpVariable %13 Function
56 %4 = OpVariable %13 Function
57 OpStore %3 %14
58 OpStore %4 %15
59 OpBranch %21
60 %21 = OpLabel
61 OpLoopMerge %22 %23 None
62 OpBranch %24
63 %24 = OpLabel
64 %25 = OpPhi %12 %19 %21 %18 %26
65 OpLoopMerge %27 %26 None
66 OpBranch %28
67 %28 = OpLabel
68 %5 = OpLoad %12 %3
69 %29 = OpSGreaterThan %16 %5 %18
70 OpBranchConditional %29 %30 %27
71 %30 = OpLabel
72 %6 = OpLoad %12 %4
73 %7 = OpISub %12 %6 %19
74 OpStore %4 %7
75 OpBranch %26
76 %26 = OpLabel
77 %8 = OpLoad %12 %3
78 %9 = OpISub %12 %8 %19
79 OpStore %3 %9
80 OpBranch %24
81 %27 = OpLabel
82 OpBranch %23
83 %23 = OpLabel
84 OpBranch %21
85 %22 = OpLabel
86 OpBranch %31
87 %31 = OpLabel
88 OpLoopMerge %32 %31 None
89 OpBranchConditional %17 %31 %32
90 %32 = OpLabel
91 OpSelectionMerge %33 None
92 OpBranchConditional %17 %34 %35
93 %34 = OpLabel
94 OpBranch %33
95 %35 = OpLabel
96 OpBranch %33
97 %33 = OpLabel
98 %42 = OpPhi %12 %19 %33 %18 %34 %18 %35
99 OpLoopMerge %36 %33 None
100 OpBranchConditional %17 %36 %33
101 %36 = OpLabel
102 %43 = OpPhi %12 %18 %33 %18 %41
103 OpReturn
104 %37 = OpLabel
105 OpLoopMerge %38 %39 None
106 OpBranch %40
107 %40 = OpLabel
108 OpBranchConditional %17 %41 %38
109 %41 = OpLabel
110 OpBranchConditional %17 %36 %39
111 %39 = OpLabel
112 OpBranch %37
113 %38 = OpLabel
114 OpReturn
115 OpFunctionEnd
116 )";
117
TEST(FuzzerPassOutlineFunctionsTest,EntryIsAlreadySuitable)118 TEST(FuzzerPassOutlineFunctionsTest, EntryIsAlreadySuitable) {
119 const auto env = SPV_ENV_UNIVERSAL_1_5;
120 const auto consumer = nullptr;
121 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
122 spvtools::ValidatorOptions validator_options;
123 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
124 kConsoleMessageConsumer));
125 TransformationContext transformation_context(
126 MakeUnique<FactManager>(context.get()), validator_options);
127 PseudoRandomGenerator prng(0);
128 FuzzerContext fuzzer_context(&prng, 100);
129 protobufs::TransformationSequence transformation_sequence;
130
131 FuzzerPassOutlineFunctions fuzzer_pass(context.get(), &transformation_context,
132 &fuzzer_context,
133 &transformation_sequence);
134
135 // Block 28
136 auto suitable_entry_block =
137 fuzzer_pass.MaybeGetEntryBlockSuitableForOutlining(
138 context->get_instr_block(28));
139
140 ASSERT_TRUE(suitable_entry_block);
141 ASSERT_TRUE(suitable_entry_block->GetLabel()->result_id() == 28);
142
143 // Block 32
144 suitable_entry_block = fuzzer_pass.MaybeGetEntryBlockSuitableForOutlining(
145 context->get_instr_block(32));
146
147 ASSERT_TRUE(suitable_entry_block);
148 ASSERT_TRUE(suitable_entry_block->GetLabel()->result_id() == 32);
149
150 // Block 41
151 suitable_entry_block = fuzzer_pass.MaybeGetEntryBlockSuitableForOutlining(
152 context->get_instr_block(41));
153
154 ASSERT_TRUE(suitable_entry_block);
155 ASSERT_TRUE(suitable_entry_block->GetLabel()->result_id() == 41);
156
157 // The module should not have been changed.
158 ASSERT_TRUE(IsEqual(env, shader, context.get()));
159 }
160
TEST(FuzzerPassOutlineFunctionsTest,EntryHasOpVariable)161 TEST(FuzzerPassOutlineFunctionsTest, EntryHasOpVariable) {
162 const auto env = SPV_ENV_UNIVERSAL_1_5;
163 const auto consumer = nullptr;
164 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
165 spvtools::ValidatorOptions validator_options;
166 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
167 kConsoleMessageConsumer));
168 TransformationContext transformation_context(
169 MakeUnique<FactManager>(context.get()), validator_options);
170 PseudoRandomGenerator prng(0);
171 FuzzerContext fuzzer_context(&prng, 100);
172 protobufs::TransformationSequence transformation_sequence;
173
174 FuzzerPassOutlineFunctions fuzzer_pass(context.get(), &transformation_context,
175 &fuzzer_context,
176 &transformation_sequence);
177
178 // Block 20
179 auto suitable_entry_block =
180 fuzzer_pass.MaybeGetEntryBlockSuitableForOutlining(
181 context->get_instr_block(20));
182
183 // The block should have been split, the new entry block being the block
184 // generated by the splitting.
185 ASSERT_TRUE(suitable_entry_block);
186 ASSERT_TRUE(suitable_entry_block->GetLabel()->result_id() == 100);
187
188 std::string after_adjustment = R"(
189 OpCapability Shader
190 %1 = OpExtInstImport "GLSL.std.450"
191 OpMemoryModel Logical GLSL450
192 OpEntryPoint Fragment %2 "main"
193 OpExecutionMode %2 OriginUpperLeft
194 OpSource ESSL 310
195 OpName %2 "main"
196 OpName %3 "a"
197 OpName %4 "b"
198 OpDecorate %3 RelaxedPrecision
199 OpDecorate %4 RelaxedPrecision
200 OpDecorate %5 RelaxedPrecision
201 OpDecorate %6 RelaxedPrecision
202 OpDecorate %7 RelaxedPrecision
203 OpDecorate %8 RelaxedPrecision
204 OpDecorate %9 RelaxedPrecision
205 %10 = OpTypeVoid
206 %11 = OpTypeFunction %10
207 %12 = OpTypeInt 32 1
208 %13 = OpTypePointer Function %12
209 %14 = OpConstant %12 8
210 %15 = OpConstant %12 23
211 %16 = OpTypeBool
212 %17 = OpConstantTrue %16
213 %18 = OpConstant %12 0
214 %19 = OpConstant %12 1
215 %2 = OpFunction %10 None %11
216 %20 = OpLabel
217 %3 = OpVariable %13 Function
218 %4 = OpVariable %13 Function
219 OpBranch %100
220 %100 = OpLabel
221 OpStore %3 %14
222 OpStore %4 %15
223 OpBranch %21
224 %21 = OpLabel
225 OpLoopMerge %22 %23 None
226 OpBranch %24
227 %24 = OpLabel
228 %25 = OpPhi %12 %19 %21 %18 %26
229 OpLoopMerge %27 %26 None
230 OpBranch %28
231 %28 = OpLabel
232 %5 = OpLoad %12 %3
233 %29 = OpSGreaterThan %16 %5 %18
234 OpBranchConditional %29 %30 %27
235 %30 = OpLabel
236 %6 = OpLoad %12 %4
237 %7 = OpISub %12 %6 %19
238 OpStore %4 %7
239 OpBranch %26
240 %26 = OpLabel
241 %8 = OpLoad %12 %3
242 %9 = OpISub %12 %8 %19
243 OpStore %3 %9
244 OpBranch %24
245 %27 = OpLabel
246 OpBranch %23
247 %23 = OpLabel
248 OpBranch %21
249 %22 = OpLabel
250 OpBranch %31
251 %31 = OpLabel
252 OpLoopMerge %32 %31 None
253 OpBranchConditional %17 %31 %32
254 %32 = OpLabel
255 OpSelectionMerge %33 None
256 OpBranchConditional %17 %34 %35
257 %34 = OpLabel
258 OpBranch %33
259 %35 = OpLabel
260 OpBranch %33
261 %33 = OpLabel
262 %42 = OpPhi %12 %19 %33 %18 %34 %18 %35
263 OpLoopMerge %36 %33 None
264 OpBranchConditional %17 %36 %33
265 %36 = OpLabel
266 %43 = OpPhi %12 %18 %33 %18 %41
267 OpReturn
268 %37 = OpLabel
269 OpLoopMerge %38 %39 None
270 OpBranch %40
271 %40 = OpLabel
272 OpBranchConditional %17 %41 %38
273 %41 = OpLabel
274 OpBranchConditional %17 %36 %39
275 %39 = OpLabel
276 OpBranch %37
277 %38 = OpLabel
278 OpReturn
279 OpFunctionEnd
280 )";
281
282 ASSERT_TRUE(IsEqual(env, after_adjustment, context.get()));
283 }
284
TEST(FuzzerPassOutlineFunctionsTest,EntryBlockIsHeader)285 TEST(FuzzerPassOutlineFunctionsTest, EntryBlockIsHeader) {
286 const auto env = SPV_ENV_UNIVERSAL_1_5;
287 const auto consumer = nullptr;
288 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
289 spvtools::ValidatorOptions validator_options;
290 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
291 kConsoleMessageConsumer));
292 TransformationContext transformation_context(
293 MakeUnique<FactManager>(context.get()), validator_options);
294 PseudoRandomGenerator prng(0);
295 FuzzerContext fuzzer_context(&prng, 100);
296 protobufs::TransformationSequence transformation_sequence;
297
298 FuzzerPassOutlineFunctions fuzzer_pass(context.get(), &transformation_context,
299 &fuzzer_context,
300 &transformation_sequence);
301
302 // Block 21
303 auto suitable_entry_block =
304 fuzzer_pass.MaybeGetEntryBlockSuitableForOutlining(
305 context->get_instr_block(21));
306
307 // A suitable entry block should have been found by finding the preheader
308 // (%20) and then splitting it.
309 ASSERT_TRUE(suitable_entry_block);
310 ASSERT_TRUE(suitable_entry_block->GetLabel()->result_id() == 100);
311
312 // Block 24
313 suitable_entry_block = fuzzer_pass.MaybeGetEntryBlockSuitableForOutlining(
314 context->get_instr_block(24));
315
316 // A preheader should have been created, because the current one is a loop
317 // header.
318 ASSERT_TRUE(suitable_entry_block);
319 ASSERT_TRUE(suitable_entry_block->GetLabel()->result_id() == 101);
320
321 // Block 31
322 suitable_entry_block = fuzzer_pass.MaybeGetEntryBlockSuitableForOutlining(
323 context->get_instr_block(31));
324
325 // An existing suitable entry block should have been found by finding the
326 // preheader (%22), which is already suitable.
327 ASSERT_TRUE(suitable_entry_block);
328 ASSERT_TRUE(suitable_entry_block->GetLabel()->result_id() == 22);
329
330 // Block 33
331 suitable_entry_block = fuzzer_pass.MaybeGetEntryBlockSuitableForOutlining(
332 context->get_instr_block(33));
333
334 // An existing suitable entry block should have been found by creating a new
335 // preheader (there is not one already), and then splitting it (as it contains
336 // OpPhi).
337 ASSERT_TRUE(suitable_entry_block);
338 ASSERT_TRUE(suitable_entry_block->GetLabel()->result_id() == 104);
339
340 // Block 37
341 suitable_entry_block = fuzzer_pass.MaybeGetEntryBlockSuitableForOutlining(
342 context->get_instr_block(37));
343
344 // No suitable entry block can be found for block 37, since it is a loop
345 // header with only one predecessor (the back-edge block).
346 ASSERT_FALSE(suitable_entry_block);
347
348 std::string after_adjustments = R"(
349 OpCapability Shader
350 %1 = OpExtInstImport "GLSL.std.450"
351 OpMemoryModel Logical GLSL450
352 OpEntryPoint Fragment %2 "main"
353 OpExecutionMode %2 OriginUpperLeft
354 OpSource ESSL 310
355 OpName %2 "main"
356 OpName %3 "a"
357 OpName %4 "b"
358 OpDecorate %3 RelaxedPrecision
359 OpDecorate %4 RelaxedPrecision
360 OpDecorate %5 RelaxedPrecision
361 OpDecorate %6 RelaxedPrecision
362 OpDecorate %7 RelaxedPrecision
363 OpDecorate %8 RelaxedPrecision
364 OpDecorate %9 RelaxedPrecision
365 %10 = OpTypeVoid
366 %11 = OpTypeFunction %10
367 %12 = OpTypeInt 32 1
368 %13 = OpTypePointer Function %12
369 %14 = OpConstant %12 8
370 %15 = OpConstant %12 23
371 %16 = OpTypeBool
372 %17 = OpConstantTrue %16
373 %18 = OpConstant %12 0
374 %19 = OpConstant %12 1
375 %2 = OpFunction %10 None %11
376 %20 = OpLabel
377 %3 = OpVariable %13 Function
378 %4 = OpVariable %13 Function
379 OpBranch %100
380 %100 = OpLabel
381 OpStore %3 %14
382 OpStore %4 %15
383 OpBranch %21
384 %21 = OpLabel
385 OpLoopMerge %22 %23 None
386 OpBranch %101
387 %101 = OpLabel
388 OpBranch %24
389 %24 = OpLabel
390 %25 = OpPhi %12 %19 %101 %18 %26
391 OpLoopMerge %27 %26 None
392 OpBranch %28
393 %28 = OpLabel
394 %5 = OpLoad %12 %3
395 %29 = OpSGreaterThan %16 %5 %18
396 OpBranchConditional %29 %30 %27
397 %30 = OpLabel
398 %6 = OpLoad %12 %4
399 %7 = OpISub %12 %6 %19
400 OpStore %4 %7
401 OpBranch %26
402 %26 = OpLabel
403 %8 = OpLoad %12 %3
404 %9 = OpISub %12 %8 %19
405 OpStore %3 %9
406 OpBranch %24
407 %27 = OpLabel
408 OpBranch %23
409 %23 = OpLabel
410 OpBranch %21
411 %22 = OpLabel
412 OpBranch %31
413 %31 = OpLabel
414 OpLoopMerge %32 %31 None
415 OpBranchConditional %17 %31 %32
416 %32 = OpLabel
417 OpSelectionMerge %102 None
418 OpBranchConditional %17 %34 %35
419 %34 = OpLabel
420 OpBranch %102
421 %35 = OpLabel
422 OpBranch %102
423 %102 = OpLabel
424 %103 = OpPhi %12 %18 %34 %18 %35
425 OpBranch %104
426 %104 = OpLabel
427 OpBranch %33
428 %33 = OpLabel
429 %42 = OpPhi %12 %103 %104 %19 %33
430 OpLoopMerge %36 %33 None
431 OpBranchConditional %17 %36 %33
432 %36 = OpLabel
433 %43 = OpPhi %12 %18 %33 %18 %41
434 OpReturn
435 %37 = OpLabel
436 OpLoopMerge %38 %39 None
437 OpBranch %40
438 %40 = OpLabel
439 OpBranchConditional %17 %41 %38
440 %41 = OpLabel
441 OpBranchConditional %17 %36 %39
442 %39 = OpLabel
443 OpBranch %37
444 %38 = OpLabel
445 OpReturn
446 OpFunctionEnd
447 )";
448
449 ASSERT_TRUE(IsEqual(env, after_adjustments, context.get()));
450 }
451
TEST(FuzzerPassOutlineFunctionsTest,ExitBlock)452 TEST(FuzzerPassOutlineFunctionsTest, ExitBlock) {
453 const auto env = SPV_ENV_UNIVERSAL_1_5;
454 const auto consumer = nullptr;
455 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
456 spvtools::ValidatorOptions validator_options;
457 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
458 kConsoleMessageConsumer));
459 TransformationContext transformation_context(
460 MakeUnique<FactManager>(context.get()), validator_options);
461 PseudoRandomGenerator prng(0);
462 FuzzerContext fuzzer_context(&prng, 100);
463 protobufs::TransformationSequence transformation_sequence;
464
465 FuzzerPassOutlineFunctions fuzzer_pass(context.get(), &transformation_context,
466 &fuzzer_context,
467 &transformation_sequence);
468
469 // Block 39 is not a merge block, so it is already suitable.
470 auto suitable_exit_block = fuzzer_pass.MaybeGetExitBlockSuitableForOutlining(
471 context->get_instr_block(39));
472 ASSERT_TRUE(suitable_exit_block);
473 ASSERT_TRUE(suitable_exit_block->GetLabel()->result_id() == 39);
474
475 // The following are merge blocks and, thus, they will need to be split.
476
477 // Block 22
478 suitable_exit_block = fuzzer_pass.MaybeGetExitBlockSuitableForOutlining(
479 context->get_instr_block(22));
480 ASSERT_TRUE(suitable_exit_block);
481 ASSERT_TRUE(suitable_exit_block->GetLabel()->result_id() == 100);
482
483 // Block 27
484 suitable_exit_block = fuzzer_pass.MaybeGetExitBlockSuitableForOutlining(
485 context->get_instr_block(27));
486 ASSERT_TRUE(suitable_exit_block);
487 ASSERT_TRUE(suitable_exit_block->GetLabel()->result_id() == 101);
488
489 // Block 36
490 suitable_exit_block = fuzzer_pass.MaybeGetExitBlockSuitableForOutlining(
491 context->get_instr_block(36));
492 ASSERT_TRUE(suitable_exit_block);
493 ASSERT_TRUE(suitable_exit_block->GetLabel()->result_id() == 102);
494
495 std::string after_adjustments = R"(
496 OpCapability Shader
497 %1 = OpExtInstImport "GLSL.std.450"
498 OpMemoryModel Logical GLSL450
499 OpEntryPoint Fragment %2 "main"
500 OpExecutionMode %2 OriginUpperLeft
501 OpSource ESSL 310
502 OpName %2 "main"
503 OpName %3 "a"
504 OpName %4 "b"
505 OpDecorate %3 RelaxedPrecision
506 OpDecorate %4 RelaxedPrecision
507 OpDecorate %5 RelaxedPrecision
508 OpDecorate %6 RelaxedPrecision
509 OpDecorate %7 RelaxedPrecision
510 OpDecorate %8 RelaxedPrecision
511 OpDecorate %9 RelaxedPrecision
512 %10 = OpTypeVoid
513 %11 = OpTypeFunction %10
514 %12 = OpTypeInt 32 1
515 %13 = OpTypePointer Function %12
516 %14 = OpConstant %12 8
517 %15 = OpConstant %12 23
518 %16 = OpTypeBool
519 %17 = OpConstantTrue %16
520 %18 = OpConstant %12 0
521 %19 = OpConstant %12 1
522 %2 = OpFunction %10 None %11
523 %20 = OpLabel
524 %3 = OpVariable %13 Function
525 %4 = OpVariable %13 Function
526 OpStore %3 %14
527 OpStore %4 %15
528 OpBranch %21
529 %21 = OpLabel
530 OpLoopMerge %22 %23 None
531 OpBranch %24
532 %24 = OpLabel
533 %25 = OpPhi %12 %19 %21 %18 %26
534 OpLoopMerge %27 %26 None
535 OpBranch %28
536 %28 = OpLabel
537 %5 = OpLoad %12 %3
538 %29 = OpSGreaterThan %16 %5 %18
539 OpBranchConditional %29 %30 %27
540 %30 = OpLabel
541 %6 = OpLoad %12 %4
542 %7 = OpISub %12 %6 %19
543 OpStore %4 %7
544 OpBranch %26
545 %26 = OpLabel
546 %8 = OpLoad %12 %3
547 %9 = OpISub %12 %8 %19
548 OpStore %3 %9
549 OpBranch %24
550 %27 = OpLabel
551 OpBranch %101
552 %101 = OpLabel
553 OpBranch %23
554 %23 = OpLabel
555 OpBranch %21
556 %22 = OpLabel
557 OpBranch %100
558 %100 = OpLabel
559 OpBranch %31
560 %31 = OpLabel
561 OpLoopMerge %32 %31 None
562 OpBranchConditional %17 %31 %32
563 %32 = OpLabel
564 OpSelectionMerge %33 None
565 OpBranchConditional %17 %34 %35
566 %34 = OpLabel
567 OpBranch %33
568 %35 = OpLabel
569 OpBranch %33
570 %33 = OpLabel
571 %42 = OpPhi %12 %19 %33 %18 %34 %18 %35
572 OpLoopMerge %36 %33 None
573 OpBranchConditional %17 %36 %33
574 %36 = OpLabel
575 %43 = OpPhi %12 %18 %33 %18 %41
576 OpBranch %102
577 %102 = OpLabel
578 OpReturn
579 %37 = OpLabel
580 OpLoopMerge %38 %39 None
581 OpBranch %40
582 %40 = OpLabel
583 OpBranchConditional %17 %41 %38
584 %41 = OpLabel
585 OpBranchConditional %17 %36 %39
586 %39 = OpLabel
587 OpBranch %37
588 %38 = OpLabel
589 OpReturn
590 OpFunctionEnd
591 )";
592
593 ASSERT_TRUE(IsEqual(env, after_adjustments, context.get()));
594 }
595 } // namespace
596 } // namespace fuzz
597 } // namespace spvtools
598