[InstCombine] Fold phi ( inttoptr/ptrtoint x ) to phi (x)

[Krishnakariya]

Summary

The inttoptr/ptrtoint roundtrip optimization is not always correct.
We are working towards removing this optimization and adding support to specific cases where this optimization works.

In this patch, we focus on phi-node operands with inttoptr casts.
We know that ptrtoint( inttoptr( ptrtoint x) ) is same as ptrtoint (x).
So, we want to remove this roundtrip cast which goes through phi-node.

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

324

Should we exclude cases where input pointers have different types?
After opaque pointers are introduced everything will be fine - it is a safeguard that will work until then.

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

324

For example:

p = phi i64 [ ptrtoint i8* %a, BB1 ], [ ptrtoint float* %b, BB2 ]
i = inttoptr p

[Krishnakariya]

Added a test for different input pointer types (func_pointer_different_types).

[aqjune]

I have a question about addrspacecast: is ptrtoint(inttoptr(ptrtoint pty1 p) to pty2) equivalent to ptrtoint(addrspacecast pty1 p to pty2)?
Does anyone have idea about this?

[lebedev.ri]

In D106289#2916089, @aqjune wrote:

I have a question about addrspacecast: is ptrtoint(inttoptr(ptrtoint pty1 p) to pty2) equivalent to ptrtoint(addrspacecast pty1 p to pty2)?
Does anyone have idea about this?

I'm going to guess no. inttoptr/ptrtoint are essentially no-op bitcasts,
while addrspacecast is implementation-defined and in general case can be assumed to e.g. offset the pointer.

[aqjune]

In D106289#2916096, @lebedev.ri wrote:

In D106289#2916089, @aqjune wrote:

I have a question about addrspacecast: is ptrtoint(inttoptr(ptrtoint pty1 p) to pty2) equivalent to ptrtoint(addrspacecast pty1 p to pty2)?
Does anyone have idea about this?

I'm going to guess no. inttoptr/ptrtoint are essentially no-op bitcasts,
while addrspacecast is implementation-defined and in general case can be assumed to e.g. offset the pointer.

Oh, thanks. @Krishnakariya does this patch deal with the case?

[Krishnakariya]

Yes, it handles this case. I have added a new test for the same.

[aqjune]

LGTM.

[aqjune]

I left a few nitpicks that is probably worth addressed

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

306

You can do this folding when PN has multiple uses all of which are ptrtoint as well.

334

Is there a reason why a new phi is created?
Would replacing the corresponding op with the optimized pointer be enough?

[Krishnakariya]

Simplified code.

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

307

Perhaps there was llvm::all_of that can take this loop body as lambda. Let's use it to simplify this further.

1344

I think you'll need to return &PN if it was updated:

if (foldPHIArgIntToPtrToPHI(PN))
  return &PN;

[Krishnakariya]

[Krishnakariya]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

307

Thanks, I have updated the patch.

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   /// second operand.
   Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
 
   /// This is a convenience wrapper function for the above two functions.
   Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
 
   Instruction *foldAddWithConstant(BinaryOperator &Add);
 
   /// Try to rotate an operation below a PHI node, using PHI nodes for
   /// its operands.
   Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
   Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
   Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
   Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
   Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
   Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
   Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
+  Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);  
 
   /// If an integer typed PHI has only one use which is an IntToPtr operation,
   /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
   /// insert a new pointer typed PHI and replace the original one.
   Instruction *foldIntegerTypedPHI(PHINode &PN);
 
   /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
   /// folded operation.

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

#endif
     NewPtrPHI->addIncoming(CI, IncomingBB);
   }
 
   // The PtrToCast + IntToPtr will be simplified later
   return CastInst::CreateBitOrPointerCast(NewPtrPHI,
                                           IntToPtr->getOperand(0)->getType());
 }
 
