1 // Copyright (c) 2017 Google Inc.
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 "source/opt/build_module.h"
19 #include "source/opt/value_number_table.h"
20 #include "test/opt/assembly_builder.h"
21 #include "test/opt/pass_fixture.h"
22 #include "test/opt/pass_utils.h"
23
24 namespace spvtools {
25 namespace opt {
26 namespace {
27
28 using ::testing::HasSubstr;
29 using ::testing::MatchesRegex;
30 using RedundancyEliminationTest = PassTest<::testing::Test>;
31
32 // Test that it can get a simple case of local redundancy elimination.
33 // The rest of the test check for extra functionality.
TEST_F(RedundancyEliminationTest,RemoveRedundantLocalAdd)34 TEST_F(RedundancyEliminationTest, RemoveRedundantLocalAdd) {
35 const std::string text = R"(
36 OpCapability Shader
37 %1 = OpExtInstImport "GLSL.std.450"
38 OpMemoryModel Logical GLSL450
39 OpEntryPoint Fragment %2 "main"
40 OpExecutionMode %2 OriginUpperLeft
41 OpSource GLSL 430
42 %3 = OpTypeVoid
43 %4 = OpTypeFunction %3
44 %5 = OpTypeFloat 32
45 %6 = OpTypePointer Function %5
46 %2 = OpFunction %3 None %4
47 %7 = OpLabel
48 %8 = OpVariable %6 Function
49 %9 = OpLoad %5 %8
50 %10 = OpFAdd %5 %9 %9
51 ; CHECK: OpFAdd
52 ; CHECK-NOT: OpFAdd
53 %11 = OpFAdd %5 %9 %9
54 OpReturn
55 OpFunctionEnd
56 )";
57 SinglePassRunAndMatch<RedundancyEliminationPass>(text, false);
58 }
59
60 // Remove a redundant add across basic blocks.
TEST_F(RedundancyEliminationTest,RemoveRedundantAdd)61 TEST_F(RedundancyEliminationTest, RemoveRedundantAdd) {
62 const std::string text = R"(
63 OpCapability Shader
64 %1 = OpExtInstImport "GLSL.std.450"
65 OpMemoryModel Logical GLSL450
66 OpEntryPoint Fragment %2 "main"
67 OpExecutionMode %2 OriginUpperLeft
68 OpSource GLSL 430
69 %3 = OpTypeVoid
70 %4 = OpTypeFunction %3
71 %5 = OpTypeFloat 32
72 %6 = OpTypePointer Function %5
73 %2 = OpFunction %3 None %4
74 %7 = OpLabel
75 %8 = OpVariable %6 Function
76 %9 = OpLoad %5 %8
77 %10 = OpFAdd %5 %9 %9
78 OpBranch %11
79 %11 = OpLabel
80 ; CHECK: OpFAdd
81 ; CHECK-NOT: OpFAdd
82 %12 = OpFAdd %5 %9 %9
83 OpReturn
84 OpFunctionEnd
85 )";
86 SinglePassRunAndMatch<RedundancyEliminationPass>(text, false);
87 }
88
89 // Remove a redundant add going through a multiple basic blocks.
TEST_F(RedundancyEliminationTest,RemoveRedundantAddDiamond)90 TEST_F(RedundancyEliminationTest, RemoveRedundantAddDiamond) {
91 const std::string text = R"(
92 OpCapability Shader
93 %1 = OpExtInstImport "GLSL.std.450"
94 OpMemoryModel Logical GLSL450
95 OpEntryPoint Fragment %2 "main"
96 OpExecutionMode %2 OriginUpperLeft
97 OpSource GLSL 430
98 %3 = OpTypeVoid
99 %4 = OpTypeFunction %3
100 %5 = OpTypeFloat 32
101 %6 = OpTypePointer Function %5
102 %7 = OpTypeBool
103 %8 = OpConstantTrue %7
104 %2 = OpFunction %3 None %4
105 %9 = OpLabel
106 %10 = OpVariable %6 Function
107 %11 = OpLoad %5 %10
108 %12 = OpFAdd %5 %11 %11
109 ; CHECK: OpFAdd
110 ; CHECK-NOT: OpFAdd
111 OpBranchConditional %8 %13 %14
112 %13 = OpLabel
113 OpBranch %15
114 %14 = OpLabel
115 OpBranch %15
116 %15 = OpLabel
117 %16 = OpFAdd %5 %11 %11
118 OpReturn
119 OpFunctionEnd
120
121 )";
122 SinglePassRunAndMatch<RedundancyEliminationPass>(text, false);
123 }
124
125 // Remove a redundant add in a side node.
TEST_F(RedundancyEliminationTest,RemoveRedundantAddInSideNode)126 TEST_F(RedundancyEliminationTest, RemoveRedundantAddInSideNode) {
127 const std::string text = R"(
128 OpCapability Shader
129 %1 = OpExtInstImport "GLSL.std.450"
130 OpMemoryModel Logical GLSL450
131 OpEntryPoint Fragment %2 "main"
132 OpExecutionMode %2 OriginUpperLeft
133 OpSource GLSL 430
134 %3 = OpTypeVoid
135 %4 = OpTypeFunction %3
136 %5 = OpTypeFloat 32
137 %6 = OpTypePointer Function %5
138 %7 = OpTypeBool
139 %8 = OpConstantTrue %7
140 %2 = OpFunction %3 None %4
141 %9 = OpLabel
142 %10 = OpVariable %6 Function
143 %11 = OpLoad %5 %10
144 %12 = OpFAdd %5 %11 %11
145 ; CHECK: OpFAdd
146 ; CHECK-NOT: OpFAdd
147 OpBranchConditional %8 %13 %14
148 %13 = OpLabel
149 OpBranch %15
150 %14 = OpLabel
151 %16 = OpFAdd %5 %11 %11
152 OpBranch %15
153 %15 = OpLabel
154 OpReturn
155 OpFunctionEnd
156
157 )";
158 SinglePassRunAndMatch<RedundancyEliminationPass>(text, false);
159 }
160
161 // Remove a redundant add whose value is in the result of a phi node.
TEST_F(RedundancyEliminationTest,RemoveRedundantAddWithPhi)162 TEST_F(RedundancyEliminationTest, RemoveRedundantAddWithPhi) {
163 const std::string text = R"(
164 OpCapability Shader
165 %1 = OpExtInstImport "GLSL.std.450"
166 OpMemoryModel Logical GLSL450
167 OpEntryPoint Fragment %2 "main"
168 OpExecutionMode %2 OriginUpperLeft
169 OpSource GLSL 430
170 %3 = OpTypeVoid
171 %4 = OpTypeFunction %3
172 %5 = OpTypeFloat 32
173 %6 = OpTypePointer Function %5
174 %7 = OpTypeBool
175 %8 = OpConstantTrue %7
176 %2 = OpFunction %3 None %4
177 %9 = OpLabel
178 %10 = OpVariable %6 Function
179 %11 = OpLoad %5 %10
180 OpBranchConditional %8 %13 %14
181 %13 = OpLabel
182 %add1 = OpFAdd %5 %11 %11
183 ; CHECK: OpFAdd
184 OpBranch %15
185 %14 = OpLabel
186 %add2 = OpFAdd %5 %11 %11
187 ; CHECK: OpFAdd
188 OpBranch %15
189 %15 = OpLabel
190 ; CHECK: OpPhi
191 %phi = OpPhi %5 %add1 %13 %add2 %14
192 ; CHECK-NOT: OpFAdd
193 %16 = OpFAdd %5 %11 %11
194 OpReturn
195 OpFunctionEnd
196
197 )";
198 SinglePassRunAndMatch<RedundancyEliminationPass>(text, false);
199 }
200
201 // Keep the add because it is redundant on some paths, but not all paths.
TEST_F(RedundancyEliminationTest,KeepPartiallyRedundantAdd)202 TEST_F(RedundancyEliminationTest, KeepPartiallyRedundantAdd) {
203 const std::string text = R"(
204 OpCapability Shader
205 %1 = OpExtInstImport "GLSL.std.450"
206 OpMemoryModel Logical GLSL450
207 OpEntryPoint Fragment %2 "main"
208 OpExecutionMode %2 OriginUpperLeft
209 OpSource GLSL 430
210 %3 = OpTypeVoid
211 %4 = OpTypeFunction %3
212 %5 = OpTypeFloat 32
213 %6 = OpTypePointer Function %5
214 %7 = OpTypeBool
215 %8 = OpConstantTrue %7
216 %2 = OpFunction %3 None %4
217 %9 = OpLabel
218 %10 = OpVariable %6 Function
219 %11 = OpLoad %5 %10
220 OpBranchConditional %8 %13 %14
221 %13 = OpLabel
222 %add = OpFAdd %5 %11 %11
223 OpBranch %15
224 %14 = OpLabel
225 OpBranch %15
226 %15 = OpLabel
227 %16 = OpFAdd %5 %11 %11
228 OpReturn
229 OpFunctionEnd
230
231 )";
232 auto result = SinglePassRunAndDisassemble<RedundancyEliminationPass>(
233 text, /* skip_nop = */ true, /* do_validation = */ false);
234 EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
235 }
236
237 // Keep the add. Even if it is redundant on all paths, there is no single id
238 // whose definition dominates the add and contains the same value.
TEST_F(RedundancyEliminationTest,KeepRedundantAddWithoutPhi)239 TEST_F(RedundancyEliminationTest, KeepRedundantAddWithoutPhi) {
240 const std::string text = R"(
241 OpCapability Shader
242 %1 = OpExtInstImport "GLSL.std.450"
243 OpMemoryModel Logical GLSL450
244 OpEntryPoint Fragment %2 "main"
245 OpExecutionMode %2 OriginUpperLeft
246 OpSource GLSL 430
247 %3 = OpTypeVoid
248 %4 = OpTypeFunction %3
249 %5 = OpTypeFloat 32
250 %6 = OpTypePointer Function %5
251 %7 = OpTypeBool
252 %8 = OpConstantTrue %7
253 %2 = OpFunction %3 None %4
254 %9 = OpLabel
255 %10 = OpVariable %6 Function
256 %11 = OpLoad %5 %10
257 OpBranchConditional %8 %13 %14
258 %13 = OpLabel
259 %add1 = OpFAdd %5 %11 %11
260 OpBranch %15
261 %14 = OpLabel
262 %add2 = OpFAdd %5 %11 %11
263 OpBranch %15
264 %15 = OpLabel
265 %16 = OpFAdd %5 %11 %11
266 OpReturn
267 OpFunctionEnd
268
269 )";
270 auto result = SinglePassRunAndDisassemble<RedundancyEliminationPass>(
271 text, /* skip_nop = */ true, /* do_validation = */ false);
272 EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
273 }
274
275 // Test that it can get a simple case of local redundancy elimination
276 // when it has OpenCL.DebugInfo.100 instructions.
TEST_F(RedundancyEliminationTest,OpenCLDebugInfo100)277 TEST_F(RedundancyEliminationTest, OpenCLDebugInfo100) {
278 // When three redundant DebugValues exist, only one DebugValue must remain.
279 const std::string text = R"(
280 OpCapability Shader
281 %1 = OpExtInstImport "OpenCL.DebugInfo.100"
282 %2 = OpExtInstImport "GLSL.std.450"
283 OpMemoryModel Logical GLSL450
284 OpEntryPoint Fragment %3 "main"
285 OpExecutionMode %3 OriginUpperLeft
286 OpSource GLSL 430
287 %4 = OpString "ps.hlsl"
288 %5 = OpString "float"
289 %6 = OpString "s0"
290 %7 = OpString "main"
291 %void = OpTypeVoid
292 %9 = OpTypeFunction %void
293 %float = OpTypeFloat 32
294 %uint = OpTypeInt 32 0
295 %uint_0 = OpConstant %uint 0
296 %uint_32 = OpConstant %uint 32
297 %_ptr_Function_float = OpTypePointer Function %float
298 %15 = OpExtInst %void %1 DebugExpression
299 %16 = OpExtInst %void %1 DebugSource %4
300 %17 = OpExtInst %void %1 DebugCompilationUnit 1 4 %16 HLSL
301 %18 = OpExtInst %void %1 DebugTypeBasic %5 %uint_32 Float
302 %19 = OpExtInst %void %1 DebugTypeVector %18 4
303 %20 = OpExtInst %void %1 DebugTypeFunction FlagIsProtected|FlagIsPrivate %19
304 %21 = OpExtInst %void %1 DebugFunction %7 %20 %16 4 1 %17 %7 FlagIsProtected|FlagIsPrivate 4 %3
305 ; CHECK: [[dbg_local_var:%\w+]] = OpExtInst %void {{%\w+}} DebugLocalVariable
306 %22 = OpExtInst %void %1 DebugLocalVariable %6 %19 %16 0 0 %21 FlagIsLocal
307 %14 = OpExtInst %void %1 DebugLocalVariable %6 %19 %16 0 0 %21 FlagIsLocal
308 %3 = OpFunction %void None %9
309 %23 = OpLabel
310 %24 = OpExtInst %void %1 DebugScope %21
311 %25 = OpVariable %_ptr_Function_float Function
312 %26 = OpLoad %float %25
313 OpLine %4 0 0
314 ; Two `OpFAdd %float %26 %26` are the same. One must be removed.
315 ; After removing one `OpFAdd %float %26 %26`, two DebugValues are the same.
316 ; One must be removed.
317 ;
318 ; CHECK: OpLine {{%\w+}} 0 0
319 ; CHECK-NEXT: [[add:%\w+]] = OpFAdd %float [[value:%\w+]]
320 ; CHECK-NEXT: DebugValue [[dbg_local_var]] [[add]]
321 ; CHECK-NEXT: OpLine {{%\w+}} 1 0
322 ; CHECK-NEXT: OpFAdd %float [[add]] [[value]]
323 ; CHECK-NEXT: OpReturn
324 %27 = OpFAdd %float %26 %26
325 %28 = OpExtInst %void %1 DebugValue %22 %27 %15 %uint_0
326 OpLine %4 1 0
327 %29 = OpFAdd %float %26 %26
328 %30 = OpExtInst %void %1 DebugValue %14 %29 %15 %uint_0
329 %31 = OpExtInst %void %1 DebugValue %22 %29 %15 %uint_0
330 %32 = OpFAdd %float %29 %26
331 %33 = OpFAdd %float %27 %26
332 OpReturn
333 OpFunctionEnd
334 )";
335 SinglePassRunAndMatch<RedundancyEliminationPass>(text, false);
336 }
337
338 } // namespace
339 } // namespace opt
340 } // namespace spvtools
341