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"
37 #include "dominance.h"
39 #include "basic-block.h"
40 #include "value-prof.h"
42 #include "insn-config.h"
46 #include "tree-ssa-alias.h"
47 #include "internal-fn.h"
49 #include "gimple-expr.h"
53 #include "gimple-iterator.h"
54 #include "gimple-ssa.h"
56 #include "tree-phinodes.h"
57 #include "ssa-iterators.h"
58 #include "stringpool.h"
59 #include "tree-ssanames.h"
60 #include "diagnostic.h"
61 #include "gimple-pretty-print.h"
69 #include "plugin-api.h"
72 #include "data-streamer.h"
74 #include "tree-nested.h"
77 /* In this file value profile based optimizations are placed. Currently the
78 following optimizations are implemented (for more detailed descriptions
79 see comments at value_profile_transformations):
81 1) Division/modulo specialization. Provided that we can determine that the
82 operands of the division have some special properties, we may use it to
83 produce more effective code.
85 2) Indirect/virtual call specialization. If we can determine most
86 common function callee in indirect/virtual call. We can use this
87 information to improve code effectiveness (especially info for
90 3) Speculative prefetching. If we are able to determine that the difference
91 between addresses accessed by a memory reference is usually constant, we
92 may add the prefetch instructions.
93 FIXME: This transformation was removed together with RTL based value
97 Value profiling internals
98 ==========================
100 Every value profiling transformation starts with defining what values
101 to profile. There are different histogram types (see HIST_TYPE_* in
102 value-prof.h) and each transformation can request one or more histogram
103 types per GIMPLE statement. The function gimple_find_values_to_profile()
104 collects the values to profile in a vec, and adds the number of counters
105 required for the different histogram types.
107 For a -fprofile-generate run, the statements for which values should be
108 recorded, are instrumented in instrument_values(). The instrumentation
109 is done by helper functions that can be found in tree-profile.c, where
110 new types of histograms can be added if necessary.
112 After a -fprofile-use, the value profiling data is read back in by
113 compute_value_histograms() that translates the collected data to
114 histograms and attaches them to the profiled statements via
115 gimple_add_histogram_value(). Histograms are stored in a hash table
116 that is attached to every intrumented function, see VALUE_HISTOGRAMS
119 The value-profile transformations driver is the function
120 gimple_value_profile_transformations(). It traverses all statements in
121 the to-be-transformed function, and looks for statements with one or
122 more histograms attached to it. If a statement has histograms, the
123 transformation functions are called on the statement.
125 Limitations / FIXME / TODO:
126 * Only one histogram of each type can be associated with a statement.
127 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
128 (This type of histogram was originally used to implement a form of
129 stride profiling based speculative prefetching to improve SPEC2000
130 scores for memory-bound benchmarks, mcf and equake. However, this
131 was an RTL value-profiling transformation, and those have all been
133 * Some value profile transformations are done in builtins.c (?!)
134 * Updating of histograms needs some TLC.
135 * The value profiling code could be used to record analysis results
136 from non-profiling (e.g. VRP).
137 * Adding new profilers should be simplified, starting with a cleanup
138 of what-happens-where andwith making gimple_find_values_to_profile
139 and gimple_value_profile_transformations table-driven, perhaps...
142 static tree
gimple_divmod_fixed_value (gimple
, tree
, int, gcov_type
, gcov_type
);
143 static tree
gimple_mod_pow2 (gimple
, int, gcov_type
, gcov_type
);
144 static tree
gimple_mod_subtract (gimple
, int, int, int, gcov_type
, gcov_type
,
146 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
147 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
148 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
149 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
150 static bool gimple_ic_transform (gimple_stmt_iterator
*);
152 /* Allocate histogram value. */
155 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
156 enum hist_type type
, gimple stmt
, tree value
)
158 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
159 hist
->hvalue
.value
= value
;
160 hist
->hvalue
.stmt
= stmt
;
165 /* Hash value for histogram. */
168 histogram_hash (const void *x
)
170 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
173 /* Return nonzero if statement for histogram_value X is Y. */
176 histogram_eq (const void *x
, const void *y
)
178 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
181 /* Set histogram for STMT. */
184 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
187 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
189 if (!VALUE_HISTOGRAMS (fun
))
190 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
192 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
193 htab_hash_pointer (stmt
),
194 hist
? INSERT
: NO_INSERT
);
198 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
204 /* Get histogram list for STMT. */
207 gimple_histogram_value (struct function
*fun
, gimple stmt
)
209 if (!VALUE_HISTOGRAMS (fun
))
211 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
212 htab_hash_pointer (stmt
));
215 /* Add histogram for STMT. */
218 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
219 histogram_value hist
)
221 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
222 set_histogram_value (fun
, stmt
, hist
);
227 /* Remove histogram HIST from STMT's histogram list. */
230 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
231 histogram_value hist
)
233 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
236 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
240 while (hist2
->hvalue
.next
!= hist
)
241 hist2
= hist2
->hvalue
.next
;
242 hist2
->hvalue
.next
= hist
->hvalue
.next
;
244 free (hist
->hvalue
.counters
);
245 #ifdef ENABLE_CHECKING
246 memset (hist
, 0xab, sizeof (*hist
));
252 /* Lookup histogram of type TYPE in the STMT. */
255 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
258 histogram_value hist
;
259 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
260 hist
= hist
->hvalue
.next
)
261 if (hist
->type
== type
)
266 /* Dump information about HIST to DUMP_FILE. */
269 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
273 case HIST_TYPE_INTERVAL
:
274 fprintf (dump_file
, "Interval counter range %d -- %d",
275 hist
->hdata
.intvl
.int_start
,
276 (hist
->hdata
.intvl
.int_start
277 + hist
->hdata
.intvl
.steps
- 1));
278 if (hist
->hvalue
.counters
)
281 fprintf (dump_file
, " [");
282 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
283 fprintf (dump_file
, " %d:%"PRId64
,
284 hist
->hdata
.intvl
.int_start
+ i
,
285 (int64_t) hist
->hvalue
.counters
[i
]);
286 fprintf (dump_file
, " ] outside range:%"PRId64
,
287 (int64_t) hist
->hvalue
.counters
[i
]);
289 fprintf (dump_file
, ".\n");
293 fprintf (dump_file
, "Pow2 counter ");
294 if (hist
->hvalue
.counters
)
296 fprintf (dump_file
, "pow2:%"PRId64
298 (int64_t) hist
->hvalue
.counters
[0],
299 (int64_t) hist
->hvalue
.counters
[1]);
301 fprintf (dump_file
, ".\n");
304 case HIST_TYPE_SINGLE_VALUE
:
305 fprintf (dump_file
, "Single value ");
306 if (hist
->hvalue
.counters
)
308 fprintf (dump_file
, "value:%"PRId64
311 (int64_t) hist
->hvalue
.counters
[0],
312 (int64_t) hist
->hvalue
.counters
[1],
313 (int64_t) hist
->hvalue
.counters
[2]);
315 fprintf (dump_file
, ".\n");
318 case HIST_TYPE_AVERAGE
:
319 fprintf (dump_file
, "Average value ");
320 if (hist
->hvalue
.counters
)
322 fprintf (dump_file
, "sum:%"PRId64
324 (int64_t) hist
->hvalue
.counters
[0],
325 (int64_t) hist
->hvalue
.counters
[1]);
327 fprintf (dump_file
, ".\n");
331 fprintf (dump_file
, "IOR value ");
332 if (hist
->hvalue
.counters
)
334 fprintf (dump_file
, "ior:%"PRId64
,
335 (int64_t) hist
->hvalue
.counters
[0]);
337 fprintf (dump_file
, ".\n");
340 case HIST_TYPE_CONST_DELTA
:
341 fprintf (dump_file
, "Constant delta ");
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_INDIR_CALL
:
354 fprintf (dump_file
, "Indirect call ");
355 if (hist
->hvalue
.counters
)
357 fprintf (dump_file
, "value:%"PRId64
360 (int64_t) hist
->hvalue
.counters
[0],
361 (int64_t) hist
->hvalue
.counters
[1],
362 (int64_t) hist
->hvalue
.counters
[2]);
364 fprintf (dump_file
, ".\n");
366 case HIST_TYPE_TIME_PROFILE
:
367 fprintf (dump_file
, "Time profile ");
368 if (hist
->hvalue
.counters
)
370 fprintf (dump_file
, "time:%"PRId64
,
371 (int64_t) hist
->hvalue
.counters
[0]);
373 fprintf (dump_file
, ".\n");
375 case HIST_TYPE_INDIR_CALL_TOPN
:
376 fprintf (dump_file
, "Indirect call topn ");
377 if (hist
->hvalue
.counters
)
381 fprintf (dump_file
, "accu:%"PRId64
, hist
->hvalue
.counters
[0]);
382 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
384 fprintf (dump_file
, " target:%"PRId64
" value:%"PRId64
,
385 (int64_t) hist
->hvalue
.counters
[i
],
386 (int64_t) hist
->hvalue
.counters
[i
+1]);
389 fprintf (dump_file
, ".\n");
396 /* Dump information about HIST to DUMP_FILE. */
399 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
404 bp
= bitpack_create (ob
->main_stream
);
405 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
406 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
407 streamer_write_bitpack (&bp
);
410 case HIST_TYPE_INTERVAL
:
411 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
412 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
417 for (i
= 0; i
< hist
->n_counters
; i
++)
418 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
419 if (hist
->hvalue
.next
)
420 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
422 /* Dump information about HIST to DUMP_FILE. */
425 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
428 unsigned int ncounters
= 0;
431 histogram_value new_val
;
433 histogram_value
*next_p
= NULL
;
437 bp
= streamer_read_bitpack (ib
);
438 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
439 next
= bp_unpack_value (&bp
, 1);
440 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
443 case HIST_TYPE_INTERVAL
:
444 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
445 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
446 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
450 case HIST_TYPE_AVERAGE
:
454 case HIST_TYPE_SINGLE_VALUE
:
455 case HIST_TYPE_INDIR_CALL
:
459 case HIST_TYPE_CONST_DELTA
:
464 case HIST_TYPE_TIME_PROFILE
:
468 case HIST_TYPE_INDIR_CALL_TOPN
:
469 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
475 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
476 new_val
->n_counters
= ncounters
;
477 for (i
= 0; i
< ncounters
; i
++)
478 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
480 gimple_add_histogram_value (cfun
, stmt
, new_val
);
483 next_p
= &new_val
->hvalue
.next
;
488 /* Dump all histograms attached to STMT to DUMP_FILE. */
491 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
493 histogram_value hist
;
494 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
495 dump_histogram_value (dump_file
, hist
);
498 /* Remove all histograms associated with STMT. */
501 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
504 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
505 gimple_remove_histogram_value (fun
, stmt
, val
);
508 /* Duplicate all histograms associates with OSTMT to STMT. */
511 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
512 struct function
*ofun
, gimple ostmt
)
515 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
517 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
518 memcpy (new_val
, val
, sizeof (*val
));
519 new_val
->hvalue
.stmt
= stmt
;
520 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
521 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
522 gimple_add_histogram_value (fun
, stmt
, new_val
);
527 /* Move all histograms associated with OSTMT to STMT. */
530 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
532 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
535 /* The following three statements can't be reordered,
536 because histogram hashtab relies on stmt field value
537 for finding the exact slot. */
538 set_histogram_value (fun
, ostmt
, NULL
);
539 for (; val
!= NULL
; val
= val
->hvalue
.next
)
540 val
->hvalue
.stmt
= stmt
;
541 set_histogram_value (fun
, stmt
, val
);
545 static bool error_found
= false;
547 /* Helper function for verify_histograms. For each histogram reachable via htab
548 walk verify that it was reached via statement walk. */
551 visit_hist (void **slot
, void *data
)
553 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
554 histogram_value hist
= *(histogram_value
*) slot
;
556 if (!visited
->contains (hist
)
557 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
559 error ("dead histogram");
560 dump_histogram_value (stderr
, hist
);
561 debug_gimple_stmt (hist
->hvalue
.stmt
);
568 /* Verify sanity of the histograms. */
571 verify_histograms (void)
574 gimple_stmt_iterator gsi
;
575 histogram_value hist
;
578 hash_set
<histogram_value
> visited_hists
;
579 FOR_EACH_BB_FN (bb
, cfun
)
580 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
582 gimple stmt
= gsi_stmt (gsi
);
584 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
585 hist
= hist
->hvalue
.next
)
587 if (hist
->hvalue
.stmt
!= stmt
)
589 error ("Histogram value statement does not correspond to "
590 "the statement it is associated with");
591 debug_gimple_stmt (stmt
);
592 dump_histogram_value (stderr
, hist
);
595 visited_hists
.add (hist
);
598 if (VALUE_HISTOGRAMS (cfun
))
599 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
601 internal_error ("verify_histograms failed");
604 /* Helper function for verify_histograms. For each histogram reachable via htab
605 walk verify that it was reached via statement walk. */
608 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
610 histogram_value hist
= *(histogram_value
*) slot
;
611 free (hist
->hvalue
.counters
);
612 #ifdef ENABLE_CHECKING
613 memset (hist
, 0xab, sizeof (*hist
));
620 free_histograms (void)
622 if (VALUE_HISTOGRAMS (cfun
))
624 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
625 htab_delete (VALUE_HISTOGRAMS (cfun
));
626 VALUE_HISTOGRAMS (cfun
) = NULL
;
631 /* The overall number of invocations of the counter should match
632 execution count of basic block. Report it as error rather than
633 internal error as it might mean that user has misused the profile
637 check_counter (gimple stmt
, const char * name
,
638 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
640 if (*all
!= bb_count
|| *count
> *all
)
643 locus
= (stmt
!= NULL
)
644 ? gimple_location (stmt
)
645 : DECL_SOURCE_LOCATION (current_function_decl
);
646 if (flag_profile_correction
)
648 if (dump_enabled_p ())
649 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
650 "correcting inconsistent value profile: %s "
651 "profiler overall count (%d) does not match BB "
652 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
660 error_at (locus
, "corrupted value profile: %s "
661 "profile counter (%d out of %d) inconsistent with "
662 "basic-block count (%d)",
675 /* GIMPLE based transformations. */
678 gimple_value_profile_transformations (void)
681 gimple_stmt_iterator gsi
;
682 bool changed
= false;
684 FOR_EACH_BB_FN (bb
, cfun
)
686 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
688 gimple stmt
= gsi_stmt (gsi
);
689 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
695 fprintf (dump_file
, "Trying transformations on stmt ");
696 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
697 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
700 /* Transformations: */
701 /* The order of things in this conditional controls which
702 transformation is used when more than one is applicable. */
703 /* It is expected that any code added by the transformations
704 will be added before the current statement, and that the
705 current statement remain valid (although possibly
706 modified) upon return. */
707 if (gimple_mod_subtract_transform (&gsi
)
708 || gimple_divmod_fixed_value_transform (&gsi
)
709 || gimple_mod_pow2_value_transform (&gsi
)
710 || gimple_stringops_transform (&gsi
)
711 || gimple_ic_transform (&gsi
))
713 stmt
= gsi_stmt (gsi
);
715 /* Original statement may no longer be in the same block. */
716 if (bb
!= gimple_bb (stmt
))
718 bb
= gimple_bb (stmt
);
719 gsi
= gsi_for_stmt (stmt
);
734 /* Generate code for transformation 1 (with parent gimple assignment
735 STMT and probability of taking the optimal path PROB, which is
736 equivalent to COUNT/ALL within roundoff error). This generates the
737 result into a temp and returns the temp; it does not replace or
738 alter the original STMT. */
741 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
744 gimple stmt1
, stmt2
, stmt3
;
745 tree tmp0
, tmp1
, tmp2
;
746 gimple bb1end
, bb2end
, bb3end
;
747 basic_block bb
, bb2
, bb3
, bb4
;
748 tree optype
, op1
, op2
;
749 edge e12
, e13
, e23
, e24
, e34
;
750 gimple_stmt_iterator gsi
;
752 gcc_assert (is_gimple_assign (stmt
)
753 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
754 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
756 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
757 op1
= gimple_assign_rhs1 (stmt
);
758 op2
= gimple_assign_rhs2 (stmt
);
760 bb
= gimple_bb (stmt
);
761 gsi
= gsi_for_stmt (stmt
);
763 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
764 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
765 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
766 stmt2
= gimple_build_assign (tmp1
, op2
);
767 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
768 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
769 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
770 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
773 tmp2
= create_tmp_reg (optype
, "PROF");
774 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
776 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
779 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
781 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
785 /* Edge e23 connects bb2 to bb3, etc. */
786 e12
= split_block (bb
, bb1end
);
789 e23
= split_block (bb2
, bb2end
);
791 bb3
->count
= all
- count
;
792 e34
= split_block (bb3
, bb3end
);
796 e12
->flags
&= ~EDGE_FALLTHRU
;
797 e12
->flags
|= EDGE_FALSE_VALUE
;
798 e12
->probability
= prob
;
801 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
802 e13
->probability
= REG_BR_PROB_BASE
- prob
;
803 e13
->count
= all
- count
;
807 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
808 e24
->probability
= REG_BR_PROB_BASE
;
811 e34
->probability
= REG_BR_PROB_BASE
;
812 e34
->count
= all
- count
;
818 /* Do transform 1) on INSN if applicable. */
821 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
823 histogram_value histogram
;
825 gcov_type val
, count
, all
;
826 tree result
, value
, tree_val
;
830 stmt
= gsi_stmt (*si
);
831 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
834 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
837 code
= gimple_assign_rhs_code (stmt
);
839 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
842 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
843 HIST_TYPE_SINGLE_VALUE
);
847 value
= histogram
->hvalue
.value
;
848 val
= histogram
->hvalue
.counters
[0];
849 count
= histogram
->hvalue
.counters
[1];
850 all
= histogram
->hvalue
.counters
[2];
851 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
853 /* We require that count is at least half of all; this means
854 that for the transformation to fire the value must be constant
855 at least 50% of time (and 75% gives the guarantee of usage). */
856 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
858 || optimize_bb_for_size_p (gimple_bb (stmt
)))
861 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
864 /* Compute probability of taking the optimal path. */
866 prob
= GCOV_COMPUTE_SCALE (count
, all
);
870 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
871 tree_val
= build_int_cst (get_gcov_type (), val
);
875 a
[0] = (unsigned HOST_WIDE_INT
) val
;
876 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
878 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
879 TYPE_PRECISION (get_gcov_type ()), false));
881 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
885 fprintf (dump_file
, "Div/mod by constant ");
886 print_generic_expr (dump_file
, value
, TDF_SLIM
);
887 fprintf (dump_file
, "=");
888 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
889 fprintf (dump_file
, " transformation on insn ");
890 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
893 gimple_assign_set_rhs_from_tree (si
, result
);
894 update_stmt (gsi_stmt (*si
));
899 /* Generate code for transformation 2 (with parent gimple assign STMT and
900 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
901 within roundoff error). This generates the result into a temp and returns
902 the temp; it does not replace or alter the original STMT. */
904 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
906 gimple stmt1
, stmt2
, stmt3
, stmt4
;
908 gimple bb1end
, bb2end
, bb3end
;
909 basic_block bb
, bb2
, bb3
, bb4
;
910 tree optype
, op1
, op2
;
911 edge e12
, e13
, e23
, e24
, e34
;
912 gimple_stmt_iterator gsi
;
915 gcc_assert (is_gimple_assign (stmt
)
916 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
918 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
919 op1
= gimple_assign_rhs1 (stmt
);
920 op2
= gimple_assign_rhs2 (stmt
);
922 bb
= gimple_bb (stmt
);
923 gsi
= gsi_for_stmt (stmt
);
925 result
= create_tmp_reg (optype
, "PROF");
926 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
927 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
928 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
929 build_int_cst (optype
, -1));
930 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
931 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
932 NULL_TREE
, NULL_TREE
);
933 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
934 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
935 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
938 /* tmp2 == op2-1 inherited from previous block. */
939 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
940 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
943 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
945 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
949 /* Edge e23 connects bb2 to bb3, etc. */
950 e12
= split_block (bb
, bb1end
);
953 e23
= split_block (bb2
, bb2end
);
955 bb3
->count
= all
- count
;
956 e34
= split_block (bb3
, bb3end
);
960 e12
->flags
&= ~EDGE_FALLTHRU
;
961 e12
->flags
|= EDGE_FALSE_VALUE
;
962 e12
->probability
= prob
;
965 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
966 e13
->probability
= REG_BR_PROB_BASE
- prob
;
967 e13
->count
= all
- count
;
971 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
972 e24
->probability
= REG_BR_PROB_BASE
;
975 e34
->probability
= REG_BR_PROB_BASE
;
976 e34
->count
= all
- count
;
981 /* Do transform 2) on INSN if applicable. */
983 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
985 histogram_value histogram
;
987 gcov_type count
, wrong_values
, all
;
988 tree lhs_type
, result
, value
;
992 stmt
= gsi_stmt (*si
);
993 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
996 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
997 if (!INTEGRAL_TYPE_P (lhs_type
))
1000 code
= gimple_assign_rhs_code (stmt
);
1002 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1005 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
1009 value
= histogram
->hvalue
.value
;
1010 wrong_values
= histogram
->hvalue
.counters
[0];
1011 count
= histogram
->hvalue
.counters
[1];
1013 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1015 /* We require that we hit a power of 2 at least half of all evaluations. */
1016 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
1017 || count
< wrong_values
1018 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1023 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
1024 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1027 /* Compute probability of taking the optimal path. */
1028 all
= count
+ wrong_values
;
1030 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1034 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1038 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1040 gimple_assign_set_rhs_from_tree (si
, result
);
1041 update_stmt (gsi_stmt (*si
));
1046 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1047 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1048 supported and this is built into this interface. The probabilities of taking
1049 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1050 COUNT2/ALL respectively within roundoff error). This generates the
1051 result into a temp and returns the temp; it does not replace or alter
1052 the original STMT. */
1053 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1056 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
1057 gcov_type count1
, gcov_type count2
, gcov_type all
)
1059 gimple stmt1
, stmt2
, stmt3
;
1061 gimple bb1end
, bb2end
= NULL
, bb3end
;
1062 basic_block bb
, bb2
, bb3
, bb4
;
1063 tree optype
, op1
, op2
;
1064 edge e12
, e23
= 0, e24
, e34
, e14
;
1065 gimple_stmt_iterator gsi
;
1068 gcc_assert (is_gimple_assign (stmt
)
1069 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1071 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1072 op1
= gimple_assign_rhs1 (stmt
);
1073 op2
= gimple_assign_rhs2 (stmt
);
1075 bb
= gimple_bb (stmt
);
1076 gsi
= gsi_for_stmt (stmt
);
1078 result
= create_tmp_reg (optype
, "PROF");
1079 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1080 stmt1
= gimple_build_assign (result
, op1
);
1081 stmt2
= gimple_build_assign (tmp1
, op2
);
1082 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1083 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1084 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1085 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1088 if (ncounts
) /* Assumed to be 0 or 1 */
1090 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
1091 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1092 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1093 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1097 /* Fallback case. */
1098 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
1100 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1104 /* Edge e23 connects bb2 to bb3, etc. */
1105 /* However block 3 is optional; if it is not there, references
1106 to 3 really refer to block 2. */
1107 e12
= split_block (bb
, bb1end
);
1109 bb2
->count
= all
- count1
;
1111 if (ncounts
) /* Assumed to be 0 or 1. */
1113 e23
= split_block (bb2
, bb2end
);
1115 bb3
->count
= all
- count1
- count2
;
1118 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1122 e12
->flags
&= ~EDGE_FALLTHRU
;
1123 e12
->flags
|= EDGE_FALSE_VALUE
;
1124 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1125 e12
->count
= all
- count1
;
1127 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1128 e14
->probability
= prob1
;
1129 e14
->count
= count1
;
1131 if (ncounts
) /* Assumed to be 0 or 1. */
1133 e23
->flags
&= ~EDGE_FALLTHRU
;
1134 e23
->flags
|= EDGE_FALSE_VALUE
;
1135 e23
->count
= all
- count1
- count2
;
1136 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1138 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1139 e24
->probability
= prob2
;
1140 e24
->count
= count2
;
1143 e34
->probability
= REG_BR_PROB_BASE
;
1144 e34
->count
= all
- count1
- count2
;
1150 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1153 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1155 histogram_value histogram
;
1156 enum tree_code code
;
1157 gcov_type count
, wrong_values
, all
;
1158 tree lhs_type
, result
;
1159 gcov_type prob1
, prob2
;
1160 unsigned int i
, steps
;
1161 gcov_type count1
, count2
;
1164 stmt
= gsi_stmt (*si
);
1165 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1168 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1169 if (!INTEGRAL_TYPE_P (lhs_type
))
1172 code
= gimple_assign_rhs_code (stmt
);
1174 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1177 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1183 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1184 all
+= histogram
->hvalue
.counters
[i
];
1186 wrong_values
+= histogram
->hvalue
.counters
[i
];
1187 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1188 steps
= histogram
->hdata
.intvl
.steps
;
1189 all
+= wrong_values
;
1190 count1
= histogram
->hvalue
.counters
[0];
1191 count2
= histogram
->hvalue
.counters
[1];
1193 /* Compute probability of taking the optimal path. */
1194 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1196 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1200 if (flag_profile_correction
&& count1
+ count2
> all
)
1201 all
= count1
+ count2
;
1203 gcc_assert (count1
+ count2
<= all
);
1205 /* We require that we use just subtractions in at least 50% of all
1208 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1210 count
+= histogram
->hvalue
.counters
[i
];
1211 if (count
* 2 >= all
)
1215 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1218 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1221 fprintf (dump_file
, "Mod subtract transformation on insn ");
1222 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1225 /* Compute probability of taking the optimal path(s). */
1228 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1229 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1236 /* In practice, "steps" is always 2. This interface reflects this,
1237 and will need to be changed if "steps" can change. */
1238 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1240 gimple_assign_set_rhs_from_tree (si
, result
);
1241 update_stmt (gsi_stmt (*si
));
1246 struct profile_id_traits
: default_hashmap_traits
1248 template<typename T
>
1252 return e
.m_key
== UINT_MAX
;
1255 template<typename T
> static bool is_empty (T
&e
) { return e
.m_key
== 0; }
1256 template<typename T
> static void mark_deleted (T
&e
) { e
.m_key
= UINT_MAX
; }
1257 template<typename T
> static void mark_empty (T
&e
) { e
.m_key
= 0; }
1260 static hash_map
<unsigned int, cgraph_node
*, profile_id_traits
> *
1261 cgraph_node_map
= 0;
1263 /* Returns true if node graph is initialized. This
1264 is used to test if profile_id has been created
1265 for cgraph_nodes. */
1268 coverage_node_map_initialized_p (void)
1270 return cgraph_node_map
!= 0;
1273 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1274 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1275 that the PROFILE_IDs was already assigned. */
1278 init_node_map (bool local
)
1280 struct cgraph_node
*n
;
1282 = new hash_map
<unsigned int, cgraph_node
*, profile_id_traits
>;
1284 FOR_EACH_DEFINED_FUNCTION (n
)
1285 if (n
->has_gimple_body_p ())
1290 n
->profile_id
= coverage_compute_profile_id (n
);
1291 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1295 fprintf (dump_file
, "Local profile-id %i conflict"
1296 " with nodes %s/%i %s/%i\n",
1302 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1305 else if (!n
->profile_id
)
1309 "Node %s/%i has no profile-id"
1310 " (profile feedback missing?)\n",
1315 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1319 "Node %s/%i has IP profile-id %i conflict. "
1327 cgraph_node_map
->put (n
->profile_id
, n
);
1331 /* Delete the CGRAPH_NODE_MAP. */
1336 delete cgraph_node_map
;
1339 /* Return cgraph node for function with pid */
1342 find_func_by_profile_id (int profile_id
)
1344 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1351 /* Perform sanity check on the indirect call target. Due to race conditions,
1352 false function target may be attributed to an indirect call site. If the
1353 call expression type mismatches with the target function's type, expand_call
1354 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1355 Returns true if TARGET is considered ok for call CALL_STMT. */
1358 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1361 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1364 locus
= gimple_location (call_stmt
);
1365 if (dump_enabled_p ())
1366 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1367 "Skipping target %s with mismatching types for icall\n",
1372 /* Do transformation
1374 if (actual_callee_address == address_of_most_common_function/method)
1381 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1382 int prob
, gcov_type count
, gcov_type all
)
1384 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1385 tree tmp0
, tmp1
, tmp
;
1386 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1387 tree optype
= build_pointer_type (void_type_node
);
1388 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1389 gimple_stmt_iterator gsi
;
1393 gimple_stmt_iterator psi
;
1395 cond_bb
= gimple_bb (icall_stmt
);
1396 gsi
= gsi_for_stmt (icall_stmt
);
1398 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1399 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1400 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1401 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1402 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1404 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1405 current_function_decl
));
1406 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1407 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1409 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1410 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1412 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1413 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1414 update_stmt (icall_stmt
);
1415 dcall_stmt
= gimple_copy (icall_stmt
);
1416 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1417 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1418 if ((dflags
& ECF_NORETURN
) != 0)
1419 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1420 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1423 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1424 e_cd
= split_block (cond_bb
, cond_stmt
);
1425 dcall_bb
= e_cd
->dest
;
1426 dcall_bb
->count
= count
;
1428 e_di
= split_block (dcall_bb
, dcall_stmt
);
1429 icall_bb
= e_di
->dest
;
1430 icall_bb
->count
= all
- count
;
1432 /* Do not disturb existing EH edges from the indirect call. */
1433 if (!stmt_ends_bb_p (icall_stmt
))
1434 e_ij
= split_block (icall_bb
, icall_stmt
);
1437 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1438 /* The indirect call might be noreturn. */
1441 e_ij
->probability
= REG_BR_PROB_BASE
;
1442 e_ij
->count
= all
- count
;
1443 e_ij
= single_pred_edge (split_edge (e_ij
));
1448 join_bb
= e_ij
->dest
;
1449 join_bb
->count
= all
;
1452 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1453 e_cd
->probability
= prob
;
1454 e_cd
->count
= count
;
1456 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1457 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1458 e_ci
->count
= all
- count
;
1464 if ((dflags
& ECF_NORETURN
) != 0)
1468 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1469 e_dj
->probability
= REG_BR_PROB_BASE
;
1470 e_dj
->count
= count
;
1472 e_ij
->count
= all
- count
;
1474 e_ij
->probability
= REG_BR_PROB_BASE
;
1477 /* Insert PHI node for the call result if necessary. */
1478 if (gimple_call_lhs (icall_stmt
)
1479 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1480 && (dflags
& ECF_NORETURN
) == 0)
1482 tree result
= gimple_call_lhs (icall_stmt
);
1483 gimple phi
= create_phi_node (result
, join_bb
);
1484 gimple_call_set_lhs (icall_stmt
,
1485 duplicate_ssa_name (result
, icall_stmt
));
1486 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1487 gimple_call_set_lhs (dcall_stmt
,
1488 duplicate_ssa_name (result
, dcall_stmt
));
1489 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1492 /* Build an EH edge for the direct call if necessary. */
1493 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1494 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1496 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1499 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1500 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1502 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1503 for (psi
= gsi_start_phis (e_eh
->dest
);
1504 !gsi_end_p (psi
); gsi_next (&psi
))
1506 gimple phi
= gsi_stmt (psi
);
1507 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1508 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1515 For every checked indirect/virtual call determine if most common pid of
1516 function/class method has probability more than 50%. If yes modify code of
1521 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1523 gimple stmt
= gsi_stmt (*gsi
);
1524 histogram_value histogram
;
1525 gcov_type val
, count
, all
, bb_all
;
1526 struct cgraph_node
*direct_call
;
1528 if (gimple_code (stmt
) != GIMPLE_CALL
)
1531 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1534 if (gimple_call_internal_p (stmt
))
1537 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1541 val
= histogram
->hvalue
.counters
[0];
1542 count
= histogram
->hvalue
.counters
[1];
1543 all
= histogram
->hvalue
.counters
[2];
1545 bb_all
= gimple_bb (stmt
)->count
;
1546 /* The order of CHECK_COUNTER calls is important -
1547 since check_counter can correct the third parameter
1548 and we want to make count <= all <= bb_all. */
1549 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1550 || check_counter (stmt
, "ic", &count
, &all
, all
))
1552 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1556 if (4 * count
<= 3 * all
)
1559 direct_call
= find_func_by_profile_id ((int)val
);
1561 if (direct_call
== NULL
)
1567 fprintf (dump_file
, "Indirect call -> direct call from other module");
1568 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1569 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1575 if (!check_ic_target (stmt
, direct_call
))
1579 fprintf (dump_file
, "Indirect call -> direct call ");
1580 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1581 fprintf (dump_file
, "=> ");
1582 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1583 fprintf (dump_file
, " transformation skipped because of type mismatch");
1584 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1586 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1592 fprintf (dump_file
, "Indirect call -> direct call ");
1593 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1594 fprintf (dump_file
, "=> ");
1595 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1596 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1597 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1598 fprintf (dump_file
, "hist->count %"PRId64
1599 " hist->all %"PRId64
"\n", count
, all
);
1605 /* Return true if the stringop CALL with FNDECL shall be profiled.
1606 SIZE_ARG be set to the argument index for the size of the string
1610 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1612 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1614 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1615 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1620 case BUILT_IN_MEMCPY
:
1621 case BUILT_IN_MEMPCPY
:
1623 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1624 INTEGER_TYPE
, VOID_TYPE
);
1625 case BUILT_IN_MEMSET
:
1627 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1628 INTEGER_TYPE
, VOID_TYPE
);
1629 case BUILT_IN_BZERO
:
1631 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1638 /* Convert stringop (..., vcall_size)
1640 if (vcall_size == icall_size)
1641 stringop (..., icall_size);
1643 stringop (..., vcall_size);
1644 assuming we'll propagate a true constant into ICALL_SIZE later. */
1647 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1648 gcov_type count
, gcov_type all
)
1650 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1651 tree tmp0
, tmp1
, vcall_size
, optype
;
1652 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1653 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1654 gimple_stmt_iterator gsi
;
1658 fndecl
= gimple_call_fndecl (vcall_stmt
);
1659 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1662 cond_bb
= gimple_bb (vcall_stmt
);
1663 gsi
= gsi_for_stmt (vcall_stmt
);
1665 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1666 optype
= TREE_TYPE (vcall_size
);
1668 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1669 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1670 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1671 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1673 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1674 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1676 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1677 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1679 gimple_set_vdef (vcall_stmt
, NULL
);
1680 gimple_set_vuse (vcall_stmt
, NULL
);
1681 update_stmt (vcall_stmt
);
1682 icall_stmt
= gimple_copy (vcall_stmt
);
1683 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1684 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1687 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1688 e_ci
= split_block (cond_bb
, cond_stmt
);
1689 icall_bb
= e_ci
->dest
;
1690 icall_bb
->count
= count
;
1692 e_iv
= split_block (icall_bb
, icall_stmt
);
1693 vcall_bb
= e_iv
->dest
;
1694 vcall_bb
->count
= all
- count
;
1696 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1697 join_bb
= e_vj
->dest
;
1698 join_bb
->count
= all
;
1700 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1701 e_ci
->probability
= prob
;
1702 e_ci
->count
= count
;
1704 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1705 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1706 e_cv
->count
= all
- count
;
1710 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1711 e_ij
->probability
= REG_BR_PROB_BASE
;
1712 e_ij
->count
= count
;
1714 e_vj
->probability
= REG_BR_PROB_BASE
;
1715 e_vj
->count
= all
- count
;
1717 /* Insert PHI node for the call result if necessary. */
1718 if (gimple_call_lhs (vcall_stmt
)
1719 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1721 tree result
= gimple_call_lhs (vcall_stmt
);
1722 gimple phi
= create_phi_node (result
, join_bb
);
1723 gimple_call_set_lhs (vcall_stmt
,
1724 duplicate_ssa_name (result
, vcall_stmt
));
1725 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1726 gimple_call_set_lhs (icall_stmt
,
1727 duplicate_ssa_name (result
, icall_stmt
));
1728 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1731 /* Because these are all string op builtins, they're all nothrow. */
1732 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1733 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1736 /* Find values inside STMT for that we want to measure histograms for
1737 division/modulo optimization. */
1739 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1741 gimple stmt
= gsi_stmt (*gsi
);
1744 enum built_in_function fcode
;
1745 histogram_value histogram
;
1746 gcov_type count
, all
, val
;
1748 unsigned int dest_align
, src_align
;
1753 if (gimple_code (stmt
) != GIMPLE_CALL
)
1755 fndecl
= gimple_call_fndecl (stmt
);
1758 fcode
= DECL_FUNCTION_CODE (fndecl
);
1759 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1762 blck_size
= gimple_call_arg (stmt
, size_arg
);
1763 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1766 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1769 val
= histogram
->hvalue
.counters
[0];
1770 count
= histogram
->hvalue
.counters
[1];
1771 all
= histogram
->hvalue
.counters
[2];
1772 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1773 /* We require that count is at least half of all; this means
1774 that for the transformation to fire the value must be constant
1775 at least 80% of time. */
1776 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1778 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1781 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1784 dest
= gimple_call_arg (stmt
, 0);
1785 dest_align
= get_pointer_alignment (dest
);
1788 case BUILT_IN_MEMCPY
:
1789 case BUILT_IN_MEMPCPY
:
1790 src
= gimple_call_arg (stmt
, 1);
1791 src_align
= get_pointer_alignment (src
);
1792 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1795 case BUILT_IN_MEMSET
:
1796 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1797 gimple_call_arg (stmt
, 1),
1801 case BUILT_IN_BZERO
:
1802 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1810 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1811 tree_val
= build_int_cst (get_gcov_type (), val
);
1815 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1816 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1818 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1819 TYPE_PRECISION (get_gcov_type ()), false));
1824 fprintf (dump_file
, "Single value %i stringop transformation on ",
1826 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1828 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1834 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1835 HOST_WIDE_INT
*expected_size
)
1837 histogram_value histogram
;
1838 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1840 *expected_size
= -1;
1841 else if (!histogram
->hvalue
.counters
[1])
1843 *expected_size
= -1;
1844 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1849 size
= ((histogram
->hvalue
.counters
[0]
1850 + histogram
->hvalue
.counters
[1] / 2)
1851 / histogram
->hvalue
.counters
[1]);
1852 /* Even if we can hold bigger value in SIZE, INT_MAX
1853 is safe "infinity" for code generation strategies. */
1856 *expected_size
= size
;
1857 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1859 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1861 *expected_align
= 0;
1862 else if (!histogram
->hvalue
.counters
[0])
1864 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1865 *expected_align
= 0;
1872 count
= histogram
->hvalue
.counters
[0];
1874 while (!(count
& alignment
)
1875 && (alignment
* 2 * BITS_PER_UNIT
))
1877 *expected_align
= alignment
* BITS_PER_UNIT
;
1878 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1883 /* Find values inside STMT for that we want to measure histograms for
1884 division/modulo optimization. */
1886 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1888 tree lhs
, divisor
, op0
, type
;
1889 histogram_value hist
;
1891 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1894 lhs
= gimple_assign_lhs (stmt
);
1895 type
= TREE_TYPE (lhs
);
1896 if (!INTEGRAL_TYPE_P (type
))
1899 switch (gimple_assign_rhs_code (stmt
))
1901 case TRUNC_DIV_EXPR
:
1902 case TRUNC_MOD_EXPR
:
1903 divisor
= gimple_assign_rhs2 (stmt
);
1904 op0
= gimple_assign_rhs1 (stmt
);
1906 values
->reserve (3);
1908 if (TREE_CODE (divisor
) == SSA_NAME
)
1909 /* Check for the case where the divisor is the same value most
1911 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1912 HIST_TYPE_SINGLE_VALUE
,
1915 /* For mod, check whether it is not often a noop (or replaceable by
1916 a few subtractions). */
1917 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1918 && TYPE_UNSIGNED (type
))
1921 /* Check for a special case where the divisor is power of 2. */
1922 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1926 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1927 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1929 hist
->hdata
.intvl
.int_start
= 0;
1930 hist
->hdata
.intvl
.steps
= 2;
1931 values
->quick_push (hist
);
1940 /* Find calls inside STMT for that we want to measure histograms for
1941 indirect/virtual call optimization. */
1944 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1948 if (gimple_code (stmt
) != GIMPLE_CALL
1949 || gimple_call_internal_p (stmt
)
1950 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1953 callee
= gimple_call_fn (stmt
);
1955 values
->reserve (3);
1957 values
->quick_push (gimple_alloc_histogram_value (
1959 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1960 HIST_TYPE_INDIR_CALL_TOPN
:
1961 HIST_TYPE_INDIR_CALL
,
1967 /* Find values inside STMT for that we want to measure histograms for
1968 string operations. */
1970 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1977 if (gimple_code (stmt
) != GIMPLE_CALL
)
1979 fndecl
= gimple_call_fndecl (stmt
);
1983 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1986 dest
= gimple_call_arg (stmt
, 0);
1987 blck_size
= gimple_call_arg (stmt
, size_arg
);
1989 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1991 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1992 HIST_TYPE_SINGLE_VALUE
,
1994 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1997 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1998 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
2002 /* Find values inside STMT for that we want to measure histograms and adds
2003 them to list VALUES. */
2006 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
2008 gimple_divmod_values_to_profile (stmt
, values
);
2009 gimple_stringops_values_to_profile (stmt
, values
);
2010 gimple_indirect_call_to_profile (stmt
, values
);
2014 gimple_find_values_to_profile (histogram_values
*values
)
2017 gimple_stmt_iterator gsi
;
2019 histogram_value hist
= NULL
;
2022 FOR_EACH_BB_FN (bb
, cfun
)
2023 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2024 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2026 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2028 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2032 case HIST_TYPE_INTERVAL
:
2033 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2036 case HIST_TYPE_POW2
:
2037 hist
->n_counters
= 2;
2040 case HIST_TYPE_SINGLE_VALUE
:
2041 hist
->n_counters
= 3;
2044 case HIST_TYPE_CONST_DELTA
:
2045 hist
->n_counters
= 4;
2048 case HIST_TYPE_INDIR_CALL
:
2049 hist
->n_counters
= 3;
2052 case HIST_TYPE_TIME_PROFILE
:
2053 hist
->n_counters
= 1;
2056 case HIST_TYPE_AVERAGE
:
2057 hist
->n_counters
= 2;
2061 hist
->n_counters
= 1;
2064 case HIST_TYPE_INDIR_CALL_TOPN
:
2065 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2073 fprintf (dump_file
, "Stmt ");
2074 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2075 dump_histogram_value (dump_file
, hist
);