1 cananian 1.1.2.1 // SESE.java, created Mon Mar 1 23:52:29 1999 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1999 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis;
5 cananian 1.1.2.1
6 cananian 1.1.2.2 import harpoon.ClassFile.HCode;
7 cananian 1.1.2.2 import harpoon.ClassFile.HCodeEdge;
8 cananian 1.1.2.2 import harpoon.ClassFile.HCodeElement;
9 cananian 1.6 import net.cscott.jutil.UnmodifiableIterator;
10 cananian 1.1.2.1 import harpoon.Util.Util;
11 cananian 1.1.2.1
12 cananian 1.1.2.1 import java.util.AbstractSet;
13 cananian 1.1.2.4 import java.util.ArrayList;
14 cananian 1.1.2.4 import java.util.Collection;
15 cananian 1.1.2.2 import java.util.Collections;
16 cananian 1.1.2.1 import java.util.HashMap;
17 cananian 1.1.2.1 import java.util.HashSet;
18 cananian 1.1.2.1 import java.util.Iterator;
19 cananian 1.1.2.1 import java.util.LinkedList;
20 cananian 1.1.2.1 import java.util.List;
21 cananian 1.1.2.1 import java.util.ListIterator;
22 cananian 1.1.2.1 import java.util.Map;
23 cananian 1.1.2.1 import java.util.Set;
24 cananian 1.1.2.2 import java.util.Stack;
25 cananian 1.1.2.1
26 cananian 1.1.2.1 /**
27 cananian 1.1.2.1 * <code>SESE</code> computes nested single-entry single-exit regions
28 cananian 1.1.2.12 * from a cycle-equivalency set.<p>
29 cananian 1.1.2.12 * See Johnson, Pearson, and Pingali, <A
30 cananian 1.1.2.12 * HREF="http://cs-tr.cs.cornell.edu:80/Dienst/UI/1.0/Display/ncstrl.cornell/TR93-1365"
31 cananian 1.1.2.12 * >"Finding regions fast: Single entry single exit and control regions in
32 cananian 1.1.2.12 * linear time"</A> (Technical Report TR 93-1365, Cornell University,
33 cananian 1.1.2.12 * July 1993). Their PLDI'94 paper "The program structure tree: Computing
34 cananian 1.1.2.12 * control regions in linear time" might also provide a useful reference.
35 cananian 1.1.2.1 *
36 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
37 cananian 1.7 * @version $Id: SESE.java,v 1.7 2004/02/08 03:19:12 cananian Exp $
38 cananian 1.1.2.1 */
39 cananian 1.1.2.1 public class SESE {
40 cananian 1.1.2.2 /** Root of <code>Region</code> tree. */
41 cananian 1.1.2.2 public final Region topLevel=new Region();
42 cananian 1.1.2.2 /** Mapping from Nodes/Edges to smallest enclosing canonical SESE
43 cananian 1.1.2.2 * <code>Region</code>. */
44 cananian 1.3.2.2 public final Map smallestSESE;
45 cananian 1.1.2.1
46 cananian 1.1.2.5 /** Creates a <code>SESE</code> using a <code>CycleEq</code>. */
47 sportbilly 1.1.2.9 public SESE(HCode hc) {
48 cananian 1.1.2.2 // compute cycle equivalence.
49 sportbilly 1.1.2.9 CycleEq ceq = new CycleEq(hc);
50 cananian 1.1.2.2 // use cycle equivalence classes to determine canonical sese regions.
51 cananian 1.1.2.1 Map entryRegion= new HashMap();
52 cananian 1.1.2.1 Map exitRegion = new HashMap();
53 cananian 1.7 for (Object lO : ceq.cdClasses()) {
54 cananian 1.7 List l = (List) lO;
55 cananian 1.1.2.1 Object prev=null;
56 cananian 1.1.2.1 for (Iterator lit=l.listIterator(); lit.hasNext(); ) {
57 cananian 1.1.2.1 Object o = lit.next();
58 cananian 1.1.2.1 if (prev!=null) {
59 cananian 1.1.2.1 Region r = new Region(prev, o);
60 cananian 1.1.2.1 entryRegion.put(prev, r);
61 cananian 1.1.2.1 exitRegion.put(o, r);
62 cananian 1.1.2.1 }
63 cananian 1.1.2.1 prev = o;
64 cananian 1.1.2.1 }
65 cananian 1.1.2.1 }
66 cananian 1.1.2.2 // now do DFS traversal of CFG to determine nesting of regions.
67 cananian 1.1.2.2 Map workSmallSESE = new HashMap();
68 cananian 1.1.2.2 // state for DFS
69 cananian 1.1.2.2 Set visited = new HashSet(); visited.add(hc.getRootElement());
70 cananian 1.1.2.2 Stack nodeS = new Stack(); nodeS.push(hc.getRootElement());
71 cananian 1.1.2.2 Stack regionS=new Stack(); regionS.push(topLevel);
72 cananian 1.1.2.2
73 cananian 1.1.2.2 while (!nodeS.isEmpty()) {
74 cananian 1.3.2.1 assert nodeS.size()==regionS.size();
75 cananian 1.1.2.2 Object o = nodeS.pop(); // either an HCodeElement or an HCodeEdge
76 cananian 1.1.2.2 Region cR= (Region) regionS.pop(); // currentRegion.
77 cananian 1.1.2.2 // deal with region entry/exit.
78 sportbilly 1.1.2.9 if (true==(o instanceof HCodeElement)) {
79 cananian 1.1.2.4 // cR is smallest enclosing canonical SESE of o.
80 cananian 1.1.2.4 workSmallSESE.put(o, cR);
81 cananian 1.1.2.4 cR.nodes.add(o);
82 cananian 1.1.2.2 } else { // update current region.
83 cananian 1.1.2.2 // if this is found in the cycle-equivalency stuff, push/pop.
84 cananian 1.1.2.2 Region r1 = (Region) entryRegion.get(o);
85 cananian 1.1.2.2 Region r2 = (Region) exitRegion.get(o);
86 cananian 1.1.2.2 // pop up one level if we are leaving the region.
87 cananian 1.1.2.2 if (cR.equals(r1)) { cR=cR.parent; r1=null; }
88 cananian 1.1.2.2 if (cR.equals(r2)) { cR=cR.parent; r2=null; }
89 cananian 1.1.2.2 // push a level if we are entering the region.
90 cananian 1.1.2.2 if (r1!=null) { Region.link(cR, r1); cR=r1; }
91 cananian 1.1.2.2 if (r2!=null) { Region.link(cR, r2); cR=r2; }
92 cananian 1.1.2.1 }
93 cananian 1.1.2.2 // continue DFS traversal.
94 cananian 1.1.2.2 Object[] succ=null;
95 cananian 1.1.2.2 if (o instanceof HCodeElement) // Node. Push edges.
96 cananian 1.1.2.10 succ = ((harpoon.IR.Properties.CFGraphable)o).succ();
97 cananian 1.1.2.2 if (o instanceof HCodeEdge) // Edge. Push node.
98 cananian 1.1.2.2 succ = new HCodeElement[] { ((HCodeEdge)o).to() };
99 cananian 1.1.2.2 for (int i=succ.length-1; i>=0; i--)
100 cananian 1.1.2.2 if (!visited.contains(succ[i])) {
101 cananian 1.1.2.2 nodeS.push(succ[i]); regionS.push(cR);
102 cananian 1.1.2.2 visited.add(succ[i]);
103 cananian 1.1.2.2 }
104 cananian 1.1.2.2 } // END while.
105 cananian 1.3.2.1 assert nodeS.isEmpty() && regionS.isEmpty();
106 cananian 1.1.2.2 // make smallestSESE map unmodifiable.
107 cananian 1.1.2.2 smallestSESE = Collections.unmodifiableMap(workSmallSESE);
108 cananian 1.1.2.4 // make region lists unmodifiable
109 cananian 1.1.2.4 for (Iterator it = topDown(); it.hasNext(); ) {
110 cananian 1.1.2.4 Region r = (Region) it.next();
111 cananian 1.1.2.4 r.nodes = Collections.unmodifiableCollection(r.nodes);
112 cananian 1.1.2.4 }
113 cananian 1.1.2.1 }
114 cananian 1.1.2.1
115 cananian 1.1.2.2 /** Iterate through SESE regions, top-down. All top-level regions
116 cananian 1.1.2.2 * are visited first, then all children of top-level regions, then
117 cananian 1.1.2.2 * all grandchildren, then all great-grandchildren, etc. */
118 cananian 1.1.2.4 public Iterator topDown() { return iterator(true); }
119 cananian 1.1.2.4 /** Iterate through SESE regions, depth-first. */
120 cananian 1.1.2.4 public Iterator depthFirst() { return iterator(false); }
121 cananian 1.1.2.4
122 cananian 1.1.2.4 private Iterator iterator(final boolean topdown) {
123 cananian 1.1.2.7 return new UnmodifiableIterator() {
124 cananian 1.1.2.1 LinkedList ll = new LinkedList();
125 cananian 1.1.2.2 { ll.add(topLevel); }
126 cananian 1.1.2.1 public boolean hasNext() { return !ll.isEmpty(); }
127 cananian 1.1.2.1 public Object next() {
128 cananian 1.1.2.4 Region r = (Region) (topdown?ll.removeFirst():ll.removeLast());
129 cananian 1.1.2.1 ll.addAll(r.children());
130 cananian 1.1.2.1 return r;
131 cananian 1.1.2.1 }
132 cananian 1.1.2.1 };
133 cananian 1.1.2.1 }
134 cananian 1.1.2.1
135 cananian 1.1.2.1 public void print(java.io.PrintWriter pw) {
136 cananian 1.1.2.4 for (Iterator it=depthFirst(); it.hasNext(); ) {
137 cananian 1.1.2.1 Region r = (Region) it.next();
138 cananian 1.1.2.4 for (int i=0; i<r.level; i++)
139 cananian 1.1.2.4 pw.print(' ');
140 cananian 1.1.2.4 pw.print(r.toString()); // print region.
141 cananian 1.1.2.4 pw.print(" : ");
142 cananian 1.1.2.4 pw.println(r.nodes.toString()); // print members
143 cananian 1.1.2.1 }
144 cananian 1.1.2.2 }
145 cananian 1.1.2.1
146 cananian 1.1.2.11 /** <code>SESE.Region</code> represents a single-entry single-exit
147 cananian 1.1.2.11 * (SESE) Region, as computed by the <code>SESE</code> object. */
148 cananian 1.1.2.1 public static class Region {
149 cananian 1.1.2.11 /** entry edge of the region. */
150 cananian 1.1.2.11 public final Object entry;
151 cananian 1.1.2.11 /** exit edge of the region. */
152 cananian 1.1.2.11 public final Object exit;
153 cananian 1.1.2.1 // tree info.
154 cananian 1.1.2.4 int level=0;
155 cananian 1.1.2.1 Region parent=null;
156 cananian 1.1.2.1 RegionList children=null;
157 cananian 1.1.2.4 // list of nodes in this region
158 cananian 1.1.2.4 Collection nodes = new ArrayList();
159 cananian 1.1.2.1
160 cananian 1.1.2.1 Region() { // create top-level region.
161 cananian 1.1.2.1 this.entry = this.exit = null;
162 cananian 1.3.2.1 assert isTopLevel();
163 cananian 1.1.2.1 }
164 cananian 1.1.2.1 Region(Object entry, Object exit) {
165 cananian 1.1.2.1 this.entry = entry; this.exit = exit;
166 cananian 1.3.2.1 assert !isTopLevel();
167 cananian 1.1.2.1 }
168 cananian 1.1.2.1
169 cananian 1.1.2.11 /** Parent region of this one (<code>null</code> for top-level
170 cananian 1.1.2.11 * region). */
171 cananian 1.1.2.1 public Region parent() { return this.parent; }
172 cananian 1.1.2.11 /** Child regions of this one. */
173 cananian 1.1.2.1 public Set children() { return RegionList.asSet(this.children); }
174 cananian 1.1.2.11 /** Nodes in this region (and not contained in any child regions) */
175 cananian 1.1.2.4 public Collection nodes() { return this.nodes; }
176 cananian 1.1.2.1
177 cananian 1.1.2.1 boolean isTopLevel() {
178 cananian 1.1.2.1 return (this.entry==null) && (this.exit==null);
179 cananian 1.1.2.1 }
180 cananian 1.1.2.11 /** Compare two regions for equality. */
181 cananian 1.1.2.1 public boolean equals(Object o) {
182 cananian 1.1.2.8 Region r;
183 cananian 1.1.2.8 if (this==o) return true;
184 cananian 1.1.2.8 if (o==null) return false;
185 cananian 1.1.2.8 try { r=(Region)o; }
186 cananian 1.1.2.8 catch (ClassCastException e) { return false; }
187 cananian 1.1.2.8 if (isTopLevel()) return r.isTopLevel();
188 cananian 1.1.2.1 else return
189 cananian 1.1.2.8 this.entry.equals(r.entry) &&
190 cananian 1.1.2.8 this.exit.equals(r.exit);
191 cananian 1.1.2.1 }
192 cananian 1.1.2.1 public int hashCode() {
193 cananian 1.1.2.1 if (isTopLevel()) return 0;
194 cananian 1.1.2.1 else return (entry.hashCode()<<7) ^ exit.hashCode();
195 cananian 1.1.2.1 }
196 cananian 1.1.2.1 public String toString() {
197 cananian 1.1.2.1 if (isTopLevel()) return "[-toplevel-]";
198 cananian 1.1.2.1 else return "["+entry+"->"+exit+"]";
199 cananian 1.1.2.1 }
200 cananian 1.1.2.1 static void link(Region parent, Region child) {
201 cananian 1.1.2.4 child.level = 1 + parent.level;
202 cananian 1.1.2.1 child.parent = parent;
203 cananian 1.1.2.1 parent.children = new RegionList(child, parent.children);
204 cananian 1.1.2.1 }
205 cananian 1.1.2.1 }
206 cananian 1.1.2.1 static class RegionList {
207 cananian 1.1.2.1 final Region region;
208 cananian 1.1.2.1 final RegionList next;
209 cananian 1.1.2.1 final int size;
210 cananian 1.1.2.1 RegionList(Region region, RegionList next) {
211 cananian 1.1.2.1 this.region = region; this.next = next;
212 cananian 1.1.2.1 this.size = 1+((next==null)?0:next.size);
213 cananian 1.1.2.1 }
214 cananian 1.1.2.1 static Iterator elements(final RegionList rl) {
215 cananian 1.1.2.7 return new UnmodifiableIterator() {
216 cananian 1.1.2.1 RegionList rlp = rl;
217 cananian 1.1.2.1 public boolean hasNext() { return rlp!=null; }
218 cananian 1.1.2.1 public Object next() {
219 cananian 1.1.2.1 Region r = rlp.region; rlp=rlp.next; return r;
220 cananian 1.1.2.1 }
221 cananian 1.1.2.1 };
222 cananian 1.1.2.1 }
223 cananian 1.1.2.1 static Set asSet(final RegionList rl) {
224 cananian 1.1.2.1 return new AbstractSet() {
225 cananian 1.1.2.1 public boolean isEmpty() { return rl==null; }
226 cananian 1.1.2.1 public int size() { return (rl==null)?0:rl.size; }
227 cananian 1.1.2.1 public Iterator iterator() { return elements(rl); }
228 cananian 1.1.2.1 };
229 cananian 1.1.2.1 }
230 cananian 1.1.2.1 }
231 cananian 1.2 }