[llvm-dev] recursive alias analysis allowed ?

[Jeroen Dobbelaere via llvm-dev]

Hi Hal,

the restrict improvements that I have done are based on your set of local restrict patches. Nothing has changed in the plain metadata.
But, I did do a split up of the intrinsic in multiple intrinsics, and I added an extra optional parameter to the store/load instructions.

The llvm.noalias intrinsic that clang initially generates, is converted into a 'llvm.side.noalias.plain' intrinsic, tracking the original metadata and relevant pointer dependencies.
These intrinsics  are connected to the noalias_sidechannel of the store/load instructions and the original llvm.noalias intrinsics are removed. Some extra intrinsics also help in propagating information into inlined functions, and getting the metadata correct while unrolling loops.

All of this allows the different optimization passes to do relevant transformations, without being bothered by the noalias intrinsics. Either the optimization keeps the sidechannel (original restrict info will be remembered), or it generates a new load/store instruction, in which case it falls back to the default of not knowing anything.

I am now looking to add support for restrict member pointer (and more generally 'pointer to a restrict pointer', ...)
An extra intrinsic will be needed: llvm.side.noalias.gep, that introduces the restrictness for a datalocation.

Something like : 

struct FOO { int* __restrict p; };
int fum(struct FOO* p0, struct FOO* p1) {
  *p0->p=42;
  *p1->p=43;
...
}

should look (after some transformations) like:

...
%p0_p = getelementptr %struct.FOO, 5struct.FOO* %p0, i32 0, i32 0
%side_gep.p0_p = i32* llvm.side.noalias.gep i32** %p0_p, metadata !99                             (2A)
%v0 = load i32*, i32** %p0_p
store i32 42, i32* %v0, noalias_sidechannel i32* %side_gep.p0_p, ...., metadata !99         (1A)

%p1_p = getelementptr %struct.FOO, 5struct.FOO* %p1, i32 0, i32 0
%side_gep.p1_p = i32* llvm.side.noalias.gep i32** %p1_p, metadata !99                             (2B)
%v1 = load i32*, i32** %p1_p
store i32 43, i32* %v1, noalias_sidechannel i32* %side_gep.p1_p, ...., metadata !99...      (1B)


In order to see if the stores (1A) and (1B) alias (according to the restrict rules), the ScopedNoAlias need to check, if:
  - the scopes are compatible,
  - and if the base objects (pointed to by the llvm.side.noalias.gep in 2A and 2B) alias (which results in a recursive alias call).


Hence my questions:
- is it safe to do recursive 'alias' calls while being in the middle of an alias pass ?
- what is the correct location for adding the initialisation of the AA pointer inside the pass ?

Greetings,

Jeroen Dobbelaere

> -----Original Message-----
> From: Finkel, Hal J. [mailto:hfinkel at anl.gov]
> Sent: Tuesday, October 9, 2018 18:40
> To: Jeroen Dobbelaere <jeroen.dobbelaere at synopsys.com>; llvm-
> dev at lists.llvm.org
> Subject: Re: recursive alias analysis allowed ?
> 
> Hi, Jeroen,
> 
> Can you please explain in more detail what you're trying to do?
> Obviously, disjoint storage locations can hold the same pointer value.
> Where does the metadata enter the picture?
> 
> Thanks again,
> 
> Hal
> 
> 
> On 10/09/2018 11:30 AM, Jeroen Dobbelaere wrote:
> > Hi Hal et al,
> >
> > I am extending the ScopedNoAliasAA pass with some deeper analysis. The
> goal is to add restrict member pointer support.
> >
> > For that I'll need to do an extra alias-analysis request from within the
> ScopedNoAliasAA pass:
> >
> > for example:
> >   %v1 = load i32*, i32** %p1
> >   %result1= load i32, i32* %v1
> >   %v2 = load i32*, i32** %p2
> >   %result2= load i32, i32* %v2
> >
> > in order to proof that %v1 and %v2 are not aliasing, I need to proof that
> their storages %p1 and %p2 are not aliasing.
> >
> > - (1) This means that we will get recursive (possibly multiple levels) alias
> analysis calls.
> > - (2) I'll also need access to the main AliasAnalysis inside the
> ScopedNoAliasAA.
> >
> > Do you think (1) will be safe to do ?
> >
> > For (2), is the right location to do this, everywhere the DominatorTree is set
> ? (setDT(), ScopedNoAliasAAResult constructor, ...)
> >
> > Thanks,
> >
> > Jeroen Dobbelaere
> >
> 
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory