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 
21 namespace llvm {
22 
23 using LoopVectorTy = SmallVector<Loop *, 8>;
24 class LPMUpdater;
25 
26 /// This class represents a loop nest and can be used to query its properties.
27 class LoopNest {
28 public:
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). Return the last basic block found or \p End if it was
65   /// reached during the search.
66   static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
67                                                const BasicBlock *End);
68 
69   /// Return the outermost loop in the loop nest.
70   Loop &getOutermostLoop() const { return *Loops.front(); }
71 
72   /// Return the innermost loop in the loop nest if the nest has only one
73   /// innermost loop, and a nullptr otherwise.
74   /// Note: the innermost loop returned is not necessarily perfectly nested.
75   Loop *getInnermostLoop() const {
76     if (Loops.size() == 1)
77       return Loops.back();
78 
79     // The loops in the 'Loops' vector have been collected in breadth first
80     // order, therefore if the last 2 loops in it have the same nesting depth
81     // there isn't a unique innermost loop in the nest.
82     Loop *LastLoop = Loops.back();
83     auto SecondLastLoopIter = ++Loops.rbegin();
84     return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth())
85                ? nullptr
86                : LastLoop;
87   }
88 
89   /// Return the loop at the given \p Index.
90   Loop *getLoop(unsigned Index) const {
91     assert(Index < Loops.size() && "Index is out of bounds");
92     return Loops[Index];
93   }
94 
95   /// Return the number of loops in the nest.
96   size_t getNumLoops() const { return Loops.size(); }
97 
98   /// Get the loops in the nest.
99   ArrayRef<Loop *> getLoops() const { return Loops; }
100 
101   /// Retrieve a vector of perfect loop nests contained in the current loop
102   /// nest. For example, given the following  nest containing 4 loops, this
103   /// member function would return {{L1,L2},{L3,L4}}.
104   /// \code
105   ///   for(i) // L1
106   ///     for(j) // L2
107   ///       <code>
108   ///       for(k) // L3
109   ///         for(l) // L4
110   /// \endcode
111   SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const;
112 
113   /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop)
114   /// For example given the loop nest:
115   /// \code
116   ///   for(i)      // loop at level 1 and Root of the nest
117   ///     for(j1)   // loop at level 2
118   ///       for(k)  // loop at level 3
119   ///     for(j2)   // loop at level 2
120   /// \endcode
121   /// getNestDepth() would return 3.
122   unsigned getNestDepth() const {
123     int NestDepth =
124         Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1;
125     assert(NestDepth > 0 && "Expecting NestDepth to be at least 1");
126     return NestDepth;
127   }
128 
129   /// Return the maximum perfect nesting depth.
130   unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
131 
132   /// Return true if all loops in the loop nest are in simplify form.
133   bool areAllLoopsSimplifyForm() const {
134     return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
135   }
136 
137   /// Return true if all loops in the loop nest are in rotated form.
138   bool areAllLoopsRotatedForm() const {
139     return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
140   }
141 
142   StringRef getName() const { return Loops.front()->getName(); }
143 
144 protected:
145   const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
146   LoopVectorTy Loops; // the loops in the nest (in breadth first order).
147 };
148 
149 raw_ostream &operator<<(raw_ostream &, const LoopNest &);
150 
151 /// This analysis provides information for a loop nest. The analysis runs on
152 /// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
153 class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
154   friend AnalysisInfoMixin<LoopNestAnalysis>;
155   static AnalysisKey Key;
156 
157 public:
158   using Result = LoopNest;
159   Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR);
160 };
161 
162 /// Printer pass for the \c LoopNest results.
163 class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> {
164   raw_ostream &OS;
165 
166 public:
167   explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {}
168 
169   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
170                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
171 };
172 
173 } // namespace llvm
174 
175 #endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H
176