[LoopUnroll+LoopUnswitch] do not transform loops containing callbr

[nickdesaulniers]

Summary

There is currently a correctness issue when unrolling loops containing
callbr's where their indirect targets are being updated correctly to the
newly created labels, but their operands are not. This manifests in
unrolled loops where the second and subsequent copies of callbr
instructions have blockaddresses of the label from the first instance of
the unrolled loop, which would result in nonsensical runtime control
flow.

For now, conservatively do not unroll the loop. In the future, I think
we can pursue unrolling such loops provided we transform the cloned
callbr's operands correctly.

Such a transform and its legalities are being discussed in:
https://reviews.llvm.org/D64101

Link: https://bugs.llvm.org/show_bug.cgi?id=42489
Link: https://groups.google.com/forum/#!topic/clang-built-linux/z-hRWP9KqPI

[nickdesaulniers]

• add back previous fixes from v2

[fhahn]

LGTM thanks. Please wait with committing a day or so, in case Hal or Eli have additional comments.

isSafeToClone is also used by LoopUnswitch, it would be good to add a test with callbr there as well, to make sure we do not miss it, in case we remove the restriction again.

[efriedma]

LGTM

[nickdesaulniers]

it would be good to add a test with callbr there as well, to make sure we do not miss it, in case we remove the restriction again.

I agree and would be happy to do so. Would you prefer that additional test case in this commit or a subsequent commit (either way, before I re-visit https://reviews.llvm.org/D64101)?

[hfinkel]

In D64368#1579690, @nickdesaulniers wrote:

it would be good to add a test with callbr there as well, to make sure we do not miss it, in case we remove the restriction again.

I agree and would be happy to do so. Would you prefer that additional test case in this commit or a subsequent commit (either way, before I re-visit https://reviews.llvm.org/D64101)?

Probably with this commit: If this gets reverted for whatever reason, that test would also need to be reverted, right?

Otherwise, LGTM too.

[nickdesaulniers]

• add test case for LoopUnswitch

[nickdesaulniers]

Thanks for the reviews thus far. Parting thoughts on the newly added test case (llvm/test/Transforms/LoopUnswitch/callbr.ll) before I commit, tomorrow?

llvm/trunk/lib/Analysis/LoopInfo.cpp

bool Loop::isLoopSimplifyForm() const {
   // exits have all their predecessors inside the loop.
   return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
 }
 
 // Routines that reform the loop CFG and split edges often fail on indirectbr.
 bool Loop::isSafeToClone() const {
   // Return false if any loop blocks contain indirectbrs, or there are any calls
   // to noduplicate functions.
+  // FIXME: it should be ok to clone CallBrInst's if we correctly update the
+  // operand list to reflect the newly cloned labels.
   for (BasicBlock *BB : this->blocks()) {
-    if (isa<IndirectBrInst>(BB->getTerminator()))
+    if (isa<IndirectBrInst>(BB->getTerminator()) ||
+        isa<CallBrInst>(BB->getTerminator()))
       return false;
 
     for (Instruction &I : *BB)
       if (auto CS = CallSite(&I))
         if (CS.cannotDuplicate())
           return false;
   }
   return true;

llvm/trunk/test/Transforms/LoopUnroll/callbr.ll

+; RUN: opt -loop-unroll -S %s | FileCheck %s
+
+; Check that the loop body exists.
+; CHECK: for.body
+; CHECK: if.then
+; CHECK: asm.fallthrough
+; CHECK: l_yes
+; CHECK: for.inc
+
+; Check that the loop body does not get unrolled.  We could modify this test in
+; the future to support loop unrolling callbr's IFF we checked that the callbr
+; operands were unrolled/updated correctly, as today they are not.
+; CHECK-NOT: if.then.1
+; CHECK-NOT: asm.fallthrough.1
+; CHECK-NOT: l_yes.1
+; CHECK-NOT: for.inc.1
+; CHECK-NOT: if.then.2
+; CHECK-NOT: asm.fallthrough.2
+; CHECK-NOT: l_yes.2
+; CHECK-NOT: for.inc.2
+
+define dso_local void @d() {
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.inc
+  ret void
+
+for.body:                                         ; preds = %for.inc, %entry
+  %e.04 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %tobool = icmp eq i32 %e.04, 0
+  br i1 %tobool, label %for.inc, label %if.then
+
+if.then:                                          ; preds = %for.body
+  callbr void asm sideeffect "1: nop\0A\09.quad b, ${0:l}, $$5\0A\09", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@d, %l_yes))
+          to label %asm.fallthrough [label %l_yes]
+
+asm.fallthrough:                                  ; preds = %if.then
+  br label %l_yes
+
+l_yes:                                            ; preds = %asm.fallthrough, %if.then
+  %call = tail call i32 (...) @g()
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %l_yes
+  %inc = add nuw nsw i32 %e.04, 1
+  %exitcond = icmp eq i32 %inc, 3
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+declare dso_local i32 @g(...) local_unnamed_addr

llvm/trunk/test/Transforms/LoopUnswitch/callbr.ll

+; RUN: opt -loop-unswitch %s -S | FileCheck %s
+
+; We want to check that the loop does not get split (so only 2 callbr's not 4).
+; It's ok to modify this test in the future should we allow the loop containing
+; callbr to be unswitched and are able to do so correctly.
+
+; CHECK: callbr void asm sideeffect "# ${0:l}", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10))
+; CHECK: to label %7 [label %10]
+; CHECK: callbr void asm sideeffect "# ${0:l}", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10))
+; CHECK: to label %9 [label %10]
+
+; CHECK-NOT: callbr void asm sideeffect "# ${0:l}", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10))
+; CHECK-NOT: to label %7 [label %10]
+; CHECK-NOT: callbr void asm sideeffect "# ${0:l}", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10))
+; CHECK-NOT: to label %9 [label %10]
+; CHECK-NOT: callbr void asm sideeffect "# ${0:l}", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %19))
+; CHECK-NOT: to label %16 [label %19]
+; CHECK-NOT: callbr void asm sideeffect "# ${0:l}", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %19))
+; CHECK-NOT: to label %18 [label %19]
+
+; This test is essentially:
+; void foo(int n) {
+;   for (int i = 0; i < 1000; ++i)
+;     if (n) {
+;       asm goto("# %l0"::::bar);
+;       bar:;
+;     } else {
+;       asm goto("# %l0"::::baz);
+;       baz:;
+;     }
+;}
+
+define dso_local void @foo(i32) #0 {
+  br label %2
+
+2:                                                ; preds = %10, %1
+  %.0 = phi i32 [ 0, %1 ], [ %11, %10 ]
+  %3 = icmp ult i32 %.0, 1000
+  br i1 %3, label %4, label %12
+
+4:                                                ; preds = %2
+  %5 = icmp eq i32 %0, 0
+  br i1 %5, label %8, label %6
+
+6:                                                ; preds = %4
+  callbr void asm sideeffect "# ${0:l}", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10)) #0
+    to label %7 [label %10]
+
+7:                                                ; preds = %6
+  br label %10
+
+8:                                                ; preds = %4
+  callbr void asm sideeffect "# ${0:l}", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@foo, %10)) #0
+    to label %9 [label %10]
+
+9:                                                ; preds = %8
+  br label %10
+
+10:                                               ; preds = %7, %6, %9, %8
+  %11 = add nuw nsw i32 %.0, 1
+  br label %2
+
+12:                                               ; preds = %2
+  ret void
+}
+