lib/Analysis/PolyhedralInfo.cpp

   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>().getSI();
  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 &SS : *S) {
 130     if (L->contains(SS.getSurroundingLoop())) {
 131
 132       unsigned int MaxDim = SS.getNumIterators();
 133       DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n");
 134       auto *ScheduleMap = SS.getSchedule();
 135       assert(
 136           ScheduleMap &&
 137           "Schedules that contain extension nodes require special handling.");
 138
 139       ScheduleMap = isl_map_project_out(ScheduleMap, isl_dim_out, CurrDim + 1,
 140                                         MaxDim - CurrDim - 1);
 141       ScheduleMap =
 142           isl_map_set_tuple_id(ScheduleMap, isl_dim_in, SS.getDomainId());
 143       Schedule =
 144           isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap));
 145     }
 146   }
 147   Schedule = isl_union_map_coalesce(Schedule);
 148   return Schedule;
 149 }
 150
 151 char PolyhedralInfo::ID = 0;
 152
 153 Pass *polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); }
 154
 155 INITIALIZE_PASS_BEGIN(PolyhedralInfo, "polyhedral-info",
 156                       "Polly - Interface to polyhedral analysis engine", false,
 157                       false);
 158 INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass);
 159 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
 160 INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass);
 161 INITIALIZE_PASS_END(PolyhedralInfo, "polyhedral-info",
 162                     "Polly - Interface to polyhedral analysis engine", false,
 163                     false)