Makes incremental dominator calculation in Loop Unroll pass

[sepavloff]

Summary

Loop unroller contains code that tries to update dominator tree on fly,
but eventually it calculates the tree from scratch for entire function.
If there are many loops in the function the compilation may be slow down.
Also inconsistent dominator info prevents from loop verification during
transformations.

This change implements incremental dominator tree update.

Part of this change (files Debug.h, LoopInfo.cpp and Dominators.cpp) is
independent from the rest of the patch, it implements changes required
to make testing of the dominator calculation.

Verifications of dominator tree and loop info are expensive operations
so they are disabled by default. They can be enabled by command line
options -verify-dom-info and -verify-loop-info. These options however
enable checks only in files Dominators.cpp and LoopInfo.cpp. If some
transformation changes dominaror tree and/or loop info, it would be
convenient to place similar checks to the files implementing the
transformation. By making corresponding flags global the verification
can be turned on optionally, even if expensive checks were not enabled
during build.

[mkuper]

This looks like it has a lot of overlap with D28073.
Please sync with Eli.

One thing D28073 doesn't do is handle peeling (I guess mostly because Eli has better things to do than fix my code :-) ), so that's a part of this patch we want regardless. Added a couple of comments on that.

lib/Transforms/Utils/LoopUnrollPeel.cpp

197

Why do you need the cast<Value>()?
Also, I'd a comment here that the reason VMap[IDom->getBlock()] is guaranteed to point to the right block is because the iteration order is RPO, so we've already made a copy of the IDom.

221

Do we really need to findNearestCommonDominator() here?
IIRC, we are guaranteed to be in loop-simplify form here, which means we have dedicated exit blocks. Can we figure out what the right IDom is without findNearestCommonDominator, a la D28073?

[efriedma]

Making a quick comparison between the two patches, the changes to LoopUnrollRuntime.cpp look almost identical. I think my version of the changes to the dominance calculation in LoopUnroll.cpp are more general. And obviously my changes to peeling don't actually dynamically update the domtree. I should probably merge the two loops in CloneLoopBlocks like this patch does.

Serge, do you have any other comments on my patch?

[sepavloff]

@mkuper - thank you for review and clarifications.

@efriedma - loop unrolling is a hot topic, things are changing too fast here, I somehow overlooked your patch, sorry. I agree, your treatment in LoopUnroll.cpp is more general, and don't think adding incremental update to LoopUnrollPeel.cpp will be a problem. The only advantage of my patch is testing, you are not going to add option unroll-peel-verify-domtree, right? :) But this is not related to loop unrolling, and probably deserves a separate patch. I think we should have possibility to provide verification flags to all tests in a test suite without need to alter the test sources. Other transformations may also gain from domtree and loop verification turned on.

[efriedma]

Committed my changes in r292447; please rebase and submit your changes to loop peeling on top of that.

