001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.util;
014
015 import java.util.Enumeration;
016 import java.util.HashSet;
017
018
019 /**
020 * SpaceEffGraph package implements a generic directed graph that can
021 * be a multigraph. It uses Lists to model nodes and edges information.<p>
022 *
023 * SpaceEffGraph is a generic graph. Extend to implement specific
024 * graph types.
025 */
026 public class SpaceEffGraph implements Graph, TopSortInterface {
027 /**
028 * First node
029 */
030 protected SpaceEffGraphNode _firstNode;
031 /**
032 * Last node
033 */
034 protected SpaceEffGraphNode _lastNode;
035 /**
036 * Nodes with no predecessors
037 */
038 private SpaceEffGraphNodeListHeader _rootNodes;
039 /**
040 * Topological sort order
041 */
042 private SpaceEffGraphNodeListHeader _topSortNodes; // top sort order.
043
044 /**
045 * Number of nodes
046 */
047 protected int numberOfNodes;
048
049 @Override
050 public final int numberOfNodes() { return numberOfNodes; }
051
052 /**
053 * Set number of nodes
054 * @param n new number of nodes
055 */
056 public final void setNumberOfNodes(int n) { numberOfNodes = n; }
057
058 /**
059 * Get the next node number
060 * @return the node number
061 */
062 public final int allocateNodeNumber() { return numberOfNodes++; }
063
064 /**
065 * Renumber the nodes densely from 0...numberOfNodes-1.
066 */
067 @Override
068 public void compactNodeNumbering() {
069 int number = 0;
070 for (SpaceEffGraphNode n = _firstNode; n != null; n = n.getNext()) {
071 n.setNumber(number++);
072 }
073 numberOfNodes = number;
074 }
075
076 /**
077 * Enumerate the nodes in no particular order
078 */
079 @Override
080 public Enumeration<GraphNode> enumerateNodes() {
081 return new NodeEnumeration(_firstNode);
082 }
083
084 //////////////////
085 // The following are to implement TopSortInterface.
086 //////////////////
087
088 @Override
089 public SortedGraphNode startNode(boolean forward) {
090 if (forward) {
091 return (SortedGraphNode) _firstNode;
092 } else {
093 return (SortedGraphNode) _lastNode;
094 }
095 }
096
097 @Override
098 public boolean isTopSorted(boolean forward) {
099 if (forward) {
100 return forwardTopSorted;
101 } else {
102 return backwardTopSorted;
103 }
104 }
105
106 @Override
107 public void setTopSorted(boolean forward) {
108 if (forward) {
109 forwardTopSorted = true;
110 } else {
111 backwardTopSorted = true;
112 }
113 }
114
115 @Override
116 public void resetTopSorted() {
117 forwardTopSorted = false;
118 backwardTopSorted = false;
119 }
120
121 public boolean forwardTopSorted = false, backwardTopSorted = false;
122
123 //////////////////
124 // End of TopSortInterface implementation
125 //////////////////
126
127 /**
128 * @param inode node to add
129 */
130 @Override
131 public final void addGraphNode(GraphNode inode) {
132 SpaceEffGraphNode node = (SpaceEffGraphNode) inode;
133 //_nodes.add(node);
134 if (_firstNode == null) {
135 _firstNode = node;
136 _lastNode = node;
137 } else {
138 _lastNode.append(node); // this is cheaper than add() call.
139 _lastNode = node;
140 }
141 numberOfNodes++;
142 }
143
144 /**
145 * Remove a node from the graph.
146 * @param node node to remove
147 */
148 public final void removeGraphNode(SpaceEffGraphNode node) {
149 if (node == _firstNode) {
150 if (node == _lastNode) {
151 _firstNode = _lastNode = null;
152 } else {
153 _firstNode = node.getNext();
154 }
155 } else if (node == _lastNode) {
156 _lastNode = node.getPrev();
157 }
158 node.remove();
159 numberOfNodes--;
160 }
161
162 /**
163 * Add an edge to the graph.
164 * @param from start node
165 * @param to end node
166 * @see #addGraphEdge(SpaceEffGraphEdge)
167 */
168 @Override
169 public void addGraphEdge(GraphNode from, GraphNode to) {
170 ((SpaceEffGraphNode) from).insertOut((SpaceEffGraphNode) to);
171 }
172
173 /**
174 * Add an edge to the graph.
175 * @param e edge to insert
176 * @see #addGraphEdge(GraphNode,GraphNode)
177 */
178 public void addGraphEdge(SpaceEffGraphEdge e) {
179 e.fromNode().appendOutEdge(e);
180 e.toNode().appendInEdge(e);
181 }
182
183 /**
184 * Reset the list of nodes of the graph.
185 * WARNING!!! Use with caution if you know what you are doing.
186 * @param firstNode new value of the node list
187 */
188 public final void setFirstNode(SpaceEffGraphNode firstNode) {
189 _firstNode = firstNode;
190 }
191
192 /**
193 * Reset the list of nodes of the graph.
194 * WARNING!!! Use with caution if you know what you are doing.
195 * @param lastNode new value of the node list
196 */
197 public final void setLastNode(SpaceEffGraphNode lastNode) {
198 _lastNode = lastNode;
199 }
200 /**
201 * Get the list of nodes.
202 * @return list of nodes
203 */
204 public final SpaceEffGraphNode firstNode() {
205 return _firstNode;
206 }
207
208 /**
209 * Get the end of the list of nodes.
210 * @return end of the list of nodes
211 */
212 public final SpaceEffGraphNode lastNode() {
213 return _lastNode;
214 }
215
216 /**
217 * Add a root node to the graph.
218 * @param root a node to add
219 */
220 public final void addRootNode(SpaceEffGraphNode root) {
221 //_rootNodes.add(root);
222 if (_rootNodes == null) {
223 _rootNodes = new SpaceEffGraphNodeListHeader();
224 }
225 _rootNodes.append(root);
226 }
227
228 /**
229 * Get the list of root nodes.
230 * @return list of root nodes
231 */
232 public final SpaceEffGraphNodeList rootNodes() {
233 return _rootNodes.first();
234 }
235
236 /**
237 * Get the topological order of nodes.
238 * @return topological order of nodes
239 */
240 public final SpaceEffGraphNodeList topSortOrder() {
241 return _topSortNodes.first();
242 }
243
244 /**
245 * Clear the DFS flags.
246 */
247 public final void clearDFS() {
248 for (SpaceEffGraphNode n = firstNode(); n != null; n = n.getNext()) {
249 n.clearDfsVisited();
250 }
251 }
252
253 /**
254 * Build a topological sort of this graph
255 */
256 public void buildTopSort() {
257 if (!forwardTopSorted) {
258 //SortedGraphNode node =
259 TopSort.buildTopological(this, true);
260 // currently, no one cares about the return value, so we don't return it
261 }
262 }
263
264 /**
265 * Build a reverse topological sort of this graph
266 * @return a node if we build a new order, null if we reused the old
267 */
268 public SortedGraphNode buildRevTopSort() {
269 if (!backwardTopSorted) {
270 return TopSort.buildTopological(this, false);
271 } else {
272 return null;
273 }
274 }
275
276 ///////////////////////
277 // Starting with the root nodes, topologically sort them using
278 // the out edge information. Builds the _topSortNodes list.
279 // TODO: figure out how this works and add comments (IP)
280 ///////////////////////
281
282 protected void initTopSort() {
283 _topSortNodes = new SpaceEffGraphNodeListHeader();
284 }
285
286 protected void addTopSortNode(SpaceEffGraphNode node) {
287 _topSortNodes.append(node);
288 }
289
290 public void topSort() {
291 initTopSort();
292 for (SpaceEffGraphNode n = firstNode(); n != null; n = n.getNext()) {
293 if (n.firstInEdge() == null) { // no predecessors
294 n.setDfsVisited();
295 n.setOnStack();
296 dfs(n);
297 addTopSortNode(n);
298 }
299 }
300 }
301
302 private void dfs(SpaceEffGraphNode node) {
303 for (SpaceEffGraphEdge edge = node.firstOutEdge(); edge != null; edge = edge.getNextOut()) {
304 SpaceEffGraphNode succ = edge.toNode();
305 if (!succ.dfsVisited()) {
306 succ.setDfsVisited();
307 succ.setOnStack();
308 dfs(succ);
309 } else if (succ.onStack() || succ == node) {
310 edge.setBackEdge();
311 }
312 }
313 node.clearOnStack();
314 for (SpaceEffGraphEdge edge = node.firstOutEdge(); edge != null; edge = edge.getNextOut()) {
315 SpaceEffGraphNode succ = edge.toNode();
316 if (!succ.topVisited() && !edge.backEdge()) {
317 addTopSortNode(succ);
318 succ.setTopVisited();
319 }
320 }
321 }
322
323 /**
324 * Return a string representation of this graph.
325 * @return a string representation of the graph
326 */
327 @Override
328 public String toString() {
329 StringBuilder res = new StringBuilder();
330 for (SpaceEffGraphNode n = firstNode(); n != null; n = n.getNext()) {
331 HashSet<SpaceEffGraphEdge> visitedNodes = new HashSet<SpaceEffGraphEdge>();
332 int duplicatedNodes = 0;
333 res.append("\nNode: ").append(n).append("\n");
334 res.append("In nodes:\n");
335 for (SpaceEffGraphEdge inEdge = n.firstInEdge(); inEdge != null; inEdge = inEdge.getNextIn()) {
336 if (visitedNodes.contains(inEdge)) {
337 duplicatedNodes ++;
338 res.append("(Duplicated edge " + inEdge.toNodeString() + ")");
339 if (duplicatedNodes > 5) {
340 break;
341 }
342 } else {
343 visitedNodes.add(inEdge);
344 res.append(inEdge.getTypeString());
345 res.append(" ");
346 res.append(inEdge.fromNode());
347 res.append("\n");
348 }
349 }
350 res.append("\n");
351 visitedNodes.clear();
352 duplicatedNodes=0;
353 res.append("Out nodes:\n");
354 for (SpaceEffGraphEdge out = n.firstOutEdge(); out != null; out = out.getNextOut()) {
355 if (visitedNodes.contains(out)) {
356 duplicatedNodes ++;
357 res.append("(Duplicated edge " + out.toNodeString() + ")");
358 if (duplicatedNodes > 5) {
359 break;
360 }
361 } else {
362 res.append(out.getTypeString());
363 res.append(" ");
364 res.append(out.toNode());
365 res.append("\n");
366 }
367 }
368 if (res.length() > 50000) {
369 res.append("....(giving up too long)\n");
370 break;
371 }
372 }
373 return res.toString();
374 }
375
376 ////////////////////
377 // Return a breadth-first enumeration of the nodes in this CFG.
378 // Note that this is different than topological ordering.
379 // TODO: figure out how this works and add comments (IP)
380 ////////////////////
381
382 /**
383 * Print, to System.out, the basic blocks in depth first order.
384 */
385 public void printDepthFirst() {
386 print(new DepthFirstEnumerator(_firstNode));
387 }
388
389 /**
390 * Print, to System.out, the basic blocks in the order given in
391 * the supplied enumeration.
392 * @param e enumeration order to print blocks
393 */
394 private void print(Enumeration<GraphNode> e) {
395 while (e.hasMoreElements()) {
396 SpaceEffGraphNode bb = (SpaceEffGraphNode) e.nextElement();
397 bb.printExtended();
398 }
399 }
400
401 private static final class NodeEnumeration implements Enumeration<GraphNode> {
402 private SpaceEffGraphNode _node;
403
404 public NodeEnumeration(SpaceEffGraphNode n) { _node = n; }
405
406 @Override
407 public boolean hasMoreElements() { return _node != null; }
408
409 @Override
410 public GraphNode nextElement() {
411 SpaceEffGraphNode n = _node;
412 _node = n.getNext();
413 return n;
414 }
415 }
416 }
417