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 {
18 // MethodDescriptor maps to HashSet<MethodDescriptor>
19 private Hashtable mapVirtual2ImplementationSet;
21 // MethodDescriptor or TaskDescriptor maps to HashSet<MethodDescriptor>
22 private Hashtable mapCaller2CalleeSet;
24 // MethodDescriptor maps to HashSet<MethodDescriptor or TaskDescriptor>
25 private Hashtable mapCallee2CallerSet;
27 public CallGraph(State state) {
29 mapVirtual2ImplementationSet = new Hashtable();
30 mapCaller2CalleeSet = new Hashtable();
31 mapCallee2CallerSet = new Hashtable();
36 // this method returns the set of Descriptors
37 // (MethodDescriptors and/or TaskDescriptors)
38 // that call the given method
39 public Set getCallerSet(MethodDescriptor md) {
40 return (Set) mapCallee2CallerSet.get(md);
43 // this method returns the set of MethodDescriptors that
44 // are called by the given method or task
45 public Set getCalleeSet(Descriptor d) {
46 assert(d instanceof MethodDescriptor) ||
47 (d instanceof TaskDescriptor);
49 return (Set) mapCaller2CalleeSet.get(d);
52 // build a mapping of virtual methods to all
53 // possible implementations of that method
54 private void buildVirtualMap() {
55 //Iterator through classes
56 Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
58 ClassDescriptor cn=(ClassDescriptor)it.next();
59 Iterator methodit=cn.getMethods();
60 //Iterator through methods
61 while(methodit.hasNext()) {
62 MethodDescriptor md=(MethodDescriptor)methodit.next();
63 if (md.isStatic()||md.getReturnType()==null)
65 ClassDescriptor superdesc=cn.getSuperDesc();
66 if (superdesc!=null) {
67 Set possiblematches=superdesc.getMethodTable().getSet(md.getSymbol());
68 boolean foundmatch=false;
69 for(Iterator matchit=possiblematches.iterator(); matchit.hasNext();) {
70 MethodDescriptor matchmd=(MethodDescriptor)matchit.next();
71 if (md.matches(matchmd)) {
72 if (!mapVirtual2ImplementationSet.containsKey(matchmd))
73 mapVirtual2ImplementationSet.put(matchmd,new HashSet());
74 ((HashSet)mapVirtual2ImplementationSet.get(matchmd)).add(md);
83 public Set getMethods(MethodDescriptor md, TypeDescriptor type) {
84 return getMethods(md);
87 /** Given a call to MethodDescriptor, lists the methods which
88 could actually be called due to virtual dispatch. */
89 public Set getMethods(MethodDescriptor md) {
90 HashSet ns=new HashSet();
92 Set s=(Set)mapVirtual2ImplementationSet.get(md);
94 for(Iterator it=s.iterator(); it.hasNext();) {
95 MethodDescriptor md2=(MethodDescriptor)it.next();
96 ns.addAll(getMethods(md2));
101 /** Given a call to MethodDescriptor, lists the methods which
102 could actually be call by that method. */
103 public Set getMethodCalls(TaskDescriptor td) {
104 return getMethodCalls( (Descriptor) td);
107 public Set getMethodCalls(MethodDescriptor md) {
108 return getMethodCalls( (Descriptor) md);
111 public Set getMethodCalls(Descriptor d) {
112 assert d instanceof MethodDescriptor ||
113 d instanceof TaskDescriptor;
115 HashSet ns=new HashSet();
117 return getMoreMethodCalls(ns, d);
120 private Set getMoreMethodCalls(HashSet found, Descriptor d) {
121 HashSet ns=new HashSet();
124 Set s=(Set)mapCaller2CalleeSet.get(d);
126 for(Iterator it=s.iterator(); it.hasNext();) {
127 MethodDescriptor md=(MethodDescriptor)it.next();
128 if( !found.contains(md) ) {
130 ns.addAll(getMoreMethodCalls(found, md));
137 private void buildGraph() {
138 Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
139 while(it.hasNext()) {
140 ClassDescriptor cn=(ClassDescriptor)it.next();
141 Iterator methodit=cn.getMethods();
142 //Iterator through methods
143 while(methodit.hasNext()) {
144 MethodDescriptor md=(MethodDescriptor)methodit.next();
145 analyzeMethod( (Object)md, state.getMethodFlat(md) );
148 it=state.getTaskSymbolTable().getDescriptorsIterator();
149 while(it.hasNext()) {
150 TaskDescriptor td=(TaskDescriptor)it.next();
151 analyzeMethod( (Object)td, state.getMethodFlat(td) );
155 private void analyzeMethod(Object caller, FlatMethod fm) {
156 HashSet toexplore=new HashSet();
158 HashSet explored=new HashSet();
159 //look at all the nodes in the flat representation
160 while(!toexplore.isEmpty()) {
161 FlatNode fn=(FlatNode)(toexplore.iterator()).next();
162 toexplore.remove(fn);
164 for(int i=0; i<fn.numNext(); i++) {
165 FlatNode fnnext=fn.getNext(i);
166 if (!explored.contains(fnnext))
167 toexplore.add(fnnext);
169 if (fn.kind()==FKind.FlatCall) {
170 FlatCall fc=(FlatCall)fn;
171 MethodDescriptor calledmethod=fc.getMethod();
172 Set methodsthatcouldbecalled=fc.getThis()==null ? getMethods(calledmethod) :
173 getMethods(calledmethod, fc.getThis().getType());
175 // add caller -> callee maps
176 if( !mapCaller2CalleeSet.containsKey(caller) ) {
177 mapCaller2CalleeSet.put(caller, new HashSet() );
179 ((HashSet)mapCaller2CalleeSet.get(caller)).addAll(methodsthatcouldbecalled);
181 // add callee -> caller maps
182 Iterator calleeItr = methodsthatcouldbecalled.iterator();
183 while( calleeItr.hasNext() ) {
184 MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
185 if( !mapCallee2CallerSet.containsKey(callee) ) {
186 mapCallee2CallerSet.put(callee, new HashSet() );
188 ((HashSet)mapCallee2CallerSet.get(callee)).add(caller);
195 public void writeVirtual2ImplemToDot(String graphName) throws java.io.IOException {
196 HashSet labeledInDot = new HashSet();
198 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
199 bw.write("digraph "+graphName+" {\n");
200 Iterator mapItr = mapVirtual2ImplementationSet.entrySet().iterator();
201 while( mapItr.hasNext() ) {
202 Map.Entry me = (Map.Entry)mapItr.next();
203 MethodDescriptor virtual = (MethodDescriptor) me.getKey();
204 HashSet implemSet = (HashSet) me.getValue();
206 if( !labeledInDot.contains(virtual) ) {
207 labeledInDot.add(virtual);
208 bw.write(" "+virtual.getNum()+"[label=\""+virtual+"\"];\n");
211 Iterator implemItr = implemSet.iterator();
212 while( implemItr.hasNext() ) {
213 Descriptor implem = (Descriptor) implemItr.next();
215 if( !labeledInDot.contains(implem) ) {
216 labeledInDot.add(implem);
217 bw.write(" "+implem.getNum()+"[label=\""+implem+"\"];\n");
220 bw.write(" "+virtual.getNum()+"->"+implem.getNum()+";\n");
228 public void writeCaller2CalleesToDot(String graphName) throws java.io.IOException {
229 // write out the call graph (should be equivalent) by
230 // using the callers mapping
231 HashSet labeledInDot = new HashSet();
232 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+"byCallers.dot") );
233 bw.write("digraph "+graphName+"byCallers {\n");
234 Iterator mapItr = mapCaller2CalleeSet.entrySet().iterator();
235 while( mapItr.hasNext() ) {
236 Map.Entry me = (Map.Entry)mapItr.next();
237 Descriptor caller = (Descriptor) me.getKey();
238 HashSet calleeSet = (HashSet) me.getValue();
240 if( !labeledInDot.contains(caller) ) {
241 labeledInDot.add(caller);
242 bw.write(" "+caller.getNum()+"[label=\"" +caller+"\"];\n");
245 Iterator calleeItr = calleeSet.iterator();
246 while( calleeItr.hasNext() ) {
247 MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
249 if( !labeledInDot.contains(callee) ) {
250 labeledInDot.add(callee);
251 bw.write(" "+callee.getNum()+"[label=\""+callee+"\"];\n");
254 bw.write(" "+caller.getNum()+"->"+callee.getNum()+";\n");
262 public void writeCallee2CallersToDot(String graphName) throws java.io.IOException {
263 // each task or method only needs to be labeled once
265 HashSet labeledInDot = new HashSet();
267 // write out the call graph using the callees mapping
268 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+"byCallees.dot") );
269 bw.write("digraph "+graphName+"byCallees {\n");
270 Iterator mapItr = mapCallee2CallerSet.entrySet().iterator();
271 while( mapItr.hasNext() ) {
272 Map.Entry me = (Map.Entry)mapItr.next();
273 MethodDescriptor callee = (MethodDescriptor) me.getKey();
274 HashSet callerSet = (HashSet) me.getValue();
276 if( !labeledInDot.contains(callee) ) {
277 labeledInDot.add(callee);
278 bw.write(" "+callee.getNum()+"[label=\""+callee+"\"];\n");
281 Iterator callerItr = callerSet.iterator();
282 while( callerItr.hasNext() ) {
283 Descriptor caller = (Descriptor) callerItr.next();
285 if( !labeledInDot.contains(caller) ) {
286 labeledInDot.add(caller);
287 bw.write(" "+caller.getNum()+"[label=\""+caller+"\"];\n");
290 bw.write(" "+caller.getNum()+"->"+callee.getNum()+";\n");