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

Jun 23, 2008 1:27:45 PM (6 years ago)



  • Commentary/Compiler/StackAreas

    v29 v30  
    9393As 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. 
    95 == The greedy algorithm == 
     95=== The greedy algorithm === 
     97One way to assign stack slots is to traverse the flow graph in a depth-first search, assigning stack space to each stack slot the first time it is encountered. The second time we encounter a stack slot, we reuse the previous assignment. 
     99The algorithm keeps two maps: 
     100 * A map from (allocated) stack slots to a space on the stack: this map is used to make sure that we use only a single stack location for each stack slot. 
     101 * A map that tracks the contents of the stack: this map allows us to identify empty locations on the stack that can be assigned to stack slots. Also, it should identify where the young end of the stack is. 
     103Note: We want to reuse stack slots whenever possible. Therefore, if a stack slot is assigned to a location {{{l}}}, we need a variation of liveness analysis to identify final references to {{{l}}}. After the final reference to {{{l}}}, we can remove it from our maps, freeing up {{{l}}} for reallocation to other stack slots. 
    97106== Random Thoughts ==