1/* Transformations based on profile information for values. 2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software 3 Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "rtl.h" 26#include "expr.h" 27#include "hard-reg-set.h" 28#include "basic-block.h" 29#include "value-prof.h" 30#include "output.h" 31#include "flags.h" 32#include "insn-config.h" 33#include "recog.h" 34#include "optabs.h" 35#include "regs.h" 36#include "ggc.h" 37#include "tree-flow.h" 38#include "tree-flow-inline.h" 39#include "diagnostic.h" 40#include "coverage.h" 41#include "tree.h" 42#include "gcov-io.h" 43#include "cgraph.h" 44#include "timevar.h" 45#include "tree-pass.h" 46#include "toplev.h" 47#include "pointer-set.h" 48 49static struct value_prof_hooks *value_prof_hooks; 50 51/* In this file value profile based optimizations are placed. Currently the 52 following optimizations are implemented (for more detailed descriptions 53 see comments at value_profile_transformations): 54 55 1) Division/modulo specialization. Provided that we can determine that the 56 operands of the division have some special properties, we may use it to 57 produce more effective code. 58 2) Speculative prefetching. If we are able to determine that the difference 59 between addresses accessed by a memory reference is usually constant, we 60 may add the prefetch instructions. 61 FIXME: This transformation was removed together with RTL based value 62 profiling. 63 64 3) Indirect/virtual call specialization. If we can determine most 65 common function callee in indirect/virtual call. We can use this 66 information to improve code effectiveness (especially info for 67 inliner). 68 69 Every such optimization should add its requirements for profiled values to 70 insn_values_to_profile function. This function is called from branch_prob 71 in profile.c and the requested values are instrumented by it in the first 72 compilation with -fprofile-arcs. The optimization may then read the 73 gathered data in the second compilation with -fbranch-probabilities. 74 75 The measured data is pointed to from the histograms 76 field of the statement annotation of the instrumented insns. It is 77 kept as a linked list of struct histogram_value_t's, which contain the 78 same information as above. */ 79 80 81static tree gimple_divmod_fixed_value (gimple, tree, int, gcov_type, gcov_type); 82static tree gimple_mod_pow2 (gimple, int, gcov_type, gcov_type); 83static tree gimple_mod_subtract (gimple, int, int, int, gcov_type, gcov_type, 84 gcov_type); 85static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *); 86static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *); 87static bool gimple_mod_subtract_transform (gimple_stmt_iterator *); 88static bool gimple_stringops_transform (gimple_stmt_iterator *); 89static bool gimple_ic_transform (gimple); 90 91/* Allocate histogram value. */ 92 93static histogram_value 94gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED, 95 enum hist_type type, gimple stmt, tree value) 96{ 97 histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist)); 98 hist->hvalue.value = value; 99 hist->hvalue.stmt = stmt; 100 hist->type = type; 101 return hist; 102} 103 104/* Hash value for histogram. */ 105 106static hashval_t 107histogram_hash (const void *x) 108{ 109 return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt); 110} 111 112/* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */ 113 114static int 115histogram_eq (const void *x, const void *y) 116{ 117 return ((const_histogram_value) x)->hvalue.stmt == (const_gimple) y; 118} 119 120/* Set histogram for STMT. */ 121 122static void 123set_histogram_value (struct function *fun, gimple stmt, histogram_value hist) 124{ 125 void **loc; 126 if (!hist && !VALUE_HISTOGRAMS (fun)) 127 return; 128 if (!VALUE_HISTOGRAMS (fun)) 129 VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash, 130 histogram_eq, NULL); 131 loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt, 132 htab_hash_pointer (stmt), 133 hist ? INSERT : NO_INSERT); 134 if (!hist) 135 { 136 if (loc) 137 htab_clear_slot (VALUE_HISTOGRAMS (fun), loc); 138 return; 139 } 140 *loc = hist; 141} 142 143/* Get histogram list for STMT. */ 144 145histogram_value 146gimple_histogram_value (struct function *fun, gimple stmt) 147{ 148 if (!VALUE_HISTOGRAMS (fun)) 149 return NULL; 150 return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt, 151 htab_hash_pointer (stmt)); 152} 153 154/* Add histogram for STMT. */ 155 156void 157gimple_add_histogram_value (struct function *fun, gimple stmt, 158 histogram_value hist) 159{ 160 hist->hvalue.next = gimple_histogram_value (fun, stmt); 161 set_histogram_value (fun, stmt, hist); 162} 163 164 165/* Remove histogram HIST from STMT's histogram list. */ 166 167void 168gimple_remove_histogram_value (struct function *fun, gimple stmt, 169 histogram_value hist) 170{ 171 histogram_value hist2 = gimple_histogram_value (fun, stmt); 172 if (hist == hist2) 173 { 174 set_histogram_value (fun, stmt, hist->hvalue.next); 175 } 176 else 177 { 178 while (hist2->hvalue.next != hist) 179 hist2 = hist2->hvalue.next; 180 hist2->hvalue.next = hist->hvalue.next; 181 } 182 free (hist->hvalue.counters); 183#ifdef ENABLE_CHECKING 184 memset (hist, 0xab, sizeof (*hist)); 185#endif 186 free (hist); 187} 188 189 190/* Lookup histogram of type TYPE in the STMT. */ 191 192histogram_value 193gimple_histogram_value_of_type (struct function *fun, gimple stmt, 194 enum hist_type type) 195{ 196 histogram_value hist; 197 for (hist = gimple_histogram_value (fun, stmt); hist; 198 hist = hist->hvalue.next) 199 if (hist->type == type) 200 return hist; 201 return NULL; 202} 203 204/* Dump information about HIST to DUMP_FILE. */ 205 206static void 207dump_histogram_value (FILE *dump_file, histogram_value hist) 208{ 209 switch (hist->type) 210 { 211 case HIST_TYPE_INTERVAL: 212 fprintf (dump_file, "Interval counter range %d -- %d", 213 hist->hdata.intvl.int_start, 214 (hist->hdata.intvl.int_start 215 + hist->hdata.intvl.steps - 1)); 216 if (hist->hvalue.counters) 217 { 218 unsigned int i; 219 fprintf(dump_file, " ["); 220 for (i = 0; i < hist->hdata.intvl.steps; i++) 221 fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC, 222 hist->hdata.intvl.int_start + i, 223 (HOST_WIDEST_INT) hist->hvalue.counters[i]); 224 fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC, 225 (HOST_WIDEST_INT) hist->hvalue.counters[i]); 226 } 227 fprintf (dump_file, ".\n"); 228 break; 229 230 case HIST_TYPE_POW2: 231 fprintf (dump_file, "Pow2 counter "); 232 if (hist->hvalue.counters) 233 { 234 fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC 235 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC, 236 (HOST_WIDEST_INT) hist->hvalue.counters[0], 237 (HOST_WIDEST_INT) hist->hvalue.counters[1]); 238 } 239 fprintf (dump_file, ".\n"); 240 break; 241 242 case HIST_TYPE_SINGLE_VALUE: 243 fprintf (dump_file, "Single value "); 244 if (hist->hvalue.counters) 245 { 246 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC 247 " match:"HOST_WIDEST_INT_PRINT_DEC 248 " wrong:"HOST_WIDEST_INT_PRINT_DEC, 249 (HOST_WIDEST_INT) hist->hvalue.counters[0], 250 (HOST_WIDEST_INT) hist->hvalue.counters[1], 251 (HOST_WIDEST_INT) hist->hvalue.counters[2]); 252 } 253 fprintf (dump_file, ".\n"); 254 break; 255 256 case HIST_TYPE_AVERAGE: 257 fprintf (dump_file, "Average value "); 258 if (hist->hvalue.counters) 259 { 260 fprintf (dump_file, "sum:"HOST_WIDEST_INT_PRINT_DEC 261 " times:"HOST_WIDEST_INT_PRINT_DEC, 262 (HOST_WIDEST_INT) hist->hvalue.counters[0], 263 (HOST_WIDEST_INT) hist->hvalue.counters[1]); 264 } 265 fprintf (dump_file, ".\n"); 266 break; 267 268 case HIST_TYPE_IOR: 269 fprintf (dump_file, "IOR value "); 270 if (hist->hvalue.counters) 271 { 272 fprintf (dump_file, "ior:"HOST_WIDEST_INT_PRINT_DEC, 273 (HOST_WIDEST_INT) hist->hvalue.counters[0]); 274 } 275 fprintf (dump_file, ".\n"); 276 break; 277 278 case HIST_TYPE_CONST_DELTA: 279 fprintf (dump_file, "Constant delta "); 280 if (hist->hvalue.counters) 281 { 282 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC 283 " match:"HOST_WIDEST_INT_PRINT_DEC 284 " wrong:"HOST_WIDEST_INT_PRINT_DEC, 285 (HOST_WIDEST_INT) hist->hvalue.counters[0], 286 (HOST_WIDEST_INT) hist->hvalue.counters[1], 287 (HOST_WIDEST_INT) hist->hvalue.counters[2]); 288 } 289 fprintf (dump_file, ".\n"); 290 break; 291 case HIST_TYPE_INDIR_CALL: 292 fprintf (dump_file, "Indirect call "); 293 if (hist->hvalue.counters) 294 { 295 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC 296 " match:"HOST_WIDEST_INT_PRINT_DEC 297 " all:"HOST_WIDEST_INT_PRINT_DEC, 298 (HOST_WIDEST_INT) hist->hvalue.counters[0], 299 (HOST_WIDEST_INT) hist->hvalue.counters[1], 300 (HOST_WIDEST_INT) hist->hvalue.counters[2]); 301 } 302 fprintf (dump_file, ".\n"); 303 break; 304 } 305} 306 307/* Dump all histograms attached to STMT to DUMP_FILE. */ 308 309void 310dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple stmt) 311{ 312 histogram_value hist; 313 for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next) 314 dump_histogram_value (dump_file, hist); 315} 316 317/* Remove all histograms associated with STMT. */ 318 319void 320gimple_remove_stmt_histograms (struct function *fun, gimple stmt) 321{ 322 histogram_value val; 323 while ((val = gimple_histogram_value (fun, stmt)) != NULL) 324 gimple_remove_histogram_value (fun, stmt, val); 325} 326 327/* Duplicate all histograms associates with OSTMT to STMT. */ 328 329void 330gimple_duplicate_stmt_histograms (struct function *fun, gimple stmt, 331 struct function *ofun, gimple ostmt) 332{ 333 histogram_value val; 334 for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next) 335 { 336 histogram_value new_val = gimple_alloc_histogram_value (fun, val->type, NULL, NULL); 337 memcpy (new_val, val, sizeof (*val)); 338 new_val->hvalue.stmt = stmt; 339 new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters); 340 memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters); 341 gimple_add_histogram_value (fun, stmt, new_val); 342 } 343} 344 345 346/* Move all histograms associated with OSTMT to STMT. */ 347 348void 349gimple_move_stmt_histograms (struct function *fun, gimple stmt, gimple ostmt) 350{ 351 histogram_value val = gimple_histogram_value (fun, ostmt); 352 if (val) 353 { 354 /* The following three statements can't be reordered, 355 because histogram hashtab relies on stmt field value 356 for finding the exact slot. */ 357 set_histogram_value (fun, ostmt, NULL); 358 for (; val != NULL; val = val->hvalue.next) 359 val->hvalue.stmt = stmt; 360 set_histogram_value (fun, stmt, val); 361 } 362} 363 364static bool error_found = false; 365 366/* Helper function for verify_histograms. For each histogram reachable via htab 367 walk verify that it was reached via statement walk. */ 368 369static int 370visit_hist (void **slot, void *data) 371{ 372 struct pointer_set_t *visited = (struct pointer_set_t *) data; 373 histogram_value hist = *(histogram_value *) slot; 374 if (!pointer_set_contains (visited, hist)) 375 { 376 error ("Dead histogram"); 377 dump_histogram_value (stderr, hist); 378 debug_gimple_stmt (hist->hvalue.stmt); 379 error_found = true; 380 } 381 return 1; 382} 383 384 385/* Verify sanity of the histograms. */ 386 387void 388verify_histograms (void) 389{ 390 basic_block bb; 391 gimple_stmt_iterator gsi; 392 histogram_value hist; 393 struct pointer_set_t *visited_hists; 394 395 error_found = false; 396 visited_hists = pointer_set_create (); 397 FOR_EACH_BB (bb) 398 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 399 { 400 gimple stmt = gsi_stmt (gsi); 401 402 for (hist = gimple_histogram_value (cfun, stmt); hist; 403 hist = hist->hvalue.next) 404 { 405 if (hist->hvalue.stmt != stmt) 406 { 407 error ("Histogram value statement does not correspond to " 408 "the statement it is associated with"); 409 debug_gimple_stmt (stmt); 410 dump_histogram_value (stderr, hist); 411 error_found = true; 412 } 413 pointer_set_insert (visited_hists, hist); 414 } 415 } 416 if (VALUE_HISTOGRAMS (cfun)) 417 htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists); 418 pointer_set_destroy (visited_hists); 419 if (error_found) 420 internal_error ("verify_histograms failed"); 421} 422 423/* Helper function for verify_histograms. For each histogram reachable via htab 424 walk verify that it was reached via statement walk. */ 425 426static int 427free_hist (void **slot, void *data ATTRIBUTE_UNUSED) 428{ 429 histogram_value hist = *(histogram_value *) slot; 430 free (hist->hvalue.counters); 431#ifdef ENABLE_CHECKING 432 memset (hist, 0xab, sizeof (*hist)); 433#endif 434 free (hist); 435 return 1; 436} 437 438void 439free_histograms (void) 440{ 441 if (VALUE_HISTOGRAMS (cfun)) 442 { 443 htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL); 444 htab_delete (VALUE_HISTOGRAMS (cfun)); 445 VALUE_HISTOGRAMS (cfun) = NULL; 446 } 447} 448 449 450/* The overall number of invocations of the counter should match 451 execution count of basic block. Report it as error rather than 452 internal error as it might mean that user has misused the profile 453 somehow. */ 454 455static bool 456check_counter (gimple stmt, const char * name, 457 gcov_type *count, gcov_type *all, gcov_type bb_count) 458{ 459 if (*all != bb_count || *count > *all) 460 { 461 location_t locus; 462 locus = (stmt != NULL) 463 ? gimple_location (stmt) 464 : DECL_SOURCE_LOCATION (current_function_decl); 465 if (flag_profile_correction) 466 { 467 inform (locus, "Correcting inconsistent value profile: " 468 "%s profiler overall count (%d) does not match BB count " 469 "(%d)", name, (int)*all, (int)bb_count); 470 *all = bb_count; 471 if (*count > *all) 472 *count = *all; 473 return false; 474 } 475 else 476 { 477 error_at (locus, "Corrupted value profile: %s " 478 "profiler overall count (%d) does not match BB count (%d)", 479 name, (int)*all, (int)bb_count); 480 return true; 481 } 482 } 483 484 return false; 485} 486 487 488/* GIMPLE based transformations. */ 489 490static bool 491gimple_value_profile_transformations (void) 492{ 493 basic_block bb; 494 gimple_stmt_iterator gsi; 495 bool changed = false; 496 497 FOR_EACH_BB (bb) 498 { 499 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 500 { 501 gimple stmt = gsi_stmt (gsi); 502 histogram_value th = gimple_histogram_value (cfun, stmt); 503 if (!th) 504 continue; 505 506 if (dump_file) 507 { 508 fprintf (dump_file, "Trying transformations on stmt "); 509 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 510 dump_histograms_for_stmt (cfun, dump_file, stmt); 511 } 512 513 /* Transformations: */ 514 /* The order of things in this conditional controls which 515 transformation is used when more than one is applicable. */ 516 /* It is expected that any code added by the transformations 517 will be added before the current statement, and that the 518 current statement remain valid (although possibly 519 modified) upon return. */ 520 if (flag_value_profile_transformations 521 && (gimple_mod_subtract_transform (&gsi) 522 || gimple_divmod_fixed_value_transform (&gsi) 523 || gimple_mod_pow2_value_transform (&gsi) 524 || gimple_stringops_transform (&gsi) 525 || gimple_ic_transform (stmt))) 526 { 527 stmt = gsi_stmt (gsi); 528 changed = true; 529 /* Original statement may no longer be in the same block. */ 530 if (bb != gimple_bb (stmt)) 531 { 532 bb = gimple_bb (stmt); 533 gsi = gsi_for_stmt (stmt); 534 } 535 } 536 } 537 } 538 539 if (changed) 540 { 541 counts_to_freqs (); 542 } 543 544 return changed; 545} 546 547 548/* Generate code for transformation 1 (with parent gimple assignment 549 STMT and probability of taking the optimal path PROB, which is 550 equivalent to COUNT/ALL within roundoff error). This generates the 551 result into a temp and returns the temp; it does not replace or 552 alter the original STMT. */ 553 554static tree 555gimple_divmod_fixed_value (gimple stmt, tree value, int prob, gcov_type count, 556 gcov_type all) 557{ 558 gimple stmt1, stmt2, stmt3; 559 tree tmp1, tmp2, tmpv; 560 gimple bb1end, bb2end, bb3end; 561 basic_block bb, bb2, bb3, bb4; 562 tree optype, op1, op2; 563 edge e12, e13, e23, e24, e34; 564 gimple_stmt_iterator gsi; 565 566 gcc_assert (is_gimple_assign (stmt) 567 && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR 568 || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR)); 569 570 optype = TREE_TYPE (gimple_assign_lhs (stmt)); 571 op1 = gimple_assign_rhs1 (stmt); 572 op2 = gimple_assign_rhs2 (stmt); 573 574 bb = gimple_bb (stmt); 575 gsi = gsi_for_stmt (stmt); 576 577 tmpv = create_tmp_var (optype, "PROF"); 578 tmp1 = create_tmp_var (optype, "PROF"); 579 stmt1 = gimple_build_assign (tmpv, fold_convert (optype, value)); 580 stmt2 = gimple_build_assign (tmp1, op2); 581 stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE); 582 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); 583 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT); 584 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT); 585 bb1end = stmt3; 586 587 tmp2 = create_tmp_var (optype, "PROF"); 588 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2, 589 op1, tmpv); 590 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); 591 bb2end = stmt1; 592 593 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2, 594 op1, op2); 595 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); 596 bb3end = stmt1; 597 598 /* Fix CFG. */ 599 /* Edge e23 connects bb2 to bb3, etc. */ 600 e12 = split_block (bb, bb1end); 601 bb2 = e12->dest; 602 bb2->count = count; 603 e23 = split_block (bb2, bb2end); 604 bb3 = e23->dest; 605 bb3->count = all - count; 606 e34 = split_block (bb3, bb3end); 607 bb4 = e34->dest; 608 bb4->count = all; 609 610 e12->flags &= ~EDGE_FALLTHRU; 611 e12->flags |= EDGE_FALSE_VALUE; 612 e12->probability = prob; 613 e12->count = count; 614 615 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); 616 e13->probability = REG_BR_PROB_BASE - prob; 617 e13->count = all - count; 618 619 remove_edge (e23); 620 621 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); 622 e24->probability = REG_BR_PROB_BASE; 623 e24->count = count; 624 625 e34->probability = REG_BR_PROB_BASE; 626 e34->count = all - count; 627 628 return tmp2; 629} 630 631 632/* Do transform 1) on INSN if applicable. */ 633 634static bool 635gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si) 636{ 637 histogram_value histogram; 638 enum tree_code code; 639 gcov_type val, count, all; 640 tree result, value, tree_val; 641 gcov_type prob; 642 gimple stmt; 643 644 stmt = gsi_stmt (*si); 645 if (gimple_code (stmt) != GIMPLE_ASSIGN) 646 return false; 647 648 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))) 649 return false; 650 651 code = gimple_assign_rhs_code (stmt); 652 653 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR) 654 return false; 655 656 histogram = gimple_histogram_value_of_type (cfun, stmt, 657 HIST_TYPE_SINGLE_VALUE); 658 if (!histogram) 659 return false; 660 661 value = histogram->hvalue.value; 662 val = histogram->hvalue.counters[0]; 663 count = histogram->hvalue.counters[1]; 664 all = histogram->hvalue.counters[2]; 665 gimple_remove_histogram_value (cfun, stmt, histogram); 666 667 /* We require that count is at least half of all; this means 668 that for the transformation to fire the value must be constant 669 at least 50% of time (and 75% gives the guarantee of usage). */ 670 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1 671 || 2 * count < all 672 || optimize_bb_for_size_p (gimple_bb (stmt))) 673 return false; 674 675 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count)) 676 return false; 677 678 /* Compute probability of taking the optimal path. */ 679 if (all > 0) 680 prob = (count * REG_BR_PROB_BASE + all / 2) / all; 681 else 682 prob = 0; 683 684 tree_val = build_int_cst_wide (get_gcov_type (), 685 (unsigned HOST_WIDE_INT) val, 686 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1); 687 result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all); 688 689 if (dump_file) 690 { 691 fprintf (dump_file, "Div/mod by constant "); 692 print_generic_expr (dump_file, value, TDF_SLIM); 693 fprintf (dump_file, "="); 694 print_generic_expr (dump_file, tree_val, TDF_SLIM); 695 fprintf (dump_file, " transformation on insn "); 696 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 697 } 698 699 gimple_assign_set_rhs_from_tree (si, result); 700 701 return true; 702} 703 704/* Generate code for transformation 2 (with parent gimple assign STMT and 705 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL 706 within roundoff error). This generates the result into a temp and returns 707 the temp; it does not replace or alter the original STMT. */ 708static tree 709gimple_mod_pow2 (gimple stmt, int prob, gcov_type count, gcov_type all) 710{ 711 gimple stmt1, stmt2, stmt3, stmt4; 712 tree tmp2, tmp3; 713 gimple bb1end, bb2end, bb3end; 714 basic_block bb, bb2, bb3, bb4; 715 tree optype, op1, op2; 716 edge e12, e13, e23, e24, e34; 717 gimple_stmt_iterator gsi; 718 tree result; 719 720 gcc_assert (is_gimple_assign (stmt) 721 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR); 722 723 optype = TREE_TYPE (gimple_assign_lhs (stmt)); 724 op1 = gimple_assign_rhs1 (stmt); 725 op2 = gimple_assign_rhs2 (stmt); 726 727 bb = gimple_bb (stmt); 728 gsi = gsi_for_stmt (stmt); 729 730 result = create_tmp_var (optype, "PROF"); 731 tmp2 = create_tmp_var (optype, "PROF"); 732 tmp3 = create_tmp_var (optype, "PROF"); 733 stmt2 = gimple_build_assign_with_ops (PLUS_EXPR, tmp2, op2, 734 build_int_cst (optype, -1)); 735 stmt3 = gimple_build_assign_with_ops (BIT_AND_EXPR, tmp3, tmp2, op2); 736 stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0), 737 NULL_TREE, NULL_TREE); 738 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT); 739 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT); 740 gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT); 741 bb1end = stmt4; 742 743 /* tmp2 == op2-1 inherited from previous block. */ 744 stmt1 = gimple_build_assign_with_ops (BIT_AND_EXPR, result, op1, tmp2); 745 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); 746 bb2end = stmt1; 747 748 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result, 749 op1, op2); 750 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); 751 bb3end = stmt1; 752 753 /* Fix CFG. */ 754 /* Edge e23 connects bb2 to bb3, etc. */ 755 e12 = split_block (bb, bb1end); 756 bb2 = e12->dest; 757 bb2->count = count; 758 e23 = split_block (bb2, bb2end); 759 bb3 = e23->dest; 760 bb3->count = all - count; 761 e34 = split_block (bb3, bb3end); 762 bb4 = e34->dest; 763 bb4->count = all; 764 765 e12->flags &= ~EDGE_FALLTHRU; 766 e12->flags |= EDGE_FALSE_VALUE; 767 e12->probability = prob; 768 e12->count = count; 769 770 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE); 771 e13->probability = REG_BR_PROB_BASE - prob; 772 e13->count = all - count; 773 774 remove_edge (e23); 775 776 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU); 777 e24->probability = REG_BR_PROB_BASE; 778 e24->count = count; 779 780 e34->probability = REG_BR_PROB_BASE; 781 e34->count = all - count; 782 783 return result; 784} 785 786/* Do transform 2) on INSN if applicable. */ 787static bool 788gimple_mod_pow2_value_transform (gimple_stmt_iterator *si) 789{ 790 histogram_value histogram; 791 enum tree_code code; 792 gcov_type count, wrong_values, all; 793 tree lhs_type, result, value; 794 gcov_type prob; 795 gimple stmt; 796 797 stmt = gsi_stmt (*si); 798 if (gimple_code (stmt) != GIMPLE_ASSIGN) 799 return false; 800 801 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt)); 802 if (!INTEGRAL_TYPE_P (lhs_type)) 803 return false; 804 805 code = gimple_assign_rhs_code (stmt); 806 807 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type)) 808 return false; 809 810 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2); 811 if (!histogram) 812 return false; 813 814 value = histogram->hvalue.value; 815 wrong_values = histogram->hvalue.counters[0]; 816 count = histogram->hvalue.counters[1]; 817 818 gimple_remove_histogram_value (cfun, stmt, histogram); 819 820 /* We require that we hit a power of 2 at least half of all evaluations. */ 821 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1 822 || count < wrong_values 823 || optimize_bb_for_size_p (gimple_bb (stmt))) 824 return false; 825 826 if (dump_file) 827 { 828 fprintf (dump_file, "Mod power of 2 transformation on insn "); 829 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 830 } 831 832 /* Compute probability of taking the optimal path. */ 833 all = count + wrong_values; 834 835 if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count)) 836 return false; 837 838 if (all > 0) 839 prob = (count * REG_BR_PROB_BASE + all / 2) / all; 840 else 841 prob = 0; 842 843 result = gimple_mod_pow2 (stmt, prob, count, all); 844 845 gimple_assign_set_rhs_from_tree (si, result); 846 847 return true; 848} 849 850/* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and 851 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is 852 supported and this is built into this interface. The probabilities of taking 853 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and 854 COUNT2/ALL respectively within roundoff error). This generates the 855 result into a temp and returns the temp; it does not replace or alter 856 the original STMT. */ 857/* FIXME: Generalize the interface to handle NCOUNTS > 1. */ 858 859static tree 860gimple_mod_subtract (gimple stmt, int prob1, int prob2, int ncounts, 861 gcov_type count1, gcov_type count2, gcov_type all) 862{ 863 gimple stmt1, stmt2, stmt3; 864 tree tmp1; 865 gimple bb1end, bb2end = NULL, bb3end; 866 basic_block bb, bb2, bb3, bb4; 867 tree optype, op1, op2; 868 edge e12, e23 = 0, e24, e34, e14; 869 gimple_stmt_iterator gsi; 870 tree result; 871 872 gcc_assert (is_gimple_assign (stmt) 873 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR); 874 875 optype = TREE_TYPE (gimple_assign_lhs (stmt)); 876 op1 = gimple_assign_rhs1 (stmt); 877 op2 = gimple_assign_rhs2 (stmt); 878 879 bb = gimple_bb (stmt); 880 gsi = gsi_for_stmt (stmt); 881 882 result = create_tmp_var (optype, "PROF"); 883 tmp1 = create_tmp_var (optype, "PROF"); 884 stmt1 = gimple_build_assign (result, op1); 885 stmt2 = gimple_build_assign (tmp1, op2); 886 stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE); 887 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); 888 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT); 889 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT); 890 bb1end = stmt3; 891 892 if (ncounts) /* Assumed to be 0 or 1 */ 893 { 894 stmt1 = gimple_build_assign_with_ops (MINUS_EXPR, result, result, tmp1); 895 stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE); 896 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); 897 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT); 898 bb2end = stmt2; 899 } 900 901 /* Fallback case. */ 902 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result, 903 result, tmp1); 904 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT); 905 bb3end = stmt1; 906 907 /* Fix CFG. */ 908 /* Edge e23 connects bb2 to bb3, etc. */ 909 /* However block 3 is optional; if it is not there, references 910 to 3 really refer to block 2. */ 911 e12 = split_block (bb, bb1end); 912 bb2 = e12->dest; 913 bb2->count = all - count1; 914 915 if (ncounts) /* Assumed to be 0 or 1. */ 916 { 917 e23 = split_block (bb2, bb2end); 918 bb3 = e23->dest; 919 bb3->count = all - count1 - count2; 920 } 921 922 e34 = split_block (ncounts ? bb3 : bb2, bb3end); 923 bb4 = e34->dest; 924 bb4->count = all; 925 926 e12->flags &= ~EDGE_FALLTHRU; 927 e12->flags |= EDGE_FALSE_VALUE; 928 e12->probability = REG_BR_PROB_BASE - prob1; 929 e12->count = all - count1; 930 931 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE); 932 e14->probability = prob1; 933 e14->count = count1; 934 935 if (ncounts) /* Assumed to be 0 or 1. */ 936 { 937 e23->flags &= ~EDGE_FALLTHRU; 938 e23->flags |= EDGE_FALSE_VALUE; 939 e23->count = all - count1 - count2; 940 e23->probability = REG_BR_PROB_BASE - prob2; 941 942 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE); 943 e24->probability = prob2; 944 e24->count = count2; 945 } 946 947 e34->probability = REG_BR_PROB_BASE; 948 e34->count = all - count1 - count2; 949 950 return result; 951} 952 953 954/* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */ 955 956static bool 957gimple_mod_subtract_transform (gimple_stmt_iterator *si) 958{ 959 histogram_value histogram; 960 enum tree_code code; 961 gcov_type count, wrong_values, all; 962 tree lhs_type, result; 963 gcov_type prob1, prob2; 964 unsigned int i, steps; 965 gcov_type count1, count2; 966 gimple stmt; 967 968 stmt = gsi_stmt (*si); 969 if (gimple_code (stmt) != GIMPLE_ASSIGN) 970 return false; 971 972 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt)); 973 if (!INTEGRAL_TYPE_P (lhs_type)) 974 return false; 975 976 code = gimple_assign_rhs_code (stmt); 977 978 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type)) 979 return false; 980 981 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL); 982 if (!histogram) 983 return false; 984 985 all = 0; 986 wrong_values = 0; 987 for (i = 0; i < histogram->hdata.intvl.steps; i++) 988 all += histogram->hvalue.counters[i]; 989 990 wrong_values += histogram->hvalue.counters[i]; 991 wrong_values += histogram->hvalue.counters[i+1]; 992 steps = histogram->hdata.intvl.steps; 993 all += wrong_values; 994 count1 = histogram->hvalue.counters[0]; 995 count2 = histogram->hvalue.counters[1]; 996 997 /* Compute probability of taking the optimal path. */ 998 if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count)) 999 { 1000 gimple_remove_histogram_value (cfun, stmt, histogram); 1001 return false; 1002 } 1003 1004 if (flag_profile_correction && count1 + count2 > all) 1005 all = count1 + count2; 1006 1007 gcc_assert (count1 + count2 <= all); 1008 1009 /* We require that we use just subtractions in at least 50% of all 1010 evaluations. */ 1011 count = 0; 1012 for (i = 0; i < histogram->hdata.intvl.steps; i++) 1013 { 1014 count += histogram->hvalue.counters[i]; 1015 if (count * 2 >= all) 1016 break; 1017 } 1018 if (i == steps 1019 || optimize_bb_for_size_p (gimple_bb (stmt))) 1020 return false; 1021 1022 gimple_remove_histogram_value (cfun, stmt, histogram); 1023 if (dump_file) 1024 { 1025 fprintf (dump_file, "Mod subtract transformation on insn "); 1026 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1027 } 1028 1029 /* Compute probability of taking the optimal path(s). */ 1030 if (all > 0) 1031 { 1032 prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all; 1033 prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all; 1034 } 1035 else 1036 { 1037 prob1 = prob2 = 0; 1038 } 1039 1040 /* In practice, "steps" is always 2. This interface reflects this, 1041 and will need to be changed if "steps" can change. */ 1042 result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all); 1043 1044 gimple_assign_set_rhs_from_tree (si, result); 1045 1046 return true; 1047} 1048 1049static struct cgraph_node** pid_map = NULL; 1050 1051/* Initialize map of pids (pid -> cgraph node) */ 1052 1053static void 1054init_pid_map (void) 1055{ 1056 struct cgraph_node *n; 1057 1058 if (pid_map != NULL) 1059 return; 1060 1061 pid_map = XCNEWVEC (struct cgraph_node*, cgraph_max_pid); 1062 1063 for (n = cgraph_nodes; n; n = n->next) 1064 { 1065 if (n->pid != -1) 1066 pid_map [n->pid] = n; 1067 } 1068} 1069 1070/* Return cgraph node for function with pid */ 1071 1072static inline struct cgraph_node* 1073find_func_by_pid (int pid) 1074{ 1075 init_pid_map (); 1076 1077 return pid_map [pid]; 1078} 1079 1080/* Do transformation 1081 1082 if (actual_callee_address == address_of_most_common_function/method) 1083 do direct call 1084 else 1085 old call 1086 */ 1087 1088static gimple 1089gimple_ic (gimple icall_stmt, struct cgraph_node *direct_call, 1090 int prob, gcov_type count, gcov_type all) 1091{ 1092 gimple dcall_stmt, load_stmt, cond_stmt; 1093 tree tmp1, tmpv, tmp; 1094 basic_block cond_bb, dcall_bb, icall_bb, join_bb; 1095 tree optype = build_pointer_type (void_type_node); 1096 edge e_cd, e_ci, e_di, e_dj, e_ij; 1097 gimple_stmt_iterator gsi; 1098 int lp_nr; 1099 1100 cond_bb = gimple_bb (icall_stmt); 1101 gsi = gsi_for_stmt (icall_stmt); 1102 1103 tmpv = create_tmp_var (optype, "PROF"); 1104 tmp1 = create_tmp_var (optype, "PROF"); 1105 tmp = unshare_expr (gimple_call_fn (icall_stmt)); 1106 load_stmt = gimple_build_assign (tmpv, tmp); 1107 gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT); 1108 1109 tmp = fold_convert (optype, build_addr (direct_call->decl, 1110 current_function_decl)); 1111 load_stmt = gimple_build_assign (tmp1, tmp); 1112 gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT); 1113 1114 cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE); 1115 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); 1116 1117 dcall_stmt = gimple_copy (icall_stmt); 1118 gimple_call_set_fndecl (dcall_stmt, direct_call->decl); 1119 gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT); 1120 1121 /* Fix CFG. */ 1122 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */ 1123 e_cd = split_block (cond_bb, cond_stmt); 1124 dcall_bb = e_cd->dest; 1125 dcall_bb->count = count; 1126 1127 e_di = split_block (dcall_bb, dcall_stmt); 1128 icall_bb = e_di->dest; 1129 icall_bb->count = all - count; 1130 1131 e_ij = split_block (icall_bb, icall_stmt); 1132 join_bb = e_ij->dest; 1133 join_bb->count = all; 1134 1135 e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE; 1136 e_cd->probability = prob; 1137 e_cd->count = count; 1138 1139 e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE); 1140 e_ci->probability = REG_BR_PROB_BASE - prob; 1141 e_ci->count = all - count; 1142 1143 remove_edge (e_di); 1144 1145 e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU); 1146 e_dj->probability = REG_BR_PROB_BASE; 1147 e_dj->count = count; 1148 1149 e_ij->probability = REG_BR_PROB_BASE; 1150 e_ij->count = all - count; 1151 1152 /* Fix eh edges */ 1153 lp_nr = lookup_stmt_eh_lp (icall_stmt); 1154 if (lp_nr != 0) 1155 { 1156 if (stmt_could_throw_p (dcall_stmt)) 1157 { 1158 add_stmt_to_eh_lp (dcall_stmt, lp_nr); 1159 make_eh_edges (dcall_stmt); 1160 } 1161 1162 gcc_assert (stmt_could_throw_p (icall_stmt)); 1163 make_eh_edges (icall_stmt); 1164 1165 /* The old EH edges are sill on the join BB, purge them. */ 1166 gimple_purge_dead_eh_edges (join_bb); 1167 } 1168 1169 return dcall_stmt; 1170} 1171 1172/* 1173 For every checked indirect/virtual call determine if most common pid of 1174 function/class method has probability more than 50%. If yes modify code of 1175 this call to: 1176 */ 1177 1178static bool 1179gimple_ic_transform (gimple stmt) 1180{ 1181 histogram_value histogram; 1182 gcov_type val, count, all, bb_all; 1183 gcov_type prob; 1184 tree callee; 1185 gimple modify; 1186 struct cgraph_node *direct_call; 1187 1188 if (gimple_code (stmt) != GIMPLE_CALL) 1189 return false; 1190 1191 callee = gimple_call_fn (stmt); 1192 1193 if (TREE_CODE (callee) == FUNCTION_DECL) 1194 return false; 1195 1196 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL); 1197 if (!histogram) 1198 return false; 1199 1200 val = histogram->hvalue.counters [0]; 1201 count = histogram->hvalue.counters [1]; 1202 all = histogram->hvalue.counters [2]; 1203 gimple_remove_histogram_value (cfun, stmt, histogram); 1204 1205 if (4 * count <= 3 * all) 1206 return false; 1207 1208 bb_all = gimple_bb (stmt)->count; 1209 /* The order of CHECK_COUNTER calls is important - 1210 since check_counter can correct the third parameter 1211 and we want to make count <= all <= bb_all. */ 1212 if ( check_counter (stmt, "ic", &all, &bb_all, bb_all) 1213 || check_counter (stmt, "ic", &count, &all, all)) 1214 return false; 1215 1216 if (all > 0) 1217 prob = (count * REG_BR_PROB_BASE + all / 2) / all; 1218 else 1219 prob = 0; 1220 direct_call = find_func_by_pid ((int)val); 1221 1222 if (direct_call == NULL) 1223 return false; 1224 1225 modify = gimple_ic (stmt, direct_call, prob, count, all); 1226 1227 if (dump_file) 1228 { 1229 fprintf (dump_file, "Indirect call -> direct call "); 1230 print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM); 1231 fprintf (dump_file, "=> "); 1232 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM); 1233 fprintf (dump_file, " transformation on insn "); 1234 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1235 fprintf (dump_file, " to "); 1236 print_gimple_stmt (dump_file, modify, 0, TDF_SLIM); 1237 fprintf (dump_file, "hist->count "HOST_WIDEST_INT_PRINT_DEC 1238 " hist->all "HOST_WIDEST_INT_PRINT_DEC"\n", count, all); 1239 } 1240 1241 return true; 1242} 1243 1244/* Return true if the stringop CALL with FNDECL shall be profiled. 1245 SIZE_ARG be set to the argument index for the size of the string 1246 operation. 1247*/ 1248static bool 1249interesting_stringop_to_profile_p (tree fndecl, gimple call, int *size_arg) 1250{ 1251 enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl); 1252 1253 if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY 1254 && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO) 1255 return false; 1256 1257 switch (fcode) 1258 { 1259 case BUILT_IN_MEMCPY: 1260 case BUILT_IN_MEMPCPY: 1261 *size_arg = 2; 1262 return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE, 1263 INTEGER_TYPE, VOID_TYPE); 1264 case BUILT_IN_MEMSET: 1265 *size_arg = 2; 1266 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE, 1267 INTEGER_TYPE, VOID_TYPE); 1268 case BUILT_IN_BZERO: 1269 *size_arg = 1; 1270 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE, 1271 VOID_TYPE); 1272 default: 1273 gcc_unreachable (); 1274 } 1275} 1276 1277/* Convert stringop (..., vcall_size) 1278 into 1279 if (vcall_size == icall_size) 1280 stringop (..., icall_size); 1281 else 1282 stringop (..., vcall_size); 1283 assuming we'll propagate a true constant into ICALL_SIZE later. */ 1284 1285static void 1286gimple_stringop_fixed_value (gimple vcall_stmt, tree icall_size, int prob, 1287 gcov_type count, gcov_type all) 1288{ 1289 gimple tmp_stmt, cond_stmt, icall_stmt; 1290 tree tmp1, tmpv, vcall_size, optype; 1291 basic_block cond_bb, icall_bb, vcall_bb, join_bb; 1292 edge e_ci, e_cv, e_iv, e_ij, e_vj; 1293 gimple_stmt_iterator gsi; 1294 tree fndecl; 1295 int size_arg; 1296 1297 fndecl = gimple_call_fndecl (vcall_stmt); 1298 if (!interesting_stringop_to_profile_p (fndecl, vcall_stmt, &size_arg)) 1299 gcc_unreachable(); 1300 1301 cond_bb = gimple_bb (vcall_stmt); 1302 gsi = gsi_for_stmt (vcall_stmt); 1303 1304 vcall_size = gimple_call_arg (vcall_stmt, size_arg); 1305 optype = TREE_TYPE (vcall_size); 1306 1307 tmpv = create_tmp_var (optype, "PROF"); 1308 tmp1 = create_tmp_var (optype, "PROF"); 1309 tmp_stmt = gimple_build_assign (tmpv, fold_convert (optype, icall_size)); 1310 gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT); 1311 1312 tmp_stmt = gimple_build_assign (tmp1, vcall_size); 1313 gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT); 1314 1315 cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE); 1316 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT); 1317 1318 icall_stmt = gimple_copy (vcall_stmt); 1319 gimple_call_set_arg (icall_stmt, size_arg, icall_size); 1320 gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT); 1321 1322 /* Fix CFG. */ 1323 /* Edge e_ci connects cond_bb to icall_bb, etc. */ 1324 e_ci = split_block (cond_bb, cond_stmt); 1325 icall_bb = e_ci->dest; 1326 icall_bb->count = count; 1327 1328 e_iv = split_block (icall_bb, icall_stmt); 1329 vcall_bb = e_iv->dest; 1330 vcall_bb->count = all - count; 1331 1332 e_vj = split_block (vcall_bb, vcall_stmt); 1333 join_bb = e_vj->dest; 1334 join_bb->count = all; 1335 1336 e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE; 1337 e_ci->probability = prob; 1338 e_ci->count = count; 1339 1340 e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE); 1341 e_cv->probability = REG_BR_PROB_BASE - prob; 1342 e_cv->count = all - count; 1343 1344 remove_edge (e_iv); 1345 1346 e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU); 1347 e_ij->probability = REG_BR_PROB_BASE; 1348 e_ij->count = count; 1349 1350 e_vj->probability = REG_BR_PROB_BASE; 1351 e_vj->count = all - count; 1352 1353 /* Because these are all string op builtins, they're all nothrow. */ 1354 gcc_assert (!stmt_could_throw_p (vcall_stmt)); 1355 gcc_assert (!stmt_could_throw_p (icall_stmt)); 1356} 1357 1358/* Find values inside STMT for that we want to measure histograms for 1359 division/modulo optimization. */ 1360static bool 1361gimple_stringops_transform (gimple_stmt_iterator *gsi) 1362{ 1363 gimple stmt = gsi_stmt (*gsi); 1364 tree fndecl; 1365 tree blck_size; 1366 enum built_in_function fcode; 1367 histogram_value histogram; 1368 gcov_type count, all, val; 1369 tree dest, src; 1370 unsigned int dest_align, src_align; 1371 gcov_type prob; 1372 tree tree_val; 1373 int size_arg; 1374 1375 if (gimple_code (stmt) != GIMPLE_CALL) 1376 return false; 1377 fndecl = gimple_call_fndecl (stmt); 1378 if (!fndecl) 1379 return false; 1380 fcode = DECL_FUNCTION_CODE (fndecl); 1381 if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg)) 1382 return false; 1383 1384 blck_size = gimple_call_arg (stmt, size_arg); 1385 if (TREE_CODE (blck_size) == INTEGER_CST) 1386 return false; 1387 1388 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE); 1389 if (!histogram) 1390 return false; 1391 val = histogram->hvalue.counters[0]; 1392 count = histogram->hvalue.counters[1]; 1393 all = histogram->hvalue.counters[2]; 1394 gimple_remove_histogram_value (cfun, stmt, histogram); 1395 /* We require that count is at least half of all; this means 1396 that for the transformation to fire the value must be constant 1397 at least 80% of time. */ 1398 if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt))) 1399 return false; 1400 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count)) 1401 return false; 1402 if (all > 0) 1403 prob = (count * REG_BR_PROB_BASE + all / 2) / all; 1404 else 1405 prob = 0; 1406 dest = gimple_call_arg (stmt, 0); 1407 dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT); 1408 switch (fcode) 1409 { 1410 case BUILT_IN_MEMCPY: 1411 case BUILT_IN_MEMPCPY: 1412 src = gimple_call_arg (stmt, 1); 1413 src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT); 1414 if (!can_move_by_pieces (val, MIN (dest_align, src_align))) 1415 return false; 1416 break; 1417 case BUILT_IN_MEMSET: 1418 if (!can_store_by_pieces (val, builtin_memset_read_str, 1419 gimple_call_arg (stmt, 1), 1420 dest_align, true)) 1421 return false; 1422 break; 1423 case BUILT_IN_BZERO: 1424 if (!can_store_by_pieces (val, builtin_memset_read_str, 1425 integer_zero_node, 1426 dest_align, true)) 1427 return false; 1428 break; 1429 default: 1430 gcc_unreachable (); 1431 } 1432 tree_val = build_int_cst_wide (get_gcov_type (), 1433 (unsigned HOST_WIDE_INT) val, 1434 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1); 1435 if (dump_file) 1436 { 1437 fprintf (dump_file, "Single value %i stringop transformation on ", 1438 (int)val); 1439 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1440 } 1441 gimple_stringop_fixed_value (stmt, tree_val, prob, count, all); 1442 1443 return true; 1444} 1445 1446void 1447stringop_block_profile (gimple stmt, unsigned int *expected_align, 1448 HOST_WIDE_INT *expected_size) 1449{ 1450 histogram_value histogram; 1451 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE); 1452 if (!histogram) 1453 *expected_size = -1; 1454 else if (!histogram->hvalue.counters[1]) 1455 { 1456 *expected_size = -1; 1457 gimple_remove_histogram_value (cfun, stmt, histogram); 1458 } 1459 else 1460 { 1461 gcov_type size; 1462 size = ((histogram->hvalue.counters[0] 1463 + histogram->hvalue.counters[1] / 2) 1464 / histogram->hvalue.counters[1]); 1465 /* Even if we can hold bigger value in SIZE, INT_MAX 1466 is safe "infinity" for code generation strategies. */ 1467 if (size > INT_MAX) 1468 size = INT_MAX; 1469 *expected_size = size; 1470 gimple_remove_histogram_value (cfun, stmt, histogram); 1471 } 1472 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR); 1473 if (!histogram) 1474 *expected_align = 0; 1475 else if (!histogram->hvalue.counters[0]) 1476 { 1477 gimple_remove_histogram_value (cfun, stmt, histogram); 1478 *expected_align = 0; 1479 } 1480 else 1481 { 1482 gcov_type count; 1483 int alignment; 1484 1485 count = histogram->hvalue.counters[0]; 1486 alignment = 1; 1487 while (!(count & alignment) 1488 && (alignment * 2 * BITS_PER_UNIT)) 1489 alignment <<= 1; 1490 *expected_align = alignment * BITS_PER_UNIT; 1491 gimple_remove_histogram_value (cfun, stmt, histogram); 1492 } 1493} 1494 1495struct value_prof_hooks { 1496 /* Find list of values for which we want to measure histograms. */ 1497 void (*find_values_to_profile) (histogram_values *); 1498 1499 /* Identify and exploit properties of values that are hard to analyze 1500 statically. See value-prof.c for more detail. */ 1501 bool (*value_profile_transformations) (void); 1502}; 1503 1504/* Find values inside STMT for that we want to measure histograms for 1505 division/modulo optimization. */ 1506static void 1507gimple_divmod_values_to_profile (gimple stmt, histogram_values *values) 1508{ 1509 tree lhs, divisor, op0, type; 1510 histogram_value hist; 1511 1512 if (gimple_code (stmt) != GIMPLE_ASSIGN) 1513 return; 1514 1515 lhs = gimple_assign_lhs (stmt); 1516 type = TREE_TYPE (lhs); 1517 if (!INTEGRAL_TYPE_P (type)) 1518 return; 1519 1520 switch (gimple_assign_rhs_code (stmt)) 1521 { 1522 case TRUNC_DIV_EXPR: 1523 case TRUNC_MOD_EXPR: 1524 divisor = gimple_assign_rhs2 (stmt); 1525 op0 = gimple_assign_rhs1 (stmt); 1526 1527 VEC_reserve (histogram_value, heap, *values, 3); 1528 1529 if (is_gimple_reg (divisor)) 1530 /* Check for the case where the divisor is the same value most 1531 of the time. */ 1532 VEC_quick_push (histogram_value, *values, 1533 gimple_alloc_histogram_value (cfun, 1534 HIST_TYPE_SINGLE_VALUE, 1535 stmt, divisor)); 1536 1537 /* For mod, check whether it is not often a noop (or replaceable by 1538 a few subtractions). */ 1539 if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR 1540 && TYPE_UNSIGNED (type)) 1541 { 1542 tree val; 1543 /* Check for a special case where the divisor is power of 2. */ 1544 VEC_quick_push (histogram_value, *values, 1545 gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2, 1546 stmt, divisor)); 1547 1548 val = build2 (TRUNC_DIV_EXPR, type, op0, divisor); 1549 hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL, 1550 stmt, val); 1551 hist->hdata.intvl.int_start = 0; 1552 hist->hdata.intvl.steps = 2; 1553 VEC_quick_push (histogram_value, *values, hist); 1554 } 1555 return; 1556 1557 default: 1558 return; 1559 } 1560} 1561 1562/* Find calls inside STMT for that we want to measure histograms for 1563 indirect/virtual call optimization. */ 1564 1565static void 1566gimple_indirect_call_to_profile (gimple stmt, histogram_values *values) 1567{ 1568 tree callee; 1569 1570 if (gimple_code (stmt) != GIMPLE_CALL 1571 || gimple_call_fndecl (stmt) != NULL_TREE) 1572 return; 1573 1574 callee = gimple_call_fn (stmt); 1575 1576 VEC_reserve (histogram_value, heap, *values, 3); 1577 1578 VEC_quick_push (histogram_value, *values, 1579 gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL, 1580 stmt, callee)); 1581 1582 return; 1583} 1584 1585/* Find values inside STMT for that we want to measure histograms for 1586 string operations. */ 1587static void 1588gimple_stringops_values_to_profile (gimple stmt, histogram_values *values) 1589{ 1590 tree fndecl; 1591 tree blck_size; 1592 tree dest; 1593 int size_arg; 1594 1595 if (gimple_code (stmt) != GIMPLE_CALL) 1596 return; 1597 fndecl = gimple_call_fndecl (stmt); 1598 if (!fndecl) 1599 return; 1600 1601 if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg)) 1602 return; 1603 1604 dest = gimple_call_arg (stmt, 0); 1605 blck_size = gimple_call_arg (stmt, size_arg); 1606 1607 if (TREE_CODE (blck_size) != INTEGER_CST) 1608 { 1609 VEC_safe_push (histogram_value, heap, *values, 1610 gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE, 1611 stmt, blck_size)); 1612 VEC_safe_push (histogram_value, heap, *values, 1613 gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE, 1614 stmt, blck_size)); 1615 } 1616 if (TREE_CODE (blck_size) != INTEGER_CST) 1617 VEC_safe_push (histogram_value, heap, *values, 1618 gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR, 1619 stmt, dest)); 1620} 1621 1622/* Find values inside STMT for that we want to measure histograms and adds 1623 them to list VALUES. */ 1624 1625static void 1626gimple_values_to_profile (gimple stmt, histogram_values *values) 1627{ 1628 if (flag_value_profile_transformations) 1629 { 1630 gimple_divmod_values_to_profile (stmt, values); 1631 gimple_stringops_values_to_profile (stmt, values); 1632 gimple_indirect_call_to_profile (stmt, values); 1633 } 1634} 1635 1636static void 1637gimple_find_values_to_profile (histogram_values *values) 1638{ 1639 basic_block bb; 1640 gimple_stmt_iterator gsi; 1641 unsigned i; 1642 histogram_value hist = NULL; 1643 1644 *values = NULL; 1645 FOR_EACH_BB (bb) 1646 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1647 gimple_values_to_profile (gsi_stmt (gsi), values); 1648 1649 for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++) 1650 { 1651 switch (hist->type) 1652 { 1653 case HIST_TYPE_INTERVAL: 1654 hist->n_counters = hist->hdata.intvl.steps + 2; 1655 break; 1656 1657 case HIST_TYPE_POW2: 1658 hist->n_counters = 2; 1659 break; 1660 1661 case HIST_TYPE_SINGLE_VALUE: 1662 hist->n_counters = 3; 1663 break; 1664 1665 case HIST_TYPE_CONST_DELTA: 1666 hist->n_counters = 4; 1667 break; 1668 1669 case HIST_TYPE_INDIR_CALL: 1670 hist->n_counters = 3; 1671 break; 1672 1673 case HIST_TYPE_AVERAGE: 1674 hist->n_counters = 2; 1675 break; 1676 1677 case HIST_TYPE_IOR: 1678 hist->n_counters = 1; 1679 break; 1680 1681 default: 1682 gcc_unreachable (); 1683 } 1684 if (dump_file) 1685 { 1686 fprintf (dump_file, "Stmt "); 1687 print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM); 1688 dump_histogram_value (dump_file, hist); 1689 } 1690 } 1691} 1692 1693static struct value_prof_hooks gimple_value_prof_hooks = { 1694 gimple_find_values_to_profile, 1695 gimple_value_profile_transformations 1696}; 1697 1698void 1699gimple_register_value_prof_hooks (void) 1700{ 1701 gcc_assert (current_ir_type () == IR_GIMPLE); 1702 value_prof_hooks = &gimple_value_prof_hooks; 1703} 1704 1705/* IR-independent entry points. */ 1706void 1707find_values_to_profile (histogram_values *values) 1708{ 1709 (value_prof_hooks->find_values_to_profile) (values); 1710} 1711 1712bool 1713value_profile_transformations (void) 1714{ 1715 return (value_prof_hooks->value_profile_transformations) (); 1716} 1717 1718