diff --git a/passes/CMakeLists.txt b/passes/CMakeLists.txt
index 7e199ec..4c5a3c0 100644
--- a/passes/CMakeLists.txt
+++ b/passes/CMakeLists.txt
@@ -8,4 +8,6 @@
 
 add_llvm_library(LLVMCppGoPasses
   GoAnnotation.cpp
+  GoStatepoints.cpp
+  Util.cpp
 )
diff --git a/passes/GoStatepoints.cpp b/passes/GoStatepoints.cpp
new file mode 100644
index 0000000..c303582
--- /dev/null
+++ b/passes/GoStatepoints.cpp
@@ -0,0 +1,2658 @@
+//===- GoStatepoints.cpp - Insert statepoints for Go GC -------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Rewrite call/invoke instructions so as to record live variables on
+// stack for the use of garbage collector.
+//
+//===----------------------------------------------------------------------===//
+
+#include "GoStatepoints.h"
+#include "GoStackMap.h"
+#include "GollvmPasses.h"
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/None.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/Argument.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/CallingConv.h"
+#include "llvm/IR/Constant.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/DomTreeUpdater.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Statepoint.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/PromoteMemToReg.h"
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <cstdint>
+#include <iterator>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#define DEBUG_TYPE "go-statepoints"
+
+using namespace llvm;
+using namespace gollvm::passes;
+
+// Print the liveset found at the insert location
+static cl::opt<bool> PrintLiveSet("gogc-print-liveset", cl::Hidden,
+                                  cl::init(false));
+
+// Print the liveset only for the specified function.
+static cl::opt<std::string> PrintFunc("gogc-print-func", cl::Hidden,
+                                      cl::init(""));
+
+// TODO: make sure ClobberNonLive work. In the original code it
+// is to clobber non-relocated pointers. We'll need a different
+// mechanism.
+static cl::opt<bool> ClobberNonLive("gogc-clobber-non-live",
+                                    cl::Hidden, cl::init(false));
+
+// Statepoint ID. TODO: this is not thread safe.
+static uint64_t ID = 0;
+
+/// The IR fed into this pass may have had attributes and
+/// metadata implying dereferenceability that are no longer valid/correct after
+/// this pass has run. This is because semantically, after
+/// this pass runs, all calls to gc.statepoint "free" the entire
+/// heap. stripNonValidData (conservatively) restores
+/// correctness by erasing all attributes in the module that externally imply
+/// dereferenceability. Similar reasoning also applies to the noalias
+/// attributes and metadata. gc.statepoint can touch the entire heap including
+/// noalias objects.
+/// Apart from attributes and metadata, we also remove instructions that imply
+/// constant physical memory: llvm.invariant.start.
+//
+// TODO: revisit this. For a non-moving GC some attributes may still be valid.
+// It probably doesn't really matter, as we run this pass at the end of
+// optimization pipeline.
+static void stripNonValidData(Module &M);
+
+static bool shouldRewriteStatepointsIn(Function &F);
+
+PreservedAnalyses GoStatepoints::run(Module &M,
+                                     ModuleAnalysisManager &AM) {
+  // Create a sentinel global variable for stack maps.
+  Type *Int64Ty = Type::getInt64Ty(M.getContext());
+  new GlobalVariable(M, Int64Ty, /* isConstant */ true,
+                     GlobalValue::InternalLinkage,
+                     ConstantInt::get(Int64Ty, GO_FUNC_SENTINEL),
+                     GO_FUNC_SYM);
+
+  bool Changed = false;
+  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+  for (Function &F : M) {
+    // Nothing to do for declarations.
+    if (F.isDeclaration() || F.empty())
+      continue;
+
+    // Policy choice says not to rewrite - the most common reason is that we're
+    // compiling code without a GCStrategy.
+    if (!shouldRewriteStatepointsIn(F))
+      continue;
+
+    auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
+    auto &TTI = FAM.getResult<TargetIRAnalysis>(F);
+    auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
+    Changed |= runOnFunction(F, DT, TTI, TLI);
+  }
+  if (!Changed)
+    return PreservedAnalyses::all();
+
+  // stripNonValidData asserts that shouldRewriteStatepointsIn
+  // returns true for at least one function in the module.  Since at least
+  // one function changed, we know that the precondition is satisfied.
+  stripNonValidData(M);
+
+  PreservedAnalyses PA;
+  PA.preserve<TargetIRAnalysis>();
+  PA.preserve<TargetLibraryAnalysis>();
+  return PA;
+}
+
+namespace {
+
+class GoStatepointsLegacyPass : public ModulePass {
+  GoStatepoints Impl;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  GoStatepointsLegacyPass() : ModulePass(ID), Impl() {
+    initializeGoStatepointsLegacyPassPass(
+        *PassRegistry::getPassRegistry());
+  }
+
+  bool runOnModule(Module &M) override {
+    // Create a sentinel global variable for stack maps.
+    Type *Int64Ty = Type::getInt64Ty(M.getContext());
+    new GlobalVariable(M, Int64Ty, /* isConstant */ true,
+                       GlobalValue::InternalLinkage,
+                       ConstantInt::get(Int64Ty, GO_FUNC_SENTINEL),
+                       GO_FUNC_SYM);
+
+    bool Changed = false;
+    const TargetLibraryInfo &TLI =
+        getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+    for (Function &F : M) {
+      // Nothing to do for declarations.
+      if (F.isDeclaration() || F.empty())
+        continue;
+
+      // Policy choice says not to rewrite - the most common reason is that
+      // we're compiling code without a GCStrategy.
+      if (!shouldRewriteStatepointsIn(F))
+        continue;
+
+      TargetTransformInfo &TTI =
+          getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
+      auto &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
+
+      Changed |= Impl.runOnFunction(F, DT, TTI, TLI);
+    }
+
+    if (!Changed)
+      return false;
+
+    // stripNonValidData asserts that shouldRewriteStatepointsIn
+    // returns true for at least one function in the module.  Since at least
+    // one function changed, we know that the precondition is satisfied.
+    stripNonValidData(M);
+    return true;
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    // We add and rewrite a bunch of instructions, but don't really do much
+    // else.  We could in theory preserve a lot more analyses here.
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
+  }
+};
+
+} // end anonymous namespace
+
+char GoStatepointsLegacyPass::ID = 0;
+
+ModulePass *llvm::createGoStatepointsLegacyPass() {
+  return new GoStatepointsLegacyPass();
+}
+
+INITIALIZE_PASS_BEGIN(GoStatepointsLegacyPass,
+                      "go-statepoints",
+                      "Insert statepoints for Go GC", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_END(GoStatepointsLegacyPass,
+                    "go-statepoints",
+                    "Insert statepoints for Go GC", false, false)
+
+namespace {
+
+// Liveness tracking has three parts: in-register values, non-address-taken
+// allocas (stack slots), and address-taken allocas.
+//
+// In-register values are live since it is defined, until it has no more
+// use. At statepoints they are spilled so the runtime can find them on
+// the stack.
+//
+// Non-address-taken allocas are live since it is initialized, until it
+// has no more use. At statepoints they are not spilled but its stack
+// location is recorded.
+//
+// Address-taken allocas are live since it is initialized and remain live
+// thereafter, unless an explicit lifetime.end is seen. As above, they
+// are not spilled at statepoints but has its stack location recorded.
+//
+// In the data structure, there are some overlap. The live sets are used
+// for both in-register values and non-address-taken allocas, but not
+// for address-taken allocas. The alloca def/kill sets are used for both
+// kinds of allocas.
+struct GCPtrLivenessData {
+  // In-register value and non-address-taken alloca.
+
+  /// Values defined in this block.
+  MapVector<BasicBlock *, SetVector<Value *>> KillSet;
+  /// Values used in this block (and thus live); does not included values
+  /// killed within this block.
+  MapVector<BasicBlock *, SetVector<Value *>> LiveSet;
+  /// Values live into this basic block (i.e. used by any
+  /// instruction in this basic block or ones reachable from here)
+  MapVector<BasicBlock *, SetVector<Value *>> LiveIn;
+  /// Values live out of this basic block (i.e. live into
+  /// any successor block)
+  MapVector<BasicBlock *, SetVector<Value *>> LiveOut;
+
+  // Alloca liveness.
+
+  MapVector<BasicBlock *, SetVector<Value *>> AllocaDefSet;  // initialized in BB
+  MapVector<BasicBlock *, SetVector<Value *>> AllocaKillSet; // killed (lifetime.end) in BB
+
+  // Unlike above, these are propagated forwards, instead of backwards.
+  MapVector<BasicBlock *, SetVector<Value *>> AllocaDefAny; // initialized at any path reaching the end of BB
+  MapVector<BasicBlock *, SetVector<Value *>> AllocaDefAll; // initialized at all paths reaching the end of BB
+};
+
+// The type of the internal cache used inside the findBasePointers family
+// of functions.  From the callers perspective, this is an opaque type and
+// should not be inspected.
+//
+// In the actual implementation this caches two relations:
+// - The base relation itself (i.e. this pointer is based on that one)
+// - The base defining value relation (i.e. before base_phi insertion)
+// Generally, after the execution of a full findBasePointer call, only the
+// base relation will remain.  Internally, we add a mixture of the two
+// types, then update all the second type to the first type
+using DefiningValueMapTy = MapVector<Value *, Value *>;
+using StatepointLiveSetTy = SetVector<Value *>;
+using RematerializedValueMapTy =
+    MapVector<AssertingVH<Instruction>, AssertingVH<Value>>;
+
+struct PartiallyConstructedSafepointRecord {
+  /// The set of values known to be live across this safepoint
+  StatepointLiveSetTy LiveSet;
+
+  /// Mapping from live pointers to a base-defining-value
+  MapVector<Value *, Value *> PointerToBase;
+
+  /// The *new* gc.statepoint instruction itself.  This produces the token
+  /// that normal path gc.relocates and the gc.result are tied to.
+  Instruction *StatepointToken;
+
+  /// Instruction to which exceptional gc relocates are attached
+  /// Makes it easier to iterate through them during relocationViaAlloca.
+  Instruction *UnwindToken;
+
+  /// Record live values we are rematerialized instead of relocating.
+  /// They are not included into 'LiveSet' field.
+  /// Maps rematerialized copy to it's original value.
+  RematerializedValueMapTy RematerializedValues;
+};
+
+} // end anonymous namespace
+
+/// Compute the live-in set for every basic block in the function
+static void computeLiveInValues(DominatorTree &DT, Function &F,
+                                GCPtrLivenessData &Data,
+                                SetVector<Value *> &AddrTakenAllocas,
+                                SetVector<Value *> &ToZero,
+                                DefiningValueMapTy &DVCache);
+
+/// Given results from the dataflow liveness computation, find the set of live
+/// Values at a particular instruction.
+static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,
+                              SetVector<Value *> &AddrTakenAllocas,
+                              StatepointLiveSetTy &out,
+                              DefiningValueMapTy &DVCache);
+
+// TODO: Once we can get to the GCStrategy, this becomes
+// Optional<bool> isGCManagedPointer(const Type *Ty) const override {
+
+static bool isGCPointerType(Type *T) {
+  return isa<PointerType>(T);
+}
+
+// Return true if this type is one which a) is a gc pointer or contains a GC
+// pointer and b) is of a type this code expects to encounter as a live value.
+// (The insertion code will assert that a type which matches (a) and not (b)
+// is not encountered.)
+static bool isHandledGCPointerType(Type *T) {
+  // We fully support gc pointers
+  if (isGCPointerType(T))
+    return true;
+  // We partially support vectors of gc pointers. The code will assert if it
+  // can't handle something.
+  if (auto VT = dyn_cast<VectorType>(T))
+    if (isGCPointerType(VT->getElementType()))
+      return true;
+  return false;
+}
+
+#ifndef NDEBUG
+/// Returns true if this type contains a gc pointer whether we know how to
+/// handle that type or not.
+static bool containsGCPtrType(Type *Ty) {
+  if (isGCPointerType(Ty))
+    return true;
+  if (VectorType *VT = dyn_cast<VectorType>(Ty))
+    return isGCPointerType(VT->getScalarType());
+  if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
+    return containsGCPtrType(AT->getElementType());
+  if (StructType *ST = dyn_cast<StructType>(Ty))
+    return llvm::any_of(ST->subtypes(), containsGCPtrType);
+  return false;
+}
+
+// Returns true if this is a type which a) is a gc pointer or contains a GC
+// pointer and b) is of a type which the code doesn't expect (i.e. first class
+// aggregates).  Used to trip assertions.
+static bool isUnhandledGCPointerType(Type *Ty) {
+  return containsGCPtrType(Ty) && !isHandledGCPointerType(Ty);
+}
+#endif
+
+// Return the name of the value suffixed with the provided value, or if the
+// value didn't have a name, the default value specified.
+static std::string suffixed_name_or(Value *V, StringRef Suffix,
+                                    StringRef DefaultName) {
+  return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.str();
+}
+
+// Helper function to print a live set, for debugging.
+static void
+printLiveSet(SetVector<Value *> &LiveSet) {
+  for (Value *V : LiveSet)
+    dbgs() << "\t" << *V << "\n";
+}
+
+// Conservatively identifies any definitions which might be live at the
+// given instruction. The  analysis is performed immediately before the
+// given instruction. Values defined by that instruction are not considered
+// live.  Values used by that instruction are considered live.
+static void
+analyzeParsePointLiveness(DominatorTree &DT,
+                          GCPtrLivenessData &OriginalLivenessData,
+                          SetVector<Value *> &AddrTakenAllocas, CallSite CS,
+                          PartiallyConstructedSafepointRecord &Result,
+                          DefiningValueMapTy &DVCache) {
+  Instruction *Inst = CS.getInstruction();
+
+  StatepointLiveSetTy LiveSet;
+  findLiveSetAtInst(Inst, OriginalLivenessData, AddrTakenAllocas, LiveSet, DVCache);
+
+  if (PrintLiveSet) {
+    dbgs() << "Live Variables at " << *Inst << ":\n";
+    printLiveSet(LiveSet);
+  }
+  Result.LiveSet = LiveSet;
+}
+
+static bool isKnownBaseResult(Value *V);
+
+namespace {
+
+/// A single base defining value - An immediate base defining value for an
+/// instruction 'Def' is an input to 'Def' whose base is also a base of 'Def'.
+/// For instructions which have multiple pointer [vector] inputs or that
+/// transition between vector and scalar types, there is no immediate base
+/// defining value.  The 'base defining value' for 'Def' is the transitive
+/// closure of this relation stopping at the first instruction which has no
+/// immediate base defining value.  The b.d.v. might itself be a base pointer,
+/// but it can also be an arbitrary derived pointer.
+struct BaseDefiningValueResult {
+  /// Contains the value which is the base defining value.
+  Value * const BDV;
+
+  /// True if the base defining value is also known to be an actual base
+  /// pointer.
+  const bool IsKnownBase;
+
+  BaseDefiningValueResult(Value *BDV, bool IsKnownBase)
+    : BDV(BDV), IsKnownBase(IsKnownBase) {
+#ifndef NDEBUG
+    // Check consistency between new and old means of checking whether a BDV is
+    // a base.
+    bool MustBeBase = isKnownBaseResult(BDV);
+    assert(!MustBeBase || MustBeBase == IsKnownBase);
+#endif
+  }
+};
+
+} // end anonymous namespace
+
+static BaseDefiningValueResult findBaseDefiningValue(Value *I);
+
+/// Return a base defining value for the 'Index' element of the given vector
+/// instruction 'I'.  If Index is null, returns a BDV for the entire vector
+/// 'I'.  As an optimization, this method will try to determine when the
+/// element is known to already be a base pointer.  If this can be established,
+/// the second value in the returned pair will be true.  Note that either a
+/// vector or a pointer typed value can be returned.  For the former, the
+/// vector returned is a BDV (and possibly a base) of the entire vector 'I'.
+/// If the later, the return pointer is a BDV (or possibly a base) for the
+/// particular element in 'I'.
+static BaseDefiningValueResult
+findBaseDefiningValueOfVector(Value *I) {
+  // Each case parallels findBaseDefiningValue below, see that code for
+  // detailed motivation.
+
+  if (isa<Argument>(I))
+    // An incoming argument to the function is a base pointer
+    return BaseDefiningValueResult(I, true);
+
+  if (isa<Constant>(I))
+    // Base of constant vector consists only of constant null pointers.
+    // For reasoning see similar case inside 'findBaseDefiningValue' function.
+    return BaseDefiningValueResult(ConstantAggregateZero::get(I->getType()),
+                                   true);
+
+  if (isa<LoadInst>(I))
+    return BaseDefiningValueResult(I, true);
+
+  if (isa<InsertElementInst>(I))
+    // We don't know whether this vector contains entirely base pointers or
+    // not.  To be conservatively correct, we treat it as a BDV and will
+    // duplicate code as needed to construct a parallel vector of bases.
+    return BaseDefiningValueResult(I, false);
+
+  if (isa<ShuffleVectorInst>(I))
+    // We don't know whether this vector contains entirely base pointers or
+    // not.  To be conservatively correct, we treat it as a BDV and will
+    // duplicate code as needed to construct a parallel vector of bases.
+    // TODO: There a number of local optimizations which could be applied here
+    // for particular sufflevector patterns.
+    return BaseDefiningValueResult(I, false);
+
+  // The behavior of getelementptr instructions is the same for vector and
+  // non-vector data types.
+  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
+    return findBaseDefiningValue(GEP->getPointerOperand());
+
+  // If the pointer comes through a bitcast of a vector of pointers to
+  // a vector of another type of pointer, then look through the bitcast
+  if (auto *BC = dyn_cast<BitCastInst>(I))
+    return findBaseDefiningValue(BC->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);
+
+  // A PHI or Select is a base defining value.  The outer findBasePointer
+  // algorithm is responsible for constructing a base value for this BDV.
+  assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&
+         "unknown vector instruction - no base found for vector element");
+  return BaseDefiningValueResult(I, false);
+}
+
+/// Helper function for findBasePointer - Will return a value which either a)
+/// defines the base pointer for the input, b) blocks the simple search
+/// (i.e. a PHI or Select of two derived pointers), or c) involves a change
+/// from pointer to vector type or back.
+static BaseDefiningValueResult findBaseDefiningValue(Value *I) {
+  assert(I->getType()->isPtrOrPtrVectorTy() &&
+         "Illegal to ask for the base pointer of a non-pointer type");
+
+  if (I->getType()->isVectorTy())
+    return findBaseDefiningValueOfVector(I);
+
+  if (isa<Argument>(I))
+    // An incoming argument to the function is a base pointer
+    // We should have never reached here if this argument isn't an gc value
+    return BaseDefiningValueResult(I, true);
+
+  if (isa<Constant>(I)) {
+    // We assume that objects with a constant base (e.g. a global) can't move
+    // and don't need to be reported to the collector because they are always
+    // live. Besides global references, all kinds of constants (e.g. undef,
+    // constant expressions, null pointers) can be introduced by the inliner or
+    // the optimizer, especially on dynamically dead paths.
+    // Here we treat all of them as having single null base. By doing this we
+    // trying to avoid problems reporting various conflicts in a form of
+    // "phi (const1, const2)" or "phi (const, regular gc ptr)".
+    // See constant.ll file for relevant test cases.
+
+    return BaseDefiningValueResult(
+        ConstantPointerNull::get(cast<PointerType>(I->getType())), true);
+  }
+
+  if (CastInst *CI = dyn_cast<CastInst>(I)) {
+    Value *Def = CI->stripPointerCasts();
+    if (isa<IntToPtrInst>(Def))
+      // Pointer converted from integer is a base.
+      return BaseDefiningValueResult(Def, true);
+
+    // Pointer-to-pointer and int-to-pointer casts are handled above.
+    // We don't know how to handle other type of casts.
+    assert(!isa<CastInst>(Def) && "shouldn't find another cast here");
+    return findBaseDefiningValue(Def);
+  }
+
+  if (isa<AllocaInst>(I))
+    // alloca is a gc base
+    return BaseDefiningValueResult(I, true);
+
+  if (isa<LoadInst>(I))
+    // The value loaded is a gc base itself
+    return BaseDefiningValueResult(I, true);
+
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I))
+    // The base of this GEP is the base
+    return findBaseDefiningValue(GEP->getPointerOperand());
+
+  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+    switch (II->getIntrinsicID()) {
+    default:
+      // fall through to general call handling
+      break;
+    case Intrinsic::experimental_gc_statepoint:
+      llvm_unreachable("statepoints don't produce pointers");
+    case Intrinsic::experimental_gc_relocate:
+      // Rerunning safepoint insertion after safepoints are already
+      // inserted is not supported.  It could probably be made to work,
+      // 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");
+    }
+  }
+  // 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);
+
+  // TODO: I have absolutely no idea how to implement this part yet.  It's not
+  // necessarily hard, I just haven't really looked at it yet.
+  assert(!isa<LandingPadInst>(I) && "Landing Pad is unimplemented");
+
+  if (isa<AtomicCmpXchgInst>(I))
+    // A CAS is effectively a atomic store and load combined under a
+    // predicate.  From the perspective of base pointers, we just treat it
+    // like a load.
+    return BaseDefiningValueResult(I, true);
+
+  assert(!isa<AtomicRMWInst>(I) && "Xchg handled above, all others are "
+                                   "binary ops which don't apply to pointers");
+
+  // The aggregate ops.  Aggregates can either be in the heap or on the
+  // stack, but in either case, this is simply a field load.  As a result,
+  // this is a defining definition of the base just like a load is.
+  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");
+
+  // 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);
+
+  // 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);
+}
+
+/// 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() << " -> "
+                      << Cached->getName() << "\n");
+  }
+  assert(Cache[I] != nullptr);
+  return Cached;
+}
+
+/// Return a base pointer for this value if known.  Otherwise, return it's
+/// base defining value.
+static Value *findBaseOrBDV(Value *I, DefiningValueMapTy &Cache) {
+  Value *Def = findBaseDefiningValueCached(I, Cache);
+  auto Found = Cache.find(Def);
+  if (Found != Cache.end()) {
+    // Either a base-of relation, or a self reference.  Caller must check.
+    return Found->second;
+  }
+  // Only a BDV available
+  return Def;
+}
+
+/// Given the result of a call to findBaseDefiningValue, or findBaseOrBDV,
+/// is it known to be a base pointer?  Or do we need to continue searching.
+static bool isKnownBaseResult(Value *V) {
+  if (!isa<PHINode>(V) && !isa<SelectInst>(V) &&
+      !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&
+      !isa<ShuffleVectorInst>(V)) {
+    // no recursion possible
+    return true;
+  }
+  if (isa<Instruction>(V) &&
+      cast<Instruction>(V)->getMetadata("is_base_value")) {
+    // This is a previously inserted base phi or select.  We know
+    // that this is a base value.
+    return true;
+  }
+
+  // We need to keep searching
+  return false;
+}
+
+namespace {
+
+/// Models the state of a single base defining value in the findBasePointer
+/// algorithm for determining where a new instruction is needed to propagate
+/// the base of this BDV.
+class BDVState {
+public:
+  enum Status { Unknown, Base, Conflict };
+
+  BDVState() : BaseValue(nullptr) {}
+
+  explicit BDVState(Status Status, Value *BaseValue = nullptr)
+      : Status(Status), BaseValue(BaseValue) {
+    assert(Status != Base || BaseValue);
+  }
+
+  explicit BDVState(Value *BaseValue) : Status(Base), BaseValue(BaseValue) {}
+
+  Status getStatus() const { return Status; }
+  Value *getBaseValue() const { return BaseValue; }
+
+  bool isBase() const { return getStatus() == Base; }
+  bool isUnknown() const { return getStatus() == Unknown; }
+  bool isConflict() const { return getStatus() == Conflict; }
+
+  bool operator==(const BDVState &Other) const {
+    return BaseValue == Other.BaseValue && Status == Other.Status;
+  }
+
+  bool operator!=(const BDVState &other) const { return !(*this == other); }
+
+  LLVM_DUMP_METHOD
+  void dump() const {
+    print(dbgs());
+    dbgs() << '\n';
+  }
+
+  void print(raw_ostream &OS) const {
+    switch (getStatus()) {
+    case Unknown:
+      OS << "U";
+      break;
+    case Base:
+      OS << "B";
+      break;
+    case Conflict:
+      OS << "C";
+      break;
+    }
+    OS << " (" << getBaseValue() << " - "
+       << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << "): ";
+  }
+
+private:
+  Status Status = Unknown;
+  AssertingVH<Value> BaseValue; // Non-null only if Status == Base.
+};
+
+} // end anonymous namespace
+
+#ifndef NDEBUG
+static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) {
+  State.print(OS);
+  return OS;
+}
+#endif
+
+static BDVState meetBDVStateImpl(const BDVState &LHS, const BDVState &RHS) {
+  switch (LHS.getStatus()) {
+  case BDVState::Unknown:
+    return RHS;
+
+  case BDVState::Base:
+    assert(LHS.getBaseValue() && "can't be null");
+    if (RHS.isUnknown())
+      return LHS;
+
+    if (RHS.isBase()) {
+      if (LHS.getBaseValue() == RHS.getBaseValue()) {
+        assert(LHS == RHS && "equality broken!");
+        return LHS;
+      }
+      return BDVState(BDVState::Conflict);
+    }
+    assert(RHS.isConflict() && "only three states!");
+    return BDVState(BDVState::Conflict);
+
+  case BDVState::Conflict:
+    return LHS;
+  }
+  llvm_unreachable("only three states!");
+}
+
+// Values of type BDVState form a lattice, and this function implements the meet
+// operation.
+static BDVState meetBDVState(const BDVState &LHS, const BDVState &RHS) {
+  BDVState Result = meetBDVStateImpl(LHS, RHS);
+  assert(Result == meetBDVStateImpl(RHS, LHS) &&
+         "Math is wrong: meet does not commute!");
+  return Result;
+}
+
+/// For a given value or instruction, figure out what base ptr its derived from.
+/// For gc objects, this is simply itself.  On success, returns a value which is
+/// the base pointer.  (This is reliable and can be used for relocation.)  On
+/// failure, returns nullptr.
+static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache) {
+  Value *Def = findBaseOrBDV(I, Cache);
+
+  if (isKnownBaseResult(Def))
+    return Def;
+
+  // Here's the rough algorithm:
+  // - For every SSA value, construct a mapping to either an actual base
+  //   pointer or a PHI which obscures the base pointer.
+  // - Construct a mapping from PHI to unknown TOP state.  Use an
+  //   optimistic algorithm to propagate base pointer information.  Lattice
+  //   looks like:
+  //   UNKNOWN
+  //   b1 b2 b3 b4
+  //   CONFLICT
+  //   When algorithm terminates, all PHIs will either have a single concrete
+  //   base or be in a conflict state.
+  // - For every conflict, insert a dummy PHI node without arguments.  Add
+  //   these to the base[Instruction] = BasePtr mapping.  For every
+  //   non-conflict, add the actual base.
+  //  - For every conflict, add arguments for the base[a] of each input
+  //   arguments.
+  //
+  // Note: A simpler form of this would be to add the conflict form of all
+  // PHIs without running the optimistic algorithm.  This would be
+  // analogous to pessimistic data flow and would likely lead to an
+  // overall worse solution.
+
+#ifndef NDEBUG
+  auto isExpectedBDVType = [](Value *BDV) {
+    return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||
+           isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) ||
+           isa<ShuffleVectorInst>(BDV);
+  };
+#endif
+
+  // Once populated, will contain a mapping from each potentially non-base BDV
+  // to a lattice value (described above) which corresponds to that BDV.
+  // We use the order of insertion (DFS over the def/use graph) to provide a
+  // stable deterministic ordering for visiting DenseMaps (which are unordered)
+  // below.  This is important for deterministic compilation.
+  MapVector<Value *, BDVState> States;
+
+  // Recursively fill in all base defining values reachable from the initial
+  // one for which we don't already know a definite base value for
+  /* scope */ {
+    SmallVector<Value*, 16> Worklist;
+    Worklist.push_back(Def);
+    States.insert({Def, BDVState()});
+    while (!Worklist.empty()) {
+      Value *Current = Worklist.pop_back_val();
+      assert(!isKnownBaseResult(Current) && "why did it get added?");
+
+      auto visitIncomingValue = [&](Value *InVal) {
+        Value *Base = findBaseOrBDV(InVal, Cache);
+        if (isKnownBaseResult(Base))
+          // Known bases won't need new instructions introduced and can be
+          // ignored safely
+          return;
+        assert(isExpectedBDVType(Base) && "the only non-base values "
+               "we see should be base defining values");
+        if (States.insert(std::make_pair(Base, BDVState())).second)
+          Worklist.push_back(Base);
+      };
+      if (PHINode *PN = dyn_cast<PHINode>(Current)) {
+        for (Value *InVal : PN->incoming_values())
+          visitIncomingValue(InVal);
+      } else if (SelectInst *SI = dyn_cast<SelectInst>(Current)) {
+        visitIncomingValue(SI->getTrueValue());
+        visitIncomingValue(SI->getFalseValue());
+      } else if (auto *EE = dyn_cast<ExtractElementInst>(Current)) {
+        visitIncomingValue(EE->getVectorOperand());
+      } else if (auto *IE = dyn_cast<InsertElementInst>(Current)) {
+        visitIncomingValue(IE->getOperand(0)); // vector operand
+        visitIncomingValue(IE->getOperand(1)); // scalar operand
+      } else if (auto *SV = dyn_cast<ShuffleVectorInst>(Current)) {
+        visitIncomingValue(SV->getOperand(0));
+        visitIncomingValue(SV->getOperand(1));
+      }
+      else {
+        llvm_unreachable("Unimplemented instruction case");
+      }
+    }
+  }
+
+#ifndef NDEBUG
+  LLVM_DEBUG(dbgs() << "States after initialization:\n");
+  for (auto Pair : States) {
+    LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
+  }
+#endif
+
+  // Return a phi state for a base defining value.  We'll generate a new
+  // base state for known bases and expect to find a cached state otherwise.
+  auto getStateForBDV = [&](Value *baseValue) {
+    if (isKnownBaseResult(baseValue))
+      return BDVState(baseValue);
+    auto I = States.find(baseValue);
+    assert(I != States.end() && "lookup failed!");
+    return I->second;
+  };
+
+  bool Progress = true;
+  while (Progress) {
+#ifndef NDEBUG
+    const size_t OldSize = States.size();
+#endif
+    Progress = false;
+    // We're only changing values in this loop, thus safe to keep iterators.
+    // Since this is computing a fixed point, the order of visit does not
+    // effect the result.  TODO: We could use a worklist here and make this run
+    // much faster.
+    for (auto Pair : States) {
+      Value *BDV = Pair.first;
+      assert(!isKnownBaseResult(BDV) && "why did it get added?");
+
+      // Given an input value for the current instruction, return a BDVState
+      // instance which represents the BDV of that value.
+      auto getStateForInput = [&](Value *V) mutable {
+        Value *BDV = findBaseOrBDV(V, Cache);
+        return getStateForBDV(BDV);
+      };
+
+      BDVState NewState;
+      if (SelectInst *SI = dyn_cast<SelectInst>(BDV)) {
+        NewState = meetBDVState(NewState, getStateForInput(SI->getTrueValue()));
+        NewState =
+            meetBDVState(NewState, getStateForInput(SI->getFalseValue()));
+      } else if (PHINode *PN = dyn_cast<PHINode>(BDV)) {
+        for (Value *Val : PN->incoming_values())
+          NewState = meetBDVState(NewState, getStateForInput(Val));
+      } else if (auto *EE = dyn_cast<ExtractElementInst>(BDV)) {
+        // The 'meet' for an extractelement is slightly trivial, but it's still
+        // useful in that it drives us to conflict if our input is.
+        NewState =
+            meetBDVState(NewState, getStateForInput(EE->getVectorOperand()));
+      } else if (auto *IE = dyn_cast<InsertElementInst>(BDV)){
+        // Given there's a inherent type mismatch between the operands, will
+        // *always* produce Conflict.
+        NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(0)));
+        NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(1)));
+      } else {
+        // The only instance this does not return a Conflict is when both the
+        // vector operands are the same vector.
+        auto *SV = cast<ShuffleVectorInst>(BDV);
+        NewState = meetBDVState(NewState, getStateForInput(SV->getOperand(0)));
+        NewState = meetBDVState(NewState, getStateForInput(SV->getOperand(1)));
+      }
+
+      BDVState OldState = States[BDV];
+      if (OldState != NewState) {
+        Progress = true;
+        States[BDV] = NewState;
+      }
+    }
+
+    assert(OldSize == States.size() &&
+           "fixed point shouldn't be adding any new nodes to state");
+  }
+
+#ifndef NDEBUG
+  LLVM_DEBUG(dbgs() << "States after meet iteration:\n");
+  for (auto Pair : States) {
+    LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
+  }
+#endif
+
+  // Insert Phis for all conflicts
+  // TODO: adjust naming patterns to avoid this order of iteration dependency
+  for (auto Pair : States) {
+    Instruction *I = cast<Instruction>(Pair.first);
+    BDVState State = Pair.second;
+    assert(!isKnownBaseResult(I) && "why did it get added?");
+    assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
+
+    // extractelement instructions are a bit special in that we may need to
+    // insert an extract even when we know an exact base for the instruction.
+    // The problem is that we need to convert from a vector base to a scalar
+    // base for the particular indice we're interested in.
+    if (State.isBase() && isa<ExtractElementInst>(I) &&
+        isa<VectorType>(State.getBaseValue()->getType())) {
+      auto *EE = cast<ExtractElementInst>(I);
+      // TODO: In many cases, the new instruction is just EE itself.  We should
+      // exploit this, but can't do it here since it would break the invariant
+      // about the BDV not being known to be a base.
+      auto *BaseInst = ExtractElementInst::Create(
+          State.getBaseValue(), EE->getIndexOperand(), "base_ee", EE);
+      BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
+      States[I] = BDVState(BDVState::Base, BaseInst);
+    }
+
+    // Since we're joining a vector and scalar base, they can never be the
+    // same.  As a result, we should always see insert element having reached
+    // the conflict state.
+    assert(!isa<InsertElementInst>(I) || State.isConflict());
+
+    if (!State.isConflict())
+      continue;
+
+    /// Create and insert a new instruction which will represent the base of
+    /// the given instruction 'I'.
+    auto MakeBaseInstPlaceholder = [](Instruction *I) -> Instruction* {
+      if (isa<PHINode>(I)) {
+        BasicBlock *BB = I->getParent();
+        int NumPreds = pred_size(BB);
+        assert(NumPreds > 0 && "how did we reach here");
+        std::string Name = suffixed_name_or(I, ".base", "base_phi");
+        return PHINode::Create(I->getType(), NumPreds, Name, I);
+      } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
+        // The undef will be replaced later
+        UndefValue *Undef = UndefValue::get(SI->getType());
+        std::string Name = suffixed_name_or(I, ".base", "base_select");
+        return SelectInst::Create(SI->getCondition(), Undef, Undef, Name, SI);
+      } else if (auto *EE = dyn_cast<ExtractElementInst>(I)) {
+        UndefValue *Undef = UndefValue::get(EE->getVectorOperand()->getType());
+        std::string Name = suffixed_name_or(I, ".base", "base_ee");
+        return ExtractElementInst::Create(Undef, EE->getIndexOperand(), Name,
+                                          EE);
+      } else if (auto *IE = dyn_cast<InsertElementInst>(I)) {
+        UndefValue *VecUndef = UndefValue::get(IE->getOperand(0)->getType());
+        UndefValue *ScalarUndef = UndefValue::get(IE->getOperand(1)->getType());
+        std::string Name = suffixed_name_or(I, ".base", "base_ie");
+        return InsertElementInst::Create(VecUndef, ScalarUndef,
+                                         IE->getOperand(2), Name, IE);
+      } else {
+        auto *SV = cast<ShuffleVectorInst>(I);
+        UndefValue *VecUndef = UndefValue::get(SV->getOperand(0)->getType());
+        std::string Name = suffixed_name_or(I, ".base", "base_sv");
+        return new ShuffleVectorInst(VecUndef, VecUndef, SV->getOperand(2),
+                                     Name, SV);
+      }
+    };
+    Instruction *BaseInst = MakeBaseInstPlaceholder(I);
+    // Add metadata marking this as a base value
+    BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
+    States[I] = BDVState(BDVState::Conflict, BaseInst);
+  }
+
+  // Returns a instruction which produces the base pointer for a given
+  // instruction.  The instruction is assumed to be an input to one of the BDVs
+  // seen in the inference algorithm above.  As such, we must either already
+  // know it's base defining value is a base, or have inserted a new
+  // instruction to propagate the base of it's BDV and have entered that newly
+  // introduced instruction into the state table.  In either case, we are
+  // assured to be able to determine an instruction which produces it's base
+  // pointer.
+  auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) {
+    Value *BDV = findBaseOrBDV(Input, Cache);
+    Value *Base = nullptr;
+    if (isKnownBaseResult(BDV)) {
+      Base = BDV;
+    } else {
+      // Either conflict or base.
+      assert(States.count(BDV));
+      Base = States[BDV].getBaseValue();
+    }
+    assert(Base && "Can't be null");
+    // The cast is needed since base traversal may strip away bitcasts
+    if (Base->getType() != Input->getType() && InsertPt)
+      Base = CastInst::CreatePointerBitCastOrAddrSpaceCast(Base, Input->getType(), "cast", InsertPt);
+    return Base;
+  };
+
+  // Fixup all the inputs of the new PHIs.  Visit order needs to be
+  // deterministic and predictable because we're naming newly created
+  // instructions.
+  for (auto Pair : States) {
+    Instruction *BDV = cast<Instruction>(Pair.first);
+    BDVState State = Pair.second;
+
+    assert(!isKnownBaseResult(BDV) && "why did it get added?");
+    assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
+    if (!State.isConflict())
+      continue;
+
+    if (PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {
+      PHINode *PN = cast<PHINode>(BDV);
+      unsigned NumPHIValues = PN->getNumIncomingValues();
+      for (unsigned i = 0; i < NumPHIValues; i++) {
+        Value *InVal = PN->getIncomingValue(i);
+        BasicBlock *InBB = PN->getIncomingBlock(i);
+
+        // If we've already seen InBB, add the same incoming value
+        // we added for it earlier.  The IR verifier requires phi
+        // nodes with multiple entries from the same basic block
+        // to have the same incoming value for each of those
+        // entries.  If we don't do this check here and basephi
+        // has a different type than base, we'll end up adding two
+        // bitcasts (and hence two distinct values) as incoming
+        // values for the same basic block.
+
+        int BlockIndex = BasePHI->getBasicBlockIndex(InBB);
+        if (BlockIndex != -1) {
+          Value *OldBase = BasePHI->getIncomingValue(BlockIndex);
+          BasePHI->addIncoming(OldBase, InBB);
+
+#ifndef NDEBUG
+          Value *Base = getBaseForInput(InVal, nullptr);
+          // In essence this assert states: the only way two values
+          // incoming from the same basic block may be different is by
+          // being different bitcasts of the same value.  A cleanup
+          // that remains TODO is changing findBaseOrBDV to return an
+          // llvm::Value of the correct type (and still remain pure).
+          // This will remove the need to add bitcasts.
+          assert(Base->stripPointerCasts() == OldBase->stripPointerCasts() &&
+                 "Sanity -- findBaseOrBDV should be pure!");
+#endif
+          continue;
+        }
+
+        // Find the instruction which produces the base for each input.  We may
+        // need to insert a bitcast in the incoming block.
+        // TODO: Need to split critical edges if insertion is needed
+        Value *Base = getBaseForInput(InVal, InBB->getTerminator());
+        BasePHI->addIncoming(Base, InBB);
+      }
+      assert(BasePHI->getNumIncomingValues() == NumPHIValues);
+    } else if (SelectInst *BaseSI =
+                   dyn_cast<SelectInst>(State.getBaseValue())) {
+      SelectInst *SI = cast<SelectInst>(BDV);
+
+      // Find the instruction which produces the base for each input.
+      // We may need to insert a bitcast.
+      BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI));
+      BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI));
+    } else if (auto *BaseEE =
+                   dyn_cast<ExtractElementInst>(State.getBaseValue())) {
+      Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();
+      // Find the instruction which produces the base for each input.  We may
+      // need to insert a bitcast.
+      BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));
+    } else if (auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){
+      auto *BdvIE = cast<InsertElementInst>(BDV);
+      auto UpdateOperand = [&](int OperandIdx) {
+        Value *InVal = BdvIE->getOperand(OperandIdx);
+        Value *Base = getBaseForInput(InVal, BaseIE);
+        BaseIE->setOperand(OperandIdx, Base);
+      };
+      UpdateOperand(0); // vector operand
+      UpdateOperand(1); // scalar operand
+    } else {
+      auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue());
+      auto *BdvSV = cast<ShuffleVectorInst>(BDV);
+      auto UpdateOperand = [&](int OperandIdx) {
+        Value *InVal = BdvSV->getOperand(OperandIdx);
+        Value *Base = getBaseForInput(InVal, BaseSV);
+        BaseSV->setOperand(OperandIdx, Base);
+      };
+      UpdateOperand(0); // vector operand
+      UpdateOperand(1); // vector operand
+    }
+  }
+
+  // Cache all of our results so we can cheaply reuse them
+  // NOTE: This is actually two caches: one of the base defining value
+  // relation and one of the base pointer relation!  FIXME
+  for (auto Pair : States) {
+    auto *BDV = Pair.first;
+    Value *Base = Pair.second.getBaseValue();
+    assert(BDV && Base);
+    assert(!isKnownBaseResult(BDV) && "why did it get added?");
+
+    LLVM_DEBUG(
+        dbgs() << "Updating base value cache"
+               << " for: " << BDV->getName() << " from: "
+               << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none")
+               << " to: " << Base->getName() << "\n");
+
+    if (Cache.count(BDV)) {
+      assert(isKnownBaseResult(Base) &&
+             "must be something we 'know' is a base pointer");
+      // Once we transition from the BDV relation being store in the Cache to
+      // the base relation being stored, it must be stable
+      assert((!isKnownBaseResult(Cache[BDV]) || Cache[BDV] == Base) &&
+             "base relation should be stable");
+    }
+    Cache[BDV] = Base;
+  }
+  assert(Cache.count(Def));
+  return Cache[Def];
+}
+
+// For a set of live pointers (base and/or derived), identify the base
+// pointer of the object which they are derived from.  This routine will
+// mutate the IR graph as needed to make the 'base' pointer live at the
+// definition site of 'derived'.  This ensures that any use of 'derived' can
+// also use 'base'.  This may involve the insertion of a number of
+// additional PHI nodes.
+//
+// preconditions: live is a set of pointer type Values
+//
+// side effects: may insert PHI nodes into the existing CFG, will preserve
+// CFG, will not remove or mutate any existing nodes
+//
+// post condition: PointerToBase contains one (derived, base) pair for every
+// pointer in live.  Note that derived can be equal to base if the original
+// pointer was a base pointer.
+static void
+findBasePointers(const StatepointLiveSetTy &live,
+                 MapVector<Value *, Value *> &PointerToBase,
+                 DominatorTree *DT, DefiningValueMapTy &DVCache) {
+  for (Value *ptr : live) {
+    Value *base = findBasePointer(ptr, DVCache);
+    assert(base && "failed to find base pointer");
+    PointerToBase[ptr] = base;
+    assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||
+            DT->dominates(cast<Instruction>(base)->getParent(),
+                          cast<Instruction>(ptr)->getParent())) &&
+           "The base we found better dominate the derived pointer");
+  }
+}
+
+/// Find the required based pointers (and adjust the live set) for the given
+/// parse point.
+static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache,
+                             CallSite CS,
+                             PartiallyConstructedSafepointRecord &result) {
+  MapVector<Value *, Value *> PointerToBase;
+  findBasePointers(result.LiveSet, PointerToBase, &DT, DVCache);
+
+  result.PointerToBase = PointerToBase;
+}
+
+// When inserting gc.relocate and gc.result calls, we need to ensure there are
+// no uses of the original value / return value between the gc.statepoint and
+// the gc.relocate / gc.result call.  One case which can arise is a phi node
+// starting one of the successor blocks.  We also need to be able to insert the
+// gc.relocates only on the path which goes through the statepoint.  We might
+// need to split an edge to make this possible.
+static BasicBlock *
+normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent,
+                            DominatorTree &DT) {
+  BasicBlock *Ret = BB;
+  if (!BB->getUniquePredecessor())
+    Ret = SplitBlockPredecessors(BB, InvokeParent, "", &DT);
+
+  // Now that 'Ret' has unique predecessor we can safely remove all phi nodes
+  // from it
+  FoldSingleEntryPHINodes(Ret);
+  assert(!isa<PHINode>(Ret->begin()) &&
+         "All PHI nodes should have been removed!");
+
+  // At this point, we can safely insert a gc.relocate or gc.result as the first
+  // instruction in Ret if needed.
+  return Ret;
+}
+
+// Create new attribute set containing only attributes which can be transferred
+// from original call to the safepoint.
+static AttributeList legalizeCallAttributes(AttributeList AL) {
+  if (AL.isEmpty())
+    return AL;
+
+  // Remove the readonly, readnone, and statepoint function attributes.
+  AttrBuilder FnAttrs = AL.getFnAttributes();
+  FnAttrs.removeAttribute(Attribute::ReadNone);
+  FnAttrs.removeAttribute(Attribute::ReadOnly);
+  for (Attribute A : AL.getFnAttributes()) {
+    if (isStatepointDirectiveAttr(A))
+      FnAttrs.remove(A);
+  }
+
+  LLVMContext &Ctx = AL.getContext();
+  AttributeList Ret = AttributeList::get(Ctx, AttributeList::FunctionIndex,
+                                         AttributeSet::get(Ctx, FnAttrs));
+
+  // Add parameter attrs.
+  // TODO: use AttrBuilder?
+  for (unsigned i = AttributeList::FirstArgIndex, e = AL.getNumAttrSets(); i < e; ++i)
+    Ret = Ret.addAttributes(Ctx, i+5,  AL.getAttributes(i));
+
+  // Skip return attributes
+  return Ret;
+}
+
+namespace {
+
+/// This struct is used to defer RAUWs and `eraseFromParent` s.  Using this
+/// avoids having to worry about keeping around dangling pointers to Values.
+class DeferredReplacement {
+  AssertingVH<Instruction> Old;
+  AssertingVH<Instruction> New;
+  bool IsDeoptimize = false;
+
+  DeferredReplacement() = default;
+
+public:
+  static DeferredReplacement createRAUW(Instruction *Old, Instruction *New) {
+    assert(Old != New && Old && New &&
+           "Cannot RAUW equal values or to / from null!");
+
+    DeferredReplacement D;
+    D.Old = Old;
+    D.New = New;
+    return D;
+  }
+
+  static DeferredReplacement createDelete(Instruction *ToErase) {
+    DeferredReplacement D;
+    D.Old = ToErase;
+    return D;
+  }
+
+  static DeferredReplacement createDeoptimizeReplacement(Instruction *Old) {
+#ifndef NDEBUG
+    auto *F = cast<CallInst>(Old)->getCalledFunction();
+    assert(F && F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&
+           "Only way to construct a deoptimize deferred replacement");
+#endif
+    DeferredReplacement D;
+    D.Old = Old;
+    D.IsDeoptimize = true;
+    return D;
+  }
+
+  /// Does the task represented by this instance.
+  void doReplacement() {
+    Instruction *OldI = Old;
+    Instruction *NewI = New;
+
+    assert(OldI != NewI && "Disallowed at construction?!");
+    assert((!IsDeoptimize || !New) &&
+           "Deoptimize intrinsics are not replaced!");
+
+    Old = nullptr;
+    New = nullptr;
+
+    if (NewI)
+      OldI->replaceAllUsesWith(NewI);
+
+    if (IsDeoptimize) {
+      // Note: we've inserted instructions, so the call to llvm.deoptimize may
+      // not necessarily be followed by the matching return.
+      auto *RI = cast<ReturnInst>(OldI->getParent()->getTerminator());
+      new UnreachableInst(RI->getContext(), RI);
+      RI->eraseFromParent();
+    }
+
+    OldI->eraseFromParent();
+  }
+};
+
+} // end anonymous namespace
+
+/// A unique function which doesn't require we sort the input vector.
+template <typename T> static void unique_unsorted(SmallVectorImpl<T> &Vec) {
+  SmallSet<T, 8> Seen;
+  Vec.erase(remove_if(Vec, [&](const T &V) { return !Seen.insert(V).second; }),
+            Vec.end());
+}
+
+// Attach the stack map to the statepoint. The statepoint is an invoke
+// with the given landing pad. The stack map (pointer) is attached as
+// the type info of the landing pad.
+static void
+attachStackMap(uint64_t StatepointID, Instruction *LandingPad) {
+  if (cast<LandingPadInst>(LandingPad)->isCleanup())
+    return;
+  Module *M = LandingPad->getModule();
+  std::string Name = (Twine(GO_STACKMAP_SYM_PREFIX) + Twine(StatepointID)).str();
+  Constant *C = M->getOrInsertGlobal(Name, Type::getInt64Ty(M->getContext()));
+  LandingPad->setOperand(0, C);
+}
+
+static void
+makeStatepointExplicitImpl(const CallSite CS, /* to replace */
+                           SmallVectorImpl<Value *> &BasePtrs,
+                           SmallVectorImpl<Value *> &LiveVariables,
+                           PartiallyConstructedSafepointRecord &Result,
+                           std::vector<DeferredReplacement> &Replacements) {
+  assert(BasePtrs.size() == LiveVariables.size());
+
+  // Then go ahead and use the builder do actually do the inserts.  We insert
+  // immediately before the previous instruction under the assumption that all
+  // arguments will be available here.  We can't insert afterwards since we may
+  // be replacing a terminator.
+  Instruction *InsertBefore = CS.getInstruction();
+  const DataLayout &DL = InsertBefore->getModule()->getDataLayout();
+  IRBuilder<> Builder(InsertBefore);
+
+  unique_unsorted(BasePtrs);
+
+  // For aggregate typed stack slots, attach a bitmap identifying its
+  // pointer fields.
+  SmallVector<Value *, 64> PtrFields;
+  for (Value *V : BasePtrs) {
+    if (isa<AllocaInst>(V) ||
+        (isa<Argument>(V) && cast<Argument>(V)->hasByValAttr())) {
+      // Byval argument is at a fixed frame offset. Treat it the same as alloca.
+      Type *T = cast<PointerType>(V->getType())->getElementType();
+      if (hasPointer(T)) {
+        PtrFields.push_back(V);
+        getPtrBitmapForType(T, DL, PtrFields);
+      }
+    } else
+      PtrFields.push_back(V);
+  }
+
+  ArrayRef<Value *> GCArgs(PtrFields);
+  uint64_t StatepointID = ID;
+  ID++;
+  uint32_t NumPatchBytes = 0;
+  uint32_t Flags = uint32_t(StatepointFlags::None);
+
+  ArrayRef<Use> CallArgs(CS.arg_begin(), CS.arg_end());
+  ArrayRef<Use> TransitionArgs;
+  if (auto TransitionBundle =
+      CS.getOperandBundle(LLVMContext::OB_gc_transition)) {
+    Flags |= uint32_t(StatepointFlags::GCTransition);
+    TransitionArgs = TransitionBundle->Inputs;
+  }
+
+  // Instead of lowering calls to @llvm.experimental.deoptimize as normal calls
+  // with a return value, we lower then as never returning calls to
+  // __llvm_deoptimize that are followed by unreachable to get better codegen.
+  bool IsDeoptimize = false;
+
+  StatepointDirectives SD =
+      parseStatepointDirectivesFromAttrs(CS.getAttributes());
+  if (SD.NumPatchBytes)
+    NumPatchBytes = *SD.NumPatchBytes;
+  if (SD.StatepointID)
+    StatepointID = *SD.StatepointID;
+
+  Value *CallTarget = CS.getCalledValue();
+  if (Function *F = dyn_cast<Function>(CallTarget)) {
+    if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize) {
+      // Calls to llvm.experimental.deoptimize are lowered to calls to the
+      // __llvm_deoptimize symbol.  We want to resolve this now, since the
+      // verifier does not allow taking the address of an intrinsic function.
+
+      SmallVector<Type *, 8> DomainTy;
+      for (Value *Arg : CallArgs)
+        DomainTy.push_back(Arg->getType());
+      auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,
+                                    /* isVarArg = */ false);
+
+      // Note: CallTarget can be a bitcast instruction of a symbol if there are
+      // calls to @llvm.experimental.deoptimize with different argument types in
+      // the same module.  This is fine -- we assume the frontend knew what it
+      // was doing when generating this kind of IR.
+      CallTarget =
+          F->getParent()->getOrInsertFunction("__llvm_deoptimize", FTy);
+
+      IsDeoptimize = true;
+    }
+  }
+
+  // Create the statepoint given all the arguments
+  Instruction *Token = nullptr;
+  if (CS.isCall()) {
+    // We should have converted all statepoints to invoke.
+    assert(false && "statepoint is not an invoke");
+  } else {
+    InvokeInst *ToReplace = cast<InvokeInst>(CS.getInstruction());
+
+    // Insert the new invoke into the old block.  We'll remove the old one in a
+    // moment at which point this will become the new terminator for the
+    // original block.
+
+    // Note (Go specific):
+    // Here we attach GCArgs actually to the "deopt arg" slots, instead of
+    // the "gc arg" slots, of the statepoint. Both are recorded in the stack
+    // map the same way. The difference is that "deopt arg" doesn't need
+    // relocation. We're implementing non-moving GC (for now).
+    InvokeInst *Invoke = Builder.CreateGCStatepointInvoke(
+        StatepointID, NumPatchBytes, CallTarget, ToReplace->getNormalDest(),
+        ToReplace->getUnwindDest(), CallArgs, GCArgs, ArrayRef<Value*>(),
+        "statepoint_token");
+
+    Invoke->setCallingConv(ToReplace->getCallingConv());
+
+    // Currently we will fail on parameter attributes and on certain
+    // function attributes.  In case if we can handle this set of attributes -
+    // set up function attrs directly on statepoint and return attrs later for
+    // gc_result intrinsic.
+    Invoke->setAttributes(legalizeCallAttributes(ToReplace->getAttributes()));
+
+    Token = Invoke;
+
+    // Generate gc relocates in exceptional path
+    BasicBlock *UnwindBlock = ToReplace->getUnwindDest();
+    assert(!isa<PHINode>(UnwindBlock->begin()) &&
+           UnwindBlock->getUniquePredecessor() &&
+           "can't safely insert in this block!");
+
+    Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt());
+    Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
+
+    // Attach exceptional gc relocates to the landingpad.
+    Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();
+    Result.UnwindToken = ExceptionalToken;
+
+    attachStackMap(StatepointID, ExceptionalToken);
+
+    BasicBlock *NormalDest = ToReplace->getNormalDest();
+    assert(!isa<PHINode>(NormalDest->begin()) &&
+           NormalDest->getUniquePredecessor() &&
+           "can't safely insert in this block!");
+
+    Builder.SetInsertPoint(&*NormalDest->getFirstInsertionPt());
+  }
+  assert(Token && "Should be set in one of the above branches!");
+
+  if (IsDeoptimize) {
+    // If we're wrapping an @llvm.experimental.deoptimize in a statepoint, we
+    // transform the tail-call like structure to a call to a void function
+    // followed by unreachable to get better codegen.
+    Replacements.push_back(
+        DeferredReplacement::createDeoptimizeReplacement(CS.getInstruction()));
+  } else {
+    Token->setName("statepoint_token");
+    if (!CS.getType()->isVoidTy() && !CS.getInstruction()->use_empty()) {
+      StringRef Name =
+          CS.getInstruction()->hasName() ? CS.getInstruction()->getName() : "";
+      CallInst *GCResult = Builder.CreateGCResult(Token, CS.getType(), Name);
+      GCResult->setAttributes(
+          AttributeList::get(GCResult->getContext(), AttributeList::ReturnIndex,
+                             CS.getAttributes().getRetAttributes()));
+
+      // We cannot RAUW or delete CS.getInstruction() because it could be in the
+      // live set of some other safepoint, in which case that safepoint's
+      // PartiallyConstructedSafepointRecord will hold a raw pointer to this
+      // llvm::Instruction.  Instead, we defer the replacement and deletion to
+      // after the live sets have been made explicit in the IR, and we no longer
+      // have raw pointers to worry about.
+      Replacements.emplace_back(
+          DeferredReplacement::createRAUW(CS.getInstruction(), GCResult));
+    } else {
+      Replacements.emplace_back(
+          DeferredReplacement::createDelete(CS.getInstruction()));
+    }
+  }
+
+  Result.StatepointToken = Token;
+}
+
+// Replace an existing gc.statepoint with a new one and a set of gc.relocates
+// which make the relocations happening at this safepoint explicit.
+//
+// WARNING: Does not do any fixup to adjust users of the original live
+// values.  That's the callers responsibility.
+static void
+makeStatepointExplicit(DominatorTree &DT, CallSite CS,
+                       PartiallyConstructedSafepointRecord &Result,
+                       std::vector<DeferredReplacement> &Replacements) {
+  const auto &LiveSet = Result.LiveSet;
+  const auto &PointerToBase = Result.PointerToBase;
+
+  // Convert to vector for efficient cross referencing.
+  SmallVector<Value *, 64> BaseVec, LiveVec;
+  LiveVec.reserve(LiveSet.size());
+  BaseVec.reserve(LiveSet.size());
+  for (Value *L : LiveSet) {
+    LiveVec.push_back(L);
+    assert(PointerToBase.count(L));
+    Value *Base = PointerToBase.find(L)->second;
+    BaseVec.push_back(Base);
+  }
+  assert(LiveVec.size() == BaseVec.size());
+
+  // Do the actual rewriting and delete the old statepoint
+  makeStatepointExplicitImpl(CS, BaseVec, LiveVec, Result, Replacements);
+}
+
+static void findLiveReferences(
+    Function &F, DominatorTree &DT, ArrayRef<CallSite> toUpdate,
+    MutableArrayRef<struct PartiallyConstructedSafepointRecord> records,
+    SetVector<Value *> &AddrTakenAllocas, SetVector <Value *> &ToZero,
+    DefiningValueMapTy &DVCache) {
+  GCPtrLivenessData OriginalLivenessData;
+  computeLiveInValues(DT, F, OriginalLivenessData, AddrTakenAllocas, ToZero, DVCache);
+  for (size_t i = 0; i < records.size(); i++) {
+    struct PartiallyConstructedSafepointRecord &info = records[i];
+    analyzeParsePointLiveness(DT, OriginalLivenessData, AddrTakenAllocas, toUpdate[i], info, DVCache);
+  }
+}
+
+// Helper function for the "rematerializeLiveValues". It walks use chain
+// starting from the "CurrentValue" until it reaches the root of the chain, i.e.
+// the base or a value it cannot process. Only "simple" values are processed
+// (currently it is GEP's and casts). The returned root is  examined by the
+// callers of findRematerializableChainToBasePointer.  Fills "ChainToBase" array
+// with all visited values.
+static Value* findRematerializableChainToBasePointer(
+  SmallVectorImpl<Instruction*> &ChainToBase,
+  Value *CurrentValue) {
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {
+    ChainToBase.push_back(GEP);
+    return findRematerializableChainToBasePointer(ChainToBase,
+                                                  GEP->getPointerOperand());
+  }
+
+  if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
+    if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
+      return CI;
+
+    ChainToBase.push_back(CI);
+    return findRematerializableChainToBasePointer(ChainToBase,
+                                                  CI->getOperand(0));
+  }
+
+  // We have reached the root of the chain, which is either equal to the base or
+  // is the first unsupported value along the use chain.
+  return CurrentValue;
+}
+
+static void
+zeroAmbiguouslyLiveSlots(Function &F, SetVector<Value *> &ToZero,
+                         SetVector<Value *> &AddrTakenAllocas) {
+  SmallVector<Instruction *, 16> InstToDelete;
+  SetVector<Value *> Done;
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  IntegerType *Int64Ty = Type::getInt64Ty(F.getParent()->getContext());
+
+  // If a slot has lifetime.start, place the zeroing right after it.
+  for (Instruction &I : instructions(F)) {
+    if (CallInst *CI = dyn_cast<CallInst>(&I))
+      if (Function *Fn = CI->getCalledFunction()) {
+        if (Fn->getIntrinsicID() == Intrinsic::lifetime_start) {
+          Value *V = I.getOperand(1)->stripPointerCasts();
+          if (ToZero.count(V) != 0) {
+            if (AddrTakenAllocas.count(V) != 0) {
+              // For addrtaken alloca, the lifetime start may not dominate all
+              // safepoints where the slot can be live.
+              // For now, zero it in the entry block and remove the lifetime
+              // marker.
+              InstToDelete.push_back(&I);
+            } else {
+              IRBuilder<> Builder(I.getNextNode());
+              Value *Zero = Constant::getNullValue(V->getType()->getPointerElementType());
+              Builder.CreateStore(Zero, V);
+              // Don't remove V from ToZero for now, as there may be multiple
+              // lifetime start markers, where we need to insert zeroing.
+              Done.insert(V);
+            }
+          }
+        } else if (Fn->getIntrinsicID() == Intrinsic::lifetime_end) {
+          Value *V = I.getOperand(1)->stripPointerCasts();
+          if (ToZero.count(V) != 0 && AddrTakenAllocas.count(V) != 0)
+            InstToDelete.push_back(&I);
+        }
+      }
+  }
+
+  for (Instruction *I : InstToDelete)
+    I->eraseFromParent();
+  ToZero.set_subtract(Done);
+  if (ToZero.empty())
+    return;
+
+  // Otherwise, place the zeroing in the entry block after the alloca.
+  for (Instruction &I : F.getEntryBlock())
+    if (ToZero.count(&I) != 0) {
+      IRBuilder<> Builder(I.getNextNode());
+      Type *ElemTyp = I.getType()->getPointerElementType();
+      if (AddrTakenAllocas.count(&I) != 0) {
+        // For addrtaken alloca, we removed the lifetime marker above.
+        // Insert a new one at the entry block.
+        unsigned Size = DL.getTypeStoreSize(ElemTyp);
+        Builder.CreateLifetimeStart(&I, ConstantInt::get(Int64Ty, Size));
+      }
+      Value *Zero = Constant::getNullValue(ElemTyp);
+      Builder.CreateStore(Zero, &I);
+      ToZero.remove(&I);
+    }
+
+  assert(ToZero.empty());
+}
+
+static bool insertParsePoints(Function &F, DominatorTree &DT,
+                              TargetTransformInfo &TTI,
+                              SmallVectorImpl<CallSite> &ToUpdate) {
+#ifndef NDEBUG
+  // sanity check the input
+  std::set<CallSite> Uniqued;
+  Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
+  assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
+
+  for (CallSite CS : ToUpdate)
+    assert(CS.getInstruction()->getFunction() == &F);
+#endif
+
+  // When inserting gc.relocates for invokes, we need to be able to insert at
+  // the top of the successor blocks.  See the comment on
+  // normalForInvokeSafepoint on exactly what is needed.  Note that this step
+  // may restructure the CFG.
+  for (CallSite CS : ToUpdate) {
+    if (!CS.isInvoke())
+      continue;
+    auto *II = cast<InvokeInst>(CS.getInstruction());
+    normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT);
+    normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT);
+  }
+
+  SmallVector<PartiallyConstructedSafepointRecord, 64> Records(ToUpdate.size());
+
+  SetVector<Value *> AddrTakenAllocas, ToZero;
+
+  // 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;
+
+  // A) Identify all gc pointers which are statically live at the given call
+  // site.
+  findLiveReferences(F, DT, ToUpdate, Records, AddrTakenAllocas, ToZero, DVCache);
+
+  // B) Find the base pointers for each live pointer
+  for (size_t i = 0; i < Records.size(); i++) {
+    PartiallyConstructedSafepointRecord &info = Records[i];
+    findBasePointers(DT, DVCache, ToUpdate[i], info);
+  }
+
+  // It is possible that non-constant live variables have a constant base.  For
+  // example, a GEP with a variable offset from a global.  In this case we can
+  // remove it from the liveset.  We already don't add constants to the liveset
+  // because we assume they won't move at runtime and the GC doesn't need to be
+  // informed about them.  The same reasoning applies if the base is constant.
+  // Note that the relocation placement code relies on this filtering for
+  // correctness as it expects the base to be in the liveset, which isn't true
+  // if the base is constant.
+  for (auto &Info : Records)
+    for (auto &BasePair : Info.PointerToBase)
+      if (isa<Constant>(BasePair.second))
+        Info.LiveSet.remove(BasePair.first);
+
+  // We need this to safely RAUW and delete call or invoke return values that
+  // may themselves be live over a statepoint.  For details, please see usage in
+  // makeStatepointExplicitImpl.
+  std::vector<DeferredReplacement> Replacements;
+
+  // Now run through and replace the existing statepoints with new ones with
+  // the live variables listed.  We do not yet update uses of the values being
+  // relocated. We have references to live variables that need to
+  // survive to the last iteration of this loop.  (By construction, the
+  // previous statepoint can not be a live variable, thus we can and remove
+  // the old statepoint calls as we go.)
+  for (size_t i = 0; i < Records.size(); i++)
+    makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements);
+
+  ToUpdate.clear(); // prevent accident use of invalid CallSites
+
+  for (auto &PR : Replacements)
+    PR.doReplacement();
+
+  Replacements.clear();
+
+  for (auto &Info : Records) {
+    // These live sets may contain state Value pointers, since we replaced calls
+    // with operand bundles with calls wrapped in gc.statepoint, and some of
+    // those calls may have been def'ing live gc pointers.  Clear these out to
+    // avoid accidentally using them.
+    //
+    // TODO: We should create a separate data structure that does not contain
+    // these live sets, and migrate to using that data structure from this point
+    // onward.
+    Info.LiveSet.clear();
+    Info.PointerToBase.clear();
+  }
+
+  // Do all the fixups of the original live variables to their relocated selves
+  SmallVector<Value *, 128> Live;
+  for (size_t i = 0; i < Records.size(); i++) {
+    PartiallyConstructedSafepointRecord &Info = Records[i];
+
+    // We can't simply save the live set from the original insertion.  One of
+    // the live values might be the result of a call which needs a safepoint.
+    // That Value* no longer exists and we need to use the new gc_result.
+    // Thankfully, the live set is embedded in the statepoint (and updated), so
+    // we just grab that.
+    Statepoint Statepoint(Info.StatepointToken);
+    Live.insert(Live.end(), Statepoint.gc_args_begin(),
+                Statepoint.gc_args_end());
+#ifndef NDEBUG
+    // Do some basic sanity checks on our liveness results before performing
+    // relocation.  Relocation can and will turn mistakes in liveness results
+    // into non-sensical code which is must harder to debug.
+    // TODO: It would be nice to test consistency as well
+    assert(DT.isReachableFromEntry(Info.StatepointToken->getParent()) &&
+           "statepoint must be reachable or liveness is meaningless");
+    for (Value *V : Statepoint.gc_args()) {
+      if (!isa<Instruction>(V))
+        // Non-instruction values trivial dominate all possible uses
+        continue;
+      auto *LiveInst = cast<Instruction>(V);
+      assert(DT.isReachableFromEntry(LiveInst->getParent()) &&
+             "unreachable values should never be live");
+      assert(DT.dominates(LiveInst, Info.StatepointToken) &&
+             "basic SSA liveness expectation violated by liveness analysis");
+    }
+#endif
+  }
+  unique_unsorted(Live);
+
+#ifndef NDEBUG
+  // sanity check
+  for (auto *Ptr : Live)
+    assert(isHandledGCPointerType(Ptr->getType()) &&
+           "must be a gc pointer type");
+#endif
+
+  zeroAmbiguouslyLiveSlots(F, ToZero, AddrTakenAllocas);
+
+  return !Records.empty();
+}
+
+// Handles both return values and arguments for Functions and CallSites.
+template <typename AttrHolder>
+static void RemoveNonValidAttrAtIndex(LLVMContext &Ctx, AttrHolder &AH,
+                                      unsigned Index) {
+  AttrBuilder R;
+  if (AH.getDereferenceableBytes(Index))
+    R.addAttribute(Attribute::get(Ctx, Attribute::Dereferenceable,
+                                  AH.getDereferenceableBytes(Index)));
+  if (AH.getDereferenceableOrNullBytes(Index))
+    R.addAttribute(Attribute::get(Ctx, Attribute::DereferenceableOrNull,
+                                  AH.getDereferenceableOrNullBytes(Index)));
+  if (AH.getAttributes().hasAttribute(Index, Attribute::NoAlias))
+    R.addAttribute(Attribute::NoAlias);
+
+  if (!R.empty())
+    AH.setAttributes(AH.getAttributes().removeAttributes(Ctx, Index, R));
+}
+
+static void stripNonValidAttributesFromPrototype(Function &F) {
+  LLVMContext &Ctx = F.getContext();
+
+  for (Argument &A : F.args())
+    if (isa<PointerType>(A.getType()))
+      RemoveNonValidAttrAtIndex(Ctx, F,
+                                A.getArgNo() + AttributeList::FirstArgIndex);
+
+  if (isa<PointerType>(F.getReturnType()))
+    RemoveNonValidAttrAtIndex(Ctx, F, AttributeList::ReturnIndex);
+}
+
+/// Certain metadata on instructions are invalid after running this pass.
+/// Optimizations that run after this can incorrectly use this metadata to
+/// optimize functions. We drop such metadata on the instruction.
+static void stripInvalidMetadataFromInstruction(Instruction &I) {
+  if (!isa<LoadInst>(I) && !isa<StoreInst>(I))
+    return;
+  // These are the attributes that are still valid on loads and stores after
+  // this pass.
+  // The metadata implying dereferenceability and noalias are (conservatively)
+  // dropped.  This is because semantically, after this pass runs,
+  // all calls to gc.statepoint "free" the entire heap. Also, gc.statepoint can
+  // touch the entire heap including noalias objects. Note: The reasoning is
+  // same as stripping the dereferenceability and noalias attributes that are
+  // analogous to the metadata counterparts.
+  // We also drop the invariant.load metadata on the load because that metadata
+  // implies the address operand to the load points to memory that is never
+  // changed once it became dereferenceable. This is no longer true after this
+  // pass. Similar reasoning applies to invariant.group metadata, which applies
+  // to loads within a group.
+  unsigned ValidMetadata[] = {LLVMContext::MD_tbaa,
+                              LLVMContext::MD_range,
+                              LLVMContext::MD_alias_scope,
+                              LLVMContext::MD_nontemporal,
+                              LLVMContext::MD_nonnull,
+                              LLVMContext::MD_align,
+                              LLVMContext::MD_type};
+
+  // Drops all metadata on the instruction other than ValidMetadata.
+  I.dropUnknownNonDebugMetadata(ValidMetadata);
+}
+
+static void stripNonValidDataFromBody(Function &F) {
+  if (F.empty())
+    return;
+
+  LLVMContext &Ctx = F.getContext();
+  MDBuilder Builder(Ctx);
+
+  // Set of invariantstart instructions that we need to remove.
+  // Use this to avoid invalidating the instruction iterator.
+  SmallVector<IntrinsicInst*, 12> InvariantStartInstructions;
+
+  for (Instruction &I : instructions(F)) {
+    // invariant.start on memory location implies that the referenced memory
+    // location is constant and unchanging. This is no longer true after
+    // this pass runs because there can be calls to gc.statepoint
+    // which frees the entire heap and the presence of invariant.start allows
+    // the optimizer to sink the load of a memory location past a statepoint,
+    // which is incorrect.
+    if (auto *II = dyn_cast<IntrinsicInst>(&I))
+      if (II->getIntrinsicID() == Intrinsic::invariant_start) {
+        InvariantStartInstructions.push_back(II);
+        continue;
+      }
+
+    if (MDNode *Tag = I.getMetadata(LLVMContext::MD_tbaa)) {
+      MDNode *MutableTBAA = Builder.createMutableTBAAAccessTag(Tag);
+      I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);
+    }
+
+    stripInvalidMetadataFromInstruction(I);
+
+    if (CallSite CS = CallSite(&I)) {
+      for (int i = 0, e = CS.arg_size(); i != e; i++)
+        if (isa<PointerType>(CS.getArgument(i)->getType()))
+          RemoveNonValidAttrAtIndex(Ctx, CS, i + AttributeList::FirstArgIndex);
+      if (isa<PointerType>(CS.getType()))
+        RemoveNonValidAttrAtIndex(Ctx, CS, AttributeList::ReturnIndex);
+    }
+  }
+
+  // Delete the invariant.start instructions and RAUW undef.
+  for (auto *II : InvariantStartInstructions) {
+    II->replaceAllUsesWith(UndefValue::get(II->getType()));
+    II->eraseFromParent();
+  }
+}
+
+/// Returns true if this function should be rewritten by this pass.
+static bool shouldRewriteStatepointsIn(Function &F) {
+  return F.hasGC();
+}
+
+static void stripNonValidData(Module &M) {
+#ifndef NDEBUG
+  assert(llvm::any_of(M, shouldRewriteStatepointsIn) && "precondition!");
+#endif
+
+  for (Function &F : M)
+    stripNonValidAttributesFromPrototype(F);
+
+  for (Function &F : M)
+    stripNonValidDataFromBody(F);
+}
+
+bool GoStatepoints::runOnFunction(Function &F, DominatorTree &DT,
+                                            TargetTransformInfo &TTI,
+                                            const TargetLibraryInfo &TLI) {
+  assert(!F.isDeclaration() && !F.empty() &&
+         "need function body to rewrite statepoints in");
+  assert(shouldRewriteStatepointsIn(F) && "mismatch in rewrite decision");
+
+  if (!PrintFunc.empty())
+    PrintLiveSet = F.getName() == PrintFunc;
+  if (PrintLiveSet)
+    dbgs() << "\n********** Liveness of function " << F.getName() << " **********\n";
+
+  auto NeedsRewrite = [&TLI](Instruction &I) {
+    if (ImmutableCallSite CS = ImmutableCallSite(&I))
+      return !callsGCLeafFunction(CS, TLI) && !isStatepoint(CS);
+    return false;
+  };
+
+  // Delete any unreachable statepoints so that we don't have unrewritten
+  // statepoints surviving this pass.  This makes testing easier and the
+  // resulting IR less confusing to human readers.
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  bool MadeChange = removeUnreachableBlocks(F, nullptr, &DTU);
+
+  // Rewrite all the calls that need statepoints to invokes, so we can
+  // attach a stack map through its landing pad.
+  SmallVector<CallInst *, 64> Calls;
+  for (Instruction &I : instructions(F))
+    if (NeedsRewrite(I) && isa<CallInst>(I))
+      Calls.push_back(cast<CallInst>(&I));
+
+  if (!Calls.empty()) {
+    MadeChange = true;
+
+    for (CallInst *CI : Calls) {
+      // Create a dummy landing pad block.
+      LLVMContext &C = F.getContext();
+      BasicBlock *PadBB = BasicBlock::Create(C, "dummy", &F);
+      Type *ExnTy = StructType::get(Type::getInt8PtrTy(C), Type::getInt32Ty(C));
+
+      LandingPadInst *LPad =
+          LandingPadInst::Create(ExnTy, 1, "dummy.ex", PadBB);
+      LPad->addClause(Constant::getNullValue(Type::getInt8PtrTy(C)));
+      new UnreachableInst(PadBB->getContext(), PadBB);
+
+      BasicBlock *Old = CI->getParent();
+      BasicBlock *New = changeToInvokeAndSplitBasicBlock(CI, PadBB);
+
+      // Old dominates New. New node dominates all other nodes dominated by Old.
+      DomTreeNode *OldNode = DT.getNode(Old);
+      std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
+
+      DomTreeNode *NewNode = DT.addNewBlock(New, Old);
+      for (DomTreeNode *I : Children)
+        DT.changeImmediateDominator(I, NewNode);
+
+      DTU.insertEdge(Old, PadBB);
+    }
+  }
+
+  // We should not run removeUnreachableBlocks at this point, as it
+  // will remove the dummy landing pads.
+
+  // 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<CallSite, 64> ParsePointNeeded;
+  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(CallSite(&I));
+    }
+  }
+
+  // Return early if no work to do.
+  if (ParsePointNeeded.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()) {
+      MadeChange = true;
+      FoldSingleEntryPHINodes(&BB);
+    }
+
+  // Before we start introducing relocations, we want to tweak the IR a bit to
+  // avoid unfortunate code generation effects.  The main example is that we
+  // want to try to make sure the comparison feeding a branch is after any
+  // safepoints.  Otherwise, we end up with a comparison of pre-relocation
+  // values feeding a branch after relocation.  This is semantically correct,
+  // but results in extra register pressure since both the pre-relocation and
+  // post-relocation copies must be available in registers.  For code without
+  // relocations this is handled elsewhere, but teaching the scheduler to
+  // reverse the transform we're about to do would be slightly complex.
+  // Note: This may extend the live range of the inputs to the icmp and thus
+  // increase the liveset of any statepoint we move over.  This is profitable
+  // as long as all statepoints are in rare blocks.  If we had in-register
+  // lowering for live values this would be a much safer transform.
+  auto getConditionInst = [](Instruction *TI) -> Instruction* {
+    if (auto *BI = dyn_cast<BranchInst>(TI))
+      if (BI->isConditional())
+        return dyn_cast<Instruction>(BI->getCondition());
+    // TODO: Extend this to handle switches
+    return nullptr;
+  };
+  for (BasicBlock &BB : F) {
+    Instruction *TI = BB.getTerminator();
+    if (auto *Cond = getConditionInst(TI))
+      // TODO: Handle more than just ICmps here.  We should be able to move
+      // most instructions without side effects or memory access.
+      if (isa<ICmpInst>(Cond) && Cond->hasOneUse()) {
+        MadeChange = true;
+        Cond->moveBefore(TI);
+      }
+  }
+
+  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.
+
+static Value*
+isAlloca(Value *V, DefiningValueMapTy &DVCache) {
+  Value *Base = findBaseOrBDV(V, DVCache);
+  return isa<AllocaInst>(Base) ? Base : nullptr;
+}
+
+static Value*
+isTrackedAlloca(Value *V, DefiningValueMapTy &DVCache) {
+  Value *Base = isAlloca(V, DVCache);
+  if (Base &&
+      hasPointer(Base->getType()->getPointerElementType()))
+    return Base;
+  return nullptr;
+}
+
+/// Compute the live-in set for the location rbegin starting from
+/// the live-out set of the basic block
+static void computeLiveInValues(BasicBlock::reverse_iterator Begin,
+                                BasicBlock::reverse_iterator End,
+                                SetVector<Value *> &LiveTmp,
+                                SetVector<Value *> &AddrTakenAllocas,
+                                DefiningValueMapTy &DVCache) {
+  for (auto &I : make_range(Begin, End)) {
+    // KILL/Def - Remove this definition from LiveIn
+    LiveTmp.remove(&I);
+
+    // Don't consider *uses* in PHI nodes, we handle their contribution to
+    // predecessor blocks when we seed the LiveOut sets
+    if (isa<PHINode>(I))
+      continue;
+
+    // USE - Add to the LiveIn set for this instruction
+    for (Value *V : I.operands()) {
+      // FIXME: skip FCA for now. They appear when pass/return aggregate type
+      // in registers (e.g. {i8*, i8*}). They don't seem live across
+      // statepoints, so we are probably fine.
+      //assert(!isUnhandledGCPointerType(V->getType()) &&
+      //       "support for FCA unimplemented");
+      if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
+        // The choice to exclude all things constant here is slightly subtle.
+        // There are two independent reasons:
+        // - We assume that things which are constant (from LLVM's definition)
+        // do not move at runtime.  For example, the address of a global
+        // variable is fixed, even though it's contents may not be.
+        // - Second, we can't disallow arbitrary inttoptr constants even
+        // if the language frontend does.  Optimization passes are free to
+        // locally exploit facts without respect to global reachability.  This
+        // can create sections of code which are dynamically unreachable and
+        // contain just about anything.  (see constants.ll in tests)
+
+        if (isAlloca(V, DVCache)) {
+          Value *Base = isTrackedAlloca(V, DVCache);
+          if (!Base || AddrTakenAllocas.count(Base))
+            continue;
+
+          // For non-address-taken alloca, record its use.
+          if (isa<DbgInfoIntrinsic>(I) || isa<BitCastInst>(I) ||
+              isa<GetElementPtrInst>(I) || isa<ICmpInst>(I) ||
+              isa<AddrSpaceCastInst>(I))
+            // Not real use.
+            continue;
+          if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<InvokeInst>(I)) {
+            LiveTmp.insert(Base);
+            continue;
+          }
+
+          if (CallInst *CI = dyn_cast<CallInst>(&I)) {
+            if (Function *Fn = CI->getCalledFunction())
+              switch (Fn->getIntrinsicID()) {
+              case Intrinsic::lifetime_start:
+              case Intrinsic::lifetime_end:
+              case Intrinsic::assume:
+                // Not real use.
+                continue;
+              default:
+                break;
+              }
+            LiveTmp.insert(Base);
+            continue;
+          }
+
+          // We know it is not address-taken, other operation should not happen.
+          assert(false && "illegal operation on non-address-taken alloca");
+        }
+
+        LiveTmp.insert(V);
+      }
+    }
+  }
+}
+
+// Compute the def and kill of allocas.
+static void
+computeAllocaDefs(BasicBlock::iterator Begin,
+                  BasicBlock::iterator End,
+                  SetVector<Value *> &AllocaDefs,
+                  SetVector<Value *> &AllocaKills,
+                  DefiningValueMapTy &DVCache) {
+  for (auto &I : make_range(Begin, End)) {
+    // skip Phi ?
+    if (isa<PHINode>(I))
+      continue;
+
+    if (StoreInst *SI = dyn_cast<StoreInst>(&I)){
+      Value *V = SI->getPointerOperand();
+      if (Value *Base = isTrackedAlloca(V, DVCache))
+        AllocaDefs.insert(Base);
+      continue;
+    }
+
+    if (CallInst *CI = dyn_cast<CallInst>(&I)){
+      if (CI->hasStructRetAttr()) {
+        Value *V = CI->getOperand(0);
+        if (Value *Base = isTrackedAlloca(V, DVCache))
+          AllocaDefs.insert(Base);
+      }
+      if (Function *Fn = CI->getCalledFunction())
+        switch (Fn->getIntrinsicID()) {
+        case Intrinsic::memmove:
+        case Intrinsic::memcpy:
+        case Intrinsic::memset: {
+          // We're writing to the first arg.
+          Value *V = CI->getOperand(0);
+          if (Value *Base = isTrackedAlloca(V, DVCache))
+            AllocaDefs.insert(Base);
+          break;
+        }
+        case Intrinsic::lifetime_end: {
+          Value *V = CI->getOperand(1);
+          if (Value *Base = isTrackedAlloca(V, DVCache)) {
+            AllocaKills.insert(Base);
+            // We don't remove it from def set, since we will subtract
+            // the kill set anyway. And when a slot is initialized and
+            // then killed in the same block, we don't lose information.
+          }
+          break;
+        }
+        default:
+          break;
+        }
+      continue;
+    }
+
+    if (InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
+      if (II->hasStructRetAttr()) {
+        Value *V = II->getOperand(0);
+        if (Value *Base = isTrackedAlloca(V, DVCache))
+          AllocaDefs.insert(Base);
+      }
+      continue;
+    }
+  }
+}
+
+// Determine whether an alloca has its address taken.
+// We use different mechanisms to track the liveness of
+// address-taken and non-address-taken allocas.
+static void
+determineAllocaAddrTaken(Function &F,
+                         SetVector<Value *> &AddrTakenAllocas,
+                         DefiningValueMapTy &DVCache) {
+  // Use the metadata inserted by the FE.
+  for (Instruction &I : F.getEntryBlock())
+    if (isa<AllocaInst>(I) && I.getMetadata("go_addrtaken"))
+      AddrTakenAllocas.insert(&I);
+
+  // The FE's addrtaken mark may be imprecise. Look for certain
+  // operations in the IR to mark as addrtaken.
+  // The address may be passed as argument to functions. We trust
+  // the FE that if it is not marked as addrtaken, the function
+  // won't hold its address. (for example, the equality function
+  // of aggregate types.)
+  for (Instruction &I : instructions(F)) {
+    if (isa<PHINode>(I) || isa<SelectInst>(I))
+      // Phi/select could happen even it is not really addrtaken:
+      // for example, an IR transformation like
+      //   if (cond) { x = a } else { x = b }
+      // ==>
+      //   if (cond) { tmp = &a } else { tmp = &b }; x = *tmp
+      // Things get complicated with them. For now, treat them as
+      // address taken.
+      for (Value *V : I.operands()) {
+        if (!isHandledGCPointerType(V->getType()))
+          continue;
+        if (Value *Base = isTrackedAlloca(V, DVCache))
+          AddrTakenAllocas.insert(Base);
+      }
+    else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
+      // If the address of a slot is stored, it must be addrtaken.
+      // In most cases the FE marks it. One exception is the array
+      // holding the ... args.
+      // TODO: maybe we should fix the FE?
+      Value *V = SI->getValueOperand();
+      if (isHandledGCPointerType(V->getType()))
+        if (Value *Base = isTrackedAlloca(V, DVCache))
+          AddrTakenAllocas.insert(Base);
+    }
+  }
+}
+
+static void computeLiveOutSeed(BasicBlock *BB, SetVector<Value *> &LiveTmp,
+                               DefiningValueMapTy &DVCache) {
+  for (BasicBlock *Succ : successors(BB)) {
+    for (auto &I : *Succ) {
+      PHINode *PN = dyn_cast<PHINode>(&I);
+      if (!PN)
+        break;
+
+      Value *V = PN->getIncomingValueForBlock(BB);
+      // FIXME: skip FCA for now, see the comment in computeLiveInValues.
+      //assert(!isUnhandledGCPointerType(V->getType()) &&
+      //       "support for FCA unimplemented");
+      if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
+        if (isAlloca(V, DVCache))
+          // Alloca is tracked separately. (It is a Phi arg so it
+          // must be address-taken.)
+          continue;
+        LiveTmp.insert(V);
+      }
+    }
+  }
+}
+
+static SetVector<Value *> computeKillSet(BasicBlock *BB, DefiningValueMapTy &DVCache) {
+  SetVector<Value *> KillSet;
+  for (Instruction &I : *BB) {
+    if (isHandledGCPointerType(I.getType()))
+      KillSet.insert(&I);
+  }
+  return KillSet;
+}
+
+#ifndef NDEBUG
+/// Check that the items in 'Live' dominate 'TI'.  This is used as a basic
+/// sanity check for the liveness computation.
+static void checkBasicSSA(DominatorTree &DT, SetVector<Value *> &Live,
+                          Instruction *TI, bool TermOkay = false) {
+  for (Value *V : Live) {
+    if (auto *I = dyn_cast<Instruction>(V)) {
+      // The terminator can be a member of the LiveOut set.  LLVM's definition
+      // of instruction dominance states that V does not dominate itself.  As
+      // such, we need to special case this to allow it.
+      if (TermOkay && TI == I)
+        continue;
+      assert(DT.dominates(I, TI) &&
+             "basic SSA liveness expectation violated by liveness analysis");
+    }
+  }
+}
+
+/// Check that all the liveness sets used during the computation of liveness
+/// obey basic SSA properties.  This is useful for finding cases where we miss
+/// a def.
+static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data,
+                          BasicBlock &BB) {
+  checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator());
+  checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true);
+  checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator());
+}
+#endif
+
+// For initialization of an aggregate-typed slot, check whether the
+// whole storage is initialized before we reach a statepoint, and
+// insert zeroing if not.
+// Normally the FE has lifted calls out of the initialization sequence.
+// But they may occur due to optimizations, for example,
+//   type A struct { ...; b B; ... }
+//   type B struct { ... }
+//   a := A{ ..., b: SomeB(), ... }
+// The FE generates something like
+//   %a = alloca A
+//   %tmp = alloca B
+//   call SomeB(%tmp) // as outgoing arg
+//   initialize part of a
+//   call memmove(gep %a, %tmp)
+//   initialize the rest of a
+// The memmove may be optimized out, with direct store to A, as
+//   %a = alloca A
+//   initialize part of a
+//   call SomeB(gep %a)
+//   initialize the rest of a
+// a is live at the call site, but not fully initialized.
+// We need to make sure a doesn't contain bad pointers.
+// TODO: this function is a little too conservative (see below).
+// TODO: instead of zeroing, maybe we can record only the part
+// of A that is live?
+static void
+checkStoreSize(Value *V, BasicBlock &BB, const DataLayout &DL,
+               SetVector<Value *> &ToZero,
+               DefiningValueMapTy &DVCache) {
+  unsigned PtrSize = DL.getPointerSize();
+  unsigned Size = DL.getTypeStoreSize(V->getType()->getPointerElementType());
+  if (Size <= PtrSize)
+    return;
+
+  // We simply add the sizes of all stores in the block, assuming
+  // no overlapping stores (which are silly).
+  unsigned StoreSize = 0;
+  for (Instruction &I : BB) {
+    if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
+      Value *Ptr = SI->getPointerOperand();
+      if (isTrackedAlloca(Ptr, DVCache) == V)
+        StoreSize += DL.getTypeStoreSize(SI->getValueOperand()->getType());
+    } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
+      if (CI->hasStructRetAttr()) {
+        Value *Ptr = CI->getOperand(0);
+        if (isTrackedAlloca(Ptr, DVCache) == V)
+          StoreSize += DL.getTypeStoreSize(Ptr->getType()->getPointerElementType());
+      }
+      if (Function *Fn = CI->getCalledFunction())
+        switch (Fn->getIntrinsicID()) {
+        case Intrinsic::memmove:
+        case Intrinsic::memcpy:
+        case Intrinsic::memset: {
+          // We're writing to the first arg. The third arg is size.
+          Value *Ptr = CI->getOperand(0);
+          if (isTrackedAlloca(Ptr, DVCache) == V) {
+            ConstantInt *Len =
+                dyn_cast<ConstantInt>(cast<MemIntrinsic>(CI)->getLength());
+            if (Len)
+              StoreSize += Len->getZExtValue();
+          }
+          break;
+        }
+        default:
+          break;
+        }
+    } else if (InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
+      if (II->hasStructRetAttr()) {
+        Value *Ptr = II->getOperand(0);
+        if (isTrackedAlloca(Ptr, DVCache) == V)
+          if (DL.getTypeStoreSize(Ptr->getType()->getPointerElementType()) + PtrSize - 1 >= Size)
+            // We are storing the whole type
+            return;
+
+          // Othersize we may have stored pointers into the alloca, which
+          // need to be live, but it is not completely initialized. We need
+          // to zero it.
+          // TODO: no need to zero if all previous stores are scalars.
+      }
+    }
+
+    // We only care about pointers, so it's safe to round up to a pointer size.
+    // TODO: things with more than a simple padding may still be false positive.
+    // TODO: if the missing fields are all scalars, no need to zero.
+    if (StoreSize + PtrSize - 1 >= Size)
+      return; // early return if we have stored enough.
+  }
+
+  // Incomplete initialization, needs zeroing.
+  if (StoreSize + PtrSize - 1 < Size)
+    ToZero.insert(V);
+}
+
+static void computeLiveInValues(DominatorTree &DT, Function &F,
+                                GCPtrLivenessData &Data,
+                                SetVector<Value *> &AddrTakenAllocas,
+                                SetVector<Value *> &ToZero,
+                                DefiningValueMapTy &DVCache) {
+  SmallSetVector<BasicBlock *, 32> Worklist;
+
+  determineAllocaAddrTaken(F, AddrTakenAllocas, DVCache);
+  if (PrintLiveSet) {
+    dbgs() << "AddrTakenAllocas:\n";
+    printLiveSet(AddrTakenAllocas);
+  }
+
+  // Seed the liveness for each individual block
+  for (BasicBlock &BB : F) {
+    Data.KillSet[&BB] = computeKillSet(&BB, DVCache);
+    Data.LiveSet[&BB].clear();
+    computeLiveInValues(BB.rbegin(), BB.rend(), Data.LiveSet[&BB], AddrTakenAllocas, DVCache);
+    computeAllocaDefs(BB.begin(), BB.end(), Data.AllocaDefSet[&BB], Data.AllocaKillSet[&BB], DVCache);
+    if (!BB.isLandingPad()) {
+      Data.AllocaDefAny[&BB] = Data.AllocaDefSet[&BB];
+      Data.AllocaDefAny[&BB].set_subtract(Data.AllocaKillSet[&BB]);
+    }
+    Data.LiveOut[&BB] = SetVector<Value *>();
+    computeLiveOutSeed(&BB, Data.LiveOut[&BB], DVCache);
+
+#ifndef NDEBUG
+    for (Value *Kill : Data.KillSet[&BB])
+      assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill");
+#endif
+  }
+
+  // Propagate Alloca def any/all until stable.
+  bool changed = true;
+  while (changed) {
+    changed = false;
+    for (BasicBlock &BB : F) {
+      // Don't propagate through landing pad. The whole frame is
+      // essentially dead when an exception is thrown.
+      if (BB.isLandingPad()) {
+        assert(Data.AllocaDefAny[&BB].empty());
+        continue;
+      }
+
+      unsigned OldSize = Data.AllocaDefAny[&BB].size();
+      for (BasicBlock *Pred : predecessors(&BB))
+        Data.AllocaDefAny[&BB].set_union(Data.AllocaDefAny[Pred]);
+      Data.AllocaDefAny[&BB].set_subtract(Data.AllocaKillSet[&BB]);
+      if (Data.AllocaDefAny[&BB].size() != OldSize)
+        changed = true;
+    }
+  }
+  for (BasicBlock &BB : F)
+    Data.AllocaDefAll[&BB] = Data.AllocaDefAny[&BB];
+  changed = true;
+  while (changed) {
+    changed = false;
+    for (BasicBlock &BB : F) {
+      auto NotDefAll = [&](Value *V){
+        if (Data.AllocaDefSet[&BB].count(V) != 0)
+          return false;
+        for (BasicBlock *Pred : predecessors(&BB))
+          if (Data.AllocaDefAll[Pred].count(V) == 0)
+            return true;
+        return false;
+      };
+      if (Data.AllocaDefAll[&BB].remove_if(NotDefAll))
+        changed = true;
+    }
+  }
+
+  const DataLayout &DL = F.getParent()->getDataLayout();
+
+  // An alloca is live only after it is initialized.
+  // It is initialized in a block if it is defined there and not defined
+  // in all of the predecessors (or there is no predecessors).
+  for (BasicBlock &BB : F) {
+    for (Value *V : Data.AllocaDefSet[&BB]) {
+      bool Init = false;
+      if (&BB == &F.getEntryBlock())
+        Init = true;
+      for (BasicBlock *Pred : predecessors(&BB))
+        if (!Data.AllocaDefAll[Pred].count(V)) {
+          Init = true;
+          break;
+        }
+      if (!Init)
+        continue;
+      if (!AddrTakenAllocas.count(V)) { // addr-taken alloca is tracked separately
+        Data.KillSet[&BB].insert(V);
+        Data.LiveSet[&BB].remove(V);
+      }
+
+      // If it is incomplete initialization, it needs zeroing.
+      checkStoreSize(V, BB, DL, ToZero, DVCache);
+    }
+  }
+
+  for (BasicBlock &BB : F) {
+    Data.LiveIn[&BB] = Data.LiveSet[&BB];
+    Data.LiveIn[&BB].set_union(Data.LiveOut[&BB]);
+    Data.LiveIn[&BB].set_subtract(Data.KillSet[&BB]);
+    if (!Data.LiveIn[&BB].empty())
+      Worklist.insert(pred_begin(&BB), pred_end(&BB));
+  }
+
+  // Propagate liveness until stable
+  while (!Worklist.empty()) {
+    BasicBlock *BB = Worklist.pop_back_val();
+
+    // Compute our new liveout set, then exit early if it hasn't changed despite
+    // the contribution of our successor.
+    SetVector<Value *> LiveOut = Data.LiveOut[BB];
+    const auto OldLiveOutSize = LiveOut.size();
+    for (BasicBlock *Succ : successors(BB)) {
+      if (Succ->isLandingPad())
+        // Don't propagate through landing pad. The frame should be dead at this point.
+        continue;
+      assert(Data.LiveIn.count(Succ));
+      LiveOut.set_union(Data.LiveIn[Succ]);
+    }
+    // assert OutLiveOut is a subset of LiveOut
+    if (OldLiveOutSize == LiveOut.size()) {
+      // If the sets are the same size, then we didn't actually add anything
+      // when unioning our successors LiveIn.  Thus, the LiveIn of this block
+      // hasn't changed.
+      continue;
+    }
+    Data.LiveOut[BB] = LiveOut;
+
+    // Apply the effects of this basic block
+    SetVector<Value *> LiveTmp = LiveOut;
+    LiveTmp.set_union(Data.LiveSet[BB]);
+    LiveTmp.set_subtract(Data.KillSet[BB]);
+
+    assert(Data.LiveIn.count(BB));
+    const SetVector<Value *> &OldLiveIn = Data.LiveIn[BB];
+    // assert: OldLiveIn is a subset of LiveTmp
+    if (OldLiveIn.size() != LiveTmp.size()) {
+      Data.LiveIn[BB] = LiveTmp;
+      Worklist.insert(pred_begin(BB), pred_end(BB));
+    }
+  } // while (!Worklist.empty())
+
+  // Sanity check: live alloca must be initialized.
+  // In some rare case it may be recorded live even before
+  // initialization. (I saw this as a result of loop hoisting.)
+  // In this case, we don't mark them live.
+  for (BasicBlock &BB : F) {
+    auto NotDefAll = [&](Value *V){
+      if (isa<AllocaInst>(V)) {
+        if (!Data.AllocaDefAll[&BB].count(V)) {
+          //dbgs() << "!!! alloca live but not initialized:\n\t" <<
+          //          F.getName() << "  " << BB.getName() << "\n" << *V << "\n";
+          return true;
+        }
+      }
+      return false;
+    };
+    Data.LiveOut[&BB].remove_if(NotDefAll);
+  }
+
+  // After this point, we only care address-taken allocas. Remove the rest.
+  for (BasicBlock &BB : F) {
+    auto NotAddrTaken = [&](Value *V){ return !AddrTakenAllocas.count(V); };
+    Data.AllocaDefAny[&BB].remove_if(NotAddrTaken);
+
+    // AllocaDefAll doesn't really matter, because we subtract it below.
+    // Update it just for printing.
+    Data.AllocaDefAll[&BB].remove_if(NotAddrTaken);
+  }
+
+  // Address-taken allocas initialized and not killed at the end of block is live-out.
+  // We don't update live-in sets, since live-in is not used after this point.
+  for (BasicBlock &BB : F)
+    Data.LiveOut[&BB].set_union(Data.AllocaDefAny[&BB]);
+
+  // Record ambiguously live slots (AllocaDefAny - AllocaDefAll), which we need to zero.
+  for (BasicBlock &BB : F) {
+    if (PrintLiveSet) {
+      dbgs() << BB.getName() << " AllocaDefAny:\n";
+      printLiveSet(Data.AllocaDefAny[&BB]);
+      dbgs() << BB.getName() << " AllocaDefAll:\n";
+      printLiveSet(Data.AllocaDefAll[&BB]);
+    }
+
+    // NOTE: this clobbers AllocaDefAny. Don't use it after this point.
+    Data.AllocaDefAny[&BB].set_subtract(Data.AllocaDefAll[&BB]);
+    ToZero.set_union(Data.AllocaDefAny[&BB]);
+
+    if (PrintLiveSet) {
+      dbgs() << BB.getName() << " ambiguously live:\n";
+      printLiveSet(Data.AllocaDefAny[&BB]);
+      dbgs() << BB.getName() << " LiveOut:\n";
+      printLiveSet(Data.LiveOut[&BB]);
+    }
+  }
+
+#ifndef NDEBUG
+  // Sanity check our output against SSA properties.  This helps catch any
+  // missing kills during the above iteration.
+  for (BasicBlock &BB : F)
+    checkBasicSSA(DT, Data, BB);
+#endif
+}
+
+static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data,
+                              SetVector<Value *> &AddrTakenAllocas,
+                              StatepointLiveSetTy &Out,
+                              DefiningValueMapTy &DVCache) {
+  BasicBlock *BB = Inst->getParent();
+
+  // Note: The copy is intentional and required
+  assert(Data.LiveOut.count(BB));
+  SetVector<Value *> LiveOut = Data.LiveOut[BB];
+
+  // We want to handle the statepoint itself oddly.  It's
+  // call result is not live (normal), nor are it's arguments
+  // (unless they're used again later).  This adjustment is
+  // specifically what we need to relocate
+  computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(),
+                      LiveOut, AddrTakenAllocas, DVCache);
+  LiveOut.remove(Inst);
+
+  // The statepoint is always an invoke instruction, which is the last
+  // instruction in the block. The only thing it can initialize is the
+  // outgoing arg.
+  if (InvokeInst *II = dyn_cast<InvokeInst>(Inst))
+    if (II->hasStructRetAttr()) {
+      Value *Ptr = II->getOperand(0);
+      Value *V = Ptr->stripPointerCasts();
+      const DataLayout &DL = Inst->getModule()->getDataLayout();
+      if (!Data.LiveIn[BB].count(V) &&
+          (DL.getTypeStoreSize(Ptr->getType()->getPointerElementType()) >=
+           DL.getTypeStoreSize(V->getType()->getPointerElementType())))
+        LiveOut.remove(V);
+    }
+
+  Out.insert(LiveOut.begin(), LiveOut.end());
+}
diff --git a/passes/GoStatepoints.h b/passes/GoStatepoints.h
new file mode 100644
index 0000000..68d884c
--- /dev/null
+++ b/passes/GoStatepoints.h
@@ -0,0 +1,39 @@
+//===- GoStatepoints.h - --------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides interface to the "Go statepoints" pass.
+//
+// Rewrite call/invoke instructions so as to record live variables on
+// stack for the use of garbage collector.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_GOLLVM_PASSES_GOSTATEPOINTS_H
+#define LLVM_GOLLVM_PASSES_GOSTATEPOINTS_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class DominatorTree;
+class Function;
+class Module;
+class TargetTransformInfo;
+class TargetLibraryInfo;
+
+struct GoStatepoints : public PassInfoMixin<GoStatepoints> {
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
+
+  bool runOnFunction(Function &F, DominatorTree &, TargetTransformInfo &,
+                     const TargetLibraryInfo &);
+};
+
+} // namespace llvm
+
+#endif // LLVM_GOLLVM_PASSES_GOSTATEPOINTS_H
diff --git a/passes/GollvmPasses.h b/passes/GollvmPasses.h
index 34eba1b..61c141e 100644
--- a/passes/GollvmPasses.h
+++ b/passes/GollvmPasses.h
@@ -9,15 +9,38 @@
 #ifndef LLVM_GOLLVM_PASSES_GOLLVMPASSES_H
 #define LLVM_GOLLVM_PASSES_GOLLVMPASSES_H
 
