[llvm-dev] Memory accesses and determining aliasing at the MI level

[Martin J. O'Riordan via llvm-dev]

Quick question:

   If the MIs have MMOs attached (Machine Memory Operands), then you can use MI->mayAlias(AA, MI2, true) to check.

Has 'mayAlias' been added to the MI interface since LLVM v4.0?  I don't seem to be able to find this, or an equivalent in the v4.0 sources.

Thanks,

	MartinO

-----Original Message-----
From: Martin J. O'Riordan [mailto:martin.oriordan at movidius.com] 
Sent: 21 May 2017 12:15
To: 'Hal Finkel' <hfinkel at anl.gov>; 'LLVM Developers' <llvm-dev at lists.llvm.org>
Subject: RE: [llvm-dev] Memory accesses and determining aliasing at the MI level

Hi Hal,

It's not completely about aliasing, though it is related.

Our target has two load/store units, and if I can determine the offset of the 2 accesses from a common reference base pointer, then I can arrange to issue the memory accesses on each unit to optimise memory performance so as to avoid accesses within the same region (tile) which can result in a stall.  For example, given a base-pointer BP, and two accesses at Delta1 and Delta2 from BP, I can check if the two accesses actually address within the same region by checking the arithmetic relationship between Delta1 and Delta2, even though they are not aliased accesses.  I suppose it's a bit like analysing two accesses to see if they are in the same cache-line or in separate cache-lines, though at a finer level of granularity.

We did experiment with this by creating a much earlier IR pass that tracked this information and attached a custom attribute with the tile affinity information, but it was more invasive to the target independent code than I would like.  So what I am trying to do now is see if this analysis can be moved closer, or even wholly, to the target specific lowering and scheduling phases.  But with each step closer to the actual machine target, useful abstract information starts disappearing a little at a time.

If the techniques would be more generally useful to multiple targets, then it may justify a target independent approach, but none of the In-Tree targets appear to benefit from this kind of analysis so I have nothing to compare against.

During Post-RA scheduling we do still have the MMOs for the majority (possible all) memory accesses, so the 'mayAlias' check does work.  I'll dig into the alias analysis to see if I can see if there are techniques there that I can leverage.

Thanks,

	MartinO

-----Original Message-----
From: Hal Finkel [mailto:hfinkel at anl.gov]
Sent: 20 May 2017 03:52
To: Martin J. O'Riordan <martin.oriordan at movidius.com>; 'LLVM Developers' <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] Memory accesses and determining aliasing at the MI level

Hi, Martin,

If the MIs have MMOs attached (Machine Memory Operands), then you can use MI->mayAlias(AA, MI2, true) to check. This will use alias analysis if available. If you look at the implementation, you'll also see how to use AA based on the MMOs.

Also, saying "same base pointer" might get a bit tricky after stack coloring.

  -Hal

On 05/18/2017 09:41 AM, Martin J. O'Riordan via llvm-dev wrote:
> In order to implement a subtle memory access optimisation during 
> post-RA scheduling, I want to be able to determine some properties 
> about the memory access.
>
> If I have two registers referring to memory, how can I determine if 
> they are derived from the same base-pointer?  Often LLVM will optimise 
> to use intermediate registers holding partial displacements, for 
> example, when a 'struct' object is on the stack, the address of the 
> start of that object might be computed as:
>
>      R1 := SP + initialDisplacement;
>
> then the access to a member of that object may be accessed with a 
> member offset from 'R1'.  This can get more complicated with larger 
> examples where a series of intermediate registers with different 
> displacements occur, yet they may all derive from a common ancestor 
> base-pointer (the SP being the most common).
>
> What I would like to determine, is during post-RA scheduling, and 
> given 2 registers 'R1' and 'R2' referring to memory:
>
> 1.  Do 'R1' and 'R2' share a common base-pointer?
> 2.  For 'R1' and 'R2', what is the summary displacement from their 
> respective base-pointers?
>
> Is this possible in post-RA at the MI level and if so how I can do 
> this, or would I have to write an earlier pass to annotate the IR with 
> the information I am looking for?
>
> Thanks,
>
>      MartinO
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--
Hal Finkel
Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory