Introduce an example statepoint GC strategy

[reames]

Summary

This change includes the most basic possible GCStrategy for a GC which is using the statepoint lowering code. At the moment, this GCStrategy doesn't really do much - aside from actually generate correct stackmaps that is - but I went ahead and added a few extra correctness checks as proof of concept. It's mostly here to provide documentation on how to do one, and to provide a point for various optimization legality hooks I'd like to add going forward. (For context, see the TODOs in InstCombine around gc.relocate.)

Note that I am deliberately not making a GCStrategy required to use gc.statepoints with this change. I want to give folks out of tree - including myself - a chance to migrate. In a week or two, I'll make having a GCStrategy be required for gc.statepoints. To this end, I added the gc tag to one of the test cases but not others.

[whitequark]

LGTM

[reames]

Previous diff did not include added file.

[majnemer]

include/llvm/CodeGen/GCStrategy.h

71–73

The other comments are formatted using ///<

Also, the layout of GCStrategy might be a little more compact if you shifted this field down.

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

429

There should be a space between the for and the (

lib/CodeGen/StatepointExampleGC.cpp

30

Space before and after =

40–41

If this is the case, why not just cast<PointerType> ?

45

Address space 1 has a special meaning in LLVM, it's identical to address space 0 except for the fact that "null" may be dereferenced. You might want to consider a different address space.

[reames]

Will update with revisions.

include/llvm/CodeGen/GCStrategy.h

71–73

FYI, I'm going to be doing a fair amount of style/spacing cleanup once I'm done with the current round of changes. Ordering fields, updating doxygen comments, and the like will happen then.

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

429

Thanks. Will fix this and other style comments.

lib/CodeGen/StatepointExampleGC.cpp

45

Er, where are you getting that from? All I see in the LangRef is that non-zero address spaces are target defined.

(p.s. I'm planning on raising this question separately on the mailing list at some point. Changing it shouldn't matter much.)

[reames]

Responding to comments.

David, Peter - Since the patch was accidentally incomplete as of the last LGTM, can one of you confirm you're happy with the current form of patch?

[artagnon]

lib/CodeGen/StatepointExampleGC.cpp

1

Perhaps rename this to StatepointGC, to look like ErlangGC and OCamlGC?
Also, you need a llvm::linkStatepointGC() { } for anyone to use it. Please see "introduce link_gc_components" for an example of the work going in this direction.

[reames]

lib/CodeGen/StatepointExampleGC.cpp

1

It looks like I do need to update the file comment to the new name.

I would strongly prefer to keep the current name. This is *specifically* an example. It is not tied to any external GC. The Ocaml and Erlang ones have external dependences.

As for your second point, see line 53 in this file.

[whitequark]

@reames, I don't know about Erlang (HiPE might actually use it), but the OCaml GC is currently just an example as well. It is not practically useful even for a hypothetical OCaml LLVM frontend.

[reames]

I will rename/document that about the Ocaml GC strategy. I filled a bug
to track that here:
http://llvm.org/bugs/show_bug.cgi?id=22098

Philip

[reames]

ping

[majnemer]

LGTM.

[whitequark]

I see you've left addrspace(1) in--is that intentional?

[reames]

In D6808#105885, @whitequark wrote:

I see you've left addrspace(1) in--is that intentional?

Yes. So far, no one has clarified what addrspace(1) is used for. Given I'd need to update other tests, I'll do that in one change once the documentation is in place.

[whitequark]

OK--LGTM from me if you still need it.

include/llvm/CodeGen/GCStrategy.h

 // 
 // The read and write barrier support can be used with either implementation.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GCSTRATEGY_H
 #define LLVM_CODEGEN_GCSTRATEGY_H
 
+#include "llvm/ADT/Optional.h"
 #include "llvm/CodeGen/GCMetadata.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/Support/Registry.h"
 #include <string>
 
 namespace llvm {
   /// GCStrategy describes a garbage collector algorithm's code generation
   /// requirements, and provides overridable hooks for those needs which cannot
   /// be abstractly described.  GCStrategy objects currently must be looked up
   /// through the GCModuleInfo analysis pass.  They are owned by the analysis
   /// pass and recreated every time that pass is invalidated.
   class GCStrategy {
   private:
     std::string Name;
     friend class GCModuleInfo;
     
   protected:
+    bool UseStatepoints;       /// Uses gc.statepoints as opposed to gc.roots,
+                               /// if set, none of the other options can be
+                               /// anything but their default values.
+
     unsigned NeededSafePoints; ///< Bitmask of required safe points.
     bool CustomReadBarriers;   ///< Default is to insert loads.
     bool CustomWriteBarriers;  ///< Default is to insert stores.
     bool CustomRoots;          ///< Default is to pass through to backend.
     bool CustomSafePoints;     ///< Default is to use NeededSafePoints
                                ///< to find safe points.
     bool InitRoots;            ///< If set, roots are nulled during lowering.
     bool UsesMetadata;         ///< If set, backend must emit metadata tables.
public:
     /// them. 
     bool customWriteBarrier() const { return CustomWriteBarriers; }
     
     /// By default, read barriers are replaced with simple load
     /// instructions. If true, then performCustomLowering must instead lower
     /// them. 
     bool customReadBarrier() const { return CustomReadBarriers; }
 
+    /// Returns true if this strategy is expecting the use of gc.statepoints,
+    /// and false otherwise.
+    bool useStatepoints() const { return UseStatepoints; }
+
+    /** @name Statepoint Specific Properties */
+    ///@{
+
+    /// If the value 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 'None' (i.e. an
+    /// empty optional indicating it can't reliably distinguish.   
+    virtual Optional<bool> isGCManagedPointer(const Value *V) const {
+      return None;
+    }
+    ///@}
+
     /** @name GCRoot Specific Properties
      * These properties and overrides only apply to collector strategies using
      * GCRoot. 
      */
     ///@{
 
     /// True if safe points of any kind are required. By default, none are
     /// recorded. 
public:
     bool customSafePoints() const { return CustomSafePoints; }
     
     /// If set, gcroot intrinsics should initialize their allocas to null
     /// before the first use. This is necessary for most GCs and is enabled by
     /// default. 
     bool initializeRoots() const { return InitRoots; }
     
     /// If set, appropriate metadata tables must be emitted by the back-end
-    /// (assembler, JIT, or otherwise). 
+    /// (assembler, JIT, or otherwise). For statepoint, this method is
+    /// currently unsupported.  The stackmap information can be found in the
+    /// StackMap section as described in the documentation.
     bool usesMetadata() const { return UsesMetadata; }
 
     ///@}
     
     /// initializeCustomLowering/performCustomLowering - If any of the actions
     /// are set to custom, performCustomLowering must be overriden to transform
     /// the corresponding actions to LLVM IR. initializeCustomLowering is
     /// optional to override. These are the only GCStrategy methods through

include/llvm/CodeGen/GCs.h

namespace llvm {
   void linkErlangGC();
 
   /// Creates an erlang-compatible metadata printer.
   void linkErlangGCPrinter();
 
   /// Creates a shadow stack garbage collector. This collector requires no code
   /// generator support.
   void linkShadowStackGC();
+
+  void linkStatepointExampleGC();
 }
 
 #endif

include/llvm/CodeGen/LinkAllCodegenComponents.h

ForceCodegenLinking() {
       (void) llvm::createFastRegisterAllocator();
       (void) llvm::createBasicRegisterAllocator();
       (void) llvm::createGreedyRegisterAllocator();
       (void) llvm::createDefaultPBQPRegisterAllocator();
 
       llvm::linkOcamlGC();
       llvm::linkErlangGC();
       llvm::linkShadowStackGC();
+      llvm::linkStatepointExampleGC();
 
       (void) llvm::createBURRListDAGScheduler(nullptr,
                                               llvm::CodeGenOpt::Default);
       (void) llvm::createSourceListDAGScheduler(nullptr,
                                                 llvm::CodeGenOpt::Default);
       (void) llvm::createHybridListDAGScheduler(nullptr,
                                                 llvm::CodeGenOpt::Default);
       (void) llvm::createFastDAGScheduler(nullptr, llvm::CodeGenOpt::Default);
       (void) llvm::createDefaultScheduler(nullptr, llvm::CodeGenOpt::Default);
       (void) llvm::createVLIWDAGScheduler(nullptr, llvm::CodeGenOpt::Default);
 
     }
   } ForceCodegenLinking; // Force link by creating a global definition.
 }
 
 #endif

lib/CodeGen/AsmPrinter/AsmPrinter.cpp

 }
 
 
 
 GCMetadataPrinter *AsmPrinter::GetOrCreateGCPrinter(GCStrategy &S) {
   if (!S.usesMetadata())
     return nullptr;
 
+  assert(!S.useStatepoints() && "statepoints do not currently support custom"
+         " stackmap formats, please see the documentation for a description of"
+         " the default format.  If you really need a custom serialized format,"
+         " please file a bug");
+
   gcp_map_type &GCMap = getGCMap(GCMetadataPrinters);
   gcp_map_type::iterator GCPI = GCMap.find(&S);
   if (GCPI != GCMap.end())
     return GCPI->second.get();
 
   const char *Name = S.getName().c_str();
 
   for (GCMetadataPrinterRegistry::iterator

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   SlotIndexes.cpp
   SpillPlacement.cpp
   SplitKit.cpp
   StackColoring.cpp
   StackProtector.cpp
   StackSlotColoring.cpp
   StackMapLivenessAnalysis.cpp
   StackMaps.cpp
+  StatepointExampleGC.cpp
   TailDuplication.cpp
   TargetFrameLoweringImpl.cpp
   TargetInstrInfo.cpp
   TargetLoweringBase.cpp
   TargetLoweringObjectFileImpl.cpp
   TargetOptionsImpl.cpp
   TargetRegisterInfo.cpp
   TargetSchedule.cpp

lib/CodeGen/GCStrategy.cpp

public:
     bool runOnMachineFunction(MachineFunction &MF) override;
   };
 
 }
 
 // -----------------------------------------------------------------------------
 
 GCStrategy::GCStrategy() :
