1 pnkfelix 1.1.2.5 // Code.java, created Fri Jul 30 13:41:35 1999 by pnkfelix
2 pnkfelix 1.1.2.5 // Copyright (C) 1999 Felix S. Klock II <pnkfelix@mit.edu>
3 andyb 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 andyb 1.1.2.1 package harpoon.Backend.StrongARM;
5 andyb 1.1.2.1
6 pnkfelix 1.1.2.5 import harpoon.IR.Tree.CanonicalTreeCode;
7 pnkfelix 1.1.2.5 import harpoon.IR.Assem.Instr;
8 pnkfelix 1.1.2.5 import harpoon.Analysis.Instr.TempInstrPair;
9 pnkfelix 1.1.2.5 import harpoon.Backend.Generic.Frame;
10 andyb 1.1.2.1 import harpoon.ClassFile.HCode;
11 andyb 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
12 pnkfelix 1.1.2.5 import harpoon.ClassFile.HMethod;
13 andyb 1.1.2.1 import harpoon.Temp.Temp;
14 andyb 1.1.2.1
15 pnkfelix 1.1.2.5 import java.util.List;
16 pnkfelix 1.1.2.5 import java.util.HashMap;
17 pnkfelix 1.1.2.21 import java.util.Iterator;
18 pnkfelix 1.1.2.5 import java.util.Map;
19 pnkfelix 1.1.2.14 import java.util.Arrays;
20 pnkfelix 1.1.2.14 import java.util.Collections;
21 pnkfelix 1.1.2.14 import java.util.Collection;
22 pnkfelix 1.1.2.14 import java.util.Set;
23 pnkfelix 1.1.2.14 import java.util.HashSet;
24 andyb 1.1.2.1
25 cananian 1.5 import net.cscott.jutil.Util;
26 andyb 1.1.2.1 /**
27 pnkfelix 1.1.2.5 * <code>Code</code> is a code-view for StrongARM assembly.
28 pnkfelix 1.1.2.5 *
29 pnkfelix 1.1.2.5 * @author Felix S. Klock II <pnkfelix@mit.edu>
30 cananian 1.6 * @version $Id: Code.java,v 1.6 2004/02/08 03:21:04 cananian Exp $
31 andyb 1.1.2.1 */
32 cananian 1.1.2.23 class Code extends harpoon.Backend.Generic.Code {
33 andyb 1.1.2.1 public static final String codename = "strongarm";
34 andyb 1.1.2.1
35 pnkfelix 1.1.2.14 private static final boolean DEBUG = false;
36 pnkfelix 1.1.2.14
37 pnkfelix 1.1.2.21 private Map tempInstrToRegisterMap;
38 pnkfelix 1.1.2.21 private RegFileInfo regFileInfo;
39 andyb 1.1.2.3
40 pnkfelix 1.1.2.5 /** Creates a <code>Code</code>. */
41 pnkfelix 1.1.2.5 public Code(harpoon.IR.Tree.Code treeCode) {
42 cananian 1.1.2.18 super(treeCode);
43 pnkfelix 1.1.2.13
44 pnkfelix 1.1.2.13 // need to cast the return type to a StrongARM.RegFileInfo
45 cananian 1.1.2.18 regFileInfo = (RegFileInfo) this.frame.getRegFileInfo();
46 cananian 1.3.2.1 assert regFileInfo != null : "Need non-null regfileinfo";
47 pnkfelix 1.1.2.13
48 pnkfelix 1.1.2.13 tempInstrToRegisterMap = new HashMap();
49 pnkfelix 1.1.2.5 }
50 andyb 1.1.2.1
51 andyb 1.1.2.1 public String getName() { return codename; }
52 andyb 1.1.2.1
53 pnkfelix 1.1.2.5 /**
54 pnkfelix 1.1.2.5 * Returns a code factory for <code>Code</code>, given a
55 pnkfelix 1.1.2.5 * code factory for <code>CanonicalTreeCode</code>.
56 pnkfelix 1.1.2.5 * <BR> <B>effects:</B> if <code>hcf</code> is a code factory for
57 pnkfelix 1.1.2.5 * <code>CanonicalTreeCode</code>, then creates and returns a code
58 pnkfelix 1.1.2.5 * factory for <code>Code</code>. Else passes
59 pnkfelix 1.1.2.5 * <code>hcf</code> to
60 pnkfelix 1.1.2.5 * <code>CanonicalTreeCode.codeFactory()</code>, and reattempts to
61 pnkfelix 1.1.2.5 * create a code factory for <code>Code</code> from the
62 pnkfelix 1.1.2.5 * code factory returned by <code>CanonicalTreeCode</code>.
63 pnkfelix 1.1.2.5 * @see CanonicalTreeCode#codeFactory(HCodeFactory, Frame)
64 pnkfelix 1.1.2.5 */
65 pnkfelix 1.1.2.5 public static HCodeFactory codeFactory(final HCodeFactory hcf,
66 pnkfelix 1.1.2.5 final Frame frame) {
67 pnkfelix 1.1.2.5 if(hcf.getCodeName().equals(CanonicalTreeCode.codename)){
68 pnkfelix 1.1.2.5 return new HCodeFactory() {
69 pnkfelix 1.1.2.5 public HCode convert(HMethod m) {
70 pnkfelix 1.1.2.5 harpoon.IR.Tree.Code tc =
71 pnkfelix 1.1.2.5 (harpoon.IR.Tree.Code) hcf.convert(m);
72 pnkfelix 1.1.2.5 return (tc == null) ? null : new Code(tc);
73 pnkfelix 1.1.2.5 }
74 pnkfelix 1.1.2.5 public void clear(HMethod m) { hcf.clear(m); }
75 pnkfelix 1.1.2.5 public String getCodeName() { return codename; }
76 pnkfelix 1.1.2.5 };
77 pnkfelix 1.1.2.5 } else {
78 pnkfelix 1.1.2.5 // recursion can be ugly some times.
79 pnkfelix 1.1.2.5 return codeFactory(CanonicalTreeCode.
80 pnkfelix 1.1.2.5 codeFactory(hcf, frame), frame);
81 pnkfelix 1.1.2.5 }
82 pnkfelix 1.1.2.5 }
83 pnkfelix 1.1.2.5
84 pnkfelix 1.1.2.27 public List getRegisters(Instr i, Temp val) {
85 cananian 1.3.2.1 assert i != null : "Code.getRegisters(null, Temp) undefined";
86 pnkfelix 1.1.2.14 if (val instanceof TwoWordTemp) {
87 pnkfelix 1.1.2.14 TwoWordTemp t = (TwoWordTemp) val;
88 pnkfelix 1.1.2.14 Temp low = get(i, t.getLow());
89 pnkfelix 1.1.2.14 Temp high = get(i, t.getHigh());
90 cananian 1.3.2.1 assert low != null : ((true)?"low reg is null"
91 pnkfelix 1.1.2.24 : "low register for "+val+" in "+i+
92 pnkfelix 1.1.2.24 " should not be null");
93 cananian 1.3.2.1 assert high != null : ((true)?"high reg is null"
94 pnkfelix 1.1.2.24 : "high register for "+val+" in "+i+
95 pnkfelix 1.1.2.24 " should not be null");
96 pnkfelix 1.1.2.14 return Arrays.asList(new Temp[]{ low, high });
97 pnkfelix 1.1.2.14
98 pnkfelix 1.1.2.14 } else {
99 pnkfelix 1.1.2.28 Temp t;
100 pnkfelix 1.1.2.28 if ( regFileInfo.isRegister(val) ) {
101 pnkfelix 1.1.2.28 t = val;
102 pnkfelix 1.1.2.28 } else {
103 pnkfelix 1.1.2.28 t = get(i, val);
104 cananian 1.3.2.1 assert t != null : "register for "+val+" in "+i+
105 cananian 1.3.2.1 " should not be null";
106 pnkfelix 1.1.2.28 }
107 pnkfelix 1.1.2.27 return Collections.nCopies(1, t);
108 pnkfelix 1.1.2.14 }
109 pnkfelix 1.1.2.14 }
110 pnkfelix 1.1.2.14
111 pnkfelix 1.1.2.13 /** This returns null or a register temp. */
112 pnkfelix 1.1.2.5 private Temp get(Instr instr, Temp val) {
113 pnkfelix 1.1.2.13 Temp reg =
114 pnkfelix 1.1.2.13 (Temp) tempInstrToRegisterMap.get
115 pnkfelix 1.1.2.13 (new TempInstrPair(instr, val));
116 pnkfelix 1.1.2.13 if(reg == null) return null;
117 cananian 1.3.2.1 assert regFileInfo.isRegister(reg) : ((true)?"should be a reg"
118 pnkfelix 1.1.2.24 : "Temp: "+reg+" should be a reg in "+
119 pnkfelix 1.1.2.24 "Instr: "+instr+", Val: "+val);
120 pnkfelix 1.1.2.13 return reg;
121 andyb 1.1.2.1 }
122 andyb 1.1.2.1
123 pnkfelix 1.1.2.5
124 pnkfelix 1.1.2.20 public String getRegisterName(final Instr instr,
125 pnkfelix 1.1.2.5 final Temp val,
126 pnkfelix 1.1.2.5 final String suffix) {
127 pnkfelix 1.1.2.5 String s=null;
128 pnkfelix 1.1.2.5 if (val instanceof TwoWordTemp) {
129 pnkfelix 1.1.2.5 // parse suffix
130 pnkfelix 1.1.2.5 TwoWordTemp t = (TwoWordTemp) val;
131 pnkfelix 1.1.2.5 Temp reg = null;
132 pnkfelix 1.1.2.5 if (suffix.startsWith("l")) {
133 pnkfelix 1.1.2.5 // low
134 pnkfelix 1.1.2.5 reg = get(instr, t.getLow());
135 pnkfelix 1.1.2.5 } else if (suffix.startsWith("h")) {
136 pnkfelix 1.1.2.5 // high
137 pnkfelix 1.1.2.5 reg = get(instr, t.getHigh());
138 pnkfelix 1.1.2.7 } else if (suffix.trim().equals("")) {
139 pnkfelix 1.1.2.22 if (true) return "TW"+val;
140 cananian 1.3.2.1 assert false : ("BREAK! empty suffix " +
141 pnkfelix 1.1.2.9 "suffix: " + suffix + "\n" +
142 pnkfelix 1.1.2.9 "instr: " + instr + "\n" +
143 pnkfelix 1.1.2.14 "instr str: " + instr.getAssem() + "\n"+
144 pnkfelix 1.1.2.9 "temp: " + val);
145 pnkfelix 1.1.2.5 } else {
146 cananian 1.3.2.1 assert false : "BREAK! This parsing needs to be "+
147 cananian 1.1.2.6 "fixed, strongarm has a lot more cases than this."+
148 pnkfelix 1.1.2.7 "\n suffix: "+ suffix + "\n" +
149 cananian 1.1.2.6 "Alternatively, the pattern could be trying to "+
150 cananian 1.1.2.6 "use a TwoWordTemp without the appropriate "+
151 cananian 1.3.2.1 "double word modifier (l, h) in " + instr;
152 pnkfelix 1.1.2.5 }
153 pnkfelix 1.1.2.5 if(reg != null) {
154 pnkfelix 1.1.2.5 s = reg.name() + suffix.substring(1);
155 pnkfelix 1.1.2.5 } else {
156 pnkfelix 1.1.2.5 s = val.name() + suffix;
157 pnkfelix 1.1.2.5 }
158 pnkfelix 1.1.2.5 } else { // single word; nothing special
159 pnkfelix 1.1.2.5 Temp reg = get(instr, val);
160 pnkfelix 1.1.2.5
161 cananian 1.3.2.1 assert !suffix.startsWith("l") &&
162 cananian 1.3.2.1 !suffix.startsWith("h") : (true) ? "suffix not allowed "
163 pnkfelix 1.1.2.24 : "Shouldn't " +
164 pnkfelix 1.1.2.24 "have 'l' or 'h' suffix with Temp: " +
165 pnkfelix 1.1.2.24 val + " Instrs: " +
166 pnkfelix 1.1.2.24 instr.getPrev() + ", " +
167 pnkfelix 1.1.2.24 instr + ", " +
168 cananian 1.3.2.1 instr.getNext();
169 pnkfelix 1.1.2.5
170 pnkfelix 1.1.2.5 if(reg != null) {
171 pnkfelix 1.1.2.5 s = reg.name() + suffix;
172 pnkfelix 1.1.2.5 } else {
173 pnkfelix 1.1.2.5 s = val.name() + suffix;
174 pnkfelix 1.1.2.5 }
175 pnkfelix 1.1.2.5 }
176 cananian 1.3.2.1 // assert s.indexOf("r0l") == -1 && s.indexOf("r0h") == -1 &&
177 cananian 1.3.2.1 // s.indexOf("r1l") == -1 && s.indexOf("r1h") == -1 : // "Improper parsing of " + suffix + " in " + instr + " " + val.getClass().getName();
178 pnkfelix 1.1.2.5
179 pnkfelix 1.1.2.5 return s;
180 pnkfelix 1.1.2.5 }
181 pnkfelix 1.1.2.5
182 pnkfelix 1.1.2.14
183 pnkfelix 1.1.2.14 // overriding superclass implementation to add
184 pnkfelix 1.1.2.14 // architecture-dependant assertions (in an effort to fail-fast)
185 cananian 1.1.2.19 public String toAssem(Instr instr) {
186 pnkfelix 1.1.2.14 if (DEBUG) {
187 pnkfelix 1.1.2.14 // these constraint checks may be flawed; I'm getting
188 pnkfelix 1.1.2.14 // assertion failures on good code, i think...
189 pnkfelix 1.1.2.14
190 pnkfelix 1.1.2.14 // check that constants are all contained in eight-bit chunks
191 pnkfelix 1.1.2.14 String assem = instr.getAssem();
192 pnkfelix 1.1.2.14 int begin = assem.lastIndexOf('#');
193 pnkfelix 1.1.2.14
194 pnkfelix 1.1.2.14
195 pnkfelix 1.1.2.14 if (begin != -1) {
196 pnkfelix 1.1.2.14 int end = assem.length();
197 pnkfelix 1.1.2.14 final char[] endChars = new char[]{ '\n', '@', ']', ' '};
198 pnkfelix 1.1.2.14 for(int i=0; i<endChars.length; i++) {
199 pnkfelix 1.1.2.14 int e = assem.lastIndexOf(endChars[i], end);
200 pnkfelix 1.1.2.14 if (e > begin) end = e;
201 pnkfelix 1.1.2.14 // System.out.println(assem.substring(begin+1, end));
202 pnkfelix 1.1.2.14 }
203 pnkfelix 1.1.2.14
204 pnkfelix 1.1.2.14 String constStr = assem.substring(begin+1, end);
205 pnkfelix 1.1.2.14 int v = 0;
206 pnkfelix 1.1.2.14 try {
207 pnkfelix 1.1.2.14 v = Integer.parseInt(constStr);
208 pnkfelix 1.1.2.14 } catch (NumberFormatException e) {
209 pnkfelix 1.1.2.14 System.out.println("bad const extraction");
210 pnkfelix 1.1.2.14 System.out.println("\'"+constStr+"\'");
211 pnkfelix 1.1.2.14 System.out.println(" from "+instr+"("+begin+","+end+")");
212 cananian 1.3.2.1 assert false;
213 pnkfelix 1.1.2.14 }
214 pnkfelix 1.1.2.14
215 cananian 1.3.2.1 assert isValidConst(v) || isValidConst(-v) : true?"const form err"
216 pnkfelix 1.1.2.24 : "const form err of "+v+" in "+
217 cananian 1.3.2.1 instr+"("+begin+","+end+")";
218 pnkfelix 1.1.2.14 }
219 pnkfelix 1.1.2.15 } // end if(DEBUG)
220 pnkfelix 1.1.2.15
221 cananian 1.1.2.19 return super.toAssem(instr);
222 pnkfelix 1.1.2.14 }
223 pnkfelix 1.1.2.14
224 pnkfelix 1.1.2.14 public static boolean isValidConst(final int val) {
225 pnkfelix 1.1.2.14 // FSK: stealing code from CSA again...
226 pnkfelix 1.1.2.14 int v;
227 pnkfelix 1.1.2.14 int r;
228 pnkfelix 1.1.2.14
229 pnkfelix 1.1.2.14 v = val;
230 pnkfelix 1.1.2.14 r=0;
231 pnkfelix 1.1.2.14 for ( ; v!=0; r++)
232 pnkfelix 1.1.2.14 v &= ~(0xFF << ((Util.ffs(v)-1) & ~1));
233 pnkfelix 1.1.2.14 return (r <= 1) ;
234 pnkfelix 1.1.2.14 }
235 pnkfelix 1.1.2.14
236 pnkfelix 1.1.2.25 // runs once / ref / instr
237 pnkfelix 1.1.2.5 /** Assigns register(s) to the <code>Temp</code> pseudoReg.
238 pnkfelix 1.1.2.5 <BR><B>requires:</B> <code>regs</code> is one of the
239 pnkfelix 1.1.2.5 <code>List</code>s returned by
240 pnkfelix 1.1.2.5 <code>SAFrame.suggestRegAssignment()</code> for
241 pnkfelix 1.1.2.5 <code>pseudoReg</code>.
242 pnkfelix 1.1.2.5 <BR><B>effects:</B> Associates the register <code>Temp</code>s
243 pnkfelix 1.1.2.5 in <code>regs</code> with (<code>instr</code> x
244 pnkfelix 1.1.2.5 <code>pseudoReg</code>) in such a manner that
245 pnkfelix 1.1.2.5 <code>getRegisterName(instr, psuedoReg, suffix)</code>
246 pnkfelix 1.1.2.5 will return the name associated with the appropriate
247 pnkfelix 1.1.2.5 register in <code>regs</code>.
248 pnkfelix 1.1.2.5 */
249 pnkfelix 1.1.2.5 public void assignRegister(final Instr instr,
250 pnkfelix 1.1.2.5 final Temp pseudoReg,
251 pnkfelix 1.1.2.5 final List regs) {
252 cananian 1.6 for (Object tO : regs) {
253 cananian 1.6 Temp t = (Temp) tO;
254 cananian 1.3.2.2 assert regFileInfo.isRegister(t)
255 cananian 1.3.2.2 : "every element of "+regs+" should be register, but "+t+
256 cananian 1.3.2.2 "is not.";
257 pnkfelix 1.1.2.21 }
258 pnkfelix 1.1.2.21
259 pnkfelix 1.1.2.5 if (pseudoReg instanceof TwoWordTemp) {
260 pnkfelix 1.1.2.5 TwoWordTemp t = (TwoWordTemp) pseudoReg;
261 cananian 1.3.2.1 assert regs.size() == 2 : "wrong reg assignment";
262 pnkfelix 1.1.2.13 tempInstrToRegisterMap.put
263 pnkfelix 1.1.2.5 (new TempInstrPair(instr, t.getLow()), regs.get(0));
264 pnkfelix 1.1.2.13 tempInstrToRegisterMap.put
265 pnkfelix 1.1.2.5 (new TempInstrPair(instr, t.getHigh()), regs.get(1));
266 pnkfelix 1.1.2.5 } else {
267 cananian 1.3.2.1 assert regs.size() == 1 : "wrong reg assignment";
268 pnkfelix 1.1.2.13 tempInstrToRegisterMap.put
269 pnkfelix 1.1.2.5 (new TempInstrPair(instr, pseudoReg), regs.get(0));
270 pnkfelix 1.1.2.10 }
271 pnkfelix 1.1.2.11
272 pnkfelix 1.1.2.11 // Register Constraint check
273 pnkfelix 1.1.2.25 if (DEBUG &&
274 pnkfelix 1.1.2.25 ((instr.getAssem().indexOf("mul ") != -1) ||
275 pnkfelix 1.1.2.25 (instr.getAssem().indexOf("mla ") != -1))) {
276 pnkfelix 1.1.2.12 Object rm = get(instr, instr.use()[0]);
277 pnkfelix 1.1.2.12 Object rd = get(instr, instr.def()[0]);
278 cananian 1.3.2.1 assert rm == null || !rm.equals(rd) : ("rd:"+rd+" and rm:"+rm+" must be different in mul");
279 pnkfelix 1.1.2.11 }
280 pnkfelix 1.1.2.10 }
281 pnkfelix 1.1.2.12
282 pnkfelix 1.1.2.12 public void removeAssignment(Instr instr, Temp preg) {
283 pnkfelix 1.1.2.12 if (preg instanceof TwoWordTemp) {
284 pnkfelix 1.1.2.12 TwoWordTemp t = (TwoWordTemp) preg;
285 pnkfelix 1.1.2.13 tempInstrToRegisterMap.remove
286 pnkfelix 1.1.2.12 (new TempInstrPair(instr, t.getLow()));
287 pnkfelix 1.1.2.13 tempInstrToRegisterMap.remove
288 pnkfelix 1.1.2.12 (new TempInstrPair(instr, t.getHigh()));
289 pnkfelix 1.1.2.12 } else {
290 pnkfelix 1.1.2.13 tempInstrToRegisterMap.remove
291 pnkfelix 1.1.2.12 (new TempInstrPair(instr, preg));
292 pnkfelix 1.1.2.12 }
293 pnkfelix 1.1.2.12 }
294 pnkfelix 1.1.2.12
295 pnkfelix 1.1.2.10
296 pnkfelix 1.1.2.10 public boolean registerAssigned(Instr instr, Temp pr) {
297 pnkfelix 1.1.2.10 if (pr instanceof TwoWordTemp) {
298 pnkfelix 1.1.2.10 TwoWordTemp t = (TwoWordTemp) pr;
299 pnkfelix 1.1.2.10 return
300 pnkfelix 1.1.2.13 (tempInstrToRegisterMap.
301 pnkfelix 1.1.2.10 keySet().contains
302 pnkfelix 1.1.2.10 (new TempInstrPair(instr, t.getLow()))
303 pnkfelix 1.1.2.10 &&
304 pnkfelix 1.1.2.13 tempInstrToRegisterMap.
305 pnkfelix 1.1.2.10 keySet().contains
306 pnkfelix 1.1.2.10 (new TempInstrPair(instr, t.getHigh())));
307 pnkfelix 1.1.2.10 } else {
308 pnkfelix 1.1.2.10 return
309 pnkfelix 1.1.2.13 (tempInstrToRegisterMap.
310 pnkfelix 1.1.2.10 keySet().contains
311 pnkfelix 1.1.2.10 (new TempInstrPair(instr, pr)));
312 pnkfelix 1.1.2.5 }
313 andyb 1.1.2.1 }
314 cananian 1.2 }