Add llvm.psub

[aqjune]

Summary

This patch adds llvm.psub(p1,p2) intrinsic function, which subtracts two pointers and returns the difference.

Its semantic is as follows.
If p1 and p2 point to different objects, and neither of them is based on a pointer casted from an integer, `llvm.psub(p1, p2)` returns poison. For example,

%p = alloca
%q = alloca
%i = llvm.psub(p, q) ; %i is poison

This allows aggressive escape analysis on pointers. Given i = llvm.psub(p1, p2), if neither of p1 and p2 is based on a pointer casted from an integer, the llvm.psub call does not make p1 or p2 escape.

If either p1 or p2 is based on a pointer casted from integer, or p1 and p2 point to a same object, it returns the result of subtraction (in bytes); for example,

%p = alloca
%q = inttoptr %x
%i = llvm.psub(p, q) ; %i is equivalent to (ptrtoint %p) - %x

`null` is regarded as a pointer casted from an integer because
it is equivalent to `inttoptr 0`.

Adding llvm.psub allows LLVM to utilize significant portion of ptrtoints & reduce a portion of inttoptrs.
When SPECrate 2017 is compiled with -O0 (r348082, Dec 2 2018), approximately 23,200 ptrtoints are generated. Among these, about 22,000 ptrtoints (95%) are generated from pointer subtraction.
When SPECrate 2017 is compiled with -O3, 22,800 inttoptrs and 31,700 ptrtoints are generated. If psub is used instead, # of inttoptr decreases to 13,500 (59%) and # of ptrtoint decreases to 14,300 (45%).

