1 pnkfelix 1.1.2.1 // RegFileInfo.java, created Sat Sep 11 00:00:07 1999 by pnkfelix
2 pnkfelix 1.1.2.1 // Copyright (C) 1999 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Backend.Generic;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.36 import harpoon.Util.Util;
7 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
8 pnkfelix 1.1.2.1 import harpoon.Temp.TempFactory;
9 pnkfelix 1.1.2.1
10 pnkfelix 1.1.2.25 import java.util.Arrays;
11 pnkfelix 1.1.2.25 import java.util.Collection;
12 pnkfelix 1.1.2.38 import java.util.Collections;
13 pnkfelix 1.1.2.1 import java.util.Set;
14 pnkfelix 1.1.2.29 import java.util.List;
15 pnkfelix 1.1.2.1 import java.util.Map;
16 pnkfelix 1.1.2.1 import java.util.Iterator;
17 pnkfelix 1.1.2.1
18 pnkfelix 1.1.2.1 /** <code>RegFileInfo</code> defines an interface that general program
19 pnkfelix 1.1.2.1 analyses can call to find out architecture specific information
20 pnkfelix 1.1.2.1 about the target machine's register file.
21 pnkfelix 1.1.2.13
22 pnkfelix 1.1.2.13 <p> A note about <code>Temp</code>s: several types of
23 pnkfelix 1.1.2.13 <code>Temp</code>s are mentioned in this interface, and the
24 pnkfelix 1.1.2.13 differences between them are worth noting.
25 pnkfelix 1.1.2.13
26 pnkfelix 1.1.2.13 <p> A Temp, as used in the rest of the compiler, is a variable
27 pnkfelix 1.1.2.13 suitable for storing some value in. They are temporary storage
28 pnkfelix 1.1.2.13 for intermediate values. I will refer to them as <i>Flex
29 pnkfelix 1.1.2.13 Temps</i> for the remainder of this discussion, to avoid confusion
30 pnkfelix 1.1.2.13 with other kinds of Temps. A <i>Physical Register Temp</i> is a
31 pnkfelix 1.1.2.13 special Temp for representing a physical register in the specific
32 pnkfelix 1.1.2.13 architecture's register file. Some kinds of Flex Temps may
33 pnkfelix 1.1.2.13 require multiple Physical Register Temps to fit in the register
34 pnkfelix 1.1.2.13 file, depending on the variable type and the types of registers
35 pnkfelix 1.1.2.13 offered by the architecture. A <i>Virtual Register Temp</i> is a
36 pnkfelix 1.1.2.13 abstraction of a Physical Register Temp (or several of them): it
37 pnkfelix 1.1.2.13 is not any specific register in the register file, it just
38 pnkfelix 1.1.2.13 represents a location that is somewhere in the register file.
39 pnkfelix 1.1.2.13
40 pnkfelix 1.1.2.13 <p> The idea is that the register allocator will first figure out
41 pnkfelix 1.1.2.13 at which points in the program the various Flex Temps will be in
42 pnkfelix 1.1.2.13 the register file, and where the various Loads and Stores for
43 pnkfelix 1.1.2.13 maintaining the state of the register file will go. However, the
44 pnkfelix 1.1.2.13 allocator does not have to actually assign specific Physical
45 pnkfelix 1.1.2.13 Register Temps to the Flex Temps if it does want to; it can delay
46 pnkfelix 1.1.2.13 that until later in the allocation process. This allows for Local
47 pnkfelix 1.1.2.13 and Global Allocation to work together, because Local Allocation
48 pnkfelix 1.1.2.13 can work with Virtual Register Temps, and then the Global
49 pnkfelix 1.1.2.13 Allocator can merge Virtual Registers in different Basic Blocks
50 pnkfelix 1.1.2.13 together before mapping them to Physical Register Temps.
51 pnkfelix 1.1.2.13
52 pnkfelix 1.1.2.1 @author Felix S. Klock II <pnkfelix@mit.edu>
53 cananian 1.6 @version $Id: RegFileInfo.java,v 1.6 2004/02/08 01:57:30 cananian Exp $ */
54 salcianu 1.5 public abstract class RegFileInfo implements java.io.Serializable {
55 pnkfelix 1.1.2.22
56 pnkfelix 1.1.2.22 /** Defines function from
57 pnkfelix 1.1.2.23 (<code>Temp</code> x DefPoint) ->
58 pnkfelix 1.1.2.22 <code>Set</code> of <code>CommonLoc</code>.
59 pnkfelix 1.1.2.22 */
60 pnkfelix 1.1.2.22 public interface TempLocator {
61 pnkfelix 1.1.2.22 public Set locate(Temp t, harpoon.IR.Assem.Instr i);
62 pnkfelix 1.1.2.22 }
63 pnkfelix 1.1.2.1
64 pnkfelix 1.1.2.15 /** Common super class for <code>StackOffsetLoc</code> and
65 pnkfelix 1.1.2.16 <code>MachineRegLoc</code>. Should only be implemented by
66 pnkfelix 1.1.2.16 <code>Temp</code> objects (is an interface to get around
67 pnkfelix 1.1.2.16 multiple inheritance problmes).
68 pnkfelix 1.1.2.15 */
69 pnkfelix 1.1.2.19 public interface CommonLoc {
70 pnkfelix 1.1.2.21 /** Returns the <code>KIND</code> of Loc <code>this</code> is.
71 pnkfelix 1.1.2.15 <BR> <B>effects:</B>
72 pnkfelix 1.1.2.21 If <code>this</code> is a
73 pnkfelix 1.1.2.21 <code>StackOffsetLoc</code>, returns
74 pnkfelix 1.1.2.21 <code>StackOffsetLoc.KIND</code>
75 pnkfelix 1.1.2.21 Else <code>this</code> implicitly is a
76 pnkfelix 1.1.2.21 <code>MachineRegLoc</code>, and returns
77 pnkfelix 1.1.2.21 <code>MachineRegLoc.KIND</code>.
78 pnkfelix 1.1.2.15 */
79 pnkfelix 1.1.2.21 int kind();
80 pnkfelix 1.1.2.15 }
81 pnkfelix 1.1.2.15
82 pnkfelix 1.1.2.16 /** Represents Stack Offset <code>Temp</code>s. */
83 pnkfelix 1.1.2.19 public interface StackOffsetLoc extends CommonLoc {
84 pnkfelix 1.1.2.15 public static int KIND = 1;
85 pnkfelix 1.1.2.15 int stackOffset();
86 pnkfelix 1.1.2.15 }
87 pnkfelix 1.1.2.15
88 pnkfelix 1.1.2.15 /** Defines the upper bound on possible indexes for
89 pnkfelix 1.1.2.15 <code>MachineRegLoc</code>s.
90 pnkfelix 1.1.2.15 */
91 cananian 1.1.2.18 public int maxRegIndex() { throw new Error("Unimplemented."); }
92 pnkfelix 1.1.2.15
93 pnkfelix 1.1.2.16 /** Represents Machine Register <code>Temp</code>s. */
94 cananian 1.1.2.24 public interface MachineRegLoc
95 cananian 1.1.2.24 extends CommonLoc, harpoon.Backend.Maps.BackendDerivation.Register {
96 pnkfelix 1.1.2.15 public static int KIND = 2;
97 pnkfelix 1.1.2.16
98 pnkfelix 1.1.2.16 /** Returns the index of <code>this</code> in the register file.
99 pnkfelix 1.1.2.16 <BR> <B>effects:</B> returns the abstract index of
100 pnkfelix 1.1.2.16 <code>this</code> in the register file. The index
101 pnkfelix 1.1.2.16 returned may not map directly to this register's
102 pnkfelix 1.1.2.16 position in the register file (for example, r8 may
103 pnkfelix 1.1.2.16 have an index of "0"). Each register for a given
104 pnkfelix 1.1.2.17 architecture will have a different index.
105 pnkfelix 1.1.2.17 The index is bounded as follows:
106 cananian 1.1.2.18 0 <= index < <code>RegFileInfo.this.maxRegIndex()</code>.
107 pnkfelix 1.1.2.16 */
108 pnkfelix 1.1.2.15 int regIndex();
109 pnkfelix 1.1.2.15 }
110 pnkfelix 1.1.2.15
111 pnkfelix 1.1.2.1 /** Creates a <code>RegFileInfo</code>. */
112 pnkfelix 1.1.2.1 public RegFileInfo() {
113 pnkfelix 1.1.2.1
114 pnkfelix 1.1.2.1 }
115 pnkfelix 1.1.2.1
116 pnkfelix 1.1.2.6 /** Returns the <code>Set</code> of registers live at a method's
117 pnkfelix 1.1.2.6 exit.
118 pnkfelix 1.1.2.6
119 pnkfelix 1.1.2.6 <BR> <B>effects:</B> Returns an unmodifiable <code>Set</code>
120 pnkfelix 1.1.2.6 of register <code>Temp</code>s of the registers that
121 pnkfelix 1.1.2.6 should be considered live at the end of a method.
122 pnkfelix 1.1.2.1 */
123 pnkfelix 1.1.2.1 public abstract Set liveOnExit();
124 pnkfelix 1.1.2.5
125 pnkfelix 1.1.2.5 /** Returns the Set of registers that are caller-saved.
126 pnkfelix 1.1.2.6
127 pnkfelix 1.1.2.6 <BR> <B>effects:</B> Returns an unmodifiable <code>Set</code>
128 pnkfelix 1.1.2.6 of all of the <I>caller-saved</I> register
129 pnkfelix 1.1.2.6 <code>Temp</code>s. Any register in this Set can be used
130 pnkfelix 1.1.2.6 arbitrarily in a method call, and therefore it is the
131 pnkfelix 1.1.2.6 responsibility of the caller of a method to save them if
132 pnkfelix 1.1.2.6 it wants them preserved.
133 pnkfelix 1.1.2.5 */
134 pnkfelix 1.1.2.32 // public abstract Set callerSave();
135 pnkfelix 1.1.2.5
136 pnkfelix 1.1.2.5 /** Returns the Set of registers that are callee-saved.
137 pnkfelix 1.1.2.6
138 pnkfelix 1.1.2.6 <BR> <B>effects:</B> Returns an unmodifiable <code>Set</code>
139 pnkfelix 1.1.2.6 of all of the <I>callee-saved</I> register
140 pnkfelix 1.1.2.6 <code>Temp</code>s. All registers in this Set are
141 pnkfelix 1.1.2.6 assumed to be preserved during a method call, and
142 pnkfelix 1.1.2.6 therefore it the responsibility of the method being
143 pnkfelix 1.1.2.6 called it save them and restore them before returning if
144 pnkfelix 1.1.2.6 it wants to use them for temporary storage.
145 pnkfelix 1.1.2.5 */
146 pnkfelix 1.1.2.32 // public abstract Set calleeSave();
147 pnkfelix 1.1.2.1
148 pnkfelix 1.1.2.1 /** Checks if <code>t</code> is a element of the register file for
149 pnkfelix 1.1.2.6 this architecture.
150 pnkfelix 1.1.2.6 <BR> <B>effects:</B>
151 pnkfelix 1.1.2.6 If <code>t</code> is an element of the register file,
152 pnkfelix 1.1.2.6 Then returns true,
153 pnkfelix 1.1.2.6 Else returns false.
154 pnkfelix 1.1.2.6 @param t <code>Temp</code> that may be part of the register
155 pnkfelix 1.1.2.6 file.
156 pnkfelix 1.1.2.1 */
157 pnkfelix 1.1.2.32 public abstract boolean isRegister(Temp t);
158 pnkfelix 1.1.2.1
159 pnkfelix 1.1.2.36
160 pnkfelix 1.1.2.36 /** Returns the number of slots that <code>t</code>'s assigned
161 pnkfelix 1.1.2.36 register sequence occupies in the register file.
162 pnkfelix 1.1.2.36
163 pnkfelix 1.1.2.36 <p> The default implementation returns 1; subclasses should
164 pnkfelix 1.1.2.36 override to account for how their respective architectures
165 pnkfelix 1.1.2.36 handle multi-register temps (such as longs or doubles).
166 pnkfelix 1.1.2.37 In any case, should always return an integer greater than
167 pnkfelix 1.1.2.37 zero.
168 pnkfelix 1.1.2.36 */
169 pnkfelix 1.1.2.37 public int occupancy(Temp t) { return 1; }
170 pnkfelix 1.1.2.36
171 pnkfelix 1.1.2.36 /** Returns the degree of conflict that <code>b</code> inflicts
172 pnkfelix 1.1.2.36 upon <code>a</code> if the two <code>Temp</code>s interfere.
173 pnkfelix 1.1.2.36
174 pnkfelix 1.1.2.36 <p> The default implementation returns 1; subclasses should
175 pnkfelix 1.1.2.36 override to account for how their respect architectures
176 pnkfelix 1.1.2.36 constrain the assignment of multi-register temps (such as
177 pnkfelix 1.1.2.36 longs or doubles).
178 pnkfelix 1.1.2.36
179 pnkfelix 1.1.2.36 <p>Also, if the two registers can never be assigned to the
180 pnkfelix 1.1.2.36 same register bank, then it is valid for this method to return
181 pnkfelix 1.1.2.36 <code>0</code>.
182 pnkfelix 1.1.2.36
183 pnkfelix 1.1.2.36 <p> For advice on choosing an appropriate number to return,
184 pnkfelix 1.1.2.36 see the paper "Coloring Register Pairs" by Briggs, Cooper, and
185 pnkfelix 1.1.2.36 Torczon. The mappings recommended by that paper are
186 pnkfelix 1.1.2.36 (double,single) => 2 and (double,double) => 2 [or 3].
187 pnkfelix 1.1.2.36
188 pnkfelix 1.1.2.36 */
189 pnkfelix 1.1.2.36 public int pressure(Temp a, Temp b) { return 1; }
190 pnkfelix 1.1.2.36
191 pnkfelix 1.1.2.36 /** Returns a List of Reg that can hold <code>needy</code>, given
192 pnkfelix 1.1.2.36 that the Regs in <code>occupied</code> are not available to
193 pnkfelix 1.1.2.36 hold <code>needy</code>.
194 pnkfelix 1.1.2.36
195 pnkfelix 1.1.2.36 <p> Note that the returned List is not a list of possible
196 pnkfelix 1.1.2.36 assignments, but rather a single assignment that may span more
197 pnkfelix 1.1.2.36 than one register.
198 pnkfelix 1.1.2.36 Thus the length of the returned List should equal
199 pnkfelix 1.1.2.36 <code>this.occupies(needy)</code>.
200 pnkfelix 1.1.2.37
201 pnkfelix 1.1.2.37 <p> Returns null if no assignment is available in the situation
202 pnkfelix 1.1.2.37 where all registers in <code>occupied</code> are in use.
203 pnkfelix 1.1.2.36 */
204 pnkfelix 1.1.2.37 public List assignment(Temp needy, Collection occupied) {
205 cananian 1.3.2.1 assert false : "abstract and implement in subclasses";
206 pnkfelix 1.1.2.36 return null;
207 pnkfelix 1.1.2.36 }
208 pnkfelix 1.1.2.36
209 pnkfelix 1.1.2.36 /** Returns the Regs that can never hold <code>t</code>.
210 pnkfelix 1.1.2.36
211 pnkfelix 1.1.2.36 <p> This method is used to increase the degree of
212 pnkfelix 1.1.2.36 <code>Temps</code> which have limited assignments in the
213 pnkfelix 1.1.2.37 register file. For example, if t is a <code>Temp</code> that
214 pnkfelix 1.1.2.37 can only be assigned to a certain register bank, this method
215 pnkfelix 1.1.2.37 will return a <code>Collection</code> containing all of the
216 pnkfelix 1.1.2.37 registers in the other register banks.
217 pnkfelix 1.1.2.36 */
218 pnkfelix 1.1.2.38 public Collection illegal(Temp t) {
219 pnkfelix 1.1.2.38 return Collections.EMPTY_SET;
220 pnkfelix 1.1.2.38 }
221 pnkfelix 1.1.2.36
222 pnkfelix 1.1.2.36 /** Returns all of the available registers on this architecture. */
223 pnkfelix 1.1.2.37 public Collection allRegs() { return getAllRegistersC(); }
224 pnkfelix 1.1.2.36
225 pnkfelix 1.1.2.31 /** Produces a mutable <code>Set</code> of register assignments
226 pnkfelix 1.1.2.31 that can hold <code>t</code>. FSK: experimental method.
227 pnkfelix 1.1.2.34 <BR> <B>requires:</B> t is not a physical register Temp.
228 pnkfelix 1.1.2.30 <BR> <B>effects:</B> Returns a <code>Set</code> of possible
229 pnkfelix 1.1.2.30 register assignments for <code>t</code>, where each
230 pnkfelix 1.1.2.31 assignment is an unmodifiable <code>List</code> of
231 pnkfelix 1.1.2.31 Register <code>Temp</code>s. The elements of each
232 pnkfelix 1.1.2.30 <code>List</code> are ordered according to proper
233 pnkfelix 1.1.2.30 placement of the Register-bitlength words of the value in
234 pnkfelix 1.1.2.35 <code>t</code>, low-order words first. Every list
235 pnkfelix 1.1.2.35 returned will have the same length.
236 pnkfelix 1.1.2.35 The Set returned may be a <code>SortedSet</code>, in
237 pnkfelix 1.1.2.35 which case the earlier assignments are favored over later
238 pnkfelix 1.1.2.35 ones.
239 pnkfelix 1.1.2.30 */
240 pnkfelix 1.1.2.30 public Set getRegAssignments(Temp t) {
241 cananian 1.3.2.1 assert false : "abstract and implement in subclasses";
242 pnkfelix 1.1.2.30 return null;
243 pnkfelix 1.1.2.30 }
244 pnkfelix 1.1.2.30
245 pnkfelix 1.1.2.1 /** Analyzes <code>regfile</code> to find free registers that
246 pnkfelix 1.1.2.1 <code>t</code> can be assigned to.
247 pnkfelix 1.1.2.25 (FSK: Need to update this method to incorporate knowledge of
248 pnkfelix 1.1.2.13 Virtual Register Temps (perhaps it is guaranteed not to throw
249 pnkfelix 1.1.2.25 a SpillException when given a Virtual Register Temp))
250 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Either returns an <code>Iterator</code>
251 pnkfelix 1.1.2.1 of possible assignments (though this is not guaranteed to
252 pnkfelix 1.1.2.1 be a complete list of all possible choices, merely the
253 pnkfelix 1.1.2.4 ones that this <code>RegFileInfo</code> chose to find), or
254 pnkfelix 1.1.2.4 throws a <code>RegFileInfo.SpillException</code> with a set of
255 pnkfelix 1.1.2.1 possible spills.
256 pnkfelix 1.1.2.7 <P> Note to implementors: Resist the urge to generate an
257 pnkfelix 1.1.2.11 <code>Iterator</code> that produces <B>all</B> possible
258 pnkfelix 1.1.2.11 assignments in series.
259 pnkfelix 1.1.2.7 In general, register allocation algorithms need to, at some
260 pnkfelix 1.1.2.7 point, construct an interference graph to represent how the
261 pnkfelix 1.1.2.7 registers should be assigned. Such a graph would contain a
262 pnkfelix 1.1.2.11 node for each register assignment (and put interference edges
263 pnkfelix 1.1.2.11 between assignments that were not allowed for a given
264 pnkfelix 1.1.2.11 <code>Temp</code>), which means that even if your
265 pnkfelix 1.1.2.11 <code>Iterator</code> did not keep all of the assignments
266 pnkfelix 1.1.2.11 in memory at once, code that USES your <code>Iterator</code>
267 pnkfelix 1.1.2.11 may very well do so. Thus, while there may be many
268 pnkfelix 1.1.2.11 assignments for a <code>Temp</code> that occupies
269 pnkfelix 1.1.2.11 more than one register, and it is possible to write an
270 pnkfelix 1.1.2.11 <code>Iterator</code> that produces all such assignments, such
271 pnkfelix 1.1.2.11 an <code>Iterator</code> would cause an time/space explosion
272 pnkfelix 1.1.2.11 when applied to a decently sized register file.
273 pnkfelix 1.1.2.8 <BR> Also, realize that it is not enough to ensure that any
274 pnkfelix 1.1.2.11 one of the set
275 pnkfelix 1.1.2.11 { of possible <code>Iterator</code>s that may be returned }
276 pnkfelix 1.1.2.8 traverses a reasonably small subset of the assignment space;
277 pnkfelix 1.1.2.8 you must ensure that the UNION of all possible traversals is
278 pnkfelix 1.1.2.8 of a reasonable size. This is because the interference graph
279 pnkfelix 1.1.2.8 that is constructed will not be built from just one Suggestion
280 pnkfelix 1.1.2.8 Iterator, but rather from an Suggestion Iterator
281 pnkfelix 1.1.2.8 <B>for each</B> variable that is given a register assignment.
282 pnkfelix 1.1.2.7
283 pnkfelix 1.1.2.1 @param t <code>Temp</code> that needs to be assigned to a set
284 pnkfelix 1.1.2.1 of Registers.
285 pnkfelix 1.1.2.1 @param regfile A mapping from Register <code>Temp</code>s to
286 pnkfelix 1.1.2.1 NonRegister <code>Temp</code>s representing the
287 pnkfelix 1.1.2.1 current state of the register file. Empty
288 pnkfelix 1.1.2.1 Register <code>Temp</code>s should simply not
289 pnkfelix 1.1.2.1 have an entry in <code>regfile</code> (as
290 pnkfelix 1.1.2.1 opposed to the alternative of mapping to some
291 pnkfelix 1.1.2.28 NoValue object).
292 pnkfelix 1.1.2.1 @return A <code>List</code> <code>Iterator</code> of Register
293 pnkfelix 1.1.2.1 <code>Temp</code>s. The <code>Iterator</code> is
294 pnkfelix 1.1.2.1 guaranteed to have at least one element. Each
295 pnkfelix 1.1.2.1 <code>List</code> represents a safe place for the
296 pnkfelix 1.1.2.1 value in <code>t</code> to be stored (safe with regard
297 pnkfelix 1.1.2.1 to the architecture targeted and the type of
298 pnkfelix 1.1.2.1 <code>t</code>, <b>not</b> with regard to the current
299 pnkfelix 1.1.2.1 contents of <code>regfile</code> or the data-flow of
300 pnkfelix 1.1.2.1 the procedure being analyzed). The elements of each
301 pnkfelix 1.1.2.1 <code>List</code> in the <code>Iterator</code>
302 pnkfelix 1.1.2.1 returned are ordered according to proper placement of
303 pnkfelix 1.1.2.1 the Register-bitlength words of the value in
304 pnkfelix 1.1.2.1 <code>t</code>, low-order words first.
305 pnkfelix 1.1.2.4 @exception RegFileInfo.SpillException if the register
306 pnkfelix 1.1.2.1 file represented by <code>regfile</code> does not
307 pnkfelix 1.1.2.1 have any Register <code>Temp</code>s free to hold a
308 pnkfelix 1.1.2.1 new value of the type of <code>t</code>. This
309 pnkfelix 1.1.2.1 exception will contain the necessary information to
310 pnkfelix 1.1.2.1 spill some set of registers. After spilling, a
311 pnkfelix 1.1.2.1 second call to <code>suggestRegAssignment()</code>
312 pnkfelix 1.1.2.1 can not throw an exception, as long as no new
313 pnkfelix 1.1.2.1 values have been loaded into the register file
314 pnkfelix 1.1.2.1 since the point of spilling.
315 pnkfelix 1.1.2.1 */
316 pnkfelix 1.1.2.36 public Iterator suggestRegAssignment(Temp t, Map regfile,
317 pnkfelix 1.1.2.36 Collection preassignedTemps)
318 pnkfelix 1.1.2.36 throws RegFileInfo.SpillException {
319 cananian 1.3.2.1 assert false; return null;
320 pnkfelix 1.1.2.36 }
321 pnkfelix 1.1.2.1
322 pnkfelix 1.1.2.1 /** SpillException tells a register allocator which
323 pnkfelix 1.1.2.1 <code>Temp</code>s are appropriate for spilling in order to
324 pnkfelix 1.1.2.1 allocate space for another <code>Temp</code>.
325 pnkfelix 1.1.2.1 In the common case, <code>this.getPotentialSpills()</code>
326 pnkfelix 1.1.2.1 will just return an <code>Iterator</code> that iterates
327 pnkfelix 1.1.2.1 through singleton <code>Set</code>s for all of the registers.
328 pnkfelix 1.1.2.1 It is the responsibility of the register allocator to actually
329 pnkfelix 1.1.2.1 decide which set of registers to spill, to generate the code
330 pnkfelix 1.1.2.1 to save the values within said registers to their appropriate
331 pnkfelix 1.1.2.1 memory locations, and to generate the code to put those values
332 pnkfelix 1.1.2.1 back in the register file when they are needed next.
333 pnkfelix 1.1.2.1 */
334 pnkfelix 1.1.2.1 public static abstract class SpillException extends Exception {
335 pnkfelix 1.1.2.1 public SpillException() { super(); }
336 pnkfelix 1.1.2.1 public SpillException(String s) { super(s); }
337 pnkfelix 1.1.2.1
338 pnkfelix 1.1.2.1 /** Returns an iterator of spill candidates.
339 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns a <code>Set</code>
340 pnkfelix 1.1.2.1 <code>Iterator</code> of spill candidates. Each
341 pnkfelix 1.1.2.1 element of the <code>Iterator</code> returned
342 pnkfelix 1.1.2.30 represents a <code>Set</code> of Register
343 pnkfelix 1.1.2.1 <code>Temp</code>s that could be spilled to free up
344 pnkfelix 1.1.2.1 the amount of space needed for the attempted
345 pnkfelix 1.1.2.1 assignment in the register file. The returned
346 pnkfelix 1.1.2.1 <code>Iterator</code> is not guaranteed to iterate
347 pnkfelix 1.1.2.1 through all possible <code>Set</code>s of
348 pnkfelix 1.1.2.1 combinations of spill candidates, but should iterate
349 pnkfelix 1.1.2.1 through a decent selection so that the Register
350 pnkfelix 1.1.2.1 Allocator has significant freedom in selecting
351 pnkfelix 1.1.2.1 registers to spill.
352 pnkfelix 1.1.2.1 */
353 pnkfelix 1.1.2.1 public abstract Iterator getPotentialSpills();
354 pnkfelix 1.1.2.1 }
355 pnkfelix 1.1.2.1
356 pnkfelix 1.1.2.1
357 pnkfelix 1.1.2.1 /** Returns an array of <code>Temp</code>s which represent all
358 pnkfelix 1.1.2.1 * the available registers on the machine. */
359 pnkfelix 1.1.2.1 public abstract Temp[] getAllRegisters();
360 pnkfelix 1.1.2.13
361 pnkfelix 1.1.2.25 /** Returns a Collection of <code>Temp</code>s which represent all
362 pnkfelix 1.1.2.25 * the available registers on the machine. */
363 pnkfelix 1.1.2.25 public Collection getAllRegistersC() {
364 pnkfelix 1.1.2.25 return Arrays.asList(getAllRegisters());
365 pnkfelix 1.1.2.29 }
366 pnkfelix 1.1.2.29
367 pnkfelix 1.1.2.29 /** Returns a List of the Component Temps that compose
368 pnkfelix 1.1.2.29 <code>t</code>. If <code>t</code> is not a Composite Temp
369 pnkfelix 1.1.2.29 (ie, it maps directly to a single register in the Register
370 pnkfelix 1.1.2.29 File) then the singleton List <code>[ t ]</code> is returned.
371 pnkfelix 1.1.2.29
372 pnkfelix 1.1.2.29 Note that the default implementation assumes that
373 pnkfelix 1.1.2.29 <code>t</code> is not a Composite Temp; architectures with
374 pnkfelix 1.1.2.29 Composite Temps should override and properly implement this
375 pnkfelix 1.1.2.29 method.
376 pnkfelix 1.1.2.29 */
377 pnkfelix 1.1.2.29 public List expand(Temp t) {
378 cananian 1.6 return net.cscott.jutil.ListFactory.singleton(t);
379 pnkfelix 1.1.2.25 }
380 pnkfelix 1.1.2.25
381 cananian 1.1.2.2 /** Returns a specific register on the machine.<BR>
382 cananian 1.1.2.2 * <code>getRegister(index)==getAllRegisters()[index]</code>
383 cananian 1.1.2.2 */
384 cananian 1.1.2.2 public Temp getRegister(int index) { return getAllRegisters()[index]; }
385 pnkfelix 1.1.2.27
386 pnkfelix 1.1.2.27
387 pnkfelix 1.1.2.27 // FSK: these two methods are probably unneeded with the General
388 pnkfelix 1.1.2.27 // Register Allocator, and may encourage register allocation
389 pnkfelix 1.1.2.27 // implementations to take a "dangerous" approach... look into
390 pnkfelix 1.1.2.27 // deprecating it (or localizing it to
391 pnkfelix 1.1.2.27 // Backend.StrongARM.RegFileInfo)
392 pnkfelix 1.1.2.1
393 pnkfelix 1.1.2.1 /** Returns an array of <code>Temp</code>s for all the registers
394 pnkfelix 1.1.2.1 * that the register allocator can feel free to play with */
395 pnkfelix 1.1.2.1 public abstract Temp[] getGeneralRegisters();
396 pnkfelix 1.1.2.13
397 pnkfelix 1.1.2.25 /** Returns a Collection of <code>Temp</code>s for all the registers
398 pnkfelix 1.1.2.25 * that the register allocator can feel free to play with */
399 pnkfelix 1.1.2.25 public Collection getGeneralRegistersC() {
400 pnkfelix 1.1.2.25 return Arrays.asList(getGeneralRegisters());
401 pnkfelix 1.1.2.25 }
402 pnkfelix 1.1.2.1
403 cananian 1.2 }