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.editor.*;
026: import EDU.purdue.cs.bloat.tree.*;
027: import EDU.purdue.cs.bloat.util.*;
028:
029: /**
030: * <tt>Block</tt> represents a basic block of code used in control flow
031: * graphs. A basic block is always entered at its beginning and exits at its
032: * end. That is, its first statement is a label and its last statement is a
033: * jump. There are no other labels or jumps in between.
034: * <p>
035: * Each <tt>Block</tt> knows its parent block and its children in the
036: * dominator and postdominator trees. It also knows which blocks are in its
037: * dominance frontier and its postdominance frontier.
038: *
039: * @see FlowGraph
040: * @see DominatorTree
041: * @see DominanceFrontier
042: */
043: public class Block extends GraphNode {
044: // There are several "types" of Blocks. A NON_HEADER block is not the
045: // header of a loop. An IRREDUCIBLE block is one of the headers of an
046: // irreducible loop. An irriducible loop has more than one entry
047: // point. They are very rare and are really ugly. The loop
048: // transformer tries to fix up mutiple headers. A REDUCIBLE header is
049: // a header for a reducible loop.
050: public static final int NON_HEADER = 0;
051:
052: public static final int IRREDUCIBLE = 1;
053:
054: public static final int REDUCIBLE = 2;
055:
056: FlowGraph graph; // CFG to which this Block belongs
057:
058: Label label; // This Block's Label
059:
060: Tree tree; // Expression tree for this block
061:
062: Block domParent; // Block that (immediately) dominates this Block
063:
064: Block pdomParent;
065:
066: Set domChildren; // Blocks that this Block dominates
067:
068: Set pdomChildren; // The postdominator children of this block
069:
070: Set domFrontier; // This Block's dominance frontier
071:
072: Set pdomFrontier; // This Block's postdominace frontier
073:
074: int blockType; // NON_HEADER, IRREDUCIBLE, or REDUCIBLE
075:
076: Block header; // The block's loop header
077:
078: StackOptimizer stackOptimizer; // Stack Optimizer
079:
080: /**
081: * Constructor.
082: *
083: * @param label
084: * The block's label. The label may be thought of as the line of
085: * code at which the block begins.
086: * @param graph
087: * The CFG containing the block.
088: */
089: Block(final Label label, final FlowGraph graph) {
090: this .label = label;
091: this .graph = graph;
092: this .tree = null;
093: this .header = null;
094: this .blockType = Block.NON_HEADER;
095:
096: label.setStartsBlock(true);
097:
098: domParent = null;
099: pdomParent = null;
100:
101: domChildren = new HashSet();
102: pdomChildren = new HashSet();
103:
104: domFrontier = new HashSet();
105: pdomFrontier = new HashSet();
106:
107: stackOptimizer = new StackOptimizer(this ); // make StackOptimizer
108: // object
109:
110: }
111:
112: /**
113: * Returns the stack optimizer for this block.
114: *
115: * @return The stack optimizer.
116: */
117: public StackOptimizer stackOptimizer() {
118: return stackOptimizer;
119: }
120:
121: /**
122: * Returns the expression tree for this block.
123: *
124: * @return The tree.
125: */
126: public Tree tree() {
127: return tree;
128: }
129:
130: /**
131: * Sets the expression tree for this block.
132: */
133: public void setTree(final Tree tree) {
134: this .tree = tree;
135: }
136:
137: /**
138: * Returns the CFG containing the block.
139: *
140: * @return The CFG.
141: */
142: public FlowGraph graph() {
143: return graph;
144: }
145:
146: /**
147: * Returns the label associated with this block.
148: */
149: public Label label() {
150: return label;
151: }
152:
153: /**
154: * Visits the expression tree contained in this block.
155: */
156: public void visitChildren(final TreeVisitor visitor) {
157: if (tree != null) {
158: tree.visit(visitor);
159: }
160: }
161:
162: public void visit(final TreeVisitor visitor) {
163: visitor.visitBlock(this );
164: }
165:
166: /**
167: * Sets the type of this Block. A Block may have one of three types:
168: *
169: * <ul>
170: * <li><tt>NON_HEADER</tt>: Not the header of any loop
171: * <li><tt>IRREDUCIBLE</tt>: Header of an irreducible loop
172: * <li><tt>REDUCIBLE</tt>: Header of a reducible loop
173: * </ul>
174: *
175: * A <i>loop</i> is a strongly connected component of a control flow graph.
176: * A loop's <i>header</i> is the block that dominates all other blocks in
177: * the loop. A loop is <i>reducible</i> if the only way to enter the loop
178: * is through the header.
179: */
180: void setBlockType(final int blockType) {
181: this .blockType = blockType;
182:
183: if (FlowGraph.DEBUG) {
184: System.out.println(" Set block type " + this );
185: }
186: }
187:
188: /**
189: * Returns the type of this Block.
190: */
191: int blockType() {
192: return blockType;
193: }
194:
195: public void setHeader(final Block header) {
196: this .header = header;
197:
198: if (FlowGraph.DEBUG) {
199: System.out.println(" Set header " + this );
200: }
201: }
202:
203: public Block header() {
204: return header;
205: }
206:
207: /**
208: * Returns a string representation of this block.
209: */
210: public String toString() {
211: String s = "<block " + label + " hdr=";
212:
213: if (header != null) {
214: s += header.label();
215: } else {
216: s += "null";
217: }
218:
219: switch (blockType) {
220: case NON_HEADER:
221: break;
222: case IRREDUCIBLE:
223: s += " irred";
224: break;
225: case REDUCIBLE:
226: s += " red";
227: break;
228: }
229:
230: if (this == graph.source()) {
231: return s + " source>";
232: } else if (this == graph.init()) {
233: return s + " init>";
234: } else if (this == graph.sink()) {
235: return s + " sink>";
236: } else {
237: return s + ">";
238: }
239: }
240:
241: /**
242: * Returns the basic blocks that this Block immediately dominates. That is,
243: * it returns this Block's children in the dominator tree for the CFG.
244: */
245: Collection domChildren() {
246: return domChildren;
247: }
248:
249: /**
250: * Returns the immediate dominator of this Block. That is, it returns the
251: * Block's parent in the dominator tree, its immediate dominator.
252: */
253: Block domParent() {
254: return domParent;
255: }
256:
257: /**
258: * Specifies that Block dominates this Block (parent in the dominator tree,
259: * the immediate dominator).
260: *
261: * @param block
262: * Block that dominates this Block.
263: */
264: void setDomParent(final Block block) {
265: // If this Block already had a dominator specified, remove
266: // it from its dominator's children.
267: if (domParent != null) {
268: domParent.domChildren.remove(this );
269: }
270:
271: domParent = block;
272:
273: // Add this Block to its new dominator's children.
274: if (domParent != null) {
275: domParent.domChildren.add(this );
276: }
277: }
278:
279: /**
280: * Returns whether or this Block dominates another given Block. A node X
281: * dominates a node Y when every path from the first node in the CFG (Enter)
282: * to Y must pass through X.
283: */
284: public boolean dominates(final Block block) {
285: Block p = block;
286:
287: while (p != null) {
288: if (p == this ) {
289: return true;
290: }
291: p = p.domParent();
292: }
293:
294: return false;
295: }
296:
297: /**
298: * Returns the children of this Block in the CFG's postdominator tree.
299: */
300: Collection pdomChildren() {
301: return pdomChildren;
302: }
303:
304: /**
305: * Returns the parent of this Block in the CFG's postdominator tree.
306: */
307: Block pdomParent() {
308: return pdomParent;
309: }
310:
311: /**
312: * Sets this Block's parent in the postdominator tree.
313: */
314: void setPdomParent(final Block block) {
315: if (pdomParent != null) {
316: pdomParent.pdomChildren.remove(this );
317: }
318:
319: pdomParent = block;
320:
321: if (pdomParent != null) {
322: pdomParent.pdomChildren.add(this );
323: }
324: }
325:
326: /**
327: * Determines whether or not this block postdominates a given block. A block
328: * X is said to postdominate a block Y when every path from Y to the last
329: * node in the CFG (Exit) passes through X. This relationship can be thought
330: * of as the reverse of dominance. That is, X dominates Y in the reverse
331: * CFG.
332: *
333: * @see DominatorTree
334: */
335: public boolean postdominates(final Block block) {
336: Block p = block;
337:
338: while (p != null) {
339: if (p == this ) {
340: return true;
341: }
342: p = p.pdomParent();
343: }
344:
345: return false;
346: }
347:
348: /**
349: * Returns the blocks that are in this block's dominance frontier. The
350: * dominance frontier of a node X in a CFG is the set of all nodes Y such
351: * that X dominates a predacessor of Y, but does not strictly dominate Y.
352: * Nodes in the dominance frontier always have more than one parent (a
353: * join).
354: *
355: * @see DominanceFrontier
356: */
357: Collection domFrontier() {
358: Assert.isTrue(domFrontier != null);
359: return domFrontier;
360: }
361:
362: /**
363: * Returns the postdominance frontier for this node. A postdominace frontier
364: * is essentially the same as a dominace frontier, but the postdominance
365: * relationship is used instead of the dominance relationship.
366: */
367: Collection pdomFrontier() {
368: Assert.isTrue(pdomFrontier != null);
369: return pdomFrontier;
370: }
371: }
|