/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/Analysis/PolyhedralInfo.cpp
Line | Count | Source (jump to first uncovered line) |
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/Support/Debug.h" |
29 | | #include "isl/union_map.h" |
30 | | |
31 | | using namespace llvm; |
32 | | using namespace polly; |
33 | | |
34 | | #define DEBUG_TYPE "polyhedral-info" |
35 | | |
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)); |
40 | | |
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)); |
45 | | |
46 | 19 | void PolyhedralInfo::getAnalysisUsage(AnalysisUsage &AU) const { |
47 | 19 | AU.addRequiredTransitive<DependenceInfoWrapperPass>(); |
48 | 19 | AU.addRequired<LoopInfoWrapperPass>(); |
49 | 19 | AU.addRequiredTransitive<ScopInfoWrapperPass>(); |
50 | 19 | AU.setPreservesAll(); |
51 | 19 | } |
52 | | |
53 | 19 | bool PolyhedralInfo::runOnFunction(Function &F) { |
54 | 19 | DI = &getAnalysis<DependenceInfoWrapperPass>(); |
55 | 19 | SI = getAnalysis<ScopInfoWrapperPass>().getSI(); |
56 | 19 | return false; |
57 | 19 | } |
58 | | |
59 | 19 | void PolyhedralInfo::print(raw_ostream &OS, const Module *) const { |
60 | 19 | auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
61 | 22 | for (auto *TopLevelLoop : LI) { |
62 | 33 | for (auto *L : depth_first(TopLevelLoop)) { |
63 | 33 | OS.indent(2) << L->getHeader()->getName() << ":\t"; |
64 | 33 | if (CheckParallel && isParallel(L)) |
65 | 15 | OS << "Loop is parallel.\n"; |
66 | 18 | else if (CheckParallel) |
67 | 18 | OS << "Loop is not parallel.\n"; |
68 | 33 | } |
69 | 22 | } |
70 | 19 | } |
71 | | |
72 | 33 | bool PolyhedralInfo::checkParallel(Loop *L, isl_pw_aff **MinDepDistPtr) const { |
73 | 33 | bool IsParallel; |
74 | 33 | const Scop *S = getScopContainingLoop(L); |
75 | 33 | if (!S) |
76 | 0 | return false; |
77 | 33 | const Dependences &D = |
78 | 33 | DI->getDependences(const_cast<Scop *>(S), Dependences::AL_Access); |
79 | 33 | if (!D.hasValidDependences()) |
80 | 0 | return false; |
81 | 33 | LLVM_DEBUG(dbgs() << "Loop :\t" << L->getHeader()->getName() << ":\n"); |
82 | 33 | |
83 | 33 | isl_union_map *Deps = |
84 | 33 | D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_WAW | |
85 | 33 | Dependences::TYPE_WAR | Dependences::TYPE_RED) |
86 | 33 | .release(); |
87 | 33 | |
88 | 33 | LLVM_DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps) << "\n"); |
89 | 33 | |
90 | 33 | isl_union_map *Schedule = getScheduleForLoop(S, L); |
91 | 33 | LLVM_DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule) << "\n"); |
92 | 33 | |
93 | 33 | IsParallel = D.isParallel(Schedule, Deps, MinDepDistPtr); |
94 | 33 | isl_union_map_free(Schedule); |
95 | 33 | return IsParallel; |
96 | 33 | } |
97 | | |
98 | 33 | bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); } |
99 | | |
100 | 33 | const Scop *PolyhedralInfo::getScopContainingLoop(Loop *L) const { |
101 | 33 | assert((SI) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n"); |
102 | 33 | for (auto &It : *SI) { |
103 | 33 | Region *R = It.first; |
104 | 33 | if (R->contains(L)) |
105 | 33 | return It.second.get(); |
106 | 33 | } |
107 | 33 | return nullptr0 ; |
108 | 33 | } |
109 | | |
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++) |
115 | | // A[j] = 1; //Stmt |
116 | | // |
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, |
124 | 33 | Loop *L) const { |
125 | 33 | isl_union_map *Schedule = isl_union_map_empty(S->getParamSpace().release()); |
126 | 33 | int CurrDim = S->getRelativeLoopDepth(L); |
127 | 33 | LLVM_DEBUG(dbgs() << "Relative loop depth:\t" << CurrDim << "\n"); |
128 | 33 | assert(CurrDim >= 0 && "Loop in region should have at least depth one"); |
129 | 33 | |
130 | 39 | for (auto &SS : *S) { |
131 | 39 | if (L->contains(SS.getSurroundingLoop())) { |
132 | 33 | |
133 | 33 | unsigned int MaxDim = SS.getNumIterators(); |
134 | 33 | LLVM_DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n"); |
135 | 33 | isl_map *ScheduleMap = SS.getSchedule().release(); |
136 | 33 | assert( |
137 | 33 | ScheduleMap && |
138 | 33 | "Schedules that contain extension nodes require special handling."); |
139 | 33 | |
140 | 33 | ScheduleMap = isl_map_project_out(ScheduleMap, isl_dim_out, CurrDim + 1, |
141 | 33 | MaxDim - CurrDim - 1); |
142 | 33 | ScheduleMap = isl_map_set_tuple_id(ScheduleMap, isl_dim_in, |
143 | 33 | SS.getDomainId().release()); |
144 | 33 | Schedule = |
145 | 33 | isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap)); |
146 | 33 | } |
147 | 39 | } |
148 | 33 | Schedule = isl_union_map_coalesce(Schedule); |
149 | 33 | return Schedule; |
150 | 33 | } |
151 | | |
152 | | char PolyhedralInfo::ID = 0; |
153 | | |
154 | 0 | Pass *polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); } |
155 | | |
156 | 48.2k | INITIALIZE_PASS_BEGIN(PolyhedralInfo, "polyhedral-info", |
157 | 48.2k | "Polly - Interface to polyhedral analysis engine", false, |
158 | 48.2k | false); |
159 | 48.2k | INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass); |
160 | 48.2k | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); |
161 | 48.2k | INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass); |
162 | 48.2k | INITIALIZE_PASS_END(PolyhedralInfo, "polyhedral-info", |
163 | | "Polly - Interface to polyhedral analysis engine", false, |
164 | | false) |