[Polly][WIP] Remove the dimensions from the MemoryAccess

[jdoerfert]

Summary

We compute and store the dimensions of a delinearized array in
multiple places. To reduce that number the MemoryAccess will now
use the Sizes in the ScopArrayInfo object.

[Meinersbur]

This patch seems to do a bit more than just make MemoryAccess use the dimension sizes from ScopArrayInfo (e.g. making the global InsnToMemAcc a member field). Those should be described in the commit message and/or put into different patches.

Accessing private members of DetectionContext from ScopInfo seems like a layer violation. DetectionContext is something ScopDetection uses internally and i.e. maybe shouldn't be exposed to other classes.

Otherwise some really good changes++

include/polly/ScopInfo.h

1124

Parameter description

lib/Analysis/ScopInfo.cpp

1514

auto not necessary

3174

I am really glad that this global variable goes away

3283

++

test/ScopInfo/delinearize-together-all-data-refs.ll

14

Can you explain why this changes? The commit message makes the impression that it is an internal reorganization only.

[Meinersbur]

Sorry, I just noticed the WIP tag.

[grosser]

Hi Johannes,

this is a small and very targeted patch that seems to never have been moved out of WIP stage. I recently improved the printing of memory references so parts of this patch may already be integrated, but some parts are probably still very useful. Hence, I wonder if you planned to move this patch out of the WIP stage and propose it for review?

[grosser]

Hi Johannes,

as I did not receive a reply on this patch, it seems to not be of interest at the moment. To clean up my patch review log I remove myself as a reviewer. Feel free to add me again when you have time to get back to this.

Best,
Tobias

include/polly/ScopDetection.h

struct MemAcc {
   // Subscripts computed by delinearization.
   SmallVector<const SCEV *, 4> DelinearizedSubscripts;
 
   MemAcc(const Instruction *I, std::shared_ptr<ArrayShape> S)
       : Insn(I), Shape(S), DelinearizedSubscripts() {}
 };
 
 typedef std::map<const Instruction *, MemAcc> MapInsnToMemAcc;
-typedef std::pair<const Instruction *, const SCEV *> PairInstSCEV;
+typedef std::pair<WeakVH, const SCEV *> PairInstSCEV;
 typedef std::vector<PairInstSCEV> AFs;
 typedef std::map<const SCEVUnknown *, AFs> BaseToAFs;
 typedef std::map<const SCEVUnknown *, const SCEV *> BaseToElSize;
 
 extern bool PollyTrackFailures;
 extern bool PollyDelinearize;
 extern bool PollyUseRuntimeAliasChecks;
 extern bool PollyProcessUnprofitable;
struct DetectionContext {
 
     /// @brief The set of base pointers with non-affine accesses.
     ///
     /// This set contains all base pointers which are used in memory accesses
     /// that can not be detected as affine accesses.
     SetVector<const SCEVUnknown *> NonAffineAccesses;
     BaseToElSize ElementSize;
 
+    MapInsnToMemAcc InsnToMemAcc;
+
     /// @brief The region has at least one load instruction.
     bool hasLoads;
 
     /// @brief The region has at least one store instruction.
     bool hasStores;
 
     /// @brief The set of non-affine subregions in the region we analyze.
     NonAffineSubRegionSetTy NonAffineSubRegionSet;

include/polly/ScopInfo.h

 ///
 class ScopArrayInfo {
 public:
   /// @brief Construct a ScopArrayInfo object.
   ///
   /// @param BasePtr        The array base pointer.
   /// @param ElementType    The type of the elements stored in the array.
   /// @param IslCtx         The isl context used to create the base pointer id.
-  /// @param DimensionSizes A vector containing the size of each dimension.
   /// @param IsPHI          Is this a PHI node specific array info object.
   /// @param S              The scop this array object belongs to.
-  ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *IslCtx,
-                ArrayRef<const SCEV *> DimensionSizes, bool IsPHI, Scop *S);
+  ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *IslCtx, bool IsPHI,
+                Scop *S);
 
   ///  @brief Update the sizes of the ScopArrayInfo object.
   ///
   ///  A ScopArrayInfo object may with certain outer dimensions not being added
   ///  on the first creation. This function allows to update the sizes of the
   ///  ScopArrayInfo object by adding additional outer array dimensions.
   ///
   ///  @param A vector of array sizes where the rightmost array sizes need to
private:
   // TODO: It might be possible to move them to ScopArrayInfo.
   // @{
 
   /// @brief The base address (e.g., A for A[i+j]).
   AssertingVH<Value> BaseAddr;
 
   /// @brief An unique name of the accessed array.
   std::string BaseName;
-
-  /// @brief Size in bytes of a single array element.
-  unsigned ElemBytes;
-
-  /// @brief Size of each dimension of the accessed array.
-  SmallVector<const SCEV *, 4> Sizes;
   // @}
 
   // Properties describing the accessed element.
   // @{
 
   /// @brief The access instruction of this memory access.
   Instruction *AccessInstruction;
 
private:
 
   /// @brief Relation from statment instances to the accessed array elements.
   isl_map *AccessRelation;
 
   /// @brief Updated access relation read from JSCOP file.
   isl_map *NewAccessRelation;
   // @}
 
-  unsigned getElemSizeInBytes() const { return ElemBytes; }
-
   bool isAffine() const { return IsAffine; }
 
   /// @brief Is this MemoryAccess modeling special PHI node accesses?
   bool isPHI() const { return Origin == PHI; }
 
   __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement);
 
-  void assumeNoOutOfBound();
+  void assumeNoOutOfBound(const ScopArrayInfo *SAI);
 
   /// @brief Compute bounds on an over approximated  access relation.
   ///
   /// @param ElementSize The size of one element accessed.
   void computeBoundsOnAccessRelation(unsigned ElementSize);
 
   /// @brief Get the original access function as read from IR.
   __isl_give isl_map *getOriginalAccessRelation() const;
private:
   /// piecewise mapping pairwise from the rightmost to the leftmost access
   /// dimension. It would also be possible to cover a wider range by introducing
   /// more cases and adding multiple of Ns to these cases. However, this has
   /// not yet been necessary.
   /// The introduction of different cases necessarily complicates the memory
   /// access function, but cases that can be statically proven to not happen
   /// will be eliminated later on.
   __isl_give isl_map *foldAccess(__isl_take isl_map *AccessRelation,
-                                 ScopStmt *Statement);
+                                 ScopStmt *Statement, const ScopArrayInfo *SAI);
 
   /// @brief Assemble the access relation from all availbale information.
   ///
   /// In particular, used the information passes in the constructor and the
   /// parent ScopStmt set by setStatment().
   ///
   /// @param SAI Info object for the accessed array.
   void buildAccessRelation(const ScopArrayInfo *SAI);
 
 public:
   /// @brief Create a new MemoryAccess.
   ///
   /// @param Stmt       The parent statement.
   /// @param AccessInst The instruction doing the access.
   /// @param Id         Identifier that is guranteed to be unique within the
   ///                   same ScopStmt.
   /// @param BaseAddr   The accessed array's address.
-  /// @param ElemBytes  Number of accessed bytes.
   /// @param AccType    Whether read or write access.
   /// @param IsAffine   Whether the subscripts are affine expressions.
   /// @param Origin     What is the purpose of this access?
   /// @param Subscripts Subscipt expressions
-  /// @param Sizes      Dimension lengths of the accessed array.
   /// @param BaseName   Name of the acessed array.
   MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, __isl_take isl_id *Id,
