GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/gprof/arcs.c Lines: 0 327 0.0 %
Date: 2017-11-07 Branches: 0 244 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: arcs.c,v 1.14 2015/12/06 23:22:51 guenther Exp $	*/
2
/*	$NetBSD: arcs.c,v 1.6 1995/04/19 07:15:52 cgd Exp $	*/
3
4
/*
5
 * Copyright (c) 1983, 1993
6
 *	The Regents of the University of California.  All rights reserved.
7
 *
8
 * Redistribution and use in source and binary forms, with or without
9
 * modification, are permitted provided that the following conditions
10
 * are met:
11
 * 1. Redistributions of source code must retain the above copyright
12
 *    notice, this list of conditions and the following disclaimer.
13
 * 2. Redistributions in binary form must reproduce the above copyright
14
 *    notice, this list of conditions and the following disclaimer in the
15
 *    documentation and/or other materials provided with the distribution.
16
 * 3. Neither the name of the University nor the names of its contributors
17
 *    may be used to endorse or promote products derived from this software
18
 *    without specific prior written permission.
19
 *
20
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30
 * SUCH DAMAGE.
31
 */
32
33
#include "gprof.h"
34
35
#ifdef DEBUG
36
int visited;
37
int viable;
38
int newcycle;
39
int oldcycle;
40
void printsubcycle(cltype *);
41
#endif /* DEBUG */
42
43
    /*
44
     *	add (or just increment) an arc
45
     */
46
void
47
addarc(nltype *parentp, nltype *childp, long count)
48
{
49
    arctype		*arcp;
50
51
#   ifdef DEBUG
52
	if ( debug & TALLYDEBUG ) {
53
	    printf( "[addarc] %ld arcs from %s to %s\n" ,
54
		    count , parentp -> name , childp -> name );
55
	}
56
#   endif /* DEBUG */
57
    arcp = arclookup( parentp , childp );
58
    if ( arcp != 0 ) {
59
	    /*
60
	     *	a hit:  just increment the count.
61
	     */
62
#	ifdef DEBUG
63
	    if ( debug & TALLYDEBUG ) {
64
		printf( "[tally] hit %ld += %ld\n" ,
65
			arcp -> arc_count , count );
66
	    }
67
#	endif /* DEBUG */
68
	arcp -> arc_count += count;
69
	return;
70
    }
71
    arcp = calloc( 1 , sizeof *arcp );
72
    arcp -> arc_parentp = parentp;
73
    arcp -> arc_childp = childp;
74
    arcp -> arc_count = count;
75
	/*
76
	 *	prepend this child to the children of this parent
77
	 */
78
    arcp -> arc_childlist = parentp -> children;
79
    parentp -> children = arcp;
80
	/*
81
	 *	prepend this parent to the parents of this child
82
	 */
83
    arcp -> arc_parentlist = childp -> parents;
84
    childp -> parents = arcp;
85
}
86
87
    /*
88
     *	the code below topologically sorts the graph (collapsing cycles),
89
     *	and propagates time bottom up and flags top down.
90
     */
91
92
    /*
93
     *	the topologically sorted name list pointers
94
     */
