include/polly/DependenceInfo.h

   1 //===--- polly/DependenceInfo.h - Polyhedral dependency analysis *- C++ -*-===//
   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 // Calculate the data dependency relations for a Scop using ISL.
  11 //
  12 // The integer set library (ISL) from Sven has an integrated dependency analysis
  13 // to calculate data dependences. This pass takes advantage of this and
  14 // calculates those dependences of a Scop.
  15 //
  16 // The dependences in this pass are exact in terms that for a specific read
  17 // statement instance only the last write statement instance is returned. In
  18 // case of may-writes, a set of possible write instances is returned. This
  19 // analysis will never produce redundant dependences.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #ifndef POLLY_DEPENDENCE_INFO_H
  24 #define POLLY_DEPENDENCE_INFO_H
  25
  26 #include "polly/ScopPass.h"
  27 #include "isl/ctx.h"
  28
  29 struct isl_pw_aff;
  30 struct isl_union_map;
  31 struct isl_union_set;
  32 struct isl_map;
  33 struct isl_set;
  34 struct clast_for;
  35
  36 using namespace llvm;
  37
  38 namespace polly {
  39
  40 class Scop;
  41 class ScopStmt;
  42 class MemoryAccess;
  43
  44 /// The accumulated dependence information for a SCoP.
  45 ///
  46 /// The Dependences struct holds all dependence information we collect and
  47 /// compute for one SCoP. It also offers an interface that allows users to
  48 /// query only specific parts.
  49 struct Dependences {
  50   // Granularities of the current dependence analysis
  51   enum AnalysisLevel {
  52     AL_Statement = 0,
  53     // Distinguish accessed memory references in the same statement
  54     AL_Reference,
  55     // Distinguish memory access instances in the same statement
  56     AL_Access,
  57
  58     NumAnalysisLevels
  59   };
  60
  61   /// Map type for reduction dependences.
  62   using ReductionDependencesMapTy = DenseMap<MemoryAccess *, isl_map *>;
  63
  64   /// Map type to associate statements with schedules.
  65   using StatementToIslMapTy = DenseMap<ScopStmt *, isl_map *>;
  66
  67   /// The type of the dependences.
  68   ///
  69   /// Reduction dependences are separated from RAW/WAW/WAR dependences because
  70   /// we can ignore them during the scheduling. That's because the order
  71   /// in which the reduction statements are executed does not matter. However,
  72   /// if they are executed in parallel we need to take additional measures
  73   /// (e.g, privatization) to ensure a correct result. The (reverse) transitive
  74   /// closure of the reduction dependences are used to check for parallel
  75   /// executed reduction statements during code generation. These dependences
  76   /// connect all instances of a reduction with each other, they are therefore
  77   /// cyclic and possibly "reversed".
  78   enum Type {
  79     // Write after read
  80     TYPE_WAR = 1 << 0,
  81
  82     // Read after write
  83     TYPE_RAW = 1 << 1,
  84
  85     // Write after write
  86     TYPE_WAW = 1 << 2,
  87
  88     // Reduction dependences
  89     TYPE_RED = 1 << 3,
  90
  91     // Transitive closure of the reduction dependences (& the reverse)
  92     TYPE_TC_RED = 1 << 4,
  93   };
  94
  95   /// Get the dependences of type @p Kinds.
  96   ///
  97   /// @param Kinds This integer defines the different kinds of dependences
  98   ///              that will be returned. To return more than one kind, the
  99   ///              different kinds are 'ored' together.
 100   __isl_give isl_union_map *getDependences(int Kinds) const;
 101
 102   /// Report if valid dependences are available.
 103   bool hasValidDependences() const;
 104
 105   /// Return the reduction dependences caused by @p MA.
 106   ///
 107   /// @return The reduction dependences caused by @p MA or nullptr if none.
 108   __isl_give isl_map *getReductionDependences(MemoryAccess *MA) const;
 109
 110   /// Return all reduction dependences.
 111   const ReductionDependencesMapTy &getReductionDependences() const {
 112     return ReductionDependences;
 113   }
 114
 115   /// Check if a partial schedule is parallel wrt to @p Deps.
 116   ///
 117   /// @param Schedule       The subset of the schedule space that we want to
 118   ///                       check.
 119   /// @param Deps           The dependences @p Schedule needs to respect.
 120   /// @param MinDistancePtr If not nullptr, the minimal dependence distance will
 121   ///                       be returned at the address of that pointer
 122   ///
 123   /// @return Returns true, if executing parallel the outermost dimension of
 124   ///         @p Schedule is valid according to the dependences @p Deps.
 125   bool isParallel(__isl_keep isl_union_map *Schedule,
 126                   __isl_take isl_union_map *Deps,
 127                   __isl_give isl_pw_aff **MinDistancePtr = nullptr) const;
 128
 129   /// Check if a new schedule is valid.
 130   ///
 131   /// @param S             The current SCoP.
 132   /// @param NewSchedules  The new schedules
 133   ///
 134   /// @return True if the new schedule is valid, false if it reverses
 135   ///         dependences.
 136   bool isValidSchedule(Scop &S, StatementToIslMapTy *NewSchedules) const;
 137
 138   /// Print the stored dependence information.
 139   void print(llvm::raw_ostream &OS) const;
 140
 141   /// Dump the dependence information stored to the dbgs stream.
 142   void dump() const;
 143
 144   /// Return the granularity of this dependence analysis.
 145   AnalysisLevel getDependenceLevel() { return Level; }
 146
 147   /// Allow the DependenceInfo access to private members and methods.
 148   ///
 149   /// To restrict access to the internal state, only the DependenceInfo class
 150   /// is able to call or modify a Dependences struct.
 151   friend struct DependenceAnalysis;
 152   friend struct DependenceInfoPrinterPass;
 153   friend class DependenceInfo;
 154   friend class DependenceInfoWrapperPass;
 155
 156   /// Destructor that will free internal objects.
 157   ~Dependences() { releaseMemory(); }
 158
 159 private:
 160   /// Create an empty dependences struct.
 161   explicit Dependences(const std::shared_ptr<isl_ctx> &IslCtx,
 162                        AnalysisLevel Level)
 163       : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr), TC_RED(nullptr),
 164         IslCtx(IslCtx), Level(Level) {}
 165
 166   /// Calculate and add at the privatization dependences.
 167   void addPrivatizationDependences();
 168
 169   /// Calculate the dependences for a certain SCoP @p S.
 170   void calculateDependences(Scop &S);
 171
 172   /// Set the reduction dependences for @p MA to @p Deps.
 173   void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
 174
 175   /// Free the objects associated with this Dependences struct.
 176   ///
 177   /// The Dependences struct will again be "empty" afterwards.
 178   void releaseMemory();
 179
 180   /// The different basic kinds of dependences we calculate.
 181   isl_union_map *RAW;
 182   isl_union_map *WAR;
 183   isl_union_map *WAW;
 184
 185   /// The special reduction dependences.
 186   isl_union_map *RED;
 187
 188   /// The (reverse) transitive closure of reduction dependences.
 189   isl_union_map *TC_RED;
 190
 191   /// Mapping from memory accesses to their reduction dependences.
 192   ReductionDependencesMapTy ReductionDependences;
 193
 194   /// Isl context from the SCoP.
 195   std::shared_ptr<isl_ctx> IslCtx;
 196
 197   /// Granularity of this dependence analysis.
 198   const AnalysisLevel Level;
 199 };
 200
 201 struct DependenceAnalysis : public AnalysisInfoMixin<DependenceAnalysis> {
 202   static AnalysisKey Key;
 203   struct Result {
 204     Scop &S;
 205     std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
 206
 207     /// Return the dependence information for the current SCoP.
 208     ///
 209     /// @param Level The granularity of dependence analysis result.
 210     ///
 211     /// @return The dependence analysis result
 212     ///
 213     const Dependences &getDependences(Dependences::AnalysisLevel Level);
 214
 215     /// Recompute dependences from schedule and memory accesses.
 216     const Dependences &recomputeDependences(Dependences::AnalysisLevel Level);
 217   };
 218   Result run(Scop &S, ScopAnalysisManager &SAM,
 219              ScopStandardAnalysisResults &SAR);
 220 };
 221
 222 struct DependenceInfoPrinterPass
 223     : public PassInfoMixin<DependenceInfoPrinterPass> {
 224   DependenceInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
 225
 226   PreservedAnalyses run(Scop &S, ScopAnalysisManager &,
 227                         ScopStandardAnalysisResults &, SPMUpdater &);
 228
 229   raw_ostream &OS;
 230 };
 231
 232 class DependenceInfo : public ScopPass {
 233 public:
 234   static char ID;
 235
 236   /// Construct a new DependenceInfo pass.
 237   DependenceInfo() : ScopPass(ID) {}
 238
 239   /// Return the dependence information for the current SCoP.
 240   ///
 241   /// @param Level The granularity of dependence analysis result.
 242   ///
 243   /// @return The dependence analysis result
 244   ///
 245   const Dependences &getDependences(Dependences::AnalysisLevel Level);
 246
 247   /// Recompute dependences from schedule and memory accesses.
 248   const Dependences &recomputeDependences(Dependences::AnalysisLevel Level);
 249
 250   /// Compute the dependence information for the SCoP @p S.
 251   bool runOnScop(Scop &S) override;
 252
 253   /// Print the dependences for the given SCoP to @p OS.
 254   void printScop(raw_ostream &OS, Scop &) const override;
 255
 256   /// Release the internal memory.
 257   void releaseMemory() override {
 258     for (auto &d : D)
 259       d.reset();
 260   }
 261
 262   /// Register all analyses and transformation required.
 263   void getAnalysisUsage(AnalysisUsage &AU) const override;
 264
 265 private:
 266   Scop *S;
 267
 268   /// Dependences struct for the current SCoP.
 269   std::unique_ptr<Dependences> D[Dependences::NumAnalysisLevels];
 270 };
 271
 272 /// Construct a new DependenceInfoWrapper pass.
 273 class DependenceInfoWrapperPass : public FunctionPass {
 274 public:
 275   static char ID;
 276
 277   /// Construct a new DependenceInfoWrapper pass.
 278   DependenceInfoWrapperPass() : FunctionPass(ID) {}
 279
 280   /// Return the dependence information for the given SCoP.
 281   ///
 282   /// @param S     SCoP object.
 283   /// @param Level The granularity of dependence analysis result.
 284   ///
 285   /// @return The dependence analysis result
 286   ///
 287   const Dependences &getDependences(Scop *S, Dependences::AnalysisLevel Level);
 288
 289   /// Recompute dependences from schedule and memory accesses.
 290   const Dependences &recomputeDependences(Scop *S,
 291                                           Dependences::AnalysisLevel Level);
 292
 293   /// Compute the dependence information on-the-fly for the function.
 294   bool runOnFunction(Function &F) override;
 295
 296   /// Print the dependences for the current function to @p OS.
 297   void print(raw_ostream &OS, const Module *M = nullptr) const override;
 298
 299   /// Release the internal memory.
 300   void releaseMemory() override { ScopToDepsMap.clear(); }
 301
 302   /// Register all analyses and transformation required.
 303   void getAnalysisUsage(AnalysisUsage &AU) const override;
 304
 305 private:
 306   using ScopToDepsMapTy = DenseMap<Scop *, std::unique_ptr<Dependences>>;
 307
 308   /// Scop to Dependence map for the current function.
 309   ScopToDepsMapTy ScopToDepsMap;
 310 };
 311
 312 } // namespace polly
 313
 314 namespace llvm {
 315 class PassRegistry;
 316 void initializeDependenceInfoPass(llvm::PassRegistry &);
 317 void initializeDependenceInfoWrapperPassPass(llvm::PassRegistry &);
 318 } // namespace llvm
 319
 320 #endif