profile.c revision 50397
150397Sobrien/* Calculate branch probabilities, and basic block execution counts. 250397Sobrien Copyright (C) 1990, 91-94, 96, 97, 1998 Free Software Foundation, Inc. 350397Sobrien Contributed by James E. Wilson, UC Berkeley/Cygnus Support; 450397Sobrien based on some ideas from Dain Samples of UC Berkeley. 550397Sobrien Further mangling by Bob Manson, Cygnus Support. 650397Sobrien 750397SobrienThis file is part of GNU CC. 850397Sobrien 950397SobrienGNU CC is free software; you can redistribute it and/or modify 1050397Sobrienit under the terms of the GNU General Public License as published by 1150397Sobrienthe Free Software Foundation; either version 2, or (at your option) 1250397Sobrienany later version. 1350397Sobrien 1450397SobrienGNU CC is distributed in the hope that it will be useful, 1550397Sobrienbut WITHOUT ANY WARRANTY; without even the implied warranty of 1650397SobrienMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1750397SobrienGNU General Public License for more details. 1850397Sobrien 1950397SobrienYou should have received a copy of the GNU General Public License 2050397Sobrienalong with GNU CC; see the file COPYING. If not, write to 2150397Sobrienthe Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ 2250397Sobrien 2350397Sobrien/* ??? Really should not put insns inside of LIBCALL sequences, when putting 2450397Sobrien insns after a call, should look for the insn setting the retval, and 2550397Sobrien insert the insns after that one. */ 2650397Sobrien 2750397Sobrien/* ??? Register allocation should use basic block execution counts to 2850397Sobrien give preference to the most commonly executed blocks. */ 2950397Sobrien 3050397Sobrien/* ??? The .da files are not safe. Changing the program after creating .da 3150397Sobrien files or using different options when compiling with -fbranch-probabilities 3250397Sobrien can result the arc data not matching the program. Maybe add instrumented 3350397Sobrien arc count to .bbg file? Maybe check whether PFG matches the .bbg file? */ 3450397Sobrien 3550397Sobrien/* ??? Should calculate branch probabilities before instrumenting code, since 3650397Sobrien then we can use arc counts to help decide which arcs to instrument. */ 3750397Sobrien 3850397Sobrien/* ??? Rearrange code so that the most frequently executed arcs become from 3950397Sobrien one block to the next block (i.e. a fall through), move seldom executed 4050397Sobrien code outside of loops even at the expense of adding a few branches to 4150397Sobrien achieve this, see Dain Sample's UC Berkeley thesis. */ 4250397Sobrien 4350397Sobrien#include "config.h" 4450397Sobrien#include "system.h" 4550397Sobrien#include "rtl.h" 4650397Sobrien#include "flags.h" 4750397Sobrien#include "insn-flags.h" 4850397Sobrien#include "insn-config.h" 4950397Sobrien#include "output.h" 5050397Sobrien#include "regs.h" 5150397Sobrien#include "tree.h" 5250397Sobrien#include "output.h" 5350397Sobrien#include "gcov-io.h" 5450397Sobrien#include "toplev.h" 5550397Sobrien 5650397Sobrienextern char * xmalloc (); 5750397Sobrien 5850397Sobrien/* One of these is dynamically created whenever we identify an arc in the 5950397Sobrien function. */ 6050397Sobrien 6150397Sobrienstruct adj_list 6250397Sobrien{ 6350397Sobrien int source; 6450397Sobrien int target; 6550397Sobrien int arc_count; 6650397Sobrien unsigned int count_valid : 1; 6750397Sobrien unsigned int on_tree : 1; 6850397Sobrien unsigned int fake : 1; 6950397Sobrien unsigned int fall_through : 1; 7050397Sobrien rtx branch_insn; 7150397Sobrien struct adj_list *pred_next; 7250397Sobrien struct adj_list *succ_next; 7350397Sobrien}; 7450397Sobrien 7550397Sobrien#define ARC_TARGET(ARCPTR) (ARCPTR->target) 7650397Sobrien#define ARC_SOURCE(ARCPTR) (ARCPTR->source) 7750397Sobrien#define ARC_COUNT(ARCPTR) (ARCPTR->arc_count) 7850397Sobrien 7950397Sobrien/* Count the number of basic blocks, and create an array of these structures, 8050397Sobrien one for each bb in the function. */ 8150397Sobrien 8250397Sobrienstruct bb_info 8350397Sobrien{ 8450397Sobrien struct adj_list *succ; 8550397Sobrien struct adj_list *pred; 8650397Sobrien int succ_count; 8750397Sobrien int pred_count; 8850397Sobrien int exec_count; 8950397Sobrien unsigned int count_valid : 1; 9050397Sobrien unsigned int on_tree : 1; 9150397Sobrien rtx first_insn; 9250397Sobrien}; 9350397Sobrien 9450397Sobrien/* Indexed by label number, gives the basic block number containing that 9550397Sobrien label. */ 9650397Sobrien 9750397Sobrienstatic int *label_to_bb; 9850397Sobrien 9950397Sobrien/* Number of valid entries in the label_to_bb array. */ 10050397Sobrien 10150397Sobrienstatic int label_to_bb_size; 10250397Sobrien 10350397Sobrien/* Indexed by block index, holds the basic block graph. */ 10450397Sobrien 10550397Sobrienstatic struct bb_info *bb_graph; 10650397Sobrien 10750397Sobrien/* Name and file pointer of the output file for the basic block graph. */ 10850397Sobrien 10950397Sobrienstatic char *bbg_file_name; 11050397Sobrienstatic FILE *bbg_file; 11150397Sobrien 11250397Sobrien/* Name and file pointer of the input file for the arc count data. */ 11350397Sobrien 11450397Sobrienstatic char *da_file_name; 11550397Sobrienstatic FILE *da_file; 11650397Sobrien 11750397Sobrien/* Pointer of the output file for the basic block/line number map. */ 11850397Sobrienstatic FILE *bb_file; 11950397Sobrien 12050397Sobrien/* Last source file name written to bb_file. */ 12150397Sobrien 12250397Sobrienstatic char *last_bb_file_name; 12350397Sobrien 12450397Sobrien/* Indicates whether the next line number note should be output to 12550397Sobrien bb_file or not. Used to eliminate a redundant note after an 12650397Sobrien expanded inline function call. */ 12750397Sobrien 12850397Sobrienstatic int ignore_next_note; 12950397Sobrien 13050397Sobrien/* Used by final, for allocating the proper amount of storage for the 13150397Sobrien instrumented arc execution counts. */ 13250397Sobrien 13350397Sobrienint count_instrumented_arcs; 13450397Sobrien 13550397Sobrien/* Number of executions for the return label. */ 13650397Sobrien 13750397Sobrienint return_label_execution_count; 13850397Sobrien 13950397Sobrien/* Collect statistics on the performance of this pass for the entire source 14050397Sobrien file. */ 14150397Sobrien 14250397Sobrienstatic int total_num_blocks; 14350397Sobrienstatic int total_num_arcs; 14450397Sobrienstatic int total_num_arcs_instrumented; 14550397Sobrienstatic int total_num_blocks_created; 14650397Sobrienstatic int total_num_passes; 14750397Sobrienstatic int total_num_times_called; 14850397Sobrienstatic int total_hist_br_prob[20]; 14950397Sobrienstatic int total_num_never_executed; 15050397Sobrienstatic int total_num_branches; 15150397Sobrien 15250397Sobrien/* Forward declarations. */ 15350397Sobrienstatic void init_arc PROTO((struct adj_list *, int, int, rtx)); 15450397Sobrienstatic void find_spanning_tree PROTO((int)); 15550397Sobrienstatic void expand_spanning_tree PROTO((int)); 15650397Sobrienstatic void fill_spanning_tree PROTO((int)); 15750397Sobrienstatic void init_arc_profiler PROTO((void)); 15850397Sobrienstatic void output_arc_profiler PROTO((int, rtx)); 15950397Sobrien 16050397Sobrien#ifndef LONG_TYPE_SIZE 16150397Sobrien#define LONG_TYPE_SIZE BITS_PER_WORD 16250397Sobrien#endif 16350397Sobrien 16450397Sobrien/* If non-zero, we need to output a constructor to set up the 16550397Sobrien per-object-file data. */ 16650397Sobrienstatic int need_func_profiler = 0; 16750397Sobrien 16850397Sobrien 16950397Sobrien/* Add arc instrumentation code to the entire insn chain. 17050397Sobrien 17150397Sobrien F is the first insn of the chain. 17250397Sobrien NUM_BLOCKS is the number of basic blocks found in F. 17350397Sobrien DUMP_FILE, if nonzero, is an rtl dump file we can write to. */ 17450397Sobrien 17550397Sobrienstatic void 17650397Sobrieninstrument_arcs (f, num_blocks, dump_file) 17750397Sobrien rtx f; 17850397Sobrien int num_blocks; 17950397Sobrien FILE *dump_file; 18050397Sobrien{ 18150397Sobrien register int i; 18250397Sobrien register struct adj_list *arcptr, *backptr; 18350397Sobrien int num_arcs = 0; 18450397Sobrien int num_instr_arcs = 0; 18550397Sobrien rtx insn; 18650397Sobrien 18750397Sobrien /* Instrument the program start. */ 18850397Sobrien /* Handle block 0 specially, since it will always be instrumented, 18950397Sobrien but it doesn't have a valid first_insn or branch_insn. We must 19050397Sobrien put the instructions before the NOTE_INSN_FUNCTION_BEG note, so 19150397Sobrien that they don't clobber any of the parameters of the current 19250397Sobrien function. */ 19350397Sobrien for (insn = f; insn; insn = NEXT_INSN (insn)) 19450397Sobrien if (GET_CODE (insn) == NOTE 19550397Sobrien && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG) 19650397Sobrien break; 19750397Sobrien insn = PREV_INSN (insn); 19850397Sobrien need_func_profiler = 1; 19950397Sobrien output_arc_profiler (total_num_arcs_instrumented + num_instr_arcs++, insn); 20050397Sobrien 20150397Sobrien for (i = 1; i < num_blocks; i++) 20250397Sobrien for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next) 20350397Sobrien if (! arcptr->on_tree) 20450397Sobrien { 20550397Sobrien if (dump_file) 20650397Sobrien fprintf (dump_file, "Arc %d to %d instrumented\n", i, 20750397Sobrien ARC_TARGET (arcptr)); 20850397Sobrien 20950397Sobrien /* Check to see if this arc is the only exit from its source block, 21050397Sobrien or the only entrance to its target block. In either case, 21150397Sobrien we don't need to create a new block to instrument the arc. */ 21250397Sobrien 21350397Sobrien if (bb_graph[i].succ == arcptr && arcptr->succ_next == 0) 21450397Sobrien { 21550397Sobrien /* Instrument the source block. */ 21650397Sobrien output_arc_profiler (total_num_arcs_instrumented 21750397Sobrien + num_instr_arcs++, 21850397Sobrien PREV_INSN (bb_graph[i].first_insn)); 21950397Sobrien } 22050397Sobrien else if (arcptr == bb_graph[ARC_TARGET (arcptr)].pred 22150397Sobrien && arcptr->pred_next == 0) 22250397Sobrien { 22350397Sobrien /* Instrument the target block. */ 22450397Sobrien output_arc_profiler (total_num_arcs_instrumented 22550397Sobrien + num_instr_arcs++, 22650397Sobrien PREV_INSN (bb_graph[ARC_TARGET (arcptr)].first_insn)); 22750397Sobrien } 22850397Sobrien else if (arcptr->fall_through) 22950397Sobrien { 23050397Sobrien /* This is a fall-through; put the instrumentation code after 23150397Sobrien the branch that ends this block. */ 23250397Sobrien 23350397Sobrien for (backptr = bb_graph[i].succ; backptr; 23450397Sobrien backptr = backptr->succ_next) 23550397Sobrien if (backptr != arcptr) 23650397Sobrien break; 23750397Sobrien 23850397Sobrien output_arc_profiler (total_num_arcs_instrumented 23950397Sobrien + num_instr_arcs++, 24050397Sobrien backptr->branch_insn); 24150397Sobrien } 24250397Sobrien else 24350397Sobrien { 24450397Sobrien /* Must emit a new basic block to hold the arc counting code. */ 24550397Sobrien enum rtx_code code = GET_CODE (PATTERN (arcptr->branch_insn)); 24650397Sobrien 24750397Sobrien if (code == SET) 24850397Sobrien { 24950397Sobrien /* Create the new basic block right after the branch. 25050397Sobrien Invert the branch so that it jumps past the end of the new 25150397Sobrien block. The new block will consist of the instrumentation 25250397Sobrien code, and a jump to the target of this arc. */ 25350397Sobrien int this_is_simplejump = simplejump_p (arcptr->branch_insn); 25450397Sobrien rtx new_label = gen_label_rtx (); 25550397Sobrien rtx old_label, set_src; 25650397Sobrien rtx after = arcptr->branch_insn; 25750397Sobrien 25850397Sobrien /* Simplejumps can't reach here. */ 25950397Sobrien if (this_is_simplejump) 26050397Sobrien abort (); 26150397Sobrien 26250397Sobrien /* We can't use JUMP_LABEL, because it won't be set if we 26350397Sobrien are compiling without optimization. */ 26450397Sobrien 26550397Sobrien set_src = SET_SRC (single_set (arcptr->branch_insn)); 26650397Sobrien if (GET_CODE (set_src) == LABEL_REF) 26750397Sobrien old_label = set_src; 26850397Sobrien else if (GET_CODE (set_src) != IF_THEN_ELSE) 26950397Sobrien abort (); 27050397Sobrien else if (XEXP (set_src, 1) == pc_rtx) 27150397Sobrien old_label = XEXP (XEXP (set_src, 2), 0); 27250397Sobrien else 27350397Sobrien old_label = XEXP (XEXP (set_src, 1), 0); 27450397Sobrien 27550397Sobrien /* Set the JUMP_LABEL so that redirect_jump will work. */ 27650397Sobrien JUMP_LABEL (arcptr->branch_insn) = old_label; 27750397Sobrien 27850397Sobrien /* Add a use for OLD_LABEL that will be needed when we emit 27950397Sobrien the JUMP_INSN below. If we don't do this here, 28050397Sobrien `invert_jump' might delete it for us. We must add two 28150397Sobrien when not optimizing, because the NUSES is zero now, 28250397Sobrien but must be at least two to prevent the label from being 28350397Sobrien deleted. */ 28450397Sobrien LABEL_NUSES (old_label) += 2; 28550397Sobrien 28650397Sobrien /* Emit the insns for the new block in reverse order, 28750397Sobrien since that is most convenient. */ 28850397Sobrien 28950397Sobrien if (this_is_simplejump) 29050397Sobrien { 29150397Sobrien after = NEXT_INSN (arcptr->branch_insn); 29250397Sobrien if (! redirect_jump (arcptr->branch_insn, new_label)) 29350397Sobrien /* Don't know what to do if this branch won't 29450397Sobrien redirect. */ 29550397Sobrien abort (); 29650397Sobrien } 29750397Sobrien else 29850397Sobrien { 29950397Sobrien if (! invert_jump (arcptr->branch_insn, new_label)) 30050397Sobrien /* Don't know what to do if this branch won't invert. */ 30150397Sobrien abort (); 30250397Sobrien 30350397Sobrien emit_label_after (new_label, after); 30450397Sobrien LABEL_NUSES (new_label)++; 30550397Sobrien } 30650397Sobrien emit_barrier_after (after); 30750397Sobrien emit_jump_insn_after (gen_jump (old_label), after); 30850397Sobrien JUMP_LABEL (NEXT_INSN (after)) = old_label; 30950397Sobrien 31050397Sobrien /* Instrument the source arc. */ 31150397Sobrien output_arc_profiler (total_num_arcs_instrumented 31250397Sobrien + num_instr_arcs++, 31350397Sobrien after); 31450397Sobrien if (this_is_simplejump) 31550397Sobrien { 31650397Sobrien emit_label_after (new_label, after); 31750397Sobrien LABEL_NUSES (new_label)++; 31850397Sobrien } 31950397Sobrien } 32050397Sobrien else if (code == ADDR_VEC || code == ADDR_DIFF_VEC) 32150397Sobrien { 32250397Sobrien /* A table jump. Create a new basic block immediately 32350397Sobrien after the table, by emitting a barrier, a label, a 32450397Sobrien counting note, and a jump to the old label. Put the 32550397Sobrien new label in the table. */ 32650397Sobrien 32750397Sobrien rtx new_label = gen_label_rtx (); 32850397Sobrien rtx old_lref, new_lref; 32950397Sobrien int index; 33050397Sobrien 33150397Sobrien /* Must determine the old_label reference, do this 33250397Sobrien by counting the arcs after this one, which will 33350397Sobrien give the index of our label in the table. */ 33450397Sobrien 33550397Sobrien index = 0; 33650397Sobrien for (backptr = arcptr->succ_next; backptr; 33750397Sobrien backptr = backptr->succ_next) 33850397Sobrien index++; 33950397Sobrien 34050397Sobrien old_lref = XVECEXP (PATTERN (arcptr->branch_insn), 34150397Sobrien (code == ADDR_DIFF_VEC), index); 34250397Sobrien 34350397Sobrien /* Emit the insns for the new block in reverse order, 34450397Sobrien since that is most convenient. */ 34550397Sobrien emit_jump_insn_after (gen_jump (XEXP (old_lref, 0)), 34650397Sobrien arcptr->branch_insn); 34750397Sobrien JUMP_LABEL (NEXT_INSN (arcptr->branch_insn)) 34850397Sobrien = XEXP (old_lref, 0); 34950397Sobrien 35050397Sobrien /* Instrument the source arc. */ 35150397Sobrien output_arc_profiler (total_num_arcs_instrumented 35250397Sobrien + num_instr_arcs++, 35350397Sobrien arcptr->branch_insn); 35450397Sobrien 35550397Sobrien emit_label_after (new_label, arcptr->branch_insn); 35650397Sobrien LABEL_NUSES (NEXT_INSN (arcptr->branch_insn))++; 35750397Sobrien emit_barrier_after (arcptr->branch_insn); 35850397Sobrien 35950397Sobrien /* Fix up the table jump. */ 36050397Sobrien new_lref = gen_rtx_LABEL_REF (Pmode, new_label); 36150397Sobrien XVECEXP (PATTERN (arcptr->branch_insn), 36250397Sobrien (code == ADDR_DIFF_VEC), index) = new_lref; 36350397Sobrien } 36450397Sobrien else 36550397Sobrien abort (); 36650397Sobrien 36750397Sobrien num_arcs += 1; 36850397Sobrien if (dump_file) 36950397Sobrien fprintf (dump_file, 37050397Sobrien "Arc %d to %d needed new basic block\n", i, 37150397Sobrien ARC_TARGET (arcptr)); 37250397Sobrien } 37350397Sobrien } 37450397Sobrien 37550397Sobrien total_num_arcs_instrumented += num_instr_arcs; 37650397Sobrien count_instrumented_arcs = total_num_arcs_instrumented; 37750397Sobrien 37850397Sobrien total_num_blocks_created += num_arcs; 37950397Sobrien if (dump_file) 38050397Sobrien { 38150397Sobrien fprintf (dump_file, "%d arcs instrumented\n", num_instr_arcs); 38250397Sobrien fprintf (dump_file, "%d extra basic blocks created\n", num_arcs); 38350397Sobrien } 38450397Sobrien} 38550397Sobrien 38650397Sobrien/* Output STRING to bb_file, surrounded by DELIMITER. */ 38750397Sobrien 38850397Sobrienstatic void 38950397Sobrienoutput_gcov_string (string, delimiter) 39050397Sobrien char *string; 39150397Sobrien long delimiter; 39250397Sobrien{ 39350397Sobrien long temp; 39450397Sobrien 39550397Sobrien /* Write a delimiter to indicate that a file name follows. */ 39650397Sobrien __write_long (delimiter, bb_file, 4); 39750397Sobrien 39850397Sobrien /* Write the string. */ 39950397Sobrien temp = strlen (string) + 1; 40050397Sobrien fwrite (string, temp, 1, bb_file); 40150397Sobrien 40250397Sobrien /* Append a few zeros, to align the output to a 4 byte boundary. */ 40350397Sobrien temp = temp & 0x3; 40450397Sobrien if (temp) 40550397Sobrien { 40650397Sobrien char c[4]; 40750397Sobrien 40850397Sobrien c[0] = c[1] = c[2] = c[3] = 0; 40950397Sobrien fwrite (c, sizeof (char), 4 - temp, bb_file); 41050397Sobrien } 41150397Sobrien 41250397Sobrien /* Store another delimiter in the .bb file, just to make it easy to find the 41350397Sobrien end of the file name. */ 41450397Sobrien __write_long (delimiter, bb_file, 4); 41550397Sobrien} 41650397Sobrien 41750397Sobrien/* Return TRUE if this insn must be a tablejump entry insn. This works for 41850397Sobrien the MIPS port, but may give false negatives for some targets. */ 41950397Sobrien 42050397Sobrienint 42150397Sobrientablejump_entry_p (insn, label) 42250397Sobrien rtx insn, label; 42350397Sobrien{ 42450397Sobrien rtx next = next_active_insn (insn); 42550397Sobrien enum rtx_code code = GET_CODE (PATTERN (next)); 42650397Sobrien 42750397Sobrien if (code != ADDR_DIFF_VEC && code != ADDR_VEC) 42850397Sobrien return 0; 42950397Sobrien 43050397Sobrien if (PREV_INSN (next) == XEXP (label, 0)) 43150397Sobrien return 1; 43250397Sobrien 43350397Sobrien return 0; 43450397Sobrien} 43550397Sobrien 43650397Sobrien/* Instrument and/or analyze program behavior based on program flow graph. 43750397Sobrien In either case, this function builds a flow graph for the function being 43850397Sobrien compiled. The flow graph is stored in BB_GRAPH. 43950397Sobrien 44050397Sobrien When FLAG_PROFILE_ARCS is nonzero, this function instruments the arcs in 44150397Sobrien the flow graph that are needed to reconstruct the dynamic behavior of the 44250397Sobrien flow graph. 44350397Sobrien 44450397Sobrien When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary 44550397Sobrien information from a data file containing arc count information from previous 44650397Sobrien executions of the function being compiled. In this case, the flow graph is 44750397Sobrien annotated with actual execution counts, which are later propagated into the 44850397Sobrien rtl for optimization purposes. 44950397Sobrien 45050397Sobrien Main entry point of this file. */ 45150397Sobrien 45250397Sobrienvoid 45350397Sobrienbranch_prob (f, dump_file) 45450397Sobrien rtx f; 45550397Sobrien FILE *dump_file; 45650397Sobrien{ 45750397Sobrien int i, num_blocks; 45850397Sobrien struct adj_list *arcptr; 45950397Sobrien int num_arcs, changes, passes; 46050397Sobrien int total, prob; 46150397Sobrien int hist_br_prob[20], num_never_executed, num_branches; 46250397Sobrien /* Set to non-zero if we got bad count information. */ 46350397Sobrien int bad_counts = 0; 46450397Sobrien 46550397Sobrien /* start of a function. */ 46650397Sobrien if (flag_test_coverage) 46750397Sobrien output_gcov_string (current_function_name, (long) -2); 46850397Sobrien 46950397Sobrien /* Execute this only if doing arc profiling or branch probabilities. */ 47050397Sobrien if (! profile_arc_flag && ! flag_branch_probabilities 47150397Sobrien && ! flag_test_coverage) 47250397Sobrien abort (); 47350397Sobrien 47450397Sobrien total_num_times_called++; 47550397Sobrien 47650397Sobrien /* Create an array label_to_bb of ints of size max_label_num. */ 47750397Sobrien label_to_bb_size = max_label_num (); 47850397Sobrien label_to_bb = (int *) oballoc (label_to_bb_size * sizeof (int)); 47950397Sobrien bzero ((char *) label_to_bb, label_to_bb_size * sizeof (int)); 48050397Sobrien 48150397Sobrien /* Scan the insns in the function, count the number of basic blocks 48250397Sobrien present. When a code label is passed, set label_to_bb[label] = bb 48350397Sobrien number. */ 48450397Sobrien 48550397Sobrien /* The first block found will be block 1, so that function entry can be 48650397Sobrien block 0. */ 48750397Sobrien 48850397Sobrien { 48950397Sobrien register RTX_CODE prev_code = JUMP_INSN; 49050397Sobrien register RTX_CODE code; 49150397Sobrien register rtx insn; 49250397Sobrien register int i; 49350397Sobrien int block_separator_emitted = 0; 49450397Sobrien 49550397Sobrien ignore_next_note = 0; 49650397Sobrien 49750397Sobrien for (insn = NEXT_INSN (f), i = 0; insn; insn = NEXT_INSN (insn)) 49850397Sobrien { 49950397Sobrien code = GET_CODE (insn); 50050397Sobrien 50150397Sobrien if (code == BARRIER) 50250397Sobrien ; 50350397Sobrien else if (code == CODE_LABEL) 50450397Sobrien /* This label is part of the next block, but we can't increment 50550397Sobrien block number yet since there might be multiple labels. */ 50650397Sobrien label_to_bb[CODE_LABEL_NUMBER (insn)] = i + 1; 50750397Sobrien /* We make NOTE_INSN_SETJMP notes into a block of their own, so that 50850397Sobrien they can be the target of the fake arc for the setjmp call. 50950397Sobrien This avoids creating cycles of fake arcs, which would happen if 51050397Sobrien the block after the setjmp call contained a call insn. */ 51150397Sobrien else if ((prev_code == JUMP_INSN || prev_code == CALL_INSN 51250397Sobrien || prev_code == CODE_LABEL || prev_code == BARRIER) 51350397Sobrien && (GET_RTX_CLASS (code) == 'i' 51450397Sobrien || (code == NOTE 51550397Sobrien && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP))) 51650397Sobrien { 51750397Sobrien i += 1; 51850397Sobrien 51950397Sobrien /* Emit the block separator if it hasn't already been emitted. */ 52050397Sobrien if (flag_test_coverage && ! block_separator_emitted) 52150397Sobrien { 52250397Sobrien /* Output a zero to the .bb file to indicate that a new 52350397Sobrien block list is starting. */ 52450397Sobrien __write_long (0, bb_file, 4); 52550397Sobrien } 52650397Sobrien block_separator_emitted = 0; 52750397Sobrien } 52850397Sobrien /* If flag_test_coverage is true, then we must add an entry to the 52950397Sobrien .bb file for every note. */ 53050397Sobrien else if (code == NOTE && flag_test_coverage) 53150397Sobrien { 53250397Sobrien /* Must ignore the line number notes that immediately follow the 53350397Sobrien end of an inline function to avoid counting it twice. There 53450397Sobrien is a note before the call, and one after the call. */ 53550397Sobrien if (NOTE_LINE_NUMBER (insn) == NOTE_REPEATED_LINE_NUMBER) 53650397Sobrien ignore_next_note = 1; 53750397Sobrien else if (NOTE_LINE_NUMBER (insn) > 0) 53850397Sobrien { 53950397Sobrien if (ignore_next_note) 54050397Sobrien ignore_next_note = 0; 54150397Sobrien else 54250397Sobrien { 54350397Sobrien /* Emit a block separator here to ensure that a NOTE 54450397Sobrien immediately following a JUMP_INSN or CALL_INSN will end 54550397Sobrien up in the right basic block list. */ 54650397Sobrien if ((prev_code == JUMP_INSN || prev_code == CALL_INSN 54750397Sobrien || prev_code == CODE_LABEL || prev_code == BARRIER) 54850397Sobrien && ! block_separator_emitted) 54950397Sobrien { 55050397Sobrien /* Output a zero to the .bb file to indicate that 55150397Sobrien a new block list is starting. */ 55250397Sobrien __write_long (0, bb_file, 4); 55350397Sobrien 55450397Sobrien block_separator_emitted = 1; 55550397Sobrien } 55650397Sobrien 55750397Sobrien /* If this is a new source file, then output the file's 55850397Sobrien name to the .bb file. */ 55950397Sobrien if (! last_bb_file_name 56050397Sobrien || strcmp (NOTE_SOURCE_FILE (insn), 56150397Sobrien last_bb_file_name)) 56250397Sobrien { 56350397Sobrien if (last_bb_file_name) 56450397Sobrien free (last_bb_file_name); 56550397Sobrien last_bb_file_name 56650397Sobrien = xmalloc (strlen (NOTE_SOURCE_FILE (insn)) + 1); 56750397Sobrien strcpy (last_bb_file_name, NOTE_SOURCE_FILE (insn)); 56850397Sobrien output_gcov_string (NOTE_SOURCE_FILE (insn), (long)-1); 56950397Sobrien } 57050397Sobrien 57150397Sobrien /* Output the line number to the .bb file. Must be done 57250397Sobrien after the output_bb_profile_data() call, and after the 57350397Sobrien file name is written, to ensure that it is correctly 57450397Sobrien handled by gcov. */ 57550397Sobrien __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4); 57650397Sobrien } 57750397Sobrien } 57850397Sobrien } 57950397Sobrien 58050397Sobrien if (code != NOTE) 58150397Sobrien prev_code = code; 58250397Sobrien else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP) 58350397Sobrien prev_code = CALL_INSN; 58450397Sobrien } 58550397Sobrien 58650397Sobrien /* Allocate last `normal' entry for bb_graph. */ 58750397Sobrien 58850397Sobrien /* The last insn was a jump, call, or label. In that case we have 58950397Sobrien a block at the end of the function with no insns. */ 59050397Sobrien if (prev_code == JUMP_INSN || prev_code == CALL_INSN 59150397Sobrien || prev_code == CODE_LABEL || prev_code == BARRIER) 59250397Sobrien { 59350397Sobrien i++; 59450397Sobrien 59550397Sobrien /* Emit the block separator if it hasn't already been emitted. */ 59650397Sobrien if (flag_test_coverage && ! block_separator_emitted) 59750397Sobrien { 59850397Sobrien /* Output a zero to the .bb file to indicate that a new 59950397Sobrien block list is starting. */ 60050397Sobrien __write_long (0, bb_file, 4); 60150397Sobrien } 60250397Sobrien } 60350397Sobrien 60450397Sobrien /* Create another block to stand for EXIT, and make all return insns, and 60550397Sobrien the last basic block point here. Add one more to account for block 60650397Sobrien zero. */ 60750397Sobrien num_blocks = i + 2; 60850397Sobrien } 60950397Sobrien 61050397Sobrien total_num_blocks += num_blocks; 61150397Sobrien if (dump_file) 61250397Sobrien fprintf (dump_file, "%d basic blocks\n", num_blocks); 61350397Sobrien 61450397Sobrien /* If we are only doing test coverage here, then return now. */ 61550397Sobrien if (! profile_arc_flag && ! flag_branch_probabilities) 61650397Sobrien return; 61750397Sobrien 61850397Sobrien /* Create and initialize the arrays that will hold bb_graph 61950397Sobrien and execution count info. */ 62050397Sobrien 62150397Sobrien bb_graph = (struct bb_info *) alloca (num_blocks * sizeof (struct bb_info)); 62250397Sobrien bzero ((char *) bb_graph, (sizeof (struct bb_info) * num_blocks)); 62350397Sobrien 62450397Sobrien { 62550397Sobrien /* Scan the insns again: 62650397Sobrien - at the entry to each basic block, increment the predecessor count 62750397Sobrien (and successor of previous block) if it is a fall through entry, 62850397Sobrien create adj_list entries for this and the previous block 62950397Sobrien - at each jump insn, increment predecessor/successor counts for 63050397Sobrien target/source basic blocks, add this insn to pred/succ lists. 63150397Sobrien 63250397Sobrien This also cannot be broken out as a separate subroutine 63350397Sobrien because it uses `alloca'. */ 63450397Sobrien 63550397Sobrien register RTX_CODE prev_code = JUMP_INSN; 63650397Sobrien register RTX_CODE code; 63750397Sobrien register rtx insn; 63850397Sobrien register int i; 63950397Sobrien int fall_through = 0; 64050397Sobrien struct adj_list *arcptr; 64150397Sobrien int dest = 0; 64250397Sobrien 64350397Sobrien /* Block 0 always falls through to block 1. */ 64450397Sobrien num_arcs = 0; 64550397Sobrien arcptr = (struct adj_list *) alloca (sizeof (struct adj_list)); 64650397Sobrien init_arc (arcptr, 0, 1, 0); 64750397Sobrien arcptr->fall_through = 1; 64850397Sobrien num_arcs++; 64950397Sobrien 65050397Sobrien /* Add a fake fall through arc from the last block to block 0, to make the 65150397Sobrien graph complete. */ 65250397Sobrien arcptr = (struct adj_list *) alloca (sizeof (struct adj_list)); 65350397Sobrien init_arc (arcptr, num_blocks - 1, 0, 0); 65450397Sobrien arcptr->fake = 1; 65550397Sobrien num_arcs++; 65650397Sobrien 65750397Sobrien /* Exit must be one node of the graph, and all exits from the function 65850397Sobrien must point there. When see a return branch, must point the arc to the 65950397Sobrien exit node. */ 66050397Sobrien 66150397Sobrien /* Must start scan with second insn in function as above. */ 66250397Sobrien for (insn = NEXT_INSN (f), i = 0; insn; insn = NEXT_INSN (insn)) 66350397Sobrien { 66450397Sobrien code = GET_CODE (insn); 66550397Sobrien 66650397Sobrien if (code == BARRIER) 66750397Sobrien fall_through = 0; 66850397Sobrien else if (code == CODE_LABEL) 66950397Sobrien ; 67050397Sobrien /* We make NOTE_INSN_SETJMP notes into a block of their own, so that 67150397Sobrien they can be the target of the fake arc for the setjmp call. 67250397Sobrien This avoids creating cycles of fake arcs, which would happen if 67350397Sobrien the block after the setjmp call ended with a call. */ 67450397Sobrien else if ((prev_code == JUMP_INSN || prev_code == CALL_INSN 67550397Sobrien || prev_code == CODE_LABEL || prev_code == BARRIER) 67650397Sobrien && (GET_RTX_CLASS (code) == 'i' 67750397Sobrien || (code == NOTE 67850397Sobrien && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP))) 67950397Sobrien { 68050397Sobrien /* This is the first insn of the block. */ 68150397Sobrien i += 1; 68250397Sobrien if (fall_through) 68350397Sobrien { 68450397Sobrien arcptr = (struct adj_list *) alloca (sizeof (struct adj_list)); 68550397Sobrien init_arc (arcptr, i - 1, i, 0); 68650397Sobrien arcptr->fall_through = 1; 68750397Sobrien 68850397Sobrien num_arcs++; 68950397Sobrien } 69050397Sobrien fall_through = 1; 69150397Sobrien bb_graph[i].first_insn = insn; 69250397Sobrien } 69350397Sobrien else if (code == NOTE) 69450397Sobrien {;} 69550397Sobrien 69650397Sobrien if (code == CALL_INSN) 69750397Sobrien { 69850397Sobrien /* In the normal case, the call returns, and this is just like 69950397Sobrien a branch fall through. */ 70050397Sobrien fall_through = 1; 70150397Sobrien 70250397Sobrien /* Setjmp may return more times than called, so to make the graph 70350397Sobrien solvable, add a fake arc from the function entrance to the 70450397Sobrien next block. 70550397Sobrien 70650397Sobrien All other functions may return fewer times than called (if 70750397Sobrien a descendent call longjmp or exit), so to make the graph 70850397Sobrien solvable, add a fake arc to the function exit from the 70950397Sobrien current block. 71050397Sobrien 71150397Sobrien Distinguish the cases by checking for a SETJUMP note. 71250397Sobrien A call_insn can be the last ins of a function, so must check 71350397Sobrien to see if next insn actually exists. */ 71450397Sobrien arcptr = (struct adj_list *) alloca (sizeof (struct adj_list)); 71550397Sobrien if (NEXT_INSN (insn) 71650397Sobrien && GET_CODE (NEXT_INSN (insn)) == NOTE 71750397Sobrien && NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP) 71850397Sobrien init_arc (arcptr, 0, i+1, insn); 71950397Sobrien else 72050397Sobrien init_arc (arcptr, i, num_blocks-1, insn); 72150397Sobrien arcptr->fake = 1; 72250397Sobrien num_arcs++; 72350397Sobrien } 72450397Sobrien else if (code == JUMP_INSN) 72550397Sobrien { 72650397Sobrien rtx tem, pattern = PATTERN (insn); 72750397Sobrien rtx tablejump = 0; 72850397Sobrien 72950397Sobrien /* If running without optimization, then jump label won't be valid, 73050397Sobrien so we must search for the destination label in that case. 73150397Sobrien We have to handle tablejumps and returns specially anyways, so 73250397Sobrien we don't check the JUMP_LABEL at all here. */ 73350397Sobrien 73450397Sobrien /* ??? This code should be rewritten. We need a more elegant way 73550397Sobrien to find the LABEL_REF. We need a more elegant way to 73650397Sobrien differentiate tablejump entries from computed gotos. 73750397Sobrien We should perhaps reuse code from flow to compute the CFG 73850397Sobrien instead of trying to compute it here. 73950397Sobrien 74050397Sobrien We can't use current_function_has_computed_jump, because that 74150397Sobrien is calculated later by flow. We can't use computed_jump_p, 74250397Sobrien because that returns true for tablejump entry insns for some 74350397Sobrien targets, e.g. HPPA and MIPS. */ 74450397Sobrien 74550397Sobrien if (GET_CODE (pattern) == PARALLEL) 74650397Sobrien { 74750397Sobrien /* This assumes that PARALLEL jumps with a USE are 74850397Sobrien tablejump entry jumps. The same assumption can be found 74950397Sobrien in computed_jump_p. */ 75050397Sobrien /* Make an arc from this jump to the label of the 75150397Sobrien jump table. This will instrument the number of 75250397Sobrien times the switch statement is executed. */ 75350397Sobrien if (GET_CODE (XVECEXP (pattern, 0, 1)) == USE) 75450397Sobrien { 75550397Sobrien tem = XEXP (XVECEXP (pattern, 0, 1), 0); 75650397Sobrien if (GET_CODE (tem) != LABEL_REF) 75750397Sobrien abort (); 75850397Sobrien dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (tem, 0))]; 75950397Sobrien } 76050397Sobrien else if (GET_CODE (XVECEXP (pattern, 0, 0)) == SET 76150397Sobrien && SET_DEST (XVECEXP (pattern, 0, 0)) == pc_rtx) 76250397Sobrien { 76350397Sobrien tem = SET_SRC (XVECEXP (pattern, 0, 0)); 76450397Sobrien if (GET_CODE (tem) == PLUS 76550397Sobrien && GET_CODE (XEXP (tem, 1)) == LABEL_REF) 76650397Sobrien { 76750397Sobrien tem = XEXP (tem, 1); 76850397Sobrien dest = label_to_bb [CODE_LABEL_NUMBER (XEXP (tem, 0))]; 76950397Sobrien } 77050397Sobrien } 77150397Sobrien else 77250397Sobrien abort (); 77350397Sobrien } 77450397Sobrien else if (GET_CODE (pattern) == ADDR_VEC 77550397Sobrien || GET_CODE (pattern) == ADDR_DIFF_VEC) 77650397Sobrien tablejump = pattern; 77750397Sobrien else if (GET_CODE (pattern) == RETURN) 77850397Sobrien dest = num_blocks - 1; 77950397Sobrien else if (GET_CODE (pattern) != SET) 78050397Sobrien abort (); 78150397Sobrien else if ((tem = SET_SRC (pattern)) 78250397Sobrien && GET_CODE (tem) == LABEL_REF) 78350397Sobrien dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (tem, 0))]; 78450397Sobrien /* Recognize HPPA table jump entry. This code is similar to 78550397Sobrien the code above in the PARALLEL case. */ 78650397Sobrien else if (GET_CODE (tem) == PLUS 78750397Sobrien && GET_CODE (XEXP (tem, 0)) == MEM 78850397Sobrien && GET_CODE (XEXP (XEXP (tem, 0), 0)) == PLUS 78950397Sobrien && GET_CODE (XEXP (XEXP (XEXP (tem, 0), 0), 0)) == PC 79050397Sobrien && GET_CODE (XEXP (tem, 1)) == LABEL_REF 79150397Sobrien && tablejump_entry_p (insn, XEXP (tem, 1))) 79250397Sobrien dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (XEXP (tem, 1), 0))]; 79350397Sobrien /* Recognize the MIPS table jump entry. */ 79450397Sobrien else if (GET_CODE (tem) == PLUS 79550397Sobrien && GET_CODE (XEXP (tem, 0)) == REG 79650397Sobrien && GET_CODE (XEXP (tem, 1)) == LABEL_REF 79750397Sobrien && tablejump_entry_p (insn, XEXP (tem, 1))) 79850397Sobrien dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (XEXP (tem, 1), 0))]; 79950397Sobrien else 80050397Sobrien { 80150397Sobrien rtx label_ref; 80250397Sobrien 80350397Sobrien /* Must be an IF_THEN_ELSE branch. If it isn't, assume it 80450397Sobrien is a computed goto, which aren't supported yet. */ 80550397Sobrien if (GET_CODE (tem) != IF_THEN_ELSE) 80650397Sobrien fatal ("-fprofile-arcs does not support computed gotos"); 80750397Sobrien if (XEXP (tem, 1) != pc_rtx) 80850397Sobrien label_ref = XEXP (tem, 1); 80950397Sobrien else 81050397Sobrien label_ref = XEXP (tem, 2); 81150397Sobrien dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (label_ref, 0))]; 81250397Sobrien } 81350397Sobrien 81450397Sobrien if (tablejump) 81550397Sobrien { 81650397Sobrien int diff_vec_p = GET_CODE (tablejump) == ADDR_DIFF_VEC; 81750397Sobrien int len = XVECLEN (tablejump, diff_vec_p); 81850397Sobrien int k; 81950397Sobrien 82050397Sobrien for (k = 0; k < len; k++) 82150397Sobrien { 82250397Sobrien rtx tem = XEXP (XVECEXP (tablejump, diff_vec_p, k), 0); 82350397Sobrien dest = label_to_bb[CODE_LABEL_NUMBER (tem)]; 82450397Sobrien 82550397Sobrien arcptr = (struct adj_list *) alloca (sizeof(struct adj_list)); 82650397Sobrien init_arc (arcptr, i, dest, insn); 82750397Sobrien 82850397Sobrien num_arcs++; 82950397Sobrien } 83050397Sobrien } 83150397Sobrien else 83250397Sobrien { 83350397Sobrien arcptr = (struct adj_list *) alloca (sizeof (struct adj_list)); 83450397Sobrien init_arc (arcptr, i, dest, insn); 83550397Sobrien 83650397Sobrien num_arcs++; 83750397Sobrien } 83850397Sobrien 83950397Sobrien /* Determine whether or not this jump will fall through. 84050397Sobrien Unconditional jumps and returns are not always followed by 84150397Sobrien barriers. */ 84250397Sobrien pattern = PATTERN (insn); 84350397Sobrien if (GET_CODE (pattern) == PARALLEL 84450397Sobrien || GET_CODE (pattern) == RETURN) 84550397Sobrien fall_through = 0; 84650397Sobrien else if (GET_CODE (pattern) == ADDR_VEC 84750397Sobrien || GET_CODE (pattern) == ADDR_DIFF_VEC) 84850397Sobrien /* These aren't actually jump insns, but they never fall 84950397Sobrien through, so... */ 85050397Sobrien fall_through = 0; 85150397Sobrien else 85250397Sobrien { 85350397Sobrien if (GET_CODE (pattern) != SET || SET_DEST (pattern) != pc_rtx) 85450397Sobrien abort (); 85550397Sobrien if (GET_CODE (SET_SRC (pattern)) != IF_THEN_ELSE) 85650397Sobrien fall_through = 0; 85750397Sobrien } 85850397Sobrien } 85950397Sobrien 86050397Sobrien if (code != NOTE) 86150397Sobrien prev_code = code; 86250397Sobrien else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP) 86350397Sobrien { 86450397Sobrien /* Make a fake insn to tag our notes on. */ 86550397Sobrien bb_graph[i].first_insn = insn 86650397Sobrien = emit_insn_after (gen_rtx_USE (VOIDmode, stack_pointer_rtx), 86750397Sobrien insn); 86850397Sobrien prev_code = CALL_INSN; 86950397Sobrien } 87050397Sobrien } 87150397Sobrien 87250397Sobrien /* If the code at the end of the function would give a new block, then 87350397Sobrien do the following. */ 87450397Sobrien 87550397Sobrien if (prev_code == JUMP_INSN || prev_code == CALL_INSN 87650397Sobrien || prev_code == CODE_LABEL || prev_code == BARRIER) 87750397Sobrien { 87850397Sobrien if (fall_through) 87950397Sobrien { 88050397Sobrien arcptr = (struct adj_list *) alloca (sizeof (struct adj_list)); 88150397Sobrien init_arc (arcptr, i, i + 1, 0); 88250397Sobrien arcptr->fall_through = 1; 88350397Sobrien 88450397Sobrien num_arcs++; 88550397Sobrien } 88650397Sobrien 88750397Sobrien /* This may not be a real insn, but that should not cause a problem. */ 88850397Sobrien bb_graph[i+1].first_insn = get_last_insn (); 88950397Sobrien } 89050397Sobrien 89150397Sobrien /* There is always a fake arc from the last block of the function 89250397Sobrien to the function exit block. */ 89350397Sobrien arcptr = (struct adj_list *) alloca (sizeof (struct adj_list)); 89450397Sobrien init_arc (arcptr, num_blocks-2, num_blocks-1, 0); 89550397Sobrien arcptr->fake = 1; 89650397Sobrien num_arcs++; 89750397Sobrien } 89850397Sobrien 89950397Sobrien total_num_arcs += num_arcs; 90050397Sobrien if (dump_file) 90150397Sobrien fprintf (dump_file, "%d arcs\n", num_arcs); 90250397Sobrien 90350397Sobrien /* Create spanning tree from basic block graph, mark each arc that is 90450397Sobrien on the spanning tree. */ 90550397Sobrien 90650397Sobrien /* To reduce the instrumentation cost, make two passes over the tree. 90750397Sobrien First, put as many must-split (crowded and fake) arcs on the tree as 90850397Sobrien possible, then on the second pass fill in the rest of the tree. 90950397Sobrien Note that the spanning tree is considered undirected, so that as many 91050397Sobrien must-split arcs as possible can be put on it. 91150397Sobrien 91250397Sobrien Fallthrough arcs which are crowded should not be chosen on the first 91350397Sobrien pass, since they do not require creating a new basic block. These 91450397Sobrien arcs will have fall_through set. */ 91550397Sobrien 91650397Sobrien find_spanning_tree (num_blocks); 91750397Sobrien 91850397Sobrien /* Create a .bbg file from which gcov can reconstruct the basic block 91950397Sobrien graph. First output the number of basic blocks, and then for every 92050397Sobrien arc output the source and target basic block numbers. 92150397Sobrien NOTE: The format of this file must be compatible with gcov. */ 92250397Sobrien 92350397Sobrien if (flag_test_coverage) 92450397Sobrien { 92550397Sobrien int flag_bits; 92650397Sobrien 92750397Sobrien __write_long (num_blocks, bbg_file, 4); 92850397Sobrien __write_long (num_arcs, bbg_file, 4); 92950397Sobrien 93050397Sobrien for (i = 0; i < num_blocks; i++) 93150397Sobrien { 93250397Sobrien long count = 0; 93350397Sobrien for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next) 93450397Sobrien count++; 93550397Sobrien __write_long (count, bbg_file, 4); 93650397Sobrien 93750397Sobrien for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next) 93850397Sobrien { 93950397Sobrien flag_bits = 0; 94050397Sobrien if (arcptr->on_tree) 94150397Sobrien flag_bits |= 0x1; 94250397Sobrien if (arcptr->fake) 94350397Sobrien flag_bits |= 0x2; 94450397Sobrien if (arcptr->fall_through) 94550397Sobrien flag_bits |= 0x4; 94650397Sobrien 94750397Sobrien __write_long (ARC_TARGET (arcptr), bbg_file, 4); 94850397Sobrien __write_long (flag_bits, bbg_file, 4); 94950397Sobrien } 95050397Sobrien } 95150397Sobrien 95250397Sobrien /* Emit a -1 to separate the list of all arcs from the list of 95350397Sobrien loop back edges that follows. */ 95450397Sobrien __write_long (-1, bbg_file, 4); 95550397Sobrien } 95650397Sobrien 95750397Sobrien /* For each arc not on the spanning tree, add counting code as rtl. */ 95850397Sobrien 95950397Sobrien if (profile_arc_flag) 96050397Sobrien { 96150397Sobrien instrument_arcs (f, num_blocks, dump_file); 96250397Sobrien allocate_reg_info (max_reg_num (), FALSE, FALSE); 96350397Sobrien } 96450397Sobrien 96550397Sobrien /* Execute the rest only if doing branch probabilities. */ 96650397Sobrien if (! flag_branch_probabilities) 96750397Sobrien return; 96850397Sobrien 96950397Sobrien /* For each arc not on the spanning tree, set its execution count from 97050397Sobrien the .da file. */ 97150397Sobrien 97250397Sobrien /* The first count in the .da file is the number of times that the function 97350397Sobrien was entered. This is the exec_count for block zero. */ 97450397Sobrien 97550397Sobrien num_arcs = 0; 97650397Sobrien for (i = 0; i < num_blocks; i++) 97750397Sobrien for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next) 97850397Sobrien if (! arcptr->on_tree) 97950397Sobrien { 98050397Sobrien num_arcs++; 98150397Sobrien if (da_file) 98250397Sobrien { 98350397Sobrien long value; 98450397Sobrien __read_long (&value, da_file, 8); 98550397Sobrien ARC_COUNT (arcptr) = value; 98650397Sobrien } 98750397Sobrien else 98850397Sobrien ARC_COUNT (arcptr) = 0; 98950397Sobrien arcptr->count_valid = 1; 99050397Sobrien bb_graph[i].succ_count--; 99150397Sobrien bb_graph[ARC_TARGET (arcptr)].pred_count--; 99250397Sobrien } 99350397Sobrien 99450397Sobrien if (dump_file) 99550397Sobrien fprintf (dump_file, "%d arc counts read\n", num_arcs); 99650397Sobrien 99750397Sobrien /* For every block in the file, 99850397Sobrien - if every exit/entrance arc has a known count, then set the block count 99950397Sobrien - if the block count is known, and every exit/entrance arc but one has 100050397Sobrien a known execution count, then set the count of the remaining arc 100150397Sobrien 100250397Sobrien As arc counts are set, decrement the succ/pred count, but don't delete 100350397Sobrien the arc, that way we can easily tell when all arcs are known, or only 100450397Sobrien one arc is unknown. */ 100550397Sobrien 100650397Sobrien /* The order that the basic blocks are iterated through is important. 100750397Sobrien Since the code that finds spanning trees starts with block 0, low numbered 100850397Sobrien arcs are put on the spanning tree in preference to high numbered arcs. 100950397Sobrien Hence, most instrumented arcs are at the end. Graph solving works much 101050397Sobrien faster if we propagate numbers from the end to the start. 101150397Sobrien 101250397Sobrien This takes an average of slightly more than 3 passes. */ 101350397Sobrien 101450397Sobrien changes = 1; 101550397Sobrien passes = 0; 101650397Sobrien while (changes) 101750397Sobrien { 101850397Sobrien passes++; 101950397Sobrien changes = 0; 102050397Sobrien 102150397Sobrien for (i = num_blocks - 1; i >= 0; i--) 102250397Sobrien { 102350397Sobrien struct bb_info *binfo = &bb_graph[i]; 102450397Sobrien if (! binfo->count_valid) 102550397Sobrien { 102650397Sobrien if (binfo->succ_count == 0) 102750397Sobrien { 102850397Sobrien total = 0; 102950397Sobrien for (arcptr = binfo->succ; arcptr; 103050397Sobrien arcptr = arcptr->succ_next) 103150397Sobrien total += ARC_COUNT (arcptr); 103250397Sobrien binfo->exec_count = total; 103350397Sobrien binfo->count_valid = 1; 103450397Sobrien changes = 1; 103550397Sobrien } 103650397Sobrien else if (binfo->pred_count == 0) 103750397Sobrien { 103850397Sobrien total = 0; 103950397Sobrien for (arcptr = binfo->pred; arcptr; 104050397Sobrien arcptr = arcptr->pred_next) 104150397Sobrien total += ARC_COUNT (arcptr); 104250397Sobrien binfo->exec_count = total; 104350397Sobrien binfo->count_valid = 1; 104450397Sobrien changes = 1; 104550397Sobrien } 104650397Sobrien } 104750397Sobrien if (binfo->count_valid) 104850397Sobrien { 104950397Sobrien if (binfo->succ_count == 1) 105050397Sobrien { 105150397Sobrien total = 0; 105250397Sobrien /* One of the counts will be invalid, but it is zero, 105350397Sobrien so adding it in also doesn't hurt. */ 105450397Sobrien for (arcptr = binfo->succ; arcptr; 105550397Sobrien arcptr = arcptr->succ_next) 105650397Sobrien total += ARC_COUNT (arcptr); 105750397Sobrien /* Calculate count for remaining arc by conservation. */ 105850397Sobrien total = binfo->exec_count - total; 105950397Sobrien /* Search for the invalid arc, and set its count. */ 106050397Sobrien for (arcptr = binfo->succ; arcptr; 106150397Sobrien arcptr = arcptr->succ_next) 106250397Sobrien if (! arcptr->count_valid) 106350397Sobrien break; 106450397Sobrien if (! arcptr) 106550397Sobrien abort (); 106650397Sobrien arcptr->count_valid = 1; 106750397Sobrien ARC_COUNT (arcptr) = total; 106850397Sobrien binfo->succ_count--; 106950397Sobrien 107050397Sobrien bb_graph[ARC_TARGET (arcptr)].pred_count--; 107150397Sobrien changes = 1; 107250397Sobrien } 107350397Sobrien if (binfo->pred_count == 1) 107450397Sobrien { 107550397Sobrien total = 0; 107650397Sobrien /* One of the counts will be invalid, but it is zero, 107750397Sobrien so adding it in also doesn't hurt. */ 107850397Sobrien for (arcptr = binfo->pred; arcptr; 107950397Sobrien arcptr = arcptr->pred_next) 108050397Sobrien total += ARC_COUNT (arcptr); 108150397Sobrien /* Calculate count for remaining arc by conservation. */ 108250397Sobrien total = binfo->exec_count - total; 108350397Sobrien /* Search for the invalid arc, and set its count. */ 108450397Sobrien for (arcptr = binfo->pred; arcptr; 108550397Sobrien arcptr = arcptr->pred_next) 108650397Sobrien if (! arcptr->count_valid) 108750397Sobrien break; 108850397Sobrien if (! arcptr) 108950397Sobrien abort (); 109050397Sobrien arcptr->count_valid = 1; 109150397Sobrien ARC_COUNT (arcptr) = total; 109250397Sobrien binfo->pred_count--; 109350397Sobrien 109450397Sobrien bb_graph[ARC_SOURCE (arcptr)].succ_count--; 109550397Sobrien changes = 1; 109650397Sobrien } 109750397Sobrien } 109850397Sobrien } 109950397Sobrien } 110050397Sobrien 110150397Sobrien total_num_passes += passes; 110250397Sobrien if (dump_file) 110350397Sobrien fprintf (dump_file, "Graph solving took %d passes.\n\n", passes); 110450397Sobrien 110550397Sobrien /* If the graph has been correctly solved, every block will have a 110650397Sobrien succ and pred count of zero. */ 110750397Sobrien for (i = 0; i < num_blocks; i++) 110850397Sobrien { 110950397Sobrien struct bb_info *binfo = &bb_graph[i]; 111050397Sobrien if (binfo->succ_count || binfo->pred_count) 111150397Sobrien abort (); 111250397Sobrien } 111350397Sobrien 111450397Sobrien /* For every arc, calculate its branch probability and add a reg_note 111550397Sobrien to the branch insn to indicate this. */ 111650397Sobrien 111750397Sobrien for (i = 0; i < 20; i++) 111850397Sobrien hist_br_prob[i] = 0; 111950397Sobrien num_never_executed = 0; 112050397Sobrien num_branches = 0; 112150397Sobrien 112250397Sobrien for (i = 0; i < num_blocks; i++) 112350397Sobrien { 112450397Sobrien struct bb_info *binfo = &bb_graph[i]; 112550397Sobrien 112650397Sobrien total = binfo->exec_count; 112750397Sobrien for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next) 112850397Sobrien { 112950397Sobrien if (arcptr->branch_insn) 113050397Sobrien { 113150397Sobrien /* This calculates the branch probability as an integer between 113250397Sobrien 0 and REG_BR_PROB_BASE, properly rounded to the nearest 113350397Sobrien integer. Perform the arithmetic in double to avoid 113450397Sobrien overflowing the range of ints. */ 113550397Sobrien 113650397Sobrien if (total == 0) 113750397Sobrien prob = -1; 113850397Sobrien else 113950397Sobrien { 114050397Sobrien rtx pat = PATTERN (arcptr->branch_insn); 114150397Sobrien 114250397Sobrien prob = (((double)ARC_COUNT (arcptr) * REG_BR_PROB_BASE) 114350397Sobrien + (total >> 1)) / total; 114450397Sobrien if (prob < 0 || prob > REG_BR_PROB_BASE) 114550397Sobrien { 114650397Sobrien if (dump_file) 114750397Sobrien fprintf (dump_file, "bad count: prob for %d-%d thought to be %d (forcibly normalized)\n", 114850397Sobrien ARC_SOURCE (arcptr), ARC_TARGET (arcptr), 114950397Sobrien prob); 115050397Sobrien 115150397Sobrien bad_counts = 1; 115250397Sobrien prob = REG_BR_PROB_BASE / 2; 115350397Sobrien } 115450397Sobrien 115550397Sobrien /* Match up probability with JUMP pattern. */ 115650397Sobrien 115750397Sobrien if (GET_CODE (pat) == SET 115850397Sobrien && GET_CODE (SET_SRC (pat)) == IF_THEN_ELSE) 115950397Sobrien { 116050397Sobrien if (ARC_TARGET (arcptr) == ARC_SOURCE (arcptr) + 1) 116150397Sobrien { 116250397Sobrien /* A fall through arc should never have a 116350397Sobrien branch insn. */ 116450397Sobrien abort (); 116550397Sobrien } 116650397Sobrien else 116750397Sobrien { 116850397Sobrien /* This is the arc for the taken branch. */ 116950397Sobrien if (GET_CODE (XEXP (SET_SRC (pat), 2)) != PC) 117050397Sobrien prob = REG_BR_PROB_BASE - prob; 117150397Sobrien } 117250397Sobrien } 117350397Sobrien } 117450397Sobrien 117550397Sobrien if (prob == -1) 117650397Sobrien num_never_executed++; 117750397Sobrien else 117850397Sobrien { 117950397Sobrien int index = prob * 20 / REG_BR_PROB_BASE; 118050397Sobrien if (index == 20) 118150397Sobrien index = 19; 118250397Sobrien hist_br_prob[index]++; 118350397Sobrien } 118450397Sobrien num_branches++; 118550397Sobrien 118650397Sobrien REG_NOTES (arcptr->branch_insn) 118750397Sobrien = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob), 118850397Sobrien REG_NOTES (arcptr->branch_insn)); 118950397Sobrien } 119050397Sobrien } 119150397Sobrien 119250397Sobrien /* Add a REG_EXEC_COUNT note to the first instruction of this block. */ 119350397Sobrien if (! binfo->first_insn 119450397Sobrien || GET_RTX_CLASS (GET_CODE (binfo->first_insn)) != 'i') 119550397Sobrien { 119650397Sobrien /* Block 0 is a fake block representing function entry, and does 119750397Sobrien not have a real first insn. The second last block might not 119850397Sobrien begin with a real insn. */ 119950397Sobrien if (i == num_blocks - 1) 120050397Sobrien return_label_execution_count = total; 120150397Sobrien else if (i != 0 && i != num_blocks - 2) 120250397Sobrien abort (); 120350397Sobrien } 120450397Sobrien else 120550397Sobrien { 120650397Sobrien REG_NOTES (binfo->first_insn) 120750397Sobrien = gen_rtx_EXPR_LIST (REG_EXEC_COUNT, GEN_INT (total), 120850397Sobrien REG_NOTES (binfo->first_insn)); 120950397Sobrien if (i == num_blocks - 1) 121050397Sobrien return_label_execution_count = total; 121150397Sobrien } 121250397Sobrien } 121350397Sobrien 121450397Sobrien /* This should never happen. */ 121550397Sobrien if (bad_counts) 121650397Sobrien warning ("Arc profiling: some arc counts were bad."); 121750397Sobrien 121850397Sobrien if (dump_file) 121950397Sobrien { 122050397Sobrien fprintf (dump_file, "%d branches\n", num_branches); 122150397Sobrien fprintf (dump_file, "%d branches never executed\n", 122250397Sobrien num_never_executed); 122350397Sobrien if (num_branches) 122450397Sobrien for (i = 0; i < 10; i++) 122550397Sobrien fprintf (dump_file, "%d%% branches in range %d-%d%%\n", 122650397Sobrien (hist_br_prob[i]+hist_br_prob[19-i])*100/num_branches, 122750397Sobrien 5*i, 5*i+5); 122850397Sobrien 122950397Sobrien total_num_branches += num_branches; 123050397Sobrien total_num_never_executed += num_never_executed; 123150397Sobrien for (i = 0; i < 20; i++) 123250397Sobrien total_hist_br_prob[i] += hist_br_prob[i]; 123350397Sobrien } 123450397Sobrien 123550397Sobrien} 123650397Sobrien 123750397Sobrien/* Initialize a new arc. 123850397Sobrien ARCPTR is the empty adj_list this function fills in. 123950397Sobrien SOURCE is the block number of the source block. 124050397Sobrien TARGET is the block number of the target block. 124150397Sobrien INSN is the insn which transfers control from SOURCE to TARGET, 124250397Sobrien or zero if the transfer is implicit. */ 124350397Sobrien 124450397Sobrienstatic void 124550397Sobrieninit_arc (arcptr, source, target, insn) 124650397Sobrien struct adj_list *arcptr; 124750397Sobrien int source, target; 124850397Sobrien rtx insn; 124950397Sobrien{ 125050397Sobrien ARC_TARGET (arcptr) = target; 125150397Sobrien ARC_SOURCE (arcptr) = source; 125250397Sobrien 125350397Sobrien ARC_COUNT (arcptr) = 0; 125450397Sobrien arcptr->count_valid = 0; 125550397Sobrien arcptr->on_tree = 0; 125650397Sobrien arcptr->fake = 0; 125750397Sobrien arcptr->fall_through = 0; 125850397Sobrien arcptr->branch_insn = insn; 125950397Sobrien 126050397Sobrien arcptr->succ_next = bb_graph[source].succ; 126150397Sobrien bb_graph[source].succ = arcptr; 126250397Sobrien bb_graph[source].succ_count++; 126350397Sobrien 126450397Sobrien arcptr->pred_next = bb_graph[target].pred; 126550397Sobrien bb_graph[target].pred = arcptr; 126650397Sobrien bb_graph[target].pred_count++; 126750397Sobrien} 126850397Sobrien 126950397Sobrien/* This function searches all of the arcs in the program flow graph, and puts 127050397Sobrien as many bad arcs as possible onto the spanning tree. Bad arcs include 127150397Sobrien fake arcs (needed for setjmp(), longjmp(), exit()) which MUST be on the 127250397Sobrien spanning tree as they can't be instrumented. Also, arcs which must be 127350397Sobrien split when instrumented should be part of the spanning tree if possible. */ 127450397Sobrien 127550397Sobrienstatic void 127650397Sobrienfind_spanning_tree (num_blocks) 127750397Sobrien int num_blocks; 127850397Sobrien{ 127950397Sobrien int i; 128050397Sobrien struct adj_list *arcptr; 128150397Sobrien struct bb_info *binfo = &bb_graph[0]; 128250397Sobrien 128350397Sobrien /* Fake arcs must be part of the spanning tree, and are always safe to put 128450397Sobrien on the spanning tree. Fake arcs will either be a successor of node 0, 128550397Sobrien a predecessor of the last node, or from the last node to node 0. */ 128650397Sobrien 128750397Sobrien for (arcptr = bb_graph[0].succ; arcptr; arcptr = arcptr->succ_next) 128850397Sobrien if (arcptr->fake) 128950397Sobrien { 129050397Sobrien /* Adding this arc should never cause a cycle. This is a fatal 129150397Sobrien error if it would. */ 129250397Sobrien if (bb_graph[ARC_TARGET (arcptr)].on_tree && binfo->on_tree) 129350397Sobrien abort(); 129450397Sobrien else 129550397Sobrien { 129650397Sobrien arcptr->on_tree = 1; 129750397Sobrien bb_graph[ARC_TARGET (arcptr)].on_tree = 1; 129850397Sobrien binfo->on_tree = 1; 129950397Sobrien } 130050397Sobrien } 130150397Sobrien 130250397Sobrien binfo = &bb_graph[num_blocks-1]; 130350397Sobrien for (arcptr = binfo->pred; arcptr; arcptr = arcptr->pred_next) 130450397Sobrien if (arcptr->fake) 130550397Sobrien { 130650397Sobrien /* Adding this arc should never cause a cycle. This is a fatal 130750397Sobrien error if it would. */ 130850397Sobrien if (bb_graph[ARC_SOURCE (arcptr)].on_tree && binfo->on_tree) 130950397Sobrien abort(); 131050397Sobrien else 131150397Sobrien { 131250397Sobrien arcptr->on_tree = 1; 131350397Sobrien bb_graph[ARC_SOURCE (arcptr)].on_tree = 1; 131450397Sobrien binfo->on_tree = 1; 131550397Sobrien } 131650397Sobrien } 131750397Sobrien /* The only entrace to node zero is a fake arc. */ 131850397Sobrien bb_graph[0].pred->on_tree = 1; 131950397Sobrien 132050397Sobrien /* Arcs which are crowded at both the source and target should be put on 132150397Sobrien the spanning tree if possible, except for fall_throuch arcs which never 132250397Sobrien require adding a new block even if crowded, add arcs with the same source 132350397Sobrien and dest which must always be instrumented. */ 132450397Sobrien for (i = 0; i < num_blocks; i++) 132550397Sobrien { 132650397Sobrien binfo = &bb_graph[i]; 132750397Sobrien 132850397Sobrien for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next) 132950397Sobrien if (! ((binfo->succ == arcptr && arcptr->succ_next == 0) 133050397Sobrien || (bb_graph[ARC_TARGET (arcptr)].pred 133150397Sobrien && arcptr->pred_next == 0)) 133250397Sobrien && ! arcptr->fall_through 133350397Sobrien && ARC_TARGET (arcptr) != i) 133450397Sobrien { 133550397Sobrien /* This is a crowded arc at both source and target. Try to put 133650397Sobrien in on the spanning tree. Can do this if either the source or 133750397Sobrien target block is not yet on the tree. */ 133850397Sobrien if (! bb_graph[ARC_TARGET (arcptr)].on_tree || ! binfo->on_tree) 133950397Sobrien { 134050397Sobrien arcptr->on_tree = 1; 134150397Sobrien bb_graph[ARC_TARGET (arcptr)].on_tree = 1; 134250397Sobrien binfo->on_tree = 1; 134350397Sobrien } 134450397Sobrien } 134550397Sobrien } 134650397Sobrien 134750397Sobrien /* Clear all of the basic block on_tree bits, so that we can use them to 134850397Sobrien create the spanning tree. */ 134950397Sobrien for (i = 0; i < num_blocks; i++) 135050397Sobrien bb_graph[i].on_tree = 0; 135150397Sobrien 135250397Sobrien /* Now fill in the spanning tree until every basic block is on it. 135350397Sobrien Don't put the 0 to 1 fall through arc on the tree, since it is 135450397Sobrien always cheap to instrument, so start filling the tree from node 1. */ 135550397Sobrien 135650397Sobrien for (i = 1; i < num_blocks; i++) 135750397Sobrien for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next) 135850397Sobrien if (! arcptr->on_tree 135950397Sobrien && ! bb_graph[ARC_TARGET (arcptr)].on_tree) 136050397Sobrien { 136150397Sobrien fill_spanning_tree (i); 136250397Sobrien break; 136350397Sobrien } 136450397Sobrien} 136550397Sobrien 136650397Sobrien/* Add arcs reached from BLOCK to the spanning tree if they are needed and 136750397Sobrien not already there. */ 136850397Sobrien 136950397Sobrienstatic void 137050397Sobrienfill_spanning_tree (block) 137150397Sobrien int block; 137250397Sobrien{ 137350397Sobrien struct adj_list *arcptr; 137450397Sobrien 137550397Sobrien expand_spanning_tree (block); 137650397Sobrien 137750397Sobrien for (arcptr = bb_graph[block].succ; arcptr; arcptr = arcptr->succ_next) 137850397Sobrien if (! arcptr->on_tree 137950397Sobrien && ! bb_graph[ARC_TARGET (arcptr)].on_tree) 138050397Sobrien { 138150397Sobrien arcptr->on_tree = 1; 138250397Sobrien fill_spanning_tree (ARC_TARGET (arcptr)); 138350397Sobrien } 138450397Sobrien} 138550397Sobrien 138650397Sobrien/* When first visit a block, must add all blocks that are already connected 138750397Sobrien to this block via tree arcs to the spanning tree. */ 138850397Sobrien 138950397Sobrienstatic void 139050397Sobrienexpand_spanning_tree (block) 139150397Sobrien int block; 139250397Sobrien{ 139350397Sobrien struct adj_list *arcptr; 139450397Sobrien 139550397Sobrien bb_graph[block].on_tree = 1; 139650397Sobrien 139750397Sobrien for (arcptr = bb_graph[block].succ; arcptr; arcptr = arcptr->succ_next) 139850397Sobrien if (arcptr->on_tree && ! bb_graph[ARC_TARGET (arcptr)].on_tree) 139950397Sobrien expand_spanning_tree (ARC_TARGET (arcptr)); 140050397Sobrien 140150397Sobrien for (arcptr = bb_graph[block].pred; 140250397Sobrien arcptr; arcptr = arcptr->pred_next) 140350397Sobrien if (arcptr->on_tree && ! bb_graph[ARC_SOURCE (arcptr)].on_tree) 140450397Sobrien expand_spanning_tree (ARC_SOURCE (arcptr)); 140550397Sobrien} 140650397Sobrien 140750397Sobrien/* Perform file-level initialization for branch-prob processing. */ 140850397Sobrien 140950397Sobrienvoid 141050397Sobrieninit_branch_prob (filename) 141150397Sobrien char *filename; 141250397Sobrien{ 141350397Sobrien long len; 141450397Sobrien int i; 141550397Sobrien 141650397Sobrien if (flag_test_coverage) 141750397Sobrien { 141850397Sobrien /* Open an output file for the basic block/line number map. */ 141950397Sobrien int len = strlen (filename); 142050397Sobrien char *data_file = (char *) alloca (len + 4); 142150397Sobrien strcpy (data_file, filename); 142250397Sobrien strip_off_ending (data_file, len); 142350397Sobrien strcat (data_file, ".bb"); 142450397Sobrien if ((bb_file = fopen (data_file, "w")) == 0) 142550397Sobrien pfatal_with_name (data_file); 142650397Sobrien 142750397Sobrien /* Open an output file for the program flow graph. */ 142850397Sobrien len = strlen (filename); 142950397Sobrien bbg_file_name = (char *) alloca (len + 5); 143050397Sobrien strcpy (bbg_file_name, filename); 143150397Sobrien strip_off_ending (bbg_file_name, len); 143250397Sobrien strcat (bbg_file_name, ".bbg"); 143350397Sobrien if ((bbg_file = fopen (bbg_file_name, "w")) == 0) 143450397Sobrien pfatal_with_name (bbg_file_name); 143550397Sobrien 143650397Sobrien /* Initialize to zero, to ensure that the first file name will be 143750397Sobrien written to the .bb file. */ 143850397Sobrien last_bb_file_name = 0; 143950397Sobrien } 144050397Sobrien 144150397Sobrien if (flag_branch_probabilities) 144250397Sobrien { 144350397Sobrien len = strlen (filename); 144450397Sobrien da_file_name = (char *) alloca (len + 4); 144550397Sobrien strcpy (da_file_name, filename); 144650397Sobrien strip_off_ending (da_file_name, len); 144750397Sobrien strcat (da_file_name, ".da"); 144850397Sobrien if ((da_file = fopen (da_file_name, "r")) == 0) 144950397Sobrien warning ("file %s not found, execution counts assumed to be zero.", 145050397Sobrien da_file_name); 145150397Sobrien 145250397Sobrien /* The first word in the .da file gives the number of instrumented arcs, 145350397Sobrien which is not needed for our purposes. */ 145450397Sobrien 145550397Sobrien if (da_file) 145650397Sobrien __read_long (&len, da_file, 8); 145750397Sobrien } 145850397Sobrien 145950397Sobrien if (profile_arc_flag) 146050397Sobrien init_arc_profiler (); 146150397Sobrien 146250397Sobrien total_num_blocks = 0; 146350397Sobrien total_num_arcs = 0; 146450397Sobrien total_num_arcs_instrumented = 0; 146550397Sobrien total_num_blocks_created = 0; 146650397Sobrien total_num_passes = 0; 146750397Sobrien total_num_times_called = 0; 146850397Sobrien total_num_branches = 0; 146950397Sobrien total_num_never_executed = 0; 147050397Sobrien for (i = 0; i < 20; i++) 147150397Sobrien total_hist_br_prob[i] = 0; 147250397Sobrien} 147350397Sobrien 147450397Sobrien/* Performs file-level cleanup after branch-prob processing 147550397Sobrien is completed. */ 147650397Sobrien 147750397Sobrienvoid 147850397Sobrienend_branch_prob (dump_file) 147950397Sobrien FILE *dump_file; 148050397Sobrien{ 148150397Sobrien if (flag_test_coverage) 148250397Sobrien { 148350397Sobrien fclose (bb_file); 148450397Sobrien fclose (bbg_file); 148550397Sobrien } 148650397Sobrien 148750397Sobrien if (flag_branch_probabilities) 148850397Sobrien { 148950397Sobrien if (da_file) 149050397Sobrien { 149150397Sobrien long temp; 149250397Sobrien /* This seems slightly dangerous, as it presumes the EOF 149350397Sobrien flag will not be set until an attempt is made to read 149450397Sobrien past the end of the file. */ 149550397Sobrien if (feof (da_file)) 149650397Sobrien warning (".da file contents exhausted too early\n"); 149750397Sobrien /* Should be at end of file now. */ 149850397Sobrien if (__read_long (&temp, da_file, 8) == 0) 149950397Sobrien warning (".da file contents not exhausted\n"); 150050397Sobrien fclose (da_file); 150150397Sobrien } 150250397Sobrien } 150350397Sobrien 150450397Sobrien if (dump_file) 150550397Sobrien { 150650397Sobrien fprintf (dump_file, "\n"); 150750397Sobrien fprintf (dump_file, "Total number of blocks: %d\n", total_num_blocks); 150850397Sobrien fprintf (dump_file, "Total number of arcs: %d\n", total_num_arcs); 150950397Sobrien fprintf (dump_file, "Total number of instrumented arcs: %d\n", 151050397Sobrien total_num_arcs_instrumented); 151150397Sobrien fprintf (dump_file, "Total number of blocks created: %d\n", 151250397Sobrien total_num_blocks_created); 151350397Sobrien fprintf (dump_file, "Total number of graph solution passes: %d\n", 151450397Sobrien total_num_passes); 151550397Sobrien if (total_num_times_called != 0) 151650397Sobrien fprintf (dump_file, "Average number of graph solution passes: %d\n", 151750397Sobrien (total_num_passes + (total_num_times_called >> 1)) 151850397Sobrien / total_num_times_called); 151950397Sobrien fprintf (dump_file, "Total number of branches: %d\n", total_num_branches); 152050397Sobrien fprintf (dump_file, "Total number of branches never executed: %d\n", 152150397Sobrien total_num_never_executed); 152250397Sobrien if (total_num_branches) 152350397Sobrien { 152450397Sobrien int i; 152550397Sobrien 152650397Sobrien for (i = 0; i < 10; i++) 152750397Sobrien fprintf (dump_file, "%d%% branches in range %d-%d%%\n", 152850397Sobrien (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100 152950397Sobrien / total_num_branches, 5*i, 5*i+5); 153050397Sobrien } 153150397Sobrien } 153250397Sobrien} 153350397Sobrien 153450397Sobrien/* The label used by the arc profiling code. */ 153550397Sobrien 153650397Sobrienstatic rtx profiler_label; 153750397Sobrien 153850397Sobrien/* Initialize the profiler_label. */ 153950397Sobrien 154050397Sobrienstatic void 154150397Sobrieninit_arc_profiler () 154250397Sobrien{ 154350397Sobrien /* Generate and save a copy of this so it can be shared. */ 154450397Sobrien char *name = xmalloc (20); 154550397Sobrien ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 2); 154650397Sobrien profiler_label = gen_rtx_SYMBOL_REF (Pmode, name); 154750397Sobrien} 154850397Sobrien 154950397Sobrien/* Output instructions as RTL to increment the arc execution count. */ 155050397Sobrien 155150397Sobrienstatic void 155250397Sobrienoutput_arc_profiler (arcno, insert_after) 155350397Sobrien int arcno; 155450397Sobrien rtx insert_after; 155550397Sobrien{ 155650397Sobrien rtx profiler_target_addr 155750397Sobrien = (arcno 155850397Sobrien ? gen_rtx_CONST (Pmode, 155950397Sobrien gen_rtx_PLUS (Pmode, profiler_label, 156050397Sobrien GEN_INT (LONG_TYPE_SIZE / BITS_PER_UNIT * arcno))) 156150397Sobrien : profiler_label); 156250397Sobrien enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0); 156350397Sobrien rtx profiler_reg = gen_reg_rtx (mode); 156450397Sobrien rtx address_reg = gen_reg_rtx (Pmode); 156550397Sobrien rtx mem_ref, add_ref; 156650397Sobrien rtx sequence; 156750397Sobrien 156850397Sobrien /* In this case, reload can use explicitly mentioned hard registers for 156950397Sobrien reloads. It is not safe to output profiling code between a call 157050397Sobrien and the instruction that copies the result to a pseudo-reg. This 157150397Sobrien is because reload may allocate one of the profiling code pseudo-regs 157250397Sobrien to the return value reg, thus clobbering the return value. So we 157350397Sobrien must check for calls here, and emit the profiling code after the 157450397Sobrien instruction that uses the return value, if any. 157550397Sobrien 157650397Sobrien ??? The code here performs the same tests that reload does so hopefully 157750397Sobrien all the bases are covered. */ 157850397Sobrien 157950397Sobrien if (SMALL_REGISTER_CLASSES 158050397Sobrien && GET_CODE (insert_after) == CALL_INSN 158150397Sobrien && (GET_CODE (PATTERN (insert_after)) == SET 158250397Sobrien || (GET_CODE (PATTERN (insert_after)) == PARALLEL 158350397Sobrien && GET_CODE (XVECEXP (PATTERN (insert_after), 0, 0)) == SET))) 158450397Sobrien { 158550397Sobrien rtx return_reg; 158650397Sobrien rtx next_insert_after = next_nonnote_insn (insert_after); 158750397Sobrien 158850397Sobrien /* The first insn after the call may be a stack pop, skip it. */ 158950397Sobrien if (next_insert_after 159050397Sobrien && GET_CODE (next_insert_after) == INSN 159150397Sobrien && GET_CODE (PATTERN (next_insert_after)) == SET 159250397Sobrien && SET_DEST (PATTERN (next_insert_after)) == stack_pointer_rtx) 159350397Sobrien next_insert_after = next_nonnote_insn (next_insert_after); 159450397Sobrien 159550397Sobrien if (next_insert_after 159650397Sobrien && GET_CODE (next_insert_after) == INSN) 159750397Sobrien { 159850397Sobrien if (GET_CODE (PATTERN (insert_after)) == SET) 159950397Sobrien return_reg = SET_DEST (PATTERN (insert_after)); 160050397Sobrien else 160150397Sobrien return_reg = SET_DEST (XVECEXP (PATTERN (insert_after), 0, 0)); 160250397Sobrien 160350397Sobrien /* Now, NEXT_INSERT_AFTER may be an instruction that uses the 160450397Sobrien return value. However, it could also be something else, 160550397Sobrien like a CODE_LABEL, so check that the code is INSN. */ 160650397Sobrien if (next_insert_after != 0 160750397Sobrien && GET_RTX_CLASS (GET_CODE (next_insert_after)) == 'i' 160850397Sobrien && reg_referenced_p (return_reg, PATTERN (next_insert_after))) 160950397Sobrien insert_after = next_insert_after; 161050397Sobrien } 161150397Sobrien } 161250397Sobrien 161350397Sobrien start_sequence (); 161450397Sobrien 161550397Sobrien emit_move_insn (address_reg, profiler_target_addr); 161650397Sobrien mem_ref = gen_rtx_MEM (mode, address_reg); 161750397Sobrien emit_move_insn (profiler_reg, mem_ref); 161850397Sobrien 161950397Sobrien add_ref = gen_rtx_PLUS (mode, profiler_reg, GEN_INT (1)); 162050397Sobrien emit_move_insn (profiler_reg, add_ref); 162150397Sobrien 162250397Sobrien /* This is the same rtx as above, but it is not legal to share this rtx. */ 162350397Sobrien mem_ref = gen_rtx_MEM (mode, address_reg); 162450397Sobrien emit_move_insn (mem_ref, profiler_reg); 162550397Sobrien 162650397Sobrien sequence = gen_sequence (); 162750397Sobrien end_sequence (); 162850397Sobrien emit_insn_after (sequence, insert_after); 162950397Sobrien} 163050397Sobrien 163150397Sobrien/* Output code for a constructor that will invoke __bb_init_func, if 163250397Sobrien this has not already been done. */ 163350397Sobrien 163450397Sobrienvoid 163550397Sobrienoutput_func_start_profiler () 163650397Sobrien{ 163750397Sobrien tree fnname, fndecl; 163850397Sobrien char *name, *cfnname; 163950397Sobrien rtx table_address; 164050397Sobrien enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0); 164150397Sobrien int save_flag_inline_functions = flag_inline_functions; 164250397Sobrien 164350397Sobrien /* It's either already been output, or we don't need it because we're 164450397Sobrien not doing profile-arcs. */ 164550397Sobrien if (! need_func_profiler) 164650397Sobrien return; 164750397Sobrien 164850397Sobrien need_func_profiler = 0; 164950397Sobrien 165050397Sobrien /* Synthesize a constructor function to invoke __bb_init_func with a 165150397Sobrien pointer to this object file's profile block. */ 165250397Sobrien start_sequence (); 165350397Sobrien 165450397Sobrien /* Try and make a unique name given the "file function name". 165550397Sobrien 165650397Sobrien And no, I don't like this either. */ 165750397Sobrien 165850397Sobrien fnname = get_file_function_name ('I'); 165950397Sobrien cfnname = IDENTIFIER_POINTER (fnname); 166050397Sobrien name = xmalloc (strlen (cfnname) + 5); 166150397Sobrien sprintf (name, "%sGCOV",cfnname); 166250397Sobrien fnname = get_identifier (name); 166350397Sobrien free (name); 166450397Sobrien 166550397Sobrien fndecl = build_decl (FUNCTION_DECL, fnname, 166650397Sobrien build_function_type (void_type_node, NULL_TREE)); 166750397Sobrien DECL_EXTERNAL (fndecl) = 0; 166850397Sobrien TREE_PUBLIC (fndecl) = 1; 166950397Sobrien DECL_ASSEMBLER_NAME (fndecl) = fnname; 167050397Sobrien DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node); 167150397Sobrien current_function_decl = fndecl; 167250397Sobrien pushlevel (0); 167350397Sobrien make_function_rtl (fndecl); 167450397Sobrien init_function_start (fndecl, input_filename, lineno); 167550397Sobrien expand_function_start (fndecl, 0); 167650397Sobrien 167750397Sobrien /* Actually generate the code to call __bb_init_func. */ 167850397Sobrien name = xmalloc (20); 167950397Sobrien ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 0); 168050397Sobrien table_address = force_reg (Pmode, gen_rtx_SYMBOL_REF (Pmode, name)); 168150397Sobrien emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), 0, 168250397Sobrien mode, 1, table_address, Pmode); 168350397Sobrien 168450397Sobrien expand_function_end (input_filename, lineno, 0); 168550397Sobrien poplevel (1, 0, 1); 168650397Sobrien 168750397Sobrien /* Since fndecl isn't in the list of globals, it would never be emitted 168850397Sobrien when it's considered to be 'safe' for inlining, so turn off 168950397Sobrien flag_inline_functions. */ 169050397Sobrien flag_inline_functions = 0; 169150397Sobrien 169250397Sobrien rest_of_compilation (fndecl); 169350397Sobrien 169450397Sobrien /* Reset flag_inline_functions to its original value. */ 169550397Sobrien flag_inline_functions = save_flag_inline_functions; 169650397Sobrien 169750397Sobrien if (! quiet_flag) 169850397Sobrien fflush (asm_out_file); 169950397Sobrien current_function_decl = NULL_TREE; 170050397Sobrien 170150397Sobrien assemble_constructor (IDENTIFIER_POINTER (DECL_NAME (fndecl))); 170250397Sobrien} 1703