A new algorithm for computing LoopInfo. Temporarily disabled.
authorAndrew Trick <atrick@apple.com>
Wed, 20 Jun 2012 05:23:33 +0000 (05:23 +0000)
committerAndrew Trick <atrick@apple.com>
Wed, 20 Jun 2012 05:23:33 +0000 (05:23 +0000)
commit37aa33bc11c01a7142bfa2428a5a4d219b07b6c3
tree2f976a6c7e2893caac5cec7813fa9dffdbc853a2
parent9059390cf0a6d57add00169c28805bb9a59308b6
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
include/llvm/Analysis/LoopInfo.h
include/llvm/Analysis/LoopInfoImpl.h
lib/Analysis/LoopInfo.cpp
lib/CodeGen/MachineLoopInfo.cpp