include/llvm/Support/Debug.h

 #ifndef LLVM_SUPPORT_DEBUG_H
 #define LLVM_SUPPORT_DEBUG_H
 
 namespace llvm {
 
 class raw_ostream;
 
 #ifndef NDEBUG
-/// DebugFlag - This boolean is set to true if the '-debug' command line option
-/// is specified.  This should probably not be referenced directly, instead, use
-/// the DEBUG macro below.
-///
-extern bool DebugFlag;
 
 /// isCurrentDebugType - Return true if the specified string is the debug type
 /// specified on the command line, or if none was specified on the command line
 /// with the -debug-only=X option.
 ///
 bool isCurrentDebugType(const char *Type);
 
 /// setCurrentDebugType - Set the current debug type, as if the -debug-only=X

 
 #else
 #define isCurrentDebugType(X) (false)
 #define setCurrentDebugType(X)
 #define setCurrentDebugTypes(X, N)
 #define DEBUG_WITH_TYPE(TYPE, X) do { } while (false)
 #endif
 
+/// This boolean is set to true if the '-debug' command line option
+/// is specified.  This should probably not be referenced directly, instead, use
+/// the DEBUG macro below.
+///
+extern bool DebugFlag;
+
+/// \name Verification flags.
+///
+/// These flags turns on/off that are expensive and are turned off by default,
+/// unless macro EXPENSIVE_CHECKS is defined. The flags allow selectively
+/// turning the checks on without need to recompile.
+/// \{
+
+/// Enables verification of dominator trees.
+///
+extern bool VerifyDomInfo;
+
+/// Enables verification of loop info.
+///
+extern bool VerifyLoopInfo;
+
+///\}
+
 /// EnableDebugBuffering - This defaults to false.  If true, the debug
 /// stream will install signal handlers to dump any buffered debug
 /// output.  It allows clients to selectively allow the debug stream
 /// to install signal handlers if they are certain there will be no
 /// conflict.
 ///
 extern bool EnableDebugBuffering;
 

lib/Analysis/LoopInfo.cpp

 using namespace llvm;
 
 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
 template class llvm::LoopBase<BasicBlock, Loop>;
 template class llvm::LoopInfoBase<BasicBlock, Loop>;
 
 // Always verify loopinfo if expensive checking is enabled.
 #ifdef EXPENSIVE_CHECKS
-static bool VerifyLoopInfo = true;
+bool llvm::VerifyLoopInfo = true;
 #else
-static bool VerifyLoopInfo = false;
+bool llvm::VerifyLoopInfo = false;
 #endif
 static cl::opt<bool,true>
 VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
                 cl::desc("Verify loop info (time consuming)"));
 
 //===----------------------------------------------------------------------===//
 // Loop implementation
 //

lib/IR/Dominators.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GenericDomTreeConstruction.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 using namespace llvm;
 
 // Always verify dominfo if expensive checking is enabled.
 #ifdef EXPENSIVE_CHECKS
-static bool VerifyDomInfo = true;
+bool llvm::VerifyDomInfo = true;
 #else
-static bool VerifyDomInfo = false;
+bool llvm::VerifyDomInfo = false;
 #endif
 static cl::opt<bool,true>
 VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
                cl::desc("Verify dominator info (time consuming)"));
 
 bool BasicBlockEdge::isSingleEdge() const {
   const TerminatorInst *TI = Start->getTerminator();
   unsigned NumEdgesToEnd = 0;

lib/Transforms/Utils/LoopUnroll.cpp

if (NeedConditional) {
           }
         }
       }
       // Replace the conditional branch with an unconditional one.
       BranchInst::Create(Dest, Term);
       Term->eraseFromParent();
     }
   }
+
   // Update dominators of blocks we might reach through exits.
   // Immediate dominator of such block might change, because we add more
   // routes which can lead to the exit: we can now reach it from the copied
   // iterations too. Thus, the new idom of the block will be the nearest
   // common dominator of the previous idom and common dominator of all copies of
   // the previous idom. This is equivalent to the nearest common dominator of
   // the previous idom and the first latch, which dominates all copies of the
   // previous idom.
   if (DT && Count > 1) {
     for (auto *BB : OriginalLoopBlocks) {
       auto *BBDomNode = DT->getNode(BB);
       SmallVector<BasicBlock *, 16> ChildrenToUpdate;
       for (auto *ChildDomNode : BBDomNode->getChildren()) {
         auto *ChildBB = ChildDomNode->getBlock();
         if (!L->contains(ChildBB))
           ChildrenToUpdate.push_back(ChildBB);
       }
       BasicBlock *NewIDom = DT->findNearestCommonDominator(BB, Latches[0]);
       for (auto *ChildBB : ChildrenToUpdate)
         DT->changeImmediateDominator(ChildBB, NewIDom);
     }
+    // If runtime prolog is created, its conditional branch jumps around the
+    // block inserted for keeping LCSSA form. So the only predecessor of
+    // LoopExit is the last latch block.
+    if (!UnrollRuntimeEpilog && RuntimeTripCount)
+      DT->changeImmediateDominator(LoopExit, Latches.back());
   }
 
   // Merge adjacent basic blocks, if possible.
   SmallPtrSet<Loop *, 4> ForgottenLoops;
   for (BasicBlock *Latch : Latches) {
     BranchInst *Term = cast<BranchInst>(Latch->getTerminator());
     if (Term->isUnconditional()) {
       BasicBlock *Dest = Term->getSuccessor(0);
       if (BasicBlock *Fold =
               foldBlockIntoPredecessor(Dest, LI, SE, ForgottenLoops, DT)) {
         // Dest has been folded into Fold. Update our worklists accordingly.
         std::replace(Latches.begin(), Latches.end(), Dest, Fold);
         UnrolledLoopBlocks.erase(std::remove(UnrolledLoopBlocks.begin(),
                                              UnrolledLoopBlocks.end(), Dest),
                                  UnrolledLoopBlocks.end());
       }
     }
   }
 
