gprof/cg_print.c

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