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   boolean turnoff;
  16
  17   public WriteBarrier(LocalityAnalysis la, State state) {
  18     this.la=la;
  19     this.state=state;
  20     turnoff=false;
  21   }
  22
  23   public void turnoff() {
  24     turnoff=true;
  25   }
  26
  27   public void turnon() {
  28     turnoff=false;
  29   }
  30
  31   public boolean needBarrier(FlatNode fn) {
  32     if (turnoff)
  33       return false;
  34     HashSet<TempDescriptor> nb=computeIntersection(fn);
  35     switch(fn.kind()) {
  36     case FKind.FlatSetElementNode:
  37     {
  38       FlatSetElementNode fsen=(FlatSetElementNode)fn;
  39       return !nb.contains(fsen.getDst());
  40     }
  41
  42     case FKind.FlatElementNode:
  43     {
  44       FlatElementNode fen=(FlatElementNode)fn;
  45       return !nb.contains(fen.getSrc());
  46     }
  47
  48     case FKind.FlatSetFieldNode:
  49     {
  50       FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
  51       return !nb.contains(fsfn.getDst());
  52     }
  53
  54     default:
  55       return true;
  56     }
  57   }
  58
  59   Hashtable<FlatNode,HashSet<TempDescriptor>> needbarrier;
  60
  61   public void analyze(LocalityBinding lb) {
  62     MethodDescriptor md=lb.getMethod();
  63     FlatMethod fm=state.getMethodFlat(md);
  64     HashSet useful=new HashSet();
  65     HashSet toprocess=new HashSet();
  66     HashSet discovered=new HashSet();
  67     needbarrier=new Hashtable<FlatNode,HashSet<TempDescriptor>>();
  68     toprocess.add(fm.getNext(0));
  69     discovered.add(fm.getNext(0));
  70     Hashtable<FlatNode, Integer> atomic=la.getAtomic(lb);
  71
  72     while(!toprocess.isEmpty()) {
  73       FlatNode fn=(FlatNode)toprocess.iterator().next();
  74       toprocess.remove(fn);
  75       for(int i=0; i<fn.numNext(); i++) {
  76         FlatNode nnext=fn.getNext(i);
  77         if (!discovered.contains(nnext)) {
  78           toprocess.add(nnext);
  79           discovered.add(nnext);
  80         }
  81       }
  82       HashSet<TempDescriptor> nb=computeIntersection(fn);
  83       TempDescriptor[] writes=fn.writesTemps();
  84       for(int i=0; i<writes.length; i++) {
  85         nb.remove(writes[i]);
  86       }
  87       switch(fn.kind()) {
  88       case FKind.FlatSetElementNode:
  89       {
  90         FlatSetElementNode fsen=(FlatSetElementNode)fn;
  91         if (!state.STMARRAY)
  92           nb.add(fsen.getDst());
  93         break;
  94       }
  95
  96       case FKind.FlatSetFieldNode:
  97       {
  98         FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
  99         nb.add(fsfn.getDst());
 100         break;
 101       }
 102
 103       case FKind.FlatOpNode:
 104       {
 105         FlatOpNode fon=(FlatOpNode)fn;
 106         if (fon.getOp().getOp()==Operation.ASSIGN) {
 107           if (nb.contains(fon.getLeft())) {
 108             nb.add(fon.getDest());
 109           }
 110         }
 111         break;
 112       }
 113
 114       case FKind.FlatNew:
 115       {
 116         FlatNew fnew=(FlatNew)fn;
 117         nb.add(fnew.getDst());
 118         break;
 119       }
 120
 121       default:
 122         //If we enter a transaction toss everything
 123         if (atomic.get(fn).intValue()>0&&
 124             atomic.get(fn.getPrev(0)).intValue()==0) {
 125           nb=new HashSet<TempDescriptor>();
 126         }
 127       }
 128       if (!needbarrier.containsKey(fn)||
 129           !needbarrier.get(fn).equals(nb)) {
 130         for(int i=0; i<fn.numNext(); i++) {
 131           FlatNode nnext=fn.getNext(i);
 132           toprocess.add(nnext);
 133         }
 134         needbarrier.put(fn,nb);
 135       }
 136     }
 137   }
 138   HashSet<TempDescriptor> computeIntersection(FlatNode fn) {
 139     HashSet<TempDescriptor> tab=new HashSet<TempDescriptor>();
 140     boolean first=true;
 141     for(int i=0; i<fn.numPrev(); i++) {
 142       FlatNode fprev=fn.getPrev(i);
 143       HashSet<TempDescriptor> hs=needbarrier.get(fprev);
 144       if (hs!=null) {
 145         if (first) {
 146           tab.addAll(hs);
 147           first=false;
 148         } else {
 149           //Intersect sets
 150           for(Iterator<TempDescriptor> it=tab.iterator(); it.hasNext(); ) {
 151             TempDescriptor t=it.next();
 152             if (!hs.contains(t))
 153               it.remove();
 154           }
 155         }
 156       }
 157     }
 158     return tab;
 159   }
 160 }