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