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 {
operator ==(const Value * V,const IsA &)33 friend bool operator==(const Value *V, const IsA &) { return isa<T>(V); }
34 };
35
36 class SPIRVConvergenceRegionAnalysisTest : public testing::Test {
37 protected:
SetUp()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
TearDown()50 void TearDown() override { M.reset(); }
51
runAnalysis(StringRef Assembly)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
getAnalysis()66 SPIRVConvergenceRegionAnalysis::Result &getAnalysis() {
67 assert(M != nullptr && "Has runAnalysis been called before?");
68 return FAM.getResult<SPIRVConvergenceRegionAnalysis>(*getFunction());
69 }
70
getFunction() const71 Function *getFunction() const {
72 assert(M != nullptr && "Has runAnalysis been called before?");
73 return M->getFunction("main");
74 }
75
getBlock(StringRef Name)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
getRegionWithEntry(StringRef Name)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
checkRegionBlocks(const ConvergenceRegion * R,std::initializer_list<const char * > InRegion,std::initializer_list<const char * > NotInRegion)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,DefaultRegion)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,DefaultRegionWithToken)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopOneRegion)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopLoopRegionParentsIsTopLevelRegion)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopExits)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopWithBreakExits)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopWithBreakRegionBlocks)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.
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopWithBreakNoConvergenceControl)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,TwoLoopsWithControl)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.
TEST_F(SPIRVConvergenceRegionAnalysisTest,LoopBothBranchExits)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,InnerLoopBreaks)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopMultipleExits)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopMultipleExitsWithPartialConvergence)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopWithDeepConvergenceBranch)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopWithDeepConvergenceLateBranch)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SingleLoopWithNoConvergenceIntrinsics)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,SimpleFunction)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
TEST_F(SPIRVConvergenceRegionAnalysisTest,NestedLoopInBreak)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 }
1102