[Polly][ScopBuilder] Pass ScopStmts around instead of BasicBlocks. NFC.

[Meinersbur]

Summary

During the construction of MemoryAccesses in ScopBuilder, BasicBlocks were used in function parameters, assuming that the ScopStmt an be directly derived from it. This won't be true anymore once we split BasicBlocks into multiple ScopStmt. As a preparation for such a change in the future, we instead pass the ScopStmt and avoid the use of getStmtFor().

There are three occasions where a kind of mapping from BasicBlock to ScopStmt is still required.

1. Initial enumeration all statements to create their MemoryAccesses. This uses getStmtsFor which returns a list of statement or getStmtFor for regions statements.

Using this could be avoided by just iterating linearly over all ScopStmts. This unfortunately changes the order of MemoryAccesses, which in turn would require changing a lot of regression tests.

2. Get the statement representing the incoming block of a PHINode using getLastStmtOf.

3. One statement is required to write a scalar to be readable by those which need it. This is most often the statement which contains its definition, which we get using getStmtFor(Instruction*).

[grosser]

LGTM.

[nandini12396]

This is amazing, Sir!

lib/Analysis/ScopBuilder.cpp

668 ↗

(On Diff #103112)

Can you please explain this to me?

[Meinersbur]

lib/Analysis/ScopBuilder.cpp

668 ↗

(On Diff #103112)

The exit block is the one executed after the SCoP. It formally does not belong to the SCoP, but can have PHI nodes in it that need to be handled (MemoryAccesses to be added).

Because it does not belong to the SCoP, there is not ScopStmt for it, i.e. Stmt is nullptr. It is the only reason why Stmt could be nullptr, everything else in the SCoP should have a ScopStmt representing it.

polly/trunk/include/polly/ScopBuilder.h

class ScopBuilder {
 
   /// Valid Regions for Scop
   ScopDetection &SD;
 
   /// The ScalarEvolution to help building Scop.
   ScalarEvolution &SE;
 
   /// Set of instructions that might read any memory location.
-  SmallVector<Instruction *, 16> GlobalReads;
+  SmallVector<std::pair<ScopStmt *, Instruction *>, 16> GlobalReads;
 
   /// Set of all accessed array base pointers.
   SmallSetVector<Value *, 16> ArrayBasePointers;
 
   // The Scop
   std::unique_ptr<Scop> scop;
 
   // Methods for pattern matching against Fortran code generated by dragonegg.
class ScopBuilder {
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param Stmt       The parent statement of the instruction
   void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Analyze and extract the cross-BB scalar dependences (or, dataflow
   /// dependencies) of an instruction.
   ///
-  /// @param Inst    The instruction to be analyzed.
-  void buildScalarDependences(Instruction *Inst);
+  /// @param UserStmt The statement @p Inst resides in.
+  /// @param Inst     The instruction to be analyzed.
+  void buildScalarDependences(ScopStmt *UserStmt, Instruction *Inst);
 
   /// Build the escaping dependences for @p Inst.
   ///
   /// Search for uses of the llvm::Value defined by @p Inst that are not
   /// within the SCoP. If there is such use, add a SCALAR WRITE such that
   /// it is available after the SCoP as escaping value.
   ///
   /// @param Inst The instruction to be analyzed.
   void buildEscapingDependences(Instruction *Inst);
 
   /// Create MemoryAccesses for the given PHI node in the given region.
   ///
+  /// @param PHIStmt            The statement @p PHI resides in.
   /// @param PHI                The PHI node to be handled
   /// @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 *NonAffineSubRegion,
-                        bool IsExitBlock = false);
+  void buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
+                        Region *NonAffineSubRegion, bool IsExitBlock = false);
 
   /// Build the access functions for the subregion @p SR.
-  ///
-  /// @param SR           A subregion of @p R.
-  /// @param InsnToMemAcc The Instruction to MemoryAccess mapping.
-  void buildAccessFunctions(Region &SR);
+  void buildAccessFunctions();
 
   /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
   ///
   /// @param SR A subregion of @p R.
   ///
   /// Some of the statements might be optimized away later when they do not
   /// access any memory and thus have no effect.
   void buildStmts(Region &SR);
 
-  /// Build the access functions for the basic block @p BB.
+  /// Build the access functions for the basic block @p BB in or represented by
+  /// @p Stmt.
   ///
+  /// @param Stmt               Statement to add MemoryAccesses to.
   /// @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(BasicBlock &BB,
+  void buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
                             Region *NonAffineSubRegion = nullptr,
                             bool IsExitBlock = false);
 
   /// Create a new MemoryAccess object and add it to #AccFuncMap.
   ///
-  /// @param BB          The block where the access takes place.
+  /// @param Stmt        The statement where the access takes place.
   /// @param Inst        The instruction doing the access. It is not necessarily
   ///                    inside @p BB.
   /// @param AccType     The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemType    The type of the accessed array elements.
   /// @param Affine      Whether all subscripts are affine expressions.
   /// @param AccessValue Value read or written.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array dimension's sizes.
   /// @param Kind        The kind of memory accessed.
   ///
   /// @return The created MemoryAccess, or nullptr if the access is not within
   ///         the SCoP.
-  MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst,
+  MemoryAccess *addMemoryAccess(ScopStmt *Stmt, Instruction *Inst,
                                 MemoryAccess::AccessType AccType,
                                 Value *BaseAddress, Type *ElemType, bool Affine,
                                 Value *AccessValue,
                                 ArrayRef<const SCEV *> Subscripts,
                                 ArrayRef<const SCEV *> Sizes, MemoryKind Kind);
 
   /// Create a MemoryAccess that represents either a LoadInst or
   /// StoreInst.
   ///
+  /// @param Stmt        The statement to add the MemoryAccess to.
   /// @param MemAccInst  The LoadInst or StoreInst.
   /// @param AccType     The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemType    The type of the accessed array elements.
   /// @param IsAffine    Whether all subscripts are affine expressions.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array dimension's sizes.
   /// @param AccessValue Value read or written.
   ///
   /// @see MemoryKind
-  void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType AccType,
-                      Value *BaseAddress, Type *ElemType, bool IsAffine,
+  void addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,
+                      MemoryAccess::AccessType AccType, Value *BaseAddress,
+                      Type *ElemType, bool IsAffine,
                       ArrayRef<const SCEV *> Subscripts,
                       ArrayRef<const SCEV *> Sizes, Value *AccessValue);
 
   /// Create a MemoryAccess for writing an llvm::Instruction.
   ///
   /// The access will be created at the position of @p Inst.
   ///
   /// @param Inst The instruction to be written.
   ///
   /// @see ensureValueRead()
   /// @see MemoryKind
   void ensureValueWrite(Instruction *Inst);
 
   /// Ensure an llvm::Value is available in the BB's statement, creating a
   /// MemoryAccess for reloading it if necessary.
   ///
-  /// @param V      The value expected to be loaded.
-  /// @param UserBB Where to reload the value.
+  /// @param V        The value expected to be loaded.
+  /// @param UserStmt Where to reload the value.
   ///
   /// @see ensureValueStore()
   /// @see MemoryKind
-  void ensureValueRead(Value *V, BasicBlock *UserBB);
+  void ensureValueRead(Value *V, ScopStmt *UserStmt);
 
   /// Create a write MemoryAccess for the incoming block of a phi node.
   ///
   /// Each of the incoming blocks write their incoming value to be picked in the
   /// phi's block.
   ///
   /// @param PHI           PHINode under consideration.
+  /// @param IncomingStmt  The statement to add the MemoryAccess to.
   /// @param IncomingBlock Some predecessor block.
   /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
   /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
   ///                      .phiops one. Required for values escaping through a
   ///                      PHINode in the SCoP region's exit block.
   /// @see addPHIReadAccess()
   /// @see MemoryKind
-  void ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
-                      Value *IncomingValue, bool IsExitBlock);
+  void ensurePHIWrite(PHINode *PHI, ScopStmt *IncomintStmt,
+                      BasicBlock *IncomingBlock, Value *IncomingValue,
+                      bool IsExitBlock);
 
   /// Create a MemoryAccess for reading the value of a phi.
   ///
   /// The modeling assumes that all incoming blocks write their incoming value
   /// to the same location. Thus, this access will read the incoming block's
   /// value as instructed by this @p PHI.
   ///
