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