From: edwin <none@none>
Date: Sat, 4 Feb 2006 17:25:57 +0000 (+0000)
Subject: * doc/stack.txt: Added. This file describes some details about the
X-Git-Url: http://wien.tomnetworks.com/gitweb/?p=cacao.git;a=commitdiff_plain;h=cf6f4df075a3bf9adc19091197b53fe41e53fd30

* doc/stack.txt: Added. This file describes some details about the
stack representation.
---

diff --git a/doc/stack.txt b/doc/stack.txt
new file mode 100644
index 000000000..02eee0fa2
--- /dev/null
+++ b/doc/stack.txt
@@ -0,0 +1,73 @@
+STACK REPRESENTATION INTERNALS
+==============================
+
+Author : Edwin Steiner
+Changes: -
+
+The array structure of the stack representation
+===============================================
+
+Within certain limits the CACAO stack representation can be treated as an 
+array of `stackelements`. This is possible because certain groups of 
+stackelements are guaranteed to be allocated consecutively.
+
+The following invariants hold at all time for the stack representation:
+
+    1) The stack representations of different basic blocks are disjoint.
+
+    2) The instack (if non-NULL) of a block is allocated consecutively:
+
+            in->prev == (in - 1) or NULL
+
+    3) The output stack slots of an instruction (if any) are allocated consecutively:
+
+            dst->prev == (dst - 1) or (stackslot present before instruction) or NULL
+
+    4) The stack slots produced by instructions within a basic block are allocated
+       consecutively:
+
+            [slots produced by instruction 0]  <--- bptr->stack
+            [slots produced by instruction 1]
+                          ...
+            [slots produced by instruction N]
+
+		CAUTION: In this context `produced` means that a stackelement has been
+		         allocated to represent the output of the instruction. For example
+				 the SWAP instruction produces two stackelements although it does
+				 not change the stack depth.
+
+    5) The instack of a block (if non-NULL) is allocated at a lower address than
+       the stack slots produced within the block (if any).
+
+    6) References can only go to lower memory addresses. That is, for each stack slot sp:
+
+            (sp->prev == NULL) or (sp->prev < sp)
+
+    ATTENTION: The instack of a block and the slots produced within the block
+               are *not* guaranteed to be adjacent (see figure below)!
+
+    ATTENTION: not every stack slot that is allocated may be reachable
+               by following the pointer in basicblock or instruction!
+
+			   NOTE: This is a problem. As far as I know it is only the case
+			         for IINC, which produces a dummy stack slot. We should
+					 change that.
+
+
+Figure 1: Stack representation of a basic block:
+               
+=============>>> rising memory address >>>================>>>========================>>>
+
+               (references may only go in this <--- direction)
+               
++-----------------------+                      +-------------------------------+
+| I0 <- I1 <- ... <- In | -------------------- | slots produced in basic block |
++-----------------------+                      +-------------------------------+
+                      ^                          ^
+                      |                          |
+                 bptr->instack              bptr->stack
+
+NOTE: The bptr->stack field will be added for inlining. It is not in CACAO SVN, yet.
+
+# vim: et sts=4 sw=4
+