1 cananian 1.1.2.1 // IdentifyNoHandler.java, created Wed Jul 12 18:26:16 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.Backend.PreciseC;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
7 cananian 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
8 cananian 1.1.2.1 import harpoon.IR.Tree.CALL;
9 cananian 1.1.2.1 import harpoon.IR.Tree.JUMP;
10 cananian 1.1.2.1 import harpoon.IR.Tree.LABEL;
11 cananian 1.1.2.1 import harpoon.IR.Tree.MOVE;
12 cananian 1.1.2.1 import harpoon.IR.Tree.NAME;
13 cananian 1.1.2.1 import harpoon.IR.Tree.Stm;
14 cananian 1.1.2.1 import harpoon.IR.Tree.TEMP;
15 cananian 1.1.2.1 import harpoon.IR.Tree.THROW;
16 cananian 1.1.2.1 import harpoon.IR.Tree.Tree;
17 cananian 1.1.2.1 import harpoon.IR.Tree.TreeVisitor;
18 cananian 1.1.2.1 import harpoon.Temp.Temp;
19 cananian 1.5 import net.cscott.jutil.GenericMultiMap;
20 cananian 1.5 import net.cscott.jutil.MultiMap;
21 cananian 1.1.2.1 import harpoon.Util.Util;
22 cananian 1.1.2.1 import java.util.Collection;
23 cananian 1.1.2.1 import java.util.HashSet;
24 cananian 1.1.2.1 import java.util.Iterator;
25 cananian 1.1.2.1 import java.util.Set;
26 cananian 1.1.2.1 /**
27 cananian 1.1.2.1 * <code>IdentifyNoHandler</code>
28 cananian 1.1.2.1 *
29 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
30 cananian 1.5 * @version $Id: IdentifyNoHandler.java,v 1.5 2004/02/08 01:57:40 cananian Exp $
31 cananian 1.1.2.1 */
32 cananian 1.1.2.1 public class IdentifyNoHandler {
33 cananian 1.1.2.1 private Set nohandlercalls = new HashSet();
34 cananian 1.1.2.1 /** Creates a <code>IdentifyNoHandler</code>. */
35 cananian 1.1.2.1 public IdentifyNoHandler(harpoon.IR.Tree.Code c) {
36 cananian 1.1.2.1 // post-order DFS.
37 cananian 1.1.2.1 CFGrapher gr = c.getGrapher();
38 cananian 1.1.2.1 dfs((Stm)gr.getFirstElement(c),gr,new HashSet(), new Visitor(gr));
39 cananian 1.1.2.1 // done with init.
40 cananian 1.1.2.1 }
41 cananian 1.1.2.1 public boolean requiresHandler(CALL call) {
42 cananian 1.1.2.1 return !nohandlercalls.contains(call);
43 cananian 1.1.2.1 }
44 cananian 1.1.2.1 private static void dfs(Stm stm, CFGrapher gr, Set seen, TreeVisitor v) {
45 cananian 1.3.2.1 assert !seen.contains(stm);
46 cananian 1.1.2.1 seen.add(stm);
47 cananian 1.1.2.1 for (Iterator it=gr.succC(stm).iterator(); it.hasNext(); ) {
48 cananian 1.1.2.1 Stm succ = (Stm) ((HCodeEdge)it.next()).to();
49 cananian 1.1.2.1 if (!seen.contains(succ))
50 cananian 1.1.2.1 dfs(succ, gr, seen, v);
51 cananian 1.1.2.1 }
52 cananian 1.1.2.1 // post-order visit.
53 cananian 1.1.2.1 stm.accept(v);
54 cananian 1.1.2.1 }
55 cananian 1.1.2.1
56 cananian 1.1.2.1 /* this is like a simple reaching-def analysis, except we want to
57 cananian 1.1.2.1 * make sure that the exception isn't tested-and-branched-on before
58 cananian 1.1.2.1 * it is thrown. */
59 cananian 1.1.2.1 private class Visitor extends TreeVisitor {
60 cananian 1.1.2.1 final CFGrapher gr;
61 cananian 1.1.2.1 final MultiMap directlyThrows = new GenericMultiMap();
62 cananian 1.1.2.1 Visitor(CFGrapher gr) { this.gr = gr; }
63 cananian 1.1.2.1 public void visit(Tree t) {
64 cananian 1.3.2.1 assert false : "should only visit stms";
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1 public void visit(Stm t) { // only propagate if t is a no-op.
67 cananian 1.1.2.1 if (Stm.isNop(t)) propagate(t);
68 cananian 1.1.2.1 }
69 cananian 1.1.2.1 public void visit(THROW t) {
70 cananian 1.1.2.1 if (t.getRetex() instanceof TEMP)
71 cananian 1.1.2.1 directlyThrows.put(t, ((TEMP)t.getRetex()).temp);
72 cananian 1.1.2.1 }
73 cananian 1.1.2.1 public void visit(MOVE t) {
74 cananian 1.1.2.1 propagate(t);
75 cananian 1.1.2.1 if (t.getDst() instanceof TEMP) {
76 cananian 1.1.2.1 Temp dst = ((TEMP)t.getDst()).temp;
77 cananian 1.1.2.1 if (directlyThrows.contains(t, dst)) { // kill
78 cananian 1.1.2.1 directlyThrows.remove(t, dst);
79 cananian 1.1.2.1 if (t.getSrc() instanceof TEMP) // gen
80 cananian 1.1.2.1 directlyThrows.add(t, ((TEMP)t.getSrc()).temp);
81 cananian 1.1.2.1 }
82 cananian 1.1.2.1 }
83 cananian 1.1.2.1 }
84 cananian 1.1.2.1 public void visit(CALL t) {
85 cananian 1.1.2.1 for (Iterator it=gr.succC(t).iterator(); it.hasNext(); ) {
86 cananian 1.1.2.1 Stm stm = (Stm) ((HCodeEdge)it.next()).to();
87 cananian 1.1.2.1 if (!(stm instanceof LABEL)) continue;
88 cananian 1.1.2.1 if (!t.getHandler().label.equals(((LABEL)stm).label)) continue;
89 cananian 1.1.2.1 // oh boy, this is the exception edge!
90 cananian 1.1.2.1 Set thrown = (Set) directlyThrows.getValues(stm);
91 cananian 1.1.2.1 if (thrown.contains(t.getRetex().temp))
92 cananian 1.1.2.1 // and we directly throw the retex!
93 cananian 1.1.2.1 nohandlercalls.add(t); // this is a no-handler call!
94 cananian 1.1.2.1 }
95 cananian 1.1.2.1 }
96 cananian 1.1.2.1 // unconditional JUMP has no effect on thrown set
97 cananian 1.1.2.1 public void visit(JUMP t) {
98 cananian 1.1.2.1 if (t.getExp() instanceof NAME) propagate(t);
99 cananian 1.1.2.1 }
100 cananian 1.1.2.1 // LABEL has no effect on thrown set
101 cananian 1.1.2.1 public void visit(LABEL t) { propagate(t); }
102 cananian 1.1.2.1
103 cananian 1.1.2.1 // in set == out set.
104 cananian 1.1.2.1 private void propagate(Tree t) {
105 cananian 1.1.2.1 Collection c = gr.succC(t);
106 cananian 1.3.2.1 assert c.size()==1;
107 cananian 1.1.2.1 Stm next = (Stm) ((HCodeEdge)c.iterator().next()).to();
108 cananian 1.1.2.1 // note that thrown set is already defined because we're
109 cananian 1.1.2.1 // doing this is dfs post-order.
110 cananian 1.1.2.1 Set thrown = (Set) directlyThrows.getValues(next);
111 cananian 1.1.2.1 directlyThrows.addAll(t, thrown);
112 cananian 1.1.2.1 }
113 cananian 1.1.2.1 }
114 cananian 1.2 }