Index: llvm/trunk/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LoopInfo.h +++ llvm/trunk/include/llvm/Analysis/LoopInfo.h @@ -570,6 +570,23 @@ reverse_iterator rend() const { return TopLevelLoops.rend(); } bool empty() const { return TopLevelLoops.empty(); } + /// Return all of the loops in the function in preorder across the loop + /// nests, with siblings in forward program order. + /// + /// Note that because loops form a forest of trees, preorder is equivalent to + /// reverse postorder. + SmallVector getLoopsInPreorder(); + + /// Return all of the loops in the function in preorder across the loop + /// nests, with siblings in *reverse* program order. + /// + /// Note that because loops form a forest of trees, preorder is equivalent to + /// reverse postorder. + /// + /// Also note that this is *not* a reverse preorder. Only the siblings are in + /// reverse program order. + SmallVector getLoopsInReverseSiblingPreorder(); + /// Return the inner most loop that BB lives in. If a basic block is in no /// loop (for example the entry node), null is returned. LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); } Index: llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h +++ llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h @@ -507,6 +507,55 @@ DFS.traverse(DomRoot->getBlock()); } +template +SmallVector LoopInfoBase::getLoopsInPreorder() { + SmallVector PreOrderLoops, PreOrderWorklist; + // The outer-most loop actually goes into the result in the same relative + // order as we walk it. But LoopInfo stores the top level loops in reverse + // program order so for here we reverse it to get forward program order. + // FIXME: If we change the order of LoopInfo we will want to remove the + // reverse here. + for (LoopT *RootL : reverse(*this)) { + assert(PreOrderWorklist.empty() && + "Must start with an empty preorder walk worklist."); + PreOrderWorklist.push_back(RootL); + do { + LoopT *L = PreOrderWorklist.pop_back_val(); + // Sub-loops are stored in forward program order, but will process the + // worklist backwards so append them in reverse order. + PreOrderWorklist.append(L->rbegin(), L->rend()); + PreOrderLoops.push_back(L); + } while (!PreOrderWorklist.empty()); + } + + return PreOrderLoops; +} + +template +SmallVector +LoopInfoBase::getLoopsInReverseSiblingPreorder() { + SmallVector PreOrderLoops, PreOrderWorklist; + // The outer-most loop actually goes into the result in the same relative + // order as we walk it. LoopInfo stores the top level loops in reverse + // program order so we walk in order here. + // FIXME: If we change the order of LoopInfo we will want to add a reverse + // here. + for (LoopT *RootL : *this) { + assert(PreOrderWorklist.empty() && + "Must start with an empty preorder walk worklist."); + PreOrderWorklist.push_back(RootL); + do { + LoopT *L = PreOrderWorklist.pop_back_val(); + // Sub-loops are stored in forward program order, but will process the + // worklist backwards so we can just append them in order. + PreOrderWorklist.append(L->begin(), L->end()); + PreOrderLoops.push_back(L); + } while (!PreOrderWorklist.empty()); + } + + return PreOrderLoops; +} + // Debugging template void LoopInfoBase::print(raw_ostream &OS) const { Index: llvm/trunk/lib/Analysis/LoopAnalysisManager.cpp =================================================================== --- llvm/trunk/lib/Analysis/LoopAnalysisManager.cpp +++ llvm/trunk/lib/Analysis/LoopAnalysisManager.cpp @@ -31,24 +31,10 @@ FunctionAnalysisManager::Invalidator &Inv) { // First compute the sequence of IR units covered by this proxy. We will want // to visit this in postorder, but because this is a tree structure we can do - // this by building a preorder sequence and walking it in reverse. - SmallVector PreOrderLoops, PreOrderWorklist; - // Note that we want to walk the roots in reverse order because we will end - // up reversing the preorder sequence. However, it happens that the loop nest - // roots are in reverse order within the LoopInfo object. So we just walk - // forward here. - // FIXME: If we change the order of LoopInfo we will want to add a reverse - // here. - for (Loop *RootL : *LI) { - assert(PreOrderWorklist.empty() && - "Must start with an empty preorder walk worklist."); - PreOrderWorklist.push_back(RootL); - do { - Loop *L = PreOrderWorklist.pop_back_val(); - PreOrderWorklist.append(L->begin(), L->end()); - PreOrderLoops.push_back(L); - } while (!PreOrderWorklist.empty()); - } + // this by building a preorder sequence and walking it backwards. We also + // want siblings in forward program order to match the LoopPassManager so we + // get the preorder with siblings reversed. + SmallVector PreOrderLoops = LI->getLoopsInReverseSiblingPreorder(); // If this proxy or the loop info is going to be invalidated, we also need // to clear all the keys coming from that analysis. We also completely blow Index: llvm/trunk/unittests/Analysis/LoopInfoTest.cpp =================================================================== --- llvm/trunk/unittests/Analysis/LoopInfoTest.cpp +++ llvm/trunk/unittests/Analysis/LoopInfoTest.cpp @@ -81,3 +81,78 @@ EXPECT_TRUE(loopIDFoundAndSet); }); } + +TEST(LoopInfoTest, PreorderTraversals) { + const char *ModuleStr = "define void @f() {\n" + "entry:\n" + " br label %loop.0\n" + "loop.0:\n" + " br i1 undef, label %loop.0.0, label %loop.1\n" + "loop.0.0:\n" + " br i1 undef, label %loop.0.0, label %loop.0.1\n" + "loop.0.1:\n" + " br i1 undef, label %loop.0.1, label %loop.0.2\n" + "loop.0.2:\n" + " br i1 undef, label %loop.0.2, label %loop.0\n" + "loop.1:\n" + " br i1 undef, label %loop.1.0, label %end\n" + "loop.1.0:\n" + " br i1 undef, label %loop.1.0, label %loop.1.1\n" + "loop.1.1:\n" + " br i1 undef, label %loop.1.1, label %loop.1.2\n" + "loop.1.2:\n" + " br i1 undef, label %loop.1.2, label %loop.1\n" + "end:\n" + " ret void\n" + "}\n"; + // Parse the module. + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + Function &F = *M->begin(); + + DominatorTree DT(F); + LoopInfo LI; + LI.analyze(DT); + + Function::iterator I = F.begin(); + ASSERT_EQ("entry", I->getName()); + ++I; + Loop &L_0 = *LI.getLoopFor(&*I++); + ASSERT_EQ("loop.0", L_0.getHeader()->getName()); + Loop &L_0_0 = *LI.getLoopFor(&*I++); + ASSERT_EQ("loop.0.0", L_0_0.getHeader()->getName()); + Loop &L_0_1 = *LI.getLoopFor(&*I++); + ASSERT_EQ("loop.0.1", L_0_1.getHeader()->getName()); + Loop &L_0_2 = *LI.getLoopFor(&*I++); + ASSERT_EQ("loop.0.2", L_0_2.getHeader()->getName()); + Loop &L_1 = *LI.getLoopFor(&*I++); + ASSERT_EQ("loop.1", L_1.getHeader()->getName()); + Loop &L_1_0 = *LI.getLoopFor(&*I++); + ASSERT_EQ("loop.1.0", L_1_0.getHeader()->getName()); + Loop &L_1_1 = *LI.getLoopFor(&*I++); + ASSERT_EQ("loop.1.1", L_1_1.getHeader()->getName()); + Loop &L_1_2 = *LI.getLoopFor(&*I++); + ASSERT_EQ("loop.1.2", L_1_2.getHeader()->getName()); + + auto Preorder = LI.getLoopsInPreorder(); + ASSERT_EQ(8u, Preorder.size()); + EXPECT_EQ(&L_0, Preorder[0]); + EXPECT_EQ(&L_0_0, Preorder[1]); + EXPECT_EQ(&L_0_1, Preorder[2]); + EXPECT_EQ(&L_0_2, Preorder[3]); + EXPECT_EQ(&L_1, Preorder[4]); + EXPECT_EQ(&L_1_0, Preorder[5]); + EXPECT_EQ(&L_1_1, Preorder[6]); + EXPECT_EQ(&L_1_2, Preorder[7]); + + auto ReverseSiblingPreorder = LI.getLoopsInReverseSiblingPreorder(); + ASSERT_EQ(8u, ReverseSiblingPreorder.size()); + EXPECT_EQ(&L_1, ReverseSiblingPreorder[0]); + EXPECT_EQ(&L_1_2, ReverseSiblingPreorder[1]); + EXPECT_EQ(&L_1_1, ReverseSiblingPreorder[2]); + EXPECT_EQ(&L_1_0, ReverseSiblingPreorder[3]); + EXPECT_EQ(&L_0, ReverseSiblingPreorder[4]); + EXPECT_EQ(&L_0_2, ReverseSiblingPreorder[5]); + EXPECT_EQ(&L_0_1, ReverseSiblingPreorder[6]); + EXPECT_EQ(&L_0_0, ReverseSiblingPreorder[7]); +}