Generalize MergeBlockIntoPredecessor. Replace uses of MergeBasicBlockIntoOnlyPred.

[asbirlea]

Summary

Two utils methods have essentially the same functionality. This is an attempt to merge them into one.

1. lib/Transforms/Utils/Local.cpp : MergeBasicBlockIntoOnlyPred
2. lib/Transforms/Utils/BasicBlockUtils.cpp : MergeBlockIntoPredecessor

Prior to the patch:

1. MergeBasicBlockIntoOnlyPred

Updates either DomTree or DeferredDominance
Moves all instructions from Pred to BB, deletes Pred
Asserts BB has single predecessor
If address was taken, replace the block address with constant 1 (?)

2. MergeBlockIntoPredecessor

Updates DomTree, LoopInfo and MemoryDependenceResults
Moves all instruction from BB to Pred, deletes BB
Returns if doesn't have a single predecessor
Returns if BB's address was taken

After the patch:
Method 2. MergeBlockIntoPredecessor is attempting to become the new default:
Updates DomTree or DeferredDominance, and LoopInfo and MemoryDependenceResults
Moves all instruction from BB to Pred, deletes BB
Returns if doesn't have a single predecessor
Returns if BB's address was taken

Uses of MergeBasicBlockIntoOnlyPred that need to be replaced:

1. lib/Transforms/Scalar/LoopSimplifyCFG.cpp

Updated in this patch. No challenges.

2. lib/CodeGen/CodeGenPrepare.cpp

Updated in this patch.

i. eliminateFallThrough is straightforward, but I added using a temporary array to avoid the iterator invalidation.
ii. eliminateMostlyEmptyBlock(s) methods also now use a temporary array for blocks

Some interesting aspects:

• Since Pred is not deleted (BB is), the entry block does not need updating.
• The entry block was being updated with the deleted block in eliminateMostlyEmptyBlock. Added assert to make obvious that BB=SinglePred.
• isMergingEmptyBlockProfitable assumes BB is the one to be deleted.
• eliminateMostlyEmptyBlock(BB) does not delete BB on one path, it deletes its unique predecessor instead.
• adding some test owner as subscribers for the interesting tests modified: test/CodeGen/X86/avx-cmp.ll test/CodeGen/AMDGPU/nested-loop-conditions.ll test/CodeGen/AMDGPU/si-annotate-cf.ll test/CodeGen/X86/hoist-spill.ll test/CodeGen/X86/2006-11-17-IllegalMove.ll

3. lib/Transforms/Scalar/JumpThreading.cpp

Not covered in this patch. It is the only use case using the DeferredDominance.
I would defer to Brian Rzycki to make this replacement.

[dberris]

lib/CodeGen/CodeGenPrepare.cpp

526

This could just be 'auto *BB =' since you mention BasicBlock already in the cast.

527–528

You could reverse this, so you end up with:

for (auto &Block : Blocks) {
  if (auto *BB = cast_or_null<BasicBlock>(Block)) {
    ...
  }
}

lib/Transforms/Utils/BasicBlockUtils.cpp

162

Consider Updates.emplace_back(DominatorTree::Delete, PredBB, BB) instead? Or does that not work because DominatorTree::UpdateType is an aggregate?

[dmgreen]

lib/Transforms/Utils/BasicBlockUtils.cpp

137–139

This and the previous block is just (PredBB->getUniqueSuccessor() == BB)?

166

I see this comes from the other function, but PredBB should only have one successor (BB), if I am reading this correctly. So this should always be true.

[trentxintong]

I think this makes sense. Except Jumpthreading needs to be modified to make sure iterator is valid after merging. I can work on the jump threading part once this lands and if you do not mind @brzycki.

[asbirlea]

Address comments.

[asbirlea]

Thank you for the comments!

lib/CodeGen/CodeGenPrepare.cpp

527–528

Agreed, but I favored reducing nesting here for easier readability.

lib/Transforms/Utils/BasicBlockUtils.cpp

137–139

This method is expected to also merge blocks when there are multiple edges from PredBB to BB.
Example: test/Transforms/SimplifyCFG/2003-08-17-FoldSwitch.ll: test3

Start:          ; preds = %0
  switch i32 3, label %TheDest [
  i32 0, label %TheDest
  i32 1, label %TheDest
  i32 2, label %TheDest
  i32 5, label %TheDest
  ]
TheDest:
  ret i32 1234

162

Being an aggregate should still work, but it doesn't link because it can't find Delete, declared as static constexpr in DominatorTreeBase. The options I got are:

• Instead of DominatorTree::Delete use the "original" enum which is DomTreeBuilder::UpdateKind::Delete, but that's icky to expose.
• Use a temporary local variable auto tmp = DominatorTree::Delete, and use that in the emplace_back.
• Use push_back.

I'm inclined to just keep the push_back here, but let me know if you think otherwise.

166

Agreed, updated.

[dmgreen]

You may need to update Transforms/LoopSimplifyCFG/scev.ll now too (which is hopefully simple). Otherwise this looks sensible to me.

lib/Transforms/Utils/BasicBlockUtils.cpp

137–139

I believe this is what getUniqueSuccessor does (as opposed to getSingleSuccessor). You are not making things any worse by leaving it as it is though.

[asbirlea]

Address comments and rebase.

[asbirlea]

format.

[asbirlea]

Updated scev.ll to be fully parametric (vs updating one label). All other tests should use variables as well, but that can be a separate cleanup.

lib/Transforms/Utils/BasicBlockUtils.cpp

137–139

Ah, I missed the difference from getSingleSuccessor. Thank you for following up!

[dmgreen]

LGTM, thanks.

(Providing no one has any problems with the rest of these test changes)

[chandlerc]

Still a few things left, but really close.

lib/CodeGen/CodeGenPrepare.cpp

522

You can use a range based loop here now that you're putting them into a temporary array.

598–605

Due to building a WeakTrackingVH, may not work.

But why not use a range based loop below? should be safe now.

778–779

This seems like a bug then -- we can't print the SinglePred after it is deleted...

[asbirlea]

Address comments.

[asbirlea]

Thank you for the review!

lib/CodeGen/CodeGenPrepare.cpp

778–779

Updated comment, SinglePred is not deleted.

[kuhar]

lib/Transforms/Utils/BasicBlockUtils.cpp

162

FYI: Updates.push_back({DominatorTree::Delete, PredBB, BB}); is used in almost all places that do DT updates. I'm not sure what benefit emplace_back would have over push_back in this case.

[asbirlea]

lib/Transforms/Utils/BasicBlockUtils.cpp

162

Ack, thank you for the input! Leaving as is.

[chandlerc]

LGTM!

[brzycki]

My apologies for missing this review, for some reason I wasn't notified of being added. I will look into the potential replacement of MergeBlockIntoPredecessor for JumpThreading.

[asbirlea]

@brzycki: Great, thank you!

[asbirlea]

Am I right that there is yet another method doing the same thing?
lib/Transforms/Utils/LoopUnroll.cpp:foldBlockIntoPredecessor

