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/call_graph.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
25 // The SPIR-V came from this GLSL, slightly modified
26 // (main is %2, A is %35, B is %48, C is %50, D is %61):
27 //
28 // #version 310 es
29 //
30 // int A (int x) {
31 // return x + 1;
32 // }
33 //
34 // void D() {
35 // }
36 //
37 // void C() {
38 // int x = 0;
39 // int y = 0;
40 //
41 // while (x < 10) {
42 // while (y < 10) {
43 // y = A(y);
44 // }
45 // x = A(x);
46 // }
47 // }
48 //
49 // void B () {
50 // int x = 0;
51 // int y = 0;
52 //
53 // while (x < 10) {
54 // D();
55 // while (y < 10) {
56 // y = A(y);
57 // C();
58 // }
59 // x++;
60 // }
61 //
62 // }
63 //
64 // void main()
65 // {
66 // int x = 0;
67 // int y = 0;
68 // int z = 0;
69 //
70 // while (x < 10) {
71 // while(y < 10) {
72 // y = A(x);
73 // while (z < 10) {
74 // z = A(z);
75 // }
76 // }
77 // x += 2;
78 // }
79 //
80 // B();
81 // C();
82 // }
83 std::string shader = R"(
84 OpCapability Shader
85 %1 = OpExtInstImport "GLSL.std.450"
86 OpMemoryModel Logical GLSL450
87 OpEntryPoint Fragment %2 "main"
88 OpExecutionMode %2 OriginUpperLeft
89 OpSource ESSL 310
90 %3 = OpTypeVoid
91 %4 = OpTypeFunction %3
92 %5 = OpTypeInt 32 1
93 %6 = OpTypePointer Function %5
94 %7 = OpTypeFunction %5 %6
95 %8 = OpConstant %5 1
96 %9 = OpConstant %5 0
97 %10 = OpConstant %5 10
98 %11 = OpTypeBool
99 %12 = OpConstant %5 2
100 %2 = OpFunction %3 None %4
101 %13 = OpLabel
102 %14 = OpVariable %6 Function
103 %15 = OpVariable %6 Function
104 %16 = OpVariable %6 Function
105 %17 = OpVariable %6 Function
106 %18 = OpVariable %6 Function
107 OpStore %14 %9
108 OpStore %15 %9
109 OpStore %16 %9
110 OpBranch %19
111 %19 = OpLabel
112 OpLoopMerge %20 %21 None
113 OpBranch %22
114 %22 = OpLabel
115 %23 = OpLoad %5 %14
116 %24 = OpSLessThan %11 %23 %10
117 OpBranchConditional %24 %25 %20
118 %25 = OpLabel
119 OpBranch %26
120 %26 = OpLabel
121 OpLoopMerge %27 %28 None
122 OpBranch %29
123 %29 = OpLabel
124 %30 = OpLoad %5 %15
125 %31 = OpSLessThan %11 %30 %10
126 OpBranchConditional %31 %32 %27
127 %32 = OpLabel
128 %33 = OpLoad %5 %14
129 OpStore %17 %33
130 %34 = OpFunctionCall %5 %35 %17
131 OpStore %15 %34
132 OpBranch %36
133 %36 = OpLabel
134 OpLoopMerge %37 %38 None
135 OpBranch %39
136 %39 = OpLabel
137 %40 = OpLoad %5 %16
138 %41 = OpSLessThan %11 %40 %10
139 OpBranchConditional %41 %42 %37
140 %42 = OpLabel
141 %43 = OpLoad %5 %16
142 OpStore %18 %43
143 %44 = OpFunctionCall %5 %35 %18
144 OpStore %16 %44
145 OpBranch %38
146 %38 = OpLabel
147 OpBranch %36
148 %37 = OpLabel
149 OpBranch %28
150 %28 = OpLabel
151 OpBranch %26
152 %27 = OpLabel
153 %45 = OpLoad %5 %14
154 %46 = OpIAdd %5 %45 %12
155 OpStore %14 %46
156 OpBranch %21
157 %21 = OpLabel
158 OpBranch %19
159 %20 = OpLabel
160 %47 = OpFunctionCall %3 %48
161 %49 = OpFunctionCall %3 %50
162 OpReturn
163 OpFunctionEnd
164 %35 = OpFunction %5 None %7
165 %51 = OpFunctionParameter %6
166 %52 = OpLabel
167 %53 = OpLoad %5 %51
168 %54 = OpIAdd %5 %53 %8
169 OpReturnValue %54
170 OpFunctionEnd
171 %48 = OpFunction %3 None %4
172 %55 = OpLabel
173 %56 = OpVariable %6 Function
174 %57 = OpVariable %6 Function
175 %58 = OpVariable %6 Function
176 OpStore %56 %9
177 OpStore %57 %9
178 OpBranch %59
179 %59 = OpLabel
180 %60 = OpFunctionCall %3 %61
181 OpLoopMerge %62 %63 None
182 OpBranch %64
183 %64 = OpLabel
184 OpLoopMerge %65 %66 None
185 OpBranch %67
186 %67 = OpLabel
187 %68 = OpLoad %5 %57
188 %69 = OpSLessThan %11 %68 %10
189 OpBranchConditional %69 %70 %65
190 %70 = OpLabel
191 %71 = OpLoad %5 %57
192 OpStore %58 %71
193 %72 = OpFunctionCall %5 %35 %58
194 OpStore %57 %72
195 %73 = OpFunctionCall %3 %50
196 OpBranch %66
197 %66 = OpLabel
198 OpBranch %64
199 %65 = OpLabel
200 %74 = OpLoad %5 %56
201 %75 = OpIAdd %5 %74 %8
202 OpStore %56 %75
203 OpBranch %63
204 %63 = OpLabel
205 %76 = OpLoad %5 %56
206 %77 = OpSLessThan %11 %76 %10
207 OpBranchConditional %77 %59 %62
208 %62 = OpLabel
209 OpReturn
210 OpFunctionEnd
211 %50 = OpFunction %3 None %4
212 %78 = OpLabel
213 %79 = OpVariable %6 Function
214 %80 = OpVariable %6 Function
215 %81 = OpVariable %6 Function
216 %82 = OpVariable %6 Function
217 OpStore %79 %9
218 OpStore %80 %9
219 OpBranch %83
220 %83 = OpLabel
221 OpLoopMerge %84 %85 None
222 OpBranch %86
223 %86 = OpLabel
224 %87 = OpLoad %5 %79
225 %88 = OpSLessThan %11 %87 %10
226 OpBranchConditional %88 %89 %84
227 %89 = OpLabel
228 OpBranch %90
229 %90 = OpLabel
230 OpLoopMerge %91 %92 None
231 OpBranch %93
232 %93 = OpLabel
233 %94 = OpLoad %5 %80
234 %95 = OpSLessThan %11 %94 %10
235 OpBranchConditional %95 %96 %91
236 %96 = OpLabel
237 %97 = OpLoad %5 %80
238 OpStore %81 %97
239 %98 = OpFunctionCall %5 %35 %81
240 OpStore %80 %98
241 OpBranch %92
242 %92 = OpLabel
243 OpBranch %90
244 %91 = OpLabel
245 %99 = OpLoad %5 %79
246 OpStore %82 %99
247 %100 = OpFunctionCall %5 %35 %82
248 OpStore %79 %100
249 OpBranch %85
250 %85 = OpLabel
251 OpBranch %83
252 %84 = OpLabel
253 OpReturn
254 OpFunctionEnd
255 %61 = OpFunction %3 None %4
256 %101 = OpLabel
257 OpReturn
258 OpFunctionEnd
259 )";
260
261 // We have that:
262 // main calls:
263 // - A (maximum loop nesting depth of function call: 3)
264 // - B (0)
265 // - C (0)
266 // A calls nothing.
267 // B calls:
268 // - A (2)
269 // - C (2)
270 // - D (1)
271 // C calls:
272 // - A (2)
273 // D calls nothing.
274
TEST(CallGraphTest,FunctionInDegree)275 TEST(CallGraphTest, FunctionInDegree) {
276 const auto env = SPV_ENV_UNIVERSAL_1_5;
277 const auto consumer = nullptr;
278
279 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
280 spvtools::ValidatorOptions validator_options;
281 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
282 kConsoleMessageConsumer));
283
284 const auto graph = CallGraph(context.get());
285
286 const auto& function_in_degree = graph.GetFunctionInDegree();
287 // Check the in-degrees of, in order: main, A, B, C, D.
288 ASSERT_EQ(function_in_degree.at(2), 0);
289 ASSERT_EQ(function_in_degree.at(35), 3);
290 ASSERT_EQ(function_in_degree.at(48), 1);
291 ASSERT_EQ(function_in_degree.at(50), 2);
292 ASSERT_EQ(function_in_degree.at(61), 1);
293 }
294
TEST(CallGraphTest,DirectCallees)295 TEST(CallGraphTest, DirectCallees) {
296 const auto env = SPV_ENV_UNIVERSAL_1_5;
297 const auto consumer = nullptr;
298
299 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
300 spvtools::ValidatorOptions validator_options;
301 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
302 kConsoleMessageConsumer));
303
304 const auto graph = CallGraph(context.get());
305
306 // Check the callee sets of, in order: main, A, B, C, D.
307 ASSERT_EQ(graph.GetDirectCallees(2), std::set<uint32_t>({35, 48, 50}));
308 ASSERT_EQ(graph.GetDirectCallees(35), std::set<uint32_t>({}));
309 ASSERT_EQ(graph.GetDirectCallees(48), std::set<uint32_t>({35, 50, 61}));
310 ASSERT_EQ(graph.GetDirectCallees(50), std::set<uint32_t>({35}));
311 ASSERT_EQ(graph.GetDirectCallees(61), std::set<uint32_t>({}));
312 }
313
TEST(CallGraphTest,IndirectCallees)314 TEST(CallGraphTest, IndirectCallees) {
315 const auto env = SPV_ENV_UNIVERSAL_1_5;
316 const auto consumer = nullptr;
317
318 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
319 spvtools::ValidatorOptions validator_options;
320 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
321 kConsoleMessageConsumer));
322
323 const auto graph = CallGraph(context.get());
324
325 // Check the callee sets of, in order: main, A, B, C, D.
326 ASSERT_EQ(graph.GetIndirectCallees(2), std::set<uint32_t>({35, 48, 50, 61}));
327 ASSERT_EQ(graph.GetDirectCallees(35), std::set<uint32_t>({}));
328 ASSERT_EQ(graph.GetDirectCallees(48), std::set<uint32_t>({35, 50, 61}));
329 ASSERT_EQ(graph.GetDirectCallees(50), std::set<uint32_t>({35}));
330 ASSERT_EQ(graph.GetDirectCallees(61), std::set<uint32_t>({}));
331 }
332
TEST(CallGraphTest,TopologicalOrder)333 TEST(CallGraphTest, TopologicalOrder) {
334 const auto env = SPV_ENV_UNIVERSAL_1_5;
335 const auto consumer = nullptr;
336
337 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
338 spvtools::ValidatorOptions validator_options;
339 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
340 kConsoleMessageConsumer));
341
342 const auto graph = CallGraph(context.get());
343
344 const auto& topological_ordering = graph.GetFunctionsInTopologicalOrder();
345
346 // The possible topological orderings are:
347 // - main, B, D, C, A
348 // - main, B, C, D, A
349 // - main, B, C, A, D
350 ASSERT_TRUE(
351 topological_ordering == std::vector<uint32_t>({2, 48, 61, 50, 35}) ||
352 topological_ordering == std::vector<uint32_t>({2, 48, 50, 61, 35}) ||
353 topological_ordering == std::vector<uint32_t>({2, 48, 50, 35, 61}));
354 }
355
TEST(CallGraphTest,LoopNestingDepth)356 TEST(CallGraphTest, LoopNestingDepth) {
357 const auto env = SPV_ENV_UNIVERSAL_1_5;
358 const auto consumer = nullptr;
359
360 const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
361 spvtools::ValidatorOptions validator_options;
362 ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
363 kConsoleMessageConsumer));
364
365 const auto graph = CallGraph(context.get());
366
367 // Check the maximum loop nesting depth for function calls to, in order:
368 // main, A, B, C, D
369 ASSERT_EQ(graph.GetMaxCallNestingDepth(2), 0);
370 ASSERT_EQ(graph.GetMaxCallNestingDepth(35), 4);
371 ASSERT_EQ(graph.GetMaxCallNestingDepth(48), 0);
372 ASSERT_EQ(graph.GetMaxCallNestingDepth(50), 2);
373 ASSERT_EQ(graph.GetMaxCallNestingDepth(61), 1);
374 }
375
376 } // namespace
377 } // namespace fuzz
378 } // namespace spvtools
379