1 //===--------- PolyhedralInfo.cpp - Create Scops from LLVM IR-------------===//
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
7 //===----------------------------------------------------------------------===//
9 // An interface to the Polyhedral analysis engine(Polly) of LLVM.
11 // This pass provides an interface to the polyhedral analysis performed by
14 // This interface provides basic interface like isParallel, isVectorizable
15 // that can be used in LLVM transformation passes.
17 // Work in progress, this file is subject to change.
19 //===----------------------------------------------------------------------===//
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/Support/Debug.h"
29 #include "isl/union_map.h"
32 using namespace polly
;
34 #define DEBUG_TYPE "polyhedral-info"
36 static cl::opt
<bool> CheckParallel("polly-check-parallel",
37 cl::desc("Check for parallel loops"),
38 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
39 cl::cat(PollyCategory
));
41 static cl::opt
<bool> CheckVectorizable("polly-check-vectorizable",
42 cl::desc("Check for vectorizable loops"),
43 cl::Hidden
, cl::init(false),
44 cl::ZeroOrMore
, cl::cat(PollyCategory
));
46 void PolyhedralInfo::getAnalysisUsage(AnalysisUsage
&AU
) const {
47 AU
.addRequiredTransitive
<DependenceInfoWrapperPass
>();
48 AU
.addRequired
<LoopInfoWrapperPass
>();
49 AU
.addRequiredTransitive
<ScopInfoWrapperPass
>();
53 bool PolyhedralInfo::runOnFunction(Function
&F
) {
54 DI
= &getAnalysis
<DependenceInfoWrapperPass
>();
55 SI
= getAnalysis
<ScopInfoWrapperPass
>().getSI();
59 void 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(TopLevelLoop
)) {
63 OS
.indent(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";
72 bool PolyhedralInfo::checkParallel(Loop
*L
, isl_pw_aff
**MinDepDistPtr
) const {
74 const Scop
*S
= getScopContainingLoop(L
);
77 const Dependences
&D
=
78 DI
->getDependences(const_cast<Scop
*>(S
), Dependences::AL_Access
);
79 if (!D
.hasValidDependences())
81 LLVM_DEBUG(dbgs() << "Loop :\t" << L
->getHeader()->getName() << ":\n");
84 D
.getDependences(Dependences::TYPE_RAW
| Dependences::TYPE_WAW
|
85 Dependences::TYPE_WAR
| Dependences::TYPE_RED
)
88 LLVM_DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps
) << "\n");
90 isl_union_map
*Schedule
= getScheduleForLoop(S
, L
);
91 LLVM_DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule
) << "\n");
93 IsParallel
= D
.isParallel(Schedule
, Deps
, MinDepDistPtr
);
94 isl_union_map_free(Schedule
);
98 bool PolyhedralInfo::isParallel(Loop
*L
) const { return checkParallel(L
); }
100 const Scop
*PolyhedralInfo::getScopContainingLoop(Loop
*L
) const {
101 assert((SI
) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n");
102 for (auto &It
: *SI
) {
103 Region
*R
= It
.first
;
105 return It
.second
.get();
110 // Given a Loop and the containing SCoP, we compute the partial schedule
111 // by taking union of individual schedules of each ScopStmt within the loop
112 // and projecting out the inner dimensions from the range of the schedule.
113 // for (i = 0; i < n; i++)
114 // for (j = 0; j < n; j++)
117 // The original schedule will be
118 // Stmt[i0, i1] -> [i0, i1]
119 // The schedule for the outer loop will be
120 // Stmt[i0, i1] -> [i0]
121 // The schedule for the inner loop will be
122 // Stmt[i0, i1] -> [i0, i1]
123 __isl_give isl_union_map
*PolyhedralInfo::getScheduleForLoop(const Scop
*S
,
125 isl_union_map
*Schedule
= isl_union_map_empty(S
->getParamSpace().release());
126 int CurrDim
= S
->getRelativeLoopDepth(L
);
127 LLVM_DEBUG(dbgs() << "Relative loop depth:\t" << CurrDim
<< "\n");
128 assert(CurrDim
>= 0 && "Loop in region should have at least depth one");
130 for (auto &SS
: *S
) {
131 if (L
->contains(SS
.getSurroundingLoop())) {
133 unsigned int MaxDim
= SS
.getNumIterators();
134 LLVM_DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim
<< "\n");
135 isl_map
*ScheduleMap
= SS
.getSchedule().release();
138 "Schedules that contain extension nodes require special handling.");
140 ScheduleMap
= isl_map_project_out(ScheduleMap
, isl_dim_out
, CurrDim
+ 1,
141 MaxDim
- CurrDim
- 1);
142 ScheduleMap
= isl_map_set_tuple_id(ScheduleMap
, isl_dim_in
,
143 SS
.getDomainId().release());
145 isl_union_map_union(Schedule
, isl_union_map_from_map(ScheduleMap
));
148 Schedule
= isl_union_map_coalesce(Schedule
);
152 char PolyhedralInfo::ID
= 0;
154 Pass
*polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); }
156 INITIALIZE_PASS_BEGIN(PolyhedralInfo
, "polyhedral-info",
157 "Polly - Interface to polyhedral analysis engine", false,
159 INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass
);
160 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass
);
161 INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass
);
162 INITIALIZE_PASS_END(PolyhedralInfo
, "polyhedral-info",
163 "Polly - Interface to polyhedral analysis engine", false,