home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / gnu / djgpp / src / binutils.2 / gprof / dfn.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-30  |  7.2 KB  |  303 lines
  1. /*
  2.  * Copyright (c) 1983 Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms are permitted
  6.  * provided that: (1) source distributions retain this entire copyright
  7.  * notice and comment, and (2) distributions including binaries display
  8.  * the following acknowledgement:  ``This product includes software
  9.  * developed by the University of California, Berkeley and its contributors''
  10.  * in the documentation or other materials provided with the distribution
  11.  * and in all advertising materials mentioning features or use of this
  12.  * software. Neither the name of the University nor the names of its
  13.  * contributors may be used to endorse or promote products derived
  14.  * from this software without specific prior written permission.
  15.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  16.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  17.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  18.  */
  19.  
  20. #ifndef lint
  21. static char sccsid[] = "@(#)dfn.c    5.4 (Berkeley) 6/1/90";
  22. #endif /* not lint */
  23.  
  24. #include <stdio.h>
  25. #include "gprof.h"
  26.  
  27. #define    DFN_DEPTH    100
  28. struct dfnstruct {
  29.     nltype    *nlentryp;
  30.     int        cycletop;
  31. };
  32. typedef struct dfnstruct    dfntype;
  33.  
  34. dfntype    dfn_stack[ DFN_DEPTH ];
  35. int    dfn_depth = 0;
  36.  
  37. int    dfn_counter = DFN_NAN;
  38.  
  39.     /*
  40.      *    given this parent, depth first number its children.
  41.      */
  42. dfn( parentp )
  43.     nltype    *parentp;
  44. {
  45.     arctype    *arcp;
  46.  
  47. #   ifdef DEBUG
  48.     if ( debug & DFNDEBUG ) {
  49.         printf( "[dfn] dfn(" );
  50.         printname( parentp );
  51.         printf( ")\n" );
  52.     }
  53. #   endif DEBUG
  54.     /*
  55.      *    if we're already numbered, no need to look any furthur.
  56.      */
  57.     if ( dfn_numbered( parentp ) ) {
  58.     return;
  59.     }
  60.     /*
  61.      *    if we're already busy, must be a cycle
  62.      */
  63.     if ( dfn_busy( parentp ) ) {
  64.     dfn_findcycle( parentp );
  65.     return;
  66.     }
  67.     /*
  68.      *    visit yourself before your children
  69.      */
  70.     dfn_pre_visit( parentp );
  71.     /*
  72.      *    visit children
  73.      */
  74.     for ( arcp = parentp -> children ; arcp ; arcp = arcp -> arc_childlist ) {
  75.         dfn( arcp -> arc_childp );
  76.     }
  77.     /*
  78.      *    visit yourself after your children
  79.      */
  80.     dfn_post_visit( parentp );
  81. }
  82.  
  83.     /*
  84.      *    push a parent onto the stack and mark it busy
  85.      */
  86. dfn_pre_visit( parentp )
  87.     nltype    *parentp;
  88. {
  89.  
  90.     dfn_depth += 1;
  91.     if ( dfn_depth >= DFN_DEPTH ) {
  92.     fprintf( stderr , "[dfn] out of my depth (dfn_stack overflow)\n" );
  93.     exit( 1 );
  94.     }
  95.     dfn_stack[ dfn_depth ].nlentryp = parentp;
  96.     dfn_stack[ dfn_depth ].cycletop = dfn_depth;
  97.     parentp -> toporder = DFN_BUSY;
  98. #   ifdef DEBUG
  99.     if ( debug & DFNDEBUG ) {
  100.         printf( "[dfn_pre_visit]\t\t%d:" , dfn_depth );
  101.         printname( parentp );
  102.         printf( "\n" );
  103.     }
  104. #   endif DEBUG
  105. }
  106.  
  107.     /*
  108.      *    are we already numbered?
  109.      */
  110. bool
  111. dfn_numbered( childp )
  112.     nltype    *childp;
  113. {
  114.     
  115.     return ( childp -> toporder != DFN_NAN && childp -> toporder != DFN_BUSY );
  116. }
  117.  
  118.     /*
  119.      *    are we already busy?
  120.      */
  121. bool
  122. dfn_busy( childp )
  123.     nltype    *childp;
  124. {
  125.  
  126.     if ( childp -> toporder == DFN_NAN ) {
  127.     return FALSE;
  128.     }
  129.     return TRUE;
  130. }
  131.  
  132.     /*
  133.      *    MISSING: an explanation
  134.      */
  135. dfn_findcycle( childp )
  136.     nltype    *childp;
  137. {
  138.     int        cycletop;
  139.     nltype    *cycleheadp;
  140.     nltype    *tailp;
  141.     int        index;
  142.  
  143.     for ( cycletop = dfn_depth ; cycletop > 0 ; cycletop -= 1 ) {
  144.     cycleheadp = dfn_stack[ cycletop ].nlentryp;
  145.     if ( childp == cycleheadp ) {
  146.         break;
  147.     }
  148.     if ( childp -> cyclehead != childp &&
  149.         childp -> cyclehead == cycleheadp ) {
  150.         break;
  151.     }
  152.     }
  153.     if ( cycletop <= 0 ) {
  154.     fprintf( stderr , "[dfn_findcycle] couldn't find head of cycle\n" );
  155.     exit( 1 );
  156.     }
  157. #   ifdef DEBUG
  158.     if ( debug & DFNDEBUG ) {
  159.         printf( "[dfn_findcycle] dfn_depth %d cycletop %d " ,
  160.             dfn_depth , cycletop  );
  161.         printname( cycleheadp );
  162.         printf( "\n" );
  163.     }
  164. #   endif DEBUG
  165.     if ( cycletop == dfn_depth ) {
  166.         /*
  167.          *    this is previous function, e.g. this calls itself
  168.          *    sort of boring
  169.          */
  170.     dfn_self_cycle( childp );
  171.     } else {
  172.         /*
  173.          *    glom intervening functions that aren't already
  174.          *    glommed into this cycle.
  175.          *    things have been glommed when their cyclehead field
  176.          *    points to the head of the cycle they are glommed into.
  177.          */
  178.     for ( tailp = cycleheadp ; tailp -> cnext ; tailp = tailp -> cnext ) {
  179.         /* void: chase down to tail of things already glommed */
  180. #        ifdef DEBUG
  181.         if ( debug & DFNDEBUG ) {
  182.             printf( "[dfn_findcycle] tail " );
  183.             printname( tailp );
  184.             printf( "\n" );
  185.         }
  186. #        endif DEBUG
  187.     }
  188.         /*
  189.          *    if what we think is the top of the cycle
  190.          *    has a cyclehead field, then it's not really the
  191.          *    head of the cycle, which is really what we want
  192.          */    
  193.     if ( cycleheadp -> cyclehead != cycleheadp ) {
  194.         cycleheadp = cycleheadp -> cyclehead;
  195. #        ifdef DEBUG
  196.         if ( debug & DFNDEBUG ) {
  197.             printf( "[dfn_findcycle] new cyclehead " );
  198.             printname( cycleheadp );
  199.             printf( "\n" );
  200.         }
  201. #        endif DEBUG
  202.     }
  203.     for ( index = cycletop + 1 ; index <= dfn_depth ; index += 1 ) {
  204.         childp = dfn_stack[ index ].nlentryp;
  205.         if ( childp -> cyclehead == childp ) {
  206.             /*
  207.              *    not yet glommed anywhere, glom it
  208.              *    and fix any children it has glommed
  209.              */
  210.         tailp -> cnext = childp;
  211.         childp -> cyclehead = cycleheadp;
  212. #        ifdef DEBUG
  213.             if ( debug & DFNDEBUG ) {
  214.             printf( "[dfn_findcycle] glomming " );
  215.             printname( childp );
  216.             printf( " onto " );
  217.             printname( cycleheadp );
  218.             printf( "\n" );
  219.             }
  220. #        endif DEBUG
  221.         for ( tailp = childp ; tailp->cnext ; tailp = tailp->cnext ) {
  222.             tailp -> cnext -> cyclehead = cycleheadp;
  223. #            ifdef DEBUG
  224.             if ( debug & DFNDEBUG ) {
  225.                 printf( "[dfn_findcycle] and its tail " );
  226.                 printname( tailp -> cnext );
  227.                 printf( " onto " );
  228.                 printname( cycleheadp );
  229.                 printf( "\n" );
  230.             }
  231. #            endif DEBUG
  232.         }
  233.         } else if ( childp -> cyclehead != cycleheadp /* firewall */ ) {
  234.         fprintf( stderr ,
  235.             "[dfn_busy] glommed, but not to cyclehead\n" );
  236.         }
  237.     }
  238.     }
  239. }
  240.  
  241.     /*
  242.      *    deal with self-cycles
  243.      *    for lint: ARGSUSED
  244.      */
  245. dfn_self_cycle( parentp )
  246.     nltype    *parentp;
  247. {
  248.     /*
  249.      *    since we are taking out self-cycles elsewhere
  250.      *    no need for the special case, here.
  251.      */
  252. #   ifdef DEBUG
  253.     if ( debug & DFNDEBUG ) {
  254.         printf( "[dfn_self_cycle] " );
  255.         printname( parentp );
  256.         printf( "\n" );
  257.     }
  258. #   endif DEBUG
  259. }
  260.  
  261.     /*
  262.      *    visit a node after all its children
  263.      *    [MISSING: an explanation]
  264.      *    and pop it off the stack
  265.      */
  266. dfn_post_visit( parentp )
  267.     nltype    *parentp;
  268. {
  269.     nltype    *memberp;
  270.  
  271. #   ifdef DEBUG
  272.     if ( debug & DFNDEBUG ) {
  273.         printf( "[dfn_post_visit]\t%d: " , dfn_depth );
  274.         printname( parentp );
  275.         printf( "\n" );
  276.     }
  277. #   endif DEBUG
  278.     /*
  279.      *    number functions and things in their cycles
  280.      *    unless the function is itself part of a cycle
  281.      */
  282.     if ( parentp -> cyclehead == parentp ) {
  283.     dfn_counter += 1;
  284.     for ( memberp = parentp ; memberp ; memberp = memberp -> cnext ) {
  285.         memberp -> toporder = dfn_counter;
  286. #        ifdef DEBUG
  287.         if ( debug & DFNDEBUG ) {
  288.             printf( "[dfn_post_visit]\t\tmember " );
  289.             printname( memberp );
  290.             printf( " -> toporder = %d\n" , dfn_counter );
  291.         }
  292. #        endif DEBUG
  293.     }
  294.     } else {
  295. #    ifdef DEBUG
  296.         if ( debug & DFNDEBUG ) {
  297.         printf( "[dfn_post_visit]\t\tis part of a cycle\n" );
  298.         }
  299. #    endif DEBUG
  300.     }
  301.     dfn_depth -= 1;
  302. }
  303.