| 1 | #ifndef lint |
| 2 | static char *sccsid = "@(#)arcs.c 1.1 (Berkeley) %G%"; |
| 3 | #endif lint |
| 4 | |
| 5 | #include "dprof.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 | printdprof(); |
| 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 | } |