[InstSimplify] Don't fold gep p, -p to null

[nikic]

Summary

This is a partial fix for https://bugs.llvm.org/show_bug.cgi?id=44403. Folding gep p, q-p to q is only legal if p and q have the same provenance. This fold should probably be guarded by something like getUnderlyingObject(p) == getUnderlyingObject(q).

This patch is a partial fix that removes the special handling for gep p, 0-p, which will fold to a null pointer, which would certainly not pass an underlying object check (unless p is also null, in which case this would fold trivially anyway). Folding to a null pointer is particularly problematic due to the special handling it receives in many places, making end-to-end miscompiles more likely.

[nlopes]

I only looked at the tests and they were correct before, see here: https://alive2.llvm.org/ce/z/UzW3pv
The tests are weird because they have 'gep inbounds'. The reason they are correct (and weird) is that the only way p - (int)p/sizeof(*p) is inbounds is p being null. Anything else will overflow.

The code is buggy because it doesn't require inbounds (not caught because there's no test without inbounds): https://gcc.godbolt.org/z/GYxc78

So in the end the transformation doesn't seem very useful in practice?

[nikic]

In D93820#2471737, @nlopes wrote:

I only looked at the tests and they were correct before, see here: https://alive2.llvm.org/ce/z/UzW3pv
The tests are weird because they have 'gep inbounds'. The reason they are correct (and weird) is that the only way p - (int)p/sizeof(*p) is inbounds is p being null. Anything else will overflow.

This doesn't look right to me, at least not given current LangRef wording. Lets say we have gep inbounds p, -p, where p = ptr(base_addr = 1, offset = -1). This means that the address value of p is 0, but it has provenance of the object at base_addr = 1. As such, the inbounds is not violated (both p and the gep results are inbounds of the zero address), but we still change provenance.

For the transform to be correct, the GEP inbounds specification would have to require not only that the base address is in bounds of an allocated object, but that it is in bounds of the allocated object corresponding to the provenance of the base value. Is that supposed to be part of the GEP inbounds semantics?

The code is buggy because it doesn't require inbounds (not caught because there's no test without inbounds): https://gcc.godbolt.org/z/GYxc78

I did consider making this transform require inbounds instead. The requirement that at least the address values belong to the same object would make practical miscompiles less likely. However, as argued above, I don't think the inbounds requirements would actually make the transform correct. And alive does agree that requiring inbounds is not sufficient for the more general case (https://alive2.llvm.org/ce/z/Fykn-3).

So in the end the transformation doesn't seem very useful in practice?

At least, the null pointer case I'm touching here doesn't fire on test-suite -O3 at all...

[nlopes]

In D93820#2471778, @nikic wrote:

In D93820#2471737, @nlopes wrote:

I only looked at the tests and they were correct before, see here: https://alive2.llvm.org/ce/z/UzW3pv
The tests are weird because they have 'gep inbounds'. The reason they are correct (and weird) is that the only way p - (int)p/sizeof(*p) is inbounds is p being null. Anything else will overflow.

This doesn't look right to me, at least not given current LangRef wording. Lets say we have gep inbounds p, -p, where p = ptr(base_addr = 1, offset = -1). This means that the address value of p is 0, but it has provenance of the object at base_addr = 1. As such, the inbounds is not violated (both p and the gep results are inbounds of the zero address), but we still change provenance.

There's an extra catch: gep inbounds requires both the input and output pointers to be in bounds. This part is explicit in LangRef, at least.
Some examples:

p = malloc()
q = gep inbounds p, -1  // poison
r = gep p, -1           // ok
s = gep inbounds r, 1   // poison: r is not inbounds
t = gep r, 1            // ok, offset = 0
u = gep inbounds t, 1   // ok, offset = 1 (assuming malloc size > 0)

For the transform to be correct, the GEP inbounds specification would have to require not only that the base address is in bounds of an allocated object, but that it is in bounds of the allocated object corresponding to the provenance of the base value. Is that supposed to be part of the GEP inbounds semantics?

