[ConstantFold] Don't convert getelementptr to ptrtoint+inttoptr

[nikic]

Summary

ConstantFolding currently converts "getelementptr i8, Ptr, (sub 0, V)" to "inttoptr (sub (ptrtoint Ptr), V)". This transform is, taken by itself, correct, but does came with two issues:

1. It unnecessarily broadens provenance by introducing an inttoptr. We generally prefer not to introduce inttoptr during optimization.
2. For the case where V == ptrtoint Ptr, this folds to inttoptr 0, which further folds to null. In that case provenance becomes incorrect. This has been observed as a real-world miscompile with rustc.

We should probably address that incorrect inttoptr 0 fold at some point, but in either case we should also drop this inttoptr-introducing fold. Instead, replace it with a fold rooted at ptrtoint(getelementptr), which seems to cover the original motivation for this fold (test2 in the changed file).

[nikic]

Rebase over test change.

[nlopes]

Sounds great, thanks! We should avoid introducing ptr2int at all costs.

Note for other reviewers: the new code is covered by existing tests. It's there to avoid regressing on cases where no int2ptr is introduced on new pointers, but we can still get rid of the gep. I think keeping this case is find as it doesn't escape more than the original code.

[tschuett]

llvm/lib/Analysis/ConstantFolding.cpp

879

Could you deprecate or warn on using this expression?

[nlopes]

llvm/lib/Analysis/ConstantFolding.cpp

879

It's not deprecated. It is used. It's just that it should be used as few times as possible.

[aqjune]

I agree that introducing ptrtoint + inttoptr here doesn't sound like a good idea because both it is bad for alias analysis and its correctness is not clear.

For the case where V == ptrtoint Ptr, this folds to inttoptr 0, which further folds to null. In that case provenance becomes incorrect. This has been observed as a real-world miscompile with rustc.

If LLVM is using the definition of null pointer in C, inttoptr 0 must be null, implying that folding gep p, -(ptrtoint p) to null must be the problematic one.

C17, 6.3.2.3.p3. An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.

[aqjune]

This has been observed as a real-world miscompile with rustc.

Could you share a link to the bug report please?

[nikic]

In D124677#3483890, @aqjune wrote:

I agree that introducing ptrtoint + inttoptr here doesn't sound like a good idea because both it is bad for alias analysis and its correctness is not clear.

For the case where V == ptrtoint Ptr, this folds to inttoptr 0, which further folds to null. In that case provenance becomes incorrect. This has been observed as a real-world miscompile with rustc.

If LLVM is using the definition of null pointer in C, inttoptr 0 must be null, implying that folding gep p, -(ptrtoint p) to null must be the problematic one.

C17, 6.3.2.3.p3. An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.

I don't think this follows: This is talking about "integer constant expressions", which are a front-end concern. It means that the front-end is required to match for (void*)0 and emit that as ptr null rather than inttoptr (i64 0 to ptr). At least from that wording, doing int x = 0; (void*)xdoes not result in a null pointer (though possibly other wording implies that?)

I don't think having ptrtoint 1 have universal provenance and ptrtoint 0 have nullary provenance can lead to consistent semantics. It renders many transforms that are "obviously correct" illegal, such as:

define ptr @src(ptr %p, i64 %idx) {
  %p2 = getelementptr i8, ptr %p, i64 %idx
  ret ptr %p2
}
define ptr @tgt(ptr %p, i64 %idx) {
  %p.int = ptrtoint ptr %p to i64
  %p.add = add i64 %p.int, %idx
  %p2 = inttoptr i64 %p.add to ptr
  ret ptr %p2
}

While this transform is very undesirable, it should be correct because it only increases provenance. However, due to the special ptrtoint 0 handling this is incorrect for the special case where p.int == -idx.

In D124677#3483900, @aqjune wrote:

This has been observed as a real-world miscompile with rustc.

Could you share a link to the bug report please?

https://github.com/rust-lang/rust/pull/96538

[aqjune]

In D124677#3483937, @nikic wrote:

In D124677#3483890, @aqjune wrote:

I don't think this follows: This is talking about "integer constant expressions", which are a front-end concern. It means that the front-end is required to match for (void*)0 and emit that as ptr null rather than inttoptr (i64 0 to ptr). At least from that wording, doing int x = 0; (void*)xdoes not result in a null pointer (though possibly other wording implies that?)