-  /// @param PHI PHINode under consideration; the READ access will be added
-  /// here.
+  /// @param PHIStmt Statement @p PHI resides in.
+  /// @param PHI     PHINode under consideration; the READ access will be added
+  ///                here.
   ///
   /// @see ensurePHIWrite()
   /// @see MemoryKind
-  void addPHIReadAccess(PHINode *PHI);
+  void addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI);
 
 public:
   explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
                        const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
                        ScopDetection &SD, ScalarEvolution &SE);
   ~ScopBuilder() {}
 
   /// Try to build the Polly IR of static control part on the current

polly/trunk/include/polly/ScopInfo.h

public:
   bool contains(BasicBlock *BB) const {
     if (isCopyStmt())
       return false;
     if (isBlockStmt())
       return BB == getBasicBlock();
     return getRegion()->contains(BB);
   }
 
+  /// Return whether this statement contains @p Inst.
+  bool contains(Instruction *Inst) const {
+    if (!Inst)
+      return false;
+    return contains(Inst->getParent());
+  }
+
   /// Return the closest innermost loop that contains this statement, but is not
   /// contained in it.
   ///
   /// For block statement, this is just the loop that contains the block. Region
   /// statements can contain boxed loops, so getting the loop of one of the
   /// region's BBs might return such an inner loop. For instance, the region's
   /// entry could be a header of a loop, but the region might extend to BBs
   /// after the loop exit. Similarly, the region might only contain parts of the
