1 cananian 1.1 // QuadFlowGraph.java, created Fri May 9 18:34:48 2003 by cananian
2 cananian 1.1 // Copyright (C) 2003 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Analysis.Companions;
5 cananian 1.1
6 cananian 1.2 import harpoon.IR.Quads.CALL;
7 cananian 1.2 import harpoon.IR.Quads.CJMP;
8 cananian 1.1 import harpoon.IR.Quads.PHI;
9 cananian 1.1 import harpoon.IR.Quads.Quad;
10 cananian 1.1 import harpoon.IR.Quads.SIGMA;
11 cananian 1.2 import harpoon.IR.Quads.SWITCH;
12 cananian 1.2 import harpoon.IR.Quads.TYPESWITCH;
13 cananian 1.2 import harpoon.Temp.Temp;
14 cananian 1.1 import harpoon.Util.Collections.AbstractGraph;
15 cananian 1.3 import net.cscott.jutil.WorkSet;
16 cananian 1.2 import java.util.ArrayList;
17 cananian 1.2 import java.util.Arrays;
18 cananian 1.2 import java.util.Collection;
19 cananian 1.2 import java.util.Collections;
20 cananian 1.1 import java.util.HashMap;
21 cananian 1.1 import java.util.Iterator;
22 cananian 1.2 import java.util.List;
23 cananian 1.1 import java.util.Map;
24 cananian 1.1 /**
25 cananian 1.1 * <code>QuadFlowGraph</code> is an expanded flow graphs for Quads, where
26 cananian 1.1 * additional nodes are added before PHI and after SIGMA nodes to make the
27 cananian 1.1 * dataflow corresponding to the phi and sigma functions easier to express.
28 cananian 1.1 * Move operations corresponding to a PHI (SIGMA) can now take place
29 cananian 1.1 * conceptually before (after) the node, on the incoming (outgoing) edge.
30 cananian 1.1 *
31 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
32 cananian 1.3 * @version $Id: QuadFlowGraph.java,v 1.3 2004/02/08 01:50:55 cananian Exp $
33 cananian 1.1 */
34 cananian 1.1 public class QuadFlowGraph extends AbstractGraph<QNode,QEdge> {
35 cananian 1.1
36 cananian 1.1 /** Creates a <code>QuadFlowGraph</code>. */
37 cananian 1.1 public QuadFlowGraph(harpoon.IR.Quads.Code c) {
38 cananian 1.1 Map<Quad,QNode> map = new HashMap<Quad,QNode>();
39 cananian 1.1 WorkSet<harpoon.IR.Quads.Edge> ws=new WorkSet<harpoon.IR.Quads.Edge>();
40 cananian 1.1 // make nodes for all Quads.
41 cananian 1.1 for (Iterator<Quad> it=c.getElementsI(); it.hasNext(); ) {
42 cananian 1.1 Quad q = it.next();
43 cananian 1.1 QNode qn = new NormalNode(this, q);
44 cananian 1.1 map.put(q, qn);
45 cananian 1.1 addNode(qn);
46 cananian 1.1 ws.addAll(q.edgeC());
47 cananian 1.1 }
48 cananian 1.1 // make QEdges for all Edges
49 cananian 1.1 while (!ws.isEmpty()) {
50 cananian 1.1 harpoon.IR.Quads.Edge e = ws.removeFirst();
51 cananian 1.1 QNode fr = map.get(e.from());
52 cananian 1.1 if (fr.baseQuad() instanceof SIGMA) { // split Sigma edge
53 cananian 1.1 QNode qn = new SigmaExitNode(this, (SIGMA) fr.baseQuad(),
54 cananian 1.1 e.which_succ());
55 cananian 1.1 addNode(qn);
56 cananian 1.1 addEdge(fr, qn);
57 cananian 1.1 fr = qn;
58 cananian 1.1 }
59 cananian 1.1 QNode to = map.get(e.to());
60 cananian 1.1 if (to.baseQuad() instanceof PHI) { // split phi edge
61 cananian 1.1 QNode qn = new PhiEntranceNode(this, (PHI) to.baseQuad(),
62 cananian 1.1 e.which_pred());
63 cananian 1.1 addNode(qn);
64 cananian 1.1 addEdge(qn, to);
65 cananian 1.1 to = qn;
66 cananian 1.1 }
67 cananian 1.1 addEdge(fr, to);
68 cananian 1.1 }
69 cananian 1.1 // done!
70 cananian 1.1 }
71 cananian 1.1 public QEdge addEdge(QNode from, QNode to) {
72 cananian 1.1 QEdge qe = new QEdge(from, to);
73 cananian 1.1 this.addEdge(qe);
74 cananian 1.1 return qe;
75 cananian 1.1 }
76 cananian 1.1 }
77 cananian 1.1 // Bug in JSR-14 compiler prevents these from being inner classes, as they
78 cananian 1.1 // ought be.
79 cananian 1.1 /** A <code>QNode</code> is an element of the <code>QuadFlowGraph</code>.
80 cananian 1.1 * Most <code>QNode</code> correspond to <code>Quad</code>s in the underlying
81 cananian 1.1 * flowgraph (these are instances of the <code>QNode</code> subclass
82 cananian 1.1 * <code>NormalNode</code>, but there are also <code>QNode</code>s
83 cananian 1.1 * representing artificial nodes before <code>PHI</code>s
84 cananian 1.1 * (<code>PhiEntranceNode</code>) and after <code>SIGMA</code>s
85 cananian 1.1 * (<code>SigmaExitNode</code>). Because of this, the <code>QNode</code>
86 cananian 1.1 * may have different edges than the underlying <code>Quad</code>
87 cananian 1.1 * returned by the <code>baseQuad()</code> method.
88 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
89 cananian 1.3 * @version $Id: QuadFlowGraph.java,v 1.3 2004/02/08 01:50:55 cananian Exp $
90 cananian 1.1 */
91 cananian 1.1 abstract class QNode extends AbstractGraph.Node<QNode,QEdge> {
92 cananian 1.1 QNode(QuadFlowGraph parent) { super(parent); }
93 cananian 1.1 abstract Quad baseQuad();
94 cananian 1.1 abstract boolean isPhiEntrance();
95 cananian 1.1 abstract boolean isSigmaExit();
96 cananian 1.1 abstract int whichEdge();
97 cananian 1.2 abstract Collection<Temp> useC();
98 cananian 1.2 abstract Collection<Temp> defC();
99 cananian 1.1 }
100 cananian 1.1 /** A <code>NormalNode</code> wraps an arbitrary <code>Quad</code> and
101 cananian 1.1 * corresponds directly to a node in the underlying flow graph,
102 cananian 1.1 * although the edges may differ if the underlying quad is a
103 cananian 1.1 * <code>PHI</code> or <code>SIGMA</code>.
104 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
105 cananian 1.3 * @version $Id: QuadFlowGraph.java,v 1.3 2004/02/08 01:50:55 cananian Exp $
106 cananian 1.1 */
107 cananian 1.1 final class NormalNode extends QNode {
108 cananian 1.1 final Quad baseQuad;
109 cananian 1.1 NormalNode(QuadFlowGraph parent, Quad baseQuad) {
110 cananian 1.1 super(parent);
111 cananian 1.1 this.baseQuad = baseQuad;
112 cananian 1.1 }
113 cananian 1.1 Quad baseQuad() { return baseQuad; }
114 cananian 1.1 boolean isPhiEntrance() { return false; }
115 cananian 1.1 boolean isSigmaExit() { return false; }
116 cananian 1.1 int whichEdge() { throw new RuntimeException("a normal quad"); }
117 cananian 1.2 Collection<Temp> useC() {
118 cananian 1.2 if (baseQuad instanceof PHI)
119 cananian 1.2 return Collections.EMPTY_LIST;
120 cananian 1.2 if (baseQuad instanceof CALL)
121 cananian 1.2 return Arrays.asList(((CALL)baseQuad).params());
122 cananian 1.2 if (baseQuad instanceof CJMP)
123 cananian 1.2 return Collections.singletonList(((CJMP)baseQuad).test());
124 cananian 1.2 if (baseQuad instanceof SWITCH)
125 cananian 1.2 return Collections.singletonList(((SWITCH)baseQuad).index());
126 cananian 1.2 if (baseQuad instanceof TYPESWITCH)
127 cananian 1.2 return Collections.singletonList(((TYPESWITCH)baseQuad).index());
128 cananian 1.2 return baseQuad.useC();
129 cananian 1.2 }
130 cananian 1.2 Collection<Temp> defC() {
131 cananian 1.2 if (baseQuad instanceof CALL) {
132 cananian 1.2 CALL call = (CALL) baseQuad;
133 cananian 1.2 List<Temp> defs = new ArrayList<Temp>(2);
134 cananian 1.2 if (call.retval()!=null) defs.add(call.retval());
135 cananian 1.2 if (call.retex()!=null) defs.add(call.retex());
136 cananian 1.2 return defs;
137 cananian 1.2 }
138 cananian 1.2 if (baseQuad instanceof PHI ||
139 cananian 1.2 baseQuad instanceof SIGMA)
140 cananian 1.2 return Collections.EMPTY_LIST;
141 cananian 1.2 return baseQuad.defC();
142 cananian 1.2 }
143 cananian 1.1 }
144 cananian 1.1 /** A <code>PhiEntranceNode</code> is an artificial node in the
145 cananian 1.1 * <code>QuadFlowGraph</code> which is inserted on the incoming
146 cananian 1.1 * edge of a <code>PHI</code>. It reports its <code>baseQuad()</code>
147 cananian 1.1 * as the affiliated <code>PHI</code>.
148 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
149 cananian 1.3 * @version $Id: QuadFlowGraph.java,v 1.3 2004/02/08 01:50:55 cananian Exp $
150 cananian 1.1 */
151 cananian 1.1 final class PhiEntranceNode extends QNode {
152 cananian 1.1 final PHI baseQuad; final int whichEdge;
153 cananian 1.1 PhiEntranceNode(QuadFlowGraph parent, PHI baseQuad, int whichEdge) {
154 cananian 1.1 super(parent);
155 cananian 1.1 this.baseQuad = baseQuad; this.whichEdge = whichEdge;
156 cananian 1.1 }
157 cananian 1.1 PHI baseQuad() { return baseQuad; }
158 cananian 1.1 boolean isPhiEntrance() { return true; }
159 cananian 1.1 boolean isSigmaExit() { return false; }
160 cananian 1.1 int whichEdge() { return whichEdge; }
161 cananian 1.2 List<Temp> defC() {
162 cananian 1.2 List<Temp> defs = new ArrayList<Temp>(baseQuad.numPhis());
163 cananian 1.2 for (int i=0; i<baseQuad.numPhis(); i++)
164 cananian 1.2 defs.add(baseQuad.dst(i));
165 cananian 1.2 return defs;
166 cananian 1.2 }
167 cananian 1.2 List<Temp> useC() {
168 cananian 1.2 List<Temp> uses = new ArrayList<Temp>(baseQuad.numPhis());
169 cananian 1.2 for (int i=0; i<baseQuad.numPhis(); i++)
170 cananian 1.2 uses.add(baseQuad.src(i, whichEdge));
171 cananian 1.2 return uses;
172 cananian 1.2 }
173 cananian 1.1 }
174 cananian 1.1 /** A <code>SigmaExitNode</code> is an artificial node in the
175 cananian 1.1 * <code>QuadFlowGraph</code> which is inserted on the outgoing
176 cananian 1.1 * edge of a <code>SIGMA</code>. It reports its <code>baseQuad()</code>
177 cananian 1.1 * as the affiliated <code>SIGMA</code>.
178 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
179 cananian 1.3 * @version $Id: QuadFlowGraph.java,v 1.3 2004/02/08 01:50:55 cananian Exp $
180 cananian 1.1 */
181 cananian 1.1 final class SigmaExitNode extends QNode {
182 cananian 1.1 final SIGMA baseQuad; final int whichEdge;
183 cananian 1.1 SigmaExitNode(QuadFlowGraph parent, SIGMA baseQuad, int whichEdge) {
184 cananian 1.1 super(parent);
185 cananian 1.1 this.baseQuad = baseQuad; this.whichEdge = whichEdge;
186 cananian 1.1 }
187 cananian 1.1 SIGMA baseQuad() { return baseQuad; }
188 cananian 1.1 boolean isPhiEntrance() { return false; }
189 cananian 1.1 boolean isSigmaExit() { return true; }
190 cananian 1.1 int whichEdge() { return whichEdge; }
191 cananian 1.2 List<Temp> defC() {
192 cananian 1.2 List<Temp> defs = new ArrayList<Temp>(baseQuad.numSigmas());
193 cananian 1.2 for (int i=0; i<baseQuad.numSigmas(); i++)
194 cananian 1.2 defs.add(baseQuad.dst(i, whichEdge));
195 cananian 1.2 return defs;
196 cananian 1.2 }
197 cananian 1.2 List<Temp> useC() {
198 cananian 1.2 List<Temp> uses = new ArrayList<Temp>(baseQuad.numSigmas());
199 cananian 1.2 for (int i=0; i<baseQuad.numSigmas(); i++)
200 cananian 1.2 uses.add(baseQuad.src(i));
201 cananian 1.2 return uses;
202 cananian 1.2 }
203 cananian 1.1 }
204 cananian 1.1 /**
205 cananian 1.1 * <code>QEdge</code> represents edges between <code>QNode</code>
206 cananian 1.1 * objects. They usually correspond to <code>Quad.Edge</code> object,
207 cananian 1.1 * but not in the case of inserted <code>PhiEntranceNode</code>s and
208 cananian 1.1 * <code>SigmaExitNode</code>s.
209 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
210 cananian 1.3 * @version $Id: QuadFlowGraph.java,v 1.3 2004/02/08 01:50:55 cananian Exp $
211 cananian 1.1 */
212 cananian 1.1 final class QEdge extends AbstractGraph.Edge<QNode,QEdge> {
213 cananian 1.1 QEdge(QNode from, QNode to) { super(from, to); }
214 cananian 1.1 }