Don't delete empty preheaders in CodeGenPrepare if it would create a critical edge

[tjablin]

Summary

Presently, CodeGenPrepare deletes all nearly empty (only phi and branch) basic blocks. This pass can delete loop preheaders which frequently creates critical edges. A preheader can be a convenient place to spill registers to the stack. If the entrance to a loop body is a critical edge, then spills may occur in the loop body rather than immediately before it. This patch protects loop preheaders from deletion in CodeGenPrepare even if they are nearly empty.

Since the patch alters the CFG, it affects a large number of test cases. In most cases, the changes are merely cosmetic (basic blocks have different names or instruction orders change slightly). I am somewhat concerned about the test/CodeGen/Mips/brdelayslot.ll test case. If the loop preheader is not deleted, then the MIPS backend does not take advantage of a branch delay slot. Consequently, I would like some close review by a MIPS expert.

The patch also partially subsumes D16893 from George Burgess IV. George correctly notes that CodeGenPrepare does not actually preserve the dominator tree. I think the dominator tree was usually not valid when CodeGenPrepare ran, but I am using LoopInfo to mark preheaders, so the dominator tree is now always valid before CodeGenPrepare.

[george.burgess.iv]

Sorry, I'm not familiar enough with LLVM to feel comfortable stamping this patch. That said, it looks sane to me, with two nits.

Thanks for doing this! :)

lib/CodeGen/CodeGenPrepare.cpp

372

Why can't we just do for (Loop *L : *LI)?

413

typo: "deleeted"

[tjablin]

Accidentally omitted code for iterating over inner loops. Fix spelling error.

[dsanders]

I am somewhat concerned about the test/CodeGen/Mips/brdelayslot.ll test case. If the loop preheader is not deleted, then the MIPS backend does not take advantage of a branch delay slot. Consequently, I would like some close review by a MIPS expert.

I see what's happening. Somehow the '%V0<def> = ADDiu %ZERO, 0' has appeared in both %entry and %for.body.preheader. It's then refusing to hoist the one in %for.body.preheader into %entry because this would move the instruction between the one in %entry and the live-in for %for.body.preheader (which contains %V0). It thinks this will change the value even though they both materialize zero into %V0 using the same instruction.

That's a weakness in our algorithm but I wonder why this patch duplicates the instruction. The one in %for.body.preheader presumably comes from the '%s.06 = phi i32 [ %add, %for.body ], [ 0, %for.body.preheader ]' in %for.body, but I can't explain the one in %entry and the delay slot filler would work without that one.

For reference, here's the IR I'm talking about above:

BB#0: derived from LLVM BB %entry
    Live Ins: %A0 %A1
        %vreg8<def> = COPY %A1; GPR32:%vreg8
        %vreg7<def> = COPY %A0; GPR32:%vreg7
        %vreg9<def> = ADDiu %ZERO, 0; GPR32:%vreg9
        BLEZ %vreg8, <BB#3>, %AT<imp-def,dead>; GPR32:%vreg8
        B <BB#1>, %AT<imp-def,dead>
    Successors according to CFG: BB#1(0x50000000 / 0x80000000 = 62.50%) BB#3(0x30000000 / 0x80000000 = 37.50%)

BB#1: derived from LLVM BB %for.body.preheader
    Predecessors according to CFG: BB#0
        %vreg10<def> = ADDiu %ZERO, 0; GPR32:%vreg10
    Successors according to CFG: BB#2(?%)

BB#2: derived from LLVM BB %for.body
    Predecessors according to CFG: BB#1 BB#2
        %vreg0<def> = PHI %vreg7, <BB#1>, %vreg5, <BB#2>; GPR32:%vreg0,%vreg7,%vreg5
        %vreg1<def> = PHI %vreg8, <BB#1>, %vreg4, <BB#2>; GPR32:%vreg1,%vreg8,%vreg4
        %vreg2<def> = PHI %vreg10, <BB#1>, %vreg3, <BB#2>; GPR32:%vreg2,%vreg10,%vreg3
        %vreg11<def> = LW %vreg0, 0; mem:LD4[%lsr.iv1] GPR32:%vreg11,%vreg0
        %vreg3<def> = ADDu %vreg11<kill>, %vreg2; GPR32:%vreg3,%vreg11,%vreg2
        %vreg5<def> = ADDiu %vreg0, 4; GPR32:%vreg5,%vreg0
        %vreg4<def> = ADDiu %vreg1, -1; GPR32:%vreg4,%vreg1
        BNE %vreg4, %ZERO, <BB#2>, %AT<imp-def,dead>; GPR32:%vreg4
        B <BB#3>, %AT<imp-def,dead>
    Successors according to CFG: BB#3(0x04000000 / 0x80000000 = 3.12%) BB#2(0x7c000000 / 0x80000000 = 96.88%)

