8 * Return value of comparison functions used to sort tables:
14 static void order_and_dump_functions_by_arcs PARAMS ((Arc **, 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));
21 double print_time = 0.0;
25 DEFUN_VOID (print_header)
35 if (!bsd_style_output)
37 if (print_descriptions)
39 printf ("\t\t Call graph (explanation follows)\n\n");
43 printf ("\t\t\tCall graph\n\n");
46 printf ("\ngranularity: each sample hit covers %ld byte(s)",
47 (long) hist_scale * sizeof (UNIT));
50 printf (" for %.2f%% of %.2f seconds\n\n",
51 100.0 / print_time, print_time / hz);
55 printf (" no time propagated\n\n");
57 * This doesn't hurt, since all the numerators will be 0.0:
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");
74 printf ("index %% time self children called name\n");
80 * Print a cycle header.
83 DEFUN (print_cycle, (cyc), Sym * cyc)
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)
95 printf ("+%-7d", cyc->cg.self_calls);
99 printf (" %7.7s", "");
101 printf (" <cycle %d as a whole> [%d]\n", cyc->cg.cyc.num, cyc->cg.index);
106 * Compare LEFT and RIGHT membmer. Major comparison key is
107 * CG.PROP.SELF+CG.PROP.CHILD, secondary key is NCALLS+CG.SELF_CALLS.
110 DEFUN (cmp_member, (left, right), Sym * left AND Sym * right)
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;
117 if (left_time > right_time)
121 if (left_time < right_time)
126 if (left_calls > right_calls)
130 if (left_calls < right_calls)
139 * Sort members of a cycle.
142 DEFUN (sort_members, (cyc), Sym * cyc)
144 Sym *todo, *doing, *prev;
146 * Detach cycle members from cyclehead, and insertion sort them
149 todo = cyc->cg.cyc.next;
150 cyc->cg.cyc.next = 0;
151 for (doing = todo; doing && doing->cg.cyc.next; doing = todo)
153 todo = doing->cg.cyc.next;
154 for (prev = cyc; prev->cg.cyc.next; prev = prev->cg.cyc.next)
156 if (cmp_member (doing, prev->cg.cyc.next) == GREATERTHAN)
161 doing->cg.cyc.next = prev->cg.cyc.next;
162 prev->cg.cyc.next = doing;
168 * Print the members of a cycle.
171 DEFUN (print_members, (cyc), Sym * cyc)
176 for (member = cyc->cg.cyc.next; member; member = member->cg.cyc.next)
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,
183 if (member->cg.self_calls != 0)
185 printf ("+%-7d", member->cg.self_calls);
189 printf (" %7.7s", "");
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
208 DEFUN (cmp_arc, (left, right), Arc * left AND Arc * right)
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;
217 printf ("[cmp_arc] ");
218 print_name (left_parent);
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);
226 print_name (right_child);
227 printf (" %f + %f %d/%d\n", right->time, right->child_time,
228 right->count, right_child->ncalls);
231 if (left_parent == left_child)
233 return LESSTHAN; /* left is a self call */
235 if (right_parent == right_child)
237 return GREATERTHAN; /* right is a self call */
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)
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)
247 /* right is a call within the cycle, too */
248 if (left->count < right->count)
252 if (left->count > right->count)
260 /* right isn't a call within the cycle */
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)
270 /* right is a call within a cycle */
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)
282 if (left_time > right_time)
286 if (left->count < right->count)
290 if (left->count > right->count)
301 DEFUN (sort_parents, (child), Sym * child)
303 Arc *arc, *detached, sorted, *prev;
306 * Unlink parents from child, then insertion sort back on to
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.
313 sorted.next_parent = 0;
314 for (arc = child->cg.parents; arc; arc = detached)
316 detached = arc->next_parent;
318 /* consider *arc as disconnected; insert it into sorted: */
319 for (prev = &sorted; prev->next_parent; prev = prev->next_parent)
321 if (cmp_arc (arc, prev->next_parent) != GREATERTHAN)
326 arc->next_parent = prev->next_parent;
327 prev->next_parent = arc;
330 /* reattach sorted arcs to child: */
331 child->cg.parents = sorted.next_parent;
336 DEFUN (print_parents, (child), Sym * child)
342 if (child->cg.cyc.head != 0)
344 cycle_head = child->cg.cyc.head;
350 if (!child->cg.parents)
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 "", "", "", "", "", "");
358 sort_parents (child);
359 for (arc = child->cg.parents; arc; arc = arc->next_parent)
361 parent = arc->parent;
362 if (child == parent || (child->cg.cyc.num != 0
363 && parent->cg.cyc.num == child->cg.cyc.num))
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 ",
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 ",
381 arc->time / hz, arc->child_time / hz,
382 arc->count, cycle_head->ncalls);
391 DEFUN (sort_children, (parent), Sym * parent)
393 Arc *arc, *detached, sorted, *prev;
395 * Unlink children from parent, then insertion sort back on to
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.
402 sorted.next_child = 0;
403 for (arc = parent->cg.children; arc; arc = detached)
405 detached = arc->next_child;
407 /* consider *arc as disconnected; insert it into sorted: */
408 for (prev = &sorted; prev->next_child; prev = prev->next_child)
410 if (cmp_arc (arc, prev->next_child) != LESSTHAN)
415 arc->next_child = prev->next_child;
416 prev->next_child = arc;
419 /* reattach sorted children to parent: */
420 parent->cg.children = sorted.next_child;
425 DEFUN (print_children, (parent), Sym * parent)
430 sort_children (parent);
431 arc = parent->cg.children;
432 for (arc = parent->cg.children; arc; arc = arc->next_child)
435 if (child == parent || (child->cg.cyc.num != 0
436 && child->cg.cyc.num == parent->cg.cyc.num))
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, "");
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 ",
453 arc->time / hz, arc->child_time / hz,
454 arc->count, child->cg.cyc.head->ncalls);
463 DEFUN (print_line, (np), Sym * np)
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)
475 printf (" %7d", np->ncalls);
476 if (np->cg.self_calls != 0)
478 printf ("+%-7d ", np->cg.self_calls);
482 printf (" %7.7s ", "");
487 printf (" %7.7s %7.7s ", "", "");
495 * Print dynamic call graph.
498 DEFUN (cg_print, (timesortsym), Sym ** timesortsym)
503 if (print_descriptions && bsd_style_output)
505 bsd_callg_blurb (stdout);
510 for (index = 0; index < symtab.len + num_cycles; ++index)
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))
521 if (!parent->name && parent->cg.cyc.num != 0)
524 print_cycle (parent);
525 print_members (parent);
529 print_parents (parent);
531 print_children (parent);
533 if (bsd_style_output)
535 printf ("-----------------------------------------------\n");
536 if (bsd_style_output)
540 if (print_descriptions && !bsd_style_output)
542 fsf_callg_blurb (stdout);
548 DEFUN (cmp_name, (left, right), const PTR left AND const PTR right)
550 const Sym **npp1 = (const Sym **) left;
551 const Sym **npp2 = (const Sym **) right;
553 return strcmp ((*npp1)->name, (*npp2)->name);
558 DEFUN_VOID (cg_print_index)
561 unsigned int nnames, todo, i, j;
562 int col, starting_col;
563 Sym **name_sorted_syms, *sym;
564 const char *filename;
566 int column_width = (output_width - 1) / 3; /* don't write in last col! */
568 * Now, sort regular function name alphabetically to create an
571 name_sorted_syms = (Sym **) xmalloc ((symtab.len + num_cycles) * sizeof (Sym *));
572 for (index = 0, nnames = 0; index < symtab.len; index++)
574 if (ignore_zeros && symtab.base[index].ncalls == 0
575 && symtab.base[index].hist.time == 0)
579 name_sorted_syms[nnames++] = &symtab.base[index];
581 qsort (name_sorted_syms, nnames, sizeof (Sym *), cmp_name);
582 for (index = 1, todo = nnames; index <= num_cycles; index++)
584 name_sorted_syms[todo++] = &cycle_header[index];
586 printf ("\f\nIndex by function name\n\n");
587 index = (todo + 2) / 3;
588 for (i = 0; i < index; i++)
592 for (j = i; j < todo; j += index)
594 sym = name_sorted_syms[j];
595 if (sym->cg.print_flag)
597 sprintf (buf, "[%d]", sym->cg.index);
601 sprintf (buf, "(%d)", sym->cg.index);
605 if (bsd_style_output)
607 printf ("%6.6s %-19.19s", buf, sym->name);
612 for (; col < starting_col + 5; ++col)
616 printf (" %s ", buf);
617 col += print_name_only (sym);
618 if (!line_granularity && sym->is_static && sym->file)
620 filename = sym->file->name;
623 filename = strrchr (filename, '/');
630 filename = sym->file->name;
633 printf (" (%s)", filename);
634 col += strlen (filename) + 3;
640 if (bsd_style_output)
642 printf ("%6.6s ", buf);
643 sprintf (buf, "<cycle %d>", sym->cg.cyc.num);
644 printf ("%-19.19s", buf);
649 for (; col < starting_col + 5; ++col)
651 printf (" %s ", buf);
652 sprintf (buf, "<cycle %d>", sym->cg.cyc.num);
657 starting_col += column_width;
661 free (name_sorted_syms);
664 /* Compare two arcs based on their usage counts. We want to sort
665 in descending order. */
667 DEFUN (cmp_arc_count, (left, right), const PTR left AND const PTR right)
669 const Arc **npp1 = (const Arc **) left;
670 const Arc **npp2 = (const Arc **) right;
672 if ((*npp1)->count > (*npp2)->count)
674 else if ((*npp1)->count < (*npp2)->count)
680 /* Compare two funtions based on their usage counts. We want to sort
681 in descending order. */
683 DEFUN (cmp_fun_nuses, (left, right), const PTR left AND const PTR right)
685 const Sym **npp1 = (const Sym **) left;
686 const Sym **npp2 = (const Sym **) right;
688 if ((*npp1)->nuses > (*npp2)->nuses)
690 else if ((*npp1)->nuses < (*npp2)->nuses)
696 /* Print a suggested function ordering based on the profiling data.
698 We perform 4 major steps when ordering functions:
700 * Group unused functions together and place them at the
701 end of the function order.
703 * Search the highest use arcs (those which account for 90% of
704 the total arc count) for functions which have several parents.
706 Group those with the most call sites together (currently the
707 top 1.25% which have at least five different call sites).
709 These are emitted at the start of the function order.
711 * Use a greedy placement algorithm to place functions which
712 occur in the top 99% of the arcs in the profile. Some provisions
713 are made to handle high usage arcs where the parent and/or
714 child has already been placed.
716 * Run the same greedy placement algorithm on the remaining
717 arcs to place the leftover functions.
720 The various "magic numbers" should (one day) be tuneable by command
721 line options. They were arrived at by benchmarking a few applications
722 with various values to see which values produced better overall function
725 Of course, profiling errors, machine limitations (PA long calls), and
726 poor cutoff values for the placement algorithm may limit the usefullness
727 of the resulting function order. Improvements would be greatly appreciated.
731 * Place the functions with many callers near the middle of the
732 list to reduce long calls.
734 * Propagate arc usage changes as functions are placed. Ie if
735 func1 and func2 are placed together, arcs to/from those arcs
736 to the same parent/child should be combined, then resort the
737 arcs to choose the next one.
739 * Implement some global positioning algorithm to place the
740 chains made by the greedy local positioning algorithm. Probably
741 by examining arcs which haven't been placed yet to tie two
744 * Take a function's size and time into account in the algorithm;
745 size in particular is important on the PA (long calls). Placing
746 many small functions onto their own page may be wise.
748 * Use better profiling information; many published algorithms
749 are based on call sequences through time, rather than just
752 * Prodecure cloning could improve performance when a small number
753 of arcs account for most of the calls to a particular function.
755 * Use relocation information to avoid moving unused functions
756 completely out of the code stream; this would avoid severe lossage
757 when the profile data bears little resemblance to actual runs.
759 * Propagation of arc usages should also improve .o link line
760 ordering which shares the same arc placement algorithm with
761 the function ordering code (in fact it is a degenerate case
762 of function ordering). */
765 DEFUN_VOID (cg_print_function_ordering)
767 unsigned long index, used, unused, scratch_index;
768 unsigned long unplaced_arc_count, high_arc_count, scratch_arc_count;
770 unsigned long long total_arcs, tmp_arcs_count;
772 unsigned long total_arcs, tmp_arcs_count;
774 Sym **unused_syms, **used_syms, **scratch_syms;
775 Arc **unplaced_arcs, **high_arcs, **scratch_arcs;
781 unplaced_arc_count = 0;
783 scratch_arc_count = 0;
785 /* First group all the unused functions together. */
786 unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
787 used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
788 scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
789 high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
790 scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
791 unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
793 /* Walk through all the functions; mark those which are never
794 called as placed (we'll emit them as a group later). */
795 for (index = 0, used = 0, unused = 0; index < symtab.len; index++)
797 if (symtab.base[index].ncalls == 0)
799 /* Filter out gprof generated names. */
800 if (strcmp (symtab.base[index].name, "<locore>")
801 && strcmp (symtab.base[index].name, "<hicore>"))
803 unused_syms[unused++] = &symtab.base[index];
804 symtab.base[index].has_been_placed = 1;
809 used_syms[used++] = &symtab.base[index];
810 symtab.base[index].has_been_placed = 0;
811 symtab.base[index].next = 0;
812 symtab.base[index].prev = 0;
813 symtab.base[index].nuses = 0;
817 /* Sort the arcs from most used to least used. */
818 qsort (arcs, numarcs, sizeof (Arc *), cmp_arc_count);
820 /* Compute the total arc count. Also mark arcs as unplaced.
822 Note we don't compensate for overflow if that happens!
823 Overflow is much less likely when this file is compiled
824 with GCC as it can double-wide integers via long long. */
826 for (index = 0; index < numarcs; index++)
828 total_arcs += arcs[index]->count;
829 arcs[index]->has_been_placed = 0;
832 /* We want to pull out those functions which are referenced
833 by many highly used arcs and emit them as a group. This
834 could probably use some tuning. */
836 for (index = 0; index < numarcs; index++)
838 tmp_arcs_count += arcs[index]->count;
840 /* Count how many times each parent and child are used up
841 to our threshhold of arcs (90%). */
842 if ((double)tmp_arcs_count / (double)total_arcs > 0.90)
845 arcs[index]->child->nuses++;
848 /* Now sort a temporary symbol table based on the number of
849 times each function was used in the highest used arcs. */
850 memcpy (scratch_syms, used_syms, used * sizeof (Sym *));
851 qsort (scratch_syms, used, sizeof (Sym *), cmp_fun_nuses);
853 /* Now pick out those symbols we're going to emit as
854 a group. We take up to 1.25% of the used symbols. */
855 for (index = 0; index < used / 80; index++)
857 Sym *sym = scratch_syms[index];
860 /* If we hit symbols that aren't used from many call sites,
861 then we can quit. We choose five as the low limit for
862 no particular reason. */
866 /* We're going to need the arcs between these functions.
867 Unfortunately, we don't know all these functions
868 until we're done. So we keep track of all the arcs
869 to the functions we care about, then prune out those
870 which are uninteresting.
872 An interesting variation would be to quit when we found
873 multi-call site functions which account for some percentage
876 arc = sym->cg.children;
879 if (arc->parent != arc->child)
880 scratch_arcs[scratch_arc_count++] = arc;
881 arc->has_been_placed = 1;
882 arc = arc->next_child;
885 arc = sym->cg.parents;
888 if (arc->parent != arc->child)
889 scratch_arcs[scratch_arc_count++] = arc;
890 arc->has_been_placed = 1;
891 arc = arc->next_parent;
894 /* Keep track of how many symbols we're going to place. */
895 scratch_index = index;
897 /* A lie, but it makes identifying these functions easier
899 sym->has_been_placed = 1;
902 /* Now walk through the temporary arcs and copy those we care about
903 into the high arcs array. */
904 for (index = 0; index < scratch_arc_count; index++)
906 Arc *arc = scratch_arcs[index];
908 /* If this arc refers to highly used functions, then
909 then we want to keep it. */
910 if (arc->child->has_been_placed
911 && arc->parent->has_been_placed)
913 high_arcs[high_arc_count++] = scratch_arcs[index];
915 /* We need to turn of has_been_placed since we're going to
916 use the main arc placement algorithm on these arcs. */
917 arc->child->has_been_placed = 0;
918 arc->parent->has_been_placed = 0;
922 /* Dump the multi-site high usage functions which are not going
923 to be ordered by the main ordering algorithm. */
924 for (index = 0; index < scratch_index; index++)
926 if (scratch_syms[index]->has_been_placed)
927 printf ("%s\n", scratch_syms[index]->name);
930 /* Now we can order the multi-site high use functions based on the
931 arcs between them. */
932 qsort (high_arcs, high_arc_count, sizeof (Arc *), cmp_arc_count);
933 order_and_dump_functions_by_arcs (high_arcs, high_arc_count, 1,
934 unplaced_arcs, &unplaced_arc_count);
936 /* Order and dump the high use functions left, these typically
937 have only a few call sites. */
938 order_and_dump_functions_by_arcs (arcs, numarcs, 0,
939 unplaced_arcs, &unplaced_arc_count);
941 /* Now place the rarely used functions. */
942 order_and_dump_functions_by_arcs (unplaced_arcs, unplaced_arc_count, 1,
943 scratch_arcs, &scratch_arc_count);
945 /* Output any functions not emitted by the order_and_dump calls. */
946 for (index = 0; index < used; index++)
947 if (used_syms[index]->has_been_placed == 0)
948 printf("%s\n", used_syms[index]->name);
950 /* Output the unused functions. */
951 for (index = 0; index < unused; index++)
952 printf("%s\n", unused_syms[index]->name);
954 unused_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
955 used_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
956 scratch_syms = (Sym **) xmalloc (symtab.len * sizeof (Sym *));
957 high_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
958 scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
959 unplaced_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
966 free (unplaced_arcs);
969 /* Place functions based on the arcs in ARCS with NUMARCS entries;
970 place unused arcs into UNPLACED_ARCS/UNPLACED_ARC_COUNT.
972 If ALL is nonzero, then place all functions referenced by ARCS,
973 else only place those referenced in the top 99% of the arcs in ARCS. */
977 order_and_dump_functions_by_arcs (arcs, numarcs, all,
978 unplaced_arcs, unplaced_arc_count)
980 unsigned long numarcs;
983 unsigned long *unplaced_arc_count;
986 unsigned long long tmp_arcs, total_arcs;
988 unsigned long tmp_arcs, total_arcs;
992 /* If needed, compute the total arc count.
994 Note we don't compensate for overflow if that happens! */
998 for (index = 0; index < numarcs; index++)
999 total_arcs += arcs[index]->count;
1005 for (index = 0; index < numarcs; index++)
1008 Sym *child, *parent;
1010 tmp_arcs += arcs[index]->count;
1012 /* Ignore this arc if it's already been placed. */
1013 if (arcs[index]->has_been_placed)
1016 child = arcs[index]->child;
1017 parent = arcs[index]->parent;
1019 /* If we're not using all arcs, and this is a rarely used
1020 arc, then put it on the unplaced_arc list. Similarly
1021 if both the parent and child of this arc have been placed. */
1022 if ((! all && (double)tmp_arcs / (double)total_arcs > MOST)
1023 || child->has_been_placed || parent->has_been_placed)
1025 unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
1029 /* If all slots in the parent and child are full, then there isn't
1030 anything we can do right now. We'll place this arc on the
1031 unplaced arc list in the hope that a global positioning
1032 algorithm can use it to place function chains. */
1033 if (parent->next && parent->prev && child->next && child->prev)
1035 unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
1039 /* If the parent is unattached, then find the closest
1040 place to attach it onto child's chain. Similarly
1041 for the opposite case. */
1042 if (!parent->next && !parent->prev)
1049 /* Walk to the beginning and end of the child's chain. */
1062 /* Choose the closest. */
1063 child = next_count < prev_count ? next : prev;
1065 else if (! child->next && !child->prev)
1084 parent = prev_count < next_count ? prev : next;
1088 /* Couldn't find anywhere to attach the functions,
1089 put the arc on the unplaced arc list. */
1090 unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
1094 /* Make sure we don't tie two ends together. */
1114 /* This would tie two ends together. */
1115 unplaced_arcs[(*unplaced_arc_count)++] = arcs[index];
1121 /* Must attach to the parent's prev field. */
1124 /* parent-prev and child-next */
1125 parent->prev = child;
1126 child->next = parent;
1127 arcs[index]->has_been_placed = 1;
1130 else if (parent->prev)
1132 /* Must attach to the parent's next field. */
1135 /* parent-next and child-prev */
1136 parent->next = child;
1137 child->prev = parent;
1138 arcs[index]->has_been_placed = 1;
1143 /* Can attach to either field in the parent, depends
1144 on where we've got space in the child. */
1147 /* parent-prev and child-next */
1148 parent->prev = child;
1149 child->next = parent;
1150 arcs[index]->has_been_placed = 1;
1154 /* parent-next and child-prev */
1155 parent->next = child;
1156 child->prev = parent;
1157 arcs[index]->has_been_placed = 1;
1162 /* Dump the chains of functions we've made. */
1163 for (index = 0; index < numarcs; index++)
1166 if (arcs[index]->parent->has_been_placed
1167 || arcs[index]->child->has_been_placed)
1170 sym = arcs[index]->parent;
1172 /* If this symbol isn't attached to any other
1173 symbols, then we've got a rarely used arc.
1175 Skip it for now, we'll deal with them later. */
1176 if (sym->next == NULL
1177 && sym->prev == NULL)
1180 /* Get to the start of this chain. */
1186 /* Mark it as placed. */
1187 sym->has_been_placed = 1;
1188 printf ("%s\n", sym->name);
1193 /* If we want to place all the arcs, then output those which weren't
1194 placed by the main algorithm. */
1196 for (index = 0; index < numarcs; index++)
1199 if (arcs[index]->parent->has_been_placed
1200 || arcs[index]->child->has_been_placed)
1203 sym = arcs[index]->parent;
1205 sym->has_been_placed = 1;
1206 printf ("%s\n", sym->name);
1210 /* Print a suggested .o ordering for files on a link line based
1211 on profiling information. This uses the function placement
1212 code for the bulk of its work. */
1214 struct function_map {
1215 char *function_name;
1220 DEFUN_VOID (cg_print_file_ordering)
1222 unsigned long scratch_arc_count, index;
1224 extern struct function_map *symbol_map;
1225 extern unsigned int symbol_map_count;
1228 scratch_arc_count = 0;
1230 scratch_arcs = (Arc **) xmalloc (numarcs * sizeof (Arc *));
1231 for (index = 0; index < numarcs; index++)
1233 if (! arcs[index]->parent->mapped
1234 || ! arcs[index]->child->mapped)
1235 arcs[index]->has_been_placed = 1;
1238 order_and_dump_functions_by_arcs (arcs, numarcs, 0,
1239 scratch_arcs, &scratch_arc_count);
1241 /* Output .o's not handled by the main placement algorithm. */
1242 for (index = 0; index < symtab.len; index++)
1244 if (symtab.base[index].mapped
1245 && ! symtab.base[index].has_been_placed)
1246 printf ("%s\n", symtab.base[index].name);
1249 /* Now output any .o's that didn't have any text symbols. */
1251 for (index = 0; index < symbol_map_count; index++)
1253 unsigned int index2;
1255 /* Don't bother searching if this symbol is the
1256 same as the previous one. */
1257 if (last && !strcmp (last, symbol_map[index].file_name))
1260 for (index2 = 0; index2 < symtab.len; index2++)
1262 if (! symtab.base[index2].mapped)
1265 if (!strcmp (symtab.base[index2].name, symbol_map[index].file_name))
1269 /* If we didn't find it in the symbol table, then it must be a .o
1270 with no text symbols. Output it last. */
1271 if (index2 == symtab.len)
1272 printf ("%s\n", symbol_map[index].file_name);
1273 last = symbol_map[index].file_name;