[RS4GC] Introduce intrinsics to get base ptr and offset

[yrouban]

Summary

There can be a need for some optimizations to get (base, offset) for any GC pointer. The base can be calculated by generating needed instructions as it is done by the RewriteStatepointsForGC::findBasePointer() function. The offset can be calculated in the same way. Though to not expose the base calculation and to make the offset calculation as simple as ptrtoint(derived_ptr) - ptrtoint(base_ptr), which is illegal outside RS4GC, this patch introduces 2 intrinsics:

• declare i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base(i8 addrspace(1)* readnone nocapture %derived_ptr) nounwind readnone willreturn
• declare i64 @llvm.experimental.gc.get.pointer.offset(i8 addrspace(1)* readnone nocapture %derived_ptr) nounwind readnone willreturn

These intrinsics are inlined by RS4GC along with generation of statepoint sequences.

With these new intrinsics the GC parseable lowering for atomic memcpy intrinsics (D88861) could be implemented as a separate pass.

[reames]

Finally had time to touch base and understand the background to this.

I think this is an entirely reasonable direction. I have minor comments on the patch, but no major concerns.

A couple of requested changes:

1. Please add verifier support to check that the return and argument type of gc.pointer.base are the same.
2. Please drop the gc-leaf intrinsic piece. That can and should be it's own patch. If you look at callsGCLeafFunction, you'll see we currently assume most intrinsics are GCLeaf, so this should be redundant.

llvm/docs/Statepoints.rst

443

Name out of sync with following text.

Also, the documentation for these should be in LangRef. If you want some extra discussion here, that's fine, but put the definition in LangRef.

464

is an pointer which is based on some object with an unknown offset from the base of said object.

469

Please add this sentence to the beginning of your current paragraph.

This intrinsic is used in the abstract machine model for GC to represent the base pointer for an arbitrary derived pointer.

498

Same change as above.

503

Add same sentence as above.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

599

I don't think this piece of the change should be required. Can you explain why this is needed?

2475

This doesn't really have anything to do with the task of inserting parse points. I see why you're structuring it this way - to avoid recomputing the base pointer - but I'd prefer to keep the api clean. Please do this before the call to insertParsePoints with a separate call to findBasePointers. This should be correct, if slightly less optimal. We can then build on that in a following patch.

[jdoerfert]

Drive by, just interested in potential use outside gc. But don't want to get into this now.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

2856

[yrouban]

I'm still working on the next version.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

599

This case is tested in the new intrinsics.ll:

Here is a simplified version:

define void @test_chained(i8 addrspace(1)* %obj1, i8 addrspace(1)* %obj2, i32 %len, i1 %c) gc "statepoint-example" {
entry:
  %obj1.12 = getelementptr inbounds i8, i8 addrspace(1)* %obj1, i64 12
  %obj2.16 = getelementptr inbounds i8, i8 addrspace(1)* %obj2, i64 16
  %obj.x = select i1 %c, i8 addrspace(1)* %obj1.12, i8 addrspace(1)* %obj2.16

  %obj.x.base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x)
  %obj.x.base_of_base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x.base)

  ret void
}

After the first %obj.x.base = get.pointer.base(%obj.x) is inlined by inlineGetBaseAndOffset() we get all %obj.x.base uses RAUWed with the result %obj.x.base1 which is marked with !is_base_value:

%obj1.12 = getelementptr inbounds i8, i8 addrspace(1)* %obj1, i64 12
%obj2.16 = getelementptr inbounds i8, i8 addrspace(1)* %obj2, i64 16
%obj.x.base1 = select i1 %c, i8 addrspace(1)* %obj1, i8 addrspace(1)* %obj2, !is_base_value !0
%obj.x = select i1 %c, i8 addrspace(1)* %obj1.12, i8 addrspace(1)* %obj2.16
%obj.x.base_of_base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x.base1)

Then inlineGetBaseAndOffset() calls findBasePointer(%obj.x.base1), which ends up in instantiating BaseDefiningValueResult(%obj.x.base1, IsKnownBase).

[reames]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

599

I think you might be thinking about an older implementation of RS4GC, we recently improved the find base pointer algorithm to detect obj.x.base as a base pointer without the hint, and the metadata check should no longer be needed. If not, I'd like to see the reduced test case which still requires it because it's probably a lurking inference bug.

Can I ask you to run that test?

To be clear, I don't really care about this. It doesn't do any major harm to have the redundant check.

[yrouban]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

599

Can I ask you to run that test?

Yes, I ran the simplified test with the fresh workspace right before sending the comment. I will make this a separate small test case.

[yrouban]

Philip, thank you for comments. I believe I addressed them all.

[reames]

LGTM w/minor comment.

As a follow up, it would be interesting to explore lowering these early during optimization when feasible. e.g. base_of(gep alloca, 15) -> alloca

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

2402

minor: use a switch here.

llvm/docs/LangRef.rst

 relationship of the newly relocated pointers is a projection of the
 unrelocated pointers.  In particular, the integer value of the pointer
 returned is unspecified.
 
 A ``gc.relocate`` is modeled as a ``readnone`` pure function.  It has no
 side effects since it is just a way to extract information about work
 done during the actual call modeled by the ``gc.statepoint``.
 
