Back to index

cell-binutils  2.17cvs20070401
cg_dfn.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 1983, 1993
00003  *      The Regents of the University of California.  All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  * 1. Redistributions of source code must retain the above copyright
00009  *    notice, this list of conditions and the following disclaimer.
00010  * 2. Redistributions in binary form must reproduce the above copyright
00011  *    notice, this list of conditions and the following disclaimer in the
00012  *    documentation and/or other materials provided with the distribution.
00013  * 3. Neither the name of the University nor the names of its contributors
00014  *    may be used to endorse or promote products derived from this software
00015  *    without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00018  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00021  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00022  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00023  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00024  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00026  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00027  * SUCH DAMAGE.
00028  */
00029 #include "libiberty.h"
00030 #include "gprof.h"
00031 #include "search_list.h"
00032 #include "source.h"
00033 #include "symtab.h"
00034 #include "cg_arcs.h"
00035 #include "cg_dfn.h"
00036 #include "utils.h"
00037 
00038 #define       DFN_INCR_DEPTH (128)
00039 
00040 typedef struct
00041   {
00042     Sym *sym;
00043     int cycle_top;
00044   }
00045 DFN_Stack;
00046 
00047 static bfd_boolean is_numbered (Sym *);
00048 static bfd_boolean is_busy (Sym *);
00049 static void find_cycle (Sym *);
00050 static void pre_visit (Sym *);
00051 static void post_visit (Sym *);
00052 
00053 DFN_Stack *dfn_stack = NULL;
00054 int dfn_maxdepth = 0;
00055 int dfn_depth = 0;
00056 int dfn_counter = DFN_NAN;
00057 
00058 
00059 /*
00060  * Is CHILD already numbered?
00061  */
00062 static bfd_boolean
00063 is_numbered (Sym *child)
00064 {
00065   return child->cg.top_order != DFN_NAN && child->cg.top_order != DFN_BUSY;
00066 }
00067 
00068 
00069 /*
00070  * Is CHILD already busy?
00071  */
00072 static bfd_boolean
00073 is_busy (Sym *child)
00074 {
00075   if (child->cg.top_order == DFN_NAN)
00076     {
00077       return FALSE;
00078     }
00079   return TRUE;
00080 }
00081 
00082 
00083 /*
00084  * CHILD is part of a cycle.  Find the top caller into this cycle
00085  * that is not part of the cycle and make all functions in cycle
00086  * members of that cycle (top caller == caller with smallest
00087  * depth-first number).
00088  */
00089 static void
00090 find_cycle (Sym *child)
00091 {
00092   Sym *head = 0;
00093   Sym *tail;
00094   int cycle_top;
00095   int index;
00096 
00097   for (cycle_top = dfn_depth; cycle_top > 0; --cycle_top)
00098     {
00099       head = dfn_stack[cycle_top].sym;
00100       if (child == head)
00101        {
00102          break;
00103        }
00104       if (child->cg.cyc.head != child && child->cg.cyc.head == head)
00105        {
00106          break;
00107        }
00108     }
00109   if (cycle_top <= 0)
00110     {
00111       fprintf (stderr, "[find_cycle] couldn't find head of cycle\n");
00112       done (1);
00113     }
00114 #ifdef DEBUG
00115   if (debug_level & DFNDEBUG)
00116     {
00117       printf ("[find_cycle] dfn_depth %d cycle_top %d ",
00118              dfn_depth, cycle_top);
00119       if (head)
00120        {
00121          print_name (head);
00122        }
00123       else
00124        {
00125          printf ("<unknown>");
00126        }
00127       printf ("\n");
00128     }
00129 #endif
00130   if (cycle_top == dfn_depth)
00131     {
00132       /*
00133        * This is previous function, e.g. this calls itself.  Sort of
00134        * boring.
00135        *
00136        * Since we are taking out self-cycles elsewhere no need for
00137        * the special case, here.
00138        */
00139       DBG (DFNDEBUG,
00140           printf ("[find_cycle] ");
00141           print_name (child);
00142           printf ("\n"));
00143     }
00144   else
00145     {
00146       /*
00147        * Glom intervening functions that aren't already glommed into
00148        * this cycle.  Things have been glommed when their cyclehead
00149        * field points to the head of the cycle they are glommed
00150        * into.
00151        */
00152       for (tail = head; tail->cg.cyc.next; tail = tail->cg.cyc.next)
00153        {
00154          /* void: chase down to tail of things already glommed */
00155          DBG (DFNDEBUG,
00156               printf ("[find_cycle] tail ");
00157               print_name (tail);
00158               printf ("\n"));
00159        }
00160       /*
00161        * If what we think is the top of the cycle has a cyclehead
00162        * field, then it's not really the head of the cycle, which is
00163        * really what we want.
00164        */
00165       if (head->cg.cyc.head != head)
00166        {
00167          head = head->cg.cyc.head;
00168          DBG (DFNDEBUG, printf ("[find_cycle] new cyclehead ");
00169               print_name (head);
00170               printf ("\n"));
00171        }
00172       for (index = cycle_top + 1; index <= dfn_depth; ++index)
00173        {
00174          child = dfn_stack[index].sym;
00175          if (child->cg.cyc.head == child)
00176            {
00177              /*
00178               * Not yet glommed anywhere, glom it and fix any
00179               * children it has glommed.
00180               */
00181              tail->cg.cyc.next = child;
00182              child->cg.cyc.head = head;
00183              DBG (DFNDEBUG, printf ("[find_cycle] glomming ");
00184                  print_name (child);
00185                  printf (" onto ");
00186                  print_name (head);
00187                  printf ("\n"));
00188              for (tail = child; tail->cg.cyc.next; tail = tail->cg.cyc.next)
00189               {
00190                 tail->cg.cyc.next->cg.cyc.head = head;
00191                 DBG (DFNDEBUG, printf ("[find_cycle] and its tail ");
00192                      print_name (tail->cg.cyc.next);
00193                      printf (" onto ");
00194                      print_name (head);
00195                      printf ("\n"));
00196               }
00197            }
00198          else if (child->cg.cyc.head != head /* firewall */ )
00199            {
00200              fprintf (stderr, "[find_cycle] glommed, but not to head\n");
00201              done (1);
00202            }
00203        }
00204     }
00205 }
00206 
00207 
00208 /*
00209  * Prepare for visiting the children of PARENT.  Push a parent onto
00210  * the stack and mark it busy.
00211  */
00212 static void
00213 pre_visit (Sym *parent)
00214 {
00215   ++dfn_depth;
00216 
00217   if (dfn_depth >= dfn_maxdepth)
00218     {
00219       dfn_maxdepth += DFN_INCR_DEPTH;
00220       dfn_stack = xrealloc (dfn_stack, dfn_maxdepth * sizeof *dfn_stack);
00221     }
00222 
00223   dfn_stack[dfn_depth].sym = parent;
00224   dfn_stack[dfn_depth].cycle_top = dfn_depth;
00225   parent->cg.top_order = DFN_BUSY;
00226   DBG (DFNDEBUG, printf ("[pre_visit]\t\t%d:", dfn_depth);
00227        print_name (parent);
00228        printf ("\n"));
00229 }
00230 
00231 
00232 /*
00233  * Done with visiting node PARENT.  Pop PARENT off dfn_stack
00234  * and number functions if PARENT is head of a cycle.
00235  */
00236 static void
00237 post_visit (Sym *parent)
00238 {
00239   Sym *member;
00240 
00241   DBG (DFNDEBUG, printf ("[post_visit]\t%d: ", dfn_depth);
00242        print_name (parent);
00243        printf ("\n"));
00244   /*
00245    * Number functions and things in their cycles unless the function
00246    * is itself part of a cycle:
00247    */
00248   if (parent->cg.cyc.head == parent)
00249     {
00250       ++dfn_counter;
00251       for (member = parent; member; member = member->cg.cyc.next)
00252        {
00253          member->cg.top_order = dfn_counter;
00254          DBG (DFNDEBUG, printf ("[post_visit]\t\tmember ");
00255               print_name (member);
00256               printf ("-> cg.top_order = %d\n", dfn_counter));
00257        }
00258     }
00259   else
00260     {
00261       DBG (DFNDEBUG, printf ("[post_visit]\t\tis part of a cycle\n"));
00262     }
00263   --dfn_depth;
00264 }
00265 
00266 
00267 /*
00268  * Given this PARENT, depth first number its children.
00269  */
00270 void
00271 cg_dfn (Sym *parent)
00272 {
00273   Arc *arc;
00274 
00275   DBG (DFNDEBUG, printf ("[dfn] dfn( ");
00276        print_name (parent);
00277        printf (")\n"));
00278   /*
00279    * If we're already numbered, no need to look any further:
00280    */
00281   if (is_numbered (parent))
00282     {
00283       return;
00284     }
00285   /*
00286    * If we're already busy, must be a cycle:
00287    */
00288   if (is_busy (parent))
00289     {
00290       find_cycle (parent);
00291       return;
00292     }
00293   pre_visit (parent);
00294   /*
00295    * Recursively visit children:
00296    */
00297   for (arc = parent->cg.children; arc; arc = arc->next_child)
00298     {
00299       cg_dfn (arc->child);
00300     }
00301   post_visit (parent);
00302 }