optimize some analysis so they run faster...benchmarks were taking too long to compil...
[IRC.git] / Robust / src / Analysis / Loops / UseDef.java
1 package Analysis.Loops;
2
3 import IR.Flat.*;
4 import java.util.HashSet;
5 import java.util.Hashtable;
6 import java.util.Set;
7 import java.util.Iterator;
8 import Analysis.Liveness;
9
10 public class UseDef{
11   Hashtable<TempFlatPair, Set<FlatNode>> defs;
12   Hashtable<TempFlatPair, Set<FlatNode>> uses;
13
14   public UseDef() {
15   }
16
17   public UseDef(FlatMethod fm) {
18     analyze(fm);
19   }
20
21   /* Return FlatNodes that define Temp */
22   public Set<FlatNode> defMap(FlatNode fn, TempDescriptor t) {
23     Set<FlatNode> s=defs.get(new TempFlatPair(t,fn));
24     if (s==null)
25       return new HashSet<FlatNode>();
26     else
27       return s;
28   }
29
30   /* Return FlatNodes that use Temp */
31   public Set<FlatNode> useMap(FlatNode fn, TempDescriptor t) {
32     Set<FlatNode> s=uses.get(new TempFlatPair(t,fn));
33     if (s==null)
34       return new HashSet<FlatNode>();
35     else
36       return s;
37   }
38
39   public void analyze(FlatMethod fm) {
40     Hashtable<FlatNode, Set<TempFlatPair>> tmp=new Hashtable<FlatNode, Set<TempFlatPair>>();
41     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
42     Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
43     toanalyze.addAll(fm.getNodeSet());
44     while(!toanalyze.isEmpty()) {
45       FlatNode fn=toanalyze.iterator().next();
46       TempDescriptor[] fnwrites=fn.writesTemps();
47
48       toanalyze.remove(fn);
49       HashSet<TempFlatPair> s=new HashSet<TempFlatPair>();
50       Set<TempDescriptor> liveset=livemap.get(fn);
51       for(int i=0;i<fn.numPrev();i++) {
52         FlatNode prev=fn.getPrev(i);
53         Set<TempFlatPair> prevs=tmp.get(prev);
54         if (prevs!=null) {
55           nexttfp:
56           for(Iterator<TempFlatPair> tfit=prevs.iterator();tfit.hasNext();) {
57             TempFlatPair tfp=tfit.next();
58             if (!liveset.contains(tfp.t))
59               continue;
60             for(int j=0;j<fnwrites.length;j++) {
61               if (tfp.t==fnwrites[j])
62                 continue nexttfp;
63             }
64             s.add(tfp);
65           }
66         }
67         for(int j=0;j<fnwrites.length;j++) {
68           TempFlatPair tfp=new TempFlatPair(fnwrites[j], fn);
69           s.add(tfp);
70         }
71       }
72       if (!tmp.containsKey(fn)||
73           !tmp.get(fn).equals(s)) {
74         tmp.put(fn,s);
75         for(int i=0;i<fn.numNext();i++)
76           toanalyze.add(fn.getNext(i));
77       }
78     }
79     Set<FlatNode> fset=fm.getNodeSet();
80     defs=new Hashtable<TempFlatPair, Set<FlatNode>>();
81     uses=new Hashtable<TempFlatPair, Set<FlatNode>>();
82     for(Iterator<FlatNode> fnit=fset.iterator();fnit.hasNext();) {
83       FlatNode fn=fnit.next();
84       TempDescriptor[] fnreads=fn.readsTemps();
85       Set<TempFlatPair> tfpset=tmp.get(fn);
86       
87       for(int i=0;i<fnreads.length;i++) {
88         TempDescriptor readt=fnreads[i];
89         for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
90           TempFlatPair tfp=tfpit.next();
91           if (tfp.t==readt) {
92             //have use
93             if (!uses.containsKey(tfp))
94               uses.put(tfp,new HashSet<FlatNode>());
95             uses.get(tfp).add(fn);
96             TempFlatPair readtfp=new TempFlatPair(readt,fn);
97             if (!defs.containsKey(readtfp))
98               defs.put(readtfp,new HashSet<FlatNode>());
99             defs.get(readtfp).add(tfp.f);
100           }
101         }
102       }
103     }
104   }
105 }
106
107 class TempFlatPair {
108   FlatNode f;
109   TempDescriptor t;
110   TempFlatPair(TempDescriptor t, FlatNode f) {
111     this.t=t;
112     this.f=f;
113   }
114
115   public int hashCode() {
116     return f.hashCode()^t.hashCode();
117   }
118   public boolean equals(Object o) {
119     TempFlatPair tf=(TempFlatPair)o;
120     return t.equals(tf.t)&&f.equals(tf.f);
121   }
122 }