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