1 // Copyright (c) 2018 Google LLC. 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 <iterator> 17 #include <memory> 18 #include <string> 19 #include <vector> 20 21 #include "effcee/effcee.h" 22 #include "gmock/gmock.h" 23 #include "source/opt/loop_descriptor.h" 24 #include "source/opt/loop_fusion.h" 25 #include "test/opt/pass_fixture.h" 26 27 namespace spvtools { 28 namespace opt { 29 namespace { 30 31 using FusionLegalTest = PassTest<::testing::Test>; 32 33 bool Validate(const std::vector<uint32_t>& bin) { 34 spv_target_env target_env = SPV_ENV_UNIVERSAL_1_2; 35 spv_context spvContext = spvContextCreate(target_env); 36 spv_diagnostic diagnostic = nullptr; 37 spv_const_binary_t binary = {bin.data(), bin.size()}; 38 spv_result_t error = spvValidate(spvContext, &binary, &diagnostic); 39 if (error != 0) spvDiagnosticPrint(diagnostic); 40 spvDiagnosticDestroy(diagnostic); 41 spvContextDestroy(spvContext); 42 return error == 0; 43 } 44 45 void Match(const std::string& checks, IRContext* context) { 46 // Silence unused warnings with !defined(SPIRV_EFFCE) 47 (void)checks; 48 49 std::vector<uint32_t> bin; 50 context->module()->ToBinary(&bin, true); 51 EXPECT_TRUE(Validate(bin)); 52 std::string assembly; 53 SpirvTools tools(SPV_ENV_UNIVERSAL_1_2); 54 EXPECT_TRUE( 55 tools.Disassemble(bin, &assembly, SPV_BINARY_TO_TEXT_OPTION_NO_HEADER)) 56 << "Disassembling failed for shader:\n" 57 << assembly << std::endl; 58 auto match_result = effcee::Match(assembly, checks); 59 EXPECT_EQ(effcee::Result::Status::Ok, match_result.status()) 60 << match_result.message() << "\nChecking result:\n" 61 << assembly; 62 } 63 64 /* 65 Generated from the following GLSL + --eliminate-local-multi-store 66 67 #version 440 core 68 void main() { 69 int[10] a; 70 int[10] b; 71 // No dependence, legal 72 for (int i = 0; i < 10; i++) { 73 a[i] = a[i]*2; 74 } 75 for (int i = 0; i < 10; i++) { 76 b[i] = b[i]+2; 77 } 78 } 79 80 */ 81 TEST_F(FusionLegalTest, DifferentArraysInLoops) { 82 std::string text = R"( 83 OpCapability Shader 84 %1 = OpExtInstImport "GLSL.std.450" 85 OpMemoryModel Logical GLSL450 86 OpEntryPoint Fragment %4 "main" 87 OpExecutionMode %4 OriginUpperLeft 88 OpSource GLSL 440 89 OpName %4 "main" 90 OpName %8 "i" 91 OpName %23 "a" 92 OpName %34 "i" 93 OpName %42 "b" 94 %2 = OpTypeVoid 95 %3 = OpTypeFunction %2 96 %6 = OpTypeInt 32 1 97 %7 = OpTypePointer Function %6 98 %9 = OpConstant %6 0 99 %16 = OpConstant %6 10 100 %17 = OpTypeBool 101 %19 = OpTypeInt 32 0 102 %20 = OpConstant %19 10 103 %21 = OpTypeArray %6 %20 104 %22 = OpTypePointer Function %21 105 %28 = OpConstant %6 2 106 %32 = OpConstant %6 1 107 %4 = OpFunction %2 None %3 108 %5 = OpLabel 109 %8 = OpVariable %7 Function 110 %23 = OpVariable %22 Function 111 %34 = OpVariable %7 Function 112 %42 = OpVariable %22 Function 113 OpStore %8 %9 114 OpBranch %10 115 %10 = OpLabel 116 %51 = OpPhi %6 %9 %5 %33 %13 117 OpLoopMerge %12 %13 None 118 OpBranch %14 119 %14 = OpLabel 120 %18 = OpSLessThan %17 %51 %16 121 OpBranchConditional %18 %11 %12 122 %11 = OpLabel 123 %26 = OpAccessChain %7 %23 %51 124 %27 = OpLoad %6 %26 125 %29 = OpIMul %6 %27 %28 126 %30 = OpAccessChain %7 %23 %51 127 OpStore %30 %29 128 OpBranch %13 129 %13 = OpLabel 130 %33 = OpIAdd %6 %51 %32 131 OpStore %8 %33 132 OpBranch %10 133 %12 = OpLabel 134 OpStore %34 %9 135 OpBranch %35 136 %35 = OpLabel 137 %52 = OpPhi %6 %9 %12 %50 %38 138 OpLoopMerge %37 %38 None 139 OpBranch %39 140 %39 = OpLabel 141 %41 = OpSLessThan %17 %52 %16 142 OpBranchConditional %41 %36 %37 143 %36 = OpLabel 144 %45 = OpAccessChain %7 %42 %52 145 %46 = OpLoad %6 %45 146 %47 = OpIAdd %6 %46 %28 147 %48 = OpAccessChain %7 %42 %52 148 OpStore %48 %47 149 OpBranch %38 150 %38 = OpLabel 151 %50 = OpIAdd %6 %52 %32 152 OpStore %34 %50 153 OpBranch %35 154 %37 = OpLabel 155 OpReturn 156 OpFunctionEnd 157 )"; 158 159 std::unique_ptr<IRContext> context = 160 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 161 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 162 Module* module = context->module(); 163 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 164 << text << std::endl; 165 Function& f = *module->begin(); 166 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 167 EXPECT_EQ(ld.NumLoops(), 2u); 168 169 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 170 171 LoopFusion fusion(context.get(), loops[0], loops[1]); 172 173 EXPECT_TRUE(fusion.AreCompatible()); 174 EXPECT_TRUE(fusion.IsLegal()); 175 176 fusion.Fuse(); 177 178 std::string checks = R"( 179 CHECK: [[PHI:%\w+]] = OpPhi 180 CHECK-NEXT: OpLoopMerge 181 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 182 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 183 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 184 CHECK-NEXT: OpStore [[STORE_0]] 185 CHECK-NOT: OpPhi 186 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 187 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 188 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 189 CHECK-NEXT: OpStore [[STORE_1]] 190 )"; 191 192 Match(checks, context.get()); 193 auto& ld_final = *context->GetLoopDescriptor(&f); 194 EXPECT_EQ(ld_final.NumLoops(), 1u); 195 } 196 197 /* 198 Generated from the following GLSL + --eliminate-local-multi-store 199 200 #version 440 core 201 void main() { 202 int[10] a; 203 int[10] b; 204 int[10] c; 205 // Only loads to the same array, legal 206 for (int i = 0; i < 10; i++) { 207 b[i] = a[i]*2; 208 } 209 for (int i = 0; i < 10; i++) { 210 c[i] = a[i]+2; 211 } 212 } 213 214 */ 215 TEST_F(FusionLegalTest, OnlyLoadsToSameArray) { 216 std::string text = R"( 217 OpCapability Shader 218 %1 = OpExtInstImport "GLSL.std.450" 219 OpMemoryModel Logical GLSL450 220 OpEntryPoint Fragment %4 "main" 221 OpExecutionMode %4 OriginUpperLeft 222 OpSource GLSL 440 223 OpName %4 "main" 224 OpName %8 "i" 225 OpName %23 "b" 226 OpName %25 "a" 227 OpName %35 "i" 228 OpName %43 "c" 229 %2 = OpTypeVoid 230 %3 = OpTypeFunction %2 231 %6 = OpTypeInt 32 1 232 %7 = OpTypePointer Function %6 233 %9 = OpConstant %6 0 234 %16 = OpConstant %6 10 235 %17 = OpTypeBool 236 %19 = OpTypeInt 32 0 237 %20 = OpConstant %19 10 238 %21 = OpTypeArray %6 %20 239 %22 = OpTypePointer Function %21 240 %29 = OpConstant %6 2 241 %33 = OpConstant %6 1 242 %4 = OpFunction %2 None %3 243 %5 = OpLabel 244 %8 = OpVariable %7 Function 245 %23 = OpVariable %22 Function 246 %25 = OpVariable %22 Function 247 %35 = OpVariable %7 Function 248 %43 = OpVariable %22 Function 249 OpStore %8 %9 250 OpBranch %10 251 %10 = OpLabel 252 %52 = OpPhi %6 %9 %5 %34 %13 253 OpLoopMerge %12 %13 None 254 OpBranch %14 255 %14 = OpLabel 256 %18 = OpSLessThan %17 %52 %16 257 OpBranchConditional %18 %11 %12 258 %11 = OpLabel 259 %27 = OpAccessChain %7 %25 %52 260 %28 = OpLoad %6 %27 261 %30 = OpIMul %6 %28 %29 262 %31 = OpAccessChain %7 %23 %52 263 OpStore %31 %30 264 OpBranch %13 265 %13 = OpLabel 266 %34 = OpIAdd %6 %52 %33 267 OpStore %8 %34 268 OpBranch %10 269 %12 = OpLabel 270 OpStore %35 %9 271 OpBranch %36 272 %36 = OpLabel 273 %53 = OpPhi %6 %9 %12 %51 %39 274 OpLoopMerge %38 %39 None 275 OpBranch %40 276 %40 = OpLabel 277 %42 = OpSLessThan %17 %53 %16 278 OpBranchConditional %42 %37 %38 279 %37 = OpLabel 280 %46 = OpAccessChain %7 %25 %53 281 %47 = OpLoad %6 %46 282 %48 = OpIAdd %6 %47 %29 283 %49 = OpAccessChain %7 %43 %53 284 OpStore %49 %48 285 OpBranch %39 286 %39 = OpLabel 287 %51 = OpIAdd %6 %53 %33 288 OpStore %35 %51 289 OpBranch %36 290 %38 = OpLabel 291 OpReturn 292 OpFunctionEnd 293 )"; 294 295 std::unique_ptr<IRContext> context = 296 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 297 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 298 Module* module = context->module(); 299 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 300 << text << std::endl; 301 Function& f = *module->begin(); 302 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 303 EXPECT_EQ(ld.NumLoops(), 2u); 304 305 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 306 307 LoopFusion fusion(context.get(), loops[0], loops[1]); 308 309 EXPECT_TRUE(fusion.AreCompatible()); 310 EXPECT_TRUE(fusion.IsLegal()); 311 312 fusion.Fuse(); 313 314 std::string checks = R"( 315 CHECK: [[PHI:%\w+]] = OpPhi 316 CHECK-NEXT: OpLoopMerge 317 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 318 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 319 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 320 CHECK-NEXT: OpStore [[STORE_0]] 321 CHECK-NOT: OpPhi 322 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 323 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 324 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 325 CHECK-NEXT: OpStore [[STORE_1]] 326 )"; 327 328 Match(checks, context.get()); 329 auto& ld_final = *context->GetLoopDescriptor(&f); 330 EXPECT_EQ(ld_final.NumLoops(), 1u); 331 } 332 333 /* 334 Generated from the following GLSL + --eliminate-local-multi-store 335 336 #version 440 core 337 void main() { 338 int[10] a; 339 int[10] b; 340 // No loop-carried dependences, legal 341 for (int i = 0; i < 10; i++) { 342 a[i] = a[i]*2; 343 } 344 for (int i = 0; i < 10; i++) { 345 b[i] = a[i]+2; 346 } 347 } 348 349 */ 350 TEST_F(FusionLegalTest, NoLoopCarriedDependences) { 351 std::string text = R"( 352 OpCapability Shader 353 %1 = OpExtInstImport "GLSL.std.450" 354 OpMemoryModel Logical GLSL450 355 OpEntryPoint Fragment %4 "main" 356 OpExecutionMode %4 OriginUpperLeft 357 OpSource GLSL 440 358 OpName %4 "main" 359 OpName %8 "i" 360 OpName %23 "a" 361 OpName %34 "i" 362 OpName %42 "b" 363 %2 = OpTypeVoid 364 %3 = OpTypeFunction %2 365 %6 = OpTypeInt 32 1 366 %7 = OpTypePointer Function %6 367 %9 = OpConstant %6 0 368 %16 = OpConstant %6 10 369 %17 = OpTypeBool 370 %19 = OpTypeInt 32 0 371 %20 = OpConstant %19 10 372 %21 = OpTypeArray %6 %20 373 %22 = OpTypePointer Function %21 374 %28 = OpConstant %6 2 375 %32 = OpConstant %6 1 376 %4 = OpFunction %2 None %3 377 %5 = OpLabel 378 %8 = OpVariable %7 Function 379 %23 = OpVariable %22 Function 380 %34 = OpVariable %7 Function 381 %42 = OpVariable %22 Function 382 OpStore %8 %9 383 OpBranch %10 384 %10 = OpLabel 385 %51 = OpPhi %6 %9 %5 %33 %13 386 OpLoopMerge %12 %13 None 387 OpBranch %14 388 %14 = OpLabel 389 %18 = OpSLessThan %17 %51 %16 390 OpBranchConditional %18 %11 %12 391 %11 = OpLabel 392 %26 = OpAccessChain %7 %23 %51 393 %27 = OpLoad %6 %26 394 %29 = OpIMul %6 %27 %28 395 %30 = OpAccessChain %7 %23 %51 396 OpStore %30 %29 397 OpBranch %13 398 %13 = OpLabel 399 %33 = OpIAdd %6 %51 %32 400 OpStore %8 %33 401 OpBranch %10 402 %12 = OpLabel 403 OpStore %34 %9 404 OpBranch %35 405 %35 = OpLabel 406 %52 = OpPhi %6 %9 %12 %50 %38 407 OpLoopMerge %37 %38 None 408 OpBranch %39 409 %39 = OpLabel 410 %41 = OpSLessThan %17 %52 %16 411 OpBranchConditional %41 %36 %37 412 %36 = OpLabel 413 %45 = OpAccessChain %7 %23 %52 414 %46 = OpLoad %6 %45 415 %47 = OpIAdd %6 %46 %28 416 %48 = OpAccessChain %7 %42 %52 417 OpStore %48 %47 418 OpBranch %38 419 %38 = OpLabel 420 %50 = OpIAdd %6 %52 %32 421 OpStore %34 %50 422 OpBranch %35 423 %37 = OpLabel 424 OpReturn 425 OpFunctionEnd 426 )"; 427 428 std::unique_ptr<IRContext> context = 429 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 430 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 431 Module* module = context->module(); 432 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 433 << text << std::endl; 434 Function& f = *module->begin(); 435 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 436 EXPECT_EQ(ld.NumLoops(), 2u); 437 438 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 439 440 LoopFusion fusion(context.get(), loops[0], loops[1]); 441 442 EXPECT_TRUE(fusion.AreCompatible()); 443 EXPECT_TRUE(fusion.IsLegal()); 444 445 fusion.Fuse(); 446 447 std::string checks = R"( 448 CHECK: [[PHI:%\w+]] = OpPhi 449 CHECK-NEXT: OpLoopMerge 450 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 451 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 452 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 453 CHECK-NEXT: OpStore [[STORE_0]] 454 CHECK-NOT: OpPhi 455 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 456 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 457 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 458 CHECK-NEXT: OpStore [[STORE_1]] 459 )"; 460 461 Match(checks, context.get()); 462 auto& ld_final = *context->GetLoopDescriptor(&f); 463 EXPECT_EQ(ld_final.NumLoops(), 1u); 464 } 465 466 /* 467 Generated from the following GLSL + --eliminate-local-multi-store 468 469 #version 440 core 470 void main() { 471 int[10] a; 472 int[10] b; 473 int[10] c; 474 // Parallelism inhibiting, but legal. 475 for (int i = 0; i < 10; i++) { 476 a[i] = b[i] + 1; 477 } 478 for (int i = 0; i < 10; i++) { 479 c[i] = a[i] + c[i-1]; 480 } 481 } 482 483 */ 484 TEST_F(FusionLegalTest, ExistingLoopCarriedDependence) { 485 std::string text = R"( 486 OpCapability Shader 487 %1 = OpExtInstImport "GLSL.std.450" 488 OpMemoryModel Logical GLSL450 489 OpEntryPoint Fragment %4 "main" 490 OpExecutionMode %4 OriginUpperLeft 491 OpSource GLSL 440 492 OpName %4 "main" 493 OpName %8 "i" 494 OpName %23 "a" 495 OpName %25 "b" 496 OpName %34 "i" 497 OpName %42 "c" 498 %2 = OpTypeVoid 499 %3 = OpTypeFunction %2 500 %6 = OpTypeInt 32 1 501 %7 = OpTypePointer Function %6 502 %9 = OpConstant %6 0 503 %16 = OpConstant %6 10 504 %17 = OpTypeBool 505 %19 = OpTypeInt 32 0 506 %20 = OpConstant %19 10 507 %21 = OpTypeArray %6 %20 508 %22 = OpTypePointer Function %21 509 %29 = OpConstant %6 1 510 %4 = OpFunction %2 None %3 511 %5 = OpLabel 512 %8 = OpVariable %7 Function 513 %23 = OpVariable %22 Function 514 %25 = OpVariable %22 Function 515 %34 = OpVariable %7 Function 516 %42 = OpVariable %22 Function 517 OpStore %8 %9 518 OpBranch %10 519 %10 = OpLabel 520 %55 = OpPhi %6 %9 %5 %33 %13 521 OpLoopMerge %12 %13 None 522 OpBranch %14 523 %14 = OpLabel 524 %18 = OpSLessThan %17 %55 %16 525 OpBranchConditional %18 %11 %12 526 %11 = OpLabel 527 %27 = OpAccessChain %7 %25 %55 528 %28 = OpLoad %6 %27 529 %30 = OpIAdd %6 %28 %29 530 %31 = OpAccessChain %7 %23 %55 531 OpStore %31 %30 532 OpBranch %13 533 %13 = OpLabel 534 %33 = OpIAdd %6 %55 %29 535 OpStore %8 %33 536 OpBranch %10 537 %12 = OpLabel 538 OpStore %34 %9 539 OpBranch %35 540 %35 = OpLabel 541 %56 = OpPhi %6 %9 %12 %54 %38 542 OpLoopMerge %37 %38 None 543 OpBranch %39 544 %39 = OpLabel 545 %41 = OpSLessThan %17 %56 %16 546 OpBranchConditional %41 %36 %37 547 %36 = OpLabel 548 %45 = OpAccessChain %7 %23 %56 549 %46 = OpLoad %6 %45 550 %48 = OpISub %6 %56 %29 551 %49 = OpAccessChain %7 %42 %48 552 %50 = OpLoad %6 %49 553 %51 = OpIAdd %6 %46 %50 554 %52 = OpAccessChain %7 %42 %56 555 OpStore %52 %51 556 OpBranch %38 557 %38 = OpLabel 558 %54 = OpIAdd %6 %56 %29 559 OpStore %34 %54 560 OpBranch %35 561 %37 = OpLabel 562 OpReturn 563 OpFunctionEnd 564 )"; 565 566 std::unique_ptr<IRContext> context = 567 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 568 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 569 Module* module = context->module(); 570 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 571 << text << std::endl; 572 Function& f = *module->begin(); 573 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 574 EXPECT_EQ(ld.NumLoops(), 2u); 575 576 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 577 578 LoopFusion fusion(context.get(), loops[0], loops[1]); 579 580 EXPECT_TRUE(fusion.AreCompatible()); 581 EXPECT_TRUE(fusion.IsLegal()); 582 583 fusion.Fuse(); 584 585 std::string checks = R"( 586 CHECK: [[PHI:%\w+]] = OpPhi 587 CHECK-NEXT: OpLoopMerge 588 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 589 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 590 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 591 CHECK-NEXT: OpStore [[STORE_0]] 592 CHECK-NOT: OpPhi 593 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 594 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 595 CHECK: [[I_1:%\w+]] = OpISub {{%\w+}} [[PHI]] {{%\w+}} 596 CHECK-NEXT: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] 597 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]] 598 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 599 CHECK-NEXT: OpStore [[STORE_1]] 600 )"; 601 602 Match(checks, context.get()); 603 auto& ld_final = *context->GetLoopDescriptor(&f); 604 EXPECT_EQ(ld_final.NumLoops(), 1u); 605 } 606 607 /* 608 Generated from the following GLSL + --eliminate-local-multi-store 609 610 #version 440 core 611 void main() { 612 int[10] a; 613 int[10] b; 614 int[10] c; 615 // Creates a loop-carried dependence, but negative, so legal 616 for (int i = 0; i < 10; i++) { 617 a[i+1] = b[i] + 1; 618 } 619 for (int i = 0; i < 10; i++) { 620 c[i] = a[i] + 2; 621 } 622 } 623 624 */ 625 TEST_F(FusionLegalTest, NegativeDistanceCreatedRAW) { 626 std::string text = R"( 627 OpCapability Shader 628 %1 = OpExtInstImport "GLSL.std.450" 629 OpMemoryModel Logical GLSL450 630 OpEntryPoint Fragment %4 "main" 631 OpExecutionMode %4 OriginUpperLeft 632 OpSource GLSL 440 633 OpName %4 "main" 634 OpName %8 "i" 635 OpName %23 "a" 636 OpName %27 "b" 637 OpName %35 "i" 638 OpName %43 "c" 639 %2 = OpTypeVoid 640 %3 = OpTypeFunction %2 641 %6 = OpTypeInt 32 1 642 %7 = OpTypePointer Function %6 643 %9 = OpConstant %6 0 644 %16 = OpConstant %6 10 645 %17 = OpTypeBool 646 %19 = OpTypeInt 32 0 647 %20 = OpConstant %19 10 648 %21 = OpTypeArray %6 %20 649 %22 = OpTypePointer Function %21 650 %25 = OpConstant %6 1 651 %48 = OpConstant %6 2 652 %4 = OpFunction %2 None %3 653 %5 = OpLabel 654 %8 = OpVariable %7 Function 655 %23 = OpVariable %22 Function 656 %27 = OpVariable %22 Function 657 %35 = OpVariable %7 Function 658 %43 = OpVariable %22 Function 659 OpStore %8 %9 660 OpBranch %10 661 %10 = OpLabel 662 %53 = OpPhi %6 %9 %5 %34 %13 663 OpLoopMerge %12 %13 None 664 OpBranch %14 665 %14 = OpLabel 666 %18 = OpSLessThan %17 %53 %16 667 OpBranchConditional %18 %11 %12 668 %11 = OpLabel 669 %26 = OpIAdd %6 %53 %25 670 %29 = OpAccessChain %7 %27 %53 671 %30 = OpLoad %6 %29 672 %31 = OpIAdd %6 %30 %25 673 %32 = OpAccessChain %7 %23 %26 674 OpStore %32 %31 675 OpBranch %13 676 %13 = OpLabel 677 %34 = OpIAdd %6 %53 %25 678 OpStore %8 %34 679 OpBranch %10 680 %12 = OpLabel 681 OpStore %35 %9 682 OpBranch %36 683 %36 = OpLabel 684 %54 = OpPhi %6 %9 %12 %52 %39 685 OpLoopMerge %38 %39 None 686 OpBranch %40 687 %40 = OpLabel 688 %42 = OpSLessThan %17 %54 %16 689 OpBranchConditional %42 %37 %38 690 %37 = OpLabel 691 %46 = OpAccessChain %7 %23 %54 692 %47 = OpLoad %6 %46 693 %49 = OpIAdd %6 %47 %48 694 %50 = OpAccessChain %7 %43 %54 695 OpStore %50 %49 696 OpBranch %39 697 %39 = OpLabel 698 %52 = OpIAdd %6 %54 %25 699 OpStore %35 %52 700 OpBranch %36 701 %38 = OpLabel 702 OpReturn 703 OpFunctionEnd 704 )"; 705 706 std::unique_ptr<IRContext> context = 707 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 708 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 709 Module* module = context->module(); 710 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 711 << text << std::endl; 712 Function& f = *module->begin(); 713 714 { 715 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 716 EXPECT_EQ(ld.NumLoops(), 2u); 717 718 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 719 720 LoopFusion fusion(context.get(), loops[0], loops[1]); 721 722 EXPECT_TRUE(fusion.AreCompatible()); 723 EXPECT_TRUE(fusion.IsLegal()); 724 725 fusion.Fuse(); 726 727 std::string checks = R"( 728 CHECK: [[PHI:%\w+]] = OpPhi 729 CHECK-NEXT: OpLoopMerge 730 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}} 731 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 732 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 733 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] 734 CHECK-NEXT: OpStore [[STORE_0]] 735 CHECK-NOT: OpPhi 736 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 737 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 738 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 739 CHECK-NEXT: OpStore [[STORE_1]] 740 )"; 741 742 Match(checks, context.get()); 743 } 744 745 { 746 auto& ld = *context->GetLoopDescriptor(&f); 747 EXPECT_EQ(ld.NumLoops(), 1u); 748 } 749 } 750 751 /* 752 Generated from the following GLSL + --eliminate-local-multi-store 753 754 #version 440 core 755 void main() { 756 int[10] a; 757 int[10] b; 758 int[10] c; 759 // Legal 760 for (int i = 0; i < 10; i++) { 761 a[i+1] = b[i] + 1; 762 } 763 for (int i = 0; i < 10; i++) { 764 c[i] = a[i+1] + 2; 765 } 766 } 767 768 */ 769 TEST_F(FusionLegalTest, NoLoopCarriedDependencesAdjustedIndex) { 770 std::string text = R"( 771 OpCapability Shader 772 %1 = OpExtInstImport "GLSL.std.450" 773 OpMemoryModel Logical GLSL450 774 OpEntryPoint Fragment %4 "main" 775 OpExecutionMode %4 OriginUpperLeft 776 OpSource GLSL 440 777 OpName %4 "main" 778 OpName %8 "i" 779 OpName %23 "a" 780 OpName %27 "b" 781 OpName %35 "i" 782 OpName %43 "c" 783 %2 = OpTypeVoid 784 %3 = OpTypeFunction %2 785 %6 = OpTypeInt 32 1 786 %7 = OpTypePointer Function %6 787 %9 = OpConstant %6 0 788 %16 = OpConstant %6 10 789 %17 = OpTypeBool 790 %19 = OpTypeInt 32 0 791 %20 = OpConstant %19 10 792 %21 = OpTypeArray %6 %20 793 %22 = OpTypePointer Function %21 794 %25 = OpConstant %6 1 795 %49 = OpConstant %6 2 796 %4 = OpFunction %2 None %3 797 %5 = OpLabel 798 %8 = OpVariable %7 Function 799 %23 = OpVariable %22 Function 800 %27 = OpVariable %22 Function 801 %35 = OpVariable %7 Function 802 %43 = OpVariable %22 Function 803 OpStore %8 %9 804 OpBranch %10 805 %10 = OpLabel 806 %54 = OpPhi %6 %9 %5 %34 %13 807 OpLoopMerge %12 %13 None 808 OpBranch %14 809 %14 = OpLabel 810 %18 = OpSLessThan %17 %54 %16 811 OpBranchConditional %18 %11 %12 812 %11 = OpLabel 813 %26 = OpIAdd %6 %54 %25 814 %29 = OpAccessChain %7 %27 %54 815 %30 = OpLoad %6 %29 816 %31 = OpIAdd %6 %30 %25 817 %32 = OpAccessChain %7 %23 %26 818 OpStore %32 %31 819 OpBranch %13 820 %13 = OpLabel 821 %34 = OpIAdd %6 %54 %25 822 OpStore %8 %34 823 OpBranch %10 824 %12 = OpLabel 825 OpStore %35 %9 826 OpBranch %36 827 %36 = OpLabel 828 %55 = OpPhi %6 %9 %12 %53 %39 829 OpLoopMerge %38 %39 None 830 OpBranch %40 831 %40 = OpLabel 832 %42 = OpSLessThan %17 %55 %16 833 OpBranchConditional %42 %37 %38 834 %37 = OpLabel 835 %46 = OpIAdd %6 %55 %25 836 %47 = OpAccessChain %7 %23 %46 837 %48 = OpLoad %6 %47 838 %50 = OpIAdd %6 %48 %49 839 %51 = OpAccessChain %7 %43 %55 840 OpStore %51 %50 841 OpBranch %39 842 %39 = OpLabel 843 %53 = OpIAdd %6 %55 %25 844 OpStore %35 %53 845 OpBranch %36 846 %38 = OpLabel 847 OpReturn 848 OpFunctionEnd 849 )"; 850 851 std::unique_ptr<IRContext> context = 852 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 853 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 854 Module* module = context->module(); 855 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 856 << text << std::endl; 857 Function& f = *module->begin(); 858 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 859 EXPECT_EQ(ld.NumLoops(), 2u); 860 861 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 862 863 LoopFusion fusion(context.get(), loops[0], loops[1]); 864 865 EXPECT_TRUE(fusion.AreCompatible()); 866 EXPECT_TRUE(fusion.IsLegal()); 867 868 fusion.Fuse(); 869 870 std::string checks = R"( 871 CHECK: [[PHI:%\w+]] = OpPhi 872 CHECK-NEXT: OpLoopMerge 873 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}} 874 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 875 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 876 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] 877 CHECK-NEXT: OpStore [[STORE_0]] 878 CHECK-NOT: OpPhi 879 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}} 880 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] 881 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 882 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 883 CHECK-NEXT: OpStore [[STORE_1]] 884 )"; 885 886 Match(checks, context.get()); 887 auto& ld_final = *context->GetLoopDescriptor(&f); 888 EXPECT_EQ(ld_final.NumLoops(), 1u); 889 } 890 891 /* 892 Generated from the following GLSL + --eliminate-local-multi-store 893 894 #version 440 core 895 void main() { 896 int[10] a; 897 int[10] b; 898 int[10] c; 899 // Legal, independent locations in |a|, SIV 900 for (int i = 0; i < 10; i++) { 901 a[2*i+1] = b[i] + 1; 902 } 903 for (int i = 0; i < 10; i++) { 904 c[i] = a[2*i] + 2; 905 } 906 } 907 908 */ 909 TEST_F(FusionLegalTest, IndependentSIV) { 910 std::string text = R"( 911 OpCapability Shader 912 %1 = OpExtInstImport "GLSL.std.450" 913 OpMemoryModel Logical GLSL450 914 OpEntryPoint Fragment %4 "main" 915 OpExecutionMode %4 OriginUpperLeft 916 OpSource GLSL 440 917 OpName %4 "main" 918 OpName %8 "i" 919 OpName %23 "a" 920 OpName %29 "b" 921 OpName %37 "i" 922 OpName %45 "c" 923 %2 = OpTypeVoid 924 %3 = OpTypeFunction %2 925 %6 = OpTypeInt 32 1 926 %7 = OpTypePointer Function %6 927 %9 = OpConstant %6 0 928 %16 = OpConstant %6 10 929 %17 = OpTypeBool 930 %19 = OpTypeInt 32 0 931 %20 = OpConstant %19 10 932 %21 = OpTypeArray %6 %20 933 %22 = OpTypePointer Function %21 934 %24 = OpConstant %6 2 935 %27 = OpConstant %6 1 936 %4 = OpFunction %2 None %3 937 %5 = OpLabel 938 %8 = OpVariable %7 Function 939 %23 = OpVariable %22 Function 940 %29 = OpVariable %22 Function 941 %37 = OpVariable %7 Function 942 %45 = OpVariable %22 Function 943 OpStore %8 %9 944 OpBranch %10 945 %10 = OpLabel 946 %55 = OpPhi %6 %9 %5 %36 %13 947 OpLoopMerge %12 %13 None 948 OpBranch %14 949 %14 = OpLabel 950 %18 = OpSLessThan %17 %55 %16 951 OpBranchConditional %18 %11 %12 952 %11 = OpLabel 953 %26 = OpIMul %6 %24 %55 954 %28 = OpIAdd %6 %26 %27 955 %31 = OpAccessChain %7 %29 %55 956 %32 = OpLoad %6 %31 957 %33 = OpIAdd %6 %32 %27 958 %34 = OpAccessChain %7 %23 %28 959 OpStore %34 %33 960 OpBranch %13 961 %13 = OpLabel 962 %36 = OpIAdd %6 %55 %27 963 OpStore %8 %36 964 OpBranch %10 965 %12 = OpLabel 966 OpStore %37 %9 967 OpBranch %38 968 %38 = OpLabel 969 %56 = OpPhi %6 %9 %12 %54 %41 970 OpLoopMerge %40 %41 None 971 OpBranch %42 972 %42 = OpLabel 973 %44 = OpSLessThan %17 %56 %16 974 OpBranchConditional %44 %39 %40 975 %39 = OpLabel 976 %48 = OpIMul %6 %24 %56 977 %49 = OpAccessChain %7 %23 %48 978 %50 = OpLoad %6 %49 979 %51 = OpIAdd %6 %50 %24 980 %52 = OpAccessChain %7 %45 %56 981 OpStore %52 %51 982 OpBranch %41 983 %41 = OpLabel 984 %54 = OpIAdd %6 %56 %27 985 OpStore %37 %54 986 OpBranch %38 987 %40 = OpLabel 988 OpReturn 989 OpFunctionEnd 990 )"; 991 992 std::unique_ptr<IRContext> context = 993 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 994 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 995 Module* module = context->module(); 996 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 997 << text << std::endl; 998 Function& f = *module->begin(); 999 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 1000 EXPECT_EQ(ld.NumLoops(), 2u); 1001 1002 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 1003 1004 LoopFusion fusion(context.get(), loops[0], loops[1]); 1005 1006 EXPECT_TRUE(fusion.AreCompatible()); 1007 EXPECT_TRUE(fusion.IsLegal()); 1008 1009 fusion.Fuse(); 1010 1011 std::string checks = R"( 1012 CHECK: [[PHI:%\w+]] = OpPhi 1013 CHECK-NEXT: OpLoopMerge 1014 CHECK: [[I_2:%\w+]] = OpIMul {{%\w+}} {{%\w+}} [[PHI]] 1015 CHECK-NEXT: [[I_2_1:%\w+]] = OpIAdd {{%\w+}} [[I_2]] {{%\w+}} 1016 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1017 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 1018 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_2_1]] 1019 CHECK-NEXT: OpStore [[STORE_0]] 1020 CHECK-NOT: OpPhi 1021 CHECK: [[I_2:%\w+]] = OpIMul {{%\w+}} {{%\w+}} [[PHI]] 1022 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_2]] 1023 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 1024 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1025 CHECK-NEXT: OpStore [[STORE_1]] 1026 )"; 1027 1028 Match(checks, context.get()); 1029 auto& ld_final = *context->GetLoopDescriptor(&f); 1030 EXPECT_EQ(ld_final.NumLoops(), 1u); 1031 } 1032 1033 /* 1034 Generated from the following GLSL + --eliminate-local-multi-store 1035 1036 #version 440 core 1037 void main() { 1038 int[10] a; 1039 int[10] b; 1040 int[10] c; 1041 // Legal, independent locations in |a|, ZIV 1042 for (int i = 0; i < 10; i++) { 1043 a[1] = b[i] + 1; 1044 } 1045 for (int i = 0; i < 10; i++) { 1046 c[i] = a[9] + 2; 1047 } 1048 } 1049 1050 */ 1051 TEST_F(FusionLegalTest, IndependentZIV) { 1052 std::string text = R"( 1053 OpCapability Shader 1054 %1 = OpExtInstImport "GLSL.std.450" 1055 OpMemoryModel Logical GLSL450 1056 OpEntryPoint Fragment %4 "main" 1057 OpExecutionMode %4 OriginUpperLeft 1058 OpSource GLSL 440 1059 OpName %4 "main" 1060 OpName %8 "i" 1061 OpName %23 "a" 1062 OpName %25 "b" 1063 OpName %33 "i" 1064 OpName %41 "c" 1065 %2 = OpTypeVoid 1066 %3 = OpTypeFunction %2 1067 %6 = OpTypeInt 32 1 1068 %7 = OpTypePointer Function %6 1069 %9 = OpConstant %6 0 1070 %16 = OpConstant %6 10 1071 %17 = OpTypeBool 1072 %19 = OpTypeInt 32 0 1073 %20 = OpConstant %19 10 1074 %21 = OpTypeArray %6 %20 1075 %22 = OpTypePointer Function %21 1076 %24 = OpConstant %6 1 1077 %43 = OpConstant %6 9 1078 %46 = OpConstant %6 2 1079 %4 = OpFunction %2 None %3 1080 %5 = OpLabel 1081 %8 = OpVariable %7 Function 1082 %23 = OpVariable %22 Function 1083 %25 = OpVariable %22 Function 1084 %33 = OpVariable %7 Function 1085 %41 = OpVariable %22 Function 1086 OpStore %8 %9 1087 OpBranch %10 1088 %10 = OpLabel 1089 %51 = OpPhi %6 %9 %5 %32 %13 1090 OpLoopMerge %12 %13 None 1091 OpBranch %14 1092 %14 = OpLabel 1093 %18 = OpSLessThan %17 %51 %16 1094 OpBranchConditional %18 %11 %12 1095 %11 = OpLabel 1096 %27 = OpAccessChain %7 %25 %51 1097 %28 = OpLoad %6 %27 1098 %29 = OpIAdd %6 %28 %24 1099 %30 = OpAccessChain %7 %23 %24 1100 OpStore %30 %29 1101 OpBranch %13 1102 %13 = OpLabel 1103 %32 = OpIAdd %6 %51 %24 1104 OpStore %8 %32 1105 OpBranch %10 1106 %12 = OpLabel 1107 OpStore %33 %9 1108 OpBranch %34 1109 %34 = OpLabel 1110 %52 = OpPhi %6 %9 %12 %50 %37 1111 OpLoopMerge %36 %37 None 1112 OpBranch %38 1113 %38 = OpLabel 1114 %40 = OpSLessThan %17 %52 %16 1115 OpBranchConditional %40 %35 %36 1116 %35 = OpLabel 1117 %44 = OpAccessChain %7 %23 %43 1118 %45 = OpLoad %6 %44 1119 %47 = OpIAdd %6 %45 %46 1120 %48 = OpAccessChain %7 %41 %52 1121 OpStore %48 %47 1122 OpBranch %37 1123 %37 = OpLabel 1124 %50 = OpIAdd %6 %52 %24 1125 OpStore %33 %50 1126 OpBranch %34 1127 %36 = OpLabel 1128 OpReturn 1129 OpFunctionEnd 1130 )"; 1131 1132 std::unique_ptr<IRContext> context = 1133 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 1134 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 1135 Module* module = context->module(); 1136 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 1137 << text << std::endl; 1138 Function& f = *module->begin(); 1139 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 1140 EXPECT_EQ(ld.NumLoops(), 2u); 1141 1142 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 1143 1144 LoopFusion fusion(context.get(), loops[0], loops[1]); 1145 1146 EXPECT_TRUE(fusion.AreCompatible()); 1147 EXPECT_TRUE(fusion.IsLegal()); 1148 1149 fusion.Fuse(); 1150 1151 std::string checks = R"( 1152 CHECK: [[PHI:%\w+]] = OpPhi 1153 CHECK-NEXT: OpLoopMerge 1154 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1155 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 1156 CHECK-NOT: OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1157 CHECK: OpStore 1158 CHECK-NOT: OpPhi 1159 CHECK-NOT: OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1160 CHECK: OpLoad 1161 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1162 CHECK-NEXT: OpStore [[STORE_1]] 1163 )"; 1164 1165 Match(checks, context.get()); 1166 auto& ld_final = *context->GetLoopDescriptor(&f); 1167 EXPECT_EQ(ld_final.NumLoops(), 1u); 1168 } 1169 1170 /* 1171 Generated from the following GLSL + --eliminate-local-multi-store 1172 1173 #version 440 core 1174 void main() { 1175 int[20] a; 1176 int[10] b; 1177 int[10] c; 1178 // Legal, non-overlapping sections in |a| 1179 for (int i = 0; i < 10; i++) { 1180 a[i] = b[i] + 1; 1181 } 1182 for (int i = 0; i < 10; i++) { 1183 c[i] = a[i+10] + 2; 1184 } 1185 } 1186 1187 */ 1188 TEST_F(FusionLegalTest, NonOverlappingAccesses) { 1189 std::string text = R"( 1190 OpCapability Shader 1191 %1 = OpExtInstImport "GLSL.std.450" 1192 OpMemoryModel Logical GLSL450 1193 OpEntryPoint Fragment %4 "main" 1194 OpExecutionMode %4 OriginUpperLeft 1195 OpSource GLSL 440 1196 OpName %4 "main" 1197 OpName %8 "i" 1198 OpName %23 "a" 1199 OpName %28 "b" 1200 OpName %37 "i" 1201 OpName %45 "c" 1202 %2 = OpTypeVoid 1203 %3 = OpTypeFunction %2 1204 %6 = OpTypeInt 32 1 1205 %7 = OpTypePointer Function %6 1206 %9 = OpConstant %6 0 1207 %16 = OpConstant %6 10 1208 %17 = OpTypeBool 1209 %19 = OpTypeInt 32 0 1210 %20 = OpConstant %19 20 1211 %21 = OpTypeArray %6 %20 1212 %22 = OpTypePointer Function %21 1213 %25 = OpConstant %19 10 1214 %26 = OpTypeArray %6 %25 1215 %27 = OpTypePointer Function %26 1216 %32 = OpConstant %6 1 1217 %51 = OpConstant %6 2 1218 %4 = OpFunction %2 None %3 1219 %5 = OpLabel 1220 %8 = OpVariable %7 Function 1221 %23 = OpVariable %22 Function 1222 %28 = OpVariable %27 Function 1223 %37 = OpVariable %7 Function 1224 %45 = OpVariable %27 Function 1225 OpStore %8 %9 1226 OpBranch %10 1227 %10 = OpLabel 1228 %56 = OpPhi %6 %9 %5 %36 %13 1229 OpLoopMerge %12 %13 None 1230 OpBranch %14 1231 %14 = OpLabel 1232 %18 = OpSLessThan %17 %56 %16 1233 OpBranchConditional %18 %11 %12 1234 %11 = OpLabel 1235 %30 = OpAccessChain %7 %28 %56 1236 %31 = OpLoad %6 %30 1237 %33 = OpIAdd %6 %31 %32 1238 %34 = OpAccessChain %7 %23 %56 1239 OpStore %34 %33 1240 OpBranch %13 1241 %13 = OpLabel 1242 %36 = OpIAdd %6 %56 %32 1243 OpStore %8 %36 1244 OpBranch %10 1245 %12 = OpLabel 1246 OpStore %37 %9 1247 OpBranch %38 1248 %38 = OpLabel 1249 %57 = OpPhi %6 %9 %12 %55 %41 1250 OpLoopMerge %40 %41 None 1251 OpBranch %42 1252 %42 = OpLabel 1253 %44 = OpSLessThan %17 %57 %16 1254 OpBranchConditional %44 %39 %40 1255 %39 = OpLabel 1256 %48 = OpIAdd %6 %57 %16 1257 %49 = OpAccessChain %7 %23 %48 1258 %50 = OpLoad %6 %49 1259 %52 = OpIAdd %6 %50 %51 1260 %53 = OpAccessChain %7 %45 %57 1261 OpStore %53 %52 1262 OpBranch %41 1263 %41 = OpLabel 1264 %55 = OpIAdd %6 %57 %32 1265 OpStore %37 %55 1266 OpBranch %38 1267 %40 = OpLabel 1268 OpReturn 1269 OpFunctionEnd 1270 )"; 1271 1272 std::unique_ptr<IRContext> context = 1273 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 1274 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 1275 Module* module = context->module(); 1276 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 1277 << text << std::endl; 1278 Function& f = *module->begin(); 1279 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 1280 EXPECT_EQ(ld.NumLoops(), 2u); 1281 1282 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 1283 1284 LoopFusion fusion(context.get(), loops[0], loops[1]); 1285 1286 EXPECT_TRUE(fusion.AreCompatible()); 1287 EXPECT_TRUE(fusion.IsLegal()); 1288 1289 fusion.Fuse(); 1290 1291 std::string checks = R"( 1292 CHECK: [[PHI:%\w+]] = OpPhi 1293 CHECK-NEXT: OpLoopMerge 1294 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1295 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 1296 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1297 CHECK-NOT: OpPhi 1298 CHECK: [[I_10:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}} 1299 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_10]] 1300 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 1301 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1302 CHECK-NEXT: OpStore [[STORE_1]] 1303 )"; 1304 1305 Match(checks, context.get()); 1306 1307 auto& ld_final = *context->GetLoopDescriptor(&f); 1308 EXPECT_EQ(ld_final.NumLoops(), 1u); 1309 } 1310 1311 /* 1312 Generated from the following GLSL + --eliminate-local-multi-store 1313 1314 #version 440 core 1315 void main() { 1316 int[10] a; 1317 int[10] b; 1318 int[10] c; 1319 // Legal, 3 adjacent loops 1320 for (int i = 0; i < 10; i++) { 1321 a[i] = b[i] + 1; 1322 } 1323 for (int i = 0; i < 10; i++) { 1324 c[i] = a[i] + 2; 1325 } 1326 for (int i = 0; i < 10; i++) { 1327 b[i] = c[i] + 10; 1328 } 1329 } 1330 1331 */ 1332 TEST_F(FusionLegalTest, AdjacentLoops) { 1333 std::string text = R"( 1334 OpCapability Shader 1335 %1 = OpExtInstImport "GLSL.std.450" 1336 OpMemoryModel Logical GLSL450 1337 OpEntryPoint Fragment %4 "main" 1338 OpExecutionMode %4 OriginUpperLeft 1339 OpSource GLSL 440 1340 OpName %4 "main" 1341 OpName %8 "i" 1342 OpName %23 "a" 1343 OpName %25 "b" 1344 OpName %34 "i" 1345 OpName %42 "c" 1346 OpName %52 "i" 1347 %2 = OpTypeVoid 1348 %3 = OpTypeFunction %2 1349 %6 = OpTypeInt 32 1 1350 %7 = OpTypePointer Function %6 1351 %9 = OpConstant %6 0 1352 %16 = OpConstant %6 10 1353 %17 = OpTypeBool 1354 %19 = OpTypeInt 32 0 1355 %20 = OpConstant %19 10 1356 %21 = OpTypeArray %6 %20 1357 %22 = OpTypePointer Function %21 1358 %29 = OpConstant %6 1 1359 %47 = OpConstant %6 2 1360 %4 = OpFunction %2 None %3 1361 %5 = OpLabel 1362 %8 = OpVariable %7 Function 1363 %23 = OpVariable %22 Function 1364 %25 = OpVariable %22 Function 1365 %34 = OpVariable %7 Function 1366 %42 = OpVariable %22 Function 1367 %52 = OpVariable %7 Function 1368 OpStore %8 %9 1369 OpBranch %10 1370 %10 = OpLabel 1371 %68 = OpPhi %6 %9 %5 %33 %13 1372 OpLoopMerge %12 %13 None 1373 OpBranch %14 1374 %14 = OpLabel 1375 %18 = OpSLessThan %17 %68 %16 1376 OpBranchConditional %18 %11 %12 1377 %11 = OpLabel 1378 %27 = OpAccessChain %7 %25 %68 1379 %28 = OpLoad %6 %27 1380 %30 = OpIAdd %6 %28 %29 1381 %31 = OpAccessChain %7 %23 %68 1382 OpStore %31 %30 1383 OpBranch %13 1384 %13 = OpLabel 1385 %33 = OpIAdd %6 %68 %29 1386 OpStore %8 %33 1387 OpBranch %10 1388 %12 = OpLabel 1389 OpStore %34 %9 1390 OpBranch %35 1391 %35 = OpLabel 1392 %69 = OpPhi %6 %9 %12 %51 %38 1393 OpLoopMerge %37 %38 None 1394 OpBranch %39 1395 %39 = OpLabel 1396 %41 = OpSLessThan %17 %69 %16 1397 OpBranchConditional %41 %36 %37 1398 %36 = OpLabel 1399 %45 = OpAccessChain %7 %23 %69 1400 %46 = OpLoad %6 %45 1401 %48 = OpIAdd %6 %46 %47 1402 %49 = OpAccessChain %7 %42 %69 1403 OpStore %49 %48 1404 OpBranch %38 1405 %38 = OpLabel 1406 %51 = OpIAdd %6 %69 %29 1407 OpStore %34 %51 1408 OpBranch %35 1409 %37 = OpLabel 1410 OpStore %52 %9 1411 OpBranch %53 1412 %53 = OpLabel 1413 %70 = OpPhi %6 %9 %37 %67 %56 1414 OpLoopMerge %55 %56 None 1415 OpBranch %57 1416 %57 = OpLabel 1417 %59 = OpSLessThan %17 %70 %16 1418 OpBranchConditional %59 %54 %55 1419 %54 = OpLabel 1420 %62 = OpAccessChain %7 %42 %70 1421 %63 = OpLoad %6 %62 1422 %64 = OpIAdd %6 %63 %16 1423 %65 = OpAccessChain %7 %25 %70 1424 OpStore %65 %64 1425 OpBranch %56 1426 %56 = OpLabel 1427 %67 = OpIAdd %6 %70 %29 1428 OpStore %52 %67 1429 OpBranch %53 1430 %55 = OpLabel 1431 OpReturn 1432 OpFunctionEnd 1433 )"; 1434 1435 std::unique_ptr<IRContext> context = 1436 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 1437 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 1438 Module* module = context->module(); 1439 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 1440 << text << std::endl; 1441 Function& f = *module->begin(); 1442 1443 { 1444 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 1445 EXPECT_EQ(ld.NumLoops(), 3u); 1446 1447 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 1448 1449 LoopFusion fusion(context.get(), loops[1], loops[2]); 1450 1451 EXPECT_TRUE(fusion.AreCompatible()); 1452 EXPECT_TRUE(fusion.IsLegal()); 1453 1454 fusion.Fuse(); 1455 } 1456 1457 std::string checks = R"( 1458 CHECK: [[PHI_0:%\w+]] = OpPhi 1459 CHECK-NEXT: OpLoopMerge 1460 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 1461 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 1462 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 1463 CHECK-NEXT: OpStore [[STORE_0]] 1464 CHECK: [[PHI_1:%\w+]] = OpPhi 1465 CHECK-NEXT: OpLoopMerge 1466 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]] 1467 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 1468 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]] 1469 CHECK-NEXT: OpStore [[STORE_1]] 1470 CHECK-NOT: OpPhi 1471 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]] 1472 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]] 1473 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]] 1474 CHECK-NEXT: OpStore [[STORE_2]] 1475 )"; 1476 1477 Match(checks, context.get()); 1478 1479 { 1480 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 1481 EXPECT_EQ(ld.NumLoops(), 2u); 1482 1483 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 1484 1485 LoopFusion fusion(context.get(), loops[0], loops[1]); 1486 1487 EXPECT_TRUE(fusion.AreCompatible()); 1488 EXPECT_TRUE(fusion.IsLegal()); 1489 1490 fusion.Fuse(); 1491 } 1492 1493 std::string checks_ = R"( 1494 CHECK: [[PHI:%\w+]] = OpPhi 1495 CHECK-NEXT: OpLoopMerge 1496 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1497 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 1498 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1499 CHECK-NEXT: OpStore [[STORE_0]] 1500 CHECK-NOT: OpPhi 1501 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1502 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 1503 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1504 CHECK-NEXT: OpStore [[STORE_1]] 1505 CHECK-NOT: OpPhi 1506 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1507 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]] 1508 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 1509 CHECK-NEXT: OpStore [[STORE_2]] 1510 )"; 1511 1512 Match(checks_, context.get()); 1513 1514 auto& ld_final = *context->GetLoopDescriptor(&f); 1515 EXPECT_EQ(ld_final.NumLoops(), 1u); 1516 } 1517 1518 /* 1519 Generated from the following GLSL + --eliminate-local-multi-store 1520 1521 #version 440 core 1522 void main() { 1523 int[10][10] a; 1524 int[10][10] b; 1525 int[10][10] c; 1526 // Legal inner loop fusion 1527 for (int i = 0; i < 10; i++) { 1528 for (int j = 0; j < 10; j++) { 1529 c[i][j] = a[i][j] + 2; 1530 } 1531 for (int j = 0; j < 10; j++) { 1532 b[i][j] = c[i][j] + 10; 1533 } 1534 } 1535 } 1536 1537 */ 1538 TEST_F(FusionLegalTest, InnerLoopFusion) { 1539 std::string text = R"( 1540 OpCapability Shader 1541 %1 = OpExtInstImport "GLSL.std.450" 1542 OpMemoryModel Logical GLSL450 1543 OpEntryPoint Fragment %4 "main" 1544 OpExecutionMode %4 OriginUpperLeft 1545 OpSource GLSL 440 1546 OpName %4 "main" 1547 OpName %8 "i" 1548 OpName %19 "j" 1549 OpName %32 "c" 1550 OpName %35 "a" 1551 OpName %46 "j" 1552 OpName %54 "b" 1553 %2 = OpTypeVoid 1554 %3 = OpTypeFunction %2 1555 %6 = OpTypeInt 32 1 1556 %7 = OpTypePointer Function %6 1557 %9 = OpConstant %6 0 1558 %16 = OpConstant %6 10 1559 %17 = OpTypeBool 1560 %27 = OpTypeInt 32 0 1561 %28 = OpConstant %27 10 1562 %29 = OpTypeArray %6 %28 1563 %30 = OpTypeArray %29 %28 1564 %31 = OpTypePointer Function %30 1565 %40 = OpConstant %6 2 1566 %44 = OpConstant %6 1 1567 %4 = OpFunction %2 None %3 1568 %5 = OpLabel 1569 %8 = OpVariable %7 Function 1570 %19 = OpVariable %7 Function 1571 %32 = OpVariable %31 Function 1572 %35 = OpVariable %31 Function 1573 %46 = OpVariable %7 Function 1574 %54 = OpVariable %31 Function 1575 OpStore %8 %9 1576 OpBranch %10 1577 %10 = OpLabel 1578 %67 = OpPhi %6 %9 %5 %66 %13 1579 OpLoopMerge %12 %13 None 1580 OpBranch %14 1581 %14 = OpLabel 1582 %18 = OpSLessThan %17 %67 %16 1583 OpBranchConditional %18 %11 %12 1584 %11 = OpLabel 1585 OpStore %19 %9 1586 OpBranch %20 1587 %20 = OpLabel 1588 %68 = OpPhi %6 %9 %11 %45 %23 1589 OpLoopMerge %22 %23 None 1590 OpBranch %24 1591 %24 = OpLabel 1592 %26 = OpSLessThan %17 %68 %16 1593 OpBranchConditional %26 %21 %22 1594 %21 = OpLabel 1595 %38 = OpAccessChain %7 %35 %67 %68 1596 %39 = OpLoad %6 %38 1597 %41 = OpIAdd %6 %39 %40 1598 %42 = OpAccessChain %7 %32 %67 %68 1599 OpStore %42 %41 1600 OpBranch %23 1601 %23 = OpLabel 1602 %45 = OpIAdd %6 %68 %44 1603 OpStore %19 %45 1604 OpBranch %20 1605 %22 = OpLabel 1606 OpStore %46 %9 1607 OpBranch %47 1608 %47 = OpLabel 1609 %69 = OpPhi %6 %9 %22 %64 %50 1610 OpLoopMerge %49 %50 None 1611 OpBranch %51 1612 %51 = OpLabel 1613 %53 = OpSLessThan %17 %69 %16 1614 OpBranchConditional %53 %48 %49 1615 %48 = OpLabel 1616 %59 = OpAccessChain %7 %32 %67 %69 1617 %60 = OpLoad %6 %59 1618 %61 = OpIAdd %6 %60 %16 1619 %62 = OpAccessChain %7 %54 %67 %69 1620 OpStore %62 %61 1621 OpBranch %50 1622 %50 = OpLabel 1623 %64 = OpIAdd %6 %69 %44 1624 OpStore %46 %64 1625 OpBranch %47 1626 %49 = OpLabel 1627 OpBranch %13 1628 %13 = OpLabel 1629 %66 = OpIAdd %6 %67 %44 1630 OpStore %8 %66 1631 OpBranch %10 1632 %12 = OpLabel 1633 OpReturn 1634 OpFunctionEnd 1635 )"; 1636 1637 std::unique_ptr<IRContext> context = 1638 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 1639 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 1640 Module* module = context->module(); 1641 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 1642 << text << std::endl; 1643 Function& f = *module->begin(); 1644 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 1645 EXPECT_EQ(ld.NumLoops(), 3u); 1646 1647 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 1648 1649 auto loop_0 = loops[0]; 1650 auto loop_1 = loops[1]; 1651 auto loop_2 = loops[2]; 1652 1653 { 1654 LoopFusion fusion(context.get(), loop_0, loop_1); 1655 EXPECT_FALSE(fusion.AreCompatible()); 1656 } 1657 1658 { 1659 LoopFusion fusion(context.get(), loop_0, loop_2); 1660 EXPECT_FALSE(fusion.AreCompatible()); 1661 } 1662 1663 { 1664 LoopFusion fusion(context.get(), loop_1, loop_2); 1665 EXPECT_TRUE(fusion.AreCompatible()); 1666 EXPECT_TRUE(fusion.IsLegal()); 1667 1668 fusion.Fuse(); 1669 } 1670 1671 std::string checks = R"( 1672 CHECK: [[PHI_0:%\w+]] = OpPhi 1673 CHECK-NEXT: OpLoopMerge 1674 CHECK: [[PHI_1:%\w+]] = OpPhi 1675 CHECK-NEXT: OpLoopMerge 1676 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1677 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 1678 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1679 CHECK-NEXT: OpStore [[STORE_0]] 1680 CHECK-NOT: OpPhi 1681 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1682 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 1683 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1684 CHECK-NEXT: OpStore [[STORE_1]] 1685 )"; 1686 1687 Match(checks, context.get()); 1688 1689 auto& ld_final = *context->GetLoopDescriptor(&f); 1690 EXPECT_EQ(ld_final.NumLoops(), 2u); 1691 } 1692 1693 /* 1694 Generated from the following GLSL + --eliminate-local-multi-store 1695 1696 // 12 1697 #version 440 core 1698 void main() { 1699 int[10][10] a; 1700 int[10][10] b; 1701 int[10][10] c; 1702 // Legal both 1703 for (int i = 0; i < 10; i++) { 1704 for (int j = 0; j < 10; j++) { 1705 c[i][j] = a[i][j] + 2; 1706 } 1707 } 1708 for (int i = 0; i < 10; i++) { 1709 for (int j = 0; j < 10; j++) { 1710 b[i][j] = c[i][j] + 10; 1711 } 1712 } 1713 } 1714 1715 */ 1716 TEST_F(FusionLegalTest, OuterAndInnerLoop) { 1717 std::string text = R"( 1718 OpCapability Shader 1719 %1 = OpExtInstImport "GLSL.std.450" 1720 OpMemoryModel Logical GLSL450 1721 OpEntryPoint Fragment %4 "main" 1722 OpExecutionMode %4 OriginUpperLeft 1723 OpSource GLSL 440 1724 OpName %4 "main" 1725 OpName %8 "i" 1726 OpName %19 "j" 1727 OpName %32 "c" 1728 OpName %35 "a" 1729 OpName %48 "i" 1730 OpName %56 "j" 1731 OpName %64 "b" 1732 %2 = OpTypeVoid 1733 %3 = OpTypeFunction %2 1734 %6 = OpTypeInt 32 1 1735 %7 = OpTypePointer Function %6 1736 %9 = OpConstant %6 0 1737 %16 = OpConstant %6 10 1738 %17 = OpTypeBool 1739 %27 = OpTypeInt 32 0 1740 %28 = OpConstant %27 10 1741 %29 = OpTypeArray %6 %28 1742 %30 = OpTypeArray %29 %28 1743 %31 = OpTypePointer Function %30 1744 %40 = OpConstant %6 2 1745 %44 = OpConstant %6 1 1746 %4 = OpFunction %2 None %3 1747 %5 = OpLabel 1748 %8 = OpVariable %7 Function 1749 %19 = OpVariable %7 Function 1750 %32 = OpVariable %31 Function 1751 %35 = OpVariable %31 Function 1752 %48 = OpVariable %7 Function 1753 %56 = OpVariable %7 Function 1754 %64 = OpVariable %31 Function 1755 OpStore %8 %9 1756 OpBranch %10 1757 %10 = OpLabel 1758 %77 = OpPhi %6 %9 %5 %47 %13 1759 OpLoopMerge %12 %13 None 1760 OpBranch %14 1761 %14 = OpLabel 1762 %18 = OpSLessThan %17 %77 %16 1763 OpBranchConditional %18 %11 %12 1764 %11 = OpLabel 1765 OpStore %19 %9 1766 OpBranch %20 1767 %20 = OpLabel 1768 %81 = OpPhi %6 %9 %11 %45 %23 1769 OpLoopMerge %22 %23 None 1770 OpBranch %24 1771 %24 = OpLabel 1772 %26 = OpSLessThan %17 %81 %16 1773 OpBranchConditional %26 %21 %22 1774 %21 = OpLabel 1775 %38 = OpAccessChain %7 %35 %77 %81 1776 %39 = OpLoad %6 %38 1777 %41 = OpIAdd %6 %39 %40 1778 %42 = OpAccessChain %7 %32 %77 %81 1779 OpStore %42 %41 1780 OpBranch %23 1781 %23 = OpLabel 1782 %45 = OpIAdd %6 %81 %44 1783 OpStore %19 %45 1784 OpBranch %20 1785 %22 = OpLabel 1786 OpBranch %13 1787 %13 = OpLabel 1788 %47 = OpIAdd %6 %77 %44 1789 OpStore %8 %47 1790 OpBranch %10 1791 %12 = OpLabel 1792 OpStore %48 %9 1793 OpBranch %49 1794 %49 = OpLabel 1795 %78 = OpPhi %6 %9 %12 %76 %52 1796 OpLoopMerge %51 %52 None 1797 OpBranch %53 1798 %53 = OpLabel 1799 %55 = OpSLessThan %17 %78 %16 1800 OpBranchConditional %55 %50 %51 1801 %50 = OpLabel 1802 OpStore %56 %9 1803 OpBranch %57 1804 %57 = OpLabel 1805 %79 = OpPhi %6 %9 %50 %74 %60 1806 OpLoopMerge %59 %60 None 1807 OpBranch %61 1808 %61 = OpLabel 1809 %63 = OpSLessThan %17 %79 %16 1810 OpBranchConditional %63 %58 %59 1811 %58 = OpLabel 1812 %69 = OpAccessChain %7 %32 %78 %79 1813 %70 = OpLoad %6 %69 1814 %71 = OpIAdd %6 %70 %16 1815 %72 = OpAccessChain %7 %64 %78 %79 1816 OpStore %72 %71 1817 OpBranch %60 1818 %60 = OpLabel 1819 %74 = OpIAdd %6 %79 %44 1820 OpStore %56 %74 1821 OpBranch %57 1822 %59 = OpLabel 1823 OpBranch %52 1824 %52 = OpLabel 1825 %76 = OpIAdd %6 %78 %44 1826 OpStore %48 %76 1827 OpBranch %49 1828 %51 = OpLabel 1829 OpReturn 1830 OpFunctionEnd 1831 )"; 1832 1833 std::unique_ptr<IRContext> context = 1834 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 1835 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 1836 Module* module = context->module(); 1837 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 1838 << text << std::endl; 1839 Function& f = *module->begin(); 1840 1841 { 1842 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 1843 EXPECT_EQ(ld.NumLoops(), 4u); 1844 1845 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 1846 1847 auto loop_0 = loops[0]; 1848 auto loop_1 = loops[1]; 1849 auto loop_2 = loops[2]; 1850 auto loop_3 = loops[3]; 1851 1852 { 1853 LoopFusion fusion(context.get(), loop_0, loop_1); 1854 EXPECT_FALSE(fusion.AreCompatible()); 1855 } 1856 1857 { 1858 LoopFusion fusion(context.get(), loop_1, loop_2); 1859 EXPECT_FALSE(fusion.AreCompatible()); 1860 } 1861 1862 { 1863 LoopFusion fusion(context.get(), loop_2, loop_3); 1864 EXPECT_FALSE(fusion.AreCompatible()); 1865 } 1866 1867 { 1868 LoopFusion fusion(context.get(), loop_1, loop_3); 1869 EXPECT_FALSE(fusion.AreCompatible()); 1870 } 1871 1872 { 1873 LoopFusion fusion(context.get(), loop_0, loop_2); 1874 EXPECT_TRUE(fusion.AreCompatible()); 1875 EXPECT_TRUE(fusion.IsLegal()); 1876 fusion.Fuse(); 1877 } 1878 1879 std::string checks = R"( 1880 CHECK: [[PHI_0:%\w+]] = OpPhi 1881 CHECK-NEXT: OpLoopMerge 1882 CHECK: [[PHI_1:%\w+]] = OpPhi 1883 CHECK-NEXT: OpLoopMerge 1884 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1885 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 1886 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1887 CHECK-NEXT: OpStore [[STORE_0]] 1888 CHECK: [[PHI_2:%\w+]] = OpPhi 1889 CHECK-NEXT: OpLoopMerge 1890 CHECK-NOT: OpPhi 1891 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]] 1892 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 1893 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]] 1894 CHECK-NEXT: OpStore [[STORE_1]] 1895 )"; 1896 1897 Match(checks, context.get()); 1898 } 1899 1900 { 1901 auto& ld = *context->GetLoopDescriptor(&f); 1902 EXPECT_EQ(ld.NumLoops(), 3u); 1903 1904 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 1905 auto loop_0 = loops[0]; 1906 auto loop_1 = loops[1]; 1907 auto loop_2 = loops[2]; 1908 1909 { 1910 LoopFusion fusion(context.get(), loop_0, loop_1); 1911 EXPECT_FALSE(fusion.AreCompatible()); 1912 } 1913 1914 { 1915 LoopFusion fusion(context.get(), loop_0, loop_2); 1916 EXPECT_FALSE(fusion.AreCompatible()); 1917 } 1918 1919 { 1920 LoopFusion fusion(context.get(), loop_1, loop_2); 1921 EXPECT_TRUE(fusion.AreCompatible()); 1922 EXPECT_TRUE(fusion.IsLegal()); 1923 fusion.Fuse(); 1924 } 1925 1926 std::string checks = R"( 1927 CHECK: [[PHI_0:%\w+]] = OpPhi 1928 CHECK-NEXT: OpLoopMerge 1929 CHECK: [[PHI_1:%\w+]] = OpPhi 1930 CHECK-NEXT: OpLoopMerge 1931 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1932 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 1933 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1934 CHECK-NEXT: OpStore [[STORE_0]] 1935 CHECK-NOT: OpPhi 1936 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1937 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 1938 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 1939 CHECK-NEXT: OpStore [[STORE_1]] 1940 )"; 1941 1942 Match(checks, context.get()); 1943 } 1944 1945 { 1946 auto& ld = *context->GetLoopDescriptor(&f); 1947 EXPECT_EQ(ld.NumLoops(), 2u); 1948 } 1949 } 1950 1951 /* 1952 Generated from the following GLSL + --eliminate-local-multi-store 1953 1954 #version 440 core 1955 void main() { 1956 int[10][10] a; 1957 int[10][10] b; 1958 int[10][10] c; 1959 // Legal both, more complex 1960 for (int i = 0; i < 10; i++) { 1961 for (int j = 0; j < 10; j++) { 1962 if (i % 2 == 0 && j % 2 == 0) { 1963 c[i][j] = a[i][j] + 2; 1964 } 1965 } 1966 } 1967 for (int i = 0; i < 10; i++) { 1968 for (int j = 0; j < 10; j++) { 1969 b[i][j] = c[i][j] + 10; 1970 } 1971 } 1972 } 1973 1974 */ 1975 TEST_F(FusionLegalTest, OuterAndInnerLoopMoreComplex) { 1976 std::string text = R"( 1977 OpCapability Shader 1978 %1 = OpExtInstImport "GLSL.std.450" 1979 OpMemoryModel Logical GLSL450 1980 OpEntryPoint Fragment %4 "main" 1981 OpExecutionMode %4 OriginUpperLeft 1982 OpSource GLSL 440 1983 OpName %4 "main" 1984 OpName %8 "i" 1985 OpName %19 "j" 1986 OpName %44 "c" 1987 OpName %47 "a" 1988 OpName %59 "i" 1989 OpName %67 "j" 1990 OpName %75 "b" 1991 %2 = OpTypeVoid 1992 %3 = OpTypeFunction %2 1993 %6 = OpTypeInt 32 1 1994 %7 = OpTypePointer Function %6 1995 %9 = OpConstant %6 0 1996 %16 = OpConstant %6 10 1997 %17 = OpTypeBool 1998 %28 = OpConstant %6 2 1999 %39 = OpTypeInt 32 0 2000 %40 = OpConstant %39 10 2001 %41 = OpTypeArray %6 %40 2002 %42 = OpTypeArray %41 %40 2003 %43 = OpTypePointer Function %42 2004 %55 = OpConstant %6 1 2005 %4 = OpFunction %2 None %3 2006 %5 = OpLabel 2007 %8 = OpVariable %7 Function 2008 %19 = OpVariable %7 Function 2009 %44 = OpVariable %43 Function 2010 %47 = OpVariable %43 Function 2011 %59 = OpVariable %7 Function 2012 %67 = OpVariable %7 Function 2013 %75 = OpVariable %43 Function 2014 OpStore %8 %9 2015 OpBranch %10 2016 %10 = OpLabel 2017 %88 = OpPhi %6 %9 %5 %58 %13 2018 OpLoopMerge %12 %13 None 2019 OpBranch %14 2020 %14 = OpLabel 2021 %18 = OpSLessThan %17 %88 %16 2022 OpBranchConditional %18 %11 %12 2023 %11 = OpLabel 2024 OpStore %19 %9 2025 OpBranch %20 2026 %20 = OpLabel 2027 %92 = OpPhi %6 %9 %11 %56 %23 2028 OpLoopMerge %22 %23 None 2029 OpBranch %24 2030 %24 = OpLabel 2031 %26 = OpSLessThan %17 %92 %16 2032 OpBranchConditional %26 %21 %22 2033 %21 = OpLabel 2034 %29 = OpSMod %6 %88 %28 2035 %30 = OpIEqual %17 %29 %9 2036 OpSelectionMerge %32 None 2037 OpBranchConditional %30 %31 %32 2038 %31 = OpLabel 2039 %34 = OpSMod %6 %92 %28 2040 %35 = OpIEqual %17 %34 %9 2041 OpBranch %32 2042 %32 = OpLabel 2043 %36 = OpPhi %17 %30 %21 %35 %31 2044 OpSelectionMerge %38 None 2045 OpBranchConditional %36 %37 %38 2046 %37 = OpLabel 2047 %50 = OpAccessChain %7 %47 %88 %92 2048 %51 = OpLoad %6 %50 2049 %52 = OpIAdd %6 %51 %28 2050 %53 = OpAccessChain %7 %44 %88 %92 2051 OpStore %53 %52 2052 OpBranch %38 2053 %38 = OpLabel 2054 OpBranch %23 2055 %23 = OpLabel 2056 %56 = OpIAdd %6 %92 %55 2057 OpStore %19 %56 2058 OpBranch %20 2059 %22 = OpLabel 2060 OpBranch %13 2061 %13 = OpLabel 2062 %58 = OpIAdd %6 %88 %55 2063 OpStore %8 %58 2064 OpBranch %10 2065 %12 = OpLabel 2066 OpStore %59 %9 2067 OpBranch %60 2068 %60 = OpLabel 2069 %89 = OpPhi %6 %9 %12 %87 %63 2070 OpLoopMerge %62 %63 None 2071 OpBranch %64 2072 %64 = OpLabel 2073 %66 = OpSLessThan %17 %89 %16 2074 OpBranchConditional %66 %61 %62 2075 %61 = OpLabel 2076 OpStore %67 %9 2077 OpBranch %68 2078 %68 = OpLabel 2079 %90 = OpPhi %6 %9 %61 %85 %71 2080 OpLoopMerge %70 %71 None 2081 OpBranch %72 2082 %72 = OpLabel 2083 %74 = OpSLessThan %17 %90 %16 2084 OpBranchConditional %74 %69 %70 2085 %69 = OpLabel 2086 %80 = OpAccessChain %7 %44 %89 %90 2087 %81 = OpLoad %6 %80 2088 %82 = OpIAdd %6 %81 %16 2089 %83 = OpAccessChain %7 %75 %89 %90 2090 OpStore %83 %82 2091 OpBranch %71 2092 %71 = OpLabel 2093 %85 = OpIAdd %6 %90 %55 2094 OpStore %67 %85 2095 OpBranch %68 2096 %70 = OpLabel 2097 OpBranch %63 2098 %63 = OpLabel 2099 %87 = OpIAdd %6 %89 %55 2100 OpStore %59 %87 2101 OpBranch %60 2102 %62 = OpLabel 2103 OpReturn 2104 OpFunctionEnd 2105 )"; 2106 2107 std::unique_ptr<IRContext> context = 2108 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 2109 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 2110 Module* module = context->module(); 2111 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 2112 << text << std::endl; 2113 Function& f = *module->begin(); 2114 2115 { 2116 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2117 EXPECT_EQ(ld.NumLoops(), 4u); 2118 2119 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 2120 2121 auto loop_0 = loops[0]; 2122 auto loop_1 = loops[1]; 2123 auto loop_2 = loops[2]; 2124 auto loop_3 = loops[3]; 2125 2126 { 2127 LoopFusion fusion(context.get(), loop_0, loop_1); 2128 EXPECT_FALSE(fusion.AreCompatible()); 2129 } 2130 2131 { 2132 LoopFusion fusion(context.get(), loop_1, loop_2); 2133 EXPECT_FALSE(fusion.AreCompatible()); 2134 } 2135 2136 { 2137 LoopFusion fusion(context.get(), loop_2, loop_3); 2138 EXPECT_FALSE(fusion.AreCompatible()); 2139 } 2140 2141 { 2142 LoopFusion fusion(context.get(), loop_1, loop_3); 2143 EXPECT_FALSE(fusion.AreCompatible()); 2144 } 2145 2146 { 2147 LoopFusion fusion(context.get(), loop_0, loop_2); 2148 EXPECT_TRUE(fusion.AreCompatible()); 2149 EXPECT_TRUE(fusion.IsLegal()); 2150 fusion.Fuse(); 2151 } 2152 2153 std::string checks = R"( 2154 CHECK: [[PHI_0:%\w+]] = OpPhi 2155 CHECK-NEXT: OpLoopMerge 2156 CHECK: [[PHI_1:%\w+]] = OpPhi 2157 CHECK-NEXT: OpLoopMerge 2158 CHECK: OpPhi 2159 CHECK-NEXT: OpSelectionMerge 2160 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 2161 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 2162 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 2163 CHECK-NEXT: OpStore [[STORE_0]] 2164 CHECK: [[PHI_2:%\w+]] = OpPhi 2165 CHECK-NEXT: OpLoopMerge 2166 CHECK-NOT: OpPhi 2167 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]] 2168 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 2169 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]] 2170 CHECK-NEXT: OpStore [[STORE_1]] 2171 )"; 2172 2173 Match(checks, context.get()); 2174 } 2175 2176 { 2177 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2178 EXPECT_EQ(ld.NumLoops(), 3u); 2179 2180 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 2181 2182 auto loop_0 = loops[0]; 2183 auto loop_1 = loops[1]; 2184 auto loop_2 = loops[2]; 2185 2186 { 2187 LoopFusion fusion(context.get(), loop_0, loop_1); 2188 EXPECT_FALSE(fusion.AreCompatible()); 2189 } 2190 2191 { 2192 LoopFusion fusion(context.get(), loop_0, loop_2); 2193 EXPECT_FALSE(fusion.AreCompatible()); 2194 } 2195 2196 { 2197 LoopFusion fusion(context.get(), loop_1, loop_2); 2198 EXPECT_TRUE(fusion.AreCompatible()); 2199 EXPECT_TRUE(fusion.IsLegal()); 2200 fusion.Fuse(); 2201 } 2202 2203 std::string checks = R"( 2204 CHECK: [[PHI_0:%\w+]] = OpPhi 2205 CHECK-NEXT: OpLoopMerge 2206 CHECK: [[PHI_1:%\w+]] = OpPhi 2207 CHECK-NEXT: OpLoopMerge 2208 CHECK: OpPhi 2209 CHECK-NEXT: OpSelectionMerge 2210 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 2211 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 2212 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 2213 CHECK-NEXT: OpStore [[STORE_0]] 2214 CHECK-NOT: OpPhi 2215 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 2216 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 2217 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 2218 CHECK-NEXT: OpStore [[STORE_1]] 2219 )"; 2220 2221 Match(checks, context.get()); 2222 } 2223 2224 { 2225 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2226 EXPECT_EQ(ld.NumLoops(), 2u); 2227 } 2228 } 2229 2230 /* 2231 Generated from the following GLSL + --eliminate-local-multi-store 2232 2233 #version 440 core 2234 void main() { 2235 int[10][10] a; 2236 int[10][10] b; 2237 int[10][10] c; 2238 // Outer would have been illegal to fuse, but since written 2239 // like this, inner loop fusion is legal. 2240 for (int i = 0; i < 10; i++) { 2241 for (int j = 0; j < 10; j++) { 2242 c[i][j] = a[i][j] + 2; 2243 } 2244 for (int j = 0; j < 10; j++) { 2245 b[i][j] = c[i+1][j] + 10; 2246 } 2247 } 2248 } 2249 2250 */ 2251 TEST_F(FusionLegalTest, InnerWithExistingDependenceOnOuter) { 2252 std::string text = R"( 2253 OpCapability Shader 2254 %1 = OpExtInstImport "GLSL.std.450" 2255 OpMemoryModel Logical GLSL450 2256 OpEntryPoint Fragment %4 "main" 2257 OpExecutionMode %4 OriginUpperLeft 2258 OpSource GLSL 440 2259 OpName %4 "main" 2260 OpName %8 "i" 2261 OpName %19 "j" 2262 OpName %32 "c" 2263 OpName %35 "a" 2264 OpName %46 "j" 2265 OpName %54 "b" 2266 %2 = OpTypeVoid 2267 %3 = OpTypeFunction %2 2268 %6 = OpTypeInt 32 1 2269 %7 = OpTypePointer Function %6 2270 %9 = OpConstant %6 0 2271 %16 = OpConstant %6 10 2272 %17 = OpTypeBool 2273 %27 = OpTypeInt 32 0 2274 %28 = OpConstant %27 10 2275 %29 = OpTypeArray %6 %28 2276 %30 = OpTypeArray %29 %28 2277 %31 = OpTypePointer Function %30 2278 %40 = OpConstant %6 2 2279 %44 = OpConstant %6 1 2280 %4 = OpFunction %2 None %3 2281 %5 = OpLabel 2282 %8 = OpVariable %7 Function 2283 %19 = OpVariable %7 Function 2284 %32 = OpVariable %31 Function 2285 %35 = OpVariable %31 Function 2286 %46 = OpVariable %7 Function 2287 %54 = OpVariable %31 Function 2288 OpStore %8 %9 2289 OpBranch %10 2290 %10 = OpLabel 2291 %68 = OpPhi %6 %9 %5 %67 %13 2292 OpLoopMerge %12 %13 None 2293 OpBranch %14 2294 %14 = OpLabel 2295 %18 = OpSLessThan %17 %68 %16 2296 OpBranchConditional %18 %11 %12 2297 %11 = OpLabel 2298 OpStore %19 %9 2299 OpBranch %20 2300 %20 = OpLabel 2301 %69 = OpPhi %6 %9 %11 %45 %23 2302 OpLoopMerge %22 %23 None 2303 OpBranch %24 2304 %24 = OpLabel 2305 %26 = OpSLessThan %17 %69 %16 2306 OpBranchConditional %26 %21 %22 2307 %21 = OpLabel 2308 %38 = OpAccessChain %7 %35 %68 %69 2309 %39 = OpLoad %6 %38 2310 %41 = OpIAdd %6 %39 %40 2311 %42 = OpAccessChain %7 %32 %68 %69 2312 OpStore %42 %41 2313 OpBranch %23 2314 %23 = OpLabel 2315 %45 = OpIAdd %6 %69 %44 2316 OpStore %19 %45 2317 OpBranch %20 2318 %22 = OpLabel 2319 OpStore %46 %9 2320 OpBranch %47 2321 %47 = OpLabel 2322 %70 = OpPhi %6 %9 %22 %65 %50 2323 OpLoopMerge %49 %50 None 2324 OpBranch %51 2325 %51 = OpLabel 2326 %53 = OpSLessThan %17 %70 %16 2327 OpBranchConditional %53 %48 %49 2328 %48 = OpLabel 2329 %58 = OpIAdd %6 %68 %44 2330 %60 = OpAccessChain %7 %32 %58 %70 2331 %61 = OpLoad %6 %60 2332 %62 = OpIAdd %6 %61 %16 2333 %63 = OpAccessChain %7 %54 %68 %70 2334 OpStore %63 %62 2335 OpBranch %50 2336 %50 = OpLabel 2337 %65 = OpIAdd %6 %70 %44 2338 OpStore %46 %65 2339 OpBranch %47 2340 %49 = OpLabel 2341 OpBranch %13 2342 %13 = OpLabel 2343 %67 = OpIAdd %6 %68 %44 2344 OpStore %8 %67 2345 OpBranch %10 2346 %12 = OpLabel 2347 OpReturn 2348 OpFunctionEnd 2349 )"; 2350 2351 std::unique_ptr<IRContext> context = 2352 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 2353 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 2354 Module* module = context->module(); 2355 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 2356 << text << std::endl; 2357 Function& f = *module->begin(); 2358 2359 { 2360 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2361 EXPECT_EQ(ld.NumLoops(), 3u); 2362 2363 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 2364 2365 auto loop_0 = loops[0]; 2366 auto loop_1 = loops[1]; 2367 auto loop_2 = loops[2]; 2368 2369 { 2370 LoopFusion fusion(context.get(), loop_0, loop_1); 2371 EXPECT_FALSE(fusion.AreCompatible()); 2372 } 2373 2374 { 2375 LoopFusion fusion(context.get(), loop_0, loop_2); 2376 EXPECT_FALSE(fusion.AreCompatible()); 2377 } 2378 2379 { 2380 LoopFusion fusion(context.get(), loop_1, loop_2); 2381 EXPECT_TRUE(fusion.AreCompatible()); 2382 EXPECT_TRUE(fusion.IsLegal()); 2383 2384 fusion.Fuse(); 2385 } 2386 } 2387 2388 { 2389 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2390 EXPECT_EQ(ld.NumLoops(), 2u); 2391 2392 std::string checks = R"( 2393 CHECK: [[PHI_0:%\w+]] = OpPhi 2394 CHECK-NEXT: OpLoopMerge 2395 CHECK: [[PHI_1:%\w+]] = OpPhi 2396 CHECK-NEXT: OpLoopMerge 2397 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 2398 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 2399 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 2400 CHECK-NEXT: OpStore [[STORE_0]] 2401 CHECK-NOT: OpPhi 2402 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI_0]] {{%\w+}} 2403 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] [[PHI_1]] 2404 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 2405 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 2406 CHECK-NEXT: OpStore [[STORE_1]] 2407 )"; 2408 2409 Match(checks, context.get()); 2410 } 2411 } 2412 2413 /* 2414 Generated from the following GLSL + --eliminate-local-multi-store 2415 2416 #version 440 core 2417 void main() { 2418 int[10] a; 2419 int[10] b; 2420 int[10] c; 2421 // One dimensional arrays. Legal, outer dist 0, inner independent. 2422 for (int i = 0; i < 10; i++) { 2423 for (int j = 0; j < 10; j++) { 2424 c[i] = a[j] + 2; 2425 } 2426 } 2427 for (int i = 0; i < 10; i++) { 2428 for (int j = 0; j < 10; j++) { 2429 b[j] = c[i] + 10; 2430 } 2431 } 2432 } 2433 2434 */ 2435 TEST_F(FusionLegalTest, OuterAndInnerLoopOneDimArrays) { 2436 std::string text = R"( 2437 OpCapability Shader 2438 %1 = OpExtInstImport "GLSL.std.450" 2439 OpMemoryModel Logical GLSL450 2440 OpEntryPoint Fragment %4 "main" 2441 OpExecutionMode %4 OriginUpperLeft 2442 OpSource GLSL 440 2443 OpName %4 "main" 2444 OpName %8 "i" 2445 OpName %19 "j" 2446 OpName %31 "c" 2447 OpName %33 "a" 2448 OpName %45 "i" 2449 OpName %53 "j" 2450 OpName %61 "b" 2451 %2 = OpTypeVoid 2452 %3 = OpTypeFunction %2 2453 %6 = OpTypeInt 32 1 2454 %7 = OpTypePointer Function %6 2455 %9 = OpConstant %6 0 2456 %16 = OpConstant %6 10 2457 %17 = OpTypeBool 2458 %27 = OpTypeInt 32 0 2459 %28 = OpConstant %27 10 2460 %29 = OpTypeArray %6 %28 2461 %30 = OpTypePointer Function %29 2462 %37 = OpConstant %6 2 2463 %41 = OpConstant %6 1 2464 %4 = OpFunction %2 None %3 2465 %5 = OpLabel 2466 %8 = OpVariable %7 Function 2467 %19 = OpVariable %7 Function 2468 %31 = OpVariable %30 Function 2469 %33 = OpVariable %30 Function 2470 %45 = OpVariable %7 Function 2471 %53 = OpVariable %7 Function 2472 %61 = OpVariable %30 Function 2473 OpStore %8 %9 2474 OpBranch %10 2475 %10 = OpLabel 2476 %72 = OpPhi %6 %9 %5 %44 %13 2477 OpLoopMerge %12 %13 None 2478 OpBranch %14 2479 %14 = OpLabel 2480 %18 = OpSLessThan %17 %72 %16 2481 OpBranchConditional %18 %11 %12 2482 %11 = OpLabel 2483 OpStore %19 %9 2484 OpBranch %20 2485 %20 = OpLabel 2486 %76 = OpPhi %6 %9 %11 %42 %23 2487 OpLoopMerge %22 %23 None 2488 OpBranch %24 2489 %24 = OpLabel 2490 %26 = OpSLessThan %17 %76 %16 2491 OpBranchConditional %26 %21 %22 2492 %21 = OpLabel 2493 %35 = OpAccessChain %7 %33 %76 2494 %36 = OpLoad %6 %35 2495 %38 = OpIAdd %6 %36 %37 2496 %39 = OpAccessChain %7 %31 %72 2497 OpStore %39 %38 2498 OpBranch %23 2499 %23 = OpLabel 2500 %42 = OpIAdd %6 %76 %41 2501 OpStore %19 %42 2502 OpBranch %20 2503 %22 = OpLabel 2504 OpBranch %13 2505 %13 = OpLabel 2506 %44 = OpIAdd %6 %72 %41 2507 OpStore %8 %44 2508 OpBranch %10 2509 %12 = OpLabel 2510 OpStore %45 %9 2511 OpBranch %46 2512 %46 = OpLabel 2513 %73 = OpPhi %6 %9 %12 %71 %49 2514 OpLoopMerge %48 %49 None 2515 OpBranch %50 2516 %50 = OpLabel 2517 %52 = OpSLessThan %17 %73 %16 2518 OpBranchConditional %52 %47 %48 2519 %47 = OpLabel 2520 OpStore %53 %9 2521 OpBranch %54 2522 %54 = OpLabel 2523 %74 = OpPhi %6 %9 %47 %69 %57 2524 OpLoopMerge %56 %57 None 2525 OpBranch %58 2526 %58 = OpLabel 2527 %60 = OpSLessThan %17 %74 %16 2528 OpBranchConditional %60 %55 %56 2529 %55 = OpLabel 2530 %64 = OpAccessChain %7 %31 %73 2531 %65 = OpLoad %6 %64 2532 %66 = OpIAdd %6 %65 %16 2533 %67 = OpAccessChain %7 %61 %74 2534 OpStore %67 %66 2535 OpBranch %57 2536 %57 = OpLabel 2537 %69 = OpIAdd %6 %74 %41 2538 OpStore %53 %69 2539 OpBranch %54 2540 %56 = OpLabel 2541 OpBranch %49 2542 %49 = OpLabel 2543 %71 = OpIAdd %6 %73 %41 2544 OpStore %45 %71 2545 OpBranch %46 2546 %48 = OpLabel 2547 OpReturn 2548 OpFunctionEnd 2549 )"; 2550 2551 std::unique_ptr<IRContext> context = 2552 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 2553 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 2554 Module* module = context->module(); 2555 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 2556 << text << std::endl; 2557 Function& f = *module->begin(); 2558 2559 { 2560 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2561 EXPECT_EQ(ld.NumLoops(), 4u); 2562 2563 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 2564 2565 auto loop_0 = loops[0]; 2566 auto loop_1 = loops[1]; 2567 auto loop_2 = loops[2]; 2568 auto loop_3 = loops[3]; 2569 2570 { 2571 LoopFusion fusion(context.get(), loop_0, loop_1); 2572 EXPECT_FALSE(fusion.AreCompatible()); 2573 } 2574 2575 { 2576 LoopFusion fusion(context.get(), loop_1, loop_2); 2577 EXPECT_FALSE(fusion.AreCompatible()); 2578 } 2579 2580 { 2581 LoopFusion fusion(context.get(), loop_2, loop_3); 2582 EXPECT_FALSE(fusion.AreCompatible()); 2583 } 2584 2585 { 2586 LoopFusion fusion(context.get(), loop_0, loop_2); 2587 EXPECT_TRUE(fusion.AreCompatible()); 2588 EXPECT_TRUE(fusion.IsLegal()); 2589 fusion.Fuse(); 2590 } 2591 2592 std::string checks = R"( 2593 CHECK: [[PHI_0:%\w+]] = OpPhi 2594 CHECK-NEXT: OpLoopMerge 2595 CHECK: [[PHI_1:%\w+]] = OpPhi 2596 CHECK-NEXT: OpLoopMerge 2597 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]] 2598 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 2599 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 2600 CHECK-NEXT: OpStore [[STORE_0]] 2601 CHECK: [[PHI_2:%\w+]] = OpPhi 2602 CHECK-NEXT: OpLoopMerge 2603 CHECK-NOT: OpPhi 2604 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 2605 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 2606 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_2]] 2607 CHECK-NEXT: OpStore [[STORE_1]] 2608 )"; 2609 2610 Match(checks, context.get()); 2611 } 2612 2613 { 2614 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2615 EXPECT_EQ(ld.NumLoops(), 3u); 2616 2617 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 2618 2619 auto loop_0 = loops[0]; 2620 auto loop_1 = loops[1]; 2621 auto loop_2 = loops[2]; 2622 2623 { 2624 LoopFusion fusion(context.get(), loop_0, loop_1); 2625 EXPECT_FALSE(fusion.AreCompatible()); 2626 } 2627 2628 { 2629 LoopFusion fusion(context.get(), loop_0, loop_2); 2630 EXPECT_FALSE(fusion.AreCompatible()); 2631 } 2632 2633 { 2634 LoopFusion fusion(context.get(), loop_1, loop_2); 2635 EXPECT_TRUE(fusion.AreCompatible()); 2636 EXPECT_TRUE(fusion.IsLegal()); 2637 2638 fusion.Fuse(); 2639 } 2640 2641 std::string checks = R"( 2642 CHECK: [[PHI_0:%\w+]] = OpPhi 2643 CHECK-NEXT: OpLoopMerge 2644 CHECK: [[PHI_1:%\w+]] = OpPhi 2645 CHECK-NEXT: OpLoopMerge 2646 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]] 2647 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 2648 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 2649 CHECK-NEXT: OpStore [[STORE_0]] 2650 CHECK-NOT: OpPhi 2651 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 2652 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 2653 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]] 2654 CHECK-NEXT: OpStore [[STORE_1]] 2655 )"; 2656 2657 Match(checks, context.get()); 2658 } 2659 } 2660 2661 /* 2662 Generated from the following GLSL + --eliminate-local-multi-store 2663 2664 #version 440 core 2665 void main() { 2666 int[10] a; 2667 int[10] b; 2668 int[10] c; 2669 // Legal, creates a loop-carried dependence, but has negative distance 2670 for (int i = 0; i < 10; i++) { 2671 c[i] = a[i+1] + 1; 2672 } 2673 for (int i = 0; i < 10; i++) { 2674 a[i] = c[i] + 2; 2675 } 2676 } 2677 2678 */ 2679 TEST_F(FusionLegalTest, NegativeDistanceCreatedWAR) { 2680 std::string text = R"( 2681 OpCapability Shader 2682 %1 = OpExtInstImport "GLSL.std.450" 2683 OpMemoryModel Logical GLSL450 2684 OpEntryPoint Fragment %4 "main" 2685 OpExecutionMode %4 OriginUpperLeft 2686 OpSource GLSL 440 2687 OpName %4 "main" 2688 OpName %8 "i" 2689 OpName %23 "c" 2690 OpName %25 "a" 2691 OpName %35 "i" 2692 %2 = OpTypeVoid 2693 %3 = OpTypeFunction %2 2694 %6 = OpTypeInt 32 1 2695 %7 = OpTypePointer Function %6 2696 %9 = OpConstant %6 0 2697 %16 = OpConstant %6 10 2698 %17 = OpTypeBool 2699 %19 = OpTypeInt 32 0 2700 %20 = OpConstant %19 10 2701 %21 = OpTypeArray %6 %20 2702 %22 = OpTypePointer Function %21 2703 %27 = OpConstant %6 1 2704 %47 = OpConstant %6 2 2705 %4 = OpFunction %2 None %3 2706 %5 = OpLabel 2707 %8 = OpVariable %7 Function 2708 %23 = OpVariable %22 Function 2709 %25 = OpVariable %22 Function 2710 %35 = OpVariable %7 Function 2711 OpStore %8 %9 2712 OpBranch %10 2713 %10 = OpLabel 2714 %52 = OpPhi %6 %9 %5 %34 %13 2715 OpLoopMerge %12 %13 None 2716 OpBranch %14 2717 %14 = OpLabel 2718 %18 = OpSLessThan %17 %52 %16 2719 OpBranchConditional %18 %11 %12 2720 %11 = OpLabel 2721 %28 = OpIAdd %6 %52 %27 2722 %29 = OpAccessChain %7 %25 %28 2723 %30 = OpLoad %6 %29 2724 %31 = OpIAdd %6 %30 %27 2725 %32 = OpAccessChain %7 %23 %52 2726 OpStore %32 %31 2727 OpBranch %13 2728 %13 = OpLabel 2729 %34 = OpIAdd %6 %52 %27 2730 OpStore %8 %34 2731 OpBranch %10 2732 %12 = OpLabel 2733 OpStore %35 %9 2734 OpBranch %36 2735 %36 = OpLabel 2736 %53 = OpPhi %6 %9 %12 %51 %39 2737 OpLoopMerge %38 %39 None 2738 OpBranch %40 2739 %40 = OpLabel 2740 %42 = OpSLessThan %17 %53 %16 2741 OpBranchConditional %42 %37 %38 2742 %37 = OpLabel 2743 %45 = OpAccessChain %7 %23 %53 2744 %46 = OpLoad %6 %45 2745 %48 = OpIAdd %6 %46 %47 2746 %49 = OpAccessChain %7 %25 %53 2747 OpStore %49 %48 2748 OpBranch %39 2749 %39 = OpLabel 2750 %51 = OpIAdd %6 %53 %27 2751 OpStore %35 %51 2752 OpBranch %36 2753 %38 = OpLabel 2754 OpReturn 2755 OpFunctionEnd 2756 )"; 2757 2758 std::unique_ptr<IRContext> context = 2759 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 2760 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 2761 Module* module = context->module(); 2762 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 2763 << text << std::endl; 2764 Function& f = *module->begin(); 2765 2766 { 2767 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2768 EXPECT_EQ(ld.NumLoops(), 2u); 2769 2770 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 2771 2772 LoopFusion fusion(context.get(), loops[0], loops[1]); 2773 EXPECT_TRUE(fusion.AreCompatible()); 2774 EXPECT_TRUE(fusion.IsLegal()); 2775 2776 fusion.Fuse(); 2777 2778 std::string checks = R"( 2779 CHECK: [[PHI:%\w+]] = OpPhi 2780 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}} 2781 CHECK-NEXT: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] 2782 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 2783 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 2784 CHECK-NEXT: OpStore [[STORE_0]] 2785 CHECK-NOT: OpPhi 2786 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 2787 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 2788 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 2789 CHECK-NEXT: OpStore [[STORE_1]] 2790 )"; 2791 2792 Match(checks, context.get()); 2793 } 2794 2795 { 2796 auto& ld = *context->GetLoopDescriptor(&f); 2797 EXPECT_EQ(ld.NumLoops(), 1u); 2798 } 2799 } 2800 2801 /* 2802 Generated from the following GLSL + --eliminate-local-multi-store 2803 2804 #version 440 core 2805 void main() { 2806 int[10] a; 2807 int[10] b; 2808 int[10] c; 2809 // Legal, creates a loop-carried dependence, but has negative distance 2810 for (int i = 0; i < 10; i++) { 2811 a[i+1] = b[i] + 1; 2812 } 2813 for (int i = 0; i < 10; i++) { 2814 a[i] = c[i+1] + 2; 2815 } 2816 } 2817 2818 */ 2819 TEST_F(FusionLegalTest, NegativeDistanceCreatedWAW) { 2820 std::string text = R"( 2821 OpCapability Shader 2822 %1 = OpExtInstImport "GLSL.std.450" 2823 OpMemoryModel Logical GLSL450 2824 OpEntryPoint Fragment %4 "main" 2825 OpExecutionMode %4 OriginUpperLeft 2826 OpSource GLSL 440 2827 OpName %4 "main" 2828 OpName %8 "i" 2829 OpName %23 "a" 2830 OpName %27 "b" 2831 OpName %35 "i" 2832 OpName %44 "c" 2833 %2 = OpTypeVoid 2834 %3 = OpTypeFunction %2 2835 %6 = OpTypeInt 32 1 2836 %7 = OpTypePointer Function %6 2837 %9 = OpConstant %6 0 2838 %16 = OpConstant %6 10 2839 %17 = OpTypeBool 2840 %19 = OpTypeInt 32 0 2841 %20 = OpConstant %19 10 2842 %21 = OpTypeArray %6 %20 2843 %22 = OpTypePointer Function %21 2844 %25 = OpConstant %6 1 2845 %49 = OpConstant %6 2 2846 %4 = OpFunction %2 None %3 2847 %5 = OpLabel 2848 %8 = OpVariable %7 Function 2849 %23 = OpVariable %22 Function 2850 %27 = OpVariable %22 Function 2851 %35 = OpVariable %7 Function 2852 %44 = OpVariable %22 Function 2853 OpStore %8 %9 2854 OpBranch %10 2855 %10 = OpLabel 2856 %54 = OpPhi %6 %9 %5 %34 %13 2857 OpLoopMerge %12 %13 None 2858 OpBranch %14 2859 %14 = OpLabel 2860 %18 = OpSLessThan %17 %54 %16 2861 OpBranchConditional %18 %11 %12 2862 %11 = OpLabel 2863 %26 = OpIAdd %6 %54 %25 2864 %29 = OpAccessChain %7 %27 %54 2865 %30 = OpLoad %6 %29 2866 %31 = OpIAdd %6 %30 %25 2867 %32 = OpAccessChain %7 %23 %26 2868 OpStore %32 %31 2869 OpBranch %13 2870 %13 = OpLabel 2871 %34 = OpIAdd %6 %54 %25 2872 OpStore %8 %34 2873 OpBranch %10 2874 %12 = OpLabel 2875 OpStore %35 %9 2876 OpBranch %36 2877 %36 = OpLabel 2878 %55 = OpPhi %6 %9 %12 %53 %39 2879 OpLoopMerge %38 %39 None 2880 OpBranch %40 2881 %40 = OpLabel 2882 %42 = OpSLessThan %17 %55 %16 2883 OpBranchConditional %42 %37 %38 2884 %37 = OpLabel 2885 %46 = OpIAdd %6 %55 %25 2886 %47 = OpAccessChain %7 %44 %46 2887 %48 = OpLoad %6 %47 2888 %50 = OpIAdd %6 %48 %49 2889 %51 = OpAccessChain %7 %23 %55 2890 OpStore %51 %50 2891 OpBranch %39 2892 %39 = OpLabel 2893 %53 = OpIAdd %6 %55 %25 2894 OpStore %35 %53 2895 OpBranch %36 2896 %38 = OpLabel 2897 OpReturn 2898 OpFunctionEnd 2899 )"; 2900 2901 std::unique_ptr<IRContext> context = 2902 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 2903 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 2904 Module* module = context->module(); 2905 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 2906 << text << std::endl; 2907 Function& f = *module->begin(); 2908 2909 { 2910 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2911 EXPECT_EQ(ld.NumLoops(), 2u); 2912 2913 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 2914 2915 LoopFusion fusion(context.get(), loops[0], loops[1]); 2916 EXPECT_TRUE(fusion.AreCompatible()); 2917 EXPECT_TRUE(fusion.IsLegal()); 2918 2919 fusion.Fuse(); 2920 } 2921 2922 { 2923 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 2924 EXPECT_EQ(ld.NumLoops(), 1u); 2925 2926 std::string checks = R"( 2927 CHECK: [[PHI:%\w+]] = OpPhi 2928 CHECK-NEXT: OpLoopMerge 2929 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}} 2930 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 2931 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 2932 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] 2933 CHECK-NEXT: OpStore 2934 CHECK-NOT: OpPhi 2935 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}} 2936 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] 2937 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 2938 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 2939 CHECK-NEXT: OpStore [[STORE_1]] 2940 )"; 2941 2942 Match(checks, context.get()); 2943 } 2944 } 2945 2946 /* 2947 Generated from the following GLSL + --eliminate-local-multi-store 2948 2949 #version 440 core 2950 void main() { 2951 int[10] a; 2952 int[10] b; 2953 int[10] c; 2954 // Legal, no loop-carried dependence 2955 for (int i = 0; i < 10; i++) { 2956 a[i] = b[i] + 1; 2957 } 2958 for (int i = 0; i < 10; i++) { 2959 a[i] = c[i+1] + 2; 2960 } 2961 } 2962 2963 */ 2964 TEST_F(FusionLegalTest, NoLoopCarriedDependencesWAW) { 2965 std::string text = R"( 2966 OpCapability Shader 2967 %1 = OpExtInstImport "GLSL.std.450" 2968 OpMemoryModel Logical GLSL450 2969 OpEntryPoint Fragment %4 "main" 2970 OpExecutionMode %4 OriginUpperLeft 2971 OpSource GLSL 440 2972 OpName %4 "main" 2973 OpName %8 "i" 2974 OpName %23 "a" 2975 OpName %25 "b" 2976 OpName %34 "i" 2977 OpName %43 "c" 2978 %2 = OpTypeVoid 2979 %3 = OpTypeFunction %2 2980 %6 = OpTypeInt 32 1 2981 %7 = OpTypePointer Function %6 2982 %9 = OpConstant %6 0 2983 %16 = OpConstant %6 10 2984 %17 = OpTypeBool 2985 %19 = OpTypeInt 32 0 2986 %20 = OpConstant %19 10 2987 %21 = OpTypeArray %6 %20 2988 %22 = OpTypePointer Function %21 2989 %29 = OpConstant %6 1 2990 %48 = OpConstant %6 2 2991 %4 = OpFunction %2 None %3 2992 %5 = OpLabel 2993 %8 = OpVariable %7 Function 2994 %23 = OpVariable %22 Function 2995 %25 = OpVariable %22 Function 2996 %34 = OpVariable %7 Function 2997 %43 = OpVariable %22 Function 2998 OpStore %8 %9 2999 OpBranch %10 3000 %10 = OpLabel 3001 %53 = OpPhi %6 %9 %5 %33 %13 3002 OpLoopMerge %12 %13 None 3003 OpBranch %14 3004 %14 = OpLabel 3005 %18 = OpSLessThan %17 %53 %16 3006 OpBranchConditional %18 %11 %12 3007 %11 = OpLabel 3008 %27 = OpAccessChain %7 %25 %53 3009 %28 = OpLoad %6 %27 3010 %30 = OpIAdd %6 %28 %29 3011 %31 = OpAccessChain %7 %23 %53 3012 OpStore %31 %30 3013 OpBranch %13 3014 %13 = OpLabel 3015 %33 = OpIAdd %6 %53 %29 3016 OpStore %8 %33 3017 OpBranch %10 3018 %12 = OpLabel 3019 OpStore %34 %9 3020 OpBranch %35 3021 %35 = OpLabel 3022 %54 = OpPhi %6 %9 %12 %52 %38 3023 OpLoopMerge %37 %38 None 3024 OpBranch %39 3025 %39 = OpLabel 3026 %41 = OpSLessThan %17 %54 %16 3027 OpBranchConditional %41 %36 %37 3028 %36 = OpLabel 3029 %45 = OpIAdd %6 %54 %29 3030 %46 = OpAccessChain %7 %43 %45 3031 %47 = OpLoad %6 %46 3032 %49 = OpIAdd %6 %47 %48 3033 %50 = OpAccessChain %7 %23 %54 3034 OpStore %50 %49 3035 OpBranch %38 3036 %38 = OpLabel 3037 %52 = OpIAdd %6 %54 %29 3038 OpStore %34 %52 3039 OpBranch %35 3040 %37 = OpLabel 3041 OpReturn 3042 OpFunctionEnd 3043 )"; 3044 3045 std::unique_ptr<IRContext> context = 3046 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 3047 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 3048 Module* module = context->module(); 3049 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 3050 << text << std::endl; 3051 Function& f = *module->begin(); 3052 3053 { 3054 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3055 EXPECT_EQ(ld.NumLoops(), 2u); 3056 3057 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 3058 3059 LoopFusion fusion(context.get(), loops[0], loops[1]); 3060 EXPECT_TRUE(fusion.AreCompatible()); 3061 EXPECT_TRUE(fusion.IsLegal()); 3062 3063 fusion.Fuse(); 3064 } 3065 3066 { 3067 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3068 EXPECT_EQ(ld.NumLoops(), 1u); 3069 3070 std::string checks = R"( 3071 CHECK: [[PHI:%\w+]] = OpPhi 3072 CHECK-NEXT: OpLoopMerge 3073 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3074 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 3075 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3076 CHECK-NEXT: OpStore [[STORE_0]] 3077 CHECK-NOT: OpPhi 3078 CHECK: [[I_1:%\w+]] = OpIAdd {{%\w+}} [[PHI]] {{%\w+}} 3079 CHECK-NEXT: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[I_1]] 3080 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 3081 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3082 CHECK-NEXT: OpStore [[STORE_1]] 3083 )"; 3084 3085 Match(checks, context.get()); 3086 } 3087 } 3088 3089 /* 3090 Generated from the following GLSL + --eliminate-local-multi-store 3091 3092 #version 440 core 3093 void main() { 3094 int[10][10] a; 3095 int[10][10] b; 3096 int[10][10] c; 3097 // Legal outer. Continue and break are fine if nested in inner loops 3098 for (int i = 0; i < 10; i++) { 3099 for (int j = 0; j < 10; j++) { 3100 if (j % 2 == 0) { 3101 c[i][j] = a[i][j] + 2; 3102 } else { 3103 continue; 3104 } 3105 } 3106 } 3107 for (int i = 0; i < 10; i++) { 3108 for (int j = 0; j < 10; j++) { 3109 if (j % 2 == 0) { 3110 b[i][j] = c[i][j] + 10; 3111 } else { 3112 break; 3113 } 3114 } 3115 } 3116 } 3117 3118 */ 3119 TEST_F(FusionLegalTest, OuterloopWithBreakContinueInInner) { 3120 std::string text = R"( 3121 OpCapability Shader 3122 %1 = OpExtInstImport "GLSL.std.450" 3123 OpMemoryModel Logical GLSL450 3124 OpEntryPoint Fragment %4 "main" 3125 OpExecutionMode %4 OriginUpperLeft 3126 OpSource GLSL 440 3127 OpName %4 "main" 3128 OpName %8 "i" 3129 OpName %19 "j" 3130 OpName %38 "c" 3131 OpName %41 "a" 3132 OpName %55 "i" 3133 OpName %63 "j" 3134 OpName %76 "b" 3135 %2 = OpTypeVoid 3136 %3 = OpTypeFunction %2 3137 %6 = OpTypeInt 32 1 3138 %7 = OpTypePointer Function %6 3139 %9 = OpConstant %6 0 3140 %16 = OpConstant %6 10 3141 %17 = OpTypeBool 3142 %28 = OpConstant %6 2 3143 %33 = OpTypeInt 32 0 3144 %34 = OpConstant %33 10 3145 %35 = OpTypeArray %6 %34 3146 %36 = OpTypeArray %35 %34 3147 %37 = OpTypePointer Function %36 3148 %51 = OpConstant %6 1 3149 %4 = OpFunction %2 None %3 3150 %5 = OpLabel 3151 %8 = OpVariable %7 Function 3152 %19 = OpVariable %7 Function 3153 %38 = OpVariable %37 Function 3154 %41 = OpVariable %37 Function 3155 %55 = OpVariable %7 Function 3156 %63 = OpVariable %7 Function 3157 %76 = OpVariable %37 Function 3158 OpStore %8 %9 3159 OpBranch %10 3160 %10 = OpLabel 3161 %91 = OpPhi %6 %9 %5 %54 %13 3162 OpLoopMerge %12 %13 None 3163 OpBranch %14 3164 %14 = OpLabel 3165 %18 = OpSLessThan %17 %91 %16 3166 OpBranchConditional %18 %11 %12 3167 %11 = OpLabel 3168 OpStore %19 %9 3169 OpBranch %20 3170 %20 = OpLabel 3171 %96 = OpPhi %6 %9 %11 %52 %23 3172 OpLoopMerge %22 %23 None 3173 OpBranch %24 3174 %24 = OpLabel 3175 %26 = OpSLessThan %17 %96 %16 3176 OpBranchConditional %26 %21 %22 3177 %21 = OpLabel 3178 %29 = OpSMod %6 %96 %28 3179 %30 = OpIEqual %17 %29 %9 3180 OpSelectionMerge %23 None 3181 OpBranchConditional %30 %31 %48 3182 %31 = OpLabel 3183 %44 = OpAccessChain %7 %41 %91 %96 3184 %45 = OpLoad %6 %44 3185 %46 = OpIAdd %6 %45 %28 3186 %47 = OpAccessChain %7 %38 %91 %96 3187 OpStore %47 %46 3188 OpBranch %32 3189 %48 = OpLabel 3190 OpBranch %23 3191 %32 = OpLabel 3192 OpBranch %23 3193 %23 = OpLabel 3194 %52 = OpIAdd %6 %96 %51 3195 OpStore %19 %52 3196 OpBranch %20 3197 %22 = OpLabel 3198 OpBranch %13 3199 %13 = OpLabel 3200 %54 = OpIAdd %6 %91 %51 3201 OpStore %8 %54 3202 OpBranch %10 3203 %12 = OpLabel 3204 OpStore %55 %9 3205 OpBranch %56 3206 %56 = OpLabel 3207 %92 = OpPhi %6 %9 %12 %90 %59 3208 OpLoopMerge %58 %59 None 3209 OpBranch %60 3210 %60 = OpLabel 3211 %62 = OpSLessThan %17 %92 %16 3212 OpBranchConditional %62 %57 %58 3213 %57 = OpLabel 3214 OpStore %63 %9 3215 OpBranch %64 3216 %64 = OpLabel 3217 %93 = OpPhi %6 %9 %57 %88 %67 3218 OpLoopMerge %66 %67 None 3219 OpBranch %68 3220 %68 = OpLabel 3221 %70 = OpSLessThan %17 %93 %16 3222 OpBranchConditional %70 %65 %66 3223 %65 = OpLabel 3224 %72 = OpSMod %6 %93 %28 3225 %73 = OpIEqual %17 %72 %9 3226 OpSelectionMerge %75 None 3227 OpBranchConditional %73 %74 %66 3228 %74 = OpLabel 3229 %81 = OpAccessChain %7 %38 %92 %93 3230 %82 = OpLoad %6 %81 3231 %83 = OpIAdd %6 %82 %16 3232 %84 = OpAccessChain %7 %76 %92 %93 3233 OpStore %84 %83 3234 OpBranch %75 3235 %75 = OpLabel 3236 OpBranch %67 3237 %67 = OpLabel 3238 %88 = OpIAdd %6 %93 %51 3239 OpStore %63 %88 3240 OpBranch %64 3241 %66 = OpLabel 3242 OpBranch %59 3243 %59 = OpLabel 3244 %90 = OpIAdd %6 %92 %51 3245 OpStore %55 %90 3246 OpBranch %56 3247 %58 = OpLabel 3248 OpReturn 3249 OpFunctionEnd 3250 )"; 3251 3252 std::unique_ptr<IRContext> context = 3253 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 3254 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 3255 Module* module = context->module(); 3256 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 3257 << text << std::endl; 3258 Function& f = *module->begin(); 3259 3260 { 3261 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3262 EXPECT_EQ(ld.NumLoops(), 4u); 3263 3264 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 3265 3266 LoopFusion fusion(context.get(), loops[0], loops[2]); 3267 EXPECT_TRUE(fusion.AreCompatible()); 3268 EXPECT_TRUE(fusion.IsLegal()); 3269 3270 fusion.Fuse(); 3271 } 3272 3273 { 3274 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3275 EXPECT_EQ(ld.NumLoops(), 3u); 3276 3277 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 3278 3279 LoopFusion fusion(context.get(), loops[1], loops[2]); 3280 EXPECT_FALSE(fusion.AreCompatible()); 3281 3282 std::string checks = R"( 3283 CHECK: [[PHI_0:%\w+]] = OpPhi 3284 CHECK-NEXT: OpLoopMerge 3285 CHECK: [[PHI_1:%\w+]] = OpPhi 3286 CHECK-NEXT: OpLoopMerge 3287 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 3288 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 3289 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_1]] 3290 CHECK-NEXT: OpStore [[STORE_0]] 3291 CHECK: [[PHI_2:%\w+]] = OpPhi 3292 CHECK-NEXT: OpLoopMerge 3293 CHECK-NOT: OpPhi 3294 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]] 3295 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 3296 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] [[PHI_2]] 3297 CHECK-NEXT: OpStore [[STORE_1]] 3298 )"; 3299 3300 Match(checks, context.get()); 3301 } 3302 } 3303 3304 /* 3305 Generated from the following GLSL + --eliminate-local-multi-store 3306 3307 // j loop preheader removed manually 3308 #version 440 core 3309 void main() { 3310 int[10] a; 3311 int[10] b; 3312 int i = 0; 3313 int j = 0; 3314 // No loop-carried dependences, legal 3315 for (; i < 10; i++) { 3316 a[i] = a[i]*2; 3317 } 3318 for (; j < 10; j++) { 3319 b[j] = a[j]+2; 3320 } 3321 } 3322 3323 */ 3324 TEST_F(FusionLegalTest, DifferentArraysInLoopsNoPreheader) { 3325 std::string text = R"( 3326 OpCapability Shader 3327 %1 = OpExtInstImport "GLSL.std.450" 3328 OpMemoryModel Logical GLSL450 3329 OpEntryPoint Fragment %4 "main" 3330 OpExecutionMode %4 OriginUpperLeft 3331 OpSource GLSL 440 3332 OpName %4 "main" 3333 OpName %8 "i" 3334 OpName %10 "j" 3335 OpName %24 "a" 3336 OpName %42 "b" 3337 %2 = OpTypeVoid 3338 %3 = OpTypeFunction %2 3339 %6 = OpTypeInt 32 1 3340 %7 = OpTypePointer Function %6 3341 %9 = OpConstant %6 0 3342 %17 = OpConstant %6 10 3343 %18 = OpTypeBool 3344 %20 = OpTypeInt 32 0 3345 %21 = OpConstant %20 10 3346 %22 = OpTypeArray %6 %21 3347 %23 = OpTypePointer Function %22 3348 %29 = OpConstant %6 2 3349 %33 = OpConstant %6 1 3350 %4 = OpFunction %2 None %3 3351 %5 = OpLabel 3352 %8 = OpVariable %7 Function 3353 %10 = OpVariable %7 Function 3354 %24 = OpVariable %23 Function 3355 %42 = OpVariable %23 Function 3356 OpStore %8 %9 3357 OpStore %10 %9 3358 OpBranch %11 3359 %11 = OpLabel 3360 %51 = OpPhi %6 %9 %5 %34 %14 3361 OpLoopMerge %35 %14 None 3362 OpBranch %15 3363 %15 = OpLabel 3364 %19 = OpSLessThan %18 %51 %17 3365 OpBranchConditional %19 %12 %35 3366 %12 = OpLabel 3367 %27 = OpAccessChain %7 %24 %51 3368 %28 = OpLoad %6 %27 3369 %30 = OpIMul %6 %28 %29 3370 %31 = OpAccessChain %7 %24 %51 3371 OpStore %31 %30 3372 OpBranch %14 3373 %14 = OpLabel 3374 %34 = OpIAdd %6 %51 %33 3375 OpStore %8 %34 3376 OpBranch %11 3377 %35 = OpLabel 3378 %52 = OpPhi %6 %9 %15 %50 %38 3379 OpLoopMerge %37 %38 None 3380 OpBranch %39 3381 %39 = OpLabel 3382 %41 = OpSLessThan %18 %52 %17 3383 OpBranchConditional %41 %36 %37 3384 %36 = OpLabel 3385 %45 = OpAccessChain %7 %24 %52 3386 %46 = OpLoad %6 %45 3387 %47 = OpIAdd %6 %46 %29 3388 %48 = OpAccessChain %7 %42 %52 3389 OpStore %48 %47 3390 OpBranch %38 3391 %38 = OpLabel 3392 %50 = OpIAdd %6 %52 %33 3393 OpStore %10 %50 3394 OpBranch %35 3395 %37 = OpLabel 3396 OpReturn 3397 OpFunctionEnd 3398 )"; 3399 3400 std::unique_ptr<IRContext> context = 3401 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 3402 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 3403 Module* module = context->module(); 3404 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 3405 << text << std::endl; 3406 Function& f = *module->begin(); 3407 3408 { 3409 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3410 EXPECT_EQ(ld.NumLoops(), 2u); 3411 3412 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 3413 3414 { 3415 LoopFusion fusion(context.get(), loops[0], loops[1]); 3416 EXPECT_FALSE(fusion.AreCompatible()); 3417 } 3418 3419 ld.CreatePreHeaderBlocksIfMissing(); 3420 3421 { 3422 LoopFusion fusion(context.get(), loops[0], loops[1]); 3423 EXPECT_TRUE(fusion.AreCompatible()); 3424 EXPECT_TRUE(fusion.IsLegal()); 3425 3426 fusion.Fuse(); 3427 } 3428 } 3429 3430 { 3431 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3432 EXPECT_EQ(ld.NumLoops(), 1u); 3433 3434 std::string checks = R"( 3435 CHECK: [[PHI:%\w+]] = OpPhi 3436 CHECK-NEXT: OpLoopMerge 3437 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3438 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 3439 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3440 CHECK-NEXT: OpStore [[STORE_0]] 3441 CHECK-NOT: OpPhi 3442 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3443 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 3444 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3445 CHECK-NEXT: OpStore [[STORE_1]] 3446 )"; 3447 3448 Match(checks, context.get()); 3449 } 3450 } 3451 3452 /* 3453 Generated from the following GLSL + --eliminate-local-multi-store 3454 3455 // j & k loop preheaders removed manually 3456 #version 440 core 3457 void main() { 3458 int[10] a; 3459 int[10] b; 3460 int i = 0; 3461 int j = 0; 3462 int k = 0; 3463 // No loop-carried dependences, legal 3464 for (; i < 10; i++) { 3465 a[i] = a[i]*2; 3466 } 3467 for (; j < 10; j++) { 3468 b[j] = a[j]+2; 3469 } 3470 for (; k < 10; k++) { 3471 a[k] = a[k]*2; 3472 } 3473 } 3474 3475 */ 3476 TEST_F(FusionLegalTest, AdjacentLoopsNoPreheaders) { 3477 std::string text = R"( 3478 OpCapability Shader 3479 %1 = OpExtInstImport "GLSL.std.450" 3480 OpMemoryModel Logical GLSL450 3481 OpEntryPoint Fragment %4 "main" 3482 OpExecutionMode %4 OriginUpperLeft 3483 OpSource GLSL 440 3484 OpName %4 "main" 3485 OpName %8 "i" 3486 OpName %10 "j" 3487 OpName %11 "k" 3488 OpName %25 "a" 3489 OpName %43 "b" 3490 %2 = OpTypeVoid 3491 %3 = OpTypeFunction %2 3492 %6 = OpTypeInt 32 1 3493 %7 = OpTypePointer Function %6 3494 %9 = OpConstant %6 0 3495 %18 = OpConstant %6 10 3496 %19 = OpTypeBool 3497 %21 = OpTypeInt 32 0 3498 %22 = OpConstant %21 10 3499 %23 = OpTypeArray %6 %22 3500 %24 = OpTypePointer Function %23 3501 %30 = OpConstant %6 2 3502 %34 = OpConstant %6 1 3503 %4 = OpFunction %2 None %3 3504 %5 = OpLabel 3505 %8 = OpVariable %7 Function 3506 %10 = OpVariable %7 Function 3507 %11 = OpVariable %7 Function 3508 %25 = OpVariable %24 Function 3509 %43 = OpVariable %24 Function 3510 OpStore %8 %9 3511 OpStore %10 %9 3512 OpStore %11 %9 3513 OpBranch %12 3514 %12 = OpLabel 3515 %67 = OpPhi %6 %9 %5 %35 %15 3516 OpLoopMerge %36 %15 None 3517 OpBranch %16 3518 %16 = OpLabel 3519 %20 = OpSLessThan %19 %67 %18 3520 OpBranchConditional %20 %13 %36 3521 %13 = OpLabel 3522 %28 = OpAccessChain %7 %25 %67 3523 %29 = OpLoad %6 %28 3524 %31 = OpIMul %6 %29 %30 3525 %32 = OpAccessChain %7 %25 %67 3526 OpStore %32 %31 3527 OpBranch %15 3528 %15 = OpLabel 3529 %35 = OpIAdd %6 %67 %34 3530 OpStore %8 %35 3531 OpBranch %12 3532 %36 = OpLabel 3533 %68 = OpPhi %6 %9 %16 %51 %39 3534 OpLoopMerge %52 %39 None 3535 OpBranch %40 3536 %40 = OpLabel 3537 %42 = OpSLessThan %19 %68 %18 3538 OpBranchConditional %42 %37 %52 3539 %37 = OpLabel 3540 %46 = OpAccessChain %7 %25 %68 3541 %47 = OpLoad %6 %46 3542 %48 = OpIAdd %6 %47 %30 3543 %49 = OpAccessChain %7 %43 %68 3544 OpStore %49 %48 3545 OpBranch %39 3546 %39 = OpLabel 3547 %51 = OpIAdd %6 %68 %34 3548 OpStore %10 %51 3549 OpBranch %36 3550 %52 = OpLabel 3551 %70 = OpPhi %6 %9 %40 %66 %55 3552 OpLoopMerge %54 %55 None 3553 OpBranch %56 3554 %56 = OpLabel 3555 %58 = OpSLessThan %19 %70 %18 3556 OpBranchConditional %58 %53 %54 3557 %53 = OpLabel 3558 %61 = OpAccessChain %7 %25 %70 3559 %62 = OpLoad %6 %61 3560 %63 = OpIMul %6 %62 %30 3561 %64 = OpAccessChain %7 %25 %70 3562 OpStore %64 %63 3563 OpBranch %55 3564 %55 = OpLabel 3565 %66 = OpIAdd %6 %70 %34 3566 OpStore %11 %66 3567 OpBranch %52 3568 %54 = OpLabel 3569 OpReturn 3570 OpFunctionEnd 3571 )"; 3572 3573 std::unique_ptr<IRContext> context = 3574 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 3575 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 3576 Module* module = context->module(); 3577 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 3578 << text << std::endl; 3579 Function& f = *module->begin(); 3580 3581 { 3582 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3583 EXPECT_EQ(ld.NumLoops(), 3u); 3584 3585 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 3586 3587 { 3588 LoopFusion fusion(context.get(), loops[0], loops[1]); 3589 EXPECT_FALSE(fusion.AreCompatible()); 3590 } 3591 3592 ld.CreatePreHeaderBlocksIfMissing(); 3593 3594 { 3595 LoopFusion fusion(context.get(), loops[0], loops[1]); 3596 EXPECT_TRUE(fusion.AreCompatible()); 3597 EXPECT_TRUE(fusion.IsLegal()); 3598 3599 fusion.Fuse(); 3600 } 3601 } 3602 3603 { 3604 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3605 EXPECT_EQ(ld.NumLoops(), 2u); 3606 3607 std::string checks = R"( 3608 CHECK: [[PHI_0:%\w+]] = OpPhi 3609 CHECK-NEXT: OpLoopMerge 3610 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 3611 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 3612 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 3613 CHECK-NEXT: OpStore [[STORE_0]] 3614 CHECK-NOT: OpPhi 3615 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 3616 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 3617 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_0]] 3618 CHECK-NEXT: OpStore [[STORE_1]] 3619 CHECK: [[PHI_1:%\w+]] = OpPhi 3620 CHECK-NEXT: OpLoopMerge 3621 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]] 3622 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]] 3623 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI_1]] 3624 CHECK-NEXT: OpStore [[STORE_2]] 3625 )"; 3626 3627 Match(checks, context.get()); 3628 3629 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 3630 3631 LoopFusion fusion(context.get(), loops[0], loops[1]); 3632 EXPECT_TRUE(fusion.AreCompatible()); 3633 EXPECT_TRUE(fusion.IsLegal()); 3634 3635 fusion.Fuse(); 3636 } 3637 3638 { 3639 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3640 EXPECT_EQ(ld.NumLoops(), 1u); 3641 3642 std::string checks = R"( 3643 CHECK: [[PHI:%\w+]] = OpPhi 3644 CHECK-NEXT: OpLoopMerge 3645 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3646 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_0]] 3647 CHECK: [[STORE_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3648 CHECK-NEXT: OpStore [[STORE_0]] 3649 CHECK-NOT: OpPhi 3650 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3651 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_1]] 3652 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3653 CHECK-NEXT: OpStore [[STORE_1]] 3654 CHECK-NOT: OpPhi 3655 CHECK: [[LOAD_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3656 CHECK-NEXT: OpLoad {{%\w+}} [[LOAD_2]] 3657 CHECK: [[STORE_2:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3658 CHECK-NEXT: OpStore [[STORE_2]] 3659 )"; 3660 3661 Match(checks, context.get()); 3662 } 3663 } 3664 3665 /* 3666 Generated from the following GLSL + --eliminate-local-multi-store 3667 3668 #version 440 core 3669 void main() { 3670 int[10] a; 3671 int[10] b; 3672 3673 int sum_0 = 0; 3674 int sum_1 = 0; 3675 3676 // No loop-carried dependences, legal 3677 for (int i = 0; i < 10; i++) { 3678 sum_0 += a[i]; 3679 } 3680 for (int j = 0; j < 10; j++) { 3681 sum_1 += b[j]; 3682 } 3683 3684 int total = sum_0 + sum_1; 3685 } 3686 3687 */ 3688 TEST_F(FusionLegalTest, IndependentReductions) { 3689 std::string text = R"( 3690 OpCapability Shader 3691 %1 = OpExtInstImport "GLSL.std.450" 3692 OpMemoryModel Logical GLSL450 3693 OpEntryPoint Fragment %4 "main" 3694 OpExecutionMode %4 OriginUpperLeft 3695 OpSource GLSL 440 3696 OpName %4 "main" 3697 OpName %8 "sum_0" 3698 OpName %10 "sum_1" 3699 OpName %11 "i" 3700 OpName %25 "a" 3701 OpName %34 "j" 3702 OpName %42 "b" 3703 OpName %50 "total" 3704 %2 = OpTypeVoid 3705 %3 = OpTypeFunction %2 3706 %6 = OpTypeInt 32 1 3707 %7 = OpTypePointer Function %6 3708 %9 = OpConstant %6 0 3709 %18 = OpConstant %6 10 3710 %19 = OpTypeBool 3711 %21 = OpTypeInt 32 0 3712 %22 = OpConstant %21 10 3713 %23 = OpTypeArray %6 %22 3714 %24 = OpTypePointer Function %23 3715 %32 = OpConstant %6 1 3716 %4 = OpFunction %2 None %3 3717 %5 = OpLabel 3718 %8 = OpVariable %7 Function 3719 %10 = OpVariable %7 Function 3720 %11 = OpVariable %7 Function 3721 %25 = OpVariable %24 Function 3722 %34 = OpVariable %7 Function 3723 %42 = OpVariable %24 Function 3724 %50 = OpVariable %7 Function 3725 OpStore %8 %9 3726 OpStore %10 %9 3727 OpStore %11 %9 3728 OpBranch %12 3729 %12 = OpLabel 3730 %57 = OpPhi %6 %9 %5 %30 %15 3731 %54 = OpPhi %6 %9 %5 %33 %15 3732 OpLoopMerge %14 %15 None 3733 OpBranch %16 3734 %16 = OpLabel 3735 %20 = OpSLessThan %19 %54 %18 3736 OpBranchConditional %20 %13 %14 3737 %13 = OpLabel 3738 %27 = OpAccessChain %7 %25 %54 3739 %28 = OpLoad %6 %27 3740 %30 = OpIAdd %6 %57 %28 3741 OpStore %8 %30 3742 OpBranch %15 3743 %15 = OpLabel 3744 %33 = OpIAdd %6 %54 %32 3745 OpStore %11 %33 3746 OpBranch %12 3747 %14 = OpLabel 3748 OpStore %34 %9 3749 OpBranch %35 3750 %35 = OpLabel 3751 %58 = OpPhi %6 %9 %14 %47 %38 3752 %55 = OpPhi %6 %9 %14 %49 %38 3753 OpLoopMerge %37 %38 None 3754 OpBranch %39 3755 %39 = OpLabel 3756 %41 = OpSLessThan %19 %55 %18 3757 OpBranchConditional %41 %36 %37 3758 %36 = OpLabel 3759 %44 = OpAccessChain %7 %42 %55 3760 %45 = OpLoad %6 %44 3761 %47 = OpIAdd %6 %58 %45 3762 OpStore %10 %47 3763 OpBranch %38 3764 %38 = OpLabel 3765 %49 = OpIAdd %6 %55 %32 3766 OpStore %34 %49 3767 OpBranch %35 3768 %37 = OpLabel 3769 %53 = OpIAdd %6 %57 %58 3770 OpStore %50 %53 3771 OpReturn 3772 OpFunctionEnd 3773 )"; 3774 3775 std::unique_ptr<IRContext> context = 3776 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 3777 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 3778 Module* module = context->module(); 3779 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 3780 << text << std::endl; 3781 Function& f = *module->begin(); 3782 3783 { 3784 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3785 EXPECT_EQ(ld.NumLoops(), 2u); 3786 3787 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 3788 3789 LoopFusion fusion(context.get(), loops[0], loops[1]); 3790 EXPECT_TRUE(fusion.AreCompatible()); 3791 EXPECT_TRUE(fusion.IsLegal()); 3792 3793 fusion.Fuse(); 3794 } 3795 3796 { 3797 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3798 EXPECT_EQ(ld.NumLoops(), 1u); 3799 3800 std::string checks = R"( 3801 CHECK: [[SUM_0:%\w+]] = OpPhi 3802 CHECK-NEXT: [[SUM_1:%\w+]] = OpPhi 3803 CHECK-NEXT: [[PHI:%\w+]] = OpPhi 3804 CHECK-NEXT: OpLoopMerge 3805 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3806 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]] 3807 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]] 3808 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]] 3809 CHECK-NOT: OpPhi 3810 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3811 CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]] 3812 CHECK-NEXT: [[ADD_RES_1:%\w+]] = OpIAdd {{%\w+}} [[SUM_1]] [[LOAD_RES_1]] 3813 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_1]] 3814 )"; 3815 3816 Match(checks, context.get()); 3817 } 3818 } 3819 3820 /* 3821 Generated from the following GLSL + --eliminate-local-multi-store 3822 3823 #version 440 core 3824 void main() { 3825 int[10] a; 3826 int[10] b; 3827 3828 int sum_0 = 0; 3829 int sum_1 = 0; 3830 3831 // No loop-carried dependences, legal 3832 for (int i = 0; i < 10; i++) { 3833 sum_0 += a[i]; 3834 } 3835 for (int j = 0; j < 10; j++) { 3836 sum_1 += b[j]; 3837 } 3838 3839 int total = sum_0 + sum_1; 3840 } 3841 3842 */ 3843 TEST_F(FusionLegalTest, IndependentReductionsOneLCSSA) { 3844 std::string text = R"( 3845 OpCapability Shader 3846 %1 = OpExtInstImport "GLSL.std.450" 3847 OpMemoryModel Logical GLSL450 3848 OpEntryPoint Fragment %4 "main" 3849 OpExecutionMode %4 OriginUpperLeft 3850 OpSource GLSL 440 3851 OpName %4 "main" 3852 OpName %8 "sum_0" 3853 OpName %10 "sum_1" 3854 OpName %11 "i" 3855 OpName %25 "a" 3856 OpName %34 "j" 3857 OpName %42 "b" 3858 OpName %50 "total" 3859 %2 = OpTypeVoid 3860 %3 = OpTypeFunction %2 3861 %6 = OpTypeInt 32 1 3862 %7 = OpTypePointer Function %6 3863 %9 = OpConstant %6 0 3864 %18 = OpConstant %6 10 3865 %19 = OpTypeBool 3866 %21 = OpTypeInt 32 0 3867 %22 = OpConstant %21 10 3868 %23 = OpTypeArray %6 %22 3869 %24 = OpTypePointer Function %23 3870 %32 = OpConstant %6 1 3871 %4 = OpFunction %2 None %3 3872 %5 = OpLabel 3873 %8 = OpVariable %7 Function 3874 %10 = OpVariable %7 Function 3875 %11 = OpVariable %7 Function 3876 %25 = OpVariable %24 Function 3877 %34 = OpVariable %7 Function 3878 %42 = OpVariable %24 Function 3879 %50 = OpVariable %7 Function 3880 OpStore %8 %9 3881 OpStore %10 %9 3882 OpStore %11 %9 3883 OpBranch %12 3884 %12 = OpLabel 3885 %57 = OpPhi %6 %9 %5 %30 %15 3886 %54 = OpPhi %6 %9 %5 %33 %15 3887 OpLoopMerge %14 %15 None 3888 OpBranch %16 3889 %16 = OpLabel 3890 %20 = OpSLessThan %19 %54 %18 3891 OpBranchConditional %20 %13 %14 3892 %13 = OpLabel 3893 %27 = OpAccessChain %7 %25 %54 3894 %28 = OpLoad %6 %27 3895 %30 = OpIAdd %6 %57 %28 3896 OpStore %8 %30 3897 OpBranch %15 3898 %15 = OpLabel 3899 %33 = OpIAdd %6 %54 %32 3900 OpStore %11 %33 3901 OpBranch %12 3902 %14 = OpLabel 3903 OpStore %34 %9 3904 OpBranch %35 3905 %35 = OpLabel 3906 %58 = OpPhi %6 %9 %14 %47 %38 3907 %55 = OpPhi %6 %9 %14 %49 %38 3908 OpLoopMerge %37 %38 None 3909 OpBranch %39 3910 %39 = OpLabel 3911 %41 = OpSLessThan %19 %55 %18 3912 OpBranchConditional %41 %36 %37 3913 %36 = OpLabel 3914 %44 = OpAccessChain %7 %42 %55 3915 %45 = OpLoad %6 %44 3916 %47 = OpIAdd %6 %58 %45 3917 OpStore %10 %47 3918 OpBranch %38 3919 %38 = OpLabel 3920 %49 = OpIAdd %6 %55 %32 3921 OpStore %34 %49 3922 OpBranch %35 3923 %37 = OpLabel 3924 %53 = OpIAdd %6 %57 %58 3925 OpStore %50 %53 3926 OpReturn 3927 OpFunctionEnd 3928 )"; 3929 3930 std::unique_ptr<IRContext> context = 3931 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 3932 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 3933 Module* module = context->module(); 3934 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 3935 << text << std::endl; 3936 Function& f = *module->begin(); 3937 3938 { 3939 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3940 EXPECT_EQ(ld.NumLoops(), 2u); 3941 3942 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 3943 3944 LoopUtils utils_0(context.get(), loops[0]); 3945 utils_0.MakeLoopClosedSSA(); 3946 3947 LoopFusion fusion(context.get(), loops[0], loops[1]); 3948 EXPECT_TRUE(fusion.AreCompatible()); 3949 EXPECT_TRUE(fusion.IsLegal()); 3950 3951 fusion.Fuse(); 3952 } 3953 3954 { 3955 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 3956 EXPECT_EQ(ld.NumLoops(), 1u); 3957 3958 std::string checks = R"( 3959 CHECK: [[SUM_0:%\w+]] = OpPhi 3960 CHECK-NEXT: [[SUM_1:%\w+]] = OpPhi 3961 CHECK-NEXT: [[PHI:%\w+]] = OpPhi 3962 CHECK-NEXT: OpLoopMerge 3963 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3964 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]] 3965 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]] 3966 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]] 3967 CHECK-NOT: OpPhi 3968 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 3969 CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]] 3970 CHECK-NEXT: [[ADD_RES_1:%\w+]] = OpIAdd {{%\w+}} [[SUM_1]] [[LOAD_RES_1]] 3971 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_1]] 3972 )"; 3973 3974 Match(checks, context.get()); 3975 } 3976 } 3977 3978 /* 3979 Generated from the following GLSL + --eliminate-local-multi-store 3980 3981 #version 440 core 3982 void main() { 3983 int[10] a; 3984 int[10] b; 3985 3986 int sum_0 = 0; 3987 int sum_1 = 0; 3988 3989 // No loop-carried dependences, legal 3990 for (int i = 0; i < 10; i++) { 3991 sum_0 += a[i]; 3992 } 3993 for (int j = 0; j < 10; j++) { 3994 sum_1 += b[j]; 3995 } 3996 3997 int total = sum_0 + sum_1; 3998 } 3999 4000 */ 4001 TEST_F(FusionLegalTest, IndependentReductionsBothLCSSA) { 4002 std::string text = R"( 4003 OpCapability Shader 4004 %1 = OpExtInstImport "GLSL.std.450" 4005 OpMemoryModel Logical GLSL450 4006 OpEntryPoint Fragment %4 "main" 4007 OpExecutionMode %4 OriginUpperLeft 4008 OpSource GLSL 440 4009 OpName %4 "main" 4010 OpName %8 "sum_0" 4011 OpName %10 "sum_1" 4012 OpName %11 "i" 4013 OpName %25 "a" 4014 OpName %34 "j" 4015 OpName %42 "b" 4016 OpName %50 "total" 4017 %2 = OpTypeVoid 4018 %3 = OpTypeFunction %2 4019 %6 = OpTypeInt 32 1 4020 %7 = OpTypePointer Function %6 4021 %9 = OpConstant %6 0 4022 %18 = OpConstant %6 10 4023 %19 = OpTypeBool 4024 %21 = OpTypeInt 32 0 4025 %22 = OpConstant %21 10 4026 %23 = OpTypeArray %6 %22 4027 %24 = OpTypePointer Function %23 4028 %32 = OpConstant %6 1 4029 %4 = OpFunction %2 None %3 4030 %5 = OpLabel 4031 %8 = OpVariable %7 Function 4032 %10 = OpVariable %7 Function 4033 %11 = OpVariable %7 Function 4034 %25 = OpVariable %24 Function 4035 %34 = OpVariable %7 Function 4036 %42 = OpVariable %24 Function 4037 %50 = OpVariable %7 Function 4038 OpStore %8 %9 4039 OpStore %10 %9 4040 OpStore %11 %9 4041 OpBranch %12 4042 %12 = OpLabel 4043 %57 = OpPhi %6 %9 %5 %30 %15 4044 %54 = OpPhi %6 %9 %5 %33 %15 4045 OpLoopMerge %14 %15 None 4046 OpBranch %16 4047 %16 = OpLabel 4048 %20 = OpSLessThan %19 %54 %18 4049 OpBranchConditional %20 %13 %14 4050 %13 = OpLabel 4051 %27 = OpAccessChain %7 %25 %54 4052 %28 = OpLoad %6 %27 4053 %30 = OpIAdd %6 %57 %28 4054 OpStore %8 %30 4055 OpBranch %15 4056 %15 = OpLabel 4057 %33 = OpIAdd %6 %54 %32 4058 OpStore %11 %33 4059 OpBranch %12 4060 %14 = OpLabel 4061 OpStore %34 %9 4062 OpBranch %35 4063 %35 = OpLabel 4064 %58 = OpPhi %6 %9 %14 %47 %38 4065 %55 = OpPhi %6 %9 %14 %49 %38 4066 OpLoopMerge %37 %38 None 4067 OpBranch %39 4068 %39 = OpLabel 4069 %41 = OpSLessThan %19 %55 %18 4070 OpBranchConditional %41 %36 %37 4071 %36 = OpLabel 4072 %44 = OpAccessChain %7 %42 %55 4073 %45 = OpLoad %6 %44 4074 %47 = OpIAdd %6 %58 %45 4075 OpStore %10 %47 4076 OpBranch %38 4077 %38 = OpLabel 4078 %49 = OpIAdd %6 %55 %32 4079 OpStore %34 %49 4080 OpBranch %35 4081 %37 = OpLabel 4082 %53 = OpIAdd %6 %57 %58 4083 OpStore %50 %53 4084 OpReturn 4085 OpFunctionEnd 4086 )"; 4087 4088 std::unique_ptr<IRContext> context = 4089 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 4090 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 4091 Module* module = context->module(); 4092 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 4093 << text << std::endl; 4094 Function& f = *module->begin(); 4095 4096 { 4097 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 4098 EXPECT_EQ(ld.NumLoops(), 2u); 4099 4100 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 4101 4102 LoopUtils utils_0(context.get(), loops[0]); 4103 utils_0.MakeLoopClosedSSA(); 4104 LoopUtils utils_1(context.get(), loops[1]); 4105 utils_1.MakeLoopClosedSSA(); 4106 4107 LoopFusion fusion(context.get(), loops[0], loops[1]); 4108 EXPECT_TRUE(fusion.AreCompatible()); 4109 EXPECT_TRUE(fusion.IsLegal()); 4110 4111 fusion.Fuse(); 4112 } 4113 4114 { 4115 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 4116 EXPECT_EQ(ld.NumLoops(), 1u); 4117 4118 std::string checks = R"( 4119 CHECK: [[SUM_0:%\w+]] = OpPhi 4120 CHECK-NEXT: [[SUM_1:%\w+]] = OpPhi 4121 CHECK-NEXT: [[PHI:%\w+]] = OpPhi 4122 CHECK-NEXT: OpLoopMerge 4123 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 4124 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]] 4125 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]] 4126 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]] 4127 CHECK-NOT: OpPhi 4128 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 4129 CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]] 4130 CHECK-NEXT: [[ADD_RES_1:%\w+]] = OpIAdd {{%\w+}} [[SUM_1]] [[LOAD_RES_1]] 4131 CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_1]] 4132 )"; 4133 4134 Match(checks, context.get()); 4135 } 4136 } 4137 4138 /* 4139 Generated from the following GLSL + --eliminate-local-multi-store 4140 4141 #version 440 core 4142 void main() { 4143 int[10] a; 4144 int[10] b; 4145 4146 int sum_0 = 0; 4147 4148 // No loop-carried dependences, legal 4149 for (int i = 0; i < 10; i++) { 4150 sum_0 += a[i]; 4151 } 4152 for (int j = 0; j < 10; j++) { 4153 a[j] = b[j]; 4154 } 4155 } 4156 4157 */ 4158 TEST_F(FusionLegalTest, LoadStoreReductionAndNonLoopCarriedDependence) { 4159 std::string text = R"( 4160 OpCapability Shader 4161 %1 = OpExtInstImport "GLSL.std.450" 4162 OpMemoryModel Logical GLSL450 4163 OpEntryPoint Fragment %4 "main" 4164 OpExecutionMode %4 OriginUpperLeft 4165 OpSource GLSL 440 4166 OpName %4 "main" 4167 OpName %8 "sum_0" 4168 OpName %10 "i" 4169 OpName %24 "a" 4170 OpName %33 "j" 4171 OpName %42 "b" 4172 %2 = OpTypeVoid 4173 %3 = OpTypeFunction %2 4174 %6 = OpTypeInt 32 1 4175 %7 = OpTypePointer Function %6 4176 %9 = OpConstant %6 0 4177 %17 = OpConstant %6 10 4178 %18 = OpTypeBool 4179 %20 = OpTypeInt 32 0 4180 %21 = OpConstant %20 10 4181 %22 = OpTypeArray %6 %21 4182 %23 = OpTypePointer Function %22 4183 %31 = OpConstant %6 1 4184 %4 = OpFunction %2 None %3 4185 %5 = OpLabel 4186 %8 = OpVariable %7 Function 4187 %10 = OpVariable %7 Function 4188 %24 = OpVariable %23 Function 4189 %33 = OpVariable %7 Function 4190 %42 = OpVariable %23 Function 4191 OpStore %8 %9 4192 OpStore %10 %9 4193 OpBranch %11 4194 %11 = OpLabel 4195 %51 = OpPhi %6 %9 %5 %29 %14 4196 %49 = OpPhi %6 %9 %5 %32 %14 4197 OpLoopMerge %13 %14 None 4198 OpBranch %15 4199 %15 = OpLabel 4200 %19 = OpSLessThan %18 %49 %17 4201 OpBranchConditional %19 %12 %13 4202 %12 = OpLabel 4203 %26 = OpAccessChain %7 %24 %49 4204 %27 = OpLoad %6 %26 4205 %29 = OpIAdd %6 %51 %27 4206 OpStore %8 %29 4207 OpBranch %14 4208 %14 = OpLabel 4209 %32 = OpIAdd %6 %49 %31 4210 OpStore %10 %32 4211 OpBranch %11 4212 %13 = OpLabel 4213 OpStore %33 %9 4214 OpBranch %34 4215 %34 = OpLabel 4216 %50 = OpPhi %6 %9 %13 %48 %37 4217 OpLoopMerge %36 %37 None 4218 OpBranch %38 4219 %38 = OpLabel 4220 %40 = OpSLessThan %18 %50 %17 4221 OpBranchConditional %40 %35 %36 4222 %35 = OpLabel 4223 %44 = OpAccessChain %7 %42 %50 4224 %45 = OpLoad %6 %44 4225 %46 = OpAccessChain %7 %24 %50 4226 OpStore %46 %45 4227 OpBranch %37 4228 %37 = OpLabel 4229 %48 = OpIAdd %6 %50 %31 4230 OpStore %33 %48 4231 OpBranch %34 4232 %36 = OpLabel 4233 OpReturn 4234 OpFunctionEnd 4235 )"; 4236 4237 std::unique_ptr<IRContext> context = 4238 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 4239 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 4240 Module* module = context->module(); 4241 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 4242 << text << std::endl; 4243 Function& f = *module->begin(); 4244 4245 { 4246 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 4247 EXPECT_EQ(ld.NumLoops(), 2u); 4248 4249 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 4250 4251 LoopFusion fusion(context.get(), loops[0], loops[1]); 4252 EXPECT_TRUE(fusion.AreCompatible()); 4253 // TODO: Loop descriptor doesn't return induction variables but all OpPhi 4254 // in the header and LoopDependenceAnalysis falls over. 4255 // EXPECT_TRUE(fusion.IsLegal()); 4256 4257 // fusion.Fuse(); 4258 } 4259 4260 { 4261 // LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 4262 // EXPECT_EQ(ld.NumLoops(), 1u); 4263 4264 // std::string checks = R"( 4265 // CHECK: [[SUM_0:%\w+]] = OpPhi 4266 // CHECK-NEXT: [[PHI:%\w+]] = OpPhi 4267 // CHECK-NEXT: OpLoopMerge 4268 // CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 4269 // CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]] 4270 // CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[SUM_0]] [[LOAD_RES_0]] 4271 // CHECK-NEXT: OpStore {{%\w+}} [[ADD_RES_0]] 4272 // CHECK-NOT: OpPhi 4273 // CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 4274 // CHECK-NEXT: [[LOAD_RES_1:%\w+]] = OpLoad {{%\w+}} [[LOAD_1]] 4275 // CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 4276 // CHECK-NEXT: OpStore [[STORE_1]] [[LOAD_RES_1]] 4277 // )"; 4278 4279 // Match(checks, context.get()); 4280 } 4281 } 4282 4283 /* 4284 Generated from the following GLSL + --eliminate-local-multi-store 4285 4286 #version 440 core 4287 int x; 4288 void main() { 4289 int[10] a; 4290 int[10] b; 4291 4292 // Legal. 4293 for (int i = 0; i < 10; i++) { 4294 x += a[i]; 4295 } 4296 for (int j = 0; j < 10; j++) { 4297 b[j] = b[j]+1; 4298 } 4299 } 4300 4301 */ 4302 TEST_F(FusionLegalTest, ReductionAndNonLoopCarriedDependence) { 4303 std::string text = R"( 4304 OpCapability Shader 4305 %1 = OpExtInstImport "GLSL.std.450" 4306 OpMemoryModel Logical GLSL450 4307 OpEntryPoint Fragment %4 "main" 4308 OpExecutionMode %4 OriginUpperLeft 4309 OpSource GLSL 440 4310 OpName %4 "main" 4311 OpName %8 "i" 4312 OpName %20 "x" 4313 OpName %25 "a" 4314 OpName %34 "j" 4315 OpName %42 "b" 4316 %2 = OpTypeVoid 4317 %3 = OpTypeFunction %2 4318 %6 = OpTypeInt 32 1 4319 %7 = OpTypePointer Function %6 4320 %9 = OpConstant %6 0 4321 %16 = OpConstant %6 10 4322 %17 = OpTypeBool 4323 %19 = OpTypePointer Private %6 4324 %20 = OpVariable %19 Private 4325 %21 = OpTypeInt 32 0 4326 %22 = OpConstant %21 10 4327 %23 = OpTypeArray %6 %22 4328 %24 = OpTypePointer Function %23 4329 %32 = OpConstant %6 1 4330 %4 = OpFunction %2 None %3 4331 %5 = OpLabel 4332 %8 = OpVariable %7 Function 4333 %25 = OpVariable %24 Function 4334 %34 = OpVariable %7 Function 4335 %42 = OpVariable %24 Function 4336 OpStore %8 %9 4337 OpBranch %10 4338 %10 = OpLabel 4339 %51 = OpPhi %6 %9 %5 %33 %13 4340 OpLoopMerge %12 %13 None 4341 OpBranch %14 4342 %14 = OpLabel 4343 %18 = OpSLessThan %17 %51 %16 4344 OpBranchConditional %18 %11 %12 4345 %11 = OpLabel 4346 %27 = OpAccessChain %7 %25 %51 4347 %28 = OpLoad %6 %27 4348 %29 = OpLoad %6 %20 4349 %30 = OpIAdd %6 %29 %28 4350 OpStore %20 %30 4351 OpBranch %13 4352 %13 = OpLabel 4353 %33 = OpIAdd %6 %51 %32 4354 OpStore %8 %33 4355 OpBranch %10 4356 %12 = OpLabel 4357 OpStore %34 %9 4358 OpBranch %35 4359 %35 = OpLabel 4360 %52 = OpPhi %6 %9 %12 %50 %38 4361 OpLoopMerge %37 %38 None 4362 OpBranch %39 4363 %39 = OpLabel 4364 %41 = OpSLessThan %17 %52 %16 4365 OpBranchConditional %41 %36 %37 4366 %36 = OpLabel 4367 %45 = OpAccessChain %7 %42 %52 4368 %46 = OpLoad %6 %45 4369 %47 = OpIAdd %6 %46 %32 4370 %48 = OpAccessChain %7 %42 %52 4371 OpStore %48 %47 4372 OpBranch %38 4373 %38 = OpLabel 4374 %50 = OpIAdd %6 %52 %32 4375 OpStore %34 %50 4376 OpBranch %35 4377 %37 = OpLabel 4378 OpReturn 4379 OpFunctionEnd 4380 )"; 4381 4382 std::unique_ptr<IRContext> context = 4383 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 4384 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 4385 Module* module = context->module(); 4386 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 4387 << text << std::endl; 4388 Function& f = *module->begin(); 4389 4390 { 4391 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 4392 EXPECT_EQ(ld.NumLoops(), 2u); 4393 4394 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 4395 4396 LoopFusion fusion(context.get(), loops[0], loops[1]); 4397 EXPECT_TRUE(fusion.AreCompatible()); 4398 EXPECT_TRUE(fusion.IsLegal()); 4399 4400 fusion.Fuse(); 4401 } 4402 4403 { 4404 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 4405 EXPECT_EQ(ld.NumLoops(), 1u); 4406 4407 std::string checks = R"( 4408 CHECK: OpName [[X:%\w+]] "x" 4409 CHECK: [[PHI:%\w+]] = OpPhi 4410 CHECK-NEXT: OpLoopMerge 4411 CHECK: [[LOAD_0:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 4412 CHECK-NEXT: [[LOAD_RES_0:%\w+]] = OpLoad {{%\w+}} [[LOAD_0]] 4413 CHECK-NEXT: [[X_LOAD:%\w+]] = OpLoad {{%\w+}} [[X]] 4414 CHECK-NEXT: [[ADD_RES_0:%\w+]] = OpIAdd {{%\w+}} [[X_LOAD]] [[LOAD_RES_0]] 4415 CHECK-NEXT: OpStore [[X]] [[ADD_RES_0]] 4416 CHECK-NOT: OpPhi 4417 CHECK: [[LOAD_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 4418 CHECK-NEXT: {{%\w+}} = OpLoad {{%\w+}} [[LOAD_1]] 4419 CHECK: [[STORE_1:%\w+]] = OpAccessChain {{%\w+}} {{%\w+}} [[PHI]] 4420 CHECK-NEXT: OpStore [[STORE_1]] 4421 )"; 4422 4423 Match(checks, context.get()); 4424 } 4425 } 4426 4427 /* 4428 Generated from the following GLSL + --eliminate-local-multi-store 4429 4430 #version 440 core 4431 struct TestStruct { 4432 int[10] a; 4433 int b; 4434 }; 4435 4436 void main() { 4437 TestStruct test_0; 4438 TestStruct test_1; 4439 TestStruct test_2; 4440 4441 test_1.b = 2; 4442 4443 for (int i = 0; i < 10; i++) { 4444 test_0.a[i] = i; 4445 } 4446 for (int j = 0; j < 10; j++) { 4447 test_2 = test_1; 4448 } 4449 } 4450 4451 */ 4452 TEST_F(FusionLegalTest, ArrayInStruct) { 4453 std::string text = R"( 4454 OpCapability Shader 4455 %1 = OpExtInstImport "GLSL.std.450" 4456 OpMemoryModel Logical GLSL450 4457 OpEntryPoint Fragment %4 "main" 4458 OpExecutionMode %4 OriginUpperLeft 4459 OpSource GLSL 440 4460 OpName %4 "main" 4461 OpName %10 "TestStruct" 4462 OpMemberName %10 0 "a" 4463 OpMemberName %10 1 "b" 4464 OpName %12 "test_1" 4465 OpName %17 "i" 4466 OpName %28 "test_0" 4467 OpName %34 "j" 4468 OpName %42 "test_2" 4469 %2 = OpTypeVoid 4470 %3 = OpTypeFunction %2 4471 %6 = OpTypeInt 32 1 4472 %7 = OpTypeInt 32 0 4473 %8 = OpConstant %7 10 4474 %9 = OpTypeArray %6 %8 4475 %10 = OpTypeStruct %9 %6 4476 %11 = OpTypePointer Function %10 4477 %13 = OpConstant %6 1 4478 %14 = OpConstant %6 2 4479 %15 = OpTypePointer Function %6 4480 %18 = OpConstant %6 0 4481 %25 = OpConstant %6 10 4482 %26 = OpTypeBool 4483 %4 = OpFunction %2 None %3 4484 %5 = OpLabel 4485 %12 = OpVariable %11 Function 4486 %17 = OpVariable %15 Function 4487 %28 = OpVariable %11 Function 4488 %34 = OpVariable %15 Function 4489 %42 = OpVariable %11 Function 4490 %16 = OpAccessChain %15 %12 %13 4491 OpStore %16 %14 4492 OpStore %17 %18 4493 OpBranch %19 4494 %19 = OpLabel 4495 %46 = OpPhi %6 %18 %5 %33 %22 4496 OpLoopMerge %21 %22 None 4497 OpBranch %23 4498 %23 = OpLabel 4499 %27 = OpSLessThan %26 %46 %25 4500 OpBranchConditional %27 %20 %21 4501 %20 = OpLabel 4502 %31 = OpAccessChain %15 %28 %18 %46 4503 OpStore %31 %46 4504 OpBranch %22 4505 %22 = OpLabel 4506 %33 = OpIAdd %6 %46 %13 4507 OpStore %17 %33 4508 OpBranch %19 4509 %21 = OpLabel 4510 OpStore %34 %18 4511 OpBranch %35 4512 %35 = OpLabel 4513 %47 = OpPhi %6 %18 %21 %45 %38 4514 OpLoopMerge %37 %38 None 4515 OpBranch %39 4516 %39 = OpLabel 4517 %41 = OpSLessThan %26 %47 %25 4518 OpBranchConditional %41 %36 %37 4519 %36 = OpLabel 4520 %43 = OpLoad %10 %12 4521 OpStore %42 %43 4522 OpBranch %38 4523 %38 = OpLabel 4524 %45 = OpIAdd %6 %47 %13 4525 OpStore %34 %45 4526 OpBranch %35 4527 %37 = OpLabel 4528 OpReturn 4529 OpFunctionEnd 4530 )"; 4531 4532 std::unique_ptr<IRContext> context = 4533 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 4534 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 4535 Module* module = context->module(); 4536 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 4537 << text << std::endl; 4538 Function& f = *module->begin(); 4539 4540 { 4541 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 4542 EXPECT_EQ(ld.NumLoops(), 2u); 4543 4544 auto loops = ld.GetLoopsInBinaryLayoutOrder(); 4545 4546 LoopFusion fusion(context.get(), loops[0], loops[1]); 4547 EXPECT_TRUE(fusion.AreCompatible()); 4548 EXPECT_TRUE(fusion.IsLegal()); 4549 4550 fusion.Fuse(); 4551 } 4552 4553 { 4554 LoopDescriptor& ld = *context->GetLoopDescriptor(&f); 4555 EXPECT_EQ(ld.NumLoops(), 1u); 4556 4557 // clang-format off 4558 std::string checks = R"( 4559 CHECK: OpName [[TEST_1:%\w+]] "test_1" 4560 CHECK: OpName [[TEST_0:%\w+]] "test_0" 4561 CHECK: OpName [[TEST_2:%\w+]] "test_2" 4562 CHECK: [[PHI:%\w+]] = OpPhi 4563 CHECK-NEXT: OpLoopMerge 4564 CHECK: [[TEST_0_STORE:%\w+]] = OpAccessChain {{%\w+}} [[TEST_0]] {{%\w+}} {{%\w+}} 4565 CHECK-NEXT: OpStore [[TEST_0_STORE]] [[PHI]] 4566 CHECK-NOT: OpPhi 4567 CHECK: [[TEST_1_LOAD:%\w+]] = OpLoad {{%\w+}} [[TEST_1]] 4568 CHECK: OpStore [[TEST_2]] [[TEST_1_LOAD]] 4569 )"; 4570 // clang-format on 4571 4572 Match(checks, context.get()); 4573 } 4574 } 4575 4576 } // namespace 4577 } // namespace opt 4578 } // namespace spvtools 4579
