From 37aa33bc11c01a7142bfa2428a5a4d219b07b6c3 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Wed, 20 Jun 2012 05:23:33 +0000 Subject: 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 --- lib/Analysis/LoopInfo.cpp | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) (limited to 'lib/Analysis/LoopInfo.cpp') diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp index e46be981fc..5d5f5066b3 100644 --- a/lib/Analysis/LoopInfo.cpp +++ b/lib/Analysis/LoopInfo.cpp @@ -44,6 +44,10 @@ static cl::opt VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo), cl::desc("Verify loop info (time consuming)")); +static cl::opt +StableLoopInfo("stable-loops", cl::Hidden, cl::init(false), + cl::desc("Compute a stable loop tree.")); + char LoopInfo::ID = 0; INITIALIZE_PASS_BEGIN(LoopInfo, "loops", "Natural Loop Information", true, true) INITIALIZE_PASS_DEPENDENCY(DominatorTree) @@ -512,7 +516,10 @@ Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) { // bool LoopInfo::runOnFunction(Function &) { releaseMemory(); - LI.Calculate(getAnalysis().getBase()); // Update + if (StableLoopInfo) + LI.Analyze(getAnalysis().getBase()); + else + LI.Calculate(getAnalysis().getBase()); // Update return false; } -- cgit v1.2.3-18-g5258