+.. _gc.get.pointer.base:
+
+'llvm.experimental.gc.get.pointer.base' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare <pointer type>
+        @llvm.experimental.gc.get.pointer.base(
+          <pointer type> readnone nocapture %derived_ptr)
+          nounwind readnone willreturn
+
+Overview:
+"""""""""
+
+``gc.get.pointer.base`` for a derived pointer returns its base pointer.
+
+Operands:
+"""""""""
+
+The only argument is a pointer which is based on some object with
+an unknown offset from the base of said object.
+
+Semantics:
+""""""""""
+
+This intrinsic is used in the abstract machine model for GC to represent
+the base pointer for an arbitrary derived pointer.
+
+This intrinsic is inlined by the :ref:`RewriteStatepointsForGC` pass by
+replacing all uses of this callsite with the offset of a derived pointer from
+its base pointer value. The replacement is done as part of the lowering to the
+explicit statepoint model.
+
+The return pointer type must be the same as the type of the parameter.
+
+
+'llvm.experimental.gc.get.pointer.offset' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare i64
+        @llvm.experimental.gc.get.pointer.offset(
+          <pointer type> readnone nocapture %derived_ptr)
+          nounwind readnone willreturn
+
+Overview:
+"""""""""
+
+``gc.get.pointer.offset`` for a derived pointer returns the offset from its
+base pointer.
+
+Operands:
+"""""""""
+
+The only argument is a pointer which is based on some object with
+an unknown offset from the base of said object.
+
+Semantics:
+""""""""""
+
+This intrinsic is used in the abstract machine model for GC to represent
+the offset of an arbitrary derived pointer from its base pointer.
+
+This intrinsic is inlined by the :ref:`RewriteStatepointsForGC` pass by
+replacing all uses of this callsite with the offset of a derived pointer from
+its base pointer value. The replacement is done as part of the lowering to the
+explicit statepoint model.
+
+Basically this call calculates difference between the derived pointer and its
+base pointer (see :ref:`gc.get.pointer.base`) both ptrtoint casted. But
+this cast done outside the :ref:`RewriteStatepointsForGC` pass could result
+in the pointers lost for further lowering from the abstract model to the
+explicit physical one.
+
 Code Generator Intrinsics
 -------------------------
 
 These intrinsics are provided by LLVM to expose special features that
 may only be implemented with code generator support.
 
 '``llvm.returnaddress``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

llvm/docs/Statepoints.rst

.Ltmp1:
     popq  %rdx
     retq
 
 Note that the design as presented above is not fully implemented: in particular,
 strategy-specific lowering is not present, and all GC transitions are emitted as
 as single no-op before and after the call instruction. These no-ops are often
 removed by the backend during dead machine instruction elimination.
 
+Before the abstract machine model is lowered to the explicit statepoint model
+of relocations by the :ref:`RewriteStatepointsForGC` pass it is possible for
+any derived pointer to get its base pointer and offset from the base pointer
+by using the ``gc.get.pointer.base`` and the ``gc.get.pointer.offset``
+intrinsics respectively. These intrinsics are inlined by the
+:ref:`RewriteStatepointsForGC` pass and must not be used after this pass.
+
 
 .. _statepoint-stackmap-format:
 
 Stack Map Format
 ================
 
 Locations for each pointer value which may need read and/or updated by
 the runtime or collector are provided in a separate section of the
 generated object file as specified in the PatchPoint documentation.
 This special section is encoded per the
 :ref:`Stack Map format <stackmap-format>`.
 
 The general expectation is that a JIT compiler will parse and discard this
 format; it is not particularly memory efficient.  If you need an alternate
 format (e.g. for an ahead of time compiler), see discussion under
 :ref: `open work items <OpenWork>` below.
 
 Each statepoint generates the following Locations:
 
 * Constant which describes the calling convention of the call target. This
   constant is a valid :ref:`calling convention identifier <callingconv>` for
   the version of LLVM used to generate the stackmap. No additional compatibility
   guarantees are made for this constant over what LLVM provides elsewhere w.r.t.
   these identifiers.
 * Constant which describes the flags passed to the statepoint intrinsic
 * Constant which describes number of following deopt *Locations* (not
   operands).  Will be 0 if no "deopt" bundle is provided.
 * Variable number of Locations, one for each deopt parameter listed in the
   "deopt" operand bundle.  At the moment, only deopt parameters with a bitwidth
   of 64 bits or less are supported.  Values of a type larger than 64 bits can be
   specified and reported only if a) the value is constant at the call site, and
   b) the constant can be represented with less than 64 bits (assuming zero 
   extension to the original bitwidth).
 * Variable number of relocation records, each of which consists of 
   exactly two Locations.  Relocation records are described in detail
   below.
 
 Each relocation record provides sufficient information for a collector to 
