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