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_SCOP_BUILDER_H
  18 #define POLLY_SCOP_BUILDER_H
  19
  20 #include "polly/ScopInfo.h"
  21
  22 namespace polly {
  23
  24 /// @brief Build the Polly IR (Scop and ScopStmt) on a Region.
  25 class ScopBuilder {
  26   //===-------------------------------------------------------------------===//
  27   ScopBuilder(const ScopBuilder &) = delete;
  28   const ScopBuilder &operator=(const ScopBuilder &) = delete;
  29
  30   /// @brief The AliasAnalysis to build AliasSetTracker.
  31   AliasAnalysis &AA;
  32
  33   /// @brief Target data for element size computing.
  34   const DataLayout &DL;
  35
  36   /// @brief DominatorTree to reason about guaranteed execution.
  37   DominatorTree &DT;
  38
  39   /// @brief LoopInfo for information about loops
  40   LoopInfo &LI;
  41
  42   /// @biref Valid Regions for Scop
  43   ScopDetection &SD;
  44
  45   /// @brief The ScalarEvolution to help building Scop.
  46   ScalarEvolution &SE;
  47
  48   /// @brief Set of instructions that might read any memory location.
  49   SmallVector<Instruction *, 16> GlobalReads;
  50
  51   /// @brief Set of all accessed array base pointers.
  52   SmallSetVector<Value *, 16> ArrayBasePointers;
  53
  54   // The Scop
  55   std::unique_ptr<Scop> scop;
  56
  57   // Build the SCoP for Region @p R.
  58   void buildScop(Region &R, AssumptionCache &AC);
  59
  60   /// @brief Try to build a multi-dimensional fixed sized MemoryAccess from
  61   ///        the Load/Store instruction.
  62   ///
  63   /// @param Inst       The Load/Store instruction that access the memory
  64   /// @param L          The parent loop of the instruction
  65   ///
  66   /// @returns True if the access could be built, False otherwise.
  67   bool buildAccessMultiDimFixed(MemAccInst Inst, Loop *L);
  68
  69   /// @brief Try to build a multi-dimensional parameteric sized MemoryAccess
  70   ///        from the Load/Store instruction.
  71   ///
  72   /// @param Inst       The Load/Store instruction that access the memory
  73   /// @param L          The parent loop of the instruction
  74   ///
  75   /// @returns True if the access could be built, False otherwise.
  76   bool buildAccessMultiDimParam(MemAccInst Inst, Loop *L);
  77
  78   /// @brief Try to build a MemoryAccess for a memory intrinsic.
  79   ///
  80   /// @param Inst       The instruction that access the memory
  81   /// @param L          The parent loop of the instruction
  82   ///
  83   /// @returns True if the access could be built, False otherwise.
  84   bool buildAccessMemIntrinsic(MemAccInst Inst, Loop *L);
  85
  86   /// @brief Try to build a MemoryAccess for a call instruction.
  87   ///
  88   /// @param Inst       The call instruction that access the memory
  89   /// @param L          The parent loop of the instruction
  90   ///
  91   /// @returns True if the access could be built, False otherwise.
  92   bool buildAccessCallInst(MemAccInst Inst, Loop *L);
  93
  94   /// @brief Build a single-dimensional parametric sized MemoryAccess
  95   ///        from the Load/Store instruction.
  96   ///
  97   /// @param Inst       The Load/Store instruction that access the memory
  98   /// @param L          The parent loop of the instruction
  99   void buildAccessSingleDim(MemAccInst Inst, Loop *L);
 100
 101   /// @brief Build an instance of MemoryAccess from the Load/Store instruction.
 102   ///
 103   /// @param Inst       The Load/Store instruction that access the memory
 104   /// @param L          The parent loop of the instruction
 105   void buildMemoryAccess(MemAccInst Inst, Loop *L);
 106
 107   /// @brief Analyze and extract the cross-BB scalar dependences (or,
 108   ///        dataflow dependencies) of an instruction.
 109   ///
 110   /// @param Inst    The instruction to be analyzed.
 111   void buildScalarDependences(Instruction *Inst);
 112
 113   /// @brief Search for uses of the llvm::Value defined by @p Inst that are not
 114   ///        within the SCoP. If there is such use, add a SCALAR WRITE such that
 115   ///        it is available after the SCoP as escaping value.
 116   ///
 117   /// @param Inst The instruction to be analyzed.
 118   void buildEscapingDependences(Instruction *Inst);
 119
 120   /// @brief Create MemoryAccesses for the given PHI node in the given region.
 121   ///
 122   /// @param PHI                The PHI node to be handled
 123   /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
 124   /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
 125   void buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion,
 126                         bool IsExitBlock = false);
 127
 128   /// @brief Build the access functions for the subregion @p SR.
 129   ///
 130   /// @param SR           A subregion of @p R.
 131   /// @param InsnToMemAcc The Instruction to MemoryAccess mapping.
 132   void buildAccessFunctions(Region &SR);
 133
 134   /// @brief Create ScopStmt for all BBs and non-affine subregions of @p SR.
 135   ///
 136   /// @param SR A subregion of @p R.
 137   ///
 138   /// Some of the statments might be optimized away later when they do not
 139   /// access any memory and thus have no effect.
 140   void buildStmts(Region &SR);
 141
 142   /// @brief Build the access functions for the basic block @p BB
 143   ///
 144   /// @param BB                 A basic block in @p R.
 145   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
 146   /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
 147   void buildAccessFunctions(BasicBlock &BB,
 148                             Region *NonAffineSubRegion = nullptr,
 149                             bool IsExitBlock = false);
 150
 151   /// @brief Create a new MemoryAccess object and add it to #AccFuncMap.
 152   ///
 153   /// @param BB          The block where the access takes place.
 154   /// @param Inst        The instruction doing the access. It is not necessarily
 155   ///                    inside @p BB.
 156   /// @param AccType     The kind of access.
 157   /// @param BaseAddress The accessed array's base address.
 158   /// @param ElemType    The type of the accessed array elements.
 159   /// @param Affine      Whether all subscripts are affine expressions.
 160   /// @param AccessValue Value read or written.
 161   /// @param Subscripts  Access subscripts per dimension.
 162   /// @param Sizes       The array dimension's sizes.
 163   /// @param Kind        The kind of memory accessed.
 164   ///
 165   /// @return The created MemoryAccess, or nullptr if the access is not within
 166   ///         the SCoP.
 167   MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst,
 168                                 MemoryAccess::AccessType AccType,
 169                                 Value *BaseAddress, Type *ElemType, bool Affine,
 170                                 Value *AccessValue,
 171                                 ArrayRef<const SCEV *> Subscripts,
 172                                 ArrayRef<const SCEV *> Sizes,
 173                                 ScopArrayInfo::MemoryKind Kind);
 174
 175   /// @brief Create a MemoryAccess that represents either a LoadInst or
 176   /// StoreInst.
 177   ///
 178   /// @param MemAccInst  The LoadInst or StoreInst.
 179   /// @param AccType     The kind of access.
 180   /// @param BaseAddress The accessed array's base address.
 181   /// @param ElemType    The type of the accessed array elements.
 182   /// @param IsAffine    Whether all subscripts are affine expressions.
 183   /// @param Subscripts  Access subscripts per dimension.
 184   /// @param Sizes       The array dimension's sizes.
 185   /// @param AccessValue Value read or written.
 186   ///
 187   /// @see ScopArrayInfo::MemoryKind
 188   void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType AccType,
 189                       Value *BaseAddress, Type *ElemType, bool IsAffine,
 190                       ArrayRef<const SCEV *> Subscripts,
 191                       ArrayRef<const SCEV *> Sizes, Value *AccessValue);
 192
 193   /// @brief Create a MemoryAccess for writing an llvm::Instruction.
 194   ///
 195   /// The access will be created at the position of @p Inst.
 196   ///
 197   /// @param Inst The instruction to be written.
 198   ///
 199   /// @see ensureValueRead()
 200   /// @see ScopArrayInfo::MemoryKind
 201   void ensureValueWrite(Instruction *Inst);
 202
 203   /// @brief Ensure an llvm::Value is available in the BB's statement, creating
 204   ///        a MemoryAccess for reloading it if necessary.
 205   ///
 206   /// @param V      The value expected to be loaded.
 207   /// @param UserBB Where to reload the value.
 208   ///
 209   /// @see ensureValueStore()
 210   /// @see ScopArrayInfo::MemoryKind
 211   void ensureValueRead(Value *V, BasicBlock *UserBB);
 212
 213   /// @brief Create a write MemoryAccess for the incoming block of a phi node.
 214   ///
 215   /// Each of the incoming blocks write their incoming value to be picked in the
 216   /// phi's block.
 217   ///
 218   /// @param PHI           PHINode under consideration.
 219   /// @param IncomingBlock Some predecessor block.
 220   /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
 221   /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
 222   ///                      .phiops one. Required for values escaping through a
 223   ///                      PHINode in the SCoP region's exit block.
 224   /// @see addPHIReadAccess()
 225   /// @see ScopArrayInfo::MemoryKind
 226   void ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
 227                       Value *IncomingValue, bool IsExitBlock);
 228
 229   /// @brief Create a MemoryAccess for reading the value of a phi.
 230   ///
 231   /// The modeling assumes that all incoming blocks write their incoming value
 232   /// to the same location. Thus, this access will read the incoming block's
 233   /// value as instructed by this @p PHI.
 234   ///
 235   /// @param PHI PHINode under consideration; the READ access will be added
 236   /// here.
 237   ///
 238   /// @see ensurePHIWrite()
 239   /// @see ScopArrayInfo::MemoryKind
 240   void addPHIReadAccess(PHINode *PHI);
 241
 242 public:
 243   explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
 244                        const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
 245                        ScopDetection &SD, ScalarEvolution &SE);
 246   ~ScopBuilder() {}
 247
 248   /// @brief Try to build the Polly IR of static control part on the current
 249   ///        SESE-Region.
 250   ///
 251   /// @return Give up the ownership of the scop object or static control part
 252   ///         for the region
 253   std::unique_ptr<Scop> getScop() { return std::move(scop); }
 254 };
 255
 256 } // end namespace polly
 257
 258 namespace llvm {
 259 class PassRegistry;
 260 void initializeScopInfoRegionPassPass(llvm::PassRegistry &);
 261 void initializeScopInfoWrapperPassPass(llvm::PassRegistry &);
 262 } // namespace llvm
 263
 264 #endif