[POLLY] Support accesses with differently sized types to the same array

[grosser]

Summary

Support accesses with differently sized types to the same array

This allows code such as:

void multiple_types(char *Short, char *Float, char *Double) {
  for (long i = 0; i < 100; i++) {
    Short[i] = *(short *)&Short[2 * i];
    Float[i] = *(float *)&Float[4 * i];
    Double[i] = *(double *)&Double[8 * i];
  }
}

To model such code we use as canonical element type of the modeled array the
smallest element type of all original array accesses, if type allocation sizes
are multiples of each other. Otherwise, we use a newly created iN type, where N
is the gcd of the allocation size of the types used in the accesses to this
array. Accesses with types larger as the canonical element type are modeled as
multiple accesses with the smaller type.

For example the second load access is modeled as:

  { Stmt_bb2[i0] -> MemRef_Float[o0] : 4i0 <= o0 <= 3 + 4i0 }

To support code-generating these memory accesses, we introduce a new method
getAccessAddressFunction that assigns each statement instance a single memory
location, the address we load from/store to. Currently we obtain this address by
taking the lexmin of the access function. We may consider keeping track of the
memory location more explicitly in the future.

We currently do _not_ handle multi-dimensional arrays and also keep the
restriction of not supporting accesses where the offset expression is not a
multiple of the access element type size. This patch adds tests that ensure
we correctly invalidate a scop in case these accesses are found. Both types of
accesses can be handled using the very same model, but are left to be added in
the future.

We also move the initialization of the scop-context into the constructor to
ensure it is already available when invalidating the scop.

[jdoerfert]

I generally like this idea but I still think the distinction between the last two test cases is not justified at all. All char pointers could have an arbitrary initial alignment in the last test case and it is in general not a problem to have unaligned accesses. This patch prevents some unaligned accesses from being represented but allows less obvious ones anyway.

include/polly/Support/ScopHelper.h

151 ↗