-  // FIXME: We only preserve DT info for complete unrolling now. Incrementally
-  // updating domtree after partial loop unrolling should also be easy.
-  if (DT && !CompletelyUnroll)
-    DT->recalculate(*L->getHeader()->getParent());
-  else if (DT)
-    DEBUG(DT->verifyDomTree());
-
   // Simplify any new induction variables in the partially unrolled loop.
   if (SE && !CompletelyUnroll && Count > 1) {
     SmallVector<WeakVH, 16> DeadInsts;
     simplifyLoopIVs(L, SE, DT, LI, DeadInsts);
 
     // Aggressively clean up dead instructions that simplifyLoopIVs already
     // identified. Any remaining should be cleaned up below.
     while (!DeadInsts.empty())
if (OuterL) {
       else
         assert(OuterL->isLCSSAForm(*DT) &&
                "Loops should be in LCSSA form after loop-unroll.");
     } else {
       // Simplify loops for which we might've broken loop-simplify form.
       for (Loop *SubLoop : LoopsToSimplify)
         simplifyLoop(SubLoop, DT, LI, SE, AC, PreserveLCSSA);
     }
+#ifndef NDEBUG
+  if (VerifyDomInfo)
+    DT->verifyDomTree();
+  if (VerifyLoopInfo)
+    LI->verify(*DT);
+#endif
   }
 
   return true;
 }
 
 /// Given an llvm.loop loop id metadata node, returns the loop hint metadata
 /// node with the given name (for example, "llvm.loop.unroll.count"). If no
 /// such metadata node exists, then nullptr is returned.

lib/Transforms/Utils/LoopUnrollPeel.cpp

 /// \param[out] VMap The value map between the loop and the new clone.
 /// \param LoopBlocks A helper for DFS-traversal of the loop.
 /// \param LVMap A value-map that maps instructions from the original loop to
 /// instructions in the last peeled-off iteration.
 static void cloneLoopBlocks(Loop *L, unsigned IterNumber, BasicBlock *InsertTop,
                             BasicBlock *InsertBot, BasicBlock *Exit,
                             SmallVectorImpl<BasicBlock *> &NewBlocks,
                             LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,
-                            ValueToValueMapTy &LVMap, LoopInfo *LI) {
+                            ValueToValueMapTy &LVMap, DominatorTree *DT,
+                            LoopInfo *LI) {
 
   BasicBlock *Header = L->getHeader();
   BasicBlock *Latch = L->getLoopLatch();
   BasicBlock *PreHeader = L->getLoopPreheader();
 
   Function *F = Header->getParent();
   LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
   LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
   Loop *ParentLoop = L->getParentLoop();
 
   // For each block in the original loop, create a new copy,
   // and update the value map with the newly created values.
   for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
     BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".peel", F);
     NewBlocks.push_back(NewBB);
 
     if (ParentLoop)
       ParentLoop->addBasicBlockToLoop(NewBB, *LI);
 
     VMap[*BB] = NewBB;
+
+    // If dominator tree is available, insert nodes to represent cloned blocks.
+    if (DT) {
+      if (Header == *BB)
+        DT->addNewBlock(NewBB, InsertTop);
+      else {
+        DomTreeNode *IDom = DT->getNode(*BB)->getIDom();
+        DT->addNewBlock(NewBB,
+                        cast<BasicBlock>(VMap[cast<Value>(IDom->getBlock())]));
+      }
+    }
   }
 
   // Hook-up the control flow for the newly inserted blocks.
   // The new header is hooked up directly to the "top", which is either
   // the original loop preheader (for the first iteration) or the previous
   // iteration's exiting block (for every other iteration)
   InsertTop->getTerminator()->setSuccessor(0, cast<BasicBlock>(VMap[Header]));
 
   // Similarly, for the latch:
   // The original exiting edge is still hooked up to the loop exit.
   // The backedge now goes to the "bottom", which is either the loop's real
   // header (for the last peeled iteration) or the copied header of the next
   // iteration (for every other iteration)
