Lines Matching +full:cycle +full:- +full:1
1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
10 * 1. Redistributions of source code must retain the above copyright
56 count , parentp -> name , childp -> name ); in addarc()
67 arcp -> arc_count , count ); in addarc()
70 arcp -> arc_count += count; in addarc()
73 arcp = (arctype *)calloc( 1 , sizeof *arcp ); in addarc()
75 errx( 1 , "malloc failed" ); in addarc()
76 arcp -> arc_parentp = parentp; in addarc()
77 arcp -> arc_childp = childp; in addarc()
78 arcp -> arc_count = count; in addarc()
82 arcp -> arc_childlist = parentp -> children; in addarc()
83 parentp -> children = arcp; in addarc()
87 arcp -> arc_parentlist = childp -> parents; in addarc()
88 childp -> parents = arcp; in addarc()
107 return (*npp1) -> toporder - (*npp2) -> toporder; in topcmp()
121 * count self-recursive calls. in doarcs()
125 parentp -> childtime = 0.0; in doarcs()
128 parentp -> ncall -= arcp -> arc_count; in doarcs()
129 parentp -> selfcalls = arcp -> arc_count; in doarcs()
131 parentp -> selfcalls = 0; in doarcs()
133 parentp -> npropcall = parentp -> ncall; in doarcs()
134 parentp -> propfraction = 0.0; in doarcs()
135 parentp -> propself = 0.0; in doarcs()
136 parentp -> propchild = 0.0; in doarcs()
137 parentp -> printflag = FALSE; in doarcs()
138 parentp -> toporder = DFN_NAN; in doarcs()
139 parentp -> cycleno = 0; in doarcs()
140 parentp -> cyclehead = parentp; in doarcs()
141 parentp -> cnext = 0; in doarcs()
143 for ( pass = 1 ; ; pass++ ) { in doarcs()
150 if ( parentp -> toporder == DFN_NAN ) { in doarcs()
155 * link together nodes on the same cycle in doarcs()
168 printf("[doarcs] pass %ld, cycle(s) %d\n" , pass , ncycle ); in doarcs()
171 if ( pass == 1 ) { in doarcs()
175 "to reduce the maximum cycle size to", cyclethreshold ); in doarcs()
182 parentp -> toporder = DFN_NAN; in doarcs()
183 parentp -> cycleno = 0; in doarcs()
184 parentp -> cyclehead = parentp; in doarcs()
185 parentp -> cnext = 0; in doarcs()
188 if ( pass > 1 ) { in doarcs()
198 errx( 1 , "[doarcs] ran out of memory for topo sorting" ); in doarcs()
199 for ( index = 0 ; index < nname ; index += 1 ) { in doarcs()
206 for ( index = 0 ; index < nname ; index += 1 ) { in doarcs()
208 printf( "%d:" , topsortnlp[ index ] -> toporder ); in doarcs()
230 * and cycle headers. in doarcs()
234 errx( 1 , "ran out of memory for sorting" ); in doarcs()
238 for ( index = 1 ; index <= ncycle ; index++ ) { in doarcs()
239 timesortnlp[nname+index-1] = &cyclenl[index]; in doarcs()
243 timesortnlp[ index ] -> index = index + 1; in doarcs()
254 for ( index = 0 ; index < nname ; index += 1 ) { in dotime()
267 if ( parentp -> propfraction == 0.0 ) { in timepropagate()
273 for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) { in timepropagate()
274 childp = arcp -> arc_childp; in timepropagate()
275 if ( arcp -> arc_flags & DEADARC ) { in timepropagate()
278 if ( arcp -> arc_count == 0 ) { in timepropagate()
284 if ( childp -> propfraction == 0.0 ) { in timepropagate()
287 if ( childp -> cyclehead != childp ) { in timepropagate()
288 if ( parentp -> cycleno == childp -> cycleno ) { in timepropagate()
291 if ( parentp -> toporder <= childp -> toporder ) { in timepropagate()
294 childp = childp -> cyclehead; in timepropagate()
296 if ( parentp -> toporder <= childp -> toporder ) { in timepropagate()
301 if ( childp -> npropcall == 0 ) { in timepropagate()
307 arcp -> arc_time = childp -> time in timepropagate()
308 * ( ( (double) arcp -> arc_count ) / in timepropagate()
309 ( (double) childp -> npropcall ) ); in timepropagate()
310 arcp -> arc_childtime = childp -> childtime in timepropagate()
311 * ( ( (double) arcp -> arc_count ) / in timepropagate()
312 ( (double) childp -> npropcall ) ); in timepropagate()
313 share = arcp -> arc_time + arcp -> arc_childtime; in timepropagate()
314 parentp -> childtime += share; in timepropagate()
316 * ( 1 - propfraction ) gets lost along the way in timepropagate()
318 propshare = parentp -> propfraction * share; in timepropagate()
322 parentp -> propchild += propshare; in timepropagate()
323 arcp -> arc_time *= parentp -> propfraction; in timepropagate()
324 arcp -> arc_childtime *= parentp -> propfraction; in timepropagate()
326 * add this share to the parent's cycle header, if any. in timepropagate()
328 if ( parentp -> cyclehead != parentp ) { in timepropagate()
329 parentp -> cyclehead -> childtime += share; in timepropagate()
330 parentp -> cyclehead -> propchild += propshare; in timepropagate()
337 childp -> time , childp -> childtime , in timepropagate()
338 arcp -> arc_count , childp -> npropcall ); in timepropagate()
352 int cycle; in cyclelink() local
357 * Count the number of cycles, and initialize the cycle lists in cyclelink()
364 if ( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) { in cyclelink()
365 ncycle += 1; in cyclelink()
369 * cyclenl is indexed by cycle number: in cyclelink()
370 * i.e. it is origin 1, not origin 0. in cyclelink()
372 cyclenl = (nltype *) calloc( ncycle + 1 , sizeof( nltype ) ); in cyclelink()
374 errx( 1 , "no room for %zu bytes of cycle headers" , in cyclelink()
375 ( ncycle + 1 ) * sizeof( nltype ) ); in cyclelink()
378 * number them, accumulate the data for the cycle in cyclelink()
380 cycle = 0; in cyclelink()
382 if ( !( nlp -> cyclehead == nlp && nlp -> cnext != 0 ) ) { in cyclelink()
385 cycle += 1; in cyclelink()
386 cyclenlp = &cyclenl[cycle]; in cyclelink()
387 cyclenlp -> name = 0; /* the name */ in cyclelink()
388 cyclenlp -> value = 0; /* the pc entry point */ in cyclelink()
389 cyclenlp -> time = 0.0; /* ticks in this routine */ in cyclelink()
390 cyclenlp -> childtime = 0.0; /* cumulative ticks in children */ in cyclelink()
391 cyclenlp -> ncall = 0; /* how many times called */ in cyclelink()
392 cyclenlp -> selfcalls = 0; /* how many calls to self */ in cyclelink()
393 cyclenlp -> propfraction = 0.0; /* what % of time propagates */ in cyclelink()
394 cyclenlp -> propself = 0.0; /* how much self time propagates */ in cyclelink()
395 cyclenlp -> propchild = 0.0; /* how much child time propagates */ in cyclelink()
396 cyclenlp -> printflag = TRUE; /* should this be printed? */ in cyclelink()
397 cyclenlp -> index = 0; /* index in the graph list */ in cyclelink()
398 cyclenlp -> toporder = DFN_NAN; /* graph call chain top-sort order */ in cyclelink()
399 cyclenlp -> cycleno = cycle; /* internal number of cycle on */ in cyclelink()
400 cyclenlp -> cyclehead = cyclenlp; /* pointer to head of cycle */ in cyclelink()
401 cyclenlp -> cnext = nlp; /* pointer to next member of cycle */ in cyclelink()
402 cyclenlp -> parents = 0; /* list of caller arcs */ in cyclelink()
403 cyclenlp -> children = 0; /* list of callee arcs */ in cyclelink()
408 printf( " is the head of cycle %d\n" , cycle ); in cyclelink()
412 * link members to cycle header in cyclelink()
414 for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { in cyclelink()
415 memberp -> cycleno = cycle; in cyclelink()
416 memberp -> cyclehead = cyclenlp; in cyclelink()
419 * count calls from outside the cycle in cyclelink()
420 * and those among cycle members in cyclelink()
422 for ( memberp = nlp ; memberp ; memberp = memberp -> cnext ) { in cyclelink()
423 for ( arcp=memberp->parents ; arcp ; arcp=arcp->arc_parentlist ) { in cyclelink()
424 if ( arcp -> arc_parentp == memberp ) { in cyclelink()
427 if ( arcp -> arc_parentp -> cycleno == cycle ) { in cyclelink()
428 cyclenlp -> selfcalls += arcp -> arc_count; in cyclelink()
430 cyclenlp -> npropcall += arcp -> arc_count; in cyclelink()
456 * calculate the size of the cycle, and find nodes that in cycleanalyze()
457 * exit the cycle as they are desirable targets to cut in cycleanalyze()
460 for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) { in cycleanalyze()
462 for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) { in cycleanalyze()
463 size += 1; in cycleanalyze()
464 nlp -> parentcnt = 0; in cycleanalyze()
465 nlp -> flags &= ~HASCYCLEXIT; in cycleanalyze()
466 for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) { in cycleanalyze()
467 nlp -> parentcnt += 1; in cycleanalyze()
468 if ( arcp -> arc_parentp -> cycleno != cycleno ) in cycleanalyze()
469 nlp -> flags |= HASCYCLEXIT; in cycleanalyze()
475 cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) ); in cycleanalyze()
477 errx( 1, "no room for %zu bytes of cycle stack" , in cycleanalyze()
478 ( size + 1 ) * sizeof( arctype * ) ); in cycleanalyze()
481 printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" , in cycleanalyze()
485 for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) { in cycleanalyze()
487 nlp -> flags |= CYCLEHEAD; in cycleanalyze()
489 nlp -> flags &= ~CYCLEHEAD; in cycleanalyze()
497 endlist = &clp -> list[ clp -> size ]; in cycleanalyze()
498 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) in cycleanalyze()
499 (*arcpp) -> arc_cyclecnt--; in cycleanalyze()
500 cyclecnt--; in cycleanalyze()
501 clp = clp -> next; in cycleanalyze()
522 for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) { in descend()
526 if ( arcp -> arc_childp -> cycleno != node -> cycleno in descend()
527 || ( arcp -> arc_childp -> flags & VISITED ) in descend()
528 || ( arcp -> arc_flags & DEADARC ) ) in descend()
534 if ( arcp -> arc_childp -> flags & CYCLEHEAD ) { in descend()
539 arcp -> arc_childp -> flags |= VISITED; in descend()
540 ret = descend( arcp -> arc_childp , stkstart , stkp + 1 ); in descend()
541 arcp -> arc_childp -> flags &= ~VISITED; in descend()
560 size = stkend - stkstart + 1; in addcycle()
561 if ( size <= 1 ) in addcycle()
569 for ( clp = cyclehead ; clp ; clp = clp -> next ) { in addcycle()
570 if ( clp -> size != size ) in addcycle()
573 endlist = &clp -> list[ size ]; in addcycle()
574 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) { in addcycle()
588 calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) ); in addcycle()
591 sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) ); in addcycle()
595 endlist = &clp -> list[ size ]; in addcycle()
596 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) { in addcycle()
600 arcp -> arc_cyclecnt++; in addcycle()
601 if ( ( arcp -> arc_flags & ONLIST ) == 0 ) { in addcycle()
602 arcp -> arc_flags |= ONLIST; in addcycle()
603 arcp -> arc_next = archead; in addcycle()
607 clp -> size = size; in addcycle()
608 clp -> next = cyclehead; in addcycle()
645 if ( arcp -> arc_cyclecnt == 0 ) { in compresslist()
646 arcp -> arc_flags &= ~ONLIST; in compresslist()
647 *endlist = arcp -> arc_next; in compresslist()
648 arcp -> arc_next = 0; in compresslist()
652 if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) { in compresslist()
653 if ( arcp -> arc_cyclecnt > maxexitcnt || in compresslist()
654 ( arcp -> arc_cyclecnt == maxexitcnt && in compresslist()
655 arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) { in compresslist()
656 maxexitcnt = arcp -> arc_cyclecnt; in compresslist()
659 } else if ( arcp -> arc_childp -> parentcnt > 1 ) { in compresslist()
660 if ( arcp -> arc_cyclecnt > maxwithparentcnt || in compresslist()
661 ( arcp -> arc_cyclecnt == maxwithparentcnt && in compresslist()
662 arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) { in compresslist()
663 maxwithparentcnt = arcp -> arc_cyclecnt; in compresslist()
667 if ( arcp -> arc_cyclecnt > maxnoparentcnt || in compresslist()
668 ( arcp -> arc_cyclecnt == maxnoparentcnt && in compresslist()
669 arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) { in compresslist()
670 maxnoparentcnt = arcp -> arc_cyclecnt; in compresslist()
674 endlist = &arcp -> arc_next; in compresslist()
675 arcp = arcp -> arc_next; in compresslist()
679 * first choice is edge leading to node with out-of-cycle parent in compresslist()
688 * other in-cycle parent in compresslist()
704 maxarcp -> arc_flags |= DEADARC; in compresslist()
705 maxarcp -> arc_childp -> parentcnt -= 1; in compresslist()
706 maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count; in compresslist()
709 printf( "%s delete %s arc: %s (%ld) -> %s from %u cycle(s)\n" , in compresslist()
710 "[compresslist]" , type , maxarcp -> arc_parentp -> name , in compresslist()
711 maxarcp -> arc_count , maxarcp -> arc_childp -> name , in compresslist()
712 maxarcp -> arc_cyclecnt ); in compresslist()
715 printf( "\t%s to %s with %ld calls\n" , maxarcp -> arc_parentp -> name , in compresslist()
716 maxarcp -> arc_childp -> name , maxarcp -> arc_count ); in compresslist()
719 endlist = &clp -> list[ clp -> size ]; in compresslist()
720 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) in compresslist()
721 if ( (*arcpp) -> arc_flags & DEADARC ) in compresslist()
724 prev = &clp -> next; in compresslist()
725 clp = clp -> next; in compresslist()
728 for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) in compresslist()
729 (*arcpp) -> arc_cyclecnt--; in compresslist()
730 cyclecnt--; in compresslist()
731 *prev = clp -> next; in compresslist()
732 clp = clp -> next; in compresslist()
744 arcpp = clp -> list; in printsubcycle()
745 printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name , in printsubcycle()
746 (*arcpp) -> arc_parentp -> cycleno ) ; in printsubcycle()
747 for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ ) in printsubcycle()
748 printf( "\t(%ld) -> %s\n" , (*arcpp) -> arc_count , in printsubcycle()
749 (*arcpp) -> arc_childp -> name ) ; in printsubcycle()
756 int cycle; in cycletime() local
760 for ( cycle = 1 ; cycle <= ncycle ; cycle += 1 ) { in cycletime()
761 cyclenlp = &cyclenl[ cycle ]; in cycletime()
762 for ( childp = cyclenlp -> cnext ; childp ; childp = childp -> cnext ) { in cycletime()
763 if ( childp -> propfraction == 0.0 ) { in cycletime()
766 * that were excluded with -E in cycletime()
770 cyclenlp -> time += childp -> time; in cycletime()
772 cyclenlp -> propself = cyclenlp -> propfraction * cyclenlp -> time; in cycletime()
791 for ( index = nname-1 ; index >= 0 ; index -= 1 ) { in doflags()
794 * if we haven't done this function or cycle, in doflags()
797 * since we do all members of a cycle (and the cycle itself) in doflags()
798 * as we hit the first member of the cycle. in doflags()
800 if ( childp -> cyclehead != oldhead ) { in doflags()
801 oldhead = childp -> cyclehead; in doflags()
809 childp -> printflag , childp -> propfraction ); in doflags()
812 if ( ! childp -> printflag ) { in doflags()
816 * being on -f list, in doflags()
817 * or there not being any -f list and not being on -e list. in doflags()
819 if ( onlist( flist , childp -> name ) in doflags()
820 || ( !fflag && !onlist( elist , childp -> name ) ) ) { in doflags()
821 childp -> printflag = TRUE; in doflags()
827 * by putting it on -e list. (but favor -f over -e) in doflags()
829 if ( ( !onlist( flist , childp -> name ) ) in doflags()
830 && onlist( elist , childp -> name ) ) { in doflags()
831 childp -> printflag = FALSE; in doflags()
834 if ( childp -> propfraction == 0.0 ) { in doflags()
838 * its on -F list, in doflags()
839 * or there isn't any -F list and its not on -E list. in doflags()
841 if ( onlist( Flist , childp -> name ) in doflags()
842 || ( !Fflag && !onlist( Elist , childp -> name ) ) ) { in doflags()
843 childp -> propfraction = 1.0; in doflags()
849 * by putting it on -E list. (but favor -F over -E) in doflags()
851 if ( !onlist( Flist , childp -> name ) in doflags()
852 && onlist( Elist , childp -> name ) ) { in doflags()
853 childp -> propfraction = 0.0; in doflags()
856 childp -> propself = childp -> time * childp -> propfraction; in doflags()
857 printtime += childp -> propself; in doflags()
863 childp -> printflag , childp -> propfraction ); in doflags()
865 childp -> time , childp -> propself , printtime ); in doflags()
873 * (or outside parents of this cycle)
875 * print flag of the child (cycle) appropriately.
886 headp = childp -> cyclehead; in inheritflags()
891 childp -> printflag = FALSE; in inheritflags()
892 childp -> propfraction = 0.0; in inheritflags()
893 for (arcp = childp -> parents ; arcp ; arcp = arcp -> arc_parentlist) { in inheritflags()
894 parentp = arcp -> arc_parentp; in inheritflags()
898 childp -> printflag |= parentp -> printflag; in inheritflags()
904 if ( arcp -> arc_flags & DEADARC ) { in inheritflags()
907 if ( childp -> npropcall ) { in inheritflags()
908 childp -> propfraction += parentp -> propfraction in inheritflags()
909 * ( ( (double) arcp -> arc_count ) in inheritflags()
910 / ( (double) childp -> npropcall ) ); in inheritflags()
915 * its a member of a cycle, look at all parents from in inheritflags()
916 * outside the cycle in inheritflags()
918 headp -> printflag = FALSE; in inheritflags()
919 headp -> propfraction = 0.0; in inheritflags()
920 for ( memp = headp -> cnext ; memp ; memp = memp -> cnext ) { in inheritflags()
921 for (arcp = memp->parents ; arcp ; arcp = arcp->arc_parentlist) { in inheritflags()
922 if ( arcp -> arc_parentp -> cyclehead == headp ) { in inheritflags()
925 parentp = arcp -> arc_parentp; in inheritflags()
926 headp -> printflag |= parentp -> printflag; in inheritflags()
928 * if the cycle was never actually called in inheritflags()
932 if ( arcp -> arc_flags & DEADARC ) { in inheritflags()
935 if ( headp -> npropcall ) { in inheritflags()
936 headp -> propfraction += parentp -> propfraction in inheritflags()
937 * ( ( (double) arcp -> arc_count ) in inheritflags()
938 / ( (double) headp -> npropcall ) ); in inheritflags()
942 for ( memp = headp ; memp ; memp = memp -> cnext ) { in inheritflags()
943 memp -> printflag = headp -> printflag; in inheritflags()
944 memp -> propfraction = headp -> propfraction; in inheritflags()