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
 132       case FKind.FlatNew: {
 133         FlatNew fnew=(FlatNew)fn;
 134         roottypes.add(fnew.getType());
 135         break;
 136       }
 137
 138       case FKind.FlatCastNode: {
 139         FlatCastNode fcn=(FlatCastNode)fn;
 140         addMapping(fcn.getSrc().getType(), fcn.getDst().getType());
 141         break;
 142       }
 143
 144       case FKind.FlatFieldNode: {
 145         FlatFieldNode ffn=(FlatFieldNode)fn;
 146         addMapping(ffn.getField().getType(), ffn.getDst().getType());
 147         break;
 148       }
 149
 150       case FKind.FlatSetFieldNode: {
 151         FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
 152         addMapping(fsfn.getSrc().getType(), fsfn.getField().getType());
 153         break;
 154       }
 155
 156       case FKind.FlatElementNode: {
 157         FlatElementNode fen=(FlatElementNode)fn;
 158         addMapping(fen.getSrc().getType().dereference(), fen.getDst().getType());
 159         break;
 160       }
 161
 162       case FKind.FlatSetElementNode: {
 163         FlatSetElementNode fsen=(FlatSetElementNode)fn;
 164         addMapping(fsen.getSrc().getType(), fsen.getDst().getType().dereference());
 165         break;
 166       }
 167
 168       case FKind.FlatCall: {
 169         FlatCall fc=(FlatCall)fn;
 170         if (fc.getReturnTemp()!=null) {
 171           addMapping(fc.getMethod().getReturnType(), fc.getReturnTemp().getType());
 172         }
 173         MethodDescriptor callmd=fc.getMethod();
 174         if (fc.getThis()!=null) {
 175           //complicated...need to deal with virtual dispatch here
 176           Set methods=cg.getMethods(callmd);
 177           for(Iterator mdit=methods.iterator(); mdit.hasNext(); ) {
 178             MethodDescriptor md2=(MethodDescriptor)mdit.next();
 179             if (fc.getThis()!=null) {
 180               TypeDescriptor ttype=new TypeDescriptor(md2.getClassDesc());
 181               if (!typeutil.isSuperorType(fc.getThis().getType(),ttype)&&
 182                   !typeutil.isSuperorType(ttype,fc.getThis().getType()))
 183                 continue;
 184               addMapping(fc.getThis().getType(), ttype);
 185             }
 186           }
 187         }
 188         for(int i=0; i<fc.numArgs(); i++) {
 189           TempDescriptor arg=fc.getArg(i);
 190           TypeDescriptor ptype=callmd.getParamType(i);
 191           addMapping(arg.getType(), ptype);
 192         }
 193         break;
 194       }
 195
 196       //both inputs and output
 197       case FKind.FlatReturnNode: {
 198         FlatReturnNode frn=(FlatReturnNode) fn;
 199         if (frn.getReturnTemp()!=null)
 200           addMapping(frn.getReturnTemp().getType(), md.getReturnType());
 201       }
 202       }
 203     }
 204   }
 205
 206 }