1 //===- LoopPassManager.h - Loop pass management -----------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
11 /// This header provides classes for managing passes over loops in LLVM IR.
12 ///
13 //===----------------------------------------------------------------------===//
14
15 #ifndef LLVM_ANALYSIS_LOOPPASSMANAGER_H
16 #define LLVM_ANALYSIS_LOOPPASSMANAGER_H
17
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/IR/PassManager.h"
21
22 namespace llvm {
23
24 extern template class PassManager<Loop>;
25 /// \brief The loop pass manager.
26 ///
27 /// See the documentation for the PassManager template for details. It runs a
28 /// sequency of loop passes over each loop that the manager is run over. This
29 /// typedef serves as a convenient way to refer to this construct.
30 typedef PassManager<Loop> LoopPassManager;
31
32 extern template class AnalysisManager<Loop>;
33 /// \brief The loop analysis manager.
34 ///
35 /// See the documentation for the AnalysisManager template for detail
36 /// documentation. This typedef serves as a convenient way to refer to this
37 /// construct in the adaptors and proxies used to integrate this into the larger
38 /// pass manager infrastructure.
39 typedef AnalysisManager<Loop> LoopAnalysisManager;
40
41 extern template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>;
42 /// A proxy from a \c LoopAnalysisManager to a \c Function.
43 typedef InnerAnalysisManagerProxy<LoopAnalysisManager, Function>
44 LoopAnalysisManagerFunctionProxy;
45
46 extern template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop>;
47 /// A proxy from a \c FunctionAnalysisManager to a \c Loop.
48 typedef OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop>
49 FunctionAnalysisManagerLoopProxy;
50
51 /// Returns the minimum set of Analyses that all loop passes must preserve.
52 PreservedAnalyses getLoopPassPreservedAnalyses();
53
54 /// \brief Adaptor that maps from a function to its loops.
55 ///
56 /// Designed to allow composition of a LoopPass(Manager) and a
57 /// FunctionPassManager. Note that if this pass is constructed with a \c
58 /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy
59 /// analysis prior to running the loop passes over the function to enable a \c
60 /// LoopAnalysisManager to be used within this run safely.
61 template <typename LoopPassT>
62 class FunctionToLoopPassAdaptor
63 : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> {
64 public:
FunctionToLoopPassAdaptor(LoopPassT Pass)65 explicit FunctionToLoopPassAdaptor(LoopPassT Pass)
66 : Pass(std::move(Pass)) {}
67 // We have to explicitly define all the special member functions because MSVC
68 // refuses to generate them.
FunctionToLoopPassAdaptor(const FunctionToLoopPassAdaptor & Arg)69 FunctionToLoopPassAdaptor(const FunctionToLoopPassAdaptor &Arg)
70 : Pass(Arg.Pass) {}
FunctionToLoopPassAdaptor(FunctionToLoopPassAdaptor && Arg)71 FunctionToLoopPassAdaptor(FunctionToLoopPassAdaptor &&Arg)
72 : Pass(std::move(Arg.Pass)) {}
swap(FunctionToLoopPassAdaptor & LHS,FunctionToLoopPassAdaptor & RHS)73 friend void swap(FunctionToLoopPassAdaptor &LHS,
74 FunctionToLoopPassAdaptor &RHS) {
75 using std::swap;
76 swap(LHS.Pass, RHS.Pass);
77 }
78 FunctionToLoopPassAdaptor &operator=(FunctionToLoopPassAdaptor RHS) {
79 swap(*this, RHS);
80 return *this;
81 }
82
83 /// \brief Runs the loop passes across every loop in the function.
run(Function & F,FunctionAnalysisManager & AM)84 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
85 // Setup the loop analysis manager from its proxy.
86 LoopAnalysisManager &LAM =
87 AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
88 // Get the loop structure for this function
89 LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
90
91 PreservedAnalyses PA = PreservedAnalyses::all();
92
93 // We want to visit the loops in reverse post-order. We'll build the stack
94 // of loops to visit in Loops by first walking the loops in pre-order.
95 SmallVector<Loop *, 2> Loops;
96 SmallVector<Loop *, 2> WorkList(LI.begin(), LI.end());
97 while (!WorkList.empty()) {
98 Loop *L = WorkList.pop_back_val();
99 WorkList.insert(WorkList.end(), L->begin(), L->end());
100 Loops.push_back(L);
101 }
102
103 // Now pop each element off of the stack to visit the loops in reverse
104 // post-order.
105 for (auto *L : reverse(Loops)) {
106 PreservedAnalyses PassPA = Pass.run(*L, LAM);
107 assert(PassPA.preserved(getLoopPassPreservedAnalyses()) &&
108 "Loop passes must preserve all relevant analyses");
109
110 // We know that the loop pass couldn't have invalidated any other loop's
111 // analyses (that's the contract of a loop pass), so directly handle the
112 // loop analysis manager's invalidation here. Also, update the
113 // preserved analyses to reflect that once invalidated these can again
114 // be preserved.
115 PassPA = LAM.invalidate(*L, std::move(PassPA));
116
117 // Then intersect the preserved set so that invalidation of module
118 // analyses will eventually occur when the module pass completes.
119 PA.intersect(std::move(PassPA));
120 }
121
122 // By definition we preserve the proxy. This precludes *any* invalidation of
123 // loop analyses by the proxy, but that's OK because we've taken care to
124 // invalidate analyses in the loop analysis manager incrementally above.
125 PA.preserve<LoopAnalysisManagerFunctionProxy>();
126 return PA;
127 }
128
129 private:
130 LoopPassT Pass;
131 };
132
133 /// \brief A function to deduce a loop pass type and wrap it in the templated
134 /// adaptor.
135 template <typename LoopPassT>
136 FunctionToLoopPassAdaptor<LoopPassT>
createFunctionToLoopPassAdaptor(LoopPassT Pass)137 createFunctionToLoopPassAdaptor(LoopPassT Pass) {
138 return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass));
139 }
140 }
141
142 #endif // LLVM_ANALYSIS_LOOPPASSMANAGER_H
143