Robust/src/Analysis/Loops/localCSE.java

   1 package Analysis.Loops;
   2
   3 import IR.MethodDescriptor;
   4 import IR.TypeDescriptor;
   5 import IR.TypeUtil;
   6 import IR.Operation;
   7 import IR.Flat.*;
   8 import IR.FieldDescriptor;
   9 import java.util.Set;
  10 import java.util.HashSet;
  11 import java.util.Hashtable;
  12 import java.util.Iterator;
  13
  14 public class localCSE {
  15   GlobalFieldType gft;
  16   TypeUtil typeutil;
  17   public localCSE(GlobalFieldType gft, TypeUtil typeutil) {
  18     this.gft=gft;
  19     this.typeutil=typeutil;
  20   }
  21   int index;
  22
  23   public Group getGroup(Hashtable<LocalExpression, Group> tab, TempDescriptor t) {
  24     LocalExpression e=new LocalExpression(t);
  25     return getGroup(tab, e);
  26   }
  27   public Group getGroup(Hashtable<LocalExpression, Group> tab, LocalExpression e) {
  28     if (tab.containsKey(e))
  29       return tab.get(e);
  30     else {
  31       Group g=new Group(index++);
  32       g.set.add(e);
  33       tab.put(e,g);
  34       return g;
  35     }
  36   }
  37   public TempDescriptor getTemp(Group g) {
  38     for(Iterator it=g.set.iterator();it.hasNext();) {
  39       LocalExpression e=(LocalExpression)it.next();
  40       if (e.t!=null)
  41         return e.t;
  42     }
  43     return null;
  44   }
  45
  46   public void doAnalysis(FlatMethod fm) {
  47     Set nodes=fm.getNodeSet();
  48     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
  49     for(Iterator it=nodes.iterator();it.hasNext();) {
  50       FlatNode fn=(FlatNode)it.next();
  51       if (fn.numPrev()>1)
  52         toanalyze.add(fn);
  53     }
  54     for(Iterator<FlatNode> it=toanalyze.iterator();it.hasNext();) {
  55       FlatNode fn=it.next();
  56       Hashtable<LocalExpression, Group> table=new Hashtable<LocalExpression,Group>();
  57       do {
  58         index=0;
  59         switch(fn.kind()) {
  60         case FKind.FlatOpNode: {
  61           FlatOpNode fon=(FlatOpNode)fn;
  62           Group left=getGroup(table, fon.getLeft());
  63           Group right=getGroup(table, fon.getRight());
  64           LocalExpression dst=new LocalExpression(fon.getDest());
  65           if (fon.getOp().getOp()==Operation.ASSIGN) {
  66             left.set.add(dst);
  67             kill(table, fon.getDest());
  68             table.put(dst, left);
  69           } else {
  70             LocalExpression e=new LocalExpression(left, right, fon.getOp());
  71             Group g=getGroup(table,e);
  72             TempDescriptor td=getTemp(g);
  73             if (td!=null) {
  74               FlatOpNode nfon=new FlatOpNode(fon.getDest(),td,null,new Operation(Operation.ASSIGN));
  75               fn.replace(nfon);
  76             }
  77             g.set.add(dst);
  78             kill(table, fon.getDest());
  79             table.put(dst,g);
  80           }
  81           break;
  82         }
  83         case FKind.FlatLiteralNode: {
  84           FlatLiteralNode fln=(FlatLiteralNode)fn;
  85           LocalExpression e=new LocalExpression(fln.getValue());
  86           Group src=getGroup(table, e);
  87           LocalExpression dst=new LocalExpression(fln.getDst());
  88           src.set.add(dst);
  89           kill(table, fln.getDst());
  90           table.put(dst, src);
  91           break;
  92         }
  93         case FKind.FlatFieldNode: {
  94           FlatFieldNode ffn=(FlatFieldNode) fn;
  95           Group src=getGroup(table, ffn.getSrc());
  96           LocalExpression e=new LocalExpression(src, ffn.getField());
  97           Group srcf=getGroup(table, e);
  98           LocalExpression dst=new LocalExpression(ffn.getDst());
  99           TempDescriptor td=getTemp(srcf);
 100           if (td!=null) {
 101             FlatOpNode fon=new FlatOpNode(ffn.getDst(),td,null,new Operation(Operation.ASSIGN));
 102             fn.replace(fon);
 103           }
 104           srcf.set.add(dst);
 105           kill(table, ffn.getDst());
 106           table.put(dst, srcf);
 107           break;
 108         }
 109         case FKind.FlatElementNode: {
 110           FlatElementNode fen=(FlatElementNode) fn;
 111           Group src=getGroup(table, fen.getSrc());
 112           Group index=getGroup(table, fen.getIndex());
 113           LocalExpression e=new LocalExpression(src, fen.getSrc().getType(), index);
 114           Group srcf=getGroup(table, e);
 115           LocalExpression dst=new LocalExpression(fen.getDst());
 116           TempDescriptor td=getTemp(srcf);
 117           if (td!=null) {
 118             FlatOpNode fon=new FlatOpNode(fen.getDst(),td,null,new Operation(Operation.ASSIGN));
 119             fn.replace(fon);
 120           }
 121           srcf.set.add(dst);
 122           kill(table, fen.getDst());
 123           table.put(dst, srcf);
 124           break;
 125         }
 126         case FKind.FlatSetFieldNode: {
 127           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 128           Group dst=getGroup(table, fsfn.getDst());
 129           LocalExpression e=new LocalExpression(dst, fsfn.getField());
 130           Group dstf=getGroup(table, e);
 131           LocalExpression src=new LocalExpression(fsfn.getSrc());
 132           dstf.set.add(src);
 133           HashSet<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
 134           fields.add(fsfn.getField());
 135           kill(table, fields, null);
 136           table.put(src, dstf);
 137           break;
 138         }
 139         case FKind.FlatSetElementNode: {
 140           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 141           Group dst=getGroup(table, fsen.getDst());
 142           Group index=getGroup(table, fsen.getIndex());
 143           LocalExpression e=new LocalExpression(dst, fsen.getDst().getType(), index);
 144           Group dstf=getGroup(table, e);
 145           LocalExpression src=new LocalExpression(fsen.getSrc());
 146           dstf.set.add(src);
 147           HashSet<TypeDescriptor> arrays=new HashSet<TypeDescriptor>();
 148           arrays.add(fsen.getDst().getType());
 149           kill(table, null, arrays);
 150           table.put(src, dstf);
 151           break;
 152         }
 153         case FKind.FlatCall:{
 154           //do side effects
 155           FlatCall fc=(FlatCall)fn;
 156           MethodDescriptor md=fc.getMethod();
 157           Set<FieldDescriptor> fields=gft.getFields(md);
 158           Set<TypeDescriptor> arrays=gft.getArrays(md);
 159           kill(table, fields, arrays);
 160         }
 161         default: {
 162           TempDescriptor[] writes=fn.writesTemps();
 163           for(int i=0;i<writes.length;i++) {
 164             kill(table,writes[i]);
 165           }
 166         }
 167         }
 168       } while(fn.numPrev()==1);
 169     }
 170   }
 171   public void kill(Hashtable<LocalExpression, Group> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays) {
 172     Set<LocalExpression> eset=tab.keySet();
 173     for(Iterator<LocalExpression> it=eset.iterator();it.hasNext();) {
 174       LocalExpression e=it.next();
 175       if (e.td!=null) {
 176         //have array
 177         TypeDescriptor artd=e.td;
 178         for(Iterator<TypeDescriptor> arit=arrays.iterator();arit.hasNext();) {
 179           TypeDescriptor td=arit.next();
 180           if (typeutil.isSuperorType(artd,td)||
 181               typeutil.isSuperorType(td,artd)) {
 182             Group g=tab.get(e);
 183             g.set.remove(e);
 184             it.remove();
 185             break;
 186           }
 187         }
 188       } else if (e.f!=null) {
 189         if (fields.contains(e.f)) {
 190           Group g=tab.get(e);
 191           g.set.remove(e);
 192           it.remove();
 193         }
 194       }
 195     }
 196   }
 197   public void kill(Hashtable<LocalExpression, Group> tab, TempDescriptor t) {
 198     LocalExpression e=new LocalExpression(t);
 199     Group g=tab.get(e);
 200     tab.remove(e);
 201     g.set.remove(e);
 202   }
 203 }
 204
 205 class Group {
 206   HashSet set;
 207   int i;
 208   Group(int i) {
 209     set=new HashSet();
 210     this.i=i;
 211   }
 212   public int hashCode() {
 213     return i;
 214   }
 215   public boolean equals(Object o) {
 216     Group g=(Group)o;
 217     return i==g.i;
 218   }
 219 }
 220
 221 class LocalExpression {
 222   Operation op;
 223   Object o;
 224   Group a;
 225   Group b;
 226   TempDescriptor t;
 227   FieldDescriptor f;
 228   TypeDescriptor td;
 229   LocalExpression(TempDescriptor t) {
 230     this.t=t;
 231   }
 232   LocalExpression(Object o) {
 233     this.o=o;
 234   }
 235   LocalExpression(Group a, Group b, Operation op) {
 236     this.a=a;
 237     this.b=b;
 238     this.op=op;
 239   }
 240   LocalExpression(Group a, FieldDescriptor f) {
 241     this.a=a;
 242     this.f=f;
 243   }
 244   LocalExpression(Group a, TypeDescriptor td, Group index) {
 245     this.a=a;
 246     this.td=td;
 247     this.b=index;
 248   }
 249   public int hashCode() {
 250     int h=0;
 251     if (td!=null)
 252       h^=td.hashCode();
 253     if (t!=null)
 254       h^=t.hashCode();
 255     if (a!=null)
 256       h^=a.hashCode();
 257     if (o!=null)
 258       h^=o.hashCode();
 259     if (op!=null)
 260       h^=op.getOp();
 261     if (b!=null)
 262       h^=b.hashCode();
 263     if (f!=null)
 264       h^=f.hashCode();
 265     return h;
 266   }
 267   public boolean equals(Object o) {
 268     LocalExpression e=(LocalExpression)o;
 269     if (a!=e.a||f!=e.f||b!=e.b)
 270       return false;
 271     if (td!=null) {
 272       if (!td.equals(e.td))
 273         return false;
 274     }
 275     if (o!=null) {
 276       if (e.o==null)
 277         return false;
 278       return o.equals(e.o);
 279     } else if (op!=null)
 280       return op.getOp()==e.op.getOp();
 281     return true;
 282   }
 283 }