gprof/cg_print.c

   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 %7lu"
  90           : "%-6.6s %5.1f %7.2f %7.2f %7lu", 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 ("+%-7lu", 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   unsigned long left_calls = left->ncalls + left->cg.self_calls;
 115   unsigned 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 %7lu"
 180               : "%6.6s %5.5s %7.2f %7.2f %7lu",
 181               "", "", member->cg.prop.self / hz, member->cg.prop.child / hz,
 182               member->ncalls);
 183       if (member->cg.self_calls != 0)
 184         {
 185           printf ("+%-7lu", 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 %lu/%lu\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 %lu/%lu\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 %7lu %7.7s     "
 368                   : "%6.6s %5.5s %7.7s %7.7s %7lu %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 %7lu/%-7lu     "
 379                   : "%6.6s %5.5s %7.2f %7.2f %7lu/%-7lu     ",
 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 %7lu %7.7s     "
 441                   : "%6.6s %5.5s %7.7s %7.7s %7lu %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 %7lu/%-7lu     "
 451                   : "%6.6s %5.5s %7.2f %7.2f %7lu/%-7lu     ",
 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 (" %7lu", np->ncalls);
 476       if (np->cg.self_calls != 0)
 477         {
 478           printf ("+%-7lu ", 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   unsigned 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           || (line_granularity && ! parent->is_func))
 518         {
 519           continue;
 520         }
 521       if (!parent->name && parent->cg.cyc.num != 0)
 522         {
 523           /* cycle header: */
 524           print_cycle (parent);
 525           print_members (parent);
 526         }
 527       else
 528         {
 529           print_parents (parent);
 530           print_line (parent);
 531           print_children (parent);
 532         }
 533       if (bsd_style_output)
 534         printf ("\n");
 535       printf ("-----------------------------------------------\n");
 536       if (bsd_style_output)
 537         printf ("\n");
 538     }
 539   free (timesortsym);
 540   if (print_descriptions && !bsd_style_output)
 541     {
 542       fsf_callg_blurb (stdout);
 543     }
 544 }
 545
 546
 547 static int
 548 DEFUN (cmp_name, (left, right), const PTR left AND const PTR right)
 549 {
 550   const Sym **npp1 = (const Sym **) left;
 551   const Sym **npp2 = (const Sym **) right;
 552
 553   return strcmp ((*npp1)->name, (*npp2)->name);
 554 }
 555
 556
 557 void
 558 DEFUN_VOID (cg_print_index)
 559 {
 560   unsigned int index;
 561   unsigned int nnames, todo, i, j;
 562   int col, starting_col;
 563   Sym **name_sorted_syms, *sym;
 564   const char *filename;
 565   char buf[20];
 566   int column_width = (output_width - 1) / 3;    /* don't write in last col! */
 567   /*
 568    * Now, sort regular function name alphabetically to create an
 569    * index:
 570    */
 571   name_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
 572   for (index = 0, nnames = 0; index < symtab.len; index++)
 573     {
 574       if (ignore_zeros && symtab.base[index].ncalls == 0
 575           && symtab.base[index].hist.time == 0)
 576         {
 577           continue;
 578         }
 579       name_sorted_syms[nnames++] = &symtab.base[index];
 580     }
 581   qsort (name_sorted_syms, nnames, sizeof (Sym *), cmp_name);
 582   for (index = 1, todo = nnames; index <= num_cycles; index++)
 583     {
 584       name_sorted_syms[todo++] = &cycle_header[index];
 585     }
 586   printf ("\f\n");
 587   printf (_("Index by function name\n\n"));
 588   index = (todo + 2) / 3;
 589   for (i = 0; i < index; i++)
 590     {
 591       col = 0;
 592       starting_col = 0;
 593       for (j = i; j < todo; j += index)
 594         {
 595           sym = name_sorted_syms[j];
 596           if (sym->cg.print_flag)
 597             {
 598               sprintf (buf, "[%d]", sym->cg.index);
 599             }
 600           else
 601             {
 602               sprintf (buf, "(%d)", sym->cg.index);
 603             }
 604           if (j < nnames)
 605             {
 606               if (bsd_style_output)
 607                 {
 608                   printf ("%6.6s %-19.19s", buf, sym->name);
 609                 }
 610               else
 611                 {
 612                   col += strlen (buf);
 613                   for (; col < starting_col + 5; ++col)
 614                     {
 615                       putchar (' ');
 616                     }
 617                   printf (" %s ", buf);
 618                   col += print_name_only (sym);
 619                   if (!line_granularity && sym->is_static && sym->file)
 620                     {
 621                       filename = sym->file->name;
 622                       if (!print_path)
 623                         {
 624                           filename = strrchr (filename, '/');
 625                           if (filename)
 626                             {
 627                               ++filename;
 628                             }
 629                           else
 630                             {
 631                               filename = sym->file->name;
 632                             }
 633                         }
 634                       printf (" (%s)", filename);
 635                       col += strlen (filename) + 3;
 636                     }
 637                 }
 638             }
 639           else
 640             {
 641               if (bsd_style_output)
 642                 {
 643                   printf ("%6.6s ", buf);
 644                   sprintf (buf, _("<cycle %d>"), sym->cg.cyc.num);
 645                   printf ("%-19.19s", buf);
 646                 }
 647               else
 648                 {
 649                   col += strlen (buf);
 650                   for (; col < starting_col + 5; ++col)
 651                     putchar (' ');
 652                   printf (" %s ", buf);
 653                   sprintf (buf, _("<cycle %d>"), sym->cg.cyc.num);
 654                   printf ("%s", buf);
 655                   col += strlen (buf);
 656                 }
 657             }
 658           starting_col += column_width;
 659         }
 660       printf ("\n");
 661     }
 662   free (name_sorted_syms);
 663 }
 664
 665 /* Compare two arcs based on their usage counts.  We want to sort
 666    in descending order.  */
 667 static int
 668 DEFUN (cmp_arc_count, (left, right), const PTR left AND const PTR right)
 669 {
 670   const Arc **npp1 = (const Arc **) left;
 671   const Arc **npp2 = (const Arc **) right;
 672
 673   if ((*npp1)->count > (*npp2)->count)
 674     return -1;
 675   else if ((*npp1)->count < (*npp2)->count)
 676     return 1;
 677   else
 678     return 0;
 679 }
 680
 681 /* Compare two funtions based on their usage counts.  We want to sort
 682    in descending order.  */
 683 static int
 684 DEFUN (cmp_fun_nuses, (left, right), const PTR left AND const PTR right)
 685 {
 686   const Sym **npp1 = (const Sym **) left;
 687   const Sym **npp2 = (const Sym **) right;
 688
 689   if ((*npp1)->nuses > (*npp2)->nuses)
 690     return -1;
 691   else if ((*npp1)->nuses < (*npp2)->nuses)
 692     return 1;
 693   else
 694     return 0;
 695 }
 696
 697 /* Print a suggested function ordering based on the profiling data.
 698
 699    We perform 4 major steps when ordering functions:
 700
 701         * Group unused functions together and place them at the
 702         end of the function order.
 703
 704         * Search the highest use arcs (those which account for 90% of
 705         the total arc count) for functions which have several parents.
 706
 707         Group those with the most call sites together (currently the
 708         top 1.25% which have at least five different call sites).
 709
 710         These are emitted at the start of the function order.
 711
 712         * Use a greedy placement algorithm to place functions which
 713         occur in the top 99% of the arcs in the profile.  Some provisions
 714         are made to handle high usage arcs where the parent and/or
 715         child has already been placed.
 716
 717         * Run the same greedy placement algorithm on the remaining
 718         arcs to place the leftover functions.
 719
 720
 721    The various "magic numbers" should (one day) be tuneable by command
 722    line options.  They were arrived at by benchmarking a few applications
 723    with various values to see which values produced better overall function
 724    orderings.
 725
 726    Of course, profiling errors, machine limitations (PA long calls), and
 727    poor cutoff values for the placement algorithm may limit the usefullness
 728    of the resulting function order.  Improvements would be greatly appreciated.
 729
 730    Suggestions:
 731
 732         * Place the functions with many callers near the middle of the
 733         list to reduce long calls.
 734
 735         * Propagate arc usage changes as functions are placed.  Ie if
 736         func1 and func2 are placed together, arcs to/from those arcs
 737         to the same parent/child should be combined, then resort the
 738         arcs to choose the next one.
 739
 740         * Implement some global positioning algorithm to place the
 741         chains made by the greedy local positioning algorithm.  Probably
 742         by examining arcs which haven't been placed yet to tie two
 743         chains together.
 744
 745         * Take a function's size and time into account in the algorithm;
 746         size in particular is important on the PA (long calls).  Placing
 747         many small functions onto their own page may be wise.
 748
 749         * Use better profiling information; many published algorithms
 750         are based on call sequences through time, rather than just
 751         arc counts.
 752
 753         * Prodecure cloning could improve performance when a small number
 754         of arcs account for most of the calls to a particular function.
 755
 756         * Use relocation information to avoid moving unused functions
 757         completely out of the code stream; this would avoid severe lossage
 758         when the profile data bears little resemblance to actual runs.
 759
 760         * Propagation of arc usages should also improve .o link line
 761         ordering which shares the same arc placement algorithm with
 762         the function ordering code (in fact it is a degenerate case
 763         of function ordering).  */
 764
 765 void
 766 DEFUN_VOID (cg_print_function_ordering)
 767 {
 768   unsigned long index, used, unused, scratch_index;
 769   unsigned long  unplaced_arc_count, high_arc_count, scratch_arc_count;
 770 #ifdef __GNUC__
 771   unsigned long long total_arcs, tmp_arcs_count;
 772 #else
 773   unsigned long total_arcs, tmp_arcs_count;
 774 #endif
 775   Sym **unused_syms, **used_syms, **scratch_syms;
 776   Arc **unplaced_arcs, **high_arcs, **scratch_arcs;
 777
 778   index = 0;
 779   used = 0;
 780   unused = 0;
 781   scratch_index = 0;
 782   unplaced_arc_count = 0;
 783   high_arc_count = 0;
 784   scratch_arc_count = 0;
 785
 786   /* First group all the unused functions together.  */
 787   unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
 788   used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
 789   scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
 790   high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
 791   scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
 792   unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
 793
 794   /* Walk through all the functions; mark those which are never
 795      called as placed (we'll emit them as a group later).  */
 796   for (index = 0, used = 0, unused = 0; index < symtab.len; index++)
 797     {
 798       if (symtab.base[index].ncalls == 0)
 799         {
 800           /* Filter out gprof generated names.  */
 801           if (strcmp (symtab.base[index].name, "<locore>")
 802               && strcmp (symtab.base[index].name, "<hicore>"))
 803             {
 804               unused_syms[unused++] = &symtab.base[index];
 805               symtab.base[index].has_been_placed = 1;
 806             }
 807         }
 808       else
 809         {
 810           used_syms[used++] = &symtab.base[index];
 811           symtab.base[index].has_been_placed = 0;
 812           symtab.base[index].next = 0;
 813           symtab.base[index].prev = 0;
 814           symtab.base[index].nuses = 0;
 815         }
 816     }
 817
 818   /* Sort the arcs from most used to least used.  */
 819   qsort (arcs, numarcs, sizeof (Arc *), cmp_arc_count);
 820
 821   /* Compute the total arc count.  Also mark arcs as unplaced.
 822
 823      Note we don't compensate for overflow if that happens!
 824      Overflow is much less likely when this file is compiled
 825      with GCC as it can double-wide integers via long long.  */
 826   total_arcs = 0;
 827   for (index = 0; index < numarcs; index++)
 828     {
 829       total_arcs += arcs[index]->count;
 830       arcs[index]->has_been_placed = 0;
 831     }
 832
 833   /* We want to pull out those functions which are referenced
 834      by many highly used arcs and emit them as a group.  This
 835      could probably use some tuning.  */
 836   tmp_arcs_count = 0;
 837   for (index = 0; index < numarcs; index++)
 838     {
 839       tmp_arcs_count += arcs[index]->count;
 840
 841       /* Count how many times each parent and child are used up
 842          to our threshhold of arcs (90%).  */
 843       if ((double)tmp_arcs_count / (double)total_arcs > 0.90)
 844         break;
 845
 846       arcs[index]->child->nuses++;
 847     }
 848
 849   /* Now sort a temporary symbol table based on the number of
 850      times each function was used in the highest used arcs.  */
 851   memcpy (scratch_syms, used_syms, used * sizeof (Sym *));
 852   qsort (scratch_syms, used, sizeof (Sym *), cmp_fun_nuses);
 853
 854   /* Now pick out those symbols we're going to emit as
 855      a group.  We take up to 1.25% of the used symbols.  */
 856   for (index = 0; index < used / 80; index++)
 857     {
 858       Sym *sym = scratch_syms[index];
 859       Arc *arc;
 860
 861       /* If we hit symbols that aren't used from many call sites,
 862          then we can quit.  We choose five as the low limit for
 863          no particular reason.  */
 864       if (sym->nuses == 5)
 865         break;
 866
 867       /* We're going to need the arcs between these functions.
 868          Unfortunately, we don't know all these functions
 869          until we're done.  So we keep track of all the arcs
 870          to the functions we care about, then prune out those
 871          which are uninteresting.
 872
 873          An interesting variation would be to quit when we found
 874          multi-call site functions which account for some percentage
 875          of the arcs.  */
 876
 877       arc = sym->cg.children;
 878       while (arc)
 879         {
 880           if (arc->parent != arc->child)
 881             scratch_arcs[scratch_arc_count++] = arc;
 882           arc->has_been_placed = 1;
 883           arc = arc->next_child;
 884         }
 885
 886       arc = sym->cg.parents;
 887       while (arc)
 888         {
 889           if (arc->parent != arc->child)
 890             scratch_arcs[scratch_arc_count++] = arc;
 891           arc->has_been_placed = 1;
 892           arc = arc->next_parent;
 893         }
 894
 895       /* Keep track of how many symbols we're going to place.  */
 896       scratch_index = index;
 897
 898       /* A lie, but it makes identifying these functions easier
 899          later.  */
 900       sym->has_been_placed = 1;
 901     }
 902
 903   /* Now walk through the temporary arcs and copy those we care about
 904      into the high arcs array.  */
 905   for (index = 0; index < scratch_arc_count; index++)
 906     {
 907       Arc *arc = scratch_arcs[index];
 908
 909       /* If this arc refers to highly used functions, then
 910          then we want to keep it.  */
 911       if (arc->child->has_been_placed
 912           && arc->parent->has_been_placed)
 913         {
 914           high_arcs[high_arc_count++] = scratch_arcs[index];
 915
 916           /* We need to turn of has_been_placed since we're going to
 917              use the main arc placement algorithm on these arcs.  */
 918           arc->child->has_been_placed = 0;
 919           arc->parent->has_been_placed = 0;
 920         }
 921     }
 922
 923   /* Dump the multi-site high usage functions which are not going
 924      to be ordered by the main ordering algorithm.  */
 925   for (index = 0; index < scratch_index; index++)
 926     {
 927       if (scratch_syms[index]->has_been_placed)
 928         printf ("%s\n", scratch_syms[index]->name);
 929     }
 930
 931   /* Now we can order the multi-site high use functions based on the
 932      arcs between them.  */
 933   qsort (high_arcs, high_arc_count, sizeof (Arc *), cmp_arc_count);
 934   order_and_dump_functions_by_arcs (high_arcs, high_arc_count, 1,
 935                                     unplaced_arcs, &unplaced_arc_count);
 936
 937   /* Order and dump the high use functions left, these typically
 938      have only a few call sites.  */
 939   order_and_dump_functions_by_arcs (arcs, numarcs, 0,
 940                                     unplaced_arcs, &unplaced_arc_count);
 941
 942   /* Now place the rarely used functions.  */
 943   order_and_dump_functions_by_arcs (unplaced_arcs, unplaced_arc_count, 1,
 944                                     scratch_arcs, &scratch_arc_count);
 945
 946   /* Output any functions not emitted by the order_and_dump calls.  */
 947   for (index = 0; index < used; index++)
 948     if (used_syms[index]->has_been_placed == 0)
 949       printf("%s\n", used_syms[index]->name);
 950
 951   /* Output the unused functions.  */
 952   for (index = 0; index < unused; index++)
 953     printf("%s\n", unused_syms[index]->name);
 954
 955   unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
 956   used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
 957   scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
 958   high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
 959   scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
 960   unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
 961
 962   free (unused_syms);
 963   free (used_syms);
 964   free (scratch_syms);
 965   free (high_arcs);
 966   free (scratch_arcs);
 967   free (unplaced_arcs);
 968 }
 969
 970 /* Place functions based on the arcs in ARCS with NUMARCS entries;
 971    place unused arcs into UNPLACED_ARCS/UNPLACED_ARC_COUNT.
 972
 973    If ALL is nonzero, then place all functions referenced by ARCS,
 974    else only place those referenced in the top 99% of the arcs in ARCS.  */
 975
 976 #define MOST 0.99
 977 static void
 978 order_and_dump_functions_by_arcs (arcs, numarcs, all,
 979                                   unplaced_arcs, unplaced_arc_count)
 980      Arc **arcs;
 981      unsigned long numarcs;
 982      int all;
 983      Arc **unplaced_arcs;
 984      unsigned long *unplaced_arc_count;
 985 {
 986 #ifdef __GNUC__
 987   unsigned long long tmp_arcs, total_arcs;
 988 #else
 989   unsigned long tmp_arcs, total_arcs;
 990 #endif
 991   unsigned int index;
 992
 993   /* If needed, compute the total arc count.
 994
 995      Note we don't compensate for overflow if that happens!  */
 996   if (! all)
 997     {
 998       total_arcs = 0;
 999       for (index = 0; index < numarcs; index++)
1000         total_arcs += arcs[index]->count;
1001     }
1002   else
1003     total_arcs = 0;
1004
1005   tmp_arcs = 0;
1006   for (index = 0; index < numarcs; index++)
1007     {
1008       Sym *sym1, *sym2;
1009       Sym *child, *parent;
1010
1011       tmp_arcs += arcs[index]->count;
1012
1013       /* Ignore this arc if it's already been placed.  */
1014       if (arcs[index]->has_been_placed)
1015         continue;
1016
1017       child = arcs[index]->child;
1018       parent = arcs[index]->parent;
1019
1020       /* If we're not using all arcs, and this is a rarely used
1021          arc, then put it on the unplaced_arc list.  Similarly
1022          if both the parent and child of this arc have been placed.  */
1023       if ((! all && (double)tmp_arcs / (double)total_arcs > MOST)
1024           || child->has_been_placed || parent->has_been_placed)
1025         {
1026           unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
1027           continue;
1028         }
1029
1030       /* If all slots in the parent and child are full, then there isn't
1031          anything we can do right now.  We'll place this arc on the
1032          unplaced arc list in the hope that a global positioning
1033          algorithm can use it to place function chains.  */
1034       if (parent->next && parent->prev && child->next && child->prev)
1035         {
1036           unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
1037           continue;
1038         }
1039
1040       /* If the parent is unattached, then find the closest
1041          place to attach it onto child's chain.   Similarly
1042          for the opposite case.  */
1043       if (!parent->next && !parent->prev)
1044         {
1045           int next_count = 0;
1046           int prev_count = 0;
1047           Sym *prev = child;
1048           Sym *next = child;
1049
1050           /* Walk to the beginning and end of the child's chain.  */
1051           while (next->next)
1052             {
1053               next = next->next;
1054               next_count++;
1055             }
1056
1057           while (prev->prev)
1058             {
1059               prev = prev->prev;
1060               prev_count++;
1061             }
1062
1063           /* Choose the closest.  */
1064           child = next_count < prev_count ? next : prev;
1065       }
1066       else if (! child->next && !child->prev)
1067         {
1068           int next_count = 0;
1069           int prev_count = 0;
1070           Sym *prev = parent;
1071           Sym *next = parent;
1072
1073           while (next->next)
1074             {
1075               next = next->next;
1076               next_count++;
1077             }
1078
1079           while (prev->prev)
1080             {
1081               prev = prev->prev;
1082               prev_count++;
1083             }
1084
1085           parent = prev_count < next_count ? prev : next;
1086         }
1087       else
1088         {
1089           /* Couldn't find anywhere to attach the functions,
1090              put the arc on the unplaced arc list.  */
1091           unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
1092           continue;
1093         }
1094
1095       /* Make sure we don't tie two ends together.  */
1096       sym1 = parent;
1097       if (sym1->next)
1098         while (sym1->next)
1099           sym1 = sym1->next;
1100       else
1101         while (sym1->prev)
1102           sym1 = sym1->prev;
1103
1104       sym2 = child;
1105       if (sym2->next)
1106         while (sym2->next)
1107           sym2 = sym2->next;
1108       else
1109         while (sym2->prev)
1110           sym2 = sym2->prev;
1111
1112       if (sym1 == child
1113           && sym2 == parent)
1114         {
1115           /* This would tie two ends together.  */
1116           unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
1117           continue;
1118         }
1119
1120       if (parent->next)
1121         {
1122           /* Must attach to the parent's prev field.  */
1123           if (! child->next)
1124             {
1125               /* parent-prev and child-next */
1126               parent->prev = child;
1127               child->next = parent;
1128               arcs[index]->has_been_placed = 1;
1129             }
1130         }
1131       else if (parent->prev)
1132         {
1133           /* Must attach to the parent's next field.  */
1134           if (! child->prev)
1135             {
1136               /* parent-next and child-prev */
1137               parent->next = child;
1138               child->prev = parent;
1139               arcs[index]->has_been_placed = 1;
1140             }
1141         }
1142       else
1143         {
1144           /* Can attach to either field in the parent, depends
1145              on where we've got space in the child.  */
1146           if (child->prev)
1147             {
1148               /* parent-prev and child-next */
1149               parent->prev = child;
1150               child->next = parent;
1151               arcs[index]->has_been_placed = 1;
1152             }
1153           else
1154             {
1155               /* parent-next and child-prev */
1156               parent->next = child;
1157               child->prev = parent;
1158               arcs[index]->has_been_placed = 1;
1159             }
1160         }
1161     }
1162
1163   /* Dump the chains of functions we've made.  */
1164   for (index = 0; index < numarcs; index++)
1165     {
1166       Sym *sym;
1167       if (arcs[index]->parent->has_been_placed
1168           || arcs[index]->child->has_been_placed)
1169         continue;
1170
1171       sym = arcs[index]->parent;
1172
1173       /* If this symbol isn't attached to any other
1174          symbols, then we've got a rarely used arc.
1175
1176          Skip it for now, we'll deal with them later.  */
1177       if (sym->next == NULL
1178           && sym->prev == NULL)
1179         continue;
1180
1181       /* Get to the start of this chain.  */
1182       while (sym->prev)
1183         sym = sym->prev;
1184
1185       while (sym)
1186         {
1187           /* Mark it as placed.  */
1188           sym->has_been_placed = 1;
1189           printf ("%s\n", sym->name);
1190           sym = sym->next;
1191         }
1192     }
1193
1194   /* If we want to place all the arcs, then output those which weren't
1195      placed by the main algorithm.  */
1196   if (all)
1197     for (index = 0; index < numarcs; index++)
1198       {
1199         Sym *sym;
1200         if (arcs[index]->parent->has_been_placed
1201             || arcs[index]->child->has_been_placed)
1202           continue;
1203
1204         sym = arcs[index]->parent;
1205
1206         sym->has_been_placed = 1;
1207         printf ("%s\n", sym->name);
1208       }
1209 }
1210
1211 /* Print a suggested .o ordering for files on a link line based
1212    on profiling information.  This uses the function placement
1213    code for the bulk of its work.  */
1214
1215 struct function_map {
1216   char *function_name;
1217   char *file_name;
1218 };
1219
1220 void
1221 DEFUN_VOID (cg_print_file_ordering)
1222 {
1223   unsigned long scratch_arc_count, index;
1224   Arc **scratch_arcs;
1225   extern struct function_map *symbol_map;
1226   extern unsigned int symbol_map_count;
1227   char *last;
1228
1229   scratch_arc_count = 0;
1230
1231   scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
1232   for (index = 0; index < numarcs; index++)
1233     {
1234       if (! arcs[index]->parent->mapped
1235           || ! arcs[index]->child->mapped)
1236         arcs[index]->has_been_placed = 1;
1237     }
1238
1239   order_and_dump_functions_by_arcs (arcs, numarcs, 0,
1240                                     scratch_arcs, &scratch_arc_count);
1241
1242   /* Output .o's not handled by the main placement algorithm.  */
1243   for (index = 0; index < symtab.len; index++)
1244     {
1245       if (symtab.base[index].mapped
1246           && ! symtab.base[index].has_been_placed)
1247         printf ("%s\n", symtab.base[index].name);
1248     }
1249
1250   /* Now output any .o's that didn't have any text symbols.  */
1251   last = NULL;
1252   for (index = 0; index < symbol_map_count; index++)
1253     {
1254       unsigned int index2;
1255
1256       /* Don't bother searching if this symbol is the
1257          same as the previous one.  */
1258       if (last && !strcmp (last, symbol_map[index].file_name))
1259         continue;
1260
1261       for (index2 = 0; index2 < symtab.len; index2++)
1262         {
1263           if (! symtab.base[index2].mapped)
1264             continue;
1265
1266           if (!strcmp (symtab.base[index2].name, symbol_map[index].file_name))
1267             break;
1268         }
1269
1270       /* If we didn't find it in the symbol table, then it must be a .o
1271          with no text symbols.  Output it last.  */
1272       if (index2 == symtab.len)
1273         printf ("%s\n", symbol_map[index].file_name);
1274       last = symbol_map[index].file_name;
1275     }
1276 }