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