-  BranchInst *LatchBR =
-      cast<BranchInst>(cast<BasicBlock>(VMap[Latch])->getTerminator());
+  BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
+  BranchInst *LatchBR = cast<BranchInst>(NewLatch->getTerminator());
   unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
   LatchBR->setSuccessor(HeaderIdx, InsertBot);
   LatchBR->setSuccessor(1 - HeaderIdx, Exit);
+  if (DT) {
+    DT->changeImmediateDominator(InsertBot, NewLatch);
+    BasicBlock *CurIDom = DT->getNode(Exit)->getIDom()->getBlock();
+    BasicBlock *NewIDom = DT->findNearestCommonDominator(CurIDom, NewLatch);
+    DT->changeImmediateDominator(Exit, NewIDom);
+  }
+
+#ifndef NDEBUG
+  if (DT && VerifyDomInfo)
+    DT->verifyDomTree();
+#endif
 
   // The new copy of the loop body starts with a bunch of PHI nodes
   // that pick an incoming value from either the preheader, or the previous
   // loop iteration. Since this copy is no longer part of the loop, we
   // resolve this statically:
   // For the first iteration, we use the value from the preheader directly.
   // For any other iteration, we replace the phi with the value generated by
   // the immediately preceding clone of the loop body (which represents
for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
     // FIXME: due to the way the distribution is constructed, we need a
     // guard here to make sure we don't end up with non-positive weights.
     if (ExitWeight < CurHeaderWeight)
       CurHeaderWeight -= ExitWeight;
     else
       CurHeaderWeight = 1;
 
     cloneLoopBlocks(L, Iter, InsertTop, InsertBot, Exit,
-                    NewBlocks, LoopBlocks, VMap, LVMap, LI);
+                    NewBlocks, LoopBlocks, VMap, LVMap, DT, LI);
     updateBranchWeights(InsertBot, cast<BranchInst>(VMap[LatchBR]), Iter,
                         PeelCount, ExitWeight);
 
     InsertTop = InsertBot;
     InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
     InsertBot->setName(Header->getName() + ".peel.next");
 
     F->getBasicBlockList().splice(InsertTop->getIterator(),

lib/Transforms/Utils/LoopUnrollRuntime.cpp

static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
   assert(Exit && "Loop must have a single exit block only");
   // Split the exit to maintain loop canonicalization guarantees
   SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
   SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", DT, LI,
                          PreserveLCSSA);
   // Add the branch to the exit block (around the unrolled loop)
   B.CreateCondBr(BrLoopExit, Exit, NewPreHeader);
   InsertPt->eraseFromParent();
+  if (DT)
+    DT->changeImmediateDominator(Exit, PrologExit);
 }
 
 /// Connect the unrolling epilog code to the original loop.
 /// The unrolling epilog code contains code to execute the
 /// 'extra' iterations if the run-time trip count modulo the
 /// unroll count is non-zero.
 ///
 /// This function performs the following:
static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
   assert(Exit && "Loop must have a single exit block only");
   // Split the exit to maintain loop canonicalization guarantees
   SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
   SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI,
                          PreserveLCSSA);
   // Add the branch to the exit block (around the unrolling loop)
   B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
   InsertPt->eraseFromParent();
