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

[Alina Sbirlea via llvm-dev]

On Fri, Dec 1, 2017 at 1:10 PM, Alina Sbirlea via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

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

Following D40933 <https://reviews.llvm.org/D40933>, ModRefInfo is an enum
class.
Since this change is potentially disruptive, I will wait pushing the patch
adding the Must bit until this change is sure to stick.


>
>
>> 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
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171207/f96885e4/attachment-0001.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/20171207/f96885e4/attachment-0001.jpg>