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