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