llvm dev - Nov 2017 - 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>

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>

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>

> 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.

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>

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>