//===- 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/ADT/STLExtras.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
namespace llvm {
using LoopVectorTy = SmallVector<Loop *, 8>;
class LPMUpdater;
/// This class represents a loop nest and can be used to query its properties.
class LLVM_EXTERNAL_VISIBILITY LoopNest {
public:
using InstrVectorTy = SmallVector<const Instruction *>;
/// Construct a loop nest rooted by loop \p Root.
LoopNest(Loop &Root, ScalarEvolution &SE);
LoopNest() = delete;
/// Construct a LoopNest object.
static std::unique_ptr<LoopNest> 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)
/// for(k)
/// \endcode
/// arePerfectlyNested(loop_i, loop_j, SE) would return true.
/// arePerfectlyNested(loop_j, loop_k, SE) would return true.
/// arePerfectlyNested(loop_i, loop_k, SE) would return false.
static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
ScalarEvolution &SE);
/// Return a vector of instructions that prevent the LoopNest given
/// by loops \p OuterLoop and \p InnerLoop from being perfect.
static InstrVectorTy getInterveningInstructions(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
/// <code>
/// for(k) // loop at level 3
/// \endcode
/// getMaxPerfectDepth(Loop_i) would return 2.
static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE);
/// Recursivelly traverse all empty 'single successor' basic blocks of \p From
/// (if there are any). When \p CheckUniquePred is set to true, check if
/// each of the empty single successors has a unique predecessor. Return
/// the last basic block found or \p End if it was reached during the search.
static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
const BasicBlock *End,
bool CheckUniquePred = false);
/// 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.
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];
}
/// Get the loop index of the given loop \p L.
unsigned getLoopIndex(const Loop &L) const {
for (unsigned I = 0; I < getNumLoops(); ++I)
if (getLoop(I) == &L)
return I;
llvm_unreachable("Loop not in the loop nest");
}
/// Return the number of loops in the nest.
size_t getNumLoops() const { return Loops.size(); }
/// Get the loops in the nest.
ArrayRef<Loop *> getLoops() const { return Loops; }
/// Get the loops in the nest at the given \p Depth.
LoopVectorTy getLoopsAtDepth(unsigned Depth) const {
assert(Depth >= Loops.front()->getLoopDepth() &&
Depth <= Loops.back()->getLoopDepth() && "Invalid depth");
LoopVectorTy Result;
for (unsigned I = 0; I < getNumLoops(); ++I) {
Loop *L = getLoop(I);
if (L->getLoopDepth() == Depth)
Result.push_back(L);
else if (L->getLoopDepth() > Depth)
break;
}
return Result;
}
/// 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
/// <code>
/// for(k) // L3
/// for(l) // L4
/// \endcode
SmallVector<LoopVectorTy, 4> 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 {
int NestDepth =
Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1;
assert(NestDepth > 0 && "Expecting NestDepth to be at least 1");
return NestDepth;
}
/// 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 all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
}
/// Return true if all loops in the loop nest are in rotated form.
bool areAllLoopsRotatedForm() const {
return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
}
/// Return the function to which the loop-nest belongs.
Function *getParent() const {
return Loops.front()->getHeader()->getParent();
}
StringRef getName() const { return Loops.front()->getName(); }
protected:
const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
LoopVectorTy Loops; // the loops in the nest (in breadth first order).
private:
enum LoopNestEnum {
PerfectLoopNest,
ImperfectLoopNest,
InvalidLoopStructure,
OuterLoopLowerBoundUnknown
};
static LoopNestEnum analyzeLoopNestForPerfectNest(const Loop &OuterLoop,
const Loop &InnerLoop,
ScalarEvolution &SE);
};
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<LoopNestAnalysis>.
class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
friend AnalysisInfoMixin<LoopNestAnalysis>;
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<LoopNestPrinterPass> {
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