I don't think having ptrtoint 1 have universal provenance and ptrtoint 0 have nullary provenance can lead to consistent semantics. It renders many transforms that are "obviously correct" illegal, such as:

define ptr @src(ptr %p, i64 %idx) {
  %p2 = getelementptr i8, ptr %p, i64 %idx
  ret ptr %p2
}
define ptr @tgt(ptr %p, i64 %idx) {
  %p.int = ptrtoint ptr %p to i64
  %p.add = add i64 %p.int, %idx
  %p2 = inttoptr i64 %p.add to ptr
  ret ptr %p2
}

While this transform is very undesirable, it should be correct because it only increases provenance. However, due to the special ptrtoint 0 handling this is incorrect for the special case where p.int == -idx.

One alternative solution is to define a null pointer as having universal provenance.
This is against the LangRef wording A null pointer in the default address-space is associated with no address. (meaning that null + x must not be able to access anything), but explains these:

• Replacing a pointer into NULL is supported because it makes the program more defined.

if (x == null) {
  f(x); -> f(null);
}

• Folding inttoptr 0 to null is naturally explained.

Instead, we will lose optimization opportunities on gep null, x. However, alias analysis can still support gep inbounds null, x because the users of this pointer must ensure that range [null, null+x] are inbounds, and no allocation is located at null.
Therefore, it comes to preserving the flag inbounds as much as possible.

IMO the semantics of NULL pointer is also in the gray area; didn't mean to be against this patch, but wanted to claim that inttoptr 0 -> NULL might be another issue.

llvm/lib/Analysis/ConstantFolding.cpp

