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