1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
//===- 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 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<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 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). 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);
/// 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];
}
/// 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; }
/// 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(); });
}
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).
};
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
|
