2 * Copyright (c) 1983, 1993
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 #include "libiberty.h"
31 #include "search_list.h"
38 #define DFN_INCR_DEPTH (128)
47 static bfd_boolean is_numbered
PARAMS ((Sym
*));
48 static bfd_boolean is_busy
PARAMS ((Sym
*));
49 static void find_cycle
PARAMS ((Sym
*));
50 static void pre_visit
PARAMS ((Sym
*));
51 static void post_visit
PARAMS ((Sym
*));
53 DFN_Stack
*dfn_stack
= NULL
;
56 int dfn_counter
= DFN_NAN
;
60 * Is CHILD already numbered?
66 return child
->cg
.top_order
!= DFN_NAN
&& child
->cg
.top_order
!= DFN_BUSY
;
71 * Is CHILD already busy?
77 if (child
->cg
.top_order
== DFN_NAN
)
86 * CHILD is part of a cycle. Find the top caller into this cycle
87 * that is not part of the cycle and make all functions in cycle
88 * members of that cycle (top caller == caller with smallest
89 * depth-first number).
100 for (cycle_top
= dfn_depth
; cycle_top
> 0; --cycle_top
)
102 head
= dfn_stack
[cycle_top
].sym
;
107 if (child
->cg
.cyc
.head
!= child
&& child
->cg
.cyc
.head
== head
)
114 fprintf (stderr
, "[find_cycle] couldn't find head of cycle\n");
118 if (debug_level
& DFNDEBUG
)
120 printf ("[find_cycle] dfn_depth %d cycle_top %d ",
121 dfn_depth
, cycle_top
);
128 printf ("<unknown>");
133 if (cycle_top
== dfn_depth
)
136 * This is previous function, e.g. this calls itself. Sort of
139 * Since we are taking out self-cycles elsewhere no need for
140 * the special case, here.
143 printf ("[find_cycle] ");
150 * Glom intervening functions that aren't already glommed into
151 * this cycle. Things have been glommed when their cyclehead
152 * field points to the head of the cycle they are glommed
155 for (tail
= head
; tail
->cg
.cyc
.next
; tail
= tail
->cg
.cyc
.next
)
157 /* void: chase down to tail of things already glommed */
159 printf ("[find_cycle] tail ");
164 * If what we think is the top of the cycle has a cyclehead
165 * field, then it's not really the head of the cycle, which is
166 * really what we want.
168 if (head
->cg
.cyc
.head
!= head
)
170 head
= head
->cg
.cyc
.head
;
171 DBG (DFNDEBUG
, printf ("[find_cycle] new cyclehead ");
175 for (index
= cycle_top
+ 1; index
<= dfn_depth
; ++index
)
177 child
= dfn_stack
[index
].sym
;
178 if (child
->cg
.cyc
.head
== child
)
181 * Not yet glommed anywhere, glom it and fix any
182 * children it has glommed.
184 tail
->cg
.cyc
.next
= child
;
185 child
->cg
.cyc
.head
= head
;
186 DBG (DFNDEBUG
, printf ("[find_cycle] glomming ");
191 for (tail
= child
; tail
->cg
.cyc
.next
; tail
= tail
->cg
.cyc
.next
)
193 tail
->cg
.cyc
.next
->cg
.cyc
.head
= head
;
194 DBG (DFNDEBUG
, printf ("[find_cycle] and its tail ");
195 print_name (tail
->cg
.cyc
.next
);
201 else if (child
->cg
.cyc
.head
!= head
/* firewall */ )
203 fprintf (stderr
, "[find_cycle] glommed, but not to head\n");
212 * Prepare for visiting the children of PARENT. Push a parent onto
213 * the stack and mark it busy.
221 if (dfn_depth
>= dfn_maxdepth
)
223 dfn_maxdepth
+= DFN_INCR_DEPTH
;
224 dfn_stack
= xrealloc (dfn_stack
, dfn_maxdepth
* sizeof *dfn_stack
);
227 dfn_stack
[dfn_depth
].sym
= parent
;
228 dfn_stack
[dfn_depth
].cycle_top
= dfn_depth
;
229 parent
->cg
.top_order
= DFN_BUSY
;
230 DBG (DFNDEBUG
, printf ("[pre_visit]\t\t%d:", dfn_depth
);
237 * Done with visiting node PARENT. Pop PARENT off dfn_stack
238 * and number functions if PARENT is head of a cycle.
246 DBG (DFNDEBUG
, printf ("[post_visit]\t%d: ", dfn_depth
);
250 * Number functions and things in their cycles unless the function
251 * is itself part of a cycle:
253 if (parent
->cg
.cyc
.head
== parent
)
256 for (member
= parent
; member
; member
= member
->cg
.cyc
.next
)
258 member
->cg
.top_order
= dfn_counter
;
259 DBG (DFNDEBUG
, printf ("[post_visit]\t\tmember ");
261 printf ("-> cg.top_order = %d\n", dfn_counter
));
266 DBG (DFNDEBUG
, printf ("[post_visit]\t\tis part of a cycle\n"));
273 * Given this PARENT, depth first number its children.
281 DBG (DFNDEBUG
, printf ("[dfn] dfn( ");
285 * If we're already numbered, no need to look any further:
287 if (is_numbered (parent
))
292 * If we're already busy, must be a cycle:
294 if (is_busy (parent
))
301 * Recursively visit children:
303 for (arc
= parent
->cg
.children
; arc
; arc
= arc
->next_child
)
This page took 0.035022 seconds and 4 git commands to generate.