1 cananian 1.1.2.1 /*
2 cananian 1.1.2.1 * RegAlloc/Spiller.java
3 cananian 1.1.2.1 * rewrite instruction list to spill overflow temporaries.
4 cananian 1.1.2.1 *
5 cananian 1.1.2.1 * C. Scott Ananian, cananian@princeton.edu, COS320
6 cananian 1.1.2.1 */
7 cananian 1.1.2.1
8 cananian 1.1.2.2 package harpoon.Backend.CSAHack.RegAlloc;
9 cananian 1.1.2.1
10 cananian 1.1.2.3 import harpoon.Backend.StrongARM.TwoWordTemp;
11 cananian 1.1.2.3
12 cananian 1.1.2.2 import harpoon.Backend.Generic.Frame;
13 cananian 1.1.2.2 import harpoon.Backend.CSAHack.RegAlloc.Code.Access;
14 cananian 1.1.2.2 import harpoon.IR.Assem.Instr;
15 duncan 1.1.2.4 import harpoon.IR.Properties.CFGEdge;
16 cananian 1.1.2.2 import harpoon.Backend.CSAHack.Graph.NodeList;
17 cananian 1.1.2.2 import harpoon.Temp.Temp;
18 cananian 1.1.2.2 import harpoon.Temp.TempList;
19 cananian 1.1.2.3 import harpoon.Temp.TempMap;
20 cananian 1.1.2.2
21 cananian 1.1.2.2 import java.util.HashMap;
22 cananian 1.1.2.2 import java.util.HashSet;
23 cananian 1.1.2.2 import java.util.Iterator;
24 cananian 1.1.2.2 import java.util.Map;
25 cananian 1.1.2.2 import java.util.Set;
26 cananian 1.1.2.1
27 cananian 1.1.2.1 /**
28 cananian 1.1.2.1 * Rewrite instruction list to spill overflowing temporaries to the
29 cananian 1.1.2.1 * local frame.
30 cananian 1.1.2.1 * @version 1.00, 25 Nov 1996
31 cananian 1.1.2.1 * @author C. Scott Ananian
32 cananian 1.1.2.1 * @see RegAlloc.RegAlloc
33 cananian 1.1.2.1 */
34 cananian 1.1.2.6 // XXX SPILLER SHOUD USE code.dg TO UPDATE DERIVATION WHILE IT SPILLS!
35 cananian 1.1.2.1 class Spiller {
36 cananian 1.1.2.2 Code code;
37 cananian 1.1.2.2 Map spills;
38 cananian 1.1.2.1
39 cananian 1.1.2.2 Spiller(Code c, TempList spilled) {
40 cananian 1.1.2.2 this.code = c;
41 cananian 1.1.2.1 // make an array of temporaries that need to be spilled
42 cananian 1.1.2.1 // and allocate each of them some space in the frame.
43 cananian 1.1.2.2 spills = new HashMap();
44 cananian 1.1.2.2 for (int i=0; spilled!=null; spilled=spilled.tail, i++)
45 cananian 1.1.2.2 spills.put(spilled.head, c.allocLocal());
46 cananian 1.1.2.1 }
47 cananian 1.1.2.1 // rewrite an instruction list.
48 cananian 1.1.2.2 Instr rewrite(Instr instrs) {
49 cananian 1.1.2.3 final Map usespill = new HashMap(), defspill=new HashMap();
50 cananian 1.1.2.3 Set instrsToSkip = new HashSet();
51 cananian 1.1.2.2 for (Instr il=instrs; il!=null; il=il.getNext()) {
52 cananian 1.1.2.3 if (instrsToSkip.contains(il)) continue;
53 cananian 1.1.2.3 // find USE and DEFs of spilltemps.
54 cananian 1.1.2.3 Temp d[] = il.def();
55 cananian 1.1.2.3 for (int i=0; i<d.length; i++) {
56 cananian 1.1.2.3 if (d[i] instanceof TwoWordTemp) {
57 cananian 1.1.2.3 // can't rename twowordtemps so just insert the pieces as themselves.
58 cananian 1.1.2.3 Temp low = ((TwoWordTemp)d[i]).getLow();
59 cananian 1.1.2.3 Temp high= ((TwoWordTemp)d[i]).getHigh();
60 cananian 1.1.2.3 if (spills.containsKey(low) &&
61 cananian 1.1.2.3 il.getAssem().indexOf("`d"+i+"l")!=-1) defspill.put(low, low);
62 cananian 1.1.2.3 if (spills.containsKey(high) &&
63 cananian 1.1.2.3 il.getAssem().indexOf("`d"+i+"h")!=-1) defspill.put(high, high);
64 cananian 1.1.2.3 } else if (spills.containsKey(d[i]) && !defspill.containsKey(d[i]))
65 cananian 1.1.2.3 defspill.put(d[i], new Temp(il.getFactory().tempFactory()));
66 cananian 1.1.2.3 }
67 cananian 1.1.2.3 Temp u[] = il.use();
68 cananian 1.1.2.3 for (int i=0; i<u.length; i++) {
69 cananian 1.1.2.3 if (u[i] instanceof TwoWordTemp) {
70 cananian 1.1.2.3 Temp low = ((TwoWordTemp)u[i]).getLow();
71 cananian 1.1.2.3 Temp high= ((TwoWordTemp)u[i]).getHigh();
72 cananian 1.1.2.3 // can't rename twowordtemps so just insert the pieces as themselves.
73 cananian 1.1.2.3 if (spills.containsKey(low) &&
74 cananian 1.1.2.3 il.getAssem().indexOf("`s"+i+"l")!=-1) usespill.put(low, low);
75 cananian 1.1.2.3 if (spills.containsKey(high) &&
76 cananian 1.1.2.3 il.getAssem().indexOf("`s"+i+"h")!=-1) usespill.put(high, high);
77 cananian 1.1.2.3 } else if (spills.containsKey(u[i]) && !usespill.containsKey(u[i]))
78 cananian 1.1.2.3 usespill.put(u[i], new Temp(il.getFactory().tempFactory()));
79 cananian 1.1.2.2 }
80 cananian 1.1.2.3 // if no uses or defs of spilltemps, continue.
81 cananian 1.1.2.3 if (defspill.size()==0 && usespill.size()==0) continue;
82 cananian 1.1.2.3 // okay, rename the original instr with the new limited-lifespan temps.
83 cananian 1.1.2.5 TempMap defMap = new TempMap() { // defmap
84 cananian 1.1.2.3 public Temp tempMap(Temp t) {
85 cananian 1.1.2.3 return defspill.containsKey(t) ? (Temp)defspill.get(t) : t;
86 cananian 1.1.2.3 }
87 cananian 1.1.2.5 }, useMap = new TempMap() { // usemap
88 cananian 1.1.2.3 public Temp tempMap(Temp t) {
89 cananian 1.1.2.3 return usespill.containsKey(t) ? (Temp)usespill.get(t) : t;
90 cananian 1.1.2.3 }
91 cananian 1.1.2.5 };
92 cananian 1.1.2.5 Instr ni = il.rename(il.getFactory(), defMap, useMap);
93 cananian 1.1.2.3 // replace old instr with new instr
94 cananian 1.1.2.3 Instr.replace(il, ni); il=ni;
95 cananian 1.1.2.3 instrsToSkip.add(ni);
96 cananian 1.1.2.3 // insert loads before any usespills.
97 cananian 1.3 for (Object eO : usespill.entrySet()) {
98 cananian 1.3 Map.Entry e = (Map.Entry) eO;
99 cananian 1.1.2.3 Temp olduse = (Temp) e.getKey(), newuse = (Temp) e.getValue();
100 cananian 1.1.2.3 Access a = (Access) spills.get(olduse);
101 cananian 1.1.2.2 for (Iterator it2=il.predC().iterator(); it2.hasNext(); ) {
102 cananian 1.1.2.3 Instr loadi = a.makeLoad(il.getFactory(), il, newuse);
103 duncan 1.1.2.4 loadi.insertAt((CFGEdge)it2.next());
104 cananian 1.1.2.3 instrsToSkip.add(loadi);
105 cananian 1.1.2.5 }
106 cananian 1.1.2.5 }
107 cananian 1.1.2.5 // treat next instruction and this one as atomic if next instr
108 cananian 1.1.2.5 // string contains '@ dummy'
109 cananian 1.1.2.5 if (il.succC().size()==1) {
110 cananian 1.1.2.5 Instr dummy = (Instr) ((CFGEdge)il.succC().iterator().next()).to();
111 cananian 1.1.2.5 if (dummy.getAssem().indexOf("@ dummy") >= 0) {
112 cananian 1.1.2.5 ni = dummy.rename(dummy.getFactory(), defMap, useMap);
113 cananian 1.1.2.5 Instr.replace(dummy, ni); il=ni;
114 cananian 1.1.2.5 instrsToSkip.add(ni);
115 cananian 1.1.2.3 }
116 cananian 1.1.2.3 }
117 cananian 1.1.2.3 // insert stores before any defspills.
118 cananian 1.3 for (Object eO : defspill.entrySet()) {
119 cananian 1.3 Map.Entry e = (Map.Entry) eO;
120 cananian 1.1.2.3 Temp olddef = (Temp) e.getKey(), newdef = (Temp) e.getValue();
121 cananian 1.1.2.3 Access a = (Access) spills.get(olddef);
122 cananian 1.1.2.3 for (Iterator it2=il.succC().iterator(); it2.hasNext(); ) {
123 cananian 1.1.2.3 Instr storei = a.makeStore(il.getFactory(), il, newdef);
124 duncan 1.1.2.4 storei.insertAt((CFGEdge)it2.next());
125 cananian 1.1.2.3 instrsToSkip.add(storei);
126 cananian 1.1.2.2 }
127 cananian 1.1.2.2 }
128 cananian 1.1.2.3 // reset usespill and defspill for efficient re-use.
129 cananian 1.1.2.3 usespill.clear(); defspill.clear();
130 cananian 1.1.2.3 // done!
131 cananian 1.1.2.1 }
132 cananian 1.1.2.2 // fixup instrs
133 cananian 1.1.2.2 while (instrs.getPrev()!=null) instrs = instrs.getPrev();
134 cananian 1.1.2.2 return instrs;
135 cananian 1.1.2.1 }
136 cananian 1.2 }