[Polly] Support memory intrinsics

[jdoerfert]

Summary

+ Allow and handle memcpy, memset and memmove intrinsics.
+ Allow to add lower/upper bounds to the access range of non-affine
  memory accesses (useful with a range analysis)

[jdoerfert]

Added early pointer check & adjusted based on the change of the misc intrinsics commit

[grosser]

Hi Johannes,

sorry I never got to review this patch. It looks small, self-contained and seems to be going into the right direction. Hence, I could most likely review this quickly if there is still interest. Does this patch still apply or does it require a rebase?

[jdoerfert]

Again, 1.5 years old... I guess a rebase is needed.

[jdoerfert]

Rebase

[etherzhhb]

include/polly/Support/ScopHelper.h

169 ↗

(On Diff #47933)

This doesn't make sense to me.

lib/Analysis/ScopDetection.cpp

492 ↗

(On Diff #47933)

should it be getArgOperand (which is equivalent at the moment, but safer)?

500 ↗

(On Diff #47933)

How about use getRawDest or getDest (this one strip the pointer-cast)?

lib/Analysis/ScopInfo.cpp

765 ↗

(On Diff #47933)

simply isa<MemIntrinsic>(getAccessInstruction())?

2576 ↗

(On Diff #47933)

why we relax this assertion?

[etherzhhb]

include/polly/Support/ScopHelper.h

169 ↗

(On Diff #47933)

We may simply return nullptr here.

[jdoerfert]

lib/Analysis/ScopInfo.cpp

2576 ↗

(On Diff #47933)

Because the alias sets in the alias set tracker look differen when we also add memory intrinsics. This does not change the semantics of the algorithm though, it just refrlects that the alias groups can be small now such that we do not care.

[jdoerfert]

Changed according to the comments. Thanks!

[Meinersbur]

I don't see that the copied' size gets evaluated apart from checking that it's affine.

Does the following work as expected?

float A[128][128], B[128];
for (int i = 0; i < 128; i+=1)
  memcpy(A[i], B, 128*sizeof(float));

include/polly/Support/ScopHelper.h

224 ↗

(On Diff #48337)

Maybe add a comment explaining this?

I guess this is taken from LoadInst/StoreInst implementation of isUnordered() with getOrdering() returning NotAtomic.

lib/Analysis/ScopDetection.cpp

38 ↗

(On Diff #48337)

Can you be more specific: memset, memcpy, memmove are allowed?

lib/Analysis/ScopInfo.cpp

306 ↗

(On Diff #48337)

LLVM coding style suggests to use auto only in specific cases. Eg. where the type already appears on the right side or the type is already abstracted away.

If you keep auto, the asterisk is superfluous.

test/ScopInfo/memcpy.ll

16 ↗

(On Diff #48337)

Shouldn't this be a ReadAccess? This look like memcpy write two locations instead of reading one, writing the other.

test/ScopInfo/memmove.ll

16 ↗

(On Diff #48337)

dito

[jdoerfert]

Updated according to comment. Thx.

[jdoerfert]

In D5226#356142, @Meinersbur wrote:

I don't see that the copied' size gets evaluated apart from checking that it's affine.

Does the following work as expected?

float A[128][128], B[128];
for (int i = 0; i < 128; i+=1)
  memcpy(A[i], B, 128*sizeof(float));

The examples contain length values already. I think they work. The evaluation can be found in MemoryAccess::buildMemIntrinsicAccessRelation.

lib/Analysis/ScopInfo.cpp

306 ↗

(On Diff #48337)

LLVM coding style suggests to use auto only in specific cases. Eg. where the type already appears on the right side or the type is already abstracted away.

Since the variable is called BB I guess the type is kinda obvious.

If you keep auto, the asterisk is superfluous.

But it tells you that this is a pointer. We had this discussion before and while ppl started to ignore it and use plain auto I still think it is a good idea to add * and & if appropriate.

[jdoerfert]

This passes all LNT tests with an unprofitable build.

@etherzhhb, @Meinersbur: Are there still open problems/comments or can I commit this?

[etherzhhb]

LGTM and I think this patch will be very useful.

include/polly/Support/ScopHelper.h

56 ↗

(On Diff #48621)

load, store or memintrinsic ...

58 ↗

(On Diff #48621)

isLoad(), isStore(), isMemIntrinsic() ...

lib/CodeGen/BlockGenerators.cpp

321–323 ↗

(On Diff #48621)

Unrelated change?

polly/trunk/include/polly/ScopDetection.h

 class Loop;
 class ScalarEvolution;
 class SCEV;
 class SCEVAddRecExpr;
 class SCEVUnknown;
 class CallInst;
 class Instruction;
 class Value;
+class IntrinsicInst;
 }
 
 namespace polly {
 typedef std::set<const SCEV *> ParamSetType;
 
 // Description of the shape of an array.
 struct ArrayShape {
   // Base pointer identifying all accesses to this array.
private:
 
   /// @brief Check if a region is a Scop.
   ///
   /// @param Context The context of scop detection.
   ///
   /// @return True if R is a Scop, false otherwise.
   bool isValidRegion(DetectionContext &Context) const;
 
+  /// @brief Check if an intrinsic call can be part of a Scop.
+  ///
+  /// @param II      The intrinsic call instruction to check.
+  /// @param Context The current detection context.
+  ///
+  /// @return True if the call instruction is valid, false otherwise.
+  bool isValidIntrinsicInst(IntrinsicInst &II, DetectionContext &Context) const;
+
   /// @brief Check if a call instruction can be part of a Scop.
   ///
-  /// @param CI The call instruction to check.
+  /// @param CI      The call instruction to check.
+  /// @param Context The current detection context.
+  ///
   /// @return True if the call instruction is valid, false otherwise.
-  static bool isValidCallInst(CallInst &CI);
+  bool isValidCallInst(CallInst &CI, DetectionContext &Context) const;
 
   /// @brief Check if the given loads could be invariant and can be hoisted.
   ///
   /// If true is returned the loads are added to the required invariant loads
   /// contained in the @p Context.
   ///
   /// @param RequiredILS The loads to check.
   /// @param Context     The current detection context.
   ///
   /// @return True if all loads can be assumed invariant.
   bool onlyValidRequiredInvariantLoads(InvariantLoadsSetTy &RequiredILS,
                                        DetectionContext &Context) const;
 
   /// @brief Check if a value is invariant in the region Reg.
   ///
   /// @param Val Value to check for invariance.
   /// @param Reg The region to consider for the invariance of Val.
   ///
   /// @return True if the value represented by Val is invariant in the region
   ///         identified by Reg.
   bool isInvariant(const Value &Val, const Region &Reg) const;
 
+  /// @brief Check if the memory access caused by @p Inst is valid.
+  ///
+  /// @param Inst    The access instruction.
+  /// @param AF      The access function.
+  /// @param BP      The access base pointer.
+  /// @param Context The current detection context.
+  bool isValidAccess(Instruction *Inst, const SCEV *AF, const SCEVUnknown *BP,
+                     DetectionContext &Context) const;
+
   /// @brief Check if a memory access can be part of a Scop.
   ///
   /// @param Inst The instruction accessing the memory.
   /// @param Context The context of scop detection.
   ///
   /// @return True if the memory access is valid, false otherwise.
   bool isValidMemoryAccess(MemAccInst Inst, DetectionContext &Context) const;
 

polly/trunk/include/polly/ScopInfo.h

private:
   /// PHI node itself.
   /// The #BaseAddr of a memory access of kind MK_Value is the instruction
   /// defining the value.
   AssertingVH<Value> BaseAddr;
 
   /// @brief An unique name of the accessed array.
   std::string BaseName;
 
-  /// @brief Size in bytes of a single array element.
-  unsigned ElemBytes;
+  /// @brief Type a single array element wrt. this access.
+  Type *ElementType;
 
   /// @brief Size of each dimension of the accessed array.
   SmallVector<const SCEV *, 4> Sizes;
   // @}
 
   // Properties describing the accessed element.
   // @{
 
private:
   Instruction *AccessInstruction;
 
   /// @brief Incoming block and value of a PHINode.
   SmallVector<std::pair<BasicBlock *, Value *>, 4> Incoming;
 
   /// @brief The value associated with this memory access.
   ///
   ///  - For array memory accesses (MK_Array) it is the loaded result or the
-  ///    stored value.
+  ///    stored value. If the access instruction is a memory intrinsic it
+  ///    the access value is also the memory intrinsic.
   ///  - For accesses of kind MK_Value it is the access instruction itself.
   ///  - For accesses of kind MK_PHI or MK_ExitPHI it is the PHI node itself
   ///    (for both, READ and WRITE accesses).
   ///
   AssertingVH<Value> AccessValue;
 
   /// @brief Are all the subscripts affine expression?
   bool IsAffine;
private:
   ///
   ///    => { 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; }
-
   bool isAffine() const { return IsAffine; }
 
   __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement);
 
   void assumeNoOutOfBound();
 
   /// @brief Compute bounds on an over approximated  access relation.
   ///
private:
   /// more cases and adding multiple of Ns to these cases. However, this has
   /// not yet been necessary.
   /// The introduction of different cases necessarily complicates the memory
   /// access function, but cases that can be statically proven to not happen
   /// will be eliminated later on.
   __isl_give isl_map *foldAccess(__isl_take isl_map *AccessRelation,
                                  ScopStmt *Statement);
 
+  /// @brief Create the access relation for the underlying memory intrinsic.
+  void buildMemIntrinsicAccessRelation();
+
   /// @brief Assemble the access relation from all availbale information.
   ///
   /// In particular, used the information passes in the constructor and the
   /// parent ScopStmt set by setStatment().
   ///
   /// @param SAI Info object for the accessed array.
   void buildAccessRelation(const ScopArrayInfo *SAI);
 
 public:
   /// @brief Create a new MemoryAccess.
   ///
   /// @param Stmt       The parent statement.
   /// @param AccessInst The instruction doing the access.
   /// @param BaseAddr   The accessed array's address.
-  /// @param ElemBytes  Number of accessed bytes.
+  /// @param ElemType   The type of the accessed array elements.
   /// @param AccType    Whether read or write access.
   /// @param IsAffine   Whether the subscripts are affine expressions.
   /// @param Kind       The kind of memory accessed.
   /// @param Subscripts Subscipt expressions
   /// @param Sizes      Dimension lengths of the accessed array.
   /// @param BaseName   Name of the acessed array.
-  MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType Type,
-               Value *BaseAddress, unsigned ElemBytes, bool Affine,
+  MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType AccType,
+               Value *BaseAddress, Type *ElemType, bool Affine,
                ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
                Value *AccessValue, ScopArrayInfo::MemoryKind Kind,
                StringRef BaseName);
   ~MemoryAccess();
 
   /// @brief Add a new incoming block/value pairs for this PHI/ExitPHI access.
   ///
   /// @param IncomingBlock The PHI's incoming block.
public:
   /// @brief Return a string representation of the accesse's reduction type.
   const std::string getReductionOperatorStr() const;
 
   /// @brief Return a string representation of the reduction type @p RT.
   static const std::string getReductionOperatorStr(ReductionType RT);
 
   const std::string &getBaseName() const { return BaseName; }
 
+  /// @brief Return the element type of the accessed array wrt. this access.
+  Type *getElementType() const { return ElementType; }
+
   /// @brief Return the access value of this memory access.
   Value *getAccessValue() const { return AccessValue; }
 
   /// @brief Return the access instruction of this memory access.
   Instruction *getAccessInstruction() const { return AccessInstruction; }
 
   /// @brief Return the access function subscript in the dimension @p Dim.
   const SCEV *getSubscript(unsigned Dim) const { return Subscripts[Dim]; }
class ScopInfo : public RegionPass {
   ///
   /// @returns True if the access could be built, False otherwise.
   bool
   buildAccessMultiDimParam(MemAccInst Inst, Loop *L, Region *R,
                            const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
                            const InvariantLoadsSetTy &ScopRIL,
                            const MapInsnToMemAcc &InsnToMemAcc);
 
+  /// @brief Try to build a MemoryAccess for a memory intrinsic.
+  ///
+  /// @param Inst       The instruction that access the memory
+  /// @param L          The parent loop of the instruction
+  /// @param R          The region on which to build the data access dictionary.
+  /// @param BoxedLoops The set of loops that are overapproximated in @p R.
+  /// @param ScopRIL    The required invariant loads equivalence classes.
+  ///
+  /// @returns True if the access could be built, False otherwise.
+  bool buildAccessMemIntrinsic(MemAccInst Inst, Loop *L, Region *R,
+                               const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
+                               const InvariantLoadsSetTy &ScopRIL);
+
   /// @brief Build a single-dimensional parameteric sized MemoryAccess
   ///        from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param L          The parent loop of the instruction
   /// @param R          The region on which to build the data access dictionary.
   /// @param BoxedLoops The set of loops that are overapproximated in @p R.
   /// @param ScopRIL    The required invariant loads equivalence classes.
void buildAccessFunctions(Region &R, BasicBlock &BB,
                             Region *NonAffineSubRegion = nullptr,
                             bool IsExitBlock = false);
 
   /// @brief Create a new MemoryAccess object and add it to #AccFuncMap.
   ///
   /// @param BB          The block where the access takes place.
   /// @param Inst        The instruction doing the access. It is not necessarily
   ///                    inside @p BB.
-  /// @param Type        The kind of access.
+  /// @param AccType     The kind of access.
   /// @param BaseAddress The accessed array's base address.
-  /// @param ElemBytes   Size of accessed array element.
+  /// @param ElemType    The type of the accessed array elements.
   /// @param Affine      Whether all subscripts are affine expressions.
   /// @param AccessValue Value read or written.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array diminsion's sizes.
   /// @param Kind        The kind of memory accessed.
   ///
   /// @return The created MemoryAccess, or nullptr if the access is not within
   ///         the SCoP.
   MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst,
-                                MemoryAccess::AccessType Type,
-                                Value *BaseAddress, unsigned ElemBytes,
-                                bool Affine, Value *AccessValue,
+                                MemoryAccess::AccessType AccType,
+                                Value *BaseAddress, Type *ElemType, bool Affine,
+                                Value *AccessValue,
                                 ArrayRef<const SCEV *> Subscripts,
                                 ArrayRef<const SCEV *> Sizes,
                                 ScopArrayInfo::MemoryKind Kind);
 
   /// @brief Create a MemoryAccess that represents either a LoadInst or
   /// StoreInst.
   ///
   /// @param MemAccInst  The LoadInst or StoreInst.
-  /// @param Type        The kind of access.
+  /// @param AccType     The kind of access.
   /// @param BaseAddress The accessed array's base address.
-  /// @param ElemBytes   Size of accessed array element.
+  /// @param ElemType    The type of the accessed array elements.
   /// @param IsAffine    Whether all subscripts are affine expressions.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array dimension's sizes.
   /// @param AccessValue Value read or written.
   ///
   /// @see ScopArrayInfo::MemoryKind
-  void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType Type,
-                      Value *BaseAddress, unsigned ElemBytes, bool IsAffine,
+  void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType AccType,
+                      Value *BaseAddress, Type *ElemType, bool IsAffine,
                       ArrayRef<const SCEV *> Subscripts,
                       ArrayRef<const SCEV *> Sizes, Value *AccessValue);
 
   /// @brief Create a MemoryAccess for writing an llvm::Instruction.
   ///
   /// The access will be created at the position of @p Inst.
   ///
   /// @param Inst The instruction to be written.

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

 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SUPPORT_IRHELPER_H
 #define POLLY_SUPPORT_IRHELPER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/ValueHandle.h"
 
 namespace llvm {
 class LoopInfo;
 class ScalarEvolution;
 class SCEV;
 class Region;
 class Pass;
using ValueMapT = llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
                                  llvm::AssertingVH<llvm::Value>>;
 
 /// @brief Type for a set of invariant loads.
 using InvariantLoadsSetTy = llvm::SetVector<llvm::AssertingVH<llvm::LoadInst>>;
 
 /// @brief Utility proxy to wrap the common members of LoadInst and StoreInst.
 ///
 /// This works like the LLVM utility class CallSite, ie. it forwards all calls
-/// to either a LoadInst or StoreInst.
+/// to either a LoadInst, StoreInst, MemIntrinsic or MemTransferInst.
 /// It is similar to LLVM's utility classes IntrinsicInst, MemIntrinsic,
 /// MemTransferInst, etc. in that it offers a common interface, but does not act
 /// as a fake base class.
 /// It is similar to StringRef and ArrayRef in that it holds a pointer to the
 /// referenced object and should be passed by-value as it is small enough.
 ///
 /// This proxy can either represent a LoadInst instance, a StoreInst instance,
-/// or a nullptr (only creatable using the default constructor); never an
-/// Instruction that is not a load or store.
-/// When representing a nullptr, only the following methods are defined:
-/// isNull(), isInstruction(), isLoad(), isStore(), operator bool(), operator!()
+/// a MemIntrinsic instance (memset, memmove, memcpy) or a nullptr (only
+/// creatable using the default constructor); never an Instruction that is
+/// neither of the above mentioned. When representing a nullptr, only the
+/// following methods are defined:
+/// isNull(), isInstruction(), isLoad(), isStore(), ..., isMemTransferInst(),
+/// operator bool(), operator!()
 ///
 /// The functions isa, cast, cast_or_null, dyn_cast are modeled te resemble
 /// those from llvm/Support/Casting.h. Partial template function specialization
 /// is currently not supported in C++ such that those cannot be used directly.
 /// (llvm::isa could, but then llvm:cast etc. would not have the expected
 /// behaviour)
 class MemAccInst {
 private:
   llvm::Instruction *I;
 
 public:
   MemAccInst() : I(nullptr) {}
   MemAccInst(const MemAccInst &Inst) : I(Inst.I) {}
   /* implicit */ MemAccInst(llvm::LoadInst &LI) : I(&LI) {}
   /* implicit */ MemAccInst(llvm::LoadInst *LI) : I(LI) {}
   /* implicit */ MemAccInst(llvm::StoreInst &SI) : I(&SI) {}
   /* implicit */ MemAccInst(llvm::StoreInst *SI) : I(SI) {}
+  /* implicit */ MemAccInst(llvm::MemIntrinsic *MI) : I(MI) {}
   explicit MemAccInst(llvm::Instruction &I) : I(&I) { assert(isa(I)); }
   explicit MemAccInst(llvm::Instruction *I) : I(I) { assert(isa(I)); }
 
   static bool isa(const llvm::Value &V) {
-    return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V);
+    return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V) ||
+           llvm::isa<llvm::MemIntrinsic>(V);
   }
   static bool isa(const llvm::Value *V) {
-    return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V);
+    return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V) ||
+           llvm::isa<llvm::MemIntrinsic>(V);
   }
   static MemAccInst cast(llvm::Value &V) {
     return MemAccInst(llvm::cast<llvm::Instruction>(V));
   }
   static MemAccInst cast(llvm::Value *V) {
     return MemAccInst(llvm::cast<llvm::Instruction>(V));
   }
   static MemAccInst cast_or_null(llvm::Value &V) {
public:
   MemAccInst &operator=(llvm::StoreInst &SI) {
     I = &SI;
     return *this;
   }
   MemAccInst &operator=(llvm::StoreInst *SI) {
     I = SI;
     return *this;
   }
+  MemAccInst &operator=(llvm::MemIntrinsic &MI) {
+    I = &MI;
+    return *this;
+  }
+  MemAccInst &operator=(llvm::MemIntrinsic *MI) {
+    I = MI;
+    return *this;
+  }
 
   operator llvm::Instruction *() const { return asInstruction(); }
   explicit operator bool() const { return isInstruction(); }
   bool operator!() const { return isNull(); }
 
   llvm::Value *getOperand(unsigned i) const { return I->getOperand(i); }
   llvm::BasicBlock *getParent() const { return I->getParent(); }
   llvm::LLVMContext &getContext() const { return I->getContext(); }
const llvm::DebugLoc &getDebugLoc() const {
     llvm_unreachable("Operation not supported on nullptr");
   }
 
   llvm::Value *getValueOperand() const {
     if (isLoad())
       return asLoad();
     if (isStore())
       return asStore()->getValueOperand();
+    if (isMemIntrinsic())
+      return nullptr;
     llvm_unreachable("Operation not supported on nullptr");
   }
   llvm::Value *getPointerOperand() const {
     if (isLoad())
       return asLoad()->getPointerOperand();
     if (isStore())
       return asStore()->getPointerOperand();
+    if (isMemIntrinsic())
+      return asMemIntrinsic()->getDest();
     llvm_unreachable("Operation not supported on nullptr");
   }
 
   unsigned getAlignment() const {
     if (isLoad())
       return asLoad()->getAlignment();
     if (isStore())
       return asStore()->getAlignment();
+    if (isMemIntrinsic())
+      return asMemIntrinsic()->getAlignment();
     llvm_unreachable("Operation not supported on nullptr");
   }
   bool isVolatile() const {
     if (isLoad())
       return asLoad()->isVolatile();
     if (isStore())
       return asStore()->isVolatile();
+    if (isMemIntrinsic())
+      return asMemIntrinsic()->isVolatile();
     llvm_unreachable("Operation not supported on nullptr");
   }
   bool isSimple() const {
     if (isLoad())
       return asLoad()->isSimple();
     if (isStore())
       return asStore()->isSimple();
+    if (isMemIntrinsic())
+      return !asMemIntrinsic()->isVolatile();
     llvm_unreachable("Operation not supported on nullptr");
   }
   llvm::AtomicOrdering getOrdering() const {
     if (isLoad())
       return asLoad()->getOrdering();
     if (isStore())
       return asStore()->getOrdering();
+    if (isMemIntrinsic())
+      return llvm::AtomicOrdering::NotAtomic;
     llvm_unreachable("Operation not supported on nullptr");
   }
   bool isUnordered() const {
     if (isLoad())
       return asLoad()->isUnordered();
     if (isStore())
       return asStore()->isUnordered();
+    // Copied from the Load/Store implementation of isUnordered:
+    if (isMemIntrinsic())
+      return !asMemIntrinsic()->isVolatile();
     llvm_unreachable("Operation not supported on nullptr");
   }
 
   bool isNull() const { return !I; }
   bool isInstruction() const { return I; }
   bool isLoad() const { return I && llvm::isa<llvm::LoadInst>(I); }
   bool isStore() const { return I && llvm::isa<llvm::StoreInst>(I); }
+  bool isMemIntrinsic() const { return I && llvm::isa<llvm::MemIntrinsic>(I); }
+  bool isMemSetInst() const { return I && llvm::isa<llvm::MemSetInst>(I); }
+  bool isMemTransferInst() const {
+    return I && llvm::isa<llvm::MemTransferInst>(I);
+  }
 
   llvm::Instruction *asInstruction() const { return I; }
   llvm::LoadInst *asLoad() const { return llvm::cast<llvm::LoadInst>(I); }
   llvm::StoreInst *asStore() const { return llvm::cast<llvm::StoreInst>(I); }
+  llvm::MemIntrinsic *asMemIntrinsic() const {
+    return llvm::cast<llvm::MemIntrinsic>(I);
+  }
+  llvm::MemSetInst *asMemSetInst() const {
+    return llvm::cast<llvm::MemSetInst>(I);
+  }
+  llvm::MemTransferInst *asMemTransferInst() const {
+    return llvm::cast<llvm::MemTransferInst>(I);
+  }
 };
 
 /// @brief Check if the PHINode has any incoming Invoke edge.
 ///
 /// @param PN The PHINode to check.
 ///
 /// @return If the PHINode has an incoming BB that jumps to the parent BB
 ///         of the PHINode with an invoke instruction, return true,

polly/trunk/lib/Analysis/ScopDetection.cpp

 // * All loops and conditions perfectly nested
 //
 // The control flow needs to be structured such that it could be written using
 // just 'for' and 'if' statements, without the need for any 'goto', 'break' or
 // 'continue'.
 //
 // * Side effect free functions call
 //
-// Only function calls and intrinsics that do not have side effects are allowed
-// (readnone).
+// Function calls and intrinsics that do not have side effects (readnone)
+// or memory intrinsics (memset, memcpy, memmove) are allowed.
 //
 // The Scop detection finds the largest Scops by checking if the largest
 // region is a Scop. If this is not the case, its canonical subregions are
 // checked until a region is a Scop. It is now tried to extend this Scop by
 // creating a larger non canonical region.
 //
 //===----------------------------------------------------------------------===//
 
if (BranchInst *BI = dyn_cast<BranchInst>(TI))
     return isValidBranch(BB, BI, Condition, IsLoopBranch, Context);
 
   SwitchInst *SI = dyn_cast<SwitchInst>(TI);
   assert(SI && "Terminator was neither branch nor switch");
 
   return isValidSwitch(BB, SI, Condition, IsLoopBranch, Context);
 }
 
-bool ScopDetection::isValidCallInst(CallInst &CI) {
+bool ScopDetection::isValidCallInst(CallInst &CI,
+                                    DetectionContext &Context) const {
   if (CI.doesNotReturn())
     return false;
 
   if (CI.doesNotAccessMemory())
     return true;
 
+  if (auto *II = dyn_cast<IntrinsicInst>(&CI))
+    return isValidIntrinsicInst(*II, Context);
+
   Function *CalledFunction = CI.getCalledFunction();
 
   // Indirect calls are not supported.
   if (CalledFunction == 0)
     return false;
 
-  if (isIgnoredIntrinsic(&CI))
+  return false;
+}
+
+bool ScopDetection::isValidIntrinsicInst(IntrinsicInst &II,
+                                         DetectionContext &Context) const {
+  if (isIgnoredIntrinsic(&II))
     return true;
 
+  // The closest loop surrounding the call instruction.
+  Loop *L = LI->getLoopFor(II.getParent());
+
+  // The access function and base pointer for memory intrinsics.
+  const SCEV *AF;
+  const SCEVUnknown *BP;
+
+  switch (II.getIntrinsicID()) {
+  // Memory intrinsics that can be represented are supported.
+  case llvm::Intrinsic::memmove:
+  case llvm::Intrinsic::memcpy:
+    AF = SE->getSCEVAtScope(cast<MemTransferInst>(II).getSource(), L);
+    BP = dyn_cast<SCEVUnknown>(SE->getPointerBase(AF));
+    // Bail if the source pointer is not valid.
+    if (!isValidAccess(&II, AF, BP, Context))
+      return false;
+  // Fall through
+  case llvm::Intrinsic::memset:
+    AF = SE->getSCEVAtScope(cast<MemIntrinsic>(II).getDest(), L);
+    BP = dyn_cast<SCEVUnknown>(SE->getPointerBase(AF));
+    // Bail if the destination pointer is not valid.
+    if (!isValidAccess(&II, AF, BP, Context))
+      return false;
+
+    // Bail if the length is not affine.
+    if (!isAffine(SE->getSCEVAtScope(cast<MemIntrinsic>(II).getLength(), L),
+                  Context))
+      return false;
+
+    return true;
+  default:
+    break;
+  }
+
   return false;
 }
 
 bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const {
   // A reference to function argument or constant value is invariant.
   if (isa<Argument>(Val) || isa<Constant>(Val))
     return true;
 
if (!hasBaseAffineAccesses(Context, BasePointer)) {
       if (KeepGoing)
         continue;
       else
         return false;
     }
   return true;
 }
 
-bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
-                                        DetectionContext &Context) const {
-  Region &CurRegion = Context.CurRegion;
-
-  Value *Ptr = Inst.getPointerOperand();
-  Loop *L = LI->getLoopFor(Inst.getParent());
-  const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L);
-  const SCEVUnknown *BasePointer;
-  Value *BaseValue;
-
-  BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
+bool ScopDetection::isValidAccess(Instruction *Inst, const SCEV *AF,
+                                  const SCEVUnknown *BP,
 
-  if (!BasePointer)
+  if (!BP)
     return invalid<ReportNoBasePtr>(Context, /*Assert=*/true, Inst);
 
-  BaseValue = BasePointer->getValue();
-
-  if (isa<UndefValue>(BaseValue))
+  auto *BV = BP->getValue();
+  if (isa<UndefValue>(BV))
     return invalid<ReportUndefBasePtr>(Context, /*Assert=*/true, Inst);
 
+  // FIXME: Think about allowing IntToPtrInst
+  if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BV))
+    return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
+
   // Check that the base address of the access is invariant in the current
   // 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[BasePointer]) {
-    if (!AllowDifferentTypes && Context.ElementSize[BasePointer] != Size)
+  if (!isInvariant(*BV, Context.CurRegion))
+    return invalid<ReportVariantBasePtr>(Context, /*Assert=*/true, BV, Inst);
+
+  AF = SE->getMinusSCEV(AF, BP);
+
+  const SCEV *Size;
+  if (!isa<MemIntrinsic>(Inst)) {
+    Size = SE->getElementSize(Inst);
+  } else {
+    auto *SizeTy =
+        SE->getEffectiveSCEVType(PointerType::getInt8PtrTy(SE->getContext()));
+    Size = SE->getConstant(SizeTy, 8);
+  }
+
+  if (Context.ElementSize[BP]) {
+    if (!AllowDifferentTypes && Context.ElementSize[BP] != Size)
       return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true,
-                                                      Inst, BaseValue);
+                                                      Inst, BV);
 
-    Context.ElementSize[BasePointer] =
-        SE->getSMinExpr(Size, Context.ElementSize[BasePointer]);
+    Context.ElementSize[BP] = SE->getSMinExpr(Size, Context.ElementSize[BP]);
   } else {
-    Context.ElementSize[BasePointer] = Size;
+    Context.ElementSize[BP] = Size;
   }
 
-  bool isVariantInNonAffineLoop = false;
+  bool IsVariantInNonAffineLoop = false;
   SetVector<const Loop *> Loops;
-  findLoops(AccessFunction, Loops);
+  findLoops(AF, Loops);
   for (const Loop *L : Loops)
     if (Context.BoxedLoopsSet.count(L))
-      isVariantInNonAffineLoop = true;
+      IsVariantInNonAffineLoop = true;
 
-  if (PollyDelinearize && !isVariantInNonAffineLoop) {
-    Context.Accesses[BasePointer].push_back({Inst, AccessFunction});
-
-    if (!isAffine(AccessFunction, Context, BaseValue))
-      Context.NonAffineAccesses.insert(BasePointer);
-  } else if (!AllowNonAffine) {
-    if (isVariantInNonAffineLoop ||
-        !isAffine(AccessFunction, Context, BaseValue))
-      return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
-                                            AccessFunction, Inst, BaseValue);
+  bool IsAffine = !IsVariantInNonAffineLoop && isAffine(AF, Context, BV);
+  // Do not try to delinearize memory intrinsics and force them to be affine.
+  if (isa<MemIntrinsic>(Inst) && !IsAffine) {
+    return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Inst,
+                                          BV);
+  } else if (PollyDelinearize && !IsVariantInNonAffineLoop) {
+    Context.Accesses[BP].push_back({Inst, AF});
+
+    if (!IsAffine)
+      Context.NonAffineAccesses.insert(BP);
+  } else if (!AllowNonAffine && !IsAffine) {
+    return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Inst,
+                                          BV);
   }
 
-  // FIXME: Think about allowing IntToPtrInst
-  if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BaseValue))
-    return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
-
   if (IgnoreAliasing)
     return true;
 
   // Check if the base pointer of the memory access does alias with
   // any other pointer. This cannot be handled at the moment.
   AAMDNodes AATags;
-  Inst.getAAMetadata(AATags);
+  Inst->getAAMetadata(AATags);
   AliasSet &AS = Context.AST.getAliasSetForPointer(
-      BaseValue, MemoryLocation::UnknownSize, AATags);
+      BP->getValue(), MemoryLocation::UnknownSize, AATags);
 
   if (!AS.isMustAlias()) {
     if (PollyUseRuntimeAliasChecks) {
       bool CanBuildRunTimeCheck = true;
       // The run-time alias check places code that involves the base pointer at
       // the beginning of the SCoP. This breaks if the base pointer is defined
       // inside the scop. Hence, we can only create a run-time check if we are
       // sure the base pointer is not an instruction defined inside the scop.
       // However, we can ignore loads that will be hoisted.
       for (const auto &Ptr : AS) {
         Instruction *Inst = dyn_cast<Instruction>(Ptr.getValue());
-        if (Inst && CurRegion.contains(Inst)) {
+        if (Inst && Context.CurRegion.contains(Inst)) {
           auto *Load = dyn_cast<LoadInst>(Inst);
-          if (Load && isHoistableLoad(Load, CurRegion, *LI, *SE)) {
+          if (Load && isHoistableLoad(Load, Context.CurRegion, *LI, *SE)) {
             Context.RequiredILS.insert(Load);
             continue;
           }
 
           CanBuildRunTimeCheck = false;
           break;
         }
       }
 
       if (CanBuildRunTimeCheck)
         return true;
     }
     return invalid<ReportAlias>(Context, /*Assert=*/true, Inst, AS);
   }
 
   return true;
 }
 
+bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
+                                        DetectionContext &Context) const {
+  Value *Ptr = Inst.getPointerOperand();
+  Loop *L = LI->getLoopFor(Inst.getParent());
+  const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L);
+  const SCEVUnknown *BasePointer;
+
+  BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
+
+  return isValidAccess(Inst, AccessFunction, BasePointer, Context);
+}
+
 bool ScopDetection::isValidInstruction(Instruction &Inst,
                                        DetectionContext &Context) const {
   for (auto &Op : Inst.operands()) {
     auto *OpInst = dyn_cast<Instruction>(&Op);
 
     if (!OpInst)
       continue;
 
     if (isErrorBlock(*OpInst->getParent(), Context.CurRegion, *LI, *DT))
       return false;
   }
 
   // We only check the call instruction but not invoke instruction.
   if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
-    if (isValidCallInst(*CI))
+    if (isValidCallInst(*CI, Context))
       return true;
 
     return invalid<ReportFuncCall>(Context, /*Assert=*/true, &Inst);
   }
 
   if (!Inst.mayWriteToMemory() && !Inst.mayReadFromMemory()) {
     if (!isa<AllocaInst>(Inst))
       return true;

polly/trunk/lib/Analysis/ScopInfo.cpp

void MemoryAccess::updateDimensionality() {
   auto *ArraySpace = SAI->getSpace();
   auto *AccessSpace = isl_space_range(isl_map_get_space(AccessRelation));
   auto *Ctx = isl_space_get_ctx(AccessSpace);
 
   auto DimsArray = isl_space_dim(ArraySpace, isl_dim_set);
   auto DimsAccess = isl_space_dim(AccessSpace, isl_dim_set);
   auto DimsMissing = DimsArray - DimsAccess;
 
+  auto *BB = getStatement()->getParent()->getRegion().getEntry();
+  auto &DL = BB->getModule()->getDataLayout();
   unsigned ArrayElemSize = SAI->getElemSizeInBytes();
+  unsigned ElemBytes = DL.getTypeAllocSize(getElementType());
 
   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);
 
void MemoryAccess::assumeNoOutOfBound() {
   Outside = isl_set_remove_divs(Outside);
   Outside = isl_set_complement(Outside);
   Statement->getParent()->addAssumption(
       INBOUNDS, Outside,
       getAccessInstruction() ? getAccessInstruction()->getDebugLoc() : nullptr);
   isl_space_free(Space);
 }
 
+void MemoryAccess::buildMemIntrinsicAccessRelation() {
+  auto MAI = MemAccInst(getAccessInstruction());
+  assert(MAI.isMemIntrinsic());
+  assert(Subscripts.size() == 2 && Sizes.size() == 0);
+
+  auto *LengthPWA = Statement->getPwAff(Subscripts[1]);
+  auto *LengthMap = isl_map_from_pw_aff(LengthPWA);
+  auto *RangeSpace = isl_space_range(isl_map_get_space(LengthMap));
+  LengthMap = isl_map_apply_range(LengthMap, isl_map_lex_gt(RangeSpace));
+  LengthMap = isl_map_lower_bound_si(LengthMap, isl_dim_out, 0, 0);
+  auto *SubscriptPWA = Statement->getPwAff(Subscripts[0]);
+  auto *SubscriptMap = isl_map_from_pw_aff(SubscriptPWA);
+  SubscriptMap =
+      isl_map_align_params(SubscriptMap, isl_map_get_space(LengthMap));
+  LengthMap = isl_map_align_params(LengthMap, isl_map_get_space(SubscriptMap));
+  LengthMap = isl_map_sum(LengthMap, SubscriptMap);
+  AccessRelation = isl_map_set_tuple_id(LengthMap, isl_dim_in,
+                                        getStatement()->getDomainId());
+}
+
 void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
   ScalarEvolution *SE = Statement->getParent()->getSE();
 
-  Value *Ptr = MemAccInst(getAccessInstruction()).getPointerOperand();
+  auto MAI = MemAccInst(getAccessInstruction());
+  if (MAI.isMemIntrinsic())
+    return;
+
+  Value *Ptr = MAI.getPointerOperand();
   if (!Ptr || !SE->isSCEVable(Ptr->getType()))
     return;
 
   auto *PtrSCEV = SE->getSCEV(Ptr);
   if (isa<SCEVCouldNotCompute>(PtrSCEV))
     return;
 
   auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);

 
 void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
   assert(!AccessRelation && "AccessReltation already built");
 
   isl_ctx *Ctx = isl_id_get_ctx(Id);
   isl_id *BaseAddrId = SAI->getBasePtrId();
 
   if (!isAffine()) {
+    if (isa<MemIntrinsic>(getAccessInstruction()))
+      buildMemIntrinsicAccessRelation();
+
     // We overapproximate non-affine accesses with a possible access to the
     // whole array. For read accesses it does not make a difference, if an
     // access must or may happen. However, for write accesses it is important to
     // differentiate between writes that must happen and writes that may happen.
+    if (!AccessRelation)
       AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
+
     AccessRelation =
         isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
     return;
   }
 
   isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0);
   AccessRelation = isl_map_universe(Space);
 
void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
   AccessRelation =
       isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
 
   AccessRelation = isl_map_gist_domain(AccessRelation, Statement->getDomain());
   isl_space_free(Space);
 }
 
 MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
