1 cananian 1.1 // DataFlowSolver.java, created Thu May 8 20:07:24 2003 by cananian
2 cananian 1.1 // Copyright (C) 2003 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Analysis.Companions;
5 cananian 1.1
6 cananian 1.2 import harpoon.ClassFile.HCode;
7 cananian 1.1 import harpoon.IR.Properties.CFGEdge;
8 cananian 1.1 import harpoon.IR.Properties.CFGraphable;
9 cananian 1.3 import harpoon.Util.Collections.Graph;
10 cananian 1.4 import net.cscott.jutil.WorkSet;
11 cananian 1.1
12 cananian 1.1 import java.util.Collection;
13 cananian 1.1 import java.util.HashMap;
14 cananian 1.1 import java.util.Iterator;
15 cananian 1.1 import java.util.Map;
16 cananian 1.1 /**
17 cananian 1.1 * The <code>DataFlowSolver</code> class provides a parameterized framework
18 cananian 1.3 * for building simple data flow analyses for various IRs. The
19 cananian 1.3 * <code>DataFlowSolver.Forward</code> and <code>DataFlowSolver.Backward</code>
20 cananian 1.3 * subclasses contain code for forward and backward analyses, respectively.
21 cananian 1.1 *
22 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
23 cananian 1.5 * @version $Id: DataFlowSolver.java,v 1.5 2004/02/08 03:19:17 cananian Exp $
24 cananian 1.1 */
25 cananian 1.3 public abstract class DataFlowSolver<N extends Graph.Node<N,E>,
26 cananian 1.3 E extends Graph.Edge<N,E>,
27 cananian 1.3 FACT> {
28 cananian 1.1 /** Compute the join operation on two dataflow <code>FACT</code>s. */
29 cananian 1.1 protected abstract FACT join(FACT e1, FACT e2);
30 cananian 1.1 /** Return the initial value of the dataflow <code>FACT</code> for the
31 cananian 1.3 * given <code>Node</code> (often, an <code>HCodeElement</code>). */
32 cananian 1.3 protected abstract FACT init(N hce);
33 cananian 1.3 /** Compute all dataflow facts on the given <code>Graph</code>.
34 cananian 1.3 * Note that <code>HCode</code> subclasses with elements implementing
35 cananian 1.3 * <code>CFGraphable</code> are typically also instances of
36 cananian 1.3 * <code>Graph</code>. */
37 cananian 1.3 public abstract Map<N,FACT> compute(Graph<N,E> hc);
38 cananian 1.1
39 cananian 1.1 /**
40 cananian 1.1 * <code>DataFlowSolver.Forward</code> is a dataflow solver for
41 cananian 1.1 * forward dataflow analyses. You need only define a <code>join</code>
42 cananian 1.1 * operation on your <code>FACT</code> type, an initial value for
43 cananian 1.3 * each node (usually, an <code>HCodeElement</code> implementation which
44 cananian 1.3 * also implements <code>Graph.Node</code>, such as <code>Quad</code>)
45 cananian 1.3 * via the return value of the <code>init()</code> method), and a means
46 cananian 1.3 * for computing the <code>OUT</code> dataflow fact given the
47 cananian 1.3 * <code>IN</code> fact for a node (<code>HCodeElement</code>).
48 cananian 1.1 * Calling <code>compute()</code> will then return a mapping from
49 cananian 1.3 * every <code>Graph.Node</code> to the final <code>IN</code>
50 cananian 1.1 * dataflow fact for that element. */
51 cananian 1.1 public static abstract class Forward
52 cananian 1.3 <N extends Graph.Node<N,E>, E extends Graph.Edge<N,E>, FACT>
53 cananian 1.3 extends DataFlowSolver<N,E,FACT> {
54 cananian 1.1 /** Compute the <code>OUT</code> fact given the <code>IN</code>
55 cananian 1.3 * fact for a <code>Node</code> (<code>HCodeElement</code>). */
56 cananian 1.3 protected abstract FACT out(N hce, FACT in);
57 cananian 1.1
58 cananian 1.3 /** Look up the FACT for the Node, adding the initial value to the
59 cananian 1.3 * map if no value was present. */
60 cananian 1.3 private final FACT lookup(N hce, Map<N,FACT> map) {
61 cananian 1.1 if (!map.containsKey(hce))
62 cananian 1.1 map.put(hce, init(hce));
63 cananian 1.1 return map.get(hce);
64 cananian 1.1 }
65 cananian 1.3 public final Map<N,FACT> compute(Graph<N,E> g) {
66 cananian 1.3 final Map<N,FACT> OUTresult = new HashMap<N,FACT>();
67 cananian 1.3 final WorkSet<N> worklist = new WorkSet<N>(g.nodes());
68 cananian 1.1 while (!worklist.isEmpty()) {
69 cananian 1.3 N hce = worklist.removeFirst();
70 cananian 1.1 // compute in using out result.
71 cananian 1.1 FACT in = computeIN(hce, OUTresult);
72 cananian 1.1 // now recompute new out.
73 cananian 1.1 FACT out = out(hce, in);
74 cananian 1.1 // if different from previous, add successors to worklist.
75 cananian 1.1 if (!out.equals(lookup(hce, OUTresult))) {
76 cananian 1.1 OUTresult.put(hce, out);
77 cananian 1.1 for (Iterator<E> it=hce.succC().iterator(); it.hasNext();)
78 cananian 1.1 worklist.add(it.next().to());
79 cananian 1.1 }
80 cananian 1.1 }
81 cananian 1.1 // done! but we want to return IN set, not OUT set.
82 cananian 1.3 final Map<N,FACT> INresult = new HashMap<N,FACT>();
83 cananian 1.5 for (N hce : g.nodes()) {
84 cananian 1.1 INresult.put(hce, computeIN(hce, OUTresult));
85 cananian 1.1 }
86 cananian 1.1 // now really done.
87 cananian 1.1 return INresult;
88 cananian 1.1 }
89 cananian 1.3 private final FACT computeIN(N hce, Map<N,FACT> outMap) {
90 cananian 1.1 Iterator<E> it=hce.predC().iterator();
91 cananian 1.1 if (!it.hasNext()) return init(hce);
92 cananian 1.1 FACT f = lookup(it.next().from(), outMap);
93 cananian 1.1 while (it.hasNext())
94 cananian 1.1 f = join(f, lookup(it.next().from(), outMap));
95 cananian 1.1 return f;
96 cananian 1.1 }
97 cananian 1.1 }
98 cananian 1.1 }