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

Thu Nov 23 03:52:18 PST 2017

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>