-                           AccessType Type, Value *BaseAddress,
-                           unsigned ElemBytes, bool Affine,
+                           AccessType AccType, Value *BaseAddress,
+                           Type *ElementType, bool Affine,
                            ArrayRef<const SCEV *> Subscripts,
                            ArrayRef<const SCEV *> Sizes, Value *AccessValue,
                            ScopArrayInfo::MemoryKind Kind, StringRef BaseName)
-    : Kind(Kind), AccType(Type), RedType(RT_NONE), Statement(Stmt),
-      BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes),
+    : Kind(Kind), AccType(AccType), RedType(RT_NONE), Statement(Stmt),
+      BaseAddr(BaseAddress), BaseName(BaseName), ElementType(ElementType),
       Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
       AccessValue(AccessValue), IsAffine(Affine),
       Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
       NewAccessRelation(nullptr) {
   static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
-  const std::string Access = TypeStrings[Type] + utostr(Stmt->size()) + "_";
+  const std::string Access = TypeStrings[AccType] + utostr(Stmt->size()) + "_";
 
   std::string IdName =
       getIslCompatibleName(Stmt->getBaseName(), Access, BaseName);
   Id = isl_id_alloc(Stmt->getParent()->getIslCtx(), IdName.c_str(), this);
 }
 
 void MemoryAccess::realignParams() {
   isl_space *ParamSpace = Statement->getParent()->getParamSpace();
assert(isl_set_is_subset(NewDomain, Domain) &&
          "New domain is not a subset of old domain!");
   isl_set_free(Domain);
   Domain = NewDomain;
 }
 
 void ScopStmt::buildAccessRelations() {
   Scop &S = *getParent();
   for (MemoryAccess *Access : MemAccs) {
-    Type *ElementType = Access->getAccessValue()->getType();
+    Type *ElementType = Access->getElementType();
 
     ScopArrayInfo::MemoryKind Ty;
     if (Access->isPHIKind())
       Ty = ScopArrayInfo::MK_PHI;
     else if (Access->isExitPHIKind())
       Ty = ScopArrayInfo::MK_ExitPHI;
     else if (Access->isValueKind())
       Ty = ScopArrayInfo::MK_Value;
if (StmtDomainEmpty)
       continue;
 
     for (MemoryAccess *MA : Stmt) {
       if (MA->isScalarKind())
         continue;
       if (!MA->isRead())
         HasWriteAccess.insert(MA->getBaseAddr());
       MemAccInst Acc(MA->getAccessInstruction());
+      if (MA->isRead() && Acc.isMemTransferInst())
+        PtrToAcc[Acc.asMemTransferInst()->getSource()] = MA;
+      else
         PtrToAcc[Acc.getPointerOperand()] = MA;
       AST.add(Acc);
     }
   }
 
   SmallVector<AliasGroupTy, 4> AliasGroups;
   for (AliasSet &AS : AST) {
     if (AS.isMustAlias() || AS.isForwardingAliasSet())
       continue;
     AliasGroupTy AG;
     for (auto &PR : AS)
       AG.push_back(PtrToAcc[PR.getValue()]);
-    assert(AG.size() > 1 &&
-           "Alias groups should contain at least two accesses");
+    if (AG.size() < 2)
+      continue;
     AliasGroups.push_back(std::move(AG));
   }
 
   // Split the alias groups based on their domain.
   for (unsigned u = 0; u < AliasGroups.size(); u++) {
     AliasGroupTy NewAG;
     AliasGroupTy &AG = AliasGroups[u];
     AliasGroupTy::iterator AGI = AG.begin();
void ScopInfo::buildEscapingDependences(Instruction *Inst) {
   }
 }
 
 bool ScopInfo::buildAccessMultiDimFixed(
     MemAccInst Inst, Loop *L, Region *R,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
     const InvariantLoadsSetTy &ScopRIL) {
   Value *Val = Inst.getValueOperand();
-  Type *SizeType = Val->getType();
-  unsigned ElementSize = DL->getTypeAllocSize(SizeType);
+  Type *ElementType = Val->getType();
   Value *Address = Inst.getPointerOperand();
   const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
   enum MemoryAccess::AccessType Type =
       Inst.isLoad() ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
   if (isa<GetElementPtrInst>(Address) || isa<BitCastInst>(Address)) {
if (auto *GEP = dyn_cast<GetElementPtrInst>(NewAddress)) {
             return false;
       }
 
       if (Sizes.size() > 0) {
         for (auto V : Sizes)
           SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
               IntegerType::getInt64Ty(BasePtr->getContext()), V)));
 
-        addArrayAccess(Inst, Type, BasePointer->getValue(), ElementSize, true,
+        addArrayAccess(Inst, Type, BasePointer->getValue(), ElementType, true,
                        Subscripts, SizesSCEV, Val);
         return true;
       }
     }
   }
   return false;
 }
 
 bool ScopInfo::buildAccessMultiDimParam(
     MemAccInst Inst, Loop *L, Region *R,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
     const InvariantLoadsSetTy &ScopRIL, const MapInsnToMemAcc &InsnToMemAcc) {
   Value *Address = Inst.getPointerOperand();
   Value *Val = Inst.getValueOperand();
-  Type *SizeType = Val->getType();
-  unsigned ElementSize = DL->getTypeAllocSize(SizeType);
+  Type *ElementType = Val->getType();
+  unsigned ElementSize = DL->getTypeAllocSize(ElementType);
   enum MemoryAccess::AccessType Type =
       Inst.isLoad() ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
   const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
 
   assert(BasePointer && "Could not find base pointer");
if (PollyDelinearize && AccItr != InsnToMemAcc.end()) {
     //
     // 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,
+    addArrayAccess(Inst, Type, BasePointer->getValue(), ElementType, true,
                    AccItr->second.DelinearizedSubscripts, Sizes, Val);
     return true;
   }
   return false;
 }
 
