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_print.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  33KB  |  1,273 lines
  1. #include "libiberty.h"
  2. #include "cg_arcs.h"
  3. #include "cg_print.h"
  4. #include "hist.h"
  5. #include "utils.h"
  6.  
  7. /*
  8.  * Return value of comparison functions used to sort tables:
  9.  */
  10. #define    LESSTHAN    -1
  11. #define    EQUALTO        0
  12. #define    GREATERTHAN    1
  13.  
  14. static void order_and_dump_functions_by_arcs PARAMS ((Arc **, unsigned long,
  15.                               int, Arc **,
  16.                               unsigned long *));
  17. /* declarations of automatically generated functions to output blurbs: */
  18. extern void bsd_callg_blurb PARAMS ((FILE * fp));
  19. extern void fsf_callg_blurb PARAMS ((FILE * fp));
  20.  
  21. double print_time = 0.0;
  22.  
  23.  
  24. static void
  25. DEFUN_VOID (print_header)
  26. {
  27.   if (first_output)
  28.     {
  29.       first_output = FALSE;
  30.     }
  31.   else
  32.     {
  33.       printf ("\f\n");
  34.     }
  35.   if (!bsd_style_output)
  36.     {
  37.       if (print_descriptions)
  38.     {
  39.       printf ("\t\t     Call graph (explanation follows)\n\n");
  40.     }
  41.       else
  42.     {
  43.       printf ("\t\t\tCall graph\n\n");
  44.     }
  45.     }
  46.   printf ("\ngranularity: each sample hit covers %ld byte(s)",
  47.       (long) hist_scale * sizeof (UNIT));
  48.   if (print_time > 0.0)
  49.     {
  50.       printf (" for %.2f%% of %.2f seconds\n\n",
  51.           100.0 / print_time, print_time / hz);
  52.     }
  53.   else
  54.     {
  55.       printf (" no time propagated\n\n");
  56.       /*
  57.        * This doesn't hurt, since all the numerators will be 0.0:
  58.        */
  59.       print_time = 1.0;
  60.     }
  61.   if (bsd_style_output)
  62.     {
  63.       printf ("%6.6s %5.5s %7.7s %11.11s %7.7s/%-7.7s     %-8.8s\n",
  64.           "", "", "", "", "called", "total", "parents");
  65.       printf ("%-6.6s %5.5s %7.7s %11.11s %7.7s+%-7.7s %-8.8s\t%5.5s\n",
  66.           "index", "%time", "self", "descendents",
  67.           "called", "self", "name", "index");
  68.       printf ("%6.6s %5.5s %7.7s %11.11s %7.7s/%-7.7s     %-8.8s\n",
  69.           "", "", "", "", "called", "total", "children");
  70.       printf ("\n");
  71.     }
  72.   else
  73.     {
  74.       printf ("index %% time    self  children    called     name\n");
  75.     }
  76. }
  77.  
  78.  
  79. /*
  80.  * Print a cycle header.
  81.  */
  82. static void
  83. DEFUN (print_cycle, (cyc), Sym * cyc)
  84. {
  85.   char buf[BUFSIZ];
  86.  
  87.   sprintf (buf, "[%d]", cyc->cg.index);
  88.   printf (bsd_style_output
  89.       ? "%-6.6s %5.1f %7.2f %11.2f %7d"
  90.       : "%-6.6s %5.1f %7.2f %7.2f %7d", buf,
  91.       100 * (cyc->cg.prop.self + cyc->cg.prop.child) / print_time,
  92.       cyc->cg.prop.self / hz, cyc->cg.prop.child / hz, cyc->ncalls);
  93.   if (cyc->cg.self_calls != 0)
  94.     {
  95.       printf ("+%-7d", cyc->cg.self_calls);
  96.     }
  97.   else
  98.     {
  99.       printf (" %7.7s", "");
  100.     }
  101.   printf (" <cycle %d as a whole> [%d]\n", cyc->cg.cyc.num, cyc->cg.index);
  102. }
  103.  
  104.  
  105. /*
  106.  * Compare LEFT and RIGHT membmer.  Major comparison key is
  107.  * CG.PROP.SELF+CG.PROP.CHILD, secondary key is NCALLS+CG.SELF_CALLS.
  108.  */
  109. static int
  110. DEFUN (cmp_member, (left, right), Sym * left AND Sym * right)
  111. {
  112.   double left_time = left->cg.prop.self + left->cg.prop.child;
  113.   double right_time = right->cg.prop.self + right->cg.prop.child;
  114.   long left_calls = left->ncalls + left->cg.self_calls;
  115.   long right_calls = right->ncalls + right->cg.self_calls;
  116.  
  117.   if (left_time > right_time)
  118.     {
  119.       return GREATERTHAN;
  120.     }
  121.   if (left_time < right_time)
  122.     {
  123.       return LESSTHAN;
  124.     }
  125.  
  126.   if (left_calls > right_calls)
  127.     {
  128.       return GREATERTHAN;
  129.     }
  130.   if (left_calls < right_calls)
  131.     {
  132.       return LESSTHAN;
  133.     }
  134.   return EQUALTO;
  135. }
  136.  
  137.  
  138. /*
  139.  * Sort members of a cycle.
  140.  */
  141. static void
  142. DEFUN (sort_members, (cyc), Sym * cyc)
  143. {
  144.   Sym *todo, *doing, *prev;
  145.   /*
  146.    * Detach cycle members from cyclehead, and insertion sort them
  147.    * back on.
  148.    */
  149.   todo = cyc->cg.cyc.next;
  150.   cyc->cg.cyc.next = 0;
  151.   for (doing = todo; doing && doing->cg.cyc.next; doing = todo)
  152.     {
  153.       todo = doing->cg.cyc.next;
  154.       for (prev = cyc; prev->cg.cyc.next; prev = prev->cg.cyc.next)
  155.     {
  156.       if (cmp_member (doing, prev->cg.cyc.next) == GREATERTHAN)
  157.         {
  158.           break;
  159.         }
  160.     }
  161.       doing->cg.cyc.next = prev->cg.cyc.next;
  162.       prev->cg.cyc.next = doing;
  163.     }
  164. }
  165.  
  166.  
  167. /*
  168.  * Print the members of a cycle.
  169.  */
  170. static void
  171. DEFUN (print_members, (cyc), Sym * cyc)
  172. {
  173.   Sym *member;
  174.  
  175.   sort_members (cyc);
  176.   for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
  177.     {
  178.       printf (bsd_style_output
  179.           ? "%6.6s %5.5s %7.2f %11.2f %7d"
  180.           : "%6.6s %5.5s %7.2f %7.2f %7d",
  181.           "", "", member->cg.prop.self / hz, member->cg.prop.child / hz,
  182.           member->ncalls);
  183.       if (member->cg.self_calls != 0)
  184.     {
  185.       printf ("+%-7d", member->cg.self_calls);
  186.     }
  187.       else
  188.     {
  189.       printf (" %7.7s", "");
  190.     }
  191.       printf ("     ");
  192.       print_name (member);
  193.       printf ("\n");
  194.     }
  195. }
  196.  
  197.  
  198. /*
  199.  * Compare two arcs to/from the same child/parent.
  200.  *      - if one arc is a self arc, it's least.
  201.  *      - if one arc is within a cycle, it's less than.
  202.  *      - if both arcs are within a cycle, compare arc counts.
  203.  *      - if neither arc is within a cycle, compare with
  204.  *              time + child_time as major key
  205.  *              arc count as minor key
  206.  */
  207. static int
  208. DEFUN (cmp_arc, (left, right), Arc * left AND Arc * right)
  209. {
  210.   Sym *left_parent = left->parent;
  211.   Sym *left_child = left->child;
  212.   Sym *right_parent = right->parent;
  213.   Sym *right_child = right->child;
  214.   double left_time, right_time;
  215.  
  216.   DBG (TIMEDEBUG,
  217.        printf ("[cmp_arc] ");
  218.        print_name (left_parent);
  219.        printf (" calls ");
  220.        print_name (left_child);
  221.        printf (" %f + %f %d/%d\n", left->time, left->child_time,
  222.            left->count, left_child->ncalls);
  223.        printf ("[cmp_arc] ");
  224.        print_name (right_parent);
  225.        printf (" calls ");
  226.        print_name (right_child);
  227.        printf (" %f + %f %d/%d\n", right->time, right->child_time,
  228.            right->count, right_child->ncalls);
  229.        printf ("\n");
  230.     );
  231.   if (left_parent == left_child)
  232.     {
  233.       return LESSTHAN;        /* left is a self call */
  234.     }
  235.   if (right_parent == right_child)
  236.     {
  237.       return GREATERTHAN;    /* right is a self call */
  238.     }
  239.  
  240.   if (left_parent->cg.cyc.num != 0 && left_child->cg.cyc.num != 0
  241.       && left_parent->cg.cyc.num == left_child->cg.cyc.num)
  242.     {
  243.       /* left is a call within a cycle */
  244.       if (right_parent->cg.cyc.num != 0 && right_child->cg.cyc.num != 0
  245.       && right_parent->cg.cyc.num == right_child->cg.cyc.num)
  246.     {
  247.       /* right is a call within the cycle, too */
  248.       if (left->count < right->count)
  249.         {
  250.           return LESSTHAN;
  251.         }
  252.       if (left->count > right->count)
  253.         {
  254.           return GREATERTHAN;
  255.         }
  256.       return EQUALTO;
  257.     }
  258.       else
  259.     {
  260.       /* right isn't a call within the cycle */
  261.       return LESSTHAN;
  262.     }
  263.     }
  264.   else
  265.     {
  266.       /* left isn't a call within a cycle */
  267.       if (right_parent->cg.cyc.num != 0 && right_child->cg.cyc.num != 0
  268.       && right_parent->cg.cyc.num == right_child->cg.cyc.num)
  269.     {
  270.       /* right is a call within a cycle */
  271.       return GREATERTHAN;
  272.     }
  273.       else
  274.     {
  275.       /* neither is a call within a cycle */
  276.       left_time = left->time + left->child_time;
  277.       right_time = right->time + right->child_time;
  278.       if (left_time < right_time)
  279.         {
  280.           return LESSTHAN;
  281.         }
  282.       if (left_time > right_time)
  283.         {
  284.           return GREATERTHAN;
  285.         }
  286.       if (left->count < right->count)
  287.         {
  288.           return LESSTHAN;
  289.         }
  290.       if (left->count > right->count)
  291.         {
  292.           return GREATERTHAN;
  293.         }
  294.       return EQUALTO;
  295.     }
  296.     }
  297. }
  298.  
  299.  
  300. static void
  301. DEFUN (sort_parents, (child), Sym * child)
  302. {
  303.   Arc *arc, *detached, sorted, *prev;
  304.  
  305.   /*
  306.    * Unlink parents from child, then insertion sort back on to
  307.    * sorted's parents.
  308.    *      *arc        the arc you have detached and are inserting.
  309.    *      *detached   the rest of the arcs to be sorted.
  310.    *      sorted      arc list onto which you insertion sort.
  311.    *      *prev       arc before the arc you are comparing.
  312.    */
  313.   sorted.next_parent = 0;
  314.   for (arc = child->cg.parents; arc; arc = detached)
  315.     {
  316.       detached = arc->next_parent;
  317.  
  318.       /* consider *arc as disconnected; insert it into sorted: */
  319.       for (prev = &sorted; prev->next_parent; prev = prev->next_parent)
  320.     {
  321.       if (cmp_arc (arc, prev->next_parent) != GREATERTHAN)
  322.         {
  323.           break;
  324.         }
  325.     }
  326.       arc->next_parent = prev->next_parent;
  327.       prev->next_parent = arc;
  328.     }
  329.  
  330.   /* reattach sorted arcs to child: */
  331.   child->cg.parents = sorted.next_parent;
  332. }
  333.  
  334.  
  335. static void
  336. DEFUN (print_parents, (child), Sym * child)
  337. {
  338.   Sym *parent;
  339.   Arc *arc;
  340.   Sym *cycle_head;
  341.  
  342.   if (child->cg.cyc.head != 0)
  343.     {
  344.       cycle_head = child->cg.cyc.head;
  345.     }
  346.   else
  347.     {
  348.       cycle_head = child;
  349.     }
  350.   if (!child->cg.parents)
  351.     {
  352.       printf (bsd_style_output
  353.           ? "%6.6s %5.5s %7.7s %11.11s %7.7s %7.7s     <spontaneous>\n"
  354.           : "%6.6s %5.5s %7.7s %7.7s %7.7s %7.7s     <spontaneous>\n",
  355.           "", "", "", "", "", "");
  356.       return;
  357.     }
  358.   sort_parents (child);
  359.   for (arc = child->cg.parents; arc; arc = arc->next_parent)
  360.     {
  361.       parent = arc->parent;
  362.       if (child == parent || (child->cg.cyc.num != 0
  363.                   && parent->cg.cyc.num == child->cg.cyc.num))
  364.     {
  365.       /* selfcall or call among siblings: */
  366.       printf (bsd_style_output
  367.           ? "%6.6s %5.5s %7.7s %11.11s %7d %7.7s     "
  368.           : "%6.6s %5.5s %7.7s %7.7s %7d %7.7s     ",
  369.           "", "", "", "",
  370.           arc->count, "");
  371.       print_name (parent);
  372.       printf ("\n");
  373.     }
  374.       else
  375.     {
  376.       /* regular parent of child: */
  377.       printf (bsd_style_output
  378.           ? "%6.6s %5.5s %7.2f %11.2f %7d/%-7d     "
  379.           : "%6.6s %5.5s %7.2f %7.2f %7d/%-7d     ",
  380.           "", "",
  381.           arc->time / hz, arc->child_time / hz,
  382.           arc->count, cycle_head->ncalls);
  383.       print_name (parent);
  384.       printf ("\n");
  385.     }
  386.     }
  387. }
  388.  
  389.  
  390. static void
  391. DEFUN (sort_children, (parent), Sym * parent)
  392. {
  393.   Arc *arc, *detached, sorted, *prev;
  394.   /*
  395.    * Unlink children from parent, then insertion sort back on to
  396.    * sorted's children.
  397.    *      *arc        the arc you have detached and are inserting.
  398.    *      *detached   the rest of the arcs to be sorted.
  399.    *      sorted      arc list onto which you insertion sort.
  400.    *      *prev       arc before the arc you are comparing.
  401.    */
  402.   sorted.next_child = 0;
  403.   for (arc = parent->cg.children; arc; arc = detached)
  404.     {
  405.       detached = arc->next_child;
  406.  
  407.       /* consider *arc as disconnected; insert it into sorted: */
  408.       for (prev = &sorted; prev->next_child; prev = prev->next_child)
  409.     {
  410.       if (cmp_arc (arc, prev->next_child) != LESSTHAN)
  411.         {
  412.           break;
  413.         }
  414.     }
  415.       arc->next_child = prev->next_child;
  416.       prev->next_child = arc;
  417.     }
  418.  
  419.   /* reattach sorted children to parent: */
  420.   parent->cg.children = sorted.next_child;
  421. }
  422.  
  423.  
  424. static void
  425. DEFUN (print_children, (parent), Sym * parent)
  426. {
  427.   Sym *child;
  428.   Arc *arc;
  429.  
  430.   sort_children (parent);
  431.   arc = parent->cg.children;
  432.   for (arc = parent->cg.children; arc; arc = arc->next_child)
  433.     {
  434.       child = arc->child;
  435.       if (child == parent || (child->cg.cyc.num != 0
  436.                   && child->cg.cyc.num == parent->cg.cyc.num))
  437.     {
  438.       /* self call or call to sibling: */
  439.       printf (bsd_style_output
  440.           ? "%6.6s %5.5s %7.7s %11.11s %7d %7.7s     "
  441.           : "%6.6s %5.5s %7.7s %7.7s %7d %7.7s     ",
  442.           "", "", "", "", arc->count, "");
  443.       print_name (child);
  444.       printf ("\n");
  445.     }
  446.       else
  447.     {
  448.       /* regular child of parent: */
  449.       printf (bsd_style_output
  450.           ? "%6.6s %5.5s %7.2f %11.2f %7d/%-7d     "
  451.           : "%6.6s %5.5s %7.2f %7.2f %7d/%-7d     ",
  452.           "", "",
  453.           arc->time / hz, arc->child_time / hz,
  454.           arc->count, child->cg.cyc.head->ncalls);
  455.       print_name (child);
  456.       printf ("\n");
  457.     }
  458.     }
  459. }
  460.  
  461.  
  462. static void
  463. DEFUN (print_line, (np), Sym * np)
  464. {
  465.   char buf[BUFSIZ];
  466.  
  467.   sprintf (buf, "[%d]", np->cg.index);
  468.   printf (bsd_style_output
  469.       ? "%-6.6s %5.1f %7.2f %11.2f"
  470.       : "%-6.6s %5.1f %7.2f %7.2f", buf,
  471.       100 * (np->cg.prop.self + np->cg.prop.child) / print_time,
  472.       np->cg.prop.self / hz, np->cg.prop.child / hz);
  473.   if ((np->ncalls + np->cg.self_calls) != 0)
  474.     {
  475.       printf (" %7d", np->ncalls);
  476.       if (np->cg.self_calls != 0)
  477.     {
  478.       printf ("+%-7d ", np->cg.self_calls);
  479.     }
  480.       else
  481.     {
  482.       printf (" %7.7s ", "");
  483.     }
  484.     }
  485.   else
  486.     {
  487.       printf (" %7.7s %7.7s ", "", "");
  488.     }
  489.   print_name (np);
  490.   printf ("\n");
  491. }
  492.  
  493.  
  494. /*
  495.  * Print dynamic call graph.
  496.  */
  497. void
  498. DEFUN (cg_print, (timesortsym), Sym ** timesortsym)
  499. {
  500.   int index;
  501.   Sym *parent;
  502.  
  503.   if (print_descriptions && bsd_style_output)
  504.     {
  505.       bsd_callg_blurb (stdout);
  506.     }
  507.  
  508.   print_header ();
  509.  
  510.   for (index = 0; index < symtab.len + num_cycles; ++index)
  511.     {
  512.       parent = timesortsym[index];
  513.       if ((ignore_zeros && parent->ncalls == 0
  514.        && parent->cg.self_calls == 0 && parent->cg.prop.self == 0
  515.        && parent->cg.prop.child == 0)
  516.       || !parent->cg.print_flag)
  517.     {
  518.       continue;
  519.     }
  520.       if (!parent->name && parent->cg.cyc.num != 0)
  521.     {
  522.       /* cycle header: */
  523.       print_cycle (parent);
  524.       print_members (parent);
  525.     }
  526.       else
  527.     {
  528.       print_parents (parent);
  529.       print_line (parent);
  530.       print_children (parent);
  531.     }
  532.       if (bsd_style_output)
  533.     printf ("\n");
  534.       printf ("-----------------------------------------------\n");
  535.       if (bsd_style_output)
  536.     printf ("\n");
  537.     }
  538.   free (timesortsym);
  539.   if (print_descriptions && !bsd_style_output)
  540.     {
  541.       fsf_callg_blurb (stdout);
  542.     }
  543. }
  544.  
  545.  
  546. static int
  547. DEFUN (cmp_name, (left, right), const PTR left AND const PTR right)
  548. {
  549.   const Sym **npp1 = (const Sym **) left;
  550.   const Sym **npp2 = (const Sym **) right;
  551.  
  552.   return strcmp ((*npp1)->name, (*npp2)->name);
  553. }
  554.  
  555.  
  556. void
  557. DEFUN_VOID (cg_print_index)
  558. {
  559.   int index, nnames, todo, i, j, col, starting_col;
  560.   Sym **name_sorted_syms, *sym;
  561.   const char *filename;
  562.   char buf[20];
  563.   int column_width = (output_width - 1) / 3;    /* don't write in last col! */
  564.   /*
  565.    * Now, sort regular function name alphabetically to create an
  566.    * index:
  567.    */
  568.   name_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
  569.   for (index = 0, nnames = 0; index < symtab.len; index++)
  570.     {
  571.       if (ignore_zeros && symtab.base[index].ncalls == 0
  572.       && symtab.base[index].hist.time == 0)
  573.     {
  574.       continue;
  575.     }
  576.       name_sorted_syms[nnames++] = &symtab.base[index];
  577.     }
  578.   qsort (name_sorted_syms, nnames, sizeof (Sym *), cmp_name);
  579.   for (index = 1, todo = nnames; index <= num_cycles; index++)
  580.     {
  581.       name_sorted_syms[todo++] = &cycle_header[index];
  582.     }
  583.   printf ("\f\nIndex by function name\n\n");
  584.   index = (todo + 2) / 3;
  585.   for (i = 0; i < index; i++)
  586.     {
  587.       col = 0;
  588.       starting_col = 0;
  589.       for (j = i; j < todo; j += index)
  590.     {
  591.       sym = name_sorted_syms[j];
  592.       if (sym->cg.print_flag)
  593.         {
  594.           sprintf (buf, "[%d]", sym->cg.index);
  595.         }
  596.       else
  597.         {
  598.           sprintf (buf, "(%d)", sym->cg.index);
  599.         }
  600.       if (j < nnames)
  601.         {
  602.           if (bsd_style_output)
  603.         {
  604.           printf ("%6.6s %-19.19s", buf, sym->name);
  605.         }
  606.           else
  607.         {
  608.           col += strlen (buf);
  609.           for (; col < starting_col + 5; ++col)
  610.             {
  611.               putchar (' ');
  612.             }
  613.           printf (" %s ", buf);
  614.           col += print_name_only (sym);
  615.           if (!line_granularity && sym->is_static && sym->file)
  616.             {
  617.               filename = sym->file->name;
  618.               if (!print_path)
  619.             {
  620.               filename = strrchr (filename, '/');
  621.               if (filename)
  622.                 {
  623.                   ++filename;
  624.                 }
  625.               else
  626.                 {
  627.                   filename = sym->file->name;
  628.                 }
  629.             }
  630.               printf (" (%s)", filename);
  631.               col += strlen (filename) + 3;
  632.             }
  633.         }
  634.         }
  635.       else
  636.         {
  637.           if (bsd_style_output)
  638.         {
  639.           printf ("%6.6s ", buf);
  640.           sprintf (buf, "<cycle %d>", sym->cg.cyc.num);
  641.           printf ("%-19.19s", buf);
  642.         }
  643.           else
  644.         {
  645.           col += strlen (buf);
  646.           for (; col < starting_col + 5; ++col)
  647.             putchar (' ');
  648.           printf (" %s ", buf);
  649.           sprintf (buf, "<cycle %d>", sym->cg.cyc.num);
  650.           printf ("%s", buf);
  651.           col += strlen (buf);
  652.         }
  653.         }
  654.       starting_col += column_width;
  655.     }
  656.       printf ("\n");
  657.     }
  658.   free (name_sorted_syms);
  659. }
  660.  
  661. /* Compare two arcs based on their usage counts.  We want to sort
  662.    in descending order.  */
  663. static int
  664. DEFUN (cmp_arc_count, (left, right), const PTR left AND const PTR right)
  665. {
  666.   const Arc **npp1 = (const Arc **) left;
  667.   const Arc **npp2 = (const Arc **) right;
  668.  
  669.   if ((*npp1)->count > (*npp2)->count)
  670.     return -1;
  671.   else if ((*npp1)->count < (*npp2)->count)
  672.     return 1;
  673.   else
  674.     return 0;
  675. }
  676.  
  677. /* Compare two funtions based on their usage counts.  We want to sort
  678.    in descending order.  */
  679. static int
  680. DEFUN (cmp_fun_nuses, (left, right), const PTR left AND const PTR right)
  681. {
  682.   const Sym **npp1 = (const Sym **) left;
  683.   const Sym **npp2 = (const Sym **) right;
  684.  
  685.   if ((*npp1)->nuses > (*npp2)->nuses)
  686.     return -1;
  687.   else if ((*npp1)->nuses < (*npp2)->nuses)
  688.     return 1;
  689.   else
  690.     return 0;
  691. }
  692.  
  693. /* Print a suggested function ordering based on the profiling data.
  694.  
  695.    We perform 4 major steps when ordering functions:
  696.  
  697.     * Group unused functions together and place them at the
  698.     end of the function order.
  699.  
  700.     * Search the highest use arcs (those which account for 90% of
  701.     the total arc count) for functions which have several parents.
  702.  
  703.     Group those with the most call sites together (currently the
  704.     top 1.25% which have at least five different call sites).
  705.  
  706.     These are emitted at the start of the function order.
  707.  
  708.     * Use a greedy placement algorithm to place functions which
  709.     occur in the top 99% of the arcs in the profile.  Some provisions
  710.     are made to handle high usage arcs where the parent and/or
  711.     child has already been placed.
  712.  
  713.     * Run the same greedy placement algorithm on the remaining
  714.     arcs to place the leftover functions.
  715.  
  716.  
  717.    The various "magic numbers" should (one day) be tuneable by command
  718.    line options.  They were arrived at by benchmarking a few applications
  719.    with various values to see which values produced better overall function
  720.    orderings.
  721.  
  722.    Of course, profiling errors, machine limitations (PA long calls), and
  723.    poor cutoff values for the placement algorithm may limit the usefullness
  724.    of the resulting function order.  Improvements would be greatly appreciated.
  725.    
  726.    Suggestions:
  727.  
  728.     * Place the functions with many callers near the middle of the
  729.     list to reduce long calls.
  730.  
  731.     * Propagate arc usage changes as functions are placed.  Ie if
  732.     func1 and func2 are placed together, arcs to/from those arcs
  733.     to the same parent/child should be combined, then resort the
  734.     arcs to choose the next one.
  735.  
  736.     * Implement some global positioning algorithm to place the
  737.     chains made by the greedy local positioning algorithm.  Probably
  738.     by examining arcs which haven't been placed yet to tie two
  739.     chains together.
  740.  
  741.     * Take a function's size and time into account in the algorithm;
  742.     size in particular is important on the PA (long calls).  Placing
  743.     many small functions onto their own page may be wise.
  744.  
  745.     * Use better profiling information; many published algorithms
  746.     are based on call sequences through time, rather than just
  747.     arc counts.
  748.  
  749.     * Prodecure cloning could improve performance when a small number
  750.     of arcs account for most of the calls to a particular function.
  751.  
  752.     * Use relocation information to avoid moving unused functions
  753.     completely out of the code stream; this would avoid severe lossage
  754.     when the profile data bears little resemblance to actual runs.
  755.  
  756.     * Propagation of arc usages should also improve .o link line
  757.     ordering which shares the same arc placement algorithm with
  758.     the function ordering code (in fact it is a degenerate case
  759.     of function ordering).  */
  760.     
  761. void
  762. DEFUN_VOID (cg_print_function_ordering)
  763. {
  764.   unsigned long index, used, unused, scratch_index;
  765.   unsigned long  unplaced_arc_count, high_arc_count, scratch_arc_count;
  766. #ifdef __GNUC__
  767.   unsigned long long total_arcs, tmp_arcs_count;
  768. #else
  769.   unsigned long total_arcs, tmp_arcs_count;
  770. #endif
  771.   Sym **unused_syms, **used_syms, **scratch_syms;
  772.   Arc **unplaced_arcs, **high_arcs, **scratch_arcs;
  773.  
  774.   index = 0;
  775.   used = 0;
  776.   unused = 0;
  777.   scratch_index = 0;
  778.   unplaced_arc_count = 0;
  779.   high_arc_count = 0;
  780.   scratch_arc_count = 0;
  781.  
  782.   /* First group all the unused functions together.  */
  783.   unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
  784.   used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
  785.   scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
  786.   high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
  787.   scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
  788.   unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
  789.  
  790.   /* Walk through all the functions; mark those which are never
  791.      called as placed (we'll emit them as a group later).  */
  792.   for (index = 0, used = 0, unused = 0; index < symtab.len; index++)
  793.     {
  794.       if (symtab.base[index].ncalls == 0)
  795.     {
  796.       /* Filter out gprof generated names.  */
  797.       if (strcmp (symtab.base[index].name, "<locore>")
  798.           && strcmp (symtab.base[index].name, "<hicore>"))
  799.         {
  800.           unused_syms[unused++] = &symtab.base[index];
  801.           symtab.base[index].has_been_placed = 1;
  802.         }
  803.     }
  804.       else
  805.     {
  806.       used_syms[used++] = &symtab.base[index];
  807.       symtab.base[index].has_been_placed = 0;
  808.       symtab.base[index].next = 0;
  809.       symtab.base[index].prev = 0;
  810.       symtab.base[index].nuses = 0;
  811.     }
  812.     }
  813.  
  814.   /* Sort the arcs from most used to least used.  */
  815.   qsort (arcs, numarcs, sizeof (Arc *), cmp_arc_count);
  816.  
  817.   /* Compute the total arc count.  Also mark arcs as unplaced.
  818.  
  819.      Note we don't compensate for overflow if that happens!
  820.      Overflow is much less likely when this file is compiled
  821.      with GCC as it can double-wide integers via long long.  */
  822.   total_arcs = 0;
  823.   for (index = 0; index < numarcs; index++)
  824.     {
  825.       total_arcs += arcs[index]->count;
  826.       arcs[index]->has_been_placed = 0;
  827.     }
  828.  
  829.   /* We want to pull out those functions which are referenced
  830.      by many highly used arcs and emit them as a group.  This
  831.      could probably use some tuning.  */
  832.   tmp_arcs_count = 0;
  833.   for (index = 0; index < numarcs; index++)
  834.     {
  835.       tmp_arcs_count += arcs[index]->count;
  836.  
  837.       /* Count how many times each parent and child are used up
  838.      to our threshhold of arcs (90%).  */
  839.       if ((double)tmp_arcs_count / (double)total_arcs > 0.90)
  840.     break;
  841.  
  842.       arcs[index]->child->nuses++;
  843.     }
  844.  
  845.   /* Now sort a temporary symbol table based on the number of
  846.      times each function was used in the highest used arcs.  */
  847.   memcpy (scratch_syms, used_syms, used * sizeof (Sym *));
  848.   qsort (scratch_syms, used, sizeof (Sym *), cmp_fun_nuses);
  849.  
  850.   /* Now pick out those symbols we're going to emit as
  851.      a group.  We take up to 1.25% of the used symbols.  */
  852.   for (index = 0; index < used / 80; index++)
  853.     {
  854.       Sym *sym = scratch_syms[index];
  855.       Arc *arc;
  856.  
  857.       /* If we hit symbols that aren't used from many call sites,
  858.      then we can quit.  We choose five as the low limit for
  859.      no particular reason.  */
  860.       if (sym->nuses == 5)
  861.     break;
  862.  
  863.       /* We're going to need the arcs between these functions.
  864.      Unfortunately, we don't know all these functions
  865.      until we're done.  So we keep track of all the arcs
  866.      to the functions we care about, then prune out those
  867.      which are uninteresting. 
  868.  
  869.      An interesting variation would be to quit when we found
  870.      multi-call site functions which account for some percentage
  871.      of the arcs.  */
  872.  
  873.       arc = sym->cg.children;
  874.       while (arc)
  875.     {
  876.       if (arc->parent != arc->child)
  877.         scratch_arcs[scratch_arc_count++] = arc;
  878.       arc->has_been_placed = 1;
  879.       arc = arc->next_child;
  880.     }
  881.  
  882.       arc = sym->cg.parents;
  883.       while (arc)
  884.     {
  885.       if (arc->parent != arc->child)
  886.         scratch_arcs[scratch_arc_count++] = arc;
  887.       arc->has_been_placed = 1;
  888.       arc = arc->next_parent;
  889.     }
  890.  
  891.       /* Keep track of how many symbols we're going to place.  */
  892.       scratch_index = index;
  893.  
  894.       /* A lie, but it makes identifying these functions easier
  895.      later.  */
  896.       sym->has_been_placed = 1;
  897.     }
  898.  
  899.   /* Now walk through the temporary arcs and copy those we care about
  900.      into the high arcs array.  */
  901.   for (index = 0; index < scratch_arc_count; index++)
  902.     {
  903.       Arc *arc = scratch_arcs[index];
  904.  
  905.       /* If this arc refers to highly used functions, then
  906.      then we want to keep it.  */
  907.       if (arc->child->has_been_placed
  908.       && arc->parent->has_been_placed)
  909.     {
  910.       high_arcs[high_arc_count++] = scratch_arcs[index];
  911.  
  912.       /* We need to turn of has_been_placed since we're going to
  913.          use the main arc placement algorithm on these arcs.  */
  914.       arc->child->has_been_placed = 0;
  915.       arc->parent->has_been_placed = 0;
  916.     }
  917.     }
  918.  
  919.   /* Dump the multi-site high usage functions which are not going
  920.      to be ordered by the main ordering algorithm.  */
  921.   for (index = 0; index < scratch_index; index++)
  922.     {
  923.       if (scratch_syms[index]->has_been_placed)
  924.     printf ("%s\n", scratch_syms[index]->name);
  925.     }
  926.  
  927.   /* Now we can order the multi-site high use functions based on the
  928.      arcs between them.  */
  929.   qsort (high_arcs, high_arc_count, sizeof (Arc *), cmp_arc_count);
  930.   order_and_dump_functions_by_arcs (high_arcs, high_arc_count, 1,
  931.                     unplaced_arcs, &unplaced_arc_count);
  932.  
  933.   /* Order and dump the high use functions left, these typically
  934.      have only a few call sites.  */
  935.   order_and_dump_functions_by_arcs (arcs, numarcs, 0,
  936.                     unplaced_arcs, &unplaced_arc_count);
  937.  
  938.   /* Now place the rarely used functions.  */
  939.   order_and_dump_functions_by_arcs (unplaced_arcs, unplaced_arc_count, 1,
  940.                     scratch_arcs, &scratch_arc_count);
  941.  
  942.   /* Output any functions not emitted by the order_and_dump calls.  */
  943.   for (index = 0; index < used; index++)
  944.     if (used_syms[index]->has_been_placed == 0)
  945.       printf("%s\n", used_syms[index]->name);
  946.  
  947.   /* Output the unused functions.  */
  948.   for (index = 0; index < unused; index++)
  949.     printf("%s\n", unused_syms[index]->name);
  950.  
  951.   unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
  952.   used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
  953.   scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
  954.   high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
  955.   scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
  956.   unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
  957.  
  958.   free (unused_syms);
  959.   free (used_syms);
  960.   free (scratch_syms);
  961.   free (high_arcs);
  962.   free (scratch_arcs);
  963.   free (unplaced_arcs);
  964. }
  965.  
  966. /* Place functions based on the arcs in ARCS with NUMARCS entries;
  967.    place unused arcs into UNPLACED_ARCS/UNPLACED_ARC_COUNT.
  968.  
  969.    If ALL is nonzero, then place all functions referenced by ARCS,
  970.    else only place those referenced in the top 99% of the arcs in ARCS.  */
  971.  
  972. #define MOST 0.99
  973. static void
  974. order_and_dump_functions_by_arcs (arcs, numarcs, all,
  975.                   unplaced_arcs, unplaced_arc_count)
  976.      Arc **arcs;
  977.      unsigned long numarcs;
  978.      int all;
  979.      Arc **unplaced_arcs;
  980.      unsigned long *unplaced_arc_count;
  981. {
  982. #ifdef __GNUC__
  983.   unsigned long long tmp_arcs, total_arcs;
  984. #else
  985.   unsigned long tmp_arcs, total_arcs;
  986. #endif
  987.   unsigned int index;
  988.  
  989.   /* If needed, compute the total arc count.
  990.  
  991.      Note we don't compensate for overflow if that happens!  */
  992.   if (! all)
  993.     {
  994.       total_arcs = 0;
  995.       for (index = 0; index < numarcs; index++)
  996.     total_arcs += arcs[index]->count;
  997.     }
  998.   else
  999.     total_arcs = 0;
  1000.  
  1001.   tmp_arcs = 0;
  1002.   for (index = 0; index < numarcs; index++)
  1003.     {
  1004.       Sym *sym1, *sym2;
  1005.       Sym *child, *parent;
  1006.  
  1007.       tmp_arcs += arcs[index]->count;
  1008.  
  1009.       /* Ignore this arc if it's already been placed.  */
  1010.       if (arcs[index]->has_been_placed)
  1011.     continue;
  1012.  
  1013.       child = arcs[index]->child;
  1014.       parent = arcs[index]->parent;
  1015.  
  1016.       /* If we're not using all arcs, and this is a rarely used
  1017.      arc, then put it on the unplaced_arc list.  Similarly
  1018.      if both the parent and child of this arc have been placed.  */
  1019.       if ((! all && (double)tmp_arcs / (double)total_arcs > MOST)
  1020.       || child->has_been_placed || parent->has_been_placed)
  1021.     {
  1022.       unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
  1023.       continue;
  1024.     }
  1025.  
  1026.       /* If all slots in the parent and child are full, then there isn't
  1027.      anything we can do right now.  We'll place this arc on the
  1028.      unplaced arc list in the hope that a global positioning
  1029.      algorithm can use it to place function chains.  */
  1030.       if (parent->next && parent->prev && child->next && child->prev)
  1031.     {
  1032.       unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
  1033.       continue;
  1034.     }
  1035.  
  1036.       /* If the parent is unattached, then find the closest
  1037.      place to attach it onto child's chain.   Similarly
  1038.      for the opposite case.  */
  1039.       if (!parent->next && !parent->prev)
  1040.     {
  1041.       int next_count = 0;
  1042.       int prev_count = 0;
  1043.       Sym *prev = child;
  1044.       Sym *next = child;
  1045.  
  1046.       /* Walk to the beginning and end of the child's chain.  */
  1047.       while (next->next)
  1048.         {
  1049.           next = next->next;
  1050.           next_count++;
  1051.         }
  1052.  
  1053.       while (prev->prev)
  1054.         {
  1055.           prev = prev->prev;
  1056.           prev_count++;
  1057.         }
  1058.       
  1059.       /* Choose the closest.  */
  1060.       child = next_count < prev_count ? next : prev;
  1061.       }
  1062.       else if (! child->next && !child->prev)
  1063.     {
  1064.       int next_count = 0;
  1065.       int prev_count = 0;
  1066.       Sym *prev = parent;
  1067.       Sym *next = parent;
  1068.  
  1069.       while (next->next)
  1070.         {
  1071.           next = next->next;
  1072.           next_count++;
  1073.         }
  1074.  
  1075.       while (prev->prev)
  1076.         {
  1077.           prev = prev->prev;
  1078.           prev_count++;
  1079.         }
  1080.  
  1081.       parent = prev_count < next_count ? prev : next;
  1082.     }
  1083.       else
  1084.     {
  1085.       /* Couldn't find anywhere to attach the functions,
  1086.          put the arc on the unplaced arc list.  */
  1087.       unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
  1088.       continue;
  1089.     }
  1090.  
  1091.       /* Make sure we don't tie two ends together.  */
  1092.       sym1 = parent;
  1093.       if (sym1->next)
  1094.     while (sym1->next)
  1095.       sym1 = sym1->next;
  1096.       else
  1097.     while (sym1->prev)
  1098.       sym1 = sym1->prev;
  1099.  
  1100.       sym2 = child;
  1101.       if (sym2->next)
  1102.     while (sym2->next)
  1103.       sym2 = sym2->next;
  1104.       else
  1105.     while (sym2->prev)
  1106.       sym2 = sym2->prev;
  1107.  
  1108.       if (sym1 == child
  1109.       && sym2 == parent)
  1110.     {
  1111.       /* This would tie two ends together.  */
  1112.       unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
  1113.       continue;
  1114.     }
  1115.  
  1116.       if (parent->next)
  1117.     {
  1118.       /* Must attach to the parent's prev field.  */
  1119.       if (! child->next)
  1120.         {
  1121.           /* parent-prev and child-next */
  1122.           parent->prev = child;
  1123.           child->next = parent;
  1124.           arcs[index]->has_been_placed = 1;
  1125.         }
  1126.     }
  1127.       else if (parent->prev)
  1128.     {
  1129.       /* Must attach to the parent's next field.  */
  1130.       if (! child->prev)
  1131.         {
  1132.           /* parent-next and child-prev */
  1133.           parent->next = child;
  1134.           child->prev = parent;
  1135.           arcs[index]->has_been_placed = 1;
  1136.         }
  1137.     }
  1138.       else
  1139.     {
  1140.       /* Can attach to either field in the parent, depends
  1141.          on where we've got space in the child.  */
  1142.       if (child->prev)
  1143.         {
  1144.           /* parent-prev and child-next */
  1145.           parent->prev = child;
  1146.           child->next = parent;
  1147.           arcs[index]->has_been_placed = 1;
  1148.         }
  1149.       else
  1150.         {
  1151.           /* parent-next and child-prev */
  1152.           parent->next = child;
  1153.           child->prev = parent;
  1154.           arcs[index]->has_been_placed = 1;
  1155.         }
  1156.     }
  1157.     }
  1158.  
  1159.   /* Dump the chains of functions we've made.  */
  1160.   for (index = 0; index < numarcs; index++)
  1161.     {
  1162.       Sym *sym;
  1163.       if (arcs[index]->parent->has_been_placed
  1164.       || arcs[index]->child->has_been_placed)
  1165.     continue;
  1166.  
  1167.       sym = arcs[index]->parent;
  1168.  
  1169.       /* If this symbol isn't attached to any other
  1170.      symbols, then we've got a rarely used arc.
  1171.  
  1172.      Skip it for now, we'll deal with them later.  */
  1173.       if (sym->next == NULL
  1174.       && sym->prev == NULL)
  1175.     continue;
  1176.  
  1177.       /* Get to the start of this chain.  */
  1178.       while (sym->prev)
  1179.     sym = sym->prev;
  1180.  
  1181.       while (sym)
  1182.     {
  1183.       /* Mark it as placed.  */
  1184.       sym->has_been_placed = 1;
  1185.       printf ("%s\n", sym->name);
  1186.       sym = sym->next;
  1187.     }
  1188.     }
  1189.  
  1190.   /* If we want to place all the arcs, then output those which weren't
  1191.      placed by the main algorithm.  */
  1192.   if (all)
  1193.     for (index = 0; index < numarcs; index++)
  1194.       {
  1195.     Sym *sym;
  1196.     if (arcs[index]->parent->has_been_placed
  1197.         || arcs[index]->child->has_been_placed)
  1198.       continue;
  1199.  
  1200.     sym = arcs[index]->parent;
  1201.  
  1202.     sym->has_been_placed = 1;
  1203.     printf ("%s\n", sym->name);
  1204.       }
  1205. }
  1206.  
  1207. /* Print a suggested .o ordering for files on a link line based
  1208.    on profiling information.  This uses the function placement
  1209.    code for the bulk of its work.  */
  1210.  
  1211. struct function_map {
  1212.   char *function_name;
  1213.   char *file_name;
  1214. };
  1215.  
  1216. void
  1217. DEFUN_VOID (cg_print_file_ordering)
  1218. {
  1219.   unsigned long scratch_arc_count, index;
  1220.   Arc **scratch_arcs;
  1221.   extern struct function_map *symbol_map;
  1222.   extern int symbol_map_count;
  1223.   char *last;
  1224.  
  1225.   scratch_arc_count = 0;
  1226.  
  1227.   scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
  1228.   for (index = 0; index < numarcs; index++)
  1229.     {
  1230.       if (! arcs[index]->parent->mapped
  1231.       || ! arcs[index]->child->mapped)
  1232.     arcs[index]->has_been_placed = 1;
  1233.     }
  1234.  
  1235.   order_and_dump_functions_by_arcs (arcs, numarcs, 0,
  1236.                     scratch_arcs, &scratch_arc_count);
  1237.  
  1238.   /* Output .o's not handled by the main placement algorithm.  */
  1239.   for (index = 0; index < symtab.len; index++)
  1240.     {
  1241.       if (symtab.base[index].mapped
  1242.       && ! symtab.base[index].has_been_placed)
  1243.     printf ("%s\n", symtab.base[index].name);
  1244.     }
  1245.  
  1246.   /* Now output any .o's that didn't have any text symbols.  */
  1247.   last = NULL;
  1248.   for (index = 0; index < symbol_map_count; index++)
  1249.     {
  1250.       int index2;
  1251.  
  1252.       /* Don't bother searching if this symbol is the
  1253.      same as the previous one.  */
  1254.       if (last && !strcmp (last, symbol_map[index].file_name))
  1255.     continue;
  1256.  
  1257.       for (index2 = 0; index2 < symtab.len; index2++)
  1258.     {
  1259.       if (! symtab.base[index2].mapped)
  1260.         continue;
  1261.  
  1262.       if (!strcmp (symtab.base[index2].name, symbol_map[index].file_name))
  1263.         break;
  1264.     }
  1265.  
  1266.       /* If we didn't find it in the symbol table, then it must be a .o
  1267.      with no text symbols.  Output it last.  */
  1268.       if (index2 == symtab.len)
  1269.     printf ("%s\n", symbol_map[index].file_name);
  1270.       last = symbol_map[index].file_name;
  1271.     } 
  1272. }
  1273.