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/shrinker.h"
16
17#include "gtest/gtest.h"
18#include "source/fuzz/fact_manager/fact_manager.h"
19#include "source/fuzz/fuzzer_context.h"
20#include "source/fuzz/fuzzer_pass_donate_modules.h"
21#include "source/fuzz/fuzzer_util.h"
22#include "source/fuzz/pseudo_random_generator.h"
23#include "source/fuzz/transformation_context.h"
24#include "source/opt/ir_context.h"
25#include "source/util/make_unique.h"
26#include "test/fuzz/fuzz_test_util.h"
27
28namespace spvtools {
29namespace fuzz {
30namespace {
31
32TEST(ShrinkerTest, ReduceAddedFunctions) {
33  const std::string kReferenceModule = R"(
34               OpCapability Shader
35          %1 = OpExtInstImport "GLSL.std.450"
36               OpMemoryModel Logical GLSL450
37               OpEntryPoint Fragment %4 "main"
38               OpExecutionMode %4 OriginUpperLeft
39               OpSource ESSL 320
40          %2 = OpTypeVoid
41          %3 = OpTypeFunction %2
42          %6 = OpTypeInt 32 1
43          %7 = OpTypePointer Private %6
44          %8 = OpVariable %7 Private
45          %9 = OpConstant %6 2
46         %10 = OpTypePointer Function %6
47          %4 = OpFunction %2 None %3
48          %5 = OpLabel
49         %11 = OpVariable %10 Function
50               OpStore %8 %9
51         %12 = OpLoad %6 %8
52               OpStore %11 %12
53               OpReturn
54               OpFunctionEnd
55  )";
56
57  const std::string kDonorModule = R"(
58               OpCapability Shader
59          %1 = OpExtInstImport "GLSL.std.450"
60               OpMemoryModel Logical GLSL450
61               OpEntryPoint Fragment %4 "main"
62               OpExecutionMode %4 OriginUpperLeft
63               OpSource ESSL 320
64          %2 = OpTypeVoid
65          %3 = OpTypeFunction %2
66          %6 = OpTypeInt 32 1
67          %7 = OpTypePointer Function %6
68          %8 = OpTypeFunction %6 %7
69         %12 = OpTypeFunction %2 %7
70         %17 = OpConstant %6 0
71         %26 = OpTypeBool
72         %32 = OpConstant %6 1
73         %46 = OpTypePointer Private %6
74         %47 = OpVariable %46 Private
75         %48 = OpConstant %6 3
76          %4 = OpFunction %2 None %3
77          %5 = OpLabel
78         %49 = OpVariable %7 Function
79         %50 = OpVariable %7 Function
80         %51 = OpLoad %6 %49
81               OpStore %50 %51
82         %52 = OpFunctionCall %2 %14 %50
83               OpReturn
84               OpFunctionEnd
85         %10 = OpFunction %6 None %8
86          %9 = OpFunctionParameter %7
87         %11 = OpLabel
88         %16 = OpVariable %7 Function
89         %18 = OpVariable %7 Function
90               OpStore %16 %17
91               OpStore %18 %17
92               OpBranch %19
93         %19 = OpLabel
94               OpLoopMerge %21 %22 None
95               OpBranch %23
96         %23 = OpLabel
97         %24 = OpLoad %6 %18
98         %25 = OpLoad %6 %9
99         %27 = OpSLessThan %26 %24 %25
100               OpBranchConditional %27 %20 %21
101         %20 = OpLabel
102         %28 = OpLoad %6 %9
103         %29 = OpLoad %6 %16
104         %30 = OpIAdd %6 %29 %28
105               OpStore %16 %30
106               OpBranch %22
107         %22 = OpLabel
108         %31 = OpLoad %6 %18
109         %33 = OpIAdd %6 %31 %32
110               OpStore %18 %33
111               OpBranch %19
112         %21 = OpLabel
113         %34 = OpLoad %6 %16
114         %35 = OpNot %6 %34
115               OpReturnValue %35
116               OpFunctionEnd
117         %14 = OpFunction %2 None %12
118         %13 = OpFunctionParameter %7
119         %15 = OpLabel
120         %37 = OpVariable %7 Function
121         %38 = OpVariable %7 Function
122         %39 = OpLoad %6 %13
123               OpStore %38 %39
124         %40 = OpFunctionCall %6 %10 %38
125               OpStore %37 %40
126         %41 = OpLoad %6 %37
127         %42 = OpLoad %6 %13
128         %43 = OpSGreaterThan %26 %41 %42
129               OpSelectionMerge %45 None
130               OpBranchConditional %43 %44 %45
131         %44 = OpLabel
132               OpStore %47 %48
133               OpBranch %45
134         %45 = OpLabel
135               OpReturn
136               OpFunctionEnd
137  )";
138
139  // Note: |env| should ideally be declared const.  However, due to a known
140  // issue with older versions of MSVC we would have to mark |env| as being
141  // captured due to its used in a lambda below, and other compilers would warn
142  // that such capturing is not necessary.  Not declaring |env| as const means
143  // that it needs to be captured to be used in the lambda, and thus all
144  // compilers are kept happy.  See:
145  // https://developercommunity.visualstudio.com/content/problem/367326/problems-with-capturing-constexpr-in-lambda.html
146  spv_target_env env = SPV_ENV_UNIVERSAL_1_3;
147  const auto consumer = fuzzerutil::kSilentMessageConsumer;
148
149  SpirvTools tools(env);
150  std::vector<uint32_t> reference_binary;
151  ASSERT_TRUE(
152      tools.Assemble(kReferenceModule, &reference_binary, kFuzzAssembleOption));
153
154  spvtools::ValidatorOptions validator_options;
155
156  const auto variant_ir_context =
157      BuildModule(env, consumer, kReferenceModule, kFuzzAssembleOption);
158  ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(
159      variant_ir_context.get(), validator_options, kConsoleMessageConsumer));
160
161  const auto donor_ir_context =
162      BuildModule(env, consumer, kDonorModule, kFuzzAssembleOption);
163  ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(
164      donor_ir_context.get(), validator_options, kConsoleMessageConsumer));
165
166  FuzzerContext fuzzer_context(MakeUnique<PseudoRandomGenerator>(0), 100,
167                               false);
168  TransformationContext transformation_context(
169      MakeUnique<FactManager>(variant_ir_context.get()), validator_options);
170
171  protobufs::TransformationSequence transformations;
172  FuzzerPassDonateModules pass(variant_ir_context.get(),
173                               &transformation_context, &fuzzer_context,
174                               &transformations, false, {});
175  pass.DonateSingleModule(donor_ir_context.get(), true);
176
177  protobufs::FactSequence no_facts;
178
179  Shrinker::InterestingnessFunction interestingness_function =
180      [consumer, env](const std::vector<uint32_t>& binary,
181                      uint32_t /*unused*/) -> bool {
182    bool found_op_not = false;
183    uint32_t op_call_count = 0;
184    auto temp_ir_context =
185        BuildModule(env, consumer, binary.data(), binary.size());
186    for (auto& function : *temp_ir_context->module()) {
187      for (auto& block : function) {
188        for (auto& inst : block) {
189          if (inst.opcode() == spv::Op::OpNot) {
190            found_op_not = true;
191          } else if (inst.opcode() == spv::Op::OpFunctionCall) {
192            op_call_count++;
193          }
194        }
195      }
196    }
197    return found_op_not && op_call_count >= 2;
198  };
199
200  auto shrinker_result =
201      Shrinker(env, consumer, reference_binary, no_facts, transformations,
202               interestingness_function, 1000, true, validator_options)
203          .Run();
204  ASSERT_EQ(Shrinker::ShrinkerResultStatus::kComplete, shrinker_result.status);
205
206  // We now check that the module after shrinking looks right.
207  // The entry point should be identical to what it looked like in the
208  // reference, while the other functions should be absolutely minimal,
209  // containing only what is needed to satisfy the interestingness function.
210  auto ir_context_after_shrinking =
211      BuildModule(env, consumer, shrinker_result.transformed_binary.data(),
212                  shrinker_result.transformed_binary.size());
213  bool first_function = true;
214  for (auto& function : *ir_context_after_shrinking->module()) {
215    if (first_function) {
216      first_function = false;
217      bool first_block = true;
218      for (auto& block : function) {
219        ASSERT_TRUE(first_block);
220        uint32_t counter = 0;
221        for (auto& inst : block) {
222          switch (counter) {
223            case 0:
224              ASSERT_EQ(spv::Op::OpVariable, inst.opcode());
225              ASSERT_EQ(11, inst.result_id());
226              break;
227            case 1:
228              ASSERT_EQ(spv::Op::OpStore, inst.opcode());
229              break;
230            case 2:
231              ASSERT_EQ(spv::Op::OpLoad, inst.opcode());
232              ASSERT_EQ(12, inst.result_id());
233              break;
234            case 3:
235              ASSERT_EQ(spv::Op::OpStore, inst.opcode());
236              break;
237            case 4:
238              ASSERT_EQ(spv::Op::OpReturn, inst.opcode());
239              break;
240            default:
241              FAIL();
242          }
243          counter++;
244        }
245      }
246    } else {
247      bool first_block = true;
248      for (auto& block : function) {
249        ASSERT_TRUE(first_block);
250        first_block = false;
251        for (auto& inst : block) {
252          switch (inst.opcode()) {
253            case spv::Op::OpVariable:
254            case spv::Op::OpNot:
255            case spv::Op::OpReturn:
256            case spv::Op::OpReturnValue:
257            case spv::Op::OpFunctionCall:
258              // These are the only instructions we expect to see.
259              break;
260            default:
261              FAIL();
262          }
263        }
264      }
265    }
266  }
267}
268
269TEST(ShrinkerTest, HitStepLimitWhenReducingAddedFunctions) {
270  const std::string kReferenceModule = R"(
271               OpCapability Shader
272          %1 = OpExtInstImport "GLSL.std.450"
273               OpMemoryModel Logical GLSL450
274               OpEntryPoint Fragment %4 "main"
275               OpExecutionMode %4 OriginUpperLeft
276               OpSource ESSL 320
277          %2 = OpTypeVoid
278          %3 = OpTypeFunction %2
279          %6 = OpTypeInt 32 1
280          %7 = OpTypePointer Private %6
281          %8 = OpVariable %7 Private
282          %9 = OpConstant %6 2
283         %10 = OpTypePointer Function %6
284          %4 = OpFunction %2 None %3
285          %5 = OpLabel
286         %11 = OpVariable %10 Function
287               OpStore %8 %9
288         %12 = OpLoad %6 %8
289               OpStore %11 %12
290               OpReturn
291               OpFunctionEnd
292  )";
293
294  const std::string kDonorModule = R"(
295               OpCapability Shader
296          %1 = OpExtInstImport "GLSL.std.450"
297               OpMemoryModel Logical GLSL450
298               OpEntryPoint Fragment %4 "main"
299               OpExecutionMode %4 OriginUpperLeft
300               OpSource ESSL 320
301          %2 = OpTypeVoid
302          %3 = OpTypeFunction %2
303          %6 = OpTypeInt 32 1
304         %48 = OpConstant %6 3
305          %4 = OpFunction %2 None %3
306          %5 = OpLabel
307         %52 = OpCopyObject %6 %48
308         %53 = OpCopyObject %6 %52
309         %54 = OpCopyObject %6 %53
310         %55 = OpCopyObject %6 %54
311         %56 = OpCopyObject %6 %55
312         %57 = OpCopyObject %6 %56
313         %58 = OpCopyObject %6 %48
314         %59 = OpCopyObject %6 %58
315         %60 = OpCopyObject %6 %59
316         %61 = OpCopyObject %6 %60
317         %62 = OpCopyObject %6 %61
318         %63 = OpCopyObject %6 %62
319         %64 = OpCopyObject %6 %48
320               OpReturn
321               OpFunctionEnd
322  )";
323
324  spv_target_env env = SPV_ENV_UNIVERSAL_1_3;
325  const auto consumer = fuzzerutil::kSilentMessageConsumer;
326
327  SpirvTools tools(env);
328  std::vector<uint32_t> reference_binary;
329  ASSERT_TRUE(
330      tools.Assemble(kReferenceModule, &reference_binary, kFuzzAssembleOption));
331
332  spvtools::ValidatorOptions validator_options;
333
334  const auto variant_ir_context =
335      BuildModule(env, consumer, kReferenceModule, kFuzzAssembleOption);
336  ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(
337      variant_ir_context.get(), validator_options, kConsoleMessageConsumer));
338
339  const auto donor_ir_context =
340      BuildModule(env, consumer, kDonorModule, kFuzzAssembleOption);
341  ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(
342      donor_ir_context.get(), validator_options, kConsoleMessageConsumer));
343
344  FuzzerContext fuzzer_context(MakeUnique<PseudoRandomGenerator>(0), 100,
345                               false);
346  TransformationContext transformation_context(
347      MakeUnique<FactManager>(variant_ir_context.get()), validator_options);
348
349  protobufs::TransformationSequence transformations;
350  FuzzerPassDonateModules pass(variant_ir_context.get(),
351                               &transformation_context, &fuzzer_context,
352                               &transformations, false, {});
353  pass.DonateSingleModule(donor_ir_context.get(), true);
354
355  protobufs::FactSequence no_facts;
356
357  Shrinker::InterestingnessFunction interestingness_function =
358      [consumer, env](const std::vector<uint32_t>& binary,
359                      uint32_t /*unused*/) -> bool {
360    auto temp_ir_context =
361        BuildModule(env, consumer, binary.data(), binary.size());
362    uint32_t copy_object_count = 0;
363    temp_ir_context->module()->ForEachInst(
364        [&copy_object_count](opt::Instruction* inst) {
365          if (inst->opcode() == spv::Op::OpCopyObject) {
366            copy_object_count++;
367          }
368        });
369    return copy_object_count >= 8;
370  };
371
372  auto shrinker_result =
373      Shrinker(env, consumer, reference_binary, no_facts, transformations,
374               interestingness_function, 30, true, validator_options)
375          .Run();
376  ASSERT_EQ(Shrinker::ShrinkerResultStatus::kStepLimitReached,
377            shrinker_result.status);
378}
379
380}  // namespace
381}  // namespace fuzz
382}  // namespace spvtools
383