95
nltype	**topsortnlp;
96
97
int
98
topcmp(const void *v1, const void *v2)
99
{
100
    const nltype * const *npp1 = v1;
101
    const nltype * const *npp2 = v2;
102
103
    if ((*npp1) -> toporder < (*npp2) -> toporder)
104
	return -1;
105
    return (*npp1) -> toporder > (*npp2) -> toporder;
106
}
107
108
nltype **
109
doarcs()
110
{
111
    nltype	*parentp, **timesortnlp;
112
    arctype	*arcp;
113
    long	index;
114
    long	pass;
115
116
	/*
117
	 *	initialize various things:
118
	 *	    zero out child times.
119
	 *	    count self-recursive calls.
120
	 *	    indicate that nothing is on cycles.
121
	 */
122
    for ( parentp = nl ; parentp < npe ; parentp++ ) {
123
	parentp -> childtime = 0.0;
124
	arcp = arclookup( parentp , parentp );
125
	if ( arcp != 0 ) {
126
	    parentp -> ncall -= arcp -> arc_count;
127
	    parentp -> selfcalls = arcp -> arc_count;
128
	} else {
129
	    parentp -> selfcalls = 0;
130
	}
131
	parentp -> npropcall = parentp -> ncall;
132
	parentp -> propfraction = 0.0;
133
	parentp -> propself = 0.0;
134
	parentp -> propchild = 0.0;
135
	parentp -> printflag = FALSE;
136
	parentp -> toporder = DFN_NAN;
137
	parentp -> cycleno = 0;
138
	parentp -> cyclehead = parentp;
139
	parentp -> cnext = 0;
140
	if ( cflag ) {
141
	    findcall( parentp , parentp -> value , (parentp+1) -> value );
142
	}
143
    }
144
    for ( pass = 1 ; ; pass++ ) {
145
	    /*
146
	     *	topologically order things
147
	     *	if any node is unnumbered,
148
	     *	    number it and any of its descendents.
149
	     */
150
	for ( dfn_init() , parentp = nl ; parentp < npe ; parentp++ ) {
151
	    if ( parentp -> toporder == DFN_NAN ) {
152
		dfn( parentp );
153
	    }
154
	}
155
	    /*
156
	     *	link together nodes on the same cycle
157
	     */
158
	cyclelink();
159
	    /*
160
	     *	if no cycles to break up, proceed
161
	     */
162
	if ( ! Cflag )
163
	    break;
164
	    /*
165
	     *	analyze cycles to determine breakup
166
	     */
167
#	ifdef DEBUG
168
	    if ( debug & BREAKCYCLE ) {
169
		printf("[doarcs] pass %ld, cycle(s) %d\n" , pass , ncycle );
170
	    }
171
#	endif /* DEBUG */
172
	if ( pass == 1 ) {
173
	    printf( "\n\n%s %s\n%s %d:\n" ,
174
		"The following arcs were deleted" ,
175
		"from the propagation calculation" ,
176
		"to reduce the maximum cycle size to", cyclethreshold );
177
	}
178
	if ( cycleanalyze() )
179
	    break;
180
	free ( cyclenl );
181
	ncycle = 0;
182
	for ( parentp = nl ; parentp < npe ; parentp++ ) {
183
	    parentp -> toporder = DFN_NAN;
184
	    parentp -> cycleno = 0;
185
	    parentp -> cyclehead = parentp;
186
	    parentp -> cnext = 0;
187
	}
188
    }
189
    if ( pass > 1 ) {
190
	printf( "\f\n" );
191
    } else {
192
	printf( "\tNone\n\n" );
193
    }
194
	/*
195
	 *	Sort the symbol table in reverse topological order
196
	 */
197
    topsortnlp = calloc( nname , sizeof(nltype *) );
198
    if ( topsortnlp == (nltype **) 0 )
199
	warnx("[doarcs] ran out of memory for topo sorting");
200
    for ( index = 0 ; index < nname ; index += 1 ) {
201
	topsortnlp[ index ] = &nl[ index ];
202
    }
203
    qsort( topsortnlp , nname , sizeof(nltype *) , topcmp );
204
#   ifdef DEBUG
205
	if ( debug & DFNDEBUG ) {
206
	    printf( "[doarcs] topological sort listing\n" );
207
	    for ( index = 0 ; index < nname ; index += 1 ) {
208
		printf( "[doarcs] " );
209
		printf( "%d:" , topsortnlp[ index ] -> toporder );
210
		printname( topsortnlp[ index ] );
211
		printf( "\n" );
212
	    }
213
	}
214
#   endif /* DEBUG */
215
	/*
216
	 *	starting from the topological top,
217
	 *	propagate print flags to children.
218
	 *	also, calculate propagation fractions.
219
	 *	this happens before time propagation
220
	 *	since time propagation uses the fractions.
221
	 */
222
    doflags();
223
	/*
224
	 *	starting from the topological bottom,
225
	 *	propagate children times up to parents.
226
	 */
227
    dotime();
228
	/*
229
	 *	Now, sort by propself + propchild.
230
	 *	sorting both the regular function names
231
	 *	and cycle headers.
232
	 */
233
    timesortnlp = calloc( nname + ncycle , sizeof(nltype *) );
234
    if ( timesortnlp == (nltype **) 0 )
235
	warnx("ran out of memory for sorting");
236
    for ( index = 0 ; index < nname ; index++ ) {
237
	timesortnlp[index] = &nl[index];
238
    }
239
    for ( index = 1 ; index <= ncycle ; index++ ) {
240
	timesortnlp[nname+index-1] = &cyclenl[index];
241
    }
242
    qsort( timesortnlp , nname + ncycle , sizeof(nltype *) , totalcmp );
243
    for ( index = 0 ; index < nname + ncycle ; index++ ) {
244
	timesortnlp[ index ] -> index = index + 1;
245
    }
246
    return( timesortnlp );
247
}
248
249
void
250
dotime()
251
{
252
    int	index;
253
254
    cycletime();
255
    for ( index = 0 ; index < nname ; index += 1 ) {
256
	timepropagate( topsortnlp[ index ] );
257
    }
258
}
259
260
void
261
timepropagate(nltype *parentp)
262
{
263
    arctype	*arcp;
264
    nltype	*childp;
265
    double	share;
266
    double	propshare;
267
268
    if ( parentp -> propfraction == 0.0 ) {
269
	return;
270
    }
271
	/*
272
	 *	gather time from children of this parent.
273
	 */
274
    for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
275
	childp = arcp -> arc_childp;
276
	if ( arcp -> arc_flags & DEADARC ) {
277
	    continue;
278
	}
279
	if ( arcp -> arc_count == 0 ) {
280
	    continue;
281
	}
282
	if ( childp == parentp ) {
283
	    continue;
284
	}
285
	if ( childp -> propfraction == 0.0 ) {
286
	    continue;
287
	}
288
	if ( childp -> cyclehead != childp ) {
289
	    if ( parentp -> cycleno == childp -> cycleno ) {
290
		continue;
291
	    }
292
	    if ( parentp -> toporder <= childp -> toporder )
293
		warnx("[propagate] toporder botches");
294
	    childp = childp -> cyclehead;
295
	} else {
296
	    if ( parentp -> toporder <= childp -> toporder ) {
297
		warnx("[propagate] toporder botches");
298
		continue;
299
	    }
300
	}
301
	if ( childp -> npropcall == 0 ) {
302
	    continue;
303
	}
304
	    /*
305
	     *	distribute time for this arc
306
	     */
307
	arcp -> arc_time = childp -> time
308
			        * ( ( (double) arcp -> arc_count ) /
309
				    ( (double) childp -> npropcall ) );
310
	arcp -> arc_childtime = childp -> childtime
311
			        * ( ( (double) arcp -> arc_count ) /
312
				    ( (double) childp -> npropcall ) );
313
	share = arcp -> arc_time + arcp -> arc_childtime;
314
	parentp -> childtime += share;
315
	    /*
316
	     *	( 1 - propfraction ) gets lost along the way
317
	     */
318
	propshare = parentp -> propfraction * share;
319
	    /*
320
	     *	fix things for printing
321
	     */
322
	parentp -> propchild += propshare;
323
	arcp -> arc_time *= parentp -> propfraction;
324
	arcp -> arc_childtime *= parentp -> propfraction;
325
	    /*
326
	     *	add this share to the parent's cycle header, if any.
327
	     */
328
	if ( parentp -> cyclehead != parentp ) {
329
	    parentp -> cyclehead -> childtime += share;
330
	    parentp -> cyclehead -> propchild += propshare;
331
	}
332
#	ifdef DEBUG
333
	    if ( debug & PROPDEBUG ) {
334
		printf( "[dotime] child \t" );
335
		printname( childp );
336
		printf( " with %f %f %ld/%ld\n" ,
337
			childp -> time , childp -> childtime ,
338
			arcp -> arc_count , childp -> npropcall );
339
		printf( "[dotime] parent\t" );
340
		printname( parentp );
341
		printf( "\n[dotime] share %f\n" , share );
342
	    }
343
#	endif /* DEBUG */
344
    }
