[LLVMdev] Pointer aliasing

[Brent Walker]

Thank you for your reply.  The compromise you describe below, is it a
compromise in the LLVM back end or in clang?  I run into this while
building a compiler for a small DSL language for which I generate
functions that receive a context from which they extract a bunch of
pointers to doubles from which inputs are passed to the function (I
just used C/clang in my examples to illustrate the problem).

Unless I can mark these extracted pointers as non-aliasing, performance
suffers a lot.  It's not just CSE that suffers -- LLVM does not do
copy propagation either so we keep loading the same values from memory
over and over again.  See the example here:

double f(double a, double * x, double *y, double * z)
{
  *x = a;
  *y = a+1;
  *z = *x + 3;

  return *x + *y + *z;
}

define double @f(double %a, double* nocapture %x, double* nocapture
%y, double* nocapture %z) nounwind uwtable {
  store double %a, double* %x, align 8, !tbaa !0
  %1 = fadd double %a, 1.000000e+00
  store double %1, double* %y, align 8, !tbaa !0
  %2 = load double* %x, align 8, !tbaa !0
  %3 = fadd double %2, 3.000000e+00
  store double %3, double* %z, align 8, !tbaa !0
  %4 = load double* %x, align 8, !tbaa !0
  %5 = load double* %y, align 8, !tbaa !0
  %6 = fadd double %4, %5
  %7 = fadd double %6, %3
  ret double %7
}

!0 = metadata !{metadata !"double", metadata !1}
!1 = metadata !{metadata !"omnipotent char", metadata !2}
!2 = metadata !{metadata !"Simple C/C++ TBAA", null}

(I used arguments here without __restrict__ which has the same effect as
loading my pointers from context as locals).  As you can see we keep
loading the value of x from memory, even though we just stored a local
into it.  Given that I am generating LLVM IR directly (via the C++
interface) can you suggest someway I could pass the noalias attribute
onto the locals?

One work around is of course to generate two functions as follows:

double f1( struct ctx* ctx )
{
   return f2(ctx->a, ctx->x, ctx->y, ctx->z);
}

double f2( double a, double *__restrict__ x, double *__restrict__ y,
double *__restrict__  z)
{
    *x = a;
    *y = a+1;
    *z = *x + 3;

    return *x + *y + *z;
}

but if at all possible I would like to avoid such acrobatics.

Thank you in advance for any help.
Brent


On Wed, Jan 25, 2012 at 4:52 AM, Dan Gohman <gohman at apple.com> wrote:
> On Jan 24, 2012, at 7:45 AM, Brent Walker wrote:
>
>> Can you explain please why it works for this version of the function:
>>
>> double f(double *__restrict__ x, double *__restrict__ y, double
>> *__restrict__ z);
>>
>> What is different here?  There are stores here as well.
>
> LLVM ignores restrict everywhere except function parameters. This is a
> compromise aimed at a sweet spot in the balance of compiler complexity
> vs. optimization opportunity.
>
>  - Many analysis and optimization techniques naturally apply to whole
>   functions. When restrict appears on a local variable inside a
>   function, its special aliasing property applies to only a subset of
>   the function. It's awkward to teach such code to understand and
>   respect local scope boundaries, in general.
>
>  - Function boundaries are often the boundaries of analysis.
>   Interprocedural analysis can be expensive and complex, so many
>   optimization passes are limited to thinking about one function
>   at a time. And even interprocedural analysis passes are
>   bounded by shared library boundaries. While local variables can
>   often be analyzed automatically (as in your first example),
>   function paramters are often incoming mystery values, so they
>   are where restrict is most often interesting.
>
> This compromise does mean that some opportunities are lost (as in
> your second example), but from clang's perspective these cases are
> rare.
>
> Dan
>