Robust/src/Analysis/Loops/GlobalFieldType.java

   1 package Analysis.Loops;
   2
   3 import IR.Flat.*;
   4 import IR.State;
   5 import IR.TypeUtil;
   6 import IR.MethodDescriptor;
   7 import IR.FieldDescriptor;
   8 import IR.TypeDescriptor;
   9 import Analysis.CallGraph.*;
  10 import java.util.Iterator;
  11 import java.util.HashSet;
  12 import java.util.Hashtable;
  13 import java.util.Set;
  14
  15 public class GlobalFieldType {
  16   CallGraph cg;
  17   State st;
  18   MethodDescriptor root;
  19   Hashtable<MethodDescriptor, Set<FieldDescriptor>> fields;
  20   Hashtable<MethodDescriptor, Set<TypeDescriptor>> arrays;
  21   Hashtable<MethodDescriptor, Set<FieldDescriptor>> fieldsrd;
  22   Hashtable<MethodDescriptor, Set<TypeDescriptor>> arraysrd;
  23   HashSet<MethodDescriptor> containsAtomic;
  24   HashSet<MethodDescriptor> containsBarrier;
  25
  26   public GlobalFieldType(CallGraph cg, State st, MethodDescriptor root) {
  27     this.cg=cg;
  28     this.st=st;
  29     this.root=root;
  30     this.fields=new Hashtable<MethodDescriptor, Set<FieldDescriptor>>();
  31     this.arrays=new Hashtable<MethodDescriptor, Set<TypeDescriptor>>();
  32     this.fieldsrd=new Hashtable<MethodDescriptor, Set<FieldDescriptor>>();
  33     this.arraysrd=new Hashtable<MethodDescriptor, Set<TypeDescriptor>>();
  34     this.containsAtomic=new HashSet<MethodDescriptor>();
  35     this.containsBarrier=new HashSet<MethodDescriptor>();
  36     doAnalysis();
  37   }
  38   private void doAnalysis() {
  39     HashSet toprocess=new HashSet();
  40     toprocess.add(root);
  41     HashSet discovered=new HashSet();
  42     discovered.add(root);
  43     while(!toprocess.isEmpty()) {
  44       MethodDescriptor md=(MethodDescriptor)toprocess.iterator().next();
  45       toprocess.remove(md);
  46       analyzeMethod(md);
  47       Set callees=cg.getCalleeSet(md);
  48       for(Iterator it=callees.iterator(); it.hasNext(); ) {
  49         MethodDescriptor md2=(MethodDescriptor)it.next();
  50         if (!discovered.contains(md2)) {
  51           discovered.add(md2);
  52           toprocess.add(md2);
  53         }
  54       }
  55       if (md.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&
  56           md.getSymbol().equals("start")&&!md.getModifiers().isStatic()&&
  57           md.numParameters()==0) {
  58         //start -> run link
  59         MethodDescriptor runmd=null;
  60         for(Iterator methodit=md.getClassDesc().getMethodTable().getSet("run").iterator(); methodit.hasNext(); ) {
  61           MethodDescriptor mdrun=(MethodDescriptor) methodit.next();
  62           if (mdrun.numParameters()!=0||mdrun.getModifiers().isStatic())
  63             continue;
  64           runmd=mdrun;
  65           break;
  66         }
  67         if (runmd!=null) {
  68           Set runmethodset=cg.getMethods(runmd);
  69           for(Iterator it=runmethodset.iterator(); it.hasNext(); ) {
  70             MethodDescriptor md2=(MethodDescriptor)it.next();
  71             if (!discovered.contains(md2)) {
  72               discovered.add(md2);
  73               toprocess.add(md2);
  74             }
  75           }
  76         } else throw new Error("Can't find run method");
  77       }
  78     }
  79     boolean changed=true;
  80     while(changed) {
  81       changed=false;
  82       for(Iterator it=discovered.iterator(); it.hasNext(); ) {
  83         MethodDescriptor md=(MethodDescriptor)it.next();
  84         Set callees=cg.getCalleeSet(md);
  85         for(Iterator cit=callees.iterator(); cit.hasNext(); ) {
  86           MethodDescriptor md2=(MethodDescriptor)cit.next();
  87           if (fields.get(md).addAll(fields.get(md2)))
  88             changed=true;
  89           if (arrays.get(md).addAll(arrays.get(md2)))
  90             changed=true;
  91           if (fieldsrd.get(md).addAll(fieldsrd.get(md2)))
  92             changed=true;
  93           if (arraysrd.get(md).addAll(arraysrd.get(md2)))
  94             changed=true;
  95           if (containsAtomic.contains(md2)) {
  96             if (containsAtomic.add(md))
  97               changed=true;
  98           }
  99           if (containsBarrier.contains(md2)) {
 100             if (containsBarrier.add(md))
 101               changed=true;
 102           }
 103         }
 104       }
 105     }
 106   }
 107
 108   public boolean containsAtomic(MethodDescriptor md) {
 109     return containsAtomic.contains(md);
 110   }
 111
 112   public boolean containsBarrier(MethodDescriptor md) {
 113     return containsBarrier.contains(md);
 114   }
 115
 116   public Set<FieldDescriptor> getFields(MethodDescriptor md) {
 117     return fields.get(md);
 118   }
 119
 120   public Set<TypeDescriptor> getArrays(MethodDescriptor md) {
 121     return arrays.get(md);
 122   }
 123
 124   public Set<FieldDescriptor> getFieldsRd(MethodDescriptor md) {
 125     return fieldsrd.get(md);
 126   }
 127
 128   public Set<TypeDescriptor> getArraysRd(MethodDescriptor md) {
 129     return arraysrd.get(md);
 130   }
 131
 132   public boolean containsAtomicAll(MethodDescriptor md) {
 133     Set methodset=cg.getMethods(md);
 134     for(Iterator it=methodset.iterator(); it.hasNext(); ) {
 135       MethodDescriptor md2=(MethodDescriptor)it.next();
 136       if (containsAtomic.contains(md2))
 137         return true;
 138     }
 139     return false;
 140   }
 141
 142   public boolean containsBarrierAll(MethodDescriptor md) {
 143     Set methodset=cg.getMethods(md);
 144     for(Iterator it=methodset.iterator(); it.hasNext(); ) {
 145       MethodDescriptor md2=(MethodDescriptor)it.next();
 146       if (containsBarrier.contains(md2))
 147         return true;
 148     }
 149     return false;
 150   }
 151
 152   public Set<FieldDescriptor> getFieldsAll(MethodDescriptor md) {
 153     HashSet<FieldDescriptor> s=new HashSet<FieldDescriptor>();
 154     Set methodset=cg.getMethods(md);
 155     for(Iterator it=methodset.iterator(); it.hasNext(); ) {
 156       MethodDescriptor md2=(MethodDescriptor)it.next();
 157       if (fields.containsKey(md2))
 158         s.addAll(fields.get(md2));
 159     }
 160     return s;
 161   }
 162
 163   public Set<TypeDescriptor> getArraysAll(MethodDescriptor md) {
 164     HashSet<TypeDescriptor> s=new HashSet<TypeDescriptor>();
 165     Set methodset=cg.getMethods(md);
 166     for(Iterator it=methodset.iterator(); it.hasNext(); ) {
 167       MethodDescriptor md2=(MethodDescriptor)it.next();
 168       if (arrays.containsKey(md2))
 169         s.addAll(arrays.get(md2));
 170     }
 171     return s;
 172   }
 173
 174   public Set<FieldDescriptor> getFieldsRdAll(MethodDescriptor md) {
 175     HashSet<FieldDescriptor> s=new HashSet<FieldDescriptor>();
 176     Set methodset=cg.getMethods(md);
 177     for(Iterator it=methodset.iterator(); it.hasNext(); ) {
 178       MethodDescriptor md2=(MethodDescriptor)it.next();
 179       if (fieldsrd.containsKey(md2))
 180         s.addAll(fieldsrd.get(md2));
 181     }
 182     return s;
 183   }
 184
 185   public Set<TypeDescriptor> getArraysRdAll(MethodDescriptor md) {
 186     HashSet<TypeDescriptor> s=new HashSet<TypeDescriptor>();
 187     Set methodset=cg.getMethods(md);
 188     for(Iterator it=methodset.iterator(); it.hasNext(); ) {
 189       MethodDescriptor md2=(MethodDescriptor)it.next();
 190       if (arraysrd.containsKey(md2))
 191         s.addAll(arraysrd.get(md2));
 192     }
 193     return s;
 194   }
 195
 196   public void analyzeMethod(MethodDescriptor md) {
 197     fields.put(md, new HashSet<FieldDescriptor>());
 198     arrays.put(md, new HashSet<TypeDescriptor>());
 199     fieldsrd.put(md, new HashSet<FieldDescriptor>());
 200     arraysrd.put(md, new HashSet<TypeDescriptor>());
 201
 202     FlatMethod fm=st.getMethodFlat(md);
 203     for(Iterator it=fm.getNodeSet().iterator(); it.hasNext(); ) {
 204       FlatNode fn=(FlatNode)it.next();
 205       if (fn.kind()==FKind.FlatSetElementNode) {
 206         FlatSetElementNode fsen=(FlatSetElementNode)fn;
 207         arrays.get(md).add(fsen.getDst().getType());
 208       } else if (fn.kind()==FKind.FlatElementNode) {
 209         FlatElementNode fen=(FlatElementNode)fn;
 210         arraysrd.get(md).add(fen.getSrc().getType());
 211       } else if (fn.kind()==FKind.FlatSetFieldNode) {
 212         FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 213         fields.get(md).add(fsfn.getField());
 214       } else if (fn.kind()==FKind.FlatFieldNode) {
 215         FlatFieldNode ffn=(FlatFieldNode)fn;
 216         fieldsrd.get(md).add(ffn.getField());
 217       } else if (fn.kind()==FKind.FlatAtomicEnterNode) {
 218         containsAtomic.add(md);
 219       } else if (fn.kind()==FKind.FlatCall) {
 220         MethodDescriptor mdcall=((FlatCall)fn).getMethod();
 221         if (mdcall.getSymbol().equals("enterBarrier")&&
 222             mdcall.getClassDesc().getSymbol().equals("Barrier")) {
 223           containsBarrier.add(md);
 224           containsBarrier.add(mdcall);
 225         }
 226         //treat lock acquire the same as a barrier
 227         if ((mdcall.getSymbol().equals("MonitorEnter")||mdcall.getSymbol().equals("MonitorExit")||mdcall.getSymbol().equals("wait"))&&
 228             mdcall.getClassDesc().getSymbol().equals("Object")) {
 229           containsBarrier.add(md);
 230           containsBarrier.add(mdcall);
 231         }
 232       }
 233     }
 234   }
 235 }