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 <algorithm>
16 #include <cstdarg>
17 #include <iostream>
18 #include <sstream>
19 #include <string>
20 #include <unordered_set>
21 #include <vector>
22
23 #include "gmock/gmock.h"
24 #include "test/opt/assembly_builder.h"
25 #include "test/opt/pass_fixture.h"
26 #include "test/opt/pass_utils.h"
27
28 namespace spvtools {
29 namespace opt {
30 namespace {
31
32 using ::testing::HasSubstr;
33 using ::testing::MatchesRegex;
34 using StrengthReductionBasicTest = PassTest<::testing::Test>;
35
36 // Test to make sure we replace 5*8.
TEST_F(StrengthReductionBasicTest,BasicReplaceMulBy8)37 TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy8) {
38 const std::vector<const char*> text = {
39 // clang-format off
40 "OpCapability Shader",
41 "%1 = OpExtInstImport \"GLSL.std.450\"",
42 "OpMemoryModel Logical GLSL450",
43 "OpEntryPoint Vertex %main \"main\"",
44 "OpName %main \"main\"",
45 "%void = OpTypeVoid",
46 "%4 = OpTypeFunction %void",
47 "%uint = OpTypeInt 32 0",
48 "%uint_5 = OpConstant %uint 5",
49 "%uint_8 = OpConstant %uint 8",
50 "%main = OpFunction %void None %4",
51 "%8 = OpLabel",
52 "%9 = OpIMul %uint %uint_5 %uint_8",
53 "OpReturn",
54 "OpFunctionEnd"
55 // clang-format on
56 };
57
58 auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
59 JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);
60
61 EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
62 const std::string& output = std::get<0>(result);
63 EXPECT_THAT(output, Not(HasSubstr("OpIMul")));
64 EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_5 %uint_3"));
65 }
66
67 // TODO(dneto): Add Effcee as required dependency, and make this unconditional.
68 // Test to make sure we replace 16*5
69 // Also demonstrate use of Effcee matching.
TEST_F(StrengthReductionBasicTest,BasicReplaceMulBy16)70 TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy16) {
71 const std::string text = R"(
72 OpCapability Shader
73 %1 = OpExtInstImport "GLSL.std.450"
74 OpMemoryModel Logical GLSL450
75 OpEntryPoint Vertex %main "main"
76 OpName %main "main"
77 %void = OpTypeVoid
78 %4 = OpTypeFunction %void
79 ; We know disassembly will produce %uint here, but
80 ; CHECK: %uint = OpTypeInt 32 0
81 ; CHECK-DAG: [[five:%[a-zA-Z_\d]+]] = OpConstant %uint 5
82
83 ; We have RE2 regular expressions, so \w matches [_a-zA-Z0-9].
84 ; This shows the preferred pattern for matching SPIR-V identifiers.
85 ; (We could have cheated in this case since we know the disassembler will
86 ; generate the 'nice' name of "%uint_4".
87 ; CHECK-DAG: [[four:%\w+]] = OpConstant %uint 4
88 %uint = OpTypeInt 32 0
89 %uint_5 = OpConstant %uint 5
90 %uint_16 = OpConstant %uint 16
91 %main = OpFunction %void None %4
92 ; CHECK: OpLabel
93 %8 = OpLabel
94 ; CHECK-NEXT: OpShiftLeftLogical %uint [[five]] [[four]]
95 ; The multiplication disappears.
96 ; CHECK-NOT: OpIMul
97 %9 = OpIMul %uint %uint_16 %uint_5
98 OpReturn
99 ; CHECK: OpFunctionEnd
100 OpFunctionEnd)";
101
102 SinglePassRunAndMatch<StrengthReductionPass>(text, false);
103 }
104
105 // Test to make sure we replace a multiple of 32 and 4.
TEST_F(StrengthReductionBasicTest,BasicTwoPowersOf2)106 TEST_F(StrengthReductionBasicTest, BasicTwoPowersOf2) {
107 // In this case, we have two powers of 2. Need to make sure we replace only
108 // one of them for the bit shift.
109 // clang-format off
110 const std::string text = R"(
111 OpCapability Shader
112 %1 = OpExtInstImport "GLSL.std.450"
113 OpMemoryModel Logical GLSL450
114 OpEntryPoint Vertex %main "main"
115 OpName %main "main"
116 %void = OpTypeVoid
117 %4 = OpTypeFunction %void
118 %int = OpTypeInt 32 1
119 %int_32 = OpConstant %int 32
120 %int_4 = OpConstant %int 4
121 %main = OpFunction %void None %4
122 %8 = OpLabel
123 %9 = OpIMul %int %int_32 %int_4
124 OpReturn
125 OpFunctionEnd
126 )";
127 // clang-format on
128 auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
129 text, /* skip_nop = */ true, /* do_validation = */ false);
130
131 EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
132 const std::string& output = std::get<0>(result);
133 EXPECT_THAT(output, Not(HasSubstr("OpIMul")));
134 EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %int %int_4 %uint_5"));
135 }
136
137 // Test to make sure we don't replace 0*5.
TEST_F(StrengthReductionBasicTest,BasicDontReplace0)138 TEST_F(StrengthReductionBasicTest, BasicDontReplace0) {
139 const std::vector<const char*> text = {
140 // clang-format off
141 "OpCapability Shader",
142 "%1 = OpExtInstImport \"GLSL.std.450\"",
143 "OpMemoryModel Logical GLSL450",
144 "OpEntryPoint Vertex %main \"main\"",
145 "OpName %main \"main\"",
146 "%void = OpTypeVoid",
147 "%4 = OpTypeFunction %void",
148 "%int = OpTypeInt 32 1",
149 "%int_0 = OpConstant %int 0",
150 "%int_5 = OpConstant %int 5",
151 "%main = OpFunction %void None %4",
152 "%8 = OpLabel",
153 "%9 = OpIMul %int %int_0 %int_5",
154 "OpReturn",
155 "OpFunctionEnd"
156 // clang-format on
157 };
158
159 auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
160 JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);
161
162 EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
163 }
164
165 // Test to make sure we do not replace a multiple of 5 and 7.
TEST_F(StrengthReductionBasicTest,BasicNoChange)166 TEST_F(StrengthReductionBasicTest, BasicNoChange) {
167 const std::vector<const char*> text = {
168 // clang-format off
169 "OpCapability Shader",
170 "%1 = OpExtInstImport \"GLSL.std.450\"",
171 "OpMemoryModel Logical GLSL450",
172 "OpEntryPoint Vertex %2 \"main\"",
173 "OpName %2 \"main\"",
174 "%3 = OpTypeVoid",
175 "%4 = OpTypeFunction %3",
176 "%5 = OpTypeInt 32 1",
177 "%6 = OpTypeInt 32 0",
178 "%7 = OpConstant %5 5",
179 "%8 = OpConstant %5 7",
180 "%2 = OpFunction %3 None %4",
181 "%9 = OpLabel",
182 "%10 = OpIMul %5 %7 %8",
183 "OpReturn",
184 "OpFunctionEnd",
185 // clang-format on
186 };
187
188 auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
189 JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);
190
191 EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
192 }
193
194 // Test to make sure constants and types are reused and not duplicated.
TEST_F(StrengthReductionBasicTest,NoDuplicateConstantsAndTypes)195 TEST_F(StrengthReductionBasicTest, NoDuplicateConstantsAndTypes) {
196 const std::vector<const char*> text = {
197 // clang-format off
198 "OpCapability Shader",
199 "%1 = OpExtInstImport \"GLSL.std.450\"",
200 "OpMemoryModel Logical GLSL450",
201 "OpEntryPoint Vertex %main \"main\"",
202 "OpName %main \"main\"",
203 "%void = OpTypeVoid",
204 "%4 = OpTypeFunction %void",
205 "%uint = OpTypeInt 32 0",
206 "%uint_8 = OpConstant %uint 8",
207 "%uint_3 = OpConstant %uint 3",
208 "%main = OpFunction %void None %4",
209 "%8 = OpLabel",
210 "%9 = OpIMul %uint %uint_8 %uint_3",
211 "OpReturn",
212 "OpFunctionEnd",
213 // clang-format on
214 };
215
216 auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
217 JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);
218
219 EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
220 const std::string& output = std::get<0>(result);
221 EXPECT_THAT(output,
222 Not(MatchesRegex(".*OpConstant %uint 3.*OpConstant %uint 3.*")));
223 EXPECT_THAT(output, Not(MatchesRegex(".*OpTypeInt 32 0.*OpTypeInt 32 0.*")));
224 }
225
226 // Test to make sure we generate the constants only once
TEST_F(StrengthReductionBasicTest,BasicCreateOneConst)227 TEST_F(StrengthReductionBasicTest, BasicCreateOneConst) {
228 const std::vector<const char*> text = {
229 // clang-format off
230 "OpCapability Shader",
231 "%1 = OpExtInstImport \"GLSL.std.450\"",
232 "OpMemoryModel Logical GLSL450",
233 "OpEntryPoint Vertex %main \"main\"",
234 "OpName %main \"main\"",
235 "%void = OpTypeVoid",
236 "%4 = OpTypeFunction %void",
237 "%uint = OpTypeInt 32 0",
238 "%uint_5 = OpConstant %uint 5",
239 "%uint_9 = OpConstant %uint 9",
240 "%uint_128 = OpConstant %uint 128",
241 "%main = OpFunction %void None %4",
242 "%8 = OpLabel",
243 "%9 = OpIMul %uint %uint_5 %uint_128",
244 "%10 = OpIMul %uint %uint_9 %uint_128",
245 "OpReturn",
246 "OpFunctionEnd"
247 // clang-format on
248 };
249
250 auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
251 JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);
252
253 EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
254 const std::string& output = std::get<0>(result);
255 EXPECT_THAT(output, Not(HasSubstr("OpIMul")));
256 EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_5 %uint_7"));
257 EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_9 %uint_7"));
258 }
259
260 // Test to make sure we generate the instructions in the correct position and
261 // that the uses get replaced as well. Here we check that the use in the return
262 // is replaced, we also check that we can replace two OpIMuls when one feeds the
263 // other.
TEST_F(StrengthReductionBasicTest,BasicCheckPositionAndReplacement)264 TEST_F(StrengthReductionBasicTest, BasicCheckPositionAndReplacement) {
265 // This is just the preamble to set up the test.
266 const std::vector<const char*> common_text = {
267 // clang-format off
268 "OpCapability Shader",
269 "%1 = OpExtInstImport \"GLSL.std.450\"",
270 "OpMemoryModel Logical GLSL450",
271 "OpEntryPoint Fragment %main \"main\" %gl_FragColor",
272 "OpExecutionMode %main OriginUpperLeft",
273 "OpName %main \"main\"",
274 "OpName %foo_i1_ \"foo(i1;\"",
275 "OpName %n \"n\"",
276 "OpName %gl_FragColor \"gl_FragColor\"",
277 "OpName %param \"param\"",
278 "OpDecorate %gl_FragColor Location 0",
279 "%void = OpTypeVoid",
280 "%3 = OpTypeFunction %void",
281 "%int = OpTypeInt 32 1",
282 "%_ptr_Function_int = OpTypePointer Function %int",
283 "%8 = OpTypeFunction %int %_ptr_Function_int",
284 "%int_256 = OpConstant %int 256",
285 "%int_2 = OpConstant %int 2",
286 "%float = OpTypeFloat 32",
287 "%v4float = OpTypeVector %float 4",
288 "%_ptr_Output_v4float = OpTypePointer Output %v4float",
289 "%gl_FragColor = OpVariable %_ptr_Output_v4float Output",
290 "%float_1 = OpConstant %float 1",
291 "%int_10 = OpConstant %int 10",
292 "%float_0_375 = OpConstant %float 0.375",
293 "%float_0_75 = OpConstant %float 0.75",
294 "%uint = OpTypeInt 32 0",
295 "%uint_8 = OpConstant %uint 8",
296 "%uint_1 = OpConstant %uint 1",
297 "%main = OpFunction %void None %3",
298 "%5 = OpLabel",
299 "%param = OpVariable %_ptr_Function_int Function",
300 "OpStore %param %int_10",
301 "%26 = OpFunctionCall %int %foo_i1_ %param",
302 "%27 = OpConvertSToF %float %26",
303 "%28 = OpFDiv %float %float_1 %27",
304 "%31 = OpCompositeConstruct %v4float %28 %float_0_375 %float_0_75 %float_1",
305 "OpStore %gl_FragColor %31",
306 "OpReturn",
307 "OpFunctionEnd"
308 // clang-format on
309 };
310
311 // This is the real test. The two OpIMul should be replaced. The expected
312 // output is in |foo_after|.
313 const std::vector<const char*> foo_before = {
314 // clang-format off
315 "%foo_i1_ = OpFunction %int None %8",
316 "%n = OpFunctionParameter %_ptr_Function_int",
317 "%11 = OpLabel",
318 "%12 = OpLoad %int %n",
319 "%14 = OpIMul %int %12 %int_256",
320 "%16 = OpIMul %int %14 %int_2",
321 "OpReturnValue %16",
322 "OpFunctionEnd",
323
324 // clang-format on
325 };
326
327 const std::vector<const char*> foo_after = {
328 // clang-format off
329 "%foo_i1_ = OpFunction %int None %8",
330 "%n = OpFunctionParameter %_ptr_Function_int",
331 "%11 = OpLabel",
332 "%12 = OpLoad %int %n",
333 "%33 = OpShiftLeftLogical %int %12 %uint_8",
334 "%34 = OpShiftLeftLogical %int %33 %uint_1",
335 "OpReturnValue %34",
336 "OpFunctionEnd",
337 // clang-format on
338 };
339
340 SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
341 SinglePassRunAndCheck<StrengthReductionPass>(
342 JoinAllInsts(Concat(common_text, foo_before)),
343 JoinAllInsts(Concat(common_text, foo_after)),
344 /* skip_nop = */ true, /* do_validate = */ true);
345 }
346
347 // Test that, when the result of an OpIMul instruction has more than 1 use, and
348 // the instruction is replaced, all of the uses of the results are replace with
349 // the new result.
TEST_F(StrengthReductionBasicTest,BasicTestMultipleReplacements)350 TEST_F(StrengthReductionBasicTest, BasicTestMultipleReplacements) {
351 // This is just the preamble to set up the test.
352 const std::vector<const char*> common_text = {
353 // clang-format off
354 "OpCapability Shader",
355 "%1 = OpExtInstImport \"GLSL.std.450\"",
356 "OpMemoryModel Logical GLSL450",
357 "OpEntryPoint Fragment %main \"main\" %gl_FragColor",
358 "OpExecutionMode %main OriginUpperLeft",
359 "OpName %main \"main\"",
360 "OpName %foo_i1_ \"foo(i1;\"",
361 "OpName %n \"n\"",
362 "OpName %gl_FragColor \"gl_FragColor\"",
363 "OpName %param \"param\"",
364 "OpDecorate %gl_FragColor Location 0",
365 "%void = OpTypeVoid",
366 "%3 = OpTypeFunction %void",
367 "%int = OpTypeInt 32 1",
368 "%_ptr_Function_int = OpTypePointer Function %int",
369 "%8 = OpTypeFunction %int %_ptr_Function_int",
370 "%int_256 = OpConstant %int 256",
371 "%int_2 = OpConstant %int 2",
372 "%float = OpTypeFloat 32",
373 "%v4float = OpTypeVector %float 4",
374 "%_ptr_Output_v4float = OpTypePointer Output %v4float",
375 "%gl_FragColor = OpVariable %_ptr_Output_v4float Output",
376 "%float_1 = OpConstant %float 1",
377 "%int_10 = OpConstant %int 10",
378 "%float_0_375 = OpConstant %float 0.375",
379 "%float_0_75 = OpConstant %float 0.75",
380 "%uint = OpTypeInt 32 0",
381 "%uint_8 = OpConstant %uint 8",
382 "%uint_1 = OpConstant %uint 1",
383 "%main = OpFunction %void None %3",
384 "%5 = OpLabel",
385 "%param = OpVariable %_ptr_Function_int Function",
386 "OpStore %param %int_10",
387 "%26 = OpFunctionCall %int %foo_i1_ %param",
388 "%27 = OpConvertSToF %float %26",
389 "%28 = OpFDiv %float %float_1 %27",
390 "%31 = OpCompositeConstruct %v4float %28 %float_0_375 %float_0_75 %float_1",
391 "OpStore %gl_FragColor %31",
392 "OpReturn",
393 "OpFunctionEnd"
394 // clang-format on
395 };
396
397 // This is the real test. The two OpIMul instructions should be replaced. In
398 // particular, we want to be sure that both uses of %16 are changed to use the
399 // new result.
400 const std::vector<const char*> foo_before = {
401 // clang-format off
402 "%foo_i1_ = OpFunction %int None %8",
403 "%n = OpFunctionParameter %_ptr_Function_int",
404 "%11 = OpLabel",
405 "%12 = OpLoad %int %n",
406 "%14 = OpIMul %int %12 %int_256",
407 "%16 = OpIMul %int %14 %int_2",
408 "%17 = OpIAdd %int %14 %16",
409 "OpReturnValue %17",
410 "OpFunctionEnd",
411
412 // clang-format on
413 };
414
415 const std::vector<const char*> foo_after = {
416 // clang-format off
417 "%foo_i1_ = OpFunction %int None %8",
418 "%n = OpFunctionParameter %_ptr_Function_int",
419 "%11 = OpLabel",
420 "%12 = OpLoad %int %n",
421 "%34 = OpShiftLeftLogical %int %12 %uint_8",
422 "%35 = OpShiftLeftLogical %int %34 %uint_1",
423 "%17 = OpIAdd %int %34 %35",
424 "OpReturnValue %17",
425 "OpFunctionEnd",
426 // clang-format on
427 };
428
429 SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
430 SinglePassRunAndCheck<StrengthReductionPass>(
431 JoinAllInsts(Concat(common_text, foo_before)),
432 JoinAllInsts(Concat(common_text, foo_after)),
433 /* skip_nop = */ true, /* do_validate = */ true);
434 }
435
436 } // namespace
437 } // namespace opt
438 } // namespace spvtools
439