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?