+bool ScopInfo::buildAccessMemIntrinsic(
+    MemAccInst Inst, Loop *L, Region *R,
+    const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
+    const InvariantLoadsSetTy &ScopRIL) {
+  if (!Inst.isMemIntrinsic())
+    return false;
+
+  auto *LengthVal = SE->getSCEVAtScope(Inst.asMemIntrinsic()->getLength(), L);
+  assert(LengthVal);
+
+  auto *DestPtrVal = Inst.asMemIntrinsic()->getDest();
+  assert(DestPtrVal);
+  auto *DestAccFunc = SE->getSCEVAtScope(DestPtrVal, L);
+  assert(DestAccFunc);
+  auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(DestAccFunc));
+  assert(DestPtrSCEV);
+  DestAccFunc = SE->getMinusSCEV(DestAccFunc, DestPtrSCEV);
+  addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
+                 IntegerType::getInt8Ty(DestPtrVal->getContext()), false,
+                 {DestAccFunc, LengthVal}, {}, Inst.getValueOperand());
+
+  if (!Inst.isMemTransferInst())
+    return true;
+
+  auto *SrcPtrVal = Inst.asMemTransferInst()->getSource();
+  assert(SrcPtrVal);
+  auto *SrcAccFunc = SE->getSCEVAtScope(SrcPtrVal, L);
+  assert(SrcAccFunc);
+  auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccFunc));
+  assert(SrcPtrSCEV);
+  SrcAccFunc = SE->getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
+  addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
+                 IntegerType::getInt8Ty(SrcPtrVal->getContext()), false,
+                 {SrcAccFunc, LengthVal}, {}, Inst.getValueOperand());
+
+  return true;
+}
+
 void ScopInfo::buildAccessSingleDim(
     MemAccInst Inst, Loop *L, Region *R,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
     const InvariantLoadsSetTy &ScopRIL) {
   Value *Address = Inst.getPointerOperand();
   Value *Val = Inst.getValueOperand();
-  Type *SizeType = Val->getType();
-  unsigned ElementSize = DL->getTypeAllocSize(SizeType);
+  Type *ElementType = Val->getType();
   enum MemoryAccess::AccessType Type =
       Inst.isLoad() ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
 
   const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
 
   assert(BasePointer && "Could not find base pointer");
void ScopInfo::buildAccessSingleDim(
 
   for (LoadInst *LInst : AccessILS)
     if (!ScopRIL.count(LInst))
       IsAffine = false;
 
   if (!IsAffine && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;
 
-  addArrayAccess(Inst, Type, BasePointer->getValue(), ElementSize, IsAffine,
+  addArrayAccess(Inst, Type, BasePointer->getValue(), ElementType, IsAffine,
                  {AccessFunction}, {}, Val);
 }
 
 void ScopInfo::buildMemoryAccess(
     MemAccInst Inst, Loop *L, Region *R,
     const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
     const InvariantLoadsSetTy &ScopRIL, const MapInsnToMemAcc &InsnToMemAcc) {
 
+  if (buildAccessMemIntrinsic(Inst, L, R, BoxedLoops, ScopRIL))
+    return;
+
   if (buildAccessMultiDimFixed(Inst, L, R, BoxedLoops, ScopRIL))
     return;
 
   if (buildAccessMultiDimParam(Inst, L, R, BoxedLoops, ScopRIL, InsnToMemAcc))
     return;
 
   buildAccessSingleDim(Inst, L, R, BoxedLoops, ScopRIL);
 }
for (Instruction &Inst : BB) {
     if (!PHI)
       buildScalarDependences(&Inst);
     if (!IsExitBlock)
       buildEscapingDependences(&Inst);
   }
 }
 
 MemoryAccess *ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
-                                        MemoryAccess::AccessType Type,
-                                        Value *BaseAddress, unsigned ElemBytes,
+                                        MemoryAccess::AccessType AccType,
+                                        Value *BaseAddress, Type *ElementType,
                                         bool Affine, Value *AccessValue,
                                         ArrayRef<const SCEV *> Subscripts,
                                         ArrayRef<const SCEV *> Sizes,
                                         ScopArrayInfo::MemoryKind Kind) {
   ScopStmt *Stmt = scop->getStmtForBasicBlock(BB);
 
   // Do not create a memory access for anything not in the SCoP. It would be
   // ignored anyway.
MemoryAccess *ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
   }
 
   // Non-affine PHI writes do not "happen" at a particular instruction, but
   // after exiting the statement. Therefore they are guaranteed execute and
   // overwrite the old value.
   if (Kind == ScopArrayInfo::MK_PHI || Kind == ScopArrayInfo::MK_ExitPHI)
     isKnownMustAccess = true;
 
-  if (!isKnownMustAccess && Type == MemoryAccess::MUST_WRITE)
-    Type = MemoryAccess::MAY_WRITE;
+  if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
+    AccType = MemoryAccess::MAY_WRITE;
 
-  AccList.emplace_back(Stmt, Inst, Type, BaseAddress, ElemBytes, Affine,
+  AccList.emplace_back(Stmt, Inst, AccType, BaseAddress, ElementType, Affine,
                        Subscripts, Sizes, AccessValue, Kind, BaseName);
   Stmt->addAccess(&AccList.back());
   return &AccList.back();
 }
 
 void ScopInfo::addArrayAccess(MemAccInst MemAccInst,
-                              MemoryAccess::AccessType Type, Value *BaseAddress,
-                              unsigned ElemBytes, bool IsAffine,
-                              ArrayRef<const SCEV *> Subscripts,
+                              MemoryAccess::AccessType AccType,
+                              Value *BaseAddress, Type *ElementType,
+                              bool IsAffine, ArrayRef<const SCEV *> Subscripts,
                               ArrayRef<const SCEV *> Sizes,
                               Value *AccessValue) {
-  assert(MemAccInst.isLoad() == (Type == MemoryAccess::READ));
-  addMemoryAccess(MemAccInst.getParent(), MemAccInst, Type, BaseAddress,
-                  ElemBytes, IsAffine, AccessValue, Subscripts, Sizes,
+  addMemoryAccess(MemAccInst.getParent(), MemAccInst, AccType, BaseAddress,
+                  ElementType, IsAffine, AccessValue, Subscripts, Sizes,
                   ScopArrayInfo::MK_Array);
 }
 
 void ScopInfo::ensureValueWrite(Instruction *Inst) {
   ScopStmt *Stmt = scop->getStmtForBasicBlock(Inst->getParent());
 
   // Inst not defined within this SCoP.
   if (!Stmt)
     return;
 
   // Do not process further if the instruction is already written.
   if (Stmt->lookupValueWriteOf(Inst))
     return;
 
-  addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst, 1,
-                  true, Inst, ArrayRef<const SCEV *>(),
+  addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
+                  Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
                   ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value);
 }
 
 void ScopInfo::ensureValueRead(Value *V, BasicBlock *UserBB) {
 
   // There cannot be an "access" for literal constants. BasicBlock references
   // (jump destinations) also never change.
   if ((isa<Constant>(V) && !isa<GlobalVariable>(V)) || isa<BasicBlock>(V))
void ScopInfo::ensureValueRead(Value *V, BasicBlock *UserBB) {
   if (ValueStmt == UserStmt)
     return;
 
   // Do not create another MemoryAccess for reloading the value if one already
   // exists.
   if (UserStmt->lookupValueReadOf(V))
     return;
 
-  addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, 1, true, V,
+  addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true, V,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   ScopArrayInfo::MK_Value);
   if (ValueInst)
     ensureValueWrite(ValueInst);
 }
 
 void ScopInfo::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
                               Value *IncomingValue, bool IsExitBlock) {
if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
     assert(Acc->getAccessInstruction() == PHI);
     Acc->addIncoming(IncomingBlock, IncomingValue);
     return;
   }
 
   MemoryAccess *Acc = addMemoryAccess(
       IncomingStmt->isBlockStmt() ? IncomingBlock
                                   : IncomingStmt->getRegion()->getEntry(),
-      PHI, MemoryAccess::MUST_WRITE, PHI, 1, true, PHI,
+      PHI, MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true, PHI,
       ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
       IsExitBlock ? ScopArrayInfo::MK_ExitPHI : ScopArrayInfo::MK_PHI);
   assert(Acc);
   Acc->addIncoming(IncomingBlock, IncomingValue);
 }
 
 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