+#include "llvm/ADT/SmallVector.h"
+
 namespace llvm {
 
-class PassRegistry;
+class DataLayout;
 class FunctionPass;
+class ModulePass;
+class PassRegistry;
+class Type;
+class Value;
 
 void initializeGoAnnotationPass(PassRegistry&);
+void initializeGoStatepointsLegacyPassPass(PassRegistry&);
 
 FunctionPass *createGoAnnotationPass();
+ModulePass *createGoStatepointsLegacyPass();
 
 } // namespace llvm
 
+namespace gollvm {
+namespace passes {
+
+// Helper functions.
+
+// Whether a type contains pointer.
+bool hasPointer(llvm::Type *);
+
+// Compute the pointer bitmap for type T, stored into Words.
+void getPtrBitmapForType(llvm::Type *T, const llvm::DataLayout &DL,
+                         llvm::SmallVectorImpl<llvm::Value *> &Words);
+
+} // namespace passes
+} // namespace gollvm
+
 #endif
diff --git a/passes/Util.cpp b/passes/Util.cpp
new file mode 100644
index 0000000..8076669
--- /dev/null
+++ b/passes/Util.cpp
@@ -0,0 +1,118 @@
+//===--- Util.cpp ---------------------------------------------------------===//
+//
+// Copyright 2018 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+//
+//===----------------------------------------------------------------------===//
+//
+// Helper functions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "GollvmPasses.h"
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Value.h"
+
+using namespace llvm;
+using namespace gollvm::passes;
+
+// Whether a type contains pointer.
+bool
+gollvm::passes::hasPointer(Type *T) {
+  switch (T->getTypeID()) {
+  case Type::PointerTyID:
+    return true;
+  case Type::ArrayTyID:
+    return hasPointer(T->getArrayElementType());
+  case Type::VectorTyID:
+    return hasPointer(T->getVectorElementType());
+  case Type::StructTyID: {
+    for (unsigned i = 0, e = T->getStructNumElements(); i < e; ++i)
+      if (hasPointer(T->getStructElementType(i)))
+        return true;
+    return false;
+  }
+  default:
+    return false;
+  }
+}
+
+static void
+getPtrBitmapForTypeHelper(Type *T, const DataLayout &DL, uint64_t BaseOffset, BitVector &BV) {
+  if (!hasPointer(T))
+    return;
+
+  const unsigned PtrSize = DL.getPointerSize();
+  Type *Int32Ty = Type::getInt32Ty(T->getContext());
+  switch (T->getTypeID()) {
+  case Type::PointerTyID:
+    BV.set(BaseOffset / PtrSize);
+    break;;
+  case Type::ArrayTyID: {
+    Type *ET = T->getArrayElementType();
+    for (unsigned i = 0, n = T->getArrayNumElements(); i < n; ++i) {
+      ArrayRef<Value*> Idx = { ConstantInt::get(Int32Ty, 0), ConstantInt::get(Int32Ty, i) };
+      uint64_t Offset = DL.getIndexedOffsetInType(T, Idx);
+      getPtrBitmapForTypeHelper(ET, DL, BaseOffset+Offset, BV);
+    }
+    break;
+  }
+  case Type::VectorTyID: {
+    Type *ET = T->getVectorElementType();
+    for (unsigned i = 0, n = T->getVectorNumElements(); i < n; ++i) {
+      ArrayRef<Value*> Idx = { ConstantInt::get(Int32Ty, 0), ConstantInt::get(Int32Ty, i) };
+      uint64_t Offset = DL.getIndexedOffsetInType(T, Idx);
+      getPtrBitmapForTypeHelper(ET, DL, BaseOffset+Offset, BV);
+    }
+    break;
+  }
+  case Type::StructTyID: {
+    for (unsigned i = 0, n = T->getStructNumElements(); i < n; ++i) {
+      Type *ET = T->getStructElementType(i);
+      if (!hasPointer(ET))
+        continue;
+      ArrayRef<Value*> Idx = { ConstantInt::get(Int32Ty, 0), ConstantInt::get(Int32Ty, i) };
+      uint64_t Offset = DL.getIndexedOffsetInType(T, Idx);
+      getPtrBitmapForTypeHelper(ET, DL, BaseOffset+Offset, BV);
+    }
+    break;
+  }
+  default:
+    break;
+  }
+}
+
+// Compute the pointer bitmap for type T, stored into Words.
+void
+gollvm::passes::getPtrBitmapForType(Type *T, const DataLayout &DL,
+                                    SmallVectorImpl<Value *> &Words) {
+  // TODO: this function is silly -- BitVector internally has
+  // a bitmap storage, but it is private. Can we do better?
+
+  const unsigned PtrSize = DL.getPointerSize();
+  Type *Int32Ty = Type::getInt32Ty(T->getContext());
+  uint64_t Size = DL.getTypeStoreSize(T);
+  BitVector BV(Size/PtrSize);
+
+  getPtrBitmapForTypeHelper(T, DL, 0, BV);
+
+  if (BV.none())
+    return;
+  unsigned last = BV.find_last();
+  if (last == 0) // a single pointer field, no need of a bitmap
+    return;
+  //Words.reserve(last/32 + 1);
+  for (unsigned i = 0; i <= last; i += 32) {
+    uint32_t w = 0;
+    for (unsigned j = 0; j < 32 && i+j <= last; j++)
+      w |= BV[i+j] ? 1<<j : 0;
+    Words.push_back(ConstantInt::get(Int32Ty, w));
+  }
+}