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