1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2020 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
31 #include "data-streamer.h"
32 #include "diagnostic.h"
33 #include "fold-const.h"
34 #include "tree-nested.h"
37 #include "value-prof.h"
40 #include "gimple-iterator.h"
42 #include "gimple-pretty-print.h"
46 /* In this file value profile based optimizations are placed. Currently the
47 following optimizations are implemented (for more detailed descriptions
48 see comments at value_profile_transformations):
50 1) Division/modulo specialization. Provided that we can determine that the
51 operands of the division have some special properties, we may use it to
52 produce more effective code.
54 2) Indirect/virtual call specialization. If we can determine most
55 common function callee in indirect/virtual call. We can use this
56 information to improve code effectiveness (especially info for
59 3) Speculative prefetching. If we are able to determine that the difference
60 between addresses accessed by a memory reference is usually constant, we
61 may add the prefetch instructions.
62 FIXME: This transformation was removed together with RTL based value
66 Value profiling internals
67 ==========================
69 Every value profiling transformation starts with defining what values
70 to profile. There are different histogram types (see HIST_TYPE_* in
71 value-prof.h) and each transformation can request one or more histogram
72 types per GIMPLE statement. The function gimple_find_values_to_profile()
73 collects the values to profile in a vec, and adds the number of counters
74 required for the different histogram types.
76 For a -fprofile-generate run, the statements for which values should be
77 recorded, are instrumented in instrument_values(). The instrumentation
78 is done by helper functions that can be found in tree-profile.c, where
79 new types of histograms can be added if necessary.
81 After a -fprofile-use, the value profiling data is read back in by
82 compute_value_histograms() that translates the collected data to
83 histograms and attaches them to the profiled statements via
84 gimple_add_histogram_value(). Histograms are stored in a hash table
85 that is attached to every intrumented function, see VALUE_HISTOGRAMS
88 The value-profile transformations driver is the function
89 gimple_value_profile_transformations(). It traverses all statements in
90 the to-be-transformed function, and looks for statements with one or
91 more histograms attached to it. If a statement has histograms, the
92 transformation functions are called on the statement.
94 Limitations / FIXME / TODO:
95 * Only one histogram of each type can be associated with a statement.
96 * Some value profile transformations are done in builtins.c (?!)
97 * Updating of histograms needs some TLC.
98 * The value profiling code could be used to record analysis results
99 from non-profiling (e.g. VRP).
100 * Adding new profilers should be simplified, starting with a cleanup
101 of what-happens-where and with making gimple_find_values_to_profile
102 and gimple_value_profile_transformations table-driven, perhaps...
105 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
106 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
107 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
108 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
109 static void dump_ic_profile (gimple_stmt_iterator
*gsi
);
111 /* Allocate histogram value. */
114 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
115 enum hist_type type
, gimple
*stmt
, tree value
)
117 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
118 hist
->hvalue
.value
= value
;
119 hist
->hvalue
.stmt
= stmt
;
124 /* Hash value for histogram. */
127 histogram_hash (const void *x
)
129 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
132 /* Return nonzero if statement for histogram_value X is Y. */
135 histogram_eq (const void *x
, const void *y
)
137 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const gimple
*) y
;
140 /* Set histogram for STMT. */
143 set_histogram_value (struct function
*fun
, gimple
*stmt
, histogram_value hist
)
146 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
148 if (!VALUE_HISTOGRAMS (fun
))
149 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
151 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
152 htab_hash_pointer (stmt
),
153 hist
? INSERT
: NO_INSERT
);
157 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
163 /* Get histogram list for STMT. */
166 gimple_histogram_value (struct function
*fun
, gimple
*stmt
)
168 if (!VALUE_HISTOGRAMS (fun
))
170 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
171 htab_hash_pointer (stmt
));
174 /* Add histogram for STMT. */
177 gimple_add_histogram_value (struct function
*fun
, gimple
*stmt
,
178 histogram_value hist
)
180 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
181 set_histogram_value (fun
, stmt
, hist
);
185 /* Remove histogram HIST from STMT's histogram list. */
188 gimple_remove_histogram_value (struct function
*fun
, gimple
*stmt
,
189 histogram_value hist
)
191 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
194 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
198 while (hist2
->hvalue
.next
!= hist
)
199 hist2
= hist2
->hvalue
.next
;
200 hist2
->hvalue
.next
= hist
->hvalue
.next
;
202 free (hist
->hvalue
.counters
);
204 memset (hist
, 0xab, sizeof (*hist
));
208 /* Lookup histogram of type TYPE in the STMT. */
211 gimple_histogram_value_of_type (struct function
*fun
, gimple
*stmt
,
214 histogram_value hist
;
215 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
216 hist
= hist
->hvalue
.next
)
217 if (hist
->type
== type
)
222 /* Dump information about HIST to DUMP_FILE. */
225 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
229 case HIST_TYPE_INTERVAL
:
230 if (hist
->hvalue
.counters
)
232 fprintf (dump_file
, "Interval counter range [%d,%d]: [",
233 hist
->hdata
.intvl
.int_start
,
234 (hist
->hdata
.intvl
.int_start
235 + hist
->hdata
.intvl
.steps
- 1));
238 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
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
, ", ");
246 fprintf (dump_file
, "] outside range: %" PRId64
".\n",
247 (int64_t) hist
->hvalue
.counters
[i
]);
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]);
259 case HIST_TYPE_TOPN_VALUES
:
260 case HIST_TYPE_INDIR_CALL
:
261 if (hist
->hvalue
.counters
)
264 (hist
->type
== HIST_TYPE_TOPN_VALUES
265 ? "Top N value counter" : "Indirect call counter"));
266 if (hist
->hvalue
.counters
)
268 unsigned count
= hist
->hvalue
.counters
[1];
269 fprintf (dump_file
, " all: %" PRId64
", %" PRId64
" values: ",
270 (int64_t) hist
->hvalue
.counters
[0], (int64_t) count
);
271 for (unsigned i
= 0; i
< count
; i
++)
273 fprintf (dump_file
, "[%" PRId64
":%" PRId64
"]",
274 (int64_t) hist
->hvalue
.counters
[2 * i
+ 2],
275 (int64_t) hist
->hvalue
.counters
[2 * i
+ 3]);
277 fprintf (dump_file
, ", ");
279 fprintf (dump_file
, ".\n");
284 case HIST_TYPE_AVERAGE
:
285 if (hist
->hvalue
.counters
)
286 fprintf (dump_file
, "Average value sum:%" PRId64
287 " times:%" PRId64
".\n",
288 (int64_t) hist
->hvalue
.counters
[0],
289 (int64_t) hist
->hvalue
.counters
[1]);
293 if (hist
->hvalue
.counters
)
294 fprintf (dump_file
, "IOR value ior:%" PRId64
".\n",
295 (int64_t) hist
->hvalue
.counters
[0]);
298 case HIST_TYPE_TIME_PROFILE
:
299 if (hist
->hvalue
.counters
)
300 fprintf (dump_file
, "Time profile time:%" PRId64
".\n",
301 (int64_t) hist
->hvalue
.counters
[0]);
308 /* Dump information about HIST to DUMP_FILE. */
311 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
316 bp
= bitpack_create (ob
->main_stream
);
317 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
318 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
319 streamer_write_bitpack (&bp
);
322 case HIST_TYPE_INTERVAL
:
323 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
324 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
329 for (i
= 0; i
< hist
->n_counters
; i
++)
331 /* When user uses an unsigned type with a big value, constant converted
332 to gcov_type (a signed type) can be negative. */
333 gcov_type value
= hist
->hvalue
.counters
[i
];
334 if (hist
->type
== HIST_TYPE_TOPN_VALUES
)
337 gcc_assert (value
>= 0);
339 streamer_write_gcov_count (ob
, value
);
341 if (hist
->hvalue
.next
)
342 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
345 /* Dump information about HIST to DUMP_FILE. */
348 stream_in_histogram_value (class lto_input_block
*ib
, gimple
*stmt
)
351 unsigned int ncounters
= 0;
354 histogram_value new_val
;
356 histogram_value
*next_p
= NULL
;
360 bp
= streamer_read_bitpack (ib
);
361 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
362 next
= bp_unpack_value (&bp
, 1);
363 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
);
366 case HIST_TYPE_INTERVAL
:
367 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
368 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
369 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
373 case HIST_TYPE_AVERAGE
:
377 case HIST_TYPE_TOPN_VALUES
:
378 case HIST_TYPE_INDIR_CALL
:
382 case HIST_TYPE_TIME_PROFILE
:
390 /* TOP N counters have variable number of counters. */
391 if (type
== HIST_TYPE_INDIR_CALL
|| type
== HIST_TYPE_TOPN_VALUES
)
393 gcov_type total
= streamer_read_gcov_count (ib
);
394 gcov_type ncounters
= streamer_read_gcov_count (ib
);
395 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
,
396 sizeof (*new_val
->hvalue
.counters
)
397 * (2 + 2 * ncounters
));
398 new_val
->hvalue
.counters
[0] = total
;
399 new_val
->hvalue
.counters
[1] = ncounters
;
400 new_val
->n_counters
= 2 + 2 * ncounters
;
401 for (i
= 0; i
< 2 * ncounters
; i
++)
402 new_val
->hvalue
.counters
[2 + i
] = streamer_read_gcov_count (ib
);
406 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
,
407 sizeof (*new_val
->hvalue
.counters
)
409 new_val
->n_counters
= ncounters
;
410 for (i
= 0; i
< ncounters
; i
++)
411 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
415 gimple_add_histogram_value (cfun
, stmt
, new_val
);
418 next_p
= &new_val
->hvalue
.next
;
423 /* Dump all histograms attached to STMT to DUMP_FILE. */
426 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
428 histogram_value hist
;
429 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
430 dump_histogram_value (dump_file
, hist
);
433 /* Remove all histograms associated with STMT. */
436 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
439 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
440 gimple_remove_histogram_value (fun
, stmt
, val
);
443 /* Duplicate all histograms associates with OSTMT to STMT. */
446 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
447 struct function
*ofun
, gimple
*ostmt
)
450 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
452 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
);
453 memcpy (new_val
, val
, sizeof (*val
));
454 new_val
->hvalue
.stmt
= stmt
;
455 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
456 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
457 gimple_add_histogram_value (fun
, stmt
, new_val
);
461 /* Move all histograms associated with OSTMT to STMT. */
464 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
466 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
469 /* The following three statements can't be reordered,
470 because histogram hashtab relies on stmt field value
471 for finding the exact slot. */
472 set_histogram_value (fun
, ostmt
, NULL
);
473 for (; val
!= NULL
; val
= val
->hvalue
.next
)
474 val
->hvalue
.stmt
= stmt
;
475 set_histogram_value (fun
, stmt
, val
);
479 static bool error_found
= false;
481 /* Helper function for verify_histograms. For each histogram reachable via htab
482 walk verify that it was reached via statement walk. */
485 visit_hist (void **slot
, void *data
)
487 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
488 histogram_value hist
= *(histogram_value
*) slot
;
490 if (!visited
->contains (hist
)
491 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
493 error ("dead histogram");
494 dump_histogram_value (stderr
, hist
);
495 debug_gimple_stmt (hist
->hvalue
.stmt
);
501 /* Verify sanity of the histograms. */
504 verify_histograms (void)
507 gimple_stmt_iterator gsi
;
508 histogram_value hist
;
511 hash_set
<histogram_value
> visited_hists
;
512 FOR_EACH_BB_FN (bb
, cfun
)
513 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
515 gimple
*stmt
= gsi_stmt (gsi
);
517 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
518 hist
= hist
->hvalue
.next
)
520 if (hist
->hvalue
.stmt
!= stmt
)
522 error ("histogram value statement does not correspond to "
523 "the statement it is associated with");
524 debug_gimple_stmt (stmt
);
525 dump_histogram_value (stderr
, hist
);
528 visited_hists
.add (hist
);
531 if (VALUE_HISTOGRAMS (cfun
))
532 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
534 internal_error ("%qs failed", __func__
);
537 /* Helper function for verify_histograms. For each histogram reachable via htab
538 walk verify that it was reached via statement walk. */
541 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
543 histogram_value hist
= *(histogram_value
*) slot
;
544 free (hist
->hvalue
.counters
);
550 free_histograms (struct function
*fn
)
552 if (VALUE_HISTOGRAMS (fn
))
554 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
555 htab_delete (VALUE_HISTOGRAMS (fn
));
556 VALUE_HISTOGRAMS (fn
) = NULL
;
560 /* The overall number of invocations of the counter should match
561 execution count of basic block. Report it as error rather than
562 internal error as it might mean that user has misused the profile
566 check_counter (gimple
*stmt
, const char * name
,
567 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
569 gcov_type bb_count
= bb_count_d
.ipa ().to_gcov_type ();
570 if (*all
!= bb_count
|| *count
> *all
)
572 dump_user_location_t locus
;
573 locus
= ((stmt
!= NULL
)
574 ? dump_user_location_t (stmt
)
575 : dump_user_location_t::from_function_decl
576 (current_function_decl
));
577 if (flag_profile_correction
)
579 if (dump_enabled_p ())
580 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
581 "correcting inconsistent value profile: %s "
582 "profiler overall count (%d) does not match BB "
583 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
591 error_at (locus
.get_location_t (), "corrupted value profile: %s "
592 "profile counter (%d out of %d) inconsistent with "
593 "basic-block count (%d)",
605 /* GIMPLE based transformations. */
608 gimple_value_profile_transformations (void)
611 gimple_stmt_iterator gsi
;
612 bool changed
= false;
614 FOR_EACH_BB_FN (bb
, cfun
)
616 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
618 gimple
*stmt
= gsi_stmt (gsi
);
619 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
625 fprintf (dump_file
, "Trying transformations on stmt ");
626 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
627 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
630 /* Transformations: */
631 /* The order of things in this conditional controls which
632 transformation is used when more than one is applicable. */
633 /* It is expected that any code added by the transformations
634 will be added before the current statement, and that the
635 current statement remain valid (although possibly
636 modified) upon return. */
637 if (gimple_mod_subtract_transform (&gsi
)
638 || gimple_divmod_fixed_value_transform (&gsi
)
639 || gimple_mod_pow2_value_transform (&gsi
)
640 || gimple_stringops_transform (&gsi
))
642 stmt
= gsi_stmt (gsi
);
644 /* Original statement may no longer be in the same block. */
645 if (bb
!= gimple_bb (stmt
))
647 bb
= gimple_bb (stmt
);
648 gsi
= gsi_for_stmt (stmt
);
652 /* The function never thansforms a GIMPLE statement. */
653 if (dump_enabled_p ())
654 dump_ic_profile (&gsi
);
661 /* Generate code for transformation 1 (with parent gimple assignment
662 STMT and probability of taking the optimal path PROB, which is
663 equivalent to COUNT/ALL within roundoff error). This generates the
664 result into a temp and returns the temp; it does not replace or
665 alter the original STMT. */
668 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, profile_probability prob
,
669 gcov_type count
, gcov_type all
)
671 gassign
*stmt1
, *stmt2
;
673 tree tmp0
, tmp1
, tmp2
;
674 gimple
*bb1end
, *bb2end
, *bb3end
;
675 basic_block bb
, bb2
, bb3
, bb4
;
676 tree optype
, op1
, op2
;
677 edge e12
, e13
, e23
, e24
, e34
;
678 gimple_stmt_iterator gsi
;
680 gcc_assert (is_gimple_assign (stmt
)
681 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
682 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
684 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
685 op1
= gimple_assign_rhs1 (stmt
);
686 op2
= gimple_assign_rhs2 (stmt
);
688 bb
= gimple_bb (stmt
);
689 gsi
= gsi_for_stmt (stmt
);
691 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
692 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
693 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
694 stmt2
= gimple_build_assign (tmp1
, op2
);
695 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
696 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
697 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
698 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
701 tmp2
= create_tmp_reg (optype
, "PROF");
702 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
703 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
706 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
707 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
711 /* Edge e23 connects bb2 to bb3, etc. */
712 e12
= split_block (bb
, bb1end
);
714 bb2
->count
= profile_count::from_gcov_type (count
);
715 e23
= split_block (bb2
, bb2end
);
717 bb3
->count
= profile_count::from_gcov_type (all
- count
);
718 e34
= split_block (bb3
, bb3end
);
720 bb4
->count
= profile_count::from_gcov_type (all
);
722 e12
->flags
&= ~EDGE_FALLTHRU
;
723 e12
->flags
|= EDGE_FALSE_VALUE
;
724 e12
->probability
= prob
;
726 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
727 e13
->probability
= prob
.invert ();
731 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
732 e24
->probability
= profile_probability::always ();
734 e34
->probability
= profile_probability::always ();
739 /* Return the n-th value count of TOPN_VALUE histogram. If
740 there's a value, return true and set VALUE and COUNT
743 Counters have the following meaning.
745 abs (counters[0]) is the number of executions
746 for i in 0 ... TOPN-1
747 counters[2 * i + 1] is target
748 abs (counters[2 * i + 2]) is corresponding hitrate counter.
750 Value of counters[0] negative when counter became
751 full during merging and some values are lost. */
754 get_nth_most_common_value (gimple
*stmt
, const char *counter_type
,
755 histogram_value hist
, gcov_type
*value
,
756 gcov_type
*count
, gcov_type
*all
, unsigned n
)
758 unsigned counters
= hist
->hvalue
.counters
[1];
765 gcov_type read_all
= abs_hwi (hist
->hvalue
.counters
[0]);
767 gcov_type v
= hist
->hvalue
.counters
[2 * n
+ 2];
768 gcov_type c
= hist
->hvalue
.counters
[2 * n
+ 3];
770 if (hist
->hvalue
.counters
[0] < 0
771 && (flag_profile_reproducible
== PROFILE_REPRODUCIBILITY_PARALLEL_RUNS
772 || (flag_profile_reproducible
773 == PROFILE_REPRODUCIBILITY_MULTITHREADED
)))
776 /* Indirect calls can't be verified. */
778 && check_counter (stmt
, counter_type
, &c
, &read_all
,
779 gimple_bb (stmt
)->count
))
789 /* Do transform 1) on INSN if applicable. */
792 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
794 histogram_value histogram
;
796 gcov_type val
, count
, all
;
797 tree result
, value
, tree_val
;
798 profile_probability prob
;
801 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
805 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
808 code
= gimple_assign_rhs_code (stmt
);
810 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
813 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
814 HIST_TYPE_TOPN_VALUES
);
818 if (!get_nth_most_common_value (stmt
, "divmod", histogram
, &val
, &count
,
822 value
= histogram
->hvalue
.value
;
823 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
825 /* We require that count is at least half of all. */
826 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
828 || optimize_bb_for_size_p (gimple_bb (stmt
)))
831 /* Compute probability of taking the optimal path. */
833 prob
= profile_probability::probability_in_gcov_type (count
, all
);
835 prob
= profile_probability::never ();
837 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
838 tree_val
= build_int_cst (get_gcov_type (), val
);
842 a
[0] = (unsigned HOST_WIDE_INT
) val
;
843 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
845 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
846 TYPE_PRECISION (get_gcov_type ()), false));
848 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
850 if (dump_enabled_p ())
851 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
852 "Transformation done: div/mod by constant %T\n", tree_val
);
854 gimple_assign_set_rhs_from_tree (si
, result
);
855 update_stmt (gsi_stmt (*si
));
860 /* Generate code for transformation 2 (with parent gimple assign STMT and
861 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
862 within roundoff error). This generates the result into a temp and returns
863 the temp; it does not replace or alter the original STMT. */
866 gimple_mod_pow2 (gassign
*stmt
, profile_probability prob
, gcov_type count
, gcov_type all
)
868 gassign
*stmt1
, *stmt2
, *stmt3
;
871 gimple
*bb1end
, *bb2end
, *bb3end
;
872 basic_block bb
, bb2
, bb3
, bb4
;
873 tree optype
, op1
, op2
;
874 edge e12
, e13
, e23
, e24
, e34
;
875 gimple_stmt_iterator gsi
;
878 gcc_assert (is_gimple_assign (stmt
)
879 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
881 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
882 op1
= gimple_assign_rhs1 (stmt
);
883 op2
= gimple_assign_rhs2 (stmt
);
885 bb
= gimple_bb (stmt
);
886 gsi
= gsi_for_stmt (stmt
);
888 result
= create_tmp_reg (optype
, "PROF");
889 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
890 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
891 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
892 build_int_cst (optype
, -1));
893 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
894 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
895 NULL_TREE
, NULL_TREE
);
896 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
897 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
898 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
901 /* tmp2 == op2-1 inherited from previous block. */
902 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
903 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
906 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
908 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
912 /* Edge e23 connects bb2 to bb3, etc. */
913 e12
= split_block (bb
, bb1end
);
915 bb2
->count
= profile_count::from_gcov_type (count
);
916 e23
= split_block (bb2
, bb2end
);
918 bb3
->count
= profile_count::from_gcov_type (all
- count
);
919 e34
= split_block (bb3
, bb3end
);
921 bb4
->count
= profile_count::from_gcov_type (all
);
923 e12
->flags
&= ~EDGE_FALLTHRU
;
924 e12
->flags
|= EDGE_FALSE_VALUE
;
925 e12
->probability
= prob
;
927 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
928 e13
->probability
= prob
.invert ();
932 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
933 e24
->probability
= profile_probability::always ();
935 e34
->probability
= profile_probability::always ();
940 /* Do transform 2) on INSN if applicable. */
943 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
945 histogram_value histogram
;
947 gcov_type count
, wrong_values
, all
;
948 tree lhs_type
, result
, value
;
949 profile_probability prob
;
952 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
956 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
957 if (!INTEGRAL_TYPE_P (lhs_type
))
960 code
= gimple_assign_rhs_code (stmt
);
962 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
965 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
969 value
= histogram
->hvalue
.value
;
970 wrong_values
= histogram
->hvalue
.counters
[0];
971 count
= histogram
->hvalue
.counters
[1];
973 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
975 /* We require that we hit a power of 2 at least half of all evaluations. */
976 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
977 || count
< wrong_values
978 || optimize_bb_for_size_p (gimple_bb (stmt
)))
981 /* Compute probability of taking the optimal path. */
982 all
= count
+ wrong_values
;
984 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
987 if (dump_enabled_p ())
988 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
989 "Transformation done: mod power of 2\n");
992 prob
= profile_probability::probability_in_gcov_type (count
, all
);
994 prob
= profile_probability::never ();
996 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
998 gimple_assign_set_rhs_from_tree (si
, result
);
999 update_stmt (gsi_stmt (*si
));
1004 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1005 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1006 supported and this is built into this interface. The probabilities of taking
1007 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1008 COUNT2/ALL respectively within roundoff error). This generates the
1009 result into a temp and returns the temp; it does not replace or alter
1010 the original STMT. */
1011 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1014 gimple_mod_subtract (gassign
*stmt
, profile_probability prob1
,
1015 profile_probability prob2
, int ncounts
,
1016 gcov_type count1
, gcov_type count2
, gcov_type all
)
1022 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
1023 basic_block bb
, bb2
, bb3
, bb4
;
1024 tree optype
, op1
, op2
;
1025 edge e12
, e23
= 0, e24
, e34
, e14
;
1026 gimple_stmt_iterator gsi
;
1029 gcc_assert (is_gimple_assign (stmt
)
1030 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1032 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1033 op1
= gimple_assign_rhs1 (stmt
);
1034 op2
= gimple_assign_rhs2 (stmt
);
1036 bb
= gimple_bb (stmt
);
1037 gsi
= gsi_for_stmt (stmt
);
1039 result
= create_tmp_reg (optype
, "PROF");
1040 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1041 stmt1
= gimple_build_assign (result
, op1
);
1042 stmt2
= gimple_build_assign (tmp1
, op2
);
1043 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1044 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1045 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1046 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1049 if (ncounts
) /* Assumed to be 0 or 1 */
1051 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1052 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1053 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1054 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1058 /* Fallback case. */
1059 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1061 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1065 /* Edge e23 connects bb2 to bb3, etc. */
1066 /* However block 3 is optional; if it is not there, references
1067 to 3 really refer to block 2. */
1068 e12
= split_block (bb
, bb1end
);
1070 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1072 if (ncounts
) /* Assumed to be 0 or 1. */
1074 e23
= split_block (bb2
, bb2end
);
1076 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1079 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1081 bb4
->count
= profile_count::from_gcov_type (all
);
1083 e12
->flags
&= ~EDGE_FALLTHRU
;
1084 e12
->flags
|= EDGE_FALSE_VALUE
;
1085 e12
->probability
= prob1
.invert ();
1087 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1088 e14
->probability
= prob1
;
1090 if (ncounts
) /* Assumed to be 0 or 1. */
1092 e23
->flags
&= ~EDGE_FALLTHRU
;
1093 e23
->flags
|= EDGE_FALSE_VALUE
;
1094 e23
->probability
= prob2
.invert ();
1096 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1097 e24
->probability
= prob2
;
1100 e34
->probability
= profile_probability::always ();
1105 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1108 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1110 histogram_value histogram
;
1111 enum tree_code code
;
1112 gcov_type count
, wrong_values
, all
;
1113 tree lhs_type
, result
;
1114 profile_probability prob1
, prob2
;
1115 unsigned int i
, steps
;
1116 gcov_type count1
, count2
;
1118 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1122 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1123 if (!INTEGRAL_TYPE_P (lhs_type
))
1126 code
= gimple_assign_rhs_code (stmt
);
1128 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1131 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1137 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1138 all
+= histogram
->hvalue
.counters
[i
];
1140 wrong_values
+= histogram
->hvalue
.counters
[i
];
1141 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1142 steps
= histogram
->hdata
.intvl
.steps
;
1143 all
+= wrong_values
;
1144 count1
= histogram
->hvalue
.counters
[0];
1145 count2
= histogram
->hvalue
.counters
[1];
1147 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1149 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1153 if (flag_profile_correction
&& count1
+ count2
> all
)
1154 all
= count1
+ count2
;
1156 gcc_assert (count1
+ count2
<= all
);
1158 /* We require that we use just subtractions in at least 50% of all
1161 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1163 count
+= histogram
->hvalue
.counters
[i
];
1164 if (count
* 2 >= all
)
1168 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1171 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1172 if (dump_enabled_p ())
1173 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1174 "Transformation done: mod subtract\n");
1176 /* Compute probability of taking the optimal path(s). */
1179 prob1
= profile_probability::probability_in_gcov_type (count1
, all
);
1180 prob2
= profile_probability::probability_in_gcov_type (count2
, all
);
1184 prob1
= prob2
= profile_probability::never ();
1187 /* In practice, "steps" is always 2. This interface reflects this,
1188 and will need to be changed if "steps" can change. */
1189 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1191 gimple_assign_set_rhs_from_tree (si
, result
);
1192 update_stmt (gsi_stmt (*si
));
1197 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1199 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1201 /* Returns true if node graph is initialized. This
1202 is used to test if profile_id has been created
1203 for cgraph_nodes. */
1206 coverage_node_map_initialized_p (void)
1208 return cgraph_node_map
!= 0;
1211 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1212 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1213 that the PROFILE_IDs was already assigned. */
1216 init_node_map (bool local
)
1218 struct cgraph_node
*n
;
1219 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1221 FOR_EACH_DEFINED_FUNCTION (n
)
1222 if (n
->has_gimple_body_p () || n
->thunk
.thunk_p
)
1225 dump_user_location_t loc
1226 = dump_user_location_t::from_function_decl (n
->decl
);
1229 n
->profile_id
= coverage_compute_profile_id (n
);
1230 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1233 if (dump_enabled_p ())
1234 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1235 "Local profile-id %i conflict"
1236 " with nodes %s %s\n",
1239 (*val
)->dump_name ());
1240 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1243 else if (!n
->profile_id
)
1245 if (dump_enabled_p ())
1246 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1247 "Node %s has no profile-id"
1248 " (profile feedback missing?)\n",
1252 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1254 if (dump_enabled_p ())
1255 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1256 "Node %s has IP profile-id %i conflict. "
1258 n
->dump_name (), n
->profile_id
);
1262 cgraph_node_map
->put (n
->profile_id
, n
);
1266 /* Delete the CGRAPH_NODE_MAP. */
1271 delete cgraph_node_map
;
1274 /* Return cgraph node for function with pid */
1277 find_func_by_profile_id (int profile_id
)
1279 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1286 /* Do transformation
1288 if (actual_callee_address == address_of_most_common_function/method)
1295 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1296 profile_probability prob
)
1301 tree tmp0
, tmp1
, tmp
;
1302 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1303 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1304 gimple_stmt_iterator gsi
;
1309 cond_bb
= gimple_bb (icall_stmt
);
1310 gsi
= gsi_for_stmt (icall_stmt
);
1312 tmp0
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1313 tmp1
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1314 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1315 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1316 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1318 tmp
= fold_convert (ptr_type_node
, build_addr (direct_call
->decl
));
1319 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1320 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1322 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1323 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1325 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1327 unlink_stmt_vdef (icall_stmt
);
1328 release_ssa_name (gimple_vdef (icall_stmt
));
1330 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1331 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1332 update_stmt (icall_stmt
);
1333 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1334 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1335 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1336 if ((dflags
& ECF_NORETURN
) != 0
1337 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1338 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1339 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1342 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1343 e_cd
= split_block (cond_bb
, cond_stmt
);
1344 dcall_bb
= e_cd
->dest
;
1345 dcall_bb
->count
= cond_bb
->count
.apply_probability (prob
);
1347 e_di
= split_block (dcall_bb
, dcall_stmt
);
1348 icall_bb
= e_di
->dest
;
1349 icall_bb
->count
= cond_bb
->count
- dcall_bb
->count
;
1351 /* Do not disturb existing EH edges from the indirect call. */
1352 if (!stmt_ends_bb_p (icall_stmt
))
1353 e_ij
= split_block (icall_bb
, icall_stmt
);
1356 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1357 /* The indirect call might be noreturn. */
1360 e_ij
->probability
= profile_probability::always ();
1361 e_ij
= single_pred_edge (split_edge (e_ij
));
1366 join_bb
= e_ij
->dest
;
1367 join_bb
->count
= cond_bb
->count
;
1370 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1371 e_cd
->probability
= prob
;
1373 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1374 e_ci
->probability
= prob
.invert ();
1380 if ((dflags
& ECF_NORETURN
) == 0)
1382 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1383 e_dj
->probability
= profile_probability::always ();
1385 e_ij
->probability
= profile_probability::always ();
1388 /* Insert PHI node for the call result if necessary. */
1389 if (gimple_call_lhs (icall_stmt
)
1390 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1391 && (dflags
& ECF_NORETURN
) == 0)
1393 tree result
= gimple_call_lhs (icall_stmt
);
1394 gphi
*phi
= create_phi_node (result
, join_bb
);
1395 gimple_call_set_lhs (icall_stmt
,
1396 duplicate_ssa_name (result
, icall_stmt
));
1397 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1398 gimple_call_set_lhs (dcall_stmt
,
1399 duplicate_ssa_name (result
, dcall_stmt
));
1400 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1403 /* Build an EH edge for the direct call if necessary. */
1404 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1405 if (lp_nr
> 0 && stmt_could_throw_p (cfun
, dcall_stmt
))
1407 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1410 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1411 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1413 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1414 e
->probability
= e_eh
->probability
;
1415 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1416 !gsi_end_p (psi
); gsi_next (&psi
))
1418 gphi
*phi
= psi
.phi ();
1419 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1420 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1423 if (!stmt_could_throw_p (cfun
, dcall_stmt
))
1424 gimple_purge_dead_eh_edges (dcall_bb
);
1428 /* Dump info about indirect call profile. */
1431 dump_ic_profile (gimple_stmt_iterator
*gsi
)
1434 histogram_value histogram
;
1435 gcov_type val
, count
, all
;
1436 struct cgraph_node
*direct_call
;
1438 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1442 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1445 if (gimple_call_internal_p (stmt
))
1448 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1453 all
= histogram
->hvalue
.counters
[0];
1455 for (unsigned j
= 0; j
< GCOV_TOPN_MAXIMUM_TRACKED_VALUES
; j
++)
1457 if (!get_nth_most_common_value (NULL
, "indirect call", histogram
, &val
,
1463 direct_call
= find_func_by_profile_id ((int) val
);
1465 if (direct_call
== NULL
)
1467 MSG_MISSED_OPTIMIZATION
, stmt
,
1468 "Indirect call -> direct call from other "
1469 "module %T=> %i (will resolve by ipa-profile only with LTO)\n",
1470 gimple_call_fn (stmt
), (int) val
);
1472 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1473 "Indirect call -> direct call "
1474 "%T => %T (will resolve by ipa-profile)\n",
1475 gimple_call_fn (stmt
), direct_call
->decl
);
1476 dump_printf_loc (MSG_NOTE
, stmt
,
1477 "hist->count %" PRId64
" hist->all %" PRId64
"\n",
1482 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1483 set to the argument index for the size of the string operation. */
1486 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1488 enum built_in_function fcode
;
1490 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1493 case BUILT_IN_MEMCPY
:
1494 case BUILT_IN_MEMPCPY
:
1495 case BUILT_IN_MEMMOVE
:
1497 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1498 INTEGER_TYPE
, VOID_TYPE
);
1499 case BUILT_IN_MEMSET
:
1501 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1502 INTEGER_TYPE
, VOID_TYPE
);
1503 case BUILT_IN_BZERO
:
1505 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1512 /* Convert stringop (..., vcall_size)
1514 if (vcall_size == icall_size)
1515 stringop (..., icall_size);
1517 stringop (..., vcall_size);
1518 assuming we'll propagate a true constant into ICALL_SIZE later. */
1521 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, profile_probability prob
,
1522 gcov_type count
, gcov_type all
)
1527 tree tmp0
, tmp1
, vcall_size
, optype
;
1528 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1529 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1530 gimple_stmt_iterator gsi
;
1533 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1536 cond_bb
= gimple_bb (vcall_stmt
);
1537 gsi
= gsi_for_stmt (vcall_stmt
);
1539 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1540 optype
= TREE_TYPE (vcall_size
);
1542 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1543 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1544 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1545 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1547 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1548 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1550 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1551 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1553 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1555 unlink_stmt_vdef (vcall_stmt
);
1556 release_ssa_name (gimple_vdef (vcall_stmt
));
1558 gimple_set_vdef (vcall_stmt
, NULL
);
1559 gimple_set_vuse (vcall_stmt
, NULL
);
1560 update_stmt (vcall_stmt
);
1561 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1562 gimple_call_set_arg (icall_stmt
, size_arg
,
1563 fold_convert (optype
, icall_size
));
1564 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1567 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1568 e_ci
= split_block (cond_bb
, cond_stmt
);
1569 icall_bb
= e_ci
->dest
;
1570 icall_bb
->count
= profile_count::from_gcov_type (count
);
1572 e_iv
= split_block (icall_bb
, icall_stmt
);
1573 vcall_bb
= e_iv
->dest
;
1574 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1576 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1577 join_bb
= e_vj
->dest
;
1578 join_bb
->count
= profile_count::from_gcov_type (all
);
1580 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1581 e_ci
->probability
= prob
;
1583 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1584 e_cv
->probability
= prob
.invert ();
1588 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1589 e_ij
->probability
= profile_probability::always ();
1591 e_vj
->probability
= profile_probability::always ();
1593 /* Insert PHI node for the call result if necessary. */
1594 if (gimple_call_lhs (vcall_stmt
)
1595 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1597 tree result
= gimple_call_lhs (vcall_stmt
);
1598 gphi
*phi
= create_phi_node (result
, join_bb
);
1599 gimple_call_set_lhs (vcall_stmt
,
1600 duplicate_ssa_name (result
, vcall_stmt
));
1601 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1602 gimple_call_set_lhs (icall_stmt
,
1603 duplicate_ssa_name (result
, icall_stmt
));
1604 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1607 /* Because these are all string op builtins, they're all nothrow. */
1608 gcc_assert (!stmt_could_throw_p (cfun
, vcall_stmt
));
1609 gcc_assert (!stmt_could_throw_p (cfun
, icall_stmt
));
1612 /* Find values inside STMT for that we want to measure histograms for
1613 division/modulo optimization. */
1616 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1620 enum built_in_function fcode
;
1621 histogram_value histogram
;
1622 gcov_type count
, all
, val
;
1624 unsigned int dest_align
, src_align
;
1625 profile_probability prob
;
1629 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1633 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1636 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1639 blck_size
= gimple_call_arg (stmt
, size_arg
);
1640 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1643 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
1644 HIST_TYPE_TOPN_VALUES
);
1648 if (!get_nth_most_common_value (stmt
, "stringops", histogram
, &val
, &count
,
1652 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1654 /* We require that count is at least half of all. */
1655 if (2 * count
< all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1657 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1660 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1662 prob
= profile_probability::never ();
1664 dest
= gimple_call_arg (stmt
, 0);
1665 dest_align
= get_pointer_alignment (dest
);
1666 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1669 case BUILT_IN_MEMCPY
:
1670 case BUILT_IN_MEMPCPY
:
1671 case BUILT_IN_MEMMOVE
:
1672 src
= gimple_call_arg (stmt
, 1);
1673 src_align
= get_pointer_alignment (src
);
1674 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1677 case BUILT_IN_MEMSET
:
1678 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1679 gimple_call_arg (stmt
, 1),
1683 case BUILT_IN_BZERO
:
1684 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1693 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1694 tree_val
= build_int_cst (get_gcov_type (), val
);
1698 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1699 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1701 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1702 TYPE_PRECISION (get_gcov_type ()), false));
1705 if (dump_enabled_p ())
1706 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1707 "Transformation done: single value %i stringop for %s\n",
1708 (int)val
, built_in_names
[(int)fcode
]);
1710 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1716 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1717 HOST_WIDE_INT
*expected_size
)
1719 histogram_value histogram
;
1720 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1723 *expected_size
= -1;
1724 else if (!histogram
->hvalue
.counters
[1])
1726 *expected_size
= -1;
1727 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1732 size
= ((histogram
->hvalue
.counters
[0]
1733 + histogram
->hvalue
.counters
[1] / 2)
1734 / histogram
->hvalue
.counters
[1]);
1735 /* Even if we can hold bigger value in SIZE, INT_MAX
1736 is safe "infinity" for code generation strategies. */
1739 *expected_size
= size
;
1740 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1743 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1746 *expected_align
= 0;
1747 else if (!histogram
->hvalue
.counters
[0])
1749 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1750 *expected_align
= 0;
1755 unsigned int alignment
;
1757 count
= histogram
->hvalue
.counters
[0];
1759 while (!(count
& alignment
)
1760 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1762 *expected_align
= alignment
* BITS_PER_UNIT
;
1763 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1768 /* Find values inside STMT for that we want to measure histograms for
1769 division/modulo optimization. */
1772 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1774 tree lhs
, divisor
, op0
, type
;
1775 histogram_value hist
;
1777 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1780 lhs
= gimple_assign_lhs (stmt
);
1781 type
= TREE_TYPE (lhs
);
1782 if (!INTEGRAL_TYPE_P (type
))
1785 switch (gimple_assign_rhs_code (stmt
))
1787 case TRUNC_DIV_EXPR
:
1788 case TRUNC_MOD_EXPR
:
1789 divisor
= gimple_assign_rhs2 (stmt
);
1790 op0
= gimple_assign_rhs1 (stmt
);
1792 if (TREE_CODE (divisor
) == SSA_NAME
)
1793 /* Check for the case where the divisor is the same value most
1795 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1796 HIST_TYPE_TOPN_VALUES
,
1799 /* For mod, check whether it is not often a noop (or replaceable by
1800 a few subtractions). */
1801 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1802 && TYPE_UNSIGNED (type
)
1803 && TREE_CODE (divisor
) == SSA_NAME
)
1806 /* Check for a special case where the divisor is power of 2. */
1807 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1810 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1811 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1813 hist
->hdata
.intvl
.int_start
= 0;
1814 hist
->hdata
.intvl
.steps
= 2;
1815 values
->safe_push (hist
);
1824 /* Find calls inside STMT for that we want to measure histograms for
1825 indirect/virtual call optimization. */
1828 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1832 if (gimple_code (stmt
) != GIMPLE_CALL
1833 || gimple_call_internal_p (stmt
)
1834 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1837 callee
= gimple_call_fn (stmt
);
1838 histogram_value v
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1840 values
->safe_push (v
);
1845 /* Find values inside STMT for that we want to measure histograms for
1846 string operations. */
1849 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1856 stmt
= dyn_cast
<gcall
*> (gs
);
1860 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
1863 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1866 dest
= gimple_call_arg (stmt
, 0);
1867 blck_size
= gimple_call_arg (stmt
, size_arg
);
1869 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1871 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1872 HIST_TYPE_TOPN_VALUES
,
1874 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1878 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1879 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1883 /* Find values inside STMT for that we want to measure histograms and adds
1884 them to list VALUES. */
1887 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1889 gimple_divmod_values_to_profile (stmt
, values
);
1890 gimple_stringops_values_to_profile (stmt
, values
);
1891 gimple_indirect_call_to_profile (stmt
, values
);
1895 gimple_find_values_to_profile (histogram_values
*values
)
1898 gimple_stmt_iterator gsi
;
1900 histogram_value hist
= NULL
;
1903 FOR_EACH_BB_FN (bb
, cfun
)
1904 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1905 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1907 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1908 HIST_TYPE_TIME_PROFILE
));
1910 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1914 case HIST_TYPE_INTERVAL
:
1915 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1918 case HIST_TYPE_POW2
:
1919 hist
->n_counters
= 2;
1922 case HIST_TYPE_TOPN_VALUES
:
1923 case HIST_TYPE_INDIR_CALL
:
1924 hist
->n_counters
= GCOV_TOPN_MEM_COUNTERS
;
1927 case HIST_TYPE_TIME_PROFILE
:
1928 hist
->n_counters
= 1;
1931 case HIST_TYPE_AVERAGE
:
1932 hist
->n_counters
= 2;
1936 hist
->n_counters
= 1;
1942 if (dump_file
&& hist
->hvalue
.stmt
!= NULL
)
1944 fprintf (dump_file
, "Stmt ");
1945 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1946 dump_histogram_value (dump_file
, hist
);