1 cananian 1.1.2.7 // LoopFinder.java, created Tue Jun 15 23:15:07 1999 by bdemsky
2 bdemsky 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
3 bdemsky 1.1.2.2 // Copyright 1999 by Brian Demsky
4 bdemsky 1.1.2.2
5 bdemsky 1.1.2.1 package harpoon.Analysis.Loops;
6 bdemsky 1.1.2.1
7 bdemsky 1.1.2.1 import harpoon.Analysis.Loops.Loops;
8 cananian 1.4 import net.cscott.jutil.WorkSet;
9 bdemsky 1.1.2.1 import harpoon.Analysis.DomTree;
10 bdemsky 1.1.2.1 import harpoon.ClassFile.HCode;
11 bdemsky 1.1.2.1 import harpoon.ClassFile.HCodeEdge;
12 bdemsky 1.1.2.1 import harpoon.ClassFile.HCodeElement;
13 pnkfelix 1.1.2.10 import harpoon.IR.Properties.CFGrapher;
14 bdemsky 1.1.2.1 import harpoon.Util.Util;
15 bdemsky 1.1.2.1
16 bdemsky 1.1.2.3 import java.util.Set;
17 pnkfelix 1.1.2.13 import java.util.Stack;
18 bdemsky 1.1.2.1 import java.util.Hashtable;
19 bdemsky 1.1.2.1 import java.util.Iterator;
20 bdemsky 1.1.2.1 /**
21 bdemsky 1.1.2.1 * <code>LoopFinder</code> implements Dominator Tree Loop detection.
22 bdemsky 1.1.2.1 *
23 bdemsky 1.1.2.5 * @author Brian Demsky <bdemsky@mit.edu>
24 cananian 1.5 * @version $Id: LoopFinder.java,v 1.5 2004/02/08 03:19:41 cananian Exp $
25 bdemsky 1.1.2.1 */
26 bdemsky 1.1.2.1
27 bdemsky 1.1.2.1 public class LoopFinder implements Loops {
28 bdemsky 1.1.2.5
29 cananian 1.1.2.9 DomTree dominator;
30 bdemsky 1.1.2.1 HCode hc,lasthc;
31 bdemsky 1.1.2.1 WorkSet setofloops;
32 bdemsky 1.1.2.1 Loop root;
33 bdemsky 1.1.2.1 Loop ptr;
34 pnkfelix 1.1.2.10
35 pnkfelix 1.1.2.10 CFGrapher grapher;
36 bdemsky 1.1.2.2
37 bdemsky 1.1.2.2 /** Creates a new LoopFinder object.
38 bdemsky 1.1.2.2 * This call takes an HCode and returns a LoopFinder object
39 bdemsky 1.1.2.2 * at the root level. Only use with Objects implementing the
40 cananian 1.1.2.8 * CFGraphable interface!
41 bdemsky 1.1.2.3 *<BR> <B> Requires: </B> <code> hc </code> is a <code> HCode</code> implementing
42 cananian 1.1.2.8 * the <code> CFGraphable </code> interface.*/
43 bdemsky 1.1.2.5
44 bdemsky 1.1.2.1 public LoopFinder(HCode hc) {
45 pnkfelix 1.1.2.10 this(hc, CFGrapher.DEFAULT);
46 pnkfelix 1.1.2.10 }
47 pnkfelix 1.1.2.10
48 pnkfelix 1.1.2.10
49 pnkfelix 1.1.2.10 /** Creates a new LoopFinder object.
50 pnkfelix 1.1.2.10 * This call takes an HCode and a CFGrapher
51 pnkfelix 1.1.2.10 * and returns a LoopFinder object
52 pnkfelix 1.1.2.10 * at the root level.
53 pnkfelix 1.1.2.10 *<BR> <B> Requires: </B> <code> grapher </code> is a
54 pnkfelix 1.1.2.10 * <code>CFGrapher</code> for <code> hc </code>.*/
55 pnkfelix 1.1.2.10
56 pnkfelix 1.1.2.10 public LoopFinder(HCode hc, CFGrapher grapher) {
57 pnkfelix 1.1.2.10 this.grapher = grapher;
58 bdemsky 1.1.2.5 this.hc=hc;
59 cananian 1.1.2.9 this.dominator=new DomTree(hc, false);
60 bdemsky 1.1.2.5 analyze();
61 bdemsky 1.1.2.5 this.ptr=root;
62 bdemsky 1.1.2.1 }
63 pnkfelix 1.1.2.10
64 bdemsky 1.1.2.3 /**This method is for internal use only.
65 bdemsky 1.1.2.5 *It returns a Loopfinder object at any level,
66 bdemsky 1.1.2.5 *but it doesn't regenerate the internal tree
67 bdemsky 1.1.2.5 *so any external calls would result in garbage.*/
68 bdemsky 1.1.2.5
69 cananian 1.1.2.11 private LoopFinder(HCode hc, CFGrapher grapher, DomTree dt, Loop root, Loop ptr) {
70 bdemsky 1.1.2.5 this.lasthc=hc;
71 cananian 1.1.2.11 this.grapher=grapher;
72 bdemsky 1.1.2.5 this.hc=hc;
73 cananian 1.1.2.9 this.dominator=dt;
74 bdemsky 1.1.2.5 this.root=root;
75 bdemsky 1.1.2.5 this.ptr=ptr;
76 bdemsky 1.1.2.1 }
77 bdemsky 1.1.2.5
78 bdemsky 1.1.2.1 /*-----------------------------*/
79 bdemsky 1.1.2.5
80 bdemsky 1.1.2.3 /** This method returns the Root level loop for a given <code>HCode</code>.
81 bdemsky 1.1.2.5 * Does the same thing as the constructor call, but for an existing
82 bdemsky 1.1.2.5 * LoopFinder object.*/
83 bdemsky 1.1.2.5
84 bdemsky 1.1.2.4 public Loops getRootloop(HCode hc) {
85 bdemsky 1.1.2.1 this.hc=hc;
86 bdemsky 1.1.2.1 analyze();
87 cananian 1.1.2.11 return new LoopFinder(hc,grapher,dominator,root,root);
88 bdemsky 1.1.2.1 }
89 bdemsky 1.1.2.5
90 bdemsky 1.1.2.3 /** This method returns the entry point of the loop.
91 bdemsky 1.1.2.2 * For the natural loops we consider, that is simply the header.
92 cananian 1.1.2.11 * It returns a <code>Set</code> of <code>HCodeElement</code>s.*/
93 bdemsky 1.1.2.5
94 bdemsky 1.1.2.4 public Set loopEntrances() {
95 cananian 1.1.2.12 WorkSet entries=new WorkSet();
96 bdemsky 1.1.2.16 analyze();
97 bdemsky 1.1.2.15 entries.push(ptr.header);
98 cananian 1.1.2.12 return entries;
99 cananian 1.1.2.12 }
100 bdemsky 1.1.2.16
101 cananian 1.1.2.12 public Set loopEntranceEdges() {
102 bdemsky 1.1.2.1 analyze();
103 cananian 1.1.2.12 WorkSet A=new WorkSet();
104 cananian 1.5 for (Object edgeO : grapher.predC(ptr.header)) {
105 cananian 1.5 HCodeEdge edge = (HCodeEdge) edgeO;
106 cananian 1.3 if (!ptr.entries.contains(edge.from()))
107 cananian 1.3 A.push(edge);
108 cananian 1.3 }
109 cananian 1.1.2.12 return A;
110 cananian 1.1.2.12 }
111 cananian 1.1.2.12 /** Returns a <code>Set</code> of all <code>HCodeElement</code>s
112 cananian 1.1.2.12 * in the loop which have an edge exiting the loop. */
113 cananian 1.1.2.12 public Set loopExits() {
114 bdemsky 1.1.2.1 WorkSet entries=new WorkSet();
115 cananian 1.5 for (Object hceO : loopExitEdges()) {
116 cananian 1.5 HCodeEdge hce = (HCodeEdge) hceO;
117 cananian 1.1.2.12 entries.push(hce.from());
118 cananian 1.1.2.12 }
119 bdemsky 1.1.2.1 return entries;
120 bdemsky 1.1.2.1 }
121 cananian 1.1.2.12 /** Returns a <code>Set</code> of all <code>HCodeEdge</code>s
122 cananian 1.1.2.12 * exiting the loop. */
123 cananian 1.1.2.12 public Set loopExitEdges() {
124 bdemsky 1.1.2.5 analyze();
125 bdemsky 1.1.2.5 WorkSet A=new WorkSet();
126 cananian 1.5 for (Object hceO : ptr.entries) {
127 cananian 1.5 HCodeElement hce = (HCodeElement) hceO;
128 cananian 1.5 for (Object edgeO : grapher.succC(hce)) {
129 cananian 1.5 HCodeEdge edge = (HCodeEdge) edgeO;
130 cananian 1.3 if (!ptr.entries.contains(edge.to()))
131 cananian 1.3 A.push(edge);
132 cananian 1.3 }
133 bdemsky 1.1.2.5 }
134 bdemsky 1.1.2.5 return A;
135 bdemsky 1.1.2.1 }
136 bdemsky 1.1.2.5
137 cananian 1.1.2.12 /** This method finds all of the backedges of the loop.
138 cananian 1.1.2.12 * Since we combine natural loops with the same header, this
139 cananian 1.1.2.12 * can be greater than one. This method returns a <code>Set</code> of
140 cananian 1.1.2.11 * <code>HCodeEdge</code>s.*/
141 cananian 1.1.2.12
142 cananian 1.1.2.12 public Set loopBackEdges() {
143 bdemsky 1.1.2.5 analyze();
144 bdemsky 1.1.2.5 WorkSet A=new WorkSet();
145 cananian 1.5 for (Object hceO : ptr.entries) {
146 cananian 1.5 HCodeElement hce = (HCodeElement) hceO;
147 cananian 1.5 for (Object edgeO : grapher.succC(hce)) {
148 cananian 1.5 HCodeEdge edge = (HCodeEdge) edgeO;
149 cananian 1.3 if (edge.to()==ptr.header)
150 cananian 1.3 A.push(edge);
151 cananian 1.3 }
152 bdemsky 1.1.2.5 }
153 bdemsky 1.1.2.5 return A;
154 bdemsky 1.1.2.1 }
155 bdemsky 1.1.2.5
156 bdemsky 1.1.2.3 /**Returns a <code>Set</code> with all of the <code>HCodeElement</code>s of the loop and
157 bdemsky 1.1.2.5 *loops included entirely within this loop. */
158 bdemsky 1.1.2.5
159 cananian 1.1.2.12 public Set loopIncElements() {
160 bdemsky 1.1.2.5 analyze();
161 bdemsky 1.1.2.5 WorkSet A=new WorkSet(ptr.entries);
162 bdemsky 1.1.2.5 return A;
163 bdemsky 1.1.2.1 }
164 bdemsky 1.1.2.5
165 bdemsky 1.1.2.3 /** Returns all of the <code>HCodeElement</code>s of this loop that aren't in a nested
166 bdemsky 1.1.2.3 * loop. This returns a <code>Set</code> of <code>HCodeElement</code>s.*/
167 bdemsky 1.1.2.5
168 cananian 1.1.2.12 public Set loopExcElements() {
169 bdemsky 1.1.2.5 analyze();
170 bdemsky 1.1.2.5 WorkSet A=new WorkSet(ptr.entries);
171 bdemsky 1.1.2.5 WorkSet todo=new WorkSet();
172 bdemsky 1.1.2.5 //Get the children
173 bdemsky 1.1.2.5 Iterator iterat=ptr.children.iterator();
174 bdemsky 1.1.2.5 while (iterat.hasNext())
175 bdemsky 1.1.2.5 todo.push(iterat.next());
176 bdemsky 1.1.2.5 //Go down the tree
177 bdemsky 1.1.2.5 while(!todo.isEmpty()) {
178 bdemsky 1.1.2.5 Loop currptr=(Loop)todo.pop();
179 bdemsky 1.1.2.5 Iterator iterate=currptr.children.iterator();
180 bdemsky 1.1.2.5 while (iterate.hasNext()) {
181 bdemsky 1.1.2.5 todo.push(iterate.next());
182 bdemsky 1.1.2.5 }
183 bdemsky 1.1.2.5 iterate=currptr.entries.iterator();
184 bdemsky 1.1.2.5 while (iterate.hasNext())
185 bdemsky 1.1.2.5 A.remove(iterate.next());
186 bdemsky 1.1.2.5 }
187 bdemsky 1.1.2.5 return A;
188 bdemsky 1.1.2.1 }
189 bdemsky 1.1.2.5
190 bdemsky 1.1.2.3 /** Returns a <code>Set</code> of loops that are nested inside of this loop.*/
191 bdemsky 1.1.2.5
192 bdemsky 1.1.2.4 public Set nestedLoops() {
193 bdemsky 1.1.2.5 analyze();
194 bdemsky 1.1.2.5 WorkSet L=new WorkSet();
195 bdemsky 1.1.2.5 Iterator iterate=ptr.children.iterator();
196 bdemsky 1.1.2.5 while (iterate.hasNext())
197 cananian 1.1.2.11 L.push(new LoopFinder(hc,grapher,dominator,root,(Loop) iterate.next()));
198 bdemsky 1.1.2.5 return L;
199 bdemsky 1.1.2.1 }
200 bdemsky 1.1.2.5
201 bdemsky 1.1.2.3 /** Returns the <code>Loops</code> that contains this loop.
202 bdemsky 1.1.2.2 * If this is the top level loop, this call returns a null pointer.*/
203 bdemsky 1.1.2.5
204 bdemsky 1.1.2.4 public Loops parentLoop() {
205 bdemsky 1.1.2.5 analyze();
206 bdemsky 1.1.2.5 if (ptr.parent!=null)
207 cananian 1.1.2.11 return new LoopFinder(hc,grapher,dominator,root,ptr.parent);
208 bdemsky 1.1.2.5 else return null;
209 bdemsky 1.1.2.1 }
210 bdemsky 1.1.2.5
211 bdemsky 1.1.2.1 /*---------------------------*/
212 bdemsky 1.1.2.1 // public information accessor methods.
213 bdemsky 1.1.2.5
214 bdemsky 1.1.2.1 /*---------------------------*/
215 bdemsky 1.1.2.1 // Analysis code.
216 bdemsky 1.1.2.5
217 bdemsky 1.1.2.5
218 bdemsky 1.1.2.1 /** Main analysis method. */
219 bdemsky 1.1.2.5
220 bdemsky 1.1.2.1 void analyze() {
221 bdemsky 1.1.2.5 //Have we analyzed this set before?
222 bdemsky 1.1.2.5 //If so, don't do it again!!!
223 bdemsky 1.1.2.5 if (hc!=lasthc) {
224 bdemsky 1.1.2.5
225 bdemsky 1.1.2.5 //Did the caller hand us a bogus object?
226 bdemsky 1.1.2.5 //If so, throw it something
227 bdemsky 1.1.2.5
228 bdemsky 1.1.2.5 lasthc=hc;
229 bdemsky 1.1.2.5
230 bdemsky 1.1.2.5 //Set up the top level loop, so we can fill it with HCodeElements
231 bdemsky 1.1.2.5 //as we go along
232 bdemsky 1.1.2.5 root=new Loop();
233 bdemsky 1.1.2.5 root.header=hc.getRootElement();
234 bdemsky 1.1.2.5
235 bdemsky 1.1.2.5 //Set up a WorkSet for storing loops before we build the
236 bdemsky 1.1.2.5 //nested loop tree
237 bdemsky 1.1.2.5 setofloops=new WorkSet();
238 bdemsky 1.1.2.5
239 bdemsky 1.1.2.5 //Find loops
240 bdemsky 1.1.2.5 findloopheaders(hc.getRootElement());
241 bdemsky 1.1.2.5
242 bdemsky 1.1.2.5 //Build the nested loop tree
243 bdemsky 1.1.2.5 buildtree();
244 bdemsky 1.1.2.5 }
245 bdemsky 1.1.2.1 }
246 bdemsky 1.1.2.1 // end analysis.
247 bdemsky 1.1.2.5
248 bdemsky 1.1.2.1 void buildtree() {
249 bdemsky 1.1.2.5 //go through set of generated loops
250 bdemsky 1.1.2.5 while(!setofloops.isEmpty()) {
251 bdemsky 1.1.2.5
252 bdemsky 1.1.2.5 //Pull out one
253 cananian 1.4 Loop A=(Loop) setofloops.removeLast();
254 bdemsky 1.1.2.5
255 bdemsky 1.1.2.5 //Add it to the tree, complain if oddness
256 bdemsky 1.1.2.5 if (addnode(A, root)!=1)
257 bdemsky 1.1.2.5 System.out.println("Evil Error in LoopFinder while building tree.");
258 bdemsky 1.1.2.5 }
259 bdemsky 1.1.2.1 }
260 bdemsky 1.1.2.1
261 bdemsky 1.1.2.2 //Adds a node to the tree...Its recursive
262 bdemsky 1.1.2.5
263 bdemsky 1.1.2.1 int addnode(Loop A, Loop treenode) {
264 bdemsky 1.1.2.2
265 bdemsky 1.1.2.5 //Only need to go deeper if the header is contained in this loop
266 bdemsky 1.1.2.5 if (treenode.entries.contains(A.header))
267 bdemsky 1.1.2.5
268 bdemsky 1.1.2.5 //Do we share headers?
269 bdemsky 1.1.2.5 if (treenode.header!=A.header) {
270 bdemsky 1.1.2.5
271 bdemsky 1.1.2.5 //No... Loop through our children to see if they want this
272 bdemsky 1.1.2.5 //node.
273 bdemsky 1.1.2.5
274 bdemsky 1.1.2.5 //Use integers for tri-state:
275 bdemsky 1.1.2.5 //0=not stored here, 1=stored and everything is good
276 bdemsky 1.1.2.5 //2=combined 2 natural loops with same header...need cleanup
277 bdemsky 1.1.2.5
278 bdemsky 1.1.2.5 int stored=0;
279 bdemsky 1.1.2.5 Iterator iterate=treenode.children.iterator();
280 bdemsky 1.1.2.5 Loop temp=new Loop();
281 bdemsky 1.1.2.5 while (iterate.hasNext()) {
282 bdemsky 1.1.2.5 temp=(Loop) iterate.next();
283 bdemsky 1.1.2.5 stored=addnode(A,temp);
284 bdemsky 1.1.2.5 if (stored!=0) break;
285 bdemsky 1.1.2.5 }
286 bdemsky 1.1.2.5
287 bdemsky 1.1.2.5 //See what our children did for us
288 bdemsky 1.1.2.5
289 bdemsky 1.1.2.5 if (stored==0) {
290 bdemsky 1.1.2.5 //We get a new child...
291 bdemsky 1.1.2.5 treenode.children.push(A);
292 bdemsky 1.1.2.5 temp=A;
293 bdemsky 1.1.2.5 }
294 bdemsky 1.1.2.5
295 bdemsky 1.1.2.5 //Need to do cleanup for case 0 or 2
296 bdemsky 1.1.2.5 //temp points to the new child
297 bdemsky 1.1.2.5
298 bdemsky 1.1.2.5 if (stored!=1) {
299 bdemsky 1.1.2.5
300 bdemsky 1.1.2.5 //Have to make sure that none of the nodes under this one
301 bdemsky 1.1.2.5 //are children of the new node
302 bdemsky 1.1.2.5
303 bdemsky 1.1.2.5 Iterator iterate2=treenode.children.iterator();
304 bdemsky 1.1.2.5 temp.parent=treenode;
305 bdemsky 1.1.2.5
306 bdemsky 1.1.2.5 //Loop through the children
307 bdemsky 1.1.2.5 while (iterate2.hasNext()) {
308 bdemsky 1.1.2.5 Loop temp2=(Loop)iterate2.next();
309 bdemsky 1.1.2.5
310 bdemsky 1.1.2.5 //Don't look at the new node...otherwise we will create
311 bdemsky 1.1.2.5 //a unreachable subtree
312 bdemsky 1.1.2.5
313 bdemsky 1.1.2.5 if (temp2!=temp)
314 bdemsky 1.1.2.5 //If the new node has a childs header
315 bdemsky 1.1.2.5 //give the child up to it...
316 bdemsky 1.1.2.5
317 bdemsky 1.1.2.5 if (temp.entries.contains(temp2.header)) {
318 bdemsky 1.1.2.5 temp.children.push(temp2);
319 bdemsky 1.1.2.5 iterate2.remove();
320 bdemsky 1.1.2.5 }
321 bdemsky 1.1.2.5 }
322 bdemsky 1.1.2.5 }
323 bdemsky 1.1.2.5
324 bdemsky 1.1.2.5 //We fixed everything...let our parents know
325 bdemsky 1.1.2.5 return 1;
326 bdemsky 1.1.2.5 } else {
327 bdemsky 1.1.2.5 //need to combine loops
328 bdemsky 1.1.2.5 while (!A.entries.isEmpty()) {
329 cananian 1.4 treenode.entries.push(A.entries.removeLast());
330 bdemsky 1.1.2.5 }
331 bdemsky 1.1.2.5 //let the previous caller know that they have stuff todo
332 bdemsky 1.1.2.5 return 2;
333 bdemsky 1.1.2.5 }
334 bdemsky 1.1.2.5 //We aren't adopting the new node
335 bdemsky 1.1.2.5 else return 0;
336 bdemsky 1.1.2.1 }
337 bdemsky 1.1.2.1
338 pnkfelix 1.1.2.13 void findloopheaders(HCodeElement current_nodeOrig) {
339 pnkfelix 1.1.2.13 Stack stk = new Stack();
340 pnkfelix 1.1.2.13 stk.push( current_nodeOrig );
341 pnkfelix 1.1.2.13 while( ! stk.isEmpty() ){
342 pnkfelix 1.1.2.13 HCodeElement current_node = (HCodeElement) stk.pop();
343 pnkfelix 1.1.2.13 //look at the current node
344 pnkfelix 1.1.2.13 visit(current_node);
345 pnkfelix 1.1.2.13
346 pnkfelix 1.1.2.13 //add it to the all inclusive root loop
347 pnkfelix 1.1.2.13 root.entries.push(current_node);
348 pnkfelix 1.1.2.13
349 pnkfelix 1.1.2.13 //See if those we dominate are backedges
350 pnkfelix 1.1.2.13 HCodeElement[] children=dominator.children(current_node);
351 pnkfelix 1.1.2.13 for (int i=0;i<children.length;i++)
352 pnkfelix 1.1.2.13 stk.push( children[i] );
353 pnkfelix 1.1.2.13 }
354 bdemsky 1.1.2.1 }
355 bdemsky 1.1.2.1
356 bdemsky 1.1.2.5 void visit(HCodeElement q) {
357 bdemsky 1.1.2.5 Loop A=new Loop();
358 bdemsky 1.1.2.5 WorkSet B=new WorkSet();
359 bdemsky 1.1.2.5
360 bdemsky 1.1.2.5 //Loop through all of our outgoing edges
361 cananian 1.5 for (Object succ_qO : grapher.succC(q)) {
362 cananian 1.5 HCodeEdge succ_q = (HCodeEdge) succ_qO;
363 bdemsky 1.1.2.5 HCodeElement temp=q;
364 bdemsky 1.1.2.5
365 bdemsky 1.1.2.5 //Go up the dominator tree until
366 bdemsky 1.1.2.5 //we hit the root element or we
367 bdemsky 1.1.2.5 //find the node we jump back too
368 bdemsky 1.1.2.5 while ((temp!=(hc.getRootElement()))&&
369 cananian 1.3 (succ_q.to()!=temp)) {
370 cananian 1.1.2.9 temp=dominator.idom(temp);
371 bdemsky 1.1.2.5 }
372 bdemsky 1.1.2.5
373 bdemsky 1.1.2.5 //If we found the node we jumped back to
374 bdemsky 1.1.2.5 //then build loop
375 bdemsky 1.1.2.5
376 cananian 1.3 if (succ_q.to()==temp) {
377 bdemsky 1.1.2.5
378 bdemsky 1.1.2.5 //found a loop
379 bdemsky 1.1.2.5 A.entries.push(temp); //Push the header
380 bdemsky 1.1.2.5 A.header=temp;
381 bdemsky 1.1.2.5 B.push(q); //Put the backedge in the todo list
382 bdemsky 1.1.2.5
383 bdemsky 1.1.2.5 //Starting with the backedge, work on the incoming edges
384 bdemsky 1.1.2.5 //until we get back to the loop header...
385 bdemsky 1.1.2.5 //Then we have the entire natural loop
386 bdemsky 1.1.2.5
387 bdemsky 1.1.2.5 while(!B.isEmpty()) {
388 cananian 1.4 HCodeElement newnode=(HCodeElement)B.removeLast();
389 bdemsky 1.1.2.5
390 bdemsky 1.1.2.5 //Add all of the new incoming edges that we haven't already
391 bdemsky 1.1.2.5 //visited
392 cananian 1.5 for (Object pred_newnodeO : grapher.predC(newnode)) {
393 cananian 1.5 HCodeEdge pred_newnode = (HCodeEdge) pred_newnodeO;
394 cananian 1.3 if (!A.entries.contains(pred_newnode.from()))
395 cananian 1.3 B.push(pred_newnode.from());
396 bdemsky 1.1.2.5 }
397 bdemsky 1.1.2.5
398 bdemsky 1.1.2.5 //push the new node on our list of nodes in the loop
399 bdemsky 1.1.2.5 A.entries.push(newnode);
400 bdemsky 1.1.2.5 }
401 bdemsky 1.1.2.2
402 bdemsky 1.1.2.5 //save our new loop
403 bdemsky 1.1.2.5 setofloops.push(A);
404 bdemsky 1.1.2.1 }
405 bdemsky 1.1.2.5 }
406 bdemsky 1.1.2.5 }
407 bdemsky 1.1.2.1
408 bdemsky 1.1.2.5 //Structure for building internal trees...
409 bdemsky 1.1.2.5
410 bdemsky 1.1.2.5 class Loop {
411 bdemsky 1.1.2.5 public WorkSet entries=new WorkSet();
412 bdemsky 1.1.2.1 public HCodeElement header;
413 bdemsky 1.1.2.5 //Elements of the WorkSet of children are
414 bdemsky 1.1.2.5 //of the type Loop
415 bdemsky 1.1.2.5 public WorkSet children=new WorkSet();
416 bdemsky 1.1.2.5 public Loop parent;
417 bdemsky 1.1.2.5 }
418 cananian 1.2 }