Version 73 (modified by simonpj, 3 years ago) (diff)


Stack Layout


Representing Stack Slots


For example, for a variable x, the expression SS(x) is the address of the stack slot where we can spill x. (I don't think we output any C-- that uses SS anymore, but the new code generator marks its stack slots prior to layout with young<k> + 4, etc. -- Edward) The stack is assumed to grow down, and we assume that the address SS(x) points to the old end of the slot. Therefore, to address the low address of a 4-byte slot, we would use the expression SS(x + 4). And we would spill x using the following instruction:

m[SS(x + 4)] := x;




into approximately the following C--:

  sp := SS(k + 16);
  m[SS(k + 4)]  := k_info_table;
  m[SS(k + 8)]  := a;
  m[SS(k + 12)] := b;
  m[SS(k + 16)] := c;
  call f returns to k;
k:  // on entry to k, sp == stack<k+12>
  x := m[SS(k + 8)]
  y := m[SS(k + 12)]


data Area
  = RegSlot  LocalReg
  | CallArea AreaId
  deriving (Eq, Ord)

data AreaId
  = Old
  | Young BlockId
  deriving (Eq, Ord)

data CmmExpr
  = CmmLit CmmLit
  | CmmStackSlot Area Int
  deriving Eq

An Area represents space on the stack; it may use either the RegSlot constructor to represent a single stack slot for a register or the CallArea constructor to represent parameters passed to/from a function call/return. In a young CallArea, the BlockId is the label of the function call's continuation, and it passes parameters to the call.

Area layout and addressing

  • Each Area grows down, towards lower machine addresses.
  • Offsets are always positive. The low-offset end is also called the "old end" of the area, the high-offset end is also called the "young end".
  • Offset 0 (if we allowed it) would address the byte one beyond the high-address end of the Area.
  • Larger offsets (from the beginning of the Area) correspond to lower machine addresses.
  • Hence, to address a 4-byte object at the old end of Area a, we use the offset +4, thus (CmmStackSlot a 4).

The Old call area is the initial state of the stack on entry to the function (the overflow parameters and the return address) as well as any arguments that will be passed to a tail call. Note that RegSlot areas are very small (since they only need to store a single register), while CallArea are contiguous chunks of arguments.


Notice that a CmmStackSlot is an address, so we can say

  Sp = SS(a+4)

to make Sp point to a particular stack slot. Use a CmmLoad to load from the stack slot.


Call area example

A RegSlot is laid out in the same fashion, with the offset 0 pointing off the high byte of the stack slot. To address an 8-byte double-word, we would use the offset 8. To address only the high word of the same stack slot, we would use the offset 4.

Currently, the intermediate code does not explicitly use a virtual frame pointer, but when we talk about offsets into the stack, we implicitly assume that there is a virtual frame pointer that points just off the oldest byte of the return address on entry to the procedures. Therefore, on entry to the procedure, the offset of the (4-byte) return address is 4.

Laying out the stack


   Area |-> VirtualOffset

which assigns a virtual stack slot (i.e. offset in bytes, relative to the virtual frame pointer) to each Area.




A greedy algorithm

We rewrite the stack slots in two passes:

  1. Walk over the graph and choose an offset for each Area.
  2. Walk over the graph, keeping track of the stack pointer, and rewrite each address of a stack slot with an offset from the stack pointer. Also, insert adjustments to the stack pointer before and after proc points.

The details are in cmm/CmmProcPointZ.hs (they have not yet been committed, but will be soon - Aug 4, 2008).

Attachments (2)

Download all attachments as: .zip