[Polly] Delinearize _all_ accesses to a multi-dimensional array

[grosser]

Summary

Even though we previously correctly detected the multi-dimensional access
pattern for accesses with a certain base address, we only delinearized
non-affine accesses to this address. Affine accesses have not been touched and
remained as single dimensional accesses. The result was an inconsistent
description of accesses to the same array, with some being one dimensional and
some being multi-dimensional.

This patch ensures that all accesses are delinearized with the same
dimensionality as soon as a single one of them has been detected as non-affine.

While writing this patch, it became evident that the options
-polly-allow-nonaffine and -polly-detect-keep-going have not been properly
supported in case delinearization has been turned on. This patch adds relevant
test coverage and addresses these issues as well. We also added some more
documentation to the functions that are modified in this patch.

TODO: The documentation and the structure of this function is possibly still

non-perfect. If reviewers can suggest ways to further improve the
readability of this function, such comments are appreciated. Maybe we
should outline some of the computations performed in
hasAffineMemoryAccesses()?

This fixes llvm.org/PR20123

[jdoerfert]

some minor comments.

lib/Analysis/ScopDetection.cpp

369–371

What does PIAF mean?

376

Did I miss an assignment of IsNonAffine or is this check always false?

389

Could you use a cast or an assert here to indicate that we "know" it is an AddRec?

419

The nested if statements make this harder to understand than it actually is.

Maybe we should just copy the isEmpty check, first if it is empty, then if it is not.

431

Above you used continue here, then reported the invalid access and checked for kepp going, I like that way (the one above) better. Maybe you could even put the two into a small function.

478

Shouldn't we at least detect them and bail?

Do we have a test case for this?

test/ScopDetectionDiagnostics/ReportMultipleNonAffineAccesses.ll

56

Not needed.

test/ScopInfo/multidim_single_and_multidim_array.ll

8

Not needed.

39

Nice test case.

[sebpop]

lib/Analysis/ScopDetection.cpp

369–371

Pair <Instruction, AccessFunction>

419

It is simpler to read the if statements when the short clause comes first:

if (Shape->DelinearizedSizes.empty()) {
  IsNonAffine = true;
} else {
  [...]
  if (Acc->DelinearizedSubscripts.empty()) {
    IsNonAffine = true;
  } else {
     // Long clause goes here.
     [...]
  }
}

[grosser]

Hi Johannes, hi Sebastian

thanks for the review. It was very valuable and nicely improved this patch. I will send an updated version right after.

lib/Analysis/ScopDetection.cpp

369–371

Pair-Instruction-AliasFunction

Yes, this is definitely an abbreviation that is not well known. It was here before, but I can change it to just 'Pair'. That should be clear, as we extract the two elements in the following two lines.

376

Good catch. In fact this part was just wrong. In case this is not a SCEVAddRecExpr, we should not report the full array as non-affine, but instead just do not collect parametric terms there. If I would just have fixed the code as written, every constant access e.g. A[0][0] would have broken the delinearization.

I added this case to the test case submitted later in this patch.

389

Unfortunately we don't know. In case this is not a SCEVAddRecExpr, we now assume (and verify) the access corresponds to the innermost dimension.

419

I pulled out the reporting of a failed delinearization. This removed one level of indentation.

431

I had this before. The problem is that the code for this reporting would then be replicated a couple of times. I also thought about using a separate function, but as the result of the reporting can have control flow implications, I can not make this a simple function call, but would need something like the following for every case where we assign IsNonAffine:

