llvm dev - Nov 2015 - noalias parameter attribute not currently exploited by alias analysis?

----- Original Message -----
> From: "Alex Bradbury" <asb at asbradbury.org>
> To: llvm-dev at lists.llvm.org
> Cc: "Hal Finkel" <hfinkel at anl.gov>
> Sent: Sunday, November 8, 2015 10:30:09 AM
> Subject: Re: noalias parameter attribute not currently exploited by alias
analysis?
> 
> On 2 November 2015 at 20:20, Alex Bradbury <asb at asbradbury.org>
> wrote:
> > Can anyone give advice on how to interpret these 'Unknown'
query
> > results? It's also curious how about halfway through the basic
> > block
> > containing the unrolled loop the Unknown query results no longer
> > have
> > an associated basic block, despite the fact the code sequences are
> > simply repeated.h
> >
> > Is there something obvious I'm missing here, or have I run in to a
> > bug/limitation?
> 
> Hi Hal, list - I'd really appreciate some input here if anyone has a
> moment. It seems there could be some real-world code missing out
> based
> mainly on whether a function with restrict args is inlined or not?
> 
> To solve this issue for my use-case, I've written something for my
> pass that's not too dissimilar to getUnderlyingObject(s) that will do
> a better job of determining if a pointer is derived from an argument,
> and added a bit of logic to filter out mayalias results where both
> operations involve pointers derived from different noalias args. Just
> generating the scoped-noalias metadata for all functions would
> probably have been more straightforward, but unfortunately my pass is
> implemented in an LLVM forked from before scoped-noalias metadata
> support was introduced.
Hi Alex,

Thanks for reporting this issue, and I apologize for the delayed reply. It seems
you've run into a limitation of the current implementation, and please do
file a bug report.

If I take your IR, and run it through:

  opt -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata
-print-all-alias-modref-info -disable-output 2>&1 < /tmp/your/input.ll

there seems to be a limitation with the way that pointer provenance is
determined. Looking at the mod/ref info, things quickly become suboptimal:

  NoAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->   store i8
%11, i8* %.013.prol, align 1, !tbaa !1
  NoAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->   store i8
%14, i8* %18, align 1, !tbaa !1
  NoAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->   store i8
%17, i8* %19, align 1, !tbaa !1
  MayAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->   store
i8 %31, i8* %.013, align 1, !tbaa !1
  MayAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->   store
i8 %34, i8* %38, align 1, !tbaa !1
  ...

it seems like looking through one PHI is okay, but as soon as we need to look
though both the PHI in the loop and also the PHI in the preheader, we're
unable to do so conclusively. This seems to be the underlying problem.

 -Hal
> 
> Thanks,
> 
> Alex
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On 9 November 2015 at 14:30, Hal Finkel <hfinkel at anl.gov>
wrote:
> Thanks for reporting this issue, and I apologize for the delayed reply. It
seems you've run into a limitation of the current implementation, and please
do file a bug report.
>
> If I take your IR, and run it through:
>
>   opt -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata
-print-all-alias-modref-info -disable-output 2>&1 < /tmp/your/input.ll
>
> there seems to be a limitation with the way that pointer provenance is
determined. Looking at the mod/ref info, things quickly become suboptimal:
>
>   NoAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->  
store i8 %11, i8* %.013.prol, align 1, !tbaa !1
>   NoAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->  
store i8 %14, i8* %18, align 1, !tbaa !1
>   NoAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->  
store i8 %17, i8* %19, align 1, !tbaa !1
>   MayAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->  
store i8 %31, i8* %.013, align 1, !tbaa !1
>   MayAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->  
store i8 %34, i8* %38, align 1, !tbaa !1
>   ...
>
> it seems like looking through one PHI is okay, but as soon as we need to
look though both the PHI in the loop and also the PHI in the preheader,
we're unable to do so conclusively. This seems to be the underlying problem.
Thanks for confirming I'm not missing anything obvious here. I'll file
an issue later today.

I don't suppose you had any thoughts on the 'Unknown' dependencies
reported in -print-memdeps? Their occurrence seems rather mysterious
to me - even more mysterious that some 'Unknown' dependencies can be
associated with a basic block but not others, despite the code being
perfectly regular.

Cheers,

Alex

----- Original Message -----
> From: "Alex Bradbury" <asb at asbradbury.org>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Monday, November 9, 2015 9:21:03 AM
> Subject: Re: noalias parameter attribute not currently exploited by alias
analysis?
> 
> On 9 November 2015 at 14:30, Hal Finkel <hfinkel at anl.gov> wrote:
> > Thanks for reporting this issue, and I apologize for the delayed
> > reply. It seems you've run into a limitation of the current
> > implementation, and please do file a bug report.
> >
> > If I take your IR, and run it through:
> >
> >   opt -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata
> >   -print-all-alias-modref-info -disable-output 2>&1 <
> >   /tmp/your/input.ll
> >
> > there seems to be a limitation with the way that pointer provenance
> > is determined. Looking at the mod/ref info, things quickly become
> > suboptimal:
> >
> >   NoAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->
> >     store i8 %11, i8* %.013.prol, align 1, !tbaa !1
> >   NoAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->
> >     store i8 %14, i8* %18, align 1, !tbaa !1
> >   NoAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->
> >     store i8 %17, i8* %19, align 1, !tbaa !1
> >   MayAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->
> >     store i8 %31, i8* %.013, align 1, !tbaa !1
> >   MayAlias:   %4 = load i8, i8* %.04.prol, align 1, !tbaa !1 <->
> >     store i8 %34, i8* %38, align 1, !tbaa !1
> >   ...
> >
> > it seems like looking through one PHI is okay, but as soon as we
> > need to look though both the PHI in the loop and also the PHI in
> > the preheader, we're unable to do so conclusively. This seems to
> > be the underlying problem.
> 
> Thanks for confirming I'm not missing anything obvious here. I'll
> file
> an issue later today.
Great, thanks!
> 
> I don't suppose you had any thoughts on the 'Unknown'
dependencies
> reported in -print-memdeps? Their occurrence seems rather mysterious
> to me - even more mysterious that some 'Unknown' dependencies can
be
> associated with a basic block but not others, despite the code being
> perfectly regular.
I'd need to look at this in more detail in order to answer. I don't use
that pass often enough to have an immediate comment.

 -Hal
> 
> Cheers,
> 
> Alex
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory