[RewriteStatepointsForGC] Remove the hardcoded GC strategy names

[znix]

Summary

Previously, RewriteStatepointsForGC had a hardcoded list of GC
strategies for which it would run, and using it with a custom strategy
required patching LLVM.

The locic for selecting the variables that are considered managed was
also hardcoded to use pointers in address space 1, rather than
delegating to GCStrategy::isGCManagedPointer.

This patch fixes both of these flaws: this pass now applies to all
functions whose GCStrategy returns true for useStatepoints, and checking
if a pointer is managed or not is also now done by the strategy.

One potentially questionable design decision in this change: the pass will
be enabled for all GC strategies that use statepoints. It seems unlikely
this would be a problem - consumers that don't use this pass probably
aren't adding it to the pass manager anyway - but if you had two different
GC strategies and only one wants this pass enabled then that'd need a new
flag in GCStrategy, which I can add if anyone thinks it's necessary.

[znix]

I'm not sure why the tests are failing? It looks like a linkage issue:

LLVM ERROR: unsupported GC: statepoint-example (did you remember to link and initialize the library?)

I'm not sure why this would occur in the tests, but not locally. I built with BUILD_SHARED_LIBS which I'm guessing has something to do with it, but llvm/lib/IR/BuiltinGCs.cpp (where the statepoint-example GC registration is located) is in LLVMCore so I'd expect it to always be initialised?

[dantrushin]

In D140458#4010049, @znix wrote:

I'm not sure why the tests are failing? It looks like a linkage issue:

LLVM ERROR: unsupported GC: statepoint-example (did you remember to link and initialize the library?)

I'm not sure why this would occur in the tests, but not locally. I built with BUILD_SHARED_LIBS which I'm guessing has something to do with it, but llvm/lib/IR/BuiltinGCs.cpp (where the statepoint-example GC registration is located) is in LLVMCore so I'd expect it to always be initialised?

This exact issue prevented me from landing similar patch in the past. And I did not figure out what was going on there.
static initializers are definitely running, but at the time RS4GC runs relevant array is zeroed (is BSS initialization happens _after_ C++ static initializers? or we have multiple copies?)
Unfortunately I had not enough time to find out.

[znix]

This diff was superseded by D141110.

llvm/docs/Statepoints.rst

 ^^^^^^^^^^^^^^^^^^^^^^^^
 
 The pass RewriteStatepointsForGC transforms a function's IR to lower from the
 abstract machine model described above to the explicit statepoint model of
 relocations.  To do this, it replaces all calls or invokes of functions which
 might contain a safepoint poll with a ``gc.statepoint`` and associated full
 relocation sequence, including all required ``gc.relocates``.
 
-Note that by default, this pass only runs for the "statepoint-example" or
-"core-clr" gc strategies.  You will need to add your custom strategy to this
-list or use one of the predefined ones.
-
 As an example, given this code:
 
 .. code-block:: llvm
 
   define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
          gc "statepoint-example" {
     call void @foo()
     ret i8 addrspace(1)* %obj
   }
 
 The pass would produce this IR:
 
 .. code-block:: llvm
 
   define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj)
          gc "statepoint-example" {
     %0 = call token (i64, i32, void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @foo, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0, i8 addrspace(1)* %obj)
     %obj.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %0, i32 12, i32 12)
     ret i8 addrspace(1)* %obj.relocated
   }
 
 In the above examples, the addrspace(1) marker on the pointers is the mechanism
 that the ``statepoint-example`` GC strategy uses to distinguish references from
 non references.  The pass assumes that all addrspace(1) pointers are non-integral
