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