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_add_dead_block.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(TransformationAddDeadBlockTest,BasicTest)25 TEST(TransformationAddDeadBlockTest, BasicTest) {
26 std::string reference_shader = R"(
27 OpCapability Shader
28 %1 = OpExtInstImport "GLSL.std.450"
29 OpMemoryModel Logical GLSL450
30 OpEntryPoint Fragment %6 "main"
31 OpExecutionMode %6 OriginUpperLeft
32
33 ; Types
34 %2 = OpTypeBool
35 %3 = OpTypeVoid
36 %4 = OpTypeFunction %3
37
38 ; Constants
39 %5 = OpConstantTrue %2
40
41 ; main function
42 %6 = OpFunction %3 None %4
43 %7 = OpLabel
44 OpSelectionMerge %11 None
45 OpBranchConditional %5 %8 %9
46 %8 = OpLabel
47 OpBranch %10
48 %9 = OpLabel
49 OpBranch %10
50 %10 = OpLabel
51 OpBranch %11
52 %11 = OpLabel
53 OpBranch %13
54 %12 = OpLabel
55 OpBranch %13
56 %13 = OpLabel
57 OpReturn
58 OpFunctionEnd
59 )";
60
61 const auto env = SPV_ENV_UNIVERSAL_1_4;
62 const auto consumer = nullptr;
63 const auto context =
64 BuildModule(env, consumer, reference_shader, kFuzzAssembleOption);
65 spvtools::ValidatorOptions validator_options;
66 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
67 kConsoleMessageConsumer));
68 TransformationContext transformation_context(
69 MakeUnique<FactManager>(context.get()), validator_options);
70 // Id 4 is already in use
71 auto transformation = TransformationAddDeadBlock(4, 11, true);
72 ASSERT_FALSE(
73 transformation.IsApplicable(context.get(), transformation_context));
74
75 // Id 5 is not a block
76 transformation = TransformationAddDeadBlock(14, 5, true);
77 ASSERT_FALSE(
78 transformation.IsApplicable(context.get(), transformation_context));
79
80 // Tests existing block not dominating its successor block.
81 transformation = TransformationAddDeadBlock(14, 8, true);
82 ASSERT_FALSE(
83 transformation.IsApplicable(context.get(), transformation_context));
84
85 transformation = TransformationAddDeadBlock(14, 9, true);
86 ASSERT_FALSE(
87 transformation.IsApplicable(context.get(), transformation_context));
88
89 // Tests existing block being an unreachable block.
90 transformation = TransformationAddDeadBlock(14, 12, true);
91 ASSERT_FALSE(
92 transformation.IsApplicable(context.get(), transformation_context));
93
94 // Tests applicable case.
95 transformation = TransformationAddDeadBlock(14, 11, true);
96 ASSERT_TRUE(
97 transformation.IsApplicable(context.get(), transformation_context));
98 ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
99
100 ASSERT_TRUE(transformation_context.GetFactManager()->BlockIsDead(14));
101
102 std::string variant_shader = R"(
103 OpCapability Shader
104 %1 = OpExtInstImport "GLSL.std.450"
105 OpMemoryModel Logical GLSL450
106 OpEntryPoint Fragment %6 "main"
107 OpExecutionMode %6 OriginUpperLeft
108
109 ; Types
110 %2 = OpTypeBool
111 %3 = OpTypeVoid
112 %4 = OpTypeFunction %3
113
114 ; Constants
115 %5 = OpConstantTrue %2
116
117 ; main function
118 %6 = OpFunction %3 None %4
119 %7 = OpLabel
120 OpSelectionMerge %11 None
121 OpBranchConditional %5 %8 %9
122 %8 = OpLabel
123 OpBranch %10
124 %9 = OpLabel
125 OpBranch %10
126 %10 = OpLabel
127 OpBranch %11
128 %11 = OpLabel
129 OpSelectionMerge %13 None
130 OpBranchConditional %5 %13 %14
131 %14 = OpLabel
132 OpBranch %13
133 %12 = OpLabel
134 OpBranch %13
135 %13 = OpLabel
136 OpReturn
137 OpFunctionEnd
138 )";
139
140 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
141 kConsoleMessageConsumer));
142 ASSERT_TRUE(IsEqual(env, variant_shader, context.get()));
143 }
144
TEST(TransformationAddDeadBlockTest,ApplicableWithFalseCondition)145 TEST(TransformationAddDeadBlockTest, ApplicableWithFalseCondition) {
146 std::string reference_shader = R"(
147 OpCapability Shader
148 %1 = OpExtInstImport "GLSL.std.450"
149 OpMemoryModel Logical GLSL450
150 OpEntryPoint Fragment %6 "main"
151 OpExecutionMode %6 OriginUpperLeft
152
153 ; Types
154 %2 = OpTypeBool
155 %3 = OpTypeVoid
156 %4 = OpTypeFunction %3
157
158 ; Constants
159 %5 = OpConstantFalse %2
160
161 ; main function
162 %6 = OpFunction %3 None %4
163 %7 = OpLabel
164 OpSelectionMerge %11 None
165 OpBranchConditional %5 %8 %9
166 %8 = OpLabel
167 OpBranch %10
168 %9 = OpLabel
169 OpBranch %10
170 %10 = OpLabel
171 OpBranch %11
172 %11 = OpLabel
173 OpBranch %13
174 %12 = OpLabel
175 OpBranch %13
176 %13 = OpLabel
177 OpReturn
178 OpFunctionEnd
179 )";
180 const auto env = SPV_ENV_UNIVERSAL_1_4;
181 const auto consumer = nullptr;
182 const auto context =
183 BuildModule(env, consumer, reference_shader, kFuzzAssembleOption);
184 spvtools::ValidatorOptions validator_options;
185 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
186 kConsoleMessageConsumer));
187 TransformationContext transformation_context(
188 MakeUnique<FactManager>(context.get()), validator_options);
189 auto transformation = TransformationAddDeadBlock(14, 11, false);
190
191 ASSERT_TRUE(
192 transformation.IsApplicable(context.get(), transformation_context));
193 ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
194
195 std::string variant_shader = R"(
196 OpCapability Shader
197 %1 = OpExtInstImport "GLSL.std.450"
198 OpMemoryModel Logical GLSL450
199 OpEntryPoint Fragment %6 "main"
200 OpExecutionMode %6 OriginUpperLeft
201
202 ; Types
203 %2 = OpTypeBool
204 %3 = OpTypeVoid
205 %4 = OpTypeFunction %3
206
207 ; Constants
208 %5 = OpConstantFalse %2
209
210 ; main function
211 %6 = OpFunction %3 None %4
212 %7 = OpLabel
213 OpSelectionMerge %11 None
214 OpBranchConditional %5 %8 %9
215 %8 = OpLabel
216 OpBranch %10
217 %9 = OpLabel
218 OpBranch %10
219 %10 = OpLabel
220 OpBranch %11
221 %11 = OpLabel
222 OpSelectionMerge %13 None
223 OpBranchConditional %5 %14 %13
224 %14 = OpLabel
225 OpBranch %13
226 %12 = OpLabel
227 OpBranch %13
228 %13 = OpLabel
229 OpReturn
230 OpFunctionEnd
231 )";
232
233 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
234 kConsoleMessageConsumer));
235 ASSERT_TRUE(IsEqual(env, variant_shader, context.get()));
236 }
237
TEST(TransformationAddDeadBlockTest,TargetBlockMustNotBeSelectionMerge)238 TEST(TransformationAddDeadBlockTest, TargetBlockMustNotBeSelectionMerge) {
239 std::string shader = R"(
240 OpCapability Shader
241 %1 = OpExtInstImport "GLSL.std.450"
242 OpMemoryModel Logical GLSL450
243 OpEntryPoint Fragment %4 "main"
244 OpExecutionMode %4 OriginUpperLeft
245 OpSource ESSL 310
246 OpName %4 "main"
247 %2 = OpTypeVoid
248 %3 = OpTypeFunction %2
249 %6 = OpTypeBool
250 %7 = OpConstantTrue %6
251 %4 = OpFunction %2 None %3
252 %5 = OpLabel
253 OpSelectionMerge %10 None
254 OpBranchConditional %7 %8 %9
255 %8 = OpLabel
256 OpBranch %10
257 %9 = OpLabel
258 OpBranch %10
259 %10 = OpLabel
260 OpReturn
261 OpFunctionEnd
262 )";
263
264 const auto env = SPV_ENV_UNIVERSAL_1_4;
265 const auto consumer = nullptr;
266 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
267 spvtools::ValidatorOptions validator_options;
268 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
269 kConsoleMessageConsumer));
270 TransformationContext transformation_context(
271 MakeUnique<FactManager>(context.get()), validator_options);
272 ASSERT_FALSE(TransformationAddDeadBlock(100, 9, true)
273 .IsApplicable(context.get(), transformation_context));
274 }
275
TEST(TransformationAddDeadBlockTest,TargetBlockMustNotBeLoopMergeOrContinue)276 TEST(TransformationAddDeadBlockTest, TargetBlockMustNotBeLoopMergeOrContinue) {
277 std::string shader = R"(
278 OpCapability Shader
279 %1 = OpExtInstImport "GLSL.std.450"
280 OpMemoryModel Logical GLSL450
281 OpEntryPoint Fragment %6 "main"
282 OpExecutionMode %6 OriginUpperLeft
283
284 ; Types
285 %2 = OpTypeBool
286 %3 = OpTypeVoid
287 %4 = OpTypeFunction %3
288
289 ; Constants
290 %5 = OpConstantTrue %2
291
292 ; main function
293 %6 = OpFunction %3 None %4
294 %7 = OpLabel
295 OpBranch %8
296 %8 = OpLabel
297 OpLoopMerge %12 %11 None
298 OpBranchConditional %5 %9 %10
299 %9 = OpLabel
300 OpBranch %11
301 %10 = OpLabel
302 OpBranch %12
303 %11 = OpLabel
304 OpBranch %8
305 %12 = OpLabel
306 OpReturn
307 OpFunctionEnd
308 )";
309
310 const auto env = SPV_ENV_UNIVERSAL_1_4;
311 const auto consumer = nullptr;
312 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
313 spvtools::ValidatorOptions validator_options;
314 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
315 kConsoleMessageConsumer));
316 TransformationContext transformation_context(
317 MakeUnique<FactManager>(context.get()), validator_options);
318 // Bad because 9's successor is the loop continue target.
319 ASSERT_FALSE(TransformationAddDeadBlock(100, 9, true)
320 .IsApplicable(context.get(), transformation_context));
321 // Bad because 10's successor is the loop merge.
322 ASSERT_FALSE(TransformationAddDeadBlock(100, 10, true)
323 .IsApplicable(context.get(), transformation_context));
324 }
325
TEST(TransformationAddDeadBlockTest,SourceBlockMustNotBeLoopHead)326 TEST(TransformationAddDeadBlockTest, SourceBlockMustNotBeLoopHead) {
327 std::string shader = R"(
328 OpCapability Shader
329 %1 = OpExtInstImport "GLSL.std.450"
330 OpMemoryModel Logical GLSL450
331 OpEntryPoint Fragment %4 "main"
332 OpExecutionMode %4 OriginUpperLeft
333 OpSource ESSL 310
334 OpName %4 "main"
335 %2 = OpTypeVoid
336 %3 = OpTypeFunction %2
337 %6 = OpTypeBool
338 %7 = OpConstantTrue %6
339 %4 = OpFunction %2 None %3
340 %5 = OpLabel
341 OpBranch %8
342 %8 = OpLabel
343 OpLoopMerge %11 %12 None
344 OpBranch %9
345 %9 = OpLabel
346 OpBranchConditional %7 %11 %12
347 %12 = OpLabel
348 OpBranch %8
349 %11 = OpLabel
350 OpReturn
351 OpFunctionEnd
352 )";
353
354 const auto env = SPV_ENV_UNIVERSAL_1_4;
355 const auto consumer = nullptr;
356 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
357 spvtools::ValidatorOptions validator_options;
358 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
359 kConsoleMessageConsumer));
360 TransformationContext transformation_context(
361 MakeUnique<FactManager>(context.get()), validator_options);
362 // Bad because 8 is a loop head.
363 ASSERT_FALSE(TransformationAddDeadBlock(100, 8, true)
364 .IsApplicable(context.get(), transformation_context));
365 }
366
TEST(TransformationAddDeadBlockTest,OpPhiInTarget)367 TEST(TransformationAddDeadBlockTest, OpPhiInTarget) {
368 std::string shader = R"(
369 OpCapability Shader
370 %1 = OpExtInstImport "GLSL.std.450"
371 OpMemoryModel Logical GLSL450
372 OpEntryPoint Fragment %4 "main"
373 OpExecutionMode %4 OriginUpperLeft
374 OpSource ESSL 310
375 OpName %4 "main"
376 %2 = OpTypeVoid
377 %3 = OpTypeFunction %2
378 %6 = OpTypeBool
379 %7 = OpConstantTrue %6
380 %9 = OpTypeInt 32 0
381 %10 = OpConstant %9 1
382 %4 = OpFunction %2 None %3
383 %5 = OpLabel
384 OpBranch %8
385 %8 = OpLabel
386 %12 = OpPhi %6 %7 %5
387 %13 = OpPhi %9 %10 %5
388 OpReturn
389 OpFunctionEnd
390 )";
391
392 const auto env = SPV_ENV_UNIVERSAL_1_4;
393 const auto consumer = nullptr;
394 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
395 spvtools::ValidatorOptions validator_options;
396 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
397 kConsoleMessageConsumer));
398 TransformationContext transformation_context(
399 MakeUnique<FactManager>(context.get()), validator_options);
400 TransformationAddDeadBlock transformation(100, 5, true);
401 ASSERT_TRUE(
402 transformation.IsApplicable(context.get(), transformation_context));
403 ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
404 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
405 kConsoleMessageConsumer));
406
407 ASSERT_TRUE(transformation_context.GetFactManager()->BlockIsDead(100));
408
409 std::string after_transformation = R"(
410 OpCapability Shader
411 %1 = OpExtInstImport "GLSL.std.450"
412 OpMemoryModel Logical GLSL450
413 OpEntryPoint Fragment %4 "main"
414 OpExecutionMode %4 OriginUpperLeft
415 OpSource ESSL 310
416 OpName %4 "main"
417 %2 = OpTypeVoid
418 %3 = OpTypeFunction %2
419 %6 = OpTypeBool
420 %7 = OpConstantTrue %6
421 %9 = OpTypeInt 32 0
422 %10 = OpConstant %9 1
423 %4 = OpFunction %2 None %3
424 %5 = OpLabel
425 OpSelectionMerge %8 None
426 OpBranchConditional %7 %8 %100
427 %100 = OpLabel
428 OpBranch %8
429 %8 = OpLabel
430 %12 = OpPhi %6 %7 %5 %7 %100
431 %13 = OpPhi %9 %10 %5 %10 %100
432 OpReturn
433 OpFunctionEnd
434 )";
435 ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
436 }
437
TEST(TransformationAddDeadBlockTest,BackEdge)438 TEST(TransformationAddDeadBlockTest, BackEdge) {
439 std::string shader = R"(
440 OpCapability Shader
441 %1 = OpExtInstImport "GLSL.std.450"
442 OpMemoryModel Logical GLSL450
443 OpEntryPoint Fragment %4 "main"
444 OpExecutionMode %4 OriginUpperLeft
445 OpSource ESSL 310
446 OpName %4 "main"
447 %2 = OpTypeVoid
448 %3 = OpTypeFunction %2
449 %6 = OpTypeBool
450 %7 = OpConstantTrue %6
451 %4 = OpFunction %2 None %3
452 %5 = OpLabel
453 OpBranch %8
454 %8 = OpLabel
455 OpLoopMerge %10 %9 None
456 OpBranchConditional %7 %9 %10
457 %9 = OpLabel
458 OpBranch %8
459 %10 = OpLabel
460 OpReturn
461 OpFunctionEnd
462 )";
463
464 const auto env = SPV_ENV_UNIVERSAL_1_4;
465 const auto consumer = nullptr;
466 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
467 spvtools::ValidatorOptions validator_options;
468 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
469 kConsoleMessageConsumer));
470 TransformationContext transformation_context(
471 MakeUnique<FactManager>(context.get()), validator_options);
472 // 9 is a back edge block, so it would not be OK to add a dead block here,
473 // as then both 9 and the dead block would branch to the loop header, 8.
474 ASSERT_FALSE(TransformationAddDeadBlock(100, 9, true)
475 .IsApplicable(context.get(), transformation_context));
476 }
477
478 } // namespace
479 } // namespace fuzz
480 } // namespace spvtools
481