+// Remove RoundTrip IntToPtr/PtrToInt Cast on PHI-Operand and
+// fold Phi-operand to bitcast.
+Instruction *InstCombinerImpl::foldPHIArgIntToPtrToPHI(PHINode &PN) {
+  // convert ptr2int ( phi[ int2ptr(ptr2int(x))] ) --> ptr2int ( phi [ x ] )
+  if (!PN.hasOneUse())
+    return nullptr;
+
+  if (!(dyn_cast<PtrToIntInst>(*(PN.user_begin()))))
+    return nullptr;
+
+  SmallVector<Value *, 4> NewIncomingValueForPhi(PN.incoming_values().begin(),
+                                                 PN.incoming_values().end());
+  bool OperandWithRoundTripCast = false;
+
+  // Iterating over all operands to check presence of target pointers for
+  // optimization.
+  for (unsigned  OpNum = 0; OpNum != PN.getNumIncomingValues(); ++OpNum) {
+    if (auto *NewOp = simplifyIntToPtrRoundTripCast(PN.getIncomingValue(OpNum))) {
+      NewIncomingValueForPhi[OpNum] = NewOp;
+      OperandWithRoundTripCast = true;
+    }
+  }
+  if (!OperandWithRoundTripCast)
+    return nullptr;
+
+  // Create a new PHI Node to receive the values of new operands.
+  PHINode *NewPtrPhi =
+      PHINode::Create(PN.getType(), PN.getNumIncomingValues(), PN.getName());
+  for (unsigned OpNum = 0; OpNum != PN.getNumIncomingValues(); ++OpNum) {
+    NewPtrPhi->addIncoming(NewIncomingValueForPhi[OpNum], PN.getIncomingBlock(OpNum));
+  }
+  PHIArgMergedDebugLoc(NewPtrPhi, PN);
+  return NewPtrPhi;
+}
+
 /// If we have something like phi [insertvalue(a,b,0), insertvalue(c,d,0)],
 /// turn this into a phi[a,c] and phi[b,d] and a single insertvalue.
 Instruction *
 InstCombinerImpl::foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN) {
   auto *FirstIVI = cast<InsertValueInst>(PN.getIncomingValue(0));
 
   // Scan to see if all operands are `insertvalue`'s with the same indicies,
   // and all have a single use.

 //
 Instruction *InstCombinerImpl::visitPHINode(PHINode &PN) {
   if (Value *V = SimplifyInstruction(&PN, SQ.getWithInstruction(&PN)))
     return replaceInstUsesWith(PN, V);
 
   if (Instruction *Result = foldPHIArgZextsIntoPHI(PN))
     return Result;
 
   // If all PHI operands are the same operation, pull them through the PHI,
   // reducing code size.
   if (isa<Instruction>(PN.getIncomingValue(0)) &&
       isa<Instruction>(PN.getIncomingValue(1)) &&
       cast<Instruction>(PN.getIncomingValue(0))->getOpcode() ==
           cast<Instruction>(PN.getIncomingValue(1))->getOpcode() &&
       PN.getIncomingValue(0)->hasOneUser())
     if (Instruction *Result = foldPHIArgOpIntoPHI(PN))
       return Result;
Instruction *InstCombinerImpl::visitPHINode(PHINode &PN) {
 
   // If this is a trivial cycle in the PHI node graph, remove it.  Basically, if
   // this PHI only has a single use (a PHI), and if that PHI only has one use (a
   // PHI)... break the cycle.
   if (PN.hasOneUse()) {
     if (Instruction *Result = foldIntegerTypedPHI(PN))
       return Result;
 
+    if (Instruction *Result = foldPHIArgIntToPtrToPHI(PN))
+      return Result;
+
     Instruction *PHIUser = cast<Instruction>(PN.user_back());
     if (PHINode *PU = dyn_cast<PHINode>(PHIUser)) {
       SmallPtrSet<PHINode*, 16> PotentiallyDeadPHIs;
       PotentiallyDeadPHIs.insert(&PN);
       if (DeadPHICycle(PU, PotentiallyDeadPHIs))
         return replaceInstUsesWith(PN, PoisonValue::get(PN.getType()));
     }
 

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

if (IntToPtr && DL.getPointerTypeSizeInBits(IntToPtr->getDestTy()) ==
                       DL.getTypeSizeInBits(IntToPtr->getSrcTy())) {
     auto *PtrToInt = dyn_cast<PtrToIntInst>(IntToPtr->getOperand(0));
     Type *CastTy = IntToPtr->getDestTy();
     if (PtrToInt &&
         CastTy->getPointerAddressSpace() ==
             PtrToInt->getSrcTy()->getPointerAddressSpace() &&
         DL.getPointerTypeSizeInBits(PtrToInt->getSrcTy()) ==
             DL.getTypeSizeInBits(PtrToInt->getDestTy())) {
-      return Builder.CreateBitCast(PtrToInt->getOperand(0), CastTy);
+      return CastInst::CreateBitOrPointerCast(PtrToInt->getOperand(0), CastTy,
+                                              "", PtrToInt);
     }
   }
   return nullptr;
 }
 
 /// This performs a few simplifications for operators that are associative or
 /// commutative:
 ///

llvm/test/Transforms/InstCombine/phi-int2ptr-fold.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -instcombine -S -disable-i2p-p2i-opt < %s | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; convert ptrtoint [ phi[ inttoptr (ptrtoint (x) ) ] ---> ptrtoint (phi[x])
+
+define i64 @func(i32** %X, i32** %Y, i1 %cond) {
+; CHECK-LABEL: @func(
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[PHI_IN_IN:%.*]] = phi i32** [ [[X:%.*]], [[BB1]] ], [ [[Y:%.*]], [[BB2]] ]
+; CHECK-NEXT:    [[PHI_IN:%.*]] = ptrtoint i32** [[PHI_IN_IN]] to i64
+; CHECK-NEXT:    ret i64 [[PHI_IN]]
+;
+  br i1 %cond, label %bb1, label %bb2
+
+bb1:
+  %X.i = ptrtoint i32** %X to i64
+  %X.p = inttoptr i64 %X.i to i32*
+  br label %exit
+
+bb2:
+  %Y.i = ptrtoint i32** %Y to i64
+  %Y.p = inttoptr i64 %Y.i to i32*
+  br label %exit
+
+exit:
+  %phi = phi i32* [%X.p, %bb1], [%Y.p, %bb2]
+  %X.p.i = ptrtoint i32* %phi to i64
+  ret i64 %X.p.i
+}
+
+define i64 @func_single_operand(i32** %X, i32** %Y, i1 %cond) {
+; CHECK-LABEL: @func_single_operand(
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[PHI_IN:%.*]] = phi i32** [ [[X:%.*]], [[BB1]] ], [ [[Y:%.*]], [[TMP0:%.*]] ]
+; CHECK-NEXT:    [[X_P_I:%.*]] = ptrtoint i32** [[PHI_IN]] to i64
+; CHECK-NEXT:    ret i64 [[X_P_I]]
+;
+  %Y.p = bitcast i32** %Y to i32*
+  br i1 %cond, label %bb1, label %exit
+
+bb1:
+  %X.i = ptrtoint i32** %X to i64
+  %X.p = inttoptr i64 %X.i to i32*
+  br label %exit
+
+exit:
+  %phi = phi i32* [%X.p, %bb1], [%Y.p, %0]
+  %X.p.i = ptrtoint i32* %phi to i64
+  ret i64 %X.p.i
+}
+
+; Negative test - Wrong Integer type
+
+define i64 @func_integer_type_too_small(i32** %X, i32** %Y, i1 %cond) {
+; CHECK-LABEL: @func_integer_type_too_small(
+; CHECK-NEXT:    [[Y_P:%.*]] = bitcast i32** [[Y:%.*]] to i32*
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP1:%.*]] = ptrtoint i32** [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], 4294967295
+; CHECK-NEXT:    [[X_P:%.*]] = inttoptr i64 [[TMP2]] to i32*
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32* [ [[X_P]], [[BB1]] ], [ [[Y_P]], [[TMP0:%.*]] ]
+; CHECK-NEXT:    [[X_P_I:%.*]] = ptrtoint i32* [[PHI]] to i64
+; CHECK-NEXT:    ret i64 [[X_P_I]]
+;
+  %Y.p = bitcast i32** %Y to i32*
+  br i1 %cond, label %bb1, label %exit
+
+bb1:
+  %X.i = ptrtoint i32** %X to i32
+  %X.p = inttoptr i32 %X.i to i32*
+  br label %exit
+
+exit:
+  %phi = phi i32* [%X.p, %bb1], [%Y.p, %0]
+  %X.p.i = ptrtoint i32* %phi to i64
+  ret i64 %X.p.i
+}
+
+; Negative test - phi not used in ptrtoint
+
+define i32* @func_phi_not_use_in_ptr2int(i32** %X, i32** %Y, i1 %cond) {
+; CHECK-LABEL: @func_phi_not_use_in_ptr2int(
+; CHECK-NEXT:    [[Y_P:%.*]] = bitcast i32** [[Y:%.*]] to i32*
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[EXIT:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP1:%.*]] = ptrtoint i32** [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], 4294967295
+; CHECK-NEXT:    [[X_P:%.*]] = inttoptr i64 [[TMP2]] to i32*
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32* [ [[X_P]], [[BB1]] ], [ [[Y_P]], [[TMP0:%.*]] ]
+; CHECK-NEXT:    ret i32* [[PHI]]
+;
+  %Y.p = bitcast i32** %Y to i32*
+  br i1 %cond, label %bb1, label %exit
+
+bb1:
+  %X.i = ptrtoint i32** %X to i32
+  %X.p = inttoptr i32 %X.i to i32*
+  br label %exit
+
+exit:
+  %phi = phi i32* [%X.p, %bb1], [%Y.p, %0]
+  ret i32* %phi
+}