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

I wanted to confirm that my understanding of the situation is correct.
For background, I've been working have an optimizer pass for a
research architecture which works best when there are large basic
blocks and good alias analysis results. I first noticed the issue in
rgbcmy01 from eembc-1.1, but have created a simpler test case which
demonstrates the same issue which is unencumbered by the EEMBC
license. Consider this simple example program:

#include <stdint.h>
#include <stdio.h>

void main_loop(int len, uint8_t *restrict input_buf, uint8_t *restrict
output_buf) {
  int    i;
  uint8_t a, b, c;

#pragma clang loop unroll_count(8)
  for (i = 0; i < len; i++) {

    a = *input_buf++;
    b = *input_buf++;
    c = *input_buf++;

    a = (uint8_t) (a - 10);
    b = (uint8_t) (b - 20);
    c = (uint8_t) (c - 30);

    *output_buf++ = a;
    *output_buf++ = b;
    *output_buf++ = c;
  }
}

__attribute__((flatten))
void dummy_function(int len, uint8_t *input_buf, uint8_t *output_buf) {
  printf("This function exists just to examine inlining behaviour\n");
  main_loop(len, input_buf, output_buf);
}

Just to skip ahead to my conclusions, as far as I can see:
* In main_loop, the noalias parameter attribute isn't exploited by
alias analysis for pointers that are created based on it
* Scoped noalias metadata along with the ScopedNoAliasAA does enable
AA to determine that input_buf and output_buf accesses don't alias
when main_loop is inlined inside dummy_function

To give some more details, I compile with a Clang nightly build with
(target mips-linux-gnu because I can't seem to get the default x86
target not to generate vector operations in the IR which complicate
matters):
clang-3.8 -emit-llvm -fno-slp-vectorize -fno-vectorize
--target=mips-linux-gnu -std=c99 -O2 example.c -c
This gives the following IR: http://pastebin.com/MXpDvUyw (note that
parameters to main_loop have noalias and that when main_loop is
inlined in to dummy_function scoped alias analysis metadata is
generated and attached to the instructions).

Running the output through opt with basicaa, tbaa and scoped-noalias
(opt-3.8 -basicaa -tbaa -scoped-noalias -aa-eval -analyze
-print-memdeps example.bc) gives the output shown at
http://pastebin.com/Z99NP6A9. You can see that 1) clobber/def
dependencies are shown throughout main_loop despite the noalias
parameter attributes. e.g.:

    Def from:   %28 = load i8, i8* %25, align 1, !tbaa !1
  store i8 %37, i8* %39, align 1, !tbaa !1

    Clobber from:   store i8 %37, i8* %39, align 1, !tbaa !1
  %42 = load i8, i8* %27, align 1, !tbaa !1

You can also see that dummy_function contains a bunch of 'unknown'
dependences:
    Unknown in block %.lr.ph.i.preheader
    Unknown in block %.lr.ph.i
  %101 = load i8, i8* %98, align 1, !tbaa !1, !alias.scope !4, !noalias !7

    Unknown
  store i8 %104, i8* %95, align 1, !tbaa !1, !alias.scope !7, !noalias !4

For what it's worth, I get the same with LLVM/Clang 3.7.

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?

Thanks,

Alex

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.

Thanks,

Alex

----- 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