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"
65 /* In this file value profile based optimizations are placed. Currently the
66 following optimizations are implemented (for more detailed descriptions
67 see comments at value_profile_transformations):
69 1) Division/modulo specialization. Provided that we can determine that the
70 operands of the division have some special properties, we may use it to
71 produce more effective code.
73 2) Indirect/virtual call specialization. If we can determine most
74 common function callee in indirect/virtual call. We can use this
75 information to improve code effectiveness (especially info for
78 3) Speculative prefetching. If we are able to determine that the difference
79 between addresses accessed by a memory reference is usually constant, we
80 may add the prefetch instructions.
81 FIXME: This transformation was removed together with RTL based value
85 Value profiling internals
86 ==========================
88 Every value profiling transformation starts with defining what values
89 to profile. There are different histogram types (see HIST_TYPE_* in
90 value-prof.h) and each transformation can request one or more histogram
91 types per GIMPLE statement. The function gimple_find_values_to_profile()
92 collects the values to profile in a vec, and adds the number of counters
93 required for the different histogram types.
95 For a -fprofile-generate run, the statements for which values should be
96 recorded, are instrumented in instrument_values(). The instrumentation
97 is done by helper functions that can be found in tree-profile.c, where
98 new types of histograms can be added if necessary.
100 After a -fprofile-use, the value profiling data is read back in by
101 compute_value_histograms() that translates the collected data to
102 histograms and attaches them to the profiled statements via
103 gimple_add_histogram_value(). Histograms are stored in a hash table
104 that is attached to every intrumented function, see VALUE_HISTOGRAMS
107 The value-profile transformations driver is the function
108 gimple_value_profile_transformations(). It traverses all statements in
109 the to-be-transformed function, and looks for statements with one or
110 more histograms attached to it. If a statement has histograms, the
111 transformation functions are called on the statement.
113 Limitations / FIXME / TODO:
114 * Only one histogram of each type can be associated with a statement.
115 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
116 (This type of histogram was originally used to implement a form of
117 stride profiling based speculative prefetching to improve SPEC2000
118 scores for memory-bound benchmarks, mcf and equake. However, this
119 was an RTL value-profiling transformation, and those have all been
121 * Some value profile transformations are done in builtins.c (?!)
122 * Updating of histograms needs some TLC.
123 * The value profiling code could be used to record analysis results
124 from non-profiling (e.g. VRP).
125 * Adding new profilers should be simplified, starting with a cleanup
126 of what-happens-where andwith making gimple_find_values_to_profile
127 and gimple_value_profile_transformations table-driven, perhaps...
130 static tree
gimple_divmod_fixed_value (gassign
*, tree
, int, gcov_type
,
132 static tree
gimple_mod_pow2 (gassign
*, int, gcov_type
, gcov_type
);
133 static tree
gimple_mod_subtract (gassign
*, int, int, int, gcov_type
,
134 gcov_type
, gcov_type
);
135 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
136 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
137 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
138 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
139 static bool gimple_ic_transform (gimple_stmt_iterator
*);
141 /* Allocate histogram value. */
143 static histogram_value
144 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
145 enum hist_type type
, gimple stmt
, tree value
)
147 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
148 hist
->hvalue
.value
= value
;
149 hist
->hvalue
.stmt
= stmt
;
154 /* Hash value for histogram. */
157 histogram_hash (const void *x
)
159 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
162 /* Return nonzero if statement for histogram_value X is Y. */
165 histogram_eq (const void *x
, const void *y
)
167 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
170 /* Set histogram for STMT. */
173 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
176 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
178 if (!VALUE_HISTOGRAMS (fun
))
179 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
181 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
182 htab_hash_pointer (stmt
),
183 hist
? INSERT
: NO_INSERT
);
187 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
193 /* Get histogram list for STMT. */
196 gimple_histogram_value (struct function
*fun
, gimple stmt
)
198 if (!VALUE_HISTOGRAMS (fun
))
200 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
201 htab_hash_pointer (stmt
));
204 /* Add histogram for STMT. */
207 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
208 histogram_value hist
)
210 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
211 set_histogram_value (fun
, stmt
, hist
);
216 /* Remove histogram HIST from STMT's histogram list. */
219 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
220 histogram_value hist
)
222 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
225 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
229 while (hist2
->hvalue
.next
!= hist
)
230 hist2
= hist2
->hvalue
.next
;
231 hist2
->hvalue
.next
= hist
->hvalue
.next
;
233 free (hist
->hvalue
.counters
);
234 #ifdef ENABLE_CHECKING
235 memset (hist
, 0xab, sizeof (*hist
));
241 /* Lookup histogram of type TYPE in the STMT. */
244 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
247 histogram_value hist
;
248 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
249 hist
= hist
->hvalue
.next
)
250 if (hist
->type
== type
)
255 /* Dump information about HIST to DUMP_FILE. */
258 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
262 case HIST_TYPE_INTERVAL
:
263 fprintf (dump_file
, "Interval counter range %d -- %d",
264 hist
->hdata
.intvl
.int_start
,
265 (hist
->hdata
.intvl
.int_start
266 + hist
->hdata
.intvl
.steps
- 1));
267 if (hist
->hvalue
.counters
)
270 fprintf (dump_file
, " [");
271 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
272 fprintf (dump_file
, " %d:%"PRId64
,
273 hist
->hdata
.intvl
.int_start
+ i
,
274 (int64_t) hist
->hvalue
.counters
[i
]);
275 fprintf (dump_file
, " ] outside range:%"PRId64
,
276 (int64_t) hist
->hvalue
.counters
[i
]);
278 fprintf (dump_file
, ".\n");
282 fprintf (dump_file
, "Pow2 counter ");
283 if (hist
->hvalue
.counters
)
285 fprintf (dump_file
, "pow2:%"PRId64
287 (int64_t) hist
->hvalue
.counters
[0],
288 (int64_t) hist
->hvalue
.counters
[1]);
290 fprintf (dump_file
, ".\n");
293 case HIST_TYPE_SINGLE_VALUE
:
294 fprintf (dump_file
, "Single value ");
295 if (hist
->hvalue
.counters
)
297 fprintf (dump_file
, "value:%"PRId64
300 (int64_t) hist
->hvalue
.counters
[0],
301 (int64_t) hist
->hvalue
.counters
[1],
302 (int64_t) hist
->hvalue
.counters
[2]);
304 fprintf (dump_file
, ".\n");
307 case HIST_TYPE_AVERAGE
:
308 fprintf (dump_file
, "Average value ");
309 if (hist
->hvalue
.counters
)
311 fprintf (dump_file
, "sum:%"PRId64
313 (int64_t) hist
->hvalue
.counters
[0],
314 (int64_t) hist
->hvalue
.counters
[1]);
316 fprintf (dump_file
, ".\n");
320 fprintf (dump_file
, "IOR value ");
321 if (hist
->hvalue
.counters
)
323 fprintf (dump_file
, "ior:%"PRId64
,
324 (int64_t) hist
->hvalue
.counters
[0]);
326 fprintf (dump_file
, ".\n");
329 case HIST_TYPE_CONST_DELTA
:
330 fprintf (dump_file
, "Constant delta ");
331 if (hist
->hvalue
.counters
)
333 fprintf (dump_file
, "value:%"PRId64
336 (int64_t) hist
->hvalue
.counters
[0],
337 (int64_t) hist
->hvalue
.counters
[1],
338 (int64_t) hist
->hvalue
.counters
[2]);
340 fprintf (dump_file
, ".\n");
342 case HIST_TYPE_INDIR_CALL
:
343 fprintf (dump_file
, "Indirect call ");
344 if (hist
->hvalue
.counters
)
346 fprintf (dump_file
, "value:%"PRId64
349 (int64_t) hist
->hvalue
.counters
[0],
350 (int64_t) hist
->hvalue
.counters
[1],
351 (int64_t) hist
->hvalue
.counters
[2]);
353 fprintf (dump_file
, ".\n");
355 case HIST_TYPE_TIME_PROFILE
:
356 fprintf (dump_file
, "Time profile ");
357 if (hist
->hvalue
.counters
)
359 fprintf (dump_file
, "time:%"PRId64
,
360 (int64_t) hist
->hvalue
.counters
[0]);
362 fprintf (dump_file
, ".\n");
364 case HIST_TYPE_INDIR_CALL_TOPN
:
365 fprintf (dump_file
, "Indirect call topn ");
366 if (hist
->hvalue
.counters
)
370 fprintf (dump_file
, "accu:%"PRId64
, hist
->hvalue
.counters
[0]);
371 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
373 fprintf (dump_file
, " target:%"PRId64
" value:%"PRId64
,
374 (int64_t) hist
->hvalue
.counters
[i
],
375 (int64_t) hist
->hvalue
.counters
[i
+1]);
378 fprintf (dump_file
, ".\n");
385 /* Dump information about HIST to DUMP_FILE. */
388 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
393 bp
= bitpack_create (ob
->main_stream
);
394 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
395 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
396 streamer_write_bitpack (&bp
);
399 case HIST_TYPE_INTERVAL
:
400 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
401 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
406 for (i
= 0; i
< hist
->n_counters
; i
++)
407 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
408 if (hist
->hvalue
.next
)
409 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
411 /* Dump information about HIST to DUMP_FILE. */
414 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
417 unsigned int ncounters
= 0;
420 histogram_value new_val
;
422 histogram_value
*next_p
= NULL
;
426 bp
= streamer_read_bitpack (ib
);
427 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
428 next
= bp_unpack_value (&bp
, 1);
429 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
432 case HIST_TYPE_INTERVAL
:
433 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
434 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
435 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
439 case HIST_TYPE_AVERAGE
:
443 case HIST_TYPE_SINGLE_VALUE
:
444 case HIST_TYPE_INDIR_CALL
:
448 case HIST_TYPE_CONST_DELTA
:
453 case HIST_TYPE_TIME_PROFILE
:
457 case HIST_TYPE_INDIR_CALL_TOPN
:
458 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
464 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
465 new_val
->n_counters
= ncounters
;
466 for (i
= 0; i
< ncounters
; i
++)
467 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
469 gimple_add_histogram_value (cfun
, stmt
, new_val
);
472 next_p
= &new_val
->hvalue
.next
;
477 /* Dump all histograms attached to STMT to DUMP_FILE. */
480 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
482 histogram_value hist
;
483 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
484 dump_histogram_value (dump_file
, hist
);
487 /* Remove all histograms associated with STMT. */
490 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
493 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
494 gimple_remove_histogram_value (fun
, stmt
, val
);
497 /* Duplicate all histograms associates with OSTMT to STMT. */
500 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
501 struct function
*ofun
, gimple ostmt
)
504 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
506 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
507 memcpy (new_val
, val
, sizeof (*val
));
508 new_val
->hvalue
.stmt
= stmt
;
509 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
510 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
511 gimple_add_histogram_value (fun
, stmt
, new_val
);
516 /* Move all histograms associated with OSTMT to STMT. */
519 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
521 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
524 /* The following three statements can't be reordered,
525 because histogram hashtab relies on stmt field value
526 for finding the exact slot. */
527 set_histogram_value (fun
, ostmt
, NULL
);
528 for (; val
!= NULL
; val
= val
->hvalue
.next
)
529 val
->hvalue
.stmt
= stmt
;
530 set_histogram_value (fun
, stmt
, val
);
534 static bool error_found
= false;
536 /* Helper function for verify_histograms. For each histogram reachable via htab
537 walk verify that it was reached via statement walk. */
540 visit_hist (void **slot
, void *data
)
542 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
543 histogram_value hist
= *(histogram_value
*) slot
;
545 if (!visited
->contains (hist
)
546 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
548 error ("dead histogram");
549 dump_histogram_value (stderr
, hist
);
550 debug_gimple_stmt (hist
->hvalue
.stmt
);
557 /* Verify sanity of the histograms. */
560 verify_histograms (void)
563 gimple_stmt_iterator gsi
;
564 histogram_value hist
;
567 hash_set
<histogram_value
> visited_hists
;
568 FOR_EACH_BB_FN (bb
, cfun
)
569 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
571 gimple stmt
= gsi_stmt (gsi
);
573 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
574 hist
= hist
->hvalue
.next
)
576 if (hist
->hvalue
.stmt
!= stmt
)
578 error ("Histogram value statement does not correspond to "
579 "the statement it is associated with");
580 debug_gimple_stmt (stmt
);
581 dump_histogram_value (stderr
, hist
);
584 visited_hists
.add (hist
);
587 if (VALUE_HISTOGRAMS (cfun
))
588 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
590 internal_error ("verify_histograms failed");
593 /* Helper function for verify_histograms. For each histogram reachable via htab
594 walk verify that it was reached via statement walk. */
597 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
599 histogram_value hist
= *(histogram_value
*) slot
;
600 free (hist
->hvalue
.counters
);
601 #ifdef ENABLE_CHECKING
602 memset (hist
, 0xab, sizeof (*hist
));
609 free_histograms (void)
611 if (VALUE_HISTOGRAMS (cfun
))
613 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
614 htab_delete (VALUE_HISTOGRAMS (cfun
));
615 VALUE_HISTOGRAMS (cfun
) = NULL
;
620 /* The overall number of invocations of the counter should match
621 execution count of basic block. Report it as error rather than
622 internal error as it might mean that user has misused the profile
626 check_counter (gimple stmt
, const char * name
,
627 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
629 if (*all
!= bb_count
|| *count
> *all
)
632 locus
= (stmt
!= NULL
)
633 ? gimple_location (stmt
)
634 : DECL_SOURCE_LOCATION (current_function_decl
);
635 if (flag_profile_correction
)
637 if (dump_enabled_p ())
638 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
639 "correcting inconsistent value profile: %s "
640 "profiler overall count (%d) does not match BB "
641 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
649 error_at (locus
, "corrupted value profile: %s "
650 "profile counter (%d out of %d) inconsistent with "
651 "basic-block count (%d)",
664 /* GIMPLE based transformations. */
667 gimple_value_profile_transformations (void)
670 gimple_stmt_iterator gsi
;
671 bool changed
= false;
673 FOR_EACH_BB_FN (bb
, cfun
)
675 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
677 gimple stmt
= gsi_stmt (gsi
);
678 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
684 fprintf (dump_file
, "Trying transformations on stmt ");
685 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
686 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
689 /* Transformations: */
690 /* The order of things in this conditional controls which
691 transformation is used when more than one is applicable. */
692 /* It is expected that any code added by the transformations
693 will be added before the current statement, and that the
694 current statement remain valid (although possibly
695 modified) upon return. */
696 if (gimple_mod_subtract_transform (&gsi
)
697 || gimple_divmod_fixed_value_transform (&gsi
)
698 || gimple_mod_pow2_value_transform (&gsi
)
699 || gimple_stringops_transform (&gsi
)
700 || gimple_ic_transform (&gsi
))
702 stmt
= gsi_stmt (gsi
);
704 /* Original statement may no longer be in the same block. */
705 if (bb
!= gimple_bb (stmt
))
707 bb
= gimple_bb (stmt
);
708 gsi
= gsi_for_stmt (stmt
);
723 /* Generate code for transformation 1 (with parent gimple assignment
724 STMT and probability of taking the optimal path PROB, which is
725 equivalent to COUNT/ALL within roundoff error). This generates the
726 result into a temp and returns the temp; it does not replace or
727 alter the original STMT. */
730 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, int prob
,
731 gcov_type count
, gcov_type all
)
733 gassign
*stmt1
, *stmt2
;
735 tree tmp0
, tmp1
, tmp2
;
736 gimple bb1end
, bb2end
, bb3end
;
737 basic_block bb
, bb2
, bb3
, bb4
;
738 tree optype
, op1
, op2
;
739 edge e12
, e13
, e23
, e24
, e34
;
740 gimple_stmt_iterator gsi
;
742 gcc_assert (is_gimple_assign (stmt
)
743 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
744 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
746 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
747 op1
= gimple_assign_rhs1 (stmt
);
748 op2
= gimple_assign_rhs2 (stmt
);
750 bb
= gimple_bb (stmt
);
751 gsi
= gsi_for_stmt (stmt
);
753 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
754 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
755 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
756 stmt2
= gimple_build_assign (tmp1
, op2
);
757 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
758 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
759 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
760 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
763 tmp2
= create_tmp_reg (optype
, "PROF");
764 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
766 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
769 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
771 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
775 /* Edge e23 connects bb2 to bb3, etc. */
776 e12
= split_block (bb
, bb1end
);
779 e23
= split_block (bb2
, bb2end
);
781 bb3
->count
= all
- count
;
782 e34
= split_block (bb3
, bb3end
);
786 e12
->flags
&= ~EDGE_FALLTHRU
;
787 e12
->flags
|= EDGE_FALSE_VALUE
;
788 e12
->probability
= prob
;
791 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
792 e13
->probability
= REG_BR_PROB_BASE
- prob
;
793 e13
->count
= all
- count
;
797 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
798 e24
->probability
= REG_BR_PROB_BASE
;
801 e34
->probability
= REG_BR_PROB_BASE
;
802 e34
->count
= all
- count
;
808 /* Do transform 1) on INSN if applicable. */
811 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
813 histogram_value histogram
;
815 gcov_type val
, count
, all
;
816 tree result
, value
, tree_val
;
820 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
824 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
827 code
= gimple_assign_rhs_code (stmt
);
829 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
832 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
833 HIST_TYPE_SINGLE_VALUE
);
837 value
= histogram
->hvalue
.value
;
838 val
= histogram
->hvalue
.counters
[0];
839 count
= histogram
->hvalue
.counters
[1];
840 all
= histogram
->hvalue
.counters
[2];
841 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
843 /* We require that count is at least half of all; this means
844 that for the transformation to fire the value must be constant
845 at least 50% of time (and 75% gives the guarantee of usage). */
846 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
848 || optimize_bb_for_size_p (gimple_bb (stmt
)))
851 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
854 /* Compute probability of taking the optimal path. */
856 prob
= GCOV_COMPUTE_SCALE (count
, all
);
860 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
861 tree_val
= build_int_cst (get_gcov_type (), val
);
865 a
[0] = (unsigned HOST_WIDE_INT
) val
;
866 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
868 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
869 TYPE_PRECISION (get_gcov_type ()), false));
871 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
875 fprintf (dump_file
, "Div/mod by constant ");
876 print_generic_expr (dump_file
, value
, TDF_SLIM
);
877 fprintf (dump_file
, "=");
878 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
879 fprintf (dump_file
, " transformation on insn ");
880 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
883 gimple_assign_set_rhs_from_tree (si
, result
);
884 update_stmt (gsi_stmt (*si
));
889 /* Generate code for transformation 2 (with parent gimple assign STMT and
890 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
891 within roundoff error). This generates the result into a temp and returns
892 the temp; it does not replace or alter the original STMT. */
894 gimple_mod_pow2 (gassign
*stmt
, int prob
, gcov_type count
, gcov_type all
)
896 gassign
*stmt1
, *stmt2
, *stmt3
;
899 gimple bb1end
, bb2end
, bb3end
;
900 basic_block bb
, bb2
, bb3
, bb4
;
901 tree optype
, op1
, op2
;
902 edge e12
, e13
, e23
, e24
, e34
;
903 gimple_stmt_iterator gsi
;
906 gcc_assert (is_gimple_assign (stmt
)
907 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
909 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
910 op1
= gimple_assign_rhs1 (stmt
);
911 op2
= gimple_assign_rhs2 (stmt
);
913 bb
= gimple_bb (stmt
);
914 gsi
= gsi_for_stmt (stmt
);
916 result
= create_tmp_reg (optype
, "PROF");
917 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
918 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
919 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
920 build_int_cst (optype
, -1));
921 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
922 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
923 NULL_TREE
, NULL_TREE
);
924 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
925 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
926 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
929 /* tmp2 == op2-1 inherited from previous block. */
930 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
931 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
934 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
936 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
940 /* Edge e23 connects bb2 to bb3, etc. */
941 e12
= split_block (bb
, bb1end
);
944 e23
= split_block (bb2
, bb2end
);
946 bb3
->count
= all
- count
;
947 e34
= split_block (bb3
, bb3end
);
951 e12
->flags
&= ~EDGE_FALLTHRU
;
952 e12
->flags
|= EDGE_FALSE_VALUE
;
953 e12
->probability
= prob
;
956 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
957 e13
->probability
= REG_BR_PROB_BASE
- prob
;
958 e13
->count
= all
- count
;
962 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
963 e24
->probability
= REG_BR_PROB_BASE
;
966 e34
->probability
= REG_BR_PROB_BASE
;
967 e34
->count
= all
- count
;
972 /* Do transform 2) on INSN if applicable. */
974 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
976 histogram_value histogram
;
978 gcov_type count
, wrong_values
, all
;
979 tree lhs_type
, result
, value
;
983 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
987 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
988 if (!INTEGRAL_TYPE_P (lhs_type
))
991 code
= gimple_assign_rhs_code (stmt
);
993 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
996 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
1000 value
= histogram
->hvalue
.value
;
1001 wrong_values
= histogram
->hvalue
.counters
[0];
1002 count
= histogram
->hvalue
.counters
[1];
1004 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1006 /* We require that we hit a power of 2 at least half of all evaluations. */
1007 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
1008 || count
< wrong_values
1009 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1014 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
1015 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1018 /* Compute probability of taking the optimal path. */
1019 all
= count
+ wrong_values
;
1021 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1025 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1029 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1031 gimple_assign_set_rhs_from_tree (si
, result
);
1032 update_stmt (gsi_stmt (*si
));
1037 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1038 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1039 supported and this is built into this interface. The probabilities of taking
1040 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1041 COUNT2/ALL respectively within roundoff error). This generates the
1042 result into a temp and returns the temp; it does not replace or alter
1043 the original STMT. */
1044 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1047 gimple_mod_subtract (gassign
*stmt
, int prob1
, int prob2
, int ncounts
,
1048 gcov_type count1
, gcov_type count2
, gcov_type all
)
1054 gimple bb1end
, bb2end
= NULL
, bb3end
;
1055 basic_block bb
, bb2
, bb3
, bb4
;
1056 tree optype
, op1
, op2
;
1057 edge e12
, e23
= 0, e24
, e34
, e14
;
1058 gimple_stmt_iterator gsi
;
1061 gcc_assert (is_gimple_assign (stmt
)
1062 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1064 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1065 op1
= gimple_assign_rhs1 (stmt
);
1066 op2
= gimple_assign_rhs2 (stmt
);
1068 bb
= gimple_bb (stmt
);
1069 gsi
= gsi_for_stmt (stmt
);
1071 result
= create_tmp_reg (optype
, "PROF");
1072 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1073 stmt1
= gimple_build_assign (result
, op1
);
1074 stmt2
= gimple_build_assign (tmp1
, op2
);
1075 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1076 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1077 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1078 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1081 if (ncounts
) /* Assumed to be 0 or 1 */
1083 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
1084 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1085 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1086 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1090 /* Fallback case. */
1091 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
1093 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1097 /* Edge e23 connects bb2 to bb3, etc. */
1098 /* However block 3 is optional; if it is not there, references
1099 to 3 really refer to block 2. */
1100 e12
= split_block (bb
, bb1end
);
1102 bb2
->count
= all
- count1
;
1104 if (ncounts
) /* Assumed to be 0 or 1. */
1106 e23
= split_block (bb2
, bb2end
);
1108 bb3
->count
= all
- count1
- count2
;
1111 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1115 e12
->flags
&= ~EDGE_FALLTHRU
;
1116 e12
->flags
|= EDGE_FALSE_VALUE
;
1117 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1118 e12
->count
= all
- count1
;
1120 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1121 e14
->probability
= prob1
;
1122 e14
->count
= count1
;
1124 if (ncounts
) /* Assumed to be 0 or 1. */
1126 e23
->flags
&= ~EDGE_FALLTHRU
;
1127 e23
->flags
|= EDGE_FALSE_VALUE
;
1128 e23
->count
= all
- count1
- count2
;
1129 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1131 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1132 e24
->probability
= prob2
;
1133 e24
->count
= count2
;
1136 e34
->probability
= REG_BR_PROB_BASE
;
1137 e34
->count
= all
- count1
- count2
;
1143 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1146 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1148 histogram_value histogram
;
1149 enum tree_code code
;
1150 gcov_type count
, wrong_values
, all
;
1151 tree lhs_type
, result
;
1152 gcov_type prob1
, prob2
;
1153 unsigned int i
, steps
;
1154 gcov_type count1
, count2
;
1157 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1161 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1162 if (!INTEGRAL_TYPE_P (lhs_type
))
1165 code
= gimple_assign_rhs_code (stmt
);
1167 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1170 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1176 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1177 all
+= histogram
->hvalue
.counters
[i
];
1179 wrong_values
+= histogram
->hvalue
.counters
[i
];
1180 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1181 steps
= histogram
->hdata
.intvl
.steps
;
1182 all
+= wrong_values
;
1183 count1
= histogram
->hvalue
.counters
[0];
1184 count2
= histogram
->hvalue
.counters
[1];
1186 /* Compute probability of taking the optimal path. */
1187 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1189 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1193 if (flag_profile_correction
&& count1
+ count2
> all
)
1194 all
= count1
+ count2
;
1196 gcc_assert (count1
+ count2
<= all
);
1198 /* We require that we use just subtractions in at least 50% of all
1201 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1203 count
+= histogram
->hvalue
.counters
[i
];
1204 if (count
* 2 >= all
)
1208 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1211 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1214 fprintf (dump_file
, "Mod subtract transformation on insn ");
1215 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1218 /* Compute probability of taking the optimal path(s). */
1221 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1222 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1229 /* In practice, "steps" is always 2. This interface reflects this,
1230 and will need to be changed if "steps" can change. */
1231 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1233 gimple_assign_set_rhs_from_tree (si
, result
);
1234 update_stmt (gsi_stmt (*si
));
1239 struct profile_id_traits
: default_hashmap_traits
1241 template<typename T
>
1245 return e
.m_key
== UINT_MAX
;
1248 template<typename T
> static bool is_empty (T
&e
) { return e
.m_key
== 0; }
1249 template<typename T
> static void mark_deleted (T
&e
) { e
.m_key
= UINT_MAX
; }
1250 template<typename T
> static void mark_empty (T
&e
) { e
.m_key
= 0; }
1253 static hash_map
<unsigned int, cgraph_node
*, profile_id_traits
> *
1254 cgraph_node_map
= 0;
1256 /* Returns true if node graph is initialized. This
1257 is used to test if profile_id has been created
1258 for cgraph_nodes. */
1261 coverage_node_map_initialized_p (void)
1263 return cgraph_node_map
!= 0;
1266 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1267 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1268 that the PROFILE_IDs was already assigned. */
1271 init_node_map (bool local
)
1273 struct cgraph_node
*n
;
1275 = new hash_map
<unsigned int, cgraph_node
*, profile_id_traits
>;
1277 FOR_EACH_DEFINED_FUNCTION (n
)
1278 if (n
->has_gimple_body_p ())
1283 n
->profile_id
= coverage_compute_profile_id (n
);
1284 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1288 fprintf (dump_file
, "Local profile-id %i conflict"
1289 " with nodes %s/%i %s/%i\n",
1295 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1298 else if (!n
->profile_id
)
1302 "Node %s/%i has no profile-id"
1303 " (profile feedback missing?)\n",
1308 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1312 "Node %s/%i has IP profile-id %i conflict. "
1320 cgraph_node_map
->put (n
->profile_id
, n
);
1324 /* Delete the CGRAPH_NODE_MAP. */
1329 delete cgraph_node_map
;
1332 /* Return cgraph node for function with pid */
1335 find_func_by_profile_id (int profile_id
)
1337 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1344 /* Perform sanity check on the indirect call target. Due to race conditions,
1345 false function target may be attributed to an indirect call site. If the
1346 call expression type mismatches with the target function's type, expand_call
1347 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1348 Returns true if TARGET is considered ok for call CALL_STMT. */
1351 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1354 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1357 locus
= gimple_location (call_stmt
);
1358 if (dump_enabled_p ())
1359 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1360 "Skipping target %s with mismatching types for icall\n",
1365 /* Do transformation
1367 if (actual_callee_address == address_of_most_common_function/method)
1374 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1375 int prob
, gcov_type count
, gcov_type all
)
1380 tree tmp0
, tmp1
, tmp
;
1381 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1382 tree optype
= build_pointer_type (void_type_node
);
1383 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1384 gimple_stmt_iterator gsi
;
1390 cond_bb
= gimple_bb (icall_stmt
);
1391 gsi
= gsi_for_stmt (icall_stmt
);
1393 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1394 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1395 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1396 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1397 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1399 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1400 current_function_decl
));
1401 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1402 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1404 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1405 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1407 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1408 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1409 update_stmt (icall_stmt
);
1410 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1411 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1412 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1413 if ((dflags
& ECF_NORETURN
) != 0)
1414 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1415 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1418 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1419 e_cd
= split_block (cond_bb
, cond_stmt
);
1420 dcall_bb
= e_cd
->dest
;
1421 dcall_bb
->count
= count
;
1423 e_di
= split_block (dcall_bb
, dcall_stmt
);
1424 icall_bb
= e_di
->dest
;
1425 icall_bb
->count
= all
- count
;
1427 /* Do not disturb existing EH edges from the indirect call. */
1428 if (!stmt_ends_bb_p (icall_stmt
))
1429 e_ij
= split_block (icall_bb
, icall_stmt
);
1432 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1433 /* The indirect call might be noreturn. */
1436 e_ij
->probability
= REG_BR_PROB_BASE
;
1437 e_ij
->count
= all
- count
;
1438 e_ij
= single_pred_edge (split_edge (e_ij
));
1443 join_bb
= e_ij
->dest
;
1444 join_bb
->count
= all
;
1447 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1448 e_cd
->probability
= prob
;
1449 e_cd
->count
= count
;
1451 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1452 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1453 e_ci
->count
= all
- count
;
1459 if ((dflags
& ECF_NORETURN
) != 0)
1463 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1464 e_dj
->probability
= REG_BR_PROB_BASE
;
1465 e_dj
->count
= count
;
1467 e_ij
->count
= all
- count
;
1469 e_ij
->probability
= REG_BR_PROB_BASE
;
1472 /* Insert PHI node for the call result if necessary. */
1473 if (gimple_call_lhs (icall_stmt
)
1474 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1475 && (dflags
& ECF_NORETURN
) == 0)
1477 tree result
= gimple_call_lhs (icall_stmt
);
1478 gphi
*phi
= create_phi_node (result
, join_bb
);
1479 gimple_call_set_lhs (icall_stmt
,
1480 duplicate_ssa_name (result
, icall_stmt
));
1481 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1482 gimple_call_set_lhs (dcall_stmt
,
1483 duplicate_ssa_name (result
, dcall_stmt
));
1484 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1487 /* Build an EH edge for the direct call if necessary. */
1488 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1489 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1491 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1494 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1495 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1497 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1498 for (psi
= gsi_start_phis (e_eh
->dest
);
1499 !gsi_end_p (psi
); gsi_next (&psi
))
1501 gphi
*phi
= psi
.phi ();
1502 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1503 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1510 For every checked indirect/virtual call determine if most common pid of
1511 function/class method has probability more than 50%. If yes modify code of
1516 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1519 histogram_value histogram
;
1520 gcov_type val
, count
, all
, bb_all
;
1521 struct cgraph_node
*direct_call
;
1523 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1527 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1530 if (gimple_call_internal_p (stmt
))
1533 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1537 val
= histogram
->hvalue
.counters
[0];
1538 count
= histogram
->hvalue
.counters
[1];
1539 all
= histogram
->hvalue
.counters
[2];
1541 bb_all
= gimple_bb (stmt
)->count
;
1542 /* The order of CHECK_COUNTER calls is important -
1543 since check_counter can correct the third parameter
1544 and we want to make count <= all <= bb_all. */
1545 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1546 || check_counter (stmt
, "ic", &count
, &all
, all
))
1548 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1552 if (4 * count
<= 3 * all
)
1555 direct_call
= find_func_by_profile_id ((int)val
);
1557 if (direct_call
== NULL
)
1563 fprintf (dump_file
, "Indirect call -> direct call from other module");
1564 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1565 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1571 if (!check_ic_target (stmt
, direct_call
))
1575 fprintf (dump_file
, "Indirect call -> direct call ");
1576 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1577 fprintf (dump_file
, "=> ");
1578 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1579 fprintf (dump_file
, " transformation skipped because of type mismatch");
1580 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1582 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1588 fprintf (dump_file
, "Indirect call -> direct call ");
1589 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1590 fprintf (dump_file
, "=> ");
1591 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1592 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1593 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1594 fprintf (dump_file
, "hist->count %"PRId64
1595 " hist->all %"PRId64
"\n", count
, all
);
1601 /* Return true if the stringop CALL with FNDECL shall be profiled.
1602 SIZE_ARG be set to the argument index for the size of the string
1606 interesting_stringop_to_profile_p (tree fndecl
, gcall
*call
, int *size_arg
)
1608 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1610 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1611 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1616 case BUILT_IN_MEMCPY
:
1617 case BUILT_IN_MEMPCPY
:
1619 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1620 INTEGER_TYPE
, VOID_TYPE
);
1621 case BUILT_IN_MEMSET
:
1623 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1624 INTEGER_TYPE
, VOID_TYPE
);
1625 case BUILT_IN_BZERO
:
1627 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1634 /* Convert stringop (..., vcall_size)
1636 if (vcall_size == icall_size)
1637 stringop (..., icall_size);
1639 stringop (..., vcall_size);
1640 assuming we'll propagate a true constant into ICALL_SIZE later. */
1643 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, int prob
,
1644 gcov_type count
, gcov_type all
)
1649 tree tmp0
, tmp1
, vcall_size
, optype
;
1650 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1651 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1652 gimple_stmt_iterator gsi
;
1656 fndecl
= gimple_call_fndecl (vcall_stmt
);
1657 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1660 cond_bb
= gimple_bb (vcall_stmt
);
1661 gsi
= gsi_for_stmt (vcall_stmt
);
1663 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1664 optype
= TREE_TYPE (vcall_size
);
1666 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1667 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1668 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1669 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1671 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1672 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1674 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1675 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1677 gimple_set_vdef (vcall_stmt
, NULL
);
1678 gimple_set_vuse (vcall_stmt
, NULL
);
1679 update_stmt (vcall_stmt
);
1680 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1681 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1682 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1685 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1686 e_ci
= split_block (cond_bb
, cond_stmt
);
1687 icall_bb
= e_ci
->dest
;
1688 icall_bb
->count
= count
;
1690 e_iv
= split_block (icall_bb
, icall_stmt
);
1691 vcall_bb
= e_iv
->dest
;
1692 vcall_bb
->count
= all
- count
;
1694 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1695 join_bb
= e_vj
->dest
;
1696 join_bb
->count
= all
;
1698 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1699 e_ci
->probability
= prob
;
1700 e_ci
->count
= count
;
1702 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1703 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1704 e_cv
->count
= all
- count
;
1708 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1709 e_ij
->probability
= REG_BR_PROB_BASE
;
1710 e_ij
->count
= count
;
1712 e_vj
->probability
= REG_BR_PROB_BASE
;
1713 e_vj
->count
= all
- count
;
1715 /* Insert PHI node for the call result if necessary. */
1716 if (gimple_call_lhs (vcall_stmt
)
1717 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1719 tree result
= gimple_call_lhs (vcall_stmt
);
1720 gphi
*phi
= create_phi_node (result
, join_bb
);
1721 gimple_call_set_lhs (vcall_stmt
,
1722 duplicate_ssa_name (result
, vcall_stmt
));
1723 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1724 gimple_call_set_lhs (icall_stmt
,
1725 duplicate_ssa_name (result
, icall_stmt
));
1726 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1729 /* Because these are all string op builtins, they're all nothrow. */
1730 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1731 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1734 /* Find values inside STMT for that we want to measure histograms for
1735 division/modulo optimization. */
1737 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1742 enum built_in_function fcode
;
1743 histogram_value histogram
;
1744 gcov_type count
, all
, val
;
1746 unsigned int dest_align
, src_align
;
1751 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1754 fndecl
= gimple_call_fndecl (stmt
);
1757 fcode
= DECL_FUNCTION_CODE (fndecl
);
1758 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1761 blck_size
= gimple_call_arg (stmt
, size_arg
);
1762 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1765 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1768 val
= histogram
->hvalue
.counters
[0];
1769 count
= histogram
->hvalue
.counters
[1];
1770 all
= histogram
->hvalue
.counters
[2];
1771 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1772 /* We require that count is at least half of all; this means
1773 that for the transformation to fire the value must be constant
1774 at least 80% of time. */
1775 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1777 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1780 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1783 dest
= gimple_call_arg (stmt
, 0);
1784 dest_align
= get_pointer_alignment (dest
);
1787 case BUILT_IN_MEMCPY
:
1788 case BUILT_IN_MEMPCPY
:
1789 src
= gimple_call_arg (stmt
, 1);
1790 src_align
= get_pointer_alignment (src
);
1791 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1794 case BUILT_IN_MEMSET
:
1795 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1796 gimple_call_arg (stmt
, 1),
1800 case BUILT_IN_BZERO
:
1801 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1809 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1810 tree_val
= build_int_cst (get_gcov_type (), val
);
1814 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1815 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1817 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1818 TYPE_PRECISION (get_gcov_type ()), false));
1823 fprintf (dump_file
, "Single value %i stringop transformation on ",
1825 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1827 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1833 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1834 HOST_WIDE_INT
*expected_size
)
1836 histogram_value histogram
;
1837 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1839 *expected_size
= -1;
1840 else if (!histogram
->hvalue
.counters
[1])
1842 *expected_size
= -1;
1843 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1848 size
= ((histogram
->hvalue
.counters
[0]
1849 + histogram
->hvalue
.counters
[1] / 2)
1850 / histogram
->hvalue
.counters
[1]);
1851 /* Even if we can hold bigger value in SIZE, INT_MAX
1852 is safe "infinity" for code generation strategies. */
1855 *expected_size
= size
;
1856 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1858 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1860 *expected_align
= 0;
1861 else if (!histogram
->hvalue
.counters
[0])
1863 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1864 *expected_align
= 0;
1871 count
= histogram
->hvalue
.counters
[0];
1873 while (!(count
& alignment
)
1874 && (alignment
* 2 * BITS_PER_UNIT
))
1876 *expected_align
= alignment
* BITS_PER_UNIT
;
1877 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1882 /* Find values inside STMT for that we want to measure histograms for
1883 division/modulo optimization. */
1885 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1887 tree lhs
, divisor
, op0
, type
;
1888 histogram_value hist
;
1890 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1893 lhs
= gimple_assign_lhs (stmt
);
1894 type
= TREE_TYPE (lhs
);
1895 if (!INTEGRAL_TYPE_P (type
))
1898 switch (gimple_assign_rhs_code (stmt
))
1900 case TRUNC_DIV_EXPR
:
1901 case TRUNC_MOD_EXPR
:
1902 divisor
= gimple_assign_rhs2 (stmt
);
1903 op0
= gimple_assign_rhs1 (stmt
);
1905 values
->reserve (3);
1907 if (TREE_CODE (divisor
) == SSA_NAME
)
1908 /* Check for the case where the divisor is the same value most
1910 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1911 HIST_TYPE_SINGLE_VALUE
,
1914 /* For mod, check whether it is not often a noop (or replaceable by
1915 a few subtractions). */
1916 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1917 && TYPE_UNSIGNED (type
))
1920 /* Check for a special case where the divisor is power of 2. */
1921 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1925 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1926 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1928 hist
->hdata
.intvl
.int_start
= 0;
1929 hist
->hdata
.intvl
.steps
= 2;
1930 values
->quick_push (hist
);
1939 /* Find calls inside STMT for that we want to measure histograms for
1940 indirect/virtual call optimization. */
1943 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1947 if (gimple_code (stmt
) != GIMPLE_CALL
1948 || gimple_call_internal_p (stmt
)
1949 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1952 callee
= gimple_call_fn (stmt
);
1954 values
->reserve (3);
1956 values
->quick_push (gimple_alloc_histogram_value (
1958 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1959 HIST_TYPE_INDIR_CALL_TOPN
:
1960 HIST_TYPE_INDIR_CALL
,
1966 /* Find values inside STMT for that we want to measure histograms for
1967 string operations. */
1969 gimple_stringops_values_to_profile (gimple gs
, histogram_values
*values
)
1977 stmt
= dyn_cast
<gcall
*> (gs
);
1980 fndecl
= gimple_call_fndecl (stmt
);
1984 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1987 dest
= gimple_call_arg (stmt
, 0);
1988 blck_size
= gimple_call_arg (stmt
, size_arg
);
1990 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1992 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1993 HIST_TYPE_SINGLE_VALUE
,
1995 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1998 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1999 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
2003 /* Find values inside STMT for that we want to measure histograms and adds
2004 them to list VALUES. */
2007 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
2009 gimple_divmod_values_to_profile (stmt
, values
);
2010 gimple_stringops_values_to_profile (stmt
, values
);
2011 gimple_indirect_call_to_profile (stmt
, values
);
2015 gimple_find_values_to_profile (histogram_values
*values
)
2018 gimple_stmt_iterator gsi
;
2020 histogram_value hist
= NULL
;
2023 FOR_EACH_BB_FN (bb
, cfun
)
2024 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2025 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2027 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2029 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2033 case HIST_TYPE_INTERVAL
:
2034 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2037 case HIST_TYPE_POW2
:
2038 hist
->n_counters
= 2;
2041 case HIST_TYPE_SINGLE_VALUE
:
2042 hist
->n_counters
= 3;
2045 case HIST_TYPE_CONST_DELTA
:
2046 hist
->n_counters
= 4;
2049 case HIST_TYPE_INDIR_CALL
:
2050 hist
->n_counters
= 3;
2053 case HIST_TYPE_TIME_PROFILE
:
2054 hist
->n_counters
= 1;
2057 case HIST_TYPE_AVERAGE
:
2058 hist
->n_counters
= 2;
2062 hist
->n_counters
= 1;
2065 case HIST_TYPE_INDIR_CALL_TOPN
:
2066 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2074 fprintf (dump_file
, "Stmt ");
2075 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2076 dump_histogram_value (dump_file
, hist
);