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 tree
gimple_divmod_fixed_value (gassign
*, tree
, int, gcov_type
,
109 static tree
gimple_mod_pow2 (gassign
*, int, gcov_type
, gcov_type
);
110 static tree
gimple_mod_subtract (gassign
*, int, int, int, gcov_type
,
111 gcov_type
, gcov_type
);
112 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
113 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
114 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
115 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
116 static bool gimple_ic_transform (gimple_stmt_iterator
*);
118 /* Allocate histogram value. */
121 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
122 enum hist_type type
, gimple
*stmt
, tree value
)
124 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
125 hist
->hvalue
.value
= value
;
126 hist
->hvalue
.stmt
= stmt
;
131 /* Hash value for histogram. */
134 histogram_hash (const void *x
)
136 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
139 /* Return nonzero if statement for histogram_value X is Y. */
142 histogram_eq (const void *x
, const void *y
)
144 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const gimple
*) y
;
147 /* Set histogram for STMT. */
150 set_histogram_value (struct function
*fun
, gimple
*stmt
, histogram_value hist
)
153 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
155 if (!VALUE_HISTOGRAMS (fun
))
156 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
158 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
159 htab_hash_pointer (stmt
),
160 hist
? INSERT
: NO_INSERT
);
164 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
170 /* Get histogram list for STMT. */
173 gimple_histogram_value (struct function
*fun
, gimple
*stmt
)
175 if (!VALUE_HISTOGRAMS (fun
))
177 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
178 htab_hash_pointer (stmt
));
181 /* Add histogram for STMT. */
184 gimple_add_histogram_value (struct function
*fun
, gimple
*stmt
,
185 histogram_value hist
)
187 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
188 set_histogram_value (fun
, stmt
, hist
);
192 /* Remove histogram HIST from STMT's histogram list. */
195 gimple_remove_histogram_value (struct function
*fun
, gimple
*stmt
,
196 histogram_value hist
)
198 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
201 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
205 while (hist2
->hvalue
.next
!= hist
)
206 hist2
= hist2
->hvalue
.next
;
207 hist2
->hvalue
.next
= hist
->hvalue
.next
;
209 free (hist
->hvalue
.counters
);
211 memset (hist
, 0xab, sizeof (*hist
));
215 /* Lookup histogram of type TYPE in the STMT. */
218 gimple_histogram_value_of_type (struct function
*fun
, gimple
*stmt
,
221 histogram_value hist
;
222 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
223 hist
= hist
->hvalue
.next
)
224 if (hist
->type
== type
)
229 /* Dump information about HIST to DUMP_FILE. */
232 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
236 case HIST_TYPE_INTERVAL
:
237 fprintf (dump_file
, "Interval counter range %d -- %d",
238 hist
->hdata
.intvl
.int_start
,
239 (hist
->hdata
.intvl
.int_start
240 + hist
->hdata
.intvl
.steps
- 1));
241 if (hist
->hvalue
.counters
)
244 fprintf (dump_file
, " [");
245 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
246 fprintf (dump_file
, " %d:%" PRId64
,
247 hist
->hdata
.intvl
.int_start
+ i
,
248 (int64_t) hist
->hvalue
.counters
[i
]);
249 fprintf (dump_file
, " ] outside range:%" PRId64
,
250 (int64_t) hist
->hvalue
.counters
[i
]);
252 fprintf (dump_file
, ".\n");
256 fprintf (dump_file
, "Pow2 counter ");
257 if (hist
->hvalue
.counters
)
259 fprintf (dump_file
, "pow2:%" PRId64
261 (int64_t) hist
->hvalue
.counters
[1],
262 (int64_t) hist
->hvalue
.counters
[0]);
264 fprintf (dump_file
, ".\n");
267 case HIST_TYPE_SINGLE_VALUE
:
268 fprintf (dump_file
, "Single value ");
269 if (hist
->hvalue
.counters
)
271 fprintf (dump_file
, "value:%" PRId64
274 (int64_t) hist
->hvalue
.counters
[0],
275 (int64_t) hist
->hvalue
.counters
[1],
276 (int64_t) hist
->hvalue
.counters
[2]);
278 fprintf (dump_file
, ".\n");
281 case HIST_TYPE_AVERAGE
:
282 fprintf (dump_file
, "Average value ");
283 if (hist
->hvalue
.counters
)
285 fprintf (dump_file
, "sum:%" PRId64
287 (int64_t) hist
->hvalue
.counters
[0],
288 (int64_t) hist
->hvalue
.counters
[1]);
290 fprintf (dump_file
, ".\n");
294 fprintf (dump_file
, "IOR value ");
295 if (hist
->hvalue
.counters
)
297 fprintf (dump_file
, "ior:%" PRId64
,
298 (int64_t) hist
->hvalue
.counters
[0]);
300 fprintf (dump_file
, ".\n");
303 case HIST_TYPE_INDIR_CALL
:
304 fprintf (dump_file
, "Indirect call ");
305 if (hist
->hvalue
.counters
)
307 fprintf (dump_file
, "value:%" PRId64
310 (int64_t) hist
->hvalue
.counters
[0],
311 (int64_t) hist
->hvalue
.counters
[1],
312 (int64_t) hist
->hvalue
.counters
[2]);
314 fprintf (dump_file
, ".\n");
316 case HIST_TYPE_TIME_PROFILE
:
317 fprintf (dump_file
, "Time profile ");
318 if (hist
->hvalue
.counters
)
320 fprintf (dump_file
, "time:%" PRId64
,
321 (int64_t) hist
->hvalue
.counters
[0]);
323 fprintf (dump_file
, ".\n");
325 case HIST_TYPE_INDIR_CALL_TOPN
:
326 fprintf (dump_file
, "Indirect call topn ");
327 if (hist
->hvalue
.counters
)
331 fprintf (dump_file
, "accu:%" PRId64
, hist
->hvalue
.counters
[0]);
332 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
334 fprintf (dump_file
, " target:%" PRId64
" value:%" PRId64
,
335 (int64_t) hist
->hvalue
.counters
[i
],
336 (int64_t) hist
->hvalue
.counters
[i
+1]);
339 fprintf (dump_file
, ".\n");
346 /* Dump information about HIST to DUMP_FILE. */
349 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
354 bp
= bitpack_create (ob
->main_stream
);
355 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
356 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
357 streamer_write_bitpack (&bp
);
360 case HIST_TYPE_INTERVAL
:
361 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
362 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
367 for (i
= 0; i
< hist
->n_counters
; i
++)
369 /* When user uses an unsigned type with a big value, constant converted
370 to gcov_type (a signed type) can be negative. */
371 gcov_type value
= hist
->hvalue
.counters
[i
];
372 if (hist
->type
== HIST_TYPE_SINGLE_VALUE
&& i
== 0)
375 gcc_assert (value
>= 0);
377 streamer_write_gcov_count (ob
, value
);
379 if (hist
->hvalue
.next
)
380 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
383 /* Dump information about HIST to DUMP_FILE. */
386 stream_in_histogram_value (struct lto_input_block
*ib
, gimple
*stmt
)
389 unsigned int ncounters
= 0;
392 histogram_value new_val
;
394 histogram_value
*next_p
= NULL
;
398 bp
= streamer_read_bitpack (ib
);
399 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
400 next
= bp_unpack_value (&bp
, 1);
401 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
404 case HIST_TYPE_INTERVAL
:
405 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
406 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
407 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
411 case HIST_TYPE_AVERAGE
:
415 case HIST_TYPE_SINGLE_VALUE
:
416 case HIST_TYPE_INDIR_CALL
:
421 case HIST_TYPE_TIME_PROFILE
:
425 case HIST_TYPE_INDIR_CALL_TOPN
:
426 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
432 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
433 new_val
->n_counters
= ncounters
;
434 for (i
= 0; i
< ncounters
; i
++)
435 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
437 gimple_add_histogram_value (cfun
, stmt
, new_val
);
440 next_p
= &new_val
->hvalue
.next
;
445 /* Dump all histograms attached to STMT to DUMP_FILE. */
448 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
450 histogram_value hist
;
451 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
452 dump_histogram_value (dump_file
, hist
);
455 /* Remove all histograms associated with STMT. */
458 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
461 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
462 gimple_remove_histogram_value (fun
, stmt
, val
);
465 /* Duplicate all histograms associates with OSTMT to STMT. */
468 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
469 struct function
*ofun
, gimple
*ostmt
)
472 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
474 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
475 memcpy (new_val
, val
, sizeof (*val
));
476 new_val
->hvalue
.stmt
= stmt
;
477 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
478 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
479 gimple_add_histogram_value (fun
, stmt
, new_val
);
483 /* Move all histograms associated with OSTMT to STMT. */
486 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
488 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
491 /* The following three statements can't be reordered,
492 because histogram hashtab relies on stmt field value
493 for finding the exact slot. */
494 set_histogram_value (fun
, ostmt
, NULL
);
495 for (; val
!= NULL
; val
= val
->hvalue
.next
)
496 val
->hvalue
.stmt
= stmt
;
497 set_histogram_value (fun
, stmt
, val
);
501 static bool error_found
= false;
503 /* Helper function for verify_histograms. For each histogram reachable via htab
504 walk verify that it was reached via statement walk. */
507 visit_hist (void **slot
, void *data
)
509 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
510 histogram_value hist
= *(histogram_value
*) slot
;
512 if (!visited
->contains (hist
)
513 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
515 error ("dead histogram");
516 dump_histogram_value (stderr
, hist
);
517 debug_gimple_stmt (hist
->hvalue
.stmt
);
523 /* Verify sanity of the histograms. */
526 verify_histograms (void)
529 gimple_stmt_iterator gsi
;
530 histogram_value hist
;
533 hash_set
<histogram_value
> visited_hists
;
534 FOR_EACH_BB_FN (bb
, cfun
)
535 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
537 gimple
*stmt
= gsi_stmt (gsi
);
539 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
540 hist
= hist
->hvalue
.next
)
542 if (hist
->hvalue
.stmt
!= stmt
)
544 error ("Histogram value statement does not correspond to "
545 "the statement it is associated with");
546 debug_gimple_stmt (stmt
);
547 dump_histogram_value (stderr
, hist
);
550 visited_hists
.add (hist
);
553 if (VALUE_HISTOGRAMS (cfun
))
554 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
556 internal_error ("verify_histograms failed");
559 /* Helper function for verify_histograms. For each histogram reachable via htab
560 walk verify that it was reached via statement walk. */
563 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
565 histogram_value hist
= *(histogram_value
*) slot
;
566 free (hist
->hvalue
.counters
);
568 memset (hist
, 0xab, sizeof (*hist
));
574 free_histograms (struct function
*fn
)
576 if (VALUE_HISTOGRAMS (fn
))
578 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
579 htab_delete (VALUE_HISTOGRAMS (fn
));
580 VALUE_HISTOGRAMS (fn
) = NULL
;
584 /* The overall number of invocations of the counter should match
585 execution count of basic block. Report it as error rather than
586 internal error as it might mean that user has misused the profile
590 check_counter (gimple
*stmt
, const char * name
,
591 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
593 gcov_type bb_count
= bb_count_d
.to_gcov_type ();
594 if (*all
!= bb_count
|| *count
> *all
)
597 locus
= (stmt
!= NULL
)
598 ? gimple_location (stmt
)
599 : DECL_SOURCE_LOCATION (current_function_decl
);
600 if (flag_profile_correction
)
602 if (dump_enabled_p ())
603 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
604 "correcting inconsistent value profile: %s "
605 "profiler overall count (%d) does not match BB "
606 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
614 error_at (locus
, "corrupted value profile: %s "
615 "profile counter (%d out of %d) inconsistent with "
616 "basic-block count (%d)",
628 /* GIMPLE based transformations. */
631 gimple_value_profile_transformations (void)
634 gimple_stmt_iterator gsi
;
635 bool changed
= false;
637 /* Autofdo does its own transformations for indirect calls,
638 and otherwise does not support value profiling. */
639 if (flag_auto_profile
)
642 FOR_EACH_BB_FN (bb
, cfun
)
644 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
646 gimple
*stmt
= gsi_stmt (gsi
);
647 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
653 fprintf (dump_file
, "Trying transformations on stmt ");
654 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
655 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
658 /* Transformations: */
659 /* The order of things in this conditional controls which
660 transformation is used when more than one is applicable. */
661 /* It is expected that any code added by the transformations
662 will be added before the current statement, and that the
663 current statement remain valid (although possibly
664 modified) upon return. */
665 if (gimple_mod_subtract_transform (&gsi
)
666 || gimple_divmod_fixed_value_transform (&gsi
)
667 || gimple_mod_pow2_value_transform (&gsi
)
668 || gimple_stringops_transform (&gsi
)
669 || gimple_ic_transform (&gsi
))
671 stmt
= gsi_stmt (gsi
);
673 /* Original statement may no longer be in the same block. */
674 if (bb
!= gimple_bb (stmt
))
676 bb
= gimple_bb (stmt
);
677 gsi
= gsi_for_stmt (stmt
);
691 /* Generate code for transformation 1 (with parent gimple assignment
692 STMT and probability of taking the optimal path PROB, which is
693 equivalent to COUNT/ALL within roundoff error). This generates the
694 result into a temp and returns the temp; it does not replace or
695 alter the original STMT. */
698 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, int prob
,
699 gcov_type count
, gcov_type all
)
701 gassign
*stmt1
, *stmt2
;
703 tree tmp0
, tmp1
, tmp2
;
704 gimple
*bb1end
, *bb2end
, *bb3end
;
705 basic_block bb
, bb2
, bb3
, bb4
;
706 tree optype
, op1
, op2
;
707 edge e12
, e13
, e23
, e24
, e34
;
708 gimple_stmt_iterator gsi
;
710 gcc_assert (is_gimple_assign (stmt
)
711 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
712 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
714 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
715 op1
= gimple_assign_rhs1 (stmt
);
716 op2
= gimple_assign_rhs2 (stmt
);
718 bb
= gimple_bb (stmt
);
719 gsi
= gsi_for_stmt (stmt
);
721 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
722 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
723 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
724 stmt2
= gimple_build_assign (tmp1
, op2
);
725 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
726 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
727 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
728 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
731 tmp2
= create_tmp_reg (optype
, "PROF");
732 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
733 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
736 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
737 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
741 /* Edge e23 connects bb2 to bb3, etc. */
742 e12
= split_block (bb
, bb1end
);
744 bb2
->count
= profile_count::from_gcov_type (count
);
745 e23
= split_block (bb2
, bb2end
);
747 bb3
->count
= profile_count::from_gcov_type (all
- count
);
748 e34
= split_block (bb3
, bb3end
);
750 bb4
->count
= profile_count::from_gcov_type (all
);
752 e12
->flags
&= ~EDGE_FALLTHRU
;
753 e12
->flags
|= EDGE_FALSE_VALUE
;
754 e12
->probability
= prob
;
755 e12
->count
= profile_count::from_gcov_type (count
);
757 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
758 e13
->probability
= REG_BR_PROB_BASE
- prob
;
759 e13
->count
= profile_count::from_gcov_type (all
- count
);
763 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
764 e24
->probability
= REG_BR_PROB_BASE
;
765 e24
->count
= profile_count::from_gcov_type (count
);
767 e34
->probability
= REG_BR_PROB_BASE
;
768 e34
->count
= profile_count::from_gcov_type (all
- count
);
773 /* Do transform 1) on INSN if applicable. */
776 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
778 histogram_value histogram
;
780 gcov_type val
, count
, all
;
781 tree result
, value
, tree_val
;
785 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
789 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
792 code
= gimple_assign_rhs_code (stmt
);
794 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
797 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
798 HIST_TYPE_SINGLE_VALUE
);
802 value
= histogram
->hvalue
.value
;
803 val
= histogram
->hvalue
.counters
[0];
804 count
= histogram
->hvalue
.counters
[1];
805 all
= histogram
->hvalue
.counters
[2];
806 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
808 /* We require that count is at least half of all; this means
809 that for the transformation to fire the value must be constant
810 at least 50% of time (and 75% gives the guarantee of usage). */
811 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
813 || optimize_bb_for_size_p (gimple_bb (stmt
)))
816 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
819 /* Compute probability of taking the optimal path. */
821 prob
= GCOV_COMPUTE_SCALE (count
, all
);
825 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
826 tree_val
= build_int_cst (get_gcov_type (), val
);
830 a
[0] = (unsigned HOST_WIDE_INT
) val
;
831 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
833 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
834 TYPE_PRECISION (get_gcov_type ()), false));
836 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
840 fprintf (dump_file
, "Div/mod by constant ");
841 print_generic_expr (dump_file
, value
, TDF_SLIM
);
842 fprintf (dump_file
, "=");
843 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
844 fprintf (dump_file
, " transformation on insn ");
845 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
848 gimple_assign_set_rhs_from_tree (si
, result
);
849 update_stmt (gsi_stmt (*si
));
854 /* Generate code for transformation 2 (with parent gimple assign STMT and
855 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
856 within roundoff error). This generates the result into a temp and returns
857 the temp; it does not replace or alter the original STMT. */
860 gimple_mod_pow2 (gassign
*stmt
, int prob
, gcov_type count
, gcov_type all
)
862 gassign
*stmt1
, *stmt2
, *stmt3
;
865 gimple
*bb1end
, *bb2end
, *bb3end
;
866 basic_block bb
, bb2
, bb3
, bb4
;
867 tree optype
, op1
, op2
;
868 edge e12
, e13
, e23
, e24
, e34
;
869 gimple_stmt_iterator gsi
;
872 gcc_assert (is_gimple_assign (stmt
)
873 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
875 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
876 op1
= gimple_assign_rhs1 (stmt
);
877 op2
= gimple_assign_rhs2 (stmt
);
879 bb
= gimple_bb (stmt
);
880 gsi
= gsi_for_stmt (stmt
);
882 result
= create_tmp_reg (optype
, "PROF");
883 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
884 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
885 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
886 build_int_cst (optype
, -1));
887 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
888 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
889 NULL_TREE
, NULL_TREE
);
890 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
891 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
892 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
895 /* tmp2 == op2-1 inherited from previous block. */
896 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
897 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
900 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
902 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
906 /* Edge e23 connects bb2 to bb3, etc. */
907 e12
= split_block (bb
, bb1end
);
909 bb2
->count
= profile_count::from_gcov_type (count
);
910 e23
= split_block (bb2
, bb2end
);
912 bb3
->count
= profile_count::from_gcov_type (all
- count
);
913 e34
= split_block (bb3
, bb3end
);
915 bb4
->count
= profile_count::from_gcov_type (all
);
917 e12
->flags
&= ~EDGE_FALLTHRU
;
918 e12
->flags
|= EDGE_FALSE_VALUE
;
919 e12
->probability
= prob
;
920 e12
->count
= profile_count::from_gcov_type (count
);
922 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
923 e13
->probability
= REG_BR_PROB_BASE
- prob
;
924 e13
->count
= profile_count::from_gcov_type (all
- count
);
928 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
929 e24
->probability
= REG_BR_PROB_BASE
;
930 e24
->count
= profile_count::from_gcov_type (count
);
932 e34
->probability
= REG_BR_PROB_BASE
;
933 e34
->count
= profile_count::from_gcov_type (all
- count
);
938 /* Do transform 2) on INSN if applicable. */
941 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
943 histogram_value histogram
;
945 gcov_type count
, wrong_values
, all
;
946 tree lhs_type
, result
, value
;
950 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
954 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
955 if (!INTEGRAL_TYPE_P (lhs_type
))
958 code
= gimple_assign_rhs_code (stmt
);
960 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
963 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
967 value
= histogram
->hvalue
.value
;
968 wrong_values
= histogram
->hvalue
.counters
[0];
969 count
= histogram
->hvalue
.counters
[1];
971 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
973 /* We require that we hit a power of 2 at least half of all evaluations. */
974 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
975 || count
< wrong_values
976 || optimize_bb_for_size_p (gimple_bb (stmt
)))
981 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
982 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
985 /* Compute probability of taking the optimal path. */
986 all
= count
+ wrong_values
;
988 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
992 prob
= GCOV_COMPUTE_SCALE (count
, all
);
996 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
998 gimple_assign_set_rhs_from_tree (si
, result
);
999 update_stmt (gsi_stmt (*si
));
1004 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1005 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1006 supported and this is built into this interface. The probabilities of taking
1007 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1008 COUNT2/ALL respectively within roundoff error). This generates the
1009 result into a temp and returns the temp; it does not replace or alter
1010 the original STMT. */
1011 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1014 gimple_mod_subtract (gassign
*stmt
, int prob1
, int prob2
, int ncounts
,
1015 gcov_type count1
, gcov_type count2
, gcov_type all
)
1021 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
1022 basic_block bb
, bb2
, bb3
, bb4
;
1023 tree optype
, op1
, op2
;
1024 edge e12
, e23
= 0, e24
, e34
, e14
;
1025 gimple_stmt_iterator gsi
;
1028 gcc_assert (is_gimple_assign (stmt
)
1029 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1031 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1032 op1
= gimple_assign_rhs1 (stmt
);
1033 op2
= gimple_assign_rhs2 (stmt
);
1035 bb
= gimple_bb (stmt
);
1036 gsi
= gsi_for_stmt (stmt
);
1038 result
= create_tmp_reg (optype
, "PROF");
1039 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1040 stmt1
= gimple_build_assign (result
, op1
);
1041 stmt2
= gimple_build_assign (tmp1
, op2
);
1042 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1043 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1044 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1045 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1048 if (ncounts
) /* Assumed to be 0 or 1 */
1050 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1051 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1052 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1053 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1057 /* Fallback case. */
1058 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1060 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1064 /* Edge e23 connects bb2 to bb3, etc. */
1065 /* However block 3 is optional; if it is not there, references
1066 to 3 really refer to block 2. */
1067 e12
= split_block (bb
, bb1end
);
1069 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1071 if (ncounts
) /* Assumed to be 0 or 1. */
1073 e23
= split_block (bb2
, bb2end
);
1075 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1078 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1080 bb4
->count
= profile_count::from_gcov_type (all
);
1082 e12
->flags
&= ~EDGE_FALLTHRU
;
1083 e12
->flags
|= EDGE_FALSE_VALUE
;
1084 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1085 e12
->count
= profile_count::from_gcov_type (all
- count1
);
1087 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1088 e14
->probability
= prob1
;
1089 e14
->count
= profile_count::from_gcov_type (count1
);
1091 if (ncounts
) /* Assumed to be 0 or 1. */
1093 e23
->flags
&= ~EDGE_FALLTHRU
;
1094 e23
->flags
|= EDGE_FALSE_VALUE
;
1095 e23
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1096 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1098 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1099 e24
->probability
= prob2
;
1100 e24
->count
= profile_count::from_gcov_type (count2
);
1103 e34
->probability
= REG_BR_PROB_BASE
;
1104 e34
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1109 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1112 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1114 histogram_value histogram
;
1115 enum tree_code code
;
1116 gcov_type count
, wrong_values
, all
;
1117 tree lhs_type
, result
;
1118 gcov_type prob1
, prob2
;
1119 unsigned int i
, steps
;
1120 gcov_type count1
, count2
;
1122 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1126 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1127 if (!INTEGRAL_TYPE_P (lhs_type
))
1130 code
= gimple_assign_rhs_code (stmt
);
1132 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1135 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1141 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1142 all
+= histogram
->hvalue
.counters
[i
];
1144 wrong_values
+= histogram
->hvalue
.counters
[i
];
1145 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1146 steps
= histogram
->hdata
.intvl
.steps
;
1147 all
+= wrong_values
;
1148 count1
= histogram
->hvalue
.counters
[0];
1149 count2
= histogram
->hvalue
.counters
[1];
1151 /* Compute probability of taking the optimal path. */
1152 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1154 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1158 if (flag_profile_correction
&& count1
+ count2
> all
)
1159 all
= count1
+ count2
;
1161 gcc_assert (count1
+ count2
<= all
);
1163 /* We require that we use just subtractions in at least 50% of all
1166 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1168 count
+= histogram
->hvalue
.counters
[i
];
1169 if (count
* 2 >= all
)
1173 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1176 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1179 fprintf (dump_file
, "Mod subtract transformation on insn ");
1180 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1183 /* Compute probability of taking the optimal path(s). */
1186 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1187 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1194 /* In practice, "steps" is always 2. This interface reflects this,
1195 and will need to be changed if "steps" can change. */
1196 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1198 gimple_assign_set_rhs_from_tree (si
, result
);
1199 update_stmt (gsi_stmt (*si
));
1204 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1206 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1208 /* Returns true if node graph is initialized. This
1209 is used to test if profile_id has been created
1210 for cgraph_nodes. */
1213 coverage_node_map_initialized_p (void)
1215 return cgraph_node_map
!= 0;
1218 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1219 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1220 that the PROFILE_IDs was already assigned. */
1223 init_node_map (bool local
)
1225 struct cgraph_node
*n
;
1226 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1228 FOR_EACH_DEFINED_FUNCTION (n
)
1229 if (n
->has_gimple_body_p ())
1234 n
->profile_id
= coverage_compute_profile_id (n
);
1235 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1239 fprintf (dump_file
, "Local profile-id %i conflict"
1240 " with nodes %s %s\n",
1243 (*val
)->dump_name ());
1244 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1247 else if (!n
->profile_id
)
1251 "Node %s has no profile-id"
1252 " (profile feedback missing?)\n",
1256 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1260 "Node %s has IP profile-id %i conflict. "
1262 n
->dump_name (), n
->profile_id
);
1266 cgraph_node_map
->put (n
->profile_id
, n
);
1270 /* Delete the CGRAPH_NODE_MAP. */
1275 delete cgraph_node_map
;
1278 /* Return cgraph node for function with pid */
1281 find_func_by_profile_id (int profile_id
)
1283 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1290 /* Perform sanity check on the indirect call target. Due to race conditions,
1291 false function target may be attributed to an indirect call site. If the
1292 call expression type mismatches with the target function's type, expand_call
1293 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1294 Returns true if TARGET is considered ok for call CALL_STMT. */
1297 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1300 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1303 locus
= gimple_location (call_stmt
);
1304 if (dump_enabled_p ())
1305 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1306 "Skipping target %s with mismatching types for icall\n",
1311 /* Do transformation
1313 if (actual_callee_address == address_of_most_common_function/method)
1320 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1321 int prob
, profile_count count
, profile_count all
)
1326 gcall
*iretbnd_stmt
= NULL
;
1327 tree tmp0
, tmp1
, tmp
;
1328 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1329 tree optype
= build_pointer_type (void_type_node
);
1330 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1331 gimple_stmt_iterator gsi
;
1335 gimple_stmt_iterator psi
;
1337 cond_bb
= gimple_bb (icall_stmt
);
1338 gsi
= gsi_for_stmt (icall_stmt
);
1340 if (gimple_call_with_bounds_p (icall_stmt
) && gimple_call_lhs (icall_stmt
))
1341 iretbnd_stmt
= chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt
));
1343 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1344 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1345 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1346 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1347 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1349 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
));
1350 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1351 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1353 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1354 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1356 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1358 unlink_stmt_vdef (icall_stmt
);
1359 release_ssa_name (gimple_vdef (icall_stmt
));
1361 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1362 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1363 update_stmt (icall_stmt
);
1364 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1365 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1366 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1367 if ((dflags
& ECF_NORETURN
) != 0
1368 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1369 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1370 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1373 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1374 e_cd
= split_block (cond_bb
, cond_stmt
);
1375 dcall_bb
= e_cd
->dest
;
1376 dcall_bb
->count
= count
;
1378 e_di
= split_block (dcall_bb
, dcall_stmt
);
1379 icall_bb
= e_di
->dest
;
1380 icall_bb
->count
= all
- count
;
1382 /* Do not disturb existing EH edges from the indirect call. */
1383 if (!stmt_ends_bb_p (icall_stmt
))
1384 e_ij
= split_block (icall_bb
, icall_stmt
);
1387 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1388 /* The indirect call might be noreturn. */
1391 e_ij
->probability
= REG_BR_PROB_BASE
;
1392 e_ij
->count
= all
- count
;
1393 e_ij
= single_pred_edge (split_edge (e_ij
));
1398 join_bb
= e_ij
->dest
;
1399 join_bb
->count
= all
;
1402 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1403 e_cd
->probability
= prob
;
1404 e_cd
->count
= count
;
1406 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1407 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1408 e_ci
->count
= all
- count
;
1414 if ((dflags
& ECF_NORETURN
) != 0)
1418 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1419 e_dj
->probability
= REG_BR_PROB_BASE
;
1420 e_dj
->count
= count
;
1422 e_ij
->count
= all
- count
;
1424 e_ij
->probability
= REG_BR_PROB_BASE
;
1427 /* Insert PHI node for the call result if necessary. */
1428 if (gimple_call_lhs (icall_stmt
)
1429 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1430 && (dflags
& ECF_NORETURN
) == 0)
1432 tree result
= gimple_call_lhs (icall_stmt
);
1433 gphi
*phi
= create_phi_node (result
, join_bb
);
1434 gimple_call_set_lhs (icall_stmt
,
1435 duplicate_ssa_name (result
, icall_stmt
));
1436 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1437 gimple_call_set_lhs (dcall_stmt
,
1438 duplicate_ssa_name (result
, dcall_stmt
));
1439 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1441 /* If indirect call has following BUILT_IN_CHKP_BNDRET
1442 call then we need to make it's copy for the direct
1446 if (gimple_call_lhs (iretbnd_stmt
))
1450 if (TREE_CODE (gimple_vdef (iretbnd_stmt
)) == SSA_NAME
)
1452 unlink_stmt_vdef (iretbnd_stmt
);
1453 release_ssa_name (gimple_vdef (iretbnd_stmt
));
1455 gimple_set_vdef (iretbnd_stmt
, NULL_TREE
);
1456 gimple_set_vuse (iretbnd_stmt
, NULL_TREE
);
1457 update_stmt (iretbnd_stmt
);
1459 result
= gimple_call_lhs (iretbnd_stmt
);
1460 phi
= create_phi_node (result
, join_bb
);
1462 copy
= gimple_copy (iretbnd_stmt
);
1463 gimple_call_set_arg (copy
, 0,
1464 gimple_call_lhs (dcall_stmt
));
1465 gimple_call_set_lhs (copy
, duplicate_ssa_name (result
, copy
));
1466 gsi_insert_on_edge (e_dj
, copy
);
1467 add_phi_arg (phi
, gimple_call_lhs (copy
),
1468 e_dj
, UNKNOWN_LOCATION
);
1470 gimple_call_set_arg (iretbnd_stmt
, 0,
1471 gimple_call_lhs (icall_stmt
));
1472 gimple_call_set_lhs (iretbnd_stmt
,
1473 duplicate_ssa_name (result
, iretbnd_stmt
));
1474 psi
= gsi_for_stmt (iretbnd_stmt
);
1475 gsi_remove (&psi
, false);
1476 gsi_insert_on_edge (e_ij
, iretbnd_stmt
);
1477 add_phi_arg (phi
, gimple_call_lhs (iretbnd_stmt
),
1478 e_ij
, UNKNOWN_LOCATION
);
1480 gsi_commit_one_edge_insert (e_dj
, NULL
);
1481 gsi_commit_one_edge_insert (e_ij
, NULL
);
1485 psi
= gsi_for_stmt (iretbnd_stmt
);
1486 gsi_remove (&psi
, true);
1491 /* Build an EH edge for the direct call if necessary. */
1492 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1493 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1495 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1498 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1499 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1501 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1502 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1503 !gsi_end_p (psi
); gsi_next (&psi
))
1505 gphi
*phi
= psi
.phi ();
1506 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1507 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1510 if (!stmt_could_throw_p (dcall_stmt
))
1511 gimple_purge_dead_eh_edges (dcall_bb
);
1516 For every checked indirect/virtual call determine if most common pid of
1517 function/class method has probability more than 50%. If yes modify code of
1522 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1525 histogram_value histogram
;
1526 gcov_type val
, count
, all
, bb_all
;
1527 struct cgraph_node
*direct_call
;
1529 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1533 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1536 if (gimple_call_internal_p (stmt
))
1539 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1543 val
= histogram
->hvalue
.counters
[0];
1544 count
= histogram
->hvalue
.counters
[1];
1545 all
= histogram
->hvalue
.counters
[2];
1547 bb_all
= gimple_bb (stmt
)->count
.to_gcov_type ();
1548 /* The order of CHECK_COUNTER calls is important -
1549 since check_counter can correct the third parameter
1550 and we want to make count <= all <= bb_all. */
1551 if (check_counter (stmt
, "ic", &all
, &bb_all
, gimple_bb (stmt
)->count
)
1552 || check_counter (stmt
, "ic", &count
, &all
,
1553 profile_count::from_gcov_type (all
)))
1555 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1559 if (4 * count
<= 3 * all
)
1562 direct_call
= find_func_by_profile_id ((int)val
);
1564 if (direct_call
== NULL
)
1570 fprintf (dump_file
, "Indirect call -> direct call from other module");
1571 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1572 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1578 if (!check_ic_target (stmt
, direct_call
))
1582 fprintf (dump_file
, "Indirect call -> direct call ");
1583 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1584 fprintf (dump_file
, "=> ");
1585 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1586 fprintf (dump_file
, " transformation skipped because of type mismatch");
1587 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1589 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1595 fprintf (dump_file
, "Indirect call -> direct call ");
1596 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1597 fprintf (dump_file
, "=> ");
1598 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1599 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1600 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1601 fprintf (dump_file
, "hist->count %" PRId64
1602 " hist->all %" PRId64
"\n", count
, all
);
1608 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1609 set to the argument index for the size of the string operation. */
1612 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1614 enum built_in_function fcode
;
1616 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1617 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1618 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1623 case BUILT_IN_MEMCPY
:
1624 case BUILT_IN_MEMPCPY
:
1626 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1627 INTEGER_TYPE
, VOID_TYPE
);
1628 case BUILT_IN_MEMSET
:
1630 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1631 INTEGER_TYPE
, VOID_TYPE
);
1632 case BUILT_IN_BZERO
:
1634 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1641 /* Convert stringop (..., vcall_size)
1643 if (vcall_size == icall_size)
1644 stringop (..., icall_size);
1646 stringop (..., vcall_size);
1647 assuming we'll propagate a true constant into ICALL_SIZE later. */
1650 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, int prob
,
1651 gcov_type count
, gcov_type all
)
1656 tree tmp0
, tmp1
, vcall_size
, optype
;
1657 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1658 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1659 gimple_stmt_iterator gsi
;
1662 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1665 cond_bb
= gimple_bb (vcall_stmt
);
1666 gsi
= gsi_for_stmt (vcall_stmt
);
1668 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1669 optype
= TREE_TYPE (vcall_size
);
1671 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1672 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1673 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1674 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1676 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1677 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1679 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1680 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1682 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1684 unlink_stmt_vdef (vcall_stmt
);
1685 release_ssa_name (gimple_vdef (vcall_stmt
));
1687 gimple_set_vdef (vcall_stmt
, NULL
);
1688 gimple_set_vuse (vcall_stmt
, NULL
);
1689 update_stmt (vcall_stmt
);
1690 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1691 gimple_call_set_arg (icall_stmt
, size_arg
,
1692 fold_convert (optype
, icall_size
));
1693 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1696 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1697 e_ci
= split_block (cond_bb
, cond_stmt
);
1698 icall_bb
= e_ci
->dest
;
1699 icall_bb
->count
= profile_count::from_gcov_type (count
);
1701 e_iv
= split_block (icall_bb
, icall_stmt
);
1702 vcall_bb
= e_iv
->dest
;
1703 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1705 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1706 join_bb
= e_vj
->dest
;
1707 join_bb
->count
= profile_count::from_gcov_type (all
);
1709 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1710 e_ci
->probability
= prob
;
1711 e_ci
->count
= profile_count::from_gcov_type (count
);
1713 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1714 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1715 e_cv
->count
= profile_count::from_gcov_type (all
- count
);
1719 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1720 e_ij
->probability
= REG_BR_PROB_BASE
;
1721 e_ij
->count
= profile_count::from_gcov_type (count
);
1723 e_vj
->probability
= REG_BR_PROB_BASE
;
1724 e_vj
->count
= profile_count::from_gcov_type (all
- count
);
1726 /* Insert PHI node for the call result if necessary. */
1727 if (gimple_call_lhs (vcall_stmt
)
1728 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1730 tree result
= gimple_call_lhs (vcall_stmt
);
1731 gphi
*phi
= create_phi_node (result
, join_bb
);
1732 gimple_call_set_lhs (vcall_stmt
,
1733 duplicate_ssa_name (result
, vcall_stmt
));
1734 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1735 gimple_call_set_lhs (icall_stmt
,
1736 duplicate_ssa_name (result
, icall_stmt
));
1737 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1740 /* Because these are all string op builtins, they're all nothrow. */
1741 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1742 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1745 /* Find values inside STMT for that we want to measure histograms for
1746 division/modulo optimization. */
1749 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1753 enum built_in_function fcode
;
1754 histogram_value histogram
;
1755 gcov_type count
, all
, val
;
1757 unsigned int dest_align
, src_align
;
1762 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1766 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1769 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1772 blck_size
= gimple_call_arg (stmt
, size_arg
);
1773 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1776 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1780 val
= histogram
->hvalue
.counters
[0];
1781 count
= histogram
->hvalue
.counters
[1];
1782 all
= histogram
->hvalue
.counters
[2];
1783 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1785 /* We require that count is at least half of all; this means
1786 that for the transformation to fire the value must be constant
1787 at least 80% of time. */
1788 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1790 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1793 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1797 dest
= gimple_call_arg (stmt
, 0);
1798 dest_align
= get_pointer_alignment (dest
);
1799 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1802 case BUILT_IN_MEMCPY
:
1803 case BUILT_IN_MEMPCPY
:
1804 src
= gimple_call_arg (stmt
, 1);
1805 src_align
= get_pointer_alignment (src
);
1806 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1809 case BUILT_IN_MEMSET
:
1810 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1811 gimple_call_arg (stmt
, 1),
1815 case BUILT_IN_BZERO
:
1816 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1825 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1826 tree_val
= build_int_cst (get_gcov_type (), val
);
1830 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1831 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1833 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1834 TYPE_PRECISION (get_gcov_type ()), false));
1839 fprintf (dump_file
, "Single value %i stringop transformation on ",
1841 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1844 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1850 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1851 HOST_WIDE_INT
*expected_size
)
1853 histogram_value histogram
;
1854 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1857 *expected_size
= -1;
1858 else if (!histogram
->hvalue
.counters
[1])
1860 *expected_size
= -1;
1861 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1866 size
= ((histogram
->hvalue
.counters
[0]
1867 + histogram
->hvalue
.counters
[1] / 2)
1868 / histogram
->hvalue
.counters
[1]);
1869 /* Even if we can hold bigger value in SIZE, INT_MAX
1870 is safe "infinity" for code generation strategies. */
1873 *expected_size
= size
;
1874 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1877 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1880 *expected_align
= 0;
1881 else if (!histogram
->hvalue
.counters
[0])
1883 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1884 *expected_align
= 0;
1889 unsigned int alignment
;
1891 count
= histogram
->hvalue
.counters
[0];
1893 while (!(count
& alignment
)
1894 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1896 *expected_align
= alignment
* BITS_PER_UNIT
;
1897 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1902 /* Find values inside STMT for that we want to measure histograms for
1903 division/modulo optimization. */
1906 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1908 tree lhs
, divisor
, op0
, type
;
1909 histogram_value hist
;
1911 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1914 lhs
= gimple_assign_lhs (stmt
);
1915 type
= TREE_TYPE (lhs
);
1916 if (!INTEGRAL_TYPE_P (type
))
1919 switch (gimple_assign_rhs_code (stmt
))
1921 case TRUNC_DIV_EXPR
:
1922 case TRUNC_MOD_EXPR
:
1923 divisor
= gimple_assign_rhs2 (stmt
);
1924 op0
= gimple_assign_rhs1 (stmt
);
1926 values
->reserve (3);
1928 if (TREE_CODE (divisor
) == SSA_NAME
)
1929 /* Check for the case where the divisor is the same value most
1931 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1932 HIST_TYPE_SINGLE_VALUE
,
1935 /* For mod, check whether it is not often a noop (or replaceable by
1936 a few subtractions). */
1937 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1938 && TYPE_UNSIGNED (type
)
1939 && TREE_CODE (divisor
) == SSA_NAME
)
1942 /* Check for a special case where the divisor is power of 2. */
1943 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1947 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1948 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1950 hist
->hdata
.intvl
.int_start
= 0;
1951 hist
->hdata
.intvl
.steps
= 2;
1952 values
->quick_push (hist
);
1961 /* Find calls inside STMT for that we want to measure histograms for
1962 indirect/virtual call optimization. */
1965 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1969 if (gimple_code (stmt
) != GIMPLE_CALL
1970 || gimple_call_internal_p (stmt
)
1971 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1974 callee
= gimple_call_fn (stmt
);
1976 values
->reserve (3);
1978 values
->quick_push (gimple_alloc_histogram_value (
1980 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1981 HIST_TYPE_INDIR_CALL_TOPN
:
1982 HIST_TYPE_INDIR_CALL
,
1988 /* Find values inside STMT for that we want to measure histograms for
1989 string operations. */
1992 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1999 stmt
= dyn_cast
<gcall
*> (gs
);
2003 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
2006 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
2009 dest
= gimple_call_arg (stmt
, 0);
2010 blck_size
= gimple_call_arg (stmt
, size_arg
);
2012 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2014 values
->safe_push (gimple_alloc_histogram_value (cfun
,
2015 HIST_TYPE_SINGLE_VALUE
,
2017 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
2021 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2022 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
2026 /* Find values inside STMT for that we want to measure histograms and adds
2027 them to list VALUES. */
2030 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
2032 gimple_divmod_values_to_profile (stmt
, values
);
2033 gimple_stringops_values_to_profile (stmt
, values
);
2034 gimple_indirect_call_to_profile (stmt
, values
);
2038 gimple_find_values_to_profile (histogram_values
*values
)
2041 gimple_stmt_iterator gsi
;
2043 histogram_value hist
= NULL
;
2046 FOR_EACH_BB_FN (bb
, cfun
)
2047 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2048 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2050 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2052 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2056 case HIST_TYPE_INTERVAL
:
2057 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2060 case HIST_TYPE_POW2
:
2061 hist
->n_counters
= 2;
2064 case HIST_TYPE_SINGLE_VALUE
:
2065 hist
->n_counters
= 3;
2068 case HIST_TYPE_INDIR_CALL
:
2069 hist
->n_counters
= 3;
2072 case HIST_TYPE_TIME_PROFILE
:
2073 hist
->n_counters
= 1;
2076 case HIST_TYPE_AVERAGE
:
2077 hist
->n_counters
= 2;
2081 hist
->n_counters
= 1;
2084 case HIST_TYPE_INDIR_CALL_TOPN
:
2085 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2093 fprintf (dump_file
, "Stmt ");
2094 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2095 dump_histogram_value (dump_file
, hist
);