Changes between Version 28 and Version 29 of Commentary/Compiler/StackAreas


Ignore:
Timestamp:
Jun 23, 2008 10:28:39 AM (6 years ago)
Author:
dias
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/StackAreas

    v28 v29  
    8787=== Laying out the stack === 
    8888 
    89 A naive approach to laying out the stack would be to give each variable its own stack slot for spilling, and allocate only the ends of the stack frame for parameter-passing areas. But this approach misses two important opportunities for optimization: 
     89A naive approach to laying out the stack would be to give each variable its own stack slot for spilling, and allocate only the ends of the stack frame for parameter-passing areas. But this approach misses two opportunities for optimization: 
    9090 * Stack slots can be reused by variables that are never on the stack at the same time 
    91  * If a function returns a variable on the stack, we might be able to use the return location as the variable's spill slot. 
     91 * If a function returns a variable on the stack, we might be able to use the return location as the variable's stack slot. 
    9292 
    93 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 spill slot.  
     93As 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 location on the stack. How is that achieved? By making sure the location where the value is returned is also its spill slot. 
     94 
     95== The greedy algorithm == 
    9496 
    9597== Random Thoughts == 
    9698 
    9799Assignments into parameter-passing areas can't be hoisted past adjustments to the stack pointer until we know the stack layout -- otherwise we might try to write off the young end of the stack. There must be some sort of invariant here, something along the lines of: "a reference to a parameter passing area must (a) succeed the adjustment moving the stack pointer to the bottom of the area and (b) precede any other stack adjustment. 
     100Restated: a def or use of a stack location is well-defined only if the stack pointer points "past" the location. Therefore, we can move a stack assignment/reference past an assignment to the stack pointer only if we can prove that this property is maintained. 
     101 
     102This all feels related to the coalescing optimization performed by register allocators. 
     103 
     104We're missing another optimization opportunity: there's no reason why different live ranges need to share the same stack slot. 
    98105 
    99106== !ToDo ==