1 #ifndef lint 2 static char *sccsid = "@(#)arcs.c 1.4 (Berkeley) 11/06/81"; 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 topcmp( npp1 , npp2 ) 55 nltype **npp1; 56 nltype **npp2; 57 { 58 return (*npp1) -> toporder - (*npp2) -> toporder; 59 } 60 61 /* 62 * sort by decreasing total time (time+childtime) 63 * if times are equal, but one is a cycle header, 64 * say that's first (e.g. less) 65 */ 66 int 67 totalcmp( npp1 , npp2 ) 68 nltype **npp1; 69 nltype **npp2; 70 { 71 register nltype *np1 = *npp1; 72 register nltype *np2 = *npp2; 73 double diff; 74 75 diff = ( np1 -> time + np1 -> childtime ) 76 - ( np2 -> time + np2 -> childtime ); 77 if ( diff < 0.0 ) 78 return 1; 79 if ( diff > 0.0 ) 80 return -1; 81 if ( np1 -> name == 0 && np1 -> cycleno != 0 ) 82 return -1; 83 if ( np2 -> name == 0 && np1 -> cycleno != 0 ) 84 return 1; 85 return 0; 86 } 87 88 doarcs() 89 { 90 nltype *parentp; 91 arctype *arcp; 92 nltype **topsortnlp; 93 long index; 94 nltype *childp; 95 double share; 96 97 /* 98 * initialize various things: 99 * zero out child times. 100 * count self-recursive calls. 101 * indicate that nothing is on cycles. 102 */ 103 for ( parentp = nl ; parentp < npe ; parentp++ ) { 104 parentp -> childtime = 0.0; 105 arcp = arclookup( parentp , parentp ); 106 if ( arcp != 0 ) { 107 parentp -> ncall -= arcp -> arc_count; 108 parentp -> selfcalls = arcp -> arc_count; 109 } else { 110 parentp -> selfcalls = 0; 111 } 112 if ( cflag ) { 113 findcalls( parentp , parentp -> value , (parentp+1) -> value ); 114 } 115 parentp -> toporder = 0; 116 parentp -> cycleno = 0; 117 parentp -> cyclehead = parentp; 118 parentp -> cnext = 0; 119 } 120 /* 121 * topologically order things 122 * from each of the roots of the call graph 123 */ 124 for ( parentp = nl ; parentp < npe ; parentp++ ) { 125 if ( parentp -> parents == 0 ) { 126 dfn( parentp ); 127 } 128 } 129 /* 130 * link together nodes on the same cycle 131 */ 132 cyclelink(); 133 /* 134 * Sort the symbol table in reverse topological order 135 */ 136 topsortnlp = (nltype **) calloc( nname , sizeof(nltype *) ); 137 if ( topsortnlp == (nltype **) 0 ) { 138 fprintf( stderr , "[doarcs] ran out of memory for topo sorting\n" ); 139 } 140 for ( index = 0 ; index < nname ; index += 1 ) { 141 topsortnlp[ index ] = &nl[ index ]; 142 } 143 qsort( topsortnlp , nname , sizeof(nltype *) , topcmp ); 144 # ifdef DEBUG 145 if ( debug & DFNDEBUG ) { 146 printf( "[doarcs] topological sort listing\n" ); 147 for ( index = 0 ; index < nname ; index += 1 ) { 148 printf( "[doarcs] " ); 149 printf( "%d:" , topsortnlp[ index ] -> toporder ); 150 printname( topsortnlp[ index ] ); 151 printf( "\n" ); 152 } 153 } 154 # endif DEBUG 155 /* 156 * starting from the topological bottom, 157 * propogate children times 158 */ 159 for ( index = 0 ; index < nname ; index += 1 ) { 160 parentp = topsortnlp[ index ]; 161 for ( arcp = parentp->children ; arcp ; arcp = arcp->arc_childlist ) { 162 childp = arcp -> arc_childp; 163 # ifdef DEBUG 164 if ( debug & ARCDEBUG ) { 165 printf( "[doarcs] " ); 166 printname( parentp ); 167 printf( " calls " ); 168 printname( childp ); 169 printf( " %d (%d) times\n" , 170 arcp -> arc_count , childp -> ncall ); 171 } 172 # endif DEBUG 173 if ( arcp -> arc_count == 0 ) { 174 continue; 175 } 176 if ( childp -> ncall == 0 ) { 177 continue; 178 } 179 if ( childp == parentp ) { 180 continue; 181 } 182 if ( childp -> cyclehead != childp ) { 183 if ( parentp -> cycleno == childp -> cycleno ) { 184 continue; 185 } 186 # ifdef DEBUG 187 if ( debug & ARCDEBUG ) { 188 printf( "[doarcs]\t it's a call into cycle %d\n" , 189 childp -> cycleno ); 190 } 191 # endif DEBUG 192 if ( parentp -> toporder <= childp -> toporder ) { 193 fprintf( stderr , "[doarcs] toporder botches\n" ); 194 } 195 childp = childp -> cyclehead; 196 } else { 197 if ( parentp -> toporder <= childp -> toporder ) { 198 fprintf( stderr , "[doarcs] toporder botches\n" ); 199 continue; 200 } 201 } 202 /* 203 * distribute time for this arc 204 */ 205 arcp -> arc_time = childp -> time * 206 ( ( (double) arcp -> arc_count ) / 207 ( (double) childp -> ncall ) ); 208 arcp -> arc_childtime = childp -> childtime * 209 ( ( (double) arcp -> arc_count ) / 210 ( (double) childp -> ncall ) ); 211 share = arcp -> arc_time + arcp -> arc_childtime; 212 # ifdef DEBUG 213 if ( debug & ARCDEBUG ) { 214 printf( "[doarcs]\t " ); 215 printname( childp ); 216 printf( " time %8.2f + childtime %8.2f\n" , 217 childp -> time , childp -> childtime ); 218 printf( "[doarcs]\t this is %d arcs of the %d calls\n", 219 arcp -> arc_count , childp -> ncall ); 220 printf( "[doarcs]\t so this gives %8.2f+%8.2f to %s\n" , 221 arcp -> arc_time , arcp -> arc_childtime , 222 parentp -> name ); 223 } 224 # endif DEBUG 225 parentp -> childtime += share; 226 /* 227 * add this share to the cycle header, if any 228 */ 229 if ( parentp -> cyclehead != parentp ) { 230 # ifdef DEBUG 231 if ( debug & ARCDEBUG ) { 232 printf( "[doarcs]\t and to cycle %d\n" , 233 parentp -> cycleno ); 234 } 235 # endif DEBUG 236 parentp -> cyclehead -> childtime += share; 237 } 238 } 239 } 240 printgprof(); 241 } 242 243 cyclelink() 244 { 245 register nltype *nlp; 246 register nltype *parentp; 247 register nltype *childp; 248 register nltype *cyclenlp; 249 int cycle; 250 arctype *arcp; 251 long ncall; 252 double time; 253 long callsamong; 254 255 /* 256 * Count the number of cycles, and initialze the cycle lists 257 */ 258 cyclemax = 0; 259 for ( nlp = nl ; nlp < npe ; nlp++ ) { 260 /* 261 * this is how you find unattached cycles 262 */ 263 if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) { 264 cyclemax += 1; 265 } 266 } 267 if ( cyclemax > ncycles ) { 268 fprintf( stderr , "prof: %d cycles in %d names exceeds %f%%\n" , 269 cyclemax , nname , CYCLEFRACTION * 100.0 ); 270 exit( 1 ); 271 } 272 /* 273 * now link cycles to true cycleheads, 274 * number them, accumulate the data for the cycle 275 */ 276 cycle = 0; 277 for ( nlp = nl ; nlp < npe ; nlp++ ) { 278 if ( nlp -> cyclehead != nlp || nlp -> cnext == 0 ) { 279 continue; 280 } 281 cycle += 1; 282 cyclenlp = &nl[nname+cycle]; 283 cyclenlp -> cycleno = cycle; 284 cyclenlp -> cyclehead = cyclenlp; 285 cyclenlp -> cnext = nlp; 286 # ifdef DEBUG 287 if ( debug & CYCLEDEBUG ) { 288 printf( "[cyclelink] " ); 289 printname( nlp ); 290 printf( " is the head of cycle %d\n" , cycle ); 291 } 292 # endif DEBUG 293 /* 294 * n-squaredly (in the size of the cycle) 295 * find all the call within the cycle 296 * (including self-recursive calls) 297 * and remove them, thus making the cycle into 298 * `node' with calls only from the outside. 299 * note: that this doesn't deal with 300 * self-recursive calls outside cycles (sigh). 301 */ 302 callsamong = 0; 303 for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) { 304 parentp -> cycleno = cycle; 305 parentp -> cyclehead = cyclenlp; 306 for ( childp = nlp ; childp ; childp = childp -> cnext ) { 307 if ( parentp == childp ) { 308 continue; 309 } 310 arcp = arclookup( parentp , childp ); 311 if ( arcp != 0 ) { 312 callsamong += arcp -> arc_count; 313 # ifdef DEBUG 314 if ( debug & CYCLEDEBUG ) { 315 printf("[cyclelink] %s calls sibling %s %d times\n", 316 parentp -> name , childp -> name , 317 arcp -> arc_count ); 318 } 319 # endif DEBUG 320 } 321 } 322 } 323 /* 324 * collect calls and time around the cycle, 325 * and save it in the cycle header. 326 */ 327 ncall = -callsamong; 328 time = 0.0; 329 for ( parentp = nlp ; parentp ; parentp = parentp -> cnext ) { 330 ncall += parentp -> ncall; 331 time += parentp -> time; 332 } 333 # ifdef DEBUG 334 if ( debug & CYCLEDEBUG ) { 335 printf( "[cyclelink] cycle %d %f ticks in %d (%d) calls\n" , 336 cycle , time , ncall , callsamong ); 337 } 338 # endif DEBUG 339 cyclenlp -> ncall = ncall; 340 cyclenlp -> selfcalls = callsamong; 341 cyclenlp -> time = time; 342 cyclenlp -> childtime = 0.0; 343 } 344 } 345