The code is buggy because it doesn't require inbounds (not caught because there's no test without inbounds): https://gcc.godbolt.org/z/GYxc78

I did consider making this transform require inbounds instead. The requirement that at least the address values belong to the same object would make practical miscompiles less likely. However, as argued above, I don't think the inbounds requirements would actually make the transform correct. And alive does agree that requiring inbounds is not sufficient for the more general case (https://alive2.llvm.org/ce/z/Fykn-3).

Right, only the null case is correct because it only works when the input pointer is null; all other cases were poison. So transforming poison into null is fine.
The general case changes provenance. It's very wrong. And LangRef is explicit about this case as well. Well, and BasicAA will break programs if you do this general transformation as it uses provenance to prove no alias.

So in the end the transformation doesn't seem very useful in practice?

At least, the null pointer case I'm touching here doesn't fire on test-suite -O3 at all...

The transformation does look weird. When is the code trying to compute nullptr in some convoluted way? I have some inclination to remove it altogether.

[nikic]

In D93820#2471788, @nlopes wrote:

In D93820#2471778, @nikic wrote:

In D93820#2471737, @nlopes wrote:

I only looked at the tests and they were correct before, see here: https://alive2.llvm.org/ce/z/UzW3pv
The tests are weird because they have 'gep inbounds'. The reason they are correct (and weird) is that the only way p - (int)p/sizeof(*p) is inbounds is p being null. Anything else will overflow.

This doesn't look right to me, at least not given current LangRef wording. Lets say we have gep inbounds p, -p, where p = ptr(base_addr = 1, offset = -1). This means that the address value of p is 0, but it has provenance of the object at base_addr = 1. As such, the inbounds is not violated (both p and the gep results are inbounds of the zero address), but we still change provenance.

There's an extra catch: gep inbounds requires both the input and output pointers to be in bounds. This part is explicit in LangRef, at least.
Some examples:

p = malloc()
q = gep inbounds p, -1  // poison
r = gep p, -1           // ok
s = gep inbounds r, 1   // poison: r is not inbounds
t = gep r, 1            // ok, offset = 0
u = gep inbounds t, 1   // ok, offset = 1 (assuming malloc size > 0)

Right, but inbounds and provenance are, as far as I can tell, orthogonal concepts. Alive claims that this code has UB due to use of gep inbounds: https://alive2.llvm.org/ce/z/zTctIR At the same time, the gep inbounds itself is not poison: https://alive2.llvm.org/ce/z/wxGGyu That makes it looks like Alive also constrains provenance based on gep inbounds, not just the value of the pointer.

[nlopes]

In D93820#2471805, @nikic wrote:

In D93820#2471788, @nlopes wrote:

In D93820#2471778, @nikic wrote:

In D93820#2471737, @nlopes wrote:

I only looked at the tests and they were correct before, see here: https://alive2.llvm.org/ce/z/UzW3pv
The tests are weird because they have 'gep inbounds'. The reason they are correct (and weird) is that the only way p - (int)p/sizeof(*p) is inbounds is p being null. Anything else will overflow.

This doesn't look right to me, at least not given current LangRef wording. Lets say we have gep inbounds p, -p, where p = ptr(base_addr = 1, offset = -1). This means that the address value of p is 0, but it has provenance of the object at base_addr = 1. As such, the inbounds is not violated (both p and the gep results are inbounds of the zero address), but we still change provenance.

There's an extra catch: gep inbounds requires both the input and output pointers to be in bounds. This part is explicit in LangRef, at least.
Some examples:

p = malloc()
q = gep inbounds p, -1  // poison
r = gep p, -1           // ok
s = gep inbounds r, 1   // poison: r is not inbounds
t = gep r, 1            // ok, offset = 0
u = gep inbounds t, 1   // ok, offset = 1 (assuming malloc size > 0)