-pointer types.  Address space 1 is not globally reserved for this purpose.
+pointer types.  Address space 1 is not globally reserved for this purpose.  This
+is controlled via GCStrategy::isGCManagedPointer, which checks for addrspace(1)
+in the ``statepoint-example`` and ``coreclr`` strategies, however custom
+strategies don't have to follow this convention.
 
 This pass can be used an utility function by a language frontend that doesn't
 want to manually reason about liveness, base pointers, or relocation when
 constructing IR.  As currently implemented, RewriteStatepointsForGC must be
 run after SSA construction (i.e. mem2ref).
 
 RewriteStatepointsForGC will ensure that appropriate base pointers are listed
 for every relocation created.  It will do so by duplicating code as needed to

llvm/include/llvm/Transforms/Scalar/RewriteStatepointsForGC.h

 
 namespace llvm {
 
 class DominatorTree;
 class Function;
 class Module;
 class TargetTransformInfo;
 class TargetLibraryInfo;
+class GCStrategy;
 
 struct RewriteStatepointsForGC : public PassInfoMixin<RewriteStatepointsForGC> {
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
   bool runOnFunction(Function &F, DominatorTree &, TargetTransformInfo &,
-                     const TargetLibraryInfo &);
+                     const TargetLibraryInfo &, GCStrategy *);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_REWRITESTATEPOINTSFORGC_H

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

 #include "llvm/IR/BasicBlock.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/Dominators.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/GCStrategy.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/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 <map>
 #include <optional>
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>
 
 #define DEBUG_TYPE "rewrite-statepoints-for-gc"
 

 static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",
                                                   cl::location(ClobberNonLive),
                                                   cl::Hidden);
 
 static cl::opt<bool>
     AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info",
                                    cl::Hidden, cl::init(true));
 
+using GCStrategyCache = std::map<StringRef, std::unique_ptr<GCStrategy>>;
+
 /// The IR fed into RewriteStatepointsForGC may have had attributes and
 /// metadata implying dereferenceability that are no longer valid/correct after
 /// RewriteStatepointsForGC has run. This is because semantically, after
 /// RewriteStatepointsForGC 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.
-static void stripNonValidData(Module &M);
+static void stripNonValidData(Module &M, GCStrategyCache &strategies);
+
+// Find the GC strategy for a function, or null if it doesn't have one.
+// Since this may involve creating the strategy, they're cached and stored in
+// the provided map.
+static GCStrategy *findGCStrategy(Function &F, GCStrategyCache &cache);
 
-static bool shouldRewriteStatepointsIn(Function &F);
+static bool shouldRewriteStatepointsIn(Function &F, GCStrategy *GC);
 
 PreservedAnalyses RewriteStatepointsForGC::run(Module &M,
                                                ModuleAnalysisManager &AM) {
   bool Changed = false;
   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+  GCStrategyCache strategies;
   for (Function &F : M) {
     // Nothing to do for declarations.
     if (F.isDeclaration() || F.empty())
       continue;
 
+    GCStrategy *GC = findGCStrategy(F, strategies);
+
     // Policy choice says not to rewrite - the most common reason is that we're
     // compiling code without a GCStrategy.
-    if (!shouldRewriteStatepointsIn(F))
+    if (!shouldRewriteStatepointsIn(F, GC))
       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);
+    Changed |= runOnFunction(F, DT, TTI, TLI, GC);
   }
   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);
