Skip to content

Commit cea6193

Browse files
author
Johannes Doerfert
committedFeb 21, 2016
Support memory intrinsics
 This patch adds support for memcpy, memset and memmove intrinsics. They are represented as one (memset) or two (memcpy, memmove) memory accesses in the polyhedral model. These accesses have an access range that describes the summarized effect of the intrinsic, i.e., memset(&A[i], '$', N); is represented as a write access from A[i] to A[i+N]. Differential Revision: http://reviews.llvm.org/D5226 llvm-svn: 261489
·
llvmorg-21-initllvmorg-3.9.0-rc1
1 parent 91bb5bc commit cea6193

File tree

8 files changed

+554
-117
lines changed

8 files changed

+554
-117
lines changed
 

‎polly/include/polly/ScopDetection.h

+22-2
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,7 @@ class SCEVUnknown;
7070
class CallInst;
7171
class Instruction;
7272
class Value;
73+
class IntrinsicInst;
7374
}
7475

7576
namespace polly {
@@ -328,11 +329,21 @@ class ScopDetection : public FunctionPass {
328329
/// @return True if R is a Scop, false otherwise.
329330
bool isValidRegion(DetectionContext &Context) const;
330331

332+
/// @brief Check if an intrinsic call can be part of a Scop.
333+
///
334+
/// @param II The intrinsic call instruction to check.
335+
/// @param Context The current detection context.
336+
///
337+
/// @return True if the call instruction is valid, false otherwise.
338+
bool isValidIntrinsicInst(IntrinsicInst &II, DetectionContext &Context) const;
339+
331340
/// @brief Check if a call instruction can be part of a Scop.
332341
///
333-
/// @param CI The call instruction to check.
342+
/// @param CI The call instruction to check.
343+
/// @param Context The current detection context.
344+
///
334345
/// @return True if the call instruction is valid, false otherwise.
335-
static bool isValidCallInst(CallInst &CI);
346+
bool isValidCallInst(CallInst &CI, DetectionContext &Context) const;
336347

337348
/// @brief Check if the given loads could be invariant and can be hoisted.
338349
///
@@ -355,6 +366,15 @@ class ScopDetection : public FunctionPass {
355366
/// identified by Reg.
356367
bool isInvariant(const Value &Val, const Region &Reg) const;
357368

369+
/// @brief Check if the memory access caused by @p Inst is valid.
370+
///
371+
/// @param Inst The access instruction.
372+
/// @param AF The access function.
373+
/// @param BP The access base pointer.
374+
/// @param Context The current detection context.
375+
bool isValidAccess(Instruction *Inst, const SCEV *AF, const SCEVUnknown *BP,
376+
DetectionContext &Context) const;
377+
358378
/// @brief Check if a memory access can be part of a Scop.
359379
///
360380
/// @param Inst The instruction accessing the memory.

‎polly/include/polly/ScopInfo.h

+35-17
Original file line numberDiff line numberDiff line change
@@ -497,8 +497,8 @@ class MemoryAccess {
497497
/// @brief An unique name of the accessed array.
498498
std::string BaseName;
499499

500-
/// @brief Size in bytes of a single array element.
501-
unsigned ElemBytes;
500+
/// @brief Type a single array element wrt. this access.
501+
Type *ElementType;
502502

503503
/// @brief Size of each dimension of the accessed array.
504504
SmallVector<const SCEV *, 4> Sizes;
@@ -529,7 +529,8 @@ class MemoryAccess {
529529
/// @brief The value associated with this memory access.
530530
///
531531
/// - For array memory accesses (MK_Array) it is the loaded result or the
532-
/// stored value.
532+
/// stored value. If the access instruction is a memory intrinsic it
533+
/// the access value is also the memory intrinsic.
533534
/// - For accesses of kind MK_Value it is the access instruction itself.
534535
/// - For accesses of kind MK_PHI or MK_ExitPHI it is the PHI node itself
535536
/// (for both, READ and WRITE accesses).
@@ -574,8 +575,6 @@ class MemoryAccess {
574575
isl_map *NewAccessRelation;
575576
// @}
576577

577-
unsigned getElemSizeInBytes() const { return ElemBytes; }
578-
579578
bool isAffine() const { return IsAffine; }
580579

581580
__isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement);
@@ -627,6 +626,9 @@ class MemoryAccess {
627626
__isl_give isl_map *foldAccess(__isl_take isl_map *AccessRelation,
628627
ScopStmt *Statement);
629628

629+
/// @brief Create the access relation for the underlying memory intrinsic.
630+
void buildMemIntrinsicAccessRelation();
631+
630632
/// @brief Assemble the access relation from all availbale information.
631633
///
632634
/// In particular, used the information passes in the constructor and the
@@ -641,15 +643,15 @@ class MemoryAccess {
641643
/// @param Stmt The parent statement.
642644
/// @param AccessInst The instruction doing the access.
643645
/// @param BaseAddr The accessed array's address.
644-
/// @param ElemBytes Number of accessed bytes.
646+
/// @param ElemType The type of the accessed array elements.
645647
/// @param AccType Whether read or write access.
646648
/// @param IsAffine Whether the subscripts are affine expressions.
647649
/// @param Kind The kind of memory accessed.
648650
/// @param Subscripts Subscipt expressions
649651
/// @param Sizes Dimension lengths of the accessed array.
650652
/// @param BaseName Name of the acessed array.
651-
MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType Type,
652-
Value *BaseAddress, unsigned ElemBytes, bool Affine,
653+
MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType AccType,
654+
Value *BaseAddress, Type *ElemType, bool Affine,
653655
ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
654656
Value *AccessValue, ScopArrayInfo::MemoryKind Kind,
655657
StringRef BaseName);
@@ -754,6 +756,9 @@ class MemoryAccess {
754756

755757
const std::string &getBaseName() const { return BaseName; }
756758

759+
/// @brief Return the element type of the accessed array wrt. this access.
760+
Type *getElementType() const { return ElementType; }
761+
757762
/// @brief Return the access value of this memory access.
758763
Value *getAccessValue() const { return AccessValue; }
759764

@@ -2066,6 +2071,19 @@ class ScopInfo : public RegionPass {
20662071
const InvariantLoadsSetTy &ScopRIL,
20672072
const MapInsnToMemAcc &InsnToMemAcc);
20682073

2074+
/// @brief Try to build a MemoryAccess for a memory intrinsic.
2075+
///
2076+
/// @param Inst The instruction that access the memory
2077+
/// @param L The parent loop of the instruction
2078+
/// @param R The region on which to build the data access dictionary.
2079+
/// @param BoxedLoops The set of loops that are overapproximated in @p R.
2080+
/// @param ScopRIL The required invariant loads equivalence classes.
2081+
///
2082+
/// @returns True if the access could be built, False otherwise.
2083+
bool buildAccessMemIntrinsic(MemAccInst Inst, Loop *L, Region *R,
2084+
const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
2085+
const InvariantLoadsSetTy &ScopRIL);
2086+
20692087
/// @brief Build a single-dimensional parameteric sized MemoryAccess
20702088
/// from the Load/Store instruction.
20712089
///
@@ -2147,9 +2165,9 @@ class ScopInfo : public RegionPass {
21472165
/// @param BB The block where the access takes place.
21482166
/// @param Inst The instruction doing the access. It is not necessarily
21492167
/// inside @p BB.
2150-
/// @param Type The kind of access.
2168+
/// @param AccType The kind of access.
21512169
/// @param BaseAddress The accessed array's base address.
2152-
/// @param ElemBytes Size of accessed array element.
2170+
/// @param ElemType The type of the accessed array elements.
21532171
/// @param Affine Whether all subscripts are affine expressions.
21542172
/// @param AccessValue Value read or written.
21552173
/// @param Subscripts Access subscripts per dimension.
@@ -2159,9 +2177,9 @@ class ScopInfo : public RegionPass {
21592177
/// @return The created MemoryAccess, or nullptr if the access is not within
21602178
/// the SCoP.
21612179
MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst,
2162-
MemoryAccess::AccessType Type,
2163-
Value *BaseAddress, unsigned ElemBytes,
2164-
bool Affine, Value *AccessValue,
2180+
MemoryAccess::AccessType AccType,
2181+
Value *BaseAddress, Type *ElemType, bool Affine,
2182+
Value *AccessValue,
21652183
ArrayRef<const SCEV *> Subscripts,
21662184
ArrayRef<const SCEV *> Sizes,
21672185
ScopArrayInfo::MemoryKind Kind);
@@ -2170,17 +2188,17 @@ class ScopInfo : public RegionPass {
21702188
/// StoreInst.
21712189
///
21722190
/// @param MemAccInst The LoadInst or StoreInst.
2173-
/// @param Type The kind of access.
2191+
/// @param AccType The kind of access.
21742192
/// @param BaseAddress The accessed array's base address.
2175-
/// @param ElemBytes Size of accessed array element.
2193+
/// @param ElemType The type of the accessed array elements.
21762194
/// @param IsAffine Whether all subscripts are affine expressions.
21772195
/// @param Subscripts Access subscripts per dimension.
21782196
/// @param Sizes The array dimension's sizes.
21792197
/// @param AccessValue Value read or written.
21802198
///
21812199
/// @see ScopArrayInfo::MemoryKind
2182-
void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType Type,
2183-
Value *BaseAddress, unsigned ElemBytes, bool IsAffine,
2200+
void addArrayAccess(MemAccInst MemAccInst, MemoryAccess::AccessType AccType,
2201+
Value *BaseAddress, Type *ElemType, bool IsAffine,
21842202
ArrayRef<const SCEV *> Subscripts,
21852203
ArrayRef<const SCEV *> Sizes, Value *AccessValue);
21862204

‎polly/include/polly/Support/ScopHelper.h

+50-7
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717
#include "llvm/ADT/DenseMap.h"
1818
#include "llvm/ADT/SetVector.h"
1919
#include "llvm/IR/Instructions.h"
20+
#include "llvm/IR/IntrinsicInst.h"
2021
#include "llvm/IR/ValueHandle.h"
2122

2223
namespace llvm {
@@ -42,18 +43,20 @@ using InvariantLoadsSetTy = llvm::SetVector<llvm::AssertingVH<llvm::LoadInst>>;
4243
/// @brief Utility proxy to wrap the common members of LoadInst and StoreInst.
4344
///
4445
/// This works like the LLVM utility class CallSite, ie. it forwards all calls
45-
/// to either a LoadInst or StoreInst.
46+
/// to either a LoadInst, StoreInst, MemIntrinsic or MemTransferInst.
4647
/// It is similar to LLVM's utility classes IntrinsicInst, MemIntrinsic,
4748
/// MemTransferInst, etc. in that it offers a common interface, but does not act
4849
/// as a fake base class.
4950
/// It is similar to StringRef and ArrayRef in that it holds a pointer to the
5051
/// referenced object and should be passed by-value as it is small enough.
5152
///
5253
/// This proxy can either represent a LoadInst instance, a StoreInst instance,
53-
/// or a nullptr (only creatable using the default constructor); never an
54-
/// Instruction that is not a load or store.
55-
/// When representing a nullptr, only the following methods are defined:
56-
/// isNull(), isInstruction(), isLoad(), isStore(), operator bool(), operator!()
54+
/// a MemIntrinsic instance (memset, memmove, memcpy) or a nullptr (only
55+
/// creatable using the default constructor); never an Instruction that is
56+
/// neither of the above mentioned. When representing a nullptr, only the
57+
/// following methods are defined:
58+
/// isNull(), isInstruction(), isLoad(), isStore(), ..., isMemTransferInst(),
59+
/// operator bool(), operator!()
5760
///
5861
/// The functions isa, cast, cast_or_null, dyn_cast are modeled te resemble
5962
/// those from llvm/Support/Casting.h. Partial template function specialization
@@ -71,14 +74,17 @@ class MemAccInst {
7174
/* implicit */ MemAccInst(llvm::LoadInst *LI) : I(LI) {}
7275
/* implicit */ MemAccInst(llvm::StoreInst &SI) : I(&SI) {}
7376
/* implicit */ MemAccInst(llvm::StoreInst *SI) : I(SI) {}
77+
/* implicit */ MemAccInst(llvm::MemIntrinsic *MI) : I(MI) {}
7478
explicit MemAccInst(llvm::Instruction &I) : I(&I) { assert(isa(I)); }
7579
explicit MemAccInst(llvm::Instruction *I) : I(I) { assert(isa(I)); }
7680

7781
static bool isa(const llvm::Value &V) {
78-
return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V);
82+
return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V) ||
83+
llvm::isa<llvm::MemIntrinsic>(V);
7984
}
8085
static bool isa(const llvm::Value *V) {
81-
return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V);
86+
return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V) ||
87+
llvm::isa<llvm::MemIntrinsic>(V);
8288
}
8389
static MemAccInst cast(llvm::Value &V) {
8490
return MemAccInst(llvm::cast<llvm::Instruction>(V));
@@ -126,6 +132,14 @@ class MemAccInst {
126132
I = SI;
127133
return *this;
128134
}
135+
MemAccInst &operator=(llvm::MemIntrinsic &MI) {
136+
I = &MI;
137+
return *this;
138+
}
139+
MemAccInst &operator=(llvm::MemIntrinsic *MI) {
140+
I = MI;
141+
return *this;
142+
}
129143

130144
operator llvm::Instruction *() const { return asInstruction(); }
131145
explicit operator bool() const { return isInstruction(); }
@@ -152,13 +166,17 @@ class MemAccInst {
152166
return asLoad();
153167
if (isStore())
154168
return asStore()->getValueOperand();
169+
if (isMemIntrinsic())
170+
return nullptr;
155171
llvm_unreachable("Operation not supported on nullptr");
156172
}
157173
llvm::Value *getPointerOperand() const {
158174
if (isLoad())
159175
return asLoad()->getPointerOperand();
160176
if (isStore())
161177
return asStore()->getPointerOperand();
178+
if (isMemIntrinsic())
179+
return asMemIntrinsic()->getDest();
162180
llvm_unreachable("Operation not supported on nullptr");
163181
}
164182

@@ -167,45 +185,70 @@ class MemAccInst {
167185
return asLoad()->getAlignment();
168186
if (isStore())
169187
return asStore()->getAlignment();
188+
if (isMemIntrinsic())
189+
return asMemIntrinsic()->getAlignment();
170190
llvm_unreachable("Operation not supported on nullptr");
171191
}
172192
bool isVolatile() const {
173193
if (isLoad())
174194
return asLoad()->isVolatile();
175195
if (isStore())
176196
return asStore()->isVolatile();
197+
if (isMemIntrinsic())
198+
return asMemIntrinsic()->isVolatile();
177199
llvm_unreachable("Operation not supported on nullptr");
178200
}
179201
bool isSimple() const {
180202
if (isLoad())
181203
return asLoad()->isSimple();
182204
if (isStore())
183205
return asStore()->isSimple();
206+
if (isMemIntrinsic())
207+
return !asMemIntrinsic()->isVolatile();
184208
llvm_unreachable("Operation not supported on nullptr");
185209
}
186210
llvm::AtomicOrdering getOrdering() const {
187211
if (isLoad())
188212
return asLoad()->getOrdering();
189213
if (isStore())
190214
return asStore()->getOrdering();
215+
if (isMemIntrinsic())
216+
return llvm::AtomicOrdering::NotAtomic;
191217
llvm_unreachable("Operation not supported on nullptr");
192218
}
193219
bool isUnordered() const {
194220
if (isLoad())
195221
return asLoad()->isUnordered();
196222
if (isStore())
197223
return asStore()->isUnordered();
224+
// Copied from the Load/Store implementation of isUnordered:
225+
if (isMemIntrinsic())
226+
return !asMemIntrinsic()->isVolatile();
198227
llvm_unreachable("Operation not supported on nullptr");
199228
}
200229

201230
bool isNull() const { return !I; }
202231
bool isInstruction() const { return I; }
203232
bool isLoad() const { return I && llvm::isa<llvm::LoadInst>(I); }
204233
bool isStore() const { return I && llvm::isa<llvm::StoreInst>(I); }
234+
bool isMemIntrinsic() const { return I && llvm::isa<llvm::MemIntrinsic>(I); }
235+
bool isMemSetInst() const { return I && llvm::isa<llvm::MemSetInst>(I); }
236+
bool isMemTransferInst() const {
237+
return I && llvm::isa<llvm::MemTransferInst>(I);
238+
}
205239

206240
llvm::Instruction *asInstruction() const { return I; }
207241
llvm::LoadInst *asLoad() const { return llvm::cast<llvm::LoadInst>(I); }
208242
llvm::StoreInst *asStore() const { return llvm::cast<llvm::StoreInst>(I); }
243+
llvm::MemIntrinsic *asMemIntrinsic() const {
244+
return llvm::cast<llvm::MemIntrinsic>(I);
245+
}
246+
llvm::MemSetInst *asMemSetInst() const {
247+
return llvm::cast<llvm::MemSetInst>(I);
248+
}
249+
llvm::MemTransferInst *asMemTransferInst() const {
250+
return llvm::cast<llvm::MemTransferInst>(I);
251+
}
209252
};
210253

211254
/// @brief Check if the PHINode has any incoming Invoke edge.

‎polly/lib/Analysis/ScopDetection.cpp

+108-53
Original file line numberDiff line numberDiff line change
@@ -34,8 +34,8 @@
3434
//
3535
// * Side effect free functions call
3636
//
37-
// Only function calls and intrinsics that do not have side effects are allowed
38-
// (readnone).
37+
// Function calls and intrinsics that do not have side effects (readnone)
38+
// or memory intrinsics (memset, memcpy, memmove) are allowed.
3939
//
4040
// The Scop detection finds the largest Scops by checking if the largest
4141
// region is a Scop. If this is not the case, its canonical subregions are
@@ -453,21 +453,64 @@ bool ScopDetection::isValidCFG(BasicBlock &BB, bool IsLoopBranch,
453453
return isValidSwitch(BB, SI, Condition, IsLoopBranch, Context);
454454
}
455455

456-
bool ScopDetection::isValidCallInst(CallInst &CI) {
456+
bool ScopDetection::isValidCallInst(CallInst &CI,
457+
DetectionContext &Context) const {
457458
if (CI.doesNotReturn())
458459
return false;
459460

460461
if (CI.doesNotAccessMemory())
461462
return true;
462463

464+
if (auto *II = dyn_cast<IntrinsicInst>(&CI))
465+
return isValidIntrinsicInst(*II, Context);
466+
463467
Function *CalledFunction = CI.getCalledFunction();
464468

465469
// Indirect calls are not supported.
466470
if (CalledFunction == 0)
467471
return false;
468472

469-
if (isIgnoredIntrinsic(&CI))
473+
return false;
474+
}
475+
476+
bool ScopDetection::isValidIntrinsicInst(IntrinsicInst &II,
477+
DetectionContext &Context) const {
478+
if (isIgnoredIntrinsic(&II))
479+
return true;
480+
481+
// The closest loop surrounding the call instruction.
482+
Loop *L = LI->getLoopFor(II.getParent());
483+
484+
// The access function and base pointer for memory intrinsics.
485+
const SCEV *AF;
486+
const SCEVUnknown *BP;
487+
488+
switch (II.getIntrinsicID()) {
489+
// Memory intrinsics that can be represented are supported.
490+
case llvm::Intrinsic::memmove:
491+
case llvm::Intrinsic::memcpy:
492+
AF = SE->getSCEVAtScope(cast<MemTransferInst>(II).getSource(), L);
493+
BP = dyn_cast<SCEVUnknown>(SE->getPointerBase(AF));
494+
// Bail if the source pointer is not valid.
495+
if (!isValidAccess(&II, AF, BP, Context))
496+
return false;
497+
// Fall through
498+
case llvm::Intrinsic::memset:
499+
AF = SE->getSCEVAtScope(cast<MemIntrinsic>(II).getDest(), L);
500+
BP = dyn_cast<SCEVUnknown>(SE->getPointerBase(AF));
501+
// Bail if the destination pointer is not valid.
502+
if (!isValidAccess(&II, AF, BP, Context))
503+
return false;
504+
505+
// Bail if the length is not affine.
506+
if (!isAffine(SE->getSCEVAtScope(cast<MemIntrinsic>(II).getLength(), L),
507+
Context))
508+
return false;
509+
470510
return true;
511+
default:
512+
break;
513+
}
471514

472515
return false;
473516
}
@@ -762,78 +805,78 @@ bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const {
762805
return true;
763806
}
764807

765-
bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
766-
DetectionContext &Context) const {
767-
Region &CurRegion = Context.CurRegion;
768-
769-
Value *Ptr = Inst.getPointerOperand();
770-
Loop *L = LI->getLoopFor(Inst.getParent());
771-
const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L);
772-
const SCEVUnknown *BasePointer;
773-
Value *BaseValue;
774-
775-
BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
808+
bool ScopDetection::isValidAccess(Instruction *Inst, const SCEV *AF,
809+
const SCEVUnknown *BP,
810+
DetectionContext &Context) const {
776811

777-
if (!BasePointer)
812+
if (!BP)
778813
return invalid<ReportNoBasePtr>(Context, /*Assert=*/true, Inst);
779814

780-
BaseValue = BasePointer->getValue();
781-
782-
if (isa<UndefValue>(BaseValue))
815+
auto *BV = BP->getValue();
816+
if (isa<UndefValue>(BV))
783817
return invalid<ReportUndefBasePtr>(Context, /*Assert=*/true, Inst);
784818

819+
// FIXME: Think about allowing IntToPtrInst
820+
if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BV))
821+
return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
822+
785823
// Check that the base address of the access is invariant in the current
786824
// region.
787-
if (!isInvariant(*BaseValue, CurRegion))
788-
return invalid<ReportVariantBasePtr>(Context, /*Assert=*/true, BaseValue,
789-
Inst);
825+
if (!isInvariant(*BV, Context.CurRegion))
826+
return invalid<ReportVariantBasePtr>(Context, /*Assert=*/true, BV, Inst);
790827

791-
AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
828+
AF = SE->getMinusSCEV(AF, BP);
792829

793-
const SCEV *Size = SE->getElementSize(Inst);
794-
if (Context.ElementSize[BasePointer]) {
795-
if (!AllowDifferentTypes && Context.ElementSize[BasePointer] != Size)
830+
const SCEV *Size;
831+
if (!isa<MemIntrinsic>(Inst)) {
832+
Size = SE->getElementSize(Inst);
833+
} else {
834+
auto *SizeTy =
835+
SE->getEffectiveSCEVType(PointerType::getInt8PtrTy(SE->getContext()));
836+
Size = SE->getConstant(SizeTy, 8);
837+
}
838+
839+
if (Context.ElementSize[BP]) {
840+
if (!AllowDifferentTypes && Context.ElementSize[BP] != Size)
796841
return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true,
797-
Inst, BaseValue);
842+
Inst, BV);
798843

799-
Context.ElementSize[BasePointer] =
800-
SE->getSMinExpr(Size, Context.ElementSize[BasePointer]);
844+
Context.ElementSize[BP] = SE->getSMinExpr(Size, Context.ElementSize[BP]);
801845
} else {
802-
Context.ElementSize[BasePointer] = Size;
846+
Context.ElementSize[BP] = Size;
803847
}
804848

805-
bool isVariantInNonAffineLoop = false;
849+
bool IsVariantInNonAffineLoop = false;
806850
SetVector<const Loop *> Loops;
807-
findLoops(AccessFunction, Loops);
851+
findLoops(AF, Loops);
808852
for (const Loop *L : Loops)
809853
if (Context.BoxedLoopsSet.count(L))
810-
isVariantInNonAffineLoop = true;
811-
812-
if (PollyDelinearize && !isVariantInNonAffineLoop) {
813-
Context.Accesses[BasePointer].push_back({Inst, AccessFunction});
814-
815-
if (!isAffine(AccessFunction, Context, BaseValue))
816-
Context.NonAffineAccesses.insert(BasePointer);
817-
} else if (!AllowNonAffine) {
818-
if (isVariantInNonAffineLoop ||
819-
!isAffine(AccessFunction, Context, BaseValue))
820-
return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
821-
AccessFunction, Inst, BaseValue);
854+
IsVariantInNonAffineLoop = true;
855+
856+
bool IsAffine = !IsVariantInNonAffineLoop && isAffine(AF, Context, BV);
857+
// Do not try to delinearize memory intrinsics and force them to be affine.
858+
if (isa<MemIntrinsic>(Inst) && !IsAffine) {
859+
return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Inst,
860+
BV);
861+
} else if (PollyDelinearize && !IsVariantInNonAffineLoop) {
862+
Context.Accesses[BP].push_back({Inst, AF});
863+
864+
if (!IsAffine)
865+
Context.NonAffineAccesses.insert(BP);
866+
} else if (!AllowNonAffine && !IsAffine) {
867+
return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Inst,
868+
BV);
822869
}
823870

824-
// FIXME: Think about allowing IntToPtrInst
825-
if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BaseValue))
826-
return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
827-
828871
if (IgnoreAliasing)
829872
return true;
830873

831874
// Check if the base pointer of the memory access does alias with
832875
// any other pointer. This cannot be handled at the moment.
833876
AAMDNodes AATags;
834-
Inst.getAAMetadata(AATags);
877+
Inst->getAAMetadata(AATags);
835878
AliasSet &AS = Context.AST.getAliasSetForPointer(
836-
BaseValue, MemoryLocation::UnknownSize, AATags);
879+
BP->getValue(), MemoryLocation::UnknownSize, AATags);
837880

