hasPath

[nlewycky]

Summary

Reimplement hasPath and put it in new CFG.h with the non-transforming parts of BasicBlockUtils.h

[chandlerc]

Reviewed it pretty thoroughly now from the API side and the core analysis logic side. Sorry for the nit picks, just commented as stuff caught my eye. The substantive comments are there as well. Anyways, detailed comments inline.

One set of test cases I'd like to see are cases where the tricks to avoid successor walks allow us to scale up better. IE, lots of tiny blocks that we skip w/ loop info (or maybe domtree).

The comments are a mixture of "please fix this" and questions or ideas for future stuff that I think would be good to do. Once the first group are addressed, I'm happy for you to commit whenever and we can continue the discussion here or in whatever forum works best. I'm not worried about seeing the fixes for the things that are obvious, and the things that aren't obvious seem likely to end up in their own separate patch anyways. So, with changes requested, LGTM.

include/llvm/Analysis/CFG.h

36

Want to reformat the code you're moving in this patch? Your call, I know this is a move.

52

I think it would be useful to give some guidance about the performance (big-O complexity based) that users should expect to help guide callers.

I would also add a brief one-line comment.

53

Would it be useful to include a convenience overload that works in terms of BBs?

Also, why not references to instructions? Can these usefully be null?

lib/Analysis/CFG.cpp

117–126

Not for this change, but I would like to see this added to LoopInfo's interface so others can find it rather than re-inventing it.

128–134

This also seems useful in LoopInfo. I would also potentially phrase it there in a more general form as 'loopContains(...)' which accepts 1, 2, or maybe more basic block (or instruction) arguments... But maybe this is the only case that comes up.

136–138

Don't duplicate the doxygen comment...

145–148

I would hoist this into a static helper function which can then carry this comment.

151–159

I think I would rewrite this whole thing as this to make it a bit more clear what's going on... Not sure how you feel about it though.

// We can't handle loops. As a consequence, we can only reason about the entry block
// without loop info.
if ((LI && LI->getLoopFor(BB) != 0) ||
    (!LI && BB != &BB->getParent()->getEntryBlock())
  return true;

161–163

mem2reg keeps a cache of instruction indices within a block to make repeated queries for the same basic block fast -- do you envision this being useful for callers of this API?

172

Comment why the limit is 32?

Make this a constant?

Make this a command line flag for debugging?

173–174

I much prefer 'Visited' to 'EverQueued'.

I also find it more conventional and easier to read 'Worklist' as a single word.

179–182

Do this before setting up the worklist. It makes more sense with the other special cases. Also, s/NULL/0/

193

Comment clearly that this is the conservative exit from the loop in the case where we don't know anything.

Also, I would put the return on its own line for consistency.

200

Does this have append semantics? If not, give it append semantics?

Then you can append onto your worklist and do the equivalent of std::remove to skip the visited blocks.

If not, at least hoist this vector out of the loop and use clear to reset it. I suspect it can also benefit from a smaller base size than '32'.

205–211

Could we do a similar trick with the domtree as the loopinfo?

Specifically, could we immediately sink to the leaves of the blocks domtree? That would allow us to skip over arbitrarily long chains of basic blocks rather than walking each one.

Clearly, adding this could go in a follow-up patch.

213

Comment that the reason we say 'false' here is that we have exhausted the possible paths, and thus know that it is in fact unreachable.

[nlewycky]

Thanks for the review! I'm going to submit this shortly, but I'll be happy to make further changes in followup patches.

include/llvm/Analysis/CFG.h

36

Done, clang-format'd.

52

Great idea, I've written a chunk about the cost. I'd rather have something more like the complexity guarantees on something like the C++ standard, but ended up with a description of the algorithm. It'll do.

I tried and failed to write a \brief within 80-columns.

53

It's uncommon to use references to IR in llvm. You're right that they can't be null, but I have an irrational dislike of this change. Sorry.

lib/Analysis/CFG.cpp

117–126

Agreed.

128–134

This code is unusual in that we always want to look at the outermost loop, while most users of Loop do not. We might want to move this to LoopInfo, but I would need to think hard about that.

136–138

Done.

151–159

Hm, your comment made me realize that this code is suboptimal in the case where LI is NULL.

It's not exactly right that we can't handle loops. Rather, if we're inside a loop then it's possible to reach any instruction in the block from any other instruction in the block just by going around the backedge. Thus the answer for loops is a truthful and correct true, not merely a conservative "true". I've updated the comments.

However, in the case where LI is null, we shouldn't bail out and return true here. Instead we should go into the per-block scanning. It may be that this block has no successors for instance, and we can prove that we don't reach BB. I'll save that for a future patch, the fix is not as simple as my first attempt.

161–163

I don't, I expect that at least one side (From or To) will be varying in parent BB with each call. I do expect to reuse the same To many times, for instance.

172

Comment why the limit is 32?

Done.

Make this a constant?

CFG.cpp:205:12: error: decrement of read-only variable ‘Limit’

Make this a command line flag for debugging?

Or make it an argument to the caller? I'll leave it for now as it's easy to change if we want to do either of these things.

173–174

I much prefer 'Visited' to 'EverQueued'.

Okay, I've switched the style to use a Visited+continue at the top.

I also find it more conventional and easier to read 'Worklist' as a single word.

Yep. Done.

179–182

Done.

193

Done.

200

It does have append semantics. Since switching to 'visited' form, I can remove Exits and the need for filtering the Worklist entirely (we just filter at the top of the loop).

205–211

I don't think so. Given a partial domtree with nodes J K and L and edges J->K K->L, we can't sink straight from J to L. There's no guarantee that K doesn't have a successor we can ignore (it could have an edge to A which in turn dominates J).

That doesn't mean we couldn't make some use of domtree, but what you're asking for is a dominance frontier, and we would end up implementing the iterated dominance frontier algorithm in here, at which point it's more sensible to tell callers that they should pass in a loopinfo. This is exactly what loopinfo gives us.

213

Done!

[chandlerc]

just FYI follow-up...

include/llvm/Analysis/CFG.h

52

You don't have to fit brief comments in 80-columns.

53

You replied to the second of my comments but not the first. ;] The first was the more important. Also, if your dislike is irrational, that says to me you should perhaps make the change.

