polly/lib/Analysis/PolyhedralInfo.cpp

   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
  32 using namespace llvm;
  33 using namespace polly;
  34
  35 #include "polly/Support/PollyDebug.h"
  36 #define DEBUG_TYPE "polyhedral-info"
  37
  38 static cl::opt<bool> CheckParallel("polly-check-parallel",
  39                                    cl::desc("Check for parallel loops"),
  40                                    cl::Hidden, cl::cat(PollyCategory));
  41
  42 static cl::opt<bool> CheckVectorizable("polly-check-vectorizable",
  43                                        cl::desc("Check for vectorizable loops"),
  44                                        cl::Hidden, cl::cat(PollyCategory));
  45
  46 void PolyhedralInfo::getAnalysisUsage(AnalysisUsage &AU) const {
  47   AU.addRequiredTransitive<DependenceInfoWrapperPass>();
  48   AU.addRequired<LoopInfoWrapperPass>();
  49   AU.addRequiredTransitive<ScopInfoWrapperPass>();
  50   AU.setPreservesAll();
  51 }
  52
  53 bool PolyhedralInfo::runOnFunction(Function &F) {
  54   DI = &getAnalysis<DependenceInfoWrapperPass>();
  55   SI = getAnalysis<ScopInfoWrapperPass>().getSI();
  56   return false;
  57 }
  58
  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";
  68     }
  69   }
  70 }
  71
  72 bool 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(const_cast<Scop *>(S), 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(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, MinDepDistPtr);
  96   isl_union_map_free(Schedule);
  97   return IsParallel;
  98 }
  99
 100 bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); }
 101
 102 const 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(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(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(ScheduleMap, isl_dim_out, CurrDim + 1,
 143                                         MaxDim - CurrDim - 1);
 144       ScheduleMap = isl_map_set_tuple_id(ScheduleMap, isl_dim_in,
 145                                          SS.getDomainId().release());
 146       Schedule =
 147           isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap));
 148     }
 149   }
 150   Schedule = isl_union_map_coalesce(Schedule);
 151   return Schedule;
 152 }
 153
 154 char PolyhedralInfo::ID = 0;
 155
 156 Pass *polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); }
 157
 158 INITIALIZE_PASS_BEGIN(PolyhedralInfo, "polyhedral-info",
 159                       "Polly - Interface to polyhedral analysis engine", false,
 160                       false);
 161 INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass);
 162 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 163 INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
 164 INITIALIZE_PASS_END(PolyhedralInfo, "polyhedral-info",
 165                     "Polly - Interface to polyhedral analysis engine", false,
 166                     false)
 167
 168 //===----------------------------------------------------------------------===//
 169
 170 namespace {
 171 /// Print result from PolyhedralInfo.
 172 class PolyhedralInfoPrinterLegacyPass final : public FunctionPass {
 173 public:
 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
 196 private:
 197   llvm::raw_ostream &OS;
 198 };
 199
 200 char PolyhedralInfoPrinterLegacyPass::ID = 0;
 201 } // namespace
 202
 203 Pass *polly::createPolyhedralInfoPrinterLegacyPass(raw_ostream &OS) {
 204   return new PolyhedralInfoPrinterLegacyPass(OS);
 205 }
 206
 207 INITIALIZE_PASS_BEGIN(
 208     PolyhedralInfoPrinterLegacyPass, "print-polyhedral-info",
 209     "Polly - Print interface to polyhedral analysis engine analysis", false,
 210     false);
 211 INITIALIZE_PASS_DEPENDENCY(PolyhedralInfo);
 212 INITIALIZE_PASS_END(
 213     PolyhedralInfoPrinterLegacyPass, "print-polyhedral-info",
 214     "Polly - Print interface to polyhedral analysis engine analysis", false,
 215     false)