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

Show
Ignore:
Timestamp:
06/23/08 06:36:42 (5 years ago)
Comment:

--

Unmodified
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