1 cananian 1.1.2.3 // ReversePostOrderEnumerator.java, created Wed Mar 10 9:00:54 1999 by jwhaley
2 cananian 1.1.2.7 // Copyright (C) 1998 John Whaley <jwhaley@alum.mit.edu>
3 cananian 1.1.2.2 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 jwhaley 1.1.2.1 package harpoon.Analysis.DataFlow;
5 jwhaley 1.1.2.1
6 jwhaley 1.1.2.1 /**
7 jwhaley 1.1.2.1 * ReversePostOrderEnumerator
8 jwhaley 1.1.2.1 *
9 cananian 1.1.2.7 * @author John Whaley <jwhaley@alum.mit.edu>
10 cananian 1.5 * @version $Id: ReversePostOrderEnumerator.java,v 1.5 2004/02/08 01:51:05 cananian Exp $
11 jwhaley 1.1.2.1 */
12 jwhaley 1.1.2.1
13 jwhaley 1.1.2.1 import java.util.Enumeration;
14 cananian 1.1.2.6 import java.util.HashSet;
15 cananian 1.1.2.6 import java.util.Set;
16 jwhaley 1.1.2.1 import java.util.Stack;
17 pnkfelix 1.1.2.4 import harpoon.Analysis.BasicBlock;
18 cananian 1.1.2.5 import harpoon.IR.Quads.Quad;
19 cananian 1.3.2.2 import harpoon.Util.ArrayIterator;
20 cananian 1.5 import net.cscott.jutil.IteratorEnumerator;
21 cananian 1.1.2.5 import harpoon.Util.Util;
22 jwhaley 1.1.2.1
23 jwhaley 1.1.2.1 public class ReversePostOrderEnumerator implements Enumeration {
24 jwhaley 1.1.2.1
25 jwhaley 1.1.2.1 public static boolean DEBUG = false;
26 jwhaley 1.1.2.1 public static void db(String s) { System.out.println(s); }
27 jwhaley 1.1.2.1
28 jwhaley 1.1.2.1 Stack order;
29 jwhaley 1.1.2.1
30 pnkfelix 1.1.2.4 public ReversePostOrderEnumerator(BasicBlock start) {
31 jwhaley 1.1.2.1 Stack enum_stack = new Stack();
32 jwhaley 1.1.2.1 Stack bb_stack = new Stack();
33 jwhaley 1.1.2.1 order = new Stack();
34 jwhaley 1.1.2.1 Set done = new HashSet();
35 cananian 1.1.2.6 done.add(start); bb_stack.push(start); enum_stack.push(start.next());
36 jwhaley 1.1.2.1 while (!bb_stack.isEmpty()) {
37 cananian 1.3.2.1 assert bb_stack.size() == enum_stack.size();
38 jwhaley 1.1.2.1 for (Enumeration e = (Enumeration)enum_stack.pop();
39 jwhaley 1.1.2.1 e.hasMoreElements(); ) {
40 jwhaley 1.1.2.1 BasicBlock bb2 = (BasicBlock) e.nextElement();
41 jwhaley 1.1.2.1 if (!done.contains(bb2)) {
42 jwhaley 1.1.2.1 if (DEBUG) db("visiting "+bb2+" for the first time");
43 cananian 1.1.2.6 done.add(bb2);
44 jwhaley 1.1.2.1 bb_stack.push(bb2);
45 jwhaley 1.1.2.1 enum_stack.push(e);
46 jwhaley 1.1.2.1 e = bb2.next();
47 jwhaley 1.1.2.1 }
48 jwhaley 1.1.2.1 }
49 jwhaley 1.1.2.1 Object o = bb_stack.pop();
50 jwhaley 1.1.2.1 if (DEBUG) db("leaving "+o);
51 jwhaley 1.1.2.1 order.push(o);
52 jwhaley 1.1.2.1 }
53 jwhaley 1.1.2.1 }
54 jwhaley 1.1.2.1
55 pnkfelix 1.1.2.4 public ReversePostOrderEnumerator(Quad start) {
56 jwhaley 1.1.2.1 Stack enum_stack = new Stack();
57 jwhaley 1.1.2.1 Stack bb_stack = new Stack();
58 jwhaley 1.1.2.1 order = new Stack();
59 jwhaley 1.1.2.1 Set done = new HashSet();
60 cananian 1.1.2.6 done.add(start); bb_stack.push(start);
61 jwhaley 1.1.2.1 enum_stack.push(new ArrayEnumerator(start.next()));
62 jwhaley 1.1.2.1 while (!bb_stack.isEmpty()) {
63 cananian 1.3.2.1 assert bb_stack.size() == enum_stack.size();
64 jwhaley 1.1.2.1 for (Enumeration e = (Enumeration)enum_stack.pop();
65 jwhaley 1.1.2.1 e.hasMoreElements(); ) {
66 jwhaley 1.1.2.1 Quad bb2 = (Quad) e.nextElement();
67 jwhaley 1.1.2.1 if (!done.contains(bb2)) {
68 jwhaley 1.1.2.1 if (DEBUG) db("visiting "+bb2+" for the first time");
69 cananian 1.1.2.6 done.add(bb2);
70 jwhaley 1.1.2.1 bb_stack.push(bb2);
71 jwhaley 1.1.2.1 enum_stack.push(e);
72 jwhaley 1.1.2.1 e = new ArrayEnumerator(bb2.next());
73 jwhaley 1.1.2.1 }
74 jwhaley 1.1.2.1 }
75 jwhaley 1.1.2.1 Object o = bb_stack.pop();
76 jwhaley 1.1.2.1 if (DEBUG) db("leaving "+o);
77 jwhaley 1.1.2.1 order.push(o);
78 jwhaley 1.1.2.1 }
79 jwhaley 1.1.2.1 }
80 jwhaley 1.1.2.1
81 jwhaley 1.1.2.1 public boolean hasMoreElements() {
82 jwhaley 1.1.2.1 return !order.empty();
83 jwhaley 1.1.2.1 }
84 jwhaley 1.1.2.1
85 jwhaley 1.1.2.1 public Object nextElement() {
86 jwhaley 1.1.2.1 return order.pop();
87 jwhaley 1.1.2.1 }
88 jwhaley 1.1.2.1 public Object next() {
89 jwhaley 1.1.2.1 return order.pop();
90 jwhaley 1.1.2.1 }
91 jwhaley 1.1.2.1
92 jwhaley 1.1.2.1 public ReversePostOrderEnumerator copy() {
93 jwhaley 1.1.2.1 ReversePostOrderEnumerator r = new ReversePostOrderEnumerator();
94 jwhaley 1.1.2.1 r.order = (Stack)order.clone();
95 jwhaley 1.1.2.1 return r;
96 jwhaley 1.1.2.1 }
97 jwhaley 1.1.2.1 private ReversePostOrderEnumerator() {}
98 jwhaley 1.1.2.1
99 cananian 1.3.2.2
100 cananian 1.3.2.2 private class ArrayEnumerator extends IteratorEnumerator {
101 cananian 1.3.2.2 ArrayEnumerator(Object[] oa) { super(new ArrayIterator(oa)); }
102 cananian 1.3.2.2 }
103 cananian 1.2 }