gcc/profile.c

   1 /* Calculate branch probabilities, and basic block execution counts.
   2    Copyright (C) 1990, 91, 92, 93, 94, 96, 1997 Free Software Foundation, Inc.
   3    Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
   4    based on some ideas from Dain Samples of UC Berkeley.
   5    Further mangling by Bob Manson, Cygnus Support.
   6
   7 This file is part of GNU CC.
   8
   9 GNU CC is free software; you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation; either version 2, or (at your option)
  12 any later version.
  13
  14 GNU CC is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GNU CC; see the file COPYING.  If not, write to
  21 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  22
  23 /* ??? Really should not put insns inside of LIBCALL sequences, when putting
  24    insns after a call, should look for the insn setting the retval, and
  25    insert the insns after that one.  */
  26
  27 /* ??? Register allocation should use basic block execution counts to
  28    give preference to the most commonly executed blocks.  */
  29
  30 /* ??? The .da files are not safe.  Changing the program after creating .da
  31    files or using different options when compiling with -fbranch-probabilities
  32    can result the arc data not matching the program.  Maybe add instrumented
  33    arc count to .bbg file?  Maybe check whether PFG matches the .bbg file?  */
  34
  35 /* ??? Should calculate branch probabilities before instrumenting code, since
  36    then we can use arc counts to help decide which arcs to instrument.  */
  37
  38 /* ??? Rearrange code so that the most frequently executed arcs become from
  39    one block to the next block (i.e. a fall through), move seldom executed
  40    code outside of loops even at the expense of adding a few branches to
  41    achieve this, see Dain Sample's UC Berkeley thesis.  */
  42
  43 #include "config.h"
  44 #include "rtl.h"
  45 #include "flags.h"
  46 #include "insn-flags.h"
  47 #include "insn-config.h"
  48 #include "output.h"
  49 #include <stdio.h>
  50 #include "tree.h"
  51 #include "output.h"
  52 #include "gcov-io.h"
  53
  54 extern char * xmalloc ();
  55 extern void free ();
  56
  57 /* One of these is dynamically created whenever we identify an arc in the
  58    function.  */
  59
  60 struct adj_list
  61 {
  62   int source;
  63   int target;
  64   int arc_count;
  65   unsigned int count_valid : 1;
  66   unsigned int on_tree : 1;
  67   unsigned int fake : 1;
  68   unsigned int fall_through : 1;
  69   rtx branch_insn;
  70   struct adj_list *pred_next;
  71   struct adj_list *succ_next;
  72 };
  73
  74 #define ARC_TARGET(ARCPTR) (ARCPTR->target)
  75 #define ARC_SOURCE(ARCPTR) (ARCPTR->source)
  76 #define ARC_COUNT(ARCPTR)  (ARCPTR->arc_count)
  77
  78 /* Count the number of basic blocks, and create an array of these structures,
  79    one for each bb in the function.  */
  80
  81 struct bb_info
  82 {
  83   struct adj_list *succ;
  84   struct adj_list *pred;
  85   int succ_count;
  86   int pred_count;
  87   int exec_count;
  88   unsigned int count_valid : 1;
  89   unsigned int on_tree : 1;
  90   rtx first_insn;
  91 };
  92
  93 /* Indexed by label number, gives the basic block number containing that
  94    label.  */
  95
  96 static int *label_to_bb;
  97
  98 /* Number of valid entries in the label_to_bb array.  */
  99
 100 static int label_to_bb_size;
 101
 102 /* Indexed by block index, holds the basic block graph.  */
 103
 104 static struct bb_info *bb_graph;
 105
 106 /* Name and file pointer of the output file for the basic block graph.  */
 107
 108 static char *bbg_file_name;
 109 static FILE *bbg_file;
 110
 111 /* Name and file pointer of the input file for the arc count data.  */
 112
 113 static char *da_file_name;
 114 static FILE *da_file;
 115
 116 /* Pointer of the output file for the basic block/line number map. */
 117 static FILE *bb_file;
 118
 119 /* Last source file name written to bb_file. */
 120
 121 static char *last_bb_file_name;
 122
 123 /* Indicates whether the next line number note should be output to
 124    bb_file or not.  Used to eliminate a redundant note after an
 125    expanded inline function call.  */
 126
 127 static int ignore_next_note;
 128
 129 /* Used by final, for allocating the proper amount of storage for the
 130    instrumented arc execution counts.  */
 131
 132 int count_instrumented_arcs;
 133
 134 /* Number of executions for the return label.  */
 135
 136 int return_label_execution_count;
 137
 138 /* Collect statistics on the performance of this pass for the entire source
 139    file.  */
 140
 141 static int total_num_blocks;
 142 static int total_num_arcs;
 143 static int total_num_arcs_instrumented;
 144 static int total_num_blocks_created;
 145 static int total_num_passes;
 146 static int total_num_times_called;
 147 static int total_hist_br_prob[20];
 148 static int total_num_never_executed;
 149 static int total_num_branches;
 150
 151 /* Forward declarations.  */
 152 static void init_arc PROTO((struct adj_list *, int, int, rtx));
 153 static void find_spanning_tree PROTO((int));
 154 static void expand_spanning_tree PROTO((int));
 155 static void fill_spanning_tree PROTO((int));
 156 static void init_arc_profiler PROTO((void));
 157 static void output_arc_profiler PROTO((int, rtx));
 158
 159 #ifndef LONG_TYPE_SIZE
 160 #define LONG_TYPE_SIZE BITS_PER_WORD
 161 #endif
 162
 163 /* If non-zero, we need to output a constructor to set up the
 164    per-object-file data. */
 165 static int need_func_profiler = 0;
 166
 167 \f
 168 /* Add arc instrumentation code to the entire insn chain.
 169
 170    F is the first insn of the chain.
 171    NUM_BLOCKS is the number of basic blocks found in F.
 172    DUMP_FILE, if nonzero, is an rtl dump file we can write to.  */
 173
 174 static void
 175 instrument_arcs (f, num_blocks, dump_file)
 176      rtx f;
 177      int num_blocks;
 178      FILE *dump_file;
 179 {
 180   register int i;
 181   register struct adj_list *arcptr, *backptr;
 182   int num_arcs = 0;
 183   int num_instr_arcs = 0;
 184   rtx insn;
 185
 186   int neg_one = -1;
 187   int zero = 0;
 188   int inverted;
 189   rtx note;
 190
 191   /* Instrument the program start.  */
 192   /* Handle block 0 specially, since it will always be instrumented,
 193      but it doesn't have a valid first_insn or branch_insn.  We must
 194      put the instructions before the NOTE_INSN_FUNCTION_BEG note, so
 195      that they don't clobber any of the parameters of the current
 196      function.  */
 197   for (insn = f; insn; insn = NEXT_INSN (insn))
 198     if (GET_CODE (insn) == NOTE
 199         && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
 200       break;
 201   insn = PREV_INSN (insn);
 202   need_func_profiler = 1;
 203   output_arc_profiler (total_num_arcs_instrumented + num_instr_arcs++, insn);
 204
 205   for (i = 1; i < num_blocks; i++)
 206     for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
 207       if (! arcptr->on_tree)
 208         {
 209           if (dump_file)
 210             fprintf (dump_file, "Arc %d to %d instrumented\n", i,
 211                      ARC_TARGET (arcptr));
 212
 213           /* Check to see if this arc is the only exit from its source block,
 214              or the only entrance to its target block.  In either case,
 215              we don't need to create a new block to instrument the arc.  */
 216
 217           if (bb_graph[i].succ == arcptr && arcptr->succ_next == 0)
 218             {
 219               /* Instrument the source block.  */
 220               output_arc_profiler (total_num_arcs_instrumented
 221                                    + num_instr_arcs++,
 222                                    PREV_INSN (bb_graph[i].first_insn));
 223             }
 224           else if (arcptr == bb_graph[ARC_TARGET (arcptr)].pred
 225                    && arcptr->pred_next == 0)
 226             {
 227               /* Instrument the target block.  */
 228               output_arc_profiler (total_num_arcs_instrumented
 229                                    + num_instr_arcs++,
 230                                    PREV_INSN (bb_graph[ARC_TARGET (arcptr)].first_insn));
 231             }
 232           else if (arcptr->fall_through)
 233             {
 234               /* This is a fall-through; put the instrumentation code after
 235                  the branch that ends this block.  */
 236
 237               for (backptr = bb_graph[i].succ; backptr;
 238                    backptr = backptr->succ_next)
 239                 if (backptr != arcptr)
 240                   break;
 241
 242               output_arc_profiler (total_num_arcs_instrumented
 243                                    + num_instr_arcs++,
 244                                    backptr->branch_insn);
 245             }
 246           else
 247             {
 248               /* Must emit a new basic block to hold the arc counting code.  */
 249               enum rtx_code code = GET_CODE (PATTERN (arcptr->branch_insn));
 250
 251               if (code == SET)
 252                 {
 253                   /* Create the new basic block right after the branch.
 254                      Invert the branch so that it jumps past the end of the new
 255                      block.  The new block will consist of the instrumentation
 256                      code, and a jump to the target of this arc.  */
 257                   int this_is_simplejump = simplejump_p (arcptr->branch_insn);
 258                   rtx new_label = gen_label_rtx ();
 259                   rtx old_label, set_src;
 260                   rtx after = arcptr->branch_insn;
 261
 262                   /* Simplejumps can't reach here.  */
 263                   if (this_is_simplejump)
 264                     abort ();
 265
 266                   /* We can't use JUMP_LABEL, because it won't be set if we
 267                      are compiling without optimization.  */
 268
 269                   set_src = SET_SRC (single_set (arcptr->branch_insn));
 270                   if (GET_CODE (set_src) == LABEL_REF)
 271                     old_label = set_src;
 272                   else if (GET_CODE (set_src) != IF_THEN_ELSE)
 273                     abort ();
 274                   else if (XEXP (set_src, 1) == pc_rtx)
 275                     old_label = XEXP (XEXP (set_src, 2), 0);
 276                   else
 277                     old_label = XEXP (XEXP (set_src, 1), 0);
 278
 279                   /* Set the JUMP_LABEL so that redirect_jump will work.  */
 280                   JUMP_LABEL (arcptr->branch_insn) = old_label;
 281
 282                   /* Add a use for OLD_LABEL that will be needed when we emit
 283                      the JUMP_INSN below.  If we don't do this here,
 284                      `invert_jump' might delete it for us.  We must add two
 285                      when not optimizing, because the NUSES is zero now,
 286                      but must be at least two to prevent the label from being
 287                      deleted.  */
 288                   LABEL_NUSES (old_label) += 2;
 289
 290                   /* Emit the insns for the new block in reverse order,
 291                      since that is most convenient.  */
 292
 293                   if (this_is_simplejump)
 294                     {
 295                       after = NEXT_INSN (arcptr->branch_insn);
 296                       if (! redirect_jump (arcptr->branch_insn, new_label))
 297                         /* Don't know what to do if this branch won't
 298                            redirect.  */
 299                         abort ();
 300                     }
 301                   else
 302                     {
 303                       if (! invert_jump (arcptr->branch_insn, new_label))
 304                         /* Don't know what to do if this branch won't invert.  */
 305                         abort ();
 306
 307                       emit_label_after (new_label, after);
 308                       LABEL_NUSES (new_label)++;
 309                     }
 310                   emit_barrier_after (after);
 311                   emit_jump_insn_after (gen_jump (old_label), after);
 312                   JUMP_LABEL (NEXT_INSN (after)) = old_label;
 313
 314                   /* Instrument the source arc.  */
 315                   output_arc_profiler (total_num_arcs_instrumented
 316                                        + num_instr_arcs++,
 317                                        after);
 318                   if (this_is_simplejump)
 319                     {
 320                       emit_label_after (new_label, after);
 321                       LABEL_NUSES (new_label)++;
 322                     }
 323                 }
 324               else if (code == ADDR_VEC || code == ADDR_DIFF_VEC)
 325                 {
 326                   /* A table jump.  Create a new basic block immediately
 327                      after the table, by emitting a barrier, a label, a
 328                      counting note, and a jump to the old label.  Put the
 329                      new label in the table.  */
 330
 331                   rtx new_label = gen_label_rtx ();
 332                   rtx old_lref, new_lref;
 333                   int index;
 334
 335                   /* Must determine the old_label reference, do this
 336                      by counting the arcs after this one, which will
 337                      give the index of our label in the table.  */
 338
 339                   index = 0;
 340                   for (backptr = arcptr->succ_next; backptr;
 341                        backptr = backptr->succ_next)
 342                     index++;
 343
 344                   old_lref = XVECEXP (PATTERN (arcptr->branch_insn),
 345                                       (code == ADDR_DIFF_VEC), index);
 346
 347                   /* Emit the insns for the new block in reverse order,
 348                      since that is most convenient.  */
 349                   emit_jump_insn_after (gen_jump (XEXP (old_lref, 0)),
 350                                         arcptr->branch_insn);
 351                   JUMP_LABEL (NEXT_INSN (arcptr->branch_insn))
 352                     = XEXP (old_lref, 0);
 353
 354                   /* Instrument the source arc.  */
 355                   output_arc_profiler (total_num_arcs_instrumented
 356                                        + num_instr_arcs++,
 357                                        arcptr->branch_insn);
 358
 359                   emit_label_after (new_label, arcptr->branch_insn);
 360                   LABEL_NUSES (NEXT_INSN (arcptr->branch_insn))++;
 361                   emit_barrier_after (arcptr->branch_insn);
 362
 363                   /* Fix up the table jump.  */
 364                   new_lref = gen_rtx (LABEL_REF, Pmode, new_label);
 365                   XVECEXP (PATTERN (arcptr->branch_insn),
 366                            (code == ADDR_DIFF_VEC), index) = new_lref;
 367                 }
 368               else
 369                 abort ();
 370
 371               num_arcs += 1;
 372               if (dump_file)
 373                 fprintf (dump_file,
 374                          "Arc %d to %d needed new basic block\n", i,
 375                          ARC_TARGET (arcptr));
 376             }
 377         }
 378
 379   total_num_arcs_instrumented += num_instr_arcs;
 380   count_instrumented_arcs = total_num_arcs_instrumented;
 381
 382   total_num_blocks_created += num_arcs;
 383   if (dump_file)
 384     {
 385       fprintf (dump_file, "%d arcs instrumented\n", num_instr_arcs);
 386       fprintf (dump_file, "%d extra basic blocks created\n", num_arcs);
 387     }
 388 }
 389
 390 /* Output STRING to bb_file, surrounded by DELIMITER.  */
 391
 392 static void
 393 output_gcov_string (string, delimiter)
 394      char *string;
 395      long delimiter;
 396 {
 397   long temp;
 398
 399   /* Write a delimiter to indicate that a file name follows.  */
 400   __write_long (delimiter, bb_file, 4);
 401
 402   /* Write the string.  */
 403   temp = strlen (string) + 1;
 404   fwrite (string, temp, 1, bb_file);
 405
 406   /* Append a few zeros, to align the output to a 4 byte boundary.  */
 407   temp = temp & 0x3;
 408   if (temp)
 409     {
 410       char c[4];
 411
 412       c[0] = c[1] = c[2] = c[3] = 0;
 413       fwrite (c, sizeof (char), 4 - temp, bb_file);
 414     }
 415
 416   /* Store another delimiter in the .bb file, just to make it easy to find the
 417      end of the file name.  */
 418   __write_long (delimiter, bb_file, 4);
 419 }
 420 \f
 421 /* Instrument and/or analyze program behavior based on program flow graph.
 422    In either case, this function builds a flow graph for the function being
 423    compiled.  The flow graph is stored in BB_GRAPH.
 424
 425    When FLAG_PROFILE_ARCS is nonzero, this function instruments the arcs in
 426    the flow graph that are needed to reconstruct the dynamic behavior of the
 427    flow graph.
 428
 429    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxilliary
 430    information from a data file containing arc count information from previous
 431    executions of the function being compiled.  In this case, the flow graph is
 432    annotated with actual execution counts, which are later propagated into the
 433    rtl for optimization purposes.
 434
 435    Main entry point of this file.  */
 436
 437 void
 438 branch_prob (f, dump_file)
 439      rtx f;
 440      FILE *dump_file;
 441 {
 442   int i, num_blocks;
 443   int dest;
 444   rtx insn;
 445   struct adj_list *arcptr;
 446   int num_arcs, changes, passes;
 447   int total, prob;
 448   int hist_br_prob[20], num_never_executed, num_branches;
 449   /* Set to non-zero if we got bad count information.  */
 450   int bad_counts = 0;
 451
 452   /* start of a function.  */
 453   if (flag_test_coverage)
 454     output_gcov_string (current_function_name, (long) -2);
 455
 456   /* Execute this only if doing arc profiling or branch probabilities.  */
 457   if (! profile_arc_flag && ! flag_branch_probabilities
 458       && ! flag_test_coverage)
 459     abort ();
 460
 461   total_num_times_called++;
 462
 463   /* Create an array label_to_bb of ints of size max_label_num.  */
 464   label_to_bb_size = max_label_num ();
 465   label_to_bb = (int *) oballoc (label_to_bb_size * sizeof (int));
 466   bzero ((char *) label_to_bb, label_to_bb_size * sizeof (int));
 467
 468   /* Scan the insns in the function, count the number of basic blocks
 469      present.  When a code label is passed, set label_to_bb[label] = bb
 470      number.  */
 471
 472   /* The first block found will be block 1, so that function entry can be
 473      block 0.  */
 474
 475   {
 476     register RTX_CODE prev_code = JUMP_INSN;
 477     register RTX_CODE code;
 478     register rtx insn;
 479     register int i;
 480     int block_separator_emitted = 0;
 481
 482     ignore_next_note = 0;
 483
 484     for (insn = NEXT_INSN (f), i = 0; insn; insn = NEXT_INSN (insn))
 485       {
 486         code = GET_CODE (insn);
 487
 488         if (code == BARRIER)
 489           ;
 490         else if (code == CODE_LABEL)
 491           /* This label is part of the next block, but we can't increment
 492              block number yet since there might be multiple labels.  */
 493           label_to_bb[CODE_LABEL_NUMBER (insn)] = i + 1;
 494         /* We make NOTE_INSN_SETJMP notes into a block of their own, so that
 495            they can be the target of the fake arc for the setjmp call.
 496            This avoids creating cycles of fake arcs, which would happen if
 497            the block after the setjmp call contained a call insn.  */
 498         else if ((prev_code == JUMP_INSN || prev_code == CALL_INSN
 499                   || prev_code == CODE_LABEL || prev_code == BARRIER)
 500                  && (GET_RTX_CLASS (code) == 'i'
 501                      || (code == NOTE
 502                          && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)))
 503           {
 504             i += 1;
 505
 506             /* Emit the block separator if it hasn't already been emitted.  */
 507             if (flag_test_coverage && ! block_separator_emitted)
 508               {
 509                 /* Output a zero to the .bb file to indicate that a new
 510                    block list is starting.  */
 511                 __write_long (0, bb_file, 4);
 512               }
 513             block_separator_emitted = 0;
 514           }
 515         /* If flag_test_coverage is true, then we must add an entry to the
 516            .bb file for every note.  */
 517         else if (code == NOTE && flag_test_coverage)
 518           {
 519             /* Must ignore the line number notes that immediately follow the
 520                end of an inline function to avoid counting it twice.  There
 521                is a note before the call, and one after the call.  */
 522             if (NOTE_LINE_NUMBER (insn) == NOTE_REPEATED_LINE_NUMBER)
 523               ignore_next_note = 1;
 524             else if (NOTE_LINE_NUMBER (insn) > 0)
 525               {
 526                 if (ignore_next_note)
 527                   ignore_next_note = 0;
 528                 else
 529                   {
 530                     /* Emit a block separator here to ensure that a NOTE
 531                        immediately following a JUMP_INSN or CALL_INSN will end
 532                        up in the right basic block list.  */
 533                     if ((prev_code == JUMP_INSN || prev_code == CALL_INSN
 534                          || prev_code == CODE_LABEL || prev_code == BARRIER)
 535                         && ! block_separator_emitted)
 536                       {
 537                         /* Output a zero to the .bb file to indicate that
 538                            a new block list is starting.  */
 539                         __write_long (0, bb_file, 4);
 540
 541                         block_separator_emitted = 1;
 542                       }
 543
 544                     /* If this is a new source file, then output the file's
 545                        name to the .bb file.  */
 546                     if (! last_bb_file_name
 547                         || strcmp (NOTE_SOURCE_FILE (insn),
 548                                    last_bb_file_name))
 549                       {
 550                         if (last_bb_file_name)
 551                           free (last_bb_file_name);
 552                         last_bb_file_name
 553                           = xmalloc (strlen (NOTE_SOURCE_FILE (insn)) + 1);
 554                         strcpy (last_bb_file_name, NOTE_SOURCE_FILE (insn));
 555                         output_gcov_string (NOTE_SOURCE_FILE (insn), (long)-1);
 556                       }
 557
 558                     /* Output the line number to the .bb file.  Must be done
 559                        after the output_bb_profile_data() call, and after the
 560                        file name is written, to ensure that it is correctly
 561                        handled by gcov.  */
 562                     __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
 563                   }
 564               }
 565           }
 566
 567         if (code != NOTE)
 568           prev_code = code;
 569         else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
 570           prev_code = CALL_INSN;
 571       }
 572
 573     /* Allocate last `normal' entry for bb_graph.  */
 574
 575     /* The last insn was a jump, call, or label.  In that case we have
 576        a block at the end of the function with no insns.  */
 577     if (prev_code == JUMP_INSN || prev_code == CALL_INSN
 578         || prev_code == CODE_LABEL || prev_code == BARRIER)
 579       {
 580         i++;
 581
 582         /* Emit the block separator if it hasn't already been emitted.  */
 583         if (flag_test_coverage && ! block_separator_emitted)
 584           {
 585             /* Output a zero to the .bb file to indicate that a new
 586                block list is starting.  */
 587             __write_long (0, bb_file, 4);
 588           }
 589       }
 590
 591     /* Create another block to stand for EXIT, and make all return insns, and
 592        the last basic block point here.  Add one more to account for block
 593        zero.  */
 594     num_blocks = i + 2;
 595   }
 596
 597   total_num_blocks += num_blocks;
 598   if (dump_file)
 599     fprintf (dump_file, "%d basic blocks\n", num_blocks);
 600
 601   /* If we are only doing test coverage here, then return now.  */
 602   if (! profile_arc_flag && ! flag_branch_probabilities)
 603     return;
 604
 605   /* Create and initialize the arrays that will hold bb_graph
 606      and execution count info.  */
 607
 608   bb_graph = (struct bb_info *) alloca (num_blocks * sizeof (struct bb_info));
 609   bzero ((char *) bb_graph, (sizeof (struct bb_info) * num_blocks));
 610
 611   {
 612     /* Scan the insns again:
 613        - at the entry to each basic block, increment the predecessor count
 614        (and successor of previous block) if it is a fall through entry,
 615        create adj_list entries for this and the previous block
 616        - at each jump insn, increment predecessor/successor counts for
 617        target/source basic blocks, add this insn to pred/succ lists.
 618
 619        This also cannot be broken out as a separate subroutine
 620        because it uses `alloca'.  */
 621
 622     register RTX_CODE prev_code = JUMP_INSN;
 623     register RTX_CODE code;
 624     register rtx insn;
 625     register int i;
 626     int fall_through = 0;
 627     struct adj_list *arcptr;
 628     int dest;
 629
 630     /* Block 0 always falls through to block 1.  */
 631     num_arcs = 0;
 632     arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
 633     init_arc (arcptr, 0, 1, 0);
 634     arcptr->fall_through = 1;
 635     num_arcs++;
 636
 637     /* Add a fake fall through arc from the last block to block 0, to make the
 638        graph complete.  */
 639     arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
 640     init_arc (arcptr, num_blocks - 1, 0, 0);
 641     arcptr->fake = 1;
 642     num_arcs++;
 643
 644     /* Exit must be one node of the graph, and all exits from the function
 645        must point there.  When see a return branch, must point the arc to the
 646        exit node.  */
 647
 648     /* Must start scan with second insn in function as above.  */
 649     for (insn = NEXT_INSN (f), i = 0; insn; insn = NEXT_INSN (insn))
 650       {
 651         code = GET_CODE (insn);
 652
 653         if (code == BARRIER)
 654           fall_through = 0;
 655         else if (code == CODE_LABEL)
 656           ;
 657         /* We make NOTE_INSN_SETJMP notes into a block of their own, so that
 658            they can be the target of the fake arc for the setjmp call.
 659            This avoids creating cycles of fake arcs, which would happen if
 660            the block after the setjmp call ended with a call.  */
 661         else if ((prev_code == JUMP_INSN || prev_code == CALL_INSN
 662                   || prev_code == CODE_LABEL || prev_code == BARRIER)
 663                  && (GET_RTX_CLASS (code) == 'i'
 664                      || (code == NOTE
 665                          && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)))
 666           {
 667             /* This is the first insn of the block.  */
 668             i += 1;
 669             if (fall_through)
 670               {
 671                 arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
 672                 init_arc (arcptr, i - 1, i, 0);
 673                 arcptr->fall_through = 1;
 674
 675                 num_arcs++;
 676               }
 677             fall_through = 1;
 678             bb_graph[i].first_insn = insn;
 679           }
 680         else if (code == NOTE)
 681           ;
 682
 683         if (code == CALL_INSN)
 684           {
 685             /* In the normal case, the call returns, and this is just like
 686                a branch fall through.  */
 687             fall_through = 1;
 688
 689             /* Setjmp may return more times than called, so to make the graph
 690                solvable, add a fake arc from the function entrance to the
 691                next block.
 692
 693                All other functions may return fewer times than called (if
 694                a descendent call longjmp or exit), so to make the graph
 695                solvable, add a fake arc to the function exit from the
 696                current block.
 697
 698                Distinguish the cases by checking for a SETJUMP note.
 699                A call_insn can be the last ins of a function, so must check
 700                to see if next insn actually exists.  */
 701             arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
 702             if (NEXT_INSN (insn)
 703                 && GET_CODE (NEXT_INSN (insn)) == NOTE
 704                 && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
 705               init_arc (arcptr, 0, i+1, insn);
 706             else
 707               init_arc (arcptr, i, num_blocks-1, insn);
 708             arcptr->fake = 1;
 709             num_arcs++;
 710           }
 711         else if (code == JUMP_INSN)
 712           {
 713             rtx tem, pattern = PATTERN (insn);
 714             rtx tablejump = 0;
 715
 716             /* If running without optimization, then jump label won't be valid,
 717                so we must search for the destination label in that case.
 718                We have to handle tablejumps and returns specially anyways, so
 719                we don't check the JUMP_LABEL at all here.  */
 720
 721             if (GET_CODE (pattern) == PARALLEL)
 722               {
 723                 /* This assumes that PARALLEL jumps are tablejump entry
 724                    jumps.  */
 725                 /* Make an arc from this jump to the label of the
 726                    jump table.  This will instrument the number of
 727                    times the switch statement is executed.  */
 728                 if (GET_CODE (XVECEXP (pattern, 0, 1)) == USE)
 729                   {
 730                     tem = XEXP (XVECEXP (pattern, 0, 1), 0);
 731                     if (GET_CODE (tem) != LABEL_REF)
 732                       abort ();
 733                     dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (tem, 0))];
 734                   }
 735                 else if (GET_CODE (XVECEXP (pattern, 0, 0)) == SET
 736                          && SET_DEST (XVECEXP (pattern, 0, 0)) == pc_rtx)
 737                   {
 738                     tem = SET_SRC (XVECEXP (pattern, 0, 0));
 739                     if (GET_CODE (tem) == PLUS
 740                         && GET_CODE (XEXP (tem, 1)) == LABEL_REF)
 741                       {
 742                         tem = XEXP (tem, 1);
 743                         dest = label_to_bb [CODE_LABEL_NUMBER (XEXP (tem, 0))];
 744                       }
 745                   }
 746                 else
 747                   abort ();
 748               }
 749             else if (GET_CODE (pattern) == ADDR_VEC
 750                      || GET_CODE (pattern) == ADDR_DIFF_VEC)
 751               tablejump = pattern;
 752             else if (GET_CODE (pattern) == RETURN)
 753               dest = num_blocks - 1;
 754             else if ((tem = SET_SRC (pattern))
 755                      && GET_CODE (tem) == LABEL_REF)
 756               dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (tem, 0))];
 757             else
 758               {
 759                 rtx label_ref;
 760
 761                 /* Must be an IF_THEN_ELSE branch.  */
 762                 if (GET_CODE (tem) != IF_THEN_ELSE)
 763                   abort ();
 764                 if (XEXP (tem, 1) != pc_rtx)
 765                   label_ref = XEXP (tem, 1);
 766                 else
 767                   label_ref = XEXP (tem, 2);
 768                 dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (label_ref, 0))];
 769               }
 770
 771             if (tablejump)
 772               {
 773                 int diff_vec_p = GET_CODE (tablejump) == ADDR_DIFF_VEC;
 774                 int len = XVECLEN (tablejump, diff_vec_p);
 775                 int k;
 776
 777                 for (k = 0; k < len; k++)
 778                   {
 779                     rtx tem = XEXP (XVECEXP (tablejump, diff_vec_p, k), 0);
 780                     dest = label_to_bb[CODE_LABEL_NUMBER (tem)];
 781
 782                     arcptr = (struct adj_list *) alloca (sizeof(struct adj_list));
 783                     init_arc (arcptr, i, dest, insn);
 784
 785                     num_arcs++;
 786                   }
 787               }
 788             else
 789               {
 790                 arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
 791                 init_arc (arcptr, i, dest, insn);
 792
 793                 num_arcs++;
 794               }
 795
 796             /* Determine whether or not this jump will fall through.
 797                Unconditional jumps and returns are not always followed by
 798                barriers.  */
 799             pattern = PATTERN (insn);
 800             if (GET_CODE (pattern) == PARALLEL
 801                 || GET_CODE (pattern) == RETURN)
 802               fall_through = 0;
 803             else if (GET_CODE (pattern) == ADDR_VEC
 804                      || GET_CODE (pattern) == ADDR_DIFF_VEC)
 805               /* These aren't actually jump insns, but they never fall
 806                  through, so...  */
 807               fall_through = 0;
 808             else
 809               {
 810                 if (GET_CODE (pattern) != SET || SET_DEST (pattern) != pc_rtx)
 811                   abort ();
 812                 if (GET_CODE (SET_SRC (pattern)) != IF_THEN_ELSE)
 813                   fall_through = 0;
 814               }
 815           }
 816
 817         if (code != NOTE)
 818           prev_code = code;
 819         else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
 820           prev_code = CALL_INSN;
 821       }
 822
 823     /* If the code at the end of the function would give a new block, then
 824        do the following.  */
 825
 826     if (prev_code == JUMP_INSN || prev_code == CALL_INSN
 827         || prev_code == CODE_LABEL || prev_code == BARRIER)
 828       {
 829         if (fall_through)
 830           {
 831             arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
 832             init_arc (arcptr, i, i + 1, 0);
 833             arcptr->fall_through = 1;
 834
 835             num_arcs++;
 836           }
 837
 838         /* This may not be a real insn, but that should not cause a problem.  */
 839         bb_graph[i+1].first_insn = get_last_insn ();
 840       }
 841
 842     /* There is always a fake arc from the last block of the function
 843        to the function exit block.  */
 844     arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
 845     init_arc (arcptr, num_blocks-2, num_blocks-1, 0);
 846     arcptr->fake = 1;
 847     num_arcs++;
 848   }
 849
 850   total_num_arcs += num_arcs;
 851   if (dump_file)
 852     fprintf (dump_file, "%d arcs\n", num_arcs);
 853
 854   /* Create spanning tree from basic block graph, mark each arc that is
 855      on the spanning tree.  */
 856
 857   /* To reduce the instrumentation cost, make two passes over the tree.
 858      First, put as many must-split (crowded and fake) arcs on the tree as
 859      possible, then on the second pass fill in the rest of the tree.
 860      Note that the spanning tree is considered undirected, so that as many
 861      must-split arcs as possible can be put on it.
 862
 863      Fallthough arcs which are crowded should not be chosen on the first
 864      pass, since they do not require creating a new basic block.  These
 865      arcs will have fall_through set.  */
 866
 867   find_spanning_tree (num_blocks);
 868
 869   /* Create a .bbg file from which gcov can reconstruct the basic block
 870      graph.  First output the number of basic blocks, and then for every
 871      arc output the source and target basic block numbers.
 872      NOTE: The format of this file must be compatible with gcov.  */
 873
 874   if (flag_test_coverage)
 875     {
 876       int flag_bits;
 877
 878       __write_long (num_blocks, bbg_file, 4);
 879       __write_long (num_arcs, bbg_file, 4);
 880
 881       for (i = 0; i < num_blocks; i++)
 882         {
 883           long count = 0;
 884           for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
 885             count++;
 886           __write_long (count, bbg_file, 4);
 887
 888           for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
 889             {
 890               flag_bits = 0;
 891               if (arcptr->on_tree)
 892                 flag_bits |= 0x1;
 893               if (arcptr->fake)
 894                 flag_bits |= 0x2;
 895               if (arcptr->fall_through)
 896                 flag_bits |= 0x4;
 897
 898               __write_long (ARC_TARGET (arcptr), bbg_file, 4);
 899               __write_long (flag_bits, bbg_file, 4);
 900             }
 901         }
 902
 903       /* Emit a -1 to separate the list of all arcs from the list of
 904          loop back edges that follows.  */
 905       __write_long (-1, bbg_file, 4);
 906     }
 907
 908   /* For each arc not on the spanning tree, add counting code as rtl.  */
 909
 910   if (profile_arc_flag)
 911     instrument_arcs (f, num_blocks, dump_file);
 912
 913   /* Execute the rest only if doing branch probabilities.  */
 914   if (! flag_branch_probabilities)
 915     return;
 916
 917   /* For each arc not on the spanning tree, set its execution count from
 918      the .da file.  */
 919
 920   /* The first count in the .da file is the number of times that the function
 921      was entered.  This is the exec_count for block zero.  */
 922
 923   num_arcs = 0;
 924   for (i = 0; i < num_blocks; i++)
 925     for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
 926       if (! arcptr->on_tree)
 927         {
 928           num_arcs++;
 929           if (da_file)
 930             {
 931               long value;
 932               __read_long (&value, da_file, 8);
 933               ARC_COUNT (arcptr) = value;
 934             }
 935           else
 936             ARC_COUNT (arcptr) = 0;
 937           arcptr->count_valid = 1;
 938           bb_graph[i].succ_count--;
 939           bb_graph[ARC_TARGET (arcptr)].pred_count--;
 940         }
 941
 942   if (dump_file)
 943     fprintf (dump_file, "%d arc counts read\n", num_arcs);
 944
 945   /* For every block in the file,
 946      - if every exit/entrance arc has a known count, then set the block count
 947      - if the block count is known, and every exit/entrance arc but one has
 948        a known execution count, then set the count of the remaining arc
 949
 950      As arc counts are set, decrement the succ/pred count, but don't delete
 951      the arc, that way we can easily tell when all arcs are known, or only
 952      one arc is unknown.  */
 953
 954   /* The order that the basic blocks are iterated through is important.
 955      Since the code that finds spanning trees starts with block 0, low numbered
 956      arcs are put on the spanning tree in preference to high numbered arcs.
 957      Hence, most instrumented arcs are at the end.  Graph solving works much
 958      faster if we propagate numbers from the end to the start.
 959
 960      This takes an average of slightly more than 3 passes.  */
 961
 962   changes = 1;
 963   passes = 0;
 964   while (changes)
 965     {
 966       passes++;
 967       changes = 0;
 968
 969       for (i = num_blocks - 1; i >= 0; i--)
 970         {
 971           struct bb_info *binfo = &bb_graph[i];
 972           if (! binfo->count_valid)
 973             {
 974               if (binfo->succ_count == 0)
 975                 {
 976                   total = 0;
 977                   for (arcptr = binfo->succ; arcptr;
 978                        arcptr = arcptr->succ_next)
 979                     total += ARC_COUNT (arcptr);
 980                   binfo->exec_count = total;
 981                   binfo->count_valid = 1;
 982                   changes = 1;
 983                 }
 984               else if (binfo->pred_count == 0)
 985                 {
 986                   total = 0;
 987                   for (arcptr = binfo->pred; arcptr;
 988                        arcptr = arcptr->pred_next)
 989                     total += ARC_COUNT (arcptr);
 990                   binfo->exec_count = total;
 991                   binfo->count_valid = 1;
 992                   changes = 1;
 993                 }
 994             }
 995           if (binfo->count_valid)
 996             {
 997               if (binfo->succ_count == 1)
 998                 {
 999                   total = 0;
1000                   /* One of the counts will be invalid, but it is zero,
1001                      so adding it in also doesn't hurt.  */
1002                   for (arcptr = binfo->succ; arcptr;
1003                        arcptr = arcptr->succ_next)
1004                     total += ARC_COUNT (arcptr);
1005                   /* Calculate count for remaining arc by conservation.  */
1006                   total = binfo->exec_count - total;
1007                   /* Search for the invalid arc, and set its count.  */
1008                   for (arcptr = binfo->succ; arcptr;
1009                        arcptr = arcptr->succ_next)
1010                     if (! arcptr->count_valid)
1011                       break;
1012                   if (! arcptr)
1013                     abort ();
1014                   arcptr->count_valid = 1;
1015                   ARC_COUNT (arcptr) = total;
1016                   binfo->succ_count--;
1017
1018                   bb_graph[ARC_TARGET (arcptr)].pred_count--;
1019                   changes = 1;
1020                 }
1021               if (binfo->pred_count == 1)
1022                 {
1023                   total = 0;
1024                   /* One of the counts will be invalid, but it is zero,
1025                      so adding it in also doesn't hurt.  */
1026                   for (arcptr = binfo->pred; arcptr;
1027                        arcptr = arcptr->pred_next)
1028                     total += ARC_COUNT (arcptr);
1029                   /* Calculate count for remaining arc by conservation.  */
1030                   total = binfo->exec_count - total;
1031                   /* Search for the invalid arc, and set its count.  */
1032                   for (arcptr = binfo->pred; arcptr;
1033                        arcptr = arcptr->pred_next)
1034                     if (! arcptr->count_valid)
1035                       break;
1036                   if (! arcptr)
1037                     abort ();
1038                   arcptr->count_valid = 1;
1039                   ARC_COUNT (arcptr) = total;
1040                   binfo->pred_count--;
1041
1042                   bb_graph[ARC_SOURCE (arcptr)].succ_count--;
1043                   changes = 1;
1044                 }
1045             }
1046         }
1047     }
1048
1049   total_num_passes += passes;
1050   if (dump_file)
1051     fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
1052
1053   /* If the graph has been correctly solved, every block will have a
1054      succ and pred count of zero.  */
1055   for (i = 0; i < num_blocks; i++)
1056     {
1057       struct bb_info *binfo = &bb_graph[i];
1058       if (binfo->succ_count || binfo->pred_count)
1059         abort ();
1060     }
1061
1062   /* For every arc, calculate its branch probability and add a reg_note
1063      to the branch insn to indicate this.  */
1064
1065   for (i = 0; i < 20; i++)
1066     hist_br_prob[i] = 0;
1067   num_never_executed = 0;
1068   num_branches = 0;
1069
1070   for (i = 0; i < num_blocks; i++)
1071     {
1072       struct bb_info *binfo = &bb_graph[i];
1073
1074       total = binfo->exec_count;
1075       for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next)
1076         {
1077           if (arcptr->branch_insn)
1078             {
1079               /* This calculates the branch probability as an integer between
1080                  0 and REG_BR_PROB_BASE, properly rounded to the nearest
1081                  integer.  Perform the arithmetic in double to avoid
1082                  overflowing the range of ints.  */
1083
1084               if (total == 0)
1085                 prob = -1;
1086               else
1087                 {
1088                   rtx pat = PATTERN (arcptr->branch_insn);
1089
1090                   prob = (((double)ARC_COUNT (arcptr) * REG_BR_PROB_BASE)
1091                           + (total >> 1)) / total;
1092                   if (prob < 0 || prob > REG_BR_PROB_BASE)
1093                     {
1094                       if (dump_file)
1095                         fprintf (dump_file, "bad count: prob for %d-%d thought to be %d (forcibly normalized)\n",
1096                                  ARC_SOURCE (arcptr), ARC_TARGET (arcptr),
1097                                  prob);
1098
1099                       bad_counts = 1;
1100                       prob = REG_BR_PROB_BASE / 2;
1101                     }
1102
1103                   /* Match up probability with JUMP pattern.  */
1104
1105                   if (GET_CODE (pat) == SET
1106                       && GET_CODE (SET_SRC (pat)) == IF_THEN_ELSE)
1107                     {
1108                       if (ARC_TARGET (arcptr) == ARC_SOURCE (arcptr) + 1)
1109                         {
1110                           /* A fall through arc should never have a
1111                              branch insn.  */
1112                           abort ();
1113                         }
1114                       else
1115                         {
1116                           /* This is the arc for the taken branch.  */
1117                           if (GET_CODE (XEXP (SET_SRC (pat), 2)) != PC)
1118                             prob = REG_BR_PROB_BASE - prob;
1119                         }
1120                     }
1121                 }
1122
1123               if (prob == -1)
1124                 num_never_executed++;
1125               else
1126                 {
1127                   int index = prob * 20 / REG_BR_PROB_BASE;
1128                   if (index == 20)
1129                     index = 19;
1130                   hist_br_prob[index]++;
1131                 }
1132               num_branches++;
1133
1134               REG_NOTES (arcptr->branch_insn)
1135                 = gen_rtx (EXPR_LIST, REG_BR_PROB, GEN_INT (prob),
1136                            REG_NOTES (arcptr->branch_insn));
1137             }
1138         }
1139
1140       /* Add a REG_EXEC_COUNT note to the first instruction of this block.  */
1141       if (! binfo->first_insn
1142           || GET_RTX_CLASS (GET_CODE (binfo->first_insn)) != 'i')
1143         {
1144           /* Block 0 is a fake block representing function entry, and does
1145              not have a real first insn.  The second last block might not
1146              begin with a real insn.  */
1147           if (i == num_blocks - 1)
1148             return_label_execution_count = total;
1149           else if (i != 0 && i != num_blocks - 2)
1150             abort ();
1151         }
1152       else
1153         {
1154           REG_NOTES (binfo->first_insn)
1155             = gen_rtx (EXPR_LIST, REG_EXEC_COUNT, GEN_INT (total),
1156                        REG_NOTES (binfo->first_insn));
1157           if (i == num_blocks - 1)
1158             return_label_execution_count = total;
1159         }
1160     }
1161
1162   /* This should never happen.  */
1163   if (bad_counts)
1164     warning ("Arc profiling: some arc counts were bad.");
1165
1166   if (dump_file)
1167     {
1168       fprintf (dump_file, "%d branches\n", num_branches);
1169       fprintf (dump_file, "%d branches never executed\n",
1170                num_never_executed);
1171       if (num_branches)
1172         for (i = 0; i < 10; i++)
1173           fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1174                    (hist_br_prob[i]+hist_br_prob[19-i])*100/num_branches,
1175                    5*i, 5*i+5);
1176
1177       total_num_branches += num_branches;
1178       total_num_never_executed += num_never_executed;
1179       for (i = 0; i < 20; i++)
1180         total_hist_br_prob[i] += hist_br_prob[i];
1181     }
1182
1183 }
1184 \f
1185 /* Initialize a new arc.
1186    ARCPTR is the empty adj_list this function fills in.
1187    SOURCE is the block number of the source block.
1188    TARGET is the block number of the target block.
1189    INSN is the insn which transfers control from SOURCE to TARGET,
1190    or zero if the transfer is implicit.  */
1191
1192 static void
1193 init_arc (arcptr, source, target, insn)
1194      struct adj_list *arcptr;
1195      int source, target;
1196      rtx insn;
1197 {
1198   ARC_TARGET (arcptr) = target;
1199   ARC_SOURCE (arcptr) = source;
1200
1201   ARC_COUNT (arcptr) = 0;
1202   arcptr->count_valid = 0;
1203   arcptr->on_tree = 0;
1204   arcptr->fake = 0;
1205   arcptr->fall_through = 0;
1206   arcptr->branch_insn = insn;
1207
1208   arcptr->succ_next = bb_graph[source].succ;
1209   bb_graph[source].succ = arcptr;
1210   bb_graph[source].succ_count++;
1211
1212   arcptr->pred_next = bb_graph[target].pred;
1213   bb_graph[target].pred = arcptr;
1214   bb_graph[target].pred_count++;
1215 }
1216
1217 /* This function searches all of the arcs in the program flow graph, and puts
1218    as many bad arcs as possible onto the spanning tree.  Bad arcs include
1219    fake arcs (needed for setjmp(), longjmp(), exit()) which MUST be on the
1220    spanning tree as they can't be instrumented.  Also, arcs which must be
1221    split when instrumented should be part of the spanning tree if possible.  */
1222
1223 static void
1224 find_spanning_tree (num_blocks)
1225      int num_blocks;
1226 {
1227   int i;
1228   struct adj_list *arcptr;
1229   struct bb_info *binfo = &bb_graph[0];
1230
1231   /* Fake arcs must be part of the spanning tree, and are always safe to put
1232      on the spanning tree.  Fake arcs will either be a successor of node 0,
1233      a predecessor of the last node, or from the last node to node 0.  */
1234
1235   for (arcptr = bb_graph[0].succ; arcptr; arcptr = arcptr->succ_next)
1236     if (arcptr->fake)
1237       {
1238         /* Adding this arc should never cause a cycle.  This is a fatal
1239            error if it would.  */
1240         if (bb_graph[ARC_TARGET (arcptr)].on_tree && binfo->on_tree)
1241           abort();
1242         else
1243           {
1244             arcptr->on_tree = 1;
1245             bb_graph[ARC_TARGET (arcptr)].on_tree = 1;
1246             binfo->on_tree = 1;
1247           }
1248       }
1249
1250   binfo = &bb_graph[num_blocks-1];
1251   for (arcptr = binfo->pred; arcptr; arcptr = arcptr->pred_next)
1252     if (arcptr->fake)
1253       {
1254         /* Adding this arc should never cause a cycle.  This is a fatal
1255            error if it would.  */
1256         if (bb_graph[ARC_SOURCE (arcptr)].on_tree && binfo->on_tree)
1257           abort();
1258         else
1259           {
1260             arcptr->on_tree = 1;
1261             bb_graph[ARC_SOURCE (arcptr)].on_tree = 1;
1262             binfo->on_tree = 1;
1263           }
1264       }
1265   /* The only entrace to node zero is a fake arc.  */
1266   bb_graph[0].pred->on_tree = 1;
1267
1268   /* Arcs which are crowded at both the source and target should be put on
1269      the spanning tree if possible, except for fall_throuch arcs which never
1270      require adding a new block even if crowded, add arcs with the same source
1271      and dest which must always be instrumented.  */
1272   for (i = 0; i < num_blocks; i++)
1273     {
1274       binfo = &bb_graph[i];
1275
1276       for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next)
1277         if (! ((binfo->succ == arcptr && arcptr->succ_next == 0)
1278                || (bb_graph[ARC_TARGET (arcptr)].pred
1279                    && arcptr->pred_next == 0))
1280             && ! arcptr->fall_through
1281             && ARC_TARGET (arcptr) != i)
1282           {
1283             /* This is a crowded arc at both source and target.  Try to put
1284                in on the spanning tree.  Can do this if either the source or
1285                target block is not yet on the tree.  */
1286             if (! bb_graph[ARC_TARGET (arcptr)].on_tree || ! binfo->on_tree)
1287               {
1288                 arcptr->on_tree = 1;
1289                 bb_graph[ARC_TARGET (arcptr)].on_tree = 1;
1290                 binfo->on_tree = 1;
1291               }
1292           }
1293     }
1294
1295   /* Clear all of the basic block on_tree bits, so that we can use them to
1296      create the spanning tree.  */
1297   for (i = 0; i < num_blocks; i++)
1298     bb_graph[i].on_tree = 0;
1299
1300   /* Now fill in the spanning tree until every basic block is on it.
1301      Don't put the 0 to 1 fall through arc on the tree, since it is
1302      always cheap to instrument, so start filling the tree from node 1.  */
1303
1304   for (i = 1; i < num_blocks; i++)
1305     for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
1306       if (! arcptr->on_tree
1307           && ! bb_graph[ARC_TARGET (arcptr)].on_tree)
1308         {
1309           fill_spanning_tree (i);
1310           break;
1311         }
1312 }
1313
1314 /* Add arcs reached from BLOCK to the spanning tree if they are needed and
1315    not already there.  */
1316
1317 static void
1318 fill_spanning_tree (block)
1319      int block;
1320 {
1321   struct adj_list *arcptr;
1322
1323   expand_spanning_tree (block);
1324
1325   for (arcptr = bb_graph[block].succ; arcptr; arcptr = arcptr->succ_next)
1326     if (! arcptr->on_tree
1327         && ! bb_graph[ARC_TARGET (arcptr)].on_tree)
1328       {
1329         arcptr->on_tree = 1;
1330         fill_spanning_tree (ARC_TARGET (arcptr));
1331       }
1332 }
1333
1334 /* When first visit a block, must add all blocks that are already connected
1335    to this block via tree arcs to the spanning tree.  */
1336
1337 static void
1338 expand_spanning_tree (block)
1339      int block;
1340 {
1341   struct adj_list *arcptr;
1342
1343   bb_graph[block].on_tree = 1;
1344
1345   for (arcptr = bb_graph[block].succ; arcptr; arcptr = arcptr->succ_next)
1346     if (arcptr->on_tree && ! bb_graph[ARC_TARGET (arcptr)].on_tree)
1347       expand_spanning_tree (ARC_TARGET (arcptr));
1348
1349   for (arcptr = bb_graph[block].pred;
1350        arcptr; arcptr = arcptr->pred_next)
1351     if (arcptr->on_tree && ! bb_graph[ARC_SOURCE (arcptr)].on_tree)
1352       expand_spanning_tree (ARC_SOURCE (arcptr));
1353 }
1354 \f
1355 /* Perform file-level initialization for branch-prob processing.  */
1356
1357 void
1358 init_branch_prob (filename)
1359      char *filename;
1360 {
1361   long len;
1362   int i;
1363
1364   if (flag_test_coverage)
1365     {
1366       /* Open an output file for the basic block/line number map.  */
1367       int len = strlen (filename);
1368       char *data_file = (char *) alloca (len + 4);
1369       strcpy (data_file, filename);
1370       strip_off_ending (data_file, len);
1371       strcat (data_file, ".bb");
1372       if ((bb_file = fopen (data_file, "w")) == 0)
1373         pfatal_with_name (data_file);
1374
1375       /* Open an output file for the program flow graph.  */
1376       len = strlen (filename);
1377       bbg_file_name = (char *) alloca (len + 5);
1378       strcpy (bbg_file_name, filename);
1379       strip_off_ending (bbg_file_name, len);
1380       strcat (bbg_file_name, ".bbg");
1381       if ((bbg_file = fopen (bbg_file_name, "w")) == 0)
1382         pfatal_with_name (bbg_file_name);
1383
1384       /* Initialize to zero, to ensure that the first file name will be
1385          written to the .bb file.  */
1386       last_bb_file_name = 0;
1387     }
1388
1389   if (flag_branch_probabilities)
1390     {
1391       len = strlen (filename);
1392       da_file_name = (char *) alloca (len + 4);
1393       strcpy (da_file_name, filename);
1394       strip_off_ending (da_file_name, len);
1395       strcat (da_file_name, ".da");
1396       if ((da_file = fopen (da_file_name, "r")) == 0)
1397         warning ("file %s not found, execution counts assumed to be zero.",
1398                  da_file_name);
1399
1400       /* The first word in the .da file gives the number of instrumented arcs,
1401          which is not needed for our purposes.  */
1402
1403       if (da_file)
1404         __read_long (&len, da_file, 8);
1405     }
1406
1407   if (profile_arc_flag)
1408     init_arc_profiler ();
1409
1410   total_num_blocks = 0;
1411   total_num_arcs = 0;
1412   total_num_arcs_instrumented = 0;
1413   total_num_blocks_created = 0;
1414   total_num_passes = 0;
1415   total_num_times_called = 0;
1416   total_num_branches = 0;
1417   total_num_never_executed = 0;
1418   for (i = 0; i < 20; i++)
1419     total_hist_br_prob[i] = 0;
1420 }
1421
1422 /* Performs file-level cleanup after branch-prob processing
1423    is completed.  */
1424
1425 void
1426 end_branch_prob (dump_file)
1427      FILE *dump_file;
1428 {
1429   if (flag_test_coverage)
1430     {
1431       fclose (bb_file);
1432       fclose (bbg_file);
1433     }
1434
1435   if (flag_branch_probabilities)
1436     {
1437       if (da_file)
1438         {
1439           long temp;
1440           /* This seems slightly dangerous, as it presumes the EOF
1441              flag will not be set until an attempt is made to read
1442              past the end of the file. */
1443           if (feof (da_file))
1444             warning (".da file contents exhausted too early\n");
1445           /* Should be at end of file now.  */
1446           if (__read_long (&temp, da_file, 8) == 0)
1447             warning (".da file contents not exhausted\n");
1448           fclose (da_file);
1449         }
1450     }
1451
1452   if (dump_file)
1453     {
1454       fprintf (dump_file, "\n");
1455       fprintf (dump_file, "Total number of blocks: %d\n", total_num_blocks);
1456       fprintf (dump_file, "Total number of arcs: %d\n", total_num_arcs);
1457       fprintf (dump_file, "Total number of instrumented arcs: %d\n",
1458                total_num_arcs_instrumented);
1459       fprintf (dump_file, "Total number of blocks created: %d\n",
1460                total_num_blocks_created);
1461       fprintf (dump_file, "Total number of graph solution passes: %d\n",
1462                total_num_passes);
1463       if (total_num_times_called != 0)
1464         fprintf (dump_file, "Average number of graph solution passes: %d\n",
1465                  (total_num_passes + (total_num_times_called  >> 1))
1466                  / total_num_times_called);
1467       fprintf (dump_file, "Total number of branches: %d\n", total_num_branches);
1468       fprintf (dump_file, "Total number of branches never executed: %d\n",
1469                total_num_never_executed);
1470       if (total_num_branches)
1471         {
1472           int i;
1473
1474           for (i = 0; i < 10; i++)
1475             fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
1476                      (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
1477                      / total_num_branches, 5*i, 5*i+5);
1478         }
1479     }
1480 }
1481 \f
1482 /* The label used by the arc profiling code.  */
1483
1484 static rtx profiler_label;
1485
1486 /* Initialize the profiler_label.  */
1487
1488 static void
1489 init_arc_profiler ()
1490 {
1491   /* Generate and save a copy of this so it can be shared.  */
1492   char *name = xmalloc (20);
1493   ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 2);
1494   profiler_label = gen_rtx (SYMBOL_REF, Pmode, name);
1495 }
1496
1497 /* Output instructions as RTL to increment the arc execution count.  */
1498
1499 static void
1500 output_arc_profiler (arcno, insert_after)
1501      int arcno;
1502      rtx insert_after;
1503 {
1504   rtx profiler_target_addr
1505     = (arcno
1506        ? gen_rtx (CONST, Pmode,
1507                   gen_rtx (PLUS, Pmode, profiler_label,
1508                            gen_rtx (CONST_INT, VOIDmode,
1509                                     LONG_TYPE_SIZE / BITS_PER_UNIT * arcno)))
1510        : profiler_label);
1511   enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0);
1512   rtx profiler_reg = gen_reg_rtx (mode);
1513   rtx address_reg = gen_reg_rtx (Pmode);
1514   rtx mem_ref, add_ref;
1515   rtx sequence;
1516
1517 #ifdef SMALL_REGISTER_CLASSES
1518   /* In this case, reload can use explicitly mentioned hard registers for
1519      reloads.  It is not safe to output profiling code between a call
1520      and the instruction that copies the result to a pseudo-reg.  This
1521      is because reload may allocate one of the profiling code pseudo-regs
1522      to the return value reg, thus clobbering the return value.  So we
1523      must check for calls here, and emit the profiling code after the
1524      instruction that uses the return value, if any.
1525
1526      ??? The code here performs the same tests that reload does so hopefully
1527      all the bases are covered.  */
1528
1529   if (SMALL_REGISTER_CLASSES
1530       && GET_CODE (insert_after) == CALL_INSN
1531       && (GET_CODE (PATTERN (insert_after)) == SET
1532           || (GET_CODE (PATTERN (insert_after)) == PARALLEL
1533               && GET_CODE (XVECEXP (PATTERN (insert_after), 0, 0)) == SET)))
1534     {
1535       rtx return_reg;
1536       rtx next_insert_after = next_nonnote_insn (insert_after);
1537
1538       /* The first insn after the call may be a stack pop, skip it.  */
1539       if (next_insert_after
1540           && GET_CODE (next_insert_after) == INSN
1541           && GET_CODE (PATTERN (next_insert_after)) == SET
1542           && SET_DEST (PATTERN (next_insert_after)) == stack_pointer_rtx)
1543         next_insert_after = next_nonnote_insn (next_insert_after);
1544
1545       if (next_insert_after
1546           && GET_CODE (next_insert_after) == INSN)
1547         {
1548           if (GET_CODE (PATTERN (insert_after)) == SET)
1549             return_reg = SET_DEST (PATTERN (insert_after));
1550           else
1551             return_reg = SET_DEST (XVECEXP (PATTERN (insert_after), 0, 0));
1552
1553           if (reg_referenced_p (return_reg, PATTERN (next_insert_after)))
1554             insert_after = next_insert_after;
1555         }
1556     }
1557 #endif
1558
1559   start_sequence ();
1560
1561   emit_move_insn (address_reg, profiler_target_addr);
1562   mem_ref = gen_rtx (MEM, mode, address_reg);
1563   emit_move_insn (profiler_reg, mem_ref);
1564
1565   add_ref = gen_rtx (PLUS, mode, profiler_reg, GEN_INT (1));
1566   emit_move_insn (profiler_reg, add_ref);
1567
1568   /* This is the same rtx as above, but it is not legal to share this rtx.  */
1569   mem_ref = gen_rtx (MEM, mode, address_reg);
1570   emit_move_insn (mem_ref, profiler_reg);
1571
1572   sequence = gen_sequence ();
1573   end_sequence ();
1574   emit_insn_after (sequence, insert_after);
1575 }
1576
1577 /* Output code for a constructor that will invoke __bb_init_func, if
1578    this has not already been done. */
1579
1580 void
1581 output_func_start_profiler ()
1582 {
1583   tree fnname, fndecl;
1584   char *name, *cfnname;
1585   rtx table_address;
1586   enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0);
1587
1588   /* It's either already been output, or we don't need it because we're
1589      not doing profile-arcs. */
1590   if (! need_func_profiler)
1591     return;
1592
1593   need_func_profiler = 0;
1594
1595   /* Synthesize a constructor function to invoke __bb_init_func with a
1596      pointer to this object file's profile block. */
1597   start_sequence ();
1598
1599   /* Try and make a unique name given the "file function name".
1600
1601      And no, I don't like this either. */
1602
1603   fnname = get_file_function_name ('I');
1604   cfnname = IDENTIFIER_POINTER (fnname);
1605   name = xmalloc (strlen (cfnname) + 5);
1606   sprintf (name, "%sGCOV",cfnname);
1607   fnname = get_identifier (name);
1608   free (name);
1609
1610   fndecl = build_decl (FUNCTION_DECL, fnname,
1611                        build_function_type (void_type_node, NULL_TREE));
1612   DECL_EXTERNAL (fndecl) = 0;
1613   TREE_PUBLIC (fndecl) = 1;
1614   DECL_ASSEMBLER_NAME (fndecl) = fnname;
1615   DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1616   current_function_decl = fndecl;
1617   pushlevel (0);
1618   make_function_rtl (fndecl);
1619   init_function_start (fndecl, input_filename, lineno);
1620   expand_function_start (fndecl, 0);
1621
1622   /* Actually generate the code to call __bb_init_func. */
1623   name = xmalloc (20);
1624   ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 0);
1625   table_address = force_reg (Pmode, gen_rtx (SYMBOL_REF, Pmode, name));
1626   emit_library_call (gen_rtx (SYMBOL_REF, Pmode, "__bb_init_func"), 0,
1627                      mode, 1, table_address, Pmode);
1628
1629   expand_function_end (input_filename, lineno, 0);
1630   poplevel (1, 0, 1);
1631   rest_of_compilation (fndecl);
1632   fflush (asm_out_file);
1633   current_function_decl = NULL_TREE;
1634
1635   assemble_constructor (IDENTIFIER_POINTER (DECL_NAME (fndecl)));
1636 }