diff --git a/llvm/include/llvm/Analysis/LoopNestAnalysis.h b/llvm/include/llvm/Analysis/LoopNestAnalysis.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/LoopNestAnalysis.h @@ -0,0 +1,156 @@ +//===- llvm/Analysis/LoopNestAnalysis.h -------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file defines the interface for the loop nest analysis. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LOOPNESTANALYSIS_H +#define LLVM_ANALYSIS_LOOPNESTANALYSIS_H + +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +using LoopVectorTy = SmallVector; + +/// This class represents a loop nest and can be used to query its properties. +class LoopNest { +public: + /// Construct a loop nest rooted by loop \p Root. + LoopNest(Loop &Root, ScalarEvolution &SE); + + LoopNest() = delete; + LoopNest &operator=(const LoopNest &) = delete; + + /// Construct a LoopNest object. + static std::unique_ptr getLoopNest(Loop &Root, ScalarEvolution &SE); + + /// Return true if the given loops \p OuterLoop and \p InnerLoop are + /// perfectly nested with respect to each other, and false otherwise. + /// Example: + /// \code + /// for(i) + /// for(j) + /// \endcode + /// arePerfectlyNested(loop_i, loop_j, SE) would return true. + static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, + ScalarEvolution &SE); + + /// Return the maximum nesting depth of the loop nest rooted by loop \p Root. + /// For example given the loop nest: + /// \code + /// for(i) // loop at level 1 and Root of the nest + /// for(j) // loop at level 2 + /// + /// for(k) // loop at level 3 + /// \endcode + /// getMaxPerfectDepth(Loop_i) would return 2. + static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE); + + /// Return the outermost loop in the loop nest. + Loop &getOutermostLoop() const { return *Loops.front(); } + + /// Return the innermost loop in the loop nest if the nest has only one + /// innermost loop, and a nullptr otherwise. + /// Note: the innermost loop returned is not necessarily perfectly nested. + Loop *getInnermostLoop() const { + if (Loops.size() == 1) + return Loops.back(); + + // The loops in the 'Loops' vector have been collected in breadth first + // order, therefore if the last 2 loops in it have the same nesting depth + // there isn't a unique innermost loop in the nest. + const Loop *LastLoop = Loops.back(); + auto SecondLastLoopIter = ++Loops.rbegin(); + return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth()) + ? nullptr + : LastLoop; + } + + /// Return the loop at the given \p Index. + Loop *getLoop(unsigned Index) const { + assert(Index < Loops.size() && "Index is out of bounds"); + return Loops[Index]; + } + + /// Return the number of loops in the nest. + unsigned getNumLoops() const { return Loops.size(); } + + /// Get the loops in the nest. + ArrayRef getLoops() const { return Loops; } + + /// Retrieve a vector of perfect loop nests contained in the current loop + /// nest. For example, given the following nest containing 4 loops, this + /// member function would return {{L1,L2},{L3,L4}}. + /// \code + /// for(i) // L1 + /// for(j) // L2 + /// + /// for(k) // L3 + /// for(l) // L4 + /// \endcode + SmallVector getPerfectLoops(ScalarEvolution &SE) const; + + /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop) + /// For example given the loop nest: + /// \code + /// for(i) // loop at level 1 and Root of the nest + /// for(j1) // loop at level 2 + /// for(k) // loop at level 3 + /// for(j2) // loop at level 2 + /// \endcode + /// getNestDepth() would return 3. + unsigned getNestDepth() const { + return (Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1); + } + + /// Return the maximum perfect nesting depth. + unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; } + + /// Return true if all loops in the loop nest are in simplify form. + bool areAllLoopsSimplifyForm() const { + return llvm::all_of(Loops, + [](const Loop *L) { return L->isLoopSimplifyForm(); }); + } + +protected: + const unsigned MaxPerfectDepth; // maximum perfect nesting depth level. + LoopVectorTy Loops; // the loops in the nest (in breadth first order). +}; + +raw_ostream &operator<<(raw_ostream &, const LoopNest &); + +/// This analysis provides information for a loop nest. The analysis runs on +/// demand and can be initiated via AM.getResult. +class LoopNestAnalysis : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + static AnalysisKey Key; + +public: + using Result = LoopNest; + Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR); +}; + +/// Printer pass for the \c LoopNest results. +class LoopNestPrinterPass : public PassInfoMixin { + raw_ostream &OS; + +public: + explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {} + + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +} // namespace llvm + +#endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -53,6 +53,7 @@ LoopAccessAnalysis.cpp LoopAnalysisManager.cpp LoopCacheAnalysis.cpp + LoopNestAnalysis.cpp LoopUnrollAnalyzer.cpp LoopInfo.cpp LoopPass.cpp diff --git a/llvm/lib/Analysis/LoopNestAnalysis.cpp b/llvm/lib/Analysis/LoopNestAnalysis.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/LoopNestAnalysis.cpp @@ -0,0 +1,296 @@ +//===- LoopNestAnalysis.cpp - Loop Nest Analysis --------------------------==// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// The implementation for the loop nest analysis. +/// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LoopNestAnalysis.h" +#include "llvm/ADT/BreadthFirstIterator.h" +#include "llvm/ADT/BreadthFirstIterator.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/PostDominators.h" +#include "llvm/Analysis/ValueTracking.h" + +using namespace llvm; + +#define DEBUG_TYPE "loopnest" +static const char *VerboseDebug = DEBUG_TYPE "-verbose"; + +/// Determine whether the loops structure violates basic requirements for +/// perfect nesting: +/// - the inner loop should be the outer loop's only child +/// - the outer loop header should 'flow' into the inner loop preheader +/// or jump around the inner loop to the outer loop latch +/// - if the inner loop latch exits the inner loop, it should 'flow' into +/// the outer loop latch. +/// Returns true if the loop structure satisfies the basic requirements and +/// false otherwise. +static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, + ScalarEvolution &SE); + +//===----------------------------------------------------------------------===// +// LoopNest implementation +// + +LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE) + : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) { + for (Loop *L : breadth_first(&Root)) + Loops.push_back(L); +} + +std::unique_ptr LoopNest::getLoopNest(Loop &Root, + ScalarEvolution &SE) { + return std::make_unique(Root, SE); +} + +bool LoopNest::arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop, + ScalarEvolution &SE) { + assert(!OuterLoop.getSubLoops().empty() && "Outer loop should have subloops"); + assert(InnerLoop.getParentLoop() && "Inner loop should have a parent"); + LLVM_DEBUG(dbgs() << "Checking whether loop '" << OuterLoop.getName() + << "' and '" << InnerLoop.getName() + << "' are perfectly nested.\n"); + + // Determine whether the loops structure satisfies the following requirements: + // - the inner loop should be the outer loop's only child + // - the outer loop header should 'flow' into the inner loop preheader + // or jump around the inner loop to the outer loop latch + // - if the inner loop latch exits the inner loop, it should 'flow' into + // the outer loop latch. + if (!checkLoopsStructure(OuterLoop, InnerLoop, SE)) { + LLVM_DEBUG(dbgs() << "Not perfectly nested: invalid loop structure.\n"); + return false; + } + + // Bail out if we cannot retrieve the outer loop bounds. + auto OuterLoopLB = OuterLoop.getBounds(SE); + if (OuterLoopLB == None) { + LLVM_DEBUG(dbgs() << "Cannot compute loop bounds of OuterLoop: " + << OuterLoop << "\n";); + return false; + } + + // Identify the outer loop latch comparison instruction. + const BasicBlock *Latch = OuterLoop.getLoopLatch(); + assert(Latch && "Expecting a valid loop latch"); + const BranchInst *BI = dyn_cast(Latch->getTerminator()); + assert(BI && BI->isConditional() && + "Expecting loop latch terminator to be a branch instruction"); + + const CmpInst *OuterLoopLatchCmp = dyn_cast(BI->getCondition()); + DEBUG_WITH_TYPE(VerboseDebug, if (OuterLoopLatchCmp) { + dbgs() << "Outer loop latch compare instruction: " << *OuterLoopLatchCmp + << "\n"; + }); + + // Identify the inner loop guard instruction. + BranchInst *InnerGuard = InnerLoop.getLoopGuardBranch(); + const CmpInst *InnerLoopGuardCmp = + (InnerGuard) ? dyn_cast(InnerGuard->getCondition()) : nullptr; + + DEBUG_WITH_TYPE(VerboseDebug, if (InnerLoopGuardCmp) { + dbgs() << "Inner loop guard compare instruction: " << *InnerLoopGuardCmp + << "\n"; + }); + + // Determine whether instructions in a basic block are one of: + // - the inner loop guard comparison + // - the outer loop latch comparison + // - the outer loop induction variable increment + // - a phi node, a cast or a branch + auto containsOnlySafeInstructions = [&](const BasicBlock &BB) { + return llvm::all_of(BB, [&](const Instruction &I) { + bool isAllowed = isSafeToSpeculativelyExecute(&I) || isa(I) || + isa(I); + if (!isAllowed) { + DEBUG_WITH_TYPE(VerboseDebug, { + dbgs() << "Instruction: " << I << "\nin basic block: " << BB + << " is considered unsafe.\n"; + }); + return false; + } + + // The only binary instruction allowed is the outer loop step instruction, + // the only comparison instructions allowed are the inner loop guard + // compare instruction and the outer loop latch compare instruction. + if ((isa(I) && &I != &OuterLoopLB->getStepInst()) || + (isa(I) && &I != OuterLoopLatchCmp && + &I != InnerLoopGuardCmp)) { + DEBUG_WITH_TYPE(VerboseDebug, { + dbgs() << "Instruction: " << I << "\nin basic block:" << BB + << "is unsafe.\n"; + }); + return false; + } + return true; + }); + }; + + // Check the code surrounding the inner loop for instructions that are deemed + // unsafe. + const BasicBlock *OuterLoopHeader = OuterLoop.getHeader(); + const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch(); + const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader(); + + if (!containsOnlySafeInstructions(*OuterLoopHeader) || + !containsOnlySafeInstructions(*OuterLoopLatch) || + (InnerLoopPreHeader != OuterLoopHeader && + !containsOnlySafeInstructions(*InnerLoopPreHeader)) || + !containsOnlySafeInstructions(*InnerLoop.getExitBlock())) { + LLVM_DEBUG(dbgs() << "Not perfectly nested: code surrounding inner loop is " + "unsafe\n";); + return false; + } + + LLVM_DEBUG(dbgs() << "Loop '" << OuterLoop.getName() << "' and '" + << InnerLoop.getName() << "' are perfectly nested.\n"); + + return true; +} + +SmallVector +LoopNest::getPerfectLoops(ScalarEvolution &SE) const { + SmallVector LV; + LoopVectorTy PerfectNest; + + for (Loop *L : depth_first(const_cast(Loops.front()))) { + if (PerfectNest.empty()) + PerfectNest.push_back(L); + + auto &SubLoops = L->getSubLoops(); + if (SubLoops.size() == 1 && + arePerfectlyNested(*L, *SubLoops.front(), SE)) { + PerfectNest.push_back(SubLoops.front()); + } + else { + LV.push_back(PerfectNest); + PerfectNest.clear(); + } + } + + return LV; +} + +unsigned LoopNest::getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE) { + LLVM_DEBUG(dbgs() << "Get maximum perfect depth of loop nest rooted by loop '" + << Root.getName() << "'\n"); + + const Loop *CurrentLoop = &Root; + const auto *SubLoops = &CurrentLoop->getSubLoops(); + unsigned CurrentDepth = 1; + + while (SubLoops->size() == 1) { + const Loop *InnerLoop = SubLoops->front(); + if (!arePerfectlyNested(*CurrentLoop, *InnerLoop, SE)) { + LLVM_DEBUG({ + dbgs() << "Not a perfect nest: loop '" << CurrentLoop->getName() + << "' is not perfectly nested with loop '" + << InnerLoop->getName() << "'\n"; + }); + break; + } + + CurrentLoop = InnerLoop; + SubLoops = &CurrentLoop->getSubLoops(); + ++CurrentDepth; + } + + return CurrentDepth; +} + +static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, + ScalarEvolution &SE) { + // The inner loop must be the only outer loop's child. + if ((OuterLoop.getSubLoops().size() != 1) || + (InnerLoop.getParentLoop() != &OuterLoop)) + return false; + + // We expect loops in normal form which have a preheader, header, latch... + if (!OuterLoop.isLoopSimplifyForm() || !InnerLoop.isLoopSimplifyForm()) + return false; + + const BasicBlock *OuterLoopHeader = OuterLoop.getHeader(); + const BasicBlock *OuterLoopLatch = OuterLoop.getLoopLatch(); + const BasicBlock *InnerLoopPreHeader = InnerLoop.getLoopPreheader(); + const BasicBlock *InnerLoopLatch = InnerLoop.getLoopLatch(); + const BasicBlock *InnerLoopExit = InnerLoop.getExitBlock(); + + // We expect rotated loops. The inner loop should have a single exit block. + if (OuterLoop.getExitingBlock() != OuterLoopLatch || + InnerLoop.getExitingBlock() != InnerLoopLatch || + !InnerLoopExit) + return false; + + // Ensure the only branch that may exist between the loops is the inner loop + // guard. + if (OuterLoopHeader != InnerLoopPreHeader) { + const BranchInst *BI = + dyn_cast(OuterLoopHeader->getTerminator()); + + if (!BI || BI != InnerLoop.getLoopGuardBranch()) + return false; + + // The successors of the inner loop guard should be the inner loop + // preheader and the outer loop latch. + for (const BasicBlock *Succ : BI->successors()) { + if (Succ == InnerLoopPreHeader) + continue; + if (Succ == OuterLoopLatch) + continue; + + DEBUG_WITH_TYPE(VerboseDebug, { + dbgs() << "Inner loop guard successor " << Succ->getName() + << " doesn't lead to inner loop preheader or " + "outer loop latch.\n"; + }); + return false; + } + } + + // Ensure the inner loop exit block leads to the outer loop latch. + if (InnerLoopExit->getSingleSuccessor() != OuterLoopLatch) { + DEBUG_WITH_TYPE( + VerboseDebug, + dbgs() << "Inner loop exit block " << *InnerLoopExit + << " does not directly lead to the outer loop latch.\n";); + return false; + } + + return true; +} + +raw_ostream &llvm::operator<<(raw_ostream &OS, const LoopNest &LN) { + OS << "IsPerfect="; + if (LN.getMaxPerfectDepth() == LN.getNestDepth()) + OS << "true"; + else + OS << "false"; + OS << ", Depth=" << LN.getNestDepth(); + OS << ", OutermostLoop: " << LN.getOutermostLoop().getName(); + OS << ", Loops: ( "; + for (const Loop *L : LN.getLoops()) + OS << L->getName() << " "; + OS << ")"; + + return OS; +} + +//===----------------------------------------------------------------------===// +// LoopNestPrinterPass implementation +// + +PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LPMUpdater &U) { + if (auto LN = LoopNest::getLoopNest(L, AR.SE)) + OS << *LN << "\n"; + + return PreservedAnalyses::all(); +} diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -38,6 +38,7 @@ #include "llvm/Analysis/LoopAccessAnalysis.h" #include "llvm/Analysis/LoopCacheAnalysis.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopNestAnalysis.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/ModuleSummaryAnalysis.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -306,6 +306,7 @@ LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs())) LOOP_PASS("print", DDGAnalysisPrinterPass(dbgs())) LOOP_PASS("print", IVUsersPrinterPass(dbgs())) +LOOP_PASS("print", LoopNestPrinterPass(dbgs())) LOOP_PASS("print", LoopCachePrinterPass(dbgs())) LOOP_PASS("loop-predication", LoopPredicationPass()) LOOP_PASS("guard-widening", GuardWideningPass()) diff --git a/llvm/test/Analysis/LoopNestAnalysis/imperfectnest.ll b/llvm/test/Analysis/LoopNestAnalysis/imperfectnest.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/LoopNestAnalysis/imperfectnest.ll @@ -0,0 +1,493 @@ +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +; Test an imperfect 2-dim loop nest of the form: +; for (int i = 0; i < nx; ++i) { +; x[i] = i; +; for (int j = 0; j < ny; ++j) +; y[j][i] = x[i] + j; +; } + +define void @imperf_nest_1(i32 signext %nx, i32 signext %ny) { +; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_1_loop_i, Loops: ( imperf_nest_1_loop_i imperf_nest_1_loop_j ) +entry: + %0 = zext i32 %ny to i64 + %1 = zext i32 %nx to i64 + %2 = mul nuw i64 %0, %1 + %vla = alloca double, i64 %2, align 8 + %3 = zext i32 %ny to i64 + %vla1 = alloca double, i64 %3, align 8 + br label %imperf_nest_1_loop_i + +imperf_nest_1_loop_i: + %i2.0 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ] + %cmp = icmp slt i32 %i2.0, %nx + br i1 %cmp, label %for.body, label %for.end17 + +for.body: + %conv = sitofp i32 %i2.0 to double + %idxprom = sext i32 %i2.0 to i64 + %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom + store double %conv, double* %arrayidx, align 8 + br label %imperf_nest_1_loop_j + +imperf_nest_1_loop_j: + %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ] + %cmp5 = icmp slt i32 %j3.0, %ny + br i1 %cmp5, label %for.body7, label %for.end + +for.body7: + %idxprom8 = sext i32 %i2.0 to i64 + %arrayidx9 = getelementptr inbounds double, double* %vla1, i64 %idxprom8 + %4 = load double, double* %arrayidx9, align 8 + %conv10 = sitofp i32 %j3.0 to double + %add = fadd double %4, %conv10 + %idxprom11 = sext i32 %j3.0 to i64 + %5 = mul nsw i64 %idxprom11, %1 + %arrayidx12 = getelementptr inbounds double, double* %vla, i64 %5 + %idxprom13 = sext i32 %i2.0 to i64 + %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13 + store double %add, double* %arrayidx14, align 8 + br label %for.inc + +for.inc: + %inc = add nsw i32 %j3.0, 1 + br label %imperf_nest_1_loop_j + +for.end: + br label %for.inc15 + +for.inc15: + %inc16 = add nsw i32 %i2.0, 1 + br label %imperf_nest_1_loop_i + +for.end17: + ret void +} + +; Test an imperfect 2-dim loop nest of the form: +; for (int i = 0; i < nx; ++i) { +; for (int j = 0; j < ny; ++j) +; y[j][i] = x[i] + j; +; y[0][i] += i; +; } + +define void @imperf_nest_2(i32 signext %nx, i32 signext %ny) { +; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_2_loop_i, Loops: ( imperf_nest_2_loop_i imperf_nest_2_loop_j ) +entry: + %0 = zext i32 %ny to i64 + %1 = zext i32 %nx to i64 + %2 = mul nuw i64 %0, %1 + %vla = alloca double, i64 %2, align 8 + %3 = zext i32 %ny to i64 + %vla1 = alloca double, i64 %3, align 8 + br label %imperf_nest_2_loop_i + +imperf_nest_2_loop_i: + %i2.0 = phi i32 [ 0, %entry ], [ %inc17, %for.inc16 ] + %cmp = icmp slt i32 %i2.0, %nx + br i1 %cmp, label %for.body, label %for.end18 + +for.body: + br label %imperf_nest_2_loop_j + +imperf_nest_2_loop_j: + %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ] + %cmp5 = icmp slt i32 %j3.0, %ny + br i1 %cmp5, label %for.body6, label %for.end + +for.body6: + %idxprom = sext i32 %i2.0 to i64 + %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom + %4 = load double, double* %arrayidx, align 8 + %conv = sitofp i32 %j3.0 to double + %add = fadd double %4, %conv + %idxprom7 = sext i32 %j3.0 to i64 + %5 = mul nsw i64 %idxprom7, %1 + %arrayidx8 = getelementptr inbounds double, double* %vla, i64 %5 + %idxprom9 = sext i32 %i2.0 to i64 + %arrayidx10 = getelementptr inbounds double, double* %arrayidx8, i64 %idxprom9 + store double %add, double* %arrayidx10, align 8 + br label %for.inc + +for.inc: + %inc = add nsw i32 %j3.0, 1 + br label %imperf_nest_2_loop_j + +for.end: + %conv11 = sitofp i32 %i2.0 to double + %6 = mul nsw i64 0, %1 + %arrayidx12 = getelementptr inbounds double, double* %vla, i64 %6 + %idxprom13 = sext i32 %i2.0 to i64 + %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13 + %7 = load double, double* %arrayidx14, align 8 + %add15 = fadd double %7, %conv11 + store double %add15, double* %arrayidx14, align 8 + br label %for.inc16 + +for.inc16: + %inc17 = add nsw i32 %i2.0, 1 + br label %imperf_nest_2_loop_i + +for.end18: + ret void +} + +; Test an imperfect 2-dim loop nest of the form: +; for (i = 0; i < nx; ++i) { +; for (j = 0; j < ny-nk; ++j) +; y[i][j] = x[i] + j; +; for (j = ny-nk; j < ny; ++j) +; y[i][j] = x[i] - j; +; } + +define void @imperf_nest_3(i32 signext %nx, i32 signext %ny, i32 signext %nk) { +; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_3_loop_i, Loops: ( imperf_nest_3_loop_i imperf_nest_3_loop_j imperf_nest_3_loop_k ) +entry: + %0 = zext i32 %nx to i64 + %1 = zext i32 %ny to i64 + %2 = mul nuw i64 %0, %1 + %vla = alloca double, i64 %2, align 8 + %3 = zext i32 %ny to i64 + %vla1 = alloca double, i64 %3, align 8 + br label %imperf_nest_3_loop_i + +imperf_nest_3_loop_i: ; preds = %for.inc25, %entry + %i.0 = phi i32 [ 0, %entry ], [ %inc26, %for.inc25 ] + %cmp = icmp slt i32 %i.0, %nx + br i1 %cmp, label %for.body, label %for.end27 + +for.body: ; preds = %for.cond + br label %imperf_nest_3_loop_j + +imperf_nest_3_loop_j: ; preds = %for.inc, %for.body + %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ] + %sub = sub nsw i32 %ny, %nk + %cmp3 = icmp slt i32 %j.0, %sub + br i1 %cmp3, label %for.body4, label %for.end + +for.body4: ; preds = %imperf_nest_3_loop_j + %idxprom = sext i32 %i.0 to i64 + %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom + %4 = load double, double* %arrayidx, align 8 + %conv = sitofp i32 %j.0 to double + %add = fadd double %4, %conv + %idxprom5 = sext i32 %i.0 to i64 + %5 = mul nsw i64 %idxprom5, %1 + %arrayidx6 = getelementptr inbounds double, double* %vla, i64 %5 + %idxprom7 = sext i32 %j.0 to i64 + %arrayidx8 = getelementptr inbounds double, double* %arrayidx6, i64 %idxprom7 + store double %add, double* %arrayidx8, align 8 + br label %for.inc + +for.inc: ; preds = %for.body4 + %inc = add nsw i32 %j.0, 1 + br label %imperf_nest_3_loop_j + +for.end: ; preds = %imperf_nest_3_loop_j + %sub9 = sub nsw i32 %ny, %nk + br label %imperf_nest_3_loop_k + +imperf_nest_3_loop_k: ; preds = %for.inc22, %for.end + %j.1 = phi i32 [ %sub9, %for.end ], [ %inc23, %for.inc22 ] + %cmp11 = icmp slt i32 %j.1, %ny + br i1 %cmp11, label %for.body13, label %for.end24 + +for.body13: ; preds = %imperf_nest_3_loop_k + %idxprom14 = sext i32 %i.0 to i64 + %arrayidx15 = getelementptr inbounds double, double* %vla1, i64 %idxprom14 + %6 = load double, double* %arrayidx15, align 8 + %conv16 = sitofp i32 %j.1 to double + %sub17 = fsub double %6, %conv16 + %idxprom18 = sext i32 %i.0 to i64 + %7 = mul nsw i64 %idxprom18, %1 + %arrayidx19 = getelementptr inbounds double, double* %vla, i64 %7 + %idxprom20 = sext i32 %j.1 to i64 + %arrayidx21 = getelementptr inbounds double, double* %arrayidx19, i64 %idxprom20 + store double %sub17, double* %arrayidx21, align 8 + br label %for.inc22 + +for.inc22: ; preds = %for.body13 + %inc23 = add nsw i32 %j.1, 1 + br label %imperf_nest_3_loop_k + +for.end24: ; preds = %imperf_nest_3_loop_k + br label %for.inc25 + +for.inc25: ; preds = %for.end24 + %inc26 = add nsw i32 %i.0, 1 + br label %imperf_nest_3_loop_i + +for.end27: ; preds = %for.cond + ret void +} + +; Test an imperfect loop nest of the form: +; for (i = 0; i < nx; ++i) { +; for (j = 0; j < ny-nk; ++j) +; for (k = 0; k < nk; ++k) +; y[i][j][k] = x[i+j] + k; +; for (j = ny-nk; j < ny; ++j) +; y[i][j][0] = x[i] - j; +; } + +define void @imperf_nest_4(i32 signext %nx, i32 signext %ny, i32 signext %nk) { +; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_4_loop_j, Loops: ( imperf_nest_4_loop_j imperf_nest_4_loop_k ) +; CHECK-LABEL: IsPerfect=false, Depth=3, OutermostLoop: imperf_nest_4_loop_i, Loops: ( imperf_nest_4_loop_i imperf_nest_4_loop_j imperf_nest_4_loop_j2 imperf_nest_4_loop_k ) +entry: + %0 = zext i32 %nx to i64 + %1 = zext i32 %ny to i64 + %2 = zext i32 %nk to i64 + %3 = mul nuw i64 %0, %1 + %4 = mul nuw i64 %3, %2 + %vla = alloca double, i64 %4, align 8 + %5 = zext i32 %ny to i64 + %vla1 = alloca double, i64 %5, align 8 + %cmp5 = icmp slt i32 0, %nx + br i1 %cmp5, label %imperf_nest_4_loop_i.lr.ph, label %for.end37 + +imperf_nest_4_loop_i.lr.ph: + br label %imperf_nest_4_loop_i + +imperf_nest_4_loop_i: + %i.0 = phi i32 [ 0, %imperf_nest_4_loop_i.lr.ph ], [ %inc36, %for.inc35 ] + %sub2 = sub nsw i32 %ny, %nk + %cmp33 = icmp slt i32 0, %sub2 + br i1 %cmp33, label %imperf_nest_4_loop_j.lr.ph, label %for.end17 + +imperf_nest_4_loop_j.lr.ph: + br label %imperf_nest_4_loop_j + +imperf_nest_4_loop_j: + %j.0 = phi i32 [ 0, %imperf_nest_4_loop_j.lr.ph ], [ %inc16, %for.inc15 ] + %cmp61 = icmp slt i32 0, %nk + br i1 %cmp61, label %imperf_nest_4_loop_k.lr.ph, label %for.end + +imperf_nest_4_loop_k.lr.ph: + br label %imperf_nest_4_loop_k + +imperf_nest_4_loop_k: + %k.0 = phi i32 [ 0, %imperf_nest_4_loop_k.lr.ph ], [ %inc, %for.inc ] + %add = add nsw i32 %i.0, %j.0 + %idxprom = sext i32 %add to i64 + %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom + %6 = load double, double* %arrayidx, align 8 + %conv = sitofp i32 %k.0 to double + %add8 = fadd double %6, %conv + %idxprom9 = sext i32 %i.0 to i64 + %7 = mul nuw i64 %1, %2 + %8 = mul nsw i64 %idxprom9, %7 + %arrayidx10 = getelementptr inbounds double, double* %vla, i64 %8 + %idxprom11 = sext i32 %j.0 to i64 + %9 = mul nsw i64 %idxprom11, %2 + %arrayidx12 = getelementptr inbounds double, double* %arrayidx10, i64 %9 + %idxprom13 = sext i32 %k.0 to i64 + %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13 + store double %add8, double* %arrayidx14, align 8 + br label %for.inc + +for.inc: + %inc = add nsw i32 %k.0, 1 + %cmp6 = icmp slt i32 %inc, %nk + br i1 %cmp6, label %imperf_nest_4_loop_k, label %for.cond5.for.end_crit_edge + +for.cond5.for.end_crit_edge: + br label %for.end + +for.end: + br label %for.inc15 + +for.inc15: + %inc16 = add nsw i32 %j.0, 1 + %sub = sub nsw i32 %ny, %nk + %cmp3 = icmp slt i32 %inc16, %sub + br i1 %cmp3, label %imperf_nest_4_loop_j, label %for.cond2.for.end17_crit_edge + +for.cond2.for.end17_crit_edge: + br label %for.end17 + +for.end17: + %sub18 = sub nsw i32 %ny, %nk + %cmp204 = icmp slt i32 %sub18, %ny + br i1 %cmp204, label %imperf_nest_4_loop_j2.lr.ph, label %for.end34 + +imperf_nest_4_loop_j2.lr.ph: + br label %imperf_nest_4_loop_j2 + +imperf_nest_4_loop_j2: + %j.1 = phi i32 [ %sub18, %imperf_nest_4_loop_j2.lr.ph ], [ %inc33, %for.inc32 ] + %idxprom23 = sext i32 %i.0 to i64 + %arrayidx24 = getelementptr inbounds double, double* %vla1, i64 %idxprom23 + %10 = load double, double* %arrayidx24, align 8 + %conv25 = sitofp i32 %j.1 to double + %sub26 = fsub double %10, %conv25 + %idxprom27 = sext i32 %i.0 to i64 + %idxprom29 = sext i32 %j.1 to i64 + %11 = mul nsw i64 %idxprom29, %2 + %12 = mul nuw i64 %1, %2 + %13 = mul nsw i64 %idxprom27, %12 + %arrayidx28 = getelementptr inbounds double, double* %vla, i64 %13 + %arrayidx30 = getelementptr inbounds double, double* %arrayidx28, i64 %11 + %arrayidx31 = getelementptr inbounds double, double* %arrayidx30, i64 0 + store double %sub26, double* %arrayidx31, align 8 + br label %for.inc32 + +for.inc32: + %inc33 = add nsw i32 %j.1, 1 + %cmp20 = icmp slt i32 %inc33, %ny + br i1 %cmp20, label %imperf_nest_4_loop_j2, label %for.cond19.for.end34_crit_edge + +for.cond19.for.end34_crit_edge: + br label %for.end34 + +for.end34: + br label %for.inc35 + +for.inc35: + %inc36 = add nsw i32 %i.0, 1 + %cmp = icmp slt i32 %inc36, %nx + br i1 %cmp, label %imperf_nest_4_loop_i, label %for.cond.for.end37_crit_edge + +for.cond.for.end37_crit_edge: + br label %for.end37 + +for.end37: + ret void +} + +; Test an imperfect loop nest of the form: +; for (int i = 0; i < nx; ++i) +; if (i > 5) { +; for (int j = 0; j < ny; ++j) +; y[j][i] = x[i][j] + j; +; } + +define void @imperf_nest_5(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) { +; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_5_loop_i, Loops: ( imperf_nest_5_loop_i imperf_nest_5_loop_j ) +entry: + %cmp2 = icmp slt i32 0, %nx + br i1 %cmp2, label %imperf_nest_5_loop_i.lr.ph, label %for.end13 + +imperf_nest_5_loop_i.lr.ph: + br label %imperf_nest_5_loop_i + +imperf_nest_5_loop_i: + %i.0 = phi i32 [ 0, %imperf_nest_5_loop_i.lr.ph ], [ %inc12, %for.inc11 ] + %cmp1 = icmp sgt i32 %i.0, 5 + br i1 %cmp1, label %if.then, label %if.end + +if.then: + %cmp31 = icmp slt i32 0, %ny + br i1 %cmp31, label %imperf_nest_5_loop_j.lr.ph, label %for.end + +imperf_nest_5_loop_j.lr.ph: + br label %imperf_nest_5_loop_j + +imperf_nest_5_loop_j: + %j.0 = phi i32 [ 0, %imperf_nest_5_loop_j.lr.ph ], [ %inc, %for.inc ] + %idxprom = sext i32 %i.0 to i64 + %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom + %0 = load i32*, i32** %arrayidx, align 8 + %idxprom5 = sext i32 %j.0 to i64 + %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5 + %1 = load i32, i32* %arrayidx6, align 4 + %add = add nsw i32 %1, %j.0 + %idxprom7 = sext i32 %j.0 to i64 + %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7 + %2 = load i32*, i32** %arrayidx8, align 8 + %idxprom9 = sext i32 %i.0 to i64 + %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9 + store i32 %add, i32* %arrayidx10, align 4 + br label %for.inc + +for.inc: + %inc = add nsw i32 %j.0, 1 + %cmp3 = icmp slt i32 %inc, %ny + br i1 %cmp3, label %imperf_nest_5_loop_j, label %for.cond2.for.end_crit_edge + +for.cond2.for.end_crit_edge: + br label %for.end + +for.end: + br label %if.end + +if.end: + br label %for.inc11 + +for.inc11: + %inc12 = add nsw i32 %i.0, 1 + %cmp = icmp slt i32 %inc12, %nx + br i1 %cmp, label %imperf_nest_5_loop_i, label %for.cond.for.end13_crit_edge + +for.cond.for.end13_crit_edge: + br label %for.end13 + +for.end13: + ret void +} + +; Test an imperfect loop nest of the form: +; for (int i = 0; i < nx; ++i) +; if (i > 5) { // user branch +; for (int j = 1; j <= 5; j+=2) +; y[j][i] = x[i][j] + j; +; } + +define void @imperf_nest_6(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) { +; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_6_loop_i, Loops: ( imperf_nest_6_loop_i imperf_nest_6_loop_j ) +entry: + %cmp2 = icmp slt i32 0, %nx + br i1 %cmp2, label %imperf_nest_6_loop_i.lr.ph, label %for.end13 + +imperf_nest_6_loop_i.lr.ph: + br label %imperf_nest_6_loop_i + +imperf_nest_6_loop_i: + %i.0 = phi i32 [ 0, %imperf_nest_6_loop_i.lr.ph ], [ %inc12, %for.inc11 ] + %cmp1 = icmp sgt i32 %i.0, 5 + br i1 %cmp1, label %imperf_nest_6_loop_j.lr.ph, label %if.end + +imperf_nest_6_loop_j.lr.ph: + br label %imperf_nest_6_loop_j + +imperf_nest_6_loop_j: + %j.0 = phi i32 [ 1, %imperf_nest_6_loop_j.lr.ph ], [ %inc, %for.inc ] + %idxprom = sext i32 %i.0 to i64 + %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom + %0 = load i32*, i32** %arrayidx, align 8 + %idxprom5 = sext i32 %j.0 to i64 + %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5 + %1 = load i32, i32* %arrayidx6, align 4 + %add = add nsw i32 %1, %j.0 + %idxprom7 = sext i32 %j.0 to i64 + %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7 + %2 = load i32*, i32** %arrayidx8, align 8 + %idxprom9 = sext i32 %i.0 to i64 + %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9 + store i32 %add, i32* %arrayidx10, align 4 + br label %for.inc + +for.inc: + %inc = add nsw i32 %j.0, 2 + %cmp3 = icmp sle i32 %inc, 5 + br i1 %cmp3, label %imperf_nest_6_loop_j, label %for.cond2.for.end_crit_edge + +for.cond2.for.end_crit_edge: + br label %for.end + +for.end: + br label %if.end + +if.end: + br label %for.inc11 + +for.inc11: + %inc12 = add nsw i32 %i.0, 1 + %cmp = icmp slt i32 %inc12, %nx + br i1 %cmp, label %imperf_nest_6_loop_i, label %for.cond.for.end13_crit_edge + +for.cond.for.end13_crit_edge: + br label %for.end13 + +for.end13: + ret void +} diff --git a/llvm/test/Analysis/LoopNestAnalysis/infinite.ll b/llvm/test/Analysis/LoopNestAnalysis/infinite.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/LoopNestAnalysis/infinite.ll @@ -0,0 +1,35 @@ +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +; Test that the loop nest analysis is able to analyze an infinite loop in a loop nest. +define void @test1(i32** %A, i1 %cond) { +; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: for.inner, Loops: ( for.inner ) +; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: for.outer, Loops: ( for.outer for.inner ) +; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: for.infinite, Loops: ( for.infinite ) +entry: + br label %for.outer + +for.outer: + %i = phi i64 [ 0, %entry ], [ %inc_i, %for.outer.latch ] + br i1 %cond, label %for.inner, label %for.infinite + +for.inner: + %j = phi i64 [ 0, %for.outer ], [ %inc_j, %for.inner ] + %arrayidx_i = getelementptr inbounds i32*, i32** %A, i64 %i + %0 = load i32*, i32** %arrayidx_i, align 8 + %arrayidx_j = getelementptr inbounds i32, i32* %0, i64 %j + store i32 0, i32* %arrayidx_j, align 4 + %inc_j = add nsw i64 %j, 1 + %cmp_j = icmp slt i64 %inc_j, 100 + br i1 %cmp_j, label %for.inner, label %for.outer.latch + +for.infinite: + br label %for.infinite + +for.outer.latch: + %inc_i = add nsw i64 %i, 1 + %cmp_i = icmp slt i64 %inc_i, 100 + br i1 %cmp_i, label %for.outer, label %for.end + +for.end: + ret void +} diff --git a/llvm/test/Analysis/LoopNestAnalysis/perfectnest.ll b/llvm/test/Analysis/LoopNestAnalysis/perfectnest.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/LoopNestAnalysis/perfectnest.ll @@ -0,0 +1,275 @@ +; RUN: opt < %s -passes='print' -disable-output 2>&1 | FileCheck %s + +; Test a perfect 2-dim loop nest of the form: +; for(i=0; i Test) { + auto *F = M.getFunction(FuncName); + ASSERT_NE(F, nullptr) << "Could not find " << FuncName; + + TargetLibraryInfoImpl TLII; + TargetLibraryInfo TLI(TLII); + AssumptionCache AC(*F); + DominatorTree DT(*F); + LoopInfo LI(DT); + ScalarEvolution SE(*F, TLI, AC, DT, LI); + + Test(*F, LI, SE); +} + +static std::unique_ptr makeLLVMModule(LLVMContext &Context, + const char *ModuleStr) { + SMDiagnostic Err; + return parseAssemblyString(ModuleStr, Err, Context); +} + +TEST(LoopNestTest, PerfectLoopNest) { + const char *ModuleStr = + "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" + "define void @foo(i64 signext %nx, i64 signext %ny) {\n" + "entry:\n" + " br label %for.outer\n" + "for.outer:\n" + " %i = phi i64 [ 0, %entry ], [ %inc13, %for.outer.latch ]\n" + " %cmp21 = icmp slt i64 0, %ny\n" + " br i1 %cmp21, label %for.inner.preheader, label %for.outer.latch\n" + "for.inner.preheader:\n" + " br label %for.inner\n" + "for.inner:\n" + " %j = phi i64 [ 0, %for.inner.preheader ], [ %inc, %for.inner.latch ]\n" + " br label %for.inner.latch\n" + "for.inner.latch:\n" + " %inc = add nsw i64 %j, 1\n" + " %cmp2 = icmp slt i64 %inc, %ny\n" + " br i1 %cmp2, label %for.inner, label %for.inner.exit\n" + "for.inner.exit:\n" + " br label %for.outer.latch\n" + "for.outer.latch:\n" + " %inc13 = add nsw i64 %i, 1\n" + " %cmp = icmp slt i64 %inc13, %nx\n" + " br i1 %cmp, label %for.outer, label %for.outer.exit\n" + "for.outer.exit:\n" + " br label %for.end\n" + "for.end:\n" + " ret void\n" + "}\n"; + + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + Function::iterator FI = F.begin(); + // Skip the first basic block (entry), get to the outer loop header. + BasicBlock *Header = &*(++FI); + assert(Header->getName() == "for.outer"); + Loop *L = LI.getLoopFor(Header); + EXPECT_NE(L, nullptr); + + LoopNest LN(*L, SE); + EXPECT_TRUE(LN.areAllLoopsSimplifyForm()); + + // Ensure that we can identify the outermost loop in the nest. + const Loop &OL = LN.getOutermostLoop(); + EXPECT_EQ(OL.getName(), "for.outer"); + + // Ensure that we can identify the innermost loop in the nest. + const Loop *IL = LN.getInnermostLoop(); + EXPECT_NE(IL, nullptr); + EXPECT_EQ(IL->getName(), "for.inner"); + + // Ensure the loop nest is recognized as having 2 loops. + const ArrayRef Loops = LN.getLoops(); + EXPECT_EQ(Loops.size(), 2ull); + + // Ensure the loop nest is recognized as perfect in its entirety. + const SmallVector &PLV = LN.getPerfectLoops(SE); + EXPECT_EQ(PLV.size(), 1ull); + EXPECT_EQ(PLV.front().size(), 2ull); + + // Ensure the nest depth and perfect nest depth are computed correctly. + EXPECT_EQ(LN.getNestDepth(), 2u); + EXPECT_EQ(LN.getMaxPerfectDepth(), 2u); + }); +} + +TEST(LoopNestTest, ImperfectLoopNest) { + const char *ModuleStr = + "target datalayout = \"e-m:o-i64:64-f80:128-n8:16:32:64-S128\"\n" + "define void @foo(i32 signext %nx, i32 signext %ny, i32 signext %nk) {\n" + "entry:\n" + " br label %loop.i\n" + "loop.i:\n" + " %i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]\n" + " %cmp21 = icmp slt i32 0, %ny\n" + " br i1 %cmp21, label %loop.j.preheader, label %for.inci\n" + "loop.j.preheader:\n" + " br label %loop.j\n" + "loop.j:\n" + " %j = phi i32 [ %incj, %for.incj ], [ 0, %loop.j.preheader ]\n" + " %cmp22 = icmp slt i32 0, %nk\n" + " br i1 %cmp22, label %loop.k.preheader, label %for.incj\n" + "loop.k.preheader:\n" + " call void @bar()\n" + " br label %loop.k\n" + "loop.k:\n" + " %k = phi i32 [ %inck, %for.inck ], [ 0, %loop.k.preheader ]\n" + " br label %for.inck\n" + "for.inck:\n" + " %inck = add nsw i32 %k, 1\n" + " %cmp5 = icmp slt i32 %inck, %nk\n" + " br i1 %cmp5, label %loop.k, label %for.incj.loopexit\n" + "for.incj.loopexit:\n" + " br label %for.incj\n" + "for.incj:\n" + " %incj = add nsw i32 %j, 1\n" + " %cmp2 = icmp slt i32 %incj, %ny\n" + " br i1 %cmp2, label %loop.j, label %for.inci.loopexit\n" + "for.inci.loopexit:\n" + " br label %for.inci\n" + "for.inci:\n" + " %inci = add nsw i32 %i, 1\n" + " %cmp = icmp slt i32 %inci, %nx\n" + " br i1 %cmp, label %loop.i, label %loop.i.end\n" + "loop.i.end:\n" + " ret void\n" + "}\n" + "declare void @bar()\n"; + + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleStr); + + runTest(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + Function::iterator FI = F.begin(); + // Skip the first basic block (entry), get to the outermost loop header. + BasicBlock *Header = &*(++FI); + assert(Header->getName() == "loop.i"); + Loop *L = LI.getLoopFor(Header); + EXPECT_NE(L, nullptr); + + LoopNest LN(*L, SE); + EXPECT_TRUE(LN.areAllLoopsSimplifyForm()); + + dbgs() << "LN: " << LN << "\n"; + + // Ensure that we can identify the outermost loop in the nest. + const Loop &OL = LN.getOutermostLoop(); + EXPECT_EQ(OL.getName(), "loop.i"); + + // Ensure that we can identify the innermost loop in the nest. + const Loop *IL = LN.getInnermostLoop(); + EXPECT_NE(IL, nullptr); + EXPECT_EQ(IL->getName(), "loop.k"); + + // Ensure the loop nest is recognized as having 3 loops. + const ArrayRef Loops = LN.getLoops(); + EXPECT_EQ(Loops.size(), 3ull); + + // Ensure the loop nest is recognized as having 2 separate perfect loops groups. + const SmallVector &PLV = LN.getPerfectLoops(SE); + EXPECT_EQ(PLV.size(), 2ull); + EXPECT_EQ(PLV.front().size(), 2ull); + EXPECT_EQ(PLV.back().size(), 1ull); + + // Ensure the nest depth and perfect nest depth are computed correctly. + EXPECT_EQ(LN.getNestDepth(), 3u); + EXPECT_EQ(LN.getMaxPerfectDepth(), 2u); + }); +} +