Home | History | Annotate | Download | only in docs 
      1 ========================
      2 Segmented Stacks in LLVM
      3 ========================
      4 
      5 .. contents::
      6    :local:
      7 
      8 Introduction
      9 ============
     10 
     11 Segmented stack allows stack space to be allocated incrementally than as a
     12 monolithic chunk (of some worst case size) at thread initialization. This is
     13 done by allocating stack blocks (henceforth called *stacklets*) and linking them
     14 into a doubly linked list. The function prologue is responsible for checking if
     15 the current stacklet has enough space for the function to execute; and if not,
     16 call into the libgcc runtime to allocate more stack space. When using ``llc``,
     17 segmented stacks can be enabled by adding ``-segmented-stacks`` to the command
     18 line.
     19 
     20 The runtime functionality is `already there in libgcc
     21 <http://gcc.gnu.org/wiki/SplitStacks>`_.
     22 
     23 Implementation Details
     24 ======================
     25 
     26 .. _allocating stacklets:
     27 
     28 Allocating Stacklets
     29 --------------------
     30 
     31 As mentioned above, the function prologue checks if the current stacklet has
     32 enough space. The current approach is to use a slot in the TCB to store the
     33 current stack limit (minus the amount of space needed to allocate a new block) -
     34 this slot's offset is again dictated by ``libgcc``. The generated
     35 assembly looks like this on x86-64:
     36 
     37 .. code-block:: nasm
     38 
     39     leaq     -8(%rsp), %r10
     40     cmpq     %fs:112,  %r10
     41     jg       .LBB0_2
     42 
     43     # More stack space needs to be allocated
     44     movabsq  $8, %r10   # The amount of space needed
     45     movabsq  $0, %r11   # The total size of arguments passed on stack
     46     callq    __morestack
     47     ret                 # The reason for this extra return is explained below
     48   .LBB0_2:
     49     # Usual prologue continues here
     50 
     51 The size of function arguments on the stack needs to be passed to
     52 ``__morestack`` (this function is implemented in ``libgcc``) since that number
     53 of bytes has to be copied from the previous stacklet to the current one. This is
     54 so that SP (and FP) relative addressing of function arguments work as expected.
     55 
     56 The unusual ``ret`` is needed to have the function which made a call to
     57 ``__morestack`` return correctly. ``__morestack``, instead of returning, calls
     58 into ``.LBB0_2``. This is possible since both, the size of the ``ret``
     59 instruction and the PC of call to ``__morestack`` are known. When the function
     60 body returns, control is transferred back to ``__morestack``. ``__morestack``
     61 then de-allocates the new stacklet, restores the correct SP value, and does a
     62 second return, which returns control to the correct caller.
     63 
     64 Variable Sized Allocas
     65 ----------------------
     66 
     67 The section on `allocating stacklets`_ automatically assumes that every stack
     68 frame will be of fixed size. However, LLVM allows the use of the ``llvm.alloca``
     69 intrinsic to allocate dynamically sized blocks of memory on the stack. When
     70 faced with such a variable-sized alloca, code is generated to:
     71 
     72 * Check if the current stacklet has enough space. If yes, just bump the SP, like
     73   in the normal case.
     74 * If not, generate a call to ``libgcc``, which allocates the memory from the
     75   heap.
     76 
     77 The memory allocated from the heap is linked into a list in the current
     78 stacklet, and freed along with the same. This prevents a memory leak.
     79