Robust/src/Analysis/Locality/DelayComputation.java

   1 package Analysis.Locality;
   2 import IR.State;
   3 import IR.MethodDescriptor;
   4 import IR.TypeDescriptor;
   5 import IR.FieldDescriptor;
   6 import IR.Flat.*;
   7 import Analysis.Loops.GlobalFieldType;
   8 import java.util.HashSet;
   9 import java.util.Hashtable;
  10 import java.util.Set;
  11 import java.util.Iterator;
  12
  13 public class DelayComputation {
  14   State state;
  15   LocalityAnalysis locality;
  16   TypeAnalysis typeanalysis;
  17   GlobalFieldType gft;
  18
  19   public DelayComputation(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
  20     this.locality=locality;
  21     this.state=state;
  22     this.typeanalysis=typeanalysis;
  23     this.gft=gft;
  24   }
  25
  26   public void doAnalysis() {
  27     Set<LocalityBinding> localityset=locality.getLocalityBindings();
  28     for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
  29       analyzeMethod(lb.next());
  30     }
  31   }
  32
  33   public void analyzeMethod(LocalityBinding lb) {
  34     MethodDescriptor md=lb.getMethod();
  35     FlatMethod fm=state.getMethodFlat(md);
  36     HashSet<FlatNode> cannotdelay=new HashSet<FlatNode>();
  37     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
  38     if (lb.isAtomic()) {
  39       //We are in a transaction already...
  40       //skip past this method or something
  41       return;
  42     }
  43
  44     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
  45     toanalyze.addAll(fm.getNodeSet());
  46
  47     //Build the hashtables
  48     Hashtable<FlatNode, HashSet<TempDescriptor>> nodelaytemps=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
  49     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldswr=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
  50     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarrayswr=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
  51     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldsrd=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
  52     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarraysrd=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
  53
  54     //Effect of adding something to nodelay set is to move it up past everything in delay set
  55     //Have to make sure we can do this commute
  56
  57     while(!toanalyze.isEmpty()) {
  58       FlatNode fn=toanalyze.iterator().next();
  59       toanalyze.remove(fn);
  60
  61       boolean isatomic=atomictable.get(fn).intValue()>0;
  62
  63       if (!isatomic)
  64         continue;
  65       boolean isnodelay=false;
  66
  67       /* Compute incoming nodelay sets */
  68       HashSet<TempDescriptor> nodelaytempset=new HashSet<TempDescriptor>();
  69       HashSet<FieldDescriptor> nodelayfieldwrset=new HashSet<FieldDescriptor>();
  70       HashSet<TypeDescriptor> nodelayarraywrset=new HashSet<TypeDescriptor>();
  71       HashSet<FieldDescriptor> nodelayfieldrdset=new HashSet<FieldDescriptor>();
  72       HashSet<TypeDescriptor> nodelayarrayrdset=new HashSet<TypeDescriptor>();
  73       for(int i=0;i<fn.numNext();i++) {
  74         if (nodelaytemps.containsKey(fn.getNext(i)))
  75           nodelaytempset.addAll(nodelaytemps.get(fn.getNext(i)));
  76         //do field/array write sets
  77         if (nodelayfieldswr.containsKey(fn.getNext(i)))
  78           nodelayfieldwrset.addAll(nodelayfieldswr.get(fn.getNext(i)));
  79         if (nodelayarrayswr.containsKey(fn.getNext(i)))
  80           nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
  81         //do read sets
  82         if (nodelayfieldsrd.containsKey(fn.getNext(i)))
  83           nodelayfieldrdset.addAll(nodelayfieldsrd.get(fn.getNext(i)));
  84         if (nodelayarrayswr.containsKey(fn.getNext(i)))
  85           nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
  86       }
  87
  88       /* Check our temp write set */
  89
  90       TempDescriptor writeset[]=fn.writesTemps();
  91       for(int i=0;i<writeset.length;i++) {
  92         TempDescriptor tmp=writeset[i];
  93         if (nodelaytempset.contains(tmp)) {
  94           //We are writing to a nodelay temp
  95           //Therefore we are nodelay
  96           isnodelay=true;
  97           //Kill temp we wrote to
  98           nodelaytempset.remove(tmp);
  99         }
 100       }
 101
 102       //See if flatnode is definitely no delay
 103       if (fn.kind()==FKind.FlatCall) {
 104         isnodelay=true;
 105         //Have to deal with fields/arrays
 106         FlatCall fcall=(FlatCall)fn;
 107         MethodDescriptor mdcall=fcall.getMethod();
 108         nodelayfieldwrset.addAll(gft.getFieldsAll(mdcall));
 109         nodelayarraywrset.addAll(typeanalysis.expandSet(gft.getArraysAll(mdcall)));
 110         //Have to deal with field/array reads
 111         nodelayfieldrdset.addAll(gft.getFieldsRdAll(mdcall));
 112         nodelayarrayrdset.addAll(typeanalysis.expandSet(gft.getArraysRdAll(mdcall)));
 113       }
 114
 115       // Can't delay branches
 116       if (fn.kind()==FKind.FlatCondBranch) {
 117         isnodelay=true;
 118       }
 119
 120       //Check for field conflicts
 121       if (fn.kind()==FKind.FlatSetFieldNode) {
 122         FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
 123         //write conflicts
 124         if (nodelayfieldwrset.contains(fd))
 125           isnodelay=true;
 126         //read
 127         if (nodelayfieldrdset.contains(fd))
 128           isnodelay=true;
 129       }
 130
 131       if (fn.kind()==FKind.FlatFieldNode) {
 132         FieldDescriptor fd=((FlatFieldNode)fn).getField();
 133         //write conflicts
 134         if (nodelayfieldwrset.contains(fd))
 135           isnodelay=true;
 136       }
 137
 138       //Check for array conflicts
 139       if (fn.kind()==FKind.FlatSetElementNode) {
 140         TypeDescriptor td=((FlatSetElementNode)fn).getDst().getType();
 141         //check for write conflicts
 142         if (nodelayarraywrset.contains(td))
 143           isnodelay=true;
 144         //check for read conflicts
 145         if (nodelayarrayrdset.contains(td))
 146           isnodelay=true;
 147       }
 148       if (fn.kind()==FKind.FlatElementNode) {
 149         TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 150         //check for write conflicts
 151         if (nodelayarraywrset.contains(td))
 152           isnodelay=true;
 153       }
 154
 155       //If we are no delay, then the temps we read are no delay
 156       if (isnodelay) {
 157         /* Add our read set */
 158         TempDescriptor readset[]=fn.readsTemps();
 159         for(int i=0;i<readset.length;i++) {
 160           TempDescriptor tmp=readset[i];
 161           nodelaytempset.add(tmp);
 162         }
 163         cannotdelay.add(fn);
 164
 165         /* Do we write to fields */
 166         if (fn.kind()==FKind.FlatSetFieldNode) {
 167           nodelayfieldwrset.add(((FlatSetFieldNode)fn).getField());
 168         }
 169         /* Do we read from fields */
 170         if (fn.kind()==FKind.FlatFieldNode) {
 171           nodelayfieldrdset.add(((FlatFieldNode)fn).getField());
 172         }
 173
 174         /* Do we write to arrays */
 175         if (fn.kind()==FKind.FlatSetElementNode) {
 176           //have to do expansion
 177           nodelayarraywrset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getDst().getType()));
 178         }
 179         /* Do we read from arrays */
 180         if (fn.kind()==FKind.FlatElementNode) {
 181           //have to do expansion
 182           nodelayarrayrdset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getSrc().getType()));
 183         }
 184       }
 185
 186       boolean changed=false;
 187       //See if we need to propagate changes
 188       if (!nodelaytemps.containsKey(fn)||
 189           !nodelaytemps.get(fn).equals(nodelaytempset)) {
 190         nodelaytemps.put(fn, nodelaytempset);
 191         changed=true;
 192       }
 193
 194       //See if we need to propagate changes
 195       if (!nodelayfieldswr.containsKey(fn)||
 196           !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
 197         nodelayfieldswr.put(fn, nodelayfieldwrset);
 198         changed=true;
 199       }
 200
 201       //See if we need to propagate changes
 202       if (!nodelayfieldsrd.containsKey(fn)||
 203           !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
 204         nodelayfieldsrd.put(fn, nodelayfieldrdset);
 205         changed=true;
 206       }
 207
 208       //See if we need to propagate changes
 209       if (!nodelayarrayswr.containsKey(fn)||
 210           !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
 211         nodelayarrayswr.put(fn, nodelayarraywrset);
 212         changed=true;
 213       }
 214
 215       //See if we need to propagate changes
 216       if (!nodelayarraysrd.containsKey(fn)||
 217           !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
 218         nodelayarraysrd.put(fn, nodelayarrayrdset);
 219         changed=true;
 220       }
 221
 222       if (changed)
 223         for(int i=0;i<fn.numPrev();i++)
 224           toanalyze.add(fn.getPrev(i));
 225     } //end of while loop
 226
 227   } //end of method
 228 } //end of class