Mercurial > hg > CbC > CbC_gcc

comparison gcc/value-prof.c @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
comparison
equal deleted inserted replaced
131:84e7813d76e9 145:1830386684a0
1 /* Transformations based on profile information for values. 1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2018 Free Software Foundation, Inc. 2 Copyright (C) 2003-2020 Free Software Foundation, Inc.
3 3
4 This file is part of GCC. 4 This file is part of GCC.
5 5
6 GCC is free software; you can redistribute it and/or modify it under 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 7 the terms of the GNU General Public License as published by the Free
40 #include "gimple-iterator.h" 40 #include "gimple-iterator.h"
41 #include "tree-cfg.h" 41 #include "tree-cfg.h"
42 #include "gimple-pretty-print.h" 42 #include "gimple-pretty-print.h"
43 #include "dumpfile.h" 43 #include "dumpfile.h"
44 #include "builtins.h" 44 #include "builtins.h"
45 #include "params.h"
46 45
47 /* In this file value profile based optimizations are placed. Currently the 46 /* In this file value profile based optimizations are placed. Currently the
48 following optimizations are implemented (for more detailed descriptions 47 following optimizations are implemented (for more detailed descriptions
49 see comments at value_profile_transformations): 48 see comments at value_profile_transformations):
50 49
105 104
106 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *); 105 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
107 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *); 106 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
108 static bool gimple_mod_subtract_transform (gimple_stmt_iterator *); 107 static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
109 static bool gimple_stringops_transform (gimple_stmt_iterator *); 108 static bool gimple_stringops_transform (gimple_stmt_iterator *);
110 static bool gimple_ic_transform (gimple_stmt_iterator *); 109 static void dump_ic_profile (gimple_stmt_iterator *gsi);
111 110
112 /* Allocate histogram value. */ 111 /* Allocate histogram value. */
113 112
114 histogram_value 113 histogram_value
115 gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED, 114 gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
226 dump_histogram_value (FILE *dump_file, histogram_value hist) 225 dump_histogram_value (FILE *dump_file, histogram_value hist)
227 { 226 {
228 switch (hist->type) 227 switch (hist->type)
229 { 228 {
230 case HIST_TYPE_INTERVAL: 229 case HIST_TYPE_INTERVAL:
231 fprintf (dump_file, "Interval counter range %d -- %d",
232 hist->hdata.intvl.int_start,
233 (hist->hdata.intvl.int_start
234 + hist->hdata.intvl.steps - 1));
235 if (hist->hvalue.counters) 230 if (hist->hvalue.counters)
236 { 231 {
237 unsigned int i; 232 fprintf (dump_file, "Interval counter range [%d,%d]: [",
238 fprintf (dump_file, " ["); 233 hist->hdata.intvl.int_start,
239 for (i = 0; i < hist->hdata.intvl.steps; i++) 234 (hist->hdata.intvl.int_start
240 fprintf (dump_file, " %d:%" PRId64, 235 + hist->hdata.intvl.steps - 1));
241 hist->hdata.intvl.int_start + i, 236
242 (int64_t) hist->hvalue.counters[i]); 237 unsigned int i;
243 fprintf (dump_file, " ] outside range:%" PRId64, 238 for (i = 0; i < hist->hdata.intvl.steps; i++)
244 (int64_t) hist->hvalue.counters[i]); 239 {
240 fprintf (dump_file, "%d:%" PRId64,
241 hist->hdata.intvl.int_start + i,
242 (int64_t) hist->hvalue.counters[i]);
243 if (i != hist->hdata.intvl.steps - 1)
244 fprintf (dump_file, ", ");
245 }
246 fprintf (dump_file, "] outside range: %" PRId64 ".\n",
247 (int64_t) hist->hvalue.counters[i]);
245 } 248 }
246 fprintf (dump_file, ".\n");
247 break; 249 break;
248 250
249 case HIST_TYPE_POW2: 251 case HIST_TYPE_POW2:
250 fprintf (dump_file, "Pow2 counter "); 252 if (hist->hvalue.counters)
253 fprintf (dump_file, "Pow2 counter pow2:%" PRId64
254 " nonpow2:%" PRId64 ".\n",
255 (int64_t) hist->hvalue.counters[1],
256 (int64_t) hist->hvalue.counters[0]);
257 break;
258
259 case HIST_TYPE_TOPN_VALUES:
260 case HIST_TYPE_INDIR_CALL:
251 if (hist->hvalue.counters) 261 if (hist->hvalue.counters)
252 { 262 {
253 fprintf (dump_file, "pow2:%" PRId64 263 fprintf (dump_file,
254 " nonpow2:%" PRId64, 264 (hist->type == HIST_TYPE_TOPN_VALUES
255 (int64_t) hist->hvalue.counters[1], 265 ? "Top N value counter" : "Indirect call counter"));
256 (int64_t) hist->hvalue.counters[0]); 266 if (hist->hvalue.counters)
267 {
268 fprintf (dump_file, " all: %" PRId64 ", values: ",
269 (int64_t) hist->hvalue.counters[0]);
270 for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++)
271 {
272 fprintf (dump_file, "[%" PRId64 ":%" PRId64 "]",
273 (int64_t) hist->hvalue.counters[2 * i + 1],
274 (int64_t) hist->hvalue.counters[2 * i + 2]);
275 if (i != GCOV_TOPN_VALUES - 1)
276 fprintf (dump_file, ", ");
277 }
278 fprintf (dump_file, ".\n");
279 }
257 } 280 }
258 fprintf (dump_file, ".\n");
259 break; 281 break;
260 282
261 case HIST_TYPE_SINGLE_VALUE: 283 case HIST_TYPE_AVERAGE:
262 fprintf (dump_file, "Single value ");
263 if (hist->hvalue.counters) 284 if (hist->hvalue.counters)
264 { 285 fprintf (dump_file, "Average value sum:%" PRId64
265 fprintf (dump_file, "value:%" PRId64 286 " times:%" PRId64 ".\n",
266 " match:%" PRId64 287 (int64_t) hist->hvalue.counters[0],
267 " wrong:%" PRId64, 288 (int64_t) hist->hvalue.counters[1]);
268 (int64_t) hist->hvalue.counters[0],
269 (int64_t) hist->hvalue.counters[1],
270 (int64_t) hist->hvalue.counters[2]);
271 }
272 fprintf (dump_file, ".\n");
273 break; 289 break;
274 290
275 case HIST_TYPE_AVERAGE: 291 case HIST_TYPE_IOR:
276 fprintf (dump_file, "Average value ");
277 if (hist->hvalue.counters) 292 if (hist->hvalue.counters)
278 { 293 fprintf (dump_file, "IOR value ior:%" PRId64 ".\n",
279 fprintf (dump_file, "sum:%" PRId64 294 (int64_t) hist->hvalue.counters[0]);
280 " times:%" PRId64,
281 (int64_t) hist->hvalue.counters[0],
282 (int64_t) hist->hvalue.counters[1]);
283 }
284 fprintf (dump_file, ".\n");
285 break; 295 break;
286 296
287 case HIST_TYPE_IOR: 297 case HIST_TYPE_TIME_PROFILE:
288 fprintf (dump_file, "IOR value ");
289 if (hist->hvalue.counters) 298 if (hist->hvalue.counters)
290 { 299 fprintf (dump_file, "Time profile time:%" PRId64 ".\n",
291 fprintf (dump_file, "ior:%" PRId64, 300 (int64_t) hist->hvalue.counters[0]);
292 (int64_t) hist->hvalue.counters[0]);
293 }
294 fprintf (dump_file, ".\n");
295 break; 301 break;
296 302 default:
297 case HIST_TYPE_INDIR_CALL:
298 fprintf (dump_file, "Indirect call ");
299 if (hist->hvalue.counters)
300 {
301 fprintf (dump_file, "value:%" PRId64
302 " match:%" PRId64
303 " all:%" PRId64,
304 (int64_t) hist->hvalue.counters[0],
305 (int64_t) hist->hvalue.counters[1],
306 (int64_t) hist->hvalue.counters[2]);
307 }
308 fprintf (dump_file, ".\n");
309 break;
310 case HIST_TYPE_TIME_PROFILE:
311 fprintf (dump_file, "Time profile ");
312 if (hist->hvalue.counters)
313 {
314 fprintf (dump_file, "time:%" PRId64,
315 (int64_t) hist->hvalue.counters[0]);
316 }
317 fprintf (dump_file, ".\n");
318 break;
319 case HIST_TYPE_INDIR_CALL_TOPN:
320 fprintf (dump_file, "Indirect call topn ");
321 if (hist->hvalue.counters)
322 {
323 int i;
324
325 fprintf (dump_file, "accu:%" PRId64, hist->hvalue.counters[0]);
326 for (i = 1; i < (GCOV_ICALL_TOPN_VAL << 2); i += 2)
327 {
328 fprintf (dump_file, " target:%" PRId64 " value:%" PRId64,
329 (int64_t) hist->hvalue.counters[i],
330 (int64_t) hist->hvalue.counters[i+1]);
331 }
332 }
333 fprintf (dump_file, ".\n");
334 break;
335 case HIST_TYPE_MAX:
336 gcc_unreachable (); 303 gcc_unreachable ();
337 } 304 }
338 } 305 }
339 306
340 /* Dump information about HIST to DUMP_FILE. */ 307 /* Dump information about HIST to DUMP_FILE. */
361 for (i = 0; i < hist->n_counters; i++) 328 for (i = 0; i < hist->n_counters; i++)
362 { 329 {
363 /* When user uses an unsigned type with a big value, constant converted 330 /* When user uses an unsigned type with a big value, constant converted
364 to gcov_type (a signed type) can be negative. */ 331 to gcov_type (a signed type) can be negative. */
365 gcov_type value = hist->hvalue.counters[i]; 332 gcov_type value = hist->hvalue.counters[i];
366 if (hist->type == HIST_TYPE_SINGLE_VALUE && i == 0) 333 if (hist->type == HIST_TYPE_TOPN_VALUES && i > 0)
367 ; 334 ;
368 else 335 else
369 gcc_assert (value >= 0); 336 gcc_assert (value >= 0);
370 337
371 streamer_write_gcov_count (ob, value); 338 streamer_write_gcov_count (ob, value);
375 } 342 }
376 343
377 /* Dump information about HIST to DUMP_FILE. */ 344 /* Dump information about HIST to DUMP_FILE. */
378 345
379 void 346 void
380 stream_in_histogram_value (struct lto_input_block *ib, gimple *stmt) 347 stream_in_histogram_value (class lto_input_block *ib, gimple *stmt)
381 { 348 {
382 enum hist_type type; 349 enum hist_type type;
383 unsigned int ncounters = 0; 350 unsigned int ncounters = 0;
384 struct bitpack_d bp; 351 struct bitpack_d bp;
385 unsigned int i; 352 unsigned int i;
390 do 357 do
391 { 358 {
392 bp = streamer_read_bitpack (ib); 359 bp = streamer_read_bitpack (ib);
393 type = bp_unpack_enum (&bp, hist_type, HIST_TYPE_MAX); 360 type = bp_unpack_enum (&bp, hist_type, HIST_TYPE_MAX);
394 next = bp_unpack_value (&bp, 1); 361 next = bp_unpack_value (&bp, 1);
395 new_val = gimple_alloc_histogram_value (cfun, type, stmt, NULL); 362 new_val = gimple_alloc_histogram_value (cfun, type, stmt);
396 switch (type) 363 switch (type)
397 { 364 {
398 case HIST_TYPE_INTERVAL: 365 case HIST_TYPE_INTERVAL:
399 new_val->hdata.intvl.int_start = streamer_read_hwi (ib); 366 new_val->hdata.intvl.int_start = streamer_read_hwi (ib);
400 new_val->hdata.intvl.steps = streamer_read_uhwi (ib); 367 new_val->hdata.intvl.steps = streamer_read_uhwi (ib);
404 case HIST_TYPE_POW2: 371 case HIST_TYPE_POW2:
405 case HIST_TYPE_AVERAGE: 372 case HIST_TYPE_AVERAGE:
406 ncounters = 2; 373 ncounters = 2;
407 break; 374 break;
408 375
409 case HIST_TYPE_SINGLE_VALUE: 376 case HIST_TYPE_TOPN_VALUES:
410 case HIST_TYPE_INDIR_CALL: 377 case HIST_TYPE_INDIR_CALL:
411 ncounters = 3; 378 ncounters = GCOV_TOPN_VALUES_COUNTERS;
412 break; 379 break;
413 380
414 case HIST_TYPE_IOR: 381 case HIST_TYPE_IOR:
415 case HIST_TYPE_TIME_PROFILE: 382 case HIST_TYPE_TIME_PROFILE:
416 ncounters = 1; 383 ncounters = 1;
417 break; 384 break;
418 385
419 case HIST_TYPE_INDIR_CALL_TOPN: 386 default:
420 ncounters = (GCOV_ICALL_TOPN_VAL << 2) + 1;
421 break;
422
423 case HIST_TYPE_MAX:
424 gcc_unreachable (); 387 gcc_unreachable ();
425 } 388 }
426 new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * ncounters); 389 new_val->hvalue.counters = XNEWVAR (gcov_type,
390 sizeof (*new_val->hvalue.counters)
391 * ncounters);
427 new_val->n_counters = ncounters; 392 new_val->n_counters = ncounters;
428 for (i = 0; i < ncounters; i++) 393 for (i = 0; i < ncounters; i++)
429 new_val->hvalue.counters[i] = streamer_read_gcov_count (ib); 394 new_val->hvalue.counters[i] = streamer_read_gcov_count (ib);
430 if (!next_p) 395 if (!next_p)
431 gimple_add_histogram_value (cfun, stmt, new_val); 396 gimple_add_histogram_value (cfun, stmt, new_val);
463 struct function *ofun, gimple *ostmt) 428 struct function *ofun, gimple *ostmt)
464 { 429 {
465 histogram_value val; 430 histogram_value val;
466 for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next) 431 for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
467 { 432 {
468 histogram_value new_val = gimple_alloc_histogram_value (fun, val->type, NULL, NULL); 433 histogram_value new_val = gimple_alloc_histogram_value (fun, val->type);
469 memcpy (new_val, val, sizeof (*val)); 434 memcpy (new_val, val, sizeof (*val));
470 new_val->hvalue.stmt = stmt; 435 new_val->hvalue.stmt = stmt;
471 new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters); 436 new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
472 memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters); 437 memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
473 gimple_add_histogram_value (fun, stmt, new_val); 438 gimple_add_histogram_value (fun, stmt, new_val);
533 for (hist = gimple_histogram_value (cfun, stmt); hist; 498 for (hist = gimple_histogram_value (cfun, stmt); hist;
534 hist = hist->hvalue.next) 499 hist = hist->hvalue.next)
535 { 500 {
536 if (hist->hvalue.stmt != stmt) 501 if (hist->hvalue.stmt != stmt)
537 { 502 {
538 error ("Histogram value statement does not correspond to " 503 error ("histogram value statement does not correspond to "
539 "the statement it is associated with"); 504 "the statement it is associated with");
540 debug_gimple_stmt (stmt); 505 debug_gimple_stmt (stmt);
541 dump_histogram_value (stderr, hist); 506 dump_histogram_value (stderr, hist);
542 error_found = true; 507 error_found = true;
543 } 508 }
545 } 510 }
546 } 511 }
547 if (VALUE_HISTOGRAMS (cfun)) 512 if (VALUE_HISTOGRAMS (cfun))
548 htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, &visited_hists); 513 htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, &visited_hists);
549 if (error_found) 514 if (error_found)
550 internal_error ("verify_histograms failed"); 515 internal_error ("%qs failed", __func__);
551 } 516 }
552 517
553 /* Helper function for verify_histograms. For each histogram reachable via htab 518 /* Helper function for verify_histograms. For each histogram reachable via htab
554 walk verify that it was reached via statement walk. */ 519 walk verify that it was reached via statement walk. */
555 520
625 { 590 {
626 basic_block bb; 591 basic_block bb;
627 gimple_stmt_iterator gsi; 592 gimple_stmt_iterator gsi;
628 bool changed = false; 593 bool changed = false;
629 594
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) 595 FOR_EACH_BB_FN (bb, cfun)
636 { 596 {
637 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 597 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
638 { 598 {
639 gimple *stmt = gsi_stmt (gsi); 599 gimple *stmt = gsi_stmt (gsi);
656 current statement remain valid (although possibly 616 current statement remain valid (although possibly
657 modified) upon return. */ 617 modified) upon return. */
658 if (gimple_mod_subtract_transform (&gsi) 618 if (gimple_mod_subtract_transform (&gsi)
659 || gimple_divmod_fixed_value_transform (&gsi) 619 || gimple_divmod_fixed_value_transform (&gsi)
660 || gimple_mod_pow2_value_transform (&gsi) 620 || gimple_mod_pow2_value_transform (&gsi)
661 || gimple_stringops_transform (&gsi) 621 || gimple_stringops_transform (&gsi))
662 || gimple_ic_transform (&gsi))
663 { 622 {
664 stmt = gsi_stmt (gsi); 623 stmt = gsi_stmt (gsi);
665 changed = true; 624 changed = true;
666 /* Original statement may no longer be in the same block. */ 625 /* Original statement may no longer be in the same block. */
667 if (bb != gimple_bb (stmt)) 626 if (bb != gimple_bb (stmt))
668 { 627 {
669 bb = gimple_bb (stmt); 628 bb = gimple_bb (stmt);
670 gsi = gsi_for_stmt (stmt); 629 gsi = gsi_for_stmt (stmt);
671 } 630 }
672 } 631 }
632
633 /* The function never thansforms a GIMPLE statement. */
634 if (dump_enabled_p ())
635 dump_ic_profile (&gsi);
673 } 636 }
674 } 637 }
675 638
676 return changed; 639 return changed;
677 } 640 }
752 e34->probability = profile_probability::always (); 715 e34->probability = profile_probability::always ();
753 716
754 return tmp2; 717 return tmp2;
755 } 718 }
756 719
720 /* Return the n-th value count of TOPN_VALUE histogram. If
721 there's a value, return true and set VALUE and COUNT
722 arguments. */
723
724 bool
725 get_nth_most_common_value (gimple *stmt, const char *counter_type,
726 histogram_value hist, gcov_type *value,
727 gcov_type *count, gcov_type *all, unsigned n)
728 {
729 if (hist->hvalue.counters[2] == -1)
730 return false;
731
732 gcc_assert (n < GCOV_TOPN_VALUES);
733
734 *count = 0;
735 *value = 0;
736
737 gcov_type read_all = hist->hvalue.counters[0];
738
739 gcov_type v = hist->hvalue.counters[2 * n + 1];
740 gcov_type c = hist->hvalue.counters[2 * n + 2];
741
742 /* Indirect calls can't be verified. */
743 if (stmt
744 && check_counter (stmt, counter_type, &c, &read_all,
745 gimple_bb (stmt)->count))
746 return false;
747
748 *all = read_all;
749
750 *value = v;
751 *count = c;
752 return true;
753 }
754
757 /* Do transform 1) on INSN if applicable. */ 755 /* Do transform 1) on INSN if applicable. */
758 756
759 static bool 757 static bool
760 gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si) 758 gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
761 { 759 {
777 775
778 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR) 776 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
779 return false; 777 return false;
780 778
781 histogram = gimple_histogram_value_of_type (cfun, stmt, 779 histogram = gimple_histogram_value_of_type (cfun, stmt,
782 HIST_TYPE_SINGLE_VALUE); 780 HIST_TYPE_TOPN_VALUES);
783 if (!histogram) 781 if (!histogram)
784 return false; 782 return false;
785 783
784 if (!get_nth_most_common_value (stmt, "divmod", histogram, &val, &count,
785 &all))
786 return false;
787
786 value = histogram->hvalue.value; 788 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); 789 gimple_remove_histogram_value (cfun, stmt, histogram);
791 790
792 /* We require that count is at least half of all; this means 791 /* We require that count is at least half of all. */
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 792 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
796 || 2 * count < all 793 || 2 * count < all
797 || optimize_bb_for_size_p (gimple_bb (stmt))) 794 || 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; 795 return false;
802 796
803 /* Compute probability of taking the optimal path. */ 797 /* Compute probability of taking the optimal path. */
804 if (all > 0) 798 if (all > 0)
805 prob = profile_probability::probability_in_gcov_type (count, all); 799 prob = profile_probability::probability_in_gcov_type (count, all);
817 tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2, 811 tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
818 TYPE_PRECISION (get_gcov_type ()), false)); 812 TYPE_PRECISION (get_gcov_type ()), false));
819 } 813 }
820 result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all); 814 result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all);
821 815
822 if (dump_file) 816 if (dump_enabled_p ())
823 { 817 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
824 fprintf (dump_file, "Transformation done: div/mod by constant "); 818 "Transformation done: div/mod by constant %T\n", tree_val);
825 print_generic_expr (dump_file, tree_val, TDF_SLIM);
826 fprintf (dump_file, "\n");
827 }
828 819
829 gimple_assign_set_rhs_from_tree (si, result); 820 gimple_assign_set_rhs_from_tree (si, result);
830 update_stmt (gsi_stmt (*si)); 821 update_stmt (gsi_stmt (*si));
831 822
832 return true; 823 return true;
957 all = count + wrong_values; 948 all = count + wrong_values;
958 949
959 if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count)) 950 if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
960 return false; 951 return false;
961 952
962 if (dump_file) 953 if (dump_enabled_p ())
963 fprintf (dump_file, "Transformation done: mod power of 2\n"); 954 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
955 "Transformation done: mod power of 2\n");
964 956
965 if (all > 0) 957 if (all > 0)
966 prob = profile_probability::probability_in_gcov_type (count, all); 958 prob = profile_probability::probability_in_gcov_type (count, all);
967 else 959 else
968 prob = profile_probability::never (); 960 prob = profile_probability::never ();
1116 steps = histogram->hdata.intvl.steps; 1108 steps = histogram->hdata.intvl.steps;
1117 all += wrong_values; 1109 all += wrong_values;
1118 count1 = histogram->hvalue.counters[0]; 1110 count1 = histogram->hvalue.counters[0];
1119 count2 = histogram->hvalue.counters[1]; 1111 count2 = histogram->hvalue.counters[1];
1120 1112
1121 /* Compute probability of taking the optimal path. */
1122 if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count)) 1113 if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count))
1123 { 1114 {
1124 gimple_remove_histogram_value (cfun, stmt, histogram); 1115 gimple_remove_histogram_value (cfun, stmt, histogram);
1125 return false; 1116 return false;
1126 } 1117 }
1142 if (i == steps 1133 if (i == steps
1143 || optimize_bb_for_size_p (gimple_bb (stmt))) 1134 || optimize_bb_for_size_p (gimple_bb (stmt)))
1144 return false; 1135 return false;
1145 1136
1146 gimple_remove_histogram_value (cfun, stmt, histogram); 1137 gimple_remove_histogram_value (cfun, stmt, histogram);
1147 if (dump_file) 1138 if (dump_enabled_p ())
1148 fprintf (dump_file, "Transformation done: mod subtract\n"); 1139 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
1140 "Transformation done: mod subtract\n");
1149 1141
1150 /* Compute probability of taking the optimal path(s). */ 1142 /* Compute probability of taking the optimal path(s). */
1151 if (all > 0) 1143 if (all > 0)
1152 { 1144 {
1153 prob1 = profile_probability::probability_in_gcov_type (count1, all); 1145 prob1 = profile_probability::probability_in_gcov_type (count1, all);
1191 { 1183 {
1192 struct cgraph_node *n; 1184 struct cgraph_node *n;
1193 cgraph_node_map = new hash_map<profile_id_hash, cgraph_node *>; 1185 cgraph_node_map = new hash_map<profile_id_hash, cgraph_node *>;
1194 1186
1195 FOR_EACH_DEFINED_FUNCTION (n) 1187 FOR_EACH_DEFINED_FUNCTION (n)
1196 if (n->has_gimple_body_p ()) 1188 if (n->has_gimple_body_p () || n->thunk.thunk_p)
1197 { 1189 {
1198 cgraph_node **val; 1190 cgraph_node **val;
1191 dump_user_location_t loc
1192 = dump_user_location_t::from_function_decl (n->decl);
1199 if (local) 1193 if (local)
1200 { 1194 {
1201 n->profile_id = coverage_compute_profile_id (n); 1195 n->profile_id = coverage_compute_profile_id (n);
1202 while ((val = cgraph_node_map->get (n->profile_id)) 1196 while ((val = cgraph_node_map->get (n->profile_id))
1203 || !n->profile_id) 1197 || !n->profile_id)
1204 { 1198 {
1205 if (dump_file) 1199 if (dump_enabled_p ())
1206 fprintf (dump_file, "Local profile-id %i conflict" 1200 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1207 " with nodes %s %s\n", 1201 "Local profile-id %i conflict"
1208 n->profile_id, 1202 " with nodes %s %s\n",
1209 n->dump_name (), 1203 n->profile_id,
1210 (*val)->dump_name ()); 1204 n->dump_name (),
1205 (*val)->dump_name ());
1211 n->profile_id = (n->profile_id + 1) & 0x7fffffff; 1206 n->profile_id = (n->profile_id + 1) & 0x7fffffff;
1212 } 1207 }
1213 } 1208 }
1214 else if (!n->profile_id) 1209 else if (!n->profile_id)
1215 { 1210 {
1216 if (dump_file) 1211 if (dump_enabled_p ())
1217 fprintf (dump_file, 1212 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1218 "Node %s has no profile-id" 1213 "Node %s has no profile-id"
1219 " (profile feedback missing?)\n", 1214 " (profile feedback missing?)\n",
1220 n->dump_name ()); 1215 n->dump_name ());
1221 continue; 1216 continue;
1222 } 1217 }
1223 else if ((val = cgraph_node_map->get (n->profile_id))) 1218 else if ((val = cgraph_node_map->get (n->profile_id)))
1224 { 1219 {
1225 if (dump_file) 1220 if (dump_enabled_p ())
1226 fprintf (dump_file, 1221 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
1227 "Node %s has IP profile-id %i conflict. " 1222 "Node %s has IP profile-id %i conflict. "
1228 "Giving up.\n", 1223 "Giving up.\n",
1229 n->dump_name (), n->profile_id); 1224 n->dump_name (), n->profile_id);
1230 *val = NULL; 1225 *val = NULL;
1231 continue; 1226 continue;
1232 } 1227 }
1233 cgraph_node_map->put (n->profile_id, n); 1228 cgraph_node_map->put (n->profile_id, n);
1234 } 1229 }
1250 cgraph_node **val = cgraph_node_map->get (profile_id); 1245 cgraph_node **val = cgraph_node_map->get (profile_id);
1251 if (val) 1246 if (val)
1252 return *val; 1247 return *val;
1253 else 1248 else
1254 return NULL; 1249 return NULL;
1255 }
1256
1257 /* Perform sanity check on the indirect call target. Due to race conditions,
1258 false function target may be attributed to an indirect call site. If the
1259 call expression type mismatches with the target function's type, expand_call
1260 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1261 Returns true if TARGET is considered ok for call CALL_STMT. */
1262
1263 bool
1264 check_ic_target (gcall *call_stmt, struct cgraph_node *target)
1265 {
1266 if (gimple_check_call_matching_types (call_stmt, target->decl, true))
1267 return true;
1268
1269 if (dump_enabled_p ())
1270 dump_printf_loc (MSG_MISSED_OPTIMIZATION, call_stmt,
1271 "Skipping target %s with mismatching types for icall\n",
1272 target->name ());
1273 return false;
1274 } 1250 }
1275 1251
1276 /* Do transformation 1252 /* Do transformation
1277 1253
1278 if (actual_callee_address == address_of_most_common_function/method) 1254 if (actual_callee_address == address_of_most_common_function/method)
1413 if (!stmt_could_throw_p (cfun, dcall_stmt)) 1389 if (!stmt_could_throw_p (cfun, dcall_stmt))
1414 gimple_purge_dead_eh_edges (dcall_bb); 1390 gimple_purge_dead_eh_edges (dcall_bb);
1415 return dcall_stmt; 1391 return dcall_stmt;
1416 } 1392 }
1417 1393
1418 /* 1394 /* Dump info about indirect call profile. */
1419 For every checked indirect/virtual call determine if most common pid of 1395
1420 function/class method has probability more than 50%. If yes modify code of 1396 static void
1421 this call to: 1397 dump_ic_profile (gimple_stmt_iterator *gsi)
1422 */
1423
1424 static bool
1425 gimple_ic_transform (gimple_stmt_iterator *gsi)
1426 { 1398 {
1427 gcall *stmt; 1399 gcall *stmt;
1428 histogram_value histogram; 1400 histogram_value histogram;
1429 gcov_type val, count, all, bb_all; 1401 gcov_type val, count, all;
1430 struct cgraph_node *direct_call; 1402 struct cgraph_node *direct_call;
1431 1403
1432 stmt = dyn_cast <gcall *> (gsi_stmt (*gsi)); 1404 stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1433 if (!stmt) 1405 if (!stmt)
1434 return false; 1406 return;
1435 1407
1436 if (gimple_call_fndecl (stmt) != NULL_TREE) 1408 if (gimple_call_fndecl (stmt) != NULL_TREE)
1437 return false; 1409 return;
1438 1410
1439 if (gimple_call_internal_p (stmt)) 1411 if (gimple_call_internal_p (stmt))
1440 return false; 1412 return;
1441 1413
1442 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL); 1414 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1443 if (!histogram) 1415 if (!histogram)
1444 return false; 1416 return;
1445 1417
1446 val = histogram->hvalue.counters [0]; 1418 count = 0;
1447 count = histogram->hvalue.counters [1]; 1419 all = histogram->hvalue.counters[0];
1448 all = histogram->hvalue.counters [2]; 1420
1449 1421 for (unsigned j = 0; j < GCOV_TOPN_VALUES; j++)
1450 bb_all = gimple_bb (stmt)->count.ipa ().to_gcov_type (); 1422 {
1451 /* The order of CHECK_COUNTER calls is important - 1423 if (!get_nth_most_common_value (NULL, "indirect call", histogram, &val,
1452 since check_counter can correct the third parameter 1424 &count, &all, j))
1453 and we want to make count <= all <= bb_all. */ 1425 return;
1454 if (check_counter (stmt, "ic", &all, &bb_all, gimple_bb (stmt)->count) 1426 if (!count)
1455 || check_counter (stmt, "ic", &count, &all, 1427 continue;
1456 profile_count::from_gcov_type (all))) 1428
1457 { 1429 direct_call = find_func_by_profile_id ((int) val);
1458 gimple_remove_histogram_value (cfun, stmt, histogram); 1430
1459 return false; 1431 if (direct_call == NULL)
1460 } 1432 dump_printf_loc (
1461 1433 MSG_MISSED_OPTIMIZATION, stmt,
1462 if (4 * count <= 3 * all) 1434 "Indirect call -> direct call from other "
1463 return false; 1435 "module %T=> %i (will resolve by ipa-profile only with LTO)\n",
1464 1436 gimple_call_fn (stmt), (int) val);
1465 direct_call = find_func_by_profile_id ((int)val); 1437 else
1466 1438 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
1467 if (direct_call == NULL) 1439 "Indirect call -> direct call "
1468 { 1440 "%T => %T (will resolve by ipa-profile)\n",
1469 if (val) 1441 gimple_call_fn (stmt), direct_call->decl);
1470 { 1442 dump_printf_loc (MSG_NOTE, stmt,
1471 if (dump_file) 1443 "hist->count %" PRId64 " hist->all %" PRId64 "\n",
1472 { 1444 count, all);
1473 fprintf (dump_file, "Indirect call -> direct call from other module"); 1445 }
1474 print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1475 fprintf (dump_file, "=> %i (will resolve only with LTO)\n", (int)val);
1476 }
1477 }
1478 return false;
1479 }
1480
1481 if (!check_ic_target (stmt, direct_call))
1482 {
1483 if (dump_file)
1484 {
1485 fprintf (dump_file, "Indirect call -> direct call ");
1486 print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1487 fprintf (dump_file, "=> ");
1488 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1489 fprintf (dump_file, " transformation skipped because of type mismatch");
1490 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1491 }
1492 gimple_remove_histogram_value (cfun, stmt, histogram);
1493 return false;
1494 }
1495
1496 if (dump_file)
1497 {
1498 fprintf (dump_file, "Indirect call -> direct call ");
1499 print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1500 fprintf (dump_file, "=> ");
1501 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1502 fprintf (dump_file, " transformation on insn postponned to ipa-profile");
1503 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1504 fprintf (dump_file, "hist->count %" PRId64
1505 " hist->all %" PRId64"\n", count, all);
1506 }
1507
1508 return true;
1509 } 1446 }
1510 1447
1511 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be 1448 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1512 set to the argument index for the size of the string operation. */ 1449 set to the argument index for the size of the string operation. */
1513 1450
1667 1604
1668 blck_size = gimple_call_arg (stmt, size_arg); 1605 blck_size = gimple_call_arg (stmt, size_arg);
1669 if (TREE_CODE (blck_size) == INTEGER_CST) 1606 if (TREE_CODE (blck_size) == INTEGER_CST)
1670 return false; 1607 return false;
1671 1608
1672 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE); 1609 histogram = gimple_histogram_value_of_type (cfun, stmt,
1610 HIST_TYPE_TOPN_VALUES);
1673 if (!histogram) 1611 if (!histogram)
1674 return false; 1612 return false;
1675 1613
1676 val = histogram->hvalue.counters[0]; 1614 if (!get_nth_most_common_value (stmt, "stringops", histogram, &val, &count,
1677 count = histogram->hvalue.counters[1]; 1615 &all))
1678 all = histogram->hvalue.counters[2]; 1616 return false;
1617
1679 gimple_remove_histogram_value (cfun, stmt, histogram); 1618 gimple_remove_histogram_value (cfun, stmt, histogram);
1680 1619
1681 /* We require that count is at least half of all; this means 1620 /* We require that count is at least half of all. */
1682 that for the transformation to fire the value must be constant 1621 if (2 * count < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1683 at least 80% of time. */
1684 if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1685 return false; 1622 return false;
1686 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count)) 1623 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1687 return false; 1624 return false;
1688 if (all > 0) 1625 if (all > 0)
1689 prob = profile_probability::probability_in_gcov_type (count, all); 1626 prob = profile_probability::probability_in_gcov_type (count, all);
1729 1666
1730 tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2, 1667 tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
1731 TYPE_PRECISION (get_gcov_type ()), false)); 1668 TYPE_PRECISION (get_gcov_type ()), false));
1732 } 1669 }
1733 1670
1734 if (dump_file) 1671 if (dump_enabled_p ())
1735 fprintf (dump_file, 1672 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, stmt,
1736 "Transformation done: single value %i stringop for %s\n", 1673 "Transformation done: single value %i stringop for %s\n",
1737 (int)val, built_in_names[(int)fcode]); 1674 (int)val, built_in_names[(int)fcode]);
1738 1675
1739 gimple_stringop_fixed_value (stmt, tree_val, prob, count, all); 1676 gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
1740 1677
1741 return true; 1678 return true;
1742 } 1679 }
1816 case TRUNC_DIV_EXPR: 1753 case TRUNC_DIV_EXPR:
1817 case TRUNC_MOD_EXPR: 1754 case TRUNC_MOD_EXPR:
1818 divisor = gimple_assign_rhs2 (stmt); 1755 divisor = gimple_assign_rhs2 (stmt);
1819 op0 = gimple_assign_rhs1 (stmt); 1756 op0 = gimple_assign_rhs1 (stmt);
1820 1757
1821 values->reserve (3);
1822
1823 if (TREE_CODE (divisor) == SSA_NAME) 1758 if (TREE_CODE (divisor) == SSA_NAME)
1824 /* Check for the case where the divisor is the same value most 1759 /* Check for the case where the divisor is the same value most
1825 of the time. */ 1760 of the time. */
1826 values->quick_push (gimple_alloc_histogram_value (cfun, 1761 values->safe_push (gimple_alloc_histogram_value (cfun,
1827 HIST_TYPE_SINGLE_VALUE, 1762 HIST_TYPE_TOPN_VALUES,
1828 stmt, divisor)); 1763 stmt, divisor));
1829 1764
1830 /* For mod, check whether it is not often a noop (or replaceable by 1765 /* For mod, check whether it is not often a noop (or replaceable by
1831 a few subtractions). */ 1766 a few subtractions). */
1832 if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR 1767 if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
1833 && TYPE_UNSIGNED (type) 1768 && TYPE_UNSIGNED (type)
1834 && TREE_CODE (divisor) == SSA_NAME) 1769 && TREE_CODE (divisor) == SSA_NAME)
1835 { 1770 {
1836 tree val; 1771 tree val;
1837 /* Check for a special case where the divisor is power of 2. */ 1772 /* Check for a special case where the divisor is power of 2. */
1838 values->quick_push (gimple_alloc_histogram_value (cfun, 1773 values->safe_push (gimple_alloc_histogram_value (cfun,
1839 HIST_TYPE_POW2, 1774 HIST_TYPE_POW2,
1840 stmt, divisor)); 1775 stmt, divisor));
1841
1842 val = build2 (TRUNC_DIV_EXPR, type, op0, divisor); 1776 val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1843 hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL, 1777 hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1844 stmt, val); 1778 stmt, val);
1845 hist->hdata.intvl.int_start = 0; 1779 hist->hdata.intvl.int_start = 0;
1846 hist->hdata.intvl.steps = 2; 1780 hist->hdata.intvl.steps = 2;
1847 values->quick_push (hist); 1781 values->safe_push (hist);
1848 } 1782 }
1849 return; 1783 return;
1850 1784
1851 default: 1785 default:
1852 return; 1786 return;
1865 || gimple_call_internal_p (stmt) 1799 || gimple_call_internal_p (stmt)
1866 || gimple_call_fndecl (stmt) != NULL_TREE) 1800 || gimple_call_fndecl (stmt) != NULL_TREE)
1867 return; 1801 return;
1868 1802
1869 callee = gimple_call_fn (stmt); 1803 callee = gimple_call_fn (stmt);
1870 1804 histogram_value v = gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1871 values->reserve (3); 1805 stmt, callee);
1872 1806 values->safe_push (v);
1873 values->quick_push (gimple_alloc_histogram_value (
1874 cfun,
1875 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE) ?
1876 HIST_TYPE_INDIR_CALL_TOPN :
1877 HIST_TYPE_INDIR_CALL,
1878 stmt, callee));
1879 1807
1880 return; 1808 return;
1881 } 1809 }
1882 1810
1883 /* Find values inside STMT for that we want to measure histograms for 1811 /* Find values inside STMT for that we want to measure histograms for
1905 blck_size = gimple_call_arg (stmt, size_arg); 1833 blck_size = gimple_call_arg (stmt, size_arg);
1906 1834
1907 if (TREE_CODE (blck_size) != INTEGER_CST) 1835 if (TREE_CODE (blck_size) != INTEGER_CST)
1908 { 1836 {
1909 values->safe_push (gimple_alloc_histogram_value (cfun, 1837 values->safe_push (gimple_alloc_histogram_value (cfun,
1910 HIST_TYPE_SINGLE_VALUE, 1838 HIST_TYPE_TOPN_VALUES,
1911 stmt, blck_size)); 1839 stmt, blck_size));
1912 values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE, 1840 values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1913 stmt, blck_size)); 1841 stmt, blck_size));
1914 } 1842 }
1915 1843
1940 1868
1941 FOR_EACH_BB_FN (bb, cfun) 1869 FOR_EACH_BB_FN (bb, cfun)
1942 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1870 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1943 gimple_values_to_profile (gsi_stmt (gsi), values); 1871 gimple_values_to_profile (gsi_stmt (gsi), values);
1944 1872
1945 values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_TIME_PROFILE, 0, 0)); 1873 values->safe_push (gimple_alloc_histogram_value (cfun,
1874 HIST_TYPE_TIME_PROFILE));
1946 1875
1947 FOR_EACH_VEC_ELT (*values, i, hist) 1876 FOR_EACH_VEC_ELT (*values, i, hist)
1948 { 1877 {
1949 switch (hist->type) 1878 switch (hist->type)
1950 { 1879 {
1954 1883
1955 case HIST_TYPE_POW2: 1884 case HIST_TYPE_POW2:
1956 hist->n_counters = 2; 1885 hist->n_counters = 2;
1957 break; 1886 break;
1958 1887
1959 case HIST_TYPE_SINGLE_VALUE: 1888 case HIST_TYPE_TOPN_VALUES:
1960 hist->n_counters = 3; 1889 case HIST_TYPE_INDIR_CALL:
1961 break; 1890 hist->n_counters = GCOV_TOPN_VALUES_COUNTERS;
1962
1963 case HIST_TYPE_INDIR_CALL:
1964 hist->n_counters = 3;
1965 break; 1891 break;
1966 1892
1967 case HIST_TYPE_TIME_PROFILE: 1893 case HIST_TYPE_TIME_PROFILE:
1968 hist->n_counters = 1; 1894 hist->n_counters = 1;
1969 break; 1895 break;
1973 break; 1899 break;
1974 1900
1975 case HIST_TYPE_IOR: 1901 case HIST_TYPE_IOR:
1976 hist->n_counters = 1; 1902 hist->n_counters = 1;
1977 break; 1903 break;
1978
1979 case HIST_TYPE_INDIR_CALL_TOPN:
1980 hist->n_counters = GCOV_ICALL_TOPN_NCOUNTS;
1981 break;
1982 1904
1983 default: 1905 default:
1984 gcc_unreachable (); 1906 gcc_unreachable ();
1985 } 1907 }
1986 if (dump_file && hist->hvalue.stmt != NULL) 1908 if (dump_file && hist->hvalue.stmt != NULL)