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     if (gft!=null)
 173       return twritemap.get(lb).contains(fn);
 174     else throw new Error();
 175   }
 176
 177   public Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> getMap(LocalityBinding lb) {
 178     return lbtofnmap.get(lb);
 179   }
 180
 181   private void analyzeLocality(LocalityBinding lb) {
 182     MethodDescriptor md=lb.getMethod();
 183     FlatMethod fm=state.getMethodFlat(md);
 184
 185     //Compute map from flatnode -> (temps -> source of value)
 186     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=computeTempSets(lb);
 187     lbtofnmap.put(lb,fnmap);
 188     HashSet<TempFlatPair> writeset=null;
 189     if (gft!=null) {
 190       writeset=new HashSet<TempFlatPair>();
 191     }
 192     HashSet<TempFlatPair> tfset=computeTranslationSet(lb, fm, fnmap, writeset);
 193     if (gft!=null) {
 194       writemap.put(lb, writeset);
 195     }
 196
 197     HashSet<FlatNode> srctrans=new HashSet<FlatNode>();
 198     HashSet<FlatNode> leftsrctrans=new HashSet<FlatNode>();
 199     HashSet<FlatNode> rightsrctrans=new HashSet<FlatNode>();
 200     transreadmap.put(lb, tfset);
 201     srcmap.put(lb,srctrans);
 202     leftsrcmap.put(lb,leftsrctrans);
 203     rightsrcmap.put(lb,rightsrctrans);
 204
 205     //compute writes that need translation on source
 206     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 207       FlatNode fn=fnit.next();
 208       Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 209       if (atomictable.get(fn).intValue()>0) {
 210         Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
 211         switch(fn.kind()) {
 212
 213           //We might need to translate arguments to pointer comparison
 214
 215         case FKind.FlatOpNode: {
 216           FlatOpNode fon=(FlatOpNode)fn;
 217           if (fon.getOp().getOp()==Operation.EQUAL||
 218               fon.getOp().getOp()==Operation.NOTEQUAL) {
 219             if (!fon.getLeft().getType().isPtr())
 220               break;
 221             Set<TempFlatPair> lefttfpset=tmap.get(fon.getLeft());
 222             Set<TempFlatPair> righttfpset=tmap.get(fon.getRight());
 223             //handle left operand
 224             if (lefttfpset!=null) {
 225               for(Iterator<TempFlatPair> tfpit=lefttfpset.iterator();tfpit.hasNext();) {
 226                 TempFlatPair tfp=tfpit.next();
 227                 if (tfset.contains(tfp)||outofscope(tfp)) {
 228                   leftsrctrans.add(fon);
 229                   break;
 230                 }
 231               }
 232             }
 233             //handle right operand
 234             if (righttfpset!=null) {
 235               for(Iterator<TempFlatPair> tfpit=righttfpset.iterator();tfpit.hasNext();) {
 236                 TempFlatPair tfp=tfpit.next();
 237                 if (tfset.contains(tfp)||outofscope(tfp)) {
 238                   rightsrctrans.add(fon);
 239                   break;
 240                 }
 241               }
 242             }
 243           }
 244           break;
 245         }
 246
 247         case FKind.FlatGlobalConvNode: {
 248           //need to translate these if the value we read from may be a
 249           //shadow...  check this by seeing if any of the values we
 250           //may read are in the transread set or came from our caller
 251           //or a method we called
 252
 253           FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
 254           if (fgcn.getLocality()!=lb||
 255               fgcn.getMakePtr())
 256             break;
 257
 258           Set<TempFlatPair> tfpset=tmap.get(fgcn.getSrc());
 259
 260           if (tfpset!=null) {
 261             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 262               TempFlatPair tfp=tfpit.next();
 263               if (tfset.contains(tfp)||outofscope(tfp)) {
 264                 srctrans.add(fgcn);
 265                 break;
 266               }
 267             }
 268           }
 269           break;
 270         }
 271
 272         case FKind.FlatSetFieldNode: {
 273           //need to translate these if the value we read from may be a
 274           //shadow...  check this by seeing if any of the values we
 275           //may read are in the transread set or came from our caller
 276           //or a method we called
 277
 278           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 279           if (!fsfn.getField().getType().isPtr())
 280             break;
 281           Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
 282           if (tfpset!=null) {
 283             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 284               TempFlatPair tfp=tfpit.next();
 285               if (tfset.contains(tfp)||outofscope(tfp)) {
 286                 srctrans.add(fsfn);
 287                 break;
 288               }
 289             }
 290           }
 291           break;
 292         }
 293         case FKind.FlatSetElementNode: {
 294           //need to translate these if the value we read from may be a
 295           //shadow...  check this by seeing if any of the values we
 296           //may read are in the transread set or came from our caller
 297           //or a method we called
 298
 299           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 300           if (!fsen.getSrc().getType().isPtr())
 301             break;
 302           Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
 303           if (tfpset!=null) {
 304             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 305               TempFlatPair tfp=tfpit.next();
 306               if (tfset.contains(tfp)||outofscope(tfp)) {
 307                 srctrans.add(fsen);
 308                 break;
 309               }
 310             }
 311           }
 312           break;
 313         }
 314         default:
 315         }
 316       }
 317     }
 318   }
 319
 320   public boolean outofscope(TempFlatPair tfp) {
 321     FlatNode fn=tfp.f;
 322     return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
 323   }
 324
 325   private void computeReadOnly(LocalityBinding lb, Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap, Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap) {
 326     //inside of transaction, try to convert rw access to ro access
 327     MethodDescriptor md=lb.getMethod();
 328     FlatMethod fm=state.getMethodFlat(md);
 329     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 330
 331     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 332     toanalyze.addAll(fm.getNodeSet());
 333
 334     while(!toanalyze.isEmpty()) {
 335       FlatNode fn=toanalyze.iterator().next();
 336       toanalyze.remove(fn);
 337       HashSet<TypeDescriptor> updatetypeset=new HashSet<TypeDescriptor>();
 338       HashSet<FieldDescriptor> updatefieldset=new HashSet<FieldDescriptor>();
 339
 340       //Stop if we aren't in a transaction
 341       if (atomictable.get(fn).intValue()==0)
 342         continue;
 343
 344       //Do merge of all exits
 345       for(int i=0;i<fn.numNext();i++) {
 346         FlatNode fnnext=fn.getNext(i);
 347         if (updatedtypemap.containsKey(fnnext)) {
 348           updatetypeset.addAll(updatedtypemap.get(fnnext));
 349         }
 350         if (updatedfieldmap.containsKey(fnnext)) {
 351           updatefieldset.addAll(updatedfieldmap.get(fnnext));
 352         }
 353       }
 354
 355       //process this node
 356       if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)!=inclusive) {
 357         switch(fn.kind()) {
 358         case FKind.FlatSetFieldNode: {
 359           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 360           updatefieldset.add(fsfn.getField());
 361           break;
 362         }
 363         case FKind.FlatSetElementNode: {
 364           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 365           updatetypeset.addAll(typeanalysis.expand(fsen.getDst().getType()));
 366           break;
 367         }
 368         case FKind.FlatCall: {
 369           FlatCall fcall=(FlatCall)fn;
 370           MethodDescriptor mdfc=fcall.getMethod();
 371
 372           //get modified fields
 373           Set<FieldDescriptor> fields=gft.getFieldsAll(mdfc);
 374           updatefieldset.addAll(fields);
 375
 376           //get modified arrays
 377           Set<TypeDescriptor> arrays=gft.getArraysAll(mdfc);
 378           updatetypeset.addAll(typeanalysis.expandSet(arrays));
 379           break;
 380         }
 381         }
 382       }
 383
 384       if (!updatedtypemap.containsKey(fn)||!updatedfieldmap.containsKey(fn)||
 385           !updatedtypemap.get(fn).equals(updatetypeset)||!updatedfieldmap.get(fn).equals(updatefieldset)) {
 386         updatedtypemap.put(fn, updatetypeset);
 387         updatedfieldmap.put(fn, updatefieldset);
 388         for(int i=0;i<fn.numPrev();i++) {
 389           toanalyze.add(fn.getPrev(i));
 390         }
 391       }
 392     }
 393   }
 394
 395
 396   /** Need to figure out which nodes need a transread to make local
 397   copies.  Transread conceptually tracks conflicts.  This depends on
 398   what fields/elements are accessed We iterate over all flatnodes that
 399   access fields...If these accesses could conflict, we mark the source
 400   tempflat pair as needing a transread */
 401
 402
 403   HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap, Set<TempFlatPair> writeset) {
 404     HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
 405
 406     //Compute maps from flatnodes -> sets of things that may be updated after this node
 407     Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap=null;
 408     Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap=null;
 409
 410     if (writeset!=null&&!lb.isAtomic()) {
 411       updatedtypemap=new Hashtable<FlatNode, Set<TypeDescriptor>>();
 412       updatedfieldmap=new Hashtable<FlatNode, Set<FieldDescriptor>>();
 413       computeReadOnly(lb, updatedtypemap, updatedfieldmap);
 414     }
 415
 416     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 417       FlatNode fn=fnit.next();
 418       //Check whether this node matters for cannot delayed computation
 419       if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)==inclusive)
 420         continue;
 421
 422       Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 423       if (atomictable.get(fn).intValue()>0) {
 424         Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
 425         switch(fn.kind()) {
 426         case FKind.FlatElementNode: {
 427           FlatElementNode fen=(FlatElementNode)fn;
 428           if (arrays.contains(fen.getSrc().getType())) {
 429             //this could cause conflict...figure out conflict set
 430             Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
 431             if (tfpset!=null)
 432               tfset.addAll(tfpset);
 433           }
 434           if (updatedtypemap!=null&&updatedtypemap.get(fen).contains(fen.getSrc().getType())) {
 435             //this could cause conflict...figure out conflict set
 436             Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
 437             if (tfpset!=null)
 438               writeset.addAll(tfpset);
 439           }
 440           break;
 441         }
 442         case FKind.FlatFieldNode: {
 443           FlatFieldNode ffn=(FlatFieldNode)fn;
 444           if (fields.contains(ffn.getField())) {
 445             //this could cause conflict...figure out conflict set
 446             Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
 447             if (tfpset!=null)
 448               tfset.addAll(tfpset);
 449           }
 450           if (updatedfieldmap!=null&&updatedfieldmap.get(ffn).contains(ffn.getField())) {
 451             //this could cause conflict...figure out conflict set
 452             Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
 453             if (tfpset!=null)
 454               writeset.addAll(tfpset);
 455           }
 456           break;
 457         }
 458         case FKind.FlatSetFieldNode: {
 459           //definitely need to translate these
 460           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 461           Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
 462           if (tfpset!=null)
 463             tfset.addAll(tfpset);
 464           if (writeset!=null) {
 465             if (tfpset!=null)
 466               writeset.addAll(tfpset);
 467           }
 468           break;
 469         }
 470         case FKind.FlatSetElementNode: {
 471           //definitely need to translate these
 472           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 473           Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
 474           if (tfpset!=null)
 475             tfset.addAll(tfpset);
 476           if (writeset!=null) {
 477             if (tfpset!=null)
 478               writeset.addAll(tfpset);
 479           }
 480           break;
 481         }
 482         case FKind.FlatCall: //assume pessimistically that calls do bad things
 483         case FKind.FlatReturnNode: {
 484           TempDescriptor []readarray=fn.readsTemps();
 485           for(int i=0;i<readarray.length;i++) {
 486             TempDescriptor rtmp=readarray[i];
 487             Set<TempFlatPair> tfpset=tmap.get(rtmp);
 488             if (tfpset!=null)
 489               tfset.addAll(tfpset);
 490             if (writeset!=null) {
 491               if (tfpset!=null)
 492                 writeset.addAll(tfpset);
 493             }
 494           }
 495           break;
 496         }
 497         default:
 498           //do nothing
 499         }
 500       }
 501     }
 502     return tfset;
 503   }
 504
 505
 506   //This method generates as output for each node
 507   //A map from from temps to a set of temp/flat pairs that the
 508   //original temp points to
 509   //A temp/flat pair gives the flatnode that the value was created at
 510   //and the original temp
 511
 512   Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
 513     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
 514     HashSet<FlatNode> discovered=new HashSet<FlatNode>();
 515     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 516     MethodDescriptor md=lb.getMethod();
 517     FlatMethod fm=state.getMethodFlat(md);
 518     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 519     Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
 520     tovisit.add(fm);
 521     discovered.add(fm);
 522
 523     while(!tovisit.isEmpty()) {
 524       FlatNode fn=tovisit.iterator().next();
 525       tovisit.remove(fn);
 526       for(int i=0;i<fn.numNext();i++) {
 527         FlatNode fnext=fn.getNext(i);
 528         if (!discovered.contains(fnext)) {
 529           discovered.add(fnext);
 530           tovisit.add(fnext);
 531         }
 532       }
 533       Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
 534       if (atomictable.get(fn).intValue()!=0) {
 535         if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
 536           //atomic node, start with new set
 537           ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
 538         } else {
 539           ttofn=doMerge(fn, tmptofnset);
 540           switch(fn.kind()) {
 541           case FKind.FlatGlobalConvNode: {
 542             FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
 543             if (lb==fgcn.getLocality()&&
 544                 fgcn.getMakePtr()) {
 545               TempDescriptor[] writes=fn.writesTemps();
 546               for(int i=0;i<writes.length;i++) {
 547                 TempDescriptor wtmp=writes[i];
 548                 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
 549                 set.add(new TempFlatPair(wtmp, fn));
 550                 ttofn.put(wtmp, set);
 551               }
 552             }
 553             break;
 554           }
 555           case FKind.FlatFieldNode:
 556           case FKind.FlatElementNode: {
 557             TempDescriptor[] writes=fn.writesTemps();
 558             for(int i=0;i<writes.length;i++) {
 559               TempDescriptor wtmp=writes[i];
 560               HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
 561               set.add(new TempFlatPair(wtmp, fn));
 562               ttofn.put(wtmp, set);
 563             }
 564             break;
 565           }
 566           case FKind.FlatCall:
 567           case FKind.FlatMethod: {
 568             TempDescriptor[] writes=fn.writesTemps();
 569             for(int i=0;i<writes.length;i++) {
 570               TempDescriptor wtmp=writes[i];
 571               HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
 572               set.add(new TempFlatPair(wtmp, fn));
 573               ttofn.put(wtmp, set);
 574             }
 575             break;
 576           }
 577           case FKind.FlatCastNode:
 578           case FKind.FlatOpNode:
 579             if (fn.kind()==FKind.FlatCastNode) {
 580               FlatCastNode fcn=(FlatCastNode)fn;
 581               if (fcn.getDst().getType().isPtr()) {
 582                 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
 583                 if (ttofn.containsKey(fcn.getSrc()))
 584                   set.addAll(ttofn.get(fcn.getSrc()));
 585                 if (normalassign)
 586                   set.add(new TempFlatPair(fcn.getDst(), fn));
 587                 ttofn.put(fcn.getDst(), set);
 588                 break;
 589               }
 590             } else if (fn.kind()==FKind.FlatOpNode) {
 591               FlatOpNode fon=(FlatOpNode)fn;
 592               if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
 593                 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
 594                 if (ttofn.containsKey(fon.getLeft()))
 595                   set.addAll(ttofn.get(fon.getLeft()));
 596                 if (normalassign)
 597                   set.add(new TempFlatPair(fon.getDest(), fn));
 598                 ttofn.put(fon.getDest(), set);
 599                 break;
 600               }
 601             }
 602           default:
 603             //Do kill computation
 604             TempDescriptor[] writes=fn.writesTemps();
 605             for(int i=0;i<writes.length;i++) {
 606               TempDescriptor wtmp=writes[i];
 607               ttofn.remove(writes[i]);
 608             }
 609           }
 610         }
 611         if (ttofn!=null) {
 612           if (!tmptofnset.containsKey(fn)||
 613               !tmptofnset.get(fn).equals(ttofn)) {
 614             //enqueue nodes to process
 615             tmptofnset.put(fn, ttofn);
 616             for(int i=0;i<fn.numNext();i++) {
 617               FlatNode fnext=fn.getNext(i);
 618               tovisit.add(fnext);
 619             }
 620           }
 621         }
 622       }
 623     }
 624     return tmptofnset;
 625   }
 626
 627   /* See what fields and arrays transactions might modify.  We only
 628    * look at changes to old objects. */
 629
 630   //Bug fix: original version forget to check if object is new and
 631   //could be optimized
 632
 633   public void computeModified(LocalityBinding lb) {
 634     MethodDescriptor md=lb.getMethod();
 635     FlatMethod fm=state.getMethodFlat(md);
 636     Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
 637     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 638       FlatNode fn=fnit.next();
 639       Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 640       if (atomictable.get(fn).intValue()>0) {
 641         Set<TempDescriptor> oldtemp=oldtemps.get(fn);
 642         switch (fn.kind()) {
 643         case FKind.FlatSetFieldNode:
 644           FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
 645           if (oldtemp.contains(fsfn.getDst()))
 646             fields.add(fsfn.getField());
 647           break;
 648         case FKind.FlatSetElementNode:
 649           FlatSetElementNode fsen=(FlatSetElementNode) fn;
 650           if (oldtemp.contains(fsen.getDst()))
 651             arrays.add(fsen.getDst().getType());
 652           break;
 653         default:
 654         }
 655       }
 656     }
 657   }
 658
 659
 660   //Returns a table that maps a flatnode to a set of temporaries
 661   //This set of temporaries is old (meaning they may point to object
 662   //allocated before the beginning of the current transaction
 663
 664   Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
 665     Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
 666     HashSet<FlatNode> discovered=new HashSet<FlatNode>();
 667     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 668     MethodDescriptor md=lb.getMethod();
 669     FlatMethod fm=state.getMethodFlat(md);
 670     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 671     Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
 672     tovisit.add(fm);
 673     discovered.add(fm);
 674
 675     while(!tovisit.isEmpty()) {
 676       FlatNode fn=tovisit.iterator().next();
 677       tovisit.remove(fn);
 678       for(int i=0;i<fn.numNext();i++) {
 679         FlatNode fnext=fn.getNext(i);
 680         if (!discovered.contains(fnext)) {
 681           discovered.add(fnext);
 682           tovisit.add(fnext);
 683         }
 684       }
 685       HashSet<TempDescriptor> oldtemps=null;
 686       if (atomictable.get(fn).intValue()!=0) {
 687         if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
 688           //Everything live is old
 689           Set<TempDescriptor> lives=livetemps.get(fn);
 690           oldtemps=new HashSet<TempDescriptor>();
 691
 692           for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
 693             TempDescriptor tmp=it.next();
 694             if (tmp.getType().isPtr()) {
 695               oldtemps.add(tmp);
 696             }
 697           }
 698         } else {
 699           oldtemps=new HashSet<TempDescriptor>();
 700           //Compute union of old temporaries
 701           for(int i=0;i<fn.numPrev();i++) {
 702             Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
 703             if (pset!=null)
 704               oldtemps.addAll(pset);
 705           }
 706
 707           switch (fn.kind()) {
 708           case FKind.FlatNew:
 709             oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
 710             break;
 711           case FKind.FlatOpNode:
 712           case FKind.FlatCastNode:
 713             if (fn.kind()==FKind.FlatCastNode) {
 714               FlatCastNode fcn=(FlatCastNode)fn;
 715               if (fcn.getDst().getType().isPtr()) {
 716                 if (oldtemps.contains(fcn.getSrc()))
 717                   oldtemps.add(fcn.getDst());
 718                 else
 719                   oldtemps.remove(fcn.getDst());
 720                 break;
 721               }
 722             } else if (fn.kind()==FKind.FlatOpNode) {
 723               FlatOpNode fon=(FlatOpNode)fn;
 724               if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
 725                 if (oldtemps.contains(fon.getLeft()))
 726                   oldtemps.add(fon.getDest());
 727                 else
 728                   oldtemps.remove(fon.getDest());
 729                 break;
 730               }
 731             }
 732           default: {
 733             TempDescriptor[] writes=fn.writesTemps();
 734             for(int i=0;i<writes.length;i++) {
 735               TempDescriptor wtemp=writes[i];
 736               if (wtemp.getType().isPtr())
 737                 oldtemps.add(wtemp);
 738             }
 739           }
 740           }
 741         }
 742       }
 743
 744       if (oldtemps!=null) {
 745         if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
 746           fntooldtmp.put(fn, oldtemps);
 747           //propagate changes
 748           for(int i=0;i<fn.numNext();i++) {
 749             FlatNode fnext=fn.getNext(i);
 750             tovisit.add(fnext);
 751           }
 752         }
 753       }
 754     }
 755     return fntooldtmp;
 756   }
 757 }
 758
 759 class TempFlatPair {
 760     FlatNode f;
 761     TempDescriptor t;
 762     TempFlatPair(TempDescriptor t, FlatNode f) {
 763         this.t=t;
 764         this.f=f;
 765     }
 766
 767     public int hashCode() {
 768         return f.hashCode()^t.hashCode();
 769     }
 770     public boolean equals(Object o) {
 771         TempFlatPair tf=(TempFlatPair)o;
 772         return t.equals(tf.t)&&f.equals(tf.f);
 773     }
 774 }