Merge TempScopInfo.{cpp|h} into ScopInfo.{cpp|h}

[Meinersbur]

Summary

This prepares for a series of patches that merges TempScopInfo into ScopInfo to
reduce Polly's code complexity. Only ScopInfo.{cpp|h} will be left thereafter.
Moving the code of TempScopInfo in one commit makes the mains diffs simpler to
understand.

In details, the following classes are intended to be merged:
TempScopInfo into ScopInfo
TempScop into Scop
IRAccess into MemoryAccess

Only moving code, no functional changes intended.

[jdoerfert]

LGTM

• msg-30032-466.dat219 BDownload

[grosser]

Not really needed, as Johannes already OKed this and the following commit,
but these look both good to me.

Tobias

[Meinersbur]

Rebase to r247142

[Meinersbur]

Committed as r247274

include/polly/ScopInfo.h

 class IRAccess;
 class Scop;
 class ScopStmt;
 class ScopInfo;
 class TempScop;
 class Comparison;
 class SCEVAffFunc;
 
+class Comparison {
+  const SCEV *LHS;
+  const SCEV *RHS;
+
+  ICmpInst::Predicate Pred;
+
+public:
+  Comparison(const SCEV *LHS, const SCEV *RHS, ICmpInst::Predicate Pred)
+      : LHS(LHS), RHS(RHS), Pred(Pred) {}
+
+  const SCEV *getLHS() const { return LHS; }
+  const SCEV *getRHS() const { return RHS; }
+
+  ICmpInst::Predicate getPred() const { return Pred; }
+  void print(raw_ostream &OS) const;
+};
+
+//===---------------------------------------------------------------------===//
+
+/// Maps from a loop to the affine function expressing its backedge taken count.
+/// The backedge taken count already enough to express iteration domain as we
+/// only allow loops with canonical induction variable.
+/// A canonical induction variable is:
+/// an integer recurrence that starts at 0 and increments by one each time
+/// through the loop.
+typedef std::map<const Loop *, const SCEV *> LoopBoundMapType;
+
+typedef std::vector<std::pair<IRAccess, Instruction *>> AccFuncSetType;
+typedef std::map<const BasicBlock *, AccFuncSetType> AccFuncMapType;
+
 /// @brief A class to store information about arrays in the SCoP.
 ///
 /// Objects are accessible via the ScoP, MemoryAccess or the id associated with
 /// the MemoryAccess access function.
 ///
 class ScopArrayInfo {
 public:
   /// @brief Construct a ScopArrayInfo object.
private:
 
   /// @brief The sizes of each dimension as isl_pw_aff.
   SmallVector<isl_pw_aff *, 4> DimensionSizesPw;
 
   /// @brief Is this PHI node specific storage?
   bool IsPHI;
 };
 
+//===---------------------------------------------------------------------===//
+/// @brief A memory access described by a SCEV expression and the access type.
+class IRAccess {
+public:
+  Value *BaseAddress;
+  Value *AccessValue;
+
+  const SCEV *Offset;
+
+  // The type of the scev affine function
+  enum TypeKind {
+    READ = 0x1,
+    MUST_WRITE = 0x2,
+    MAY_WRITE = 0x3,
+  };
+
+private:
+  unsigned ElemBytes;
+  TypeKind Type;
+  bool IsAffine;
+
+  /// @brief Is this IRAccess modeling special PHI node accesses?
+  bool IsPHI;
+
+public:
+  SmallVector<const SCEV *, 4> Subscripts, Sizes;
+
+  /// @brief Create a new IRAccess
+  ///
+  /// @param IsPHI Are we modeling special PHI node accesses?
+  explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset,
+                    unsigned elemBytes, bool Affine, Value *AccessValue,
+                    bool IsPHI = false)
+      : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset),
+        ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(IsPHI) {}
+
+  explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset,
+                    unsigned elemBytes, bool Affine,
+                    SmallVector<const SCEV *, 4> Subscripts,
+                    SmallVector<const SCEV *, 4> Sizes, Value *AccessValue)
+      : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset),
+        ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(false),
+        Subscripts(Subscripts), Sizes(Sizes) {}
+
+  enum TypeKind getType() const { return Type; }
+
+  Value *getBase() const { return BaseAddress; }
+
+  Value *getAccessValue() const { return AccessValue; }
+
+  const SCEV *getOffset() const { return Offset; }
+
+  unsigned getElemSizeInBytes() const { return ElemBytes; }
+
+  bool isAffine() const { return IsAffine; }
+
+  bool isRead() const { return Type == READ; }
+
+  bool isWrite() const { return Type == MUST_WRITE; }
+
+  void setMayWrite() { Type = MAY_WRITE; }
+
+  bool isMayWrite() const { return Type == MAY_WRITE; }
+
+  bool isScalar() const { return Subscripts.size() == 0; }
+
+  // @brief Is this IRAccess modeling special PHI node accesses?
+  bool isPHI() const { return IsPHI; }
+
+  void print(raw_ostream &OS) const;
+};
+
 /// @brief Represent memory accesses in statements.
 class MemoryAccess {
 public:
   /// @brief The access type of a memory access
   ///
   /// There are three kind of access types:
   ///
   /// * A read access

 };
 
 /// @brief Print Scop scop to raw_ostream O.
 static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {
   scop.print(O);
   return O;
 }
 
