001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.cfg;
022:
023: import java.util.*;
024:
025: import EDU.purdue.cs.bloat.util.*;
026:
027: /**
028: * DominatorTree finds the dominator tree of a FlowGraph.
029: * <p>
030: * The algorithm used is Purdum-Moore. It isn't as fast as Lengauer-Tarjan, but
031: * it's a lot simpler.
032: *
033: * @see FlowGraph
034: * @see Block
035: */
036: public class DominatorTree {
037: public static boolean DEBUG = false;
038:
039: /**
040: * Calculates what vertices dominate other verices and notify the basic
041: * Blocks as to who their dominator is.
042: *
043: * @param graph
044: * The cfg that is used to find the dominator tree.
045: * @param reverse
046: * Do we go in revsers? That is, are we computing the dominatance
047: * (false) or postdominance (true) tree.
048: * @see Block
049: */
050: public static void buildTree(final FlowGraph graph, boolean reverse) {
051: final int size = graph.size(); // The number of vertices in the cfg
052:
053: final Map snkPreds = new HashMap(); // The predacessor vertices from the
054: // sink
055:
056: // Determine the predacessors of the cfg's sink node
057: DominatorTree.insertEdgesToSink(graph, snkPreds, reverse);
058:
059: // Get the index of the root
060: final int root = reverse ? graph.preOrderIndex(graph.sink())
061: : graph.preOrderIndex(graph.source());
062:
063: Assert.isTrue((0 <= root) && (root < size));
064:
065: // Bit matrix indicating the dominators of each vertex.
066: // If bit j of dom[i] is set, then node j dominates node i.
067: final BitSet[] dom = new BitSet[size];
068:
069: // A bit vector of all 1's
070: final BitSet ALL = new BitSet(size);
071:
072: for (int i = 0; i < size; i++) {
073: ALL.set(i);
074: }
075:
076: // Initially, all the bits in the dominance matrix are set, except
077: // for the root node. The root node is initialized to have itself
078: // as an immediate dominator.
079: //
080: for (int i = 0; i < size; i++) {
081: final BitSet blockDoms = new BitSet(size);
082: dom[i] = blockDoms;
083:
084: if (i != root) {
085: blockDoms.or(ALL);
086: } else {
087: blockDoms.set(root);
088: }
089: }
090:
091: // Did the dominator bit vector array change?
092: boolean changed = true;
093:
094: while (changed) {
095: changed = false;
096:
097: // Get the basic blocks contained in the cfg
098: final Iterator blocks = reverse ? graph.postOrder()
099: .iterator() : graph.preOrder().iterator();
100:
101: // Compute the dominators of each node in the cfg. We iterate
102: // over every node in the cfg. The dominators of a node, x, are
103: // found by taking the intersection of the dominator bit vectors
104: // of each predacessor of x and unioning that with x. This
105: // process is repeated until no changes are made to any dominator
106: // bit vector.
107:
108: while (blocks.hasNext()) {
109: final Block block = (Block) blocks.next();
110:
111: final int i = graph.preOrderIndex(block);
112:
113: Assert.isTrue((0 <= i) && (i < size),
114: "Unreachable block " + block);
115:
116: // We already know the dominators of the root, keep looking
117: if (i == root) {
118: continue;
119: }
120:
121: final BitSet oldSet = dom[i];
122: final BitSet blockDoms = new BitSet(size);
123: blockDoms.or(oldSet);
124:
125: // print(graph, reverse, "old set", i, blockDoms);
126:
127: // blockDoms := intersection of dom(pred) for all pred(block).
128: Collection preds = reverse ? graph.succs(block) : graph
129: .preds(block);
130:
131: Iterator e = preds.iterator();
132:
133: // Find the intersection of the dominators of block's
134: // predacessors.
135: while (e.hasNext()) {
136: final Block pred = (Block) e.next();
137:
138: final int j = graph.preOrderIndex(pred);
139: Assert.isTrue(j >= 0, "Unreachable block " + pred);
140:
141: blockDoms.and(dom[j]);
142: }
143:
144: // Don't forget to account for the sink node if block is a
145: // leaf node. Appearantly, there are not edges between
146: // leaf nodes and the sink node!
147: preds = (Collection) snkPreds.get(block);
148:
149: if (preds != null) {
150: e = preds.iterator();
151:
152: while (e.hasNext()) {
153: final Block pred = (Block) e.next();
154:
155: final int j = graph.preOrderIndex(pred);
156: Assert.isTrue(j >= 0, "Unreachable block "
157: + pred);
158:
159: blockDoms.and(dom[j]);
160: }
161: }
162:
163: // Include yourself in your dominators?!
164: blockDoms.set(i);
165:
166: // print(graph, reverse, "intersecting " + preds, i, blockDoms);
167:
168: // If the set changed, set the changed bit.
169: if (!blockDoms.equals(oldSet)) {
170: changed = true;
171: dom[i] = blockDoms;
172: }
173: }
174: }
175:
176: // Once we have the predacessor bit vectors all squared away, we can
177: // determine which vertices dominate which vertices.
178:
179: Iterator blocks = graph.nodes().iterator();
180:
181: // Initialize each block's (post)dominator parent and children
182: while (blocks.hasNext()) {
183: final Block block = (Block) blocks.next();
184: if (!reverse) {
185: block.setDomParent(null);
186: block.domChildren().clear();
187: } else {
188: block.setPdomParent(null);
189: block.pdomChildren().clear();
190: }
191: }
192:
193: blocks = graph.nodes().iterator();
194:
195: // A block's immediate dominator is its closest dominator. So, we
196: // start with the dominators, dom(b), of a block, b. To find the
197: // imediate dominator of b, we remove all blocks from dom(b) that
198: // dominate any block in dom(b).
199:
200: while (blocks.hasNext()) {
201: final Block block = (Block) blocks.next();
202:
203: final int i = graph.preOrderIndex(block);
204:
205: Assert.isTrue((0 <= i) && (i < size), "Unreachable block "
206: + block);
207:
208: if (i == root) {
209: if (!reverse) {
210: block.setDomParent(null);
211: } else {
212: block.setPdomParent(null);
213: }
214:
215: } else {
216: // Find the immediate dominator
217: // idom := dom(block) - dom(dom(block)) - block
218: final BitSet blockDoms = dom[i];
219:
220: // print(graph, reverse, "dom set", i, blockDoms);
221:
222: final BitSet idom = new BitSet(size);
223: idom.or(blockDoms);
224: idom.clear(i);
225:
226: for (int j = 0; j < size; j++) {
227: if ((i != j) && blockDoms.get(j)) {
228: final BitSet domDomBlocks = dom[j];
229:
230: // idom = idom - (domDomBlocks - {j})
231: final BitSet b = new BitSet(size);
232: b.or(domDomBlocks);
233: b.xor(ALL);
234: b.set(j);
235: idom.and(b);
236:
237: // print(graph, reverse,
238: // "removing dom(" + graph.preOrder().get(j) +")",
239: // i, idom);
240: }
241: }
242:
243: Block parent = null;
244:
245: // A block should only have one immediate dominator.
246: for (int j = 0; j < size; j++) {
247: if (idom.get(j)) {
248: final Block p = (Block) graph.preOrder().get(j);
249:
250: Assert
251: .isTrue(
252: parent == null,
253: block
254: + " has more than one immediate dominator: "
255: + parent + " and " + p);
256:
257: parent = p;
258: }
259: }
260:
261: Assert.isTrue(parent != null, block
262: + " has 0 immediate "
263: + (reverse ? "postdominators" : "dominators"));
264:
265: if (!reverse) {
266: if (DominatorTree.DEBUG) {
267: System.out.println(parent + " dominates "
268: + block);
269: }
270:
271: block.setDomParent(parent);
272:
273: } else {
274: if (DominatorTree.DEBUG) {
275: System.out.println(parent + " postdominates "
276: + block);
277: }
278:
279: block.setPdomParent(parent);
280: }
281: }
282: }
283: }
284:
285: /**
286: * Determines which nodes are predacessors of a cfg's sink node. Creates a
287: * Map that maps the sink node to its predacessors (or the leaf nodes to the
288: * sink node, their predacessor, if we're going backwards).
289: *
290: * @param graph
291: * The cfg to operate on.
292: * @param preds
293: * A mapping from leaf nodes to their predacessors. The exact
294: * semantics depend on whether or not we are going forwards.
295: * @param reverse
296: * Are we computing the dominators or postdominators?
297: */
298: private static void insertEdgesToSink(final FlowGraph graph,
299: final Map preds, final boolean reverse) {
300: final BitSet visited = new BitSet(); // see insertEdgesToSinkDFS
301: final BitSet returned = new BitSet();
302:
303: visited.set(graph.preOrderIndex(graph.source()));
304:
305: DominatorTree.insertEdgesToSinkDFS(graph, graph.source(),
306: visited, returned, preds, reverse);
307: }
308:
309: /**
310: * This method determines which nodes are the predacessor of the sink node
311: * of a cfg. A depth-first traversal of the cfg is performed. When a leaf
312: * node (that is not the sink node) is encountered, add an entry to the
313: * preds Map.
314: *
315: * @param graph
316: * The cfg being operated on.
317: * @param block
318: * The basic Block to start at.
319: * @param visited
320: * Vertices that were visited
321: * @param returned
322: * Vertices that returned
323: * @param preds
324: * Maps a node to a HashSet representing its predacessors. In the
325: * case that we're determining the dominace tree, preds maps the
326: * sink node to its predacessors. In the case that we're
327: * determining the postdominance tree, preds maps the sink node's
328: * predacessors to the sink node.
329: * @param reverse
330: * Do we go in reverse?
331: */
332: private static void insertEdgesToSinkDFS(final FlowGraph graph,
333: final Block block, final BitSet visited,
334: final BitSet returned, final Map preds, boolean reverse) {
335: boolean leaf = true; // Is a vertex a leaf node?
336:
337: // Get the successors of block
338: final Iterator e = graph.succs(block).iterator();
339:
340: while (e.hasNext()) {
341: final Block succ = (Block) e.next();
342:
343: // Determine index of succ vertex in a pre-order traversal
344: final int index = graph.preOrderIndex(succ);
345: Assert.isTrue(index >= 0, "Unreachable block " + succ);
346:
347: if (!visited.get(index)) {
348: // If the successor block hasn't been visited, visit it
349: visited.set(index);
350: DominatorTree.insertEdgesToSinkDFS(graph, succ,
351: visited, returned, preds, reverse);
352: returned.set(index);
353: leaf = false;
354:
355: } else if (returned.get(index)) {
356: // Already visited and returned, so a descendent of succ
357: // has an edge to the sink.
358: leaf = false;
359: }
360: }
361:
362: if (leaf && (block != graph.sink())) {
363: // If we're dealing with a leaf node that is not the sink, set
364: // up its predacessor set.
365:
366: if (!reverse) {
367: // If we're going forwards (computing dominators), get the
368: // predacessor vertices from the sink
369: Set p = (Set) preds.get(graph.sink());
370:
371: // If there are no (known) predacessors, make a new HashSet to
372: // store them and register it in the pred Map.
373: if (p == null) {
374: p = new HashSet();
375: preds.put(graph.sink(), p);
376: }
377:
378: // The block is in the predacessors of the sink
379: p.add(block);
380:
381: } else {
382: // If we're going backwards, get the block's predacessors
383: Set p = (Set) preds.get(block);
384:
385: if (p == null) {
386: p = new HashSet();
387: preds.put(block, p);
388: }
389:
390: // Add the sink vertex to the predacessors of the block
391: p.add(graph.sink());
392: }
393: }
394: }
395: }
|