(On Diff #46885)

Can we use this somewhere else too? If so we might want to do so and commit it ahead of time.

lib/Analysis/ScopInfo.cpp

205 ↗

(On Diff #46885)

Maybe you can use:

APInt GreatestCommonDivisor (const APInt &Val1, const APInt &Val2)

or

std::experimental::gcd

from here http://en.cppreference.com/w/cpp/experimental/gcd .

496 ↗

(On Diff #46885)

Shouldn't the structute allow us to look for the lower bound instead of the lexmin?

test/ScopInfo/multiple-types-non-power-of-two.ll

24 ↗

(On Diff #46885)

I do not get the part about the allocation sizes. Where do you verify them in this test case?

test/ScopInfo/multiple-types-unaligned.ll

5 ↗

(On Diff #46885)

You don't know that. Same as you don't know that they are in the example below. As long as there is no alignment information attached to the pointers it is not clear how the alignment is and how it has to be in order to access the memory through this pointers. Not all machines require aligned accesses...

[grosser]

Addressed Johannes' comments.

[grosser]

Hi Johannes,

thanks for the quick review. I replied inline.

Regarding the alignment test case. I renamed it and made clear that this is not about alignment, but about the offset expression being a multiple of the element size. A restriction, we have today and which is left untouched by this patch.

Best,
Tobias

include/polly/Support/ScopHelper.h

151 ↗

(On Diff #46885)

I just went through the code, but did not find an obvious example. I could add it e.g. in the invariant load hoisting, but it would just add an unnecessary layer of indirection. So I think we can not move this out of this patch.

lib/Analysis/ScopInfo.cpp

205 ↗

(On Diff #46885)

I now use GreatestCommonDivisor64 from include/llvm/Support/MathExtras.h

496 ↗

(On Diff #46885)

What do you mean by "lower bound". Is there another isl function I could use instead of lexmin? (for me lexmin is the smallest value, so it seems to be some kind of lowerbound).

test/ScopInfo/multiple-types-non-power-of-two.ll

24 ↗

(On Diff #46885)

I added the following text:

; The allocation size discussed above defines the number of canonical array      
; elements accessed. For example, even though i27 only consists of 3 bytes,      
; its allocation size is 4 bytes. Consequently, we model the access to an        
; i27 element as an access to four canonical elements resulting in access        
; relation constraints '4i0 <= o0 <= 3 + 4i0' instead of '3i0 <= o0 <= 2 + 3i0'.

Did this make the test case more clear?

test/ScopInfo/multiple-types-unaligned.ll

5 ↗

(On Diff #46885)

For LLVM some alignment information is always known, it is either given explicitly with an alignment annotation or implicitly through the target data interface. For most architectures this means that types are by-default aligned to a multiple of their type size. So yes, we always get some information about alignment guarantees.

However, the term alignment is a little confusing here and the above alignment is not what this is about. We use the term unaligned in Polly to talk about access functions for which the offset from the base pointer can not be evenly divided by the type size, as we otherwise can not generate an access function for it (without falling back to smaller types). This restriction has been introduced by you as a correctness fix in https://llvm.org/svn/llvm-project/polly/trunk@252942.

Regarding this patch: we just leave the existing restriction in place (and we just add a test to verify that this is indeed the case). As written in the comment, this could be allowed as a straightforward extension. However, to keep this patch small, I focused on what I see as the more common case and left this for a later extension. Even so this is surely a nice extension, I do not see an inherent need why this needs to be part of an initial implementation.

I could add a brief explanation to this test case to make this difference clear.

[Meinersbur]

include/polly/Support/ScopHelper.h

151 ↗

(On Diff #46892)

getDebugLoc() is declared in llvm::Instruction. Just use

const llvm::DebugLoc &getDebugLoc() const {
    return I->getDebugLoc();
}

[grosser]

Addressed Michael's comment

[jdoerfert]

Regarding the "alignment" test cases:
I get your point now. The comment in the test cases confused me and the new comment makes it clear why we do not handle these cases _yet_.

lib/Analysis/ScopInfo.cpp

205 ↗

(On Diff #46892)

cool. I did not find that one.

489 ↗

(On Diff #46892)

I thought so but I cannot find it now.. let's just stick with lexmin. Sorry for the noise.

test/ScopInfo/multiple-types-non-power-of-two.ll

25 ↗

(On Diff #46892)

This does not help. Sorry.

1. In my book i27 consists of more than 3 bytes, thus I do not get the comment. It does not access 4 complete bytes, true, but it accesses more than 3. See point 2) for my take on the modeling.
2. The allocation size is target specific and should not be hard coded in Polly. This means we should not fix the argumentation to byte level. Instead the gcd of the allocation sizes in bit should be used as granularity. This will never make a difference for machines that work on byte level (gcd will just be a multiple of 8) and will prevent problems on machines that do not...

[jdoerfert]

include/polly/Support/ScopHelper.h

151 ↗

(On Diff #46894)

This method (as well as most of the ones above) is now just a plain wrapper around the same one in llvm::Instruction. I argued this before and will do it again: __ Do not copy all these functions but instead use the original __

MAcc.asInstruction()->getDebugLoc();

is not soo bad is it?

[Meinersbur]

include/polly/Support/ScopHelper.h

151 ↗

(On Diff #46894)

The model CallSite class also has some of these forwarders. In my original design, MemAccInst was derived from llvm::Instruction st this was no issue.

Suggestion:

Instruction *operator->() const { return I; }

and use like this:

MAcc->getDebugLoc();

[grosser]

Address Johannes' comment

[grosser]

Last comments inline.

include/polly/Support/ScopHelper.h

151 ↗

(On Diff #46894)

I still like the shorter version.

Adding new, trivial functions out-of-line seems to be minimal cost whereas adding (even so minimal) complexity in already non-trivial functions is something I am slightly worried about.

Clearly this is nothing super important, so if you feel strong about this I could change this.

test/ScopInfo/multiple-types-non-power-of-two.ll

26 ↗

(On Diff #46894)

Sorry, i27 was a mistake. It should be i24. Then the explanation makes sense.

Regarding the allocation size. We derived it using DL.getTypeAllocSize(), so it was already target specific. I now use the function getTypeAllocSizeInBits(), which allows us to also get rid of the magic constant '8'.

[jdoerfert]

LGTM.

test/ScopInfo/multiple-types-non-power-of-two.ll

27 ↗

(On Diff #46896)

Thanks for changing this.

polly/trunk/docs/ReleaseNotes.rst

 =============
 Release Notes
 =============
 
 In Polly 3.9 the following important changes have been incorporated.
 
+Increased analysis coverage
+---------------------------
+
+Polly's modeling has been improved to increase the applicability of Polly. The
+following code pieces are newly supported:
+
+Arrays accessed through different types
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+It is not uncommon that one array stores elements of different types. Polly now
+can model and optimize such code.
+
+.. code-block:: c
+
+    void multiple_types(char *Short, char *Float, char *Double) {
+      for (long i = 0; i < 100; i++) {
+        Short[i] = *(short *)&Short[2 * i];
+        Float[i] = *(float *)&Float[4 * i];
+        Double[i] = *(double *)&Double[8 * i];
+      }
+    }
 
 Update of the isl math library
 ------------------------------
 
 We imported the latest version of the isl math library into Polly.
 

polly/trunk/include/polly/ScopDetectionDiagnostic.h

enum RejectReasonKind {
   rrkInvalidCond,
   rrkUnsignedCond,
   rrkUndefOperand,
   rrkNonAffBranch,
   rrkNoBasePtr,
   rrkUndefBasePtr,
   rrkVariantBasePtr,
   rrkNonAffineAccess,
-  rrkDifferentElementSize,
   rrkLastAffFunc,
 
   rrkLoopBound,
 
   rrkFuncCall,
   rrkNonSimpleMemoryAccess,
 
   rrkAlias,
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 Captures errors with non affine loop bounds.
 class ReportLoopBound : public RejectReason {
   //===--------------------------------------------------------------------===//
 
   // The offending loop.
   Loop *L;
 
   // The non-affine loop bound.

polly/trunk/include/polly/ScopInfo.h

public:
 
   ///  @brief Update the sizes of the ScopArrayInfo object.
   ///
   ///  A ScopArrayInfo object may be created without all outer dimensions being
   ///  available. This function is called when new memory accesses are added for
   ///  this ScopArrayInfo object. It verifies that sizes are compatible and adds
   ///  additional outer array dimensions, if needed.
   ///
-  ///  @param Sizes A vector of array sizes where the rightmost array sizes need
-  ///               to match the innermost array sizes already defined in SAI.
-  ///  @returns Returns true if the update was successful, otherwise false.
-  bool updateSizes(ArrayRef<const SCEV *> Sizes);
+  ///  Similarly, memory accesses referencing this ScopArrayInfo object may use
+  ///  different element sizes. This function ensures the canonical element type
+  ///  stored is small enough to model all memory accesses.
+  ///
+  ///  @param Sizes       A vector of array sizes where the rightmost array
+  ///                     sizes need to match the innermost array sizes already
+  ///                     defined in SAI.
+  ///  @param ElementType The element type of this memory access.
+  bool updateSizes(ArrayRef<const SCEV *> Sizes, Type *ElementType);
 
   /// @brief Destructor to free the isl id of the base pointer.
   ~ScopArrayInfo();
 
   /// @brief Set the base pointer to @p BP.
   void setBasePtr(Value *BP) { BasePtr = BP; }
 
   /// @brief Return the base pointer.
private:
   /// @brief The base pointer.
   AssertingVH<Value> BasePtr;
 
   /// @brief The canonical element type of this array.
   ///
   /// The canonical element type describes the minimal accessible element in
   /// this array. Not all elements accessed, need to be of the very same type,
   /// but the allocation size of the type of the elements loaded/stored from/to
-  /// this array needs to match the allocation size of the canonical type.
+  /// this array needs to be a multiple of the allocation size of the canonical
+  /// type.
   Type *ElementType;
 
   /// @brief The isl id for the base pointer.
   isl_id *Id;
 
   /// @brief The sizes of each dimension as SCEV*.
   SmallVector<const SCEV *, 4> DimensionSizes;
 
private:
   ///        for j
   ///    S:     A[i + 3 j] = ...
   ///
   ///    => { S[i,j] -> A[i + 3j] }
   ///
   /// In case the exact access function is not known, the access relation may
   /// also be a one to all mapping { S[i,j] -> A[o] } describing that any
   /// element accessible through A might be accessed.
+  ///
+  /// In case of an access to a larger element belonging to an array that also
+  /// contains smaller elements, the access relation models the larger access
+  /// with multiple smaller accesses of the size of the minimal array element
+  /// type:
+  ///
+  ///      short *A;
+  ///
+  ///      for i
+  ///    S:     A[i] = *((double*)&A[4 * i]);
+  ///
+  ///    => { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 }
   isl_map *AccessRelation;
 
   /// @brief Updated access relation read from JSCOP file.
   isl_map *NewAccessRelation;
   // @}
 
   unsigned getElemSizeInBytes() const { return ElemBytes; }
 
public:
   /// As 2) is by construction "newer" than 1) we return the new access
   /// relation if present.
   ///
   isl_map *getAccessRelation() const {
     return hasNewAccessRelation() ? getNewAccessRelation()
                                   : getOriginalAccessRelation();
   }
 
+  /// @brief Get an isl map describing the memory address accessed.
+  ///
+  /// In most cases the memory address accessed is well described by the access
+  /// relation obtained with getAccessRelation. However, in case of arrays
+  /// accessed with types of different size the access relation maps one access
+  /// to multiple smaller address locations. This method returns an isl map that
+  /// relates each dynamic statement instance to the unique memory location
+  /// that is loaded from / stored to.
+  ///
+  /// For an access relation { S[i] -> A[o] : 4i <= o <= 4i + 3 } this method
+  /// will return the address function { S[i] -> A[4i] }.
+  ///
+  /// @returns The address function for this memory access.
+  __isl_give isl_map *getAddressFunction() const;
+
   /// @brief Return the access relation after the schedule was applied.
   __isl_give isl_pw_multi_aff *
   applyScheduleToAccessRelation(__isl_take isl_union_map *Schedule) const;
 
   /// @brief Get an isl string representing the access function read from IR.
   std::string getOriginalAccessRelationStr() const;
 
   /// @brief Get an isl string representing a new access function, if available.

polly/trunk/include/polly/Support/ScopHelper.h

public:
 
   llvm::Value *getOperand(unsigned i) const { return I->getOperand(i); }
   llvm::BasicBlock *getParent() const { return I->getParent(); }
   llvm::LLVMContext &getContext() const { return I->getContext(); }
   void getAAMetadata(llvm::AAMDNodes &N, bool Merge = false) const {
     I->getAAMetadata(N, Merge);
   }
 
+  /// @brief Get the debug location of this instruction.
+  ///
+  /// @returns The debug location of this instruction.
+  const llvm::DebugLoc &getDebugLoc() const {
+    if (I)
+      return I->getDebugLoc();
+    llvm_unreachable("Operation not supported on nullptr");
+  }
+
   llvm::Value *getValueOperand() const {
     if (isLoad())
       return asLoad();
     if (isStore())
       return asStore()->getValueOperand();
     llvm_unreachable("Operation not supported on nullptr");
   }
   llvm::Value *getPointerOperand() const {

polly/trunk/lib/Analysis/ScopDetection.cpp

bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
   // region.
   if (!isInvariant(*BaseValue, CurRegion))
     return invalid<ReportVariantBasePtr>(Context, /*Assert=*/true, BaseValue,
                                          Inst);
 
   AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
 
   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 {
+  if (Context.ElementSize[BasePointer])
+    Context.ElementSize[BasePointer] =
+        SE->getSMinExpr(Size, Context.ElementSize[BasePointer]);
+  else
     Context.ElementSize[BasePointer] = Size;
-  }
 
   bool isVariantInNonAffineLoop = false;
   SetVector<const Loop *> Loops;
   findLoops(AccessFunction, Loops);
   for (const Loop *L : Loops)
     if (Context.BoxedLoopsSet.count(L))
       isVariantInNonAffineLoop = true;
 

polly/trunk/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;

polly/trunk/lib/Analysis/ScopInfo.cpp

 ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *Ctx,
                              ArrayRef<const SCEV *> Sizes, enum MemoryKind Kind,
                              const DataLayout &DL, Scop *S)
     : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {
   std::string BasePtrName =
       getIslCompatibleName("MemRef_", BasePtr, Kind == MK_PHI ? "__phi" : "");
   Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this);
 
-  updateSizes(Sizes);
+  updateSizes(Sizes, ElementType);
   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());
   Space = isl_space_set_tuple_id(Space, isl_dim_set, isl_id_copy(Id));
   return Space;
 }
 
-bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes) {
+bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes,
+                                Type *NewElementType) {
+  auto OldElementSize = DL.getTypeAllocSizeInBits(ElementType);
+  auto NewElementSize = DL.getTypeAllocSizeInBits(NewElementType);
+
+  if (NewElementSize != OldElementSize) {
+    if (NewElementSize % OldElementSize == 0 &&
+        NewElementSize < OldElementSize) {
+      ElementType = NewElementType;
+    } else {
+      auto GCD = GreatestCommonDivisor64(NewElementSize, OldElementSize);
+      ElementType = IntegerType::get(ElementType->getContext(), GCD);
+    }
+  }
+
   int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());
   int ExtraDimsNew = NewSizes.size() - SharedDims;
   int ExtraDimsOld = DimensionSizes.size() - SharedDims;
   for (int i = 0; i < SharedDims; i++)
     if (NewSizes[i + ExtraDimsNew] != DimensionSizes[i + ExtraDimsOld])
       return false;
 
   if (DimensionSizes.size() >= NewSizes.size())

 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));
+  auto Map = isl_map_from_domain_and_range(
+      isl_set_universe(AccessSpace),
+      isl_set_universe(isl_space_copy(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);
 
+  // Introduce multi-element accesses in case the type loaded by this memory
+  // access is larger than the canonical element type of the array.
+  //
+  // An access ((float *)A)[i] to an array char *A is modeled as
+  // {[i] -> A[o] : 4 i <= o <= 4 i + 3
+  unsigned ArrayElemSize = getScopArrayInfo()->getElemSizeInBytes();
+  if (ElemBytes > ArrayElemSize) {
+    assert(ElemBytes % ArrayElemSize == 0 &&
+           "Loaded element size should be multiple of canonical element size");
+    auto Map = isl_map_from_domain_and_range(
+        isl_set_universe(isl_space_copy(ArraySpace)),
+        isl_set_universe(isl_space_copy(ArraySpace)));
+    for (unsigned i = 0; i < DimsArray - 1; i++)
+      Map = isl_map_equate(Map, isl_dim_in, i, isl_dim_out, i);
+
+    isl_ctx *Ctx;
+    isl_constraint *C;
+    isl_local_space *LS;
+
+    LS = isl_local_space_from_space(isl_map_get_space(Map));
+    Ctx = isl_map_get_ctx(Map);
+    int Num = ElemBytes / getScopArrayInfo()->getElemSizeInBytes();
+
+    C = isl_constraint_alloc_inequality(isl_local_space_copy(LS));
+    C = isl_constraint_set_constant_val(C, isl_val_int_from_si(Ctx, Num - 1));
+    C = isl_constraint_set_coefficient_si(C, isl_dim_in,
+                                          DimsArray - 1 - DimsMissing, Num);
+    C = isl_constraint_set_coefficient_si(C, isl_dim_out, DimsArray - 1, -1);
+    Map = isl_map_add_constraint(Map, C);
+
+    C = isl_constraint_alloc_inequality(LS);
+    C = isl_constraint_set_coefficient_si(C, isl_dim_in,
+                                          DimsArray - 1 - DimsMissing, -Num);
+    C = isl_constraint_set_coefficient_si(C, isl_dim_out, DimsArray - 1, 1);
+    C = isl_constraint_set_constant_val(C, isl_val_int_from_si(Ctx, 0));
+    Map = isl_map_add_constraint(Map, C);
+    AccessRelation = isl_map_apply_range(AccessRelation, Map);
+  }
+
+  isl_space_free(ArraySpace);
+
   assumeNoOutOfBound();
 }
 
 const std::string
 MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {
   switch (RT) {
   case MemoryAccess::RT_NONE:
     llvm_unreachable("Requested a reduction operator string for a memory "
const ScopArrayInfo *MemoryAccess::getScopArrayInfo() const {
   isl_id_free(ArrayId);
   return SAI;
 }
 
 __isl_give isl_id *MemoryAccess::getArrayId() const {
   return isl_map_get_tuple_id(AccessRelation, isl_dim_out);
 }
 
+__isl_give isl_map *MemoryAccess::getAddressFunction() const {
+  return isl_map_lexmin(getAccessRelation());
+}
+
 __isl_give isl_pw_multi_aff *MemoryAccess::applyScheduleToAccessRelation(
     __isl_take isl_union_map *USchedule) const {
   isl_map *Schedule, *ScheduledAccRel;
   isl_union_set *UDomain;
 
   UDomain = isl_union_set_from_set(getStatement()->getDomain());
   USchedule = isl_union_map_intersect_domain(USchedule, UDomain);
   Schedule = isl_map_from_union_map(USchedule);
-  ScheduledAccRel = isl_map_apply_domain(getAccessRelation(), Schedule);
+  ScheduledAccRel = isl_map_apply_domain(getAddressFunction(), Schedule);
   return isl_pw_multi_aff_from_map(ScheduledAccRel);
 }
 
 __isl_give isl_map *MemoryAccess::getOriginalAccessRelation() const {
   return isl_map_copy(AccessRelation);
 }
 
 std::string MemoryAccess::getOriginalAccessRelationStr() const {

 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()), HasErrorBlock(false),
       MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Context(nullptr),
       Affinator(this), AssumedContext(nullptr), BoundaryContext(nullptr),
-      Schedule(nullptr) {}
+      Schedule(nullptr) {
+  buildContext();
+}
 
 void Scop::init(AliasAnalysis &AA, AssumptionCache &AC) {
-  buildContext();
   addUserAssumptions(AC);
   buildInvariantEquivalenceClasses();
 
   buildDomains(&R);
 
   // Remove empty and ignored statements.
   // Exit early in case there are no executable statements left in this scop.
   simplifySCoP(true);
Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
   auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)];
   if (!SAI) {
     auto &DL = getRegion().getEntry()->getModule()->getDataLayout();
     SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
                                 DL, this));
   } else {
     // In case of mismatching array sizes, we bail out by setting the run-time
     // context to false.
-    if (!SAI->updateSizes(Sizes))
+    if (!SAI->updateSizes(Sizes, ElementType))
       invalidate(DELINEARIZATION, DebugLoc());
   }
   return SAI.get();
 }
 
 const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr,
                                             ScopArrayInfo::MemoryKind Kind) {
   auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();
bool ScopInfo::buildAccessMultiDimParam(
   assert(BasePointer && "Could not find base pointer");
   AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
 
   auto AccItr = InsnToMemAcc.find(Inst);
   if (PollyDelinearize && AccItr != InsnToMemAcc.end()) {
     std::vector<const SCEV *> Sizes(
         AccItr->second.Shape->DelinearizedSizes.begin(),
         AccItr->second.Shape->DelinearizedSizes.end());
-    assert(cast<const SCEVConstant>(Sizes.back())->getAPInt().getSExtValue() ==
-           ElementSize);
     // Remove the element size. This information is already provided by the
-    // ElementSize parameter.
+    // ElementSize parameter. In case the element size of this access and the
+    // element size used for delinearization differs the delinearization is
+    // incorrect. Hence, we invalidate the scop.
+    //
+    // TODO: Handle delinearization with differing element sizes.
+    auto DelinearizedSize =
+        cast<SCEVConstant>(Sizes.back())->getAPInt().getSExtValue();
     Sizes.pop_back();
+    if (ElementSize != DelinearizedSize)
+      scop->invalidate(DELINEARIZATION, Inst.getDebugLoc());
 
     addArrayAccess(Inst, Type, BasePointer->getValue(), ElementSize, true,
                    AccItr->second.DelinearizedSubscripts, Sizes, Val);
     return true;
   }
   return false;
 }
 

polly/trunk/lib/CodeGen/BlockGenerators.cpp

if (AccessExpr) {
     // Cast the address of this memory access to a pointer type that has the
     // same element type as the original access, but uses the address space of
     // the newly generated pointer.
     auto OldPtrTy = MA.getAccessValue()->getType()->getPointerTo();
     auto NewPtrTy = Address->getType();
     OldPtrTy = PointerType::get(OldPtrTy->getElementType(),
                                 NewPtrTy->getPointerAddressSpace());
 
-    if (OldPtrTy != NewPtrTy) {
-      assert(OldPtrTy->getPointerElementType()->getPrimitiveSizeInBits() ==
-                 NewPtrTy->getPointerElementType()->getPrimitiveSizeInBits() &&
-             "Pointer types to elements with different size found");
+    if (OldPtrTy != NewPtrTy)
       Address = Builder.CreateBitOrPointerCast(Address, OldPtrTy);
-    }
     return Address;
   }
 
   return getNewValue(Stmt, Inst.getPointerOperand(), BBMap, LTS,
                      getLoopForInst(Inst));
 }
 
 Loop *BlockGenerator::getLoopForInst(const llvm::Instruction *Inst) {

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

Value *IslNodeBuilder::preloadUnconditionally(isl_set *AccessRange,
 
   LInst->eraseFromParent();
   return PreloadVal;
 }
 
 Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
                                             isl_set *Domain) {
 
-  isl_set *AccessRange = isl_map_range(MA.getAccessRelation());
+  isl_set *AccessRange = isl_map_range(MA.getAddressFunction());
   if (!materializeParameters(AccessRange, false)) {
     isl_set_free(AccessRange);
     isl_set_free(Domain);
     return nullptr;
   }
 
   auto *Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace()));
   isl_set *Universe = isl_set_universe(isl_set_get_space(Domain));

polly/trunk/test/Isl/CodeGen/MemAccess/multiple_types.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S \
+; RUN:   -polly-codegen -S    < %s | FileCheck %s
+;
+;    // Check that accessing one array with different types works.
+;    void multiple_types(char *Short, char *Float, char *Double) {
+;      for (long i = 0; i < 100; i++) {
+;        Short[i] = *(short *)&Short[2 * i];
+;        Float[i] = *(float *)&Float[4 * i];
+;        Double[i] = *(double *)&Double[8 * i];
+;      }
+;    }
+
+; Short[0]
+; CHECK: %polly.access.Short10 = getelementptr i8, i8* %Short, i64 0
+; CHECK: %12 = bitcast i8* %polly.access.Short10 to i16*
+; CHECK: %tmp5_p_scalar_ = load i16, i16* %12
+
+; Float[8 * i]
+; CHECK: %13 = mul nsw i64 8, %polly.indvar
+; CHECK: %polly.access.Float11 = getelementptr i8, i8* %Float, i64 %13
+; CHECK: %14 = bitcast i8* %polly.access.Float11 to float*
+; CHECK: %tmp11_p_scalar_ = load float, float* %14
+
+; Double[8]
+; CHECK: %polly.access.Double13 = getelementptr i8, i8* %Double, i64 8
+; CHECK: %15 = bitcast i8* %polly.access.Double13 to double*
+; CHECK: %tmp17_p_scalar_ = load double, double* %15
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @multiple_types(i8* %Short, i8* %Float, i8* %Double) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb20, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ]
+  %exitcond = icmp ne i64 %i.0, 100
+  br i1 %exitcond, label %bb2, label %bb22
+
+bb2:                                              ; preds = %bb1
+  %tmp = shl nsw i64 %i.0, 1
+  %tmp3 = getelementptr inbounds i8, i8* %Short, i64 %tmp
+  %tmp4 = bitcast i8* %tmp3 to i16*
+  %tmp5 = load i16, i16* %tmp4, align 2
+  %tmp6 = trunc i16 %tmp5 to i8
+  %tmp7 = getelementptr inbounds i8, i8* %Short, i64 %i.0
+  store i8 %tmp6, i8* %tmp7, align 1
+  %tmp8 = shl nsw i64 %i.0, 2
+  %tmp9 = getelementptr inbounds i8, i8* %Float, i64 %tmp8
+  %tmp10 = bitcast i8* %tmp9 to float*
+  %tmp11 = load float, float* %tmp10, align 4
+  %tmp12 = fptosi float %tmp11 to i8
+  %tmp13 = getelementptr inbounds i8, i8* %Float, i64 %i.0
+  store i8 %tmp12, i8* %tmp13, align 1
+  %tmp14 = shl nsw i64 %i.0, 3
+  %tmp15 = getelementptr inbounds i8, i8* %Double, i64 %tmp14
+  %tmp16 = bitcast i8* %tmp15 to double*
+  %tmp17 = load double, double* %tmp16, align 8
+  %tmp18 = fptosi double %tmp17 to i8
+  %tmp19 = getelementptr inbounds i8, i8* %Double, i64 %i.0
+  store i8 %tmp18, i8* %tmp19, align 1
+  br label %bb20
+
+bb20:                                             ; preds = %bb2
+  %tmp21 = add nuw nsw i64 %i.0, 1
+  br label %bb1
+
+bb22:                                             ; preds = %bb1
+  ret void
+}

polly/trunk/test/Isl/CodeGen/MemAccess/multiple_types___%bb1---%bb22.jscop

+{
+   "context" : "{  :  }",
+   "name" : "bb1 => bb22",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_bb2[i0] -> MemRef_Short[0]}"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_bb2[i0] -> MemRef_Short[i0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_bb2[i0] -> MemRef_Float[o0] : 8i0 <=  o0 <= 3 + 8i0 }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_bb2[i0] -> MemRef_Float[i0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_bb2[i0] -> MemRef_Double[8]}"
+            },
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_bb2[i0] -> MemRef_Double[i0] }"
+            }
+         ],
+         "domain" : "{ Stmt_bb2[i0] : 0 <= i0 <= 99 }",
+         "name" : "Stmt_bb2",
+         "schedule" : "{ Stmt_bb2[i0] -> [i0] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/multiple-types-invariant-load.ll

+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+
+; CHECK: %polly.access.cast.global.load = bitcast %struct.hoge* %global.load to i32*
+; CHECK: %polly.access.global.load = getelementptr i32, i32* %polly.access.cast.global.load, i64 0
+; CHECK: %polly.access.global.load.load = load i32, i32* %polly.access.global.load
+
+; CHECK: %polly.access.cast.global.load1 = bitcast %struct.hoge* %global.load to i32*
+; CHECK: %polly.access.global.load2 = getelementptr i32, i32* %polly.access.cast.global.load1, i64 2
+; CHECK: %polly.access.global.load2.cast = bitcast i32* %polly.access.global.load2 to double*
+; CHECK: %polly.access.global.load2.load3 = load double, double* %polly.access.global.load2.cast
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.hoge = type { i32, double }
+
+@global = external global %struct.hoge*, align 8
+
+; Function Attrs: nounwind uwtable
+define void @widget(double* %A) #0 {
+bb:
+  br label %bb4
+
+bb4:
+  %tmp = load %struct.hoge*, %struct.hoge** @global
+  %tmp5 = getelementptr inbounds %struct.hoge, %struct.hoge* %tmp, i64 0, i32 0
+  %tmp6 = load i32, i32* %tmp5
+  %tmp7 = getelementptr inbounds %struct.hoge, %struct.hoge* %tmp, i64 0, i32 1
+  %tmp8 = load double, double* %tmp7
+  store double %tmp8, double* %A
+  br i1 false, label %bb11, label %bb12
+
+bb11:
+  br label %bb12
+
+bb12:
+  %tmp13 = phi float [ undef, %bb11 ], [ 1.000000e+00, %bb4 ]
+  unreachable
+}
+

polly/trunk/test/ScopDetectionDiagnostics/ReportDifferentElementSize.ll

-; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-detect-track-failures -polly-detect -analyze < %s 2>&1| FileCheck %s
-
-; 1 void differenttypes(char *A)
-; 2 {
-; 3   for (long i = 0; i < 1024; ++i)
-; 4     ((float*)A)[i] = ((double*)A)[i];
-; 5 }
-
-; CHECK: remark: /tmp/test.c:3:20: The following errors keep this region from being a Scop.
-; CHECK-NEXT: remark: /tmp/test.c:4:14: The array "A" is accessed through elements that differ in size
-; CHECK-NEXT: remark: /tmp/test.c:4:32: Invalid Scop candidate ends here.
-
-target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
-
-define void @differenttypes(i8* nocapture %A)  !dbg !4 {
-entry:
-  br label %for.body, !dbg !10
-
-for.body:                                         ; preds = %for.body, %entry
-  %i.05 = phi i64 [ 0, %entry ], [ %tmp11, %for.body ]
-  %tmp = shl i64 %i.05, 3, !dbg !15
-  %uglygep = getelementptr i8, i8* %A, i64 %tmp
-  %arrayidx = bitcast i8* %uglygep to double*, !dbg !16
-  %tmp9 = shl i64 %i.05, 2, !dbg !15
-  %uglygep7 = getelementptr i8, i8* %A, i64 %tmp9
-  %arrayidx1 = bitcast i8* %uglygep7 to float*, !dbg !17
-  %tmp10 = load double, double* %arrayidx, align 8, !dbg !16, !tbaa !18
-  %conv = fptrunc double %tmp10 to float, !dbg !16
-  store float %conv, float* %arrayidx1, align 4, !dbg !17, !tbaa !22
-  %tmp11 = add nsw i64 %i.05, 1, !dbg !24
-  %exitcond = icmp eq i64 %tmp11, 1024, !dbg !10
-  br i1 %exitcond, label %for.end, label %for.body, !dbg !10
-
-for.end:                                          ; preds = %for.body
-  ret void, !dbg !25
-}
-
-!llvm.dbg.cu = !{!0}
-!llvm.module.flags = !{!7, !8}
-!llvm.ident = !{!9}
-
-!0 = distinct !DICompileUnit(language: DW_LANG_C99, producer: "clang version 3.6.0 ", isOptimized: true, emissionKind: 2, file: !1, enums: !2, retainedTypes: !2, subprograms: !3, globals: !2, imports: !2)
-!1 = !DIFile(filename: "/tmp/test.c", directory: "/home/grosser/Projects/polly/git/tools/polly/test/ScopDetectionDiagnostics")
-!2 = !{}
-!3 = !{!4}
-!4 = distinct !DISubprogram(name: "differenttypes", line: 1, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: true, scopeLine: 2, file: !1, scope: !5, type: !6, variables: !2)
-!5 = !DIFile(filename: "/tmp/test.c", directory: "/home/grosser/Projects/polly/git/tools/polly/test/ScopDetectionDiagnostics")
-!6 = !DISubroutineType(types: !2)
-!7 = !{i32 2, !"Dwarf Version", i32 4}
-!8 = !{i32 2, !"Debug Info Version", i32 3}
-!9 = !{!"clang version 3.6.0 "}
-!10 = !DILocation(line: 3, column: 20, scope: !11)
-!11 = !DILexicalBlockFile(discriminator: 2, file: !1, scope: !12)
-!12 = !DILexicalBlockFile(discriminator: 1, file: !1, scope: !13)
-!13 = distinct !DILexicalBlock(line: 3, column: 3, file: !1, scope: !14)
-!14 = distinct !DILexicalBlock(line: 3, column: 3, file: !1, scope: !4)
-!15 = !DILocation(line: 4, column: 32, scope: !13)
-!16 = !DILocation(line: 4, column: 22, scope: !13)
-!17 = !DILocation(line: 4, column: 14, scope: !13)
-!18 = !{!19, !19, i64 0}
-!19 = !{!"double", !20, i64 0}
-!20 = !{!"omnipotent char", !21, i64 0}
-!21 = !{!"Simple C/C++ TBAA"}
-!22 = !{!23, !23, i64 0}
-!23 = !{!"float", !20, i64 0}
-!24 = !DILocation(line: 3, column: 30, scope: !13)
-!25 = !DILocation(line: 5, column: 1, scope: !4)

polly/trunk/test/ScopInfo/multiple-types-access-offset-not-dividable-by-element-size.ll

+; RUN: opt %loadPolly -polly-scops -pass-remarks-analysis="polly-scops" \
+; RUN:                -analyze < %s  2>&1 | FileCheck %s
+;
+;    // For the following accesses the offset expression from the base pointer
+;    // is not always a multiple of the type size.
+;    void multiple_types(char *Short, char *Float, char *Double) {
+;      for (long i = 0; i < 100; i++) {
+;        Short[i] = *(short *)&Short[i];
+;        Float[i] = *(float *)&Float[i];
+;        Double[i] = *(double *)&Double[i];
+;      }
+;    }
+;
+;   Polly currently does not allow such cases (even without multiple accesses of
+;   different type being involved).
+;   TODO: Add support for such kind of accesses
+;
+;
+; CHECK: Alignment assumption: {  : 1 = 0 }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @multiple_types(i8* %Short, i8* %Float, i8* %Double) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb17, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp18, %bb17 ]
+  %exitcond = icmp ne i64 %i.0, 100
+  br i1 %exitcond, label %bb2, label %bb19
+
+bb2:                                              ; preds = %bb1
+  %tmp = getelementptr inbounds i8, i8* %Short, i64 %i.0
+  %tmp3 = bitcast i8* %tmp to i16*
+  %tmp4 = load i16, i16* %tmp3, align 1
+  %tmp5 = trunc i16 %tmp4 to i8
+  %tmp6 = getelementptr inbounds i8, i8* %Short, i64 %i.0
+  store i8 %tmp5, i8* %tmp6, align 1
+  %tmp7 = getelementptr inbounds i8, i8* %Float, i64 %i.0
+  %tmp8 = bitcast i8* %tmp7 to float*
+  %tmp9 = load float, float* %tmp8, align 1
+  %tmp10 = fptosi float %tmp9 to i8
+  %tmp11 = getelementptr inbounds i8, i8* %Float, i64 %i.0
+  store i8 %tmp10, i8* %tmp11, align 1
+  %tmp12 = getelementptr inbounds i8, i8* %Double, i64 %i.0
+  %tmp13 = bitcast i8* %tmp12 to double*
+  %tmp14 = load double, double* %tmp13, align 1
+  %tmp15 = fptosi double %tmp14 to i8
+  %tmp16 = getelementptr inbounds i8, i8* %Double, i64 %i.0
+  store i8 %tmp15, i8* %tmp16, align 1
+  br label %bb17
+
+bb17:                                             ; preds = %bb2
+  %tmp18 = add nuw nsw i64 %i.0, 1
+  br label %bb1
+
+bb19:                                             ; preds = %bb1
+  ret void
+}

polly/trunk/test/ScopInfo/multiple-types-non-power-of-two-2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;  void multiple_types(i128 *A) {
+;    for (long i = 0; i < 100; i++) {
+;      A[i] = *(i128 *)&A[16 * i] +
+;             *(i192 *)&A[24 * i];
+;    }
+;  }
+;
+;
+; CHECK: Arrays {
+; CHECK:     i64 MemRef_A[*]; // Element size 8
+; CHECK: }
+; CHECK: Arrays (Bounds as pw_affs) {
+; CHECK:     i64 MemRef_A[*]; // Element size 8
+; CHECK: }
+; CHECK: Alias Groups (0):
+; CHECK:     n/a
+; CHECK: Statements {
+; CHECK:   Stmt_bb2
+; CHECK:         Domain :=
+; CHECK:             { Stmt_bb2[i0] : 0 <= i0 <= 99 };
+; CHECK:         Schedule :=
+; CHECK:             { Stmt_bb2[i0] -> [i0] };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 2i0 <= o0 <= 1 + 2i0 }
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 3i0 <= o0 <= 2 + 3i0 }
+; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 2i0 <= o0 <= 1 + 2i0 }
+; CHECK: }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @multiple_types(i8* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb20, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ]
+  %exitcond = icmp ne i64 %i.0, 100
+  br i1 %exitcond, label %bb2, label %bb22
+
+bb2:                                              ; preds = %bb1
+  %load.i128.offset = mul i64 %i.0, 16
+  %load.i128.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i128.offset
+  %load.i128.ptrcast = bitcast i8* %load.i128.ptr to i128*
+  %load.i128.val = load i128, i128* %load.i128.ptrcast
+
+  %load.i192.offset = mul i64 %i.0, 24
+  %load.i192.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i192.offset
+  %load.i192.ptrcast = bitcast i8* %load.i192.ptr to i192*
+  %load.i192.val = load i192, i192* %load.i192.ptrcast
+  %load.i192.val.trunc = trunc i192 %load.i192.val to i128
+
+  %sum = add i128 %load.i128.val, %load.i192.val.trunc
+  store i128 %sum, i128* %load.i128.ptrcast
+  br label %bb20
+
+bb20:                                             ; preds = %bb2
+  %tmp21 = add nuw nsw i64 %i.0, 1
+  br label %bb1
+
+bb22:                                             ; preds = %bb1
+  ret void
+}
+

