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,TargetBlockMustNotBeSelectionMerge)145 TEST(TransformationAddDeadBlockTest, TargetBlockMustNotBeSelectionMerge) {
146 std::string shader = R"(
147 OpCapability Shader
148 %1 = OpExtInstImport "GLSL.std.450"
149 OpMemoryModel Logical GLSL450
150 OpEntryPoint Fragment %4 "main"
151 OpExecutionMode %4 OriginUpperLeft
152 OpSource ESSL 310
153 OpName %4 "main"
154 %2 = OpTypeVoid
155 %3 = OpTypeFunction %2
156 %6 = OpTypeBool
157 %7 = OpConstantTrue %6
158 %4 = OpFunction %2 None %3
159 %5 = OpLabel
160 OpSelectionMerge %10 None
161 OpBranchConditional %7 %8 %9
162 %8 = OpLabel
163 OpBranch %10
164 %9 = OpLabel
165 OpBranch %10
166 %10 = OpLabel
167 OpReturn
168 OpFunctionEnd
169 )";
170
171 const auto env = SPV_ENV_UNIVERSAL_1_4;
172 const auto consumer = nullptr;
173 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
174 spvtools::ValidatorOptions validator_options;
175 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
176 kConsoleMessageConsumer));
177 TransformationContext transformation_context(
178 MakeUnique<FactManager>(context.get()), validator_options);
179 ASSERT_FALSE(TransformationAddDeadBlock(100, 9, true)
180 .IsApplicable(context.get(), transformation_context));
181 }
182
TEST(TransformationAddDeadBlockTest,TargetBlockMustNotBeLoopMergeOrContinue)183 TEST(TransformationAddDeadBlockTest, TargetBlockMustNotBeLoopMergeOrContinue) {
184 std::string shader = R"(
185 OpCapability Shader
186 %1 = OpExtInstImport "GLSL.std.450"
187 OpMemoryModel Logical GLSL450
188 OpEntryPoint Fragment %6 "main"
189 OpExecutionMode %6 OriginUpperLeft
190
191 ; Types
192 %2 = OpTypeBool
193 %3 = OpTypeVoid
194 %4 = OpTypeFunction %3
195
196 ; Constants
197 %5 = OpConstantTrue %2
198
199 ; main function
200 %6 = OpFunction %3 None %4
201 %7 = OpLabel
202 OpBranch %8
203 %8 = OpLabel
204 OpLoopMerge %12 %11 None
205 OpBranchConditional %5 %9 %10
206 %9 = OpLabel
207 OpBranch %11
208 %10 = OpLabel
209 OpBranch %12
210 %11 = OpLabel
211 OpBranch %8
212 %12 = OpLabel
213 OpReturn
214 OpFunctionEnd
215 )";
216
217 const auto env = SPV_ENV_UNIVERSAL_1_4;
218 const auto consumer = nullptr;
219 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
220 spvtools::ValidatorOptions validator_options;
221 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
222 kConsoleMessageConsumer));
223 TransformationContext transformation_context(
224 MakeUnique<FactManager>(context.get()), validator_options);
225 // Bad because 9's successor is the loop continue target.
226 ASSERT_FALSE(TransformationAddDeadBlock(100, 9, true)
227 .IsApplicable(context.get(), transformation_context));
228 // Bad because 10's successor is the loop merge.
229 ASSERT_FALSE(TransformationAddDeadBlock(100, 10, true)
230 .IsApplicable(context.get(), transformation_context));
231 }
232
TEST(TransformationAddDeadBlockTest,SourceBlockMustNotBeLoopHead)233 TEST(TransformationAddDeadBlockTest, SourceBlockMustNotBeLoopHead) {
234 std::string shader = R"(
235 OpCapability Shader
236 %1 = OpExtInstImport "GLSL.std.450"
237 OpMemoryModel Logical GLSL450
238 OpEntryPoint Fragment %4 "main"
239 OpExecutionMode %4 OriginUpperLeft
240 OpSource ESSL 310
241 OpName %4 "main"
242 %2 = OpTypeVoid
243 %3 = OpTypeFunction %2
244 %6 = OpTypeBool
245 %7 = OpConstantTrue %6
246 %4 = OpFunction %2 None %3
247 %5 = OpLabel
248 OpBranch %8
249 %8 = OpLabel
250 OpLoopMerge %11 %12 None
251 OpBranch %9
252 %9 = OpLabel
253 OpBranchConditional %7 %11 %12
254 %12 = OpLabel
255 OpBranch %8
256 %11 = OpLabel
257 OpReturn
258 OpFunctionEnd
259 )";
260
261 const auto env = SPV_ENV_UNIVERSAL_1_4;
262 const auto consumer = nullptr;
263 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
264 spvtools::ValidatorOptions validator_options;
265 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
266 kConsoleMessageConsumer));
267 TransformationContext transformation_context(
268 MakeUnique<FactManager>(context.get()), validator_options);
269 // Bad because 8 is a loop head.
270 ASSERT_FALSE(TransformationAddDeadBlock(100, 8, true)
271 .IsApplicable(context.get(), transformation_context));
272 }
273
TEST(TransformationAddDeadBlockTest,OpPhiInTarget)274 TEST(TransformationAddDeadBlockTest, OpPhiInTarget) {
275 std::string shader = R"(
276 OpCapability Shader
277 %1 = OpExtInstImport "GLSL.std.450"
278 OpMemoryModel Logical GLSL450
279 OpEntryPoint Fragment %4 "main"
280 OpExecutionMode %4 OriginUpperLeft
281 OpSource ESSL 310
282 OpName %4 "main"
283 %2 = OpTypeVoid
284 %3 = OpTypeFunction %2
285 %6 = OpTypeBool
286 %7 = OpConstantTrue %6
287 %9 = OpTypeInt 32 0
288 %10 = OpConstant %9 1
289 %4 = OpFunction %2 None %3
290 %5 = OpLabel
291 OpBranch %8
292 %8 = OpLabel
293 %12 = OpPhi %6 %7 %5
294 %13 = OpPhi %9 %10 %5
295 OpReturn
296 OpFunctionEnd
297 )";
298
299 const auto env = SPV_ENV_UNIVERSAL_1_4;
300 const auto consumer = nullptr;
301 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
302 spvtools::ValidatorOptions validator_options;
303 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
304 kConsoleMessageConsumer));
305 TransformationContext transformation_context(
306 MakeUnique<FactManager>(context.get()), validator_options);
307 TransformationAddDeadBlock transformation(100, 5, true);
308 ASSERT_TRUE(
309 transformation.IsApplicable(context.get(), transformation_context));
310 ApplyAndCheckFreshIds(transformation, context.get(), &transformation_context);
311 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
312 kConsoleMessageConsumer));
313
314 ASSERT_TRUE(transformation_context.GetFactManager()->BlockIsDead(100));
315
316 std::string after_transformation = R"(
317 OpCapability Shader
318 %1 = OpExtInstImport "GLSL.std.450"
319 OpMemoryModel Logical GLSL450
320 OpEntryPoint Fragment %4 "main"
321 OpExecutionMode %4 OriginUpperLeft
322 OpSource ESSL 310
323 OpName %4 "main"
324 %2 = OpTypeVoid
325 %3 = OpTypeFunction %2
326 %6 = OpTypeBool
327 %7 = OpConstantTrue %6
328 %9 = OpTypeInt 32 0
329 %10 = OpConstant %9 1
330 %4 = OpFunction %2 None %3
331 %5 = OpLabel
332 OpSelectionMerge %8 None
333 OpBranchConditional %7 %8 %100
334 %100 = OpLabel
335 OpBranch %8
336 %8 = OpLabel
337 %12 = OpPhi %6 %7 %5 %7 %100
338 %13 = OpPhi %9 %10 %5 %10 %100
339 OpReturn
340 OpFunctionEnd
341 )";
342 ASSERT_TRUE(IsEqual(env, after_transformation, context.get()));
343 }
344
TEST(TransformationAddDeadBlockTest,BackEdge)345 TEST(TransformationAddDeadBlockTest, BackEdge) {
346 std::string shader = R"(
347 OpCapability Shader
348 %1 = OpExtInstImport "GLSL.std.450"
349 OpMemoryModel Logical GLSL450
350 OpEntryPoint Fragment %4 "main"
351 OpExecutionMode %4 OriginUpperLeft
352 OpSource ESSL 310
353 OpName %4 "main"
354 %2 = OpTypeVoid
355 %3 = OpTypeFunction %2
356 %6 = OpTypeBool
357 %7 = OpConstantTrue %6
358 %4 = OpFunction %2 None %3
359 %5 = OpLabel
360 OpBranch %8
361 %8 = OpLabel
362 OpLoopMerge %10 %9 None
363 OpBranchConditional %7 %9 %10
364 %9 = OpLabel
365 OpBranch %8
366 %10 = OpLabel
367 OpReturn
368 OpFunctionEnd
369 )";
370
371 const auto env = SPV_ENV_UNIVERSAL_1_4;
372 const auto consumer = nullptr;
373 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
374 spvtools::ValidatorOptions validator_options;
375 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
376 kConsoleMessageConsumer));
377 TransformationContext transformation_context(
378 MakeUnique<FactManager>(context.get()), validator_options);
379 // 9 is a back edge block, so it would not be OK to add a dead block here,
380 // as then both 9 and the dead block would branch to the loop header, 8.
381 ASSERT_FALSE(TransformationAddDeadBlock(100, 9, true)
382 .IsApplicable(context.get(), transformation_context));
383 }
384
385 } // namespace
386 } // namespace fuzz
387 } // namespace spvtools
388