1 cananian 1.1.2.9 // TreeGrapher2.java, created Sun Jul 16 18:23:48 2000 by cananian
2 cananian 1.1.2.9 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.5 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 duncan 1.1.2.1 package harpoon.IR.Tree;
5 duncan 1.1.2.1
6 cananian 1.1.2.8 import harpoon.ClassFile.HCode;
7 duncan 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
8 duncan 1.1.2.1 import harpoon.ClassFile.HCodeElement;
9 duncan 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
10 cananian 1.1.2.9 import harpoon.Temp.Label;
11 duncan 1.1.2.1 import harpoon.Temp.LabelList;
12 cananian 1.6 import net.cscott.jutil.Factories;
13 cananian 1.6 import net.cscott.jutil.GenericMultiMap;
14 cananian 1.6 import net.cscott.jutil.MultiMap;
15 duncan 1.1.2.1 import harpoon.Util.Util;
16 duncan 1.1.2.1
17 cananian 1.1.2.12 import java.util.ArrayList;
18 duncan 1.1.2.1 import java.util.Collection;
19 duncan 1.1.2.1 import java.util.HashMap;
20 duncan 1.1.2.1 import java.util.Iterator;
21 cananian 1.1.2.12 import java.util.List;
22 duncan 1.1.2.1 import java.util.Map;
23 duncan 1.1.2.1
24 duncan 1.1.2.1 /**
25 duncan 1.1.2.1 * <code>TreeGrapher</code> provides a means to externally associate
26 cananian 1.1.2.9 * control-flow graph information with elements of a canonical tree.
27 duncan 1.1.2.1 *
28 cananian 1.1.2.9 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
29 cananian 1.6 * @version $Id: TreeGrapher.java,v 1.6 2004/02/08 01:55:51 cananian Exp $
30 duncan 1.1.2.1 */
31 cananian 1.3.2.2 class TreeGrapher extends CFGrapher<Tree> {
32 cananian 1.1.2.9 Tree firstElement = null;
33 cananian 1.3.2.2 List<Tree> lastElements = new ArrayList<Tree>();
34 cananian 1.3.2.2 final MultiMap<Tree,HCodeEdge<Tree>> predMap =
35 cananian 1.6 new GenericMultiMap<Tree,HCodeEdge<Tree>>(Factories.<HCodeEdge<Tree>>arrayListFactory());
36 cananian 1.3.2.2 final MultiMap<Tree,HCodeEdge<Tree>> succMap =
37 cananian 1.6 new GenericMultiMap<Tree,HCodeEdge<Tree>>(Factories.<HCodeEdge<Tree>>arrayListFactory());
38 cananian 1.1.2.9 /** Class constructor. Don't call this directly -- use
39 cananian 1.1.2.9 * the getGrapher() method in <code>harpoon.IR.Tree.Code</code> instead.
40 cananian 1.1.2.9 */
41 cananian 1.1.2.9 TreeGrapher(Code code) {
42 duncan 1.1.2.1 // Tree grapher only works on canonical trees.
43 cananian 1.3.2.1 assert code.getName().equals("canonical-tree");
44 cananian 1.1.2.10 Edger e = new Edger(code);
45 cananian 1.1.2.9 // done.
46 cananian 1.1.2.9 }
47 cananian 1.3.2.2 public Tree getFirstElement(HCode<Tree> hcode) { return firstElement; }
48 cananian 1.3.2.2 public Tree[] getLastElements(HCode<Tree> hcode) {
49 cananian 1.3.2.2 return
50 cananian 1.1.2.12 lastElements.toArray(new Tree[lastElements.size()]);
51 cananian 1.1.2.12 }
52 cananian 1.5 public List<HCodeEdge<Tree>> predC(Tree hce) {
53 cananian 1.5 return (List<HCodeEdge<Tree>>) predMap.getValues(hce);
54 cananian 1.3.2.2 }
55 cananian 1.5 public List<HCodeEdge<Tree>> succC(Tree hce) {
56 cananian 1.5 return (List<HCodeEdge<Tree>>) succMap.getValues(hce);
57 cananian 1.3.2.2 }
58 cananian 1.1.2.9
59 cananian 1.1.2.10 /** this class does the real work of the grapher */
60 cananian 1.1.2.10 private class Edger {
61 cananian 1.1.2.10 /** maps Temp.Labels to IR.Tree.LABELs */
62 cananian 1.3.2.2 private final Map<Label,LABEL> labelmap = new HashMap<Label,LABEL>();
63 cananian 1.1.2.10 /** Look up an IR.Tree.LABEL given a Temp.Label. */
64 cananian 1.1.2.10 private LABEL lookup(Label l) {
65 cananian 1.3.2.1 assert labelmap.containsKey(l);
66 cananian 1.3.2.2 return labelmap.get(l);
67 cananian 1.1.2.9 }
68 cananian 1.1.2.10 /** Add a <from, to> edge to the predMap and succMap */
69 cananian 1.1.2.10 private void addEdge(final Tree from, final Tree to) {
70 cananian 1.3.2.2 HCodeEdge<Tree> hce = new HCodeEdge<Tree>() {
71 cananian 1.3.2.2 public Tree from() { return from; }
72 cananian 1.3.2.2 public Tree to() { return to; }
73 cananian 1.1.2.9 public String toString() { return "Edge from "+from+" to "+to;}
74 cananian 1.1.2.9 };
75 cananian 1.1.2.9 predMap.add(to, hce);
76 cananian 1.1.2.9 succMap.add(from, hce);
77 cananian 1.1.2.9 }
78 cananian 1.1.2.10 /** the constructor does the analysis. */
79 cananian 1.1.2.10 Edger(Code code) {
80 cananian 1.1.2.10 // collect labels from tree
81 cananian 1.1.2.10 TreeVisitor labelv = new TreeVisitor() {
82 cananian 1.1.2.10 public void visit(Tree e) { /* no op */ }
83 cananian 1.1.2.10 public void visit(LABEL l) { labelmap.put(l.label, l); }
84 cananian 1.1.2.10 };
85 cananian 1.3.2.2 for (Iterator<Tree> it=code.getElementsI(); it.hasNext(); )
86 cananian 1.3.2.2 it.next().accept(labelv);
87 cananian 1.1.2.10 // now make all the edges
88 cananian 1.1.2.10 TreeVisitor edgev = new TreeVisitor() {
89 cananian 1.1.2.9 Tree last = null;
90 cananian 1.1.2.9 void linkup(Stm s, boolean canFallThrough) {
91 cananian 1.1.2.9 if (firstElement==null) firstElement = s;
92 cananian 1.1.2.9 if (last!=null) addEdge(last, s);
93 cananian 1.1.2.9 last = canFallThrough ? s : null;
94 cananian 1.1.2.12 if (succMap.getValues(s).size()==0)
95 cananian 1.1.2.12 lastElements.add(s);
96 cananian 1.1.2.9 }
97 cananian 1.1.2.9 public void visit(Tree t) { /* ignore */ }
98 cananian 1.1.2.9 public void visit(Stm s) { linkup(s, true); }
99 cananian 1.1.2.9 public void visit(CALL c) {
100 cananian 1.1.2.9 // edge to handler; also fall-through.
101 cananian 1.1.2.10 addEdge(c, lookup(c.getHandler().label));
102 cananian 1.1.2.9 linkup(c, true);
103 cananian 1.1.2.9 }
104 cananian 1.1.2.9 public void visit(CJUMP c) {
105 cananian 1.1.2.9 // edges to iftrue and iffalse; no fall-through.
106 cananian 1.1.2.10 addEdge(c, lookup(c.iffalse));
107 cananian 1.1.2.10 addEdge(c, lookup(c.iftrue));
108 cananian 1.1.2.9 linkup(c, false);
109 cananian 1.1.2.9 }
110 cananian 1.1.2.9 public void visit(ESEQ e) {
111 cananian 1.3.2.1 assert false : "Not in canonical form!";
112 cananian 1.1.2.9 }
113 cananian 1.1.2.9 public void visit(JUMP j) {
114 cananian 1.1.2.9 // edges to targets list. no fall-through.
115 cananian 1.3.2.1 assert j.targets!=null : "JUMP WITH NO TARGETS!";
116 cananian 1.1.2.9 for (LabelList ll=j.targets; ll!=null; ll=ll.tail)
117 cananian 1.1.2.10 addEdge(j, lookup(ll.head));
118 cananian 1.1.2.9 linkup(j, false);
119 cananian 1.1.2.9 }
120 cananian 1.1.2.9 public void visit(RETURN r) {
121 cananian 1.1.2.9 // no fall-through.
122 cananian 1.1.2.9 linkup(r, false);
123 cananian 1.1.2.9 }
124 cananian 1.1.2.9 public void visit(SEQ s) { /* ignore this guy! */ }
125 cananian 1.1.2.9 public void visit(THROW t) {
126 cananian 1.1.2.9 // no fall-through.
127 cananian 1.1.2.9 linkup(t, false);
128 duncan 1.1.2.1 }
129 cananian 1.1.2.10 };
130 cananian 1.1.2.9 // iterate in depth-first pre-order:
131 cananian 1.3.2.2 for (Iterator<Tree> it=code.getElementsI(); it.hasNext(); )
132 cananian 1.3.2.2 it.next().accept(edgev);
133 cananian 1.1.2.10 // done!
134 duncan 1.1.2.1 }
135 duncan 1.1.2.1 }
136 cananian 1.2 }