Changes between Version 62 and Version 63 of Commentary/Compiler/StackAreas
- Jun 30, 2008 4:23:10 PM (6 years ago)
v62 v63 74 74 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. 75 75 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. 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. 77 77 78 78 … … 83 83 Area |-> VirtualOffset 84 84 }}} 85 which assigns a virtual stack slot (i.e offsetrelative to the virtual frame pointer) to each `Area`. 85 which assigns a virtual stack slot (i.e relative to the virtual frame pointer) to each `Area`. 86 86 87 87 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 opportunities for optimization: … … 91 91 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 location on the stack. How is that achieved? By making sure the location where the value is returned is also its spill slot. 92 92 93 === The greedy algorithm === 93 === A greedy algorithm === 94 95 We 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. 94 98 95 99 One 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.