[SimplifyCFG] Fold `llvm.guard(false)` to unreachable

[sanjoy]

Summary

llvm.guard(false) always bails out of the current compilation unit, so
we can prune any control flow following it.

Note: earlier I had submitted an incorrect version of this change as
D19188.

[reames]

include/llvm/Transforms/Utils/Local.h

295

Why can't you just use the API immediately above?

lib/Transforms/Utils/Local.cpp

1287

You should respect UseLLVMTrap here.

1347

Add a comment explain what this does rather than what it does not do.

[sanjoy]

• Address review

include/llvm/Transforms/Utils/Local.h

295

No specific reason; just from a readability POV I found it a little better to have a separately named utility than add a bool to an existing one. If you prefer editing changeToUnreachable instead, I can do that too (as you can tell, I won't even have to change the implementation).

In case you were asking why I cannot use the API above as is, changeToUnreachable removes I. But for guards the original instruction needs to remain, since that is how we'll get out of the compile (IOW it is more like "exit(0)" than it is like "store to null").

[reames]

include/llvm/Transforms/Utils/Local.h

295

I'm still missing something here. I get why you can't remove the *guard*, but why can't you remove the instruction *after* the guard? changeToUnreachable(std::next(BBI))?

[sanjoy]

You're right, there was never a need for a new utility. Fixed.

[majnemer]

lib/Transforms/Utils/Local.cpp

1348

An call -> A call.

1358

I think the usual style doesn't have spaces before the variable or around the equals:

changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false);

I've also seen it formatted like so:

changeToUnreachable(II->getNextNode(), /*UseLLVMTrap*/ false);

[reames]

LGTM w/remaining comments from David and my own addressed.

test/Transforms/SimplifyCFG/guards.ll

13

I believe this branch is redundant?

24

Clarify: and do not want to.

Also, add a test case for guard(true) just as a sanity check!

46

Naming wise: true, false are confusing. Possibly: dead_via_guard and merge? Applies to all tests.

include/llvm/Transforms/Utils/Local.h

 /// Remove all instructions from a basic block other than it's terminator
 /// and any present EH pad instructions.
 unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);
 
 /// Insert an unreachable instruction before the specified
 /// instruction, making it and the rest of the code in the block dead.
 unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap);
 
+/// Append an `unreachable` instruction after \p I, making everything following
+/// it in the CFG dead.  Does not delete \p I.  If \p UseLLVMTrap is true, adds
+/// a call to @llvm.trap before the newly inserted unreachable instruction.
+/// Returns the number of instructions deleted.
+unsigned appendUnreachable(Instruction *I, bool UseLLVMTrap);
+
 /// Replace 'BB's terminator with one that does not have an unwind successor
 /// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind
 /// successor.
 ///
 /// \param BB  Block whose terminator will be replaced.  Its terminator must
 ///            have an unwind successor.
 void removeUnwindEdge(BasicBlock *BB);
 

lib/Transforms/Utils/Local.cpp

while (EndInst != &BB->front()) {
     }
     if (!isa<DbgInfoIntrinsic>(Inst))
       ++NumDeadInst;
     Inst->eraseFromParent();
   }
   return NumDeadInst;
 }
 
-unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap) {
+static unsigned makeUnreachableImpl(Instruction *I, bool UseLLVMTrap,
+                                    bool KeepOriginalInst) {
   BasicBlock *BB = I->getParent();
   // Loop over all of the successors, removing BB's entry from any PHI
   // nodes.
   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
     (*SI)->removePredecessor(BB);
 
   // Insert a call to llvm.trap right before this.  This turns the undefined
   // behavior into a hard fail instead of falling through into random code.
   if (UseLLVMTrap) {
-    Function *TrapFn =
-      Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
+    Function *TrapFn = Intrinsic::getDeclaration(BB->getParent()->getParent(),
+                                                 Intrinsic::trap);
     CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
     CallTrap->setDebugLoc(I->getDebugLoc());
   }
-  new UnreachableInst(I->getContext(), I);
+
+  assert((!KeepOriginalInst || !isa<TerminatorInst>(I)) &&
+         "Can't have two terminators!");
 
   // All instructions after this are dead.
   unsigned NumInstrsRemoved = 0;
   BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
+  if (KeepOriginalInst)
+    BBI = std::next(BBI);
+
   while (BBI != BBE) {
     if (!BBI->use_empty())
       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
     BB->getInstList().erase(BBI++);
     ++NumInstrsRemoved;
   }
+
+  new UnreachableInst(I->getContext(), BB);
   return NumInstrsRemoved;
 }
 
+unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap) {
+  return makeUnreachableImpl(I, UseLLVMTrap, /* KeepOriginalInst = */ false);
+}
+
+unsigned llvm::appendUnreachable(Instruction *I, bool UseLLVMTrap) {
+  return makeUnreachableImpl(I, UseLLVMTrap,
+                             /* KeepOriginalInst = */ true);
+}
+
 /// changeToCall - Convert the specified invoke into a normal call.
 static void changeToCall(InvokeInst *II) {
   SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());
   SmallVector<OperandBundleDef, 1> OpBundles;
   II->getOperandBundlesAsDefs(OpBundles);
   CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
                                        "", II);
   NewCall->takeName(II);
