1 /* 2 * Copyright (c) 1983 Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms are permitted 6 * provided that the above copyright notice and this paragraph are 7 * duplicated in all such forms and that any documentation, 8 * advertising materials, and other materials related to such 9 * distribution and use acknowledge that the software was developed 10 * by the University of California, Berkeley. The name of the 11 * University may not be used to endorse or promote products derived 12 * from this software without specific prior written permission. 13 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 14 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 15 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. 16 */ 17 18 #ifndef lint 19 static char sccsid[] = "@(#)dfn.c 5.3 (Berkeley) 06/29/88"; 20 #endif /* not lint */ 21 22 #include <stdio.h> 23 #include "gprof.h" 24 25 #define DFN_DEPTH 100 26 struct dfnstruct { 27 nltype *nlentryp; 28 int cycletop; 29 }; 30 typedef struct dfnstruct dfntype; 31 32 dfntype dfn_stack[ DFN_DEPTH ]; 33 int dfn_depth = 0; 34 35 int dfn_counter = DFN_NAN; 36 37 /* 38 * given this parent, depth first number its children. 39 */ 40 dfn( parentp ) 41 nltype *parentp; 42 { 43 arctype *arcp; 44 45 # ifdef DEBUG 46 if ( debug & DFNDEBUG ) { 47 printf( "[dfn] dfn(" ); 48 printname( parentp ); 49 printf( ")\n" ); 50 } 51 # endif DEBUG 52 /* 53 * if we're already numbered, no need to look any furthur. 54 */ 55 if ( dfn_numbered( parentp ) ) { 56 return; 57 } 58 /* 59 * if we're already busy, must be a cycle 60 */ 61 if ( dfn_busy( parentp ) ) { 62 dfn_findcycle( parentp ); 63 return; 64 } 65 /* 66 * visit yourself before your children 67 */ 68 dfn_pre_visit( parentp ); 69 /* 70 * visit children 71 */ 72 for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 73 dfn( arcp -> arc_childp ); 74 } 75 /* 76 * visit yourself after your children 77 */ 78 dfn_post_visit( parentp ); 79 } 80 81 /* 82 * push a parent onto the stack and mark it busy 83 */ 84 dfn_pre_visit( parentp ) 85 nltype *parentp; 86 { 87 88 dfn_depth += 1; 89 if ( dfn_depth >= DFN_DEPTH ) { 90 fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" ); 91 exit( 1 ); 92 } 93 dfn_stack[ dfn_depth ].nlentryp = parentp; 94 dfn_stack[ dfn_depth ].cycletop = dfn_depth; 95 parentp -> toporder = DFN_BUSY; 96 # ifdef DEBUG 97 if ( debug & DFNDEBUG ) { 98 printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth ); 99 printname( parentp ); 100 printf( "\n" ); 101 } 102 # endif DEBUG 103 } 104 105 /* 106 * are we already numbered? 107 */ 108 bool 109 dfn_numbered( childp ) 110 nltype *childp; 111 { 112 113 return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY ); 114 } 115 116 /* 117 * are we already busy? 118 */ 119 bool 120 dfn_busy( childp ) 121 nltype *childp; 122 { 123 124 if ( childp -> toporder == DFN_NAN ) { 125 return FALSE; 126 } 127 return TRUE; 128 } 129 130 /* 131 * MISSING: an explanation 132 */ 133 dfn_findcycle( childp ) 134 nltype *childp; 135 { 136 int cycletop; 137 nltype *cycleheadp; 138 nltype *tailp; 139 int index; 140 141 for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) { 142 cycleheadp = dfn_stack[ cycletop ].nlentryp; 143 if ( childp == cycleheadp ) { 144 break; 145 } 146 if ( childp -> cyclehead != childp && 147 childp -> cyclehead == cycleheadp ) { 148 break; 149 } 150 } 151 if ( cycletop <= 0 ) { 152 fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" ); 153 exit( 1 ); 154 } 155 # ifdef DEBUG 156 if ( debug & DFNDEBUG ) { 157 printf( "[dfn_findcycle] dfn_depth %d cycletop %d " , 158 dfn_depth , cycletop ); 159 printname( cycleheadp ); 160 printf( "\n" ); 161 } 162 # endif DEBUG 163 if ( cycletop == dfn_depth ) { 164 /* 165 * this is previous function, e.g. this calls itself 166 * sort of boring 167 */ 168 dfn_self_cycle( childp ); 169 } else { 170 /* 171 * glom intervening functions that aren't already 172 * glommed into this cycle. 173 * things have been glommed when their cyclehead field 174 * points to the head of the cycle they are glommed into. 175 */ 176 for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) { 177 /* void: chase down to tail of things already glommed */ 178 # ifdef DEBUG 179 if ( debug & DFNDEBUG ) { 180 printf( "[dfn_findcycle] tail " ); 181 printname( tailp ); 182 printf( "\n" ); 183 } 184 # endif DEBUG 185 } 186 /* 187 * if what we think is the top of the cycle 188 * has a cyclehead field, then it's not really the 189 * head of the cycle, which is really what we want 190 */ 191 if ( cycleheadp -> cyclehead != cycleheadp ) { 192 cycleheadp = cycleheadp -> cyclehead; 193 # ifdef DEBUG 194 if ( debug & DFNDEBUG ) { 195 printf( "[dfn_findcycle] new cyclehead " ); 196 printname( cycleheadp ); 197 printf( "\n" ); 198 } 199 # endif DEBUG 200 } 201 for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) { 202 childp = dfn_stack[ index ].nlentryp; 203 if ( childp -> cyclehead == childp ) { 204 /* 205 * not yet glommed anywhere, glom it 206 * and fix any children it has glommed 207 */ 208 tailp -> cnext = childp; 209 childp -> cyclehead = cycleheadp; 210 # ifdef DEBUG 211 if ( debug & DFNDEBUG ) { 212 printf( "[dfn_findcycle] glomming " ); 213 printname( childp ); 214 printf( " onto " ); 215 printname( cycleheadp ); 216 printf( "\n" ); 217 } 218 # endif DEBUG 219 for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) { 220 tailp -> cnext -> cyclehead = cycleheadp; 221 # ifdef DEBUG 222 if ( debug & DFNDEBUG ) { 223 printf( "[dfn_findcycle] and its tail " ); 224 printname( tailp -> cnext ); 225 printf( " onto " ); 226 printname( cycleheadp ); 227 printf( "\n" ); 228 } 229 # endif DEBUG 230 } 231 } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) { 232 fprintf( stderr , 233 "[dfn_busy] glommed, but not to cyclehead\n" ); 234 } 235 } 236 } 237 } 238 239 /* 240 * deal with self-cycles 241 * for lint: ARGSUSED 242 */ 243 dfn_self_cycle( parentp ) 244 nltype *parentp; 245 { 246 /* 247 * since we are taking out self-cycles elsewhere 248 * no need for the special case, here. 249 */ 250 # ifdef DEBUG 251 if ( debug & DFNDEBUG ) { 252 printf( "[dfn_self_cycle] " ); 253 printname( parentp ); 254 printf( "\n" ); 255 } 256 # endif DEBUG 257 } 258 259 /* 260 * visit a node after all its children 261 * [MISSING: an explanation] 262 * and pop it off the stack 263 */ 264 dfn_post_visit( parentp ) 265 nltype *parentp; 266 { 267 nltype *memberp; 268 269 # ifdef DEBUG 270 if ( debug & DFNDEBUG ) { 271 printf( "[dfn_post_visit]\t%d: " , dfn_depth ); 272 printname( parentp ); 273 printf( "\n" ); 274 } 275 # endif DEBUG 276 /* 277 * number functions and things in their cycles 278 * unless the function is itself part of a cycle 279 */ 280 if ( parentp -> cyclehead == parentp ) { 281 dfn_counter += 1; 282 for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) { 283 memberp -> toporder = dfn_counter; 284 # ifdef DEBUG 285 if ( debug & DFNDEBUG ) { 286 printf( "[dfn_post_visit]\t\tmember " ); 287 printname( memberp ); 288 printf( " -> toporder = %d\n" , dfn_counter ); 289 } 290 # endif DEBUG 291 } 292 } else { 293 # ifdef DEBUG 294 if ( debug & DFNDEBUG ) { 295 printf( "[dfn_post_visit]\t\tis part of a cycle\n" ); 296 } 297 # endif DEBUG 298 } 299 dfn_depth -= 1; 300 } 301