1 /* 2 * Copyright (c) 1983, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 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. 16 * 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 27 * SUCH DAMAGE. 28 */ 29 #include "libiberty.h" 30 #include "gprof.h" 31 #include "search_list.h" 32 #include "source.h" 33 #include "symtab.h" 34 #include "cg_arcs.h" 35 #include "cg_dfn.h" 36 #include "utils.h" 37 38 #define DFN_INCR_DEPTH (128) 39 40 typedef struct 41 { 42 Sym *sym; 43 int cycle_top; 44 } 45 DFN_Stack; 46 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 *)); 52 53 DFN_Stack *dfn_stack = NULL; 54 int dfn_maxdepth = 0; 55 int dfn_depth = 0; 56 int dfn_counter = DFN_NAN; 57 58 59 /* 60 * Is CHILD already numbered? 61 */ 62 static bfd_boolean 63 is_numbered (child) 64 Sym *child; 65 { 66 return child->cg.top_order != DFN_NAN && child->cg.top_order != DFN_BUSY; 67 } 68 69 70 /* 71 * Is CHILD already busy? 72 */ 73 static bfd_boolean 74 is_busy (child) 75 Sym *child; 76 { 77 if (child->cg.top_order == DFN_NAN) 78 { 79 return FALSE; 80 } 81 return TRUE; 82 } 83 84 85 /* 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). 90 */ 91 static void 92 find_cycle (child) 93 Sym *child; 94 { 95 Sym *head = 0; 96 Sym *tail; 97 int cycle_top; 98 int index; 99 100 for (cycle_top = dfn_depth; cycle_top > 0; --cycle_top) 101 { 102 head = dfn_stack[cycle_top].sym; 103 if (child == head) 104 { 105 break; 106 } 107 if (child->cg.cyc.head != child && child->cg.cyc.head == head) 108 { 109 break; 110 } 111 } 112 if (cycle_top <= 0) 113 { 114 fprintf (stderr, "[find_cycle] couldn't find head of cycle\n"); 115 done (1); 116 } 117 #ifdef DEBUG 118 if (debug_level & DFNDEBUG) 119 { 120 printf ("[find_cycle] dfn_depth %d cycle_top %d ", 121 dfn_depth, cycle_top); 122 if (head) 123 { 124 print_name (head); 125 } 126 else 127 { 128 printf ("<unknown>"); 129 } 130 printf ("\n"); 131 } 132 #endif 133 if (cycle_top == dfn_depth) 134 { 135 /* 136 * This is previous function, e.g. this calls itself. Sort of 137 * boring. 138 * 139 * Since we are taking out self-cycles elsewhere no need for 140 * the special case, here. 141 */ 142 DBG (DFNDEBUG, 143 printf ("[find_cycle] "); 144 print_name (child); 145 printf ("\n")); 146 } 147 else 148 { 149 /* 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 153 * into. 154 */ 155 for (tail = head; tail->cg.cyc.next; tail = tail->cg.cyc.next) 156 { 157 /* void: chase down to tail of things already glommed */ 158 DBG (DFNDEBUG, 159 printf ("[find_cycle] tail "); 160 print_name (tail); 161 printf ("\n")); 162 } 163 /* 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. 167 */ 168 if (head->cg.cyc.head != head) 169 { 170 head = head->cg.cyc.head; 171 DBG (DFNDEBUG, printf ("[find_cycle] new cyclehead "); 172 print_name (head); 173 printf ("\n")); 174 } 175 for (index = cycle_top + 1; index <= dfn_depth; ++index) 176 { 177 child = dfn_stack[index].sym; 178 if (child->cg.cyc.head == child) 179 { 180 /* 181 * Not yet glommed anywhere, glom it and fix any 182 * children it has glommed. 183 */ 184 tail->cg.cyc.next = child; 185 child->cg.cyc.head = head; 186 DBG (DFNDEBUG, printf ("[find_cycle] glomming "); 187 print_name (child); 188 printf (" onto "); 189 print_name (head); 190 printf ("\n")); 191 for (tail = child; tail->cg.cyc.next; tail = tail->cg.cyc.next) 192 { 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); 196 printf (" onto "); 197 print_name (head); 198 printf ("\n")); 199 } 200 } 201 else if (child->cg.cyc.head != head /* firewall */ ) 202 { 203 fprintf (stderr, "[find_cycle] glommed, but not to head\n"); 204 done (1); 205 } 206 } 207 } 208 } 209 210 211 /* 212 * Prepare for visiting the children of PARENT. Push a parent onto 213 * the stack and mark it busy. 214 */ 215 static void 216 pre_visit (parent) 217 Sym *parent; 218 { 219 ++dfn_depth; 220 221 if (dfn_depth >= dfn_maxdepth) 222 { 223 dfn_maxdepth += DFN_INCR_DEPTH; 224 dfn_stack = xrealloc (dfn_stack, dfn_maxdepth * sizeof *dfn_stack); 225 } 226 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); 231 print_name (parent); 232 printf ("\n")); 233 } 234 235 236 /* 237 * Done with visiting node PARENT. Pop PARENT off dfn_stack 238 * and number functions if PARENT is head of a cycle. 239 */ 240 static void 241 post_visit (parent) 242 Sym *parent; 243 { 244 Sym *member; 245 246 DBG (DFNDEBUG, printf ("[post_visit]\t%d: ", dfn_depth); 247 print_name (parent); 248 printf ("\n")); 249 /* 250 * Number functions and things in their cycles unless the function 251 * is itself part of a cycle: 252 */ 253 if (parent->cg.cyc.head == parent) 254 { 255 ++dfn_counter; 256 for (member = parent; member; member = member->cg.cyc.next) 257 { 258 member->cg.top_order = dfn_counter; 259 DBG (DFNDEBUG, printf ("[post_visit]\t\tmember "); 260 print_name (member); 261 printf ("-> cg.top_order = %d\n", dfn_counter)); 262 } 263 } 264 else 265 { 266 DBG (DFNDEBUG, printf ("[post_visit]\t\tis part of a cycle\n")); 267 } 268 --dfn_depth; 269 } 270 271 272 /* 273 * Given this PARENT, depth first number its children. 274 */ 275 void 276 cg_dfn (parent) 277 Sym *parent; 278 { 279 Arc *arc; 280 281 DBG (DFNDEBUG, printf ("[dfn] dfn( "); 282 print_name (parent); 283 printf (")\n")); 284 /* 285 * If we're already numbered, no need to look any further: 286 */ 287 if (is_numbered (parent)) 288 { 289 return; 290 } 291 /* 292 * If we're already busy, must be a cycle: 293 */ 294 if (is_busy (parent)) 295 { 296 find_cycle (parent); 297 return; 298 } 299 pre_visit (parent); 300 /* 301 * Recursively visit children: 302 */ 303 for (arc = parent->cg.children; arc; arc = arc->next_child) 304 { 305 cg_dfn (arc->child); 306 } 307 post_visit (parent); 308 } 309