Index: llvm/trunk/include/llvm/Transforms/Utils/LoopSimplify.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/LoopSimplify.h +++ llvm/trunk/include/llvm/Transforms/Utils/LoopSimplify.h @@ -0,0 +1,65 @@ +//===- LoopSimplify.h - Loop Canonicalization Pass --------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs several transformations to transform natural loops into a +// simpler form, which makes subsequent analyses and transformations simpler and +// more effective. +// +// Loop pre-header insertion guarantees that there is a single, non-critical +// entry edge from outside of the loop to the loop header. This simplifies a +// number of analyses and transformations, such as LICM. +// +// Loop exit-block insertion guarantees that all exit blocks from the loop +// (blocks which are outside of the loop that have predecessors inside of the +// loop) only have predecessors from inside of the loop (and are thus dominated +// by the loop header). This simplifies transformations such as store-sinking +// that are built into LICM. +// +// This pass also guarantees that loops will have exactly one backedge. +// +// Indirectbr instructions introduce several complications. If the loop +// contains or is entered by an indirectbr instruction, it may not be possible +// to transform the loop and make these guarantees. Client code should check +// that these conditions are true before relying on them. +// +// Note that the simplifycfg pass will clean up blocks which are split out but +// end up being unnecessary, so usage of this pass should not pessimize +// generated code. +// +// This pass obviously modifies the CFG, but updates loop information and +// dominator information. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H +#define LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H + +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// This pass is responsible for loop canonicalization. +class LoopSimplifyPass : public PassInfoMixin { +public: + PreservedAnalyses run(Function &F, AnalysisManager &AM); +}; + +/// \brief Simplify each loop in a loop nest recursively. +/// +/// This takes a potentially un-simplified loop L (and its children) and turns +/// it into a simplified loop nest with preheaders and single backedges. It will +/// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null. +bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, + AssumptionCache *AC, bool PreserveLCSSA); + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H Index: llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h +++ llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h @@ -323,14 +323,6 @@ BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA); -/// \brief Simplify each loop in a loop nest recursively. -/// -/// This takes a potentially un-simplified loop L (and its children) and turns -/// it into a simplified loop nest with preheaders and single backedges. It will -/// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null. -bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, - AssumptionCache *AC, bool PreserveLCSSA); - /// \brief Put loop into LCSSA form. /// /// Looks at all instructions in the loop which have uses outside of the Index: llvm/trunk/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/trunk/lib/Passes/PassBuilder.cpp +++ llvm/trunk/lib/Passes/PassBuilder.cpp @@ -102,6 +102,7 @@ #include "llvm/Transforms/Scalar/TailRecursionElimination.h" #include "llvm/Transforms/Utils/AddDiscriminators.h" #include "llvm/Transforms/Utils/LCSSA.h" +#include "llvm/Transforms/Utils/LoopSimplify.h" #include "llvm/Transforms/Utils/Mem2Reg.h" #include "llvm/Transforms/Utils/MemorySSA.h" #include "llvm/Transforms/Utils/SimplifyInstructions.h" Index: llvm/trunk/lib/Passes/PassRegistry.def =================================================================== --- llvm/trunk/lib/Passes/PassRegistry.def +++ llvm/trunk/lib/Passes/PassRegistry.def @@ -140,6 +140,7 @@ FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass()) FUNCTION_PASS("guard-widening", GuardWideningPass()) FUNCTION_PASS("gvn", GVN()) +FUNCTION_PASS("loop-simplify", LoopSimplifyPass()) FUNCTION_PASS("mem2reg", PromotePass()) FUNCTION_PASS("memcpyopt", MemCpyOptPass()) FUNCTION_PASS("mldst-motion", MergedLoadStoreMotionPass()) Index: llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp +++ llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp @@ -37,6 +37,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/Transforms/Utils/LoopSimplify.h" #include "llvm/Transforms/Scalar.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SetOperations.h" @@ -802,6 +803,36 @@ return Changed; } +PreservedAnalyses LoopSimplifyPass::run(Function &F, + AnalysisManager &AM) { + bool Changed = false; + LoopInfo *LI = &AM.getResult(F); + DominatorTree *DT = &AM.getResult(F); + ScalarEvolution *SE = AM.getCachedResult(F); + AssumptionCache *AC = &AM.getResult(F); + + // FIXME: This pass should verify that the loops on which it's operating + // are in canonical SSA form, and that the pass itself preserves this form. + for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) + Changed |= simplifyLoop(*I, DT, LI, SE, AC, true /* PreserveLCSSA */); + + if (!Changed) + return PreservedAnalyses::all(); + PreservedAnalyses PA; + + // The old PM also preserved LCSSAID and BreakCriticalEdgesID. + // This makes no sense in the new PM so we omit those from the set + // of preserved passes. + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; +} + // FIXME: Restore this code when we re-enable verification in verifyAnalysis // below. #if 0 Index: llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp +++ llvm/trunk/lib/Transforms/Utils/LoopUnroll.cpp @@ -34,6 +34,7 @@ #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/LoopSimplify.h" #include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/Transforms/Utils/SimplifyIndVar.h" using namespace llvm; Index: llvm/trunk/test/Transforms/LoopSimplify/basictest.ll =================================================================== --- llvm/trunk/test/Transforms/LoopSimplify/basictest.ll +++ llvm/trunk/test/Transforms/LoopSimplify/basictest.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -loop-simplify +; RUN: opt < %s -passes=loop-simplify ; This function should get a preheader inserted before BB3, that is jumped ; to by BB1 & BB2