Programming Languages Research Group: Git - IRC.git/blob

   1 package Analysis.CallGraph;
   2 import IR.State;
   3 import IR.Flat.FlatMethod;
   4 import IR.Flat.FlatNode;
   5 import IR.Flat.FlatCall;
   6 import IR.Flat.FKind;
   7 import IR.Descriptor;
   8 import IR.ClassDescriptor;
   9 import IR.MethodDescriptor;
  10 import IR.TaskDescriptor;
  11 import IR.TypeDescriptor;
  12 import java.util.*;
  13 import java.io.*;
  14
  15 public class CallGraph {
  16   private State state;
  17
  18   // MethodDescriptor maps to HashSet<MethodDescriptor>
  19   private Hashtable mapVirtual2ImplementationSet;
  20
  21   // MethodDescriptor or TaskDescriptor maps to HashSet<MethodDescriptor>
  22   private Hashtable mapCaller2CalleeSet;
  23
  24   // MethodDescriptor maps to HashSet<MethodDescriptor or TaskDescriptor>
  25   private Hashtable mapCallee2CallerSet;
  26
  27   public CallGraph(State state) {
  28     this.state=state;
  29     mapVirtual2ImplementationSet = new Hashtable();
  30     mapCaller2CalleeSet          = new Hashtable();
  31     mapCallee2CallerSet          = new Hashtable();
  32     buildVirtualMap();
  33     buildGraph();
  34   }
  35
  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);
  41   }
  42
  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);
  48
  49     return (Set) mapCaller2CalleeSet.get(d);
  50   }
  51
  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();
  57     while(it.hasNext()) {
  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)
  64           continue;
  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);
  75               break;
  76             }
  77           }
  78         }
  79       }
  80     }
  81   }
  82
  83   public Set getMethods(MethodDescriptor md, TypeDescriptor type) {
  84     return getMethods(md);
  85   }
  86
  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();
  91     ns.add(md);
  92     Set s=(Set)mapVirtual2ImplementationSet.get(md);
  93     if (s!=null)
  94       for(Iterator it=s.iterator(); it.hasNext();) {
  95         MethodDescriptor md2=(MethodDescriptor)it.next();
  96         ns.addAll(getMethods(md2));
  97       }
  98     return ns;
  99   }
 100
 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);
 105   }
 106
 107   public Set getMethodCalls(MethodDescriptor md) {
 108     return getMethodCalls( (Descriptor) md);
 109   }
 110
 111   public Set getMethodCalls(Descriptor d) {
 112     assert d instanceof MethodDescriptor ||
 113     d instanceof TaskDescriptor;
 114
 115     HashSet ns=new HashSet();
 116     ns.add(d);
 117     return getMoreMethodCalls(ns, d);
 118   }
 119
 120   private Set getMoreMethodCalls(HashSet found, Descriptor d) {
 121     HashSet ns=new HashSet();
 122     ns.add(d);
 123     found.add(d);
 124     Set s=(Set)mapCaller2CalleeSet.get(d);
 125     if (s!=null)
 126       for(Iterator it=s.iterator(); it.hasNext();) {
 127         MethodDescriptor md=(MethodDescriptor)it.next();
 128         if( !found.contains(md) ) {
 129           found.contains(md);
 130           ns.addAll(getMoreMethodCalls(found, md));
 131         }
 132       }
 133     return ns;
 134   }
 135
 136
 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) );
 146       }
 147     }
 148     it=state.getTaskSymbolTable().getDescriptorsIterator();
 149     while(it.hasNext()) {
 150       TaskDescriptor td=(TaskDescriptor)it.next();
 151       analyzeMethod( (Object)td, state.getMethodFlat(td) );
 152     }
 153   }
 154
 155   private void analyzeMethod(Object caller, FlatMethod fm) {
 156     HashSet toexplore=new HashSet();
 157     toexplore.add(fm);
 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);
 163       explored.add(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);
 168       }
 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());
 174
 175         // add caller -> callee maps
 176         if( !mapCaller2CalleeSet.containsKey(caller) ) {
 177           mapCaller2CalleeSet.put(caller, new HashSet() );
 178         }
 179         ((HashSet)mapCaller2CalleeSet.get(caller)).addAll(methodsthatcouldbecalled);
 180
 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() );
 187           }
 188           ((HashSet)mapCallee2CallerSet.get(callee)).add(caller);
 189         }
 190       }
 191     }
 192   }
 193
 194
 195   public void writeVirtual2ImplemToDot(String graphName)  throws java.io.IOException {
 196     HashSet labeledInDot = new HashSet();
 197
 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();
 205
 206       if( !labeledInDot.contains(virtual) ) {
 207         labeledInDot.add(virtual);
 208         bw.write("  "+virtual.getNum()+"[label=\""+virtual+"\"];\n");
 209       }
 210
 211       Iterator implemItr = implemSet.iterator();
 212       while( implemItr.hasNext() ) {
 213         Descriptor implem = (Descriptor) implemItr.next();
 214
 215         if( !labeledInDot.contains(implem) ) {
 216           labeledInDot.add(implem);
 217           bw.write("  "+implem.getNum()+"[label=\""+implem+"\"];\n");
 218         }
 219
 220         bw.write("  "+virtual.getNum()+"->"+implem.getNum()+";\n");
 221       }
 222     }
 223     bw.write("}\n");
 224     bw.close();
 225   }
 226
 227
 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();
 239
 240       if( !labeledInDot.contains(caller) ) {
 241         labeledInDot.add(caller);
 242         bw.write("  "+caller.getNum()+"[label=\"" +caller+"\"];\n");
 243       }
 244
 245       Iterator calleeItr = calleeSet.iterator();
 246       while( calleeItr.hasNext() ) {
 247         MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
 248
 249         if( !labeledInDot.contains(callee) ) {
 250           labeledInDot.add(callee);
 251           bw.write("  "+callee.getNum()+"[label=\""+callee+"\"];\n");
 252         }
 253
 254         bw.write("  "+caller.getNum()+"->"+callee.getNum()+";\n");
 255       }
 256     }
 257     bw.write("}\n");
 258     bw.close();
 259   }
 260
 261
 262   public void writeCallee2CallersToDot(String graphName)  throws java.io.IOException {
 263     // each task or method only needs to be labeled once
 264     // in a dot file
 265     HashSet labeledInDot = new HashSet();
 266
 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();
 275
 276       if( !labeledInDot.contains(callee) ) {
 277         labeledInDot.add(callee);
 278         bw.write("  "+callee.getNum()+"[label=\""+callee+"\"];\n");
 279       }
 280
 281       Iterator callerItr = callerSet.iterator();
 282       while( callerItr.hasNext() ) {
 283         Descriptor caller = (Descriptor) callerItr.next();
 284
 285         if( !labeledInDot.contains(caller) ) {
 286           labeledInDot.add(caller);
 287           bw.write("  "+caller.getNum()+"[label=\""+caller+"\"];\n");
 288         }
 289
 290         bw.write("  "+caller.getNum()+"->"+callee.getNum()+";\n");
 291       }
 292     }
 293     bw.write("}\n");
 294     bw.close();
 295   }
 296 }