-               AccessType Type, Value *BaseAddress, unsigned ElemBytes,
-               bool Affine, ArrayRef<const SCEV *> Subscripts,
-               ArrayRef<const SCEV *> Sizes, Value *AccessValue,
+               AccessType Type, Value *BaseAddress, bool Affine,
+               ArrayRef<const SCEV *> Subscripts, Value *AccessValue,
                AccessOrigin Origin, StringRef BaseName);
   ~MemoryAccess();
 
   /// @brief Get the type of a memory access.
   enum AccessType getType() { return AccType; }
 
   /// @brief Is this a reduction like access?
   bool isReductionLike() const { return RedType != RT_NONE; }
public:
   void setNewAccessRelation(__isl_take isl_map *NewAccessRelation);
 
   /// @brief Mark this a reduction like access
   void markAsReductionLike(ReductionType RT) { RedType = RT; }
 
   /// @brief Align the parameters in the access relation to the scop context
   void realignParams();
 
-  /// @brief Update the dimensionality of the memory access.
-  ///
-  /// During scop construction some memory accesses may not be constructed with
-  /// their full dimensionality, but outer dimensions that may have been omitted
-  /// if they took the value 'zero'. By updating the dimensionality of the
-  /// statement we add additional zero-valued dimensions to match the
-  /// dimensionality of the ScopArrayInfo object that belongs to this memory
-  /// access.
-  void updateDimensionality();
-
   /// @brief Get identifier for the memory access.
   ///
   /// This identifier is unique for all accesses that belong to the same scop
   /// statement.
   __isl_give isl_id *getId() const;
 
   /// @brief Print the MemoryAccess.
   ///
private:
   InvariantAccessesTy InvariantAccesses;
 
   /// @brief Scop constructor; invoked from ScopInfo::buildScop.
   Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD,
        ScalarEvolution &SE, DominatorTree &DT, LoopInfo &LI, isl_ctx *ctx,
        unsigned MaxLoopDepth);
 
   /// @brief Initialize this ScopInfo .
-  void init(AliasAnalysis &AA);
+  void
+  init(AliasAnalysis &AA,
+       DenseMap<const Instruction *, std::vector<const SCEV *>> &AccessSizes);
 
   /// @brief Add loop carried constraints to the header block of the loop @p L.
   ///
   /// @param L  The loop to process.
   void addLoopBoundsToHeaderDomain(Loop *L);
 
   /// @brief Compute the branching constraints for each basic block in @p R.
   ///
private:
   /// @brief Simplify the SCoP representation
   ///
   /// At the moment we perform the following simplifications:
   ///   - removal of no-op statements
   /// @param RemoveIgnoredStmts If true, also removed ignored statments.
   /// @see isIgnored()
   void simplifySCoP(bool RemoveIgnoredStmts);
 
+  /// @brief Create a new ScopArrayInfo object.
+  ///
+  /// @param BasePtr     The base pointer of the array.
+  /// @param ElementType The type of the elements stored in this array.
+  ScopArrayInfo *createScopArrayInfo(Value *BasePtr, Type *ElementType);
+
+  /// @brief Create the ScopArrayInfo objects for memory accesses in this SCoP.
+  void buildScopArrays(
+      DenseMap<const Instruction *, std::vector<const SCEV *>> &AccessSizes);
+
   /// @brief Hoist invariant memory loads and check for required ones.
   ///
   /// We first identify "common" invariant loads, thus loads that are invariant
   /// and can be hoisted. Then we check if all required invariant loads have
   /// been identified as (common) invariant. A load is a required invariant load
   /// if it was assumed to be invariant during SCoP detection, e.g., to assume
   /// loop bounds to be affine or runtime alias checks to be placeable. In case
   /// a required invariant load was not identified as (common) invariant we will
private:
   ///
   /// Either @p BB or @p R should be non-null. A new statement for the non-null
   /// argument will be created and added to the statement vector and map.
   ///
   /// @param BB         The basic block we build the statement for (or null)
   /// @param R          The region we build the statement for (or null).
   ScopStmt *addScopStmt(BasicBlock *BB, Region *R);
 
-  /// @param Update access dimensionalities.
-  ///
-  /// When detecting memory accesses different accesses to the same array may
-  /// have built with different dimensionality, as outer zero-values dimensions
-  /// may not have been recognized as separate dimensions. This function goes
-  /// again over all memory accesses and updates their dimensionality to match
-  /// the dimensionality of the underlying ScopArrayInfo object.
-  void updateAccessDimensionality();
-
   /// @brief Build Schedule and ScopStmts.
   ///
   /// @param R              The current region traversed.
   /// @param LoopSchedules  Map from loops to their schedule and progress.
   void buildSchedule(
       Region *R,
       DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> &LoopSchedules);
 
public:
 
   /// @brief Return the (possibly new) ScopArrayInfo object for @p Access.
   ///
   /// @param ElementType The type of the elements stored in this array.
   /// @param IsPHI       Is this ScopArrayInfo object modeling special
   ///                    PHI node storage.
   const ScopArrayInfo *getOrCreateScopArrayInfo(Value *BasePtr,
                                                 Type *ElementType,
-                                                ArrayRef<const SCEV *> Sizes,
                                                 bool IsPHI = false);
 
   /// @brief Return the cached ScopArrayInfo object for @p BasePtr.
   ///
   /// @param BasePtr The base pointer the object has been stored for
   /// @param IsPHI   Are we looking for special PHI storage.
   const ScopArrayInfo *getScopArrayInfo(Value *BasePtr, bool IsPHI = false);
 
class ScopInfo : public RegionPass {
   const DataLayout *TD;
 
   // Access function of statements (currently BasicBlocks) .
   //
   // This owns all the MemoryAccess objects of the Scop created in this pass. It
   // must live until #scop is deleted.
   AccFuncMapType AccFuncMap;
 
+  /// @brief Helper map to remember the delinearization shape of GEPs
+  ///
+  /// TODO: This should be unified with the rest of the delinearization.
+  DenseMap<const Instruction *, std::vector<const SCEV *>> AccessSizes;
+
   // The Scop
   Scop *scop;
   isl_ctx *ctx;
 
   /// @brief Return the SCoP region that is currently processed.
   Region *getRegion() const {
     if (!scop)
       return nullptr;
     return &scop->getRegion();
   }
 
   // Clear the context.
   void clear();
 
   // Build the SCoP for Region @p R.
   void buildScop(Region &R, DominatorTree &DT);
 
   /// @brief Build an instance of MemoryAccess 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 to build the data access dictionary.
-  /// @param BoxedLoops The set of loops that are overapproximated in @p R.
-  /// @param ScopRIL    The required invariant loads equivalence classes.
+  /// @param Inst The Load/Store instruction that access the memory
+  /// @param L    The parent loop of the instruction
+  /// @param R    The region on which to build the data access dictionary.
+  /// @param DC   The detection context for @p R.
   void buildMemoryAccess(Instruction *Inst, Loop *L, Region *R,
-                         const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
-                         const InvariantLoadsSetTy &ScopRIL);
+                         const ScopDetection::DetectionContext *DC);
 
   /// @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.
   ///
class ScopInfo : public RegionPass {
 