public:
 
   /// Get an isl string representing the invalid context.
   std::string getInvalidContextStr() const;
 
   /// Return the ScopStmt for the given @p BB or nullptr if there is
   ///        none.
   ScopStmt *getStmtFor(BasicBlock *BB) const;
 
+  /// Return the last statement representing @p BB.
+  ///
+  /// Of the sequence of statements that represent a @p BB, this is the last one
+  /// to be executed. It is typically used to determine which instruction to add
+  /// a MemoryKind::PHI WRITE to. For this purpose, it is not strictly required
+  /// to be executed last, only that the incoming value is available in it.
+  ScopStmt *getLastStmtFor(BasicBlock *BB) const { return getStmtFor(BB); }
+
   /// Return the ScopStmt that represents the Region @p R, or nullptr if
   ///        it is not represented by any statement in this Scop.
   ScopStmt *getStmtFor(Region *R) const;
 
   /// Return the ScopStmt that represents @p RN; can return nullptr if
   ///        the RegionNode is not within the SCoP or has been removed due to
   ///        simplifications.
   ScopStmt *getStmtFor(RegionNode *RN) const;

polly/trunk/lib/Analysis/ScopBuilder.cpp

static cl::opt<bool> UnprofitableScalarAccs(
     cl::desc("Count statements with scalar accesses as not optimizable"),
     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool> DetectFortranArrays(
     "polly-detect-fortran-arrays",
     cl::desc("Detect Fortran arrays and use this for code generation"),
     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
-void ScopBuilder::buildPHIAccesses(PHINode *PHI, Region *NonAffineSubRegion,
+void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
+                                   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.
   auto *Scope = LI.getLoopFor(PHI->getParent());
   if (!IsExitBlock && canSynthesize(PHI, *scop, &SE, Scope))
     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);
+    ScopStmt *OpStmt = scop->getLastStmtFor(OpBB);
 
     // Do not build PHI dependences inside a non-affine subregion, but make
     // sure that the necessary scalar values are still made available.
     if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) {
       auto *OpInst = dyn_cast<Instruction>(Op);
       if (!OpInst || !NonAffineSubRegion->contains(OpInst))
-        ensureValueRead(Op, OpBB);
+        ensureValueRead(Op, OpStmt);
       continue;
     }
 
     OnlyNonAffineSubRegionOperands = false;
-    ensurePHIWrite(PHI, OpBB, Op, IsExitBlock);
+    ensurePHIWrite(PHI, OpStmt, OpBB, Op, IsExitBlock);
   }
 
   if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
