1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2014 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"
25 #include "tree-nested.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "value-prof.h"
33 #include "insn-config.h"
37 #include "tree-ssa-alias.h"
38 #include "internal-fn.h"
40 #include "gimple-expr.h"
44 #include "gimple-iterator.h"
45 #include "gimple-ssa.h"
47 #include "tree-phinodes.h"
48 #include "ssa-iterators.h"
49 #include "stringpool.h"
50 #include "tree-ssanames.h"
51 #include "diagnostic.h"
52 #include "gimple-pretty-print.h"
59 #include "data-streamer.h"
61 #include "tree-nested.h"
63 /* In this file value profile based optimizations are placed. Currently the
64 following optimizations are implemented (for more detailed descriptions
65 see comments at value_profile_transformations):
67 1) Division/modulo specialization. Provided that we can determine that the
68 operands of the division have some special properties, we may use it to
69 produce more effective code.
71 2) Indirect/virtual call specialization. If we can determine most
72 common function callee in indirect/virtual call. We can use this
73 information to improve code effectiveness (especially info for
76 3) Speculative prefetching. If we are able to determine that the difference
77 between addresses accessed by a memory reference is usually constant, we
78 may add the prefetch instructions.
79 FIXME: This transformation was removed together with RTL based value
83 Value profiling internals
84 ==========================
86 Every value profiling transformation starts with defining what values
87 to profile. There are different histogram types (see HIST_TYPE_* in
88 value-prof.h) and each transformation can request one or more histogram
89 types per GIMPLE statement. The function gimple_find_values_to_profile()
90 collects the values to profile in a vec, and adds the number of counters
91 required for the different histogram types.
93 For a -fprofile-generate run, the statements for which values should be
94 recorded, are instrumented in instrument_values(). The instrumentation
95 is done by helper functions that can be found in tree-profile.c, where
96 new types of histograms can be added if necessary.
98 After a -fprofile-use, the value profiling data is read back in by
99 compute_value_histograms() that translates the collected data to
100 histograms and attaches them to the profiled statements via
101 gimple_add_histogram_value(). Histograms are stored in a hash table
102 that is attached to every intrumented function, see VALUE_HISTOGRAMS
105 The value-profile transformations driver is the function
106 gimple_value_profile_transformations(). It traverses all statements in
107 the to-be-transformed function, and looks for statements with one or
108 more histograms attached to it. If a statement has histograms, the
109 transformation functions are called on the statement.
111 Limitations / FIXME / TODO:
112 * Only one histogram of each type can be associated with a statement.
113 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
114 (This type of histogram was originally used to implement a form of
115 stride profiling based speculative prefetching to improve SPEC2000
116 scores for memory-bound benchmarks, mcf and equake. However, this
117 was an RTL value-profiling transformation, and those have all been
119 * Some value profile transformations are done in builtins.c (?!)
120 * Updating of histograms needs some TLC.
121 * The value profiling code could be used to record analysis results
122 from non-profiling (e.g. VRP).
123 * Adding new profilers should be simplified, starting with a cleanup
124 of what-happens-where andwith making gimple_find_values_to_profile
125 and gimple_value_profile_transformations table-driven, perhaps...
128 static tree
gimple_divmod_fixed_value (gimple
, tree
, int, gcov_type
, gcov_type
);
129 static tree
gimple_mod_pow2 (gimple
, int, gcov_type
, gcov_type
);
130 static tree
gimple_mod_subtract (gimple
, int, int, int, gcov_type
, gcov_type
,
132 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
133 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
134 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
135 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
136 static bool gimple_ic_transform (gimple_stmt_iterator
*);
138 /* Allocate histogram value. */
140 static histogram_value
141 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
142 enum hist_type type
, gimple stmt
, tree value
)
144 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
145 hist
->hvalue
.value
= value
;
146 hist
->hvalue
.stmt
= stmt
;
151 /* Hash value for histogram. */
154 histogram_hash (const void *x
)
156 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
159 /* Return nonzero if statement for histogram_value X is Y. */
162 histogram_eq (const void *x
, const void *y
)
164 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
167 /* Set histogram for STMT. */
170 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
173 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
175 if (!VALUE_HISTOGRAMS (fun
))
176 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
178 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
179 htab_hash_pointer (stmt
),
180 hist
? INSERT
: NO_INSERT
);
184 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
190 /* Get histogram list for STMT. */
193 gimple_histogram_value (struct function
*fun
, gimple stmt
)
195 if (!VALUE_HISTOGRAMS (fun
))
197 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
198 htab_hash_pointer (stmt
));
201 /* Add histogram for STMT. */
204 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
205 histogram_value hist
)
207 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
208 set_histogram_value (fun
, stmt
, hist
);
213 /* Remove histogram HIST from STMT's histogram list. */
216 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
217 histogram_value hist
)
219 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
222 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
226 while (hist2
->hvalue
.next
!= hist
)
227 hist2
= hist2
->hvalue
.next
;
228 hist2
->hvalue
.next
= hist
->hvalue
.next
;
230 free (hist
->hvalue
.counters
);
231 #ifdef ENABLE_CHECKING
232 memset (hist
, 0xab, sizeof (*hist
));
238 /* Lookup histogram of type TYPE in the STMT. */
241 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
244 histogram_value hist
;
245 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
246 hist
= hist
->hvalue
.next
)
247 if (hist
->type
== type
)
252 /* Dump information about HIST to DUMP_FILE. */
255 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
259 case HIST_TYPE_INTERVAL
:
260 fprintf (dump_file
, "Interval counter range %d -- %d",
261 hist
->hdata
.intvl
.int_start
,
262 (hist
->hdata
.intvl
.int_start
263 + hist
->hdata
.intvl
.steps
- 1));
264 if (hist
->hvalue
.counters
)
267 fprintf (dump_file
, " [");
268 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
269 fprintf (dump_file
, " %d:%"PRId64
,
270 hist
->hdata
.intvl
.int_start
+ i
,
271 (int64_t) hist
->hvalue
.counters
[i
]);
272 fprintf (dump_file
, " ] outside range:%"PRId64
,
273 (int64_t) hist
->hvalue
.counters
[i
]);
275 fprintf (dump_file
, ".\n");
279 fprintf (dump_file
, "Pow2 counter ");
280 if (hist
->hvalue
.counters
)
282 fprintf (dump_file
, "pow2:%"PRId64
284 (int64_t) hist
->hvalue
.counters
[0],
285 (int64_t) hist
->hvalue
.counters
[1]);
287 fprintf (dump_file
, ".\n");
290 case HIST_TYPE_SINGLE_VALUE
:
291 fprintf (dump_file
, "Single value ");
292 if (hist
->hvalue
.counters
)
294 fprintf (dump_file
, "value:%"PRId64
297 (int64_t) hist
->hvalue
.counters
[0],
298 (int64_t) hist
->hvalue
.counters
[1],
299 (int64_t) hist
->hvalue
.counters
[2]);
301 fprintf (dump_file
, ".\n");
304 case HIST_TYPE_AVERAGE
:
305 fprintf (dump_file
, "Average value ");
306 if (hist
->hvalue
.counters
)
308 fprintf (dump_file
, "sum:%"PRId64
310 (int64_t) hist
->hvalue
.counters
[0],
311 (int64_t) hist
->hvalue
.counters
[1]);
313 fprintf (dump_file
, ".\n");
317 fprintf (dump_file
, "IOR value ");
318 if (hist
->hvalue
.counters
)
320 fprintf (dump_file
, "ior:%"PRId64
,
321 (int64_t) hist
->hvalue
.counters
[0]);
323 fprintf (dump_file
, ".\n");
326 case HIST_TYPE_CONST_DELTA
:
327 fprintf (dump_file
, "Constant delta ");
328 if (hist
->hvalue
.counters
)
330 fprintf (dump_file
, "value:%"PRId64
333 (int64_t) hist
->hvalue
.counters
[0],
334 (int64_t) hist
->hvalue
.counters
[1],
335 (int64_t) hist
->hvalue
.counters
[2]);
337 fprintf (dump_file
, ".\n");
339 case HIST_TYPE_INDIR_CALL
:
340 fprintf (dump_file
, "Indirect call ");
341 if (hist
->hvalue
.counters
)
343 fprintf (dump_file
, "value:%"PRId64
346 (int64_t) hist
->hvalue
.counters
[0],
347 (int64_t) hist
->hvalue
.counters
[1],
348 (int64_t) hist
->hvalue
.counters
[2]);
350 fprintf (dump_file
, ".\n");
352 case HIST_TYPE_TIME_PROFILE
:
353 fprintf (dump_file
, "Time profile ");
354 if (hist
->hvalue
.counters
)
356 fprintf (dump_file
, "time:%"PRId64
,
357 (int64_t) hist
->hvalue
.counters
[0]);
359 fprintf (dump_file
, ".\n");
366 /* Dump information about HIST to DUMP_FILE. */
369 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
374 bp
= bitpack_create (ob
->main_stream
);
375 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
376 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
377 streamer_write_bitpack (&bp
);
380 case HIST_TYPE_INTERVAL
:
381 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
382 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
387 for (i
= 0; i
< hist
->n_counters
; i
++)
388 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
389 if (hist
->hvalue
.next
)
390 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
:
440 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
441 new_val
->n_counters
= ncounters
;
442 for (i
= 0; i
< ncounters
; i
++)
443 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
445 gimple_add_histogram_value (cfun
, stmt
, new_val
);
448 next_p
= &new_val
->hvalue
.next
;
453 /* Dump all histograms attached to STMT to DUMP_FILE. */
456 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
458 histogram_value hist
;
459 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
460 dump_histogram_value (dump_file
, hist
);
463 /* Remove all histograms associated with STMT. */
466 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
469 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
470 gimple_remove_histogram_value (fun
, stmt
, val
);
473 /* Duplicate all histograms associates with OSTMT to STMT. */
476 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
477 struct function
*ofun
, gimple ostmt
)
480 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
482 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
483 memcpy (new_val
, val
, sizeof (*val
));
484 new_val
->hvalue
.stmt
= stmt
;
485 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
486 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
487 gimple_add_histogram_value (fun
, stmt
, new_val
);
492 /* Move all histograms associated with OSTMT to STMT. */
495 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
497 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
500 /* The following three statements can't be reordered,
501 because histogram hashtab relies on stmt field value
502 for finding the exact slot. */
503 set_histogram_value (fun
, ostmt
, NULL
);
504 for (; val
!= NULL
; val
= val
->hvalue
.next
)
505 val
->hvalue
.stmt
= stmt
;
506 set_histogram_value (fun
, stmt
, val
);
510 static bool error_found
= false;
512 /* Helper function for verify_histograms. For each histogram reachable via htab
513 walk verify that it was reached via statement walk. */
516 visit_hist (void **slot
, void *data
)
518 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
519 histogram_value hist
= *(histogram_value
*) slot
;
521 if (!pointer_set_contains (visited
, hist
)
522 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
524 error ("dead histogram");
525 dump_histogram_value (stderr
, hist
);
526 debug_gimple_stmt (hist
->hvalue
.stmt
);
533 /* Verify sanity of the histograms. */
536 verify_histograms (void)
539 gimple_stmt_iterator gsi
;
540 histogram_value hist
;
541 struct pointer_set_t
*visited_hists
;
544 visited_hists
= pointer_set_create ();
545 FOR_EACH_BB_FN (bb
, cfun
)
546 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
548 gimple stmt
= gsi_stmt (gsi
);
550 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
551 hist
= hist
->hvalue
.next
)
553 if (hist
->hvalue
.stmt
!= stmt
)
555 error ("Histogram value statement does not correspond to "
556 "the statement it is associated with");
557 debug_gimple_stmt (stmt
);
558 dump_histogram_value (stderr
, hist
);
561 pointer_set_insert (visited_hists
, hist
);
564 if (VALUE_HISTOGRAMS (cfun
))
565 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, visited_hists
);
566 pointer_set_destroy (visited_hists
);
568 internal_error ("verify_histograms failed");
571 /* Helper function for verify_histograms. For each histogram reachable via htab
572 walk verify that it was reached via statement walk. */
575 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
577 histogram_value hist
= *(histogram_value
*) slot
;
578 free (hist
->hvalue
.counters
);
579 #ifdef ENABLE_CHECKING
580 memset (hist
, 0xab, sizeof (*hist
));
587 free_histograms (void)
589 if (VALUE_HISTOGRAMS (cfun
))
591 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
592 htab_delete (VALUE_HISTOGRAMS (cfun
));
593 VALUE_HISTOGRAMS (cfun
) = NULL
;
598 /* The overall number of invocations of the counter should match
599 execution count of basic block. Report it as error rather than
600 internal error as it might mean that user has misused the profile
604 check_counter (gimple stmt
, const char * name
,
605 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
607 if (*all
!= bb_count
|| *count
> *all
)
610 locus
= (stmt
!= NULL
)
611 ? gimple_location (stmt
)
612 : DECL_SOURCE_LOCATION (current_function_decl
);
613 if (flag_profile_correction
)
615 if (dump_enabled_p ())
616 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
617 "correcting inconsistent value profile: %s "
618 "profiler overall count (%d) does not match BB "
619 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
627 error_at (locus
, "corrupted value profile: %s "
628 "profile counter (%d out of %d) inconsistent with "
629 "basic-block count (%d)",
642 /* GIMPLE based transformations. */
645 gimple_value_profile_transformations (void)
648 gimple_stmt_iterator gsi
;
649 bool changed
= false;
651 FOR_EACH_BB_FN (bb
, cfun
)
653 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
655 gimple stmt
= gsi_stmt (gsi
);
656 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
662 fprintf (dump_file
, "Trying transformations on stmt ");
663 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
664 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
667 /* Transformations: */
668 /* The order of things in this conditional controls which
669 transformation is used when more than one is applicable. */
670 /* It is expected that any code added by the transformations
671 will be added before the current statement, and that the
672 current statement remain valid (although possibly
673 modified) upon return. */
674 if (gimple_mod_subtract_transform (&gsi
)
675 || gimple_divmod_fixed_value_transform (&gsi
)
676 || gimple_mod_pow2_value_transform (&gsi
)
677 || gimple_stringops_transform (&gsi
)
678 || gimple_ic_transform (&gsi
))
680 stmt
= gsi_stmt (gsi
);
682 /* Original statement may no longer be in the same block. */
683 if (bb
!= gimple_bb (stmt
))
685 bb
= gimple_bb (stmt
);
686 gsi
= gsi_for_stmt (stmt
);
701 /* Generate code for transformation 1 (with parent gimple assignment
702 STMT and probability of taking the optimal path PROB, which is
703 equivalent to COUNT/ALL within roundoff error). This generates the
704 result into a temp and returns the temp; it does not replace or
705 alter the original STMT. */
708 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
711 gimple stmt1
, stmt2
, stmt3
;
712 tree tmp0
, tmp1
, tmp2
;
713 gimple bb1end
, bb2end
, bb3end
;
714 basic_block bb
, bb2
, bb3
, bb4
;
715 tree optype
, op1
, op2
;
716 edge e12
, e13
, e23
, e24
, e34
;
717 gimple_stmt_iterator gsi
;
719 gcc_assert (is_gimple_assign (stmt
)
720 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
721 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
723 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
724 op1
= gimple_assign_rhs1 (stmt
);
725 op2
= gimple_assign_rhs2 (stmt
);
727 bb
= gimple_bb (stmt
);
728 gsi
= gsi_for_stmt (stmt
);
730 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
731 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
732 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
733 stmt2
= gimple_build_assign (tmp1
, op2
);
734 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
735 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
736 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
737 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
740 tmp2
= create_tmp_reg (optype
, "PROF");
741 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
743 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
746 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
748 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
752 /* Edge e23 connects bb2 to bb3, etc. */
753 e12
= split_block (bb
, bb1end
);
756 e23
= split_block (bb2
, bb2end
);
758 bb3
->count
= all
- count
;
759 e34
= split_block (bb3
, bb3end
);
763 e12
->flags
&= ~EDGE_FALLTHRU
;
764 e12
->flags
|= EDGE_FALSE_VALUE
;
765 e12
->probability
= prob
;
768 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
769 e13
->probability
= REG_BR_PROB_BASE
- prob
;
770 e13
->count
= all
- count
;
774 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
775 e24
->probability
= REG_BR_PROB_BASE
;
778 e34
->probability
= REG_BR_PROB_BASE
;
779 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
= gsi_stmt (*si
);
798 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
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. */
871 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
873 gimple stmt1
, stmt2
, stmt3
, stmt4
;
875 gimple bb1end
, bb2end
, bb3end
;
876 basic_block bb
, bb2
, bb3
, bb4
;
877 tree optype
, op1
, op2
;
878 edge e12
, e13
, e23
, e24
, e34
;
879 gimple_stmt_iterator gsi
;
882 gcc_assert (is_gimple_assign (stmt
)
883 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
885 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
886 op1
= gimple_assign_rhs1 (stmt
);
887 op2
= gimple_assign_rhs2 (stmt
);
889 bb
= gimple_bb (stmt
);
890 gsi
= gsi_for_stmt (stmt
);
892 result
= create_tmp_reg (optype
, "PROF");
893 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
894 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
895 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
896 build_int_cst (optype
, -1));
897 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
898 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
899 NULL_TREE
, NULL_TREE
);
900 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
901 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
902 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
905 /* tmp2 == op2-1 inherited from previous block. */
906 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
907 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
910 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
912 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
916 /* Edge e23 connects bb2 to bb3, etc. */
917 e12
= split_block (bb
, bb1end
);
920 e23
= split_block (bb2
, bb2end
);
922 bb3
->count
= all
- count
;
923 e34
= split_block (bb3
, bb3end
);
927 e12
->flags
&= ~EDGE_FALLTHRU
;
928 e12
->flags
|= EDGE_FALSE_VALUE
;
929 e12
->probability
= prob
;
932 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
933 e13
->probability
= REG_BR_PROB_BASE
- prob
;
934 e13
->count
= all
- count
;
938 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
939 e24
->probability
= REG_BR_PROB_BASE
;
942 e34
->probability
= REG_BR_PROB_BASE
;
943 e34
->count
= all
- count
;
948 /* Do transform 2) on INSN if applicable. */
950 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
952 histogram_value histogram
;
954 gcov_type count
, wrong_values
, all
;
955 tree lhs_type
, result
, value
;
959 stmt
= gsi_stmt (*si
);
960 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
963 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
964 if (!INTEGRAL_TYPE_P (lhs_type
))
967 code
= gimple_assign_rhs_code (stmt
);
969 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
972 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
976 value
= histogram
->hvalue
.value
;
977 wrong_values
= histogram
->hvalue
.counters
[0];
978 count
= histogram
->hvalue
.counters
[1];
980 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
982 /* We require that we hit a power of 2 at least half of all evaluations. */
983 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
984 || count
< wrong_values
985 || optimize_bb_for_size_p (gimple_bb (stmt
)))
990 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
991 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
994 /* Compute probability of taking the optimal path. */
995 all
= count
+ wrong_values
;
997 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1001 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1005 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1007 gimple_assign_set_rhs_from_tree (si
, result
);
1008 update_stmt (gsi_stmt (*si
));
1013 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1014 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1015 supported and this is built into this interface. The probabilities of taking
1016 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1017 COUNT2/ALL respectively within roundoff error). This generates the
1018 result into a temp and returns the temp; it does not replace or alter
1019 the original STMT. */
1020 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1023 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
1024 gcov_type count1
, gcov_type count2
, gcov_type all
)
1026 gimple stmt1
, stmt2
, stmt3
;
1028 gimple bb1end
, bb2end
= NULL
, bb3end
;
1029 basic_block bb
, bb2
, bb3
, bb4
;
1030 tree optype
, op1
, op2
;
1031 edge e12
, e23
= 0, e24
, e34
, e14
;
1032 gimple_stmt_iterator gsi
;
1035 gcc_assert (is_gimple_assign (stmt
)
1036 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1038 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1039 op1
= gimple_assign_rhs1 (stmt
);
1040 op2
= gimple_assign_rhs2 (stmt
);
1042 bb
= gimple_bb (stmt
);
1043 gsi
= gsi_for_stmt (stmt
);
1045 result
= create_tmp_reg (optype
, "PROF");
1046 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1047 stmt1
= gimple_build_assign (result
, op1
);
1048 stmt2
= gimple_build_assign (tmp1
, op2
);
1049 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1050 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1051 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1052 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1055 if (ncounts
) /* Assumed to be 0 or 1 */
1057 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
1058 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1059 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1060 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1064 /* Fallback case. */
1065 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
1067 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1071 /* Edge e23 connects bb2 to bb3, etc. */
1072 /* However block 3 is optional; if it is not there, references
1073 to 3 really refer to block 2. */
1074 e12
= split_block (bb
, bb1end
);
1076 bb2
->count
= all
- count1
;
1078 if (ncounts
) /* Assumed to be 0 or 1. */
1080 e23
= split_block (bb2
, bb2end
);
1082 bb3
->count
= all
- count1
- count2
;
1085 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1089 e12
->flags
&= ~EDGE_FALLTHRU
;
1090 e12
->flags
|= EDGE_FALSE_VALUE
;
1091 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1092 e12
->count
= all
- count1
;
1094 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1095 e14
->probability
= prob1
;
1096 e14
->count
= count1
;
1098 if (ncounts
) /* Assumed to be 0 or 1. */
1100 e23
->flags
&= ~EDGE_FALLTHRU
;
1101 e23
->flags
|= EDGE_FALSE_VALUE
;
1102 e23
->count
= all
- count1
- count2
;
1103 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1105 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1106 e24
->probability
= prob2
;
1107 e24
->count
= count2
;
1110 e34
->probability
= REG_BR_PROB_BASE
;
1111 e34
->count
= all
- count1
- count2
;
1117 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1120 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1122 histogram_value histogram
;
1123 enum tree_code code
;
1124 gcov_type count
, wrong_values
, all
;
1125 tree lhs_type
, result
;
1126 gcov_type prob1
, prob2
;
1127 unsigned int i
, steps
;
1128 gcov_type count1
, count2
;
1131 stmt
= gsi_stmt (*si
);
1132 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1135 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1136 if (!INTEGRAL_TYPE_P (lhs_type
))
1139 code
= gimple_assign_rhs_code (stmt
);
1141 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1144 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1150 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1151 all
+= histogram
->hvalue
.counters
[i
];
1153 wrong_values
+= histogram
->hvalue
.counters
[i
];
1154 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1155 steps
= histogram
->hdata
.intvl
.steps
;
1156 all
+= wrong_values
;
1157 count1
= histogram
->hvalue
.counters
[0];
1158 count2
= histogram
->hvalue
.counters
[1];
1160 /* Compute probability of taking the optimal path. */
1161 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1163 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1167 if (flag_profile_correction
&& count1
+ count2
> all
)
1168 all
= count1
+ count2
;
1170 gcc_assert (count1
+ count2
<= all
);
1172 /* We require that we use just subtractions in at least 50% of all
1175 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1177 count
+= histogram
->hvalue
.counters
[i
];
1178 if (count
* 2 >= all
)
1182 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1185 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1188 fprintf (dump_file
, "Mod subtract transformation on insn ");
1189 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1192 /* Compute probability of taking the optimal path(s). */
1195 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1196 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1203 /* In practice, "steps" is always 2. This interface reflects this,
1204 and will need to be changed if "steps" can change. */
1205 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1207 gimple_assign_set_rhs_from_tree (si
, result
);
1208 update_stmt (gsi_stmt (*si
));
1213 static pointer_map_t
*cgraph_node_map
= 0;
1215 /* Returns true if node graph is initialized. This
1216 is used to test if profile_id has been created
1217 for cgraph_nodes. */
1220 coverage_node_map_initialized_p (void)
1222 return cgraph_node_map
!= 0;
1225 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1226 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1227 that the PROFILE_IDs was already assigned. */
1230 init_node_map (bool local
)
1232 struct cgraph_node
*n
;
1233 cgraph_node_map
= pointer_map_create ();
1235 FOR_EACH_DEFINED_FUNCTION (n
)
1236 if (n
->has_gimple_body_p ())
1241 n
->profile_id
= coverage_compute_profile_id (n
);
1242 while ((val
= pointer_map_contains (cgraph_node_map
,
1243 (void *)(size_t)n
->profile_id
))
1247 fprintf (dump_file
, "Local profile-id %i conflict"
1248 " with nodes %s/%i %s/%i\n",
1252 (*(symtab_node
**)val
)->name (),
1253 (*(symtab_node
**)val
)->order
);
1254 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1257 else if (!n
->profile_id
)
1261 "Node %s/%i has no profile-id"
1262 " (profile feedback missing?)\n",
1267 else if ((val
= pointer_map_contains (cgraph_node_map
,
1268 (void *)(size_t)n
->profile_id
)))
1272 "Node %s/%i has IP profile-id %i conflict. "
1280 *pointer_map_insert (cgraph_node_map
,
1281 (void *)(size_t)n
->profile_id
) = (void *)n
;
1285 /* Delete the CGRAPH_NODE_MAP. */
1290 pointer_map_destroy (cgraph_node_map
);
1293 /* Return cgraph node for function with pid */
1296 find_func_by_profile_id (int profile_id
)
1298 void **val
= pointer_map_contains (cgraph_node_map
,
1299 (void *)(size_t)profile_id
);
1301 return (struct cgraph_node
*)*val
;
1306 /* Perform sanity check on the indirect call target. Due to race conditions,
1307 false function target may be attributed to an indirect call site. If the
1308 call expression type mismatches with the target function's type, expand_call
1309 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1310 Returns true if TARGET is considered ok for call CALL_STMT. */
1313 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1316 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1319 locus
= gimple_location (call_stmt
);
1320 if (dump_enabled_p ())
1321 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1322 "Skipping target %s with mismatching types for icall\n",
1327 /* Do transformation
1329 if (actual_callee_address == address_of_most_common_function/method)
1336 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1337 int prob
, gcov_type count
, gcov_type all
)
1339 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1340 tree tmp0
, tmp1
, tmp
;
1341 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1342 tree optype
= build_pointer_type (void_type_node
);
1343 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1344 gimple_stmt_iterator gsi
;
1348 gimple_stmt_iterator psi
;
1350 cond_bb
= gimple_bb (icall_stmt
);
1351 gsi
= gsi_for_stmt (icall_stmt
);
1353 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1354 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1355 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1356 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1357 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1359 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1360 current_function_decl
));
1361 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1362 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1364 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1365 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1367 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1368 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1369 update_stmt (icall_stmt
);
1370 dcall_stmt
= gimple_copy (icall_stmt
);
1371 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1372 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1373 if ((dflags
& ECF_NORETURN
) != 0)
1374 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1375 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1378 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1379 e_cd
= split_block (cond_bb
, cond_stmt
);
1380 dcall_bb
= e_cd
->dest
;
1381 dcall_bb
->count
= count
;
1383 e_di
= split_block (dcall_bb
, dcall_stmt
);
1384 icall_bb
= e_di
->dest
;
1385 icall_bb
->count
= all
- count
;
1387 /* Do not disturb existing EH edges from the indirect call. */
1388 if (!stmt_ends_bb_p (icall_stmt
))
1389 e_ij
= split_block (icall_bb
, icall_stmt
);
1392 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1393 /* The indirect call might be noreturn. */
1396 e_ij
->probability
= REG_BR_PROB_BASE
;
1397 e_ij
->count
= all
- count
;
1398 e_ij
= single_pred_edge (split_edge (e_ij
));
1403 join_bb
= e_ij
->dest
;
1404 join_bb
->count
= all
;
1407 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1408 e_cd
->probability
= prob
;
1409 e_cd
->count
= count
;
1411 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1412 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1413 e_ci
->count
= all
- count
;
1419 if ((dflags
& ECF_NORETURN
) != 0)
1423 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1424 e_dj
->probability
= REG_BR_PROB_BASE
;
1425 e_dj
->count
= count
;
1427 e_ij
->count
= all
- count
;
1429 e_ij
->probability
= REG_BR_PROB_BASE
;
1432 /* Insert PHI node for the call result if necessary. */
1433 if (gimple_call_lhs (icall_stmt
)
1434 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1435 && (dflags
& ECF_NORETURN
) == 0)
1437 tree result
= gimple_call_lhs (icall_stmt
);
1438 gimple phi
= create_phi_node (result
, join_bb
);
1439 gimple_call_set_lhs (icall_stmt
,
1440 duplicate_ssa_name (result
, icall_stmt
));
1441 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1442 gimple_call_set_lhs (dcall_stmt
,
1443 duplicate_ssa_name (result
, dcall_stmt
));
1444 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1447 /* Build an EH edge for the direct call if necessary. */
1448 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1449 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1451 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1454 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1455 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1457 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1458 for (psi
= gsi_start_phis (e_eh
->dest
);
1459 !gsi_end_p (psi
); gsi_next (&psi
))
1461 gimple phi
= gsi_stmt (psi
);
1462 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1463 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1470 For every checked indirect/virtual call determine if most common pid of
1471 function/class method has probability more than 50%. If yes modify code of
1476 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1478 gimple stmt
= gsi_stmt (*gsi
);
1479 histogram_value histogram
;
1480 gcov_type val
, count
, all
, bb_all
;
1481 struct cgraph_node
*direct_call
;
1483 if (gimple_code (stmt
) != GIMPLE_CALL
)
1486 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1489 if (gimple_call_internal_p (stmt
))
1492 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1496 val
= histogram
->hvalue
.counters
[0];
1497 count
= histogram
->hvalue
.counters
[1];
1498 all
= histogram
->hvalue
.counters
[2];
1500 bb_all
= gimple_bb (stmt
)->count
;
1501 /* The order of CHECK_COUNTER calls is important -
1502 since check_counter can correct the third parameter
1503 and we want to make count <= all <= bb_all. */
1504 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1505 || check_counter (stmt
, "ic", &count
, &all
, all
))
1507 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1511 if (4 * count
<= 3 * all
)
1514 direct_call
= find_func_by_profile_id ((int)val
);
1516 if (direct_call
== NULL
)
1522 fprintf (dump_file
, "Indirect call -> direct call from other module");
1523 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1524 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1530 if (!check_ic_target (stmt
, direct_call
))
1534 fprintf (dump_file
, "Indirect call -> direct call ");
1535 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1536 fprintf (dump_file
, "=> ");
1537 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1538 fprintf (dump_file
, " transformation skipped because of type mismatch");
1539 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1541 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1547 fprintf (dump_file
, "Indirect call -> direct call ");
1548 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1549 fprintf (dump_file
, "=> ");
1550 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1551 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1552 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1553 fprintf (dump_file
, "hist->count %"PRId64
1554 " hist->all %"PRId64
"\n", count
, all
);
1560 /* Return true if the stringop CALL with FNDECL shall be profiled.
1561 SIZE_ARG be set to the argument index for the size of the string
1565 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1567 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1569 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1570 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1575 case BUILT_IN_MEMCPY
:
1576 case BUILT_IN_MEMPCPY
:
1578 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1579 INTEGER_TYPE
, VOID_TYPE
);
1580 case BUILT_IN_MEMSET
:
1582 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1583 INTEGER_TYPE
, VOID_TYPE
);
1584 case BUILT_IN_BZERO
:
1586 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1593 /* Convert stringop (..., vcall_size)
1595 if (vcall_size == icall_size)
1596 stringop (..., icall_size);
1598 stringop (..., vcall_size);
1599 assuming we'll propagate a true constant into ICALL_SIZE later. */
1602 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1603 gcov_type count
, gcov_type all
)
1605 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1606 tree tmp0
, tmp1
, vcall_size
, optype
;
1607 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1608 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1609 gimple_stmt_iterator gsi
;
1613 fndecl
= gimple_call_fndecl (vcall_stmt
);
1614 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1617 cond_bb
= gimple_bb (vcall_stmt
);
1618 gsi
= gsi_for_stmt (vcall_stmt
);
1620 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1621 optype
= TREE_TYPE (vcall_size
);
1623 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1624 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1625 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1626 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1628 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1629 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1631 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1632 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1634 gimple_set_vdef (vcall_stmt
, NULL
);
1635 gimple_set_vuse (vcall_stmt
, NULL
);
1636 update_stmt (vcall_stmt
);
1637 icall_stmt
= gimple_copy (vcall_stmt
);
1638 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1639 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1642 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1643 e_ci
= split_block (cond_bb
, cond_stmt
);
1644 icall_bb
= e_ci
->dest
;
1645 icall_bb
->count
= count
;
1647 e_iv
= split_block (icall_bb
, icall_stmt
);
1648 vcall_bb
= e_iv
->dest
;
1649 vcall_bb
->count
= all
- count
;
1651 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1652 join_bb
= e_vj
->dest
;
1653 join_bb
->count
= all
;
1655 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1656 e_ci
->probability
= prob
;
1657 e_ci
->count
= count
;
1659 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1660 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1661 e_cv
->count
= all
- count
;
1665 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1666 e_ij
->probability
= REG_BR_PROB_BASE
;
1667 e_ij
->count
= count
;
1669 e_vj
->probability
= REG_BR_PROB_BASE
;
1670 e_vj
->count
= all
- count
;
1672 /* Insert PHI node for the call result if necessary. */
1673 if (gimple_call_lhs (vcall_stmt
)
1674 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1676 tree result
= gimple_call_lhs (vcall_stmt
);
1677 gimple phi
= create_phi_node (result
, join_bb
);
1678 gimple_call_set_lhs (vcall_stmt
,
1679 duplicate_ssa_name (result
, vcall_stmt
));
1680 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1681 gimple_call_set_lhs (icall_stmt
,
1682 duplicate_ssa_name (result
, icall_stmt
));
1683 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1686 /* Because these are all string op builtins, they're all nothrow. */
1687 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1688 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1691 /* Find values inside STMT for that we want to measure histograms for
1692 division/modulo optimization. */
1694 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1696 gimple stmt
= gsi_stmt (*gsi
);
1699 enum built_in_function fcode
;
1700 histogram_value histogram
;
1701 gcov_type count
, all
, val
;
1703 unsigned int dest_align
, src_align
;
1708 if (gimple_code (stmt
) != GIMPLE_CALL
)
1710 fndecl
= gimple_call_fndecl (stmt
);
1713 fcode
= DECL_FUNCTION_CODE (fndecl
);
1714 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1717 blck_size
= gimple_call_arg (stmt
, size_arg
);
1718 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1721 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1724 val
= histogram
->hvalue
.counters
[0];
1725 count
= histogram
->hvalue
.counters
[1];
1726 all
= histogram
->hvalue
.counters
[2];
1727 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1728 /* We require that count is at least half of all; this means
1729 that for the transformation to fire the value must be constant
1730 at least 80% of time. */
1731 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1733 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1736 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1739 dest
= gimple_call_arg (stmt
, 0);
1740 dest_align
= get_pointer_alignment (dest
);
1743 case BUILT_IN_MEMCPY
:
1744 case BUILT_IN_MEMPCPY
:
1745 src
= gimple_call_arg (stmt
, 1);
1746 src_align
= get_pointer_alignment (src
);
1747 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1750 case BUILT_IN_MEMSET
:
1751 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1752 gimple_call_arg (stmt
, 1),
1756 case BUILT_IN_BZERO
:
1757 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1765 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1766 tree_val
= build_int_cst (get_gcov_type (), val
);
1770 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1771 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1773 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1774 TYPE_PRECISION (get_gcov_type ()), false));
1779 fprintf (dump_file
, "Single value %i stringop transformation on ",
1781 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1783 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1789 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1790 HOST_WIDE_INT
*expected_size
)
1792 histogram_value histogram
;
1793 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1795 *expected_size
= -1;
1796 else if (!histogram
->hvalue
.counters
[1])
1798 *expected_size
= -1;
1799 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1804 size
= ((histogram
->hvalue
.counters
[0]
1805 + histogram
->hvalue
.counters
[1] / 2)
1806 / histogram
->hvalue
.counters
[1]);
1807 /* Even if we can hold bigger value in SIZE, INT_MAX
1808 is safe "infinity" for code generation strategies. */
1811 *expected_size
= size
;
1812 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1814 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1816 *expected_align
= 0;
1817 else if (!histogram
->hvalue
.counters
[0])
1819 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1820 *expected_align
= 0;
1827 count
= histogram
->hvalue
.counters
[0];
1829 while (!(count
& alignment
)
1830 && (alignment
* 2 * BITS_PER_UNIT
))
1832 *expected_align
= alignment
* BITS_PER_UNIT
;
1833 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1838 /* Find values inside STMT for that we want to measure histograms for
1839 division/modulo optimization. */
1841 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1843 tree lhs
, divisor
, op0
, type
;
1844 histogram_value hist
;
1846 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1849 lhs
= gimple_assign_lhs (stmt
);
1850 type
= TREE_TYPE (lhs
);
1851 if (!INTEGRAL_TYPE_P (type
))
1854 switch (gimple_assign_rhs_code (stmt
))
1856 case TRUNC_DIV_EXPR
:
1857 case TRUNC_MOD_EXPR
:
1858 divisor
= gimple_assign_rhs2 (stmt
);
1859 op0
= gimple_assign_rhs1 (stmt
);
1861 values
->reserve (3);
1863 if (TREE_CODE (divisor
) == SSA_NAME
)
1864 /* Check for the case where the divisor is the same value most
1866 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1867 HIST_TYPE_SINGLE_VALUE
,
1870 /* For mod, check whether it is not often a noop (or replaceable by
1871 a few subtractions). */
1872 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1873 && TYPE_UNSIGNED (type
))
1876 /* Check for a special case where the divisor is power of 2. */
1877 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1881 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1882 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1884 hist
->hdata
.intvl
.int_start
= 0;
1885 hist
->hdata
.intvl
.steps
= 2;
1886 values
->quick_push (hist
);
1895 /* Find calls inside STMT for that we want to measure histograms for
1896 indirect/virtual call optimization. */
1899 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1903 if (gimple_code (stmt
) != GIMPLE_CALL
1904 || gimple_call_internal_p (stmt
)
1905 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1908 callee
= gimple_call_fn (stmt
);
1910 values
->reserve (3);
1912 values
->quick_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1918 /* Find values inside STMT for that we want to measure histograms for
1919 string operations. */
1921 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1928 if (gimple_code (stmt
) != GIMPLE_CALL
)
1930 fndecl
= gimple_call_fndecl (stmt
);
1934 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1937 dest
= gimple_call_arg (stmt
, 0);
1938 blck_size
= gimple_call_arg (stmt
, size_arg
);
1940 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1942 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1943 HIST_TYPE_SINGLE_VALUE
,
1945 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1948 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1949 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1953 /* Find values inside STMT for that we want to measure histograms and adds
1954 them to list VALUES. */
1957 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1959 gimple_divmod_values_to_profile (stmt
, values
);
1960 gimple_stringops_values_to_profile (stmt
, values
);
1961 gimple_indirect_call_to_profile (stmt
, values
);
1965 gimple_find_values_to_profile (histogram_values
*values
)
1968 gimple_stmt_iterator gsi
;
1970 histogram_value hist
= NULL
;
1973 FOR_EACH_BB_FN (bb
, cfun
)
1974 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1975 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1977 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
1979 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1983 case HIST_TYPE_INTERVAL
:
1984 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1987 case HIST_TYPE_POW2
:
1988 hist
->n_counters
= 2;
1991 case HIST_TYPE_SINGLE_VALUE
:
1992 hist
->n_counters
= 3;
1995 case HIST_TYPE_CONST_DELTA
:
1996 hist
->n_counters
= 4;
1999 case HIST_TYPE_INDIR_CALL
:
2000 hist
->n_counters
= 3;
2003 case HIST_TYPE_TIME_PROFILE
:
2004 hist
->n_counters
= 1;
2007 case HIST_TYPE_AVERAGE
:
2008 hist
->n_counters
= 2;
2012 hist
->n_counters
= 1;
2020 fprintf (dump_file
, "Stmt ");
2021 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2022 dump_histogram_value (dump_file
, hist
);