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=new Hashtable<Expression, TempDescriptor>();
  41       boolean first=true;
  42
  43       //compute intersection
  44       for(int i=0;i<fn.numPrev();i++) {
  45         FlatNode prev=fn.getPrev(i);
  46         if (first) {
  47           if (availexpr.containsKey(prev))
  48             tab.putAll(availexpr.get(prev));
  49           first=false;
  50         } else {
  51           if (availexpr.containsKey(prev)) {
  52             Hashtable<Expression, TempDescriptor> table=availexpr.get(prev);
  53             for(Iterator mapit=tab.entrySet().iterator();mapit.hasNext();) {
  54               Object entry=mapit.next();
  55               if (!table.contains(entry))
  56                 mapit.remove();
  57             }
  58           }
  59         }
  60       }
  61       //Do kills of expression/variable mappings
  62       TempDescriptor[] write=fn.writesTemps();
  63       for(int i=0;i<write.length;i++) {
  64         if (tab.containsKey(write[i]))
  65           tab.remove(write[i]);
  66       }
  67
  68       switch(fn.kind()) {
  69       case FKind.FlatCall:
  70         {
  71           FlatCall fc=(FlatCall) fn;
  72           MethodDescriptor md=fc.getMethod();
  73           Set<FieldDescriptor> fields=gft.getFields(md);
  74           Set<TypeDescriptor> arrays=gft.getArrays(md);
  75           killexpressions(tab, fields, arrays);
  76           break;
  77         }
  78       case FKind.FlatOpNode:
  79         {
  80           FlatOpNode fon=(FlatOpNode) fn;
  81           Expression e=new Expression(fon.getLeft(), fon.getRight(),fon.getOp());
  82           tab.put(e, fon.getDest());
  83           break;
  84         }
  85       case FKind.FlatSetFieldNode:
  86         {
  87           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
  88           Set<FieldDescriptor> fields=new HashSet<FieldDescriptor>();
  89           fields.add(fsfn.getField());
  90           killexpressions(tab, fields, null);
  91           Expression e=new Expression(fsfn.getDst(), fsfn.getField());
  92           tab.put(e, fsfn.getSrc());
  93           break;
  94         }
  95       case FKind.FlatFieldNode:
  96         {
  97           FlatFieldNode ffn=(FlatFieldNode)fn;
  98           Expression e=new Expression(ffn.getSrc(), ffn.getField());
  99           tab.put(e, ffn.getDst());
 100           break;
 101         }
 102       case FKind.FlatSetElementNode:
 103         {
 104           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 105           Expression e=new Expression(fsen.getDst(),fsen.getIndex());
 106           tab.put(e, fsen.getSrc());
 107           break;
 108         }
 109       case FKind.FlatElementNode:
 110         {
 111           FlatElementNode fen=(FlatElementNode)fn;
 112           Expression e=new Expression(fen.getSrc(),fen.getIndex());
 113           tab.put(e, fen.getDst());
 114           break;
 115         }
 116       default:
 117       }
 118
 119       if (write.length==1) {
 120         TempDescriptor w=write[0];
 121         for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
 122           Map.Entry m=(Map.Entry)it.next();
 123           Expression e=(Expression)m.getKey();
 124           if (e.a==w||e.b==w)
 125             it.remove();
 126         }
 127       }
 128       if (!availexpr.containsKey(fn)||!availexpr.get(fn).equals(tab)) {
 129         availexpr.put(fn, tab);
 130         for(int i=0;i<fn.numNext();i++) {
 131           FlatNode nnext=fn.getNext(i);
 132           toprocess.add(nnext);
 133         }
 134       }
 135     }
 136   }
 137
 138   public void killexpressions(Hashtable<Expression, TempDescriptor> tab, Set<FieldDescriptor> fields, Set<TypeDescriptor> arrays) {
 139     for(Iterator it=tab.entrySet().iterator();it.hasNext();) {
 140       Map.Entry m=(Map.Entry)it.next();
 141       Expression e=(Expression)m.getKey();
 142       if (e.f!=null&&fields!=null&&fields.contains(e.f))
 143         it.remove();
 144       else if ((e.a!=null)&&(arrays!=null)) {
 145         for(Iterator<TypeDescriptor> arit=arrays.iterator();arit.hasNext();) {
 146           TypeDescriptor artd=arit.next();
 147           if (typeutil.isSuperorType(artd,e.a.getType())||
 148               typeutil.isSuperorType(e.a.getType(),artd)) {
 149             it.remove();
 150             break;
 151           }
 152         }
 153       }
 154     }
 155   }
 156 }
 157
 158 class Expression {
 159   Operation op;
 160   TempDescriptor a;
 161   TempDescriptor b;
 162   FieldDescriptor f;
 163   Expression(TempDescriptor a, TempDescriptor b, Operation op) {
 164     this.a=a;
 165     this.b=b;
 166     this.op=op;
 167   }
 168   Expression(TempDescriptor a, FieldDescriptor f) {
 169     this.a=a;
 170     this.f=f;
 171   }
 172   Expression(TempDescriptor a, TempDescriptor index) {
 173     this.a=a;
 174     this.b=index;
 175   }
 176   public int hashCode() {
 177     int h=0;
 178     h^=a.hashCode();
 179     if (op!=null)
 180       h^=op.getOp();
 181     if (b!=null)
 182       h^=b.hashCode();
 183     if (f!=null)
 184       h^=f.hashCode();
 185     return h;
 186   }
 187   public boolean equals(Object o) {
 188     Expression e=(Expression)o;
 189     if (a!=e.a||f!=e.f||b!=e.b)
 190       return false;
 191     if (op!=null)
 192       return op.getOp()==e.op.getOp();
 193     return true;
 194   }
 195 }