CbC/CbC_llvm: docs/Statepoints.rst comparison

comparison docs/Statepoints.rst @ 122:36195a0db682

merging ( incomplete )

author	Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date	Fri, 17 Nov 2017 20:32:31 +0900
parents	803732b1fca8
children	c2174574ed3a

comparison

equal deleted inserted replaced

-:d9df2cbd60cd
+:36195a0db682
 :depth: 2
 Status
 =======
-This document describes a set of experimental extensions to LLVM. Use
+This document describes a set of extensions to LLVM to support garbage
-with caution.  Because the intrinsics have experimental status,
+collection.  By now, these mechanisms are well proven with commercial java
-compatibility across LLVM releases is not guaranteed.
+implementation with a fully relocating collector having shipped using them.
+There are a couple places where bugs might still linger; these are called out
-LLVM currently supports an alternate mechanism for conservative
+below.
-garbage collection support using the ``gcroot`` intrinsic.  The mechanism
-described here shares little in common with the alternate ``gcroot``
+They are still listed as "experimental" to indicate that no forward or backward
-implementation and it is hoped that this mechanism will eventually
+compatibility guarantees are offered across versions.  If your use case is such
-replace the gc_root mechanism.
+that you need some form of forward compatibility guarantee, please raise the
+issue on the llvm-dev mailing list.
+LLVM still supports an alternate mechanism for conservative garbage collection
+support using the ``gcroot`` intrinsic.  The ``gcroot`` mechanism is mostly of
+historical interest at this point with one exception - its implementation of
+shadow stacks has been used successfully by a number of language frontends and
+is still supported.
 Overview
 ========
 To collect dead objects, garbage collectors must be able to identify
 #. identify which object each pointer relates to, and
 #. potentially update each of those copies.
 This document describes the mechanism by which an LLVM based compiler
 can provide this information to a language runtime/collector, and
-ensure that all pointers can be read and updated if desired.  The
+ensure that all pointers can be read and updated if desired.
-heart of the approach is to construct (or rewrite) the IR in a manner
-where the possible updates performed by the garbage collector are
+At a high level, LLVM has been extended to support compiling to an abstract
+machine which extends the actual target with a non-integral pointer type
+suitable for representing a garbage collected reference to an object.  In
+particular, such non-integral pointer type have no defined mapping to an
+integer representation.  This semantic quirk allows the runtime to pick a
+integer mapping for each point in the program allowing relocations of objects
+without visible effects.
+Warning: Non-Integral Pointer Types are a newly added concept in LLVM IR.
+It's possible that we've missed disabling some of the optimizations which
+assume an integral value for pointers.  If you find such a case, please
+file a bug or share a patch.
+Warning: There is one currently known semantic hole in the definition of
+non-integral pointers which has not been addressed upstream.  To work around
+this, you need to disable speculation of loads unless the memory type
+(non-integral pointer vs anything else) is known to unchanged.  That is, it is
+not safe to speculate a load if doing causes a non-integral pointer value to
+be loaded as any other type or vice versa.  In practice, this restriction is
+well isolated to isSafeToSpeculate in ValueTracking.cpp.
+This high level abstract machine model is used for most of the LLVM optimizer.
+Before starting code generation, we switch representations to an explicit form.
+In theory, a frontend could directly generate this low level explicit form, but
+doing so is likely to inhibit optimization.
+The heart of the explicit approach is to construct (or rewrite) the IR in a
+manner where the possible updates performed by the garbage collector are
 explicitly visible in the IR.  Doing so requires that we:
 #. create a new SSA value for each potentially relocated pointer, and
 ensure that no uses of the original (non relocated) value is
 reachable after the safepoint,
 associated with) for each statepoint.
 At the most abstract level, inserting a safepoint can be thought of as
 replacing a call instruction with a call to a multiple return value
 function which both calls the original target of the call, returns
-it's result, and returns updated values for any live pointers to
+its result, and returns updated values for any live pointers to
 garbage collected objects.
 Note that the task of identifying all live pointers to garbage
 collected values, transforming the IR to expose a pointer giving the
 base object for every such live pointer, and inserting all the
 	  .byte	2
 	  .byte	8
 	  .short	7
 	  .long	0
-This example was taken from the tests for the :ref:`RewriteStatepointsForGC` utility pass.  As such, it's full StackMap can be easily examined with the following command.
+This example was taken from the tests for the :ref:`RewriteStatepointsForGC`
+utility pass.  As such, its full StackMap can be easily examined with the
+following command.
 .. code-block:: bash
 opt -rewrite-statepoints-for-gc test/Transforms/RewriteStatepointsForGC/basics.ll -S | llc -debug-only=stackmaps
 As a practical consideration, many garbage-collected systems allow code that is
 collector-aware ("managed code") to call code that is not collector-aware
 ("unmanaged code"). It is common that such calls must also be safepoints, since
 it is desirable to allow the collector to run during the execution of
