[SCCP] Don't mark edges feasible when resolving undefs

[nikic]

Summary

As branch on undef is immediate undefined behavior, there is no need to mark one of the edges as feasible. We can leave all the edges non-feasible. In IPSCCP, we can replace the branch with an unreachable terminator.

Unfortunately, while this does make undef resolution much simpler, we do still need the other part of it (which marks instructions as overdefined). I think what we currently do there is somewhat non-optimal, but having some kind of undef resolution phase is probably not avoidable.

[nikic]

Rebase over https://github.com/llvm/llvm-project/commit/38ad963cc9998c5b60bde8253670237eebc8ca74. This patch exposed UB in the LEB128 test.

[nikic]

Ping

[fhahn]

LGTM, this should be fine now that branch-on-undef/poison is considered UB in most places including ValueTracking. It might be good to wait a few days with committing in case Eli has additional thoughts.

llvm/test/Transforms/FunctionSpecialization/bug52821-use-after-free.ll

37

not sure if it would be better to use i1 argument instead here and llvm/test/Transforms/FunctionSpecialization/bug55000-read-uninitialized-value.ll

llvm/test/Transforms/SCCP/indirectbr.ll

77

needs updating

llvm/test/Transforms/SCCP/return-zapped.ll

3–4

needs updating

[nikic]

Update some test comments.

[nikic]

llvm/test/Transforms/FunctionSpecialization/bug52821-use-after-free.ll

37

I've picked the i1 false in these tests to retain the same behavior that that resolveUndefs would end up picking, so that the test expectation remains the same.

[efriedma]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1450

I don't think the example given in the comment is accurate. The lattice distinguishes between unknown and undef, so PHI nodes should propagate correctly.

The problem is other operations: for example, visitCastInst doesn't propagate undef values. (This is an optimization: if the operand of a cast transitions from undef to a non-undef constant, we don't want to force the result of the cast to overdefined. We might want to consider revisiting this once we're using poison more consistently.)

[nikic]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1450

Yes, allowing the lattice value transition from undef -> constant is the point. We do make use of that for phi nodes as well, because we merge undef and C into C, not overdefined.

[efriedma]

llvm/lib/Transforms/Utils/SCCPSolver.cpp

1450

The undef->constant transition, by itself, doesn't imply we need resolvedUndefsIn, I think. The way the transition is defined, a "constant" just means "a specific value, or an undef we can force to that value". Given the way SCCPInstVisitor::visitPHINode works, that actually just works.

The issues come up when you try to mix in other operations; SCCPInstVisitor visitors for arithmetic/casts/etc. with an undef input produce unknown, which is different from what you'd otherwise expect for ValueLattice solving.

[nikic]

Improve comment on resolvedUndefsIn().

[fhahn]

It looks like this regressed DCE in some cases when using the default optimization pipeline. The reproducer for opt -sccp -jump-threading is:

https://llvm.godbolt.org/z/TbGYvo7x8

declare void @foo()
declare void @bar()

define void @test(i1 %c) {
entry:
  br i1 %c, label %unreachable, label %next

next:
  br i1 undef, label %exit, label %unreachable

exit:
  call void @foo()
  ret void

unreachable:
  call void @bar()
  unreachable
}

[nikic]

Ideally, we would remove dead blocks during normal SCCP as well, not just IPSCCP, which should avoid this issue. I'll check whether that has any negative compile-time impact.

Alternatively (or preferably: additionally) we can adjust more passes to make use of branch on undef UB. JumpThreading is one of those (I believe it currently tries to pick one of the successors based on some heuristics).

[nikic]

I've put up D128796 for the CFG simplification in scalar SCCP.

llvm/lib/Transforms/Scalar/SCCP.cpp

if (!HasNonFeasibleEdges)
     return false;
 
   // SCCP can only determine non-feasible edges for br, switch and indirectbr.
   Instruction *TI = BB->getTerminator();
   assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
           isa<IndirectBrInst>(TI)) &&
          "Terminator must be a br, switch or indirectbr");
 
