[SCCP] Directly remove non-feasible edges

[nikic]

Summary

Non-feasible control-flow edges are currently removed by replacing the branch condition with a constant and then calling ConstantFoldTerminator. This happens in a rather roundabout manner, by inspecting the users (effectively: predecessors) of unreachable blocks, and further complicated by the need to explicitly materialize the condition for "forced" edges. I would like to extend SCCP to discard switch conditions that are non-feasible based on range information, but this is incompatible with the current approach (as there is no single constant we could use.)

Instead, this patch explicitly removes non-feasible edges. It currently only handles the case where there is a single feasible edge. The llvm_unreachable() branch will need to be implemented for the aforementioned switch improvement.

[efriedma]

llvm/lib/Transforms/Scalar/SCCP.cpp

1825

Iterating over a smallptrset is non-deterministic.

1827

I'm not sure calling removePredecessor once is enough if there are multiple edges to the same successor, for example in a switch.

1837

Even if only one basic block is a possible successor, there could still be multiple edges, for example in a switch. (This matters because you might need to update PHI nodes.)

ConstantFoldTerminator does some stuff with profile metadata; do we need something similar here?

1840

Is it possible that no successor is feasible?

[fhahn]

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

8

These checks seem odd. We care basically just creating a FileCheck variable, but never match the variable elsewhere, right? So we aren't actually checking if we branch to bb9 here, unless I am missing something.

[nikic]

llvm/lib/Transforms/Scalar/SCCP.cpp

1827

I think you are right. removePredecessor() is basically removeIncomingValue() on all phi nodes, and that function only removes a single incoming value. I'll try to come up with a failing test case.

1837

The profile metadata adjustment is only done when merging cases into the default destination. We don't need to adjust metadata if we convert into an unconditional branch.

1840

This shouldn't be possible right now, as we always force one successor to be feasible, even if it was undef/unknown. It might be possible in the future if we want to make use of branch-on-undef being UB and all successors being non-feasible.

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

8

Yes, this is a weakness of update_test_checks generated check lines. Do you want me to manually undo these?

[nikic]

Fix handling of multi-edges. The corresponding test case has been added in https://github.com/llvm/llvm-project/commit/eae6bb3807977a2998ac9114a1d6ecb6bdafc3cd.

[nikic]

llvm/lib/Transforms/Scalar/SCCP.cpp

1825

The updated version no longer iterates over SmallPtrSet :)

1827

This is now fixed. Previously the test case from https://github.com/llvm/llvm-project/commit/eae6bb3807977a2998ac9114a1d6ecb6bdafc3cd crashed.

llvm/test/Transforms/SCCP/switch.ll

21

This test change shows another weakness of the previous approach: Even though we already determined that here only the default edge is feasible, we did not make use of this fact, because the target block is still reachable through a different edge. Because ConstantFoldTerminator was called for the predecessors of unreachable blocks, this case was missed.

[efriedma]

llvm/lib/Transforms/Scalar/SCCP.cpp

1831

Can we skip creating the unconditional branch if the terminator is already an unconditional branch?

Is it possible for this code to see other branches which inherently only have one successor, e.g. catchret?

1837

Even if only one basic block is a possible successor, there could still be multiple edges, for example in a switch. (This matters because you might need to update PHI nodes.)

Any response to this?

[nikic]

Fix multi-edge handling more thoroughly.

[nikic]

llvm/lib/Transforms/Scalar/SCCP.cpp

1831

Any of this code is only executed if there is at least one non-feasible successor, i.e. only cases for which SCCP supports feasible edge analysis (that is more precise than "all successors"). Those are conditional branches, switches and indirectbr, thus the types in the assert.

1837

Sorry, I misunderstood what you meant here and thought this was resolved by the previous change. I've now added two additional test cases in https://github.com/llvm/llvm-project/commit/e20b3079c14d8e68ebc90125eb95156f2e1ee9e4 and fixed this to remove all but one of the edges.

[efriedma]

LGTM

[MaskRay]

Reverted this revision and its follow-up 5db5b4bc4394ca247c9eb665e03b851848aa2fbf in 4637daa9905cbe12adba85fc88ea95a3be7db85d

This broke a stage-2 build

[nikic]

@MaskRay How would I go about reproducing this issue? This is the first time I'm trying a stage2 build. I've used this cmake configuration

