1//===- llvm/Analysis/LoopNestAnalysis.h -------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file defines the interface for the loop nest analysis.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_LOOPNESTANALYSIS_H
15#define LLVM_ANALYSIS_LOOPNESTANALYSIS_H
16
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/Analysis/LoopAnalysisManager.h"
19#include "llvm/Analysis/LoopInfo.h"
20
21namespace llvm {
22
23using LoopVectorTy = SmallVector<Loop *, 8>;
24class LPMUpdater;
25
26/// This class represents a loop nest and can be used to query its properties.
27class LoopNest {
28public:
29  /// Construct a loop nest rooted by loop \p Root.
30  LoopNest(Loop &Root, ScalarEvolution &SE);
31
32  LoopNest() = delete;
33  LoopNest &operator=(const LoopNest &) = delete;
34
35  /// Construct a LoopNest object.
36  static std::unique_ptr<LoopNest> getLoopNest(Loop &Root, ScalarEvolution &SE);
37
38  /// Return true if the given loops \p OuterLoop and \p InnerLoop are
39  /// perfectly nested with respect to each other, and false otherwise.
40  /// Example:
41  /// \code
42  ///   for(i)
43  ///     for(j)
44  ///       for(k)
45  /// \endcode
46  /// arePerfectlyNested(loop_i, loop_j, SE) would return true.
47  /// arePerfectlyNested(loop_j, loop_k, SE) would return true.
48  /// arePerfectlyNested(loop_i, loop_k, SE) would return false.
49  static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
50                                 ScalarEvolution &SE);
51
52  /// Return the maximum nesting depth of the loop nest rooted by loop \p Root.
53  /// For example given the loop nest:
54  /// \code
55  ///   for(i)     // loop at level 1 and Root of the nest
56  ///     for(j)   // loop at level 2
57  ///       <code>
58  ///       for(k) // loop at level 3
59  /// \endcode
60  /// getMaxPerfectDepth(Loop_i) would return 2.
61  static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE);
62
63  /// Recursivelly traverse all empty 'single successor' basic blocks of \p From
64  /// (if there are any). When \p CheckUniquePred is set to true, check if
65  /// each of the empty single successors has a unique predecessor. Return
66  /// the last basic block found or \p End if it was reached during the search.
67  static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
68                                               const BasicBlock *End,
69                                               bool CheckUniquePred = false);
70
71  /// Return the outermost loop in the loop nest.
72  Loop &getOutermostLoop() const { return *Loops.front(); }
73
74  /// Return the innermost loop in the loop nest if the nest has only one
75  /// innermost loop, and a nullptr otherwise.
76  /// Note: the innermost loop returned is not necessarily perfectly nested.
77  Loop *getInnermostLoop() const {
78    if (Loops.size() == 1)
79      return Loops.back();
80
81    // The loops in the 'Loops' vector have been collected in breadth first
82    // order, therefore if the last 2 loops in it have the same nesting depth
83    // there isn't a unique innermost loop in the nest.
84    Loop *LastLoop = Loops.back();
85    auto SecondLastLoopIter = ++Loops.rbegin();
86    return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth())
87               ? nullptr
88               : LastLoop;
89  }
90
91  /// Return the loop at the given \p Index.
92  Loop *getLoop(unsigned Index) const {
93    assert(Index < Loops.size() && "Index is out of bounds");
94    return Loops[Index];
95  }
96
97  /// Return the number of loops in the nest.
98  size_t getNumLoops() const { return Loops.size(); }
99
100  /// Get the loops in the nest.
101  ArrayRef<Loop *> getLoops() const { return Loops; }
102
103  /// Retrieve a vector of perfect loop nests contained in the current loop
104  /// nest. For example, given the following  nest containing 4 loops, this
105  /// member function would return {{L1,L2},{L3,L4}}.
106  /// \code
107  ///   for(i) // L1
108  ///     for(j) // L2
109  ///       <code>
110  ///       for(k) // L3
111  ///         for(l) // L4
112  /// \endcode
113  SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const;
114
115  /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop)
116  /// For example given the loop nest:
117  /// \code
118  ///   for(i)      // loop at level 1 and Root of the nest
119  ///     for(j1)   // loop at level 2
120  ///       for(k)  // loop at level 3
121  ///     for(j2)   // loop at level 2
122  /// \endcode
123  /// getNestDepth() would return 3.
124  unsigned getNestDepth() const {
125    int NestDepth =
126        Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1;
127    assert(NestDepth > 0 && "Expecting NestDepth to be at least 1");
128    return NestDepth;
129  }
130
131  /// Return the maximum perfect nesting depth.
132  unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
133
134  /// Return true if all loops in the loop nest are in simplify form.
135  bool areAllLoopsSimplifyForm() const {
136    return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
137  }
138
139  /// Return true if all loops in the loop nest are in rotated form.
140  bool areAllLoopsRotatedForm() const {
141    return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
142  }
143
144  /// Return the function to which the loop-nest belongs.
145  Function *getParent() const {
146    return Loops.front()->getHeader()->getParent();
147  }
148
149  StringRef getName() const { return Loops.front()->getName(); }
150
151protected:
152  const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
153  LoopVectorTy Loops; // the loops in the nest (in breadth first order).
154};
155
156raw_ostream &operator<<(raw_ostream &, const LoopNest &);
157
158/// This analysis provides information for a loop nest. The analysis runs on
159/// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
160class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
161  friend AnalysisInfoMixin<LoopNestAnalysis>;
162  static AnalysisKey Key;
163
164public:
165  using Result = LoopNest;
166  Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR);
167};
168
169/// Printer pass for the \c LoopNest results.
170class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> {
171  raw_ostream &OS;
172
173public:
174  explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {}
175
176  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
177                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
178};
179
180} // namespace llvm
181
182#endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H
183