1 pnkfelix 1.1.2.1 // RegFile.java, created Wed Dec 8 16:24:41 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.Analysis.Instr;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
7 pnkfelix 1.1.2.10 import harpoon.IR.Assem.Instr;
8 pnkfelix 1.1.2.1 import harpoon.Util.Util;
9 pnkfelix 1.1.2.1
10 pnkfelix 1.1.2.1 import java.util.List;
11 pnkfelix 1.1.2.1 import java.util.Map;
12 pnkfelix 1.1.2.2 import java.util.Set;
13 pnkfelix 1.1.2.1 import java.util.HashMap;
14 pnkfelix 1.1.2.2 import java.util.HashSet;
15 pnkfelix 1.1.2.1 import java.util.Collections;
16 pnkfelix 1.1.2.9 import java.util.Collection;
17 pnkfelix 1.1.2.1 import java.util.Iterator;
18 pnkfelix 1.1.2.1
19 pnkfelix 1.1.2.1 /**
20 pnkfelix 1.1.2.1 * <code>RegFile</code> is an abstraction for a register file found in
21 pnkfelix 1.1.2.1 * most processor architectures for storing working sets of data.
22 pnkfelix 1.1.2.1 *
23 pnkfelix 1.1.2.1 * @author Felix S. Klock II <pnkfelix@mit.edu>
24 cananian 1.5 * @version $Id: RegFile.java,v 1.5 2004/02/08 03:19:37 cananian Exp $
25 pnkfelix 1.1.2.1 */
26 pnkfelix 1.1.2.1 class RegFile {
27 pnkfelix 1.1.2.6
28 pnkfelix 1.1.2.6 public static final boolean PRINT_USAGE = false;
29 pnkfelix 1.1.2.6
30 pnkfelix 1.1.2.9 private Collection allRegs;
31 pnkfelix 1.1.2.9
32 pnkfelix 1.1.2.8 private Map regToTmp; // Map[ Reg -> Temp ]
33 pnkfelix 1.1.2.10 private Map tmpToRegLst; // Map[ Temp -> (List<Reg>, Instr) ]
34 pnkfelix 1.1.2.1
35 pnkfelix 1.1.2.2 private Set dirtyTemps; // Set of all Temps that have been written
36 pnkfelix 1.1.2.2
37 pnkfelix 1.1.2.1 /** Creates a <code>RegFile</code>. */
38 pnkfelix 1.1.2.9 public RegFile(Collection allRegisters) {
39 pnkfelix 1.1.2.8 regToTmp = new HashMap();
40 pnkfelix 1.1.2.2 tmpToRegLst = new HashMap();
41 pnkfelix 1.1.2.2 dirtyTemps = new HashSet();
42 pnkfelix 1.1.2.9 allRegs = allRegisters;
43 pnkfelix 1.1.2.1 }
44 pnkfelix 1.1.2.1
45 pnkfelix 1.1.2.2 /** Marks the pseudo register <code>preg</code> as dirty.
46 pnkfelix 1.1.2.7 <BR> <B>requires:</B> <OL>
47 pnkfelix 1.1.2.7 <LI> <code>preg</code> is a pseudo register Temp
48 pnkfelix 1.1.2.7 (not a register)
49 pnkfelix 1.1.2.7 <LI> <code>preg</code> currently is assigned
50 pnkfelix 1.1.2.7 in <code>this</code>.
51 pnkfelix 1.1.2.7 </OL>
52 pnkfelix 1.1.2.2 <BR> <B>modifies:</B> <code>this</code>
53 pnkfelix 1.1.2.2 <BR> <B>effects:</B> marks <code>preg</code> as dirty.
54 pnkfelix 1.1.2.2 <code>preg</code> will remain dirty until it is removed
55 pnkfelix 1.1.2.2 from <code>this</code>.
56 pnkfelix 1.1.2.2 */
57 pnkfelix 1.1.2.2 public void writeTo(Temp preg) {
58 cananian 1.3.2.1 assert hasAssignment(preg) : (/* "temp: "+preg+ */
59 pnkfelix 1.1.2.11 " should have an assignment "
60 pnkfelix 1.1.2.11 /* +"in "+this */);
61 pnkfelix 1.1.2.5
62 pnkfelix 1.1.2.6 if (PRINT_USAGE) System.out.println(this+".writeTo: "+preg);
63 pnkfelix 1.1.2.6
64 pnkfelix 1.1.2.5 // FSK: this assertion is too strict, but it might only be
65 pnkfelix 1.1.2.5 // because of a hack in the spec-file. Find out whether we
66 pnkfelix 1.1.2.5 // can make multiple writes illegal
67 cananian 1.3.2.1 // assert !dirtyTemps.contains(preg) : // "should only write to "+preg+" once";
68 pnkfelix 1.1.2.2 dirtyTemps.add(preg);
69 pnkfelix 1.1.2.2 }
70 pnkfelix 1.1.2.2
71 pnkfelix 1.1.2.2 /** Returns whether the pseudo register is clean.
72 pnkfelix 1.1.2.2 <BR> <B>requires:</B> <code>preg</code> currently is assigned
73 pnkfelix 1.1.2.2 in <code>this</code>.
74 pnkfelix 1.1.2.2 <BR> <B>effects:</B> if the pseudo register <code>preg</code>
75 pnkfelix 1.1.2.2 has been marked as dirty since last being assigned in
76 pnkfelix 1.1.2.2 <code>this</code>, returns False. Else returns True.
77 pnkfelix 1.1.2.2 */
78 pnkfelix 1.1.2.2 public boolean isClean(Temp preg) {
79 pnkfelix 1.1.2.4 return !isDirty(preg);
80 pnkfelix 1.1.2.2 }
81 pnkfelix 1.1.2.2
82 pnkfelix 1.1.2.2 /** Returns whether the pseudo register is dirty.
83 pnkfelix 1.1.2.2 <BR> <B>requires:</B> <code>preg</code> currently is assigned
84 pnkfelix 1.1.2.2 in <code>this</code>.
85 pnkfelix 1.1.2.2 <BR> <B>effects:</B> if pseudo register <code>preg</code> has
86 pnkfelix 1.1.2.2 been marked as dirty since last being assigned in
87 pnkfelix 1.1.2.2 <code>this</code>, returns True. Else returns False.
88 pnkfelix 1.1.2.2 */
89 pnkfelix 1.1.2.2 public boolean isDirty(Temp preg) {
90 cananian 1.3.2.1 assert hasAssignment(preg) : (/* "temp: "+preg+ */
91 pnkfelix 1.1.2.11 " should have an assignment "
92 cananian 1.3.2.1 /* +"in "+this */);
93 pnkfelix 1.1.2.2 return dirtyTemps.contains(preg);
94 pnkfelix 1.1.2.2 }
95 pnkfelix 1.1.2.2
96 pnkfelix 1.1.2.2 public String toString() {
97 pnkfelix 1.1.2.6 return tmpToRegLst.toString();
98 pnkfelix 1.1.2.6 // return regToTmp.toString();
99 pnkfelix 1.1.2.6 // return "RegFile"+hashCode();
100 pnkfelix 1.1.2.2 }
101 pnkfelix 1.1.2.2
102 pnkfelix 1.1.2.3 /** Returns a snapshot of the current mapping from registers to
103 pnkfelix 1.1.2.3 pseudoregisters.
104 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns an immutable <code>Map</code> of
105 pnkfelix 1.1.2.1 Register <code>Temp</code>s to Pseudo-Register
106 pnkfelix 1.1.2.1 <code>Temp</code>s, representing the current state of the
107 pnkfelix 1.1.2.1 register file. The <code>Map</code> returned is suitable
108 pnkfelix 1.1.2.1 for use with RegFileInfo.
109 pnkfelix 1.1.2.1 */
110 pnkfelix 1.1.2.1 public Map getRegToTemp() {
111 pnkfelix 1.1.2.1 // we create a new HashMap so that changes to the current
112 pnkfelix 1.1.2.1 // Register File are not reflected in the returned Map, and we
113 pnkfelix 1.1.2.1 // make it unmodifiable so that it remains immutable.
114 pnkfelix 1.1.2.1 return Collections.unmodifiableMap(new HashMap(regToTmp));
115 pnkfelix 1.1.2.1 }
116 pnkfelix 1.1.2.1
117 pnkfelix 1.1.2.8 /** Generates a set-view of the pseudo-register <code>Temp</code>s
118 pnkfelix 1.1.2.8 in <code>this</code>.
119 pnkfelix 1.1.2.8 */
120 pnkfelix 1.1.2.8 public Set tempSet() {
121 pnkfelix 1.1.2.8 return tmpToRegLst.keySet();
122 pnkfelix 1.1.2.8 }
123 pnkfelix 1.1.2.8
124 pnkfelix 1.1.2.6 /** Returns some pseudo-register associated with <code>reg</code>.
125 pnkfelix 1.1.2.1 If there is no pseudo-register associated with
126 pnkfelix 1.1.2.1 <code>reg</code>, returns <code>null</code>.
127 pnkfelix 1.1.2.1 */
128 pnkfelix 1.1.2.1 public Temp getTemp(Temp reg) {
129 pnkfelix 1.1.2.1 return (Temp) regToTmp.get(reg);
130 pnkfelix 1.1.2.1 }
131 pnkfelix 1.1.2.10
132 pnkfelix 1.1.2.10 class RegListAndInstr {
133 pnkfelix 1.1.2.10 final List l; final Instr i;
134 pnkfelix 1.1.2.10 RegListAndInstr(List regs, Instr instr) {
135 pnkfelix 1.1.2.10 l = regs; i = instr;
136 pnkfelix 1.1.2.10 }
137 pnkfelix 1.1.2.10 public String toString() {
138 pnkfelix 1.1.2.10 return "( "+(l!=null?l.toString():"") + ", "+
139 pnkfelix 1.1.2.10 (i!=null?i.toString():"")+" )";
140 pnkfelix 1.1.2.10 }
141 pnkfelix 1.1.2.10 }
142 pnkfelix 1.1.2.1
143 pnkfelix 1.1.2.10 /** Assigns <code>pseudoReg</code> to <code>regs</code> and
144 pnkfelix 1.1.2.10 <code>src</code>.
145 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <OL>
146 pnkfelix 1.1.2.1 <LI> <code>pseudoReg</code> does not currently have an
147 pnkfelix 1.1.2.1 assignment in <code>this</code>.
148 pnkfelix 1.1.2.1 </OL>
149 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>
150 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Creates an association between
151 pnkfelix 1.1.2.10 <code>pseudoReg</code> and <code>(regs, src)</code>.
152 pnkfelix 1.1.2.6 <BR> Note: Requirement 1 may seem strange, as its not
153 pnkfelix 1.1.2.6 strictly illegal in a compiler to assign a pseudo register
154 pnkfelix 1.1.2.6 multiple times to different machine registers.
155 pnkfelix 1.1.2.6 But the alternative would require making tmpToRegLst a
156 pnkfelix 1.1.2.6 MultiMap, the semantics of remove(pseudoReg)
157 pnkfelix 1.1.2.1 would have been ugly, and theres no place i know of where
158 pnkfelix 1.1.2.1 it would make sense to assign preg multiple times.
159 pnkfelix 1.1.2.1 */
160 pnkfelix 1.1.2.10 public void assign(final Temp pseudoReg, final List regs, Instr src) {
161 cananian 1.5 for (Object regO : regs) {
162 cananian 1.5 Temp reg = (Temp) regO;
163 pnkfelix 1.1.2.6
164 pnkfelix 1.1.2.8
165 cananian 1.3.2.1 assert !regToTmp.containsKey(reg) : ("non-empty reg: " /* +reg */);
166 pnkfelix 1.1.2.6
167 pnkfelix 1.1.2.8 regToTmp.put(reg, pseudoReg);
168 pnkfelix 1.1.2.8 // regToTmp.add(reg, pseudoReg); // use if mult. assoc.
169 pnkfelix 1.1.2.1 }
170 pnkfelix 1.1.2.10 RegListAndInstr rli = new RegListAndInstr(regs, src);
171 pnkfelix 1.1.2.1
172 pnkfelix 1.1.2.6 if (tmpToRegLst.containsKey(pseudoReg)) {
173 cananian 1.3.2.1 assert ((RegListAndInstr)tmpToRegLst.get
174 cananian 1.3.2.1 (pseudoReg)).l.equals(regs) : ((true)?"dont assign pregs > once":
175 pnkfelix 1.1.2.6 "dont assign preg:"+pseudoReg+" more than once \n"+
176 pnkfelix 1.1.2.6 "curr: "+tmpToRegLst.get(pseudoReg)+"\n"+
177 pnkfelix 1.1.2.10 "next: "+rli);
178 pnkfelix 1.1.2.6 }
179 cananian 1.3.2.1 assert !regs.isEmpty() : "regs should not be empty";
180 pnkfelix 1.1.2.10 tmpToRegLst.put(pseudoReg, rli);
181 pnkfelix 1.1.2.6
182 pnkfelix 1.1.2.6 if (PRINT_USAGE) System.out.println(this+".assign: "+regs+" <- "+pseudoReg);
183 pnkfelix 1.1.2.1 }
184 pnkfelix 1.1.2.1
185 pnkfelix 1.1.2.8 /** Checks if <code>reg</code> is currently holding a value in
186 pnkfelix 1.1.2.8 <code>this</code>. (Meant mainly for debugging, not for
187 pnkfelix 1.1.2.8 utility)
188 pnkfelix 1.1.2.8 */
189 pnkfelix 1.1.2.8 public boolean isEmpty(final Temp reg) {
190 pnkfelix 1.1.2.8 return !regToTmp.containsKey(reg);
191 pnkfelix 1.1.2.8 }
192 pnkfelix 1.1.2.8
193 pnkfelix 1.1.2.1 /** Checks if <code>pseudoReg</code> has an register assignment in
194 pnkfelix 1.1.2.1 <code>this</code>.
195 pnkfelix 1.1.2.1 <BR> <B>effects:</B> If <code>pseudoReg</code> currently maps
196 pnkfelix 1.1.2.1 to some <code>List</code> of registers in
197 pnkfelix 1.1.2.1 <code>this</code>, returns <code>true</code>.
198 pnkfelix 1.1.2.1 Else returns <code>false</code>.
199 pnkfelix 1.1.2.1 */
200 pnkfelix 1.1.2.1 public boolean hasAssignment(final Temp pseudoReg) {
201 pnkfelix 1.1.2.1 return tmpToRegLst.containsKey(pseudoReg);
202 pnkfelix 1.1.2.1 }
203 pnkfelix 1.1.2.1
204 pnkfelix 1.1.2.10 /** Returns the currently assigned register List for
205 pnkfelix 1.1.2.10 <code>pseudoReg</code>.
206 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>pseudoReg</code> current has an
207 pnkfelix 1.1.2.1 assignment in <code>this</code>.
208 pnkfelix 1.1.2.1 <BR> <B>effects:</B> Returns the <code>List</code> of register
209 pnkfelix 1.1.2.1 <code>Temp</code>s currently associated with
210 pnkfelix 1.1.2.1 <code>pseudoReg</code> in <code>this</code>.
211 pnkfelix 1.1.2.1 */
212 pnkfelix 1.1.2.1 public List getAssignment(final Temp pseudoReg) {
213 pnkfelix 1.1.2.10 return ((RegListAndInstr)tmpToRegLst.get(pseudoReg)).l;
214 pnkfelix 1.1.2.1 }
215 pnkfelix 1.1.2.10
216 pnkfelix 1.1.2.10 /** Returns the currently assigned Source for
217 pnkfelix 1.1.2.10 <code>pseudoReg</code>.
218 pnkfelix 1.1.2.10 <BR> <B>requires:</B> <code>pseudoReg</code> current has an
219 pnkfelix 1.1.2.10 assignment in <code>this</code>.
220 pnkfelix 1.1.2.10 <BR> <B>effects:</B> Returns the <code>Instr</code>
221 pnkfelix 1.1.2.10 currently associated with <code>pseudoReg</code> in
222 pnkfelix 1.1.2.10 <code>this</code>.
223 pnkfelix 1.1.2.10 */
224 pnkfelix 1.1.2.10 public Instr getSource(final Temp pseudoReg) {
225 pnkfelix 1.1.2.10 RegListAndInstr rli = (RegListAndInstr)
226 pnkfelix 1.1.2.10 tmpToRegLst.get(pseudoReg);
227 cananian 1.3.2.1 assert rli != null : (/* "Temp:"+pseudoReg+ */" has no assignment");
228 pnkfelix 1.1.2.10 return rli.i;
229 pnkfelix 1.1.2.10 }
230 pnkfelix 1.1.2.1
231 pnkfelix 1.1.2.1 /** Removes the assignment for <code>pseudoReg</code>.
232 pnkfelix 1.1.2.1 <BR> <B>requires:</B> <code>pseudoReg</code> currently has an
233 pnkfelix 1.1.2.1 assignment in <code>this</code>.
234 pnkfelix 1.1.2.1 <BR> <B>modifies:</B> <code>this</code>
235 pnkfelix 1.1.2.1 <BR> <B>effects:</B> removes all associations in
236 pnkfelix 1.1.2.1 <code>this</code> between <code>pseudoReg</code> and
237 pnkfelix 1.1.2.1 register <code>Temp</code>s.
238 pnkfelix 1.1.2.1 */
239 pnkfelix 1.1.2.1 public void remove(final Temp pseudoReg) {
240 pnkfelix 1.1.2.10 List regs = ((RegListAndInstr)tmpToRegLst.remove(pseudoReg)).l;
241 cananian 1.5 for (Object regO : regs) {
242 cananian 1.5 Temp reg = (Temp) regO;
243 pnkfelix 1.1.2.8 regToTmp.remove(reg);
244 pnkfelix 1.1.2.1 }
245 pnkfelix 1.1.2.2 dirtyTemps.remove(pseudoReg);
246 pnkfelix 1.1.2.6
247 pnkfelix 1.1.2.6 if (PRINT_USAGE) System.out.println(this+".remove: "+pseudoReg);
248 pnkfelix 1.1.2.1 }
249 cananian 1.2 }