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