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