+//===---------------------------------------------------------------------===//
+/// @brief Scop represent with llvm objects.
+///
+/// A helper class for remembering the parameter number and the max depth in
+/// this Scop, and others context.
+class TempScop {
+  // The Region.
+  Region &R;
+
+  // Access function of bbs.
+  AccFuncMapType &AccFuncMap;
+
+  friend class TempScopInfo;
+
+  explicit TempScop(Region &r, AccFuncMapType &accFuncMap)
+      : R(r), AccFuncMap(accFuncMap) {}
+
+public:
+  ~TempScop();
+
+  /// @brief Get the maximum Region contained by this Scop.
+  ///
+  /// @return The maximum Region contained by this Scop.
+  Region &getMaxRegion() const { return R; }
+
+  /// @brief Get all access functions in a BasicBlock
+  ///
+  /// @param  BB The BasicBlock that containing the access functions.
+  ///
+  /// @return All access functions in BB
+  ///
+  AccFuncSetType *getAccessFunctions(const BasicBlock *BB) {
+    AccFuncMapType::iterator at = AccFuncMap.find(BB);
+    return at != AccFuncMap.end() ? &(at->second) : 0;
+  }
+  //@}
+
+  /// @brief Print the Temporary Scop information.
+  ///
+  /// @param OS The output stream the access functions is printed to.
+  /// @param SE The ScalarEvolution that help printing Temporary Scop
+  ///           information.
+  /// @param LI The LoopInfo that help printing the access functions.
+  void print(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI) const;
+
+  /// @brief Print the access functions and loop bounds in this Scop.
+  ///
+  /// @param OS The output stream the access functions is printed to.
+  /// @param SE The ScalarEvolution that help printing the access functions.
+  /// @param LI The LoopInfo that help printing the access functions.
+  void printDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI,
+                   const Region *Reg, unsigned ind) const;
+};
+
+typedef std::map<const Region *, TempScop *> TempScopMapType;
+//===----------------------------------------------------------------------===//
+/// @brief The Function Pass to extract temporary information for Static control
+///        part in llvm function.
+///
+class TempScopInfo : public RegionPass {
+  //===-------------------------------------------------------------------===//
+  TempScopInfo(const TempScopInfo &) = delete;
+  const TempScopInfo &operator=(const TempScopInfo &) = delete;
+
+  // The ScalarEvolution to help building Scop.
+  ScalarEvolution *SE;
+
+  // LoopInfo for information about loops
+  LoopInfo *LI;
+
+  // The AliasAnalysis to build AliasSetTracker.
+  AliasAnalysis *AA;
+
+  // Valid Regions for Scop
+  ScopDetection *SD;
+
+  // Target data for element size computing.
+  const DataLayout *TD;
+
+  // Access function of statements (currently BasicBlocks) .
+  AccFuncMapType AccFuncMap;
+
+  // Pre-created zero for the scalar accesses, with it we do not need create a
+  // zero scev every time when we need it.
+  const SCEV *ZeroOffset;
+
+  // The TempScop for this region.
+  TempScop *TempScopOfRegion;
+
+  // Clear the context.
+  void clear();
+
+  // Build the temprory information of Region R, where R must be a valid part
+  // of Scop.
+  TempScop *buildTempScop(Region &R);
+
+  /// @brief Build an instance of IRAccess from the Load/Store instruction.
+  ///
+  /// @param Inst       The Load/Store instruction that access the memory
+  /// @param L          The parent loop of the instruction
+  /// @param R          The region on which we are going to build a TempScop
+  /// @param BoxedLoops The set of loops that are overapproximated in @p R.
+  ///
+  /// @return     The IRAccess to describe the access function of the
+  ///             instruction.
+  IRAccess buildIRAccess(Instruction *Inst, Loop *L, Region *R,
+                         const ScopDetection::BoxedLoopsSetTy *BoxedLoops);
+
+  /// @brief Analyze and extract the cross-BB scalar dependences (or,
+  ///        dataflow dependencies) of an instruction.
+  ///
+  /// @param Inst               The instruction to be analyzed
+  /// @param R                  The SCoP region
+  /// @param NonAffineSubRegion The non affine sub-region @p Inst is in.
+  ///
+  /// @return     True if the Instruction is used in other BB and a scalar write
+  ///             Access is required.
+  bool buildScalarDependences(Instruction *Inst, Region *R,
+                              Region *NonAffineSubRegio);
+
+  /// @brief Create IRAccesses for the given PHI node in the given region.
+  ///
+  /// @param PHI                The PHI node to be handled
+  /// @param R                  The SCoP region
+  /// @param Functions          The access functions of the current BB
+  /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
+  /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
+  void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions,
+                        Region *NonAffineSubRegion, bool IsExitBlock = false);
+
+  /// @brief Build the access functions for the subregion @p SR.
+  ///
+  /// @param R  The SCoP region.
+  /// @param SR A subregion of @p R.
+  void buildAccessFunctions(Region &R, Region &SR);
+
+  /// @brief Build the access functions for the basic block @p BB
+  ///
+  /// @param R                  The SCoP region.
+  /// @param BB                 A basic block in @p R.
+  /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
+  /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
+  void buildAccessFunctions(Region &R, BasicBlock &BB,
+                            Region *NonAffineSubRegion = nullptr,
+                            bool IsExitBlock = false);
+
+public:
+  static char ID;
+  explicit TempScopInfo() : RegionPass(ID), TempScopOfRegion(nullptr) {}
+  ~TempScopInfo();
+
+  /// @brief Get the temporay Scop information in LLVM IR for this region.
+  ///
+  /// @return The Scop information in LLVM IR represent.
+  TempScop *getTempScop() const;
+
+  /// @name RegionPass interface
+  //@{
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+  virtual void releaseMemory() { clear(); }
+  virtual bool runOnRegion(Region *R, RGPassManager &RGM);
+  virtual void print(raw_ostream &OS, const Module *) const;
+  //@}
+};
+
 ///===---------------------------------------------------------------------===//
 /// @brief Build the Polly IR (Scop and ScopStmt) on a Region.
 ///
 class ScopInfo : public RegionPass {
   //===-------------------------------------------------------------------===//
   ScopInfo(const ScopInfo &) = delete;
   const ScopInfo &operator=(const ScopInfo &) = delete;
 
public:
   }
   //@}
 };
 
 } // end namespace polly
 
 namespace llvm {
 class PassRegistry;
+void initializeTempScopInfoPass(llvm::PassRegistry &);
 void initializeScopInfoPass(llvm::PassRegistry &);
 }
 
 #endif