345
}
346
347
void
348
cyclelink()
349
{
350
    nltype	*nlp;
351
    nltype	*cyclenlp;
352
    int			cycle;
353
    nltype		*memberp;
354
    arctype		*arcp;
355
356
	/*
357
	 *	Count the number of cycles, and initialze the cycle lists
358
	 */
359
    ncycle = 0;
360
    for ( nlp = nl ; nlp < npe ; nlp++ ) {
361
	    /*
362
	     *	this is how you find unattached cycles
363
	     */
364
	if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) {
365
	    ncycle += 1;
366
	}
367
    }
368
	/*
369
	 *	cyclenl is indexed by cycle number:
370
	 *	i.e. it is origin 1, not origin 0.
371
	 */
372
    cyclenl = calloc( ncycle + 1 , sizeof( nltype ) );
373
    if ( cyclenl == 0 )
374
	errx(0, "No room for %ld bytes of cycle headers",
375
	    (ncycle + 1) * sizeof(nltype));
376
	/*
377
	 *	now link cycles to true cycleheads,
378
	 *	number them, accumulate the data for the cycle
379
	 */
380
    cycle = 0;
381
    for ( nlp = nl ; nlp < npe ; nlp++ ) {
382
	if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) {
383
	    continue;
384
	}
385
	cycle += 1;
