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