Robust/src/Analysis/Loops/CopyPropagation.java

   1 package Analysis.Loops;
   2 import IR.Flat.*;
   3 import IR.Operation;
   4 import java.util.Iterator;
   5 import java.util.Hashtable;
   6 import java.util.HashSet;
   7 import java.util.Set;
   8 import java.util.Map;
   9 import Analysis.Liveness;
  10
  11 public class CopyPropagation {
  12   public CopyPropagation() {
  13   }
  14
  15   public void optimize(FlatMethod fm) {
  16     Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
  17     Hashtable<FlatNode, Hashtable<TempDescriptor, TempDescriptor>> table
  18       =new Hashtable<FlatNode, Hashtable<TempDescriptor, TempDescriptor>>();
  19     boolean changed=false;
  20     TempDescriptor bogustd=new TempDescriptor("bogus");
  21     do {
  22       changed=false;
  23       HashSet tovisit=new HashSet();
  24       tovisit.add(fm);
  25       while(!tovisit.isEmpty()) {
  26         FlatNode fn=(FlatNode) tovisit.iterator().next();
  27         tovisit.remove(fn);
  28
  29         Hashtable<TempDescriptor, TempDescriptor> tab;
  30         if (fn.numPrev()>=1&&table.containsKey(fn.getPrev(0)))
  31           tab=new Hashtable<TempDescriptor, TempDescriptor>(table.get(fn.getPrev(0)));
  32         else
  33           tab=new Hashtable<TempDescriptor, TempDescriptor>();
  34         //Compute intersection
  35
  36         Set<TempDescriptor> liveset=livetemps.get(fn);
  37         for(int i=1;i<fn.numPrev();i++) {
  38           Hashtable<TempDescriptor, TempDescriptor> tp=table.get(fn.getPrev(i));
  39           if (tp==null)
  40             continue;
  41           for(Iterator tmpit=tp.entrySet().iterator();tmpit.hasNext();) {
  42             Map.Entry t=(Map.Entry)tmpit.next();
  43             TempDescriptor tmp=(TempDescriptor)t.getKey();
  44             if (!liveset.contains(tmp))
  45               continue;
  46             TempDescriptor dsttmp=tp.get(tmp);
  47             if (!tab.containsKey(tmp)) {
  48               tab.put(tmp, dsttmp);
  49             } else if (tab.get(tmp)!=dsttmp) {
  50               tab.put(tmp, bogustd);
  51             }
  52           }
  53         }
  54
  55         HashSet<TempDescriptor> toremove=new HashSet<TempDescriptor>();
  56         TempDescriptor[]writes=fn.writesTemps();
  57         for(int i=0;i<writes.length;i++) {
  58           TempDescriptor tmp=writes[i];
  59           toremove.add(tmp);
  60           for(Iterator<TempDescriptor> tmpit=tab.keySet().iterator();tmpit.hasNext();) {
  61             TempDescriptor tmp2=tmpit.next();
  62             if (tmp==tab.get(tmp2))
  63               toremove.add(tmp2);
  64           }
  65         }
  66
  67         for(Iterator<TempDescriptor> tmpit=toremove.iterator();tmpit.hasNext();) {
  68           TempDescriptor tmp=tmpit.next();
  69           tab.put(tmp, bogustd);
  70         }
  71
  72         if (fn.kind()==FKind.FlatOpNode) {
  73           FlatOpNode fon=(FlatOpNode)fn;
  74           if (fon.getOp().getOp()==Operation.ASSIGN) {
  75             tab.put(fon.getDest(), fon.getLeft());
  76           }
  77         }
  78         if (!table.containsKey(fn)||!table.get(fn).equals(tab)) {
  79           table.put(fn,tab);
  80           changed=true;
  81           for(int i=0;i<fn.numNext();i++) {
  82             FlatNode nnext=fn.getNext(i);
  83             tovisit.add(nnext);
  84           }
  85         }
  86       } //end of dataflow while loop
  87
  88       Set<FlatNode> nodeset=fm.getNodeSet();
  89
  90       for(Iterator<FlatNode> it=fm.getNodeSet().iterator();it.hasNext();) {
  91         FlatNode fn=it.next();
  92         if (fn.numPrev()==0)
  93           continue;
  94
  95         Hashtable<TempDescriptor, TempDescriptor> tab=new Hashtable<TempDescriptor, TempDescriptor>();
  96
  97         for(int i=0;i<fn.numPrev();i++) {
  98           Hashtable<TempDescriptor, TempDescriptor> tp=table.get(fn.getPrev(i));
  99           for(Iterator tmpit=tp.entrySet().iterator();tmpit.hasNext();) {
 100             Map.Entry t=(Map.Entry)tmpit.next();
 101             TempDescriptor tmp=(TempDescriptor)t.getKey();
 102
 103             if (!tab.containsKey(tmp))
 104               tab.put(tmp, tp.get(tmp));
 105             else if (tab.get(tmp)!=tp.get(tmp)) {
 106               tab.put(tmp, bogustd);
 107             }
 108           }
 109         }
 110
 111         TempMap tmap=null;
 112         TempDescriptor[]reads=fn.readsTemps();
 113         for(int i=0;i<reads.length;i++) {
 114           TempDescriptor tmp=reads[i];
 115           if (tab.containsKey(tmp)&&tab.get(tmp)!=bogustd) {
 116             if (tmap==null)
 117               tmap=new TempMap();
 118             tmap.addPair(tmp, tab.get(tmp));
 119           }
 120         }
 121         if (tmap!=null)
 122           fn.rewriteUse(tmap);
 123       } //end of remapping for loop
 124     } while(changed);
 125   }
 126 }