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     ATTENTION: The instack of a block and the slots produced within the block
  47                are *not* guaranteed to be adjacent (see figure below)!
  48
  49     ATTENTION: not every stack slot that is allocated may be reachable
  50                by following the pointers in basicblock or the instructions!
  51
  52                NOTE: This is a problem. As far as I know it is only the case
  53                      for IINC, which produces a dummy stack slot. We should
  54                      change that.
  55
  56
  57 Figure 1: Stack representation of a basic block:
  58
  59 =============>>> rising memory address >>>================>>>========================>>>
  60
  61                (references may only go in this <--- direction)
  62
  63 +-----------------------+                      +-------------------------------+
  64 | I0 <- I1 <- ... <- In | -------------------- | slots produced in basic block |
  65 +-----------------------+                      +-------------------------------+
  66                       ^                          ^
  67                       |                          |
  68                  bptr->instack              bptr->stack
  69
  70 NOTE: The bptr->stack field will be added for inlining. It is not in CACAO SVN, yet.
  71
  72 # vim: et sts=4 sw=4 ts=4
  73