llvm/unittests/Target/SPIRV/SPIRVConvergenceRegionAnalysisTests.cpp

   1 //===- SPIRVConvergenceRegionAnalysisTests.cpp ----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "Analysis/SPIRVConvergenceRegionAnalysis.h"
  10 #include "llvm/Analysis/DominanceFrontier.h"
  11 #include "llvm/Analysis/PostDominators.h"
  12 #include "llvm/AsmParser/Parser.h"
  13 #include "llvm/IR/Instructions.h"
  14 #include "llvm/IR/LLVMContext.h"
  15 #include "llvm/IR/LegacyPassManager.h"
  16 #include "llvm/IR/Module.h"
  17 #include "llvm/IR/PassInstrumentation.h"
  18 #include "llvm/IR/Type.h"
  19 #include "llvm/IR/TypedPointerType.h"
  20 #include "llvm/Support/SourceMgr.h"
  21
  22 #include "gmock/gmock.h"
  23 #include "gtest/gtest.h"
  24 #include <queue>
  25
  26 using ::testing::Contains;
  27 using ::testing::Pair;
  28
  29 using namespace llvm;
  30 using namespace llvm::SPIRV;
  31
  32 template <typename T> struct IsA {
  33   friend bool operator==(const Value *V, const IsA &) { return isa<T>(V); }
  34 };
  35
  36 class SPIRVConvergenceRegionAnalysisTest : public testing::Test {
  37 protected:
  38   void SetUp() override {
  39     // Required for tests.
  40     FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
  41     MAM.registerPass([&] { return PassInstrumentationAnalysis(); });
  42
  43     // Required for ConvergenceRegionAnalysis.
  44     FAM.registerPass([&] { return DominatorTreeAnalysis(); });
  45     FAM.registerPass([&] { return LoopAnalysis(); });
  46
  47     FAM.registerPass([&] { return SPIRVConvergenceRegionAnalysis(); });
  48   }
  49
  50   void TearDown() override { M.reset(); }
  51
  52   SPIRVConvergenceRegionAnalysis::Result &runAnalysis(StringRef Assembly) {
  53     assert(M == nullptr &&
  54            "Calling runAnalysis multiple times is unsafe. See getAnalysis().");
  55
  56     SMDiagnostic Error;
  57     M = parseAssemblyString(Assembly, Error, Context);
  58     assert(M && "Bad assembly. Bad test?");
  59     auto *F = getFunction();
  60
  61     ModulePassManager MPM;
  62     MPM.run(*M, MAM);
  63     return FAM.getResult<SPIRVConvergenceRegionAnalysis>(*F);
  64   }
  65
  66   SPIRVConvergenceRegionAnalysis::Result &getAnalysis() {
  67     assert(M != nullptr && "Has runAnalysis been called before?");
  68     return FAM.getResult<SPIRVConvergenceRegionAnalysis>(*getFunction());
  69   }
  70
  71   Function *getFunction() const {
  72     assert(M != nullptr && "Has runAnalysis been called before?");
  73     return M->getFunction("main");
  74   }
  75
  76   const BasicBlock *getBlock(StringRef Name) {
  77     assert(M != nullptr && "Has runAnalysis been called before?");
  78
  79     auto *F = getFunction();
  80     for (BasicBlock &BB : *F) {
  81       if (BB.getName() == Name)
  82         return &BB;
  83     }
  84
  85     ADD_FAILURE() << "Error: Could not locate requested block. Bad test?";
  86     return nullptr;
  87   }
  88
  89   const ConvergenceRegion *getRegionWithEntry(StringRef Name) {
  90     assert(M != nullptr && "Has runAnalysis been called before?");
  91
  92     std::queue<const ConvergenceRegion *> ToProcess;
  93     ToProcess.push(getAnalysis().getTopLevelRegion());
  94
  95     while (ToProcess.size() != 0) {
  96       auto *R = ToProcess.front();
  97       ToProcess.pop();
  98       for (auto *Child : R->Children)
  99         ToProcess.push(Child);
 100
 101       if (R->Entry->getName() == Name)
 102         return R;
 103     }
 104
 105     ADD_FAILURE() << "Error: Could not locate requested region. Bad test?";
 106     return nullptr;
 107   }
 108
 109   void checkRegionBlocks(const ConvergenceRegion *R,
 110                          std::initializer_list<const char *> InRegion,
 111                          std::initializer_list<const char *> NotInRegion) {
 112     for (const char *Name : InRegion) {
 113       EXPECT_TRUE(R->contains(getBlock(Name)))
 114           << "error: " << Name << " not in region " << R->Entry->getName();
 115     }
 116
 117     for (const char *Name : NotInRegion) {
 118       EXPECT_FALSE(R->contains(getBlock(Name)))
 119           << "error: " << Name << " in region " << R->Entry->getName();
 120     }
 121   }
 122
 123 protected:
 124   LLVMContext Context;
 125   FunctionAnalysisManager FAM;
 126   ModuleAnalysisManager MAM;
 127   std::unique_ptr<Module> M;
 128 };
 129
 130 MATCHER_P(ContainsBasicBlock, label, "") {
 131   for (const auto *bb : arg)
 132     if (bb->getName() == label)
 133       return true;
 134   return false;
 135 }
 136
 137 TEST_F(SPIRVConvergenceRegionAnalysisTest, DefaultRegion) {
 138   StringRef Assembly = R"(
 139     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 140       ret void
 141     }
 142   )";
 143
 144   const auto *CR = runAnalysis(Assembly).getTopLevelRegion();
 145
 146   EXPECT_EQ(CR->Parent, nullptr);
 147   EXPECT_EQ(CR->ConvergenceToken, std::nullopt);
 148   EXPECT_EQ(CR->Children.size(), 0u);
 149 }
 150
 151 TEST_F(SPIRVConvergenceRegionAnalysisTest, DefaultRegionWithToken) {
 152   StringRef Assembly = R"(
 153     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 154       %t1 = call token @llvm.experimental.convergence.entry()
 155       ret void
 156     }
 157
 158     declare token @llvm.experimental.convergence.entry()
 159   )";
 160
 161   const auto *CR = runAnalysis(Assembly).getTopLevelRegion();
 162
 163   EXPECT_EQ(CR->Parent, nullptr);
 164   EXPECT_EQ(CR->Children.size(), 0u);
 165   EXPECT_TRUE(CR->ConvergenceToken.has_value());
 166   EXPECT_EQ(CR->ConvergenceToken.value()->getIntrinsicID(),
 167             Intrinsic::experimental_convergence_entry);
 168 }
 169
 170 TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopOneRegion) {
 171   StringRef Assembly = R"(
 172     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 173       %t1 = call token @llvm.experimental.convergence.entry()
 174       %1 = icmp ne i32 0, 0
 175       br label %l1
 176
 177     l1:
 178       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 179       br i1 %1, label %l1_body, label %l1_end
 180
 181     l1_body:
 182       br label %l1_continue
 183
 184     l1_continue:
 185       br label %l1
 186
 187     l1_end:
 188       br label %end
 189
 190     end:
 191       ret void
 192     }
 193
 194     declare token @llvm.experimental.convergence.entry()
 195     declare token @llvm.experimental.convergence.control()
 196     declare token @llvm.experimental.convergence.loop()
 197   )";
 198
 199   const auto *CR = runAnalysis(Assembly).getTopLevelRegion();
 200
 201   EXPECT_EQ(CR->Parent, nullptr);
 202   EXPECT_EQ(CR->ConvergenceToken.value()->getName(), "t1");
 203   EXPECT_TRUE(CR->ConvergenceToken.has_value());
 204   EXPECT_EQ(CR->ConvergenceToken.value()->getIntrinsicID(),
 205             Intrinsic::experimental_convergence_entry);
 206   EXPECT_EQ(CR->Children.size(), 1u);
 207 }
 208
 209 TEST_F(SPIRVConvergenceRegionAnalysisTest,
 210        SingleLoopLoopRegionParentsIsTopLevelRegion) {
 211   StringRef Assembly = R"(
 212     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 213       %t1 = call token @llvm.experimental.convergence.entry()
 214       %1 = icmp ne i32 0, 0
 215       br label %l1
 216
 217     l1:
 218       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 219       br i1 %1, label %l1_body, label %l1_end
 220
 221     l1_body:
 222       br label %l1_continue
 223
 224     l1_continue:
 225       br label %l1
 226
 227     l1_end:
 228       br label %end
 229
 230     end:
 231       ret void
 232     }
 233
 234     declare token @llvm.experimental.convergence.entry()
 235     declare token @llvm.experimental.convergence.control()
 236     declare token @llvm.experimental.convergence.loop()
 237   )";
 238
 239   const auto *CR = runAnalysis(Assembly).getTopLevelRegion();
 240
 241   EXPECT_EQ(CR->Parent, nullptr);
 242   EXPECT_EQ(CR->ConvergenceToken.value()->getName(), "t1");
 243   EXPECT_EQ(CR->Children[0]->Parent, CR);
 244   EXPECT_EQ(CR->Children[0]->ConvergenceToken.value()->getName(), "tl1");
 245 }
 246
 247 TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopExits) {
 248   StringRef Assembly = R"(
 249     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 250       %t1 = call token @llvm.experimental.convergence.entry()
 251       %1 = icmp ne i32 0, 0
 252       br label %l1
 253
 254     l1:
 255       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 256       br i1 %1, label %l1_body, label %l1_end
 257
 258     l1_body:
 259       br label %l1_continue
 260
 261     l1_continue:
 262       br label %l1
 263
 264     l1_end:
 265       br label %end
 266
 267     end:
 268       ret void
 269     }
 270
 271     declare token @llvm.experimental.convergence.entry()
 272     declare token @llvm.experimental.convergence.control()
 273     declare token @llvm.experimental.convergence.loop()
 274   )";
 275
 276   const auto *CR = runAnalysis(Assembly).getTopLevelRegion();
 277   const auto *L = CR->Children[0];
 278
 279   EXPECT_EQ(L->Exits.size(), 1ul);
 280   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1"));
 281 }
 282
 283 TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopWithBreakExits) {
 284   StringRef Assembly = R"(
 285     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 286       %t1 = call token @llvm.experimental.convergence.entry()
 287       %1 = icmp ne i32 0, 0
 288       br label %l1_header
 289
 290     l1_header:
 291       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 292       br i1 %1, label %l1_body, label %end.loopexit
 293
 294     l1_body:
 295       %2 = icmp ne i32 0, 0
 296       br i1 %2, label %l1_condition_true, label %l1_condition_false
 297
 298     l1_condition_true:
 299       %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]
 300       br label %end
 301
 302     l1_condition_false:
 303       br label %l1_continue
 304
 305     l1_continue:
 306       br label %l1_header
 307
 308     end.loopexit:
 309       br label %end
 310
 311     end:
 312       ret void
 313     }
 314
 315     declare token @llvm.experimental.convergence.entry()
 316     declare token @llvm.experimental.convergence.control()
 317     declare token @llvm.experimental.convergence.loop()
 318
 319     ; This intrinsic is not convergent. This is only because the backend doesn't
 320     ; support convergent operations yet.
 321     declare spir_func i32 @_Z3absi(i32) convergent
 322   )";
 323
 324   const auto *CR = runAnalysis(Assembly).getTopLevelRegion();
 325   const auto *L = CR->Children[0];
 326
 327   EXPECT_EQ(L->Exits.size(), 2ul);
 328   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));
 329   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_condition_true"));
 330
 331   EXPECT_TRUE(CR->contains(getBlock("l1_header")));
 332   EXPECT_TRUE(CR->contains(getBlock("l1_condition_true")));
 333 }
 334
 335 TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopWithBreakRegionBlocks) {
 336   StringRef Assembly = R"(
 337     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 338       %t1 = call token @llvm.experimental.convergence.entry()
 339       %1 = icmp ne i32 0, 0
 340       br label %l1_header
 341
 342     l1_header:
 343       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 344       br i1 %1, label %l1_body, label %end.loopexit
 345
 346     l1_body:
 347       %2 = icmp ne i32 0, 0
 348       br i1 %2, label %l1_condition_true, label %l1_condition_false
 349
 350     l1_condition_true:
 351       %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]
 352       br label %end
 353
 354     l1_condition_false:
 355       br label %l1_continue
 356
 357     l1_continue:
 358       br label %l1_header
 359
 360     end.loopexit:
 361       br label %end
 362
 363     end:
 364       ret void
 365     }
 366
 367     declare token @llvm.experimental.convergence.entry()
 368     declare token @llvm.experimental.convergence.control()
 369     declare token @llvm.experimental.convergence.loop()
 370
 371     ; This intrinsic is not convergent. This is only because the backend doesn't
 372     ; support convergent operations yet.
 373     declare spir_func i32 @_Z3absi(i32) convergent
 374   )";
 375
 376   const auto *CR = runAnalysis(Assembly).getTopLevelRegion();
 377   const auto *L = CR->Children[0];
 378
 379   EXPECT_TRUE(CR->contains(getBlock("l1_header")));
 380   EXPECT_TRUE(L->contains(getBlock("l1_header")));
 381
 382   EXPECT_TRUE(CR->contains(getBlock("l1_body")));
 383   EXPECT_TRUE(L->contains(getBlock("l1_body")));
 384
 385   EXPECT_TRUE(CR->contains(getBlock("l1_condition_true")));
 386   EXPECT_TRUE(L->contains(getBlock("l1_condition_true")));
 387
 388   EXPECT_TRUE(CR->contains(getBlock("l1_condition_false")));
 389   EXPECT_TRUE(L->contains(getBlock("l1_condition_false")));
 390
 391   EXPECT_TRUE(CR->contains(getBlock("l1_continue")));
 392   EXPECT_TRUE(L->contains(getBlock("l1_continue")));
 393
 394   EXPECT_TRUE(CR->contains(getBlock("end.loopexit")));
 395   EXPECT_FALSE(L->contains(getBlock("end.loopexit")));
 396
 397   EXPECT_TRUE(CR->contains(getBlock("end")));
 398   EXPECT_FALSE(L->contains(getBlock("end")));
 399 }
 400
 401 // Exact same test as before, except the 'if() break' condition in the loop is
 402 // not marked with any convergence intrinsic. In such case, it is valid to
 403 // consider it outside of the loop.
 404 TEST_F(SPIRVConvergenceRegionAnalysisTest,
 405        SingleLoopWithBreakNoConvergenceControl) {
 406   StringRef Assembly = R"(
 407     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 408       %t1 = call token @llvm.experimental.convergence.entry()
 409       %1 = icmp ne i32 0, 0
 410       br label %l1_header
 411
 412     l1_header:
 413       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 414       br i1 %1, label %l1_body, label %end.loopexit
 415
 416     l1_body:
 417       %2 = icmp ne i32 0, 0
 418       br i1 %2, label %l1_condition_true, label %l1_condition_false
 419
 420     l1_condition_true:
 421       br label %end
 422
 423     l1_condition_false:
 424       br label %l1_continue
 425
 426     l1_continue:
 427       br label %l1_header
 428
 429     end.loopexit:
 430       br label %end
 431
 432     end:
 433       ret void
 434     }
 435
 436     declare token @llvm.experimental.convergence.entry()
 437     declare token @llvm.experimental.convergence.control()
 438     declare token @llvm.experimental.convergence.loop()
 439   )";
 440
 441   runAnalysis(Assembly);
 442   const auto *L = getRegionWithEntry("l1_header");
 443
 444   EXPECT_EQ(L->Entry->getName(), "l1_header");
 445   EXPECT_EQ(L->Exits.size(), 2ul);
 446   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));
 447   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));
 448
 449   EXPECT_TRUE(L->contains(getBlock("l1_header")));
 450   EXPECT_TRUE(L->contains(getBlock("l1_body")));
 451   EXPECT_FALSE(L->contains(getBlock("l1_condition_true")));
 452   EXPECT_TRUE(L->contains(getBlock("l1_condition_false")));
 453   EXPECT_TRUE(L->contains(getBlock("l1_continue")));
 454   EXPECT_FALSE(L->contains(getBlock("end.loopexit")));
 455   EXPECT_FALSE(L->contains(getBlock("end")));
 456 }
 457
 458 TEST_F(SPIRVConvergenceRegionAnalysisTest, TwoLoopsWithControl) {
 459   StringRef Assembly = R"(
 460     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 461       %t1 = call token @llvm.experimental.convergence.entry()
 462       %1 = icmp ne i32 0, 0
 463       br label %l1_header
 464
 465     l1_header:
 466       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 467       br i1 %1, label %l1_body, label %l1_exit
 468
 469     l1_body:
 470       br i1 %1, label %l1_condition_true, label %l1_condition_false
 471
 472     l1_condition_true:
 473       br label %mid
 474
 475     l1_condition_false:
 476       br label %l1_continue
 477
 478     l1_continue:
 479       br label %l1_header
 480
 481     l1_exit:
 482       br label %mid
 483
 484     mid:
 485       br label %l2_header
 486
 487     l2_header:
 488       %tl2 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 489       br i1 %1, label %l2_body, label %l2_exit
 490
 491     l2_body:
 492       br i1 %1, label %l2_condition_true, label %l2_condition_false
 493
 494     l2_condition_true:
 495       br label %end
 496
 497     l2_condition_false:
 498       br label %l2_continue
 499
 500     l2_continue:
 501       br label %l2_header
 502
 503     l2_exit:
 504       br label %end
 505
 506     end:
 507       ret void
 508     }
 509
 510     declare token @llvm.experimental.convergence.entry()
 511     declare token @llvm.experimental.convergence.control()
 512     declare token @llvm.experimental.convergence.loop()
 513   )";
 514
 515   runAnalysis(Assembly);
 516
 517   {
 518     const auto *L = getRegionWithEntry("l1_header");
 519
 520     EXPECT_EQ(L->Entry->getName(), "l1_header");
 521     EXPECT_EQ(L->Exits.size(), 2ul);
 522     EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));
 523     EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));
 524
 525     checkRegionBlocks(
 526         L, {"l1_header", "l1_body", "l1_condition_false", "l1_continue"},
 527         {"", "l2_header", "l2_body", "l2_condition_true", "l2_condition_false",
 528          "l2_continue", "l2_exit", "l1_condition_true", "l1_exit", "end"});
 529   }
 530   {
 531     const auto *L = getRegionWithEntry("l2_header");
 532
 533     EXPECT_EQ(L->Entry->getName(), "l2_header");
 534     EXPECT_EQ(L->Exits.size(), 2ul);
 535     EXPECT_THAT(L->Exits, ContainsBasicBlock("l2_header"));
 536     EXPECT_THAT(L->Exits, ContainsBasicBlock("l2_body"));
 537
 538     checkRegionBlocks(
 539         L, {"l2_header", "l2_body", "l2_condition_false", "l2_continue"},
 540         {"", "l1_header", "l1_body", "l1_condition_true", "l1_condition_false",
 541          "l1_continue", "l1_exit", "l2_condition_true", "l2_exit", "end"});
 542   }
 543 }
 544
 545 // Both branches in the loop condition break. This means the loop continue
 546 // targets are unreachable, meaning no reachable back-edge. This should
 547 // transform the loop condition into a simple condition, meaning we have a
 548 // single convergence region.
 549 TEST_F(SPIRVConvergenceRegionAnalysisTest, LoopBothBranchExits) {
 550   StringRef Assembly = R"(
 551     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 552       %t1 = call token @llvm.experimental.convergence.entry()
 553       %1 = icmp ne i32 0, 0
 554       br label %l1_header
 555
 556     l1_header:
 557       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 558       br i1 %1, label %l1_body, label %l1_exit
 559
 560     l1_body:
 561       br i1 %1, label %l1_condition_true, label %l1_condition_false
 562
 563     l1_condition_true:
 564       %call_true = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]
 565       br label %end
 566
 567     l1_condition_false:
 568       %call_false = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]
 569       br label %end
 570
 571     l1_continue:
 572       br label %l1_header
 573
 574     l1_exit:
 575       br label %end
 576
 577     end:
 578       ret void
 579     }
 580
 581     declare token @llvm.experimental.convergence.entry()
 582     declare token @llvm.experimental.convergence.control()
 583     declare token @llvm.experimental.convergence.loop()
 584
 585     ; This intrinsic is not convergent. This is only because the backend doesn't
 586     ; support convergent operations yet.
 587     declare spir_func i32 @_Z3absi(i32) convergent
 588   )";
 589
 590   ;
 591   const auto *R = runAnalysis(Assembly).getTopLevelRegion();
 592
 593   ASSERT_EQ(R->Children.size(), 0ul);
 594   EXPECT_EQ(R->Exits.size(), 1ul);
 595   EXPECT_THAT(R->Exits, ContainsBasicBlock("end"));
 596 }
 597
 598 TEST_F(SPIRVConvergenceRegionAnalysisTest, InnerLoopBreaks) {
 599   StringRef Assembly = R"(
 600     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 601       %t1 = call token @llvm.experimental.convergence.entry()
 602       %1 = icmp ne i32 0, 0
 603       br label %l1_header
 604
 605     l1_header:
 606       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 607       br i1 %1, label %l1_body, label %l1_exit
 608
 609     l1_body:
 610       br label %l2_header
 611
 612     l2_header:
 613       %tl2 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tl1) ]
 614       br i1 %1, label %l2_body, label %l2_exit
 615
 616     l2_body:
 617       br i1 %1, label %l2_condition_true, label %l2_condition_false
 618
 619     l2_condition_true:
 620       %call_true = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]
 621       br label %end
 622
 623     l2_condition_false:
 624       br label %l2_continue
 625
 626     l2_continue:
 627       br label %l2_header
 628
 629     l2_exit:
 630       br label %l1_continue
 631
 632     l1_continue:
 633       br label %l1_header
 634
 635     l1_exit:
 636       br label %end
 637
 638     end:
 639       ret void
 640     }
 641
 642     declare token @llvm.experimental.convergence.entry()
 643     declare token @llvm.experimental.convergence.control()
 644     declare token @llvm.experimental.convergence.loop()
 645
 646     ; This intrinsic is not convergent. This is only because the backend doesn't
 647     ; support convergent operations yet.
 648     declare spir_func i32 @_Z3absi(i32) convergent
 649   )";
 650
 651   const auto *R = runAnalysis(Assembly).getTopLevelRegion();
 652   const auto *L1 = getRegionWithEntry("l1_header");
 653   const auto *L2 = getRegionWithEntry("l2_header");
 654
 655   EXPECT_EQ(R->Children.size(), 1ul);
 656   EXPECT_EQ(L1->Children.size(), 1ul);
 657   EXPECT_EQ(L1->Parent, R);
 658   EXPECT_EQ(L2->Parent, L1);
 659
 660   EXPECT_EQ(R->Entry->getName(), "");
 661   EXPECT_EQ(R->Exits.size(), 1ul);
 662   EXPECT_THAT(R->Exits, ContainsBasicBlock("end"));
 663
 664   EXPECT_EQ(L1->Entry->getName(), "l1_header");
 665   EXPECT_EQ(L1->Exits.size(), 2ul);
 666   EXPECT_THAT(L1->Exits, ContainsBasicBlock("l1_header"));
 667   EXPECT_THAT(L1->Exits, ContainsBasicBlock("l2_condition_true"));
 668
 669   checkRegionBlocks(L1,
 670                     {"l1_header", "l1_body", "l2_header", "l2_body",
 671                      "l2_condition_false", "l2_condition_true", "l2_continue",
 672                      "l2_exit", "l1_continue"},
 673                     {"", "l1_exit", "end"});
 674
 675   EXPECT_EQ(L2->Entry->getName(), "l2_header");
 676   EXPECT_EQ(L2->Exits.size(), 2ul);
 677   EXPECT_THAT(L2->Exits, ContainsBasicBlock("l2_header"));
 678   EXPECT_THAT(L2->Exits, ContainsBasicBlock("l2_body"));
 679   checkRegionBlocks(
 680       L2, {"l2_header", "l2_body", "l2_condition_false", "l2_continue"},
 681       {"", "l1_header", "l1_body", "l2_exit", "l1_continue",
 682        "l2_condition_true", "l1_exit", "end"});
 683 }
 684
 685 TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopMultipleExits) {
 686   StringRef Assembly = R"(
 687     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 688       %t1 = call token @llvm.experimental.convergence.entry()
 689       %cond = icmp ne i32 0, 0
 690       br label %l1
 691
 692     l1:
 693       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 694       br i1 %cond, label %l1_body, label %l1_exit
 695
 696     l1_body:
 697       switch i32 0, label %sw.default.exit [
 698         i32 0, label %sw.bb
 699         i32 1, label %sw.bb1
 700         i32 2, label %sw.bb2
 701       ]
 702
 703     sw.default.exit:
 704       br label %sw.default
 705
 706     sw.default:
 707       br label %l1_end
 708
 709     sw.bb:
 710       br label %l1_end
 711
 712     sw.bb1:
 713       br label %l1_continue
 714
 715     sw.bb2:
 716       br label %sw.default
 717
 718     l1_continue:
 719       br label %l1
 720
 721     l1_exit:
 722       br label %l1_end
 723
 724     l1_end:
 725       br label %end
 726
 727     end:
 728       ret void
 729     }
 730
 731     declare token @llvm.experimental.convergence.entry()
 732     declare token @llvm.experimental.convergence.control()
 733     declare token @llvm.experimental.convergence.loop()
 734   )";
 735
 736   runAnalysis(Assembly).getTopLevelRegion();
 737   const auto *L = getRegionWithEntry("l1");
 738   ASSERT_NE(L, nullptr);
 739
 740   EXPECT_EQ(L->Entry, getBlock("l1"));
 741   EXPECT_EQ(L->Exits.size(), 2ul);
 742   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1"));
 743   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));
 744
 745   checkRegionBlocks(L, {"l1", "l1_body", "l1_continue", "sw.bb1"},
 746                     {"", "sw.default.exit", "sw.default", "l1_end", "end",
 747                      "sw.bb", "sw.bb2", "l1_exit"});
 748 }
 749
 750 TEST_F(SPIRVConvergenceRegionAnalysisTest,
 751        SingleLoopMultipleExitsWithPartialConvergence) {
 752   StringRef Assembly = R"(
 753     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 754       %t1 = call token @llvm.experimental.convergence.entry()
 755       %cond = icmp ne i32 0, 0
 756       br label %l1
 757
 758     l1:
 759       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 760       br i1 %cond, label %l1_body, label %l1_exit
 761
 762     l1_body:
 763       switch i32 0, label %sw.default.exit [
 764         i32 0, label %sw.bb
 765         i32 1, label %sw.bb1
 766         i32 2, label %sw.bb2
 767       ]
 768
 769     sw.default.exit:
 770       br label %sw.default
 771
 772     sw.default:
 773       %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]
 774       br label %l1_end
 775
 776     sw.bb:
 777       br label %l1_end
 778
 779     sw.bb1:
 780       br label %l1_continue
 781
 782     sw.bb2:
 783       br label %sw.default
 784
 785     l1_continue:
 786       br label %l1
 787
 788     l1_exit:
 789       br label %l1_end
 790
 791     l1_end:
 792       br label %end
 793
 794     end:
 795       ret void
 796     }
 797
 798     declare token @llvm.experimental.convergence.entry()
 799     declare token @llvm.experimental.convergence.control()
 800     declare token @llvm.experimental.convergence.loop()
 801
 802     ; This intrinsic is not convergent. This is only because the backend doesn't
 803     ; support convergent operations yet.
 804     declare spir_func i32 @_Z3absi(i32) convergent
 805   )";
 806
 807   runAnalysis(Assembly).getTopLevelRegion();
 808   const auto *L = getRegionWithEntry("l1");
 809   ASSERT_NE(L, nullptr);
 810
 811   EXPECT_EQ(L->Entry, getBlock("l1"));
 812   EXPECT_EQ(L->Exits.size(), 3ul);
 813   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1"));
 814   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));
 815   EXPECT_THAT(L->Exits, ContainsBasicBlock("sw.default"));
 816
 817   checkRegionBlocks(L,
 818                     {"l1", "l1_body", "l1_continue", "sw.bb1",
 819                      "sw.default.exit", "sw.bb2", "sw.default"},
 820                     {"", "l1_end", "end", "sw.bb", "l1_exit"});
 821 }
 822
 823 TEST_F(SPIRVConvergenceRegionAnalysisTest,
 824        SingleLoopWithDeepConvergenceBranch) {
 825   StringRef Assembly = R"(
 826     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 827       %t1 = call token @llvm.experimental.convergence.entry()
 828       %1 = icmp ne i32 0, 0
 829       br label %l1_header
 830
 831     l1_header:
 832       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 833       br i1 %1, label %l1_body, label %l1_end
 834
 835     l1_body:
 836       %2 = icmp ne i32 0, 0
 837       br i1 %2, label %l1_condition_true, label %l1_condition_false
 838
 839     l1_condition_true:
 840       br label %a
 841
 842     a:
 843       br label %b
 844
 845     b:
 846       br label %c
 847
 848     c:
 849       %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]
 850       br label %end
 851
 852     l1_condition_false:
 853       br label %l1_continue
 854
 855     l1_continue:
 856       br label %l1_header
 857
 858     l1_end:
 859       br label %end
 860
 861     end:
 862       ret void
 863     }
 864
 865     declare token @llvm.experimental.convergence.entry()
 866     declare token @llvm.experimental.convergence.control()
 867     declare token @llvm.experimental.convergence.loop()
 868
 869     ; This intrinsic is not convergent. This is only because the backend doesn't
 870     ; support convergent operations yet.
 871     declare spir_func i32 @_Z3absi(i32) convergent
 872   )";
 873
 874   runAnalysis(Assembly).getTopLevelRegion();
 875   const auto *L = getRegionWithEntry("l1_header");
 876   ASSERT_NE(L, nullptr);
 877
 878   EXPECT_EQ(L->Entry, getBlock("l1_header"));
 879   EXPECT_EQ(L->Exits.size(), 2ul);
 880   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));
 881   EXPECT_THAT(L->Exits, ContainsBasicBlock("c"));
 882
 883   checkRegionBlocks(L,
 884                     {"l1_header", "l1_body", "l1_continue",
 885                      "l1_condition_false", "l1_condition_true", "a", "b", "c"},
 886                     {"", "l1_end", "end"});
 887 }
 888
 889 TEST_F(SPIRVConvergenceRegionAnalysisTest,
 890        SingleLoopWithDeepConvergenceLateBranch) {
 891   StringRef Assembly = R"(
 892     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 893       %t1 = call token @llvm.experimental.convergence.entry()
 894       %1 = icmp ne i32 0, 0
 895       br label %l1_header
 896
 897     l1_header:
 898       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
 899       br i1 %1, label %l1_body, label %l1_end
 900
 901     l1_body:
 902       %2 = icmp ne i32 0, 0
 903       br i1 %2, label %l1_condition_true, label %l1_condition_false
 904
 905     l1_condition_true:
 906       br label %a
 907
 908     a:
 909       br label %b
 910
 911     b:
 912       br i1 %2, label %c, label %d
 913
 914     c:
 915       %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]
 916       br label %end
 917
 918     d:
 919       br label %end
 920
 921     l1_condition_false:
 922       br label %l1_continue
 923
 924     l1_continue:
 925       br label %l1_header
 926
 927     l1_end:
 928       br label %end
 929
 930     end:
 931       ret void
 932     }
 933
 934     declare token @llvm.experimental.convergence.entry()
 935     declare token @llvm.experimental.convergence.control()
 936     declare token @llvm.experimental.convergence.loop()
 937
 938     ; This intrinsic is not convergent. This is only because the backend doesn't
 939     ; support convergent operations yet.
 940     declare spir_func i32 @_Z3absi(i32) convergent
 941   )";
 942
 943   runAnalysis(Assembly).getTopLevelRegion();
 944   const auto *L = getRegionWithEntry("l1_header");
 945   ASSERT_NE(L, nullptr);
 946
 947   EXPECT_EQ(L->Entry, getBlock("l1_header"));
 948   EXPECT_EQ(L->Exits.size(), 3ul);
 949   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));
 950   EXPECT_THAT(L->Exits, ContainsBasicBlock("b"));
 951   EXPECT_THAT(L->Exits, ContainsBasicBlock("c"));
 952
 953   checkRegionBlocks(L,
 954                     {"l1_header", "l1_body", "l1_continue",
 955                      "l1_condition_false", "l1_condition_true", "a", "b", "c"},
 956                     {"", "l1_end", "end", "d"});
 957 }
 958
 959 TEST_F(SPIRVConvergenceRegionAnalysisTest,
 960        SingleLoopWithNoConvergenceIntrinsics) {
 961   StringRef Assembly = R"(
 962     define void @main() "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 963       %1 = icmp ne i32 0, 0
 964       br label %l1_header
 965
 966     l1_header:
 967       br i1 %1, label %l1_body, label %l1_end
 968
 969     l1_body:
 970       %2 = icmp ne i32 0, 0
 971       br i1 %2, label %l1_condition_true, label %l1_condition_false
 972
 973     l1_condition_true:
 974       br label %a
 975
 976     a:
 977       br label %end
 978
 979     l1_condition_false:
 980       br label %l1_continue
 981
 982     l1_continue:
 983       br label %l1_header
 984
 985     l1_end:
 986       br label %end
 987
 988     end:
 989       ret void
 990     }
 991   )";
 992
 993   runAnalysis(Assembly).getTopLevelRegion();
 994   const auto *L = getRegionWithEntry("l1_header");
 995   ASSERT_NE(L, nullptr);
 996
 997   EXPECT_EQ(L->Entry, getBlock("l1_header"));
 998   EXPECT_EQ(L->Exits.size(), 2ul);
 999   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));
