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.tree;
022:
023: import java.io.*;
024:
025: import EDU.purdue.cs.bloat.cfg.*;
026: import EDU.purdue.cs.bloat.util.*;
027:
028: /**
029: * Node represents a node in an expression tree. Each Node has a value number
030: * and a key associated with it. The value number is used to eliminate
031: * statements and expressions that have the same value (PRE). Statements and
032: * expressions of the same value will be mapped to the same value number.
033: *
034: * @see Expr
035: * @see Stmt
036: * @see Tree
037: */
038: public abstract class Node {
039: protected Node parent; // This Node's parent in a Tree.
040:
041: int key; // integer used in some analyses. For instance, when
042:
043: // dead code elimination is performed, key is set to
044: // DEAD or LIVE.
045: int valueNumber; // Used in eliminating redundent statements
046:
047: /**
048: * Constructor.
049: */
050: public Node() {
051: // if (Tree.DEBUG) {
052: // // We can't print the Node because things aren't initialized yet
053: // System.out.println(" new node " +
054: // System.identityHashCode(this));
055: // }
056:
057: parent = null;
058: valueNumber = -1;
059: key = 0;
060: }
061:
062: /**
063: * Returns this Node's value number.
064: */
065: public int valueNumber() {
066: return valueNumber;
067: }
068:
069: /**
070: * Sets this Node's value number.
071: */
072: public void setValueNumber(final int valueNumber) {
073: // if (Tree.DEBUG) {
074: // System.out.println(" setVN[" + this + "] = " + valueNumber);
075: // }
076: this .valueNumber = valueNumber;
077: }
078:
079: /**
080: * A Node's key represents an integer value that can be used by an algorithm
081: * to mark this node. For instance, when dead code elimination is performed
082: * a Node is marked as DEAD or ALIVE.
083: */
084: public int key() {
085: return key;
086: }
087:
088: public void setKey(final int key) {
089: this .key = key;
090: }
091:
092: /**
093: * Visit the children of this node. Not all Nodes will have children to
094: * visit.
095: */
096: public abstract void visitForceChildren(TreeVisitor visitor);
097:
098: public abstract void visit(TreeVisitor visitor);
099:
100: public void visitChildren(final TreeVisitor visitor) {
101: if (!visitor.prune()) {
102: visitForceChildren(visitor);
103: }
104: }
105:
106: public void visitOnly(final TreeVisitor visitor) {
107: visitor.setPrune(true);
108: visit(visitor);
109: visitor.setPrune(false);
110: }
111:
112: /**
113: * Returns the basic block in which this Node resides.
114: */
115: public Block block() {
116: Node p = this ;
117:
118: while (p != null) {
119: if (p instanceof Tree) {
120: return ((Tree) p).block();
121: }
122:
123: p = p.parent;
124: }
125:
126: throw new RuntimeException(this + " is not in a block");
127: }
128:
129: /**
130: * Sets the parent Node of this Node.
131: */
132: public void setParent(final Node parent) {
133: // if (Tree.DEBUG) {
134: // System.out.println(" setting parent of " + this + " (" +
135: // System.identityHashCode(this) + ") to " + parent);
136: // }
137:
138: this .parent = parent;
139: }
140:
141: public boolean hasParent() {
142: return parent != null;
143: }
144:
145: public Node parent() {
146: // Note that we can't print this Node because of recursion. Sigh.
147: Assert.isTrue(parent != null, "Null parent for "
148: + this .getClass().toString() + " node "
149: + System.identityHashCode(this ));
150: return parent;
151: }
152:
153: /**
154: * Copies the contents of one Node into another.
155: *
156: * @param node
157: * A Node from which to copy.
158: *
159: * @return node containing the contents of this Node.
160: */
161: protected Node copyInto(final Node node) {
162: node.setValueNumber(valueNumber);
163: return node;
164: }
165:
166: /**
167: * Clean up this Node only. Does not effect its children nodes.
168: */
169: public abstract void cleanupOnly();
170:
171: /**
172: * Cleans up this node so that it is independent of the expression tree in
173: * which it resides. This is usually performed before a Node is moved from
174: * one part of an expression tree to another.
175: * <p>
176: * Traverse the Tree starting at this Node. Remove the parent of each node
177: * and perform any Node-specific cleanup (see cleanupOnly). Sets various
178: * pointers to null so that they eventually may be garbage collected.
179: */
180: public void cleanup() {
181: // if (Tree.DEBUG) {
182: // System.out.println(" CLEANING UP " + this + " " +
183: // System.identityHashCode(this));
184: // }
185:
186: visit(new TreeVisitor() {
187: public void visitNode(final Node node) {
188: node.setParent(null);
189: node.cleanupOnly();
190: node.visitChildren(this );
191: }
192: });
193: }
194:
195: /**
196: * Replaces this node with another and perform cleanup.
197: */
198: public void replaceWith(final Node node) {
199: replaceWith(node, true);
200: }
201:
202: /**
203: * Replaces this Node with node in its (this's) tree.
204: *
205: * @param node
206: * The Node with which to replace.
207: * @param cleanup
208: * Do we perform cleanup on the tree?
209: */
210: public void replaceWith(final Node node, final boolean cleanup) {
211: // Check a couple of things:
212: // 1. The node with which we are replace this does not have a parent.
213: // 2. This Node does have a parent.
214: Assert.isTrue(node.parent == null, node
215: + " already has a parent");
216: Assert.isTrue(parent != null, this + " has no parent");
217:
218: final Node oldParent = parent;
219:
220: if (this instanceof Stmt) {
221: Assert.isTrue(node instanceof Stmt, "Attempt to replace "
222: + this + " with " + node);
223: }
224:
225: if (this instanceof Expr) {
226: Assert.isTrue(node instanceof Expr, "Attempt to replace "
227: + this + " with " + node);
228:
229: final Expr expr1 = (Expr) this ;
230: final Expr expr2 = (Expr) node;
231:
232: // Make sure the expressions can be interchanged (i.e. their
233: // descriptors
234: // are compatible).
235: Assert.isTrue(expr1.type().simple().equals(
236: expr2.type().simple()),
237: "Type mismatch when replacing " + expr1 + " with "
238: + expr2 + ": " + expr1.type() + " != "
239: + expr2.type());
240: }
241:
242: // Iterate over this parent's tree and replace this with node.
243: parent.visit(new ReplaceVisitor(this , node));
244:
245: Assert.isTrue(node.parent == oldParent, node + " parent == "
246: + node.parent + " != " + oldParent);
247:
248: if (cleanup) {
249: cleanup();
250: }
251: }
252:
253: /**
254: * @return A textual representation of this Node.
255: */
256: public String toString() {
257: final StringWriter w = new StringWriter();
258:
259: visit(new PrintVisitor(w) {
260: protected void println(final Object s) {
261: print(s);
262: }
263:
264: protected void println() {
265: }
266: });
267:
268: w.flush();
269:
270: return w.toString();
271: }
272: }
|