1 package Analysis.Loops;
4 import java.util.Iterator;
5 import java.util.Hashtable;
6 import java.util.HashSet;
9 import Analysis.Liveness;
11 public class CopyPropagation {
12 public CopyPropagation() {
15 public void optimize(FlatMethod fm) {
16 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
17 Hashtable<FlatNode, Hashtable<TempDescriptor, TempDescriptor>> table
18 =new Hashtable<FlatNode, Hashtable<TempDescriptor, TempDescriptor>>();
19 boolean changed=false;
20 TempDescriptor bogustd=new TempDescriptor("bogus");
23 HashSet tovisit=new HashSet();
25 while(!tovisit.isEmpty()) {
26 FlatNode fn=(FlatNode) tovisit.iterator().next();
29 Hashtable<TempDescriptor, TempDescriptor> tab;
30 if (fn.numPrev()>=1&&table.containsKey(fn.getPrev(0)))
31 tab=new Hashtable<TempDescriptor, TempDescriptor>(table.get(fn.getPrev(0)));
33 tab=new Hashtable<TempDescriptor, TempDescriptor>();
34 //Compute intersection
36 Set<TempDescriptor> liveset=livetemps.get(fn);
37 for(int i=1; i<fn.numPrev(); i++) {
38 Hashtable<TempDescriptor, TempDescriptor> tp=table.get(fn.getPrev(i));
41 for(Iterator tmpit=tp.entrySet().iterator(); tmpit.hasNext(); ) {
42 Map.Entry t=(Map.Entry)tmpit.next();
43 TempDescriptor tmp=(TempDescriptor)t.getKey();
44 if (!liveset.contains(tmp))
46 TempDescriptor dsttmp=tp.get(tmp);
47 if (!tab.containsKey(tmp)) {
49 } else if (tab.get(tmp)!=dsttmp) {
50 tab.put(tmp, bogustd);
55 HashSet<TempDescriptor> toremove=new HashSet<TempDescriptor>();
56 TempDescriptor[] writes=fn.writesTemps();
57 for(int i=0; i<writes.length; i++) {
58 TempDescriptor tmp=writes[i];
60 for(Iterator<TempDescriptor> tmpit=tab.keySet().iterator(); tmpit.hasNext(); ) {
61 TempDescriptor tmp2=tmpit.next();
62 if (tmp==tab.get(tmp2))
67 for(Iterator<TempDescriptor> tmpit=toremove.iterator(); tmpit.hasNext(); ) {
68 TempDescriptor tmp=tmpit.next();
69 tab.put(tmp, bogustd);
72 if (fn.kind()==FKind.FlatOpNode) {
73 FlatOpNode fon=(FlatOpNode)fn;
74 if (fon.getOp().getOp()==Operation.ASSIGN) {
75 tab.put(fon.getDest(), fon.getLeft());
78 if (!table.containsKey(fn)||!table.get(fn).equals(tab)) {
81 for(int i=0; i<fn.numNext(); i++) {
82 FlatNode nnext=fn.getNext(i);
86 } //end of dataflow while loop
88 Set<FlatNode> nodeset=fm.getNodeSet();
90 for(Iterator<FlatNode> it=fm.getNodeSet().iterator(); it.hasNext(); ) {
91 FlatNode fn=it.next();
95 Hashtable<TempDescriptor, TempDescriptor> tab=new Hashtable<TempDescriptor, TempDescriptor>();
97 for(int i=0; i<fn.numPrev(); i++) {
98 Hashtable<TempDescriptor, TempDescriptor> tp=table.get(fn.getPrev(i));
99 for(Iterator tmpit=tp.entrySet().iterator(); tmpit.hasNext(); ) {
100 Map.Entry t=(Map.Entry)tmpit.next();
101 TempDescriptor tmp=(TempDescriptor)t.getKey();
103 if (!tab.containsKey(tmp))
104 tab.put(tmp, tp.get(tmp));
105 else if (tab.get(tmp)!=tp.get(tmp)) {
106 tab.put(tmp, bogustd);
112 TempDescriptor[] reads=fn.readsTemps();
113 for(int i=0; i<reads.length; i++) {
114 TempDescriptor tmp=reads[i];
115 if (tab.containsKey(tmp)&&tab.get(tmp)!=bogustd) {
118 tmap.addPair(tmp, tab.get(tmp));
123 } //end of remapping for loop