   /// @brief Create a new MemoryAccess object and add it to #AccFuncMap.
   ///
   /// @param BB          The block where the access takes place.
   /// @param Inst        The instruction doing the access. It is not necessarily
   ///                    inside @p BB.
   /// @param Type        The kind of access.
   /// @param BaseAddress The accessed array's base address.
-  /// @param ElemBytes   Size of accessed array element.
   /// @param Affine      Whether all subscripts are affine expressions.
   /// @param AccessValue Value read or written.
   /// @param Subscripts  Access subscripts per dimension.
-  /// @param Sizes       The array diminsion's sizes.
   /// @param Origin      Purpose of this access.
   void addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                        MemoryAccess::AccessType Type, Value *BaseAddress,
-                       unsigned ElemBytes, bool Affine, Value *AccessValue,
+                       bool Affine, Value *AccessValue,
                        ArrayRef<const SCEV *> Subscripts,
-                       ArrayRef<const SCEV *> Sizes,
                        MemoryAccess::AccessOrigin Origin);
 
   /// @brief Create a MemoryAccess that represents either a LoadInst or
   /// StoreInst.
   ///
   /// @param MemAccInst  The LoadInst or StoreInst.
   /// @param Type        The kind of access.
   /// @param BaseAddress The accessed array's base address.
-  /// @param ElemBytes   Size of accessed array element.
   /// @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 AccessOrigin
   void addExplicitAccess(Instruction *MemAccInst, MemoryAccess::AccessType Type,
-                         Value *BaseAddress, unsigned ElemBytes, bool IsAffine,
-                         ArrayRef<const SCEV *> Subscripts,
-                         ArrayRef<const SCEV *> Sizes, Value *AccessValue);
+                         Value *BaseAddress, bool IsAffine,
+                         ArrayRef<const SCEV *> Subscripts, Value *AccessValue);
 
   /// @brief Create a MemoryAccess for writing an llvm::Value.
   ///
   /// The access will be created at the @p Value's definition.
   ///
   /// @param Value The value to be written.
   /// @see addScalarReadAccess()
   /// @see AccessOrigin

lib/Analysis/ScopDetection.cpp

bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const {
 
   for (const Use &Operand : I->operands())
     if (!isInvariant(*Operand, Reg))
       return false;
 
   return true;
 }
 
-MapInsnToMemAcc InsnToMemAcc;
-
 bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
   for (const SCEVUnknown *BasePointer : Context.NonAffineAccesses) {
     Value *BaseValue = BasePointer->getValue();
     auto Shape = std::shared_ptr<ArrayShape>(new ArrayShape(BasePointer));
     bool BasePtrHasNonAffine = false;
 
for (const SCEVUnknown *BasePointer : Context.NonAffineAccesses) {
     SE->findArrayDimensions(Terms, Shape->DelinearizedSizes,
                             Context.ElementSize[BasePointer]);
 
     if (!AllowNonAffine)
       for (const SCEV *DelinearizedSize : Shape->DelinearizedSizes) {
         if (auto *Unknown = dyn_cast<SCEVUnknown>(DelinearizedSize)) {
           auto *value = dyn_cast<Value>(Unknown->getValue());
           if (isa<UndefValue>(value)) {
-            invalid<ReportDifferentArrayElementSize>(
-                Context, /*Assert=*/true,
-                Context.Accesses[BasePointer].front().first, BaseValue);
+            const Instruction *Insn =
+                cast<Instruction>(Context.Accesses[BasePointer].front().first);
+            invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true,
+                                                     Insn, BaseValue);
             return false;
           }
         }
-        if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion))
-          invalid<ReportNonAffineAccess>(
-              Context, /*Assert=*/true, DelinearizedSize,
-              Context.Accesses[BasePointer].front().first, BaseValue);
+        if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion)) {
+          const Instruction *Insn =
+              cast<Instruction>(Context.Accesses[BasePointer].front().first);
+          invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
+                                         DelinearizedSize, Insn, BaseValue);
+        }
       }
 
     // No array shape derived.
     if (Shape->DelinearizedSizes.empty()) {
       if (AllowNonAffine)
         continue;
 
       for (const auto &Pair : Context.Accesses[BasePointer]) {
-        const Instruction *Insn = Pair.first;
+        const Instruction *Insn = cast<Instruction>(Pair.first);
         const SCEV *AF = Pair.second;
 
         if (!isAffine(AF, Context, BaseValue)) {
           invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Insn,
                                          BaseValue);
           if (!KeepGoing)
             return false;
         }
       }
       continue;
     }
 
     // Third step: compute the access functions for each subscript.
     //
     // We first store the resulting memory accesses in TempMemoryAccesses. Only
     // if the access functions for all memory accesses have been successfully
     // delinearized we continue. Otherwise, we either report a failure or, if
     // non-affine accesses are allowed, we drop the information. In case the
     // information is dropped the memory accesses need to be overapproximated
     // when translated to a polyhedral representation.
     MapInsnToMemAcc TempMemoryAccesses;
     for (const auto &Pair : Context.Accesses[BasePointer]) {
-      const Instruction *Insn = Pair.first;
+      const Instruction *Insn = cast<Instruction>(Pair.first);
       auto *AF = Pair.second;
       bool IsNonAffine = false;
       TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape)));
       MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second;
 
       if (!AF) {
         if (isAffine(Pair.second, Context, BaseValue))
           Acc->DelinearizedSubscripts.push_back(Pair.second);
for (const auto &Pair : Context.Accesses[BasePointer]) {
           invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Pair.second,
                                          Insn, BaseValue);
         if (!KeepGoing && !AllowNonAffine)
           return false;
       }
     }
 
     if (!BasePtrHasNonAffine)
-      InsnToMemAcc.insert(TempMemoryAccesses.begin(), TempMemoryAccesses.end());
+      Context.InsnToMemAcc.insert(TempMemoryAccesses.begin(),
+                                  TempMemoryAccesses.end());
   }
   return true;
 }
 
 bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
                                         DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
 
   bool isVariantInNonAffineLoop = false;
   SetVector<const Loop *> Loops;
   findLoops(AccessFunction, Loops);
   for (const Loop *L : Loops)
     if (Context.BoxedLoopsSet.count(L))
       isVariantInNonAffineLoop = true;
 
-  if (PollyDelinearize && !isVariantInNonAffineLoop) {
-    Context.Accesses[BasePointer].push_back({&Inst, AccessFunction});
 
-    if (!isAffine(AccessFunction, Context, BaseValue))
+  if (isVariantInNonAffineLoop) {
+    if (AllowNonAffine)
       Context.NonAffineAccesses.insert(BasePointer);
-  } else if (!AllowNonAffine) {
-    if (isVariantInNonAffineLoop ||
-        !isAffine(AccessFunction, Context, BaseValue))
+    else
+      return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
+                                            AccessFunction, &Inst, BaseValue);
+  } else if (!isAffine(AccessFunction, Context, BaseValue)) {
+    if (AllowNonAffine || PollyDelinearize)
+      Context.NonAffineAccesses.insert(BasePointer);
+    else
       return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
                                             AccessFunction, &Inst, BaseValue);
   }
 
   // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions
   // created by IndependentBlocks Pass.
   if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BaseValue))
     return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
for (BasicBlock *BB : CurRegion.blocks()) {
 
     if (!isValidCFG(*BB, false, Context) && !KeepGoing)
       return false;
     for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
       if (!isValidInstruction(*I, Context) && !KeepGoing)
         return false;
   }
 
-  if (!hasAffineMemoryAccesses(Context))
-    return false;
+  if (PollyDelinearize)
+    return hasAffineMemoryAccesses(Context);
 
-  return true;
+  return AllowNonAffine || Context.NonAffineAccesses.empty();
 }
 
 bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
   DEBUG(dbgs() << "Checking region: " << CurRegion.getNameStr() << "\n\t");
 
   if (CurRegion.isTopLevelRegion()) {
for (const Region *R : ValidRegions)
     OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
 
   OS << "\n";
 }
 
 void ScopDetection::releaseMemory() {
   RejectLogs.clear();
   ValidRegions.clear();
-  InsnToMemAcc.clear();
   DetectionContextMap.clear();
 
   // Do not clear the invalid function set.
 }
 
 char ScopDetection::ID = 0;
 
 Pass *polly::createScopDetectionPass() { return new ScopDetection(); }

