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
22namespace spvtools {
23namespace fuzz {
24namespace {
25
26std::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
118TEST(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  FuzzerContext fuzzer_context(MakeUnique<PseudoRandomGenerator>(0), 100,
128                               false);
129  protobufs::TransformationSequence transformation_sequence;
130
131  FuzzerPassOutlineFunctions fuzzer_pass(context.get(), &transformation_context,
132                                         &fuzzer_context,
133                                         &transformation_sequence, false);
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
161TEST(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  FuzzerContext fuzzer_context(MakeUnique<PseudoRandomGenerator>(0), 100,
171                               false);
172  protobufs::TransformationSequence transformation_sequence;
173
174  FuzzerPassOutlineFunctions fuzzer_pass(context.get(), &transformation_context,
175                                         &fuzzer_context,
176                                         &transformation_sequence, false);
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
285TEST(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  FuzzerContext fuzzer_context(MakeUnique<PseudoRandomGenerator>(0), 100,
295                               false);
296  protobufs::TransformationSequence transformation_sequence;
297
298  FuzzerPassOutlineFunctions fuzzer_pass(context.get(), &transformation_context,
299                                         &fuzzer_context,
300                                         &transformation_sequence, false);
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
452TEST(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  FuzzerContext fuzzer_context(MakeUnique<PseudoRandomGenerator>(0), 100,
462                               false);
463  protobufs::TransformationSequence transformation_sequence;
464
465  FuzzerPassOutlineFunctions fuzzer_pass(context.get(), &transformation_context,
466                                         &fuzzer_context,
467                                         &transformation_sequence, false);
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