Robust/src/Analysis/Loops/WriteBarrier.java

   1 package Analysis.Loops;
   2 import IR.Flat.*;
   3 import Analysis.Locality.*;
   4 import IR.Operation;
   5 import IR.State;
   6 import IR.MethodDescriptor;
   7 import java.util.HashSet;
   8 import java.util.Hashtable;
   9 import java.util.Iterator;
  10
  11 public class WriteBarrier {
  12   /* This computes whether we actually need a write barrier. */
  13   LocalityAnalysis la;
  14   State state;
  15   public WriteBarrier(LocalityAnalysis la, State state) {
  16     this.la=la;
  17     this.state=state;
  18   }
  19
  20   public boolean needBarrier(FlatNode fn) {
  21     HashSet<TempDescriptor> nb=computeIntersection(fn);
  22     switch(fn.kind()) {
  23     case FKind.FlatSetElementNode:
  24       {
  25         FlatSetElementNode fsen=(FlatSetElementNode)fn;
  26         return !nb.contains(fsen.getDst());
  27       }
  28     case FKind.FlatSetFieldNode:
  29       {
  30         FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
  31         return !nb.contains(fsfn.getDst());
  32       }
  33     default:
  34       return true;
  35     }
  36   }
  37
  38   Hashtable<FlatNode,HashSet<TempDescriptor>> needbarrier;
  39
  40   public void analyze(LocalityBinding lb) {
  41     MethodDescriptor md=lb.getMethod();
  42     FlatMethod fm=state.getMethodFlat(md);
  43     HashSet useful=new HashSet();
  44     HashSet toprocess=new HashSet();
  45     HashSet discovered=new HashSet();
  46     needbarrier=new Hashtable<FlatNode,HashSet<TempDescriptor>>();
  47     toprocess.add(fm.getNext(0));
  48     discovered.add(fm.getNext(0));
  49     Hashtable<FlatNode, Integer> atomic=la.getAtomic(lb);
  50
  51     while(!toprocess.isEmpty()) {
  52       FlatNode fn=(FlatNode)toprocess.iterator().next();
  53       toprocess.remove(fn);
  54       for(int i=0;i<fn.numNext();i++) {
  55         FlatNode nnext=fn.getNext(i);
  56         if (!discovered.contains(nnext)) {
  57           toprocess.add(nnext);
  58           discovered.add(nnext);
  59         }
  60       }
  61       HashSet<TempDescriptor> nb=computeIntersection(fn);
  62       TempDescriptor[] writes=fn.writesTemps();
  63       for(int i=0;i<writes.length;i++) {
  64         nb.remove(writes[i]);
  65       }
  66       switch(fn.kind()) {
  67       case FKind.FlatSetElementNode:
  68         {
  69           FlatSetElementNode fsen=(FlatSetElementNode)fn;
  70           nb.add(fsen.getDst());
  71           break;
  72         }
  73       case FKind.FlatSetFieldNode:
  74         {
  75           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
  76           nb.add(fsfn.getDst());
  77           break;
  78         }
  79       case FKind.FlatOpNode:
  80         {
  81           FlatOpNode fon=(FlatOpNode)fn;
  82           if (fon.getOp().getOp()==Operation.ASSIGN) {
  83             if (nb.contains(fon.getLeft())) {
  84               nb.add(fon.getDest());
  85             }
  86           }
  87           break;
  88         }
  89       case FKind.FlatNew:
  90         {
  91           FlatNew fnew=(FlatNew)fn;
  92           nb.add(fnew.getDst());
  93           break;
  94         }
  95       default:
  96         //If we enter a transaction toss everything
  97         if (atomic.get(fn).intValue()>0&&
  98             atomic.get(fn.getPrev(0)).intValue()==0) {
  99           nb=new HashSet<TempDescriptor>();
 100         }
 101       }
 102       if (!needbarrier.containsKey(fn)||
 103           !needbarrier.get(fn).equals(nb)) {
 104         for(int i=0;i<fn.numNext();i++) {
 105           FlatNode nnext=fn.getNext(i);
 106           toprocess.add(nnext);
 107         }
 108         needbarrier.put(fn,nb);
 109       }
 110     }
 111   }
 112   HashSet<TempDescriptor> computeIntersection(FlatNode fn) {
 113     HashSet<TempDescriptor> tab=new HashSet<TempDescriptor>();
 114     boolean first=true;
 115     for(int i=0;i<fn.numPrev();i++) {
 116       FlatNode fprev=fn.getPrev(i);
 117       HashSet<TempDescriptor> hs=needbarrier.get(fprev);
 118       if (hs!=null) {
 119         if (first) {
 120           tab.addAll(hs);
 121           first=false;
 122         } else {
 123           //Intersect sets
 124           for(Iterator<TempDescriptor> it=tab.iterator();it.hasNext();) {
 125             TempDescriptor t=it.next();
 126             if (!hs.contains(t))
 127               it.remove();
 128           }
 129         }
 130       }
 131     }
 132     return tab;
 133   }
 134 }