cmake -G Ninja ../llvm \
  -DCLANG_ENABLE_BOOTSTRAP=On \
  -DCMAKE_BUILD_TYPE=Release \
  -DLLVM_TARGETS_TO_BUILD="X86;Hexagon" \
  -DLLVM_ENABLE_PROJECTS="clang;compiler-rt" \
  -DLLVM_APPEND_VC_REV=false \
  -DCLANG_ENABLE_ARCMT=false \
  -DCLANG_ENABLE_STATIC_ANALYZER=false

and then ran ninja stage2. However, I did not get an error this way.

[fhahn]

In D84264#2172687, @nikic wrote:

@MaskRay How would I go about reproducing this issue? This is the first time I'm trying a stage2 build. I've used this cmake configuration

cmake -G Ninja ../llvm \
  -DCLANG_ENABLE_BOOTSTRAP=On \
  -DCMAKE_BUILD_TYPE=Release \
  -DLLVM_TARGETS_TO_BUILD="X86;Hexagon" \
  -DLLVM_ENABLE_PROJECTS="clang;compiler-rt" \
  -DLLVM_APPEND_VC_REV=false \
  -DCLANG_ENABLE_ARCMT=false \
  -DCLANG_ENABLE_STATIC_ANALYZER=false

and then ran ninja stage2. However, I did not get an error this way.

I usually set up things myself, by treating it as a regular build, just with additionally setting -DCMAKE_C_COMPILER= and -DCMAKE_CXX_COMPILER= to the local build I want to use to build stage2. Before building stage2, you just have to make sure the stage1 compiler build is up-to-date with the changes you want.

@MaskRay I guess some additional options need to be set for the build? It would be great if you could provide additional details, ideally with the full traceback as well.

[nikic]

I usually set up things myself, by treating it as a regular build, just with additionally setting -DCMAKE_C_COMPILER= and -DCMAKE_CXX_COMPILER= to the local build I want to use to build stage2. Before building stage2, you just have to make sure the stage1 compiler build is up-to-date with the changes you want.

Thanks, that is indeed much simpler to work with.

After some tinkering with different configs, I now managed to reproduce this by compiling with -fexperimental-new-pass-manager.