polly/trunk/test/ScopInfo/multiple-types-non-power-of-two.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;  void multiple_types(i8 *A) {
+;    for (long i = 0; i < 100; i++) {
+;      A[i] = *(i1 *)&A[1 * i] +
+;             *(i16 *)&A[2 * i] +
+;             *(i24 *)&A[4 * i] +
+;             *(i32 *)&A[4 * i] +
+;             *(i40 *)&A[8 * i] +
+;             *(i48 *)&A[8 * i] +
+;             *(i56 *)&A[8 * i] +
+;             *(i64 *)&A[8 * i] +
+;             *(i120 *)&A[16 * i] +
+;             *(i192 *)&A[24 * i] +
+;             *(i248 *)&A[32 * i];
+;    }
+;  }
+;
+; Verify that different data type sizes are correctly modeled. Specifically,
+; we want to verify that type i1 is modeled with allocation size i8,
+; type i24 is modeled with allocation size i32 and that i40, i48 and i56 are
+; modeled with allocation size i64. Larger types, e.g., i120, i192 and i248 are
+; not rounded up to the next power-of-two allocation size, but rather to the
+; next multiple of 64.
+
+; The allocation size discussed above defines the number of canonical array
+; elements accessed. For example, even though i24 only consists of 3 bytes,
+; its allocation size is 4 bytes. Consequently, we model the access to an
+; i24 element as an access to four canonical elements resulting in access
+; relation constraints '4i0 <= o0 <= 3 + 4i0' instead of '3i0 <= o0 <= 2 + 3i0'.
+
+; CHECK: Statements {
+; CHECK:   Stmt_bb2
+; CHECK:         Domain :=
+; CHECK:             { Stmt_bb2[i0] : 0 <= i0 <= 99 };
+; CHECK:         Schedule :=
+; CHECK:             { Stmt_bb2[i0] -> [i0] };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 2i0 <= o0 <= 1 + 2i0 };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 4i0 <= o0 <= 3 + 4i0 };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 4i0 <= o0 <= 3 + 4i0 };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 8i0 <= o0 <= 7 + 8i0 };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 8i0 <= o0 <= 7 + 8i0 };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 8i0 <= o0 <= 7 + 8i0 };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 8i0 <= o0 <= 7 + 8i0 };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 16i0 <= o0 <= 15 + 16i0 };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 24i0 <= o0 <= 23 + 24i0 };
+; CHECK:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[o0] : 32i0 <= o0 <= 31 + 32i0 };
+; CHECK:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK:             { Stmt_bb2[i0] -> MemRef_A[i0] };
+; CHECK: }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @multiple_types(i8* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb20, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ]
+  %exitcond = icmp ne i64 %i.0, 100
+  br i1 %exitcond, label %bb2, label %bb22
+
+bb2:                                              ; preds = %bb1
+  %load.i1.offset = mul i64 %i.0, 1
+  %load.i1.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i1.offset
+  %load.i1.ptrcast = bitcast i8* %load.i1.ptr to i1*
+  %load.i1.val = load i1, i1* %load.i1.ptrcast
+  %load.i1.val.trunc = zext i1 %load.i1.val to i8
+
+  %load.i16.offset = mul i64 %i.0, 2
+  %load.i16.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i16.offset
+  %load.i16.ptrcast = bitcast i8* %load.i16.ptr to i16*
+  %load.i16.val = load i16, i16* %load.i16.ptrcast
+  %load.i16.val.trunc = trunc i16 %load.i16.val to i8
+
+  %load.i24.offset = mul i64 %i.0, 4
+  %load.i24.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i24.offset
+  %load.i24.ptrcast = bitcast i8* %load.i24.ptr to i24*
+  %load.i24.val = load i24, i24* %load.i24.ptrcast
+  %load.i24.val.trunc = trunc i24 %load.i24.val to i8
+
+  %load.i32.offset = mul i64 %i.0, 4
+  %load.i32.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i32.offset
+  %load.i32.ptrcast = bitcast i8* %load.i32.ptr to i32*
+  %load.i32.val = load i32, i32* %load.i32.ptrcast
+  %load.i32.val.trunc = trunc i32 %load.i32.val to i8
+
+  %load.i40.offset = mul i64 %i.0, 8
+  %load.i40.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i40.offset
+  %load.i40.ptrcast = bitcast i8* %load.i40.ptr to i40*
+  %load.i40.val = load i40, i40* %load.i40.ptrcast
+  %load.i40.val.trunc = trunc i40 %load.i40.val to i8
+
+  %load.i48.offset = mul i64 %i.0, 8
+  %load.i48.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i48.offset
+  %load.i48.ptrcast = bitcast i8* %load.i48.ptr to i48*
+  %load.i48.val = load i48, i48* %load.i48.ptrcast
+  %load.i48.val.trunc = trunc i48 %load.i48.val to i8
+
+  %load.i56.offset = mul i64 %i.0, 8
+  %load.i56.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i56.offset
+  %load.i56.ptrcast = bitcast i8* %load.i56.ptr to i56*
+  %load.i56.val = load i56, i56* %load.i56.ptrcast
+  %load.i56.val.trunc = trunc i56 %load.i56.val to i8
+
+  %load.i64.offset = mul i64 %i.0, 8
+  %load.i64.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i64.offset
+  %load.i64.ptrcast = bitcast i8* %load.i64.ptr to i64*
+  %load.i64.val = load i64, i64* %load.i64.ptrcast
+  %load.i64.val.trunc = trunc i64 %load.i64.val to i8
+
+  %load.i120.offset = mul i64 %i.0, 16
+  %load.i120.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i120.offset
+  %load.i120.ptrcast = bitcast i8* %load.i120.ptr to i120*
+  %load.i120.val = load i120, i120* %load.i120.ptrcast
+  %load.i120.val.trunc = trunc i120 %load.i120.val to i8
+
+  %load.i192.offset = mul i64 %i.0, 24
+  %load.i192.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i192.offset
+  %load.i192.ptrcast = bitcast i8* %load.i192.ptr to i192*
+  %load.i192.val = load i192, i192* %load.i192.ptrcast
+  %load.i192.val.trunc = trunc i192 %load.i192.val to i8
+
+  %load.i248.offset = mul i64 %i.0, 32
+  %load.i248.ptr = getelementptr inbounds i8, i8* %A, i64 %load.i248.offset
+  %load.i248.ptrcast = bitcast i8* %load.i248.ptr to i248*
+  %load.i248.val = load i248, i248* %load.i248.ptrcast
+  %load.i248.val.trunc = trunc i248 %load.i248.val to i8
+
+  %sum = add i8 %load.i1.val.trunc, %load.i16.val.trunc
+  %sum0 = add i8 %sum, %load.i24.val.trunc
+  %sum1 = add i8 %sum0, %load.i32.val.trunc
+  %sum2 = add i8 %sum1, %load.i40.val.trunc
+  %sum3 = add i8 %sum2, %load.i48.val.trunc
+  %sum4 = add i8 %sum3, %load.i56.val.trunc
+  %sum5 = add i8 %sum4, %load.i64.val.trunc
+  %sum6 = add i8 %sum5, %load.i120.val.trunc
+  %sum7 = add i8 %sum6, %load.i192.val.trunc
+  %sum8 = add i8 %sum7, %load.i248.val.trunc
+  %tmp7 = getelementptr inbounds i8, i8* %A, i64 %i.0
+  store i8 %sum8, i8* %tmp7
+  br label %bb20
+
+bb20:                                             ; preds = %bb2
+  %tmp21 = add nuw nsw i64 %i.0, 1
+  br label %bb1
+
+bb22:                                             ; preds = %bb1
+  ret void
+}