-  if (FeasibleSuccessors.size() == 1) {
+  if (FeasibleSuccessors.size() == 0) {
+    // Branch on undef/poison, replace with unreachable.
+    SmallPtrSet<BasicBlock *, 8> SeenSuccs;
+    SmallVector<DominatorTree::UpdateType, 8> Updates;
+    for (BasicBlock *Succ : successors(BB)) {
+      Succ->removePredecessor(BB);
+      if (SeenSuccs.insert(Succ).second)
+        Updates.push_back({DominatorTree::Delete, BB, Succ});
+    }
+    TI->eraseFromParent();
+    new UnreachableInst(BB->getContext(), BB);
+    DTU.applyUpdatesPermissive(Updates);
+  } else if (FeasibleSuccessors.size() == 1) {
     // Replace with an unconditional branch to the only feasible successor.
     BasicBlock *OnlyFeasibleSuccessor = *FeasibleSuccessors.begin();
     SmallVector<DominatorTree::UpdateType, 8> Updates;
     bool HaveSeenOnlyFeasibleSuccessor = false;
     for (BasicBlock *Succ : successors(BB)) {
       if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
         // Don't remove the edge to the only feasible successor the first time
         // we see it. We still do need to remove any multi-edges to it though.

llvm/lib/Transforms/Utils/SCCPSolver.cpp

while (!BBWorkList.empty()) {
 
       // Notify all instructions in this basic block that they are newly
       // executable.
       visit(BB);
     }
   }
 }
 
-/// resolvedUndefsIn - While solving the dataflow for a function, we assume
-/// that branches on undef values cannot reach any of their successors.
-/// However, this is not a safe assumption.  After we solve dataflow, this
-/// method should be use to handle this.  If this returns true, the solver
-/// should be rerun.
+/// While solving the dataflow for a function, we don't compute a result for
+/// operations with an undef operand, to allow undef to be lowered to a
+/// constant later. For example, constant folding of "zext i8 undef to i16"
+/// would result in "i16 0", and if undef is later lowered to "i8 1", then the
+/// zext result would become "i16 1" and would result into an overdefined
+/// lattice value once merged with the previous result. Not computing the
+/// result of the zext (treating undef the same as unknown) allows us to handle
+/// a later undef->constant lowering more optimally.
 ///
-/// This method handles this by finding an unresolved branch and marking it one
-/// of the edges from the block as being feasible, even though the condition
-/// doesn't say it would otherwise be.  This allows SCCP to find the rest of the
-/// CFG and only slightly pessimizes the analysis results (by marking one,
-/// potentially infeasible, edge feasible).  This cannot usefully modify the
-/// constraints on the condition of the branch, as that would impact other users
-/// of the value.
-///
-/// This scan also checks for values that use undefs. It conservatively marks
-/// them as overdefined.
+/// However, if the operand remains undef when the solver returns, we do need
+/// to assign some result to the instruction (otherwise we would treat it as
+/// unreachable). For simplicity, we mark any instructions that are still
+/// unknown/undef as overdefined.
 bool SCCPInstVisitor::resolvedUndefsIn(Function &F) {
   bool MadeChange = false;
   for (BasicBlock &BB : F) {
     if (!BBExecutable.count(&BB))
       continue;
 
     for (Instruction &I : BB) {
       // Look for instructions which produce undef values.
for (Instruction &I : BB) {
         // a load from an unknown pointer.  Either way, having it return undef
         // is okay.
         continue;
       }
 
       markOverdefined(&I);
       MadeChange = true;
     }
-
-    // Check to see if we have a branch or switch on an undefined value.  If so
-    // we force the branch to go one way or the other to make the successor
-    // values live.  It doesn't really matter which way we force it.
-    Instruction *TI = BB.getTerminator();
-    if (auto *BI = dyn_cast<BranchInst>(TI)) {
-      if (!BI->isConditional())
-        continue;
-      if (!getValueState(BI->getCondition()).isUnknownOrUndef())
-        continue;
-
-      // If the input to SCCP is actually branch on undef, fix the undef to
-      // false.
-      if (isa<UndefValue>(BI->getCondition())) {
-        BI->setCondition(ConstantInt::getFalse(BI->getContext()));
-        markEdgeExecutable(&BB, TI->getSuccessor(1));
-        MadeChange = true;
-        continue;
-      }
-
-      // Otherwise, it is a branch on a symbolic value which is currently
-      // considered to be undef.  Make sure some edge is executable, so a
-      // branch on "undef" always flows somewhere.
-      // FIXME: Distinguish between dead code and an LLVM "undef" value.
-      BasicBlock *DefaultSuccessor = TI->getSuccessor(1);
-      if (markEdgeExecutable(&BB, DefaultSuccessor))
-        MadeChange = true;
-
-      continue;
-    }
-
-    if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
-      // Indirect branch with no successor ?. Its ok to assume it branches
-      // to no target.
-      if (IBR->getNumSuccessors() < 1)
-        continue;
-
-      if (!getValueState(IBR->getAddress()).isUnknownOrUndef())
-        continue;
-
-      // If the input to SCCP is actually branch on undef, fix the undef to
-      // the first successor of the indirect branch.
-      if (isa<UndefValue>(IBR->getAddress())) {
-        IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
-        markEdgeExecutable(&BB, IBR->getSuccessor(0));
-        MadeChange = true;
-        continue;
-      }
-
-      // Otherwise, it is a branch on a symbolic value which is currently
-      // considered to be undef.  Make sure some edge is executable, so a
-      // branch on "undef" always flows somewhere.
-      // FIXME: IndirectBr on "undef" doesn't actually need to go anywhere:
-      // we can assume the branch has undefined behavior instead.
-      BasicBlock *DefaultSuccessor = IBR->getSuccessor(0);
-      if (markEdgeExecutable(&BB, DefaultSuccessor))
-        MadeChange = true;
-
-      continue;
-    }
-
-    if (auto *SI = dyn_cast<SwitchInst>(TI)) {
-      if (!SI->getNumCases() ||
-          !getValueState(SI->getCondition()).isUnknownOrUndef())
-        continue;
-
-      // If the input to SCCP is actually switch on undef, fix the undef to
-      // the first constant.
-      if (isa<UndefValue>(SI->getCondition())) {
-        SI->setCondition(SI->case_begin()->getCaseValue());
-        markEdgeExecutable(&BB, SI->case_begin()->getCaseSuccessor());
-        MadeChange = true;
-        continue;
-      }
-
-      // Otherwise, it is a branch on a symbolic value which is currently
-      // considered to be undef.  Make sure some edge is executable, so a
-      // branch on "undef" always flows somewhere.
-      // FIXME: Distinguish between dead code and an LLVM "undef" value.
-      BasicBlock *DefaultSuccessor = SI->case_begin()->getCaseSuccessor();
-      if (markEdgeExecutable(&BB, DefaultSuccessor))
-        MadeChange = true;
-
-      continue;
-    }
   }
 
   return MadeChange;
 }
 
 //===----------------------------------------------------------------------===//
 //
 // SCCPSolver implementations

