1 cananian 1.1.2.12 // Code.java, created Tue Feb 16 22:25:11 1999 by andyb
2 andyb 1.1.2.1 // Copyright (C) 1999 Andrew Berkheimer <andyb@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.Generic;
5 andyb 1.1.2.1
6 pnkfelix 1.1.2.53 import harpoon.ClassFile.HCodeElement;
7 cananian 1.1.2.39 import harpoon.IR.Assem.Instr;
8 andyb 1.1.2.1 import harpoon.Temp.Temp;
9 pnkfelix 1.1.2.51 import harpoon.Temp.Label;
10 pnkfelix 1.1.2.8 import harpoon.Util.Util;
11 pnkfelix 1.1.2.43 import harpoon.Analysis.Maps.Derivation;
12 pnkfelix 1.1.2.34
13 pnkfelix 1.1.2.34 import java.util.Collection;
14 pnkfelix 1.1.2.34 import java.util.List;
15 andyb 1.1.2.1
16 andyb 1.1.2.1 /**
17 andyb 1.1.2.1 * <code>Generic.Code</code> is an abstract superclass of codeviews
18 andyb 1.1.2.1 * which use <code>Instr</code>s.
19 andyb 1.1.2.1 *
20 andyb 1.1.2.1 * @author Andrew Berkheimer <andyb@mit.edu>
21 cananian 1.5 * @version $Id: Code.java,v 1.5 2002/04/10 03:02:42 cananian Exp $
22 andyb 1.1.2.1 */
23 cananian 1.1.2.39 public abstract class Code extends harpoon.IR.Assem.Code {
24 pnkfelix 1.1.2.52
25 pnkfelix 1.1.2.52 public void printPreallocatedCode() {
26 pnkfelix 1.1.2.52 myPrint(new java.io.PrintWriter(System.out),false,true,new PrintCallback());
27 pnkfelix 1.1.2.53 }
28 pnkfelix 1.1.2.53 public void printPreallocatedCode(PrintCallback callback) {
29 pnkfelix 1.1.2.53 myPrint(new java.io.PrintWriter(System.out),false,true,callback);
30 pnkfelix 1.1.2.52 }
31 pnkfelix 1.1.2.44
32 pnkfelix 1.1.2.51 public static boolean PEEPHOLE_OPTIMIZATIONS = true;
33 pnkfelix 1.1.2.51
34 pnkfelix 1.1.2.44 private Derivation derivation;
35 pnkfelix 1.1.2.40
36 pnkfelix 1.1.2.40 /** Generates a new <code>Generic.Code</code> from
37 pnkfelix 1.1.2.40 another <code>Generic.Code</code>, <code>code</code>, with
38 pnkfelix 1.1.2.40 <code>i</code> as the root instruction (instead of whatever
39 pnkfelix 1.1.2.41 root was used in <code>code</code>, and <code>codeName</code>
40 pnkfelix 1.1.2.41 as the value that would be returned by a call
41 pnkfelix 1.1.2.41 <code>getName()</code>. (the codeName argument is a hack to
42 pnkfelix 1.1.2.41 get around a dependency problem in the constructor for
43 pnkfelix 1.1.2.41 <code>Assem.Code</code>.
44 pnkfelix 1.1.2.40 */
45 pnkfelix 1.1.2.44 protected Code(Code code, Instr i, Derivation d, String codeName) {
46 pnkfelix 1.1.2.41 super(code.getMethod(), code.getFrame(), codeName);
47 pnkfelix 1.1.2.40 this.instrs = i;
48 pnkfelix 1.1.2.44 this.derivation = d;
49 pnkfelix 1.1.2.40 }
50 andyb 1.1.2.1
51 cananian 1.1.2.38 protected Code(harpoon.IR.Tree.Code treeCode) {
52 cananian 1.1.2.39 super(treeCode.getMethod(), treeCode.getFrame());
53 pnkfelix 1.1.2.44 List pair = this.frame.getCodeGen().
54 pnkfelix 1.1.2.44 genCode(treeCode, this.inf);
55 pnkfelix 1.1.2.44 this.instrs = (Instr) pair.get(0);
56 pnkfelix 1.1.2.44 this.derivation = (Derivation) pair.get(1);
57 cananian 1.3.2.1 assert instrs != null;
58 cananian 1.3.2.1 assert derivation != null;
59 pnkfelix 1.1.2.44 }
60 pnkfelix 1.1.2.44
61 pnkfelix 1.1.2.44 public Derivation getDerivation() {
62 pnkfelix 1.1.2.44 return derivation;
63 pnkfelix 1.1.2.51 }
64 pnkfelix 1.1.2.51
65 pnkfelix 1.1.2.51 /** Returns false if <code>instr</code> cannot be safely deleted.
66 pnkfelix 1.1.2.51 <BR> <B>effects:</B> If it is safe to remove
67 pnkfelix 1.1.2.51 <code>instr</code> from <code>this</code> stream of
68 pnkfelix 1.1.2.51 instructions without changing the semantic meaning of the
69 pnkfelix 1.1.2.51 program, then this <b>might</b> return true.
70 pnkfelix 1.1.2.51 Otherwise, returns false.
71 pnkfelix 1.1.2.51 */
72 pnkfelix 1.1.2.51 public boolean isSafeToRemove(Instr instr) {
73 pnkfelix 1.1.2.51
74 pnkfelix 1.1.2.51 if (instr.isMove()) {
75 pnkfelix 1.1.2.51
76 pnkfelix 1.1.2.51 // Eliminate MOVEs where [src] = [dst]
77 cananian 1.3.2.1 assert instr.use().length == 1 : "moves have single use!";
78 cananian 1.3.2.1 assert instr.def().length == 1 : "moves have single def!";
79 pnkfelix 1.1.2.51 if (getRegisters(instr, instr.use()[0]). equals (getRegisters(instr, instr.def()[0]))) {
80 pnkfelix 1.1.2.51 return true;
81 pnkfelix 1.1.2.51 }
82 pnkfelix 1.1.2.51
83 pnkfelix 1.1.2.51
84 pnkfelix 1.1.2.51 } else if (instr.isJump()) {
85 pnkfelix 1.1.2.51
86 pnkfelix 1.1.2.51 // Eliminate JUMPs to immediate successor in layout
87 cananian 1.3.2.1 assert !instr.canFallThrough;
88 cananian 1.3.2.1 assert instr.getTargets().size() == 1;
89 pnkfelix 1.1.2.51 Label l = (Label) instr.getTargets().get(0);
90 pnkfelix 1.1.2.51 if (instr.getInstrFor(l).equals( instr.getNext() )) {
91 pnkfelix 1.1.2.51 return true;
92 pnkfelix 1.1.2.51 }
93 pnkfelix 1.1.2.51
94 pnkfelix 1.1.2.51 }
95 pnkfelix 1.1.2.51
96 pnkfelix 1.1.2.51
97 pnkfelix 1.1.2.51 return false;
98 pnkfelix 1.1.2.51 }
99 pnkfelix 1.1.2.51
100 pnkfelix 1.1.2.51 /** Overrides superclass implementation of toAssem to return an empty string if <code>instr</code>
101 pnkfelix 1.1.2.51 can be safely eliminated from output. */
102 pnkfelix 1.1.2.51 public String toAssem(Instr instr) {
103 pnkfelix 1.1.2.51 if (PEEPHOLE_OPTIMIZATIONS &&
104 pnkfelix 1.1.2.51 isSafeToRemove(instr)) {
105 pnkfelix 1.1.2.51
106 pnkfelix 1.1.2.51 return "";
107 pnkfelix 1.1.2.51
108 pnkfelix 1.1.2.51 } else {
109 pnkfelix 1.1.2.51
110 pnkfelix 1.1.2.51 return super.toAssem(instr);
111 pnkfelix 1.1.2.51
112 pnkfelix 1.1.2.51 }
113 andyb 1.1.2.1 }
114 pnkfelix 1.1.2.43
115 andyb 1.1.2.1 public abstract String getName();
116 pnkfelix 1.1.2.11
117 pnkfelix 1.1.2.33 /** Returns all of the Register <code>Temp</code>s that
118 pnkfelix 1.1.2.33 <code>val</code> maps to in <code>i</code>.
119 pnkfelix 1.1.2.33 <BR> <B>requires:</B> <OL>
120 pnkfelix 1.1.2.33 <LI> <code>val</code> must be a <code>Temp</code> that
121 pnkfelix 1.1.2.33 is an element of <code>i.defC()</code> or
122 pnkfelix 1.1.2.33 <code>i.useC()</code>
123 pnkfelix 1.1.2.50 <LI> (val is not Register for this architecture) =>
124 pnkfelix 1.1.2.50 <code>registerAssigned(i, val)</code> is true
125 pnkfelix 1.1.2.33 <BR> <B>effects:</B> Returns a <code>Collection</code> of the
126 pnkfelix 1.1.2.33 Register <code>Temp</code>s that are assigned to
127 pnkfelix 1.1.2.33 <code>val</code> in <code>i</code>. Every member of the
128 pnkfelix 1.1.2.33 <code>Collection</code> returned will be a valid Register
129 pnkfelix 1.1.2.33 for this architecture.
130 pnkfelix 1.1.2.33 */
131 pnkfelix 1.1.2.49 public abstract List getRegisters(Instr i, Temp val);
132 pnkfelix 1.1.2.11
133 pnkfelix 1.1.2.11 /** Assigns a register to a <code>Temp</code> in <code>i</code>.
134 pnkfelix 1.1.2.11 <BR> <B>modifies:</B> <code>i</code> (FSK: potentially at least)
135 pnkfelix 1.1.2.11 <BR> <B>effects:</B> creates a mapping
136 pnkfelix 1.1.2.11 <BR> NOTE: This is only an experimental method; only FSK
137 pnkfelix 1.1.2.11 should be using it until he makes sure that it implies no
138 pnkfelix 1.1.2.11 design flaws.
139 pnkfelix 1.1.2.26
140 pnkfelix 1.1.2.26 <P> FSK: Flaw 1 -- if there are multiple references to
141 pnkfelix 1.1.2.26 <code>pseudoReg</code> in <code>i</code>, like a := a + 1,
142 pnkfelix 1.1.2.26 then this method is too general; it does not allow us to put
143 pnkfelix 1.1.2.26 a's def in a different register from its use. Now, since
144 pnkfelix 1.1.2.26 we're using SSI form at a high level, I don't know if we'll
145 pnkfelix 1.1.2.26 ever encounter code like that (depends on how Tree->Instr form
146 pnkfelix 1.1.2.26 is performed), but
147 pnkfelix 1.1.2.26 <BR> (1.) I don't like <b>relying</b> on SSI to catch
148 pnkfelix 1.1.2.26 undocumented problems like this implicitly,
149 pnkfelix 1.1.2.26 <BR> (2.) we could, in theory, try to use this backend with a
150 pnkfelix 1.1.2.26 non-SSI front end
151 pnkfelix 1.1.2.26 <BR> The other issue here is I don't know when allowing the
152 pnkfelix 1.1.2.26 flexibility of having different registers for a's def and use
153 pnkfelix 1.1.2.48 will buy us anything...
154 pnkfelix 1.1.2.48 UPDATE: it does buy us something:
155 pnkfelix 1.1.2.48 since it allows for smaller webs w/o move instructions. we
156 pnkfelix 1.1.2.48 can get around this problem relatively cheaply by maintaining
157 cananian 1.4 not just a Instr x Temp -> List<Reg> mapping, but instead two
158 pnkfelix 1.1.2.48 mappings:
159 cananian 1.4 Instr x Use -> List<Reg>
160 cananian 1.4 Instr x Def -> List<Reg>.
161 pnkfelix 1.1.2.48 i will implement this after preliminary Global Register
162 pnkfelix 1.1.2.48 Allocation is working.
163 pnkfelix 1.1.2.48
164 pnkfelix 1.1.2.11 */
165 pnkfelix 1.1.2.45 public abstract void assignRegister(Instr i,
166 pnkfelix 1.1.2.28 Temp pseudoReg,
167 pnkfelix 1.1.2.28 List regs);
168 pnkfelix 1.1.2.28
169 pnkfelix 1.1.2.33 /** Checks if <code>pseudoReg</code> has been assigned to some
170 pnkfelix 1.1.2.33 registers in <code>i</code>.
171 pnkfelix 1.1.2.33 <BR> <B>requires:</B>
172 pnkfelix 1.1.2.33 <code>val</code> must be a <code>Temp</code> that
173 pnkfelix 1.1.2.33 is an element of <code>i.defC()</code> or
174 pnkfelix 1.1.2.33 <code>i.useC()</code>
175 pnkfelix 1.1.2.33 <BR> <B>effects:</B>
176 pnkfelix 1.1.2.33 If <code>pseudoReg</code> has been assigned
177 pnkfelix 1.1.2.33 to some <code>List</code> of registers in <code>i</code>
178 pnkfelix 1.1.2.33 and <code>removeAssignment(i, pseudoReg)</code> has not
179 pnkfelix 1.1.2.33 been called since, returns <code>true</code>.
180 pnkfelix 1.1.2.33 Else returns <code>false</code>.
181 pnkfelix 1.1.2.33 */
182 pnkfelix 1.1.2.28 public abstract boolean registerAssigned(Instr i, Temp pseudoReg);
183 pnkfelix 1.1.2.29
184 pnkfelix 1.1.2.29 public void removeAssignment(Instr i, Temp pseudoReg) {
185 cananian 1.3.2.1 assert false : "override and implement Code.removeAssignment"+
186 pnkfelix 1.1.2.29 " (which should be abstract but since its an "+
187 pnkfelix 1.1.2.29 "experimental method I don't want have add it "+
188 cananian 1.3.2.1 "to all the other code yet)";
189 pnkfelix 1.1.2.29 }
190 pnkfelix 1.1.2.8
191 cananian 1.2 }