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