llvm/test/Transforms/FunctionSpecialization/bug52821-use-after-free.ll

for.cond:                                     ; preds = %for.body, %entry
   br i1 %cond, label %for.cond2, label %for.body
 
 for.body:                                     ; preds = %for.cond
   call void @callee(%mystruct* nonnull %phi)
   br label %for.cond
 
 for.cond2:                                     ; preds = %for.body2, %for.cond
   %phi2 = phi %mystruct* [ undef, %for.body2 ], [ null, %for.cond ]
-  br i1 undef, label %for.end, label %for.body2
+  br i1 false, label %for.end, label %for.body2
 
 for.body2:                                     ; preds = %for.cond2
   %arrayidx = getelementptr inbounds %mystruct, %mystruct* %phi2, i64 0, i32 1, i64 3
   br label %for.cond2
 
 for.end:                                      ; preds = %for.cond2
   ret %mystruct* %arg
 }

llvm/test/Transforms/FunctionSpecialization/bug55000-read-uninitialized-value.ll

 ; RUN: opt -function-specialization -func-specialization-max-iters=2 -func-specialization-size-threshold=20 -func-specialization-avg-iters-cost=20 -function-specialization-for-literal-constant=true -S < %s | FileCheck %s
 
 declare hidden i1 @compare(ptr) align 2
 declare hidden { i8, ptr } @getType(ptr) align 2
 
 ; CHECK-LABEL: @foo
 ; CHECK-LABEL: @foo.1
 ; CHECK-LABEL: @foo.2
 
 define internal void @foo(ptr %TLI, ptr %DL, ptr %Ty, ptr %ValueVTs, ptr %Offsets, i64 %StartingOffset) {
 entry:
   %VT = alloca i64, align 8
-  br i1 undef, label %if.then, label %if.end4
+  br i1 false, label %if.then, label %if.end4
 
 if.then:                                          ; preds = %entry
   ret void
 
 if.end4:                                          ; preds = %entry
   %cmp = call zeroext i1 @compare(ptr undef)
   br i1 %cmp, label %for.body, label %for.cond16
 

llvm/test/Transforms/SCCP/2004-12-10-UndefBranchBug.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=sccp -S | FileCheck %s
 
-; This function definitely returns 1, even if we don't know the direction
-; of the branch.
+; Branch on undef is UB, so the T block is never executed, and we can return
+; undef (IPSCCP would replace the block with unreachable).
 
 define i32 @foo() {
 ; CHECK-LABEL: @foo(
-; CHECK-NEXT:    br i1 false, label [[T:%.*]], label [[T]]
+; CHECK-NEXT:    br i1 undef, label [[T:%.*]], label [[T]]
 ; CHECK:       T:
-; CHECK-NEXT:    [[X:%.*]] = add i32 0, 1
-; CHECK-NEXT:    ret i32 [[X]]
+; CHECK-NEXT:    ret i32 undef
 ;
   br i1 undef, label %T, label %T
 T:
   %X = add i32 0, 1
   ret i32 %X
 }
 

llvm/test/Transforms/SCCP/2008-01-27-UndefCorrelate.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=sccp -S | FileCheck %s
 ; PR1938
 
 define i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb:
-; CHECK-NEXT:    [[INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[K:%.*]], [[BB_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[K]] = add i32 [[INDVAR]], 1
-; CHECK-NEXT:    br i1 false, label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]]
+; CHECK-NEXT:    br i1 undef, label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]]
 ; CHECK:       cond_true:
