llvm dev - Apr 2016 - Different index types in GEPs -> non-aliasing?

Hi,

It seems that opt thinks that the two pointers

  %_tmp2 = getelementptr [3 x i16], [3 x i16]* %a, i16 0, i64 1
and
  %_tmp4 = getelementptr [3 x i16], [3 x i16]* %a, i16 0, i16 1

does not alias? Is this intended or a bug?


Details below:
--------------

I found this when I ran opt on:

define i16 @f () {
  %a = alloca [3 x i16]

  ; Write 98 at index 1 in the array.
  ; NB: using i64 as type of the index argument!
  %_tmp2 = getelementptr [3 x i16], [3 x i16]* %a, i16 0, i64 1
  store i16 98, i16* %_tmp2

  ; Read at index 1 in the array
  ; NB: using i16 as type of the index argument!
  %_tmp4 = getelementptr [3 x i16], [3 x i16]* %a, i16 0, i16 1
  %_tmp5 = load i16, i16* %_tmp4

  ; Check read value. If not 98, jump to bb1
  %_tmp6 = icmp ne i16 %_tmp5, 98
  br i1 %_tmp6, label %bb1, label %bb2

bb1:
  ; Error
  ret i16 1;
bb2:
  ; Ok
  ret i16 0;
}

opt -S -gvn foo.ll

and I got the result

; ModuleID = 'foo.ll'

define i16 @f() {
   %a = alloca [3 x i16]
   %_tmp2 = getelementptr [3 x i16], [3 x i16]* %a, i16 0, i64 1
   store i16 98, i16* %_tmp2
   %_tmp4 = getelementptr [3 x i16], [3 x i16]* %a, i16 0, i16 1
   br i1 undef, label %bb1, label %bb2

bb1:                                              ; preds = %0
   ret i16 1

bb2:                                              ; preds = %0
   ret i16 0
}

Note the "undef" in the branch which GVN put there:

GVN iteration: 0
GVN removed:   %_tmp5 = load i16, i16* %_tmp4
GVN removed:   %_tmp6 = icmp ne i16 undef, 98

When digging into why GVN does this, I found this little piece of code 
in GVN::AnalyzeLoadAvailability that triggers

   // Loading the allocation -> undef.
   if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI) ||
       // Loading immediately after lifetime begin -> undef.
       isLifetimeStart(DepInst)) {
     Res = AvailableValue::get(UndefValue::get(LI->getType()));
     return true;
   }

And the DepInst here is

  %a = alloca [3 x i16]

and not the store
  store i16 98, i16* %_tmp2

Digging further it seems the reason for this is that the alias analysis 
considers the two pointers used to store and load the value 98 are 
non-aliasing, even if both the pointer and the indices has the same 
values. The only difference is the type of the last value.

In e.g. BasicAliasAnalysis.cpp we have

bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
                                                   const Value *V2) {
   if (V != V2)
     return false;

and in

aliasSameBasePointerGEPs:

   // 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)
     return MayAlias;

so here we consider two pointers to be completely different just because 
the types of the last indices differ.

So is this intended or is it a bug?

What I found in the documentation of GEP is:

"When indexing into an array, pointer or vector, integers of any width 
are allowed, and they are not required to be constant. These integers 
are treated as signed values where relevant."

Regards,
Mikael

This sounds like a bug to me.

>  // 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)
>    return MayAlias;
Does changing this condition fix the issue? E.g

  if (C1 && C2 && C1->getSExtValue() ==
C2->getSExtValue()) { ... }


best
vedant

Hi,

On 04/18/2016 05:28 PM, Vedant Kumar wrote:
> This sounds like a bug to me.
>
>
>>   // 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)
>>     return MayAlias;
>
> Does changing this condition fix the issue? E.g
>
>    if (C1 && C2 && C1->getSExtValue() ==
C2->getSExtValue()) { ... }
Yes it does. Then it realize the two GEPs alias and I get the expected 
result.

But since there is also a Value pointer comparison in

bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
                                                   const Value *V2) {
   if (V != V2)
     return false;

and probably in several other places too I wasn't comfortable just 
changing it... Right now I made my front-end always use i64 for GEP 
array indices instead.

Should I file a bugzilla report on this?

Regards,
Mikael
>
>
> best
> vedant
>