llvm dev - May 2017 - Memory accesses and determining aliasing at the MI level

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

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

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

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