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
30 #include "libiberty.h"
31 #include "search_list.h"
38 #define DFN_INCR_DEPTH (128)
47 static bfd_boolean
is_numbered (Sym
*);
48 static bfd_boolean
is_busy (Sym
*);
49 static void find_cycle (Sym
*);
50 static void pre_visit (Sym
*);
51 static void post_visit (Sym
*);
53 DFN_Stack
*dfn_stack
= NULL
;
56 int dfn_counter
= DFN_NAN
;
60 * Is CHILD already numbered?
63 is_numbered (Sym
*child
)
65 return child
->cg
.top_order
!= DFN_NAN
&& child
->cg
.top_order
!= DFN_BUSY
;
70 * Is CHILD already busy?
75 if (child
->cg
.top_order
== DFN_NAN
)
84 * CHILD is part of a cycle. Find the top caller into this cycle
85 * that is not part of the cycle and make all functions in cycle
86 * members of that cycle (top caller == caller with smallest
87 * depth-first number).
90 find_cycle (Sym
*child
)
97 for (cycle_top
= dfn_depth
; cycle_top
> 0; --cycle_top
)
99 head
= dfn_stack
[cycle_top
].sym
;
104 if (child
->cg
.cyc
.head
!= child
&& child
->cg
.cyc
.head
== head
)
111 fprintf (stderr
, "[find_cycle] couldn't find head of cycle\n");
115 if (debug_level
& DFNDEBUG
)
117 printf ("[find_cycle] dfn_depth %d cycle_top %d ",
118 dfn_depth
, cycle_top
);
125 printf ("<unknown>");
130 if (cycle_top
== dfn_depth
)
133 * This is previous function, e.g. this calls itself. Sort of
136 * Since we are taking out self-cycles elsewhere no need for
137 * the special case, here.
140 printf ("[find_cycle] ");
147 * Glom intervening functions that aren't already glommed into
148 * this cycle. Things have been glommed when their cyclehead
149 * field points to the head of the cycle they are glommed
152 for (tail
= head
; tail
->cg
.cyc
.next
; tail
= tail
->cg
.cyc
.next
)
154 /* void: chase down to tail of things already glommed */
156 printf ("[find_cycle] tail ");
161 * If what we think is the top of the cycle has a cyclehead
162 * field, then it's not really the head of the cycle, which is
163 * really what we want.
165 if (head
->cg
.cyc
.head
!= head
)
167 head
= head
->cg
.cyc
.head
;
168 DBG (DFNDEBUG
, printf ("[find_cycle] new cyclehead ");
172 for (cycle_index
= cycle_top
+ 1; cycle_index
<= dfn_depth
; ++cycle_index
)
174 child
= dfn_stack
[cycle_index
].sym
;
175 if (child
->cg
.cyc
.head
== child
)
178 * Not yet glommed anywhere, glom it and fix any
179 * children it has glommed.
181 tail
->cg
.cyc
.next
= child
;
182 child
->cg
.cyc
.head
= head
;
183 DBG (DFNDEBUG
, printf ("[find_cycle] glomming ");
188 for (tail
= child
; tail
->cg
.cyc
.next
; tail
= tail
->cg
.cyc
.next
)
190 tail
->cg
.cyc
.next
->cg
.cyc
.head
= head
;
191 DBG (DFNDEBUG
, printf ("[find_cycle] and its tail ");
192 print_name (tail
->cg
.cyc
.next
);
198 else if (child
->cg
.cyc
.head
!= head
/* firewall */ )
200 fprintf (stderr
, "[find_cycle] glommed, but not to head\n");
209 * Prepare for visiting the children of PARENT. Push a parent onto
210 * the stack and mark it busy.
213 pre_visit (Sym
*parent
)
217 if (dfn_depth
>= dfn_maxdepth
)
219 dfn_maxdepth
+= DFN_INCR_DEPTH
;
220 dfn_stack
= (DFN_Stack
*) xrealloc (dfn_stack
,
221 dfn_maxdepth
* sizeof *dfn_stack
);
224 dfn_stack
[dfn_depth
].sym
= parent
;
225 dfn_stack
[dfn_depth
].cycle_top
= dfn_depth
;
226 parent
->cg
.top_order
= DFN_BUSY
;
227 DBG (DFNDEBUG
, printf ("[pre_visit]\t\t%d:", dfn_depth
);
234 * Done with visiting node PARENT. Pop PARENT off dfn_stack
235 * and number functions if PARENT is head of a cycle.
238 post_visit (Sym
*parent
)
242 DBG (DFNDEBUG
, printf ("[post_visit]\t%d: ", dfn_depth
);
246 * Number functions and things in their cycles unless the function
247 * is itself part of a cycle:
249 if (parent
->cg
.cyc
.head
== parent
)
252 for (member
= parent
; member
; member
= member
->cg
.cyc
.next
)
254 member
->cg
.top_order
= dfn_counter
;
255 DBG (DFNDEBUG
, printf ("[post_visit]\t\tmember ");
257 printf ("-> cg.top_order = %d\n", dfn_counter
));
262 DBG (DFNDEBUG
, printf ("[post_visit]\t\tis part of a cycle\n"));
269 * Given this PARENT, depth first number its children.
276 DBG (DFNDEBUG
, printf ("[dfn] dfn( ");
280 * If we're already numbered, no need to look any further:
282 if (is_numbered (parent
))
287 * If we're already busy, must be a cycle:
289 if (is_busy (parent
))
296 * Recursively visit children:
298 for (arc
= parent
->cg
.children
; arc
; arc
= arc
->next_child
)
This page took 0.03525 seconds and 4 git commands to generate.