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: /**
026: * <tt>DominanceFrontier</tt> is used to calculate the <i>dominance frontier</i>
027: * of each node in a control flow graph.
028: * <p>
029: * The <i>dominance frontier</i> of a node x is the set of all nodes w such
030: * that x dominates a predacessor of w, but does not strictly dominate w.
031: * Basically, nodes in the dominance frontier have one parent that <b>is</b>
032: * dominated by x and at least one parent that <b>is not</b> dominated by x.
033: * <p>
034: * <tt>DominanceFrontier</tt> can be used to calculate both the dominance
035: * (forward) and the postdominance (reverse) frontiers for a control flow graph.
036: *
037: * @see FlowGraph
038: */
039:
040: public class DominanceFrontier {
041: /**
042: * Calculates the dominance frontier for a cfg and notifies the blocks in it
043: * appropriately.
044: *
045: * @param graph
046: * The cfg to operate on
047: * @param reverse
048: * Do we calculate the postdominance frontier?
049: */
050: public static void buildFrontier(final FlowGraph graph,
051: boolean reverse) {
052: if (!reverse) {
053: DominanceFrontier.calcFrontier(graph.source(), graph,
054: reverse);
055: } else {
056: DominanceFrontier
057: .calcFrontier(graph.sink(), graph, reverse);
058: }
059: }
060:
061: /**
062: * Recursively traverses the cfg and builds up the dominance frontier.
063: * <p>
064: * A block n's dominance frontier is the union of two sets of nodes. The
065: * first set is the nodes in the dominance frontier of the nodes that n
066: * dominates that are not dominated by n's immediate dominator. The second
067: * set consists of the successors of n that are not strictly dominated by n.
068: *
069: * @param block
070: * The block to start from (either source or sink)
071: * @param graph
072: * The cfg from which to get blocks
073: * @param reverse
074: * Do we calculate the dominance or postdominance frontier?
075: *
076: * @return The blocks in the (post)dominance frontier of block
077: */
078: private static LinkedList calcFrontier(final Block block,
079: final FlowGraph graph, boolean reverse) {
080: // local is an array of Blocks that are in block's dominance
081: // frontier. It is indexed by the block's pre-order index. I
082: // suppose an array is used so that no block is added to the
083: // dominance frontier twice.
084: final Block[] local = new Block[graph.size()];
085:
086: Iterator children; // The blocks that are dominated by block
087:
088: if (!reverse) {
089: children = block.domChildren().iterator();
090: } else {
091: children = block.pdomChildren().iterator();
092: }
093:
094: // Recursively calculate the nodes in the dominance frontier of
095: // block that are not dominated by block's immediate dominator
096: while (children.hasNext()) {
097: final Block child = (Block) children.next();
098:
099: final LinkedList df = DominanceFrontier.calcFrontier(child,
100: graph, reverse);
101:
102: final Iterator e = df.iterator();
103:
104: while (e.hasNext()) {
105: final Block dfChild = (Block) e.next();
106:
107: if (!reverse) {
108: if (block != dfChild.domParent()) {
109: local[graph.preOrderIndex(dfChild)] = dfChild;
110: }
111:
112: } else {
113: if (block != dfChild.pdomParent()) {
114: local[graph.preOrderIndex(dfChild)] = dfChild;
115: }
116: }
117: }
118: }
119:
120: final Iterator succs = reverse ? graph.preds(block).iterator()
121: : graph.succs(block).iterator();
122:
123: // Caculate the successors of block that are not strictly
124: // dominated by block.
125: while (succs.hasNext()) {
126: final Block succ = (Block) succs.next();
127:
128: // If block is not the immediate (post)dominator of its
129: // successor, add it to block's dominance frontier.
130: if (!reverse) {
131: if (block != succ.domParent()) {
132: local[graph.preOrderIndex(succ)] = succ;
133: }
134:
135: } else {
136: if (block != succ.pdomParent()) {
137: local[graph.preOrderIndex(succ)] = succ;
138: }
139: }
140: }
141:
142: final LinkedList v = new LinkedList(); // The dominance frontier
143:
144: for (int i = 0; i < local.length; i++) {
145: if (local[i] != null) {
146: v.add(local[i]);
147: }
148: }
149:
150: // Set block's (post)dominance frontier
151: if (!reverse) {
152: block.domFrontier().clear();
153: block.domFrontier().addAll(v);
154: } else {
155: block.pdomFrontier().clear();
156: block.pdomFrontier().addAll(v);
157: }
158:
159: return v;
160: }
161: }
|