[InstSimplify][InstCombine] Fold ptrtoint(gep i8 null, x) -> x

[arichardson]

Summary

This commit is the InstSimplify follow-up to the previous constant-folding
change that enables noticeable optimizations for CHERI-enabled targets.

We could fold all ptrtoint(inbounds GEP) to zero here since that is the
only valid offset for an inbounds GEP. If the offset is not zero, that GEP
is poison so returning 0 is valid (https://alive2.llvm.org/ce/z/Gzb5iH).
However, Clang currentlygenerates inbounds GEPs on NULL for hand-written
offsetof expressions, so this risks miscompilation.

FIXME: is this transformation also valid for non-integral pointers?

Depends on D110245

[arichardson]

• Use Q.DL.getTypeAllocSize instead of Q.DL.getTypeSizeInBits
• Drop unnecessary code and comments

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

4673

4679

Doesn't this essentially call ->getType() on a pointer?
You can't do that. Perhaps you want getSourceElementType()?

4680

What if it's a constant?

4685

This is surely broken

[arichardson]

• Use isNonIntegralAddressSpace(GEP->getAddressSpace())

[arichardson]

llvm/lib/Analysis/InstructionSimplify.cpp

4680

In that case it should have been handled by D110245? Will add a comment.

4685

In what way? It's here to ensure that the following isn't incorrectly folded to %val:

; We can't fold non-i8 GEPs in InstSimplify since that would require adding new arithmetic.
; TODO: handle this case in InstCombine
define i64 @fold_ptrtoint_nullgep_i32_variable(i64 %val) {
  %ptr = getelementptr i32, i32 addrspace(1)* null, i64 %val
  %ret = ptrtoint i32 addrspace(1)* %ptr to i64
  ret i64 %ret
}

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

4685

Why 8 and not 42?

[arichardson]

• fix getTypeAllocSize

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

4682

https://godbolt.org/z/hTbv3qqGT

[arichardson]

llvm/lib/Analysis/InstructionSimplify.cpp

4682

Sorry, I don't quite understand what this link is showing. The base is not null and there is more than one GEP index so this transformation won't happen.

4685

Good catch, that was a bad copy-paste error from TypeSizeInBits().

If I understand the GEP logic correctly, then TypeAllocSize == 1 implies there is no multiplier and we can therefore return the index unchanged.

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

4682

I'm saying that the precondition you want is that the only non-zero index must be the last one (+ stride check),
not that there must only be a single index.

[arichardson]

llvm/lib/Analysis/InstructionSimplify.cpp

4682

Ah yes of course. Will update the patch. Right now that is only handled by the InstCombine follow-up (D110247)

[arichardson]

• Handle multiple index as long as only the last one is non-zero

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

4681–4685

Can this be something closer to this?
I'm having trouble parsing the current one..

[arichardson]

• Try to increase readability by using llvm::all_of

[lebedev.ri]

LG with nits.
No idea about non-integral pointers.

llvm/lib/Analysis/InstructionSimplify.cpp

4684–4685

Then you might aswell just use the one from C++ STL taking separate begin/end

4687

The LastIndexOp->getType() == Ty check can be done earlier, before all_of check
(or just inline OtherIndicesAllZero variable?)

4688–4691

Again, this seems like a cheaper check that should be done before all_of

[arichardson]

• simplify and reorder to do cheap check first.

[nikic]

I'm not convinced that it makes sense to add this to InstSimplify. This is extra complexity to cover a really narrow subset of what InstCombine will handle anyway. This already seems like quite the edge case fold -- is there some reason to believe that it is critical to handle the "i8 with variable index" special case in InstSimplify?

[arichardson]

In D110246#3018908, @nikic wrote:

I'm not convinced that it makes sense to add this to InstSimplify. This is extra complexity to cover a really narrow subset of what InstCombine will handle anyway. This already seems like quite the edge case fold -- is there some reason to believe that it is critical to handle the "i8 with variable index" special case in InstSimplify?

I think you are right, for us it seems like the most important cases will be handled by constant folding and deferring the rest to InstCombine instead of InstSimplify should address the rest. Will drop this and just focus on the InstCombine fold.

llvm/lib/Analysis/InstructionSimplify.cpp

if (Src->getType() == Ty) {
       if (CastInst::isEliminableCastPair(FirstOp, SecondOp, SrcTy, MidTy, DstTy,
                                          SrcIntPtrTy, MidIntPtrTy,
                                          DstIntPtrTy) == Instruction::BitCast)
         return Src;
     }
   }
 
   // bitcast x -> x
