1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2018 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 fprintf (dump_file
, "Interval counter range %d -- %d",
232 hist
->hdata
.intvl
.int_start
,
233 (hist
->hdata
.intvl
.int_start
234 + hist
->hdata
.intvl
.steps
- 1));
235 if (hist
->hvalue
.counters
)
238 fprintf (dump_file
, " [");
239 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 fprintf (dump_file
, " ] outside range:%" PRId64
,
244 (int64_t) hist
->hvalue
.counters
[i
]);
246 fprintf (dump_file
, ".\n");
250 fprintf (dump_file
, "Pow2 counter ");
251 if (hist
->hvalue
.counters
)
253 fprintf (dump_file
, "pow2:%" PRId64
255 (int64_t) hist
->hvalue
.counters
[1],
256 (int64_t) hist
->hvalue
.counters
[0]);
258 fprintf (dump_file
, ".\n");
261 case HIST_TYPE_SINGLE_VALUE
:
262 fprintf (dump_file
, "Single value ");
263 if (hist
->hvalue
.counters
)
265 fprintf (dump_file
, "value:%" PRId64
268 (int64_t) hist
->hvalue
.counters
[0],
269 (int64_t) hist
->hvalue
.counters
[1],
270 (int64_t) hist
->hvalue
.counters
[2]);
272 fprintf (dump_file
, ".\n");
275 case HIST_TYPE_AVERAGE
:
276 fprintf (dump_file
, "Average value ");
277 if (hist
->hvalue
.counters
)
279 fprintf (dump_file
, "sum:%" PRId64
281 (int64_t) hist
->hvalue
.counters
[0],
282 (int64_t) hist
->hvalue
.counters
[1]);
284 fprintf (dump_file
, ".\n");
288 fprintf (dump_file
, "IOR value ");
289 if (hist
->hvalue
.counters
)
291 fprintf (dump_file
, "ior:%" PRId64
,
292 (int64_t) hist
->hvalue
.counters
[0]);
294 fprintf (dump_file
, ".\n");
297 case HIST_TYPE_INDIR_CALL
:
298 fprintf (dump_file
, "Indirect call ");
299 if (hist
->hvalue
.counters
)
301 fprintf (dump_file
, "value:%" PRId64
304 (int64_t) hist
->hvalue
.counters
[0],
305 (int64_t) hist
->hvalue
.counters
[1],
306 (int64_t) hist
->hvalue
.counters
[2]);
308 fprintf (dump_file
, ".\n");
310 case HIST_TYPE_TIME_PROFILE
:
311 fprintf (dump_file
, "Time profile ");
312 if (hist
->hvalue
.counters
)
314 fprintf (dump_file
, "time:%" PRId64
,
315 (int64_t) hist
->hvalue
.counters
[0]);
317 fprintf (dump_file
, ".\n");
319 case HIST_TYPE_INDIR_CALL_TOPN
:
320 fprintf (dump_file
, "Indirect call topn ");
321 if (hist
->hvalue
.counters
)
325 fprintf (dump_file
, "accu:%" PRId64
, hist
->hvalue
.counters
[0]);
326 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
328 fprintf (dump_file
, " target:%" PRId64
" value:%" PRId64
,
329 (int64_t) hist
->hvalue
.counters
[i
],
330 (int64_t) hist
->hvalue
.counters
[i
+1]);
333 fprintf (dump_file
, ".\n");
340 /* Dump information about HIST to DUMP_FILE. */
343 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
348 bp
= bitpack_create (ob
->main_stream
);
349 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
350 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
351 streamer_write_bitpack (&bp
);
354 case HIST_TYPE_INTERVAL
:
355 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
356 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
361 for (i
= 0; i
< hist
->n_counters
; i
++)
363 /* When user uses an unsigned type with a big value, constant converted
364 to gcov_type (a signed type) can be negative. */
365 gcov_type value
= hist
->hvalue
.counters
[i
];
366 if (hist
->type
== HIST_TYPE_SINGLE_VALUE
&& i
== 0)
369 gcc_assert (value
>= 0);
371 streamer_write_gcov_count (ob
, value
);
373 if (hist
->hvalue
.next
)
374 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
377 /* Dump information about HIST to DUMP_FILE. */
380 stream_in_histogram_value (struct lto_input_block
*ib
, gimple
*stmt
)
383 unsigned int ncounters
= 0;
386 histogram_value new_val
;
388 histogram_value
*next_p
= NULL
;
392 bp
= streamer_read_bitpack (ib
);
393 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
394 next
= bp_unpack_value (&bp
, 1);
395 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
398 case HIST_TYPE_INTERVAL
:
399 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
400 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
401 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
405 case HIST_TYPE_AVERAGE
:
409 case HIST_TYPE_SINGLE_VALUE
:
410 case HIST_TYPE_INDIR_CALL
:
415 case HIST_TYPE_TIME_PROFILE
:
419 case HIST_TYPE_INDIR_CALL_TOPN
:
420 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
426 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
427 new_val
->n_counters
= ncounters
;
428 for (i
= 0; i
< ncounters
; i
++)
429 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
431 gimple_add_histogram_value (cfun
, stmt
, new_val
);
434 next_p
= &new_val
->hvalue
.next
;
439 /* Dump all histograms attached to STMT to DUMP_FILE. */
442 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
444 histogram_value hist
;
445 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
446 dump_histogram_value (dump_file
, hist
);
449 /* Remove all histograms associated with STMT. */
452 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
455 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
456 gimple_remove_histogram_value (fun
, stmt
, val
);
459 /* Duplicate all histograms associates with OSTMT to STMT. */
462 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
463 struct function
*ofun
, gimple
*ostmt
)
466 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
468 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
469 memcpy (new_val
, val
, sizeof (*val
));
470 new_val
->hvalue
.stmt
= stmt
;
471 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
472 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
473 gimple_add_histogram_value (fun
, stmt
, new_val
);
477 /* Move all histograms associated with OSTMT to STMT. */
480 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
482 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
485 /* The following three statements can't be reordered,
486 because histogram hashtab relies on stmt field value
487 for finding the exact slot. */
488 set_histogram_value (fun
, ostmt
, NULL
);
489 for (; val
!= NULL
; val
= val
->hvalue
.next
)
490 val
->hvalue
.stmt
= stmt
;
491 set_histogram_value (fun
, stmt
, val
);
495 static bool error_found
= false;
497 /* Helper function for verify_histograms. For each histogram reachable via htab
498 walk verify that it was reached via statement walk. */
501 visit_hist (void **slot
, void *data
)
503 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
504 histogram_value hist
= *(histogram_value
*) slot
;
506 if (!visited
->contains (hist
)
507 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
509 error ("dead histogram");
510 dump_histogram_value (stderr
, hist
);
511 debug_gimple_stmt (hist
->hvalue
.stmt
);
517 /* Verify sanity of the histograms. */
520 verify_histograms (void)
523 gimple_stmt_iterator gsi
;
524 histogram_value hist
;
527 hash_set
<histogram_value
> visited_hists
;
528 FOR_EACH_BB_FN (bb
, cfun
)
529 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
531 gimple
*stmt
= gsi_stmt (gsi
);
533 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
534 hist
= hist
->hvalue
.next
)
536 if (hist
->hvalue
.stmt
!= stmt
)
538 error ("Histogram value statement does not correspond to "
539 "the statement it is associated with");
540 debug_gimple_stmt (stmt
);
541 dump_histogram_value (stderr
, hist
);
544 visited_hists
.add (hist
);
547 if (VALUE_HISTOGRAMS (cfun
))
548 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
550 internal_error ("verify_histograms failed");
553 /* Helper function for verify_histograms. For each histogram reachable via htab
554 walk verify that it was reached via statement walk. */
557 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
559 histogram_value hist
= *(histogram_value
*) slot
;
560 free (hist
->hvalue
.counters
);
566 free_histograms (struct function
*fn
)
568 if (VALUE_HISTOGRAMS (fn
))
570 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
571 htab_delete (VALUE_HISTOGRAMS (fn
));
572 VALUE_HISTOGRAMS (fn
) = NULL
;
576 /* The overall number of invocations of the counter should match
577 execution count of basic block. Report it as error rather than
578 internal error as it might mean that user has misused the profile
582 check_counter (gimple
*stmt
, const char * name
,
583 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
585 gcov_type bb_count
= bb_count_d
.ipa ().to_gcov_type ();
586 if (*all
!= bb_count
|| *count
> *all
)
588 dump_user_location_t locus
;
589 locus
= ((stmt
!= NULL
)
590 ? dump_user_location_t (stmt
)
591 : dump_user_location_t::from_function_decl
592 (current_function_decl
));
593 if (flag_profile_correction
)
595 if (dump_enabled_p ())
596 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
597 "correcting inconsistent value profile: %s "
598 "profiler overall count (%d) does not match BB "
599 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
607 error_at (locus
.get_location_t (), "corrupted value profile: %s "
608 "profile counter (%d out of %d) inconsistent with "
609 "basic-block count (%d)",
621 /* GIMPLE based transformations. */
624 gimple_value_profile_transformations (void)
627 gimple_stmt_iterator gsi
;
628 bool changed
= false;
630 /* Autofdo does its own transformations for indirect calls,
631 and otherwise does not support value profiling. */
632 if (flag_auto_profile
)
635 FOR_EACH_BB_FN (bb
, cfun
)
637 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
639 gimple
*stmt
= gsi_stmt (gsi
);
640 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
646 fprintf (dump_file
, "Trying transformations on stmt ");
647 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
648 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
651 /* Transformations: */
652 /* The order of things in this conditional controls which
653 transformation is used when more than one is applicable. */
654 /* It is expected that any code added by the transformations
655 will be added before the current statement, and that the
656 current statement remain valid (although possibly
657 modified) upon return. */
658 if (gimple_mod_subtract_transform (&gsi
)
659 || gimple_divmod_fixed_value_transform (&gsi
)
660 || gimple_mod_pow2_value_transform (&gsi
)
661 || gimple_stringops_transform (&gsi
)
662 || gimple_ic_transform (&gsi
))
664 stmt
= gsi_stmt (gsi
);
666 /* Original statement may no longer be in the same block. */
667 if (bb
!= gimple_bb (stmt
))
669 bb
= gimple_bb (stmt
);
670 gsi
= gsi_for_stmt (stmt
);
679 /* Generate code for transformation 1 (with parent gimple assignment
680 STMT and probability of taking the optimal path PROB, which is
681 equivalent to COUNT/ALL within roundoff error). This generates the
682 result into a temp and returns the temp; it does not replace or
683 alter the original STMT. */
686 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, profile_probability prob
,
687 gcov_type count
, gcov_type all
)
689 gassign
*stmt1
, *stmt2
;
691 tree tmp0
, tmp1
, tmp2
;
692 gimple
*bb1end
, *bb2end
, *bb3end
;
693 basic_block bb
, bb2
, bb3
, bb4
;
694 tree optype
, op1
, op2
;
695 edge e12
, e13
, e23
, e24
, e34
;
696 gimple_stmt_iterator gsi
;
698 gcc_assert (is_gimple_assign (stmt
)
699 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
700 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
702 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
703 op1
= gimple_assign_rhs1 (stmt
);
704 op2
= gimple_assign_rhs2 (stmt
);
706 bb
= gimple_bb (stmt
);
707 gsi
= gsi_for_stmt (stmt
);
709 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
710 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
711 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
712 stmt2
= gimple_build_assign (tmp1
, op2
);
713 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
714 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
715 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
716 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
719 tmp2
= create_tmp_reg (optype
, "PROF");
720 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
721 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
724 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
725 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
729 /* Edge e23 connects bb2 to bb3, etc. */
730 e12
= split_block (bb
, bb1end
);
732 bb2
->count
= profile_count::from_gcov_type (count
);
733 e23
= split_block (bb2
, bb2end
);
735 bb3
->count
= profile_count::from_gcov_type (all
- count
);
736 e34
= split_block (bb3
, bb3end
);
738 bb4
->count
= profile_count::from_gcov_type (all
);
740 e12
->flags
&= ~EDGE_FALLTHRU
;
741 e12
->flags
|= EDGE_FALSE_VALUE
;
742 e12
->probability
= prob
;
744 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
745 e13
->probability
= prob
.invert ();
749 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
750 e24
->probability
= profile_probability::always ();
752 e34
->probability
= profile_probability::always ();
757 /* Do transform 1) on INSN if applicable. */
760 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
762 histogram_value histogram
;
764 gcov_type val
, count
, all
;
765 tree result
, value
, tree_val
;
766 profile_probability prob
;
769 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
773 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
776 code
= gimple_assign_rhs_code (stmt
);
778 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
781 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
782 HIST_TYPE_SINGLE_VALUE
);
786 value
= histogram
->hvalue
.value
;
787 val
= histogram
->hvalue
.counters
[0];
788 count
= histogram
->hvalue
.counters
[1];
789 all
= histogram
->hvalue
.counters
[2];
790 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
792 /* We require that count is at least half of all; this means
793 that for the transformation to fire the value must be constant
794 at least 50% of time (and 75% gives the guarantee of usage). */
795 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
797 || optimize_bb_for_size_p (gimple_bb (stmt
)))
800 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
803 /* Compute probability of taking the optimal path. */
805 prob
= profile_probability::probability_in_gcov_type (count
, all
);
807 prob
= profile_probability::never ();
809 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
810 tree_val
= build_int_cst (get_gcov_type (), val
);
814 a
[0] = (unsigned HOST_WIDE_INT
) val
;
815 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
817 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
818 TYPE_PRECISION (get_gcov_type ()), false));
820 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
824 fprintf (dump_file
, "Transformation done: div/mod by constant ");
825 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
826 fprintf (dump_file
, "\n");
829 gimple_assign_set_rhs_from_tree (si
, result
);
830 update_stmt (gsi_stmt (*si
));
835 /* Generate code for transformation 2 (with parent gimple assign STMT and
836 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
837 within roundoff error). This generates the result into a temp and returns
838 the temp; it does not replace or alter the original STMT. */
841 gimple_mod_pow2 (gassign
*stmt
, profile_probability prob
, gcov_type count
, gcov_type all
)
843 gassign
*stmt1
, *stmt2
, *stmt3
;
846 gimple
*bb1end
, *bb2end
, *bb3end
;
847 basic_block bb
, bb2
, bb3
, bb4
;
848 tree optype
, op1
, op2
;
849 edge e12
, e13
, e23
, e24
, e34
;
850 gimple_stmt_iterator gsi
;
853 gcc_assert (is_gimple_assign (stmt
)
854 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
856 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
857 op1
= gimple_assign_rhs1 (stmt
);
858 op2
= gimple_assign_rhs2 (stmt
);
860 bb
= gimple_bb (stmt
);
861 gsi
= gsi_for_stmt (stmt
);
863 result
= create_tmp_reg (optype
, "PROF");
864 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
865 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
866 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
867 build_int_cst (optype
, -1));
868 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
869 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
870 NULL_TREE
, NULL_TREE
);
871 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
872 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
873 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
876 /* tmp2 == op2-1 inherited from previous block. */
877 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
878 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
881 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
883 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
887 /* Edge e23 connects bb2 to bb3, etc. */
888 e12
= split_block (bb
, bb1end
);
890 bb2
->count
= profile_count::from_gcov_type (count
);
891 e23
= split_block (bb2
, bb2end
);
893 bb3
->count
= profile_count::from_gcov_type (all
- count
);
894 e34
= split_block (bb3
, bb3end
);
896 bb4
->count
= profile_count::from_gcov_type (all
);
898 e12
->flags
&= ~EDGE_FALLTHRU
;
899 e12
->flags
|= EDGE_FALSE_VALUE
;
900 e12
->probability
= prob
;
902 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
903 e13
->probability
= prob
.invert ();
907 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
908 e24
->probability
= profile_probability::always ();
910 e34
->probability
= profile_probability::always ();
915 /* Do transform 2) on INSN if applicable. */
918 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
920 histogram_value histogram
;
922 gcov_type count
, wrong_values
, all
;
923 tree lhs_type
, result
, value
;
924 profile_probability prob
;
927 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
931 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
932 if (!INTEGRAL_TYPE_P (lhs_type
))
935 code
= gimple_assign_rhs_code (stmt
);
937 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
940 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
944 value
= histogram
->hvalue
.value
;
945 wrong_values
= histogram
->hvalue
.counters
[0];
946 count
= histogram
->hvalue
.counters
[1];
948 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
950 /* We require that we hit a power of 2 at least half of all evaluations. */
951 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
952 || count
< wrong_values
953 || optimize_bb_for_size_p (gimple_bb (stmt
)))
956 /* Compute probability of taking the optimal path. */
957 all
= count
+ wrong_values
;
959 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
963 fprintf (dump_file
, "Transformation done: mod power of 2\n");
966 prob
= profile_probability::probability_in_gcov_type (count
, all
);
968 prob
= profile_probability::never ();
970 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
972 gimple_assign_set_rhs_from_tree (si
, result
);
973 update_stmt (gsi_stmt (*si
));
978 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
979 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
980 supported and this is built into this interface. The probabilities of taking
981 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
982 COUNT2/ALL respectively within roundoff error). This generates the
983 result into a temp and returns the temp; it does not replace or alter
984 the original STMT. */
985 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
988 gimple_mod_subtract (gassign
*stmt
, profile_probability prob1
,
989 profile_probability prob2
, int ncounts
,
990 gcov_type count1
, gcov_type count2
, gcov_type all
)
996 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
997 basic_block bb
, bb2
, bb3
, bb4
;
998 tree optype
, op1
, op2
;
999 edge e12
, e23
= 0, e24
, e34
, e14
;
1000 gimple_stmt_iterator gsi
;
1003 gcc_assert (is_gimple_assign (stmt
)
1004 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1006 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1007 op1
= gimple_assign_rhs1 (stmt
);
1008 op2
= gimple_assign_rhs2 (stmt
);
1010 bb
= gimple_bb (stmt
);
1011 gsi
= gsi_for_stmt (stmt
);
1013 result
= create_tmp_reg (optype
, "PROF");
1014 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1015 stmt1
= gimple_build_assign (result
, op1
);
1016 stmt2
= gimple_build_assign (tmp1
, op2
);
1017 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1018 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1019 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1020 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1023 if (ncounts
) /* Assumed to be 0 or 1 */
1025 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1026 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1027 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1028 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1032 /* Fallback case. */
1033 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1035 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1039 /* Edge e23 connects bb2 to bb3, etc. */
1040 /* However block 3 is optional; if it is not there, references
1041 to 3 really refer to block 2. */
1042 e12
= split_block (bb
, bb1end
);
1044 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1046 if (ncounts
) /* Assumed to be 0 or 1. */
1048 e23
= split_block (bb2
, bb2end
);
1050 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1053 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1055 bb4
->count
= profile_count::from_gcov_type (all
);
1057 e12
->flags
&= ~EDGE_FALLTHRU
;
1058 e12
->flags
|= EDGE_FALSE_VALUE
;
1059 e12
->probability
= prob1
.invert ();
1061 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1062 e14
->probability
= prob1
;
1064 if (ncounts
) /* Assumed to be 0 or 1. */
1066 e23
->flags
&= ~EDGE_FALLTHRU
;
1067 e23
->flags
|= EDGE_FALSE_VALUE
;
1068 e23
->probability
= prob2
.invert ();
1070 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1071 e24
->probability
= prob2
;
1074 e34
->probability
= profile_probability::always ();
1079 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1082 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1084 histogram_value histogram
;
1085 enum tree_code code
;
1086 gcov_type count
, wrong_values
, all
;
1087 tree lhs_type
, result
;
1088 profile_probability prob1
, prob2
;
1089 unsigned int i
, steps
;
1090 gcov_type count1
, count2
;
1092 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1096 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1097 if (!INTEGRAL_TYPE_P (lhs_type
))
1100 code
= gimple_assign_rhs_code (stmt
);
1102 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1105 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1111 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1112 all
+= histogram
->hvalue
.counters
[i
];
1114 wrong_values
+= histogram
->hvalue
.counters
[i
];
1115 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1116 steps
= histogram
->hdata
.intvl
.steps
;
1117 all
+= wrong_values
;
1118 count1
= histogram
->hvalue
.counters
[0];
1119 count2
= histogram
->hvalue
.counters
[1];
1121 /* Compute probability of taking the optimal path. */
1122 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1124 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1128 if (flag_profile_correction
&& count1
+ count2
> all
)
1129 all
= count1
+ count2
;
1131 gcc_assert (count1
+ count2
<= all
);
1133 /* We require that we use just subtractions in at least 50% of all
1136 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1138 count
+= histogram
->hvalue
.counters
[i
];
1139 if (count
* 2 >= all
)
1143 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1146 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1148 fprintf (dump_file
, "Transformation done: mod subtract\n");
1150 /* Compute probability of taking the optimal path(s). */
1153 prob1
= profile_probability::probability_in_gcov_type (count1
, all
);
1154 prob2
= profile_probability::probability_in_gcov_type (count2
, all
);
1158 prob1
= prob2
= profile_probability::never ();
1161 /* In practice, "steps" is always 2. This interface reflects this,
1162 and will need to be changed if "steps" can change. */
1163 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1165 gimple_assign_set_rhs_from_tree (si
, result
);
1166 update_stmt (gsi_stmt (*si
));
1171 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1173 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1175 /* Returns true if node graph is initialized. This
1176 is used to test if profile_id has been created
1177 for cgraph_nodes. */
1180 coverage_node_map_initialized_p (void)
1182 return cgraph_node_map
!= 0;
1185 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1186 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1187 that the PROFILE_IDs was already assigned. */
1190 init_node_map (bool local
)
1192 struct cgraph_node
*n
;
1193 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1195 FOR_EACH_DEFINED_FUNCTION (n
)
1196 if (n
->has_gimple_body_p ())
1201 n
->profile_id
= coverage_compute_profile_id (n
);
1202 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1206 fprintf (dump_file
, "Local profile-id %i conflict"
1207 " with nodes %s %s\n",
1210 (*val
)->dump_name ());
1211 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1214 else if (!n
->profile_id
)
1218 "Node %s has no profile-id"
1219 " (profile feedback missing?)\n",
1223 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1227 "Node %s has IP profile-id %i conflict. "
1229 n
->dump_name (), n
->profile_id
);
1233 cgraph_node_map
->put (n
->profile_id
, n
);
1237 /* Delete the CGRAPH_NODE_MAP. */
1242 delete cgraph_node_map
;
1245 /* Return cgraph node for function with pid */
1248 find_func_by_profile_id (int profile_id
)
1250 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1257 /* Perform sanity check on the indirect call target. Due to race conditions,
1258 false function target may be attributed to an indirect call site. If the
1259 call expression type mismatches with the target function's type, expand_call
1260 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1261 Returns true if TARGET is considered ok for call CALL_STMT. */
1264 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1266 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1269 if (dump_enabled_p ())
1270 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, call_stmt
,
1271 "Skipping target %s with mismatching types for icall\n",
1276 /* Do transformation
1278 if (actual_callee_address == address_of_most_common_function/method)
1285 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1286 profile_probability prob
)
1291 tree tmp0
, tmp1
, tmp
;
1292 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1293 tree optype
= build_pointer_type (void_type_node
);
1294 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1295 gimple_stmt_iterator gsi
;
1300 cond_bb
= gimple_bb (icall_stmt
);
1301 gsi
= gsi_for_stmt (icall_stmt
);
1303 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1304 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1305 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1306 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1307 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1309 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
));
1310 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1311 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1313 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1314 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1316 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1318 unlink_stmt_vdef (icall_stmt
);
1319 release_ssa_name (gimple_vdef (icall_stmt
));
1321 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1322 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1323 update_stmt (icall_stmt
);
1324 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1325 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1326 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1327 if ((dflags
& ECF_NORETURN
) != 0
1328 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1329 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1330 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1333 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1334 e_cd
= split_block (cond_bb
, cond_stmt
);
1335 dcall_bb
= e_cd
->dest
;
1336 dcall_bb
->count
= cond_bb
->count
.apply_probability (prob
);
1338 e_di
= split_block (dcall_bb
, dcall_stmt
);
1339 icall_bb
= e_di
->dest
;
1340 icall_bb
->count
= cond_bb
->count
- dcall_bb
->count
;
1342 /* Do not disturb existing EH edges from the indirect call. */
1343 if (!stmt_ends_bb_p (icall_stmt
))
1344 e_ij
= split_block (icall_bb
, icall_stmt
);
1347 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1348 /* The indirect call might be noreturn. */
1351 e_ij
->probability
= profile_probability::always ();
1352 e_ij
= single_pred_edge (split_edge (e_ij
));
1357 join_bb
= e_ij
->dest
;
1358 join_bb
->count
= cond_bb
->count
;
1361 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1362 e_cd
->probability
= prob
;
1364 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1365 e_ci
->probability
= prob
.invert ();
1371 if ((dflags
& ECF_NORETURN
) == 0)
1373 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1374 e_dj
->probability
= profile_probability::always ();
1376 e_ij
->probability
= profile_probability::always ();
1379 /* Insert PHI node for the call result if necessary. */
1380 if (gimple_call_lhs (icall_stmt
)
1381 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1382 && (dflags
& ECF_NORETURN
) == 0)
1384 tree result
= gimple_call_lhs (icall_stmt
);
1385 gphi
*phi
= create_phi_node (result
, join_bb
);
1386 gimple_call_set_lhs (icall_stmt
,
1387 duplicate_ssa_name (result
, icall_stmt
));
1388 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1389 gimple_call_set_lhs (dcall_stmt
,
1390 duplicate_ssa_name (result
, dcall_stmt
));
1391 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1394 /* Build an EH edge for the direct call if necessary. */
1395 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1396 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1398 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1401 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1402 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1404 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1405 e
->probability
= e_eh
->probability
;
1406 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1407 !gsi_end_p (psi
); gsi_next (&psi
))
1409 gphi
*phi
= psi
.phi ();
1410 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1411 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1414 if (!stmt_could_throw_p (dcall_stmt
))
1415 gimple_purge_dead_eh_edges (dcall_bb
);
1420 For every checked indirect/virtual call determine if most common pid of
1421 function/class method has probability more than 50%. If yes modify code of
1426 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1429 histogram_value histogram
;
1430 gcov_type val
, count
, all
, bb_all
;
1431 struct cgraph_node
*direct_call
;
1433 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1437 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1440 if (gimple_call_internal_p (stmt
))
1443 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1447 val
= histogram
->hvalue
.counters
[0];
1448 count
= histogram
->hvalue
.counters
[1];
1449 all
= histogram
->hvalue
.counters
[2];
1451 bb_all
= gimple_bb (stmt
)->count
.ipa ().to_gcov_type ();
1452 /* The order of CHECK_COUNTER calls is important -
1453 since check_counter can correct the third parameter
1454 and we want to make count <= all <= bb_all. */
1455 if (check_counter (stmt
, "ic", &all
, &bb_all
, gimple_bb (stmt
)->count
)
1456 || check_counter (stmt
, "ic", &count
, &all
,
1457 profile_count::from_gcov_type (all
)))
1459 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1463 if (4 * count
<= 3 * all
)
1466 direct_call
= find_func_by_profile_id ((int)val
);
1468 if (direct_call
== NULL
)
1474 fprintf (dump_file
, "Indirect call -> direct call from other module");
1475 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1476 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1482 if (!check_ic_target (stmt
, direct_call
))
1486 fprintf (dump_file
, "Indirect call -> direct call ");
1487 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1488 fprintf (dump_file
, "=> ");
1489 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1490 fprintf (dump_file
, " transformation skipped because of type mismatch");
1491 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1493 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1499 fprintf (dump_file
, "Indirect call -> direct call ");
1500 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1501 fprintf (dump_file
, "=> ");
1502 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1503 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1504 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1505 fprintf (dump_file
, "hist->count %" PRId64
1506 " hist->all %" PRId64
"\n", count
, all
);
1512 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1513 set to the argument index for the size of the string operation. */
1516 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1518 enum built_in_function fcode
;
1520 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1523 case BUILT_IN_MEMCPY
:
1524 case BUILT_IN_MEMPCPY
:
1525 case BUILT_IN_MEMMOVE
:
1527 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1528 INTEGER_TYPE
, VOID_TYPE
);
1529 case BUILT_IN_MEMSET
:
1531 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1532 INTEGER_TYPE
, VOID_TYPE
);
1533 case BUILT_IN_BZERO
:
1535 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1542 /* Convert stringop (..., vcall_size)
1544 if (vcall_size == icall_size)
1545 stringop (..., icall_size);
1547 stringop (..., vcall_size);
1548 assuming we'll propagate a true constant into ICALL_SIZE later. */
1551 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, profile_probability prob
,
1552 gcov_type count
, gcov_type all
)
1557 tree tmp0
, tmp1
, vcall_size
, optype
;
1558 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1559 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1560 gimple_stmt_iterator gsi
;
1563 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1566 cond_bb
= gimple_bb (vcall_stmt
);
1567 gsi
= gsi_for_stmt (vcall_stmt
);
1569 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1570 optype
= TREE_TYPE (vcall_size
);
1572 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1573 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1574 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1575 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1577 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1578 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1580 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1581 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1583 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1585 unlink_stmt_vdef (vcall_stmt
);
1586 release_ssa_name (gimple_vdef (vcall_stmt
));
1588 gimple_set_vdef (vcall_stmt
, NULL
);
1589 gimple_set_vuse (vcall_stmt
, NULL
);
1590 update_stmt (vcall_stmt
);
1591 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1592 gimple_call_set_arg (icall_stmt
, size_arg
,
1593 fold_convert (optype
, icall_size
));
1594 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1597 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1598 e_ci
= split_block (cond_bb
, cond_stmt
);
1599 icall_bb
= e_ci
->dest
;
1600 icall_bb
->count
= profile_count::from_gcov_type (count
);
1602 e_iv
= split_block (icall_bb
, icall_stmt
);
1603 vcall_bb
= e_iv
->dest
;
1604 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1606 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1607 join_bb
= e_vj
->dest
;
1608 join_bb
->count
= profile_count::from_gcov_type (all
);
1610 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1611 e_ci
->probability
= prob
;
1613 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1614 e_cv
->probability
= prob
.invert ();
1618 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1619 e_ij
->probability
= profile_probability::always ();
1621 e_vj
->probability
= profile_probability::always ();
1623 /* Insert PHI node for the call result if necessary. */
1624 if (gimple_call_lhs (vcall_stmt
)
1625 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1627 tree result
= gimple_call_lhs (vcall_stmt
);
1628 gphi
*phi
= create_phi_node (result
, join_bb
);
1629 gimple_call_set_lhs (vcall_stmt
,
1630 duplicate_ssa_name (result
, vcall_stmt
));
1631 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1632 gimple_call_set_lhs (icall_stmt
,
1633 duplicate_ssa_name (result
, icall_stmt
));
1634 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1637 /* Because these are all string op builtins, they're all nothrow. */
1638 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1639 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1642 /* Find values inside STMT for that we want to measure histograms for
1643 division/modulo optimization. */
1646 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1650 enum built_in_function fcode
;
1651 histogram_value histogram
;
1652 gcov_type count
, all
, val
;
1654 unsigned int dest_align
, src_align
;
1655 profile_probability prob
;
1659 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1663 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1666 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1669 blck_size
= gimple_call_arg (stmt
, size_arg
);
1670 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1673 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1677 val
= histogram
->hvalue
.counters
[0];
1678 count
= histogram
->hvalue
.counters
[1];
1679 all
= histogram
->hvalue
.counters
[2];
1680 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1682 /* We require that count is at least half of all; this means
1683 that for the transformation to fire the value must be constant
1684 at least 80% of time. */
1685 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1687 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1690 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1692 prob
= profile_probability::never ();
1694 dest
= gimple_call_arg (stmt
, 0);
1695 dest_align
= get_pointer_alignment (dest
);
1696 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1699 case BUILT_IN_MEMCPY
:
1700 case BUILT_IN_MEMPCPY
:
1701 case BUILT_IN_MEMMOVE
:
1702 src
= gimple_call_arg (stmt
, 1);
1703 src_align
= get_pointer_alignment (src
);
1704 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1707 case BUILT_IN_MEMSET
:
1708 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1709 gimple_call_arg (stmt
, 1),
1713 case BUILT_IN_BZERO
:
1714 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1723 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1724 tree_val
= build_int_cst (get_gcov_type (), val
);
1728 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1729 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1731 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1732 TYPE_PRECISION (get_gcov_type ()), false));
1737 "Transformation done: single value %i stringop for %s\n",
1738 (int)val
, built_in_names
[(int)fcode
]);
1740 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1746 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1747 HOST_WIDE_INT
*expected_size
)
1749 histogram_value histogram
;
1750 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1753 *expected_size
= -1;
1754 else if (!histogram
->hvalue
.counters
[1])
1756 *expected_size
= -1;
1757 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1762 size
= ((histogram
->hvalue
.counters
[0]
1763 + histogram
->hvalue
.counters
[1] / 2)
1764 / histogram
->hvalue
.counters
[1]);
1765 /* Even if we can hold bigger value in SIZE, INT_MAX
1766 is safe "infinity" for code generation strategies. */
1769 *expected_size
= size
;
1770 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1773 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1776 *expected_align
= 0;
1777 else if (!histogram
->hvalue
.counters
[0])
1779 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1780 *expected_align
= 0;
1785 unsigned int alignment
;
1787 count
= histogram
->hvalue
.counters
[0];
1789 while (!(count
& alignment
)
1790 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1792 *expected_align
= alignment
* BITS_PER_UNIT
;
1793 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1798 /* Find values inside STMT for that we want to measure histograms for
1799 division/modulo optimization. */
1802 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1804 tree lhs
, divisor
, op0
, type
;
1805 histogram_value hist
;
1807 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1810 lhs
= gimple_assign_lhs (stmt
);
1811 type
= TREE_TYPE (lhs
);
1812 if (!INTEGRAL_TYPE_P (type
))
1815 switch (gimple_assign_rhs_code (stmt
))
1817 case TRUNC_DIV_EXPR
:
1818 case TRUNC_MOD_EXPR
:
1819 divisor
= gimple_assign_rhs2 (stmt
);
1820 op0
= gimple_assign_rhs1 (stmt
);
1822 values
->reserve (3);
1824 if (TREE_CODE (divisor
) == SSA_NAME
)
1825 /* Check for the case where the divisor is the same value most
1827 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1828 HIST_TYPE_SINGLE_VALUE
,
1831 /* For mod, check whether it is not often a noop (or replaceable by
1832 a few subtractions). */
1833 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1834 && TYPE_UNSIGNED (type
)
1835 && TREE_CODE (divisor
) == SSA_NAME
)
1838 /* Check for a special case where the divisor is power of 2. */
1839 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1843 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1844 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1846 hist
->hdata
.intvl
.int_start
= 0;
1847 hist
->hdata
.intvl
.steps
= 2;
1848 values
->quick_push (hist
);
1857 /* Find calls inside STMT for that we want to measure histograms for
1858 indirect/virtual call optimization. */
1861 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1865 if (gimple_code (stmt
) != GIMPLE_CALL
1866 || gimple_call_internal_p (stmt
)
1867 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1870 callee
= gimple_call_fn (stmt
);
1872 values
->reserve (3);
1874 values
->quick_push (gimple_alloc_histogram_value (
1876 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1877 HIST_TYPE_INDIR_CALL_TOPN
:
1878 HIST_TYPE_INDIR_CALL
,
1884 /* Find values inside STMT for that we want to measure histograms for
1885 string operations. */
1888 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1895 stmt
= dyn_cast
<gcall
*> (gs
);
1899 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
1902 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1905 dest
= gimple_call_arg (stmt
, 0);
1906 blck_size
= gimple_call_arg (stmt
, size_arg
);
1908 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1910 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1911 HIST_TYPE_SINGLE_VALUE
,
1913 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1917 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1918 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1922 /* Find values inside STMT for that we want to measure histograms and adds
1923 them to list VALUES. */
1926 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1928 gimple_divmod_values_to_profile (stmt
, values
);
1929 gimple_stringops_values_to_profile (stmt
, values
);
1930 gimple_indirect_call_to_profile (stmt
, values
);
1934 gimple_find_values_to_profile (histogram_values
*values
)
1937 gimple_stmt_iterator gsi
;
1939 histogram_value hist
= NULL
;
1942 FOR_EACH_BB_FN (bb
, cfun
)
1943 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1944 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1946 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
1948 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1952 case HIST_TYPE_INTERVAL
:
1953 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1956 case HIST_TYPE_POW2
:
1957 hist
->n_counters
= 2;
1960 case HIST_TYPE_SINGLE_VALUE
:
1961 hist
->n_counters
= 3;
1964 case HIST_TYPE_INDIR_CALL
:
1965 hist
->n_counters
= 3;
1968 case HIST_TYPE_TIME_PROFILE
:
1969 hist
->n_counters
= 1;
1972 case HIST_TYPE_AVERAGE
:
1973 hist
->n_counters
= 2;
1977 hist
->n_counters
= 1;
1980 case HIST_TYPE_INDIR_CALL_TOPN
:
1981 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
1987 if (dump_file
&& hist
->hvalue
.stmt
!= NULL
)
1989 fprintf (dump_file
, "Stmt ");
1990 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1991 dump_histogram_value (dump_file
, hist
);