Merge "Update aosp/master LLVM for rebase to r230699."

1 files changed, 580 insertions, 0 deletions

diff --git a/docs/Statepoints.rst b/docs/Statepoints.rst
new file mode 100644
index 0000000..9741c93
--- /dev/null
+++ b/docs/Statepoints.rst
@@ -0,0 +1,580 @@
+=====================================
+Garbage Collection Safepoints in LLVM
+=====================================
+
+.. contents::
+   :local:
+   :depth: 2
+
+Status
+=======
+
+This document describes a set of experimental extensions to LLVM. Use
+with caution.  Because the intrinsics have experimental status,
+compatibility across LLVM releases is not guaranteed.
+
+LLVM currently supports an alternate mechanism for conservative
+garbage collection support using the ``gcroot`` intrinsic.  The mechanism
+described here shares little in common with the alternate ``gcroot``
+implementation and it is hoped that this mechanism will eventually
+replace the gc_root mechanism.
+
+Overview
+========
+
+To collect dead objects, garbage collectors must be able to identify
+any references to objects contained within executing code, and,
+depending on the collector, potentially update them.  The collector
+does not need this information at all points in code - that would make
+the problem much harder - but only at well-defined points in the
+execution known as 'safepoints' For most collectors, it is sufficient
+to track at least one copy of each unique pointer value.  However, for
+a collector which wishes to relocate objects directly reachable from
+running code, a higher standard is required.
+
+One additional challenge is that the compiler may compute intermediate
+results ("derived pointers") which point outside of the allocation or
+even into the middle of another allocation.  The eventual use of this
+intermediate value must yield an address within the bounds of the
+allocation, but such "exterior derived pointers" may be visible to the
+collector.  Given this, a garbage collector can not safely rely on the
+runtime value of an address to indicate the object it is associated
+with.  If the garbage collector wishes to move any object, the
+compiler must provide a mapping, for each pointer, to an indication of
+its allocation.
+
+To simplify the interaction between a collector and the compiled code,
+most garbage collectors are organized in terms of three abstractions:
+load barriers, store barriers, and safepoints.
+
+#. A load barrier is a bit of code executed immediately after the
+   machine load instruction, but before any use of the value loaded.
+   Depending on the collector, such a barrier may be needed for all
+   loads, merely loads of a particular type (in the original source
+   language), or none at all.
+
+#. Analogously, a store barrier is a code fragement that runs
+   immediately before the machine store instruction, but after the
+   computation of the value stored.  The most common use of a store
+   barrier is to update a 'card table' in a generational garbage
+   collector.
+
+#. A safepoint is a location at which pointers visible to the compiled
+   code (i.e. currently in registers or on the stack) are allowed to
+   change.  After the safepoint completes, the actual pointer value
+   may differ, but the 'object' (as seen by the source language)
+   pointed to will not.
+
+  Note that the term 'safepoint' is somewhat overloaded.  It refers to
+  both the location at which the machine state is parsable and the
+  coordination protocol involved in bring application threads to a
+  point at which the collector can safely use that information.  The
+  term "statepoint" as used in this document refers exclusively to the
+  former.
+
+This document focuses on the last item - compiler support for
+safepoints in generated code.  We will assume that an outside
+mechanism has decided where to place safepoints.  From our
+perspective, all safepoints will be function calls.  To support
+relocation of objects directly reachable from values in compiled code,
+the collector must be able to:
+
+#. identify every copy of a pointer (including copies introduced by
+   the compiler itself) at the safepoint,
+#. 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
+heart of the 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,
+#. specify the relocation in a way which is opaque to the compiler to
+   ensure that the optimizer can not introduce new uses of an
+   unrelocated value after a statepoint. This prevents the optimizer
+   from performing unsound optimizations.
+#. recording a mapping of live pointers (and the allocation they're
+   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
+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
+  intrinsics correctly is explicitly out of scope for this document.
+  The recommended approach is to use the :ref:`utility passes 
+  <statepoint-utilities>` described below. 
+
+This abstract function call is concretely represented by a sequence of
+intrinsic calls known collectively as a "statepoint relocation sequence".
+
+Let's consider a simple call in LLVM IR:
+
+.. code-block:: llvm
+
+  define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 
+         gc "statepoint-example" {
+    call void ()* @foo()
+    ret i8 addrspace(1)* %obj
+  }
+
+Depending on our language we may need to allow a safepoint during the execution 
+of ``foo``. If so, we need to let the collector update local values in the 
+current frame.  If we don't, we'll be accessing a potential invalid reference 
+once we eventually return from the call.
+
+In this example, we need to relocate the SSA value ``%obj``.  Since we can't 
+actually change the value in the SSA value ``%obj``, we need to introduce a new 
+SSA value ``%obj.relocated`` which represents the potentially changed value of
+``%obj`` after the safepoint and update any following uses appropriately.  The 
+resulting relocation sequence is:
+
+.. code-block:: llvm
+
+  define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 
+         gc "statepoint-example" {
+    %0 = call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, 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(i32 %0, i32 9, i32 9)
+    ret i8 addrspace(1)* %obj.relocated
+  }
+
+Ideally, this sequence would have been represented as a M argument, N
+return value function (where M is the number of values being
+relocated + the original call arguments and N is the original return
+value + each relocated value), but LLVM does not easily support such a
+representation.
+
+Instead, the statepoint intrinsic marks the actual site of the
+safepoint or statepoint.  The statepoint returns a token value (which
+exists only at compile time).  To get back the original return value
+of the call, we use the ``gc.result`` intrinsic.  To get the relocation
+of each pointer in turn, we use the ``gc.relocate`` intrinsic with the
+appropriate index.  Note that both the ``gc.relocate`` and ``gc.result`` are
+tied to the statepoint.  The combination forms a "statepoint relocation 
+sequence" and represents the entitety of a parseable call or 'statepoint'.
+
+When lowered, this example would generate the following x86 assembly:
+
+.. code-block:: gas
+  
+	  .globl	test1
+	  .align	16, 0x90
+	  pushq	%rax
+	  callq	foo
+  .Ltmp1:
+	  movq	(%rsp), %rax  # This load is redundant (oops!)
+	  popq	%rdx
+	  retq
+
+Each of the potentially relocated values has been spilled to the
+stack, and a record of that location has been recorded to the
+:ref:`Stack Map section <stackmap-section>`.  If the garbage collector
+needs to update any of these pointers during the call, it knows
+exactly what to change.
+
+The relevant parts of the StackMap section for our example are:
+
+.. code-block:: gas
+  
+  # This describes the call site
+  # Stack Maps: callsite 2882400000
+	  .quad	2882400000
+	  .long	.Ltmp1-test1
+	  .short	0
+  # .. 8 entries skipped ..
+  # This entry describes the spill slot which is directly addressable
+  # off RSP with offset 0.  Given the value was spilled with a pushq, 
+  # that makes sense.
+  # Stack Maps:   Loc 8: Direct RSP     [encoding: .byte 2, .byte 8, .short 7, .int 0]
+	  .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.
+
+.. code-block:: bash
+
+  opt -rewrite-statepoints-for-gc test/Transforms/RewriteStatepointsForGC/basics.ll -S | llc -debug-only=stackmaps
+
+
+
+
+
+Intrinsics
+===========
+
+'llvm.experimental.gc.statepoint' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare i32
+        @llvm.experimental.gc.statepoint(func_type <target>, 
+                       i64 <#call args>. i64 <unused>, 
+                       ... (call parameters),
+                       i64 <# deopt args>, ... (deopt parameters),
+                       ... (gc parameters))
+
+Overview:
+"""""""""
+
+The statepoint intrinsic represents a call which is parse-able by the
+runtime.
+
+Operands:
+"""""""""
+
+The 'target' operand is the function actually being called.  The
+target can be specified as either a symbolic LLVM function, or as an
+arbitrary Value of appropriate function type.  Note that the function
+type must match the signature of the callee and the types of the 'call
+parameters' arguments.
+
+The '#call args' operand is the number of arguments to the actual
+call.  It must exactly match the number of arguments passed in the
+'call parameters' variable length section.
+
+The 'unused' operand is unused and likely to be removed.  Please do
+not use.
+
+The 'call parameters' arguments are simply the arguments which need to
+be passed to the call target.  They will be lowered according to the
+specified calling convention and otherwise handled like a normal call
+instruction.  The number of arguments must exactly match what is
+specified in '# call args'.  The types must match the signature of
+'target'.
+
+The 'deopt parameters' arguments contain an arbitrary list of Values
+which is meaningful to the runtime.  The runtime may read any of these
+values, but is assumed not to modify them.  If the garbage collector
+might need to modify one of these values, it must also be listed in
+the 'gc pointer' argument list.  The '# deopt args' field indicates
+how many operands are to be interpreted as 'deopt parameters'.
+
+The 'gc parameters' arguments contain every pointer to a garbage
+collector object which potentially needs to be updated by the garbage
+collector.  Note that the argument list must explicitly contain a base
+pointer for every derived pointer listed.  The order of arguments is
+unimportant.  Unlike the other variable length parameter sets, this
+list is not length prefixed.
+
+Semantics:
+""""""""""
+
+A statepoint is assumed to read and write all memory.  As a result,
+memory operations can not be reordered past a statepoint.  It is
+illegal to mark a statepoint as being either 'readonly' or 'readnone'.
+
+Note that legal IR can not perform any memory operation on a 'gc
+pointer' argument of the statepoint in a location statically reachable
+from the statepoint.  Instead, the explicitly relocated value (from a
+``gc.relocate``) must be used.
+
+'llvm.experimental.gc.result' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare type*
+        @llvm.experimental.gc.result(i32 %statepoint_token)
+
+Overview:
+"""""""""
+
+``gc.result`` extracts the result of the original call instruction
+which was replaced by the ``gc.statepoint``.  The ``gc.result``
+intrinsic is actually a family of three intrinsics due to an
+implementation limitation.  Other than the type of the return value,
+the semantics are the same.
+
+Operands:
+"""""""""
+
+The first and only argument is the ``gc.statepoint`` which starts
+the safepoint sequence of which this ``gc.result`` is a part.
+Despite the typing of this as a generic i32, *only* the value defined
+by a ``gc.statepoint`` is legal here.
+
+Semantics:
+""""""""""
+
+The ``gc.result`` represents the return value of the call target of
+the ``statepoint``.  The type of the ``gc.result`` must exactly match
+the type of the target.  If the call target returns void, there will
+be no ``gc.result``.
+
+A ``gc.result`` is modeled as a 'readnone' pure function.  It has no
+side effects since it is just a projection of the return value of the
+previous call represented by the ``gc.statepoint``.
+
+'llvm.experimental.gc.relocate' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+
+::
+
+      declare <pointer type>
+        @llvm.experimental.gc.relocate(i32 %statepoint_token, 
+                                       i32 %base_offset, 
+                                       i32 %pointer_offset)
+
+Overview:
+"""""""""
+
+A ``gc.relocate`` returns the potentially relocated value of a pointer
+at the safepoint.
+
+Operands:
+"""""""""
+
+The first argument is the ``gc.statepoint`` which starts the
+safepoint sequence of which this ``gc.relocation`` is a part.
+Despite the typing of this as a generic i32, *only* the value defined
+by a ``gc.statepoint`` is legal here.
+
+The second argument is an index into the statepoints list of arguments
+which specifies the base pointer for the pointer being relocated.
+This index must land within the 'gc parameter' section of the
+statepoint's argument list.
+
+The third argument is an index into the statepoint's list of arguments
+which specify the (potentially) derived pointer being relocated.  It
+is legal for this index to be the same as the second argument
+if-and-only-if a base pointer is being relocated. This index must land
+within the 'gc parameter' section of the statepoint's argument list.
+
+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
+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
+returned is unspecified.
+
+A ``gc.relocate`` is modeled as a ``readnone`` pure function.  It has no
+side effects since it is just a way to extract information about work
+done during the actual call modeled by the ``gc.statepoint``.
+
+.. _statepoint-stackmap-format:
+
+Stack Map Format
+================
+
+Locations for each pointer value which may need read and/or updated by
+the runtime or collector are provided via the :ref:`Stack Map format
+<stackmap-format>` specified in the PatchPoint documentation.
+
+Each statepoint generates the following Locations:
+
+* Constant which describes number of following deopt *Locations* (not
+  operands)
+* Variable number of Locations, one for each deopt parameter listed in
+  the IR statepoint (same number as described by previous Constant)
+* Variable number of Locations pairs, one pair for each unique pointer
+  which needs relocated.  The first Location in each pair describes
+  the base pointer for the object.  The second is the derived pointer
+  actually being relocated.  It is guaranteed that the base pointer
+  must also appear explicitly as a relocation pair if used after the
+  statepoint. There may be fewer pairs then gc parameters in the IR
+  statepoint. Each *unique* pair will occur at least once; duplicates
+  are possible.
+
+Note that the Locations used in each section may describe the same
+physical location.  e.g. A stack slot may appear as a deopt location,
+a gc base pointer, and a gc derived pointer.
+
+The ID field of the 'StkMapRecord' for a statepoint is meaningless and
+it's value is explicitly unspecified.
+
+The LiveOut section of the StkMapRecord will be empty for a statepoint
+record.
+
+Safepoint Semantics & Verification
+==================================
+
+The fundamental correctness property for the compiled code's
+correctness w.r.t. the garbage collector is a dynamic one.  It must be
+the case that there is no dynamic trace such that a operation
+involving a potentially relocated pointer is observably-after a
+safepoint which could relocate it.  'observably-after' is this usage
+means that an outside observer could observe this sequence of events
+in a way which precludes the operation being performed before the
+safepoint.
+
+To understand why this 'observable-after' property is required,
+consider a null comparison performed on the original copy of a
+relocated pointer.  Assuming that control flow follows the safepoint,
+there is no way to observe externally whether the null comparison is
+performed before or after the safepoint.  (Remember, the original
+Value is unmodified by the safepoint.)  The compiler is free to make
+either scheduling choice.
+
+The actual correctness property implemented is slightly stronger than
+this.  We require that there be no *static path* on which a
+potentially relocated pointer is 'observably-after' it may have been
+relocated.  This is slightly stronger than is strictly necessary (and
+thus may disallow some otherwise valid programs), but greatly
+simplifies reasoning about correctness of the compiled code.
+
+By construction, this property will be upheld by the optimizer if
+correctly established in the source IR.  This is a key invariant of
+the design.
+
+The existing IR Verifier pass has been extended to check most of the
+local restrictions on the intrinsics mentioned in their respective
+documentation.  The current implementation in LLVM does not check the
+key relocation invariant, but this is ongoing work on developing such
+a verifier.  Please ask on llvmdev if you're interested in
+experimenting with the current version.
+
+.. _statepoint-utilities:
+
+Utility Passes for Safepoint Insertion
+======================================
+
+.. _RewriteStatepointsForGC:
+
+RewriteStatepointsForGC
+^^^^^^^^^^^^^^^^^^^^^^^^
+
+The pass RewriteStatepointsForGC transforms a functions IR by replacing a 
+``gc.statepoint`` (with an optional ``gc.result``) with a full relocation 
+sequence, including all required ``gc.relocates``.  To function, the pass 
+requires that the GC strategy specified for the function be able to reliably 
+distinguish between GC references and non-GC references in IR it is given.
+
+As an example, given this code:
+
+.. code-block:: llvm
+
+  define i8 addrspace(1)* @test1(i8 addrspace(1)* %obj) 
+         gc "statepoint-example" {
+    call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+    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 i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, 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(i32 %0, i32 9, i32 9)
+    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.
+
+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).  
+
+
+In practice, RewriteStatepointsForGC can be run much later in the pass 
+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 i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @do_safepoint, i32 0, i32 0, i32 0)
+    %safepoint_token1 = call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, 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.
+
+If you are scheduling the RewriteStatepointsForGC pass late in the pass order,
+you should probably schedule this pass immediately before it.  The exception 
+would be if you need to preserve abstract frame information (e.g. for
+deoptimization or introspection) at safepoints.  In that case, ask on the 
+llvmdev mailing list for suggestions.
+
+
+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>`_
+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 `llvmdev
+<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>`_, and patches
+should be sent to `llvm-commits
+<http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits>`_ for review.
+