-    addPHIReadAccess(PHI);
+    addPHIReadAccess(PHIStmt, PHI);
   }
 }
 
-void ScopBuilder::buildScalarDependences(Instruction *Inst) {
+void ScopBuilder::buildScalarDependences(ScopStmt *UserStmt,
+                                         Instruction *Inst) {
   assert(!isa<PHINode>(Inst));
 
   // Pull-in required operands.
   for (Use &Op : Inst->operands())
-    ensureValueRead(Op.get(), Inst->getParent());
+    ensureValueRead(Op.get(), UserStmt);
 }
 
 void ScopBuilder::buildEscapingDependences(Instruction *Inst) {
   // Check for uses of this instruction outside the scop. Because we do not
   // iterate over such instructions and therefore did not "ensure" the existence
   // of a write, we must determine such use here.
   for (Use &U : Inst->uses()) {
     Instruction *UI = dyn_cast<Instruction>(U.getUser());
if (Sizes.empty())
     return false;
 
   SizesSCEV.push_back(nullptr);
 
   for (auto V : Sizes)
     SizesSCEV.push_back(SE.getSCEV(
         ConstantInt::get(IntegerType::getInt64Ty(BasePtr->getContext()), V)));
 
-  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
-                 Subscripts, SizesSCEV, Val);
+  addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
+                 true, Subscripts, SizesSCEV, Val);
   return true;
 }
 
 bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
   if (!PollyDelinearize)
     return false;
 
   Value *Address = Inst.getPointerOperand();
bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) {
   //
   // TODO: Handle delinearization with differing element sizes.
   auto DelinearizedSize =
       cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
   Sizes.pop_back();
   if (ElementSize != DelinearizedSize)
     scop->invalidate(DELINEARIZATION, Inst->getDebugLoc());
 
-  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, true,
-                 AccItr->second.DelinearizedSubscripts, Sizes, Val);
+  addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
+                 true, AccItr->second.DelinearizedSubscripts, Sizes, Val);
   return true;
 }
 
 bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
   auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst);
 
   if (MemIntr == nullptr)
     return false;
bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) {
   //          isl_set_complement(isl_set_params(getDomain()))
   //       as we know it would be undefined to execute this instruction anyway.
   if (DestAccFunc->isZero())
     return true;
 
   auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(DestAccFunc));
   assert(DestPtrSCEV);
   DestAccFunc = SE.getMinusSCEV(DestAccFunc, DestPtrSCEV);
-  addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
+  addArrayAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(DestPtrVal->getContext()),
                  LengthIsAffine, {DestAccFunc, LengthVal}, {nullptr},
                  Inst.getValueOperand());
 
   auto *MemTrans = dyn_cast<MemTransferInst>(MemIntr);
   if (!MemTrans)
     return true;
 
   auto *SrcPtrVal = MemTrans->getSource();
   assert(SrcPtrVal);
 
   auto *SrcAccFunc = SE.getSCEVAtScope(SrcPtrVal, L);
   assert(SrcAccFunc);
   // Ignore accesses to "NULL".
   // TODO: See above TODO
   if (SrcAccFunc->isZero())
     return true;
 
   auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE.getPointerBase(SrcAccFunc));
   assert(SrcPtrSCEV);
   SrcAccFunc = SE.getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
