gprof/cg_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 #include <stdio.h>
  20 #include "gprof.h"
  21 #include "cg_arcs.h"
  22 #include "cg_dfn.h"
  23 #include "symtab.h"
  24 #include "utils.h"
  25
  26 #define DFN_DEPTH       100
  27
  28 typedef struct {
  29     Sym *sym;
  30     int cycle_top;
  31 } DFN_Stack;
  32
  33 DFN_Stack dfn_stack[DFN_DEPTH];
  34 int     dfn_depth = 0;
  35 int     dfn_counter = DFN_NAN;
  36
  37
  38 /*
  39  * Is CHILD already numbered?
  40  */
  41 static bool
  42 DEFUN(is_numbered, (child), Sym *child)
  43 {
  44     return child->cg.top_order != DFN_NAN && child->cg.top_order != DFN_BUSY;
  45 } /* is_numbered */
  46
  47
  48 /*
  49  * Is CHILD already busy?
  50  */
  51 static bool
  52 DEFUN(is_busy, (child), Sym *child)
  53 {
  54     if (child->cg.top_order == DFN_NAN) {
  55         return FALSE;
  56     } /* if */
  57     return TRUE;
  58 } /* is_busy */
  59
  60
  61 /*
  62  * CHILD is part of a cycle.  Find the top caller into this cycle
  63  * that is not part of the cycle and make all functions in cycle
  64  * members of that cycle (top caller == caller with smallest
  65  * depth-first number).
  66  */
  67 static void
  68 DEFUN(find_cycle, (child), Sym *child)
  69 {
  70     Sym *head = 0;
  71     Sym *tail;
  72     int cycle_top;
  73     int index;
  74
  75     for (cycle_top = dfn_depth; cycle_top > 0; --cycle_top) {
  76         head = dfn_stack[cycle_top].sym;
  77         if (child == head) {
  78             break;
  79         } /* if */
  80         if (child->cg.cyc.head != child && child->cg.cyc.head == head) {
  81             break;
  82         } /* if */
  83     } /* for */
  84     if (cycle_top <= 0) {
  85         fprintf(stderr, "[find_cycle] couldn't find head of cycle\n");
  86         done(1);
  87     } /* if */
  88     DBG(DFNDEBUG, printf("[find_cycle] dfn_depth %d cycle_top %d ",
  89                          dfn_depth, cycle_top);
  90         if (head) {
  91             print_name(head);
  92         } else {
  93             printf("<unknown>");
  94         } /* if */
  95         printf("\n"));
  96     if (cycle_top == dfn_depth) {
  97         /*
  98          * This is previous function, e.g. this calls itself.  Sort of
  99          * boring.
 100          *
 101          * Since we are taking out self-cycles elsewhere no need for
 102          * the special case, here.
 103          */
 104         DBG(DFNDEBUG,
 105             printf("[find_cycle] "); print_name(child); printf("\n"));
 106     } else {
 107         /*
 108          * Glom intervening functions that aren't already glommed into
 109          * this cycle.  Things have been glommed when their cyclehead
 110          * field points to the head of the cycle they are glommed
 111          * into.
 112          */
 113         for (tail = head; tail->cg.cyc.next; tail = tail->cg.cyc.next) {
 114             /* void: chase down to tail of things already glommed */
 115             DBG(DFNDEBUG,
 116                 printf("[find_cycle] tail "); print_name(tail); printf("\n"));
 117         } /* for */
 118         /*
 119          * If what we think is the top of the cycle has a cyclehead
 120          * field, then it's not really the head of the cycle, which is
 121          * really what we want.
 122          */
 123         if (head->cg.cyc.head != head) {
 124             head = head->cg.cyc.head;
 125             DBG(DFNDEBUG, printf("[find_cycle] new cyclehead ");
 126                 print_name(head); printf("\n"));
 127         } /* if */
 128         for (index = cycle_top + 1; index <= dfn_depth; ++index) {
 129             child = dfn_stack[index].sym;
 130             if (child->cg.cyc.head == child) {
 131                 /*
 132                  * Not yet glommed anywhere, glom it and fix any
 133                  * children it has glommed.
 134                  */
 135                 tail->cg.cyc.next = child;
 136                 child->cg.cyc.head = head;
 137                 DBG(DFNDEBUG, printf("[find_cycle] glomming ");
 138                     print_name(child); printf(" onto "); print_name(head);
 139                     printf("\n"));
 140                 for (tail = child; tail->cg.cyc.next; tail = tail->cg.cyc.next)
 141                 {
 142                     tail->cg.cyc.next->cg.cyc.head = head;
 143                     DBG(DFNDEBUG, printf("[find_cycle] and its tail ");
 144                         print_name(tail->cg.cyc.next); printf(" onto ");
 145                         print_name(head); printf("\n"));
 146                 } /* for */
 147             } else if (child->cg.cyc.head != head /* firewall */) {
 148                 fprintf(stderr, "[find_cycle] glommed, but not to head\n");
 149                 done(1);
 150             } /* if */
 151         } /* for */
 152     } /* if */
 153 } /* find_cycle */
 154
 155
 156 /*
 157  * Prepare for visiting the children of PARENT.  Push a parent onto
 158  * the stack and mark it busy.
 159  */
 160 static void
 161 DEFUN(pre_visit, (parent), Sym *parent)
 162 {
 163     ++dfn_depth;
 164     if (dfn_depth >= DFN_DEPTH) {
 165         fprintf(stderr, "[pre_visit] dfn_stack overflow\n");
 166         done(1);
 167     } /* if */
 168     dfn_stack[dfn_depth].sym = parent;
 169     dfn_stack[dfn_depth].cycle_top = dfn_depth;
 170     parent->cg.top_order = DFN_BUSY;
 171     DBG(DFNDEBUG, printf("[pre_visit]\t\t%d:", dfn_depth); print_name(parent);
 172         printf("\n"));
 173 } /* pre_visit */
 174
 175
 176 /*
 177  * Done with visiting node PARENT.  Pop PARENT off dfn_stack
 178  * and number functions if PARENT is head of a cycle.
 179  */
 180 static void
 181 DEFUN(post_visit, (parent), Sym *parent)
 182 {
 183     Sym *member;
 184
 185     DBG(DFNDEBUG, printf("[post_visit]\t%d: ", dfn_depth);
 186         print_name(parent); printf("\n"));
 187     /*
 188      * Number functions and things in their cycles unless the function
 189      * is itself part of a cycle:
 190      */
 191     if (parent->cg.cyc.head == parent) {
 192         ++dfn_counter;
 193         for (member = parent; member; member = member->cg.cyc.next) {
 194             member->cg.top_order = dfn_counter;
 195             DBG(DFNDEBUG, printf("[post_visit]\t\tmember ");
 196                 print_name(member);
 197                 printf("-> cg.top_order = %d\n", dfn_counter));
 198         } /* for */
 199     } else {
 200         DBG(DFNDEBUG, printf("[post_visit]\t\tis part of a cycle\n"));
 201     } /* if */
 202     --dfn_depth;
 203 } /* post_visit */
 204
 205
 206 /*
 207  * Given this PARENT, depth first number its children.
 208  */
 209 void
 210 DEFUN(cg_dfn, (parent), Sym *parent)
 211 {
 212     Arc *arc;
 213
 214     DBG(DFNDEBUG, printf("[dfn] dfn( "); print_name(parent); printf(")\n"));
 215     /*
 216      * If we're already numbered, no need to look any further:
 217      */
 218     if (is_numbered(parent)) {
 219         return;
 220     } /* if */
 221     /*
 222      * If we're already busy, must be a cycle:
 223      */
 224     if (is_busy(parent)) {
 225         find_cycle(parent);
 226         return;
 227     } /* if */
 228     pre_visit(parent);
 229     /*
 230      * Recursively visit children:
 231      */
 232     for (arc = parent->cg.children; arc; arc = arc->next_child) {
 233         cg_dfn(arc->child);
 234     } /* for */
 235     post_visit(parent);
 236 } /* cg_dfn */
 237
 238                         /*** end of cg_dfn.c ***/