1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2016 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 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
99 (This type of histogram was originally used to implement a form of
100 stride profiling based speculative prefetching to improve SPEC2000
101 scores for memory-bound benchmarks, mcf and equake. However, this
102 was an RTL value-profiling transformation, and those have all been
104 * Some value profile transformations are done in builtins.c (?!)
105 * Updating of histograms needs some TLC.
106 * The value profiling code could be used to record analysis results
107 from non-profiling (e.g. VRP).
108 * Adding new profilers should be simplified, starting with a cleanup
109 of what-happens-where andwith making gimple_find_values_to_profile
110 and gimple_value_profile_transformations table-driven, perhaps...
113 static tree
gimple_divmod_fixed_value (gassign
*, tree
, int, gcov_type
,
115 static tree
gimple_mod_pow2 (gassign
*, int, gcov_type
, gcov_type
);
116 static tree
gimple_mod_subtract (gassign
*, int, int, int, gcov_type
,
117 gcov_type
, gcov_type
);
118 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
119 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
120 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
121 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
122 static bool gimple_ic_transform (gimple_stmt_iterator
*);
124 /* Allocate histogram value. */
127 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
128 enum hist_type type
, gimple
*stmt
, tree value
)
130 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
131 hist
->hvalue
.value
= value
;
132 hist
->hvalue
.stmt
= stmt
;
137 /* Hash value for histogram. */
140 histogram_hash (const void *x
)
142 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
145 /* Return nonzero if statement for histogram_value X is Y. */
148 histogram_eq (const void *x
, const void *y
)
150 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const gimple
*) y
;
153 /* Set histogram for STMT. */
156 set_histogram_value (struct function
*fun
, gimple
*stmt
, histogram_value hist
)
159 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
161 if (!VALUE_HISTOGRAMS (fun
))
162 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
164 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
165 htab_hash_pointer (stmt
),
166 hist
? INSERT
: NO_INSERT
);
170 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
176 /* Get histogram list for STMT. */
179 gimple_histogram_value (struct function
*fun
, gimple
*stmt
)
181 if (!VALUE_HISTOGRAMS (fun
))
183 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
184 htab_hash_pointer (stmt
));
187 /* Add histogram for STMT. */
190 gimple_add_histogram_value (struct function
*fun
, gimple
*stmt
,
191 histogram_value hist
)
193 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
194 set_histogram_value (fun
, stmt
, hist
);
198 /* Remove histogram HIST from STMT's histogram list. */
201 gimple_remove_histogram_value (struct function
*fun
, gimple
*stmt
,
202 histogram_value hist
)
204 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
207 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
211 while (hist2
->hvalue
.next
!= hist
)
212 hist2
= hist2
->hvalue
.next
;
213 hist2
->hvalue
.next
= hist
->hvalue
.next
;
215 free (hist
->hvalue
.counters
);
217 memset (hist
, 0xab, sizeof (*hist
));
221 /* Lookup histogram of type TYPE in the STMT. */
224 gimple_histogram_value_of_type (struct function
*fun
, gimple
*stmt
,
227 histogram_value hist
;
228 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
229 hist
= hist
->hvalue
.next
)
230 if (hist
->type
== type
)
235 /* Dump information about HIST to DUMP_FILE. */
238 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
242 case HIST_TYPE_INTERVAL
:
243 fprintf (dump_file
, "Interval counter range %d -- %d",
244 hist
->hdata
.intvl
.int_start
,
245 (hist
->hdata
.intvl
.int_start
246 + hist
->hdata
.intvl
.steps
- 1));
247 if (hist
->hvalue
.counters
)
250 fprintf (dump_file
, " [");
251 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
252 fprintf (dump_file
, " %d:%" PRId64
,
253 hist
->hdata
.intvl
.int_start
+ i
,
254 (int64_t) hist
->hvalue
.counters
[i
]);
255 fprintf (dump_file
, " ] outside range:%" PRId64
,
256 (int64_t) hist
->hvalue
.counters
[i
]);
258 fprintf (dump_file
, ".\n");
262 fprintf (dump_file
, "Pow2 counter ");
263 if (hist
->hvalue
.counters
)
265 fprintf (dump_file
, "pow2:%" PRId64
267 (int64_t) hist
->hvalue
.counters
[1],
268 (int64_t) hist
->hvalue
.counters
[0]);
270 fprintf (dump_file
, ".\n");
273 case HIST_TYPE_SINGLE_VALUE
:
274 fprintf (dump_file
, "Single value ");
275 if (hist
->hvalue
.counters
)
277 fprintf (dump_file
, "value:%" PRId64
280 (int64_t) hist
->hvalue
.counters
[0],
281 (int64_t) hist
->hvalue
.counters
[1],
282 (int64_t) hist
->hvalue
.counters
[2]);
284 fprintf (dump_file
, ".\n");
287 case HIST_TYPE_AVERAGE
:
288 fprintf (dump_file
, "Average value ");
289 if (hist
->hvalue
.counters
)
291 fprintf (dump_file
, "sum:%" PRId64
293 (int64_t) hist
->hvalue
.counters
[0],
294 (int64_t) hist
->hvalue
.counters
[1]);
296 fprintf (dump_file
, ".\n");
300 fprintf (dump_file
, "IOR value ");
301 if (hist
->hvalue
.counters
)
303 fprintf (dump_file
, "ior:%" PRId64
,
304 (int64_t) hist
->hvalue
.counters
[0]);
306 fprintf (dump_file
, ".\n");
309 case HIST_TYPE_CONST_DELTA
:
310 fprintf (dump_file
, "Constant delta ");
311 if (hist
->hvalue
.counters
)
313 fprintf (dump_file
, "value:%" PRId64
316 (int64_t) hist
->hvalue
.counters
[0],
317 (int64_t) hist
->hvalue
.counters
[1],
318 (int64_t) hist
->hvalue
.counters
[2]);
320 fprintf (dump_file
, ".\n");
322 case HIST_TYPE_INDIR_CALL
:
323 fprintf (dump_file
, "Indirect call ");
324 if (hist
->hvalue
.counters
)
326 fprintf (dump_file
, "value:%" PRId64
329 (int64_t) hist
->hvalue
.counters
[0],
330 (int64_t) hist
->hvalue
.counters
[1],
331 (int64_t) hist
->hvalue
.counters
[2]);
333 fprintf (dump_file
, ".\n");
335 case HIST_TYPE_TIME_PROFILE
:
336 fprintf (dump_file
, "Time profile ");
337 if (hist
->hvalue
.counters
)
339 fprintf (dump_file
, "time:%" PRId64
,
340 (int64_t) hist
->hvalue
.counters
[0]);
342 fprintf (dump_file
, ".\n");
344 case HIST_TYPE_INDIR_CALL_TOPN
:
345 fprintf (dump_file
, "Indirect call topn ");
346 if (hist
->hvalue
.counters
)
350 fprintf (dump_file
, "accu:%" PRId64
, hist
->hvalue
.counters
[0]);
351 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
353 fprintf (dump_file
, " target:%" PRId64
" value:%" PRId64
,
354 (int64_t) hist
->hvalue
.counters
[i
],
355 (int64_t) hist
->hvalue
.counters
[i
+1]);
358 fprintf (dump_file
, ".\n");
365 /* Dump information about HIST to DUMP_FILE. */
368 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
373 bp
= bitpack_create (ob
->main_stream
);
374 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
375 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
376 streamer_write_bitpack (&bp
);
379 case HIST_TYPE_INTERVAL
:
380 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
381 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
386 for (i
= 0; i
< hist
->n_counters
; i
++)
387 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
388 if (hist
->hvalue
.next
)
389 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
392 /* Dump information about HIST to DUMP_FILE. */
395 stream_in_histogram_value (struct lto_input_block
*ib
, gimple
*stmt
)
398 unsigned int ncounters
= 0;
401 histogram_value new_val
;
403 histogram_value
*next_p
= NULL
;
407 bp
= streamer_read_bitpack (ib
);
408 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
409 next
= bp_unpack_value (&bp
, 1);
410 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
413 case HIST_TYPE_INTERVAL
:
414 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
415 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
416 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
420 case HIST_TYPE_AVERAGE
:
424 case HIST_TYPE_SINGLE_VALUE
:
425 case HIST_TYPE_INDIR_CALL
:
429 case HIST_TYPE_CONST_DELTA
:
434 case HIST_TYPE_TIME_PROFILE
:
438 case HIST_TYPE_INDIR_CALL_TOPN
:
439 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
445 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
446 new_val
->n_counters
= ncounters
;
447 for (i
= 0; i
< ncounters
; i
++)
448 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
450 gimple_add_histogram_value (cfun
, stmt
, new_val
);
453 next_p
= &new_val
->hvalue
.next
;
458 /* Dump all histograms attached to STMT to DUMP_FILE. */
461 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
463 histogram_value hist
;
464 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
465 dump_histogram_value (dump_file
, hist
);
468 /* Remove all histograms associated with STMT. */
471 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
474 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
475 gimple_remove_histogram_value (fun
, stmt
, val
);
478 /* Duplicate all histograms associates with OSTMT to STMT. */
481 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
482 struct function
*ofun
, gimple
*ostmt
)
485 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
487 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
488 memcpy (new_val
, val
, sizeof (*val
));
489 new_val
->hvalue
.stmt
= stmt
;
490 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
491 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
492 gimple_add_histogram_value (fun
, stmt
, new_val
);
496 /* Move all histograms associated with OSTMT to STMT. */
499 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
501 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
504 /* The following three statements can't be reordered,
505 because histogram hashtab relies on stmt field value
506 for finding the exact slot. */
507 set_histogram_value (fun
, ostmt
, NULL
);
508 for (; val
!= NULL
; val
= val
->hvalue
.next
)
509 val
->hvalue
.stmt
= stmt
;
510 set_histogram_value (fun
, stmt
, val
);
514 static bool error_found
= false;
516 /* Helper function for verify_histograms. For each histogram reachable via htab
517 walk verify that it was reached via statement walk. */
520 visit_hist (void **slot
, void *data
)
522 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
523 histogram_value hist
= *(histogram_value
*) slot
;
525 if (!visited
->contains (hist
)
526 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
528 error ("dead histogram");
529 dump_histogram_value (stderr
, hist
);
530 debug_gimple_stmt (hist
->hvalue
.stmt
);
536 /* Verify sanity of the histograms. */
539 verify_histograms (void)
542 gimple_stmt_iterator gsi
;
543 histogram_value hist
;
546 hash_set
<histogram_value
> visited_hists
;
547 FOR_EACH_BB_FN (bb
, cfun
)
548 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
550 gimple
*stmt
= gsi_stmt (gsi
);
552 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
553 hist
= hist
->hvalue
.next
)
555 if (hist
->hvalue
.stmt
!= stmt
)
557 error ("Histogram value statement does not correspond to "
558 "the statement it is associated with");
559 debug_gimple_stmt (stmt
);
560 dump_histogram_value (stderr
, hist
);
563 visited_hists
.add (hist
);
566 if (VALUE_HISTOGRAMS (cfun
))
567 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
569 internal_error ("verify_histograms failed");
572 /* Helper function for verify_histograms. For each histogram reachable via htab
573 walk verify that it was reached via statement walk. */
576 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
578 histogram_value hist
= *(histogram_value
*) slot
;
579 free (hist
->hvalue
.counters
);
581 memset (hist
, 0xab, sizeof (*hist
));
587 free_histograms (struct function
*fn
)
589 if (VALUE_HISTOGRAMS (fn
))
591 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
592 htab_delete (VALUE_HISTOGRAMS (fn
));
593 VALUE_HISTOGRAMS (fn
) = NULL
;
597 /* The overall number of invocations of the counter should match
598 execution count of basic block. Report it as error rather than
599 internal error as it might mean that user has misused the profile
603 check_counter (gimple
*stmt
, const char * name
,
604 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
606 if (*all
!= bb_count
|| *count
> *all
)
609 locus
= (stmt
!= NULL
)
610 ? gimple_location (stmt
)
611 : DECL_SOURCE_LOCATION (current_function_decl
);
612 if (flag_profile_correction
)
614 if (dump_enabled_p ())
615 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
616 "correcting inconsistent value profile: %s "
617 "profiler overall count (%d) does not match BB "
618 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
626 error_at (locus
, "corrupted value profile: %s "
627 "profile counter (%d out of %d) inconsistent with "
628 "basic-block count (%d)",
640 /* GIMPLE based transformations. */
643 gimple_value_profile_transformations (void)
646 gimple_stmt_iterator gsi
;
647 bool changed
= false;
649 /* Autofdo does its own transformations for indirect calls,
650 and otherwise does not support value profiling. */
651 if (flag_auto_profile
)
654 FOR_EACH_BB_FN (bb
, cfun
)
656 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
658 gimple
*stmt
= gsi_stmt (gsi
);
659 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
665 fprintf (dump_file
, "Trying transformations on stmt ");
666 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
667 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
670 /* Transformations: */
671 /* The order of things in this conditional controls which
672 transformation is used when more than one is applicable. */
673 /* It is expected that any code added by the transformations
674 will be added before the current statement, and that the
675 current statement remain valid (although possibly
676 modified) upon return. */
677 if (gimple_mod_subtract_transform (&gsi
)
678 || gimple_divmod_fixed_value_transform (&gsi
)
679 || gimple_mod_pow2_value_transform (&gsi
)
680 || gimple_stringops_transform (&gsi
)
681 || gimple_ic_transform (&gsi
))
683 stmt
= gsi_stmt (gsi
);
685 /* Original statement may no longer be in the same block. */
686 if (bb
!= gimple_bb (stmt
))
688 bb
= gimple_bb (stmt
);
689 gsi
= gsi_for_stmt (stmt
);
703 /* Generate code for transformation 1 (with parent gimple assignment
704 STMT and probability of taking the optimal path PROB, which is
705 equivalent to COUNT/ALL within roundoff error). This generates the
706 result into a temp and returns the temp; it does not replace or
707 alter the original STMT. */
710 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, int prob
,
711 gcov_type count
, gcov_type all
)
713 gassign
*stmt1
, *stmt2
;
715 tree tmp0
, tmp1
, tmp2
;
716 gimple
*bb1end
, *bb2end
, *bb3end
;
717 basic_block bb
, bb2
, bb3
, bb4
;
718 tree optype
, op1
, op2
;
719 edge e12
, e13
, e23
, e24
, e34
;
720 gimple_stmt_iterator gsi
;
722 gcc_assert (is_gimple_assign (stmt
)
723 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
724 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
726 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
727 op1
= gimple_assign_rhs1 (stmt
);
728 op2
= gimple_assign_rhs2 (stmt
);
730 bb
= gimple_bb (stmt
);
731 gsi
= gsi_for_stmt (stmt
);
733 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
734 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
735 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
736 stmt2
= gimple_build_assign (tmp1
, op2
);
737 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
738 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
739 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
740 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
743 tmp2
= create_tmp_reg (optype
, "PROF");
744 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
745 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
748 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
749 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
753 /* Edge e23 connects bb2 to bb3, etc. */
754 e12
= split_block (bb
, bb1end
);
757 e23
= split_block (bb2
, bb2end
);
759 bb3
->count
= all
- count
;
760 e34
= split_block (bb3
, bb3end
);
764 e12
->flags
&= ~EDGE_FALLTHRU
;
765 e12
->flags
|= EDGE_FALSE_VALUE
;
766 e12
->probability
= prob
;
769 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
770 e13
->probability
= REG_BR_PROB_BASE
- prob
;
771 e13
->count
= all
- count
;
775 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
776 e24
->probability
= REG_BR_PROB_BASE
;
779 e34
->probability
= REG_BR_PROB_BASE
;
780 e34
->count
= all
- count
;
785 /* Do transform 1) on INSN if applicable. */
788 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
790 histogram_value histogram
;
792 gcov_type val
, count
, all
;
793 tree result
, value
, tree_val
;
797 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
801 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
804 code
= gimple_assign_rhs_code (stmt
);
806 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
809 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
810 HIST_TYPE_SINGLE_VALUE
);
814 value
= histogram
->hvalue
.value
;
815 val
= histogram
->hvalue
.counters
[0];
816 count
= histogram
->hvalue
.counters
[1];
817 all
= histogram
->hvalue
.counters
[2];
818 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
820 /* We require that count is at least half of all; this means
821 that for the transformation to fire the value must be constant
822 at least 50% of time (and 75% gives the guarantee of usage). */
823 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
825 || optimize_bb_for_size_p (gimple_bb (stmt
)))
828 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
831 /* Compute probability of taking the optimal path. */
833 prob
= GCOV_COMPUTE_SCALE (count
, all
);
837 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
838 tree_val
= build_int_cst (get_gcov_type (), val
);
842 a
[0] = (unsigned HOST_WIDE_INT
) val
;
843 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
845 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
846 TYPE_PRECISION (get_gcov_type ()), false));
848 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
852 fprintf (dump_file
, "Div/mod by constant ");
853 print_generic_expr (dump_file
, value
, TDF_SLIM
);
854 fprintf (dump_file
, "=");
855 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
856 fprintf (dump_file
, " transformation on insn ");
857 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
860 gimple_assign_set_rhs_from_tree (si
, result
);
861 update_stmt (gsi_stmt (*si
));
866 /* Generate code for transformation 2 (with parent gimple assign STMT and
867 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
868 within roundoff error). This generates the result into a temp and returns
869 the temp; it does not replace or alter the original STMT. */
872 gimple_mod_pow2 (gassign
*stmt
, int prob
, gcov_type count
, gcov_type all
)
874 gassign
*stmt1
, *stmt2
, *stmt3
;
877 gimple
*bb1end
, *bb2end
, *bb3end
;
878 basic_block bb
, bb2
, bb3
, bb4
;
879 tree optype
, op1
, op2
;
880 edge e12
, e13
, e23
, e24
, e34
;
881 gimple_stmt_iterator gsi
;
884 gcc_assert (is_gimple_assign (stmt
)
885 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
887 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
888 op1
= gimple_assign_rhs1 (stmt
);
889 op2
= gimple_assign_rhs2 (stmt
);
891 bb
= gimple_bb (stmt
);
892 gsi
= gsi_for_stmt (stmt
);
894 result
= create_tmp_reg (optype
, "PROF");
895 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
896 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
897 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
898 build_int_cst (optype
, -1));
899 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
900 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
901 NULL_TREE
, NULL_TREE
);
902 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
903 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
904 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
907 /* tmp2 == op2-1 inherited from previous block. */
908 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
909 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
912 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
914 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
918 /* Edge e23 connects bb2 to bb3, etc. */
919 e12
= split_block (bb
, bb1end
);
922 e23
= split_block (bb2
, bb2end
);
924 bb3
->count
= all
- count
;
925 e34
= split_block (bb3
, bb3end
);
929 e12
->flags
&= ~EDGE_FALLTHRU
;
930 e12
->flags
|= EDGE_FALSE_VALUE
;
931 e12
->probability
= prob
;
934 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
935 e13
->probability
= REG_BR_PROB_BASE
- prob
;
936 e13
->count
= all
- count
;
940 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
941 e24
->probability
= REG_BR_PROB_BASE
;
944 e34
->probability
= REG_BR_PROB_BASE
;
945 e34
->count
= all
- count
;
950 /* Do transform 2) on INSN if applicable. */
953 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
955 histogram_value histogram
;
957 gcov_type count
, wrong_values
, all
;
958 tree lhs_type
, result
, value
;
962 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
966 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
967 if (!INTEGRAL_TYPE_P (lhs_type
))
970 code
= gimple_assign_rhs_code (stmt
);
972 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
975 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
979 value
= histogram
->hvalue
.value
;
980 wrong_values
= histogram
->hvalue
.counters
[0];
981 count
= histogram
->hvalue
.counters
[1];
983 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
985 /* We require that we hit a power of 2 at least half of all evaluations. */
986 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
987 || count
< wrong_values
988 || optimize_bb_for_size_p (gimple_bb (stmt
)))
993 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
994 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
997 /* Compute probability of taking the optimal path. */
998 all
= count
+ wrong_values
;
1000 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1004 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1008 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1010 gimple_assign_set_rhs_from_tree (si
, result
);
1011 update_stmt (gsi_stmt (*si
));
1016 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1017 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1018 supported and this is built into this interface. The probabilities of taking
1019 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1020 COUNT2/ALL respectively within roundoff error). This generates the
1021 result into a temp and returns the temp; it does not replace or alter
1022 the original STMT. */
1023 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1026 gimple_mod_subtract (gassign
*stmt
, int prob1
, int prob2
, int ncounts
,
1027 gcov_type count1
, gcov_type count2
, gcov_type all
)
1033 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
1034 basic_block bb
, bb2
, bb3
, bb4
;
1035 tree optype
, op1
, op2
;
1036 edge e12
, e23
= 0, e24
, e34
, e14
;
1037 gimple_stmt_iterator gsi
;
1040 gcc_assert (is_gimple_assign (stmt
)
1041 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1043 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1044 op1
= gimple_assign_rhs1 (stmt
);
1045 op2
= gimple_assign_rhs2 (stmt
);
1047 bb
= gimple_bb (stmt
);
1048 gsi
= gsi_for_stmt (stmt
);
1050 result
= create_tmp_reg (optype
, "PROF");
1051 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1052 stmt1
= gimple_build_assign (result
, op1
);
1053 stmt2
= gimple_build_assign (tmp1
, op2
);
1054 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1055 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1056 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1057 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1060 if (ncounts
) /* Assumed to be 0 or 1 */
1062 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1063 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1064 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1065 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1069 /* Fallback case. */
1070 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1072 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1076 /* Edge e23 connects bb2 to bb3, etc. */
1077 /* However block 3 is optional; if it is not there, references
1078 to 3 really refer to block 2. */
1079 e12
= split_block (bb
, bb1end
);
1081 bb2
->count
= all
- count1
;
1083 if (ncounts
) /* Assumed to be 0 or 1. */
1085 e23
= split_block (bb2
, bb2end
);
1087 bb3
->count
= all
- count1
- count2
;
1090 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1094 e12
->flags
&= ~EDGE_FALLTHRU
;
1095 e12
->flags
|= EDGE_FALSE_VALUE
;
1096 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1097 e12
->count
= all
- count1
;
1099 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1100 e14
->probability
= prob1
;
1101 e14
->count
= count1
;
1103 if (ncounts
) /* Assumed to be 0 or 1. */
1105 e23
->flags
&= ~EDGE_FALLTHRU
;
1106 e23
->flags
|= EDGE_FALSE_VALUE
;
1107 e23
->count
= all
- count1
- count2
;
1108 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1110 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1111 e24
->probability
= prob2
;
1112 e24
->count
= count2
;
1115 e34
->probability
= REG_BR_PROB_BASE
;
1116 e34
->count
= all
- count1
- count2
;
1121 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1124 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1126 histogram_value histogram
;
1127 enum tree_code code
;
1128 gcov_type count
, wrong_values
, all
;
1129 tree lhs_type
, result
;
1130 gcov_type prob1
, prob2
;
1131 unsigned int i
, steps
;
1132 gcov_type count1
, count2
;
1134 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1138 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1139 if (!INTEGRAL_TYPE_P (lhs_type
))
1142 code
= gimple_assign_rhs_code (stmt
);
1144 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1147 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1153 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1154 all
+= histogram
->hvalue
.counters
[i
];
1156 wrong_values
+= histogram
->hvalue
.counters
[i
];
1157 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1158 steps
= histogram
->hdata
.intvl
.steps
;
1159 all
+= wrong_values
;
1160 count1
= histogram
->hvalue
.counters
[0];
1161 count2
= histogram
->hvalue
.counters
[1];
1163 /* Compute probability of taking the optimal path. */
1164 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1166 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1170 if (flag_profile_correction
&& count1
+ count2
> all
)
1171 all
= count1
+ count2
;
1173 gcc_assert (count1
+ count2
<= all
);
1175 /* We require that we use just subtractions in at least 50% of all
1178 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1180 count
+= histogram
->hvalue
.counters
[i
];
1181 if (count
* 2 >= all
)
1185 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1188 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1191 fprintf (dump_file
, "Mod subtract transformation on insn ");
1192 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1195 /* Compute probability of taking the optimal path(s). */
1198 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1199 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1206 /* In practice, "steps" is always 2. This interface reflects this,
1207 and will need to be changed if "steps" can change. */
1208 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1210 gimple_assign_set_rhs_from_tree (si
, result
);
1211 update_stmt (gsi_stmt (*si
));
1216 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1218 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1220 /* Returns true if node graph is initialized. This
1221 is used to test if profile_id has been created
1222 for cgraph_nodes. */
1225 coverage_node_map_initialized_p (void)
1227 return cgraph_node_map
!= 0;
1230 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1231 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1232 that the PROFILE_IDs was already assigned. */
1235 init_node_map (bool local
)
1237 struct cgraph_node
*n
;
1238 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1240 FOR_EACH_DEFINED_FUNCTION (n
)
1241 if (n
->has_gimple_body_p ())
1246 n
->profile_id
= coverage_compute_profile_id (n
);
1247 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1251 fprintf (dump_file
, "Local profile-id %i conflict"
1252 " with nodes %s/%i %s/%i\n",
1258 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1261 else if (!n
->profile_id
)
1265 "Node %s/%i has no profile-id"
1266 " (profile feedback missing?)\n",
1271 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1275 "Node %s/%i has IP profile-id %i conflict. "
1283 cgraph_node_map
->put (n
->profile_id
, n
);
1287 /* Delete the CGRAPH_NODE_MAP. */
1292 delete cgraph_node_map
;
1295 /* Return cgraph node for function with pid */
1298 find_func_by_profile_id (int profile_id
)
1300 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1307 /* Perform sanity check on the indirect call target. Due to race conditions,
1308 false function target may be attributed to an indirect call site. If the
1309 call expression type mismatches with the target function's type, expand_call
1310 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1311 Returns true if TARGET is considered ok for call CALL_STMT. */
1314 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1317 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1320 locus
= gimple_location (call_stmt
);
1321 if (dump_enabled_p ())
1322 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1323 "Skipping target %s with mismatching types for icall\n",
1328 /* Do transformation
1330 if (actual_callee_address == address_of_most_common_function/method)
1337 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1338 int prob
, gcov_type count
, gcov_type all
)
1343 gcall
*iretbnd_stmt
= NULL
;
1344 tree tmp0
, tmp1
, tmp
;
1345 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1346 tree optype
= build_pointer_type (void_type_node
);
1347 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1348 gimple_stmt_iterator gsi
;
1352 gimple_stmt_iterator psi
;
1354 cond_bb
= gimple_bb (icall_stmt
);
1355 gsi
= gsi_for_stmt (icall_stmt
);
1357 if (gimple_call_with_bounds_p (icall_stmt
) && gimple_call_lhs (icall_stmt
))
1358 iretbnd_stmt
= chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt
));
1360 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1361 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1362 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1363 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1364 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1366 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
));
1367 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1368 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1370 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1371 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1373 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1375 unlink_stmt_vdef (icall_stmt
);
1376 release_ssa_name (gimple_vdef (icall_stmt
));
1378 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1379 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1380 update_stmt (icall_stmt
);
1381 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1382 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1383 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1384 if ((dflags
& ECF_NORETURN
) != 0)
1385 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1386 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1389 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1390 e_cd
= split_block (cond_bb
, cond_stmt
);
1391 dcall_bb
= e_cd
->dest
;
1392 dcall_bb
->count
= count
;
1394 e_di
= split_block (dcall_bb
, dcall_stmt
);
1395 icall_bb
= e_di
->dest
;
1396 icall_bb
->count
= all
- count
;
1398 /* Do not disturb existing EH edges from the indirect call. */
1399 if (!stmt_ends_bb_p (icall_stmt
))
1400 e_ij
= split_block (icall_bb
, icall_stmt
);
1403 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1404 /* The indirect call might be noreturn. */
1407 e_ij
->probability
= REG_BR_PROB_BASE
;
1408 e_ij
->count
= all
- count
;
1409 e_ij
= single_pred_edge (split_edge (e_ij
));
1414 join_bb
= e_ij
->dest
;
1415 join_bb
->count
= all
;
1418 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1419 e_cd
->probability
= prob
;
1420 e_cd
->count
= count
;
1422 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1423 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1424 e_ci
->count
= all
- count
;
1430 if ((dflags
& ECF_NORETURN
) != 0)
1434 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1435 e_dj
->probability
= REG_BR_PROB_BASE
;
1436 e_dj
->count
= count
;
1438 e_ij
->count
= all
- count
;
1440 e_ij
->probability
= REG_BR_PROB_BASE
;
1443 /* Insert PHI node for the call result if necessary. */
1444 if (gimple_call_lhs (icall_stmt
)
1445 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1446 && (dflags
& ECF_NORETURN
) == 0)
1448 tree result
= gimple_call_lhs (icall_stmt
);
1449 gphi
*phi
= create_phi_node (result
, join_bb
);
1450 gimple_call_set_lhs (icall_stmt
,
1451 duplicate_ssa_name (result
, icall_stmt
));
1452 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1453 gimple_call_set_lhs (dcall_stmt
,
1454 duplicate_ssa_name (result
, dcall_stmt
));
1455 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1457 /* If indirect call has following BUILT_IN_CHKP_BNDRET
1458 call then we need to make it's copy for the direct
1462 if (gimple_call_lhs (iretbnd_stmt
))
1466 if (TREE_CODE (gimple_vdef (iretbnd_stmt
)) == SSA_NAME
)
1468 unlink_stmt_vdef (iretbnd_stmt
);
1469 release_ssa_name (gimple_vdef (iretbnd_stmt
));
1471 gimple_set_vdef (iretbnd_stmt
, NULL_TREE
);
1472 gimple_set_vuse (iretbnd_stmt
, NULL_TREE
);
1473 update_stmt (iretbnd_stmt
);
1475 result
= gimple_call_lhs (iretbnd_stmt
);
1476 phi
= create_phi_node (result
, join_bb
);
1478 copy
= gimple_copy (iretbnd_stmt
);
1479 gimple_call_set_arg (copy
, 0,
1480 gimple_call_lhs (dcall_stmt
));
1481 gimple_call_set_lhs (copy
, duplicate_ssa_name (result
, copy
));
1482 gsi_insert_on_edge (e_dj
, copy
);
1483 add_phi_arg (phi
, gimple_call_lhs (copy
),
1484 e_dj
, UNKNOWN_LOCATION
);
1486 gimple_call_set_arg (iretbnd_stmt
, 0,
1487 gimple_call_lhs (icall_stmt
));
1488 gimple_call_set_lhs (iretbnd_stmt
,
1489 duplicate_ssa_name (result
, iretbnd_stmt
));
1490 psi
= gsi_for_stmt (iretbnd_stmt
);
1491 gsi_remove (&psi
, false);
1492 gsi_insert_on_edge (e_ij
, iretbnd_stmt
);
1493 add_phi_arg (phi
, gimple_call_lhs (iretbnd_stmt
),
1494 e_ij
, UNKNOWN_LOCATION
);
1496 gsi_commit_one_edge_insert (e_dj
, NULL
);
1497 gsi_commit_one_edge_insert (e_ij
, NULL
);
1501 psi
= gsi_for_stmt (iretbnd_stmt
);
1502 gsi_remove (&psi
, true);
1507 /* Build an EH edge for the direct call if necessary. */
1508 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1509 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1511 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1514 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1515 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1517 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1518 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1519 !gsi_end_p (psi
); gsi_next (&psi
))
1521 gphi
*phi
= psi
.phi ();
1522 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1523 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1526 if (!stmt_could_throw_p (dcall_stmt
))
1527 gimple_purge_dead_eh_edges (dcall_bb
);
1532 For every checked indirect/virtual call determine if most common pid of
1533 function/class method has probability more than 50%. If yes modify code of
1538 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1541 histogram_value histogram
;
1542 gcov_type val
, count
, all
, bb_all
;
1543 struct cgraph_node
*direct_call
;
1545 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1549 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1552 if (gimple_call_internal_p (stmt
))
1555 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1559 val
= histogram
->hvalue
.counters
[0];
1560 count
= histogram
->hvalue
.counters
[1];
1561 all
= histogram
->hvalue
.counters
[2];
1563 bb_all
= gimple_bb (stmt
)->count
;
1564 /* The order of CHECK_COUNTER calls is important -
1565 since check_counter can correct the third parameter
1566 and we want to make count <= all <= bb_all. */
1567 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1568 || check_counter (stmt
, "ic", &count
, &all
, all
))
1570 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1574 if (4 * count
<= 3 * all
)
1577 direct_call
= find_func_by_profile_id ((int)val
);
1579 if (direct_call
== NULL
)
1585 fprintf (dump_file
, "Indirect call -> direct call from other module");
1586 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1587 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1593 if (!check_ic_target (stmt
, direct_call
))
1597 fprintf (dump_file
, "Indirect call -> direct call ");
1598 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1599 fprintf (dump_file
, "=> ");
1600 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1601 fprintf (dump_file
, " transformation skipped because of type mismatch");
1602 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1604 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1610 fprintf (dump_file
, "Indirect call -> direct call ");
1611 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1612 fprintf (dump_file
, "=> ");
1613 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1614 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1615 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1616 fprintf (dump_file
, "hist->count %" PRId64
1617 " hist->all %" PRId64
"\n", count
, all
);
1623 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1624 set to the argument index for the size of the string operation. */
1627 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1629 enum built_in_function fcode
;
1631 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1632 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1633 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1638 case BUILT_IN_MEMCPY
:
1639 case BUILT_IN_MEMPCPY
:
1641 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1642 INTEGER_TYPE
, VOID_TYPE
);
1643 case BUILT_IN_MEMSET
:
1645 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1646 INTEGER_TYPE
, VOID_TYPE
);
1647 case BUILT_IN_BZERO
:
1649 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1656 /* Convert stringop (..., vcall_size)
1658 if (vcall_size == icall_size)
1659 stringop (..., icall_size);
1661 stringop (..., vcall_size);
1662 assuming we'll propagate a true constant into ICALL_SIZE later. */
1665 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, int prob
,
1666 gcov_type count
, gcov_type all
)
1671 tree tmp0
, tmp1
, vcall_size
, optype
;
1672 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1673 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1674 gimple_stmt_iterator gsi
;
1677 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1680 cond_bb
= gimple_bb (vcall_stmt
);
1681 gsi
= gsi_for_stmt (vcall_stmt
);
1683 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1684 optype
= TREE_TYPE (vcall_size
);
1686 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1687 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1688 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1689 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1691 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1692 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1694 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1695 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1697 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1699 unlink_stmt_vdef (vcall_stmt
);
1700 release_ssa_name (gimple_vdef (vcall_stmt
));
1702 gimple_set_vdef (vcall_stmt
, NULL
);
1703 gimple_set_vuse (vcall_stmt
, NULL
);
1704 update_stmt (vcall_stmt
);
1705 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1706 gimple_call_set_arg (icall_stmt
, size_arg
,
1707 fold_convert (optype
, icall_size
));
1708 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1711 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1712 e_ci
= split_block (cond_bb
, cond_stmt
);
1713 icall_bb
= e_ci
->dest
;
1714 icall_bb
->count
= count
;
1716 e_iv
= split_block (icall_bb
, icall_stmt
);
1717 vcall_bb
= e_iv
->dest
;
1718 vcall_bb
->count
= all
- count
;
1720 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1721 join_bb
= e_vj
->dest
;
1722 join_bb
->count
= all
;
1724 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1725 e_ci
->probability
= prob
;
1726 e_ci
->count
= count
;
1728 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1729 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1730 e_cv
->count
= all
- count
;
1734 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1735 e_ij
->probability
= REG_BR_PROB_BASE
;
1736 e_ij
->count
= count
;
1738 e_vj
->probability
= REG_BR_PROB_BASE
;
1739 e_vj
->count
= all
- count
;
1741 /* Insert PHI node for the call result if necessary. */
1742 if (gimple_call_lhs (vcall_stmt
)
1743 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1745 tree result
= gimple_call_lhs (vcall_stmt
);
1746 gphi
*phi
= create_phi_node (result
, join_bb
);
1747 gimple_call_set_lhs (vcall_stmt
,
1748 duplicate_ssa_name (result
, vcall_stmt
));
1749 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1750 gimple_call_set_lhs (icall_stmt
,
1751 duplicate_ssa_name (result
, icall_stmt
));
1752 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1755 /* Because these are all string op builtins, they're all nothrow. */
1756 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1757 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1760 /* Find values inside STMT for that we want to measure histograms for
1761 division/modulo optimization. */
1764 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1768 enum built_in_function fcode
;
1769 histogram_value histogram
;
1770 gcov_type count
, all
, val
;
1772 unsigned int dest_align
, src_align
;
1777 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1781 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1784 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1787 blck_size
= gimple_call_arg (stmt
, size_arg
);
1788 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1791 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1795 val
= histogram
->hvalue
.counters
[0];
1796 count
= histogram
->hvalue
.counters
[1];
1797 all
= histogram
->hvalue
.counters
[2];
1798 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1800 /* We require that count is at least half of all; this means
1801 that for the transformation to fire the value must be constant
1802 at least 80% of time. */
1803 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1805 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1808 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1812 dest
= gimple_call_arg (stmt
, 0);
1813 dest_align
= get_pointer_alignment (dest
);
1814 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1817 case BUILT_IN_MEMCPY
:
1818 case BUILT_IN_MEMPCPY
:
1819 src
= gimple_call_arg (stmt
, 1);
1820 src_align
= get_pointer_alignment (src
);
1821 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1824 case BUILT_IN_MEMSET
:
1825 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1826 gimple_call_arg (stmt
, 1),
1830 case BUILT_IN_BZERO
:
1831 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1840 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1841 tree_val
= build_int_cst (get_gcov_type (), val
);
1845 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1846 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1848 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1849 TYPE_PRECISION (get_gcov_type ()), false));
1854 fprintf (dump_file
, "Single value %i stringop transformation on ",
1856 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1859 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1865 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1866 HOST_WIDE_INT
*expected_size
)
1868 histogram_value histogram
;
1869 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
);
1892 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1895 *expected_align
= 0;
1896 else if (!histogram
->hvalue
.counters
[0])
1898 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1899 *expected_align
= 0;
1906 count
= histogram
->hvalue
.counters
[0];
1908 while (!(count
& alignment
)
1909 && (alignment
* 2 * BITS_PER_UNIT
))
1911 *expected_align
= alignment
* BITS_PER_UNIT
;
1912 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1917 /* Find values inside STMT for that we want to measure histograms for
1918 division/modulo optimization. */
1921 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1923 tree lhs
, divisor
, op0
, type
;
1924 histogram_value hist
;
1926 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1929 lhs
= gimple_assign_lhs (stmt
);
1930 type
= TREE_TYPE (lhs
);
1931 if (!INTEGRAL_TYPE_P (type
))
1934 switch (gimple_assign_rhs_code (stmt
))
1936 case TRUNC_DIV_EXPR
:
1937 case TRUNC_MOD_EXPR
:
1938 divisor
= gimple_assign_rhs2 (stmt
);
1939 op0
= gimple_assign_rhs1 (stmt
);
1941 values
->reserve (3);
1943 if (TREE_CODE (divisor
) == SSA_NAME
)
1944 /* Check for the case where the divisor is the same value most
1946 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1947 HIST_TYPE_SINGLE_VALUE
,
1950 /* For mod, check whether it is not often a noop (or replaceable by
1951 a few subtractions). */
1952 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1953 && TYPE_UNSIGNED (type
)
1954 && TREE_CODE (divisor
) == SSA_NAME
)
1957 /* Check for a special case where the divisor is power of 2. */
1958 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1962 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1963 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1965 hist
->hdata
.intvl
.int_start
= 0;
1966 hist
->hdata
.intvl
.steps
= 2;
1967 values
->quick_push (hist
);
1976 /* Find calls inside STMT for that we want to measure histograms for
1977 indirect/virtual call optimization. */
1980 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1984 if (gimple_code (stmt
) != GIMPLE_CALL
1985 || gimple_call_internal_p (stmt
)
1986 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1989 callee
= gimple_call_fn (stmt
);
1991 values
->reserve (3);
1993 values
->quick_push (gimple_alloc_histogram_value (
1995 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1996 HIST_TYPE_INDIR_CALL_TOPN
:
1997 HIST_TYPE_INDIR_CALL
,
2003 /* Find values inside STMT for that we want to measure histograms for
2004 string operations. */
2007 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
2014 stmt
= dyn_cast
<gcall
*> (gs
);
2018 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
2021 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
2024 dest
= gimple_call_arg (stmt
, 0);
2025 blck_size
= gimple_call_arg (stmt
, size_arg
);
2027 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2029 values
->safe_push (gimple_alloc_histogram_value (cfun
,
2030 HIST_TYPE_SINGLE_VALUE
,
2032 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
2036 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2037 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
2041 /* Find values inside STMT for that we want to measure histograms and adds
2042 them to list VALUES. */
2045 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
2047 gimple_divmod_values_to_profile (stmt
, values
);
2048 gimple_stringops_values_to_profile (stmt
, values
);
2049 gimple_indirect_call_to_profile (stmt
, values
);
2053 gimple_find_values_to_profile (histogram_values
*values
)
2056 gimple_stmt_iterator gsi
;
2058 histogram_value hist
= NULL
;
2061 FOR_EACH_BB_FN (bb
, cfun
)
2062 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2063 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2065 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2067 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2071 case HIST_TYPE_INTERVAL
:
2072 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2075 case HIST_TYPE_POW2
:
2076 hist
->n_counters
= 2;
2079 case HIST_TYPE_SINGLE_VALUE
:
2080 hist
->n_counters
= 3;
2083 case HIST_TYPE_CONST_DELTA
:
2084 hist
->n_counters
= 4;
2087 case HIST_TYPE_INDIR_CALL
:
2088 hist
->n_counters
= 3;
2091 case HIST_TYPE_TIME_PROFILE
:
2092 hist
->n_counters
= 1;
2095 case HIST_TYPE_AVERAGE
:
2096 hist
->n_counters
= 2;
2100 hist
->n_counters
= 1;
2103 case HIST_TYPE_INDIR_CALL_TOPN
:
2104 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2112 fprintf (dump_file
, "Stmt ");
2113 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2114 dump_histogram_value (dump_file
, hist
);