Changes between Version 62 and Version 63 of Commentary/Compiler/StackAreas


Ignore:
Timestamp:
Jun 30, 2008 4:23:10 PM (6 years ago)
Author:
dias
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/StackAreas

    v62 v63  
    7474A `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. 
    7575 
    76 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. 
     76Currently, 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. 
    7777 
    7878 
     
    8383   Area |-> VirtualOffset 
    8484}}} 
    85 which assigns a virtual stack slot (i.e offset relative to the virtual frame pointer) to each `Area`. 
     85which assigns a virtual stack slot (i.e. offset in bytes, relative to the virtual frame pointer) to each `Area`. 
    8686 
    8787A 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: 
     
    9191As 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. 
    9292 
    93 === The greedy algorithm === 
     93=== A greedy algorithm === 
     94 
     95We rewrite the stack slots in two passes: 
     96 1. Walk over the graph and choose an offset for each `Area`. 
     97 1. 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. 
    9498 
    9599One way to assign stack slots is to traverse the flow graph in a reverse post-order depth-first search, allocating a stack location to each stack slot the first time we encounter the slot. (Note: When we encounter a parameter-passing area for the first time, we allocate stack locations for the whole area.) The allocation is then reused for every reference to the stack slot.