Changes between Version 32 and Version 33 of Commentary/Compiler/StackAreas


Ignore:
Timestamp:
Jun 23, 2008 2:14:23 PM (7 years ago)
Author:
dias
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/StackAreas

    v32 v33  
    9696=== The greedy algorithm ===
    9797
    98 One way to assign stack slots is to traverse the flow graph in a depth-first search, assigning a stack location to a stack slot the first time we encounter the slot. The assignment is reused for each subsequent reference to the stack slot.
     98One way to assign stack slots is to traverse the flow graph in a reverse post-order depth-first search, assigning a stack location to each stack slot the first time we encounter the slot. The assignment is reused for each subsequent reference to the stack slot.
    9999
    100100The algorithm keeps two maps:
     
    144144}}}
    145145
    146 What about a procedure's incoming and outgoing parameters, which should appear at the young end of the stack?
     146Let's assume we visit the blocks in lexical order, which is what a reverse post-order depth-first search would give us.
     147
     148
     149Note: We can make the copy propagation only if the stack location is not "live"-out. Otherwise, we would have two values sharing the stack slot, with no guarantee that they could safely share the location. If we had an interference graph, we could make a more informed decision, but that's a non-greedy optimization.
     150
     151What about a procedure's incoming and outgoing parameters, which should appear at the young end of the stack, in a predetermined location? The locations of these stack slots are determined by convention. Should we initialize the map with their locations?
    147152
    148153Invariant: A load from a stack slot must be preceded by a spill to that stack slot. And we should visit that spill before the reload. Otherwise, something has gone horribly wrong.