[BasicAA] Compare GEP indices based on value

[vsk]

Summary

Equivalent GEP indices with different types are treated as different
indices altogether, leading to a loss in AA precision. Fix the issue
(PR27418) by comparing indices based on their values.

[ab]

Good catch; scary bug! The test is somewhat brittle though. What do you think of boiling it down to its essence; something like:

; PR27418 - Treat GEP indices with the same value but different types the same
; CHECK-LABEL: test_different_index_types
; CHECK: MustAlias: i16* %tmp1, i16* %tmp2
define void @test_different_index_types([2 x i16]* %arr) {
  %tmp1 = getelementptr [2 x i16], [2 x i16]* %arr, i16 0, i32 1
  %tmp2 = getelementptr [2 x i16], [2 x i16]* %arr, i16 0, i16 1
  ret void
}

in struct-geps.ll ? Looks like that actually used to return NoAlias (because of the assumption that C1 && C2 implies C1 != C2 later on).

[vsk]

• Updated with Ahmed's suggested test case.

[uabelho]

Great! We've done a fix like this locally to get around the problem and it's worked so far.

However, I'm a little bit worried that there could be other places in AA where GEPs are considered to be noaliasing only based on checking Value pointers, e.g in

bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,

                                                const Value *V2) {
if (V != V2)
  return false;

but I don't know the code well enough to know if the code above can cause any similar problems or not.

[ab]

In D19935#425744, @uabelho wrote:

However, I'm a little bit worried that there could be other places in AA where GEPs are considered to be noaliasing only based on checking Value pointers, e.g in

bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,

                                                const Value *V2) {
if (V != V2)
  return false;

but I don't know the code well enough to know if the code above can cause any similar problems or not.

You're absolutely right that this problem could lurk elsewhere; isValueEqualInPotentialCycles was actually added to avoid that problem in r198290, for PHI cycles though. I think the same problem could occur for no-op instructions ("alias((add x, 0), x)"), but it looks like all the current users are safe. I'm not sure I have an answer to the general problem though :/

Re: this particular issue though: LGTM, thanks Vedant!

llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp

static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
 
   ConstantInt *C1 =
       dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
   ConstantInt *C2 =
       dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
 
   // If the last (struct) indices are constants and are equal, the other indices
   // might be also be dynamically equal, so the GEPs can alias.
-  if (C1 && C2 && C1 == C2)
+  if (C1 && C2 && C1->getSExtValue() == C2->getSExtValue())
     return MayAlias;
 
   // Find the last-indexed type of the GEP, i.e., the type you'd get if
   // you stripped the last index.
   // On the way, look at each indexed type.  If there's something other
   // than an array, different indices can lead to different final types.
   SmallVector<Value *, 8> IntermediateIndices;
 

llvm/trunk/test/Analysis/BasicAA/struct-geps.ll

 
 ; CHECK-LABEL: test_struct_in_array
 ; CHECK-DAG: MustAlias: i32* %x, i32* %y
 define void @test_struct_in_array(%struct2* %st, i64 %i, i64 %j, i64 %k) {
   %x = getelementptr %struct2, %struct2* %st, i32 0, i32 1, i32 1, i32 0
   %y = getelementptr %struct2, %struct2* %st, i32 0, i32 0, i32 1, i32 1
   ret void
 }
+
+; PR27418 - Treat GEP indices with the same value but different types the same
+; CHECK-LABEL: test_different_index_types
+; CHECK: MustAlias: i16* %tmp1, i16* %tmp2
+define void @test_different_index_types([2 x i16]* %arr) {
+  %tmp1 = getelementptr [2 x i16], [2 x i16]* %arr, i16 0, i32 1
+  %tmp2 = getelementptr [2 x i16], [2 x i16]* %arr, i16 0, i16 1
+  ret void
+}