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