* There may be fewer relocation records then gc parameters in the IR
   are possible.  
 * The Locations within each record may either be of pointer size or a 
   multiple of pointer size.  In the later case, the record must be 
   interpreted as describing a sequence of pointers and their corresponding 
   base pointers. If the Location is of size N x sizeof(pointer), then
   there will be N records of one pointer each contained within the Location.
   Both Locations in a pair can be assumed to be of the same size.
 
 Note that the Locations used in each section may describe the same
 physical location.  e.g. A stack slot may appear as a deopt location,
 a gc base pointer, and a gc derived pointer.
 
 The LiveOut section of the StkMapRecord will be empty for a statepoint
 record.
 
 Safepoint Semantics & Verification
 ==================================
 
 The fundamental correctness property for the compiled code's
 correctness w.r.t. the garbage collector is a dynamic one.  It must be
 the case that there is no dynamic trace such that an operation
 involving a potentially relocated pointer is observably-after a

 the quality of the generated code when compiled with garbage collection support.
 
 .. _RewriteStatepointsForGC_intrinsic_lowering:
 
 RewriteStatepointsForGC intrinsic lowering
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 As a part of lowering to the explicit model of relocations
-RewriteStatepointsForGC performs GC specific lowering for
-'``llvm.memcpy.element.unordered.atomic.*``',
-'``llvm.memmove.element.unordered.atomic.*``' intrinsics.
+RewriteStatepointsForGC performs GC specific lowering for the following
+intrinsics:
+
+* ``gc.get.pointer.base``
+* ``gc.get.pointer.offset``
+* ``llvm.memcpy.element.unordered.atomic.*``
+* ``llvm.memmove.element.unordered.atomic.*``
 
-There are two possible lowerings for these copy operations: GC leaf lowering
-and GC parseable lowering. If a call is explicitly marked with
+There are two possible lowerings for the memcpy and memmove operations:
+GC leaf lowering and GC parseable lowering. If a call is explicitly marked with
 "gc-leaf-function" attribute the call is lowered to a GC leaf call to
 '``__llvm_memcpy_element_unordered_atomic_*``' or
 '``__llvm_memmove_element_unordered_atomic_*``' symbol. Such a call can not
 take a safepoint. Otherwise, the call is made GC parseable by wrapping the
 call into a statepoint. This makes it possible to take a safepoint during
 copy operation. Note that a GC parseable copy operation is not required to
 take a safepoint. For example, a short copy operation may be performed without
 taking a safepoint.

llvm/include/llvm/IR/IRBuilder.h

#endif
   /// Create a call to the experimental.gc.relocate intrinsics to
   /// project the relocated value of one pointer from the statepoint.
   CallInst *CreateGCRelocate(Instruction *Statepoint,
                              int BaseOffset,
                              int DerivedOffset,
                              Type *ResultType,
                              const Twine &Name = "");
 
+  /// Create a call to the experimental.gc.pointer.base intrinsic to get the
+  /// base pointer for the specified derived pointer.
+  CallInst *CreateGCGetPointerBase(Value *DerivedPtr, const Twine &Name = "");
+
+  /// Create a call to the experimental.gc.get.pointer.offset intrinsic to get
+  /// the offset of the specified derived pointer from its base.
+  CallInst *CreateGCGetPointerOffset(Value *DerivedPtr, const Twine &Name = "");
+
   /// Create a call to llvm.vscale, multiplied by \p Scaling. The type of VScale
   /// will be the same type as that of \p Scaling.
   Value *CreateVScale(Constant *Scaling, const Twine &Name = "");
 
   /// Creates a vector of type \p DstType with the linear sequence <0, 1, ...>
   Value *CreateStepVector(Type *DstType, const Twine &Name = "");
 
   /// Create a call to intrinsic \p ID with 1 operand which is mangled on its

llvm/include/llvm/IR/Intrinsics.td

 def int_experimental_gc_result   : Intrinsic<[llvm_any_ty], [llvm_token_ty],
                                              [IntrNoMem]>;
 def int_experimental_gc_relocate : Intrinsic<[llvm_any_ty],
                                              [llvm_token_ty, llvm_i32_ty,
                                               llvm_i32_ty],
                                              [IntrNoMem, ImmArg<ArgIndex<1>>,
                                               ImmArg<ArgIndex<2>>]>;
 
+def int_experimental_gc_get_pointer_base : Intrinsic<[llvm_anyptr_ty],
+                 [llvm_anyptr_ty], [IntrNoMem, IntrWillReturn,
+                 ReadNone<ArgIndex<0>>, NoCapture<ArgIndex<0>>]>;
+
+def int_experimental_gc_get_pointer_offset : Intrinsic<[llvm_i64_ty],
+                 [llvm_anyptr_ty], [IntrNoMem, IntrWillReturn,
+                 ReadNone<ArgIndex<0>>, NoCapture<ArgIndex<0>>]>;
+
 //===------------------------ Coroutine Intrinsics ---------------===//
 // These are documented in docs/Coroutines.rst
 
 // Coroutine Structure Intrinsics.
 
 def int_coro_id : Intrinsic<[llvm_token_ty], [llvm_i32_ty, llvm_ptr_ty,
                              llvm_ptr_ty, llvm_ptr_ty],
                             [IntrArgMemOnly, IntrReadMem,

llvm/lib/IR/IRBuilder.cpp

Function *FnGCRelocate =
      Intrinsic::getDeclaration(M, Intrinsic::experimental_gc_relocate, Types);
 
  Value *Args[] = {Statepoint,
                   getInt32(BaseOffset),
                   getInt32(DerivedOffset)};
  return createCallHelper(FnGCRelocate, Args, this, Name);
 }
 