do {
 
     // Do a quick scan of the basic block, turning any obviously unreachable
     // instructions into LLVM unreachable insts.  The instruction combining pass
     // canonicalizes unreachable insts into stores to null or undef.
     for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){
       // Assumptions that are known to be false are equivalent to unreachable.
       // Also, if the condition is undefined, then we make the choice most
       // beneficial to the optimizer, and choose that to also be unreachable.
-      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI))
+      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(BBI)) {
         if (II->getIntrinsicID() == Intrinsic::assume) {
           bool MakeUnreachable = false;
           if (isa<UndefValue>(II->getArgOperand(0)))
             MakeUnreachable = true;
           else if (ConstantInt *Cond =
                    dyn_cast<ConstantInt>(II->getArgOperand(0)))
             MakeUnreachable = Cond->isZero();
 
           if (MakeUnreachable) {
             // Don't insert a call to llvm.trap right before the unreachable.
             changeToUnreachable(&*BBI, false);
             Changed = true;
             break;
           }
         }
 
+        if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
+          // An call to the guard intrinsic bails out of the current compilation
+          // unit if the predicate passed to it is false.  If the predicate is a
+          // constant false, then we know the guard will bail out of the current
+          // compile unconditionally, so all code following it is dead.
+          //
+          // Note: unlike in llvm.assume, it is not "obviously profitable" for
+          // guards to treat `undef` as `false` since a guard on `undef` can
+          // still be useful for widening.
+          if (auto *CI = dyn_cast<ConstantInt>(II->getArgOperand(0)))
+            if (CI->isZero() && !isa<UnreachableInst>(II->getNextNode())) {
+              appendUnreachable(II, /* UseLLVMTrap = */ false);
+              Changed = true;
+              break;
+            }
+        }
+      }
+
       if (CallInst *CI = dyn_cast<CallInst>(BBI)) {
         if (CI->doesNotReturn()) {
           // If we found a call to a no-return function, insert an unreachable
           // instruction after it.  Make sure there isn't *already* one there
           // though.
           ++BBI;
           if (!isa<UnreachableInst>(BBI)) {
             // Don't insert a call to llvm.trap right before the unreachable.

test/Transforms/SimplifyCFG/guards.ll

+; RUN: opt -S -simplifycfg < %s | FileCheck %s
+
+declare void @llvm.experimental.guard(i1, ...)
+
+define i32 @f_0(i1 %c) {
+; CHECK-LABEL: @f_0(
+; CHECK-NEXT: entry:
+; CHECK: true:
+; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+; CHECK-NEXT:  unreachable
+entry:
+  br i1 %c, label %true, label %false
+
+true:
+  call void(i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+  ret i32 10
+
+false:
+  ret i32 20
+}
+
+define i32 @f_1(i1 %c) {
+; Demonstrate that we do not yet simplify a guard on undef
+
+; CHECK-LABEL: @f_1(
+; CHECK: ret i32 10
+; CHECK: ret i32 20
+
+entry:
+  br i1 %c, label %true, label %false
+
+true:
+  call void(i1, ...) @llvm.experimental.guard(i1 undef) [ "deopt"() ]
+  ret i32 10
+
+false:
+  ret i32 20
+}
+
+define i32 @f_2(i1 %c, i32* %buf) {
+; CHECK-LABEL: @f_2(
+entry:
+  br i1 %c, label %true, label %false
+
+true:
+  call void(i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+  %val = load i32, i32* %buf
+  br label %false
+
+false:
+  %to.return = phi i32 [ %val, %true ], [ 50, %entry ]
+  ret i32 %to.return
+; CHECK: true:
+; CHECK-NEXT:  call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+; CHECK-NEXT:  unreachable
+
+; CHECK: false:
+; CHECK-NEXT:  ret i32 50
+}
+
+define i32 @f_3(i1* %c, i32* %buf) {
+; CHECK-LABEL: @f_3(
+entry:
+  %c0 = load volatile i1, i1* %c
+  br i1 %c0, label %true, label %false
+
+true:
+  call void(i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+  %val = load i32, i32* %buf
+  %c2 = load volatile i1, i1* %c
+  br i1 %c2, label %left, label %right
+
+false:
+  %c1 = load volatile i1, i1* %c
+  br i1 %c1, label %left, label %right
+
+left:
+  %val.left = phi i32 [ %val, %true ], [ 50, %false ]
+  ret i32 %val.left
+
+right:
+  %val.right = phi i32 [ %val, %true ], [ 100, %false ]
+  ret i32 %val.right
+
+; CHECK: true:
+; CHECK-NEXT:   call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ]
+; CHECK-NEXT:  unreachable
+
+; CHECK: false:
+; CHECK-NEXT:  %c1 = load volatile i1, i1* %c
+; CHECK-NEXT:  [[VAL:%[^ ]]] = select i1 %c1, i32 50, i32 100
+; CHECK-NEXT:  ret i32 [[VAL]]
+}