+  if (DT)
+    DT->changeImmediateDominator(Exit, NewExit);
 }
 
 /// Create a clone of the blocks in a loop and connect them together.
 /// If CreateRemainderLoop is false, loop structure will not be cloned,
 /// otherwise a new loop will be created including all cloned blocks, and the
 /// iterator of it switches to count NewIter down to 0.
 /// The cloned blocks should be inserted between InsertTop and InsertBot.
 /// If loop structure is cloned InsertTop should be new preheader, InsertBot
 /// new loop exit.
 ///
 static void CloneLoopBlocks(Loop *L, Value *NewIter,
                             const bool CreateRemainderLoop,
                             const bool UseEpilogRemainder,
                             BasicBlock *InsertTop, BasicBlock *InsertBot,
                             BasicBlock *Preheader,
                             std::vector<BasicBlock *> &NewBlocks,
                             LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,
-                            LoopInfo *LI) {
+                            DominatorTree *DT, LoopInfo *LI) {
   StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
   BasicBlock *Header = L->getHeader();
   BasicBlock *Latch = L->getLoopLatch();
   Function *F = Header->getParent();
   LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
   LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
   Loop *NewLoop = nullptr;
   Loop *ParentLoop = L->getParentLoop();
if (Latch == *BB) {
         Value *IdxCmp =
             Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
         Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
         NewIdx->addIncoming(NewIter, InsertTop);
         NewIdx->addIncoming(IdxSub, NewBB);
       }
       LatchBR->eraseFromParent();
     }