/// Folds a basic block into its predecessor if it only has one predecessor, and
/// that predecessor only has one successor.
/// The LoopInfo Analysis that is passed will be kept consistent.
BasicBlock *llvm::foldBlockIntoPredecessor(BasicBlock *BB, LoopInfo *LI,
                                           ScalarEvolution *SE,
                                           DominatorTree *DT) {

include/llvm/Transforms/Utils/BasicBlockUtils.h

 /// tracing the def-use list from the PHI to see if it is ultimately unused or
 /// if it reaches an unused cycle. Return true if any PHIs were deleted.
 bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr);
 
 /// Attempts to merge a block into its predecessor, if possible. The return
 /// value indicates success or failure.
 bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr,
                                LoopInfo *LI = nullptr,
-                               MemoryDependenceResults *MemDep = nullptr);
+                               MemoryDependenceResults *MemDep = nullptr,
+                               DeferredDominance *DDT = nullptr);
 
 /// Replace all uses of an instruction (specified by BI) with a value, then
 /// remove and delete the original instruction.
 void ReplaceInstWithValue(BasicBlock::InstListType &BIL,
                           BasicBlock::iterator &BI, Value *V);
 
 /// Replace the instruction specified by BI with the instruction specified by I.
 /// Copies DebugLoc from BI to I, if I doesn't already have a DebugLoc. The

lib/CodeGen/CodeGenPrepare.cpp

 }
 
 /// Merge basic blocks which are connected by a single edge, where one of the
 /// basic blocks has a single successor pointing to the other basic block,
 /// which has a single predecessor.
 bool CodeGenPrepare::eliminateFallThrough(Function &F) {
   bool Changed = false;
   // Scan all of the blocks in the function, except for the entry block.
-  for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
-    BasicBlock *BB = &*I++;
+  // Use a temporary array to avoid iterator being invalidated when
+  // deleting blocks.
+  SmallVector<WeakTrackingVH, 16> Blocks;
+  for (auto &Block : llvm::make_range(std::next(F.begin()), F.end()))
+    Blocks.push_back(&Block);
+
+  for (auto &Block : Blocks) {
+    auto *BB = cast_or_null<BasicBlock>(Block);
+    if (!BB)
+      continue;
     // If the destination block has a single pred, then this is a trivial
     // edge, just collapse it.
     BasicBlock *SinglePred = BB->getSinglePredecessor();
 
     // Don't merge if BB's address is taken.
     if (!SinglePred || SinglePred == BB || BB->hasAddressTaken()) continue;
 
     BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
     if (Term && !Term->isConditional()) {
       Changed = true;
-      LLVM_DEBUG(dbgs() << "To merge:\n" << *SinglePred << "\n\n\n");
-      // Remember if SinglePred was the entry block of the function.
-      // If so, we will need to move BB back to the entry position.
-      bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
-      MergeBasicBlockIntoOnlyPred(BB, nullptr);
+      LLVM_DEBUG(dbgs() << "To merge:\n" << *BB << "\n\n\n");
 
-      if (isEntry && BB != &BB->getParent()->getEntryBlock())
-        BB->moveBefore(&BB->getParent()->getEntryBlock());
-
-      // We have erased a block. Update the iterator.
-      I = BB->getIterator();
+      // Merge BB into SinglePred and delete it.
+      MergeBlockIntoPredecessor(BB);
     }
   }
   return Changed;
 }
 
 /// Find a destination block from BB if BB is mergeable empty block.
 BasicBlock *CodeGenPrepare::findDestBlockOfMergeableEmptyBlock(BasicBlock *BB) {
   // If this block doesn't end with an uncond branch, ignore it.
bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) {
   while (!LoopList.empty()) {
     Loop *L = LoopList.pop_back_val();
     LoopList.insert(LoopList.end(), L->begin(), L->end());
     if (BasicBlock *Preheader = L->getLoopPreheader())
       Preheaders.insert(Preheader);
   }
 
   bool MadeChange = false;
+  // Copy blocks into a temporary array to avoid iterator invalidation issues
+  // as we remove them.
   // Note that this intentionally skips the entry block.
-  for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
-    BasicBlock *BB = &*I++;
+  SmallVector<WeakTrackingVH, 16> Blocks;
+  for (auto &Block : llvm::make_range(std::next(F.begin()), F.end()))
+    Blocks.push_back(&Block);
+
+  for (auto &Block : Blocks) {
+    BasicBlock *BB = cast_or_null<BasicBlock>(Block);
+    if (!BB)
+      continue;
     BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
     if (!DestBB ||
         !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.count(BB)))
       continue;
 
     eliminateMostlyEmptyBlock(BB);
     MadeChange = true;
   }
void CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
 
   LLVM_DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n"
                     << *BB << *DestBB);
 
   // If the destination block has a single pred, then this is a trivial edge,
   // just collapse it.
   if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
     if (SinglePred != DestBB) {
-      // Remember if SinglePred was the entry block of the function.  If so, we
-      // will need to move BB back to the entry position.
-      bool isEntry = SinglePred == &SinglePred->getParent()->getEntryBlock();
-      MergeBasicBlockIntoOnlyPred(DestBB, nullptr);
-
-      if (isEntry && BB != &BB->getParent()->getEntryBlock())
-        BB->moveBefore(&BB->getParent()->getEntryBlock());
-
-      LLVM_DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
+      assert(SinglePred == BB &&
+             "Single predecessor not the same as predecessor");
+      // Merge DestBB into SinglePred/BB and delete it.
+      MergeBlockIntoPredecessor(DestBB);
+      // Note: BB(=SinglePred) will not be deleted on this path.
+      // DestBB(=its single successor) is the one that was deleted.
+      LLVM_DEBUG(dbgs() << "AFTER:\n" << *SinglePred << "\n\n\n");
       return;
     }
   }
 
   // Otherwise, we have multiple predecessors of BB.  Update the PHIs in DestBB
   // to handle the new incoming edges it is about to have.
   for (PHINode &PN : DestBB->phis()) {
     // Remove the incoming value for BB, and remember it.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-simplifycfg"
 
 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
                             ScalarEvolution &SE) {
   bool Changed = false;
   // Copy blocks into a temporary array to avoid iterator invalidation issues
   // as we remove them.
   SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
 
   for (auto &Block : Blocks) {
     // Attempt to merge blocks in the trivial case. Don't modify blocks which
     // belong to other loops.
     BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
     if (!Succ)
       continue;
 
     BasicBlock *Pred = Succ->getSinglePredecessor();
     if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
       continue;
 
-    // Pred is going to disappear, so we need to update the loop info.
-    if (L.getHeader() == Pred)
-      L.moveToHeader(Succ);
-    LI.removeBlock(Pred);
-    MergeBasicBlockIntoOnlyPred(Succ, &DT);
+    // Merge Succ into Pred and delete it.
+    MergeBlockIntoPredecessor(Succ, &DT, &LI);
 
     SE.forgetLoop(&L);
     Changed = true;
   }
 
   return Changed;
 }
 

lib/Transforms/Utils/BasicBlockUtils.cpp

for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
     if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
       Changed |= RecursivelyDeleteDeadPHINode(PN, TLI);
 
   return Changed;
 }
 
 bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT,
                                      LoopInfo *LI,
