[InstCombine] Fold Int2Ptr/PtrToInt if the ptr is dereferenceable

[Krishnakariya]

Summary

In this patch, we remove the int2ptr [ptr2int (p)] if p is dereferenceable.
If the user of the round-trip cast is dominated by a load/store instruction of the same address, then we
can replace round-trip cast with bitcast.

[Krishnakariya]

Modified code and Added new tests

[Krishnakariya]

updated

[Krishnakariya]

updated.

[Krishnakariya]

ping

[aqjune]

Hi,

I became to wonder what happens if a pointer is freed in the function.
For example:

// assume that %p is dereferenceable(8)
call void @g(%p);
%q = inttoptr (ptrtoint %p);
use(%q); // can we replace this with %p?

I guess the answer is no, because if @g freed %p and allocated an object at %p's location, replacing inttoptr(ptrtoint %p) with %p makes the program more undefined.

Is the semantics of dereferenceable(8) %p implying %p must not be freed in the function as well?
If it isn't I think we should check whether nofree flag is attached to the functions (@test, @test1, ...) as well.

[nlopes]

In D107822#2953955, @aqjune wrote:

Hi,

I became to wonder what happens if a pointer is freed in the function.
For example:

// assume that %p is dereferenceable(8)
call void @g(%p);
%q = inttoptr (ptrtoint %p);
use(%q); // can we replace this with %p?

I guess the answer is no, because if @g freed %p and allocated an object at %p's location, replacing inttoptr(ptrtoint %p) with %p makes the program more undefined.

Is the semantics of dereferenceable(8) %p implying %p must not be freed in the function as well?
If it isn't I think we should check whether nofree flag is attached to the functions (@test, @test1, ...) as well.

I agree with you, but this is a bug in isDereferenceableAndAlignedPointer. This API should receive the instruction where we want to prove the ptr is dereferenceable and take care of free, etc.
So I would not block this patch on this.

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

348

Then, what do you think about adding a nofree check at this point? @nlopes

Let's check whether CI's function has a nofree attribute. The checking will be fairly simple.

define void @test(i8* %X, i8* %Y, i8* %Z) *nofree* {
...
}

[lebedev.ri]

The code here looks very weird.
Please can you at least split this up into a preparatory NFC changes, the deref-based fold, and the domination-based fold?
Also, please precommit the tests, even if just locally for you, so that the patches show how the check lines change.

[nlopes]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

348

Well, nofree is still not very common. Which would render this optimization useless. Plus it would be unnecessary (and restrictive) to check once isDereferenceableAndAlignedPointer is fixed.
Maybe what we need is a bug report for isDereferenceableAndAlignedPointer as it seems Philip abandoned the work on nofree.

[aqjune]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

348

Okay, then I'm fine with the code leaving as it is here.
Could you split this patch into three as suggested by Lebedev? @Krishnakariya

[Krishnakariya]

Updated diff

[Krishnakariya]

In D107822#2956860, @lebedev.ri wrote:

The code here looks very weird.
Please can you at least split this up into a preparatory NFC changes, the deref-based fold, and the domination-based fold?
Also, please precommit the tests, even if just locally for you, so that the patches show how the check lines change.

Splited this patch into 3 parts: D108504 (NFC), D108506 (deref-based fold), and this one (dominator-based fold). Added precommit tests also.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

 //===- InstCombineCasts.cpp -----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visit functions for cast operations.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Transforms/InstCombine/InstCombiner.h"
 #include <numeric>
 using namespace llvm;
if (match(Src, m_OneUse(m_Shuffle(m_Value(X), m_Undef(), m_Mask(Mask))))) {
     if (SrcTy && DestTy &&
         SrcTy->getNumElements() == DestTy->getNumElements() &&
         SrcTy->getPrimitiveSizeInBits() == DestTy->getPrimitiveSizeInBits()) {
       Value *CastX = Builder.CreateCast(CI.getOpcode(), X, DestTy);
       return new ShuffleVectorInst(CastX, UndefValue::get(DestTy), Mask);
     }
   }
 
