From b042d2d26a27a3715988c9829f628eaa416aba62 Mon Sep 17 00:00:00 2001 From: kkyzylov Date: Thu, 10 Nov 2016 18:37:55 +0300 Subject: Change ordering of blocks as required by SPIRV Spec (#195) --- lib/SPIRV/SPIRVRegularizeLLVM.cpp | 38 +++++++++++++++ test/OpLine.ll | 25 +++++----- test/block_ordering.ll | 99 +++++++++++++++++++++++++++++++++++++++ test/unreachable.ll | 45 ++++++------------ 4 files changed, 165 insertions(+), 42 deletions(-) create mode 100644 test/block_ordering.ll diff --git a/lib/SPIRV/SPIRVRegularizeLLVM.cpp b/lib/SPIRV/SPIRVRegularizeLLVM.cpp index 1631b61..022d2c1 100644 --- a/lib/SPIRV/SPIRVRegularizeLLVM.cpp +++ b/lib/SPIRV/SPIRVRegularizeLLVM.cpp @@ -42,8 +42,10 @@ #include "SPIRVMDBuilder.h" #include "SPIRVMDWalker.h" +#include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/StringSwitch.h" #include "llvm/ADT/Triple.h" +#include "llvm/IR/CFG.h" #include "llvm/IR/InstVisitor.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IRBuilder.h" @@ -81,6 +83,8 @@ public: void lowerFuncPtr(Function *F, Op OC); void lowerFuncPtr(Module *M); + bool getSwitchCaseOrdering(BasicBlock *BB); + static char ID; private: Module *M; @@ -154,6 +158,22 @@ SPIRVRegularizeLLVM::regularize() { } } } + + if (F->getBasicBlockList().size() < 2) + continue; + // The order of blocks in a function must satisfy the rule + // that blocks appear before all blocks they dominate. + // We iterate over the SCCs in a graph in post-order + for (scc_iterator SCCI = scc_begin(F); !SCCI.isAtEnd(); ++SCCI) { + const std::vector &NextSCC = *SCCI; + assert(!NextSCC.empty()); + for (const auto &I : NextSCC) { + BasicBlock *BB = I; + // The order of blocks in switch instruction shouldn't be changed + if (!getSwitchCaseOrdering(BB)) + BB->moveAfter(&F->getEntryBlock()); + } + } } std::string Err; @@ -205,8 +225,26 @@ SPIRVRegularizeLLVM::lowerFuncPtr(Module* M) { lowerFuncPtr(I.first, I.second); } +bool +SPIRVRegularizeLLVM::getSwitchCaseOrdering(BasicBlock *BB) { + // The order of the BBs was reversed + // We want to restore the original order of switch statement + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + BasicBlock *Pred = *PI; + // Check if we have a case value + if (auto SI = dyn_cast(Pred->getTerminator())) { + BasicBlock* Default = SI->getDefaultDest(); + if (BB == Default) + BB->moveAfter(Pred); + else + BB->moveBefore(Default); + return true; + } + } + return false; } +} INITIALIZE_PASS(SPIRVRegularizeLLVM, "spvregular", "Regularize LLVM for SPIR-V", false, false) diff --git a/test/OpLine.ll b/test/OpLine.ll index 9599b11..f983c43 100644 --- a/test/OpLine.ll +++ b/test/OpLine.ll @@ -83,29 +83,30 @@ if.then: ; preds = %while.body ; CHECK-LLVM: br label %if.end, !dbg ![[Line_7]] br label %if.end, !dbg !38 -; CHECK-SPIRV: Label [[if_else]] +; CHECK-SPIRV: Label [[if_end]] if.else: ; preds = %while.body +; CHECK-SPIRV: 4 Line [[str]] 5 0 +; CHECK-SPIRV-NEXT: Branch [[while_cond]] +; CHECK-LLVM: br label %while.cond, !dbg ![[Line_5]] + %add1 = add nsw i32 %a.addr.0, 1, !dbg !39 + call void @llvm.dbg.value(metadata i32 %add1, i64 0, metadata !28, metadata !25), !dbg !29 + %mul = mul nsw i32 %a.addr.0, 3, !dbg !41 + call void @llvm.dbg.value(metadata i32 %mul, i64 0, metadata !24, metadata !25), !dbg !26 + br label %if.end + +; CHECK-SPIRV: Label [[if_else]] +if.end: ; preds = %if.else, %if.then ; CHECK-SPIRV: 4 Line [[str]] 9 0 ; CHECK-SPIRV-NEXT: IAdd ; CHECK-LLVM: %add1 = add i32 %a.addr.0, 1, !dbg ![[Line_9:[0-9]+]] - %add1 = add nsw i32 %a.addr.0, 1, !dbg !39 - call void @llvm.dbg.value(metadata i32 %add1, i64 0, metadata !28, metadata !25), !dbg !29 ; CHECK-SPIRV: 4 Line [[str]] 10 0 ; CHECK-SPIRV-NEXT: IMul ; CHECK-LLVM: %mul = mul i32 %a.addr.0, 3, !dbg ![[Line_10:[0-9]+]] - %mul = mul nsw i32 %a.addr.0, 3, !dbg !41 - call void @llvm.dbg.value(metadata i32 %mul, i64 0, metadata !24, metadata !25), !dbg !26 ; CHECK-SPIRV-NEXT: Branch [[if_end]] ; CHECK-LLVM: br label %if.end, !dbg ![[Line_10]] - br label %if.end - -; CHECK-SPIRV: Label [[if_end]] -if.end: ; preds = %if.else, %if.then %b.1 = phi i32 [ %sub, %if.then ], [ %add1, %if.else ] %a.addr.1 = phi i32 [ %a.addr.0, %if.then ], [ %mul, %if.else ] -; CHECK-SPIRV: 4 Line [[str]] 5 0 -; CHECK-SPIRV-NEXT: Branch [[while_cond]] -; CHECK-LLVM: br label %while.cond, !dbg ![[Line_5]] + br label %while.cond, !dbg !30 ; CHECK-SPIRV: Label [[while_end]] diff --git a/test/block_ordering.ll b/test/block_ordering.ll new file mode 100644 index 0000000..7cb0317 --- /dev/null +++ b/test/block_ordering.ll @@ -0,0 +1,99 @@ +; RUN: llvm-as %s -o %t.bc +; RUN: llvm-spirv %t.bc -spirv-text -o %t.spt +; RUN: FileCheck < %t.spt %s --check-prefix=CHECK-SPIRV +; RUN: llvm-spirv %t.bc -o %t.spv +; RUN: llvm-spirv -r %t.spv -o %t.bc +; RUN: llvm-dis < %t.bc | FileCheck %s --check-prefix=CHECK-LLVM + +; CHECK-SPIRV: 2 Label [[entry:[0-9]+]] +; CHECK-SPIRV: 2 Branch [[test:[0-9]+]] +; CHECK-LLVM: entry: +; CHECK-LLVM: br label %test + +; CHECK-SPIRV: 2 Label [[test]] +; CHECK-SPIRV: 4 BranchConditional {{[0-9]+}} [[if_then2:[0-9]+]] [[if_end3:[0-9]+]] +; CHECK-LLVM: test: +; CHECK-LLVM: preds = %if.end, %entry +; CHECK-LLVM: br i1 %tobool1, label %if.then2, label %if.end3 + +; CHECK-SPIRV: 2 Label [[if_then2]] +; CHECK-SPIRV: 2 Branch [[loop:[0-9]+]] +; CHECK-LLVM: if.then2: +; CHECK-LLVM: preds = %test +; CHECK-LLVM: br label %loop + +; CHECK-SPIRV: 2 Label [[loop]] +; CHECK-SPIRV: 4 BranchConditional {{[0-9]+}} [[if_then:[0-9]+]] [[if_end:[0-9]+]] +; CHECK-LLVM: loop: +; CHECK-LLVM: preds = %if.then2 +; CHECK-LLVM: br i1 %tobool, label %if.then, label %if.end + +; CHECK-SPIRV: 2 Label [[if_then]] +; CHECK-SPIRV: 2 Branch [[if_end]] +; CHECK-LLVM: if.then: +; CHECK-LLVM: preds = %loop +; CHECK-LLVM: br label %if.end + +; CHECK-SPIRV: 2 Label [[if_end]] +; CHECK-SPIRV: 2 Branch [[test]] +; CHECK-LLVM: if.end: +; CHECK-LLVM: preds = %if.then, %loop +; CHECK-LLVM: br label %test + +; CHECK-SPIRV: 2 Label [[if_end3]] +; CHECK-LLVM: if.end3: +; CHECK-LLVM: preds = %test + +; ModuleID = 'main' +target datalayout = "e-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-n8:16:32:64" +target triple = "spir64-unknown-unknown" + +; Function Attrs: nounwind +define spir_kernel void @test_kernel(i32 addrspace(1)* %results) #0 { +entry: + br label %test + +loop: ; preds = %if.then2 + %tobool = icmp ne i32 %ix.1, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: ; preds = %loop + br label %if.end + +if.end: ; preds = %if.then, %loop + %ix.0 = phi i32 [ 20, %if.then ], [ %ix.1, %loop ] + br label %test + +test: ; preds = %if.end, %entry + %ix.1 = phi i32 [ 10, %entry ], [ %ix.0, %if.end ] + %tobool1 = icmp ne i32 %ix.1, 0 + br i1 %tobool1, label %if.then2, label %if.end3 + +if.then2: ; preds = %test + br label %loop + +if.end3: ; preds = %test + ret void +} + +attributes #0 = { nounwind "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-realign-stack" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" } + +!opencl.kernels = !{!0} +!opencl.enable.FP_CONTRACT = !{} +!opencl.spir.version = !{!6} +!opencl.ocl.version = !{!7} +!opencl.used.extensions = !{!8} +!opencl.used.optional.core.features = !{!8} +!opencl.compiler.options = !{!8} +!llvm.ident = !{!9} + +!0 = !{void (i32 addrspace(1)*)* @test_kernel, !1, !2, !3, !4, !5} +!1 = !{!"kernel_arg_addr_space", i32 1} +!2 = !{!"kernel_arg_access_qual", !"none"} +!3 = !{!"kernel_arg_type", !"int*"} +!4 = !{!"kernel_arg_base_type", !"int*"} +!5 = !{!"kernel_arg_type_qual", !""} +!6 = !{i32 1, i32 2} +!7 = !{i32 2, i32 0} +!8 = !{} +!9 = !{!"clang version 3.6.1"} \ No newline at end of file diff --git a/test/unreachable.ll b/test/unreachable.ll index 201eedc..4b98534 100644 --- a/test/unreachable.ll +++ b/test/unreachable.ll @@ -13,44 +13,29 @@ target datalayout = "e-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256: target triple = "spir64-unknown-unknown" ; Function Attrs: nounwind -define spir_kernel void @unreachable_simple(i32 addrspace(1)* nocapture %in, i32 addrspace(1)* %out) #0 { - %1 = call spir_func i64 @_Z13get_global_idj(i32 0) #1 - %2 = shl i64 %1, 32 - %3 = ashr exact i64 %2, 32 - %4 = getelementptr inbounds i32 addrspace(1)* %in, i64 %3 - %5 = getelementptr inbounds i32 addrspace(1)* %out, i64 %3 - br label %7 - ; No predecessors! +define spir_kernel void @unreachable_simple() #0 { +entry: unreachable - -;