-  addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
+  addArrayAccess(Stmt, Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(SrcPtrVal->getContext()),
                  LengthIsAffine, {SrcAccFunc, LengthVal}, {nullptr},
                  Inst.getValueOperand());
 
   return true;
 }
 
 bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) {
case FMRB_UnknownModRefBehavior:
     llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
   case FMRB_DoesNotAccessMemory:
     return true;
   case FMRB_DoesNotReadMemory:
   case FMRB_OnlyAccessesInaccessibleMem:
   case FMRB_OnlyAccessesInaccessibleOrArgMem:
     return false;
   case FMRB_OnlyReadsMemory:
-    GlobalReads.push_back(CI);
+    GlobalReads.emplace_back(Stmt, CI);
     return true;
   case FMRB_OnlyReadsArgumentPointees:
     ReadOnly = true;
   // Fall through
   case FMRB_OnlyAccessesArgumentPointees:
     auto AccType = ReadOnly ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;
     Loop *L = LI.getLoopFor(Inst->getParent());
     for (const auto &Arg : CI->arg_operands()) {
       if (!Arg->getType()->isPointerTy())
         continue;
 
       auto *ArgSCEV = SE.getSCEVAtScope(Arg, L);
       if (ArgSCEV->isZero())
         continue;
 
       auto *ArgBasePtr = cast<SCEVUnknown>(SE.getPointerBase(ArgSCEV));
-      addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
+      addArrayAccess(Stmt, Inst, AccType, ArgBasePtr->getValue(),
                      ArgBasePtr->getType(), false, {AF}, {nullptr}, CI);
     }
     return true;
   }
 
   return true;
 }
 
void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) {
   const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads();
   for (LoadInst *LInst : AccessILS)
     if (!ScopRIL.count(LInst))
       IsAffine = false;
 
   if (!IsAffine && AccType == MemoryAccess::MUST_WRITE)
     AccType = MemoryAccess::MAY_WRITE;
 
-  addArrayAccess(Inst, AccType, BasePointer->getValue(), ElementType, IsAffine,
-                 {AccessFunction}, {nullptr}, Val);
+  addArrayAccess(Stmt, Inst, AccType, BasePointer->getValue(), ElementType,
+                 IsAffine, {AccessFunction}, {nullptr}, Val);
 }
 
 void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) {
 
   if (buildAccessMemIntrinsic(Inst, Stmt))
     return;
 
   if (buildAccessCallInst(Inst, Stmt))
     return;
 
   if (buildAccessMultiDimFixed(Inst, Stmt))
     return;
 
   if (buildAccessMultiDimParam(Inst, Stmt))
     return;
 
   buildAccessSingleDim(Inst, Stmt);
 }
 
-void ScopBuilder::buildAccessFunctions(Region &SR) {
-
-  if (scop->isNonAffineSubRegion(&SR)) {
-    for (BasicBlock *BB : SR.blocks())
-      buildAccessFunctions(*BB, &SR);
-    return;
+void ScopBuilder::buildAccessFunctions() {
+  for (auto &Stmt : *scop) {
+    if (Stmt.isBlockStmt()) {
+      buildAccessFunctions(&Stmt, *Stmt.getBasicBlock());
+      continue;
     }
 
-  for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
-    if (I->isSubRegion())
-      buildAccessFunctions(*I->getNodeAs<Region>());
-    else
-      buildAccessFunctions(*I->getNodeAs<BasicBlock>());
+    Region *R = Stmt.getRegion();
+    for (BasicBlock *BB : R->blocks())
+      buildAccessFunctions(&Stmt, *BB, R);
+  }
 }
 
 void ScopBuilder::buildStmts(Region &SR) {
-
   if (scop->isNonAffineSubRegion(&SR)) {
     Loop *SurroundingLoop = LI.getLoopFor(SR.getEntry());
     auto &BoxedLoops = scop->getBoxedLoops();
     while (BoxedLoops.count(SurroundingLoop))
       SurroundingLoop = SurroundingLoop->getParentLoop();
     scop->addScopStmt(&SR, SurroundingLoop);
     return;
   }
else {
           Instructions.push_back(&Inst);
       }
       Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs<BasicBlock>());
       scop->addScopStmt(I->getNodeAs<BasicBlock>(), SurroundingLoop,
                         Instructions);
     }
 }
 
