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/comparator_deep_blocks_first.h"
16 
17 #include "gtest/gtest.h"
18 #include "source/fuzz/fact_manager/fact_manager.h"
19 #include "source/fuzz/fuzzer_util.h"
20 #include "source/fuzz/pseudo_random_generator.h"
21 #include "source/fuzz/transformation_context.h"
22 #include "test/fuzz/fuzz_test_util.h"
23 
24 namespace spvtools {
25 namespace fuzz {
26 namespace {
27 
28 std::string shader = R"(
29                OpCapability Shader
30           %1 = OpExtInstImport "GLSL.std.450"
31                OpMemoryModel Logical GLSL450
32                OpEntryPoint Fragment %2 "main"
33                OpExecutionMode %2 OriginUpperLeft
34                OpSource ESSL 310
35           %3 = OpTypeVoid
36           %4 = OpTypeFunction %3
37           %5 = OpTypeBool
38           %6 = OpConstantTrue %5
39           %7 = OpTypeInt 32 1
40           %8 = OpTypePointer Function %7
41           %9 = OpConstant %7 1
42          %10 = OpConstant %7 10
43          %11 = OpConstant %7 2
44           %2 = OpFunction %3 None %4
45          %12 = OpLabel
46                OpSelectionMerge %13 None
47                OpBranchConditional %6 %14 %15
48          %14 = OpLabel
49                OpBranch %13
50          %15 = OpLabel
51                OpBranch %16
52          %16 = OpLabel
53                OpLoopMerge %17 %18 None
54                OpBranch %19
55          %19 = OpLabel
56                OpBranchConditional %6 %20 %17
57          %20 = OpLabel
58                OpSelectionMerge %21 None
59                OpBranchConditional %6 %22 %23
60          %22 = OpLabel
61                OpBranch %21
62          %23 = OpLabel
63                OpBranch %21
64          %21 = OpLabel
65                OpBranch %18
66          %18 = OpLabel
67                OpBranch %16
68          %17 = OpLabel
69                OpBranch %13
70          %13 = OpLabel
71                OpReturn
72                OpFunctionEnd
73 )";
74 
TEST(ComparatorDeepBlocksFirstTest,Compare)75 TEST(ComparatorDeepBlocksFirstTest, Compare) {
76   const auto env = SPV_ENV_UNIVERSAL_1_5;
77   const auto consumer = nullptr;
78   const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
79   spvtools::ValidatorOptions validator_options;
80   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
81                                                kConsoleMessageConsumer));
82   TransformationContext transformation_context(
83       MakeUnique<FactManager>(context.get()), validator_options);
84   auto is_deeper = ComparatorDeepBlocksFirst(context.get());
85 
86   // The block ids and the corresponding depths are:
87   // 12, 13          -> depth 0
88   // 14, 15, 16, 17  -> depth 1
89   // 18, 19, 20, 21  -> depth 2
90   // 22, 23          -> depth 3
91 
92   // Perform some comparisons and check that they return true iff the first
93   // block is deeper than the second.
94   ASSERT_FALSE(is_deeper(12, 12));
95   ASSERT_FALSE(is_deeper(12, 13));
96   ASSERT_FALSE(is_deeper(12, 14));
97   ASSERT_FALSE(is_deeper(12, 18));
98   ASSERT_FALSE(is_deeper(12, 22));
99   ASSERT_TRUE(is_deeper(14, 12));
100   ASSERT_FALSE(is_deeper(14, 15));
101   ASSERT_FALSE(is_deeper(15, 14));
102   ASSERT_FALSE(is_deeper(14, 18));
103   ASSERT_TRUE(is_deeper(18, 12));
104   ASSERT_TRUE(is_deeper(18, 16));
105 }
106 
TEST(ComparatorDeepBlocksFirstTest,Sort)107 TEST(ComparatorDeepBlocksFirstTest, Sort) {
108   const auto env = SPV_ENV_UNIVERSAL_1_5;
109   const auto consumer = nullptr;
110   const auto context = BuildModule(env, consumer, shader, kFuzzAssembleOption);
111   spvtools::ValidatorOptions validator_options;
112   ASSERT_TRUE(fuzzerutil::IsValidAndWellFormed(context.get(), validator_options,
113                                                kConsoleMessageConsumer));
114   TransformationContext transformation_context(
115       MakeUnique<FactManager>(context.get()), validator_options);
116   // Check that, sorting using the comparator, the blocks are ordered from more
117   // deeply nested to less deeply nested.
118   // 17 has depth 1, 20 has depth 2, 13 has depth 0.
119   std::vector<opt::BasicBlock*> blocks = {context->get_instr_block(17),
120                                           context->get_instr_block(20),
121                                           context->get_instr_block(13)};
122 
123   std::sort(blocks.begin(), blocks.end(),
124             ComparatorDeepBlocksFirst(context.get()));
125 
126   // Check that the blocks are in the correct order.
127   ASSERT_EQ(blocks[0]->id(), 20);
128   ASSERT_EQ(blocks[1]->id(), 17);
129   ASSERT_EQ(blocks[2]->id(), 13);
130 }
131 }  // namespace
132 }  // namespace fuzz
133 }  // namespace spvtools
134