Change callbr to only define its output SSA variable on the normal path, not the indirect targets.

[jyknight]

Summary

Fixes PR45565.

[rnk]

I think we should make this change. I have this idea that we can eliminate catchswitch by using callbr instead of invoke for Windows EH. Catchswitch effectively allows us to multiplex unwind edges from invoke and cleanupret. However, catchswitch blocks have no valid insertion point for non-phi instructions, and this causes a long tail of bugs where optimizers (somewhat reasonably) assume they can find an insertion point after any phi. Using callbr would help us make the CFG more accurate, and if we did that, we would want the return value to only be available on the normal edge.

If we do ever add support for asm blobs that have outputs along non-default edges, we can add some new IR construct for that (burn that bridge when we get there, as they say). asmbrpad, anyone?

[rnk]

There was discussion on the bugzilla bug, so please wait to get some agreement before landing this. Please don't wait for more feedback from me, I'm marking it accepted to indicate I'm happy with it.

Although, I suppose you should add a verifier test that shows that we reject inputs where a use on the non-default edge is not dominated by a def.

[efriedma]

Does this do something reasonable if one of the indirect destinations of the callbr is also the normal destination?

[nickdesaulniers]

In D78341#1989369, @rnk wrote:

I think we should make this change. I have this idea that we can eliminate catchswitch by using callbr instead of invoke for Windows EH. Catchswitch effectively allows us to multiplex unwind edges from invoke and cleanupret. However, catchswitch blocks have no valid insertion point for non-phi instructions, and this causes a long tail of bugs where optimizers (somewhat reasonably) assume they can find an insertion point after any phi. Using callbr would help us make the CFG more accurate, and if we did that, we would want the return value to only be available on the normal edge.

I would be happier if there were more users of callbr, which would help us find more bugs and edge cases. That would ultimately make it more resilient, and help spread the responsibility for it.

If we do ever add support for asm blobs that have outputs along non-default edges, we can add some new IR construct for that (burn that bridge when we get there, as they say). asmbrpad, anyone?

Let's cross that bridge when we get there. I don't think we need to design for something that no one has asked for yet.

In D78341#1989370, @rnk wrote:

Although, I suppose you should add a verifier test that shows that we reject inputs where a use on the non-default edge is not dominated by a def.

Some tests would be good.

In D78341#1989404, @efriedma wrote:

Does this do something reasonable if one of the indirect destinations of the callbr is also the normal destination?

I'm more concerned now about what we should do in the front end for these cases. Indeed https://bugs.llvm.org/show_bug.cgi?id=45565#c5 came from the Linux kernel, and with this change patched in, I now see this compiler crash for kernel/futex.c (previously, we'd only fail an assertion, unknown what bugs awaited in the generated code).

[efriedma]

I'm more concerned now about what we should do in the front end for these cases

In the frontend, it should be impossible for the normal destination to be the same as an indirect destination. Even if there's a label immediately after the asm goto, we should create an extra basic block between the asm goto and the label to emit whatever stores etc. are necessary.

[nickdesaulniers]

In D78341#1989625, @efriedma wrote:

I'm more concerned now about what we should do in the front end for these cases

In the frontend, it should be impossible for the normal destination to be the same as an indirect destination. Even if there's a label immediately after the asm goto, we should create an extra basic block between the asm goto and the label to emit whatever stores etc. are necessary.

Ah, sorry, my use of these cases was ambiguous. I was not referring to the case you were describing of the indirect target and fallthrough being the same BasicBlock at the IR level.

I was asking about the C code from the Linux kernel that now crashes LLVM (which maybe is better than a failed assert) with this patch applied:

int futex_lock_pi_atomic(void) {
  int d;
  asm goto("" : "=r"(d) : : : e);
e:
  return d;
}

Which indeed does have a basic block inserted by the IR, and a PHI thanks to James' patch, but produces crashes when compiling the Linux kernel.

[jyknight]

Fix crash reported by Nick, InstructionSimplify was bypassing the
Dominators code in some cases, and doing its own thing.

[nickdesaulniers]

Thanks! My test case from the kernel now builds with Diff 258438. Tests in tree pass, but with some additional test cases added in this CL, I'd be very happy to approve. Thanks @jyknight!

The only other thing of note: this patch changes the other error I'm tracking for "asm goto with outputs." https://reviews.llvm.org/D77849. I have assertions I'm working on in https://reviews.llvm.org/D78166 and https://reviews.llvm.org/D78234. With this change applied though, I instead hit the assertion:

