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