[Polly] Support ModRef function behaviour

[jdoerfert]

Summary

Check the ModRefBehaviour of functions in order to decide whether or
not a call instruction might be acceptable.

+ Test cases for each ModRef behaviour

[grosser]

Hey Johannes,

it is great you are pushing the limits of Polly further. Supporting memory modifying function calls is great.

Two questions:

• What is the reason no test cases are added? This is a new feature were it seems very valuable to have test cases. Did you encounter a certain problem when creating test cases? How did you test this code without test cases?

• It is not fully clear to me what kind of functions are now supported. Your commit message sounds to me as if the newly supported functions can only read/modify the data locations they directly point to? I had the impression they are not allowed to do something like:

void arrayoffset(float *A) {

A[10] = 10;

}

or

void arraycast(float *A) {

*((double*) A) = 10;

}

right? But the following is allowed:

void pointerdereference(float *A) {

*A = 10;

}

Now looking at the actual code it seems all three of them are theoretically allowed. Is this right?

It may be helpful to state this more clearly in the commit message possibly giving some examples and explaining that we model this as an access to the full and unbounded data space of this array. Similarly, a comment in the code about what is supported here may also help readability.

Also, for the arraycast test case, it would be useful to give some reasoning why your choice of WSize is still correct.

Tobias

lib/Analysis/TempScopInfo.cpp

290 ↗

