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
28 namespace spvtools {
29 namespace fuzz {
30 namespace {
31
TEST(ShrinkerTest,ReduceAddedFunctions)32 TEST(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() == SpvOpNot) {
190 found_op_not = true;
191 } else if (inst.opcode() == SpvOpFunctionCall) {
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(SpvOpVariable, inst.opcode());
225 ASSERT_EQ(11, inst.result_id());
226 break;
227 case 1:
228 ASSERT_EQ(SpvOpStore, inst.opcode());
229 break;
230 case 2:
231 ASSERT_EQ(SpvOpLoad, inst.opcode());
232 ASSERT_EQ(12, inst.result_id());
233 break;
234 case 3:
235 ASSERT_EQ(SpvOpStore, inst.opcode());
236 break;
237 case 4:
238 ASSERT_EQ(SpvOpReturn, 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 SpvOpVariable:
254 case SpvOpNot:
255 case SpvOpReturn:
256 case SpvOpReturnValue:
257 case SpvOpFunctionCall:
258 // These are the only instructions we expect to see.
259 break;
260 default:
261 FAIL();
262 }
263 }
264 }
265 }
266 }
267 }
268
TEST(ShrinkerTest,HitStepLimitWhenReducingAddedFunctions)269 TEST(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 [©_object_count](opt::Instruction* inst) {
365 if (inst->opcode() == SpvOpCopyObject) {
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