if (reportAndCheckForReturn(Inst, S, &GlobalNonAffine)
  return false;

The other changes allowed a couple of simplifications. Maybe it is now already simple enough.

478

This is somehow unrelated, but you are right it should be fixed. I added a separate patch that fixes this issue before we perform the actual all-accesses patch.

test/ScopDetectionDiagnostics/ReportMultipleNonAffineAccesses.ll

56

Removed data layout and triple.

test/ScopInfo/multidim_single_and_multidim_array.ll

8

Removed the triple, the data-layout is required for -polly-scops.

[grosser]

A new patch:

"Check that the elements of an array have the same size"

And some updates to

"Delinearize _all_ accesses to a multi-dimensional array"

to address Johannes' review comments.

[dpeixott]

include/polly/ScopDetectionDiagnostic.h

90

The rrkDifferentElementSize enum value should go above rrkLastAffFunc because ReportDifferentArrayElementSize is a subclass of ReportAffFunc. Otherwise

isa<ReportAffFunc>(ReportDifferentArrayElementSize)

will be false.

[grosser]

Address David's comment

[sebpop]

LGTM

[grosser]

Update the ReportDifferentElementSize.ll test case

For some reason, a wrong test case file slipped in, which did not test for the
right error.

[jdoerfert]

LGTM.

[grosser]

Closed by commit rL217727 (authored by @grosser).

[grosser]

Closed by commit rL217728 (authored by @grosser).

include/polly/ScopDetection.h

 #ifndef POLLY_SCOP_DETECTION_H
 #define POLLY_SCOP_DETECTION_H
 
 #include "llvm/Pass.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 
 #include "polly/ScopDetectionDiagnostic.h"
 
+#include "llvm/ADT/SetVector.h"
+
 #include <set>
 #include <map>
 
 using namespace llvm;
 
 namespace llvm {
 class RegionInfo;
 class Region;
struct MemAcc {
   // Subscripts computed by delinearization.
   SmallVector<const SCEV *, 4> DelinearizedSubscripts;
 
   MemAcc(const Instruction *I, ArrayShape *S)
       : Insn(I), Shape(S), DelinearizedSubscripts() {}
 };
 
 typedef std::map<const Instruction *, MemAcc *> MapInsnToMemAcc;
-typedef std::pair<const Instruction *, const SCEVAddRecExpr *> PairInsnAddRec;
-typedef std::vector<PairInsnAddRec> AFs;
+typedef std::pair<const Instruction *, 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;
 
 /// @brief A function attribute which will cause Polly to skip the function
 extern llvm::StringRef PollySkipFnAttr;
class ScopDetection : public FunctionPass {
 
   /// @brief Context variables for SCoP detection.
   struct DetectionContext {
     Region &CurRegion;   // The region to check.
     AliasSetTracker AST; // The AliasSetTracker to hold the alias information.
     bool Verifying;      // If we are in the verification phase?
     RejectLog Log;
 
-    // Map a base pointer to all access functions accessing it.
-    BaseToAFs NonAffineAccesses, AffineAccesses;
+    /// @brief Map a base pointer to all access functions accessing it.
+    ///
+    /// This map is indexed by the base pointer. Each element of the map
+    /// is a list of memory accesses that reference this base pointer.
+    BaseToAFs Accesses;
+
+    /// @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;
 
     DetectionContext(Region &R, AliasAnalysis &AA, bool Verify)
         : CurRegion(R), AST(AA), Verifying(Verify), Log(&R) {}
   };
 
   // Remember the valid regions
   typedef std::set<const Region *> RegionSet;

include/polly/ScopDetectionDiagnostic.h

enum RejectReasonKind {
   rrkInvalidCond,
   rrkUndefOperand,
   rrkNonAffBranch,
   rrkNoBasePtr,
   rrkUndefBasePtr,
   rrkVariantBasePtr,
   rrkNonAffineAccess,
   rrkLastAffFunc,
+  rrkDifferentElementSize,
 
   // IndVar
   rrkIndVar,
   rrkPhiNodeRefInRegion,
   rrkNonCanonicalPhiNode,
   rrkLoopHeader,
   rrkLastIndVar,
 
public:
   /// @name RejectReason interface
   //@{
   virtual std::string getMessage() const override;
   virtual std::string getEndUserMessage() const override;
   //@}
 };
 
 //===----------------------------------------------------------------------===//
+/// @brief Report array accesses with differing element size.
+class ReportDifferentArrayElementSize : public ReportAffFunc {
+  //===--------------------------------------------------------------------===//
+
+  // The base pointer of the memory access.
+  const Value *BaseValue;
+
+public:
+  ReportDifferentArrayElementSize(const Instruction *Inst, const Value *V)
+      : ReportAffFunc(rrkDifferentElementSize, Inst), BaseValue(V) {}
+
+  /// @name LLVM-RTTI interface
+  //@{
+  static bool classof(const RejectReason *RR);
+  //@}
+
+  /// @name RejectReason interface
+  //@{
+  virtual std::string getMessage() const override;
+  virtual std::string getEndUserMessage() const override;
+  //@}
+};
+
+//===----------------------------------------------------------------------===//
 /// @brief Base class for reject reasons related to induction variables.
 ///
 //  ReportIndVar reject reasons are generated when the ScopDetection finds
 /// errors in the induction variable(s) of the Scop candidate.
 class ReportIndVar : public RejectReason {
   //===--------------------------------------------------------------------===//
 public:
   ReportIndVar(const RejectReasonKind K);

lib/Analysis/ScopDetection.cpp

bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const {
   }
 
   return true;
 }
 
 MapInsnToMemAcc InsnToMemAcc;
 
 bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const {
-  for (auto P : Context.NonAffineAccesses) {
-    const SCEVUnknown *BasePointer = P.first;
+  for (const SCEVUnknown *BasePointer : Context.NonAffineAccesses) {
     Value *BaseValue = BasePointer->getValue();
     ArrayShape *Shape = new ArrayShape(BasePointer);
+    bool BasePtrHasNonAffine = false;
 
     // First step: collect parametric terms in all array references.
     SmallVector<const SCEV *, 4> Terms;
-    for (PairInsnAddRec PIAF : Context.NonAffineAccesses[BasePointer])
-      PIAF.second->collectParametricTerms(*SE, Terms);
+    for (const auto &Pair : Context.Accesses[BasePointer]) {
+      const SCEVAddRecExpr *AccessFunction =
+          dyn_cast<SCEVAddRecExpr>(Pair.second);
 
-    // Also collect terms from the affine memory accesses.
-    for (PairInsnAddRec PIAF : Context.AffineAccesses[BasePointer])
-      PIAF.second->collectParametricTerms(*SE, Terms);
+      if (AccessFunction)
+        AccessFunction->collectParametricTerms(*SE, Terms);
+    }
 
     // Second step: find array shape.
     SE->findArrayDimensions(Terms, Shape->DelinearizedSizes,
                             Context.ElementSize[BasePointer]);
 
-    // Third step: compute the access functions for each subscript.
-    for (PairInsnAddRec PIAF : Context.NonAffineAccesses[BasePointer]) {
-      const SCEVAddRecExpr *AF = PIAF.second;
-      const Instruction *Insn = PIAF.first;
-      if (Shape->DelinearizedSizes.empty())
-        return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF,
-                                              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 SCEV *AF = Pair.second;
+
+        if (!isAffineExpr(&Context.CurRegion, AF, *SE, 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 SCEVAddRecExpr *AF = dyn_cast<SCEVAddRecExpr>(Pair.second);
+      bool IsNonAffine = false;
       MemAcc *Acc = new MemAcc(Insn, Shape);
-      InsnToMemAcc.insert({Insn, Acc});
+      TempMemoryAccesses.insert({Insn, Acc});
+
+      if (!AF) {
+        if (isAffineExpr(&Context.CurRegion, Pair.second, *SE, BaseValue))
+          Acc->DelinearizedSubscripts.push_back(Pair.second);
+        else
+          IsNonAffine = true;
+      } else {
         AF->computeAccessFunctions(*SE, Acc->DelinearizedSubscripts,
                                    Shape->DelinearizedSizes);
-      if (Shape->DelinearizedSizes.empty() ||
-          Acc->DelinearizedSubscripts.empty())
-        return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF,
-                                              Insn, BaseValue);
-
-      // Check that the delinearized subscripts are affine.
+        if (Acc->DelinearizedSubscripts.size() == 0)
+          IsNonAffine = true;
         for (const SCEV *S : Acc->DelinearizedSubscripts)
           if (!isAffineExpr(&Context.CurRegion, S, *SE, BaseValue))
-          return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF,
-                                                Insn, BaseValue);
+            IsNonAffine = true;
+      }
+
+      // (Possibly) report non affine access
+      if (IsNonAffine) {
+        BasePtrHasNonAffine = true;
+        if (!AllowNonAffine)
+          invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Insn,
+                                         BaseValue);
+        if (!KeepGoing && !AllowNonAffine)
+          return false;
+      }
     }
+
+    if (!BasePtrHasNonAffine)
+      InsnToMemAcc.insert(TempMemoryAccesses.begin(), TempMemoryAccesses.end());
   }
   return true;
 }
 
 bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
                                         DetectionContext &Context) const {
   Value *Ptr = getPointerOperand(Inst);
   Loop *L = LI->getLoopFor(Inst.getParent());
if (!isInvariant(*BaseValue, Context.CurRegion))
     // Verification of this property is difficult as the independent blocks
     // pass may introduce aliasing that we did not have when running the
     // scop detection.
     return invalid<ReportVariantBasePtr>(Context, /*Assert=*/false, BaseValue,
                                          &Inst);
 
   AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
 
-  if (AllowNonAffine) {
-    // Do not check whether AccessFunction is affine.
-  } else if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE,
-                           BaseValue)) {
-    const SCEVAddRecExpr *AF = dyn_cast<SCEVAddRecExpr>(AccessFunction);
+  const SCEV *Size = SE->getElementSize(&Inst);
+  if (Context.ElementSize.count(BasePointer)) {
+    if (Context.ElementSize[BasePointer] != Size)
+      return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true,
+                                                      &Inst, BaseValue);
+  } else {
+    Context.ElementSize[BasePointer] = Size;
+  }
+
+  if (PollyDelinearize) {
+    Context.Accesses[BasePointer].push_back({&Inst, AccessFunction});
 
-    if (!PollyDelinearize || !AF)
+    if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue))
+      Context.NonAffineAccesses.insert(BasePointer);
+  } else if (!AllowNonAffine) {
+    if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue))
       return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
                                             AccessFunction, &Inst, BaseValue);
