aboutsummaryrefslogtreecommitdiffstats
path: root/include
diff options
context:
space:
mode:
authorDan Gohman <gohman@apple.com>2009-09-03 16:31:42 +0000
committerDan Gohman <gohman@apple.com>2009-09-03 16:31:42 +0000
commit8fc5ad33691b2a0672a7487da1f56b6f7f675a1b (patch)
tree61eab90d9619850507fb5d69501817b1629d3201 /include
parentc8b26880fd667238d56c64c3c73ea3fc4ed35111 (diff)
downloadexternal_llvm-8fc5ad33691b2a0672a7487da1f56b6f7f675a1b.zip
external_llvm-8fc5ad33691b2a0672a7487da1f56b6f7f675a1b.tar.gz
external_llvm-8fc5ad33691b2a0672a7487da1f56b6f7f675a1b.tar.bz2
Add a verifyAnalysis to LoopInfo, LoopSimplify, and LCSSA form that verify
that these passes are properly preserved. Fix several transformation passes that claimed to preserve LoopSimplify form but weren't. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@80926 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include')
-rw-r--r--include/llvm/Analysis/LoopInfo.h72
-rw-r--r--include/llvm/Transforms/Utils/BasicBlockUtils.h21
2 files changed, 81 insertions, 12 deletions
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index b803176..1892bc7 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -376,11 +376,73 @@ public:
/// verifyLoop - Verify loop structure
void verifyLoop() const {
#ifndef NDEBUG
- assert (getHeader() && "Loop header is missing");
- assert (getLoopPreheader() && "Loop preheader is missing");
- assert (getLoopLatch() && "Loop latch is missing");
- for (iterator I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I)
+ assert(!Blocks.empty() && "Loop header is missing");
+ assert(getHeader() && "Loop header is missing");
+
+ // Verify the individual blocks.
+ for (block_iterator I = block_begin(), E = block_end(); I != E; ++I) {
+ BlockT *BB = *I;
+ bool HasInsideLoopSuccs = false;
+ bool HasInsideLoopPreds = false;
+ SmallVector<BlockT *, 2> OutsideLoopPreds;
+
+ typedef GraphTraits<BlockT*> BlockTraits;
+ for (typename BlockTraits::ChildIteratorType SI =
+ BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
+ SI != SE; ++SI)
+ if (contains(*SI))
+ HasInsideLoopSuccs = true;
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ for (typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
+ PI != PE; ++PI) {
+ if (contains(*PI))
+ HasInsideLoopPreds = true;
+ else
+ OutsideLoopPreds.push_back(*PI);
+ }
+
+ if (BB == getHeader()) {
+ assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
+ } else if (!OutsideLoopPreds.empty()) {
+ // A non-header loop shouldn't be reachable from outside the loop,
+ // though it is permitted if the predecessor is not itself actually
+ // reachable.
+ BlockT *EntryBB = BB->getParent()->begin();
+ for (df_iterator<BlockT *> NI = df_begin(EntryBB),
+ NE = df_end(EntryBB); NI != NE; ++NI)
+ for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
+ assert(*NI != OutsideLoopPreds[i] &&
+ "Loop has multiple entry points!");
+ }
+ assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!");
+ assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");
+ assert(BB != getHeader()->getParent()->begin() &&
+ "Loop contains function entry block!");
+ }
+
+ // Verify the subloops.
+ for (iterator I = begin(), E = end(); I != E; ++I) {
+ // Each block in each subloop should be contained within this loop.
+ for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
+ BI != BE; ++BI) {
+ assert(contains(*BI) &&
+ "Loop does not contain all the blocks of a subloop!");
+ }
+ // Recursively check the subloop.
(*I)->verifyLoop();
+ }
+
+ // Verify the parent loop.
+ if (ParentLoop) {
+ bool FoundSelf = false;
+ for (iterator I = ParentLoop->begin(), E = ParentLoop->end(); I != E; ++I)
+ if (*I == this) {
+ FoundSelf = true;
+ break;
+ }
+ assert(FoundSelf && "Loop is not a subloop of its parent!");
+ }
#endif
}
@@ -873,6 +935,8 @@ public:
///
virtual bool runOnFunction(Function &F);
+ virtual void verifyAnalysis() const;
+
virtual void releaseMemory() { LI.releaseMemory(); }
virtual void print(raw_ostream &O, const Module* M = 0) const;
diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
index 95ffa46..e766d72 100644
--- a/include/llvm/Transforms/Utils/BasicBlockUtils.h
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -126,10 +126,10 @@ bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
/// dest go to one block instead of each going to a different block, but isn't
/// the standard definition of a "critical edge".
///
-bool SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P = 0,
- bool MergeIdenticalEdges = false);
+BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
+ Pass *P = 0, bool MergeIdenticalEdges = false);
-inline bool SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) {
+inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) {
return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P);
}
@@ -143,7 +143,7 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) {
TerminatorInst *TI = (*PI)->getTerminator();
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
if (TI->getSuccessor(i) == Succ)
- MadeChange |= SplitCriticalEdge(TI, i, P);
+ MadeChange |= !!SplitCriticalEdge(TI, i, P);
return MadeChange;
}
@@ -151,8 +151,9 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) {
/// and return true, otherwise return false. This method requires that there be
/// an edge between the two blocks. If P is specified, it updates the analyses
/// described above.
-inline bool SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, Pass *P = 0,
- bool MergeIdenticalEdges = false) {
+inline BasicBlock *SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst,
+ Pass *P = 0,
+ bool MergeIdenticalEdges = false) {
TerminatorInst *TI = Src->getTerminator();
unsigned i = 0;
while (1) {
@@ -180,8 +181,12 @@ BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P);
/// Preds array, which has NumPreds elements in it. The new block is given a
/// suffix of 'Suffix'. This function returns the new block.
///
-/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and
-/// DominanceFrontier, but no other analyses.
+/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
+/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses.
+/// In particular, it does not preserve LoopSimplify (because it's
+/// complicated to handle the case where one of the edges being split
+/// is an exit of a loop with other exits).
+///
BasicBlock *SplitBlockPredecessors(BasicBlock *BB, BasicBlock *const *Preds,
unsigned NumPreds, const char *Suffix,
Pass *P = 0);