To see the performance change, I ran SPECrate 2017 (thread # = 1) with three versions of LLVM, which are r313797 (Sep 21, 2017), LLVM 6.0 official, and r348082 (Dec 2, 2018). Running r313797 shows that 505.mcf_r has consistent 2.0% speedup over 3 different machines (which are i3-6100, i5-6600, i7-7700). For LLVM 6.0 and r348082, there's neither consistent speedup nor slowdown, but the average speedup is near 0. I believe there's still a room of improvement.

[aqjune]

https://reviews.llvm.org/D56601 shows how CaptureTracker can be enhanced with llvm.psub.

[lebedev.ri]

Tests missing.

docs/LangRef.rst

16077

declare iN @llvm.psub.iN.pty.pty(pty p1, pty p2) nounwind readnone speculatable

16095

I realize that it is just a snippet, but this is not a valid IR.

[arichardson]

I like the introduction of a explicit pointer subtraction since ptrtoint/inttoptr can cause lots of subtle bugs in our CHERI backend. However, I wonder if this should be an instruction instead of an intrinsic?

docs/LangRef.rst

16095

I'm not sure disallowing pointer diffs between objects with different provenance is a good idea.

For CHERI we have an explicit instruction to get the difference between two capabilities (effectively pointers with bounds, permissions and integrity protection). If we were to take provenance into account and raise a trap when one of the values is derived from a different object, it would cause lots of C code to stop working. Our CSub instruction ignores bounds an object provenance and only subtracts the virtual address.

[efriedma]

This patch doesn't have llvm-commits subscribed. The developer policy says all review discussion for LLVM patches must happen on llvm-commits.

Please "abandon" this revision, and post it again with llvm-commits correctly CC'ed.

[aqjune]

Hello all, I sincerely thank you for your comments. I'll apply the comments & re-upload the patch.

@arichardson I think csub and psub should be used differently, sadly :( Returning poison on different provenances allow more analysis, and I believe this a benefit of introducing psub.

docs/LangRef.rst

 obviously not constant. However, a call like
 ``llvm.is.constant.i32(i32 %param)`` *can* return true after the
 function is inlined, if the value passed to the function parameter was
 a constant.
 
 On the other hand, if constant folding is not run, it will never
 evaluate to true, even in simple cases.
 
+'``llvm.psub``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare iN @llvm.psub.iN.pty.pty(pty, pty) nounwind readnone speculatable
+
+Overview:
+"""""""""
+
+The '``llvm.psub(p1, p2)``' intrinsic returns the result of subtraction
+of two pointers `p1 - p2` in bytes.
+
+Arguments:
+""""""""""
+The two arguments are pointers of the same type to subtract.
+The return value is the result of subtraction.
+
+Semantics:
+""""""""""
+If p1 and p2 point to different objects(global variable, alloca, etc)
+and neither of them is based on a pointer casted from an integer,
+``llvm.psub(p1, p2)`` returns poison. Otherwise, the result is equivalent to
+``sub (ptrtoint p1 to iN) (ptrtoint p2 to iN)``.
+``null`` is regarded as a pointer casted from an integer because
+it is equivalent to ``inttoptr 0``.
+Therefore, ``llvm.psub(p1, null)`` is equivalent to
+``ptrtoint p1``.
+
+The goal of this intrinsics is to allow more aggressive escape analysis on
+pointers. Given ``i = llvm.psub(p1, p2)``, if neither of p1 and p2
+is based on a pointer casted from an integer, this ``llvm.psub``
+does not make p1 or p2 escape.
+
 Stack Map Intrinsics
 --------------------
 
 LLVM provides experimental intrinsics to support runtime patching
 mechanisms commonly desired in dynamic language JITs. These intrinsics
 are described in :doc:`StackMaps`.
 
 Element Wise Atomic Memory Intrinsics

include/llvm/CodeGen/BasicTTIImpl.h

case Intrinsic::experimental_vector_reduce_fmin:
       return static_cast<T *>(this)->getMinMaxReductionCost(
           Tys[0], CmpInst::makeCmpResultType(Tys[0]), /*IsPairwiseForm=*/false,
           /*IsSigned=*/true);
     case Intrinsic::experimental_vector_reduce_umax:
     case Intrinsic::experimental_vector_reduce_umin:
       return static_cast<T *>(this)->getMinMaxReductionCost(
           Tys[0], CmpInst::makeCmpResultType(Tys[0]), /*IsPairwiseForm=*/false,
           /*IsSigned=*/false);
+    case Intrinsic::psub: {
+      // Two ptrtoints followed by sub.
+      unsigned p2i_cost = static_cast<T *>(this)
+          ->getOperationCost(Instruction::PtrToInt, Tys[0], RetTy);
+      unsigned sub_cost = static_cast<T *>(this)
+          ->getOperationCost(Instruction::Sub, RetTy, RetTy);
+      return p2i_cost * 2 + sub_cost;
+    }
     case Intrinsic::ctpop:
       ISDs.push_back(ISD::CTPOP);
       // In case of legalization use TCC_Expensive. This is cheaper than a
       // library call but still not a cheap instruction.
       SingleCallCost = TargetTransformInfo::TCC_Expensive;
       break;
     // FIXME: ctlz, cttz, ...
     }

include/llvm/IR/IRBuilder.h

   /// the size of the pointed-to objects.
   ///
   /// This is intended to implement C-style pointer subtraction. As such, the
   /// pointers must be appropriately aligned for their element types and
   /// pointing into the same object.
   Value *CreatePtrDiff(Value *LHS, Value *RHS, const Twine &Name = "") {
     assert(LHS->getType() == RHS->getType() &&
            "Pointer subtraction operand types must match!");
-    auto *ArgType = cast<PointerType>(LHS->getType());
-    Value *LHS_int = CreatePtrToInt(LHS, Type::getInt64Ty(Context));
-    Value *RHS_int = CreatePtrToInt(RHS, Type::getInt64Ty(Context));
-    Value *Difference = CreateSub(LHS_int, RHS_int);
+    PointerType *ArgType = cast<PointerType>(LHS->getType());
+    Type *psubTys[] = { Type::getInt64Ty(Context), ArgType, ArgType };
+    Value *psubArgs[] = { LHS, RHS };
+    Module *M = BB->getParent()->getParent();
+    Value *Difference = CreateCall(Intrinsic::getDeclaration(M,
+                  llvm::Intrinsic::psub, ArrayRef<llvm::Type *>(psubTys, 3)),
+               psubArgs);
     return CreateExactSDiv(Difference,
                            ConstantExpr::getSizeOf(ArgType->getElementType()),
                            Name);
   }
 
   /// Create a launder.invariant.group intrinsic call. If Ptr type is
   /// different from pointer to i8, it's casted to pointer to i8 in the same
   /// address space before call and casted back to Ptr type after call.

include/llvm/IR/Intrinsics.td

 // Clear cache intrinsic, default to ignore (ie. emit nothing)
 // maps to void __clear_cache() on supporting platforms
 def int_clear_cache : Intrinsic<[], [llvm_ptr_ty, llvm_ptr_ty],
                                 [], "llvm.clear_cache">;
 
 // Intrinsic to detect whether its argument is a constant.
 def int_is_constant : Intrinsic<[llvm_i1_ty], [llvm_any_ty], [IntrNoMem], "llvm.is.constant">;
 
+let IntrProperties = [IntrNoMem, IntrSpeculatable] in {
+def int_psub : Intrinsic<[llvm_anyint_ty], [llvm_anyptr_ty, llvm_anyptr_ty]>;
+}
 
 //===-------------------------- Masked Intrinsics -------------------------===//
 //
 def int_masked_store : Intrinsic<[], [llvm_anyvector_ty,
                                       LLVMAnyPointerType<LLVMMatchType<0>>,
                                       llvm_i32_ty,
                                       LLVMVectorSameWidth<0, llvm_i1_ty>],
                                  [IntrArgMemOnly]>;

lib/Analysis/InstructionSimplify.cpp

if ((match(Op0, m_APFloat(C)) && C->isInfinity() &&
       return ConstantFP::getInfinity(ReturnType, UseNegInf);
 
     // TODO: minnum(nnan x, inf) -> x
     // TODO: minnum(nnan ninf x, flt_max) -> x
     // TODO: maxnum(nnan x, -inf) -> x
     // TODO: maxnum(nnan ninf x, -flt_max) -> x
     break;
   }
+  case Intrinsic::psub:
+    if (Constant *Result = computePointerDifference(Q.DL, Op0, Op1))
+      return ConstantExpr::getIntegerCast(Result, F->getReturnType(), true);
+    break;
   default:
     break;
   }
 
   return nullptr;
 }
 
 template <typename IterTy>

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

case Intrinsic::icall_branch_funnel: {
     return nullptr;
   }
 
   case Intrinsic::wasm_landingpad_index:
     // Information this intrinsic contained has been transferred to
     // MachineFunction in SelectionDAGISel::PrepareEHLandingPad. We can safely
     // delete it now.
     return nullptr;
+  case Intrinsic::psub:
+    // pointer to integer casting
+    EVT DestVT = DAG.getTargetLoweringInfo().getValueType(DAG.getDataLayout(),
+                                                          I.getType());
+    SDValue Op1 = DAG.getZExtOrTrunc(getValue(I.getArgOperand(0)), getCurSDLoc(), DestVT);
+    SDValue Op2 = DAG.getZExtOrTrunc(getValue(I.getArgOperand(1)), getCurSDLoc(), DestVT);
+    SDValue BinNodeValue = DAG.getNode(ISD::SUB, getCurSDLoc(), Op1.getValueType(),
+                                       Op1, Op2);
+    setValue(&I, BinNodeValue);
+    return nullptr;
   }
 }
 
 void SelectionDAGBuilder::visitConstrainedFPIntrinsic(
     const ConstrainedFPIntrinsic &FPI) {
   SDLoc sdl = getCurSDLoc();
   unsigned Opcode;
   switch (FPI.getIntrinsicID()) {

lib/Transforms/InstCombine/InstCombineCalls.cpp

if (match(NextInst,
         MoveI = MoveI->getNextNode();
         Temp->moveBefore(II);
       }
       II->setArgOperand(0, Builder.CreateAnd(CurrCond, NextCond));
       return eraseInstFromFunction(*NextInst);
     }
     break;
   }
+
+  case Intrinsic::psub: {
+    Value *Op1 = II->getArgOperand(0);
+    Value *Op2 = II->getArgOperand(1);
+    if (Value *Res = OptimizePointerDifference(Op1, Op2, II->getType())) {
+      return replaceInstUsesWith(*II, Res);
+    }
+    //   psub(inttoptr(i1), p2)
+    // =>
+    //   sub (ptrtoint(inttoptr i1), ptrtoint(p2))
+    // Note that ptrtoint(inttoptr i1) can be optimized to i1.
+    if (Operator::getOpcode(Op1) == Instruction::IntToPtr ||
+        Operator::getOpcode(Op2) == Instruction::IntToPtr ||
+        isa<ConstantPointerNull>(Op1) || isa<ConstantPointerNull>(Op2)) {
+      Type *Op1Ty = Op1->getType();
+      IntegerType *ITy = IntegerType::get(Op1->getContext(),
+                                          DL.getPointerTypeSizeInBits(Op1Ty));
+      Value *I1 = Builder.CreatePtrToInt(Op1, ITy);
+      Value *I2 = Builder.CreatePtrToInt(Op2, ITy);
+      Value *Sub = Builder.CreateSub(I1, I2);
+      Value *Cast = Builder.CreateIntCast(Sub, II->getType(), true, II->getName());
+      return replaceInstUsesWith(*II, Cast);
+    }
+    break;
+  }
   }
   return visitCallSite(II);
 }
 
 // Fence instruction simplification
 Instruction *InstCombiner::visitFenceInst(FenceInst &FI) {
   // Remove identical consecutive fences.
   Instruction *Next = FI.getNextNonDebugInstruction();

lib/Transforms/InstCombine/InstCombineCompares.cpp

if (IsZero || C == BitWidth) {
       Cmp.setOperand(0, II->getArgOperand(0));
       auto *NewOp =
           IsZero ? Constant::getNullValue(Ty) : Constant::getAllOnesValue(Ty);
       Cmp.setOperand(1, NewOp);
       return &Cmp;
     }
     break;
   }
+  case Intrinsic::psub: {
+    // psub(a, b) == 0  ->  a == b
+    if (C.isNullValue()) {
+      Value *Op0 = II->getArgOperand(0);
+      Value *Op1 = II->getArgOperand(1);
+      Value *NewCmp = nullptr;
+      if (Cmp.getPredicate() == CmpInst::ICMP_EQ) {
+        NewCmp = Builder.CreateICmpEQ(Op0, Op1);
+      } else if (Cmp.getPredicate() == CmpInst::ICMP_NE) {
+        NewCmp = Builder.CreateICmpNE(Op0, Op1);
+      } // There's no other case because this function starts with
+        // Cmp.isEquality().
+      NewCmp->takeName(&Cmp);
+      replaceInstUsesWith(Cmp, NewCmp);
+      Worklist.Add(II);
+      return &Cmp;
+    }
+    break;
+  }
   default:
     break;
   }
 
   return nullptr;
 }
 
 /// Handle icmp with constant (but not simple integer constant) RHS.