[ADCE] Add code to remove dead branches

[david2050]

Summary

This is last in of a series of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch adds the code to update the control and data flow graphs
to remove the dead control flow.

Also update unit tests to test the capability to remove dead,
may-be-infinite loop which is enabled by the switch
-adce-remove-loops.

Previous patches:

D23824 [ADCE] Add handling of PHI nodes when removing control flow
D23559 [ADCE] Add control dependence computation
D23225 [ADCE] Modify data structures to support removing control flow
D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

[• dberlin]

lib/Transforms/Scalar/ADCE.cpp

217 ↗

(On Diff #72486)

I don't think this does what you think.
The order here is not actually guaranteed to be in any particular order, AFAIK.

It happens most things produce blocks in lexical order, but this is not guaranteed (again, AFAIK)

Thus, it's entirely possible you see a successor before a predecessor, which you will incorrectly mark a a back edge.
Please just use a standard DFS approach that is guaranteed correct.

228 ↗

(On Diff #72486)

This isn't correct. What if you have two backedges going out of a single block?

235 ↗

(On Diff #72486)

We should just fix IDF calculator in the reverse case?

In any case, this is just a reverse DFS (IE DFS over Inverse<BasicBlock>) from all blocks with no successors (LLVM does not hvae a single return block, you can't really say "the return of the function").

Please just do that.

248 ↗

(On Diff #72486)

This has the same bug as above :)

610 ↗

(On Diff #72486)

Is the above really necessary?

The standard way to do this, AFAIK, is to mark the useful block set while doing marking, and then just walking up the PDT to find the nearest block marked useful for each dead branch.
Replace all uses of the bb with that block using RAUW.
This should update phi nodes, since I believe the blocks in phi nodes are still considered uses.

[david2050]

lib/Transforms/Scalar/ADCE.cpp

217 ↗

(On Diff #72486)

This seems super simple and conservative in the sense it will catch all loops. The variant of this code before this review cycle started used po_iterator but there no measurable benefit but quite a bit more code.

228 ↗

(On Diff #72486)

Still can only mark the terminator of that block live once.

235 ↗

(On Diff #72486)

I think you are proposing to indentify all blocks where there is a path to function return. Given that we we can then infer those blocks which do not reach a return. But this seems to be exactly the information already available from the post-dominator tree.

248 ↗

(On Diff #72486)

I don't think so: marking the terminator of the source block not the successor block.

[david2050]

lib/Transforms/Scalar/ADCE.cpp

610 ↗

(On Diff #72486)

I don't understand this approach. Given a live branch (x,y) where y is dead and z is the live post-dominator of y, we can't just replace uses of 'y' because the 'y' may not be directly referenced in phi nodes in 'z' which only will old references to its predecessors. Also, 'y' could have multiple branches into it which are dead.

[• dberlin]

lib/Transforms/Scalar/ADCE.cpp

217 ↗

(On Diff #72486)

So, here are two of identical code, laid out in the IR differently, where we will do different things, and should not.

A
jump C
B
jump D
C
jump B

A
jump C
C
jump B
B
jump D

In the first, the visitation order will be A, B, C.
You will mark A as seen.
No successors seen, nothing marked.
You will now mark B as visited
No successors seen, nothing marked
You will now mark C as visited
You will see that you have marked B as visited
You will incorrectly think this is a back edge.

In the second, the visitation order, will be A, C, B.
You will mark A as seen.
No successors seen, nothing marked.
You will mark C as seen
No successors seen, nothing marked.
You will mark B as seen
No successors seen, nothing marked

228 ↗

(On Diff #72486)

yes, i read it wrong, sorry!

248 ↗

(On Diff #72486)

yes, i read it wrong, sorry!

[david2050]

rebase and update to new df_iterator interface

[david2050]

ping

[david2050]

ping

[mehdi_amini]

I had started reviewing after you previous ping last week but couldn't finish because of the conference preparation, so just some piece of wip feedback inline.

lib/Transforms/Scalar/ADCE.cpp

232 ↗

(On Diff #73820)

OK, I was wondering how the "completed" stuff worked when you introduced it, I see now :)

243 ↗

(On Diff #73820)

I think the boilerplate can be reduced:

for (auto *BB : make_range(Iterator::begin(&F.getEntryBlock(), State),
                                               Iterator::end(&F.getEntryBlock(), State)) {
   ....

The repetition of &F.getEntryBlock(), State isn't great, upgrading iterator_range<df_iterator<T>> depth_first(const T& G) and df_begin and df_end to accept the extra State parameter should allow to write:

for (auto *BB : depth_first(&F.getEntryBlock(), State)) {
   ....

[david2050]

Use depth_first_ext() template

[david2050]

ping

lib/Transforms/Scalar/ADCE.cpp

243 ↗

(On Diff #73820)

Thanks, the existing depth_first_ext applies.

[mehdi_amini]

Sorry for the delay, I keep getting interrupted in the middle of getting this code into my head, and paging out has a real cost when getting back to it. Especially as I don't really know the algorithm, I have to infer what you're doing from the implementation (which isn't a bad way to judge of the clarity of the code).

Anyway, a few inline comments.

lib/Transforms/Scalar/ADCE.cpp

610 ↗

(On Diff #72486)

I'm not sure I understood what @dberlin referred to, but as I read it it should be possible to just process DeadBlocks without computing the dead region, and only manipulate Phi in the live PDOM if the live PDOM is a direct successor of the current block. I think this should get the same result in term of Phi, but does not seems less costly than computing the region.
Also I'm not sure if you can rewrite the branches from the live predecessors into the dead region to jump directly to the live PDOM without computing the region (but with the invariant you are already relying on to get a dead region with a unique live PDOM it may be possible).

240 ↗

(On Diff #76904)

Remove this empty line?

496 ↗

(On Diff #76904)

This is quite complex to follow: the NewBranches is some state that is kept on the side and updated by makeUnconditional (transitively called by updateDeadRegions), and used here as a cleanup. It is never cleared BTW.
Maybe declaring NewBranches locally to this function and passing it by as an output parameter to updateDeadRegions()?

571 ↗

(On Diff #76904)

s/unprocsesed/unprocessed/

580 ↗

(On Diff #76904)

Parameter should be SmallPtrSetImpl<BasicBlock *> *VisitedBlocks. The template with the size is only used where you need to actually create one.

(Also I'd use a reference instead of pointer)

611 ↗

(On Diff #76904)

auto * for pointers
(Many other occurrences)

621 ↗

(On Diff #76904)

How do we get this invariant that a region has a single live PDOM?
(If you can point me to the relevant code)

628 ↗

(On Diff #76904)

Could be compressed to a single else:

else  {
  assert(!LivePDOM || LivePDOM == SuccBB);
  LivePDOM = SuccBB;
}

Also we usually try to add a message with assertions when possible.

665 ↗

(On Diff #76904)

To make sure I understand correctly: if the terminator was a conditional branch with each target BB in different dead region, then this terminator shouldn't be marked as dead?

667 ↗

(On Diff #76904)

/me scrolling but don't see the example...

[david2050]

lib/Transforms/Scalar/ADCE.cpp

621 ↗

(On Diff #76904)

I will add a comment:

// (A block with a dead branch which reaches a live block that
//  is not a post-dominator would be a control dependence source
//  and hence its branch must be live)

665 ↗

(On Diff #76904)

This is a live block which has whose terminator is dead the implication is that all paths from this branch must reach LivePDOM (directly or through blocks with dead branches). We replace this branch with an unconditional branch.

[mehdi_amini]

lib/Transforms/Scalar/ADCE.cpp

665 ↗

(On Diff #76904)

My question was about another invariant at this stage:

A
| \
B C
| |
D E

If B and C are dead, but A, D and E are live.
A's terminator branch to either B or C, which are both dead. However B and C aren't part of the same dead region.
You're operating here under the assumption that A's terminator has be marked as live somehow, right?

[david2050]

reduce scope of NewBranches, fix formatting

[david2050]

reduce scope of NewBranches, fix formatting

[david2050]

lib/Transforms/Scalar/ADCE.cpp

665 ↗

(On Diff #76904)

Yes, if "D" is live then, as expressed, "A" is a control-dependence source for "D" (and for all non-A nodes listed) and as such will be marked live. "A" will be in the iterated dominance frontier of the "D" in the reverse control flow graph. If the terminator is not live then "D" and "E" must be the same (and in the code labeled LivePDOM).

[david2050]

Regarding the question of simpler update to the control flow, I reviewed two references from @dberlin:

(1) https://www.clear.rice.edu/comp512/Lectures/10Dead-Clean-SCCP.pdf

In this work, the PHI nodes contain only references to named definitions and do not include a reference to the predecessor blocks associated with reaching paths from those definitions.

(2) https://github.com/apple/swift/blob/master/lib/SILOptimizer/Transforms/DeadCodeElimination.cpp

This swift variant makes no explicit reference to Phi nodes and does neither updates them nor manages explicit predecessors as far as I can tell.

Does anyone have another pointer to compiler which have SSA-based dead code elimination including control flow which might guide to a similar approach the code here?
Thanks!

[david2050]

Use reverse CFG numbering to alter control flow

[• dberlin]

lib/Transforms/Scalar/ADCE.cpp

601 ↗

(On Diff #80516)

I think you should just be able to output the PO iterator on Inverse<F> into an array, no?

I would just add

template <class T>
po_iterator<T> inverse_po_begin(const T &G) { return po_iterator<Inverse<T>>::begin(G); }
template <class T>
po_iterator<T> inverse_po_end  (const T &G) { return po_iterator<Inverse<T>>::end(G); }

template <class T> iterator_range<po_iterator<T>> inverse_post_order(const T &G) {
  return make_range(inverse_po_begin(G), inverse_po_end(G));
}

To PostOrderIterator.h
Then you can just use a nice range loop to fill in the numbers wherever you want them.

[david2050]

use existing inverse_post_order

[david2050]

lib/Transforms/Scalar/ADCE.cpp

601 ↗

(On Diff #80516)

Thanks for reminding me. These macros already are defined in in the header. We still need the loop to find all nodes without successors right, because there could be multiple returns/

[david2050]

remove unused declarations

[mehdi_amini]

Skimming through it it LGTM as well. Thanks!

llvm/trunk/lib/Transforms/Scalar/ADCE.cpp

 // allowing it to eliminate dead computations that other DCE passes do not
 // catch, particularly involving loop computations.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/ADCE.h"
 
 #include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Pass.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Transforms/Scalar.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "adce"
 
 STATISTIC(NumRemoved, "Number of instructions removed");
+STATISTIC(NumBranchesRemoved, "Number of branch instructions removed");
 
 // This is a tempoary option until we change the interface
 // to this pass based on optimization level.
 static cl::opt<bool> RemoveControlFlowFlag("adce-remove-control-flow",
-                                           cl::init(false), cl::Hidden);
+                                           cl::init(true), cl::Hidden);
+
+// This option enables removing of may-be-infinite loops which have no other
+// effect.
+static cl::opt<bool> RemoveLoops("adce-remove-loops", cl::init(false),
+                                 cl::Hidden);
 
 namespace {
 /// Information about Instructions
 struct InstInfoType {
   /// True if the associated instruction is live.
   bool Live = false;
   /// Quick access to information for block containing associated Instruction.
   struct BlockInfoType *Block = nullptr;
struct BlockInfoType {
   /// holds the value &InstInfo[Terminator]
   InstInfoType *TerminatorLiveInfo = nullptr;
 
   bool terminatorIsLive() const { return TerminatorLiveInfo->Live; }
 
   /// Corresponding BasicBlock.
   BasicBlock *BB = nullptr;
 
-  /// Cache of BB->getTerminator()
+  /// Cache of BB->getTerminator().
   TerminatorInst *Terminator = nullptr;
+
+  /// Post-order numbering of reverse control flow graph.
+  unsigned PostOrder;
 };
 
 class AggressiveDeadCodeElimination {
   Function &F;
   PostDominatorTree &PDT;
 
   /// Mapping of blocks to associated information, an element in BlockInfoVec.
   DenseMap<BasicBlock *, BlockInfoType> BlockInfo;
   bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; }
 
   /// Mapping of instructions to associated information.
   DenseMap<Instruction *, InstInfoType> InstInfo;
   bool isLive(Instruction *I) { return InstInfo[I].Live; }
 
   /// Instructions known to be live where we need to mark
   /// reaching definitions as live.
   SmallVector<Instruction *, 128> Worklist;
   /// Debug info scopes around a live instruction.
   SmallPtrSet<const Metadata *, 32> AliveScopes;
 
   /// Set of blocks with not known to have live terminators.
   SmallPtrSet<BasicBlock *, 16> BlocksWithDeadTerminators;
 
-  /// The set of blocks which we have determined are live in the
-  /// most recent iteration of propagating liveness.
+  /// The set of blocks which we have determined whose control
+  /// dependence sources must be live and which have not had
+  /// those dependences analyized.
   SmallPtrSet<BasicBlock *, 16> NewLiveBlocks;
 
   /// Set up auxiliary data structures for Instructions and BasicBlocks and
   /// initialize the Worklist to the set of must-be-live Instruscions.
   void initialize();
   /// Return true for operations which are always treated as live.
   bool isAlwaysLive(Instruction &I);
   /// Return true for instrumentation instructions for value profiling.
   bool isInstrumentsConstant(Instruction &I);
 
   /// Propagate liveness to reaching definitions.
   void markLiveInstructions();
   /// Mark an instruction as live.
   void markLive(Instruction *I);
-  
+  /// Mark a block as live.
+  void markLive(BlockInfoType &BB);
+  void markLive(BasicBlock *BB) { markLive(BlockInfo[BB]); }
   /// Mark terminators of control predecessors of a PHI node live.
   void markPhiLive(PHINode *PN);
 
   /// Record the Debug Scopes which surround live debug information.
   void collectLiveScopes(const DILocalScope &LS);
   void collectLiveScopes(const DILocation &DL);
 
   /// Analyze dead branches to find those whose branches are the sources
   /// of control dependences impacting a live block. Those branches are
   /// marked live.
   void markLiveBranchesFromControlDependences();
 
   /// Remove instructions not marked live, return if any any instruction
   /// was removed.
   bool removeDeadInstructions();
 
+  /// Identify connected sections of the control flow grap which have
+  /// dead terminators and rewrite the control flow graph to remove them.
+  void updateDeadRegions();
+
+  /// Set the BlockInfo::PostOrder field based on a post-order
+  /// numbering of the reverse control flow graph.
+  void computeReversePostOrder();
+
+  /// Make the terminator of this block an unconditional branch to \p Target.
+  void makeUnconditional(BasicBlock *BB, BasicBlock *Target);
+
 public:
   AggressiveDeadCodeElimination(Function &F, PostDominatorTree &PDT)
       : F(F), PDT(PDT) {}
   bool performDeadCodeElimination();
 };
 }
 
 bool AggressiveDeadCodeElimination::performDeadCodeElimination() {
   initialize();
   markLiveInstructions();
   return removeDeadInstructions();
 }
 
 static bool isUnconditionalBranch(TerminatorInst *Term) {
-  auto BR = dyn_cast<BranchInst>(Term);
+  auto *BR = dyn_cast<BranchInst>(Term);
   return BR && BR->isUnconditional();
 }
 
 void AggressiveDeadCodeElimination::initialize() {
 
   auto NumBlocks = F.size();
 
   // We will have an entry in the map for each block so we grow the
void AggressiveDeadCodeElimination::initialize() {
   // Collect the set of "root" instructions that are known live.
   for (Instruction &I : instructions(F))
     if (isAlwaysLive(I))
       markLive(&I);
 
   if (!RemoveControlFlowFlag)
     return;
 
-  // This is temporary: will update with post order traveral to
-  // find loop bottoms
-  SmallPtrSet<BasicBlock *, 16> Seen;
-  for (auto &BB : F) {
-    Seen.insert(&BB);
-    TerminatorInst *Term = BB.getTerminator();
+  if (!RemoveLoops) {
+    // This stores state for the depth-first iterator. In addition
+    // to recording which nodes have been visited we also record whether
+    // a node is currently on the "stack" of active ancestors of the current
+    // node.
+    typedef DenseMap<BasicBlock *, bool>  StatusMap ;
+    class DFState : public StatusMap {
+    public:
+      std::pair<StatusMap::iterator, bool> insert(BasicBlock *BB) {
+        return StatusMap::insert(std::make_pair(BB, true));
+      }
+
+      // Invoked after we have visited all children of a node.
+      void completed(BasicBlock *BB) { (*this)[BB] = false; }
+
+      // Return true if \p BB is currently on the active stack
+      // of ancestors.
+      bool onStack(BasicBlock *BB) {
+        auto Iter = find(BB);
+        return Iter != end() && Iter->second;
+      }
+    } State;
+    
+    State.reserve(F.size());
+    // Iterate over blocks in depth-first pre-order and
+    // treat all edges to a block already seen as loop back edges
+    // and mark the branch live it if there is a back edge.
+    for (auto *BB: depth_first_ext(&F.getEntryBlock(), State)) {
+      TerminatorInst *Term = BB->getTerminator();
       if (isLive(Term))
         continue;
 
-    for (auto Succ : successors(&BB))
-      if (Seen.count(Succ)) {
+      for (auto *Succ : successors(BB))
+        if (State.onStack(Succ)) {
           // back edge....
           markLive(Term);
           break;
         }
     }
-  // End temporary handling of loops.
+  }
+
+  // Mark blocks live if there is no path from the block to the
+  // return of the function or a successor for which this is true.
+  // This protects IDFCalculator which cannot handle such blocks.
+  for (auto &BBInfoPair : BlockInfo) {
+    auto &BBInfo = BBInfoPair.second;
+    if (BBInfo.terminatorIsLive())
+      continue;
+    auto *BB = BBInfo.BB;
+    if (!PDT.getNode(BB)) {
+      markLive(BBInfo.Terminator);
+      continue;
+    }
+    for (auto *Succ : successors(BB))
+      if (!PDT.getNode(Succ)) {
+        markLive(BBInfo.Terminator);
+        break;
+      }
+  }
 
   // Mark blocks live if there is no path from the block to the
   // return of the function or a successor for which this is true.
   // This protects IDFCalculator which cannot handle such blocks.
   for (auto &BBInfoPair : BlockInfo) {
     auto &BBInfo = BBInfoPair.second;
     if (BBInfo.terminatorIsLive())
       continue;
     auto *BB = BBInfo.BB;
     if (!PDT.getNode(BB)) {
       DEBUG(dbgs() << "Not post-dominated by return: " << BB->getName()
                    << '\n';);
       markLive(BBInfo.Terminator);
       continue;
     }
-    for (auto Succ : successors(BB))
+    for (auto *Succ : successors(BB))
       if (!PDT.getNode(Succ)) {
         DEBUG(dbgs() << "Successor not post-dominated by return: "
                      << BB->getName() << '\n';);
         markLive(BBInfo.Terminator);
         break;
       }
   }
 
void AggressiveDeadCodeElimination::markLiveInstructions() {
   // Propagate liveness backwards to operands.
   do {
     // Worklist holds newly discovered live instructions
     // where we need to mark the inputs as live.
     while (!Worklist.empty()) {
       Instruction *LiveInst = Worklist.pop_back_val();
       DEBUG(dbgs() << "work live: "; LiveInst->dump(););
 
-      // Collect the live debug info scopes attached to this instruction.
-      if (const DILocation *DL = LiveInst->getDebugLoc())
-        collectLiveScopes(*DL);
-
       for (Use &OI : LiveInst->operands())
         if (Instruction *Inst = dyn_cast<Instruction>(OI))
           markLive(Inst);
-      
       if (auto *PN = dyn_cast<PHINode>(LiveInst))
         markPhiLive(PN);
     }
+
+    // After data flow liveness has been identified, examine which branch
+    // decisions are required to determine live instructions are executed.
     markLiveBranchesFromControlDependences();
 
-    if (Worklist.empty()) {
-      // Temporary until we can actually delete branches.
-      SmallVector<TerminatorInst *, 16> DeadTerminators;
-      for (auto *BB : BlocksWithDeadTerminators)
-        DeadTerminators.push_back(BB->getTerminator());
-      for (auto *I : DeadTerminators)
-        markLive(I);
-      assert(BlocksWithDeadTerminators.empty());
-      // End temporary.
-    }
   } while (!Worklist.empty());
-
-  assert(BlocksWithDeadTerminators.empty());
 }
 
 void AggressiveDeadCodeElimination::markLive(Instruction *I) {
 
   auto &Info = InstInfo[I];
   if (Info.Live)
     return;
 
   DEBUG(dbgs() << "mark live: "; I->dump());
   Info.Live = true;
   Worklist.push_back(I);
 
+  // Collect the live debug info scopes attached to this instruction.
+  if (const DILocation *DL = I->getDebugLoc())
+    collectLiveScopes(*DL);
+
   // Mark the containing block live
   auto &BBInfo = *Info.Block;
-  if (BBInfo.Terminator == I)
+  if (BBInfo.Terminator == I) {
     BlocksWithDeadTerminators.erase(BBInfo.BB);
+    // For live terminators, mark destination blocks
+    // live to preserve this control flow edges.
+    if (!BBInfo.UnconditionalBranch)
+      for (auto *BB : successors(I->getParent()))
+        markLive(BB);
+  }
+  markLive(BBInfo);
+}
+
+void AggressiveDeadCodeElimination::markLive(BlockInfoType &BBInfo) {
   if (BBInfo.Live)
     return;
-
   DEBUG(dbgs() << "mark block live: " << BBInfo.BB->getName() << '\n');
   BBInfo.Live = true;
   if (!BBInfo.CFLive) {
     BBInfo.CFLive = true;
     NewLiveBlocks.insert(BBInfo.BB);
   }
 
   // Mark unconditional branches at the end of live
   // blocks as live since there is no work to do for them later
-  if (BBInfo.UnconditionalBranch && I != BBInfo.Terminator)
+  if (BBInfo.UnconditionalBranch)
     markLive(BBInfo.Terminator);
 }
 
 void AggressiveDeadCodeElimination::collectLiveScopes(const DILocalScope &LS) {
   if (!AliveScopes.insert(&LS).second)
     return;
 
   if (isa<DISubprogram>(LS))
void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
   SmallVector<BasicBlock *, 32> IDFBlocks;
   ReverseIDFCalculator IDFs(PDT);
   IDFs.setDefiningBlocks(NewLiveBlocks);
   IDFs.setLiveInBlocks(BlocksWithDeadTerminators);
   IDFs.calculate(IDFBlocks);
   NewLiveBlocks.clear();
 
   // Dead terminators which control live blocks are now marked live.
-  for (auto BB : IDFBlocks) {
+  for (auto *BB : IDFBlocks) {
     DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
     markLive(BB->getTerminator());
   }
 }
 
 //===----------------------------------------------------------------------===//
 //
 //  Routines to update the CFG and SSA information before removing dead code.
 //
 //===----------------------------------------------------------------------===//
 bool AggressiveDeadCodeElimination::removeDeadInstructions() {
 
-  // The inverse of the live set is the dead set.  These are those instructions
-  // which have no side effects and do not influence the control flow or return
-  // value of the function, and may therefore be deleted safely.
-  // NOTE: We reuse the Worklist vector here for memory efficiency.
+  // Updates control and dataflow around dead blocks
+  updateDeadRegions();
+
+  DEBUG({
     for (Instruction &I : instructions(F)) {
       // Check if the instruction is alive.
       if (isLive(&I))
         continue;
 
-    assert(!I.isTerminator() && "NYI: Removing Control Flow");
-
       if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
         // Check if the scope of this variable location is alive.
         if (AliveScopes.count(DII->getDebugLoc()->getScope()))
           continue;
 
-      // Fallthrough and drop the intrinsic.
-      DEBUG({
         // If intrinsic is pointing at a live SSA value, there may be an
         // earlier optimization bug: if we know the location of the variable,
         // why isn't the scope of the location alive?
         if (Value *V = DII->getVariableLocation())
           if (Instruction *II = dyn_cast<Instruction>(V))
             if (isLive(II))
               dbgs() << "Dropping debug info for " << *DII << "\n";
-      });
+      }
+    }
+
+  // The inverse of the live set is the dead set.  These are those instructions
+  // that have no side effects and do not influence the control flow or return
+  // value of the function, and may therefore be deleted safely.
+  // NOTE: We reuse the Worklist vector here for memory efficiency.
+  for (Instruction &I : instructions(F)) {
+    // Check if the instruction is alive.
+    if (isLive(&I))
+      continue;
+
+    if (auto *DII = dyn_cast<DbgInfoIntrinsic>(&I)) {
+      // Check if the scope of this variable location is alive.
+      if (AliveScopes.count(DII->getDebugLoc()->getScope()))
+        continue;
+
+      // Fallthrough and drop the intrinsic.
     }
 
     // Prepare to delete.
     Worklist.push_back(&I);
     I.dropAllReferences();
   }
 
   for (Instruction *&I : Worklist) {
     ++NumRemoved;
     I->eraseFromParent();
   }
 
   return !Worklist.empty();
 }
 
+// A dead region is the set of dead blocks with a common live post-dominator.
+void AggressiveDeadCodeElimination::updateDeadRegions() {
+
+  DEBUG({
+    dbgs() << "final dead terminator blocks: " << '\n';
+    for (auto *BB : BlocksWithDeadTerminators)
+      dbgs() << '\t' << BB->getName()
+             << (BlockInfo[BB].Live ? " LIVE\n" : "\n");
+  });
+
+  // Don't compute the post ordering unless we needed it.
+  bool HavePostOrder = false;
+
+  for (auto *BB : BlocksWithDeadTerminators) {
+    auto &Info = BlockInfo[BB];
+    if (Info.UnconditionalBranch) {
+      InstInfo[Info.Terminator].Live = true;
+      continue;
+    }
+
+    if (!HavePostOrder) {
+      computeReversePostOrder();
+      HavePostOrder = true;
+    }
+
+    // Add an unconditional branch to the successor closest to the
+    // end of the function which insures a path to the exit for each
+    // live edge.
+    BlockInfoType *PreferredSucc = nullptr;
+    for (auto *Succ : successors(BB)) {
+      auto *Info = &BlockInfo[Succ];
+      if (!PreferredSucc || PreferredSucc->PostOrder < Info->PostOrder)
+        PreferredSucc = Info;
+    }
+    assert((PreferredSucc && PreferredSucc->PostOrder > 0) &&
+           "Failed to find safe successor for dead branc");
+    bool First = true;
+    for (auto *Succ : successors(BB)) {
+      if (!First || Succ != PreferredSucc->BB)
+        Succ->removePredecessor(BB);
+      else
+        First = false;
+    }
+    makeUnconditional(BB, PreferredSucc->BB);
+    NumBranchesRemoved += 1;
+  }
+}
+
+// reverse top-sort order
+void AggressiveDeadCodeElimination::computeReversePostOrder() {
+  
+  // This provides a post-order numbering of the reverse conrtol flow graph
+  // Note that it is incomplete in the presence of infinite loops but we don't
+  // need numbers blocks which don't reach the end of the functions since
+  // all branches in those blocks are forced live.
+  
+  // For each block without successors, extend the DFS from the bloack
+  // backward through the graph
+  SmallPtrSet<BasicBlock*, 16> Visited;
+  unsigned PostOrder = 0;
+  for (auto &BB : F) {
+    if (succ_begin(&BB) != succ_end(&BB))
+      continue;
+    for (BasicBlock *Block : inverse_post_order_ext(&BB,Visited))
+      BlockInfo[Block].PostOrder = PostOrder++;
+  }
+}
+
+void AggressiveDeadCodeElimination::makeUnconditional(BasicBlock *BB,
+                                                      BasicBlock *Target) {
+  TerminatorInst *PredTerm = BB->getTerminator();
+  // Collect the live debug info scopes attached to this instruction.
+  if (const DILocation *DL = PredTerm->getDebugLoc())
+    collectLiveScopes(*DL);
+
+  // Just mark live an existing unconditional branch
+  if (isUnconditionalBranch(PredTerm)) {
+    PredTerm->setSuccessor(0, Target);
+    InstInfo[PredTerm].Live = true;
+    return;
+  }
+  DEBUG(dbgs() << "making unconditional " << BB->getName() << '\n');
+  NumBranchesRemoved += 1;
+  IRBuilder<> Builder(PredTerm);
+  auto *NewTerm = Builder.CreateBr(Target);
+  InstInfo[NewTerm].Live = true;
+  if (const DILocation *DL = PredTerm->getDebugLoc())
+    NewTerm->setDebugLoc(DL);
+}
+
 //===----------------------------------------------------------------------===//
 //
 // Pass Manager integration code
 //
 //===----------------------------------------------------------------------===//
 PreservedAnalyses ADCEPass::run(Function &F, FunctionAnalysisManager &FAM) {
   auto &PDT = FAM.getResult<PostDominatorTreeAnalysis>(F);
   if (!AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination())
bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
     auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
     return AggressiveDeadCodeElimination(F, PDT).performDeadCodeElimination();
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<PostDominatorTreeWrapperPass>();
-    AU.setPreservesCFG(); // TODO -- will remove when we start removing branches
+    if (!RemoveControlFlowFlag)
+      AU.setPreservesCFG();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 };
 }
 
 char ADCELegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(ADCELegacyPass, "adce",
                       "Aggressive Dead Code Elimination", false, false)
 INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_END(ADCELegacyPass, "adce", "Aggressive Dead Code Elimination",
                     false, false)
 
 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCELegacyPass(); }

llvm/trunk/test/Transforms/ADCE/2002-05-23-ZeroArgPHITest.ll

 ; This testcase contains a entire loop that should be removed.  The only thing
 ; left is the store instruction in BB0.  The problem this testcase was running
 ; into was that when the reg109 PHI was getting zero predecessors, it was 
 ; removed even though there were uses still around.  Now the uses are filled
 ; in with a dummy value before the PHI is deleted.
 ;
-; RUN: opt < %s -adce
+; RUN: opt < %s -S -adce | grep bb1
+; RUN: opt < %s -S -adce -adce-remove-loops | FileCheck %s
   
         %node_t = type { double*, %node_t*, %node_t**, double**, double*, i32, i32 }
 
 define void @localize_local(%node_t* %nodelist) {
 bb0:
         %nodelist.upgrd.1 = alloca %node_t*             ; <%node_t**> [#uses=2]
         store %node_t* %nodelist, %node_t** %nodelist.upgrd.1
         br label %bb1
 
 bb1:            ; preds = %bb0
         %reg107 = load %node_t*, %node_t** %nodelist.upgrd.1              ; <%node_t*> [#uses=2]
         %cond211 = icmp eq %node_t* %reg107, null               ; <i1> [#uses=1]
+; CHECK: br label %bb3
         br i1 %cond211, label %bb3, label %bb2
 
 bb2:            ; preds = %bb2, %bb1
         %reg109 = phi %node_t* [ %reg110, %bb2 ], [ %reg107, %bb1 ]             ; <%node_t*> [#uses=1]
         %reg212 = getelementptr %node_t, %node_t* %reg109, i64 0, i32 1          ; <%node_t**> [#uses=1]
         %reg110 = load %node_t*, %node_t** %reg212                ; <%node_t*> [#uses=2]
         %cond213 = icmp ne %node_t* %reg110, null               ; <i1> [#uses=1]
+; CHECK: br label %bb3
         br i1 %cond213, label %bb2, label %bb3
 
 bb3:            ; preds = %bb2, %bb1
         ret void
 }
 

llvm/trunk/test/Transforms/ADCE/2002-05-28-Crash-distilled.ll

 ; This testcase is a distilled form of: 2002-05-28-Crash.ll
 
 ; RUN: opt < %s -adce 
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define float @test(i32 %i) {
         %F = sitofp i32 %i to float             ; <float> [#uses=1]
         %I = bitcast i32 %i to i32              ; <i32> [#uses=1]
         br label %Loop
 
 Loop:           ; preds = %Loop, %0
         %B = icmp ne i32 %I, 0          ; <i1> [#uses=1]
+; CHECK:   br label %Out
         br i1 %B, label %Out, label %Loop
 
 Out:            ; preds = %Loop
         ret float %F
 }
 

llvm/trunk/test/Transforms/ADCE/2002-05-28-Crash.ll

 ; This testcase is distilled from the GNU rx package.  The loop should be 
 ; removed but causes a problem when ADCE does.  The source function is:
 ; int rx_bitset_empty (int size, rx_Bitset set) {
 ;  int x;
 ;  RX_subset s;
 ;  s = set[0];
 ;  set[0] = 1;
 ;  for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x)
 ;    ;
 ;  set[0] = s;
 ;  return !s;
 ;}
 ;
 ; RUN: opt < %s -adce
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define i32 @rx_bitset_empty(i32 %size, i32* %set) {
 bb1:
         %reg110 = load i32, i32* %set                ; <i32> [#uses=2]
         store i32 1, i32* %set
         %cast112 = sext i32 %size to i64                ; <i64> [#uses=1]
         %reg113 = add i64 %cast112, 31          ; <i64> [#uses=1]
         %reg114 = lshr i64 %reg113, 5           ; <i64> [#uses=2]
         %cast109 = trunc i64 %reg114 to i32             ; <i32> [#uses=1]
         %reg129 = add i32 %cast109, -1          ; <i32> [#uses=1]
         %reg114-idxcast = trunc i64 %reg114 to i32              ; <i32> [#uses=1]
         %reg114-idxcast-offset = add i32 %reg114-idxcast, 1073741823            ; <i32> [#uses=1]
         %reg114-idxcast-offset.upgrd.1 = zext i32 %reg114-idxcast-offset to i64         ; <i64> [#uses=1]
         %reg124 = getelementptr i32, i32* %set, i64 %reg114-idxcast-offset.upgrd.1           ; <i32*> [#uses=1]
         %reg125 = load i32, i32* %reg124             ; <i32> [#uses=1]
         %cond232 = icmp ne i32 %reg125, 0               ; <i1> [#uses=1]
+; CHECK: br label %bb3
         br i1 %cond232, label %bb3, label %bb2
 
 bb2:            ; preds = %bb2, %bb1
         %cann-indvar = phi i32 [ 0, %bb1 ], [ %add1-indvar, %bb2 ]              ; <i32> [#uses=2]
         %reg130-scale = mul i32 %cann-indvar, -1                ; <i32> [#uses=1]
         %reg130 = add i32 %reg130-scale, %reg129                ; <i32> [#uses=1]
         %add1-indvar = add i32 %cann-indvar, 1          ; <i32> [#uses=1]
         %reg130-idxcast = bitcast i32 %reg130 to i32            ; <i32> [#uses=1]

llvm/trunk/test/Transforms/ADCE/2002-07-17-AssertionFailure.ll

 ; This testcase fails because ADCE does not correctly delete the chain of 
 ; three instructions that are dead here.  Ironically there were a dead basic
 ; block in this function, it would work fine, but that would be the part we 
 ; have to fix now, wouldn't it....
 ;
-; RUN: opt < %s -adce
+; RUN: opt < %s -adce -S | FileCheck %s
 
 define void @foo(i8* %reg5481) {
         %cast611 = bitcast i8* %reg5481 to i8**         ; <i8**> [#uses=1]
         %reg162 = load i8*, i8** %cast611            ; <i8*> [#uses=1]
+; CHECK-NOT: ptrtoint
         ptrtoint i8* %reg162 to i32             ; <i32>:1 [#uses=0]
         ret void
 }

llvm/trunk/test/Transforms/ADCE/2002-07-17-PHIAssertion.ll

 ; This testcase was extracted from the gzip SPEC benchmark
 ;
-; RUN: opt < %s -adce
+; RUN: opt < %s -adce | FileCheck %s
 
 @bk = external global i32               ; <i32*> [#uses=2]
 @hufts = external global i32            ; <i32*> [#uses=1]
 
 define i32 @inflate() {
 bb0:
         br label %bb2
 
 bb2:            ; preds = %bb6, %bb0
         %reg128 = phi i32 [ %reg130, %bb6 ], [ 0, %bb0 ]                ; <i32> [#uses=2]
         br i1 true, label %bb4, label %bb3
 
 bb3:            ; preds = %bb2
         br label %UnifiedExitNode
 
+; CHECK-NOT: bb4:
+; CHECK-NOT: bb5:
 bb4:            ; preds = %bb2
         %reg117 = load i32, i32* @hufts              ; <i32> [#uses=2]
         %cond241 = icmp ule i32 %reg117, %reg128                ; <i1> [#uses=1]
         br i1 %cond241, label %bb6, label %bb5
 
 bb5:            ; preds = %bb4
         br label %bb6
 

llvm/trunk/test/Transforms/ADCE/2002-07-29-Segfault.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -disable-output -adce-remove-loops
 
 define void @test() {
         br label %BB3
 
 BB3:            ; preds = %BB3, %0
         br label %BB3
 }
 

llvm/trunk/test/Transforms/ADCE/2003-01-22-PredecessorProblem.ll

 ; Testcase reduced from 197.parser by bugpoint
 ; RUN: opt < %s -adce 
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define void @conjunction_prune() {
 ; <label>:0
         br label %bb19
 
 bb19:           ; preds = %bb23, %bb22, %0
         %reg205 = phi i8* [ null, %bb22 ], [ null, %bb23 ], [ null, %0 ]                ; <i8*> [#uses=1]
+; CHECK: br label %bb22
         br i1 false, label %bb21, label %bb22
 
 bb21:           ; preds = %bb19
         %cast455 = bitcast i8* %reg205 to i8**          ; <i8**> [#uses=0]
+; CHECK: br label %bb22
         br label %bb22
 
 bb22:           ; preds = %bb21, %bb19
+; CHECK: br label %bb23
         br i1 false, label %bb19, label %bb23
 
 bb23:           ; preds = %bb22
+; CHECK: br label %bb28
         br i1 false, label %bb19, label %bb28
 
 bb28:           ; preds = %bb23
         ret void
 }
 

llvm/trunk/test/Transforms/ADCE/2003-04-25-PHIPostDominateProblem.ll

 ; THis testcase caused an assertion failure because a PHI node did not have 
 ; entries for it's postdominator.  But I think this can only happen when the 
 ; PHI node is dead, so we just avoid patching up dead PHI nodes.
 
-; RUN: opt < %s -adce
+; RUN: opt < %s -adce                    -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 target datalayout = "e-p:32:32"
 
 define void @dead_test8() {
 entry:
         br label %loopentry
 
 loopentry:              ; preds = %endif, %entry
         %k.1 = phi i32 [ %k.0, %endif ], [ 0, %entry ]          ; <i32> [#uses=1]
         br i1 false, label %no_exit, label %return
 
 no_exit:                ; preds = %loopentry
+; CHECK: br label %then
         br i1 false, label %then, label %else
 
 then:           ; preds = %no_exit
         br label %endif
 
 else:           ; preds = %no_exit
         %dec = add i32 %k.1, -1         ; <i32> [#uses=1]
         br label %endif

llvm/trunk/test/Transforms/ADCE/2003-06-11-InvalidCFG.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 @G = external global i32*               ; <i32**> [#uses=1]
 
 declare void @Fn(i32*)
 
 define i32 @main(i32 %argc.1, i8** %argv.1) {
 entry:
         br label %endif.42

llvm/trunk/test/Transforms/ADCE/2003-06-24-BadSuccessor.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops=true -disable-output
+
 target datalayout = "e-p:32:32"
   %struct..CppObjTypeDesc = type { i32, i16, i16 }
   %struct..TypeToken = type { i32, i16, i16 }
 
 define i32 @C_ReFaxToDb() {
 entry:
   br i1 false, label %endif.0, label %then.0
 

 endif.14:   ; preds = %loopentry.0
   br i1 false, label %loopentry.1, label %loopentry.0
 
 loopentry.1:    ; preds = %then.53, %endif.14
   %SubArrays.10 = phi i32* [ %SubArrays.8, %then.53 ], [ null, %endif.14 ]    ; <i32*> [#uses=3]
   br i1 false, label %no_exit.1, label %loopentry.0
 
 no_exit.1:    ; preds = %loopentry.1
+; CHECK: switch
   switch i32 0, label %label.17 [
      i32 2, label %label.11
      i32 19, label %label.10
   ]
 
 label.10:   ; preds = %no_exit.1
   br i1 false, label %then.43, label %endif.43
 

llvm/trunk/test/Transforms/ADCE/2003-06-24-BasicFunctionality.ll

-; RUN: opt < %s -adce -simplifycfg -S | not grep then:
+; RUN: opt < %s -adce -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
 
 define void @dead_test8(i32* %data.1, i32 %idx.1) {
 entry:
         %tmp.1 = load i32, i32* %data.1              ; <i32> [#uses=2]
         %tmp.41 = icmp sgt i32 %tmp.1, 0                ; <i1> [#uses=1]
         br i1 %tmp.41, label %no_exit.preheader, label %return
 
 no_exit.preheader:              ; preds = %entry
         %tmp.11 = getelementptr i32, i32* %data.1, i64 1             ; <i32*> [#uses=1]
         %tmp.22-idxcast = sext i32 %idx.1 to i64                ; <i64> [#uses=1]
         %tmp.28 = getelementptr i32, i32* %data.1, i64 %tmp.22-idxcast               ; <i32*> [#uses=1]
         br label %no_exit
 
 no_exit:                ; preds = %endif, %no_exit.preheader
         %k.1 = phi i32 [ %k.0, %endif ], [ 0, %no_exit.preheader ]              ; <i32> [#uses=3]
         %i.0 = phi i32 [ %inc.1, %endif ], [ 0, %no_exit.preheader ]            ; <i32> [#uses=1]
         %tmp.12 = load i32, i32* %tmp.11             ; <i32> [#uses=1]
         %tmp.14 = sub i32 0, %tmp.12            ; <i32> [#uses=1]
+; CHECK-NOT: %tmp.161
         %tmp.161 = icmp ne i32 %k.1, %tmp.14            ; <i1> [#uses=1]
+; CHECK: br label %then
         br i1 %tmp.161, label %then, label %else
 
 then:           ; preds = %no_exit
         %inc.0 = add i32 %k.1, 1                ; <i32> [#uses=1]
         br label %endif
 
 else:           ; preds = %no_exit
         %dec = add i32 %k.1, -1         ; <i32> [#uses=1]

llvm/trunk/test/Transforms/ADCE/2003-09-15-InfLoopCrash.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 define i32 @main() {
         br label %loop
 
 loop:           ; preds = %loop, %0
         br label %loop
 }
 

llvm/trunk/test/Transforms/ADCE/2003-11-16-MissingPostDominanceInfo.ll

 ; RUN: opt < %s -adce -simplifycfg -S | grep call
+; RUN: opt < %s -adce -adce-remove-loops -simplifycfg -S | grep call
+
 declare void @exit(i32)
 
 define i32 @main(i32 %argc) {
         %C = icmp eq i32 %argc, 1               ; <i1> [#uses=2]
         br i1 %C, label %Cond, label %Done
 
 Cond:           ; preds = %0
         br i1 %C, label %Loop, label %Done

llvm/trunk/test/Transforms/ADCE/2004-05-04-UnreachableBlock.ll

 ; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -disable-output
 
 define void @test() {
 entry:
         br label %UnifiedReturnBlock
 
 UnifiedReturnBlock:             ; preds = %invoke_catch.0, %entry
         ret void
 
 invoke_catch.0:         ; No predecessors!
         br i1 false, label %UnifiedUnwindBlock, label %UnifiedReturnBlock
 
 UnifiedUnwindBlock:             ; preds = %invoke_catch.0
         unreachable
 }
 

llvm/trunk/test/Transforms/ADCE/2016-09-06.ll

+; RUN: opt < %s -sroa -adce -adce-remove-loops -S | FileCheck %s
+; ModuleID = 'test1.bc'
+source_filename = "test1.c"
+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
+define i32 @foo(i32, i32, i32) #0 {
+  %4 = alloca i32, align 4
+  %5 = alloca i32, align 4
+  %6 = alloca i32, align 4
+  %7 = alloca i32, align 4
+  %8 = alloca i32, align 4
+  store i32 %0, i32* %4, align 4
+  store i32 %1, i32* %5, align 4
+  store i32 %2, i32* %6, align 4
+  store i32 0, i32* %7, align 4
+  %9 = load i32, i32* %5, align 4
+  %I10 = icmp ne i32 %9, 0
+  br i1 %I10, label %B11, label %B21
+
+B11: 
+  store i32 0, i32* %8, align 4
+  br label %B12
+
+B12:
+  %I13 = load i32, i32* %8, align 4
+  %I14 = load i32, i32* %6, align 4
+  %I15 = icmp slt i32 %I13, %I14
+; CHECK: br label %B20
+  br i1 %I15, label %B16, label %B20
+
+B16: 
+  br label %B17
+
+B17: 
+  %I18 = load i32, i32* %8, align 4
+  %I19 = add nsw i32 %I18, 1
+  store i32 %I19, i32* %8, align 4
+  br label %B12
+
+B20:
+  store i32 1, i32* %7, align 4
+  br label %B21
+
+B21: 
+  %I22 = load i32, i32* %7, align 4
+  ret i32 %I22
+}
+
+attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 4.0.0 (http://llvm.org/git/clang.git 5864a13abf4490e76ae2eb0896198e1305927df2)"}

llvm/trunk/test/Transforms/ADCE/basictest1.ll

-; RUN: opt < %s -adce -simplifycfg | llvm-dis  
+; RUN: opt < %s -adce -S | FileCheck %s
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
+
 %FILE = type { i32, i8*, i8*, i8, i8, i32, i32, i32 }
   %spec_fd_t = type { i32, i32, i32, i8* }
 @__iob = external global [20 x %FILE]    ; <[20 x %FILE]*> [#uses=1]
 @dbglvl = global i32 4    ; <i32*> [#uses=3]
 @spec_fd = external global [3 x %spec_fd_t]    ; <[3 x %spec_fd_t]*> [#uses=4]
 @.LC9 = internal global [34 x i8] c"spec_read: fd=%d, > MAX_SPEC_FD!\0A\00"    ; <[34 x i8]*> [#uses=1]
 @.LC10 = internal global [4 x i8] c"EOF\00"    ; <[4 x i8]*> [#uses=1]
 @.LC11 = internal global [4 x i8] c"%d\0A\00"    ; <[4 x i8]*> [#uses=1]

 
 declare i32 @fwrite(i8*, i32, i32, %FILE*)
 
 declare void @perror(i8*)
 
 define i32 @spec_getc(i32 %fd) {
   %reg109 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond266 = icmp sle i32 %reg109, 4    ; <i1> [#uses=1]
+; CHECKL br label %bb3
   br i1 %cond266, label %bb3, label %bb2
 
 bb2:    ; preds = %0
   %cast273 = getelementptr [17 x i8], [17 x i8]* @.LC12, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb3
 
 bb3:    ; preds = %bb2, %0
   %cond267 = icmp sle i32 %fd, 3    ; <i1> [#uses=1]
bb5:    ; preds = %bb3
   %idx2 = getelementptr %spec_fd_t, %spec_fd_t* %reg1311, i64 0, i32 1    ; <i32*> [#uses=1]
   %reg1331 = load i32, i32* %idx2    ; <i32> [#uses=1]
   %cond270 = icmp slt i32 %reg1321, %reg1331    ; <i1> [#uses=1]
   br i1 %cond270, label %bb9, label %bb6
 
 bb6:    ; preds = %bb5
   %reg134 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond271 = icmp sle i32 %reg134, 4    ; <i1> [#uses=1]
+; CHECK: br label %bb8
   br i1 %cond271, label %bb8, label %bb7
 
 bb7:    ; preds = %bb6
   %cast277 = getelementptr [4 x i8], [4 x i8]* @.LC10, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb8
 
 bb8:    ; preds = %bb7, %bb6
   br label %UnifiedExitNode
 
 bb9:    ; preds = %bb5
   %reg107-idxcast3 = sext i32 %fd to i64    ; <i64> [#uses=1]
   %idx3 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast3, i32 3    ; <i8**> [#uses=1]
   %reg1601 = load i8*, i8** %idx3    ; <i8*> [#uses=1]
   %reg132-idxcast1 = sext i32 %reg1321 to i64    ; <i64> [#uses=1]
   %idx4 = getelementptr i8, i8* %reg1601, i64 %reg132-idxcast1    ; <i8*> [#uses=1]
   %reg1621 = load i8, i8* %idx4    ; <i8> [#uses=2]
   %cast108 = zext i8 %reg1621 to i64    ; <i64> [#uses=0]
   %reg157 = add i32 %reg1321, 1   ; <i32> [#uses=1]
   %idx5 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast1, i32 2    ; <i32*> [#uses=1]
   store i32 %reg157, i32* %idx5
   %reg163 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond272 = icmp sle i32 %reg163, 4    ; <i1> [#uses=1]
+; CHECK: br label %bb11
   br i1 %cond272, label %bb11, label %bb10
 
 bb10:   ; preds = %bb9
   %cast279 = getelementptr [4 x i8], [4 x i8]* @.LC11, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb11
 
 bb11:   ; preds = %bb10, %bb9
   %cast291 = zext i8 %reg1621 to i32    ; <i32> [#uses=1]

llvm/trunk/test/Transforms/ADCE/basictest2.ll

-; RUN: opt < %s -adce -simplifycfg | llvm-dis
+; RUN: opt < %s -adce -disable-output
+; RUN: opt < %s -adce -adce-remove-loops -S | FileCheck %s
+
   %FILE = type { i32, i8*, i8*, i8, i8, i32, i32, i32 }
   %spec_fd_t = type { i32, i32, i32, i8* }
 @__iob = external global [20 x %FILE]    ; <[20 x %FILE]*> [#uses=1]
 @dbglvl = global i32 4    ; <i32*> [#uses=3]
 @spec_fd = external global [3 x %spec_fd_t]    ; <[3 x %spec_fd_t]*> [#uses=4]
 @.LC9 = internal global [34 x i8] c"spec_read: fd=%d, > MAX_SPEC_FD!\0A\00"    ; <[34 x i8]*> [#uses=1]
 @.LC10 = internal global [4 x i8] c"EOF\00"    ; <[4 x i8]*> [#uses=1]
 @.LC11 = internal global [4 x i8] c"%d\0A\00"    ; <[4 x i8]*> [#uses=1]

 
 declare i32 @fwrite(i8*, i32, i32, %FILE*)
 
 declare void @perror(i8*)
 
 define i32 @spec_getc(i32 %fd) {
   %reg109 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond266 = icmp sle i32 %reg109, 4    ; <i1> [#uses=1]
+; CHECK: br label %bb3
   br i1 %cond266, label %bb3, label %bb2
 
 bb2:    ; preds = %0
   %cast273 = getelementptr [17 x i8], [17 x i8]* @.LC12, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb3
 
 bb3:    ; preds = %bb2, %0
   %cond267 = icmp sle i32 %fd, 3    ; <i1> [#uses=0]
bb5:    ; preds = %bb3
   %idx2 = getelementptr %spec_fd_t, %spec_fd_t* %reg1311, i64 0, i32 1    ; <i32*> [#uses=1]
   %reg1331 = load i32, i32* %idx2    ; <i32> [#uses=1]
   %cond270 = icmp slt i32 %reg1321, %reg1331    ; <i1> [#uses=1]
   br i1 %cond270, label %bb9, label %bb6
 
 bb6:    ; preds = %bb5
   %reg134 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond271 = icmp sle i32 %reg134, 4    ; <i1> [#uses=1]
+; CHECK: br label %bb8
   br i1 %cond271, label %bb8, label %bb7
 
 bb7:    ; preds = %bb6
   %cast277 = getelementptr [4 x i8], [4 x i8]* @.LC10, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb8
 
 bb8:    ; preds = %bb7, %bb6
   br label %UnifiedExitNode
 
 bb9:    ; preds = %bb5
   %reg107-idxcast3 = sext i32 %fd to i64    ; <i64> [#uses=1]
   %idx3 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast3, i32 3    ; <i8**> [#uses=1]
   %reg1601 = load i8*, i8** %idx3    ; <i8*> [#uses=1]
   %reg132-idxcast1 = sext i32 %reg1321 to i64    ; <i64> [#uses=1]
   %idx4 = getelementptr i8, i8* %reg1601, i64 %reg132-idxcast1    ; <i8*> [#uses=1]
   %reg1621 = load i8, i8* %idx4    ; <i8> [#uses=2]
   %cast108 = zext i8 %reg1621 to i64    ; <i64> [#uses=0]
   %reg157 = add i32 %reg1321, 1   ; <i32> [#uses=1]
   %idx5 = getelementptr [3 x %spec_fd_t], [3 x %spec_fd_t]* @spec_fd, i64 0, i64 %reg107-idxcast1, i32 2    ; <i32*> [#uses=1]
   store i32 %reg157, i32* %idx5
   %reg163 = load i32, i32* @dbglvl    ; <i32> [#uses=1]
   %cond272 = icmp sle i32 %reg163, 4    ; <i1> [#uses=1]
+; CHECK: br label %bb11
   br i1 %cond272, label %bb11, label %bb10
 
 bb10:   ; preds = %bb9
   %cast279 = getelementptr [4 x i8], [4 x i8]* @.LC11, i64 0, i64 0    ; <i8*> [#uses=0]
   br label %bb11
 
 bb11:   ; preds = %bb10, %bb9
   %cast291 = zext i8 %reg1621 to i32    ; <i32> [#uses=1]