+  // Replace Int2Ptr/Ptr2Int RoundTrip Cast with bitcast if the pointer
+  // is dereferenceable.
+  Value *Ptr = isIntToPtrRoundTripCast(&CI);
+  if (Ptr) {
+    if (isDereferenceableAndAlignedPointer(Ptr, Align(1), APInt(64, 1), DL)) {
+      return new BitCastInst(Ptr, CI.getDestTy());
+    }
+    // Vector to find out all target users of roundtrip (int2ptr/ptr2int) cast
+    // which are dominated by load/store instruction of same address as of
+    // roundtripcast.
+    SmallVector<User *> TargetUsers;
+    Instruction *I;
+    for (auto *CU : CI.users()) {
+      if (!(I = dyn_cast<Instruction>(CU))) {
+        continue;
+      }
+      int NumIterations = 0;
+      for (auto *U : Ptr->users()) {
+        NumIterations++;
+        if ((isa<LoadInst>(U) || isa<StoreInst>(U)) &&
+            (DT.dominates(cast<Instruction>(U), I))) {
+          TargetUsers.push_back(CU);
+          break;
+        }
+        if (NumIterations == 10) {
+          goto DoneWithUsers;
+        }
+      }
+    }
+  DoneWithUsers:
+    if (!TargetUsers.empty()) {
+      Value *BitCast = Builder.CreateBitCast(Ptr, CI.getDestTy());
+      for (auto *U : TargetUsers) {
+        U->replaceUsesOfWith(&CI, BitCast);
+      }
+      return &CI;
+    }
+  }
   return nullptr;
 }
 
 /// Constants and extensions/truncates from the destination type are always
 /// free to be evaluated in that type. This is a helper for canEvaluate*.
 static bool canAlwaysEvaluateInType(Value *V, Type *Ty) {
   if (isa<Constant>(V))
     return true;

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
   /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
   /// Instruction::CastOps value for a cast that can replace the pair, casting
   /// CI1->getSrcTy() to CI2->getDstTy().
   ///
   /// \see CastInst::isEliminableCastPair
   Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
                                             const CastInst *CI2);
   Value *simplifyIntToPtrRoundTripCast(Value *Val);
+  Value *isIntToPtrRoundTripCast(Value *Val);
 
   Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &And);
   Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Or);
   Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
 
   /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
   /// NOTE: Unlike most of instcombine, this returns a Value which should
   /// already be inserted into the function.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

static bool simplifyAssocCastAssoc(BinaryOperator *BinOp1,
   IC.replaceOperand(*Cast, 0, BinOp2->getOperand(0));
   IC.replaceOperand(*BinOp1, 1, FoldedC);
   return true;
 }
 
 // Simplifies IntToPtr/PtrToInt RoundTrip Cast To BitCast.
 // inttoptr ( ptrtoint (x) ) --> x
 Value *InstCombinerImpl::simplifyIntToPtrRoundTripCast(Value *Val) {
+  if (Value *Ptr = isIntToPtrRoundTripCast(Val)) {
+    return CastInst::CreateBitOrPointerCast(Ptr, Val->getType(), "",
+                                            cast<Instruction>(Val));
+  }
+  return nullptr;
+}
+
+Value *InstCombinerImpl::isIntToPtrRoundTripCast(Value *Val) {
   auto *IntToPtr = dyn_cast<IntToPtrInst>(Val);
   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 CastInst::CreateBitOrPointerCast(PtrToInt->getOperand(0), CastTy,
-                                              "", PtrToInt);
+      return PtrToInt->getOperand(0);
     }
   }
   return nullptr;
 }
 
 /// This performs a few simplifications for operators that are associative or
 /// commutative:
 ///