838881
if (!AS.isMustAlias()) {
839882
if (PollyUseRuntimeAliasChecks) {
@@ -845,9 +888,9 @@ bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
845888
// However, we can ignore loads that will be hoisted.
846889
for (const auto &Ptr : AS) {
847890
Instruction *Inst = dyn_cast<Instruction>(Ptr.getValue());
848-
if (Inst && CurRegion.contains(Inst)) {
891+
if (Inst && Context.CurRegion.contains(Inst)) {
849892
auto *Load = dyn_cast<LoadInst>(Inst);
850-
if (Load && isHoistableLoad(Load, CurRegion, *LI, *SE)) {
893+
if (Load && isHoistableLoad(Load, Context.CurRegion, *LI, *SE)) {
851894
Context.RequiredILS.insert(Load);
852895
continue;
853896
}
@@ -866,6 +909,18 @@ bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
866909
return true;
867910
}
868911

912+
bool ScopDetection::isValidMemoryAccess(MemAccInst Inst,
913+
DetectionContext &Context) const {
914+
Value *Ptr = Inst.getPointerOperand();
915+
Loop *L = LI->getLoopFor(Inst.getParent());
916+
const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L);
917+
const SCEVUnknown *BasePointer;
918+
919+
BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
920+
921+
return isValidAccess(Inst, AccessFunction, BasePointer, Context);
922+
}
923+
869924
bool ScopDetection::isValidInstruction(Instruction &Inst,
870925
DetectionContext &Context) const {
871926
for (auto &Op : Inst.operands()) {
@@ -880,7 +935,7 @@ bool ScopDetection::isValidInstruction(Instruction &Inst,
880935

881936
// We only check the call instruction but not invoke instruction.
882937
if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
883-
if (isValidCallInst(*CI))
938+
if (isValidCallInst(*CI, Context))
884939
return true;
885940

886941
return invalid<ReportFuncCall>(Context, /*Assert=*/true, &Inst);

‎polly/lib/Analysis/ScopInfo.cpp

+111-38
Original file line numberDiff line numberDiff line change
@@ -303,7 +303,10 @@ void MemoryAccess::updateDimensionality() {
303303
auto DimsAccess = isl_space_dim(AccessSpace, isl_dim_set);
304304
auto DimsMissing = DimsArray - DimsAccess;
305305

306+
auto *BB = getStatement()->getParent()->getRegion().getEntry();
307+
auto &DL = BB->getModule()->getDataLayout();
306308
unsigned ArrayElemSize = SAI->getElemSizeInBytes();
309+
unsigned ElemBytes = DL.getTypeAllocSize(getElementType());
307310

308311
auto *Map = isl_map_from_domain_and_range(
309312
isl_set_universe(AccessSpace),
@@ -612,10 +615,34 @@ void MemoryAccess::assumeNoOutOfBound() {
612615
isl_space_free(Space);
613616
}
614617

618+
void MemoryAccess::buildMemIntrinsicAccessRelation() {
619+
auto MAI = MemAccInst(getAccessInstruction());
620+
assert(MAI.isMemIntrinsic());
621+
assert(Subscripts.size() == 2 && Sizes.size() == 0);
622+
623+
auto *LengthPWA = Statement->getPwAff(Subscripts[1]);
624+
auto *LengthMap = isl_map_from_pw_aff(LengthPWA);
625+
auto *RangeSpace = isl_space_range(isl_map_get_space(LengthMap));
626+
LengthMap = isl_map_apply_range(LengthMap, isl_map_lex_gt(RangeSpace));
627+
LengthMap = isl_map_lower_bound_si(LengthMap, isl_dim_out, 0, 0);
628+
auto *SubscriptPWA = Statement->getPwAff(Subscripts[0]);
629+
auto *SubscriptMap = isl_map_from_pw_aff(SubscriptPWA);
630+
SubscriptMap =
631+
isl_map_align_params(SubscriptMap, isl_map_get_space(LengthMap));
632+
LengthMap = isl_map_align_params(LengthMap, isl_map_get_space(SubscriptMap));
633+
LengthMap = isl_map_sum(LengthMap, SubscriptMap);
634+
AccessRelation = isl_map_set_tuple_id(LengthMap, isl_dim_in,
635+
getStatement()->getDomainId());
636+
}
637+
615638
void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
616639
ScalarEvolution *SE = Statement->getParent()->getSE();
617640

618-
Value *Ptr = MemAccInst(getAccessInstruction()).getPointerOperand();
641+
auto MAI = MemAccInst(getAccessInstruction());
642+
if (MAI.isMemIntrinsic())
643+
return;
644+
645+
Value *Ptr = MAI.getPointerOperand();
619646
if (!Ptr || !SE->isSCEVable(Ptr->getType()))
620647
return;
621648

@@ -731,11 +758,16 @@ void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
731758
isl_id *BaseAddrId = SAI->getBasePtrId();
732759

733760
if (!isAffine()) {
761+
if (isa<MemIntrinsic>(getAccessInstruction()))
762+
buildMemIntrinsicAccessRelation();
763+
734764
// We overapproximate non-affine accesses with a possible access to the
735765
// whole array. For read accesses it does not make a difference, if an
736766
// access must or may happen. However, for write accesses it is important to
737767
// differentiate between writes that must happen and writes that may happen.
738-
AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
768+
if (!AccessRelation)
769+
AccessRelation = isl_map_from_basic_map(createBasicAccessMap(Statement));
770+
739771
AccessRelation =
740772
isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId);
741773
return;
@@ -764,19 +796,19 @@ void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {
764796
}
765797

766798
MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,
767-
AccessType Type, Value *BaseAddress,
768-
unsigned ElemBytes, bool Affine,
799+
AccessType AccType, Value *BaseAddress,
800+
Type *ElementType, bool Affine,
769801
ArrayRef<const SCEV *> Subscripts,
770802
ArrayRef<const SCEV *> Sizes, Value *AccessValue,
771803
ScopArrayInfo::MemoryKind Kind, StringRef BaseName)
772-
: Kind(Kind), AccType(Type), RedType(RT_NONE), Statement(Stmt),
773-
BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes),
804+
: Kind(Kind), AccType(AccType), RedType(RT_NONE), Statement(Stmt),
805+
BaseAddr(BaseAddress), BaseName(BaseName), ElementType(ElementType),
774806
Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),
775807
AccessValue(AccessValue), IsAffine(Affine),
776808
Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr),
777809
NewAccessRelation(nullptr) {
778810
static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};
779-
const std::string Access = TypeStrings[Type] + utostr(Stmt->size()) + "_";
811+
const std::string Access = TypeStrings[AccType] + utostr(Stmt->size()) + "_";
780812

781813
std::string IdName =
782814
getIslCompatibleName(Stmt->getBaseName(), Access, BaseName);
@@ -948,7 +980,7 @@ void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
948980
void ScopStmt::buildAccessRelations() {
949981
Scop &S = *getParent();
950982
for (MemoryAccess *Access : MemAccs) {
951-
Type *ElementType = Access->getAccessValue()->getType();
983+
Type *ElementType = Access->getElementType();
952984

953985
ScopArrayInfo::MemoryKind Ty;
954986
if (Access->isPHIKind())
@@ -2566,7 +2598,10 @@ bool Scop::buildAliasGroups(AliasAnalysis &AA) {
25662598
if (!MA->isRead())
25672599
HasWriteAccess.insert(MA->getBaseAddr());
25682600
MemAccInst Acc(MA->getAccessInstruction());
2569-
PtrToAcc[Acc.getPointerOperand()] = MA;
2601+
if (MA->isRead() && Acc.isMemTransferInst())
2602+
PtrToAcc[Acc.asMemTransferInst()->getSource()] = MA;
2603+
else
2604+
PtrToAcc[Acc.getPointerOperand()] = MA;
25702605
AST.add(Acc);
25712606
}
25722607
}
@@ -2578,8 +2613,8 @@ bool Scop::buildAliasGroups(AliasAnalysis &AA) {
25782613
AliasGroupTy AG;
25792614
for (auto &PR : AS)
25802615
AG.push_back(PtrToAcc[PR.getValue()]);
2581-
assert(AG.size() > 1 &&
2582-
"Alias groups should contain at least two accesses");
2616+
if (AG.size() < 2)
2617+
continue;
25832618
AliasGroups.push_back(std::move(AG));
25842619
}
25852620

@@ -3774,8 +3809,7 @@ bool ScopInfo::buildAccessMultiDimFixed(
37743809
const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
37753810
const InvariantLoadsSetTy &ScopRIL) {
37763811
Value *Val = Inst.getValueOperand();
3777-
Type *SizeType = Val->getType();
3778-
unsigned ElementSize = DL->getTypeAllocSize(SizeType);
3812+
Type *ElementType = Val->getType();
37793813
Value *Address = Inst.getPointerOperand();
37803814
const SCEV *AccessFunction = SE->getSCEVAtScope(Address, L);
37813815
const SCEVUnknown *BasePointer =
@@ -3816,7 +3850,7 @@ bool ScopInfo::buildAccessMultiDimFixed(
38163850
SizesSCEV.push_back(SE->getSCEV(ConstantInt::get(
38173851
IntegerType::getInt64Ty(BasePtr->getContext()), V)));
38183852

3819-
addArrayAccess(Inst, Type, BasePointer->getValue(), ElementSize, true,
3853+
addArrayAccess(Inst, Type, BasePointer->getValue(), ElementType, true,
38203854
Subscripts, SizesSCEV, Val);
38213855
return true;
38223856
}
@@ -3831,8 +3865,8 @@ bool ScopInfo::buildAccessMultiDimParam(
38313865
const InvariantLoadsSetTy &ScopRIL, const MapInsnToMemAcc &InsnToMemAcc) {
38323866
Value *Address = Inst.getPointerOperand();
38333867
Value *Val = Inst.getValueOperand();
3834-
Type *SizeType = Val->getType();
3835-
unsigned ElementSize = DL->getTypeAllocSize(SizeType);
3868+
Type *ElementType = Val->getType();
3869+
unsigned ElementSize = DL->getTypeAllocSize(ElementType);
38363870
enum MemoryAccess::AccessType Type =
38373871
Inst.isLoad() ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
38383872

@@ -3860,21 +3894,58 @@ bool ScopInfo::buildAccessMultiDimParam(
38603894
if (ElementSize != DelinearizedSize)
38613895
scop->invalidate(DELINEARIZATION, Inst.getDebugLoc());
38623896

3863-
addArrayAccess(Inst, Type, BasePointer->getValue(), ElementSize, true,
3897+
addArrayAccess(Inst, Type, BasePointer->getValue(), ElementType, true,
38643898
AccItr->second.DelinearizedSubscripts, Sizes, Val);
38653899
return true;
38663900
}
38673901
return false;
38683902
}
38693903

3904+
bool ScopInfo::buildAccessMemIntrinsic(
3905+
MemAccInst Inst, Loop *L, Region *R,
3906+
const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
3907+
const InvariantLoadsSetTy &ScopRIL) {
3908+
if (!Inst.isMemIntrinsic())
3909+
return false;
3910+
3911+
auto *LengthVal = SE->getSCEVAtScope(Inst.asMemIntrinsic()->getLength(), L);
3912+
assert(LengthVal);
3913+
3914+
auto *DestPtrVal = Inst.asMemIntrinsic()->getDest();
3915+
assert(DestPtrVal);
3916+
auto *DestAccFunc = SE->getSCEVAtScope(DestPtrVal, L);
3917+
assert(DestAccFunc);
3918+
auto *DestPtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(DestAccFunc));
3919+
assert(DestPtrSCEV);
3920+
DestAccFunc = SE->getMinusSCEV(DestAccFunc, DestPtrSCEV);
3921+
addArrayAccess(Inst, MemoryAccess::MUST_WRITE, DestPtrSCEV->getValue(),
3922+
IntegerType::getInt8Ty(DestPtrVal->getContext()), false,
3923+
{DestAccFunc, LengthVal}, {}, Inst.getValueOperand());
3924+
3925+
if (!Inst.isMemTransferInst())
3926+
return true;
3927+
3928+
auto *SrcPtrVal = Inst.asMemTransferInst()->getSource();
3929+
assert(SrcPtrVal);
3930+
auto *SrcAccFunc = SE->getSCEVAtScope(SrcPtrVal, L);
3931+
assert(SrcAccFunc);
3932+
auto *SrcPtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccFunc));
3933+
assert(SrcPtrSCEV);
3934+
SrcAccFunc = SE->getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
3935+
addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
3936+
IntegerType::getInt8Ty(SrcPtrVal->getContext()), false,
3937+
{SrcAccFunc, LengthVal}, {}, Inst.getValueOperand());
3938+
3939+
return true;
3940+
}
3941+
38703942
void ScopInfo::buildAccessSingleDim(
38713943
MemAccInst Inst, Loop *L, Region *R,
38723944
const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
38733945
const InvariantLoadsSetTy &ScopRIL) {
38743946
Value *Address = Inst.getPointerOperand();
38753947
Value *Val = Inst.getValueOperand();
3876-
Type *SizeType = Val->getType();
3877-
unsigned ElementSize = DL->getTypeAllocSize(SizeType);
3948+
Type *ElementType = Val->getType();
38783949
enum MemoryAccess::AccessType Type =
38793950
Inst.isLoad() ? MemoryAccess::READ : MemoryAccess::MUST_WRITE;
38803951

@@ -3907,7 +3978,7 @@ void ScopInfo::buildAccessSingleDim(
39073978
if (!IsAffine && Type == MemoryAccess::MUST_WRITE)
39083979
Type = MemoryAccess::MAY_WRITE;
39093980

3910-
addArrayAccess(Inst, Type, BasePointer->getValue(), ElementSize, IsAffine,
3981+
addArrayAccess(Inst, Type, BasePointer->getValue(), ElementType, IsAffine,
39113982
{AccessFunction}, {}, Val);
39123983
}
39133984

@@ -3916,6 +3987,9 @@ void ScopInfo::buildMemoryAccess(
39163987
const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
39173988
const InvariantLoadsSetTy &ScopRIL, const MapInsnToMemAcc &InsnToMemAcc) {
39183989

3990+
if (buildAccessMemIntrinsic(Inst, L, R, BoxedLoops, ScopRIL))
3991+
return;
3992+
39193993
if (buildAccessMultiDimFixed(Inst, L, R, BoxedLoops, ScopRIL))
39203994
return;
39213995

@@ -3999,8 +4073,8 @@ void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
39994073
}
40004074

40014075
MemoryAccess *ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
4002-
MemoryAccess::AccessType Type,
4003-
Value *BaseAddress, unsigned ElemBytes,
4076+
MemoryAccess::AccessType AccType,
4077+
Value *BaseAddress, Type *ElementType,
40044078
bool Affine, Value *AccessValue,
40054079
ArrayRef<const SCEV *> Subscripts,
40064080
ArrayRef<const SCEV *> Sizes,
@@ -4037,24 +4111,23 @@ MemoryAccess *ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
40374111
if (Kind == ScopArrayInfo::MK_PHI || Kind == ScopArrayInfo::MK_ExitPHI)
40384112
isKnownMustAccess = true;
40394113

4040-
if (!isKnownMustAccess && Type == MemoryAccess::MUST_WRITE)
4041-
Type = MemoryAccess::MAY_WRITE;
4114+
if (!isKnownMustAccess && AccType == MemoryAccess::MUST_WRITE)
4115+
AccType = MemoryAccess::MAY_WRITE;
40424116

4043-
AccList.emplace_back(Stmt, Inst, Type, BaseAddress, ElemBytes, Affine,
4117+
AccList.emplace_back(Stmt, Inst, AccType, BaseAddress, ElementType, Affine,
40444118
Subscripts, Sizes, AccessValue, Kind, BaseName);
40454119
Stmt->addAccess(&AccList.back());
40464120
return &AccList.back();
40474121
}
40484122

40494123
void ScopInfo::addArrayAccess(MemAccInst MemAccInst,
4050-
MemoryAccess::AccessType Type, Value *BaseAddress,
4051-
unsigned ElemBytes, bool IsAffine,
4052-
ArrayRef<const SCEV *> Subscripts,
4124+
MemoryAccess::AccessType AccType,
4125+
Value *BaseAddress, Type *ElementType,
4126+
bool IsAffine, ArrayRef<const SCEV *> Subscripts,
40534127
ArrayRef<const SCEV *> Sizes,
40544128
Value *AccessValue) {
4055-
assert(MemAccInst.isLoad() == (Type == MemoryAccess::READ));
4056-
addMemoryAccess(MemAccInst.getParent(), MemAccInst, Type, BaseAddress,
4057-
ElemBytes, IsAffine, AccessValue, Subscripts, Sizes,
4129+
addMemoryAccess(MemAccInst.getParent(), MemAccInst, AccType, BaseAddress,
4130+
ElementType, IsAffine, AccessValue, Subscripts, Sizes,
40584131
ScopArrayInfo::MK_Array);
40594132
}
40604133

@@ -4069,8 +4142,8 @@ void ScopInfo::ensureValueWrite(Instruction *Inst) {
40694142
if (Stmt->lookupValueWriteOf(Inst))
40704143
return;
40714144

4072-
addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst, 1,
4073-
true, Inst, ArrayRef<const SCEV *>(),
4145+
addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::MUST_WRITE, Inst,
4146+
Inst->getType(), true, Inst, ArrayRef<const SCEV *>(),
40744147
ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value);
40754148
}
40764149

@@ -4119,7 +4192,7 @@ void ScopInfo::ensureValueRead(Value *V, BasicBlock *UserBB) {
41194192
if (UserStmt->lookupValueReadOf(V))
41204193
return;
41214194

4122-
addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, 1, true, V,
4195+
addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, V, V->getType(), true, V,
41234196
ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
41244197
ScopArrayInfo::MK_Value);
41254198
if (ValueInst)
@@ -4149,17 +4222,17 @@ void ScopInfo::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
41494222
MemoryAccess *Acc = addMemoryAccess(
41504223
IncomingStmt->isBlockStmt() ? IncomingBlock
41514224
: IncomingStmt->getRegion()->getEntry(),
4152-
PHI, MemoryAccess::MUST_WRITE, PHI, 1, true, PHI,
4225+
PHI, MemoryAccess::MUST_WRITE, PHI, PHI->getType(), true, PHI,
41534226
ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
41544227
IsExitBlock ? ScopArrayInfo::MK_ExitPHI : ScopArrayInfo::MK_PHI);
41554228
assert(Acc);
41564229
Acc->addIncoming(IncomingBlock, IncomingValue);
41574230
}
41584231

41594232
void ScopInfo::addPHIReadAccess(PHINode *PHI) {
4160-
addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
4161-
ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
4162-
ScopArrayInfo::MK_PHI);
4233+
addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI,
4234+
PHI->getType(), true, PHI, ArrayRef<const SCEV *>(),
4235+
ArrayRef<const SCEV *>(), ScopArrayInfo::MK_PHI);
41634236
}
41644237

41654238
void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {

‎polly/test/ScopInfo/memcpy.ll

+80
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
; RUN: opt %loadPolly -basicaa -polly-allow-differing-element-types -polly-scops -analyze < %s | FileCheck %s
2+
; RUN: opt %loadPolly -S -basicaa -polly-allow-differing-element-types -polly-codegen < %s | FileCheck --check-prefix=IR %s
3+
;
4+
; CHECK: Arrays {
5+
; CHECK-NEXT: i8 MemRef_A[*]; // Element size 1
6+
; CHECK-NEXT: i8 MemRef_B[*]; // Element size 1
7+
; CHECK-NEXT: }
8+
; CHECK: Statements {
9+
; CHECK-NEXT: Stmt_for_body3
10+
; CHECK-NEXT: Domain :=
11+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 };
12+
; CHECK-NEXT: Schedule :=
13+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] -> [i0, i1] };
14+
; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
15+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] -> MemRef_A[o0] : -16 <= o0 <= 20 };
16+
; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
17+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] -> MemRef_B[o0] : 64 <= o0 <= 100 };
18+
;
19+
; IR: polly.loop_preheader:
20+
; IR: %[[r1:[a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 -4
21+
; IR: %[[r2:[a-zA-Z0-9]*]] = bitcast i32* %scevgep to i8*
22+
; IR: %[[r3:[a-zA-Z0-9]*]] = getelementptr i64, i64* %B, i64 8
23+
; IR: %[[r4:[a-zA-Z0-9]*]] = bitcast i64* %scevgep8 to i8*
24+
;
25+
; IR: polly.stmt.for.body3:
26+
; IR: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %[[r2]], i8* %[[r4]], i64 37, i32 4, i1 false)
27+
;
28+
;
29+
; #include <string.h>
30+
;
31+
; void jd(int *restrict A, long *restrict B) {
32+
; for (int i = 0; i < 1024; i++)
33+
; for (int j = 0; j < 1024; j++)
34+
; memcpy(A - 4, B + 8, 37);
35+
; }
36+
;
37+
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
38+
39+
define void @jd(i32* noalias %A, i64* noalias %B) {
40+
entry:
41+
br label %for.cond
42+
43+
for.cond: ; preds = %for.inc5, %entry
44+
%i.0 = phi i32 [ 0, %entry ], [ %inc6, %for.inc5 ]
45+
%exitcond1 = icmp ne i32 %i.0, 1024
46+
br i1 %exitcond1, label %for.body, label %for.end7
47+
48+
for.body: ; preds = %for.cond
49+
br label %for.cond1
50+
51+
for.cond1: ; preds = %for.inc, %for.body
52+
%j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
53+
%exitcond = icmp ne i32 %j.0, 1024
54+
br i1 %exitcond, label %for.body3, label %for.end
55+
56+
for.body3: ; preds = %for.cond1
57+
%add.ptr = getelementptr inbounds i32, i32* %A, i64 -4
58+
%tmp = bitcast i32* %add.ptr to i8*
59+
%add.ptr4 = getelementptr inbounds i64, i64* %B, i64 8
60+
%tmp2 = bitcast i64* %add.ptr4 to i8*
61+
call void @llvm.memcpy.p0i8.p0i8.i64(i8* %tmp, i8* %tmp2, i64 37, i32 4, i1 false)
62+
br label %for.inc
63+
64+
for.inc: ; preds = %for.body3
65+
%inc = add nsw i32 %j.0, 1
66+
br label %for.cond1
67+
68+
for.end: ; preds = %for.cond1
69+
br label %for.inc5
70+
71+
for.inc5: ; preds = %for.end
72+
%inc6 = add nsw i32 %i.0, 1
73+
br label %for.cond
74+
75+
for.end7: ; preds = %for.cond
76+
ret void
77+
}
78+
79+
declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1) #1
80+

‎polly/test/ScopInfo/memmove.ll

+79
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
; RUN: opt %loadPolly -basicaa -polly-allow-differing-element-types -polly-scops -analyze < %s | FileCheck %s
2+
; RUN: opt %loadPolly -S -basicaa -polly-allow-differing-element-types -polly-codegen < %s | FileCheck --check-prefix=IR %s
3+
;
4+
; CHECK: Arrays {
5+
; CHECK-NEXT: i8 MemRef_A[*]; // Element size 1
6+
; CHECK-NEXT: i8 MemRef_B[*]; // Element size 1
7+
; CHECK-NEXT: }
8+
; CHECK: Statements {
9+
; CHECK-NEXT: Stmt_for_body3
10+
; CHECK-NEXT: Domain :=
11+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 };
12+
; CHECK-NEXT: Schedule :=
13+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] -> [i0, i1] };
14+
; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
15+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] -> MemRef_A[o0] : -16 <= o0 <= 15 };
16+
; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
17+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] -> MemRef_B[o0] : 64 <= o0 <= 95 };
18+
;
19+
; IR: polly.loop_preheader:
20+
; IR: %[[r1:[a-zA-Z0-9]*]] = getelementptr i32, i32* %A, i64 -4
21+
; IR: %[[r2:[a-zA-Z0-9]*]] = bitcast i32* %scevgep to i8*
22+
; IR: %[[r3:[a-zA-Z0-9]*]] = getelementptr i64, i64* %B, i64 8
23+
; IR: %[[r4:[a-zA-Z0-9]*]] = bitcast i64* %scevgep8 to i8*
24+
;
25+
; IR: polly.stmt.for.body3:
26+
; IR: call void @llvm.memmove.p0i8.p0i8.i64(i8* %[[r2]], i8* %[[r4]], i64 32, i32 4, i1 false)
27+
;
28+
; #include <string.h>
29+
;
30+
; void jd(int *restrict A, long *restrict B) {
31+
; for (int i = 0; i < 1024; i++)
32+
; for (int j = 0; j < 1024; j++)
33+
; memmove(A - 4, B + 8, 32);
34+
; }
35+
;
36+
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
37+
38+
define void @jd(i32* noalias %A, i64* noalias %B) {
39+
entry:
40+
br label %for.cond
41+
42+
for.cond: ; preds = %for.inc5, %entry
43+
%i.0 = phi i32 [ 0, %entry ], [ %inc6, %for.inc5 ]
44+
%exitcond1 = icmp ne i32 %i.0, 1024
45+
br i1 %exitcond1, label %for.body, label %for.end7
46+
47+
for.body: ; preds = %for.cond
48+
br label %for.cond1
49+
50+
for.cond1: ; preds = %for.inc, %for.body
51+
%j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
52+
%exitcond = icmp ne i32 %j.0, 1024
53+
br i1 %exitcond, label %for.body3, label %for.end
54+
55+
for.body3: ; preds = %for.cond1
56+
%add.ptr = getelementptr inbounds i32, i32* %A, i64 -4
57+
%tmp = bitcast i32* %add.ptr to i8*
58+
%add.ptr4 = getelementptr inbounds i64, i64* %B, i64 8
59+
%tmp2 = bitcast i64* %add.ptr4 to i8*
60+
call void @llvm.memmove.p0i8.p0i8.i64(i8* %tmp, i8* %tmp2, i64 32, i32 4, i1 false)
61+
br label %for.inc
62+
63+
for.inc: ; preds = %for.body3
64+
%inc = add nsw i32 %j.0, 1
65+
br label %for.cond1
66+
67+
for.end: ; preds = %for.cond1
68+
br label %for.inc5
69+
70+
for.inc5: ; preds = %for.end
71+
%inc6 = add nsw i32 %i.0, 1
72+
br label %for.cond
73+
74+
for.end7: ; preds = %for.cond
75+
ret void
76+
}
77+
78+
declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture, i8* nocapture readonly, i64, i32, i1) #1
79+

