thr3ads.net - llvm dev - [LLVMdev] Alias analysis issue with structs on PPC [Mar 2015]

If this information is useful, please help other people find it:
Share via:

Olivier H Sallenave

2015-Mar-13 21:36 UTC

[LLVMdev] Alias analysis issue with structs on PPC

Hi,

I have the following C loop to vectorize:

struct box {
    double* source;
};

void test(double* restrict result, struct box my_struct, int len)
{
    for (int i=0 ; i<len; i++) {
        result[i] = my_struct.source[i] * my_struct.source[i];
    }
}

There are two references in the loop, result[i] (restrict) and
my_struct.source[i] (readonly). The compiler should easily figure out that
they do not alias.

Compiling for x86, the loop alias analysis works just fine:
  AST: Alias Set Tracker: 2 alias sets for 2 pointer values.
  AliasSet[0x7fd8e2f32290, 1] must alias, No access Pointers: (double*
%arrayidx5, 18446744073709551615)
  AliasSet[0x7fd8e2f322e0, 1] must alias, No access Pointers: (double*
%arrayidx, 18446744073709551615)

Compiling for PPC with -target powerpc64le-ibm-linux-gnu, the two addresses
now alias:
  AST: Alias Set Tracker: 1 alias sets for 2 pointer values.
  AliasSet[0x7f931bd5bdc0, 2] may alias, No access Pointers: (double*
%arrayidx5, 18446744073709551615), (double* %arrayidx,
18446744073709551615)

