Robust/src/Analysis/Locality/TypeAnalysis.java

   1 package Analysis.Locality;
   2
   3 import IR.Flat.*;
   4 import java.util.Set;
   5 import java.util.Arrays;
   6 import java.util.HashSet;
   7 import java.util.Iterator;
   8 import java.util.Hashtable;
   9 import Analysis.CallGraph.CallGraph;
  10 import IR.State;
  11 import IR.TypeUtil;
  12 import IR.Operation;
  13 import IR.TypeDescriptor;
  14 import IR.MethodDescriptor;
  15 import IR.FieldDescriptor;
  16
  17 public class TypeAnalysis {
  18   /* This analysis is essentially a dataflow analysis.
  19    */
  20   LocalityAnalysis locality;
  21   State state;
  22   TypeUtil typeutil;
  23   CallGraph cg;
  24   Hashtable<TypeDescriptor, Set<TypeDescriptor>> map;
  25   HashSet<TypeDescriptor> roottypes;
  26   Hashtable<TypeDescriptor, Set<TypeDescriptor>> transmap;
  27   Hashtable<TypeDescriptor, Set<TypeDescriptor>> namemap;
  28
  29   public TypeAnalysis(LocalityAnalysis locality, State state, TypeUtil typeutil, CallGraph cg) {
  30     this.state=state;
  31     this.locality=locality;
  32     this.typeutil=typeutil;
  33     this.cg=cg;
  34     map=new Hashtable<TypeDescriptor, Set<TypeDescriptor>>();
  35     transmap=new Hashtable<TypeDescriptor, Set<TypeDescriptor>>();
  36     namemap=new Hashtable<TypeDescriptor, Set<TypeDescriptor>>();
  37     roottypes=new HashSet<TypeDescriptor>();
  38     doAnalysis();
  39   }
  40
  41   /* We use locality bindings to get calleable methods.  This could be
  42    * changed to use the callgraph starting from the main method. */
  43
  44   void doAnalysis() {
  45     Set<LocalityBinding> localityset=locality.getLocalityBindings();
  46     for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
  47       computeTypes(lb.next().getMethod());
  48     }
  49     computeTrans();
  50     computeOtherNames();
  51   }
  52
  53   void computeOtherNames() {
  54     for(Iterator<TypeDescriptor> it=transmap.keySet().iterator();it.hasNext();) {
  55       TypeDescriptor td=it.next();
  56       Set<TypeDescriptor> set=transmap.get(td);
  57       for(Iterator<TypeDescriptor> it2=set.iterator();it2.hasNext();) {
  58         TypeDescriptor type=it2.next();
  59         if (!namemap.containsKey(type))
  60           namemap.put(type, new HashSet<TypeDescriptor>());
  61         namemap.get(type).addAll(set);
  62       }
  63     }
  64   }
  65
  66   void computeTrans() {
  67     //Idea: for each type we want to know all of the possible types it could be called
  68     for(Iterator<TypeDescriptor> it=roottypes.iterator();it.hasNext();) {
  69       TypeDescriptor td=it.next();
  70       HashSet<TypeDescriptor> tovisit=new HashSet<TypeDescriptor>();
  71       transmap.put(td, new HashSet<TypeDescriptor>());
  72       tovisit.add(td);
  73       transmap.get(td).add(td);
  74
  75       while(!tovisit.isEmpty()) {
  76         TypeDescriptor type=tovisit.iterator().next();
  77         tovisit.remove(type);
  78         //Is type a supertype of td...if not skip along
  79         if (!typeutil.isSuperorType(type,td))
  80           continue;
  81         //Check if we have seen it before
  82         if (!transmap.get(td).contains(type)) {
  83           //If not, add to set and continue processing
  84           transmap.get(td).add(type);
  85           tovisit.add(type);
  86         }
  87       }
  88     }
  89   }
  90
  91   public Set<TypeDescriptor> expand(TypeDescriptor td) {
  92     return namemap.get(td);
  93   }
  94
  95   public void addMapping(TypeDescriptor src, TypeDescriptor dst) {
  96     if (!map.containsKey(src))
  97       map.put(src, new HashSet<TypeDescriptor>());
  98     map.get(src).add(dst);
  99   }
 100
 101   void computeTypes(MethodDescriptor md) {
 102     FlatMethod fm=state.getMethodFlat(md);
 103     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 104       FlatNode fn=fnit.next();
 105       switch(fn.kind()) {
 106       case FKind.FlatOpNode: {
 107         FlatOpNode fon=(FlatOpNode)fn;
 108         if(fon.getOp().getOp()==Operation.ASSIGN) {
 109           addMapping(fon.getLeft().getType(),fon.getDest().getType());
 110         }
 111         break;
 112       }
 113       case FKind.FlatNew: {
 114         FlatNew fnew=(FlatNew)fn;
 115         roottypes.add(fnew.getType());
 116         break;
 117       }
 118       case FKind.FlatCastNode: {
 119         FlatCastNode fcn=(FlatCastNode)fn;
 120         addMapping(fcn.getSrc().getType(), fcn.getDst().getType());
 121         break;
 122       }
 123       case FKind.FlatFieldNode: {
 124         FlatFieldNode ffn=(FlatFieldNode)fn;
 125         addMapping(ffn.getField().getType(), ffn.getDst().getType());
 126         break;
 127       }
 128       case FKind.FlatSetFieldNode: {
 129         FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
 130         addMapping(fsfn.getSrc().getType(), fsfn.getField().getType());
 131         break;
 132       }
 133       case FKind.FlatElementNode: {
 134         FlatElementNode fen=(FlatElementNode)fn;
 135         addMapping(fen.getSrc().getType().dereference(), fen.getDst().getType());
 136         break;
 137       }
 138       case FKind.FlatSetElementNode: {
 139         FlatSetElementNode fsen=(FlatSetElementNode)fn;
 140         addMapping(fsen.getSrc().getType(), fsen.getDst().getType().dereference());
 141         break;
 142       }
 143       case FKind.FlatCall: {
 144         FlatCall fc=(FlatCall)fn;
 145         if (fc.getReturnTemp()!=null) {
 146           addMapping(fc.getMethod().getReturnType(), fc.getReturnTemp().getType());
 147         }
 148         if (fc.getThis()!=null) {
 149           //complicated...need to deal with virtual dispatch here
 150           MethodDescriptor callmd=fc.getMethod();
 151           Set methods=cg.getMethods(callmd);
 152           for(Iterator mdit=methods.iterator();mdit.hasNext();) {
 153             MethodDescriptor md2=(MethodDescriptor)mdit.next();
 154             if (fc.getThis()!=null) {
 155               TypeDescriptor ttype=new TypeDescriptor(md2.getClassDesc());
 156               if (!typeutil.isSuperorType(fc.getThis().getType(),ttype)&&
 157                   !typeutil.isSuperorType(ttype,fc.getThis().getType()))
 158                 continue;
 159               addMapping(fc.getThis().getType(), ttype);
 160             }
 161           }
 162         }
 163         for(int i=0;i<fc.numArgs();i++) {
 164           TempDescriptor arg=fc.getArg(i);
 165           TypeDescriptor ptype=md.getParamType(i);
 166           addMapping(arg.getType(), ptype);
 167         }
 168         break;
 169       }
 170         //both inputs and output
 171       case FKind.FlatReturnNode: {
 172         FlatReturnNode frn=(FlatReturnNode) fn;
 173         if (frn.getReturnTemp()!=null)
 174           addMapping(frn.getReturnTemp().getType(), md.getReturnType());
 175       }
 176       }
 177     }
 178   }
 179
 180 }