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