Robust/src/Analysis/Locality/DiscoverConflicts.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 IR.State;
  10 import IR.Operation;
  11 import IR.TypeDescriptor;
  12 import IR.MethodDescriptor;
  13 import IR.FieldDescriptor;
  14 import Analysis.Liveness;
  15 import Analysis.Loops.GlobalFieldType;
  16
  17 public class DiscoverConflicts {
  18   Set<FieldDescriptor> fields;
  19   Set<TypeDescriptor> arrays;
  20   LocalityAnalysis locality;
  21   State state;
  22   Hashtable<LocalityBinding, Set<FlatNode>> treadmap;
  23   Hashtable<LocalityBinding, Set<TempFlatPair>> transreadmap;
  24   Hashtable<LocalityBinding, Set<FlatNode>> twritemap;
  25   Hashtable<LocalityBinding, Set<TempFlatPair>> writemap;
  26   Hashtable<LocalityBinding, Set<FlatNode>> srcmap;
  27   Hashtable<LocalityBinding, Set<FlatNode>> leftsrcmap;
  28   Hashtable<LocalityBinding, Set<FlatNode>> rightsrcmap;
  29   TypeAnalysis typeanalysis;
  30   Hashtable<LocalityBinding, HashSet<FlatNode>>cannotdelaymap;
  31   Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>> lbtofnmap;
  32   boolean inclusive=false;
  33   boolean normalassign=false;
  34   GlobalFieldType gft;
  35
  36   public DiscoverConflicts(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
  37     this.locality=locality;
  38     this.fields=new HashSet<FieldDescriptor>();
  39     this.arrays=new HashSet<TypeDescriptor>();
  40     this.state=state;
  41     this.typeanalysis=typeanalysis;
  42     transreadmap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
  43     treadmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  44     srcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  45     leftsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  46     rightsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  47     lbtofnmap=new Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>>();
  48     if (gft!=null) {
  49       twritemap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  50       writemap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
  51     }
  52     this.gft=gft;
  53   }
  54
  55   public DiscoverConflicts(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap, boolean inclusive, boolean normalassign, GlobalFieldType gft) {
  56     this.locality=locality;
  57     this.fields=new HashSet<FieldDescriptor>();
  58     this.arrays=new HashSet<TypeDescriptor>();
  59     this.state=state;
  60     this.typeanalysis=typeanalysis;
  61     this.cannotdelaymap=cannotdelaymap;
  62     transreadmap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
  63     treadmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  64     srcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  65     leftsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  66     rightsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  67     lbtofnmap=new Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>>();
  68     this.inclusive=inclusive;
  69     this.normalassign=normalassign;
  70     if (gft!=null) {
  71       twritemap=new Hashtable<LocalityBinding, Set<FlatNode>>();
  72       writemap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
  73     }
  74     this.gft=gft;
  75   }
  76
  77   public Set<FieldDescriptor> getFields() {
  78     return fields;
  79   }
  80
  81   public Set<TypeDescriptor> getArrays() {
  82     return arrays;
  83   }
  84
  85   public void doAnalysis() {
  86     //Compute fields and arrays for all transactions.  Note that we
  87     //only look at changes to old objects
  88
  89     Set<LocalityBinding> localityset=locality.getLocalityBindings();
  90     for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
  91       computeModified(lb.next());
  92     }
  93     expandTypes();
  94     //Compute set of nodes that need transread
  95     for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
  96       LocalityBinding l=lb.next();
  97       analyzeLocality(l);
  98       setNeedReadTrans(l);
  99     }
 100   }
 101
 102   //Change flatnode/temp pairs to just flatnodes that need transactional reads
 103
 104   public void setNeedReadTrans(LocalityBinding lb) {
 105     HashSet<FlatNode> set=new HashSet<FlatNode>();
 106     for(Iterator<TempFlatPair> it=transreadmap.get(lb).iterator();it.hasNext();) {
 107       TempFlatPair tfp=it.next();
 108       set.add(tfp.f);
 109     }
 110     treadmap.put(lb, set);
 111     if (gft!=null) {
 112       //need to translate write map set
 113       set=new HashSet<FlatNode>();
 114       for(Iterator<TempFlatPair> it=writemap.get(lb).iterator();it.hasNext();) {
 115         TempFlatPair tfp=it.next();
 116         set.add(tfp.f);
 117       }
 118       twritemap.put(lb, set);
 119     }
 120   }
 121
 122   //We have a set of things we write to, figure out what things this
 123   //could effect.
 124   public void expandTypes() {
 125     Set<TypeDescriptor> expandedarrays=new HashSet<TypeDescriptor>();
 126     for(Iterator<TypeDescriptor> it=arrays.iterator();it.hasNext();) {
 127       TypeDescriptor td=it.next();
 128       expandedarrays.addAll(typeanalysis.expand(td));
 129     }
 130     arrays=expandedarrays;
 131   }
 132
 133   Hashtable<TempDescriptor, Set<TempFlatPair>> doMerge(FlatNode fn, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset) {
 134     Hashtable<TempDescriptor, Set<TempFlatPair>> table=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
 135     for(int i=0;i<fn.numPrev();i++) {
 136       FlatNode fprev=fn.getPrev(i);
 137       Hashtable<TempDescriptor, Set<TempFlatPair>> tabset=tmptofnset.get(fprev);
 138       if (tabset!=null) {
 139         for(Iterator<TempDescriptor> tmpit=tabset.keySet().iterator();tmpit.hasNext();) {
 140           TempDescriptor td=tmpit.next();
 141           Set<TempFlatPair> fnset=tabset.get(td);
 142           if (!table.containsKey(td))
 143             table.put(td, new HashSet<TempFlatPair>());
 144           table.get(td).addAll(fnset);
 145         }
 146       }
 147     }
 148     return table;
 149   }
 150
 151   public Set<FlatNode> getNeedSrcTrans(LocalityBinding lb) {
 152     return srcmap.get(lb);
 153   }
 154
 155   public boolean getNeedSrcTrans(LocalityBinding lb, FlatNode fn) {
 156     return srcmap.get(lb).contains(fn);
 157   }
 158
 159   public boolean getNeedLeftSrcTrans(LocalityBinding lb, FlatNode fn) {
 160     return leftsrcmap.get(lb).contains(fn);
 161   }
 162
 163   public boolean getNeedRightSrcTrans(LocalityBinding lb, FlatNode fn) {
 164     return rightsrcmap.get(lb).contains(fn);
 165   }
 166
 167   public boolean getNeedTrans(LocalityBinding lb, FlatNode fn) {
 168     return treadmap.get(lb).contains(fn);
 169   }
 170
 171   public boolean getNeedWriteTrans(LocalityBinding lb, FlatNode fn) {
 172     return twritemap.get(lb).contains(fn);
 173   }
 174
 175   public Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> getMap(LocalityBinding lb) {
 176     return lbtofnmap.get(lb);
 177   }
 178
 179   private void analyzeLocality(LocalityBinding lb) {
 180     MethodDescriptor md=lb.getMethod();
 181     FlatMethod fm=state.getMethodFlat(md);
 182
 183     //Compute map from flatnode -> (temps -> source of value)
 184     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=computeTempSets(lb);
 185     lbtofnmap.put(lb,fnmap);
 186     HashSet<TempFlatPair> writeset=null;
 187     if (gft!=null) {
 188       writeset=new HashSet<TempFlatPair>();
 189     }
 190     HashSet<TempFlatPair> tfset=computeTranslationSet(lb, fm, fnmap, writeset);
 191     if (gft!=null) {
 192       writemap.put(lb, writeset);
 193     }
 194
 195     HashSet<FlatNode> srctrans=new HashSet<FlatNode>();
 196     HashSet<FlatNode> leftsrctrans=new HashSet<FlatNode>();
 197     HashSet<FlatNode> rightsrctrans=new HashSet<FlatNode>();
 198     transreadmap.put(lb, tfset);
 199     srcmap.put(lb,srctrans);
 200     leftsrcmap.put(lb,leftsrctrans);
 201     rightsrcmap.put(lb,rightsrctrans);
 202
 203     //compute writes that need translation on source
 204     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 205       FlatNode fn=fnit.next();
 206       Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 207       if (atomictable.get(fn).intValue()>0) {
 208         Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
 209         switch(fn.kind()) {
 210
 211           //We might need to translate arguments to pointer comparison
 212
 213         case FKind.FlatOpNode: {
 214           FlatOpNode fon=(FlatOpNode)fn;
 215           if (fon.getOp().getOp()==Operation.EQUAL||
 216               fon.getOp().getOp()==Operation.NOTEQUAL) {
 217             if (!fon.getLeft().getType().isPtr())
 218               break;
 219             Set<TempFlatPair> lefttfpset=tmap.get(fon.getLeft());
 220             Set<TempFlatPair> righttfpset=tmap.get(fon.getRight());
 221             //handle left operand
 222             if (lefttfpset!=null) {
 223               for(Iterator<TempFlatPair> tfpit=lefttfpset.iterator();tfpit.hasNext();) {
 224                 TempFlatPair tfp=tfpit.next();
 225                 if (tfset.contains(tfp)||outofscope(tfp)) {
 226                   leftsrctrans.add(fon);
 227                   break;
 228                 }
 229               }
 230             }
 231             //handle right operand
 232             if (righttfpset!=null) {
 233               for(Iterator<TempFlatPair> tfpit=righttfpset.iterator();tfpit.hasNext();) {
 234                 TempFlatPair tfp=tfpit.next();
 235                 if (tfset.contains(tfp)||outofscope(tfp)) {
 236                   rightsrctrans.add(fon);
 237                   break;
 238                 }
 239               }
 240             }
 241           }
 242           break;
 243         }
 244
 245         case FKind.FlatGlobalConvNode: {
 246           //need to translate these if the value we read from may be a
 247           //shadow...  check this by seeing if any of the values we
 248           //may read are in the transread set or came from our caller
 249           //or a method we called
 250
 251           FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
 252           if (fgcn.getLocality()!=lb||
 253               fgcn.getMakePtr())
 254             break;
 255
 256           Set<TempFlatPair> tfpset=tmap.get(fgcn.getSrc());
 257
 258           if (tfpset!=null) {
 259             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 260               TempFlatPair tfp=tfpit.next();
 261               if (tfset.contains(tfp)||outofscope(tfp)) {
 262                 srctrans.add(fgcn);
 263                 break;
 264               }
 265             }
 266           }
 267           break;
 268         }
 269
 270         case FKind.FlatSetFieldNode: {
 271           //need to translate these if the value we read from may be a
 272           //shadow...  check this by seeing if any of the values we
 273           //may read are in the transread set or came from our caller
 274           //or a method we called
 275
 276           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 277           if (!fsfn.getField().getType().isPtr())
 278             break;
 279           Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
 280           if (tfpset!=null) {
 281             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 282               TempFlatPair tfp=tfpit.next();
 283               if (tfset.contains(tfp)||outofscope(tfp)) {
 284                 srctrans.add(fsfn);
 285                 break;
 286               }
 287             }
 288           }
 289           break;
 290         }
 291         case FKind.FlatSetElementNode: {
 292           //need to translate these if the value we read from may be a
 293           //shadow...  check this by seeing if any of the values we
 294           //may read are in the transread set or came from our caller
 295           //or a method we called
 296
 297           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 298           if (!fsen.getSrc().getType().isPtr())
 299             break;
 300           Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
 301           if (tfpset!=null) {
 302             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 303               TempFlatPair tfp=tfpit.next();
 304               if (tfset.contains(tfp)||outofscope(tfp)) {
 305                 srctrans.add(fsen);
 306                 break;
 307               }
 308             }
 309           }
 310           break;
 311         }
 312         default:
 313         }
 314       }
 315     }
 316   }
 317
 318   public boolean outofscope(TempFlatPair tfp) {
 319     FlatNode fn=tfp.f;
 320     return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
 321   }
 322
 323   private void computeReadOnly(LocalityBinding lb, Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap, Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap) {
 324     //inside of transaction, try to convert rw access to ro access
 325     MethodDescriptor md=lb.getMethod();
 326     FlatMethod fm=state.getMethodFlat(md);
 327     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 328
 329     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 330     toanalyze.addAll(fm.getNodeSet());
 331
 332     while(!toanalyze.isEmpty()) {
 333       FlatNode fn=toanalyze.iterator().next();
 334       toanalyze.remove(fn);
 335       HashSet<TypeDescriptor> updatetypeset=new HashSet<TypeDescriptor>();
 336       HashSet<FieldDescriptor> updatefieldset=new HashSet<FieldDescriptor>();
 337
 338       //Stop if we aren't in a transaction
 339       if (atomictable.get(fn).intValue()==0)
 340         continue;
 341
 342       //Do merge of all exits
 343       for(int i=0;i<fn.numNext();i++) {
 344         FlatNode fnnext=fn.getNext(i);
 345         if (updatedtypemap.containsKey(fnnext)) {
 346           updatetypeset.addAll(updatedtypemap.get(fnnext));
 347         }
 348         if (updatedfieldmap.containsKey(fnnext)) {
 349           updatefieldset.addAll(updatedfieldmap.get(fnnext));
 350         }
 351       }
 352
 353       //process this node
 354       if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)!=inclusive) {
 355         switch(fn.kind()) {
 356         case FKind.FlatSetFieldNode: {
 357           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 358           updatefieldset.add(fsfn.getField());
 359           break;
 360         }
 361         case FKind.FlatSetElementNode: {
 362           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 363           updatetypeset.addAll(typeanalysis.expand(fsen.getDst().getType()));
 364           break;
 365         }
 366         case FKind.FlatCall: {
 367           FlatCall fcall=(FlatCall)fn;
 368           MethodDescriptor mdfc=fcall.getMethod();
 369
 370           //get modified fields
 371           Set<FieldDescriptor> fields=gft.getFieldsAll(mdfc);
 372           updatefieldset.addAll(fields);
 373
 374           //get modified arrays
 375           Set<TypeDescriptor> arrays=gft.getArraysAll(mdfc);
 376           updatetypeset.addAll(typeanalysis.expandSet(arrays));
 377           break;
 378         }
 379         }
 380       }
 381
 382       if (!updatedtypemap.containsKey(fn)||!updatedfieldmap.containsKey(fn)||
 383           !updatedtypemap.get(fn).equals(updatetypeset)||!updatedfieldmap.get(fn).equals(updatefieldset)) {
 384         updatedtypemap.put(fn, updatetypeset);
 385         updatedfieldmap.put(fn, updatefieldset);
 386         for(int i=0;i<fn.numPrev();i++) {
 387           toanalyze.add(fn.getPrev(i));
 388         }
 389       }
 390     }
 391   }
 392
 393
 394   /** Need to figure out which nodes need a transread to make local
 395   copies.  Transread conceptually tracks conflicts.  This depends on
 396   what fields/elements are accessed We iterate over all flatnodes that
 397   access fields...If these accesses could conflict, we mark the source
 398   tempflat pair as needing a transread */
 399
 400
 401   HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap, Set<TempFlatPair> writeset) {
 402     HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
 403
 404     //Compute maps from flatnodes -> sets of things that may be updated after this node
 405     Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap=null;
 406     Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap=null;
 407
 408     if (writeset!=null&&!lb.isAtomic()) {
 409       updatedtypemap=new Hashtable<FlatNode, Set<TypeDescriptor>>();
 410       updatedfieldmap=new Hashtable<FlatNode, Set<FieldDescriptor>>();
 411       computeReadOnly(lb, updatedtypemap, updatedfieldmap);
 412     }
 413
 414     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 415       FlatNode fn=fnit.next();
 416       //Check whether this node matters for cannot delayed computation
 417       if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)==inclusive)
 418         continue;
 419
 420       Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 421       if (atomictable.get(fn).intValue()>0) {
 422         Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
 423         switch(fn.kind()) {
 424         case FKind.FlatElementNode: {
 425           FlatElementNode fen=(FlatElementNode)fn;
 426           if (arrays.contains(fen.getSrc().getType())) {
 427             //this could cause conflict...figure out conflict set
 428             Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
 429             if (tfpset!=null)
 430               tfset.addAll(tfpset);
 431           }
 432           if (updatedtypemap!=null&&updatedtypemap.get(fen).contains(fen.getSrc().getType())) {
 433             //this could cause conflict...figure out conflict set
 434             Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
 435             if (tfpset!=null)
 436               writeset.addAll(tfpset);
 437           }
 438           break;
 439         }
 440         case FKind.FlatFieldNode: {
 441           FlatFieldNode ffn=(FlatFieldNode)fn;
 442           if (fields.contains(ffn.getField())) {
 443             //this could cause conflict...figure out conflict set
 444             Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
 445             if (tfpset!=null)
 446               tfset.addAll(tfpset);
 447           }
 448           if (updatedfieldmap!=null&&updatedfieldmap.get(ffn).contains(ffn.getField())) {
 449             //this could cause conflict...figure out conflict set
 450             Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
 451             if (tfpset!=null)
 452               writeset.addAll(tfpset);
 453           }
 454           break;
 455         }
 456         case FKind.FlatSetFieldNode: {
 457           //definitely need to translate these
 458           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 459           Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
 460           if (tfpset!=null)
 461             tfset.addAll(tfpset);
 462           if (writeset!=null) {
 463             if (tfpset!=null)
 464               writeset.addAll(tfpset);
 465           }
 466           break;
 467         }
 468         case FKind.FlatSetElementNode: {
 469           //definitely need to translate these
 470           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 471           Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
 472           if (tfpset!=null)
 473             tfset.addAll(tfpset);
 474           if (writeset!=null) {
 475             if (tfpset!=null)
 476               writeset.addAll(tfpset);
 477           }
 478           break;
 479         }
 480         case FKind.FlatCall: //assume pessimistically that calls do bad things
 481         case FKind.FlatReturnNode: {
 482           TempDescriptor []readarray=fn.readsTemps();
 483           for(int i=0;i<readarray.length;i++) {
 484             TempDescriptor rtmp=readarray[i];
 485             Set<TempFlatPair> tfpset=tmap.get(rtmp);
 486             if (tfpset!=null)
 487               tfset.addAll(tfpset);
 488             if (writeset!=null) {
 489               if (tfpset!=null)
 490                 writeset.addAll(tfpset);
 491             }
 492           }
 493           break;
 494         }
 495         default:
 496           //do nothing
 497         }
 498       }
 499     }
 500     return tfset;
 501   }
 502
 503
 504   //This method generates as output for each node
 505   //A map from from temps to a set of temp/flat pairs that the
 506   //original temp points to
 507   //A temp/flat pair gives the flatnode that the value was created at
 508   //and the original temp
 509
 510   Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
 511     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
 512     HashSet<FlatNode> discovered=new HashSet<FlatNode>();
 513     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 514     MethodDescriptor md=lb.getMethod();
 515     FlatMethod fm=state.getMethodFlat(md);
 516     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 517     Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
 518     tovisit.add(fm);
 519     discovered.add(fm);
 520
 521     while(!tovisit.isEmpty()) {
 522       FlatNode fn=tovisit.iterator().next();
 523       tovisit.remove(fn);
 524       for(int i=0;i<fn.numNext();i++) {
 525         FlatNode fnext=fn.getNext(i);
 526         if (!discovered.contains(fnext)) {
 527           discovered.add(fnext);
 528           tovisit.add(fnext);
 529         }
 530       }
 531       Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
 532       if (atomictable.get(fn).intValue()!=0) {
 533         if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
 534           //atomic node, start with new set
 535           ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
 536         } else {
 537           ttofn=doMerge(fn, tmptofnset);
 538           switch(fn.kind()) {
 539           case FKind.FlatGlobalConvNode: {
 540             FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
 541             if (lb==fgcn.getLocality()&&
 542                 fgcn.getMakePtr()) {
 543               TempDescriptor[] writes=fn.writesTemps();
 544               for(int i=0;i<writes.length;i++) {
 545                 TempDescriptor wtmp=writes[i];
 546                 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
 547                 set.add(new TempFlatPair(wtmp, fn));
 548                 ttofn.put(wtmp, set);
 549               }
 550             }
 551             break;
 552           }
 553           case FKind.FlatFieldNode:
 554           case FKind.FlatElementNode: {
 555             TempDescriptor[] writes=fn.writesTemps();
 556             for(int i=0;i<writes.length;i++) {
 557               TempDescriptor wtmp=writes[i];
 558               HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
 559               set.add(new TempFlatPair(wtmp, fn));
 560               ttofn.put(wtmp, set);
 561             }
 562             break;
 563           }
 564           case FKind.FlatCall:
 565           case FKind.FlatMethod: {
 566             TempDescriptor[] writes=fn.writesTemps();
 567             for(int i=0;i<writes.length;i++) {
 568               TempDescriptor wtmp=writes[i];
 569               HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
 570               set.add(new TempFlatPair(wtmp, fn));
 571               ttofn.put(wtmp, set);
 572             }
 573             break;
 574           }
 575           case FKind.FlatOpNode: {
 576             FlatOpNode fon=(FlatOpNode)fn;
 577             if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
 578               HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
 579               if (ttofn.containsKey(fon.getLeft()))
 580                 set.addAll(ttofn.get(fon.getLeft()));
 581               if (normalassign)
 582                 set.add(new TempFlatPair(fon.getDest(), fn));
 583               ttofn.put(fon.getDest(), set);
 584               break;
 585             }
 586           }
 587           default:
 588             //Do kill computation
 589             TempDescriptor[] writes=fn.writesTemps();
 590             for(int i=0;i<writes.length;i++) {
 591               TempDescriptor wtmp=writes[i];
 592               ttofn.remove(writes[i]);
 593             }
 594           }
 595         }
 596         if (ttofn!=null) {
 597           if (!tmptofnset.containsKey(fn)||
 598               !tmptofnset.get(fn).equals(ttofn)) {
 599             //enqueue nodes to process
 600             tmptofnset.put(fn, ttofn);
 601             for(int i=0;i<fn.numNext();i++) {
 602               FlatNode fnext=fn.getNext(i);
 603               tovisit.add(fnext);
 604             }
 605           }
 606         }
 607       }
 608     }
 609     return tmptofnset;
 610   }
 611
 612   /* See what fields and arrays transactions might modify.  We only
 613    * look at changes to old objects. */
 614
 615   public void computeModified(LocalityBinding lb) {
 616     MethodDescriptor md=lb.getMethod();
 617     FlatMethod fm=state.getMethodFlat(md);
 618     Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
 619     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 620       FlatNode fn=fnit.next();
 621       Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 622       if (atomictable.get(fn).intValue()>0) {
 623         switch (fn.kind()) {
 624         case FKind.FlatSetFieldNode:
 625           FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
 626           fields.add(fsfn.getField());
 627           break;
 628         case FKind.FlatSetElementNode:
 629           FlatSetElementNode fsen=(FlatSetElementNode) fn;
 630           arrays.add(fsen.getDst().getType());
 631           break;
 632         default:
 633         }
 634       }
 635     }
 636   }
 637
 638
 639   //Returns a table that maps a flatnode to a set of temporaries
 640   //This set of temporaries is old (meaning they may point to object
 641   //allocated before the beginning of the current transaction
 642
 643   Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
 644     Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
 645     HashSet<FlatNode> discovered=new HashSet<FlatNode>();
 646     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 647     MethodDescriptor md=lb.getMethod();
 648     FlatMethod fm=state.getMethodFlat(md);
 649     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 650     Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
 651     tovisit.add(fm);
 652     discovered.add(fm);
 653
 654     while(!tovisit.isEmpty()) {
 655       FlatNode fn=tovisit.iterator().next();
 656       tovisit.remove(fn);
 657       for(int i=0;i<fn.numNext();i++) {
 658         FlatNode fnext=fn.getNext(i);
 659         if (!discovered.contains(fnext)) {
 660           discovered.add(fnext);
 661           tovisit.add(fnext);
 662         }
 663       }
 664       HashSet<TempDescriptor> oldtemps=null;
 665       if (atomictable.get(fn).intValue()!=0) {
 666         if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
 667           //Everything live is old
 668           Set<TempDescriptor> lives=livetemps.get(fn);
 669           oldtemps=new HashSet<TempDescriptor>();
 670
 671           for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
 672             TempDescriptor tmp=it.next();
 673             if (tmp.getType().isPtr()) {
 674               oldtemps.add(tmp);
 675             }
 676           }
 677         } else {
 678           oldtemps=new HashSet<TempDescriptor>();
 679           //Compute union of old temporaries
 680           for(int i=0;i<fn.numPrev();i++) {
 681             Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
 682             if (pset!=null)
 683               oldtemps.addAll(pset);
 684           }
 685
 686           switch (fn.kind()) {
 687           case FKind.FlatNew:
 688             oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
 689             break;
 690           case FKind.FlatOpNode: {
 691             FlatOpNode fon=(FlatOpNode)fn;
 692             if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
 693               if (oldtemps.contains(fon.getLeft()))
 694                 oldtemps.add(fon.getDest());
 695               else
 696                 oldtemps.remove(fon.getDest());
 697               break;
 698             }
 699           }
 700           default: {
 701             TempDescriptor[] writes=fn.writesTemps();
 702             for(int i=0;i<writes.length;i++) {
 703               TempDescriptor wtemp=writes[i];
 704               if (wtemp.getType().isPtr())
 705                 oldtemps.add(wtemp);
 706             }
 707           }
 708           }
 709         }
 710       }
 711
 712       if (oldtemps!=null) {
 713         if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
 714           fntooldtmp.put(fn, oldtemps);
 715           //propagate changes
 716           for(int i=0;i<fn.numNext();i++) {
 717             FlatNode fnext=fn.getNext(i);
 718             tovisit.add(fnext);
 719           }
 720         }
 721       }
 722     }
 723     return fntooldtmp;
 724   }
 725 }
 726
 727 class TempFlatPair {
 728     FlatNode f;
 729     TempDescriptor t;
 730     TempFlatPair(TempDescriptor t, FlatNode f) {
 731         this.t=t;
 732         this.f=f;
 733     }
 734
 735     public int hashCode() {
 736         return f.hashCode()^t.hashCode();
 737     }
 738     public boolean equals(Object o) {
 739         TempFlatPair tf=(TempFlatPair)o;
 740         return t.equals(tf.t)&&f.equals(tf.f);
 741     }
 742 }