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
getAnalysisUsage(AnalysisUsage & AU) const45 void PolyhedralInfo::getAnalysisUsage(AnalysisUsage &AU) const {
46 AU.addRequiredTransitive<DependenceInfoWrapperPass>();
47 AU.addRequired<LoopInfoWrapperPass>();
48 AU.addRequiredTransitive<ScopInfoWrapperPass>();
49 AU.setPreservesAll();
50 }
51
runOnFunction(Function & F)52 bool PolyhedralInfo::runOnFunction(Function &F) {
53 DI = &getAnalysis<DependenceInfoWrapperPass>();
54 SI = getAnalysis<ScopInfoWrapperPass>().getSI();
55 return false;
56 }
57
print(raw_ostream & OS,const Module *) const58 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(TopLevelLoop)) {
62 OS.indent(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
checkParallel(Loop * L,isl_pw_aff ** MinDepDistPtr) const71 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(const_cast<Scop *>(S), 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(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, MinDepDistPtr);
95 isl_union_map_free(Schedule);
96 return IsParallel;
97 }
98
isParallel(Loop * L) const99 bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); }
100
getScopContainingLoop(Loop * L) const101 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]
getScheduleForLoop(const Scop * S,Loop * L) const124 __isl_give isl_union_map *PolyhedralInfo::getScheduleForLoop(const Scop *S,
125 Loop *L) const {
126 isl_union_map *Schedule = isl_union_map_empty(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(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(ScheduleMap, isl_dim_out, CurrDim + 1,
142 MaxDim - CurrDim - 1);
143 ScheduleMap = isl_map_set_tuple_id(ScheduleMap, isl_dim_in,
144 SS.getDomainId().release());
145 Schedule =
146 isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap));
147 }
148 }
149 Schedule = isl_union_map_coalesce(Schedule);
150 return Schedule;
151 }
152
153 char PolyhedralInfo::ID = 0;
154
createPolyhedralInfoPass()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
PolyhedralInfoPrinterLegacyPass()175 PolyhedralInfoPrinterLegacyPass() : PolyhedralInfoPrinterLegacyPass(outs()) {}
PolyhedralInfoPrinterLegacyPass(llvm::raw_ostream & OS)176 explicit PolyhedralInfoPrinterLegacyPass(llvm::raw_ostream &OS)
177 : FunctionPass(ID), OS(OS) {}
178
runOnFunction(Function & F)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
getAnalysisUsage(AnalysisUsage & AU) const189 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
createPolyhedralInfoPrinterLegacyPass(raw_ostream & OS)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