1100 lines · 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-exception6//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/IntrinsicInst.h"15#include "llvm/IR/LLVMContext.h"16#include "llvm/IR/LegacyPassManager.h"17#include "llvm/IR/Module.h"18#include "llvm/IR/PassInstrumentation.h"19#include "llvm/IR/Type.h"20#include "llvm/IR/TypedPointerType.h"21#include "llvm/Support/SourceMgr.h"22 23#include "gmock/gmock.h"24#include "gtest/gtest.h"25#include <queue>26 27using namespace llvm;28using namespace llvm::SPIRV;29 30template <typename T> struct IsA {31 friend bool operator==(const Value *V, const IsA &) { return isa<T>(V); }32};33 34class SPIRVConvergenceRegionAnalysisTest : public testing::Test {35protected:36 void SetUp() override {37 // Required for tests.38 FAM.registerPass([&] { return PassInstrumentationAnalysis(); });39 MAM.registerPass([&] { return PassInstrumentationAnalysis(); });40 41 // Required for ConvergenceRegionAnalysis.42 FAM.registerPass([&] { return DominatorTreeAnalysis(); });43 FAM.registerPass([&] { return LoopAnalysis(); });44 45 FAM.registerPass([&] { return SPIRVConvergenceRegionAnalysis(); });46 }47 48 void TearDown() override { M.reset(); }49 50 SPIRVConvergenceRegionAnalysis::Result &runAnalysis(StringRef Assembly) {51 assert(M == nullptr &&52 "Calling runAnalysis multiple times is unsafe. See getAnalysis().");53 54 SMDiagnostic Error;55 M = parseAssemblyString(Assembly, Error, Context);56 assert(M && "Bad assembly. Bad test?");57 auto *F = getFunction();58 59 ModulePassManager MPM;60 MPM.run(*M, MAM);61 return FAM.getResult<SPIRVConvergenceRegionAnalysis>(*F);62 }63 64 SPIRVConvergenceRegionAnalysis::Result &getAnalysis() {65 assert(M != nullptr && "Has runAnalysis been called before?");66 return FAM.getResult<SPIRVConvergenceRegionAnalysis>(*getFunction());67 }68 69 Function *getFunction() const {70 assert(M != nullptr && "Has runAnalysis been called before?");71 return M->getFunction("main");72 }73 74 const BasicBlock *getBlock(StringRef Name) {75 assert(M != nullptr && "Has runAnalysis been called before?");76 77 auto *F = getFunction();78 for (BasicBlock &BB : *F) {79 if (BB.getName() == Name)80 return &BB;81 }82 83 ADD_FAILURE() << "Error: Could not locate requested block. Bad test?";84 return nullptr;85 }86 87 const ConvergenceRegion *getRegionWithEntry(StringRef Name) {88 assert(M != nullptr && "Has runAnalysis been called before?");89 90 std::queue<const ConvergenceRegion *> ToProcess;91 ToProcess.push(getAnalysis().getTopLevelRegion());92 93 while (ToProcess.size() != 0) {94 auto *R = ToProcess.front();95 ToProcess.pop();96 for (auto *Child : R->Children)97 ToProcess.push(Child);98 99 if (R->Entry->getName() == Name)100 return R;101 }102 103 ADD_FAILURE() << "Error: Could not locate requested region. Bad test?";104 return nullptr;105 }106 107 void checkRegionBlocks(const ConvergenceRegion *R,108 std::initializer_list<const char *> InRegion,109 std::initializer_list<const char *> NotInRegion) {110 for (const char *Name : InRegion) {111 EXPECT_TRUE(R->contains(getBlock(Name)))112 << "error: " << Name << " not in region " << R->Entry->getName();113 }114 115 for (const char *Name : NotInRegion) {116 EXPECT_FALSE(R->contains(getBlock(Name)))117 << "error: " << Name << " in region " << R->Entry->getName();118 }119 }120 121protected:122 LLVMContext Context;123 FunctionAnalysisManager FAM;124 ModuleAnalysisManager MAM;125 std::unique_ptr<Module> M;126};127 128MATCHER_P(ContainsBasicBlock, label, "") {129 for (const auto *bb : arg)130 if (bb->getName() == label)131 return true;132 return false;133}134 135TEST_F(SPIRVConvergenceRegionAnalysisTest, DefaultRegion) {136 StringRef Assembly = R"(137 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {138 ret void139 }140 )";141 142 const auto *CR = runAnalysis(Assembly).getTopLevelRegion();143 144 EXPECT_EQ(CR->Parent, nullptr);145 EXPECT_EQ(CR->ConvergenceToken, std::nullopt);146 EXPECT_EQ(CR->Children.size(), 0u);147}148 149TEST_F(SPIRVConvergenceRegionAnalysisTest, DefaultRegionWithToken) {150 StringRef Assembly = R"(151 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {152 %t1 = call token @llvm.experimental.convergence.entry()153 ret void154 }155 156 declare token @llvm.experimental.convergence.entry()157 )";158 159 const auto *CR = runAnalysis(Assembly).getTopLevelRegion();160 161 EXPECT_EQ(CR->Parent, nullptr);162 EXPECT_EQ(CR->Children.size(), 0u);163 EXPECT_TRUE(CR->ConvergenceToken.has_value());164 EXPECT_EQ(CR->ConvergenceToken.value()->getIntrinsicID(),165 Intrinsic::experimental_convergence_entry);166}167 168TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopOneRegion) {169 StringRef Assembly = R"(170 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {171 %t1 = call token @llvm.experimental.convergence.entry()172 %1 = icmp ne i32 0, 0173 br label %l1174 175 l1:176 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]177 br i1 %1, label %l1_body, label %l1_end178 179 l1_body:180 br label %l1_continue181 182 l1_continue:183 br label %l1184 185 l1_end:186 br label %end187 188 end:189 ret void190 }191 192 declare token @llvm.experimental.convergence.entry()193 declare token @llvm.experimental.convergence.control()194 declare token @llvm.experimental.convergence.loop()195 )";196 197 const auto *CR = runAnalysis(Assembly).getTopLevelRegion();198 199 EXPECT_EQ(CR->Parent, nullptr);200 EXPECT_EQ(CR->ConvergenceToken.value()->getName(), "t1");201 EXPECT_TRUE(CR->ConvergenceToken.has_value());202 EXPECT_EQ(CR->ConvergenceToken.value()->getIntrinsicID(),203 Intrinsic::experimental_convergence_entry);204 EXPECT_EQ(CR->Children.size(), 1u);205}206 207TEST_F(SPIRVConvergenceRegionAnalysisTest,208 SingleLoopLoopRegionParentsIsTopLevelRegion) {209 StringRef Assembly = R"(210 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {211 %t1 = call token @llvm.experimental.convergence.entry()212 %1 = icmp ne i32 0, 0213 br label %l1214 215 l1:216 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]217 br i1 %1, label %l1_body, label %l1_end218 219 l1_body:220 br label %l1_continue221 222 l1_continue:223 br label %l1224 225 l1_end:226 br label %end227 228 end:229 ret void230 }231 232 declare token @llvm.experimental.convergence.entry()233 declare token @llvm.experimental.convergence.control()234 declare token @llvm.experimental.convergence.loop()235 )";236 237 const auto *CR = runAnalysis(Assembly).getTopLevelRegion();238 239 EXPECT_EQ(CR->Parent, nullptr);240 EXPECT_EQ(CR->ConvergenceToken.value()->getName(), "t1");241 EXPECT_EQ(CR->Children[0]->Parent, CR);242 EXPECT_EQ(CR->Children[0]->ConvergenceToken.value()->getName(), "tl1");243}244 245TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopExits) {246 StringRef Assembly = R"(247 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {248 %t1 = call token @llvm.experimental.convergence.entry()249 %1 = icmp ne i32 0, 0250 br label %l1251 252 l1:253 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]254 br i1 %1, label %l1_body, label %l1_end255 256 l1_body:257 br label %l1_continue258 259 l1_continue:260 br label %l1261 262 l1_end:263 br label %end264 265 end:266 ret void267 }268 269 declare token @llvm.experimental.convergence.entry()270 declare token @llvm.experimental.convergence.control()271 declare token @llvm.experimental.convergence.loop()272 )";273 274 const auto *CR = runAnalysis(Assembly).getTopLevelRegion();275 const auto *L = CR->Children[0];276 277 EXPECT_EQ(L->Exits.size(), 1ul);278 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1"));279}280 281TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopWithBreakExits) {282 StringRef Assembly = R"(283 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {284 %t1 = call token @llvm.experimental.convergence.entry()285 %1 = icmp ne i32 0, 0286 br label %l1_header287 288 l1_header:289 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]290 br i1 %1, label %l1_body, label %end.loopexit291 292 l1_body:293 %2 = icmp ne i32 0, 0294 br i1 %2, label %l1_condition_true, label %l1_condition_false295 296 l1_condition_true:297 %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]298 br label %end299 300 l1_condition_false:301 br label %l1_continue302 303 l1_continue:304 br label %l1_header305 306 end.loopexit:307 br label %end308 309 end:310 ret void311 }312 313 declare token @llvm.experimental.convergence.entry()314 declare token @llvm.experimental.convergence.control()315 declare token @llvm.experimental.convergence.loop()316 317 ; This intrinsic is not convergent. This is only because the backend doesn't318 ; support convergent operations yet.319 declare spir_func i32 @_Z3absi(i32) convergent320 )";321 322 const auto *CR = runAnalysis(Assembly).getTopLevelRegion();323 const auto *L = CR->Children[0];324 325 EXPECT_EQ(L->Exits.size(), 2ul);326 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));327 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_condition_true"));328 329 EXPECT_TRUE(CR->contains(getBlock("l1_header")));330 EXPECT_TRUE(CR->contains(getBlock("l1_condition_true")));331}332 333TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopWithBreakRegionBlocks) {334 StringRef Assembly = R"(335 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {336 %t1 = call token @llvm.experimental.convergence.entry()337 %1 = icmp ne i32 0, 0338 br label %l1_header339 340 l1_header:341 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]342 br i1 %1, label %l1_body, label %end.loopexit343 344 l1_body:345 %2 = icmp ne i32 0, 0346 br i1 %2, label %l1_condition_true, label %l1_condition_false347 348 l1_condition_true:349 %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]350 br label %end351 352 l1_condition_false:353 br label %l1_continue354 355 l1_continue:356 br label %l1_header357 358 end.loopexit:359 br label %end360 361 end:362 ret void363 }364 365 declare token @llvm.experimental.convergence.entry()366 declare token @llvm.experimental.convergence.control()367 declare token @llvm.experimental.convergence.loop()368 369 ; This intrinsic is not convergent. This is only because the backend doesn't370 ; support convergent operations yet.371 declare spir_func i32 @_Z3absi(i32) convergent372 )";373 374 const auto *CR = runAnalysis(Assembly).getTopLevelRegion();375 const auto *L = CR->Children[0];376 377 EXPECT_TRUE(CR->contains(getBlock("l1_header")));378 EXPECT_TRUE(L->contains(getBlock("l1_header")));379 380 EXPECT_TRUE(CR->contains(getBlock("l1_body")));381 EXPECT_TRUE(L->contains(getBlock("l1_body")));382 383 EXPECT_TRUE(CR->contains(getBlock("l1_condition_true")));384 EXPECT_TRUE(L->contains(getBlock("l1_condition_true")));385 386 EXPECT_TRUE(CR->contains(getBlock("l1_condition_false")));387 EXPECT_TRUE(L->contains(getBlock("l1_condition_false")));388 389 EXPECT_TRUE(CR->contains(getBlock("l1_continue")));390 EXPECT_TRUE(L->contains(getBlock("l1_continue")));391 392 EXPECT_TRUE(CR->contains(getBlock("end.loopexit")));393 EXPECT_FALSE(L->contains(getBlock("end.loopexit")));394 395 EXPECT_TRUE(CR->contains(getBlock("end")));396 EXPECT_FALSE(L->contains(getBlock("end")));397}398 399// Exact same test as before, except the 'if() break' condition in the loop is400// not marked with any convergence intrinsic. In such case, it is valid to401// consider it outside of the loop.402TEST_F(SPIRVConvergenceRegionAnalysisTest,403 SingleLoopWithBreakNoConvergenceControl) {404 StringRef Assembly = R"(405 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {406 %t1 = call token @llvm.experimental.convergence.entry()407 %1 = icmp ne i32 0, 0408 br label %l1_header409 410 l1_header:411 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]412 br i1 %1, label %l1_body, label %end.loopexit413 414 l1_body:415 %2 = icmp ne i32 0, 0416 br i1 %2, label %l1_condition_true, label %l1_condition_false417 418 l1_condition_true:419 br label %end420 421 l1_condition_false:422 br label %l1_continue423 424 l1_continue:425 br label %l1_header426 427 end.loopexit:428 br label %end429 430 end:431 ret void432 }433 434 declare token @llvm.experimental.convergence.entry()435 declare token @llvm.experimental.convergence.control()436 declare token @llvm.experimental.convergence.loop()437 )";438 439 runAnalysis(Assembly);440 const auto *L = getRegionWithEntry("l1_header");441 442 EXPECT_EQ(L->Entry->getName(), "l1_header");443 EXPECT_EQ(L->Exits.size(), 2ul);444 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));445 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));446 447 EXPECT_TRUE(L->contains(getBlock("l1_header")));448 EXPECT_TRUE(L->contains(getBlock("l1_body")));449 EXPECT_FALSE(L->contains(getBlock("l1_condition_true")));450 EXPECT_TRUE(L->contains(getBlock("l1_condition_false")));451 EXPECT_TRUE(L->contains(getBlock("l1_continue")));452 EXPECT_FALSE(L->contains(getBlock("end.loopexit")));453 EXPECT_FALSE(L->contains(getBlock("end")));454}455 456TEST_F(SPIRVConvergenceRegionAnalysisTest, TwoLoopsWithControl) {457 StringRef Assembly = R"(458 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {459 %t1 = call token @llvm.experimental.convergence.entry()460 %1 = icmp ne i32 0, 0461 br label %l1_header462 463 l1_header:464 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]465 br i1 %1, label %l1_body, label %l1_exit466 467 l1_body:468 br i1 %1, label %l1_condition_true, label %l1_condition_false469 470 l1_condition_true:471 br label %mid472 473 l1_condition_false:474 br label %l1_continue475 476 l1_continue:477 br label %l1_header478 479 l1_exit:480 br label %mid481 482 mid:483 br label %l2_header484 485 l2_header:486 %tl2 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]487 br i1 %1, label %l2_body, label %l2_exit488 489 l2_body:490 br i1 %1, label %l2_condition_true, label %l2_condition_false491 492 l2_condition_true:493 br label %end494 495 l2_condition_false:496 br label %l2_continue497 498 l2_continue:499 br label %l2_header500 501 l2_exit:502 br label %end503 504 end:505 ret void506 }507 508 declare token @llvm.experimental.convergence.entry()509 declare token @llvm.experimental.convergence.control()510 declare token @llvm.experimental.convergence.loop()511 )";512 513 runAnalysis(Assembly);514 515 {516 const auto *L = getRegionWithEntry("l1_header");517 518 EXPECT_EQ(L->Entry->getName(), "l1_header");519 EXPECT_EQ(L->Exits.size(), 2ul);520 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));521 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));522 523 checkRegionBlocks(524 L, {"l1_header", "l1_body", "l1_condition_false", "l1_continue"},525 {"", "l2_header", "l2_body", "l2_condition_true", "l2_condition_false",526 "l2_continue", "l2_exit", "l1_condition_true", "l1_exit", "end"});527 }528 {529 const auto *L = getRegionWithEntry("l2_header");530 531 EXPECT_EQ(L->Entry->getName(), "l2_header");532 EXPECT_EQ(L->Exits.size(), 2ul);533 EXPECT_THAT(L->Exits, ContainsBasicBlock("l2_header"));534 EXPECT_THAT(L->Exits, ContainsBasicBlock("l2_body"));535 536 checkRegionBlocks(537 L, {"l2_header", "l2_body", "l2_condition_false", "l2_continue"},538 {"", "l1_header", "l1_body", "l1_condition_true", "l1_condition_false",539 "l1_continue", "l1_exit", "l2_condition_true", "l2_exit", "end"});540 }541}542 543// Both branches in the loop condition break. This means the loop continue544// targets are unreachable, meaning no reachable back-edge. This should545// transform the loop condition into a simple condition, meaning we have a546// single convergence region.547TEST_F(SPIRVConvergenceRegionAnalysisTest, LoopBothBranchExits) {548 StringRef Assembly = R"(549 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {550 %t1 = call token @llvm.experimental.convergence.entry()551 %1 = icmp ne i32 0, 0552 br label %l1_header553 554 l1_header:555 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]556 br i1 %1, label %l1_body, label %l1_exit557 558 l1_body:559 br i1 %1, label %l1_condition_true, label %l1_condition_false560 561 l1_condition_true:562 %call_true = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]563 br label %end564 565 l1_condition_false:566 %call_false = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]567 br label %end568 569 l1_continue:570 br label %l1_header571 572 l1_exit:573 br label %end574 575 end:576 ret void577 }578 579 declare token @llvm.experimental.convergence.entry()580 declare token @llvm.experimental.convergence.control()581 declare token @llvm.experimental.convergence.loop()582 583 ; This intrinsic is not convergent. This is only because the backend doesn't584 ; support convergent operations yet.585 declare spir_func i32 @_Z3absi(i32) convergent586 )";587 588 ;589 const auto *R = runAnalysis(Assembly).getTopLevelRegion();590 591 ASSERT_EQ(R->Children.size(), 0ul);592 EXPECT_EQ(R->Exits.size(), 1ul);593 EXPECT_THAT(R->Exits, ContainsBasicBlock("end"));594}595 596TEST_F(SPIRVConvergenceRegionAnalysisTest, InnerLoopBreaks) {597 StringRef Assembly = R"(598 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {599 %t1 = call token @llvm.experimental.convergence.entry()600 %1 = icmp ne i32 0, 0601 br label %l1_header602 603 l1_header:604 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]605 br i1 %1, label %l1_body, label %l1_exit606 607 l1_body:608 br label %l2_header609 610 l2_header:611 %tl2 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tl1) ]612 br i1 %1, label %l2_body, label %l2_exit613 614 l2_body:615 br i1 %1, label %l2_condition_true, label %l2_condition_false616 617 l2_condition_true:618 %call_true = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]619 br label %end620 621 l2_condition_false:622 br label %l2_continue623 624 l2_continue:625 br label %l2_header626 627 l2_exit:628 br label %l1_continue629 630 l1_continue:631 br label %l1_header632 633 l1_exit:634 br label %end635 636 end:637 ret void638 }639 640 declare token @llvm.experimental.convergence.entry()641 declare token @llvm.experimental.convergence.control()642 declare token @llvm.experimental.convergence.loop()643 644 ; This intrinsic is not convergent. This is only because the backend doesn't645 ; support convergent operations yet.646 declare spir_func i32 @_Z3absi(i32) convergent647 )";648 649 const auto *R = runAnalysis(Assembly).getTopLevelRegion();650 const auto *L1 = getRegionWithEntry("l1_header");651 const auto *L2 = getRegionWithEntry("l2_header");652 653 EXPECT_EQ(R->Children.size(), 1ul);654 EXPECT_EQ(L1->Children.size(), 1ul);655 EXPECT_EQ(L1->Parent, R);656 EXPECT_EQ(L2->Parent, L1);657 658 EXPECT_EQ(R->Entry->getName(), "");659 EXPECT_EQ(R->Exits.size(), 1ul);660 EXPECT_THAT(R->Exits, ContainsBasicBlock("end"));661 662 EXPECT_EQ(L1->Entry->getName(), "l1_header");663 EXPECT_EQ(L1->Exits.size(), 2ul);664 EXPECT_THAT(L1->Exits, ContainsBasicBlock("l1_header"));665 EXPECT_THAT(L1->Exits, ContainsBasicBlock("l2_condition_true"));666 667 checkRegionBlocks(L1,668 {"l1_header", "l1_body", "l2_header", "l2_body",669 "l2_condition_false", "l2_condition_true", "l2_continue",670 "l2_exit", "l1_continue"},671 {"", "l1_exit", "end"});672 673 EXPECT_EQ(L2->Entry->getName(), "l2_header");674 EXPECT_EQ(L2->Exits.size(), 2ul);675 EXPECT_THAT(L2->Exits, ContainsBasicBlock("l2_header"));676 EXPECT_THAT(L2->Exits, ContainsBasicBlock("l2_body"));677 checkRegionBlocks(678 L2, {"l2_header", "l2_body", "l2_condition_false", "l2_continue"},679 {"", "l1_header", "l1_body", "l2_exit", "l1_continue",680 "l2_condition_true", "l1_exit", "end"});681}682 683TEST_F(SPIRVConvergenceRegionAnalysisTest, SingleLoopMultipleExits) {684 StringRef Assembly = R"(685 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {686 %t1 = call token @llvm.experimental.convergence.entry()687 %cond = icmp ne i32 0, 0688 br label %l1689 690 l1:691 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]692 br i1 %cond, label %l1_body, label %l1_exit693 694 l1_body:695 switch i32 0, label %sw.default.exit [696 i32 0, label %sw.bb697 i32 1, label %sw.bb1698 i32 2, label %sw.bb2699 ]700 701 sw.default.exit:702 br label %sw.default703 704 sw.default:705 br label %l1_end706 707 sw.bb:708 br label %l1_end709 710 sw.bb1:711 br label %l1_continue712 713 sw.bb2:714 br label %sw.default715 716 l1_continue:717 br label %l1718 719 l1_exit:720 br label %l1_end721 722 l1_end:723 br label %end724 725 end:726 ret void727 }728 729 declare token @llvm.experimental.convergence.entry()730 declare token @llvm.experimental.convergence.control()731 declare token @llvm.experimental.convergence.loop()732 )";733 734 runAnalysis(Assembly).getTopLevelRegion();735 const auto *L = getRegionWithEntry("l1");736 ASSERT_NE(L, nullptr);737 738 EXPECT_EQ(L->Entry, getBlock("l1"));739 EXPECT_EQ(L->Exits.size(), 2ul);740 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1"));741 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));742 743 checkRegionBlocks(L, {"l1", "l1_body", "l1_continue", "sw.bb1"},744 {"", "sw.default.exit", "sw.default", "l1_end", "end",745 "sw.bb", "sw.bb2", "l1_exit"});746}747 748TEST_F(SPIRVConvergenceRegionAnalysisTest,749 SingleLoopMultipleExitsWithPartialConvergence) {750 StringRef Assembly = R"(751 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {752 %t1 = call token @llvm.experimental.convergence.entry()753 %cond = icmp ne i32 0, 0754 br label %l1755 756 l1:757 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]758 br i1 %cond, label %l1_body, label %l1_exit759 760 l1_body:761 switch i32 0, label %sw.default.exit [762 i32 0, label %sw.bb763 i32 1, label %sw.bb1764 i32 2, label %sw.bb2765 ]766 767 sw.default.exit:768 br label %sw.default769 770 sw.default:771 %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]772 br label %l1_end773 774 sw.bb:775 br label %l1_end776 777 sw.bb1:778 br label %l1_continue779 780 sw.bb2:781 br label %sw.default782 783 l1_continue:784 br label %l1785 786 l1_exit:787 br label %l1_end788 789 l1_end:790 br label %end791 792 end:793 ret void794 }795 796 declare token @llvm.experimental.convergence.entry()797 declare token @llvm.experimental.convergence.control()798 declare token @llvm.experimental.convergence.loop()799 800 ; This intrinsic is not convergent. This is only because the backend doesn't801 ; support convergent operations yet.802 declare spir_func i32 @_Z3absi(i32) convergent803 )";804 805 runAnalysis(Assembly).getTopLevelRegion();806 const auto *L = getRegionWithEntry("l1");807 ASSERT_NE(L, nullptr);808 809 EXPECT_EQ(L->Entry, getBlock("l1"));810 EXPECT_EQ(L->Exits.size(), 3ul);811 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1"));812 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));813 EXPECT_THAT(L->Exits, ContainsBasicBlock("sw.default"));814 815 checkRegionBlocks(L,816 {"l1", "l1_body", "l1_continue", "sw.bb1",817 "sw.default.exit", "sw.bb2", "sw.default"},818 {"", "l1_end", "end", "sw.bb", "l1_exit"});819}820 821TEST_F(SPIRVConvergenceRegionAnalysisTest,822 SingleLoopWithDeepConvergenceBranch) {823 StringRef Assembly = R"(824 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {825 %t1 = call token @llvm.experimental.convergence.entry()826 %1 = icmp ne i32 0, 0827 br label %l1_header828 829 l1_header:830 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]831 br i1 %1, label %l1_body, label %l1_end832 833 l1_body:834 %2 = icmp ne i32 0, 0835 br i1 %2, label %l1_condition_true, label %l1_condition_false836 837 l1_condition_true:838 br label %a839 840 a:841 br label %b842 843 b:844 br label %c845 846 c:847 %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]848 br label %end849 850 l1_condition_false:851 br label %l1_continue852 853 l1_continue:854 br label %l1_header855 856 l1_end:857 br label %end858 859 end:860 ret void861 }862 863 declare token @llvm.experimental.convergence.entry()864 declare token @llvm.experimental.convergence.control()865 declare token @llvm.experimental.convergence.loop()866 867 ; This intrinsic is not convergent. This is only because the backend doesn't868 ; support convergent operations yet.869 declare spir_func i32 @_Z3absi(i32) convergent870 )";871 872 runAnalysis(Assembly).getTopLevelRegion();873 const auto *L = getRegionWithEntry("l1_header");874 ASSERT_NE(L, nullptr);875 876 EXPECT_EQ(L->Entry, getBlock("l1_header"));877 EXPECT_EQ(L->Exits.size(), 2ul);878 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));879 EXPECT_THAT(L->Exits, ContainsBasicBlock("c"));880 881 checkRegionBlocks(L,882 {"l1_header", "l1_body", "l1_continue",883 "l1_condition_false", "l1_condition_true", "a", "b", "c"},884 {"", "l1_end", "end"});885}886 887TEST_F(SPIRVConvergenceRegionAnalysisTest,888 SingleLoopWithDeepConvergenceLateBranch) {889 StringRef Assembly = R"(890 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {891 %t1 = call token @llvm.experimental.convergence.entry()892 %1 = icmp ne i32 0, 0893 br label %l1_header894 895 l1_header:896 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]897 br i1 %1, label %l1_body, label %l1_end898 899 l1_body:900 %2 = icmp ne i32 0, 0901 br i1 %2, label %l1_condition_true, label %l1_condition_false902 903 l1_condition_true:904 br label %a905 906 a:907 br label %b908 909 b:910 br i1 %2, label %c, label %d911 912 c:913 %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]914 br label %end915 916 d:917 br label %end918 919 l1_condition_false:920 br label %l1_continue921 922 l1_continue:923 br label %l1_header924 925 l1_end:926 br label %end927 928 end:929 ret void930 }931 932 declare token @llvm.experimental.convergence.entry()933 declare token @llvm.experimental.convergence.control()934 declare token @llvm.experimental.convergence.loop()935 936 ; This intrinsic is not convergent. This is only because the backend doesn't937 ; support convergent operations yet.938 declare spir_func i32 @_Z3absi(i32) convergent939 )";940 941 runAnalysis(Assembly).getTopLevelRegion();942 const auto *L = getRegionWithEntry("l1_header");943 ASSERT_NE(L, nullptr);944 945 EXPECT_EQ(L->Entry, getBlock("l1_header"));946 EXPECT_EQ(L->Exits.size(), 3ul);947 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));948 EXPECT_THAT(L->Exits, ContainsBasicBlock("b"));949 EXPECT_THAT(L->Exits, ContainsBasicBlock("c"));950 951 checkRegionBlocks(L,952 {"l1_header", "l1_body", "l1_continue",953 "l1_condition_false", "l1_condition_true", "a", "b", "c"},954 {"", "l1_end", "end", "d"});955}956 957TEST_F(SPIRVConvergenceRegionAnalysisTest,958 SingleLoopWithNoConvergenceIntrinsics) {959 StringRef Assembly = R"(960 define void @main() "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {961 %1 = icmp ne i32 0, 0962 br label %l1_header963 964 l1_header:965 br i1 %1, label %l1_body, label %l1_end966 967 l1_body:968 %2 = icmp ne i32 0, 0969 br i1 %2, label %l1_condition_true, label %l1_condition_false970 971 l1_condition_true:972 br label %a973 974 a:975 br label %end976 977 l1_condition_false:978 br label %l1_continue979 980 l1_continue:981 br label %l1_header982 983 l1_end:984 br label %end985 986 end:987 ret void988 }989 )";990 991 runAnalysis(Assembly).getTopLevelRegion();992 const auto *L = getRegionWithEntry("l1_header");993 ASSERT_NE(L, nullptr);994 995 EXPECT_EQ(L->Entry, getBlock("l1_header"));996 EXPECT_EQ(L->Exits.size(), 2ul);997 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_header"));998 EXPECT_THAT(L->Exits, ContainsBasicBlock("l1_body"));999 1000 checkRegionBlocks(1001 L, {"l1_header", "l1_body", "l1_continue", "l1_condition_false"},1002 {"", "l1_end", "end", "l1_condition_true", "a"});1003}1004 1005TEST_F(SPIRVConvergenceRegionAnalysisTest, SimpleFunction) {1006 StringRef Assembly = R"(1007 define void @main() "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {1008 ret void1009 }1010 )";1011 1012 const auto *R = runAnalysis(Assembly).getTopLevelRegion();1013 ASSERT_NE(R, nullptr);1014 1015 EXPECT_EQ(R->Entry, getBlock(""));1016 EXPECT_EQ(R->Exits.size(), 1ul);1017 EXPECT_THAT(R->Exits, ContainsBasicBlock(""));1018 EXPECT_TRUE(R->contains(getBlock("")));1019}1020 1021TEST_F(SPIRVConvergenceRegionAnalysisTest, NestedLoopInBreak) {1022 StringRef Assembly = R"(1023 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {1024 %t1 = call token @llvm.experimental.convergence.entry()1025 %1 = icmp ne i32 0, 01026 br label %l11027 1028 l1:1029 %tl1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %t1) ]1030 br i1 %1, label %l1_body, label %l1_to_end1031 1032 l1_body:1033 br i1 %1, label %cond_inner, label %l1_continue1034 1035 cond_inner:1036 br label %l21037 1038 l2:1039 %tl2 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tl1) ]1040 br i1 %1, label %l2_body, label %l2_end1041 1042 l2_body:1043 %call = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl2) ]1044 br label %l2_continue1045 1046 l2_continue:1047 br label %l21048 1049 l2_end:1050 br label %l2_exit1051 1052 l2_exit:1053 %call2 = call spir_func i32 @_Z3absi(i32 0) [ "convergencectrl"(token %tl1) ]1054 br label %l1_end1055 1056 l1_continue:1057 br label %l11058 1059 l1_to_end:1060 br label %l1_end1061 1062 l1_end:1063 br label %end1064 1065 end:1066 ret void1067 }1068 1069 declare token @llvm.experimental.convergence.entry()1070 declare token @llvm.experimental.convergence.control()1071 declare token @llvm.experimental.convergence.loop()1072 declare spir_func i32 @_Z3absi(i32) convergent1073 )";1074 1075 const auto *R = runAnalysis(Assembly).getTopLevelRegion();1076 ASSERT_NE(R, nullptr);1077 1078 EXPECT_EQ(R->Children.size(), 1ul);1079 1080 const auto *L1 = R->Children[0];1081 EXPECT_EQ(L1->Children.size(), 1ul);1082 EXPECT_EQ(L1->Entry->getName(), "l1");1083 EXPECT_EQ(L1->Exits.size(), 2ul);1084 EXPECT_THAT(L1->Exits, ContainsBasicBlock("l1"));1085 EXPECT_THAT(L1->Exits, ContainsBasicBlock("l2_exit"));1086 checkRegionBlocks(L1,1087 {"l1", "l1_body", "l1_continue", "cond_inner", "l2",1088 "l2_body", "l2_end", "l2_continue", "l2_exit"},1089 {"", "l1_to_end", "l1_end", "end"});1090 1091 const auto *L2 = L1->Children[0];1092 EXPECT_EQ(L2->Children.size(), 0ul);1093 EXPECT_EQ(L2->Entry->getName(), "l2");1094 EXPECT_EQ(L2->Exits.size(), 1ul);1095 EXPECT_THAT(L2->Exits, ContainsBasicBlock("l2"));1096 checkRegionBlocks(L2, {"l2", "l2_body", "l2_continue"},1097 {"", "l1_to_end", "l1_end", "end", "l1", "l1_body",1098 "l1_continue", "cond_inner", "l2_end", "l2_exit"});1099}1100