include/polly/TempScopInfo.h

   1 //===-------- polly/TempScopInfo.h - Extract TempScops ----------*- 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 // Collect information about the control flow regions detected by the Scop
  11 // detection, such that this information can be translated info its polyhedral
  12 // representation.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef POLLY_TEMP_SCOP_EXTRACTION_H
  17 #define POLLY_TEMP_SCOP_EXTRACTION_H
  18
  19 #include "polly/MayAliasSet.h"
  20 #include "polly/ScopDetection.h"
  21
  22 #include "llvm/Analysis/RegionPass.h"
  23 #include "llvm/IR/Instructions.h"
  24
  25 namespace llvm {
  26   class DataLayout;
  27 }
  28
  29 using namespace llvm;
  30
  31 namespace polly {
  32 class MayAliasSetInfo;
  33
  34 //===---------------------------------------------------------------------===//
  35 /// @brief A memory access described by a SCEV expression and the access type.
  36 class IRAccess {
  37 public:
  38   const Value *BaseAddress;
  39
  40   const SCEV *Offset;
  41
  42   // The type of the scev affine function
  43   enum TypeKind { READ, WRITE };
  44
  45 private:
  46   unsigned ElemBytes;
  47   TypeKind Type;
  48   bool IsAffine;
  49
  50 public:
  51   explicit IRAccess (TypeKind Type, const Value *BaseAddress,
  52                      const SCEV *Offset, unsigned elemBytes, bool Affine)
  53     : BaseAddress(BaseAddress), Offset(Offset),
  54       ElemBytes(elemBytes), Type(Type), IsAffine(Affine) {}
  55
  56   enum TypeKind getType() const { return Type; }
  57
  58   const Value *getBase() const { return BaseAddress; }
  59
  60   const SCEV *getOffset() const { return Offset; }
  61
  62   unsigned getElemSizeInBytes() const { return ElemBytes; }
  63
  64   bool isAffine() const { return IsAffine; }
  65
  66   bool isRead() const { return Type == READ; }
  67
  68   bool isWrite() const { return Type == WRITE; }
  69 };
  70
  71 class Comparison {
  72
  73   const SCEV *LHS;
  74   const SCEV *RHS;
  75
  76   ICmpInst::Predicate Pred;
  77
  78 public:
  79   Comparison(const SCEV *LHS, const SCEV *RHS, ICmpInst::Predicate Pred)
  80     : LHS(LHS), RHS(RHS), Pred(Pred) {}
  81
  82   const SCEV *getLHS() const { return LHS; }
  83   const SCEV *getRHS() const { return RHS; }
  84
  85   ICmpInst::Predicate getPred() const { return Pred; }
  86   void print(raw_ostream &OS) const;
  87 };
  88
  89 //===---------------------------------------------------------------------===//
  90 /// Types
  91 // The condition of a Basicblock, combine brcond with "And" operator.
  92 typedef SmallVector<Comparison, 4> BBCond;
  93
  94 /// Maps from a loop to the affine function expressing its backedge taken count.
  95 /// The backedge taken count already enough to express iteration domain as we
  96 /// only allow loops with canonical induction variable.
  97 /// A canonical induction variable is:
  98 /// an integer recurrence that starts at 0 and increments by one each time
  99 /// through the loop.
 100 typedef std::map<const Loop*, const SCEV*> LoopBoundMapType;
 101
 102 /// Mapping BBs to its condition constrains
 103 typedef std::map<const BasicBlock*, BBCond> BBCondMapType;
 104
 105 typedef std::vector<std::pair<IRAccess, Instruction*> > AccFuncSetType;
 106 typedef std::map<const BasicBlock*, AccFuncSetType> AccFuncMapType;
 107
 108 //===---------------------------------------------------------------------===//
 109 /// @brief Scop represent with llvm objects.
 110 ///
 111 /// A helper class for remembering the parameter number and the max depth in
 112 /// this Scop, and others context.
 113 class TempScop {
 114   // The Region.
 115   Region &R;
 116
 117   // The max loop depth of this Scop
 118   unsigned MaxLoopDepth;
 119
 120   // Remember the bounds of loops, to help us build iteration domain of BBs.
 121   const LoopBoundMapType &LoopBounds;
 122   const BBCondMapType &BBConds;
 123
 124   // Access function of bbs.
 125   const AccFuncMapType &AccFuncMap;
 126
 127   // The alias information about this SCoP.
 128   MayAliasSetInfo *MayASInfo;
 129
 130   friend class TempScopInfo;
 131
 132   explicit TempScop(Region &r, LoopBoundMapType &loopBounds,
 133                     BBCondMapType &BBCmps, AccFuncMapType &accFuncMap)
 134     : R(r), MaxLoopDepth(0), LoopBounds(loopBounds), BBConds(BBCmps),
 135     AccFuncMap(accFuncMap), MayASInfo(new MayAliasSetInfo()) {}
 136
 137 public:
 138   ~TempScop();
 139
 140   /// @brief Get the maximum Region contained by this Scop.
 141   ///
 142   /// @return The maximum Region contained by this Scop.
 143   Region &getMaxRegion() const { return R; }
 144
 145   /// @brief Get the maximum loop depth of Region R.
 146   ///
 147   /// @return The maximum loop depth of Region R.
 148   unsigned getMaxLoopDepth() const { return MaxLoopDepth; }
 149
 150   /// @brief Get the loop bounds of the given loop.
 151   ///
 152   /// @param L The loop to get the bounds.
 153   ///
 154   /// @return The bounds of the loop L in { Lower bound, Upper bound } form.
 155   ///
 156   const SCEV *getLoopBound(const Loop *L) const {
 157     LoopBoundMapType::const_iterator at = LoopBounds.find(L);
 158     assert(at != LoopBounds.end() && "Only valid loop is allow!");
 159     return at->second;
 160   }
 161
 162   /// @brief Get the condition from entry block of the Scop to a BasicBlock
 163   ///
 164   /// @param BB The BasicBlock
 165   ///
 166   /// @return The condition from entry block of the Scop to a BB
 167   ///
 168   const BBCond *getBBCond(const BasicBlock *BB) const {
 169     BBCondMapType::const_iterator at = BBConds.find(BB);
 170     return at != BBConds.end() ? &(at->second) : 0;
 171   }
 172
 173   /// @brief Get all access functions in a BasicBlock
 174   ///
 175   /// @param  BB The BasicBlock that containing the access functions.
 176   ///
 177   /// @return All access functions in BB
 178   ///
 179   const AccFuncSetType *getAccessFunctions(const BasicBlock* BB) const {
 180     AccFuncMapType::const_iterator at = AccFuncMap.find(BB);
 181     return at != AccFuncMap.end()? &(at->second) : 0;
 182   }
 183   //@}
 184
 185   /// @brief Print the Temporary Scop information.
 186   ///
 187   /// @param OS The output stream the access functions is printed to.
 188   /// @param SE The ScalarEvolution that help printing Temporary Scop
 189   ///           information.
 190   /// @param LI The LoopInfo that help printing the access functions.
 191   void print(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI) const;
 192
 193   /// @brief Print the access functions and loop bounds in this Scop.
 194   ///
 195   /// @param OS The output stream the access functions is printed to.
 196   /// @param SE The ScalarEvolution that help printing the access functions.
 197   /// @param LI The LoopInfo that help printing the access functions.
 198   void printDetail(raw_ostream &OS, ScalarEvolution *SE,
 199                    LoopInfo *LI, const Region *Reg, unsigned ind) const;
 200 };
 201
 202 typedef std::map<const Region*, TempScop*> TempScopMapType;
 203 //===----------------------------------------------------------------------===//
 204 /// @brief The Function Pass to extract temporary information for Static control
 205 ///        part in llvm function.
 206 ///
 207 class TempScopInfo : public FunctionPass {
 208   //===-------------------------------------------------------------------===//
 209   // DO NOT IMPLEMENT
 210   TempScopInfo(const TempScopInfo &);
 211   // DO NOT IMPLEMENT
 212   const TempScopInfo &operator=(const TempScopInfo &);
 213
 214   // The ScalarEvolution to help building Scop.
 215   ScalarEvolution* SE;
 216
 217   // LoopInfo for information about loops
 218   LoopInfo *LI;
 219
 220   // The AliasAnalysis to build AliasSetTracker.
 221   AliasAnalysis *AA;
 222
 223   // Valid Regions for Scop
 224   ScopDetection *SD;
 225
 226   // For condition extraction support.
 227   DominatorTree *DT;
 228   PostDominatorTree *PDT;
 229
 230   // Target data for element size computing.
 231   DataLayout *TD;
 232
 233   // Remember the bounds of loops, to help us build iteration domain of BBs.
 234   LoopBoundMapType LoopBounds;
 235
 236   // And also Remember the constrains for BBs
 237   BBCondMapType BBConds;
 238
 239   // Access function of bbs.
 240   AccFuncMapType AccFuncMap;
 241
 242   // Mapping regions to the corresponding Scop in current function.
 243   TempScopMapType TempScops;
 244
 245   // Clear the context.
 246   void clear();
 247
 248   /// @brief Build condition constrains to BBs in a valid Scop.
 249   ///
 250   /// @param BB           The BasicBlock to build condition constrains
 251   /// @param RegionEntry  The entry block of the Smallest Region that containing
 252   ///                     BB
 253   void buildCondition(BasicBlock *BB, BasicBlock *RegionEntry);
 254
 255   // Build the affine function of the given condition
 256   void buildAffineCondition(Value &V, bool inverted, Comparison **Comp) const;
 257
 258   // Return the temporary Scop information of Region R, where R must be a valid
 259   // part of Scop
 260   TempScop *getTempScop(Region &R);
 261
 262   // Build the temprory information of Region R, where R must be a valid part
 263   // of Scop.
 264   TempScop *buildTempScop(Region &R);
 265
 266   void buildAccessFunctions(Region &RefRegion, BasicBlock &BB);
 267
 268   void buildLoopBounds(TempScop &Scop);
 269
 270 public:
 271   static char ID;
 272   explicit TempScopInfo() : FunctionPass(ID) {}
 273   ~TempScopInfo();
 274
 275   /// @brief Get the temporay Scop information in LLVM IR represent
 276   ///        for Region R.
 277   ///
 278   /// @return The Scop information in LLVM IR represent.
 279   TempScop *getTempScop(const Region *R) const;
 280
 281   /// @name FunctionPass interface
 282   //@{
 283   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 284   virtual void releaseMemory() { clear(); }
 285   virtual bool runOnFunction(Function &F);
 286   virtual void print(raw_ostream &OS, const Module *) const;
 287   //@}
 288 };
 289
 290 } // end namespace polly
 291
 292 namespace llvm {
 293   class PassRegistry;
 294   void initializeTempScopInfoPass(llvm::PassRegistry&);
 295 }
 296
 297 #endif