llvm/unittests/Target/SPIRV/SPIRVSortBlocksTests.cpp

   1 //===- SPIRVSortBlocksTests.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 "SPIRVUtils.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 namespace llvm;
  27 using namespace llvm::SPIRV;
  28
  29 class SPIRVSortBlocksTest : public testing::Test {
  30 protected:
  31   void TearDown() override { M.reset(); }
  32
  33   bool run(StringRef Assembly) {
  34     assert(M == nullptr &&
  35            "Calling runAnalysis multiple times is unsafe. See getAnalysis().");
  36
  37     SMDiagnostic Error;
  38     M = parseAssemblyString(Assembly, Error, Context);
  39     assert(M && "Bad assembly. Bad test?");
  40     llvm::Function *F = M->getFunction("main");
  41     return sortBlocks(*F);
  42   }
  43
  44   void checkBasicBlockOrder(std::vector<const char *> &&Expected) {
  45     llvm::Function *F = M->getFunction("main");
  46     auto It = F->begin();
  47     for (const char *Name : Expected) {
  48       ASSERT_TRUE(It != F->end())
  49           << "Expected block \"" << Name
  50           << "\" but reached the end of the function instead.";
  51       ASSERT_TRUE(It->getName() == Name)
  52           << "Error: expected block \"" << Name << "\" got \"" << It->getName()
  53           << "\"";
  54       It++;
  55     }
  56     ASSERT_TRUE(It == F->end())
  57         << "No more blocks were expected, but function has more.";
  58   }
  59
  60 protected:
  61   LLVMContext Context;
  62   std::unique_ptr<Module> M;
  63 };
  64
  65 TEST_F(SPIRVSortBlocksTest, DefaultRegion) {
  66   StringRef Assembly = R"(
  67     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
  68       ret void
  69     }
  70   )";
  71
  72   // No sorting is required.
  73   EXPECT_FALSE(run(Assembly));
  74 }
  75
  76 TEST_F(SPIRVSortBlocksTest, BasicBlockSwap) {
  77   StringRef Assembly = R"(
  78     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
  79     entry:
  80       br label %middle
  81     exit:
  82       ret void
  83     middle:
  84       br label %exit
  85     }
  86   )";
  87
  88   EXPECT_TRUE(run(Assembly));
  89   checkBasicBlockOrder({"entry", "middle", "exit"});
  90 }
  91
  92 // Skip condition:
  93 //         +-> A -+
  94 //  entry -+      +-> C
  95 //         +------+
  96 TEST_F(SPIRVSortBlocksTest, SkipCondition) {
  97   StringRef Assembly = R"(
  98     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
  99     entry:
 100       %1 = icmp ne i32 0, 0
 101       br i1 %1, label %c, label %a
 102     c:
 103       ret void
 104     a:
 105       br label %c
 106     }
 107   )";
 108
 109   EXPECT_TRUE(run(Assembly));
 110   checkBasicBlockOrder({"entry", "a", "c"});
 111 }
 112
 113 // Simple loop:
 114 // entry -> header <-----------------+
 115 //           | `-> body -> continue -+
 116 //           `-> end
 117 TEST_F(SPIRVSortBlocksTest, LoopOrdering) {
 118   StringRef Assembly = R"(
 119     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 120     entry:
 121       %1 = icmp ne i32 0, 0
 122       br label %header
 123     end:
 124       ret void
 125     body:
 126       br label %continue
 127     continue:
 128       br label %header
 129     header:
 130       br i1 %1, label %body, label %end
 131     }
 132   )";
 133
 134   EXPECT_TRUE(run(Assembly));
 135   checkBasicBlockOrder({"entry", "header", "end", "body", "continue"});
 136 }
 137
 138 // Diamond condition:
 139 //         +-> A -+
 140 //  entry -+      +-> C
 141 //         +-> B -+
 142 //
 143 // A and B order can be flipped with no effect, but it must be remain
 144 // deterministic/stable.
 145 TEST_F(SPIRVSortBlocksTest, DiamondCondition) {
 146   StringRef Assembly = R"(
 147     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 148     entry:
 149       %1 = icmp ne i32 0, 0
 150       br i1 %1, label %b, label %a
 151     c:
 152       ret void
 153     b:
 154       br label %c
 155     a:
 156       br label %c
 157     }
 158   )";
 159
 160   EXPECT_TRUE(run(Assembly));
 161   checkBasicBlockOrder({"entry", "a", "b", "c"});
 162 }
 163
 164 // Crossing conditions:
 165 //             +------+  +-> C -+
 166 //         +-> A -+   |  |      |
 167 //  entry -+      +--_|_-+      +-> E
 168 //         +-> B -+   |         |
 169 //             +------+----> D -+
 170 //
 171 // A & B have the same rank.
 172 // C & D have the same rank, but are after A & B.
 173 // E if the last block.
 174 TEST_F(SPIRVSortBlocksTest, CrossingCondition) {
 175   StringRef Assembly = R"(
 176     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 177     entry:
 178       %1 = icmp ne i32 0, 0
 179       br i1 %1, label %b, label %a
 180     e:
 181       ret void
 182     c:
 183       br label %e
 184     b:
 185       br i1 %1, label %d, label %c
 186     d:
 187       br label %e
 188     a:
 189       br i1 %1, label %d, label %c
 190     }
 191   )";
 192
 193   EXPECT_TRUE(run(Assembly));
 194   checkBasicBlockOrder({"entry", "a", "b", "c", "d", "e"});
 195 }
 196
 197 // Irreducible CFG
 198 // digraph {
 199 //    entry -> A;
 200 //
 201 //    A -> B;
 202 //    A -> C;
 203 //
 204 //    B -> A;
 205 //    B -> C;
 206 //
 207 //    C -> B;
 208 // }
 209 //
 210 // Order starts with Entry and A. Order of B and C can change, but must remain
 211 // stable.
 212 // In such case, rank will be defined by the arbitrary traversal order. What's
 213 // important is to have a stable value.
 214 TEST_F(SPIRVSortBlocksTest, IrreducibleOrdering) {
 215   StringRef Assembly = R"(
 216     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 217     entry:
 218       %1 = icmp ne i32 0, 0
 219       br label %a
 220
 221     b:
 222       br i1 %1, label %a, label %c
 223
 224     c:
 225       br label %b
 226
 227     a:
 228       br i1 %1, label %b, label %c
 229
 230     }
 231   )";
 232
 233   EXPECT_TRUE(run(Assembly));
 234   checkBasicBlockOrder({"entry", "a", "b", "c"});
 235 }
 236
 237 TEST_F(SPIRVSortBlocksTest, IrreducibleOrderingBeforeReduction) {
 238   StringRef Assembly = R"(
 239     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 240     entry:
 241       %1 = icmp ne i32 0, 0
 242       br label %a
 243
 244     c:
 245       br i1 %1, label %e, label %d
 246
 247     e:
 248       ret void
 249
 250     b:
 251       br i1 %1, label %c, label %d
 252
 253     a:
 254       br label %b
 255
 256     d:
 257       br i1 %1, label %b, label %c
 258
 259     }
 260   )";
 261
 262   EXPECT_TRUE(run(Assembly));
 263   checkBasicBlockOrder({"entry", "a", "b", "c", "d", "e"});
 264 }
 265
 266 TEST_F(SPIRVSortBlocksTest, LoopDiamond) {
 267   StringRef Assembly = R"(
 268     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 269     entry:
 270       %1 = icmp ne i32 0, 0
 271       br label %header
 272     header:
 273       br i1 %1, label %body, label %end
 274     body:
 275       br i1 %1, label %break, label %inside_a
 276     inside_a:
 277       br label %inside_b
 278     inside_b:
 279       br i1 %1, label %inside_d, label %inside_c
 280     inside_c:
 281       br label %continue
 282     inside_d:
 283       br label %continue
 284     break:
 285       br label %end
 286     continue:
 287       br label %header
 288     end:
 289       ret void
 290     }
 291   )";
 292
 293   EXPECT_TRUE(run(Assembly));
 294   checkBasicBlockOrder({"entry", "header", "body", "inside_a", "inside_b",
 295                         "inside_c", "inside_d", "continue", "break", "end"});
 296 }
 297
 298 TEST_F(SPIRVSortBlocksTest, LoopNested) {
 299   StringRef Assembly = R"(
 300     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 301     entry:
 302       %1 = icmp ne i32 0, 0
 303       br label %a
 304     a:
 305       br i1 %1, label %h, label %b
 306     b:
 307       br label %c
 308     c:
 309       br i1 %1, label %d, label %e
 310     d:
 311       br label %g
 312     e:
 313       br label %f
 314     f:
 315       br label %c
 316     g:
 317       br label %a
 318     h:
 319       ret void
 320     }
 321   )";
 322
 323   EXPECT_TRUE(run(Assembly));
 324   checkBasicBlockOrder({"entry", "a", "b", "c", "e", "f", "d", "g", "h"});
 325 }
 326
 327 TEST_F(SPIRVSortBlocksTest, IfNested) {
 328   StringRef Assembly = R"(
 329     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 330     entry:
 331       br i1 true, label %d, label %a
 332     i:
 333       br label %j
 334     j:
 335       ret void
 336     a:
 337       br i1 true, label %b, label %c
 338     d:
 339       br i1 true, label %f, label %e
 340     e:
 341       br label %i
 342     b:
 343       br label %c
 344     f:
 345       br i1 true, label %h, label %g
 346     g:
 347       br label %h
 348     c:
 349       br label %j
 350     h:
 351       br label %i
 352     }
 353   )";
 354   EXPECT_TRUE(run(Assembly));
 355   checkBasicBlockOrder(
 356       {"entry", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j"});
 357 }
 358
 359 // Same as above, but this time blocks are already sorted, so no need to reorder
 360 // them.
 361 TEST_F(SPIRVSortBlocksTest, IfNestedSorted) {
 362   StringRef Assembly = R"(
 363     define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {
 364     entry:
 365       br i1 true, label %d, label %z
 366     z:
 367       br i1 true, label %b, label %c
 368     b:
 369       br label %c
 370     c:
 371       br label %j
 372     d:
 373       br i1 true, label %f, label %e
 374     e:
 375       br label %i
 376     f:
 377       br i1 true, label %h, label %g
 378     g:
 379       br label %h
 380     h:
 381       br label %i
 382     i:
 383       br label %j
 384     j:
 385       ret void
 386     }
 387   )";
 388   EXPECT_FALSE(run(Assembly));
 389 }