lib/Analysis/CFG.cpp

145–148

?

[Eugene.Zelenko]

Looks like patch was not committed.

include/llvm/Analysis/CFG.h

+//===-- Analysis/CFG.h - BasicBlock Analyses --------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions performs analyses on basic blocks, and instructions
+// contained within basic blocks.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CFG_H
+#define LLVM_ANALYSIS_CFG_H
+
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/Support/CFG.h"
+
+namespace llvm {
+
+class BasicBlock;
+class DominatorTree;
+class Function;
+class Instruction;
+class LoopInfo;
+class TerminatorInst;
+
+/// Analyze the specified function to find all of the loop backedges in the
+/// function and return them.  This is a relatively cheap (compared to
+/// computing dominators and loop info) analysis.
+///
+/// The output is added to Result, as pairs of <from,to> edge info.
+void FindFunctionBackedges(const Function &F,
+      SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result);
+
+/// Search for the specified successor of basic block BB and return its position
+/// in the terminator instruction's list of successors.  It is an error to call
+/// this with a block that is not a successor.
+unsigned GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ);
+
+/// Return true if the specified edge is a critical edge. Critical edges are
+/// edges from a block with multiple successors to a block with multiple
+/// predecessors.
+///
+bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
+                    bool AllowIdenticalEdges = false);
+
+/// Determine whether there is a path from From to To within a single function.
+/// Returns false only if we can prove that once 'From' has been executed then
+/// 'To' can not be executed. Conservatively returns true.
+bool isPotentiallyReachable(const Instruction *From, const Instruction *To,
+                            DominatorTree *DT = 0, LoopInfo *LI = 0);
+
+} // End llvm namespace
+
+#endif

include/llvm/Transforms/Utils/BasicBlockUtils.h

 void ReplaceInstWithInst(BasicBlock::InstListType &BIL,
                          BasicBlock::iterator &BI, Instruction *I);
 
 // ReplaceInstWithInst - Replace the instruction specified by From with the
 // instruction specified by To.
 //
 void ReplaceInstWithInst(Instruction *From, Instruction *To);
 
-/// FindFunctionBackedges - Analyze the specified function to find all of the
-/// loop backedges in the function and return them.  This is a relatively cheap
-/// (compared to computing dominators and loop info) analysis.
-///
-/// The output is added to Result, as pairs of <from,to> edge info.
-void FindFunctionBackedges(const Function &F,
-      SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result);
-
-
-/// GetSuccessorNumber - Search for the specified successor of basic block BB
-/// and return its position in the terminator instruction's list of
-/// successors.  It is an error to call this with a block that is not a
-/// successor.
-unsigned GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ);
-
-/// isCriticalEdge - Return true if the specified edge is a critical edge.
-/// Critical edges are edges from a block with multiple successors to a block
-/// with multiple predecessors.
-///
-bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
-                    bool AllowIdenticalEdges = false);
-
 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
 /// split the critical edge.  This will update DominatorTree and
 /// DominatorFrontier information if it is available, thus calling this pass
 /// will not invalidate either of them. This returns the new block if the edge
 /// was split, null otherwise.
 ///
 /// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the
 /// specified successor will be merged into the same critical edge block.

