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