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