-  if (CastOpc == Instruction::BitCast)
+  if (CastOpc == Instruction::BitCast) {
     if (Op->getType() == Ty)
       return Op;
+  } else if (CastOpc == Instruction::PtrToInt) {
+    // Fold (ptrtoint (gep i8 null, x)) -> x for non-inbounds GEPs.
+    // The GEP simplification will transform all inbounds GEPs with known
+    // non-zero arguments to poison, so we don't have to handle the
+    // non-inbounds case here. We don't perform this fold for non-integral
+    // pointers since the bitwise representation is undefined (even for GEPs
+    // on null).
+    // FIXME: Or is this also valid for non-integral pointers?
+    if (auto *GEP = dyn_cast<GetElementPtrInst>(Op)) {
+      if (isa<ConstantPointerNull>(GEP->getOperand(0)) &&
+          !Q.DL.isNonIntegralPointerType(GEP->getPointerOperandType())) {
+        // FIXME: we could fold all ptrtoint(inbounds GEP) to zero here since
+        // that is the only valid offset for an inbounds GEP. If the offset is
+        // not zero, that GEP is poison so returning 0 is also valid
+        // (https://alive2.llvm.org/ce/z/Gzb5iH). However, Clang currently
+        // generates inbounds GEPs on NULL for hand-written offsetof
+        // expressions, so this risks miscompilation.
+        constexpr bool CanFoldInboundsNullGEPToZero = false;
+        if (CanFoldInboundsNullGEPToZero && GEP->isInBounds()) {
+          return ConstantInt::get(Ty, 0);
+        }
+        // We can't create any zext/trunc instructions here, so this fold is
+        // limited to cases where the result type matches the GEP index type.
+        // We also can't perform the fold if the GEP type is not an i8
+        // More complex cases are handled in InstCombineCompares.cpp.
+        if (GEP->getNumIndices() == 1 && GEP->getOperand(1)->getType() == Ty &&
+            Q.DL.getTypeSizeInBits(GEP->getSourceElementType()) == 8)
+          return GEP->getOperand(1);
+      }
+    }
+  }
 
   return nullptr;
 }
 
 Value *llvm::SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
                               const SimplifyQuery &Q) {
   return ::SimplifyCastInst(CastOpc, Op, Ty, Q, RecursionLimit);
 }

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

