[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

Should we not verify this already in the ScopDetection?

295

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

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

40 ↗

(On Diff #13542)

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

3979 ↗

(On Diff #48639)

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

4308 ↗

(On Diff #48639)

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 ↗

(On Diff #48639)

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

3979 ↗

(On Diff #48639)

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 ↗

(On Diff #48639)

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 ↗

(On Diff #48639)

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

[jdoerfert]

lib/Analysis/ScopInfo.cpp

3979 ↗

(On Diff #48639)

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

class ScopDetection : public FunctionPass {
   ///
   /// @return True if R is a Scop, false otherwise.
   bool isValidRegion(Region &R) const;
 
   /// @brief Check if a call instruction can be part of a Scop.
   ///
   /// @param CI The call instruction to check.
   /// @return True if the call instruction is valid, false otherwise.
-  static bool isValidCallInst(CallInst &CI);
+  bool isValidCallInst(CallInst &CI) const;
 
   /// @brief Check if a value is invariant in the region Reg.
   ///
   /// @param Val Value to check for invariance.
   /// @param Reg The region to consider for the invariance of Val.
   ///
   /// @return True if the value represented by Val is invariant in the region
   ///         identified by Reg.

lib/Analysis/ScopDetection.cpp

bool ScopDetection::isValidCFG(BasicBlock &BB,
   // Allow perfectly nested conditions.
   Region *R = RI->getRegionFor(&BB);
   if (R->getEntry() != &BB)
     return invalid<ReportCondition>(Context, /*Assert=*/true, &BB);
 
   return true;
 }
 
-bool ScopDetection::isValidCallInst(CallInst &CI) {
+bool ScopDetection::isValidCallInst(CallInst &CI) const {
   if (CI.doesNotReturn())
     return false;
 
   if (CI.doesNotAccessMemory())
     return true;
 
   Function *CalledFunction = CI.getCalledFunction();
 
   // Indirect calls are not supported.
   if (CalledFunction == 0)
     return false;
 
   // Check if we can handle the intrinsic call.
   if (auto *IT = dyn_cast<IntrinsicInst>(&CI)) {
     switch (IT->getIntrinsicID()) {
     // Basic mathematical intrinsics are supported.
     case llvm::Intrinsic::sqrt:
     case llvm::Intrinsic::powi:
     case llvm::Intrinsic::sin:
     case llvm::Intrinsic::cos:
     case llvm::Intrinsic::pow:
     case llvm::Intrinsic::exp:
     case llvm::Intrinsic::exp2:
if (auto *IT = dyn_cast<IntrinsicInst>(&CI)) {
     case llvm::Intrinsic::memcpy:
       return true;
     default:
       // Other intrinsics are not supported.
       break;
     }
   }
 
+  switch (AA->getModRefBehavior(CalledFunction)) {
+  case AliasAnalysis::DoesNotAccessMemory:
+  case AliasAnalysis::OnlyReadsArgumentPointees:
+  case AliasAnalysis::OnlyAccessesArgumentPointees:
+    return true;
+  // TODO Handle the case everything is read.
+  case AliasAnalysis::OnlyReadsMemory:
+    break;
+  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/TempScopInfo.cpp

case llvm::Intrinsic::memset:
       }
 
       return;
     default:
       break;
     }
   }
 
+  bool OnlyReadsPointees = false;
+  Function *CalledFunction = CI->getCalledFunction();
+  switch (AA->getModRefBehavior(CalledFunction)) {
+  case AliasAnalysis::DoesNotAccessMemory:
+    return;
+  case AliasAnalysis::OnlyReadsArgumentPointees:
+    OnlyReadsPointees = true;
+  // Fall through
+  case AliasAnalysis::OnlyAccessesArgumentPointees:
+    for (const auto &ArgUse : CI->arg_operands()) {
+      Value *Arg = ArgUse.get();
+      if (!Arg->getType()->isPointerTy())
+        continue;
+
+      ReadAF = SE->getSCEVAtScope(Arg, 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());
+      Accs.push_back(std::make_pair(
+          IRAccess(IRAccess::READ, ReadBasePtr->getValue(), ReadAF, RSize,
+                   false, Subscripts, Sizes, ReadAF, ReadUB),
+          CI));
+
+      if (OnlyReadsPointees)
+        continue;
+
+      WriteAF = SE->getSCEVAtScope(Arg, L);
+      WriteBasePtr = dyn_cast<SCEVUnknown>(SE->getPointerBase(WriteAF));
+      assert(WriteBasePtr && "Could not find base pointer");
+      WriteAF = SE->getMinusSCEV(WriteAF, WriteBasePtr);
+      WSize = TD->getTypeStoreSize(
+          WriteBasePtr->getType()->getPointerElementType());
+      Accs.push_back(std::make_pair(
+          IRAccess(IRAccess::MAY_WRITE, WriteBasePtr->getValue(), WriteAF,
+                   WSize, false, Subscripts, Sizes, WriteAF, WriteUB),
+          CI));
+    }
+  // TODO Handle the case everything is read.
+  case AliasAnalysis::OnlyReadsMemory:
+  default:
+    break;
+  }
+
   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) {