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 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 FOR_EACH_BB_FN (bb
, cfun
)
632 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
634 gimple
*stmt
= gsi_stmt (gsi
);
635 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
641 fprintf (dump_file
, "Trying transformations on stmt ");
642 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
643 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
646 /* Transformations: */
647 /* The order of things in this conditional controls which
648 transformation is used when more than one is applicable. */
649 /* It is expected that any code added by the transformations
650 will be added before the current statement, and that the
651 current statement remain valid (although possibly
652 modified) upon return. */
653 if (gimple_mod_subtract_transform (&gsi
)
654 || gimple_divmod_fixed_value_transform (&gsi
)
655 || gimple_mod_pow2_value_transform (&gsi
)
656 || gimple_stringops_transform (&gsi
)
657 || gimple_ic_transform (&gsi
))
659 stmt
= gsi_stmt (gsi
);
661 /* Original statement may no longer be in the same block. */
662 if (bb
!= gimple_bb (stmt
))
664 bb
= gimple_bb (stmt
);
665 gsi
= gsi_for_stmt (stmt
);
674 /* Generate code for transformation 1 (with parent gimple assignment
675 STMT and probability of taking the optimal path PROB, which is
676 equivalent to COUNT/ALL within roundoff error). This generates the
677 result into a temp and returns the temp; it does not replace or
678 alter the original STMT. */
681 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, profile_probability prob
,
682 gcov_type count
, gcov_type all
)
684 gassign
*stmt1
, *stmt2
;
686 tree tmp0
, tmp1
, tmp2
;
687 gimple
*bb1end
, *bb2end
, *bb3end
;
688 basic_block bb
, bb2
, bb3
, bb4
;
689 tree optype
, op1
, op2
;
690 edge e12
, e13
, e23
, e24
, e34
;
691 gimple_stmt_iterator gsi
;
693 gcc_assert (is_gimple_assign (stmt
)
694 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
695 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
697 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
698 op1
= gimple_assign_rhs1 (stmt
);
699 op2
= gimple_assign_rhs2 (stmt
);
701 bb
= gimple_bb (stmt
);
702 gsi
= gsi_for_stmt (stmt
);
704 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
705 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
706 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
707 stmt2
= gimple_build_assign (tmp1
, op2
);
708 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
709 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
710 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
711 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
714 tmp2
= create_tmp_reg (optype
, "PROF");
715 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
716 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
719 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
720 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
724 /* Edge e23 connects bb2 to bb3, etc. */
725 e12
= split_block (bb
, bb1end
);
727 bb2
->count
= profile_count::from_gcov_type (count
);
728 e23
= split_block (bb2
, bb2end
);
730 bb3
->count
= profile_count::from_gcov_type (all
- count
);
731 e34
= split_block (bb3
, bb3end
);
733 bb4
->count
= profile_count::from_gcov_type (all
);
735 e12
->flags
&= ~EDGE_FALLTHRU
;
736 e12
->flags
|= EDGE_FALSE_VALUE
;
737 e12
->probability
= prob
;
739 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
740 e13
->probability
= prob
.invert ();
744 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
745 e24
->probability
= profile_probability::always ();
747 e34
->probability
= profile_probability::always ();
752 /* Do transform 1) on INSN if applicable. */
755 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
757 histogram_value histogram
;
759 gcov_type val
, count
, all
;
760 tree result
, value
, tree_val
;
761 profile_probability prob
;
764 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
768 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
771 code
= gimple_assign_rhs_code (stmt
);
773 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
776 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
777 HIST_TYPE_SINGLE_VALUE
);
781 value
= histogram
->hvalue
.value
;
782 val
= histogram
->hvalue
.counters
[0];
783 count
= histogram
->hvalue
.counters
[1];
784 all
= histogram
->hvalue
.counters
[2];
785 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
787 /* We require that count is at least half of all; this means
788 that for the transformation to fire the value must be constant
789 at least 50% of time (and 75% gives the guarantee of usage). */
790 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
792 || optimize_bb_for_size_p (gimple_bb (stmt
)))
795 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
798 /* Compute probability of taking the optimal path. */
800 prob
= profile_probability::probability_in_gcov_type (count
, all
);
802 prob
= profile_probability::never ();
804 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
805 tree_val
= build_int_cst (get_gcov_type (), val
);
809 a
[0] = (unsigned HOST_WIDE_INT
) val
;
810 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
812 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
813 TYPE_PRECISION (get_gcov_type ()), false));
815 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
819 fprintf (dump_file
, "Transformation done: div/mod by constant ");
820 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
821 fprintf (dump_file
, "\n");
824 gimple_assign_set_rhs_from_tree (si
, result
);
825 update_stmt (gsi_stmt (*si
));
830 /* Generate code for transformation 2 (with parent gimple assign STMT and
831 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
832 within roundoff error). This generates the result into a temp and returns
833 the temp; it does not replace or alter the original STMT. */
836 gimple_mod_pow2 (gassign
*stmt
, profile_probability prob
, gcov_type count
, gcov_type all
)
838 gassign
*stmt1
, *stmt2
, *stmt3
;
841 gimple
*bb1end
, *bb2end
, *bb3end
;
842 basic_block bb
, bb2
, bb3
, bb4
;
843 tree optype
, op1
, op2
;
844 edge e12
, e13
, e23
, e24
, e34
;
845 gimple_stmt_iterator gsi
;
848 gcc_assert (is_gimple_assign (stmt
)
849 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
851 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
852 op1
= gimple_assign_rhs1 (stmt
);
853 op2
= gimple_assign_rhs2 (stmt
);
855 bb
= gimple_bb (stmt
);
856 gsi
= gsi_for_stmt (stmt
);
858 result
= create_tmp_reg (optype
, "PROF");
859 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
860 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
861 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
862 build_int_cst (optype
, -1));
863 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
864 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
865 NULL_TREE
, NULL_TREE
);
866 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
867 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
868 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
871 /* tmp2 == op2-1 inherited from previous block. */
872 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
873 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
876 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
878 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
882 /* Edge e23 connects bb2 to bb3, etc. */
883 e12
= split_block (bb
, bb1end
);
885 bb2
->count
= profile_count::from_gcov_type (count
);
886 e23
= split_block (bb2
, bb2end
);
888 bb3
->count
= profile_count::from_gcov_type (all
- count
);
889 e34
= split_block (bb3
, bb3end
);
891 bb4
->count
= profile_count::from_gcov_type (all
);
893 e12
->flags
&= ~EDGE_FALLTHRU
;
894 e12
->flags
|= EDGE_FALSE_VALUE
;
895 e12
->probability
= prob
;
897 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
898 e13
->probability
= prob
.invert ();
902 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
903 e24
->probability
= profile_probability::always ();
905 e34
->probability
= profile_probability::always ();
910 /* Do transform 2) on INSN if applicable. */
913 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
915 histogram_value histogram
;
917 gcov_type count
, wrong_values
, all
;
918 tree lhs_type
, result
, value
;
919 profile_probability prob
;
922 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
926 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
927 if (!INTEGRAL_TYPE_P (lhs_type
))
930 code
= gimple_assign_rhs_code (stmt
);
932 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
935 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
939 value
= histogram
->hvalue
.value
;
940 wrong_values
= histogram
->hvalue
.counters
[0];
941 count
= histogram
->hvalue
.counters
[1];
943 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
945 /* We require that we hit a power of 2 at least half of all evaluations. */
946 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
947 || count
< wrong_values
948 || optimize_bb_for_size_p (gimple_bb (stmt
)))
951 /* Compute probability of taking the optimal path. */
952 all
= count
+ wrong_values
;
954 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
958 fprintf (dump_file
, "Transformation done: mod power of 2\n");
961 prob
= profile_probability::probability_in_gcov_type (count
, all
);
963 prob
= profile_probability::never ();
965 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
967 gimple_assign_set_rhs_from_tree (si
, result
);
968 update_stmt (gsi_stmt (*si
));
973 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
974 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
975 supported and this is built into this interface. The probabilities of taking
976 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
977 COUNT2/ALL respectively within roundoff error). This generates the
978 result into a temp and returns the temp; it does not replace or alter
979 the original STMT. */
980 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
983 gimple_mod_subtract (gassign
*stmt
, profile_probability prob1
,
984 profile_probability prob2
, int ncounts
,
985 gcov_type count1
, gcov_type count2
, gcov_type all
)
991 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
992 basic_block bb
, bb2
, bb3
, bb4
;
993 tree optype
, op1
, op2
;
994 edge e12
, e23
= 0, e24
, e34
, e14
;
995 gimple_stmt_iterator gsi
;
998 gcc_assert (is_gimple_assign (stmt
)
999 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1001 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1002 op1
= gimple_assign_rhs1 (stmt
);
1003 op2
= gimple_assign_rhs2 (stmt
);
1005 bb
= gimple_bb (stmt
);
1006 gsi
= gsi_for_stmt (stmt
);
1008 result
= create_tmp_reg (optype
, "PROF");
1009 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1010 stmt1
= gimple_build_assign (result
, op1
);
1011 stmt2
= gimple_build_assign (tmp1
, op2
);
1012 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1013 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1014 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1015 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1018 if (ncounts
) /* Assumed to be 0 or 1 */
1020 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1021 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1022 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1023 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1027 /* Fallback case. */
1028 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1030 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1034 /* Edge e23 connects bb2 to bb3, etc. */
1035 /* However block 3 is optional; if it is not there, references
1036 to 3 really refer to block 2. */
1037 e12
= split_block (bb
, bb1end
);
1039 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1041 if (ncounts
) /* Assumed to be 0 or 1. */
1043 e23
= split_block (bb2
, bb2end
);
1045 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1048 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1050 bb4
->count
= profile_count::from_gcov_type (all
);
1052 e12
->flags
&= ~EDGE_FALLTHRU
;
1053 e12
->flags
|= EDGE_FALSE_VALUE
;
1054 e12
->probability
= prob1
.invert ();
1056 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1057 e14
->probability
= prob1
;
1059 if (ncounts
) /* Assumed to be 0 or 1. */
1061 e23
->flags
&= ~EDGE_FALLTHRU
;
1062 e23
->flags
|= EDGE_FALSE_VALUE
;
1063 e23
->probability
= prob2
.invert ();
1065 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1066 e24
->probability
= prob2
;
1069 e34
->probability
= profile_probability::always ();
1074 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1077 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1079 histogram_value histogram
;
1080 enum tree_code code
;
1081 gcov_type count
, wrong_values
, all
;
1082 tree lhs_type
, result
;
1083 profile_probability prob1
, prob2
;
1084 unsigned int i
, steps
;
1085 gcov_type count1
, count2
;
1087 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1091 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1092 if (!INTEGRAL_TYPE_P (lhs_type
))
1095 code
= gimple_assign_rhs_code (stmt
);
1097 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1100 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1106 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1107 all
+= histogram
->hvalue
.counters
[i
];
1109 wrong_values
+= histogram
->hvalue
.counters
[i
];
1110 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1111 steps
= histogram
->hdata
.intvl
.steps
;
1112 all
+= wrong_values
;
1113 count1
= histogram
->hvalue
.counters
[0];
1114 count2
= histogram
->hvalue
.counters
[1];
1116 /* Compute probability of taking the optimal path. */
1117 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1119 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1123 if (flag_profile_correction
&& count1
+ count2
> all
)
1124 all
= count1
+ count2
;
1126 gcc_assert (count1
+ count2
<= all
);
1128 /* We require that we use just subtractions in at least 50% of all
1131 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1133 count
+= histogram
->hvalue
.counters
[i
];
1134 if (count
* 2 >= all
)
1138 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1141 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1143 fprintf (dump_file
, "Transformation done: mod subtract\n");
1145 /* Compute probability of taking the optimal path(s). */
1148 prob1
= profile_probability::probability_in_gcov_type (count1
, all
);
1149 prob2
= profile_probability::probability_in_gcov_type (count2
, all
);
1153 prob1
= prob2
= profile_probability::never ();
1156 /* In practice, "steps" is always 2. This interface reflects this,
1157 and will need to be changed if "steps" can change. */
1158 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1160 gimple_assign_set_rhs_from_tree (si
, result
);
1161 update_stmt (gsi_stmt (*si
));
1166 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1168 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1170 /* Returns true if node graph is initialized. This
1171 is used to test if profile_id has been created
1172 for cgraph_nodes. */
1175 coverage_node_map_initialized_p (void)
1177 return cgraph_node_map
!= 0;
1180 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1181 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1182 that the PROFILE_IDs was already assigned. */
1185 init_node_map (bool local
)
1187 struct cgraph_node
*n
;
1188 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1190 FOR_EACH_DEFINED_FUNCTION (n
)
1191 if (n
->has_gimple_body_p () || n
->thunk
.thunk_p
)
1196 n
->profile_id
= coverage_compute_profile_id (n
);
1197 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1201 fprintf (dump_file
, "Local profile-id %i conflict"
1202 " with nodes %s %s\n",
1205 (*val
)->dump_name ());
1206 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1209 else if (!n
->profile_id
)
1213 "Node %s has no profile-id"
1214 " (profile feedback missing?)\n",
1218 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1222 "Node %s has IP profile-id %i conflict. "
1224 n
->dump_name (), n
->profile_id
);
1228 cgraph_node_map
->put (n
->profile_id
, n
);
1232 /* Delete the CGRAPH_NODE_MAP. */
1237 delete cgraph_node_map
;
1240 /* Return cgraph node for function with pid */
1243 find_func_by_profile_id (int profile_id
)
1245 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1252 /* Perform sanity check on the indirect call target. Due to race conditions,
1253 false function target may be attributed to an indirect call site. If the
1254 call expression type mismatches with the target function's type, expand_call
1255 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1256 Returns true if TARGET is considered ok for call CALL_STMT. */
1259 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1261 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1264 if (dump_enabled_p ())
1265 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, call_stmt
,
1266 "Skipping target %s with mismatching types for icall\n",
1271 /* Do transformation
1273 if (actual_callee_address == address_of_most_common_function/method)
1280 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1281 profile_probability prob
)
1286 tree tmp0
, tmp1
, tmp
;
1287 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1288 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1289 gimple_stmt_iterator gsi
;
1294 cond_bb
= gimple_bb (icall_stmt
);
1295 gsi
= gsi_for_stmt (icall_stmt
);
1297 tmp0
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1298 tmp1
= make_temp_ssa_name (ptr_type_node
, NULL
, "PROF");
1299 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1300 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1301 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1303 tmp
= fold_convert (ptr_type_node
, build_addr (direct_call
->decl
));
1304 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1305 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1307 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1308 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1310 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1312 unlink_stmt_vdef (icall_stmt
);
1313 release_ssa_name (gimple_vdef (icall_stmt
));
1315 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1316 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1317 update_stmt (icall_stmt
);
1318 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1319 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1320 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1321 if ((dflags
& ECF_NORETURN
) != 0
1322 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1323 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1324 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1327 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1328 e_cd
= split_block (cond_bb
, cond_stmt
);
1329 dcall_bb
= e_cd
->dest
;
1330 dcall_bb
->count
= cond_bb
->count
.apply_probability (prob
);
1332 e_di
= split_block (dcall_bb
, dcall_stmt
);
1333 icall_bb
= e_di
->dest
;
1334 icall_bb
->count
= cond_bb
->count
- dcall_bb
->count
;
1336 /* Do not disturb existing EH edges from the indirect call. */
1337 if (!stmt_ends_bb_p (icall_stmt
))
1338 e_ij
= split_block (icall_bb
, icall_stmt
);
1341 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1342 /* The indirect call might be noreturn. */
1345 e_ij
->probability
= profile_probability::always ();
1346 e_ij
= single_pred_edge (split_edge (e_ij
));
1351 join_bb
= e_ij
->dest
;
1352 join_bb
->count
= cond_bb
->count
;
1355 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1356 e_cd
->probability
= prob
;
1358 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1359 e_ci
->probability
= prob
.invert ();
1365 if ((dflags
& ECF_NORETURN
) == 0)
1367 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1368 e_dj
->probability
= profile_probability::always ();
1370 e_ij
->probability
= profile_probability::always ();
1373 /* Insert PHI node for the call result if necessary. */
1374 if (gimple_call_lhs (icall_stmt
)
1375 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1376 && (dflags
& ECF_NORETURN
) == 0)
1378 tree result
= gimple_call_lhs (icall_stmt
);
1379 gphi
*phi
= create_phi_node (result
, join_bb
);
1380 gimple_call_set_lhs (icall_stmt
,
1381 duplicate_ssa_name (result
, icall_stmt
));
1382 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1383 gimple_call_set_lhs (dcall_stmt
,
1384 duplicate_ssa_name (result
, dcall_stmt
));
1385 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1388 /* Build an EH edge for the direct call if necessary. */
1389 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1390 if (lp_nr
> 0 && stmt_could_throw_p (cfun
, dcall_stmt
))
1392 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1395 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1396 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1398 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1399 e
->probability
= e_eh
->probability
;
1400 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1401 !gsi_end_p (psi
); gsi_next (&psi
))
1403 gphi
*phi
= psi
.phi ();
1404 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1405 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1408 if (!stmt_could_throw_p (cfun
, dcall_stmt
))
1409 gimple_purge_dead_eh_edges (dcall_bb
);
1414 For every checked indirect/virtual call determine if most common pid of
1415 function/class method has probability more than 50%. If yes modify code of
1420 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1423 histogram_value histogram
;
1424 gcov_type val
, count
, all
, bb_all
;
1425 struct cgraph_node
*direct_call
;
1427 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1431 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1434 if (gimple_call_internal_p (stmt
))
1437 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1441 val
= histogram
->hvalue
.counters
[0];
1442 count
= histogram
->hvalue
.counters
[1];
1443 all
= histogram
->hvalue
.counters
[2];
1445 bb_all
= gimple_bb (stmt
)->count
.ipa ().to_gcov_type ();
1446 /* The order of CHECK_COUNTER calls is important -
1447 since check_counter can correct the third parameter
1448 and we want to make count <= all <= bb_all. */
1449 if (check_counter (stmt
, "ic", &all
, &bb_all
, gimple_bb (stmt
)->count
)
1450 || check_counter (stmt
, "ic", &count
, &all
,
1451 profile_count::from_gcov_type (all
)))
1453 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1457 if (4 * count
<= 3 * all
)
1460 direct_call
= find_func_by_profile_id ((int)val
);
1462 if (direct_call
== NULL
)
1468 fprintf (dump_file
, "Indirect call -> direct call from other module");
1469 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1470 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1476 if (!check_ic_target (stmt
, direct_call
))
1480 fprintf (dump_file
, "Indirect call -> direct call ");
1481 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1482 fprintf (dump_file
, "=> ");
1483 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1484 fprintf (dump_file
, " transformation skipped because of type mismatch");
1485 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1487 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1493 fprintf (dump_file
, "Indirect call -> direct call ");
1494 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1495 fprintf (dump_file
, "=> ");
1496 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1497 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1498 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1499 fprintf (dump_file
, "hist->count %" PRId64
1500 " hist->all %" PRId64
"\n", count
, all
);
1506 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1507 set to the argument index for the size of the string operation. */
1510 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1512 enum built_in_function fcode
;
1514 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1517 case BUILT_IN_MEMCPY
:
1518 case BUILT_IN_MEMPCPY
:
1519 case BUILT_IN_MEMMOVE
:
1521 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1522 INTEGER_TYPE
, VOID_TYPE
);
1523 case BUILT_IN_MEMSET
:
1525 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1526 INTEGER_TYPE
, VOID_TYPE
);
1527 case BUILT_IN_BZERO
:
1529 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1536 /* Convert stringop (..., vcall_size)
1538 if (vcall_size == icall_size)
1539 stringop (..., icall_size);
1541 stringop (..., vcall_size);
1542 assuming we'll propagate a true constant into ICALL_SIZE later. */
1545 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, profile_probability prob
,
1546 gcov_type count
, gcov_type all
)
1551 tree tmp0
, tmp1
, vcall_size
, optype
;
1552 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1553 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1554 gimple_stmt_iterator gsi
;
1557 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1560 cond_bb
= gimple_bb (vcall_stmt
);
1561 gsi
= gsi_for_stmt (vcall_stmt
);
1563 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1564 optype
= TREE_TYPE (vcall_size
);
1566 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1567 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1568 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1569 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1571 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1572 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1574 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1575 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1577 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1579 unlink_stmt_vdef (vcall_stmt
);
1580 release_ssa_name (gimple_vdef (vcall_stmt
));
1582 gimple_set_vdef (vcall_stmt
, NULL
);
1583 gimple_set_vuse (vcall_stmt
, NULL
);
1584 update_stmt (vcall_stmt
);
1585 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1586 gimple_call_set_arg (icall_stmt
, size_arg
,
1587 fold_convert (optype
, icall_size
));
1588 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1591 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1592 e_ci
= split_block (cond_bb
, cond_stmt
);
1593 icall_bb
= e_ci
->dest
;
1594 icall_bb
->count
= profile_count::from_gcov_type (count
);
1596 e_iv
= split_block (icall_bb
, icall_stmt
);
1597 vcall_bb
= e_iv
->dest
;
1598 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1600 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1601 join_bb
= e_vj
->dest
;
1602 join_bb
->count
= profile_count::from_gcov_type (all
);
1604 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1605 e_ci
->probability
= prob
;
1607 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1608 e_cv
->probability
= prob
.invert ();
1612 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1613 e_ij
->probability
= profile_probability::always ();
1615 e_vj
->probability
= profile_probability::always ();
1617 /* Insert PHI node for the call result if necessary. */
1618 if (gimple_call_lhs (vcall_stmt
)
1619 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1621 tree result
= gimple_call_lhs (vcall_stmt
);
1622 gphi
*phi
= create_phi_node (result
, join_bb
);
1623 gimple_call_set_lhs (vcall_stmt
,
1624 duplicate_ssa_name (result
, vcall_stmt
));
1625 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1626 gimple_call_set_lhs (icall_stmt
,
1627 duplicate_ssa_name (result
, icall_stmt
));
1628 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1631 /* Because these are all string op builtins, they're all nothrow. */
1632 gcc_assert (!stmt_could_throw_p (cfun
, vcall_stmt
));
1633 gcc_assert (!stmt_could_throw_p (cfun
, icall_stmt
));
1636 /* Find values inside STMT for that we want to measure histograms for
1637 division/modulo optimization. */
1640 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1644 enum built_in_function fcode
;
1645 histogram_value histogram
;
1646 gcov_type count
, all
, val
;
1648 unsigned int dest_align
, src_align
;
1649 profile_probability prob
;
1653 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1657 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1660 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1663 blck_size
= gimple_call_arg (stmt
, size_arg
);
1664 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1667 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1671 val
= histogram
->hvalue
.counters
[0];
1672 count
= histogram
->hvalue
.counters
[1];
1673 all
= histogram
->hvalue
.counters
[2];
1674 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1676 /* We require that count is at least half of all; this means
1677 that for the transformation to fire the value must be constant
1678 at least 80% of time. */
1679 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1681 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1684 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1686 prob
= profile_probability::never ();
1688 dest
= gimple_call_arg (stmt
, 0);
1689 dest_align
= get_pointer_alignment (dest
);
1690 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1693 case BUILT_IN_MEMCPY
:
1694 case BUILT_IN_MEMPCPY
:
1695 case BUILT_IN_MEMMOVE
:
1696 src
= gimple_call_arg (stmt
, 1);
1697 src_align
= get_pointer_alignment (src
);
1698 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1701 case BUILT_IN_MEMSET
:
1702 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1703 gimple_call_arg (stmt
, 1),
1707 case BUILT_IN_BZERO
:
1708 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1717 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1718 tree_val
= build_int_cst (get_gcov_type (), val
);
1722 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1723 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1725 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1726 TYPE_PRECISION (get_gcov_type ()), false));
1731 "Transformation done: single value %i stringop for %s\n",
1732 (int)val
, built_in_names
[(int)fcode
]);
1734 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1740 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1741 HOST_WIDE_INT
*expected_size
)
1743 histogram_value histogram
;
1744 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1747 *expected_size
= -1;
1748 else if (!histogram
->hvalue
.counters
[1])
1750 *expected_size
= -1;
1751 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1756 size
= ((histogram
->hvalue
.counters
[0]
1757 + histogram
->hvalue
.counters
[1] / 2)
1758 / histogram
->hvalue
.counters
[1]);
1759 /* Even if we can hold bigger value in SIZE, INT_MAX
1760 is safe "infinity" for code generation strategies. */
1763 *expected_size
= size
;
1764 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1767 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1770 *expected_align
= 0;
1771 else if (!histogram
->hvalue
.counters
[0])
1773 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1774 *expected_align
= 0;
1779 unsigned int alignment
;
1781 count
= histogram
->hvalue
.counters
[0];
1783 while (!(count
& alignment
)
1784 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1786 *expected_align
= alignment
* BITS_PER_UNIT
;
1787 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1792 /* Find values inside STMT for that we want to measure histograms for
1793 division/modulo optimization. */
1796 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1798 tree lhs
, divisor
, op0
, type
;
1799 histogram_value hist
;
1801 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1804 lhs
= gimple_assign_lhs (stmt
);
1805 type
= TREE_TYPE (lhs
);
1806 if (!INTEGRAL_TYPE_P (type
))
1809 switch (gimple_assign_rhs_code (stmt
))
1811 case TRUNC_DIV_EXPR
:
1812 case TRUNC_MOD_EXPR
:
1813 divisor
= gimple_assign_rhs2 (stmt
);
1814 op0
= gimple_assign_rhs1 (stmt
);
1816 values
->reserve (3);
1818 if (TREE_CODE (divisor
) == SSA_NAME
)
1819 /* Check for the case where the divisor is the same value most
1821 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1822 HIST_TYPE_SINGLE_VALUE
,
1825 /* For mod, check whether it is not often a noop (or replaceable by
1826 a few subtractions). */
1827 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1828 && TYPE_UNSIGNED (type
)
1829 && TREE_CODE (divisor
) == SSA_NAME
)
1832 /* Check for a special case where the divisor is power of 2. */
1833 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1837 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1838 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1840 hist
->hdata
.intvl
.int_start
= 0;
1841 hist
->hdata
.intvl
.steps
= 2;
1842 values
->quick_push (hist
);
1851 /* Find calls inside STMT for that we want to measure histograms for
1852 indirect/virtual call optimization. */
1855 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1859 if (gimple_code (stmt
) != GIMPLE_CALL
1860 || gimple_call_internal_p (stmt
)
1861 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1864 callee
= gimple_call_fn (stmt
);
1866 values
->reserve (3);
1868 values
->quick_push (gimple_alloc_histogram_value (
1870 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1871 HIST_TYPE_INDIR_CALL_TOPN
:
1872 HIST_TYPE_INDIR_CALL
,
1878 /* Find values inside STMT for that we want to measure histograms for
1879 string operations. */
1882 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1889 stmt
= dyn_cast
<gcall
*> (gs
);
1893 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
1896 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1899 dest
= gimple_call_arg (stmt
, 0);
1900 blck_size
= gimple_call_arg (stmt
, size_arg
);
1902 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1904 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1905 HIST_TYPE_SINGLE_VALUE
,
1907 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1911 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1912 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1916 /* Find values inside STMT for that we want to measure histograms and adds
1917 them to list VALUES. */
1920 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1922 gimple_divmod_values_to_profile (stmt
, values
);
1923 gimple_stringops_values_to_profile (stmt
, values
);
1924 gimple_indirect_call_to_profile (stmt
, values
);
1928 gimple_find_values_to_profile (histogram_values
*values
)
1931 gimple_stmt_iterator gsi
;
1933 histogram_value hist
= NULL
;
1936 FOR_EACH_BB_FN (bb
, cfun
)
1937 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1938 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1940 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
1942 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1946 case HIST_TYPE_INTERVAL
:
1947 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1950 case HIST_TYPE_POW2
:
1951 hist
->n_counters
= 2;
1954 case HIST_TYPE_SINGLE_VALUE
:
1955 hist
->n_counters
= 3;
1958 case HIST_TYPE_INDIR_CALL
:
1959 hist
->n_counters
= 3;
1962 case HIST_TYPE_TIME_PROFILE
:
1963 hist
->n_counters
= 1;
1966 case HIST_TYPE_AVERAGE
:
1967 hist
->n_counters
= 2;
1971 hist
->n_counters
= 1;
1974 case HIST_TYPE_INDIR_CALL_TOPN
:
1975 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
1981 if (dump_file
&& hist
->hvalue
.stmt
!= NULL
)
1983 fprintf (dump_file
, "Stmt ");
1984 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1985 dump_histogram_value (dump_file
, hist
);