polly/trunk/test/ScopInfo/multiple-types-two-dimensional-2.ll

+; RUN: opt %loadPolly -polly-scops -pass-remarks-analysis="polly-scops" \
+; RUN:                -analyze < %s  2>&1 | FileCheck %s
+;
+;
+;    void foo(long n, long m, char A[][m]) {
+;      for (long i = 0; i < n; i++)
+;        for (long j = 0; j < m / 4; j++)
+;          *(float *)&A[i][4 * j] = A[i][j];
+;    }
+;
+; We do not yet correctly handle multi-dimensional arrays which are accessed
+; through different base types. Verify that we correctly bail out.
+;
+; CHECK: Delinearization assumption:  {  : 1 = 0 }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @foo(i64 %n, i64 %m, i8* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb20, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ]
+  %tmp = icmp slt i64 %i.0, %n
+  br i1 %tmp, label %bb2, label %bb22
+
+bb2:                                              ; preds = %bb1
+  br label %bb3
+
+bb3:                                              ; preds = %bb17, %bb2
+  %j.0 = phi i64 [ 0, %bb2 ], [ %tmp18, %bb17 ]
+  %tmp4 = sdiv i64 %m, 4
+  %tmp5 = icmp slt i64 %j.0, %tmp4
+  br i1 %tmp5, label %bb6, label %bb19
+
+bb6:                                              ; preds = %bb3
+  %tmp7 = mul nsw i64 %i.0, %m
+  %tmp8 = getelementptr inbounds i8, i8* %A, i64 %tmp7
+  %tmp9 = getelementptr inbounds i8, i8* %tmp8, i64 %j.0
+  %tmp10 = load i8, i8* %tmp9, align 1
+  %tmp11 = sitofp i8 %tmp10 to float
+  %tmp12 = shl nsw i64 %j.0, 2
+  %tmp13 = mul nsw i64 %i.0, %m
+  %tmp14 = getelementptr inbounds i8, i8* %A, i64 %tmp13
+  %tmp15 = getelementptr inbounds i8, i8* %tmp14, i64 %tmp12
+  %tmp16 = bitcast i8* %tmp15 to float*
+  store float %tmp11, float* %tmp16, align 4
+  br label %bb17
+
+bb17:                                             ; preds = %bb6
+  %tmp18 = add nuw nsw i64 %j.0, 1
+  br label %bb3
+
+bb19:                                             ; preds = %bb3
+  br label %bb20
+
+bb20:                                             ; preds = %bb19
+  %tmp21 = add nuw nsw i64 %i.0, 1
+  br label %bb1
+
+bb22:                                             ; preds = %bb1
+  ret void
+}

