1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2019 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"
47 /* In this file value profile based optimizations are placed. Currently the
48 following optimizations are implemented (for more detailed descriptions
49 see comments at value_profile_transformations):
51 1) Division/modulo specialization. Provided that we can determine that the
52 operands of the division have some special properties, we may use it to
53 produce more effective code.
55 2) Indirect/virtual call specialization. If we can determine most
56 common function callee in indirect/virtual call. We can use this
57 information to improve code effectiveness (especially info for
60 3) Speculative prefetching. If we are able to determine that the difference
61 between addresses accessed by a memory reference is usually constant, we
62 may add the prefetch instructions.
63 FIXME: This transformation was removed together with RTL based value
67 Value profiling internals
68 ==========================
70 Every value profiling transformation starts with defining what values
71 to profile. There are different histogram types (see HIST_TYPE_* in
72 value-prof.h) and each transformation can request one or more histogram
73 types per GIMPLE statement. The function gimple_find_values_to_profile()
74 collects the values to profile in a vec, and adds the number of counters
75 required for the different histogram types.
77 For a -fprofile-generate run, the statements for which values should be
78 recorded, are instrumented in instrument_values(). The instrumentation
79 is done by helper functions that can be found in tree-profile.c, where
80 new types of histograms can be added if necessary.
82 After a -fprofile-use, the value profiling data is read back in by
83 compute_value_histograms() that translates the collected data to
84 histograms and attaches them to the profiled statements via
85 gimple_add_histogram_value(). Histograms are stored in a hash table
86 that is attached to every intrumented function, see VALUE_HISTOGRAMS
89 The value-profile transformations driver is the function
90 gimple_value_profile_transformations(). It traverses all statements in
91 the to-be-transformed function, and looks for statements with one or
92 more histograms attached to it. If a statement has histograms, the
93 transformation functions are called on the statement.
95 Limitations / FIXME / TODO:
96 * Only one histogram of each type can be associated with a statement.
97 * Some value profile transformations are done in builtins.c (?!)
98 * Updating of histograms needs some TLC.
99 * The value profiling code could be used to record analysis results
100 from non-profiling (e.g. VRP).
101 * Adding new profilers should be simplified, starting with a cleanup
102 of what-happens-where and with making gimple_find_values_to_profile
103 and gimple_value_profile_transformations table-driven, perhaps...
106 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
107 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
108 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
109 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
110 static bool gimple_ic_transform (gimple_stmt_iterator
*);
112 /* Allocate histogram value. */
115 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
116 enum hist_type type
, gimple
*stmt
, tree value
)
118 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
119 hist
->hvalue
.value
= value
;
120 hist
->hvalue
.stmt
= stmt
;
125 /* Hash value for histogram. */
128 histogram_hash (const void *x
)
130 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
133 /* Return nonzero if statement for histogram_value X is Y. */
136 histogram_eq (const void *x
, const void *y
)
138 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const gimple
*) y
;
141 /* Set histogram for STMT. */
144 set_histogram_value (struct function
*fun
, gimple
*stmt
, histogram_value hist
)
147 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
149 if (!VALUE_HISTOGRAMS (fun
))
150 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
152 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
153 htab_hash_pointer (stmt
),
154 hist
? INSERT
: NO_INSERT
);
158 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
164 /* Get histogram list for STMT. */
167 gimple_histogram_value (struct function
*fun
, gimple
*stmt
)
169 if (!VALUE_HISTOGRAMS (fun
))
171 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
172 htab_hash_pointer (stmt
));
175 /* Add histogram for STMT. */
178 gimple_add_histogram_value (struct function
*fun
, gimple
*stmt
,
179 histogram_value hist
)
181 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
182 set_histogram_value (fun
, stmt
, hist
);
186 /* Remove histogram HIST from STMT's histogram list. */
189 gimple_remove_histogram_value (struct function
*fun
, gimple
*stmt
,
190 histogram_value hist
)
192 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
195 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
199 while (hist2
->hvalue
.next
!= hist
)
200 hist2
= hist2
->hvalue
.next
;
201 hist2
->hvalue
.next
= hist
->hvalue
.next
;
203 free (hist
->hvalue
.counters
);
205 memset (hist
, 0xab, sizeof (*hist
));
209 /* Lookup histogram of type TYPE in the STMT. */
212 gimple_histogram_value_of_type (struct function
*fun
, gimple
*stmt
,
215 histogram_value hist
;
216 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
217 hist
= hist
->hvalue
.next
)
218 if (hist
->type
== type
)
223 /* Dump information about HIST to DUMP_FILE. */
226 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
230 case HIST_TYPE_INTERVAL
:
231 if (hist
->hvalue
.counters
)
233 fprintf (dump_file
, "Interval counter range [%d,%d]: [",
234 hist
->hdata
.intvl
.int_start
,
235 (hist
->hdata
.intvl
.int_start
236 + hist
->hdata
.intvl
.steps
- 1));
239 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
241 fprintf (dump_file
, "%d:%" PRId64
,
242 hist
->hdata
.intvl
.int_start
+ i
,
243 (int64_t) hist
->hvalue
.counters
[i
]);
244 if (i
!= hist
->hdata
.intvl
.steps
- 1)
245 fprintf (dump_file
, ", ");
247 fprintf (dump_file
, "] outside range: %" PRId64
".\n",
248 (int64_t) hist
->hvalue
.counters
[i
]);
253 if (hist
->hvalue
.counters
)
254 fprintf (dump_file
, "Pow2 counter pow2:%" PRId64
255 " nonpow2:%" PRId64
".\n",
256 (int64_t) hist
->hvalue
.counters
[1],
257 (int64_t) hist
->hvalue
.counters
[0]);
260 case HIST_TYPE_TOPN_VALUES
:
261 case HIST_TYPE_INDIR_CALL
:
262 if (hist
->hvalue
.counters
)
265 (hist
->type
== HIST_TYPE_TOPN_VALUES
266 ? "Top N value counter " : "Indirect call counter"));
267 if (hist
->hvalue
.counters
)
269 fprintf (dump_file
, "all: %" PRId64
", values: ",
270 (int64_t) hist
->hvalue
.counters
[0]);
271 for (unsigned i
= 0; i
< GCOV_TOPN_VALUES
; i
++)
273 fprintf (dump_file
, "[%" PRId64
":%" PRId64
"]",
274 (int64_t) hist
->hvalue
.counters
[2 * i
+ 1],
275 (int64_t) hist
->hvalue
.counters
[2 * i
+ 2]);
276 if (i
!= GCOV_TOPN_VALUES
- 1)
277 fprintf (dump_file
, ", ");
279 fprintf (dump_file
, ".\n");
284 case HIST_TYPE_AVERAGE
:
285 if (hist
->hvalue
.counters
)
286 fprintf (dump_file
, "Average value sum:%" PRId64
287 " times:%" PRId64
".\n",
288 (int64_t) hist
->hvalue
.counters
[0],
289 (int64_t) hist
->hvalue
.counters
[1]);
293 if (hist
->hvalue
.counters
)
294 fprintf (dump_file
, "IOR value ior:%" PRId64
".\n",
295 (int64_t) hist
->hvalue
.counters
[0]);
298 case HIST_TYPE_TIME_PROFILE
:
299 if (hist
->hvalue
.counters
)
300 fprintf (dump_file
, "Time profile time:%" PRId64
".\n",
301 (int64_t) hist
->hvalue
.counters
[0]);
308 /* Dump information about HIST to DUMP_FILE. */
311 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
316 bp
= bitpack_create (ob
->main_stream
);
317 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
318 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
319 streamer_write_bitpack (&bp
);
322 case HIST_TYPE_INTERVAL
:
323 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
324 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
329 for (i
= 0; i
< hist
->n_counters
; i
++)
331 /* When user uses an unsigned type with a big value, constant converted
332 to gcov_type (a signed type) can be negative. */
333 gcov_type value
= hist
->hvalue
.counters
[i
];
334 if (hist
->type
== HIST_TYPE_TOPN_VALUES
&& i
> 0)
337 gcc_assert (value
>= 0);
339 streamer_write_gcov_count (ob
, value
);
341 if (hist
->hvalue
.next
)
342 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
345 /* Dump information about HIST to DUMP_FILE. */
348 stream_in_histogram_value (class lto_input_block
*ib
, gimple
*stmt
)
351 unsigned int ncounters
= 0;
354 histogram_value new_val
;
356 histogram_value
*next_p
= NULL
;
360 bp
= streamer_read_bitpack (ib
);
361 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
362 next
= bp_unpack_value (&bp
, 1);
363 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
366 case HIST_TYPE_INTERVAL
:
367 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
368 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
369 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
373 case HIST_TYPE_AVERAGE
:
377 case HIST_TYPE_TOPN_VALUES
:
378 case HIST_TYPE_INDIR_CALL
:
379 ncounters
= GCOV_TOPN_VALUES_COUNTERS
;
383 case HIST_TYPE_TIME_PROFILE
:
390 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
391 new_val
->n_counters
= ncounters
;
392 for (i
= 0; i
< ncounters
; i
++)
393 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
395 gimple_add_histogram_value (cfun
, stmt
, new_val
);
398 next_p
= &new_val
->hvalue
.next
;
403 /* Dump all histograms attached to STMT to DUMP_FILE. */
406 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
408 histogram_value hist
;
409 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
410 dump_histogram_value (dump_file
, hist
);
413 /* Remove all histograms associated with STMT. */
416 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
419 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
420 gimple_remove_histogram_value (fun
, stmt
, val
);
423 /* Duplicate all histograms associates with OSTMT to STMT. */
426 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
427 struct function
*ofun
, gimple
*ostmt
)
430 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
432 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
433 memcpy (new_val
, val
, sizeof (*val
));
434 new_val
->hvalue
.stmt
= stmt
;
435 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
436 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
437 gimple_add_histogram_value (fun
, stmt
, new_val
);
441 /* Move all histograms associated with OSTMT to STMT. */
444 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
446 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
449 /* The following three statements can't be reordered,
450 because histogram hashtab relies on stmt field value
451 for finding the exact slot. */
452 set_histogram_value (fun
, ostmt
, NULL
);
453 for (; val
!= NULL
; val
= val
->hvalue
.next
)
454 val
->hvalue
.stmt
= stmt
;
455 set_histogram_value (fun
, stmt
, val
);
459 static bool error_found
= false;
461 /* Helper function for verify_histograms. For each histogram reachable via htab
462 walk verify that it was reached via statement walk. */
465 visit_hist (void **slot
, void *data
)
467 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
468 histogram_value hist
= *(histogram_value
*) slot
;
470 if (!visited
->contains (hist
)
471 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
473 error ("dead histogram");
474 dump_histogram_value (stderr
, hist
);
475 debug_gimple_stmt (hist
->hvalue
.stmt
);
481 /* Verify sanity of the histograms. */
484 verify_histograms (void)
487 gimple_stmt_iterator gsi
;
488 histogram_value hist
;
491 hash_set
<histogram_value
> visited_hists
;
492 FOR_EACH_BB_FN (bb
, cfun
)
493 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
495 gimple
*stmt
= gsi_stmt (gsi
);
497 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
498 hist
= hist
->hvalue
.next
)
500 if (hist
->hvalue
.stmt
!= stmt
)
502 error ("histogram value statement does not correspond to "
503 "the statement it is associated with");
504 debug_gimple_stmt (stmt
);
505 dump_histogram_value (stderr
, hist
);
508 visited_hists
.add (hist
);
511 if (VALUE_HISTOGRAMS (cfun
))
512 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
514 internal_error ("%qs failed", __func__
);
517 /* Helper function for verify_histograms. For each histogram reachable via htab
518 walk verify that it was reached via statement walk. */
521 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
523 histogram_value hist
= *(histogram_value
*) slot
;
524 free (hist
->hvalue
.counters
);
530 free_histograms (struct function
*fn
)
532 if (VALUE_HISTOGRAMS (fn
))
534 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
535 htab_delete (VALUE_HISTOGRAMS (fn
));
536 VALUE_HISTOGRAMS (fn
) = NULL
;
540 /* The overall number of invocations of the counter should match
541 execution count of basic block. Report it as error rather than
542 internal error as it might mean that user has misused the profile
546 check_counter (gimple
*stmt
, const char * name
,
547 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
549 gcov_type bb_count
= bb_count_d
.ipa ().to_gcov_type ();
550 if (*all
!= bb_count
|| *count
> *all
)
552 dump_user_location_t locus
;
553 locus
= ((stmt
!= NULL
)
554 ? dump_user_location_t (stmt
)
555 : dump_user_location_t::from_function_decl
556 (current_function_decl
));
557 if (flag_profile_correction
)
559 if (dump_enabled_p ())
560 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
561 "correcting inconsistent value profile: %s "
562 "profiler overall count (%d) does not match BB "
563 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
571 error_at (locus
.get_location_t (), "corrupted value profile: %s "
572 "profile counter (%d out of %d) inconsistent with "
573 "basic-block count (%d)",
585 /* GIMPLE based transformations. */
588 gimple_value_profile_transformations (void)
591 gimple_stmt_iterator gsi
;
592 bool changed
= false;
594 FOR_EACH_BB_FN (bb
, cfun
)
596 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
598 gimple
*stmt
= gsi_stmt (gsi
);
599 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
605 fprintf (dump_file
, "Trying transformations on stmt ");
606 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
607 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
610 /* Transformations: */
611 /* The order of things in this conditional controls which
612 transformation is used when more than one is applicable. */
613 /* It is expected that any code added by the transformations
614 will be added before the current statement, and that the
615 current statement remain valid (although possibly
616 modified) upon return. */
617 if (gimple_mod_subtract_transform (&gsi
)
618 || gimple_divmod_fixed_value_transform (&gsi
)
619 || gimple_mod_pow2_value_transform (&gsi
)
620 || gimple_stringops_transform (&gsi
)
621 || gimple_ic_transform (&gsi
))
623 stmt
= gsi_stmt (gsi
);
625 /* Original statement may no longer be in the same block. */
626 if (bb
!= gimple_bb (stmt
))
628 bb
= gimple_bb (stmt
);
629 gsi
= gsi_for_stmt (stmt
);
638 /* Generate code for transformation 1 (with parent gimple assignment
639 STMT and probability of taking the optimal path PROB, which is
640 equivalent to COUNT/ALL within roundoff error). This generates the
641 result into a temp and returns the temp; it does not replace or
642 alter the original STMT. */
645 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, profile_probability prob
,
646 gcov_type count
, gcov_type all
)
648 gassign
*stmt1
, *stmt2
;
650 tree tmp0
, tmp1
, tmp2
;
651 gimple
*bb1end
, *bb2end
, *bb3end
;
652 basic_block bb
, bb2
, bb3
, bb4
;
653 tree optype
, op1
, op2
;
654 edge e12
, e13
, e23
, e24
, e34
;
655 gimple_stmt_iterator gsi
;
657 gcc_assert (is_gimple_assign (stmt
)
658 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
659 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
661 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
662 op1
= gimple_assign_rhs1 (stmt
);
663 op2
= gimple_assign_rhs2 (stmt
);
665 bb
= gimple_bb (stmt
);
666 gsi
= gsi_for_stmt (stmt
);
668 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
669 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
670 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
671 stmt2
= gimple_build_assign (tmp1
, op2
);
672 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
673 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
674 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
675 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
678 tmp2
= create_tmp_reg (optype
, "PROF");
679 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
680 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
683 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
684 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
688 /* Edge e23 connects bb2 to bb3, etc. */
689 e12
= split_block (bb
, bb1end
);
691 bb2
->count
= profile_count::from_gcov_type (count
);
692 e23
= split_block (bb2
, bb2end
);
694 bb3
->count
= profile_count::from_gcov_type (all
- count
);
695 e34
= split_block (bb3
, bb3end
);
697 bb4
->count
= profile_count::from_gcov_type (all
);
699 e12
->flags
&= ~EDGE_FALLTHRU
;
700 e12
->flags
|= EDGE_FALSE_VALUE
;
701 e12
->probability
= prob
;
703 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
704 e13
->probability
= prob
.invert ();
708 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
709 e24
->probability
= profile_probability::always ();
711 e34
->probability
= profile_probability::always ();
716 /* Return the n-th value count of TOPN_VALUE histogram. If
717 there's a value, return true and set VALUE and COUNT
721 get_nth_most_common_value (gimple
*stmt
, const char *counter_type
,
722 histogram_value hist
, gcov_type
*value
,
723 gcov_type
*count
, gcov_type
*all
, unsigned n
)
725 if (hist
->hvalue
.counters
[2] == -1)
728 gcc_assert (n
< GCOV_TOPN_VALUES
);
733 gcov_type read_all
= hist
->hvalue
.counters
[0];
735 gcov_type v
= hist
->hvalue
.counters
[2 * n
+ 1];
736 gcov_type c
= hist
->hvalue
.counters
[2 * n
+ 2];
738 /* Indirect calls can't be verified. */
740 && check_counter (stmt
, counter_type
, &c
, &read_all
,
741 gimple_bb (stmt
)->count
))
751 /* Do transform 1) on INSN if applicable. */
754 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
756 histogram_value histogram
;
758 gcov_type val
, count
, all
;
759 tree result
, value
, tree_val
;
760 profile_probability prob
;
763 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
767 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
770 code
= gimple_assign_rhs_code (stmt
);
772 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
775 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
776 HIST_TYPE_TOPN_VALUES
);
780 if (!get_nth_most_common_value (stmt
, "divmod", histogram
, &val
, &count
,
784 value
= histogram
->hvalue
.value
;
785 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
787 /* We require that count is at least half of all. */
788 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
790 || optimize_bb_for_size_p (gimple_bb (stmt
)))
793 /* Compute probability of taking the optimal path. */
795 prob
= profile_probability::probability_in_gcov_type (count
, all
);
797 prob
= profile_probability::never ();
799 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
800 tree_val
= build_int_cst (get_gcov_type (), val
);
804 a
[0] = (unsigned HOST_WIDE_INT
) val
;
805 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
807 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
808 TYPE_PRECISION (get_gcov_type ()), false));
810 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
814 fprintf (dump_file
, "Transformation done: div/mod by constant ");
815 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
816 fprintf (dump_file
, "\n");
819 gimple_assign_set_rhs_from_tree (si
, result
);
820 update_stmt (gsi_stmt (*si
));
825 /* Generate code for transformation 2 (with parent gimple assign STMT and
826 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
827 within roundoff error). This generates the result into a temp and returns
828 the temp; it does not replace or alter the original STMT. */
831 gimple_mod_pow2 (gassign
*stmt
, profile_probability prob
, gcov_type count
, gcov_type all
)
833 gassign
*stmt1
, *stmt2
, *stmt3
;
836 gimple
*bb1end
, *bb2end
, *bb3end
;
837 basic_block bb
, bb2
, bb3
, bb4
;
838 tree optype
, op1
, op2
;
839 edge e12
, e13
, e23
, e24
, e34
;
840 gimple_stmt_iterator gsi
;
843 gcc_assert (is_gimple_assign (stmt
)
844 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
846 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
847 op1
= gimple_assign_rhs1 (stmt
);
848 op2
= gimple_assign_rhs2 (stmt
);
850 bb
= gimple_bb (stmt
);
851 gsi
= gsi_for_stmt (stmt
);
853 result
= create_tmp_reg (optype
, "PROF");
854 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
855 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
856 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
857 build_int_cst (optype
, -1));
858 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
859 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
860 NULL_TREE
, NULL_TREE
);
861 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
862 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
863 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
866 /* tmp2 == op2-1 inherited from previous block. */
867 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
868 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
871 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
873 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
877 /* Edge e23 connects bb2 to bb3, etc. */
878 e12
= split_block (bb
, bb1end
);
880 bb2
->count
= profile_count::from_gcov_type (count
);
881 e23
= split_block (bb2
, bb2end
);
883 bb3
->count
= profile_count::from_gcov_type (all
- count
);
884 e34
= split_block (bb3
, bb3end
);
886 bb4
->count
= profile_count::from_gcov_type (all
);
888 e12
->flags
&= ~EDGE_FALLTHRU
;
889 e12
->flags
|= EDGE_FALSE_VALUE
;
890 e12
->probability
= prob
;
892 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
893 e13
->probability
= prob
.invert ();
897 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
898 e24
->probability
= profile_probability::always ();
900 e34
->probability
= profile_probability::always ();
905 /* Do transform 2) on INSN if applicable. */
908 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
910 histogram_value histogram
;
912 gcov_type count
, wrong_values
, all
;
913 tree lhs_type
, result
, value
;
914 profile_probability prob
;
917 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
921 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
922 if (!INTEGRAL_TYPE_P (lhs_type
))
925 code
= gimple_assign_rhs_code (stmt
);
927 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
930 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
934 value
= histogram
->hvalue
.value
;
935 wrong_values
= histogram
->hvalue
.counters
[0];
936 count
= histogram
->hvalue
.counters
[1];
938 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
940 /* We require that we hit a power of 2 at least half of all evaluations. */
941 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
942 || count
< wrong_values
943 || optimize_bb_for_size_p (gimple_bb (stmt
)))
946 /* Compute probability of taking the optimal path. */
947 all
= count
+ wrong_values
;
949 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
953 fprintf (dump_file
, "Transformation done: mod power of 2\n");
956 prob
= profile_probability::probability_in_gcov_type (count
, all
);
958 prob
= profile_probability::never ();
960 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
962 gimple_assign_set_rhs_from_tree (si
, result
);
963 update_stmt (gsi_stmt (*si
));
968 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
969 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
970 supported and this is built into this interface. The probabilities of taking
971 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
972 COUNT2/ALL respectively within roundoff error). This generates the
973 result into a temp and returns the temp; it does not replace or alter
974 the original STMT. */
975 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
978 gimple_mod_subtract (gassign
*stmt
, profile_probability prob1
,
979 profile_probability prob2
, int ncounts
,
980 gcov_type count1
, gcov_type count2
, gcov_type all
)
986 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
987 basic_block bb
, bb2
, bb3
, bb4
;
988 tree optype
, op1
, op2
;
989 edge e12
, e23
= 0, e24
, e34
, e14
;
990 gimple_stmt_iterator gsi
;
993 gcc_assert (is_gimple_assign (stmt
)
994 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
996 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
997 op1
= gimple_assign_rhs1 (stmt
);
998 op2
= gimple_assign_rhs2 (stmt
);
1000 bb
= gimple_bb (stmt
);
1001 gsi
= gsi_for_stmt (stmt
);
1003 result
= create_tmp_reg (optype
, "PROF");
1004 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1005 stmt1
= gimple_build_assign (result
, op1
);
1006 stmt2
= gimple_build_assign (tmp1
, op2
);
1007 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1008 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1009 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1010 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1013 if (ncounts
) /* Assumed to be 0 or 1 */
1015 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1016 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1017 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1018 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1022 /* Fallback case. */
1023 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1025 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1029 /* Edge e23 connects bb2 to bb3, etc. */
1030 /* However block 3 is optional; if it is not there, references
1031 to 3 really refer to block 2. */
1032 e12
= split_block (bb
, bb1end
);
1034 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1036 if (ncounts
) /* Assumed to be 0 or 1. */
1038 e23
= split_block (bb2
, bb2end
);
1040 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1043 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1045 bb4
->count
= profile_count::from_gcov_type (all
);
1047 e12
->flags
&= ~EDGE_FALLTHRU
;
1048 e12
->flags
|= EDGE_FALSE_VALUE
;
1049 e12
->probability
= prob1
.invert ();
1051 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1052 e14
->probability
= prob1
;
1054 if (ncounts
) /* Assumed to be 0 or 1. */
1056 e23
->flags
&= ~EDGE_FALLTHRU
;
1057 e23
->flags
|= EDGE_FALSE_VALUE
;
1058 e23
->probability
= prob2
.invert ();
1060 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1061 e24
->probability
= prob2
;
1064 e34
->probability
= profile_probability::always ();
1069 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1072 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1074 histogram_value histogram
;
1075 enum tree_code code
;
1076 gcov_type count
, wrong_values
, all
;
1077 tree lhs_type
, result
;
1078 profile_probability prob1
, prob2
;
1079 unsigned int i
, steps
;
1080 gcov_type count1
, count2
;
1082 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1086 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1087 if (!INTEGRAL_TYPE_P (lhs_type
))
1090 code
= gimple_assign_rhs_code (stmt
);
1092 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1095 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1101 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1102 all
+= histogram
->hvalue
.counters
[i
];
1104 wrong_values
+= histogram
->hvalue
.counters
[i
];
1105 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1106 steps
= histogram
->hdata
.intvl
.steps
;
1107 all
+= wrong_values
;
1108 count1
= histogram
->hvalue
.counters
[0];
1109 count2
= histogram
->hvalue
.counters
[1];
1111 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1113 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1117 if (flag_profile_correction
&& count1
+ count2
> all
)
1118 all
= count1
+ count2
;
1120 gcc_assert (count1
+ count2
<= all
);
1122 /* We require that we use just subtractions in at least 50% of all
1125 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1127 count
+= histogram
->hvalue
.counters
[i
];
1128 if (count
* 2 >= all
)
1132 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1135 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1137 fprintf (dump_file
, "Transformation done: mod subtract\n");
1139 /* Compute probability of taking the optimal path(s). */
1142 prob1
= profile_probability::probability_in_gcov_type (count1
, all
);
1143 prob2
= profile_probability::probability_in_gcov_type (count2
, all
);
1147 prob1
= prob2
= profile_probability::never ();
1150 /* In practice, "steps" is always 2. This interface reflects this,
1151 and will need to be changed if "steps" can change. */
1152 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1154 gimple_assign_set_rhs_from_tree (si
, result
);
1155 update_stmt (gsi_stmt (*si
));
1160 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1162 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1164 /* Returns true if node graph is initialized. This
1165 is used to test if profile_id has been created
1166 for cgraph_nodes. */
1169 coverage_node_map_initialized_p (void)
1171 return cgraph_node_map
!= 0;
1174 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1175 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1176 that the PROFILE_IDs was already assigned. */
1179 init_node_map (bool local
)
1181 struct cgraph_node
*n
;
1182 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1184 FOR_EACH_DEFINED_FUNCTION (n
)
1185 if (n
->has_gimple_body_p () || n
->thunk
.thunk_p
)
1190 n
->profile_id
= coverage_compute_profile_id (n
);
1191 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1195 fprintf (dump_file
, "Local profile-id %i conflict"
1196 " with nodes %s %s\n",
1199 (*val
)->dump_name ());
1200 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1203 else if (!n
->profile_id
)
1207 "Node %s has no profile-id"
1208 " (profile feedback missing?)\n",
1212 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1216 "Node %s has IP profile-id %i conflict. "
1218 n
->dump_name (), n
->profile_id
);
1222 cgraph_node_map
->put (n
->profile_id
, n
);
1226 /* Delete the CGRAPH_NODE_MAP. */
1231 delete cgraph_node_map
;
1234 /* Return cgraph node for function with pid */
1237 find_func_by_profile_id (int profile_id
)
1239 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1246 /* Perform sanity check on the indirect call target. Due to race conditions,
1247 false function target may be attributed to an indirect call site. If the
1248 call expression type mismatches with the target function's type, expand_call
1249 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1250 Returns true if TARGET is considered ok for call CALL_STMT. */
1253 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1255 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1258 if (dump_enabled_p ())
1259 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, call_stmt
,
1260 "Skipping target %s with mismatching types for icall\n",
1265 /* Do transformation
1267 if (actual_callee_address == address_of_most_common_function/method)
1274 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1275 profile_probability prob
)
1280 tree tmp0
, tmp1
, tmp
;
1281 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1282 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1283 gimple_stmt_iterator gsi
;
1288 cond_bb
= gimple_bb (icall_stmt
);
1289 gsi
= gsi_for_stmt (icall_stmt
);
1291 tmp0
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1292 tmp1
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1293 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1294 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1295 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1297 tmp
= fold_convert (ptr_type_node
, build_addr (direct_call
->decl
));
1298 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1299 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1301 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1302 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1304 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1306 unlink_stmt_vdef (icall_stmt
);
1307 release_ssa_name (gimple_vdef (icall_stmt
));
1309 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1310 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1311 update_stmt (icall_stmt
);
1312 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1313 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1314 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1315 if ((dflags
& ECF_NORETURN
) != 0
1316 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1317 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1318 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1321 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1322 e_cd
= split_block (cond_bb
, cond_stmt
);
1323 dcall_bb
= e_cd
->dest
;
1324 dcall_bb
->count
= cond_bb
->count
.apply_probability (prob
);
1326 e_di
= split_block (dcall_bb
, dcall_stmt
);
1327 icall_bb
= e_di
->dest
;
1328 icall_bb
->count
= cond_bb
->count
- dcall_bb
->count
;
1330 /* Do not disturb existing EH edges from the indirect call. */
1331 if (!stmt_ends_bb_p (icall_stmt
))
1332 e_ij
= split_block (icall_bb
, icall_stmt
);
1335 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1336 /* The indirect call might be noreturn. */
1339 e_ij
->probability
= profile_probability::always ();
1340 e_ij
= single_pred_edge (split_edge (e_ij
));
1345 join_bb
= e_ij
->dest
;
1346 join_bb
->count
= cond_bb
->count
;
1349 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1350 e_cd
->probability
= prob
;
1352 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1353 e_ci
->probability
= prob
.invert ();
1359 if ((dflags
& ECF_NORETURN
) == 0)
1361 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1362 e_dj
->probability
= profile_probability::always ();
1364 e_ij
->probability
= profile_probability::always ();
1367 /* Insert PHI node for the call result if necessary. */
1368 if (gimple_call_lhs (icall_stmt
)
1369 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1370 && (dflags
& ECF_NORETURN
) == 0)
1372 tree result
= gimple_call_lhs (icall_stmt
);
1373 gphi
*phi
= create_phi_node (result
, join_bb
);
1374 gimple_call_set_lhs (icall_stmt
,
1375 duplicate_ssa_name (result
, icall_stmt
));
1376 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1377 gimple_call_set_lhs (dcall_stmt
,
1378 duplicate_ssa_name (result
, dcall_stmt
));
1379 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1382 /* Build an EH edge for the direct call if necessary. */
1383 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1384 if (lp_nr
> 0 && stmt_could_throw_p (cfun
, dcall_stmt
))
1386 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1389 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1390 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1392 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1393 e
->probability
= e_eh
->probability
;
1394 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1395 !gsi_end_p (psi
); gsi_next (&psi
))
1397 gphi
*phi
= psi
.phi ();
1398 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1399 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1402 if (!stmt_could_throw_p (cfun
, dcall_stmt
))
1403 gimple_purge_dead_eh_edges (dcall_bb
);
1408 For every checked indirect/virtual call determine if most common pid of
1409 function/class method has probability more than 50%. If yes modify code of
1414 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1417 histogram_value histogram
;
1418 gcov_type val
, count
, all
;
1419 struct cgraph_node
*direct_call
;
1421 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1425 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1428 if (gimple_call_internal_p (stmt
))
1431 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1435 if (!get_nth_most_common_value (NULL
, "indirect call", histogram
, &val
,
1439 if (4 * count
<= 3 * all
)
1442 direct_call
= find_func_by_profile_id ((int)val
);
1444 if (direct_call
== NULL
)
1450 fprintf (dump_file
, "Indirect call -> direct call from other module");
1451 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1452 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1458 if (!check_ic_target (stmt
, direct_call
))
1462 fprintf (dump_file
, "Indirect call -> direct call ");
1463 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1464 fprintf (dump_file
, "=> ");
1465 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1466 fprintf (dump_file
, " transformation skipped because of type mismatch");
1467 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1469 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1475 fprintf (dump_file
, "Indirect call -> direct call ");
1476 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1477 fprintf (dump_file
, "=> ");
1478 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1479 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1480 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1481 fprintf (dump_file
, "hist->count %" PRId64
1482 " hist->all %" PRId64
"\n", count
, all
);
1488 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1489 set to the argument index for the size of the string operation. */
1492 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1494 enum built_in_function fcode
;
1496 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1499 case BUILT_IN_MEMCPY
:
1500 case BUILT_IN_MEMPCPY
:
1501 case BUILT_IN_MEMMOVE
:
1503 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1504 INTEGER_TYPE
, VOID_TYPE
);
1505 case BUILT_IN_MEMSET
:
1507 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1508 INTEGER_TYPE
, VOID_TYPE
);
1509 case BUILT_IN_BZERO
:
1511 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1518 /* Convert stringop (..., vcall_size)
1520 if (vcall_size == icall_size)
1521 stringop (..., icall_size);
1523 stringop (..., vcall_size);
1524 assuming we'll propagate a true constant into ICALL_SIZE later. */
1527 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, profile_probability prob
,
1528 gcov_type count
, gcov_type all
)
1533 tree tmp0
, tmp1
, vcall_size
, optype
;
1534 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1535 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1536 gimple_stmt_iterator gsi
;
1539 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1542 cond_bb
= gimple_bb (vcall_stmt
);
1543 gsi
= gsi_for_stmt (vcall_stmt
);
1545 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1546 optype
= TREE_TYPE (vcall_size
);
1548 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1549 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1550 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1551 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1553 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1554 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1556 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1557 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1559 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1561 unlink_stmt_vdef (vcall_stmt
);
1562 release_ssa_name (gimple_vdef (vcall_stmt
));
1564 gimple_set_vdef (vcall_stmt
, NULL
);
1565 gimple_set_vuse (vcall_stmt
, NULL
);
1566 update_stmt (vcall_stmt
);
1567 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1568 gimple_call_set_arg (icall_stmt
, size_arg
,
1569 fold_convert (optype
, icall_size
));
1570 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1573 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1574 e_ci
= split_block (cond_bb
, cond_stmt
);
1575 icall_bb
= e_ci
->dest
;
1576 icall_bb
->count
= profile_count::from_gcov_type (count
);
1578 e_iv
= split_block (icall_bb
, icall_stmt
);
1579 vcall_bb
= e_iv
->dest
;
1580 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1582 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1583 join_bb
= e_vj
->dest
;
1584 join_bb
->count
= profile_count::from_gcov_type (all
);
1586 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1587 e_ci
->probability
= prob
;
1589 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1590 e_cv
->probability
= prob
.invert ();
1594 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1595 e_ij
->probability
= profile_probability::always ();
1597 e_vj
->probability
= profile_probability::always ();
1599 /* Insert PHI node for the call result if necessary. */
1600 if (gimple_call_lhs (vcall_stmt
)
1601 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1603 tree result
= gimple_call_lhs (vcall_stmt
);
1604 gphi
*phi
= create_phi_node (result
, join_bb
);
1605 gimple_call_set_lhs (vcall_stmt
,
1606 duplicate_ssa_name (result
, vcall_stmt
));
1607 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1608 gimple_call_set_lhs (icall_stmt
,
1609 duplicate_ssa_name (result
, icall_stmt
));
1610 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1613 /* Because these are all string op builtins, they're all nothrow. */
1614 gcc_assert (!stmt_could_throw_p (cfun
, vcall_stmt
));
1615 gcc_assert (!stmt_could_throw_p (cfun
, icall_stmt
));
1618 /* Find values inside STMT for that we want to measure histograms for
1619 division/modulo optimization. */
1622 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1626 enum built_in_function fcode
;
1627 histogram_value histogram
;
1628 gcov_type count
, all
, val
;
1630 unsigned int dest_align
, src_align
;
1631 profile_probability prob
;
1635 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1639 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1642 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1645 blck_size
= gimple_call_arg (stmt
, size_arg
);
1646 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1649 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
1650 HIST_TYPE_TOPN_VALUES
);
1654 if (!get_nth_most_common_value (stmt
, "stringops", histogram
, &val
, &count
,
1658 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1660 /* We require that count is at least half of all. */
1661 if (2 * count
< all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1663 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1666 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1668 prob
= profile_probability::never ();
1670 dest
= gimple_call_arg (stmt
, 0);
1671 dest_align
= get_pointer_alignment (dest
);
1672 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1675 case BUILT_IN_MEMCPY
:
1676 case BUILT_IN_MEMPCPY
:
1677 case BUILT_IN_MEMMOVE
:
1678 src
= gimple_call_arg (stmt
, 1);
1679 src_align
= get_pointer_alignment (src
);
1680 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1683 case BUILT_IN_MEMSET
:
1684 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1685 gimple_call_arg (stmt
, 1),
1689 case BUILT_IN_BZERO
:
1690 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1699 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1700 tree_val
= build_int_cst (get_gcov_type (), val
);
1704 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1705 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1707 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1708 TYPE_PRECISION (get_gcov_type ()), false));
1713 "Transformation done: single value %i stringop for %s\n",
1714 (int)val
, built_in_names
[(int)fcode
]);
1716 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1722 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1723 HOST_WIDE_INT
*expected_size
)
1725 histogram_value histogram
;
1726 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1729 *expected_size
= -1;
1730 else if (!histogram
->hvalue
.counters
[1])
1732 *expected_size
= -1;
1733 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1738 size
= ((histogram
->hvalue
.counters
[0]
1739 + histogram
->hvalue
.counters
[1] / 2)
1740 / histogram
->hvalue
.counters
[1]);
1741 /* Even if we can hold bigger value in SIZE, INT_MAX
1742 is safe "infinity" for code generation strategies. */
1745 *expected_size
= size
;
1746 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1749 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1752 *expected_align
= 0;
1753 else if (!histogram
->hvalue
.counters
[0])
1755 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1756 *expected_align
= 0;
1761 unsigned int alignment
;
1763 count
= histogram
->hvalue
.counters
[0];
1765 while (!(count
& alignment
)
1766 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1768 *expected_align
= alignment
* BITS_PER_UNIT
;
1769 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1774 /* Find values inside STMT for that we want to measure histograms for
1775 division/modulo optimization. */
1778 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1780 tree lhs
, divisor
, op0
, type
;
1781 histogram_value hist
;
1783 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1786 lhs
= gimple_assign_lhs (stmt
);
1787 type
= TREE_TYPE (lhs
);
1788 if (!INTEGRAL_TYPE_P (type
))
1791 switch (gimple_assign_rhs_code (stmt
))
1793 case TRUNC_DIV_EXPR
:
1794 case TRUNC_MOD_EXPR
:
1795 divisor
= gimple_assign_rhs2 (stmt
);
1796 op0
= gimple_assign_rhs1 (stmt
);
1798 values
->reserve (3);
1800 if (TREE_CODE (divisor
) == SSA_NAME
)
1801 /* Check for the case where the divisor is the same value most
1803 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1804 HIST_TYPE_TOPN_VALUES
,
1807 /* For mod, check whether it is not often a noop (or replaceable by
1808 a few subtractions). */
1809 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1810 && TYPE_UNSIGNED (type
)
1811 && TREE_CODE (divisor
) == SSA_NAME
)
1814 /* Check for a special case where the divisor is power of 2. */
1815 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1819 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1820 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1822 hist
->hdata
.intvl
.int_start
= 0;
1823 hist
->hdata
.intvl
.steps
= 2;
1824 values
->quick_push (hist
);
1833 /* Find calls inside STMT for that we want to measure histograms for
1834 indirect/virtual call optimization. */
1837 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1841 if (gimple_code (stmt
) != GIMPLE_CALL
1842 || gimple_call_internal_p (stmt
)
1843 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1846 callee
= gimple_call_fn (stmt
);
1848 values
->reserve (3);
1850 values
->quick_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1856 /* Find values inside STMT for that we want to measure histograms for
1857 string operations. */
1860 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1867 stmt
= dyn_cast
<gcall
*> (gs
);
1871 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
1874 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1877 dest
= gimple_call_arg (stmt
, 0);
1878 blck_size
= gimple_call_arg (stmt
, size_arg
);
1880 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1882 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1883 HIST_TYPE_TOPN_VALUES
,
1885 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1889 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1890 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1894 /* Find values inside STMT for that we want to measure histograms and adds
1895 them to list VALUES. */
1898 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1900 gimple_divmod_values_to_profile (stmt
, values
);
1901 gimple_stringops_values_to_profile (stmt
, values
);
1902 gimple_indirect_call_to_profile (stmt
, values
);
1906 gimple_find_values_to_profile (histogram_values
*values
)
1909 gimple_stmt_iterator gsi
;
1911 histogram_value hist
= NULL
;
1914 FOR_EACH_BB_FN (bb
, cfun
)
1915 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1916 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1918 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
1920 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1924 case HIST_TYPE_INTERVAL
:
1925 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1928 case HIST_TYPE_POW2
:
1929 hist
->n_counters
= 2;
1932 case HIST_TYPE_TOPN_VALUES
:
1933 case HIST_TYPE_INDIR_CALL
:
1934 hist
->n_counters
= GCOV_TOPN_VALUES_COUNTERS
;
1937 case HIST_TYPE_TIME_PROFILE
:
1938 hist
->n_counters
= 1;
1941 case HIST_TYPE_AVERAGE
:
1942 hist
->n_counters
= 2;
1946 hist
->n_counters
= 1;
1952 if (dump_file
&& hist
->hvalue
.stmt
!= NULL
)
1954 fprintf (dump_file
, "Stmt ");
1955 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1956 dump_histogram_value (dump_file
, hist
);