-void ScopBuilder::buildAccessFunctions(BasicBlock &BB,
+void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
                                        Region *NonAffineSubRegion,
                                        bool IsExitBlock) {
+  assert(
+      !Stmt == IsExitBlock &&
+      "The exit BB is the only one that cannot be represented by a statement");
+  assert(IsExitBlock || Stmt->contains(&BB));
+
   // We do not build access functions for error blocks, as they may contain
   // instructions we can not model.
   if (isErrorBlock(BB, scop->getRegion(), LI, DT) && !IsExitBlock)
     return;
 
-  ScopStmt *Stmt = scop->getStmtFor(&BB);
-
   for (Instruction &Inst : BB) {
     PHINode *PHI = dyn_cast<PHINode>(&Inst);
     if (PHI)
-      buildPHIAccesses(PHI, NonAffineSubRegion, IsExitBlock);
+      buildPHIAccesses(Stmt, PHI, NonAffineSubRegion, IsExitBlock);
 
     // For the exit block we stop modeling after the last PHI node.
     if (!PHI && IsExitBlock)
       break;
 
     if (auto MemInst = MemAccInst::dyn_cast(Inst)) {
       assert(Stmt && "Cannot build access function in non-existing statement");
       buildMemoryAccess(MemInst, Stmt);
     }
 
     if (isIgnoredIntrinsic(&Inst))
       continue;
 
     // PHI nodes have already been modeled above and TerminatorInsts that are
     // not part of a non-affine subregion are fully modeled and regenerated
     // from the polyhedral domains. Hence, they do not need to be modeled as
     // explicit data dependences.
     if (!PHI && (!isa<TerminatorInst>(&Inst) || NonAffineSubRegion))
-      buildScalarDependences(&Inst);
+      buildScalarDependences(Stmt, &Inst);
 
     if (!IsExitBlock)
       buildEscapingDependences(&Inst);
   }
 }
 
 MemoryAccess *ScopBuilder::addMemoryAccess(
-    BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType AccType,
+    ScopStmt *Stmt, Instruction *Inst, MemoryAccess::AccessType AccType,
     Value *BaseAddress, Type *ElementType, bool Affine, Value *AccessValue,
     ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
     MemoryKind Kind) {
-  ScopStmt *Stmt = scop->getStmtFor(BB);
-
-  // Do not create a memory access for anything not in the SCoP. It would be
-  // ignored anyway.
-  if (!Stmt)
-    return nullptr;
-
   bool isKnownMustAccess = false;
 
   // Accesses in single-basic block statements are always executed.
   if (Stmt->isBlockStmt())
     isKnownMustAccess = true;
 
   if (Stmt->isRegionStmt()) {
     // Accesses that dominate the exit block of a non-affine region are always
     // executed. In non-affine regions there may exist MemoryKind::Values that
     // do not dominate the exit. MemoryKind::Values will always dominate the
     // exit and MemoryKind::PHIs only if there is at most one PHI_WRITE in the
     // non-affine region.
-    if (DT.dominates(BB, Stmt->getRegion()->getExit()))
+    if (Inst && DT.dominates(Inst->getParent(), Stmt->getRegion()->getExit()))
       isKnownMustAccess = true;
   }
 
   // Non-affine PHI writes do not "happen" at a particular instruction, but
   // after exiting the statement. Therefore they are guaranteed to execute and
   // overwrite the old value.
   if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI)
     isKnownMustAccess = true;
 
   if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
     AccType = MemoryAccess::MAY_WRITE;
 
   auto *Access = new MemoryAccess(Stmt, Inst, AccType, BaseAddress, ElementType,
                                   Affine, Subscripts, Sizes, AccessValue, Kind);
 
   scop->addAccessFunction(Access);
   Stmt->addAccess(Access);
   return Access;
 }
 
