1 #ifndef lint 2 static char *sccsid = "@(#)arcs.c 1.7 (Berkeley) 06/14/82"; 3 #endif lint 4 5 #include "gprof.h" 6 7 /* 8 * add (or just increment) an arc 9 */ 10 addarc( parentp , childp , count ) 11 nltype *parentp; 12 nltype *childp; 13 long count; 14 { 15 arctype *calloc(); 16 arctype *arcp; 17 18 # ifdef DEBUG 19 if ( debug & TALLYDEBUG ) { 20 printf( "[addarc] %d arcs from %s to %s\n" , 21 count , parentp -> name , childp -> name ); 22 } 23 # endif DEBUG 24 arcp = arclookup( parentp , childp ); 25 if ( arcp != 0 ) { 26 /* 27 * a hit: just increment the count. 28 */ 29 # ifdef DEBUG 30 if ( debug & TALLYDEBUG ) { 31 printf( "[tally] hit %d += %d\n" , 32 arcp -> arc_count , count ); 33 } 34 # endif DEBUG 35 arcp -> arc_count += count; 36 return; 37 } 38 arcp = calloc( 1 , sizeof *arcp ); 39 arcp -> arc_parentp = parentp; 40 arcp -> arc_childp = childp; 41 arcp -> arc_count = count; 42 /* 43 * prepend this child to the children of this parent 44 */ 45 arcp -> arc_childlist = parentp -> children; 46 parentp -> children = arcp; 47 /* 48 * prepend this parent to the parents of this child 49 */ 50 arcp -> arc_parentlist = childp -> parents; 51 childp -> parents = arcp; 52 } 53 54 /* 55 * the code below topologically sorts the graph (collapsing cycles), 56 * and propagates time bottom up and flags top down. 57 */ 58 59 /* 60 * the topologically sorted name list pointers 61 */ 62 nltype **topsortnlp; 63 64 topcmp( npp1 , npp2 ) 65 nltype **npp1; 66 nltype **npp2; 67 { 68 return (*npp1) -> toporder - (*npp2) -> toporder; 69 } 70 71 doarcs() 72 { 73 nltype *parentp; 74 arctype *arcp; 75 long index; 76 77 /* 78 * initialize various things: 79 * zero out child times. 80 * count self-recursive calls. 81 * indicate that nothing is on cycles. 82 */ 83 for ( parentp = nl ; parentp < npe ; parentp++ ) { 84 parentp -> childtime = 0.0; 85 arcp = arclookup( parentp , parentp ); 86 if ( arcp != 0 ) { 87 parentp -> ncall -= arcp -> arc_count; 88 parentp -> selfcalls = arcp -> arc_count; 89 } else { 90 parentp -> selfcalls = 0; 91 } 92 parentp -> printflag = FALSE; 93 parentp -> toporder = 0; 94 parentp -> cycleno = 0; 95 parentp -> cyclehead = parentp; 96 parentp -> cnext = 0; 97 if ( cflag ) { 98 findcalls( parentp , parentp -> value , (parentp+1) -> value ); 99 } 100 } 101 /* 102 * time for functions which print is accumulated here. 103 */ 104 printtime = 0.0; 105 /* 106 * topologically order things 107 * from each of the roots of the call graph 108 */ 109 for ( parentp = nl ; parentp < npe ; parentp++ ) { 110 if ( parentp -> parents == 0 ) { 111 dfn( parentp ); 112 } 113 } 114 /* 115 * link together nodes on the same cycle 116 */ 117 cyclelink(); 118 /* 119 * Sort the symbol table in reverse topological order 120 */ 121 topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) ); 122 if ( topsortnlp == (nltype **) 0 ) { 123 fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" ); 124 } 125 for ( index = 0 ; index < nname ; index += 1 ) { 126 topsortnlp[ index ] = &nl[ index ]; 127 } 128 qsort( topsortnlp , nname , sizeof(nltype *) , topcmp ); 129 # ifdef DEBUG 130 if ( debug & DFNDEBUG ) { 131 printf( "[doarcs] topological sort listing\n" ); 132 for ( index = 0 ; index < nname ; index += 1 ) { 133 printf( "[doarcs] " ); 134 printf( "%d:" , topsortnlp[ index ] -> toporder ); 135 printname( topsortnlp[ index ] ); 136 printf( "\n" ); 137 } 138 } 139 # endif DEBUG 140 /* 141 * starting from the topological bottom, 142 * propogate children times up to parents. 143 */ 144 dotime(); 145 /* 146 * starting from the topological top, 147 * propagate print flags to children. 148 */ 149 doflags(); 150 printgprof(); 151 } 152 153 dotime() 154 { 155 int index; 156 157 cycletime(); 158 for ( index = 0 ; index < nname ; index += 1 ) { 159 timepropagate( topsortnlp[ index ] ); 160 } 161 } 162 163 timepropagate( parentp ) 164 nltype *parentp; 165 { 166 arctype *arcp; 167 nltype *childp; 168 double share; 169 170 /* 171 * gather time from children of this parent. 172 */ 173 for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { 174 childp = arcp -> arc_childp; 175 # ifdef DEBUG 176 if ( debug & ARCDEBUG ) { 177 printf( "[propagate] " ); 178 printname( parentp ); 179 printf( " calls " ); 180 printname( childp ); 181 printf( " %d (%d) times\n" , 182 arcp -> arc_count , childp -> ncall ); 183 } 184 # endif DEBUG 185 if ( arcp -> arc_count == 0 ) { 186 continue; 187 } 188 if ( childp -> ncall == 0 ) { 189 continue; 190 } 191 if ( childp == parentp ) { 192 continue; 193 } 194 if ( childp -> cyclehead != childp ) { 195 if ( parentp -> cycleno == childp -> cycleno ) { 196 continue; 197 } 198 # ifdef DEBUG 199 if ( debug & ARCDEBUG ) { 200 printf( "[propagate]\t it's a call into cycle %d\n" , 201 childp -> cycleno ); 202 } 203 # endif DEBUG 204 if ( parentp -> toporder <= childp -> toporder ) { 205 fprintf( stderr , "[propagate] toporder botches\n" ); 206 } 207 childp = childp -> cyclehead; 208 } else { 209 if ( parentp -> toporder <= childp -> toporder ) { 210 fprintf( stderr , "[propagate] toporder botches\n" ); 211 continue; 212 } 213 } 214 /* 215 * distribute time for this arc 216 */ 217 arcp -> arc_time = childp -> time * 218 ( ( (double) arcp -> arc_count ) / 219 ( (double) childp -> ncall ) ); 220 arcp -> arc_childtime = childp -> childtime * 221 ( ( (double) arcp -> arc_count ) / 222 ( (double) childp -> ncall ) ); 223 share = arcp -> arc_time + arcp -> arc_childtime; 224 # ifdef DEBUG 225 if ( debug & ARCDEBUG ) { 226 printf( "[propagate]\t " ); 227 printname( childp ); 228 printf( " time %8.2f + childtime %8.2f\n" , 229 childp -> time , childp -> childtime ); 230 printf( "[propagate]\t this is %d arcs of the %d calls\n", 231 arcp -> arc_count , childp -> ncall ); 232 printf( "[propagate]\t so this gives %8.2f+%8.2f to %s\n" , 233 arcp -> arc_time , arcp -> arc_childtime , 234 parentp -> name ); 235 } 236 # endif DEBUG 237 parentp -> childtime += share; 238 /* 239 * add this share to the cycle header, if any 240 */ 241 if ( parentp -> cyclehead != parentp ) { 242 # ifdef DEBUG 243 if ( debug & ARCDEBUG ) { 244 printf( "[propagate]\t and to cycle %d\n" , 245 parentp -> cycleno ); 246 } 247 # endif DEBUG 248 parentp -> cyclehead -> childtime += share; 249 } 250 } 251 } 252 253 cyclelink() 254 { 255 register nltype *nlp; 256 register nltype *cyclenlp; 257 int cycle; 258 nltype *memberp; 259 260 /* 261 * Count the number of cycles, and initialze the cycle lists 262 */ 263 ncycle = 0; 264 for ( nlp = nl ; nlp < npe ; nlp++ ) { 265 /* 266 * this is how you find unattached cycles 267 */ 268 if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) { 269 ncycle += 1; 270 } 271 } 272 /* 273 * cyclenl is indexed by cycle number: 274 * i.e. it is origin 1, not origin 0. 275 */ 276 cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) ); 277 if ( cyclenl == 0 ) { 278 fprintf( stderr , "%s: No room for %d bytes of cycle headers\n" , 279 whoami , ( ncycle + 1 ) * sizeof( nltype ) ); 280 done(); 281 } 282 /* 283 * now link cycles to true cycleheads, 284 * number them, accumulate the data for the cycle 285 */ 286 cycle = 0; 287 for ( nlp = nl ; nlp < npe ; nlp++ ) { 288 if ( nlp -> cyclehead != nlp || nlp -> cnext == 0 ) { 289 continue; 290 } 291 cycle += 1; 292 cyclenlp = &cyclenl[cycle]; 293 cyclenlp -> cycleno = cycle; 294 cyclenlp -> cyclehead = cyclenlp; 295 cyclenlp -> cnext = nlp; 296 # ifdef DEBUG 297 if ( debug & CYCLEDEBUG ) { 298 printf( "[cyclelink] " ); 299 printname( nlp ); 300 printf( " is the head of cycle %d\n" , cycle ); 301 } 302 # endif DEBUG 303 for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { 304 memberp -> cycleno = cycle; 305 memberp -> cyclehead = cyclenlp; 306 } 307 } 308 } 309 310 cycletime() 311 { 312 int cycle; 313 nltype *cyclenlp; 314 nltype *parentp; 315 nltype *childp; 316 arctype *arcp; 317 long ncall; 318 double time; 319 long callsamong; 320 321 for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) { 322 cyclenlp = &cyclenl[ cycle ]; 323 /* 324 * n-squaredly (in the size of the cycle) 325 * find all the call within the cycle 326 * (including self-recursive calls) 327 * and remove them, thus making the cycle into 328 * `node' with calls only from the outside. 329 * note: that this doesn't deal with 330 * self-recursive calls outside cycles (sigh). 331 */ 332 callsamong = 0; 333 for ( parentp = cyclenlp->cnext; parentp; parentp = parentp->cnext ) { 334 for ( childp = cyclenlp->cnext; childp; childp = childp -> cnext ) { 335 if ( parentp == childp ) { 336 continue; 337 } 338 arcp = arclookup( parentp , childp ); 339 if ( arcp != 0 ) { 340 callsamong += arcp -> arc_count; 341 # ifdef DEBUG 342 if ( debug & CYCLEDEBUG ) { 343 printf("[cyclelink] %s calls sibling %s %d times\n", 344 parentp -> name , childp -> name , 345 arcp -> arc_count ); 346 } 347 # endif DEBUG 348 } 349 } 350 } 351 /* 352 * collect calls and time around the cycle, 353 * and save it in the cycle header. 354 */ 355 ncall = -callsamong; 356 time = 0.0; 357 for ( parentp = cyclenlp->cnext; parentp; parentp = parentp->cnext ) { 358 ncall += parentp -> ncall; 359 time += parentp -> time; 360 } 361 # ifdef DEBUG 362 if ( debug & CYCLEDEBUG ) { 363 printf( "[cyclelink] cycle %d %f ticks in %d (%d) calls\n" , 364 cycle , time , ncall , callsamong ); 365 } 366 # endif DEBUG 367 cyclenlp -> ncall = ncall; 368 cyclenlp -> selfcalls = callsamong; 369 cyclenlp -> time = time; 370 cyclenlp -> childtime = 0.0; 371 } 372 } 373 374 /* 375 * in one top to bottom pass over the topologically sorted namelist 376 * set the print flags and sum up the time that will be shown in the 377 * graph profile. 378 */ 379 doflags() 380 { 381 int index; 382 nltype *childp; 383 nltype *oldhead; 384 385 oldhead = 0; 386 for ( index = nname-1 ; index >= 0 ; index -= 1 ) { 387 childp = topsortnlp[ index ]; 388 /* 389 * if we haven't done this function or cycle, 390 * calculate its printflag. 391 * this way, we are linear in the number of arcs 392 * since we do all members of a cycle (and the cycle itself) 393 * as we hit the first member of the cycle. 394 */ 395 if ( childp -> cyclehead != oldhead ) { 396 oldhead = childp -> cyclehead; 397 parentprint( childp ); 398 } 399 if ( ! childp -> printflag ) { 400 /* 401 * -f function says print the sucker 402 * -e function says don't print it (leave it non-printing) 403 * no -f's at all says print everything 404 */ 405 if ( fflag && onflist( childp -> name ) ) { 406 childp -> printflag = TRUE; 407 printtime += childp -> time + childp -> childtime; 408 continue; 409 } 410 if ( eflag && onelist( childp -> name ) ) { 411 continue; 412 } 413 if ( !fflag ) { 414 childp -> printflag = TRUE; 415 printtime += childp -> time + childp -> childtime; 416 continue; 417 } 418 continue; 419 } 420 /* 421 * this function has printing parents: 422 * maybe someone wants to shut it up. 423 */ 424 if ( eflag && onelist( childp -> name ) ) { 425 childp -> printflag = FALSE; 426 continue; 427 } 428 } 429 } 430 431 /* 432 * check if any parent of this child 433 * (or outside parents of this cycle) 434 * have their print flags on and set the 435 * print flag of the child (cycle) appropriately. 436 */ 437 parentprint( childp ) 438 nltype *childp; 439 { 440 nltype *headp; 441 nltype *memp; 442 arctype *arcp; 443 444 headp = childp -> cyclehead; 445 if ( childp == headp ) { 446 /* 447 * just a regular child, check its parents 448 */ 449 for ( arcp = childp->parents ; arcp ; arcp = arcp->arc_parentlist ) { 450 if ( arcp -> arc_parentp -> printflag ) { 451 childp -> printflag = TRUE; 452 break; 453 } 454 } 455 return; 456 } 457 /* 458 * its a member of a cycle, look at all parents from 459 * outside the cycle 460 */ 461 for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) { 462 for ( arcp = memp -> parents ; arcp ; arcp = arcp -> arc_parentlist ) { 463 if ( arcp -> arc_parentp -> cyclehead == headp ) { 464 continue; 465 } 466 if ( arcp -> arc_parentp -> printflag ) { 467 goto set; 468 } 469 } 470 } 471 return; 472 /* 473 * the cycle has a printing parent: set the cycle 474 */ 475 set: 476 for ( memp = headp ; memp ; memp = memp -> cnext ) { 477 memp -> printflag = TRUE; 478 } 479 } 480