[llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)

[Alina Sbirlea via llvm-dev]

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>