gprof/cg_print.c

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