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     Set<TypeDescriptor> expandset=namemap.get(td);
  93     return expandset;
  94   }
  95
  96   public Set<TypeDescriptor> expandSet(Set<TypeDescriptor> tdset) {
  97     HashSet<TypeDescriptor> expandedSet=new HashSet<TypeDescriptor>();
  98     for(Iterator<TypeDescriptor> it=tdset.iterator();it.hasNext();) {
  99       TypeDescriptor td=it.next();
 100       Set<TypeDescriptor> etdset=expand(td);
 101       if (etdset==null)
 102         expandedSet.add(td);
 103       else
 104         expandedSet.addAll(etdset);
 105     }
 106     return expandedSet;
 107   }
 108
 109   public boolean couldAlias(TypeDescriptor td1, TypeDescriptor td2) {
 110     return namemap.get(td1).contains(td2);
 111   }
 112
 113   public void addMapping(TypeDescriptor src, TypeDescriptor dst) {
 114     if (!map.containsKey(src))
 115       map.put(src, new HashSet<TypeDescriptor>());
 116     map.get(src).add(dst);
 117   }
 118
 119   void computeTypes(MethodDescriptor md) {
 120     FlatMethod fm=state.getMethodFlat(md);
 121     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 122       FlatNode fn=fnit.next();
 123       switch(fn.kind()) {
 124       case FKind.FlatOpNode: {
 125         FlatOpNode fon=(FlatOpNode)fn;
 126         if(fon.getOp().getOp()==Operation.ASSIGN) {
 127           addMapping(fon.getLeft().getType(),fon.getDest().getType());
 128         }
 129         break;
 130       }
 131       case FKind.FlatNew: {
 132         FlatNew fnew=(FlatNew)fn;
 133         roottypes.add(fnew.getType());
 134         break;
 135       }
 136       case FKind.FlatCastNode: {
 137         FlatCastNode fcn=(FlatCastNode)fn;
 138         addMapping(fcn.getSrc().getType(), fcn.getDst().getType());
 139         break;
 140       }
 141       case FKind.FlatFieldNode: {
 142         FlatFieldNode ffn=(FlatFieldNode)fn;
 143         addMapping(ffn.getField().getType(), ffn.getDst().getType());
 144         break;
 145       }
 146       case FKind.FlatSetFieldNode: {
 147         FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
 148         addMapping(fsfn.getSrc().getType(), fsfn.getField().getType());
 149         break;
 150       }
 151       case FKind.FlatElementNode: {
 152         FlatElementNode fen=(FlatElementNode)fn;
 153         addMapping(fen.getSrc().getType().dereference(), fen.getDst().getType());
 154         break;
 155       }
 156       case FKind.FlatSetElementNode: {
 157         FlatSetElementNode fsen=(FlatSetElementNode)fn;
 158         addMapping(fsen.getSrc().getType(), fsen.getDst().getType().dereference());
 159         break;
 160       }
 161       case FKind.FlatCall: {
 162         FlatCall fc=(FlatCall)fn;
 163         if (fc.getReturnTemp()!=null) {
 164           addMapping(fc.getMethod().getReturnType(), fc.getReturnTemp().getType());
 165         }
 166         MethodDescriptor callmd=fc.getMethod();
 167         if (fc.getThis()!=null) {
 168           //complicated...need to deal with virtual dispatch here
 169           Set methods=cg.getMethods(callmd);
 170           for(Iterator mdit=methods.iterator();mdit.hasNext();) {
 171             MethodDescriptor md2=(MethodDescriptor)mdit.next();
 172             if (fc.getThis()!=null) {
 173               TypeDescriptor ttype=new TypeDescriptor(md2.getClassDesc());
 174               if (!typeutil.isSuperorType(fc.getThis().getType(),ttype)&&
 175                   !typeutil.isSuperorType(ttype,fc.getThis().getType()))
 176                 continue;
 177               addMapping(fc.getThis().getType(), ttype);
 178             }
 179           }
 180         }
 181         for(int i=0;i<fc.numArgs();i++) {
 182           TempDescriptor arg=fc.getArg(i);
 183           TypeDescriptor ptype=callmd.getParamType(i);
 184           addMapping(arg.getType(), ptype);
 185         }
 186         break;
 187       }
 188         //both inputs and output
 189       case FKind.FlatReturnNode: {
 190         FlatReturnNode frn=(FlatReturnNode) fn;
 191         if (frn.getReturnTemp()!=null)
 192           addMapping(frn.getReturnTemp().getType(), md.getReturnType());
 193       }
 194       }
 195     }
 196   }
 197
 198 }