include/polly/ScopBuilder.h

   1 //===- polly/ScopBuilder.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 // Create a polyhedral description for a static control flow region.
  11 //
  12 // The pass creates a polyhedral description of the Scops detected by the SCoP
  13 // detection derived from their LLVM-IR code.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef POLLY_SCOPBUILDER_H
  18 #define POLLY_SCOPBUILDER_H
  19
  20 #include "polly/ScopInfo.h"
  21 #include "polly/Support/ScopHelper.h"
  22 #include "llvm/ADT/ArrayRef.h"
  23 #include "llvm/ADT/SetVector.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include <algorithm>
  26 #include <memory>
  27 #include <utility>
  28
  29 namespace llvm {
  30
  31 class AssumptionCache;
  32 class BasicBlock;
  33 class DataLayout;
  34 class DominatorTree;
  35 class Instruction;
  36 class LoopInfo;
  37 class PassRegistry;
  38 class PHINode;
  39 class Region;
  40 class ScalarEvolution;
  41 class SCEV;
  42 class Type;
  43 class Value;
  44
  45 void initializeScopInfoRegionPassPass(PassRegistry &);
  46 void initializeScopInfoWrapperPassPass(PassRegistry &);
  47
  48 } // end namespace llvm
  49
  50 namespace polly {
  51
  52 class ScopDetection;
  53
  54 /// Command line switch whether to model read-only accesses.
  55 extern bool ModelReadOnlyScalars;
  56
  57 /// Build the Polly IR (Scop and ScopStmt) on a Region.
  58 class ScopBuilder {
  59   /// The AliasAnalysis to build AliasSetTracker.
  60   AliasAnalysis &AA;
  61
  62   /// Target data for element size computing.
  63   const DataLayout &DL;
  64
  65   /// DominatorTree to reason about guaranteed execution.
  66   DominatorTree &DT;
  67
  68   /// LoopInfo for information about loops.
  69   LoopInfo &LI;
  70
  71   /// Valid Regions for Scop
  72   ScopDetection &SD;
  73
  74   /// The ScalarEvolution to help building Scop.
  75   ScalarEvolution &SE;
  76
  77   /// Set of instructions that might read any memory location.
  78   SmallVector<std::pair<ScopStmt *, Instruction *>, 16> GlobalReads;
  79
  80   /// Set of all accessed array base pointers.
  81   SmallSetVector<Value *, 16> ArrayBasePointers;
  82
  83   // The Scop
  84   std::unique_ptr<Scop> scop;
  85
  86   // Methods for pattern matching against Fortran code generated by dragonegg.
  87   // @{
  88
  89   /// Try to match for the descriptor of a Fortran array whose allocation
  90   /// is not visible. That is, we can see the load/store into the memory, but
  91   /// we don't actually know where the memory is allocated. If ALLOCATE had been
  92   /// called on the Fortran array, then we will see the lowered malloc() call.
  93   /// If not, this is dubbed as an "invisible allocation".
  94   ///
  95   /// "<descriptor>" is the descriptor of the Fortran array.
  96   ///
  97   /// Pattern match for "@descriptor":
  98   ///  1. %mem = load double*, double** bitcast (%"struct.array1_real(kind=8)"*
  99   ///    <descriptor> to double**), align 32
 100   ///
 101   ///  2. [%slot = getelementptr inbounds i8, i8* %mem, i64 <index>]
 102   ///  2 is optional because if you are writing to the 0th index, you don't
 103   ///     need a GEP.
 104   ///
 105   ///  3.1 store/load <memtype> <val>, <memtype>* %slot
 106   ///  3.2 store/load <memtype> <val>, <memtype>* %mem
 107   ///
 108   /// @see polly::MemoryAccess, polly::ScopArrayInfo
 109   ///
 110   /// @note assumes -polly-canonicalize has been run.
 111   ///
 112   /// @param Inst The LoadInst/StoreInst that accesses the memory.
 113   ///
 114   /// @returns Reference to <descriptor> on success, nullptr on failure.
 115   Value *findFADAllocationInvisible(MemAccInst Inst);
 116
 117   /// Try to match for the descriptor of a Fortran array whose allocation
 118   /// call is visible. When we have a Fortran array, we try to look for a
 119   /// Fortran array where we can see the lowered ALLOCATE call. ALLOCATE
 120   /// is materialized as a malloc(...) which we pattern match for.
 121   ///
 122   /// Pattern match for "%untypedmem":
 123   ///  1. %untypedmem = i8* @malloc(...)
 124   ///
 125   ///  2. %typedmem = bitcast i8* %untypedmem to <memtype>
 126   ///
 127   ///  3. [%slot = getelementptr inbounds i8, i8* %typedmem, i64 <index>]
 128   ///  3 is optional because if you are writing to the 0th index, you don't
 129   ///     need a GEP.
 130   ///
 131   ///  4.1 store/load <memtype> <val>, <memtype>* %slot, align 8
 132   ///  4.2 store/load <memtype> <val>, <memtype>* %mem, align 8
 133   ///
 134   /// @see polly::MemoryAccess, polly::ScopArrayInfo
 135   ///
 136   /// @note assumes -polly-canonicalize has been run.
 137   ///
 138   /// @param Inst The LoadInst/StoreInst that accesses the memory.
 139   ///
 140   /// @returns Reference to %untypedmem on success, nullptr on failure.
 141   Value *findFADAllocationVisible(MemAccInst Inst);
 142
 143   // @}
 144
 145   // Build the SCoP for Region @p R.
 146   void buildScop(Region &R, AssumptionCache &AC,
 147                  OptimizationRemarkEmitter &ORE);
 148
 149   /// Try to build a multi-dimensional fixed sized MemoryAccess from the
 150   /// Load/Store instruction.
 151   ///
 152   /// @param Inst       The Load/Store instruction that access the memory
 153   /// @param Stmt       The parent statement of the instruction
 154   ///
 155   /// @returns True if the access could be built, False otherwise.
 156   bool buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt);
 157
 158   /// Try to build a multi-dimensional parametric sized MemoryAccess.
 159   ///        from the Load/Store instruction.
 160   ///
 161   /// @param Inst       The Load/Store instruction that access the memory
 162   /// @param Stmt       The parent statement of the instruction
 163   ///
 164   /// @returns True if the access could be built, False otherwise.
 165   bool buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt);
 166
 167   /// Try to build a MemoryAccess for a memory intrinsic.
 168   ///
 169   /// @param Inst       The instruction that access the memory
 170   /// @param Stmt       The parent statement of the instruction
 171   ///
 172   /// @returns True if the access could be built, False otherwise.
 173   bool buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt);
 174
 175   /// Try to build a MemoryAccess for a call instruction.
 176   ///
 177   /// @param Inst       The call instruction that access the memory
 178   /// @param Stmt       The parent statement of the instruction
 179   ///
 180   /// @returns True if the access could be built, False otherwise.
 181   bool buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt);
 182
 183   /// Build a single-dimensional parametric sized MemoryAccess
 184   ///        from the Load/Store instruction.
 185   ///
 186   /// @param Inst       The Load/Store instruction that access the memory
 187   /// @param Stmt       The parent statement of the instruction
 188   void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt);
 189
 190   /// Build an instance of MemoryAccess from the Load/Store instruction.
 191   ///
 192   /// @param Inst       The Load/Store instruction that access the memory
 193   /// @param Stmt       The parent statement of the instruction
 194   void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt);
 195
 196   /// Analyze and extract the cross-BB scalar dependences (or, dataflow
 197   /// dependencies) of an instruction.
 198   ///
 199   /// @param UserStmt The statement @p Inst resides in.
 200   /// @param Inst     The instruction to be analyzed.
 201   void buildScalarDependences(ScopStmt *UserStmt, Instruction *Inst);
 202
 203   /// Build the escaping dependences for @p Inst.
 204   ///
 205   /// Search for uses of the llvm::Value defined by @p Inst that are not
 206   /// within the SCoP. If there is such use, add a SCALAR WRITE such that
 207   /// it is available after the SCoP as escaping value.
 208   ///
 209   /// @param Inst The instruction to be analyzed.
 210   void buildEscapingDependences(Instruction *Inst);
 211
 212   /// Create MemoryAccesses for the given PHI node in the given region.
 213   ///
 214   /// @param PHIStmt            The statement @p PHI resides in.
 215   /// @param PHI                The PHI node to be handled
 216   /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
 217   /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
 218   void buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
 219                         Region *NonAffineSubRegion, bool IsExitBlock = false);
 220
 221   /// Build the access functions for the subregion @p SR.
 222   void buildAccessFunctions();
 223
 224   /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
 225   ///
 226   /// @param SR A subregion of @p R.
 227   ///
 228   /// Some of the statements might be optimized away later when they do not
 229   /// access any memory and thus have no effect.
 230   void buildStmts(Region &SR);
 231
 232   /// Build the access functions for the statement @p Stmt in or represented by
 233   /// @p BB.
 234   ///
 235   /// @param Stmt               Statement to add MemoryAccesses to.
 236   /// @param BB                 A basic block in @p R.
 237   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
 238   /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
 239   void buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
 240                             Region *NonAffineSubRegion = nullptr,
 241                             bool IsExitBlock = false);
 242
 243   /// Create a new MemoryAccess object and add it to #AccFuncMap.
 244   ///
 245   /// @param Stmt        The statement where the access takes place.
 246   /// @param Inst        The instruction doing the access. It is not necessarily
 247   ///                    inside @p BB.
 248   /// @param AccType     The kind of access.
 249   /// @param BaseAddress The accessed array's base address.
 250   /// @param ElemType    The type of the accessed array elements.
 251   /// @param Affine      Whether all subscripts are affine expressions.
 252   /// @param AccessValue Value read or written.
 253   /// @param Subscripts  Access subscripts per dimension.
 254   /// @param Sizes       The array dimension's sizes.
 255   /// @param Kind        The kind of memory accessed.
 256   ///
 257   /// @return The created MemoryAccess, or nullptr if the access is not within
 258   ///         the SCoP.
 259   MemoryAccess *addMemoryAccess(ScopStmt *Stmt, Instruction *Inst,
 260                                 MemoryAccess::AccessType AccType,
 261                                 Value *BaseAddress, Type *ElemType, bool Affine,
 262                                 Value *AccessValue,
 263                                 ArrayRef<const SCEV *> Subscripts,
 264                                 ArrayRef<const SCEV *> Sizes, MemoryKind Kind);
 265
 266   /// Create a MemoryAccess that represents either a LoadInst or
 267   /// StoreInst.
 268   ///
 269   /// @param Stmt        The statement to add the MemoryAccess to.
 270   /// @param MemAccInst  The LoadInst or StoreInst.
 271   /// @param AccType     The kind of access.
 272   /// @param BaseAddress The accessed array's base address.
 273   /// @param ElemType    The type of the accessed array elements.
 274   /// @param IsAffine    Whether all subscripts are affine expressions.
 275   /// @param Subscripts  Access subscripts per dimension.
 276   /// @param Sizes       The array dimension's sizes.
 277   /// @param AccessValue Value read or written.
 278   ///
 279   /// @see MemoryKind
 280   void addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,
 281                       MemoryAccess::AccessType AccType, Value *BaseAddress,
 282                       Type *ElemType, bool IsAffine,
 283                       ArrayRef<const SCEV *> Subscripts,
 284                       ArrayRef<const SCEV *> Sizes, Value *AccessValue);
 285
 286   /// Create a MemoryAccess for writing an llvm::Instruction.
 287   ///
 288   /// The access will be created at the position of @p Inst.
 289   ///
 290   /// @param Inst The instruction to be written.
 291   ///
 292   /// @see ensureValueRead()
 293   /// @see MemoryKind
 294   void ensureValueWrite(Instruction *Inst);
 295
 296   /// Ensure an llvm::Value is available in the BB's statement, creating a
 297   /// MemoryAccess for reloading it if necessary.
 298   ///
 299   /// @param V        The value expected to be loaded.
 300   /// @param UserStmt Where to reload the value.
 301   ///
 302   /// @see ensureValueStore()
 303   /// @see MemoryKind
 304   void ensureValueRead(Value *V, ScopStmt *UserStmt);
 305
 306   /// Create a write MemoryAccess for the incoming block of a phi node.
 307   ///
 308   /// Each of the incoming blocks write their incoming value to be picked in the
 309   /// phi's block.
 310   ///
 311   /// @param PHI           PHINode under consideration.
 312   /// @param IncomingStmt  The statement to add the MemoryAccess to.
 313   /// @param IncomingBlock Some predecessor block.
 314   /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
 315   /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
 316   ///                      .phiops one. Required for values escaping through a
 317   ///                      PHINode in the SCoP region's exit block.
 318   /// @see addPHIReadAccess()
 319   /// @see MemoryKind
 320   void ensurePHIWrite(PHINode *PHI, ScopStmt *IncomintStmt,
 321                       BasicBlock *IncomingBlock, Value *IncomingValue,
 322                       bool IsExitBlock);
 323
 324   /// Create a MemoryAccess for reading the value of a phi.
 325   ///
 326   /// The modeling assumes that all incoming blocks write their incoming value
 327   /// to the same location. Thus, this access will read the incoming block's
 328   /// value as instructed by this @p PHI.
 329   ///
 330   /// @param PHIStmt Statement @p PHI resides in.
 331   /// @param PHI     PHINode under consideration; the READ access will be added
 332   ///                here.
 333   ///
 334   /// @see ensurePHIWrite()
 335   /// @see MemoryKind
 336   void addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI);
 337
 338   /// Build the domain of @p Stmt.
 339   void buildDomain(ScopStmt &Stmt);
 340
 341   /// Fill NestLoops with loops surrounding @p Stmt.
 342   void collectSurroundingLoops(ScopStmt &Stmt);
 343
 344   /// Build the access relation of all memory accesses of @p Stmt.
 345   void buildAccessRelations(ScopStmt &Stmt);
 346
 347 public:
 348   explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
 349                        const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
 350                        ScopDetection &SD, ScalarEvolution &SE,
 351                        OptimizationRemarkEmitter &ORE);
 352   ScopBuilder(const ScopBuilder &) = delete;
 353   ScopBuilder &operator=(const ScopBuilder &) = delete;
 354   ~ScopBuilder() = default;
 355
 356   /// Try to build the Polly IR of static control part on the current
 357   /// SESE-Region.
 358   ///
 359   /// @return Give up the ownership of the scop object or static control part
 360   ///         for the region
 361   std::unique_ptr<Scop> getScop() { return std::move(scop); }
 362 };
 363
 364 } // end namespace polly
 365
 366 #endif // POLLY_SCOPBUILDER_H