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. 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. 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. 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. 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. 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. 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 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. 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. 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
