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(MethodDescriptor md) {
104 HashSet ns=new HashSet();
106 Set s=(Set)mapCaller2CalleeSet.get(md);
108 for(Iterator it=s.iterator();it.hasNext();) {
109 MethodDescriptor md2=(MethodDescriptor)it.next();
110 ns.addAll(getMethodCalls(md2));
115 private void buildGraph() {
116 Iterator it=state.getClassSymbolTable().getDescriptorsIterator();
117 while(it.hasNext()) {
118 ClassDescriptor cn=(ClassDescriptor)it.next();
119 Iterator methodit=cn.getMethods();
120 //Iterator through methods
121 while(methodit.hasNext()) {
122 MethodDescriptor md=(MethodDescriptor)methodit.next();
123 analyzeMethod( (Object)md, state.getMethodFlat(md) );
126 it=state.getTaskSymbolTable().getDescriptorsIterator();
127 while(it.hasNext()) {
128 TaskDescriptor td=(TaskDescriptor)it.next();
129 analyzeMethod( (Object)td, state.getMethodFlat(td) );
133 private void analyzeMethod(Object caller, FlatMethod fm) {
134 HashSet toexplore=new HashSet();
136 HashSet explored=new HashSet();
137 //look at all the nodes in the flat representation
138 while(!toexplore.isEmpty()) {
139 FlatNode fn=(FlatNode)(toexplore.iterator()).next();
140 toexplore.remove(fn);
142 for(int i=0;i<fn.numNext();i++) {
143 FlatNode fnnext=fn.getNext(i);
144 if (!explored.contains(fnnext))
145 toexplore.add(fnnext);
147 if (fn.kind()==FKind.FlatCall) {
148 FlatCall fc=(FlatCall)fn;
149 MethodDescriptor calledmethod=fc.getMethod();
150 Set methodsthatcouldbecalled=fc.getThis()==null?getMethods(calledmethod):
151 getMethods(calledmethod, fc.getThis().getType());
153 // add caller -> callee maps
154 if( !mapCaller2CalleeSet.containsKey( caller ) ) {
155 mapCaller2CalleeSet.put( caller, new HashSet() );
157 ((HashSet)mapCaller2CalleeSet.get( caller )).addAll( methodsthatcouldbecalled );
159 // add callee -> caller maps
160 Iterator calleeItr = methodsthatcouldbecalled.iterator();
161 while( calleeItr.hasNext() ) {
162 MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
163 if( !mapCallee2CallerSet.containsKey( callee ) ) {
164 mapCallee2CallerSet.put( callee, new HashSet() );
166 ((HashSet)mapCallee2CallerSet.get( callee )).add( caller );
172 public void writeToDot( String graphName ) throws java.io.IOException {
173 // each task or method only needs to be labeled once
175 HashSet labeledInDot = new HashSet();
177 // write out the call graph using the callees mapping
178 BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+"byCallees.dot" ) );
179 bw.write( "digraph "+graphName+"byCallees {\n" );
180 Iterator mapItr = mapCallee2CallerSet.entrySet().iterator();
181 while( mapItr.hasNext() ) {
182 Map.Entry me = (Map.Entry) mapItr.next();
183 MethodDescriptor callee = (MethodDescriptor) me.getKey();
184 HashSet callerSet = (HashSet) me.getValue();
186 if( !labeledInDot.contains( callee ) ) {
187 labeledInDot.add( callee );
188 bw.write( " " + callee.getNum() + "[label=\"" + callee + "\"];\n" );
191 Iterator callerItr = callerSet.iterator();
192 while( callerItr.hasNext() ) {
193 Descriptor caller = (Descriptor) callerItr.next();
195 if( !labeledInDot.contains( caller ) ) {
196 labeledInDot.add( caller );
197 bw.write( " " + caller.getNum() + "[label=\"" + caller + "\"];\n" );
200 bw.write( " " + callee.getNum() + "->" + caller.getNum() + ";\n" );
206 // write out the call graph (should be equivalent) by
207 // using the callers mapping
208 labeledInDot = new HashSet();
209 bw = new BufferedWriter( new FileWriter( graphName+"byCallers.dot" ) );
210 bw.write( "digraph "+graphName+"byCallers {\n" );
211 mapItr = mapCaller2CalleeSet.entrySet().iterator();
212 while( mapItr.hasNext() ) {
213 Map.Entry me = (Map.Entry) mapItr.next();
214 Descriptor caller = (Descriptor) me.getKey();
215 HashSet calleeSet = (HashSet) me.getValue();
217 if( !labeledInDot.contains( caller ) ) {
218 labeledInDot.add( caller );
219 bw.write( " " + caller.getNum() + "[label=\"" + caller + "\"];\n" );
222 Iterator calleeItr = calleeSet.iterator();
223 while( calleeItr.hasNext() ) {
224 MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
226 if( !labeledInDot.contains( callee ) ) {
227 labeledInDot.add( callee );
228 bw.write( " " + callee.getNum() + "[label=\"" + callee + "\"];\n" );
231 bw.write( " " + callee.getNum() + "->" + caller.getNum() + ";\n" );