Index: llvm/include/llvm/Analysis/LoopNestAnalysis.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/LoopNestAnalysis.h @@ -0,0 +1,170 @@ +//===- 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 { + +/// This class represents a loop nest and can be used to query its properties. +class LoopNest { +public: + using LoopVector = SmallVector; + + /// Construct a loop nest rooted by loop \p Root. + LoopNest(Loop &Root, ScalarEvolution &SE); + + LoopNest() = delete; + LoopNest &operator=(const LoopNest &) = delete; + + /// Return true if the given loops \p OuterLoop and \p InnerLoop are + /// perfectly nested with respect to each other, and false otherwise. + 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 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(j1) // loop at level 2 + /// for(k) // loop at level 3 + /// for(j2) // loop at level 2 + /// \endcode + /// getNestDepth(Loop_i) would return 3. + static unsigned getNestDepth(const Loop &Root); + + /// Return true if the loop nest rooted by loop \p Root is perfect. + static bool isPerfectNest(const Loop &Root, ScalarEvolution &SE); + + /// Return the outermost loop in the loop nest. + const Loop &getOutermostLoop() const { return *Loops.front(); } + Loop &getOutermostLoop() { + return const_cast( + static_cast(*this).getOutermostLoop()); + } + + /// Return the innermost loop in the loop nest if the nest has only one + /// innermost loop, and a nullptr otherwise. + const 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; + } + Loop *getInnermostLoop() { + return const_cast( + static_cast(*this).getInnermostLoop()); + } + + /// Return the loop at the given \p Index. + const Loop *getLoop(unsigned Index) const { + assert(Index < Loops.size() && "Index is out of bounds"); + return Loops[Index]; + } + Loop *getLoop(unsigned Index) { + return const_cast( + static_cast(*this).getLoop(Index)); + } + + /// Get the loops in the nest. + const LoopVector &getLoops() const { return Loops; } + + /// Return the loop nest depth (e.g. 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 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(); }); + } + + /// Return the maximum perfect nesting depth. + unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; } + +private: + /// 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); + +protected: + const unsigned MaxPerfectDepth; // maximum perfect nesting depth level. + LoopVector Loops; // the loops in the nest (in breath 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 Index: llvm/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/CMakeLists.txt +++ llvm/lib/Analysis/CMakeLists.txt @@ -53,6 +53,7 @@ LoopAccessAnalysis.cpp LoopAnalysisManager.cpp LoopCacheAnalysis.cpp + LoopNestAnalysis.cpp LoopUnrollAnalyzer.cpp LoopInfo.cpp LoopPass.cpp Index: llvm/lib/Analysis/LoopNestAnalysis.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/LoopNestAnalysis.cpp @@ -0,0 +1,281 @@ +//===- 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"; + +//===----------------------------------------------------------------------===// +// LoopNest implementation +// + +LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE) + : MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) { + for (Loop *L : breadth_first(&Root)) + Loops.push_back(L); +} + +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 containSafeInstructions = [&](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 (!containSafeInstructions(*OuterLoopHeader) || + !containSafeInstructions(*OuterLoopLatch) || + (InnerLoopPreHeader != OuterLoopHeader && + !containSafeInstructions(*InnerLoopPreHeader)) || + !containSafeInstructions(*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; +} + +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; +} + +unsigned LoopNest::getNestDepth(const Loop &Root) { + LoopVector Loops; + for (Loop *L : breadth_first(const_cast(&Root))) + Loops.push_back(L); + + return (Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1); +} + +bool LoopNest::isPerfectNest(const Loop &Root, ScalarEvolution &SE) { + LLVM_DEBUG(dbgs() << "Checking whether loop nest rooted by loop '" + << Root.getName() << "' is a perfect nest\n";); + + return getMaxPerfectDepth(Root, SE) == getNestDepth(Root); +} + +bool LoopNest::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; +} + +//===----------------------------------------------------------------------===// +// LoopNestAnalysis implementation +// + +AnalysisKey LoopNestAnalysis::Key; + +LoopNestAnalysis::Result +LoopNestAnalysis::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR) { + return LoopNest(L, AR.SE); +} + +//===----------------------------------------------------------------------===// +// LoopNestPrinterPass implementation +// + +PreservedAnalyses LoopNestPrinterPass::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LPMUpdater &U) { + const LoopNest &LN = AM.getResult(L, AR); + OS << LN << "\n"; + + return PreservedAnalyses::all(); +} Index: llvm/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/lib/Passes/PassBuilder.cpp +++ 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" Index: llvm/lib/Passes/PassRegistry.def =================================================================== --- llvm/lib/Passes/PassRegistry.def +++ llvm/lib/Passes/PassRegistry.def @@ -283,6 +283,7 @@ LOOP_ANALYSIS("access-info", LoopAccessAnalysis()) LOOP_ANALYSIS("ddg", DDGAnalysis()) LOOP_ANALYSIS("ivusers", IVUsersAnalysis()) +LOOP_ANALYSIS("loopnest", LoopNestAnalysis()) LOOP_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC)) #undef LOOP_ANALYSIS @@ -306,6 +307,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()) Index: llvm/test/Analysis/LoopNestAnalysis/imperfectnest.ll =================================================================== --- /dev/null +++ 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 +} Index: llvm/test/Analysis/LoopNestAnalysis/infinite.ll =================================================================== --- /dev/null +++ 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 +} Index: llvm/test/Analysis/LoopNestAnalysis/perfectnest.ll =================================================================== --- /dev/null +++ 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