polly/trunk/test/ScopInfo/multiple-types-two-dimensional.ll

+; RUN: opt %loadPolly -polly-scops -pass-remarks-analysis="polly-scops" \
+; RUN:                -analyze < %s  2>&1 | FileCheck %s
+;
+;    void foo(long n, long m, char A[][m]) {
+;      for (long i = 0; i < n; i++)
+;        for (long j = 0; j < m / 4; j++)
+;          A[i][j] = *(float *)&A[i][4 * j];
+;    }
+;
+; We do not yet correctly handle multi-dimensional arrays which are accessed
+; through different base types. Verify that we correctly bail out.
+;
+; CHECK: Delinearization assumption:  {  : 1 = 0 }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @foo(i64 %n, i64 %m, i8* %A) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb20, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ]
+  %tmp = icmp slt i64 %i.0, %n
+  br i1 %tmp, label %bb2, label %bb22
+
+bb2:                                              ; preds = %bb1
+  br label %bb3
+
+bb3:                                              ; preds = %bb17, %bb2
+  %j.0 = phi i64 [ 0, %bb2 ], [ %tmp18, %bb17 ]
+  %tmp4 = sdiv i64 %m, 4
+  %tmp5 = icmp slt i64 %j.0, %tmp4
+  br i1 %tmp5, label %bb6, label %bb19
+
+bb6:                                              ; preds = %bb3
+  %tmp7 = shl nsw i64 %j.0, 2
+  %tmp8 = mul nsw i64 %i.0, %m
+  %tmp9 = getelementptr inbounds i8, i8* %A, i64 %tmp8
+  %tmp10 = getelementptr inbounds i8, i8* %tmp9, i64 %tmp7
+  %tmp11 = bitcast i8* %tmp10 to float*
+  %tmp12 = load float, float* %tmp11, align 4
+  %tmp13 = fptosi float %tmp12 to i8
+  %tmp14 = mul nsw i64 %i.0, %m
+  %tmp15 = getelementptr inbounds i8, i8* %A, i64 %tmp14
+  %tmp16 = getelementptr inbounds i8, i8* %tmp15, i64 %j.0
+  store i8 %tmp13, i8* %tmp16, align 1
+  br label %bb17
+
+bb17:                                             ; preds = %bb6
+  %tmp18 = add nuw nsw i64 %j.0, 1
+  br label %bb3
+
+bb19:                                             ; preds = %bb3
+  br label %bb20
+
+bb20:                                             ; preds = %bb19
+  %tmp21 = add nuw nsw i64 %i.0, 1
+  br label %bb1
+
+bb22:                                             ; preds = %bb1
+  ret void
+}