clang++: /home/nikic/llvm-project/llvm/include/llvm/Support/GenericDomTree.h:641: void llvm::DominatorTreeBase<NodeT, IsPostDom>::eraseNode(NodeT*) [with NodeT = llvm::BasicBlock; bool IsPostDom = false]: Assertion `Node->isLeaf() && "Node is not a leaf node."' failed.
...
 #9 0x000055e32f884bab llvm::DomTreeUpdater::eraseDelBBNode(llvm::BasicBlock*) (/home/nikic/llvm-project/build/bin/clang+++0x528bbab)
#10 0x000055e32f884d15 llvm::DomTreeUpdater::forceFlushDeletedBB() (/home/nikic/llvm-project/build/bin/clang+++0x528bd15)
#11 0x000055e32f885ebc llvm::DomTreeUpdater::dropOutOfDateUpdates() (/home/nikic/llvm-project/build/bin/clang+++0x528cebc)
#12 0x000055e32d566aa1 llvm::runIPSCCP(llvm::Module&, llvm::DataLayout const&, std::function<llvm::TargetLibraryInfo const& (llvm::Function&)>, llvm::function_ref<llvm::AnalysisResultsForFn (llvm::Function&)>) (/home/nikic/llvm-project/build/bin/clang+++0x2f6daa1)
#13 0x000055e32d0ad35c llvm::IPSCCPPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nikic/llvm-project/build/bin/clang+++0x2ab435c)

[nikic]

• How do I get the pre-ipsccp IR under NewPM -- without getting a full print-after-all dump? There is no opt-bisect and I didn't find anything else. Is inserting manual M.dump() calls really the state of the art here?
• How do I reduce test cases under NewPM? After wrangling with it for a while, I finally understood that bugpoint just doesn't understand NewPM at all. So I tried llvm-reduce. After learning how to make that work -- which seems way more complicated than bugpoint -- it just managed to break the module after a couple iterations :(

Per a recent mailing list thread, people have been using NewPM in production for years -- how do you debug issues under it?

For the record, this is the IR dump I managed to get: https://gist.github.com/nikic/138cbd24f0c87b847d52fa9d941a4ae4 And the reason why this only affects NewPM is that we don't preserve DT/PDT under the LegacyPM in this pass at all.

[nikic]

Okay, it looks like you can use bugpoint with NewPM after all, you just need to use it the same way as llvm-reduce, via -compile-custom -compile-command. With that and some manual cleanup, here is a reduced test case:

; opt -passes=ipsccp
define i32 @test() {
entry:
  br label %for.body

for.body:                                         ; preds = %entry
  br i1 true, label %if.then2, label %if.else

if.then2:                                         ; preds = %for.body
  br label %for.inc

if.else:                                          ; preds = %for.body
  br i1 undef, label %lor.rhs, label %if.then19.critedge

lor.rhs:                                          ; preds = %if.else
  br i1 undef, label %if.then19, label %for.inc

if.then19.critedge:                               ; preds = %if.else
  br label %if.then19

if.then19:                                        ; preds = %if.then19.critedge, %lor.rhs
  unreachable

for.inc:                                          ; preds = %lor.rhs, %if.then2
  unreachable
}

[nikic]

Apply DTU updates only after changing the CFG and add previously crashing test. This is the first point in the CAUTION list at https://github.com/llvm/llvm-project/blob/3c1476d26c769cd97a631a129b30c62232ac96b6/llvm/include/llvm/Analysis/DomTreeUpdater.h#L135-L139.

[fhahn]

In D84264#2173974, @nikic wrote:

Apply DTU updates only after changing the CFG and add previously crashing test. This is the first point in the CAUTION list at https://github.com/llvm/llvm-project/blob/3c1476d26c769cd97a631a129b30c62232ac96b6/llvm/include/llvm/Analysis/DomTreeUpdater.h#L135-L139.

That sounds right, thanks! LGTM

llvm/test/Transforms/SCCP/domtree-update.ll

2

perhaps also add verify<domtree>

Also, even though we don't actively preserve the DT with the legacy pass manager, we might as well run the test with the legacy pass manager as well. Or add a note why we only check the NewPM

[MaskRay]

Glad that you figured out the problem! We are indeed using -fexperimental-new-pass-manager. Sorry that I was not very responsive yesterday because I was/am investigating a mysterious PGO regression.

llvm/lib/Transforms/Scalar/SCCP.cpp

public:
   bool ResolvedUndefsIn(Function &F);
 
   bool isBlockExecutable(BasicBlock *BB) const {
     return BBExecutable.count(BB);
   }
 
   // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
   // block to the 'To' basic block is currently feasible.
-  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To);
+  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const;
 
   std::vector<ValueLatticeElement> getStructLatticeValueFor(Value *V) const {
     std::vector<ValueLatticeElement> StructValues;
     auto *STy = dyn_cast<StructType>(V->getType());
     assert(STy && "getStructLatticeValueFor() can be called only on structs");
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       auto I = StructValueState.find(std::make_pair(V, i));
       assert(I != StructValueState.end() && "Value not in valuemap!");
void SCCPSolver::getFeasibleSuccessors(Instruction &TI,
   }
 
   LLVM_DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
   llvm_unreachable("SCCP: Don't know how to handle this terminator!");
 }
 
 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 // block to the 'To' basic block is currently feasible.
-bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) {
+bool SCCPSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To) const {
   // Check if we've called markEdgeExecutable on the edge yet. (We could
   // be more aggressive and try to consider edges which haven't been marked
   // yet, but there isn't any need.)
   return KnownFeasibleEdges.count(Edge(From, To));
 }
 
 // visit Implementations - Something changed in this instruction, either an
 // operand made a transition, or the instruction is newly executable.  Change
for (BasicBlock &BB : F) {
     }
 
     if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
       if (!isa<UndefValue>(RI->getOperand(0)))
         ReturnsToZap.push_back(RI);
   }
 }
 
-// Update the condition for terminators that are branching on indeterminate
-// values, forcing them to use a specific edge.
-static void forceIndeterminateEdge(Instruction* I, SCCPSolver &Solver) {
-  BasicBlock *Dest = nullptr;
-  Constant *C = nullptr;
-  if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
-    if (!isa<ConstantInt>(SI->getCondition())) {
-      // Indeterminate switch; use first case value.
-      Dest = SI->case_begin()->getCaseSuccessor();
-      C = SI->case_begin()->getCaseValue();
-    }
-  } else if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
-    if (!isa<ConstantInt>(BI->getCondition())) {
-      // Indeterminate branch; use false.
-      Dest = BI->getSuccessor(1);
-      C = ConstantInt::getFalse(BI->getContext());
-    }
-  } else if (IndirectBrInst *IBR = dyn_cast<IndirectBrInst>(I)) {
-    if (!isa<BlockAddress>(IBR->getAddress()->stripPointerCasts())) {
-      // Indeterminate indirectbr; use successor 0.
-      Dest = IBR->getSuccessor(0);
-      C = BlockAddress::get(IBR->getSuccessor(0));
-    }
-  } else {
-    llvm_unreachable("Unexpected terminator instruction");
+static bool removeNonFeasibleEdges(const SCCPSolver &Solver, BasicBlock *BB,
+                                   DomTreeUpdater &DTU) {
+  SmallPtrSet<BasicBlock *, 8> FeasibleSuccessors;
+  bool HasNonFeasibleEdges = false;
+  for (BasicBlock *Succ : successors(BB)) {
+    if (Solver.isEdgeFeasible(BB, Succ))
+      FeasibleSuccessors.insert(Succ);
+    else
+      HasNonFeasibleEdges = true;
+
+  // All edges feasible, nothing to do.
+  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) {
+    // 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.
+        HaveSeenOnlyFeasibleSuccessor = true;
+        continue;
       }
-  if (C) {
-    assert(Solver.isEdgeFeasible(I->getParent(), Dest) &&
-           "Didn't find feasible edge?");
-    (void)Dest;
 
-    I->setOperand(0, C);
+      Succ->removePredecessor(BB);
+      Updates.push_back({DominatorTree::Delete, BB, Succ});
+    }
+
+    BranchInst::Create(OnlyFeasibleSuccessor, BB);
+    TI->eraseFromParent();
+    DTU.applyUpdatesPermissive(Updates);
+  } else {
+    llvm_unreachable("Either all successors are feasible, or exactly one is");
   }
+  return true;
 }
 
 bool llvm::runIPSCCP(
     Module &M, const DataLayout &DL,
     std::function<const TargetLibraryInfo &(Function &)> GetTLI,
     function_ref<AnalysisResultsForFn(Function &)> getAnalysis) {
   SCCPSolver Solver(DL, GetTLI, M.getContext());
 
for (BasicBlock *BB : BlocksToErase) {
           changeToUnreachable(BB->getFirstNonPHI(), /*UseLLVMTrap=*/false,
                               /*PreserveLCSSA=*/false, &DTU);
     }
     if (!Solver.isBlockExecutable(&F.front()))
       NumInstRemoved += changeToUnreachable(F.front().getFirstNonPHI(),
                                             /*UseLLVMTrap=*/false,
                                             /*PreserveLCSSA=*/false, &DTU);
 
-    // Now that all instructions in the function are constant folded,
-    // use ConstantFoldTerminator to get rid of in-edges, record DT updates and
-    // delete dead BBs.
-    for (BasicBlock *DeadBB : BlocksToErase) {
-      // If there are any PHI nodes in this successor, drop entries for BB now.
-      for (Value::user_iterator UI = DeadBB->user_begin(),
-                                UE = DeadBB->user_end();
-           UI != UE;) {
-        // Grab the user and then increment the iterator early, as the user
-        // will be deleted. Step past all adjacent uses from the same user.
-        auto *I = dyn_cast<Instruction>(*UI);
-        do { ++UI; } while (UI != UE && *UI == I);
-
-        // Ignore blockaddress users; BasicBlock's dtor will handle them.
-        if (!I) continue;
-
-        // If we have forced an edge for an indeterminate value, then force the
-        // terminator to fold to that edge.
-        forceIndeterminateEdge(I, Solver);
-        BasicBlock *InstBB = I->getParent();
-        bool Folded = ConstantFoldTerminator(InstBB,
-                                             /*DeleteDeadConditions=*/false,
-                                             /*TLI=*/nullptr, &DTU);
-        assert(Folded &&
-              "Expect TermInst on constantint or blockaddress to be folded");
-        (void) Folded;
-        // If we folded the terminator to an unconditional branch to another
-        // dead block, replace it with Unreachable, to avoid trying to fold that
-        // branch again.
-        BranchInst *BI = cast<BranchInst>(InstBB->getTerminator());
-        if (BI && BI->isUnconditional() &&
-            !Solver.isBlockExecutable(BI->getSuccessor(0))) {
-          InstBB->getTerminator()->eraseFromParent();
-          new UnreachableInst(InstBB->getContext(), InstBB);
-        }
-      }
-      // Mark dead BB for deletion.
+    for (BasicBlock &BB : F)
+      removeNonFeasibleEdges(Solver, &BB, DTU);
+
+    for (BasicBlock *DeadBB : BlocksToErase)
       DTU.deleteBB(DeadBB);
-    }
 
     for (BasicBlock &BB : F) {
       for (BasicBlock::iterator BI = BB.begin(), E = BB.end(); BI != E;) {
         Instruction *Inst = &*BI++;
         if (Solver.getPredicateInfoFor(Inst)) {
           if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
             if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
               Value *Op = II->getOperand(0);

llvm/test/Transforms/SCCP/conditions-ranges.ll

 ; Test with 2 unrelated nested conditions.
 define void @f7_nested_conds(i32* %a, i32 %b) {
 ; CHECK-LABEL: @f7_nested_conds(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_V:%.*]] = load i32, i32* [[A:%.*]], align 4
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ne i32 [[A_V]], 0
 ; CHECK-NEXT:    br i1 [[C_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       false:
-; CHECK-NEXT:    br i1 true, label [[TRUE_2:%.*]], label [[TRUE]]
+; CHECK-NEXT:    br label [[TRUE_2:%.*]]
 ; CHECK:       true.2:
 ; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       true:
-; CHECK-NEXT:    store i32 [[B:%.*]], i32* [[A]]
+; CHECK-NEXT:    store i32 [[B:%.*]], i32* [[A]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a.v = load i32, i32* %a
   %c.1 = icmp ne i32 %a.v, 0
   br i1 %c.1, label %true, label %false
 
 false:

llvm/test/Transforms/SCCP/domtree-update.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes=ipsccp < %s | FileCheck %s
+
+; DTU should not crash.
+
+define i32 @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    br label [[IF_THEN2:%.*]]
+; CHECK:       if.then2:
+; CHECK-NEXT:    br label [[FOR_INC:%.*]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry
+  br i1 true, label %if.then2, label %if.else
+
+if.then2:                                         ; preds = %for.body
+  br label %for.inc
+
+if.else:                                          ; preds = %for.body
+  br i1 undef, label %lor.rhs, label %if.then19.critedge
+
+lor.rhs:                                          ; preds = %if.else
+  br i1 undef, label %if.then19, label %for.inc
+
+if.then19.critedge:                               ; preds = %if.else
+  br label %if.then19
+
+if.then19:                                        ; preds = %if.then19.critedge, %lor.rhs
+  unreachable
+
+for.inc:                                          ; preds = %lor.rhs, %if.then2
+  unreachable
+}

llvm/test/Transforms/SCCP/predicateinfo-cond.ll

 
 define void @pr46814(i32 %a) {
 ; CHECK-LABEL: @pr46814(
 ; CHECK-NEXT:    [[C1:%.*]] = icmp uge i32 [[A:%.*]], 10
 ; CHECK-NEXT:    [[C2:%.*]] = icmp ult i32 [[A]], 20
 ; CHECK-NEXT:    [[C3:%.*]] = and i1 [[C1]], [[C2]]
 ; CHECK-NEXT:    br i1 [[C3]], label [[IF_1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       if.1:
-; CHECK-NEXT:    br i1 true, label [[IF_2:%.*]], label [[EXIT]]
+; CHECK-NEXT:    br label [[IF_2:%.*]]
 ; CHECK:       if.2:
 ; CHECK-NEXT:    br i1 true, label [[EXIT]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
   %c1 = icmp uge i32 %a, 10
   %c2 = icmp ult i32 %a, 20
   %c3 = and i1 %c1, %c2

llvm/test/Transforms/SCCP/resolvedundefsin-tracked-fn.ll

entry:
   ret i32 undef
 
 }
 
 define internal i1 @test2_g(%t1* %h, i32 %i) {
 ; CHECK-LABEL: define {{[^@]+}}@test2_g
 ; CHECK-SAME: (%t1* [[H:%.*]], i32 [[I:%.*]])
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br i1 true, label [[LAND_RHS:%.*]], label [[LAND_END:%.*]]
+; CHECK-NEXT:    br label [[LAND_RHS:%.*]]
 ; CHECK:       land.rhs:
 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 (...) @test2_j()
 ; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp ne i32 [[CALL]], 0
-; CHECK-NEXT:    br label [[LAND_END]]
+; CHECK-NEXT:    br label [[LAND_END:%.*]]
 ; CHECK:       land.end:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[TOBOOL1]], [[LAND_RHS]] ]
 ; CHECK-NEXT:    ret i1 undef
 ;
 entry:
   %tobool = icmp ne i32 %i, 0
   br i1 %tobool, label %land.rhs, label %land.end
 
 land.rhs:                                         ; preds = %entry
   %call = call i32 (...) @test2_j()

 ; CHECK-LABEL: define {{[^@]+}}@test3_k
 ; CHECK-SAME: (i8 [[H:%.*]], i32 [[I:%.*]])
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @e, align 4
 ; CHECK-NEXT:    [[CONV:%.*]] = sext i32 [[TMP0]] to i64
 ; CHECK-NEXT:    [[TMP1:%.*]] = inttoptr i64 [[CONV]] to %t1*
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i1 [ undef, [[ENTRY:%.*]] ], [ false, [[LOOP]] ]
 ; CHECK-NEXT:    [[CALL:%.*]] = call i1 @test3_g(%t1* [[TMP1]], i32 0)
 ; CHECK-NEXT:    call void @use.1(i1 false)
-; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 undef
 ;
 entry:
   %0 = load i32, i32* @e, align 4
   %conv = sext i32 %0 to i64
   %1 = inttoptr i64 %conv to %t1*
   br label %loop

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -ipsccp < %s -S | FileCheck %s
 ; RUN: opt -passes=ipsccp < %s -S | FileCheck %s
 
 define void @barney() {
 ; CHECK-LABEL: @barney(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    br label %bb9
+; CHECK-NEXT:    br label [[BB9:%.*]]
 ; CHECK:       bb6:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb9:
-; CHECK-NEXT:    unreachable
+; CHECK-NEXT:    br label [[BB6:%.*]]
 ;
 bb:
   br label %bb9
 
 bb6:                                              ; preds = %bb9
   unreachable
 
 bb7:                                              ; preds = %bb9
   unreachable
 
 bb9:                                              ; preds = %bb
   switch i16 0, label %bb6 [
   i16 61, label %bb7
   ]
 }
 
 define void @blam() {
 ; CHECK-LABEL: @blam(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    br label %bb16
+; CHECK-NEXT:    br label [[BB16:%.*]]
 ; CHECK:       bb16:
-; CHECK-NEXT:    br label %bb38
+; CHECK-NEXT:    br label [[BB38:%.*]]
 ; CHECK:       bb38:
 ; CHECK-NEXT:    unreachable
 ;
 bb:
   br label %bb16
 
 bb16:                                             ; preds = %bb
   switch i32 0, label %bb38 [

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

llvm/test/Transforms/SCCP/switch.ll

 ; CHECK-NEXT:    ret void
 ;
   switch i32 undef, label %d []
 d:
   call void @foo()
   ret void
 }
 
 define i32 @test_duplicate_successors_phi(i1 %c, i32 %x) {
 ; CHECK-LABEL: @test_duplicate_successors_phi(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[SWITCH:%.*]], label [[END:%.*]]
 ; CHECK:       switch:
-; CHECK-NEXT:    switch i32 -1, label [[SWITCH_DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 0, label [[END]]
-; CHECK-NEXT:    i32 1, label [[END]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[SWITCH_DEFAULT:%.*]]
 ; CHECK:       switch.default:
 ; CHECK-NEXT:    ret i32 -1
 ; CHECK:       end:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ 1, [[SWITCH]] ], [ 1, [[SWITCH]] ]
-; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
 entry:
   br i1 %c, label %switch, label %end
 
 switch:
   switch i32 -1, label %switch.default [
   i32 0, label %end
   i32 1, label %end

llvm/test/Transforms/SCCP/widening.ll

 ; IPSCCP-NEXT:    [[C_2:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_2]], label [[EXIT]], label [[BB2:%.*]]
 ; IPSCCP:       bb2:
 ; IPSCCP-NEXT:    [[C_3:%.*]] = call i1 @cond()
 ; IPSCCP-NEXT:    br i1 [[C_3]], label [[BB3:%.*]], label [[EXIT]]
 ; IPSCCP:       bb3:
 ; IPSCCP-NEXT:    br label [[EXIT]]
 ; IPSCCP:       exit:
-; IPSCCP-NEXT:    [[P:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 3, [[BB1]] ], [ 2, [[BB2]] ], [ 5, [[BB3]] ], [ [[A:%.*]], [[EXIT]] ]
-; IPSCCP-NEXT:    [[A]] = add i32 [[P]], 1
+; IPSCCP-NEXT:    [[P:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 3, [[BB1]] ], [ 2, [[BB2]] ], [ 5, [[BB3]] ]
+; IPSCCP-NEXT:    [[A:%.*]] = add i32 [[P]], 1
 ; IPSCCP-NEXT:    call void @use(i1 true)
 ; IPSCCP-NEXT:    call void @use(i1 false)
-; IPSCCP-NEXT:    br i1 false, label [[EXIT]], label [[EXIT_1:%.*]]
+; IPSCCP-NEXT:    br label [[EXIT_1:%.*]]
 ; IPSCCP:       exit.1:
 ; IPSCCP-NEXT:    ret void
 ;
 entry:
   %c.1 = call i1 @cond()
   br i1 %c.1, label %exit, label %bb1
 
 bb1:

 ; SCCP:       bb3:
 ; SCCP-NEXT:    unreachable
 ; SCCP:       bb4:
 ; SCCP-NEXT:    [[TMP5:%.*]] = add i64 [[TMP2]], 3
 ; SCCP-NEXT:    [[TMP6:%.*]] = and i64 [[TMP5]], 3
 ; SCCP-NEXT:    [[TMP7:%.*]] = sub i64 3, [[TMP6]]
 ; SCCP-NEXT:    [[TMP8:%.*]] = shl i64 [[TMP7]], 1
 ; SCCP-NEXT:    [[TMP9:%.*]] = trunc i64 [[TMP8]] to i32
-; SCCP-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP9]] to i64
+; SCCP-NEXT:    [[TMP0:%.*]] = zext i32 [[TMP9]] to i64
 ; SCCP-NEXT:    br label [[BB11:%.*]]
 ; SCCP:       bb11:
-; SCCP-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP10]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ]
+; SCCP-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP0]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ]
 ; SCCP-NEXT:    br label [[BB13:%.*]]
 ; SCCP:       bb13:
 ; SCCP-NEXT:    [[C_1:%.*]] = icmp eq i64 [[TMP12]], 6
 ; SCCP-NEXT:    br i1 [[C_1]], label [[BB15:%.*]], label [[BB16:%.*]]
 ; SCCP:       bb15:
 ; SCCP-NEXT:    unreachable
 ; SCCP:       bb16:
 ; SCCP-NEXT:    [[TMP17]] = add i64 [[TMP12]], 2

 ; IPSCCP:       bb3:
 ; IPSCCP-NEXT:    unreachable
 ; IPSCCP:       bb4:
 ; IPSCCP-NEXT:    [[TMP5:%.*]] = add i64 [[TMP2]], 3
 ; IPSCCP-NEXT:    [[TMP6:%.*]] = and i64 [[TMP5]], 3
 ; IPSCCP-NEXT:    [[TMP7:%.*]] = sub i64 3, [[TMP6]]
 ; IPSCCP-NEXT:    [[TMP8:%.*]] = shl i64 [[TMP7]], 1
 ; IPSCCP-NEXT:    [[TMP9:%.*]] = trunc i64 [[TMP8]] to i32
-; IPSCCP-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP9]] to i64
+; IPSCCP-NEXT:    [[TMP0:%.*]] = zext i32 [[TMP9]] to i64
 ; IPSCCP-NEXT:    br label [[BB11:%.*]]
 ; IPSCCP:       bb11:
-; IPSCCP-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP10]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ]
+; IPSCCP-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP0]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ]
 ; IPSCCP-NEXT:    br label [[BB13:%.*]]
 ; IPSCCP:       bb13:
 ; IPSCCP-NEXT:    [[C_1:%.*]] = icmp eq i64 [[TMP12]], 6
 ; IPSCCP-NEXT:    br i1 [[C_1]], label [[BB15:%.*]], label [[BB16:%.*]]
 ; IPSCCP:       bb15:
 ; IPSCCP-NEXT:    unreachable
 ; IPSCCP:       bb16:
 ; IPSCCP-NEXT:    [[TMP17]] = add i64 [[TMP12]], 2