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