if (Constant *C = CastGEPIndices(SrcElemTy, Ops, ResTy,
     return C;
 
   Constant *Ptr = Ops[0];
   if (!Ptr->getType()->isPointerTy())
     return nullptr;
 
   Type *IntIdxTy = DL.getIndexType(Ptr->getType());
 
-  // If this is "gep i8* Ptr, (sub 0, V)", fold this as:
-  // "inttoptr (sub (ptrtoint Ptr), V)"
-  if (Ops.size() == 2 && ResElemTy->isIntegerTy(8)) {
-    auto *CE = dyn_cast<ConstantExpr>(Ops[1]);
-    assert((!CE || CE->getType() == IntIdxTy) &&
-           "CastGEPIndices didn't canonicalize index types!");
-    if (CE && CE->getOpcode() == Instruction::Sub &&
-        CE->getOperand(0)->isNullValue()) {
-      Constant *Res = ConstantExpr::getPtrToInt(Ptr, CE->getType());
-      Res = ConstantExpr::getSub(Res, CE->getOperand(1));
-      Res = ConstantExpr::getIntToPtr(Res, ResTy);
-      return ConstantFoldConstant(Res, DL, TLI);
-    }
-  }
-
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
     if (!isa<ConstantInt>(Ops[i]))
       return nullptr;
 
   unsigned BitWidth = DL.getTypeSizeInBits(IntIdxTy);
   APInt Offset =
       APInt(BitWidth,
             DL.getIndexedOffsetInType(
if (auto *CE = dyn_cast<ConstantExpr>(C)) {
         // (ptrtoint (gep null, x)) -> x
         // (ptrtoint (gep (gep null, x), y) -> x + y, etc.
         unsigned BitWidth = DL.getIndexTypeSizeInBits(GEP->getType());
         APInt BaseOffset(BitWidth, 0);
         auto *Base = cast<Constant>(GEP->stripAndAccumulateConstantOffsets(
             DL, BaseOffset, /*AllowNonInbounds=*/true));
         if (Base->isNullValue()) {
           FoldedValue = ConstantInt::get(CE->getContext(), BaseOffset);
+        } else {
+          // ptrtoint (gep i8, Ptr, (sub 0, V)) -> sub (ptrtoint Ptr), V
+          if (GEP->getNumIndices() == 1 &&
+              GEP->getSourceElementType()->isIntegerTy(8)) {
+            auto *Ptr = cast<Constant>(GEP->getPointerOperand());
+            auto *Sub = dyn_cast<ConstantExpr>(GEP->getOperand(1));
+            Type *IntIdxTy = DL.getIndexType(Ptr->getType());
+            if (Sub && Sub->getType() == IntIdxTy &&
+                Sub->getOpcode() == Instruction::Sub &&
+                Sub->getOperand(0)->isNullValue())
+              FoldedValue = ConstantExpr::getSub(
+                  ConstantExpr::getPtrToInt(Ptr, IntIdxTy), Sub->getOperand(1));
+          }
         }
       }
       if (FoldedValue) {
         // Do a zext or trunc to get to the ptrtoint dest size.
         return ConstantExpr::getIntegerCast(FoldedValue, DestTy,
                                             /*IsSigned=*/false);
       }
     }

llvm/test/Transforms/InstCombine/constant-fold-gep.ll

 @g = external global i8
 @g2 = external global i8
 
 declare i64 @get.i64()
 declare void @use.ptr(i8*)
 
 define i8* @gep_sub_self() {
 ; CHECK-LABEL: @gep_sub_self(
-; CHECK-NEXT:    ret i8* null
+; CHECK-NEXT:    ret i8* getelementptr (i8, i8* @g, i64 sub (i64 0, i64 ptrtoint (i8* @g to i64)))
 ;
   %p.int = ptrtoint i8* @g to i64
   %p.int.neg = sub i64 0, %p.int
   %p1 = getelementptr i8, i8* @g, i64 %p.int.neg
   ret i8* %p1
 }
 
 define i8* @gep_sub_self_plus_addr(i64 %addr) {
 ; CHECK-LABEL: @gep_sub_self_plus_addr(
-; CHECK-NEXT:    [[P2:%.*]] = getelementptr i8, i8* null, i64 [[ADDR:%.*]]
+; CHECK-NEXT:    [[P2:%.*]] = getelementptr i8, i8* getelementptr (i8, i8* @g, i64 sub (i64 0, i64 ptrtoint (i8* @g to i64))), i64 [[ADDR:%.*]]
 ; CHECK-NEXT:    ret i8* [[P2]]
 ;
   %p.int = ptrtoint i8* @g to i64
   %p.int.neg = sub i64 0, %p.int
   %p1 = getelementptr i8, i8* @g, i64 %p.int.neg
   %p2 = getelementptr i8, i8* %p1, i64 %addr
   ret i8* %p2
 }
;
   ret i8* %p2
 }
 
 define i8* @gep_plus_addr_sub_self_in_loop() {
 ; CHECK-LABEL: @gep_plus_addr_sub_self_in_loop(
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[ADDR:%.*]] = call i64 @get.i64()
-; CHECK-NEXT:    [[P2:%.*]] = getelementptr i8, i8* null, i64 [[ADDR]]
+; CHECK-NEXT:    [[P2:%.*]] = getelementptr i8, i8* getelementptr (i8, i8* @g, i64 sub (i64 0, i64 ptrtoint (i8* @g to i64))), i64 [[ADDR]]
 ; CHECK-NEXT:    call void @use.ptr(i8* [[P2]])
 ; CHECK-NEXT:    br label [[LOOP]]
 ;
   %p.int = ptrtoint i8* @g to i64
   %p.int.neg = sub i64 0, %p.int
   br label %loop
 
 loop:
   %addr = call i64 @get.i64()
   %p1 = getelementptr i8, i8* @g, i64 %addr
   %p2 = getelementptr i8, i8* %p1, i64 %p.int.neg
   call void @use.ptr(i8* %p2)
   br label %loop
 }
 
 define i8* @gep_sub_other() {
 ; CHECK-LABEL: @gep_sub_other(
-; CHECK-NEXT:    ret i8* inttoptr (i64 sub (i64 ptrtoint (i8* @g to i64), i64 ptrtoint (i8* @g2 to i64)) to i8*)
+; CHECK-NEXT:    ret i8* getelementptr (i8, i8* @g, i64 sub (i64 0, i64 ptrtoint (i8* @g2 to i64)))
 ;
   %p.int = ptrtoint i8* @g2 to i64
   %p.int.neg = sub i64 0, %p.int
   %p1 = getelementptr i8, i8* @g, i64 %p.int.neg
   ret i8* %p1
 }
 
 define i64 @gep_sub_other_to_int() {