-; CHECK-NEXT:    br i1 undef, label [[BB_BACKEDGE]], label [[BB12:%.*]]
+; CHECK-NEXT:    br i1 undef, label [[BB_BACKEDGE:%.*]], label [[BB12:%.*]]
 ; CHECK:       bb.backedge:
 ; CHECK-NEXT:    br label [[BB]]
 ; CHECK:       cond_false:
-; CHECK-NEXT:    [[TMP9:%.*]] = icmp slt i32 [[K]], 10
-; CHECK-NEXT:    br i1 [[TMP9]], label [[BB_BACKEDGE]], label [[BB12]]
+; CHECK-NEXT:    br i1 undef, label [[BB_BACKEDGE]], label [[BB12]]
 ; CHECK:       bb12:
-; CHECK-NEXT:    [[TMP14:%.*]] = icmp eq i32 [[K]], 10
-; CHECK-NEXT:    br i1 [[TMP14]], label [[COND_NEXT18:%.*]], label [[COND_TRUE17:%.*]]
+; CHECK-NEXT:    br i1 undef, label [[COND_NEXT18:%.*]], label [[COND_TRUE17:%.*]]
 ; CHECK:       cond_true17:
-; CHECK-NEXT:    tail call void @abort()
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cond_next18:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   br label %bb
 
 bb:

