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 }  // namespace
276 }  // namespace opt
277 }  // namespace spvtools
278