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"
64 /* In this file value profile based optimizations are placed. Currently the
65 following optimizations are implemented (for more detailed descriptions
66 see comments at value_profile_transformations):
68 1) Division/modulo specialization. Provided that we can determine that the
69 operands of the division have some special properties, we may use it to
70 produce more effective code.
72 2) Indirect/virtual call specialization. If we can determine most
73 common function callee in indirect/virtual call. We can use this
74 information to improve code effectiveness (especially info for
77 3) Speculative prefetching. If we are able to determine that the difference
78 between addresses accessed by a memory reference is usually constant, we
79 may add the prefetch instructions.
80 FIXME: This transformation was removed together with RTL based value
84 Value profiling internals
85 ==========================
87 Every value profiling transformation starts with defining what values
88 to profile. There are different histogram types (see HIST_TYPE_* in
89 value-prof.h) and each transformation can request one or more histogram
90 types per GIMPLE statement. The function gimple_find_values_to_profile()
91 collects the values to profile in a vec, and adds the number of counters
92 required for the different histogram types.
94 For a -fprofile-generate run, the statements for which values should be
95 recorded, are instrumented in instrument_values(). The instrumentation
96 is done by helper functions that can be found in tree-profile.c, where
97 new types of histograms can be added if necessary.
99 After a -fprofile-use, the value profiling data is read back in by
100 compute_value_histograms() that translates the collected data to
101 histograms and attaches them to the profiled statements via
102 gimple_add_histogram_value(). Histograms are stored in a hash table
103 that is attached to every intrumented function, see VALUE_HISTOGRAMS
106 The value-profile transformations driver is the function
107 gimple_value_profile_transformations(). It traverses all statements in
108 the to-be-transformed function, and looks for statements with one or
109 more histograms attached to it. If a statement has histograms, the
110 transformation functions are called on the statement.
112 Limitations / FIXME / TODO:
113 * Only one histogram of each type can be associated with a statement.
114 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
115 (This type of histogram was originally used to implement a form of
116 stride profiling based speculative prefetching to improve SPEC2000
117 scores for memory-bound benchmarks, mcf and equake. However, this
118 was an RTL value-profiling transformation, and those have all been
120 * Some value profile transformations are done in builtins.c (?!)
121 * Updating of histograms needs some TLC.
122 * The value profiling code could be used to record analysis results
123 from non-profiling (e.g. VRP).
124 * Adding new profilers should be simplified, starting with a cleanup
125 of what-happens-where andwith making gimple_find_values_to_profile
126 and gimple_value_profile_transformations table-driven, perhaps...
129 static tree
gimple_divmod_fixed_value (gimple
, tree
, int, gcov_type
, gcov_type
);
130 static tree
gimple_mod_pow2 (gimple
, int, gcov_type
, gcov_type
);
131 static tree
gimple_mod_subtract (gimple
, int, int, int, gcov_type
, gcov_type
,
133 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
134 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
135 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
136 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
137 static bool gimple_ic_transform (gimple_stmt_iterator
*);
139 /* Allocate histogram value. */
141 static histogram_value
142 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
143 enum hist_type type
, gimple stmt
, tree value
)
145 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
146 hist
->hvalue
.value
= value
;
147 hist
->hvalue
.stmt
= stmt
;
152 /* Hash value for histogram. */
155 histogram_hash (const void *x
)
157 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
160 /* Return nonzero if statement for histogram_value X is Y. */
163 histogram_eq (const void *x
, const void *y
)
165 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
168 /* Set histogram for STMT. */
171 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
174 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
176 if (!VALUE_HISTOGRAMS (fun
))
177 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
179 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
180 htab_hash_pointer (stmt
),
181 hist
? INSERT
: NO_INSERT
);
185 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
191 /* Get histogram list for STMT. */
194 gimple_histogram_value (struct function
*fun
, gimple stmt
)
196 if (!VALUE_HISTOGRAMS (fun
))
198 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
199 htab_hash_pointer (stmt
));
202 /* Add histogram for STMT. */
205 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
206 histogram_value hist
)
208 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
209 set_histogram_value (fun
, stmt
, hist
);
214 /* Remove histogram HIST from STMT's histogram list. */
217 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
218 histogram_value hist
)
220 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
223 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
227 while (hist2
->hvalue
.next
!= hist
)
228 hist2
= hist2
->hvalue
.next
;
229 hist2
->hvalue
.next
= hist
->hvalue
.next
;
231 free (hist
->hvalue
.counters
);
232 #ifdef ENABLE_CHECKING
233 memset (hist
, 0xab, sizeof (*hist
));
239 /* Lookup histogram of type TYPE in the STMT. */
242 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
245 histogram_value hist
;
246 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
247 hist
= hist
->hvalue
.next
)
248 if (hist
->type
== type
)
253 /* Dump information about HIST to DUMP_FILE. */
256 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
260 case HIST_TYPE_INTERVAL
:
261 fprintf (dump_file
, "Interval counter range %d -- %d",
262 hist
->hdata
.intvl
.int_start
,
263 (hist
->hdata
.intvl
.int_start
264 + hist
->hdata
.intvl
.steps
- 1));
265 if (hist
->hvalue
.counters
)
268 fprintf (dump_file
, " [");
269 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
270 fprintf (dump_file
, " %d:%"PRId64
,
271 hist
->hdata
.intvl
.int_start
+ i
,
272 (int64_t) hist
->hvalue
.counters
[i
]);
273 fprintf (dump_file
, " ] outside range:%"PRId64
,
274 (int64_t) hist
->hvalue
.counters
[i
]);
276 fprintf (dump_file
, ".\n");
280 fprintf (dump_file
, "Pow2 counter ");
281 if (hist
->hvalue
.counters
)
283 fprintf (dump_file
, "pow2:%"PRId64
285 (int64_t) hist
->hvalue
.counters
[0],
286 (int64_t) hist
->hvalue
.counters
[1]);
288 fprintf (dump_file
, ".\n");
291 case HIST_TYPE_SINGLE_VALUE
:
292 fprintf (dump_file
, "Single value ");
293 if (hist
->hvalue
.counters
)
295 fprintf (dump_file
, "value:%"PRId64
298 (int64_t) hist
->hvalue
.counters
[0],
299 (int64_t) hist
->hvalue
.counters
[1],
300 (int64_t) hist
->hvalue
.counters
[2]);
302 fprintf (dump_file
, ".\n");
305 case HIST_TYPE_AVERAGE
:
306 fprintf (dump_file
, "Average value ");
307 if (hist
->hvalue
.counters
)
309 fprintf (dump_file
, "sum:%"PRId64
311 (int64_t) hist
->hvalue
.counters
[0],
312 (int64_t) hist
->hvalue
.counters
[1]);
314 fprintf (dump_file
, ".\n");
318 fprintf (dump_file
, "IOR value ");
319 if (hist
->hvalue
.counters
)
321 fprintf (dump_file
, "ior:%"PRId64
,
322 (int64_t) hist
->hvalue
.counters
[0]);
324 fprintf (dump_file
, ".\n");
327 case HIST_TYPE_CONST_DELTA
:
328 fprintf (dump_file
, "Constant delta ");
329 if (hist
->hvalue
.counters
)
331 fprintf (dump_file
, "value:%"PRId64
334 (int64_t) hist
->hvalue
.counters
[0],
335 (int64_t) hist
->hvalue
.counters
[1],
336 (int64_t) hist
->hvalue
.counters
[2]);
338 fprintf (dump_file
, ".\n");
340 case HIST_TYPE_INDIR_CALL
:
341 fprintf (dump_file
, "Indirect call ");
342 if (hist
->hvalue
.counters
)
344 fprintf (dump_file
, "value:%"PRId64
347 (int64_t) hist
->hvalue
.counters
[0],
348 (int64_t) hist
->hvalue
.counters
[1],
349 (int64_t) hist
->hvalue
.counters
[2]);
351 fprintf (dump_file
, ".\n");
353 case HIST_TYPE_TIME_PROFILE
:
354 fprintf (dump_file
, "Time profile ");
355 if (hist
->hvalue
.counters
)
357 fprintf (dump_file
, "time:%"PRId64
,
358 (int64_t) hist
->hvalue
.counters
[0]);
360 fprintf (dump_file
, ".\n");
367 /* Dump information about HIST to DUMP_FILE. */
370 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
375 bp
= bitpack_create (ob
->main_stream
);
376 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
377 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
378 streamer_write_bitpack (&bp
);
381 case HIST_TYPE_INTERVAL
:
382 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
383 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
388 for (i
= 0; i
< hist
->n_counters
; i
++)
389 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
390 if (hist
->hvalue
.next
)
391 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
393 /* Dump information about HIST to DUMP_FILE. */
396 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
399 unsigned int ncounters
= 0;
402 histogram_value new_val
;
404 histogram_value
*next_p
= NULL
;
408 bp
= streamer_read_bitpack (ib
);
409 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
410 next
= bp_unpack_value (&bp
, 1);
411 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
414 case HIST_TYPE_INTERVAL
:
415 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
416 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
417 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
421 case HIST_TYPE_AVERAGE
:
425 case HIST_TYPE_SINGLE_VALUE
:
426 case HIST_TYPE_INDIR_CALL
:
430 case HIST_TYPE_CONST_DELTA
:
435 case HIST_TYPE_TIME_PROFILE
:
441 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
442 new_val
->n_counters
= ncounters
;
443 for (i
= 0; i
< ncounters
; i
++)
444 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
446 gimple_add_histogram_value (cfun
, stmt
, new_val
);
449 next_p
= &new_val
->hvalue
.next
;
454 /* Dump all histograms attached to STMT to DUMP_FILE. */
457 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
459 histogram_value hist
;
460 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
461 dump_histogram_value (dump_file
, hist
);
464 /* Remove all histograms associated with STMT. */
467 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
470 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
471 gimple_remove_histogram_value (fun
, stmt
, val
);
474 /* Duplicate all histograms associates with OSTMT to STMT. */
477 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
478 struct function
*ofun
, gimple ostmt
)
481 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
483 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
484 memcpy (new_val
, val
, sizeof (*val
));
485 new_val
->hvalue
.stmt
= stmt
;
486 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
487 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
488 gimple_add_histogram_value (fun
, stmt
, new_val
);
493 /* Move all histograms associated with OSTMT to STMT. */
496 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
498 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
501 /* The following three statements can't be reordered,
502 because histogram hashtab relies on stmt field value
503 for finding the exact slot. */
504 set_histogram_value (fun
, ostmt
, NULL
);
505 for (; val
!= NULL
; val
= val
->hvalue
.next
)
506 val
->hvalue
.stmt
= stmt
;
507 set_histogram_value (fun
, stmt
, val
);
511 static bool error_found
= false;
513 /* Helper function for verify_histograms. For each histogram reachable via htab
514 walk verify that it was reached via statement walk. */
517 visit_hist (void **slot
, void *data
)
519 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
520 histogram_value hist
= *(histogram_value
*) slot
;
522 if (!visited
->contains (hist
)
523 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
525 error ("dead histogram");
526 dump_histogram_value (stderr
, hist
);
527 debug_gimple_stmt (hist
->hvalue
.stmt
);
534 /* Verify sanity of the histograms. */
537 verify_histograms (void)
540 gimple_stmt_iterator gsi
;
541 histogram_value hist
;
544 hash_set
<histogram_value
> visited_hists
;
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 visited_hists
.add (hist
);
564 if (VALUE_HISTOGRAMS (cfun
))
565 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
567 internal_error ("verify_histograms failed");
570 /* Helper function for verify_histograms. For each histogram reachable via htab
571 walk verify that it was reached via statement walk. */
574 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
576 histogram_value hist
= *(histogram_value
*) slot
;
577 free (hist
->hvalue
.counters
);
578 #ifdef ENABLE_CHECKING
579 memset (hist
, 0xab, sizeof (*hist
));
586 free_histograms (void)
588 if (VALUE_HISTOGRAMS (cfun
))
590 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
591 htab_delete (VALUE_HISTOGRAMS (cfun
));
592 VALUE_HISTOGRAMS (cfun
) = 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)",
641 /* GIMPLE based transformations. */
644 gimple_value_profile_transformations (void)
647 gimple_stmt_iterator gsi
;
648 bool changed
= false;
650 FOR_EACH_BB_FN (bb
, cfun
)
652 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
654 gimple stmt
= gsi_stmt (gsi
);
655 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
661 fprintf (dump_file
, "Trying transformations on stmt ");
662 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
663 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
666 /* Transformations: */
667 /* The order of things in this conditional controls which
668 transformation is used when more than one is applicable. */
669 /* It is expected that any code added by the transformations
670 will be added before the current statement, and that the
671 current statement remain valid (although possibly
672 modified) upon return. */
673 if (gimple_mod_subtract_transform (&gsi
)
674 || gimple_divmod_fixed_value_transform (&gsi
)
675 || gimple_mod_pow2_value_transform (&gsi
)
676 || gimple_stringops_transform (&gsi
)
677 || gimple_ic_transform (&gsi
))
679 stmt
= gsi_stmt (gsi
);
681 /* Original statement may no longer be in the same block. */
682 if (bb
!= gimple_bb (stmt
))
684 bb
= gimple_bb (stmt
);
685 gsi
= gsi_for_stmt (stmt
);
700 /* Generate code for transformation 1 (with parent gimple assignment
701 STMT and probability of taking the optimal path PROB, which is
702 equivalent to COUNT/ALL within roundoff error). This generates the
703 result into a temp and returns the temp; it does not replace or
704 alter the original STMT. */
707 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
710 gimple stmt1
, stmt2
, stmt3
;
711 tree tmp0
, tmp1
, tmp2
;
712 gimple bb1end
, bb2end
, bb3end
;
713 basic_block bb
, bb2
, bb3
, bb4
;
714 tree optype
, op1
, op2
;
715 edge e12
, e13
, e23
, e24
, e34
;
716 gimple_stmt_iterator gsi
;
718 gcc_assert (is_gimple_assign (stmt
)
719 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
720 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
722 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
723 op1
= gimple_assign_rhs1 (stmt
);
724 op2
= gimple_assign_rhs2 (stmt
);
726 bb
= gimple_bb (stmt
);
727 gsi
= gsi_for_stmt (stmt
);
729 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
730 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
731 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
732 stmt2
= gimple_build_assign (tmp1
, op2
);
733 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
734 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
735 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
736 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
739 tmp2
= create_tmp_reg (optype
, "PROF");
740 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
742 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
745 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
747 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
751 /* Edge e23 connects bb2 to bb3, etc. */
752 e12
= split_block (bb
, bb1end
);
755 e23
= split_block (bb2
, bb2end
);
757 bb3
->count
= all
- count
;
758 e34
= split_block (bb3
, bb3end
);
762 e12
->flags
&= ~EDGE_FALLTHRU
;
763 e12
->flags
|= EDGE_FALSE_VALUE
;
764 e12
->probability
= prob
;
767 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
768 e13
->probability
= REG_BR_PROB_BASE
- prob
;
769 e13
->count
= all
- count
;
773 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
774 e24
->probability
= REG_BR_PROB_BASE
;
777 e34
->probability
= REG_BR_PROB_BASE
;
778 e34
->count
= all
- count
;
784 /* Do transform 1) on INSN if applicable. */
787 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
789 histogram_value histogram
;
791 gcov_type val
, count
, all
;
792 tree result
, value
, tree_val
;
796 stmt
= gsi_stmt (*si
);
797 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
800 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
803 code
= gimple_assign_rhs_code (stmt
);
805 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
808 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
809 HIST_TYPE_SINGLE_VALUE
);
813 value
= histogram
->hvalue
.value
;
814 val
= histogram
->hvalue
.counters
[0];
815 count
= histogram
->hvalue
.counters
[1];
816 all
= histogram
->hvalue
.counters
[2];
817 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
819 /* We require that count is at least half of all; this means
820 that for the transformation to fire the value must be constant
821 at least 50% of time (and 75% gives the guarantee of usage). */
822 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
824 || optimize_bb_for_size_p (gimple_bb (stmt
)))
827 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
830 /* Compute probability of taking the optimal path. */
832 prob
= GCOV_COMPUTE_SCALE (count
, all
);
836 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
837 tree_val
= build_int_cst (get_gcov_type (), val
);
841 a
[0] = (unsigned HOST_WIDE_INT
) val
;
842 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
844 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
845 TYPE_PRECISION (get_gcov_type ()), false));
847 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
851 fprintf (dump_file
, "Div/mod by constant ");
852 print_generic_expr (dump_file
, value
, TDF_SLIM
);
853 fprintf (dump_file
, "=");
854 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
855 fprintf (dump_file
, " transformation on insn ");
856 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
859 gimple_assign_set_rhs_from_tree (si
, result
);
860 update_stmt (gsi_stmt (*si
));
865 /* Generate code for transformation 2 (with parent gimple assign STMT and
866 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
867 within roundoff error). This generates the result into a temp and returns
868 the temp; it does not replace or alter the original STMT. */
870 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
872 gimple stmt1
, stmt2
, stmt3
, stmt4
;
874 gimple bb1end
, bb2end
, bb3end
;
875 basic_block bb
, bb2
, bb3
, bb4
;
876 tree optype
, op1
, op2
;
877 edge e12
, e13
, e23
, e24
, e34
;
878 gimple_stmt_iterator gsi
;
881 gcc_assert (is_gimple_assign (stmt
)
882 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
884 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
885 op1
= gimple_assign_rhs1 (stmt
);
886 op2
= gimple_assign_rhs2 (stmt
);
888 bb
= gimple_bb (stmt
);
889 gsi
= gsi_for_stmt (stmt
);
891 result
= create_tmp_reg (optype
, "PROF");
892 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
893 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
894 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
895 build_int_cst (optype
, -1));
896 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
897 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
898 NULL_TREE
, NULL_TREE
);
899 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
900 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
901 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
904 /* tmp2 == op2-1 inherited from previous block. */
905 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
906 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
909 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
911 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
915 /* Edge e23 connects bb2 to bb3, etc. */
916 e12
= split_block (bb
, bb1end
);
919 e23
= split_block (bb2
, bb2end
);
921 bb3
->count
= all
- count
;
922 e34
= split_block (bb3
, bb3end
);
926 e12
->flags
&= ~EDGE_FALLTHRU
;
927 e12
->flags
|= EDGE_FALSE_VALUE
;
928 e12
->probability
= prob
;
931 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
932 e13
->probability
= REG_BR_PROB_BASE
- prob
;
933 e13
->count
= all
- count
;
937 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
938 e24
->probability
= REG_BR_PROB_BASE
;
941 e34
->probability
= REG_BR_PROB_BASE
;
942 e34
->count
= all
- count
;
947 /* Do transform 2) on INSN if applicable. */
949 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
951 histogram_value histogram
;
953 gcov_type count
, wrong_values
, all
;
954 tree lhs_type
, result
, value
;
958 stmt
= gsi_stmt (*si
);
959 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
962 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
963 if (!INTEGRAL_TYPE_P (lhs_type
))
966 code
= gimple_assign_rhs_code (stmt
);
968 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
971 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
975 value
= histogram
->hvalue
.value
;
976 wrong_values
= histogram
->hvalue
.counters
[0];
977 count
= histogram
->hvalue
.counters
[1];
979 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
981 /* We require that we hit a power of 2 at least half of all evaluations. */
982 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
983 || count
< wrong_values
984 || optimize_bb_for_size_p (gimple_bb (stmt
)))
989 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
990 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
993 /* Compute probability of taking the optimal path. */
994 all
= count
+ wrong_values
;
996 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1000 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1004 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1006 gimple_assign_set_rhs_from_tree (si
, result
);
1007 update_stmt (gsi_stmt (*si
));
1012 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1013 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1014 supported and this is built into this interface. The probabilities of taking
1015 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1016 COUNT2/ALL respectively within roundoff error). This generates the
1017 result into a temp and returns the temp; it does not replace or alter
1018 the original STMT. */
1019 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1022 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
1023 gcov_type count1
, gcov_type count2
, gcov_type all
)
1025 gimple stmt1
, stmt2
, stmt3
;
1027 gimple bb1end
, bb2end
= NULL
, bb3end
;
1028 basic_block bb
, bb2
, bb3
, bb4
;
1029 tree optype
, op1
, op2
;
1030 edge e12
, e23
= 0, e24
, e34
, e14
;
1031 gimple_stmt_iterator gsi
;
1034 gcc_assert (is_gimple_assign (stmt
)
1035 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1037 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1038 op1
= gimple_assign_rhs1 (stmt
);
1039 op2
= gimple_assign_rhs2 (stmt
);
1041 bb
= gimple_bb (stmt
);
1042 gsi
= gsi_for_stmt (stmt
);
1044 result
= create_tmp_reg (optype
, "PROF");
1045 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1046 stmt1
= gimple_build_assign (result
, op1
);
1047 stmt2
= gimple_build_assign (tmp1
, op2
);
1048 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1049 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1050 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1051 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1054 if (ncounts
) /* Assumed to be 0 or 1 */
1056 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
1057 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1058 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1059 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1063 /* Fallback case. */
1064 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
1066 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1070 /* Edge e23 connects bb2 to bb3, etc. */
1071 /* However block 3 is optional; if it is not there, references
1072 to 3 really refer to block 2. */
1073 e12
= split_block (bb
, bb1end
);
1075 bb2
->count
= all
- count1
;
1077 if (ncounts
) /* Assumed to be 0 or 1. */
1079 e23
= split_block (bb2
, bb2end
);
1081 bb3
->count
= all
- count1
- count2
;
1084 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1088 e12
->flags
&= ~EDGE_FALLTHRU
;
1089 e12
->flags
|= EDGE_FALSE_VALUE
;
1090 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1091 e12
->count
= all
- count1
;
1093 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1094 e14
->probability
= prob1
;
1095 e14
->count
= count1
;
1097 if (ncounts
) /* Assumed to be 0 or 1. */
1099 e23
->flags
&= ~EDGE_FALLTHRU
;
1100 e23
->flags
|= EDGE_FALSE_VALUE
;
1101 e23
->count
= all
- count1
- count2
;
1102 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1104 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1105 e24
->probability
= prob2
;
1106 e24
->count
= count2
;
1109 e34
->probability
= REG_BR_PROB_BASE
;
1110 e34
->count
= all
- count1
- count2
;
1116 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1119 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1121 histogram_value histogram
;
1122 enum tree_code code
;
1123 gcov_type count
, wrong_values
, all
;
1124 tree lhs_type
, result
;
1125 gcov_type prob1
, prob2
;
1126 unsigned int i
, steps
;
1127 gcov_type count1
, count2
;
1130 stmt
= gsi_stmt (*si
);
1131 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1134 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1135 if (!INTEGRAL_TYPE_P (lhs_type
))
1138 code
= gimple_assign_rhs_code (stmt
);
1140 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1143 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1149 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1150 all
+= histogram
->hvalue
.counters
[i
];
1152 wrong_values
+= histogram
->hvalue
.counters
[i
];
1153 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1154 steps
= histogram
->hdata
.intvl
.steps
;
1155 all
+= wrong_values
;
1156 count1
= histogram
->hvalue
.counters
[0];
1157 count2
= histogram
->hvalue
.counters
[1];
1159 /* Compute probability of taking the optimal path. */
1160 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1162 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1166 if (flag_profile_correction
&& count1
+ count2
> all
)
1167 all
= count1
+ count2
;
1169 gcc_assert (count1
+ count2
<= all
);
1171 /* We require that we use just subtractions in at least 50% of all
1174 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1176 count
+= histogram
->hvalue
.counters
[i
];
1177 if (count
* 2 >= all
)
1181 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1184 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1187 fprintf (dump_file
, "Mod subtract transformation on insn ");
1188 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1191 /* Compute probability of taking the optimal path(s). */
1194 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1195 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1202 /* In practice, "steps" is always 2. This interface reflects this,
1203 and will need to be changed if "steps" can change. */
1204 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1206 gimple_assign_set_rhs_from_tree (si
, result
);
1207 update_stmt (gsi_stmt (*si
));
1212 static pointer_map_t
*cgraph_node_map
= 0;
1214 /* Returns true if node graph is initialized. This
1215 is used to test if profile_id has been created
1216 for cgraph_nodes. */
1219 coverage_node_map_initialized_p (void)
1221 return cgraph_node_map
!= 0;
1224 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1225 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1226 that the PROFILE_IDs was already assigned. */
1229 init_node_map (bool local
)
1231 struct cgraph_node
*n
;
1232 cgraph_node_map
= pointer_map_create ();
1234 FOR_EACH_DEFINED_FUNCTION (n
)
1235 if (n
->has_gimple_body_p ())
1240 n
->profile_id
= coverage_compute_profile_id (n
);
1241 while ((val
= pointer_map_contains (cgraph_node_map
,
1242 (void *)(size_t)n
->profile_id
))
1246 fprintf (dump_file
, "Local profile-id %i conflict"
1247 " with nodes %s/%i %s/%i\n",
1251 (*(symtab_node
**)val
)->name (),
1252 (*(symtab_node
**)val
)->order
);
1253 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1256 else if (!n
->profile_id
)
1260 "Node %s/%i has no profile-id"
1261 " (profile feedback missing?)\n",
1266 else if ((val
= pointer_map_contains (cgraph_node_map
,
1267 (void *)(size_t)n
->profile_id
)))
1271 "Node %s/%i has IP profile-id %i conflict. "
1279 *pointer_map_insert (cgraph_node_map
,
1280 (void *)(size_t)n
->profile_id
) = (void *)n
;
1284 /* Delete the CGRAPH_NODE_MAP. */
1289 pointer_map_destroy (cgraph_node_map
);
1292 /* Return cgraph node for function with pid */
1295 find_func_by_profile_id (int profile_id
)
1297 void **val
= pointer_map_contains (cgraph_node_map
,
1298 (void *)(size_t)profile_id
);
1300 return (struct cgraph_node
*)*val
;
1305 /* Perform sanity check on the indirect call target. Due to race conditions,
1306 false function target may be attributed to an indirect call site. If the
1307 call expression type mismatches with the target function's type, expand_call
1308 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1309 Returns true if TARGET is considered ok for call CALL_STMT. */
1312 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1315 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1318 locus
= gimple_location (call_stmt
);
1319 if (dump_enabled_p ())
1320 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1321 "Skipping target %s with mismatching types for icall\n",
1326 /* Do transformation
1328 if (actual_callee_address == address_of_most_common_function/method)
1335 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1336 int prob
, gcov_type count
, gcov_type all
)
1338 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1339 tree tmp0
, tmp1
, tmp
;
1340 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1341 tree optype
= build_pointer_type (void_type_node
);
1342 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1343 gimple_stmt_iterator gsi
;
1347 gimple_stmt_iterator psi
;
1349 cond_bb
= gimple_bb (icall_stmt
);
1350 gsi
= gsi_for_stmt (icall_stmt
);
1352 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1353 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1354 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1355 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1356 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1358 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1359 current_function_decl
));
1360 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1361 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1363 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1364 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1366 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1367 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1368 update_stmt (icall_stmt
);
1369 dcall_stmt
= gimple_copy (icall_stmt
);
1370 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1371 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1372 if ((dflags
& ECF_NORETURN
) != 0)
1373 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1374 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1377 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1378 e_cd
= split_block (cond_bb
, cond_stmt
);
1379 dcall_bb
= e_cd
->dest
;
1380 dcall_bb
->count
= count
;
1382 e_di
= split_block (dcall_bb
, dcall_stmt
);
1383 icall_bb
= e_di
->dest
;
1384 icall_bb
->count
= all
- count
;
1386 /* Do not disturb existing EH edges from the indirect call. */
1387 if (!stmt_ends_bb_p (icall_stmt
))
1388 e_ij
= split_block (icall_bb
, icall_stmt
);
1391 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1392 /* The indirect call might be noreturn. */
1395 e_ij
->probability
= REG_BR_PROB_BASE
;
1396 e_ij
->count
= all
- count
;
1397 e_ij
= single_pred_edge (split_edge (e_ij
));
1402 join_bb
= e_ij
->dest
;
1403 join_bb
->count
= all
;
1406 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1407 e_cd
->probability
= prob
;
1408 e_cd
->count
= count
;
1410 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1411 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1412 e_ci
->count
= all
- count
;
1418 if ((dflags
& ECF_NORETURN
) != 0)
1422 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1423 e_dj
->probability
= REG_BR_PROB_BASE
;
1424 e_dj
->count
= count
;
1426 e_ij
->count
= all
- count
;
1428 e_ij
->probability
= REG_BR_PROB_BASE
;
1431 /* Insert PHI node for the call result if necessary. */
1432 if (gimple_call_lhs (icall_stmt
)
1433 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1434 && (dflags
& ECF_NORETURN
) == 0)
1436 tree result
= gimple_call_lhs (icall_stmt
);
1437 gimple phi
= create_phi_node (result
, join_bb
);
1438 gimple_call_set_lhs (icall_stmt
,
1439 duplicate_ssa_name (result
, icall_stmt
));
1440 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1441 gimple_call_set_lhs (dcall_stmt
,
1442 duplicate_ssa_name (result
, dcall_stmt
));
1443 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1446 /* Build an EH edge for the direct call if necessary. */
1447 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1448 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1450 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1453 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1454 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1456 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1457 for (psi
= gsi_start_phis (e_eh
->dest
);
1458 !gsi_end_p (psi
); gsi_next (&psi
))
1460 gimple phi
= gsi_stmt (psi
);
1461 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1462 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1469 For every checked indirect/virtual call determine if most common pid of
1470 function/class method has probability more than 50%. If yes modify code of
1475 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1477 gimple stmt
= gsi_stmt (*gsi
);
1478 histogram_value histogram
;
1479 gcov_type val
, count
, all
, bb_all
;
1480 struct cgraph_node
*direct_call
;
1482 if (gimple_code (stmt
) != GIMPLE_CALL
)
1485 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1488 if (gimple_call_internal_p (stmt
))
1491 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1495 val
= histogram
->hvalue
.counters
[0];
1496 count
= histogram
->hvalue
.counters
[1];
1497 all
= histogram
->hvalue
.counters
[2];
1499 bb_all
= gimple_bb (stmt
)->count
;
1500 /* The order of CHECK_COUNTER calls is important -
1501 since check_counter can correct the third parameter
1502 and we want to make count <= all <= bb_all. */
1503 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1504 || check_counter (stmt
, "ic", &count
, &all
, all
))
1506 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1510 if (4 * count
<= 3 * all
)
1513 direct_call
= find_func_by_profile_id ((int)val
);
1515 if (direct_call
== NULL
)
1521 fprintf (dump_file
, "Indirect call -> direct call from other module");
1522 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1523 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1529 if (!check_ic_target (stmt
, direct_call
))
1533 fprintf (dump_file
, "Indirect call -> direct call ");
1534 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1535 fprintf (dump_file
, "=> ");
1536 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1537 fprintf (dump_file
, " transformation skipped because of type mismatch");
1538 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1540 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1546 fprintf (dump_file
, "Indirect call -> direct call ");
1547 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1548 fprintf (dump_file
, "=> ");
1549 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1550 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1551 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1552 fprintf (dump_file
, "hist->count %"PRId64
1553 " hist->all %"PRId64
"\n", count
, all
);
1559 /* Return true if the stringop CALL with FNDECL shall be profiled.
1560 SIZE_ARG be set to the argument index for the size of the string
1564 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1566 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1568 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1569 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1574 case BUILT_IN_MEMCPY
:
1575 case BUILT_IN_MEMPCPY
:
1577 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1578 INTEGER_TYPE
, VOID_TYPE
);
1579 case BUILT_IN_MEMSET
:
1581 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1582 INTEGER_TYPE
, VOID_TYPE
);
1583 case BUILT_IN_BZERO
:
1585 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1592 /* Convert stringop (..., vcall_size)
1594 if (vcall_size == icall_size)
1595 stringop (..., icall_size);
1597 stringop (..., vcall_size);
1598 assuming we'll propagate a true constant into ICALL_SIZE later. */
1601 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1602 gcov_type count
, gcov_type all
)
1604 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1605 tree tmp0
, tmp1
, vcall_size
, optype
;
1606 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1607 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1608 gimple_stmt_iterator gsi
;
1612 fndecl
= gimple_call_fndecl (vcall_stmt
);
1613 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1616 cond_bb
= gimple_bb (vcall_stmt
);
1617 gsi
= gsi_for_stmt (vcall_stmt
);
1619 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1620 optype
= TREE_TYPE (vcall_size
);
1622 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1623 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1624 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1625 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1627 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1628 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1630 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1631 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1633 gimple_set_vdef (vcall_stmt
, NULL
);
1634 gimple_set_vuse (vcall_stmt
, NULL
);
1635 update_stmt (vcall_stmt
);
1636 icall_stmt
= gimple_copy (vcall_stmt
);
1637 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1638 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1641 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1642 e_ci
= split_block (cond_bb
, cond_stmt
);
1643 icall_bb
= e_ci
->dest
;
1644 icall_bb
->count
= count
;
1646 e_iv
= split_block (icall_bb
, icall_stmt
);
1647 vcall_bb
= e_iv
->dest
;
1648 vcall_bb
->count
= all
- count
;
1650 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1651 join_bb
= e_vj
->dest
;
1652 join_bb
->count
= all
;
1654 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1655 e_ci
->probability
= prob
;
1656 e_ci
->count
= count
;
1658 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1659 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1660 e_cv
->count
= all
- count
;
1664 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1665 e_ij
->probability
= REG_BR_PROB_BASE
;
1666 e_ij
->count
= count
;
1668 e_vj
->probability
= REG_BR_PROB_BASE
;
1669 e_vj
->count
= all
- count
;
1671 /* Insert PHI node for the call result if necessary. */
1672 if (gimple_call_lhs (vcall_stmt
)
1673 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1675 tree result
= gimple_call_lhs (vcall_stmt
);
1676 gimple phi
= create_phi_node (result
, join_bb
);
1677 gimple_call_set_lhs (vcall_stmt
,
1678 duplicate_ssa_name (result
, vcall_stmt
));
1679 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1680 gimple_call_set_lhs (icall_stmt
,
1681 duplicate_ssa_name (result
, icall_stmt
));
1682 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1685 /* Because these are all string op builtins, they're all nothrow. */
1686 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1687 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1690 /* Find values inside STMT for that we want to measure histograms for
1691 division/modulo optimization. */
1693 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1695 gimple stmt
= gsi_stmt (*gsi
);
1698 enum built_in_function fcode
;
1699 histogram_value histogram
;
1700 gcov_type count
, all
, val
;
1702 unsigned int dest_align
, src_align
;
1707 if (gimple_code (stmt
) != GIMPLE_CALL
)
1709 fndecl
= gimple_call_fndecl (stmt
);
1712 fcode
= DECL_FUNCTION_CODE (fndecl
);
1713 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1716 blck_size
= gimple_call_arg (stmt
, size_arg
);
1717 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1720 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1723 val
= histogram
->hvalue
.counters
[0];
1724 count
= histogram
->hvalue
.counters
[1];
1725 all
= histogram
->hvalue
.counters
[2];
1726 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1727 /* We require that count is at least half of all; this means
1728 that for the transformation to fire the value must be constant
1729 at least 80% of time. */
1730 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1732 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1735 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1738 dest
= gimple_call_arg (stmt
, 0);
1739 dest_align
= get_pointer_alignment (dest
);
1742 case BUILT_IN_MEMCPY
:
1743 case BUILT_IN_MEMPCPY
:
1744 src
= gimple_call_arg (stmt
, 1);
1745 src_align
= get_pointer_alignment (src
);
1746 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1749 case BUILT_IN_MEMSET
:
1750 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1751 gimple_call_arg (stmt
, 1),
1755 case BUILT_IN_BZERO
:
1756 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1764 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1765 tree_val
= build_int_cst (get_gcov_type (), val
);
1769 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1770 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1772 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1773 TYPE_PRECISION (get_gcov_type ()), false));
1778 fprintf (dump_file
, "Single value %i stringop transformation on ",
1780 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1782 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1788 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1789 HOST_WIDE_INT
*expected_size
)
1791 histogram_value histogram
;
1792 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1794 *expected_size
= -1;
1795 else if (!histogram
->hvalue
.counters
[1])
1797 *expected_size
= -1;
1798 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1803 size
= ((histogram
->hvalue
.counters
[0]
1804 + histogram
->hvalue
.counters
[1] / 2)
1805 / histogram
->hvalue
.counters
[1]);
1806 /* Even if we can hold bigger value in SIZE, INT_MAX
1807 is safe "infinity" for code generation strategies. */
1810 *expected_size
= size
;
1811 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1813 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1815 *expected_align
= 0;
1816 else if (!histogram
->hvalue
.counters
[0])
1818 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1819 *expected_align
= 0;
1826 count
= histogram
->hvalue
.counters
[0];
1828 while (!(count
& alignment
)
1829 && (alignment
* 2 * BITS_PER_UNIT
))
1831 *expected_align
= alignment
* BITS_PER_UNIT
;
1832 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1837 /* Find values inside STMT for that we want to measure histograms for
1838 division/modulo optimization. */
1840 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1842 tree lhs
, divisor
, op0
, type
;
1843 histogram_value hist
;
1845 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1848 lhs
= gimple_assign_lhs (stmt
);
1849 type
= TREE_TYPE (lhs
);
1850 if (!INTEGRAL_TYPE_P (type
))
1853 switch (gimple_assign_rhs_code (stmt
))
1855 case TRUNC_DIV_EXPR
:
1856 case TRUNC_MOD_EXPR
:
1857 divisor
= gimple_assign_rhs2 (stmt
);
1858 op0
= gimple_assign_rhs1 (stmt
);
1860 values
->reserve (3);
1862 if (TREE_CODE (divisor
) == SSA_NAME
)
1863 /* Check for the case where the divisor is the same value most
1865 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1866 HIST_TYPE_SINGLE_VALUE
,
1869 /* For mod, check whether it is not often a noop (or replaceable by
1870 a few subtractions). */
1871 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1872 && TYPE_UNSIGNED (type
))
1875 /* Check for a special case where the divisor is power of 2. */
1876 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1880 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1881 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1883 hist
->hdata
.intvl
.int_start
= 0;
1884 hist
->hdata
.intvl
.steps
= 2;
1885 values
->quick_push (hist
);
1894 /* Find calls inside STMT for that we want to measure histograms for
1895 indirect/virtual call optimization. */
1898 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1902 if (gimple_code (stmt
) != GIMPLE_CALL
1903 || gimple_call_internal_p (stmt
)
1904 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1907 callee
= gimple_call_fn (stmt
);
1909 values
->reserve (3);
1911 values
->quick_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1917 /* Find values inside STMT for that we want to measure histograms for
1918 string operations. */
1920 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1927 if (gimple_code (stmt
) != GIMPLE_CALL
)
1929 fndecl
= gimple_call_fndecl (stmt
);
1933 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1936 dest
= gimple_call_arg (stmt
, 0);
1937 blck_size
= gimple_call_arg (stmt
, size_arg
);
1939 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1941 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1942 HIST_TYPE_SINGLE_VALUE
,
1944 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1947 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1948 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1952 /* Find values inside STMT for that we want to measure histograms and adds
1953 them to list VALUES. */
1956 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1958 gimple_divmod_values_to_profile (stmt
, values
);
1959 gimple_stringops_values_to_profile (stmt
, values
);
1960 gimple_indirect_call_to_profile (stmt
, values
);
1964 gimple_find_values_to_profile (histogram_values
*values
)
1967 gimple_stmt_iterator gsi
;
1969 histogram_value hist
= NULL
;
1972 FOR_EACH_BB_FN (bb
, cfun
)
1973 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1974 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1976 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
1978 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1982 case HIST_TYPE_INTERVAL
:
1983 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1986 case HIST_TYPE_POW2
:
1987 hist
->n_counters
= 2;
1990 case HIST_TYPE_SINGLE_VALUE
:
1991 hist
->n_counters
= 3;
1994 case HIST_TYPE_CONST_DELTA
:
1995 hist
->n_counters
= 4;
1998 case HIST_TYPE_INDIR_CALL
:
1999 hist
->n_counters
= 3;
2002 case HIST_TYPE_TIME_PROFILE
:
2003 hist
->n_counters
= 1;
2006 case HIST_TYPE_AVERAGE
:
2007 hist
->n_counters
= 2;
2011 hist
->n_counters
= 1;
2019 fprintf (dump_file
, "Stmt ");
2020 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2021 dump_histogram_value (dump_file
, hist
);