+  stripNonValidData(M, strategies);
 
   PreservedAnalyses PA;
   PA.preserve<TargetIRAnalysis>();
   PA.preserve<TargetLibraryAnalysis>();
   return PA;
 }
 
 namespace {
 
 class RewriteStatepointsForGCLegacyPass : public ModulePass {
   RewriteStatepointsForGC Impl;
 
 public:
   static char ID; // Pass identification, replacement for typeid
 
   RewriteStatepointsForGCLegacyPass() : ModulePass(ID), Impl() {
     initializeRewriteStatepointsForGCLegacyPassPass(
         *PassRegistry::getPassRegistry());
   }
 
   bool runOnModule(Module &M) override {
     bool Changed = false;
+    GCStrategyCache strategies;
     for (Function &F : M) {
       // Nothing to do for declarations.
       if (F.isDeclaration() || F.empty())
         continue;
 
+      GCStrategy *GC = findGCStrategy(F, strategies);
+
       // Policy choice says not to rewrite - the most common reason is that
       // we're compiling code without a GCStrategy.
-      if (!shouldRewriteStatepointsIn(F))
+      if (!shouldRewriteStatepointsIn(F, GC))
         continue;
 
       TargetTransformInfo &TTI =
           getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
       const TargetLibraryInfo &TLI =
           getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
       auto &DT = getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
 
-      Changed |= Impl.runOnFunction(F, DT, TTI, TLI);
+      Changed |= Impl.runOnFunction(F, DT, TTI, TLI, GC);
     }
 
     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);
+    stripNonValidData(M, strategies);
     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>();
if (!DeoptBundle) {
     return std::nullopt;
   }
 
   return DeoptBundle->Inputs;
 }
 
 /// Compute the live-in set for every basic block in the function
 static void computeLiveInValues(DominatorTree &DT, Function &F,
-                                GCPtrLivenessData &Data);
+                                GCPtrLivenessData &Data, GCStrategy *GC);
 
 /// Given results from the dataflow liveness computation, find the set of live
 /// Values at a particular instruction.
 static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,
-                              StatepointLiveSetTy &out);
+                              StatepointLiveSetTy &out, GCStrategy *GC);
 
-// TODO: Once we can get to the GCStrategy, this becomes
-// std::optional<bool> isGCManagedPointer(const Type *Ty) const override {
+static bool isGCPointerType(Type *T, GCStrategy *GC) {
+  assert(GC && "GC Strategy for isGCPointerType cannot be null");
 
-static bool isGCPointerType(Type *T) {
-  if (auto *PT = dyn_cast<PointerType>(T))
-    // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
-    // GC managed heap.  We know that a pointer into this heap needs to be
-    // updated and that no other pointer does.
-    return PT->getAddressSpace() == 1;
+  if (!isa<PointerType>(T))
     return false;
+
+  if (auto IsManaged = GC->isGCManagedPointer(T))
+    return *IsManaged;
+  return true; // conservative - same as StatepointLowering
 }
 
 // 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) {
+static bool isHandledGCPointerType(Type *T, GCStrategy *GC) {
   // We fully support gc pointers
-  if (isGCPointerType(T))
+  if (isGCPointerType(T, GC))
     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()))
+    if (isGCPointerType(VT->getElementType(), GC))
       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))
+static bool containsGCPtrType(Type *Ty, GCStrategy *GC) {
+  if (isGCPointerType(Ty, GC))
     return true;
   if (VectorType *VT = dyn_cast<VectorType>(Ty))
-    return isGCPointerType(VT->getScalarType());
+    return isGCPointerType(VT->getScalarType(), GC);
   if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
-    return containsGCPtrType(AT->getElementType());
+    return containsGCPtrType(AT->getElementType(), GC);
   if (StructType *ST = dyn_cast<StructType>(Ty))
-    return llvm::any_of(ST->elements(), containsGCPtrType);
+    return llvm::any_of(ST->elements(),
+                        [GC](Type *Ty) { return containsGCPtrType(Ty, GC); });
   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);
+static bool isUnhandledGCPointerType(Type *Ty, GCStrategy *GC) {
+  return containsGCPtrType(Ty, GC) && !isHandledGCPointerType(Ty, GC);
 }
 #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();
 }
 
 // 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, CallBase *Call,