386
	cyclenlp = &cyclenl[cycle];
387
        cyclenlp -> name = 0;		/* the name */
388
        cyclenlp -> value = 0;		/* the pc entry point */
389
        cyclenlp -> time = 0.0;		/* ticks in this routine */
390
        cyclenlp -> childtime = 0.0;	/* cumulative ticks in children */
391
	cyclenlp -> ncall = 0;		/* how many times called */
392
	cyclenlp -> selfcalls = 0;	/* how many calls to self */
393
	cyclenlp -> propfraction = 0.0;	/* what % of time propagates */
394
	cyclenlp -> propself = 0.0;	/* how much self time propagates */
395
	cyclenlp -> propchild = 0.0;	/* how much child time propagates */
396
	cyclenlp -> printflag = TRUE;	/* should this be printed? */
397
	cyclenlp -> index = 0;		/* index in the graph list */
398
	cyclenlp -> toporder = DFN_NAN;	/* graph call chain top-sort order */
399
	cyclenlp -> cycleno = cycle;	/* internal number of cycle on */
400
	cyclenlp -> cyclehead = cyclenlp;	/* pointer to head of cycle */
401
	cyclenlp -> cnext = nlp;	/* pointer to next member of cycle */
402
	cyclenlp -> parents = 0;	/* list of caller arcs */
403
	cyclenlp -> children = 0;	/* list of callee arcs */
404
#	ifdef DEBUG
405
	    if ( debug & CYCLEDEBUG ) {
406
		printf( "[cyclelink] " );
407
		printname( nlp );
408
		printf( " is the head of cycle %d\n" , cycle );
409
	    }
410
#	endif /* DEBUG */
411
	    /*
412
	     *	link members to cycle header
413
	     */
414
	for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
415
	    memberp -> cycleno = cycle;
416
	    memberp -> cyclehead = cyclenlp;
417
	}
418
	    /*
419
	     *	count calls from outside the cycle
420
	     *	and those among cycle members
421
	     */
422
	for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) {
423
	    for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) {
424
		if ( arcp -> arc_parentp == memberp ) {
425
		    continue;
426
		}
427
		if ( arcp -> arc_parentp -> cycleno == cycle ) {
428
		    cyclenlp -> selfcalls += arcp -> arc_count;
429
		} else {
430
		    cyclenlp -> npropcall += arcp -> arc_count;
431
		}
432
	    }
433
	}
434
    }
435
}
436
437
    /*
438
     *	analyze cycles to determine breakup
439
     */
440
int
441
cycleanalyze()
442
{
443
    arctype	**cyclestack;
444
    arctype	**stkp;
445
    arctype	**arcpp;
446
    arctype	**endlist;
447
    arctype	*arcp;
448
    nltype	*nlp;
449
    cltype	*clp;
450
    bool	ret;
451
    bool	done;
452
    int		size;
453
    int		cycleno;
454
455
	/*
456
	 *	calculate the size of the cycle, and find nodes that
457
	 *	exit the cycle as they are desirable targets to cut
458
	 *	some of their parents
459
	 */
460
    for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) {
461
	size = 0;
462
	for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) {
463
	    size += 1;
464
	    nlp -> parentcnt = 0;
465
	    nlp -> flags &= ~HASCYCLEXIT;
466
	    for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) {
467
		nlp -> parentcnt += 1;
468
		if ( arcp -> arc_parentp -> cycleno != cycleno )
469
		    nlp -> flags |= HASCYCLEXIT;
470
	    }
471
	}
