profile.c revision 90075
185556Siwasaki/* Calculate branch probabilities, and basic block execution counts. 285556Siwasaki Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999, 385556Siwasaki 2000, 2001 Free Software Foundation, Inc. 485556Siwasaki Contributed by James E. Wilson, UC Berkeley/Cygnus Support; 585556Siwasaki based on some ideas from Dain Samples of UC Berkeley. 685556Siwasaki Further mangling by Bob Manson, Cygnus Support. 785556Siwasaki 885556SiwasakiThis file is part of GCC. 985556Siwasaki 1085556SiwasakiGCC is free software; you can redistribute it and/or modify it under 1185556Siwasakithe terms of the GNU General Public License as published by the Free 1285556SiwasakiSoftware Foundation; either version 2, or (at your option) any later 1385556Siwasakiversion. 1485556Siwasaki 1585556SiwasakiGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1685556SiwasakiWARRANTY; without even the implied warranty of MERCHANTABILITY or 1785556SiwasakiFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1885556Siwasakifor more details. 1985556Siwasaki 2085556SiwasakiYou should have received a copy of the GNU General Public License 2185556Siwasakialong with GCC; see the file COPYING. If not, write to the Free 2285556SiwasakiSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2385556Siwasaki02111-1307, USA. */ 2485556Siwasaki 2585556Siwasaki/* ??? Register allocation should use basic block execution counts to 2685556Siwasaki give preference to the most commonly executed blocks. */ 2785556Siwasaki 2885556Siwasaki/* ??? The .da files are not safe. Changing the program after creating .da 2985556Siwasaki files or using different options when compiling with -fbranch-probabilities 3085556Siwasaki can result the arc data not matching the program. Maybe add instrumented 3185556Siwasaki arc count to .bbg file? Maybe check whether PFG matches the .bbg file? */ 3285556Siwasaki 3385556Siwasaki/* ??? Should calculate branch probabilities before instrumenting code, since 3485556Siwasaki then we can use arc counts to help decide which arcs to instrument. */ 3585556Siwasaki 3685556Siwasaki#include "config.h" 3785556Siwasaki#include "system.h" 3885556Siwasaki#include "rtl.h" 3985556Siwasaki#include "tree.h" 4085556Siwasaki#include "flags.h" 4185556Siwasaki#include "insn-config.h" 4285556Siwasaki#include "output.h" 4385556Siwasaki#include "regs.h" 4485556Siwasaki#include "expr.h" 4585556Siwasaki#include "function.h" 46105276Sjhb#include "toplev.h" 47105276Sjhb#include "ggc.h" 48105276Sjhb#include "hard-reg-set.h" 4985556Siwasaki#include "basic-block.h" 50105276Sjhb#include "gcov-io.h" 5185556Siwasaki#include "target.h" 5285556Siwasaki 5385556Siwasaki/* Additional information about the edges we need. */ 5485556Siwasakistruct edge_info 5585556Siwasaki { 5685556Siwasaki unsigned int count_valid : 1; 5785556Siwasaki unsigned int on_tree : 1; 5885556Siwasaki unsigned int ignore : 1; 5985556Siwasaki }; 6085556Siwasakistruct bb_info 6185556Siwasaki { 6285556Siwasaki unsigned int count_valid : 1; 6385556Siwasaki gcov_type succ_count; 6485556Siwasaki gcov_type pred_count; 6585556Siwasaki }; 6685556Siwasaki 67111815Sphk#define EDGE_INFO(e) ((struct edge_info *) (e)->aux) 68111815Sphk#define BB_INFO(b) ((struct bb_info *) (b)->aux) 69111815Sphk 70111815Sphk/* Keep all basic block indexes nonnegative in the gcov output. Index 0 71111815Sphk is used for entry block, last block exit block. */ 72111815Sphk#define GCOV_INDEX_TO_BB(i) ((i) == 0 ? ENTRY_BLOCK_PTR \ 73111815Sphk : (((i) == n_basic_blocks + 1) \ 7485556Siwasaki ? EXIT_BLOCK_PTR : BASIC_BLOCK ((i)-1))) 7585556Siwasaki#define BB_TO_GCOV_INDEX(bb) ((bb) == ENTRY_BLOCK_PTR ? 0 \ 7685556Siwasaki : ((bb) == EXIT_BLOCK_PTR \ 7785556Siwasaki ? n_basic_blocks + 1 : (bb)->index + 1)) 7885556Siwasaki 7985556Siwasaki/* Name and file pointer of the output file for the basic block graph. */ 8085556Siwasaki 8185556Siwasakistatic FILE *bbg_file; 8285556Siwasaki 8385556Siwasaki/* Name and file pointer of the input file for the arc count data. */ 8485556Siwasaki 8585556Siwasakistatic FILE *da_file; 8685556Siwasaki 8785556Siwasaki/* Pointer of the output file for the basic block/line number map. */ 8885556Siwasakistatic FILE *bb_file; 8985556Siwasaki 9085556Siwasaki/* Last source file name written to bb_file. */ 9185556Siwasaki 9285556Siwasakistatic char *last_bb_file_name; 9385556Siwasaki 9485556Siwasaki/* Used by final, for allocating the proper amount of storage for the 9585556Siwasaki instrumented arc execution counts. */ 9685556Siwasaki 9785556Siwasakiint count_instrumented_edges; 9885556Siwasaki 9985556Siwasaki/* Collect statistics on the performance of this pass for the entire source 10085556Siwasaki file. */ 10185556Siwasaki 10285556Siwasakistatic int total_num_blocks; 10385556Siwasakistatic int total_num_edges; 10485556Siwasakistatic int total_num_edges_ignored; 10585556Siwasakistatic int total_num_edges_instrumented; 10685556Siwasakistatic int total_num_blocks_created; 10785556Siwasakistatic int total_num_passes; 10885556Siwasakistatic int total_num_times_called; 10985556Siwasakistatic int total_hist_br_prob[20]; 11085556Siwasakistatic int total_num_never_executed; 11185556Siwasakistatic int total_num_branches; 11285556Siwasaki 11385556Siwasaki/* Forward declarations. */ 11485556Siwasakistatic void find_spanning_tree PARAMS ((struct edge_list *)); 11585556Siwasakistatic void init_edge_profiler PARAMS ((void)); 11685556Siwasakistatic rtx gen_edge_profiler PARAMS ((int)); 11785556Siwasakistatic void instrument_edges PARAMS ((struct edge_list *)); 11885556Siwasakistatic void output_gcov_string PARAMS ((const char *, long)); 11985556Siwasakistatic void compute_branch_probabilities PARAMS ((void)); 12085556Siwasakistatic basic_block find_group PARAMS ((basic_block)); 12185556Siwasakistatic void union_groups PARAMS ((basic_block, basic_block)); 12285556Siwasaki 12385556Siwasaki/* If non-zero, we need to output a constructor to set up the 12485556Siwasaki per-object-file data. */ 12585556Siwasakistatic int need_func_profiler = 0; 12685556Siwasaki 12785556Siwasaki/* Add edge instrumentation code to the entire insn chain. 12885556Siwasaki 12985556Siwasaki F is the first insn of the chain. 13085556Siwasaki NUM_BLOCKS is the number of basic blocks found in F. */ 13185556Siwasaki 13285556Siwasakistatic void 13385556Siwasakiinstrument_edges (el) 13485556Siwasaki struct edge_list *el; 13585556Siwasaki{ 13685556Siwasaki int i; 13785556Siwasaki int num_instr_edges = 0; 13885556Siwasaki int num_edges = NUM_EDGES (el); 13985556Siwasaki remove_fake_edges (); 14085556Siwasaki 14185556Siwasaki for (i = 0; i < n_basic_blocks + 2; i++) 14285556Siwasaki { 14385556Siwasaki basic_block bb = GCOV_INDEX_TO_BB (i); 14485556Siwasaki edge e = bb->succ; 14585556Siwasaki while (e) 14685556Siwasaki { 14785556Siwasaki struct edge_info *inf = EDGE_INFO (e); 14885556Siwasaki if (!inf->ignore && !inf->on_tree) 14985556Siwasaki { 15085556Siwasaki if (e->flags & EDGE_ABNORMAL) 15185556Siwasaki abort (); 15285556Siwasaki if (rtl_dump_file) 15385556Siwasaki fprintf (rtl_dump_file, "Edge %d to %d instrumented%s\n", 15485556Siwasaki e->src->index, e->dest->index, 15585556Siwasaki EDGE_CRITICAL_P (e) ? " (and split)" : ""); 15685556Siwasaki need_func_profiler = 1; 15785556Siwasaki insert_insn_on_edge ( 15885556Siwasaki gen_edge_profiler (total_num_edges_instrumented 15985556Siwasaki + num_instr_edges++), e); 16085556Siwasaki } 16185556Siwasaki e = e->succ_next; 16285556Siwasaki } 16385556Siwasaki } 16485556Siwasaki 16585556Siwasaki total_num_edges_instrumented += num_instr_edges; 16685556Siwasaki count_instrumented_edges = total_num_edges_instrumented; 16785556Siwasaki 16885556Siwasaki total_num_blocks_created += num_edges; 16985556Siwasaki if (rtl_dump_file) 17085556Siwasaki fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges); 17185556Siwasaki 17285556Siwasaki commit_edge_insertions (); 17385556Siwasaki} 17485556Siwasaki 17585556Siwasaki/* Output STRING to bb_file, surrounded by DELIMITER. */ 17685556Siwasaki 17785556Siwasakistatic void 17885556Siwasakioutput_gcov_string (string, delimiter) 17985556Siwasaki const char *string; 18085556Siwasaki long delimiter; 18185556Siwasaki{ 18285556Siwasaki long temp; 18385556Siwasaki 18485556Siwasaki /* Write a delimiter to indicate that a file name follows. */ 18585556Siwasaki __write_long (delimiter, bb_file, 4); 18685556Siwasaki 18785556Siwasaki /* Write the string. */ 18885556Siwasaki temp = strlen (string) + 1; 18985556Siwasaki fwrite (string, temp, 1, bb_file); 19085556Siwasaki 19185556Siwasaki /* Append a few zeros, to align the output to a 4 byte boundary. */ 19285556Siwasaki temp = temp & 0x3; 19385556Siwasaki if (temp) 19485556Siwasaki { 195104727Sjhb char c[4]; 19685556Siwasaki 19785556Siwasaki c[0] = c[1] = c[2] = c[3] = 0; 19885556Siwasaki fwrite (c, sizeof (char), 4 - temp, bb_file); 19985556Siwasaki } 20085556Siwasaki 201104727Sjhb /* Store another delimiter in the .bb file, just to make it easy to find 20285556Siwasaki the end of the file name. */ 20385556Siwasaki __write_long (delimiter, bb_file, 4); 20485556Siwasaki} 20585556Siwasaki 20685556Siwasaki 207104727Sjhb/* Compute the branch probabilities for the various branches. 20885556Siwasaki Annotate them accordingly. */ 20985556Siwasaki 21085556Siwasakistatic void 21185556Siwasakicompute_branch_probabilities () 21285556Siwasaki{ 21385556Siwasaki int i; 21485556Siwasaki int num_edges = 0; 21585556Siwasaki int changes; 21685556Siwasaki int passes; 21785556Siwasaki int hist_br_prob[20]; 21885556Siwasaki int num_never_executed; 21985556Siwasaki int num_branches; 22085556Siwasaki 22185556Siwasaki /* Attach extra info block to each bb. */ 22285556Siwasaki 22385556Siwasaki alloc_aux_for_blocks (sizeof (struct bb_info)); 22485556Siwasaki for (i = 0; i < n_basic_blocks + 2; i++) 22585556Siwasaki { 22685556Siwasaki basic_block bb = GCOV_INDEX_TO_BB (i); 22785556Siwasaki edge e; 22885556Siwasaki 22985556Siwasaki for (e = bb->succ; e; e = e->succ_next) 23085556Siwasaki if (!EDGE_INFO (e)->ignore) 23185556Siwasaki BB_INFO (bb)->succ_count++; 23285556Siwasaki for (e = bb->pred; e; e = e->pred_next) 23385556Siwasaki if (!EDGE_INFO (e)->ignore) 23485556Siwasaki BB_INFO (bb)->pred_count++; 23585556Siwasaki } 23685556Siwasaki 23785556Siwasaki /* Avoid predicting entry on exit nodes. */ 23885556Siwasaki BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2; 23985556Siwasaki BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2; 24085556Siwasaki 24185556Siwasaki /* For each edge not on the spanning tree, set its execution count from 24285556Siwasaki the .da file. */ 24385556Siwasaki 24485556Siwasaki /* The first count in the .da file is the number of times that the function 24585556Siwasaki was entered. This is the exec_count for block zero. */ 24685556Siwasaki 24785556Siwasaki for (i = 0; i < n_basic_blocks + 2; i++) 24885556Siwasaki { 24985556Siwasaki basic_block bb = GCOV_INDEX_TO_BB (i); 25085556Siwasaki edge e; 25185556Siwasaki for (e = bb->succ; e; e = e->succ_next) 25285556Siwasaki if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree) 25385556Siwasaki { 25485556Siwasaki num_edges++; 25585556Siwasaki if (da_file) 25685556Siwasaki { 25785556Siwasaki gcov_type value; 25885556Siwasaki __read_gcov_type (&value, da_file, 8); 25985556Siwasaki e->count = value; 26085556Siwasaki } 26185556Siwasaki else 26285556Siwasaki e->count = 0; 26385556Siwasaki EDGE_INFO (e)->count_valid = 1; 26485556Siwasaki BB_INFO (bb)->succ_count--; 26585556Siwasaki BB_INFO (e->dest)->pred_count--; 26685556Siwasaki if (rtl_dump_file) 26785556Siwasaki { 26885556Siwasaki fprintf (rtl_dump_file, "\nRead edge from %i to %i, count:", 26985556Siwasaki bb->index, e->dest->index); 27085556Siwasaki fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC, 27185556Siwasaki (HOST_WIDEST_INT) e->count); 27285556Siwasaki } 27385556Siwasaki } 27485556Siwasaki } 27585556Siwasaki 27685556Siwasaki if (rtl_dump_file) 27785556Siwasaki fprintf (rtl_dump_file, "\n%d edge counts read\n", num_edges); 27885556Siwasaki 27985556Siwasaki /* For every block in the file, 28085556Siwasaki - if every exit/entrance edge has a known count, then set the block count 28185556Siwasaki - if the block count is known, and every exit/entrance edge but one has 28285556Siwasaki a known execution count, then set the count of the remaining edge 28385556Siwasaki 28485556Siwasaki As edge counts are set, decrement the succ/pred count, but don't delete 28585556Siwasaki the edge, that way we can easily tell when all edges are known, or only 28685556Siwasaki one edge is unknown. */ 28785556Siwasaki 28885556Siwasaki /* The order that the basic blocks are iterated through is important. 28985556Siwasaki Since the code that finds spanning trees starts with block 0, low numbered 29085556Siwasaki edges are put on the spanning tree in preference to high numbered edges. 29185556Siwasaki Hence, most instrumented edges are at the end. Graph solving works much 29285556Siwasaki faster if we propagate numbers from the end to the start. 29385556Siwasaki 29485556Siwasaki This takes an average of slightly more than 3 passes. */ 29585556Siwasaki 29685556Siwasaki changes = 1; 29785556Siwasaki passes = 0; 29885556Siwasaki while (changes) 29985556Siwasaki { 30085556Siwasaki passes++; 30185556Siwasaki changes = 0; 30285556Siwasaki for (i = n_basic_blocks + 1; i >= 0; i--) 30385556Siwasaki { 30485556Siwasaki basic_block bb = GCOV_INDEX_TO_BB (i); 305104727Sjhb struct bb_info *bi = BB_INFO (bb); 30685556Siwasaki if (! bi->count_valid) 30785556Siwasaki { 30885556Siwasaki if (bi->succ_count == 0) 30985556Siwasaki { 31085556Siwasaki edge e; 31185556Siwasaki gcov_type total = 0; 31285556Siwasaki 31385556Siwasaki for (e = bb->succ; e; e = e->succ_next) 31485556Siwasaki total += e->count; 31585556Siwasaki bb->count = total; 31685556Siwasaki bi->count_valid = 1; 31785556Siwasaki changes = 1; 31885556Siwasaki } 31985556Siwasaki else if (bi->pred_count == 0) 32085556Siwasaki { 32185556Siwasaki edge e; 32285556Siwasaki gcov_type total = 0; 32385556Siwasaki 32485556Siwasaki for (e = bb->pred; e; e = e->pred_next) 32585556Siwasaki total += e->count; 32685556Siwasaki bb->count = total; 327104223Sjhb bi->count_valid = 1; 328104223Sjhb changes = 1; 329104223Sjhb } 330104223Sjhb } 331104223Sjhb if (bi->count_valid) 332104223Sjhb { 33385556Siwasaki if (bi->succ_count == 1) 33485556Siwasaki { 33585556Siwasaki edge e; 33685556Siwasaki gcov_type total = 0; 337107144Sjhb 338103023Sjhb /* One of the counts will be invalid, but it is zero, 339103023Sjhb so adding it in also doesn't hurt. */ 34085556Siwasaki for (e = bb->succ; e; e = e->succ_next) 34185556Siwasaki total += e->count; 34285556Siwasaki 343 /* Seedgeh for the invalid edge, and set its count. */ 344 for (e = bb->succ; e; e = e->succ_next) 345 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) 346 break; 347 348 /* Calculate count for remaining edge by conservation. */ 349 total = bb->count - total; 350 351 if (! e) 352 abort (); 353 EDGE_INFO (e)->count_valid = 1; 354 e->count = total; 355 bi->succ_count--; 356 357 BB_INFO (e->dest)->pred_count--; 358 changes = 1; 359 } 360 if (bi->pred_count == 1) 361 { 362 edge e; 363 gcov_type total = 0; 364 365 /* One of the counts will be invalid, but it is zero, 366 so adding it in also doesn't hurt. */ 367 for (e = bb->pred; e; e = e->pred_next) 368 total += e->count; 369 370 /* Seedgeh for the invalid edge, and set its count. */ 371 for (e = bb->pred; e; e = e->pred_next) 372 if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore) 373 break; 374 375 /* Calculate count for remaining edge by conservation. */ 376 total = bb->count - total + e->count; 377 378 if (! e) 379 abort (); 380 EDGE_INFO (e)->count_valid = 1; 381 e->count = total; 382 bi->pred_count--; 383 384 BB_INFO (e->src)->succ_count--; 385 changes = 1; 386 } 387 } 388 } 389 } 390 if (rtl_dump_file) 391 dump_flow_info (rtl_dump_file); 392 393 total_num_passes += passes; 394 if (rtl_dump_file) 395 fprintf (rtl_dump_file, "Graph solving took %d passes.\n\n", passes); 396 397 /* If the graph has been correctly solved, every block will have a 398 succ and pred count of zero. */ 399 for (i = 0; i < n_basic_blocks; i++) 400 { 401 basic_block bb = BASIC_BLOCK (i); 402 if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count) 403 abort (); 404 } 405 406 /* For every edge, calculate its branch probability and add a reg_note 407 to the branch insn to indicate this. */ 408 409 for (i = 0; i < 20; i++) 410 hist_br_prob[i] = 0; 411 num_never_executed = 0; 412 num_branches = 0; 413 414 for (i = 0; i <= n_basic_blocks + 1; i++) 415 { 416 basic_block bb = GCOV_INDEX_TO_BB (i); 417 edge e; 418 gcov_type total; 419 rtx note; 420 421 total = bb->count; 422 if (total) 423 { 424 for (e = bb->succ; e; e = e->succ_next) 425 { 426 e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total; 427 if (e->probability < 0 || e->probability > REG_BR_PROB_BASE) 428 { 429 error ("corrupted profile info: prob for %d-%d thought to be %d", 430 e->src->index, e->dest->index, e->probability); 431 e->probability = REG_BR_PROB_BASE / 2; 432 } 433 } 434 if (bb->index >= 0 435 && any_condjump_p (bb->end) 436 && bb->succ->succ_next) 437 { 438 int prob; 439 edge e; 440 int index; 441 442 /* Find the branch edge. It is possible that we do have fake 443 edges here. */ 444 for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU); 445 e = e->succ_next) 446 continue; /* Loop body has been intentionally left blank. */ 447 448 prob = e->probability; 449 index = prob * 20 / REG_BR_PROB_BASE; 450 451 if (index == 20) 452 index = 19; 453 hist_br_prob[index]++; 454 455 note = find_reg_note (bb->end, REG_BR_PROB, 0); 456 /* There may be already note put by some other pass, such 457 as builtin_expect expander. */ 458 if (note) 459 XEXP (note, 0) = GEN_INT (prob); 460 else 461 REG_NOTES (bb->end) 462 = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob), 463 REG_NOTES (bb->end)); 464 num_branches++; 465 } 466 } 467 /* Otherwise distribute the probabilities evenly so we get sane sum. 468 Use simple heuristics that if there are normal edges, give all abnormals 469 frequency of 0, otherwise distribute the frequency over abnormals 470 (this is the case of noreturn calls). */ 471 else 472 { 473 for (e = bb->succ; e; e = e->succ_next) 474 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 475 total ++; 476 if (total) 477 { 478 for (e = bb->succ; e; e = e->succ_next) 479 if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE))) 480 e->probability = REG_BR_PROB_BASE / total; 481 else 482 e->probability = 0; 483 } 484 else 485 { 486 for (e = bb->succ; e; e = e->succ_next) 487 total ++; 488 for (e = bb->succ; e; e = e->succ_next) 489 e->probability = REG_BR_PROB_BASE / total; 490 } 491 if (bb->index >= 0 492 && any_condjump_p (bb->end) 493 && bb->succ->succ_next) 494 num_branches++, num_never_executed; 495 } 496 } 497 498 if (rtl_dump_file) 499 { 500 fprintf (rtl_dump_file, "%d branches\n", num_branches); 501 fprintf (rtl_dump_file, "%d branches never executed\n", 502 num_never_executed); 503 if (num_branches) 504 for (i = 0; i < 10; i++) 505 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n", 506 (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches, 507 5 * i, 5 * i + 5); 508 509 total_num_branches += num_branches; 510 total_num_never_executed += num_never_executed; 511 for (i = 0; i < 20; i++) 512 total_hist_br_prob[i] += hist_br_prob[i]; 513 514 fputc ('\n', rtl_dump_file); 515 fputc ('\n', rtl_dump_file); 516 } 517 518 free_aux_for_blocks (); 519} 520 521/* Instrument and/or analyze program behavior based on program flow graph. 522 In either case, this function builds a flow graph for the function being 523 compiled. The flow graph is stored in BB_GRAPH. 524 525 When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in 526 the flow graph that are needed to reconstruct the dynamic behavior of the 527 flow graph. 528 529 When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary 530 information from a data file containing edge count information from previous 531 executions of the function being compiled. In this case, the flow graph is 532 annotated with actual execution counts, which are later propagated into the 533 rtl for optimization purposes. 534 535 Main entry point of this file. */ 536 537void 538branch_prob () 539{ 540 int i; 541 int num_edges, ignored_edges; 542 struct edge_list *el; 543 544 /* Start of a function. */ 545 if (flag_test_coverage) 546 output_gcov_string (current_function_name, (long) -2); 547 548 total_num_times_called++; 549 550 flow_call_edges_add (NULL); 551 add_noreturn_fake_exit_edges (); 552 553 /* We can't handle cyclic regions constructed using abnormal edges. 554 To avoid these we replace every source of abnormal edge by a fake 555 edge from entry node and every destination by fake edge to exit. 556 This keeps graph acyclic and our calculation exact for all normal 557 edges except for exit and entrance ones. 558 559 We also add fake exit edges for each call and asm statement in the 560 basic, since it may not return. */ 561 562 for (i = 0; i < n_basic_blocks ; i++) 563 { 564 int need_exit_edge = 0, need_entry_edge = 0; 565 int have_exit_edge = 0, have_entry_edge = 0; 566 basic_block bb = BASIC_BLOCK (i); 567 rtx insn; 568 edge e; 569 570 /* Add fake edges from entry block to the call insns that may return 571 twice. The CFG is not quite correct then, as call insn plays more 572 role of CODE_LABEL, but for our purposes, everything should be OK, 573 as we never insert code to the beggining of basic block. */ 574 for (insn = bb->head; insn != NEXT_INSN (bb->end); 575 insn = NEXT_INSN (insn)) 576 { 577 if (GET_CODE (insn) == CALL_INSN 578 && find_reg_note (insn, REG_SETJMP, NULL)) 579 { 580 if (GET_CODE (bb->head) == CODE_LABEL 581 || insn != NEXT_INSN (bb->head)) 582 { 583 e = split_block (bb, PREV_INSN (insn)); 584 make_edge (ENTRY_BLOCK_PTR, e->dest, EDGE_FAKE); 585 break; 586 } 587 else 588 { 589 /* We should not get abort here, as call to setjmp should not 590 be the very first instruction of function. */ 591 if (!i) 592 abort (); 593 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE); 594 } 595 } 596 } 597 598 for (e = bb->succ; e; e = e->succ_next) 599 { 600 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 601 && e->dest != EXIT_BLOCK_PTR) 602 need_exit_edge = 1; 603 if (e->dest == EXIT_BLOCK_PTR) 604 have_exit_edge = 1; 605 } 606 for (e = bb->pred; e; e = e->pred_next) 607 { 608 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 609 && e->src != ENTRY_BLOCK_PTR) 610 need_entry_edge = 1; 611 if (e->src == ENTRY_BLOCK_PTR) 612 have_entry_edge = 1; 613 } 614 615 if (need_exit_edge && !have_exit_edge) 616 { 617 if (rtl_dump_file) 618 fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n", 619 bb->index); 620 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 621 } 622 if (need_entry_edge && !have_entry_edge) 623 { 624 if (rtl_dump_file) 625 fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n", 626 bb->index); 627 make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE); 628 } 629 } 630 631 el = create_edge_list (); 632 num_edges = NUM_EDGES (el); 633 alloc_aux_for_edges (sizeof (struct edge_info)); 634 635 ignored_edges = 0; 636 for (i = 0 ; i < num_edges ; i++) 637 { 638 edge e = INDEX_EDGE (el, i); 639 e->count = 0; 640 641 /* Mark edges we've replaced by fake edges above as ignored. */ 642 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL)) 643 && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR) 644 { 645 EDGE_INFO (e)->ignore = 1; 646 ignored_edges++; 647 } 648 } 649 650#ifdef ENABLE_CHECKING 651 verify_flow_info (); 652#endif 653 654 /* Output line number information about each basic block for 655 GCOV utility. */ 656 if (flag_test_coverage) 657 { 658 int i = 0; 659 for (i = 0 ; i < n_basic_blocks; i++) 660 { 661 basic_block bb = BASIC_BLOCK (i); 662 rtx insn = bb->head; 663 static int ignore_next_note = 0; 664 665 /* We are looking for line number notes. Search backward before 666 basic block to find correct ones. */ 667 insn = prev_nonnote_insn (insn); 668 if (!insn) 669 insn = get_insns (); 670 else 671 insn = NEXT_INSN (insn); 672 673 /* Output a zero to the .bb file to indicate that a new 674 block list is starting. */ 675 __write_long (0, bb_file, 4); 676 677 while (insn != bb->end) 678 { 679 if (GET_CODE (insn) == NOTE) 680 { 681 /* Must ignore the line number notes that immediately 682 follow the end of an inline function to avoid counting 683 it twice. There is a note before the call, and one 684 after the call. */ 685 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER) 686 ignore_next_note = 1; 687 else if (NOTE_LINE_NUMBER (insn) > 0) 688 { 689 if (ignore_next_note) 690 ignore_next_note = 0; 691 else 692 { 693 /* If this is a new source file, then output the 694 file's name to the .bb file. */ 695 if (! last_bb_file_name 696 || strcmp (NOTE_SOURCE_FILE (insn), 697 last_bb_file_name)) 698 { 699 if (last_bb_file_name) 700 free (last_bb_file_name); 701 last_bb_file_name 702 = xstrdup (NOTE_SOURCE_FILE (insn)); 703 output_gcov_string (NOTE_SOURCE_FILE (insn), 704 (long)-1); 705 } 706 /* Output the line number to the .bb file. Must be 707 done after the output_bb_profile_data() call, and 708 after the file name is written, to ensure that it 709 is correctly handled by gcov. */ 710 __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4); 711 } 712 } 713 } 714 insn = NEXT_INSN (insn); 715 } 716 } 717 __write_long (0, bb_file, 4); 718 } 719 720 /* Create spanning tree from basic block graph, mark each edge that is 721 on the spanning tree. We insert as many abnormal and critical edges 722 as possible to minimize number of edge splits necessary. */ 723 724 find_spanning_tree (el); 725 726 /* Fake edges that are not on the tree will not be instrumented, so 727 mark them ignored. */ 728 for (i = 0; i < num_edges; i++) 729 { 730 edge e = INDEX_EDGE (el, i); 731 struct edge_info *inf = EDGE_INFO (e); 732 if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree) 733 { 734 inf->ignore = 1; 735 ignored_edges++; 736 } 737 } 738 739 total_num_blocks += n_basic_blocks + 2; 740 if (rtl_dump_file) 741 fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks); 742 743 total_num_edges += num_edges; 744 if (rtl_dump_file) 745 fprintf (rtl_dump_file, "%d edges\n", num_edges); 746 747 total_num_edges_ignored += ignored_edges; 748 if (rtl_dump_file) 749 fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges); 750 751 /* Create a .bbg file from which gcov can reconstruct the basic block 752 graph. First output the number of basic blocks, and then for every 753 edge output the source and target basic block numbers. 754 NOTE: The format of this file must be compatible with gcov. */ 755 756 if (flag_test_coverage) 757 { 758 int flag_bits; 759 760 /* The plus 2 stands for entry and exit block. */ 761 __write_long (n_basic_blocks + 2, bbg_file, 4); 762 __write_long (num_edges - ignored_edges + 1, bbg_file, 4); 763 764 for (i = 0; i < n_basic_blocks + 1; i++) 765 { 766 basic_block bb = GCOV_INDEX_TO_BB (i); 767 edge e; 768 long count = 0; 769 770 for (e = bb->succ; e; e = e->succ_next) 771 if (!EDGE_INFO (e)->ignore) 772 count++; 773 __write_long (count, bbg_file, 4); 774 775 for (e = bb->succ; e; e = e->succ_next) 776 { 777 struct edge_info *i = EDGE_INFO (e); 778 if (!i->ignore) 779 { 780 flag_bits = 0; 781 if (i->on_tree) 782 flag_bits |= 0x1; 783 if (e->flags & EDGE_FAKE) 784 flag_bits |= 0x2; 785 if (e->flags & EDGE_FALLTHRU) 786 flag_bits |= 0x4; 787 788 __write_long (BB_TO_GCOV_INDEX (e->dest), bbg_file, 4); 789 __write_long (flag_bits, bbg_file, 4); 790 } 791 } 792 } 793 /* Emit fake loopback edge for EXIT block to maintain compatibility with 794 old gcov format. */ 795 __write_long (1, bbg_file, 4); 796 __write_long (0, bbg_file, 4); 797 __write_long (0x1, bbg_file, 4); 798 799 /* Emit a -1 to separate the list of all edges from the list of 800 loop back edges that follows. */ 801 __write_long (-1, bbg_file, 4); 802 } 803 804 if (flag_branch_probabilities) 805 compute_branch_probabilities (); 806 807 /* For each edge not on the spanning tree, add counting code as rtl. */ 808 809 if (profile_arc_flag) 810 { 811 instrument_edges (el); 812 allocate_reg_info (max_reg_num (), FALSE, FALSE); 813 } 814 815 remove_fake_edges (); 816 /* Re-merge split basic blocks and the mess introduced by 817 insert_insn_on_edge. */ 818 cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0); 819 if (rtl_dump_file) 820 dump_flow_info (rtl_dump_file); 821 822 free_aux_for_edges (); 823 free_edge_list (el); 824} 825 826/* Union find algorithm implementation for the basic blocks using 827 aux fields. */ 828 829static basic_block 830find_group (bb) 831 basic_block bb; 832{ 833 basic_block group = bb, bb1; 834 835 while ((basic_block) group->aux != group) 836 group = (basic_block) group->aux; 837 838 /* Compress path. */ 839 while ((basic_block) bb->aux != group) 840 { 841 bb1 = (basic_block) bb->aux; 842 bb->aux = (void *) group; 843 bb = bb1; 844 } 845 return group; 846} 847 848static void 849union_groups (bb1, bb2) 850 basic_block bb1, bb2; 851{ 852 basic_block bb1g = find_group (bb1); 853 basic_block bb2g = find_group (bb2); 854 855 /* ??? I don't have a place for the rank field. OK. Lets go w/o it, 856 this code is unlikely going to be performance problem anyway. */ 857 if (bb1g == bb2g) 858 abort (); 859 860 bb1g->aux = bb2g; 861} 862 863/* This function searches all of the edges in the program flow graph, and puts 864 as many bad edges as possible onto the spanning tree. Bad edges include 865 abnormals edges, which can't be instrumented at the moment. Since it is 866 possible for fake edges to form an cycle, we will have to develop some 867 better way in the future. Also put critical edges to the tree, since they 868 are more expensive to instrument. */ 869 870static void 871find_spanning_tree (el) 872 struct edge_list *el; 873{ 874 int i; 875 int num_edges = NUM_EDGES (el); 876 877 /* We use aux field for standard union-find algorithm. */ 878 EXIT_BLOCK_PTR->aux = EXIT_BLOCK_PTR; 879 ENTRY_BLOCK_PTR->aux = ENTRY_BLOCK_PTR; 880 for (i = 0; i < n_basic_blocks; i++) 881 BASIC_BLOCK (i)->aux = BASIC_BLOCK (i); 882 883 /* Add fake edge exit to entry we can't instrument. */ 884 union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR); 885 886 /* First add all abnormal edges to the tree unless they form an cycle. */ 887 for (i = 0; i < num_edges; i++) 888 { 889 edge e = INDEX_EDGE (el, i); 890 if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE)) 891 && !EDGE_INFO (e)->ignore 892 && (find_group (e->src) != find_group (e->dest))) 893 { 894 EDGE_INFO (e)->on_tree = 1; 895 union_groups (e->src, e->dest); 896 } 897 } 898 899 /* Now insert all critical edges to the tree unless they form an cycle. */ 900 for (i = 0; i < num_edges; i++) 901 { 902 edge e = INDEX_EDGE (el, i); 903 if ((EDGE_CRITICAL_P (e)) 904 && !EDGE_INFO (e)->ignore 905 && (find_group (e->src) != find_group (e->dest))) 906 { 907 EDGE_INFO (e)->on_tree = 1; 908 union_groups (e->src, e->dest); 909 } 910 } 911 912 /* And now the rest. */ 913 for (i = 0; i < num_edges; i++) 914 { 915 edge e = INDEX_EDGE (el, i); 916 if (find_group (e->src) != find_group (e->dest) 917 && !EDGE_INFO (e)->ignore) 918 { 919 EDGE_INFO (e)->on_tree = 1; 920 union_groups (e->src, e->dest); 921 } 922 } 923 924 EXIT_BLOCK_PTR->aux = NULL; 925 ENTRY_BLOCK_PTR->aux = NULL; 926 for (i = 0; i < n_basic_blocks; i++) 927 BASIC_BLOCK (i)->aux = NULL; 928} 929 930/* Perform file-level initialization for branch-prob processing. */ 931 932void 933init_branch_prob (filename) 934 const char *filename; 935{ 936 long len; 937 int i; 938 939 if (flag_test_coverage) 940 { 941 int len = strlen (filename); 942 char *data_file, *bbg_file_name; 943 944 /* Open an output file for the basic block/line number map. */ 945 data_file = (char *) alloca (len + 4); 946 strcpy (data_file, filename); 947 strip_off_ending (data_file, len); 948 strcat (data_file, ".bb"); 949 if ((bb_file = fopen (data_file, "wb")) == 0) 950 fatal_io_error ("can't open %s", data_file); 951 952 /* Open an output file for the program flow graph. */ 953 bbg_file_name = (char *) alloca (len + 5); 954 strcpy (bbg_file_name, filename); 955 strip_off_ending (bbg_file_name, len); 956 strcat (bbg_file_name, ".bbg"); 957 if ((bbg_file = fopen (bbg_file_name, "wb")) == 0) 958 fatal_io_error ("can't open %s", bbg_file_name); 959 960 /* Initialize to zero, to ensure that the first file name will be 961 written to the .bb file. */ 962 last_bb_file_name = 0; 963 } 964 965 if (flag_branch_probabilities) 966 { 967 char *da_file_name; 968 969 len = strlen (filename); 970 da_file_name = (char *) alloca (len + 4); 971 strcpy (da_file_name, filename); 972 strip_off_ending (da_file_name, len); 973 strcat (da_file_name, ".da"); 974 if ((da_file = fopen (da_file_name, "rb")) == 0) 975 warning ("file %s not found, execution counts assumed to be zero", 976 da_file_name); 977 978 /* The first word in the .da file gives the number of instrumented 979 edges, which is not needed for our purposes. */ 980 981 if (da_file) 982 __read_long (&len, da_file, 8); 983 } 984 985 if (profile_arc_flag) 986 init_edge_profiler (); 987 988 total_num_blocks = 0; 989 total_num_edges = 0; 990 total_num_edges_ignored = 0; 991 total_num_edges_instrumented = 0; 992 total_num_blocks_created = 0; 993 total_num_passes = 0; 994 total_num_times_called = 0; 995 total_num_branches = 0; 996 total_num_never_executed = 0; 997 for (i = 0; i < 20; i++) 998 total_hist_br_prob[i] = 0; 999} 1000 1001/* Performs file-level cleanup after branch-prob processing 1002 is completed. */ 1003 1004void 1005end_branch_prob () 1006{ 1007 if (flag_test_coverage) 1008 { 1009 fclose (bb_file); 1010 fclose (bbg_file); 1011 } 1012 1013 if (flag_branch_probabilities) 1014 { 1015 if (da_file) 1016 { 1017 long temp; 1018 /* This seems slightly dangerous, as it presumes the EOF 1019 flag will not be set until an attempt is made to read 1020 past the end of the file. */ 1021 if (feof (da_file)) 1022 error (".da file contents exhausted too early"); 1023 /* Should be at end of file now. */ 1024 if (__read_long (&temp, da_file, 8) == 0) 1025 error (".da file contents not exhausted"); 1026 fclose (da_file); 1027 } 1028 } 1029 1030 if (rtl_dump_file) 1031 { 1032 fprintf (rtl_dump_file, "\n"); 1033 fprintf (rtl_dump_file, "Total number of blocks: %d\n", 1034 total_num_blocks); 1035 fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges); 1036 fprintf (rtl_dump_file, "Total number of ignored edges: %d\n", 1037 total_num_edges_ignored); 1038 fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n", 1039 total_num_edges_instrumented); 1040 fprintf (rtl_dump_file, "Total number of blocks created: %d\n", 1041 total_num_blocks_created); 1042 fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n", 1043 total_num_passes); 1044 if (total_num_times_called != 0) 1045 fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n", 1046 (total_num_passes + (total_num_times_called >> 1)) 1047 / total_num_times_called); 1048 fprintf (rtl_dump_file, "Total number of branches: %d\n", 1049 total_num_branches); 1050 fprintf (rtl_dump_file, "Total number of branches never executed: %d\n", 1051 total_num_never_executed); 1052 if (total_num_branches) 1053 { 1054 int i; 1055 1056 for (i = 0; i < 10; i++) 1057 fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n", 1058 (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100 1059 / total_num_branches, 5*i, 5*i+5); 1060 } 1061 } 1062} 1063 1064/* The label used by the edge profiling code. */ 1065 1066static rtx profiler_label; 1067 1068/* Initialize the profiler_label. */ 1069 1070static void 1071init_edge_profiler () 1072{ 1073 /* Generate and save a copy of this so it can be shared. */ 1074 char buf[20]; 1075 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2); 1076 profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf)); 1077 ggc_add_rtx_root (&profiler_label, 1); 1078} 1079 1080/* Output instructions as RTL to increment the edge execution count. */ 1081 1082static rtx 1083gen_edge_profiler (edgeno) 1084 int edgeno; 1085{ 1086 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0); 1087 rtx mem_ref, tmp; 1088 rtx sequence; 1089 1090 start_sequence (); 1091 1092 tmp = force_reg (Pmode, profiler_label); 1093 tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno); 1094 mem_ref = validize_mem (gen_rtx_MEM (mode, tmp)); 1095 1096 tmp = expand_simple_binop (mode, PLUS, mem_ref, const1_rtx, 1097 mem_ref, 0, OPTAB_WIDEN); 1098 1099 if (tmp != mem_ref) 1100 emit_move_insn (copy_rtx (mem_ref), tmp); 1101 1102 sequence = gen_sequence (); 1103 end_sequence (); 1104 return sequence; 1105} 1106 1107/* Output code for a constructor that will invoke __bb_init_func, if 1108 this has not already been done. */ 1109 1110void 1111output_func_start_profiler () 1112{ 1113 tree fnname, fndecl; 1114 char *name; 1115 char buf[20]; 1116 const char *cfnname; 1117 rtx table_address; 1118 enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0); 1119 int save_flag_inline_functions = flag_inline_functions; 1120 int save_flag_test_coverage = flag_test_coverage; 1121 int save_profile_arc_flag = profile_arc_flag; 1122 int save_flag_branch_probabilities = flag_branch_probabilities; 1123 1124 /* It's either already been output, or we don't need it because we're 1125 not doing profile-edges. */ 1126 if (! need_func_profiler) 1127 return; 1128 1129 need_func_profiler = 0; 1130 1131 /* Synthesize a constructor function to invoke __bb_init_func with a 1132 pointer to this object file's profile block. */ 1133 1134 /* Try and make a unique name given the "file function name". 1135 1136 And no, I don't like this either. */ 1137 1138 fnname = get_file_function_name ('I'); 1139 cfnname = IDENTIFIER_POINTER (fnname); 1140 name = concat (cfnname, "GCOV", NULL); 1141 fnname = get_identifier (name); 1142 free (name); 1143 1144 fndecl = build_decl (FUNCTION_DECL, fnname, 1145 build_function_type (void_type_node, NULL_TREE)); 1146 DECL_EXTERNAL (fndecl) = 0; 1147 1148 /* It can be a static function as long as collect2 does not have 1149 to scan the object file to find its ctor/dtor routine. */ 1150 TREE_PUBLIC (fndecl) = ! targetm.have_ctors_dtors; 1151 1152 TREE_USED (fndecl) = 1; 1153 1154 DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node); 1155 1156 fndecl = pushdecl (fndecl); 1157 rest_of_decl_compilation (fndecl, 0, 1, 0); 1158 announce_function (fndecl); 1159 current_function_decl = fndecl; 1160 DECL_INITIAL (fndecl) = error_mark_node; 1161 make_decl_rtl (fndecl, NULL); 1162 init_function_start (fndecl, input_filename, lineno); 1163 pushlevel (0); 1164 expand_function_start (fndecl, 0); 1165 1166 /* Actually generate the code to call __bb_init_func. */ 1167 ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 0); 1168 table_address = force_reg (Pmode, 1169 gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf))); 1170 emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), LCT_NORMAL, 1171 mode, 1, table_address, Pmode); 1172 1173 expand_function_end (input_filename, lineno, 0); 1174 poplevel (1, 0, 1); 1175 1176 /* Since fndecl isn't in the list of globals, it would never be emitted 1177 when it's considered to be 'safe' for inlining, so turn off 1178 flag_inline_functions. */ 1179 flag_inline_functions = 0; 1180 1181 /* Don't instrument the function that turns on instrumentation. Which 1182 is also handy since we'd get silly warnings about not consuming all 1183 of our da_file input. */ 1184 flag_test_coverage = 0; 1185 profile_arc_flag = 0; 1186 flag_branch_probabilities = 0; 1187 1188 rest_of_compilation (fndecl); 1189 1190 /* Reset flag_inline_functions to its original value. */ 1191 flag_inline_functions = save_flag_inline_functions; 1192 flag_test_coverage = save_flag_test_coverage; 1193 profile_arc_flag = save_profile_arc_flag; 1194 flag_branch_probabilities = save_flag_branch_probabilities; 1195 1196 if (! quiet_flag) 1197 fflush (asm_out_file); 1198 current_function_decl = NULL_TREE; 1199 1200 if (targetm.have_ctors_dtors) 1201 (* targetm.asm_out.constructor) (XEXP (DECL_RTL (fndecl), 0), 1202 DEFAULT_INIT_PRIORITY); 1203} 1204