[RFC][AliasAnalysis][BasicAA] Return MayAlias for the pointer plus variable offset to structure object member

[shiva0217]

Summary

In the following case, pointer addoff calculate by "&x.q + off" may have a chance alias to x.p structure member.

struct X {
  int *p;
  int *q;
};
int foo(int i, int j, int off)
{
  struct X x;
  int **t, *addoff;
  x.p = &i;
  x.q = &j;
  t = &x.q;
  t += off;
  addoff = *t;
  return *addoff;
}

[efriedma]

lib/Analysis/BasicAliasAnalysis.cpp

1164 ↗

(On Diff #141945)

*indices.

You should probably fix the big block comment as well; "we can't count on the constant offsets that come from non-struct sources" isn't an accurate description of the LangRef rules for GEPs.

[shiva0217]

lib/Analysis/BasicAliasAnalysis.cpp

1164 ↗

(On Diff #141945)

Hi @efriedma. Thanks for your comments. I update the comment block. Is it ok?

[efriedma]

lib/Analysis/BasicAliasAnalysis.cpp

1164 ↗

(On Diff #141945)

Could you reorganize the code so it looks more like if (!DecompGEP.VarIndices.empty()) return false; int64_t GEPBaseOffset = DecompGEP.StructOffset + DecompGEP.OtherOffset;?

[• dberlin]

This C case is actually not legal (it's been discussed before many times).
You cannot take the address of .a field, add an offset, and get to another field legally.
So i wouldn't express it in these terms, since in that language, this is clearly illegal.

The LLVM version, of course, does not make this undefined behavior AFAIK (which is a source of much imprecision)

[shiva0217]

In D45510#1066136, @dberlin wrote:

This C case is actually not legal (it's been discussed before many times).
You cannot take the address of .a field, add an offset, and get to another field legally.
So i wouldn't express it in these terms, since in that language, this is clearly illegal.

The LLVM version, of course, does not make this undefined behavior AFAIK (which is a source of much imprecision)

Hi @dberlin. Thanks for the comments. So it's a language restriction which is illegal! Would you mind point me out which rule in C99 mention this restriction or the threads relative to this topic we could follow?

[efriedma]

Ultimately the undefined behavior comes out of section 6.5.6 of the C standard: "If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined."

[hfinkel]

The LLVM version, of course, does not make this undefined behavior AFAIK (which is a source of much imprecision)

I agree. I believe this is UB in C/C++, but is well defined at the IR level (and, thus, we should still fix this).

[shiva0217]

Hi @dberlin, @efriedma, @hfinkel,

I have found some discussion about the memory layout of the structural member.
It couldn't guarantee due to the padding and alignment are according to CPU target and not restrict in C language.
So pointer arithmetic for structure member will produce undefined behavior.
Thanks for pointing me out this.

Still, @hfinkel's point seems reasonable because GEP has well defined its behavior.
So should we return MayAlias in this case?

[efriedma]

LGTM.

Yes, this patch is correct.

llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp

if (!(isa<AllocaInst>(DecompObject.Base) ||
         isa<GlobalVariable>(DecompObject.Base)) ||
       !DecompObject.VarIndices.empty())
     return false;
 
   int64_t ObjectBaseOffset = DecompObject.StructOffset +
                              DecompObject.OtherOffset;
 
   // If the GEP has no variable indices, we know the precise offset
-  // from the base, then use it. If the GEP has variable indices, we're in
-  // a bit more trouble: we can't count on the constant offsets that come
-  // from non-struct sources, since these can be "rewound" by a negative
-  // variable offset. So use only offsets that came from structs.
+  // from the base, then use it. If the GEP has variable indices,
+  // we can't get exact GEP offset to identify pointer alias. So return
+  // false in that case.
+  if (!DecompGEP.VarIndices.empty())
+    return false;
   int64_t GEPBaseOffset = DecompGEP.StructOffset;
-  if (DecompGEP.VarIndices.empty())
-    GEPBaseOffset += DecompGEP.OtherOffset;
 
   return (GEPBaseOffset >= ObjectBaseOffset + (int64_t)ObjectAccessSize);
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
 /// another pointer.
 ///
 /// We know that V1 is a GEP, but we don't know anything about V2.

llvm/trunk/test/Analysis/BasicAA/negoffset.ll

 
 ; CHECK-LABEL: Function: complex1:
 ; CHECK-DAG:  MayAlias:     i32* %a2.0, i32* %r2.0
 ; CHECK-DAG:  NoAlias:      i32* %a2.0, i32* %r2.1
 ; CHECK-DAG:  MayAlias:     i32* %a2.0, i32* %r2.i
 ; CHECK-DAG:  MayAlias:     i32* %a2.0, i32* %r2.1i
 ; CHECK-DAG:  NoAlias:      i32* %a1, i32* %r2.0
 ; CHECK-DAG:  NoAlias:      i32* %a1, i32* %r2.1
-; CHECK-DAG:  NoAlias:      i32* %a1, i32* %r2.i
-; CHECK-DAG:  NoAlias:      i32* %a1, i32* %r2.1i
+; CHECK-DAG:  MayAlias:     i32* %a1, i32* %r2.i
+; CHECK-DAG:  MayAlias:     i32* %a1, i32* %r2.1i
 %complex = type { i32, i32, [4 x i32] }
 define void @complex1(i32 %i) {
   %alloca = alloca %complex
   %alloca.i32 = bitcast %complex* %alloca to i32*
   %r.i32 = call i32* @random.i32(i32* %alloca.i32)
   %random = bitcast i32* %r.i32 to %complex*
   %a1 = getelementptr inbounds %complex, %complex* %alloca, i32 0, i32 1
   %a2.0 = getelementptr inbounds %complex, %complex* %alloca, i32 0, i32 2, i32 0
   %r2.0 = getelementptr inbounds %complex, %complex* %random, i32 0, i32 2, i32 0
   %r2.1 = getelementptr inbounds %complex, %complex* %random, i32 0, i32 2, i32 1
   %r2.i = getelementptr inbounds %complex, %complex* %random, i32 0, i32 2, i32 %i
   %r2.1i = getelementptr inbounds i32, i32* %r2.1, i32 %i
   ret void
 }
 
 ; CHECK-LABEL: Function: complex2:
-; CHECK-DAG: NoAlias: i32* %alloca, i32* %p120
-; CHECK-DAG: NoAlias: i32* %alloca, i32* %pi20
-; CHECK-DAG: NoAlias: i32* %alloca, i32* %pij1
+; CHECK-DAG: NoAlias:  i32* %alloca, i32* %p120
+; CHECK-DAG: MayAlias: i32* %alloca, i32* %pi20
+; CHECK-DAG: MayAlias: i32* %alloca, i32* %pij1
 ; CHECK-DAG: MayAlias: i32* %a3, i32* %pij1
 %inner = type { i32, i32 }
 %outer = type { i32, i32, [10 x %inner] }
 declare %outer* @rand_outer(i32* %p)
 define void @complex2(i32 %i, i32 %j) {
   %alloca = alloca i32, i32 128
   %a3 = getelementptr inbounds i32, i32* %alloca, i32 3
   %random = call %outer* @rand_outer(i32* %alloca)
   %p120 = getelementptr inbounds %outer, %outer* %random, i32 1, i32 2, i32 2, i32 0
   %pi20 = getelementptr inbounds %outer, %outer* %random, i32 %i, i32 2, i32 2, i32 0
   %pij1 = getelementptr inbounds %outer, %outer* %random, i32 %i, i32 2, i32 %j, i32 1
   ret void
 }
 
+; CHECK-LABEL: Function: pointer_offset:
+; CHECK-DAG: MayAlias: i32** %add.ptr, i32** %p1
+; CHECK-DAG: MayAlias: i32** %add.ptr, i32** %q2
+%struct.X = type { i32*, i32* }
+define i32 @pointer_offset(i32 signext %i, i32 signext %j, i32 zeroext %off) {
+entry:
+  %i.addr = alloca i32
+  %j.addr = alloca i32
+  %x = alloca %struct.X
+  store i32 %i, i32* %i.addr
+  store i32 %j, i32* %j.addr
+  %0 = bitcast %struct.X* %x to i8*
+  %p1 = getelementptr inbounds %struct.X, %struct.X* %x, i32 0, i32 0
+  store i32* %i.addr, i32** %p1
+  %q2 = getelementptr inbounds %struct.X, %struct.X* %x, i32 0, i32 1
+  store i32* %j.addr, i32** %q2
+  %add.ptr = getelementptr inbounds i32*, i32** %q2, i32 %off
+  %1 = load i32*, i32** %add.ptr
+  %2 = load i32, i32* %1
+  ret i32 %2
+}