-unmanaged code. Futhermore, it is common that coordinating the transition from
+unmanaged code. Furthermore, it is common that coordinating the transition from
 managed to unmanaged code requires extra code generation at the call site to
 inform the collector of the transition. In order to support these needs, a
 statepoint may be marked as a GC transition, and data that is necessary to
 perform the transition (if any) may be provided as additional arguments to the
 statepoint.
 Semantics:
 """"""""""
 The return value of ``gc.relocate`` is the potentially relocated value
-of the pointer specified by it's arguments.  It is unspecified how the
+of the pointer specified by its arguments.  It is unspecified how the
 value of the returned pointer relates to the argument to the
 ``gc.statepoint`` other than that a) it points to the same source
 language object with the same offset, and b) the 'based-on'
 relationship of the newly relocated pointers is a projection of the
 unrelocated pointers.  In particular, the integer value of the pointer
 .. _RewriteStatepointsForGC:
 RewriteStatepointsForGC
 ^^^^^^^^^^^^^^^^^^^^^^^^
-The pass RewriteStatepointsForGC transforms a functions IR by replacing a
+The pass RewriteStatepointsForGC transforms a function's IR to lower from the
-``gc.statepoint`` (with an optional ``gc.result``) with a full relocation
+abstract machine model described above to the explicit statepoint model of
-sequence, including all required ``gc.relocates``.  To function, the pass
+relocations.  To do this, it replaces all calls or invokes of functions which
-requires that the GC strategy specified for the function be able to reliably
+might contain a safepoint poll with a ``gc.statepoint`` and associated full
-distinguish between GC references and non-GC references in IR it is given.
+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
+whitelist 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 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)
+call void @foo()
 ret i8 addrspace(1)* %obj
 }
 The pass would produce this IR:
 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.  Address space 1 is not globally reserved for this purpose.
+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.
 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).
 as null) are also assumed to be base pointers.  In practice, this constraint
 can be relaxed to producing interior derived pointers provided the target
 collector can find the associated allocation from an arbitrary interior
 derived pointer.
-In practice, RewriteStatepointsForGC can be run much later in the pass
+By default RewriteStatepointsForGC passes in ``0xABCDEF00`` as the statepoint
-pipeline, after most optimization is already done.  This helps to improve
-the quality of the generated code when compiled with garbage collection support.
-In the long run, this is the intended usage model.  At this time, a few details
-have yet to be worked out about the semantic model required to guarantee this
-is always correct.  As such, please use with caution and report bugs.
-.. _PlaceSafepoints:
-PlaceSafepoints
-^^^^^^^^^^^^^^^^
-The pass PlaceSafepoints transforms a function's IR by replacing any call or
-invoke instructions with appropriate ``gc.statepoint`` and ``gc.result`` pairs,
-and inserting safepoint polls sufficient to ensure running code checks for a
-safepoint request on a timely manner.  This pass is expected to be run before
-RewriteStatepointsForGC and thus does not produce full relocation sequences.
-As an example, given input IR of the following:
-.. code-block:: llvm
-define void @test() gc "statepoint-example" {
-call void @foo()
-ret void
-}
-declare void @do_safepoint()
-define void @gc.safepoint_poll() {
-call void @do_safepoint()
-ret void
-}
-This pass would produce the following IR:
-.. code-block:: llvm
-define void @test() gc "statepoint-example" {
-%safepoint_token = call token (i64, i32, void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0)
-%safepoint_token1 = 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 0)
-ret void
-}
-In this case, we've added an (unconditional) entry safepoint poll and converted the call into a ``gc.statepoint``.  Note that despite appearances, the entry poll is not necessarily redundant.  We'd have to know that ``foo`` and ``test`` were not mutually recursive for the poll to be redundant.  In practice, you'd probably want to your poll definition to contain a conditional branch of some form.
-At the moment, PlaceSafepoints can insert safepoint polls at method entry and
-loop backedges locations.  Extending this to work with return polls would be
-straight forward if desired.
-PlaceSafepoints includes a number of optimizations to avoid placing safepoint
-polls at particular sites unless needed to ensure timely execution of a poll
-under normal conditions.  PlaceSafepoints does not attempt to ensure timely
-execution of a poll under worst case conditions such as heavy system paging.
-The implementation of a safepoint poll action is specified by looking up a
-function of the name ``gc.safepoint_poll`` in the containing Module.  The body
-of this function is inserted at each poll site desired.  While calls or invokes
-inside this method are transformed to a ``gc.statepoints``, recursive poll
-insertion is not performed.
-By default PlaceSafepoints passes in ``0xABCDEF00`` as the statepoint
 ID and ``0`` as the number of patchable bytes to the newly constructed
 ``gc.statepoint``.  These values can be configured on a per-callsite
 basis using the attributes ``"statepoint-id"`` and
 ``"statepoint-num-patch-bytes"``.  If a call site is marked with a
 ``"statepoint-id"`` function attribute and its value is a positive
 bytes' parameter of the newly constructed ``gc.statepoint``.  The
 ``"statepoint-id"`` and ``"statepoint-num-patch-bytes"`` attributes
 are not propagated to the ``gc.statepoint`` call or invoke if they
 could be successfully parsed.
-If you are scheduling the RewriteStatepointsForGC pass late in the pass order,
+In practice, RewriteStatepointsForGC should be run much later in the pass
-you should probably schedule this pass immediately before it.  The exception
+pipeline, after most optimization is already done.  This helps to improve
-would be if you need to preserve abstract frame information (e.g. for
+the quality of the generated code when compiled with garbage collection support.
-deoptimization or introspection) at safepoints.  In that case, ask on the
-llvm-dev mailing list for suggestions.
+.. _PlaceSafepoints:
+PlaceSafepoints
+^^^^^^^^^^^^^^^^
+The pass PlaceSafepoints inserts safepoint polls sufficient to ensure running
+code checks for a safepoint request on a timely manner. This pass is expected
+to be run before RewriteStatepointsForGC and thus does not produce full
+relocation sequences.
+As an example, given input IR of the following:
+.. code-block:: llvm
+define void @test() gc "statepoint-example" {
+call void @foo()
+ret void
+}
+declare void @do_safepoint()
+define void @gc.safepoint_poll() {
+call void @do_safepoint()
+ret void
+}
+This pass would produce the following IR:
+.. code-block:: llvm
+define void @test() gc "statepoint-example" {
+call void @do_safepoint()
+call void @foo()
+ret void
+}
+In this case, we've added an (unconditional) entry safepoint poll.  Note that
+despite appearances, the entry poll is not necessarily redundant.  We'd have to
+know that ``foo`` and ``test`` were not mutually recursive for the poll to be
+redundant.  In practice, you'd probably want to your poll definition to contain
+a conditional branch of some form.
+At the moment, PlaceSafepoints can insert safepoint polls at method entry and
+loop backedges locations.  Extending this to work with return polls would be
+straight forward if desired.
+PlaceSafepoints includes a number of optimizations to avoid placing safepoint
+polls at particular sites unless needed to ensure timely execution of a poll
+under normal conditions.  PlaceSafepoints does not attempt to ensure timely
+execution of a poll under worst case conditions such as heavy system paging.
+The implementation of a safepoint poll action is specified by looking up a
+function of the name ``gc.safepoint_poll`` in the containing Module.  The body
+of this function is inserted at each poll site desired.  While calls or invokes
+inside this method are transformed to a ``gc.statepoints``, recursive poll
+insertion is not performed.
+This pass is useful for any language frontend which only has to support
+garbage collection semantics at safepoints.  If you need other abstract
+frame information at safepoints (e.g. for deoptimization or introspection),
+you can insert safepoint polls in the frontend.  If you have the later case,
+please ask on llvm-dev for suggestions.  There's been a good amount of work
+done on making such a scheme work well in practice which is not yet documented
+here.
 Supported Architectures
 =======================
 Support for statepoint generation requires some code for each backend.
 Today, only X86_64 is supported.
+Problem Areas and Active Work
+=============================
+#. Support for languages which allow unmanaged pointers to garbage collected
+objects (i.e. pass a pointer to an object to a C routine) via pinning.
+#. Support for garbage collected objects allocated on the stack.  Specifically,
+allocas are always assumed to be in address space 0 and we need a
+cast/promotion operator to let rewriting identify them.
+#. The current statepoint lowering is known to be somewhat poor.  In the very
+long term, we'd like to integrate statepoints with the register allocator;
+in the near term this is unlikely to happen.  We've found the quality of
+lowering to be relatively unimportant as hot-statepoints are almost always
+inliner bugs.
+#. Concerns have been raised that the statepoint representation results in a
+large amount of IR being produced for some examples and that this
+contributes to higher than expected memory usage and compile times.  There's
+no immediate plans to make changes due to this, but alternate models may be
+explored in the future.
+#. Relocations along exceptional paths are currently broken in ToT.  In
+particular, there is current no way to represent a rethrow on a path which
+also has relocations.  See `this llvm-dev discussion
+<https://groups.google.com/forum/#!topic/llvm-dev/AE417XjgxvI>`_ for more
+detail.
 Bugs and Enhancements
 =====================
 Currently known bugs and enhancements under consideration can be
 tracked by performing a `bugzilla search
-<http://llvm.org/bugs/buglist.cgi?cmdtype=runnamed&namedcmd=Statepoint%20Bugs&list_id=64342>`_
+<https://bugs.llvm.org/buglist.cgi?cmdtype=runnamed&namedcmd=Statepoint%20Bugs&list_id=64342>`_
 for [Statepoint] in the summary field. When filing new bugs, please
 use this tag so that interested parties see the newly filed bug.  As
 with most LLVM features, design discussions take place on `llvm-dev
 <http://lists.llvm.org/mailman/listinfo/llvm-dev>`_, and patches
 should be sent to `llvm-commits

Mercurial > hg > CbC > CbC_llvm

comparison docs/Statepoints.rst @ 122:36195a0db682