lib/Analysis/AliasAnalysis.cpp

 // handles lots of little corner cases, other, more complex, alias analysis
 // implementations may choose to rely on this pass to resolve these simple and
 // easy cases.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
AliasAnalysis::getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc) {
   // If the atomicrmw address does not alias the location, it does not access it.
   if (!alias(getLocation(RMW), Loc))
     return NoModRef;
 
   return ModRef;
 }
 
 namespace {
-  // Conservatively return true. Return false, if there is a single path
-  // starting from "From" and the path does not reach "To".
-  static bool hasPath(const BasicBlock *From, const BasicBlock *To) {
-    const unsigned MaxCheck = 5;
-    const BasicBlock *Current = From;
-    for (unsigned I = 0; I < MaxCheck; I++) {
-      unsigned NumSuccs = Current->getTerminator()->getNumSuccessors();
-      if (NumSuccs > 1)
-        return true;
-      if (NumSuccs == 0)
-        return false;
-      Current = Current->getTerminator()->getSuccessor(0);
-      if (Current == To)
-        return true;
-    }
-    return true;
-  }
-
   /// Only find pointer captures which happen before the given instruction. Uses
   /// the dominator tree to determine whether one instruction is before another.
   /// Only support the case where the Value is defined in the same basic block
   /// as the given instruction and the use.
   struct CapturesBefore : public CaptureTracker {
     CapturesBefore(const Instruction *I, DominatorTree *DT)
       : BeforeHere(I), DT(DT), Captured(false) {}
 
     void tooManyUses() { Captured = true; }
 
     bool shouldExplore(Use *U) {
       Instruction *I = cast<Instruction>(U->getUser());
       BasicBlock *BB = I->getParent();
       // We explore this usage only if the usage can reach "BeforeHere".
       // If use is not reachable from entry, there is no need to explore.
       if (BeforeHere != I && !DT->isReachableFromEntry(BB))
         return false;
       // If the value is defined in the same basic block as use and BeforeHere,
       // there is no need to explore the use if BeforeHere dominates use.
       // Check whether there is a path from I to BeforeHere.
       if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
-          !hasPath(BB, BeforeHere->getParent()))
+          !isPotentiallyReachable(I, BeforeHere, DT))
         return false;
       return true;
     }
 
     bool captured(Use *U) {
       Instruction *I = cast<Instruction>(U->getUser());
       BasicBlock *BB = I->getParent();
       // Same logic as in shouldExplore.
       if (BeforeHere != I && !DT->isReachableFromEntry(BB))
         return false;
       if (BeforeHere != I && DT->dominates(BeforeHere, I) &&
-          !hasPath(BB, BeforeHere->getParent()))
+          !isPotentiallyReachable(I, BeforeHere, DT))
         return false;
       Captured = true;
       return true;
     }
 
     const Instruction *BeforeHere;
     DominatorTree *DT;
 

lib/Analysis/CFG.cpp