-                                     MemoryDependenceResults *MemDep) {
-  // Don't merge away blocks who have their address taken.
-  if (BB->hasAddressTaken()) return false;
+                                     MemoryDependenceResults *MemDep,
+                                     DeferredDominance *DDT) {
+  assert(!(DT && DDT) && "Cannot call with both DT and DDT.");
+
+  if (BB->hasAddressTaken())
+    return false;
 
   // Can't merge if there are multiple predecessors, or no predecessors.
   BasicBlock *PredBB = BB->getUniquePredecessor();
   if (!PredBB) return false;
 
   // Don't break self-loops.
   if (PredBB == BB) return false;
   // Don't break unwinding instructions.
   if (PredBB->getTerminator()->isExceptional())
     return false;
 
-  succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB));
-  BasicBlock *OnlySucc = BB;
-  for (; SI != SE; ++SI)
-    if (*SI != OnlySucc) {
-      OnlySucc = nullptr;     // There are multiple distinct successors!
-      break;
-    }
-
-  // Can't merge if there are multiple successors.
-  if (!OnlySucc) return false;
+  // Can't merge if there are multiple distinct successors.
+  if (PredBB->getUniqueSuccessor() != BB)
+    return false;
 
   // Can't merge if there is PHI loop.
   for (PHINode &PN : BB->phis())
     for (Value *IncValue : PN.incoming_values())
       if (IncValue == &PN)
         return false;
 
   // Begin by getting rid of unneeded PHIs.
   SmallVector<AssertingVH<Value>, 4> IncomingValues;
   if (isa<PHINode>(BB->front())) {
     for (PHINode &PN : BB->phis())
       if (!isa<PHINode>(PN.getIncomingValue(0)) ||
           cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
         IncomingValues.push_back(PN.getIncomingValue(0));
     FoldSingleEntryPHINodes(BB, MemDep);
   }
 
+  // Deferred DT update: Collect all the edges that exit BB. These
+  // dominator edges will be redirected from Pred.
+  std::vector<DominatorTree::UpdateType> Updates;
+  if (DDT) {
+    Updates.reserve(1 + (2 * succ_size(BB)));
+    Updates.push_back({DominatorTree::Delete, PredBB, BB});
+    for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
+      Updates.push_back({DominatorTree::Delete, BB, *I});
+      Updates.push_back({DominatorTree::Insert, PredBB, *I});
+    }
+  }
+
   // Delete the unconditional branch from the predecessor...
   PredBB->getInstList().pop_back();
 
   // Make all PHI nodes that referred to BB now refer to Pred as their
   // source...
   BB->replaceAllUsesWith(PredBB);
 
   // Move all definitions in the successor to the predecessor...
if (DT)
     }
 
   if (LI)
     LI->removeBlock(BB);
 
   if (MemDep)
     MemDep->invalidateCachedPredecessors();
 
-  BB->eraseFromParent();
+  if (DDT) {
+    DDT->deleteBB(BB); // Deferred deletion of BB.
+    DDT->applyUpdates(Updates);
+  } else {
+    BB->eraseFromParent(); // Nuke BB.
+  }
   return true;
 }
 
 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
                                 BasicBlock::iterator &BI, Value *V) {
   Instruction &I = *BI;
   // Replaces all of the uses of the instruction with uses of the value
   I.replaceAllUsesWith(V);

test/CodeGen/AMDGPU/branch-relaxation.ll

 ; GCN-NEXT: s_xor_b64  [[MASK:s\[[0-9]+:[0-9]+\]]], exec, [[TEMP_MASK]]
 ; GCN-NEXT: ; mask branch [[FLOW:BB[0-9]+_[0-9]+]]
 
 ; GCN: [[FLOW]]: ; %Flow
 ; GCN-NEXT: s_or_saveexec_b64 [[TEMP_MASK1:s\[[0-9]+:[0-9]+\]]], [[MASK]]
 ; GCN-NEXT: s_xor_b64 exec, exec, [[TEMP_MASK1]]
 ; GCN-NEXT: ; mask branch [[RET:BB[0-9]+_[0-9]+]]
 
-; GCN: [[LOOP_BODY:BB[0-9]+_[0-9]+]]: ; %loop_body
+; GCN: [[LOOP_BODY:BB[0-9]+_[0-9]+]]: ; %loop
 ; GCN: ;;#ASMSTART
 ; GCN: v_nop_e64
 ; GCN: v_nop_e64
 ; GCN: v_nop_e64
 ; GCN: v_nop_e64
 ; GCN: v_nop_e64
 ; GCN: v_nop_e64
 ; GCN: ;;#ASMEND
 ; GCN: s_cbranch_vccz [[RET]]
 
-; GCN-NEXT: [[LONGBB:BB[0-9]+_[0-9]+]]: ; %loop_body
+; GCN-NEXT: [[LONGBB:BB[0-9]+_[0-9]+]]: ; %loop
 ; GCN-NEXT: ; in Loop: Header=[[LOOP_BODY]] Depth=1
 ; GCN-NEXT: s_getpc_b64 vcc
 ; GCN-NEXT: s_sub_u32 vcc_lo, vcc_lo, ([[LONGBB]]+4)-[[LOOP_BODY]]
 ; GCN-NEXT: s_subb_u32 vcc_hi, vcc_hi, 0
 ; GCN-NEXT: s_setpc_b64 vcc
 
 ; GCN-NEXT: [[RET]]: ; %UnifiedReturnBlock
 ; GCN-NEXT: s_endpgm

test/CodeGen/AMDGPU/nested-loop-conditions.ll

 ; IR-NEXT: br label %bb9
 
 ; IR: bb23:
 ; IR-NEXT: call void @llvm.amdgcn.end.cf(i64 %loop.phi)
 ; IR-NEXT: ret void
 
 ; GCN-LABEL: {{^}}reduced_nested_loop_conditions:
 
-; GCN: s_cmp_eq_u32 s{{[0-9]+}}, 1
-; GCN-NEXT: s_cbranch_scc1
+; GCN: s_cmp_lg_u32 s{{[0-9]+}}, 1
+; GCN-NEXT: s_cbranch_scc0
 
 ; FIXME: Should fold to unconditional branch?
 ; GCN: ; implicit-def
-; GCN: s_cbranch_vccz
+; GCN: s_cbranch_vccnz
 
 ; GCN: ds_read_b32
 
 ; GCN: [[BB9:BB[0-9]+_[0-9]+]]: ; %bb9
 ; GCN-NEXT: ; =>This Inner Loop Header: Depth=1
 ; GCN-NEXT: s_cbranch_vccnz [[BB9]]
 define amdgpu_kernel void @reduced_nested_loop_conditions(i64 addrspace(3)* nocapture %arg) #0 {
 bb:

test/CodeGen/AMDGPU/si-annotate-cf.ll

 sw.epilog:
   ret void
 }
 
 declare float @llvm.fabs.f32(float) nounwind readnone
 
 ; This broke the old AMDIL cfg structurizer
 ; FUNC-LABEL: {{^}}loop_land_info_assert:
-; SI: s_cmp_gt_i32
-; SI-NEXT: s_cbranch_scc0 [[ENDPGM:BB[0-9]+_[0-9]+]]
+; SI: s_cmp_lt_i32
+; SI-NEXT: s_cbranch_scc1 [[ENDPGM:BB[0-9]+_[0-9]+]]
 
