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