[RS4GC] Remove the hardcoded GC strategy names (v2)

[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.

This is an updated version of D140458, rebased to account for LLVM's
changes since D140504 (required by this patch) landed.

Please note I don't have commit access, so if approved I'd need someone else to land it.

[zero9178]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

116

Use of std::map is generally discouraged unless you require any of its properties.
As far as I can tell you're just doing pure insert and lookups on it, so you'll probably want to use StringMap from LLVM.

3046

You are doing 3 lookups in the map here, which can be reduced to just one.
The trick is to use insert({F.getGC(), nullptr}), which will return an iterator and bool as pairs. The iterator will either point to an existing entry if it was NOT inserted, or to the now inserted entry. The bool is true if inserted.
That way you just need to check if it was inserted, if it was, assign to second of the entry the result of getGCStrategy.
At the end also just return second of the iterator pointing to the entry.

[dantrushin]

BTW, there is no need to create new revision to reflect trunk changes. You could simply rebase your local branch and then update diffs for the existing review. This works well and is common practice.

As for review itself.
First, I don't think that GCStrategy cache really belongs here. If I want to use GCStrategy say, in Verifier or in other Transform passes, should I add yet another GCStrategy cache everywhere? I don't think so.
The question is where to implement it. There was an attempt to move it to LLVMContext (see D6811), but it was reverted later (commit 56a03938f7a536dc2cef3c42ed67b3f218a1c758).
As hinted in mentioned commit we can create an IR analysis pass for that (which would duplicate CodeGen's GCModuleInfo to some extent, but I think we can live with that).
There even was arguing if GCStrategy are singletons or not (see discussions in D100559). @reames thinks they are and I'm leaning to agree with him. But if they don't then bare llvm::getGCStrategy() would suffice.

Second, a bunch of static functions with long parameter lists start looking ridiculously. Local class which keeps per-function state would look cleaner IMHO, but that can be done separately from this change.

llvm/docs/Statepoints.rst

581–582

This is not true anymore ('The pass assumes that all addrspace(1) pointers are non-integral pointer types')? Perhaps simply delete this sentence?

585

This seems to repeat what was said in first sentence of paragraph.

But English is not my native language, so I'd leave review of this to native speakers.

[dantrushin]

Added couple folks who should be interested in this stuff :-)

[znix]

I'll work on making a GCStrategyAnalysisPass then. Given RS4GC supports both the new and legacy pass manager, I assume this new pass needs to support both, too?

With regards to moving all the static RS4GC functions to a class, should I make that a separate diff, a separate commit within the diff, or something similar? I ask because there will be a lot of mostly-whitespace changes as all the function arguments are indented, which would make the patch quite long.

Apologies for this very basic question, but how do I update a patch using Arcanist? I had a look on the docs page about Phabricator reviews, and it didn't mention how to do them.

Thanks,
Campbell

[dantrushin]

In D141110#4048764, @znix wrote:

I'll work on making a GCStrategyAnalysisPass then. Given RS4GC supports both the new and legacy pass manager, I assume this new pass needs to support both, too?

I think yes. Even though Legacy PM is deprecated, supporting it is just several extra lines.

With regards to moving all the static RS4GC functions to a class, should I make that a separate diff, a separate commit within the diff, or something similar? I ask because there will be a lot of mostly-whitespace changes as all the function arguments are indented, which would make the patch quite long.

This usually done as a separate NFC (non-functional change) patch.
Note that such change is not a blocker for this review - we can do it later.

Apologies for this very basic question, but how do I update a patch using Arcanist? I had a look on the docs page about Phabricator reviews, and it didn't mention how to do them.

Simply do arc diff again. As long as your commit message has Differential Revision line, arcanist is smart enough to update existing review instead of creating new one.

[reames]

Please don't couple all uses of statepoints to RS4GC. Adding another function to GCStrategy should be straight forward, please do it.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

3042

I'm confused by your implementation here. getGCStrategy uses the register of GCStrategy objects internally. If calling that works, why do you need another caching layer here at all?

As a bit of history, the GC registery was initially in CodeGen and not available in the rest of LLVM due to some weird linkage problems. I think - though I don't quite remember details, so check - that got fixed years ago.

[dantrushin]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

3042

@reames: llvm::getGCStrategy() calls GCStrategy::instantiate() for every query (creating new instance).
CodeGen's GCModuleInfo::getGCStrategy() implements GC strategy cache on top of that. I guess, in attempt to have them as singletons (?).
Do you think we don't need it in IR?
I also found your previous attempt to move ownership of GCStrategies to LLVM Context which was reverted and you mentioned that it
makes sense to have them in Immutable Analysis pass. Was its only purpose solve that linkage problem?
If yes, we can drop this GCStrategy cache completely and call llvm::getGCStrategy()directly.

BTW, that linkage problem was fixed recently by Campbell.

[dantrushin]

@znix : I suggest you to remove GCStrategy cache from this patch (and use llvm::getGCStrategy() instead where necessary). I think it will unblock review.
We can figure out caching later/separately.

[znix]

Get rid of the strategy cache

[znix]

Rephrase the Statepoint documentation to properly reflect this patch's changes.

[znix]

Make individual GCStrategies op-in to RS4GC support.

[dantrushin]

Please make a separate NFC review with GCStrategy changes. Besides being common llvm review practice it will allow downstream projects to handle this API change without breakage.
With separate reviews/commit we will have time to update our downstream strategies before RS4GC starts using new API.
If they come in single commit, it will immediately break all existing RS4GC users.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

147

I think getting GCStrategy from function should be moved inside this function. See comments below

153

Same here. Move it inside and you don't need change header file

189

Ditto

335–337

You can use optional::value_or here:

return GC->isGCManagerPointer(T).value_or(true);

3055

Returning false and then asserting looks confusing, this will raise questions like what Strategy really is; is it different from F.getGC; etc.
I think it would be much mo readable to get GCStrategy from function right here and use it.

3061

Moving this assert to GCStrategy::useRS4GC() looks more logical to me.

3072

You won't need this if you move getting GCStrategy inside shouldRewriteStatepointsIn()

[znix]

• Split the GCStrategy::UseRS4GC into a separate diff
• Reword some changes to Statepoints.rst and mention UseRS4GC in them
• Don't pass the GCStrategy into shouldRewriteStatepointsIn or runOnFunction
• Use optional::value_or in isGCPointerType

[dantrushin]

LGTM.
I'll wait for a few days before landing it to let other reviewers speak up.

llvm/docs/Statepoints.rst

558–559

pass, not patch?

llvm/docs/Statepoints.rst

 RewriteStatepointsForGC
 ^^^^^^^^^^^^^^^^^^^^^^^^
 
 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.
+non references.  This is controlled via GCStrategy::isGCManagedPointer. The
+``statepoint-example`` and ``coreclr`` strategies (the only two default
+strategies that support statepoints) both use addrspace(1) to determine which
+pointers are references, 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/IR/GCStrategy.h

 class GCStrategy {
 private:
   friend class GCModuleInfo;
 
   std::string Name;
 
 protected:
   bool UseStatepoints = false; /// Uses gc.statepoints as opposed to gc.roots,
-                               /// if set, none of the other options can be
-                               /// anything but their default values.
+                               /// if set, NeededSafePoints and UsesMetadata
+                               /// should be left at their default values.
+
+  bool UseRS4GC = false; /// If UseStatepoints is set, this determines whether
+                         /// the RewriteStatepointsForGC pass should rewrite
+                         /// this function's calls.
+                         /// This should only be set if UseStatepoints is set.
 
   bool NeededSafePoints = false;    ///< if set, calls are inferred to be safepoints
   bool UsesMetadata = false;     ///< If set, backend must emit metadata tables.
 
 public:
   GCStrategy();
   virtual ~GCStrategy() = default;
 
public:
 
   /// If the type specified can be reliably distinguished, returns true for
   /// pointers to GC managed locations and false for pointers to non-GC
   /// managed locations.  Note a GCStrategy can always return 'std::nullopt'
   /// (i.e. an empty optional indicating it can't reliably distinguish.
   virtual std::optional<bool> isGCManagedPointer(const Type *Ty) const {
     return std::nullopt;
   }
+
+  /// Returns true if the RewriteStatepointsForGC pass should run on functions
+  /// using this GC.
+  bool useRS4GC() const { return UseRS4GC; }
+
   ///@}
 
   /// If set, appropriate metadata tables must be emitted by the back-end
   /// (assembler, JIT, or otherwise). The default stackmap information can be
   /// found in the StackMap section as described in the documentation.
   bool usesMetadata() const { return UsesMetadata; }
 
   /** @name GCRoot Specific Properties

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/IR/BuiltinGCs.cpp

 /// implementation usable with any collector which can consume the standard
 /// stackmap format generated by statepoints, uses the default addrespace to
 /// distinguish between gc managed and non-gc managed pointers, and has
 /// reasonable relocation semantics.
 class StatepointGC : public GCStrategy {
 public:
   StatepointGC() {
     UseStatepoints = true;
+    UseRS4GC = true;
     // These options are all gc.root specific, we specify them so that the
     // gc.root lowering code doesn't run.
     NeededSafePoints = false;
     UsesMetadata = false;
   }
 
   std::optional<bool> isGCManagedPointer(const Type *Ty) const override {
     // Method is only valid on pointer typed values.

 ///    edges and before tail-calls (not needed at function-entry)
 ///
 /// The above differences in behavior are to be implemented in upcoming
 /// checkins.
 class CoreCLRGC : public GCStrategy {
 public:
   CoreCLRGC() {
     UseStatepoints = true;
+    UseRS4GC = true;
     // These options are all gc.root specific, we specify them so that the
     // gc.root lowering code doesn't run.
     NeededSafePoints = false;
     UsesMetadata = false;
   }
 
   std::optional<bool> isGCManagedPointer(const Type *Ty) const override {
     // Method is only valid on pointer typed values.

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"

 
 static cl::opt<bool>
     AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info",
                                    cl::Hidden, cl::init(true));
 
 static cl::opt<bool> RematDerivedAtUses("rs4gc-remat-derived-at-uses",
                                         cl::Hidden, cl::init(true));
 
 /// 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 bool shouldRewriteStatepointsIn(Function &F);
+// Find the GC strategy for a function, or null if it doesn't have one.
+static std::unique_ptr<GCStrategy> findGCStrategy(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();
   for (Function &F : M) {
     // Nothing to do for declarations.
     if (F.isDeclaration() || F.empty())
       continue;
 
+    std::unique_ptr<GCStrategy> GC = findGCStrategy(F);
+
     // 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.get()))
       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.get());
   }
   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);
public:
 
   bool runOnModule(Module &M) override {
     bool Changed = false;
     for (Function &F : M) {
       // Nothing to do for declarations.
       if (F.isDeclaration() || F.empty())
         continue;
 
+      std::unique_ptr<GCStrategy> GC = findGCStrategy(F);
+
       // 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.get()))
         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.get());
     }
 
     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.
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 std::unique_ptr<GCStrategy> findGCStrategy(Function &F) {
+  if (!F.hasGC())
+    return nullptr;
+
+  return getGCStrategy(F.getGC());
+}
+
 /// 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");
+
+  if (!Strategy->useRS4GC())
+    return false;
+
+  assert(Strategy->useStatepoints() &&
+         "GC strategy has useRS4GC but not useStatepoints set");
+  return true;
+}
+
+/// 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) {
+  for (Function &F : M) {
+    std::unique_ptr<GCStrategy> GC = findGCStrategy(F);
+    if (shouldRewriteStatepointsIn(F, GC.get()))
+      return true;
+  }
 }
 
 static void stripNonValidData(Module &M) {
 #ifndef NDEBUG
-  assert(llvm::any_of(M, shouldRewriteStatepointsIn) && "precondition!");
+  assert(anyFunctionNeedsRewrite(M) && "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;
 }