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


Ignore:
Timestamp:
Jun 23, 2008 1:36:42 PM (6 years ago)
Author:
dias
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Commentary/Compiler/StackAreas

    v30 v31  
    4040where {{{m[e]}}} refers to an address {{{e}}} in memory. 
    4141 
    42 But what about parameter passing? We use a similar technique, but this time we describe the slot for each location as an offset within the area where the parameters are passed. For example, we compile a function call 
     42But what about parameter passing? We use a similar technique, but this time we describe the slot for each location as an offset within the area where the parameters are passed. For example, we lower a function call 
    4343 
    4444{{{ 
     
    9595=== The greedy algorithm === 
    9696 
    97 One 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. 
     97One 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. 
    9898 
    9999The 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. 
     100 * A map from each allocated stack slot to its assigned location on the stack: this map is used to make sure that we use only a single stack location for each stack slot. 
    101101 * 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. 
    102102 
    103103Note: 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. 
     104 
     105Let's walk through an example. The following is a simple program in pseudo-C--: 
     106 
     107{{{ 
     108   if <> then 
     109     x, y = f(a, b, c); 
     110     ... <uses y> 
     111   else 
     112     x, z = g(a, b, c); 
     113   spill<x> // some source code resulting in x getting spilled 
     114   ... <possibly uses y> 
     115}}} 
     116 
     117The program may be lowered to the following C-- code: 
     118 
     119{{{ 
     120  sp := stack<k + 4>; 
     121  m[stack<k + 1>] := k_info_table; 
     122  m[stack<k + 2>] := a; 
     123  m[stack<k + 3>] := b; 
     124  m[stack<k + 4>] := c; 
     125k:  // on entry to k, sp == stack<k+3> 
     126  x := m[stack<k + 2>] 
     127  y := m[stack<k + 3>] 
     128}}} 
    104129 
    105130