1 cananian 1.1.2.1 // DeadCodeElimination.java, created Wed Feb 16 12:58:13 2000 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Tree;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.Liveness;
7 cananian 1.1.2.1 import harpoon.Analysis.DataFlow.LiveVars;
8 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
9 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
10 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
11 cananian 1.1.2.2 import harpoon.IR.Properties.CFGrapher;
12 cananian 1.1.2.2 import harpoon.IR.Properties.UseDefer;
13 cananian 1.1.2.2 import harpoon.IR.Tree.CanonicalTreeCode;
14 cananian 1.1.2.2 import harpoon.IR.Tree.DerivationGenerator;
15 jwhaley 1.1.2.5 import harpoon.IR.Tree.EXPR;
16 cananian 1.1.2.2 import harpoon.IR.Tree.Exp;
17 cananian 1.1.2.2 import harpoon.IR.Tree.MOVE;
18 cananian 1.1.2.2 import harpoon.IR.Tree.SEQ;
19 cananian 1.1.2.2 import harpoon.IR.Tree.Stm;
20 cananian 1.1.2.2 import harpoon.IR.Tree.TEMP;
21 cananian 1.1.2.2 import harpoon.IR.Tree.Tree;
22 cananian 1.1.2.2 import harpoon.IR.Tree.TreeFactory;
23 cananian 1.1.2.2 import harpoon.IR.Tree.TreeKind;
24 cananian 1.1.2.1 import harpoon.Temp.Temp;
25 cananian 1.1.2.1 import harpoon.Util.Util;
26 cananian 1.1.2.1
27 cananian 1.1.2.1 import java.util.Arrays;
28 cananian 1.1.2.1 import java.util.Collections;
29 cananian 1.1.2.1 import java.util.HashSet;
30 cananian 1.1.2.1 import java.util.Iterator;
31 cananian 1.1.2.1 import java.util.List;
32 cananian 1.1.2.1 import java.util.Set;
33 cananian 1.1.2.1
34 cananian 1.1.2.1 /**
35 cananian 1.1.2.1 * <code>DeadCodeElimination</code> removes unused MOVEs, useless
36 jwhaley 1.1.2.5 * EXPRs, and whatever other cruft it can detect using a liveness
37 cananian 1.1.2.1 * analysis.
38 cananian 1.1.2.1 *
39 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
40 cananian 1.5 * @version $Id: DeadCodeElimination.java,v 1.5 2003/03/11 18:46:47 cananian Exp $
41 cananian 1.1.2.1 */
42 cananian 1.1.2.1 public abstract class DeadCodeElimination extends Simplification {
43 cananian 1.1.2.1 // hide constructor
44 cananian 1.1.2.1 private DeadCodeElimination() { }
45 cananian 1.1.2.1
46 cananian 1.1.2.1 /** Code factory for applying DeadCodeElimination to a
47 cananian 1.1.2.1 * canonical tree. Clones the tree before doing
48 cananian 1.1.2.1 * DCE in-place. */
49 cananian 1.1.2.1 public static HCodeFactory codeFactory(final HCodeFactory parent) {
50 cananian 1.3.2.1 assert parent.getCodeName().equals(CanonicalTreeCode.codename);
51 cananian 1.1.2.1 return new HCodeFactory() {
52 cananian 1.1.2.1 public HCode convert(HMethod m) {
53 cananian 1.1.2.1 HCode hc = parent.convert(m);
54 cananian 1.1.2.1 if (hc!=null) {
55 cananian 1.1.2.1 harpoon.IR.Tree.Code code = (harpoon.IR.Tree.Code) hc;
56 cananian 1.1.2.1 // clone code...
57 cananian 1.1.2.6 code = (harpoon.IR.Tree.Code) code.clone(m).hcode();
58 cananian 1.1.2.1 DerivationGenerator dg = null;
59 cananian 1.1.2.1 try {
60 cananian 1.1.2.1 dg = (DerivationGenerator) code.getTreeDerivation();
61 cananian 1.1.2.1 } catch (ClassCastException ex) { /* i guess not */ }
62 cananian 1.1.2.1 // ...do liveness analysis and modify cloned code in-place.
63 cananian 1.1.2.1 simplify((Stm)code.getRootElement(), dg, HCE_RULES(code));
64 cananian 1.1.2.3 hc = code;
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1 return hc;
67 cananian 1.1.2.1 }
68 cananian 1.1.2.1 public String getCodeName() { return parent.getCodeName(); }
69 cananian 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
70 cananian 1.1.2.1 };
71 cananian 1.1.2.1 }
72 cananian 1.1.2.1
73 cananian 1.5 public static List<Rule> HCE_RULES(final harpoon.IR.Tree.Code code) {
74 cananian 1.1.2.1 // compute liveness
75 cananian 1.5 final CFGrapher<Tree> cfgr = code.getGrapher();
76 cananian 1.5 final UseDefer<Tree> ud = code.getUseDefer();
77 cananian 1.1.2.1 final Liveness l = new LiveVars(code, cfgr, ud, Collections.EMPTY_SET);
78 cananian 1.1.2.1 // now collect info about dead moves.
79 cananian 1.5 final Set<MOVE> deadMoves = new HashSet<MOVE>();
80 cananian 1.5 for (Iterator<Tree> it=code.getElementsI(); it.hasNext(); ) {
81 cananian 1.5 Tree tr = it.next();
82 cananian 1.1.2.1 if (tr.kind() == TreeKind.MOVE &&
83 cananian 1.1.2.1 ((MOVE)tr).getDst().kind() == TreeKind.TEMP) {
84 cananian 1.1.2.1 Temp temp = ((TEMP) ((MOVE) tr).getDst()).temp;
85 cananian 1.1.2.1 Set liveOut = l.getLiveOut(tr);
86 cananian 1.1.2.1 if (!liveOut.contains(temp)) // a MOVE to an unused temp.
87 cananian 1.5 deadMoves.add((MOVE)tr);
88 cananian 1.1.2.1 }
89 cananian 1.1.2.1 }
90 cananian 1.1.2.1 // debugging
91 cananian 1.1.2.1 System.err.print("["+deadMoves.size()+" DEAD MOVES]");
92 cananian 1.1.2.1
93 cananian 1.1.2.1 return Arrays.asList(new Rule[] {
94 jwhaley 1.1.2.5 // remove expressions of the form EXPR(CONST(c)) or EXPR(TEMP(t))
95 cananian 1.1.2.1 //
96 jwhaley 1.1.2.5 // SEQ(EXPR(CONST(c)), s1) --> s1
97 jwhaley 1.1.2.5 // SEQ(s1, EXPR(CONST(c)) --> s1
98 jwhaley 1.1.2.5 // SEQ(EXPR(TEMP(t)), s1) --> s1
99 jwhaley 1.1.2.5 // SEQ(s1, EXPR(TEMP(t))) --> s1
100 cananian 1.1.2.1 new Rule("removeNop") {
101 cananian 1.1.2.1 public boolean match(Stm s) {
102 cananian 1.1.2.1 if (s.kind() != TreeKind.SEQ) return false;
103 cananian 1.1.2.1 SEQ seq = (SEQ) s;
104 cananian 1.1.2.1 return isNop(seq.getLeft()) || isNop(seq.getRight());
105 cananian 1.1.2.1 }
106 cananian 1.1.2.1 public Stm apply(TreeFactory tf,Stm s,DerivationGenerator dg) {
107 cananian 1.1.2.1 SEQ seq = (SEQ) s;
108 cananian 1.1.2.1 if (isNop(seq.getLeft())) return seq.getRight();
109 cananian 1.1.2.1 if (isNop(seq.getRight())) return seq.getLeft();
110 cananian 1.1.2.1 throw new Error("Neither side is a Nop!");
111 cananian 1.1.2.1 }
112 cananian 1.1.2.1 private boolean isNop(Stm s) {
113 jwhaley 1.1.2.5 if (s.kind() != TreeKind.EXPR) return false;
114 jwhaley 1.1.2.5 EXPR exp = (EXPR) s;
115 cananian 1.1.2.1 return contains(_KIND(exp.getExp()), _CONST|_TEMP);
116 cananian 1.1.2.1 }
117 cananian 1.1.2.1 },
118 jwhaley 1.1.2.5 // MOVE(t1, e) --> EXPR(e) if t1 is dead after move
119 cananian 1.1.2.1 new Rule("deadMoves") {
120 cananian 1.1.2.1 public boolean match(Stm s) {
121 cananian 1.1.2.1 return deadMoves.contains(s);
122 cananian 1.1.2.1 }
123 cananian 1.1.2.1 public Stm apply(TreeFactory tf,Stm s,DerivationGenerator dg) {
124 cananian 1.1.2.1 MOVE move = (MOVE) s;
125 jwhaley 1.1.2.5 return new EXPR(tf, move, move.getSrc());
126 cananian 1.1.2.1 }
127 cananian 1.1.2.1 },
128 cananian 1.1.2.1 });
129 cananian 1.1.2.1 }
130 cananian 1.2 }