Instruction *InstCombinerImpl::visitPtrToInt(PtrToIntInst &CI) {
   unsigned PtrSize = DL.getPointerSizeInBits(AS);
   if (TySize != PtrSize) {
     Type *IntPtrTy =
         SrcTy->getWithNewType(DL.getIntPtrType(CI.getContext(), AS));
     Value *P = Builder.CreatePtrToInt(SrcOp, IntPtrTy);
     return CastInst::CreateIntegerCast(P, Ty, /*isSigned=*/false);
   }
 
+  // TODO: should we call SimplifyCastInst() in commonCastTransforms()?
+  if (Value *V = SimplifyCastInst(CI.getOpcode(), SrcOp, Ty,
+                                  SQ.getWithInstruction(&CI)))
+    return replaceInstUsesWith(CI, V);
+
   Value *Vec, *Scalar, *Index;
   if (match(SrcOp, m_OneUse(m_InsertElt(m_IntToPtr(m_Value(Vec)),
                                         m_Value(Scalar), m_Value(Index)))) &&
       Vec->getType() == Ty) {
     assert(Vec->getType()->getScalarSizeInBits() == PtrSize && "Wrong type");
     // Convert the scalar to int followed by insert to eliminate one cast:
     // p2i (ins (i2p Vec), Scalar, Index --> ins Vec, (p2i Scalar), Index
     Value *NewCast = Builder.CreatePtrToInt(Scalar, Ty->getScalarType());

llvm/test/Transforms/InstCombine/ptrtoint-nullgep.ll

;
   %offset = add i64 1234, 0
   %ptr = getelementptr inbounds i8, i8 addrspace(1)* null, i64 %offset
   %ret = ptrtoint i8 addrspace(1)* %ptr to i64
   ret i64 %ret
 }
 
 ; We should be able to fold ptrtoint(gep null, x) to x
 define i64 @fold_ptrtoint_nullgep_variable(i64 %val) {
-; ALL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable
-; ALL-SAME: (i64 [[VAL:%.*]]) {
-; ALL-NEXT:    [[PTR:%.*]] = getelementptr i8, i8 addrspace(1)* null, i64 [[VAL]]
-; ALL-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
-; ALL-NEXT:    ret i64 [[RET]]
+; LLPARSER-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable
+; LLPARSER-SAME: (i64 [[VAL:%.*]]) {
+; LLPARSER-NEXT:    [[PTR:%.*]] = getelementptr i8, i8 addrspace(1)* null, i64 [[VAL]]
+; LLPARSER-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
+; LLPARSER-NEXT:    ret i64 [[RET]]
+;
+; INTEGRAL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable
+; INTEGRAL-SAME: (i64 [[VAL:%.*]]) {
+; INTEGRAL-NEXT:    ret i64 [[VAL]]
+;
+; NONINTEGRAL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable
+; NONINTEGRAL-SAME: (i64 [[VAL:%.*]]) {
+; NONINTEGRAL-NEXT:    [[PTR:%.*]] = getelementptr i8, i8 addrspace(1)* null, i64 [[VAL]]
+; NONINTEGRAL-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
+; NONINTEGRAL-NEXT:    ret i64 [[RET]]
 ;
   %ptr = getelementptr i8, i8 addrspace(1)* null, i64 %val
   %ret = ptrtoint i8 addrspace(1)* %ptr to i64
   ret i64 %ret
 }
 
 ; Inbounds null-GEP with non-zero offset can be folded to poison.
 define i64 @fold_ptrtoint_nullgep_variable_known_nonzero(i64 %val) {
-; ALL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_known_nonzero
-; ALL-SAME: (i64 [[VAL:%.*]]) {
-; ALL-NEXT:    [[NON_ZERO_OFFSET:%.*]] = or i64 [[VAL]], 1
-; ALL-NEXT:    [[PTR:%.*]] = getelementptr i8, i8 addrspace(1)* null, i64 [[NON_ZERO_OFFSET]]
-; ALL-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
-; ALL-NEXT:    ret i64 [[RET]]
+; LLPARSER-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_known_nonzero
+; LLPARSER-SAME: (i64 [[VAL:%.*]]) {
+; LLPARSER-NEXT:    [[NON_ZERO_OFFSET:%.*]] = or i64 [[VAL]], 1
+; LLPARSER-NEXT:    [[PTR:%.*]] = getelementptr i8, i8 addrspace(1)* null, i64 [[NON_ZERO_OFFSET]]
+; LLPARSER-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
+; LLPARSER-NEXT:    ret i64 [[RET]]
+;
+; INTEGRAL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_known_nonzero
+; INTEGRAL-SAME: (i64 [[VAL:%.*]]) {
+; INTEGRAL-NEXT:    [[NON_ZERO_OFFSET:%.*]] = or i64 [[VAL]], 1
+; INTEGRAL-NEXT:    ret i64 [[NON_ZERO_OFFSET]]
+;
+; NONINTEGRAL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_known_nonzero
+; NONINTEGRAL-SAME: (i64 [[VAL:%.*]]) {
+; NONINTEGRAL-NEXT:    [[NON_ZERO_OFFSET:%.*]] = or i64 [[VAL]], 1
+; NONINTEGRAL-NEXT:    [[PTR:%.*]] = getelementptr i8, i8 addrspace(1)* null, i64 [[NON_ZERO_OFFSET]]
+; NONINTEGRAL-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
+; NONINTEGRAL-NEXT:    ret i64 [[RET]]
 ;
   %non_zero_offset = or i64 %val, 1
   %ptr = getelementptr i8, i8 addrspace(1)* null, i64 %non_zero_offset
   %ret = ptrtoint i8 addrspace(1)* %ptr to i64
   ret i64 %ret
 }
 
 ; This is only valid if %val is zero so we can fold the result to 0.
 define i64 @fold_ptrtoint_nullgep_variable_inbounds(i64 %val) {
-; ALL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_inbounds
-; ALL-SAME: (i64 [[VAL:%.*]]) {
-; ALL-NEXT:    [[PTR:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* null, i64 [[VAL]]
-; ALL-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
-; ALL-NEXT:    ret i64 [[RET]]
+; LLPARSER-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_inbounds
+; LLPARSER-SAME: (i64 [[VAL:%.*]]) {
+; LLPARSER-NEXT:    [[PTR:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* null, i64 [[VAL]]
+; LLPARSER-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
+; LLPARSER-NEXT:    ret i64 [[RET]]
+;
+; INTEGRAL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_inbounds
+; INTEGRAL-SAME: (i64 [[VAL:%.*]]) {
+; INTEGRAL-NEXT:    ret i64 [[VAL]]
+;
+; NONINTEGRAL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_inbounds
+; NONINTEGRAL-SAME: (i64 [[VAL:%.*]]) {
+; NONINTEGRAL-NEXT:    [[PTR:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* null, i64 [[VAL]]
+; NONINTEGRAL-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
+; NONINTEGRAL-NEXT:    ret i64 [[RET]]
 ;
   %ptr = getelementptr inbounds i8, i8 addrspace(1)* null, i64 %val
   %ret = ptrtoint i8 addrspace(1)* %ptr to i64
   ret i64 %ret
 }
 
 ; A non-constant but known-non-zero GEP should fold to poison
 define i64 @fold_ptrtoint_nullgep_variable_known_nonzero_inbounds(i64 %val) {
-; ALL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_known_nonzero_inbounds
-; ALL-SAME: (i64 [[VAL:%.*]]) {
-; ALL-NEXT:    [[NON_ZERO_OFFSET:%.*]] = or i64 [[VAL]], 1
-; ALL-NEXT:    [[PTR:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* null, i64 [[NON_ZERO_OFFSET]]
-; ALL-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
-; ALL-NEXT:    ret i64 [[RET]]
+; LLPARSER-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_known_nonzero_inbounds
+; LLPARSER-SAME: (i64 [[VAL:%.*]]) {
+; LLPARSER-NEXT:    [[NON_ZERO_OFFSET:%.*]] = or i64 [[VAL]], 1
+; LLPARSER-NEXT:    [[PTR:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* null, i64 [[NON_ZERO_OFFSET]]
+; LLPARSER-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
+; LLPARSER-NEXT:    ret i64 [[RET]]
+;
+; INTEGRAL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_known_nonzero_inbounds
+; INTEGRAL-SAME: (i64 [[VAL:%.*]]) {
+; INTEGRAL-NEXT:    [[NON_ZERO_OFFSET:%.*]] = or i64 [[VAL]], 1
+; INTEGRAL-NEXT:    ret i64 [[NON_ZERO_OFFSET]]
+;
+; NONINTEGRAL-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_known_nonzero_inbounds
+; NONINTEGRAL-SAME: (i64 [[VAL:%.*]]) {
+; NONINTEGRAL-NEXT:    [[NON_ZERO_OFFSET:%.*]] = or i64 [[VAL]], 1
+; NONINTEGRAL-NEXT:    [[PTR:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* null, i64 [[NON_ZERO_OFFSET]]
+; NONINTEGRAL-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
+; NONINTEGRAL-NEXT:    ret i64 [[RET]]
 ;
   %non_zero_offset = or i64 %val, 1
   %ptr = getelementptr inbounds i8, i8 addrspace(1)* null, i64 %non_zero_offset
   %ret = ptrtoint i8 addrspace(1)* %ptr to i64
   ret i64 %ret
 }
 
 ; A non-constant but known-non-zero GEP should fold to poison

 ; LLPARSER-NEXT:    ret i32 [[RET]]
 ;
 ; INSTSIMPLIFY-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_trunc
 ; INSTSIMPLIFY-SAME: (i64 [[VAL:%.*]]) {
 ; INSTSIMPLIFY-NEXT:    [[PTR:%.*]] = getelementptr i8, i8 addrspace(1)* null, i64 [[VAL]]
 ; INSTSIMPLIFY-NEXT:    [[RET:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i32
 ; INSTSIMPLIFY-NEXT:    ret i32 [[RET]]
 ;
-; INSTCOMBINE-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_trunc
-; INSTCOMBINE-SAME: (i64 [[VAL:%.*]]) {
-; INSTCOMBINE-NEXT:    [[PTR:%.*]] = getelementptr i8, i8 addrspace(1)* null, i64 [[VAL]]
-; INSTCOMBINE-NEXT:    [[TMP1:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
-; INSTCOMBINE-NEXT:    [[RET:%.*]] = trunc i64 [[TMP1]] to i32
-; INSTCOMBINE-NEXT:    ret i32 [[RET]]
+; INTEGRAL-INSTCOMBINE-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_trunc
+; INTEGRAL-INSTCOMBINE-SAME: (i64 [[VAL:%.*]]) {
+; INTEGRAL-INSTCOMBINE-NEXT:    [[RET:%.*]] = trunc i64 [[VAL]] to i32
+; INTEGRAL-INSTCOMBINE-NEXT:    ret i32 [[RET]]
+;
+; NONINTEGRAL-INSTCOMBINE-LABEL: define {{[^@]+}}@fold_ptrtoint_nullgep_variable_trunc
+; NONINTEGRAL-INSTCOMBINE-SAME: (i64 [[VAL:%.*]]) {
+; NONINTEGRAL-INSTCOMBINE-NEXT:    [[PTR:%.*]] = getelementptr i8, i8 addrspace(1)* null, i64 [[VAL]]
+; NONINTEGRAL-INSTCOMBINE-NEXT:    [[TMP1:%.*]] = ptrtoint i8 addrspace(1)* [[PTR]] to i64
+; NONINTEGRAL-INSTCOMBINE-NEXT:    [[RET:%.*]] = trunc i64 [[TMP1]] to i32
+; NONINTEGRAL-INSTCOMBINE-NEXT:    ret i32 [[RET]]
 ;
   %ptr = getelementptr i8, i8 addrspace(1)* null, i64 %val
   %ret = ptrtoint i8 addrspace(1)* %ptr to i32
   ret i32 %ret
 }
 
 ; For the following three tests, we should fold the result to poison since there is at least
 ; one inbounds GEP on null with a non-zero offset. This was previously folded to 1234