Suggested BasicAA improvements

We recently noticed some deficiencies in BasicAA that result in poor scheduling for our downstream VLIW target. It boils down to BasicAA not being able to tell that accesses to %G1 and %G2 below would not alias.

%1 = mul i16 %X, 6
%2 = shl i16 %X, 3
%G1 = getelementptr i16, i16* %base, i16 %1
%G2 = getelementptr i16, i16* %base, i16 %2

In general that would be correct but in the special case where it is known that %X != 0 it seems reasonable to conclude that they cannot alias.

In https://reviews.llvm.org/D55107 (not at all ready, just for discussion) there is an attempt to teach BasicAA about this in the presence of a @llvm.assume on %X.

Now I am curious if adding such additional analysis to BasicAA would be considered a good idea and if so what would be the proper way to integrate it as right now my implementation feels mostly bolted on top of the existing one.

-Markus

We recently noticed some deficiencies in BasicAA that result in poor scheduling for our downstream VLIW target. It boils down to BasicAA not being able to tell that accesses to %G1 and %G2 below would not alias.

%1 = mul i16 %X, 6
%2 = shl i16 %X, 3
%G1 = getelementptr i16, i16* %base, i16 %1
%G2 = getelementptr i16, i16* %base, i16 %2

In general that would be correct but in the special case where it is known that %X != 0 it seems reasonable to conclude that they cannot alias.

In https://reviews.llvm.org/D55107 (not at all ready, just for discussion) there is an attempt to teach BasicAA about this in the presence of a @llvm.assume on %X.

Now I am curious if adding such additional analysis to BasicAA would be considered a good idea and if so what would be the proper way to integrate it as right now my implementation feels mostly bolted on top of the existing one.

Logically speaking, BasicAA is the place that should do this kind of algebraic reasoning. We need to be careful about (at least) two things:

1. Compile-time impact.

2. That we don't introduce more problems when we look back through loop backedges (look for PR32314 if you don't know what I mean).

-Hal

-Markus