Right, but inbounds and provenance are, as far as I can tell, orthogonal concepts. Alive claims that this code has UB due to use of gep inbounds: https://alive2.llvm.org/ce/z/zTctIR At the same time, the gep inbounds itself is not poison: https://alive2.llvm.org/ce/z/wxGGyu That makes it looks like Alive also constrains provenance based on gep inbounds, not just the value of the pointer.

Your example just needs reasoning about inbounds. Let's see:

%p.int = ptrtoint i8* %p to i64
%p.neg = sub i64 0, %p.int
%p.null = getelementptr i8, i8* %p, i64 %p.neg
%p.null2 = getelementptr inbounds i8, i8* %p.null, i64 %p.null.neg

gep inbounds requires %p.null to be inbounds, otherwise the result is poison. For %p.null to be inbounds, we need the following (assuming %p has a positive offset to start with):

• %p.neg but be >= 0
• therefore %p.int <= 0
• therefore %p=null

He have established that %p.null2 is either null if %p=null, or poison otherwise. As both can be replaced with null, your example transformation is correct.

If %p was OOB, then its offset might have been negative, for example. But the reasoning is similar to what I wrote above.

[nagisa]

Why is discussion about gepi coming up at all?

This differential, from its description is all about a regular gep, which is currently mis-optimized according to Alive itself. Sure there has been collateral damage from fixing handling of gep, but I think we all agree having a working gep is more important than a very efficient gepi?

(If the fold turns out to be actually valid for gepi, it can be added back just for gepi…)

The only thing missing in this diff from what I can tell is just a regression test…

[nikic]

Rebase over additional tests without inbounds.

[nikic]

Based on what @RalfJung mentioned on zulip, the question of whether the transform is legal for inbounds comes down to the particular choice of inbounds semantics. I was using the semantics specified in LangRef, which make the optimization illegal, while @nlopes used the semantics from https://people.mpi-sws.org/~jung/twinsem/twinsem.pdf (or something similar), which makes it legal. The relevant difference to the LangRef semantics (if we stick to the gep-inbounds-logical case) would be:

- The base pointer has an in bounds address of an allocated object [...]
+ The base pointer has an in bounds address of the allocated object it is based on [...]

In any case, regardless of whether this is legal for the inbounds case, I think everyone agrees it's not legal for the non-inbounds case (and not legal for the non-null case regardless of inbounds). Is that enough to move forward here, or do you want me to thread inbounds information through SimplifyGEPInst and retain this optimization for the inbounds case?

[nlopes]

In D93820#2489066, @nikic wrote:

Based on what @RalfJung mentioned on zulip, the question of whether the transform is legal for inbounds comes down to the particular choice of inbounds semantics. I was using the semantics specified in LangRef, which make the optimization illegal, while @nlopes used the semantics from https://people.mpi-sws.org/~jung/twinsem/twinsem.pdf (or something similar), which makes it legal. The relevant difference to the LangRef semantics (if we stick to the gep-inbounds-logical case) would be:

- The base pointer has an in bounds address of an allocated object [...]
+ The base pointer has an in bounds address of the allocated object it is based on [...]

In any case, regardless of whether this is legal for the inbounds case, I think everyone agrees it's not legal for the non-inbounds case (and not legal for the non-null case regardless of inbounds). Is that enough to move forward here, or do you want me to thread inbounds information through SimplifyGEPInst and retain this optimization for the inbounds case?

LGTM, it's a step in the right direction (removing wrong optimizations)!

[RalfJung]

+ The base pointer has an in bounds address of the allocated object it is based on [...]

It's slightly more tricky than this. A wrong GEPi doesn't always immediately produce poison; instead it records (in the provenance) which offsets all have to be inbounds and then when a load/store happens, it causes UB if any of these offsets is not inbounds. So there are "doomed" pointers (that cause UB when dereferenced) that are not poison. They cannot be optimized to poison since they can still be legally used e.g. in "icmp".

