Reapplying r136844.
authorAndrew Trick <atrick@apple.com>
Wed, 10 Aug 2011 23:22:57 +0000 (23:22 +0000)
committerAndrew Trick <atrick@apple.com>
Wed, 10 Aug 2011 23:22:57 +0000 (23:22 +0000)
commitfb62b8deb3c837bc5f4cf98543b89d08e7db9f84
tree69e9c74b38f5079c81e5bd50ce3e902ecb85fb93
parent64104f48f23ff46538e46f01c076fef2ff55d97f
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
include/llvm/Analysis/LoopInfo.h
lib/Analysis/LoopInfo.cpp
lib/Analysis/LoopPass.cpp