4.3BSD - /usr/src/ucb/gprof/dfn.c

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

Defined functions

Defined variables

Defined struct's

Defined typedef's

Defined macros