472
	if ( size <= cyclethreshold )
473
	    continue;
474
	done = FALSE;
475
        cyclestack = calloc( size + 1 , sizeof( arctype *) );
476
	if ( cyclestack == 0 ) {
477
	    warnx("No room for %ld bytes of cycle stack" ,
478
		(size + 1) * sizeof(arctype *));
479
	    return (done);
480
	}
481
#	ifdef DEBUG
482
	    if ( debug & BREAKCYCLE ) {
483
		printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
484
		    cycleno , ncycle , size );
485
	    }
486
#	endif /* DEBUG */
487
	for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
488
	    stkp = &cyclestack[0];
489
	    nlp -> flags |= CYCLEHEAD;
490
	    ret = descend ( nlp , cyclestack , stkp );
491
	    nlp -> flags &= ~CYCLEHEAD;
492
	    if ( ret == FALSE )
493
		break;
494
	}
495
	free( cyclestack );
496
	if ( cyclecnt > 0 ) {
497
	    compresslist();
498
	    for ( clp = cyclehead ; clp ; ) {
499
		endlist = &clp -> list[ clp -> size ];
500
		for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
501
		    (*arcpp) -> arc_cyclecnt--;
502
		cyclecnt--;
503
		clp = clp -> next;
504
		free( clp );
505
	    }
506
	    cyclehead = 0;
507
	}
508
    }
509
#   ifdef DEBUG
510
	if ( debug & BREAKCYCLE ) {
511
	    printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
512
		"[doarcs]" , visited , viable , newcycle , oldcycle);
513
	}
514
#   endif /* DEBUG */
515
    return (done);
516
}
517
518
int
519
descend(nltype *node, arctype **stkstart, arctype **stkp)
520
{
521
    arctype	*arcp;
522
    bool	ret;
523
524
    for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) {
525
#	ifdef DEBUG
526
	    visited++;
527
#	endif /* DEBUG */
528
	if ( arcp -> arc_childp -> cycleno != node -> cycleno
529
	    || ( arcp -> arc_childp -> flags & VISITED )
530
	    || ( arcp -> arc_flags & DEADARC ) )
531
	    continue;
532
#	ifdef DEBUG
533
	    viable++;
534
#	endif /* DEBUG */
535
	*stkp = arcp;
536
	if ( arcp -> arc_childp -> flags & CYCLEHEAD ) {
537
	    if ( addcycle( stkstart , stkp ) == FALSE )
538
		return( FALSE );
539
	    continue;
540
	}
541
	arcp -> arc_childp -> flags |= VISITED;
542
	ret = descend( arcp -> arc_childp , stkstart , stkp + 1 );
543
	arcp -> arc_childp -> flags &= ~VISITED;
544
	if ( ret == FALSE )
545
	    return( FALSE );
546
    }
547
    return (TRUE);
548
}
549
550
int
551
addcycle(arctype **stkstart, arctype **stkend)
552
{
553
    arctype	**arcpp;
554
    arctype	**stkloc;
555
    arctype	**stkp;
556
    arctype	**endlist;
557
    arctype	*minarc;
558
    arctype	*arcp;
559
    cltype	*clp;
560
    int		size;
561
562
    size = stkend - stkstart + 1;
563
    if ( size <= 1 )
564
	return( TRUE );
565
    for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
566
	if ( *arcpp > minarc )
567
	    continue;
568
	minarc = *arcpp;
569
	stkloc = arcpp;
570
    }
571
    for ( clp = cyclehead ; clp ; clp = clp -> next ) {
572
	if ( clp -> size != size )
573
	    continue;
574
	stkp = stkloc;
575
	endlist = &clp -> list[ size ];
576
	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
577
	    if ( *stkp++ != *arcpp )
578
		break;
579
	    if ( stkp > stkend )
580
		stkp = stkstart;
581
	}
582
	if ( arcpp == endlist ) {
583
#	    ifdef DEBUG
584
		oldcycle++;
585
#	    endif /* DEBUG */
586
	    return( TRUE );
587
	}
588
    }
589
    clp = calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
590
    if ( clp == 0 ) {
591
	warnx("No room for %ld bytes of subcycle storage" ,
592
	    sizeof(cltype) + (size - 1) * sizeof(arctype *));
593
	return( FALSE );
594
    }
595
    stkp = stkloc;