+
+    // If dominator tree is available, insert nodes to represent cloned blocks.
+    // Note, that the dominator tree remains in inconsistent state, because
+    // the cloned block terminators points to original blocks. The consistency
+    // will be restored after instruction remap is made.
+    if (DT) {
+      if (Header == *BB)
+        DT->addNewBlock(NewBB, InsertTop);
+      else {
+        DomTreeNode *IDom = DT->getNode(*BB)->getIDom();
+        DT->addNewBlock(NewBB,
+          cast<BasicBlock>(VMap[cast<Value>(IDom->getBlock())]));
+      }
+    }
   }
 
   // Change the incoming values to the ones defined in the preheader or
   // cloned loop.
   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
     PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
     if (!CreateRemainderLoop) {
       if (UseEpilogRemainder) {
if (!CreateRemainderLoop) {
       BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
       idx = NewPHI->getBasicBlockIndex(Latch);
       Value *InVal = NewPHI->getIncomingValue(idx);
       NewPHI->setIncomingBlock(idx, NewLatch);
       if (Value *V = VMap.lookup(InVal))
         NewPHI->setIncomingValue(idx, V);
     }
   }
+
   if (NewLoop) {
     // Add unroll disable metadata to disable future unrolling for this loop.
     SmallVector<Metadata *, 4> MDs;
     // Reserve first location for self reference to the LoopID metadata node.
     MDs.push_back(nullptr);
     MDNode *LoopID = NewLoop->getLoopID();
     if (LoopID) {
       // First remove any existing loop unrolling metadata.
Value *BranchVal =
                                            ConstantInt::get(BECount->getType(),
                                                             Count - 1)) :
                            B.CreateIsNotNull(ModVal, "lcmp.mod");
   BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
   BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
   // Branch to either remainder (extra iterations) loop or unrolling loop.
   B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
   PreHeaderBR->eraseFromParent();
+  if (DT) {
+    if (UseEpilogRemainder)
+      DT->changeImmediateDominator(NewExit, PreHeader);
+    else
+      DT->changeImmediateDominator(UnrollingLoop, PreHeader);
+#ifndef NDEBUG
+    if (VerifyDomInfo)
+      DT->verifyDomTree();
+#endif
+  }
   Function *F = Header->getParent();
   // Get an ordered list of blocks in the loop to help with the ordering of the
   // cloned blocks in the prolog/epilog code
   LoopBlocksDFS LoopBlocks(L);
   LoopBlocks.perform(LI);
 
   //
   // For each extra loop iteration, create a copy of the loop's basic blocks
   // and generate a condition that branches to the copy depending on the
   // number of 'left over' iterations.
   //
   std::vector<BasicBlock *> NewBlocks;
   ValueToValueMapTy VMap;
 
   // For unroll factor 2 remainder loop will have 1 iterations.
   // Do not create 1 iteration loop.
   bool CreateRemainderLoop = (Count != 2);
 
   // Clone all the basic blocks in the loop. If Count is 2, we don't clone
   // the loop, otherwise we create a cloned loop to execute the extra
   // iterations. This function adds the appropriate CFG connections.
   BasicBlock *InsertBot = UseEpilogRemainder ? Exit : PrologExit;
   BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
   CloneLoopBlocks(L, ModVal, CreateRemainderLoop, UseEpilogRemainder, InsertTop,
-                  InsertBot, NewPreHeader, NewBlocks, LoopBlocks, VMap, LI);
+                  InsertBot, NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
 
   // Insert the cloned blocks into the function.
   F->getBasicBlockList().splice(InsertBot->getIterator(),
                                 F->getBasicBlockList(),
                                 NewBlocks[0]->getIterator(),
                                 F->end());
 
   // Loop structure should be the following:
if (UseEpilogRemainder) {
     LatchBR->setCondition(IdxCmp);
   } else {
     // Connect the prolog code to the original loop and update the
     // PHI functions.
     ConnectProlog(L, BECount, Count, PrologExit, PreHeader, NewPreHeader,
                   VMap, DT, LI, PreserveLCSSA);
   }
 
+#ifndef NDEBUG
+  if (DT) {
+    if (VerifyDomInfo)
+      DT->verifyDomTree();
+    if (VerifyLoopInfo)
+      LI->verify(*DT);
+  }
+#endif
+
   // If this loop is nested, then the loop unroller changes the code in the
   // parent loop, so the Scalar Evolution pass needs to be run again.
   if (Loop *ParentLoop = L->getParentLoop())
     SE->forgetLoop(ParentLoop);
 
   NumRuntimeUnrolled++;
   return true;
 }

test/Transforms/LoopUnroll/2007-05-09-UnknownTripCount.ll

-; RUN: opt < %s -loop-unroll -unroll-count=3 -S | grep bb72.2
+; RUN: opt < %s -loop-unroll -unroll-count=3 -verify-dom-info -verify-loop-info -S | grep bb72.2
 
 define void @foo(i32 %trips) {
 entry:
   br label %cond_true.outer
 
 cond_true.outer:
   %indvar1.ph = phi i32 [ 0, %entry ], [ %indvar.next2, %bb72 ]
   br label %bb72

test/Transforms/LoopUnroll/peel-loop.ll

-; RUN: opt < %s -S -loop-unroll -unroll-force-peel-count=3 -simplifycfg -instcombine | FileCheck %s
+; RUN: opt < %s -S -loop-unroll -unroll-force-peel-count=3 -verify-dom-info -verify-loop-info -simplifycfg -instcombine | FileCheck %s
 
 ; Basic loop peeling - check that we can peel-off the first 3 loop iterations
 ; when explicitly requested.
 ; CHECK-LABEL: @basic
 ; CHECK: %[[CMP0:.*]] = icmp sgt i32 %k, 0
 ; CHECK: br i1 %[[CMP0]], label %[[NEXT0:.*]], label %for.end
 ; CHECK: [[NEXT0]]:
 ; CHECK: store i32 0, i32* %p, align 4

test/Transforms/LoopUnroll/runtime-loop.ll

-; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=true  | FileCheck %s -check-prefix=EPILOG
-; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
+; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=true  -verify-dom-info -verify-loop-info | FileCheck %s -check-prefix=EPILOG
+; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=false -verify-dom-info -verify-loop-info | FileCheck %s -check-prefix=PROLOG
 
 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-S128"
 
 ; Tests for unrolling loops with run-time trip counts
 
 ; EPILOG: %xtraiter = and i32 %n
 ; EPILOG:  %lcmp.mod = icmp ne i32 %xtraiter, 0
 ; EPILOG:  br i1 %lcmp.mod, label %for.body.epil.preheader, label %for.end.loopexit

test/Transforms/LoopUnroll/runtime-loop3.ll

 ; REQUIRES: asserts
-; RUN: opt < %s -disable-output -stats -loop-unroll -unroll-runtime -unroll-threshold=400 -info-output-file - | FileCheck %s --check-prefix=STATS
+; RUN: opt < %s -disable-output -stats -loop-unroll -unroll-runtime -unroll-threshold=400 -verify-dom-info -verify-loop-info -info-output-file - | FileCheck %s --check-prefix=STATS
 
 ; Test that nested loops can be unrolled.  We need to increase threshold to do it
 
 ; STATS: 2 loop-unroll - Number of loops unrolled (completely or otherwise)
 
 define i32 @nested(i32* nocapture %a, i32 %n, i32 %m) nounwind uwtable readonly {
 entry:
   %cmp11 = icmp sgt i32 %n, 0