+//===-- CFG.cpp - BasicBlock analysis --------------------------------------==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions performs analyses on basic blocks, and instructions
+// contained within basic blocks.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CFG.h"
+
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/LoopInfo.h"
+
+using namespace llvm;
+
+/// FindFunctionBackedges - Analyze the specified function to find all of the
+/// loop backedges in the function and return them.  This is a relatively cheap
+/// (compared to computing dominators and loop info) analysis.
+///
+/// The output is added to Result, as pairs of <from,to> edge info.
+void llvm::FindFunctionBackedges(const Function &F,
+     SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
+  const BasicBlock *BB = &F.getEntryBlock();
+  if (succ_begin(BB) == succ_end(BB))
+    return;
+
+  SmallPtrSet<const BasicBlock*, 8> Visited;
+  SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
+  SmallPtrSet<const BasicBlock*, 8> InStack;
+
+  Visited.insert(BB);
+  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
+  InStack.insert(BB);
+  do {
+    std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
+    const BasicBlock *ParentBB = Top.first;
+    succ_const_iterator &I = Top.second;
+
+    bool FoundNew = false;
+    while (I != succ_end(ParentBB)) {
+      BB = *I++;
+      if (Visited.insert(BB)) {
+        FoundNew = true;
+        break;
+      }
+      // Successor is in VisitStack, it's a back edge.
+      if (InStack.count(BB))
+        Result.push_back(std::make_pair(ParentBB, BB));
+    }
+
+    if (FoundNew) {
+      // Go down one level if there is a unvisited successor.
+      InStack.insert(BB);
+      VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
+    } else {
+      // Go up one level.
+      InStack.erase(VisitStack.pop_back_val().first);
+    }
+  } while (!VisitStack.empty());
+}
+
+/// GetSuccessorNumber - Search for the specified successor of basic block BB
+/// and return its position in the terminator instruction's list of
+/// successors.  It is an error to call this with a block that is not a
+/// successor.
+unsigned llvm::GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ) {
+  TerminatorInst *Term = BB->getTerminator();
+#ifndef NDEBUG
+  unsigned e = Term->getNumSuccessors();
+#endif
+  for (unsigned i = 0; ; ++i) {
+    assert(i != e && "Didn't find edge?");
+    if (Term->getSuccessor(i) == Succ)
+      return i;
+  }
+}
+
+/// isCriticalEdge - Return true if the specified edge is a critical edge.
+/// Critical edges are edges from a block with multiple successors to a block
+/// with multiple predecessors.
+bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
+                          bool AllowIdenticalEdges) {
+  assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
+  if (TI->getNumSuccessors() == 1) return false;
+
+  const BasicBlock *Dest = TI->getSuccessor(SuccNum);
+  const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
+
+  // If there is more than one predecessor, this is a critical edge...
+  assert(I != E && "No preds, but we have an edge to the block?");
+  const BasicBlock *FirstPred = *I;
+  ++I;        // Skip one edge due to the incoming arc from TI.
+  if (!AllowIdenticalEdges)
+    return I != E;
+
+  // If AllowIdenticalEdges is true, then we allow this edge to be considered
+  // non-critical iff all preds come from TI's block.
+  while (I != E) {
+    const BasicBlock *P = *I;
+    if (P != FirstPred)
+      return true;
+    // Note: leave this as is until no one ever compiles with either gcc 4.0.1
+    // or Xcode 2. This seems to work around the pred_iterator assert in PR 2207
+    E = pred_end(P);
+    ++I;
+  }
+  return false;
+}
+
+// LoopInfo contains a mapping from basic block to the innermost loop. Find
+// the outermost loop in the loop nest that contains BB.
+static const Loop *getOutermostLoop(LoopInfo *LI, const BasicBlock *BB) {
+  const Loop *L = LI->getLoopFor(BB);
+  if (L) {
+    while (const Loop *Parent = L->getParentLoop())
+      L = Parent;
+  }
+  return L;
+}
+
+// True if there is a loop which contains both BB1 and BB2.
+static bool loopContainsBoth(LoopInfo *LI,
+                             const BasicBlock *BB1, const BasicBlock *BB2) {
+  const Loop *L1 = getOutermostLoop(LI, BB1);
+  const Loop *L2 = getOutermostLoop(LI, BB2);
+  return L1 != NULL && L1 == L2;
+}
+
+/// Determine whether there is a path from From to To within a single function.
+/// Returns false only if we can prove that once 'From' has been executed then
+/// 'To' can not be executed. Conservatively returns true.
+bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B,
+                                  DominatorTree *DT, LoopInfo *LI) {
+  assert(A->getParent()->getParent() == B->getParent()->getParent() &&
+         "This analysis is function-local!");
+
+  if (A->getParent() == B->getParent()) {
+    // The same block case is special because it's the only time we're looking
+    // within a single block to see which comes first. Once we start looking at
+    // multiple blocks, the first instruction of the block is reachable, so we
+    // only need to determine reachability between whole blocks.
+
+    const BasicBlock *BB = A->getParent();
+    // Can't be in a loop if it's the entry block -- the entry block may not
+    // have predecessors.
+    bool HasLoop = BB != &BB->getParent()->getEntryBlock();
+
+    // Can't be in a loop if LoopInfo doesn't know about it.
+    if (LI && HasLoop) {
+      HasLoop = LI->getLoopFor(BB) != 0;
+    }
+    if (HasLoop) return true;
+
+    // Linear scan, start at 'A', see whether we hit 'B' or the end first.
+    for (BasicBlock::const_iterator BBI = A, BBE = BB->end(); BBI != BBE; ++BBI)
+      if (&*BBI == B) return true;
+    return false;
+  }
+
+  if (A->getParent() == &A->getParent()->getParent()->getEntryBlock())
+    return true;
+  if (B->getParent() == &A->getParent()->getParent()->getEntryBlock())
+    return false;
+
+  unsigned Limit = 32;
+  SmallSet<const BasicBlock*, 64> EverQueued;
+  SmallVector<const BasicBlock*, 32> WorkList;
+  WorkList.push_back(A->getParent());
+  const BasicBlock *StopBB = B->getParent();
+  EverQueued.insert(WorkList.back());
+
+  // When the stop block is unreachable, it's dominated from everywhere,
+  // regardless of whether there's a path between the two blocks.
+  if (DT && !DT->isReachableFromEntry(StopBB))
+    DT = NULL;
+
+  do {
+    const BasicBlock *BB = WorkList.pop_back_val();
+    if (BB == StopBB)
+      return true;
+    if (DT && DT->dominates(BB, StopBB))
+      return true;
+    if (LI && loopContainsBoth(LI, BB, StopBB))
+      return true;
+
+    if (!--Limit) return true;
+
+    if (const Loop *Outer = LI ? getOutermostLoop(LI, BB) : 0) {
+      // All blocks in a single loop are reachable from all other blocks. From
+      // any of these blocks, we can skip directly to the exits of the loop,
+      // ignoring any other blocks inside the loop body.
+      SmallVector<BasicBlock*, 32> Exits;
+      Outer->getExitBlocks(Exits);
+      for (unsigned i = 0, e = Exits.size(); i != e; ++i) {
+        if (EverQueued.insert(Exits[i]))
+          WorkList.push_back(Exits[i]);
+      }
+    } else {
+      for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E;
+           ++I) {
+        if (EverQueued.insert(*I))
+          WorkList.push_back(*I);
+      }
+    }
+  } while (!WorkList.empty());
+  return false;
+}

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

 #define DEBUG_TYPE "isel"
 #include "llvm/CodeGen/SelectionDAGISel.h"
 #include "ScheduleDAGSDNodes.h"
 #include "SelectionDAGBuilder.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/FastISel.h"
 #include "llvm/CodeGen/FunctionLoweringInfo.h"
 #include "llvm/CodeGen/GCMetadata.h"
 #include "llvm/CodeGen/GCStrategy.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"

