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