All this is necessary since LLVM considers both inttoptr and GEPi pure operations that it will reorder across anything. To determine "the allocated object it (the pointer) is based on" we'd have to look up in memory which allocated object corresponds to this integer address, but that would make the operation impure and make the reorderings wrong. So instead determining which allocated object this ptr is based on is delayed until the next memory access.

I think everyone agrees it's not legal for the non-inbounds case (and not legal for the non-null case regardless of inbounds)

For non-inbounds, I agree that "folding gep p, q-p to q is only legal if p and q have the same provenance" (so, barely ever).

I didn't entirely follow the "inbounds" arguments here, but I am happy to leave that to y'all. ;)

llvm/lib/Analysis/InstructionSimplify.cpp

if (!IsScalableVec && Ty->isSized()) {
       // getelementptr P, N -> P if P points to a type of zero size.
       if (TyAllocSize == 0 && Ops[0]->getType() == GEPTy)
         return Ops[0];
 
       // The following transforms are only safe if the ptrtoint cast
       // doesn't truncate the pointers.
       if (Ops[1]->getType()->getScalarSizeInBits() ==
           Q.DL.getPointerSizeInBits(AS)) {
-        auto PtrToIntOrZero = [GEPTy](Value *P) -> Value * {
-          if (match(P, m_Zero()))
-            return Constant::getNullValue(GEPTy);
+        auto PtrToInt = [GEPTy](Value *P) -> Value * {
           Value *Temp;
           if (match(P, m_PtrToInt(m_Value(Temp))))
             if (Temp->getType() == GEPTy)
               return Temp;
           return nullptr;
         };
 
+        // FIXME: The following transforms are only legal if P and V have the
+        // same provenance (PR44403). Check whether getUnderlyingObject() is
+        // the same?
+
         // getelementptr V, (sub P, V) -> P if P points to a type of size 1.
         if (TyAllocSize == 1 &&
             match(Ops[1], m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0])))))
-          if (Value *R = PtrToIntOrZero(P))
+          if (Value *R = PtrToInt(P))
             return R;
 
         // getelementptr V, (ashr (sub P, V), C) -> Q
         // if P points to a type of size 1 << C.
         if (match(Ops[1],
                   m_AShr(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
                          m_ConstantInt(C))) &&
             TyAllocSize == 1ULL << C)
-          if (Value *R = PtrToIntOrZero(P))
+          if (Value *R = PtrToInt(P))
             return R;
 
         // getelementptr V, (sdiv (sub P, V), C) -> Q
         // if P points to a type of size C.
         if (match(Ops[1],
                   m_SDiv(m_Sub(m_Value(P), m_PtrToInt(m_Specific(Ops[0]))),
                          m_SpecificInt(TyAllocSize))))
-          if (Value *R = PtrToIntOrZero(P))
+          if (Value *R = PtrToInt(P))
             return R;
       }
     }
   }
 
   if (!IsScalableVec && Q.DL.getTypeAllocSize(LastType) == 1 &&
       all_of(Ops.slice(1).drop_back(1),
              [](Value *Idx) { return match(Idx, m_Zero()); })) {
     unsigned IdxWidth =
         Q.DL.getIndexSizeInBits(Ops[0]->getType()->getPointerAddressSpace());
     if (Q.DL.getTypeSizeInBits(Ops.back()->getType()) == IdxWidth) {
       APInt BasePtrOffset(IdxWidth, 0);
       Value *StrippedBasePtr =
           Ops[0]->stripAndAccumulateInBoundsConstantOffsets(Q.DL,
                                                             BasePtrOffset);
 
+      // Avoid creating inttoptr of zero here: While LLVMs treatment of
+      // inttoptr is generally conservative, this particular case is folded to
+      // a null pointer, which will have incorrect provenance.
+
       // gep (gep V, C), (sub 0, V) -> C
       if (match(Ops.back(),
-                m_Sub(m_Zero(), m_PtrToInt(m_Specific(StrippedBasePtr))))) {
+                m_Sub(m_Zero(), m_PtrToInt(m_Specific(StrippedBasePtr)))) &&
+          !BasePtrOffset.isNullValue()) {
         auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset);
         return ConstantExpr::getIntToPtr(CI, GEPTy);
       }
       // gep (gep V, C), (xor V, -1) -> C-1
       if (match(Ops.back(),
-                m_Xor(m_PtrToInt(m_Specific(StrippedBasePtr)), m_AllOnes()))) {
+                m_Xor(m_PtrToInt(m_Specific(StrippedBasePtr)), m_AllOnes())) &&
+          !BasePtrOffset.isOneValue()) {
         auto *CI = ConstantInt::get(GEPTy->getContext(), BasePtrOffset - 1);
         return ConstantExpr::getIntToPtr(CI, GEPTy);
       }
     }
   }
 
   // Check to see if this is constant foldable.
   if (!all_of(Ops, [](Value *V) { return isa<Constant>(V); }))

