A new algorithm for computing LoopInfo. Temporarily disabled.

-stable-loops enables a new algorithm for generating the Loop
forest. It differs from the original algorithm in a few respects:

- Not determined by use-list order.
- Initially guarantees RPO order of block and subloops.
- Linear in the number of CFG edges.
- Nonrecursive.

I didn't want to change the LoopInfo API yet, so the block lists are
still inclusive. This seems strange to me, and it means that building
LoopInfo is not strictly linear, but it may not be a problem in
practice. At least the block lists start out in RPO order now. In the
future we may add an attribute or wrapper analysis that allows other
passes to assume RPO order.

The primary motivation of this work was not to optimize LoopInfo, but
to allow reproducing performance issues by decomposing the compilation
stages. I'm often unable to do this with the current LoopInfo, because
the loop tree order determines Loop pass order. Serializing the IR
tends to invert the order, which reverses the optimization order. This
makes it nearly impossible to debug interdependent loop optimizations
such as LSR.

I also believe this will provide more stable performance results across time.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158790 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 8 insertions, 0 deletions

diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 03ca316cfc..329650e81f 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -97,6 +97,9 @@ public:
   BlockT *getHeader() const { return Blocks.front(); }
   LoopT *getParentLoop() const { return ParentLoop; }
 
+  /// setParentLoop is a raw interface for bypassing addChildLoop.
+  void setParentLoop(LoopT *L) { ParentLoop = L; }
+
   /// contains - Return true if the specified loop is contained within in
   /// this loop.
   ///
@@ -122,6 +125,7 @@ public:
   /// iterator/begin/end - Return the loops contained entirely within this loop.
   ///
   const std::vector<LoopT *> &getSubLoops() const { return SubLoops; }
+  std::vector<LoopT *> &getSubLoopsVector() { return SubLoops; }
   typedef typename std::vector<LoopT *>::const_iterator iterator;
   iterator begin() const { return SubLoops.begin(); }
   iterator end() const { return SubLoops.end(); }
@@ -130,6 +134,7 @@ public:
   /// getBlocks - Get a list of the basic blocks which make up this loop.
   ///
   const std::vector<BlockT*> &getBlocks() const { return Blocks; }
+  std::vector<BlockT*> &getBlocksVector() { return Blocks; }
   typedef typename std::vector<BlockT*>::const_iterator block_iterator;
   block_iterator block_begin() const { return Blocks.begin(); }
   block_iterator block_end() const { return Blocks.end(); }
@@ -528,6 +533,9 @@ public:
   /// inserted into L instead.
   void InsertLoopInto(LoopT *L, LoopT *Parent);
 
+  /// Create the loop forest using a stable algorithm.
+  void Analyze(DominatorTreeBase<BlockT> &DomTree);
+
   // Debugging
 
   void print(raw_ostream &OS) const;