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


Ignore:
Timestamp:
Jun 23, 2008 1:36:42 PM (7 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