[Delinearization] Delinearization of Array-of-Struct. Proof-of-Concept.

[Meinersbur]

Summary

struct  __attribute__((packed)) Pair { int x; long y; };
void foo(unsigned long N,  struct Pair A[][N]) {
  for (unsigned long i = 0; i < N; i+=1)
      A[i][i].y = 0;
}

lowered to

%0 = mul nsw i64 %i.0, %N
%arrayidx = getelementptr inbounds %struct.Pair, %struct.Pair* %A, i64 %0
%arrayidx1 = getelementptr inbounds %struct.Pair, %struct.Pair* %arrayidx, i64 %i.0
%y = getelementptr inbounds %struct.Pair, %struct.Pair* %arrayidx1, i64 0, i32 1

corresponding to the SCEVExpr

{4,+,(12 + (12 * %N))}<%for.cond>

delinearized to

ArrayDecl[UnknownSize][%N][12]
ArrayRef[{0,+,1}<%for.cond>][{0,+,1}<%for.cond>][4]

See test case array_of_struct.ll

[bmahjour]

llvm/test/Analysis/Delinearization/array_of_struct.ll

2

Could we add the following as a motivating test case as well:

struct __attribute__((packed)) MyS {
  float a;
  double b;
  char c;
};

void foo(long long n, long long m, struct MyS f1[][n][m]) {
  for (int i = 0; i < 1024; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < m; k++)
        f1[i][j][k].b = f1[i-1][j][k].b;
}

The expected delinearization would produce the same subscripts in every dimension (including the added inner-most byte dimension) except for the outer-most dimension where the absolute difference between the subscripts should be 1.

[nikic]

llvm/lib/Analysis/Delinearization.cpp

505

This isn't compatible with opaque pointers. The access size needs to be determine exclusively based on load/store element type (using GEP type is inappropriate for this as well, even if it won't outright crash).

[Meinersbur]

llvm/lib/Analysis/Delinearization.cpp

505

This is the fallback case, we could pass the actual load/store as another parameter instead, but wasn't necessary for this PoC.

The GEP type is/was useful information though, leaking some information of how data is accessed from the source code. However, in principle this information can also derived from recurrence in the SCEV. In the test case it is (12 + (12 * %N)), i.e. a multiple of 12, suggesting that to be the array element size.

llvm/test/Analysis/Delinearization/array_of_struct.ll

2

I will try to make this work.

[Meinersbur]

• Multiple sources for element size: Access size, GEP, SCEV stride

[Meinersbur]

• Re-add gcd test case

llvm/include/llvm/ADT/STLExtras.h

auto partition_point(R &&Range, Predicate P) {
   return std::partition_point(adl_begin(Range), adl_end(Range), P);
 }
 
 template<typename Range, typename Predicate>
 auto unique(Range &&R, Predicate P) {
   return std::unique(adl_begin(R), adl_end(R), P);
 }
 
+template <typename Range> auto unique(Range &&R) {
+  return std::unique(adl_begin(R), adl_end(R));
+}
+
 /// Wrapper function around std::equal to detect if pair-wise elements between
 /// two ranges are the same.
 template <typename L, typename R> bool equal(L &&LRange, R &&RRange) {
   return std::equal(adl_begin(LRange), adl_end(LRange), adl_begin(RRange),
                     adl_end(RRange));
 }
 
 /// Wrapper function around std::equal to detect if all elements

llvm/include/llvm/Analysis/Delinearization.h

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 class GetElementPtrInst;
 class ScalarEvolution;
 class SCEV;
+class Loop;
 
 /// Compute the array dimensions Sizes from the set of Terms extracted from
 /// the memory access function of this SCEVAddRecExpr (second step of
 /// delinearization).
 void findArrayDimensions(ScalarEvolution &SE,
                          SmallVectorImpl<const SCEV *> &Terms,
                          SmallVectorImpl<const SCEV *> &Sizes,
                          const SCEV *ElementSize);
 
 /// Collect parametric terms occurring in step expressions (first step of
 /// delinearization).
 void collectParametricTerms(ScalarEvolution &SE, const SCEV *Expr,
                             SmallVectorImpl<const SCEV *> &Terms);
 
 /// Return in Subscripts the access functions for each dimension in Sizes
 /// (third step of delinearization).
 void computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr,
                             SmallVectorImpl<const SCEV *> &Subscripts,
-                            SmallVectorImpl<const SCEV *> &Sizes);
+                            ArrayRef<const SCEV *> Sizes);
+
 /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
 /// subscripts and sizes of an array access.
 ///
 /// The delinearization is a 3 step process: the first two steps compute the
 /// sizes of each subscript and the third step computes the access functions
 /// for the delinearized array:
 ///
 /// 1. Find the terms in the step functions

 /// accesses, and compute in step 2 a unique array shape. This guarantees
 /// that the array shape will be the same across all memory accesses.
 ///
 /// FIXME: We could derive the result of steps 1 and 2 from a description of
 /// the array shape given in metadata.
 ///
 /// Example:
 ///
-/// A[][n][m]
+/// float A[][n][m]
 ///
 /// for i
 ///   for j
 ///     for k
 ///       A[j+k][2i][5i] =
 ///
 /// The initial SCEV:
 ///
 /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
+/// (Note: The SCEV of a pointer is in bytes, here we use the argument
+/// of the GetElementPtr for illustration)
 ///
 /// 1. Find the different terms in the step functions:
 /// -> [2*m, 5, n*m, n*m]
 ///
 /// 2. Compute the array size: sort and unique them
 /// -> [n*m, 2*m, 5]
 /// find the GCD of all the terms = 1
 /// divide by the GCD and erase constant terms

 ///
 /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n
 /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k
 /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k
 /// The Remainder is the subscript of the next array dimension: [2i].
 ///
 /// The subscript of the outermost dimension is the Quotient: [j+k].
 ///
-/// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
+/// Overall, for the address of the above memory access we have: A[][n][m][4],
+/// and the access function: A[j+k][2i][5i][0] where [4] is the array element
+/// size in bytes and [0] is the byte offset into this element.
 void delinearize(ScalarEvolution &SE, const SCEV *Expr,
                  SmallVectorImpl<const SCEV *> &Subscripts,
                  SmallVectorImpl<const SCEV *> &Sizes, const SCEV *ElementSize);
 
+bool delinearizeAccess(ScalarEvolution &SE, Value *PtrVal, Type *AccessTy,
+                       Loop *Scope, SmallVectorImpl<const SCEV *> &Subscripts,
+                       SmallVectorImpl<const SCEV *> &Sizes);
+
 /// Gathers the individual index expressions from a GEP instruction.
 ///
 /// This function optimistically assumes the GEP references into a fixed size
 /// array. If this is actually true, this function returns a list of array
 /// subscript expressions in \p Subscripts and a list of integers describing
 /// the size of the individual array dimensions in \p Sizes. Both lists have
 /// either equal length or the size list is one element shorter in case there
 /// is no known size available for the outermost array dimension. Returns true

llvm/lib/Analysis/Delinearization.cpp

