1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
31 #include "data-streamer.h"
32 #include "diagnostic.h"
33 #include "fold-const.h"
34 #include "tree-nested.h"
37 #include "value-prof.h"
40 #include "gimple-iterator.h"
42 #include "gimple-pretty-print.h"
46 #include "tree-chkp.h"
48 /* In this file value profile based optimizations are placed. Currently the
49 following optimizations are implemented (for more detailed descriptions
50 see comments at value_profile_transformations):
52 1) Division/modulo specialization. Provided that we can determine that the
53 operands of the division have some special properties, we may use it to
54 produce more effective code.
56 2) Indirect/virtual call specialization. If we can determine most
57 common function callee in indirect/virtual call. We can use this
58 information to improve code effectiveness (especially info for
61 3) Speculative prefetching. If we are able to determine that the difference
62 between addresses accessed by a memory reference is usually constant, we
63 may add the prefetch instructions.
64 FIXME: This transformation was removed together with RTL based value
68 Value profiling internals
69 ==========================
71 Every value profiling transformation starts with defining what values
72 to profile. There are different histogram types (see HIST_TYPE_* in
73 value-prof.h) and each transformation can request one or more histogram
74 types per GIMPLE statement. The function gimple_find_values_to_profile()
75 collects the values to profile in a vec, and adds the number of counters
76 required for the different histogram types.
78 For a -fprofile-generate run, the statements for which values should be
79 recorded, are instrumented in instrument_values(). The instrumentation
80 is done by helper functions that can be found in tree-profile.c, where
81 new types of histograms can be added if necessary.
83 After a -fprofile-use, the value profiling data is read back in by
84 compute_value_histograms() that translates the collected data to
85 histograms and attaches them to the profiled statements via
86 gimple_add_histogram_value(). Histograms are stored in a hash table
87 that is attached to every intrumented function, see VALUE_HISTOGRAMS
90 The value-profile transformations driver is the function
91 gimple_value_profile_transformations(). It traverses all statements in
92 the to-be-transformed function, and looks for statements with one or
93 more histograms attached to it. If a statement has histograms, the
94 transformation functions are called on the statement.
96 Limitations / FIXME / TODO:
97 * Only one histogram of each type can be associated with a statement.
98 * Some value profile transformations are done in builtins.c (?!)
99 * Updating of histograms needs some TLC.
100 * The value profiling code could be used to record analysis results
101 from non-profiling (e.g. VRP).
102 * Adding new profilers should be simplified, starting with a cleanup
103 of what-happens-where and with making gimple_find_values_to_profile
104 and gimple_value_profile_transformations table-driven, perhaps...
107 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
108 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
109 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
110 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
111 static bool gimple_ic_transform (gimple_stmt_iterator
*);
113 /* Allocate histogram value. */
116 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
117 enum hist_type type
, gimple
*stmt
, tree value
)
119 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
120 hist
->hvalue
.value
= value
;
121 hist
->hvalue
.stmt
= stmt
;
126 /* Hash value for histogram. */
129 histogram_hash (const void *x
)
131 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
134 /* Return nonzero if statement for histogram_value X is Y. */
137 histogram_eq (const void *x
, const void *y
)
139 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const gimple
*) y
;
142 /* Set histogram for STMT. */
145 set_histogram_value (struct function
*fun
, gimple
*stmt
, histogram_value hist
)
148 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
150 if (!VALUE_HISTOGRAMS (fun
))
151 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
153 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
154 htab_hash_pointer (stmt
),
155 hist
? INSERT
: NO_INSERT
);
159 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
165 /* Get histogram list for STMT. */
168 gimple_histogram_value (struct function
*fun
, gimple
*stmt
)
170 if (!VALUE_HISTOGRAMS (fun
))
172 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
173 htab_hash_pointer (stmt
));
176 /* Add histogram for STMT. */
179 gimple_add_histogram_value (struct function
*fun
, gimple
*stmt
,
180 histogram_value hist
)
182 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
183 set_histogram_value (fun
, stmt
, hist
);
187 /* Remove histogram HIST from STMT's histogram list. */
190 gimple_remove_histogram_value (struct function
*fun
, gimple
*stmt
,
191 histogram_value hist
)
193 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
196 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
200 while (hist2
->hvalue
.next
!= hist
)
201 hist2
= hist2
->hvalue
.next
;
202 hist2
->hvalue
.next
= hist
->hvalue
.next
;
204 free (hist
->hvalue
.counters
);
206 memset (hist
, 0xab, sizeof (*hist
));
210 /* Lookup histogram of type TYPE in the STMT. */
213 gimple_histogram_value_of_type (struct function
*fun
, gimple
*stmt
,
216 histogram_value hist
;
217 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
218 hist
= hist
->hvalue
.next
)
219 if (hist
->type
== type
)
224 /* Dump information about HIST to DUMP_FILE. */
227 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
231 case HIST_TYPE_INTERVAL
:
232 fprintf (dump_file
, "Interval counter range %d -- %d",
233 hist
->hdata
.intvl
.int_start
,
234 (hist
->hdata
.intvl
.int_start
235 + hist
->hdata
.intvl
.steps
- 1));
236 if (hist
->hvalue
.counters
)
239 fprintf (dump_file
, " [");
240 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
241 fprintf (dump_file
, " %d:%" PRId64
,
242 hist
->hdata
.intvl
.int_start
+ i
,
243 (int64_t) hist
->hvalue
.counters
[i
]);
244 fprintf (dump_file
, " ] outside range:%" PRId64
,
245 (int64_t) hist
->hvalue
.counters
[i
]);
247 fprintf (dump_file
, ".\n");
251 fprintf (dump_file
, "Pow2 counter ");
252 if (hist
->hvalue
.counters
)
254 fprintf (dump_file
, "pow2:%" PRId64
256 (int64_t) hist
->hvalue
.counters
[1],
257 (int64_t) hist
->hvalue
.counters
[0]);
259 fprintf (dump_file
, ".\n");
262 case HIST_TYPE_SINGLE_VALUE
:
263 fprintf (dump_file
, "Single value ");
264 if (hist
->hvalue
.counters
)
266 fprintf (dump_file
, "value:%" PRId64
269 (int64_t) hist
->hvalue
.counters
[0],
270 (int64_t) hist
->hvalue
.counters
[1],
271 (int64_t) hist
->hvalue
.counters
[2]);
273 fprintf (dump_file
, ".\n");
276 case HIST_TYPE_AVERAGE
:
277 fprintf (dump_file
, "Average value ");
278 if (hist
->hvalue
.counters
)
280 fprintf (dump_file
, "sum:%" PRId64
282 (int64_t) hist
->hvalue
.counters
[0],
283 (int64_t) hist
->hvalue
.counters
[1]);
285 fprintf (dump_file
, ".\n");
289 fprintf (dump_file
, "IOR value ");
290 if (hist
->hvalue
.counters
)
292 fprintf (dump_file
, "ior:%" PRId64
,
293 (int64_t) hist
->hvalue
.counters
[0]);
295 fprintf (dump_file
, ".\n");
298 case HIST_TYPE_INDIR_CALL
:
299 fprintf (dump_file
, "Indirect call ");
300 if (hist
->hvalue
.counters
)
302 fprintf (dump_file
, "value:%" PRId64
305 (int64_t) hist
->hvalue
.counters
[0],
306 (int64_t) hist
->hvalue
.counters
[1],
307 (int64_t) hist
->hvalue
.counters
[2]);
309 fprintf (dump_file
, ".\n");
311 case HIST_TYPE_TIME_PROFILE
:
312 fprintf (dump_file
, "Time profile ");
313 if (hist
->hvalue
.counters
)
315 fprintf (dump_file
, "time:%" PRId64
,
316 (int64_t) hist
->hvalue
.counters
[0]);
318 fprintf (dump_file
, ".\n");
320 case HIST_TYPE_INDIR_CALL_TOPN
:
321 fprintf (dump_file
, "Indirect call topn ");
322 if (hist
->hvalue
.counters
)
326 fprintf (dump_file
, "accu:%" PRId64
, hist
->hvalue
.counters
[0]);
327 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
329 fprintf (dump_file
, " target:%" PRId64
" value:%" PRId64
,
330 (int64_t) hist
->hvalue
.counters
[i
],
331 (int64_t) hist
->hvalue
.counters
[i
+1]);
334 fprintf (dump_file
, ".\n");
341 /* Dump information about HIST to DUMP_FILE. */
344 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
349 bp
= bitpack_create (ob
->main_stream
);
350 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
351 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
352 streamer_write_bitpack (&bp
);
355 case HIST_TYPE_INTERVAL
:
356 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
357 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
362 for (i
= 0; i
< hist
->n_counters
; i
++)
364 /* When user uses an unsigned type with a big value, constant converted
365 to gcov_type (a signed type) can be negative. */
366 gcov_type value
= hist
->hvalue
.counters
[i
];
367 if (hist
->type
== HIST_TYPE_SINGLE_VALUE
&& i
== 0)
370 gcc_assert (value
>= 0);
372 streamer_write_gcov_count (ob
, value
);
374 if (hist
->hvalue
.next
)
375 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
378 /* Dump information about HIST to DUMP_FILE. */
381 stream_in_histogram_value (struct lto_input_block
*ib
, gimple
*stmt
)
384 unsigned int ncounters
= 0;
387 histogram_value new_val
;
389 histogram_value
*next_p
= NULL
;
393 bp
= streamer_read_bitpack (ib
);
394 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
395 next
= bp_unpack_value (&bp
, 1);
396 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
399 case HIST_TYPE_INTERVAL
:
400 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
401 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
402 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
406 case HIST_TYPE_AVERAGE
:
410 case HIST_TYPE_SINGLE_VALUE
:
411 case HIST_TYPE_INDIR_CALL
:
416 case HIST_TYPE_TIME_PROFILE
:
420 case HIST_TYPE_INDIR_CALL_TOPN
:
421 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
427 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
428 new_val
->n_counters
= ncounters
;
429 for (i
= 0; i
< ncounters
; i
++)
430 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
432 gimple_add_histogram_value (cfun
, stmt
, new_val
);
435 next_p
= &new_val
->hvalue
.next
;
440 /* Dump all histograms attached to STMT to DUMP_FILE. */
443 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
445 histogram_value hist
;
446 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
447 dump_histogram_value (dump_file
, hist
);
450 /* Remove all histograms associated with STMT. */
453 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
456 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
457 gimple_remove_histogram_value (fun
, stmt
, val
);
460 /* Duplicate all histograms associates with OSTMT to STMT. */
463 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
464 struct function
*ofun
, gimple
*ostmt
)
467 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
469 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
470 memcpy (new_val
, val
, sizeof (*val
));
471 new_val
->hvalue
.stmt
= stmt
;
472 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
473 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
474 gimple_add_histogram_value (fun
, stmt
, new_val
);
478 /* Move all histograms associated with OSTMT to STMT. */
481 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
483 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
486 /* The following three statements can't be reordered,
487 because histogram hashtab relies on stmt field value
488 for finding the exact slot. */
489 set_histogram_value (fun
, ostmt
, NULL
);
490 for (; val
!= NULL
; val
= val
->hvalue
.next
)
491 val
->hvalue
.stmt
= stmt
;
492 set_histogram_value (fun
, stmt
, val
);
496 static bool error_found
= false;
498 /* Helper function for verify_histograms. For each histogram reachable via htab
499 walk verify that it was reached via statement walk. */
502 visit_hist (void **slot
, void *data
)
504 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
505 histogram_value hist
= *(histogram_value
*) slot
;
507 if (!visited
->contains (hist
)
508 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
510 error ("dead histogram");
511 dump_histogram_value (stderr
, hist
);
512 debug_gimple_stmt (hist
->hvalue
.stmt
);
518 /* Verify sanity of the histograms. */
521 verify_histograms (void)
524 gimple_stmt_iterator gsi
;
525 histogram_value hist
;
528 hash_set
<histogram_value
> visited_hists
;
529 FOR_EACH_BB_FN (bb
, cfun
)
530 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
532 gimple
*stmt
= gsi_stmt (gsi
);
534 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
535 hist
= hist
->hvalue
.next
)
537 if (hist
->hvalue
.stmt
!= stmt
)
539 error ("Histogram value statement does not correspond to "
540 "the statement it is associated with");
541 debug_gimple_stmt (stmt
);
542 dump_histogram_value (stderr
, hist
);
545 visited_hists
.add (hist
);
548 if (VALUE_HISTOGRAMS (cfun
))
549 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
551 internal_error ("verify_histograms failed");
554 /* Helper function for verify_histograms. For each histogram reachable via htab
555 walk verify that it was reached via statement walk. */
558 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
560 histogram_value hist
= *(histogram_value
*) slot
;
561 free (hist
->hvalue
.counters
);
567 free_histograms (struct function
*fn
)
569 if (VALUE_HISTOGRAMS (fn
))
571 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
572 htab_delete (VALUE_HISTOGRAMS (fn
));
573 VALUE_HISTOGRAMS (fn
) = NULL
;
577 /* The overall number of invocations of the counter should match
578 execution count of basic block. Report it as error rather than
579 internal error as it might mean that user has misused the profile
583 check_counter (gimple
*stmt
, const char * name
,
584 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
586 gcov_type bb_count
= bb_count_d
.to_gcov_type ();
587 if (*all
!= bb_count
|| *count
> *all
)
590 locus
= (stmt
!= NULL
)
591 ? gimple_location (stmt
)
592 : DECL_SOURCE_LOCATION (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
, "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
);
684 /* Generate code for transformation 1 (with parent gimple assignment
685 STMT and probability of taking the optimal path PROB, which is
686 equivalent to COUNT/ALL within roundoff error). This generates the
687 result into a temp and returns the temp; it does not replace or
688 alter the original STMT. */
691 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, profile_probability prob
,
692 gcov_type count
, gcov_type all
)
694 gassign
*stmt1
, *stmt2
;
696 tree tmp0
, tmp1
, tmp2
;
697 gimple
*bb1end
, *bb2end
, *bb3end
;
698 basic_block bb
, bb2
, bb3
, bb4
;
699 tree optype
, op1
, op2
;
700 edge e12
, e13
, e23
, e24
, e34
;
701 gimple_stmt_iterator gsi
;
703 gcc_assert (is_gimple_assign (stmt
)
704 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
705 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
707 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
708 op1
= gimple_assign_rhs1 (stmt
);
709 op2
= gimple_assign_rhs2 (stmt
);
711 bb
= gimple_bb (stmt
);
712 gsi
= gsi_for_stmt (stmt
);
714 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
715 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
716 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
717 stmt2
= gimple_build_assign (tmp1
, op2
);
718 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
719 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
720 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
721 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
724 tmp2
= create_tmp_reg (optype
, "PROF");
725 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
726 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
729 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
730 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
734 /* Edge e23 connects bb2 to bb3, etc. */
735 e12
= split_block (bb
, bb1end
);
737 bb2
->count
= profile_count::from_gcov_type (count
);
738 e23
= split_block (bb2
, bb2end
);
740 bb3
->count
= profile_count::from_gcov_type (all
- count
);
741 e34
= split_block (bb3
, bb3end
);
743 bb4
->count
= profile_count::from_gcov_type (all
);
745 e12
->flags
&= ~EDGE_FALLTHRU
;
746 e12
->flags
|= EDGE_FALSE_VALUE
;
747 e12
->probability
= prob
;
749 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
750 e13
->probability
= prob
.invert ();
754 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
755 e24
->probability
= profile_probability::always ();
757 e34
->probability
= profile_probability::always ();
762 /* Do transform 1) on INSN if applicable. */
765 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
767 histogram_value histogram
;
769 gcov_type val
, count
, all
;
770 tree result
, value
, tree_val
;
771 profile_probability prob
;
774 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
778 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
781 code
= gimple_assign_rhs_code (stmt
);
783 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
786 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
787 HIST_TYPE_SINGLE_VALUE
);
791 value
= histogram
->hvalue
.value
;
792 val
= histogram
->hvalue
.counters
[0];
793 count
= histogram
->hvalue
.counters
[1];
794 all
= histogram
->hvalue
.counters
[2];
795 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
797 /* We require that count is at least half of all; this means
798 that for the transformation to fire the value must be constant
799 at least 50% of time (and 75% gives the guarantee of usage). */
800 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
802 || optimize_bb_for_size_p (gimple_bb (stmt
)))
805 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
808 /* Compute probability of taking the optimal path. */
810 prob
= profile_probability::probability_in_gcov_type (count
, all
);
812 prob
= profile_probability::never ();
814 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
815 tree_val
= build_int_cst (get_gcov_type (), val
);
819 a
[0] = (unsigned HOST_WIDE_INT
) val
;
820 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
822 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
823 TYPE_PRECISION (get_gcov_type ()), false));
825 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
829 fprintf (dump_file
, "Div/mod by constant ");
830 print_generic_expr (dump_file
, value
, TDF_SLIM
);
831 fprintf (dump_file
, "=");
832 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
833 fprintf (dump_file
, " transformation on insn ");
834 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
837 gimple_assign_set_rhs_from_tree (si
, result
);
838 update_stmt (gsi_stmt (*si
));
843 /* Generate code for transformation 2 (with parent gimple assign STMT and
844 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
845 within roundoff error). This generates the result into a temp and returns
846 the temp; it does not replace or alter the original STMT. */
849 gimple_mod_pow2 (gassign
*stmt
, profile_probability prob
, gcov_type count
, gcov_type all
)
851 gassign
*stmt1
, *stmt2
, *stmt3
;
854 gimple
*bb1end
, *bb2end
, *bb3end
;
855 basic_block bb
, bb2
, bb3
, bb4
;
856 tree optype
, op1
, op2
;
857 edge e12
, e13
, e23
, e24
, e34
;
858 gimple_stmt_iterator gsi
;
861 gcc_assert (is_gimple_assign (stmt
)
862 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
864 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
865 op1
= gimple_assign_rhs1 (stmt
);
866 op2
= gimple_assign_rhs2 (stmt
);
868 bb
= gimple_bb (stmt
);
869 gsi
= gsi_for_stmt (stmt
);
871 result
= create_tmp_reg (optype
, "PROF");
872 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
873 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
874 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
875 build_int_cst (optype
, -1));
876 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
877 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
878 NULL_TREE
, NULL_TREE
);
879 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
880 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
881 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
884 /* tmp2 == op2-1 inherited from previous block. */
885 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
886 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
889 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
891 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
895 /* Edge e23 connects bb2 to bb3, etc. */
896 e12
= split_block (bb
, bb1end
);
898 bb2
->count
= profile_count::from_gcov_type (count
);
899 e23
= split_block (bb2
, bb2end
);
901 bb3
->count
= profile_count::from_gcov_type (all
- count
);
902 e34
= split_block (bb3
, bb3end
);
904 bb4
->count
= profile_count::from_gcov_type (all
);
906 e12
->flags
&= ~EDGE_FALLTHRU
;
907 e12
->flags
|= EDGE_FALSE_VALUE
;
908 e12
->probability
= prob
;
910 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
911 e13
->probability
= prob
.invert ();
915 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
916 e24
->probability
= profile_probability::always ();
918 e34
->probability
= profile_probability::always ();
923 /* Do transform 2) on INSN if applicable. */
926 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
928 histogram_value histogram
;
930 gcov_type count
, wrong_values
, all
;
931 tree lhs_type
, result
, value
;
932 profile_probability prob
;
935 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
939 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
940 if (!INTEGRAL_TYPE_P (lhs_type
))
943 code
= gimple_assign_rhs_code (stmt
);
945 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
948 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
952 value
= histogram
->hvalue
.value
;
953 wrong_values
= histogram
->hvalue
.counters
[0];
954 count
= histogram
->hvalue
.counters
[1];
956 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
958 /* We require that we hit a power of 2 at least half of all evaluations. */
959 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
960 || count
< wrong_values
961 || optimize_bb_for_size_p (gimple_bb (stmt
)))
966 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
967 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
970 /* Compute probability of taking the optimal path. */
971 all
= count
+ wrong_values
;
973 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
977 prob
= profile_probability::probability_in_gcov_type (count
, all
);
979 prob
= profile_probability::never ();
981 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
983 gimple_assign_set_rhs_from_tree (si
, result
);
984 update_stmt (gsi_stmt (*si
));
989 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
990 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
991 supported and this is built into this interface. The probabilities of taking
992 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
993 COUNT2/ALL respectively within roundoff error). This generates the
994 result into a temp and returns the temp; it does not replace or alter
995 the original STMT. */
996 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
999 gimple_mod_subtract (gassign
*stmt
, profile_probability prob1
,
1000 profile_probability prob2
, int ncounts
,
1001 gcov_type count1
, gcov_type count2
, gcov_type all
)
1007 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
1008 basic_block bb
, bb2
, bb3
, bb4
;
1009 tree optype
, op1
, op2
;
1010 edge e12
, e23
= 0, e24
, e34
, e14
;
1011 gimple_stmt_iterator gsi
;
1014 gcc_assert (is_gimple_assign (stmt
)
1015 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1017 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1018 op1
= gimple_assign_rhs1 (stmt
);
1019 op2
= gimple_assign_rhs2 (stmt
);
1021 bb
= gimple_bb (stmt
);
1022 gsi
= gsi_for_stmt (stmt
);
1024 result
= create_tmp_reg (optype
, "PROF");
1025 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1026 stmt1
= gimple_build_assign (result
, op1
);
1027 stmt2
= gimple_build_assign (tmp1
, op2
);
1028 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1029 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1030 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1031 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1034 if (ncounts
) /* Assumed to be 0 or 1 */
1036 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1037 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1038 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1039 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1043 /* Fallback case. */
1044 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1046 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1050 /* Edge e23 connects bb2 to bb3, etc. */
1051 /* However block 3 is optional; if it is not there, references
1052 to 3 really refer to block 2. */
1053 e12
= split_block (bb
, bb1end
);
1055 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1057 if (ncounts
) /* Assumed to be 0 or 1. */
1059 e23
= split_block (bb2
, bb2end
);
1061 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1064 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1066 bb4
->count
= profile_count::from_gcov_type (all
);
1068 e12
->flags
&= ~EDGE_FALLTHRU
;
1069 e12
->flags
|= EDGE_FALSE_VALUE
;
1070 e12
->probability
= prob1
.invert ();
1072 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1073 e14
->probability
= prob1
;
1075 if (ncounts
) /* Assumed to be 0 or 1. */
1077 e23
->flags
&= ~EDGE_FALLTHRU
;
1078 e23
->flags
|= EDGE_FALSE_VALUE
;
1079 e23
->probability
= prob2
.invert ();
1081 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1082 e24
->probability
= prob2
;
1085 e34
->probability
= profile_probability::always ();
1090 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1093 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1095 histogram_value histogram
;
1096 enum tree_code code
;
1097 gcov_type count
, wrong_values
, all
;
1098 tree lhs_type
, result
;
1099 profile_probability prob1
, prob2
;
1100 unsigned int i
, steps
;
1101 gcov_type count1
, count2
;
1103 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1107 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1108 if (!INTEGRAL_TYPE_P (lhs_type
))
1111 code
= gimple_assign_rhs_code (stmt
);
1113 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1116 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1122 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1123 all
+= histogram
->hvalue
.counters
[i
];
1125 wrong_values
+= histogram
->hvalue
.counters
[i
];
1126 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1127 steps
= histogram
->hdata
.intvl
.steps
;
1128 all
+= wrong_values
;
1129 count1
= histogram
->hvalue
.counters
[0];
1130 count2
= histogram
->hvalue
.counters
[1];
1132 /* Compute probability of taking the optimal path. */
1133 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1135 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1139 if (flag_profile_correction
&& count1
+ count2
> all
)
1140 all
= count1
+ count2
;
1142 gcc_assert (count1
+ count2
<= all
);
1144 /* We require that we use just subtractions in at least 50% of all
1147 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1149 count
+= histogram
->hvalue
.counters
[i
];
1150 if (count
* 2 >= all
)
1154 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1157 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1160 fprintf (dump_file
, "Mod subtract transformation on insn ");
1161 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1164 /* Compute probability of taking the optimal path(s). */
1167 prob1
= profile_probability::probability_in_gcov_type (count1
, all
);
1168 prob2
= profile_probability::probability_in_gcov_type (count2
, all
);
1172 prob1
= prob2
= profile_probability::never ();
1175 /* In practice, "steps" is always 2. This interface reflects this,
1176 and will need to be changed if "steps" can change. */
1177 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1179 gimple_assign_set_rhs_from_tree (si
, result
);
1180 update_stmt (gsi_stmt (*si
));
1185 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1187 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1189 /* Returns true if node graph is initialized. This
1190 is used to test if profile_id has been created
1191 for cgraph_nodes. */
1194 coverage_node_map_initialized_p (void)
1196 return cgraph_node_map
!= 0;
1199 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1200 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1201 that the PROFILE_IDs was already assigned. */
1204 init_node_map (bool local
)
1206 struct cgraph_node
*n
;
1207 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1209 FOR_EACH_DEFINED_FUNCTION (n
)
1210 if (n
->has_gimple_body_p ())
1215 n
->profile_id
= coverage_compute_profile_id (n
);
1216 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1220 fprintf (dump_file
, "Local profile-id %i conflict"
1221 " with nodes %s %s\n",
1224 (*val
)->dump_name ());
1225 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1228 else if (!n
->profile_id
)
1232 "Node %s has no profile-id"
1233 " (profile feedback missing?)\n",
1237 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1241 "Node %s has IP profile-id %i conflict. "
1243 n
->dump_name (), n
->profile_id
);
1247 cgraph_node_map
->put (n
->profile_id
, n
);
1251 /* Delete the CGRAPH_NODE_MAP. */
1256 delete cgraph_node_map
;
1259 /* Return cgraph node for function with pid */
1262 find_func_by_profile_id (int profile_id
)
1264 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1271 /* Perform sanity check on the indirect call target. Due to race conditions,
1272 false function target may be attributed to an indirect call site. If the
1273 call expression type mismatches with the target function's type, expand_call
1274 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1275 Returns true if TARGET is considered ok for call CALL_STMT. */
1278 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1281 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1284 locus
= gimple_location (call_stmt
);
1285 if (dump_enabled_p ())
1286 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1287 "Skipping target %s with mismatching types for icall\n",
1292 /* Do transformation
1294 if (actual_callee_address == address_of_most_common_function/method)
1301 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1302 profile_probability prob
, profile_count count
, profile_count all
)
1307 gcall
*iretbnd_stmt
= NULL
;
1308 tree tmp0
, tmp1
, tmp
;
1309 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1310 tree optype
= build_pointer_type (void_type_node
);
1311 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1312 gimple_stmt_iterator gsi
;
1316 gimple_stmt_iterator psi
;
1318 cond_bb
= gimple_bb (icall_stmt
);
1319 gsi
= gsi_for_stmt (icall_stmt
);
1321 if (gimple_call_with_bounds_p (icall_stmt
) && gimple_call_lhs (icall_stmt
))
1322 iretbnd_stmt
= chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt
));
1324 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1325 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1326 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1327 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1328 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1330 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
));
1331 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1332 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1334 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1335 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1337 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1339 unlink_stmt_vdef (icall_stmt
);
1340 release_ssa_name (gimple_vdef (icall_stmt
));
1342 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1343 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1344 update_stmt (icall_stmt
);
1345 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1346 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1347 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1348 if ((dflags
& ECF_NORETURN
) != 0
1349 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1350 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1351 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1354 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1355 e_cd
= split_block (cond_bb
, cond_stmt
);
1356 dcall_bb
= e_cd
->dest
;
1357 dcall_bb
->count
= count
;
1359 e_di
= split_block (dcall_bb
, dcall_stmt
);
1360 icall_bb
= e_di
->dest
;
1361 icall_bb
->count
= all
- count
;
1363 /* Do not disturb existing EH edges from the indirect call. */
1364 if (!stmt_ends_bb_p (icall_stmt
))
1365 e_ij
= split_block (icall_bb
, icall_stmt
);
1368 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1369 /* The indirect call might be noreturn. */
1372 e_ij
->probability
= profile_probability::always ();
1373 e_ij
= single_pred_edge (split_edge (e_ij
));
1378 join_bb
= e_ij
->dest
;
1379 join_bb
->count
= all
;
1382 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1383 e_cd
->probability
= prob
;
1385 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1386 e_ci
->probability
= prob
.invert ();
1392 if ((dflags
& ECF_NORETURN
) == 0)
1394 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1395 e_dj
->probability
= profile_probability::always ();
1397 e_ij
->probability
= profile_probability::always ();
1400 /* Insert PHI node for the call result if necessary. */
1401 if (gimple_call_lhs (icall_stmt
)
1402 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1403 && (dflags
& ECF_NORETURN
) == 0)
1405 tree result
= gimple_call_lhs (icall_stmt
);
1406 gphi
*phi
= create_phi_node (result
, join_bb
);
1407 gimple_call_set_lhs (icall_stmt
,
1408 duplicate_ssa_name (result
, icall_stmt
));
1409 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1410 gimple_call_set_lhs (dcall_stmt
,
1411 duplicate_ssa_name (result
, dcall_stmt
));
1412 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1414 /* If indirect call has following BUILT_IN_CHKP_BNDRET
1415 call then we need to make it's copy for the direct
1419 if (gimple_call_lhs (iretbnd_stmt
))
1423 if (TREE_CODE (gimple_vdef (iretbnd_stmt
)) == SSA_NAME
)
1425 unlink_stmt_vdef (iretbnd_stmt
);
1426 release_ssa_name (gimple_vdef (iretbnd_stmt
));
1428 gimple_set_vdef (iretbnd_stmt
, NULL_TREE
);
1429 gimple_set_vuse (iretbnd_stmt
, NULL_TREE
);
1430 update_stmt (iretbnd_stmt
);
1432 result
= gimple_call_lhs (iretbnd_stmt
);
1433 phi
= create_phi_node (result
, join_bb
);
1435 copy
= gimple_copy (iretbnd_stmt
);
1436 gimple_call_set_arg (copy
, 0,
1437 gimple_call_lhs (dcall_stmt
));
1438 gimple_call_set_lhs (copy
, duplicate_ssa_name (result
, copy
));
1439 gsi_insert_on_edge (e_dj
, copy
);
1440 add_phi_arg (phi
, gimple_call_lhs (copy
),
1441 e_dj
, UNKNOWN_LOCATION
);
1443 gimple_call_set_arg (iretbnd_stmt
, 0,
1444 gimple_call_lhs (icall_stmt
));
1445 gimple_call_set_lhs (iretbnd_stmt
,
1446 duplicate_ssa_name (result
, iretbnd_stmt
));
1447 psi
= gsi_for_stmt (iretbnd_stmt
);
1448 gsi_remove (&psi
, false);
1449 gsi_insert_on_edge (e_ij
, iretbnd_stmt
);
1450 add_phi_arg (phi
, gimple_call_lhs (iretbnd_stmt
),
1451 e_ij
, UNKNOWN_LOCATION
);
1453 gsi_commit_one_edge_insert (e_dj
, NULL
);
1454 gsi_commit_one_edge_insert (e_ij
, NULL
);
1458 psi
= gsi_for_stmt (iretbnd_stmt
);
1459 gsi_remove (&psi
, true);
1464 /* Build an EH edge for the direct call if necessary. */
1465 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1466 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1468 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1471 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1472 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1474 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1475 e
->probability
= e_eh
->probability
;
1476 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1477 !gsi_end_p (psi
); gsi_next (&psi
))
1479 gphi
*phi
= psi
.phi ();
1480 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1481 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1484 if (!stmt_could_throw_p (dcall_stmt
))
1485 gimple_purge_dead_eh_edges (dcall_bb
);
1490 For every checked indirect/virtual call determine if most common pid of
1491 function/class method has probability more than 50%. If yes modify code of
1496 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1499 histogram_value histogram
;
1500 gcov_type val
, count
, all
, bb_all
;
1501 struct cgraph_node
*direct_call
;
1503 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1507 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1510 if (gimple_call_internal_p (stmt
))
1513 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1517 val
= histogram
->hvalue
.counters
[0];
1518 count
= histogram
->hvalue
.counters
[1];
1519 all
= histogram
->hvalue
.counters
[2];
1521 bb_all
= gimple_bb (stmt
)->count
.to_gcov_type ();
1522 /* The order of CHECK_COUNTER calls is important -
1523 since check_counter can correct the third parameter
1524 and we want to make count <= all <= bb_all. */
1525 if (check_counter (stmt
, "ic", &all
, &bb_all
, gimple_bb (stmt
)->count
)
1526 || check_counter (stmt
, "ic", &count
, &all
,
1527 profile_count::from_gcov_type (all
)))
1529 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1533 if (4 * count
<= 3 * all
)
1536 direct_call
= find_func_by_profile_id ((int)val
);
1538 if (direct_call
== NULL
)
1544 fprintf (dump_file
, "Indirect call -> direct call from other module");
1545 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1546 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1552 if (!check_ic_target (stmt
, direct_call
))
1556 fprintf (dump_file
, "Indirect call -> direct call ");
1557 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1558 fprintf (dump_file
, "=> ");
1559 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1560 fprintf (dump_file
, " transformation skipped because of type mismatch");
1561 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1563 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1569 fprintf (dump_file
, "Indirect call -> direct call ");
1570 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1571 fprintf (dump_file
, "=> ");
1572 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1573 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1574 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1575 fprintf (dump_file
, "hist->count %" PRId64
1576 " hist->all %" PRId64
"\n", count
, all
);
1582 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1583 set to the argument index for the size of the string operation. */
1586 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1588 enum built_in_function fcode
;
1590 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1591 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1592 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1597 case BUILT_IN_MEMCPY
:
1598 case BUILT_IN_MEMPCPY
:
1600 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1601 INTEGER_TYPE
, VOID_TYPE
);
1602 case BUILT_IN_MEMSET
:
1604 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1605 INTEGER_TYPE
, VOID_TYPE
);
1606 case BUILT_IN_BZERO
:
1608 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1615 /* Convert stringop (..., vcall_size)
1617 if (vcall_size == icall_size)
1618 stringop (..., icall_size);
1620 stringop (..., vcall_size);
1621 assuming we'll propagate a true constant into ICALL_SIZE later. */
1624 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, profile_probability prob
,
1625 gcov_type count
, gcov_type all
)
1630 tree tmp0
, tmp1
, vcall_size
, optype
;
1631 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1632 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1633 gimple_stmt_iterator gsi
;
1636 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1639 cond_bb
= gimple_bb (vcall_stmt
);
1640 gsi
= gsi_for_stmt (vcall_stmt
);
1642 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1643 optype
= TREE_TYPE (vcall_size
);
1645 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1646 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1647 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1648 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1650 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1651 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1653 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1654 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1656 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1658 unlink_stmt_vdef (vcall_stmt
);
1659 release_ssa_name (gimple_vdef (vcall_stmt
));
1661 gimple_set_vdef (vcall_stmt
, NULL
);
1662 gimple_set_vuse (vcall_stmt
, NULL
);
1663 update_stmt (vcall_stmt
);
1664 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1665 gimple_call_set_arg (icall_stmt
, size_arg
,
1666 fold_convert (optype
, icall_size
));
1667 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1670 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1671 e_ci
= split_block (cond_bb
, cond_stmt
);
1672 icall_bb
= e_ci
->dest
;
1673 icall_bb
->count
= profile_count::from_gcov_type (count
);
1675 e_iv
= split_block (icall_bb
, icall_stmt
);
1676 vcall_bb
= e_iv
->dest
;
1677 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1679 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1680 join_bb
= e_vj
->dest
;
1681 join_bb
->count
= profile_count::from_gcov_type (all
);
1683 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1684 e_ci
->probability
= prob
;
1686 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1687 e_cv
->probability
= prob
.invert ();
1691 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1692 e_ij
->probability
= profile_probability::always ();
1694 e_vj
->probability
= profile_probability::always ();
1696 /* Insert PHI node for the call result if necessary. */
1697 if (gimple_call_lhs (vcall_stmt
)
1698 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1700 tree result
= gimple_call_lhs (vcall_stmt
);
1701 gphi
*phi
= create_phi_node (result
, join_bb
);
1702 gimple_call_set_lhs (vcall_stmt
,
1703 duplicate_ssa_name (result
, vcall_stmt
));
1704 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1705 gimple_call_set_lhs (icall_stmt
,
1706 duplicate_ssa_name (result
, icall_stmt
));
1707 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1710 /* Because these are all string op builtins, they're all nothrow. */
1711 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1712 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1715 /* Find values inside STMT for that we want to measure histograms for
1716 division/modulo optimization. */
1719 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1723 enum built_in_function fcode
;
1724 histogram_value histogram
;
1725 gcov_type count
, all
, val
;
1727 unsigned int dest_align
, src_align
;
1728 profile_probability prob
;
1732 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1736 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1739 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1742 blck_size
= gimple_call_arg (stmt
, size_arg
);
1743 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1746 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1750 val
= histogram
->hvalue
.counters
[0];
1751 count
= histogram
->hvalue
.counters
[1];
1752 all
= histogram
->hvalue
.counters
[2];
1753 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1755 /* We require that count is at least half of all; this means
1756 that for the transformation to fire the value must be constant
1757 at least 80% of time. */
1758 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1760 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1763 prob
= profile_probability::probability_in_gcov_type (count
, all
);
1765 prob
= profile_probability::never ();
1767 dest
= gimple_call_arg (stmt
, 0);
1768 dest_align
= get_pointer_alignment (dest
);
1769 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1772 case BUILT_IN_MEMCPY
:
1773 case BUILT_IN_MEMPCPY
:
1774 src
= gimple_call_arg (stmt
, 1);
1775 src_align
= get_pointer_alignment (src
);
1776 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1779 case BUILT_IN_MEMSET
:
1780 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1781 gimple_call_arg (stmt
, 1),
1785 case BUILT_IN_BZERO
:
1786 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1795 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1796 tree_val
= build_int_cst (get_gcov_type (), val
);
1800 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1801 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1803 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1804 TYPE_PRECISION (get_gcov_type ()), false));
1809 fprintf (dump_file
, "Single value %i stringop transformation on ",
1811 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1814 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1820 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1821 HOST_WIDE_INT
*expected_size
)
1823 histogram_value histogram
;
1824 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1827 *expected_size
= -1;
1828 else if (!histogram
->hvalue
.counters
[1])
1830 *expected_size
= -1;
1831 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1836 size
= ((histogram
->hvalue
.counters
[0]
1837 + histogram
->hvalue
.counters
[1] / 2)
1838 / histogram
->hvalue
.counters
[1]);
1839 /* Even if we can hold bigger value in SIZE, INT_MAX
1840 is safe "infinity" for code generation strategies. */
1843 *expected_size
= size
;
1844 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1847 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1850 *expected_align
= 0;
1851 else if (!histogram
->hvalue
.counters
[0])
1853 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1854 *expected_align
= 0;
1859 unsigned int alignment
;
1861 count
= histogram
->hvalue
.counters
[0];
1863 while (!(count
& alignment
)
1864 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1866 *expected_align
= alignment
* BITS_PER_UNIT
;
1867 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1872 /* Find values inside STMT for that we want to measure histograms for
1873 division/modulo optimization. */
1876 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1878 tree lhs
, divisor
, op0
, type
;
1879 histogram_value hist
;
1881 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1884 lhs
= gimple_assign_lhs (stmt
);
1885 type
= TREE_TYPE (lhs
);
1886 if (!INTEGRAL_TYPE_P (type
))
1889 switch (gimple_assign_rhs_code (stmt
))
1891 case TRUNC_DIV_EXPR
:
1892 case TRUNC_MOD_EXPR
:
1893 divisor
= gimple_assign_rhs2 (stmt
);
1894 op0
= gimple_assign_rhs1 (stmt
);
1896 values
->reserve (3);
1898 if (TREE_CODE (divisor
) == SSA_NAME
)
1899 /* Check for the case where the divisor is the same value most
1901 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1902 HIST_TYPE_SINGLE_VALUE
,
1905 /* For mod, check whether it is not often a noop (or replaceable by
1906 a few subtractions). */
1907 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1908 && TYPE_UNSIGNED (type
)
1909 && TREE_CODE (divisor
) == SSA_NAME
)
1912 /* Check for a special case where the divisor is power of 2. */
1913 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1917 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1918 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1920 hist
->hdata
.intvl
.int_start
= 0;
1921 hist
->hdata
.intvl
.steps
= 2;
1922 values
->quick_push (hist
);
1931 /* Find calls inside STMT for that we want to measure histograms for
1932 indirect/virtual call optimization. */
1935 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1939 if (gimple_code (stmt
) != GIMPLE_CALL
1940 || gimple_call_internal_p (stmt
)
1941 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1944 callee
= gimple_call_fn (stmt
);
1946 values
->reserve (3);
1948 values
->quick_push (gimple_alloc_histogram_value (
1950 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1951 HIST_TYPE_INDIR_CALL_TOPN
:
1952 HIST_TYPE_INDIR_CALL
,
1958 /* Find values inside STMT for that we want to measure histograms for
1959 string operations. */
1962 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1969 stmt
= dyn_cast
<gcall
*> (gs
);
1973 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
1976 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1979 dest
= gimple_call_arg (stmt
, 0);
1980 blck_size
= gimple_call_arg (stmt
, size_arg
);
1982 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1984 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1985 HIST_TYPE_SINGLE_VALUE
,
1987 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1991 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1992 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1996 /* Find values inside STMT for that we want to measure histograms and adds
1997 them to list VALUES. */
2000 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
2002 gimple_divmod_values_to_profile (stmt
, values
);
2003 gimple_stringops_values_to_profile (stmt
, values
);
2004 gimple_indirect_call_to_profile (stmt
, values
);
2008 gimple_find_values_to_profile (histogram_values
*values
)
2011 gimple_stmt_iterator gsi
;
2013 histogram_value hist
= NULL
;
2016 FOR_EACH_BB_FN (bb
, cfun
)
2017 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2018 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2020 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2022 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2026 case HIST_TYPE_INTERVAL
:
2027 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2030 case HIST_TYPE_POW2
:
2031 hist
->n_counters
= 2;
2034 case HIST_TYPE_SINGLE_VALUE
:
2035 hist
->n_counters
= 3;
2038 case HIST_TYPE_INDIR_CALL
:
2039 hist
->n_counters
= 3;
2042 case HIST_TYPE_TIME_PROFILE
:
2043 hist
->n_counters
= 1;
2046 case HIST_TYPE_AVERAGE
:
2047 hist
->n_counters
= 2;
2051 hist
->n_counters
= 1;
2054 case HIST_TYPE_INDIR_CALL_TOPN
:
2055 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2063 fprintf (dump_file
, "Stmt ");
2064 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2065 dump_histogram_value (dump_file
, hist
);