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