Change ordering of blocks as required by SPIRV Spec (#195)

4 files changed, 165 insertions, 42 deletions

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<Function*> SCCI = scc_begin(F); !SCCI.isAtEnd(); ++SCCI) {

+      const std::vector<BasicBlock *> &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<SwitchInst>(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

-

-; <label>:7                                       ; preds = %0

-  %8 = load i32 addrspace(1)* %4

-  store i32 %8, i32 addrspace(1)* %5

-  ret void

 }

 

-; Function Attrs: nounwind readnone

-declare spir_func i64 @_Z13get_global_idj(i32) #1

-

 attributes #0 = { nounwind }

-attributes #1 = { nounwind readnone }

 

 !opencl.kernels = !{!0}

 !opencl.enable.FP_CONTRACT = !{}

-!spirv.Source = !{!6}

-!opencl.spir.version = !{!7}

+!opencl.spir.version = !{!6}

 !opencl.ocl.version = !{!7}

 !opencl.used.extensions = !{!8}

 !opencl.used.optional.core.features = !{!8}

-!spirv.Generator = !{!9}

-

-!0 = !{void (i32 addrspace(1)*, i32 addrspace(1)*)* @unreachable_simple, !1, !2, !3, !4, !5}

-!1 = !{!"kernel_arg_addr_space", i32 1, i32 1}

-!2 = !{!"kernel_arg_access_qual", !"none", !"none"}

-!3 = !{!"kernel_arg_type", !"int*", !"int*"}

-!4 = !{!"kernel_arg_type_qual", !"", !""}

-!5 = !{!"kernel_arg_base_type", !"int*", !"int*"}

-!6 = !{i32 3, i32 102000}

-!7 = !{i32 1, i32 2}

+!opencl.compiler.options = !{!8}

+!llvm.ident = !{!9}

+

+!0 = !{void ()* @unreachable_simple, !1, !2, !3, !4, !5}

+!1 = !{!"kernel_arg_addr_space"}

+!2 = !{!"kernel_arg_access_qual"}

+!3 = !{!"kernel_arg_type"}

+!4 = !{!"kernel_arg_base_type"}

+!5 = !{!"kernel_arg_type_qual"}

+!6 = !{i32 1, i32 2}

+!7 = !{i32 2, i32 0}

 !8 = !{}

-!9 = !{i16 7, i16 0}
\ No newline at end of file
+!9 = !{!"clang version 3.6.1"}