1 cananian 1.1.2.4 // TreeSolver.java, created Tue Jul 27 17:53:34 1999 by duncan
2 cananian 1.1.2.3 // Copyright (C) 1998 Duncan Bryce <duncan@lcs.mit.edu>
3 cananian 1.1.2.3 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 duncan 1.1.2.1 package harpoon.Analysis.DataFlow;
5 duncan 1.1.2.1
6 duncan 1.1.2.1 import java.util.Enumeration;
7 duncan 1.1.2.1 import java.util.Iterator;
8 cananian 1.1.2.8 import harpoon.IR.Properties.CFGraphable;
9 duncan 1.1.2.1 import harpoon.ClassFile.HCodeElement;
10 cananian 1.1.2.11 import harpoon.Util.Collections.WorkSet;
11 duncan 1.1.2.1 import harpoon.Util.Util;
12 cananian 1.5 import net.cscott.jutil.IteratorEnumerator;
13 duncan 1.1.2.1 import harpoon.Analysis.EdgesIterator;
14 pnkfelix 1.1.2.6 import harpoon.Analysis.BasicBlock;
15 duncan 1.1.2.1
16 duncan 1.1.2.5 /**
17 duncan 1.1.2.5 * A blatant rip-off of Whaley's <code>QuadSolver</code> class, used to
18 duncan 1.1.2.5 * solve data flow equations (baby). As Felix pointed out, there is
19 duncan 1.1.2.5 * probably not much of a need for separate quad and tree solver classes.
20 duncan 1.1.2.5 * Ultimately they should probably be combined into a
21 duncan 1.1.2.5 * <code>BasicBlockSolver</code> class.
22 duncan 1.1.2.5 *
23 cananian 1.1.2.3 * @author Duncan Bryce <duncan@lcs.mit.edu>
24 cananian 1.5 * @version $Id: TreeSolver.java,v 1.5 2004/02/08 01:51:05 cananian Exp $
25 cananian 1.1.2.2 */
26 duncan 1.1.2.1 public abstract class TreeSolver {
27 duncan 1.1.2.1
28 duncan 1.1.2.7 public static boolean DEBUG = false;
29 duncan 1.1.2.1 public static void db(String s) { System.out.println(s); }
30 duncan 1.1.2.1
31 duncan 1.1.2.5
32 duncan 1.1.2.1 public static void forward_rpo_solver(BasicBlock root,
33 duncan 1.1.2.1 DataFlowBasicBlockVisitor v) {
34 duncan 1.1.2.1
35 duncan 1.1.2.1 ReversePostOrderEnumerator rpo = new ReversePostOrderEnumerator(root);
36 duncan 1.1.2.1 boolean changed = false;
37 duncan 1.1.2.1 do {
38 duncan 1.1.2.1 changed = false;
39 duncan 1.1.2.1
40 duncan 1.1.2.1 ReversePostOrderEnumerator iter = rpo.copy();
41 duncan 1.1.2.1 while (iter.hasMoreElements()) {
42 duncan 1.1.2.1 BasicBlock q = (BasicBlock)iter.next();
43 duncan 1.1.2.1 if (DEBUG) db("visiting: "+q);
44 pnkfelix 1.1.2.10 q.accept(v);
45 duncan 1.1.2.1 for (Enumeration e=q.next(); e.hasMoreElements(); ) {
46 duncan 1.1.2.1 BasicBlock qn = (BasicBlock)e.nextElement();
47 duncan 1.1.2.1 if (DEBUG) db("doing edge "+q+" -> "+qn);
48 duncan 1.1.2.5 changed = v.merge(q, qn);
49 duncan 1.1.2.1 }
50 duncan 1.1.2.1 }
51 duncan 1.1.2.1
52 duncan 1.1.2.1 } while (changed);
53 duncan 1.1.2.1
54 duncan 1.1.2.1 }
55 duncan 1.1.2.1
56 duncan 1.1.2.1 public static void worklist_solver(BasicBlock root,
57 duncan 1.1.2.1 DataFlowBasicBlockVisitor v) {
58 duncan 1.1.2.1
59 cananian 1.5 WorkSet W = new WorkSet();
60 duncan 1.1.2.1 W.push(root);
61 duncan 1.1.2.7 while (!W.isEmpty()) {
62 duncan 1.1.2.7 //v.changed = false;
63 duncan 1.1.2.7 BasicBlock q = (BasicBlock) W.pull();
64 duncan 1.1.2.7 if (DEBUG) db("visiting: "+q);
65 pnkfelix 1.1.2.10 q.accept(v);
66 duncan 1.1.2.7 v.addSuccessors(W, q);
67 duncan 1.1.2.7 }
68 duncan 1.1.2.7 }
69 duncan 1.1.2.7
70 duncan 1.1.2.7
71 duncan 1.1.2.7 public static void worklist_solver(Iterator iter,
72 duncan 1.1.2.7 DataFlowBasicBlockVisitor v) {
73 duncan 1.1.2.7
74 cananian 1.5 WorkSet W = new WorkSet();
75 duncan 1.1.2.7 while (iter.hasNext()) W.push(iter.next());
76 duncan 1.1.2.1 while (!W.isEmpty()) {
77 duncan 1.1.2.1 //v.changed = false;
78 duncan 1.1.2.1 BasicBlock q = (BasicBlock) W.pull();
79 duncan 1.1.2.1 if (DEBUG) db("visiting: "+q);
80 pnkfelix 1.1.2.10 q.accept(v);
81 duncan 1.1.2.1 v.addSuccessors(W, q);
82 duncan 1.1.2.1 }
83 duncan 1.1.2.1 }
84 duncan 1.1.2.1
85 duncan 1.1.2.1 public static int getMaxID(HCodeElement root) {
86 duncan 1.1.2.1 int max = 0;
87 cananian 1.1.2.8 for (Iterator i = new EdgesIterator((CFGraphable)root); i.hasNext();) {
88 duncan 1.1.2.1 int id = ((HCodeElement)(i.next())).getID();
89 cananian 1.3.2.1 assert id >= 0;
90 duncan 1.1.2.1 if (id > max) max = id;
91 duncan 1.1.2.1 }
92 duncan 1.1.2.1 if (DEBUG) db("max tree ID is "+max);
93 duncan 1.1.2.1 return max;
94 duncan 1.1.2.1 }
95 cananian 1.2 }