clang-11: ../lib/CodeGen/InlineSpiller.cpp:1194: bool (anonymous namespace)::HoistSpillHelper::isSpillCandBB(llvm::LiveInterval &, llvm::VNInfo &, llvm::MachineBasicBlock &, unsigned int &): Assertion `OrigLI.getVNInfoAt(Idx) == &OrigVNI && "Unexpected VNI"' failed.

I suspect it's the same issue; but I could creduce the input (same file and pass, but different function). Either way, I'd rather take this patch, and follow up on that. Just making a note of a bunch of related CLs.

llvm/lib/Analysis/InstructionSimplify.cpp

225

../lib/Analysis/InstructionSimplify.cpp:225:35: error: unknown type name 'CallbrInst'; did you mean 'CallBrInst'?
      !isa<InvokeInst>(I) && !isa<CallbrInst>(I))
                                  ^~~~~~~~~~
                                  CallBrInst
../include/llvm/IR/Instruction.def:137:40: note: 'CallBrInst' declared here
HANDLE_TERM_INST  (11, CallBr        , CallBrInst) // A call-site terminator
                                       ^

[efriedma]

There's one part of this that's a little subtle: if an indirect destination is the same as the normal destination, the value is available at that destination even if the indirect edge is taken.

That's not necessarily a problem at the IR level, but we might need to special-case it in isel.

[jyknight]

In D78341#1989923, @efriedma wrote:

There's one part of this that's a little subtle: if an indirect destination is the same as the normal destination, the value is available at that destination even if the indirect edge is taken.

That's not necessarily a problem at the IR level, but we might need to special-case it in isel.

That's not actually possible: it results in an error "Duplicate callbr destination!".

[jyknight]

Updated with some tests. Committing this shortly.

[nickdesaulniers]

Thanks @jyknight !

llvm/docs/LangRef.rst

 Semantics:
 """"""""""
 
 This instruction is designed to operate as a standard '``call``'
 instruction in most regards. The primary difference is that it
 establishes an association with additional labels to define where control
 flow goes after the call.
 
-Outputs of a '``callbr``' instruction are valid only on the '``fallthrough``'
-path.  Use of outputs on the '``indirect``' path(s) results in :ref:`poison
-values <poisonvalues>`.
+The output values of a '``callbr``' instruction are available only to
+the '``fallthrough``' block, not to any '``indirect``' blocks(s).
 
 The only use of this today is to implement the "goto" feature of gcc inline
 assembly where additional labels can be provided as locations for the inline
 assembly to jump to.
 
 Example:
 """"""""
 

llvm/lib/Analysis/InstructionSimplify.cpp

static bool valueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) {
 
   // If we have a DominatorTree then do a precise test.
   if (DT)
     return DT->dominates(I, P);
 
   // Otherwise, if the instruction is in the entry block and is not an invoke,
   // then it obviously dominates all phi nodes.
   if (I->getParent() == &I->getFunction()->getEntryBlock() &&
-      !isa<InvokeInst>(I))
+      !isa<InvokeInst>(I) && !isa<CallBrInst>(I))
     return true;
 
   return false;
 }
 
 /// Simplify "A op (B op' C)" by distributing op over op', turning it into
 /// "(A op B) op' (A op C)".  Here "op" is given by Opcode and "op'" is
 /// given by OpcodeToExpand, while "A" corresponds to LHS and "B op' C" to RHS.

llvm/lib/Analysis/ValueTracking.cpp

bool llvm::canCreatePoison(const Instruction *I) {
   case Instruction::FPToUI:
     // fptosi/ui yields poison if the resulting value does not fit in the
     // destination type.
     return true;
   case Instruction::Call:
   case Instruction::CallBr:
   case Instruction::Invoke:
     // Function calls can return a poison value even if args are non-poison
-    // values. CallBr returns poison when jumping to indirect labels.
+    // values.
     return true;
   case Instruction::InsertElement:
   case Instruction::ExtractElement: {
     // If index exceeds the length of the vector, it returns poison
     auto *VTy = cast<VectorType>(I->getOperand(0)->getType());
     unsigned IdxOp = I->getOpcode() == Instruction::InsertElement ? 2 : 1;
     auto *Idx = dyn_cast<ConstantInt>(I->getOperand(IdxOp));
     if (!Idx || Idx->getZExtValue() >= VTy->getElementCount().Min)

llvm/lib/IR/Dominators.cpp

bool DominatorTree::dominates(const Instruction *Def,
   // An instruction doesn't dominate a use in itself.
   if (Def == User)
     return false;
 
   // The value defined by an invoke dominates an instruction only if it
   // dominates every instruction in UseBB.
   // A PHI is dominated only if the instruction dominates every possible use in
   // the UseBB.
-  if (isa<InvokeInst>(Def) || isa<PHINode>(User))
+  if (isa<InvokeInst>(Def) || isa<CallBrInst>(Def) || isa<PHINode>(User))
     return dominates(Def, UseBB);
 
   if (DefBB != UseBB)
     return dominates(DefBB, UseBB);
 
   return Def->comesBefore(User);
 }
 
bool DominatorTree::dominates(const Instruction *Def,
   // Invoke results are only usable in the normal destination, not in the
   // exceptional destination.
   if (const auto *II = dyn_cast<InvokeInst>(Def)) {
     BasicBlock *NormalDest = II->getNormalDest();
     BasicBlockEdge E(DefBB, NormalDest);
     return dominates(E, UseBB);
   }
 
+  // Callbr results are similarly only usable in the default destination.
+  if (const auto *CBI = dyn_cast<CallBrInst>(Def)) {
+    BasicBlock *NormalDest = CBI->getDefaultDest();
+    BasicBlockEdge E(DefBB, NormalDest);
+    return dominates(E, UseBB);
+  }
+
   return dominates(DefBB, UseBB);
 }
 
 bool DominatorTree::dominates(const BasicBlockEdge &BBE,
                               const BasicBlock *UseBB) const {
   // If the BB the edge ends in doesn't dominate the use BB, then the
   // edge also doesn't.
   const BasicBlock *Start = BBE.getStart();
bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
   // their own block, except possibly a phi, so we don't need to
   // walk the block in any case.
   if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
     BasicBlock *NormalDest = II->getNormalDest();
     BasicBlockEdge E(DefBB, NormalDest);
     return dominates(E, U);
   }
 
+  // Callbr results are similarly only usable in the default destination.
+  if (const auto *CBI = dyn_cast<CallBrInst>(Def)) {
+    BasicBlock *NormalDest = CBI->getDefaultDest();
+    BasicBlockEdge E(DefBB, NormalDest);
+    return dominates(E, U);
+  }
+
   // If the def and use are in different blocks, do a simple CFG dominator
   // tree query.
   if (DefBB != UseBB)
     return dominates(DefBB, UseBB);
 
   // Ok, def and use are in the same block. If the def is an invoke, it
   // doesn't dominate anything in the block. If it's a PHI, it dominates
   // everything in the block.
if (VerifyDomInfo)
     assert(DT.verify(DominatorTree::VerificationLevel::Full));
   else if (ExpensiveChecksEnabled)
     assert(DT.verify(DominatorTree::VerificationLevel::Basic));
 }
 
 void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
   DT.print(OS);
 }
-

llvm/test/CodeGen/X86/callbr-codegenprepare.ll

+;; RUN: opt -S -codegenprepare < %s | FileCheck %s
+
+;; Ensure that codegenprepare (via InstSimplify) doesn't eliminate the
+;; phi here (which would cause a module verification error).
+
+;; CHECK: phi
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @foo(i32)
+
+define dso_local i32 @futex_lock_pi_atomic() local_unnamed_addr {
+entry:
+  %0 = callbr i32 asm "", "=r,X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@futex_lock_pi_atomic, %b.exit))
+          to label %asm.fallthrough.i [label %b.exit]
+
+asm.fallthrough.i:
+  br label %b.exit
+
+b.exit:
+  %g.0 = phi i32 [ %0, %asm.fallthrough.i ], [ undef, %entry ]
+  tail call void @foo(i32 %g.0)
+  ret i32 undef
+}
+

llvm/test/Verifier/dominates.ll

 next:
   %y = phi i32 [ 0, %entry ]
   %x = phi i32 [ %y, %entry ]
   ret void
 ; CHECK: Instruction does not dominate all uses!
 ; CHECK-NEXT:  %y = phi i32 [ 0, %entry ]
 ; CHECK-NEXT:  %x = phi i32 [ %y, %entry ]
 }
+
+define i32 @f6(i32 %x) {
+bb0:
+  %y1 = callbr i32 asm "", "=r"() to label %bb1 [label %bb2]
+bb1:
+  ret i32 0
+bb2:
+  ret i32 %y1
+; CHECK: Instruction does not dominate all uses!
+; CHECK-NEXT:  %y1 = callbr i32 asm "", "=r"()
+; CHECK-NEXT:        to label %bb1 [label %bb2]
+; CHECK-NEXT:  ret i32 %y1
+}