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

Tue Nov 28 15:55:22 PST 2017

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