-
-    const SCEV *ElementSize = SE->getElementSize(&Inst);
-    Context.ElementSize[BasePointer] = ElementSize;
-
-    // Collect all non affine memory accesses, and check whether they are linear
-    // at the end of scop detection. That way we can delinearize all the memory
-    // accesses to the same array in a unique step.
-    Context.NonAffineAccesses[BasePointer].push_back({&Inst, AF});
-  } else if (const SCEVAddRecExpr *AF =
-                 dyn_cast<SCEVAddRecExpr>(AccessFunction)) {
-    Context.AffineAccesses[BasePointer].push_back({&Inst, AF});
   }
 
   // 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);
 
   if (IgnoreAliasing)

lib/Analysis/ScopDetectionDiagnostic.cpp

std::string ReportVariantBasePtr::getEndUserMessage() const {
   return "The base address of this array is not invariant inside the loop";
 }
 
 bool ReportVariantBasePtr::classof(const RejectReason *RR) {
   return RR->getKind() == rrkVariantBasePtr;
 }
 
 //===----------------------------------------------------------------------===//
+// ReportDifferentArrayElementSize
+
+std::string ReportDifferentArrayElementSize::getMessage() const {
+  return "Access to one array through data types of different size";
+}
+
+bool ReportDifferentArrayElementSize::classof(const RejectReason *RR) {
+  return RR->getKind() == rrkDifferentElementSize;
+}
+
+std::string ReportDifferentArrayElementSize::getEndUserMessage() const {
+  llvm::StringRef BaseName = BaseValue->getName();
+  std::string Name = (BaseName.size() > 0) ? BaseName : "UNKNOWN";
+  return "The array \"" + Name + "\" is accessed through elements that differ "
+                                 "in size";
+}
+
+//===----------------------------------------------------------------------===//
 // ReportNonAffineAccess.
 
 std::string ReportNonAffineAccess::getMessage() const {
   return "Non affine access function: " + *AccessFunction;
 }
 
 bool ReportNonAffineAccess::classof(const RejectReason *RR) {
   return RR->getKind() == rrkNonAffineAccess;

test/ScopDetectionDiagnostics/ReportDifferentElementSize.ll

+; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s
+
+;void f(int A[], int B[]) {
+;  for (int i=0; i<42; i++)
+;    A[i] = B[i];
+;}
+
+; CHECK: remark: :2:8: The following errors keep this region from being a Scop.
+; CHECK-NEXT: remark: :3:5: Accesses to the arrays "A", "B" may access the same memory.
+; CHECK-NEXT: remark: :3:5: Invalid Scop candidate ends here.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32* %B) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  tail call void @llvm.dbg.value(metadata !{i32* %A}, i64 0, metadata !13), !dbg !14
+  tail call void @llvm.dbg.value(metadata !{i32* %B}, i64 0, metadata !15), !dbg !16
+  tail call void @llvm.dbg.value(metadata !17, i64 0, metadata !18), !dbg !20
+  br label %for.body, !dbg !21
+
+for.body:                                         ; preds = %entry.split, %for.body
+  %indvar = phi i64 [ 0, %entry.split ], [ %indvar.next, %for.body ]
+  %arrayidx = getelementptr i32* %B, i64 %indvar, !dbg !22
+  %arrayidx2 = getelementptr i32* %A, i64 %indvar, !dbg !22
+  %0 = load i32* %arrayidx, align 4, !dbg !22
+  store i32 %0, i32* %arrayidx2, align 4, !dbg !22
+  tail call void @llvm.dbg.value(metadata !{null}, i64 0, metadata !18), !dbg !20
+  %indvar.next = add i64 %indvar, 1, !dbg !21
+  %exitcond = icmp ne i64 %indvar.next, 42, !dbg !21
+  br i1 %exitcond, label %for.body, label %for.end, !dbg !21
+
+for.end:                                          ; preds = %for.body
+  ret void, !dbg !23
+}
+
+declare void @llvm.dbg.declare(metadata, metadata)
+declare void @llvm.dbg.value(metadata, i64, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!10, !11}
+!llvm.ident = !{!12}
+
+!0 = metadata !{i32 786449, metadata !1, i32 12, metadata !"clang version 3.6.0 ", i1 false, metadata !"", i32 0, metadata !2, metadata !2, metadata !3, metadata !2, metadata !2, metadata !"", i32 1}
+!1 = metadata !{metadata !"", metadata !"test/ScopDetectionDiagnostic/"}
+!2 = metadata !{}
+!3 = metadata !{metadata !4}
+!4 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"f", metadata !"f", metadata !"", i32 1, metadata !6, i1 false, i1 true, i32 0, i32 0, null, i32 256, i1 false, void (i32*, i32*)* @f, null, null, metadata !2, i32 1} ; [ DW_TAG_subprogram ] [line 1] [def] [f]
+!5 = metadata !{i32 786473, metadata !1}
+!6 = metadata !{i32 786453, i32 0, null, metadata !"", i32 0, i64 0, i64 0, i64 0, i32 0, null, metadata !7, i32 0, null, null, null} ; [ DW_TAG_subroutine_type ] [line 0, size 0, align 0, offset 0] [from ]
+!7 = metadata !{null, metadata !8, metadata !8}
+!8 = metadata !{i32 786447, null, null, metadata !"", i32 0, i64 64, i64 64, i64 0, i32 0, metadata !9} ; [ DW_TAG_pointer_type ] [line 0, size 64, align 64, offset 0] [from int]
+!9 = metadata !{i32 786468, null, null, metadata !"int", i32 0, i64 32, i64 32, i64 0, i32 0, i32 5} ; [ DW_TAG_base_type ] [int] [line 0, size 32, align 32, offset 0, enc DW_ATE_signed]
+!10 = metadata !{i32 2, metadata !"Dwarf Version", i32 4}
+!11 = metadata !{i32 2, metadata !"Debug Info Version", i32 1}
+!12 = metadata !{metadata !"clang version 3.6.0 "}
+!13 = metadata !{i32 786689, metadata !4, metadata !"A", metadata !5, i32 16777217, metadata !8, i32 0, i32 0} ; [ DW_TAG_arg_variable ] [A] [line 1]
+!14 = metadata !{i32 1, i32 12, metadata !4, null}
+!15 = metadata !{i32 786689, metadata !4, metadata !"B", metadata !5, i32 33554433, metadata !8, i32 0, i32 0} ; [ DW_TAG_arg_variable ] [B] [line 1]
+!16 = metadata !{i32 1, i32 21, metadata !4, null}
+!17 = metadata !{i32 0}
+!18 = metadata !{i32 786688, metadata !19, metadata !"i", metadata !5, i32 2, metadata !9, i32 0, i32 0} ; [ DW_TAG_auto_variable ] [i] [line 2]
+!19 = metadata !{i32 786443, metadata !1, metadata !4, i32 2, i32 3, i32 0, i32 0}
+!20 = metadata !{i32 2, i32 12, metadata !19, null}
+!21 = metadata !{i32 2, i32 8, metadata !19, null}
+!22 = metadata !{i32 3, i32 5, metadata !19, null}
+!23 = metadata !{i32 4, i32 1, metadata !4, null}

