1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2015 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"
29 #include "fold-const.h"
30 #include "tree-nested.h"
33 #include "insn-config.h"
41 #include "value-prof.h"
43 #include "insn-codes.h"
46 #include "internal-fn.h"
49 #include "gimple-iterator.h"
51 #include "diagnostic.h"
52 #include "gimple-pretty-print.h"
59 #include "data-streamer.h"
62 #include "tree-chkp.h"
64 /* In this file value profile based optimizations are placed. Currently the
65 following optimizations are implemented (for more detailed descriptions
66 see comments at value_profile_transformations):
68 1) Division/modulo specialization. Provided that we can determine that the
69 operands of the division have some special properties, we may use it to
70 produce more effective code.
72 2) Indirect/virtual call specialization. If we can determine most
73 common function callee in indirect/virtual call. We can use this
74 information to improve code effectiveness (especially info for
77 3) Speculative prefetching. If we are able to determine that the difference
78 between addresses accessed by a memory reference is usually constant, we
79 may add the prefetch instructions.
80 FIXME: This transformation was removed together with RTL based value
84 Value profiling internals
85 ==========================
87 Every value profiling transformation starts with defining what values
88 to profile. There are different histogram types (see HIST_TYPE_* in
89 value-prof.h) and each transformation can request one or more histogram
90 types per GIMPLE statement. The function gimple_find_values_to_profile()
91 collects the values to profile in a vec, and adds the number of counters
92 required for the different histogram types.
94 For a -fprofile-generate run, the statements for which values should be
95 recorded, are instrumented in instrument_values(). The instrumentation
96 is done by helper functions that can be found in tree-profile.c, where
97 new types of histograms can be added if necessary.
99 After a -fprofile-use, the value profiling data is read back in by
100 compute_value_histograms() that translates the collected data to
101 histograms and attaches them to the profiled statements via
102 gimple_add_histogram_value(). Histograms are stored in a hash table
103 that is attached to every intrumented function, see VALUE_HISTOGRAMS
106 The value-profile transformations driver is the function
107 gimple_value_profile_transformations(). It traverses all statements in
108 the to-be-transformed function, and looks for statements with one or
109 more histograms attached to it. If a statement has histograms, the
110 transformation functions are called on the statement.
112 Limitations / FIXME / TODO:
113 * Only one histogram of each type can be associated with a statement.
114 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
115 (This type of histogram was originally used to implement a form of
116 stride profiling based speculative prefetching to improve SPEC2000
117 scores for memory-bound benchmarks, mcf and equake. However, this
118 was an RTL value-profiling transformation, and those have all been
120 * Some value profile transformations are done in builtins.c (?!)
121 * Updating of histograms needs some TLC.
122 * The value profiling code could be used to record analysis results
123 from non-profiling (e.g. VRP).
124 * Adding new profilers should be simplified, starting with a cleanup
125 of what-happens-where andwith making gimple_find_values_to_profile
126 and gimple_value_profile_transformations table-driven, perhaps...
129 static tree
gimple_divmod_fixed_value (gassign
*, tree
, int, gcov_type
,
131 static tree
gimple_mod_pow2 (gassign
*, int, gcov_type
, gcov_type
);
132 static tree
gimple_mod_subtract (gassign
*, int, int, int, gcov_type
,
133 gcov_type
, gcov_type
);
134 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
135 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
136 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
137 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
138 static bool gimple_ic_transform (gimple_stmt_iterator
*);
140 /* Allocate histogram value. */
143 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
144 enum hist_type type
, gimple stmt
, tree value
)
146 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
147 hist
->hvalue
.value
= value
;
148 hist
->hvalue
.stmt
= stmt
;
153 /* Hash value for histogram. */
156 histogram_hash (const void *x
)
158 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
161 /* Return nonzero if statement for histogram_value X is Y. */
164 histogram_eq (const void *x
, const void *y
)
166 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
169 /* Set histogram for STMT. */
172 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
175 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
177 if (!VALUE_HISTOGRAMS (fun
))
178 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
180 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
181 htab_hash_pointer (stmt
),
182 hist
? INSERT
: NO_INSERT
);
186 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
192 /* Get histogram list for STMT. */
195 gimple_histogram_value (struct function
*fun
, gimple stmt
)
197 if (!VALUE_HISTOGRAMS (fun
))
199 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
200 htab_hash_pointer (stmt
));
203 /* Add histogram for STMT. */
206 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
207 histogram_value hist
)
209 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
210 set_histogram_value (fun
, stmt
, hist
);
215 /* Remove histogram HIST from STMT's histogram list. */
218 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
219 histogram_value hist
)
221 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
224 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
228 while (hist2
->hvalue
.next
!= hist
)
229 hist2
= hist2
->hvalue
.next
;
230 hist2
->hvalue
.next
= hist
->hvalue
.next
;
232 free (hist
->hvalue
.counters
);
233 #ifdef ENABLE_CHECKING
234 memset (hist
, 0xab, sizeof (*hist
));
240 /* Lookup histogram of type TYPE in the STMT. */
243 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
246 histogram_value hist
;
247 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
248 hist
= hist
->hvalue
.next
)
249 if (hist
->type
== type
)
254 /* Dump information about HIST to DUMP_FILE. */
257 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
261 case HIST_TYPE_INTERVAL
:
262 fprintf (dump_file
, "Interval counter range %d -- %d",
263 hist
->hdata
.intvl
.int_start
,
264 (hist
->hdata
.intvl
.int_start
265 + hist
->hdata
.intvl
.steps
- 1));
266 if (hist
->hvalue
.counters
)
269 fprintf (dump_file
, " [");
270 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
271 fprintf (dump_file
, " %d:%" PRId64
,
272 hist
->hdata
.intvl
.int_start
+ i
,
273 (int64_t) hist
->hvalue
.counters
[i
]);
274 fprintf (dump_file
, " ] outside range:%" PRId64
,
275 (int64_t) hist
->hvalue
.counters
[i
]);
277 fprintf (dump_file
, ".\n");
281 fprintf (dump_file
, "Pow2 counter ");
282 if (hist
->hvalue
.counters
)
284 fprintf (dump_file
, "pow2:%" PRId64
286 (int64_t) hist
->hvalue
.counters
[0],
287 (int64_t) hist
->hvalue
.counters
[1]);
289 fprintf (dump_file
, ".\n");
292 case HIST_TYPE_SINGLE_VALUE
:
293 fprintf (dump_file
, "Single value ");
294 if (hist
->hvalue
.counters
)
296 fprintf (dump_file
, "value:%" PRId64
299 (int64_t) hist
->hvalue
.counters
[0],
300 (int64_t) hist
->hvalue
.counters
[1],
301 (int64_t) hist
->hvalue
.counters
[2]);
303 fprintf (dump_file
, ".\n");
306 case HIST_TYPE_AVERAGE
:
307 fprintf (dump_file
, "Average value ");
308 if (hist
->hvalue
.counters
)
310 fprintf (dump_file
, "sum:%" PRId64
312 (int64_t) hist
->hvalue
.counters
[0],
313 (int64_t) hist
->hvalue
.counters
[1]);
315 fprintf (dump_file
, ".\n");
319 fprintf (dump_file
, "IOR value ");
320 if (hist
->hvalue
.counters
)
322 fprintf (dump_file
, "ior:%" PRId64
,
323 (int64_t) hist
->hvalue
.counters
[0]);
325 fprintf (dump_file
, ".\n");
328 case HIST_TYPE_CONST_DELTA
:
329 fprintf (dump_file
, "Constant delta ");
330 if (hist
->hvalue
.counters
)
332 fprintf (dump_file
, "value:%" PRId64
335 (int64_t) hist
->hvalue
.counters
[0],
336 (int64_t) hist
->hvalue
.counters
[1],
337 (int64_t) hist
->hvalue
.counters
[2]);
339 fprintf (dump_file
, ".\n");
341 case HIST_TYPE_INDIR_CALL
:
342 fprintf (dump_file
, "Indirect call ");
343 if (hist
->hvalue
.counters
)
345 fprintf (dump_file
, "value:%" PRId64
348 (int64_t) hist
->hvalue
.counters
[0],
349 (int64_t) hist
->hvalue
.counters
[1],
350 (int64_t) hist
->hvalue
.counters
[2]);
352 fprintf (dump_file
, ".\n");
354 case HIST_TYPE_TIME_PROFILE
:
355 fprintf (dump_file
, "Time profile ");
356 if (hist
->hvalue
.counters
)
358 fprintf (dump_file
, "time:%" PRId64
,
359 (int64_t) hist
->hvalue
.counters
[0]);
361 fprintf (dump_file
, ".\n");
363 case HIST_TYPE_INDIR_CALL_TOPN
:
364 fprintf (dump_file
, "Indirect call topn ");
365 if (hist
->hvalue
.counters
)
369 fprintf (dump_file
, "accu:%" PRId64
, hist
->hvalue
.counters
[0]);
370 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
372 fprintf (dump_file
, " target:%" PRId64
" value:%" PRId64
,
373 (int64_t) hist
->hvalue
.counters
[i
],
374 (int64_t) hist
->hvalue
.counters
[i
+1]);
377 fprintf (dump_file
, ".\n");
384 /* Dump information about HIST to DUMP_FILE. */
387 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
392 bp
= bitpack_create (ob
->main_stream
);
393 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
394 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
395 streamer_write_bitpack (&bp
);
398 case HIST_TYPE_INTERVAL
:
399 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
400 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
405 for (i
= 0; i
< hist
->n_counters
; i
++)
406 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
407 if (hist
->hvalue
.next
)
408 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
410 /* Dump information about HIST to DUMP_FILE. */
413 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
416 unsigned int ncounters
= 0;
419 histogram_value new_val
;
421 histogram_value
*next_p
= NULL
;
425 bp
= streamer_read_bitpack (ib
);
426 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
427 next
= bp_unpack_value (&bp
, 1);
428 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
431 case HIST_TYPE_INTERVAL
:
432 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
433 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
434 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
438 case HIST_TYPE_AVERAGE
:
442 case HIST_TYPE_SINGLE_VALUE
:
443 case HIST_TYPE_INDIR_CALL
:
447 case HIST_TYPE_CONST_DELTA
:
452 case HIST_TYPE_TIME_PROFILE
:
456 case HIST_TYPE_INDIR_CALL_TOPN
:
457 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
463 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
464 new_val
->n_counters
= ncounters
;
465 for (i
= 0; i
< ncounters
; i
++)
466 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
468 gimple_add_histogram_value (cfun
, stmt
, new_val
);
471 next_p
= &new_val
->hvalue
.next
;
476 /* Dump all histograms attached to STMT to DUMP_FILE. */
479 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
481 histogram_value hist
;
482 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
483 dump_histogram_value (dump_file
, hist
);
486 /* Remove all histograms associated with STMT. */
489 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
492 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
493 gimple_remove_histogram_value (fun
, stmt
, val
);
496 /* Duplicate all histograms associates with OSTMT to STMT. */
499 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
500 struct function
*ofun
, gimple ostmt
)
503 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
505 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
506 memcpy (new_val
, val
, sizeof (*val
));
507 new_val
->hvalue
.stmt
= stmt
;
508 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
509 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
510 gimple_add_histogram_value (fun
, stmt
, new_val
);
515 /* Move all histograms associated with OSTMT to STMT. */
518 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
520 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
523 /* The following three statements can't be reordered,
524 because histogram hashtab relies on stmt field value
525 for finding the exact slot. */
526 set_histogram_value (fun
, ostmt
, NULL
);
527 for (; val
!= NULL
; val
= val
->hvalue
.next
)
528 val
->hvalue
.stmt
= stmt
;
529 set_histogram_value (fun
, stmt
, val
);
533 static bool error_found
= false;
535 /* Helper function for verify_histograms. For each histogram reachable via htab
536 walk verify that it was reached via statement walk. */
539 visit_hist (void **slot
, void *data
)
541 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
542 histogram_value hist
= *(histogram_value
*) slot
;
544 if (!visited
->contains (hist
)
545 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
547 error ("dead histogram");
548 dump_histogram_value (stderr
, hist
);
549 debug_gimple_stmt (hist
->hvalue
.stmt
);
556 /* Verify sanity of the histograms. */
559 verify_histograms (void)
562 gimple_stmt_iterator gsi
;
563 histogram_value hist
;
566 hash_set
<histogram_value
> visited_hists
;
567 FOR_EACH_BB_FN (bb
, cfun
)
568 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
570 gimple stmt
= gsi_stmt (gsi
);
572 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
573 hist
= hist
->hvalue
.next
)
575 if (hist
->hvalue
.stmt
!= stmt
)
577 error ("Histogram value statement does not correspond to "
578 "the statement it is associated with");
579 debug_gimple_stmt (stmt
);
580 dump_histogram_value (stderr
, hist
);
583 visited_hists
.add (hist
);
586 if (VALUE_HISTOGRAMS (cfun
))
587 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
589 internal_error ("verify_histograms failed");
592 /* Helper function for verify_histograms. For each histogram reachable via htab
593 walk verify that it was reached via statement walk. */
596 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
598 histogram_value hist
= *(histogram_value
*) slot
;
599 free (hist
->hvalue
.counters
);
600 #ifdef ENABLE_CHECKING
601 memset (hist
, 0xab, sizeof (*hist
));
608 free_histograms (void)
610 if (VALUE_HISTOGRAMS (cfun
))
612 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
613 htab_delete (VALUE_HISTOGRAMS (cfun
));
614 VALUE_HISTOGRAMS (cfun
) = NULL
;
619 /* The overall number of invocations of the counter should match
620 execution count of basic block. Report it as error rather than
621 internal error as it might mean that user has misused the profile
625 check_counter (gimple stmt
, const char * name
,
626 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
628 if (*all
!= bb_count
|| *count
> *all
)
631 locus
= (stmt
!= NULL
)
632 ? gimple_location (stmt
)
633 : DECL_SOURCE_LOCATION (current_function_decl
);
634 if (flag_profile_correction
)
636 if (dump_enabled_p ())
637 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
638 "correcting inconsistent value profile: %s "
639 "profiler overall count (%d) does not match BB "
640 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
648 error_at (locus
, "corrupted value profile: %s "
649 "profile counter (%d out of %d) inconsistent with "
650 "basic-block count (%d)",
663 /* GIMPLE based transformations. */
666 gimple_value_profile_transformations (void)
669 gimple_stmt_iterator gsi
;
670 bool changed
= false;
672 FOR_EACH_BB_FN (bb
, cfun
)
674 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
676 gimple stmt
= gsi_stmt (gsi
);
677 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
683 fprintf (dump_file
, "Trying transformations on stmt ");
684 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
685 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
688 /* Transformations: */
689 /* The order of things in this conditional controls which
690 transformation is used when more than one is applicable. */
691 /* It is expected that any code added by the transformations
692 will be added before the current statement, and that the
693 current statement remain valid (although possibly
694 modified) upon return. */
695 if (gimple_mod_subtract_transform (&gsi
)
696 || gimple_divmod_fixed_value_transform (&gsi
)
697 || gimple_mod_pow2_value_transform (&gsi
)
698 || gimple_stringops_transform (&gsi
)
699 || gimple_ic_transform (&gsi
))
701 stmt
= gsi_stmt (gsi
);
703 /* Original statement may no longer be in the same block. */
704 if (bb
!= gimple_bb (stmt
))
706 bb
= gimple_bb (stmt
);
707 gsi
= gsi_for_stmt (stmt
);
722 /* Generate code for transformation 1 (with parent gimple assignment
723 STMT and probability of taking the optimal path PROB, which is
724 equivalent to COUNT/ALL within roundoff error). This generates the
725 result into a temp and returns the temp; it does not replace or
726 alter the original STMT. */
729 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, int prob
,
730 gcov_type count
, gcov_type all
)
732 gassign
*stmt1
, *stmt2
;
734 tree tmp0
, tmp1
, tmp2
;
735 gimple bb1end
, bb2end
, bb3end
;
736 basic_block bb
, bb2
, bb3
, bb4
;
737 tree optype
, op1
, op2
;
738 edge e12
, e13
, e23
, e24
, e34
;
739 gimple_stmt_iterator gsi
;
741 gcc_assert (is_gimple_assign (stmt
)
742 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
743 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
745 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
746 op1
= gimple_assign_rhs1 (stmt
);
747 op2
= gimple_assign_rhs2 (stmt
);
749 bb
= gimple_bb (stmt
);
750 gsi
= gsi_for_stmt (stmt
);
752 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
753 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
754 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
755 stmt2
= gimple_build_assign (tmp1
, op2
);
756 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
757 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
758 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
759 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
762 tmp2
= create_tmp_reg (optype
, "PROF");
763 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
764 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
767 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
768 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
772 /* Edge e23 connects bb2 to bb3, etc. */
773 e12
= split_block (bb
, bb1end
);
776 e23
= split_block (bb2
, bb2end
);
778 bb3
->count
= all
- count
;
779 e34
= split_block (bb3
, bb3end
);
783 e12
->flags
&= ~EDGE_FALLTHRU
;
784 e12
->flags
|= EDGE_FALSE_VALUE
;
785 e12
->probability
= prob
;
788 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
789 e13
->probability
= REG_BR_PROB_BASE
- prob
;
790 e13
->count
= all
- count
;
794 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
795 e24
->probability
= REG_BR_PROB_BASE
;
798 e34
->probability
= REG_BR_PROB_BASE
;
799 e34
->count
= all
- count
;
805 /* Do transform 1) on INSN if applicable. */
808 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
810 histogram_value histogram
;
812 gcov_type val
, count
, all
;
813 tree result
, value
, tree_val
;
817 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
821 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
824 code
= gimple_assign_rhs_code (stmt
);
826 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
829 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
830 HIST_TYPE_SINGLE_VALUE
);
834 value
= histogram
->hvalue
.value
;
835 val
= histogram
->hvalue
.counters
[0];
836 count
= histogram
->hvalue
.counters
[1];
837 all
= histogram
->hvalue
.counters
[2];
838 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
840 /* We require that count is at least half of all; this means
841 that for the transformation to fire the value must be constant
842 at least 50% of time (and 75% gives the guarantee of usage). */
843 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
845 || optimize_bb_for_size_p (gimple_bb (stmt
)))
848 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
851 /* Compute probability of taking the optimal path. */
853 prob
= GCOV_COMPUTE_SCALE (count
, all
);
857 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
858 tree_val
= build_int_cst (get_gcov_type (), val
);
862 a
[0] = (unsigned HOST_WIDE_INT
) val
;
863 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
865 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
866 TYPE_PRECISION (get_gcov_type ()), false));
868 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
872 fprintf (dump_file
, "Div/mod by constant ");
873 print_generic_expr (dump_file
, value
, TDF_SLIM
);
874 fprintf (dump_file
, "=");
875 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
876 fprintf (dump_file
, " transformation on insn ");
877 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
880 gimple_assign_set_rhs_from_tree (si
, result
);
881 update_stmt (gsi_stmt (*si
));
886 /* Generate code for transformation 2 (with parent gimple assign STMT and
887 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
888 within roundoff error). This generates the result into a temp and returns
889 the temp; it does not replace or alter the original STMT. */
891 gimple_mod_pow2 (gassign
*stmt
, int prob
, gcov_type count
, gcov_type all
)
893 gassign
*stmt1
, *stmt2
, *stmt3
;
896 gimple bb1end
, bb2end
, bb3end
;
897 basic_block bb
, bb2
, bb3
, bb4
;
898 tree optype
, op1
, op2
;
899 edge e12
, e13
, e23
, e24
, e34
;
900 gimple_stmt_iterator gsi
;
903 gcc_assert (is_gimple_assign (stmt
)
904 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
906 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
907 op1
= gimple_assign_rhs1 (stmt
);
908 op2
= gimple_assign_rhs2 (stmt
);
910 bb
= gimple_bb (stmt
);
911 gsi
= gsi_for_stmt (stmt
);
913 result
= create_tmp_reg (optype
, "PROF");
914 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
915 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
916 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
917 build_int_cst (optype
, -1));
918 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
919 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
920 NULL_TREE
, NULL_TREE
);
921 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
922 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
923 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
926 /* tmp2 == op2-1 inherited from previous block. */
927 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
928 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
931 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
933 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
937 /* Edge e23 connects bb2 to bb3, etc. */
938 e12
= split_block (bb
, bb1end
);
941 e23
= split_block (bb2
, bb2end
);
943 bb3
->count
= all
- count
;
944 e34
= split_block (bb3
, bb3end
);
948 e12
->flags
&= ~EDGE_FALLTHRU
;
949 e12
->flags
|= EDGE_FALSE_VALUE
;
950 e12
->probability
= prob
;
953 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
954 e13
->probability
= REG_BR_PROB_BASE
- prob
;
955 e13
->count
= all
- count
;
959 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
960 e24
->probability
= REG_BR_PROB_BASE
;
963 e34
->probability
= REG_BR_PROB_BASE
;
964 e34
->count
= all
- count
;
969 /* Do transform 2) on INSN if applicable. */
971 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
973 histogram_value histogram
;
975 gcov_type count
, wrong_values
, all
;
976 tree lhs_type
, result
, value
;
980 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
984 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
985 if (!INTEGRAL_TYPE_P (lhs_type
))
988 code
= gimple_assign_rhs_code (stmt
);
990 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
993 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
997 value
= histogram
->hvalue
.value
;
998 wrong_values
= histogram
->hvalue
.counters
[0];
999 count
= histogram
->hvalue
.counters
[1];
1001 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1003 /* We require that we hit a power of 2 at least half of all evaluations. */
1004 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
1005 || count
< wrong_values
1006 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1011 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
1012 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1015 /* Compute probability of taking the optimal path. */
1016 all
= count
+ wrong_values
;
1018 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1022 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1026 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1028 gimple_assign_set_rhs_from_tree (si
, result
);
1029 update_stmt (gsi_stmt (*si
));
1034 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1035 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1036 supported and this is built into this interface. The probabilities of taking
1037 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1038 COUNT2/ALL respectively within roundoff error). This generates the
1039 result into a temp and returns the temp; it does not replace or alter
1040 the original STMT. */
1041 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1044 gimple_mod_subtract (gassign
*stmt
, int prob1
, int prob2
, int ncounts
,
1045 gcov_type count1
, gcov_type count2
, gcov_type all
)
1051 gimple bb1end
, bb2end
= NULL
, bb3end
;
1052 basic_block bb
, bb2
, bb3
, bb4
;
1053 tree optype
, op1
, op2
;
1054 edge e12
, e23
= 0, e24
, e34
, e14
;
1055 gimple_stmt_iterator gsi
;
1058 gcc_assert (is_gimple_assign (stmt
)
1059 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1061 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1062 op1
= gimple_assign_rhs1 (stmt
);
1063 op2
= gimple_assign_rhs2 (stmt
);
1065 bb
= gimple_bb (stmt
);
1066 gsi
= gsi_for_stmt (stmt
);
1068 result
= create_tmp_reg (optype
, "PROF");
1069 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1070 stmt1
= gimple_build_assign (result
, op1
);
1071 stmt2
= gimple_build_assign (tmp1
, op2
);
1072 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1073 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1074 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1075 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1078 if (ncounts
) /* Assumed to be 0 or 1 */
1080 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1081 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1082 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1083 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1087 /* Fallback case. */
1088 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1090 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1094 /* Edge e23 connects bb2 to bb3, etc. */
1095 /* However block 3 is optional; if it is not there, references
1096 to 3 really refer to block 2. */
1097 e12
= split_block (bb
, bb1end
);
1099 bb2
->count
= all
- count1
;
1101 if (ncounts
) /* Assumed to be 0 or 1. */
1103 e23
= split_block (bb2
, bb2end
);
1105 bb3
->count
= all
- count1
- count2
;
1108 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1112 e12
->flags
&= ~EDGE_FALLTHRU
;
1113 e12
->flags
|= EDGE_FALSE_VALUE
;
1114 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1115 e12
->count
= all
- count1
;
1117 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1118 e14
->probability
= prob1
;
1119 e14
->count
= count1
;
1121 if (ncounts
) /* Assumed to be 0 or 1. */
1123 e23
->flags
&= ~EDGE_FALLTHRU
;
1124 e23
->flags
|= EDGE_FALSE_VALUE
;
1125 e23
->count
= all
- count1
- count2
;
1126 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1128 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1129 e24
->probability
= prob2
;
1130 e24
->count
= count2
;
1133 e34
->probability
= REG_BR_PROB_BASE
;
1134 e34
->count
= all
- count1
- count2
;
1140 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1143 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1145 histogram_value histogram
;
1146 enum tree_code code
;
1147 gcov_type count
, wrong_values
, all
;
1148 tree lhs_type
, result
;
1149 gcov_type prob1
, prob2
;
1150 unsigned int i
, steps
;
1151 gcov_type count1
, count2
;
1154 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1158 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1159 if (!INTEGRAL_TYPE_P (lhs_type
))
1162 code
= gimple_assign_rhs_code (stmt
);
1164 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1167 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1173 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1174 all
+= histogram
->hvalue
.counters
[i
];
1176 wrong_values
+= histogram
->hvalue
.counters
[i
];
1177 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1178 steps
= histogram
->hdata
.intvl
.steps
;
1179 all
+= wrong_values
;
1180 count1
= histogram
->hvalue
.counters
[0];
1181 count2
= histogram
->hvalue
.counters
[1];
1183 /* Compute probability of taking the optimal path. */
1184 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1186 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1190 if (flag_profile_correction
&& count1
+ count2
> all
)
1191 all
= count1
+ count2
;
1193 gcc_assert (count1
+ count2
<= all
);
1195 /* We require that we use just subtractions in at least 50% of all
1198 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1200 count
+= histogram
->hvalue
.counters
[i
];
1201 if (count
* 2 >= all
)
1205 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1208 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1211 fprintf (dump_file
, "Mod subtract transformation on insn ");
1212 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1215 /* Compute probability of taking the optimal path(s). */
1218 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1219 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1226 /* In practice, "steps" is always 2. This interface reflects this,
1227 and will need to be changed if "steps" can change. */
1228 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1230 gimple_assign_set_rhs_from_tree (si
, result
);
1231 update_stmt (gsi_stmt (*si
));
1236 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1238 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1240 /* Returns true if node graph is initialized. This
1241 is used to test if profile_id has been created
1242 for cgraph_nodes. */
1245 coverage_node_map_initialized_p (void)
1247 return cgraph_node_map
!= 0;
1250 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1251 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1252 that the PROFILE_IDs was already assigned. */
1255 init_node_map (bool local
)
1257 struct cgraph_node
*n
;
1258 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1260 FOR_EACH_DEFINED_FUNCTION (n
)
1261 if (n
->has_gimple_body_p ())
1266 n
->profile_id
= coverage_compute_profile_id (n
);
1267 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1271 fprintf (dump_file
, "Local profile-id %i conflict"
1272 " with nodes %s/%i %s/%i\n",
1278 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1281 else if (!n
->profile_id
)
1285 "Node %s/%i has no profile-id"
1286 " (profile feedback missing?)\n",
1291 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1295 "Node %s/%i has IP profile-id %i conflict. "
1303 cgraph_node_map
->put (n
->profile_id
, n
);
1307 /* Delete the CGRAPH_NODE_MAP. */
1312 delete cgraph_node_map
;
1315 /* Return cgraph node for function with pid */
1318 find_func_by_profile_id (int profile_id
)
1320 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1327 /* Perform sanity check on the indirect call target. Due to race conditions,
1328 false function target may be attributed to an indirect call site. If the
1329 call expression type mismatches with the target function's type, expand_call
1330 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1331 Returns true if TARGET is considered ok for call CALL_STMT. */
1334 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1337 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1340 locus
= gimple_location (call_stmt
);
1341 if (dump_enabled_p ())
1342 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1343 "Skipping target %s with mismatching types for icall\n",
1348 /* Do transformation
1350 if (actual_callee_address == address_of_most_common_function/method)
1357 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1358 int prob
, gcov_type count
, gcov_type all
)
1363 gcall
*iretbnd_stmt
= NULL
;
1364 tree tmp0
, tmp1
, tmp
;
1365 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1366 tree optype
= build_pointer_type (void_type_node
);
1367 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1368 gimple_stmt_iterator gsi
;
1372 gimple_stmt_iterator psi
;
1374 cond_bb
= gimple_bb (icall_stmt
);
1375 gsi
= gsi_for_stmt (icall_stmt
);
1377 if (gimple_call_with_bounds_p (icall_stmt
) && gimple_call_lhs (icall_stmt
))
1378 iretbnd_stmt
= chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt
));
1380 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1381 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1382 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1383 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1384 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1386 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1387 current_function_decl
));
1388 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1389 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1391 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1392 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1394 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1395 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1396 update_stmt (icall_stmt
);
1397 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1398 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1399 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1400 if ((dflags
& ECF_NORETURN
) != 0)
1401 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1402 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1405 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1406 e_cd
= split_block (cond_bb
, cond_stmt
);
1407 dcall_bb
= e_cd
->dest
;
1408 dcall_bb
->count
= count
;
1410 e_di
= split_block (dcall_bb
, dcall_stmt
);
1411 icall_bb
= e_di
->dest
;
1412 icall_bb
->count
= all
- count
;
1414 /* Do not disturb existing EH edges from the indirect call. */
1415 if (!stmt_ends_bb_p (icall_stmt
))
1416 e_ij
= split_block (icall_bb
, icall_stmt
);
1419 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1420 /* The indirect call might be noreturn. */
1423 e_ij
->probability
= REG_BR_PROB_BASE
;
1424 e_ij
->count
= all
- count
;
1425 e_ij
= single_pred_edge (split_edge (e_ij
));
1430 join_bb
= e_ij
->dest
;
1431 join_bb
->count
= all
;
1434 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1435 e_cd
->probability
= prob
;
1436 e_cd
->count
= count
;
1438 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1439 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1440 e_ci
->count
= all
- count
;
1446 if ((dflags
& ECF_NORETURN
) != 0)
1450 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1451 e_dj
->probability
= REG_BR_PROB_BASE
;
1452 e_dj
->count
= count
;
1454 e_ij
->count
= all
- count
;
1456 e_ij
->probability
= REG_BR_PROB_BASE
;
1459 /* Insert PHI node for the call result if necessary. */
1460 if (gimple_call_lhs (icall_stmt
)
1461 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1462 && (dflags
& ECF_NORETURN
) == 0)
1464 tree result
= gimple_call_lhs (icall_stmt
);
1465 gphi
*phi
= create_phi_node (result
, join_bb
);
1466 gimple_call_set_lhs (icall_stmt
,
1467 duplicate_ssa_name (result
, icall_stmt
));
1468 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1469 gimple_call_set_lhs (dcall_stmt
,
1470 duplicate_ssa_name (result
, dcall_stmt
));
1471 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1473 /* If indirect call has following BUILT_IN_CHKP_BNDRET
1474 call then we need to make it's copy for the direct
1478 if (gimple_call_lhs (iretbnd_stmt
))
1482 gimple_set_vdef (iretbnd_stmt
, NULL_TREE
);
1483 gimple_set_vuse (iretbnd_stmt
, NULL_TREE
);
1484 update_stmt (iretbnd_stmt
);
1486 result
= gimple_call_lhs (iretbnd_stmt
);
1487 phi
= create_phi_node (result
, join_bb
);
1489 copy
= gimple_copy (iretbnd_stmt
);
1490 gimple_call_set_arg (copy
, 0,
1491 gimple_call_lhs (dcall_stmt
));
1492 gimple_call_set_lhs (copy
, duplicate_ssa_name (result
, copy
));
1493 gsi_insert_on_edge (e_dj
, copy
);
1494 add_phi_arg (phi
, gimple_call_lhs (copy
),
1495 e_dj
, UNKNOWN_LOCATION
);
1497 gimple_call_set_arg (iretbnd_stmt
, 0,
1498 gimple_call_lhs (icall_stmt
));
1499 gimple_call_set_lhs (iretbnd_stmt
,
1500 duplicate_ssa_name (result
, iretbnd_stmt
));
1501 psi
= gsi_for_stmt (iretbnd_stmt
);
1502 gsi_remove (&psi
, false);
1503 gsi_insert_on_edge (e_ij
, iretbnd_stmt
);
1504 add_phi_arg (phi
, gimple_call_lhs (iretbnd_stmt
),
1505 e_ij
, UNKNOWN_LOCATION
);
1507 gsi_commit_one_edge_insert (e_dj
, NULL
);
1508 gsi_commit_one_edge_insert (e_ij
, NULL
);
1512 psi
= gsi_for_stmt (iretbnd_stmt
);
1513 gsi_remove (&psi
, true);
1518 /* Build an EH edge for the direct call if necessary. */
1519 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1520 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1522 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1525 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1526 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1528 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1529 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1530 !gsi_end_p (psi
); gsi_next (&psi
))
1532 gphi
*phi
= psi
.phi ();
1533 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1534 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1537 if (!stmt_could_throw_p (dcall_stmt
))
1538 gimple_purge_dead_eh_edges (dcall_bb
);
1543 For every checked indirect/virtual call determine if most common pid of
1544 function/class method has probability more than 50%. If yes modify code of
1549 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1552 histogram_value histogram
;
1553 gcov_type val
, count
, all
, bb_all
;
1554 struct cgraph_node
*direct_call
;
1556 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1560 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1563 if (gimple_call_internal_p (stmt
))
1566 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1570 val
= histogram
->hvalue
.counters
[0];
1571 count
= histogram
->hvalue
.counters
[1];
1572 all
= histogram
->hvalue
.counters
[2];
1574 bb_all
= gimple_bb (stmt
)->count
;
1575 /* The order of CHECK_COUNTER calls is important -
1576 since check_counter can correct the third parameter
1577 and we want to make count <= all <= bb_all. */
1578 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1579 || check_counter (stmt
, "ic", &count
, &all
, all
))
1581 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1585 if (4 * count
<= 3 * all
)
1588 direct_call
= find_func_by_profile_id ((int)val
);
1590 if (direct_call
== NULL
)
1596 fprintf (dump_file
, "Indirect call -> direct call from other module");
1597 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1598 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1604 if (!check_ic_target (stmt
, direct_call
))
1608 fprintf (dump_file
, "Indirect call -> direct call ");
1609 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1610 fprintf (dump_file
, "=> ");
1611 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1612 fprintf (dump_file
, " transformation skipped because of type mismatch");
1613 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1615 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1621 fprintf (dump_file
, "Indirect call -> direct call ");
1622 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1623 fprintf (dump_file
, "=> ");
1624 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1625 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1626 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1627 fprintf (dump_file
, "hist->count %" PRId64
1628 " hist->all %" PRId64
"\n", count
, all
);
1634 /* Return true if the stringop CALL with FNDECL shall be profiled.
1635 SIZE_ARG be set to the argument index for the size of the string
1639 interesting_stringop_to_profile_p (tree fndecl
, gcall
*call
, int *size_arg
)
1641 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1643 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1644 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1649 case BUILT_IN_MEMCPY
:
1650 case BUILT_IN_MEMPCPY
:
1652 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1653 INTEGER_TYPE
, VOID_TYPE
);
1654 case BUILT_IN_MEMSET
:
1656 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1657 INTEGER_TYPE
, VOID_TYPE
);
1658 case BUILT_IN_BZERO
:
1660 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1667 /* Convert stringop (..., vcall_size)
1669 if (vcall_size == icall_size)
1670 stringop (..., icall_size);
1672 stringop (..., vcall_size);
1673 assuming we'll propagate a true constant into ICALL_SIZE later. */
1676 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, int prob
,
1677 gcov_type count
, gcov_type all
)
1682 tree tmp0
, tmp1
, vcall_size
, optype
;
1683 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1684 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1685 gimple_stmt_iterator gsi
;
1689 fndecl
= gimple_call_fndecl (vcall_stmt
);
1690 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1693 cond_bb
= gimple_bb (vcall_stmt
);
1694 gsi
= gsi_for_stmt (vcall_stmt
);
1696 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1697 optype
= TREE_TYPE (vcall_size
);
1699 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1700 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1701 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1702 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1704 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1705 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1707 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1708 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1710 gimple_set_vdef (vcall_stmt
, NULL
);
1711 gimple_set_vuse (vcall_stmt
, NULL
);
1712 update_stmt (vcall_stmt
);
1713 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1714 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1715 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1718 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1719 e_ci
= split_block (cond_bb
, cond_stmt
);
1720 icall_bb
= e_ci
->dest
;
1721 icall_bb
->count
= count
;
1723 e_iv
= split_block (icall_bb
, icall_stmt
);
1724 vcall_bb
= e_iv
->dest
;
1725 vcall_bb
->count
= all
- count
;
1727 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1728 join_bb
= e_vj
->dest
;
1729 join_bb
->count
= all
;
1731 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1732 e_ci
->probability
= prob
;
1733 e_ci
->count
= count
;
1735 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1736 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1737 e_cv
->count
= all
- count
;
1741 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1742 e_ij
->probability
= REG_BR_PROB_BASE
;
1743 e_ij
->count
= count
;
1745 e_vj
->probability
= REG_BR_PROB_BASE
;
1746 e_vj
->count
= all
- count
;
1748 /* Insert PHI node for the call result if necessary. */
1749 if (gimple_call_lhs (vcall_stmt
)
1750 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1752 tree result
= gimple_call_lhs (vcall_stmt
);
1753 gphi
*phi
= create_phi_node (result
, join_bb
);
1754 gimple_call_set_lhs (vcall_stmt
,
1755 duplicate_ssa_name (result
, vcall_stmt
));
1756 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1757 gimple_call_set_lhs (icall_stmt
,
1758 duplicate_ssa_name (result
, icall_stmt
));
1759 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1762 /* Because these are all string op builtins, they're all nothrow. */
1763 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1764 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1767 /* Find values inside STMT for that we want to measure histograms for
1768 division/modulo optimization. */
1770 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1775 enum built_in_function fcode
;
1776 histogram_value histogram
;
1777 gcov_type count
, all
, val
;
1779 unsigned int dest_align
, src_align
;
1784 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1787 fndecl
= gimple_call_fndecl (stmt
);
1790 fcode
= DECL_FUNCTION_CODE (fndecl
);
1791 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1794 blck_size
= gimple_call_arg (stmt
, size_arg
);
1795 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1798 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1801 val
= histogram
->hvalue
.counters
[0];
1802 count
= histogram
->hvalue
.counters
[1];
1803 all
= histogram
->hvalue
.counters
[2];
1804 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1805 /* We require that count is at least half of all; this means
1806 that for the transformation to fire the value must be constant
1807 at least 80% of time. */
1808 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1810 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1813 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1816 dest
= gimple_call_arg (stmt
, 0);
1817 dest_align
= get_pointer_alignment (dest
);
1820 case BUILT_IN_MEMCPY
:
1821 case BUILT_IN_MEMPCPY
:
1822 src
= gimple_call_arg (stmt
, 1);
1823 src_align
= get_pointer_alignment (src
);
1824 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1827 case BUILT_IN_MEMSET
:
1828 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1829 gimple_call_arg (stmt
, 1),
1833 case BUILT_IN_BZERO
:
1834 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1842 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1843 tree_val
= build_int_cst (get_gcov_type (), val
);
1847 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1848 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1850 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1851 TYPE_PRECISION (get_gcov_type ()), false));
1856 fprintf (dump_file
, "Single value %i stringop transformation on ",
1858 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1860 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1866 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1867 HOST_WIDE_INT
*expected_size
)
1869 histogram_value histogram
;
1870 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1872 *expected_size
= -1;
1873 else if (!histogram
->hvalue
.counters
[1])
1875 *expected_size
= -1;
1876 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1881 size
= ((histogram
->hvalue
.counters
[0]
1882 + histogram
->hvalue
.counters
[1] / 2)
1883 / histogram
->hvalue
.counters
[1]);
1884 /* Even if we can hold bigger value in SIZE, INT_MAX
1885 is safe "infinity" for code generation strategies. */
1888 *expected_size
= size
;
1889 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1891 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1893 *expected_align
= 0;
1894 else if (!histogram
->hvalue
.counters
[0])
1896 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1897 *expected_align
= 0;
1904 count
= histogram
->hvalue
.counters
[0];
1906 while (!(count
& alignment
)
1907 && (alignment
* 2 * BITS_PER_UNIT
))
1909 *expected_align
= alignment
* BITS_PER_UNIT
;
1910 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1915 /* Find values inside STMT for that we want to measure histograms for
1916 division/modulo optimization. */
1918 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1920 tree lhs
, divisor
, op0
, type
;
1921 histogram_value hist
;
1923 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1926 lhs
= gimple_assign_lhs (stmt
);
1927 type
= TREE_TYPE (lhs
);
1928 if (!INTEGRAL_TYPE_P (type
))
1931 switch (gimple_assign_rhs_code (stmt
))
1933 case TRUNC_DIV_EXPR
:
1934 case TRUNC_MOD_EXPR
:
1935 divisor
= gimple_assign_rhs2 (stmt
);
1936 op0
= gimple_assign_rhs1 (stmt
);
1938 values
->reserve (3);
1940 if (TREE_CODE (divisor
) == SSA_NAME
)
1941 /* Check for the case where the divisor is the same value most
1943 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1944 HIST_TYPE_SINGLE_VALUE
,
1947 /* For mod, check whether it is not often a noop (or replaceable by
1948 a few subtractions). */
1949 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1950 && TYPE_UNSIGNED (type
))
1953 /* Check for a special case where the divisor is power of 2. */
1954 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1958 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1959 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1961 hist
->hdata
.intvl
.int_start
= 0;
1962 hist
->hdata
.intvl
.steps
= 2;
1963 values
->quick_push (hist
);
1972 /* Find calls inside STMT for that we want to measure histograms for
1973 indirect/virtual call optimization. */
1976 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1980 if (gimple_code (stmt
) != GIMPLE_CALL
1981 || gimple_call_internal_p (stmt
)
1982 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1985 callee
= gimple_call_fn (stmt
);
1987 values
->reserve (3);
1989 values
->quick_push (gimple_alloc_histogram_value (
1991 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1992 HIST_TYPE_INDIR_CALL_TOPN
:
1993 HIST_TYPE_INDIR_CALL
,
1999 /* Find values inside STMT for that we want to measure histograms for
2000 string operations. */
2002 gimple_stringops_values_to_profile (gimple gs
, histogram_values
*values
)
2010 stmt
= dyn_cast
<gcall
*> (gs
);
2013 fndecl
= gimple_call_fndecl (stmt
);
2017 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
2020 dest
= gimple_call_arg (stmt
, 0);
2021 blck_size
= gimple_call_arg (stmt
, size_arg
);
2023 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2025 values
->safe_push (gimple_alloc_histogram_value (cfun
,
2026 HIST_TYPE_SINGLE_VALUE
,
2028 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
2031 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2032 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
2036 /* Find values inside STMT for that we want to measure histograms and adds
2037 them to list VALUES. */
2040 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
2042 gimple_divmod_values_to_profile (stmt
, values
);
2043 gimple_stringops_values_to_profile (stmt
, values
);
2044 gimple_indirect_call_to_profile (stmt
, values
);
2048 gimple_find_values_to_profile (histogram_values
*values
)
2051 gimple_stmt_iterator gsi
;
2053 histogram_value hist
= NULL
;
2056 FOR_EACH_BB_FN (bb
, cfun
)
2057 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2058 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2060 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2062 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2066 case HIST_TYPE_INTERVAL
:
2067 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2070 case HIST_TYPE_POW2
:
2071 hist
->n_counters
= 2;
2074 case HIST_TYPE_SINGLE_VALUE
:
2075 hist
->n_counters
= 3;
2078 case HIST_TYPE_CONST_DELTA
:
2079 hist
->n_counters
= 4;
2082 case HIST_TYPE_INDIR_CALL
:
2083 hist
->n_counters
= 3;
2086 case HIST_TYPE_TIME_PROFILE
:
2087 hist
->n_counters
= 1;
2090 case HIST_TYPE_AVERAGE
:
2091 hist
->n_counters
= 2;
2095 hist
->n_counters
= 1;
2098 case HIST_TYPE_INDIR_CALL_TOPN
:
2099 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2107 fprintf (dump_file
, "Stmt ");
2108 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2109 dump_histogram_value (dump_file
, hist
);