1 cananian 1.1.2.1 // Unreachable.java, created Wed Feb 24 20:03:06 1999 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1999 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.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.3 import harpoon.Analysis.Maps.Derivation;
7 cananian 1.1.2.3
8 cananian 1.1.2.3 import harpoon.ClassFile.HCode;
9 cananian 1.1.2.3
10 cananian 1.1.2.3 import harpoon.IR.LowQuad.DerivationMap;
11 cananian 1.1.2.2 import harpoon.IR.LowQuad.LowQuadVisitor;
12 cananian 1.1.2.1 import harpoon.IR.Quads.Edge;
13 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
14 cananian 1.1.2.1 import harpoon.IR.Quads.FOOTER;
15 cananian 1.1.2.1 import harpoon.IR.Quads.HEADER;
16 cananian 1.1.2.3 import harpoon.IR.Quads.MOVE;
17 cananian 1.1.2.1 import harpoon.IR.Quads.PHI;
18 cananian 1.1.2.1
19 cananian 1.1.2.3 import harpoon.Temp.Temp;
20 cananian 1.1.2.3
21 cananian 1.1.2.1 import harpoon.Util.Util;
22 cananian 1.6 import net.cscott.jutil.WorkSet;
23 cananian 1.1.2.1
24 cananian 1.1.2.1 import java.util.ArrayList;
25 cananian 1.1.2.1 import java.util.Collections;
26 cananian 1.1.2.1 import java.util.HashSet;
27 cananian 1.1.2.1 import java.util.Iterator;
28 cananian 1.1.2.1 import java.util.List;
29 cananian 1.1.2.1 import java.util.Set;
30 cananian 1.1.2.1 import java.util.Stack;
31 cananian 1.1.2.1 /**
32 cananian 1.1.2.1 * <code>Unreachable</code> gets rid of unreachable code.
33 cananian 1.1.2.1 * <b>CAUTION</b>: it modifies code in-place.
34 cananian 1.1.2.1 *
35 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
36 cananian 1.6 * @version $Id: Unreachable.java,v 1.6 2004/02/08 01:53:14 cananian Exp $
37 cananian 1.1.2.1 */
38 cananian 1.1.2.1 public abstract class Unreachable {
39 cananian 1.1.2.1
40 cananian 1.1.2.3 /** Prunes unreachable code from a quad graph in-place. Also updates
41 cananian 1.1.2.3 * the derivation for the <code>HCode</code>, if present. */
42 cananian 1.5 public static final void prune(harpoon.IR.Quads.Code hc) {
43 cananian 1.1.2.3 // fetch or invalidate mutable derivation information.
44 cananian 1.5 DerivationMap<Quad> dm = null;
45 cananian 1.5 if (hc.getDerivation()!=null) {
46 cananian 1.1.2.3 harpoon.IR.LowQuad.Code c = (harpoon.IR.LowQuad.Code) hc;
47 cananian 1.1.2.3 if (c.getDerivation() instanceof DerivationMap)
48 cananian 1.5 dm = (DerivationMap<Quad>) c.getDerivation();
49 cananian 1.1.2.3 else {
50 cananian 1.1.2.3 //c.setDerivation(null); // clear derivation information.
51 cananian 1.3.2.1 assert false; // can't invalidate, can't update, abort!
52 cananian 1.1.2.3 }
53 cananian 1.1.2.3 }
54 cananian 1.5 prune(hc.getRootElement(), dm);
55 cananian 1.1.2.3 }
56 cananian 1.1.2.3 /** Prunes unreachable code *without updating the derivation*. */
57 cananian 1.1.2.1 public static final void prune(HEADER header) {
58 cananian 1.1.2.3 prune(header, null);
59 cananian 1.1.2.3 }
60 cananian 1.1.2.3 /** private pruning method. */
61 cananian 1.5 private static final void prune(HEADER header, DerivationMap<Quad> dm) {
62 cananian 1.1.2.3 // okay, now find the unreachable code and prune it.
63 cananian 1.5 Set<Quad> reachable = (new ReachabilityVisitor(header)).reachableSet();
64 cananian 1.1.2.3 (new PruningVisitor(reachable, dm)).prune();
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1
67 cananian 1.1.2.1 /** Class to do reachability analysis. */
68 cananian 1.1.2.2 static private class ReachabilityVisitor extends LowQuadVisitor {
69 cananian 1.5 final Set<Quad> reachable = new HashSet<Quad>();
70 cananian 1.5 WorkSet<Quad> todo = new WorkSet<Quad>();
71 cananian 1.1.2.1 ReachabilityVisitor(HEADER h) {
72 cananian 1.1.2.2 super(false); /* not strict low quad */
73 cananian 1.1.2.1 todo.add(h);
74 cananian 1.1.2.1 while (!todo.isEmpty())
75 cananian 1.5 todo.pop().accept(this);
76 cananian 1.1.2.1
77 cananian 1.1.2.1 todo = null; // free space.
78 cananian 1.1.2.1 }
79 cananian 1.5 public Set<Quad> reachableSet() { return reachable; }
80 cananian 1.1.2.1
81 cananian 1.1.2.1 public void visit(Quad q) {
82 cananian 1.1.2.1 reachable.add(q);
83 cananian 1.1.2.1 Quad[] nxt = q.next();
84 cananian 1.1.2.1 for (int i=0; i<nxt.length; i++)
85 cananian 1.1.2.1 if (!reachable.contains(nxt[i]))
86 cananian 1.1.2.1 todo.add(nxt[i]);
87 cananian 1.1.2.1 }
88 cananian 1.1.2.1 }
89 cananian 1.1.2.1
90 cananian 1.1.2.1 /** Class to do the pruning of unreachable edges. */
91 cananian 1.1.2.2 static private class PruningVisitor extends LowQuadVisitor {
92 cananian 1.5 final Set<Quad> reachable;
93 cananian 1.5 final DerivationMap<Quad> dm;
94 cananian 1.5 PruningVisitor(Set<Quad> reachable, DerivationMap<Quad> dm) {
95 cananian 1.1.2.2 super(false); /* not strict low quad */
96 cananian 1.1.2.2 this.reachable = reachable;
97 cananian 1.1.2.3 this.dm = dm;
98 cananian 1.1.2.2 }
99 cananian 1.1.2.1 void prune() {
100 cananian 1.1.2.1 // dump the original live elements into a list.
101 cananian 1.5 List<Quad> l = new ArrayList<Quad>(reachable);
102 cananian 1.5 for (Iterator<Quad> it=l.iterator(); it.hasNext(); )
103 cananian 1.5 it.next().accept(this);
104 cananian 1.1.2.1 }
105 cananian 1.1.2.1 public void visit(Quad q) { /* do nothing. */ }
106 cananian 1.1.2.1 public void visit(PHI q) {
107 cananian 1.1.2.1 // remove unused inputs to PHI.
108 cananian 1.1.2.3 PHI oldphi = q;
109 cananian 1.1.2.1 for (int i=q.prevLength()-1; i>=0; i--)
110 cananian 1.1.2.1 if (!reachable.contains(q.prev(i)))
111 cananian 1.1.2.1 q = q.shrink(i);
112 cananian 1.1.2.3 if (oldphi != q) { // update derivation/make reachable
113 cananian 1.1.2.3 if (dm!=null) updateDM(oldphi, q);
114 cananian 1.1.2.3 reachable.add(q);
115 cananian 1.1.2.3 }
116 cananian 1.1.2.1
117 cananian 1.1.2.1 // if it shrinks too small, then remove it.
118 cananian 1.1.2.3 if (q.arity()==1) { // make arity-1 PHI into MOVEs.
119 cananian 1.1.2.1 Edge in = q.prevEdge(0), out = q.nextEdge(0);
120 cananian 1.5 Quad header = in.from();
121 cananian 1.1.2.3 int which_succ = in.which_succ();
122 cananian 1.1.2.3 for (int i=0; i<q.numPhis(); i++) {
123 cananian 1.1.2.3 MOVE m=new MOVE(q.getFactory(), q, q.dst(i), q.src(i, 0));
124 cananian 1.1.2.3 Quad.addEdge(header, which_succ, m, 0);
125 cananian 1.1.2.3 header = m; which_succ = 0;
126 cananian 1.1.2.3 reachable.add(m);
127 cananian 1.1.2.3 if (dm!=null) dm.update(q, q.dst(i), m, m.dst());
128 cananian 1.1.2.3 }
129 cananian 1.1.2.3 Quad.addEdge(header, which_succ,
130 cananian 1.1.2.1 (Quad)out.to(), out.which_pred());
131 cananian 1.1.2.3 }
132 cananian 1.1.2.1 }
133 cananian 1.1.2.1 public void visit(FOOTER q) {
134 cananian 1.1.2.1 // remove unused inputs to footer.
135 cananian 1.1.2.1 for (int i=q.prevLength()-1; i>=0; i--)
136 cananian 1.1.2.1 if (!reachable.contains(q.prev(i)))
137 cananian 1.1.2.1 q = q.remove(i);
138 cananian 1.1.2.1
139 cananian 1.1.2.1 // make sure new quad is marked as reachable.
140 cananian 1.1.2.1 reachable.add(q);
141 cananian 1.1.2.3 }
142 cananian 1.1.2.3
143 cananian 1.1.2.3 private void updateDM(Quad oldq, Quad newq) {
144 cananian 1.1.2.3 // transfer derivations of temps defined in newq
145 cananian 1.1.2.3 Temp[] defs = newq.def();
146 cananian 1.1.2.3 for (int i=0; i<defs.length; i++)
147 cananian 1.1.2.3 dm.update(oldq, defs[i], newq, defs[i]);
148 cananian 1.1.2.3 // clear out any left over derivations from oldq
149 cananian 1.1.2.3 defs = oldq.def();
150 cananian 1.1.2.3 for (int i=0; i<defs.length; i++)
151 cananian 1.1.2.3 dm.remove(oldq, defs[i]);
152 cananian 1.1.2.1 }
153 cananian 1.1.2.1 }
154 cananian 1.2 }