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

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

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