1 //===--------- PolyhedralInfo.cpp  - Create Scops from LLVM IR-------------===//
2 ///
3 ///                     The LLVM Compiler Infrastructure
4 ///
5 /// This file is distributed under the University of Illinois Open Source
6 /// License. See LICENSE.TXT for details.
7 ///
8 //===----------------------------------------------------------------------===//
9 ///
10 /// An interface to the Polyhedral analysis engine(Polly) of LLVM.
11 ///
12 /// This pass provides an interface to the polyhedral analysis performed by
13 /// Polly.
14 ///
15 /// This interface provides basic interface like isParallel, isVectorizable
16 /// that can be used in LLVM transformation passes.
17 ///
18 /// Work in progress, this file is subject to change.
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/map.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::init(false), cl::ZeroOrMore,
40                                    cl::cat(PollyCategory));
41 
42 static cl::opt<bool> CheckVectorizable("polly-check-vectorizable",
43                                        cl::desc("Check for vectorizable loops"),
44                                        cl::Hidden, cl::init(false),
45                                        cl::ZeroOrMore, cl::cat(PollyCategory));
46 
47 void PolyhedralInfo::getAnalysisUsage(AnalysisUsage &AU) const {
48   AU.addRequiredTransitive<DependenceInfoWrapperPass>();
49   AU.addRequired<LoopInfoWrapperPass>();
50   AU.addRequiredTransitive<ScopInfoWrapperPass>();
51   AU.setPreservesAll();
52 }
53 
54 bool PolyhedralInfo::runOnFunction(Function &F) {
55   DI = &getAnalysis<DependenceInfoWrapperPass>();
56   SI = &getAnalysis<ScopInfoWrapperPass>();
57   return false;
58 }
59 
60 void PolyhedralInfo::print(raw_ostream &OS, const Module *) const {
61   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
62   for (auto *TopLevelLoop : LI) {
63     for (auto *L : depth_first(TopLevelLoop)) {
64       OS.indent(2) << L->getHeader()->getName() << ":\t";
65       if (CheckParallel && isParallel(L))
66         OS << "Loop is parallel.\n";
67       else if (CheckParallel)
68         OS << "Loop is not parallel.\n";
69     }
70   }
71 }
72 
73 bool PolyhedralInfo::checkParallel(Loop *L, isl_pw_aff **MinDepDistPtr) const {
74   bool IsParallel;
75   const Scop *S = getScopContainingLoop(L);
76   if (!S)
77     return false;
78   const Dependences &D =
79       DI->getDependences(const_cast<Scop *>(S), Dependences::AL_Access);
80   if (!D.hasValidDependences())
81     return false;
82   DEBUG(dbgs() << "Loop :\t" << L->getHeader()->getName() << ":\n");
83 
84   isl_union_map *Deps =
85       D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_WAW |
86                        Dependences::TYPE_WAR | Dependences::TYPE_RED);
87   DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps) << "\n");
88 
89   isl_union_map *Schedule = getScheduleForLoop(S, L);
90   DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule) << "\n");
91 
92   IsParallel = D.isParallel(Schedule, Deps, MinDepDistPtr);
93   isl_union_map_free(Schedule);
94   return IsParallel;
95 }
96 
97 bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); }
98 
99 const Scop *PolyhedralInfo::getScopContainingLoop(Loop *L) const {
100   assert((SI) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n");
101   for (auto &It : *SI) {
102     Region *R = It.first;
103     if (R->contains(L))
104       return It.second.get();
105   }
106   return nullptr;
107 }
108 
109 //  Given a Loop and the containing SCoP, we compute the partial schedule
110 //  by taking union of individual schedules of each ScopStmt within the loop
111 //  and projecting out the inner dimensions from the range of the schedule.
112 //   for (i = 0; i < n; i++)
113 //      for (j = 0; j < n; j++)
114 //        A[j] = 1;  //Stmt
115 //
116 //  The original schedule will be
117 //    Stmt[i0, i1] -> [i0, i1]
118 //  The schedule for the outer loop will be
119 //    Stmt[i0, i1] -> [i0]
120 //  The schedule for the inner loop will be
121 //    Stmt[i0, i1] -> [i0, i1]
122 __isl_give isl_union_map *PolyhedralInfo::getScheduleForLoop(const Scop *S,
123                                                              Loop *L) const {
124   isl_union_map *Schedule = isl_union_map_empty(S->getParamSpace());
125   int CurrDim = S->getRelativeLoopDepth(L);
126   DEBUG(dbgs() << "Relative loop depth:\t" << CurrDim << "\n");
127   assert(CurrDim >= 0 && "Loop in region should have at least depth one");
128 
129   for (auto *BB : L->blocks()) {
130     auto *SS = S->getStmtFor(BB);
131     if (!SS)
132       continue;
133 
134     unsigned int MaxDim = SS->getNumIterators();
135     DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n");
136     auto *ScheduleMap = SS->getSchedule();
137     assert(ScheduleMap &&
138            "Schedules that contain extension nodes require special handling.");
139 
140     ScheduleMap = isl_map_project_out(ScheduleMap, isl_dim_out, CurrDim + 1,
141                                       MaxDim - CurrDim - 1);
142     ScheduleMap =
143         isl_map_set_tuple_id(ScheduleMap, isl_dim_in, SS->getDomainId());
144     Schedule =
145         isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap));
146   }
147 
148   Schedule = isl_union_map_coalesce(Schedule);
149   return Schedule;
150 }
151 
152 char PolyhedralInfo::ID = 0;
153 
154 Pass *polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); }
155 
156 INITIALIZE_PASS_BEGIN(PolyhedralInfo, "polyhedral-info",
157                       "Polly - Interface to polyhedral analysis engine", false,
158                       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,
164                     false)
165