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

source code of polly/lib/Analysis/PolyhedralInfo.cpp