Add one more No-alias case to alias analysis.
Needs ReviewPublic

Authored by jaykang10 on Jun 12 2018, 2:50 AM.

Details

Summary

Let's look at following C code snippet.

char buf[4];
int idx = any value;
char *a = buf[3 - idx];
char *b = buf[idx];

a and b are not aliased. As a result, if the offsets has form as below,
we can say it is not aliased.

offset1 = odd number - index;
offset2 = index;

Diff Detail

jaykang10 created this revision.Jun 12 2018, 2:50 AM

I put this on the llvm-dev thread, but to repeat it here:

In your example, we have:

3 - idx == idx => 3 == 2*idx

and you've generalized this slightly to make this:

(odd number) == 2*idx

which makes sense. I think that we can go further looking at:

n == 2*idx

and, calling computeKnownBits on n and idx, then asking whether:

knownZeros(n) == (knownZeros(idx) << 1) | 1 and
knownOnes(n) == knownOnes(idx) << 1

(please note the comment in aliasSameBasePointerGEPs regarding avoiding
PR32314)

also, if we have more than one array access, we can have:

n - idx == m - idx

then we have:

n-m == 2*idx

and so we can check:

knownZeros(n-m) == (knownZeros(idx) << 1) | 1 and
knownOnes(n-m) == knownOnes(idx) << 1

Sadly, we don't have a good API to do the knownBits check on the
subtraction of non-constants, but you only need the constants in your
case, and we can leave the more-general case for future work.

nlopes added a subscriber: nlopes.Jun 12 2018, 5:39 AM
nlopes added inline comments.
lib/Analysis/BasicAliasAnalysis.cpp
1813

you don't need the zext here. The value should have at least 1 bit, so that's sufficient to test for even/odd.

jaykang10 updated this revision to Diff 150932.Jun 12 2018, 5:46 AM
nlopes added inline comments.Jun 12 2018, 5:55 AM
lib/Analysis/BasicAliasAnalysis.cpp
1886

BTW don't you need to limit this trick to 1 byte accesses?

I think that this optimization is going to be very fragile in practice without also handling the case where both sides look like (m-idx). Nevertheless, it's good to make AA changes in minimal small increments. Let's try this single case for now.

Even with this, however, regarding this:

It seems the 'computeKnownBits' does not handle non-constant values well.

For example,

define void @test(i32 %idx) {
entry:
 %sub = sub nsw i32 3, %idx

It fails to get Zero and One from %idx.

I'm not sure you mean? In this case, nothing is known about idx, so what would it get?

However, if you do something like:

 ... @test(i32 %i) {
  %idx = and i32 %i, 3
  %sub nsw i32 3, %idx
}

then computeKnownBits will know something about the bits of idx.

lib/Analysis/BasicAliasAnalysis.cpp
1812

Don't need { } here.

1816

Don't need { } here.

1822

Don't need { } here. Also, is there an extra set of parenthesis here?

1882

Don't need { } here.

jaykang10 added inline comments.Jun 12 2018, 6:28 AM
lib/Analysis/BasicAliasAnalysis.cpp
1813

Oops, sorry... I have updated it with @hfinkel 's comment.

knownZeros(n) == (knownZeros(idx) << 1) | 1 and
knownOnes(n) == knownOnes(idx) << 1

I meant if nothing is known about idx, we fail to get No-alias opportunity. If there is nothing for KnownBits, let's just check odd number and the idx is used by both offsets as below.

if (success of computeKnownBits with `n` and `idx`) {
  knownZeros(n) == (knownZeros(idx) << 1) | 1 and
  knownOnes(n) == knownOnes(idx) << 1
} else {
  check just LHS is odd number and RHS is shared by offsets.
}

How do you think about it? @hfinkel

knownZeros(n) == (knownZeros(idx) << 1) | 1 and
knownOnes(n) == knownOnes(idx) << 1

I meant if nothing is known about idx, we fail to get No-alias opportunity. If there is nothing for KnownBits, let's just check odd number and the idx is used by both offsets as below.

if (success of computeKnownBits with `n` and `idx`) {
  knownZeros(n) == (knownZeros(idx) << 1) | 1 and
  knownOnes(n) == knownOnes(idx) << 1
} else {
  check just LHS is odd number and RHS is shared by offsets.
}

How do you think about it? @hfinkel

I don't understand what you're saying. Once you shift, you know that the lowest-order bit is zero. You can naturally combine that with whatever other information also happens to be known about idx.

jaykang10 updated this revision to Diff 150956.Jun 12 2018, 8:54 AM

I don't understand what you're saying. Once you shift, you know that the lowest-order bit is zero. You can naturally combine that with whatever other information also happens to be known about idx.

Ah... I understand it now... I am sorry for late understand... I am not smart person. I have updated code. Please review whether it is correct or not. If it is correct, I will write the code for "n - m == 2 * idx". Thank you very much @hfinkel !!!

jaykang10 updated this revision to Diff 150970.Jun 12 2018, 9:31 AM