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