polly/trunk/test/ScopInfo/multiple-types.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+;    // Check that accessing one array with different types works.
+;    void multiple_types(char *Short, char *Float, char *Double) {
+;      for (long i = 0; i < 100; i++) {
+;        Short[i] = *(short *)&Short[2 * i];
+;        Float[i] = *(float *)&Float[4 * i];
+;        Double[i] = *(double *)&Double[8 * i];
+;      }
+;    }
+
+; CHECK: Statements {
+; CHECK-NEXT: Stmt_bb2
+; CHECK-NEXT: Domain :=
+; CHECK-NEXT:     { Stmt_bb2[i0] : 0 <= i0 <= 99 };
+; CHECK-NEXT: Schedule :=
+; CHECK-NEXT:     { Stmt_bb2[i0] -> [i0] };
+; CHECK-NEXT: ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:     { Stmt_bb2[i0] -> MemRef_Short[o0] : 2i0 <= o0 <= 1 + 2i0 };
+; CHECK-NEXT: MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:     { Stmt_bb2[i0] -> MemRef_Short[i0] };
+; CHECK-NEXT: ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:     { Stmt_bb2[i0] -> MemRef_Float[o0] : 4i0 <= o0 <= 3 + 4i0 };
+; CHECK-NEXT: MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:     { Stmt_bb2[i0] -> MemRef_Float[i0] };
+; CHECK-NEXT: ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:     { Stmt_bb2[i0] -> MemRef_Double[o0] : 8i0 <= o0 <= 7 + 8i0 };
+; CHECK-NEXT: MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:     { Stmt_bb2[i0] -> MemRef_Double[i0] };
+; CHECK-NEXT: }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @multiple_types(i8* %Short, i8* %Float, i8* %Double) {
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb20, %bb
+  %i.0 = phi i64 [ 0, %bb ], [ %tmp21, %bb20 ]
+  %exitcond = icmp ne i64 %i.0, 100
+  br i1 %exitcond, label %bb2, label %bb22
+
+bb2:                                              ; preds = %bb1
+  %tmp = shl nsw i64 %i.0, 1
+  %tmp3 = getelementptr inbounds i8, i8* %Short, i64 %tmp
+  %tmp4 = bitcast i8* %tmp3 to i16*
+  %tmp5 = load i16, i16* %tmp4, align 2
+  %tmp6 = trunc i16 %tmp5 to i8
+  %tmp7 = getelementptr inbounds i8, i8* %Short, i64 %i.0
+  store i8 %tmp6, i8* %tmp7, align 1
+  %tmp8 = shl nsw i64 %i.0, 2
+  %tmp9 = getelementptr inbounds i8, i8* %Float, i64 %tmp8
+  %tmp10 = bitcast i8* %tmp9 to float*
+  %tmp11 = load float, float* %tmp10, align 4
+  %tmp12 = fptosi float %tmp11 to i8
+  %tmp13 = getelementptr inbounds i8, i8* %Float, i64 %i.0
+  store i8 %tmp12, i8* %tmp13, align 1
+  %tmp14 = shl nsw i64 %i.0, 3
+  %tmp15 = getelementptr inbounds i8, i8* %Double, i64 %tmp14
+  %tmp16 = bitcast i8* %tmp15 to double*
+  %tmp17 = load double, double* %tmp16, align 8
+  %tmp18 = fptosi double %tmp17 to i8
+  %tmp19 = getelementptr inbounds i8, i8* %Double, i64 %i.0
+  store i8 %tmp18, i8* %tmp19, align 1
+  br label %bb20
+
+bb20:                                             ; preds = %bb2
+  %tmp21 = add nuw nsw i64 %i.0, 1
+  br label %bb1
+
+bb22:                                             ; preds = %bb1
+  ret void
+}