-    PartiallyConstructedSafepointRecord &Result) {
+    PartiallyConstructedSafepointRecord &Result, GCStrategy *GC) {
   StatepointLiveSetTy LiveSet;
-  findLiveSetAtInst(Call, OriginalLivenessData, LiveSet);
+  findLiveSetAtInst(Call, OriginalLivenessData, LiveSet, GC);
 
   if (PrintLiveSet) {
     dbgs() << "Live Variables:\n";
     for (Value *V : LiveSet)
       dbgs() << " " << V->getName() << " " << *V << "\n";
   }
   if (PrintLiveSetSize) {
     dbgs() << "Safepoint For: " << Call->getCalledOperand()->getName() << "\n";
findBasePointers(PotentiallyDerivedPointers, PointerToBase, &DT, DVCache,
                    KnownBases);
 }
 
 /// Given an updated version of the dataflow liveness results, update the
 /// liveset and base pointer maps for the call site CS.
 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
                                   CallBase *Call,
                                   PartiallyConstructedSafepointRecord &result,
-                                  PointerToBaseTy &PointerToBase);
+                                  PointerToBaseTy &PointerToBase,
+                                  GCStrategy *GC);
 
 static void recomputeLiveInValues(
     Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate,
     MutableArrayRef<struct PartiallyConstructedSafepointRecord> records,
-    PointerToBaseTy &PointerToBase) {
+    PointerToBaseTy &PointerToBase, GCStrategy *GC) {
   // TODO-PERF: reuse the original liveness, then simply run the dataflow
   // again.  The old values are still live and will help it stabilize quickly.
   GCPtrLivenessData RevisedLivenessData;
-  computeLiveInValues(DT, F, RevisedLivenessData);
+  computeLiveInValues(DT, F, RevisedLivenessData, GC);
   for (size_t i = 0; i < records.size(); i++) {
     struct PartiallyConstructedSafepointRecord &info = records[i];
-    recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info,
-                          PointerToBase);
+    recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info, PointerToBase,
+                          GC);
   }
 }
 
 // Utility function which clones all instructions from "ChainToBase"
 // and inserts them before "InsertBefore". Returns rematerialized value
 // which should be used after statepoint.
 static Instruction *rematerializeChain(ArrayRef<Instruction *> ChainToBase,
                                        Instruction *InsertBefore,

 ///   liveVariables - list of variables to be relocated.
 ///   basePtrs - base pointers.
 ///   statepointToken - statepoint instruction to which relocates should be
 ///   bound.
 ///   Builder - Llvm IR builder to be used to construct new calls.
 static void CreateGCRelocates(ArrayRef<Value *> LiveVariables,
                               ArrayRef<Value *> BasePtrs,
                               Instruction *StatepointToken,
-                              IRBuilder<> &Builder) {
+                              IRBuilder<> &Builder, GCStrategy *GC) {
   if (LiveVariables.empty())
     return;
 
   auto FindIndex = [](ArrayRef<Value *> LiveVec, Value *Val) {
     auto ValIt = llvm::find(LiveVec, Val);
     assert(ValIt != LiveVec.end() && "Val not found in LiveVec!");
     size_t Index = std::distance(LiveVec.begin(), ValIt);
     assert(Index < LiveVec.size() && "Bug in std::find?");
     return Index;
   };
   Module *M = StatepointToken->getModule();
 
   // All gc_relocate are generated as i8 addrspace(1)* (or a vector type whose
   // element type is i8 addrspace(1)*). We originally generated unique
   // declarations for each pointer type, but this proved problematic because
   // the intrinsic mangling code is incomplete and fragile.  Since we're moving
   // towards a single unified pointer type anyways, we can just cast everything
   // to an i8* of the right address space.  A bitcast is added later to convert
   // gc_relocate to the actual value's type.
-  auto getGCRelocateDecl = [&] (Type *Ty) {
-    assert(isHandledGCPointerType(Ty));
+  auto getGCRelocateDecl = [&](Type *Ty) {
+    assert(isHandledGCPointerType(Ty, GC));
     auto AS = Ty->getScalarType()->getPointerAddressSpace();
     Type *NewTy = Type::getInt8PtrTy(M->getContext(), AS);
     if (auto *VT = dyn_cast<VectorType>(Ty))
       NewTy = FixedVectorType::get(NewTy,
                                    cast<FixedVectorType>(VT)->getNumElements());
     return Intrinsic::getDeclaration(M, Intrinsic::experimental_gc_relocate,
                                      {NewTy});
   };

 }
 
 static void
 makeStatepointExplicitImpl(CallBase *Call, /* to replace */
                            const SmallVectorImpl<Value *> &BasePtrs,
                            const SmallVectorImpl<Value *> &LiveVariables,
                            PartiallyConstructedSafepointRecord &Result,
                            std::vector<DeferredReplacement> &Replacements,
-                           const PointerToBaseTy &PointerToBase) {
+                           const PointerToBaseTy &PointerToBase,
+                           GCStrategy *GC) {
   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.
   IRBuilder<> Builder(Call);
 
if (auto *CI = dyn_cast<CallInst>(Call)) {
 
     Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt());
     Builder.SetCurrentDebugLocation(II->getDebugLoc());
 
     // Attach exceptional gc relocates to the landingpad.
     Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();
     Result.UnwindToken = ExceptionalToken;
 
-    CreateGCRelocates(LiveVariables, BasePtrs, ExceptionalToken, Builder);
+    CreateGCRelocates(LiveVariables, BasePtrs, ExceptionalToken, Builder, GC);
 
     // Generate gc relocates and returns for normal block
     BasicBlock *NormalDest = II->getNormalDest();
     assert(!isa<PHINode>(NormalDest->begin()) &&
            NormalDest->getUniquePredecessor() &&
            "can't safely insert in this block!");
 
     Builder.SetInsertPoint(&*NormalDest->getFirstInsertionPt());
if (IsDeoptimize) {
     } else {
       Replacements.emplace_back(DeferredReplacement::createDelete(Call));
     }
   }
 
   Result.StatepointToken = Token;
 
   // Second, create a gc.relocate for every live variable
-  CreateGCRelocates(LiveVariables, BasePtrs, Token, Builder);
+  CreateGCRelocates(LiveVariables, BasePtrs, Token, Builder, GC);
 }
 
 // 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, CallBase *Call,
                        PartiallyConstructedSafepointRecord &Result,
                        std::vector<DeferredReplacement> &Replacements,
-                       const PointerToBaseTy &PointerToBase) {
+                       const PointerToBaseTy &PointerToBase, GCStrategy *GC) {
   const auto &LiveSet = Result.LiveSet;
 
   // 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(Call, BaseVec, LiveVec, Result, Replacements,
-                             PointerToBase);
+                             PointerToBase, GC);
 }
 
 // Helper function for the relocationViaAlloca.
 //
 // It receives iterator to the statepoint gc relocates and emits a store to the
 // assigned location (via allocaMap) for the each one of them.  It adds the
 // visited values into the visitedLiveValues set, which we will later use them
 // for validation checking.
