llvm dev - Nov 2020 - Clarifying noalias with metadata merging

Hi,

Looking at how noalias is defined:
https://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata
"When evaluating an aliasing query, **if for some domain**, the set of
scopes with that domain in one instruction’s alias.scope list is a subset of (or
equal to) the set of scopes for that domain in another instruction’s noalias
list, then the two memory accesses are assumed not to alias."


This corresponds to Hal's change from llvm-svn: 213948
"...
The subset/superset condition now
applies within each domain independently, and we only need it to hold in one
domain. Each time we inline, we add the new scopes in a new scope domain, and
everything now composes nicely. In addition, this simplifies the
implementation.
..."

I think I understand the intent here for inlining: domains are compared in
nested order and the first one in noalias which is a superset of alias.scope
means regardless of further inlining there can't be aliasing.

However, when other optimizations like memcpyopt merge instructions they merge
metadata which in the case of alias.scope means taking the union between the 2
instructions. However, this appears to break the nesting paradigm since
what's getting merged in doesn't need to have an inline-inliner
relationship. This can then lead to incorrect aliasing information being
computed.

Is the semantics for noalias/alias.scope in use still that which is documented
in the LangRef? And if so, is metadata merging as it is now doing something
wrong here?

Thanks,
Modi

Hi Modi,

for !noalias/!alias.scope, merging metadata for from two instructions means:
- !noalias: taking the intersection (= the merged instruction can only
'noalias'
  with the scopes for which all of the original instructions are
'noalias')
- !alias.scope: taking the union (= the merged instruction can alias with any
  of the 'aliases of the original instructions')

This ensures that, at worst, a previous 'NoAlias' alias analysis result
will
now become 'MayAlias', which is still correct, but maybe less efficient.

Note: if you are interested in alias analysis and restrict support, you
should take a look at the 'Full Restrict' patches[0]. 

Greetings,

Jeroen Dobbelaere

[0] Full Restrict Patches: https://reviews.llvm.org/D68484

> -----Original Message-----
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Modi
Mo via
> llvm-dev
> Sent: Tuesday, November 17, 2020 03:36
> To: llvm-dev at lists.llvm.org
> Subject: [llvm-dev] Clarifying noalias with metadata merging
> 
> Hi,
> 
> Looking at how noalias is defined:
> https://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata
> "When evaluating an aliasing query, **if for some domain**, the set of
scopes
> with that domain in one instruction’s alias.scope list is a subset of (or
> equal to) the set of scopes for that domain in another instruction’s
noalias
> list, then the two memory accesses are assumed not to alias."
> 
> 
> This corresponds to Hal's change from llvm-svn: 213948
> "...
> The subset/superset condition now
> applies within each domain independently, and we only need it to hold in
one
> domain. Each time we inline, we add the new scopes in a new scope domain,
and
> everything now composes nicely. In addition, this simplifies the
> implementation.
> ..."
> 
> I think I understand the intent here for inlining: domains are compared in
> nested order and the first one in noalias which is a superset of
alias.scope
> means regardless of further inlining there can't be aliasing.
> 
> However, when other optimizations like memcpyopt merge instructions they
merge
> metadata which in the case of alias.scope means taking the union between
the 2
> instructions. However, this appears to break the nesting paradigm since
what's
> getting merged in doesn't need to have an inline-inliner relationship.
This
> can then lead to incorrect aliasing information being computed.
> 
> Is the semantics for noalias/alias.scope in use still that which is
documented
> in the LangRef? And if so, is metadata merging as it is now doing something
> wrong here?
> 
> Thanks,
> Modi
>