LLVM_DEBUG({
     dbgs() << "Sizes:\n";
     for (const SCEV *S : Sizes)
       dbgs() << *S << "\n";
   });
 }
 
 void llvm::computeAccessFunctions(ScalarEvolution &SE, const SCEV *Expr,
                                   SmallVectorImpl<const SCEV *> &Subscripts,
-                                  SmallVectorImpl<const SCEV *> &Sizes) {
+                                  ArrayRef<const SCEV *> Sizes) {
   // Early exit in case this SCEV is not an affine multivariate function.
   if (Sizes.empty())
     return;
 
   if (auto *AR = dyn_cast<SCEVAddRecExpr>(Expr))
     if (!AR->isAffine())
       return;
 
   const SCEV *Res = Expr;
   int Last = Sizes.size() - 1;
   for (int i = Last; i >= 0; i--) {
     const SCEV *Q, *R;
     SCEVDivision::divide(SE, Res, Sizes[i], &Q, &R);
 
+    // if (i == Last && !isa<SCEVConstant>(R)) {
+    // R = Res;
+    // Q = SE.getZero(R->getType());
+    //   Q = SE.getUDivExpr(Res, Sizes[i]);
+    //   R = SE.getURemExpr(Res, Sizes[i]);
+    // }
+
     LLVM_DEBUG({
       dbgs() << "Res: " << *Res << "\n";
       dbgs() << "Sizes[i]: " << *Sizes[i] << "\n";
       dbgs() << "Res divided by Sizes[i]:\n";
       dbgs() << "Quotient: " << *Q << "\n";
       dbgs() << "Remainder: " << *R << "\n";
     });
 
     Res = Q;
 
-    // Do not record the last subscript corresponding to the size of elements in
-    // the array.
-    if (i == Last) {
-
-      // Bail out if the byte offset is non-zero.
-      if (!R->isZero()) {
-        Subscripts.clear();
-        Sizes.clear();
-        return;
-      }
-
-      continue;
-    }
 
     // Record the access function for the current subscript.
     Subscripts.push_back(R);
   }
 
   // Also push in last position the remainder of the last division: it will be
   // the access function of the innermost dimension.
   Subscripts.push_back(Res);

 /// because it appears as an offset that does not divide any of the strides in
 /// the loops:
 ///
 ///  CHECK: Base offset: %A
 ///
 /// and then SCEV->delinearize determines the size of some of the dimensions of
 /// the array as these are the multiples by which the strides are happening:
 ///
-///  CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of sizeof(double)
-///  bytes.
+///  CHECK: ArrayDecl[UnknownSize][%m][%o][sizeof(double)]
 ///
 /// Note that the outermost dimension remains of UnknownSize because there are
 /// no strides that would help identifying the size of the last dimension: when
 /// the array has been statically allocated, one could compute the size of that
 /// dimension by dividing the overall size of the array by the size of the known
 /// dimensions: %m * %o * 8.
 ///
 /// Finally delinearize provides the access functions for the array reference
 /// that does correspond to A[i][j][k] of the above C testcase:
 ///
-///  CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]
+///  CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>][0]
 ///
 /// The testcases are checking the output of a function pass:
 /// DelinearizationPass that walks through all loads and stores of a function
 /// asking for the SCEV of the memory access with respect to all enclosing
 /// loops, calling SCEV->delinearize on that and printing the results.
 void llvm::delinearize(ScalarEvolution &SE, const SCEV *Expr,
                        SmallVectorImpl<const SCEV *> &Subscripts,
                        SmallVectorImpl<const SCEV *> &Sizes,
LLVM_DEBUG({
 
     dbgs() << "\nArrayRef";
     for (const SCEV *S : Subscripts)
       dbgs() << "[" << *S << "]";
     dbgs() << "\n";
   });
 }
 
+class SCEVEliminateParams : public SCEVRewriteVisitor<SCEVEliminateParams> {
+public:
+  static const SCEV *rewrite(ScalarEvolution &SE, const SCEV *E) {
+    SCEVEliminateParams Rewriter(SE);
+    return Rewriter.visit(E);
+  }
+
+  SCEVEliminateParams(ScalarEvolution &SE) : SCEVRewriteVisitor(SE) {}
+
+  const SCEV *visitUnknown(const SCEVUnknown *Expr) {
+    auto Ty = Expr->getType();
+    return SE.getZero(Ty);
+  }
+};
+
 bool llvm::getIndexExpressionsFromGEP(ScalarEvolution &SE,
                                       const GetElementPtrInst *GEP,
                                       SmallVectorImpl<const SCEV *> &Subscripts,
                                       SmallVectorImpl<int> &Sizes) {
   assert(Subscripts.empty() && Sizes.empty() &&
          "Expected output lists to be empty on entry to this function.");
   assert(GEP && "getIndexExpressionsFromGEP called with a null GEP");
   Type *Ty = nullptr;
   bool DroppedFirstDim = false;
   for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
     const SCEV *Expr = SE.getSCEV(GEP->getOperand(i));
     if (i == 1) {
       Ty = GEP->getSourceElementType();
       if (auto *Const = dyn_cast<SCEVConstant>(Expr))
         if (Const->getValue()->isZero()) {
           DroppedFirstDim = true;
           continue;
         }
for (unsigned i = 1; i < GEP->getNumOperands(); i++) {
     if (!(DroppedFirstDim && i == 2))
       Sizes.push_back(ArrayTy->getNumElements());
 
     Ty = ArrayTy->getElementType();
   }
   return !Subscripts.empty();
 }
 
+bool llvm::delinearizeAccess(ScalarEvolution &SE, Value *PtrVal, Type *AccessTy,
+                             Loop *Scope,
+                             SmallVectorImpl<const SCEV *> &Subscripts,
+                             SmallVectorImpl<const SCEV *> &Sizes) {
+
+  const SCEV *PtrExpr = SE.getSCEVAtScope(PtrVal, Scope);
+
+  const SCEVUnknown *BasePointer =
+      dyn_cast<SCEVUnknown>(SE.getPointerBase(PtrExpr));
+  // Do not delinearize if we cannot find the base pointer.
+  if (!BasePointer)
+    return false;
+
+  const SCEV *AccessFn = SE.getMinusSCEV(PtrExpr, BasePointer);
+
+  Type *PtrItTy = SE.getEffectiveSCEVType(PtrVal->getType());
+  const SCEV *AccessSize = SE.getSizeOfExpr(PtrItTy, AccessTy);
+
+  SmallVector<APInt> CandidateElementSize;
+
+  // 1. For non-structure-of-arrays, the access size is the element size.
+  if (const SCEVConstant *C = dyn_cast_or_null<SCEVConstant>(AccessSize))
+    CandidateElementSize.push_back(C->getAPInt());
+
+  // 2. Try to infer the element size from the GEP.
+  SmallVector<GEPOperator *> GEPChain;
+  Value *GEPStart = PtrVal;
+  while (GEPOperator *GEP = dyn_cast<GEPOperator>(GEPStart)) {
+    GEPChain.push_back(GEP);
+    GEPStart = GEP->getPointerOperand();
+  }
+  std::reverse(GEPChain.begin(), GEPChain.end());
+
+  auto AddCandidateStructTy = [&](Type *Ty) {
+    const SCEV *SizeExpr = SE.getSizeOfExpr(PtrItTy, Ty);
+    if (!SizeExpr || SizeExpr->isZero())
+      return;
+    if (const SCEVConstant *C = dyn_cast_or_null<SCEVConstant>(SizeExpr))
+      CandidateElementSize.push_back(C->getAPInt());
+  };
+
+  for (GEPOperator *GEP : GEPChain) {
+    Type *SrcType = GEP->getSourceElementType();
+    AddCandidateStructTy(SrcType);
+    // Value* PtrIndex = *GEP->indices().begin();
+    SmallVector<Value *> Indices;
+    llvm::append_range(Indices, llvm::drop_begin(GEP->indices(), 1));
+    for (auto Idx : Indices) {
+      SrcType = GetElementPtrInst::getTypeAtIndex(SrcType, Idx);
+      AddCandidateStructTy(SrcType);
+    }
+    GEPStart = GEP;
+  }
+  assert(GEPStart == PtrVal);
+
+  // 3. Infer that array element size from the SCEV stride.
+  SCEVEliminateParams Eliminator(SE);
+  SmallVector<const SCEV *> Strides;
+  SCEVCollectStrides StrideCollector(SE, Strides);
+  visitAll(AccessFn, StrideCollector);
+  for (const SCEV *Stride : StrideCollector.Strides) {
+    const SCEV *ReducedStride = Eliminator.visit(Stride);
+    if (const SCEVConstant *C = dyn_cast_or_null<SCEVConstant>(ReducedStride))
+      CandidateElementSize.push_back(C->getAPInt());
+  }
+
+  // Use largest ElementSize that does give a benefit, fall back to AccessSize
+  // if not does.
+  const SCEV *ElementSize = AccessSize;
+  unsigned MaxIntBitWidth = 0;
+  for (const APInt &V : CandidateElementSize)
+    MaxIntBitWidth = std::max(MaxIntBitWidth, V.getBitWidth());
+  for (APInt &V : CandidateElementSize)
+    if (V.getBitWidth() < MaxIntBitWidth)
+      V = V.zext(MaxIntBitWidth);
+  llvm::sort(CandidateElementSize,
+             [](const APInt &LHS, const APInt &RHS) { return LHS.ult(RHS); });
+  CandidateElementSize.erase(llvm::unique(CandidateElementSize),
+                             CandidateElementSize.end());
+  for (APInt &S : llvm::reverse(CandidateElementSize)) {
+    if (S.isZero())
+      continue;
+
+    // Only consider element sizes where the subscript will be constant. This
+    // must be the case for structure accesses.
+    const SCEV *Q, *R;
+    SCEVDivision::divide(SE, AccessFn, SE.getConstant(S), &Q, &R);
+    if (isa<SCEVConstant>(R)) {
+      ElementSize = SE.getConstant(S);
+      break;
+    }
+  }
+
+  // First step: collect parametric terms.
+  SmallVector<const SCEV *, 4> Terms;
+  collectParametricTerms(SE, AccessFn, Terms);
+
+  if (Terms.empty())
+    return false;
+
+  // Second step: find subscript sizes.
+  findArrayDimensions(SE, Terms, Sizes, ElementSize);
+
+  if (Sizes.empty())
+    return false;
+
+  // Third step: compute the access functions for each subscript.
+  computeAccessFunctions(SE, AccessFn, Subscripts, Sizes);
+
+  if (Subscripts.empty())
+    return false;
+
+  LLVM_DEBUG({
+    dbgs() << "succeeded to delinearize " << *AccessFn << "\n";
+    dbgs() << "ArrayDecl[UnknownSize]";
+    for (const SCEV *S : Sizes)
+      dbgs() << "[" << *S << "]";
+
+    dbgs() << "\nArrayRef";
+    for (const SCEV *S : Subscripts)
+      dbgs() << "[" << *S << "]";
+    dbgs() << "\n";
+  });
+  return true;
+}
+
 namespace {
 
 class Delinearization : public FunctionPass {
   Delinearization(const Delinearization &); // do not implement
 protected:
   Function *F;
   LoopInfo *LI;
   ScalarEvolution *SE;
public:
   void print(raw_ostream &O, const Module *M = nullptr) const override;
 };
 
 void printDelinearization(raw_ostream &O, Function *F, LoopInfo *LI,
                           ScalarEvolution *SE) {
   O << "Delinearization on function " << F->getName() << ":\n";
   for (Instruction &Inst : instructions(F)) {
     // Only analyze loads and stores.
-    if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst) &&
-        !isa<GetElementPtrInst>(&Inst))
+    if (!isa<StoreInst>(&Inst) && !isa<LoadInst>(&Inst))
       continue;
 
     const BasicBlock *BB = Inst.getParent();
     // Delinearize the memory access as analyzed in all the surrounding loops.
     // Do not analyze memory accesses outside loops.
     for (Loop *L = LI->getLoopFor(BB); L != nullptr; L = L->getParentLoop()) {
       const SCEV *AccessFn = SE->getSCEVAtScope(getPointerOperand(&Inst), L);
 
+      auto PtrVal = getPointerOperand(&Inst);
+      auto AccessTy = getLoadStoreType(&Inst);
+
       const SCEVUnknown *BasePointer =
           dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFn));
       // Do not delinearize if we cannot find the base pointer.
       if (!BasePointer)
         break;
       AccessFn = SE->getMinusSCEV(AccessFn, BasePointer);
 
       O << "\n";
       O << "Inst:" << Inst << "\n";
       O << "In Loop with Header: " << L->getHeader()->getName() << "\n";
       O << "AccessFunction: " << *AccessFn << "\n";
 
       SmallVector<const SCEV *, 3> Subscripts, Sizes;
-      delinearize(*SE, AccessFn, Subscripts, Sizes, SE->getElementSize(&Inst));
+      delinearizeAccess(*SE, PtrVal, AccessTy, L, Subscripts, Sizes);
       if (Subscripts.size() == 0 || Sizes.size() == 0 ||
-          Subscripts.size() != Sizes.size()) {
+          Subscripts.size() != Sizes.size() + 1) {
         O << "failed to delinearize\n";
         continue;
       }
 
       O << "Base offset: " << *BasePointer << "\n";
       O << "ArrayDecl[UnknownSize]";
-      int Size = Subscripts.size();
-      for (int i = 0; i < Size - 1; i++)
-        O << "[" << *Sizes[i] << "]";
-      O << " with elements of " << *Sizes[Size - 1] << " bytes.\n";
+      for (const SCEV *Size : Sizes)
+        O << "[" << *Size << "]";
+      O << "\n";
 
       O << "ArrayRef";
-      for (int i = 0; i < Size; i++)
-        O << "[" << *Subscripts[i] << "]";
+      for (const SCEV *Subscript : Subscripts)
+        O << "[" << *Subscript << "]";
       O << "\n";
     }
   }
 }
 
 } // end anonymous namespace
 
 void Delinearization::getAnalysisUsage(AnalysisUsage &AU) const {

llvm/lib/Analysis/DependenceAnalysis.cpp

bool DependenceInfo::tryDelinearizeParametricSize(
   // Second step: find subscript sizes.
   SmallVector<const SCEV *, 4> Sizes;
   findArrayDimensions(*SE, Terms, Sizes, ElementSize);
 
   // Third step: compute the access functions for each subscript.
   computeAccessFunctions(*SE, SrcAR, SrcSubscripts, Sizes);
   computeAccessFunctions(*SE, DstAR, DstSubscripts, Sizes);
 
+  // computeAccessFunctions also returns the by offset into the array element,
+  // which DependenceAnalysis does not handle. Pop that last subscript and bail
+  // out if it is not zero.
+  // TODO: Support memory accesses that fall into the array element's byte
+  // range.
+  if (!SrcSubscripts.empty()) {
+    const SCEV *EltOffset = SrcSubscripts.pop_back_val();
+    if (!EltOffset->isZero())
+      return false;
+  }
+  if (!DstSubscripts.empty()) {
+    const SCEV *EltOffset = DstSubscripts.pop_back_val();
+    if (!EltOffset->isZero())
+      return false;
+  }
+
   // Fail when there is only a subscript: that's a linearized access function.
   if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
       SrcSubscripts.size() != DstSubscripts.size())
     return false;
 
   size_t Size = SrcSubscripts.size();
 
   // Statically check that the array bounds are in-range. The first subscript we

llvm/lib/Analysis/LoopCacheAnalysis.cpp

if (Loop *L = LI.getLoopFor(BB)) {
     AccessFn = SE.getMinusSCEV(AccessFn, BasePointer);
 
     LLVM_DEBUG(dbgs().indent(2) << "In Loop '" << L->getName()
                                 << "', AccessFn: " << *AccessFn << "\n");
 
     llvm::delinearize(SE, AccessFn, Subscripts, Sizes,
                       SE.getElementSize(&StoreOrLoadInst));
 
+    // Eliminate the innermost subscript (for the byte offset to the array
+    // element). LoopCacheAnalysis assumes it is zero.
+    if (!Subscripts.empty() && Subscripts.back()->isZero())
+      Subscripts.pop_back();
+
     if (Subscripts.empty() || Sizes.empty() ||
         Subscripts.size() != Sizes.size()) {
+      Subscripts.clear();
+      Sizes.clear();
+
       // Attempt to determine whether we have a single dimensional array access.
       // before giving up.
       if (!isOneDimensionalArray(*AccessFn, *ElemSize, *L, SE)) {
         LLVM_DEBUG(dbgs().indent(2)
                    << "ERROR: failed to delinearize reference\n");
-        Subscripts.clear();
-        Sizes.clear();
         return false;
       }
 
       // The array may be accessed in reverse, for example:
       //   for (i = N; i > 0; i--)
       //     A[i] = 0;
       // In this case, reconstruct the access function using the absolute value
       // of the step recurrence.

llvm/test/Analysis/Delinearization/a.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 ;
 ; void foo(long n, long m, long o, int A[n][m][o]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[2*i+3][3*j-4][5*k+7] = 1;
 ; }
 
 ; AddRec: {{{(28 + (4 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(12 * %o)}<%for.j>,+,20}<%for.k>
 ; CHECK: Base offset: %A
-; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 4 bytes.
-; CHECK: ArrayRef[{3,+,2}<nuw><%for.i>][{-4,+,3}<nw><%for.j>][{7,+,5}<nw><%for.k>]
+; CHECK: ArrayDecl[UnknownSize][%m][%o][4]
+; CHECK: ArrayRef[{3,+,2}<nuw><%for.i>][{-4,+,3}<nw><%for.j>][{7,+,5}<nw><%for.k>][0]
 
 define void @foo(i64 %n, i64 %m, i64 %o, i32* nocapture %A) #0 {
 entry:
   %cmp32 = icmp sgt i64 %n, 0
   br i1 %cmp32, label %for.cond1.preheader.lr.ph, label %for.end17
 
 for.cond1.preheader.lr.ph:                        ; preds = %entry
   %cmp230 = icmp sgt i64 %m, 0

llvm/test/Analysis/Delinearization/array_of_struct.ll

+; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s
+; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
+
+; CHECK: Inst:  store i64 0, i64* %y, align 1, !tbaa !3
+; CHECK: In Loop with Header: for.cond
+; CHECK: AccessFunction: {4,+,(12 + (12 * %N))}<%for.cond>
+; CHECK: Base offset: %A
+; CHECK: ArrayDecl[UnknownSize][%N][12]
+; CHECK: ArrayRef[{0,+,1}<%for.cond>][{0,+,1}<%for.cond>][4]
+
+; struct  __attribute__((packed)) Pair { int x; long y; };
+; void foo(unsigned long N,  struct Pair A[][N]) {
+;   for (unsigned long i = 0; i < N; i+=1)
+;       A[i][i].y = 0;
+; }
+
+
+
+source_filename = "byte_offset.c"
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.Pair = type <{ i32, i64 }>
+
+; Function Attrs: nounwind uwtable
+define dso_local void @foo(i64 %N, %struct.Pair* %A) #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i64 [ 0, %entry ], [ %add, %for.body ]
+  %cmp = icmp ult i64 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %0 = mul nsw i64 %i.0, %N
+  %arrayidx = getelementptr inbounds %struct.Pair, %struct.Pair* %A, i64 %0
+  %arrayidx1 = getelementptr inbounds %struct.Pair, %struct.Pair* %arrayidx, i64 %i.0
+  %y = getelementptr inbounds %struct.Pair, %struct.Pair* %arrayidx1, i64 0, i32 1
+  store i64 0, i64* %y, align 1, !tbaa !3
+  %add = add i64 %i.0, 1
+  br label %for.cond, !llvm.loop !9
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+; Function Attrs: argmemonly nofree nosync nounwind willreturn
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: argmemonly nofree nosync nounwind willreturn
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+attributes #0 = { nounwind uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #1 = { argmemonly nofree nosync nounwind willreturn }
+
+!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{i32 7, !"uwtable", i32 1}
+!2 = !{!"clang version 14.0.0 (/home/meinersbur/src/llvm-project/clang 164631ce80ecbcc0af069cb6ddd29fef726f222a)"}
+!3 = !{!4, !8, i64 4}
+!4 = !{!"Pair", !5, i64 0, !8, i64 4}
+!5 = !{!"int", !6, i64 0}
+!6 = !{!"omnipotent char", !7, i64 0}
+!7 = !{!"Simple C/C++ TBAA"}
+!8 = !{!"long", !6, i64 0}
+!9 = distinct !{!9, !10}
+!10 = !{!"llvm.loop.mustprogress"}
 No newline at end of file

llvm/test/Analysis/Delinearization/array_of_struct3.ll

+; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s
+; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
+
+; CHECK:      Inst:  %3 = load double, double* %b, align 1, !tbaa !3
+; CHECK-NEXT: In Loop with Header: for.cond6
+; CHECK-NEXT: AccessFunction: {{\{\{\{}}(4 + (-13 * %n * %m)),+,(13 * %n * %m)}<%for.cond>,+,(13 * %m)}<%for.cond1>,+,13}<%for.cond6>
+; CHECK-NEXT: Base offset: %f1
+; CHECK-NEXT: ArrayDecl[UnknownSize][%n][%m][13]
+; CHECK-NEXT: ArrayRef[{-1,+,1}<nsw><%for.cond>][{0,+,1}<nuw><nsw><%for.cond1>][{0,+,1}<nuw><nsw><%for.cond6>][4]
+
+; CHECK:      AccessFunction: {{\{\{\{}}4,+,(13 * %n * %m)}<%for.cond>,+,(13 * %m)}<%for.cond1>,+,13}<%for.cond6>
+; CHECK-NEXT: Base offset: %f1
+; CHECK-NEXT: ArrayDecl[UnknownSize][%n][%m][13]
+; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.cond>][{0,+,1}<nuw><nsw><%for.cond1>][{0,+,1}<nuw><nsw><%for.cond6>][4]
+
+; struct __attribute__((packed)) MyS {
+;   float a;
+;   double b;
+;   char c;
+; };
+; void foo(long long n, long long m, struct MyS f1[][n][m]) {
+;   for (int i = 0; i < 1024; i++)
+;     for (int j = 0; j < n; j++)
+;       for (int k = 0; k < m; k++)
+;         f1[i][j][k].b = f1[i-1][j][k].b;
+; }
+
+source_filename = "array_of_struct2.c"
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.MyS = type <{ float, double, i8 }>
+
+; Function Attrs: nounwind uwtable
+define dso_local void @foo(i64 %n, i64 %m, %struct.MyS* %f1) #0 {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc26, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc27, %for.inc26 ]
+  %cmp = icmp ult i32 %i.0, 1024
+  br i1 %cmp, label %for.cond1.preheader, label %for.end28
+
+for.cond1.preheader:                              ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.cond1.preheader, %for.inc23
+  %j.0 = phi i32 [ %inc24, %for.inc23 ], [ 0, %for.cond1.preheader ]
+  %conv = zext i32 %j.0 to i64
+  %cmp2 = icmp slt i64 %conv, %n
+  br i1 %cmp2, label %for.cond6.preheader, label %for.inc26
+
+for.cond6.preheader:                              ; preds = %for.cond1
+  br label %for.cond6
+
+for.cond6:                                        ; preds = %for.cond6.preheader, %for.body11
+  %k.0 = phi i32 [ %inc, %for.body11 ], [ 0, %for.cond6.preheader ]
+  %conv7 = zext i32 %k.0 to i64
+  %cmp8 = icmp slt i64 %conv7, %m
+  br i1 %cmp8, label %for.body11, label %for.inc23
+
+for.body11:                                       ; preds = %for.cond6
+  %sub = add nsw i32 %i.0, -1
+  %idxprom = sext i32 %sub to i64
+  %0 = mul nuw i64 %n, %m
+  %1 = mul nsw i64 %0, %idxprom
+  %arrayidx = getelementptr inbounds %struct.MyS, %struct.MyS* %f1, i64 %1
+  %idxprom12 = zext i32 %j.0 to i64
+  %2 = mul nsw i64 %idxprom12, %m
+  %arrayidx13 = getelementptr inbounds %struct.MyS, %struct.MyS* %arrayidx, i64 %2
+  %idxprom14 = zext i32 %k.0 to i64
+  %arrayidx15 = getelementptr inbounds %struct.MyS, %struct.MyS* %arrayidx13, i64 %idxprom14
+  %b = getelementptr inbounds %struct.MyS, %struct.MyS* %arrayidx15, i64 0, i32 1
+  %3 = load double, double* %b, align 1, !tbaa !3
+  %idxprom16 = zext i32 %i.0 to i64
+  %4 = mul nuw i64 %n, %m
+  %5 = mul nsw i64 %4, %idxprom16
+  %arrayidx17 = getelementptr inbounds %struct.MyS, %struct.MyS* %f1, i64 %5
+  %idxprom18 = zext i32 %j.0 to i64
+  %6 = mul nsw i64 %idxprom18, %m
+  %arrayidx19 = getelementptr inbounds %struct.MyS, %struct.MyS* %arrayidx17, i64 %6
+  %idxprom20 = zext i32 %k.0 to i64
+  %arrayidx21 = getelementptr inbounds %struct.MyS, %struct.MyS* %arrayidx19, i64 %idxprom20
+  %b22 = getelementptr inbounds %struct.MyS, %struct.MyS* %arrayidx21, i64 0, i32 1
+  store double %3, double* %b22, align 1, !tbaa !3
+  %inc = add nuw nsw i32 %k.0, 1
+  br label %for.cond6, !llvm.loop !9
+
+for.inc23:                                        ; preds = %for.cond6
+  %inc24 = add nuw nsw i32 %j.0, 1
+  br label %for.cond1, !llvm.loop !11
+
+for.inc26:                                        ; preds = %for.cond1
+  %inc27 = add nuw nsw i32 %i.0, 1
+  br label %for.cond, !llvm.loop !12
+
+for.end28:                                        ; preds = %for.cond
+  ret void
+}
+
+; Function Attrs: argmemonly nofree nosync nounwind willreturn
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
+
+; Function Attrs: argmemonly nofree nosync nounwind willreturn
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1
+
+attributes #0 = { nounwind uwtable "frame-pointer"="none" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+attributes #1 = { argmemonly nofree nosync nounwind willreturn }
+
+!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{i32 7, !"uwtable", i32 1}
+!2 = !{!"clang version 14.0.0 (/home/meinersbur/src/llvm-project/clang 8f792707c4e5208bba08d837504c93de28b1f209)"}
+!3 = !{!4, !8, i64 4}
+!4 = !{!"MyS", !5, i64 0, !8, i64 4, !6, i64 12}
+!5 = !{!"float", !6, i64 0}
+!6 = !{!"omnipotent char", !7, i64 0}
+!7 = !{!"Simple C/C++ TBAA"}
+!8 = !{!"double", !6, i64 0}
+!9 = distinct !{!9, !10}
+!10 = !{!"llvm.loop.mustprogress"}
+!11 = distinct !{!11, !10}
+!12 = distinct !{!12, !10}

llvm/test/Analysis/Delinearization/byte_offset.ll

 ; RUN: opt < %s -analyze -enable-new-pm=0 -delinearize | FileCheck %s
 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 
+; CHECK: Inst:  store float 0.000000e+00, float* %ptr, align 4
+; CHECK: In Loop with Header: inner.loop
 ; CHECK: AccessFunction: ({0,+,%i2}<%outer.loop> + %unknown)
-; CHECK-NEXT: failed to delinearize
+; CHECK: Base offset: %A
+; CHECK: ArrayDecl[UnknownSize][%i2][4]
+; CHECK: ArrayRef[0][0][({0,+,%i2}<%outer.loop> + %unknown)]
 
 ; void foo(char A[], long i2, bool c) {
 ;   for (long i = 0; ; ++i) {
 ;     char *tmp = &A[i * i2];
 ;     if (c)
 ;       while (1)
 ;          *((float*)&tmp[arg << arg]) = 0;
 ;   }

llvm/test/Analysis/Delinearization/constant_functions_multi_dim.ll

 ; RUN: opt -passes='print<delinearization>' -disable-output < %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; CHECK:      Inst:  %tmp = load float, float* %arrayidx, align 4
 ; CHECK-NEXT: In Loop with Header: for.inc
 ; CHECK-NEXT: AccessFunction: {(4 * %N * %call),+,4}<nsw><%for.inc>
 ; CHECK-NEXT: Base offset: %A
-; CHECK-NEXT: ArrayDecl[UnknownSize][%N] with elements of 4 bytes.
-; CHECK-NEXT: ArrayRef[%call][{0,+,1}<nuw><nsw><%for.inc>]
+; CHECK-NEXT: ArrayDecl[UnknownSize][%N][4]
+; CHECK-NEXT: ArrayRef[%call][{0,+,1}<nuw><nsw><%for.inc>][0]
 
 ; CHECK:      Inst:  %tmp5 = load float, float* %arrayidx4, align 4
 ; CHECK-NEXT: In Loop with Header: for.inc
 ; CHECK-NEXT: AccessFunction: {(4 * %call1),+,(4 * %N)}<nsw><%for.inc>
 ; CHECK-NEXT: Base offset: %B
-; CHECK-NEXT: ArrayDecl[UnknownSize][%N] with elements of 4 bytes.
-; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.inc>][%call1]
+; CHECK-NEXT: ArrayDecl[UnknownSize][%N][4]
+; CHECK-NEXT: ArrayRef[{0,+,1}<nuw><nsw><%for.inc>][%call1][0]
 
 ; Function Attrs: noinline nounwind uwtable
 define void @mat_mul(float* %C, float* %A, float* %B, i64 %N) #0 !kernel_arg_addr_space !2 !kernel_arg_access_qual !3 !kernel_arg_type !4 !kernel_arg_base_type !4 !kernel_arg_type_qual !5 {
 entry:
   br label %entry.split
 
 entry.split:                                      ; preds = %entry
   %call = tail call i64 @_Z13get_global_idj(i32 0) #3

llvm/test/Analysis/Delinearization/divide_by_one.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-p:32:32-i1:32-i64:64-a:0-n32"
 
 ; Check that division by 1 can be delinearized.
 ;
 ; void test1(unsigned char *dst, int stride, int bs) {
 ;   for (int r = bs; r >= 0; --r)
 ;     for (int c = 0; c < bs; ++c)
 ;       dst[r * stride + c] = dst[(r + 1) * stride + c - 1];
 ; }
 
 ; AddRec: {{(-1 + ((1 + %bs) * %stride)),+,(-1 * %stride)}<%for.cond1.preheader>,+,1}<nw><%for.body3>
 ; CHECK: Inst:  %0 = load i8, i8* %arrayidx, align 1
 ; CHECK: Base offset: %dst
-; CHECK: ArrayDecl[UnknownSize][%stride] with elements of 1 bytes.
-; CHECK: ArrayRef[{(1 + %bs),+,-1}<nw><%for.cond1.preheader>][{-1,+,1}<nw><%for.body3>]
+; CHECK: ArrayDecl[UnknownSize][%stride][1]
+; CHECK: ArrayRef[{(1 + %bs),+,-1}<nw><%for.cond1.preheader>][{-1,+,1}<nw><%for.body3>][0]
 
 ; AddRec: {{(%stride * %bs),+,(-1 * %stride)}<%for.cond1.preheader>,+,1}<nw><%for.body3>
 ; CHECK: Inst:  store i8 %0, i8* %arrayidx7, align 1
 ; CHECK: Base offset: %dst
-; CHECK: ArrayDecl[UnknownSize][%stride] with elements of 1 bytes.
-; CHECK: ArrayRef[{%bs,+,-1}<nsw><%for.cond1.preheader>][{0,+,1}<nuw><nsw><%for.body3>]
+; CHECK: ArrayDecl[UnknownSize][%stride][1]
+; CHECK: ArrayRef[{%bs,+,-1}<nsw><%for.cond1.preheader>][{0,+,1}<nuw><nsw><%for.body3>][0]
 
 define void @test(i8* nocapture %dst, i32 %stride, i32 %bs) {
 entry:
   %cmp20 = icmp sgt i32 %bs, -1
   br i1 %cmp20, label %for.cond1.preheader.lr.ph, label %for.end9
 
 for.cond1.preheader.lr.ph:
   %cmp218 = icmp slt i32 0, %bs

llvm/test/Analysis/Delinearization/himeno_1.ll

 ;     for(i = 1; i < p_rows_sub; i++)
 ;       for(j = 1; j < p_cols_sub; j++)
 ;         for(k = 1; k < p_deps_sub; k++)
 ;           MR(a,0,i,j,k) = i + j + k;
 ; }
 
 ; AddRec: {{{(4 + (4 * (sext i32 %a.deps to i64) * (1 + (sext i32 %a.cols to i64))) + %a.base),+,(4 * (sext i32 %a.deps to i64) * (sext i32 %a.cols to i64))}<%for.i>,+,(4 * (sext i32 %a.deps to i64))}<%for.j>,+,4}<%for.k>
 ; CHECK: Base offset: %a.base
-; CHECK: ArrayDecl[UnknownSize][(sext i32 %a.cols to i64)][(sext i32 %a.deps to i64)] with elements of 4 bytes.
-; CHECK: ArrayRef[{1,+,1}<nuw><nsw><%for.i>][{1,+,1}<nuw><nsw><%for.j>][{1,+,1}<nuw><nsw><%for.k>]
+; CHECK: ArrayDecl[UnknownSize][(sext i32 %a.cols to i64)][(sext i32 %a.deps to i64)][4]
+; CHECK: ArrayRef[{1,+,1}<nuw><nsw><%for.i>][{1,+,1}<nuw><nsw><%for.j>][{1,+,1}<nuw><nsw><%for.k>][0]
 
 %struct.Mat = type { float*, i32, i32, i32, i32 }
 
 define void @jacobi(i32 %nn, %struct.Mat* nocapture %a, %struct.Mat* nocapture %p) nounwind uwtable {
 entry:
   %p.rows.ptr = getelementptr inbounds %struct.Mat, %struct.Mat* %p, i64 0, i32 2
   %p.rows = load i32, i32* %p.rows.ptr
   %p.rows.sub = add i32 %p.rows, -1

llvm/test/Analysis/Delinearization/himeno_2.ll

 ;     for(i = 1; i < p_rows_sub; i++)
 ;       for(j = 1; j < p_cols_sub; j++)
 ;         for(k = 1; k < p_deps_sub; k++)
 ;           MR(a,0,i,j,k) = i + j + k;
 ; }
 
 ; AddRec: {{{(4 + (4 * (sext i32 %a.deps to i64) * (1 + (sext i32 %a.cols to i64))) + %a.base),+,(4 * (sext i32 %a.deps to i64) * (sext i32 %a.cols to i64))}<%for.i>,+,(4 * (sext i32 %a.deps to i64))}<%for.j>,+,4}<%for.k>
 ; CHECK: Base offset: %a.base
-; CHECK: ArrayDecl[UnknownSize][(sext i32 %a.cols to i64)][(sext i32 %a.deps to i64)] with elements of 4 bytes.
-; CHECK: ArrayRef[{1,+,1}<nuw><nsw><%for.i>][{1,+,1}<nuw><nsw><%for.j>][{1,+,1}<nuw><nsw><%for.k>]
+; CHECK: ArrayDecl[UnknownSize][(sext i32 %a.cols to i64)][(sext i32 %a.deps to i64)][4]
+; CHECK: ArrayRef[{1,+,1}<nuw><nsw><%for.i>][{1,+,1}<nuw><nsw><%for.j>][{1,+,1}<nuw><nsw><%for.k>][0]
 
 %struct.Mat = type { float*, i32, i32, i32, i32 }
 
 define void @jacobi(i32 %nn, %struct.Mat* nocapture %a, %struct.Mat* nocapture %p) nounwind uwtable {
 entry:
   %p.rows.ptr = getelementptr inbounds %struct.Mat, %struct.Mat* %p, i64 0, i32 2
   %p.rows = load i32, i32* %p.rows.ptr
   %p.rows.sub = add i32 %p.rows, -1

llvm/test/Analysis/Delinearization/iv_times_constant_in_subscript.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 
 ; Derived from the following code:
 ;
 ; void foo(long n, long m, long b, double A[n][m]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       A[2i+b][2j] = 1.0;
 ; }
 
 ; AddRec: {{((%m * %b * 8) + %A),+,(2 * %m * 8)}<%for.i>,+,(2 * 8)}<%for.j>
 ; CHECK: Base offset: %A
-; CHECK: ArrayDecl[UnknownSize][%m] with elements of 8 bytes.
-; CHECK: ArrayRef[{%b,+,2}<nsw><%for.i>][{0,+,2}<nuw><%for.j>]
+; CHECK: ArrayDecl[UnknownSize][%m][8]
+; CHECK: ArrayRef[{%b,+,2}<nsw><%for.i>][{0,+,2}<nuw><%for.j>][0]
 
 
+; A[2i+b][2j][0]
+; A[(2*i+b)*m*8+2*j*8+0]
+; A[2*i*m*8+b*m*8+2*j*8+0]
+; A[i*m*16+b*m*8+j*16]
+
 define void @foo(i64 %n, i64 %m, i64 %b, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   %outerdim = mul nsw i64 %i, 2
   %outerdim2 = add nsw i64 %outerdim, %b

llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output  2>&1 | FileCheck %s
 
 ; void foo(long n, long m, long o, double A[n][m][o]) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i+3][j-4][k+7] = 1.0;
 ; }
 
 ; AddRec: {{{(56 + (8 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
 ; CHECK: Base offset: %A
-; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 8 bytes.
-; CHECK: ArrayRef[{3,+,1}<nuw><%for.i>][{-4,+,1}<nw><%for.j>][{7,+,1}<nuw><nsw><%for.k>]
+; CHECK: ArrayDecl[UnknownSize][%m][%o][8]
+; CHECK: ArrayRef[{3,+,1}<nuw><%for.i>][{-4,+,1}<nw><%for.j>][{7,+,1}<nuw><nsw><%for.k>][0]
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   br label %for.j

llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 
 ; void foo(long n, long m, long o, long p, double A[n][m][o+p]) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i+3][j-4][k+7] = 1.0;
 ; }
 
 ; AddRec: {{{(56 + (8 * (-4 + (3 * %m)) * (%o + %p)) + %A),+,(8 * (%o + %p) * %m)}<%for.cond4.preheader.lr.ph.us>,+,(8 * (%o + %p))}<%for.body6.lr.ph.us.us>,+,8}<%for.body6.us.us>
 ; CHECK: Base offset: %A
-; CHECK: ArrayDecl[UnknownSize][%m][(%o + %p)] with elements of 8 bytes.
-; CHECK: ArrayRef[{3,+,1}<nuw><%for.cond4.preheader.lr.ph.us>][{-4,+,1}<nw><%for.body6.lr.ph.us.us>][{7,+,1}<nw><%for.body6.us.us>]
+; CHECK: ArrayDecl[UnknownSize][%m][(%o + %p)][8]
+; CHECK: ArrayRef[{3,+,1}<nuw><%for.cond4.preheader.lr.ph.us>][{-4,+,1}<nw><%for.body6.lr.ph.us.us>][{7,+,1}<nw><%for.body6.us.us>][0]
 
 define void @foo(i64 %n, i64 %m, i64 %o, i64 %p, double* nocapture %A) nounwind uwtable {
 entry:
   %add = add nsw i64 %p, %o
   %cmp22 = icmp sgt i64 %n, 0
   br i1 %cmp22, label %for.cond1.preheader.lr.ph, label %for.end16
 
 for.cond1.preheader.lr.ph:                        ; preds = %entry

llvm/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 
 ; void foo(long n, long m, long o, double A[n][m][o], long p, long q, long r) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i+p][j+q][k+r] = 1.0;
 ; }
 
 ; AddRec: {{{((8 * ((((%m * %p) + %q) * %o) + %r)) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
 ; CHECK: Base offset: %A
-; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 8 bytes.
-; CHECK: ArrayRef[{%p,+,1}<nw><%for.i>][{%q,+,1}<nw><%for.j>][{%r,+,1}<nsw><%for.k>]
+; CHECK: ArrayDecl[UnknownSize][%m][%o][8]
+; CHECK: ArrayRef[{%p,+,1}<nw><%for.i>][{%q,+,1}<nw><%for.j>][{%r,+,1}<nsw><%for.k>][0]
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A, i64 %p, i64 %q, i64 %r) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   br label %for.j

llvm/test/Analysis/Delinearization/multidim_only_ivs_2d.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 
 ; Derived from the following code:
 ;
 ; void foo(long n, long m, double A[n][m]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       A[i][j] = 1.0;
 ; }
 
 ; Inst:  %val = load double, double* %arrayidx
 ; In Loop with Header: for.j
 ; AddRec: {{0,+,(%m * 8)}<%for.i>,+,8}<%for.j>
 ; Base offset: %A
-; ArrayDecl[UnknownSize][%m] with elements of 8 bytes.
-; ArrayRef[{0,+,1}<nuw><nsw><%for.i>][{0,+,1}<nuw><nsw><%for.j>]
+; ArrayDecl[UnknownSize][%m][8]
+; ArrayRef[{0,+,1}<nuw><nsw><%for.i>][{0,+,1}<nuw><nsw><%for.j>][0]
 
 ; Inst:  store double %val, double* %arrayidx
 ; In Loop with Header: for.j
 ; AddRec: {{%A,+,(8 * %m)}<%for.i>,+,8}<%for.j>
 ; CHECK: Base offset: %A
-; CHECK: ArrayDecl[UnknownSize][%m] with elements of 8 bytes.
-; CHECK: ArrayRef[{0,+,1}<nuw><nsw><%for.i>][{0,+,1}<nuw><nsw><%for.j>]
+; CHECK: ArrayDecl[UnknownSize][%m][8]
+; CHECK: ArrayRef[{0,+,1}<nuw><nsw><%for.i>][{0,+,1}<nuw><nsw><%for.j>][0]
 
 define void @foo(i64 %n, i64 %m, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   %tmp = mul nsw i64 %i, %m

llvm/test/Analysis/Delinearization/multidim_only_ivs_3d.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 
 ; void foo(long n, long m, long o, double A[n][m][o]) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i][j][k] = 1.0;
 ; }
 
 ; AddRec: {{{%A,+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
 ; CHECK: Base offset: %A
-; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 8 bytes.
-; CHECK: ArrayRef[{0,+,1}<nuw><nsw><%for.i>][{0,+,1}<nuw><nsw><%for.j>][{0,+,1}<nuw><nsw><%for.k>]
+; CHECK: ArrayDecl[UnknownSize][%m][%o][8]
+; CHECK: ArrayRef[{0,+,1}<nuw><nsw><%for.i>][{0,+,1}<nuw><nsw><%for.j>][{0,+,1}<nuw><nsw><%for.k>][0]
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   br label %for.j

llvm/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 ; void foo(int n, int m, int o, double A[n][m][o]) {
 ;
 ;   for (int i = 0; i < n; i++)
 ;     for (int j = 0; j < m; j++)
 ;       for (int k = 0; k < o; k++)
 ;         A[i][j][k] = 1.0;
 ; }
 
 ; AddRec: {{{%A,+,(8 * (zext i32 %m to i64) * (zext i32 %o to i64))}<%for.i>,+,(8 * (zext i32 %o to i64))}<%for.j>,+,8}<%for.k>
 ; CHECK: Base offset: %A
-; CHECK: ArrayDecl[UnknownSize][(zext i32 %m to i64)][(zext i32 %o to i64)] with elements of 8 bytes.
-; CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>]
+; CHECK: ArrayDecl[UnknownSize][(zext i32 %m to i64)][(zext i32 %o to i64)][8]
+; CHECK: ArrayRef[{0,+,1}<%for.i>][{0,+,1}<%for.j>][{0,+,1}<%for.k>][0]
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @foo(i32 %n, i32 %m, i32 %o, double* %A) {
 entry:
   %m_zext = zext i32 %m to i64
   %n_zext = zext i32 %o to i64

llvm/test/Analysis/Delinearization/parameter_addrec_product.ll

 ; RUN: opt -passes='print<delinearization>' -disable-output < %s 2>&1 | FileCheck %s
 ;
 ;    void foo(float *A, long *p) {
 ;      for (long i = 0; i < 100; i++)
 ;        for (long j = 0; j < 100; j++)
 ;          A[i * (*p) + j] += i + j;
 ;    }
 ;
-; CHECK: ArrayDecl[UnknownSize][%pval] with elements of 4 bytes.
-; CHECK: ArrayRef[{0,+,1}<nuw><nsw><%bb2>][{0,+,1}<nuw><nsw><%bb4>]
+; CHECK: ArrayDecl[UnknownSize][%pval][4]
+; CHECK: ArrayRef[{0,+,1}<nuw><nsw><%bb2>][{0,+,1}<nuw><nsw><%bb4>][0]
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @foo(float* %A, i64* %p) {
 bb:
   br label %bb2
 
 bb2:                                              ; preds = %bb16, %bb

polly/lib/Analysis/ScopDetection.cpp

for (const auto &Pair : Context.Accesses[BasePointer]) {
           return false;
       }
     }
     return false;
   }
   return true;
 }
 
+static bool isKnownLessOrEqual(ScalarEvolution &SE, const SCEV *LHS,
+                               const SCEV *RHS) {
+  return SE.isKnownPredicate(ICmpInst::ICMP_SLE, LHS, RHS);
+}
+
 // 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.
 bool ScopDetection::computeAccessFunctions(
     DetectionContext &Context, const SCEVUnknown *BasePointer,
if (!AF) {
       else
         IsNonAffine = true;
     } else {
       if (Shape->DelinearizedSizes.size() == 0) {
         Acc->DelinearizedSubscripts.push_back(AF);
       } else {
         llvm::computeAccessFunctions(SE, AF, Acc->DelinearizedSubscripts,
                                      Shape->DelinearizedSizes);
-        if (Acc->DelinearizedSubscripts.size() == 0)
+        if (Acc->DelinearizedSubscripts.size() == 0) {
+          IsNonAffine = true;
+        } else {
+          // TODO: Do not drop the last DelinearizedSubscripts. If non-zero it
+          // must be preseved for code-generation such that it represents the
+          // same pointer.
+          const SCEV *AccOffset = Acc->DelinearizedSubscripts.pop_back_val();
+          const SCEV *ArrSize = Shape->DelinearizedSizes.back();
+          const SCEV *AccSize = Context.ElementSize[BasePointer];
+          if (!AccOffset->isZero() ||
+              !isKnownLessOrEqual(SE, AccSize, ArrSize)) {
+            LLVM_DEBUG(dbgs()
+                       << "Accessed element bytes [" << *AccOffset << ",+"
+                       << *AccSize << ") possibly outside element [0,"
+                       << *ArrSize << ")\n");
             IsNonAffine = true;
           }
+        }
+      }
       for (const SCEV *S : Acc->DelinearizedSubscripts)
         if (!isAffine(S, Scope, Context))
           IsNonAffine = true;
     }
 
     // (Possibly) report non affine access
     if (IsNonAffine) {
       BasePtrHasNonAffine = true;

polly/test/ScopDetect/array_elt_byte_offset.ll

+; RUN: opt %loadPolly -polly-detect -disable-output -debug < %s 2>&1 | FileCheck %s
+
+; CHECK: Accessed element bytes [{{.+}},+4) possibly outside element [0,4)
+; REQUIRES: asserts
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.CCGFace = type { %struct.CCGFace*, i8*, i16, i16, i16, i16 }
+%struct.CCGVert = type { %struct.CCGVert*, i8*, i16, i16, i16, i16, %struct.CCGEdge**, %struct.CCGFace** }
+%struct.CCGEdge = type { %struct.CCGEdge*, i8*, i16, i16, float, %struct.CCGVert*, %struct.CCGVert*, %struct.CCGFace** }
+
+define void @ccgSubSurf__calcSubdivLevel() {
+entry:
+  %shl.i1795 = shl nuw i32 1, undef
+  %i = load i32, i32* undef, align 8
+  %shl.i.i = shl nuw i32 1, undef
+  %add.i.i = add nuw nsw i32 %shl.i.i, 1
+  %mul.i = mul nsw i32 %add.i.i, %add.i.i
+  %add.i1797 = add nsw i32 %mul.i, %add.i.i
+  %smax = call i32 @llvm.smax.i32(i32 %shl.i1795, i32 1)
+  %i1 = sext i32 %add.i1797 to i64
+  %i2 = sext i32 %i to i64
+  %i3 = load %struct.CCGFace*, %struct.CCGFace** undef, align 8
+  %i4 = load i16, i16* undef, align 8
+  %arrayidx.i.i.i.i = getelementptr inbounds %struct.CCGFace, %struct.CCGFace* %i3, i64 1
+  %i5 = bitcast %struct.CCGFace* %arrayidx.i.i.i.i to %struct.CCGVert**
+  %idxprom.i.i.i = sext i16 %i4 to i64
+  %arrayidx.i.i.i = getelementptr inbounds %struct.CCGVert*, %struct.CCGVert** %i5, i64 %idxprom.i.i.i
+  %arrayidx2.i.i = getelementptr inbounds %struct.CCGVert*, %struct.CCGVert** %arrayidx.i.i.i, i64 %idxprom.i.i.i
+  %i6 = bitcast %struct.CCGVert** %arrayidx2.i.i to i8*
+  %i7 = load i32, i32* undef, align 4
+  %wide.trip.count.i.us.us.us = zext i32 %i7 to i64
+  br label %for.cond10.preheader.us.us.us
+
+for.cond10.preheader.us.us.us:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.cond10.for.inc38_crit_edge.split.us.split.us.us.us.us ]
+  %i8 = mul nsw i64 %indvars.iv, %i1
+  %i9 = add nsw i64 %i8, 1
+  %i10 = mul nsw i64 %i9, %i2
+  %add.ptr.i.us.us.us = getelementptr inbounds i8, i8* %i6, i64 %i10
+  br label %for.cond14.preheader.us.us.us.us.us
+
+for.cond14.preheader.us.us.us.us.us:
+  br label %for.body18.us.us.us.us.us.us
+
+for.body18.us.us.us.us.us.us:
+  %x.04761.us.us.us.us.us.us = phi i32 [ 0, %for.cond14.preheader.us.us.us.us.us ], [ %add25.us.us.us.us.us.us, %VertDataAvg4.exit.loopexit.us.us.us.us.us.us ]
+  %mul8.i.us.us.us.us.us.us = shl i32 undef, undef
+  %add9.i.us.us.us.us.us.us = add nsw i32 %mul8.i.us.us.us.us.us.us, %add.i.i
+  %mul10.i.us.us.us.us.us.us = mul nsw i32 %add9.i.us.us.us.us.us.us, %i
+  %idxprom.i.us.us.us.us.us.us = sext i32 %mul10.i.us.us.us.us.us.us to i64
+  %arrayidx.i.us.us.us.us.us.us = getelementptr inbounds i8, i8* %add.ptr.i.us.us.us, i64 %idxprom.i.us.us.us.us.us.us
+  %i11 = bitcast i8* %arrayidx.i.us.us.us.us.us.us to float*
+  %add25.us.us.us.us.us.us = add nuw nsw i32 %x.04761.us.us.us.us.us.us, 1
+  br label %for.body.i.us.us.us.us.us.us
+
+for.body.i.us.us.us.us.us.us:
+  %indvars.iv.i.us.us.us.us.us.us = phi i64 [ 0, %for.body18.us.us.us.us.us.us ], [ %indvars.iv.next.i.us.us.us.us.us.us, %for.body.i.us.us.us.us.us.us ]
+  %arrayidx.i1890.us.us.us.us.us.us = getelementptr inbounds float, float* %i11, i64 %indvars.iv.i.us.us.us.us.us.us
+  %i12 = load float, float* %arrayidx.i1890.us.us.us.us.us.us, align 4
+  %indvars.iv.next.i.us.us.us.us.us.us = add nuw nsw i64 %indvars.iv.i.us.us.us.us.us.us, 1
+  %exitcond.not.i.us.us.us.us.us.us = icmp eq i64 %indvars.iv.next.i.us.us.us.us.us.us, %wide.trip.count.i.us.us.us
+  br i1 %exitcond.not.i.us.us.us.us.us.us, label %VertDataAvg4.exit.loopexit.us.us.us.us.us.us, label %for.body.i.us.us.us.us.us.us
+
+VertDataAvg4.exit.loopexit.us.us.us.us.us.us:
+  %exitcond.not = icmp eq i32 %add25.us.us.us.us.us.us, %smax
+  br i1 %exitcond.not, label %for.cond14.for.inc35_crit_edge.split.us.us.us.us.us.us, label %for.body18.us.us.us.us.us.us
+
+for.cond14.for.inc35_crit_edge.split.us.us.us.us.us.us:
+  br i1 undef, label %for.cond10.for.inc38_crit_edge.split.us.split.us.us.us.us, label %for.cond14.preheader.us.us.us.us.us
+
+for.cond10.for.inc38_crit_edge.split.us.split.us.us.us.us:
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond10.preheader.us.us.us
+}
+
+declare i32 @llvm.smax.i32(i32, i32)
+