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