include/polly/ZoneAlgo.h

   1 //===------ ZoneAlgo.h ------------------------------------------*- 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 // Derive information about array elements between statements ("Zones").
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef POLLY_ZONEALGO_H
  15 #define POLLY_ZONEALGO_H
  16
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/DenseSet.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "isl/isl-noexceptions.h"
  21 #include <memory>
  22
  23 namespace llvm {
  24 class Value;
  25 class LoopInfo;
  26 class Loop;
  27 class PHINode;
  28 class raw_ostream;
  29 } // namespace llvm
  30
  31 namespace polly {
  32 class Scop;
  33 class ScopStmt;
  34 class MemoryAccess;
  35 class ScopArrayInfo;
  36
  37 /// Return only the mappings that map to known values.
  38 ///
  39 /// @param UMap { [] -> ValInst[] }
  40 ///
  41 /// @return { [] -> ValInst[] }
  42 isl::union_map filterKnownValInst(const isl::union_map &UMap);
  43
  44 /// Base class for algorithms based on zones, like DeLICM.
  45 class ZoneAlgorithm {
  46 protected:
  47   /// The name of the pass this is used from. Used for optimization remarks.
  48   const char *PassName;
  49
  50   /// Hold a reference to the isl_ctx to avoid it being freed before we released
  51   /// all of the isl objects.
  52   ///
  53   /// This must be declared before any other member that holds an isl object.
  54   /// This guarantees that the shared_ptr and its isl_ctx is destructed last,
  55   /// after all other members free'd the isl objects they were holding.
  56   std::shared_ptr<isl_ctx> IslCtx;
  57
  58   /// Cached reaching definitions for each ScopStmt.
  59   ///
  60   /// Use getScalarReachingDefinition() to get its contents.
  61   llvm::DenseMap<ScopStmt *, isl::map> ScalarReachDefZone;
  62
  63   /// The analyzed Scop.
  64   Scop *S;
  65
  66   /// LoopInfo analysis used to determine whether values are synthesizable.
  67   llvm::LoopInfo *LI;
  68
  69   /// Parameter space that does not need realignment.
  70   isl::space ParamSpace;
  71
  72   /// Space the schedule maps to.
  73   isl::space ScatterSpace;
  74
  75   /// Cached version of the schedule and domains.
  76   isl::union_map Schedule;
  77
  78   /// Combined access relations of all MemoryKind::Array READ accesses.
  79   /// { DomainRead[] -> Element[] }
  80   isl::union_map AllReads;
  81
  82   /// The loaded values (llvm::LoadInst) of all reads.
  83   /// { [Element[] -> DomainRead[]] -> ValInst[] }
  84   isl::union_map AllReadValInst;
  85
  86   /// Combined access relations of all MemoryKind::Array, MAY_WRITE accesses.
  87   /// { DomainMayWrite[] -> Element[] }
  88   isl::union_map AllMayWrites;
  89
  90   /// Combined access relations of all MemoryKind::Array, MUST_WRITE accesses.
  91   /// { DomainMustWrite[] -> Element[] }
  92   isl::union_map AllMustWrites;
  93
  94   /// Combined access relations of all MK_Array write accesses (union of
  95   /// AllMayWrites and AllMustWrites).
  96   /// { DomainWrite[] -> Element[] }
  97   isl::union_map AllWrites;
  98
  99   /// The value instances written to array elements of all write accesses.
 100   /// { [Element[] -> DomainWrite[]] -> ValInst[] }
 101   isl::union_map AllWriteValInst;
 102
 103   /// All reaching definitions for  MemoryKind::Array writes.
 104   /// { [Element[] -> Zone[]] -> DomainWrite[] }
 105   isl::union_map WriteReachDefZone;
 106
 107   /// Map llvm::Values to an isl identifier.
 108   /// Used with -polly-use-llvm-names=false as an alternative method to get
 109   /// unique ids that do not depend on pointer values.
 110   llvm::DenseMap<llvm::Value *, isl::id> ValueIds;
 111
 112   /// Set of array elements that can be reliably used for zone analysis.
 113   /// { Element[] }
 114   isl::union_set CompatibleElts;
 115
 116   /// List of PHIs that may transitively refer to themselves.
 117   ///
 118   /// Computing them would require a polyhedral transitive closure operation,
 119   /// for which isl may only return an approximation. For correctness, we always
 120   /// require an exact result. Hence, we exclude such PHIs.
 121   llvm::SmallPtrSet<llvm::PHINode *, 4> RecursivePHIs;
 122
 123   /// PHIs that have been computed.
 124   ///
 125   /// Computed PHIs are replaced by their incoming values using #NormalizeMap.
 126   llvm::DenseSet<llvm::PHINode *> ComputedPHIs;
 127
 128   /// For computed PHIs, contains the ValInst they stand for.
 129   ///
 130   /// To show an example, assume the following PHINode:
 131   ///
 132   ///   Stmt:
 133   ///     %phi = phi double [%val1, %bb1], [%val2, %bb2]
 134   ///
 135   /// It's ValInst is:
 136   ///
 137   ///   { [Stmt[i] -> phi[]] }
 138   ///
 139   /// The value %phi will be either %val1 or %val2, depending on whether in
 140   /// iteration i %bb1 or %bb2 has been executed before. In SCoPs, this can be
 141   /// determined at compile-time, and the result stored in #NormalizeMap. For
 142   /// the previous example, it could be:
 143   ///
 144   ///   { [Stmt[i] -> phi[]] -> [Stmt[0] -> val1[]];
 145   ///     [Stmt[i] -> phi[]] -> [Stmt[i] -> val2[]] : i > 0 }
 146   ///
 147   /// Only ValInsts in #ComputedPHIs are present in this map. Other values are
 148   /// assumed to represent themselves. This is to avoid adding lots of identity
 149   /// entries to this map.
 150   ///
 151   /// { PHIValInst[] -> IncomingValInst[] }
 152   isl::union_map NormalizeMap;
 153
 154   /// Cache for computePerPHI(const ScopArrayInfo *)
 155   llvm::SmallDenseMap<llvm::PHINode *, isl::union_map> PerPHIMaps;
 156
 157   /// Prepare the object before computing the zones of @p S.
 158   ///
 159   /// @param PassName Name of the pass using this analysis.
 160   /// @param S        The SCoP to process.
 161   /// @param LI       LoopInfo analysis used to determine synthesizable values.
 162   ZoneAlgorithm(const char *PassName, Scop *S, llvm::LoopInfo *LI);
 163
 164 private:
 165   /// Find the array elements that violate the zone analysis assumptions.
 166   ///
 167   /// What violates our assumptions:
 168   /// - A load after a write of the same location; we assume that all reads
 169   ///   occur before the writes.
 170   /// - Two writes to the same location; we cannot model the order in which
 171   ///   these occur.
 172   ///
 173   /// Scalar reads implicitly always occur before other accesses therefore never
 174   /// violate the first condition. There is also at most one write to a scalar,
 175   /// satisfying the second condition.
 176   ///
 177   /// @param Stmt                  The statement to be analyzed.
 178   /// @param[out] IncompatibleElts Receives the elements that are not
 179   ///                              zone-analysis compatible.
 180   /// @param[out]                  AllElts receives all encountered elements.
 181   void collectIncompatibleElts(ScopStmt *Stmt, isl::union_set &IncompatibleElts,
 182                                isl::union_set &AllElts);
 183
 184   void addArrayReadAccess(MemoryAccess *MA);
 185
 186   /// Return the ValInst write by a (must-)write access. Returns the 'unknown'
 187   /// ValInst if there is no single ValInst[] the array element written to will
 188   /// have.
 189   ///
 190   /// @return { ValInst[] }
 191   isl::union_map getWrittenValue(MemoryAccess *MA, isl::map AccRel);
 192
 193   void addArrayWriteAccess(MemoryAccess *MA);
 194
 195 protected:
 196   isl::union_set makeEmptyUnionSet() const;
 197
 198   isl::union_map makeEmptyUnionMap() const;
 199
 200   /// For each 'execution' of a PHINode, get the incoming block that was
 201   /// executed before.
 202   ///
 203   /// For each PHI instance we can directly determine which was the incoming
 204   /// block, and hence derive which value the PHI has.
 205   ///
 206   /// @param SAI The ScopArrayInfo representing the PHI's storage.
 207   ///
 208   /// @return { DomainPHIRead[] -> DomainPHIWrite[] }
 209   isl::union_map computePerPHI(const polly::ScopArrayInfo *SAI);
 210
 211   /// Find the array elements that can be used for zone analysis.
 212   void collectCompatibleElts();
 213
 214   /// Get the schedule for @p Stmt.
 215   ///
 216   /// The domain of the result is as narrow as possible.
 217   isl::map getScatterFor(ScopStmt *Stmt) const;
 218
 219   /// Get the schedule of @p MA's parent statement.
 220   isl::map getScatterFor(MemoryAccess *MA) const;
 221
 222   /// Get the schedule for the statement instances of @p Domain.
 223   isl::union_map getScatterFor(isl::union_set Domain) const;
 224
 225   /// Get the schedule for the statement instances of @p Domain.
 226   isl::map getScatterFor(isl::set Domain) const;
 227
 228   /// Get the domain of @p Stmt.
 229   isl::set getDomainFor(ScopStmt *Stmt) const;
 230
 231   /// Get the domain @p MA's parent statement.
 232   isl::set getDomainFor(MemoryAccess *MA) const;
 233
 234   /// Get the access relation of @p MA.
 235   ///
 236   /// The domain of the result is as narrow as possible.
 237   isl::map getAccessRelationFor(MemoryAccess *MA) const;
 238
 239   /// Get the reaching definition of a scalar defined in @p Stmt.
 240   ///
 241   /// Note that this does not depend on the llvm::Instruction, only on the
 242   /// statement it is defined in. Therefore the same computation can be reused.
 243   ///
 244   /// @param Stmt The statement in which a scalar is defined.
 245   ///
 246   /// @return { Scatter[] -> DomainDef[] }
 247   isl::map getScalarReachingDefinition(ScopStmt *Stmt);
 248
 249   /// Get the reaching definition of a scalar defined in @p DefDomain.
 250   ///
 251   /// @param DomainDef { DomainDef[] }
 252   ///              The write statements to get the reaching definition for.
 253   ///
 254   /// @return { Scatter[] -> DomainDef[] }
 255   isl::map getScalarReachingDefinition(isl::set DomainDef);
 256
 257   /// Create a statement-to-unknown value mapping.
 258   ///
 259   /// @param Stmt The statement whose instances are mapped to unknown.
 260   ///
 261   /// @return { Domain[] -> ValInst[] }
 262   isl::map makeUnknownForDomain(ScopStmt *Stmt) const;
 263
 264   /// Create an isl_id that represents @p V.
 265   isl::id makeValueId(llvm::Value *V);
 266
 267   /// Create the space for an llvm::Value that is available everywhere.
 268   isl::space makeValueSpace(llvm::Value *V);
 269
 270   /// Create a set with the llvm::Value @p V which is available everywhere.
 271   isl::set makeValueSet(llvm::Value *V);
 272
 273   /// Create a mapping from a statement instance to the instance of an
 274   /// llvm::Value that can be used in there.
 275   ///
 276   /// Although LLVM IR uses single static assignment, llvm::Values can have
 277   /// different contents in loops, when they get redefined in the last
 278   /// iteration. This function tries to get the statement instance of the
 279   /// previous definition, relative to a user.
 280   ///
 281   /// Example:
 282   /// for (int i = 0; i < N; i += 1) {
 283   /// DEF:
 284   ///    int v = A[i];
 285   /// USE:
 286   ///    use(v);
 287   ///  }
 288   ///
 289   /// The value instance used by statement instance USE[i] is DEF[i]. Hence,
 290   /// makeValInst returns:
 291   ///
 292   /// { USE[i] -> [DEF[i] -> v[]] : 0 <= i < N }
 293   ///
 294   /// @param Val       The value to get the instance of.
 295   /// @param UserStmt  The statement that uses @p Val. Can be nullptr.
 296   /// @param Scope     Loop the using instruction resides in.
 297   /// @param IsCertain Pass true if the definition of @p Val is a
 298   ///                  MUST_WRITE or false if the write is conditional.
 299   ///
 300   /// @return { DomainUse[] -> ValInst[] }
 301   isl::map makeValInst(llvm::Value *Val, ScopStmt *UserStmt, llvm::Loop *Scope,
 302                        bool IsCertain = true);
 303
 304   /// Create and normalize a ValInst.
 305   ///
 306   /// @see makeValInst
 307   /// @see normalizeValInst
 308   /// @see #NormalizedPHI
 309   isl::union_map makeNormalizedValInst(llvm::Value *Val, ScopStmt *UserStmt,
 310                                        llvm::Loop *Scope,
 311                                        bool IsCertain = true);
 312
 313   /// Return whether @p MA can be used for transformations (e.g. OpTree load
 314   /// forwarding, DeLICM mapping).
 315   bool isCompatibleAccess(MemoryAccess *MA);
 316
 317   /// Compute the different zones.
 318   void computeCommon();
 319
 320   ///  Compute the normalization map that replaces PHIs by their incoming
 321   ///  values.
 322   ///
 323   /// @see #NormalizeMap
 324   void computeNormalizedPHIs();
 325
 326   /// Print the current state of all MemoryAccesses to @p.
 327   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const;
 328
 329   /// Is @p MA a PHI READ access that can be normalized?
 330   ///
 331   /// @see #NormalizeMap
 332   bool isNormalizable(MemoryAccess *MA);
 333
 334   /// @{
 335   /// Determine whether the argument does not map to any computed PHI. Those
 336   /// should have been replaced by their incoming values.
 337   ///
 338   /// @see #NormalizedPHI
 339   bool isNormalized(isl::map Map);
 340   bool isNormalized(isl::union_map Map);
 341   /// @}
 342
 343 public:
 344   /// Return the SCoP this object is analyzing.
 345   Scop *getScop() const { return S; }
 346
 347   /// A reaching definition zone is known to have the definition's written value
 348   /// if the definition is a MUST_WRITE.
 349   ///
 350   /// @return { [Element[] -> Zone[]] -> ValInst[] }
 351   isl::union_map computeKnownFromMustWrites() const;
 352
 353   /// A reaching definition zone is known to be the same value as any load that
 354   /// reads from that array element in that period.
 355   ///
 356   /// @return { [Element[] -> Zone[]] -> ValInst[] }
 357   isl::union_map computeKnownFromLoad() const;
 358
 359   /// Compute which value an array element stores at every instant.
 360   ///
 361   /// @param FromWrite Use stores as source of information.
 362   /// @param FromRead  Use loads as source of information.
 363   ///
 364   /// @return { [Element[] -> Zone[]] -> ValInst[] }
 365   isl::union_map computeKnown(bool FromWrite, bool FromRead) const;
 366 };
 367
 368 /// Create a domain-to-unknown value mapping.
 369 ///
 370 /// Value instances that do not represent a specific value are represented by an
 371 /// unnamed tuple of 0 dimensions. Its meaning depends on the context. It can
 372 /// either mean a specific but unknown value which cannot be represented by
 373 /// other means. It conflicts with itself because those two unknown ValInsts may
 374 /// have different concrete values at runtime.
 375 ///
 376 /// The other meaning is an arbitrary or wildcard value that can be chosen
 377 /// freely, like LLVM's undef. If matched with an unknown ValInst, there is no
 378 /// conflict.
 379 ///
 380 /// @param Domain { Domain[] }
 381 ///
 382 /// @return { Domain[] -> ValInst[] }
 383 isl::union_map makeUnknownForDomain(isl::union_set Domain);
 384 } // namespace polly
 385
 386 #endif /* POLLY_ZONEALGO_H */