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 fprintf (dump_file
, " all: %" PRId64
", values: ",
269 (int64_t) hist
->hvalue
.counters
[0]);
270 for (unsigned i
= 0; i
< GCOV_TOPN_VALUES
; i
++)
272 fprintf (dump_file
, "[%" PRId64
":%" PRId64
"]",
273 (int64_t) hist
->hvalue
.counters
[2 * i
+ 1],
274 (int64_t) hist
->hvalue
.counters
[2 * i
+ 2]);
275 if (i
!= GCOV_TOPN_VALUES
- 1)
276 fprintf (dump_file
, ", ");
278 fprintf (dump_file
, ".\n");
283 case HIST_TYPE_AVERAGE
:
284 if (hist
->hvalue
.counters
)
285 fprintf (dump_file
, "Average value sum:%" PRId64
286 " times:%" PRId64
".\n",
287 (int64_t) hist
->hvalue
.counters
[0],
288 (int64_t) hist
->hvalue
.counters
[1]);
292 if (hist
->hvalue
.counters
)
293 fprintf (dump_file
, "IOR value ior:%" PRId64
".\n",
294 (int64_t) hist
->hvalue
.counters
[0]);
297 case HIST_TYPE_TIME_PROFILE
:
298 if (hist
->hvalue
.counters
)
299 fprintf (dump_file
, "Time profile time:%" PRId64
".\n",
300 (int64_t) hist
->hvalue
.counters
[0]);
307 /* Dump information about HIST to DUMP_FILE. */
310 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
315 bp
= bitpack_create (ob
->main_stream
);
316 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
317 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
318 streamer_write_bitpack (&bp
);
321 case HIST_TYPE_INTERVAL
:
322 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
323 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
328 for (i
= 0; i
< hist
->n_counters
; i
++)
330 /* When user uses an unsigned type with a big value, constant converted
331 to gcov_type (a signed type) can be negative. */
332 gcov_type value
= hist
->hvalue
.counters
[i
];
333 if (hist
->type
== HIST_TYPE_TOPN_VALUES
&& i
> 0)
336 gcc_assert (value
>= 0);
338 streamer_write_gcov_count (ob
, value
);
340 if (hist
->hvalue
.next
)
341 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
344 /* Dump information about HIST to DUMP_FILE. */
347 stream_in_histogram_value (class lto_input_block
*ib
, gimple
*stmt
)
350 unsigned int ncounters
= 0;
353 histogram_value new_val
;
355 histogram_value
*next_p
= NULL
;
359 bp
= streamer_read_bitpack (ib
);
360 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
361 next
= bp_unpack_value (&bp
, 1);
362 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
);
365 case HIST_TYPE_INTERVAL
:
366 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
367 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
368 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
372 case HIST_TYPE_AVERAGE
:
376 case HIST_TYPE_TOPN_VALUES
:
377 case HIST_TYPE_INDIR_CALL
:
378 ncounters
= GCOV_TOPN_VALUES_COUNTERS
;
382 case HIST_TYPE_TIME_PROFILE
:
389 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
,
390 sizeof (*new_val
->hvalue
.counters
)
392 new_val
->n_counters
= ncounters
;
393 for (i
= 0; i
< ncounters
; i
++)
394 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
396 gimple_add_histogram_value (cfun
, stmt
, new_val
);
399 next_p
= &new_val
->hvalue
.next
;
404 /* Dump all histograms attached to STMT to DUMP_FILE. */
407 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
409 histogram_value hist
;
410 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
411 dump_histogram_value (dump_file
, hist
);
414 /* Remove all histograms associated with STMT. */
417 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
420 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
421 gimple_remove_histogram_value (fun
, stmt
, val
);
424 /* Duplicate all histograms associates with OSTMT to STMT. */
427 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
428 struct function
*ofun
, gimple
*ostmt
)
431 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
433 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
);
434 memcpy (new_val
, val
, sizeof (*val
));
435 new_val
->hvalue
.stmt
= stmt
;
436 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
437 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
438 gimple_add_histogram_value (fun
, stmt
, new_val
);
442 /* Move all histograms associated with OSTMT to STMT. */
445 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
447 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
450 /* The following three statements can't be reordered,
451 because histogram hashtab relies on stmt field value
452 for finding the exact slot. */
453 set_histogram_value (fun
, ostmt
, NULL
);
454 for (; val
!= NULL
; val
= val
->hvalue
.next
)
455 val
->hvalue
.stmt
= stmt
;
456 set_histogram_value (fun
, stmt
, val
);
460 static bool error_found
= false;
462 /* Helper function for verify_histograms. For each histogram reachable via htab
463 walk verify that it was reached via statement walk. */
466 visit_hist (void **slot
, void *data
)
468 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
469 histogram_value hist
= *(histogram_value
*) slot
;
471 if (!visited
->contains (hist
)
472 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
474 error ("dead histogram");
475 dump_histogram_value (stderr
, hist
);
476 debug_gimple_stmt (hist
->hvalue
.stmt
);
482 /* Verify sanity of the histograms. */
485 verify_histograms (void)
488 gimple_stmt_iterator gsi
;
489 histogram_value hist
;
492 hash_set
<histogram_value
> visited_hists
;
493 FOR_EACH_BB_FN (bb
, cfun
)
494 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
496 gimple
*stmt
= gsi_stmt (gsi
);
498 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
499 hist
= hist
->hvalue
.next
)
501 if (hist
->hvalue
.stmt
!= stmt
)
503 error ("histogram value statement does not correspond to "
504 "the statement it is associated with");
505 debug_gimple_stmt (stmt
);
506 dump_histogram_value (stderr
, hist
);
509 visited_hists
.add (hist
);
512 if (VALUE_HISTOGRAMS (cfun
))
513 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
515 internal_error ("%qs failed", __func__
);
518 /* Helper function for verify_histograms. For each histogram reachable via htab
519 walk verify that it was reached via statement walk. */
522 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
524 histogram_value hist
= *(histogram_value
*) slot
;
525 free (hist
->hvalue
.counters
);
531 free_histograms (struct function
*fn
)
533 if (VALUE_HISTOGRAMS (fn
))
535 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
536 htab_delete (VALUE_HISTOGRAMS (fn
));
537 VALUE_HISTOGRAMS (fn
) = NULL
;
541 /* The overall number of invocations of the counter should match
542 execution count of basic block. Report it as error rather than
543 internal error as it might mean that user has misused the profile
547 check_counter (gimple
*stmt
, const char * name
,
548 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
550 gcov_type bb_count
= bb_count_d
.ipa ().to_gcov_type ();
551 if (*all
!= bb_count
|| *count
> *all
)
553 dump_user_location_t locus
;
554 locus
= ((stmt
!= NULL
)
555 ? dump_user_location_t (stmt
)
556 : dump_user_location_t::from_function_decl
557 (current_function_decl
));
558 if (flag_profile_correction
)
560 if (dump_enabled_p ())
561 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
562 "correcting inconsistent value profile: %s "
563 "profiler overall count (%d) does not match BB "
564 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
572 error_at (locus
.get_location_t (), "corrupted value profile: %s "
573 "profile counter (%d out of %d) inconsistent with "
574 "basic-block count (%d)",
586 /* GIMPLE based transformations. */
589 gimple_value_profile_transformations (void)
592 gimple_stmt_iterator gsi
;
593 bool changed
= false;
595 FOR_EACH_BB_FN (bb
, cfun
)
597 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
599 gimple
*stmt
= gsi_stmt (gsi
);
600 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
606 fprintf (dump_file
, "Trying transformations on stmt ");
607 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
608 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
611 /* Transformations: */
612 /* The order of things in this conditional controls which
613 transformation is used when more than one is applicable. */
614 /* It is expected that any code added by the transformations
615 will be added before the current statement, and that the
616 current statement remain valid (although possibly
617 modified) upon return. */
618 if (gimple_mod_subtract_transform (&gsi
)
619 || gimple_divmod_fixed_value_transform (&gsi
)
620 || gimple_mod_pow2_value_transform (&gsi
)
621 || gimple_stringops_transform (&gsi
))
623 stmt
= gsi_stmt (gsi
);
625 /* Original statement may no longer be in the same block. */
626 if (bb
!= gimple_bb (stmt
))
628 bb
= gimple_bb (stmt
);
629 gsi
= gsi_for_stmt (stmt
);
633 /* The function never thansforms a GIMPLE statement. */
634 if (dump_enabled_p ())
635 dump_ic_profile (&gsi
);
642 /* Generate code for transformation 1 (with parent gimple assignment
643 STMT and probability of taking the optimal path PROB, which is
644 equivalent to COUNT/ALL within roundoff error). This generates the
645 result into a temp and returns the temp; it does not replace or
646 alter the original STMT. */
649 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, profile_probability prob
,
650 gcov_type count
, gcov_type all
)
652 gassign
*stmt1
, *stmt2
;
654 tree tmp0
, tmp1
, tmp2
;
655 gimple
*bb1end
, *bb2end
, *bb3end
;
656 basic_block bb
, bb2
, bb3
, bb4
;
657 tree optype
, op1
, op2
;
658 edge e12
, e13
, e23
, e24
, e34
;
659 gimple_stmt_iterator gsi
;
661 gcc_assert (is_gimple_assign (stmt
)
662 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
663 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
665 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
666 op1
= gimple_assign_rhs1 (stmt
);
667 op2
= gimple_assign_rhs2 (stmt
);
669 bb
= gimple_bb (stmt
);
670 gsi
= gsi_for_stmt (stmt
);
672 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
673 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
674 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
675 stmt2
= gimple_build_assign (tmp1
, op2
);
676 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
677 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
678 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
679 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
682 tmp2
= create_tmp_reg (optype
, "PROF");
683 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
684 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
687 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
688 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
692 /* Edge e23 connects bb2 to bb3, etc. */
693 e12
= split_block (bb
, bb1end
);
695 bb2
->count
= profile_count::from_gcov_type (count
);
696 e23
= split_block (bb2
, bb2end
);
698 bb3
->count
= profile_count::from_gcov_type (all
- count
);
699 e34
= split_block (bb3
, bb3end
);
701 bb4
->count
= profile_count::from_gcov_type (all
);
703 e12
->flags
&= ~EDGE_FALLTHRU
;
704 e12
->flags
|= EDGE_FALSE_VALUE
;
705 e12
->probability
= prob
;
707 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
708 e13
->probability
= prob
.invert ();
712 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
713 e24
->probability
= profile_probability::always ();
715 e34
->probability
= profile_probability::always ();
720 /* Return the n-th value count of TOPN_VALUE histogram. If
721 there's a value, return true and set VALUE and COUNT
725 get_nth_most_common_value (gimple
*stmt
, const char *counter_type
,
726 histogram_value hist
, gcov_type
*value
,
727 gcov_type
*count
, gcov_type
*all
, unsigned n
)
729 if (hist
->hvalue
.counters
[2] == -1)
732 gcc_assert (n
< GCOV_TOPN_VALUES
);
737 gcov_type read_all
= hist
->hvalue
.counters
[0];
739 gcov_type v
= hist
->hvalue
.counters
[2 * n
+ 1];
740 gcov_type c
= hist
->hvalue
.counters
[2 * n
+ 2];
742 /* Indirect calls can't be verified. */
744 && check_counter (stmt
, counter_type
, &c
, &read_all
,
745 gimple_bb (stmt
)->count
))
755 /* Do transform 1) on INSN if applicable. */
758 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
760 histogram_value histogram
;
762 gcov_type val
, count
, all
;
763 tree result
, value
, tree_val
;
764 profile_probability prob
;
767 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
771 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
774 code
= gimple_assign_rhs_code (stmt
);
776 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
779 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
780 HIST_TYPE_TOPN_VALUES
);
784 if (!get_nth_most_common_value (stmt
, "divmod", histogram
, &val
, &count
,
788 value
= histogram
->hvalue
.value
;
789 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
791 /* We require that count is at least half of all. */
792 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
794 || optimize_bb_for_size_p (gimple_bb (stmt
)))
797 /* Compute probability of taking the optimal path. */
799 prob
= profile_probability::probability_in_gcov_type (count
, all
);
801 prob
= profile_probability::never ();
803 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
804 tree_val
= build_int_cst (get_gcov_type (), val
);
808 a
[0] = (unsigned HOST_WIDE_INT
) val
;
809 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
811 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
812 TYPE_PRECISION (get_gcov_type ()), false));
814 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
816 if (dump_enabled_p ())
817 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
818 "Transformation done: div/mod by constant %T\n", tree_val
);
820 gimple_assign_set_rhs_from_tree (si
, result
);
821 update_stmt (gsi_stmt (*si
));
826 /* Generate code for transformation 2 (with parent gimple assign STMT and
827 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
828 within roundoff error). This generates the result into a temp and returns
829 the temp; it does not replace or alter the original STMT. */
832 gimple_mod_pow2 (gassign
*stmt
, profile_probability prob
, gcov_type count
, gcov_type all
)
834 gassign
*stmt1
, *stmt2
, *stmt3
;
837 gimple
*bb1end
, *bb2end
, *bb3end
;
838 basic_block bb
, bb2
, bb3
, bb4
;
839 tree optype
, op1
, op2
;
840 edge e12
, e13
, e23
, e24
, e34
;
841 gimple_stmt_iterator gsi
;
844 gcc_assert (is_gimple_assign (stmt
)
845 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
847 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
848 op1
= gimple_assign_rhs1 (stmt
);
849 op2
= gimple_assign_rhs2 (stmt
);
851 bb
= gimple_bb (stmt
);
852 gsi
= gsi_for_stmt (stmt
);
854 result
= create_tmp_reg (optype
, "PROF");
855 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
856 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
857 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
858 build_int_cst (optype
, -1));
859 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
860 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
861 NULL_TREE
, NULL_TREE
);
862 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
863 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
864 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
867 /* tmp2 == op2-1 inherited from previous block. */
868 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
869 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
872 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
874 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
878 /* Edge e23 connects bb2 to bb3, etc. */
879 e12
= split_block (bb
, bb1end
);
881 bb2
->count
= profile_count::from_gcov_type (count
);
882 e23
= split_block (bb2
, bb2end
);
884 bb3
->count
= profile_count::from_gcov_type (all
- count
);
885 e34
= split_block (bb3
, bb3end
);
887 bb4
->count
= profile_count::from_gcov_type (all
);
889 e12
->flags
&= ~EDGE_FALLTHRU
;
890 e12
->flags
|= EDGE_FALSE_VALUE
;
891 e12
->probability
= prob
;
893 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
894 e13
->probability
= prob
.invert ();
898 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
899 e24
->probability
= profile_probability::always ();
901 e34
->probability
= profile_probability::always ();
906 /* Do transform 2) on INSN if applicable. */
909 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
911 histogram_value histogram
;
913 gcov_type count
, wrong_values
, all
;
914 tree lhs_type
, result
, value
;
915 profile_probability prob
;
918 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
922 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
923 if (!INTEGRAL_TYPE_P (lhs_type
))
926 code
= gimple_assign_rhs_code (stmt
);
928 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
931 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
935 value
= histogram
->hvalue
.value
;
936 wrong_values
= histogram
->hvalue
.counters
[0];
937 count
= histogram
->hvalue
.counters
[1];
939 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
941 /* We require that we hit a power of 2 at least half of all evaluations. */
942 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
943 || count
< wrong_values
944 || optimize_bb_for_size_p (gimple_bb (stmt
)))
947 /* Compute probability of taking the optimal path. */
948 all
= count
+ wrong_values
;
950 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
953 if (dump_enabled_p ())
954 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
955 "Transformation done: mod power of 2\n");
958 prob
= profile_probability::probability_in_gcov_type (count
, all
);
960 prob
= profile_probability::never ();
962 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
964 gimple_assign_set_rhs_from_tree (si
, result
);
965 update_stmt (gsi_stmt (*si
));
970 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
971 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
972 supported and this is built into this interface. The probabilities of taking
973 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
974 COUNT2/ALL respectively within roundoff error). This generates the
975 result into a temp and returns the temp; it does not replace or alter
976 the original STMT. */
977 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
980 gimple_mod_subtract (gassign
*stmt
, profile_probability prob1
,
981 profile_probability prob2
, int ncounts
,
982 gcov_type count1
, gcov_type count2
, gcov_type all
)
988 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
989 basic_block bb
, bb2
, bb3
, bb4
;
990 tree optype
, op1
, op2
;
991 edge e12
, e23
= 0, e24
, e34
, e14
;
992 gimple_stmt_iterator gsi
;
995 gcc_assert (is_gimple_assign (stmt
)
996 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
998 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
999 op1
= gimple_assign_rhs1 (stmt
);
1000 op2
= gimple_assign_rhs2 (stmt
);
1002 bb
= gimple_bb (stmt
);
1003 gsi
= gsi_for_stmt (stmt
);
1005 result
= create_tmp_reg (optype
, "PROF");
1006 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1007 stmt1
= gimple_build_assign (result
, op1
);
1008 stmt2
= gimple_build_assign (tmp1
, op2
);
1009 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1010 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1011 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1012 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1015 if (ncounts
) /* Assumed to be 0 or 1 */
1017 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1018 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1019 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1020 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1024 /* Fallback case. */
1025 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1027 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1031 /* Edge e23 connects bb2 to bb3, etc. */
1032 /* However block 3 is optional; if it is not there, references
1033 to 3 really refer to block 2. */
1034 e12
= split_block (bb
, bb1end
);
1036 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1038 if (ncounts
) /* Assumed to be 0 or 1. */
1040 e23
= split_block (bb2
, bb2end
);
1042 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1045 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1047 bb4
->count
= profile_count::from_gcov_type (all
);
1049 e12
->flags
&= ~EDGE_FALLTHRU
;
1050 e12
->flags
|= EDGE_FALSE_VALUE
;
1051 e12
->probability
= prob1
.invert ();
1053 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1054 e14
->probability
= prob1
;
1056 if (ncounts
) /* Assumed to be 0 or 1. */
1058 e23
->flags
&= ~EDGE_FALLTHRU
;
1059 e23
->flags
|= EDGE_FALSE_VALUE
;
1060 e23
->probability
= prob2
.invert ();
1062 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1063 e24
->probability
= prob2
;
1066 e34
->probability
= profile_probability::always ();
1071 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1074 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1076 histogram_value histogram
;
1077 enum tree_code code
;
1078 gcov_type count
, wrong_values
, all
;
1079 tree lhs_type
, result
;
1080 profile_probability prob1
, prob2
;
1081 unsigned int i
, steps
;
1082 gcov_type count1
, count2
;
1084 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1088 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1089 if (!INTEGRAL_TYPE_P (lhs_type
))
1092 code
= gimple_assign_rhs_code (stmt
);
1094 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1097 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1103 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1104 all
+= histogram
->hvalue
.counters
[i
];
1106 wrong_values
+= histogram
->hvalue
.counters
[i
];
1107 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1108 steps
= histogram
->hdata
.intvl
.steps
;
1109 all
+= wrong_values
;
1110 count1
= histogram
->hvalue
.counters
[0];
1111 count2
= histogram
->hvalue
.counters
[1];
1113 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1115 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1119 if (flag_profile_correction
&& count1
+ count2
> all
)
1120 all
= count1
+ count2
;
1122 gcc_assert (count1
+ count2
<= all
);
1124 /* We require that we use just subtractions in at least 50% of all
1127 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1129 count
+= histogram
->hvalue
.counters
[i
];
1130 if (count
* 2 >= all
)
1134 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1137 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1138 if (dump_enabled_p ())
1139 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1140 "Transformation done: mod subtract\n");
1142 /* Compute probability of taking the optimal path(s). */
1145 prob1
= profile_probability::probability_in_gcov_type (count1
, all
);
1146 prob2
= profile_probability::probability_in_gcov_type (count2
, all
);
1150 prob1
= prob2
= profile_probability::never ();
1153 /* In practice, "steps" is always 2. This interface reflects this,
1154 and will need to be changed if "steps" can change. */
1155 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1157 gimple_assign_set_rhs_from_tree (si
, result
);
1158 update_stmt (gsi_stmt (*si
));
1163 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1165 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1167 /* Returns true if node graph is initialized. This
1168 is used to test if profile_id has been created
1169 for cgraph_nodes. */
1172 coverage_node_map_initialized_p (void)
1174 return cgraph_node_map
!= 0;
1177 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1178 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1179 that the PROFILE_IDs was already assigned. */
1182 init_node_map (bool local
)
1184 struct cgraph_node
*n
;
1185 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1187 FOR_EACH_DEFINED_FUNCTION (n
)
1188 if (n
->has_gimple_body_p () || n
->thunk
.thunk_p
)
1191 dump_user_location_t loc
1192 = dump_user_location_t::from_function_decl (n
->decl
);
1195 n
->profile_id
= coverage_compute_profile_id (n
);
1196 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1199 if (dump_enabled_p ())
1200 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1201 "Local profile-id %i conflict"
1202 " with nodes %s %s\n",
1205 (*val
)->dump_name ());
1206 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1209 else if (!n
->profile_id
)
1211 if (dump_enabled_p ())
1212 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1213 "Node %s has no profile-id"
1214 " (profile feedback missing?)\n",
1218 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1220 if (dump_enabled_p ())
1221 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1222 "Node %s has IP profile-id %i conflict. "
1224 n
->dump_name (), n
->profile_id
);
1228 cgraph_node_map
->put (n
->profile_id
, n
);
1232 /* Delete the CGRAPH_NODE_MAP. */
1237 delete cgraph_node_map
;
1240 /* Return cgraph node for function with pid */
1243 find_func_by_profile_id (int profile_id
)
1245 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1252 /* Do transformation
1254 if (actual_callee_address == address_of_most_common_function/method)
1261 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1262 profile_probability prob
)
1267 tree tmp0
, tmp1
, tmp
;
1268 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1269 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1270 gimple_stmt_iterator gsi
;
1275 cond_bb
= gimple_bb (icall_stmt
);
1276 gsi
= gsi_for_stmt (icall_stmt
);
1278 tmp0
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1279 tmp1
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1280 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1281 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1282 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1284 tmp
= fold_convert (ptr_type_node
, build_addr (direct_call
->decl
));
1285 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1286 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1288 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1289 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1291 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1293 unlink_stmt_vdef (icall_stmt
);
1294 release_ssa_name (gimple_vdef (icall_stmt
));
1296 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1297 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1298 update_stmt (icall_stmt
);
1299 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1300 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1301 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1302 if ((dflags
& ECF_NORETURN
) != 0
1303 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1304 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1305 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1308 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1309 e_cd
= split_block (cond_bb
, cond_stmt
);
1310 dcall_bb
= e_cd
->dest
;
1311 dcall_bb
->count
= cond_bb
->count
.apply_probability (prob
);
1313 e_di
= split_block (dcall_bb
, dcall_stmt
);
1314 icall_bb
= e_di
->dest
;
1315 icall_bb
->count
= cond_bb
->count
- dcall_bb
->count
;
1317 /* Do not disturb existing EH edges from the indirect call. */
1318 if (!stmt_ends_bb_p (icall_stmt
))
1319 e_ij
= split_block (icall_bb
, icall_stmt
);
1322 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1323 /* The indirect call might be noreturn. */
1326 e_ij
->probability
= profile_probability::always ();
1327 e_ij
= single_pred_edge (split_edge (e_ij
));
1332 join_bb
= e_ij
->dest
;
1333 join_bb
->count
= cond_bb
->count
;
1336 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1337 e_cd
->probability
= prob
;
1339 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1340 e_ci
->probability
= prob
.invert ();
1346 if ((dflags
& ECF_NORETURN
) == 0)
1348 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1349 e_dj
->probability
= profile_probability::always ();
1351 e_ij
->probability
= profile_probability::always ();
1354 /* Insert PHI node for the call result if necessary. */
1355 if (gimple_call_lhs (icall_stmt
)
1356 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1357 && (dflags
& ECF_NORETURN
) == 0)
1359 tree result
= gimple_call_lhs (icall_stmt
);
1360 gphi
*phi
= create_phi_node (result
, join_bb
);
1361 gimple_call_set_lhs (icall_stmt
,
1362 duplicate_ssa_name (result
, icall_stmt
));
1363 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1364 gimple_call_set_lhs (dcall_stmt
,
1365 duplicate_ssa_name (result
, dcall_stmt
));
1366 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1369 /* Build an EH edge for the direct call if necessary. */
1370 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1371 if (lp_nr
> 0 && stmt_could_throw_p (cfun
, dcall_stmt
))
1373 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1376 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1377 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1379 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1380 e
->probability
= e_eh
->probability
;
1381 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1382 !gsi_end_p (psi
); gsi_next (&psi
))
1384 gphi
*phi
= psi
.phi ();
1385 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1386 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1389 if (!stmt_could_throw_p (cfun
, dcall_stmt
))
1390 gimple_purge_dead_eh_edges (dcall_bb
);
1394 /* Dump info about indirect call profile. */
1397 dump_ic_profile (gimple_stmt_iterator
*gsi
)
1400 histogram_value histogram
;
1401 gcov_type val
, count
, all
;
1402 struct cgraph_node
*direct_call
;
1404 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1408 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1411 if (gimple_call_internal_p (stmt
))
1414 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1419 all
= histogram
->hvalue
.counters
[0];
1421 for (unsigned j
= 0; j
< GCOV_TOPN_VALUES
; j
++)
1423 if (!get_nth_most_common_value (NULL
, "indirect call", histogram
, &val
,
1429 direct_call
= find_func_by_profile_id ((int) val
);
1431 if (direct_call
== NULL
)
1433 MSG_MISSED_OPTIMIZATION
, stmt
,
1434 "Indirect call -> direct call from other "
1435 "module %T=> %i (will resolve by ipa-profile only with LTO)\n",
1436 gimple_call_fn (stmt
), (int) val
);
1438 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1439 "Indirect call -> direct call "
1440 "%T => %T (will resolve by ipa-profile)\n",
1441 gimple_call_fn (stmt
), direct_call
->decl
);
1442 dump_printf_loc (MSG_NOTE
, stmt
,
1443 "hist->count %" PRId64
" hist->all %" PRId64
"\n",
1448 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1449 set to the argument index for the size of the string operation. */
1452 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1454 enum built_in_function fcode
;
1456 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1459 case BUILT_IN_MEMCPY
:
1460 case BUILT_IN_MEMPCPY
:
1461 case BUILT_IN_MEMMOVE
:
1463 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1464 INTEGER_TYPE
, VOID_TYPE
);
1465 case BUILT_IN_MEMSET
:
1467 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1468 INTEGER_TYPE
, VOID_TYPE
);
1469 case BUILT_IN_BZERO
:
1471 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1478 /* Convert stringop (..., vcall_size)
1480 if (vcall_size == icall_size)
1481 stringop (..., icall_size);
1483 stringop (..., vcall_size);
1484 assuming we'll propagate a true constant into ICALL_SIZE later. */
1487 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, profile_probability prob
,
1488 gcov_type count
, gcov_type all
)
1493 tree tmp0
, tmp1
, vcall_size
, optype
;
1494 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1495 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1496 gimple_stmt_iterator gsi
;
1499 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1502 cond_bb
= gimple_bb (vcall_stmt
);
1503 gsi
= gsi_for_stmt (vcall_stmt
);
1505 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1506 optype
= TREE_TYPE (vcall_size
);
1508 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1509 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1510 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1511 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1513 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1514 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1516 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1517 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1519 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1521 unlink_stmt_vdef (vcall_stmt
);
1522 release_ssa_name (gimple_vdef (vcall_stmt
));
1524 gimple_set_vdef (vcall_stmt
, NULL
);
1525 gimple_set_vuse (vcall_stmt
, NULL
);
1526 update_stmt (vcall_stmt
);
1527 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1528 gimple_call_set_arg (icall_stmt
, size_arg
,
1529 fold_convert (optype
, icall_size
));
1530 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1533 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1534 e_ci
= split_block (cond_bb
, cond_stmt
);
1535 icall_bb
= e_ci
->dest
;
1536 icall_bb
->count
= profile_count::from_gcov_type (count
);
1538 e_iv
= split_block (icall_bb
, icall_stmt
);
1539 vcall_bb
= e_iv
->dest
;
1540 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1542 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1543 join_bb
= e_vj
->dest
;
1544 join_bb
->count
= profile_count::from_gcov_type (all
);
1546 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1547 e_ci
->probability
= prob
;
1549 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1550 e_cv
->probability
= prob
.invert ();
1554 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1555 e_ij
->probability
= profile_probability::always ();
1557 e_vj
->probability
= profile_probability::always ();
1559 /* Insert PHI node for the call result if necessary. */
1560 if (gimple_call_lhs (vcall_stmt
)
1561 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1563 tree result
= gimple_call_lhs (vcall_stmt
);
1564 gphi
*phi
= create_phi_node (result
, join_bb
);
1565 gimple_call_set_lhs (vcall_stmt
,
1566 duplicate_ssa_name (result
, vcall_stmt
));
1567 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1568 gimple_call_set_lhs (icall_stmt
,
1569 duplicate_ssa_name (result
, icall_stmt
));
1570 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1573 /* Because these are all string op builtins, they're all nothrow. */
1574 gcc_assert (!stmt_could_throw_p (cfun
, vcall_stmt
));
1575 gcc_assert (!stmt_could_throw_p (cfun
, icall_stmt
));
1578 /* Find values inside STMT for that we want to measure histograms for
1579 division/modulo optimization. */
1582 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1586 enum built_in_function fcode
;
1587 histogram_value histogram
;
1588 gcov_type count
, all
, val
;
1590 unsigned int dest_align
, src_align
;
1591 profile_probability prob
;
1595 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1599 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1602 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1605 blck_size
= gimple_call_arg (stmt
, size_arg
);
1606 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1609 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
1610 HIST_TYPE_TOPN_VALUES
);
1614 if (!get_nth_most_common_value (stmt
, "stringops", histogram
, &val
, &count
,
1618 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1620 /* We require that count is at least half of all. */
1621 if (2 * count
< all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1623 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1626 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1628 prob
= profile_probability::never ();
1630 dest
= gimple_call_arg (stmt
, 0);
1631 dest_align
= get_pointer_alignment (dest
);
1632 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1635 case BUILT_IN_MEMCPY
:
1636 case BUILT_IN_MEMPCPY
:
1637 case BUILT_IN_MEMMOVE
:
1638 src
= gimple_call_arg (stmt
, 1);
1639 src_align
= get_pointer_alignment (src
);
1640 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1643 case BUILT_IN_MEMSET
:
1644 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1645 gimple_call_arg (stmt
, 1),
1649 case BUILT_IN_BZERO
:
1650 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1659 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1660 tree_val
= build_int_cst (get_gcov_type (), val
);
1664 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1665 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1667 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1668 TYPE_PRECISION (get_gcov_type ()), false));
1671 if (dump_enabled_p ())
1672 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1673 "Transformation done: single value %i stringop for %s\n",
1674 (int)val
, built_in_names
[(int)fcode
]);
1676 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1682 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1683 HOST_WIDE_INT
*expected_size
)
1685 histogram_value histogram
;
1686 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1689 *expected_size
= -1;
1690 else if (!histogram
->hvalue
.counters
[1])
1692 *expected_size
= -1;
1693 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1698 size
= ((histogram
->hvalue
.counters
[0]
1699 + histogram
->hvalue
.counters
[1] / 2)
1700 / histogram
->hvalue
.counters
[1]);
1701 /* Even if we can hold bigger value in SIZE, INT_MAX
1702 is safe "infinity" for code generation strategies. */
1705 *expected_size
= size
;
1706 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1709 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1712 *expected_align
= 0;
1713 else if (!histogram
->hvalue
.counters
[0])
1715 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1716 *expected_align
= 0;
1721 unsigned int alignment
;
1723 count
= histogram
->hvalue
.counters
[0];
1725 while (!(count
& alignment
)
1726 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1728 *expected_align
= alignment
* BITS_PER_UNIT
;
1729 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1734 /* Find values inside STMT for that we want to measure histograms for
1735 division/modulo optimization. */
1738 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1740 tree lhs
, divisor
, op0
, type
;
1741 histogram_value hist
;
1743 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1746 lhs
= gimple_assign_lhs (stmt
);
1747 type
= TREE_TYPE (lhs
);
1748 if (!INTEGRAL_TYPE_P (type
))
1751 switch (gimple_assign_rhs_code (stmt
))
1753 case TRUNC_DIV_EXPR
:
1754 case TRUNC_MOD_EXPR
:
1755 divisor
= gimple_assign_rhs2 (stmt
);
1756 op0
= gimple_assign_rhs1 (stmt
);
1758 if (TREE_CODE (divisor
) == SSA_NAME
)
1759 /* Check for the case where the divisor is the same value most
1761 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1762 HIST_TYPE_TOPN_VALUES
,
1765 /* For mod, check whether it is not often a noop (or replaceable by
1766 a few subtractions). */
1767 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1768 && TYPE_UNSIGNED (type
)
1769 && TREE_CODE (divisor
) == SSA_NAME
)
1772 /* Check for a special case where the divisor is power of 2. */
1773 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1776 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1777 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1779 hist
->hdata
.intvl
.int_start
= 0;
1780 hist
->hdata
.intvl
.steps
= 2;
1781 values
->safe_push (hist
);
1790 /* Find calls inside STMT for that we want to measure histograms for
1791 indirect/virtual call optimization. */
1794 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1798 if (gimple_code (stmt
) != GIMPLE_CALL
1799 || gimple_call_internal_p (stmt
)
1800 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1803 callee
= gimple_call_fn (stmt
);
1804 histogram_value v
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1806 values
->safe_push (v
);
1811 /* Find values inside STMT for that we want to measure histograms for
1812 string operations. */
1815 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1822 stmt
= dyn_cast
<gcall
*> (gs
);
1826 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
1829 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1832 dest
= gimple_call_arg (stmt
, 0);
1833 blck_size
= gimple_call_arg (stmt
, size_arg
);
1835 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1837 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1838 HIST_TYPE_TOPN_VALUES
,
1840 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1844 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1845 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1849 /* Find values inside STMT for that we want to measure histograms and adds
1850 them to list VALUES. */
1853 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1855 gimple_divmod_values_to_profile (stmt
, values
);
1856 gimple_stringops_values_to_profile (stmt
, values
);
1857 gimple_indirect_call_to_profile (stmt
, values
);
1861 gimple_find_values_to_profile (histogram_values
*values
)
1864 gimple_stmt_iterator gsi
;
1866 histogram_value hist
= NULL
;
1869 FOR_EACH_BB_FN (bb
, cfun
)
1870 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1871 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1873 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1874 HIST_TYPE_TIME_PROFILE
));
1876 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1880 case HIST_TYPE_INTERVAL
:
1881 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1884 case HIST_TYPE_POW2
:
1885 hist
->n_counters
= 2;
1888 case HIST_TYPE_TOPN_VALUES
:
1889 case HIST_TYPE_INDIR_CALL
:
1890 hist
->n_counters
= GCOV_TOPN_VALUES_COUNTERS
;
1893 case HIST_TYPE_TIME_PROFILE
:
1894 hist
->n_counters
= 1;
1897 case HIST_TYPE_AVERAGE
:
1898 hist
->n_counters
= 2;
1902 hist
->n_counters
= 1;
1908 if (dump_file
&& hist
->hvalue
.stmt
!= NULL
)
1910 fprintf (dump_file
, "Stmt ");
1911 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1912 dump_histogram_value (dump_file
, hist
);