-  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
-                  ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  ScopArrayInfo::MK_PHI);
+  addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
+                  PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
+                  ArrayRef<const SCEV *>(), ScopArrayInfo::MK_PHI);
 }
 
 void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {
   unsigned MaxLoopDepth = getMaxLoopDepthInRegion(R, *LI, *SD);
   scop.reset(new Scop(R, *SE, MaxLoopDepth));
 
   buildStmts(R, R);
   buildAccessFunctions(R, R, *SD->getInsnToMemAccMap(&R));

polly/trunk/test/ScopInfo/memcpy.ll

+; RUN: opt %loadPolly -basicaa -polly-allow-differing-element-types -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -S -basicaa -polly-allow-differing-element-types -polly-codegen < %s | FileCheck --check-prefix=IR %s
+;
+; CHECK:         Arrays {
+; CHECK-NEXT:        i8 MemRef_A[*]; // Element size 1
+; CHECK-NEXT:        i8 MemRef_B[*]; // Element size 1
+; CHECK-NEXT:    }
+; CHECK:         Statements {
+; CHECK-NEXT:       Stmt_for_body3
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] -> [i0, i1] };
+; CHECK-NEXT:            MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] -> MemRef_A[o0] : -16 <= o0 <= 20 };
+; CHECK-NEXT:            ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] -> MemRef_B[o0] : 64 <= o0 <= 100 };
+;
+; IR: polly.loop_preheader:
+; IR:   %[[r1:[a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 -4
+; IR:   %[[r2:[a-zA-Z0-9]*]] = bitcast i32* %scevgep to i8*
+; IR:   %[[r3:[a-zA-Z0-9]*]] = getelementptr i64, i64* %B, i64 8
+; IR:   %[[r4:[a-zA-Z0-9]*]] = bitcast i64* %scevgep8 to i8*
+;
+; IR: polly.stmt.for.body3:
+; IR:   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %[[r2]], i8* %[[r4]], i64 37, i32 4, i1 false)
+;
+;
+;    #include <string.h>
+;
+;    void jd(int *restrict A, long *restrict B) {
+;      for (int i = 0; i < 1024; i++)
+;        for (int j = 0; j < 1024; j++)
+;          memcpy(A - 4, B + 8, 37);
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* noalias %A, i64* noalias %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc5, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc6, %for.inc5 ]
+  %exitcond1 = icmp ne i32 %i.0, 1024
+  br i1 %exitcond1, label %for.body, label %for.end7
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %j.0, 1024
+  br i1 %exitcond, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %add.ptr = getelementptr inbounds i32, i32* %A, i64 -4
+  %tmp = bitcast i32* %add.ptr to i8*
+  %add.ptr4 = getelementptr inbounds i64, i64* %B, i64 8
+  %tmp2 = bitcast i64* %add.ptr4 to i8*
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %tmp, i8* %tmp2, i64 37, i32 4, i1 false)
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %inc = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc5
+
+for.inc5:                                         ; preds = %for.end
+  %inc6 = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end7:                                         ; preds = %for.cond
+  ret void
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1) #1
+

