One more No-alias case on Alias analysis

Project Infrastructure LLVM Dev List Archives
#1

Hello All,

I have met one may-alias case from llvm's alias analysis. The code snippet is as following:

char buf[4];

void test (int idx) {
char *a = &buf[3 - idx];
char *b = &buf[idx];
*a = 1;
*b = 2;
}

I can see below output from alias set tracker for above code snippet.

Alias sets for function 'test':
Alias Set Tracker: 1 alias sets for 2 pointer values.
AliasSet[0x53d8070, 2] may alias, Mod Pointers: (i8* %arrayidx, 1), (i8* %arrayidx2, 1)

As you can see on above code snippet, the 'a' and 'b' are not aliased. I think if we have following offset form, we can say No-alias between them.

offset1 = odd_number - index

offset2 = index

I have implemented simple code for it and the output is as following:

Alias sets for function 'test':
Alias Set Tracker: 2 alias sets for 2 pointer values.
AliasSet[0x541a070, 1] must alias, Mod Pointers: (i8* %arrayidx, 1)
AliasSet[0x541cc00, 1] must alias, Mod Pointers: (i8* %arrayidx2, 1)

How do you think about this? Is it legal for current alias analysis or not? I have attached the diff file as reference. If I missed something, please let me know.

Thanks,

JinGu Kang

alias.diff (2.16 KB)

#2

Oops, there is a typo on diff file. getLoBits(0) -->getLoBits(1)

#3

The concept works. I'm not sure your patch handles all the edge cases correctly, at first glance. (If you want a full review, please post on Phabricator.)

-Eli

#4

Thanks Eli for kind comment. I have created the review on Phabricator. Please review it.

Kind regards,

JinGu Kang

#5

Hello All,

I have met one may-alias case from llvm's alias analysis. The code
snippet is as following:

char buf[4];

void test (int idx) {
char *a = &buf[3 - idx];
char *b = &buf[idx];
*a = 1;
*b = 2;
}

I can see below output from alias set tracker for above code snippet.

Alias sets for function 'test':
Alias Set Tracker: 1 alias sets for 2 pointer values.
AliasSet[0x53d8070, 2] may alias, Mod Pointers: (i8*
%arrayidx, 1), (i8* %arrayidx2, 1)

As you can see on above code snippet, the 'a' and 'b' are not
aliased. I think if we have following offset form, we can say
No-alias between them.

offset1 = odd_number - index

offset2 = index

I have implemented simple code for it and the output is as following:

Alias sets for function 'test':
Alias Set Tracker: 2 alias sets for 2 pointer values.
AliasSet[0x541a070, 1] must alias, Mod Pointers: (i8*
%arrayidx, 1)
AliasSet[0x541cc00, 1] must alias, Mod Pointers: (i8*
%arrayidx2, 1)

How do you think about this? Is it legal for current alias analysis
or not? I have attached the diff file as reference. If I missed
something, please let me know.

The concept works. I'm not sure your patch handles all the edge cases
correctly, at first glance. (If you want a full review, please post
on Phabricator.)

+1

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.

Thanks again,
Hal

#6

Thanks Hal for good comment!

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 agree with using 'computeKnowBits' to check odd number. If I missed something, please let me know.

Thanks,

JinGu Kang

#7

Thanks Hal for good comment!

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 agree with using 'computeKnowBits' to check odd number. If I missed
something, please let me know.

We'll move this to the code-review thread.

-Hal