BB#3: derived from LLVM BB %for.end
    Predecessors according to CFG: BB#0 BB#2
        %vreg6<def> = PHI %vreg9, <BB#0>, %vreg3, <BB#2>; GPR32:%vreg6,%vreg9,%vreg3
        %V0<def> = COPY %vreg6; GPR32:%vreg6
        RetRA %V0<imp-use>

test/CodeGen/Mips/brdelayslot.ll

2–6

On each of these, the preheader contains a duplicate of the 'addiu $2, $zero, 0' at the end of the previous bb.

[kbarton]

LGTM.
Note that the only test case I looked at in detail was dont-remove-empty-preheader.ll

lib/CodeGen/CodeGenPrepare.cpp

372

This wasn't immediately obvious to me either.
This is needed because of nested loops. The begin() and end() iterators for LoopInfo just contain the topmost loops for a given depth (nest level). For each loop in the list you need to:

1. Check its preheader;
2. Add all of the loops contained within it. Line 374 handles adding the topmost loops within the current loop body.

[cycheng]

On behalf of Tom.
Committed revision: r265397

lib/CodeGen/CodeGenPrepare.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
static cl::opt<bool> DisableExtLdPromotion(
     cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
              "CodeGenPrepare"));
 
 static cl::opt<bool> StressExtLdPromotion(
     "stress-cgp-ext-ld-promotion", cl::Hidden, cl::init(false),
     cl::desc("Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
              "optimization in CodeGenPrepare"));
 
