1 cananian 1.1.2.1 /*
2 cananian 1.1.2.1 * RegAlloc/RegAlloc.java
3 cananian 1.1.2.1 * register allocator
4 cananian 1.1.2.1 *
5 cananian 1.1.2.1 * ALGORITHM: iterate coloring and spilling until no more
6 cananian 1.1.2.1 * temporaries are left to be spilled.
7 cananian 1.1.2.1 *
8 cananian 1.1.2.1 * C. Scott Ananian, cananian@princeton.edu, COS320
9 cananian 1.1.2.1 */
10 cananian 1.1.2.1
11 cananian 1.1.2.2 package harpoon.Backend.CSAHack.RegAlloc;
12 cananian 1.1.2.1
13 cananian 1.1.2.2 import harpoon.Backend.Generic.Frame;
14 cananian 1.1.2.1
15 cananian 1.1.2.4 import harpoon.Analysis.Maps.Derivation;
16 cananian 1.1.2.4
17 cananian 1.1.2.2 import harpoon.Backend.CSAHack.Graph.Node;
18 cananian 1.1.2.2 import harpoon.Backend.CSAHack.Graph.NodeList;
19 cananian 1.1.2.1
20 cananian 1.1.2.4 import harpoon.ClassFile.HCodeEdge;
21 cananian 1.1.2.4 import harpoon.ClassFile.HCodeElement;
22 cananian 1.1.2.4
23 cananian 1.1.2.2 import harpoon.IR.Assem.Instr;
24 cananian 1.1.2.2 import harpoon.IR.Assem.InstrMOVE;
25 cananian 1.1.2.4 import harpoon.IR.Properties.CFGrapher;
26 cananian 1.1.2.4 import harpoon.IR.Properties.UseDefer;
27 cananian 1.1.2.2
28 cananian 1.1.2.2 import harpoon.Temp.Temp;
29 cananian 1.1.2.2 import harpoon.Temp.TempList;
30 cananian 1.1.2.2 import harpoon.Temp.TempMap;
31 cananian 1.1.2.2
32 cananian 1.1.2.2 import harpoon.Backend.CSAHack.FlowGraph.AssemFlowGraph;
33 cananian 1.5 import net.cscott.jutil.GenericMultiMap;
34 cananian 1.5 import net.cscott.jutil.MultiMap;
35 cananian 1.5 import net.cscott.jutil.Environment;
36 cananian 1.5 import net.cscott.jutil.HashEnvironment;
37 cananian 1.1.2.2 import harpoon.Util.Util;
38 cananian 1.1.2.1
39 cananian 1.1.2.4 import java.util.ArrayList;
40 cananian 1.1.2.4 import java.util.Collection;
41 cananian 1.1.2.4 import java.util.HashSet;
42 cananian 1.1.2.4 import java.util.Iterator;
43 cananian 1.1.2.4 import java.util.Set;
44 cananian 1.1.2.1 /**
45 cananian 1.1.2.1 * Register allocation module.
46 cananian 1.1.2.1 * @version 1.00, 25 Nov 1996
47 cananian 1.1.2.1 * @author C. Scott Ananian
48 cananian 1.1.2.1 */
49 cananian 1.1.2.2 public class RegAlloc implements TempMap {
50 cananian 1.1.2.2 Frame frame;
51 cananian 1.1.2.2 Code code;
52 cananian 1.1.2.1 Color color;
53 cananian 1.1.2.1
54 cananian 1.1.2.1 /**
55 cananian 1.1.2.1 * A list of instructions that have been successfully allocated to
56 cananian 1.1.2.1 * registers (using the mapping defined by tempMap()).
57 cananian 1.1.2.1 * Instructions to spill variables may be added during the
58 cananian 1.1.2.1 * allocation process.
59 cananian 1.1.2.1 * Unnecessary moves may similarly be deleted.
60 cananian 1.1.2.1 */
61 cananian 1.1.2.5 Instr instrs; // this is the head of the list.
62 cananian 1.1.2.5 /** A derivation generator, or null. */
63 cananian 1.1.2.5 DerivationGenerator dg;
64 cananian 1.1.2.1
65 cananian 1.1.2.1 boolean debug = false; // enable debugging output.
66 cananian 1.1.2.6 static boolean quiet = false; // don't show progress
67 cananian 1.1.2.1
68 cananian 1.1.2.1
69 cananian 1.1.2.1 /**
70 cananian 1.1.2.1 * Allocate the temporaries defined and used in an Assem.InstrList to
71 cananian 1.1.2.2 * machine registers defined in a Frame.
72 cananian 1.1.2.1 * The resulting InstrList is placed in the instrs field of this class.
73 cananian 1.1.2.1 * @param f a machine-specific frame and register description
74 cananian 1.1.2.1 * @param il a list of instructions to be register allocated.
75 cananian 1.1.2.1 */
76 cananian 1.1.2.5 public RegAlloc(final Frame f, Code c, Instr root, DerivationGenerator dg) {
77 cananian 1.1.2.1 AssemFlowGraph flow;
78 cananian 1.1.2.5 UseDefer ud0 = UseDefer.DEFAULT;
79 cananian 1.1.2.1
80 cananian 1.1.2.1 frame = f;
81 cananian 1.1.2.2 code = c;
82 cananian 1.1.2.2 instrs = root;
83 cananian 1.1.2.5 this.dg = dg;
84 cananian 1.1.2.1
85 cananian 1.1.2.5 UseDefer ud = (dg==null) ? ud0 : new DerivedUseDefer(c, ud0);
86 cananian 1.1.2.4
87 cananian 1.1.2.3 // thunk the register array to a register list...
88 cananian 1.1.2.3 TempList registers=null;
89 cananian 1.1.2.3 Temp[] reg = f.getRegFileInfo().getAllRegisters();
90 cananian 1.1.2.3 for (int i=reg.length-1; i>=0; i--)
91 cananian 1.1.2.3 registers = new TempList(reg[i], registers);
92 cananian 1.1.2.3
93 cananian 1.1.2.1 // repeat these steps until no more variables need to be spilled:
94 cananian 1.1.2.6 if (!quiet) System.err.print("{");
95 cananian 1.1.2.1 do {
96 cananian 1.1.2.1 // create a flow graph
97 cananian 1.1.2.6 if (!quiet) System.err.print("F");
98 cananian 1.1.2.4 flow = new AssemFlowGraph(this.instrs, ud, true);
99 cananian 1.1.2.1 // create an interference graph after analyzing the flow for liveness.
100 cananian 1.1.2.6 if (!quiet) System.err.print("L");
101 cananian 1.1.2.1 Liveness live = new Liveness(flow);
102 cananian 1.1.2.1 // possibly dump these graphs for debugging.
103 cananian 1.1.2.1 if (debug) {
104 cananian 1.1.2.1 flow.show(System.err);
105 cananian 1.1.2.1 live.show(System.err);
106 cananian 1.1.2.1 }
107 cananian 1.1.2.1 // color the temporaries using the interference graph.
108 cananian 1.1.2.6 if (!quiet) System.err.print("C");
109 cananian 1.1.2.2 color = new Color(flow, live, new TempMap() {
110 cananian 1.1.2.2 public Temp tempMap(Temp t) {
111 cananian 1.3.2.1 assert f.getRegFileInfo().isRegister(t);
112 cananian 1.1.2.2 return t;
113 cananian 1.1.2.2 }
114 cananian 1.1.2.2 }, registers);
115 cananian 1.1.2.6 if (!quiet) System.err.print("S");
116 cananian 1.1.2.1 // rewrite program to spill temporaries, if necessary.
117 cananian 1.1.2.5 if (color.spills() != null) {
118 cananian 1.1.2.2 rewriteProgram(root, color.spills());
119 cananian 1.1.2.5 // re-create derived ptr use info.
120 cananian 1.1.2.5 if (dg!=null) ud = new DerivedUseDefer(c, ud0);
121 cananian 1.1.2.5 }
122 cananian 1.1.2.1 } while (color.spills() != null);
123 cananian 1.1.2.6 if (!quiet) System.err.print("}");
124 cananian 1.1.2.1
125 cananian 1.1.2.1 // trim redundant instructions.
126 cananian 1.1.2.1 instrs = trim(instrs);
127 cananian 1.1.2.1 }
128 cananian 1.1.2.1
129 cananian 1.1.2.1 // use the Spiller class to rewrite the program.
130 cananian 1.1.2.2 private void rewriteProgram(Instr root, TempList spilled) {
131 cananian 1.1.2.2 //throw new Error(root.getFactory().getMethod()+" needs "+color.spills()+" spilled.");
132 cananian 1.1.2.6 if (!quiet) {
133 cananian 1.1.2.6 int i=0; for (TempList tl=spilled; tl!=null; tl=tl.tail) i++;
134 cananian 1.1.2.6 System.err.print("("+i+")");
135 cananian 1.1.2.6 }
136 cananian 1.1.2.2 Spiller spiller = new Spiller(code, spilled);
137 cananian 1.1.2.1 instrs = spiller.rewrite(instrs);
138 cananian 1.1.2.1 }
139 cananian 1.1.2.1
140 cananian 1.1.2.1 // trim coalesced moves from the instruction list.
141 cananian 1.1.2.2 private Instr trim(Instr root) {
142 cananian 1.1.2.2 for (Instr il = root; il != null; ) {
143 cananian 1.1.2.2 if ((il instanceof InstrMOVE) &&
144 cananian 1.1.2.2 canBeCoalesced((InstrMOVE)il)) {
145 cananian 1.1.2.2 // delete coalesced move. (src=dst)
146 cananian 1.1.2.2 if (il == root) root = root.getNext();
147 cananian 1.1.2.2 il = il.getNext();
148 cananian 1.1.2.2 il.getPrev().remove();
149 cananian 1.1.2.2 } else il = il.getNext();
150 cananian 1.1.2.2 }
151 cananian 1.1.2.2 return root;
152 cananian 1.1.2.1 }
153 cananian 1.1.2.1
154 cananian 1.1.2.2 // check two moves for equality.
155 cananian 1.1.2.2 boolean canBeCoalesced(InstrMOVE instr) {
156 cananian 1.1.2.2 Temp[] u = (Temp[]) instr.use().clone();
157 cananian 1.1.2.2 for (int i=0; i<u.length; i++)
158 cananian 1.1.2.2 u[i] = tempMap(u[i]);
159 cananian 1.1.2.2 Temp[] d = (Temp[]) instr.def().clone();
160 cananian 1.1.2.2 for (int i=0; i<d.length; i++)
161 cananian 1.1.2.2 d[i] = tempMap(d[i]);
162 cananian 1.1.2.2 java.util.List ul =
163 cananian 1.1.2.2 java.util.Arrays.asList(u), dl = java.util.Arrays.asList(d);
164 cananian 1.1.2.2 return ul.containsAll(dl) && dl.containsAll(ul);
165 cananian 1.1.2.2 }
166 cananian 1.1.2.2
167 cananian 1.1.2.1 // the tempMap is the coloring defined in RegAlloc.Color
168 cananian 1.1.2.1 /**
169 cananian 1.1.2.1 * A mapping of temporaries to registers.
170 cananian 1.1.2.1 */
171 cananian 1.1.2.2 public Temp tempMap(Temp temp) {
172 cananian 1.1.2.1 return color.tempMap(temp);
173 cananian 1.1.2.4 }
174 cananian 1.1.2.4
175 cananian 1.1.2.4 private static class DerivedUseDefer extends UseDefer {
176 cananian 1.1.2.4 UseDefer ud;
177 cananian 1.1.2.4 MultiMap extras = new GenericMultiMap();
178 cananian 1.1.2.4 DerivedUseDefer(Code c, UseDefer ud) {
179 cananian 1.1.2.4 this.ud = ud;
180 cananian 1.1.2.4 if (c.getDerivation()==null) return; // no deriv info.
181 cananian 1.1.2.4
182 cananian 1.1.2.6 if (!quiet) System.err.print("[COMPUTING EXTRAS...");
183 cananian 1.1.2.4 // do a depth-first search of the CFG to determine (one of the)
184 cananian 1.1.2.4 // reaching definitions for each use.
185 cananian 1.1.2.4 CFGrapher cfg = CFGrapher.DEFAULT;
186 cananian 1.1.2.4 dfs(cfg.getFirstElement(c), cfg, c.getDerivation(),
187 cananian 1.1.2.4 new HashEnvironment(), new HashSet());
188 cananian 1.1.2.6 if (!quiet) System.err.print("done.]");
189 cananian 1.1.2.4 }
190 cananian 1.1.2.4 /** dfs of cfg to determine (a) reaching def for each use.
191 cananian 1.1.2.4 * current reaching defs are in 'env'. */
192 cananian 1.1.2.4 private void dfs(HCodeElement hce, CFGrapher cfg, Derivation deriv,
193 cananian 1.1.2.4 Environment env, Set seen) {
194 cananian 1.1.2.4 seen.add(hce); // keep track of touched hces.
195 cananian 1.1.2.4 // process *this*
196 cananian 1.1.2.4 // for all uses, use current reaching def to determine 'extras'
197 cananian 1.6 for (Object uO : ud.useC(hce)) {
198 cananian 1.6 Temp u = (Temp) uO;
199 cananian 1.1.2.4 HCodeElement def = (HCodeElement) env.get(u);
200 cananian 1.1.2.4 if (def==null) {
201 cananian 1.1.2.4 System.err.println("WARNING: no reaching def found for " + u +
202 cananian 1.1.2.4 " in " + hce);
203 cananian 1.1.2.4 continue;
204 cananian 1.1.2.4 }
205 cananian 1.1.2.4 for (Derivation.DList dl = deriv.derivation(def, u);
206 cananian 1.1.2.4 dl!=null; dl=dl.next)
207 cananian 1.1.2.4 extras.add(hce, dl.base);
208 cananian 1.1.2.4 }
209 cananian 1.1.2.4 // for all defs, update reaching def environment.
210 cananian 1.6 for (Object dO : ud.defC(hce)) {
211 cananian 1.6 Temp d = (Temp) dO;
212 cananian 1.1.2.4 env.put(d, hce);
213 cananian 1.1.2.4 }
214 cananian 1.1.2.4 // recurse
215 cananian 1.1.2.4 Environment.Mark mark = env.getMark();
216 cananian 1.1.2.4 for (Iterator it=cfg.succC(hce).iterator(); it.hasNext(); ) {
217 cananian 1.1.2.4 HCodeElement succ = ((HCodeEdge) it.next()).to();
218 cananian 1.1.2.4 if (seen.contains(succ)) continue;
219 cananian 1.1.2.4 dfs(succ, cfg, deriv, env, seen);
220 cananian 1.1.2.4 env.undoToMark(mark);
221 cananian 1.1.2.4 }
222 cananian 1.1.2.4 }
223 cananian 1.1.2.4
224 cananian 1.1.2.4 public Collection defC(HCodeElement hce) { return ud.defC(hce); }
225 cananian 1.1.2.4 // add base pointers for derived temps to use set.
226 cananian 1.1.2.4 public Collection useC(HCodeElement hce) {
227 cananian 1.1.2.4 Collection c = ud.useC(hce);
228 cananian 1.1.2.4 if (extras.containsKey(hce)) {
229 cananian 1.1.2.4 c = new ArrayList(c);
230 cananian 1.1.2.4 c.addAll(extras.getValues(hce));
231 cananian 1.1.2.4 }
232 cananian 1.1.2.4 return c;
233 cananian 1.1.2.4 }
234 cananian 1.1.2.1 }
235 cananian 1.2 }