llvm/test/Transforms/InstCombine/load-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-p:64:64-p1:16:16-p2:32:32:32-p3:64:64:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test(i8* %X, i8* %Y, i8* %Z) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:    [[XVAL:%.*]] = load i8, i8* [[X:%.*]], align 1
+; CHECK-NEXT:    [[YVAL:%.*]] = load i8, i8* [[Y:%.*]], align 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[XVAL]], [[YVAL]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[CALL:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[Z_I:%.*]] = ptrtoint i8* [[Z:%.*]] to i64
+; CHECK-NEXT:    [[Z_P:%.*]] = inttoptr i64 [[Z_I]] to i8*
+; CHECK-NEXT:    br label [[CALL]]
+; CHECK:       call:
+; CHECK-NEXT:    [[PHI_1:%.*]] = phi i8* [ [[Z_P]], [[IF_ELSE]] ], [ [[Y]], [[IF_THEN]] ]
+; CHECK-NEXT:    [[PHI_2:%.*]] = phi i8* [ [[Z_P]], [[IF_ELSE]] ], [ [[X]], [[IF_THEN]] ]
+; CHECK-NEXT:    tail call void @foo(i8* [[PHI_1]], i8* [[PHI_2]])
+; CHECK-NEXT:    ret void
+;
+  %Xval = load i8, i8* %X
+  %Yval = load i8, i8* %Y
+  %cmp  = icmp slt i8 %Xval, %Yval
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %Y.i = ptrtoint i8* %Y to i64
+  %Y.p = inttoptr i64 %Y.i to i8*
+  %X.i = ptrtoint i8* %X to i64
+  %X.p = inttoptr i64 %X.i to i8*
+  br label %call
+
+if.else:
+  %Z.i = ptrtoint i8* %Z to i64
+  %Z.p = inttoptr i64 %Z.i to i8*
+  br label %call
+
+call:
+  %phi.1 = phi i8* [ %Z.p, %if.else ], [ %Y.p, %if.then ]
+  %phi.2 = phi i8* [ %Z.p, %if.else ], [ %X.p, %if.then ]
+  tail call void @foo(i8* %phi.1, i8* %phi.2)
+  ret void
+}
+
+declare void @foo (i8* %a, i8* %b)
+
+define i8* @test1(i8* %X, i8* %Y, i8* %Z, i1 %cmp) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[XVAL:%.*]] = load i8, i8* [[X:%.*]], align 1
+; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body.preheader:
+; CHECK-NEXT:    [[YVAL:%.*]] = load i8, i8* [[Y:%.*]], align 1
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i8* [ [[X]], [[FOR_BODY]] ], [ [[Y]], [[FOR_BODY_PREHEADER]] ]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[XVAL]], [[YVAL]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY]], label [[FOR_END]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[PHI1:%.*]] = phi i8* [ [[PHI]], [[FOR_BODY]] ], [ [[Z:%.*]], [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8* [[PHI1]]
+;
+entry:
+  %Xval = load i8, i8* %X
+  br i1 %cmp, label %for.body.preheader, label %for.end
+
+for.body.preheader:                               ; preds = %entry
+  %Yval = load i8, i8* %Y
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %for.body.preheader
+  %phi = phi i8* [ %X.p, %for.body ], [ %Y, %for.body.preheader ]
+  %X.i = ptrtoint i8* %X to i64
+  %X.p = inttoptr i64 %X.i to i8*
+  %cmp1  = icmp slt i8 %Xval, %Yval
+  br i1 %cmp1, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.body, %entry
+  %phi1 = phi i8* [%phi, %for.body], [%Z, %entry]
+  ret i8* %phi1
+}
+
+define void @test_dereferenceable(i8* %X, i8* dereferenceable(1) %Z, i1 %cmp) {
+; CHECK-LABEL: @test_dereferenceable(
+; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[X_I:%.*]] = ptrtoint i8* [[X:%.*]] to i64
+; CHECK-NEXT:    [[X_P:%.*]] = inttoptr i64 [[X_I]] to i8*
+; CHECK-NEXT:    br label [[CALL:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    br label [[CALL]]
+; CHECK:       call:
+; CHECK-NEXT:    [[PHI_1:%.*]] = phi i8* [ [[Z:%.*]], [[IF_ELSE]] ], [ [[X_P]], [[IF_THEN]] ]
+; CHECK-NEXT:    tail call void @foo(i8* [[PHI_1]], i8* [[PHI_1]])
+; CHECK-NEXT:    ret void
+;
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %X.i = ptrtoint i8* %X to i64
+  %X.p = inttoptr i64 %X.i to i8*
+  br label %call
+
+if.else:
+  %Z.i = ptrtoint i8* %Z to i64
+  %Z.p = inttoptr i64 %Z.i to i8*
+  br label %call
+
+call:
+  %phi.1 = phi i8* [ %Z.p, %if.else ], [ %X.p, %if.then ]
+  tail call void @foo(i8* %phi.1, i8* %phi.1)
+  ret void
+}
+
+define void @test_dereferenceable_2(i8* dereferenceable(16) %X, i8* dereferenceable(16) %Z, i1 %cmp) {
+; CHECK-LABEL: @test_dereferenceable_2(
+; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[CALL:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    br label [[CALL]]
+; CHECK:       call:
+; CHECK-NEXT:    [[PHI_1:%.*]] = phi i8* [ [[Z:%.*]], [[IF_ELSE]] ], [ [[X:%.*]], [[IF_THEN]] ]
+; CHECK-NEXT:    tail call void @foo(i8* nonnull [[PHI_1]], i8* nonnull [[PHI_1]])
+; CHECK-NEXT:    ret void
+;
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:
+  %X.i = ptrtoint i8* %X to i64
+  %X.p = inttoptr i64 %X.i to i8*
+  br label %call
+
+if.else:
+  %Z.i = ptrtoint i8* %Z to i64
+  %Z.p = inttoptr i64 %Z.i to i8*
+  br label %call
+
+call:
+  %phi.1 = phi i8* [ %Z.p, %if.else ], [ %X.p, %if.then ]
+  tail call void @foo(i8* %phi.1, i8* %phi.1)
+  ret void
+}