+  UseStatepoints(false),
   NeededSafePoints(0),
   CustomReadBarriers(false),
   CustomWriteBarriers(false),
   CustomRoots(false),
   CustomSafePoints(false),
   InitRoots(true),
   UsesMetadata(false)
 {}

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "StatepointLowering.h"
 #include "SelectionDAGBuilder.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/FunctionLoweringInfo.h"
+#include "llvm/CodeGen/GCStrategy.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/StackMaps.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Statepoint.h"
 #include "llvm/Target/TargetLowering.h"
static void lowerStatepointMetaArgs(SmallVectorImpl<SDValue> &Ops,
 
   // Lower the deopt and gc arguments for this statepoint.  Layout will
   // be: deopt argument length, deopt arguments.., gc arguments...
 
   SmallVector<const Value *, 64> Bases, Ptrs, Relocations;
   getIncomingStatepointGCValues(Bases, Ptrs, Relocations,
                                 Statepoint.getCallSite(), Builder);
 
+#ifndef NDEBUG
+  // Check that each of the gc pointer and bases we've gotten out of the
+  // safepoint is something the strategy thinks might be a pointer into the GC
+  // heap.  This is basically just here to help catch errors during statepoint
+  // insertion. TODO: This should actually be in the Verifier, but we can't get
+  // to the GCStrategy from there (yet).
+  if (Builder.GFI) {
+    GCStrategy &S = Builder.GFI->getStrategy();
+    for (const Value *V : Bases) {
+      auto Opt = S.isGCManagedPointer(V);
+      if (Opt.hasValue()) {
+        assert(Opt.getValue() &&
+               "non gc managed base pointer found in statepoint");
+      }
+    }
+    for (const Value *V : Ptrs) {
+      auto Opt = S.isGCManagedPointer(V);
+      if (Opt.hasValue()) {
+        assert(Opt.getValue() &&
+               "non gc managed derived pointer found in statepoint");
+      }
+    }
+    for (const Value *V : Relocations) {
+      auto Opt = S.isGCManagedPointer(V);
+      if (Opt.hasValue()) {
+        assert(Opt.getValue() && "non gc managed pointer relocated");
+      }
+    }
+  }
+#endif
+
+
+
   // Before we actually start lowering (and allocating spill slots for values),
   // reserve any stack slots which we judge to be profitable to reuse for a
   // particular value.  This is purely an optimization over the code below and
   // doesn't change semantics at all.  It is important for performance that we
   // reserve slots for both deopt and gc values before lowering either.
   for (auto I = Statepoint.vm_state_begin() + 1, E = Statepoint.vm_state_end();
        I != E; ++I) {
     Value *V = *I;

 #endif
 
   ImmutableStatepoint ISP(&CI);
 #ifndef NDEBUG
   // If this is a malformed statepoint, report it early to simplify debugging.
   // This should catch any IR level mistake that's made when constructing or
   // transforming statepoints.
   ISP.verify();
+
+  // Check that the associated GCStrategy expects to encounter statepoints.
+  // TODO: This if should become an assert.  For now, we allow the GCStrategy
+  // to be optional for backwards compatibility.  This will only last a short
+  // period (i.e. a couple of weeks).
+  if (GFI) {
+    assert(GFI->getStrategy().useStatepoints() &&
+           "GCStrategy does not expect to encounter statepoints");
+  }
 #endif
 
 
   // Lower statepoint vmstate and gcstate arguments
   SmallVector<SDValue, 10> LoweredArgs;
   lowerStatepointMetaArgs(LoweredArgs, ISP, *this);
 
   // Get call node, we will replace it later with statepoint

lib/CodeGen/StatepointExampleGC.cpp

+//===-- StatepointDefaultGC.cpp - The default statepoint GC strategy ------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains a GCStrategy which serves as an example for the usage
+// of a statepoint based lowering strategy.  This GCStrategy is intended to
+// suitable as a default 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.  
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/GCStrategy.h"
+#include "llvm/IR/Value.h"
+#include "llvm/IR/DerivedTypes.h"
+
+using namespace llvm;
+
+namespace {
+class StatepointGC : public GCStrategy {
+public:
+  StatepointGC() {
+    UseStatepoints = true;
+    // These options are all gc.root specific, we specify them so that the
+    // gc.root lowering code doesn't run.
+    InitRoots = false;
+    NeededSafePoints = 0;
+    UsesMetadata = false;
+    CustomRoots = false;
+    CustomSafePoints = false;
+  }
+  Optional<bool> isGCManagedPointer(const Value *V) const override {
+    // Method is only valid on pointer typed values.
+    PointerType *PT = cast<PointerType>(V->getType());
+    // 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 (1 == PT->getAddressSpace());
+  }
+};
+}
+
+static GCRegistry::Add<StatepointGC>
+X("statepoint-example", "an example strategy for statepoint");
+
+namespace llvm {
+void linkStatepointExampleGC() {}
+}

test/CodeGen/X86/statepoint-forward.ll

 
 ; If not at a statepoint, we could forward known memory values
 ; across this call.
 declare void @func() readonly
 
 ;; Forwarding the value of a pointer load is invalid since it may have
 ;; changed at the safepoint.  Forwarding a non-gc pointer value would 
 ;; be valid, but is not currently implemented.
-define i1 @test_load_forward(i32 addrspace(1)* addrspace(1)* %p) {
+define i1 @test_load_forward(i32 addrspace(1)* addrspace(1)* %p) gc "statepoint-example" {
 entry:
   %before = load i32 addrspace(1)* addrspace(1)* %p
   %cmp1 = call i1 @f(i32 addrspace(1)* %before)
   call void @llvm.assume(i1 %cmp1)
   %safepoint_token = tail call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @func, i32 0, i32 0, i32 0, i32 addrspace(1)* addrspace(1)* %p)
   %pnew = call i32 addrspace(1)* addrspace(1)* @llvm.experimental.gc.relocate.p1p1i32(i32 %safepoint_token, i32 4, i32 4)
   %after = load i32 addrspace(1)* addrspace(1)* %pnew
   %cmp2 = call i1 @f(i32 addrspace(1)* %after)
   ret i1 %cmp2
 
 ; CHECK-OPT-LABEL: test_load_forward
 ; CHECK-OPT: ret i1 %cmp2
 ; CHECK-LLC-LABEL: test_load_forward
 ; CHECK-LLC: callq f
 }
 
 ;; Same as above, but forwarding from a store
 define i1 @test_store_forward(i32 addrspace(1)* addrspace(1)* %p,
-                              i32 addrspace(1)* %v) {
+                              i32 addrspace(1)* %v) gc "statepoint-example" {
 entry:
   %cmp1 = call i1 @f(i32 addrspace(1)* %v)
   call void @llvm.assume(i1 %cmp1)
   store i32 addrspace(1)* %v, i32 addrspace(1)* addrspace(1)* %p
   %safepoint_token = tail call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @func, i32 0, i32 0, i32 0, i32 addrspace(1)* addrspace(1)* %p)
   %pnew = call i32 addrspace(1)* addrspace(1)* @llvm.experimental.gc.relocate.p1p1i32(i32 %safepoint_token, i32 4, i32 4)
   %after = load i32 addrspace(1)* addrspace(1)* %pnew
   %cmp2 = call i1 @f(i32 addrspace(1)* %after)

 ; of the pointer and is thus not safe to reuse after a statepoint.
 declare i1 @f(i32 addrspace(1)* %v) readnone
 
 ; This is a variant of the test_load_forward test which is intended to 
 ; highlight the fact that a gc pointer can be stored in part of the heap
 ; that is not itself GC managed.  The GC may have an external mechanism
 ; to know about and update that value at a safepoint.  Note that the 
 ; statepoint does not provide the collector with this root.
-define i1 @test_load_forward_nongc_heap(i32 addrspace(1)** %p) {
+define i1 @test_load_forward_nongc_heap(i32 addrspace(1)** %p) gc "statepoint-example" {
 entry:
   %before = load i32 addrspace(1)** %p
   %cmp1 = call i1 @f(i32 addrspace(1)* %before)
   call void @llvm.assume(i1 %cmp1)
   call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @func, i32 0, i32 0, i32 0)
   %after = load i32 addrspace(1)** %p
   %cmp2 = call i1 @f(i32 addrspace(1)* %after)
   ret i1 %cmp2
 
 ; CHECK-OPT-LABEL: test_load_forward_nongc_heap
 ; CHECK-OPT: ret i1 %cmp2
 ; CHECK-LLC-LABEL: test_load_forward_nongc_heap
 ; CHECK-LLC: callq f
 }
 
 ;; Same as above, but forwarding from a store
 define i1 @test_store_forward_nongc_heap(i32 addrspace(1)** %p,
-                                         i32 addrspace(1)* %v) {
+                                         i32 addrspace(1)* %v) gc "statepoint-example" {
 entry:
   %cmp1 = call i1 @f(i32 addrspace(1)* %v)
   call void @llvm.assume(i1 %cmp1)
   store i32 addrspace(1)* %v, i32 addrspace(1)** %p
   call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @func, i32 0, i32 0, i32 0)
   %after = load i32 addrspace(1)** %p
   %cmp2 = call i1 @f(i32 addrspace(1)* %after)
   ret i1 %cmp2
 
 ; CHECK-OPT-LABEL: test_store_forward_nongc_heap
 ; CHECK-OPT: ret i1 %cmp2
 ; CHECK-LLC-LABEL: test_store_forward_nongc_heap
 ; CHECK-LLC: callq f
 }
 
-
 declare void @llvm.assume(i1)
 declare i32 @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()*, i32, i32, ...)
 declare i32 addrspace(1)* addrspace(1)* @llvm.experimental.gc.relocate.p1p1i32(i32, i32, i32) #3