1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2023 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 #include "tree-ssa-loop-manip.h"
48 /* In this file value profile based optimizations are placed. Currently the
49 following optimizations are implemented (for more detailed descriptions
50 see comments at value_profile_transformations):
52 1) Division/modulo specialization. Provided that we can determine that the
53 operands of the division have some special properties, we may use it to
54 produce more effective code.
56 2) Indirect/virtual call specialization. If we can determine most
57 common function callee in indirect/virtual call. We can use this
58 information to improve code effectiveness (especially info for
61 3) Speculative prefetching. If we are able to determine that the difference
62 between addresses accessed by a memory reference is usually constant, we
63 may add the prefetch instructions.
64 FIXME: This transformation was removed together with RTL based value
68 Value profiling internals
69 ==========================
71 Every value profiling transformation starts with defining what values
72 to profile. There are different histogram types (see HIST_TYPE_* in
73 value-prof.h) and each transformation can request one or more histogram
74 types per GIMPLE statement. The function gimple_find_values_to_profile()
75 collects the values to profile in a vec, and adds the number of counters
76 required for the different histogram types.
78 For a -fprofile-generate run, the statements for which values should be
79 recorded, are instrumented in instrument_values(). The instrumentation
80 is done by helper functions that can be found in tree-profile.cc, where
81 new types of histograms can be added if necessary.
83 After a -fprofile-use, the value profiling data is read back in by
84 compute_value_histograms() that translates the collected data to
85 histograms and attaches them to the profiled statements via
86 gimple_add_histogram_value(). Histograms are stored in a hash table
87 that is attached to every intrumented function, see VALUE_HISTOGRAMS
90 The value-profile transformations driver is the function
91 gimple_value_profile_transformations(). It traverses all statements in
92 the to-be-transformed function, and looks for statements with one or
93 more histograms attached to it. If a statement has histograms, the
94 transformation functions are called on the statement.
96 Limitations / FIXME / TODO:
97 * Only one histogram of each type can be associated with a statement.
98 * Some value profile transformations are done in builtins.cc (?!)
99 * Updating of histograms needs some TLC.
100 * The value profiling code could be used to record analysis results
101 from non-profiling (e.g. VRP).
102 * Adding new profilers should be simplified, starting with a cleanup
103 of what-happens-where and with making gimple_find_values_to_profile
104 and gimple_value_profile_transformations table-driven, perhaps...
107 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
108 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
109 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
110 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
111 static void dump_ic_profile (gimple_stmt_iterator
*gsi
);
113 /* Allocate histogram value. */
116 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
117 enum hist_type type
, gimple
*stmt
, tree value
)
119 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
120 hist
->hvalue
.value
= value
;
121 hist
->hvalue
.stmt
= stmt
;
122 hist
->hvalue
.lp
= NULL
;
128 gimple_alloc_histogram_value_loop (struct function
*fun ATTRIBUTE_UNUSED
,
129 enum hist_type type
, tree value
,
132 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
133 hist
->hvalue
.value
= value
;
134 hist
->hvalue
.stmt
= NULL
;
135 hist
->hvalue
.lp
= lp
;
140 /* Hash value for histogram. */
143 histogram_hash (const void *x
)
145 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
148 /* Return nonzero if statement for histogram_value X is Y. */
151 histogram_eq (const void *x
, const void *y
)
153 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const gimple
*) y
;
156 /* Set histogram for STMT. */
159 set_histogram_value (struct function
*fun
, gimple
*stmt
, histogram_value hist
)
162 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
164 if (!VALUE_HISTOGRAMS (fun
))
165 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
167 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
168 htab_hash_pointer (stmt
),
169 hist
? INSERT
: NO_INSERT
);
173 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
179 /* Get histogram list for STMT. */
182 gimple_histogram_value (struct function
*fun
, gimple
*stmt
)
184 if (!VALUE_HISTOGRAMS (fun
))
186 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
187 htab_hash_pointer (stmt
));
190 /* Add histogram for STMT. */
193 gimple_add_histogram_value (struct function
*fun
, gimple
*stmt
,
194 histogram_value hist
)
196 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
197 set_histogram_value (fun
, stmt
, hist
);
201 /* Remove histogram HIST from STMT's histogram list. */
204 gimple_remove_histogram_value (struct function
*fun
, gimple
*stmt
,
205 histogram_value hist
)
207 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
210 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
214 while (hist2
->hvalue
.next
!= hist
)
215 hist2
= hist2
->hvalue
.next
;
216 hist2
->hvalue
.next
= hist
->hvalue
.next
;
218 free (hist
->hvalue
.counters
);
220 memset (hist
, 0xab, sizeof (*hist
));
224 /* Lookup histogram of type TYPE in the STMT. */
227 gimple_histogram_value_of_type (struct function
*fun
, gimple
*stmt
,
230 histogram_value hist
;
231 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
232 hist
= hist
->hvalue
.next
)
233 if (hist
->type
== type
)
238 /* Dump information about HIST to DUMP_FILE. */
241 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
245 case HIST_TYPE_INTERVAL
:
246 if (hist
->hvalue
.counters
)
248 fprintf (dump_file
, "Interval counter range [%d,%d]: [",
249 hist
->hdata
.intvl
.int_start
,
250 (hist
->hdata
.intvl
.int_start
251 + hist
->hdata
.intvl
.steps
- 1));
254 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
256 fprintf (dump_file
, "%d:%" PRId64
,
257 hist
->hdata
.intvl
.int_start
+ i
,
258 (int64_t) hist
->hvalue
.counters
[i
]);
259 if (i
!= hist
->hdata
.intvl
.steps
- 1)
260 fprintf (dump_file
, ", ");
262 fprintf (dump_file
, "] outside range: %" PRId64
".\n",
263 (int64_t) hist
->hvalue
.counters
[i
]);
266 case HIST_TYPE_HISTOGRAM
:
267 if (hist
->hvalue
.counters
)
269 for (int i
= 0; i
<= param_profile_histogram_size_lin
; ++i
)
272 "Histogram counter histogram%" PRId64
":%" PRId64
".\n",
273 (int64_t) i
, (int64_t) hist
->hvalue
.counters
[i
]);
275 int lin2_log
= floor_log2 (param_profile_histogram_size_lin
);
276 for (int64_t i
= lin2_log
;
277 i
< param_profile_histogram_size_exp
+ lin2_log
; ++i
)
281 "Histogram counter histogram%" PRId64
":%" PRId64
".\n",
283 (int64_t) hist
->hvalue
284 .counters
[(param_profile_histogram_size_lin
- lin2_log
) + i
]);
286 for (int i
= 0; i
< param_profile_histogram_size_mod
; ++i
)
289 "Histogram counter histogram%" PRId64
" mod:%" PRId64
292 (int64_t) hist
->hvalue
293 .counters
[i
+ param_profile_histogram_size_lin
294 + param_profile_histogram_size_exp
]);
300 if (hist
->hvalue
.counters
)
301 fprintf (dump_file
, "Pow2 counter pow2:%" PRId64
302 " nonpow2:%" PRId64
".\n",
303 (int64_t) hist
->hvalue
.counters
[1],
304 (int64_t) hist
->hvalue
.counters
[0]);
307 case HIST_TYPE_TOPN_VALUES
:
308 case HIST_TYPE_INDIR_CALL
:
309 if (hist
->hvalue
.counters
)
312 (hist
->type
== HIST_TYPE_TOPN_VALUES
313 ? "Top N value counter" : "Indirect call counter"));
314 if (hist
->hvalue
.counters
)
316 unsigned count
= hist
->hvalue
.counters
[1];
317 fprintf (dump_file
, " all: %" PRId64
", %" PRId64
" values: ",
318 (int64_t) hist
->hvalue
.counters
[0], (int64_t) count
);
319 for (unsigned i
= 0; i
< count
; i
++)
321 fprintf (dump_file
, "[%" PRId64
":%" PRId64
"]",
322 (int64_t) hist
->hvalue
.counters
[2 * i
+ 2],
323 (int64_t) hist
->hvalue
.counters
[2 * i
+ 3]);
325 fprintf (dump_file
, ", ");
327 fprintf (dump_file
, ".\n");
332 case HIST_TYPE_AVERAGE
:
333 if (hist
->hvalue
.counters
)
334 fprintf (dump_file
, "Average value sum:%" PRId64
335 " times:%" PRId64
".\n",
336 (int64_t) hist
->hvalue
.counters
[0],
337 (int64_t) hist
->hvalue
.counters
[1]);
341 if (hist
->hvalue
.counters
)
342 fprintf (dump_file
, "IOR value ior:%" PRId64
".\n",
343 (int64_t) hist
->hvalue
.counters
[0]);
346 case HIST_TYPE_TIME_PROFILE
:
347 if (hist
->hvalue
.counters
)
348 fprintf (dump_file
, "Time profile time:%" PRId64
".\n",
349 (int64_t) hist
->hvalue
.counters
[0]);
356 /* Dump information about HIST to DUMP_FILE. */
359 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
364 bp
= bitpack_create (ob
->main_stream
);
365 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
366 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
367 streamer_write_bitpack (&bp
);
370 case HIST_TYPE_INTERVAL
:
371 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
372 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
377 for (i
= 0; i
< hist
->n_counters
; i
++)
379 /* When user uses an unsigned type with a big value, constant converted
380 to gcov_type (a signed type) can be negative. */
381 gcov_type value
= hist
->hvalue
.counters
[i
];
382 streamer_write_gcov_count (ob
, value
);
384 if (hist
->hvalue
.next
)
385 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
388 /* Dump information about HIST to DUMP_FILE. */
391 stream_in_histogram_value (class lto_input_block
*ib
, gimple
*stmt
)
394 unsigned int ncounters
= 0;
397 histogram_value new_val
;
399 histogram_value
*next_p
= NULL
;
403 bp
= streamer_read_bitpack (ib
);
404 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
405 next
= bp_unpack_value (&bp
, 1);
406 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
);
409 case HIST_TYPE_INTERVAL
:
410 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
411 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
412 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
415 case HIST_TYPE_HISTOGRAM
:
416 ncounters
= param_profile_histogram_size_lin
417 + param_profile_histogram_size_exp
418 + param_profile_histogram_size_mod
;
421 case HIST_TYPE_AVERAGE
:
425 case HIST_TYPE_TOPN_VALUES
:
426 case HIST_TYPE_INDIR_CALL
:
430 case HIST_TYPE_TIME_PROFILE
:
438 /* TOP N counters have variable number of counters. */
439 if (type
== HIST_TYPE_INDIR_CALL
|| type
== HIST_TYPE_TOPN_VALUES
)
441 gcov_type total
= streamer_read_gcov_count (ib
);
442 gcov_type ncounters
= streamer_read_gcov_count (ib
);
443 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
,
444 sizeof (*new_val
->hvalue
.counters
)
445 * (2 + 2 * ncounters
));
446 new_val
->hvalue
.counters
[0] = total
;
447 new_val
->hvalue
.counters
[1] = ncounters
;
448 new_val
->n_counters
= 2 + 2 * ncounters
;
449 for (i
= 0; i
< 2 * ncounters
; i
++)
450 new_val
->hvalue
.counters
[2 + i
] = streamer_read_gcov_count (ib
);
454 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
,
455 sizeof (*new_val
->hvalue
.counters
)
457 new_val
->n_counters
= ncounters
;
458 for (i
= 0; i
< ncounters
; i
++)
459 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
463 gimple_add_histogram_value (cfun
, stmt
, new_val
);
466 next_p
= &new_val
->hvalue
.next
;
471 /* Dump all histograms attached to STMT to DUMP_FILE. */
474 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
476 histogram_value hist
;
477 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
478 dump_histogram_value (dump_file
, hist
);
481 /* Remove all histograms associated with STMT. */
484 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
487 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
488 gimple_remove_histogram_value (fun
, stmt
, val
);
491 /* Duplicate all histograms associates with OSTMT to STMT. */
494 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
495 struct function
*ofun
, gimple
*ostmt
)
498 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
500 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
);
501 memcpy (new_val
, val
, sizeof (*val
));
502 new_val
->hvalue
.stmt
= stmt
;
503 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
504 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
505 gimple_add_histogram_value (fun
, stmt
, new_val
);
509 /* Move all histograms associated with OSTMT to STMT. */
512 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
514 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
517 /* The following three statements can't be reordered,
518 because histogram hashtab relies on stmt field value
519 for finding the exact slot. */
520 set_histogram_value (fun
, ostmt
, NULL
);
521 for (; val
!= NULL
; val
= val
->hvalue
.next
)
522 val
->hvalue
.stmt
= stmt
;
523 set_histogram_value (fun
, stmt
, val
);
527 static bool error_found
= false;
529 /* Helper function for verify_histograms. For each histogram reachable via htab
530 walk verify that it was reached via statement walk. */
533 visit_hist (void **slot
, void *data
)
535 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
536 histogram_value hist
= *(histogram_value
*) slot
;
538 if (!visited
->contains (hist
)
539 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
541 error ("dead histogram");
542 dump_histogram_value (stderr
, hist
);
543 debug_gimple_stmt (hist
->hvalue
.stmt
);
549 /* Verify sanity of the histograms. */
552 verify_histograms (void)
555 gimple_stmt_iterator gsi
;
556 histogram_value hist
;
559 hash_set
<histogram_value
> visited_hists
;
560 FOR_EACH_BB_FN (bb
, cfun
)
561 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
563 gimple
*stmt
= gsi_stmt (gsi
);
565 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
566 hist
= hist
->hvalue
.next
)
568 if (hist
->hvalue
.stmt
!= stmt
)
570 error ("histogram value statement does not correspond to "
571 "the statement it is associated with");
572 debug_gimple_stmt (stmt
);
573 dump_histogram_value (stderr
, hist
);
576 visited_hists
.add (hist
);
579 if (VALUE_HISTOGRAMS (cfun
))
580 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
582 internal_error ("%qs failed", __func__
);
585 /* Helper function for verify_histograms. For each histogram reachable via htab
586 walk verify that it was reached via statement walk. */
589 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
591 histogram_value hist
= *(histogram_value
*) slot
;
592 free (hist
->hvalue
.counters
);
598 free_histograms (struct function
*fn
)
600 if (VALUE_HISTOGRAMS (fn
))
602 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
603 htab_delete (VALUE_HISTOGRAMS (fn
));
604 VALUE_HISTOGRAMS (fn
) = NULL
;
608 /* The overall number of invocations of the counter should match
609 execution count of basic block. Report it as error rather than
610 internal error as it might mean that user has misused the profile
614 check_counter (gimple
*stmt
, const char * name
,
615 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
617 gcov_type bb_count
= bb_count_d
.ipa ().to_gcov_type ();
618 if (*all
!= bb_count
|| *count
> *all
)
620 dump_user_location_t locus
;
621 locus
= ((stmt
!= NULL
)
622 ? dump_user_location_t (stmt
)
623 : dump_user_location_t::from_function_decl
624 (current_function_decl
));
625 if (flag_profile_correction
)
627 if (dump_enabled_p ())
628 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
629 "correcting inconsistent value profile: %s "
630 "profiler overall count (%d) does not match BB "
631 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
639 error_at (locus
.get_location_t (), "corrupted value profile: %s "
640 "profile counter (%d out of %d) inconsistent with "
641 "basic-block count (%d)",
653 /* GIMPLE based transformations. */
656 gimple_value_profile_transformations (void)
659 gimple_stmt_iterator gsi
;
660 bool changed
= false;
662 FOR_EACH_BB_FN (bb
, cfun
)
664 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
666 gimple
*stmt
= gsi_stmt (gsi
);
667 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
673 fprintf (dump_file
, "Trying transformations on stmt ");
674 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
675 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
678 /* Transformations: */
679 /* The order of things in this conditional controls which
680 transformation is used when more than one is applicable. */
681 /* It is expected that any code added by the transformations
682 will be added before the current statement, and that the
683 current statement remain valid (although possibly
684 modified) upon return. */
685 if (gimple_mod_subtract_transform (&gsi
)
686 || gimple_divmod_fixed_value_transform (&gsi
)
687 || gimple_mod_pow2_value_transform (&gsi
)
688 || gimple_stringops_transform (&gsi
))
690 stmt
= gsi_stmt (gsi
);
692 /* Original statement may no longer be in the same block. */
693 if (bb
!= gimple_bb (stmt
))
695 bb
= gimple_bb (stmt
);
696 gsi
= gsi_for_stmt (stmt
);
700 /* The function never thansforms a GIMPLE statement. */
701 if (dump_enabled_p ())
702 dump_ic_profile (&gsi
);
709 /* Generate code for transformation 1 (with parent gimple assignment
710 STMT and probability of taking the optimal path PROB, which is
711 equivalent to COUNT/ALL within roundoff error). This generates the
712 result into a temp and returns the temp; it does not replace or
713 alter the original STMT. */
716 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, profile_probability prob
,
717 gcov_type count
, gcov_type all
)
719 gassign
*stmt1
, *stmt2
;
721 tree tmp0
, tmp1
, tmp2
;
722 gimple
*bb1end
, *bb2end
, *bb3end
;
723 basic_block bb
, bb2
, bb3
, bb4
;
724 tree optype
, op1
, op2
;
725 edge e12
, e13
, e23
, e24
, e34
;
726 gimple_stmt_iterator gsi
;
728 gcc_assert (is_gimple_assign (stmt
)
729 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
730 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
732 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
733 op1
= gimple_assign_rhs1 (stmt
);
734 op2
= gimple_assign_rhs2 (stmt
);
736 bb
= gimple_bb (stmt
);
737 gsi
= gsi_for_stmt (stmt
);
739 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
740 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
741 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
742 stmt2
= gimple_build_assign (tmp1
, op2
);
743 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
744 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
745 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
746 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
749 tmp2
= create_tmp_reg (optype
, "PROF");
750 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
751 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
754 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
755 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
759 /* Edge e23 connects bb2 to bb3, etc. */
760 e12
= split_block (bb
, bb1end
);
762 bb2
->count
= profile_count::from_gcov_type (count
);
763 e23
= split_block (bb2
, bb2end
);
765 bb3
->count
= profile_count::from_gcov_type (all
- count
);
766 e34
= split_block (bb3
, bb3end
);
768 bb4
->count
= profile_count::from_gcov_type (all
);
770 e12
->flags
&= ~EDGE_FALLTHRU
;
771 e12
->flags
|= EDGE_FALSE_VALUE
;
772 e12
->probability
= prob
;
774 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
775 e13
->probability
= prob
.invert ();
779 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
780 e24
->probability
= profile_probability::always ();
782 e34
->probability
= profile_probability::always ();
787 /* Return the n-th value count of TOPN_VALUE histogram. If
788 there's a value, return true and set VALUE and COUNT
791 Counters have the following meaning.
793 abs (counters[0]) is the number of executions
794 for i in 0 ... TOPN-1
795 counters[2 * i + 2] is target
796 counters[2 * i + 3] is corresponding hitrate counter.
798 Value of counters[0] negative when counter became
799 full during merging and some values are lost. */
802 get_nth_most_common_value (gimple
*stmt
, const char *counter_type
,
803 histogram_value hist
, gcov_type
*value
,
804 gcov_type
*count
, gcov_type
*all
, unsigned n
)
806 unsigned counters
= hist
->hvalue
.counters
[1];
813 gcov_type read_all
= abs_hwi (hist
->hvalue
.counters
[0]);
814 gcov_type covered
= 0;
815 for (unsigned i
= 0; i
< counters
; ++i
)
816 covered
+= hist
->hvalue
.counters
[2 * i
+ 3];
818 gcov_type v
= hist
->hvalue
.counters
[2 * n
+ 2];
819 gcov_type c
= hist
->hvalue
.counters
[2 * n
+ 3];
821 if (hist
->hvalue
.counters
[0] < 0
822 && flag_profile_reproducible
== PROFILE_REPRODUCIBILITY_PARALLEL_RUNS
)
825 fprintf (dump_file
, "Histogram value dropped in '%s' mode\n",
826 "-fprofile-reproducible=parallel-runs");
829 else if (covered
!= read_all
830 && flag_profile_reproducible
== PROFILE_REPRODUCIBILITY_MULTITHREADED
)
833 fprintf (dump_file
, "Histogram value dropped in '%s' mode\n",
834 "-fprofile-reproducible=multithreaded");
838 /* Indirect calls can't be verified. */
840 && check_counter (stmt
, counter_type
, &c
, &read_all
,
841 gimple_bb (stmt
)->count
))
851 /* Do transform 1) on INSN if applicable. */
854 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
856 histogram_value histogram
;
858 gcov_type val
, count
, all
;
859 tree result
, value
, tree_val
;
860 profile_probability prob
;
863 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
867 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
870 code
= gimple_assign_rhs_code (stmt
);
872 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
875 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
876 HIST_TYPE_TOPN_VALUES
);
880 if (!get_nth_most_common_value (stmt
, "divmod", histogram
, &val
, &count
,
884 value
= histogram
->hvalue
.value
;
885 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
887 /* We require that count is at least half of all. */
888 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
890 || optimize_bb_for_size_p (gimple_bb (stmt
)))
893 /* Compute probability of taking the optimal path. */
895 prob
= profile_probability::probability_in_gcov_type (count
, all
);
897 prob
= profile_probability::never ();
899 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
900 tree_val
= build_int_cst (get_gcov_type (), val
);
904 a
[0] = (unsigned HOST_WIDE_INT
) val
;
905 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
907 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
908 TYPE_PRECISION (get_gcov_type ()), false));
910 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
912 if (dump_enabled_p ())
913 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
914 "Transformation done: div/mod by constant %T\n", tree_val
);
916 gimple_assign_set_rhs_from_tree (si
, result
);
917 update_stmt (gsi_stmt (*si
));
922 /* Generate code for transformation 2 (with parent gimple assign STMT and
923 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
924 within roundoff error). This generates the result into a temp and returns
925 the temp; it does not replace or alter the original STMT. */
928 gimple_mod_pow2 (gassign
*stmt
, profile_probability prob
, gcov_type count
, gcov_type all
)
930 gassign
*stmt1
, *stmt2
, *stmt3
;
933 gimple
*bb1end
, *bb2end
, *bb3end
;
934 basic_block bb
, bb2
, bb3
, bb4
;
935 tree optype
, op1
, op2
;
936 edge e12
, e13
, e23
, e24
, e34
;
937 gimple_stmt_iterator gsi
;
940 gcc_assert (is_gimple_assign (stmt
)
941 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
943 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
944 op1
= gimple_assign_rhs1 (stmt
);
945 op2
= gimple_assign_rhs2 (stmt
);
947 bb
= gimple_bb (stmt
);
948 gsi
= gsi_for_stmt (stmt
);
950 result
= create_tmp_reg (optype
, "PROF");
951 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
952 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
953 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
954 build_int_cst (optype
, -1));
955 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
956 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
957 NULL_TREE
, NULL_TREE
);
958 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
959 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
960 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
963 /* tmp2 == op2-1 inherited from previous block. */
964 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
965 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
968 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
970 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
974 /* Edge e23 connects bb2 to bb3, etc. */
975 e12
= split_block (bb
, bb1end
);
977 bb2
->count
= profile_count::from_gcov_type (count
);
978 e23
= split_block (bb2
, bb2end
);
980 bb3
->count
= profile_count::from_gcov_type (all
- count
);
981 e34
= split_block (bb3
, bb3end
);
983 bb4
->count
= profile_count::from_gcov_type (all
);
985 e12
->flags
&= ~EDGE_FALLTHRU
;
986 e12
->flags
|= EDGE_FALSE_VALUE
;
987 e12
->probability
= prob
;
989 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
990 e13
->probability
= prob
.invert ();
994 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
995 e24
->probability
= profile_probability::always ();
997 e34
->probability
= profile_probability::always ();
1002 /* Do transform 2) on INSN if applicable. */
1005 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
1007 histogram_value histogram
;
1008 enum tree_code code
;
1009 gcov_type count
, wrong_values
, all
;
1010 tree lhs_type
, result
, value
;
1011 profile_probability prob
;
1014 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1018 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1019 if (!INTEGRAL_TYPE_P (lhs_type
))
1022 code
= gimple_assign_rhs_code (stmt
);
1024 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1027 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
1031 value
= histogram
->hvalue
.value
;
1032 wrong_values
= histogram
->hvalue
.counters
[0];
1033 count
= histogram
->hvalue
.counters
[1];
1035 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1037 /* We require that we hit a power of 2 at least half of all evaluations. */
1038 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
1039 || count
< wrong_values
1040 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1043 /* Compute probability of taking the optimal path. */
1044 all
= count
+ wrong_values
;
1046 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1049 if (dump_enabled_p ())
1050 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1051 "Transformation done: mod power of 2\n");
1054 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1056 prob
= profile_probability::never ();
1058 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1060 gimple_assign_set_rhs_from_tree (si
, result
);
1061 update_stmt (gsi_stmt (*si
));
1066 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1067 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1068 supported and this is built into this interface. The probabilities of taking
1069 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1070 COUNT2/ALL respectively within roundoff error). This generates the
1071 result into a temp and returns the temp; it does not replace or alter
1072 the original STMT. */
1073 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1076 gimple_mod_subtract (gassign
*stmt
, profile_probability prob1
,
1077 profile_probability prob2
, int ncounts
,
1078 gcov_type count1
, gcov_type count2
, gcov_type all
)
1084 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
1085 basic_block bb
, bb2
, bb3
, bb4
;
1086 tree optype
, op1
, op2
;
1087 edge e12
, e23
= 0, e24
, e34
, e14
;
1088 gimple_stmt_iterator gsi
;
1091 gcc_assert (is_gimple_assign (stmt
)
1092 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1094 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1095 op1
= gimple_assign_rhs1 (stmt
);
1096 op2
= gimple_assign_rhs2 (stmt
);
1098 bb
= gimple_bb (stmt
);
1099 gsi
= gsi_for_stmt (stmt
);
1101 result
= create_tmp_reg (optype
, "PROF");
1102 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1103 stmt1
= gimple_build_assign (result
, op1
);
1104 stmt2
= gimple_build_assign (tmp1
, op2
);
1105 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1106 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1107 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1108 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1111 if (ncounts
) /* Assumed to be 0 or 1 */
1113 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1114 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1115 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1116 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1120 /* Fallback case. */
1121 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1123 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1127 /* Edge e23 connects bb2 to bb3, etc. */
1128 /* However block 3 is optional; if it is not there, references
1129 to 3 really refer to block 2. */
1130 e12
= split_block (bb
, bb1end
);
1132 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1134 if (ncounts
) /* Assumed to be 0 or 1. */
1136 e23
= split_block (bb2
, bb2end
);
1138 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1141 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1143 bb4
->count
= profile_count::from_gcov_type (all
);
1145 e12
->flags
&= ~EDGE_FALLTHRU
;
1146 e12
->flags
|= EDGE_FALSE_VALUE
;
1147 e12
->probability
= prob1
.invert ();
1149 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1150 e14
->probability
= prob1
;
1152 if (ncounts
) /* Assumed to be 0 or 1. */
1154 e23
->flags
&= ~EDGE_FALLTHRU
;
1155 e23
->flags
|= EDGE_FALSE_VALUE
;
1156 e23
->probability
= prob2
.invert ();
1158 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1159 e24
->probability
= prob2
;
1162 e34
->probability
= profile_probability::always ();
1167 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1170 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1172 histogram_value histogram
;
1173 enum tree_code code
;
1174 gcov_type count
, wrong_values
, all
;
1175 tree lhs_type
, result
;
1176 profile_probability prob1
, prob2
;
1177 unsigned int i
, steps
;
1178 gcov_type count1
, count2
;
1180 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1184 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1185 if (!INTEGRAL_TYPE_P (lhs_type
))
1188 code
= gimple_assign_rhs_code (stmt
);
1190 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1193 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1199 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1200 all
+= histogram
->hvalue
.counters
[i
];
1202 wrong_values
+= histogram
->hvalue
.counters
[i
];
1203 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1204 steps
= histogram
->hdata
.intvl
.steps
;
1205 all
+= wrong_values
;
1206 count1
= histogram
->hvalue
.counters
[0];
1207 count2
= histogram
->hvalue
.counters
[1];
1209 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1211 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1215 if (flag_profile_correction
&& count1
+ count2
> all
)
1216 all
= count1
+ count2
;
1218 gcc_assert (count1
+ count2
<= all
);
1220 /* We require that we use just subtractions in at least 50% of all
1223 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1225 count
+= histogram
->hvalue
.counters
[i
];
1226 if (count
* 2 >= all
)
1230 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1233 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1234 if (dump_enabled_p ())
1235 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1236 "Transformation done: mod subtract\n");
1238 /* Compute probability of taking the optimal path(s). */
1241 prob1
= profile_probability::probability_in_gcov_type (count1
, all
);
1242 prob2
= profile_probability::probability_in_gcov_type (count2
, all
);
1246 prob1
= prob2
= profile_probability::never ();
1249 /* In practice, "steps" is always 2. This interface reflects this,
1250 and will need to be changed if "steps" can change. */
1251 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1253 gimple_assign_set_rhs_from_tree (si
, result
);
1254 update_stmt (gsi_stmt (*si
));
1259 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1261 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1263 /* Returns true if node graph is initialized. This
1264 is used to test if profile_id has been created
1265 for cgraph_nodes. */
1268 coverage_node_map_initialized_p (void)
1270 return cgraph_node_map
!= 0;
1273 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1274 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1275 that the PROFILE_IDs was already assigned. */
1278 init_node_map (bool local
)
1280 struct cgraph_node
*n
;
1281 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1283 FOR_EACH_DEFINED_FUNCTION (n
)
1284 if (n
->has_gimple_body_p () || n
->thunk
)
1287 dump_user_location_t loc
1288 = dump_user_location_t::from_function_decl (n
->decl
);
1291 n
->profile_id
= coverage_compute_profile_id (n
);
1292 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1295 if (dump_enabled_p ())
1296 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1297 "Local profile-id %i conflict"
1298 " with nodes %s %s\n",
1301 (*val
)->dump_name ());
1302 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1305 else if (!n
->profile_id
)
1307 if (dump_enabled_p ())
1308 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1309 "Node %s has no profile-id"
1310 " (profile feedback missing?)\n",
1314 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1316 if (dump_enabled_p ())
1317 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1318 "Node %s has IP profile-id %i conflict. "
1320 n
->dump_name (), n
->profile_id
);
1324 cgraph_node_map
->put (n
->profile_id
, n
);
1328 /* Delete the CGRAPH_NODE_MAP. */
1333 delete cgraph_node_map
;
1336 /* Return cgraph node for function with pid */
1339 find_func_by_profile_id (int profile_id
)
1341 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1348 /* Do transformation
1350 if (actual_callee_address == address_of_most_common_function/method)
1357 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1358 profile_probability prob
)
1363 tree tmp0
, tmp1
, tmp
;
1364 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1365 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1366 gimple_stmt_iterator gsi
;
1371 cond_bb
= gimple_bb (icall_stmt
);
1372 gsi
= gsi_for_stmt (icall_stmt
);
1374 tmp0
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1375 tmp1
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1376 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1377 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1378 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1380 tmp
= fold_convert (ptr_type_node
, build_addr (direct_call
->decl
));
1381 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1382 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1384 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1385 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1387 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1389 unlink_stmt_vdef (icall_stmt
);
1390 release_ssa_name (gimple_vdef (icall_stmt
));
1392 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1393 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1394 update_stmt (icall_stmt
);
1395 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1396 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1397 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1398 if ((dflags
& ECF_NORETURN
) != 0
1399 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1400 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1401 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1404 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1405 e_cd
= split_block (cond_bb
, cond_stmt
);
1406 dcall_bb
= e_cd
->dest
;
1407 dcall_bb
->count
= cond_bb
->count
.apply_probability (prob
);
1409 e_di
= split_block (dcall_bb
, dcall_stmt
);
1410 icall_bb
= e_di
->dest
;
1411 icall_bb
->count
= cond_bb
->count
- dcall_bb
->count
;
1413 /* Do not disturb existing EH edges from the indirect call. */
1414 if (!stmt_ends_bb_p (icall_stmt
))
1415 e_ij
= split_block (icall_bb
, icall_stmt
);
1418 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1419 /* The indirect call might be noreturn. */
1422 e_ij
->probability
= profile_probability::always ();
1423 e_ij
= single_pred_edge (split_edge (e_ij
));
1428 join_bb
= e_ij
->dest
;
1429 join_bb
->count
= cond_bb
->count
;
1432 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1433 e_cd
->probability
= prob
;
1435 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1436 e_ci
->probability
= prob
.invert ();
1442 if ((dflags
& ECF_NORETURN
) == 0)
1444 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1445 e_dj
->probability
= profile_probability::always ();
1447 e_ij
->probability
= profile_probability::always ();
1450 /* Insert PHI node for the call result if necessary. */
1451 if (gimple_call_lhs (icall_stmt
)
1452 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1453 && (dflags
& ECF_NORETURN
) == 0)
1455 tree result
= gimple_call_lhs (icall_stmt
);
1456 gphi
*phi
= create_phi_node (result
, join_bb
);
1457 gimple_call_set_lhs (icall_stmt
,
1458 duplicate_ssa_name (result
, icall_stmt
));
1459 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1460 gimple_call_set_lhs (dcall_stmt
,
1461 duplicate_ssa_name (result
, dcall_stmt
));
1462 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1465 /* Build an EH edge for the direct call if necessary. */
1466 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1467 if (lp_nr
> 0 && stmt_could_throw_p (cfun
, dcall_stmt
))
1469 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1472 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1473 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1475 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1476 e
->probability
= e_eh
->probability
;
1477 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1478 !gsi_end_p (psi
); gsi_next (&psi
))
1480 gphi
*phi
= psi
.phi ();
1481 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1482 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1485 if (!stmt_could_throw_p (cfun
, dcall_stmt
))
1486 gimple_purge_dead_eh_edges (dcall_bb
);
1490 /* Dump info about indirect call profile. */
1493 dump_ic_profile (gimple_stmt_iterator
*gsi
)
1496 histogram_value histogram
;
1497 gcov_type val
, count
, all
;
1498 struct cgraph_node
*direct_call
;
1500 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1504 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1507 if (gimple_call_internal_p (stmt
))
1510 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1515 all
= histogram
->hvalue
.counters
[0];
1517 for (unsigned j
= 0; j
< GCOV_TOPN_MAXIMUM_TRACKED_VALUES
; j
++)
1519 if (!get_nth_most_common_value (NULL
, "indirect call", histogram
, &val
,
1525 direct_call
= find_func_by_profile_id ((int) val
);
1527 if (direct_call
== NULL
)
1529 MSG_MISSED_OPTIMIZATION
, stmt
,
1530 "Indirect call -> direct call from other "
1531 "module %T=> %i (will resolve by ipa-profile only with LTO)\n",
1532 gimple_call_fn (stmt
), (int) val
);
1534 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1535 "Indirect call -> direct call "
1536 "%T => %T (will resolve by ipa-profile)\n",
1537 gimple_call_fn (stmt
), direct_call
->decl
);
1538 dump_printf_loc (MSG_NOTE
, stmt
,
1539 "hist->count %" PRId64
" hist->all %" PRId64
"\n",
1544 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1545 set to the argument index for the size of the string operation. */
1548 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1550 enum built_in_function fcode
;
1552 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1555 case BUILT_IN_MEMCPY
:
1556 case BUILT_IN_MEMPCPY
:
1557 case BUILT_IN_MEMMOVE
:
1559 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1560 INTEGER_TYPE
, VOID_TYPE
);
1561 case BUILT_IN_MEMSET
:
1563 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1564 INTEGER_TYPE
, VOID_TYPE
);
1565 case BUILT_IN_BZERO
:
1567 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1574 /* Convert stringop (..., vcall_size)
1576 if (vcall_size == icall_size)
1577 stringop (..., icall_size);
1579 stringop (..., vcall_size);
1580 assuming we'll propagate a true constant into ICALL_SIZE later. */
1583 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, profile_probability prob
,
1584 gcov_type count
, gcov_type all
)
1589 tree tmp0
, tmp1
, vcall_size
, optype
;
1590 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1591 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1592 gimple_stmt_iterator gsi
;
1595 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1598 cond_bb
= gimple_bb (vcall_stmt
);
1599 gsi
= gsi_for_stmt (vcall_stmt
);
1601 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1602 optype
= TREE_TYPE (vcall_size
);
1604 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1605 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1606 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1607 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1609 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1610 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1612 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1613 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1615 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1617 unlink_stmt_vdef (vcall_stmt
);
1618 release_ssa_name (gimple_vdef (vcall_stmt
));
1620 gimple_set_vdef (vcall_stmt
, NULL
);
1621 gimple_set_vuse (vcall_stmt
, NULL
);
1622 update_stmt (vcall_stmt
);
1623 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1624 gimple_call_set_arg (icall_stmt
, size_arg
,
1625 fold_convert (optype
, icall_size
));
1626 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1629 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1630 e_ci
= split_block (cond_bb
, cond_stmt
);
1631 icall_bb
= e_ci
->dest
;
1632 icall_bb
->count
= profile_count::from_gcov_type (count
);
1634 e_iv
= split_block (icall_bb
, icall_stmt
);
1635 vcall_bb
= e_iv
->dest
;
1636 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1638 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1639 join_bb
= e_vj
->dest
;
1640 join_bb
->count
= profile_count::from_gcov_type (all
);
1642 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1643 e_ci
->probability
= prob
;
1645 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1646 e_cv
->probability
= prob
.invert ();
1650 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1651 e_ij
->probability
= profile_probability::always ();
1653 e_vj
->probability
= profile_probability::always ();
1655 /* Insert PHI node for the call result if necessary. */
1656 if (gimple_call_lhs (vcall_stmt
)
1657 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1659 tree result
= gimple_call_lhs (vcall_stmt
);
1660 gphi
*phi
= create_phi_node (result
, join_bb
);
1661 gimple_call_set_lhs (vcall_stmt
,
1662 duplicate_ssa_name (result
, vcall_stmt
));
1663 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1664 gimple_call_set_lhs (icall_stmt
,
1665 duplicate_ssa_name (result
, icall_stmt
));
1666 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1669 /* Because these are all string op builtins, they're all nothrow. */
1670 gcc_assert (!stmt_could_throw_p (cfun
, vcall_stmt
));
1671 gcc_assert (!stmt_could_throw_p (cfun
, icall_stmt
));
1674 /* Find values inside STMT for that we want to measure histograms for
1675 division/modulo optimization. */
1678 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1682 enum built_in_function fcode
;
1683 histogram_value histogram
;
1684 gcov_type count
, all
, val
;
1686 unsigned int dest_align
, src_align
;
1687 profile_probability prob
;
1691 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1695 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1698 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1701 blck_size
= gimple_call_arg (stmt
, size_arg
);
1702 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1705 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
1706 HIST_TYPE_TOPN_VALUES
);
1710 if (!get_nth_most_common_value (stmt
, "stringops", histogram
, &val
, &count
,
1714 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1716 /* We require that count is at least half of all. */
1717 if (2 * count
< all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1719 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1722 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1724 prob
= profile_probability::never ();
1726 dest
= gimple_call_arg (stmt
, 0);
1727 dest_align
= get_pointer_alignment (dest
);
1728 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1731 case BUILT_IN_MEMCPY
:
1732 case BUILT_IN_MEMPCPY
:
1733 case BUILT_IN_MEMMOVE
:
1734 src
= gimple_call_arg (stmt
, 1);
1735 src_align
= get_pointer_alignment (src
);
1736 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1739 case BUILT_IN_MEMSET
:
1740 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1741 gimple_call_arg (stmt
, 1),
1745 case BUILT_IN_BZERO
:
1746 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1755 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1756 tree_val
= build_int_cst (get_gcov_type (), val
);
1760 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1761 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1763 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1764 TYPE_PRECISION (get_gcov_type ()), false));
1767 if (dump_enabled_p ())
1768 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1769 "Transformation done: single value %i stringop for %s\n",
1770 (int)val
, built_in_names
[(int)fcode
]);
1772 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1778 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1779 HOST_WIDE_INT
*expected_size
)
1781 histogram_value histogram
;
1782 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1785 *expected_size
= -1;
1786 else if (!histogram
->hvalue
.counters
[1])
1788 *expected_size
= -1;
1789 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1794 size
= ((histogram
->hvalue
.counters
[0]
1795 + histogram
->hvalue
.counters
[1] / 2)
1796 / histogram
->hvalue
.counters
[1]);
1797 /* Even if we can hold bigger value in SIZE, INT_MAX
1798 is safe "infinity" for code generation strategies. */
1801 *expected_size
= size
;
1802 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1805 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1808 *expected_align
= 0;
1809 else if (!histogram
->hvalue
.counters
[0])
1811 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1812 *expected_align
= 0;
1817 unsigned int alignment
;
1819 count
= histogram
->hvalue
.counters
[0];
1821 while (!(count
& alignment
)
1822 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1824 *expected_align
= alignment
* BITS_PER_UNIT
;
1825 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1830 /* Find values inside STMT for that we want to measure histograms for
1831 division/modulo optimization. */
1834 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1836 tree lhs
, divisor
, op0
, type
;
1837 histogram_value hist
;
1839 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1842 lhs
= gimple_assign_lhs (stmt
);
1843 type
= TREE_TYPE (lhs
);
1844 if (!INTEGRAL_TYPE_P (type
))
1847 switch (gimple_assign_rhs_code (stmt
))
1849 case TRUNC_DIV_EXPR
:
1850 case TRUNC_MOD_EXPR
:
1851 divisor
= gimple_assign_rhs2 (stmt
);
1852 op0
= gimple_assign_rhs1 (stmt
);
1854 if (TREE_CODE (divisor
) == SSA_NAME
)
1856 /* Check for the case where the divisor is the same value most
1859 gimple_alloc_histogram_value (cfun
, HIST_TYPE_TOPN_VALUES
, stmt
,
1863 /* For mod, check whether it is not often a noop (or replaceable by
1864 a few subtractions). */
1865 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1866 && TYPE_UNSIGNED (type
)
1867 && TREE_CODE (divisor
) == SSA_NAME
)
1870 /* Check for a special case where the divisor is power of 2. */
1871 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1875 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1876 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1878 hist
->hdata
.intvl
.int_start
= 0;
1879 hist
->hdata
.intvl
.steps
= 2;
1880 values
->safe_push (hist
);
1889 /* Find calls inside STMT for that we want to measure histograms for
1890 indirect/virtual call optimization. */
1893 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1897 if (gimple_code (stmt
) != GIMPLE_CALL
1898 || gimple_call_internal_p (stmt
)
1899 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1902 callee
= gimple_call_fn (stmt
);
1903 histogram_value v
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1905 values
->safe_push (v
);
1910 /* Find values inside STMT for that we want to measure histograms for
1911 string operations. */
1914 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1921 stmt
= dyn_cast
<gcall
*> (gs
);
1925 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
1928 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1931 dest
= gimple_call_arg (stmt
, 0);
1932 blck_size
= gimple_call_arg (stmt
, size_arg
);
1934 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1936 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1937 HIST_TYPE_TOPN_VALUES
,
1939 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1943 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1944 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1949 gimple_histogram_values_to_profile (function
*fun
, histogram_values
*values
)
1951 for (auto loop
: loops_list (fun
, 0))
1954 gimple_stmt_iterator gsi
;
1956 gsi
= gsi_start_bb (loop
->latch
);
1957 create_iv (build_int_cst_type (get_gcov_type (), 0),
1958 build_int_cst (get_gcov_type (), 1), NULL_TREE
, loop
, &gsi
,
1960 values
->safe_push (gimple_alloc_histogram_value_loop (fun
,
1961 HIST_TYPE_HISTOGRAM
,
1966 /* Find values inside STMT for that we want to measure histograms and adds
1967 them to list VALUES. */
1970 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1972 gimple_divmod_values_to_profile (stmt
, values
);
1973 gimple_stringops_values_to_profile (stmt
, values
);
1974 gimple_indirect_call_to_profile (stmt
, values
);
1978 gimple_find_values_to_profile (histogram_values
*values
)
1981 gimple_stmt_iterator gsi
;
1983 histogram_value hist
= NULL
;
1985 gimple_histogram_values_to_profile (cfun
, values
);
1986 FOR_EACH_BB_FN (bb
, cfun
)
1987 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1988 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1990 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1991 HIST_TYPE_TIME_PROFILE
));
1993 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1997 case HIST_TYPE_INTERVAL
:
1998 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2001 case HIST_TYPE_POW2
:
2002 hist
->n_counters
= 2;
2005 case HIST_TYPE_TOPN_VALUES
:
2006 case HIST_TYPE_INDIR_CALL
:
2007 hist
->n_counters
= GCOV_TOPN_MEM_COUNTERS
;
2010 case HIST_TYPE_TIME_PROFILE
:
2011 hist
->n_counters
= 1;
2014 case HIST_TYPE_AVERAGE
:
2015 hist
->n_counters
= 2;
2019 hist
->n_counters
= 1;
2022 case HIST_TYPE_HISTOGRAM
:
2023 hist
->n_counters
= param_profile_histogram_size_lin
2024 + param_profile_histogram_size_exp
2025 + param_profile_histogram_size_mod
;
2031 if (dump_file
&& hist
->hvalue
.stmt
!= NULL
)
2033 fprintf (dump_file
, "Stmt ");
2034 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2035 dump_histogram_value (dump_file
, hist
);