diff options
author | Andrew Trick <atrick@apple.com> | 2011-08-10 23:22:57 +0000 |
---|---|---|
committer | Andrew Trick <atrick@apple.com> | 2011-08-10 23:22:57 +0000 |
commit | fb62b8deb3c837bc5f4cf98543b89d08e7db9f84 (patch) | |
tree | 69e9c74b38f5079c81e5bd50ce3e902ecb85fb93 /include/llvm/Analysis/LoopInfo.h | |
parent | 64104f48f23ff46538e46f01c076fef2ff55d97f (diff) | |
download | llvm-fb62b8deb3c837bc5f4cf98543b89d08e7db9f84.tar.gz llvm-fb62b8deb3c837bc5f4cf98543b89d08e7db9f84.tar.bz2 llvm-fb62b8deb3c837bc5f4cf98543b89d08e7db9f84.tar.xz |
Reapplying r136844.
An algorithm for incrementally updating LoopInfo within a
LoopPassManager. The incremental update should be extremely cheap in
most cases and can be used in places where it's not feasible to
regenerate the entire loop forest.
- "Unloop" is a node in the loop tree whose last backedge has been removed.
- Perform reverse dataflow on the block inside Unloop to propagate the
nearest loop from the block's successors.
- For reducible CFG, each block in unloop is visited exactly
once. This is because unloop no longer has a backedge and blocks
within subloops don't change parents.
- Immediate subloops are summarized by the nearest loop reachable from
their exits or exits within nested subloops.
- At completion the unloop blocks each have a new parent loop, and
each immediate subloop has a new parent.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137276 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm/Analysis/LoopInfo.h')
-rw-r--r-- | include/llvm/Analysis/LoopInfo.h | 16 |
1 files changed, 13 insertions, 3 deletions
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 7ebcd6b849..7c89744123 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -708,9 +708,13 @@ public: /// specified loop. This should be used by transformations that restructure /// the loop hierarchy tree. void changeLoopFor(BlockT *BB, LoopT *L) { - LoopT *&OldLoop = BBMap[BB]; - assert(OldLoop && "Block not in a loop yet!"); - OldLoop = L; + if (!L) { + typename DenseMap<BlockT *, LoopT *>::iterator I = BBMap.find(BB); + if (I != BBMap.end()) + BBMap.erase(I); + return; + } + BBMap[BB] = L; } /// changeTopLevelLoop - Replace the specified loop in the top-level loops @@ -1029,6 +1033,12 @@ public: LI.removeBlock(BB); } + /// updateUnloop - Update LoopInfo after removing the last backedge from a + /// loop--now the "unloop". This updates the loop forest and parent loops for + /// each block so that Unloop is no longer referenced, but the caller must + /// actually delete the Unloop object. + void updateUnloop(Loop *Unloop); + /// replacementPreservesLCSSAForm - Returns true if replacing From with To /// everywhere is guaranteed to preserve LCSSA form. bool replacementPreservesLCSSAForm(Instruction *From, Value *To) { |