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.trans;
022:
023: import java.util.*;
024:
025: import EDU.purdue.cs.bloat.cfg.*;
026: import EDU.purdue.cs.bloat.editor.*;
027: import EDU.purdue.cs.bloat.tree.*;
028: import EDU.purdue.cs.bloat.util.*;
029:
030: /**
031: * Attempts to remove residency checks an update checks from a control flow
032: * graph.
033: */
034: public class PersistentCheckElimination {
035: public static boolean DEBUG = false;
036:
037: private static final int RC = 0;
038:
039: private static final int AUPDATE = 1;
040:
041: private static final int SUPDATE = 2;
042:
043: private static final int SIZE = 3; // Number of persistent opcodes
044:
045: private EditorContext context;
046:
047: /**
048: * Examines each residency check (<Tt>RCExpr</tt>) and update check (<tt>UCExpr</tt>)
049: * and determines whether or it is redundent. If a residency check checks
050: * something that we know is resident (i.e. the this pointer or the result
051: * of an object creation), then the check is redundent. Once an update check
052: * has been performed on a value, all subsequent checks are redundent.
053: * Redundent checks are removed from the control flow graph.
054: *
055: * @see RCExpr
056: * @see UCExpr
057: */
058: public void transform(final FlowGraph cfg) {
059: context = cfg.method().declaringClass().context();
060:
061: final BitSet[] seen = new BitSet[PersistentCheckElimination.SIZE];
062:
063: for (int i = 0; i < PersistentCheckElimination.SIZE; i++) {
064: seen[i] = new BitSet();
065: }
066:
067: search(cfg, cfg.source(), seen);
068: }
069:
070: /**
071: * Recursively searches the tree for residency statements that can be
072: * removed. The value numbers of expressions that create new objects are
073: * noted. The value number of the "this" pointer is also noted. If a
074: * residency check (RCExpr) is performed on any of these expressions, it is
075: * redundent and can be removed.
076: *
077: * <p>
078: *
079: * When an update check (UCExpr) is encountered each of its children is
080: * visited. The value numbers of expressions that are checked (i.e. wrapped
081: * in UCExpr) are noted. If an UCExpr is encountered that checks an
082: * expression with one of these value numbers, the check is redundent and
083: * can be removed.
084: *
085: * @param seen
086: * An array containing a BitSet for each type of
087: * residency-related instruction (RC, AUPDATE, SUPDATE). Each bit
088: * in the BitSet corresponds to an expression involving residency
089: * being visited. That is, its value number is "seen".
090: */
091: private void search(final FlowGraph cfg, final Block block,
092: final BitSet[] seen) {
093: // Accumulate the information stored in seen...
094: // Save a copy of the contens of seen
095: final BitSet[] save = new BitSet[PersistentCheckElimination.SIZE];
096:
097: for (int i = 0; i < PersistentCheckElimination.SIZE; i++) {
098: save[i] = new BitSet(seen[i].size());
099: save[i].or(seen[i]);
100: }
101:
102: // Visit each expression in the tree.
103: block.visit(new TreeVisitor() {
104: // When we reach an expression that creates a new object
105: // (NewArrayExpr, NewMultiArrayExpr, or NewExpr), set the bit in
106: // the RC bit vector corresponding to the expression's value
107: // number.
108: public void visitNewArrayExpr(final NewArrayExpr expr) {
109: expr.visitChildren(this );
110:
111: final int v = expr.valueNumber();
112: Assert.isTrue(v != -1);
113: seen[PersistentCheckElimination.RC].set(v);
114: }
115:
116: public void visitNewMultiArrayExpr(
117: final NewMultiArrayExpr expr) {
118: expr.visitChildren(this );
119:
120: final int v = expr.valueNumber();
121: Assert.isTrue(v != -1);
122: seen[PersistentCheckElimination.RC].set(v);
123: }
124:
125: public void visitNewExpr(final NewExpr expr) {
126: expr.visitChildren(this );
127:
128: final int v = expr.valueNumber();
129: Assert.isTrue(v != -1);
130: seen[PersistentCheckElimination.RC].set(v);
131: }
132:
133: // Find the value number of the LocalExpr corresponding to the
134: // "this" variable. Set the bit in the RC bit vector
135: // corresponding to the "this" pointer's value number.
136: public void visitInitStmt(final InitStmt stmt) {
137: stmt.visitChildren(this );
138:
139: final MethodEditor method = stmt.block().graph()
140: .method();
141:
142: if (!method.isStatic()) {
143: Assert.isTrue(stmt.targets().length > 0);
144: final int v = stmt.targets()[0].valueNumber();
145: Assert.isTrue(v != -1);
146: seen[PersistentCheckElimination.RC].set(v);
147: }
148: }
149:
150: // If the expression being checked by the RCExpr is either the
151: // result of a "new" expression or it is the "this" pointer, we
152: // know that it is resident and thus does not need to be
153: // checked. All occurrences of the RCExpr are replaced with the
154: // expression being checked. All of this is contingent on the
155: // fact that the check does not have an ALIAS side effect.
156: public void visitRCExpr(final RCExpr expr) {
157: expr.visitChildren(this );
158:
159: final int v = expr.expr().valueNumber();
160: Assert.isTrue(v != -1);
161:
162: final SideEffectChecker sideEffects = new SideEffectChecker(
163: context);
164: expr.expr().visit(sideEffects);
165: final int flag = sideEffects.sideEffects();
166:
167: if (seen[PersistentCheckElimination.RC].get(v)
168: && ((flag & SideEffectChecker.ALIAS) == 0)) {
169: // rc(x) --> x
170: expr.expr().setParent(null);
171: expr.replaceWith(expr.expr(), false);
172: expr.cleanupOnly();
173: }
174:
175: seen[PersistentCheckElimination.RC].set(v);
176: }
177:
178: // If an object has already been updated, it does not need to be
179: // updated again. Note that the children of the UCExpr are
180: // visited first. There is a seen bit vector for both AUPDATE
181: // and SUPDATE UCExpr. If the value number of the expression
182: // being checked has already been encountered in a UCExpr, then
183: // the UCExpr is redundent and can be replaced with the
184: // expression being checked provided that it has no ALIAS side
185: // effects.
186: public void visitUCExpr(final UCExpr expr) {
187: expr.visitChildren(this );
188:
189: final int v = expr.expr().valueNumber();
190: Assert.isTrue(v != -1);
191:
192: final SideEffectChecker sideEffects = new SideEffectChecker(
193: context);
194: expr.expr().visit(sideEffects);
195: final int flag = sideEffects.sideEffects();
196:
197: if (expr.kind() == UCExpr.POINTER) {
198: if (seen[PersistentCheckElimination.AUPDATE].get(v)
199: && ((flag & SideEffectChecker.ALIAS) == 0)) {
200: // aupdate(x) --> x
201: expr.expr().setParent(null);
202: expr.replaceWith(expr.expr(), false);
203: expr.cleanupOnly();
204: }
205:
206: seen[PersistentCheckElimination.AUPDATE].set(v);
207:
208: } else {
209: if (seen[PersistentCheckElimination.SUPDATE].get(v)
210: && ((flag & SideEffectChecker.ALIAS) == 0)) {
211: // supdate(x) --> x
212: expr.expr().setParent(null);
213: expr.replaceWith(expr.expr(), false);
214: expr.cleanupOnly();
215: }
216:
217: seen[PersistentCheckElimination.SUPDATE].set(v);
218: }
219: }
220: });
221:
222: // Visit the blocks in the dominator tree in pre-order
223: final Iterator children = cfg.domChildren(block).iterator();
224:
225: while (children.hasNext()) {
226: final Block child = (Block) children.next();
227: search(cfg, child, seen);
228: }
229:
230: for (int i = 0; i < PersistentCheckElimination.SIZE; i++) {
231: seen[i] = save[i];
232: }
233: }
234: }
|