polly/trunk/test/ScopInfo/memmove.ll

+; RUN: opt %loadPolly -basicaa -polly-allow-differing-element-types -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -S -basicaa -polly-allow-differing-element-types -polly-codegen < %s | FileCheck --check-prefix=IR %s
+;
+; CHECK:         Arrays {
+; CHECK-NEXT:        i8 MemRef_A[*]; // Element size 1
+; CHECK-NEXT:        i8 MemRef_B[*]; // Element size 1
+; CHECK-NEXT:    }
+; CHECK:         Statements {
+; CHECK-NEXT:       Stmt_for_body3
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] -> [i0, i1] };
+; CHECK-NEXT:            MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] -> MemRef_A[o0] : -16 <= o0 <= 15 };
+; CHECK-NEXT:            ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] -> MemRef_B[o0] : 64 <= o0 <= 95 };
+;
+; IR: polly.loop_preheader:
+; IR:   %[[r1:[a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 -4
+; IR:   %[[r2:[a-zA-Z0-9]*]] = bitcast i32* %scevgep to i8*
+; IR:   %[[r3:[a-zA-Z0-9]*]] = getelementptr i64, i64* %B, i64 8
+; IR:   %[[r4:[a-zA-Z0-9]*]] = bitcast i64* %scevgep8 to i8*
+;
+; IR: polly.stmt.for.body3:
+; IR:   call void @llvm.memmove.p0i8.p0i8.i64(i8* %[[r2]], i8* %[[r4]], i64 32, i32 4, i1 false)
+;
+;    #include <string.h>
+;
+;    void jd(int *restrict A, long *restrict B) {
+;      for (int i = 0; i < 1024; i++)
+;        for (int j = 0; j < 1024; j++)
+;          memmove(A - 4, B + 8, 32);
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* noalias %A, i64* noalias %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc5, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc6, %for.inc5 ]
+  %exitcond1 = icmp ne i32 %i.0, 1024
+  br i1 %exitcond1, label %for.body, label %for.end7
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %j.0, 1024
+  br i1 %exitcond, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %add.ptr = getelementptr inbounds i32, i32* %A, i64 -4
+  %tmp = bitcast i32* %add.ptr to i8*
+  %add.ptr4 = getelementptr inbounds i64, i64* %B, i64 8
+  %tmp2 = bitcast i64* %add.ptr4 to i8*
+  call void @llvm.memmove.p0i8.p0i8.i64(i8* %tmp, i8* %tmp2, i64 32, i32 4, i1 false)
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %inc = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc5
+
+for.inc5:                                         ; preds = %for.end
+  %inc6 = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end7:                                         ; preds = %for.cond
+  ret void
+}
+
+declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1) #1
+

polly/trunk/test/ScopInfo/memset.ll

+; RUN: opt %loadPolly -polly-allow-differing-element-types -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -S -polly-allow-differing-element-types -polly-codegen < %s | FileCheck --check-prefix=IR %s
+;
+; CHECK:         Arrays {
+; CHECK-NEXT:        i8 MemRef_A[*]; // Element size 1
+; CHECK-NEXT:    }
+; CHECK:         Statements {
+; CHECK-NEXT:       Stmt_for_body3
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] -> [i0, i1] };
+; CHECK-NEXT:            MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                { Stmt_for_body3[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 186 };
+;
+; IR:   %[[r1:[a-zA-Z0-9]*]] = bitcast i32* %A to i8*
+;
+; IR: polly.stmt.for.body3:
+; IR:   call void @llvm.memset.p0i8.i64(i8* %[[r1]], i8 36, i64 187, i32 4, i1 false)
+;
+;    #include <string.h>
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        for (int j = 0; j < 1024; j++)
+;          memset(A, '$', 187);
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* noalias %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc4, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc5, %for.inc4 ]
+  %exitcond1 = icmp ne i32 %i.0, 1024
+  br i1 %exitcond1, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc, %for.body
+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %exitcond = icmp ne i32 %j.0, 1024
+  br i1 %exitcond, label %for.body3, label %for.end
+
+for.body3:                                        ; preds = %for.cond1
+  %tmp = bitcast i32* %A to i8*
+  call void @llvm.memset.p0i8.i64(i8* %tmp, i8 36, i64 187, i32 4, i1 false)
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body3
+  %inc = add nsw i32 %j.0, 1
+  br label %for.cond1
+
+for.end:                                          ; preds = %for.cond1
+  br label %for.inc4
+
+for.inc4:                                         ; preds = %for.end
+  %inc5 = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end6:                                         ; preds = %for.cond
+  ret void
+}
+
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) #1
+