BasicAA is used for both targets by default. The difference is that in PPC,
the IR obtained from Clang takes an i64 as parameter instead of a double*
for my_struct. This parameter is then coerced into double* using an
inttoptr instruction. The code in BasicAliasAnalysis.cpp which is triggered
for x86 is the following:

    // Function arguments can't alias with things that are known to be
    // unambigously identified at the function level.
    if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
        (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
      return NoAlias;

isIdentifiedFunctionLocal(V) returns true for a noalias argument (such as
result), but the other address (my_struct) must be a function argument in
order to return NoAlias, which is not the case anymore for PPC (since
my_struct is now the result from an inttoptr instruction). If I understand,
the problem is that we cannot trust the fact that locals do not alias with
restrict parameters (because the compiler could generate some locals which
alias)? If someone has suggestions about this, that would help a lot.

Thanks,
Olivier
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150313/f5c2f21b/attachment.html>

Daniel Berlin

2015-Mar-13 21:54 UTC

head link

[LLVMdev] Alias analysis issue with structs on PPC

On Fri, Mar 13, 2015 at 2:39 PM Olivier H Sallenave <ohsallen at
us.ibm.com>
wrote:
> Hi,
>
> I have the following C loop to vectorize:
>
> struct box {
>     double* source;
> };
>
> void test(double* restrict result, struct box my_struct, int len)
> {
>     for (int i=0 ; i<len; i++) {
>         result[i] = my_struct.source[i] * my_struct.source[i];
>     }
> }
>
> There are two references in the loop, result[i] (restrict) and
> my_struct.source[i] (readonly). The compiler should easily figure out that
> they do not alias.
>
> Compiling for x86, the loop alias analysis works just fine:
>   AST: Alias Set Tracker: 2 alias sets for 2 pointer values.
>   AliasSet[0x7fd8e2f32290, 1] must alias, No access Pointers: (double*
> %arrayidx5, 18446744073709551615)
>   AliasSet[0x7fd8e2f322e0, 1] must alias, No access Pointers: (double*
> %arrayidx, 18446744073709551615)
>
> Compiling for PPC with -target powerpc64le-ibm-linux-gnu, the two
> addresses now alias:
>   AST: Alias Set Tracker: 1 alias sets for 2 pointer values.
>   AliasSet[0x7f931bd5bdc0, 2] may alias, No access Pointers: (double*
> %arrayidx5, 18446744073709551615), (double* %arrayidx,
18446744073709551615)
>
> BasicAA is used for both targets by default. The difference is that in
> PPC, the IR obtained from Clang takes an i64 as parameter instead of a
> double* for my_struct.
>
I don't even want to know why this would be the case :)

> This parameter is then coerced into double* using an inttoptr instruction.
> The code in BasicAliasAnalysis.cpp which is triggered for x86 is the
> following:
>
>     // Function arguments can't alias with things that are known to be
>     // unambigously identified at the function level.
>     if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2))
||
>         (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
>       return NoAlias;
>
> isIdentifiedFunctionLocal(V) returns true for a noalias argument (such as
> result), but the other address (my_struct) must be a function argument in
> order to return NoAlias, which is not the case anymore for PPC (since
> my_struct is now the result from an inttoptr instruction). If I understand,
> the problem is that we cannot trust the fact that locals do not alias with
> restrict parameters (because the compiler could generate some locals which
> alias)?
>Yes, because pointers *based on* the noalias'd argument are legal aliases.

So if you don't know it's an argument or an identified local, it could
be
based on the restricted pointer, and thus, alias it.


If someone has suggestions about this, that would help a
lot.>
The only way you could prove something in this case would be to walk the
chain and prove the value comes directly from an argument with no
modification.

That is expensive to do in the general case, and inttoptr is generally not
going to be wonderful for performance (for example, outside of BasicAA,
more advanced AA's like CFL-AA will give up on anything that comes from or
goes through ptrtoint/inttoptr). So what's the issue that makes you pass
this as i64 in the first place?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150313/46717bad/attachment.html>

Daniel Berlin

2015-Mar-13 22:51 UTC

head link

[LLVMdev] Alias analysis issue with structs on PPC

On Fri, Mar 13, 2015 at 2:54 PM Daniel Berlin <dberlin at dberlin.org>
wrote:
> On Fri, Mar 13, 2015 at 2:39 PM Olivier H Sallenave <ohsallen at
us.ibm.com>
> wrote:
>
>> Hi,
>>
>> I have the following C loop to vectorize:
>>
>> struct box {
>>     double* source;
>> };
>>
>> void test(double* restrict result, struct box my_struct, int len)
>> {
>>     for (int i=0 ; i<len; i++) {
>>         result[i] = my_struct.source[i] * my_struct.source[i];
>>     }
>> }
>>
>> There are two references in the loop, result[i] (restrict) and
>> my_struct.source[i] (readonly). The compiler should easily figure out
that
>> they do not alias.
>>
>> Compiling for x86, the loop alias analysis works just fine:
>>   AST: Alias Set Tracker: 2 alias sets for 2 pointer values.
>>   AliasSet[0x7fd8e2f32290, 1] must alias, No access Pointers: (double*
>> %arrayidx5, 18446744073709551615)
>>   AliasSet[0x7fd8e2f322e0, 1] must alias, No access Pointers: (double*
>> %arrayidx, 18446744073709551615)
>>
>> Compiling for PPC with -target powerpc64le-ibm-linux-gnu, the two
>> addresses now alias:
>>   AST: Alias Set Tracker: 1 alias sets for 2 pointer values.
>>   AliasSet[0x7f931bd5bdc0, 2] may alias, No access Pointers: (double*
>> %arrayidx5, 18446744073709551615), (double* %arrayidx,
18446744073709551615)
>>
>> BasicAA is used for both targets by default. The difference is that in
>> PPC, the IR obtained from Clang takes an i64 as parameter instead of a
>> double* for my_struct.
>>
>
> I don't even want to know why this would be the case :)
>
>
>> This parameter is then coerced into double* using an inttoptr
>> instruction. The code in BasicAliasAnalysis.cpp which is triggered for
x86
>> is the following:
>>
>>     // Function arguments can't alias with things that are known to
be
>>     // unambigously identified at the function level.
>>     if ((isa<Argument>(O1) &&
isIdentifiedFunctionLocal(O2)) ||
>>         (isa<Argument>(O2) &&
isIdentifiedFunctionLocal(O1)))
>>       return NoAlias;
>>
>> isIdentifiedFunctionLocal(V) returns true for a noalias argument (such
as
>> result), but the other address (my_struct) must be a function argument
in
>> order to return NoAlias, which is not the case anymore for PPC (since
>> my_struct is now the result from an inttoptr instruction). If I
understand,
>> the problem is that we cannot trust the fact that locals do not alias
with
>> restrict parameters (because the compiler could generate some locals
which
>> alias)?
>>
> Yes, because pointers *based on* the noalias'd argument are legal
aliases.
>
> So if you don't know it's an argument or an identified local, it
could be
> based on the restricted pointer, and thus, alias it.
>
>
> If someone has suggestions about this, that would help a lot.
>>
>
> The only way you could prove something in this case would be to walk the
> chain and prove the value comes directly from an argument with no
> modification.
>
Actually, you could do the opposite, too, pretty cheaply.

You could write a new pass or AA.
It traverses chains in the reverse direction (IE it goes from the
arguments, and walks down the immediate use chain, marking things as based
on arguments or not), and makes a lookup table of things it can prove are
also  unmolested identified objects.
(which would be the result of inttoptr in your case).

You can then use this simple lookup table to answer the isIdentifiedObject
question better.
(You'd have to make isIdentifiedObject part of the AA interface, or take an
optional table, blah blah blah)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150313/63c5e267/attachment.html>

Possibly Parallel Threads

Search for more maybe matching threads

llvm dev - Mar 2015 - [LLVMdev] Alias analysis issue with structs on PPC

[LLVMdev] Alias analysis issue with structs on PPC

[LLVMdev] Alias analysis issue with structs on PPC

[LLVMdev] Alias analysis issue with structs on PPC

Possibly Parallel Threads