static void insertUseHolderAfter(CallBase *Call, const ArrayRef<Value *> Values,
   Holders.push_back(CallInst::Create(
       Func, Values, "", &*II->getNormalDest()->getFirstInsertionPt()));
   Holders.push_back(CallInst::Create(
       Func, Values, "", &*II->getUnwindDest()->getFirstInsertionPt()));
 }
 
 static void findLiveReferences(
     Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate,
-    MutableArrayRef<struct PartiallyConstructedSafepointRecord> records) {
+    MutableArrayRef<struct PartiallyConstructedSafepointRecord> records,
+    GCStrategy *GC) {
   GCPtrLivenessData OriginalLivenessData;
-  computeLiveInValues(DT, F, OriginalLivenessData);
+  computeLiveInValues(DT, F, OriginalLivenessData, GC);
   for (size_t i = 0; i < records.size(); i++) {
     struct PartiallyConstructedSafepointRecord &info = records[i];
-    analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info);
+    analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info, GC);
   }
 }
 
 // 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
static bool inlineGetBaseAndOffset(Function &F,
 
   return Changed;
 }
 
 static bool insertParsePoints(Function &F, DominatorTree &DT,
                               TargetTransformInfo &TTI,
                               SmallVectorImpl<CallBase *> &ToUpdate,
                               DefiningValueMapTy &DVCache,
-                              IsKnownBaseMapTy &KnownBases) {
+                              IsKnownBaseMapTy &KnownBases, GCStrategy *GC) {
 #ifndef NDEBUG
   // Validate the input
   std::set<CallBase *> Uniqued;
   Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
   assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
 
   for (CallBase *Call : ToUpdate)
     assert(Call->getFunction() == &F);
#endif
   // Insert a dummy call with all of the deopt operands we'll need for the
   // actual safepoint insertion as arguments.  This ensures reference operands
   // in the deopt argument list are considered live through the safepoint (and
   // thus makes sure they get relocated.)
   for (CallBase *Call : ToUpdate) {
     SmallVector<Value *, 64> DeoptValues;
 
     for (Value *Arg : GetDeoptBundleOperands(Call)) {
-      assert(!isUnhandledGCPointerType(Arg->getType()) &&
+      assert(!isUnhandledGCPointerType(Arg->getType(), GC) &&
              "support for FCA unimplemented");
-      if (isHandledGCPointerType(Arg->getType()))
+      if (isHandledGCPointerType(Arg->getType(), GC))
         DeoptValues.push_back(Arg);
     }
 
     insertUseHolderAfter(Call, DeoptValues, Holders);
   }
 
   SmallVector<PartiallyConstructedSafepointRecord, 64> Records(ToUpdate.size());
 
   // A) Identify all gc pointers which are statically live at the given call
   // site.
-  findLiveReferences(F, DT, ToUpdate, Records);
+  findLiveReferences(F, DT, ToUpdate, Records, GC);
 
   /// Global mapping from live pointers to a base-defining-value.
   PointerToBaseTy PointerToBase;
 
   // 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, PointerToBase, KnownBases);
for (size_t i = 0; i < Records.size(); i++) {
     }
 
     insertUseHolderAfter(ToUpdate[i], Bases, Holders);
   }
 
   // By selecting base pointers, we've effectively inserted new uses. Thus, we
   // need to rerun liveness.  We may *also* have inserted new defs, but that's
   // not the key issue.
-  recomputeLiveInValues(F, DT, ToUpdate, Records, PointerToBase);
+  recomputeLiveInValues(F, DT, ToUpdate, Records, PointerToBase, GC);
 
   if (PrintBasePointers) {
     errs() << "Base Pairs: (w/Relocation)\n";
     for (auto Pair : PointerToBase) {
       errs() << " derived ";
       Pair.first->printAsOperand(errs(), false);
       errs() << " base ";
       Pair.second->printAsOperand(errs(), false);
#endif
   // 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,
-                           PointerToBase);
+                           PointerToBase, GC);
 
   ToUpdate.clear(); // prevent accident use of invalid calls.
 
   for (auto &PR : Replacements)
     PR.doReplacement();
 
   Replacements.clear();
 
#ifndef NDEBUG
     }
 #endif
   }
   unique_unsorted(Live);
 
 #ifndef NDEBUG
   // Validation check
   for (auto *Ptr : Live)