test/ScopDetectionDiagnostics/ReportMultipleNonAffineAccesses.ll

+; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s
+; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-detect-keep-going -analyze < %s 2>&1| FileCheck %s -check-prefix=ALL
+; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-delinearize -analyze < %s 2>&1| FileCheck %s -check-prefix=DELIN
+; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-delinearize -polly-detect-keep-going -analyze < %s 2>&1| FileCheck %s -check-prefix=DELIN-ALL
+; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-allow-nonaffine -analyze < %s 2>&1| FileCheck %s -check-prefix=NONAFFINE
+; RUN: opt %loadPolly -basicaa -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -polly-delinearize -polly-allow-nonaffine -analyze < %s 2>&1| FileCheck %s -check-prefix=NONAFFINE
+
+;  1 void manyaccesses(float A[restrict], long n, float B[restrict][n])
+;  2 {
+;  3   for (long i = 0; i < 1024; ++i) {
+;  4     float a1 = A[2 * i * i];
+;  5     float a2 = A[2 * i * i + 1];
+;  6     float b1 = B[0][0];
+;  7     float b2 = B[i][i];
+;  8     float b3 = B[i * i][i];
+;  9     float b4 = B[i][0];
+; 10     float b5 = B[0][i];
+; 11     float b6 = B[0][i*i];
+; 12
+; 13     A[i * i] = a1 + a2 + b1 + b2 + b3 + b4 + b5 + b6;
+; 14   }
+; 15 }
+
+; CHECK: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop.
+; CHECK-NEXT: remark: /tmp/test.c:4:16: The array subscript of "A" is not affine
+; CHECK-NEXT: remark: /tmp/test.c:13:51: Invalid Scop candidate ends here.
+
+; ALL: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop.
+; ALL-NEXT: remark: /tmp/test.c:4:16: The array subscript of "A" is not affine
+; ALL-NEXT: remark: /tmp/test.c:5:16: The array subscript of "A" is not affine
+; -> B[0][0] is affine
+; ALL-NEXT: remark: /tmp/test.c:7:16: The array subscript of "B" is not affine
+; ALL-NEXT: remark: /tmp/test.c:8:16: The array subscript of "B" is not affine
+; ALL-NEXT: remark: /tmp/test.c:9:16: The array subscript of "B" is not affine
+; -> B[0][i] is affine
+; ALL-NEXT: remark: /tmp/test.c:11:16: The array subscript of "B" is not affine
+; ALL-NEXT: remark: /tmp/test.c:13:5: The array subscript of "A" is not affine
+; ALL-NEXT: remark: /tmp/test.c:13:51: Invalid Scop candidate ends here.
+
+; DELIN: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop.
+; DELIN-NEXT: remark: /tmp/test.c:4:16: The array subscript of "A" is not affine
+; DELIN-NEXT: remark: /tmp/test.c:13:51: Invalid Scop candidate ends here.
+
+; DELIN-ALL: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop.
+; DELIN-ALL-NEXT: remark: /tmp/test.c:4:16: The array subscript of "A" is not affine
+; DELIN-ALL-NEXT: remark: /tmp/test.c:5:16: The array subscript of "A" is not affine
+; DELIN-ALL-NEXT: remark: /tmp/test.c:13:5: The array subscript of "A" is not affine
+; -> B[0][0] is affine if delinearized
+; -> B[i][i] is affine if delinearized
+; DELIN-ALL-NEXT: remark: /tmp/test.c:8:16: The array subscript of "B" is not affine
+; -> B[i][0] is affine if delinearized
+; -> B[0][i] is affine if delinearized
+; DELIN-ALL-NEXT: remark: /tmp/test.c:11:16: The array subscript of "B" is not affine
+; DELIN-ALL-NEXT: remark: /tmp/test.c:13:51: Invalid Scop candidate ends here.
+
+; NONAFFINE-NOT: remark: The following errors keep this region from being a Scop.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @manyaccesses(float* noalias %A, i64 %n, float* noalias %B) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %tmp = add i64 %n, 1, !dbg !10
+  br label %for.body, !dbg !10
+
+for.body:                                         ; preds = %entry.split, %for.body
+  %tmp3 = phi i64 [ 0, %entry.split ], [ %tmp14, %for.body ], !dbg !15
+  %mul = mul i64 %tmp3, 2, !dbg !17
+  %tmp4 = mul i64 %tmp, %tmp3, !dbg !18
+  %arrayidx8 = getelementptr float* %B, i64 %tmp4, !dbg !19
+  %mul9 = mul i64 %n, %tmp3, !dbg !15
+  %arrayidx12 = getelementptr float* %B, i64 %mul9, !dbg !20
+  %arrayidx15 = getelementptr float* %B, i64 %tmp3, !dbg !21
+  %mul1 = mul nsw i64 %mul, %tmp3, !dbg !17
+  %arrayidx = getelementptr inbounds float* %A, i64 %mul1, !dbg !22
+  %tmp5 = load float* %arrayidx, align 4, !dbg !22
+  %mul3 = mul nsw i64 %mul, %tmp3, !dbg !27
+  %add1 = or i64 %mul3, 1, !dbg !27
+  %arrayidx4 = getelementptr inbounds float* %A, i64 %add1, !dbg !28
+  %tmp6 = load float* %arrayidx4, align 4, !dbg !28
+  %tmp7 = load float* %B, align 4, !dbg !29
+  %tmp8 = load float* %arrayidx8, align 4, !dbg !19
+  %tmp9 = mul i64 %mul9, %tmp3, !dbg !15
+  %arrayidx10.sum = add i64 %tmp9, %tmp3, !dbg !15
+  %arrayidx11 = getelementptr inbounds float* %B, i64 %arrayidx10.sum, !dbg !15
+  %tmp10 = load float* %arrayidx11, align 4, !dbg !15
+  %tmp11 = load float* %arrayidx12, align 4, !dbg !20
+  %tmp12 = load float* %arrayidx15, align 4, !dbg !21
+  %mul16 = mul nsw i64 %tmp3, %tmp3, !dbg !30
+  %arrayidx18 = getelementptr inbounds float* %B, i64 %mul16, !dbg !31
+  %tmp13 = load float* %arrayidx18, align 4, !dbg !31
+  %add19 = fadd float %tmp5, %tmp6, !dbg !32
+  %add20 = fadd float %add19, %tmp7, !dbg !33
+  %add21 = fadd float %add20, %tmp8, !dbg !34
+  %add22 = fadd float %add21, %tmp10, !dbg !35
+  %add23 = fadd float %add22, %tmp11, !dbg !36
+  %add24 = fadd float %add23, %tmp12, !dbg !37
+  %add25 = fadd float %add24, %tmp13, !dbg !38
+  %mul26 = mul nsw i64 %tmp3, %tmp3, !dbg !39
+  %arrayidx27 = getelementptr inbounds float* %A, i64 %mul26, !dbg !40
+  store float %add25, float* %arrayidx27, align 4, !dbg !40
+  %tmp14 = add nsw i64 %tmp3, 1, !dbg !41
+  %exitcond = icmp ne i64 %tmp14, 1024, !dbg !10
+  br i1 %exitcond, label %for.body, label %for.end, !dbg !10
+
+for.end:                                          ; preds = %for.body
+  ret void, !dbg !42
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!7, !8}
+!llvm.ident = !{!9}
+
+!0 = metadata !{i32 786449, metadata !1, i32 12, metadata !"clang version 3.6.0 ", i1 true, metadata !"", i32 0, metadata !2, metadata !2, metadata !3, metadata !2, metadata !2, metadata !"", i32 2} ; [ DW_TAG_compile_unit ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c] [DW_LANG_C99]
+!1 = metadata !{metadata !"/tmp/test.c", metadata !"/home/grosser/Projects/polly/git/tools/polly/test"}
+!2 = metadata !{}
+!3 = metadata !{metadata !4}
+!4 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"manyaccesses", metadata !"manyaccesses", metadata !"", i32 1, metadata !6, i1 false, i1 true, i32 0, i32 0, null, i32 256, i1 true, void (float*, i64, float*)* @manyaccesses, null, null, metadata !2, i32 2} ; [ DW_TAG_subprogram ] [line 1] [def] [scope 2] [manyaccesses]
+!5 = metadata !{i32 786473, metadata !1}          ; [ DW_TAG_file_type ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c]
+!6 = metadata !{i32 786453, i32 0, null, metadata !"", i32 0, i64 0, i64 0, i64 0, i32 0, null, metadata !2, i32 0, null, null, null} ; [ DW_TAG_subroutine_type ] [line 0, size 0, align 0, offset 0] [from ]
+!7 = metadata !{i32 2, metadata !"Dwarf Version", i32 4}
+!8 = metadata !{i32 2, metadata !"Debug Info Version", i32 1}
+!9 = metadata !{metadata !"clang version 3.6.0 "}
+!10 = metadata !{i32 3, i32 20, metadata !11, null}
+!11 = metadata !{i32 786443, metadata !1, metadata !12, i32 2} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c]
+!12 = metadata !{i32 786443, metadata !1, metadata !13, i32 1} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c]
+!13 = metadata !{i32 786443, metadata !1, metadata !14, i32 3, i32 3, i32 1} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c]
+!14 = metadata !{i32 786443, metadata !1, metadata !4, i32 3, i32 3, i32 0} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c]
+!15 = metadata !{i32 8, i32 16, metadata !16, null} ; [ DW_TAG_imported_declaration ]
+!16 = metadata !{i32 786443, metadata !1, metadata !13, i32 3, i32 35, i32 2} ; [ DW_TAG_lexical_block ] [/home/grosser/Projects/polly/git/tools/polly/test//tmp/test.c]
+!17 = metadata !{i32 4, i32 26, metadata !16, null}
+!18 = metadata !{i32 4, i32 22, metadata !16, null}
+!19 = metadata !{i32 7, i32 16, metadata !16, null}
+!20 = metadata !{i32 9, i32 16, metadata !16, null}
+!21 = metadata !{i32 10, i32 16, metadata !16, null}
+!22 = metadata !{i32 4, i32 16, metadata !16, null}
+!27 = metadata !{i32 5, i32 26, metadata !16, null}
+!28 = metadata !{i32 5, i32 16, metadata !16, null}
+!29 = metadata !{i32 6, i32 16, metadata !16, null}
+!30 = metadata !{i32 11, i32 23, metadata !16, null} ; [ DW_TAG_lexical_block ] [/]
+!31 = metadata !{i32 11, i32 16, metadata !16, null} ; [ DW_TAG_lexical_block ] [/]
+!32 = metadata !{i32 13, i32 21, metadata !16, null}
+!33 = metadata !{i32 13, i32 26, metadata !16, null}
+!34 = metadata !{i32 13, i32 31, metadata !16, null}
+!35 = metadata !{i32 13, i32 36, metadata !16, null}
+!36 = metadata !{i32 13, i32 41, metadata !16, null}
+!37 = metadata !{i32 13, i32 46, metadata !16, null}
+!38 = metadata !{i32 13, i32 51, metadata !16, null}
+!39 = metadata !{i32 13, i32 11, metadata !16, null}
+!40 = metadata !{i32 13, i32 5, metadata !16, null}
+!41 = metadata !{i32 3, i32 30, metadata !13, null}
+!42 = metadata !{i32 15, i32 1, metadata !4, null}

test/ScopInfo/multidim_single_and_multidim_array.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-scops -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=NONAFFINE
+; RUN: opt %loadPolly -polly-scops -polly-delinearize -analyze < %s | FileCheck %s --check-prefix=DELIN
+; RUN: opt %loadPolly -polly-scops -polly-delinearize -polly-allow-nonaffine -analyze < %s | FileCheck %s --check-prefix=DELIN
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; void single-and-multi-dimensional-array(long n,float X[n][n]) {
+;  for (long i1 = 0; i1 < n; i1++)
+;    X[i1][0] = 1;
+;
+;  for (long i2 = 0; i2 < n; i2++)
+;    X[n-1][i2] = 1;
+; }
+;
+; In previous versions of Polly, the second access was detected as single
+; dimensional access whereas the first one was detected as multi-dimensional.
+; This test case checks that we now consistently delinearize the array accesses.
+
+; CHECK-NOT: Stmt_for_i_1
+
+; NONAFFINE: p0: %n
+; NONAFFINE: p1: (4 * (-1 + %n) * %n)
+; NONAFFINE: Statements {
+; NONAFFINE:   Stmt_for_i_1
+; NONAFFINE:         MayWriteAccess :=   [Reduction Type: NONE]
+; NONAFFINE:             [n, p_1] -> { Stmt_for_i_1[i0] -> MemRef_X[o0] };
+; NONAFFINE:   Stmt_for_i_2
+; NONAFFINE:         MustWriteAccess :=  [Reduction Type: NONE]
+; NONAFFINE:             [n, p_1] -> { Stmt_for_i_2[i0] -> MemRef_X[o0] : 4o0 = p_1 + 4i0 };
+
+; DELIN: Stmt_for_i_1
+; DELIN:   MustWriteAccess :=
+; DELIN:      [n] -> { Stmt_for_i_1[i0] -> MemRef_X[i0, 0] };
+; DELIN: Stmt_for_i_2
+; DELIN:   MustWriteAccess :=
+; DELIN:      [n] -> { Stmt_for_i_2[i0] -> MemRef_X[-1 + n, i0] };
+
+define void @single-and-multi-dimensional-array(i64 %n, float* %X) {
+entry:
+  br label %for.i.1
+
+for.i.1:
+  %indvar.1 = phi i64 [ 0, %entry ], [ %indvar.next.1, %for.i.1 ]
+  %offset.1 = mul i64 %n, %indvar.1
+  %arrayidx.1 = getelementptr float* %X, i64 %offset.1
+  store float 1.000000e+00, float* %arrayidx.1
+  %indvar.next.1 = add nsw i64 %indvar.1, 1
+  %exitcond.1 = icmp ne i64 %indvar.next.1, %n
+  br i1 %exitcond.1, label %for.i.1, label %next
+
+next:
+  br label %for.i.2
+
+for.i.2:
+  %indvar.2 = phi i64 [ 0, %next ], [ %indvar.next.2, %for.i.2 ]
+  %offset.2.a = add i64 %n, -1
+  %offset.2.b = mul i64 %n, %offset.2.a
+  %offset.2.c = add i64 %offset.2.b, %indvar.2
+  %arrayidx.2 = getelementptr float* %X, i64 %offset.2.c
+  store float 1.000000e+00, float* %arrayidx.2
+  %indvar.next.2 = add nsw i64 %indvar.2, 1
+  %exitcond.2 = icmp ne i64 %indvar.next.2, %n
+  br i1 %exitcond.2, label %for.i.2, label %exit
+
+exit:
+  ret void
+}