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