doc/stack.txt

   1 STACK REPRESENTATION INTERNALS
   2 ==============================
   3
   4 Author : Edwin Steiner
   5 Changes: -
   6
   7 The array structure of the stack representation
   8 ===============================================
   9
  10 Within certain limits the CACAO stack representation can be treated as an
  11 array of `stackelements`. This is possible because certain groups of
  12 stackelements are guaranteed to be allocated consecutively.
  13
  14 The following invariants hold at all time for the stack representation:
  15
  16     1) The stack representations of different basic blocks are disjoint.
  17
  18     2) The instack (if non-NULL) of a block is allocated consecutively:
  19
  20             in->prev == (in - 1) or NULL
  21
  22     3) The output stack slots of an instruction (if any) are allocated consecutively:
  23
  24             dst->prev == (dst - 1) or (stackslot present before instruction) or NULL
  25
  26     4) The stack slots produced by instructions within a basic block are allocated
  27        consecutively:
  28
  29             [slots produced by instruction 0]  <--- bptr->stack
  30             [slots produced by instruction 1]
  31                           ...
  32             [slots produced by instruction N]
  33
  34         CAUTION: In this context `produced` means that a stackelement has been
  35                  allocated to represent the output of the instruction. For example
  36                  the SWAP instruction produces two stackelements although it does
  37                  not change the stack depth.
  38
  39     5) The instack of a block (if non-NULL) is allocated at a lower address than
  40        the stack slots produced within the block (if any).
  41
  42     6) References can only go to lower memory addresses. That is, for each stack slot sp:
  43
  44             (sp->prev == NULL) or (sp->prev < sp)
  45
  46     7) If an instruction produces any stackslots, iptr->dst points to the highest-address
  47        stackslot produced
  48        Corollary: if iptr->dst points to curstack or below, the instruction does
  49                    not produce any stackslots
  50
  51
  52     ATTENTION: The instack of a block and the slots produced within the block
  53                are *not* guaranteed to be adjacent (see figure below)!
  54
  55     ATTENTION: not every stack slot that is allocated may be reachable
  56                by following the pointers in basicblock or the instructions!
  57
  58                NOTE: This is a problem. As far as I know it is only the case
  59                      for IINC, which produces a dummy stack slot. We should
  60                      change that.
  61
  62
  63 Figure 1: Stack representation of a basic block:
  64
  65 =============>>> rising memory address >>>================>>>========================>>>
  66
  67                (references may only go in this <--- direction)
  68
  69 +-----------------------+                      +-------------------------------+
  70 | I0 <- I1 <- ... <- In | -------------------- | slots produced in basic block |
  71 +-----------------------+                      +-------------------------------+
  72                       ^                          ^
  73                       |                          |
  74                  bptr->instack              bptr->stack
  75
  76 NOTE: The bptr->stack field will be added for inlining. It is not in CACAO SVN, yet.
  77
  78 # vim: et sts=4 sw=4 ts=4
  79