-void ScopBuilder::addArrayAccess(
-    MemAccInst MemAccInst, MemoryAccess::AccessType AccType, Value *BaseAddress,
-    Type *ElementType, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
-    ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
+void ScopBuilder::addArrayAccess(ScopStmt *Stmt, MemAccInst MemAccInst,
+                                 MemoryAccess::AccessType AccType,
+                                 Value *BaseAddress, Type *ElementType,
+                                 bool IsAffine,
+                                 ArrayRef<const SCEV *> Subscripts,
+                                 ArrayRef<const SCEV *> Sizes,
+                                 Value *AccessValue) {
   ArrayBasePointers.insert(BaseAddress);
-  auto *MemAccess = addMemoryAccess(
-      MemAccInst->getParent(), MemAccInst, AccType, BaseAddress, ElementType,
-      IsAffine, AccessValue, Subscripts, Sizes, MemoryKind::Array);
+  auto *MemAccess = addMemoryAccess(Stmt, MemAccInst, AccType, BaseAddress,
+                                    ElementType, IsAffine, AccessValue,
+                                    Subscripts, Sizes, MemoryKind::Array);
 
   if (!DetectFortranArrays)
     return;
 
   if (Value *FAD = findFADAllocationInvisible(MemAccInst))
     MemAccess->setFortranArrayDescriptor(FAD);
   else if (Value *FAD = findFADAllocationVisible(MemAccInst))
     MemAccess->setFortranArrayDescriptor(FAD);
 }
 
 void ScopBuilder::ensureValueWrite(Instruction *Inst) {
+  // Find the statement that defines the value of Inst. That statement has to
+  // write the value to make it available to those statements that read it.
   ScopStmt *Stmt = scop->getStmtFor(Inst);
 
+  // It is possible that the value is synthesizable within a loop (such that it
+  // is not part of any statement), but not after the loop (where you need the
+  // number of loop round-trips to synthesize it). In LCSSA-form a PHI node will
+  // avoid this. In case the IR has no such PHI, use the last statement (where
+  // the value is synthesizable) to write the value.
+  if (!Stmt)
+    Stmt = scop->getLastStmtFor(Inst->getParent());
+
   // Inst not defined within this SCoP.
   if (!Stmt)
     return;
 
   // Do not process further if the instruction is already written.
   if (Stmt->lookupValueWriteOf(Inst))
     return;
 
-  addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
-                  Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
+  addMemoryAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, Inst, Inst->getType(),
+                  true, Inst, ArrayRef<const SCEV *>(),
                   ArrayRef<const SCEV *>(), MemoryKind::Value);
 }
 
-void ScopBuilder::ensureValueRead(Value *V, BasicBlock *UserBB) {
-  ScopStmt *UserStmt = scop->getStmtFor(UserBB);
-  auto *Scope = LI.getLoopFor(UserBB);
+void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) {
+  auto *Scope = UserStmt->getSurroundingLoop();
   auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false);
   switch (VUse.getKind()) {
   case VirtualUse::Constant:
   case VirtualUse::Block:
   case VirtualUse::Synthesizable:
   case VirtualUse::Hoisted:
   case VirtualUse::Intra:
     // Uses of these kinds do not need a MemoryAccess.
     break;
 
   case VirtualUse::ReadOnly:
     // Add MemoryAccess for invariant values only if requested.
     if (!ModelReadOnlyScalars)
       break;
 
     LLVM_FALLTHROUGH;
   case VirtualUse::Inter:
 
     // Do not create another MemoryAccess for reloading the value if one already
     // exists.
     if (UserStmt->lookupValueReadOf(V))
       break;
 
-    addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true,
-                    V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
+    addMemoryAccess(UserStmt, nullptr, MemoryAccess::READ, V, V->getType(),
+                    true, V, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                     MemoryKind::Value);
 
     // Inter-statement uses need to write the value in their defining statement.
     if (VUse.isInter())
       ensureValueWrite(cast<Instruction>(V));
     break;
   }
 }
 