-    assert(isHandledGCPointerType(Ptr->getType()) &&
+    assert(isHandledGCPointerType(Ptr->getType(), GC) &&
            "must be a gc pointer type");
 #endif
 
   relocationViaAlloca(F, DT, Live, Records);
   return !Records.empty();
 }
 
 // List of all parameter and return attributes which must be stripped when
static void stripNonValidDataFromBody(Function &F) {
 
   // Delete the invariant.start instructions and RAUW undef.
   for (auto *II : InvariantStartInstructions) {
     II->replaceAllUsesWith(UndefValue::get(II->getType()));
     II->eraseFromParent();
   }
 }
 
+/// Looks up the GC strategy for a given function, returning null if the
+/// function doesn't have a GC tag. The strategy is stored in the cache.
+static GCStrategy *findGCStrategy(Function &F, GCStrategyCache &cache) {
+  if (!F.hasGC())
+    return nullptr;
+
+  if (cache.count(F.getGC()) == 0) {
+    cache[F.getGC()] = getGCStrategy(F.getGC());
+  }
+  return cache.at(F.getGC()).get();
+}
+
 /// Returns true if this function should be rewritten by this pass.  The main
 /// point of this function is as an extension point for custom logic.
-static bool shouldRewriteStatepointsIn(Function &F) {
-  // TODO: This should check the GCStrategy
-  if (F.hasGC()) {
-    const auto &FunctionGCName = F.getGC();
-    const StringRef StatepointExampleName("statepoint-example");
-    const StringRef CoreCLRName("coreclr");
-    return (StatepointExampleName == FunctionGCName) ||
-           (CoreCLRName == FunctionGCName);
-  } else
-    return false;
+static bool shouldRewriteStatepointsIn(Function &F, GCStrategy *Strategy) {
+  if (!F.hasGC())
+    return false;
+
+  assert(Strategy && "GC strategy is required by function, but was not found");
+  return Strategy->useStatepoints();
+}
+
+/// Find whether or not at least one function in a given module should be
+/// rewritten, as per the rewrite policy.
+static bool anyFunctionNeedsRewrite(Module &M, GCStrategyCache &strategies) {
+  for (Function &F : M) {
+    GCStrategy *GC = findGCStrategy(F, strategies);
+    if (shouldRewriteStatepointsIn(F, GC))
+      return true;
+  }
 }
 
-static void stripNonValidData(Module &M) {
+static void stripNonValidData(Module &M, GCStrategyCache &strategies) {
 #ifndef NDEBUG
-  assert(llvm::any_of(M, shouldRewriteStatepointsIn) && "precondition!");
+  assert(anyFunctionNeedsRewrite(M, strategies) && "precondition!");
 #endif
 
   for (Function &F : M)
     stripNonValidAttributesFromPrototype(F);
 
   for (Function &F : M)
     stripNonValidDataFromBody(F);
 }
 
 bool RewriteStatepointsForGC::runOnFunction(Function &F, DominatorTree &DT,
                                             TargetTransformInfo &TTI,
-                                            const TargetLibraryInfo &TLI) {
+                                            const TargetLibraryInfo &TLI,
+                                            GCStrategy *GC) {
   assert(!F.isDeclaration() && !F.empty() &&
          "need function body to rewrite statepoints in");
-  assert(shouldRewriteStatepointsIn(F) && "mismatch in rewrite decision");
+  assert(shouldRewriteStatepointsIn(F, GC) && "mismatch in rewrite decision");
 
   auto NeedsRewrite = [&TLI](Instruction &I) {
     if (const auto *Call = dyn_cast<CallBase>(&I)) {
       if (isa<GCStatepointInst>(Call))
         return false;
       if (callsGCLeafFunction(Call, TLI))
         return false;
 
bool RewriteStatepointsForGC::runOnFunction(Function &F, DominatorTree &DT,
   IsKnownBaseMapTy KnownBases;
 
   if (!Intrinsics.empty())
     // Inline @gc.get.pointer.base() and @gc.get.pointer.offset() before finding
     // live references.
     MadeChange |= inlineGetBaseAndOffset(F, Intrinsics, DVCache, KnownBases);
 
   if (!ParsePointNeeded.empty())
-    MadeChange |=
-        insertParsePoints(F, DT, TTI, ParsePointNeeded, DVCache, KnownBases);
+    MadeChange |= insertParsePoints(F, DT, TTI, ParsePointNeeded, DVCache,
+                                    KnownBases, GC);
 
   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.
 
 /// 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 *> &LiveTmp, GCStrategy *GC) {
   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()) {
-      assert(!isUnhandledGCPointerType(V->getType()) &&
+      assert(!isUnhandledGCPointerType(V->getType(), GC) &&
              "support for FCA unimplemented");
-      if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V)) {
+      if (isHandledGCPointerType(V->getType(), GC) && !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)
         LiveTmp.insert(V);
       }
     }
   }
 }
 
-static void computeLiveOutSeed(BasicBlock *BB, SetVector<Value *> &LiveTmp) {
+static void computeLiveOutSeed(BasicBlock *BB, SetVector<Value *> &LiveTmp,
+                               GCStrategy *GC) {
   for (BasicBlock *Succ : successors(BB)) {
     for (auto &I : *Succ) {
       PHINode *PN = dyn_cast<PHINode>(&I);
       if (!PN)
         break;
 
       Value *V = PN->getIncomingValueForBlock(BB);
-      assert(!isUnhandledGCPointerType(V->getType()) &&
+      assert(!isUnhandledGCPointerType(V->getType(), GC) &&
              "support for FCA unimplemented");
-      if (isHandledGCPointerType(V->getType()) && !isa<Constant>(V))
+      if (isHandledGCPointerType(V->getType(), GC) && !isa<Constant>(V))
         LiveTmp.insert(V);
     }
   }
 }
 
-static SetVector<Value *> computeKillSet(BasicBlock *BB) {
+static SetVector<Value *> computeKillSet(BasicBlock *BB, GCStrategy *GC) {
   SetVector<Value *> KillSet;
   for (Instruction &I : *BB)
-    if (isHandledGCPointerType(I.getType()))
+    if (isHandledGCPointerType(I.getType(), GC))
       KillSet.insert(&I);
   return KillSet;
 }
 
 #ifndef NDEBUG
 /// Check that the items in 'Live' dominate 'TI'.  This is used as a basic
 /// validation check for the liveness computation.
 static void checkBasicSSA(DominatorTree &DT, SetVector<Value *> &Live,
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
 
 static void computeLiveInValues(DominatorTree &DT, Function &F,
-                                GCPtrLivenessData &Data) {
+                                GCPtrLivenessData &Data, GCStrategy *GC) {
   SmallSetVector<BasicBlock *, 32> Worklist;
 
   // Seed the liveness for each individual block
   for (BasicBlock &BB : F) {
-    Data.KillSet[&BB] = computeKillSet(&BB);
+    Data.KillSet[&BB] = computeKillSet(&BB, GC);
     Data.LiveSet[&BB].clear();
-    computeLiveInValues(BB.rbegin(), BB.rend(), Data.LiveSet[&BB]);
+    computeLiveInValues(BB.rbegin(), BB.rend(), Data.LiveSet[&BB], GC);
 
 #ifndef NDEBUG
     for (Value *Kill : Data.KillSet[&BB])
       assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill");
 #endif
 
     Data.LiveOut[&BB] = SetVector<Value *>();
-    computeLiveOutSeed(&BB, Data.LiveOut[&BB]);
+    computeLiveOutSeed(&BB, Data.LiveOut[&BB], GC);
     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 that liveness until stable
#ifndef NDEBUG
   // Verify 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,
-                              StatepointLiveSetTy &Out) {
+                              StatepointLiveSetTy &Out, GCStrategy *GC) {
   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);
+  computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(), LiveOut,
+                      GC);
   LiveOut.remove(Inst);
   Out.insert(LiveOut.begin(), LiveOut.end());
 }
 
 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
                                   CallBase *Call,
                                   PartiallyConstructedSafepointRecord &Info,
-                                  PointerToBaseTy &PointerToBase) {
+                                  PointerToBaseTy &PointerToBase,
+                                  GCStrategy *GC) {
   StatepointLiveSetTy Updated;
-  findLiveSetAtInst(Call, RevisedLivenessData, Updated);
+  findLiveSetAtInst(Call, RevisedLivenessData, Updated, GC);
 
   // We may have base pointers which are now live that weren't before.  We need
   // to update the PointerToBase structure to reflect this.
   for (auto *V : Updated)
     PointerToBase.insert({ V, V });
 
   Info.LiveSet = Updated;
 }