596
    endlist = &clp -> list[ size ];
597
    for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
598
	arcp = *arcpp = *stkp++;
599
	if ( stkp > stkend )
600
	    stkp = stkstart;
601
	arcp -> arc_cyclecnt++;
602
	if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
603
	    arcp -> arc_flags |= ONLIST;
604
	    arcp -> arc_next = archead;
605
	    archead = arcp;
606
	}
607
    }
608
    clp -> size = size;
609
    clp -> next = cyclehead;
610
    cyclehead = clp;
611
#   ifdef DEBUG
612
	newcycle++;
613
	if ( debug & SUBCYCLELIST ) {
614
	    printsubcycle( clp );
615
	}
616
#   endif /* DEBUG */
617
    cyclecnt++;
618
    if ( cyclecnt >= CYCLEMAX )
619
	return( FALSE );
620
    return( TRUE );
621
}
622
623
void
624
compresslist()
625
{
626
    cltype	*clp;
627
    cltype	**prev;
628
    arctype	**arcpp;
629
    arctype	**endlist;
630
    arctype	*arcp;
631
    arctype	*maxarcp;
632
    arctype	*maxexitarcp;
633
    arctype	*maxwithparentarcp;
634
    arctype	*maxnoparentarcp;
635
    int		maxexitcnt;
636
    int		maxwithparentcnt;
637
    int		maxnoparentcnt;
638
#   ifdef DEBUG
639
        char	*type;
640
#   endif
641
642
    maxexitcnt = 0;
643
    maxwithparentcnt = 0;
644
    maxnoparentcnt = 0;
645
    for ( endlist = &archead , arcp = archead ; arcp ; ) {
646
	if ( arcp -> arc_cyclecnt == 0 ) {
647
	    arcp -> arc_flags &= ~ONLIST;
648
	    *endlist = arcp -> arc_next;
649
	    arcp -> arc_next = 0;
650
	    arcp = *endlist;
651
	    continue;
652
	}
653
	if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) {
654
	    if ( arcp -> arc_cyclecnt > maxexitcnt ||
655
		( arcp -> arc_cyclecnt == maxexitcnt &&
656
		arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) {
657
		maxexitcnt = arcp -> arc_cyclecnt;
658
		maxexitarcp = arcp;
659
	    }
660
	} else if ( arcp -> arc_childp -> parentcnt > 1 ) {
661
	    if ( arcp -> arc_cyclecnt > maxwithparentcnt ||
662
		( arcp -> arc_cyclecnt == maxwithparentcnt &&
663
		arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) {
664
		maxwithparentcnt = arcp -> arc_cyclecnt;
665
		maxwithparentarcp = arcp;
666
	    }
667
	} else {
668
	    if ( arcp -> arc_cyclecnt > maxnoparentcnt ||
669
		( arcp -> arc_cyclecnt == maxnoparentcnt &&
670
		arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) {
671
		maxnoparentcnt = arcp -> arc_cyclecnt;
672
		maxnoparentarcp = arcp;
673
	    }
674
	}
675
	endlist = &arcp -> arc_next;
676
	arcp = arcp -> arc_next;
677
    }
678
    if ( maxexitcnt > 0 ) {
679
	/*
680
	 *	first choice is edge leading to node with out-of-cycle parent
681
	 */
682
	maxarcp = maxexitarcp;
683
#	ifdef DEBUG
684
	    type = "exit";
685
#	endif /* DEBUG */
686
    } else if ( maxwithparentcnt > 0 ) {
687
	/*
688
	 *	second choice is edge leading to node with at least one
689
	 *	other in-cycle parent
690
	 */
691
	maxarcp = maxwithparentarcp;
692
#	ifdef DEBUG
693
	    type = "internal";
694
#	endif /* DEBUG */
695
    } else {
696
	/*
697
	 *	last choice is edge leading to node with only this arc as
698
	 *	a parent (as it will now be orphaned)
699
	 */
700
	maxarcp = maxnoparentarcp;
701
#	ifdef DEBUG
702
	    type = "orphan";
703
#	endif /* DEBUG */
704
    }
705
    maxarcp -> arc_flags |= DEADARC;
706
    maxarcp -> arc_childp -> parentcnt -= 1;
707
    maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count;
708
#   ifdef DEBUG
709
	if ( debug & BREAKCYCLE ) {
710
	    printf("[compresslist] delete %s arc: "
711
		"%s (%ld) -> %s from %d cycle(s)\n", type,
712
		maxarcp -> arc_parentp -> name, maxarcp -> arc_count,
713
		maxarcp -> arc_childp -> name, maxarcp -> arc_cyclecnt);
714
	}
715
#   endif /* DEBUG */
716
    printf("\t%s to %s with %ld calls\n", maxarcp->arc_parentp -> name,
717
	maxarcp->arc_childp->name, maxarcp->arc_count);
718
    prev = &cyclehead;
719
    for ( clp = cyclehead ; clp ; ) {
720
	endlist = &clp -> list[ clp -> size ];
721
	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
722
	    if ( (*arcpp) -> arc_flags & DEADARC )
723
		break;
724
	if ( arcpp == endlist ) {
725
	    prev = &clp -> next;
726
	    clp = clp -> next;
727
	    continue;
728
	}
729
	for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
730
	    (*arcpp) -> arc_cyclecnt--;
731
	cyclecnt--;
732
	*prev = clp -> next;
733
	free( clp );
734
	clp = *prev;
735
    }
736
}
737
738
#ifdef DEBUG
739
void
740
printsubcycle(cltype *clp)
741
{
742
    arctype	**arcpp;
743
    arctype	**endlist;
744
745
    arcpp = clp -> list;
746
    printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name ,
747
	(*arcpp) -> arc_parentp -> cycleno ) ;
748
    for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ )
749
	printf( "\t(%ld) -> %s\n" , (*arcpp) -> arc_count ,
750
	    (*arcpp) -> arc_childp -> name ) ;
751
}
752
#endif /* DEBUG */
753
754
void
755
cycletime()
756
{
757
    int			cycle;
758
    nltype		*cyclenlp;
759
    nltype		*childp;
760
761
    for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) {
762
	cyclenlp = &cyclenl[ cycle ];
763
	for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) {
764
	    if ( childp -> propfraction == 0.0 ) {
765
		    /*
766
		     * all members have the same propfraction except those
767
		     *	that were excluded with -E
768
		     */
769
		continue;
770
	    }
771
	    cyclenlp -> time += childp -> time;
772
	}
