1) allow to set the maximum threshold for the liveness analysis. if threashold is...
[IRC.git] / 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 }