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