gprof/cg_dfn.c

   1 /*
   2  * Copyright (c) 1983, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29 #include "gprof.h"
  30 #include "libiberty.h"
  31 #include "search_list.h"
  32 #include "source.h"
  33 #include "symtab.h"
  34 #include "cg_arcs.h"
  35 #include "cg_dfn.h"
  36 #include "utils.h"
  37
  38 #define DFN_INCR_DEPTH (128)
  39
  40 typedef struct
  41   {
  42     Sym *sym;
  43     int cycle_top;
  44   }
  45 DFN_Stack;
  46
  47 static bfd_boolean is_numbered (Sym *);
  48 static bfd_boolean is_busy (Sym *);
  49 static void find_cycle (Sym *);
  50 static void pre_visit (Sym *);
  51 static void post_visit (Sym *);
  52
  53 DFN_Stack *dfn_stack = NULL;
  54 int dfn_maxdepth = 0;
  55 int dfn_depth = 0;
  56 int dfn_counter = DFN_NAN;
  57
  58
  59 /*
  60  * Is CHILD already numbered?
  61  */
  62 static bfd_boolean
  63 is_numbered (Sym *child)
  64 {
  65   return child->cg.top_order != DFN_NAN && child->cg.top_order != DFN_BUSY;
  66 }
  67
  68
  69 /*
  70  * Is CHILD already busy?
  71  */
  72 static bfd_boolean
  73 is_busy (Sym *child)
  74 {
  75   if (child->cg.top_order == DFN_NAN)
  76     {
  77       return FALSE;
  78     }
  79   return TRUE;
  80 }
  81
  82
  83 /*
  84  * CHILD is part of a cycle.  Find the top caller into this cycle
  85  * that is not part of the cycle and make all functions in cycle
  86  * members of that cycle (top caller == caller with smallest
  87  * depth-first number).
  88  */
  89 static void
  90 find_cycle (Sym *child)
  91 {
  92   Sym *head = 0;
  93   Sym *tail;
  94   int cycle_top;
  95   int index;
  96
  97   for (cycle_top = dfn_depth; cycle_top > 0; --cycle_top)
  98     {
  99       head = dfn_stack[cycle_top].sym;
 100       if (child == head)
 101         {
 102           break;
 103         }
 104       if (child->cg.cyc.head != child && child->cg.cyc.head == head)
 105         {
 106           break;
 107         }
 108     }
 109   if (cycle_top <= 0)
 110     {
 111       fprintf (stderr, "[find_cycle] couldn't find head of cycle\n");
 112       done (1);
 113     }
 114 #ifdef DEBUG
 115   if (debug_level & DFNDEBUG)
 116     {
 117       printf ("[find_cycle] dfn_depth %d cycle_top %d ",
 118               dfn_depth, cycle_top);
 119       if (head)
 120         {
 121           print_name (head);
 122         }
 123       else
 124         {
 125           printf ("<unknown>");
 126         }
 127       printf ("\n");
 128     }
 129 #endif
 130   if (cycle_top == dfn_depth)
 131     {
 132       /*
 133        * This is previous function, e.g. this calls itself.  Sort of
 134        * boring.
 135        *
 136        * Since we are taking out self-cycles elsewhere no need for
 137        * the special case, here.
 138        */
 139       DBG (DFNDEBUG,
 140            printf ("[find_cycle] ");
 141            print_name (child);
 142            printf ("\n"));
 143     }
 144   else
 145     {
 146       /*
 147        * Glom intervening functions that aren't already glommed into
 148        * this cycle.  Things have been glommed when their cyclehead
 149        * field points to the head of the cycle they are glommed
 150        * into.
 151        */
 152       for (tail = head; tail->cg.cyc.next; tail = tail->cg.cyc.next)
 153         {
 154           /* void: chase down to tail of things already glommed */
 155           DBG (DFNDEBUG,
 156                printf ("[find_cycle] tail ");
 157                print_name (tail);
 158                printf ("\n"));
 159         }
 160       /*
 161        * If what we think is the top of the cycle has a cyclehead
 162        * field, then it's not really the head of the cycle, which is
 163        * really what we want.
 164        */
 165       if (head->cg.cyc.head != head)
 166         {
 167           head = head->cg.cyc.head;
 168           DBG (DFNDEBUG, printf ("[find_cycle] new cyclehead ");
 169                print_name (head);
 170                printf ("\n"));
 171         }
 172       for (index = cycle_top + 1; index <= dfn_depth; ++index)
 173         {
 174           child = dfn_stack[index].sym;
 175           if (child->cg.cyc.head == child)
 176             {
 177               /*
 178                * Not yet glommed anywhere, glom it and fix any
 179                * children it has glommed.
 180                */
 181               tail->cg.cyc.next = child;
 182               child->cg.cyc.head = head;
 183               DBG (DFNDEBUG, printf ("[find_cycle] glomming ");
 184                    print_name (child);
 185                    printf (" onto ");
 186                    print_name (head);
 187                    printf ("\n"));
 188               for (tail = child; tail->cg.cyc.next; tail = tail->cg.cyc.next)
 189                 {
 190                   tail->cg.cyc.next->cg.cyc.head = head;
 191                   DBG (DFNDEBUG, printf ("[find_cycle] and its tail ");
 192                        print_name (tail->cg.cyc.next);
 193                        printf (" onto ");
 194                        print_name (head);
 195                        printf ("\n"));
 196                 }
 197             }
 198           else if (child->cg.cyc.head != head /* firewall */ )
 199             {
 200               fprintf (stderr, "[find_cycle] glommed, but not to head\n");
 201               done (1);
 202             }
 203         }
 204     }
 205 }
 206
 207
 208 /*
 209  * Prepare for visiting the children of PARENT.  Push a parent onto
 210  * the stack and mark it busy.
 211  */
 212 static void
 213 pre_visit (Sym *parent)
 214 {
 215   ++dfn_depth;
 216
 217   if (dfn_depth >= dfn_maxdepth)
 218     {
 219       dfn_maxdepth += DFN_INCR_DEPTH;
 220       dfn_stack = xrealloc (dfn_stack, dfn_maxdepth * sizeof *dfn_stack);
 221     }
 222
 223   dfn_stack[dfn_depth].sym = parent;
 224   dfn_stack[dfn_depth].cycle_top = dfn_depth;
 225   parent->cg.top_order = DFN_BUSY;
 226   DBG (DFNDEBUG, printf ("[pre_visit]\t\t%d:", dfn_depth);
 227        print_name (parent);
 228        printf ("\n"));
 229 }
 230
 231
 232 /*
 233  * Done with visiting node PARENT.  Pop PARENT off dfn_stack
 234  * and number functions if PARENT is head of a cycle.
 235  */
 236 static void
 237 post_visit (Sym *parent)
 238 {
 239   Sym *member;
 240
 241   DBG (DFNDEBUG, printf ("[post_visit]\t%d: ", dfn_depth);
 242        print_name (parent);
 243        printf ("\n"));
 244   /*
 245    * Number functions and things in their cycles unless the function
 246    * is itself part of a cycle:
 247    */
 248   if (parent->cg.cyc.head == parent)
 249     {
 250       ++dfn_counter;
 251       for (member = parent; member; member = member->cg.cyc.next)
 252         {
 253           member->cg.top_order = dfn_counter;
 254           DBG (DFNDEBUG, printf ("[post_visit]\t\tmember ");
 255                print_name (member);
 256                printf ("-> cg.top_order = %d\n", dfn_counter));
 257         }
 258     }
 259   else
 260     {
 261       DBG (DFNDEBUG, printf ("[post_visit]\t\tis part of a cycle\n"));
 262     }
 263   --dfn_depth;
 264 }
 265
 266
 267 /*
 268  * Given this PARENT, depth first number its children.
 269  */
 270 void
 271 cg_dfn (Sym *parent)
 272 {
 273   Arc *arc;
 274
 275   DBG (DFNDEBUG, printf ("[dfn] dfn( ");
 276        print_name (parent);
 277        printf (")\n"));
 278   /*
 279    * If we're already numbered, no need to look any further:
 280    */
 281   if (is_numbered (parent))
 282     {
 283       return;
 284     }
 285   /*
 286    * If we're already busy, must be a cycle:
 287    */
 288   if (is_busy (parent))
 289     {
 290       find_cycle (parent);
 291       return;
 292     }
 293   pre_visit (parent);
 294   /*
 295    * Recursively visit children:
 296    */
 297   for (arc = parent->cg.children; arc; arc = arc->next_child)
 298     {
 299       cg_dfn (arc->child);
 300     }
 301   post_visit (parent);
 302 }