lib/Transforms/Scalar/GVN.cpp

 #define DEBUG_TYPE "gvn"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/PHITransAddr.h"
 #include "llvm/Analysis/ValueTracking.h"

lib/Transforms/Scalar/JumpThreading.cpp

 #define DEBUG_TYPE "jump-threading"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Pass.h"
bool JumpThreading::DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB,
   BB->removePredecessor(PredBB, true);
 
   // Remove the unconditional branch at the end of the PredBB block.
   OldPredBranch->eraseFromParent();
 
   ++NumDupes;
   return true;
 }
-
-

lib/Transforms/Utils/BasicBlockUtils.cpp

 //===-- BasicBlockUtils.cpp - BasicBlock Utilities -------------------------==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This family of functions perform manipulations on basic blocks, and
 // instructions contained within basic blocks.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"

 /// ReplaceInstWithInst - Replace the instruction specified by From with the
 /// instruction specified by To.
 ///
 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
   BasicBlock::iterator BI(From);
   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
 }
 
-/// GetSuccessorNumber - Search for the specified successor of basic block BB
-/// and return its position in the terminator instruction's list of
-/// successors.  It is an error to call this with a block that is not a
-/// successor.
-unsigned llvm::GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ) {
-  TerminatorInst *Term = BB->getTerminator();
-#ifndef NDEBUG
-  unsigned e = Term->getNumSuccessors();
-#endif
-  for (unsigned i = 0; ; ++i) {
-    assert(i != e && "Didn't find edge?");
-    if (Term->getSuccessor(i) == Succ)
-      return i;
-  }
-}
-
 /// SplitEdge -  Split the edge connecting specified block. Pass P must
 /// not be NULL.
 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, Pass *P) {
   unsigned SuccNum = GetSuccessorNumber(BB, Succ);
 
   // If this is a critical edge, let SplitCriticalEdge do it.
   TerminatorInst *LatchTerm = BB->getTerminator();
   if (SplitCriticalEdge(LatchTerm, SuccNum, P))
void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
   } else {
     // There is no second clone. Just replace the landing pad with the first
     // clone.
     LPad->replaceAllUsesWith(Clone1);
     LPad->eraseFromParent();
   }
 }
 
