1 cananian 1.1.2.1 // Prune.java, created Fri Jun 30 19:15:56 2000 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.IR.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
7 cananian 1.1.2.1 import harpoon.Temp.Temp;
8 cananian 1.7 import net.cscott.jutil.BitSetFactory;
9 cananian 1.7 import net.cscott.jutil.SetFactory;
10 cananian 1.7 import net.cscott.jutil.UniqueVector;
11 cananian 1.1.2.1 import harpoon.Util.Util;
12 cananian 1.1.2.1 import java.util.HashMap;
13 cananian 1.1.2.1 import java.util.HashSet;
14 cananian 1.1.2.1 import java.util.Iterator;
15 cananian 1.1.2.1 import java.util.Map;
16 cananian 1.1.2.1 import java.util.Set;
17 cananian 1.1.2.1 /**
18 cananian 1.1.2.1 * <code>Prune</code> quickly prunes dead variable assignments from the
19 cananian 1.1.2.1 * quad graph. It doesn't do a full liveness analysis, so it doesn't
20 cananian 1.1.2.1 * get *everything*, but it works in linear time (well, O(EV) time)
21 cananian 1.1.2.1 * and gets most of the egregious dead vars.
22 cananian 1.1.2.1 *
23 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
24 cananian 1.8 * @version $Id: Prune.java,v 1.8 2004/02/08 03:21:24 cananian Exp $
25 cananian 1.1.2.1 */
26 cananian 1.1.2.1 class Prune {
27 cananian 1.1.2.1 private final static boolean DEBUG=false;
28 cananian 1.1.2.1
29 cananian 1.1.2.1 /** one one can create an instance of this class */
30 cananian 1.1.2.1 private Prune() { }
31 cananian 1.1.2.1
32 cananian 1.1.2.1 /** Remove quads which do nothing but define dead variables from
33 cananian 1.1.2.1 * the CFG. */
34 cananian 1.1.2.1 static void prune(HCode hc) {
35 cananian 1.1.2.1 // the State object does the analysis.
36 cananian 1.1.2.1 State s = new State(hc);
37 cananian 1.1.2.1 // now trim out useless quads.
38 cananian 1.8 for (Object qO : s.useless) {
39 cananian 1.8 Quad q = (Quad) qO;
40 cananian 1.1.2.1 if (DEBUG) System.err.println("PRUNING: #"+q.getID()+" "+q);
41 cananian 1.3.2.1 assert q.nextLength()==1 && q.prevLength()==1;
42 cananian 1.1.2.1 Edge fromE = q.prevEdge(0), toE = q.nextEdge(0);
43 cananian 1.1.2.1 Quad.addEdge((Quad)fromE.from(), fromE.which_succ(),
44 cananian 1.1.2.1 (Quad)toE.to(), toE.which_pred());
45 cananian 1.1.2.1 }
46 cananian 1.1.2.1 // done!
47 cananian 1.1.2.1 }
48 cananian 1.1.2.1
49 cananian 1.1.2.1 private static class State {
50 cananian 1.1.2.1 private final SetFactory sf;
51 cananian 1.1.2.1 private final Map seen = new HashMap();
52 cananian 1.1.2.1 private final Set EMPTY_SET, FULL_SET;
53 cananian 1.1.2.1 /** useless quads, as determined by our analysis. */
54 cananian 1.1.2.1 final Set useless = new HashSet();
55 cananian 1.1.2.1 State(HCode hc) {
56 cananian 1.1.2.1 // create Temp universe.
57 cananian 1.1.2.1 Set universe = new HashSet();
58 cananian 1.1.2.1 for (Iterator it=hc.getElementsI(); it.hasNext(); ) {
59 cananian 1.1.2.1 Quad q = (Quad) it.next();
60 cananian 1.1.2.1 universe.addAll(q.defC());
61 cananian 1.1.2.1 universe.addAll(q.useC());
62 cananian 1.1.2.1 }
63 cananian 1.1.2.1 // create BitSetFactory
64 cananian 1.1.2.1 this.sf = new BitSetFactory(universe, Temp.INDEXER);
65 cananian 1.1.2.1 this.EMPTY_SET = sf.makeSet();
66 cananian 1.1.2.1 this.FULL_SET = sf.makeSet(universe);
67 cananian 1.1.2.1 // okay, do the thing that we do.
68 cananian 1.5 // This command will suffice:
69 cananian 1.5 //-------------------------------------
70 cananian 1.5 //knownDeadInto((Quad)hc.getRootElement());
71 cananian 1.5 //-------------------------------------
72 cananian 1.5 // Instead of directly doing the above, we're going to
73 cananian 1.5 // first visit all PHIs in post-order DFS. This will
74 cananian 1.5 // limit the amount of on-stack recursion required for
75 cananian 1.5 // the algorithm, without changing any of the results.
76 cananian 1.5 // (or the running time, hopefully!)
77 cananian 1.5
78 cananian 1.5 UniqueVector worklist = new UniqueVector();
79 cananian 1.6 // order nodes in reverse post-order.
80 cananian 1.5 worklist.add(hc.getRootElement());
81 cananian 1.5 for (int i=0; i<worklist.size(); i++) {
82 cananian 1.5 Quad q = (Quad) worklist.get(i);
83 cananian 1.6 for (int j=q.nextLength()-1; j>=0; j--)
84 cananian 1.5 worklist.add(q.next(j));
85 cananian 1.5 }
86 cananian 1.6 // reverse order of worklist to get post-order dfs.
87 cananian 1.5 // so, do knownDeadInto() in that order.
88 cananian 1.5 for (int i=worklist.size()-1; i>=0; i--) {
89 cananian 1.5 Quad q = (Quad) worklist.get(i);
90 cananian 1.5 if (q instanceof PHI || q instanceof HEADER)
91 cananian 1.5 knownDeadInto(q);
92 cananian 1.5 }
93 cananian 1.5
94 cananian 1.1.2.1 // now we've got a useless set.
95 cananian 1.1.2.1 }
96 cananian 1.1.2.1
97 cananian 1.1.2.1 /** main body of the analysis is a post-order dfs search */
98 cananian 1.1.2.1 private Set knownDeadInto(Quad q) {
99 cananian 1.1.2.1 if (seen.containsKey(q)) return sf.makeSet((Set) seen.get(q));
100 cananian 1.1.2.1 if (q.prevLength()>1) seen.put(q, EMPTY_SET);
101 cananian 1.1.2.3 Set r = (q.nextLength()<1) ? sf.makeSet(FULL_SET) :
102 cananian 1.1.2.3 knownDeadInto(q.next(0));
103 cananian 1.1.2.3 for (int i=1; i<q.nextLength(); i++)
104 cananian 1.1.2.3 r.retainAll(knownDeadInto(q.next(i)));
105 cananian 1.1.2.1 // now we have the knownDeadOutOf set.
106 cananian 1.1.2.1 if (isUseless(q, r)) useless.add(q);
107 cananian 1.1.2.1 // construct knownDeadInto set:
108 cananian 1.1.2.1 // all defs of this instr are known dead into this.
109 cananian 1.1.2.1 r.addAll(q.defC());
110 cananian 1.1.2.1 // all uses of this instr are live into this.
111 cananian 1.1.2.1 // (note that the simpler r.removeAll(q.useC()) uses time
112 cananian 1.1.2.1 // proportional to the size of *r*, which is not what we want)
113 cananian 1.1.2.1 for (Iterator it=q.useC().iterator(); it.hasNext(); )
114 cananian 1.1.2.1 r.remove(it.next());
115 cananian 1.1.2.1 if (DEBUG)
116 cananian 1.1.2.1 System.err.println("DEAD INTO #"+q.getID()+" is "+r+
117 cananian 1.1.2.1 " (using "+q.useC()+")");
118 cananian 1.1.2.1 // if this is a phi, record the set.
119 cananian 1.1.2.1 if (q.prevLength()>1) seen.put(q, sf.makeSet(r));
120 cananian 1.1.2.1 // okay, this is it!
121 cananian 1.1.2.1 return r;
122 cananian 1.1.2.1 }
123 cananian 1.1.2.1
124 cananian 1.1.2.1 private static boolean isUseless(Quad q, Set knownDeadOut) {
125 cananian 1.1.2.1 // quads defining live variables are not useless.
126 cananian 1.1.2.1 if (!knownDeadOut.containsAll(q.defC())) return false;
127 cananian 1.1.2.1 // also, quads with side effects are not useless.
128 cananian 1.1.2.1 if (q instanceof ARRAYINIT || q instanceof ASET ||
129 cananian 1.1.2.1 q instanceof SIGMA || q instanceof PHI ||
130 cananian 1.1.2.1 q instanceof DEBUG || q instanceof HANDLER ||
131 cananian 1.1.2.1 q instanceof HEADER || q instanceof FOOTER ||
132 cananian 1.1.2.1 q instanceof LABEL || q instanceof METHOD ||
133 cananian 1.1.2.1 q instanceof MONITORENTER || q instanceof MONITOREXIT ||
134 cananian 1.1.2.1 q instanceof TYPECAST || q instanceof RETURN ||
135 cananian 1.1.2.1 q instanceof SET || q instanceof THROW)
136 cananian 1.1.2.1 return false;
137 cananian 1.1.2.1 // otherwise, it's useless!
138 cananian 1.1.2.1 if (DEBUG)
139 cananian 1.1.2.1 System.err.println("#"+q.getID()+" is useless because all of "+
140 cananian 1.1.2.1 q.defC()+" are in "+knownDeadOut);
141 cananian 1.1.2.1 return true;
142 cananian 1.1.2.1 }
143 cananian 1.1.2.1 }
144 cananian 1.2 }