+CallInst *IRBuilderBase::CreateGCGetPointerBase(Value *DerivedPtr,
+                                                const Twine &Name) {
+  Module *M = BB->getParent()->getParent();
+  Type *PtrTy = DerivedPtr->getType();
+  Function *FnGCFindBase = Intrinsic::getDeclaration(
+      M, Intrinsic::experimental_gc_get_pointer_base, {PtrTy, PtrTy});
+  return createCallHelper(FnGCFindBase, {DerivedPtr}, this, Name);
+}
+
+CallInst *IRBuilderBase::CreateGCGetPointerOffset(Value *DerivedPtr,
+                                                  const Twine &Name) {
+  Module *M = BB->getParent()->getParent();
+  Type *PtrTy = DerivedPtr->getType();
+  Function *FnGCGetOffset = Intrinsic::getDeclaration(
+      M, Intrinsic::experimental_gc_get_pointer_offset, {PtrTy});
+  return createCallHelper(FnGCGetOffset, {DerivedPtr}, this, Name);
+}
+
 CallInst *IRBuilderBase::CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V,
                                               Instruction *FMFSource,
                                               const Twine &Name) {
   Module *M = BB->getModule();
   Function *Fn = Intrinsic::getDeclaration(M, ID, {V->getType()});
   return createCallHelper(Fn, {V}, this, Name, FMFSource);
 }
 

llvm/lib/IR/Verifier.cpp

void Verifier::visitFunction(const Function &F) {
   // Only do this if the module is materialized, otherwise we don't have all the
   // uses.
   if (F.getIntrinsicID() && F.getParent()->isMaterialized()) {
     const User *U;
     if (F.hasAddressTaken(&U))
       Assert(false, "Invalid user of intrinsic instruction!", U);
   }
 
+  // Check intrinsics' signatures.
+  switch (F.getIntrinsicID()) {
+  case Intrinsic::experimental_gc_get_pointer_base: {
+    FunctionType *FT = F.getFunctionType();
+    Assert(FT->getNumParams() == 1, "wrong number of parameters", F);
+    Assert(isa<PointerType>(F.getReturnType()),
+           "gc.get.pointer.base must return a pointer", F);
+    Assert(FT->getParamType(0) == F.getReturnType(),
+           "gc.get.pointer.base operand and result must be of the same type",
+           F);
+    break;
+  }
+  case Intrinsic::experimental_gc_get_pointer_offset: {
+    FunctionType *FT = F.getFunctionType();
+    Assert(FT->getNumParams() == 1, "wrong number of parameters", F);
+    Assert(isa<PointerType>(FT->getParamType(0)),
+           "gc.get.pointer.offset operand must be a pointer", F);
+    Assert(F.getReturnType()->isIntegerTy(),
+           "gc.get.pointer.offset must return integer", F);
+    break;
+  }
+  }
+
   auto *N = F.getSubprogram();
   HasDebugInfo = (N != nullptr);
   if (!HasDebugInfo)
     return;
 
   // Check that all !dbg attachments lead to back to N.
   //
   // FIXME: Check this incrementally while visiting !dbg attachments.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

case Intrinsic::experimental_gc_relocate:
       // but why are you doing this?  There's no good reason.
       llvm_unreachable("repeat safepoint insertion is not supported");
     case Intrinsic::gcroot:
       // Currently, this mechanism hasn't been extended to work with gcroot.
       // There's no reason it couldn't be, but I haven't thought about the
       // implications much.
       llvm_unreachable(
           "interaction with the gcroot mechanism is not supported");
+    case Intrinsic::experimental_gc_get_pointer_base:
+      return findBaseDefiningValue(II->getOperand(0));
     }
   }
   // We assume that functions in the source language only return base
   // pointers.  This should probably be generalized via attributes to support
   // both source language and internal functions.
   if (isa<CallInst>(I) || isa<InvokeInst>(I))
     return BaseDefiningValueResult(I, true);
 
static BaseDefiningValueResult findBaseDefiningValue(Value *I) {
   if (isa<ExtractValueInst>(I))
     return BaseDefiningValueResult(I, true);
 
   // We should never see an insert vector since that would require we be
   // tracing back a struct value not a pointer value.
   assert(!isa<InsertValueInst>(I) &&
          "Base pointer for a struct is meaningless");
 
+  // This value might have been generated by findBasePointer() called when
+  // substituting gc.get.pointer.base() intrinsic.
+  bool IsKnownBase =
+      isa<Instruction>(I) && cast<Instruction>(I)->getMetadata("is_base_value");
+
   // An extractelement produces a base result exactly when it's input does.
   // We may need to insert a parallel instruction to extract the appropriate
   // element out of the base vector corresponding to the input. Given this,
   // it's analogous to the phi and select case even though it's not a merge.
   if (isa<ExtractElementInst>(I))
     // Note: There a lot of obvious peephole cases here.  This are deliberately
     // handled after the main base pointer inference algorithm to make writing
     // test cases to exercise that code easier.
-    return BaseDefiningValueResult(I, false);
+    return BaseDefiningValueResult(I, IsKnownBase);
 
   // The last two cases here don't return a base pointer.  Instead, they
   // return a value which dynamically selects from among several base
   // derived pointers (each with it's own base potentially).  It's the job of
   // the caller to resolve these.
   assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&
          "missing instruction case in findBaseDefiningValing");
