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
"%s, values: ",
269 (int64_t) abs_hwi (hist
->hvalue
.counters
[0]),
270 hist
->hvalue
.counters
[0] < 0
271 ? " (values missing)": "");
272 for (unsigned i
= 0; i
< GCOV_TOPN_VALUES
; i
++)
274 fprintf (dump_file
, "[%" PRId64
":%" PRId64
"]",
275 (int64_t) hist
->hvalue
.counters
[2 * i
+ 1],
276 (int64_t) hist
->hvalue
.counters
[2 * i
+ 2]);
277 if (i
!= GCOV_TOPN_VALUES
- 1)
278 fprintf (dump_file
, ", ");
280 fprintf (dump_file
, ".\n");
285 case HIST_TYPE_AVERAGE
:
286 if (hist
->hvalue
.counters
)
287 fprintf (dump_file
, "Average value sum:%" PRId64
288 " times:%" PRId64
".\n",
289 (int64_t) hist
->hvalue
.counters
[0],
290 (int64_t) hist
->hvalue
.counters
[1]);
294 if (hist
->hvalue
.counters
)
295 fprintf (dump_file
, "IOR value ior:%" PRId64
".\n",
296 (int64_t) hist
->hvalue
.counters
[0]);
299 case HIST_TYPE_TIME_PROFILE
:
300 if (hist
->hvalue
.counters
)
301 fprintf (dump_file
, "Time profile time:%" PRId64
".\n",
302 (int64_t) hist
->hvalue
.counters
[0]);
309 /* Dump information about HIST to DUMP_FILE. */
312 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
317 bp
= bitpack_create (ob
->main_stream
);
318 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
319 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
320 streamer_write_bitpack (&bp
);
323 case HIST_TYPE_INTERVAL
:
324 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
325 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
330 for (i
= 0; i
< hist
->n_counters
; i
++)
332 /* When user uses an unsigned type with a big value, constant converted
333 to gcov_type (a signed type) can be negative. */
334 gcov_type value
= hist
->hvalue
.counters
[i
];
335 if (hist
->type
== HIST_TYPE_TOPN_VALUES
)
338 gcc_assert (value
>= 0);
340 streamer_write_gcov_count (ob
, value
);
342 if (hist
->hvalue
.next
)
343 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
346 /* Dump information about HIST to DUMP_FILE. */
349 stream_in_histogram_value (class lto_input_block
*ib
, gimple
*stmt
)
352 unsigned int ncounters
= 0;
355 histogram_value new_val
;
357 histogram_value
*next_p
= NULL
;
361 bp
= streamer_read_bitpack (ib
);
362 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
363 next
= bp_unpack_value (&bp
, 1);
364 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
);
367 case HIST_TYPE_INTERVAL
:
368 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
369 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
370 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
374 case HIST_TYPE_AVERAGE
:
378 case HIST_TYPE_TOPN_VALUES
:
379 case HIST_TYPE_INDIR_CALL
:
380 ncounters
= GCOV_TOPN_VALUES_COUNTERS
;
384 case HIST_TYPE_TIME_PROFILE
:
391 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
,
392 sizeof (*new_val
->hvalue
.counters
)
394 new_val
->n_counters
= ncounters
;
395 for (i
= 0; i
< ncounters
; i
++)
396 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
398 gimple_add_histogram_value (cfun
, stmt
, new_val
);
401 next_p
= &new_val
->hvalue
.next
;
406 /* Dump all histograms attached to STMT to DUMP_FILE. */
409 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
411 histogram_value hist
;
412 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
413 dump_histogram_value (dump_file
, hist
);
416 /* Remove all histograms associated with STMT. */
419 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
422 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
423 gimple_remove_histogram_value (fun
, stmt
, val
);
426 /* Duplicate all histograms associates with OSTMT to STMT. */
429 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
430 struct function
*ofun
, gimple
*ostmt
)
433 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
435 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
);
436 memcpy (new_val
, val
, sizeof (*val
));
437 new_val
->hvalue
.stmt
= stmt
;
438 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
439 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
440 gimple_add_histogram_value (fun
, stmt
, new_val
);
444 /* Move all histograms associated with OSTMT to STMT. */
447 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
449 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
452 /* The following three statements can't be reordered,
453 because histogram hashtab relies on stmt field value
454 for finding the exact slot. */
455 set_histogram_value (fun
, ostmt
, NULL
);
456 for (; val
!= NULL
; val
= val
->hvalue
.next
)
457 val
->hvalue
.stmt
= stmt
;
458 set_histogram_value (fun
, stmt
, val
);
462 static bool error_found
= false;
464 /* Helper function for verify_histograms. For each histogram reachable via htab
465 walk verify that it was reached via statement walk. */
468 visit_hist (void **slot
, void *data
)
470 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
471 histogram_value hist
= *(histogram_value
*) slot
;
473 if (!visited
->contains (hist
)
474 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
476 error ("dead histogram");
477 dump_histogram_value (stderr
, hist
);
478 debug_gimple_stmt (hist
->hvalue
.stmt
);
484 /* Verify sanity of the histograms. */
487 verify_histograms (void)
490 gimple_stmt_iterator gsi
;
491 histogram_value hist
;
494 hash_set
<histogram_value
> visited_hists
;
495 FOR_EACH_BB_FN (bb
, cfun
)
496 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
498 gimple
*stmt
= gsi_stmt (gsi
);
500 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
501 hist
= hist
->hvalue
.next
)
503 if (hist
->hvalue
.stmt
!= stmt
)
505 error ("histogram value statement does not correspond to "
506 "the statement it is associated with");
507 debug_gimple_stmt (stmt
);
508 dump_histogram_value (stderr
, hist
);
511 visited_hists
.add (hist
);
514 if (VALUE_HISTOGRAMS (cfun
))
515 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
517 internal_error ("%qs failed", __func__
);
520 /* Helper function for verify_histograms. For each histogram reachable via htab
521 walk verify that it was reached via statement walk. */
524 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
526 histogram_value hist
= *(histogram_value
*) slot
;
527 free (hist
->hvalue
.counters
);
533 free_histograms (struct function
*fn
)
535 if (VALUE_HISTOGRAMS (fn
))
537 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
538 htab_delete (VALUE_HISTOGRAMS (fn
));
539 VALUE_HISTOGRAMS (fn
) = NULL
;
543 /* The overall number of invocations of the counter should match
544 execution count of basic block. Report it as error rather than
545 internal error as it might mean that user has misused the profile
549 check_counter (gimple
*stmt
, const char * name
,
550 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
552 gcov_type bb_count
= bb_count_d
.ipa ().to_gcov_type ();
553 if (*all
!= bb_count
|| *count
> *all
)
555 dump_user_location_t locus
;
556 locus
= ((stmt
!= NULL
)
557 ? dump_user_location_t (stmt
)
558 : dump_user_location_t::from_function_decl
559 (current_function_decl
));
560 if (flag_profile_correction
)
562 if (dump_enabled_p ())
563 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
564 "correcting inconsistent value profile: %s "
565 "profiler overall count (%d) does not match BB "
566 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
574 error_at (locus
.get_location_t (), "corrupted value profile: %s "
575 "profile counter (%d out of %d) inconsistent with "
576 "basic-block count (%d)",
588 /* GIMPLE based transformations. */
591 gimple_value_profile_transformations (void)
594 gimple_stmt_iterator gsi
;
595 bool changed
= false;
597 FOR_EACH_BB_FN (bb
, cfun
)
599 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
601 gimple
*stmt
= gsi_stmt (gsi
);
602 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
608 fprintf (dump_file
, "Trying transformations on stmt ");
609 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
610 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
613 /* Transformations: */
614 /* The order of things in this conditional controls which
615 transformation is used when more than one is applicable. */
616 /* It is expected that any code added by the transformations
617 will be added before the current statement, and that the
618 current statement remain valid (although possibly
619 modified) upon return. */
620 if (gimple_mod_subtract_transform (&gsi
)
621 || gimple_divmod_fixed_value_transform (&gsi
)
622 || gimple_mod_pow2_value_transform (&gsi
)
623 || gimple_stringops_transform (&gsi
))
625 stmt
= gsi_stmt (gsi
);
627 /* Original statement may no longer be in the same block. */
628 if (bb
!= gimple_bb (stmt
))
630 bb
= gimple_bb (stmt
);
631 gsi
= gsi_for_stmt (stmt
);
635 /* The function never thansforms a GIMPLE statement. */
636 if (dump_enabled_p ())
637 dump_ic_profile (&gsi
);
644 /* Generate code for transformation 1 (with parent gimple assignment
645 STMT and probability of taking the optimal path PROB, which is
646 equivalent to COUNT/ALL within roundoff error). This generates the
647 result into a temp and returns the temp; it does not replace or
648 alter the original STMT. */
651 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, profile_probability prob
,
652 gcov_type count
, gcov_type all
)
654 gassign
*stmt1
, *stmt2
;
656 tree tmp0
, tmp1
, tmp2
;
657 gimple
*bb1end
, *bb2end
, *bb3end
;
658 basic_block bb
, bb2
, bb3
, bb4
;
659 tree optype
, op1
, op2
;
660 edge e12
, e13
, e23
, e24
, e34
;
661 gimple_stmt_iterator gsi
;
663 gcc_assert (is_gimple_assign (stmt
)
664 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
665 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
667 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
668 op1
= gimple_assign_rhs1 (stmt
);
669 op2
= gimple_assign_rhs2 (stmt
);
671 bb
= gimple_bb (stmt
);
672 gsi
= gsi_for_stmt (stmt
);
674 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
675 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
676 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
677 stmt2
= gimple_build_assign (tmp1
, op2
);
678 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
679 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
680 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
681 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
684 tmp2
= create_tmp_reg (optype
, "PROF");
685 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
686 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
689 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
690 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
694 /* Edge e23 connects bb2 to bb3, etc. */
695 e12
= split_block (bb
, bb1end
);
697 bb2
->count
= profile_count::from_gcov_type (count
);
698 e23
= split_block (bb2
, bb2end
);
700 bb3
->count
= profile_count::from_gcov_type (all
- count
);
701 e34
= split_block (bb3
, bb3end
);
703 bb4
->count
= profile_count::from_gcov_type (all
);
705 e12
->flags
&= ~EDGE_FALLTHRU
;
706 e12
->flags
|= EDGE_FALSE_VALUE
;
707 e12
->probability
= prob
;
709 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
710 e13
->probability
= prob
.invert ();
714 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
715 e24
->probability
= profile_probability::always ();
717 e34
->probability
= profile_probability::always ();
722 /* Return the n-th value count of TOPN_VALUE histogram. If
723 there's a value, return true and set VALUE and COUNT
726 Counters have the following meaning.
728 abs (counters[0]) is the number of executions
729 for i in 0 ... TOPN-1
730 counters[2 * i + 1] is target
731 abs (counters[2 * i + 2]) is corresponding hitrate counter.
733 Value of counters[0] negative when counter became
734 full during merging and some values are lost. */
737 get_nth_most_common_value (gimple
*stmt
, const char *counter_type
,
738 histogram_value hist
, gcov_type
*value
,
739 gcov_type
*count
, gcov_type
*all
, unsigned n
)
741 gcc_assert (n
< GCOV_TOPN_VALUES
);
746 gcov_type read_all
= abs_hwi (hist
->hvalue
.counters
[0]);
748 gcov_type v
= hist
->hvalue
.counters
[2 * n
+ 1];
749 gcov_type c
= hist
->hvalue
.counters
[2 * n
+ 2];
751 if (hist
->hvalue
.counters
[0] < 0
752 && (flag_profile_reproducible
== PROFILE_REPRODUCIBILITY_PARALLEL_RUNS
753 || (flag_profile_reproducible
754 == PROFILE_REPRODUCIBILITY_MULTITHREADED
)))
757 /* Indirect calls can't be verified. */
759 && check_counter (stmt
, counter_type
, &c
, &read_all
,
760 gimple_bb (stmt
)->count
))
770 /* Do transform 1) on INSN if applicable. */
773 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
775 histogram_value histogram
;
777 gcov_type val
, count
, all
;
778 tree result
, value
, tree_val
;
779 profile_probability prob
;
782 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
786 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
789 code
= gimple_assign_rhs_code (stmt
);
791 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
794 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
795 HIST_TYPE_TOPN_VALUES
);
799 if (!get_nth_most_common_value (stmt
, "divmod", histogram
, &val
, &count
,
803 value
= histogram
->hvalue
.value
;
804 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
806 /* We require that count is at least half of all. */
807 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
809 || optimize_bb_for_size_p (gimple_bb (stmt
)))
812 /* Compute probability of taking the optimal path. */
814 prob
= profile_probability::probability_in_gcov_type (count
, all
);
816 prob
= profile_probability::never ();
818 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
819 tree_val
= build_int_cst (get_gcov_type (), val
);
823 a
[0] = (unsigned HOST_WIDE_INT
) val
;
824 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
826 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
827 TYPE_PRECISION (get_gcov_type ()), false));
829 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
831 if (dump_enabled_p ())
832 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
833 "Transformation done: div/mod by constant %T\n", tree_val
);
835 gimple_assign_set_rhs_from_tree (si
, result
);
836 update_stmt (gsi_stmt (*si
));
841 /* Generate code for transformation 2 (with parent gimple assign STMT and
842 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
843 within roundoff error). This generates the result into a temp and returns
844 the temp; it does not replace or alter the original STMT. */
847 gimple_mod_pow2 (gassign
*stmt
, profile_probability prob
, gcov_type count
, gcov_type all
)
849 gassign
*stmt1
, *stmt2
, *stmt3
;
852 gimple
*bb1end
, *bb2end
, *bb3end
;
853 basic_block bb
, bb2
, bb3
, bb4
;
854 tree optype
, op1
, op2
;
855 edge e12
, e13
, e23
, e24
, e34
;
856 gimple_stmt_iterator gsi
;
859 gcc_assert (is_gimple_assign (stmt
)
860 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
862 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
863 op1
= gimple_assign_rhs1 (stmt
);
864 op2
= gimple_assign_rhs2 (stmt
);
866 bb
= gimple_bb (stmt
);
867 gsi
= gsi_for_stmt (stmt
);
869 result
= create_tmp_reg (optype
, "PROF");
870 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
871 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
872 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
873 build_int_cst (optype
, -1));
874 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
875 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
876 NULL_TREE
, NULL_TREE
);
877 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
878 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
879 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
882 /* tmp2 == op2-1 inherited from previous block. */
883 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
884 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
887 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
889 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
893 /* Edge e23 connects bb2 to bb3, etc. */
894 e12
= split_block (bb
, bb1end
);
896 bb2
->count
= profile_count::from_gcov_type (count
);
897 e23
= split_block (bb2
, bb2end
);
899 bb3
->count
= profile_count::from_gcov_type (all
- count
);
900 e34
= split_block (bb3
, bb3end
);
902 bb4
->count
= profile_count::from_gcov_type (all
);
904 e12
->flags
&= ~EDGE_FALLTHRU
;
905 e12
->flags
|= EDGE_FALSE_VALUE
;
906 e12
->probability
= prob
;
908 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
909 e13
->probability
= prob
.invert ();
913 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
914 e24
->probability
= profile_probability::always ();
916 e34
->probability
= profile_probability::always ();
921 /* Do transform 2) on INSN if applicable. */
924 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
926 histogram_value histogram
;
928 gcov_type count
, wrong_values
, all
;
929 tree lhs_type
, result
, value
;
930 profile_probability prob
;
933 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
937 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
938 if (!INTEGRAL_TYPE_P (lhs_type
))
941 code
= gimple_assign_rhs_code (stmt
);
943 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
946 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
950 value
= histogram
->hvalue
.value
;
951 wrong_values
= histogram
->hvalue
.counters
[0];
952 count
= histogram
->hvalue
.counters
[1];
954 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
956 /* We require that we hit a power of 2 at least half of all evaluations. */
957 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
958 || count
< wrong_values
959 || optimize_bb_for_size_p (gimple_bb (stmt
)))
962 /* Compute probability of taking the optimal path. */
963 all
= count
+ wrong_values
;
965 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
968 if (dump_enabled_p ())
969 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
970 "Transformation done: mod power of 2\n");
973 prob
= profile_probability::probability_in_gcov_type (count
, all
);
975 prob
= profile_probability::never ();
977 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
979 gimple_assign_set_rhs_from_tree (si
, result
);
980 update_stmt (gsi_stmt (*si
));
985 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
986 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
987 supported and this is built into this interface. The probabilities of taking
988 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
989 COUNT2/ALL respectively within roundoff error). This generates the
990 result into a temp and returns the temp; it does not replace or alter
991 the original STMT. */
992 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
995 gimple_mod_subtract (gassign
*stmt
, profile_probability prob1
,
996 profile_probability prob2
, int ncounts
,
997 gcov_type count1
, gcov_type count2
, gcov_type all
)
1003 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
1004 basic_block bb
, bb2
, bb3
, bb4
;
1005 tree optype
, op1
, op2
;
1006 edge e12
, e23
= 0, e24
, e34
, e14
;
1007 gimple_stmt_iterator gsi
;
1010 gcc_assert (is_gimple_assign (stmt
)
1011 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1013 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1014 op1
= gimple_assign_rhs1 (stmt
);
1015 op2
= gimple_assign_rhs2 (stmt
);
1017 bb
= gimple_bb (stmt
);
1018 gsi
= gsi_for_stmt (stmt
);
1020 result
= create_tmp_reg (optype
, "PROF");
1021 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1022 stmt1
= gimple_build_assign (result
, op1
);
1023 stmt2
= gimple_build_assign (tmp1
, op2
);
1024 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1025 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1026 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1027 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1030 if (ncounts
) /* Assumed to be 0 or 1 */
1032 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1033 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1034 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1035 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1039 /* Fallback case. */
1040 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1042 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1046 /* Edge e23 connects bb2 to bb3, etc. */
1047 /* However block 3 is optional; if it is not there, references
1048 to 3 really refer to block 2. */
1049 e12
= split_block (bb
, bb1end
);
1051 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1053 if (ncounts
) /* Assumed to be 0 or 1. */
1055 e23
= split_block (bb2
, bb2end
);
1057 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1060 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1062 bb4
->count
= profile_count::from_gcov_type (all
);
1064 e12
->flags
&= ~EDGE_FALLTHRU
;
1065 e12
->flags
|= EDGE_FALSE_VALUE
;
1066 e12
->probability
= prob1
.invert ();
1068 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1069 e14
->probability
= prob1
;
1071 if (ncounts
) /* Assumed to be 0 or 1. */
1073 e23
->flags
&= ~EDGE_FALLTHRU
;
1074 e23
->flags
|= EDGE_FALSE_VALUE
;
1075 e23
->probability
= prob2
.invert ();
1077 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1078 e24
->probability
= prob2
;
1081 e34
->probability
= profile_probability::always ();
1086 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1089 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1091 histogram_value histogram
;
1092 enum tree_code code
;
1093 gcov_type count
, wrong_values
, all
;
1094 tree lhs_type
, result
;
1095 profile_probability prob1
, prob2
;
1096 unsigned int i
, steps
;
1097 gcov_type count1
, count2
;
1099 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1103 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1104 if (!INTEGRAL_TYPE_P (lhs_type
))
1107 code
= gimple_assign_rhs_code (stmt
);
1109 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1112 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1118 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1119 all
+= histogram
->hvalue
.counters
[i
];
1121 wrong_values
+= histogram
->hvalue
.counters
[i
];
1122 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1123 steps
= histogram
->hdata
.intvl
.steps
;
1124 all
+= wrong_values
;
1125 count1
= histogram
->hvalue
.counters
[0];
1126 count2
= histogram
->hvalue
.counters
[1];
1128 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1130 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1134 if (flag_profile_correction
&& count1
+ count2
> all
)
1135 all
= count1
+ count2
;
1137 gcc_assert (count1
+ count2
<= all
);
1139 /* We require that we use just subtractions in at least 50% of all
1142 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1144 count
+= histogram
->hvalue
.counters
[i
];
1145 if (count
* 2 >= all
)
1149 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1152 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1153 if (dump_enabled_p ())
1154 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1155 "Transformation done: mod subtract\n");
1157 /* Compute probability of taking the optimal path(s). */
1160 prob1
= profile_probability::probability_in_gcov_type (count1
, all
);
1161 prob2
= profile_probability::probability_in_gcov_type (count2
, all
);
1165 prob1
= prob2
= profile_probability::never ();
1168 /* In practice, "steps" is always 2. This interface reflects this,
1169 and will need to be changed if "steps" can change. */
1170 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1172 gimple_assign_set_rhs_from_tree (si
, result
);
1173 update_stmt (gsi_stmt (*si
));
1178 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1180 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1182 /* Returns true if node graph is initialized. This
1183 is used to test if profile_id has been created
1184 for cgraph_nodes. */
1187 coverage_node_map_initialized_p (void)
1189 return cgraph_node_map
!= 0;
1192 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1193 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1194 that the PROFILE_IDs was already assigned. */
1197 init_node_map (bool local
)
1199 struct cgraph_node
*n
;
1200 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1202 FOR_EACH_DEFINED_FUNCTION (n
)
1203 if (n
->has_gimple_body_p () || n
->thunk
.thunk_p
)
1206 dump_user_location_t loc
1207 = dump_user_location_t::from_function_decl (n
->decl
);
1210 n
->profile_id
= coverage_compute_profile_id (n
);
1211 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1214 if (dump_enabled_p ())
1215 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1216 "Local profile-id %i conflict"
1217 " with nodes %s %s\n",
1220 (*val
)->dump_name ());
1221 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1224 else if (!n
->profile_id
)
1226 if (dump_enabled_p ())
1227 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1228 "Node %s has no profile-id"
1229 " (profile feedback missing?)\n",
1233 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1235 if (dump_enabled_p ())
1236 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, loc
,
1237 "Node %s has IP profile-id %i conflict. "
1239 n
->dump_name (), n
->profile_id
);
1243 cgraph_node_map
->put (n
->profile_id
, n
);
1247 /* Delete the CGRAPH_NODE_MAP. */
1252 delete cgraph_node_map
;
1255 /* Return cgraph node for function with pid */
1258 find_func_by_profile_id (int profile_id
)
1260 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1267 /* Do transformation
1269 if (actual_callee_address == address_of_most_common_function/method)
1276 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1277 profile_probability prob
)
1282 tree tmp0
, tmp1
, tmp
;
1283 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1284 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1285 gimple_stmt_iterator gsi
;
1290 cond_bb
= gimple_bb (icall_stmt
);
1291 gsi
= gsi_for_stmt (icall_stmt
);
1293 tmp0
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1294 tmp1
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1295 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1296 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1297 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1299 tmp
= fold_convert (ptr_type_node
, build_addr (direct_call
->decl
));
1300 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1301 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1303 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1304 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1306 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1308 unlink_stmt_vdef (icall_stmt
);
1309 release_ssa_name (gimple_vdef (icall_stmt
));
1311 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1312 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1313 update_stmt (icall_stmt
);
1314 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1315 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1316 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1317 if ((dflags
& ECF_NORETURN
) != 0
1318 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1319 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1320 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1323 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1324 e_cd
= split_block (cond_bb
, cond_stmt
);
1325 dcall_bb
= e_cd
->dest
;
1326 dcall_bb
->count
= cond_bb
->count
.apply_probability (prob
);
1328 e_di
= split_block (dcall_bb
, dcall_stmt
);
1329 icall_bb
= e_di
->dest
;
1330 icall_bb
->count
= cond_bb
->count
- dcall_bb
->count
;
1332 /* Do not disturb existing EH edges from the indirect call. */
1333 if (!stmt_ends_bb_p (icall_stmt
))
1334 e_ij
= split_block (icall_bb
, icall_stmt
);
1337 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1338 /* The indirect call might be noreturn. */
1341 e_ij
->probability
= profile_probability::always ();
1342 e_ij
= single_pred_edge (split_edge (e_ij
));
1347 join_bb
= e_ij
->dest
;
1348 join_bb
->count
= cond_bb
->count
;
1351 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1352 e_cd
->probability
= prob
;
1354 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1355 e_ci
->probability
= prob
.invert ();
1361 if ((dflags
& ECF_NORETURN
) == 0)
1363 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1364 e_dj
->probability
= profile_probability::always ();
1366 e_ij
->probability
= profile_probability::always ();
1369 /* Insert PHI node for the call result if necessary. */
1370 if (gimple_call_lhs (icall_stmt
)
1371 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1372 && (dflags
& ECF_NORETURN
) == 0)
1374 tree result
= gimple_call_lhs (icall_stmt
);
1375 gphi
*phi
= create_phi_node (result
, join_bb
);
1376 gimple_call_set_lhs (icall_stmt
,
1377 duplicate_ssa_name (result
, icall_stmt
));
1378 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1379 gimple_call_set_lhs (dcall_stmt
,
1380 duplicate_ssa_name (result
, dcall_stmt
));
1381 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1384 /* Build an EH edge for the direct call if necessary. */
1385 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1386 if (lp_nr
> 0 && stmt_could_throw_p (cfun
, dcall_stmt
))
1388 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1391 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1392 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1394 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1395 e
->probability
= e_eh
->probability
;
1396 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1397 !gsi_end_p (psi
); gsi_next (&psi
))
1399 gphi
*phi
= psi
.phi ();
1400 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1401 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1404 if (!stmt_could_throw_p (cfun
, dcall_stmt
))
1405 gimple_purge_dead_eh_edges (dcall_bb
);
1409 /* Dump info about indirect call profile. */
1412 dump_ic_profile (gimple_stmt_iterator
*gsi
)
1415 histogram_value histogram
;
1416 gcov_type val
, count
, all
;
1417 struct cgraph_node
*direct_call
;
1419 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1423 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1426 if (gimple_call_internal_p (stmt
))
1429 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1434 all
= histogram
->hvalue
.counters
[0];
1436 for (unsigned j
= 0; j
< GCOV_TOPN_VALUES
; j
++)
1438 if (!get_nth_most_common_value (NULL
, "indirect call", histogram
, &val
,
1444 direct_call
= find_func_by_profile_id ((int) val
);
1446 if (direct_call
== NULL
)
1448 MSG_MISSED_OPTIMIZATION
, stmt
,
1449 "Indirect call -> direct call from other "
1450 "module %T=> %i (will resolve by ipa-profile only with LTO)\n",
1451 gimple_call_fn (stmt
), (int) val
);
1453 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1454 "Indirect call -> direct call "
1455 "%T => %T (will resolve by ipa-profile)\n",
1456 gimple_call_fn (stmt
), direct_call
->decl
);
1457 dump_printf_loc (MSG_NOTE
, stmt
,
1458 "hist->count %" PRId64
" hist->all %" PRId64
"\n",
1463 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1464 set to the argument index for the size of the string operation. */
1467 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1469 enum built_in_function fcode
;
1471 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1474 case BUILT_IN_MEMCPY
:
1475 case BUILT_IN_MEMPCPY
:
1476 case BUILT_IN_MEMMOVE
:
1478 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1479 INTEGER_TYPE
, VOID_TYPE
);
1480 case BUILT_IN_MEMSET
:
1482 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1483 INTEGER_TYPE
, VOID_TYPE
);
1484 case BUILT_IN_BZERO
:
1486 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1493 /* Convert stringop (..., vcall_size)
1495 if (vcall_size == icall_size)
1496 stringop (..., icall_size);
1498 stringop (..., vcall_size);
1499 assuming we'll propagate a true constant into ICALL_SIZE later. */
1502 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, profile_probability prob
,
1503 gcov_type count
, gcov_type all
)
1508 tree tmp0
, tmp1
, vcall_size
, optype
;
1509 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1510 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1511 gimple_stmt_iterator gsi
;
1514 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1517 cond_bb
= gimple_bb (vcall_stmt
);
1518 gsi
= gsi_for_stmt (vcall_stmt
);
1520 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1521 optype
= TREE_TYPE (vcall_size
);
1523 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1524 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1525 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1526 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1528 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1529 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1531 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1532 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1534 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1536 unlink_stmt_vdef (vcall_stmt
);
1537 release_ssa_name (gimple_vdef (vcall_stmt
));
1539 gimple_set_vdef (vcall_stmt
, NULL
);
1540 gimple_set_vuse (vcall_stmt
, NULL
);
1541 update_stmt (vcall_stmt
);
1542 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1543 gimple_call_set_arg (icall_stmt
, size_arg
,
1544 fold_convert (optype
, icall_size
));
1545 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1548 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1549 e_ci
= split_block (cond_bb
, cond_stmt
);
1550 icall_bb
= e_ci
->dest
;
1551 icall_bb
->count
= profile_count::from_gcov_type (count
);
1553 e_iv
= split_block (icall_bb
, icall_stmt
);
1554 vcall_bb
= e_iv
->dest
;
1555 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1557 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1558 join_bb
= e_vj
->dest
;
1559 join_bb
->count
= profile_count::from_gcov_type (all
);
1561 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1562 e_ci
->probability
= prob
;
1564 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1565 e_cv
->probability
= prob
.invert ();
1569 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1570 e_ij
->probability
= profile_probability::always ();
1572 e_vj
->probability
= profile_probability::always ();
1574 /* Insert PHI node for the call result if necessary. */
1575 if (gimple_call_lhs (vcall_stmt
)
1576 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1578 tree result
= gimple_call_lhs (vcall_stmt
);
1579 gphi
*phi
= create_phi_node (result
, join_bb
);
1580 gimple_call_set_lhs (vcall_stmt
,
1581 duplicate_ssa_name (result
, vcall_stmt
));
1582 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1583 gimple_call_set_lhs (icall_stmt
,
1584 duplicate_ssa_name (result
, icall_stmt
));
1585 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1588 /* Because these are all string op builtins, they're all nothrow. */
1589 gcc_assert (!stmt_could_throw_p (cfun
, vcall_stmt
));
1590 gcc_assert (!stmt_could_throw_p (cfun
, icall_stmt
));
1593 /* Find values inside STMT for that we want to measure histograms for
1594 division/modulo optimization. */
1597 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1601 enum built_in_function fcode
;
1602 histogram_value histogram
;
1603 gcov_type count
, all
, val
;
1605 unsigned int dest_align
, src_align
;
1606 profile_probability prob
;
1610 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1614 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1617 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1620 blck_size
= gimple_call_arg (stmt
, size_arg
);
1621 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1624 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
1625 HIST_TYPE_TOPN_VALUES
);
1629 if (!get_nth_most_common_value (stmt
, "stringops", histogram
, &val
, &count
,
1633 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1635 /* We require that count is at least half of all. */
1636 if (2 * count
< all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1638 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1641 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1643 prob
= profile_probability::never ();
1645 dest
= gimple_call_arg (stmt
, 0);
1646 dest_align
= get_pointer_alignment (dest
);
1647 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1650 case BUILT_IN_MEMCPY
:
1651 case BUILT_IN_MEMPCPY
:
1652 case BUILT_IN_MEMMOVE
:
1653 src
= gimple_call_arg (stmt
, 1);
1654 src_align
= get_pointer_alignment (src
);
1655 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1658 case BUILT_IN_MEMSET
:
1659 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1660 gimple_call_arg (stmt
, 1),
1664 case BUILT_IN_BZERO
:
1665 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1674 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1675 tree_val
= build_int_cst (get_gcov_type (), val
);
1679 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1680 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1682 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1683 TYPE_PRECISION (get_gcov_type ()), false));
1686 if (dump_enabled_p ())
1687 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, stmt
,
1688 "Transformation done: single value %i stringop for %s\n",
1689 (int)val
, built_in_names
[(int)fcode
]);
1691 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1697 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1698 HOST_WIDE_INT
*expected_size
)
1700 histogram_value histogram
;
1701 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1704 *expected_size
= -1;
1705 else if (!histogram
->hvalue
.counters
[1])
1707 *expected_size
= -1;
1708 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1713 size
= ((histogram
->hvalue
.counters
[0]
1714 + histogram
->hvalue
.counters
[1] / 2)
1715 / histogram
->hvalue
.counters
[1]);
1716 /* Even if we can hold bigger value in SIZE, INT_MAX
1717 is safe "infinity" for code generation strategies. */
1720 *expected_size
= size
;
1721 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1724 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1727 *expected_align
= 0;
1728 else if (!histogram
->hvalue
.counters
[0])
1730 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1731 *expected_align
= 0;
1736 unsigned int alignment
;
1738 count
= histogram
->hvalue
.counters
[0];
1740 while (!(count
& alignment
)
1741 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1743 *expected_align
= alignment
* BITS_PER_UNIT
;
1744 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1749 /* Find values inside STMT for that we want to measure histograms for
1750 division/modulo optimization. */
1753 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1755 tree lhs
, divisor
, op0
, type
;
1756 histogram_value hist
;
1758 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1761 lhs
= gimple_assign_lhs (stmt
);
1762 type
= TREE_TYPE (lhs
);
1763 if (!INTEGRAL_TYPE_P (type
))
1766 switch (gimple_assign_rhs_code (stmt
))
1768 case TRUNC_DIV_EXPR
:
1769 case TRUNC_MOD_EXPR
:
1770 divisor
= gimple_assign_rhs2 (stmt
);
1771 op0
= gimple_assign_rhs1 (stmt
);
1773 if (TREE_CODE (divisor
) == SSA_NAME
)
1774 /* Check for the case where the divisor is the same value most
1776 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1777 HIST_TYPE_TOPN_VALUES
,
1780 /* For mod, check whether it is not often a noop (or replaceable by
1781 a few subtractions). */
1782 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1783 && TYPE_UNSIGNED (type
)
1784 && TREE_CODE (divisor
) == SSA_NAME
)
1787 /* Check for a special case where the divisor is power of 2. */
1788 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1791 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1792 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1794 hist
->hdata
.intvl
.int_start
= 0;
1795 hist
->hdata
.intvl
.steps
= 2;
1796 values
->safe_push (hist
);
1805 /* Find calls inside STMT for that we want to measure histograms for
1806 indirect/virtual call optimization. */
1809 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1813 if (gimple_code (stmt
) != GIMPLE_CALL
1814 || gimple_call_internal_p (stmt
)
1815 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1818 callee
= gimple_call_fn (stmt
);
1819 histogram_value v
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1821 values
->safe_push (v
);
1826 /* Find values inside STMT for that we want to measure histograms for
1827 string operations. */
1830 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1837 stmt
= dyn_cast
<gcall
*> (gs
);
1841 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
1844 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1847 dest
= gimple_call_arg (stmt
, 0);
1848 blck_size
= gimple_call_arg (stmt
, size_arg
);
1850 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1852 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1853 HIST_TYPE_TOPN_VALUES
,
1855 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1859 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1860 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1864 /* Find values inside STMT for that we want to measure histograms and adds
1865 them to list VALUES. */
1868 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1870 gimple_divmod_values_to_profile (stmt
, values
);
1871 gimple_stringops_values_to_profile (stmt
, values
);
1872 gimple_indirect_call_to_profile (stmt
, values
);
1876 gimple_find_values_to_profile (histogram_values
*values
)
1879 gimple_stmt_iterator gsi
;
1881 histogram_value hist
= NULL
;
1884 FOR_EACH_BB_FN (bb
, cfun
)
1885 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1886 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1888 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1889 HIST_TYPE_TIME_PROFILE
));
1891 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1895 case HIST_TYPE_INTERVAL
:
1896 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1899 case HIST_TYPE_POW2
:
1900 hist
->n_counters
= 2;
1903 case HIST_TYPE_TOPN_VALUES
:
1904 case HIST_TYPE_INDIR_CALL
:
1905 hist
->n_counters
= GCOV_TOPN_VALUES_COUNTERS
;
1908 case HIST_TYPE_TIME_PROFILE
:
1909 hist
->n_counters
= 1;
1912 case HIST_TYPE_AVERAGE
:
1913 hist
->n_counters
= 2;
1917 hist
->n_counters
= 1;
1923 if (dump_file
&& hist
->hvalue
.stmt
!= NULL
)
1925 fprintf (dump_file
, "Stmt ");
1926 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1927 dump_histogram_value (dump_file
, hist
);