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