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