lib/Analysis/ScopInfo.cpp

static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {
   auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(OriginBaseSCEV);
   if (!OriginBaseSCEVUnknown)
     return nullptr;
 
   return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue());
 }
 
 ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *Ctx,
-                             ArrayRef<const SCEV *> Sizes, bool IsPHI, Scop *S)
+                             bool IsPHI, Scop *S)
     : BasePtr(BasePtr), ElementType(ElementType), IsPHI(IsPHI), S(*S) {
   std::string BasePtrName =
       getIslCompatibleName("MemRef_", BasePtr, IsPHI ? "__phi" : "");
   Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this);
 
-  updateSizes(Sizes);
   BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);
   if (BasePtrOriginSAI)
     const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this);
 }
 
 __isl_give isl_space *ScopArrayInfo::getSpace() const {
   auto Space =
       isl_space_set_alloc(isl_id_get_ctx(Id), 0, getNumberOfDimensions());
ScopArrayInfo::~ScopArrayInfo() {
   isl_id_free(Id);
   for (isl_pw_aff *Size : DimensionSizesPw)
     isl_pw_aff_free(Size);
 }
 
 std::string ScopArrayInfo::getName() const { return isl_id_get_name(Id); }
 
 int ScopArrayInfo::getElemSizeInBytes() const {
-  return ElementType->getPrimitiveSizeInBits() / 8;
+  const auto *DL = &S.getRegion().getEntry()->getModule()->getDataLayout();
+  return DL->getTypeAllocSize(ElementType);
 }
 
 isl_id *ScopArrayInfo::getBasePtrId() const { return isl_id_copy(Id); }
 
 void ScopArrayInfo::dump() const { print(errs()); }
 
 void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {
   OS.indent(8) << *getElementType() << " " << getName() << "[*]";
-  for (unsigned u = 0; u < getNumberOfDimensions(); u++) {
+  for (int u = 0, e = getNumberOfDimensions() - 1; u < e; u++) {
     OS << "[";
 
     if (SizeAsPwAff)
       OS << " " << DimensionSizesPw[u] << " ";
     else
       OS << *DimensionSizes[u];
 
     OS << "]";

 
 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 MemoryAccess::updateDimensionality() {
-  auto ArraySpace = getScopArrayInfo()->getSpace();
-  auto AccessSpace = isl_space_range(isl_map_get_space(AccessRelation));
-
-  auto DimsArray = isl_space_dim(ArraySpace, isl_dim_set);
-  auto DimsAccess = isl_space_dim(AccessSpace, isl_dim_set);
-  auto DimsMissing = DimsArray - DimsAccess;
-
-  auto Map = isl_map_from_domain_and_range(isl_set_universe(AccessSpace),
-                                           isl_set_universe(ArraySpace));
-
-  for (unsigned i = 0; i < DimsMissing; i++)
-    Map = isl_map_fix_si(Map, isl_dim_out, i, 0);
-
-  for (unsigned i = DimsMissing; i < DimsArray; i++)
-    Map = isl_map_equate(Map, isl_dim_in, i - DimsMissing, isl_dim_out, i);
-
-  AccessRelation = isl_map_apply_range(AccessRelation, Map);
-}
-
 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 "+";

 // then apply the reverse access relation to obtain the set of iterations that
 // may contain invalid accesses and reduce this set of iterations to the ones
 // that are actually executed by intersecting them with the domain of the
 // statement. If we now project out all loop dimensions, we obtain a set of
 // parameters that may cause statement instances to be executed that may
 // possibly yield out of bound memory accesses. The complement of these
 // constraints is the set of constraints that needs to be assumed to ensure such
 // statement instances are never executed.
-void MemoryAccess::assumeNoOutOfBound() {
+void MemoryAccess::assumeNoOutOfBound(const ScopArrayInfo *SAI) {
   isl_space *Space = isl_space_range(getOriginalAccessRelationSpace());
   isl_set *Outside = isl_set_empty(isl_space_copy(Space));
   for (int i = 1, Size = Subscripts.size(); i < Size; ++i) {
     isl_local_space *LS = isl_local_space_from_space(isl_space_copy(Space));
     isl_pw_aff *Var =
         isl_pw_aff_var_on_domain(isl_local_space_copy(LS), isl_dim_set, i);
     isl_pw_aff *Zero = isl_pw_aff_zero_on_domain(LS);
 
     isl_set *DimOutside;
 
     DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero);
-    isl_pw_aff *SizeE = Statement->getPwAff(Sizes[i - 1]);
+    isl_pw_aff *SizeE = Statement->getPwAff(SAI->getDimensionSize(i - 1));
 
     SizeE = isl_pw_aff_drop_dims(SizeE, isl_dim_in, 0,
                                  Statement->getNumIterators());
     SizeE = isl_pw_aff_add_dims(SizeE, isl_dim_in,
                                 isl_space_dim(Space, isl_dim_set));
     SizeE = isl_pw_aff_set_tuple_id(SizeE, isl_dim_in,
                                     isl_space_get_tuple_id(Space, isl_dim_set));
 
void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
 
   isl_set *AccessRange = isl_map_range(isl_map_copy(AccessRelation));
   AccessRange =
       addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0, isl_dim_set);
   AccessRelation = isl_map_intersect_range(AccessRelation, AccessRange);
 }
 
 __isl_give isl_map *MemoryAccess::foldAccess(__isl_take isl_map *AccessRelation,
-                                             ScopStmt *Statement) {
+                                             ScopStmt *Statement,
+                                             const ScopArrayInfo *SAI) {
   int Size = Subscripts.size();
 
   for (int i = Size - 2; i >= 0; --i) {
     isl_space *Space;
     isl_map *MapOne, *MapTwo;
-    isl_pw_aff *DimSize = Statement->getPwAff(Sizes[i]);
+    isl_pw_aff *DimSize = Statement->getPwAff(SAI->getDimensionSize(i));
 
     isl_space *SpaceSize = isl_pw_aff_get_space(DimSize);
     isl_pw_aff_free(DimSize);
     isl_id *ParamId = isl_space_get_dim_id(SpaceSize, isl_dim_param, 0);
 
     Space = isl_map_get_space(AccessRelation);
     Space = isl_space_map_from_set(isl_space_range(Space));
     Space = isl_space_align_params(Space, SpaceSize);
for (int i = Size - 2; i >= 0; --i) {
     AccessRelation = isl_map_apply_range(AccessRelation, MapOne);
   }
   return AccessRelation;
 }
 
 void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
   assert(!AccessRelation && "AccessReltation already built");
 
+  unsigned SAINumDim = SAI->getNumberOfDimensions();
+  if (isExplicit() && Subscripts.size() <= SAINumDim) {
+    while (Subscripts.size() < SAINumDim) {
+      ScalarEvolution *SE = Statement->getParent()->getSE();
+      auto *I64Ty = IntegerType::getInt64Ty(AccessValue->getContext());
+      auto *ZeroSCEV = SE->getConstant(I64Ty, 0);
+      Subscripts.insert(Subscripts.begin(), ZeroSCEV);
+    }
+  }
+
   isl_ctx *Ctx = isl_id_get_ctx(Id);
   isl_id *BaseAddrId = SAI->getBasePtrId();
 
   if (!isAffine()) {
     // We overapproximate non-affine accesses with a possible access to the
     // whole array. For read accesses it does not make a difference, if an
     // access must or may happen. However, for write accesses it is important to
     // differentiate between writes that must happen and writes that may happen.
     AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
     AccessRelation =
         isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
 
-    computeBoundsOnAccessRelation(getElemSizeInBytes());
+    computeBoundsOnAccessRelation(SAI->getElemSizeInBytes());
     return;
   }
 
   isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0);
   AccessRelation = isl_map_universe(Space);
 
   for (int i = 0, Size = Subscripts.size(); i < Size; ++i) {
     isl_pw_aff *Affine = Statement->getPwAff(Subscripts[i]);
 
     if (Size == 1) {
       // For the non delinearized arrays, divide the access function of the last
       // subscript by the size of the elements in the array.
       //
       // A stride one array access in C expressed as A[i] is expressed in
       // LLVM-IR as something like A[i * elementsize]. This hides the fact that
       // two subsequent values of 'i' index two values that are stored next to
       // each other in memory. By this division we make this characteristic
       // obvious again.
-      isl_val *v = isl_val_int_from_si(Ctx, getElemSizeInBytes());
+      isl_val *v = isl_val_int_from_si(Ctx, SAI->getElemSizeInBytes());
       Affine = isl_pw_aff_scale_down_val(Affine, v);
     }
 
     isl_map *SubscriptMap = isl_map_from_pw_aff(Affine);
 
     AccessRelation = isl_map_flat_range_product(AccessRelation, SubscriptMap);
   }
 
-  if (Sizes.size() > 1 && !isa<SCEVConstant>(Sizes[0]))
-    AccessRelation = foldAccess(AccessRelation, Statement);
+  if (SAINumDim > 1 && !isa<SCEVConstant>(SAI->getDimensionSize(0)))
+    AccessRelation = foldAccess(AccessRelation, Statement, SAI);
 
   Space = Statement->getDomainSpace();
   AccessRelation = isl_map_set_tuple_id(
       AccessRelation, isl_dim_in, isl_space_get_tuple_id(Space, isl_dim_set));
   AccessRelation =
       isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
 
-  assumeNoOutOfBound();
+  assumeNoOutOfBound(SAI);
   AccessRelation = isl_map_gist_domain(AccessRelation, Statement->getDomain());
   isl_space_free(Space);
 }
 
 MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
                            __isl_take isl_id *Id, AccessType Type,
-                           Value *BaseAddress, unsigned ElemBytes, bool Affine,
+                           Value *BaseAddress, bool Affine,
                            ArrayRef<const SCEV *> Subscripts,
-                           ArrayRef<const SCEV *> Sizes, Value *AccessValue,
-                           AccessOrigin Origin, StringRef BaseName)
+                           Value *AccessValue, AccessOrigin Origin,
+                           StringRef BaseName)
     : Id(Id), Origin(Origin), AccType(Type), RedType(RT_NONE), Statement(Stmt),
-      BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes),
-      Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
+      BaseAddr(BaseAddress), BaseName(BaseName), AccessInstruction(AccessInst),
       AccessValue(AccessValue), IsAffine(Affine),
       Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
       NewAccessRelation(nullptr) {}
 
 void MemoryAccess::realignParams() {
   isl_space *ParamSpace = Statement->getParent()->getParamSpace();
   AccessRelation = isl_map_align_params(AccessRelation, ParamSpace);
 }
void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
   Domain = NewDomain;
 }
 
 void ScopStmt::buildAccessRelations() {
   for (MemoryAccess *Access : MemAccs) {
     Type *ElementType = Access->getAccessValue()->getType();
 
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
-        Access->getBaseAddr(), ElementType, Access->Sizes, Access->isPHI());
+        Access->getBaseAddr(), ElementType, Access->isPHI());
 
     Access->buildAccessRelation(SAI);
   }
 }
 
 void ScopStmt::addAccess(MemoryAccess *Access) {
   Instruction *AccessInst = Access->getAccessInstruction();
 
UserContext =
         isl_set_set_dim_id(UserContext, isl_dim_param, i,
                            isl_space_get_dim_id(Space, isl_dim_param, i));
   }
 
   Context = isl_set_intersect(Context, UserContext);
   isl_space_free(Space);
 }
 
+void Scop::buildScopArrays(
+    DenseMap<const Instruction *, std::vector<const SCEV *>> &AccessSizes) {
+  const auto &DC = *SD.getDetectionContext(&getRegion());
+
+  for (auto &B2AIt : DC.Accesses) {
+
+    const SCEVUnknown *BasePtrSCEV = B2AIt.first;
+    Value *BasePtr = BasePtrSCEV->getValue();
+    assert(BasePtr);
+
+    Type *ArrayType = nullptr;
+    for (auto &InstIt : B2AIt.second) {
+      if (!InstIt.first)
+        continue;
+
+      unsigned TypeSize = UINT_MAX;
+      Value *PtrOp = getPointerOperand(*cast<Instruction>(InstIt.first));
+      if (TypeSize > PtrOp->getType()->getPrimitiveSizeInBits()) {
+        ArrayType = PtrOp->getType();
+        TypeSize = ArrayType->getPrimitiveSizeInBits();
+      }
+    }
+
+    if (!ArrayType)
+      continue;
+
+    auto *SAI =
+        createScopArrayInfo(BasePtr, ArrayType->getPointerElementType());
+
+    for (auto &InstIt : B2AIt.second) {
+      if (!InstIt.first)
+        continue;
+
+      auto AccItr = DC.InsnToMemAcc.find(cast<Instruction>(InstIt.first));
+      if (AccItr != DC.InsnToMemAcc.end()) {
+        auto &Sizes = AccItr->second.Shape->DelinearizedSizes;
+        if (Sizes.size() > SAI->getNumberOfDimensions())
+          SAI->updateSizes(Sizes);
+      }
+
+      auto ASIt = AccessSizes.find(cast<Instruction>(InstIt.first));
+      if (ASIt != AccessSizes.end()) {
+        auto &Sizes = ASIt->second;
+        Sizes.push_back(
+            SE->getConstant(IntegerType::getInt64Ty(BasePtr->getContext()),
+                            SAI->getElemSizeInBytes()));
+        if (Sizes.size() > SAI->getNumberOfDimensions())
+          SAI->updateSizes(Sizes);
+      }
+    }
+  }
+}
+
 void Scop::buildContext() {
   isl_space *Space = isl_space_params_alloc(IslCtx, 0);
   Context = isl_set_universe(isl_space_copy(Space));
   AssumedContext = isl_set_universe(Space);
 }
 
 void Scop::addParameterBounds() {
   for (const auto &ParamID : ParameterIds) {
Scop::Scop(Region &R, AccFuncMapType &AccFuncMap, ScopDetection &SD,
            ScalarEvolution &ScalarEvolution, DominatorTree &DT, LoopInfo &LI,
            isl_ctx *Context, unsigned MaxLoopDepth)
     : LI(LI), DT(DT), SE(&ScalarEvolution), SD(SD), R(R),
       AccFuncMap(AccFuncMap), IsOptimized(false),
       HasSingleExitEdge(R.getExitingBlock()), MaxLoopDepth(MaxLoopDepth),
       IslCtx(Context), Context(nullptr), Affinator(this),
       AssumedContext(nullptr), BoundaryContext(nullptr), Schedule(nullptr) {}
 
-void Scop::init(AliasAnalysis &AA) {
+void Scop::init(
+    AliasAnalysis &AA,
+    DenseMap<const Instruction *, std::vector<const SCEV *>> &AccessSizes) {
   buildContext();
   buildDomains(&R);
 
   // Remove empty and ignored statements.
   // Exit early in case there are no executable statements left in this scop.
   simplifySCoP(true);
   if (Stmts.empty())
     return;
 
+  buildScopArrays(AccessSizes);
+
   // The ScopStmts now have enough information to initialize themselves.
   for (ScopStmt &Stmt : Stmts)
     Stmt.init();
 
   DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> LoopSchedules;
   Loop *L = getLoopSurroundingRegion(R, LI);
   LoopSchedules[L];
   buildSchedule(&R, LoopSchedules);
-  updateAccessDimensionality();
   Schedule = LoopSchedules[L].first;
 
   realignParams();
   addParameterBounds();
   addUserContext();
   buildBoundaryContext();
   simplifyContexts();
   buildAliasChecks(AA);
for (MinMaxAccessTy &MMA : MinMaxAccessPair.second) {
       isl_pw_multi_aff_free(MMA.second);
     }
   }
 
   for (const auto &IA : InvariantAccesses)
     isl_set_free(IA.second);
 }
 
-void Scop::updateAccessDimensionality() {
-  for (auto &Stmt : *this)
-    for (auto &Access : Stmt)
-      Access->updateDimensionality();
-}
-
 void Scop::simplifySCoP(bool RemoveIgnoredStmts) {
   for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
     ScopStmt &Stmt = *StmtIt;
     RegionNode *RN = Stmt.isRegionStmt()
                          ? Stmt.getRegion()->getNode()
                          : getRegion().getBBNode(Stmt.getBasicBlock());
 
     if (StmtIt->isEmpty() ||
auto compareInvariantAccesses = [this](const InvariantAccessTy &IA0,
 
     return Involves1Id0;
   };
 
   std::stable_sort(InvariantAccesses.begin(), InvariantAccesses.end(),
                    compareInvariantAccesses);
 }
 
+ScopArrayInfo *Scop::createScopArrayInfo(Value *BasePtr, Type *AccessType) {
+  auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, false)];
+  assert(!SAI && "SAI already created");
+  SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), false, this));
+  return SAI.get();
+}
+
 const ScopArrayInfo *
-Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType,
-                               ArrayRef<const SCEV *> Sizes, bool IsPHI) {
+Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType, bool IsPHI) {
   auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, IsPHI)];
-  if (!SAI) {
-    SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes, IsPHI,
-                                this));
-  } else {
-    if (Sizes.size() > SAI->getNumberOfDimensions())
-      SAI->updateSizes(Sizes);
-  }
+  if (!SAI)
+    SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), IsPHI, this));
   return SAI.get();
 }
 
 const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, bool IsPHI) {
   auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, IsPHI)].get();
   assert(SAI && "No ScopArrayInfo available for this base pointer");
   return SAI;
 }
for (Value *Op : Inst->operands()) {
 
       addScalarReadAccess(Op, Inst);
     }
   }
 
   return AnyCrossStmtUse;
 }
 
-extern MapInsnToMemAcc InsnToMemAcc;
-
-void ScopInfo::buildMemoryAccess(
-    Instruction *Inst, Loop *L, Region *R,
-    const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
-    const InvariantLoadsSetTy &ScopRIL) {
-  unsigned Size;
-  Type *SizeType;
+void ScopInfo::buildMemoryAccess(Instruction *Inst, Loop *L, Region *R,
+                                 const ScopDetection::DetectionContext *DC) {
   Value *Val;
   enum MemoryAccess::AccessType Type;
 
   if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
-    SizeType = Load->getType();
-    Size = TD->getTypeStoreSize(SizeType);
     Type = MemoryAccess::READ;
     Val = Load;
   } else {
     StoreInst *Store = cast<StoreInst>(Inst);
-    SizeType = Store->getValueOperand()->getType();
-    Size = TD->getTypeStoreSize(SizeType);
     Type = MemoryAccess::MUST_WRITE;
     Val = Store->getValueOperand();
   }
 
   auto Address = getPointerOperand(*Inst);
 
   const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
   const SCEVUnknown *BasePointer =
if (isa<GetElementPtrInst>(Address) || isa<BitCastInst>(Address)) {
     }
 
     if (auto *GEP = dyn_cast<GetElementPtrInst>(NewAddress)) {
       std::vector<const SCEV *> Subscripts;
       std::vector<int> Sizes;
       std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, *SE);
       auto BasePtr = GEP->getOperand(0);
 
-      std::vector<const SCEV *> SizesSCEV;
+      std::vector<const SCEV *> &SizesSCEV = AccessSizes[Inst];
 
       bool AllAffineSubcripts = true;
       for (auto Subscript : Subscripts) {
         InvariantLoadsSetTy AccessILS;
         AllAffineSubcripts =
             isAffineExpr(R, Subscript, *SE, nullptr, &AccessILS);
 
         for (LoadInst *LInst : AccessILS)
-          if (!ScopRIL.count(LInst))
+          if (!DC->RequiredILS.count(LInst))
             AllAffineSubcripts = false;
 
         if (!AllAffineSubcripts)
           break;
       }
 
       if (AllAffineSubcripts && Sizes.size() > 0) {
         for (auto V : Sizes)
           SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
               IntegerType::getInt64Ty(BasePtr->getContext()), V)));
-        SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
-            IntegerType::getInt64Ty(BasePtr->getContext()), Size)));
 
-        addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true,
-                          Subscripts, SizesSCEV, Val);
+        // TODO: Unify the delinearization.
+        addExplicitAccess(Inst, Type, BasePointer->getValue(), true, Subscripts,
+                          Val);
         return;
       }
     }
   }
 
-  auto AccItr = InsnToMemAcc.find(Inst);
-  if (PollyDelinearize && AccItr != InsnToMemAcc.end()) {
-    addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true,
-                      AccItr->second.DelinearizedSubscripts,
-                      AccItr->second.Shape->DelinearizedSizes, Val);
+  auto AccItr = DC->InsnToMemAcc.find(Inst);
+  if (PollyDelinearize && AccItr != DC->InsnToMemAcc.end()) {
+    addExplicitAccess(Inst, Type, BasePointer->getValue(), true,
+                      AccItr->second.DelinearizedSubscripts, Val);
     return;
   }
 
   // Check if the access depends on a loop contained in a non-affine subregion.
   bool isVariantInNonAffineLoop = false;
-  if (BoxedLoops) {
+  if (!DC->BoxedLoopsSet.empty()) {
     SetVector<const Loop *> Loops;
     findLoops(AccessFunction, Loops);
     for (const Loop *L : Loops)
-      if (BoxedLoops->count(L))
+      if (DC->BoxedLoopsSet.count(L))
         isVariantInNonAffineLoop = true;
   }
 
   InvariantLoadsSetTy AccessILS;
   bool IsAffine =
       !isVariantInNonAffineLoop &&
       isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue(), &AccessILS);
 
   for (LoadInst *LInst : AccessILS)
-    if (!ScopRIL.count(LInst))
+    if (!DC->RequiredILS.count(LInst))
       IsAffine = false;
 
-  // FIXME: Size of the number of bytes of an array element, not the number of
-  // elements as probably intended here.
-  const SCEV *SizeSCEV =
-      SE->getConstant(TD->getIntPtrType(Inst->getContext()), Size);
-
   if (!IsAffine && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;
 
-  addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, IsAffine,
-                    ArrayRef<const SCEV *>(AccessFunction),
-                    ArrayRef<const SCEV *>(SizeSCEV), Val);
+  addExplicitAccess(Inst, Type, BasePointer->getValue(), IsAffine,
+                    ArrayRef<const SCEV *>(AccessFunction), Val);
 }
 
 void ScopInfo::buildAccessFunctions(Region &R, Region &SR) {
 
   if (SD->isNonAffineSubRegion(&SR, &R)) {
     for (BasicBlock *BB : SR.blocks())
       buildAccessFunctions(R, *BB, &SR);
     return;
else
       scop->addScopStmt(I->getNodeAs<BasicBlock>(), nullptr);
 }
 
 void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
                                     Region *NonAffineSubRegion,
                                     bool IsExitBlock) {
   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);
