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