gprof/dfn.c

   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 }