1 cananian 1.1 // DomFrontier.java, created Mon Sep 14 22:21:38 1998 by cananian
2 cananian 1.6 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.6 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Analysis;
5 cananian 1.1
6 cananian 1.6.2.3 import harpoon.ClassFile.HCode;
7 cananian 1.6.2.3 import harpoon.ClassFile.HCodeEdge;
8 cananian 1.6.2.3 import harpoon.ClassFile.HCodeElement;
9 cananian 1.6.2.8 import harpoon.IR.Properties.CFGrapher;
10 cananian 1.6.2.9 import harpoon.Util.ArrayFactory;
11 cananian 1.6.2.8 import harpoon.Util.ArrayIterator;
12 cananian 1.6.2.8 import harpoon.Util.ArraySet;
13 cananian 1.8 import net.cscott.jutil.AggregateSetFactory;
14 cananian 1.8 import net.cscott.jutil.GenericMultiMap;
15 cananian 1.8 import net.cscott.jutil.MultiMap;
16 cananian 1.8 import net.cscott.jutil.Default;
17 cananian 1.6.2.8 import harpoon.Util.Util;
18 cananian 1.8 import net.cscott.jutil.WorkSet;
19 cananian 1.1
20 cananian 1.6.2.9 import java.util.Collection;
21 cananian 1.6.2.8 import java.util.Collections;
22 cananian 1.1 import java.util.Hashtable;
23 cananian 1.6.2.8 import java.util.Iterator;
24 cananian 1.6.2.6 import java.util.Set;
25 cananian 1.6.2.6 import java.util.HashSet;
26 cananian 1.1 /**
27 cananian 1.1 * <code>DomFrontier</code> computes the dominance frontier of a
28 cananian 1.1 * flowgraph-structured IR. The <code>HCodeElement</code>s must implement
29 cananian 1.6.2.7 * the <code>harpoon.IR.Properties.CFGraphable</code> interface.
30 cananian 1.1 *
31 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
32 cananian 1.9 * @version $Id: DomFrontier.java,v 1.9 2004/02/08 03:19:12 cananian Exp $
33 cananian 1.1 */
34 cananian 1.1
35 cananian 1.1 public class DomFrontier {
36 cananian 1.6.2.9 final ArrayFactory af;
37 cananian 1.6.2.8 /** Creates a <code>DomFrontier</code> using a pre-existing
38 cananian 1.6.2.8 * <code>DomTree</code>. */
39 cananian 1.1 public DomFrontier(DomTree dt) {
40 cananian 1.6.2.9 this.af = dt.hcode.elementArrayFactory();
41 cananian 1.6.2.8 analyze(dt);
42 cananian 1.6.2.8 }
43 cananian 1.6.2.8 /** Creates a <code>DomFrontier</code> for the given
44 cananian 1.6.2.8 * <code>HCode</code> using the default grapher; if
45 cananian 1.6.2.8 * <code>isPost</code> is <code>false</code> creates the
46 cananian 1.6.2.8 * dominance frontier; otherwise creates the postdominance
47 cananian 1.6.2.8 * frontier. */
48 cananian 1.6.2.8 public DomFrontier(HCode hcode, boolean isPost) {
49 cananian 1.6.2.8 this(hcode, CFGrapher.DEFAULT, isPost);
50 cananian 1.1 }
51 cananian 1.6.2.8 /** Creates a <code>DomFrontier</code> for the given
52 cananian 1.6.2.8 * <code>HCode</code> using the given <code>CFGrapher</code>; if
53 cananian 1.6.2.8 * <code>isPost</code> is <code>false</code> creates the
54 cananian 1.6.2.8 * dominance frontier; otherwise creates the postdominance
55 cananian 1.6.2.8 * frontier. */
56 cananian 1.6.2.8 public DomFrontier(HCode hcode, CFGrapher grapher, boolean isPost) {
57 cananian 1.6.2.8 this(new DomTree(hcode, grapher, isPost));
58 cananian 1.1 }
59 cananian 1.1
60 cananian 1.6.2.9 MultiMap DF = new GenericMultiMap(new AggregateSetFactory());
61 cananian 1.1
62 cananian 1.5 /** Return an array of <code>HCodeElement</code>s in the (post)dominance
63 cananian 1.2 * frontier of <code>n</code>.
64 cananian 1.2 */
65 cananian 1.6.2.8 public HCodeElement[] df(HCodeElement n) {
66 cananian 1.6.2.9 Collection c = DF.getValues(n);
67 cananian 1.6.2.9 return (HCodeElement[]) c.toArray(af.newArray(c.size()));
68 cananian 1.5 }
69 cananian 1.6.2.8 /** Return an immutable <code>Set</code> of <code>HCodeElement</code>s
70 cananian 1.6.2.8 * in the (post)dominance frontier of <code>n</code>.
71 cananian 1.5 */
72 cananian 1.6.2.8 public Set dfS(HCodeElement n) {
73 cananian 1.6.2.9 return Collections.unmodifiableSet((Set)DF.getValues(n));
74 cananian 1.1 }
75 cananian 1.1
76 cananian 1.6.2.8 void analyze(DomTree dt) {
77 cananian 1.6.2.8 HCodeElement[] roots = dt.roots();
78 cananian 1.3 for (int i=0; i < roots.length; i++)
79 cananian 1.6.2.8 computeDF(dt, roots[i]);
80 cananian 1.1 }
81 cananian 1.6.2.8 void computeDF(DomTree dt, HCodeElement n) {
82 cananian 1.6.2.8 CFGrapher grapher = dt.grapher;
83 cananian 1.1
84 cananian 1.1 // for every child y in succ[n]
85 cananian 1.6.2.8 for (Iterator it=grapher.succC(n).iterator(); it.hasNext(); ) {
86 cananian 1.6.2.8 HCodeElement y = ((HCodeEdge)it.next()).to();
87 cananian 1.6.2.8 if (!n.equals( dt.idom(y) ))
88 cananian 1.6.2.9 DF.add(n, y);
89 cananian 1.1 }
90 cananian 1.1 // for each child c of n in the (post)dominator tree
91 cananian 1.9 for (Object cO : dt.children(n)) {
92 cananian 1.9 HCodeElement c = (HCodeElement) cO;
93 cananian 1.6.2.8 computeDF(dt, c);
94 cananian 1.1 // for each element w of DF[c]
95 cananian 1.9 for (Object wO : DF.getValues(c)) {
96 cananian 1.9 HCodeElement w = (HCodeElement) wO;
97 cananian 1.6.2.9 if (!n.equals( dt.idom(w) ))
98 cananian 1.6.2.9 DF.add(n, w);
99 cananian 1.6.2.9 }
100 cananian 1.1 }
101 cananian 1.1 }
102 cananian 1.1 }