1 package Analysis.CallGraph;
3 import IR.Flat.FlatMethod;
4 import IR.Flat.FlatNode;
5 import IR.Flat.FlatCall;
8 import IR.ClassDescriptor;
9 import IR.MethodDescriptor;
10 import IR.TaskDescriptor;
11 import IR.TypeDescriptor;
15 public class CallGraph {
16 protected State state;
18 // MethodDescriptor maps to HashSet<MethodDescriptor>
19 protected Hashtable mapVirtual2ImplementationSet;
21 // MethodDescriptor or TaskDescriptor maps to HashSet<MethodDescriptor>
22 protected Hashtable mapCaller2CalleeSet;
24 // MethodDescriptor maps to HashSet<MethodDescriptor or TaskDescriptor>
25 protected Hashtable mapCallee2CallerSet;
27 protected CallGraph() {}
29 public CallGraph(State state) {
31 mapVirtual2ImplementationSet = new Hashtable();
32 mapCaller2CalleeSet = new Hashtable();
33 mapCallee2CallerSet = new Hashtable();
38 // this method returns the set of Descriptors
39 // (MethodDescriptors and/or TaskDescriptors)
40 // that call the given method
41 public Set getCallerSet(MethodDescriptor md) {
42 Set s = (Set) mapCallee2CallerSet.get(md);
50 // this method returns the set of MethodDescriptors that
51 // are called by the given method or task
52 public Set getCalleeSet(Descriptor d) {
53 assert(d instanceof MethodDescriptor) ||
54 (d instanceof TaskDescriptor);
56 Set s = (Set) mapCaller2CalleeSet.get(d);
64 // build a mapping of virtual methods to all
65 // possible implementations of that method
66 protected void buildVirtualMap() {
67 //Iterator through classes
68 Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
70 ClassDescriptor cn=(ClassDescriptor)it.next();
71 Iterator methodit=cn.getMethods();
72 //Iterator through methods
73 while(methodit.hasNext()) {
74 MethodDescriptor md=(MethodDescriptor)methodit.next();
75 if (md.isStatic()||md.getReturnType()==null)
77 ClassDescriptor superdesc=cn.getSuperDesc();
78 if (superdesc!=null) {
79 Set possiblematches=superdesc.getMethodTable().getSet(md.getSymbol());
80 boolean foundmatch=false;
81 for(Iterator matchit=possiblematches.iterator(); matchit.hasNext();) {
82 MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
83 if (md.matches(matchmd)) {
84 if (!mapVirtual2ImplementationSet.containsKey(matchmd))
85 mapVirtual2ImplementationSet.put(matchmd,new HashSet());
86 ((HashSet)mapVirtual2ImplementationSet.get(matchmd)).add(md);
95 public Set getMethods(MethodDescriptor md, TypeDescriptor type) {
96 return getMethods(md);
99 /** Given a call to MethodDescriptor, lists the methods which
100 could actually be called due to virtual dispatch. */
101 public Set getMethods(MethodDescriptor md) {
102 HashSet ns=new HashSet();
104 Set s=(Set)mapVirtual2ImplementationSet.get(md);
106 for(Iterator it=s.iterator(); it.hasNext();) {
107 MethodDescriptor md2=(MethodDescriptor)it.next();
108 ns.addAll(getMethods(md2));
113 /** Given a call to MethodDescriptor, lists the methods which
114 could actually be call by that method. */
115 public Set getMethodCalls(TaskDescriptor td) {
116 return getMethodCalls( (Descriptor) td);
119 public Set getMethodCalls(MethodDescriptor md) {
120 return getMethodCalls( (Descriptor) md);
123 public Set getMethodCalls(Descriptor d) {
124 assert d instanceof MethodDescriptor ||
125 d instanceof TaskDescriptor;
127 HashSet ns=new HashSet();
129 return getMoreMethodCalls(ns, d);
132 private Set getMoreMethodCalls(HashSet found, Descriptor d) {
133 HashSet ns=new HashSet();
136 Set s=(Set)mapCaller2CalleeSet.get(d);
138 for(Iterator it=s.iterator(); it.hasNext();) {
139 MethodDescriptor md=(MethodDescriptor)it.next();
140 if( !found.contains(md) ) {
141 ns.addAll(getMoreMethodCalls(found, md));
147 /** Returns all methods transitively callable from d */
149 public Set getAllMethods(Descriptor d) {
150 HashSet tovisit=new HashSet();
152 HashSet callable=new HashSet();
153 while(!tovisit.isEmpty()) {
154 Descriptor md=(Descriptor)tovisit.iterator().next();
156 Set s=(Set)mapCaller2CalleeSet.get(md);
158 for(Iterator it=s.iterator(); it.hasNext();) {
159 MethodDescriptor md2=(MethodDescriptor)it.next();
160 if( !callable.contains(md2) ) {
170 // Returns a set of methods containing SESEs and located at the first
171 // in transitive call chain starting from d
172 public Set getFirstReachableMethodContainingSESE(Descriptor d,
173 Set<MethodDescriptor> methodsContainingSESEs) {
174 HashSet tovisit = new HashSet();
176 HashSet callable = new HashSet();
177 while (!tovisit.isEmpty()) {
178 Descriptor md = (Descriptor) tovisit.iterator().next();
180 Set s = (Set) mapCaller2CalleeSet.get(md);
183 for (Iterator it = s.iterator(); it.hasNext();) {
184 MethodDescriptor md2 = (MethodDescriptor) it.next();
185 if (!callable.contains(md2)) {
187 if (!methodsContainingSESEs.contains(md2)) {
188 // if current method has sese, do not need to go down
195 // callable.retainAll(methodsContainingSESEs);
200 private void buildGraph() {
201 Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
202 while(it.hasNext()) {
203 ClassDescriptor cn=(ClassDescriptor)it.next();
204 Iterator methodit=cn.getMethods();
205 //Iterator through methods
206 while(methodit.hasNext()) {
207 MethodDescriptor md=(MethodDescriptor)methodit.next();
208 analyzeMethod( (Object)md, state.getMethodFlat(md) );
211 it=state.getTaskSymbolTable().getDescriptorsIterator();
212 while(it.hasNext()) {
213 TaskDescriptor td=(TaskDescriptor)it.next();
214 analyzeMethod( (Object)td, state.getMethodFlat(td) );
218 protected void analyzeMethod(Object caller, FlatMethod fm) {
219 HashSet toexplore=new HashSet();
221 HashSet explored=new HashSet();
222 //look at all the nodes in the flat representation
223 while(!toexplore.isEmpty()) {
224 FlatNode fn=(FlatNode)(toexplore.iterator()).next();
225 toexplore.remove(fn);
227 for(int i=0; i<fn.numNext(); i++) {
228 FlatNode fnnext=fn.getNext(i);
229 if (!explored.contains(fnnext))
230 toexplore.add(fnnext);
232 if (fn.kind()==FKind.FlatCall) {
233 FlatCall fc=(FlatCall)fn;
234 MethodDescriptor calledmethod=fc.getMethod();
235 Set methodsthatcouldbecalled=fc.getThis()==null ? getMethods(calledmethod) :
236 getMethods(calledmethod, fc.getThis().getType());
238 // add caller -> callee maps
239 if( !mapCaller2CalleeSet.containsKey(caller) ) {
240 mapCaller2CalleeSet.put(caller, new HashSet() );
242 ((HashSet)mapCaller2CalleeSet.get(caller)).addAll(methodsthatcouldbecalled);
244 // add callee -> caller maps
245 Iterator calleeItr = methodsthatcouldbecalled.iterator();
246 while( calleeItr.hasNext() ) {
247 MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
248 if( !mapCallee2CallerSet.containsKey(callee) ) {
249 mapCallee2CallerSet.put(callee, new HashSet() );
251 ((HashSet)mapCallee2CallerSet.get(callee)).add(caller);
258 public void writeVirtual2ImplemToDot(String graphName) throws java.io.IOException {
259 HashSet labeledInDot = new HashSet();
261 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
262 bw.write("digraph "+graphName+" {\n");
263 Iterator mapItr = mapVirtual2ImplementationSet.entrySet().iterator();
264 while( mapItr.hasNext() ) {
265 Map.Entry me = (Map.Entry)mapItr.next();
266 MethodDescriptor virtual = (MethodDescriptor) me.getKey();
267 HashSet implemSet = (HashSet) me.getValue();
269 if( !labeledInDot.contains(virtual) ) {
270 labeledInDot.add(virtual);
271 bw.write(" "+virtual.getNum()+"[label=\""+virtual+"\"];\n");
274 Iterator implemItr = implemSet.iterator();
275 while( implemItr.hasNext() ) {
276 Descriptor implem = (Descriptor) implemItr.next();
278 if( !labeledInDot.contains(implem) ) {
279 labeledInDot.add(implem);
280 bw.write(" "+implem.getNum()+"[label=\""+implem+"\"];\n");
283 bw.write(" "+virtual.getNum()+"->"+implem.getNum()+";\n");
291 public void writeCaller2CalleesToDot(String graphName) throws java.io.IOException {
292 // write out the call graph (should be equivalent) by
293 // using the callers mapping
294 HashSet labeledInDot = new HashSet();
295 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+"byCallers.dot") );
296 bw.write("digraph "+graphName+"byCallers {\n");
297 Iterator mapItr = mapCaller2CalleeSet.entrySet().iterator();
298 while( mapItr.hasNext() ) {
299 Map.Entry me = (Map.Entry)mapItr.next();
300 Descriptor caller = (Descriptor) me.getKey();
301 HashSet calleeSet = (HashSet) me.getValue();
303 if( !labeledInDot.contains(caller) ) {
304 labeledInDot.add(caller);
305 bw.write(" "+caller.getNum()+"[label=\"" +caller+"\"];\n");
308 Iterator calleeItr = calleeSet.iterator();
309 while( calleeItr.hasNext() ) {
310 MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
312 if( !labeledInDot.contains(callee) ) {
313 labeledInDot.add(callee);
314 bw.write(" "+callee.getNum()+"[label=\""+callee+"\"];\n");
317 bw.write(" "+caller.getNum()+"->"+callee.getNum()+";\n");
325 public void writeCallee2CallersToDot(String graphName) throws java.io.IOException {
326 // each task or method only needs to be labeled once
328 HashSet labeledInDot = new HashSet();
330 // write out the call graph using the callees mapping
331 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+"byCallees.dot") );
332 bw.write("digraph "+graphName+"byCallees {\n");
333 Iterator mapItr = mapCallee2CallerSet.entrySet().iterator();
334 while( mapItr.hasNext() ) {
335 Map.Entry me = (Map.Entry)mapItr.next();
336 MethodDescriptor callee = (MethodDescriptor) me.getKey();
337 HashSet callerSet = (HashSet) me.getValue();
339 if( !labeledInDot.contains(callee) ) {
340 labeledInDot.add(callee);
341 bw.write(" "+callee.getNum()+"[label=\""+callee+"\"];\n");
344 Iterator callerItr = callerSet.iterator();
345 while( callerItr.hasNext() ) {
346 Descriptor caller = (Descriptor) callerItr.next();
348 if( !labeledInDot.contains(caller) ) {
349 labeledInDot.add(caller);
350 bw.write(" "+caller.getNum()+"[label=\""+caller+"\"];\n");
353 bw.write(" "+caller.getNum()+"->"+callee.getNum()+";\n");