-; SI: s_cmpk_gt_i32
-; SI-NEXT: s_cbranch_scc1 [[ENDPGM]]
+; SI: s_cmpk_lt_i32
+; SI-NEXT: s_cbranch_scc0 [[ENDPGM]]
 
 ; SI: [[INFLOOP:BB[0-9]+_[0-9]+]]
 ; SI: s_cbranch_vccnz [[INFLOOP]]
 
 ; SI: [[ENDPGM]]:
 ; SI: s_endpgm
 define amdgpu_kernel void @loop_land_info_assert(i32 %c0, i32 %c1, i32 %c2, i32 %c3, i32 %x, i32 %y, i1 %arg) nounwind {
 entry:

test/CodeGen/ARM/indirectbr.ll

L4:                                               ; preds = %L5, %bb2
   %res.0 = phi i32 [ 385, %L5 ], [ 35, %bb2 ]     ; <i32> [#uses=1]
   br label %L3
 
 L3:                                               ; preds = %L4, %bb2
   %res.1 = phi i32 [ %res.0, %L4 ], [ 5, %bb2 ]   ; <i32> [#uses=1]
   br label %L2
 
 L2:                                               ; preds = %L3, %bb2
-; THUMB-LABEL: %L1.clone
+; THUMB-LABEL: %.split4
 ; THUMB: muls
   %res.2 = phi i32 [ %res.1, %L3 ], [ 1, %bb2 ]   ; <i32> [#uses=1]
   %phitmp = mul i32 %res.2, 6                     ; <i32> [#uses=1]
   br label %L1
 
 L1:                                               ; preds = %L2, %bb2
   %res.3 = phi i32 [ %phitmp, %L2 ], [ 2, %bb2 ]  ; <i32> [#uses=1]
 ; ARM-LABEL: %L1

test/CodeGen/PowerPC/memCmpUsedInZeroEqualityComparison.ll

; CHECK-NEXT:    blr
   %call.lobit = lshr i32 %call, 31
   %call.lobit.not = xor i32 %call.lobit, 1
   ret i32 %call.lobit.not
 }
 
 ; Validate with memcmp()?:
 define signext i32 @equalityFoldTwoConstants() {
 ; CHECK-LABEL: equalityFoldTwoConstants:
-; CHECK:       # %bb.0: # %endblock
+; CHECK:       # %bb.0: # %loadbb
 ; CHECK-NEXT:    li 3, 1
 ; CHECK-NEXT:    blr
   %call = tail call signext i32 @memcmp(i8* bitcast ([15 x i32]* @zeroEqualityTest04.buffer1 to i8*), i8* bitcast ([15 x i32]* @zeroEqualityTest04.buffer2 to i8*), i64 16)
   %not.tobool = icmp eq i32 %call, 0
   %cond = zext i1 %not.tobool to i32
   ret i32 %cond
 }
 

test/CodeGen/PowerPC/memcmp-mergeexpand.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -verify-machineinstrs -mcpu=pwr8 -mtriple=powerpc64le-unknown-gnu-linux  < %s | FileCheck %s -check-prefix=PPC64LE
 
 ; This tests interaction between MergeICmp and ExpandMemCmp.
 
 %"struct.std::pair" = type { i32, i32 }
 
 define zeroext i1 @opeq1(
 ; PPC64LE-LABEL: opeq1:
-; PPC64LE:       # %bb.0: # %opeq1.exit
+; PPC64LE:       # %bb.0: # %entry
 ; PPC64LE-NEXT:    ld 3, 0(3)
 ; PPC64LE-NEXT:    ld 4, 0(4)
 ; PPC64LE-NEXT:    xor 3, 3, 4
 ; PPC64LE-NEXT:    cntlzd 3, 3
 ; PPC64LE-NEXT:    rldicl 3, 3, 58, 63
 ; PPC64LE-NEXT:    blr
   %"struct.std::pair"* nocapture readonly dereferenceable(8) %a,
   %"struct.std::pair"* nocapture readonly dereferenceable(8) %b) local_unnamed_addr #0 {

test/CodeGen/PowerPC/ppc-shrink-wrapping.ll

 ; CHECK: .[[LOOP:LBB[0-9_]+]]: # %for.body
 ; CHECK: bl something
 ; CHECK-DAG: addi [[IV]], [[IV]], -1
 ; CHECK-DAG: add [[SUM]], 3, [[SUM]] 
 ; CHECK-NEXT: cmplwi [[IV]], 0
 ; CHECK-NEXT: bne 0, .[[LOOP]]
 ;
 ; Next BB
-; CHECK: %for.end
+; CHECK: %for.exit
 ; CHECK: mtlr {{[0-9]+}}
 ; CHECK-NEXT: blr
 define i32 @freqSaveAndRestoreOutsideLoop2(i32 %cond) {
 entry:
   br label %for.preheader
 
 for.preheader:
   tail call void asm "nop", ""()

test/CodeGen/PowerPC/simplifyConstCmpToISEL.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=powerpc64le-unknown-unknown -mcpu=pwr8 \
 ; RUN:   -ppc-convert-rr-to-ri -verify-machineinstrs | FileCheck %s
 define void @test(i32 zeroext %parts) {
 ; CHECK-LABEL: test:
-; CHECK:       # %bb.0: # %cond.end.i
+; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    cmplwi 0, 3, 1
 ; CHECK-NEXT:    bnelr+ 0
 ; CHECK-NEXT:  # %bb.1: # %test2.exit.us.unr-lcssa
 ; CHECK-NEXT:    ld 3, 0(3)
 ; CHECK-NEXT:    std 3, 0(3)
 entry:
   br label %cond.end.i
 

test/CodeGen/Thumb2/2010-11-22-EpilogueBug.ll

 bb2:
   call void @bar() nounwind optsize
   br i1 undef, label %bb, label %bb3
 
 bb3:
   br i1 undef, label %return, label %bb
 
 return:
-; CHECK: %return
+; CHECK: %bb3
 ; 'mov sp, r7' would have left sp in an invalid state
 ; CHECK-NOT: mov sp, r7
 ; CHECK-NOT: sub, sp, #4
 ; CHECK: add sp, #4
   ret void
 }

test/CodeGen/Thumb2/thumb2-jtb.ll

 ; RUN: llc -mtriple=thumb-eabi -mcpu=arm1156t2-s -mattr=+thumb2 -arm-adjust-jump-tables=0 %s -o - | FileCheck %s
 ; RUN: llc -mtriple=thumbv6-eabi -mcpu=cortex-m0 -arm-adjust-jump-tables=0 %s -o - | FileCheck %s
 
 ; Do not use tbb / tbh if any destination is before the jumptable.
 ; rdar://7102917
 
 define i16 @main__getopt_internal_2E_exit_2E_ce(i32, i1 %b) nounwind {
 ; CHECK: main__getopt_internal_2E_exit_2E_ce
 ; CHECK-NOT: tbb
 ; CHECK-NOT: tbh
 ; 32-bit jump tables use explicit branches, not data regions, so make sure
 ; we don't annotate this region.
 ; CHECK-NOT: data_region
 entry:
   br i1 %b, label %codeRepl127.exitStub, label %newFuncRoot
 
-newFuncRoot:
-  br label %_getopt_internal.exit.ce
-
 codeRepl127.exitStub:   ; preds = %_getopt_internal.exit.ce
   ; Add an explicit edge back to before the jump table to ensure this block
   ; is placed first.
   br i1 %b, label %newFuncRoot, label %codeRepl127.exitStub.exit
 
 codeRepl127.exitStub.exit:
   ret i16 0
 
codeRepl54.exitStub:    ; preds = %_getopt_internal.exit.ce
   ret i16 24
 
 codeRepl57.exitStub:    ; preds = %_getopt_internal.exit.ce
   ret i16 25
 
 codeRepl103.exitStub:   ; preds = %_getopt_internal.exit.ce
   ret i16 26
 
+newFuncRoot:
+  br label %_getopt_internal.exit.ce
+
 _getopt_internal.exit.ce:   ; preds = %newFuncRoot
   switch i32 %0, label %codeRepl127.exitStub [
     i32 -1, label %parse_options.exit.loopexit.exitStub
     i32 0, label %bb1.i.exitStub
     i32 63, label %bb90.i.exitStub
     i32 66, label %codeRepl104.exitStub
     i32 67, label %codeRepl113.exitStub
     i32 71, label %codeRepl51.exitStub

test/CodeGen/X86/2006-11-17-IllegalMove.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s
 
 define void @handle_vector_size_attribute() nounwind {
 ; CHECK-LABEL: handle_vector_size_attribute:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    movl 0, %eax
 ; CHECK-NEXT:    decl %eax
-; CHECK-NEXT:    cmpl $2, %eax
-; CHECK-NEXT:    jae .LBB0_2
-; CHECK-NEXT:  # %bb.1: # %cond_next129
+; CHECK-NEXT:    cmpl $1, %eax
+; CHECK-NEXT:    ja .LBB0_2
+; CHECK-NEXT:  # %bb.1: # %bb77
 ; CHECK-NEXT:    movb 0, %al
 ; CHECK-NEXT:    movzbl %al, %eax
 ; CHECK-NEXT:    # kill: def $eax killed $eax def $ax
 ; CHECK-NEXT:    divb %al
 ; CHECK-NEXT:    movzbl %al, %eax
 ; CHECK-NEXT:    cmpq %rax, %rax
 ; CHECK-NEXT:  .LBB0_2: # %bb84
 ; CHECK-NEXT:    retq

test/CodeGen/X86/avx-cmp.ll

; CHECK-NEXT:    retq
   ret <4 x i64> %s
 }
 
 declare void @scale() nounwind
 
 define void @render() nounwind {
 ; CHECK-LABEL: render:
 ; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    pushq %rbp
 ; CHECK-NEXT:    pushq %rbx
+; CHECK-NEXT:    pushq %rax
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB2_6
 ; CHECK-NEXT:  # %bb.1: # %for.cond5.preheader
 ; CHECK-NEXT:    xorl %ebx, %ebx
+; CHECK-NEXT:    movb $1, %bpl
 ; CHECK-NEXT:    jmp .LBB2_2
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB2_5: # %if.then
 ; CHECK-NEXT:    # in Loop: Header=BB2_2 Depth=1
 ; CHECK-NEXT:    callq scale
 ; CHECK-NEXT:  .LBB2_2: # %for.cond5
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    testb %bl, %bl
 ; CHECK-NEXT:    jne .LBB2_2
 ; CHECK-NEXT:  # %bb.3: # %for.cond5
 ; CHECK-NEXT:    # in Loop: Header=BB2_2 Depth=1
-; CHECK-NEXT:    testb %bl, %bl
-; CHECK-NEXT:    je .LBB2_2
+; CHECK-NEXT:    testb %bpl, %bpl
+; CHECK-NEXT:    jne .LBB2_2
 ; CHECK-NEXT:  # %bb.4: # %for.body33
 ; CHECK-NEXT:    # in Loop: Header=BB2_2 Depth=1
 ; CHECK-NEXT:    vucomisd {{\.LCPI.*}}, %xmm0
 ; CHECK-NEXT:    jne .LBB2_5
 ; CHECK-NEXT:    jp .LBB2_5
 ; CHECK-NEXT:    jmp .LBB2_2
 ; CHECK-NEXT:  .LBB2_6: # %for.end52
+; CHECK-NEXT:    addq $8, %rsp
 ; CHECK-NEXT:    popq %rbx
+; CHECK-NEXT:    popq %rbp
 ; CHECK-NEXT:    retq
 entry:
   br i1 undef, label %for.cond5, label %for.end52
 
 for.cond5:
   %or.cond = and i1 undef, false
   br i1 %or.cond, label %for.body33, label %for.cond5
 

test/CodeGen/X86/avx-splat.ll

entry:
   ret <4 x double> %vecinit6.i
 }
 
 ; Test this turns into a broadcast:
 ;   shuffle (scalar_to_vector (load (ptr + 4))), undef, <0, 0, 0, 0>
 ;
 define <8 x float> @funcE() nounwind {
 ; CHECK-LABEL: funcE:
-; CHECK:       # %bb.0: # %for_exit499
+; CHECK:       # %bb.0: # %allocas
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    # implicit-def: $ymm0
 ; CHECK-NEXT:    jne .LBB4_2
 ; CHECK-NEXT:  # %bb.1: # %load.i1247
 ; CHECK-NEXT:    pushq %rbp
 ; CHECK-NEXT:    movq %rsp, %rbp
 ; CHECK-NEXT:    andq $-32, %rsp

test/CodeGen/X86/avx2-vbroadcast.ll

 ; X32-LABEL: crash:
 ; X32:       ## %bb.0: ## %WGLoopsEntry
 ; X32-NEXT:    xorl %eax, %eax
 ; X32-NEXT:    testb %al, %al
 ; X32-NEXT:    je LBB33_1
 ; X32-NEXT:  ## %bb.2: ## %ret
 ; X32-NEXT:    retl
 ; X32-NEXT:    .p2align 4, 0x90
-; X32-NEXT:  LBB33_1: ## %footer349VF
+; X32-NEXT:  LBB33_1: ## %footer329VF
 ; X32-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; X32-NEXT:    jmp LBB33_1
 ;
 ; X64-LABEL: crash:
 ; X64:       ## %bb.0: ## %WGLoopsEntry
 ; X64-NEXT:    xorl %eax, %eax
 ; X64-NEXT:    testb %al, %al
 ; X64-NEXT:    je LBB33_1
 ; X64-NEXT:  ## %bb.2: ## %ret
 ; X64-NEXT:    retq
 ; X64-NEXT:    .p2align 4, 0x90
-; X64-NEXT:  LBB33_1: ## %footer349VF
+; X64-NEXT:  LBB33_1: ## %footer329VF
 ; X64-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; X64-NEXT:    jmp LBB33_1
 WGLoopsEntry:
   br i1 undef, label %ret, label %footer329VF
 
 footer329VF:
   %A.0.inVF = fmul float undef, 6.553600e+04
   %B.0.in407VF = fmul <8 x float> undef, <float 6.553600e+04, float 6.553600e+04, float 6.553600e+04, float 6.553600e+04, float 6.553600e+04, float 6.553600e+04, float 6.553600e+04, float 6.553600e+04>

test/CodeGen/X86/avx512-i1test.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mattr=+avx512f | FileCheck %s  --check-prefix=CHECK --check-prefix=KNL
 ; RUN: llc < %s -mattr=+avx512f -mattr=+avx512vl -mattr=+avx512bw -mattr=+avx512dq | FileCheck %s  --check-prefix=CHECK --check-prefix=SKX
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @func() {
 ; CHECK-LABEL: func:
-; CHECK:       # %bb.0: # %L_10
+; CHECK:       # %bb.0: # %bb1
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    je .LBB0_1
 ; CHECK-NEXT:  # %bb.4: # %L_30
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB0_1: # %bb56
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    jmp .LBB0_2

 ; PR 28175
 define i64 @func2(i1 zeroext %i, i32 %j) {
 ; CHECK-LABEL: func2:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    testl %esi, %esi
 ; CHECK-NEXT:    je .LBB1_1
 ; CHECK-NEXT:  # %bb.2: # %if.then
 ; CHECK-NEXT:    jmp bar # TAILCALL
-; CHECK-NEXT:  .LBB1_1: # %return
+; CHECK-NEXT:  .LBB1_1: # %if.end
 ; CHECK-NEXT:    movzbl %dil, %eax
 ; CHECK-NEXT:    orq $-2, %rax
 ; CHECK-NEXT:    retq
 entry:
   %tobool = icmp eq i32 %j, 0
   br i1 %tobool, label %if.end, label %if.then
 
 if.then:                                          ; preds = %entry

test/CodeGen/X86/block-placement.ll

exit:
   ret i32 %sum
 }
 
 define void @unnatural_cfg1() {
 ; Test that we can handle a loop with an inner unnatural loop at the end of
 ; a function. This is a gross CFG reduced out of the single source GCC.
 ; CHECK-LABEL: unnatural_cfg1
 ; CHECK: %entry
-; CHECK: %loop.body1
+; CHECK: %loop.header
 ; CHECK: %loop.body2
 ; CHECK: %loop.body3
 
 entry:
   br label %loop.header
 
 loop.header:
   br label %loop.body1

 ; Test that when we encounter an unnatural CFG structure after having formed
 ; a chain for an inner loop which happened to be laid out backwards we don't
 ; attempt to merge onto the wrong end of the inner loop just because we find it
 ; first. This was reduced from a crasher in GCC's single source.
 ;
 ; CHECK-LABEL: test_unnatural_cfg_backwards_inner_loop
 ; CHECK: %entry
 ; CHECK: %loop2b
-; CHECK: %loop1
+; CHECK: %loop3
 
 entry:
   br i1 undef, label %loop2a, label %body
 
 body:
   br label %loop2a
 
 loop1:

test/CodeGen/X86/hoist-spill.ll

for.cond:                                         ; preds = %for.inc14, %entry
   %smax = select i1 %tmp11, i32 %indvars.iv30, i32 0
   %tmp12 = zext i32 %smax to i64
   %sub = sub nsw i32 %p1, %c.0
   %cmp = icmp sgt i32 %sub, 0
   %sub. = select i1 %cmp, i32 %sub, i32 0
   %cmp326 = icmp sgt i32 %k.0, %p1
   br i1 %cmp326, label %for.cond4.preheader, label %for.body.preheader
 
-for.body.preheader:                               ; preds = %for.cond
-  br label %for.body
-
 for.cond4.preheader:                              ; preds = %for.body, %for.cond
   %k.1.lcssa = phi i32 [ %k.0, %for.cond ], [ %add, %for.body ]
   %cmp528 = icmp sgt i32 %sub., %p1
   br i1 %cmp528, label %for.inc14, label %for.body6.preheader
 
 for.body6.preheader:                              ; preds = %for.cond4.preheader
   br i1 undef, label %for.body6, label %min.iters.checked
 
vector.body:                                      ; preds = %vector.body, %vector.body.preheader.split
   %tmp17 = bitcast i32* %tmp16 to <4 x i32>*
   store <4 x i32> %wide.load.1, <4 x i32>* %tmp17, align 4
   %index.next.3 = add i64 %index, 32
   br i1 undef, label %middle.block, label %vector.body
 
 middle.block:                                     ; preds = %vector.body, %vector.body.preheader.split
   br i1 undef, label %for.inc14, label %for.body6
 
+for.body.preheader:                               ; preds = %for.cond
+  br label %for.body
+
 for.body:                                         ; preds = %for.body, %for.body.preheader
   %k.127 = phi i32 [ %k.0, %for.body.preheader ], [ %add, %for.body ]
   %add = add nsw i32 %k.127, 1
   %tmp18 = load i32, i32* undef, align 4
   store i32 %tmp18, i32* @b, align 4
   br i1 undef, label %for.body, label %for.cond4.preheader
 
 for.body6:                                        ; preds = %for.body6, %middle.block, %vector.memcheck, %min.iters.checked, %for.body6.preheader

test/CodeGen/X86/ins_subreg_coalesce-1.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-- -mattr=-bmi | FileCheck %s
 
 define fastcc i32 @t() nounwind  {
 ; CHECK-LABEL: t:
-; CHECK:       # %bb.0: # %walkExprTree.exit
+; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    movzwl 0, %eax
 ; CHECK-NEXT:    orl $2, %eax
 ; CHECK-NEXT:    movw %ax, 0
 ; CHECK-NEXT:    shrl $3, %eax
 ; CHECK-NEXT:    andl $1, %eax
 ; CHECK-NEXT:    retl
 entry:
   br i1 false, label %UnifiedReturnBlock, label %bb4

test/CodeGen/X86/memcmp-mergeexpand.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown-unknown               | FileCheck %s --check-prefix=X86
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown             | FileCheck %s --check-prefix=X64
 
 ; This tests interaction between MergeICmp and ExpandMemCmp.
 
 %"struct.std::pair" = type { i32, i32 }
 
 define zeroext i1 @opeq1(
 ; X86-LABEL: opeq1:
-; X86:       # %bb.0: # %opeq1.exit
+; X86:       # %bb.0: # %entry
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl (%ecx), %edx
 ; X86-NEXT:    movl 4(%ecx), %ecx
 ; X86-NEXT:    xorl (%eax), %edx
 ; X86-NEXT:    xorl 4(%eax), %ecx
 ; X86-NEXT:    orl %edx, %ecx
 ; X86-NEXT:    sete %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: opeq1:
-; X64:       # %bb.0: # %opeq1.exit
+; X64:       # %bb.0: # %entry
 ; X64-NEXT:    movq (%rdi), %rax
 ; X64-NEXT:    cmpq (%rsi), %rax
 ; X64-NEXT:    sete %al
 ; X64-NEXT:    retq
   %"struct.std::pair"* nocapture readonly dereferenceable(8) %a,
   %"struct.std::pair"* nocapture readonly dereferenceable(8) %b) local_unnamed_addr #0 {
 entry:
   %first.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %a, i64 0, i32 0

test/CodeGen/X86/pr32108.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
 
 define void @pr32108() {
 ; CHECK-LABEL: pr32108:
-; CHECK:       # %bb.0: # %CF257
+; CHECK:       # %bb.0: # %BB
 ; CHECK-NEXT:    movb $0, -{{[0-9]+}}(%rsp)
 ; CHECK-NEXT:    .p2align 4, 0x90
 ; CHECK-NEXT:  .LBB0_1: # %CF244
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    jmp .LBB0_1
 BB:
   %Cmp45 = icmp slt <4 x i32> undef, undef
   br label %CF243

test/CodeGen/X86/setcc-lowering.ll

entry:
   %1 = icmp eq <8 x i23> %0, zeroinitializer
   %2 = or <8 x i1> %1, <i1 true, i1 true, i1 true, i1 true, i1 false, i1 false, i1 false, i1 false>
   %3 = sext <8 x i1> %2 to <8 x i16>
   ret <8 x i16> %3
 }
 
 define void @pr26232(i64 %a, <16 x i1> %b) {
 ; AVX-LABEL: pr26232:
-; AVX:       # %bb.0: # %for_loop599.preheader
+; AVX:       # %bb.0: # %allocas
 ; AVX-NEXT:    vpxor %xmm1, %xmm1, %xmm1
 ; AVX-NEXT:    vmovdqa {{.*#+}} xmm2 = [128,128,128,128,128,128,128,128,128,128,128,128,128,128,128,128]
 ; AVX-NEXT:    .p2align 4, 0x90
 ; AVX-NEXT:  .LBB1_1: # %for_loop599
 ; AVX-NEXT:    # =>This Inner Loop Header: Depth=1
 ; AVX-NEXT:    xorl %eax, %eax
 ; AVX-NEXT:    cmpq $65536, %rdi # imm = 0x10000
 ; AVX-NEXT:    setl %al
 ; AVX-NEXT:    vmovd %eax, %xmm3
 ; AVX-NEXT:    vpshufb %xmm1, %xmm3, %xmm3
 ; AVX-NEXT:    vpand %xmm0, %xmm3, %xmm3
 ; AVX-NEXT:    vpsllw $7, %xmm3, %xmm3
 ; AVX-NEXT:    vpand %xmm2, %xmm3, %xmm3
 ; AVX-NEXT:    vpmovmskb %xmm3, %eax
 ; AVX-NEXT:    testw %ax, %ax
 ; AVX-NEXT:    jne .LBB1_1
 ; AVX-NEXT:  # %bb.2: # %for_exit600
 ; AVX-NEXT:    retq
 ;
 ; KNL-32-LABEL: pr26232:
-; KNL-32:       # %bb.0: # %for_loop599.preheader
+; KNL-32:       # %bb.0: # %allocas
 ; KNL-32-NEXT:    pushl %esi
 ; KNL-32-NEXT:    .cfi_def_cfa_offset 8
 ; KNL-32-NEXT:    .cfi_offset %esi, -8
 ; KNL-32-NEXT:    vpmovsxbd %xmm0, %zmm0
 ; KNL-32-NEXT:    vpslld $31, %zmm0, %zmm0
 ; KNL-32-NEXT:    vptestmd %zmm0, %zmm0, %k0
 ; KNL-32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; KNL-32-NEXT:    movl {{[0-9]+}}(%esp), %ecx

test/CodeGen/X86/split-store.ll

; CHECK-NEXT:    retq
   %t3 = zext i1 %tmp1 to i2
   %t4 = or i2 %t2, %t3
   store i2 %t4, i2* %ref.tmp, align 1
   ret void
 }
 
 define void @mbb_int32_float_pair(i32 %tmp1, float %tmp2, i64* %ref.tmp) {
 ; CHECK-LABEL: mbb_int32_float_pair:
-; CHECK:       # %bb.0: # %next
+; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    movl %edi, (%rsi)
 ; CHECK-NEXT:    movss %xmm0, 4(%rsi)
 ; CHECK-NEXT:    retq
 entry:
   %t0 = bitcast float %tmp2 to i32
   br label %next
 next:
   %t1 = zext i32 %t0 to i64
   %t2 = shl nuw i64 %t1, 32
   %t3 = zext i32 %tmp1 to i64
   %t4 = or i64 %t2, %t3
   store i64 %t4, i64* %ref.tmp, align 8
   ret void
 }
 
 define void @mbb_int32_float_multi_stores(i32 %tmp1, float %tmp2, i64* %ref.tmp, i64* %ref.tmp1, i1 %cmp) {
 ; CHECK-LABEL: mbb_int32_float_multi_stores:
-; CHECK:       # %bb.0: # %bb1
+; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    movl %edi, (%rsi)
 ; CHECK-NEXT:    movss %xmm0, 4(%rsi)
 ; CHECK-NEXT:    testb $1, %cl
 ; CHECK-NEXT:    je .LBB15_2
 ; CHECK-NEXT:  # %bb.1: # %bb2
 ; CHECK-NEXT:    movl %edi, (%rdx)
 ; CHECK-NEXT:    movss %xmm0, 4(%rdx)
 ; CHECK-NEXT:  .LBB15_2: # %exitbb

test/CodeGen/X86/tail-dup-merge-loop-headers.ll

 ; RUN: llc -O2 -o - %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind uwtable
 ; CHECK-LABEL: tail_dup_merge_loops
 ; CHECK: # %entry
 ; CHECK-NOT: # %{{[a-zA-Z_]+}}
 ; CHECK: # %inner_loop_exit
 ; CHECK-NOT: # %{{[a-zA-Z_]+}}
 ; CHECK: # %inner_loop_latch
 ; CHECK-NOT: # %{{[a-zA-Z_]+}}
-; CHECK: # %inner_loop_test
+; CHECK: # %inner_loop_top
 ; CHECK-NOT: # %{{[a-zA-Z_]+}}
 ; CHECK: # %exit
 define void @tail_dup_merge_loops(i32 %a, i8* %b, i8* %c) local_unnamed_addr #0 {
 entry:
   %notlhs674.i = icmp eq i32 %a, 0
   br label %outer_loop_top
 
 outer_loop_top:                         ; preds = %inner_loop_exit, %entry

test/DebugInfo/Generic/sunk-compare.ll

 ; RUN: opt -S -codegenprepare < %s | FileCheck %s
 ;
 ; This test case has been generated by hand but is inspired by the
 ; observation that compares that are sunk into the basic blocks where
 ; their results are used did not retain their debug locs. This caused
 ; sample profiling to attribute code to the wrong source lines. 
 ;
 ; We check that the compare instruction retains its debug loc after 
 ; it is sunk into other.bb by the codegen prepare pass.
 ; 
-; CHECK:       other.bb:
+; CHECK:       entry:
 ; CHECK-NEXT:  icmp{{.*}}%x, 0, !dbg ![[MDHANDLE:[0-9]*]]
 ; CHECK:       ![[MDHANDLE]] = !DILocation(line: 2
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define i32 @_Z3fooii(i32 %x, i32 %y) !dbg !5 {
 entry:
   %cmp17 = icmp sgt i32 %x, 0, !dbg !6

test/Transforms/CodeGenPrepare/X86/computedgoto.ll

 exit:
   ret void
 }
 
 ; Make sure we do the right thing for cases where the indirectbr branches to
 ; the block it terminates.
 define void @loop(i64* nocapture readonly %p) {
 ; CHECK-LABEL: @loop(
-; CHECK-NEXT:  bb0.clone:
+; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[DOTSPLIT:%.*]]
 ; CHECK:       bb0:
 ; CHECK-NEXT:    br label [[DOTSPLIT]]
 ; CHECK:       .split:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i64 [ [[I_NEXT:%.*]], [[BB0:%.*]] ], [ 0, [[BB0_CLONE:%.*]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i64, i64* [[P:%.*]], i64 [[MERGE]]
 ; CHECK-NEXT:    store i64 [[MERGE]], i64* [[TMP0]], align 4
 ; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i64 [[MERGE]], 1

test/Transforms/CodeGenPrepare/basic.ll

 ; RUN: opt -codegenprepare -S < %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin10.0.0"
 
 ; CHECK-LABEL: @test1(
 ; objectsize should fold to a constant, which causes the branch to fold to an
 ; uncond branch. Next, we fold the control flow alltogether.
 ; rdar://8785296
 define i32 @test1(i8* %ptr) nounwind ssp noredzone align 2 {
 entry:
   %0 = tail call i64 @llvm.objectsize.i64(i8* %ptr, i1 false, i1 false)
   %1 = icmp ugt i64 %0, 3
   br i1 %1, label %T, label %trap
 
-; CHECK: T:
+; CHECK: entry:
 ; CHECK-NOT: br label %
 
 trap:                                             ; preds = %0, %entry
   tail call void @llvm.trap() noreturn nounwind
   unreachable
 
 T:
 ; CHECK: ret i32 4

test/Transforms/LoopSimplifyCFG/scev.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-simplifycfg -verify-scev < %s | FileCheck %s
 
 ; Verify that the scev information is still valid. Verification should not fail
 
 define void @t_run_test() {
 ; CHECK-LABEL: @t_run_test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[LOOP_PH:%.*]]
-; CHECK:       loop.ph:
-; CHECK-NEXT:    br label [[LOOP_BODY:%.*]]
-; CHECK:       loop.body:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[LOOP_PH]] ], [ [[INC:%.*]], [[LOOP_BODY]] ]
+; CHECK-NEXT:    br label %[[LOOP_PH:.*]]
+; CHECK:       [[LOOP_PH]]:
+; CHECK-NEXT:    br label %[[LOOP_BODY:.*]]
+; CHECK:       [[LOOP_BODY]]:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, %[[LOOP_PH]] ], [ [[INC:%.*]], %[[LOOP_BODY]] ]
 ; CHECK-NEXT:    [[INC]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC]], 10
-; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_BODY]], label [[EXIT:%.*]]
-; CHECK:       exit:
-; CHECK-NEXT:    br label [[LOOP_BODY2:%.*]]
-; CHECK:       loop.body2:
-; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, [[EXIT]] ], [ [[INC2:%.*]], [[LOOP_BODY2]] ]
+; CHECK-NEXT:    br i1 [[CMP]], label %[[LOOP_BODY]], label %[[EXIT:.*]]
+; CHECK:       [[EXIT]]:
+; CHECK-NEXT:    br label %[[LOOP_BODY2:.*]]
+; CHECK:       [[LOOP_BODY2]]:
+; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, %[[EXIT]] ], [ [[INC2:%.*]], %[[LOOP_BODY2]] ]
 ; CHECK-NEXT:    [[INC2]] = add i32 [[IV2]], 1
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[INC2]], 10
-; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP_BODY2]], label [[EXIT2:%.*]]
-; CHECK:       exit2:
+; CHECK-NEXT:    br i1 [[CMP2]], label %[[LOOP_BODY2]], label %[[EXIT2:.*]]
+; CHECK:       [[EXIT2]]:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %loop.ph
 
 loop.ph:
   br label %loop.header
 

test/Transforms/LoopStrengthReduce/ARM/2012-06-15-lsr-noaddrmode.ll

 
 @ncol = external global i32, align 4
 
 declare i32* @getptr() nounwind
 declare %s* @getstruct() nounwind
 
 ; CHECK: @main
 ; Check that the loop preheader contains no address computation.
-; CHECK: %end_of_chain
+; CHECK: %while.cond.i.i
 ; CHECK-NOT: add{{.*}}lsl
 ; CHECK: ldr{{.*}}lsl #2
 ; CHECK: ldr{{.*}}lsl #2
 define i32 @main() nounwind ssp {
 entry:
   %v0 = load i32, i32* @ncol, align 4
   %v1 = tail call i32* @getptr() nounwind
   %cmp10.i = icmp eq i32 %v0, 0

test/Transforms/LoopStrengthReduce/X86/2012-01-13-phielim.ll

while.end:                                        ; preds = %entry
   ret void
 }
 
 ; PR12898: SCEVExpander crash
 ; Test redundant phi elimination when the deleted phi's increment is
 ; itself a phi.
 ;
 ; CHECK: @test3
-; CHECK: %for.body3.lr.ph.us.i.loopexit
+; CHECK: %meshBB1
+; CHECK: %meshBB
 ; CHECK-NEXT: Parent Loop
 ; CHECK-NEXT: Inner Loop
 ; CHECK-NEXT: incq
 ; CHECK: testb
 ; CHECK: je
 ; CHECK: jmp
 define fastcc void @test3(double* nocapture %u) nounwind uwtable ssp {
 entry:

test/Transforms/SimpleLoopUnswitch/trivial-unswitch-iteration.ll

 ; RUN: opt -passes='loop(loop-instsimplify,simplify-cfg,unswitch),verify<loops>' -S < %s | FileCheck %s
 
 declare void @some_func() noreturn
 
 define i32 @test1(i32* %var, i1 %cond1, i1 %cond2) {
 ; CHECK-LABEL: @test1(
 entry:
   br label %loop_begin
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 %{{.*}}, label %entry.split, label %loop_exit.split
 ;
 ; CHECK:       entry.split:
 ; CHECK-NEXT:    br i1 %{{.*}}, label %entry.split.split, label %loop_exit
 ;
 ; CHECK:       entry.split.split:
-; CHECK-NEXT:    br label %do_something
+; CHECK-NEXT:    br label %loop_begin
 
 loop_begin:
   br i1 %cond1, label %continue, label %loop_exit ; first trivial condition
 
 continue:
   %var_val = load i32, i32* %var
   %var_cond = trunc i32 %var_val to i1
   %maybe_cond = select i1 %cond1, i1 %cond2, i1 %var_cond
   br i1 %maybe_cond, label %do_something, label %loop_exit ; second trivial condition
 
 do_something:
   call void @some_func() noreturn nounwind
   br label %loop_begin
-; CHECK:       do_something:
+; CHECK:       loop_begin:
 ; CHECK-NEXT:    call
-; CHECK-NEXT:    br label %do_something
+; CHECK-NEXT:    br label %loop_begin
 
 loop_exit:
   ret i32 0
 ; CHECK:       loop_exit:
 ; CHECK-NEXT:    br label %loop_exit.split
 ;
 ; CHECK:       loop_exit.split:
 ; CHECK-NEXT:    ret
-}
+}