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
018 /**
019 * An efficient topsort dataflow iterator to be used with
020 * SortedGraphNode. The graph represents entities (values,
021 * statements, block, etc) to analyze and the graph makes explicit the
022 * data-flow dependencies between them. Fixed-point iteration is
023 * expressed using a special iterator that takes a parameter denoting
024 * whether analysis of the current element changed the data-flow
025 * result. If not, the iterator continues thru other unanalyzed
026 * elements. If there is a change, then the data-flow successors of
027 * the current node become the new head of the order of remaining
028 * nodes.
029 * <p>
030 * A typical use is as follows:
031 * <pre>
032 * BasicBlock start = ir.cfg.entry();
033 * SortedGraphIterator bbIter = new SortedGraphIterator(start, true);
034 * // true means forward analysis; false means backward analysis
035 * for (BasicBlock currBlock = start; currBlock!= null;) {
036 *
037 * // do your analysis of the currBlock here
038 *
039 * boolean changed = ... // true if the solution of currBlock has been changed since
040 * // the last visit of currBlock.
041 * // false if not.
042 *
043 * currBlock = (BasicBlock) bbIter.markAndGetNextTopSort(changed);
044 * }
045 *</pre>
046 */
047 public class SortedGraphIterator {
048
049 /**
050 * The earliest place where we needed to move currentNode back in the list
051 * because its successor needed to be processed.
052 */
053 protected SortedGraphNode barrier;
054
055 /**
056 * A unique marker to use to mark nodes
057 */
058 protected int changeMark;
059
060 /**
061 * The current node we are processing
062 */
063 protected SortedGraphNode currentNode;
064
065 /**
066 * The direction we are moving on the graph
067 */
068 protected boolean forward;
069
070 /**
071 * Constructor
072 * @param current the node to start the iteration at
073 * @param forward the direction we are processing the graph
074 */
075 public SortedGraphIterator(SortedGraphNode current, boolean forward) {
076 currentNode = current;
077 barrier = current.getSortedNext(forward);
078 this.forward = forward;
079 changeMark = SortedGraphNode.getNewSortMarker(current);
080 currentNode.setSortMarker(Integer.MIN_VALUE);
081 }
082
083 /**
084 * General fixed-pointer iterator; call this repeatedly until there
085 * is no more work to do. There are specialized (more efficient)
086 * mechanisms provided by this class.
087 *
088 * @param changed Whether analysis of the current element changed
089 * any data-flow result.
090 *
091 * @return the next node to analyze
092 *
093 * @see #isSingleSuccessor
094 * @see #isSinglePredecessor
095 */
096 public SortedGraphNode markAndGetNextTopSort(boolean changed) {
097 if (changed) {
098 int currOrder = currentNode.getSortNumber(forward);
099 int newOrder = currOrder + 1; // currentNode can be a target to be re-executed
100 int barrierOrder;
101 if (barrier == null) {
102 barrierOrder = Integer.MAX_VALUE;
103 } else {
104 barrierOrder = barrier.getSortNumber(forward);
105 }
106 SortedGraphNode newNode = null;
107 Enumeration<? extends SortedGraphNode> e;
108 if (forward) {
109 e = currentNode.getOutNodes();
110 } else {
111 e = currentNode.getInNodes();
112 }
113
114 while (e.hasMoreElements()) {
115 // Select the node with the smallest sort number among the "successor" nodes
116 SortedGraphNode outNode = e.nextElement();
117 if (outNode.getSortNumber(forward) < barrierOrder) { // anything larger than barrier will be visited later
118 outNode.setSortMarker(changeMark);
119 if (outNode.getSortNumber(forward) < newOrder) { // have to go backward
120 newOrder = outNode.getSortNumber(forward);
121 newNode = outNode;
122 }
123 }
124 }
125 if (newOrder <= currOrder) {
126 currentNode = newNode;
127 // retreat
128 advanceBarrier();
129 return newNode;
130 }
131 }
132
133 // Either changed = false or no retreat
134 // Return the first one with changeMark before barrier or
135 // barrier itself.
136 currentNode = currentNode.getSortedNext(forward);
137 for (; currentNode != barrier; currentNode = currentNode.getSortedNext(forward)) {
138 if (currentNode.getSortMarker() == changeMark) {
139 advanceBarrier();
140 return currentNode;
141 }
142 }
143
144 // Nothing before the barrier
145 advanceBarrier();
146 return currentNode;
147 }
148
149 /**
150 * This method checks to see if the second parameter has a single
151 * predecessor, which is the first parameter.
152 * If this condition is true, data flow analyses can reuse their
153 * results from the previous iteration rather than perform a meet operation
154 * (See LiveAnalysis.java for an example.)
155 *
156 * @param currentNode the possibly unique predecessor
157 * @param nextNode the node of interest
158 * @return if first parameter is the only predecessor of the 2nd parameter
159 */
160 public boolean isSingleSuccessor(SortedGraphNode currentNode, SortedGraphNode nextNode) {
161 // check that next node has only 1 predecessor
162 if (!nextNode.hasOneIn()) return false;
163 // now check that the predecessor is current node
164 Enumeration<? extends SortedGraphNode> inEnum = nextNode.getInNodes();
165 return inEnum.nextElement() == currentNode;
166 }
167
168 /**
169 * This method checks to see if the second parameter has a single
170 * successor, which is the first parameter.
171 * If this condition is true, data flow analyses can reuse their
172 * results from the previous iteration rather than perform a meet operation
173 * (See LiveAnalysis.java for an example.)
174 *
175 * @param currentNode the possibly unique predecessor
176 * @param nextNode the node of interest
177 * @return if first parameter is the only successor of the 2nd parameter
178 */
179 public boolean isSinglePredecessor(SortedGraphNode currentNode, SortedGraphNode nextNode) {
180 // check that next node has only 1 successor
181 if (!nextNode.hasOneOut()) return false;
182 // now check that the successor is current node
183 Enumeration<? extends SortedGraphNode> outEnum = nextNode.getOutNodes();
184 return outEnum.nextElement() == currentNode;
185 }
186
187 /**
188 * This method keeps track of nodes in the graph that are known to
189 * not have been visited yet even once. Advance the barrier, if needed
190 */
191 private void advanceBarrier() {
192 if (currentNode != null) {
193 currentNode.setSortMarker(Integer.MIN_VALUE);
194 }
195 if ((currentNode == barrier) && (barrier != null)) {
196 barrier = barrier.getSortedNext(forward);
197 }
198 }
199 }
200