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
);
572 free_histograms (struct function
*fn
)
574 if (VALUE_HISTOGRAMS (fn
))
576 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
577 htab_delete (VALUE_HISTOGRAMS (fn
));
578 VALUE_HISTOGRAMS (fn
) = NULL
;
582 /* The overall number of invocations of the counter should match
583 execution count of basic block. Report it as error rather than
584 internal error as it might mean that user has misused the profile
588 check_counter (gimple
*stmt
, const char * name
,
589 gcov_type
*count
, gcov_type
*all
, profile_count bb_count_d
)
591 gcov_type bb_count
= bb_count_d
.to_gcov_type ();
592 if (*all
!= bb_count
|| *count
> *all
)
595 locus
= (stmt
!= NULL
)
596 ? gimple_location (stmt
)
597 : DECL_SOURCE_LOCATION (current_function_decl
);
598 if (flag_profile_correction
)
600 if (dump_enabled_p ())
601 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
602 "correcting inconsistent value profile: %s "
603 "profiler overall count (%d) does not match BB "
604 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
612 error_at (locus
, "corrupted value profile: %s "
613 "profile counter (%d out of %d) inconsistent with "
614 "basic-block count (%d)",
626 /* GIMPLE based transformations. */
629 gimple_value_profile_transformations (void)
632 gimple_stmt_iterator gsi
;
633 bool changed
= false;
635 /* Autofdo does its own transformations for indirect calls,
636 and otherwise does not support value profiling. */
637 if (flag_auto_profile
)
640 FOR_EACH_BB_FN (bb
, cfun
)
642 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
644 gimple
*stmt
= gsi_stmt (gsi
);
645 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
651 fprintf (dump_file
, "Trying transformations on stmt ");
652 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
653 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
656 /* Transformations: */
657 /* The order of things in this conditional controls which
658 transformation is used when more than one is applicable. */
659 /* It is expected that any code added by the transformations
660 will be added before the current statement, and that the
661 current statement remain valid (although possibly
662 modified) upon return. */
663 if (gimple_mod_subtract_transform (&gsi
)
664 || gimple_divmod_fixed_value_transform (&gsi
)
665 || gimple_mod_pow2_value_transform (&gsi
)
666 || gimple_stringops_transform (&gsi
)
667 || gimple_ic_transform (&gsi
))
669 stmt
= gsi_stmt (gsi
);
671 /* Original statement may no longer be in the same block. */
672 if (bb
!= gimple_bb (stmt
))
674 bb
= gimple_bb (stmt
);
675 gsi
= gsi_for_stmt (stmt
);
689 /* Generate code for transformation 1 (with parent gimple assignment
690 STMT and probability of taking the optimal path PROB, which is
691 equivalent to COUNT/ALL within roundoff error). This generates the
692 result into a temp and returns the temp; it does not replace or
693 alter the original STMT. */
696 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, int prob
,
697 gcov_type count
, gcov_type all
)
699 gassign
*stmt1
, *stmt2
;
701 tree tmp0
, tmp1
, tmp2
;
702 gimple
*bb1end
, *bb2end
, *bb3end
;
703 basic_block bb
, bb2
, bb3
, bb4
;
704 tree optype
, op1
, op2
;
705 edge e12
, e13
, e23
, e24
, e34
;
706 gimple_stmt_iterator gsi
;
708 gcc_assert (is_gimple_assign (stmt
)
709 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
710 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
712 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
713 op1
= gimple_assign_rhs1 (stmt
);
714 op2
= gimple_assign_rhs2 (stmt
);
716 bb
= gimple_bb (stmt
);
717 gsi
= gsi_for_stmt (stmt
);
719 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
720 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
721 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
722 stmt2
= gimple_build_assign (tmp1
, op2
);
723 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
724 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
725 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
726 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
729 tmp2
= create_tmp_reg (optype
, "PROF");
730 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
731 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
734 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
735 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
739 /* Edge e23 connects bb2 to bb3, etc. */
740 e12
= split_block (bb
, bb1end
);
742 bb2
->count
= profile_count::from_gcov_type (count
);
743 e23
= split_block (bb2
, bb2end
);
745 bb3
->count
= profile_count::from_gcov_type (all
- count
);
746 e34
= split_block (bb3
, bb3end
);
748 bb4
->count
= profile_count::from_gcov_type (all
);
750 e12
->flags
&= ~EDGE_FALLTHRU
;
751 e12
->flags
|= EDGE_FALSE_VALUE
;
752 e12
->probability
= prob
;
753 e12
->count
= profile_count::from_gcov_type (count
);
755 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
756 e13
->probability
= REG_BR_PROB_BASE
- prob
;
757 e13
->count
= profile_count::from_gcov_type (all
- count
);
761 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
762 e24
->probability
= REG_BR_PROB_BASE
;
763 e24
->count
= profile_count::from_gcov_type (count
);
765 e34
->probability
= REG_BR_PROB_BASE
;
766 e34
->count
= profile_count::from_gcov_type (all
- count
);
771 /* Do transform 1) on INSN if applicable. */
774 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
776 histogram_value histogram
;
778 gcov_type val
, count
, all
;
779 tree result
, value
, tree_val
;
783 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
787 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
790 code
= gimple_assign_rhs_code (stmt
);
792 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
795 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
796 HIST_TYPE_SINGLE_VALUE
);
800 value
= histogram
->hvalue
.value
;
801 val
= histogram
->hvalue
.counters
[0];
802 count
= histogram
->hvalue
.counters
[1];
803 all
= histogram
->hvalue
.counters
[2];
804 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
806 /* We require that count is at least half of all; this means
807 that for the transformation to fire the value must be constant
808 at least 50% of time (and 75% gives the guarantee of usage). */
809 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
811 || optimize_bb_for_size_p (gimple_bb (stmt
)))
814 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
817 /* Compute probability of taking the optimal path. */
819 prob
= GCOV_COMPUTE_SCALE (count
, all
);
823 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
824 tree_val
= build_int_cst (get_gcov_type (), val
);
828 a
[0] = (unsigned HOST_WIDE_INT
) val
;
829 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
831 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
832 TYPE_PRECISION (get_gcov_type ()), false));
834 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
838 fprintf (dump_file
, "Div/mod by constant ");
839 print_generic_expr (dump_file
, value
, TDF_SLIM
);
840 fprintf (dump_file
, "=");
841 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
842 fprintf (dump_file
, " transformation on insn ");
843 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
846 gimple_assign_set_rhs_from_tree (si
, result
);
847 update_stmt (gsi_stmt (*si
));
852 /* Generate code for transformation 2 (with parent gimple assign STMT and
853 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
854 within roundoff error). This generates the result into a temp and returns
855 the temp; it does not replace or alter the original STMT. */
858 gimple_mod_pow2 (gassign
*stmt
, int prob
, gcov_type count
, gcov_type all
)
860 gassign
*stmt1
, *stmt2
, *stmt3
;
863 gimple
*bb1end
, *bb2end
, *bb3end
;
864 basic_block bb
, bb2
, bb3
, bb4
;
865 tree optype
, op1
, op2
;
866 edge e12
, e13
, e23
, e24
, e34
;
867 gimple_stmt_iterator gsi
;
870 gcc_assert (is_gimple_assign (stmt
)
871 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
873 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
874 op1
= gimple_assign_rhs1 (stmt
);
875 op2
= gimple_assign_rhs2 (stmt
);
877 bb
= gimple_bb (stmt
);
878 gsi
= gsi_for_stmt (stmt
);
880 result
= create_tmp_reg (optype
, "PROF");
881 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
882 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
883 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
884 build_int_cst (optype
, -1));
885 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
886 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
887 NULL_TREE
, NULL_TREE
);
888 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
889 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
890 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
893 /* tmp2 == op2-1 inherited from previous block. */
894 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
895 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
898 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
900 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
904 /* Edge e23 connects bb2 to bb3, etc. */
905 e12
= split_block (bb
, bb1end
);
907 bb2
->count
= profile_count::from_gcov_type (count
);
908 e23
= split_block (bb2
, bb2end
);
910 bb3
->count
= profile_count::from_gcov_type (all
- count
);
911 e34
= split_block (bb3
, bb3end
);
913 bb4
->count
= profile_count::from_gcov_type (all
);
915 e12
->flags
&= ~EDGE_FALLTHRU
;
916 e12
->flags
|= EDGE_FALSE_VALUE
;
917 e12
->probability
= prob
;
918 e12
->count
= profile_count::from_gcov_type (count
);
920 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
921 e13
->probability
= REG_BR_PROB_BASE
- prob
;
922 e13
->count
= profile_count::from_gcov_type (all
- count
);
926 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
927 e24
->probability
= REG_BR_PROB_BASE
;
928 e24
->count
= profile_count::from_gcov_type (count
);
930 e34
->probability
= REG_BR_PROB_BASE
;
931 e34
->count
= profile_count::from_gcov_type (all
- count
);
936 /* Do transform 2) on INSN if applicable. */
939 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
941 histogram_value histogram
;
943 gcov_type count
, wrong_values
, all
;
944 tree lhs_type
, result
, value
;
948 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
952 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
953 if (!INTEGRAL_TYPE_P (lhs_type
))
956 code
= gimple_assign_rhs_code (stmt
);
958 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
961 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
965 value
= histogram
->hvalue
.value
;
966 wrong_values
= histogram
->hvalue
.counters
[0];
967 count
= histogram
->hvalue
.counters
[1];
969 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
971 /* We require that we hit a power of 2 at least half of all evaluations. */
972 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
973 || count
< wrong_values
974 || optimize_bb_for_size_p (gimple_bb (stmt
)))
979 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
980 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
983 /* Compute probability of taking the optimal path. */
984 all
= count
+ wrong_values
;
986 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
990 prob
= GCOV_COMPUTE_SCALE (count
, all
);
994 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
996 gimple_assign_set_rhs_from_tree (si
, result
);
997 update_stmt (gsi_stmt (*si
));
1002 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1003 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1004 supported and this is built into this interface. The probabilities of taking
1005 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1006 COUNT2/ALL respectively within roundoff error). This generates the
1007 result into a temp and returns the temp; it does not replace or alter
1008 the original STMT. */
1009 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1012 gimple_mod_subtract (gassign
*stmt
, int prob1
, int prob2
, int ncounts
,
1013 gcov_type count1
, gcov_type count2
, gcov_type all
)
1019 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
1020 basic_block bb
, bb2
, bb3
, bb4
;
1021 tree optype
, op1
, op2
;
1022 edge e12
, e23
= 0, e24
, e34
, e14
;
1023 gimple_stmt_iterator gsi
;
1026 gcc_assert (is_gimple_assign (stmt
)
1027 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1029 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1030 op1
= gimple_assign_rhs1 (stmt
);
1031 op2
= gimple_assign_rhs2 (stmt
);
1033 bb
= gimple_bb (stmt
);
1034 gsi
= gsi_for_stmt (stmt
);
1036 result
= create_tmp_reg (optype
, "PROF");
1037 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1038 stmt1
= gimple_build_assign (result
, op1
);
1039 stmt2
= gimple_build_assign (tmp1
, op2
);
1040 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1041 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1042 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1043 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1046 if (ncounts
) /* Assumed to be 0 or 1 */
1048 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1049 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1050 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1051 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1055 /* Fallback case. */
1056 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1058 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1062 /* Edge e23 connects bb2 to bb3, etc. */
1063 /* However block 3 is optional; if it is not there, references
1064 to 3 really refer to block 2. */
1065 e12
= split_block (bb
, bb1end
);
1067 bb2
->count
= profile_count::from_gcov_type (all
- count1
);
1069 if (ncounts
) /* Assumed to be 0 or 1. */
1071 e23
= split_block (bb2
, bb2end
);
1073 bb3
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1076 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1078 bb4
->count
= profile_count::from_gcov_type (all
);
1080 e12
->flags
&= ~EDGE_FALLTHRU
;
1081 e12
->flags
|= EDGE_FALSE_VALUE
;
1082 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1083 e12
->count
= profile_count::from_gcov_type (all
- count1
);
1085 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1086 e14
->probability
= prob1
;
1087 e14
->count
= profile_count::from_gcov_type (count1
);
1089 if (ncounts
) /* Assumed to be 0 or 1. */
1091 e23
->flags
&= ~EDGE_FALLTHRU
;
1092 e23
->flags
|= EDGE_FALSE_VALUE
;
1093 e23
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1094 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1096 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1097 e24
->probability
= prob2
;
1098 e24
->count
= profile_count::from_gcov_type (count2
);
1101 e34
->probability
= REG_BR_PROB_BASE
;
1102 e34
->count
= profile_count::from_gcov_type (all
- count1
- count2
);
1107 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1110 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1112 histogram_value histogram
;
1113 enum tree_code code
;
1114 gcov_type count
, wrong_values
, all
;
1115 tree lhs_type
, result
;
1116 gcov_type prob1
, prob2
;
1117 unsigned int i
, steps
;
1118 gcov_type count1
, count2
;
1120 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1124 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1125 if (!INTEGRAL_TYPE_P (lhs_type
))
1128 code
= gimple_assign_rhs_code (stmt
);
1130 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1133 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1139 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1140 all
+= histogram
->hvalue
.counters
[i
];
1142 wrong_values
+= histogram
->hvalue
.counters
[i
];
1143 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1144 steps
= histogram
->hdata
.intvl
.steps
;
1145 all
+= wrong_values
;
1146 count1
= histogram
->hvalue
.counters
[0];
1147 count2
= histogram
->hvalue
.counters
[1];
1149 /* Compute probability of taking the optimal path. */
1150 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1152 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1156 if (flag_profile_correction
&& count1
+ count2
> all
)
1157 all
= count1
+ count2
;
1159 gcc_assert (count1
+ count2
<= all
);
1161 /* We require that we use just subtractions in at least 50% of all
1164 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1166 count
+= histogram
->hvalue
.counters
[i
];
1167 if (count
* 2 >= all
)
1171 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1174 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1177 fprintf (dump_file
, "Mod subtract transformation on insn ");
1178 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1181 /* Compute probability of taking the optimal path(s). */
1184 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1185 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1192 /* In practice, "steps" is always 2. This interface reflects this,
1193 and will need to be changed if "steps" can change. */
1194 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1196 gimple_assign_set_rhs_from_tree (si
, result
);
1197 update_stmt (gsi_stmt (*si
));
1202 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1204 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1206 /* Returns true if node graph is initialized. This
1207 is used to test if profile_id has been created
1208 for cgraph_nodes. */
1211 coverage_node_map_initialized_p (void)
1213 return cgraph_node_map
!= 0;
1216 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1217 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1218 that the PROFILE_IDs was already assigned. */
1221 init_node_map (bool local
)
1223 struct cgraph_node
*n
;
1224 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1226 FOR_EACH_DEFINED_FUNCTION (n
)
1227 if (n
->has_gimple_body_p ())
1232 n
->profile_id
= coverage_compute_profile_id (n
);
1233 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1237 fprintf (dump_file
, "Local profile-id %i conflict"
1238 " with nodes %s %s\n",
1241 (*val
)->dump_name ());
1242 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1245 else if (!n
->profile_id
)
1249 "Node %s has no profile-id"
1250 " (profile feedback missing?)\n",
1254 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1258 "Node %s has IP profile-id %i conflict. "
1260 n
->dump_name (), n
->profile_id
);
1264 cgraph_node_map
->put (n
->profile_id
, n
);
1268 /* Delete the CGRAPH_NODE_MAP. */
1273 delete cgraph_node_map
;
1276 /* Return cgraph node for function with pid */
1279 find_func_by_profile_id (int profile_id
)
1281 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1288 /* Perform sanity check on the indirect call target. Due to race conditions,
1289 false function target may be attributed to an indirect call site. If the
1290 call expression type mismatches with the target function's type, expand_call
1291 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1292 Returns true if TARGET is considered ok for call CALL_STMT. */
1295 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1298 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1301 locus
= gimple_location (call_stmt
);
1302 if (dump_enabled_p ())
1303 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1304 "Skipping target %s with mismatching types for icall\n",
1309 /* Do transformation
1311 if (actual_callee_address == address_of_most_common_function/method)
1318 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1319 int prob
, profile_count count
, profile_count all
)
1324 gcall
*iretbnd_stmt
= NULL
;
1325 tree tmp0
, tmp1
, tmp
;
1326 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1327 tree optype
= build_pointer_type (void_type_node
);
1328 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1329 gimple_stmt_iterator gsi
;
1333 gimple_stmt_iterator psi
;
1335 cond_bb
= gimple_bb (icall_stmt
);
1336 gsi
= gsi_for_stmt (icall_stmt
);
1338 if (gimple_call_with_bounds_p (icall_stmt
) && gimple_call_lhs (icall_stmt
))
1339 iretbnd_stmt
= chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt
));
1341 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1342 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1343 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1344 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1345 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1347 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
));
1348 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1349 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1351 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1352 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1354 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1356 unlink_stmt_vdef (icall_stmt
);
1357 release_ssa_name (gimple_vdef (icall_stmt
));
1359 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1360 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1361 update_stmt (icall_stmt
);
1362 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1363 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1364 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1365 if ((dflags
& ECF_NORETURN
) != 0
1366 && should_remove_lhs_p (gimple_call_lhs (dcall_stmt
)))
1367 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1368 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1371 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1372 e_cd
= split_block (cond_bb
, cond_stmt
);
1373 dcall_bb
= e_cd
->dest
;
1374 dcall_bb
->count
= count
;
1376 e_di
= split_block (dcall_bb
, dcall_stmt
);
1377 icall_bb
= e_di
->dest
;
1378 icall_bb
->count
= all
- count
;
1380 /* Do not disturb existing EH edges from the indirect call. */
1381 if (!stmt_ends_bb_p (icall_stmt
))
1382 e_ij
= split_block (icall_bb
, icall_stmt
);
1385 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1386 /* The indirect call might be noreturn. */
1389 e_ij
->probability
= REG_BR_PROB_BASE
;
1390 e_ij
->count
= all
- count
;
1391 e_ij
= single_pred_edge (split_edge (e_ij
));
1396 join_bb
= e_ij
->dest
;
1397 join_bb
->count
= all
;
1400 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1401 e_cd
->probability
= prob
;
1402 e_cd
->count
= count
;
1404 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1405 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1406 e_ci
->count
= all
- count
;
1412 if ((dflags
& ECF_NORETURN
) != 0)
1416 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1417 e_dj
->probability
= REG_BR_PROB_BASE
;
1418 e_dj
->count
= count
;
1420 e_ij
->count
= all
- count
;
1422 e_ij
->probability
= REG_BR_PROB_BASE
;
1425 /* Insert PHI node for the call result if necessary. */
1426 if (gimple_call_lhs (icall_stmt
)
1427 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1428 && (dflags
& ECF_NORETURN
) == 0)
1430 tree result
= gimple_call_lhs (icall_stmt
);
1431 gphi
*phi
= create_phi_node (result
, join_bb
);
1432 gimple_call_set_lhs (icall_stmt
,
1433 duplicate_ssa_name (result
, icall_stmt
));
1434 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1435 gimple_call_set_lhs (dcall_stmt
,
1436 duplicate_ssa_name (result
, dcall_stmt
));
1437 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1439 /* If indirect call has following BUILT_IN_CHKP_BNDRET
1440 call then we need to make it's copy for the direct
1444 if (gimple_call_lhs (iretbnd_stmt
))
1448 if (TREE_CODE (gimple_vdef (iretbnd_stmt
)) == SSA_NAME
)
1450 unlink_stmt_vdef (iretbnd_stmt
);
1451 release_ssa_name (gimple_vdef (iretbnd_stmt
));
1453 gimple_set_vdef (iretbnd_stmt
, NULL_TREE
);
1454 gimple_set_vuse (iretbnd_stmt
, NULL_TREE
);
1455 update_stmt (iretbnd_stmt
);
1457 result
= gimple_call_lhs (iretbnd_stmt
);
1458 phi
= create_phi_node (result
, join_bb
);
1460 copy
= gimple_copy (iretbnd_stmt
);
1461 gimple_call_set_arg (copy
, 0,
1462 gimple_call_lhs (dcall_stmt
));
1463 gimple_call_set_lhs (copy
, duplicate_ssa_name (result
, copy
));
1464 gsi_insert_on_edge (e_dj
, copy
);
1465 add_phi_arg (phi
, gimple_call_lhs (copy
),
1466 e_dj
, UNKNOWN_LOCATION
);
1468 gimple_call_set_arg (iretbnd_stmt
, 0,
1469 gimple_call_lhs (icall_stmt
));
1470 gimple_call_set_lhs (iretbnd_stmt
,
1471 duplicate_ssa_name (result
, iretbnd_stmt
));
1472 psi
= gsi_for_stmt (iretbnd_stmt
);
1473 gsi_remove (&psi
, false);
1474 gsi_insert_on_edge (e_ij
, iretbnd_stmt
);
1475 add_phi_arg (phi
, gimple_call_lhs (iretbnd_stmt
),
1476 e_ij
, UNKNOWN_LOCATION
);
1478 gsi_commit_one_edge_insert (e_dj
, NULL
);
1479 gsi_commit_one_edge_insert (e_ij
, NULL
);
1483 psi
= gsi_for_stmt (iretbnd_stmt
);
1484 gsi_remove (&psi
, true);
1489 /* Build an EH edge for the direct call if necessary. */
1490 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1491 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1493 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1496 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1497 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1499 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1500 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1501 !gsi_end_p (psi
); gsi_next (&psi
))
1503 gphi
*phi
= psi
.phi ();
1504 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1505 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1508 if (!stmt_could_throw_p (dcall_stmt
))
1509 gimple_purge_dead_eh_edges (dcall_bb
);
1514 For every checked indirect/virtual call determine if most common pid of
1515 function/class method has probability more than 50%. If yes modify code of
1520 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1523 histogram_value histogram
;
1524 gcov_type val
, count
, all
, bb_all
;
1525 struct cgraph_node
*direct_call
;
1527 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1531 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1534 if (gimple_call_internal_p (stmt
))
1537 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1541 val
= histogram
->hvalue
.counters
[0];
1542 count
= histogram
->hvalue
.counters
[1];
1543 all
= histogram
->hvalue
.counters
[2];
1545 bb_all
= gimple_bb (stmt
)->count
.to_gcov_type ();
1546 /* The order of CHECK_COUNTER calls is important -
1547 since check_counter can correct the third parameter
1548 and we want to make count <= all <= bb_all. */
1549 if (check_counter (stmt
, "ic", &all
, &bb_all
, gimple_bb (stmt
)->count
)
1550 || check_counter (stmt
, "ic", &count
, &all
,
1551 profile_count::from_gcov_type (all
)))
1553 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1557 if (4 * count
<= 3 * all
)
1560 direct_call
= find_func_by_profile_id ((int)val
);
1562 if (direct_call
== NULL
)
1568 fprintf (dump_file
, "Indirect call -> direct call from other module");
1569 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1570 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1576 if (!check_ic_target (stmt
, direct_call
))
1580 fprintf (dump_file
, "Indirect call -> direct call ");
1581 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1582 fprintf (dump_file
, "=> ");
1583 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1584 fprintf (dump_file
, " transformation skipped because of type mismatch");
1585 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1587 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1593 fprintf (dump_file
, "Indirect call -> direct call ");
1594 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1595 fprintf (dump_file
, "=> ");
1596 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1597 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1598 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1599 fprintf (dump_file
, "hist->count %" PRId64
1600 " hist->all %" PRId64
"\n", count
, all
);
1606 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1607 set to the argument index for the size of the string operation. */
1610 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1612 enum built_in_function fcode
;
1614 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1615 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1616 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1621 case BUILT_IN_MEMCPY
:
1622 case BUILT_IN_MEMPCPY
:
1624 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1625 INTEGER_TYPE
, VOID_TYPE
);
1626 case BUILT_IN_MEMSET
:
1628 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1629 INTEGER_TYPE
, VOID_TYPE
);
1630 case BUILT_IN_BZERO
:
1632 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1639 /* Convert stringop (..., vcall_size)
1641 if (vcall_size == icall_size)
1642 stringop (..., icall_size);
1644 stringop (..., vcall_size);
1645 assuming we'll propagate a true constant into ICALL_SIZE later. */
1648 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, int prob
,
1649 gcov_type count
, gcov_type all
)
1654 tree tmp0
, tmp1
, vcall_size
, optype
;
1655 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1656 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1657 gimple_stmt_iterator gsi
;
1660 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1663 cond_bb
= gimple_bb (vcall_stmt
);
1664 gsi
= gsi_for_stmt (vcall_stmt
);
1666 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1667 optype
= TREE_TYPE (vcall_size
);
1669 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1670 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1671 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1672 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1674 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1675 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1677 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1678 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1680 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1682 unlink_stmt_vdef (vcall_stmt
);
1683 release_ssa_name (gimple_vdef (vcall_stmt
));
1685 gimple_set_vdef (vcall_stmt
, NULL
);
1686 gimple_set_vuse (vcall_stmt
, NULL
);
1687 update_stmt (vcall_stmt
);
1688 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1689 gimple_call_set_arg (icall_stmt
, size_arg
,
1690 fold_convert (optype
, icall_size
));
1691 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1694 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1695 e_ci
= split_block (cond_bb
, cond_stmt
);
1696 icall_bb
= e_ci
->dest
;
1697 icall_bb
->count
= profile_count::from_gcov_type (count
);
1699 e_iv
= split_block (icall_bb
, icall_stmt
);
1700 vcall_bb
= e_iv
->dest
;
1701 vcall_bb
->count
= profile_count::from_gcov_type (all
- count
);
1703 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1704 join_bb
= e_vj
->dest
;
1705 join_bb
->count
= profile_count::from_gcov_type (all
);
1707 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1708 e_ci
->probability
= prob
;
1709 e_ci
->count
= profile_count::from_gcov_type (count
);
1711 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1712 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1713 e_cv
->count
= profile_count::from_gcov_type (all
- count
);
1717 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1718 e_ij
->probability
= REG_BR_PROB_BASE
;
1719 e_ij
->count
= profile_count::from_gcov_type (count
);
1721 e_vj
->probability
= REG_BR_PROB_BASE
;
1722 e_vj
->count
= profile_count::from_gcov_type (all
- count
);
1724 /* Insert PHI node for the call result if necessary. */
1725 if (gimple_call_lhs (vcall_stmt
)
1726 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1728 tree result
= gimple_call_lhs (vcall_stmt
);
1729 gphi
*phi
= create_phi_node (result
, join_bb
);
1730 gimple_call_set_lhs (vcall_stmt
,
1731 duplicate_ssa_name (result
, vcall_stmt
));
1732 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1733 gimple_call_set_lhs (icall_stmt
,
1734 duplicate_ssa_name (result
, icall_stmt
));
1735 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1738 /* Because these are all string op builtins, they're all nothrow. */
1739 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1740 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1743 /* Find values inside STMT for that we want to measure histograms for
1744 division/modulo optimization. */
1747 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1751 enum built_in_function fcode
;
1752 histogram_value histogram
;
1753 gcov_type count
, all
, val
;
1755 unsigned int dest_align
, src_align
;
1760 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1764 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1767 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1770 blck_size
= gimple_call_arg (stmt
, size_arg
);
1771 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1774 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1778 val
= histogram
->hvalue
.counters
[0];
1779 count
= histogram
->hvalue
.counters
[1];
1780 all
= histogram
->hvalue
.counters
[2];
1781 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1783 /* We require that count is at least half of all; this means
1784 that for the transformation to fire the value must be constant
1785 at least 80% of time. */
1786 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1788 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1791 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1795 dest
= gimple_call_arg (stmt
, 0);
1796 dest_align
= get_pointer_alignment (dest
);
1797 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1800 case BUILT_IN_MEMCPY
:
1801 case BUILT_IN_MEMPCPY
:
1802 src
= gimple_call_arg (stmt
, 1);
1803 src_align
= get_pointer_alignment (src
);
1804 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1807 case BUILT_IN_MEMSET
:
1808 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1809 gimple_call_arg (stmt
, 1),
1813 case BUILT_IN_BZERO
:
1814 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1823 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1824 tree_val
= build_int_cst (get_gcov_type (), val
);
1828 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1829 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1831 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1832 TYPE_PRECISION (get_gcov_type ()), false));
1837 fprintf (dump_file
, "Single value %i stringop transformation on ",
1839 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1842 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1848 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1849 HOST_WIDE_INT
*expected_size
)
1851 histogram_value histogram
;
1852 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1855 *expected_size
= -1;
1856 else if (!histogram
->hvalue
.counters
[1])
1858 *expected_size
= -1;
1859 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1864 size
= ((histogram
->hvalue
.counters
[0]
1865 + histogram
->hvalue
.counters
[1] / 2)
1866 / histogram
->hvalue
.counters
[1]);
1867 /* Even if we can hold bigger value in SIZE, INT_MAX
1868 is safe "infinity" for code generation strategies. */
1871 *expected_size
= size
;
1872 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1875 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1878 *expected_align
= 0;
1879 else if (!histogram
->hvalue
.counters
[0])
1881 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1882 *expected_align
= 0;
1887 unsigned int alignment
;
1889 count
= histogram
->hvalue
.counters
[0];
1891 while (!(count
& alignment
)
1892 && (alignment
<= UINT_MAX
/ 2 / BITS_PER_UNIT
))
1894 *expected_align
= alignment
* BITS_PER_UNIT
;
1895 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1900 /* Find values inside STMT for that we want to measure histograms for
1901 division/modulo optimization. */
1904 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1906 tree lhs
, divisor
, op0
, type
;
1907 histogram_value hist
;
1909 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1912 lhs
= gimple_assign_lhs (stmt
);
1913 type
= TREE_TYPE (lhs
);
1914 if (!INTEGRAL_TYPE_P (type
))
1917 switch (gimple_assign_rhs_code (stmt
))
1919 case TRUNC_DIV_EXPR
:
1920 case TRUNC_MOD_EXPR
:
1921 divisor
= gimple_assign_rhs2 (stmt
);
1922 op0
= gimple_assign_rhs1 (stmt
);
1924 values
->reserve (3);
1926 if (TREE_CODE (divisor
) == SSA_NAME
)
1927 /* Check for the case where the divisor is the same value most
1929 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1930 HIST_TYPE_SINGLE_VALUE
,
1933 /* For mod, check whether it is not often a noop (or replaceable by
1934 a few subtractions). */
1935 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1936 && TYPE_UNSIGNED (type
)
1937 && TREE_CODE (divisor
) == SSA_NAME
)
1940 /* Check for a special case where the divisor is power of 2. */
1941 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1945 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1946 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1948 hist
->hdata
.intvl
.int_start
= 0;
1949 hist
->hdata
.intvl
.steps
= 2;
1950 values
->quick_push (hist
);
1959 /* Find calls inside STMT for that we want to measure histograms for
1960 indirect/virtual call optimization. */
1963 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1967 if (gimple_code (stmt
) != GIMPLE_CALL
1968 || gimple_call_internal_p (stmt
)
1969 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1972 callee
= gimple_call_fn (stmt
);
1974 values
->reserve (3);
1976 values
->quick_push (gimple_alloc_histogram_value (
1978 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1979 HIST_TYPE_INDIR_CALL_TOPN
:
1980 HIST_TYPE_INDIR_CALL
,
1986 /* Find values inside STMT for that we want to measure histograms for
1987 string operations. */
1990 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
1997 stmt
= dyn_cast
<gcall
*> (gs
);
2001 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
2004 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
2007 dest
= gimple_call_arg (stmt
, 0);
2008 blck_size
= gimple_call_arg (stmt
, size_arg
);
2010 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2012 values
->safe_push (gimple_alloc_histogram_value (cfun
,
2013 HIST_TYPE_SINGLE_VALUE
,
2015 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
2019 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2020 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
2024 /* Find values inside STMT for that we want to measure histograms and adds
2025 them to list VALUES. */
2028 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
2030 gimple_divmod_values_to_profile (stmt
, values
);
2031 gimple_stringops_values_to_profile (stmt
, values
);
2032 gimple_indirect_call_to_profile (stmt
, values
);
2036 gimple_find_values_to_profile (histogram_values
*values
)
2039 gimple_stmt_iterator gsi
;
2041 histogram_value hist
= NULL
;
2044 FOR_EACH_BB_FN (bb
, cfun
)
2045 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2046 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2048 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2050 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2054 case HIST_TYPE_INTERVAL
:
2055 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2058 case HIST_TYPE_POW2
:
2059 hist
->n_counters
= 2;
2062 case HIST_TYPE_SINGLE_VALUE
:
2063 hist
->n_counters
= 3;
2066 case HIST_TYPE_INDIR_CALL
:
2067 hist
->n_counters
= 3;
2070 case HIST_TYPE_TIME_PROFILE
:
2071 hist
->n_counters
= 1;
2074 case HIST_TYPE_AVERAGE
:
2075 hist
->n_counters
= 2;
2079 hist
->n_counters
= 1;
2082 case HIST_TYPE_INDIR_CALL_TOPN
:
2083 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2091 fprintf (dump_file
, "Stmt ");
2092 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2093 dump_histogram_value (dump_file
, hist
);