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