[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

433

Should we not verify this already in the ScopDetection?

438

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

433

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 ↗

(On Diff #48639)

This change can be pushed directly

include/polly/Support/ScopHelper.h

78 ↗

(On Diff #48639)

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 ↗

(On Diff #48639)

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 ↗

(On Diff #48639)

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

include/polly/Support/ScopHelper.h

78 ↗

(On Diff #48639)

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 ↗

(On Diff #48639)

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 ↗

(On Diff #48639)

ok

include/polly/Support/ScopHelper.h

78 ↗

(On Diff #48639)

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 ↗

(On Diff #48639)

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

317

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

lib/Analysis/ScopInfo.cpp

1440

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

1451

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

8–18

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

317

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

1440

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.

1451

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

8–18

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

[jdoerfert]

lib/Analysis/ScopInfo.cpp

1440

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

317

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

317

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/TempScopInfo.h

 
 #include "polly/ScopDetection.h"
 
 #include "llvm/Analysis/RegionPass.h"
 #include "llvm/IR/Instructions.h"
 
 namespace llvm {
 class DataLayout;
+class IntrinsicInst;
 }
 
 using namespace llvm;
 
 namespace polly {
 
 extern bool PollyDelinearize;
 
class TempScopInfo : public FunctionPass {
   LoopBoundMapType LoopBounds;
 
   // And also Remember the constrains for BBs
   BBCondMapType BBConds;
 
   // Access function of statements (currently BasicBlocks) .
   AccFuncMapType AccFuncMap;
 
+  /// @brief All base addresses of arrays in this SCoP.
+  SmallPtrSet<Value *, 4> BaseAddresses;
+
   // Pre-created zero for the scalar accesses, with it we do not need create a
   // zero scev every time when we need it.
   const SCEV *ZeroOffset;
 
   // Mapping regions to the corresponding Scop in current function.
   TempScopMapType TempScops;
 
+  /// @brief Set of intstructions which may access __all__ memory locations.
+  ///
+  /// Elements in this set have unknown access behaviours we have to over
+  /// approximate. To do so we pretend all memory locations known in the SCoP
+  /// are accessed by the instruction. The access kind read/write is stored too.
+  using GlobalAccessInstruction = std::pair<Instruction *, IRAccess::TypeKind>;
+  SmallVector<GlobalAccessInstruction, 4> GlobalAccessInstructions;
+
   // Clear the context.
   void clear();
 
   /// @brief Build condition constrains to BBs in a valid Scop.
   ///
   /// @param BB           The BasicBlock to build condition constrains
   /// @param RegionEntry  The entry block of the Smallest Region that containing
   ///                     BB
class TempScopInfo : public FunctionPass {
   /// @param Inst The Load/Store instruction that access the memory
   /// @param L    The parent loop of the instruction
   /// @param R    The region on which we are going to build a TempScop
   ///
   /// @return     The IRAccess to describe the access function of the
   ///             instruction.
   IRAccess buildIRAccess(Instruction *Inst, Loop *L, Region *R);
 
-  /// @brief Build an instance of IRAccess if the call can access the memory.
+  /// @brief Build instances of IRAccess if the call can access the memory.
   ///
   /// @param CI   The call instruction that might access the memory
   /// @param L    The parent loop of the instruction
-  /// @param R    The region on which we are going to build a TempScop
   /// @param Accs The set of accesses in which we accumulate IRAccesses
-  void buildIRCallAccess(CallInst *CI, Loop *L, Region *R,
-                         AccFuncSetType &Accs);
+  void buildIRCallAccess(CallInst *CI, Loop *L, AccFuncSetType &Accs);
+
+  /// @brief Build instances of IRAccess if the intrinsic can access the memory.
+  ///
+  /// @param IT   The intrinsic call instruction that might access the memory
+  /// @param L    The parent loop of the instruction
+  /// @param Accs The set of accesses in which we accumulate IRAccesses
+  ///
+  /// @return True iff the intrinsic was handled here, false otherwise.
+  ///
+  /// @note If the intrinsic is not handled here it should be treated as a call.
+  bool buildIRIntrinsicAccess(IntrinsicInst *IT, Loop *L, AccFuncSetType &Accs);
+
+  /// @brief Build all IRAccesses representing global accesses.
+  ///
+  /// Global accesses are instructions which have effects we cannot model
+  /// precicely but is purely on the memory level. For these instructions
+  /// we create overaproximated accesses to __all__ arrays in this SCoP.
+  void buildGlobalAccesses();
 
   /// @brief Analyze and extract the cross-BB scalar dependences (or,
   ///        dataflow dependencies) of an instruction.
   ///
   /// @param Inst The instruction to be analyzed
   /// @param R    The SCoP region
   ///
   /// @return     True if the Instruction is used in other BB and a scalar write

lib/Analysis/ScopDetection.cpp

bool ScopDetection::isValidCallInst(CallInst &CI) const {
   Function *CalledFunction = CI.getCalledFunction();
 
   // Indirect calls are not supported.
   if (CalledFunction == 0)
     return false;
 
   // The access "function" for memory intrinsics.
   const SCEV *AF;
 
   // The closest loop surrounding the call instruction.
   Loop *L = LI->getLoopFor(CI.getParent());
 
   // Check if we can handle the intrinsic call.
   if (auto *IT = dyn_cast<IntrinsicInst>(&CI)) {
     switch (IT->getIntrinsicID()) {
     // Lifetime markers are supported/ignored.
     case llvm::Intrinsic::lifetime_start:
case llvm::Intrinsic::memset:
       return true;
 
     default:
       // Other intrinsics which may access the memory are not yet supported.
       break;
     }
   }
 
+  switch (AA->getModRefBehavior(CalledFunction)) {
+  case AliasAnalysis::DoesNotAccessMemory:
+  case AliasAnalysis::OnlyReadsMemory:
+    return true;
+  case AliasAnalysis::OnlyReadsArgumentPointees:
+  case AliasAnalysis::OnlyAccessesArgumentPointees:
+    for (const auto &ArgUse : CI.arg_operands()) {
+      Value *Arg = ArgUse.get();
+      if (!Arg->getType()->isPointerTy())
+        continue;
+
+      AF = SE->getSCEVAtScope(Arg, L);
+      // Bail if a pointer argument has a base address not known to
+      // ScalarEvolution. Note that a zero pointer is acceptable.
+      if (!AF->isZero() && !isa<SCEVUnknown>(SE->getPointerBase(AF)))
+        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;
 

lib/Analysis/ScopInfo.cpp

MemoryAccess::MemoryAccess(const IRAccess &Access, Instruction *AccInst,
 
   isl_ctx *Ctx = Statement->getIslCtx();
   BaseAddr = Access.getBase();
   BaseName = getIslCompatibleName("MemRef_", getBaseAddr(), "");
   isl_id *BaseAddrId = isl_id_alloc(Ctx, getBaseName().c_str(), nullptr);
 
   // Non affine accesses are either real memory accesses with access functions
   // we can not analyze or special instructions (e.g., memset intrinsics) which
-  // write and/or read memory. The former will be overaproximatied (e.g., we
+  // write and/or read memory. The former will be overaproximated (e.g., we
   // model the access to the whole array) while the later comes with bounds.
   // Since the overaproximated accesses might not write all array cells they
   // are marked as MAY_WRITE.
   if (!Access.isAffine()) {
     isl_set *LBSet, *UBSet, *Range;
     isl_local_space *LocalSpace;
     isl_space *Space;
     isl_pw_aff *IV;
void Scop::buildScop(TempScop &tempScop, const Region &CurRegion,
 
   if (!L)
     return;
 
   // Exiting a loop region.
   Scatter[loopDepth] = 0;
   NestLoops.pop_back();
   ++Scatter[loopDepth - 1];
 }
 
 //===----------------------------------------------------------------------===//
 ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
   ctx = isl_ctx_alloc();
   isl_options_set_on_error(ctx, ISL_ON_ERROR_ABORT);
 }
 
 ScopInfo::~ScopInfo() {
   clear();
   isl_ctx_free(ctx);
 }
 
 void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfo>();
   AU.addRequired<RegionInfoPass>();
   AU.addRequired<ScalarEvolution>();
   AU.addRequired<TempScopInfo>();
   AU.setPreservesAll();
 }

lib/Analysis/TempScopInfo.cpp

if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
     Type = IRAccess::MUST_WRITE;
   }
 
   const SCEV *AccessFunction = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
 
   assert(BasePointer && "Could not find base pointer");
+  BaseAddresses.insert(BasePointer->getValue());
+
   AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
   SmallVector<const SCEV *, 4> Subscripts, Sizes;
 
   MemAcc *Acc = InsnToMemAcc[Inst];
   if (PollyDelinearize && Acc)
     return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, true,
                     Acc->DelinearizedSubscripts, Acc->Shape->DelinearizedSizes);
 
   bool IsAffine = isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue());
   Subscripts.push_back(AccessFunction);
   if (!IsAffine && Type == IRAccess::MUST_WRITE)
     Type = IRAccess::MAY_WRITE;
 
   Sizes.push_back(SE->getConstant(ZeroOffset->getType(), Size));
   return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, IsAffine,
                   Subscripts, Sizes);
 }
 
-void TempScopInfo::buildIRCallAccess(CallInst *CI, Loop *L, Region *R,
-                                     AccFuncSetType &Accs) {
-  // Trivial calls can be ignored.
-  if (CI->doesNotAccessMemory())
+void TempScopInfo::buildGlobalAccesses() {
+  // Determine if we have read/write/both or no global accesses.
+  bool HasRead = false, HasWrite = false;
+  for (auto &GlobalAccessPair : GlobalAccessInstructions) {
+    if (GlobalAccessPair.second == IRAccess::READ)
+      HasRead = true;
+    else
+      HasWrite = true;
+  }
+
+  // If there are no global accesses in this SCoP we are done.
+  if (!HasRead && !HasWrite)
     return;
 
   SmallVector<const SCEV *, 4> Subscripts, Sizes;
+  SmallVector<IRAccess, 4> ReadAccesses, WriteAccesses;
 
-  const SCEVUnknown *WriteBasePtr = nullptr, *ReadBasePtr = nullptr;
-  const SCEV *Len = nullptr, *WriteLen = nullptr, *ReadLen = nullptr;
-  const SCEV *WriteSize = nullptr, *ReadSize = nullptr;
-  const SCEV *WriteAF = nullptr, *ReadAF = nullptr;
-  const SCEV *WriteUB = nullptr, *ReadUB = nullptr;
-  unsigned RSize, WSize;
+  // Create read/write IRAccesses for all base addresses in the SCoP.
+  for (Value *BaseAddr : BaseAddresses) {
+    if (HasRead)
+      ReadAccesses.push_back(IRAccess(IRAccess::READ, BaseAddr, ZeroOffset, 1,
+                                      /* isAffine? */ false, Subscripts,
+                                      Sizes));
+    if (HasWrite)
+      WriteAccesses.push_back(
+          IRAccess(IRAccess::MAY_WRITE, BaseAddr, ZeroOffset, 1,
+                   /* isAffine? */ false, Subscripts, Sizes));
+  }
+
+  // For each global access create read/write accesses based on the IRAccesses.
+  for (auto &GlobalAccessPair : GlobalAccessInstructions) {
+    Instruction *I = GlobalAccessPair.first;
+    BasicBlock *BB = I->getParent();
+    AccFuncSetType &Accs = AccFuncMap[BB];
+    if (GlobalAccessPair.second == IRAccess::READ)
+      for (const IRAccess &Acc : ReadAccesses)
+        Accs.push_back(std::make_pair(Acc, I));
+    else
+      for (const IRAccess &Acc : WriteAccesses)
+        Accs.push_back(std::make_pair(Acc, I));
+  }
 
-  // Handle memory intrinsics with well defined read and write effects.
-  if (auto *IT = dyn_cast<IntrinsicInst>(CI)) {
-    switch (IT->getIntrinsicID()) {
-    // Ignore misc intrinsics without any "real" memory effect for now.
-    case llvm::Intrinsic::lifetime_start:
-    case llvm::Intrinsic::lifetime_end:
-    case llvm::Intrinsic::invariant_start:
-    case llvm::Intrinsic::invariant_end:
-    case llvm::Intrinsic::var_annotation:
-    case llvm::Intrinsic::ptr_annotation:
-    case llvm::Intrinsic::annotation:
-    case llvm::Intrinsic::donothing:
-    case llvm::Intrinsic::assume:
-    case llvm::Intrinsic::expect:
-      return;
-    // Check for intrinsics with "real" memory effects.
-    case llvm::Intrinsic::memmove:
-    case llvm::Intrinsic::memcpy:
-      ReadAF = SE->getSCEVAtScope(IT->getOperand(1), L);
-      ReadBasePtr = dyn_cast<SCEVUnknown>(SE->getPointerBase(ReadAF));
-      assert(ReadBasePtr && "Could not find base pointer");
-      ReadAF = SE->getMinusSCEV(ReadAF, ReadBasePtr);
-      RSize =
-          TD->getTypeStoreSize(ReadBasePtr->getType()->getPointerElementType());
-      ReadSize = SE->getConstant(ZeroOffset->getType(), RSize);
+  // Reset the set of global accesses.
+  GlobalAccessInstructions.clear();
+}
+
+bool TempScopInfo::buildIRIntrinsicAccess(IntrinsicInst *IT, Loop *L,
+                                          AccFuncSetType &Accs) {
+
+  // First check if we treat this intrinsic special or as a general call.
+  // In the latter case we return false and are done.
+    return true;
+  case llvm::Intrinsic::memset:
+    break;
+  // All other intrinsics should be handled as regular call statements.
+  default:
+    return false;
+  }
+
+  const SCEVUnknown *WriteBasePtr = nullptr, *ReadBasePtr = nullptr;
+  const SCEV *Len = nullptr, *WriteLen = nullptr, *ReadLen = nullptr;
+  const SCEV *WriteSize = nullptr, *ReadSize = nullptr;
+  const SCEV *WriteAF = nullptr, *ReadAF = nullptr;
+  const SCEV *WriteUB = nullptr, *ReadUB = nullptr;
+  unsigned RSize, WSize;
+
+  SmallVector<const SCEV *, 4> Subscripts, Sizes;
+
+  // Handle memory intrinsics with well defined read and write effects.
+  switch (IT->getIntrinsicID()) {
+  case llvm::Intrinsic::memmove:
+  case llvm::Intrinsic::memcpy:
+    BaseAddresses.insert(ReadBasePtr->getValue());
 
-    // Fall through
-    case llvm::Intrinsic::memset:
-      WriteAF = SE->getSCEVAtScope(IT->getOperand(0), L);
-      WriteBasePtr = dyn_cast<SCEVUnknown>(SE->getPointerBase(WriteAF));
-      assert(WriteBasePtr && "Could not find base pointer");
-      WriteAF = SE->getMinusSCEV(WriteAF, WriteBasePtr);
+    BaseAddresses.insert(WriteBasePtr->getValue());
 
-      WSize = TD->getTypeStoreSize(
-          WriteBasePtr->getType()->getPointerElementType());
-      WriteSize = SE->getConstant(ZeroOffset->getType(), WSize);
+    WSize =
+        TD->getTypeStoreSize(WriteBasePtr->getType()->getPointerElementType());
 
-      Len = SE->getSCEVAtScope(IT->getOperand(2), L);
-      WriteLen =
-          SE->getAddExpr(Len, SE->getConstant(Len->getType(), WSize - 1));
-      WriteLen = SE->getUDivExpr(WriteLen, WriteSize);
-      WriteUB = SE->getAddExpr(WriteLen, WriteAF);
+    WriteLen = SE->getAddExpr(Len, SE->getConstant(Len->getType(), WSize - 1));
 
-      Accs.push_back(std::make_pair(
-          IRAccess(IRAccess::MUST_WRITE, WriteBasePtr->getValue(), WriteAF,
-                   WSize, false, Subscripts, Sizes, WriteAF, WriteUB),
-          CI));
+        IRAccess(IRAccess::MUST_WRITE, WriteBasePtr->getValue(), WriteAF, WSize,
+                 false, Subscripts, Sizes, WriteAF, WriteUB),
+        IT));
 
-      if (ReadBasePtr) {
-        ReadLen =
-            SE->getAddExpr(Len, SE->getConstant(Len->getType(), RSize - 1));
-        ReadLen = SE->getUDivExpr(ReadLen, ReadSize);
-        ReadUB = SE->getAddExpr(ReadLen, ReadAF);
+      ReadLen = SE->getAddExpr(Len, SE->getConstant(Len->getType(), RSize - 1));
 
-        Accs.push_back(std::make_pair(
-            IRAccess(IRAccess::READ, ReadBasePtr->getValue(), ReadAF, RSize,
-                     false, Subscripts, Sizes, ReadAF, ReadUB),
+          IT));
+    }
+
+    return true;
+  default:
+    IT->dump();
+    llvm_unreachable("Unhandled intrinsic call!");
+  }
+
+  return false;
+}
+
+void TempScopInfo::buildIRCallAccess(CallInst *CI, Loop *L,
+                                     AccFuncSetType &Accs) {
+  // Trivial calls can be ignored.
+  if (CI->doesNotAccessMemory())
+    return;
+
+  // Check intriniscis explicitly, some are treated special.
+  if (auto *IT = dyn_cast<IntrinsicInst>(CI))
+    if (buildIRIntrinsicAccess(IT, L, Accs))
+      return;
+
+  Function *CalledFunction = CI->getCalledFunction();
+  assert(CalledFunction && "Found indirect function call");
+
+  SmallVector<const SCEV *, 4> Subscripts, Sizes;
+  const SCEVUnknown *BasePtrSCEV;
+  const SCEV *AccessFunction;
+  bool OnlyReads;
+  Value *BasePtr;
+
+  OnlyReads = false;
+  switch (AA->getModRefBehavior(CalledFunction)) {
+  case AliasAnalysis::DoesNotAccessMemory:
+    return;
+  case AliasAnalysis::OnlyReadsArgumentPointees:
+    OnlyReads = true;
+  // Fall through
+  case AliasAnalysis::OnlyAccessesArgumentPointees:
+
+    // Iterate over all arguments and filter those with pointer type
+    for (const auto &ArgUse : CI->arg_operands()) {
+      Value *Arg = ArgUse.get();
+      if (!Arg->getType()->isPointerTy())
+        continue;
+
+      // Get the ScalarEvolution representation of the pointer.
+      AccessFunction = SE->getSCEVAtScope(Arg, L);
+
+      // Skip zero pointers as they can't be used to access any memory.
+      if (AccessFunction->isZero())
+        continue;
+
+      // Compute the actual base address and offset.
+      BasePtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
+      assert(BasePtr && "Could not find base pointer");
+      AccessFunction = SE->getMinusSCEV(AccessFunction, BasePtrSCEV);
+      BasePtr = BasePtrSCEV->getValue();
+      BaseAddresses.insert(BasePtr);
+
+      Accs.push_back(
+          std::make_pair(IRAccess(IRAccess::READ, BasePtr, AccessFunction, 1,
+                                  false, Subscripts, Sizes),
+                         CI));
+
+      if (!OnlyReads)
+        Accs.push_back(std::make_pair(IRAccess(IRAccess::MAY_WRITE, BasePtr,
+                                               AccessFunction, 1, false,
+                                               Subscripts, Sizes),
                                       CI));
-      }
+    return;
 
-      return;
-    default:
-      break;
-    }
-  }
+  case AliasAnalysis::OnlyReadsMemory:
+    // Remember the call for later when we know all arrays in the SCoP. Only
+    // then is it possible to overestimate the effect of this call.
+    GlobalAccessInstructions.push_back(std::make_pair(CI, IRAccess::READ));
 
   llvm_unreachable("Unknown call instruction, cannot model the effect!");
 }
 
 void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB) {
   AccFuncSetType Functions;
   Loop *L = LI->getLoopFor(&BB);
 
   for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
     Instruction *Inst = I;
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
       Functions.push_back(std::make_pair(buildIRAccess(Inst, L, &R), Inst));
 
     // Some call accesses and intrinsics might access the memory. If so we
     // build over approximated IRAccesses for them.
     if (CallInst *CI = dyn_cast<CallInst>(Inst))
-      buildIRCallAccess(CI, L, &R, Functions);
+      buildIRCallAccess(CI, L, Functions);
 
     if (!isa<StoreInst>(Inst) && buildScalarDependences(Inst, &R)) {
       // If the Instruction is used outside the statement, we need to build the
       // write access.
       SmallVector<const SCEV *, 4> Subscripts, Sizes;
       IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true,
                             Subscripts, Sizes);
+      BaseAddresses.insert(Inst);
       Functions.push_back(std::make_pair(ScalarAccess, Inst));
     }
   }
 
   if (Functions.empty())
     return;
 
   AccFuncSetType &Accs = AccFuncMap[&BB];
   Accs.insert(Accs.end(), Functions.begin(), Functions.end());
 }
 
 void TempScopInfo::buildLoopBounds(TempScop &Scop) {
   Region &R = Scop.getMaxRegion();
   unsigned MaxLoopDepth = 0;
 
   for (auto const &BB : R.blocks()) {
     Loop *L = LI->getLoopFor(BB);
 
     if (!L || !R.contains(L))
       continue;

 TempScop *TempScopInfo::buildTempScop(Region &R) {
   TempScop *TScop = new TempScop(R, LoopBounds, BBConds, AccFuncMap);
 
   for (const auto &BB : R.blocks()) {
     buildAccessFunctions(R, *BB);
     buildCondition(BB, R.getEntry());
   }
 
+  // After all basic blocks are traversed we can build global accesses.
+  buildGlobalAccesses();
+
   buildLoopBounds(*TScop);
 
   return TScop;
 }
 
 TempScop *TempScopInfo::getTempScop(const Region *R) const {
   TempScopMapType::const_iterator at = TempScops.find(R);
   return at == TempScops.end() ? 0 : at->second;

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* %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
+;
+; Verify that we model the read and 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] : i0 >= 0 and i0 <= 1023 };
+; CHECK:   Scattering :=
+; CHECK:       { Stmt_for_body[i0] -> scattering[0, i0, 0] };
+; CHECK:   ReadAccess := [Reduction Type: NONE]
+; CHECK:       { Stmt_for_body[i0] -> MemRef_A[o0] };
+; 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* %A, i64 %indvars.iv
+  %arrayidx2 = getelementptr inbounds 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* %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
+;
+; 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] : i0 >= 0 and i0 <= 1023 };
+; CHECK:   Scattering :=
+; CHECK:       { Stmt_for_body[i0] -> scattering[0, i0, 0] };
+; 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* %A, i64 %indvars.iv
+  %arrayidx2 = getelementptr inbounds 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* %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
+;
+; Check that we assume the call to func has a read on the whole A array.
+; TODO: Use range analysis metadata!
+;
+; CHECK: Stmt_for_body
+; CHECK:   Domain :=
+; CHECK:       { Stmt_for_body[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:   Scattering :=
+; CHECK:       { Stmt_for_body[i0] -> scattering[0, i0, 0] };
+; 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* %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
+;
+; 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] : i0 >= 0 and i0 <= 1023 };
+; CHECK:       Scattering :=
+; CHECK:           { Stmt_for_body[i0] -> scattering[0, i0, 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[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) #2
+  %arrayidx = getelementptr inbounds i32* %B, i64 %indvars.iv
+  %tmp = load i32* %arrayidx, align 4
+  %add = add nsw i32 %call, %tmp
+  %tmp2 = add nsw i64 %indvars.iv, 2
+  %arrayidx3 = getelementptr inbounds 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 }