llvm/test/Transforms/SCCP/PR26044.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
 ; RUN: opt < %s -S -passes=ipsccp | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @fn2(i32* %P) {
 ; CHECK-LABEL: define {{[^@]+}}@fn2
-; CHECK-SAME: (i32* [[P:%.*]])
+; CHECK-SAME: (i32* [[P:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       for.cond1:
-; CHECK-NEXT:    br i1 false, label [[IF_END]], label [[IF_END]]
+; CHECK-NEXT:    unreachable
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[CALL:%.*]] = call i32 @fn1(i32 undef)
-; CHECK-NEXT:    store i32 [[CALL]], i32* [[P]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* undef, align 4
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @fn1(i32 [[TMP0]])
+; CHECK-NEXT:    store i32 [[CALL]], i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
 ;
 entry:
   br label %if.end
 
 for.cond1:                                        ; preds = %if.end, %for.end
   br i1 undef, label %if.end, label %if.end
 
 if.end:                                           ; preds = %lbl, %for.cond1
   %e.2 = phi i32* [ undef, %entry ], [ null, %for.cond1 ], [ null, %for.cond1 ]
   %0 = load i32, i32* %e.2, align 4
   %call = call i32 @fn1(i32 %0)
   store i32 %call, i32* %P
   br label %for.cond1
 }
 
 define internal i32 @fn1(i32 %p1) {
 ; CHECK-LABEL: define {{[^@]+}}@fn1
-; CHECK-SAME: (i32 [[P1:%.*]])
+; CHECK-SAME: (i32 [[P1:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 undef, 0
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 undef, i32 undef
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[P1]], 0
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 [[P1]], i32 [[P1]]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;
 entry:
   %tobool = icmp ne i32 %p1, 0
   %cond = select i1 %tobool, i32 %p1, i32 %p1
   ret i32 %cond
 }
 
 define void @fn_no_null_opt(i32* %P) #0 {
 ; CHECK-LABEL: define {{[^@]+}}@fn_no_null_opt
-; CHECK-SAME: (i32* [[P:%.*]])
+; CHECK-SAME: (i32* [[P:%.*]]) #[[ATTR0:[0-9]+]] {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       for.cond1:
-; CHECK-NEXT:    br i1 false, label [[IF_END]], label [[IF_END]]
+; CHECK-NEXT:    unreachable
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* null, align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* undef, align 4
 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 @fn0(i32 [[TMP0]])
-; CHECK-NEXT:    store i32 [[CALL]], i32* [[P]]
+; CHECK-NEXT:    store i32 [[CALL]], i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
 ;
 entry:
   br label %if.end
 
 for.cond1:                                        ; preds = %if.end, %for.end
   br i1 undef, label %if.end, label %if.end
 
 if.end:                                           ; preds = %lbl, %for.cond1
   %e.2 = phi i32* [ undef, %entry ], [ null, %for.cond1 ], [ null, %for.cond1 ]
   %0 = load i32, i32* %e.2, align 4
   %call = call i32 @fn0(i32 %0)
   store i32 %call, i32* %P
   br label %for.cond1
 }
 
 define internal i32 @fn0(i32 %p1) {
 ; CHECK-LABEL: define {{[^@]+}}@fn0
-; CHECK-SAME: (i32 [[P1:%.*]])
+; CHECK-SAME: (i32 [[P1:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[P1]], 0
 ; CHECK-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 [[P1]], i32 [[P1]]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;
 entry:
   %tobool = icmp ne i32 %p1, 0
   %cond = select i1 %tobool, i32 %p1, i32 %p1
   ret i32 %cond
 }
 
 attributes #0 = { null_pointer_is_valid }

llvm/test/Transforms/SCCP/indirectbr.ll

 BB0:
   call void @BB0_f()
   br label %BB1
 BB1:
   call void @BB1_f()
   ret void
 }
 
-; Make sure we eliminate BB1 as we pick the first successor on undef.
+; Branch on undef is UB, so we can convert the indirectbr to unreachable.
 
 define void @indbrtest4(i8** %Q) {
 ; CHECK-LABEL: @indbrtest4(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[BB0:%.*]]
-; CHECK:       BB0:
-; CHECK-NEXT:    call void @BB0_f()
-; CHECK-NEXT:    ret void
+; CHECK-NEXT:    unreachable
 ;
 entry:
   indirectbr i8* undef, [label %BB0, label %BB1]
 BB0:
   call void @BB0_f()
   ret void
 BB1:
   call void @BB1_f()

llvm/test/Transforms/SCCP/ipsccp-branch-unresolved-undef.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
 ; RUN: opt < %s -S -passes=ipsccp | FileCheck %s
 
 define void @main() {
 ; CHECK-LABEL: define {{[^@]+}}@main() {
 ; CHECK-NEXT:    [[CALL:%.*]] = call i1 @patatino(i1 undef)
 ; CHECK-NEXT:    ret void
 ;
   %call = call i1 @patatino(i1 undef)
   ret void
 }
 
 define internal i1 @patatino(i1 %a) {
 ; CHECK-LABEL: define {{[^@]+}}@patatino
 ; CHECK-SAME: (i1 [[A:%.*]]) {
-; CHECK-NEXT:    br label [[ONFALSE:%.*]]
-; CHECK:       onfalse:
-; CHECK-NEXT:    ret i1 undef
+; CHECK-NEXT:    unreachable
 ;
   br i1 %a, label %ontrue, label %onfalse
 ontrue:
   ret i1 false
 onfalse:
   ret i1 false
 }

llvm/test/Transforms/SCCP/return-zapped.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
 ; RUN: opt < %s -S -passes=ipsccp | FileCheck %s
 
-; After the first round of Solver.Solve(), the return value of @testf still
-; undefined as we hit a branch on undef. Therefore the conditional branch on
-; @testf's return value in @bar is unknown. In ResolvedUndefsIn, we force the
-; false branch to be feasible. We later discover that @testf actually
-; returns true, so we end up with an unfolded "br i1 true".
+; testf() performs an unconditional branch on undef, as such the testf() return
+; value used in test1() will remain "unknown" and the following branch on it
+; replaced by unreachable. This is fine, as the call to testf() will already
+; trigger undefined behavior.
 define void @test1() {
 ; CHECK-LABEL: define {{[^@]+}}@test1() {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[IF_THEN:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    [[FOO:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[NEXT:%.*]], [[IF_THEN]] ]
-; CHECK-NEXT:    [[NEXT]] = add i32 [[FOO]], 1
 ; CHECK-NEXT:    [[CALL:%.*]] = call i1 @testf()
-; CHECK-NEXT:    br i1 true, label [[IF_END:%.*]], label [[IF_THEN]]
-; CHECK:       if.end:
-; CHECK-NEXT:    ret void
+; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %if.then
 if.then:                                          ; preds = %entry, %if.then
   %foo = phi i32 [ 0, %entry], [ %next, %if.then]
   %next = add i32 %foo, 1
   %call = call i1 @testf()
   br i1 %call, label %if.end, label %if.then
 
 if.end:                                           ; preds = %if.then, %entry
   ret void
 }
 
 define internal i1 @testf() {
 ; CHECK-LABEL: define {{[^@]+}}@testf() {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[IF_END3:%.*]]
-; CHECK:       if.end3:
-; CHECK-NEXT:    ret i1 undef
+; CHECK-NEXT:    unreachable
 ;
 entry:
   br i1 undef, label %if.then1, label %if.end3
 
 if.then1:                                         ; preds = %if.end
   br label %if.end3
 
 if.end3:                                          ; preds = %if.then1, %entry
   ret i1 true
 }
 
 ; Call sites in unreachable blocks should not be a problem.
 define i1 @test2() {
 ; CHECK-LABEL: define {{[^@]+}}@test2() {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[CALL2:%.*]] = call i1 @testf()
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 undef
 ;
 entry:
   br label %if.end
 
 if.then:                                          ; preds = %entry, %if.then
   %call = call i1 @testf()
   br i1 %call, label %if.end, label %if.then
 
 if.end:                                           ; preds = %if.then, %entry
   %call2 = call i1 @testf()
   ret i1 %call2
 }

llvm/test/Transforms/SCCP/switch-constantfold-crash.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
-; RUN: opt -passes=ipsccp < %s -S | FileCheck --check-prefixes=CHECK,ONCE %s
-; RUN: opt -passes='ipsccp,ipsccp' < %s -S | FileCheck --check-prefixes=CHECK,TWICE %s
+; RUN: opt -passes=ipsccp < %s -S | FileCheck %s
+; RUN: opt -passes='ipsccp,ipsccp' < %s -S | FileCheck %s
 
 define void @barney() {
 ; CHECK-LABEL: define {{[^@]+}}@barney() {
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB9:%.*]]
 ; CHECK:       bb6:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb9:

 bb38:                                             ; preds = %bb16
   unreachable
 }
 
 
 define void @hoge() {
 ; CHECK-LABEL: define {{[^@]+}}@hoge() {
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    br label [[BB2:%.*]]
-; CHECK:       bb2:
-; CHECK-NEXT:    br label [[BB3:%.*]]
-; CHECK:       bb3:
 ; CHECK-NEXT:    unreachable
 ;
 bb:
   switch i16 undef, label %bb1 [
   i16 135, label %bb2
   i16 66, label %bb2
   ]
 

 
 bb4:                                              ; preds = %bb2, %bb2, %bb2
   unreachable
 }
 
 ; Test case from PR49573. %default.bb is unfeasible. Make sure it gets replaced
 ; by an unreachable block.
 define void @pr49573_main() {
-; ONCE-LABEL: define {{[^@]+}}@pr49573_main() {
-; ONCE-NEXT:  entry:
-; ONCE-NEXT:    [[TGT:%.*]] = call i16 @pr49573_fn()
-; ONCE-NEXT:    switch i16 2, label [[DEFAULT_UNREACHABLE:%.*]] [
-; ONCE-NEXT:    i16 0, label [[CASE_0:%.*]]
-; ONCE-NEXT:    i16 2, label [[CASE_2:%.*]]
-; ONCE-NEXT:    ]
-; ONCE:       case.0:
-; ONCE-NEXT:    unreachable
-; ONCE:       default.unreachable:
-; ONCE-NEXT:    unreachable
-; ONCE:       case.2:
-; ONCE-NEXT:    br label [[NEXT:%.*]]
-; ONCE:       next:
-; ONCE-NEXT:    [[TGT_2:%.*]] = call i16 @pr49573_fn_2()
-; ONCE-NEXT:    switch i16 2, label [[DEFAULT_UNREACHABLE]] [
-; ONCE-NEXT:    i16 0, label [[CASE_0]]
-; ONCE-NEXT:    i16 2, label [[CASE_2]]
-; ONCE-NEXT:    ]
-;
-; TWICE-LABEL: define {{[^@]+}}@pr49573_main() {
-; TWICE-NEXT:  entry:
-; TWICE-NEXT:    [[TGT:%.*]] = call i16 @pr49573_fn()
-; TWICE-NEXT:    br label [[CASE_2:%.*]]
-; TWICE:       case.2:
-; TWICE-NEXT:    br label [[NEXT:%.*]]
-; TWICE:       next:
-; TWICE-NEXT:    [[TGT_2:%.*]] = call i16 @pr49573_fn_2()
-; TWICE-NEXT:    br label [[CASE_2]]
+; CHECK-LABEL: define {{[^@]+}}@pr49573_main() {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TGT:%.*]] = call i16 @pr49573_fn()
+; CHECK-NEXT:    unreachable
 ;
 entry:
   %tgt = call i16 @pr49573_fn()
   switch i16 %tgt, label %default.bb [
   i16 0, label %case.0
   i16 1, label %case.1
   i16 2, label %case.2
   ]
next:
   switch i16 %tgt.2, label %default.bb [
   i16 0, label %case.0
   i16 2, label %case.2
   ]
 }
 
 ; Make sure a new unreachable BB is created.
 define void @pr49573_main_2() {
-; ONCE-LABEL: define {{[^@]+}}@pr49573_main_2() {
-; ONCE-NEXT:  entry:
-; ONCE-NEXT:    [[TGT:%.*]] = call i16 @pr49573_fn()
-; ONCE-NEXT:    switch i16 2, label [[DEFAULT_UNREACHABLE:%.*]] [
-; ONCE-NEXT:    i16 0, label [[CASE_0:%.*]]
-; ONCE-NEXT:    i16 2, label [[CASE_2:%.*]]
-; ONCE-NEXT:    ]
-; ONCE:       case.0:
-; ONCE-NEXT:    unreachable
-; ONCE:       default.unreachable:
-; ONCE-NEXT:    unreachable
-; ONCE:       case.2:
-; ONCE-NEXT:    ret void
-;
-; TWICE-LABEL: define {{[^@]+}}@pr49573_main_2() {
-; TWICE-NEXT:  entry:
-; TWICE-NEXT:    [[TGT:%.*]] = call i16 @pr49573_fn()
-; TWICE-NEXT:    br label [[CASE_2:%.*]]
-; TWICE:       case.2:
-; TWICE-NEXT:    ret void
+; CHECK-LABEL: define {{[^@]+}}@pr49573_main_2() {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TGT:%.*]] = call i16 @pr49573_fn()
+; CHECK-NEXT:    unreachable
 ;
 entry:
   %tgt = call i16 @pr49573_fn()
   switch i16 %tgt, label %default.bb [
   i16 0, label %case.0
   i16 1, label %case.1
   i16 2, label %case.2
   ]

 
 case.2:
   ret void
 }
 
 define internal i16 @pr49573_fn() {
 ; CHECK-LABEL: define {{[^@]+}}@pr49573_fn() {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[ELSE:%.*]]
-; CHECK:       else:
-; CHECK-NEXT:    ret i16 undef
+; CHECK-NEXT:    unreachable
 ;
 entry:
   br i1 undef, label %then, label %else
 
 then:
   ret i16 0
 
 else:
   ret i16 2
 }
 
 define internal i16 @pr49573_fn_2() {
 ; CHECK-LABEL: define {{[^@]+}}@pr49573_fn_2() {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[ELSE:%.*]]
-; CHECK:       else:
-; CHECK-NEXT:    ret i16 undef
+; CHECK-NEXT:    unreachable
 ;
 entry:
   br i1 undef, label %then, label %else
 
 then:
   ret i16 0
 
 else:
   ret i16 2
 }

llvm/test/Transforms/SCCP/switch-undef-constantfoldterminator.ll

entry:
   %call = call i16 @f3(i16 undef)
   ret void
 }
 
 define internal i16 @f3(i16 %p1) {
 ; CHECK-LABEL: define {{[^@]+}}@f3
 ; CHECK-SAME: (i16 [[P1:%.*]]) {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[LAND_END:%.*]]
-; CHECK:       land.end:
-; CHECK-NEXT:    ret i16 undef
+; CHECK-NEXT:    unreachable
 ;
 entry:
   switch i16 %p1, label %land.end [
   i16 0, label %land.end
   i16 1, label %lor.rhs
   ]
 
 lor.rhs:
   br label %land.end
 
 land.end:
   ret i16 0
 }