1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2021 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
335 || hist
->type
== HIST_TYPE_IOR
)
336 /* Note that the IOR counter tracks pointer values and these can have
340 gcc_assert (value
>= 0);
342 streamer_write_gcov_count (ob
, value
);
344 if (hist
->hvalue
.next
)
345 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
348 /* Dump information about HIST to DUMP_FILE. */
351 stream_in_histogram_value (class lto_input_block
*ib
, gimple
*stmt
)
354 unsigned int ncounters
= 0;
357 histogram_value new_val
;
359 histogram_value
*next_p
= NULL
;
363 bp
= streamer_read_bitpack (ib
);
364 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
365 next
= bp_unpack_value (&bp
, 1);
366 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
);
369 case HIST_TYPE_INTERVAL
:
370 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
371 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
372 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
376 case HIST_TYPE_AVERAGE
:
380 case HIST_TYPE_TOPN_VALUES
:
381 case HIST_TYPE_INDIR_CALL
:
385 case HIST_TYPE_TIME_PROFILE
:
393 /* TOP N counters have variable number of counters. */
394 if (type
== HIST_TYPE_INDIR_CALL
|| type
== HIST_TYPE_TOPN_VALUES
)
396 gcov_type total
= streamer_read_gcov_count (ib
);
397 gcov_type ncounters
= streamer_read_gcov_count (ib
);
398 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
,
399 sizeof (*new_val
->hvalue
.counters
)
400 * (2 + 2 * ncounters
));
401 new_val
->hvalue
.counters
[0] = total
;
402 new_val
->hvalue
.counters
[1] = ncounters
;
403 new_val
->n_counters
= 2 + 2 * ncounters
;
404 for (i
= 0; i
< 2 * ncounters
; i
++)
405 new_val
->hvalue
.counters
[2 + i
] = streamer_read_gcov_count (ib
);
409 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
,
410 sizeof (*new_val
->hvalue
.counters
)
412 new_val
->n_counters
= ncounters
;
413 for (i
= 0; i
< ncounters
; i
++)
414 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
418 gimple_add_histogram_value (cfun
, stmt
, new_val
);
421 next_p
= &new_val
->hvalue
.next
;
426 /* Dump all histograms attached to STMT to DUMP_FILE. */
429 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
431 histogram_value hist
;
432 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
433 dump_histogram_value (dump_file
, hist
);
436 /* Remove all histograms associated with STMT. */
439 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
442 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
443 gimple_remove_histogram_value (fun
, stmt
, val
);
446 /* Duplicate all histograms associates with OSTMT to STMT. */
449 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
450 struct function
*ofun
, gimple
*ostmt
)
453 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
455 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
);
456 memcpy (new_val
, val
, sizeof (*val
));
457 new_val
->hvalue
.stmt
= stmt
;
458 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
459 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
460 gimple_add_histogram_value (fun
, stmt
, new_val
);
464 /* Move all histograms associated with OSTMT to STMT. */
467 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
469 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
472 /* The following three statements can't be reordered,
473 because histogram hashtab relies on stmt field value
474 for finding the exact slot. */
475 set_histogram_value (fun
, ostmt
, NULL
);
476 for (; val
!= NULL
; val
= val
->hvalue
.next
)
477 val
->hvalue
.stmt
= stmt
;
478 set_histogram_value (fun
, stmt
, val
);
482 static bool error_found
= false;
484 /* Helper function for verify_histograms. For each histogram reachable via htab
485 walk verify that it was reached via statement walk. */
488 visit_hist (void **slot
, void *data
)
490 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
491 histogram_value hist
= *(histogram_value
*) slot
;
493 if (!visited
->contains (hist
)
494 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
496 error ("dead histogram");
497 dump_histogram_value (stderr
, hist
);
498 debug_gimple_stmt (hist
->hvalue
.stmt
);
504 /* Verify sanity of the histograms. */
507 verify_histograms (void)
510 gimple_stmt_iterator gsi
;
511 histogram_value hist
;
514 hash_set
<histogram_value
> visited_hists
;
515 FOR_EACH_BB_FN (bb
, cfun
)
516 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
518 gimple
*stmt
= gsi_stmt (gsi
);
520 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
521 hist
= hist
->hvalue
.next
)
523 if (hist
->hvalue
.stmt
!= stmt
)
525 error ("histogram value statement does not correspond to "
526 "the statement it is associated with");
527 debug_gimple_stmt (stmt
);
528 dump_histogram_value (stderr
, hist
);
531 visited_hists
.add (hist
);
534 if (VALUE_HISTOGRAMS (cfun
))
535 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
537 internal_error ("%qs failed", __func__
);
540 /* Helper function for verify_histograms. For each histogram reachable via htab
541 walk verify that it was reached via statement walk. */
544 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
546 histogram_value hist
= *(histogram_value
*) slot
;
547 free (hist
->hvalue
.counters
);
553 free_histograms (struct function
*fn
)
555 if (VALUE_HISTOGRAMS (fn
))
557 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
558 htab_delete (VALUE_HISTOGRAMS (fn
));
559 VALUE_HISTOGRAMS (fn
) = NULL
;
563 /* The overall number of invocations of the counter should match
564 execution count of basic block. Report it as error rather than
565 internal error as it might mean that user has misused the profile
569 check_counter (gimple
*stmt
, const char * name
,
570 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
572 gcov_type bb_count
= bb_count_d
.ipa ().to_gcov_type ();
573 if (*all
!= bb_count
|| *count
> *all
)
575 dump_user_location_t locus
;
576 locus
= ((stmt
!= NULL
)
577 ? dump_user_location_t (stmt
)
578 : dump_user_location_t::from_function_decl
579 (current_function_decl
));
580 if (flag_profile_correction
)
582 if (dump_enabled_p ())
583 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
584 "correcting inconsistent value profile: %s "
585 "profiler overall count (%d) does not match BB "
586 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
594 error_at (locus
.get_location_t (), "corrupted value profile: %s "
595 "profile counter (%d out of %d) inconsistent with "
596 "basic-block count (%d)",
608 /* GIMPLE based transformations. */
611 gimple_value_profile_transformations (void)
614 gimple_stmt_iterator gsi
;
615 bool changed
= false;
617 FOR_EACH_BB_FN (bb
, cfun
)
619 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
621 gimple
*stmt
= gsi_stmt (gsi
);
622 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
628 fprintf (dump_file
, "Trying transformations on stmt ");
629 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
630 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
633 /* Transformations: */
634 /* The order of things in this conditional controls which
635 transformation is used when more than one is applicable. */
636 /* It is expected that any code added by the transformations
637 will be added before the current statement, and that the
638 current statement remain valid (although possibly
639 modified) upon return. */
640 if (gimple_mod_subtract_transform (&gsi
)
641 || gimple_divmod_fixed_value_transform (&gsi
)
642 || gimple_mod_pow2_value_transform (&gsi
)
643 || gimple_stringops_transform (&gsi
))
645 stmt
= gsi_stmt (gsi
);
647 /* Original statement may no longer be in the same block. */
648 if (bb
!= gimple_bb (stmt
))
650 bb
= gimple_bb (stmt
);
651 gsi
= gsi_for_stmt (stmt
);
655 /* The function never thansforms a GIMPLE statement. */
656 if (dump_enabled_p ())
657 dump_ic_profile (&gsi
);
664 /* Generate code for transformation 1 (with parent gimple assignment
665 STMT and probability of taking the optimal path PROB, which is
666 equivalent to COUNT/ALL within roundoff error). This generates the
667 result into a temp and returns the temp; it does not replace or
668 alter the original STMT. */
671 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, profile_probability prob
,
672 gcov_type count
, gcov_type all
)
674 gassign
*stmt1
, *stmt2
;
676 tree tmp0
, tmp1
, tmp2
;
677 gimple
*bb1end
, *bb2end
, *bb3end
;
678 basic_block bb
, bb2
, bb3
, bb4
;
679 tree optype
, op1
, op2
;
680 edge e12
, e13
, e23
, e24
, e34
;
681 gimple_stmt_iterator gsi
;
683 gcc_assert (is_gimple_assign (stmt
)
684 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
685 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
687 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
688 op1
= gimple_assign_rhs1 (stmt
);
689 op2
= gimple_assign_rhs2 (stmt
);
691 bb
= gimple_bb (stmt
);
692 gsi
= gsi_for_stmt (stmt
);
694 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
695 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
696 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
697 stmt2
= gimple_build_assign (tmp1
, op2
);
698 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
699 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
700 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
701 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
704 tmp2
= create_tmp_reg (optype
, "PROF");
705 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
706 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
709 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
710 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
714 /* Edge e23 connects bb2 to bb3, etc. */
715 e12
= split_block (bb
, bb1end
);
717 bb2
->count
= profile_count::from_gcov_type (count
);
718 e23
= split_block (bb2
, bb2end
);
720 bb3
->count
= profile_count::from_gcov_type (all
- count
);
721 e34
= split_block (bb3
, bb3end
);
723 bb4
->count
= profile_count::from_gcov_type (all
);
725 e12
->flags
&= ~EDGE_FALLTHRU
;
726 e12
->flags
|= EDGE_FALSE_VALUE
;
727 e12
->probability
= prob
;
729 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
730 e13
->probability
= prob
.invert ();
734 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
735 e24
->probability
= profile_probability::always ();
737 e34
->probability
= profile_probability::always ();
742 /* Return the n-th value count of TOPN_VALUE histogram. If
743 there's a value, return true and set VALUE and COUNT
746 Counters have the following meaning.
748 abs (counters[0]) is the number of executions
749 for i in 0 ... TOPN-1
750 counters[2 * i + 1] is target
751 abs (counters[2 * i + 2]) is corresponding hitrate counter.
753 Value of counters[0] negative when counter became
754 full during merging and some values are lost. */
757 get_nth_most_common_value (gimple
*stmt
, const char *counter_type
,
758 histogram_value hist
, gcov_type
*value
,
759 gcov_type
*count
, gcov_type
*all
, unsigned n
)
761 unsigned counters
= hist
->hvalue
.counters
[1];
768 gcov_type read_all
= abs_hwi (hist
->hvalue
.counters
[0]);
770 gcov_type v
= hist
->hvalue
.counters
[2 * n
+ 2];
771 gcov_type c
= hist
->hvalue
.counters
[2 * n
+ 3];
773 if (hist
->hvalue
.counters
[0] < 0
774 && (flag_profile_reproducible
== PROFILE_REPRODUCIBILITY_PARALLEL_RUNS
775 || (flag_profile_reproducible
776 == PROFILE_REPRODUCIBILITY_MULTITHREADED
)))
779 /* Indirect calls can't be verified. */
781 && check_counter (stmt
, counter_type
, &c
, &read_all
,
782 gimple_bb (stmt
)->count
))
792 /* Do transform 1) on INSN if applicable. */
795 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
797 histogram_value histogram
;
799 gcov_type val
, count
, all
;
800 tree result
, value
, tree_val
;
801 profile_probability prob
;
804 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
808 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
811 code
= gimple_assign_rhs_code (stmt
);
813 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
816 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
817 HIST_TYPE_TOPN_VALUES
);
821 if (!get_nth_most_common_value (stmt
, "divmod", histogram
, &val
, &count
,
825 value
= histogram
->hvalue
.value
;
826 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
828 /* We require that count is at least half of all. */
829 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
831 || optimize_bb_for_size_p (gimple_bb (stmt
)))
834 /* Compute probability of taking the optimal path. */
836 prob
= profile_probability::probability_in_gcov_type (count
, all
);
838 prob
= profile_probability::never ();
840 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
841 tree_val
= build_int_cst (get_gcov_type (), val
);
845 a
[0] = (unsigned HOST_WIDE_INT
) val
;
846 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
848 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
849 TYPE_PRECISION (get_gcov_type ()), false));
851 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
853 if (dump_enabled_p ())
854 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
855 "Transformation done: div/mod by constant %T\n", tree_val
);
857 gimple_assign_set_rhs_from_tree (si
, result
);
858 update_stmt (gsi_stmt (*si
));
863 /* Generate code for transformation 2 (with parent gimple assign STMT and
864 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
865 within roundoff error). This generates the result into a temp and returns
866 the temp; it does not replace or alter the original STMT. */
869 gimple_mod_pow2 (gassign
*stmt
, profile_probability prob
, gcov_type count
, gcov_type all
)
871 gassign
*stmt1
, *stmt2
, *stmt3
;
874 gimple
*bb1end
, *bb2end
, *bb3end
;
875 basic_block bb
, bb2
, bb3
, bb4
;
876 tree optype
, op1
, op2
;
877 edge e12
, e13
, e23
, e24
, e34
;
878 gimple_stmt_iterator gsi
;
881 gcc_assert (is_gimple_assign (stmt
)
882 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
884 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
885 op1
= gimple_assign_rhs1 (stmt
);
886 op2
= gimple_assign_rhs2 (stmt
);
888 bb
= gimple_bb (stmt
);
889 gsi
= gsi_for_stmt (stmt
);
891 result
= create_tmp_reg (optype
, "PROF");
892 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
893 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
894 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
895 build_int_cst (optype
, -1));
896 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
897 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
898 NULL_TREE
, NULL_TREE
);
899 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
900 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
901 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
904 /* tmp2 == op2-1 inherited from previous block. */
905 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
906 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
909 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
911 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
915 /* Edge e23 connects bb2 to bb3, etc. */
916 e12
= split_block (bb
, bb1end
);
918 bb2
->count
= profile_count::from_gcov_type (count
);
919 e23
= split_block (bb2
, bb2end
);
921 bb3
->count
= profile_count::from_gcov_type (all
- count
);
922 e34
= split_block (bb3
, bb3end
);
924 bb4
->count
= profile_count::from_gcov_type (all
);
926 e12
->flags
&= ~EDGE_FALLTHRU
;
927 e12
->flags
|= EDGE_FALSE_VALUE
;
928 e12
->probability
= prob
;
930 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
931 e13
->probability
= prob
.invert ();
935 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
936 e24
->probability
= profile_probability::always ();
938 e34
->probability
= profile_probability::always ();
943 /* Do transform 2) on INSN if applicable. */
946 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
948 histogram_value histogram
;
950 gcov_type count
, wrong_values
, all
;
951 tree lhs_type
, result
, value
;
952 profile_probability prob
;
955 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
959 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
960 if (!INTEGRAL_TYPE_P (lhs_type
))
963 code
= gimple_assign_rhs_code (stmt
);
965 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
968 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
972 value
= histogram
->hvalue
.value
;
973 wrong_values
= histogram
->hvalue
.counters
[0];
974 count
= histogram
->hvalue
.counters
[1];
976 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
978 /* We require that we hit a power of 2 at least half of all evaluations. */
979 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
980 || count
< wrong_values
981 || optimize_bb_for_size_p (gimple_bb (stmt
)))
984 /* Compute probability of taking the optimal path. */
985 all
= count
+ wrong_values
;
987 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
990 if (dump_enabled_p ())
991 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
992 "Transformation done: mod power of 2\n");
995 prob
= profile_probability::probability_in_gcov_type (count
, all
);
997 prob
= profile_probability::never ();
999 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1001 gimple_assign_set_rhs_from_tree (si
, result
);
1002 update_stmt (gsi_stmt (*si
));
1007 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1008 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1009 supported and this is built into this interface. The probabilities of taking
1010 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1011 COUNT2/ALL respectively within roundoff error). This generates the
1012 result into a temp and returns the temp; it does not replace or alter
1013 the original STMT. */
1014 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1017 gimple_mod_subtract (gassign
*stmt
, profile_probability prob1
,
1018 profile_probability prob2
, int ncounts
,
1019 gcov_type count1
, gcov_type count2
, gcov_type all
)
1025 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
1026 basic_block bb
, bb2
, bb3
, bb4
;
1027 tree optype
, op1
, op2
;
1028 edge e12
, e23
= 0, e24
, e34
, e14
;
1029 gimple_stmt_iterator gsi
;
1032 gcc_assert (is_gimple_assign (stmt
)
1033 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1035 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1036 op1
= gimple_assign_rhs1 (stmt
);
1037 op2
= gimple_assign_rhs2 (stmt
);
1039 bb
= gimple_bb (stmt
);
1040 gsi
= gsi_for_stmt (stmt
);
1042 result
= create_tmp_reg (optype
, "PROF");
1043 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1044 stmt1
= gimple_build_assign (result
, op1
);
1045 stmt2
= gimple_build_assign (tmp1
, op2
);
1046 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1047 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1048 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1049 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1052 if (ncounts
) /* Assumed to be 0 or 1 */
1054 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1055 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1056 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1057 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1061 /* Fallback case. */
1062 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1064 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1068 /* Edge e23 connects bb2 to bb3, etc. */
1069 /* However block 3 is optional; if it is not there, references
1070 to 3 really refer to block 2. */
1071 e12
= split_block (bb
, bb1end
);
1073 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1075 if (ncounts
) /* Assumed to be 0 or 1. */
1077 e23
= split_block (bb2
, bb2end
);
1079 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1082 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1084 bb4
->count
= profile_count::from_gcov_type (all
);
1086 e12
->flags
&= ~EDGE_FALLTHRU
;
1087 e12
->flags
|= EDGE_FALSE_VALUE
;
1088 e12
->probability
= prob1
.invert ();
1090 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1091 e14
->probability
= prob1
;
1093 if (ncounts
) /* Assumed to be 0 or 1. */
1095 e23
->flags
&= ~EDGE_FALLTHRU
;
1096 e23
->flags
|= EDGE_FALSE_VALUE
;
1097 e23
->probability
= prob2
.invert ();
1099 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1100 e24
->probability
= prob2
;
1103 e34
->probability
= profile_probability::always ();
1108 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1111 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1113 histogram_value histogram
;
1114 enum tree_code code
;
1115 gcov_type count
, wrong_values
, all
;
1116 tree lhs_type
, result
;
1117 profile_probability prob1
, prob2
;
1118 unsigned int i
, steps
;
1119 gcov_type count1
, count2
;
1121 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1125 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1126 if (!INTEGRAL_TYPE_P (lhs_type
))
1129 code
= gimple_assign_rhs_code (stmt
);
1131 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1134 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1140 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1141 all
+= histogram
->hvalue
.counters
[i
];
1143 wrong_values
+= histogram
->hvalue
.counters
[i
];
1144 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1145 steps
= histogram
->hdata
.intvl
.steps
;
1146 all
+= wrong_values
;
1147 count1
= histogram
->hvalue
.counters
[0];
1148 count2
= histogram
->hvalue
.counters
[1];
1150 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1152 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1156 if (flag_profile_correction
&& count1
+ count2
> all
)
1157 all
= count1
+ count2
;
1159 gcc_assert (count1
+ count2
<= all
);
1161 /* We require that we use just subtractions in at least 50% of all
1164 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1166 count
+= histogram
->hvalue
.counters
[i
];
1167 if (count
* 2 >= all
)
1171 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1174 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1175 if (dump_enabled_p ())
1176 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1177 "Transformation done: mod subtract\n");
1179 /* Compute probability of taking the optimal path(s). */
1182 prob1
= profile_probability::probability_in_gcov_type (count1
, all
);
1183 prob2
= profile_probability::probability_in_gcov_type (count2
, all
);
1187 prob1
= prob2
= profile_probability::never ();
1190 /* In practice, "steps" is always 2. This interface reflects this,
1191 and will need to be changed if "steps" can change. */
1192 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1194 gimple_assign_set_rhs_from_tree (si
, result
);
1195 update_stmt (gsi_stmt (*si
));
1200 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1202 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1204 /* Returns true if node graph is initialized. This
1205 is used to test if profile_id has been created
1206 for cgraph_nodes. */
1209 coverage_node_map_initialized_p (void)
1211 return cgraph_node_map
!= 0;
1214 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1215 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1216 that the PROFILE_IDs was already assigned. */
1219 init_node_map (bool local
)
1221 struct cgraph_node
*n
;
1222 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1224 FOR_EACH_DEFINED_FUNCTION (n
)
1225 if (n
->has_gimple_body_p () || n
->thunk
)
1228 dump_user_location_t loc
1229 = dump_user_location_t::from_function_decl (n
->decl
);
1232 n
->profile_id
= coverage_compute_profile_id (n
);
1233 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1236 if (dump_enabled_p ())
1237 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1238 "Local profile-id %i conflict"
1239 " with nodes %s %s\n",
1242 (*val
)->dump_name ());
1243 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1246 else if (!n
->profile_id
)
1248 if (dump_enabled_p ())
1249 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1250 "Node %s has no profile-id"
1251 " (profile feedback missing?)\n",
1255 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1257 if (dump_enabled_p ())
1258 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1259 "Node %s has IP profile-id %i conflict. "
1261 n
->dump_name (), n
->profile_id
);
1265 cgraph_node_map
->put (n
->profile_id
, n
);
1269 /* Delete the CGRAPH_NODE_MAP. */
1274 delete cgraph_node_map
;
1277 /* Return cgraph node for function with pid */
1280 find_func_by_profile_id (int profile_id
)
1282 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1289 /* Do transformation
1291 if (actual_callee_address == address_of_most_common_function/method)
1298 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1299 profile_probability prob
)
1304 tree tmp0
, tmp1
, tmp
;
1305 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1306 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1307 gimple_stmt_iterator gsi
;
1312 cond_bb
= gimple_bb (icall_stmt
);
1313 gsi
= gsi_for_stmt (icall_stmt
);
1315 tmp0
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1316 tmp1
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1317 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1318 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1319 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1321 tmp
= fold_convert (ptr_type_node
, build_addr (direct_call
->decl
));
1322 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1323 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1325 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1326 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1328 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1330 unlink_stmt_vdef (icall_stmt
);
1331 release_ssa_name (gimple_vdef (icall_stmt
));
1333 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1334 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1335 update_stmt (icall_stmt
);
1336 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1337 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1338 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1339 if ((dflags
& ECF_NORETURN
) != 0
1340 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1341 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1342 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1345 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1346 e_cd
= split_block (cond_bb
, cond_stmt
);
1347 dcall_bb
= e_cd
->dest
;
1348 dcall_bb
->count
= cond_bb
->count
.apply_probability (prob
);
1350 e_di
= split_block (dcall_bb
, dcall_stmt
);
1351 icall_bb
= e_di
->dest
;
1352 icall_bb
->count
= cond_bb
->count
- dcall_bb
->count
;
1354 /* Do not disturb existing EH edges from the indirect call. */
1355 if (!stmt_ends_bb_p (icall_stmt
))
1356 e_ij
= split_block (icall_bb
, icall_stmt
);
1359 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1360 /* The indirect call might be noreturn. */
1363 e_ij
->probability
= profile_probability::always ();
1364 e_ij
= single_pred_edge (split_edge (e_ij
));
1369 join_bb
= e_ij
->dest
;
1370 join_bb
->count
= cond_bb
->count
;
1373 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1374 e_cd
->probability
= prob
;
1376 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1377 e_ci
->probability
= prob
.invert ();
1383 if ((dflags
& ECF_NORETURN
) == 0)
1385 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1386 e_dj
->probability
= profile_probability::always ();
1388 e_ij
->probability
= profile_probability::always ();
1391 /* Insert PHI node for the call result if necessary. */
1392 if (gimple_call_lhs (icall_stmt
)
1393 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1394 && (dflags
& ECF_NORETURN
) == 0)
1396 tree result
= gimple_call_lhs (icall_stmt
);
1397 gphi
*phi
= create_phi_node (result
, join_bb
);
1398 gimple_call_set_lhs (icall_stmt
,
1399 duplicate_ssa_name (result
, icall_stmt
));
1400 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1401 gimple_call_set_lhs (dcall_stmt
,
1402 duplicate_ssa_name (result
, dcall_stmt
));
1403 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1406 /* Build an EH edge for the direct call if necessary. */
1407 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1408 if (lp_nr
> 0 && stmt_could_throw_p (cfun
, dcall_stmt
))
1410 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1413 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1414 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1416 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1417 e
->probability
= e_eh
->probability
;
1418 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1419 !gsi_end_p (psi
); gsi_next (&psi
))
1421 gphi
*phi
= psi
.phi ();
1422 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1423 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1426 if (!stmt_could_throw_p (cfun
, dcall_stmt
))
1427 gimple_purge_dead_eh_edges (dcall_bb
);
1431 /* Dump info about indirect call profile. */
1434 dump_ic_profile (gimple_stmt_iterator
*gsi
)
1437 histogram_value histogram
;
1438 gcov_type val
, count
, all
;
1439 struct cgraph_node
*direct_call
;
1441 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1445 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1448 if (gimple_call_internal_p (stmt
))
1451 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1456 all
= histogram
->hvalue
.counters
[0];
1458 for (unsigned j
= 0; j
< GCOV_TOPN_MAXIMUM_TRACKED_VALUES
; j
++)
1460 if (!get_nth_most_common_value (NULL
, "indirect call", histogram
, &val
,
1466 direct_call
= find_func_by_profile_id ((int) val
);
1468 if (direct_call
== NULL
)
1470 MSG_MISSED_OPTIMIZATION
, stmt
,
1471 "Indirect call -> direct call from other "
1472 "module %T=> %i (will resolve by ipa-profile only with LTO)\n",
1473 gimple_call_fn (stmt
), (int) val
);
1475 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1476 "Indirect call -> direct call "
1477 "%T => %T (will resolve by ipa-profile)\n",
1478 gimple_call_fn (stmt
), direct_call
->decl
);
1479 dump_printf_loc (MSG_NOTE
, stmt
,
1480 "hist->count %" PRId64
" hist->all %" PRId64
"\n",
1485 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1486 set to the argument index for the size of the string operation. */
1489 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1491 enum built_in_function fcode
;
1493 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1496 case BUILT_IN_MEMCPY
:
1497 case BUILT_IN_MEMPCPY
:
1498 case BUILT_IN_MEMMOVE
:
1500 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1501 INTEGER_TYPE
, VOID_TYPE
);
1502 case BUILT_IN_MEMSET
:
1504 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1505 INTEGER_TYPE
, VOID_TYPE
);
1506 case BUILT_IN_BZERO
:
1508 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1515 /* Convert stringop (..., vcall_size)
1517 if (vcall_size == icall_size)
1518 stringop (..., icall_size);
1520 stringop (..., vcall_size);
1521 assuming we'll propagate a true constant into ICALL_SIZE later. */
1524 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, profile_probability prob
,
1525 gcov_type count
, gcov_type all
)
1530 tree tmp0
, tmp1
, vcall_size
, optype
;
1531 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1532 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1533 gimple_stmt_iterator gsi
;
1536 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1539 cond_bb
= gimple_bb (vcall_stmt
);
1540 gsi
= gsi_for_stmt (vcall_stmt
);
1542 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1543 optype
= TREE_TYPE (vcall_size
);
1545 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1546 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1547 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1548 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1550 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1551 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1553 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1554 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1556 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1558 unlink_stmt_vdef (vcall_stmt
);
1559 release_ssa_name (gimple_vdef (vcall_stmt
));
1561 gimple_set_vdef (vcall_stmt
, NULL
);
1562 gimple_set_vuse (vcall_stmt
, NULL
);
1563 update_stmt (vcall_stmt
);
1564 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1565 gimple_call_set_arg (icall_stmt
, size_arg
,
1566 fold_convert (optype
, icall_size
));
1567 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1570 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1571 e_ci
= split_block (cond_bb
, cond_stmt
);
1572 icall_bb
= e_ci
->dest
;
1573 icall_bb
->count
= profile_count::from_gcov_type (count
);
1575 e_iv
= split_block (icall_bb
, icall_stmt
);
1576 vcall_bb
= e_iv
->dest
;
1577 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1579 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1580 join_bb
= e_vj
->dest
;
1581 join_bb
->count
= profile_count::from_gcov_type (all
);
1583 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1584 e_ci
->probability
= prob
;
1586 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1587 e_cv
->probability
= prob
.invert ();
1591 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1592 e_ij
->probability
= profile_probability::always ();
1594 e_vj
->probability
= profile_probability::always ();
1596 /* Insert PHI node for the call result if necessary. */
1597 if (gimple_call_lhs (vcall_stmt
)
1598 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1600 tree result
= gimple_call_lhs (vcall_stmt
);
1601 gphi
*phi
= create_phi_node (result
, join_bb
);
1602 gimple_call_set_lhs (vcall_stmt
,
1603 duplicate_ssa_name (result
, vcall_stmt
));
1604 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1605 gimple_call_set_lhs (icall_stmt
,
1606 duplicate_ssa_name (result
, icall_stmt
));
1607 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1610 /* Because these are all string op builtins, they're all nothrow. */
1611 gcc_assert (!stmt_could_throw_p (cfun
, vcall_stmt
));
1612 gcc_assert (!stmt_could_throw_p (cfun
, icall_stmt
));
1615 /* Find values inside STMT for that we want to measure histograms for
1616 division/modulo optimization. */
1619 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1623 enum built_in_function fcode
;
1624 histogram_value histogram
;
1625 gcov_type count
, all
, val
;
1627 unsigned int dest_align
, src_align
;
1628 profile_probability prob
;
1632 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1636 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1639 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1642 blck_size
= gimple_call_arg (stmt
, size_arg
);
1643 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1646 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
1647 HIST_TYPE_TOPN_VALUES
);
1651 if (!get_nth_most_common_value (stmt
, "stringops", histogram
, &val
, &count
,
1655 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1657 /* We require that count is at least half of all. */
1658 if (2 * count
< all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1660 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1663 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1665 prob
= profile_probability::never ();
1667 dest
= gimple_call_arg (stmt
, 0);
1668 dest_align
= get_pointer_alignment (dest
);
1669 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1672 case BUILT_IN_MEMCPY
:
1673 case BUILT_IN_MEMPCPY
:
1674 case BUILT_IN_MEMMOVE
:
1675 src
= gimple_call_arg (stmt
, 1);
1676 src_align
= get_pointer_alignment (src
);
1677 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1680 case BUILT_IN_MEMSET
:
1681 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1682 gimple_call_arg (stmt
, 1),
1686 case BUILT_IN_BZERO
:
1687 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1696 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1697 tree_val
= build_int_cst (get_gcov_type (), val
);
1701 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1702 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1704 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1705 TYPE_PRECISION (get_gcov_type ()), false));
1708 if (dump_enabled_p ())
1709 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1710 "Transformation done: single value %i stringop for %s\n",
1711 (int)val
, built_in_names
[(int)fcode
]);
1713 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1719 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1720 HOST_WIDE_INT
*expected_size
)
1722 histogram_value histogram
;
1723 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1726 *expected_size
= -1;
1727 else if (!histogram
->hvalue
.counters
[1])
1729 *expected_size
= -1;
1730 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1735 size
= ((histogram
->hvalue
.counters
[0]
1736 + histogram
->hvalue
.counters
[1] / 2)
1737 / histogram
->hvalue
.counters
[1]);
1738 /* Even if we can hold bigger value in SIZE, INT_MAX
1739 is safe "infinity" for code generation strategies. */
1742 *expected_size
= size
;
1743 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1746 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1749 *expected_align
= 0;
1750 else if (!histogram
->hvalue
.counters
[0])
1752 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1753 *expected_align
= 0;
1758 unsigned int alignment
;
1760 count
= histogram
->hvalue
.counters
[0];
1762 while (!(count
& alignment
)
1763 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1765 *expected_align
= alignment
* BITS_PER_UNIT
;
1766 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1771 /* Find values inside STMT for that we want to measure histograms for
1772 division/modulo optimization. */
1775 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1777 tree lhs
, divisor
, op0
, type
;
1778 histogram_value hist
;
1780 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1783 lhs
= gimple_assign_lhs (stmt
);
1784 type
= TREE_TYPE (lhs
);
1785 if (!INTEGRAL_TYPE_P (type
))
1788 switch (gimple_assign_rhs_code (stmt
))
1790 case TRUNC_DIV_EXPR
:
1791 case TRUNC_MOD_EXPR
:
1792 divisor
= gimple_assign_rhs2 (stmt
);
1793 op0
= gimple_assign_rhs1 (stmt
);
1795 if (TREE_CODE (divisor
) == SSA_NAME
)
1796 /* Check for the case where the divisor is the same value most
1798 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1799 HIST_TYPE_TOPN_VALUES
,
1802 /* For mod, check whether it is not often a noop (or replaceable by
1803 a few subtractions). */
1804 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1805 && TYPE_UNSIGNED (type
)
1806 && TREE_CODE (divisor
) == SSA_NAME
)
1809 /* Check for a special case where the divisor is power of 2. */
1810 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1813 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1814 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1816 hist
->hdata
.intvl
.int_start
= 0;
1817 hist
->hdata
.intvl
.steps
= 2;
1818 values
->safe_push (hist
);
1827 /* Find calls inside STMT for that we want to measure histograms for
1828 indirect/virtual call optimization. */
1831 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1835 if (gimple_code (stmt
) != GIMPLE_CALL
1836 || gimple_call_internal_p (stmt
)
1837 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1840 callee
= gimple_call_fn (stmt
);
1841 histogram_value v
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1843 values
->safe_push (v
);
1848 /* Find values inside STMT for that we want to measure histograms for
1849 string operations. */
1852 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1859 stmt
= dyn_cast
<gcall
*> (gs
);
1863 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
1866 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1869 dest
= gimple_call_arg (stmt
, 0);
1870 blck_size
= gimple_call_arg (stmt
, size_arg
);
1872 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1874 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1875 HIST_TYPE_TOPN_VALUES
,
1877 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1881 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1882 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1886 /* Find values inside STMT for that we want to measure histograms and adds
1887 them to list VALUES. */
1890 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1892 gimple_divmod_values_to_profile (stmt
, values
);
1893 gimple_stringops_values_to_profile (stmt
, values
);
1894 gimple_indirect_call_to_profile (stmt
, values
);
1898 gimple_find_values_to_profile (histogram_values
*values
)
1901 gimple_stmt_iterator gsi
;
1903 histogram_value hist
= NULL
;
1906 FOR_EACH_BB_FN (bb
, cfun
)
1907 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1908 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1910 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1911 HIST_TYPE_TIME_PROFILE
));
1913 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1917 case HIST_TYPE_INTERVAL
:
1918 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1921 case HIST_TYPE_POW2
:
1922 hist
->n_counters
= 2;
1925 case HIST_TYPE_TOPN_VALUES
:
1926 case HIST_TYPE_INDIR_CALL
:
1927 hist
->n_counters
= GCOV_TOPN_MEM_COUNTERS
;
1930 case HIST_TYPE_TIME_PROFILE
:
1931 hist
->n_counters
= 1;
1934 case HIST_TYPE_AVERAGE
:
1935 hist
->n_counters
= 2;
1939 hist
->n_counters
= 1;
1945 if (dump_file
&& hist
->hvalue
.stmt
!= NULL
)
1947 fprintf (dump_file
, "Stmt ");
1948 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1949 dump_histogram_value (dump_file
, hist
);