-void ScopBuilder::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
+void ScopBuilder::ensurePHIWrite(PHINode *PHI, ScopStmt *IncomingStmt,
+                                 BasicBlock *IncomingBlock,
                                  Value *IncomingValue, bool IsExitBlock) {
   // As the incoming block might turn out to be an error statement ensure we
   // will create an exit PHI SAI object. It is needed during code generation
   // and would be created later anyway.
   if (IsExitBlock)
     scop->getOrCreateScopArrayInfo(PHI, PHI->getType(), {},
                                    MemoryKind::ExitPHI);
 
-  ScopStmt *IncomingStmt = scop->getStmtFor(IncomingBlock);
+  // This is possible if PHI is in the SCoP's entry block. The incoming blocks
+  // from outside the SCoP's region have no statement representation.
   if (!IncomingStmt)
     return;
 
   // Take care for the incoming value being available in the incoming block.
   // This must be done before the check for multiple PHI writes because multiple
   // exiting edges from subregion each can be the effective written value of the
   // subregion. As such, all of them must be made available in the subregion
   // statement.
-  ensureValueRead(IncomingValue, IncomingBlock);
+  ensureValueRead(IncomingValue, IncomingStmt);
 
   // Do not add more than one MemoryAccess per PHINode and ScopStmt.
   if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
     assert(Acc->getAccessInstruction() == PHI);
     Acc->addIncoming(IncomingBlock, IncomingValue);
     return;
   }
 
-  MemoryAccess *Acc =
-      addMemoryAccess(IncomingStmt->getEntryBlock(), PHI,
-                      MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true, PHI,
-                      ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                      IsExitBlock ? MemoryKind::ExitPHI : MemoryKind::PHI);
+  MemoryAccess *Acc = addMemoryAccess(
+      IncomingStmt, PHI, MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true,
+      PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
   assert(Acc);
   Acc->addIncoming(IncomingBlock, IncomingValue);
 }
 
-void ScopBuilder::addPHIReadAccess(PHINode *PHI) {
-  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
-                  PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
-                  ArrayRef<const SCEV *>(), MemoryKind::PHI);
+void ScopBuilder::addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI) {
+  addMemoryAccess(PHIStmt, PHI, MemoryAccess::READ, PHI, PHI->getType(), true,
+                  PHI, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
+                  MemoryKind::PHI);
 }
 
 #ifndef NDEBUG
 static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {
   auto PhysUse = VirtualUse::create(S, Op, &LI, false);
   auto VirtUse = VirtualUse::create(S, Op, &LI, true);
   assert(PhysUse.getKind() == VirtUse.getKind());
 }
static void verifyUses(Scop *S, LoopInfo &LI, DominatorTree &DT) {
   }
 }
 #endif
 
 void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
   scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));
 
   buildStmts(R);
-  buildAccessFunctions(R);
+  buildAccessFunctions();
 
   // 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.isTopLevelRegion() && !scop->hasSingleExitEdge())
-    buildAccessFunctions(*R.getExit(), nullptr,
+    buildAccessFunctions(nullptr, *R.getExit(), nullptr,
                          /* IsExitBlock */ true);
 
   // Create memory accesses for global reads since all arrays are now known.
   auto *AF = SE.getConstant(IntegerType::getInt64Ty(SE.getContext()), 0);
-  for (auto *GlobalRead : GlobalReads)
+  for (auto GlobalReadPair : GlobalReads) {
+    ScopStmt *GlobalReadStmt = GlobalReadPair.first;
+    Instruction *GlobalRead = GlobalReadPair.second;
     for (auto *BP : ArrayBasePointers)
-      addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
-                     BP->getType(), false, {AF}, {nullptr}, GlobalRead);
+      addArrayAccess(GlobalReadStmt, MemAccInst(GlobalRead), MemoryAccess::READ,
+                     BP, BP->getType(), false, {AF}, {nullptr}, GlobalRead);
+  }
 
   scop->buildInvariantEquivalenceClasses();
 
   if (!scop->buildDomains(&R, DT, LI))
     return;
 
   scop->addUserAssumptions(AC, DT, LI);