-
-  // The set of loads that are required to be invariant.
-  auto &ScopRIL = *SD->getRequiredInvariantLoads(&R);
+  // The detection context for @R
+  const ScopDetection::DetectionContext *DC = SD->getDetectionContext(&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, NonAffineSubRegion, IsExitBlock);
 
     // For the exit block we stop modeling after the last PHI node.
     if (!PHI && IsExitBlock)
       break;
 
-    // TODO: At this point we only know that elements of ScopRIL have to be
-    //       invariant and will be hoisted for the SCoP to be processed. Though,
-    //       there might be other invariant accesses that will be hoisted and
-    //       that would allow to make a non-affine access affine.
+    // TODO: At this point we only know that elements of DC->RequiredILS have to
+    //       be invariant and will be hoisted for the SCoP to be processed.
+    //       Though,there might be other invariant accesses that will be hoisted
+    //       and that would allow to make a non-affine access affine.
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
-      buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL);
+      buildMemoryAccess(Inst, L, &R, DC);
 
     if (isIgnoredIntrinsic(Inst))
       continue;
 
     // Do not build scalar dependences for required invariant loads as we will
     // hoist them later on anyway or drop the SCoP if we cannot.
-    if (ScopRIL.count(dyn_cast<LoadInst>(Inst)))
+    if (DC->RequiredILS.count(dyn_cast<LoadInst>(Inst)))
       continue;
 
     if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       if (!isa<StoreInst>(Inst))
         addScalarWriteAccess(Inst);
     }
   }
 }
 
 void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                                MemoryAccess::AccessType Type,
-                               Value *BaseAddress, unsigned ElemBytes,
-                               bool Affine, Value *AccessValue,
+                               Value *BaseAddress, bool Affine,
+                               Value *AccessValue,
                                ArrayRef<const SCEV *> Subscripts,
-                               ArrayRef<const SCEV *> Sizes,
                                MemoryAccess::AccessOrigin Origin) {
   ScopStmt *Stmt = scop->getStmtForBasicBlock(BB);
 
   // Do not create a memory access for anything not in the SCoP. It would be
   // ignored anyway.
   if (!Stmt)
     return;
 
   AccFuncSetType &AccList = AccFuncMap[BB];
   size_t Identifier = AccList.size();
 
   Value *BaseAddr = BaseAddress;
   std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
 
   std::string IdName = "__polly_array_ref_" + std::to_string(Identifier);
   isl_id *Id = isl_id_alloc(ctx, IdName.c_str(), nullptr);
 
   bool isApproximated =
       Stmt->isRegionStmt() && (Stmt->getRegion()->getEntry() != BB);
   if (isApproximated && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;
 
-  AccList.emplace_back(Stmt, Inst, Id, Type, BaseAddress, ElemBytes, Affine,
-                       Subscripts, Sizes, AccessValue, Origin, BaseName);
+  AccList.emplace_back(Stmt, Inst, Id, Type, BaseAddress, Affine, Subscripts,
+                       AccessValue, Origin, BaseName);
   Stmt->addAccess(&AccList.back());
 }
 
-void ScopInfo::addExplicitAccess(
-    Instruction *MemAccInst, MemoryAccess::AccessType Type, Value *BaseAddress,
-    unsigned ElemBytes, bool IsAffine, ArrayRef<const SCEV *> Subscripts,
-    ArrayRef<const SCEV *> Sizes, Value *AccessValue) {
+void ScopInfo::addExplicitAccess(Instruction *MemAccInst,
+                                 MemoryAccess::AccessType Type,
+                                 Value *BaseAddress, bool IsAffine,
+                                 ArrayRef<const SCEV *> Subscripts,
+                                 Value *AccessValue) {
   assert(isa<LoadInst>(MemAccInst) || isa<StoreInst>(MemAccInst));
   assert(isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ));
   addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress,
-                  ElemBytes, IsAffine, AccessValue, Subscripts, Sizes,
-                  MemoryAccess::EXPLICIT);
+                  IsAffine, AccessValue, Subscripts, MemoryAccess::EXPLICIT);
 }
 void ScopInfo::addScalarWriteAccess(Instruction *Value) {
-  addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1,
-                  true, Value, ArrayRef<const SCEV *>(),
-                  ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
+  addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value,
+                  true, Value, ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
 }
 void ScopInfo::addScalarReadAccess(Value *Value, Instruction *User) {
   assert(!isa<PHINode>(User));
-  addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true,
-                  Value, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  MemoryAccess::SCALAR);
+  addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, true,
+                  Value, ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
 }
 void ScopInfo::addScalarReadAccess(Value *Value, PHINode *User,
                                    BasicBlock *UserBB) {
-  addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
-                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  MemoryAccess::SCALAR);
+  addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, true, Value,
+                  ArrayRef<const SCEV *>(), MemoryAccess::SCALAR);
 }
 void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
                                  Value *IncomingValue, bool IsExitBlock) {
   addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(),
-                  MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue,
-                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
+                  MemoryAccess::MUST_WRITE, PHI, true, IncomingValue,
+                  ArrayRef<const SCEV *>(),
                   IsExitBlock ? MemoryAccess::SCALAR : MemoryAccess::PHI);
 }
 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
-  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
-                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  MemoryAccess::PHI);
+  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, true, PHI,
+                  ArrayRef<const SCEV *>(), MemoryAccess::PHI);
 }
 
 void ScopInfo::buildScop(Region &R, DominatorTree &DT) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
   scop = new Scop(R, AccFuncMap, *SD, *SE, DT, *LI, ctx, MaxLoopDepth);
 
   buildStmts(R);
   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);
 
-  scop->init(*AA);
+  scop->init(*AA, AccessSizes);
 }
 
 void ScopInfo::print(raw_ostream &OS, const Module *) const {
   if (!scop) {
     OS << "Invalid Scop!\n";
     return;
   }
 
   scop->print(OS);
 }
 
 void ScopInfo::clear() {
   AccFuncMap.clear();
+  AccessSizes.clear();
   if (scop) {
     delete scop;
     scop = 0;
   }
 }
 
 //===----------------------------------------------------------------------===//
 ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {

test/ScopDetect/cross_loop_non_single_exit.ll

for.i:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   fence seq_cst
   ret void
 }
 
-; CHECK: Valid Region for Scop: next => return
-; CHECK: Valid Region for Scop: next2 => return
+; CHECK-DAG: Valid Region for Scop: next => return
+; CHECK-DAG: Valid Region for Scop: next2 => return

test/ScopInfo/delinearize-together-all-data-refs.ll

 ; RUN: opt %loadPolly -polly-scops -analyze -polly-delinearize < %s | FileCheck %s
 
 ; void foo(long n, long m, long o, double A[n][m][o]) {
 ;   for (long i = 0; i < n-3; i++)
 ;     for (long j = 4; j < m; j++)
 ;       for (long k = 0; k < o-7; k++) {
 ;         A[i+3][j-4][k+7] = 1.0;
 ;         A[i][0][k] = 2.0;
 ;       }
 ; }
 
 
 ; CHECK: Arrays {
-; CHECK:     double MemRef_A[*][%m][%o][8] // Element size 8
+; CHECK:     double MemRef_A[*][%m][%o] // Element size 8
 ; CHECK: }
 
 ; CHECK: [m, o, n] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[3 + i0, i1, 7 + i2] };
 ; CHECK: [m, o, n] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[i0, 0, i2] };
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Function Attrs: nounwind uwtable

