Alina Sbirlea via llvm-dev
2017-Oct-10 20:13 UTC
[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)
On Tue, Oct 10, 2017 at 1:05 PM, Hal Finkel <hfinkel at anl.gov> wrote:> > On 10/10/2017 02:49 PM, Alina Sbirlea wrote: > > Sigh >> I should have taken the time to give a better example. >> The must-alias part is irrelevant to an example (it only requires >> read-onlyness) >> >> You said "LICM doesn't move calls, so we'd never really care about >> must-alias for promotion". I was just pointing out other things move calls >> any may want to know. >> >> If you want an example where the must-alias part would matter: >> >> *a = something >> foo(a) >> b = *a >> >> If foo mustalias a (and only a) not only can you move foo with a, you can >> actually clone foo here, change it to be pass-by-value, and promote the >> argument inside of it (if you wanted to). >> >> So you can use this info to, for example, do interprocedural promotion. >> >> >>> Are we instead looking to set a MRI_Must bit, disjunct of MRI_Mod, and >>> test for MRI_Ref&MRI_Must or MRI_Mod&MRI_Must? >>> >> >> Yes. >> > > I didn't mean to pick on the example, sorry if that's how it came through. > > Since the consensus is to expose the Must info in ModRefInfo, I'm trying > to figure out how to add it in a way that makes sense to me. > The way I see ModRefInfo is designed right now is to lower the lattice to > NoModRef as fast as possible (start with ModRef as top, get to NoModRef as > bottom). The implementation is based on having either Mod or Ref and > masking out everything else. > Introducing a Must bit, means setting it occasionally (since May is > conservative) and then preserving it, so the opposite: start lattice at > bottom, set to top. > > What I was trying, that *somewhat* made sense: > enum ModRefInfo { > MRI_NoModRef = 0, > MRI_Ref = 1, > MRI_Mod = 2, > MRI_ModRef = MRI_Ref | MRI_Mod, > MRI_Must = 4, > MRI_MustRef = MRI_Ref | MRI_Must, > MRI_MustMod = MRI_Mod | MRI_Must, > MRI_MustModRef = MRI_ModRef | MRI_Must > }; > // + shift values in FunctionModRefLocation to 8, 16, 32. > > Recursive masking of MRI_Ref/MRI_Mod would get replaced by > MRI_MustRef/MRI_MustMod. > But the top of the lattice is still MRI_ModRef. > While the implementation details *may* be ok to resolve, there are calls > checking for equality to MRI_Ref or MRI_Mod (not &), so adding the > occasional Must bit seems bad. > > > I don't see this as a major problem. Please feel free to fix these places > by replacing the equality checks with mask checks. >Ok, thank you!> > > -Hal > > So I guess my question is, what's the right approach here? I feel like I'm > not on the right path. > > >> In getModRefInfo(CS, Loc), the MRI_Must bit would then be set if >>> doesAccessArgPointees and ArgAlias == MustAlias for all Args, which seems >>> correct. >>> >> >> >> alias == MustAlias for Loc, not for all args. >> (IE It it returns a singular result about Loc, not a result about all >> args) >> >> To get the set answer for all args, we'd have to query further. >> > > Yes, that's what I meant. In getModRefInfo(CS, Loc) there is a loop over > all args, it checks alias() for each one. > > > -- > Hal Finkel > Lead, Compiler Technology and Programming Languages > Leadership Computing Facility > Argonne National Laboratory > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171010/445331af/attachment-0001.html>
Alina Sbirlea via llvm-dev
2017-Nov-22 23:05 UTC
[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)
Re-opening this discussion, to get some feedback.
Adding alias info is under review in https://reviews.llvm.org/D38862.
An issue that came up, that was bugging me before is how to reason of what
is top/bottom of the lattice, and what is the default to test against.
So talking offline is Sanjoy, we reached a slightly different conclusion
which makes more sense to me.
Current patch has:
enum ModRefInfo {
MRI_NoModRef = 0,
MRI_Ref = 1,
MRI_Mod = 2,
MRI_ModRef = MRI_Ref | MRI_Mod,
MRI_Must = 4,
MRI_MustRef = MRI_Ref | MRI_Must,
MRI_MustMod = MRI_Mod | MRI_Must,
MRI_MustModRef = MRI_ModRef | MRI_Must
};
Proposed change:
enum ModRefInfo {
MRI_Must = 0,
MRI_MustRef = 1,
MRI_MustMod = 2,
MRI_MustModRef = MRI_MustRef | MRI_MustMod
MRI_NoModRef = 4,
MRI_Ref = MRI_NoModRef | MRI_MustRef , /* Same semantics as right now,
i.e. MayRef */
MRI_Mod = MRI_NoModRef | MRI_MustMod , /* Same semantics as right now,
i.e. MayMod */
MRI_ModRef = MRI_Ref | MRI_Mod, /* Same semantics as right now, i.e. May
Ref or Mod */
};
With this change:
- the same approach of "set a bit to 0 when additional info is
available"
will apply to the Must bit, as it does to Ref and Mod.
- we could keep the same checks with MRI_NoModRef
- MRI_ModRef remains the most conservative answer (top).
- finding MRI_Must gives more info than MRI_NoModRef, so it makes sense to
be bottom.
- MRI_NoModRef means "no mod or ref, and no must alias".
The only obvious change I see right now will be to to add " |
MRI_NoModRef",
essentially setting the default to "not must alias".
For GlobalsModRef, we can also always set MRI_NoModRef bit.
I may be missing details here, happy to elaborate.
Happy Thanksgiving!
Alina
On Tue, Oct 10, 2017 at 1:13 PM, Alina Sbirlea <alina.sbirlea at
gmail.com>
wrote:
>
> On Tue, Oct 10, 2017 at 1:05 PM, Hal Finkel <hfinkel at anl.gov>
wrote:
>
>>
>> On 10/10/2017 02:49 PM, Alina Sbirlea wrote:
>>
>> Sigh
>>> I should have taken the time to give a better example.
>>> The must-alias part is irrelevant to an example (it only requires
>>> read-onlyness)
>>>
>>> You said "LICM doesn't move calls, so we'd never
really care about
>>> must-alias for promotion". I was just pointing out other
things move calls
>>> any may want to know.
>>>
>>> If you want an example where the must-alias part would matter:
>>>
>>> *a = something
>>> foo(a)
>>> b = *a
>>>
>>> If foo mustalias a (and only a) not only can you move foo with a,
you
>>> can actually clone foo here, change it to be pass-by-value, and
promote the
>>> argument inside of it (if you wanted to).
>>>
>>> So you can use this info to, for example, do interprocedural
promotion.
>>>
>>>
>>>> Are we instead looking to set a MRI_Must bit, disjunct of
MRI_Mod, and
>>>> test for MRI_Ref&MRI_Must or MRI_Mod&MRI_Must?
>>>>
>>>
>>> Yes.
>>>
>>
>> I didn't mean to pick on the example, sorry if that's how it
came through.
>>
>> Since the consensus is to expose the Must info in ModRefInfo, I'm
trying
>> to figure out how to add it in a way that makes sense to me.
>> The way I see ModRefInfo is designed right now is to lower the lattice
to
>> NoModRef as fast as possible (start with ModRef as top, get to NoModRef
as
>> bottom). The implementation is based on having either Mod or Ref and
>> masking out everything else.
>> Introducing a Must bit, means setting it occasionally (since May is
>> conservative) and then preserving it, so the opposite: start lattice at
>> bottom, set to top.
>>
>> What I was trying, that *somewhat* made sense:
>> enum ModRefInfo {
>> MRI_NoModRef = 0,
>> MRI_Ref = 1,
>> MRI_Mod = 2,
>> MRI_ModRef = MRI_Ref | MRI_Mod,
>> MRI_Must = 4,
>> MRI_MustRef = MRI_Ref | MRI_Must,
>> MRI_MustMod = MRI_Mod | MRI_Must,
>> MRI_MustModRef = MRI_ModRef | MRI_Must
>> };
>> // + shift values in FunctionModRefLocation to 8, 16, 32.
>>
>> Recursive masking of MRI_Ref/MRI_Mod would get replaced by
>> MRI_MustRef/MRI_MustMod.
>> But the top of the lattice is still MRI_ModRef.
>> While the implementation details *may* be ok to resolve, there are
calls
>> checking for equality to MRI_Ref or MRI_Mod (not &), so adding the
>> occasional Must bit seems bad.
>>
>>
>> I don't see this as a major problem. Please feel free to fix these
places
>> by replacing the equality checks with mask checks.
>>
>
> Ok, thank you!
>
>>
>>
>> -Hal
>>
>> So I guess my question is, what's the right approach here? I feel
like
>> I'm not on the right path.
>>
>>
>>> In getModRefInfo(CS, Loc), the MRI_Must bit would then be set if
>>>> doesAccessArgPointees and ArgAlias == MustAlias for all Args,
which seems
>>>> correct.
>>>>
>>>
>>>
>>> alias == MustAlias for Loc, not for all args.
>>> (IE It it returns a singular result about Loc, not a result about
all
>>> args)
>>>
>>> To get the set answer for all args, we'd have to query further.
>>>
>>
>> Yes, that's what I meant. In getModRefInfo(CS, Loc) there is a loop
over
>> all args, it checks alias() for each one.
>>
>>
>> --
>> Hal Finkel
>> Lead, Compiler Technology and Programming Languages
>> Leadership Computing Facility
>> Argonne National Laboratory
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171122/e745bf87/attachment.html>
Nuno Lopes via llvm-dev
2017-Nov-23 11:52 UTC
[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)
Hi Alina,
My only concern with that design is that it seems that you can go from
MustModRef into Ref or Mod, and that is not true.
Assuming my understanding of what ModRef & friends mean is correct, this is
the lattice (where green are the official names, and black are my comments):
AFAIU, MustModRef means that an operation *must* read and write to the given
location. Moreover, it *must* alias with that allocation.
Therefore, we cannot go from MustModRef into MayRef, because MayRef implies
there’s no write; there’s at most a read.
What confused me first is that Mod has 2 “mays”: may read, and if it does it may
be to the given location.
While MustMod has 2 “musts”: must read, and it must read exactly from the given
location.
Your lattice doesn’t have the intermediate values (1 may + 1 must, like
MustModMayAlias), but that would increase significantly the size of the lattice.
I don’t know which clients would benefit of that precision increase (if any) –
didn’t think about that.
Nuno
From: Alina Sbirlea
Sent: 22 November 2017 23:06
To: Hal Finkel <hfinkel at anl.gov>; Daniel Berlin <dberlin at
dberlin.org>; George Burgess IV <george.burgess.iv at gmail.com>;
llvm-dev <llvm-dev at lists.llvm.org>; Sanjoy Das <sanjoy at
playingwithpointers.com>
Subject: Re: [llvm-dev] Expose aliasing information in getModRefInfo (or
viceversa?)
Re-opening this discussion, to get some feedback.
Adding alias info is under review in https://reviews.llvm.org/D38862.
An issue that came up, that was bugging me before is how to reason of what is
top/bottom of the lattice, and what is the default to test against.
So talking offline is Sanjoy, we reached a slightly different conclusion which
makes more sense to me.
Current patch has:
enum ModRefInfo {
MRI_NoModRef = 0,
MRI_Ref = 1,
MRI_Mod = 2,
MRI_ModRef = MRI_Ref | MRI_Mod,
MRI_Must = 4,
MRI_MustRef = MRI_Ref | MRI_Must,
MRI_MustMod = MRI_Mod | MRI_Must,
MRI_MustModRef = MRI_ModRef | MRI_Must
};
Proposed change:
enum ModRefInfo {
MRI_Must = 0,
MRI_MustRef = 1,
MRI_MustMod = 2,
MRI_MustModRef = MRI_MustRef | MRI_MustMod
MRI_NoModRef = 4,
MRI_Ref = MRI_NoModRef | MRI_MustRef , /* Same semantics as right now, i.e.
MayRef */
MRI_Mod = MRI_NoModRef | MRI_MustMod , /* Same semantics as right now, i.e.
MayMod */
MRI_ModRef = MRI_Ref | MRI_Mod, /* Same semantics as right now, i.e. May Ref
or Mod */
};
With this change:
- the same approach of "set a bit to 0 when additional info is
available" will apply to the Must bit, as it does to Ref and Mod.
- we could keep the same checks with MRI_NoModRef
- MRI_ModRef remains the most conservative answer (top).
- finding MRI_Must gives more info than MRI_NoModRef, so it makes sense to be
bottom.
- MRI_NoModRef means "no mod or ref, and no must alias".
The only obvious change I see right now will be to to add " |
MRI_NoModRef", essentially setting the default to "not must
alias".
For GlobalsModRef, we can also always set MRI_NoModRef bit.
I may be missing details here, happy to elaborate.
Happy Thanksgiving!
Alina
On Tue, Oct 10, 2017 at 1:13 PM, Alina Sbirlea <alina.sbirlea at gmail.com
<mailto:alina.sbirlea at gmail.com> > wrote:
On Tue, Oct 10, 2017 at 1:05 PM, Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov> > wrote:
On 10/10/2017 02:49 PM, Alina Sbirlea wrote:
Sigh
I should have taken the time to give a better example.
The must-alias part is irrelevant to an example (it only requires read-onlyness)
You said "LICM doesn't move calls, so we'd never really care about
must-alias for promotion". I was just pointing out other things move calls
any may want to know.
If you want an example where the must-alias part would matter:
*a = something
foo(a)
b = *a
If foo mustalias a (and only a) not only can you move foo with a, you can
actually clone foo here, change it to be pass-by-value, and promote the argument
inside of it (if you wanted to).
So you can use this info to, for example, do interprocedural promotion.
Are we instead looking to set a MRI_Must bit, disjunct of MRI_Mod, and test for
MRI_Ref&MRI_Must or MRI_Mod&MRI_Must?
Yes.
I didn't mean to pick on the example, sorry if that's how it came
through.
Since the consensus is to expose the Must info in ModRefInfo, I'm trying to
figure out how to add it in a way that makes sense to me.
The way I see ModRefInfo is designed right now is to lower the lattice to
NoModRef as fast as possible (start with ModRef as top, get to NoModRef as
bottom). The implementation is based on having either Mod or Ref and masking out
everything else.
Introducing a Must bit, means setting it occasionally (since May is
conservative) and then preserving it, so the opposite: start lattice at bottom,
set to top.
What I was trying, that *somewhat* made sense:
enum ModRefInfo {
MRI_NoModRef = 0,
MRI_Ref = 1,
MRI_Mod = 2,
MRI_ModRef = MRI_Ref | MRI_Mod,
MRI_Must = 4,
MRI_MustRef = MRI_Ref | MRI_Must,
MRI_MustMod = MRI_Mod | MRI_Must,
MRI_MustModRef = MRI_ModRef | MRI_Must
};
// + shift values in FunctionModRefLocation to 8, 16, 32.
Recursive masking of MRI_Ref/MRI_Mod would get replaced by
MRI_MustRef/MRI_MustMod.
But the top of the lattice is still MRI_ModRef.
While the implementation details *may* be ok to resolve, there are calls
checking for equality to MRI_Ref or MRI_Mod (not &), so adding the
occasional Must bit seems bad.
I don't see this as a major problem. Please feel free to fix these places by
replacing the equality checks with mask checks.
Ok, thank you!
-Hal
So I guess my question is, what's the right approach here? I feel like
I'm not on the right path.
In getModRefInfo(CS, Loc), the MRI_Must bit would then be set if
doesAccessArgPointees and ArgAlias == MustAlias for all Args, which seems
correct.
alias == MustAlias for Loc, not for all args.
(IE It it returns a singular result about Loc, not a result about all args)
To get the set answer for all args, we'd have to query further.
Yes, that's what I meant. In getModRefInfo(CS, Loc) there is a loop over all
args, it checks alias() for each one.
--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171123/9a87bae0/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 19652 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171123/9a87bae0/attachment.jpg>
Alina Sbirlea via llvm-dev
2017-Nov-28 23:55 UTC
[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)
> In your new proposal, doing & on the result of getModRef() may yieldunexpected results. Agreed. I made the change I proposed locally, and, while it simplifies some cases, it makes other bit-wise operations look unintuitive.> Maybe we should just hide all that in inline functions or something andmake it an enum class Noted, and looking into this option. Hoping a couple of static functions (e.g. mods(), refs(), isMust(), addMust()) will be more intuitive than the bit-wise ops. Should also make it easier to understand and prove. Alina On Tue, Nov 28, 2017 at 8:42 AM, Daniel Berlin <dberlin at dberlin.org> wrote:> Maybe we should just hide all that in inline functions or something and > make it an enum class > > > On Tue, Nov 28, 2017, 7:28 AM Nuno Lopes <nunoplopes at sapo.pt> wrote: > >> Just to be clear: I don’t have any particular concerns regarding your >> patch. I just did a cursory review and apart of the minor comment I left in >> Phabricator it looks good. AFAIU your goal is to pick a good combination >> of values in the enum to make the implementation simpler & correct. I don >> ’t know enough about this specific code to help with this respect. >> >> >> >> My concern was with the users of getModReg(). In your new proposal, >> doing & on the result of getModRef() may yield unexpected results. >> >> E.g., “getModRef() & MRI_MustMod != 0” doesn’t imply that the >> instruction will write because the result might have been MRI_Mod (>> NoModRef | MustMod). >> >> As long as this fact is properly document, I’m good :) (btw, thanks for >> fixing the documentation of the old MRI_* values; it was really misleading). >> >> >> >> Nuno >> >> >> >> P.S.: BTW, not sure I mentioned this to you at the LLVM conf, but my >> interest in this area is because I’ve built a little tool to >> automatically verify correctness of alias analyses (think of Alive for >> AA/ModRef). Since I’m not an expert in this area, I need to ask a lot of >> questions to make sure I’m proving the right thing :) The script >> reported a few bugs in BasicAA (mostly for GEPs wo/ inbounds); need to >> report these.. >> >> >> >> >> >> *From:* Alina Sbirlea >> *Sent:* 27 November 2017 20:02 >> *To:* Nuno Lopes <nunoplopes at sapo.pt> >> *Cc:* Hal Finkel <hfinkel at anl.gov>; Daniel Berlin <dberlin at dberlin.org>; >> George Burgess IV <george.burgess.iv at gmail.com>; Sanjoy Das < >> sanjoy at playingwithpointers.com> >> >> >> *Subject:* Re: [llvm-dev] Expose aliasing information in getModRefInfo >> (or viceversa?) >> >> >> >> Hi Nuno, >> >> >> >> Thanks for taking the time to look over this! >> >> >> >> Here's the reasoning I reached after going over this again. >> >> >> >> > "you can go from MustModRef into Ref or Mod, and that is not true.". >> >> That's correct. While the initial thought I had was "Found may" + "Found >> must", then we should return "May", that's not the right, we should return >> "Must". Here's why: >> >> Right now, if one AA returns Ref and another Mod, then we do logical & >> and return NoModRef, because one AA analysis removed the Mod bit because it >> was sure there was no Mod, so it returned Ref, while the other was sure >> there was no Ref and returned Mod. So correct answer is NoModRef. >> >> With the Must bit, the logic should be the same. If one analysis removed >> the "May" bit, then it's sure there is a Must alias there. Now, by Must >> alias, I mean all aliases were MustAlias and NoAlias, and no May or >> PartialAlias was found. >> >> > Therefore, we cannot go from MustModRef into MayRef, because MayRef >> implies there’s no write; there’s at most a read. >> >> Exactly, from MustModRef, we should have no reason to go into MayRef. >> Logical & here will give MustRef. This case should be when one analysis >> finds "I'm sure there is a must alias, not sure if I can remove either mod >> or ref so will conservatively say both", and the second says "I only know >> there's no Mod". >> >> >> >> I've been talking here about different AA results. I'll reiterate that >> within the same analysis, the Must bit should only be cleared if all >> aliases found MustAlias, otherwise that bit should be conservatively kept >> set. >> >> >> >> > What confused me first is that Mod has 2 “mays”: may read, and if it >> does it may be to the given location. >> >> > While MustMod has 2 “musts”: must read, and it must read exactly from >> the given location. >> >> > >> >> > Your lattice doesn’t have the intermediate values (1 may + 1 must, >> like MustModMayAlias), but that would increase significantly the size of >> the lattice. I don’t know which clients would benefit of that precision >> increase (if any) – didn’t think about that. >> >> >> >> True, such info would increase the size of the lattice a lot. Going into >> MustMod is meant as the certainty you mentioned: it must read and it must >> be exactly that location. Anything less than that will conservatively be >> Mod. >> >> >> >> Does this make sense? >> >> >> >> Thanks, >> >> Alina >> >> >> >> On Thu, Nov 23, 2017 at 3:47 AM, Nuno Lopes <nunoplopes at sapo.pt> wrote: >> >> Hi Alina, >> >> >> >> My only concern with that design is that it seems that you can go from >> MustModRef into Ref or Mod, and that is not true. >> >> Assuming my understanding of what ModRef & friends mean is correct, this >> is the lattice (where green are the official names, and black are my >> comments): >> >> >> >> >> >> >> >> >> >> >> >> >> >> AFAIU, MustModRef means that an operation **must** read and write to the >> given location. Moreover, it **must** alias with that allocation. >> >> Therefore, we cannot go from MustModRef into MayRef, because MayRef >> implies there’s no write; there’s at most a read. >> >> >> >> What confused me first is that Mod has 2 “mays”: may read, and if it >> does it may be to the given location. >> >> While MustMod has 2 “musts”: must read, and it must read exactly from >> the given location. >> >> >> >> Your lattice doesn’t have the intermediate values (1 may + 1 must, like >> MustModMayAlias), but that would increase significantly the size of the >> lattice. I don’t know which clients would benefit of that precision >> increase (if any) – didn’t think about that. >> >> >> >> Nuno >> >> >> >> >> >> *From:* Alina Sbirlea >> *Sent:* 22 November 2017 23:06 >> *To:* Hal Finkel <hfinkel at anl.gov>; Daniel Berlin <dberlin at dberlin.org>; >> George Burgess IV <george.burgess.iv at gmail.com>; llvm-dev < >> llvm-dev at lists.llvm.org>; Sanjoy Das <sanjoy at playingwithpointers.com> >> *Subject:* Re: [llvm-dev] Expose aliasing information in getModRefInfo >> (or viceversa?) >> >> >> >> Re-opening this discussion, to get some feedback. >> >> >> >> Adding alias info is under review in https://reviews.llvm.org/D38862. >> >> >> >> An issue that came up, that was bugging me before is how to reason of >> what is top/bottom of the lattice, and what is the default to test against. >> >> So talking offline is Sanjoy, we reached a slightly different conclusion >> which makes more sense to me. >> >> >> >> Current patch has: >> >> enum ModRefInfo { >> MRI_NoModRef = 0, >> MRI_Ref = 1, >> MRI_Mod = 2, >> MRI_ModRef = MRI_Ref | MRI_Mod, >> MRI_Must = 4, >> >> MRI_MustRef = MRI_Ref | MRI_Must, >> >> MRI_MustMod = MRI_Mod | MRI_Must, >> >> MRI_MustModRef = MRI_ModRef | MRI_Must >> }; >> >> >> >> Proposed change: >> >> enum ModRefInfo { >> >> MRI_Must = 0, >> >> MRI_MustRef = 1, >> >> MRI_MustMod = 2, >> >> MRI_MustModRef = MRI_MustRef | MRI_MustMod >> >> MRI_NoModRef = 4, >> MRI_Ref = MRI_NoModRef | MRI_MustRef , /* Same semantics as right now, >> i.e. MayRef */ >> >> MRI_Mod = MRI_NoModRef | MRI_MustMod , /* Same semantics as right >> now, i.e. MayMod */ >> >> MRI_ModRef = MRI_Ref | MRI_Mod, /* Same semantics as right now, >> i.e. May Ref or Mod */ >> >> }; >> >> >> >> With this change: >> >> - the same approach of "set a bit to 0 when additional info is available" >> will apply to the Must bit, as it does to Ref and Mod. >> >> - we could keep the same checks with MRI_NoModRef >> >> - MRI_ModRef remains the most conservative answer (top). >> >> - finding MRI_Must gives more info than MRI_NoModRef, so it makes sense >> to be bottom. >> >> - MRI_NoModRef means "no mod or ref, and no must alias". >> >> >> >> The only obvious change I see right now will be to to add " >> | MRI_NoModRef", essentially setting the default to "not must alias". >> >> For GlobalsModRef, we can also always set MRI_NoModRef bit. >> >> >> >> I may be missing details here, happy to elaborate. >> >> >> >> Happy Thanksgiving! >> >> >> >> Alina >> >> >> >> >> >> >> >> On Tue, Oct 10, 2017 at 1:13 PM, Alina Sbirlea <alina.sbirlea at gmail.com> >> wrote: >> >> >> >> On Tue, Oct 10, 2017 at 1:05 PM, Hal Finkel <hfinkel at anl.gov> wrote: >> >> >> >> On 10/10/2017 02:49 PM, Alina Sbirlea wrote: >> >> Sigh >> >> I should have taken the time to give a better example. >> >> The must-alias part is irrelevant to an example (it only requires >> read-onlyness) >> >> >> >> You said "LICM doesn't move calls, so we'd never really care about >> must-alias for promotion". I was just pointing out other things move calls >> any may want to know. >> >> >> >> If you want an example where the must-alias part would matter: >> >> >> >> *a = something >> >> foo(a) >> >> b = *a >> >> >> >> If foo mustalias a (and only a) not only can you move foo with a, you can >> actually clone foo here, change it to be pass-by-value, and promote the >> argument inside of it (if you wanted to). >> >> >> >> So you can use this info to, for example, do interprocedural promotion. >> >> >> >> >> >> Are we instead looking to set a MRI_Must bit, disjunct of MRI_Mod, and >> test for MRI_Ref&MRI_Must or MRI_Mod&MRI_Must? >> >> >> >> Yes. >> >> >> >> I didn't mean to pick on the example, sorry if that's how it came through. >> >> >> >> Since the consensus is to expose the Must info in ModRefInfo, I'm trying >> to figure out how to add it in a way that makes sense to me. >> >> The way I see ModRefInfo is designed right now is to lower the lattice to >> NoModRef as fast as possible (start with ModRef as top, get to NoModRef as >> bottom). The implementation is based on having either Mod or Ref and >> masking out everything else. >> >> Introducing a Must bit, means setting it occasionally (since May is >> conservative) and then preserving it, so the opposite: start lattice at >> bottom, set to top. >> >> >> >> What I was trying, that *somewhat* made sense: >> enum ModRefInfo { >> MRI_NoModRef = 0, >> MRI_Ref = 1, >> MRI_Mod = 2, >> MRI_ModRef = MRI_Ref | MRI_Mod, >> MRI_Must = 4, >> >> MRI_MustRef = MRI_Ref | MRI_Must, >> >> MRI_MustMod = MRI_Mod | MRI_Must, >> >> MRI_MustModRef = MRI_ModRef | MRI_Must >> }; >> >> // + shift values in FunctionModRefLocation to 8, 16, 32. >> >> >> >> Recursive masking of MRI_Ref/MRI_Mod would get replaced by >> MRI_MustRef/MRI_MustMod. >> >> But the top of the lattice is still MRI_ModRef. >> >> While the implementation details *may* be ok to resolve, there are calls >> checking for equality to MRI_Ref or MRI_Mod (not &), so adding the >> occasional Must bit seems bad. >> >> >> >> I don't see this as a major problem. Please feel free to fix these places >> by replacing the equality checks with mask checks. >> >> >> >> Ok, thank you! >> >> >> >> -Hal >> >> So I guess my question is, what's the right approach here? I feel like >> I'm not on the right path. >> >> >> >> >> >> In getModRefInfo(CS, Loc), the MRI_Must bit would then be set if >> doesAccessArgPointees and ArgAlias == MustAlias for all Args, which seems >> correct. >> >> >> >> >> >> alias == MustAlias for Loc, not for all args. >> >> (IE It it returns a singular result about Loc, not a result about all >> args) >> >> >> >> To get the set answer for all args, we'd have to query further. >> >> >> >> Yes, that's what I meant. In getModRefInfo(CS, Loc) there is a loop over >> all args, it checks alias() for each one. >> >> >> >> >> >> -- >> >> Hal Finkel >> >> Lead, Compiler Technology and Programming Languages >> >> Leadership Computing Facility >> >> Argonne National Laboratory >> >> >> >> >> >> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171128/5da0f38b/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: image003.jpg Type: image/jpeg Size: 19653 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171128/5da0f38b/attachment.jpg>
Alina Sbirlea via llvm-dev
2017-Dec-01 21:10 UTC
[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)
On Tue, Nov 28, 2017 at 3:55 PM, Alina Sbirlea <alina.sbirlea at gmail.com> wrote:> > In your new proposal, doing & on the result of getModRef() may yield > unexpected results. > Agreed. I made the change I proposed locally, and, while it > simplifies some cases, it makes other bit-wise operations look unintuitive. > > > Maybe we should just hide all that in inline functions or something and > make it an enum class > Noted, and looking into this option. Hoping a couple of static functions > (e.g. mods(), refs(), isMust(), addMust()) will be more intuitive than the > bit-wise ops. > Should also make it easier to understand and prove. >All, I put D40749 <https://reviews.llvm.org/D40749> up for review. It's only a NFC and adding the Must bit can be rebased on top of it. It does not do full replacement of bit-wise operations across all AAs, but I'm hoping to get some feedback on the approach, and I can update the patch to add the changes for the other AAs. Thanks, Alina> On Tue, Nov 28, 2017 at 8:42 AM, Daniel Berlin <dberlin at dberlin.org> > wrote: > >> Maybe we should just hide all that in inline functions or something and >> make it an enum class >> >> >> On Tue, Nov 28, 2017, 7:28 AM Nuno Lopes <nunoplopes at sapo.pt> wrote: >> >>> Just to be clear: I don’t have any particular concerns regarding your >>> patch. I just did a cursory review and apart of the minor comment I left in >>> Phabricator it looks good. AFAIU your goal is to pick a good combination >>> of values in the enum to make the implementation simpler & correct. I don >>> ’t know enough about this specific code to help with this respect. >>> >>> >>> >>> My concern was with the users of getModReg(). In your new proposal, >>> doing & on the result of getModRef() may yield unexpected results. >>> >>> E.g., “getModRef() & MRI_MustMod != 0” doesn’t imply that the >>> instruction will write because the result might have been MRI_Mod (>>> NoModRef | MustMod). >>> >>> As long as this fact is properly document, I’m good :) (btw, thanks >>> for fixing the documentation of the old MRI_* values; it was really >>> misleading). >>> >>> >>> >>> Nuno >>> >>> >>> >>> P.S.: BTW, not sure I mentioned this to you at the LLVM conf, but my >>> interest in this area is because I’ve built a little tool to >>> automatically verify correctness of alias analyses (think of Alive for >>> AA/ModRef). Since I’m not an expert in this area, I need to ask a lot >>> of questions to make sure I’m proving the right thing :) The script >>> reported a few bugs in BasicAA (mostly for GEPs wo/ inbounds); need to >>> report these.. >>> >>> >>> >>> >>> >>> *From:* Alina Sbirlea >>> *Sent:* 27 November 2017 20:02 >>> *To:* Nuno Lopes <nunoplopes at sapo.pt> >>> *Cc:* Hal Finkel <hfinkel at anl.gov>; Daniel Berlin <dberlin at dberlin.org>; >>> George Burgess IV <george.burgess.iv at gmail.com>; Sanjoy Das < >>> sanjoy at playingwithpointers.com> >>> >>> >>> *Subject:* Re: [llvm-dev] Expose aliasing information in getModRefInfo >>> (or viceversa?) >>> >>> >>> >>> Hi Nuno, >>> >>> >>> >>> Thanks for taking the time to look over this! >>> >>> >>> >>> Here's the reasoning I reached after going over this again. >>> >>> >>> >>> > "you can go from MustModRef into Ref or Mod, and that is not true.". >>> >>> That's correct. While the initial thought I had was "Found may" + "Found >>> must", then we should return "May", that's not the right, we should return >>> "Must". Here's why: >>> >>> Right now, if one AA returns Ref and another Mod, then we do logical & >>> and return NoModRef, because one AA analysis removed the Mod bit because it >>> was sure there was no Mod, so it returned Ref, while the other was sure >>> there was no Ref and returned Mod. So correct answer is NoModRef. >>> >>> With the Must bit, the logic should be the same. If one analysis removed >>> the "May" bit, then it's sure there is a Must alias there. Now, by Must >>> alias, I mean all aliases were MustAlias and NoAlias, and no May or >>> PartialAlias was found. >>> >>> > Therefore, we cannot go from MustModRef into MayRef, because MayRef >>> implies there’s no write; there’s at most a read. >>> >>> Exactly, from MustModRef, we should have no reason to go into MayRef. >>> Logical & here will give MustRef. This case should be when one analysis >>> finds "I'm sure there is a must alias, not sure if I can remove either mod >>> or ref so will conservatively say both", and the second says "I only know >>> there's no Mod". >>> >>> >>> >>> I've been talking here about different AA results. I'll reiterate that >>> within the same analysis, the Must bit should only be cleared if all >>> aliases found MustAlias, otherwise that bit should be conservatively kept >>> set. >>> >>> >>> >>> > What confused me first is that Mod has 2 “mays”: may read, and if it >>> does it may be to the given location. >>> >>> > While MustMod has 2 “musts”: must read, and it must read exactly from >>> the given location. >>> >>> > >>> >>> > Your lattice doesn’t have the intermediate values (1 may + 1 must, >>> like MustModMayAlias), but that would increase significantly the size of >>> the lattice. I don’t know which clients would benefit of that precision >>> increase (if any) – didn’t think about that. >>> >>> >>> >>> True, such info would increase the size of the lattice a lot. Going >>> into MustMod is meant as the certainty you mentioned: it must read and it >>> must be exactly that location. Anything less than that will conservatively >>> be Mod. >>> >>> >>> >>> Does this make sense? >>> >>> >>> >>> Thanks, >>> >>> Alina >>> >>> >>> >>> On Thu, Nov 23, 2017 at 3:47 AM, Nuno Lopes <nunoplopes at sapo.pt> wrote: >>> >>> Hi Alina, >>> >>> >>> >>> My only concern with that design is that it seems that you can go from >>> MustModRef into Ref or Mod, and that is not true. >>> >>> Assuming my understanding of what ModRef & friends mean is correct, this >>> is the lattice (where green are the official names, and black are my >>> comments): >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> AFAIU, MustModRef means that an operation **must** read and write to >>> the given location. Moreover, it **must** alias with that allocation. >>> >>> Therefore, we cannot go from MustModRef into MayRef, because MayRef >>> implies there’s no write; there’s at most a read. >>> >>> >>> >>> What confused me first is that Mod has 2 “mays”: may read, and if it >>> does it may be to the given location. >>> >>> While MustMod has 2 “musts”: must read, and it must read exactly from >>> the given location. >>> >>> >>> >>> Your lattice doesn’t have the intermediate values (1 may + 1 must, like >>> MustModMayAlias), but that would increase significantly the size of the >>> lattice. I don’t know which clients would benefit of that precision >>> increase (if any) – didn’t think about that. >>> >>> >>> >>> Nuno >>> >>> >>> >>> >>> >>> *From:* Alina Sbirlea >>> *Sent:* 22 November 2017 23:06 >>> *To:* Hal Finkel <hfinkel at anl.gov>; Daniel Berlin <dberlin at dberlin.org>; >>> George Burgess IV <george.burgess.iv at gmail.com>; llvm-dev < >>> llvm-dev at lists.llvm.org>; Sanjoy Das <sanjoy at playingwithpointers.com> >>> *Subject:* Re: [llvm-dev] Expose aliasing information in getModRefInfo >>> (or viceversa?) >>> >>> >>> >>> Re-opening this discussion, to get some feedback. >>> >>> >>> >>> Adding alias info is under review in https://reviews.llvm.org/D38862. >>> >>> >>> >>> An issue that came up, that was bugging me before is how to reason of >>> what is top/bottom of the lattice, and what is the default to test against. >>> >>> So talking offline is Sanjoy, we reached a slightly different conclusion >>> which makes more sense to me. >>> >>> >>> >>> Current patch has: >>> >>> enum ModRefInfo { >>> MRI_NoModRef = 0, >>> MRI_Ref = 1, >>> MRI_Mod = 2, >>> MRI_ModRef = MRI_Ref | MRI_Mod, >>> MRI_Must = 4, >>> >>> MRI_MustRef = MRI_Ref | MRI_Must, >>> >>> MRI_MustMod = MRI_Mod | MRI_Must, >>> >>> MRI_MustModRef = MRI_ModRef | MRI_Must >>> }; >>> >>> >>> >>> Proposed change: >>> >>> enum ModRefInfo { >>> >>> MRI_Must = 0, >>> >>> MRI_MustRef = 1, >>> >>> MRI_MustMod = 2, >>> >>> MRI_MustModRef = MRI_MustRef | MRI_MustMod >>> >>> MRI_NoModRef = 4, >>> MRI_Ref = MRI_NoModRef | MRI_MustRef , /* Same semantics as right >>> now, i.e. MayRef */ >>> >>> MRI_Mod = MRI_NoModRef | MRI_MustMod , /* Same semantics as right >>> now, i.e. MayMod */ >>> >>> MRI_ModRef = MRI_Ref | MRI_Mod, /* Same semantics as right now, >>> i.e. May Ref or Mod */ >>> >>> }; >>> >>> >>> >>> With this change: >>> >>> - the same approach of "set a bit to 0 when additional info is >>> available" will apply to the Must bit, as it does to Ref and Mod. >>> >>> - we could keep the same checks with MRI_NoModRef >>> >>> - MRI_ModRef remains the most conservative answer (top). >>> >>> - finding MRI_Must gives more info than MRI_NoModRef, so it makes sense >>> to be bottom. >>> >>> - MRI_NoModRef means "no mod or ref, and no must alias". >>> >>> >>> >>> The only obvious change I see right now will be to to add " >>> | MRI_NoModRef", essentially setting the default to "not must alias". >>> >>> For GlobalsModRef, we can also always set MRI_NoModRef bit. >>> >>> >>> >>> I may be missing details here, happy to elaborate. >>> >>> >>> >>> Happy Thanksgiving! >>> >>> >>> >>> Alina >>> >>> >>> >>> >>> >>> >>> >>> On Tue, Oct 10, 2017 at 1:13 PM, Alina Sbirlea <alina.sbirlea at gmail.com> >>> wrote: >>> >>> >>> >>> On Tue, Oct 10, 2017 at 1:05 PM, Hal Finkel <hfinkel at anl.gov> wrote: >>> >>> >>> >>> On 10/10/2017 02:49 PM, Alina Sbirlea wrote: >>> >>> Sigh >>> >>> I should have taken the time to give a better example. >>> >>> The must-alias part is irrelevant to an example (it only requires >>> read-onlyness) >>> >>> >>> >>> You said "LICM doesn't move calls, so we'd never really care about >>> must-alias for promotion". I was just pointing out other things move calls >>> any may want to know. >>> >>> >>> >>> If you want an example where the must-alias part would matter: >>> >>> >>> >>> *a = something >>> >>> foo(a) >>> >>> b = *a >>> >>> >>> >>> If foo mustalias a (and only a) not only can you move foo with a, you >>> can actually clone foo here, change it to be pass-by-value, and promote the >>> argument inside of it (if you wanted to). >>> >>> >>> >>> So you can use this info to, for example, do interprocedural promotion. >>> >>> >>> >>> >>> >>> Are we instead looking to set a MRI_Must bit, disjunct of MRI_Mod, and >>> test for MRI_Ref&MRI_Must or MRI_Mod&MRI_Must? >>> >>> >>> >>> Yes. >>> >>> >>> >>> I didn't mean to pick on the example, sorry if that's how it came >>> through. >>> >>> >>> >>> Since the consensus is to expose the Must info in ModRefInfo, I'm trying >>> to figure out how to add it in a way that makes sense to me. >>> >>> The way I see ModRefInfo is designed right now is to lower the lattice >>> to NoModRef as fast as possible (start with ModRef as top, get to NoModRef >>> as bottom). The implementation is based on having either Mod or Ref and >>> masking out everything else. >>> >>> Introducing a Must bit, means setting it occasionally (since May is >>> conservative) and then preserving it, so the opposite: start lattice at >>> bottom, set to top. >>> >>> >>> >>> What I was trying, that *somewhat* made sense: >>> enum ModRefInfo { >>> MRI_NoModRef = 0, >>> MRI_Ref = 1, >>> MRI_Mod = 2, >>> MRI_ModRef = MRI_Ref | MRI_Mod, >>> MRI_Must = 4, >>> >>> MRI_MustRef = MRI_Ref | MRI_Must, >>> >>> MRI_MustMod = MRI_Mod | MRI_Must, >>> >>> MRI_MustModRef = MRI_ModRef | MRI_Must >>> }; >>> >>> // + shift values in FunctionModRefLocation to 8, 16, 32. >>> >>> >>> >>> Recursive masking of MRI_Ref/MRI_Mod would get replaced by >>> MRI_MustRef/MRI_MustMod. >>> >>> But the top of the lattice is still MRI_ModRef. >>> >>> While the implementation details *may* be ok to resolve, there are calls >>> checking for equality to MRI_Ref or MRI_Mod (not &), so adding the >>> occasional Must bit seems bad. >>> >>> >>> >>> I don't see this as a major problem. Please feel free to fix these >>> places by replacing the equality checks with mask checks. >>> >>> >>> >>> Ok, thank you! >>> >>> >>> >>> -Hal >>> >>> So I guess my question is, what's the right approach here? I feel like >>> I'm not on the right path. >>> >>> >>> >>> >>> >>> In getModRefInfo(CS, Loc), the MRI_Must bit would then be set if >>> doesAccessArgPointees and ArgAlias == MustAlias for all Args, which seems >>> correct. >>> >>> >>> >>> >>> >>> alias == MustAlias for Loc, not for all args. >>> >>> (IE It it returns a singular result about Loc, not a result about all >>> args) >>> >>> >>> >>> To get the set answer for all args, we'd have to query further. >>> >>> >>> >>> Yes, that's what I meant. In getModRefInfo(CS, Loc) there is a loop over >>> all args, it checks alias() for each one. >>> >>> >>> >>> >>> >>> -- >>> >>> Hal Finkel >>> >>> Lead, Compiler Technology and Programming Languages >>> >>> Leadership Computing Facility >>> >>> Argonne National Laboratory >>> >>> >>> >>> >>> >>> >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171201/3de0b85c/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: image003.jpg Type: image/jpeg Size: 19653 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171201/3de0b85c/attachment.jpg>