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