1 | //===--------- PolyhedralInfo.cpp - Create Scops from LLVM IR-------------===// |
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 | // An interface to the Polyhedral analysis engine(Polly) of LLVM. |
10 | // |
11 | // This pass provides an interface to the polyhedral analysis performed by |
12 | // Polly. |
13 | // |
14 | // This interface provides basic interface like isParallel, isVectorizable |
15 | // that can be used in LLVM transformation passes. |
16 | // |
17 | // Work in progress, this file is subject to change. |
18 | // |
19 | //===----------------------------------------------------------------------===// |
20 | |
21 | #include "polly/PolyhedralInfo.h" |
22 | #include "polly/DependenceInfo.h" |
23 | #include "polly/LinkAllPasses.h" |
24 | #include "polly/Options.h" |
25 | #include "polly/ScopInfo.h" |
26 | #include "polly/Support/GICHelper.h" |
27 | #include "llvm/Analysis/LoopInfo.h" |
28 | #include "llvm/InitializePasses.h" |
29 | #include "llvm/Support/Debug.h" |
30 | #include "isl/union_map.h" |
31 | |
32 | using namespace llvm; |
33 | using namespace polly; |
34 | |
35 | #define DEBUG_TYPE "polyhedral-info" |
36 | |
37 | static cl::opt<bool> CheckParallel("polly-check-parallel" , |
38 | cl::desc("Check for parallel loops" ), |
39 | cl::Hidden, cl::cat(PollyCategory)); |
40 | |
41 | static cl::opt<bool> CheckVectorizable("polly-check-vectorizable" , |
42 | cl::desc("Check for vectorizable loops" ), |
43 | cl::Hidden, cl::cat(PollyCategory)); |
44 | |
45 | void PolyhedralInfo::getAnalysisUsage(AnalysisUsage &AU) const { |
46 | AU.addRequiredTransitive<DependenceInfoWrapperPass>(); |
47 | AU.addRequired<LoopInfoWrapperPass>(); |
48 | AU.addRequiredTransitive<ScopInfoWrapperPass>(); |
49 | AU.setPreservesAll(); |
50 | } |
51 | |
52 | bool PolyhedralInfo::runOnFunction(Function &F) { |
53 | DI = &getAnalysis<DependenceInfoWrapperPass>(); |
54 | SI = getAnalysis<ScopInfoWrapperPass>().getSI(); |
55 | return false; |
56 | } |
57 | |
58 | void PolyhedralInfo::print(raw_ostream &OS, const Module *) const { |
59 | auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
60 | for (auto *TopLevelLoop : LI) { |
61 | for (auto *L : depth_first(G: TopLevelLoop)) { |
62 | OS.indent(NumSpaces: 2) << L->getHeader()->getName() << ":\t" ; |
63 | if (CheckParallel && isParallel(L)) |
64 | OS << "Loop is parallel.\n" ; |
65 | else if (CheckParallel) |
66 | OS << "Loop is not parallel.\n" ; |
67 | } |
68 | } |
69 | } |
70 | |
71 | bool PolyhedralInfo::checkParallel(Loop *L, isl_pw_aff **MinDepDistPtr) const { |
72 | bool IsParallel; |
73 | const Scop *S = getScopContainingLoop(L); |
74 | if (!S) |
75 | return false; |
76 | const Dependences &D = |
77 | DI->getDependences(S: const_cast<Scop *>(S), Level: Dependences::AL_Access); |
78 | if (!D.hasValidDependences()) |
79 | return false; |
80 | LLVM_DEBUG(dbgs() << "Loop :\t" << L->getHeader()->getName() << ":\n" ); |
81 | |
82 | isl_union_map *Deps = |
83 | D.getDependences(Kinds: Dependences::TYPE_RAW | Dependences::TYPE_WAW | |
84 | Dependences::TYPE_WAR | Dependences::TYPE_RED) |
85 | .release(); |
86 | |
87 | LLVM_DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps, "null" ) |
88 | << "\n" ); |
89 | |
90 | isl_union_map *Schedule = getScheduleForLoop(S, L); |
91 | LLVM_DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule, "null" ) |
92 | << "\n" ); |
93 | |
94 | IsParallel = D.isParallel(Schedule, Deps, MinDistancePtr: MinDepDistPtr); |
95 | isl_union_map_free(umap: Schedule); |
96 | return IsParallel; |
97 | } |
98 | |
99 | bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); } |
100 | |
101 | const Scop *PolyhedralInfo::getScopContainingLoop(Loop *L) const { |
102 | assert((SI) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n" ); |
103 | for (auto &It : *SI) { |
104 | Region *R = It.first; |
105 | if (R->contains(L)) |
106 | return It.second.get(); |
107 | } |
108 | return nullptr; |
109 | } |
110 | |
111 | // Given a Loop and the containing SCoP, we compute the partial schedule |
112 | // by taking union of individual schedules of each ScopStmt within the loop |
113 | // and projecting out the inner dimensions from the range of the schedule. |
114 | // for (i = 0; i < n; i++) |
115 | // for (j = 0; j < n; j++) |
116 | // A[j] = 1; //Stmt |
117 | // |
118 | // The original schedule will be |
119 | // Stmt[i0, i1] -> [i0, i1] |
120 | // The schedule for the outer loop will be |
121 | // Stmt[i0, i1] -> [i0] |
122 | // The schedule for the inner loop will be |
123 | // Stmt[i0, i1] -> [i0, i1] |
124 | __isl_give isl_union_map *PolyhedralInfo::getScheduleForLoop(const Scop *S, |
125 | Loop *L) const { |
126 | isl_union_map *Schedule = isl_union_map_empty(space: S->getParamSpace().release()); |
127 | int CurrDim = S->getRelativeLoopDepth(L); |
128 | LLVM_DEBUG(dbgs() << "Relative loop depth:\t" << CurrDim << "\n" ); |
129 | assert(CurrDim >= 0 && "Loop in region should have at least depth one" ); |
130 | |
131 | for (auto &SS : *S) { |
132 | if (L->contains(L: SS.getSurroundingLoop())) { |
133 | |
134 | unsigned int MaxDim = SS.getNumIterators(); |
135 | LLVM_DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n" ); |
136 | isl_map *ScheduleMap = SS.getSchedule().release(); |
137 | assert( |
138 | ScheduleMap && |
139 | "Schedules that contain extension nodes require special handling." ); |
140 | |
141 | ScheduleMap = isl_map_project_out(map: ScheduleMap, type: isl_dim_out, first: CurrDim + 1, |
142 | n: MaxDim - CurrDim - 1); |
143 | ScheduleMap = isl_map_set_tuple_id(map: ScheduleMap, type: isl_dim_in, |
144 | id: SS.getDomainId().release()); |
145 | Schedule = |
146 | isl_union_map_union(umap1: Schedule, umap2: isl_union_map_from_map(map: ScheduleMap)); |
147 | } |
148 | } |
149 | Schedule = isl_union_map_coalesce(umap: Schedule); |
150 | return Schedule; |
151 | } |
152 | |
153 | char PolyhedralInfo::ID = 0; |
154 | |
155 | Pass *polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); } |
156 | |
157 | INITIALIZE_PASS_BEGIN(PolyhedralInfo, "polyhedral-info" , |
158 | "Polly - Interface to polyhedral analysis engine" , false, |
159 | false); |
160 | INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass); |
161 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); |
162 | INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass); |
163 | INITIALIZE_PASS_END(PolyhedralInfo, "polyhedral-info" , |
164 | "Polly - Interface to polyhedral analysis engine" , false, |
165 | false) |
166 | |
167 | //===----------------------------------------------------------------------===// |
168 | |
169 | namespace { |
170 | /// Print result from PolyhedralInfo. |
171 | class PolyhedralInfoPrinterLegacyPass final : public FunctionPass { |
172 | public: |
173 | static char ID; |
174 | |
175 | PolyhedralInfoPrinterLegacyPass() : PolyhedralInfoPrinterLegacyPass(outs()) {} |
176 | explicit PolyhedralInfoPrinterLegacyPass(llvm::raw_ostream &OS) |
177 | : FunctionPass(ID), OS(OS) {} |
178 | |
179 | bool runOnFunction(Function &F) override { |
180 | PolyhedralInfo &P = getAnalysis<PolyhedralInfo>(); |
181 | |
182 | OS << "Printing analysis '" << P.getPassName() << "' for function '" |
183 | << F.getName() << "':\n" ; |
184 | P.print(OS); |
185 | |
186 | return false; |
187 | } |
188 | |
189 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
190 | FunctionPass::getAnalysisUsage(AU); |
191 | AU.addRequired<PolyhedralInfo>(); |
192 | AU.setPreservesAll(); |
193 | } |
194 | |
195 | private: |
196 | llvm::raw_ostream &OS; |
197 | }; |
198 | |
199 | char PolyhedralInfoPrinterLegacyPass::ID = 0; |
200 | } // namespace |
201 | |
202 | Pass *polly::createPolyhedralInfoPrinterLegacyPass(raw_ostream &OS) { |
203 | return new PolyhedralInfoPrinterLegacyPass(OS); |
204 | } |
205 | |
206 | INITIALIZE_PASS_BEGIN( |
207 | PolyhedralInfoPrinterLegacyPass, "print-polyhedral-info" , |
208 | "Polly - Print interface to polyhedral analysis engine analysis" , false, |
209 | false); |
210 | INITIALIZE_PASS_DEPENDENCY(PolyhedralInfo); |
211 | INITIALIZE_PASS_END( |
212 | PolyhedralInfoPrinterLegacyPass, "print-polyhedral-info" , |
213 | "Polly - Print interface to polyhedral analysis engine analysis" , false, |
214 | false) |
215 | |