llvm/test/Transforms/InstSimplify/gep.ll

;
   %e_ptr = ptrtoint i64* %e to i64
   %b_ptr = ptrtoint i64* %b to i64
   %sub = sub i64 %e_ptr, %b_ptr
   %ashr = ashr exact i64 %sub, 3
   %gep = getelementptr inbounds i64, i64* %b, i64 %ashr
   ret i64* %gep
 }
 
+; The following tests should not be folded to null, because this would
+; lose provenance of the base pointer %b.
+
 define %struct.A* @test4(%struct.A* %b) {
 ; CHECK-LABEL: @test4(
-; CHECK-NEXT:    ret %struct.A* null
+; CHECK-NEXT:    [[B_PTR:%.*]] = ptrtoint %struct.A* [[B:%.*]] to i64
+; CHECK-NEXT:    [[SUB:%.*]] = sub i64 0, [[B_PTR]]
+; CHECK-NEXT:    [[SDIV:%.*]] = sdiv exact i64 [[SUB]], 7
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds [[STRUCT_A:%.*]], %struct.A* [[B]], i64 [[SDIV]]
+; CHECK-NEXT:    ret %struct.A* [[GEP]]
 ;
   %b_ptr = ptrtoint %struct.A* %b to i64
   %sub = sub i64 0, %b_ptr
   %sdiv = sdiv exact i64 %sub, 7
   %gep = getelementptr inbounds %struct.A, %struct.A* %b, i64 %sdiv
   ret %struct.A* %gep
 }
 
 define i8* @test5(i8* %b) {
 ; CHECK-LABEL: @test5(
-; CHECK-NEXT:    ret i8* null
+; CHECK-NEXT:    [[B_PTR:%.*]] = ptrtoint i8* [[B:%.*]] to i64
+; CHECK-NEXT:    [[SUB:%.*]] = sub i64 0, [[B_PTR]]
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[B]], i64 [[SUB]]
+; CHECK-NEXT:    ret i8* [[GEP]]
 ;
   %b_ptr = ptrtoint i8* %b to i64
   %sub = sub i64 0, %b_ptr
   %gep = getelementptr inbounds i8, i8* %b, i64 %sub
   ret i8* %gep
 }
 
 define i64* @test6(i64* %b) {
 ; CHECK-LABEL: @test6(
-; CHECK-NEXT:    ret i64* null
+; CHECK-NEXT:    [[B_PTR:%.*]] = ptrtoint i64* [[B:%.*]] to i64
+; CHECK-NEXT:    [[SUB:%.*]] = sub i64 0, [[B_PTR]]
+; CHECK-NEXT:    [[ASHR:%.*]] = ashr exact i64 [[SUB]], 3
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i64, i64* [[B]], i64 [[ASHR]]
+; CHECK-NEXT:    ret i64* [[GEP]]
 ;
   %b_ptr = ptrtoint i64* %b to i64
   %sub = sub i64 0, %b_ptr
   %ashr = ashr exact i64 %sub, 3
   %gep = getelementptr inbounds i64, i64* %b, i64 %ashr
   ret i64* %gep
 }