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 <string>
16
17 #include "gmock/gmock.h"
18 #include "gtest/gtest.h"
19 #include "source/opt/ir_context.h"
20 #include "test/opt/pass_fixture.h"
21 #include "test/opt/pass_utils.h"
22
23 namespace spvtools {
24 namespace opt {
25 namespace {
26
27 using ::testing::ContainerEq;
28
29 using CFGTest = PassTest<::testing::Test>;
30
TEST_F(CFGTest,ForEachBlockInPostOrderIf)31 TEST_F(CFGTest, ForEachBlockInPostOrderIf) {
32 const std::string test = R"(
33 OpCapability Shader
34 %1 = OpExtInstImport "GLSL.std.450"
35 OpMemoryModel Logical GLSL450
36 OpEntryPoint Vertex %main "main"
37 OpName %main "main"
38 %bool = OpTypeBool
39 %true = OpConstantTrue %bool
40 %void = OpTypeVoid
41 %4 = OpTypeFunction %void
42 %uint = OpTypeInt 32 0
43 %5 = OpConstant %uint 5
44 %main = OpFunction %void None %4
45 %8 = OpLabel
46 OpSelectionMerge %10 None
47 OpBranchConditional %true %9 %10
48 %9 = OpLabel
49 OpBranch %10
50 %10 = OpLabel
51 OpReturn
52 OpFunctionEnd
53 )";
54
55 std::unique_ptr<IRContext> context =
56 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, test,
57 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
58 ASSERT_NE(nullptr, context);
59
60 CFG* cfg = context->cfg();
61 Module* module = context->module();
62 Function* function = &*module->begin();
63 std::vector<uint32_t> order;
64 cfg->ForEachBlockInPostOrder(&*function->begin(), [&order](BasicBlock* bb) {
65 order.push_back(bb->id());
66 });
67
68 std::vector<uint32_t> expected_result = {10, 9, 8};
69 EXPECT_THAT(order, ContainerEq(expected_result));
70 }
71
TEST_F(CFGTest,ForEachBlockInPostOrderLoop)72 TEST_F(CFGTest, ForEachBlockInPostOrderLoop) {
73 const std::string test = R"(
74 OpCapability Shader
75 %1 = OpExtInstImport "GLSL.std.450"
76 OpMemoryModel Logical GLSL450
77 OpEntryPoint Vertex %main "main"
78 OpName %main "main"
79 %bool = OpTypeBool
80 %true = OpConstantTrue %bool
81 %void = OpTypeVoid
82 %4 = OpTypeFunction %void
83 %uint = OpTypeInt 32 0
84 %5 = OpConstant %uint 5
85 %main = OpFunction %void None %4
86 %8 = OpLabel
87 OpBranch %9
88 %9 = OpLabel
89 OpLoopMerge %11 %10 None
90 OpBranchConditional %true %11 %10
91 %10 = OpLabel
92 OpBranch %9
93 %11 = OpLabel
94 OpReturn
95 OpFunctionEnd
96 )";
97
98 std::unique_ptr<IRContext> context =
99 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, test,
100 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
101 ASSERT_NE(nullptr, context);
102
103 CFG* cfg = context->cfg();
104 Module* module = context->module();
105 Function* function = &*module->begin();
106 std::vector<uint32_t> order;
107 cfg->ForEachBlockInPostOrder(&*function->begin(), [&order](BasicBlock* bb) {
108 order.push_back(bb->id());
109 });
110
111 std::vector<uint32_t> expected_result1 = {10, 11, 9, 8};
112 std::vector<uint32_t> expected_result2 = {11, 10, 9, 8};
113 EXPECT_THAT(order, AnyOf(ContainerEq(expected_result1),
114 ContainerEq(expected_result2)));
115 }
116
TEST_F(CFGTest,ForEachBlockInReversePostOrderIf)117 TEST_F(CFGTest, ForEachBlockInReversePostOrderIf) {
118 const std::string test = R"(
119 OpCapability Shader
120 %1 = OpExtInstImport "GLSL.std.450"
121 OpMemoryModel Logical GLSL450
122 OpEntryPoint Vertex %main "main"
123 OpName %main "main"
124 %bool = OpTypeBool
125 %true = OpConstantTrue %bool
126 %void = OpTypeVoid
127 %4 = OpTypeFunction %void
128 %uint = OpTypeInt 32 0
129 %5 = OpConstant %uint 5
130 %main = OpFunction %void None %4
131 %8 = OpLabel
132 OpSelectionMerge %10 None
133 OpBranchConditional %true %9 %10
134 %9 = OpLabel
135 OpBranch %10
136 %10 = OpLabel
137 OpReturn
138 OpFunctionEnd
139 )";
140
141 std::unique_ptr<IRContext> context =
142 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, test,
143 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
144 ASSERT_NE(nullptr, context);
145
146 CFG* cfg = context->cfg();
147 Module* module = context->module();
148 Function* function = &*module->begin();
149 std::vector<uint32_t> order;
150 cfg->ForEachBlockInReversePostOrder(
151 &*function->begin(),
152 [&order](BasicBlock* bb) { order.push_back(bb->id()); });
153
154 std::vector<uint32_t> expected_result = {8, 9, 10};
155 EXPECT_THAT(order, ContainerEq(expected_result));
156 }
157
TEST_F(CFGTest,ForEachBlockInReversePostOrderLoop)158 TEST_F(CFGTest, ForEachBlockInReversePostOrderLoop) {
159 const std::string test = R"(
160 OpCapability Shader
161 %1 = OpExtInstImport "GLSL.std.450"
162 OpMemoryModel Logical GLSL450
163 OpEntryPoint Vertex %main "main"
164 OpName %main "main"
165 %bool = OpTypeBool
166 %true = OpConstantTrue %bool
167 %void = OpTypeVoid
168 %4 = OpTypeFunction %void
169 %uint = OpTypeInt 32 0
170 %5 = OpConstant %uint 5
171 %main = OpFunction %void None %4
172 %8 = OpLabel
173 OpBranch %9
174 %9 = OpLabel
175 OpLoopMerge %11 %10 None
176 OpBranchConditional %true %11 %10
177 %10 = OpLabel
178 OpBranch %9
179 %11 = OpLabel
180 OpReturn
181 OpFunctionEnd
182 )";
183
184 std::unique_ptr<IRContext> context =
185 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, test,
186 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
187 ASSERT_NE(nullptr, context);
188
189 CFG* cfg = context->cfg();
190 Module* module = context->module();
191 Function* function = &*module->begin();
192 std::vector<uint32_t> order;
193 cfg->ForEachBlockInReversePostOrder(
194 &*function->begin(),
195 [&order](BasicBlock* bb) { order.push_back(bb->id()); });
196
197 std::vector<uint32_t> expected_result1 = {8, 9, 10, 11};
198 std::vector<uint32_t> expected_result2 = {8, 9, 11, 10};
199 EXPECT_THAT(order, AnyOf(ContainerEq(expected_result1),
200 ContainerEq(expected_result2)));
201 }
202
203 } // namespace
204 } // namespace opt
205 } // namespace spvtools
206