1 cananian 1.1.2.1 // SmallMethodInliner.java, created Mon Jun 18 13:28:16 2001 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.1 import harpoon.ClassFile.CachingCodeFactory;
8 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
9 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
10 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
11 cananian 1.1.2.1 import harpoon.IR.Quads.CALL;
12 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
13 cananian 1.6 import net.cscott.jutil.BinaryHeap;
14 cananian 1.6 import net.cscott.jutil.GenericMultiMap;
15 cananian 1.6 import net.cscott.jutil.Heap;
16 cananian 1.6 import net.cscott.jutil.MultiMap;
17 cananian 1.1.2.1
18 cananian 1.1.2.1 import java.lang.reflect.Modifier;
19 cananian 1.1.2.1 import java.util.Collection;
20 cananian 1.1.2.1 import java.util.HashMap;
21 cananian 1.1.2.1 import java.util.Iterator;
22 cananian 1.1.2.1 import java.util.List;
23 cananian 1.1.2.2 import java.util.Map;
24 cananian 1.1.2.1 import java.util.Set;
25 cananian 1.1.2.1 /**
26 cananian 1.1.2.1 * <code>SmallMethodInliner</code> will inline small methods until
27 cananian 1.1.2.1 * the code is bloated by the specified amount.
28 cananian 1.1.2.1 *
29 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
30 cananian 1.7 * @version $Id: SmallMethodInliner.java,v 1.7 2004/02/08 03:20:10 cananian Exp $
31 cananian 1.1.2.1 */
32 cananian 1.1.2.1 public class SmallMethodInliner extends MethodInliningCodeFactory {
33 salcianu 1.5 static final int NPERCENT= // default to 25 percent bloat.
34 cananian 1.1.2.3 Integer.parseInt(System.getProperty("harpoon.inliner.percent", "25"));
35 cananian 1.1.2.1
36 cananian 1.1.2.1 /** Creates a <code>SmallMethodInliner</code>. */
37 cananian 1.1.2.1 public SmallMethodInliner(HCodeFactory hcf, ClassHierarchy ch) {
38 cananian 1.1.2.1 this(new CachingCodeFactory(hcf), ch);
39 cananian 1.1.2.1 }
40 cananian 1.1.2.1 // scan ccf for appropriate call sites.
41 cananian 1.1.2.1 private SmallMethodInliner(CachingCodeFactory ccf, ClassHierarchy ch) {
42 cananian 1.1.2.1 super(ccf);
43 cananian 1.1.2.1 long totalsize = 0;
44 cananian 1.1.2.2
45 cananian 1.1.2.2 IntMap methodSize = new IntMap();
46 cananian 1.1.2.2 MultiMap callSites = new GenericMultiMap();
47 cananian 1.1.2.2 Map call2caller = new HashMap();
48 cananian 1.1.2.2
49 cananian 1.7 for (Object hmO : ch.callableMethods()) {
50 cananian 1.7 HMethod hm = (HMethod) hmO;
51 cananian 1.1.2.1 HCode hc = ccf.convert(hm);
52 cananian 1.1.2.1 // determine method sizes
53 cananian 1.1.2.1 if (hc==null) continue;
54 cananian 1.1.2.1 // size-4: CALL, HEADER, FOOTER, METHOD.
55 cananian 1.1.2.1 methodSize.putInt(hm, hc.getElementsL().size()-4);
56 cananian 1.1.2.1 // find call sites.
57 cananian 1.1.2.1 for (Iterator it2=hc.getElementsI(); it2.hasNext(); ) {
58 cananian 1.1.2.1 Quad q = (Quad) it2.next();
59 cananian 1.1.2.1 if (!(q instanceof CALL)) continue;
60 cananian 1.1.2.1 CALL call = (CALL) q;
61 cananian 1.1.2.1 if (call.isVirtual()) continue;
62 cananian 1.1.2.1 callSites.add(call.method(), call);
63 cananian 1.1.2.2 call2caller.put(call, hm);
64 cananian 1.1.2.1 }
65 cananian 1.1.2.1 // keep track of total program size
66 cananian 1.1.2.1 totalsize+=methodSize.getInt(hm);
67 cananian 1.1.2.1 }
68 cananian 1.1.2.2 Heap h = new BinaryHeap();
69 cananian 1.1.2.2 Map method2entry = new HashMap();
70 cananian 1.7 for (Object hmO : ch.callableMethods()) {
71 cananian 1.7 HMethod hm = (HMethod) hmO;
72 cananian 1.1.2.2 // compute score for hm.
73 cananian 1.1.2.2 int score = score(hm, methodSize, callSites);
74 cananian 1.1.2.2 // add to heap, and to method-to-entry map.
75 cananian 1.1.2.2 if (callSites.getValues(hm).size()>0) // unless no sites to inline
76 cananian 1.1.2.2 method2entry.put(hm, h.insert(new Integer(score), hm));
77 cananian 1.1.2.2 }
78 cananian 1.1.2.1 // inline to bloat the program by the specified percentage of
79 cananian 1.1.2.1 // total program size.
80 cananian 1.1.2.1 long bloat = 0;
81 cananian 1.1.2.2 while (bloat < (NPERCENT*totalsize/100)) {
82 cananian 1.1.2.2 if (h.isEmpty()) break;
83 cananian 1.1.2.2 HMethod hm = (HMethod) h.extractMinimum().getValue();//inline this!
84 cananian 1.1.2.2 method2entry.remove(hm);
85 cananian 1.1.2.1 if (Modifier.isNative(hm.getModifiers())) continue;//unless native
86 cananian 1.1.2.1 int size = methodSize.getInt(hm);
87 cananian 1.1.2.2 Iterator it2=callSites.getValues(hm).iterator();
88 cananian 1.1.2.2 if (it2.hasNext())
89 cananian 1.1.2.2 System.err.println("INLINING all nonvirtual calls to "+hm);
90 cananian 1.1.2.1 while (it2.hasNext()) {
91 cananian 1.1.2.2 CALL call = (CALL) it2.next();
92 cananian 1.1.2.2 inline(call);
93 cananian 1.1.2.1 bloat+=size;
94 cananian 1.1.2.2 // add 'size' to caller's method size...
95 cananian 1.1.2.2 HMethod caller = (HMethod) call2caller.get(call);
96 cananian 1.1.2.2 methodSize.putInt(caller, methodSize.getInt(caller)+size);
97 cananian 1.1.2.2 // ...and adjust caller's key in pqueue.
98 cananian 1.1.2.2 Map.Entry me = (Map.Entry) method2entry.get(caller);
99 cananian 1.1.2.2 if (me!=null) {
100 cananian 1.1.2.2 int score = score(hm, methodSize, callSites);
101 cananian 1.1.2.2 h.updateKey(me, new Integer(score));
102 cananian 1.1.2.2 }
103 cananian 1.1.2.1 }
104 cananian 1.1.2.1 }
105 cananian 1.1.2.1 // done!
106 cananian 1.1.2.2 System.out.println("ACTUAL INLINING BLOAT: " +
107 cananian 1.1.2.2 ((1+2*100*bloat)/(2*totalsize)) + "%");
108 cananian 1.1.2.1 }
109 wbeebee 1.3
110 wbeebee 1.3 /** Override this if you want to define your own scoring function
111 wbeebee 1.3 * for inlining methods.
112 wbeebee 1.3 */
113 wbeebee 1.3 protected int score(HMethod hm, IntMap methodSize, MultiMap callSites)
114 cananian 1.1.2.2 {
115 cananian 1.1.2.1 return methodSize.getInt(hm) * callSites.getValues(hm).size();
116 cananian 1.1.2.1 }
117 cananian 1.1.2.1
118 wbeebee 1.4 protected static class IntMap extends HashMap {
119 cananian 1.1.2.1 IntMap() { super(); }
120 cananian 1.1.2.1 int getInt(Object key) {
121 cananian 1.1.2.1 Integer i = (Integer) get(key);
122 cananian 1.1.2.1 return (i==null)?0:i.intValue();
123 cananian 1.1.2.1 }
124 cananian 1.1.2.1 void putInt(Object key, int val) {
125 cananian 1.1.2.1 put(key, new Integer(val));
126 cananian 1.1.2.1 }
127 cananian 1.1.2.1 }
128 cananian 1.2 }