1 STACK REPRESENTATION INTERNALS
2 ==============================
7 The array structure of the stack representation
8 ===============================================
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.
14 The following invariants hold at all time for the stack representation:
16 1) The stack representations of different basic blocks are disjoint.
18 2) The instack (if non-NULL) of a block is allocated consecutively:
20 in->prev == (in - 1) or NULL
22 3) The output stack slots of an instruction (if any) are allocated consecutively:
24 dst->prev == (dst - 1) or (stackslot present before instruction) or NULL
26 4) The stack slots produced by instructions within a basic block are allocated
29 [slots produced by instruction 0] <--- bptr->stack
30 [slots produced by instruction 1]
32 [slots produced by instruction N]
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.
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).
42 6) References can only go to lower memory addresses. That is, for each stack slot sp:
44 (sp->prev == NULL) or (sp->prev < sp)
46 7) If an instruction produces any stackslots, iptr->dst points to the highest-address
48 Corollary: if iptr->dst points to curstack or below, the instruction does
49 not produce any stackslots
52 ATTENTION: The instack of a block and the slots produced within the block
53 are *not* guaranteed to be adjacent (see figure below)!
55 ATTENTION: not every stack slot that is allocated may be reachable
56 by following the pointers in basicblock or the instructions!
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
63 Figure 1: Stack representation of a basic block:
65 =============>>> rising memory address >>>================>>>========================>>>
67 (references may only go in this <--- direction)
69 +-----------------------+ +-------------------------------+
70 | I0 <- I1 <- ... <- In | -------------------- | slots produced in basic block |
71 +-----------------------+ +-------------------------------+
74 bptr->instack bptr->stack
76 NOTE: The bptr->stack field will be added for inlining. It is not in CACAO SVN, yet.
78 # vim: et sts=4 sw=4 ts=4