1 pnkfelix 1.1.2.1 package harpoon.Analysis.Instr;
2 pnkfelix 1.1.2.1
3 pnkfelix 1.1.2.1 import harpoon.Analysis.Instr.AppelRegAllocClasses.Web;
4 pnkfelix 1.1.2.1 import harpoon.Analysis.Instr.AppelRegAllocClasses.Node;
5 pnkfelix 1.1.2.1 import harpoon.Analysis.Instr.AppelRegAllocClasses.NodeIter;
6 pnkfelix 1.1.2.1
7 pnkfelix 1.1.2.1 import harpoon.Analysis.Loops.Loops;
8 pnkfelix 1.1.2.1 import harpoon.Analysis.Loops.LoopFinder;
9 pnkfelix 1.1.2.1
10 pnkfelix 1.1.2.1 import harpoon.IR.Assem.Instr;
11 pnkfelix 1.1.2.1
12 cananian 1.5 import net.cscott.jutil.GenericMultiMap;
13 cananian 1.5 import net.cscott.jutil.CombineIterator;
14 pnkfelix 1.1.2.1 import harpoon.Util.Util;
15 pnkfelix 1.1.2.1
16 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
17 pnkfelix 1.1.2.1
18 pnkfelix 1.1.2.1 import java.util.Collection;
19 pnkfelix 1.1.2.1 import java.util.Map;
20 pnkfelix 1.1.2.1 import java.util.AbstractCollection;
21 pnkfelix 1.1.2.1 import java.util.ArrayList;
22 pnkfelix 1.1.2.1 import java.util.HashMap;
23 pnkfelix 1.1.2.1 import java.util.Iterator;
24 pnkfelix 1.1.2.1
25 pnkfelix 1.1.2.1 /** Abstracts away the heuristic used for deciding between
26 pnkfelix 1.1.2.1 spill candidates during graph simplification.
27 pnkfelix 1.1.2.1 <p>
28 pnkfelix 1.1.2.1 See "Spill code minimization techniques for optimizing
29 pnkfelix 1.1.2.1 compilers", Bernstein et. al
30 pnkfelix 1.1.2.1 */
31 pnkfelix 1.1.2.1 public class SpillHeuristics {
32 pnkfelix 1.1.2.2
33 pnkfelix 1.1.2.3 public static boolean USE_ANANIAN_HEURISTIC = true;
34 pnkfelix 1.1.2.2 public static boolean USE_CHAITIN_HEURISTIC = true;
35 pnkfelix 1.1.2.3 public static boolean USE_PINTER_HEURISTICS = true;
36 pnkfelix 1.1.2.2
37 pnkfelix 1.1.2.1 // Node n -> Set of Instr i, s.t. n is alive at i
38 pnkfelix 1.1.2.1 private GenericMultiMap nodeToLiveAt = new GenericMultiMap();
39 pnkfelix 1.1.2.1 private Map nestedLoopDepth;
40 pnkfelix 1.1.2.1
41 pnkfelix 1.1.2.1 // shares state with the AppelRegAlloc class
42 pnkfelix 1.1.2.1 AppelRegAlloc regalloc;
43 pnkfelix 1.1.2.1
44 pnkfelix 1.1.2.1 SpillHeuristics(AppelRegAlloc ara) {
45 pnkfelix 1.1.2.1 regalloc = ara;
46 pnkfelix 1.1.2.1 }
47 pnkfelix 1.1.2.1
48 pnkfelix 1.1.2.1 /** Resets the state of this in preparation for analysis on
49 pnkfelix 1.1.2.1 altered code.
50 pnkfelix 1.1.2.1 */
51 pnkfelix 1.1.2.1 void reset() {
52 pnkfelix 1.1.2.1 // FSK: Lazily build these mappings...
53 pnkfelix 1.1.2.1 nodeToLiveAt = null;
54 pnkfelix 1.1.2.1 nestedLoopDepth = null;
55 pnkfelix 1.1.2.1 }
56 pnkfelix 1.1.2.1
57 pnkfelix 1.1.2.1 /** Instr -> Integer, val is loop nesting depth for the key (0 for
58 pnkfelix 1.1.2.1 non-looped code). Constructed on demand; access through method
59 pnkfelix 1.1.2.1 call only. */
60 pnkfelix 1.1.2.1 Map nestedLoopDepth() {
61 pnkfelix 1.1.2.1 if (nestedLoopDepth == null)
62 pnkfelix 1.1.2.1 nestedLoopDepth = buildNestedLoopDepth();
63 pnkfelix 1.1.2.1 return nestedLoopDepth;
64 pnkfelix 1.1.2.1 }
65 pnkfelix 1.1.2.1
66 pnkfelix 1.1.2.1 private Map buildNestedLoopDepth() {
67 pnkfelix 1.1.2.1 // builds the nestedLoopDepth map, doing a breadth-first
68 pnkfelix 1.1.2.1 // traversal of the loop tree.
69 pnkfelix 1.1.2.1 HashMap depthMap = new HashMap();
70 pnkfelix 1.1.2.1 LoopFinder root = new LoopFinder(regalloc.code);
71 pnkfelix 1.1.2.1
72 pnkfelix 1.1.2.1 // List<Loops> where index of vector is the looping depth
73 pnkfelix 1.1.2.1 // (thus the 0th elem is the root itself)
74 pnkfelix 1.1.2.1 ArrayList level = new ArrayList();
75 pnkfelix 1.1.2.1 level.add(root);
76 pnkfelix 1.1.2.1 int depth = 0; // tracks the current level in the tree
77 pnkfelix 1.1.2.1 while( ! level.isEmpty()) {
78 pnkfelix 1.1.2.1 Iterator levelIter = level.iterator();
79 pnkfelix 1.1.2.1 level = new ArrayList();
80 pnkfelix 1.1.2.1 Integer currDepth = new Integer( depth );
81 pnkfelix 1.1.2.1 while( levelIter.hasNext() ){
82 pnkfelix 1.1.2.1 Loops curr = (Loops) levelIter.next();
83 pnkfelix 1.1.2.1 level.addAll( curr.nestedLoops() );
84 pnkfelix 1.1.2.1
85 cananian 1.6 for (Object iO : curr.loopExcElements()){
86 cananian 1.6 Instr i = (Instr) iO;
87 cananian 1.3.2.1 assert ! depthMap.keySet().contains( i );
88 pnkfelix 1.1.2.1 depthMap.put( i , currDepth );
89 pnkfelix 1.1.2.1 }
90 pnkfelix 1.1.2.1 }
91 pnkfelix 1.1.2.1 depth++;
92 pnkfelix 1.1.2.1 }
93 pnkfelix 1.1.2.1
94 pnkfelix 1.1.2.1 return depthMap;
95 pnkfelix 1.1.2.1 }
96 pnkfelix 1.1.2.1
97 pnkfelix 1.1.2.1 /** Returns a bunch of SpillHeuristic objects, with "cheap" ones
98 pnkfelix 1.1.2.1 in front.
99 pnkfelix 1.1.2.1 */
100 pnkfelix 1.1.2.1 SpillHeuristic[] spillHeuristics() {
101 pnkfelix 1.1.2.1 SpillHeuristic[] hs = new SpillHeuristic[] {
102 pnkfelix 1.1.2.1
103 pnkfelix 1.1.2.2 USE_ANANIAN_HEURISTIC ?
104 pnkfelix 1.1.2.1 new SpillHeuristic() { double cost(Node m) {
105 pnkfelix 1.1.2.1 return (1000*(m.web.defs.size()+m.web.uses.size() ) ) / m.degree; }}
106 pnkfelix 1.1.2.2 : null
107 pnkfelix 1.1.2.1 ,
108 pnkfelix 1.1.2.1
109 pnkfelix 1.1.2.2 USE_CHAITIN_HEURISTIC ?
110 pnkfelix 1.1.2.1 new SpillHeuristic() { double cost( Node m ) {
111 pnkfelix 1.1.2.1 return chaitinCost(m) / m.degree; }}
112 pnkfelix 1.1.2.2 : null
113 pnkfelix 1.1.2.1 ,
114 pnkfelix 1.1.2.2 USE_PINTER_HEURISTICS ?
115 pnkfelix 1.1.2.1 new SpillHeuristic() { double cost( Node m ) {
116 pnkfelix 1.1.2.1 return chaitinCost(m) / (m.degree * m.degree); }}
117 pnkfelix 1.1.2.2 : null
118 pnkfelix 1.1.2.1 ,
119 pnkfelix 1.1.2.2 USE_PINTER_HEURISTICS ?
120 pnkfelix 1.1.2.1 new SpillHeuristic() { double cost( Node m ) {
121 pnkfelix 1.1.2.1 return chaitinCost(m) / ( area(m) * m.degree ); }}
122 pnkfelix 1.1.2.2 : null
123 pnkfelix 1.1.2.1 ,
124 pnkfelix 1.1.2.2 USE_PINTER_HEURISTICS ?
125 pnkfelix 1.1.2.1 new SpillHeuristic() { double cost( Node m ) {
126 pnkfelix 1.1.2.2 return chaitinCost(m) / ( area(m) * m.degree * m.degree ); }}
127 pnkfelix 1.1.2.2 : null
128 pnkfelix 1.1.2.1 };
129 pnkfelix 1.1.2.1
130 pnkfelix 1.1.2.2 int nonnull=0;
131 pnkfelix 1.1.2.2 for(int i=0; i<hs.length; i++)
132 pnkfelix 1.1.2.2 if (hs[i] != null)
133 pnkfelix 1.1.2.2 nonnull++;
134 pnkfelix 1.1.2.2 SpillHeuristic[] shs = new SpillHeuristic[nonnull];
135 pnkfelix 1.1.2.2 int j=0;
136 pnkfelix 1.1.2.2 for(int i=0; i<hs.length; i++) {
137 pnkfelix 1.1.2.2 if (hs[i] != null) {
138 pnkfelix 1.1.2.2 shs[j] = hs[i];
139 pnkfelix 1.1.2.2 j++;
140 pnkfelix 1.1.2.2 }
141 pnkfelix 1.1.2.2 }
142 cananian 1.3.2.1 assert j == nonnull;
143 pnkfelix 1.1.2.2 return shs;
144 pnkfelix 1.1.2.1 }
145 pnkfelix 1.1.2.1
146 pnkfelix 1.1.2.1 /** Returns the loop nested depth of <code>i</code>. */
147 pnkfelix 1.1.2.1 int depth(Instr i){ return((Integer)nestedLoopDepth().get(i)).intValue(); }
148 pnkfelix 1.1.2.1 /** Returns the number of temporaries live at <code>i</code>. */
149 pnkfelix 1.1.2.1 int width(Instr i){ return liveAt(i).size(); }
150 pnkfelix 1.1.2.1
151 pnkfelix 1.1.2.1
152 pnkfelix 1.1.2.1 // wrapper for dealing with union'ing a large bitset with a small
153 pnkfelix 1.1.2.1 // appendage set.
154 pnkfelix 1.1.2.1 private class ExtremityCollection extends AbstractCollection {
155 pnkfelix 1.1.2.1 ArrayList appendage;
156 pnkfelix 1.1.2.1 Collection body;
157 pnkfelix 1.1.2.1 // shares state with big, but not with small. I bet remove()
158 pnkfelix 1.1.2.1 // is pretty sketch...
159 pnkfelix 1.1.2.1 ExtremityCollection(Collection big, Collection small) {
160 pnkfelix 1.1.2.1 appendage = new ArrayList(small.size());
161 pnkfelix 1.1.2.1 for(Iterator iter=small.iterator(); iter.hasNext();){
162 pnkfelix 1.1.2.1 Object s = iter.next();
163 pnkfelix 1.1.2.1 if (!big.contains(s)) {
164 pnkfelix 1.1.2.1 appendage.add(s);
165 pnkfelix 1.1.2.1 }
166 pnkfelix 1.1.2.1 }
167 pnkfelix 1.1.2.1 body = big;
168 pnkfelix 1.1.2.1 }
169 pnkfelix 1.1.2.1 public Iterator iterator() {
170 pnkfelix 1.1.2.1 return new CombineIterator(body.iterator(), appendage.iterator());
171 pnkfelix 1.1.2.1 }
172 pnkfelix 1.1.2.1 public int size() { return body.size() + appendage.size(); }
173 pnkfelix 1.1.2.1 }
174 pnkfelix 1.1.2.1
175 pnkfelix 1.1.2.1 private Collection liveAt(Instr i) {
176 pnkfelix 1.1.2.1 // live-at(i) should be live-in(i) U defs(i), according to scott
177 pnkfelix 1.1.2.1 Collection liveTempC = regalloc.liveTemps.getLiveBefore(i);
178 pnkfelix 1.1.2.1 return new ExtremityCollection( liveTempC, i.defC() );
179 pnkfelix 1.1.2.1 }
180 pnkfelix 1.1.2.1
181 pnkfelix 1.1.2.1 private void buildNodeToLiveAt() {
182 pnkfelix 1.1.2.1 nodeToLiveAt.clear();
183 pnkfelix 1.1.2.1 for(Iterator instrs = regalloc.instrs(); instrs.hasNext(); ){
184 pnkfelix 1.1.2.1 Instr i = (Instr) instrs.next();
185 pnkfelix 1.1.2.1 Collection liveAt = liveAt(i);
186 cananian 1.6 for(Object tO : liveAt) {
187 cananian 1.6 Temp t = (Temp) tO;
188 pnkfelix 1.1.2.1 Collection rdefC = regalloc.rdefs.reachingDefs(i, t);
189 pnkfelix 1.1.2.1 Collection webC = regalloc.tempToWebs.getValues( t );
190 cananian 1.6 for(Object wO : webC){
191 cananian 1.6 Web w = (Web) wO;
192 pnkfelix 1.1.2.1 boolean intersect = false;
193 cananian 1.6 for(Object defO : rdefC){
194 cananian 1.6 Instr def = (Instr) defO;
195 pnkfelix 1.1.2.1 if(w.defs.contains( def )){
196 pnkfelix 1.1.2.1 intersect = true;
197 pnkfelix 1.1.2.1 break;
198 pnkfelix 1.1.2.1 }
199 pnkfelix 1.1.2.1 }
200 pnkfelix 1.1.2.1 if ( intersect ) {
201 pnkfelix 1.1.2.1 // w has a def that reaches i, thus w is live-at i
202 pnkfelix 1.1.2.1 Collection nodeC = (Collection) regalloc.nodesFor(w);
203 cananian 1.6 for(Object nO : nodeC){
204 cananian 1.6 Node n = (Node) nO;
205 pnkfelix 1.1.2.1 nodeToLiveAt.add( n, i );
206 pnkfelix 1.1.2.1 }
207 pnkfelix 1.1.2.1 }
208 pnkfelix 1.1.2.1 }
209 pnkfelix 1.1.2.1 }
210 pnkfelix 1.1.2.1 }
211 pnkfelix 1.1.2.1 }
212 pnkfelix 1.1.2.1
213 pnkfelix 1.1.2.1 protected abstract class SpillHeuristic {
214 pnkfelix 1.1.2.1 public String toString() {
215 pnkfelix 1.1.2.1 return "SpillHeuristic<"
216 pnkfelix 1.1.2.1 +"accumExpCost:"+accumExpCost
217 pnkfelix 1.1.2.1 +" maxExpSpills:"+maxExpSpills
218 pnkfelix 1.1.2.1 +" actualCost:"+actualCost
219 pnkfelix 1.1.2.1 +" actualSpills:"+actualSpills
220 pnkfelix 1.1.2.1 +">";
221 pnkfelix 1.1.2.1 }
222 pnkfelix 1.1.2.1
223 pnkfelix 1.1.2.1 double accumExpCost = 0.0;
224 pnkfelix 1.1.2.1 int maxExpSpills = 0;
225 pnkfelix 1.1.2.1
226 pnkfelix 1.1.2.1 double actualCost = 0.0;
227 pnkfelix 1.1.2.1 int actualSpills = 0;
228 pnkfelix 1.1.2.1
229 pnkfelix 1.1.2.1 HashMap instrToAreaCache = new HashMap();
230 pnkfelix 1.1.2.1 HashMap nodeToAreaCache = new HashMap();
231 pnkfelix 1.1.2.1
232 pnkfelix 1.1.2.1 void reset() {
233 pnkfelix 1.1.2.1 accumExpCost = 0.0;
234 pnkfelix 1.1.2.1 maxExpSpills = 0;
235 pnkfelix 1.1.2.1 actualCost = 0.0;
236 pnkfelix 1.1.2.1 actualSpills = 0;
237 pnkfelix 1.1.2.1 instrToAreaCache.clear();
238 pnkfelix 1.1.2.1 nodeToAreaCache.clear();
239 pnkfelix 1.1.2.1 }
240 pnkfelix 1.1.2.1 void expectSpill( Node m ) {
241 pnkfelix 1.1.2.1 // IMPORTANT: don't confuse "accumExpCost" here (which is called
242 pnkfelix 1.1.2.1 // "h_i" in the paper) with "cost" in the paper (which is
243 pnkfelix 1.1.2.1 // called chaitinCost here)
244 pnkfelix 1.1.2.1 accumExpCost += chaitinCost( m );
245 pnkfelix 1.1.2.1 maxExpSpills++;
246 pnkfelix 1.1.2.1 }
247 pnkfelix 1.1.2.1
248 pnkfelix 1.1.2.1
249 pnkfelix 1.1.2.1 /** called when spill code is added for n . */
250 pnkfelix 1.1.2.1 void reallySpill( NodeIter ni ){
251 pnkfelix 1.1.2.1 while(ni.hasNext())
252 pnkfelix 1.1.2.1 reallySpill(ni.next());
253 pnkfelix 1.1.2.1 }
254 pnkfelix 1.1.2.1 void reallySpill( Node n ){
255 pnkfelix 1.1.2.1 actualCost += chaitinCost(n);
256 pnkfelix 1.1.2.1 actualSpills++;
257 pnkfelix 1.1.2.1 }
258 pnkfelix 1.1.2.1
259 pnkfelix 1.1.2.1 abstract double cost( Node m );
260 pnkfelix 1.1.2.1
261 pnkfelix 1.1.2.1 double chaitinCost( Node m ) {
262 pnkfelix 1.1.2.1 double sum = 0.0;
263 cananian 1.6 for(Object iO : m.web.defs){
264 cananian 1.6 Instr i = (Instr) iO;
265 pnkfelix 1.1.2.1 sum += Math.pow( 10.0, depth(i));
266 pnkfelix 1.1.2.1 }
267 cananian 1.6 for(Object iO : m.web.uses){
268 cananian 1.6 Instr i = (Instr) iO;
269 pnkfelix 1.1.2.1 sum += Math.pow( 10.0, depth(i));
270 pnkfelix 1.1.2.1 }
271 pnkfelix 1.1.2.1 return sum;
272 pnkfelix 1.1.2.1 }
273 pnkfelix 1.1.2.1 double area( Node m ) {
274 pnkfelix 1.1.2.1 if (nodeToLiveAt == null) {
275 pnkfelix 1.1.2.1 nodeToLiveAt = new GenericMultiMap();
276 pnkfelix 1.1.2.1 buildNodeToLiveAt();
277 pnkfelix 1.1.2.1 }
278 pnkfelix 1.1.2.1
279 pnkfelix 1.1.2.1 if (nodeToAreaCache.containsKey(m)) {
280 pnkfelix 1.1.2.1 return ((Double)nodeToAreaCache.get(m)).doubleValue();
281 pnkfelix 1.1.2.1 } else {
282 pnkfelix 1.1.2.1 double sum = 0.0;
283 pnkfelix 1.1.2.1 Collection instrC = nodeToLiveAt.getValues( m );
284 cananian 1.6 for(Object iO : instrC){
285 cananian 1.6 Instr i = (Instr) iO;
286 pnkfelix 1.1.2.1
287 pnkfelix 1.1.2.1 if (instrToAreaCache.containsKey(i)) {
288 pnkfelix 1.1.2.1 sum += ((Double)instrToAreaCache.get(i)).doubleValue();
289 pnkfelix 1.1.2.1 } else {
290 pnkfelix 1.1.2.1 double val = (Math.pow(5.0, depth(i)) * width(i));
291 pnkfelix 1.1.2.1 sum += val;
292 pnkfelix 1.1.2.1 instrToAreaCache.put(i, new Double(val) );
293 pnkfelix 1.1.2.1 }
294 pnkfelix 1.1.2.1 }
295 pnkfelix 1.1.2.1 nodeToAreaCache.put(m, new Double(sum));
296 pnkfelix 1.1.2.1 return sum;
297 pnkfelix 1.1.2.1 }
298 pnkfelix 1.1.2.1 }
299 pnkfelix 1.1.2.1
300 pnkfelix 1.1.2.1 }
301 cananian 1.2 }