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
21namespace spvtools {
22namespace fuzz {
23namespace {
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//    }
83std::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
275TEST(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
295TEST(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
314TEST(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
333TEST(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
356TEST(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