lib/Analysis/ScopInfo.cpp

 //===----------------------------------------------------------------------===//
 
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
-#include "polly/TempScopInfo.h"
+#include "polly/CodeGen/BlockGenerators.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"

 using namespace llvm;
 using namespace polly;
 
 #define DEBUG_TYPE "polly-scops"
 
 STATISTIC(ScopFound, "Number of valid Scops");
 STATISTIC(RichScopFound, "Number of Scops containing a loop");
 
+static cl::opt<bool> ModelReadOnlyScalars(
+    "polly-analyze-read-only-scalars",
+    cl::desc("Model read-only scalar values in the scop description"),
+    cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
+
 // Multiplicative reductions can be disabled separately as these kind of
 // operations can overflow easily. Additive reductions and bit operations
 // are in contrast pretty stable.
 static cl::opt<bool> DisableMultiplicativeReductions(
     "polly-disable-multiplicative-reductions",
     cl::desc("Disable multiplicative reductions"), cl::Hidden, cl::ZeroOrMore,
     cl::init(false), cl::cat(PollyCategory));
 
static cl::opt<std::string> UserContextStr(
     cl::desc("Provide additional constraints on the context parameters"),
     cl::init(""), cl::cat(PollyCategory));
 
 static cl::opt<bool> DetectReductions("polly-detect-reductions",
                                       cl::desc("Detect and exploit reductions"),
                                       cl::Hidden, cl::ZeroOrMore,
                                       cl::init(true), cl::cat(PollyCategory));
 
+//===----------------------------------------------------------------------===//
+/// Helper Classes
+
+void Comparison::print(raw_ostream &OS) const {
+  // Not yet implemented.
+}
+
 // Create a sequence of two schedules. Either argument may be null and is
 // interpreted as the empty schedule. Can also return null if both schedules are
 // empty.
 static __isl_give isl_schedule *
 combineInSequence(__isl_take isl_schedule *Prev,
                   __isl_take isl_schedule *Succ) {
   if (!Prev)
     return Succ;

 
 const ScopArrayInfo *ScopArrayInfo::getFromId(isl_id *Id) {
   void *User = isl_id_get_user(Id);
   const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);
   isl_id_free(Id);
   return SAI;
 }
 
+void IRAccess::print(raw_ostream &OS) const {
+  if (isRead())
+    OS << "Read ";
+  else {
+    if (isMayWrite())
+      OS << "May";
+    OS << "Write ";
+  }
+  OS << BaseAddress->getName() << '[' << *Offset << "]\n";
+}
+
 const std::string
 MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
   switch (RT) {
   case MemoryAccess::RT_NONE:
     llvm_unreachable("Requested a reduction operator string for a memory "
                      "access which isn't a reduction");
   case MemoryAccess::RT_ADD:
     return "+";

 
 ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
   auto StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
     return nullptr;
   return StmtMapIt->second;
 }
 
+//===----------------------------------------------------------------------===//
+// TempScop implementation
+TempScop::~TempScop() {}
+
+void TempScop::print(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI) const {
+  OS << "Scop: " << R.getNameStr() << "\n";
+
+  printDetail(OS, SE, LI, &R, 0);
+}
+
+void TempScop::printDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI,
+                           const Region *CurR, unsigned ind) const {
+  // FIXME: Print other details rather than memory accesses.
+  for (const auto &CurBlock : CurR->blocks()) {
+    AccFuncMapType::const_iterator AccSetIt = AccFuncMap.find(CurBlock);
+
+    // Ignore trivial blocks that do not contain any memory access.
+    if (AccSetIt == AccFuncMap.end())
+      continue;
+
+    OS.indent(ind) << "BB: " << CurBlock->getName() << '\n';
+    typedef AccFuncSetType::const_iterator access_iterator;
+    const AccFuncSetType &AccFuncs = AccSetIt->second;
+
+    for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE;
+         ++AI)
+      AI->first.print(OS.indent(ind + 2));
+  }
+}
+
 int Scop::getRelativeLoopDepth(const Loop *L) const {
   Loop *OuterLoop =
       L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
   if (!OuterLoop)
     return -1;
   return L->getLoopDepth() - OuterLoop->getLoopDepth();
 }
 