773
	cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time;
774
    }
775
}
776
777
    /*
778
     *	in one top to bottom pass over the topologically sorted namelist
779
     *	propagate:
780
     *		printflag as the union of parents' printflags
781
     *		propfraction as the sum of fractional parents' propfractions
782
     *	and while we're here, sum time for functions.
783
     */
784
void
785
doflags()
786
{
787
    int		index;
788
    nltype	*childp;
789
    nltype	*oldhead;
790
791
    oldhead = 0;
792
    for ( index = nname-1 ; index >= 0 ; index -= 1 ) {
793
	childp = topsortnlp[ index ];
794
	    /*
795
	     *	if we haven't done this function or cycle,
796
	     *	inherit things from parent.
797
	     *	this way, we are linear in the number of arcs
798
	     *	since we do all members of a cycle (and the cycle itself)
799
	     *	as we hit the first member of the cycle.
800
	     */
801
	if ( childp -> cyclehead != oldhead ) {
802
	    oldhead = childp -> cyclehead;
803
	    inheritflags( childp );
804
	}
805
#	ifdef DEBUG
806
	    if ( debug & PROPDEBUG ) {
807
		printf( "[doflags] " );
808
		printname( childp );
809
		printf( " inherits printflag %d and propfraction %f\n" ,
810
			childp -> printflag , childp -> propfraction );
811
	    }
812
#	endif /* DEBUG */
813
	if ( ! childp -> printflag ) {
814
		/*
815
		 *	printflag is off
816
		 *	it gets turned on by
817
		 *	being on -f list,
818
		 *	or there not being any -f list and not being on -e list.
819
		 */
820
	    if (   onlist( flist , childp -> name )
821
		|| ( !fflag && !onlist( elist , childp -> name ) ) ) {
822
		childp -> printflag = TRUE;
823
	    }
824
	} else {
825
		/*
826
		 *	this function has printing parents:
827
		 *	maybe someone wants to shut it up
828
		 *	by putting it on -e list.  (but favor -f over -e)
829
		 */
830
	    if (  ( !onlist( flist , childp -> name ) )
831
		&& onlist( elist , childp -> name ) ) {
832
		childp -> printflag = FALSE;
833
	    }
834
	}
835
	if ( childp -> propfraction == 0.0 ) {
836
		/*
837
		 *	no parents to pass time to.
838
		 *	collect time from children if
839
		 *	its on -F list,
840
		 *	or there isn't any -F list and its not on -E list.
841
		 */
842
	    if ( onlist( Flist , childp -> name )
843
		|| ( !Fflag && !onlist( Elist , childp -> name ) ) ) {
844
		    childp -> propfraction = 1.0;
845
	    }
846
	} else {
847
		/*
848
		 *	it has parents to pass time to,
849
		 *	but maybe someone wants to shut it up
850
		 *	by puttting it on -E list.  (but favor -F over -E)
851
		 */
852
	    if (  !onlist( Flist , childp -> name )
853
		&& onlist( Elist , childp -> name ) ) {
854
		childp -> propfraction = 0.0;
855
	    }
856
	}
857
	childp -> propself = childp -> time * childp -> propfraction;
858
	printtime += childp -> propself;
859
#	ifdef DEBUG
860
	    if ( debug & PROPDEBUG ) {
861
		printf( "[doflags] " );
862
		printname( childp );
863
		printf( " ends up with printflag %d and propfraction %f\n" ,
864
			childp -> printflag , childp -> propfraction );
865
		printf( "time %f propself %f printtime %f\n" ,
866
			childp -> time , childp -> propself , printtime );
867
	    }
868
#	endif /* DEBUG */
869
    }
870
}
871
872
    /*
873
     *	check if any parent of this child
874
     *	(or outside parents of this cycle)
875
     *	have their print flags on and set the
876
     *	print flag of the child (cycle) appropriately.
877
     *	similarly, deal with propagation fractions from parents.
878
     */
