1 ovy      1.1 package harpoon.Analysis.MemOpt;
 2 ovy      1.1 
 3 ovy      1.1 /* This computes SSI liveness via a simple O(E) algorithm.
 4 ovy      1.1    FIXME: add comments, implement Liveness
 5 ovy      1.1    FIXME: make non-recursive postfix sort.
 6 ovy      1.1 */
 7 ovy      1.1 
 8 cananian 1.3 import harpoon.ClassFile.HCode;
 9 cananian 1.3 import harpoon.IR.Quads.Edge;
10 cananian 1.3 import harpoon.IR.Quads.PHI;
11 cananian 1.3 import harpoon.IR.Quads.Quad;
12 cananian 1.4 import net.cscott.jutil.AggregateSetFactory;
13 cananian 1.4 import net.cscott.jutil.GenericMultiMap;
14 cananian 1.4 import net.cscott.jutil.LinearSet;
15 cananian 1.4 import net.cscott.jutil.MultiMap;
16 cananian 1.3 import java.util.Collection;
17 cananian 1.3 import java.util.HashSet;
18 cananian 1.3 import java.util.Iterator;
19 cananian 1.3 import java.util.LinkedList;
20 cananian 1.3 import java.util.List;
21 cananian 1.3 import java.util.Set;
22 ovy      1.1 
23 ovy      1.1 public class SSILiveness {
24 ovy      1.1 
25 ovy      1.1     private MultiMap liveOut;
26 ovy      1.1     
27 ovy      1.1     public SSILiveness(HCode hcode) {
28 ovy      1.1         Set reached = new HashSet();
29 ovy      1.1         List sorted = new LinkedList();
30 ovy      1.1 
31 ovy      1.1         postfixSort((Quad)hcode.getElementsI().next(), sorted, reached);
32 ovy      1.1 
33 ovy      1.1         liveOut = new GenericMultiMap(new AggregateSetFactory());
34 ovy      1.1 
35 cananian 1.5         for (Object qO : sorted) {
36 cananian 1.5             Quad q = (Quad) qO;
37 ovy      1.1 
38 ovy      1.1             // compute this node's liveOut
39 ovy      1.1             for (int j = 0; j<q.nextLength(); j++) {
40 ovy      1.1                 Edge edge = q.nextEdge(j);
41 ovy      1.1 
42 ovy      1.1                 liveOut.addAll(q, liveOn_helper(edge));
43 ovy      1.1             }
44 ovy      1.1             
45 ovy      1.1         }
46 ovy      1.1     }
47 ovy      1.1 
48 ovy      1.1 
49 ovy      1.1     public Set getLiveOn(Edge edge) {
50 ovy      1.1         return liveOn_helper(edge);
51 ovy      1.1     }
52 ovy      1.1     
53 ovy      1.1     private Set liveOn_helper(Edge edge) {
54 cananian 1.2         Quad to = edge.to();
55 ovy      1.1         int branch = edge.which_pred();
56 ovy      1.1 
57 ovy      1.1         Collection lvOut_to = liveOut.getValues(to);
58 ovy      1.1 
59 ovy      1.1         Set lvOn = new LinearSet(lvOut_to.size());
60 ovy      1.1         lvOn.addAll(lvOut_to);
61 ovy      1.1 
62 ovy      1.1         lvOn.removeAll(to.defC());
63 ovy      1.1 
64 ovy      1.1         // treat phis separately
65 ovy      1.1         if (to instanceof PHI) {
66 ovy      1.1             PHI qPhi = (PHI) to;
67 ovy      1.1 
68 ovy      1.1             for (int i = 0; i<qPhi.numPhis(); i++) {
69 ovy      1.1                 lvOn.add(qPhi.src(i, branch));
70 ovy      1.1             }
71 ovy      1.1         } else lvOn.addAll(to.useC());
72 ovy      1.1 
73 ovy      1.1         return lvOn;
74 ovy      1.1     }
75 ovy      1.1         
76 ovy      1.1     private void postfixSort(Quad q, List nodes, Set reached) {
77 ovy      1.1         reached.add(q);
78 ovy      1.1 
79 ovy      1.1         for (int i = 0; i<q.nextLength(); i++) {
80 ovy      1.1             Quad son = (Quad) q.nextEdge(i).to();
81 ovy      1.1             if (!reached.contains(son)) {
82 ovy      1.1                 postfixSort(son, nodes, reached);
83 ovy      1.1             }
84 ovy      1.1         }
85 ovy      1.1 
86 ovy      1.1         nodes.add(q);
87 ovy      1.1     }
88 ovy      1.1 
89 ovy      1.1     public String toString() {
90 ovy      1.1         return " liveOut mmap: " + liveOut;
91 ovy      1.1     }
92 ovy      1.1         
93 ovy      1.1         
94 ovy      1.1 }