Page MenuHomePhabricator

[Polly] Support ModRef function behaviour
ClosedPublic

Authored by jdoerfert on Sep 6 2014, 3:35 AM.

Details

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

Diff Detail

Repository
rL LLVM

Event Timeline

jdoerfert updated this revision to Diff 13366.Sep 6 2014, 3:35 AM
jdoerfert retitled this revision from to [Polly] Support ModRef function behaviour.
jdoerfert updated this object.
jdoerfert edited the test plan for this revision. (Show Details)
jdoerfert added reviewers: grosser, sebpop, simbuerg.
jdoerfert added subscribers: Restricted Project, Unknown Object (MLST).
grosser edited edge metadata.Sep 7 2014, 11:48 PM

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 added a comment.EditedSep 8 2014, 2:24 AM
  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.
  1. 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.
  1. I will also address your comments.
lib/Analysis/TempScopInfo.cpp
290 ↗(On Diff #13366)

Good point, will do.

dpeixott edited edge metadata.Sep 8 2014, 2:19 PM

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 updated this revision to Diff 13542.Sep 10 2014, 7:26 AM
jdoerfert edited edge metadata.

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

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.

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 added inline comments.Sep 10 2014, 10:55 AM
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

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.

  • Original Message -----

From: "Johannes Doerfert" <doerfert@cs.uni-saarland.de>
To: doerfert@cs.uni-saarland.de, sebpop@gmail.com, simbuerg@fim.uni-passau.de, dpeixott@codeaurora.org,
tobias@grosser.es
Cc: llvm-commits@cs.uiuc.edu
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
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

jdoerfert updated this revision to Diff 13558.Sep 10 2014, 1:57 PM

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

jdoerfert updated this object.Sep 10 2014, 1:58 PM

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.

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

etherzhhb requested changes to this revision.Feb 22 2016, 7:18 AM
etherzhhb edited edge metadata.
etherzhhb added inline comments.
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

This revision now requires changes to proceed.Feb 22 2016, 7:18 AM
jdoerfert added inline comments.Feb 22 2016, 11:21 AM
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.

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 accepted this revision.Feb 22 2016, 2:50 PM
etherzhhb edited edge metadata.

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

This revision is now accepted and ready to land.Feb 22 2016, 2:50 PM
Meinersbur added inline comments.
lib/Analysis/ScopDetection.cpp
476 ↗(On Diff #48639)

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.

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 ↗(On Diff #48639)

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 added inline comments.Feb 23 2016, 12:19 PM
lib/Analysis/ScopInfo.cpp
3979 ↗(On Diff #48639)

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

jdoerfert updated this revision to Diff 48843.Feb 23 2016, 12:24 PM
jdoerfert edited edge metadata.

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

Meinersbur accepted this revision.Feb 24 2016, 7:55 AM
Meinersbur added a reviewer: Meinersbur.

LGTM

Meinersbur added inline comments.Feb 24 2016, 9:43 AM
lib/Analysis/ScopDetection.cpp
476 ↗(On Diff #48843)

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 added inline comments.Feb 24 2016, 12:50 PM
lib/Analysis/ScopDetection.cpp
476 ↗(On Diff #48843)

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.

This revision was automatically updated to reflect the committed changes.