879
void
880
inheritflags(nltype *childp)
881
{
882
    nltype	*headp;
883
    arctype	*arcp;
884
    nltype	*parentp;
885
    nltype	*memp;
886
887
    headp = childp -> cyclehead;
888
    if ( childp == headp ) {
889
	    /*
890
	     *	just a regular child, check its parents
891
	     */
892
	childp -> printflag = FALSE;
893
	childp -> propfraction = 0.0;
894
	for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) {
895
	    parentp = arcp -> arc_parentp;
896
	    if ( childp == parentp ) {
897
		continue;
898
	    }
899
	    childp -> printflag |= parentp -> printflag;
900
		/*
901
		 *	if the child was never actually called
902
		 *	(e.g. this arc is static (and all others are, too))
903
		 *	no time propagates along this arc.
904
		 */
905
	    if ( arcp -> arc_flags & DEADARC ) {
906
		continue;
907
	    }
908
	    if ( childp -> npropcall ) {
909
		childp -> propfraction += parentp -> propfraction
910
					* ( ( (double) arcp -> arc_count )
911
					  / ( (double) childp -> npropcall ) );
912
	    }
913
	}
914
    } else {
915
	    /*
916
	     *	its a member of a cycle, look at all parents from
917
	     *	outside the cycle
918
	     */
919
	headp -> printflag = FALSE;
920
	headp -> propfraction = 0.0;
921
	for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) {
922
	    for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) {
923
		if ( arcp -> arc_parentp -> cyclehead == headp ) {
924
		    continue;
925
		}
926
		parentp = arcp -> arc_parentp;
927
		headp -> printflag |= parentp -> printflag;
928
		    /*
929
		     *	if the cycle was never actually called
930
		     *	(e.g. this arc is static (and all others are, too))
931
		     *	no time propagates along this arc.
932
		     */
933
		if ( arcp -> arc_flags & DEADARC ) {
934
		    continue;
935
		}
936
		if ( headp -> npropcall ) {
937
		    headp -> propfraction += parentp -> propfraction
938
					* ( ( (double) arcp -> arc_count )
939
					  / ( (double) headp -> npropcall ) );
940
		}
941
	    }
942
	}
943
	for ( memp = headp ; memp ; memp = memp -> cnext ) {
944
	    memp -> printflag = headp -> printflag;
945
	    memp -> propfraction = headp -> propfraction;
946
	}
947
    }
948
}