1 salcianu 1.1.2.1 // PACheckRemoval.java, created Mon Jan 22 19:51:51 2001 by salcianu
2 cananian 1.1.2.6 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Analysis.Realtime;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.3 import java.util.Map;
7 salcianu 1.1.2.3 import java.util.Hashtable;
8 salcianu 1.1.2.3 import java.util.Set;
9 salcianu 1.1.2.3 import java.util.Iterator;
10 salcianu 1.1.2.3
11 wbeebee 1.1.2.2 import harpoon.ClassFile.Linker;
12 wbeebee 1.1.2.2 import harpoon.ClassFile.HCodeFactory;
13 salcianu 1.1.2.3 import harpoon.ClassFile.HMethod;
14 salcianu 1.1.2.3 import harpoon.IR.Quads.QuadNoSSA;
15 wbeebee 1.1.2.2 import harpoon.Analysis.ClassHierarchy;
16 wbeebee 1.1.2.2
17 salcianu 1.1.2.3 import harpoon.IR.Quads.Quad;
18 salcianu 1.1.2.3 import harpoon.IR.Quads.SET;
19 salcianu 1.1.2.3 import harpoon.IR.Quads.ASET;
20 salcianu 1.1.2.3 import harpoon.IR.Quads.QuadVisitor;
21 salcianu 1.1.2.3
22 salcianu 1.1.2.3 import harpoon.Temp.Temp;
23 salcianu 1.1.2.3
24 salcianu 1.1.2.3 import harpoon.Analysis.PointerAnalysis.PointerAnalysis;
25 salcianu 1.1.2.3 import harpoon.Analysis.PointerAnalysis.PANode;
26 salcianu 1.1.2.3
27 salcianu 1.1.2.3 import harpoon.Analysis.MetaMethods.MetaCallGraph;
28 salcianu 1.1.2.3 import harpoon.Analysis.MetaMethods.MetaMethod;
29 salcianu 1.1.2.3 import harpoon.Analysis.MetaMethods.FakeMetaCallGraph;
30 salcianu 1.1.2.3 import harpoon.Analysis.MetaMethods.MetaCallGraphImpl;
31 salcianu 1.1.2.3 import harpoon.Analysis.MetaMethods.MetaAllCallers;
32 salcianu 1.1.2.3 import harpoon.Util.LightBasicBlocks.LBBConverter;
33 salcianu 1.1.2.3
34 salcianu 1.1.2.3 import harpoon.ClassFile.CachingCodeFactory;
35 salcianu 1.1.2.3 import harpoon.Util.BasicBlocks.CachingBBConverter;
36 salcianu 1.1.2.3 import harpoon.Util.LightBasicBlocks.LightBasicBlock;
37 salcianu 1.1.2.3 import harpoon.Util.LightBasicBlocks.LBBConverter;
38 salcianu 1.1.2.3 import harpoon.Util.LightBasicBlocks.CachingLBBConverter;
39 salcianu 1.1.2.5 import harpoon.Util.LightBasicBlocks.CachingSCCLBBFactory;
40 salcianu 1.1.2.3
41 salcianu 1.1.2.3 import harpoon.Analysis.Quads.CallGraph;
42 salcianu 1.1.2.3 import harpoon.Analysis.Quads.CallGraphImpl;
43 salcianu 1.1.2.3 import harpoon.Analysis.MetaMethods.SmartCallGraph;
44 salcianu 1.1.2.3
45 salcianu 1.1.2.3 import harpoon.Util.Util;
46 salcianu 1.1.2.1
47 salcianu 1.1.2.1 /**
48 salcianu 1.1.2.3 * <code>PACheckRemoval</code> is a pointer analysis based
49 salcianu 1.1.2.1 * implementation of the <codE>CheckRemoval</code> interface.
50 salcianu 1.1.2.1 *
51 cananian 1.1.2.6 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
52 cananian 1.8 * @version $Id: PACheckRemoval.java,v 1.8 2004/02/08 03:20:13 cananian Exp $ */
53 salcianu 1.1.2.1 public class PACheckRemoval implements CheckRemoval {
54 salcianu 1.1.2.3
55 salcianu 1.1.2.3 PointerAnalysis pa = null;
56 salcianu 1.1.2.3
57 salcianu 1.1.2.3 private static final boolean SMART_CALL_GRAPH = true;
58 salcianu 1.1.2.1
59 salcianu 1.1.2.1 /** Creates a <code>PACheckRemoval</code>. */
60 salcianu 1.1.2.3 public PACheckRemoval(Linker linker, ClassHierarchy ch,
61 salcianu 1.1.2.3 HCodeFactory hcf, Set mroots) {
62 salcianu 1.1.2.3
63 cananian 1.3.2.1 assert hcf.getCodeName().equals(QuadNoSSA.codename) : "Not a QuadNoSSA code factory";
64 salcianu 1.1.2.3 // we really need a caching code factory; raise an error otherwise
65 salcianu 1.1.2.3 CachingCodeFactory ccf = (CachingCodeFactory) hcf;
66 salcianu 1.1.2.3 CachingBBConverter bbconv = new CachingBBConverter(ccf);
67 salcianu 1.1.2.3 LBBConverter lbbconv = new CachingLBBConverter(bbconv);
68 salcianu 1.1.2.3
69 salcianu 1.1.2.3 Set run_mms = null;
70 salcianu 1.1.2.3 CallGraph cg = null;
71 salcianu 1.1.2.3
72 salcianu 1.1.2.3 System.out.print("CallGraph ... ");
73 salcianu 1.1.2.3 long tstart = time();
74 salcianu 1.1.2.3 if(SMART_CALL_GRAPH){ // smart call graph!
75 salcianu 1.5 MetaCallGraph fmcg =
76 salcianu 1.5 new MetaCallGraphImpl(ccf, linker, ch, mroots);
77 salcianu 1.1.2.3 run_mms = fmcg.getRunMetaMethods();
78 salcianu 1.1.2.3 cg = new SmartCallGraph(fmcg);
79 salcianu 1.1.2.3 }
80 salcianu 1.1.2.3 else
81 salcianu 1.1.2.3 cg = new CallGraphImpl(ch, ccf);
82 salcianu 1.1.2.3
83 salcianu 1.1.2.3 MetaCallGraph mcg =
84 salcianu 1.6 new FakeMetaCallGraph(cg, run_mms);
85 salcianu 1.1.2.3
86 salcianu 1.1.2.3 MetaAllCallers mac = new MetaAllCallers(mcg);
87 salcianu 1.1.2.3 System.out.println((time() - tstart) + "ms");
88 salcianu 1.1.2.3
89 salcianu 1.1.2.3 System.out.println("PointerAnalysis ... ");
90 salcianu 1.1.2.3 tstart = time();
91 salcianu 1.7 pa = new PointerAnalysis(mcg,
92 salcianu 1.1.2.5 new CachingSCCLBBFactory(lbbconv),
93 salcianu 1.7 linker, ch);
94 salcianu 1.1.2.3 // intrathread analysis of all the callable methods
95 cananian 1.8 for(Object mmO : mcg.getAllMetaMethods()) {
96 cananian 1.8 MetaMethod mm = (MetaMethod) mmO;
97 salcianu 1.1.2.3 if(!analyzable(mm)) continue;
98 salcianu 1.1.2.3 pa.getIntParIntGraph(mm);
99 salcianu 1.1.2.3 }
100 salcianu 1.1.2.3 System.out.println((time() - tstart) + "ms");
101 salcianu 1.1.2.1 }
102 salcianu 1.1.2.1
103 salcianu 1.1.2.3
104 salcianu 1.1.2.3 private boolean analyzable(MetaMethod mm) {
105 salcianu 1.1.2.3 HMethod hm = mm.getHMethod();
106 salcianu 1.1.2.3 if(java.lang.reflect.Modifier.isNative(hm.getModifiers()))
107 salcianu 1.1.2.3 return false;
108 salcianu 1.1.2.3 return true;
109 salcianu 1.1.2.3 }
110 salcianu 1.1.2.3
111 salcianu 1.1.2.3
112 salcianu 1.1.2.3 private long time() {
113 salcianu 1.1.2.3 return System.currentTimeMillis();
114 salcianu 1.1.2.3 }
115 salcianu 1.1.2.3
116 salcianu 1.1.2.3
117 salcianu 1.1.2.3
118 salcianu 1.1.2.3 // returns the a from (SET) a.f=b or (ASET) a[i]=b
119 salcianu 1.1.2.3 private Temp getDestTemp(Quad instr) {
120 salcianu 1.1.2.3 class CRQuadVisitor extends QuadVisitor {
121 salcianu 1.1.2.3 public Temp a;
122 salcianu 1.1.2.3
123 salcianu 1.1.2.3 public void visit(SET q) {
124 salcianu 1.1.2.3 a = q.objectref();
125 salcianu 1.1.2.3 }
126 salcianu 1.1.2.3
127 salcianu 1.1.2.3 public void visit(ASET q) {
128 salcianu 1.1.2.3 a = q.objectref();
129 salcianu 1.1.2.3 }
130 salcianu 1.1.2.3
131 salcianu 1.1.2.3 public void visit(Quad q) {
132 cananian 1.3.2.1 assert false : "Not a SET or an ASET quad!";
133 salcianu 1.1.2.3 }
134 salcianu 1.1.2.3 };
135 salcianu 1.1.2.3 CRQuadVisitor qv = new CRQuadVisitor();
136 salcianu 1.1.2.3 instr.accept(qv);
137 salcianu 1.1.2.3 return qv.a;
138 salcianu 1.1.2.3 }
139 salcianu 1.1.2.3
140 salcianu 1.1.2.3 /* instr: SET or ASET
141 salcianu 1.1.2.3 a.f = b
142 salcianu 1.1.2.3 a[i] = b
143 salcianu 1.1.2.3 returns true iff a does not escape from a run method
144 salcianu 1.1.2.3 (conservative approx of "a does not escape from the run method of
145 salcianu 1.1.2.3 a memory scope). */
146 salcianu 1.1.2.3 public boolean shouldRemoveCheck(Quad instr) {
147 salcianu 1.1.2.3 Temp a = getDestTemp(instr);
148 salcianu 1.1.2.3 MetaMethod mm = null; // TODO
149 salcianu 1.1.2.3
150 salcianu 1.1.2.3 // treat the static fields (ie global vars)
151 salcianu 1.1.2.3 if(a == null) return false;
152 salcianu 1.1.2.3
153 salcianu 1.1.2.3 // the nodes that might by pointed to by a
154 salcianu 1.1.2.3 Set nodes = pa.pointedNodes(instr, a);
155 cananian 1.8 for(Object nodeO : nodes) {
156 cananian 1.8 PANode node = (PANode) nodeO;
157 salcianu 1.1.2.3 // if any of them might escape, the check is needed
158 salcianu 1.1.2.3 if(!remainInMemScope(node, mm))
159 salcianu 1.1.2.3 return false;
160 salcianu 1.1.2.3 }
161 salcianu 1.1.2.3
162 salcianu 1.1.2.3 return true;
163 salcianu 1.1.2.1 }
164 salcianu 1.1.2.1
165 salcianu 1.1.2.3
166 salcianu 1.1.2.3 // attaches to each node created by the pointer analysis a Boolean that
167 salcianu 1.1.2.3 // conservatively says whether it remains in the memory scope run method.
168 salcianu 1.1.2.3 Map node2remain = new Hashtable();
169 salcianu 1.1.2.3
170 salcianu 1.1.2.3 private boolean remainInMemScope(PANode node, MetaMethod mm) {
171 salcianu 1.1.2.3 Boolean remain = (Boolean) node2remain.get(node);
172 salcianu 1.1.2.3 if(remain == null) {
173 salcianu 1.1.2.3 remain = new Boolean(remainInMemScope2(node, mm, ""));
174 salcianu 1.1.2.3 node2remain.put(node, remain);
175 salcianu 1.1.2.3 }
176 salcianu 1.1.2.3 return remain.booleanValue();
177 salcianu 1.1.2.3 }
178 salcianu 1.1.2.3
179 salcianu 1.1.2.3
180 salcianu 1.1.2.3 private boolean remainInMemScope2(PANode node, MetaMethod mm, String idt) {
181 salcianu 1.1.2.3 return false;
182 salcianu 1.1.2.3 }
183 salcianu 1.1.2.3
184 cananian 1.2 }