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(MethodDescriptor md) {
 104     HashSet ns=new HashSet();
 105     ns.add(md);
 106     Set s=(Set)mapCaller2CalleeSet.get(md);
 107     if (s!=null)
 108       for(Iterator it=s.iterator(); it.hasNext();) {
 109         MethodDescriptor md2=(MethodDescriptor)it.next();
 110         ns.addAll(getMethodCalls(md2));
 111       }
 112     return ns;
 113   }
 114
 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) );
 124       }
 125     }
 126     it=state.getTaskSymbolTable().getDescriptorsIterator();
 127     while(it.hasNext()) {
 128       TaskDescriptor td=(TaskDescriptor)it.next();
 129       analyzeMethod( (Object)td, state.getMethodFlat(td) );
 130     }
 131   }
 132
 133   private void analyzeMethod(Object caller, FlatMethod fm) {
 134     HashSet toexplore=new HashSet();
 135     toexplore.add(fm);
 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);
 141       explored.add(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);
 146       }
 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());
 152
 153         // add caller -> callee maps
 154         if( !mapCaller2CalleeSet.containsKey(caller) ) {
 155           mapCaller2CalleeSet.put(caller, new HashSet() );
 156         }
 157         ((HashSet)mapCaller2CalleeSet.get(caller)).addAll(methodsthatcouldbecalled);
 158
 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() );
 165           }
 166           ((HashSet)mapCallee2CallerSet.get(callee)).add(caller);
 167         }
 168       }
 169     }
 170   }
 171
 172   public void writeToDot(String graphName)  throws java.io.IOException {
 173     // each task or method only needs to be labeled once
 174     // in a dot file
 175     HashSet labeledInDot = new HashSet();
 176
 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();
 185
 186       if( !labeledInDot.contains(callee) ) {
 187         labeledInDot.add(callee);
 188         bw.write("  " + callee.getNum() + "[label=\"" + callee + "\"];\n");
 189       }
 190
 191       Iterator callerItr = callerSet.iterator();
 192       while( callerItr.hasNext() ) {
 193         Descriptor caller = (Descriptor) callerItr.next();
 194
 195         if( !labeledInDot.contains(caller) ) {
 196           labeledInDot.add(caller);
 197           bw.write("  " + caller.getNum() + "[label=\"" + caller + "\"];\n");
 198         }
 199
 200         bw.write("  " + callee.getNum() + "->" + caller.getNum() + ";\n");
 201       }
 202     }
 203     bw.write("}\n");
 204     bw.close();
 205
 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();
 216
 217       if( !labeledInDot.contains(caller) ) {
 218         labeledInDot.add(caller);
 219         bw.write("  " + caller.getNum() + "[label=\"" + caller + "\"];\n");
 220       }
 221
 222       Iterator calleeItr = calleeSet.iterator();
 223       while( calleeItr.hasNext() ) {
 224         MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
 225
 226         if( !labeledInDot.contains(callee) ) {
 227           labeledInDot.add(callee);
 228           bw.write("  " + callee.getNum() + "[label=\"" + callee + "\"];\n");
 229         }
 230
 231         bw.write("  " + callee.getNum() + "->" + caller.getNum() + ";\n");
 232       }
 233     }
 234     bw.write("}\n");
 235     bw.close();
 236   }
 237 }