Reimplement isPotentiallyReachable to make nocapture deduction much stronger.
Adds unit tests for it too.
Split BasicBlockUtils into an analysis-half and a transforms-half, and put the
analysis bits into a new Analysis/CFG.{h,cpp}. Promote isPotentiallyReachable
into llvm::isPotentiallyReachable and move it into Analysis/CFG.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187283 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index dad3147..bc418af 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -23,6 +23,7 @@
#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"
diff --git a/lib/Transforms/Scalar/JumpThreading.cpp b/lib/Transforms/Scalar/JumpThreading.cpp
index b61c5ba..2d961ee 100644
--- a/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/lib/Transforms/Scalar/JumpThreading.cpp
@@ -19,6 +19,7 @@
#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"
@@ -1614,5 +1615,3 @@
++NumDupes;
return true;
}
-
-
diff --git a/lib/Transforms/Utils/BasicBlockUtils.cpp b/lib/Transforms/Utils/BasicBlockUtils.cpp
index 9167795..28c08d5 100644
--- a/lib/Transforms/Utils/BasicBlockUtils.cpp
+++ b/lib/Transforms/Utils/BasicBlockUtils.cpp
@@ -14,6 +14,7 @@
#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"
@@ -235,22 +236,6 @@
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) {
@@ -598,52 +583,6 @@
}
}
-/// 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
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index 8513772..8f3ff96 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -19,6 +19,7 @@
#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"
@@ -84,39 +85,6 @@
// 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
diff --git a/lib/Transforms/Utils/DemoteRegToStack.cpp b/lib/Transforms/Utils/DemoteRegToStack.cpp
index db525cd..0723b35 100644
--- a/lib/Transforms/Utils/DemoteRegToStack.cpp
+++ b/lib/Transforms/Utils/DemoteRegToStack.cpp
@@ -10,6 +10,7 @@
#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"