-  return BaseDefiningValueResult(I, false);
+  return BaseDefiningValueResult(I, IsKnownBase);
 }
 
 /// Returns the base defining value for this value.
 static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache) {
   Value *&Cached = Cache[I];
   if (!Cached) {
     Cached = findBaseDefiningValue(I).BDV;
     LLVM_DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> "
#endif
   }
 
   // Remove rematerializaed values from the live set
   for (auto LiveValue: LiveValuesToBeDeleted) {
     Info.LiveSet.remove(LiveValue);
   }
 }
 
+static bool inlineGetBaseAndOffset(Function &F,
+                                   SmallVectorImpl<CallInst *> &Intrinsics) {
+  DefiningValueMapTy DVCache;
+  auto &Context = F.getContext();
+  auto &DL = F.getParent()->getDataLayout();
+  bool Changed = false;
+
+  for (auto *Callsite : Intrinsics)
+    switch (Callsite->getIntrinsicID()) {
+    case Intrinsic::experimental_gc_get_pointer_base: {
+      Changed = true;
+      Value *Base = findBasePointer(Callsite->getOperand(0), DVCache);
+      assert(!DVCache.count(Callsite));
+      auto *BaseBC = IRBuilder<>(Callsite).CreateBitCast(
+          Base, Callsite->getType(), suffixed_name_or(Base, ".cast", ""));
+      if (BaseBC != Base)
+        DVCache[BaseBC] = Base;
+      Callsite->replaceAllUsesWith(BaseBC);
+      if (!BaseBC->hasName())
+        BaseBC->takeName(Callsite);
+      Callsite->eraseFromParent();
+      break;
+    }
+    case Intrinsic::experimental_gc_get_pointer_offset: {
+      Changed = true;
+      Value *Derived = Callsite->getOperand(0);
+      Value *Base = findBasePointer(Derived, DVCache);
+      assert(!DVCache.count(Callsite));
+      unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();
+      unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);
+      IRBuilder<> Builder(Callsite);
+      Value *BaseInt =
+          Builder.CreatePtrToInt(Base, Type::getIntNTy(Context, IntPtrSize),
+                                 suffixed_name_or(Base, ".int", ""));
+      Value *DerivedInt =
+          Builder.CreatePtrToInt(Derived, Type::getIntNTy(Context, IntPtrSize),
+                                 suffixed_name_or(Derived, ".int", ""));
+      Value *Offset = Builder.CreateSub(DerivedInt, BaseInt);
+      Callsite->replaceAllUsesWith(Offset);
+      Offset->takeName(Callsite);
+      Callsite->eraseFromParent();
+      break;
+    }
+    default:
+      llvm_unreachable("Unknown intrinsic");
+    }
+
+  return Changed;
+}
+
 static bool insertParsePoints(Function &F, DominatorTree &DT,
                               TargetTransformInfo &TTI,
                               SmallVectorImpl<CallBase *> &ToUpdate) {
 #ifndef NDEBUG
   // sanity check the input
   std::set<CallBase *> Uniqued;
   Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
   assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
#endif
   }
 
   // A list of dummy calls added to the IR to keep various values obviously
   // live in the IR.  We'll remove all of these when done.
   SmallVector<CallInst *, 64> Holders;
 
   // Insert a dummy call with all of the deopt operands we'll need for the
   // actual safepoint insertion as arguments.  This ensures reference operands
   // in the deopt argument list are considered live through the safepoint (and
   // thus makes sure they get relocated.)
   for (CallBase *Call : ToUpdate) {
     SmallVector<Value *, 64> DeoptValues;
 
     for (Value *Arg : GetDeoptBundleOperands(Call)) {
       assert(!isUnhandledGCPointerType(Arg->getType()) &&
              "support for FCA unimplemented");
       if (isHandledGCPointerType(Arg->getType()))
#endif
   findLiveReferences(F, DT, ToUpdate, Records);
 
   // B) Find the base pointers for each live pointer
   /* scope for caching */ {
     // Cache the 'defining value' relation used in the computation and
     // insertion of base phis and selects.  This ensures that we don't insert
     // large numbers of duplicate base_phis.
     DefiningValueMapTy DVCache;
-
     for (size_t i = 0; i < Records.size(); i++) {
       PartiallyConstructedSafepointRecord &info = Records[i];
       findBasePointers(DT, DVCache, ToUpdate[i], info);
     }
   } // end of cache scope
 
   // The base phi insertion logic (for any safepoint) may have inserted new
   // instructions which are now live at some safepoint.  The simplest such
bool RewriteStatepointsForGC::runOnFunction(Function &F, DominatorTree &DT,
   bool MadeChange = removeUnreachableBlocks(F, &DTU);
   // Flush the Dominator Tree.
   DTU.getDomTree();
 
   // Gather all the statepoints which need rewritten.  Be careful to only
   // consider those in reachable code since we need to ask dominance queries
   // when rewriting.  We'll delete the unreachable ones in a moment.
   SmallVector<CallBase *, 64> ParsePointNeeded;
+  SmallVector<CallInst *, 64> Intrinsics;
   for (Instruction &I : instructions(F)) {
     // TODO: only the ones with the flag set!
     if (NeedsRewrite(I)) {
       // NOTE removeUnreachableBlocks() is stronger than
       // DominatorTree::isReachableFromEntry(). In other words
       // removeUnreachableBlocks can remove some blocks for which
       // isReachableFromEntry() returns true.
       assert(DT.isReachableFromEntry(I.getParent()) &&
             "no unreachable blocks expected");
       ParsePointNeeded.push_back(cast<CallBase>(&I));
     }
+    if (auto *CI = dyn_cast<CallInst>(&I))
+      if (CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_base ||
+          CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_offset)
+        Intrinsics.emplace_back(CI);
   }
 
   // Return early if no work to do.
-  if (ParsePointNeeded.empty())
+  if (ParsePointNeeded.empty() && Intrinsics.empty())
     return MadeChange;
 
   // As a prepass, go ahead and aggressively destroy single entry phi nodes.
   // These are created by LCSSA.  They have the effect of increasing the size
   // of liveness sets for no good reason.  It may be harder to do this post
   // insertion since relocations and base phis can confuse things.
   for (BasicBlock &BB : F)
     if (BB.getUniquePredecessor())
for (Instruction &I : instructions(F)) {
     if (!I.getOperand(0)->getType()->isVectorTy() && VF != 0) {
       IRBuilder<> B(&I);
       auto *Splat = B.CreateVectorSplat(VF, I.getOperand(0));
       I.setOperand(0, Splat);
       MadeChange = true;
     }
   }
 
+  if (!Intrinsics.empty())
+    // Inline @gc.get.pointer.base() and @gc.get.pointer.offset() before finding
+    // live references.
+    MadeChange |= inlineGetBaseAndOffset(F, Intrinsics);
+
+  if (!ParsePointNeeded.empty())
     MadeChange |= insertParsePoints(F, DT, TTI, ParsePointNeeded);
   return MadeChange;
 }
 
 // liveness computation via standard dataflow
 // -------------------------------------------------------------------
 
 // TODO: Consider using bitvectors for liveness, the set of potentially
 // interesting values should be small and easy to pre-compute.

llvm/test/Transforms/RewriteStatepointsForGC/intrinsics.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
+; Use instcombine to cleanup offset computation.
+; Use gvn to remove duplicate computation.
+; RUN: opt -passes=rewrite-statepoints-for-gc,gvn,instcombine -S < %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128-p1:64:64"
+target triple = "x86_64-apple-macosx10.11.0"
+
+declare i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* readnone nocapture) nounwind readnone willreturn
+declare i8 addrspace(1)* addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1p1i8.p1p1i8(i8 addrspace(1)* addrspace(1)* readnone nocapture) nounwind readnone willreturn
+declare i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* readnone nocapture) nounwind readnone willreturn
+declare i64 @llvm.experimental.gc.get.pointer.offset.p1p1i8(i8 addrspace(1)* addrspace(1)* readnone nocapture) nounwind readnone willreturn
+
+declare void @foo() readonly
+
+define i8 addrspace(1)* addrspace(1)* @test_simple(i8 addrspace(1)* %obj1, i8 addrspace(1)* %obj2, i32 %len, i1 %c) gc "statepoint-example" {
+; CHECK-LABEL: define {{[^@]+}}@test_simple
+; CHECK-SAME: (i8 addrspace(1)* [[OBJ1:%.*]], i8 addrspace(1)* [[OBJ2:%.*]], i32 [[LEN:%.*]], i1 [[C:%.*]]) gc "statepoint-example" {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OBJ1_12:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* [[OBJ1]], i64 12
+; CHECK-NEXT:    [[OBJ2_16:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* [[OBJ2]], i64 16
+; CHECK-NEXT:    [[OBJ_X_BASE1:%.*]] = select i1 [[C]], i8 addrspace(1)* [[OBJ1]], i8 addrspace(1)* [[OBJ2]], !is_base_value !0
+; CHECK-NEXT:    [[OBJ_X:%.*]] = select i1 [[C]], i8 addrspace(1)* [[OBJ1_12]], i8 addrspace(1)* [[OBJ2_16]]
+; CHECK-NEXT:    [[OBJ_Y_BASE:%.*]] = select i1 [[C]], i8 addrspace(1)* [[OBJ2]], i8 addrspace(1)* [[OBJ1]]
+; CHECK-NEXT:    [[OBJ_Y:%.*]] = select i1 [[C]], i8 addrspace(1)* [[OBJ2_16]], i8 addrspace(1)* [[OBJ1_12]]
+; CHECK-NEXT:    [[OBJ_YA:%.*]] = bitcast i8 addrspace(1)* [[OBJ_Y]] to i8 addrspace(1)* addrspace(1)*
+; CHECK-NEXT:    [[OBJ_X_BASE1_INT:%.*]] = ptrtoint i8 addrspace(1)* [[OBJ_X_BASE1]] to i64
+; CHECK-NEXT:    [[OBJ_X_INT:%.*]] = ptrtoint i8 addrspace(1)* [[OBJ_X]] to i64
+; CHECK-NEXT:    [[OBJ_X_OFFSET:%.*]] = sub i64 [[OBJ_X_INT]], [[OBJ_X_BASE1_INT]]
+; CHECK-NEXT:    [[OBJ_Y_BASE_CAST:%.*]] = bitcast i8 addrspace(1)* [[OBJ_Y_BASE]] to i8 addrspace(1)* addrspace(1)*
+; CHECK-NEXT:    [[OBJ_Y_BASE_INT:%.*]] = ptrtoint i8 addrspace(1)* [[OBJ_Y_BASE]] to i64
+; CHECK-NEXT:    [[OBJ_YA_INT:%.*]] = ptrtoint i8 addrspace(1)* [[OBJ_Y]] to i64
+; CHECK-NEXT:    [[OBJ_YA_OFFSET:%.*]] = sub i64 [[OBJ_YA_INT]], [[OBJ_Y_BASE_INT]]
+; CHECK-NEXT:    [[STATEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* nonnull @foo, i32 0, i32 0, i32 0, i32 0) [ "deopt"(i8 addrspace(1)* [[OBJ_X_BASE1]], i64 [[OBJ_X_OFFSET]], i8 addrspace(1)* [[OBJ_X_BASE1]], i64 [[OBJ_X_OFFSET]], i8 addrspace(1)* addrspace(1)* [[OBJ_Y_BASE_CAST]], i64 [[OBJ_YA_OFFSET]]), "gc-live"(i8 addrspace(1)* addrspace(1)* [[OBJ_YA]], i8 addrspace(1)* [[OBJ_Y_BASE]]) ]
+; CHECK-NEXT:    [[OBJ_YA_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 1, i32 0)
+; CHECK-NEXT:    [[OBJ_YA_RELOCATED_CASTED:%.*]] = bitcast i8 addrspace(1)* [[OBJ_YA_RELOCATED]] to i8 addrspace(1)* addrspace(1)*
+; CHECK-NEXT:    ret i8 addrspace(1)* addrspace(1)* [[OBJ_YA_RELOCATED_CASTED]]
+;
+entry:
+  %obj1.12 = getelementptr inbounds i8, i8 addrspace(1)* %obj1, i64 12
+  %obj2.16 = getelementptr inbounds i8, i8 addrspace(1)* %obj2, i64 16
+  %obj.x = select i1 %c, i8 addrspace(1)* %obj1.12, i8 addrspace(1)* %obj2.16
+  %obj.y = select i1 %c, i8 addrspace(1)* %obj2.16, i8 addrspace(1)* %obj1.12
+  %obj.ya = bitcast i8 addrspace(1)* %obj.y to i8 addrspace(1)* addrspace(1)*
+  %obj.x.base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x)
+  %obj.x.offset = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x)
+  %obj.x.base2 = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x)
+  %obj.x.offset2 = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x)
+  %obj.ya.base = call i8 addrspace(1)* addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1p1i8.p1p1i8(i8 addrspace(1)* addrspace(1)* %obj.ya)
+  %obj.ya.offset = call i64 @llvm.experimental.gc.get.pointer.offset.p1p1i8(i8 addrspace(1)* addrspace(1)* %obj.ya)
+  call void @foo() readonly [
+  "deopt"(i8 addrspace(1)* %obj.x.base, i64 %obj.x.offset, i8 addrspace(1)* %obj.x.base2, i64 %obj.x.offset2, i8 addrspace(1)* addrspace(1)* %obj.ya.base, i64 %obj.ya.offset) ]
+  ret i8 addrspace(1)* addrspace(1)* %obj.ya
+}
+
+define void @test_base_of_base(i8 addrspace(1)* %obj1, i8 addrspace(1)* %obj2, i32 %len, i1 %c) gc "statepoint-example" {
+; CHECK-LABEL: define {{[^@]+}}@test_base_of_base
+; CHECK-SAME: (i8 addrspace(1)* [[OBJ1:%.*]], i8 addrspace(1)* [[OBJ2:%.*]], i32 [[LEN:%.*]], i1 [[C:%.*]]) gc "statepoint-example" {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %obj1.12 = getelementptr inbounds i8, i8 addrspace(1)* %obj1, i64 12
+  %obj2.16 = getelementptr inbounds i8, i8 addrspace(1)* %obj2, i64 16
+  %obj.x = select i1 %c, i8 addrspace(1)* %obj1.12, i8 addrspace(1)* %obj2.16
+
+  %obj.x.base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x)
+  %obj.x.base_of_base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x.base)
+
+  ret void
+}
+
+define i8 addrspace(1)* @test_chained(i8 addrspace(1)* %obj1, i8 addrspace(1)* %obj2, i32 %len, i1 %c) gc "statepoint-example" {
+; CHECK-LABEL: define {{[^@]+}}@test_chained
+; CHECK-SAME: (i8 addrspace(1)* [[OBJ1:%.*]], i8 addrspace(1)* [[OBJ2:%.*]], i32 [[LEN:%.*]], i1 [[C:%.*]]) gc "statepoint-example" {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[OBJ_X_BASE1:%.*]] = select i1 [[C]], i8 addrspace(1)* [[OBJ1]], i8 addrspace(1)* [[OBJ2]], !is_base_value !0
+; CHECK-NEXT:    [[OBJ_X_BASE_GEP:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* [[OBJ_X_BASE1]], i64 8
+; CHECK-NEXT:    [[OBJ_X_BASE_OF_BASE_GEP:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* [[OBJ_X_BASE1]], i64 20
+; CHECK-NEXT:    [[OBJ_X_BASE_OF_BASE_OF_BASE_GEP:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* [[OBJ_X_BASE1]], i64 24
+; CHECK-NEXT:    [[STATEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* nonnull @foo, i32 0, i32 0, i32 0, i32 0) [ "deopt"(i8 addrspace(1)* [[OBJ_X_BASE1]], i8 addrspace(1)* [[OBJ_X_BASE1]], i8 addrspace(1)* [[OBJ_X_BASE1]], i8 addrspace(1)* [[OBJ_X_BASE_GEP]], i8 addrspace(1)* [[OBJ_X_BASE_OF_BASE_GEP]], i8 addrspace(1)* [[OBJ_X_BASE_OF_BASE_OF_BASE_GEP]], i8 addrspace(1)* [[OBJ_X_BASE1]], i8 addrspace(1)* [[OBJ_X_BASE1]], i8 addrspace(1)* [[OBJ_X_BASE1]], i64 0, i64 0, i64 0, i64 8, i64 20, i64 24, i64 0, i64 0, i64 0), "gc-live"(i8 addrspace(1)* [[OBJ_X_BASE1]]) ]
+; CHECK-NEXT:    [[OBJ_X_BASE1_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 0, i32 0)
+; CHECK-NEXT:    ret i8 addrspace(1)* [[OBJ_X_BASE1_RELOCATED]]
+;
+entry:
+  %obj1.12 = getelementptr inbounds i8, i8 addrspace(1)* %obj1, i64 12
+  %obj2.16 = getelementptr inbounds i8, i8 addrspace(1)* %obj2, i64 16
+  %obj.x = select i1 %c, i8 addrspace(1)* %obj1.12, i8 addrspace(1)* %obj2.16
+
+  %obj.x.base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x)
+  %obj.x.base_of_base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x.base)
+  %obj.x.base_of_base_of_base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x.base_of_base)
+
+  %obj.x.base_gep                 = getelementptr inbounds i8, i8 addrspace(1)* %obj.x.base, i64 8
+  %obj.x.base_of_base_gep         = getelementptr inbounds i8, i8 addrspace(1)* %obj.x.base_of_base, i64 20
+  %obj.x.base_of_base_of_base_gep = getelementptr inbounds i8, i8 addrspace(1)* %obj.x.base_of_base_of_base, i64 24
+
+  %obj.x.base_gep_base                 = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x.base_gep)
+  %obj.x.base_of_base_gep_base         = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x.base_of_base_gep)
+  %obj.x.base_of_base_of_base_gep_base = call i8 addrspace(1)* @llvm.experimental.gc.get.pointer.base.p1i8.p1i8(i8 addrspace(1)* %obj.x.base_of_base_of_base_gep)
+
+  %obj.x.base_offset                          = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x.base)
+  %obj.x.base_of_base_offset                  = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x.base_of_base)
+  %obj.x.base_of_base_of_base_offset          = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x.base_of_base_of_base)
+  %obj.x.base_gep_offset                      = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x.base_gep)
+  %obj.x.base_of_base_gep_offset              = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x.base_of_base_gep)
+  %obj.x.base_of_base_of_base_gep_offset      = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x.base_of_base_of_base_gep)
+  %obj.x.base_gep_base_offset                 = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x.base_gep_base)
+  %obj.x.base_of_base_gep_base_offset         = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x.base_of_base_gep_base)
+  %obj.x.base_of_base_of_base_gep_base_offset = call i64 @llvm.experimental.gc.get.pointer.offset.p1i8(i8 addrspace(1)* %obj.x.base_of_base_of_base_gep_base)
+
+  call void @foo() readonly [
+  "deopt"(
+      i8 addrspace(1)* %obj.x.base,
+      i8 addrspace(1)* %obj.x.base_of_base_of_base,
+      i8 addrspace(1)* %obj.x.base_of_base,
+      i8 addrspace(1)* %obj.x.base_gep,
+      i8 addrspace(1)* %obj.x.base_of_base_gep,
+      i8 addrspace(1)* %obj.x.base_of_base_of_base_gep,
+      i8 addrspace(1)* %obj.x.base_gep_base,
+      i8 addrspace(1)* %obj.x.base_of_base_gep_base,
+      i8 addrspace(1)* %obj.x.base_of_base_of_base_gep_base,
+      i64 %obj.x.base_offset,
+      i64 %obj.x.base_of_base_offset,
+      i64 %obj.x.base_of_base_of_base_offset,
+      i64 %obj.x.base_gep_offset,
+      i64 %obj.x.base_of_base_gep_offset,
+      i64 %obj.x.base_of_base_of_base_gep_offset,
+      i64 %obj.x.base_gep_base_offset,
+      i64 %obj.x.base_of_base_gep_base_offset,
+      i64 %obj.x.base_of_base_of_base_gep_base_offset) ]
+
+  ret i8 addrspace(1)* %obj.x.base_of_base
+}