+static cl::opt<bool> DisablePreheaderProtect(
+    "disable-preheader-prot", cl::Hidden, cl::init(false),
+    cl::desc("Disable protection against removing loop preheaders"));
+
 namespace {
 typedef SmallPtrSet<Instruction *, 16> SetOfInstrs;
 typedef PointerIntPair<Type *, 1, bool> TypeIsSExt;
 typedef DenseMap<Instruction *, TypeIsSExt> InstrToOrigTy;
 class TypePromotionTransaction;
 
   class CodeGenPrepare : public FunctionPass {
     const TargetMachine *TM;
     const TargetLowering *TLI;
     const TargetTransformInfo *TTI;
     const TargetLibraryInfo *TLInfo;
+    const LoopInfo *LI;
 
     /// As we scan instructions optimizing them, this is the next instruction
     /// to optimize. Transforms that can invalidate this should update it.
     BasicBlock::iterator CurInstIterator;
 
     /// Keeps track of non-local addresses that have been sunk into a block.
     /// This allows us to avoid inserting duplicate code for blocks with
     /// multiple load/stores of the same address.
explicit CodeGenPrepare(const TargetMachine *TM = nullptr)
         : FunctionPass(ID), TM(TM), TLI(nullptr), TTI(nullptr), DL(nullptr) {
         initializeCodeGenPreparePass(*PassRegistry::getPassRegistry());
       }
     bool runOnFunction(Function &F) override;
 
     const char *getPassName() const override { return "CodeGen Prepare"; }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.addPreserved<DominatorTreeWrapperPass>();
+      // FIXME: When we can selectively preserve passes, preserve the domtree.
       AU.addRequired<TargetLibraryInfoWrapperPass>();
       AU.addRequired<TargetTransformInfoWrapperPass>();
+      AU.addRequired<LoopInfoWrapperPass>();
     }
 
   private:
     bool eliminateFallThrough(Function &F);
     bool eliminateMostlyEmptyBlocks(Function &F);
     bool canMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
     void eliminateMostlyEmptyBlock(BasicBlock *BB);
     bool optimizeBlock(BasicBlock &BB, bool& ModifiedDT);
bool CodeGenPrepare::runOnFunction(Function &F) {
   InsertedInsts.clear();
   PromotedInsts.clear();
 
   ModifiedDT = false;
   if (TM)
     TLI = TM->getSubtargetImpl(F)->getTargetLowering();
   TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
+  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   OptSize = F.optForSize();
 
   /// This optimization identifies DIV instructions that can be
   /// profitably bypassed and carried out with a shorter, faster divide.
   if (!OptSize && TLI && TLI->isSlowDivBypassed()) {
     const DenseMap<unsigned int, unsigned int> &BypassWidths =
        TLI->getBypassSlowDivWidths();
     BasicBlock* BB = &*F.begin();
bool CodeGenPrepare::eliminateFallThrough(Function &F) {
   return Changed;
 }
 
 /// Eliminate blocks that contain only PHI nodes, debug info directives, and an
 /// unconditional branch. Passes before isel (e.g. LSR/loopsimplify) often split
 /// edges in ways that are non-optimal for isel. Start by eliminating these
 /// blocks so we can split them the way we want them.
 bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) {
+  SmallPtrSet<BasicBlock *, 16> Preheaders;
+  SmallVector<Loop *, 16> LoopList(LI->begin(), LI->end());
+  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;
   // Note that this intentionally skips the entry block.
   for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
     BasicBlock *BB = &*I++;
 
     // If this block doesn't end with an uncond branch, ignore it.
     BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
     if (!BI || !BI->isUnconditional())
for (Function::iterator I = std::next(F.begin()), E = F.end(); I != E;) {
     // Do not break infinite loops.
     BasicBlock *DestBB = BI->getSuccessor(0);
     if (DestBB == BB)
       continue;
 
     if (!canMergeBlocks(BB, DestBB))
       continue;
 
+    // Do not delete loop preheaders if doing so would create a critical edge.
+    // Loop preheaders can be good locations to spill registers. If the
+    // preheader is deleted and we create a critical edge, registers may be
+    // spilled in the loop body instead.
+    if (!DisablePreheaderProtect && Preheaders.count(BB) &&
+        !(BB->getSinglePredecessor() && BB->getSinglePredecessor()->getSingleSuccessor()))
+     continue;
+
     eliminateMostlyEmptyBlock(BB);
     MadeChange = true;
   }
   return MadeChange;
 }
 
 /// Return true if we can merge BB into DestBB if there is a single
 /// unconditional branch between them, and BB contains no other non-phi

test/CodeGen/AArch64/arm64-shrink-wrapping.ll

 ;
 ; Store %a in the alloca.
 ; CHECK: stur w0, {{\[}}[[SAVE_SP]], #-4]
 ; Set the alloca address in the second argument.
 ; CHECK-NEXT: sub x1, [[SAVE_SP]], #4
 ; Set the first argument to zero.
 ; CHECK-NEXT: mov w0, wzr
 ; CHECK-NEXT: bl _doSomething
-; 
+;
 ; Without shrink-wrapping, epilogue is in the exit block.
 ; DISABLE: [[EXIT_LABEL]]:
 ; Epilogue code.
 ; CHECK-NEXT: mov sp, [[SAVE_SP]]
 ; CHECK-NEXT: ldp [[SAVE_SP]], [[CSR]], [sp], #16
 ;
 ; With shrink-wrapping, exit block is a simple return.
 ; ENABLE: [[EXIT_LABEL]]:

 ;
 ; ENABLE: cbz w0, [[ELSE_LABEL:LBB[0-9_]+]]
 ;
 ; Prologue code.
 ; CHECK: sub sp, sp, #16
 ; DISABLE: cbz w0, [[ELSE_LABEL:LBB[0-9_]+]]
 ;
 ; Sum is merged with the returned register.
-; CHECK: mov [[SUM:w0]], wzr
-; CHECK-NEXT: add [[VA_BASE:x[0-9]+]], sp, #16
+; CHECK: add [[VA_BASE:x[0-9]+]], sp, #16
 ; CHECK-NEXT: str [[VA_BASE]], [sp, #8]
 ; CHECK-NEXT: cmp w1, #1
 ; CHECK-NEXT: b.lt [[IFEND_LABEL:LBB[0-9_]+]]
+; CHECK: mov [[SUM:w0]], wzr
 ;
 ; CHECK: [[LOOP_LABEL:LBB[0-9_]+]]: ; %for.body
 ; CHECK: ldr [[VA_ADDR:x[0-9]+]], [sp, #8]
 ; CHECK-NEXT: add [[NEXT_VA_ADDR:x[0-9]+]], [[VA_ADDR]], #8
 ; CHECK-NEXT: str [[NEXT_VA_ADDR]], [sp, #8]
 ; CHECK-NEXT: ldr [[VA_VAL:w[0-9]+]], {{\[}}[[VA_ADDR]]]
 ; CHECK-NEXT: add [[SUM]], [[SUM]], [[VA_VAL]]
 ; CHECK-NEXT: sub w1, w1, #1
 ; CHECK-NEXT: cbnz w1, [[LOOP_LABEL]]
 ;
-; DISABLE-NEXT: b [[IFEND_LABEL]]
+; DISABLE-NEXT: b
 ; DISABLE: [[ELSE_LABEL]]: ; %if.else
 ; DISABLE: lsl w0, w1, #1
 ;
+; ENABLE: [[ELSE_LABEL]]: ; %if.else
+; ENABLE: lsl w0, w1, #1
+; ENABLE-NEXT: ret
+;
 ; CHECK: [[IFEND_LABEL]]:
 ; Epilogue code.
 ; CHECK: add sp, sp, #16
 ; CHECK-NEXT: ret
-;
-; ENABLE: [[ELSE_LABEL]]: ; %if.else
-; ENABLE: lsl w0, w1, #1
-; ENABLE-NEXT: ret
 define i32 @variadicFunc(i32 %cond, i32 %count, ...) #0 {
 entry:
   %ap = alloca i8*, align 8
   %tobool = icmp eq i32 %cond, 0
   br i1 %tobool, label %if.else, label %if.then
 
 if.then:                                          ; preds = %entry
   %ap1 = bitcast i8** %ap to i8*

test/CodeGen/ARM/code-placement.ll

 ; RUN: llc < %s -mtriple=armv7-apple-darwin | FileCheck %s
 ; PHI elimination shouldn't break backedge.
 ; rdar://8263994
 
 %struct.list_data_s = type { i16, i16 }
 %struct.list_head = type { %struct.list_head*, %struct.list_data_s* }
 
 define arm_apcscc %struct.list_head* @t1(%struct.list_head* %list) nounwind {
 entry:
 ; CHECK-LABEL: t1:
   %0 = icmp eq %struct.list_head* %list, null
   br i1 %0, label %bb2, label %bb
 
 bb:
-; CHECK: LBB0_1:
-; CHECK: bne LBB0_1
-; CHECK-NOT: b LBB0_1
+; CHECK: LBB0_2:
+; CHECK: bne LBB0_2
+; CHECK-NOT: b LBB0_2
 ; CHECK: bx lr
   %list_addr.05 = phi %struct.list_head* [ %2, %bb ], [ %list, %entry ]
   %next.04 = phi %struct.list_head* [ %list_addr.05, %bb ], [ null, %entry ]
   %1 = getelementptr inbounds %struct.list_head, %struct.list_head* %list_addr.05, i32 0, i32 0
   %2 = load %struct.list_head*, %struct.list_head** %1, align 4
   store %struct.list_head* %next.04, %struct.list_head** %1, align 4
   %3 = icmp eq %struct.list_head* %2, null
   br i1 %3, label %bb2, label %bb

test/CodeGen/ARM/sjlj-prepare-critical-edge.ll

 ; %call.i.i.i14.i.i follows the instruction that saves the value to the stack in
 ; basic block %entry.do.body.i.i.i_crit_edge.
 ; Previously, DemoteRegToStack would insert a load instruction into the entry
 ; block to reload %call.i.i.i14.i.i before the phi instruction (%0) in block
 ; %do.body.i.i.i.
 
 ; CHECK-LABEL: __Z4foo1c:
 ; CHECK: blx __Znwm
-; CHECK: {{.*}}@ %entry.do.body.i.i.i_crit_edge
+; CHECK: {{.*}}@ %do.body.i.i.i.preheader
 ; CHECK: str r0, [sp, [[OFFSET:#[0-9]+]]]
 ; CHECK: {{.*}}@ %do.body.i.i.i
 ; CHECK: ldr [[R0:r[0-9]+]], [sp, [[OFFSET]]]
 ; CHECK: cbz [[R0]]
 
 %"class.std::__1::basic_string" = type { %"class.std::__1::__compressed_pair" }
 %"class.std::__1::__compressed_pair" = type { %"class.std::__1::__libcpp_compressed_pair_imp" }
 %"class.std::__1::__libcpp_compressed_pair_imp" = type { %"struct.std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::__rep" }

test/CodeGen/Generic/dont-remove-empty-preheader.ll

+; RUN: opt -codegenprepare -S < %s | FileCheck %s
+; CHECK: for.body.preheader
+
+@N = common global i32 0, align 4
+@E = common global i8** null, align 8
+@B = common global i8** null, align 8
+
+; Function Attrs: nounwind
+define i32 @foo() {
+entry:
+  %0 = load i32, i32* @N, align 4
+  %1 = load i8**, i8*** @E, align 8
+  %2 = load i8**, i8*** @B, align 8
+  %cmp7 = icmp eq i8** %2, %1
+  br i1 %cmp7, label %for.cond.cleanup, label %for.body.preheader
+
+for.body.preheader:                               ; preds = %entry
+  br label %for.body
+
+for.cond.cleanup.loopexit:                        ; preds = %for.body
+  %add.lcssa = phi i32 [ %add, %for.body ]
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
+  %n.0.lcssa = phi i32 [ %0, %entry ], [ %add.lcssa, %for.cond.cleanup.loopexit ]
+  ret i32 %n.0.lcssa
+
+for.body:                                         ; preds = %for.body.preheader, %for.body
+  %I.09 = phi i8** [ %incdec.ptr, %for.body ], [ %2, %for.body.preheader ]
+  %n.08 = phi i32 [ %add, %for.body ], [ %0, %for.body.preheader ]
+  %3 = load i8*, i8** %I.09, align 8
+  %call = tail call i32 @map(i8* %3)
+  %add = add nsw i32 %call, %n.08
+  %incdec.ptr = getelementptr inbounds i8*, i8** %I.09, i64 1
+  %cmp = icmp eq i8** %incdec.ptr, %1
+  br i1 %cmp, label %for.cond.cleanup.loopexit, label %for.body
+}
+
+declare i32 @map(i8*)

test/CodeGen/Mips/brdelayslot.ll

 ; RUN: llc -march=mipsel -O0 < %s | FileCheck %s -check-prefix=None
 ; RUN: llc -march=mipsel < %s | FileCheck %s -check-prefix=Default
 ; RUN: llc -march=mipsel -O1 -relocation-model=static < %s | \
 ; RUN: FileCheck %s -check-prefix=STATICO1
 ; RUN: llc -march=mipsel -disable-mips-df-forward-search=false \
 ; RUN: -relocation-model=static < %s | FileCheck %s -check-prefix=FORWARD
 ; RUN: llc -march=mipsel -disable-mips-df-backward-search \
-; RUN: -disable-mips-df-succbb-search=false < %s | \
+; RUN: -disable-mips-df-succbb-search=false -disable-preheader-prot=true < %s | \
 ; RUN: FileCheck %s -check-prefix=SUCCBB
 
 define void @foo1() nounwind {
 entry:
-; Default:     jalr 
-; Default-NOT: nop 
-; Default:     jr 
+; Default:     jalr
+; Default-NOT: nop
+; Default:     jr
 ; Default-NOT: nop
 ; Default:     .end
-; None: jalr 
-; None: nop 
-; None: jr 
+; None: jalr
+; None: nop
+; None: jr
 ; None: nop
 ; None: .end
 
   tail call void @foo2(i32 3) nounwind
   ret void
 }
 
 declare void @foo2(i32)

test/CodeGen/Mips/prevent-hoisting.ll

 ; RUN: llc -march=mipsel -O3 < %s | FileCheck %s
 
 
 ; MIPS direct branches implicitly define register $at. This test makes sure that
 ; code hoisting optimization (which moves identical instructions at the start of
 ; two basic blocks to the common predecessor block) takes this into account and
 ; doesn't move definition of $at to the predecessor block (which would make $at
 ; live-in at the start of successor block).
 
 
 ; CHECK-LABEL: readLumaCoeff8x8_CABAC
 
 ; The check for first "addiu" instruction is added so that we can match the correct "b" instruction.
-; CHECK:           addiu ${{[0-9]+}}, $zero, -1
+; CHECK:           andi
 ; CHECK:           b $[[BB0:BB[0-9_]+]]
-; CHECK-NEXT:      addiu ${{[0-9]+}}, $zero, 0
+; CHECK-NEXT:      sll
 
 ; Check that at the start of a fallthrough block there is a instruction that writes to $1.
-; CHECK-NEXT:  {{BB[0-9_#]+}}: 
+; CHECK-NEXT:  {{BB[0-9_#]+}}:
 ; CHECK-NEXT:      lw      $[[R1:[0-9]+]], %got(assignSE2partition)($[[R2:[0-9]+]])
 ; CHECK-NEXT:      sll $1, $[[R0:[0-9]+]], 4
 
 ; Check that identical instructions are at the start of a target block.
 ; CHECK:       [[BB0]]:
 ; CHECK-NEXT:      lw      $[[R1]], %got(assignSE2partition)($[[R2]])
 ; CHECK-NEXT:      sll $1, $[[R0]], 4
 

test/CodeGen/X86/2011-09-14-valcoalesce.ll

 ; Prior to fixing PR10920 401.bzip miscompile, the coalescer would
 ; consider vreg1 and vreg27 to be copies of the same value. It would
 ; then remove one of the critical edge copes, which cannot safely be removed.
 
 ; There are two obvious ways the register-allocator could go here, either
 ; reusing the pre-addition register later, or the post-addition one. Currently,
 ; it does the latter, so we check:
 
-; CHECK: # %while.body85.i
+; CHECK: # %while.body85.i{{$}}
 ; CHECK-NOT: # %
 ; CHECK-NOT: add
 ; CHECK: movl %[[POSTR:e[abcdxi]+]], %[[PRER:e[abcdxi]+]]
 ; CHECK: addl %{{.*}}, %[[POSTR]]
 ; CHECK: # %while.end.i
 ; CHECK-NOT: movl %[[POSTR]]
 ; CHECK: # %land.lhs.true.i
 ; CHECK-NOT: movl %[[POSTR]]

test/CodeGen/X86/block-placement.ll

 define void @test_unnatural_cfg_backwards_inner_loop() {
 ; 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: test_unnatural_cfg_backwards_inner_loop
 ; CHECK: %entry
-; CHECK: [[BODY:# BB#[0-9]+]]:
 ; CHECK: %loop2b
 ; CHECK: %loop1
-; CHECK: %loop2a
 
 entry:
   br i1 undef, label %loop2a, label %body
 
 body:
   br label %loop2a
 
 loop1:

test/CodeGen/X86/break-false-dep.ll

; SSE: sqrtsd ([[A0]]), %xmm0
   %t = call double @llvm.sqrt.f64(double %z)
   ret double %t
 }
 
 declare float @llvm.sqrt.f32(float)
 declare double @llvm.sqrt.f64(double)
 
 ; SSE-LABEL: loopdep1
-; SSE: for.body
+; SSE: for.body{{$}}
 ;
 ; This loop contains two cvtsi2ss instructions that update the same xmm
 ; register.  Verify that the execution dependency fix pass breaks those
 ; dependencies by inserting xorps instructions.
 ;
 ; If the register allocator chooses different registers for the two cvtsi2ss
 ; instructions, they are still dependent on themselves.
 ; SSE: xorps [[XMM1:%xmm[0-9]+]]
loop:
   %exitcond = icmp eq i64 %inc, 156250000
   br i1 %exitcond, label %ret, label %loop
 ret:
   ret i64 %s2
 }
 
 ; This loop contains a cvtsi2sd instruction that has a loop-carried
 ; false dependency on an xmm that is modified by other scalar instructions
-; that follow it in the loop. Additionally, the source of convert is a 
+; that follow it in the loop. Additionally, the source of convert is a
 ; memory operand. Verify the execution dependency fix pass breaks this
 ; dependency by inserting a xor before the convert.
 @x = common global [1024 x double] zeroinitializer, align 16
 @y = common global [1024 x double] zeroinitializer, align 16
 @z = common global [1024 x double] zeroinitializer, align 16
 @w = common global [1024 x double] zeroinitializer, align 16
 @v = common global [1024 x i32] zeroinitializer, align 16
 

test/CodeGen/X86/lsr-static-addr.ll

 ; RUN: llc -march=x86-64 -mcpu=generic -mtriple=x86_64-unknown-linux-gnu -relocation-model=static -asm-verbose=false < %s | FileCheck %s
 ; RUN: llc -march=x86-64 -mcpu=atom -mtriple=x86_64-unknown-linux-gnu -relocation-model=static -asm-verbose=false < %s | FileCheck -check-prefix=ATOM %s
 
 ; CHECK: xorl  %eax, %eax
 ; CHECK: movsd .LCPI0_0(%rip), %xmm0
 ; CHECK: align
 ; CHECK-NEXT: BB0_2:
 ; CHECK-NEXT: movsd A(,%rax,8)
 ; CHECK-NEXT: mulsd
 ; CHECK-NEXT: movsd
 ; CHECK-NEXT: incq %rax
 
 
-; ATOM: xorl  %eax, %eax
 ; ATOM: movsd .LCPI0_0(%rip), %xmm0
+; ATOM: xorl  %eax, %eax
 ; ATOM: align
 ; ATOM-NEXT: BB0_2:
 ; ATOM-NEXT: movsd A(,%rax,8)
 ; ATOM-NEXT: mulsd
 ; ATOM-NEXT: movsd
 ; ATOM-NEXT: incq %rax
 
 @A = external global [0 x double]

test/CodeGen/X86/phi-immediate-factoring.ll

 ; REQUIRES: asserts
-; RUN: llc < %s -march=x86 -stats 2>&1 | grep "Number of blocks eliminated" | grep 6
+; RUN: llc < %s -disable-preheader-prot=true  -march=x86 -stats 2>&1 | grep "Number of blocks eliminated" | grep 6
+; RUN: llc < %s -disable-preheader-prot=false -march=x86 -stats 2>&1 | grep "Number of blocks eliminated" | grep 3
 ; PR1296
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64"
 target triple = "i686-apple-darwin8"
 
 define i32 @foo(i32 %A, i32 %B, i32 %C) nounwind {
 entry:
   switch i32 %A, label %out [

test/CodeGen/X86/phys_subreg_coalesce-2.ll

 ; RUN: llc < %s -march=x86 | FileCheck %s
 ; RUN: llc -no-phi-elim-live-out-early-exit -terminal-rule < %s -march=x86 | FileCheck %s
 ; PR2659
 
 define i32 @binomial(i32 %n, i32 %k) nounwind {
 entry:
   %cmp = icmp ugt i32 %k, %n    ; <i1> [#uses=1]
   br i1 %cmp, label %ifthen, label %forcond.preheader
 
 forcond.preheader:    ; preds = %entry
   %cmp44 = icmp eq i32 %k, 0    ; <i1> [#uses=1]
   br i1 %cmp44, label %afterfor, label %forbody
 
 ifthen:   ; preds = %entry
   ret i32 0
-; CHECK: forbody
+; CHECK: forbody{{$}}
 ; CHECK-NOT: mov
 forbody:    ; preds = %forbody, %forcond.preheader
   %indvar = phi i32 [ 0, %forcond.preheader ], [ %divisor.02, %forbody ]    ; <i32> [#uses=3]
   %accumulator.01 = phi i32 [ 1, %forcond.preheader ], [ %div, %forbody ]    ; <i32> [#uses=1]
   %divisor.02 = add i32 %indvar, 1    ; <i32> [#uses=2]
   %n.addr.03 = sub i32 %n, %indvar    ; <i32> [#uses=1]
   %mul = mul i32 %n.addr.03, %accumulator.01    ; <i32> [#uses=1]
   %div = udiv i32 %mul, %divisor.02   ; <i32> [#uses=2]
   %inc = add i32 %indvar, 2   ; <i32> [#uses=1]
   %cmp4 = icmp ugt i32 %inc, %k    ; <i1> [#uses=1]
   br i1 %cmp4, label %afterfor, label %forbody
 
 afterfor:   ; preds = %forbody, %forcond.preheader
   %accumulator.0.lcssa = phi i32 [ 1, %forcond.preheader ], [ %div, %forbody ]    ; <i32> [#uses=1]
   ret i32 %accumulator.0.lcssa
 }

test/CodeGen/X86/pr2659.ll

 ; CHECK: %forcond.preheader
 ; CHECK: movl $1
 ; CHECK-NOT: xorl
 ; CHECK-NOT: movl
 ; CHECK-NOT: LBB
 ; CHECK: je
 
 ; There should be no moves required in the for loop body.
-; CHECK: %forbody
+; CHECK: %forbody{{$}}
 ; CHECK-NOT: mov
 ; CHECK: jbe
 
 ifthen:         ; preds = %entry
   ret i32 0
 
 forbody:                ; preds = %forbody, %forcond.preheader
   %indvar = phi i32 [ 0, %forcond.preheader ], [ %divisor.02, %forbody ]                ; <i32> [#uses=3]

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) {
 ; KNL-32-LABEL: pr26232:
-; KNL-32:       # BB#0: # %for_test11.preheader
+; KNL-32:       # BB#0: # %for_loop599.preheader
 ; KNL-32-NEXT:    pushl %esi
 ; KNL-32-NEXT:  .Ltmp0:
 ; KNL-32-NEXT:    .cfi_def_cfa_offset 8
 ; KNL-32-NEXT:  .Ltmp1:
 ; KNL-32-NEXT:    .cfi_offset %esi, -8
 ; KNL-32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; KNL-32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; KNL-32-NEXT:    movw $-1, %dx

test/CodeGen/X86/sink-blockfreq.ll

-; RUN: llc -disable-machine-licm -machine-sink-bfi=true -mtriple=x86_64-apple-darwin < %s | FileCheck %s -check-prefix=MSINK_BFI
-; RUN: llc -disable-machine-licm -machine-sink-bfi=false -mtriple=x86_64-apple-darwin < %s | FileCheck %s -check-prefix=MSINK_NOBFI
+; RUN: llc -disable-preheader-prot=true -disable-machine-licm -machine-sink-bfi=true -mtriple=x86_64-apple-darwin < %s | FileCheck %s -check-prefix=MSINK_BFI
+; RUN: llc -disable-preheader-prot=true -disable-machine-licm -machine-sink-bfi=false -mtriple=x86_64-apple-darwin < %s | FileCheck %s -check-prefix=MSINK_NOBFI
 
 ; Test that by changing BlockFrequencyInfo we change the order in which
 ; machine-sink looks for sucessor blocks. By not using BFI, both G and B
 ; have the same loop depth and no instructions is sinked - B is selected but
 ; can't be used as to avoid breaking a non profitable critical edge. By using
 ; BFI, "mul" is sinked into the less frequent block G.
 define i32 @sink_freqinfo(i32 %a, i32 %b) nounwind uwtable ssp {
 ; MSINK_BFI-LABEL: sink_freqinfo

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

 ;
 ; CHECK: @test3
 ; CHECK: %for.body3.lr.ph.us.i.loopexit
 ; CHECK-NEXT: in Loop: Header
 ; CHECK-NEXT: incq
 ; CHECK-NEXT: %for.body3.us.i
 ; CHECK-NEXT: Inner Loop
 ; CHECK: testb
-; CHECK: jne
+; CHECK: je
 ; CHECK: jmp
 define fastcc void @test3(double* nocapture %u) nounwind uwtable ssp {
 entry:
   br i1 undef, label %meshBB1, label %meshBB5
 
 for.inc8.us.i:                                    ; preds = %for.body3.us.i
   br i1 undef, label %meshBB1, label %meshBB