AliasAnalysis: may-alias subcategory

Hi,

The current AliasAnalysis marks may-alias for cases when memory passed as function argument.

i.e.

void foo(int *A, int *B, int *C) {

for (int i=0; i<N; i++)

A[i] = B[i] + C[i];

}

In the above example, it’s may-alias for memory ‘A’, because ’A’ is not known at ‘foo’ call sites.

Alias analysis is able to figure out memory ‘A’ is no-alias, if I modify the above test by making ‘A’ as an stack variable.

I’m interested to find the cases where memory is always may-alias because of input function parameter.

Probably a sub category(may-alias-because-of-function-parameter) of may-alias may help.

Not sure llvm already has something to sub categorize may-alias cases.

Thanks,

Ashutosh

You're right that stating may-alias(A, B) and may-alias(A, C) are the only possible answers right now, since the compiler cannot possibly know if these alias or not.
LLVM supports the noalias attribute for function parameters, which may be what you're looking for? http://llvm.org/docs/LangRef.html#noalias

If not, how differentiating between a may-alias and a may-alias-because-it's-input would help? Do you have a particular optimization that would be enabled?

Nuno

There are function which does have optimization opportunities but because of may-alias memory dependencies sometimes optimization is not effective. May be runtime checks kills the gains of optimization. For such cases aiming to do interprocedural function specialization optimization where in the clone function version no-alias assumption can be assumed and the original function version will hold the default alias assumption.

i.e.
void foo(int *A, int *B, int *C) {
  for (int i=0; i<N; i++)
       A[i] = B[i] + C[i];
}
void callFoo() {
   foo (A1, B1, C1); // A1 no-alias with B1 & C1
   foo (A2, B2, C2); // A2 no-alias with B1 & C1
   foo (A3, B3, C3); // A3 must-alias with B3/C3
}

Will be transformed to:
void foo(int *A, int *B, int *C) {
       // default loop version
}
void foo.clone(int * restrict A, int *B, int *C) {
       // Optimal loop version
}
void callFoo() {
   foo.clone(A1, B1, C1); // Call to optimal version
   foo.clone(A2, B2, C2); // Call to optimal version
   foo (A3, B3, C3); // Call to default version
}

For such cases I like to differentiate between “may-alias” and “may-alias-because-it's-input”.

Regards,
Ashutosh

There are function which does have optimization opportunities but because of may-alias memory dependencies sometimes optimization is not effective. May be runtime checks kills the gains of optimization. For such cases aiming to do interprocedural function specialization optimization where in the clone function version no-alias assumption can be assumed and the original function version will hold the default alias assumption.

i.e.
void foo(int *A, int *B, int *C) {
   for (int i=0; i<N; i++)
        A[i] = B[i] + C[i];
}
void callFoo() {
    foo (A1, B1, C1); // A1 no-alias with B1 & C1
    foo (A2, B2, C2); // A2 no-alias with B1 & C1
    foo (A3, B3, C3); // A3 must-alias with B3/C3
}

Will be transformed to:
void foo(int *A, int *B, int *C) {
        // default loop version
}
void foo.clone(int * restrict A, int *B, int *C) {
        // Optimal loop version
}
void callFoo() {
    foo.clone(A1, B1, C1); // Call to optimal version
    foo.clone(A2, B2, C2); // Call to optimal version
    foo (A3, B3, C3); // Call to default version
}

For such cases I like to differentiate between “may-alias” and “may-alias-because-it's-input”.

You can always call GetUnderlyingObjects on the relevant pointer values and check for those that are Arguments. Is your goal here to collect all of these may-alias results in some kind of cache while other optimizations run and then use that to specialize later?

  -Hal

Thanks Hal for inputs I'll try using it.

Regards,
Ashutosh

Agreed. Changing AA to include this information just for this use case doesn't seem like a good solution (adding a new AA result requires a lot of work). GetUnderlyingObjects() should do the trick.

Nuno