test/ScopInfo/invariant_load_ptr_ptr_noalias.ll

 ; RUN: opt %loadPolly -tbaa -polly-scops -polly-ignore-aliasing \
 ; RUN:                -analyze < %s | FileCheck %s
 ;
 ; Note: The order of the invariant accesses is important because A is the
 ;       base pointer of tmp3 and we will generate code in the same order as
 ;       the invariant accesses are listed here.
 ;
 ; CHECK: Invariant Accesses: {
 ; CHECK:    ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:         MemRef_A[42]
 ; CHECK:    ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:         MemRef_tmp3[32]
 ; CHECK: }
 ;
 ; CHECK: Arrays {
-; CHECK:   i32** MemRef_A[*][8]
-; CHECK:   i32* MemRef_tmp3[*][8] [BasePtrOrigin: MemRef_A]
-; CHECK:   i32 MemRef_tmp5[*][4] [BasePtrOrigin: MemRef_tmp3]
+; CHECK:   i32** MemRef_A[*]
+; CHECK:   i32* MemRef_tmp3[*] [BasePtrOrigin: MemRef_A]
+; CHECK:   i32 MemRef_tmp5[*] [BasePtrOrigin: MemRef_tmp3]
 ; CHECK: }
 ;
 ; CHECK: Arrays (Bounds as pw_affs) {
-; CHECK:   i32** MemRef_A[*][ { [] -> [(8)] } ]
-; CHECK:   i32* MemRef_tmp3[*][ { [] -> [(8)] } ] [BasePtrOrigin: MemRef_A]
-; CHECK:   i32 MemRef_tmp5[*][ { [] -> [(4)] } ] [BasePtrOrigin: MemRef_tmp3]
+; CHECK:   i32** MemRef_A[*]
+; CHECK:   i32* MemRef_tmp3[*] [BasePtrOrigin: MemRef_A]
+; CHECK:   i32 MemRef_tmp5[*] [BasePtrOrigin: MemRef_tmp3]
 ; CHECK: }
 ;
 ;    void f(int ***A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        A[42][32][i] = 0;
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

test/ScopInfo/multi-scop.ll

for.body81:                                       ; preds = %for.body81, %for.end
   store double undef, double* %arrayidx139, align 8
   %add169 = add nsw i32 %j.19, 2
   br i1 false, label %for.body81, label %for.end170
 
 for.end170:                                       ; preds = %for.body81
   ret void
 }
 
-; CHECK: Valid Region for Scop: entry.split => for.end
-; CHECK: Valid Region for Scop: for.body81 => for.end170
+; CHECK-DAG: Valid Region for Scop: entry.split => for.end
+; CHECK-DAG: Valid Region for Scop: for.body81 => for.end170
 

test/ScopInfo/multidim_only_ivs_3d_cast.ll

 ; CHECK: p0: %o
 ; CHECK: p1: %m
 ; CHECK: p2: %n
 ; CHECK: p3: (zext i32 %m to i64)
 ; CHECK: p4: (zext i32 %o to i64)
 ; CHECK-NOT: p5
 
 ; CHECK: Arrays {
-; CHECK: double MemRef_A[*][(zext i32 %m to i64)][(zext i32 %o to i64)][8] // Element size 8
+; CHECK: double MemRef_A[*][(zext i32 %m to i64)][(zext i32 %o to i64)] // Element size 8
 ; CHECK: }
 ; CHECK: Arrays (Bounds as pw_affs) {
-; CHECK: double MemRef_A[*][ [p_3] -> { [] -> [(p_3)] } ][ [p_4] -> { [] -> [(p_4)] } ][ { [] -> [(8)] } ] // Element size 8
+; CHECK: double MemRef_A[*][ [p_3] -> { [] -> [(p_3)] } ][ [p_4] -> { [] -> [(p_4)] } ] // Element size 8
 ; CHECK: }
 
 
 ; CHECK: Domain
 ; CHECK:   [o, m, n, p_3, p_4] -> { Stmt_for_k[i0, i1, i2] :
 ; CHECK-DAG:             i0 >= 0
 ; CHECK-DAG:          and
 ; CHECK-DAG:             i0 <= -1 + n

test/ScopInfo/non_affine_region_4.ll

 ;          y++;
 ;        A[i] = x + y;
 ;      }
 ;    }
 ;
 ; CHECK:    Region: %bb1---%bb11
 ;
 ; CHECK: Arrays {
-; CHECK:   i32 MemRef_A[*][4]
+; CHECK:   i32 MemRef_A[*]
 ; CHECK:   i32 MemRef_x[*] [BasePtrOrigin: MemRef_A]
 ; CHECK:   i32 MemRef_y__phi[*]
 ; CHECK: }
 ;
 ; CHECK: Arrays (Bounds as pw_affs) {
-; CHECK:   i32 MemRef_A[*][ { [] -> [(4)] } ]
+; CHECK:   i32 MemRef_A[*]
 ; CHECK:   i32 MemRef_x[*] [BasePtrOrigin: MemRef_A]
 ; CHECK:   i32 MemRef_y__phi[*]
 ; CHECK: }
 ;
 ; CHECK:      Stmt_bb2__TO__bb7
 ; CHECK:            Domain :=
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] :
 ; CHECK-DAG:               i0 >= 0

test/ScopInfo/scalar.ll

for.backedge:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for
 
 return:
   ret void
 }
 
 ; CHECK: Arrays {
-; CHECK:   i64 MemRef_a[*][8]
+; CHECK:   i64 MemRef_a[*]
 ; CHECK:   i64 MemRef_val[*] [BasePtrOrigin: MemRef_a]
 ; CHECK: }
 ;
 ; CHECK: Arrays (Bounds as pw_affs) {
-; CHECK:   i64 MemRef_a[*][ { [] -> [(8)] } ]
+; CHECK:   i64 MemRef_a[*]
 ; CHECK:   i64 MemRef_val[*] [BasePtrOrigin: MemRef_a]
 ; CHECK: }
 
 ; CHECK: Stmt_S1
 ; CHECK:       Domain :=
 ; CHECK:           [N] -> { Stmt_S1[i0] : i0 >= 0 and i0 <= -1 + N };
 ; CHECK:       Schedule :=
 ; CHECK:           [N] -> { Stmt_S1[i0] -> [i0, 0] };

test/ScopInfo/simple_loop_1.ll

 
 return:                                           ; preds = %bb, %entry
   ret void
 }
 
 ; CHECK: Assumed Context:
 ; CHECK:   {  :  }
 ; CHECK: Arrays {
-; CHECK:     i64 MemRef_a[*][8] // Element size 8
+; CHECK:     i64 MemRef_a[*] // Element size 8
 ; CHECK: }
 
 ; CHECK:  Stmt_bb
 ; CHECK:        Domain :=
 ; CHECK:            [N] -> { Stmt_bb[i0] : i0 >= 0 and i0 <= -1 + N };
 ; CHECK:        Schedule :=
 ; CHECK:            [N] -> { Stmt_bb[i0] -> [i0] };
 ; CHECK:        MustWriteAccess := [Reduction Type: NONE]
 ; CHECK:            [N] -> { Stmt_bb[i0] -> MemRef_a[i0] };