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