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 OpBranch %13
299 %13 = OpLabel
300 OpSelectionMerge %14 None
301 OpBranchConditional %5 %9 %10
302 %9 = OpLabel
303 OpBranch %11
304 %10 = OpLabel
305 OpBranch %12
306 %14 = OpLabel
307 OpUnreachable
308 %11 = OpLabel
309 OpBranch %8
310 %12 = OpLabel
311 OpReturn
312 OpFunctionEnd
313 )";
314
315 const auto env = SPV_ENV_UNIVERSAL_1_4;
316 const auto consumer = nullptr;
317 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
318 spvtools::ValidatorOptions validator_options;
319 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
320 kConsoleMessageConsumer));
321 TransformationContext transformation_context(
322 MakeUnique<FactManager>(context.get()), validator_options);
323 // Bad because 9's successor is the loop continue target.
324 ASSERT_FALSE(TransformationAddDeadBlock(100, 9, true)
325 .IsApplicable(context.get(), transformation_context));
326 // Bad because 10's successor is the loop merge.
327 ASSERT_FALSE(TransformationAddDeadBlock(100, 10, true)
328 .IsApplicable(context.get(), transformation_context));
329 }
330
TEST(TransformationAddDeadBlockTest, SourceBlockMustNotBeLoopHead)331 TEST(TransformationAddDeadBlockTest, SourceBlockMustNotBeLoopHead) {
332 std::string shader = R"(
333 OpCapability Shader
334 %1 = OpExtInstImport "GLSL.std.450"
335 OpMemoryModel Logical GLSL450
336 OpEntryPoint Fragment %4 "main"
337 OpExecutionMode %4 OriginUpperLeft
338 OpSource ESSL 310
339 OpName %4 "main"
340 %2 = OpTypeVoid
341 %3 = OpTypeFunction %2
342 %6 = OpTypeBool
343 %7 = OpConstantTrue %6
344 %4 = OpFunction %2 None %3
345 %5 = OpLabel
346 OpBranch %8
347 %8 = OpLabel
348 OpLoopMerge %11 %12 None
349 OpBranch %9
350 %9 = OpLabel
351 OpBranchConditional %7 %11 %12
352 %12 = OpLabel
353 OpBranch %8
354 %11 = OpLabel
355 OpReturn
356 OpFunctionEnd
357 )";
358
359 const auto env = SPV_ENV_UNIVERSAL_1_4;
360 const auto consumer = nullptr;
361 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
362 spvtools::ValidatorOptions validator_options;
363 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
364 kConsoleMessageConsumer));
365 TransformationContext transformation_context(
366 MakeUnique<FactManager>(context.get()), validator_options);
367 // Bad because 8 is a loop head.
368 ASSERT_FALSE(TransformationAddDeadBlock(100, 8, true)
369 .IsApplicable(context.get(), transformation_context));
370 }
371
TEST(TransformationAddDeadBlockTest, OpPhiInTarget)372 TEST(TransformationAddDeadBlockTest, OpPhiInTarget) {
373 std::string shader = R"(
374 OpCapability Shader
375 %1 = OpExtInstImport "GLSL.std.450"
376 OpMemoryModel Logical GLSL450
377 OpEntryPoint Fragment %4 "main"
378 OpExecutionMode %4 OriginUpperLeft
379 OpSource ESSL 310
380 OpName %4 "main"
381 %2 = OpTypeVoid
382 %3 = OpTypeFunction %2
383 %6 = OpTypeBool
384 %7 = OpConstantTrue %6
385 %9 = OpTypeInt 32 0
386 %10 = OpConstant %9 1
387 %4 = OpFunction %2 None %3
388 %5 = OpLabel
389 OpBranch %8
390 %8 = OpLabel
391 %12 = OpPhi %6 %7 %5
392 %13 = OpPhi %9 %10 %5
393 OpReturn
394 OpFunctionEnd
395 )";
396
397 const auto env = SPV_ENV_UNIVERSAL_1_4;
398 const auto consumer = nullptr;
399 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
400 spvtools::ValidatorOptions validator_options;
401 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
402 kConsoleMessageConsumer));
403 TransformationContext transformation_context(
404 MakeUnique<FactManager>(context.get()), validator_options);
405 TransformationAddDeadBlock transformation(100, 5, true);
406 ASSERT_TRUE(
407 transformation.IsApplicable(context.get(), transformation_context));
408 ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
409 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
410 kConsoleMessageConsumer));
411
412 ASSERT_TRUE(transformation_context.GetFactManager()->BlockIsDead(100));
413
414 std::string after_transformation = R"(
415 OpCapability Shader
416 %1 = OpExtInstImport "GLSL.std.450"
417 OpMemoryModel Logical GLSL450
418 OpEntryPoint Fragment %4 "main"
419 OpExecutionMode %4 OriginUpperLeft
420 OpSource ESSL 310
421 OpName %4 "main"
422 %2 = OpTypeVoid
423 %3 = OpTypeFunction %2
424 %6 = OpTypeBool
425 %7 = OpConstantTrue %6
426 %9 = OpTypeInt 32 0
427 %10 = OpConstant %9 1
428 %4 = OpFunction %2 None %3
429 %5 = OpLabel
430 OpSelectionMerge %8 None
431 OpBranchConditional %7 %8 %100
432 %100 = OpLabel
433 OpBranch %8
434 %8 = OpLabel
435 %12 = OpPhi %6 %7 %5 %7 %100
436 %13 = OpPhi %9 %10 %5 %10 %100
437 OpReturn
438 OpFunctionEnd
439 )";
440 ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
441 }
442
TEST(TransformationAddDeadBlockTest, BackEdge)443 TEST(TransformationAddDeadBlockTest, BackEdge) {
444 std::string shader = R"(
445 OpCapability Shader
446 %1 = OpExtInstImport "GLSL.std.450"
447 OpMemoryModel Logical GLSL450
448 OpEntryPoint Fragment %4 "main"
449 OpExecutionMode %4 OriginUpperLeft
450 OpSource ESSL 310
451 OpName %4 "main"
452 %2 = OpTypeVoid
453 %3 = OpTypeFunction %2
454 %6 = OpTypeBool
455 %7 = OpConstantTrue %6
456 %4 = OpFunction %2 None %3
457 %5 = OpLabel
458 OpBranch %8
459 %8 = OpLabel
460 OpLoopMerge %10 %9 None
461 OpBranchConditional %7 %9 %10
462 %9 = OpLabel
463 OpBranch %8
464 %10 = OpLabel
465 OpReturn
466 OpFunctionEnd
467 )";
468
469 const auto env = SPV_ENV_UNIVERSAL_1_4;
470 const auto consumer = nullptr;
471 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
472 spvtools::ValidatorOptions validator_options;
473 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
474 kConsoleMessageConsumer));
475 TransformationContext transformation_context(
476 MakeUnique<FactManager>(context.get()), validator_options);
477 // 9 is a back edge block, so it would not be OK to add a dead block here,
478 // as then both 9 and the dead block would branch to the loop header, 8.
479 ASSERT_FALSE(TransformationAddDeadBlock(100, 9, true)
480 .IsApplicable(context.get(), transformation_context));
481 }
482
483 } // namespace
484 } // namespace fuzz
485 } // namespace spvtools
486