-/// FindFunctionBackedges - Analyze the specified function to find all of the
-/// loop backedges in the function and return them.  This is a relatively cheap
-/// (compared to computing dominators and loop info) analysis.
-///
-/// The output is added to Result, as pairs of <from,to> edge info.
-void llvm::FindFunctionBackedges(const Function &F,
-     SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
-  const BasicBlock *BB = &F.getEntryBlock();
-  if (succ_begin(BB) == succ_end(BB))
-    return;
-
-  SmallPtrSet<const BasicBlock*, 8> Visited;
-  SmallVector<std::pair<const BasicBlock*, succ_const_iterator>, 8> VisitStack;
-  SmallPtrSet<const BasicBlock*, 8> InStack;
-
-  Visited.insert(BB);
-  VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
-  InStack.insert(BB);
-  do {
-    std::pair<const BasicBlock*, succ_const_iterator> &Top = VisitStack.back();
-    const BasicBlock *ParentBB = Top.first;
-    succ_const_iterator &I = Top.second;
-
-    bool FoundNew = false;
-    while (I != succ_end(ParentBB)) {
-      BB = *I++;
-      if (Visited.insert(BB)) {
-        FoundNew = true;
-        break;
-      }
-      // Successor is in VisitStack, it's a back edge.
-      if (InStack.count(BB))
-        Result.push_back(std::make_pair(ParentBB, BB));
-    }
-
-    if (FoundNew) {
-      // Go down one level if there is a unvisited successor.
-      InStack.insert(BB);
-      VisitStack.push_back(std::make_pair(BB, succ_begin(BB)));
-    } else {
-      // Go up one level.
-      InStack.erase(VisitStack.pop_back_val().first);
-    }
-  } while (!VisitStack.empty());
-}
-
 /// FoldReturnIntoUncondBranch - This method duplicates the specified return
 /// instruction into a predecessor which ends in an unconditional branch. If
 /// the return instruction returns a value defined by a PHI, propagate the
 /// right value into the return. It returns the new return instruction in the
 /// predecessor.
 ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
                                              BasicBlock *Pred) {
   Instruction *UncondBranch = Pred->getTerminator();

lib/Transforms/Utils/BreakCriticalEdges.cpp

 // dominator trees.
 //
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "break-crit-edges"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ProfileInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/ErrorHandling.h"
bool BreakCriticalEdges::runOnFunction(Function &F) {
 
   return Changed;
 }
 
 //===----------------------------------------------------------------------===//
 //    Implementation of the external critical edge manipulation functions
 //===----------------------------------------------------------------------===//
 
-// isCriticalEdge - Return true if the specified edge is a critical edge.
-// Critical edges are edges from a block with multiple successors to a block
-// with multiple predecessors.
-//
-bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
-                          bool AllowIdenticalEdges) {
-  assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!");
-  if (TI->getNumSuccessors() == 1) return false;
-
-  const BasicBlock *Dest = TI->getSuccessor(SuccNum);
-  const_pred_iterator I = pred_begin(Dest), E = pred_end(Dest);
-
-  // If there is more than one predecessor, this is a critical edge...
-  assert(I != E && "No preds, but we have an edge to the block?");
-  const BasicBlock *FirstPred = *I;
-  ++I;        // Skip one edge due to the incoming arc from TI.
-  if (!AllowIdenticalEdges)
-    return I != E;
-
-  // If AllowIdenticalEdges is true, then we allow this edge to be considered
-  // non-critical iff all preds come from TI's block.
-  while (I != E) {
-    const BasicBlock *P = *I;
-    if (P != FirstPred)
-      return true;
-    // Note: leave this as is until no one ever compiles with either gcc 4.0.1
-    // or Xcode 2. This seems to work around the pred_iterator assert in PR 2207
-    E = pred_end(P);
-    ++I;
-  }
-  return false;
-}
-
 /// createPHIsForSplitLoopExit - When a loop exit edge is split, LCSSA form
 /// may require new PHIs in the new exit block. This function inserts the
 /// new PHIs, as needed. Preds is a list of preds inside the loop, SplitBB
 /// is the new loop exit block, and DestBB is the old loop exit, now the
 /// successor of SplitBB.
 static void createPHIsForSplitLoopExit(ArrayRef<BasicBlock *> Preds,
                                        BasicBlock *SplitBB,
                                        BasicBlock *DestBB) {

lib/Transforms/Utils/DemoteRegToStack.cpp

 //===- DemoteRegToStack.cpp - Move a virtual register to the stack --------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/Analysis/CFG.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 using namespace llvm;
 
 /// DemoteRegToStack - This function takes a virtual register computed by an
 /// Instruction and replaces it with a slot in the stack frame, allocated via
 /// alloca.  This allows the CFG to be changed around without fear of

unittests/Analysis/CFGTest.cpp

+//===- CFGTest.cpp - CFG tests --------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CFG.h"
+#include "llvm/ADT/OwningPtr.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Assembly/Parser.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/InstIterator.h"
+#include "llvm/Support/SourceMgr.h"
+#include "llvm/Pass.h"
+#include "llvm/PassManager.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+// This fixture assists in running the isPotentiallyReachable utility four ways
+// and ensuring it produces the correct answer each time.
+class IsPotentiallyReachableTest : public testing::Test {
+protected:
+  void ParseAssembly(const char *Assembly) {
+    M.reset(new Module("Module", getGlobalContext()));
+
+    SMDiagnostic Error;
+    bool Parsed = ParseAssemblyString(Assembly, M.get(),
+                                      Error, M->getContext()) == M.get();
+                                      
+    std::string errMsg;
+    raw_string_ostream os(errMsg);
+    Error.print("", os);
+
+    if (!Parsed) {
+      // A failure here means that the test itself is buggy.
+      report_fatal_error(os.str().c_str());
+    }
+
+    Function *F = M->getFunction("test");
+    if (F == NULL)
+      report_fatal_error("Test must have a function named @test");
+
+    A = B = NULL;
+    for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
+      if (I->hasName()) {
+        if (I->getName() == "A")
+          A = &*I;
+        else if (I->getName() == "B")
+          B = &*I;
+      }
+    }
+    if (A == NULL)
+      report_fatal_error("@test must have an instruction %A");
+    if (B == NULL)
+      report_fatal_error("@test must have an instruction %B");
+  }
+
+  void ExpectPath(bool ExpectedResult) {
+    static char ID;
+    class IsPotentiallyReachableTestPass : public FunctionPass {
+     public:
+      IsPotentiallyReachableTestPass(bool ExpectedResult,
+                                     Instruction *A, Instruction *B)
+          : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {}
+
+      void getAnalysisUsage(AnalysisUsage &AU) const {
+        AU.setPreservesAll();
+        AU.addRequired<LoopInfo>();
+        AU.addRequired<DominatorTree>();
+      }
+
+      bool runOnFunction(Function &F) {
+        if (!F.hasName() || F.getName() != "test")
+          return false;
+
+        LoopInfo *LI = &getAnalysis<LoopInfo>();
+        DominatorTree *DT = &getAnalysis<DominatorTree>();
+        EXPECT_EQ(isPotentiallyReachable(A, B, 0, 0), ExpectedResult);
+        EXPECT_EQ(isPotentiallyReachable(A, B, DT, 0), ExpectedResult);
+        EXPECT_EQ(isPotentiallyReachable(A, B, 0, LI), ExpectedResult);
+        EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult);
+        return false;
+      }
+      bool ExpectedResult;
+      Instruction *A, *B;
+    };
+
+    IsPotentiallyReachableTestPass *P =
+        new IsPotentiallyReachableTestPass(ExpectedResult, A, B);
+    PassManager PM;
+    PM.add(P);
+    PM.run(*M);
+  }
+private:
+  OwningPtr<Module> M;
+  Instruction *A, *B;
+};
+
+}
+
+TEST_F(IsPotentiallyReachableTest, SameBlockNoPath) {
+  ParseAssembly(
+      "define void @test() {\n"
+      "entry:\n"
+      "  bitcast i8 undef to i8\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  bitcast i8 undef to i8\n"
+      "  bitcast i8 undef to i8\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  ret void\n"
+      "}\n");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, SameBlockPath) {
+  ParseAssembly(
+      "define void @test() {\n"
+      "entry:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  bitcast i8 undef to i8\n"
+      "  bitcast i8 undef to i8\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  ret void\n"
+      "}\n");
+  ExpectPath(true);
+}
+
+TEST_F(IsPotentiallyReachableTest, StraightNoPath) {
+  ParseAssembly(
+      "define void @test() {\n"
+      "entry:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  br label %exit\n"
+      "exit:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  ret void\n"
+      "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, StraightPath) {
+  ParseAssembly(
+      "define void @test() {\n"
+      "entry:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  br label %exit\n"
+      "exit:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  ret void\n"
+      "}");
+  ExpectPath(true);
+}
+
+TEST_F(IsPotentiallyReachableTest, DestUnreachable) {
+  ParseAssembly(
+      "define void @test() {\n"
+      "entry:\n"
+      "  br label %midblock\n"
+      "midblock:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  ret void\n"
+      "unreachable:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  br label %midblock\n"
+      "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, BranchToReturn) {
+  ParseAssembly(
+      "define void @test(i1 %x) {\n"
+      "entry:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  br i1 %x, label %block1, label %block2\n"
+      "block1:\n"
+      "  ret void\n"
+      "block2:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  ret void\n"
+      "}");
+  ExpectPath(true);
+}
+
+TEST_F(IsPotentiallyReachableTest, SimpleLoop1) {
+  ParseAssembly(
+      "declare i1 @switch()\n"
+      "\n"
+      "define void @test() {\n"
+      "entry:\n"
+      "  br label %loop\n"
+      "loop:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  %x = call i1 @switch()\n"
+      "  br i1 %x, label %loop, label %exit\n"
+      "exit:\n"
+      "  ret void\n"
+      "}");
+  ExpectPath(true);
+}
+
+TEST_F(IsPotentiallyReachableTest, SimpleLoop2) {
+  ParseAssembly(
+      "declare i1 @switch()\n"
+      "\n"
+      "define void @test() {\n"
+      "entry:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  br label %loop\n"
+      "loop:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  %x = call i1 @switch()\n"
+      "  br i1 %x, label %loop, label %exit\n"
+      "exit:\n"
+      "  ret void\n"
+      "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, SimpleLoop3) {
+  ParseAssembly(
+      "declare i1 @switch()\n"
+      "\n"
+      "define void @test() {\n"
+      "entry:\n"
+      "  br label %loop\n"
+      "loop:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  %x = call i1 @switch()\n"
+      "  br i1 %x, label %loop, label %exit\n"
+      "exit:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  ret void\n"
+      "}");
+  ExpectPath(false);
+}
+
+
+TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther1) {
+  ParseAssembly(
+      "declare i1 @switch()\n"
+      "\n"
+      "define void @test() {\n"
+      "entry:\n"
+      "  br label %loop1\n"
+      "loop1:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  %x = call i1 @switch()\n"
+      "  br i1 %x, label %loop1, label %loop1exit\n"
+      "loop1exit:\n"
+      "  br label %loop2\n"
+      "loop2:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  %y = call i1 @switch()\n"
+      "  br i1 %x, label %loop2, label %loop2exit\n"
+      "loop2exit:"
+      "  ret void\n"
+      "}");
+  ExpectPath(true);
+}
+
+TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOther2) {
+  ParseAssembly(
+      "declare i1 @switch()\n"
+      "\n"
+      "define void @test() {\n"
+      "entry:\n"
+      "  br label %loop1\n"
+      "loop1:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  %x = call i1 @switch()\n"
+      "  br i1 %x, label %loop1, label %loop1exit\n"
+      "loop1exit:\n"
+      "  br label %loop2\n"
+      "loop2:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  %y = call i1 @switch()\n"
+      "  br i1 %x, label %loop2, label %loop2exit\n"
+      "loop2exit:"
+      "  ret void\n"
+      "}");
+  ExpectPath(false);
+}
+
+TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) {
+  ParseAssembly(
+      "declare i1 @switch()\n"
+      "\n"
+      "define void @test() {\n"
+      "entry:\n"
+      "  br label %outerloop3\n"
+      "outerloop3:\n"
+      "  br label %innerloop1\n"
+      "innerloop1:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  %x = call i1 @switch()\n"
+      "  br i1 %x, label %innerloop1, label %innerloop1exit\n"
+      "innerloop1exit:\n"
+      "  br label %innerloop2\n"
+      "innerloop2:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  %y = call i1 @switch()\n"
+      "  br i1 %x, label %innerloop2, label %innerloop2exit\n"
+      "innerloop2exit:"
+      "  ;; In outer loop3 now.\n"
+      "  %z = call i1 @switch()\n"
+      "  br i1 %z, label %outerloop3, label %exit\n"
+      "exit:\n"
+      "  ret void\n"
+      "}");
+  ExpectPath(true);
+}
+
+TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) {
+  ParseAssembly(
+      "declare i1 @switch()\n"
+      "\n"
+      "define void @test() {\n"
+      "entry:\n"
+      "  br label %loop\n"
+      "loop:\n"
+      "  %x = call i1 @switch()\n"
+      "  br i1 %x, label %nextloopblock, label %exit\n"
+      "nextloopblock:\n"
+      "  %y = call i1 @switch()\n"
+      "  br i1 %y, label %left, label %right\n"
+      "left:\n"
+      "  %A = bitcast i8 undef to i8\n"
+      "  br label %loop\n"
+      "right:\n"
+      "  %B = bitcast i8 undef to i8\n"
+      "  br label %loop\n"
+      "exit:\n"
+      "  ret void\n"
+      "}");
+  ExpectPath(true);
+}