‎polly/test/ScopInfo/memset.ll

+69
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
; RUN: opt %loadPolly -polly-allow-differing-element-types -polly-scops -analyze < %s | FileCheck %s
2+
; RUN: opt %loadPolly -S -polly-allow-differing-element-types -polly-codegen < %s | FileCheck --check-prefix=IR %s
3+
;
4+
; CHECK: Arrays {
5+
; CHECK-NEXT: i8 MemRef_A[*]; // Element size 1
6+
; CHECK-NEXT: }
7+
; CHECK: Statements {
8+
; CHECK-NEXT: Stmt_for_body3
9+
; CHECK-NEXT: Domain :=
10+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] : 0 <= i0 <= 1023 and 0 <= i1 <= 1023 };
11+
; CHECK-NEXT: Schedule :=
12+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] -> [i0, i1] };
13+
; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
14+
; CHECK-NEXT: { Stmt_for_body3[i0, i1] -> MemRef_A[o0] : 0 <= o0 <= 186 };
15+
;
16+
; IR: %[[r1:[a-zA-Z0-9]*]] = bitcast i32* %A to i8*
17+
;
18+
; IR: polly.stmt.for.body3:
19+
; IR: call void @llvm.memset.p0i8.i64(i8* %[[r1]], i8 36, i64 187, i32 4, i1 false)
20+
;
21+
; #include <string.h>
22+
;
23+
; void jd(int *A) {
24+
; for (int i = 0; i < 1024; i++)
25+
; for (int j = 0; j < 1024; j++)
26+
; memset(A, '$', 187);
27+
; }
28+
;
29+
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
30+
31+
define void @jd(i32* noalias %A) {
32+
entry:
33+
br label %for.cond
34+
35+
for.cond: ; preds = %for.inc4, %entry
36+
%i.0 = phi i32 [ 0, %entry ], [ %inc5, %for.inc4 ]
37+
%exitcond1 = icmp ne i32 %i.0, 1024
38+
br i1 %exitcond1, label %for.body, label %for.end6
39+
40+
for.body: ; preds = %for.cond
41+
br label %for.cond1
42+
43+
for.cond1: ; preds = %for.inc, %for.body
44+
%j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
45+
%exitcond = icmp ne i32 %j.0, 1024
46+
br i1 %exitcond, label %for.body3, label %for.end
47+
48+
for.body3: ; preds = %for.cond1
49+
%tmp = bitcast i32* %A to i8*
50+
call void @llvm.memset.p0i8.i64(i8* %tmp, i8 36, i64 187, i32 4, i1 false)
51+
br label %for.inc
52+
53+
for.inc: ; preds = %for.body3
54+
%inc = add nsw i32 %j.0, 1
55+
br label %for.cond1
56+
57+
for.end: ; preds = %for.cond1
58+
br label %for.inc4
59+
60+
for.inc4: ; preds = %for.end
61+
%inc5 = add nsw i32 %i.0, 1
62+
br label %for.cond
63+
64+
for.end6: ; preds = %for.cond
65+
ret void
66+
}
67+
68+
declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) #1
69+

0 commit comments

Comments
 (0)
Please sign in to comment.