1000   EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));
1001
1002   checkRegionBlocks(
1003       L, {"l1_header", "l1_body", "l1_continue", "l1_condition_false"},
1004       {"", "l1_end", "end", "l1_condition_true", "a"});
1005 }
1006
1007 TEST_F(SPIRVConvergenceRegionAnalysisTest, SimpleFunction) {
1008   StringRef Assembly = R"(
1009     define void @main() "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
1010       ret void
1011     }
1012   )";
1013
1014   const auto *R = runAnalysis(Assembly).getTopLevelRegion();
1015   ASSERT_NE(R, nullptr);
1016
1017   EXPECT_EQ(R->Entry, getBlock(""));
1018   EXPECT_EQ(R->Exits.size(), 1ul);
1019   EXPECT_THAT(R->Exits, ContainsBasicBlock(""));
1020   EXPECT_TRUE(R->contains(getBlock("")));
1021 }
1022
1023 TEST_F(SPIRVConvergenceRegionAnalysisTest, NestedLoopInBreak) {
1024   StringRef Assembly = R"(
1025     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
1026       %t1 = call token @llvm.experimental.convergence.entry()
1027       %1 = icmp ne i32 0, 0
1028       br label %l1
1029
1030     l1:
1031       %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]
1032       br i1 %1, label %l1_body, label %l1_to_end
1033
1034     l1_body:
1035       br i1 %1, label %cond_inner, label %l1_continue
1036
1037     cond_inner:
1038       br label %l2
1039
1040     l2:
1041       %tl2 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tl1) ]
1042       br i1 %1, label %l2_body, label %l2_end
1043
1044     l2_body:
1045       %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl2) ]
1046       br label %l2_continue
1047
1048     l2_continue:
1049       br label %l2
1050
1051     l2_end:
1052       br label %l2_exit
1053
1054     l2_exit:
1055       %call2 = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]
1056       br label %l1_end
1057
1058     l1_continue:
1059       br label %l1
1060
1061     l1_to_end:
1062       br label %l1_end
1063
1064     l1_end:
1065       br label %end
1066
1067     end:
1068       ret void
1069     }
1070
1071     declare token @llvm.experimental.convergence.entry()
1072     declare token @llvm.experimental.convergence.control()
1073     declare token @llvm.experimental.convergence.loop()
1074     declare spir_func i32 @_Z3absi(i32) convergent
1075   )";
1076
1077   const auto *R = runAnalysis(Assembly).getTopLevelRegion();
1078   ASSERT_NE(R, nullptr);
1079
1080   EXPECT_EQ(R->Children.size(), 1ul);
1081
1082   const auto *L1 = R->Children[0];
1083   EXPECT_EQ(L1->Children.size(), 1ul);
1084   EXPECT_EQ(L1->Entry->getName(), "l1");
1085   EXPECT_EQ(L1->Exits.size(), 2ul);
1086   EXPECT_THAT(L1->Exits, ContainsBasicBlock("l1"));
1087   EXPECT_THAT(L1->Exits, ContainsBasicBlock("l2_exit"));
1088   checkRegionBlocks(L1,
1089                     {"l1", "l1_body", "l1_continue", "cond_inner", "l2",
1090                      "l2_body", "l2_end", "l2_continue", "l2_exit"},
1091                     {"", "l1_to_end", "l1_end", "end"});
1092
1093   const auto *L2 = L1->Children[0];
1094   EXPECT_EQ(L2->Children.size(), 0ul);
1095   EXPECT_EQ(L2->Entry->getName(), "l2");
1096   EXPECT_EQ(L2->Exits.size(), 1ul);
1097   EXPECT_THAT(L2->Exits, ContainsBasicBlock("l2"));
1098   checkRegionBlocks(L2, {"l2", "l2_body", "l2_continue"},
1099                     {"", "l1_to_end", "l1_end", "end", "l1", "l1_body",
1100                      "l1_continue", "cond_inner", "l2_end", "l2_exit"});
1101 }