+void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
+                                    AccFuncSetType &Functions,
+                                    Region *NonAffineSubRegion,
+                                    bool IsExitBlock) {
+
+  // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
+  // true, are not modeled as ordinary PHI nodes as they are not part of the
+  // region. However, we model the operands in the predecessor blocks that are
+  // part of the region as regular scalar accesses.
+
+  // If we can synthesize a PHI we can skip it, however only if it is in
+  // the region. If it is not it can only be in the exit block of the region.
+  // In this case we model the operands but not the PHI itself.
+  if (!IsExitBlock && canSynthesize(PHI, LI, SE, &R))
+    return;
+
+  // PHI nodes are modeled as if they had been demoted prior to the SCoP
+  // detection. Hence, the PHI is a load of a new memory location in which the
+  // incoming value was written at the end of the incoming basic block.
+  bool OnlyNonAffineSubRegionOperands = true;
+  for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
+    Value *Op = PHI->getIncomingValue(u);
+    BasicBlock *OpBB = PHI->getIncomingBlock(u);
+
+    // Do not build scalar dependences inside a non-affine subregion.
+    if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB))
+      continue;
+
+    OnlyNonAffineSubRegionOperands = false;
+
+    if (!R.contains(OpBB))
+      continue;
+
+    Instruction *OpI = dyn_cast<Instruction>(Op);
+    if (OpI) {
+      BasicBlock *OpIBB = OpI->getParent();
+      // As we pretend there is a use (or more precise a write) of OpI in OpBB
+      // we have to insert a scalar dependence from the definition of OpI to
+      // OpBB if the definition is not in OpBB.
+      if (OpIBB != OpBB) {
+        IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true, OpI);
+        AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI));
+        IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true,
+                             OpI);
+        AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI));
+      }
+    }
+
+    // Always use the terminator of the incoming basic block as the access
+    // instruction.
+    OpI = OpBB->getTerminator();
+
+    IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true, Op,
+                          /* IsPHI */ !IsExitBlock);
+    AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI));
+  }
+
+  if (!OnlyNonAffineSubRegionOperands) {
+    IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI,
+                          /* IsPHI */ !IsExitBlock);
+    Functions.push_back(std::make_pair(ScalarAccess, PHI));
+  }
+}
+
+bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
+                                          Region *NonAffineSubRegion) {
+  bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
+  if (isIgnoredIntrinsic(Inst))
+    return false;
+
+  bool AnyCrossStmtUse = false;
+  BasicBlock *ParentBB = Inst->getParent();
+
+  for (User *U : Inst->users()) {
+    Instruction *UI = dyn_cast<Instruction>(U);
+
+    // Ignore the strange user
+    if (UI == 0)
+      continue;
+
+    BasicBlock *UseParent = UI->getParent();
+
+    // Ignore the users in the same BB (statement)
+    if (UseParent == ParentBB)
+      continue;
+
+    // Do not build scalar dependences inside a non-affine subregion.
+    if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
+      continue;
+
+    // Check whether or not the use is in the SCoP.
+    if (!R->contains(UseParent)) {
+      AnyCrossStmtUse = true;
+      continue;
+    }
+
+    // If the instruction can be synthesized and the user is in the region
+    // we do not need to add scalar dependences.
+    if (canSynthesizeInst)
+      continue;
+
+    // No need to translate these scalar dependences into polyhedral form,
+    // because synthesizable scalars can be generated by the code generator.
+    if (canSynthesize(UI, LI, SE, R))
+      continue;
+
+    // Skip PHI nodes in the region as they handle their operands on their own.
+    if (isa<PHINode>(UI))
+      continue;
+
+    // Now U is used in another statement.
+    AnyCrossStmtUse = true;
+
+    // Do not build a read access that is not in the current SCoP
+    // Use the def instruction as base address of the IRAccess, so that it will
+    // become the name of the scalar access in the polyhedral form.
+    IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true, Inst);
+    AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, UI));
+  }
+
+  if (ModelReadOnlyScalars) {
+    for (Value *Op : Inst->operands()) {
+      if (canSynthesize(Op, LI, SE, R))
+        continue;
+
+      if (Instruction *OpInst = dyn_cast<Instruction>(Op))
+        if (R->contains(OpInst))
+          continue;
+
+      if (isa<Constant>(Op))
+        continue;
+
+      IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true, Op);
+      AccFuncMap[Inst->getParent()].push_back(
+          std::make_pair(ScalarAccess, Inst));
+    }
+  }
+
+  return AnyCrossStmtUse;
+}
+
+extern MapInsnToMemAcc InsnToMemAcc;
+
+IRAccess
+TempScopInfo::buildIRAccess(Instruction *Inst, Loop *L, Region *R,
+                            const ScopDetection::BoxedLoopsSetTy *BoxedLoops) {
+  unsigned Size;
+  Type *SizeType;
+  Value *Val;
+  enum IRAccess::TypeKind Type;
+
+  if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
+    SizeType = Load->getType();
+    Size = TD->getTypeStoreSize(SizeType);
+    Type = IRAccess::READ;
+    Val = Load;
+  } else {
+    StoreInst *Store = cast<StoreInst>(Inst);
+    SizeType = Store->getValueOperand()->getType();
+    Size = TD->getTypeStoreSize(SizeType);
+    Type = IRAccess::MUST_WRITE;
+    Val = Store->getValueOperand();
+  }
+
+  const SCEV *AccessFunction = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
+  const SCEVUnknown *BasePointer =
+      dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
+
+  assert(BasePointer && "Could not find base pointer");
+  AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
+
+  auto AccItr = InsnToMemAcc.find(Inst);
+  if (PollyDelinearize && AccItr != InsnToMemAcc.end())
+    return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, true,
+                    AccItr->second.DelinearizedSubscripts,
+                    AccItr->second.Shape->DelinearizedSizes, Val);
+
+  // Check if the access depends on a loop contained in a non-affine subregion.
+  bool isVariantInNonAffineLoop = false;
+  if (BoxedLoops) {
+    SetVector<const Loop *> Loops;
+    findLoops(AccessFunction, Loops);
+    for (const Loop *L : Loops)
+      if (BoxedLoops->count(L))
+        isVariantInNonAffineLoop = true;
+  }
+
+  bool IsAffine = !isVariantInNonAffineLoop &&
+                  isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue());
+
+  SmallVector<const SCEV *, 4> Subscripts, Sizes;
+  Subscripts.push_back(AccessFunction);
+  Sizes.push_back(SE->getConstant(ZeroOffset->getType(), Size));
+
+  if (!IsAffine && Type == IRAccess::MUST_WRITE)
+    Type = IRAccess::MAY_WRITE;
+
+  return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, IsAffine,
+                  Subscripts, Sizes, Val);
+}
+
+void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) {
+
+  if (SD->isNonAffineSubRegion(&SR, &R)) {
+    for (BasicBlock *BB : SR.blocks())
+      buildAccessFunctions(R, *BB, &SR);
+    return;
+  }
+
+  for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
+    if (I->isSubRegion())
+      buildAccessFunctions(R, *I->getNodeAs<Region>());
+    else
+      buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
+}
+
+void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
+                                        Region *NonAffineSubRegion,
+                                        bool IsExitBlock) {
+  AccFuncSetType Functions;
+  Loop *L = LI->getLoopFor(&BB);
+
+  // The set of loops contained in non-affine subregions that are part of R.
+  const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
+
+  for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
+    Instruction *Inst = I;
+
+    PHINode *PHI = dyn_cast<PHINode>(Inst);
+    if (PHI)
+      buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion, IsExitBlock);
+
+    // For the exit block we stop modeling after the last PHI node.
+    if (!PHI && IsExitBlock)
+      break;
+
+    if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
+      Functions.push_back(
+          std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst));
+
+    if (isIgnoredIntrinsic(Inst))
+      continue;
+
+    if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
+      // If the Instruction is used outside the statement, we need to build the
+      // write access.
+      if (!isa<StoreInst>(Inst)) {
+        IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true,
+                              Inst);
+        Functions.push_back(std::make_pair(ScalarAccess, Inst));
+      }
+    }
+  }
+
+  if (Functions.empty())
+    return;
+
+  AccFuncSetType &Accs = AccFuncMap[&BB];
+  Accs.insert(Accs.end(), Functions.begin(), Functions.end());
+}
+
+TempScop *TempScopInfo::buildTempScop(Region &R) {
+  TempScop *TScop = new TempScop(R, AccFuncMap);
+
+  buildAccessFunctions(R, R);
+
+  // In case the region does not have an exiting block we will later (during
+  // code generation) split the exit block. This will move potential PHI nodes
+  // from the current exit block into the new region exiting block. Hence, PHI
+  // nodes that are at this point not part of the region will be.
+  // To handle these PHI nodes later we will now model their operands as scalar
+  // accesses. Note that we do not model anything in the exit block if we have
+  // an exiting block in the region, as there will not be any splitting later.
+  if (!R.getExitingBlock())
+    buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true);
+
+  return TScop;
+}
+
+TempScop *TempScopInfo::getTempScop() const { return TempScopOfRegion; }
+
+void TempScopInfo::print(raw_ostream &OS, const Module *) const {
+  if (TempScopOfRegion)
+    TempScopOfRegion->print(OS, SE, LI);
+}
+
+bool TempScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
+  SD = &getAnalysis<ScopDetection>();
+
+  if (!SD->isMaxRegionInScop(*R))
+    return false;
+
+  Function *F = R->getEntry()->getParent();
+  SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  AA = &getAnalysis<AliasAnalysis>();
+  TD = &F->getParent()->getDataLayout();
+  ZeroOffset = SE->getConstant(TD->getIntPtrType(F->getContext()), 0);
+
+  assert(!TempScopOfRegion && "Build the TempScop only once");
+  TempScopOfRegion = buildTempScop(*R);
+
+  return false;
+}
+
+void TempScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequiredTransitive<LoopInfoWrapperPass>();
+  AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
+  AU.addRequiredTransitive<ScopDetection>();
+  AU.addRequiredID(IndependentBlocksID);
+  AU.addRequired<AliasAnalysis>();
+  AU.setPreservesAll();
+}
+
+TempScopInfo::~TempScopInfo() { clear(); }
+
+void TempScopInfo::clear() {
+  AccFuncMap.clear();
+  if (TempScopOfRegion)
+    delete TempScopOfRegion;
+  TempScopOfRegion = nullptr;
+}
+
+//===----------------------------------------------------------------------===//
+// TempScop information extraction pass implement
+char TempScopInfo::ID = 0;
+
+Pass *polly::createTempScopInfoPass() { return new TempScopInfo(); }
+
+INITIALIZE_PASS_BEGIN(TempScopInfo, "polly-analyze-ir",
+                      "Polly - Analyse the LLVM-IR in the detected regions",
+                      false, false);
+INITIALIZE_AG_DEPENDENCY(AliasAnalysis);
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
+INITIALIZE_PASS_END(TempScopInfo, "polly-analyze-ir",
+                    "Polly - Analyse the LLVM-IR in the detected regions",
+                    false, false)
+
 //===----------------------------------------------------------------------===//
 ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
   ctx = isl_ctx_alloc();
   isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
 }
 
 ScopInfo::~ScopInfo() {
   clear();

lib/CMakeLists.txt

 
 add_polly_library(Polly
   Analysis/DependenceInfo.cpp
   Analysis/ScopDetection.cpp
   Analysis/ScopDetectionDiagnostic.cpp
   Analysis/ScopInfo.cpp
   Analysis/ScopGraphPrinter.cpp
   Analysis/ScopPass.cpp
-  Analysis/TempScopInfo.cpp
   CodeGen/BlockGenerators.cpp
   ${ISL_CODEGEN_FILES}
   CodeGen/LoopGenerators.cpp
   CodeGen/IRBuilder.cpp
   CodeGen/Utils.cpp
   CodeGen/RuntimeDebugBuilder.cpp
   ${GPGPU_CODEGEN_FILES}
   Exchange/JSONExporter.cpp

lib/CodeGen/CodeGeneration.cpp

 
 #include "polly/CodeGen/IslNodeBuilder.h"
 #include "polly/CodeGen/IslAst.h"
 #include "polly/CodeGen/Utils.h"
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/ScopHelper.h"
-#include "polly/TempScopInfo.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Analysis/PostDominators.h"
 
 using namespace polly;
 using namespace llvm;
 

lib/CodeGen/IslNodeBuilder.cpp

 #include "polly/CodeGen/Utils.h"
 #include "polly/Config/config.h"
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
-#include "polly/TempScopInfo.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/CommandLine.h"

lib/Support/RegisterPasses.cpp

 #include "polly/RegisterPasses.h"
 #include "polly/Canonicalization.h"
 #include "polly/CodeGen/CodeGeneration.h"
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopDetection.h"
 #include "polly/ScopInfo.h"
-#include "polly/TempScopInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Vectorize.h"
 
 using namespace llvm;
 using namespace polly;