390 lines · 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-exception6//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 26using namespace llvm;27using namespace llvm::SPIRV;28 29class SPIRVSortBlocksTest : public testing::Test {30protected: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 \"" << Name50 << "\" 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 60protected:61 LLVMContext Context;62 std::unique_ptr<Module> M;63};64 65TEST_F(SPIRVSortBlocksTest, DefaultRegion) {66 StringRef Assembly = R"(67 define void @main() convergent "hlsl.numthreads"="4,8,16" "hlsl.shader"="compute" {68 ret void69 }70 )";71 72 // No sorting is required.73 EXPECT_FALSE(run(Assembly));74}75 76TEST_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 %middle81 exit:82 ret void83 middle:84 br label %exit85 }86 )";87 88 EXPECT_TRUE(run(Assembly));89 checkBasicBlockOrder({"entry", "middle", "exit"});90}91 92// Skip condition:93// +-> A -+94// entry -+ +-> C95// +------+96TEST_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, 0101 br i1 %1, label %c, label %a102 c:103 ret void104 a:105 br label %c106 }107 )";108 109 EXPECT_TRUE(run(Assembly));110 checkBasicBlockOrder({"entry", "a", "c"});111}112 113// Simple loop:114// entry -> header <-----------------+115// | `-> body -> continue -+116// `-> end117TEST_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, 0122 br label %header123 end:124 ret void125 body:126 br label %continue127 continue:128 br label %header129 header:130 br i1 %1, label %body, label %end131 }132 )";133 134 EXPECT_TRUE(run(Assembly));135 checkBasicBlockOrder({"entry", "header", "end", "body", "continue"});136}137 138// Diamond condition:139// +-> A -+140// entry -+ +-> C141// +-> B -+142//143// A and B order can be flipped with no effect, but it must be remain144// deterministic/stable.145TEST_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, 0150 br i1 %1, label %b, label %a151 c:152 ret void153 b:154 br label %c155 a:156 br label %c157 }158 )";159 160 EXPECT_TRUE(run(Assembly));161 checkBasicBlockOrder({"entry", "a", "b", "c"});162}163 164// Crossing conditions:165// +------+ +-> C -+166// +-> A -+ | | |167// entry -+ +--_|_-+ +-> E168// +-> 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.174TEST_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, 0179 br i1 %1, label %b, label %a180 e:181 ret void182 c:183 br label %e184 b:185 br i1 %1, label %d, label %c186 d:187 br label %e188 a:189 br i1 %1, label %d, label %c190 }191 )";192 193 EXPECT_TRUE(run(Assembly));194 checkBasicBlockOrder({"entry", "a", "b", "c", "d", "e"});195}196 197// Irreducible CFG198// 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 remain211// stable.212// In such case, rank will be defined by the arbitrary traversal order. What's213// important is to have a stable value.214TEST_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, 0219 br label %a220 221 b:222 br i1 %1, label %a, label %c223 224 c:225 br label %b226 227 a:228 br i1 %1, label %b, label %c229 230 }231 )";232 233 EXPECT_TRUE(run(Assembly));234 checkBasicBlockOrder({"entry", "a", "b", "c"});235}236 237TEST_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, 0242 br label %a243 244 c:245 br i1 %1, label %e, label %d246 247 e:248 ret void249 250 b:251 br i1 %1, label %c, label %d252 253 a:254 br label %b255 256 d:257 br i1 %1, label %b, label %c258 259 }260 )";261 262 EXPECT_TRUE(run(Assembly));263 checkBasicBlockOrder({"entry", "a", "b", "c", "d", "e"});264}265 266TEST_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, 0271 br label %header272 header:273 br i1 %1, label %body, label %end274 body:275 br i1 %1, label %break, label %inside_a276 inside_a:277 br label %inside_b278 inside_b:279 br i1 %1, label %inside_d, label %inside_c280 inside_c:281 br label %continue282 inside_d:283 br label %continue284 break:285 br label %end286 continue:287 br label %header288 end:289 ret void290 }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 298TEST_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, 0303 br label %a304 a:305 br i1 %1, label %h, label %b306 b:307 br label %c308 c:309 br i1 %1, label %d, label %e310 d:311 br label %g312 e:313 br label %f314 f:315 br label %c316 g:317 br label %a318 h:319 ret void320 }321 )";322 323 EXPECT_TRUE(run(Assembly));324 checkBasicBlockOrder({"entry", "a", "b", "c", "e", "f", "d", "g", "h"});325}326 327TEST_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 %a332 i:333 br label %j334 j:335 ret void336 a:337 br i1 true, label %b, label %c338 d:339 br i1 true, label %f, label %e340 e:341 br label %i342 b:343 br label %c344 f:345 br i1 true, label %h, label %g346 g:347 br label %h348 c:349 br label %j350 h:351 br label %i352 }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 reorder360// them.361TEST_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 %z366 z:367 br i1 true, label %b, label %c368 b:369 br label %c370 c:371 br label %j372 d:373 br i1 true, label %f, label %e374 e:375 br label %i376 f:377 br i1 true, label %h, label %g378 g:379 br label %h380 h:381 br label %i382 i:383 br label %j384 j:385 ret void386 }387 )";388 EXPECT_FALSE(run(Assembly));389}390