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: example.ll - Pastebin.com (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
example.ll alias analysis - Pastebin.com. 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

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

From: "Alex Bradbury" <asb@asbradbury.org>
To: llvm-dev@lists.llvm.org
Cc: "Hal Finkel" <hfinkel@anl.gov>
Sent: Sunday, November 8, 2015 10:30:09 AM
Subject: Re: noalias parameter attribute not currently exploited by alias analysis?

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

From: "Alex Bradbury" <asb@asbradbury.org>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "llvm-dev" <llvm-dev@lists.llvm.org>
Sent: Monday, November 9, 2015 9:21:03 AM
Subject: Re: noalias parameter attribute not currently exploited by alias analysis?

> 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

For anyone interested in following this further, the bug is filed as
PR25462 https://llvm.org/bugs/show_bug.cgi?id=25462

Alex