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
017 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
018
019 /**
020 * SpaceEffGraphNode is a generic graph node. Extend this to implement
021 * specific graph node types. A node has a list of out edges and a
022 * list of in edges. We maintain both to support bidirectional traversal
023 * of the graph.
024 */
025 public class SpaceEffGraphNode implements GraphNode {
026
027 /** scratch field: optimizations use as they wish */
028 public Object scratchObject;
029
030 /** any optimization can use this for its own purposes */
031 public int scratch;
032
033 /**
034 * The following word is used for various purposes. The first
035 * 8 bits are used for flags, and the remaining 24 bits for any
036 * node information (node number, for example)
037 */
038 protected int info;
039
040 static final int DFS_VISITED = 0x01000000;
041 static final int TOP_VISITED = 0x02000000;
042 static final int ON_STACK = 0x04000000;
043
044 static final int LOOP_HEADER = 0x08000000;
045
046 static final int INFO_MASK = 0x00ffffff;
047
048 public final boolean dfsVisited() { return (info & DFS_VISITED) != 0; }
049
050 public final boolean topVisited() { return (info & TOP_VISITED) != 0; }
051
052 public final boolean onStack() { return (info & ON_STACK) != 0; }
053
054 public final boolean flagsOn() { return (info & (DFS_VISITED | TOP_VISITED | ON_STACK)) != 0; }
055
056 public final boolean isLoopHeader() { return (info & LOOP_HEADER) != 0; }
057
058 public final void setDfsVisited() { info |= DFS_VISITED; }
059
060 public final void setTopVisited() { info |= TOP_VISITED; }
061
062 public final void setOnStack() { info |= ON_STACK; }
063
064 public final void setDfsVisitedOnStack() { info |= (DFS_VISITED | ON_STACK); }
065
066 public final void setLoopHeader() { info |= LOOP_HEADER; }
067
068 public final void clearDfsVisited() { info &= ~DFS_VISITED; }
069
070 public final void clearTopVisited() { info &= ~TOP_VISITED; }
071
072 public final void clearOnStack() { info &= ~ON_STACK; }
073
074 public final void clearFlags() { info &= ~(DFS_VISITED | TOP_VISITED | ON_STACK); }
075
076 public final void clearLoopHeader() { info &= ~LOOP_HEADER; }
077
078 public int getScratch() { return scratch; }
079
080 public int setScratch(int scratch) { return this.scratch = scratch; }
081
082 public final void setNumber(int value) {
083 info = (info & ~INFO_MASK) | (value & INFO_MASK);
084 }
085
086 public final int getNumber() {
087 return info & INFO_MASK;
088 }
089
090 public final int getIndex() {
091 return getNumber();
092 }
093
094 public final void setIndex(int i) {
095 setNumber(i);
096 }
097
098 /////////////////
099 // The following is used by several node sorting schemes
100 /////////////////
101
102 public SpaceEffGraphNode nextSorted;
103
104 // return the first in/out edge
105
106 public final SpaceEffGraphEdge firstInEdge() {
107 return _inEdgeStart;
108 }
109
110 public final SpaceEffGraphEdge firstOutEdge() {
111 return _outEdgeStart;
112 }
113
114 public final SpaceEffGraphNode firstInNode() {
115 return _inEdgeStart.fromNode();
116 }
117
118 public final SpaceEffGraphNode firstOutNode() {
119 return _outEdgeStart.toNode();
120 }
121
122 /**
123 * clear the in set of edges
124 */
125 final void clearIn() {
126 _inEdgeStart = _inEdgeEnd = null;
127 }
128
129 /**
130 * clear the out set of edges
131 */
132 final void clearOut() {
133 _outEdgeStart = _outEdgeEnd = null;
134 }
135
136 // deletes all the in/out edges
137
138 public final void deleteIn() {
139 for (SpaceEffGraphEdge e = _inEdgeStart; e != null; e = e.nextIn) {
140 e.fromNode().removeOut(e);
141 }
142 clearIn();
143 }
144
145 public final void deleteOut() {
146 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.nextOut) {
147 e.toNode().removeIn(e);
148 }
149 clearOut();
150 }
151
152 /* get number of in/out edges */
153
154 public final int getNumberOfIn() {
155 int count = 0;
156 for (SpaceEffGraphEdge e = _inEdgeStart; e != null; e = e.nextIn) {
157 count++;
158 }
159 return count;
160 }
161
162 public final int getNumberOfOut() {
163 int count = 0;
164 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.nextOut) {
165 count++;
166 }
167 return count;
168 }
169
170 /* specialized versions */
171 public final boolean hasZeroOut() {
172 return _outEdgeStart == null;
173 }
174
175 public final boolean hasZeroIn() {
176 return _inEdgeStart == null;
177 }
178
179 public final boolean hasOneOut() {
180 SpaceEffGraphEdge first = _outEdgeStart;
181 return (first != null) && (first.nextOut == null);
182 }
183
184 public final boolean hasOneIn() {
185 SpaceEffGraphEdge first = _inEdgeStart;
186 return (first != null) && (first.nextIn == null);
187 }
188
189 /* returns true if points to the in/out set */
190
191 public final boolean pointsIn(SpaceEffGraphNode inNode) {
192 for (SpaceEffGraphEdge e = _inEdgeStart; e != null; e = e.nextIn) {
193 if (e.fromNode() == inNode) return true;
194 }
195 return false;
196 }
197
198 public final boolean pointsOut(SpaceEffGraphNode outNode) {
199 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.nextOut) {
200 if (e.toNode() == outNode) return true;
201 }
202 return false;
203 }
204
205 public final boolean hasIn(GraphNode in) {
206 return pointsIn((SpaceEffGraphNode) in);
207 }
208
209 public final boolean hasOut(GraphNode out) {
210 return pointsOut((SpaceEffGraphNode) out);
211 }
212
213 /*
214 * returns the out edge pointing to node n, if it exists.
215 * returns null otherwise
216 */
217 public final SpaceEffGraphEdge findOutEdgeTo(SpaceEffGraphNode n) {
218 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.nextOut) {
219 if (e.toNode() == n) return e;
220 }
221 return null;
222 }
223
224 /*
225 * replaces the in edge matching e1 with e2.
226 * maintains the ordering of edges
227 * YUCK: this data structure is messy. I assume this is in the name
228 * of efficiency, but it makes control flow graph manipulations
229 * a real pain. (SJF)
230 */
231 public final void replaceInEdge(SpaceEffGraphEdge e1, SpaceEffGraphEdge e2) {
232 // set the predecessor of e1 to point to e2
233 if (_inEdgeStart == e1) {
234 _inEdgeStart = e2;
235 } else {
236 // walk the list until we find the predecessor to e1
237 SpaceEffGraphEdge pred = null;
238 for (pred = _inEdgeStart; pred != null; pred = pred.nextIn) {
239 if (pred.nextIn == e1) break;
240 }
241 // if not found, there's an error
242 if (pred == null) {
243 throw new OptimizingCompilerException("SpaceEffGraphNode.replaceInEdge: called incorrectly");
244 }
245 pred.nextIn = e2;
246 }
247 // set e2 to point to e1.nextIn
248 e2.nextIn = e1.nextIn;
249
250 // fix up _inEdgeStart, _inEdgeEnd
251 if (_inEdgeStart == e1) _inEdgeStart = e2;
252 if (_inEdgeEnd == e1) _inEdgeEnd = e2;
253
254 // clear the links of e1
255 e1.nextIn = null;
256 }
257
258 /* returns true if the node is the single predecessor/successor of
259 this block */
260
261 public final boolean hasOneIn(SpaceEffGraphNode inNode) {
262 SpaceEffGraphEdge first = _inEdgeStart;
263 return (first != null) && (first.nextIn == null) && (first.fromNode() == inNode);
264 }
265
266 public final boolean hasOneOut(SpaceEffGraphNode outNode) {
267 SpaceEffGraphEdge first = _outEdgeStart;
268 return (first != null) && (first.nextOut == null) && (first.toNode() == outNode);
269 }
270
271 /* replaces an oldnode with a new node */
272
273 public final void replaceOut(SpaceEffGraphNode oldOut, SpaceEffGraphNode newOut) {
274 deleteOut(oldOut);
275 insertOut(newOut);
276 }
277
278 /* inserts an outgoing edge to a node 'to' */
279
280 public final void insertOut(SpaceEffGraphNode to, SpaceEffGraphEdge e) {
281 this.appendOutEdge(e);
282 to.appendInEdge(e);
283 }
284
285 /* same as before, if you don't care the edge type */
286
287 public final void insertOut(SpaceEffGraphNode to) {
288 if (this.pointsOut(to)) return;
289 SpaceEffGraphEdge e = new SpaceEffGraphEdge(this, to);
290 this.appendOutEdge(e);
291 to.appendInEdge(e);
292 }
293
294 /* delete an outgoing edge to a node */
295
296 public final void deleteOut(SpaceEffGraphNode node) {
297 SpaceEffGraphEdge edge = this.removeOut(node);
298 node.removeIn(edge);
299 }
300
301 /* delete an outgoing edge */
302
303 public final void deleteOut(SpaceEffGraphEdge e) {
304 SpaceEffGraphNode to = e.toNode();
305 this.removeOut(e);
306 to.removeIn(e);
307 }
308
309 /* mark nodes in a DFS manner, result written in 'scratch' */
310 /* NOTE: it assummes that the 'dfs' flag has been cleared before */
311
312 public final void markDFN(int DFN) {
313 setDfsVisited();
314 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.nextOut) {
315 SpaceEffGraphNode n = e.toNode();
316 if (!n.dfsVisited()) {
317 n.markDFN(DFN);
318 }
319 }
320 scratch = DFN - 1;
321 }
322
323 /* mark nodes according to the SCC (Strongly Connected Component Number),
324 result written in 'scratch'
325 NOTE: it assummes that the 'dfs' flag has been cleared before */
326
327 public final void markSCC(int currSCC) {
328 setDfsVisited();
329 scratch = currSCC;
330 for (SpaceEffGraphEdge e = _inEdgeStart; e != null; e = e.nextIn) {
331 SpaceEffGraphNode n = e.fromNode();
332 if (!n.dfsVisited()) {
333 n.markSCC(currSCC);
334 }
335 }
336 }
337
338 /* sort nodes according to DFS. result is a list of nodes with the current
339 as root. Note: it assumes that the dfs flags have been cleared before */
340
341 public final void sortDFS() {
342 _sortDFS(null);
343 }
344
345 protected final void _sortDFS(SpaceEffGraphNode header) {
346 setDfsVisited();
347 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.nextOut) {
348 SpaceEffGraphNode n = e.toNode();
349 if (!n.dfsVisited()) {
350 n._sortDFS(header);
351 header = n;
352 }
353 }
354 nextSorted = header;
355 }
356
357 /* clear all out/in flags */
358
359 public final void clearOutFlags() {
360 clearFlags();
361 for (SpaceEffGraphEdge e = firstOutEdge(); e != null; e = e.getNextOut()) {
362 SpaceEffGraphNode succ = e.toNode();
363 e.clearVisited();
364 if (succ.flagsOn()) {
365 succ.clearOutFlags();
366 }
367 }
368 }
369
370 public final void clearInFlags() {
371 clearFlags();
372 for (SpaceEffGraphEdge e = firstInEdge(); e != null; e = e.getNextIn()) {
373 SpaceEffGraphNode succ = e.fromNode();
374 e.clearVisited();
375 if (succ.flagsOn()) {
376 succ.clearInFlags();
377 }
378 }
379 }
380
381 /* topological sort of nodes. result is a list of nodes with the current
382 as root */
383
384 public final void sortTop() {
385 clearOutFlags();
386 setDfsVisitedOnStack();
387 nextSorted = _sortTop(null);
388 }
389
390 protected final SpaceEffGraphNode _sortTop(SpaceEffGraphNode tail) {
391 for (SpaceEffGraphEdge e = firstOutEdge(); e != null; e = e.getNextOut()) {
392 SpaceEffGraphNode succ = e.toNode();
393 if (!succ.dfsVisited()) {
394 succ.setDfsVisitedOnStack();
395 tail = succ._sortTop(tail);
396 } else if (succ.onStack() || succ == this) {
397 e.setVisited(); // back edge
398 }
399 }
400 clearOnStack();
401 for (SpaceEffGraphEdge e = firstOutEdge(); e != null; e = e.getNextOut()) {
402 SpaceEffGraphNode succ = e.toNode();
403 if (!succ.topVisited() && !e.visited()) {
404 succ.nextSorted = tail;
405 tail = succ;
406 succ.setTopVisited();
407 }
408 }
409 return tail;
410 }
411
412 /* reverse topological sort of nodes. result is a list of nodes with the
413 current as root */
414
415 public final void sortRevTop() {
416 clearInFlags();
417 setDfsVisitedOnStack();
418 nextSorted = _sortRevTop(null);
419 }
420
421 protected final SpaceEffGraphNode _sortRevTop(SpaceEffGraphNode tail) {
422 for (SpaceEffGraphEdge e = firstInEdge(); e != null; e = e.getNextIn()) {
423 SpaceEffGraphNode succ = e.fromNode();
424 if (!succ.dfsVisited()) {
425 succ.setDfsVisitedOnStack();
426 tail = succ._sortRevTop(tail);
427 } else if (succ.onStack() || succ == this) {
428 e.setVisited(); // forward edge
429 }
430 }
431 clearOnStack();
432 for (SpaceEffGraphEdge e = firstInEdge(); e != null; e = e.getNextIn()) {
433 SpaceEffGraphNode succ = e.fromNode();
434 if (!succ.topVisited() && !e.visited()) {
435 succ.nextSorted = tail;
436 tail = succ;
437 succ.setTopVisited();
438 }
439 }
440 return tail;
441 }
442
443 /* print sorted nodes starting from this */
444
445 final void printSorted() {
446 for (SpaceEffGraphNode n = this; n != null; n = n.nextSorted) {
447 System.out.println(n);
448 }
449 }
450
451 /**
452 * Revert the sequence of out edges
453 */
454 final void revertOuts() {
455 SpaceEffGraphEdge last = null;
456 SpaceEffGraphEdge e = firstOutEdge();
457 _outEdgeStart = _outEdgeEnd;
458 _outEdgeEnd = e;
459 while (e != null) {
460 SpaceEffGraphEdge next = e.getNextOut();
461 e.appendOut(last);
462 last = e;
463 e = next;
464 }
465 }
466
467 /* enumerations to get the nodes/edges */
468
469 public interface GraphEdgeEnumeration<T extends GraphEdge> extends Enumeration<T> {
470 // Same as nextElement but avoid the need to downcast from Object
471 T next();
472 }
473
474 public final InEdgeEnumeration inEdges() {
475 return new InEdgeEnumeration(this);
476 }
477
478 public final OutEdgeEnumeration outEdges() {
479 return new OutEdgeEnumeration(this);
480 }
481
482 public final GraphNodeEnumeration inNodes() {
483 return new InNodeEnumeration(this);
484 }
485
486 public final GraphNodeEnumeration outNodes() {
487 return new OutNodeEnumeration(this);
488 }
489
490 /* print utilities */
491
492 public void printInEdges() {
493 for (SpaceEffGraphEdge in = firstInEdge(); in != null; in = in.getNextIn()) {
494 System.out.println(in.fromNodeString());
495 }
496 }
497
498 public void printOutEdges() {
499 for (SpaceEffGraphEdge out = firstOutEdge(); out != null; out = out.getNextOut()) {
500 System.out.println(out.toNodeString());
501 }
502 }
503
504 public void printInNodes() {
505 for (SpaceEffGraphEdge in = firstInEdge(); in != null; in = in.getNextIn()) {
506 System.out.println(in.fromNode());
507 }
508 }
509
510 public void printOutNodes() {
511 for (SpaceEffGraphEdge out = firstOutEdge(); out != null; out = out.getNextOut()) {
512 System.out.println(out.toNode());
513 }
514 }
515
516 public void printExtended() {
517 System.out.println(this);
518 }
519
520 /////////////////
521 // Implementation: the following is not intended for general client use
522 /////////////////
523
524 protected SpaceEffGraphEdge _outEdgeStart;
525 protected SpaceEffGraphEdge _outEdgeEnd;
526 protected SpaceEffGraphEdge _inEdgeStart;
527 protected SpaceEffGraphEdge _inEdgeEnd;
528
529 //
530 // add an in/out edge from 'node' to this node.
531 //
532
533 // (SJF): I had to make these public to do SSA transformations.
534 // TODO: The CFG data structure should not depend this tightly
535 // on the underlying Graph implementation, but rather should be
536 // designed so that the SSA-like transformations are easy to do.
537
538 protected final void appendInEdge(SpaceEffGraphEdge e) {
539 SpaceEffGraphEdge inEdgeEnd = _inEdgeEnd;
540 if (inEdgeEnd != null) {
541 inEdgeEnd.appendIn(e);
542 } else {
543 _inEdgeStart = e;
544 }
545 _inEdgeEnd = e;
546 }
547
548 protected final void appendOutEdge(SpaceEffGraphEdge e) {
549 SpaceEffGraphEdge outEdgeEnd = _outEdgeEnd;
550 if (outEdgeEnd != null) {
551 outEdgeEnd.appendOut(e);
552 } else {
553 _outEdgeStart = e;
554 }
555 _outEdgeEnd = e;
556 }
557
558 /* remove and edge/node from the in/out set */
559
560 protected final void removeIn(SpaceEffGraphEdge InEdge) {
561 SpaceEffGraphEdge prev = null;
562 for (SpaceEffGraphEdge edge = _inEdgeStart; edge != null; prev = edge, edge = edge.nextIn) {
563 if (edge == InEdge) {
564 SpaceEffGraphEdge next = edge.nextIn;
565 if (prev == null) {
566 _inEdgeStart = next;
567 } else {
568 prev.appendIn(next);
569 }
570 if (next == null) {
571 _inEdgeEnd = prev;
572 }
573 break;
574 }
575 }
576 }
577
578 protected final SpaceEffGraphEdge removeIn(SpaceEffGraphNode InNode) {
579 SpaceEffGraphEdge edge, prev = null;
580 for (edge = _inEdgeStart; edge != null; prev = edge, edge = edge.nextIn) {
581 if (edge.fromNode() == InNode) {
582 SpaceEffGraphEdge next = edge.nextIn;
583 if (prev == null) {
584 _inEdgeStart = next;
585 } else {
586 prev.appendIn(next);
587 }
588 if (next == null) {
589 _inEdgeEnd = prev;
590 }
591 break;
592 }
593 }
594 return edge;
595 }
596
597 protected final void removeOut(SpaceEffGraphEdge OutEdge) {
598 SpaceEffGraphEdge edge, prev = null;
599 for (edge = _outEdgeStart; edge != null; prev = edge, edge = edge.nextOut) {
600 if (edge == OutEdge) {
601 SpaceEffGraphEdge next = edge.nextOut;
602 if (prev == null) {
603 _outEdgeStart = next;
604 } else {
605 prev.appendOut(next);
606 }
607 if (next == null) {
608 _outEdgeEnd = prev;
609 }
610 break;
611 }
612 }
613 }
614
615 protected final SpaceEffGraphEdge removeOut(SpaceEffGraphNode OutNode) {
616 SpaceEffGraphEdge edge, prev = null;
617 for (edge = _outEdgeStart; edge != null; prev = edge, edge = edge.nextOut) {
618 if (edge.toNode() == OutNode) {
619 SpaceEffGraphEdge next = edge.nextOut;
620 if (prev == null) {
621 _outEdgeStart = next;
622 } else {
623 prev.appendOut(next);
624 }
625 if (next == null) {
626 _outEdgeEnd = prev;
627 }
628 break;
629 }
630 }
631 return edge;
632 }
633
634 static final class InEdgeEnumeration implements GraphEdgeEnumeration<GraphEdge> {
635 private SpaceEffGraphEdge _edge;
636
637 public InEdgeEnumeration(SpaceEffGraphNode n) {
638 _edge = n._inEdgeStart;
639 }
640
641 public boolean hasMoreElements() { return _edge != null; }
642
643 public SpaceEffGraphEdge nextElement() { return next(); }
644
645 public SpaceEffGraphEdge next() {
646 SpaceEffGraphEdge e = _edge;
647 _edge = e.nextIn;
648 return e;
649 }
650 }
651
652 static final class InNodeEnumeration implements GraphNodeEnumeration {
653 private SpaceEffGraphEdge _edge;
654
655 public InNodeEnumeration(SpaceEffGraphNode n) {
656 _edge = n._inEdgeStart;
657 }
658
659 public boolean hasMoreElements() { return _edge != null; }
660
661 public GraphNode nextElement() { return next(); }
662
663 public GraphNode next() {
664 SpaceEffGraphEdge e = _edge;
665 _edge = e.nextIn;
666 return e.fromNode();
667 }
668 }
669
670 public static final class OutEdgeEnumeration implements GraphEdgeEnumeration<GraphEdge> {
671 private SpaceEffGraphEdge _edge;
672
673 public OutEdgeEnumeration(SpaceEffGraphNode n) {
674 _edge = n._outEdgeStart;
675 }
676
677 public boolean hasMoreElements() { return _edge != null; }
678
679 public GraphEdge nextElement() { return next(); }
680
681 public GraphEdge next() {
682 SpaceEffGraphEdge e = _edge;
683 _edge = e.nextOut;
684 return e;
685 }
686 }
687
688 static final class OutNodeEnumeration implements GraphNodeEnumeration {
689 private SpaceEffGraphEdge _edge;
690
691 public OutNodeEnumeration(SpaceEffGraphNode n) {
692 _edge = n._outEdgeStart;
693 }
694
695 public boolean hasMoreElements() { return _edge != null; }
696
697 public GraphNode nextElement() { return next(); }
698
699 public GraphNode next() {
700 SpaceEffGraphEdge e = _edge;
701 _edge = e.nextOut;
702 return e.toNode();
703 }
704 }
705
706 /**
707 * Links inlined from DoublyLinkedListElement.
708 */
709 public SpaceEffGraphNode prev, next;
710
711 /**
712 * Get the next node.
713 * @return next node
714 */
715 public final SpaceEffGraphNode getNext() {
716 return next;
717 }
718
719 /**
720 * Get the previous node.
721 * @return previous node
722 */
723 public final SpaceEffGraphNode getPrev() {
724 return prev;
725 }
726
727 /**
728 * Append a given node after this node.
729 * @param n the node to append
730 */
731 public final void append(SpaceEffGraphNode n) {
732 next = n;
733 n.prev = this;
734 }
735
736 /**
737 * Remove this node from the list.
738 * @return the next node in the list
739 */
740 public final SpaceEffGraphNode remove() {
741 // copy old links
742 SpaceEffGraphNode Prev = prev, Next = next;
743
744 // reset old links
745 prev = null;
746 next = null;
747
748 // compute new links
749 if (Prev != null) Prev.next = Next;
750 if (Next != null) Next.prev = Prev;
751
752 // return next node
753 return Next;
754 }
755 }
756
757