Changes between Version 38 and Version 39 of Commentary/Compiler/StackAreas


Ignore:
Timestamp:
Jun 24, 2008 9:40:42 AM (7 years ago)
Author:
dias
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/StackAreas

    v38 v39  
    193193== !ToDo ==
    194194
    195  * Explain the stack layout algorithm.
    196195 * State the invariants.
    197196 * Say something about aliasing.
    198 
    199 
    200 == Old Text ==
    201 
    202 The current CMM code-generation path leaves stack management completely implicit until the end of the pipeline. The consequence is that a number of things must happen all at once:
    203  * The stack is laid out.
    204  * !CopyIn and !CopyOut nodes are converted to the appropriate moves, loads and stores, as required by the calling conventions.
    205  * The stack pointer is adjusted to conventional locations before and after function calls.
    206  * The return address is pushed on the stack at call sites.
    207 And of course, none of the argument-passing or stack-adjusting instructions are available during optimization, before the stack layout is fixed.
    208 
    209 A much better approach is to give symbolic names to locations on the stack, lower all the argument passing and stack adjusting to the actual data-movement instructions, and replace the names later when the final stack layout is fixed.
    210 
    211 For example
    212 {{{
    213 f(x) {
    214    y = x;
    215    ...
    216 
    217    call g(x) returning to L;
    218 
    219  L:
    220    ...
    221 }
    222 }}}
    223 
    224 should be compiled to
    225 
    226 {{{
    227 f:
    228    x = m[stack(f, 1)]; // copy the argument from stack area `f' to local x
    229    y = x;
    230 
    231    ...
    232 
    233    sp = stack(L, 1); // Make room on the stack for the arguments
    234    m[stack(L, 1)] = L; // copy the return address
    235    m[stack(L, 0)] = x; // copy the argument
    236    call g();
    237 
    238  L:
    239    ...
    240 }
    241 }}}
    242 
    243 The exact syntax will probably be a bit different, but there's the gist of it.
    244 
    245 But how do we map the stack slots to actual hardware locations? As it turns out, it is quite common in GHC that the first definition of a variable comes when its value is returned from a function call. If the value is returned on the stack, then an important optimization is to avoid copying that value to some other ``local`` location on the stack. How is that achieved? By making sure the location where the value is returned is defined as its local location.
    246 
    247 For example,
    248 
    249 {{{
    250 f() {
    251   x = g();
    252   ...
    253 }
    254 }}}
    255 
    256 If g() returns x on the stack, we would like the return location to be x's stack slot for the rest of the procedure.
    257 Issues raised by this:
    258  * Stack holes where return addresses were stored. Such a hole can be filled with a variable that can't be stored in a convenient return slot.
    259  * Stack allocation must be based on control flow -- how else would you know if x has already been placed or if it can be stored on the bottom of the stack?