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.tree.*;
027: import EDU.purdue.cs.bloat.util.*;
028:
029: /**
030: * DeadCodeElimination performs SSA-based dead code elimination as described in
031: * [Cytron, et. al. 91]. The idea behind dead code elimination is that there are
032: * some instructions that do not contribute anything useful to the result of the
033: * program. Most dead code is introduced by other optimizations.
034: *
035: * A program statement is live if one or more of the following holds:
036: *
037: * <ol>
038: *
039: * <li>The statement effects program output. In Java this is a lot more than
040: * just I/O. We must be conservative and assume that exceptions and monitor
041: * expression are always live.
042: *
043: * <li>The statement is an assignment statement whose target is used in a live
044: * statement.
045: *
046: * <li>The statement is a conditional branch and there are live statements
047: * whose execution depend on the conditional branch.
048: *
049: * <ol>
050: *
051: * Basically, the algorithm proceeds by marking a number of statements as being
052: * pre-live and then uses a worklist to determine which statements must also be
053: * live by the above three conditions.
054: */
055: public class DeadCodeElimination {
056: public static boolean DEBUG = false;
057:
058: private static final int DEAD = 0;
059:
060: private static final int LIVE = 1;
061:
062: FlowGraph cfg;
063:
064: /**
065: * Constructor.
066: */
067: public DeadCodeElimination(final FlowGraph cfg) {
068: this .cfg = cfg;
069: }
070:
071: // Keep a work list of expressions that need to be made live.
072: LinkedList worklist;
073:
074: /**
075: * Performs dead code elimination.
076: */
077: public void transform() {
078: // Mark all nodes in the tree as DEAD.
079: cfg.visit(new TreeVisitor() {
080: public void visitNode(final Node node) {
081: node.visitChildren(this );
082: node.setKey(DeadCodeElimination.DEAD);
083: }
084: });
085:
086: worklist = new LinkedList();
087:
088: // Visit the nodes in the tree and mark nodes that we know must be
089: // LIVE.
090: cfg.visit(new TreeVisitor() {
091: public void visitMonitorStmt(final MonitorStmt stmt) {
092: // NullPointerException, IllegalMonitorStateException
093: if (DeadCodeElimination.DEBUG) {
094: System.out.println(stmt + " is prelive");
095: }
096:
097: makeLive(stmt);
098: }
099:
100: public void visitInitStmt(final InitStmt stmt) {
101: // Needed to correctly initialize the formal parameters when
102: // coloring
103: if (DeadCodeElimination.DEBUG) {
104: System.out.println(stmt + " is prelive");
105: }
106:
107: makeLive(stmt);
108: }
109:
110: public void visitJsrStmt(final JsrStmt stmt) {
111: // Branch
112: if (DeadCodeElimination.DEBUG) {
113: System.out.println(stmt + " is prelive");
114: }
115:
116: makeLive(stmt);
117: }
118:
119: public void visitAddressStoreStmt(
120: final AddressStoreStmt stmt) {
121: // Branch
122: if (DeadCodeElimination.DEBUG) {
123: System.out.println(stmt + " is prelive");
124: }
125:
126: makeLive(stmt);
127: }
128:
129: public void visitRetStmt(final RetStmt stmt) {
130: // Branch
131: if (DeadCodeElimination.DEBUG) {
132: System.out.println(stmt + " is prelive");
133: }
134:
135: makeLive(stmt);
136: }
137:
138: public void visitSRStmt(final SRStmt stmt) {
139: if (DeadCodeElimination.DEBUG) {
140: System.out.println(stmt + " is prelive");
141: }
142:
143: makeLive(stmt);
144: }
145:
146: public void visitSCStmt(final SCStmt stmt) {
147: if (DeadCodeElimination.DEBUG) {
148: System.out.println(stmt + " is prelive");
149: }
150:
151: makeLive(stmt);
152: }
153:
154: public void visitNewMultiArrayExpr(
155: final NewMultiArrayExpr expr) {
156: // Memory allocation
157: // NegativeArraySizeException
158: if (DeadCodeElimination.DEBUG) {
159: System.out.println(expr + " is prelive");
160: }
161:
162: makeLive(expr);
163: }
164:
165: public void visitNewArrayExpr(final NewArrayExpr expr) {
166: // Memory allocation
167: // NegativeArraySizeException
168: if (DeadCodeElimination.DEBUG) {
169: System.out.println(expr + " is prelive");
170: }
171:
172: makeLive(expr);
173: }
174:
175: public void visitNewExpr(final NewExpr expr) {
176: // Memory allocation
177: if (DeadCodeElimination.DEBUG) {
178: System.out.println(expr + " is prelive");
179: }
180:
181: makeLive(expr);
182: }
183:
184: public void visitStackExpr(final StackExpr expr) {
185: if (expr.stmt() instanceof PhiStmt) {
186: return;
187: }
188:
189: // Stack change
190: if (DeadCodeElimination.DEBUG) {
191: System.out.println(expr + " is prelive");
192: }
193:
194: makeLive(expr);
195: }
196:
197: public void visitZeroCheckExpr(final ZeroCheckExpr expr) {
198: // NullPointerException or DivideByZeroException
199: if (DeadCodeElimination.DEBUG) {
200: System.out.println(expr + " is prelive");
201: }
202:
203: makeLive(expr);
204: }
205:
206: public void visitRCExpr(final RCExpr expr) {
207: // Residency check
208: if (DeadCodeElimination.DEBUG) {
209: System.out.println(expr + " is prelive");
210: }
211:
212: makeLive(expr);
213: }
214:
215: public void visitUCExpr(final UCExpr expr) {
216: // Update check
217: if (DeadCodeElimination.DEBUG) {
218: System.out.println(expr + " is prelive");
219: }
220:
221: makeLive(expr);
222: }
223:
224: public void visitCastExpr(final CastExpr expr) {
225: // ClassCastException
226: if (expr.castType().isReference()) {
227: if (DeadCodeElimination.DEBUG) {
228: System.out.println(expr + " is prelive");
229: }
230:
231: makeLive(expr);
232: } else {
233: expr.visitChildren(this );
234: }
235: }
236:
237: public void visitArithExpr(final ArithExpr expr) {
238: // DivideByZeroException
239: if ((expr.operation() == ArithExpr.DIV)
240: || (expr.operation() == ArithExpr.REM)) {
241:
242: if (expr.type().isIntegral()) {
243: if (DeadCodeElimination.DEBUG) {
244: System.out.println(expr + " is prelive");
245: }
246:
247: makeLive(expr);
248: return;
249: }
250: }
251:
252: expr.visitChildren(this );
253: }
254:
255: public void visitArrayLengthExpr(final ArrayLengthExpr expr) {
256: // NullPointerException
257: if (DeadCodeElimination.DEBUG) {
258: System.out.println(expr + " is prelive");
259: }
260:
261: makeLive(expr);
262: }
263:
264: public void visitArrayRefExpr(final ArrayRefExpr expr) {
265: // NullPointerException, ArrayIndexOutOfBoundsException,
266: // ArrayStoreException
267: if (DeadCodeElimination.DEBUG) {
268: System.out.println(expr + " is prelive");
269: }
270:
271: makeLive(expr);
272: }
273:
274: public void visitFieldExpr(final FieldExpr expr) {
275: // NullPointerException
276: if (DeadCodeElimination.DEBUG) {
277: System.out.println(expr + " is prelive");
278: }
279:
280: makeLive(expr);
281: }
282:
283: public void visitCallStaticExpr(final CallStaticExpr expr) {
284: // Call
285: if (DeadCodeElimination.DEBUG) {
286: System.out.println(expr + " is prelive");
287: }
288:
289: makeLive(expr);
290: }
291:
292: public void visitCallMethodExpr(final CallMethodExpr expr) {
293: // Call
294: if (DeadCodeElimination.DEBUG) {
295: System.out.println(expr + " is prelive");
296: }
297:
298: makeLive(expr);
299: }
300:
301: public void visitCatchExpr(final CatchExpr expr) {
302: // Stack change
303: if (DeadCodeElimination.DEBUG) {
304: System.out.println(expr + " is prelive");
305: }
306:
307: makeLive(expr);
308: }
309:
310: public void visitStackManipStmt(final StackManipStmt stmt) {
311: // Stack change
312: if (DeadCodeElimination.DEBUG) {
313: System.out.println(stmt + " is prelive");
314: }
315:
316: makeLive(stmt);
317: }
318:
319: public void visitThrowStmt(final ThrowStmt stmt) {
320: // Branch
321: if (DeadCodeElimination.DEBUG) {
322: System.out.println(stmt + " is prelive");
323: }
324:
325: makeLive(stmt);
326: }
327:
328: public void visitSwitchStmt(final SwitchStmt stmt) {
329: // Branch
330: if (DeadCodeElimination.DEBUG) {
331: System.out.println(stmt + " is prelive");
332: }
333:
334: makeLive(stmt);
335: }
336:
337: public void visitIfStmt(final IfStmt stmt) {
338: // Branch
339: if (DeadCodeElimination.DEBUG) {
340: System.out.println(stmt + " is prelive");
341: }
342:
343: makeLive(stmt);
344: }
345:
346: public void visitGotoStmt(final GotoStmt stmt) {
347: // Branch
348: if (DeadCodeElimination.DEBUG) {
349: System.out.println(stmt + " is prelive");
350: }
351:
352: makeLive(stmt);
353: }
354:
355: public void visitReturnStmt(final ReturnStmt stmt) {
356: // Branch
357: if (DeadCodeElimination.DEBUG) {
358: System.out.println(stmt + " is prelive");
359: }
360:
361: makeLive(stmt);
362: }
363:
364: public void visitReturnExprStmt(final ReturnExprStmt stmt) {
365: // Branch
366: if (DeadCodeElimination.DEBUG) {
367: System.out.println(stmt + " is prelive");
368: }
369:
370: makeLive(stmt);
371: }
372:
373: public void visitStoreExpr(final StoreExpr expr) {
374: // Can change a variable visible outside the method.
375: if (!(expr.target() instanceof LocalExpr)) {
376: if (DeadCodeElimination.DEBUG) {
377: System.out.println(expr + " is prelive");
378: }
379:
380: makeLive(expr);
381:
382: } else {
383: expr.visitChildren(this );
384: }
385: }
386: });
387:
388: // Go through the nodes in the worklist and make the nodes that
389: // defined the VarExprs live.
390: while (!worklist.isEmpty()) {
391: final VarExpr expr = (VarExpr) worklist.removeFirst();
392:
393: final DefExpr def = expr.def();
394:
395: if (def != null) {
396: if (DeadCodeElimination.DEBUG) {
397: System.out.println("making live def of " + expr);
398: System.out.println(" def = " + def);
399: }
400:
401: makeLive(def.parent());
402: }
403: }
404:
405: // Remove dead stores.
406: cfg.visit(new TreeVisitor() {
407: public void visitStoreExpr(final StoreExpr expr) {
408: final Expr lhs = expr.target();
409: final Expr rhs = expr.expr();
410:
411: if ((lhs.key() == DeadCodeElimination.DEAD)
412: && (rhs.key() == DeadCodeElimination.LIVE)) {
413: rhs.setParent(null);
414: expr.replaceWith(rhs, false);
415:
416: lhs.cleanup();
417: expr.cleanupOnly();
418:
419: lhs.setKey(DeadCodeElimination.DEAD);
420: expr.setKey(DeadCodeElimination.DEAD);
421:
422: rhs.visit(this );
423:
424: } else {
425: expr.visitChildren(this );
426: }
427: }
428: });
429:
430: // Pull out live expressions from their dead parents. Gee, Nate,
431: // what a lovely sentiment. I'll think I'll send that one to
432: // Hallmark.
433: cfg.visit(new TreeVisitor() {
434: public void visitStmt(final Stmt stmt) {
435: if (stmt.key() == DeadCodeElimination.DEAD) {
436: stmt.visitChildren(this );
437: }
438: }
439:
440: public void visitExpr(final Expr expr) {
441: if (expr.key() == DeadCodeElimination.DEAD) {
442: expr.visitChildren(this );
443: return;
444: }
445:
446: final Node parent = expr.parent();
447:
448: if (parent.key() == DeadCodeElimination.LIVE) {
449: // expr will removed later
450: return;
451: }
452:
453: if (parent instanceof ExprStmt) {
454: // The expr and its parent are both dead, but expr resides
455: // in an ExprStmt. We want the parent after all.
456: parent.setKey(DeadCodeElimination.LIVE);
457: return;
458: }
459:
460: // We are going to remove the expr's parent, but keep the
461: // expr. Add eval(expr) [ExprStmt] before the stmt containing
462: // the expr. This is safe, since any exprs to the left in the
463: // statement's tree which are live have already been
464: // extracted.
465:
466: final Stmt oldStmt = expr.stmt();
467:
468: final Tree tree = parent.block().tree();
469:
470: // Replace the expr with an unused stack expr.
471: final StackExpr t = tree.newStack(expr.type());
472: expr.replaceWith(t, false);
473: t.setValueNumber(expr.valueNumber());
474:
475: final ExprStmt stmt = new ExprStmt(expr);
476: stmt.setValueNumber(expr.valueNumber());
477: stmt.setKey(DeadCodeElimination.LIVE);
478:
479: tree.addStmtBefore(stmt, oldStmt);
480:
481: // The old statement is dead and will be removed later.
482: Assert.isTrue(
483: oldStmt.key() == DeadCodeElimination.DEAD,
484: oldStmt + " should be dead");
485: }
486: });
487:
488: // Finally, remove the dead statements from the Tree.
489: cfg.visit(new TreeVisitor() {
490: public void visitTree(final Tree tree) {
491: final Iterator e = tree.stmts().iterator();
492:
493: while (e.hasNext()) {
494: final Stmt stmt = (Stmt) e.next();
495:
496: if (stmt.key() == DeadCodeElimination.DEAD) {
497: if (stmt instanceof LabelStmt) {
498: continue;
499: }
500:
501: if (stmt instanceof JumpStmt) {
502: continue;
503: }
504:
505: if (DeadCodeElimination.DEBUG) {
506: System.out.println("Removing DEAD " + stmt);
507: }
508:
509: e.remove();
510: }
511: }
512: }
513: });
514:
515: worklist = null;
516: }
517:
518: // /**
519: // * Make all of a statement's children LIVE. I don't think its used.
520: // *
521: // * @param stmt
522: // * A statement whose children to make live.
523: // */
524: // void reviveStmt(Stmt stmt) {
525: // stmt.visit(new TreeVisitor() {
526: // public void visitExpr(Expr expr) {
527: // expr.setKey(LIVE);
528: // expr.visitChildren(this);
529: // }
530: // });
531: // }
532:
533: /**
534: * Make a node and all of its children (recursively) LIVE.
535: *
536: * @param node
537: * A node to make LIVE.
538: */
539: void makeLive(Node node) {
540:
541: if (node instanceof StoreExpr) {
542: // Make the StoreExpr, its target, and its RHS live. Add the
543: // target and the RHS to the worklist.
544:
545: final StoreExpr expr = (StoreExpr) node;
546:
547: if (expr.key() == DeadCodeElimination.DEAD) {
548: if (DeadCodeElimination.DEBUG) {
549: System.out.println("making live " + expr + " in "
550: + expr.parent());
551: }
552:
553: expr.setKey(DeadCodeElimination.LIVE);
554: }
555:
556: if (expr.target().key() == DeadCodeElimination.DEAD) {
557: if (DeadCodeElimination.DEBUG) {
558: System.out.println("making live " + expr.target()
559: + " in " + expr);
560: }
561:
562: expr.target().setKey(DeadCodeElimination.LIVE);
563:
564: if (expr.target() instanceof VarExpr) {
565: worklist.add(expr.target());
566: }
567: }
568:
569: if (expr.expr().key() == DeadCodeElimination.DEAD) {
570: if (DeadCodeElimination.DEBUG) {
571: System.out.println("making live " + expr.expr()
572: + " in " + expr);
573: }
574:
575: expr.expr().setKey(DeadCodeElimination.LIVE);
576:
577: if (expr.expr() instanceof VarExpr) {
578: worklist.add(expr.expr());
579: }
580: }
581: }
582:
583: if (node instanceof Expr) {
584: // If one expression inside an ExprStmt is live, then the entire
585: // ExprStmt is live.
586: final Node parent = ((Expr) node).parent();
587:
588: if (parent instanceof ExprStmt) {
589: node = parent;
590: }
591: }
592:
593: node.visit(new TreeVisitor() {
594: public void visitStoreExpr(final StoreExpr expr) {
595: // Don't make local variable targets live yet. If the
596: // variable is used in a live expression, the target will be
597: // made live later.
598: if (expr.target() instanceof LocalExpr) {
599: expr.expr().visit(this );
600:
601: } else {
602: visitExpr(expr);
603: }
604: }
605:
606: public void visitVarExpr(final VarExpr expr) {
607: if (expr.key() == DeadCodeElimination.DEAD) {
608: if (DeadCodeElimination.DEBUG) {
609: System.out.println("making live " + expr
610: + " in " + expr.parent());
611: }
612:
613: expr.setKey(DeadCodeElimination.LIVE);
614: worklist.add(expr);
615: }
616: }
617:
618: public void visitExpr(final Expr expr) {
619: if (expr.key() == DeadCodeElimination.DEAD) {
620: if (DeadCodeElimination.DEBUG) {
621: System.out.println("making live " + expr
622: + " in " + expr.parent());
623: }
624:
625: expr.setKey(DeadCodeElimination.LIVE);
626: }
627:
628: expr.visitChildren(this );
629: }
630:
631: public void visitStmt(final Stmt stmt) {
632: if (stmt.key() == DeadCodeElimination.DEAD) {
633: if (DeadCodeElimination.DEBUG) {
634: System.out.println("making live " + stmt);
635: }
636:
637: stmt.setKey(DeadCodeElimination.LIVE);
638: }
639:
640: stmt.visitChildren(this);
641: }
642: });
643: }
644: }
|