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       HashSet discovered=new HashSet();
  22       tovisit.add(fm);
  23       discovered.add(fm);
  24       while(!tovisit.isEmpty()) {
  25         FlatNode fn=(FlatNode) tovisit.iterator().next();
  26         tovisit.remove(fn);
  27         for(int i=0;i<fn.numNext();i++) {
  28           FlatNode nnext=fn.getNext(i);
  29           if (!discovered.contains(nnext)) {
  30             discovered.add(nnext);
  31             tovisit.add(nnext);
  32           }
  33         }
  34         Hashtable<TempDescriptor, TempDescriptor> tab;
  35         if (fn.numPrev()>=1&&table.containsKey(fn.getPrev(0)))
  36           tab=new Hashtable<TempDescriptor, TempDescriptor>(table.get(fn.getPrev(0)));
  37         else
  38           tab=new Hashtable<TempDescriptor, TempDescriptor>();
  39         //Compute intersection
  40         for(int i=1;i<fn.numPrev();i++) {
  41           Hashtable<TempDescriptor, TempDescriptor> tp=table.get(fn.getPrev(i));
  42           for(Iterator tmpit=tab.entrySet().iterator();tmpit.hasNext();) {
  43             Map.Entry t=(Map.Entry)tmpit.next();
  44             TempDescriptor tmp=(TempDescriptor)t.getKey();
  45             if (tp!=null&&(!tp.containsKey(tmp)||tp.get(tmp)!=tab.get(tmp))) {
  46               tmpit.remove();
  47             }
  48           }
  49         }
  50         TempDescriptor[]writes=fn.writesTemps();
  51         for(int i=0;i<writes.length;i++) {
  52           TempDescriptor tmp=writes[i];
  53           for(Iterator<TempDescriptor> tmpit=tab.keySet().iterator();tmpit.hasNext();) {
  54             TempDescriptor tmp2=tmpit.next();
  55             if (tmp==tab.get(tmp2))
  56               tmpit.remove();
  57           }
  58         }
  59         if (fn.kind()==FKind.FlatOpNode) {
  60           FlatOpNode fon=(FlatOpNode)fn;
  61           if (fon.getOp().getOp()==Operation.ASSIGN) {
  62             tab.put(fon.getDest(), fon.getLeft());
  63           }
  64         }
  65         if (!table.containsKey(fn)||!table.get(fn).equals(tab)) {
  66           table.put(fn,tab);
  67           changed=true;
  68           for(int i=0;i<fn.numNext();i++) {
  69             FlatNode nnext=fn.getNext(i);
  70             tovisit.add(nnext);
  71           }
  72         }
  73       }
  74       for(Iterator<FlatNode> it=fm.getNodeSet().iterator();it.hasNext();) {
  75         FlatNode fn=it.next();
  76         Hashtable<TempDescriptor, TempDescriptor> tab=table.get(fn);
  77         TempMap tmap=null;
  78         TempDescriptor[]reads=fn.readsTemps();
  79         for(int i=0;i<reads.length;i++) {
  80           TempDescriptor tmp=reads[i];
  81           if (tab.containsKey(tmp)) {
  82             if (tmap==null)
  83               tmap=new TempMap();
  84             tmap.addPair(tmp, tab.get(tmp));
  85           }
  86         }
  87         if (tmap!=null)
  88           fn.rewriteUse(tmap);
  89       }
  90     } while(changed);
  91   }
  92 }