Robust/src/Analysis/Loops/CSE.java

   1 package Analysis.Loops;
   2
   3 import IR.Flat.*;
   4 import IR.TypeUtil;
   5 import IR.Operation;
   6 import IR.FieldDescriptor;
   7 import IR.MethodDescriptor;
   8 import IR.TypeDescriptor;
   9 import java.util.Map;
  10 import java.util.Iterator;
  11 import java.util.Hashtable;
  12 import java.util.HashSet;
  13 import java.util.Set;
  14
  15 public class CSE {
  16   GlobalFieldType gft;
  17   TypeUtil typeutil;
  18   public CSE(GlobalFieldType gft, TypeUtil typeutil) {
  19     this.gft=gft;
  20     this.typeutil=typeutil;
  21   }
  22
  23   public void doAnalysis(FlatMethod fm) {
  24     Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr=new Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>>();
  25
  26     HashSet toprocess=new HashSet();
  27     HashSet discovered=new HashSet();
  28     toprocess.add(fm);
  29     discovered.add(fm);
  30     while(!toprocess.isEmpty()) {
  31       FlatNode fn=(FlatNode)toprocess.iterator().next();
  32       toprocess.remove(fn);
  33       for(int i=0;i<fn.numNext();i++) {
  34         FlatNode nnext=fn.getNext(i);
  35         if (!discovered.contains(nnext)) {
  36           toprocess.add(nnext);
  37           discovered.add(nnext);
  38         }
  39       }
  40       Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
  41
  42       //Do kills of expression/variable mappings
  43       TempDescriptor[] write=fn.writesTemps();
  44       for(int i=0;i<write.length;i++) {
  45         if (tab.containsKey(write[i]))
  46           tab.remove(write[i]);
  47       }
  48
  49       switch(fn.kind()) {
  50       case FKind.FlatCall:
  51         {
  52           FlatCall fc=(FlatCall) fn;
  53           MethodDescriptor md=fc.getMethod();
  54           Set<FieldDescriptor> fields=gft.getFields(md);
  55           Set<TypeDescriptor> arrays=gft.getArrays(md);
  56           killexpressions(tab, fields, arrays);
  57           break;
  58         }
  59       case FKind.FlatOpNode:
  60         {
  61           FlatOpNode fon=(FlatOpNode) fn;
  62           Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
  63           tab.put(e, fon.getDest());
  64           break;
  65         }
  66       case FKind.FlatSetFieldNode:
  67         {
  68           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
  69           Set<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
  70           fields.add(fsfn.getField());
  71           killexpressions(tab, fields, null);
  72           Expression e=new Expression(fsfn.getDst(), fsfn.getField());
  73           tab.put(e, fsfn.getSrc());
  74           break;
  75         }
  76       case FKind.FlatFieldNode:
  77         {
  78           FlatFieldNode ffn=(FlatFieldNode)fn;
  79           Expression e=new Expression(ffn.getSrc(), ffn.getField());
  80           tab.put(e, ffn.getDst());
  81           break;
  82         }
  83       case FKind.FlatSetElementNode:
  84         {
  85           FlatSetElementNode fsen=(FlatSetElementNode)fn;
  86           Expression e=new Expression(fsen.getDst(),fsen.getIndex());
  87           tab.put(e, fsen.getSrc());
  88           break;
  89         }
  90       case FKind.FlatElementNode:
  91         {
  92           FlatElementNode fen=(FlatElementNode)fn;
  93           Expression e=new Expression(fen.getSrc(),fen.getIndex());
  94           tab.put(e, fen.getDst());
  95           break;
  96         }
  97       default:
  98       }
  99
 100       if (write.length==1) {
 101         TempDescriptor w=write[0];
 102         for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
 103           Map.Entry m=(Map.Entry)it.next();
 104           Expression e=(Expression)m.getKey();
 105           if (e.a==w||e.b==w)
 106             it.remove();
 107         }
 108       }
 109       if (!availexpr.containsKey(fn)||!availexpr.get(fn).equals(tab)) {
 110         availexpr.put(fn, tab);
 111         for(int i=0;i<fn.numNext();i++) {
 112           FlatNode nnext=fn.getNext(i);
 113           toprocess.add(nnext);
 114         }
 115       }
 116     }
 117     doOptimize(fm, availexpr);
 118   }
 119
 120   public void doOptimize(FlatMethod fm, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
 121       for(Iterator<FlatNode> it=fm.getNodeSet().iterator();it.hasNext();) {
 122           FlatNode fn=it.next();
 123           Hashtable<Expression, TempDescriptor> tab=computeIntersection(fn, availexpr);
 124           switch(fn.kind()) {
 125           case FKind.FlatOpNode:
 126               {
 127                   FlatOpNode fon=(FlatOpNode) fn;
 128                   Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
 129                   if (tab.containsKey(e)) {
 130                       TempDescriptor t=tab.get(e);
 131                       FlatOpNode newfon=new FlatOpNode(fon.getDest(),t,null,new Operation(Operation.ASSIGN));
 132                       fon.replace(newfon);
 133                   }
 134                   break;
 135               }
 136           case FKind.FlatFieldNode:
 137               {
 138                   FlatFieldNode ffn=(FlatFieldNode)fn;
 139                   Expression e=new Expression(ffn.getSrc(), ffn.getField());
 140                   if (tab.containsKey(e)) {
 141                       TempDescriptor t=tab.get(e);
 142                       FlatOpNode newfon=new FlatOpNode(ffn.getDst(),t,null,new Operation(Operation.ASSIGN));
 143                       ffn.replace(newfon);
 144                   }
 145                   break;
 146               }
 147           case FKind.FlatElementNode:
 148               {
 149                   FlatElementNode fen=(FlatElementNode)fn;
 150                   Expression e=new Expression(fen.getSrc(),fen.getIndex());
 151                   if (tab.containsKey(e)) {
 152                       TempDescriptor t=tab.get(e);
 153                       FlatOpNode newfon=new FlatOpNode(fen.getDst(),t,null,new Operation(Operation.ASSIGN));
 154                       fen.replace(newfon);
 155                   }
 156                   break;
 157               }
 158           default:
 159           }
 160       }
 161   }
 162
 163   public Hashtable<Expression, TempDescriptor> computeIntersection(FlatNode fn, Hashtable<FlatNode,Hashtable<Expression, TempDescriptor>> availexpr) {
 164     Hashtable<Expression, TempDescriptor> tab=new Hashtable<Expression, TempDescriptor>();
 165     boolean first=true;
 166
 167     //compute intersection
 168     for(int i=0;i<fn.numPrev();i++) {
 169       FlatNode prev=fn.getPrev(i);
 170       if (first) {
 171         if (availexpr.containsKey(prev))
 172           tab.putAll(availexpr.get(prev));
 173         first=false;
 174       } else {
 175         if (availexpr.containsKey(prev)) {
 176           Hashtable<Expression, TempDescriptor> table=availexpr.get(prev);
 177           for(Iterator mapit=tab.entrySet().iterator();mapit.hasNext();) {
 178             Object entry=mapit.next();
 179             if (!table.contains(entry))
 180               mapit.remove();
 181           }
 182         }
 183       }
 184     }
 185     return tab;
 186   }
 187
 188   public void killexpressions(Hashtable<Expression, TempDescriptor> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays) {
 189     for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
 190       Map.Entry m=(Map.Entry)it.next();
 191       Expression e=(Expression)m.getKey();
 192       if (e.f!=null&&fields!=null&&fields.contains(e.f))
 193         it.remove();
 194       else if ((e.a!=null)&&(arrays!=null)) {
 195         for(Iterator<TypeDescriptor> arit=arrays.iterator();arit.hasNext();) {
 196           TypeDescriptor artd=arit.next();
 197           if (typeutil.isSuperorType(artd,e.a.getType())||
 198               typeutil.isSuperorType(e.a.getType(),artd)) {
 199             it.remove();
 200             break;
 201           }
 202         }
 203       }
 204     }
 205   }
 206 }
 207
 208 class Expression {
 209   Operation op;
 210   TempDescriptor a;
 211   TempDescriptor b;
 212   FieldDescriptor f;
 213   Expression(TempDescriptor a, TempDescriptor b, Operation op) {
 214     this.a=a;
 215     this.b=b;
 216     this.op=op;
 217   }
 218   Expression(TempDescriptor a, FieldDescriptor f) {
 219     this.a=a;
 220     this.f=f;
 221   }
 222   Expression(TempDescriptor a, TempDescriptor index) {
 223     this.a=a;
 224     this.b=index;
 225   }
 226   public int hashCode() {
 227     int h=0;
 228     h^=a.hashCode();
 229     if (op!=null)
 230       h^=op.getOp();
 231     if (b!=null)
 232       h^=b.hashCode();
 233     if (f!=null)
 234       h^=f.hashCode();
 235     return h;
 236   }
 237   public boolean equals(Object o) {
 238     Expression e=(Expression)o;
 239     if (a!=e.a||f!=e.f||b!=e.b)
 240       return false;
 241     if (op!=null)
 242       return op.getOp()==e.op.getOp();
 243     return true;
 244   }
 245 }