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.util.*;
024:
025: /**
026: * DecsendVisitor is the superclass of a few private classes of Type0Visitor and
027: * Type1Visitor. It descends the tree, keeping track of the number of right
028: * links that have been taken.
029: */
030: public abstract class DescendVisitor extends TreeVisitor {
031:
032: Hashtable useInfoMap;
033:
034: Hashtable defInfoMap;
035:
036: boolean found;
037:
038: Node beginNode; // where this visitor starts its search from
039:
040: LocalExpr start; // where the original search began
041:
042: int exchangeFactor;
043:
044: public DescendVisitor(final Hashtable useInfoMap,
045: final Hashtable defInfoMap) {
046: this .useInfoMap = useInfoMap;
047: this .defInfoMap = defInfoMap;
048: }
049:
050: public boolean search(final Node beginNode, final LocalExpr start) {
051: this .beginNode = beginNode;
052: this .start = start;
053: exchangeFactor = 0;
054: found = false;
055:
056: beginNode.visit(this );
057:
058: return found;
059: }
060:
061: public void visitExprStmt(final ExprStmt stmt) {
062: stmt.expr().visit(this );
063: }
064:
065: public void visitIfStmt(final IfStmt stmt) {
066:
067: if (stmt instanceof IfCmpStmt) {
068: visitIfCmpStmt((IfCmpStmt) stmt);
069: } else if (stmt instanceof IfZeroStmt) {
070: visitIfZeroStmt((IfZeroStmt) stmt);
071: }
072: }
073:
074: public void visitIfCmpStmt(final IfCmpStmt stmt) {
075: stmt.left().visit(this ); // search the left branch
076: if (!found) { // if nothing has been found
077: exchangeFactor++; // increase the exchange factor,
078: if (stmt.left().type().isWide()) {
079: exchangeFactor++; // twice to get
080: }
081: // around wides
082: if (exchangeFactor < 3) {
083: stmt.right().visit(this ); // search the right branch.
084: }
085: }
086:
087: }
088:
089: public void visitIfZeroStmt(final IfZeroStmt stmt) {
090:
091: stmt.expr().visit(this );
092:
093: }
094:
095: public void visitInitStmt(final InitStmt stmt) {
096:
097: // would have been checked by the Type0Visitor
098:
099: }
100:
101: public void visitGotoStmt(final GotoStmt stmt) {
102:
103: }
104:
105: public void visitLabelStmt(final LabelStmt stmt) {
106:
107: }
108:
109: public void visitMonitorStmt(final MonitorStmt stmt) {
110:
111: }
112:
113: public void visitPhiStmt(final PhiStmt stmt) {
114: if (stmt instanceof PhiCatchStmt) {
115: visitPhiCatchStmt((PhiCatchStmt) stmt);
116: } else if (stmt instanceof PhiJoinStmt) {
117: visitPhiJoinStmt((PhiJoinStmt) stmt);
118: /*
119: * else if (stmt instanceof PhiReturnStmt)
120: * visitPhiReturnStmt((PhiReturnStmt) stmt);
121: */
122: }
123: }
124:
125: public void visitCatchExpr(final CatchExpr expr) {
126:
127: }
128:
129: public void visitDefExpr(final DefExpr expr) {
130: if (expr instanceof MemExpr) {
131: visitMemExpr((MemExpr) expr);
132: }
133:
134: }
135:
136: public void visitStackManipStmt(final StackManipStmt stmt) {
137:
138: }
139:
140: public void visitPhiCatchStmt(final PhiCatchStmt stmt) {
141:
142: }
143:
144: public void visitPhiJoinStmt(final PhiJoinStmt stmt) {
145:
146: }
147:
148: public void visitRetStmt(final RetStmt stmt) {
149:
150: }
151:
152: public void visitReturnExprStmt(final ReturnExprStmt stmt) {
153:
154: }
155:
156: public void visitReturnStmt(final ReturnStmt stmt) {
157:
158: }
159:
160: public void visitAddressStoreStmt(final AddressStoreStmt stmt) {
161:
162: }
163:
164: // StoreExprs are very difficult because they represent several
165: // types of expressions. What we do will depend on what the target
166: // of the store is: ArrayRefExpr, FieldExpr, StaticFieldExpr,
167: // or LocalExpr
168:
169: public void visitStoreExpr(final StoreExpr expr) {
170: final MemExpr target = expr.target();
171:
172: if (target instanceof ArrayRefExpr) {
173: // ArrayRefExpr: the store will be something like an astore
174: // which manipulates the stack like
175: // arrayref, index, val => ...
176: // so, think of the tree like
177: // (StoreExpr)
178: // / \
179: // Array Ref .
180: // / \
181: // index value
182: // This is unlike the structure of the tree BLOAT uses for
183: // intermediate representation, but it better relates to what's
184: // on the stack at what time
185:
186: ((ArrayRefExpr) target).array().visit(this ); // visit the
187: // left child
188: if (!found) { // if match wasn't found
189: exchangeFactor++; // take the right branch
190: if (exchangeFactor < 3) { // (an array ref isn't wide)
191: // visit next left child
192: ((ArrayRefExpr) target).index().visit(this );
193: if (!found) { // if match wasn't found
194: exchangeFactor++;
195: if (exchangeFactor < 3) {
196: expr.expr().visit(this ); // search the right
197: // branch
198: }
199: } // end seaching RR
200: }
201: } // end searching R
202: } // end case where target is ArrayRefExpr
203:
204: else if (target instanceof FieldExpr) {
205: // FieldExpr: the store will be like a putfield
206: // which manipulates the stack like
207: // objref, val => ...
208: // so, think of the tree like
209: // (StoreExpr)
210: // / \
211: // Object Ref value
212:
213: ((FieldExpr) target).object().visit(this ); // visit the left child
214:
215: if (!found) {
216: exchangeFactor++; // (an object ref isn't wide)
217: if (exchangeFactor < 3) {
218: expr.expr().visit(this );
219: }
220: }
221: } // end case where target is FieldRef
222:
223: else if (target instanceof StaticFieldExpr) {
224: // StaticFieldExpr: the store will be like a putstatic
225: // which manipulates the stack like
226: // val => ...
227: // so, think of the tree like
228: // (StoreExpr)
229: // /
230: // value
231:
232: expr.expr.visit(this );
233: }
234:
235: else if (target instanceof LocalExpr) {
236: // LocalExpr: the store will be like istore/astore/etc.
237: // which manipulates the stack like
238: // val => ...
239: // so, think of the tree like
240: // (StoreExpr)
241: // /
242: // value
243:
244: expr.expr.visit(this );
245: }
246: }
247:
248: public void visitJsrStmt(final JsrStmt stmt) {
249:
250: }
251:
252: public void visitSwitchStmt(final SwitchStmt stmt) {
253:
254: }
255:
256: public void visitThrowStmt(final ThrowStmt stmt) {
257:
258: }
259:
260: public void visitStmt(final Stmt stmt) {
261:
262: }
263:
264: public void visitSCStmt(final SCStmt stmt) {
265:
266: }
267:
268: public void visitSRStmt(final SRStmt stmt) {
269:
270: }
271:
272: public void visitArithExpr(final ArithExpr expr) { // important one
273: expr.left().visit(this ); // visit the left branch
274:
275: if (!found) { // if a match isn't found yet
276: exchangeFactor++; // increase the exchange factor
277: if (expr.left().type().isWide()) {
278: exchangeFactor++; // twice if wide
279: }
280: if (exchangeFactor < 3) {
281: expr.right().visit(this ); // visit right branch
282: }
283: }
284: }
285:
286: public void visitArrayLengthExpr(final ArrayLengthExpr expr) {
287: expr.array().visit(this );
288: }
289:
290: public void visitMemExpr(final MemExpr expr) {
291: if (expr instanceof LocalExpr) {
292: visitLocalExpr((LocalExpr) expr);
293: }
294: }
295:
296: public void visitMemRefExpr(final MemRefExpr expr) {
297:
298: }
299:
300: public void visitArrayRefExpr(final ArrayRefExpr expr) {
301:
302: }
303:
304: public void visitCallExpr(final CallExpr expr) {
305: if (expr instanceof CallMethodExpr) {
306: visitCallMethodExpr((CallMethodExpr) expr);
307: } else if (expr instanceof CallStaticExpr) {
308: visitCallStaticExpr((CallStaticExpr) expr);
309: }
310: }
311:
312: public void visitCallMethodExpr(final CallMethodExpr expr) {
313: // Method invocations are to be thought of, in terms of
314: // binary expression trees, as
315: // (CallMethodExpr)
316: // / \
317: // receiver .
318: // / \
319: // arg1 .
320: // / \
321: // arg2 .
322: // / \
323: // arg3 ...
324: // This might be the opposite of what one would think in terms
325: // of currying (ie, one might think of currying in terms of
326: // left associativity), but this gives a better picture of what
327: // happens to the stack when invokestatic or invokevirtual is called:
328: // objectref, [arg1, [arg2 ...]] => ...
329:
330: expr.receiver().visit(this );
331: final Expr[] params = expr.params();
332: if (!found && (exchangeFactor < 2) && (params.length > 0)) {
333: exchangeFactor++; // (reciever won't be wide)
334: params[0].visit(this );
335: }
336:
337: }
338:
339: public void visitCallStaticExpr(final CallStaticExpr expr) {
340:
341: final Expr[] params = expr.params();
342: if (params.length > 0) {
343: params[0].visit(this );
344: }
345: if (!found && (exchangeFactor < 2) && (params.length > 1)) {
346: exchangeFactor++;
347: params[1].visit(this );
348: }
349: }
350:
351: public void visitCastExpr(final CastExpr expr) {
352: expr.expr().visit(this );
353: }
354:
355: public void visitConstantExpr(final ConstantExpr expr) {
356:
357: }
358:
359: public void visitFieldExpr(final FieldExpr expr) {
360: expr.object.visit(this );
361: }
362:
363: public void visitInstanceOfExpr(final InstanceOfExpr expr) {
364: expr.expr().visit(this );
365: }
366:
367: /* needs to be different for Type0 and Type1 */
368: public abstract void visitLocalExpr(LocalExpr expr);
369:
370: public void visitNegExpr(final NegExpr expr) {
371: expr.expr().visit(this );
372: }
373:
374: public void visitNewArrayExpr(final NewArrayExpr expr) {
375: expr.size().visit(this );
376: }
377:
378: public void visitNewExpr(final NewExpr expr) {
379:
380: }
381:
382: public void visitNewMultiArrayExpr(final NewMultiArrayExpr expr) {
383: // Think of the tree like
384: // (NewMultiArrayExpr)
385: // / \
386: // count1 .
387: // / \
388: // count2 etc.
389: // since multianewarray manipulates the stack like
390: // count1, [count1 ...] => ...
391:
392: final Expr[] dims = expr.dimensions();
393: if (dims.length > 0) {
394: dims[0].visit(this );
395: }
396: if (!found && (exchangeFactor < 2) && (dims.length > 1)) {
397: exchangeFactor++; // (count1 won't be wide)
398: dims[1].visit(this );
399: }
400: }
401:
402: public void visitCheckExpr(final CheckExpr expr) {
403: if (expr instanceof ZeroCheckExpr) {
404: visitZeroCheckExpr((ZeroCheckExpr) expr);
405: } else if (expr instanceof RCExpr) {
406: visitRCExpr((RCExpr) expr);
407: } else if (expr instanceof UCExpr) {
408: visitUCExpr((UCExpr) expr);
409: }
410: }
411:
412: public void visitZeroCheckExpr(final ZeroCheckExpr expr) {
413: // perhaps add something here
414: }
415:
416: public void visitRCExpr(final RCExpr expr) {
417:
418: }
419:
420: public void visitUCExpr(final UCExpr expr) {
421:
422: }
423:
424: public void visitReturnAddressExpr(final ReturnAddressExpr expr) {
425:
426: }
427:
428: public void visitShiftExpr(final ShiftExpr expr) {
429:
430: }
431:
432: public void visitVarExpr(final VarExpr expr) {
433: if (expr instanceof LocalExpr) {
434: visitLocalExpr((LocalExpr) expr);
435: }
436: }
437:
438: public void visitStaticFieldExpr(final StaticFieldExpr expr) {
439:
440: }
441:
442: public void visitExpr(final Expr expr) {
443:
444: }
445:
446: }
|