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 <memory> 16#include <vector> 17 18#include "source/opt/loop_dependence.h" 19#include "source/opt/loop_descriptor.h" 20#include "source/opt/scalar_analysis.h" 21#include "test/opt/assembly_builder.h" 22#include "test/opt/function_utils.h" 23#include "test/opt/pass_fixture.h" 24#include "test/opt/pass_utils.h" 25 26namespace spvtools { 27namespace opt { 28namespace { 29 30using DependencyAnalysisHelpers = ::testing::Test; 31 32/* 33 Generated from the following GLSL fragment shader 34 with --eliminate-local-multi-store 35#version 440 core 36void a() { 37 int[10][10] arr; 38 int i = 0; 39 int j = 0; 40 for (; i < 10 && j < 10; i++, j++) { 41 arr[i][j] = arr[i][j]; 42 } 43} 44void b() { 45 int[10] arr; 46 for (int i = 0; i < 10; i+=2) { 47 arr[i] = arr[i]; 48 } 49} 50void main(){ 51 a(); 52 b(); 53} 54*/ 55TEST(DependencyAnalysisHelpers, UnsupportedLoops) { 56 const std::string text = R"( OpCapability Shader 57 %1 = OpExtInstImport "GLSL.std.450" 58 OpMemoryModel Logical GLSL450 59 OpEntryPoint Fragment %4 "main" 60 OpExecutionMode %4 OriginUpperLeft 61 OpSource GLSL 440 62 OpName %4 "main" 63 OpName %6 "a(" 64 OpName %8 "b(" 65 OpName %12 "i" 66 OpName %14 "j" 67 OpName %32 "arr" 68 OpName %45 "i" 69 OpName %54 "arr" 70 %2 = OpTypeVoid 71 %3 = OpTypeFunction %2 72 %10 = OpTypeInt 32 1 73 %11 = OpTypePointer Function %10 74 %13 = OpConstant %10 0 75 %21 = OpConstant %10 10 76 %22 = OpTypeBool 77 %27 = OpTypeInt 32 0 78 %28 = OpConstant %27 10 79 %29 = OpTypeArray %10 %28 80 %30 = OpTypeArray %29 %28 81 %31 = OpTypePointer Function %30 82 %41 = OpConstant %10 1 83 %53 = OpTypePointer Function %29 84 %60 = OpConstant %10 2 85 %4 = OpFunction %2 None %3 86 %5 = OpLabel 87 %63 = OpFunctionCall %2 %6 88 %64 = OpFunctionCall %2 %8 89 OpReturn 90 OpFunctionEnd 91 %6 = OpFunction %2 None %3 92 %7 = OpLabel 93 %12 = OpVariable %11 Function 94 %14 = OpVariable %11 Function 95 %32 = OpVariable %31 Function 96 OpStore %12 %13 97 OpStore %14 %13 98 OpBranch %15 99 %15 = OpLabel 100 %65 = OpPhi %10 %13 %7 %42 %18 101 %66 = OpPhi %10 %13 %7 %44 %18 102 OpLoopMerge %17 %18 None 103 OpBranch %19 104 %19 = OpLabel 105 %23 = OpSLessThan %22 %65 %21 106 %25 = OpSLessThan %22 %66 %21 107 %26 = OpLogicalAnd %22 %23 %25 108 OpBranchConditional %26 %16 %17 109 %16 = OpLabel 110 %37 = OpAccessChain %11 %32 %65 %66 111 %38 = OpLoad %10 %37 112 %39 = OpAccessChain %11 %32 %65 %66 113 OpStore %39 %38 114 OpBranch %18 115 %18 = OpLabel 116 %42 = OpIAdd %10 %65 %41 117 OpStore %12 %42 118 %44 = OpIAdd %10 %66 %41 119 OpStore %14 %44 120 OpBranch %15 121 %17 = OpLabel 122 OpReturn 123 OpFunctionEnd 124 %8 = OpFunction %2 None %3 125 %9 = OpLabel 126 %45 = OpVariable %11 Function 127 %54 = OpVariable %53 Function 128 OpStore %45 %13 129 OpBranch %46 130 %46 = OpLabel 131 %67 = OpPhi %10 %13 %9 %62 %49 132 OpLoopMerge %48 %49 None 133 OpBranch %50 134 %50 = OpLabel 135 %52 = OpSLessThan %22 %67 %21 136 OpBranchConditional %52 %47 %48 137 %47 = OpLabel 138 %57 = OpAccessChain %11 %54 %67 139 %58 = OpLoad %10 %57 140 %59 = OpAccessChain %11 %54 %67 141 OpStore %59 %58 142 OpBranch %49 143 %49 = OpLabel 144 %62 = OpIAdd %10 %67 %60 145 OpStore %45 %62 146 OpBranch %46 147 %48 = OpLabel 148 OpReturn 149 OpFunctionEnd 150)"; 151 std::unique_ptr<IRContext> context = 152 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 153 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 154 Module* module = context->module(); 155 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 156 << text << std::endl; 157 { 158 // Function a 159 const Function* f = spvtest::GetFunction(module, 6); 160 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 161 162 Loop* loop = &ld.GetLoopByIndex(0); 163 std::vector<const Loop*> loops{loop}; 164 LoopDependenceAnalysis analysis{context.get(), loops}; 165 166 const Instruction* store[1] = {nullptr}; 167 int stores_found = 0; 168 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 16)) { 169 if (inst.opcode() == spv::Op::OpStore) { 170 store[stores_found] = &inst; 171 ++stores_found; 172 } 173 } 174 // 38 -> 39 175 DistanceVector distance_vector{loops.size()}; 176 EXPECT_FALSE(analysis.IsSupportedLoop(loops[0])); 177 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(38), 178 store[0], &distance_vector)); 179 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information, 180 DistanceEntry::DependenceInformation::UNKNOWN); 181 EXPECT_EQ(distance_vector.GetEntries()[0].direction, 182 DistanceEntry::Directions::ALL); 183 } 184 { 185 // Function b 186 const Function* f = spvtest::GetFunction(module, 8); 187 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 188 189 Loop* loop = &ld.GetLoopByIndex(0); 190 std::vector<const Loop*> loops{loop}; 191 LoopDependenceAnalysis analysis{context.get(), loops}; 192 193 const Instruction* store[1] = {nullptr}; 194 int stores_found = 0; 195 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 47)) { 196 if (inst.opcode() == spv::Op::OpStore) { 197 store[stores_found] = &inst; 198 ++stores_found; 199 } 200 } 201 // 58 -> 59 202 DistanceVector distance_vector{loops.size()}; 203 EXPECT_FALSE(analysis.IsSupportedLoop(loops[0])); 204 EXPECT_FALSE(analysis.GetDependence(context->get_def_use_mgr()->GetDef(58), 205 store[0], &distance_vector)); 206 EXPECT_EQ(distance_vector.GetEntries()[0].dependence_information, 207 DistanceEntry::DependenceInformation::UNKNOWN); 208 EXPECT_EQ(distance_vector.GetEntries()[0].direction, 209 DistanceEntry::Directions::ALL); 210 } 211} 212 213/* 214 Generated from the following GLSL fragment shader 215 with --eliminate-local-multi-store 216#version 440 core 217void a() { 218 for (int i = -10; i < 0; i++) { 219 220 } 221} 222void b() { 223 for (int i = -5; i < 5; i++) { 224 225 } 226} 227void c() { 228 for (int i = 0; i < 10; i++) { 229 230 } 231} 232void d() { 233 for (int i = 5; i < 15; i++) { 234 235 } 236} 237void e() { 238 for (int i = -10; i <= 0; i++) { 239 240 } 241} 242void f() { 243 for (int i = -5; i <= 5; i++) { 244 245 } 246} 247void g() { 248 for (int i = 0; i <= 10; i++) { 249 250 } 251} 252void h() { 253 for (int i = 5; i <= 15; i++) { 254 255 } 256} 257void i() { 258 for (int i = 0; i > -10; i--) { 259 260 } 261} 262void j() { 263 for (int i = 5; i > -5; i--) { 264 265 } 266} 267void k() { 268 for (int i = 10; i > 0; i--) { 269 270 } 271} 272void l() { 273 for (int i = 15; i > 5; i--) { 274 275 } 276} 277void m() { 278 for (int i = 0; i >= -10; i--) { 279 280 } 281} 282void n() { 283 for (int i = 5; i >= -5; i--) { 284 285 } 286} 287void o() { 288 for (int i = 10; i >= 0; i--) { 289 290 } 291} 292void p() { 293 for (int i = 15; i >= 5; i--) { 294 295 } 296} 297void main(){ 298 a(); 299 b(); 300 c(); 301 d(); 302 e(); 303 f(); 304 g(); 305 h(); 306 i(); 307 j(); 308 k(); 309 l(); 310 m(); 311 n(); 312 o(); 313 p(); 314} 315*/ 316TEST(DependencyAnalysisHelpers, loop_information) { 317 const std::string text = R"( OpCapability Shader 318 %1 = OpExtInstImport "GLSL.std.450" 319 OpMemoryModel Logical GLSL450 320 OpEntryPoint Fragment %4 "main" 321 OpExecutionMode %4 OriginUpperLeft 322 OpSource GLSL 440 323 OpName %4 "main" 324 OpName %6 "a(" 325 OpName %8 "b(" 326 OpName %10 "c(" 327 OpName %12 "d(" 328 OpName %14 "e(" 329 OpName %16 "f(" 330 OpName %18 "g(" 331 OpName %20 "h(" 332 OpName %22 "i(" 333 OpName %24 "j(" 334 OpName %26 "k(" 335 OpName %28 "l(" 336 OpName %30 "m(" 337 OpName %32 "n(" 338 OpName %34 "o(" 339 OpName %36 "p(" 340 OpName %40 "i" 341 OpName %54 "i" 342 OpName %66 "i" 343 OpName %77 "i" 344 OpName %88 "i" 345 OpName %98 "i" 346 OpName %108 "i" 347 OpName %118 "i" 348 OpName %128 "i" 349 OpName %138 "i" 350 OpName %148 "i" 351 OpName %158 "i" 352 OpName %168 "i" 353 OpName %178 "i" 354 OpName %188 "i" 355 OpName %198 "i" 356 %2 = OpTypeVoid 357 %3 = OpTypeFunction %2 358 %38 = OpTypeInt 32 1 359 %39 = OpTypePointer Function %38 360 %41 = OpConstant %38 -10 361 %48 = OpConstant %38 0 362 %49 = OpTypeBool 363 %52 = OpConstant %38 1 364 %55 = OpConstant %38 -5 365 %62 = OpConstant %38 5 366 %73 = OpConstant %38 10 367 %84 = OpConstant %38 15 368 %4 = OpFunction %2 None %3 369 %5 = OpLabel 370 %208 = OpFunctionCall %2 %6 371 %209 = OpFunctionCall %2 %8 372 %210 = OpFunctionCall %2 %10 373 %211 = OpFunctionCall %2 %12 374 %212 = OpFunctionCall %2 %14 375 %213 = OpFunctionCall %2 %16 376 %214 = OpFunctionCall %2 %18 377 %215 = OpFunctionCall %2 %20 378 %216 = OpFunctionCall %2 %22 379 %217 = OpFunctionCall %2 %24 380 %218 = OpFunctionCall %2 %26 381 %219 = OpFunctionCall %2 %28 382 %220 = OpFunctionCall %2 %30 383 %221 = OpFunctionCall %2 %32 384 %222 = OpFunctionCall %2 %34 385 %223 = OpFunctionCall %2 %36 386 OpReturn 387 OpFunctionEnd 388 %6 = OpFunction %2 None %3 389 %7 = OpLabel 390 %40 = OpVariable %39 Function 391 OpStore %40 %41 392 OpBranch %42 393 %42 = OpLabel 394 %224 = OpPhi %38 %41 %7 %53 %45 395 OpLoopMerge %44 %45 None 396 OpBranch %46 397 %46 = OpLabel 398 %50 = OpSLessThan %49 %224 %48 399 OpBranchConditional %50 %43 %44 400 %43 = OpLabel 401 OpBranch %45 402 %45 = OpLabel 403 %53 = OpIAdd %38 %224 %52 404 OpStore %40 %53 405 OpBranch %42 406 %44 = OpLabel 407 OpReturn 408 OpFunctionEnd 409 %8 = OpFunction %2 None %3 410 %9 = OpLabel 411 %54 = OpVariable %39 Function 412 OpStore %54 %55 413 OpBranch %56 414 %56 = OpLabel 415 %225 = OpPhi %38 %55 %9 %65 %59 416 OpLoopMerge %58 %59 None 417 OpBranch %60 418 %60 = OpLabel 419 %63 = OpSLessThan %49 %225 %62 420 OpBranchConditional %63 %57 %58 421 %57 = OpLabel 422 OpBranch %59 423 %59 = OpLabel 424 %65 = OpIAdd %38 %225 %52 425 OpStore %54 %65 426 OpBranch %56 427 %58 = OpLabel 428 OpReturn 429 OpFunctionEnd 430 %10 = OpFunction %2 None %3 431 %11 = OpLabel 432 %66 = OpVariable %39 Function 433 OpStore %66 %48 434 OpBranch %67 435 %67 = OpLabel 436 %226 = OpPhi %38 %48 %11 %76 %70 437 OpLoopMerge %69 %70 None 438 OpBranch %71 439 %71 = OpLabel 440 %74 = OpSLessThan %49 %226 %73 441 OpBranchConditional %74 %68 %69 442 %68 = OpLabel 443 OpBranch %70 444 %70 = OpLabel 445 %76 = OpIAdd %38 %226 %52 446 OpStore %66 %76 447 OpBranch %67 448 %69 = OpLabel 449 OpReturn 450 OpFunctionEnd 451 %12 = OpFunction %2 None %3 452 %13 = OpLabel 453 %77 = OpVariable %39 Function 454 OpStore %77 %62 455 OpBranch %78 456 %78 = OpLabel 457 %227 = OpPhi %38 %62 %13 %87 %81 458 OpLoopMerge %80 %81 None 459 OpBranch %82 460 %82 = OpLabel 461 %85 = OpSLessThan %49 %227 %84 462 OpBranchConditional %85 %79 %80 463 %79 = OpLabel 464 OpBranch %81 465 %81 = OpLabel 466 %87 = OpIAdd %38 %227 %52 467 OpStore %77 %87 468 OpBranch %78 469 %80 = OpLabel 470 OpReturn 471 OpFunctionEnd 472 %14 = OpFunction %2 None %3 473 %15 = OpLabel 474 %88 = OpVariable %39 Function 475 OpStore %88 %41 476 OpBranch %89 477 %89 = OpLabel 478 %228 = OpPhi %38 %41 %15 %97 %92 479 OpLoopMerge %91 %92 None 480 OpBranch %93 481 %93 = OpLabel 482 %95 = OpSLessThanEqual %49 %228 %48 483 OpBranchConditional %95 %90 %91 484 %90 = OpLabel 485 OpBranch %92 486 %92 = OpLabel 487 %97 = OpIAdd %38 %228 %52 488 OpStore %88 %97 489 OpBranch %89 490 %91 = OpLabel 491 OpReturn 492 OpFunctionEnd 493 %16 = OpFunction %2 None %3 494 %17 = OpLabel 495 %98 = OpVariable %39 Function 496 OpStore %98 %55 497 OpBranch %99 498 %99 = OpLabel 499 %229 = OpPhi %38 %55 %17 %107 %102 500 OpLoopMerge %101 %102 None 501 OpBranch %103 502 %103 = OpLabel 503 %105 = OpSLessThanEqual %49 %229 %62 504 OpBranchConditional %105 %100 %101 505 %100 = OpLabel 506 OpBranch %102 507 %102 = OpLabel 508 %107 = OpIAdd %38 %229 %52 509 OpStore %98 %107 510 OpBranch %99 511 %101 = OpLabel 512 OpReturn 513 OpFunctionEnd 514 %18 = OpFunction %2 None %3 515 %19 = OpLabel 516 %108 = OpVariable %39 Function 517 OpStore %108 %48 518 OpBranch %109 519 %109 = OpLabel 520 %230 = OpPhi %38 %48 %19 %117 %112 521 OpLoopMerge %111 %112 None 522 OpBranch %113 523 %113 = OpLabel 524 %115 = OpSLessThanEqual %49 %230 %73 525 OpBranchConditional %115 %110 %111 526 %110 = OpLabel 527 OpBranch %112 528 %112 = OpLabel 529 %117 = OpIAdd %38 %230 %52 530 OpStore %108 %117 531 OpBranch %109 532 %111 = OpLabel 533 OpReturn 534 OpFunctionEnd 535 %20 = OpFunction %2 None %3 536 %21 = OpLabel 537 %118 = OpVariable %39 Function 538 OpStore %118 %62 539 OpBranch %119 540 %119 = OpLabel 541 %231 = OpPhi %38 %62 %21 %127 %122 542 OpLoopMerge %121 %122 None 543 OpBranch %123 544 %123 = OpLabel 545 %125 = OpSLessThanEqual %49 %231 %84 546 OpBranchConditional %125 %120 %121 547 %120 = OpLabel 548 OpBranch %122 549 %122 = OpLabel 550 %127 = OpIAdd %38 %231 %52 551 OpStore %118 %127 552 OpBranch %119 553 %121 = OpLabel 554 OpReturn 555 OpFunctionEnd 556 %22 = OpFunction %2 None %3 557 %23 = OpLabel 558 %128 = OpVariable %39 Function 559 OpStore %128 %48 560 OpBranch %129 561 %129 = OpLabel 562 %232 = OpPhi %38 %48 %23 %137 %132 563 OpLoopMerge %131 %132 None 564 OpBranch %133 565 %133 = OpLabel 566 %135 = OpSGreaterThan %49 %232 %41 567 OpBranchConditional %135 %130 %131 568 %130 = OpLabel 569 OpBranch %132 570 %132 = OpLabel 571 %137 = OpISub %38 %232 %52 572 OpStore %128 %137 573 OpBranch %129 574 %131 = OpLabel 575 OpReturn 576 OpFunctionEnd 577 %24 = OpFunction %2 None %3 578 %25 = OpLabel 579 %138 = OpVariable %39 Function 580 OpStore %138 %62 581 OpBranch %139 582 %139 = OpLabel 583 %233 = OpPhi %38 %62 %25 %147 %142 584 OpLoopMerge %141 %142 None 585 OpBranch %143 586 %143 = OpLabel 587 %145 = OpSGreaterThan %49 %233 %55 588 OpBranchConditional %145 %140 %141 589 %140 = OpLabel 590 OpBranch %142 591 %142 = OpLabel 592 %147 = OpISub %38 %233 %52 593 OpStore %138 %147 594 OpBranch %139 595 %141 = OpLabel 596 OpReturn 597 OpFunctionEnd 598 %26 = OpFunction %2 None %3 599 %27 = OpLabel 600 %148 = OpVariable %39 Function 601 OpStore %148 %73 602 OpBranch %149 603 %149 = OpLabel 604 %234 = OpPhi %38 %73 %27 %157 %152 605 OpLoopMerge %151 %152 None 606 OpBranch %153 607 %153 = OpLabel 608 %155 = OpSGreaterThan %49 %234 %48 609 OpBranchConditional %155 %150 %151 610 %150 = OpLabel 611 OpBranch %152 612 %152 = OpLabel 613 %157 = OpISub %38 %234 %52 614 OpStore %148 %157 615 OpBranch %149 616 %151 = OpLabel 617 OpReturn 618 OpFunctionEnd 619 %28 = OpFunction %2 None %3 620 %29 = OpLabel 621 %158 = OpVariable %39 Function 622 OpStore %158 %84 623 OpBranch %159 624 %159 = OpLabel 625 %235 = OpPhi %38 %84 %29 %167 %162 626 OpLoopMerge %161 %162 None 627 OpBranch %163 628 %163 = OpLabel 629 %165 = OpSGreaterThan %49 %235 %62 630 OpBranchConditional %165 %160 %161 631 %160 = OpLabel 632 OpBranch %162 633 %162 = OpLabel 634 %167 = OpISub %38 %235 %52 635 OpStore %158 %167 636 OpBranch %159 637 %161 = OpLabel 638 OpReturn 639 OpFunctionEnd 640 %30 = OpFunction %2 None %3 641 %31 = OpLabel 642 %168 = OpVariable %39 Function 643 OpStore %168 %48 644 OpBranch %169 645 %169 = OpLabel 646 %236 = OpPhi %38 %48 %31 %177 %172 647 OpLoopMerge %171 %172 None 648 OpBranch %173 649 %173 = OpLabel 650 %175 = OpSGreaterThanEqual %49 %236 %41 651 OpBranchConditional %175 %170 %171 652 %170 = OpLabel 653 OpBranch %172 654 %172 = OpLabel 655 %177 = OpISub %38 %236 %52 656 OpStore %168 %177 657 OpBranch %169 658 %171 = OpLabel 659 OpReturn 660 OpFunctionEnd 661 %32 = OpFunction %2 None %3 662 %33 = OpLabel 663 %178 = OpVariable %39 Function 664 OpStore %178 %62 665 OpBranch %179 666 %179 = OpLabel 667 %237 = OpPhi %38 %62 %33 %187 %182 668 OpLoopMerge %181 %182 None 669 OpBranch %183 670 %183 = OpLabel 671 %185 = OpSGreaterThanEqual %49 %237 %55 672 OpBranchConditional %185 %180 %181 673 %180 = OpLabel 674 OpBranch %182 675 %182 = OpLabel 676 %187 = OpISub %38 %237 %52 677 OpStore %178 %187 678 OpBranch %179 679 %181 = OpLabel 680 OpReturn 681 OpFunctionEnd 682 %34 = OpFunction %2 None %3 683 %35 = OpLabel 684 %188 = OpVariable %39 Function 685 OpStore %188 %73 686 OpBranch %189 687 %189 = OpLabel 688 %238 = OpPhi %38 %73 %35 %197 %192 689 OpLoopMerge %191 %192 None 690 OpBranch %193 691 %193 = OpLabel 692 %195 = OpSGreaterThanEqual %49 %238 %48 693 OpBranchConditional %195 %190 %191 694 %190 = OpLabel 695 OpBranch %192 696 %192 = OpLabel 697 %197 = OpISub %38 %238 %52 698 OpStore %188 %197 699 OpBranch %189 700 %191 = OpLabel 701 OpReturn 702 OpFunctionEnd 703 %36 = OpFunction %2 None %3 704 %37 = OpLabel 705 %198 = OpVariable %39 Function 706 OpStore %198 %84 707 OpBranch %199 708 %199 = OpLabel 709 %239 = OpPhi %38 %84 %37 %207 %202 710 OpLoopMerge %201 %202 None 711 OpBranch %203 712 %203 = OpLabel 713 %205 = OpSGreaterThanEqual %49 %239 %62 714 OpBranchConditional %205 %200 %201 715 %200 = OpLabel 716 OpBranch %202 717 %202 = OpLabel 718 %207 = OpISub %38 %239 %52 719 OpStore %198 %207 720 OpBranch %199 721 %201 = OpLabel 722 OpReturn 723 OpFunctionEnd 724)"; 725 std::unique_ptr<IRContext> context = 726 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 727 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 728 Module* module = context->module(); 729 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 730 << text << std::endl; 731 { 732 // Function a 733 const Function* f = spvtest::GetFunction(module, 6); 734 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 735 Loop* loop = &ld.GetLoopByIndex(0); 736 std::vector<const Loop*> loops{loop}; 737 LoopDependenceAnalysis analysis{context.get(), loops}; 738 739 EXPECT_EQ( 740 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 741 -10); 742 EXPECT_EQ( 743 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 744 -1); 745 746 EXPECT_EQ( 747 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 748 10); 749 750 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 751 analysis.GetScalarEvolution()->CreateConstant(-10)); 752 753 EXPECT_EQ(analysis.GetFinalTripInductionNode( 754 loop, analysis.GetScalarEvolution()->CreateConstant(1)), 755 analysis.GetScalarEvolution()->CreateConstant(-1)); 756 } 757 { 758 // Function b 759 const Function* f = spvtest::GetFunction(module, 8); 760 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 761 Loop* loop = &ld.GetLoopByIndex(0); 762 std::vector<const Loop*> loops{loop}; 763 LoopDependenceAnalysis analysis{context.get(), loops}; 764 765 EXPECT_EQ( 766 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 767 -5); 768 EXPECT_EQ( 769 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 770 4); 771 772 EXPECT_EQ( 773 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 774 10); 775 776 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 777 analysis.GetScalarEvolution()->CreateConstant(-5)); 778 779 EXPECT_EQ(analysis.GetFinalTripInductionNode( 780 loop, analysis.GetScalarEvolution()->CreateConstant(1)), 781 analysis.GetScalarEvolution()->CreateConstant(4)); 782 } 783 { 784 // Function c 785 const Function* f = spvtest::GetFunction(module, 10); 786 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 787 Loop* loop = &ld.GetLoopByIndex(0); 788 std::vector<const Loop*> loops{loop}; 789 LoopDependenceAnalysis analysis{context.get(), loops}; 790 791 EXPECT_EQ( 792 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 793 0); 794 EXPECT_EQ( 795 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 796 9); 797 798 EXPECT_EQ( 799 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 800 10); 801 802 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 803 analysis.GetScalarEvolution()->CreateConstant(0)); 804 805 EXPECT_EQ(analysis.GetFinalTripInductionNode( 806 loop, analysis.GetScalarEvolution()->CreateConstant(1)), 807 analysis.GetScalarEvolution()->CreateConstant(9)); 808 } 809 { 810 // Function d 811 const Function* f = spvtest::GetFunction(module, 12); 812 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 813 Loop* loop = &ld.GetLoopByIndex(0); 814 std::vector<const Loop*> loops{loop}; 815 LoopDependenceAnalysis analysis{context.get(), loops}; 816 817 EXPECT_EQ( 818 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 819 5); 820 EXPECT_EQ( 821 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 822 14); 823 824 EXPECT_EQ( 825 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 826 10); 827 828 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 829 analysis.GetScalarEvolution()->CreateConstant(5)); 830 831 EXPECT_EQ(analysis.GetFinalTripInductionNode( 832 loop, analysis.GetScalarEvolution()->CreateConstant(1)), 833 analysis.GetScalarEvolution()->CreateConstant(14)); 834 } 835 { 836 // Function e 837 const Function* f = spvtest::GetFunction(module, 14); 838 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 839 Loop* loop = &ld.GetLoopByIndex(0); 840 std::vector<const Loop*> loops{loop}; 841 LoopDependenceAnalysis analysis{context.get(), loops}; 842 843 EXPECT_EQ( 844 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 845 -10); 846 EXPECT_EQ( 847 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 848 0); 849 850 EXPECT_EQ( 851 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 852 11); 853 854 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 855 analysis.GetScalarEvolution()->CreateConstant(-10)); 856 857 EXPECT_EQ(analysis.GetFinalTripInductionNode( 858 loop, analysis.GetScalarEvolution()->CreateConstant(1)), 859 analysis.GetScalarEvolution()->CreateConstant(0)); 860 } 861 { 862 // Function f 863 const Function* f = spvtest::GetFunction(module, 16); 864 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 865 Loop* loop = &ld.GetLoopByIndex(0); 866 std::vector<const Loop*> loops{loop}; 867 LoopDependenceAnalysis analysis{context.get(), loops}; 868 869 EXPECT_EQ( 870 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 871 -5); 872 EXPECT_EQ( 873 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 874 5); 875 876 EXPECT_EQ( 877 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 878 11); 879 880 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 881 analysis.GetScalarEvolution()->CreateConstant(-5)); 882 883 EXPECT_EQ(analysis.GetFinalTripInductionNode( 884 loop, analysis.GetScalarEvolution()->CreateConstant(1)), 885 analysis.GetScalarEvolution()->CreateConstant(5)); 886 } 887 { 888 // Function g 889 const Function* f = spvtest::GetFunction(module, 18); 890 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 891 Loop* loop = &ld.GetLoopByIndex(0); 892 std::vector<const Loop*> loops{loop}; 893 LoopDependenceAnalysis analysis{context.get(), loops}; 894 895 EXPECT_EQ( 896 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 897 0); 898 EXPECT_EQ( 899 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 900 10); 901 902 EXPECT_EQ( 903 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 904 11); 905 906 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 907 analysis.GetScalarEvolution()->CreateConstant(0)); 908 909 EXPECT_EQ(analysis.GetFinalTripInductionNode( 910 loop, analysis.GetScalarEvolution()->CreateConstant(1)), 911 analysis.GetScalarEvolution()->CreateConstant(10)); 912 } 913 { 914 // Function h 915 const Function* f = spvtest::GetFunction(module, 20); 916 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 917 Loop* loop = &ld.GetLoopByIndex(0); 918 std::vector<const Loop*> loops{loop}; 919 LoopDependenceAnalysis analysis{context.get(), loops}; 920 921 EXPECT_EQ( 922 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 923 5); 924 EXPECT_EQ( 925 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 926 15); 927 928 EXPECT_EQ( 929 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 930 11); 931 932 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 933 analysis.GetScalarEvolution()->CreateConstant(5)); 934 935 EXPECT_EQ(analysis.GetFinalTripInductionNode( 936 loop, analysis.GetScalarEvolution()->CreateConstant(1)), 937 analysis.GetScalarEvolution()->CreateConstant(15)); 938 } 939 { 940 // Function i 941 const Function* f = spvtest::GetFunction(module, 22); 942 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 943 Loop* loop = &ld.GetLoopByIndex(0); 944 std::vector<const Loop*> loops{loop}; 945 LoopDependenceAnalysis analysis{context.get(), loops}; 946 947 EXPECT_EQ( 948 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 949 0); 950 EXPECT_EQ( 951 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 952 -9); 953 954 EXPECT_EQ( 955 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 956 10); 957 958 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 959 analysis.GetScalarEvolution()->CreateConstant(0)); 960 961 EXPECT_EQ(analysis.GetFinalTripInductionNode( 962 loop, analysis.GetScalarEvolution()->CreateConstant(-1)), 963 analysis.GetScalarEvolution()->CreateConstant(-9)); 964 } 965 { 966 // Function j 967 const Function* f = spvtest::GetFunction(module, 24); 968 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 969 Loop* loop = &ld.GetLoopByIndex(0); 970 std::vector<const Loop*> loops{loop}; 971 LoopDependenceAnalysis analysis{context.get(), loops}; 972 973 EXPECT_EQ( 974 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 975 5); 976 EXPECT_EQ( 977 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 978 -4); 979 980 EXPECT_EQ( 981 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 982 10); 983 984 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 985 analysis.GetScalarEvolution()->CreateConstant(5)); 986 987 EXPECT_EQ(analysis.GetFinalTripInductionNode( 988 loop, analysis.GetScalarEvolution()->CreateConstant(-1)), 989 analysis.GetScalarEvolution()->CreateConstant(-4)); 990 } 991 { 992 // Function k 993 const Function* f = spvtest::GetFunction(module, 26); 994 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 995 Loop* loop = &ld.GetLoopByIndex(0); 996 std::vector<const Loop*> loops{loop}; 997 LoopDependenceAnalysis analysis{context.get(), loops}; 998 999 EXPECT_EQ( 1000 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1001 10); 1002 EXPECT_EQ( 1003 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1004 1); 1005 1006 EXPECT_EQ( 1007 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 1008 10); 1009 1010 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 1011 analysis.GetScalarEvolution()->CreateConstant(10)); 1012 1013 EXPECT_EQ(analysis.GetFinalTripInductionNode( 1014 loop, analysis.GetScalarEvolution()->CreateConstant(-1)), 1015 analysis.GetScalarEvolution()->CreateConstant(1)); 1016 } 1017 { 1018 // Function l 1019 const Function* f = spvtest::GetFunction(module, 28); 1020 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1021 Loop* loop = &ld.GetLoopByIndex(0); 1022 std::vector<const Loop*> loops{loop}; 1023 LoopDependenceAnalysis analysis{context.get(), loops}; 1024 1025 EXPECT_EQ( 1026 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1027 15); 1028 EXPECT_EQ( 1029 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1030 6); 1031 1032 EXPECT_EQ( 1033 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 1034 10); 1035 1036 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 1037 analysis.GetScalarEvolution()->CreateConstant(15)); 1038 1039 EXPECT_EQ(analysis.GetFinalTripInductionNode( 1040 loop, analysis.GetScalarEvolution()->CreateConstant(-1)), 1041 analysis.GetScalarEvolution()->CreateConstant(6)); 1042 } 1043 { 1044 // Function m 1045 const Function* f = spvtest::GetFunction(module, 30); 1046 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1047 Loop* loop = &ld.GetLoopByIndex(0); 1048 std::vector<const Loop*> loops{loop}; 1049 LoopDependenceAnalysis analysis{context.get(), loops}; 1050 1051 EXPECT_EQ( 1052 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1053 0); 1054 EXPECT_EQ( 1055 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1056 -10); 1057 1058 EXPECT_EQ( 1059 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 1060 11); 1061 1062 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 1063 analysis.GetScalarEvolution()->CreateConstant(0)); 1064 1065 EXPECT_EQ(analysis.GetFinalTripInductionNode( 1066 loop, analysis.GetScalarEvolution()->CreateConstant(-1)), 1067 analysis.GetScalarEvolution()->CreateConstant(-10)); 1068 } 1069 { 1070 // Function n 1071 const Function* f = spvtest::GetFunction(module, 32); 1072 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1073 Loop* loop = &ld.GetLoopByIndex(0); 1074 std::vector<const Loop*> loops{loop}; 1075 LoopDependenceAnalysis analysis{context.get(), loops}; 1076 1077 EXPECT_EQ( 1078 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1079 5); 1080 EXPECT_EQ( 1081 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1082 -5); 1083 1084 EXPECT_EQ( 1085 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 1086 11); 1087 1088 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 1089 analysis.GetScalarEvolution()->CreateConstant(5)); 1090 1091 EXPECT_EQ(analysis.GetFinalTripInductionNode( 1092 loop, analysis.GetScalarEvolution()->CreateConstant(-1)), 1093 analysis.GetScalarEvolution()->CreateConstant(-5)); 1094 } 1095 { 1096 // Function o 1097 const Function* f = spvtest::GetFunction(module, 34); 1098 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1099 Loop* loop = &ld.GetLoopByIndex(0); 1100 std::vector<const Loop*> loops{loop}; 1101 LoopDependenceAnalysis analysis{context.get(), loops}; 1102 1103 EXPECT_EQ( 1104 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1105 10); 1106 EXPECT_EQ( 1107 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1108 0); 1109 1110 EXPECT_EQ( 1111 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 1112 11); 1113 1114 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 1115 analysis.GetScalarEvolution()->CreateConstant(10)); 1116 1117 EXPECT_EQ(analysis.GetFinalTripInductionNode( 1118 loop, analysis.GetScalarEvolution()->CreateConstant(-1)), 1119 analysis.GetScalarEvolution()->CreateConstant(0)); 1120 } 1121 { 1122 // Function p 1123 const Function* f = spvtest::GetFunction(module, 36); 1124 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1125 Loop* loop = &ld.GetLoopByIndex(0); 1126 std::vector<const Loop*> loops{loop}; 1127 LoopDependenceAnalysis analysis{context.get(), loops}; 1128 1129 EXPECT_EQ( 1130 analysis.GetLowerBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1131 15); 1132 EXPECT_EQ( 1133 analysis.GetUpperBound(loop)->AsSEConstantNode()->FoldToSingleValue(), 1134 5); 1135 1136 EXPECT_EQ( 1137 analysis.GetTripCount(loop)->AsSEConstantNode()->FoldToSingleValue(), 1138 11); 1139 1140 EXPECT_EQ(analysis.GetFirstTripInductionNode(loop), 1141 analysis.GetScalarEvolution()->CreateConstant(15)); 1142 1143 EXPECT_EQ(analysis.GetFinalTripInductionNode( 1144 loop, analysis.GetScalarEvolution()->CreateConstant(-1)), 1145 analysis.GetScalarEvolution()->CreateConstant(5)); 1146 } 1147} 1148 1149/* 1150 Generated from the following GLSL fragment shader 1151 with --eliminate-local-multi-store 1152#version 440 core 1153void main(){ 1154 for (int i = 0; i < 10; i++) { 1155 1156 } 1157} 1158*/ 1159TEST(DependencyAnalysisHelpers, bounds_checks) { 1160 const std::string text = R"( OpCapability Shader 1161 %1 = OpExtInstImport "GLSL.std.450" 1162 OpMemoryModel Logical GLSL450 1163 OpEntryPoint Fragment %4 "main" 1164 OpExecutionMode %4 OriginUpperLeft 1165 OpSource GLSL 440 1166 OpName %4 "main" 1167 OpName %8 "i" 1168 %2 = OpTypeVoid 1169 %3 = OpTypeFunction %2 1170 %6 = OpTypeInt 32 1 1171 %7 = OpTypePointer Function %6 1172 %9 = OpConstant %6 0 1173 %16 = OpConstant %6 10 1174 %17 = OpTypeBool 1175 %20 = OpConstant %6 1 1176 %4 = OpFunction %2 None %3 1177 %5 = OpLabel 1178 %8 = OpVariable %7 Function 1179 OpStore %8 %9 1180 OpBranch %10 1181 %10 = OpLabel 1182 %22 = OpPhi %6 %9 %5 %21 %13 1183 OpLoopMerge %12 %13 None 1184 OpBranch %14 1185 %14 = OpLabel 1186 %18 = OpSLessThan %17 %22 %16 1187 OpBranchConditional %18 %11 %12 1188 %11 = OpLabel 1189 OpBranch %13 1190 %13 = OpLabel 1191 %21 = OpIAdd %6 %22 %20 1192 OpStore %8 %21 1193 OpBranch %10 1194 %12 = OpLabel 1195 OpReturn 1196 OpFunctionEnd 1197)"; 1198 std::unique_ptr<IRContext> context = 1199 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 1200 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 1201 Module* module = context->module(); 1202 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 1203 << text << std::endl; 1204 // We need a shader that includes a loop for this test so we can build a 1205 // LoopDependenceAnalaysis 1206 const Function* f = spvtest::GetFunction(module, 4); 1207 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1208 Loop* loop = &ld.GetLoopByIndex(0); 1209 std::vector<const Loop*> loops{loop}; 1210 LoopDependenceAnalysis analysis{context.get(), loops}; 1211 1212 EXPECT_TRUE(analysis.IsWithinBounds(0, 0, 0)); 1213 EXPECT_TRUE(analysis.IsWithinBounds(0, -1, 0)); 1214 EXPECT_TRUE(analysis.IsWithinBounds(0, 0, 1)); 1215 EXPECT_TRUE(analysis.IsWithinBounds(0, -1, 1)); 1216 EXPECT_TRUE(analysis.IsWithinBounds(-2, -2, -2)); 1217 EXPECT_TRUE(analysis.IsWithinBounds(-2, -3, 0)); 1218 EXPECT_TRUE(analysis.IsWithinBounds(-2, 0, -3)); 1219 EXPECT_TRUE(analysis.IsWithinBounds(2, 2, 2)); 1220 EXPECT_TRUE(analysis.IsWithinBounds(2, 3, 0)); 1221 1222 EXPECT_FALSE(analysis.IsWithinBounds(2, 3, 3)); 1223 EXPECT_FALSE(analysis.IsWithinBounds(0, 1, 5)); 1224 EXPECT_FALSE(analysis.IsWithinBounds(0, -1, -4)); 1225 EXPECT_FALSE(analysis.IsWithinBounds(-2, -4, -3)); 1226} 1227 1228/* 1229 Generated from the following GLSL fragment shader 1230 with --eliminate-local-multi-store 1231#version 440 core 1232layout(location = 0) in vec4 in_vec; 1233// Loop iterates from constant to symbolic 1234void a() { 1235 int N = int(in_vec.x); 1236 int arr[10]; 1237 for (int i = 0; i < N; i++) { // Bounds are N - 0 - 1 1238 arr[i] = arr[i+N]; // |distance| = N 1239 arr[i+N] = arr[i]; // |distance| = N 1240 } 1241} 1242void b() { 1243 int N = int(in_vec.x); 1244 int arr[10]; 1245 for (int i = 0; i <= N; i++) { // Bounds are N - 0 1246 arr[i] = arr[i+N]; // |distance| = N 1247 arr[i+N] = arr[i]; // |distance| = N 1248 } 1249} 1250void c() { 1251 int N = int(in_vec.x); 1252 int arr[10]; 1253 for (int i = 9; i > N; i--) { // Bounds are 9 - N - 1 1254 arr[i] = arr[i+N]; // |distance| = N 1255 arr[i+N] = arr[i]; // |distance| = N 1256 } 1257} 1258void d() { 1259 int N = int(in_vec.x); 1260 int arr[10]; 1261 for (int i = 9; i >= N; i--) { // Bounds are 9 - N 1262 arr[i] = arr[i+N]; // |distance| = N 1263 arr[i+N] = arr[i]; // |distance| = N 1264 } 1265} 1266void main(){ 1267 a(); 1268 b(); 1269 c(); 1270 d(); 1271} 1272*/ 1273TEST(DependencyAnalysisHelpers, const_to_symbolic) { 1274 const std::string text = R"( OpCapability Shader 1275 %1 = OpExtInstImport "GLSL.std.450" 1276 OpMemoryModel Logical GLSL450 1277 OpEntryPoint Fragment %4 "main" %20 1278 OpExecutionMode %4 OriginUpperLeft 1279 OpSource GLSL 440 1280 OpName %4 "main" 1281 OpName %6 "a(" 1282 OpName %8 "b(" 1283 OpName %10 "c(" 1284 OpName %12 "d(" 1285 OpName %16 "N" 1286 OpName %20 "in_vec" 1287 OpName %27 "i" 1288 OpName %41 "arr" 1289 OpName %59 "N" 1290 OpName %63 "i" 1291 OpName %72 "arr" 1292 OpName %89 "N" 1293 OpName %93 "i" 1294 OpName %103 "arr" 1295 OpName %120 "N" 1296 OpName %124 "i" 1297 OpName %133 "arr" 1298 OpDecorate %20 Location 0 1299 %2 = OpTypeVoid 1300 %3 = OpTypeFunction %2 1301 %14 = OpTypeInt 32 1 1302 %15 = OpTypePointer Function %14 1303 %17 = OpTypeFloat 32 1304 %18 = OpTypeVector %17 4 1305 %19 = OpTypePointer Input %18 1306 %20 = OpVariable %19 Input 1307 %21 = OpTypeInt 32 0 1308 %22 = OpConstant %21 0 1309 %23 = OpTypePointer Input %17 1310 %28 = OpConstant %14 0 1311 %36 = OpTypeBool 1312 %38 = OpConstant %21 10 1313 %39 = OpTypeArray %14 %38 1314 %40 = OpTypePointer Function %39 1315 %57 = OpConstant %14 1 1316 %94 = OpConstant %14 9 1317 %4 = OpFunction %2 None %3 1318 %5 = OpLabel 1319 %150 = OpFunctionCall %2 %6 1320 %151 = OpFunctionCall %2 %8 1321 %152 = OpFunctionCall %2 %10 1322 %153 = OpFunctionCall %2 %12 1323 OpReturn 1324 OpFunctionEnd 1325 %6 = OpFunction %2 None %3 1326 %7 = OpLabel 1327 %16 = OpVariable %15 Function 1328 %27 = OpVariable %15 Function 1329 %41 = OpVariable %40 Function 1330 %24 = OpAccessChain %23 %20 %22 1331 %25 = OpLoad %17 %24 1332 %26 = OpConvertFToS %14 %25 1333 OpStore %16 %26 1334 OpStore %27 %28 1335 OpBranch %29 1336 %29 = OpLabel 1337 %154 = OpPhi %14 %28 %7 %58 %32 1338 OpLoopMerge %31 %32 None 1339 OpBranch %33 1340 %33 = OpLabel 1341 %37 = OpSLessThan %36 %154 %26 1342 OpBranchConditional %37 %30 %31 1343 %30 = OpLabel 1344 %45 = OpIAdd %14 %154 %26 1345 %46 = OpAccessChain %15 %41 %45 1346 %47 = OpLoad %14 %46 1347 %48 = OpAccessChain %15 %41 %154 1348 OpStore %48 %47 1349 %51 = OpIAdd %14 %154 %26 1350 %53 = OpAccessChain %15 %41 %154 1351 %54 = OpLoad %14 %53 1352 %55 = OpAccessChain %15 %41 %51 1353 OpStore %55 %54 1354 OpBranch %32 1355 %32 = OpLabel 1356 %58 = OpIAdd %14 %154 %57 1357 OpStore %27 %58 1358 OpBranch %29 1359 %31 = OpLabel 1360 OpReturn 1361 OpFunctionEnd 1362 %8 = OpFunction %2 None %3 1363 %9 = OpLabel 1364 %59 = OpVariable %15 Function 1365 %63 = OpVariable %15 Function 1366 %72 = OpVariable %40 Function 1367 %60 = OpAccessChain %23 %20 %22 1368 %61 = OpLoad %17 %60 1369 %62 = OpConvertFToS %14 %61 1370 OpStore %59 %62 1371 OpStore %63 %28 1372 OpBranch %64 1373 %64 = OpLabel 1374 %155 = OpPhi %14 %28 %9 %88 %67 1375 OpLoopMerge %66 %67 None 1376 OpBranch %68 1377 %68 = OpLabel 1378 %71 = OpSLessThanEqual %36 %155 %62 1379 OpBranchConditional %71 %65 %66 1380 %65 = OpLabel 1381 %76 = OpIAdd %14 %155 %62 1382 %77 = OpAccessChain %15 %72 %76 1383 %78 = OpLoad %14 %77 1384 %79 = OpAccessChain %15 %72 %155 1385 OpStore %79 %78 1386 %82 = OpIAdd %14 %155 %62 1387 %84 = OpAccessChain %15 %72 %155 1388 %85 = OpLoad %14 %84 1389 %86 = OpAccessChain %15 %72 %82 1390 OpStore %86 %85 1391 OpBranch %67 1392 %67 = OpLabel 1393 %88 = OpIAdd %14 %155 %57 1394 OpStore %63 %88 1395 OpBranch %64 1396 %66 = OpLabel 1397 OpReturn 1398 OpFunctionEnd 1399 %10 = OpFunction %2 None %3 1400 %11 = OpLabel 1401 %89 = OpVariable %15 Function 1402 %93 = OpVariable %15 Function 1403 %103 = OpVariable %40 Function 1404 %90 = OpAccessChain %23 %20 %22 1405 %91 = OpLoad %17 %90 1406 %92 = OpConvertFToS %14 %91 1407 OpStore %89 %92 1408 OpStore %93 %94 1409 OpBranch %95 1410 %95 = OpLabel 1411 %156 = OpPhi %14 %94 %11 %119 %98 1412 OpLoopMerge %97 %98 None 1413 OpBranch %99 1414 %99 = OpLabel 1415 %102 = OpSGreaterThan %36 %156 %92 1416 OpBranchConditional %102 %96 %97 1417 %96 = OpLabel 1418 %107 = OpIAdd %14 %156 %92 1419 %108 = OpAccessChain %15 %103 %107 1420 %109 = OpLoad %14 %108 1421 %110 = OpAccessChain %15 %103 %156 1422 OpStore %110 %109 1423 %113 = OpIAdd %14 %156 %92 1424 %115 = OpAccessChain %15 %103 %156 1425 %116 = OpLoad %14 %115 1426 %117 = OpAccessChain %15 %103 %113 1427 OpStore %117 %116 1428 OpBranch %98 1429 %98 = OpLabel 1430 %119 = OpISub %14 %156 %57 1431 OpStore %93 %119 1432 OpBranch %95 1433 %97 = OpLabel 1434 OpReturn 1435 OpFunctionEnd 1436 %12 = OpFunction %2 None %3 1437 %13 = OpLabel 1438 %120 = OpVariable %15 Function 1439 %124 = OpVariable %15 Function 1440 %133 = OpVariable %40 Function 1441 %121 = OpAccessChain %23 %20 %22 1442 %122 = OpLoad %17 %121 1443 %123 = OpConvertFToS %14 %122 1444 OpStore %120 %123 1445 OpStore %124 %94 1446 OpBranch %125 1447 %125 = OpLabel 1448 %157 = OpPhi %14 %94 %13 %149 %128 1449 OpLoopMerge %127 %128 None 1450 OpBranch %129 1451 %129 = OpLabel 1452 %132 = OpSGreaterThanEqual %36 %157 %123 1453 OpBranchConditional %132 %126 %127 1454 %126 = OpLabel 1455 %137 = OpIAdd %14 %157 %123 1456 %138 = OpAccessChain %15 %133 %137 1457 %139 = OpLoad %14 %138 1458 %140 = OpAccessChain %15 %133 %157 1459 OpStore %140 %139 1460 %143 = OpIAdd %14 %157 %123 1461 %145 = OpAccessChain %15 %133 %157 1462 %146 = OpLoad %14 %145 1463 %147 = OpAccessChain %15 %133 %143 1464 OpStore %147 %146 1465 OpBranch %128 1466 %128 = OpLabel 1467 %149 = OpISub %14 %157 %57 1468 OpStore %124 %149 1469 OpBranch %125 1470 %127 = OpLabel 1471 OpReturn 1472 OpFunctionEnd 1473)"; 1474 std::unique_ptr<IRContext> context = 1475 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 1476 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 1477 Module* module = context->module(); 1478 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 1479 << text << std::endl; 1480 1481 { 1482 // Function a 1483 const Function* f = spvtest::GetFunction(module, 6); 1484 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1485 Loop* loop = &ld.GetLoopByIndex(0); 1486 std::vector<const Loop*> loops{loop}; 1487 LoopDependenceAnalysis analysis{context.get(), loops}; 1488 1489 const Instruction* stores[2]; 1490 int stores_found = 0; 1491 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 30)) { 1492 if (inst.opcode() == spv::Op::OpStore) { 1493 stores[stores_found] = &inst; 1494 ++stores_found; 1495 } 1496 } 1497 1498 for (int i = 0; i < 2; ++i) { 1499 EXPECT_TRUE(stores[i]); 1500 } 1501 1502 // 47 -> 48 1503 { 1504 // Analyse and simplify the instruction behind the access chain of this 1505 // load. 1506 Instruction* load_var = context->get_def_use_mgr()->GetDef( 1507 context->get_def_use_mgr() 1508 ->GetDef(context->get_def_use_mgr() 1509 ->GetDef(47) 1510 ->GetSingleWordInOperand(0)) 1511 ->GetSingleWordInOperand(1)); 1512 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 1513 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 1514 1515 // Analyse and simplify the instruction behind the access chain of this 1516 // store. 1517 Instruction* store_var = context->get_def_use_mgr()->GetDef( 1518 context->get_def_use_mgr() 1519 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 1520 ->GetSingleWordInOperand(1)); 1521 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 1522 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 1523 1524 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 1525 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 1526 1527 // Independent and supported. 1528 EXPECT_TRUE(analysis.IsProvablyOutsideOfLoopBounds( 1529 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 1530 } 1531 1532 // 54 -> 55 1533 { 1534 // Analyse and simplify the instruction behind the access chain of this 1535 // load. 1536 Instruction* load_var = context->get_def_use_mgr()->GetDef( 1537 context->get_def_use_mgr() 1538 ->GetDef(context->get_def_use_mgr() 1539 ->GetDef(54) 1540 ->GetSingleWordInOperand(0)) 1541 ->GetSingleWordInOperand(1)); 1542 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 1543 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 1544 1545 // Analyse and simplify the instruction behind the access chain of this 1546 // store. 1547 Instruction* store_var = context->get_def_use_mgr()->GetDef( 1548 context->get_def_use_mgr() 1549 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 1550 ->GetSingleWordInOperand(1)); 1551 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 1552 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 1553 1554 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 1555 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 1556 1557 // Independent but not supported. 1558 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 1559 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 1560 } 1561 } 1562 { 1563 // Function b 1564 const Function* f = spvtest::GetFunction(module, 8); 1565 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1566 Loop* loop = &ld.GetLoopByIndex(0); 1567 std::vector<const Loop*> loops{loop}; 1568 LoopDependenceAnalysis analysis{context.get(), loops}; 1569 1570 const Instruction* stores[2]; 1571 int stores_found = 0; 1572 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 65)) { 1573 if (inst.opcode() == spv::Op::OpStore) { 1574 stores[stores_found] = &inst; 1575 ++stores_found; 1576 } 1577 } 1578 1579 for (int i = 0; i < 2; ++i) { 1580 EXPECT_TRUE(stores[i]); 1581 } 1582 1583 // 78 -> 79 1584 { 1585 // Analyse and simplify the instruction behind the access chain of this 1586 // load. 1587 Instruction* load_var = context->get_def_use_mgr()->GetDef( 1588 context->get_def_use_mgr() 1589 ->GetDef(context->get_def_use_mgr() 1590 ->GetDef(78) 1591 ->GetSingleWordInOperand(0)) 1592 ->GetSingleWordInOperand(1)); 1593 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 1594 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 1595 // Analyse and simplify the instruction behind the access chain of this 1596 // store. 1597 Instruction* store_var = context->get_def_use_mgr()->GetDef( 1598 context->get_def_use_mgr() 1599 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 1600 ->GetSingleWordInOperand(1)); 1601 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 1602 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 1603 1604 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 1605 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 1606 1607 // Dependent. 1608 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 1609 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 1610 } 1611 1612 // 85 -> 86 1613 { 1614 // Analyse and simplify the instruction behind the access chain of this 1615 // load. 1616 Instruction* load_var = context->get_def_use_mgr()->GetDef( 1617 context->get_def_use_mgr() 1618 ->GetDef(context->get_def_use_mgr() 1619 ->GetDef(85) 1620 ->GetSingleWordInOperand(0)) 1621 ->GetSingleWordInOperand(1)); 1622 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 1623 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 1624 // Analyse and simplify the instruction behind the access chain of this 1625 // store. 1626 Instruction* store_var = context->get_def_use_mgr()->GetDef( 1627 context->get_def_use_mgr() 1628 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 1629 ->GetSingleWordInOperand(1)); 1630 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 1631 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 1632 1633 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 1634 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 1635 1636 // Dependent. 1637 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 1638 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 1639 } 1640 } 1641 { 1642 // Function c 1643 const Function* f = spvtest::GetFunction(module, 10); 1644 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1645 Loop* loop = &ld.GetLoopByIndex(0); 1646 std::vector<const Loop*> loops{loop}; 1647 LoopDependenceAnalysis analysis{context.get(), loops}; 1648 1649 const Instruction* stores[2]; 1650 int stores_found = 0; 1651 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 96)) { 1652 if (inst.opcode() == spv::Op::OpStore) { 1653 stores[stores_found] = &inst; 1654 ++stores_found; 1655 } 1656 } 1657 1658 for (int i = 0; i < 2; ++i) { 1659 EXPECT_TRUE(stores[i]); 1660 } 1661 1662 // 109 -> 110 1663 { 1664 // Analyse and simplify the instruction behind the access chain of this 1665 // load. 1666 Instruction* load_var = context->get_def_use_mgr()->GetDef( 1667 context->get_def_use_mgr() 1668 ->GetDef(context->get_def_use_mgr() 1669 ->GetDef(109) 1670 ->GetSingleWordInOperand(0)) 1671 ->GetSingleWordInOperand(1)); 1672 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 1673 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 1674 // Analyse and simplify the instruction behind the access chain of this 1675 // store. 1676 Instruction* store_var = context->get_def_use_mgr()->GetDef( 1677 context->get_def_use_mgr() 1678 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 1679 ->GetSingleWordInOperand(1)); 1680 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 1681 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 1682 1683 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 1684 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 1685 1686 // Independent but not supported. 1687 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 1688 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 1689 } 1690 1691 // 116 -> 117 1692 { 1693 // Analyse and simplify the instruction behind the access chain of this 1694 // load. 1695 Instruction* load_var = context->get_def_use_mgr()->GetDef( 1696 context->get_def_use_mgr() 1697 ->GetDef(context->get_def_use_mgr() 1698 ->GetDef(116) 1699 ->GetSingleWordInOperand(0)) 1700 ->GetSingleWordInOperand(1)); 1701 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 1702 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 1703 // Analyse and simplify the instruction behind the access chain of this 1704 // store. 1705 Instruction* store_var = context->get_def_use_mgr()->GetDef( 1706 context->get_def_use_mgr() 1707 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 1708 ->GetSingleWordInOperand(1)); 1709 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 1710 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 1711 1712 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 1713 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 1714 1715 // Independent but not supported. 1716 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 1717 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 1718 } 1719 } 1720 { 1721 // Function d 1722 const Function* f = spvtest::GetFunction(module, 12); 1723 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 1724 Loop* loop = &ld.GetLoopByIndex(0); 1725 std::vector<const Loop*> loops{loop}; 1726 LoopDependenceAnalysis analysis{context.get(), loops}; 1727 1728 const Instruction* stores[2]; 1729 int stores_found = 0; 1730 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 126)) { 1731 if (inst.opcode() == spv::Op::OpStore) { 1732 stores[stores_found] = &inst; 1733 ++stores_found; 1734 } 1735 } 1736 1737 for (int i = 0; i < 2; ++i) { 1738 EXPECT_TRUE(stores[i]); 1739 } 1740 1741 // 139 -> 140 1742 { 1743 // Analyse and simplify the instruction behind the access chain of this 1744 // load. 1745 Instruction* load_var = context->get_def_use_mgr()->GetDef( 1746 context->get_def_use_mgr() 1747 ->GetDef(context->get_def_use_mgr() 1748 ->GetDef(139) 1749 ->GetSingleWordInOperand(0)) 1750 ->GetSingleWordInOperand(1)); 1751 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 1752 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 1753 // Analyse and simplify the instruction behind the access chain of this 1754 // store. 1755 Instruction* store_var = context->get_def_use_mgr()->GetDef( 1756 context->get_def_use_mgr() 1757 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 1758 ->GetSingleWordInOperand(1)); 1759 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 1760 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 1761 1762 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 1763 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 1764 1765 // Dependent. 1766 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 1767 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 1768 } 1769 1770 // 146 -> 147 1771 { 1772 // Analyse and simplify the instruction behind the access chain of this 1773 // load. 1774 Instruction* load_var = context->get_def_use_mgr()->GetDef( 1775 context->get_def_use_mgr() 1776 ->GetDef(context->get_def_use_mgr() 1777 ->GetDef(146) 1778 ->GetSingleWordInOperand(0)) 1779 ->GetSingleWordInOperand(1)); 1780 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 1781 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 1782 // Analyse and simplify the instruction behind the access chain of this 1783 // store. 1784 Instruction* store_var = context->get_def_use_mgr()->GetDef( 1785 context->get_def_use_mgr() 1786 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 1787 ->GetSingleWordInOperand(1)); 1788 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 1789 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 1790 1791 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 1792 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 1793 1794 // Dependent. 1795 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 1796 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 1797 } 1798 } 1799} 1800 1801/* 1802 Generated from the following GLSL fragment shader 1803 with --eliminate-local-multi-store 1804#version 440 core 1805layout(location = 0) in vec4 in_vec; 1806// Loop iterates from symbolic to constant 1807void a() { 1808 int N = int(in_vec.x); 1809 int arr[10]; 1810 for (int i = N; i < 9; i++) { // Bounds are 9 - N - 1 1811 arr[i] = arr[i+N]; // |distance| = N 1812 arr[i+N] = arr[i]; // |distance| = N 1813 } 1814} 1815void b() { 1816 int N = int(in_vec.x); 1817 int arr[10]; 1818 for (int i = N; i <= 9; i++) { // Bounds are 9 - N 1819 arr[i] = arr[i+N]; // |distance| = N 1820 arr[i+N] = arr[i]; // |distance| = N 1821 } 1822} 1823void c() { 1824 int N = int(in_vec.x); 1825 int arr[10]; 1826 for (int i = N; i > 0; i--) { // Bounds are N - 0 - 1 1827 arr[i] = arr[i+N]; // |distance| = N 1828 arr[i+N] = arr[i]; // |distance| = N 1829 } 1830} 1831void d() { 1832 int N = int(in_vec.x); 1833 int arr[10]; 1834 for (int i = N; i >= 0; i--) { // Bounds are N - 0 1835 arr[i] = arr[i+N]; // |distance| = N 1836 arr[i+N] = arr[i]; // |distance| = N 1837 } 1838} 1839void main(){ 1840 a(); 1841 b(); 1842 c(); 1843 d(); 1844} 1845*/ 1846TEST(DependencyAnalysisHelpers, symbolic_to_const) { 1847 const std::string text = R"( OpCapability Shader 1848 %1 = OpExtInstImport "GLSL.std.450" 1849 OpMemoryModel Logical GLSL450 1850 OpEntryPoint Fragment %4 "main" %20 1851 OpExecutionMode %4 OriginUpperLeft 1852 OpSource GLSL 440 1853 OpName %4 "main" 1854 OpName %6 "a(" 1855 OpName %8 "b(" 1856 OpName %10 "c(" 1857 OpName %12 "d(" 1858 OpName %16 "N" 1859 OpName %20 "in_vec" 1860 OpName %27 "i" 1861 OpName %41 "arr" 1862 OpName %59 "N" 1863 OpName %63 "i" 1864 OpName %72 "arr" 1865 OpName %89 "N" 1866 OpName %93 "i" 1867 OpName %103 "arr" 1868 OpName %120 "N" 1869 OpName %124 "i" 1870 OpName %133 "arr" 1871 OpDecorate %20 Location 0 1872 %2 = OpTypeVoid 1873 %3 = OpTypeFunction %2 1874 %14 = OpTypeInt 32 1 1875 %15 = OpTypePointer Function %14 1876 %17 = OpTypeFloat 32 1877 %18 = OpTypeVector %17 4 1878 %19 = OpTypePointer Input %18 1879 %20 = OpVariable %19 Input 1880 %21 = OpTypeInt 32 0 1881 %22 = OpConstant %21 0 1882 %23 = OpTypePointer Input %17 1883 %35 = OpConstant %14 9 1884 %36 = OpTypeBool 1885 %38 = OpConstant %21 10 1886 %39 = OpTypeArray %14 %38 1887 %40 = OpTypePointer Function %39 1888 %57 = OpConstant %14 1 1889 %101 = OpConstant %14 0 1890 %4 = OpFunction %2 None %3 1891 %5 = OpLabel 1892 %150 = OpFunctionCall %2 %6 1893 %151 = OpFunctionCall %2 %8 1894 %152 = OpFunctionCall %2 %10 1895 %153 = OpFunctionCall %2 %12 1896 OpReturn 1897 OpFunctionEnd 1898 %6 = OpFunction %2 None %3 1899 %7 = OpLabel 1900 %16 = OpVariable %15 Function 1901 %27 = OpVariable %15 Function 1902 %41 = OpVariable %40 Function 1903 %24 = OpAccessChain %23 %20 %22 1904 %25 = OpLoad %17 %24 1905 %26 = OpConvertFToS %14 %25 1906 OpStore %16 %26 1907 OpStore %27 %26 1908 OpBranch %29 1909 %29 = OpLabel 1910 %154 = OpPhi %14 %26 %7 %58 %32 1911 OpLoopMerge %31 %32 None 1912 OpBranch %33 1913 %33 = OpLabel 1914 %37 = OpSLessThan %36 %154 %35 1915 OpBranchConditional %37 %30 %31 1916 %30 = OpLabel 1917 %45 = OpIAdd %14 %154 %26 1918 %46 = OpAccessChain %15 %41 %45 1919 %47 = OpLoad %14 %46 1920 %48 = OpAccessChain %15 %41 %154 1921 OpStore %48 %47 1922 %51 = OpIAdd %14 %154 %26 1923 %53 = OpAccessChain %15 %41 %154 1924 %54 = OpLoad %14 %53 1925 %55 = OpAccessChain %15 %41 %51 1926 OpStore %55 %54 1927 OpBranch %32 1928 %32 = OpLabel 1929 %58 = OpIAdd %14 %154 %57 1930 OpStore %27 %58 1931 OpBranch %29 1932 %31 = OpLabel 1933 OpReturn 1934 OpFunctionEnd 1935 %8 = OpFunction %2 None %3 1936 %9 = OpLabel 1937 %59 = OpVariable %15 Function 1938 %63 = OpVariable %15 Function 1939 %72 = OpVariable %40 Function 1940 %60 = OpAccessChain %23 %20 %22 1941 %61 = OpLoad %17 %60 1942 %62 = OpConvertFToS %14 %61 1943 OpStore %59 %62 1944 OpStore %63 %62 1945 OpBranch %65 1946 %65 = OpLabel 1947 %155 = OpPhi %14 %62 %9 %88 %68 1948 OpLoopMerge %67 %68 None 1949 OpBranch %69 1950 %69 = OpLabel 1951 %71 = OpSLessThanEqual %36 %155 %35 1952 OpBranchConditional %71 %66 %67 1953 %66 = OpLabel 1954 %76 = OpIAdd %14 %155 %62 1955 %77 = OpAccessChain %15 %72 %76 1956 %78 = OpLoad %14 %77 1957 %79 = OpAccessChain %15 %72 %155 1958 OpStore %79 %78 1959 %82 = OpIAdd %14 %155 %62 1960 %84 = OpAccessChain %15 %72 %155 1961 %85 = OpLoad %14 %84 1962 %86 = OpAccessChain %15 %72 %82 1963 OpStore %86 %85 1964 OpBranch %68 1965 %68 = OpLabel 1966 %88 = OpIAdd %14 %155 %57 1967 OpStore %63 %88 1968 OpBranch %65 1969 %67 = OpLabel 1970 OpReturn 1971 OpFunctionEnd 1972 %10 = OpFunction %2 None %3 1973 %11 = OpLabel 1974 %89 = OpVariable %15 Function 1975 %93 = OpVariable %15 Function 1976 %103 = OpVariable %40 Function 1977 %90 = OpAccessChain %23 %20 %22 1978 %91 = OpLoad %17 %90 1979 %92 = OpConvertFToS %14 %91 1980 OpStore %89 %92 1981 OpStore %93 %92 1982 OpBranch %95 1983 %95 = OpLabel 1984 %156 = OpPhi %14 %92 %11 %119 %98 1985 OpLoopMerge %97 %98 None 1986 OpBranch %99 1987 %99 = OpLabel 1988 %102 = OpSGreaterThan %36 %156 %101 1989 OpBranchConditional %102 %96 %97 1990 %96 = OpLabel 1991 %107 = OpIAdd %14 %156 %92 1992 %108 = OpAccessChain %15 %103 %107 1993 %109 = OpLoad %14 %108 1994 %110 = OpAccessChain %15 %103 %156 1995 OpStore %110 %109 1996 %113 = OpIAdd %14 %156 %92 1997 %115 = OpAccessChain %15 %103 %156 1998 %116 = OpLoad %14 %115 1999 %117 = OpAccessChain %15 %103 %113 2000 OpStore %117 %116 2001 OpBranch %98 2002 %98 = OpLabel 2003 %119 = OpISub %14 %156 %57 2004 OpStore %93 %119 2005 OpBranch %95 2006 %97 = OpLabel 2007 OpReturn 2008 OpFunctionEnd 2009 %12 = OpFunction %2 None %3 2010 %13 = OpLabel 2011 %120 = OpVariable %15 Function 2012 %124 = OpVariable %15 Function 2013 %133 = OpVariable %40 Function 2014 %121 = OpAccessChain %23 %20 %22 2015 %122 = OpLoad %17 %121 2016 %123 = OpConvertFToS %14 %122 2017 OpStore %120 %123 2018 OpStore %124 %123 2019 OpBranch %126 2020 %126 = OpLabel 2021 %157 = OpPhi %14 %123 %13 %149 %129 2022 OpLoopMerge %128 %129 None 2023 OpBranch %130 2024 %130 = OpLabel 2025 %132 = OpSGreaterThanEqual %36 %157 %101 2026 OpBranchConditional %132 %127 %128 2027 %127 = OpLabel 2028 %137 = OpIAdd %14 %157 %123 2029 %138 = OpAccessChain %15 %133 %137 2030 %139 = OpLoad %14 %138 2031 %140 = OpAccessChain %15 %133 %157 2032 OpStore %140 %139 2033 %143 = OpIAdd %14 %157 %123 2034 %145 = OpAccessChain %15 %133 %157 2035 %146 = OpLoad %14 %145 2036 %147 = OpAccessChain %15 %133 %143 2037 OpStore %147 %146 2038 OpBranch %129 2039 %129 = OpLabel 2040 %149 = OpISub %14 %157 %57 2041 OpStore %124 %149 2042 OpBranch %126 2043 %128 = OpLabel 2044 OpReturn 2045 OpFunctionEnd 2046)"; 2047 std::unique_ptr<IRContext> context = 2048 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 2049 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 2050 Module* module = context->module(); 2051 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 2052 << text << std::endl; 2053 { 2054 // Function a 2055 const Function* f = spvtest::GetFunction(module, 6); 2056 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 2057 Loop* loop = &ld.GetLoopByIndex(0); 2058 std::vector<const Loop*> loops{loop}; 2059 LoopDependenceAnalysis analysis{context.get(), loops}; 2060 2061 const Instruction* stores[2]; 2062 int stores_found = 0; 2063 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 30)) { 2064 if (inst.opcode() == spv::Op::OpStore) { 2065 stores[stores_found] = &inst; 2066 ++stores_found; 2067 } 2068 } 2069 2070 for (int i = 0; i < 2; ++i) { 2071 EXPECT_TRUE(stores[i]); 2072 } 2073 2074 // 47 -> 48 2075 { 2076 // Analyse and simplify the instruction behind the access chain of this 2077 // load. 2078 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2079 context->get_def_use_mgr() 2080 ->GetDef(context->get_def_use_mgr() 2081 ->GetDef(47) 2082 ->GetSingleWordInOperand(0)) 2083 ->GetSingleWordInOperand(1)); 2084 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2085 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2086 2087 // Analyse and simplify the instruction behind the access chain of this 2088 // store. 2089 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2090 context->get_def_use_mgr() 2091 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 2092 ->GetSingleWordInOperand(1)); 2093 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2094 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2095 2096 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2097 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2098 2099 // Independent but not supported. 2100 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2101 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2102 } 2103 2104 // 54 -> 55 2105 { 2106 // Analyse and simplify the instruction behind the access chain of this 2107 // load. 2108 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2109 context->get_def_use_mgr() 2110 ->GetDef(context->get_def_use_mgr() 2111 ->GetDef(54) 2112 ->GetSingleWordInOperand(0)) 2113 ->GetSingleWordInOperand(1)); 2114 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2115 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2116 2117 // Analyse and simplify the instruction behind the access chain of this 2118 // store. 2119 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2120 context->get_def_use_mgr() 2121 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 2122 ->GetSingleWordInOperand(1)); 2123 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2124 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2125 2126 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2127 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2128 2129 // Independent but not supported. 2130 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2131 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2132 } 2133 } 2134 { 2135 // Function b 2136 const Function* f = spvtest::GetFunction(module, 8); 2137 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 2138 Loop* loop = &ld.GetLoopByIndex(0); 2139 std::vector<const Loop*> loops{loop}; 2140 LoopDependenceAnalysis analysis{context.get(), loops}; 2141 2142 const Instruction* stores[2]; 2143 int stores_found = 0; 2144 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 66)) { 2145 if (inst.opcode() == spv::Op::OpStore) { 2146 stores[stores_found] = &inst; 2147 ++stores_found; 2148 } 2149 } 2150 2151 for (int i = 0; i < 2; ++i) { 2152 EXPECT_TRUE(stores[i]); 2153 } 2154 2155 // 78 -> 79 2156 { 2157 // Analyse and simplify the instruction behind the access chain of this 2158 // load. 2159 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2160 context->get_def_use_mgr() 2161 ->GetDef(context->get_def_use_mgr() 2162 ->GetDef(78) 2163 ->GetSingleWordInOperand(0)) 2164 ->GetSingleWordInOperand(1)); 2165 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2166 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2167 2168 // Analyse and simplify the instruction behind the access chain of this 2169 // store. 2170 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2171 context->get_def_use_mgr() 2172 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 2173 ->GetSingleWordInOperand(1)); 2174 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2175 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2176 2177 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2178 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2179 2180 // Dependent. 2181 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2182 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2183 } 2184 2185 // 85 -> 86 2186 { 2187 // Analyse and simplify the instruction behind the access chain of this 2188 // load. 2189 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2190 context->get_def_use_mgr() 2191 ->GetDef(context->get_def_use_mgr() 2192 ->GetDef(85) 2193 ->GetSingleWordInOperand(0)) 2194 ->GetSingleWordInOperand(1)); 2195 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2196 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2197 2198 // Analyse and simplify the instruction behind the access chain of this 2199 // store. 2200 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2201 context->get_def_use_mgr() 2202 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 2203 ->GetSingleWordInOperand(1)); 2204 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2205 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2206 2207 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2208 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2209 2210 // Dependent. 2211 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2212 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2213 } 2214 } 2215 { 2216 // Function c 2217 const Function* f = spvtest::GetFunction(module, 10); 2218 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 2219 Loop* loop = &ld.GetLoopByIndex(0); 2220 std::vector<const Loop*> loops{loop}; 2221 LoopDependenceAnalysis analysis{context.get(), loops}; 2222 2223 const Instruction* stores[2]; 2224 int stores_found = 0; 2225 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 96)) { 2226 if (inst.opcode() == spv::Op::OpStore) { 2227 stores[stores_found] = &inst; 2228 ++stores_found; 2229 } 2230 } 2231 2232 for (int i = 0; i < 2; ++i) { 2233 EXPECT_TRUE(stores[i]); 2234 } 2235 2236 // 109 -> 110 2237 { 2238 // Analyse and simplify the instruction behind the access chain of this 2239 // load. 2240 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2241 context->get_def_use_mgr() 2242 ->GetDef(context->get_def_use_mgr() 2243 ->GetDef(109) 2244 ->GetSingleWordInOperand(0)) 2245 ->GetSingleWordInOperand(1)); 2246 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2247 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2248 2249 // Analyse and simplify the instruction behind the access chain of this 2250 // store. 2251 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2252 context->get_def_use_mgr() 2253 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 2254 ->GetSingleWordInOperand(1)); 2255 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2256 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2257 2258 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2259 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2260 2261 // Independent and supported. 2262 EXPECT_TRUE(analysis.IsProvablyOutsideOfLoopBounds( 2263 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2264 } 2265 2266 // 116 -> 117 2267 { 2268 // Analyse and simplify the instruction behind the access chain of this 2269 // load. 2270 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2271 context->get_def_use_mgr() 2272 ->GetDef(context->get_def_use_mgr() 2273 ->GetDef(116) 2274 ->GetSingleWordInOperand(0)) 2275 ->GetSingleWordInOperand(1)); 2276 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2277 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2278 2279 // Analyse and simplify the instruction behind the access chain of this 2280 // store. 2281 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2282 context->get_def_use_mgr() 2283 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 2284 ->GetSingleWordInOperand(1)); 2285 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2286 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2287 2288 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2289 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2290 2291 // Independent but not supported. 2292 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2293 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2294 } 2295 } 2296 { 2297 // Function d 2298 const Function* f = spvtest::GetFunction(module, 12); 2299 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 2300 Loop* loop = &ld.GetLoopByIndex(0); 2301 std::vector<const Loop*> loops{loop}; 2302 LoopDependenceAnalysis analysis{context.get(), loops}; 2303 2304 const Instruction* stores[2]; 2305 int stores_found = 0; 2306 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 127)) { 2307 if (inst.opcode() == spv::Op::OpStore) { 2308 stores[stores_found] = &inst; 2309 ++stores_found; 2310 } 2311 } 2312 2313 for (int i = 0; i < 2; ++i) { 2314 EXPECT_TRUE(stores[i]); 2315 } 2316 2317 // 139 -> 140 2318 { 2319 // Analyse and simplify the instruction behind the access chain of this 2320 // load. 2321 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2322 context->get_def_use_mgr() 2323 ->GetDef(context->get_def_use_mgr() 2324 ->GetDef(139) 2325 ->GetSingleWordInOperand(0)) 2326 ->GetSingleWordInOperand(1)); 2327 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2328 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2329 2330 // Analyse and simplify the instruction behind the access chain of this 2331 // store. 2332 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2333 context->get_def_use_mgr() 2334 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 2335 ->GetSingleWordInOperand(1)); 2336 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2337 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2338 2339 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2340 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2341 2342 // Dependent 2343 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2344 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2345 } 2346 2347 // 146 -> 147 2348 { 2349 // Analyse and simplify the instruction behind the access chain of this 2350 // load. 2351 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2352 context->get_def_use_mgr() 2353 ->GetDef(context->get_def_use_mgr() 2354 ->GetDef(146) 2355 ->GetSingleWordInOperand(0)) 2356 ->GetSingleWordInOperand(1)); 2357 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2358 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2359 2360 // Analyse and simplify the instruction behind the access chain of this 2361 // store. 2362 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2363 context->get_def_use_mgr() 2364 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 2365 ->GetSingleWordInOperand(1)); 2366 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2367 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2368 2369 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2370 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2371 2372 // Dependent 2373 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2374 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2375 } 2376 } 2377} 2378 2379/* 2380 Generated from the following GLSL fragment shader 2381 with --eliminate-local-multi-store 2382#version 440 core 2383layout(location = 0) in vec4 in_vec; 2384// Loop iterates from symbolic to symbolic 2385void a() { 2386 int M = int(in_vec.x); 2387 int N = int(in_vec.y); 2388 int arr[10]; 2389 for (int i = M; i < N; i++) { // Bounds are N - M - 1 2390 arr[i+M+N] = arr[i+M+2*N]; // |distance| = N 2391 arr[i+M+2*N] = arr[i+M+N]; // |distance| = N 2392 } 2393} 2394void b() { 2395 int M = int(in_vec.x); 2396 int N = int(in_vec.y); 2397 int arr[10]; 2398 for (int i = M; i <= N; i++) { // Bounds are N - M 2399 arr[i+M+N] = arr[i+M+2*N]; // |distance| = N 2400 arr[i+M+2*N] = arr[i+M+N]; // |distance| = N 2401 } 2402} 2403void c() { 2404 int M = int(in_vec.x); 2405 int N = int(in_vec.y); 2406 int arr[10]; 2407 for (int i = M; i > N; i--) { // Bounds are M - N - 1 2408 arr[i+M+N] = arr[i+M+2*N]; // |distance| = N 2409 arr[i+M+2*N] = arr[i+M+N]; // |distance| = N 2410 } 2411} 2412void d() { 2413 int M = int(in_vec.x); 2414 int N = int(in_vec.y); 2415 int arr[10]; 2416 for (int i = M; i >= N; i--) { // Bounds are M - N 2417 arr[i+M+N] = arr[i+M+2*N]; // |distance| = N 2418 arr[i+M+2*N] = arr[i+M+N]; // |distance| = N 2419 } 2420} 2421void main(){ 2422 a(); 2423 b(); 2424 c(); 2425 d(); 2426} 2427*/ 2428TEST(DependencyAnalysisHelpers, symbolic_to_symbolic) { 2429 const std::string text = R"( OpCapability Shader 2430 %1 = OpExtInstImport "GLSL.std.450" 2431 OpMemoryModel Logical GLSL450 2432 OpEntryPoint Fragment %4 "main" %20 2433 OpExecutionMode %4 OriginUpperLeft 2434 OpSource GLSL 440 2435 OpName %4 "main" 2436 OpName %6 "a(" 2437 OpName %8 "b(" 2438 OpName %10 "c(" 2439 OpName %12 "d(" 2440 OpName %16 "M" 2441 OpName %20 "in_vec" 2442 OpName %27 "N" 2443 OpName %32 "i" 2444 OpName %46 "arr" 2445 OpName %79 "M" 2446 OpName %83 "N" 2447 OpName %87 "i" 2448 OpName %97 "arr" 2449 OpName %128 "M" 2450 OpName %132 "N" 2451 OpName %136 "i" 2452 OpName %146 "arr" 2453 OpName %177 "M" 2454 OpName %181 "N" 2455 OpName %185 "i" 2456 OpName %195 "arr" 2457 OpDecorate %20 Location 0 2458 %2 = OpTypeVoid 2459 %3 = OpTypeFunction %2 2460 %14 = OpTypeInt 32 1 2461 %15 = OpTypePointer Function %14 2462 %17 = OpTypeFloat 32 2463 %18 = OpTypeVector %17 4 2464 %19 = OpTypePointer Input %18 2465 %20 = OpVariable %19 Input 2466 %21 = OpTypeInt 32 0 2467 %22 = OpConstant %21 0 2468 %23 = OpTypePointer Input %17 2469 %28 = OpConstant %21 1 2470 %41 = OpTypeBool 2471 %43 = OpConstant %21 10 2472 %44 = OpTypeArray %14 %43 2473 %45 = OpTypePointer Function %44 2474 %55 = OpConstant %14 2 2475 %77 = OpConstant %14 1 2476 %4 = OpFunction %2 None %3 2477 %5 = OpLabel 2478 %226 = OpFunctionCall %2 %6 2479 %227 = OpFunctionCall %2 %8 2480 %228 = OpFunctionCall %2 %10 2481 %229 = OpFunctionCall %2 %12 2482 OpReturn 2483 OpFunctionEnd 2484 %6 = OpFunction %2 None %3 2485 %7 = OpLabel 2486 %16 = OpVariable %15 Function 2487 %27 = OpVariable %15 Function 2488 %32 = OpVariable %15 Function 2489 %46 = OpVariable %45 Function 2490 %24 = OpAccessChain %23 %20 %22 2491 %25 = OpLoad %17 %24 2492 %26 = OpConvertFToS %14 %25 2493 OpStore %16 %26 2494 %29 = OpAccessChain %23 %20 %28 2495 %30 = OpLoad %17 %29 2496 %31 = OpConvertFToS %14 %30 2497 OpStore %27 %31 2498 OpStore %32 %26 2499 OpBranch %34 2500 %34 = OpLabel 2501 %230 = OpPhi %14 %26 %7 %78 %37 2502 OpLoopMerge %36 %37 None 2503 OpBranch %38 2504 %38 = OpLabel 2505 %42 = OpSLessThan %41 %230 %31 2506 OpBranchConditional %42 %35 %36 2507 %35 = OpLabel 2508 %49 = OpIAdd %14 %230 %26 2509 %51 = OpIAdd %14 %49 %31 2510 %54 = OpIAdd %14 %230 %26 2511 %57 = OpIMul %14 %55 %31 2512 %58 = OpIAdd %14 %54 %57 2513 %59 = OpAccessChain %15 %46 %58 2514 %60 = OpLoad %14 %59 2515 %61 = OpAccessChain %15 %46 %51 2516 OpStore %61 %60 2517 %64 = OpIAdd %14 %230 %26 2518 %66 = OpIMul %14 %55 %31 2519 %67 = OpIAdd %14 %64 %66 2520 %70 = OpIAdd %14 %230 %26 2521 %72 = OpIAdd %14 %70 %31 2522 %73 = OpAccessChain %15 %46 %72 2523 %74 = OpLoad %14 %73 2524 %75 = OpAccessChain %15 %46 %67 2525 OpStore %75 %74 2526 OpBranch %37 2527 %37 = OpLabel 2528 %78 = OpIAdd %14 %230 %77 2529 OpStore %32 %78 2530 OpBranch %34 2531 %36 = OpLabel 2532 OpReturn 2533 OpFunctionEnd 2534 %8 = OpFunction %2 None %3 2535 %9 = OpLabel 2536 %79 = OpVariable %15 Function 2537 %83 = OpVariable %15 Function 2538 %87 = OpVariable %15 Function 2539 %97 = OpVariable %45 Function 2540 %80 = OpAccessChain %23 %20 %22 2541 %81 = OpLoad %17 %80 2542 %82 = OpConvertFToS %14 %81 2543 OpStore %79 %82 2544 %84 = OpAccessChain %23 %20 %28 2545 %85 = OpLoad %17 %84 2546 %86 = OpConvertFToS %14 %85 2547 OpStore %83 %86 2548 OpStore %87 %82 2549 OpBranch %89 2550 %89 = OpLabel 2551 %231 = OpPhi %14 %82 %9 %127 %92 2552 OpLoopMerge %91 %92 None 2553 OpBranch %93 2554 %93 = OpLabel 2555 %96 = OpSLessThanEqual %41 %231 %86 2556 OpBranchConditional %96 %90 %91 2557 %90 = OpLabel 2558 %100 = OpIAdd %14 %231 %82 2559 %102 = OpIAdd %14 %100 %86 2560 %105 = OpIAdd %14 %231 %82 2561 %107 = OpIMul %14 %55 %86 2562 %108 = OpIAdd %14 %105 %107 2563 %109 = OpAccessChain %15 %97 %108 2564 %110 = OpLoad %14 %109 2565 %111 = OpAccessChain %15 %97 %102 2566 OpStore %111 %110 2567 %114 = OpIAdd %14 %231 %82 2568 %116 = OpIMul %14 %55 %86 2569 %117 = OpIAdd %14 %114 %116 2570 %120 = OpIAdd %14 %231 %82 2571 %122 = OpIAdd %14 %120 %86 2572 %123 = OpAccessChain %15 %97 %122 2573 %124 = OpLoad %14 %123 2574 %125 = OpAccessChain %15 %97 %117 2575 OpStore %125 %124 2576 OpBranch %92 2577 %92 = OpLabel 2578 %127 = OpIAdd %14 %231 %77 2579 OpStore %87 %127 2580 OpBranch %89 2581 %91 = OpLabel 2582 OpReturn 2583 OpFunctionEnd 2584 %10 = OpFunction %2 None %3 2585 %11 = OpLabel 2586 %128 = OpVariable %15 Function 2587 %132 = OpVariable %15 Function 2588 %136 = OpVariable %15 Function 2589 %146 = OpVariable %45 Function 2590 %129 = OpAccessChain %23 %20 %22 2591 %130 = OpLoad %17 %129 2592 %131 = OpConvertFToS %14 %130 2593 OpStore %128 %131 2594 %133 = OpAccessChain %23 %20 %28 2595 %134 = OpLoad %17 %133 2596 %135 = OpConvertFToS %14 %134 2597 OpStore %132 %135 2598 OpStore %136 %131 2599 OpBranch %138 2600 %138 = OpLabel 2601 %232 = OpPhi %14 %131 %11 %176 %141 2602 OpLoopMerge %140 %141 None 2603 OpBranch %142 2604 %142 = OpLabel 2605 %145 = OpSGreaterThan %41 %232 %135 2606 OpBranchConditional %145 %139 %140 2607 %139 = OpLabel 2608 %149 = OpIAdd %14 %232 %131 2609 %151 = OpIAdd %14 %149 %135 2610 %154 = OpIAdd %14 %232 %131 2611 %156 = OpIMul %14 %55 %135 2612 %157 = OpIAdd %14 %154 %156 2613 %158 = OpAccessChain %15 %146 %157 2614 %159 = OpLoad %14 %158 2615 %160 = OpAccessChain %15 %146 %151 2616 OpStore %160 %159 2617 %163 = OpIAdd %14 %232 %131 2618 %165 = OpIMul %14 %55 %135 2619 %166 = OpIAdd %14 %163 %165 2620 %169 = OpIAdd %14 %232 %131 2621 %171 = OpIAdd %14 %169 %135 2622 %172 = OpAccessChain %15 %146 %171 2623 %173 = OpLoad %14 %172 2624 %174 = OpAccessChain %15 %146 %166 2625 OpStore %174 %173 2626 OpBranch %141 2627 %141 = OpLabel 2628 %176 = OpISub %14 %232 %77 2629 OpStore %136 %176 2630 OpBranch %138 2631 %140 = OpLabel 2632 OpReturn 2633 OpFunctionEnd 2634 %12 = OpFunction %2 None %3 2635 %13 = OpLabel 2636 %177 = OpVariable %15 Function 2637 %181 = OpVariable %15 Function 2638 %185 = OpVariable %15 Function 2639 %195 = OpVariable %45 Function 2640 %178 = OpAccessChain %23 %20 %22 2641 %179 = OpLoad %17 %178 2642 %180 = OpConvertFToS %14 %179 2643 OpStore %177 %180 2644 %182 = OpAccessChain %23 %20 %28 2645 %183 = OpLoad %17 %182 2646 %184 = OpConvertFToS %14 %183 2647 OpStore %181 %184 2648 OpStore %185 %180 2649 OpBranch %187 2650 %187 = OpLabel 2651 %233 = OpPhi %14 %180 %13 %225 %190 2652 OpLoopMerge %189 %190 None 2653 OpBranch %191 2654 %191 = OpLabel 2655 %194 = OpSGreaterThanEqual %41 %233 %184 2656 OpBranchConditional %194 %188 %189 2657 %188 = OpLabel 2658 %198 = OpIAdd %14 %233 %180 2659 %200 = OpIAdd %14 %198 %184 2660 %203 = OpIAdd %14 %233 %180 2661 %205 = OpIMul %14 %55 %184 2662 %206 = OpIAdd %14 %203 %205 2663 %207 = OpAccessChain %15 %195 %206 2664 %208 = OpLoad %14 %207 2665 %209 = OpAccessChain %15 %195 %200 2666 OpStore %209 %208 2667 %212 = OpIAdd %14 %233 %180 2668 %214 = OpIMul %14 %55 %184 2669 %215 = OpIAdd %14 %212 %214 2670 %218 = OpIAdd %14 %233 %180 2671 %220 = OpIAdd %14 %218 %184 2672 %221 = OpAccessChain %15 %195 %220 2673 %222 = OpLoad %14 %221 2674 %223 = OpAccessChain %15 %195 %215 2675 OpStore %223 %222 2676 OpBranch %190 2677 %190 = OpLabel 2678 %225 = OpISub %14 %233 %77 2679 OpStore %185 %225 2680 OpBranch %187 2681 %189 = OpLabel 2682 OpReturn 2683 OpFunctionEnd 2684)"; 2685 std::unique_ptr<IRContext> context = 2686 BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, text, 2687 SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS); 2688 Module* module = context->module(); 2689 EXPECT_NE(nullptr, module) << "Assembling failed for shader:\n" 2690 << text << std::endl; 2691 { 2692 // Function a 2693 const Function* f = spvtest::GetFunction(module, 6); 2694 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 2695 Loop* loop = &ld.GetLoopByIndex(0); 2696 std::vector<const Loop*> loops{loop}; 2697 LoopDependenceAnalysis analysis{context.get(), loops}; 2698 2699 const Instruction* stores[2]; 2700 int stores_found = 0; 2701 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 35)) { 2702 if (inst.opcode() == spv::Op::OpStore) { 2703 stores[stores_found] = &inst; 2704 ++stores_found; 2705 } 2706 } 2707 2708 for (int i = 0; i < 2; ++i) { 2709 EXPECT_TRUE(stores[i]); 2710 } 2711 2712 // 60 -> 61 2713 { 2714 // Analyse and simplify the instruction behind the access chain of this 2715 // load. 2716 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2717 context->get_def_use_mgr() 2718 ->GetDef(context->get_def_use_mgr() 2719 ->GetDef(60) 2720 ->GetSingleWordInOperand(0)) 2721 ->GetSingleWordInOperand(1)); 2722 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2723 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2724 2725 // Analyse and simplify the instruction behind the access chain of this 2726 // store. 2727 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2728 context->get_def_use_mgr() 2729 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 2730 ->GetSingleWordInOperand(1)); 2731 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2732 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2733 2734 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2735 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2736 2737 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2738 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2739 } 2740 2741 // 74 -> 75 2742 { 2743 // Analyse and simplify the instruction behind the access chain of this 2744 // load. 2745 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2746 context->get_def_use_mgr() 2747 ->GetDef(context->get_def_use_mgr() 2748 ->GetDef(74) 2749 ->GetSingleWordInOperand(0)) 2750 ->GetSingleWordInOperand(1)); 2751 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2752 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2753 2754 // Analyse and simplify the instruction behind the access chain of this 2755 // store. 2756 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2757 context->get_def_use_mgr() 2758 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 2759 ->GetSingleWordInOperand(1)); 2760 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2761 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2762 2763 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2764 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2765 2766 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2767 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2768 } 2769 } 2770 { 2771 // Function b 2772 const Function* f = spvtest::GetFunction(module, 8); 2773 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 2774 Loop* loop = &ld.GetLoopByIndex(0); 2775 std::vector<const Loop*> loops{loop}; 2776 LoopDependenceAnalysis analysis{context.get(), loops}; 2777 2778 const Instruction* stores[2]; 2779 int stores_found = 0; 2780 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 90)) { 2781 if (inst.opcode() == spv::Op::OpStore) { 2782 stores[stores_found] = &inst; 2783 ++stores_found; 2784 } 2785 } 2786 2787 for (int i = 0; i < 2; ++i) { 2788 EXPECT_TRUE(stores[i]); 2789 } 2790 2791 // 110 -> 111 2792 { 2793 // Analyse and simplify the instruction behind the access chain of this 2794 // load. 2795 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2796 context->get_def_use_mgr() 2797 ->GetDef(context->get_def_use_mgr() 2798 ->GetDef(110) 2799 ->GetSingleWordInOperand(0)) 2800 ->GetSingleWordInOperand(1)); 2801 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2802 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2803 2804 // Analyse and simplify the instruction behind the access chain of this 2805 // store. 2806 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2807 context->get_def_use_mgr() 2808 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 2809 ->GetSingleWordInOperand(1)); 2810 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2811 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2812 2813 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2814 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2815 2816 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2817 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2818 } 2819 2820 // 124 -> 125 2821 { 2822 // Analyse and simplify the instruction behind the access chain of this 2823 // load. 2824 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2825 context->get_def_use_mgr() 2826 ->GetDef(context->get_def_use_mgr() 2827 ->GetDef(124) 2828 ->GetSingleWordInOperand(0)) 2829 ->GetSingleWordInOperand(1)); 2830 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2831 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2832 2833 // Analyse and simplify the instruction behind the access chain of this 2834 // store. 2835 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2836 context->get_def_use_mgr() 2837 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 2838 ->GetSingleWordInOperand(1)); 2839 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2840 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2841 2842 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2843 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2844 2845 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2846 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2847 } 2848 } 2849 { 2850 // Function c 2851 const Function* f = spvtest::GetFunction(module, 10); 2852 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 2853 Loop* loop = &ld.GetLoopByIndex(0); 2854 std::vector<const Loop*> loops{loop}; 2855 LoopDependenceAnalysis analysis{context.get(), loops}; 2856 2857 const Instruction* stores[2]; 2858 int stores_found = 0; 2859 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 139)) { 2860 if (inst.opcode() == spv::Op::OpStore) { 2861 stores[stores_found] = &inst; 2862 ++stores_found; 2863 } 2864 } 2865 2866 for (int i = 0; i < 2; ++i) { 2867 EXPECT_TRUE(stores[i]); 2868 } 2869 2870 // 159 -> 160 2871 { 2872 // Analyse and simplify the instruction behind the access chain of this 2873 // load. 2874 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2875 context->get_def_use_mgr() 2876 ->GetDef(context->get_def_use_mgr() 2877 ->GetDef(159) 2878 ->GetSingleWordInOperand(0)) 2879 ->GetSingleWordInOperand(1)); 2880 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2881 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2882 2883 // Analyse and simplify the instruction behind the access chain of this 2884 // store. 2885 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2886 context->get_def_use_mgr() 2887 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 2888 ->GetSingleWordInOperand(1)); 2889 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2890 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2891 2892 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2893 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2894 2895 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2896 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2897 } 2898 2899 // 173 -> 174 2900 { 2901 // Analyse and simplify the instruction behind the access chain of this 2902 // load. 2903 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2904 context->get_def_use_mgr() 2905 ->GetDef(context->get_def_use_mgr() 2906 ->GetDef(173) 2907 ->GetSingleWordInOperand(0)) 2908 ->GetSingleWordInOperand(1)); 2909 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2910 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2911 2912 // Analyse and simplify the instruction behind the access chain of this 2913 // store. 2914 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2915 context->get_def_use_mgr() 2916 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 2917 ->GetSingleWordInOperand(1)); 2918 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2919 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2920 2921 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2922 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2923 2924 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2925 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2926 } 2927 } 2928 { 2929 // Function d 2930 const Function* f = spvtest::GetFunction(module, 12); 2931 LoopDescriptor& ld = *context->GetLoopDescriptor(f); 2932 Loop* loop = &ld.GetLoopByIndex(0); 2933 std::vector<const Loop*> loops{loop}; 2934 LoopDependenceAnalysis analysis{context.get(), loops}; 2935 2936 const Instruction* stores[2]; 2937 int stores_found = 0; 2938 for (const Instruction& inst : *spvtest::GetBasicBlock(f, 188)) { 2939 if (inst.opcode() == spv::Op::OpStore) { 2940 stores[stores_found] = &inst; 2941 ++stores_found; 2942 } 2943 } 2944 2945 for (int i = 0; i < 2; ++i) { 2946 EXPECT_TRUE(stores[i]); 2947 } 2948 2949 // 208 -> 209 2950 { 2951 // Analyse and simplify the instruction behind the access chain of this 2952 // load. 2953 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2954 context->get_def_use_mgr() 2955 ->GetDef(context->get_def_use_mgr() 2956 ->GetDef(208) 2957 ->GetSingleWordInOperand(0)) 2958 ->GetSingleWordInOperand(1)); 2959 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2960 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2961 2962 // Analyse and simplify the instruction behind the access chain of this 2963 // store. 2964 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2965 context->get_def_use_mgr() 2966 ->GetDef(stores[0]->GetSingleWordInOperand(0)) 2967 ->GetSingleWordInOperand(1)); 2968 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2969 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2970 2971 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 2972 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 2973 2974 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 2975 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 2976 } 2977 2978 // 222 -> 223 2979 { 2980 // Analyse and simplify the instruction behind the access chain of this 2981 // load. 2982 Instruction* load_var = context->get_def_use_mgr()->GetDef( 2983 context->get_def_use_mgr() 2984 ->GetDef(context->get_def_use_mgr() 2985 ->GetDef(222) 2986 ->GetSingleWordInOperand(0)) 2987 ->GetSingleWordInOperand(1)); 2988 SENode* load = analysis.GetScalarEvolution()->SimplifyExpression( 2989 analysis.GetScalarEvolution()->AnalyzeInstruction(load_var)); 2990 2991 // Analyse and simplify the instruction behind the access chain of this 2992 // store. 2993 Instruction* store_var = context->get_def_use_mgr()->GetDef( 2994 context->get_def_use_mgr() 2995 ->GetDef(stores[1]->GetSingleWordInOperand(0)) 2996 ->GetSingleWordInOperand(1)); 2997 SENode* store = analysis.GetScalarEvolution()->SimplifyExpression( 2998 analysis.GetScalarEvolution()->AnalyzeInstruction(store_var)); 2999 3000 SENode* delta = analysis.GetScalarEvolution()->SimplifyExpression( 3001 analysis.GetScalarEvolution()->CreateSubtraction(load, store)); 3002 3003 EXPECT_FALSE(analysis.IsProvablyOutsideOfLoopBounds( 3004 loop, delta, store->AsSERecurrentNode()->GetCoefficient())); 3005 } 3006 } 3007} 3008 3009} // namespace 3010} // namespace opt 3011} // namespace spvtools 3012