(On Diff #13366)

Should we not verify this already in the ScopDetection?

295 ↗

(On Diff #13366)

Good that you choose MAY_WRITE here.

[jdoerfert]

1. There is no test case becuase I didn't have the time and idea how to write some. We need to check which alias analysis implementations actually annotate the functions with the "mod-ref-behaviour". I will create test cases once I know there this will go in afterwards.

2. The Scope is basically defined in http://llvm.org/docs/doxygen/html/classllvm_1_1AliasAnalysis.html#ae0276e687a2b2ddd7d0d549d98140f91 to which (without the anchor) I can add a link to the commit message. Basically everything C allows you to do with a pointer (here the argument) is allowed, thus read/write on the whole memory object underneath.

3. I will also address your comments.

lib/Analysis/TempScopInfo.cpp

290 ↗

(On Diff #13366)

Good point, will do.

[dpeixott]

As far as I know detailed mod-ref-behaviour is currently only returned in the case of intrinsic functions. These functions are defined with the appropriate values and tablegen generates some code to return the correct values. You could use an intrinsic function in your test (e.g. llvm.prefetch).

[jdoerfert]

Disabled read/access of pointer arguments but implemented the global readonly

[jdoerfert]

In D5227#7, @dpeixott wrote:

As far as I know detailed mod-ref-behaviour is currently only returned in the case of intrinsic functions. These functions are defined with the appropriate values and tablegen generates some code to return the correct values. You could use an intrinsic function in your test (e.g. llvm.prefetch).

Unfortunatly I cannot export the "onlyReadsArgumentPointees" of llvm.prefetch to IR... it gets overaproximated to "onlyReadsMemory" for now.

[dpeixott]

In D5227#10, @jdoerfert wrote:

In D5227#7, @dpeixott wrote:

As far as I know detailed mod-ref-behaviour is currently only returned in the case of intrinsic functions. These functions are defined with the appropriate values and tablegen generates some code to return the correct values. You could use an intrinsic function in your test (e.g. llvm.prefetch).

Unfortunatly I cannot export the "onlyReadsArgumentPointees" of llvm.prefetch to IR... it gets overaproximated to "onlyReadsMemory" for now.

You could try the llvm.gcread (OnlyReadsArgumentPointes) and llvm.gcwrite (OnlyAccessesArgumentPointers) if you want to generate a test case. There are also a number of target-specific intrinsics you could use (e.g. llvm.arm.neon.vld1 (OnlyReadsArgumentPointes) llvm.arm.neon.vst1 (OnlyAccessesArgumentPointers)). An easy way find them is to check include/llvm/IR/Intrinsics.gen in the build directory.

[dpeixott]

test/ScopInfo/mod_ref_read_pointers.ll

41

What is the extra #2 here? I don't see those attributes actually defined in the IR

[jdoerfert]

In D5227#11, @dpeixott wrote:

In D5227#10, @jdoerfert wrote:

In D5227#7, @dpeixott wrote:

As far as I know detailed mod-ref-behaviour is currently only returned in the case of intrinsic functions. These functions are defined with the appropriate values and tablegen generates some code to return the correct values. You could use an intrinsic function in your test (e.g. llvm.prefetch).

Unfortunatly I cannot export the "onlyReadsArgumentPointees" of llvm.prefetch to IR... it gets overaproximated to "onlyReadsMemory" for now.

You could try the llvm.gcread (OnlyReadsArgumentPointes) and llvm.gcwrite (OnlyAccessesArgumentPointers) if you want to generate a test case. There are also a number of target-specific intrinsics you could use (e.g. llvm.arm.neon.vld1 (OnlyReadsArgumentPointes) llvm.arm.neon.vst1 (OnlyAccessesArgumentPointers)). An easy way find them is to check include/llvm/IR/Intrinsics.gen in the build directory.

Same problem as for prefetch, they have the attibute only between the time they are created and written to IR. In LLVM-IR there is yet no onlyReadsArgumentPointees or onlyAccessesArgumentPointees. The first attribute gets lowered to onlyReads and the second one will be lost in LLVM-IR.
I talked to Hal about this and offered to help add the new attributes to the IR, maybe I should ping him again.

[hfinkel]

• Original Message -----

From: "Johannes Doerfert" <[e-mail]>
To: [e-mail], [e-mail], [e-mail], [e-mail],
[e-mail]
Cc: [e-mail]
Sent: Wednesday, September 10, 2014 1:32:32 PM
Subject: Re: [PATCH] [Polly] Support ModRef function behaviour

In D5227#11, @dpeixott wrote:

In D5227#10, @jdoerfert wrote:

In D5227#7, @dpeixott wrote:

As far as I know detailed mod-ref-behaviour is currently only
returned in the case of intrinsic functions. These functions are
defined with the appropriate values and tablegen generates some
code to return the correct values. You could use an intrinsic
function in your test (e.g. llvm.prefetch).

Unfortunatly I cannot export the "onlyReadsArgumentPointees" of
llvm.prefetch to IR... it gets overaproximated to
"onlyReadsMemory" for now.

You could try the llvm.gcread (OnlyReadsArgumentPointes) and
llvm.gcwrite (OnlyAccessesArgumentPointers) if you want to
generate a test case. There are also a number of target-specific
intrinsics you could use (e.g. llvm.arm.neon.vld1
(OnlyReadsArgumentPointes) llvm.arm.neon.vst1
(OnlyAccessesArgumentPointers)). An easy way find them is to
check include/llvm/IR/Intrinsics.gen in the build directory.

Same problem as for prefetch, they have the attibute only between the
time they are created and written to IR. In LLVM-IR there is yet no
onlyReadsArgumentPointees or onlyAccessesArgumentPointees. The first
attribute gets lowered to onlyReads and the second one will be lost
in LLVM-IR.
I talked to Hal about this and offered to help add the new attributes
to the IR, maybe I should ping him again.

Sure, but I don't understand your statement. You can get at this information at the IR level by using ModRefBehavior getModRefBehavior(ImmutableCallSite CS) or ModRefBehavior getModRefBehavior(const Function *F) functions from AliasAnalysis. BasicAA does understand the properties of these intrinsics.

-Hal

http://reviews.llvm.org/D5227

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[jdoerfert]

Added test cases for all ModRef behaviours (Thanks to David & Hal)

[grosser]

Hi Johannes,

this change has been reviewed by David and Hal. Could you update me with the latest status? Does this need review, comments, ...? Is this ready to commit.

[jdoerfert]

This patch is 1.5 years old. I guess a rebase will need some time and then I can tell more.

[jdoerfert]

Rebased

[etherzhhb]

include/polly/ScopInfo.h

330–331

This change can be pushed directly

include/polly/Support/ScopHelper.h

78

A little bit weird, I think CallInst is too different from the other instruction above. Could we not mix CallInst with the other MemAccInst?

192

This is very confusing as a CallInst can have multiple pointer operands if the call read/write the location of multiples pointer arguments

[jdoerfert]

include/polly/ScopInfo.h

330–331

We try not to introduce unused methodes, thus I would like to push it with a user.

include/polly/Support/ScopHelper.h

78

Could we not mix CallInst with the other MemAccInst?

If we do not want to duplicate all methodes that take a MemAccInst, I guess we cannot.

A little bit weird, I think CallInst is too different from the other instruction above.

I would say the step from MemIntrinsic to CallInst is not that big.

192

But that "problem" is already present for MemIntrinsics. Some have 2 pointer operands but we allow only access to one of them through this interface. One has to cast it to a MemTransferInst to access the other.

[etherzhhb]

Is there a test to demonstrate "global reads" CallInsts that read all arrays?

include/polly/ScopInfo.h

330–331

ok

include/polly/Support/ScopHelper.h

78

If we do not want to duplicate all methodes that take a MemAccInst, I guess we cannot.

If there is no better solution, I think this change is ok

192

Ok, we can figure out a better solution for this (if there is any) later.

[etherzhhb]

I think there is no major issue, and this patch had been review by several people. It should be ready to push

[Meinersbur]

lib/Analysis/ScopDetection.cpp

476

The same approach as for FMRB_OnlyReadsMemory could be taken here, but with "GlobalWrites", also known as Clobbers.

lib/Analysis/ScopInfo.cpp

3979

What happens if there are other multi-dimensional accesses to the same array exist?

4308

Can't we iterate over all ScopArrayInfo's of type MK_Array instead of introducing a new list ArrayBasePointers?

test/ScopInfo/mod_ref_access_pointee_arguments.ll

7–17

I think we want to go to the CHECK-NEXT style.

[jdoerfert]

I guess this patch is close to landing. I wait for Michaels reply though.

I also discussed some extended use today with Philip Pfaffe from KIT, but I will start an email thread for that one.

lib/Analysis/ScopDetection.cpp

476

Yes, that is a good remark. I would like to push that only when we have more infrastructure/heuristics in-place that can determine if we should exit early. As a start we could "not count" all loops that contain a UnknownModRefBehaviour call in their body. This way the current heuristic would kick in if the loop is trivially sequential. Do you agree we can move forward on this in a follow up patch?

lib/Analysis/ScopInfo.cpp

3979

This is also a really good point! Thanks! I will add a test case and add code to the ScopDetection that will prevent us to delinearize a base pointer that is used in such a call (The same problem is actually present for MemIntrinsics, thus I will push the check and another test prior to this one). Later we can lift that restriction and make the access we create here multidimensional. Again I would like to do that in a follow-up patch if you agree.

4308

I tried and I failed to do that. The reason is the late creation of the ScopArrayInfo objects. At that point in time we do no have access to the ScopInfo, the "addArrayAccess" method and a couple of other things. I do agree it would be nicer, though I also see a benefit in keeping the creation of the SCoP in the ScopInfo pass. Is it OK to keep it like this for now? [Assuming you don't have a good way to call/emulate addArrayAccess after the ScopArrayInfo objects have been created. If this assumption is wrong I can change the patch immediately.]]

test/ScopInfo/mod_ref_access_pointee_arguments.ll

7–17

I ported the test case. My bad. I will change them.

[jdoerfert]

lib/Analysis/ScopInfo.cpp

3979

Forget the part in the parenthesis, that was not true.

[jdoerfert]

FIX problem with mixed multidim + unknown accesses + use CHECK-NEXT in all tests

[Meinersbur]

LGTM

[Meinersbur]

lib/Analysis/ScopDetection.cpp

476

Having another though about it, I don't know whether it would be useful at all. Such a clobber would inhibit all transformations from before and after the call.

[jdoerfert]

lib/Analysis/ScopDetection.cpp

476

It would basically be an optimization barrier. Nevertheless it might be useful at some later point (e.g., local arrays cannot be changed by such a call if they are not escaping or arguments). Let's see when if we want to impleemnt that.

include/polly/ScopInfo.h

public:
   /// where the result of the PHI node is stored and later loaded from as well
   /// as a second one where the incoming values of the PHI nodes are stored
   /// into and reloaded when the PHI is executed. As both memories use the
   /// original PHI node as virtual base pointer, we have this additional
   /// attribute to distinguish the PHI node specific array modeling from the
   /// normal scalar array modeling.
   bool isPHIKind() const { return Kind == MK_PHI; };
 
+  /// @brief Is this array info modeling an array?
+  bool isArrayKind() const { return Kind == MK_Array; };
+
   /// @brief Dump a readable representation to stderr.
   void dump() const;
 
   /// @brief Print a readable representation to @p OS.
   ///
   /// @param SizeAsPwAff Print the size as isl_pw_aff
   void print(raw_ostream &OS, bool SizeAsPwAff = false) const;
 
class ScopInfo : public RegionPass {
   LoopInfo *LI;
 
   /// @biref Valid Regions for Scop
   ScopDetection *SD;
 
   /// @brief The ScalarEvolution to help building Scop.
   ScalarEvolution *SE;
 
+  /// @brief Set of instructions that might read any memory location.
+  SmallVector<Instruction *, 16> GlobalReads;
+
+  /// @brief Set of all accessed array base pointers.
+  SmallSetVector<Value *, 16> ArrayBasePointers;
+
   // The Scop
   std::unique_ptr<Scop> scop;
 
   // Clear the context.
   void clear();
 
   // Build the SCoP for Region @p R.
   void buildScop(Region &R, AssumptionCache &AC);
class ScopInfo : public RegionPass {
   /// @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 Try to build a MemoryAccess for a call instruction.
+  ///
+  /// @param Inst       The call 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 buildAccessCallInst(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.

include/polly/Support/ScopHelper.h

 /// 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,
-/// 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:
+/// a MemIntrinsic instance (memset, memmove, memcpy), a CallInst instance 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) {}
+  /* implicit */ MemAccInst(llvm::CallInst *CI) : I(CI) {}
   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) ||
-           llvm::isa<llvm::MemIntrinsic>(V);
+           llvm::isa<llvm::CallInst>(V) || llvm::isa<llvm::MemIntrinsic>(V);
   }
   static bool isa(const llvm::Value *V) {
     return llvm::isa<llvm::LoadInst>(V) || llvm::isa<llvm::StoreInst>(V) ||
-           llvm::isa<llvm::MemIntrinsic>(V);
+           llvm::isa<llvm::CallInst>(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::MemIntrinsic &MI) {
     I = &MI;
     return *this;
   }
   MemAccInst &operator=(llvm::MemIntrinsic *MI) {
     I = MI;
     return *this;
   }
+  MemAccInst &operator=(llvm::CallInst &CI) {
+    I = &CI;
+    return *this;
+  }
+  MemAccInst &operator=(llvm::CallInst *CI) {
+    I = CI;
+    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(); }
public:
 
   llvm::Value *getValueOperand() const {
     if (isLoad())
       return asLoad();
     if (isStore())
       return asStore()->getValueOperand();
     if (isMemIntrinsic())
       return nullptr;
+    if (isCallInst())
+      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();
+    if (isCallInst())
+      return nullptr;
     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();
+    if (isCallInst())
+      return 0;
     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();
+    if (isCallInst())
+      return false;
     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();
+    if (isCallInst())
+      return true;
     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;
+    if (isCallInst())
+      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();
+    if (isCallInst())
+      return true;
     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 isCallInst() const { return I && llvm::isa<llvm::CallInst>(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::CallInst *asCallInst() const { return llvm::cast<llvm::CallInst>(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);

lib/Analysis/ScopDetection.cpp

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);
+    if (isValidIntrinsicInst(*II, Context))
+      return true;
 
   Function *CalledFunction = CI.getCalledFunction();
 
   // Indirect calls are not supported.
   if (CalledFunction == 0)
     return false;
 
+  switch (AA->getModRefBehavior(CalledFunction)) {
+  case llvm::FMRB_UnknownModRefBehavior:
+    return false;
+  case llvm::FMRB_DoesNotAccessMemory:
+  case llvm::FMRB_OnlyReadsMemory:
+    return true;
+  case llvm::FMRB_OnlyReadsArgumentPointees:
+  case llvm::FMRB_OnlyAccessesArgumentPointees:
+    for (const auto &Arg : CI.arg_operands()) {
+      if (!Arg->getType()->isPointerTy())
+        continue;
+
+      // Bail if a pointer argument has a base address not known to
+      // ScalarEvolution. Note that a zero pointer is acceptable.
+      auto *ArgSCEV = SE->getSCEVAtScope(Arg, LI->getLoopFor(CI.getParent()));
+      if (ArgSCEV->isZero())
+        continue;
+      if (!isa<SCEVUnknown>(SE->getPointerBase(ArgSCEV)))
+        return false;
+    }
+    return true;
+  }
+
   return false;
 }
 
 bool ScopDetection::isValidIntrinsicInst(IntrinsicInst &II,
                                          DetectionContext &Context) const {
   if (isIgnoredIntrinsic(&II))
     return true;
 

lib/Analysis/ScopInfo.cpp

bool ScopInfo::buildAccessMemIntrinsic(
   SrcAccFunc = SE->getMinusSCEV(SrcAccFunc, SrcPtrSCEV);
   addArrayAccess(Inst, MemoryAccess::READ, SrcPtrSCEV->getValue(),
                  IntegerType::getInt8Ty(SrcPtrVal->getContext()), false,
                  {SrcAccFunc, LengthVal}, {}, Inst.getValueOperand());
 
   return true;
 }
 
+bool ScopInfo::buildAccessCallInst(
+    MemAccInst Inst, Loop *L, Region *R,
+    const ScopDetection::BoxedLoopsSetTy *BoxedLoops,
+    const InvariantLoadsSetTy &ScopRIL) {
+  if (!Inst.isCallInst())
+    return false;
+
+  auto &CI = *Inst.asCallInst();
+  if (isIgnoredIntrinsic(&CI))
+    return true;
+
+  bool ReadOnly = false;
+  auto *AF = SE->getConstant(IntegerType::getInt64Ty(CI.getContext()), 0);
+  auto *CalledFunction = CI.getCalledFunction();
+  switch (AA->getModRefBehavior(CalledFunction)) {
+  case llvm::FMRB_UnknownModRefBehavior:
+    llvm_unreachable("Unknown mod ref behaviour cannot be represented.");
+  case llvm::FMRB_DoesNotAccessMemory:
+    return true;
+  case llvm::FMRB_OnlyReadsMemory:
+    GlobalReads.push_back(&CI);
+    return true;
+  case llvm::FMRB_OnlyReadsArgumentPointees:
+    ReadOnly = true;
+  // Fall through
+  case llvm::FMRB_OnlyAccessesArgumentPointees:
+    auto AccType = ReadOnly ? MemoryAccess::READ : MemoryAccess::MAY_WRITE;
+    for (const auto &Arg : CI.arg_operands()) {
+      if (!Arg->getType()->isPointerTy())
+        continue;
+
+      auto *ArgSCEV = SE->getSCEVAtScope(Arg, L);
+      if (ArgSCEV->isZero())
+        continue;
+
+      auto *ArgBasePtr = cast<SCEVUnknown>(SE->getPointerBase(ArgSCEV));
+      addArrayAccess(Inst, AccType, ArgBasePtr->getValue(),
+                     ArgBasePtr->getType(), false, {AF}, {}, &CI);
+    }
+    return true;
+  }
+
+  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 *ElementType = Val->getType();
   enum MemoryAccess::AccessType Type =

 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 (buildAccessCallInst(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);
 }

 }
 
 void ScopInfo::addArrayAccess(MemAccInst MemAccInst,
                               MemoryAccess::AccessType AccType,
                               Value *BaseAddress, Type *ElementType,
                               bool IsAffine, ArrayRef<const SCEV *> Subscripts,
                               ArrayRef<const SCEV *> Sizes,
                               Value *AccessValue) {
+  ArrayBasePointers.insert(BaseAddress);
   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());
 
void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {
   // nodes that are at this point not part of the region will be.
   // To handle these PHI nodes later we will now model their operands as scalar
   // accesses. Note that we do not model anything in the exit block if we have
   // an exiting block in the region, as there will not be any splitting later.
   if (!R.getExitingBlock())
     buildAccessFunctions(R, *R.getExit(), *SD->getInsnToMemAccMap(&R), nullptr,
                          /* IsExitBlock */ true);
 
+  // Create memory accesses for global reads since all arrays are now known.
+  auto *AF = SE->getConstant(IntegerType::getInt64Ty(SE->getContext()), 0);
+  for (auto *GlobalRead : GlobalReads)
+    for (auto *BP : ArrayBasePointers)
+      addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
+                     BP->getType()->getPointerElementType(), false, {AF}, {},
+                     GlobalRead);
+
   scop->init(*AA, AC, *SD, *DT, *LI);
 }
 
 void ScopInfo::print(raw_ostream &OS, const Module *) const {
   if (!scop) {
     OS << "Invalid Scop!\n";
     return;
   }

lib/CodeGen/IRBuilder.cpp

void ScopAnnotator::annotate(Instruction *Inst) {
   // TODO: Use the ScopArrayInfo once available here.
   if (!AliasScopeDomain)
     return;
 
   auto MemInst = MemAccInst::dyn_cast(Inst);
   if (!MemInst)
     return;
 
-  auto *PtrSCEV = SE->getSCEV(MemInst.getPointerOperand());
+  auto *Ptr = MemInst.getPointerOperand();
+  if (!Ptr)
+    return;
+
+  auto *PtrSCEV = SE->getSCEV(Ptr);
   auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
   auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
 
   if (!SU)
     return;
 
   auto *BasePtr = SU->getValue();
 

test/ScopDetect/mod_ref_read_pointer.ll

+; RUN: opt %loadPolly -basicaa -polly-detect -analyze < %s | FileCheck %s
+;
+; CHECK: Valid Region for Scop: for.cond => for.end
+;
+;    #pragma readonly
+;    int func(int *A);
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i + 2] = func(A);
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+declare i32 @func(i32* %A) #1
+
+define void @jd(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %call = call i32 @func(i32* %A)
+  %tmp = add nsw i64 %indvars.iv, 2
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %tmp
+  store i32 %call, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+attributes #1 = { nounwind readonly }

test/ScopInfo/mod_ref_access_pointee_arguments.ll

+; RUN: opt %loadPolly -basicaa -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-codegen -disable-output < %s
+;
+; Verify that we model the may-write access of the prefetch intrinsic
+; correctly, thus that A is accessed by it but B is not.
+;
+; CHECK: Stmt_for_body
+; CHECK:   Domain :=
+; CHECK:       { Stmt_for_body[i0] : 0 <= i0 <= 1023 };
+; CHECK:   Schedule :=
+; CHECK:       { Stmt_for_body[i0] -> [i0] };
+; CHECK:   MayWriteAccess := [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_A[o0] };
+; CHECK:   ReadAccess := [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_B[i0] };
+; CHECK:   MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_A[i0] };
+;
+;    void jd(int *restirct A, int *restrict B) {
+;      for (int i = 0; i < 1024; i++) {
+;        @llvm.prefetch(A);
+;        A[i] = B[i];
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* noalias %A, i32* noalias %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %bc = bitcast i32* %arrayidx to i8*
+  call void @llvm.prefetch(i8* %bc, i32 1, i32 1, i32 1)
+  %tmp = load i32, i32* %arrayidx2
+  store i32 %tmp, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @llvm.prefetch(i8*, i32, i32, i32)

test/ScopInfo/mod_ref_read_pointee_arguments.ll

+; RUN: opt %loadPolly -basicaa -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-codegen -disable-output < %s
+;
+; Verify that we model the read access of the gcread intrinsic
+; correctly, thus that A is read by it but B is not.
+;
+; CHECK: Stmt_for_body
+; CHECK:   Domain :=
+; CHECK:       { Stmt_for_body[i0] : 0 <= i0 <= 1023 };
+; CHECK:   Schedule :=
+; CHECK:       { Stmt_for_body[i0] -> [i0] };
+; CHECK:   ReadAccess := [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_A[o0] };
+; CHECK:   MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_dummyloc[0] };
+; CHECK:   ReadAccess := [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_B[i0] };
+; CHECK:   MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_A[i0] };
+;
+;    void jd(int *restirct A, int *restrict B) {
+;      char **dummyloc;
+;      for (int i = 0; i < 1024; i++) {
+;        char *dummy = @llvm.gcread(A, nullptr);
+;        *dummyloc = dummy;
+;        A[i] = B[i];
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* noalias %A, i32* noalias %B) gc "dummy" {
+entry:
+  %dummyloc = alloca i8*
+  br label %entry.split
+
+entry.split:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry.split
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry.split ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %bc = bitcast i32* %arrayidx to i8*
+  %dummy = call i8* @llvm.gcread(i8* %bc, i8** null)
+  store i8* %dummy, i8** %dummyloc, align 4
+  %tmp = load i32, i32* %arrayidx2
+  store i32 %tmp, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare i8* @llvm.gcread(i8*, i8**)

test/ScopInfo/mod_ref_read_pointer.ll

+; RUN: opt %loadPolly -basicaa -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-codegen -disable-output < %s
+;
+; Check that we assume the call to func has a read on the whole A array.
+;
+; CHECK: Stmt_for_body
+; CHECK:   Domain :=
+; CHECK:       { Stmt_for_body[i0] : 0 <= i0 <= 1023 };
+; CHECK:   Schedule :=
+; CHECK:       { Stmt_for_body[i0] -> [i0] };
+; CHECK:   MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_A[2 + i0] };
+; CHECK:   ReadAccess :=  [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_A[o0] };
+;
+;    #pragma readonly
+;    int func(int *A);
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i + 2] = func(A);
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %call = call i32 @func(i32* %A) #2
+  %tmp = add nsw i64 %indvars.iv, 2
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %tmp
+  store i32 %call, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare i32 @func(i32*) #1
+
+attributes #1 = { nounwind readonly }

test/ScopInfo/mod_ref_read_pointers.ll

+; RUN: opt %loadPolly -basicaa -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -basicaa -polly-codegen -disable-output < %s
+;
+; Check that the call to func will "read" not only the A array but also the
+; B array. The reason is the readonly annotation of func.
+;
+; CHECK:     Stmt_for_body
+; CHECK:       Domain :=
+; CHECK:           { Stmt_for_body[i0] : 0 <= i0 <= 1023 };
+; CHECK:       Schedule :=
+; CHECK:           { Stmt_for_body[i0] -> [i0] };
+; CHECK:       ReadAccess :=  [Reduction Type: NONE]
+; CHECK:           { Stmt_for_body[i0] -> MemRef_B[i0] };
+; CHECK:       MustWriteAccess :=  [Reduction Type: NONE]
+; CHECK:           { Stmt_for_body[i0] -> MemRef_A[2 + i0] };
+; CHECK-DAG:   ReadAccess :=  [Reduction Type: NONE]
+; CHECK-DAG:       { Stmt_for_body[i0] -> MemRef_B[o0] };
+; CHECK-DAG:   ReadAccess :=  [Reduction Type: NONE]
+; CHECK-DAG:       { Stmt_for_body[i0] -> MemRef_A[o0] };
+;
+;    #pragma readonly
+;    int func(int *A);
+;
+;    void jd(int *restrict A, int *restrict B) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i + 2] = func(A) + B[i];
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* noalias %A, i32* noalias %B) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %call = call i32 @func(i32* %A)
+  %arrayidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %tmp = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %call, %tmp
+  %tmp2 = add nsw i64 %indvars.iv, 2
+  %arrayidx3 = getelementptr inbounds i32, i32* %A, i64 %tmp2
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare i32 @func(i32*) #1
+
+attributes #1 = { nounwind readonly }