1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2015 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"
37 #include "data-streamer.h"
38 #include "diagnostic.h"
40 #include "fold-const.h"
41 #include "tree-nested.h"
49 #include "value-prof.h"
50 #include "internal-fn.h"
53 #include "gimple-iterator.h"
55 #include "gimple-pretty-print.h"
60 #include "tree-chkp.h"
62 /* In this file value profile based optimizations are placed. Currently the
63 following optimizations are implemented (for more detailed descriptions
64 see comments at value_profile_transformations):
66 1) Division/modulo specialization. Provided that we can determine that the
67 operands of the division have some special properties, we may use it to
68 produce more effective code.
70 2) Indirect/virtual call specialization. If we can determine most
71 common function callee in indirect/virtual call. We can use this
72 information to improve code effectiveness (especially info for
75 3) Speculative prefetching. If we are able to determine that the difference
76 between addresses accessed by a memory reference is usually constant, we
77 may add the prefetch instructions.
78 FIXME: This transformation was removed together with RTL based value
82 Value profiling internals
83 ==========================
85 Every value profiling transformation starts with defining what values
86 to profile. There are different histogram types (see HIST_TYPE_* in
87 value-prof.h) and each transformation can request one or more histogram
88 types per GIMPLE statement. The function gimple_find_values_to_profile()
89 collects the values to profile in a vec, and adds the number of counters
90 required for the different histogram types.
92 For a -fprofile-generate run, the statements for which values should be
93 recorded, are instrumented in instrument_values(). The instrumentation
94 is done by helper functions that can be found in tree-profile.c, where
95 new types of histograms can be added if necessary.
97 After a -fprofile-use, the value profiling data is read back in by
98 compute_value_histograms() that translates the collected data to
99 histograms and attaches them to the profiled statements via
100 gimple_add_histogram_value(). Histograms are stored in a hash table
101 that is attached to every intrumented function, see VALUE_HISTOGRAMS
104 The value-profile transformations driver is the function
105 gimple_value_profile_transformations(). It traverses all statements in
106 the to-be-transformed function, and looks for statements with one or
107 more histograms attached to it. If a statement has histograms, the
108 transformation functions are called on the statement.
110 Limitations / FIXME / TODO:
111 * Only one histogram of each type can be associated with a statement.
112 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
113 (This type of histogram was originally used to implement a form of
114 stride profiling based speculative prefetching to improve SPEC2000
115 scores for memory-bound benchmarks, mcf and equake. However, this
116 was an RTL value-profiling transformation, and those have all been
118 * Some value profile transformations are done in builtins.c (?!)
119 * Updating of histograms needs some TLC.
120 * The value profiling code could be used to record analysis results
121 from non-profiling (e.g. VRP).
122 * Adding new profilers should be simplified, starting with a cleanup
123 of what-happens-where andwith making gimple_find_values_to_profile
124 and gimple_value_profile_transformations table-driven, perhaps...
127 static tree
gimple_divmod_fixed_value (gassign
*, tree
, int, gcov_type
,
129 static tree
gimple_mod_pow2 (gassign
*, int, gcov_type
, gcov_type
);
130 static tree
gimple_mod_subtract (gassign
*, int, int, int, gcov_type
,
131 gcov_type
, gcov_type
);
132 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
133 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
134 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
135 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
136 static bool gimple_ic_transform (gimple_stmt_iterator
*);
138 /* Allocate histogram value. */
141 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
142 enum hist_type type
, gimple
*stmt
, tree value
)
144 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
145 hist
->hvalue
.value
= value
;
146 hist
->hvalue
.stmt
= stmt
;
151 /* Hash value for histogram. */
154 histogram_hash (const void *x
)
156 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
159 /* Return nonzero if statement for histogram_value X is Y. */
162 histogram_eq (const void *x
, const void *y
)
164 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const gimple
*) y
;
167 /* Set histogram for STMT. */
170 set_histogram_value (struct function
*fun
, gimple
*stmt
, histogram_value hist
)
173 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
175 if (!VALUE_HISTOGRAMS (fun
))
176 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
178 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
179 htab_hash_pointer (stmt
),
180 hist
? INSERT
: NO_INSERT
);
184 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
190 /* Get histogram list for STMT. */
193 gimple_histogram_value (struct function
*fun
, gimple
*stmt
)
195 if (!VALUE_HISTOGRAMS (fun
))
197 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
198 htab_hash_pointer (stmt
));
201 /* Add histogram for STMT. */
204 gimple_add_histogram_value (struct function
*fun
, gimple
*stmt
,
205 histogram_value hist
)
207 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
208 set_histogram_value (fun
, stmt
, hist
);
212 /* Remove histogram HIST from STMT's histogram list. */
215 gimple_remove_histogram_value (struct function
*fun
, gimple
*stmt
,
216 histogram_value hist
)
218 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
221 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
225 while (hist2
->hvalue
.next
!= hist
)
226 hist2
= hist2
->hvalue
.next
;
227 hist2
->hvalue
.next
= hist
->hvalue
.next
;
229 free (hist
->hvalue
.counters
);
231 memset (hist
, 0xab, sizeof (*hist
));
235 /* Lookup histogram of type TYPE in the STMT. */
238 gimple_histogram_value_of_type (struct function
*fun
, gimple
*stmt
,
241 histogram_value hist
;
242 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
243 hist
= hist
->hvalue
.next
)
244 if (hist
->type
== type
)
249 /* Dump information about HIST to DUMP_FILE. */
252 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
256 case HIST_TYPE_INTERVAL
:
257 fprintf (dump_file
, "Interval counter range %d -- %d",
258 hist
->hdata
.intvl
.int_start
,
259 (hist
->hdata
.intvl
.int_start
260 + hist
->hdata
.intvl
.steps
- 1));
261 if (hist
->hvalue
.counters
)
264 fprintf (dump_file
, " [");
265 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
266 fprintf (dump_file
, " %d:%" PRId64
,
267 hist
->hdata
.intvl
.int_start
+ i
,
268 (int64_t) hist
->hvalue
.counters
[i
]);
269 fprintf (dump_file
, " ] outside range:%" PRId64
,
270 (int64_t) hist
->hvalue
.counters
[i
]);
272 fprintf (dump_file
, ".\n");
276 fprintf (dump_file
, "Pow2 counter ");
277 if (hist
->hvalue
.counters
)
279 fprintf (dump_file
, "pow2:%" PRId64
281 (int64_t) hist
->hvalue
.counters
[0],
282 (int64_t) hist
->hvalue
.counters
[1]);
284 fprintf (dump_file
, ".\n");
287 case HIST_TYPE_SINGLE_VALUE
:
288 fprintf (dump_file
, "Single value ");
289 if (hist
->hvalue
.counters
)
291 fprintf (dump_file
, "value:%" PRId64
294 (int64_t) hist
->hvalue
.counters
[0],
295 (int64_t) hist
->hvalue
.counters
[1],
296 (int64_t) hist
->hvalue
.counters
[2]);
298 fprintf (dump_file
, ".\n");
301 case HIST_TYPE_AVERAGE
:
302 fprintf (dump_file
, "Average value ");
303 if (hist
->hvalue
.counters
)
305 fprintf (dump_file
, "sum:%" PRId64
307 (int64_t) hist
->hvalue
.counters
[0],
308 (int64_t) hist
->hvalue
.counters
[1]);
310 fprintf (dump_file
, ".\n");
314 fprintf (dump_file
, "IOR value ");
315 if (hist
->hvalue
.counters
)
317 fprintf (dump_file
, "ior:%" PRId64
,
318 (int64_t) hist
->hvalue
.counters
[0]);
320 fprintf (dump_file
, ".\n");
323 case HIST_TYPE_CONST_DELTA
:
324 fprintf (dump_file
, "Constant delta ");
325 if (hist
->hvalue
.counters
)
327 fprintf (dump_file
, "value:%" PRId64
330 (int64_t) hist
->hvalue
.counters
[0],
331 (int64_t) hist
->hvalue
.counters
[1],
332 (int64_t) hist
->hvalue
.counters
[2]);
334 fprintf (dump_file
, ".\n");
336 case HIST_TYPE_INDIR_CALL
:
337 fprintf (dump_file
, "Indirect call ");
338 if (hist
->hvalue
.counters
)
340 fprintf (dump_file
, "value:%" PRId64
343 (int64_t) hist
->hvalue
.counters
[0],
344 (int64_t) hist
->hvalue
.counters
[1],
345 (int64_t) hist
->hvalue
.counters
[2]);
347 fprintf (dump_file
, ".\n");
349 case HIST_TYPE_TIME_PROFILE
:
350 fprintf (dump_file
, "Time profile ");
351 if (hist
->hvalue
.counters
)
353 fprintf (dump_file
, "time:%" PRId64
,
354 (int64_t) hist
->hvalue
.counters
[0]);
356 fprintf (dump_file
, ".\n");
358 case HIST_TYPE_INDIR_CALL_TOPN
:
359 fprintf (dump_file
, "Indirect call topn ");
360 if (hist
->hvalue
.counters
)
364 fprintf (dump_file
, "accu:%" PRId64
, hist
->hvalue
.counters
[0]);
365 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
367 fprintf (dump_file
, " target:%" PRId64
" value:%" PRId64
,
368 (int64_t) hist
->hvalue
.counters
[i
],
369 (int64_t) hist
->hvalue
.counters
[i
+1]);
372 fprintf (dump_file
, ".\n");
379 /* Dump information about HIST to DUMP_FILE. */
382 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
387 bp
= bitpack_create (ob
->main_stream
);
388 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
389 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
390 streamer_write_bitpack (&bp
);
393 case HIST_TYPE_INTERVAL
:
394 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
395 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
400 for (i
= 0; i
< hist
->n_counters
; i
++)
401 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
402 if (hist
->hvalue
.next
)
403 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
406 /* Dump information about HIST to DUMP_FILE. */
409 stream_in_histogram_value (struct lto_input_block
*ib
, gimple
*stmt
)
412 unsigned int ncounters
= 0;
415 histogram_value new_val
;
417 histogram_value
*next_p
= NULL
;
421 bp
= streamer_read_bitpack (ib
);
422 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
423 next
= bp_unpack_value (&bp
, 1);
424 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
427 case HIST_TYPE_INTERVAL
:
428 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
429 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
430 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
434 case HIST_TYPE_AVERAGE
:
438 case HIST_TYPE_SINGLE_VALUE
:
439 case HIST_TYPE_INDIR_CALL
:
443 case HIST_TYPE_CONST_DELTA
:
448 case HIST_TYPE_TIME_PROFILE
:
452 case HIST_TYPE_INDIR_CALL_TOPN
:
453 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
459 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
460 new_val
->n_counters
= ncounters
;
461 for (i
= 0; i
< ncounters
; i
++)
462 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
464 gimple_add_histogram_value (cfun
, stmt
, new_val
);
467 next_p
= &new_val
->hvalue
.next
;
472 /* Dump all histograms attached to STMT to DUMP_FILE. */
475 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple
*stmt
)
477 histogram_value hist
;
478 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
479 dump_histogram_value (dump_file
, hist
);
482 /* Remove all histograms associated with STMT. */
485 gimple_remove_stmt_histograms (struct function
*fun
, gimple
*stmt
)
488 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
489 gimple_remove_histogram_value (fun
, stmt
, val
);
492 /* Duplicate all histograms associates with OSTMT to STMT. */
495 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple
*stmt
,
496 struct function
*ofun
, gimple
*ostmt
)
499 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
501 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
502 memcpy (new_val
, val
, sizeof (*val
));
503 new_val
->hvalue
.stmt
= stmt
;
504 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
505 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
506 gimple_add_histogram_value (fun
, stmt
, new_val
);
510 /* Move all histograms associated with OSTMT to STMT. */
513 gimple_move_stmt_histograms (struct function
*fun
, gimple
*stmt
, gimple
*ostmt
)
515 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
518 /* The following three statements can't be reordered,
519 because histogram hashtab relies on stmt field value
520 for finding the exact slot. */
521 set_histogram_value (fun
, ostmt
, NULL
);
522 for (; val
!= NULL
; val
= val
->hvalue
.next
)
523 val
->hvalue
.stmt
= stmt
;
524 set_histogram_value (fun
, stmt
, val
);
528 static bool error_found
= false;
530 /* Helper function for verify_histograms. For each histogram reachable via htab
531 walk verify that it was reached via statement walk. */
534 visit_hist (void **slot
, void *data
)
536 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
537 histogram_value hist
= *(histogram_value
*) slot
;
539 if (!visited
->contains (hist
)
540 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
542 error ("dead histogram");
543 dump_histogram_value (stderr
, hist
);
544 debug_gimple_stmt (hist
->hvalue
.stmt
);
550 /* Verify sanity of the histograms. */
553 verify_histograms (void)
556 gimple_stmt_iterator gsi
;
557 histogram_value hist
;
560 hash_set
<histogram_value
> visited_hists
;
561 FOR_EACH_BB_FN (bb
, cfun
)
562 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
564 gimple
*stmt
= gsi_stmt (gsi
);
566 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
567 hist
= hist
->hvalue
.next
)
569 if (hist
->hvalue
.stmt
!= stmt
)
571 error ("Histogram value statement does not correspond to "
572 "the statement it is associated with");
573 debug_gimple_stmt (stmt
);
574 dump_histogram_value (stderr
, hist
);
577 visited_hists
.add (hist
);
580 if (VALUE_HISTOGRAMS (cfun
))
581 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
583 internal_error ("verify_histograms failed");
586 /* Helper function for verify_histograms. For each histogram reachable via htab
587 walk verify that it was reached via statement walk. */
590 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
592 histogram_value hist
= *(histogram_value
*) slot
;
593 free (hist
->hvalue
.counters
);
595 memset (hist
, 0xab, sizeof (*hist
));
601 free_histograms (struct function
*fn
)
603 if (VALUE_HISTOGRAMS (fn
))
605 htab_traverse (VALUE_HISTOGRAMS (fn
), free_hist
, NULL
);
606 htab_delete (VALUE_HISTOGRAMS (fn
));
607 VALUE_HISTOGRAMS (fn
) = NULL
;
611 /* The overall number of invocations of the counter should match
612 execution count of basic block. Report it as error rather than
613 internal error as it might mean that user has misused the profile
617 check_counter (gimple
*stmt
, const char * name
,
618 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
620 if (*all
!= bb_count
|| *count
> *all
)
623 locus
= (stmt
!= NULL
)
624 ? gimple_location (stmt
)
625 : DECL_SOURCE_LOCATION (current_function_decl
);
626 if (flag_profile_correction
)
628 if (dump_enabled_p ())
629 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
630 "correcting inconsistent value profile: %s "
631 "profiler overall count (%d) does not match BB "
632 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
640 error_at (locus
, "corrupted value profile: %s "
641 "profile counter (%d out of %d) inconsistent with "
642 "basic-block count (%d)",
654 /* GIMPLE based transformations. */
657 gimple_value_profile_transformations (void)
660 gimple_stmt_iterator gsi
;
661 bool changed
= false;
662 FOR_EACH_BB_FN (bb
, cfun
)
664 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
666 gimple
*stmt
= gsi_stmt (gsi
);
667 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
673 fprintf (dump_file
, "Trying transformations on stmt ");
674 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
675 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
678 /* Transformations: */
679 /* The order of things in this conditional controls which
680 transformation is used when more than one is applicable. */
681 /* It is expected that any code added by the transformations
682 will be added before the current statement, and that the
683 current statement remain valid (although possibly
684 modified) upon return. */
685 if (gimple_mod_subtract_transform (&gsi
)
686 || gimple_divmod_fixed_value_transform (&gsi
)
687 || gimple_mod_pow2_value_transform (&gsi
)
688 || gimple_stringops_transform (&gsi
)
689 || gimple_ic_transform (&gsi
))
691 stmt
= gsi_stmt (gsi
);
693 /* Original statement may no longer be in the same block. */
694 if (bb
!= gimple_bb (stmt
))
696 bb
= gimple_bb (stmt
);
697 gsi
= gsi_for_stmt (stmt
);
711 /* Generate code for transformation 1 (with parent gimple assignment
712 STMT and probability of taking the optimal path PROB, which is
713 equivalent to COUNT/ALL within roundoff error). This generates the
714 result into a temp and returns the temp; it does not replace or
715 alter the original STMT. */
718 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, int prob
,
719 gcov_type count
, gcov_type all
)
721 gassign
*stmt1
, *stmt2
;
723 tree tmp0
, tmp1
, tmp2
;
724 gimple
*bb1end
, *bb2end
, *bb3end
;
725 basic_block bb
, bb2
, bb3
, bb4
;
726 tree optype
, op1
, op2
;
727 edge e12
, e13
, e23
, e24
, e34
;
728 gimple_stmt_iterator gsi
;
730 gcc_assert (is_gimple_assign (stmt
)
731 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
732 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
734 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
735 op1
= gimple_assign_rhs1 (stmt
);
736 op2
= gimple_assign_rhs2 (stmt
);
738 bb
= gimple_bb (stmt
);
739 gsi
= gsi_for_stmt (stmt
);
741 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
742 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
743 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
744 stmt2
= gimple_build_assign (tmp1
, op2
);
745 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
746 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
747 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
748 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
751 tmp2
= create_tmp_reg (optype
, "PROF");
752 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
753 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
756 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
757 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
761 /* Edge e23 connects bb2 to bb3, etc. */
762 e12
= split_block (bb
, bb1end
);
765 e23
= split_block (bb2
, bb2end
);
767 bb3
->count
= all
- count
;
768 e34
= split_block (bb3
, bb3end
);
772 e12
->flags
&= ~EDGE_FALLTHRU
;
773 e12
->flags
|= EDGE_FALSE_VALUE
;
774 e12
->probability
= prob
;
777 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
778 e13
->probability
= REG_BR_PROB_BASE
- prob
;
779 e13
->count
= all
- count
;
783 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
784 e24
->probability
= REG_BR_PROB_BASE
;
787 e34
->probability
= REG_BR_PROB_BASE
;
788 e34
->count
= all
- count
;
793 /* Do transform 1) on INSN if applicable. */
796 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
798 histogram_value histogram
;
800 gcov_type val
, count
, all
;
801 tree result
, value
, tree_val
;
805 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
809 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
812 code
= gimple_assign_rhs_code (stmt
);
814 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
817 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
818 HIST_TYPE_SINGLE_VALUE
);
822 value
= histogram
->hvalue
.value
;
823 val
= histogram
->hvalue
.counters
[0];
824 count
= histogram
->hvalue
.counters
[1];
825 all
= histogram
->hvalue
.counters
[2];
826 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
828 /* We require that count is at least half of all; this means
829 that for the transformation to fire the value must be constant
830 at least 50% of time (and 75% gives the guarantee of usage). */
831 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
833 || optimize_bb_for_size_p (gimple_bb (stmt
)))
836 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
839 /* Compute probability of taking the optimal path. */
841 prob
= GCOV_COMPUTE_SCALE (count
, all
);
845 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
846 tree_val
= build_int_cst (get_gcov_type (), val
);
850 a
[0] = (unsigned HOST_WIDE_INT
) val
;
851 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
853 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
854 TYPE_PRECISION (get_gcov_type ()), false));
856 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
860 fprintf (dump_file
, "Div/mod by constant ");
861 print_generic_expr (dump_file
, value
, TDF_SLIM
);
862 fprintf (dump_file
, "=");
863 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
864 fprintf (dump_file
, " transformation on insn ");
865 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
868 gimple_assign_set_rhs_from_tree (si
, result
);
869 update_stmt (gsi_stmt (*si
));
874 /* Generate code for transformation 2 (with parent gimple assign STMT and
875 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
876 within roundoff error). This generates the result into a temp and returns
877 the temp; it does not replace or alter the original STMT. */
880 gimple_mod_pow2 (gassign
*stmt
, int prob
, gcov_type count
, gcov_type all
)
882 gassign
*stmt1
, *stmt2
, *stmt3
;
885 gimple
*bb1end
, *bb2end
, *bb3end
;
886 basic_block bb
, bb2
, bb3
, bb4
;
887 tree optype
, op1
, op2
;
888 edge e12
, e13
, e23
, e24
, e34
;
889 gimple_stmt_iterator gsi
;
892 gcc_assert (is_gimple_assign (stmt
)
893 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
895 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
896 op1
= gimple_assign_rhs1 (stmt
);
897 op2
= gimple_assign_rhs2 (stmt
);
899 bb
= gimple_bb (stmt
);
900 gsi
= gsi_for_stmt (stmt
);
902 result
= create_tmp_reg (optype
, "PROF");
903 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
904 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
905 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
906 build_int_cst (optype
, -1));
907 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
908 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
909 NULL_TREE
, NULL_TREE
);
910 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
911 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
912 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
915 /* tmp2 == op2-1 inherited from previous block. */
916 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
917 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
920 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
922 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
926 /* Edge e23 connects bb2 to bb3, etc. */
927 e12
= split_block (bb
, bb1end
);
930 e23
= split_block (bb2
, bb2end
);
932 bb3
->count
= all
- count
;
933 e34
= split_block (bb3
, bb3end
);
937 e12
->flags
&= ~EDGE_FALLTHRU
;
938 e12
->flags
|= EDGE_FALSE_VALUE
;
939 e12
->probability
= prob
;
942 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
943 e13
->probability
= REG_BR_PROB_BASE
- prob
;
944 e13
->count
= all
- count
;
948 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
949 e24
->probability
= REG_BR_PROB_BASE
;
952 e34
->probability
= REG_BR_PROB_BASE
;
953 e34
->count
= all
- count
;
958 /* Do transform 2) on INSN if applicable. */
961 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
963 histogram_value histogram
;
965 gcov_type count
, wrong_values
, all
;
966 tree lhs_type
, result
, value
;
970 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
974 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
975 if (!INTEGRAL_TYPE_P (lhs_type
))
978 code
= gimple_assign_rhs_code (stmt
);
980 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
983 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
987 value
= histogram
->hvalue
.value
;
988 wrong_values
= histogram
->hvalue
.counters
[0];
989 count
= histogram
->hvalue
.counters
[1];
991 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
993 /* We require that we hit a power of 2 at least half of all evaluations. */
994 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
995 || count
< wrong_values
996 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1001 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
1002 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1005 /* Compute probability of taking the optimal path. */
1006 all
= count
+ wrong_values
;
1008 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1012 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1016 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1018 gimple_assign_set_rhs_from_tree (si
, result
);
1019 update_stmt (gsi_stmt (*si
));
1024 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1025 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1026 supported and this is built into this interface. The probabilities of taking
1027 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1028 COUNT2/ALL respectively within roundoff error). This generates the
1029 result into a temp and returns the temp; it does not replace or alter
1030 the original STMT. */
1031 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1034 gimple_mod_subtract (gassign
*stmt
, int prob1
, int prob2
, int ncounts
,
1035 gcov_type count1
, gcov_type count2
, gcov_type all
)
1041 gimple
*bb1end
, *bb2end
= NULL
, *bb3end
;
1042 basic_block bb
, bb2
, bb3
, bb4
;
1043 tree optype
, op1
, op2
;
1044 edge e12
, e23
= 0, e24
, e34
, e14
;
1045 gimple_stmt_iterator gsi
;
1048 gcc_assert (is_gimple_assign (stmt
)
1049 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1051 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1052 op1
= gimple_assign_rhs1 (stmt
);
1053 op2
= gimple_assign_rhs2 (stmt
);
1055 bb
= gimple_bb (stmt
);
1056 gsi
= gsi_for_stmt (stmt
);
1058 result
= create_tmp_reg (optype
, "PROF");
1059 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1060 stmt1
= gimple_build_assign (result
, op1
);
1061 stmt2
= gimple_build_assign (tmp1
, op2
);
1062 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1063 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1064 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1065 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1068 if (ncounts
) /* Assumed to be 0 or 1 */
1070 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1071 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1072 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1073 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1077 /* Fallback case. */
1078 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1080 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1084 /* Edge e23 connects bb2 to bb3, etc. */
1085 /* However block 3 is optional; if it is not there, references
1086 to 3 really refer to block 2. */
1087 e12
= split_block (bb
, bb1end
);
1089 bb2
->count
= all
- count1
;
1091 if (ncounts
) /* Assumed to be 0 or 1. */
1093 e23
= split_block (bb2
, bb2end
);
1095 bb3
->count
= all
- count1
- count2
;
1098 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1102 e12
->flags
&= ~EDGE_FALLTHRU
;
1103 e12
->flags
|= EDGE_FALSE_VALUE
;
1104 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1105 e12
->count
= all
- count1
;
1107 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1108 e14
->probability
= prob1
;
1109 e14
->count
= count1
;
1111 if (ncounts
) /* Assumed to be 0 or 1. */
1113 e23
->flags
&= ~EDGE_FALLTHRU
;
1114 e23
->flags
|= EDGE_FALSE_VALUE
;
1115 e23
->count
= all
- count1
- count2
;
1116 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1118 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1119 e24
->probability
= prob2
;
1120 e24
->count
= count2
;
1123 e34
->probability
= REG_BR_PROB_BASE
;
1124 e34
->count
= all
- count1
- count2
;
1129 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1132 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1134 histogram_value histogram
;
1135 enum tree_code code
;
1136 gcov_type count
, wrong_values
, all
;
1137 tree lhs_type
, result
;
1138 gcov_type prob1
, prob2
;
1139 unsigned int i
, steps
;
1140 gcov_type count1
, count2
;
1142 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1146 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1147 if (!INTEGRAL_TYPE_P (lhs_type
))
1150 code
= gimple_assign_rhs_code (stmt
);
1152 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1155 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1161 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1162 all
+= histogram
->hvalue
.counters
[i
];
1164 wrong_values
+= histogram
->hvalue
.counters
[i
];
1165 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1166 steps
= histogram
->hdata
.intvl
.steps
;
1167 all
+= wrong_values
;
1168 count1
= histogram
->hvalue
.counters
[0];
1169 count2
= histogram
->hvalue
.counters
[1];
1171 /* Compute probability of taking the optimal path. */
1172 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1174 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1178 if (flag_profile_correction
&& count1
+ count2
> all
)
1179 all
= count1
+ count2
;
1181 gcc_assert (count1
+ count2
<= all
);
1183 /* We require that we use just subtractions in at least 50% of all
1186 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1188 count
+= histogram
->hvalue
.counters
[i
];
1189 if (count
* 2 >= all
)
1193 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1196 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1199 fprintf (dump_file
, "Mod subtract transformation on insn ");
1200 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1203 /* Compute probability of taking the optimal path(s). */
1206 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1207 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1214 /* In practice, "steps" is always 2. This interface reflects this,
1215 and will need to be changed if "steps" can change. */
1216 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1218 gimple_assign_set_rhs_from_tree (si
, result
);
1219 update_stmt (gsi_stmt (*si
));
1224 typedef int_hash
<unsigned int, 0, UINT_MAX
> profile_id_hash
;
1226 static hash_map
<profile_id_hash
, cgraph_node
*> *cgraph_node_map
= 0;
1228 /* Returns true if node graph is initialized. This
1229 is used to test if profile_id has been created
1230 for cgraph_nodes. */
1233 coverage_node_map_initialized_p (void)
1235 return cgraph_node_map
!= 0;
1238 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1239 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1240 that the PROFILE_IDs was already assigned. */
1243 init_node_map (bool local
)
1245 struct cgraph_node
*n
;
1246 cgraph_node_map
= new hash_map
<profile_id_hash
, cgraph_node
*>;
1248 FOR_EACH_DEFINED_FUNCTION (n
)
1249 if (n
->has_gimple_body_p ())
1254 n
->profile_id
= coverage_compute_profile_id (n
);
1255 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1259 fprintf (dump_file
, "Local profile-id %i conflict"
1260 " with nodes %s/%i %s/%i\n",
1266 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1269 else if (!n
->profile_id
)
1273 "Node %s/%i has no profile-id"
1274 " (profile feedback missing?)\n",
1279 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1283 "Node %s/%i has IP profile-id %i conflict. "
1291 cgraph_node_map
->put (n
->profile_id
, n
);
1295 /* Delete the CGRAPH_NODE_MAP. */
1300 delete cgraph_node_map
;
1303 /* Return cgraph node for function with pid */
1306 find_func_by_profile_id (int profile_id
)
1308 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1315 /* Perform sanity check on the indirect call target. Due to race conditions,
1316 false function target may be attributed to an indirect call site. If the
1317 call expression type mismatches with the target function's type, expand_call
1318 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1319 Returns true if TARGET is considered ok for call CALL_STMT. */
1322 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1325 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1328 locus
= gimple_location (call_stmt
);
1329 if (dump_enabled_p ())
1330 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1331 "Skipping target %s with mismatching types for icall\n",
1336 /* Do transformation
1338 if (actual_callee_address == address_of_most_common_function/method)
1345 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1346 int prob
, gcov_type count
, gcov_type all
)
1351 gcall
*iretbnd_stmt
= NULL
;
1352 tree tmp0
, tmp1
, tmp
;
1353 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1354 tree optype
= build_pointer_type (void_type_node
);
1355 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1356 gimple_stmt_iterator gsi
;
1360 gimple_stmt_iterator psi
;
1362 cond_bb
= gimple_bb (icall_stmt
);
1363 gsi
= gsi_for_stmt (icall_stmt
);
1365 if (gimple_call_with_bounds_p (icall_stmt
) && gimple_call_lhs (icall_stmt
))
1366 iretbnd_stmt
= chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt
));
1368 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1369 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1370 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1371 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1372 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1374 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
));
1375 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1376 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1378 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1379 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1381 if (TREE_CODE (gimple_vdef (icall_stmt
)) == SSA_NAME
)
1383 unlink_stmt_vdef (icall_stmt
);
1384 release_ssa_name (gimple_vdef (icall_stmt
));
1386 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1387 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1388 update_stmt (icall_stmt
);
1389 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1390 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1391 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1392 if ((dflags
& ECF_NORETURN
) != 0)
1393 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1394 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1397 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1398 e_cd
= split_block (cond_bb
, cond_stmt
);
1399 dcall_bb
= e_cd
->dest
;
1400 dcall_bb
->count
= count
;
1402 e_di
= split_block (dcall_bb
, dcall_stmt
);
1403 icall_bb
= e_di
->dest
;
1404 icall_bb
->count
= all
- count
;
1406 /* Do not disturb existing EH edges from the indirect call. */
1407 if (!stmt_ends_bb_p (icall_stmt
))
1408 e_ij
= split_block (icall_bb
, icall_stmt
);
1411 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1412 /* The indirect call might be noreturn. */
1415 e_ij
->probability
= REG_BR_PROB_BASE
;
1416 e_ij
->count
= all
- count
;
1417 e_ij
= single_pred_edge (split_edge (e_ij
));
1422 join_bb
= e_ij
->dest
;
1423 join_bb
->count
= all
;
1426 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1427 e_cd
->probability
= prob
;
1428 e_cd
->count
= count
;
1430 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1431 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1432 e_ci
->count
= all
- count
;
1438 if ((dflags
& ECF_NORETURN
) != 0)
1442 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1443 e_dj
->probability
= REG_BR_PROB_BASE
;
1444 e_dj
->count
= count
;
1446 e_ij
->count
= all
- count
;
1448 e_ij
->probability
= REG_BR_PROB_BASE
;
1451 /* Insert PHI node for the call result if necessary. */
1452 if (gimple_call_lhs (icall_stmt
)
1453 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1454 && (dflags
& ECF_NORETURN
) == 0)
1456 tree result
= gimple_call_lhs (icall_stmt
);
1457 gphi
*phi
= create_phi_node (result
, join_bb
);
1458 gimple_call_set_lhs (icall_stmt
,
1459 duplicate_ssa_name (result
, icall_stmt
));
1460 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1461 gimple_call_set_lhs (dcall_stmt
,
1462 duplicate_ssa_name (result
, dcall_stmt
));
1463 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1465 /* If indirect call has following BUILT_IN_CHKP_BNDRET
1466 call then we need to make it's copy for the direct
1470 if (gimple_call_lhs (iretbnd_stmt
))
1474 if (TREE_CODE (gimple_vdef (iretbnd_stmt
)) == SSA_NAME
)
1476 unlink_stmt_vdef (iretbnd_stmt
);
1477 release_ssa_name (gimple_vdef (iretbnd_stmt
));
1479 gimple_set_vdef (iretbnd_stmt
, NULL_TREE
);
1480 gimple_set_vuse (iretbnd_stmt
, NULL_TREE
);
1481 update_stmt (iretbnd_stmt
);
1483 result
= gimple_call_lhs (iretbnd_stmt
);
1484 phi
= create_phi_node (result
, join_bb
);
1486 copy
= gimple_copy (iretbnd_stmt
);
1487 gimple_call_set_arg (copy
, 0,
1488 gimple_call_lhs (dcall_stmt
));
1489 gimple_call_set_lhs (copy
, duplicate_ssa_name (result
, copy
));
1490 gsi_insert_on_edge (e_dj
, copy
);
1491 add_phi_arg (phi
, gimple_call_lhs (copy
),
1492 e_dj
, UNKNOWN_LOCATION
);
1494 gimple_call_set_arg (iretbnd_stmt
, 0,
1495 gimple_call_lhs (icall_stmt
));
1496 gimple_call_set_lhs (iretbnd_stmt
,
1497 duplicate_ssa_name (result
, iretbnd_stmt
));
1498 psi
= gsi_for_stmt (iretbnd_stmt
);
1499 gsi_remove (&psi
, false);
1500 gsi_insert_on_edge (e_ij
, iretbnd_stmt
);
1501 add_phi_arg (phi
, gimple_call_lhs (iretbnd_stmt
),
1502 e_ij
, UNKNOWN_LOCATION
);
1504 gsi_commit_one_edge_insert (e_dj
, NULL
);
1505 gsi_commit_one_edge_insert (e_ij
, NULL
);
1509 psi
= gsi_for_stmt (iretbnd_stmt
);
1510 gsi_remove (&psi
, true);
1515 /* Build an EH edge for the direct call if necessary. */
1516 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1517 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1519 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1522 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1523 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1525 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1526 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1527 !gsi_end_p (psi
); gsi_next (&psi
))
1529 gphi
*phi
= psi
.phi ();
1530 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1531 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1534 if (!stmt_could_throw_p (dcall_stmt
))
1535 gimple_purge_dead_eh_edges (dcall_bb
);
1540 For every checked indirect/virtual call determine if most common pid of
1541 function/class method has probability more than 50%. If yes modify code of
1546 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1549 histogram_value histogram
;
1550 gcov_type val
, count
, all
, bb_all
;
1551 struct cgraph_node
*direct_call
;
1553 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1557 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1560 if (gimple_call_internal_p (stmt
))
1563 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1567 val
= histogram
->hvalue
.counters
[0];
1568 count
= histogram
->hvalue
.counters
[1];
1569 all
= histogram
->hvalue
.counters
[2];
1571 bb_all
= gimple_bb (stmt
)->count
;
1572 /* The order of CHECK_COUNTER calls is important -
1573 since check_counter can correct the third parameter
1574 and we want to make count <= all <= bb_all. */
1575 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1576 || check_counter (stmt
, "ic", &count
, &all
, all
))
1578 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1582 if (4 * count
<= 3 * all
)
1585 direct_call
= find_func_by_profile_id ((int)val
);
1587 if (direct_call
== NULL
)
1593 fprintf (dump_file
, "Indirect call -> direct call from other module");
1594 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1595 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1601 if (!check_ic_target (stmt
, direct_call
))
1605 fprintf (dump_file
, "Indirect call -> direct call ");
1606 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1607 fprintf (dump_file
, "=> ");
1608 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1609 fprintf (dump_file
, " transformation skipped because of type mismatch");
1610 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1612 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1618 fprintf (dump_file
, "Indirect call -> direct call ");
1619 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1620 fprintf (dump_file
, "=> ");
1621 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1622 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1623 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1624 fprintf (dump_file
, "hist->count %" PRId64
1625 " hist->all %" PRId64
"\n", count
, all
);
1631 /* Return true if the stringop CALL shall be profiled. SIZE_ARG be
1632 set to the argument index for the size of the string operation. */
1635 interesting_stringop_to_profile_p (gcall
*call
, int *size_arg
)
1637 enum built_in_function fcode
;
1639 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (call
));
1640 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1641 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1646 case BUILT_IN_MEMCPY
:
1647 case BUILT_IN_MEMPCPY
:
1649 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1650 INTEGER_TYPE
, VOID_TYPE
);
1651 case BUILT_IN_MEMSET
:
1653 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1654 INTEGER_TYPE
, VOID_TYPE
);
1655 case BUILT_IN_BZERO
:
1657 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1664 /* Convert stringop (..., vcall_size)
1666 if (vcall_size == icall_size)
1667 stringop (..., icall_size);
1669 stringop (..., vcall_size);
1670 assuming we'll propagate a true constant into ICALL_SIZE later. */
1673 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, int prob
,
1674 gcov_type count
, gcov_type all
)
1679 tree tmp0
, tmp1
, vcall_size
, optype
;
1680 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1681 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1682 gimple_stmt_iterator gsi
;
1685 if (!interesting_stringop_to_profile_p (vcall_stmt
, &size_arg
))
1688 cond_bb
= gimple_bb (vcall_stmt
);
1689 gsi
= gsi_for_stmt (vcall_stmt
);
1691 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1692 optype
= TREE_TYPE (vcall_size
);
1694 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1695 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1696 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1697 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1699 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1700 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1702 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1703 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1705 if (TREE_CODE (gimple_vdef (vcall_stmt
)) == SSA_NAME
)
1707 unlink_stmt_vdef (vcall_stmt
);
1708 release_ssa_name (gimple_vdef (vcall_stmt
));
1710 gimple_set_vdef (vcall_stmt
, NULL
);
1711 gimple_set_vuse (vcall_stmt
, NULL
);
1712 update_stmt (vcall_stmt
);
1713 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1714 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1715 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1718 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1719 e_ci
= split_block (cond_bb
, cond_stmt
);
1720 icall_bb
= e_ci
->dest
;
1721 icall_bb
->count
= count
;
1723 e_iv
= split_block (icall_bb
, icall_stmt
);
1724 vcall_bb
= e_iv
->dest
;
1725 vcall_bb
->count
= all
- count
;
1727 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1728 join_bb
= e_vj
->dest
;
1729 join_bb
->count
= all
;
1731 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1732 e_ci
->probability
= prob
;
1733 e_ci
->count
= count
;
1735 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1736 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1737 e_cv
->count
= all
- count
;
1741 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1742 e_ij
->probability
= REG_BR_PROB_BASE
;
1743 e_ij
->count
= count
;
1745 e_vj
->probability
= REG_BR_PROB_BASE
;
1746 e_vj
->count
= all
- count
;
1748 /* Insert PHI node for the call result if necessary. */
1749 if (gimple_call_lhs (vcall_stmt
)
1750 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1752 tree result
= gimple_call_lhs (vcall_stmt
);
1753 gphi
*phi
= create_phi_node (result
, join_bb
);
1754 gimple_call_set_lhs (vcall_stmt
,
1755 duplicate_ssa_name (result
, vcall_stmt
));
1756 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1757 gimple_call_set_lhs (icall_stmt
,
1758 duplicate_ssa_name (result
, icall_stmt
));
1759 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1762 /* Because these are all string op builtins, they're all nothrow. */
1763 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1764 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1767 /* Find values inside STMT for that we want to measure histograms for
1768 division/modulo optimization. */
1771 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1775 enum built_in_function fcode
;
1776 histogram_value histogram
;
1777 gcov_type count
, all
, val
;
1779 unsigned int dest_align
, src_align
;
1784 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1788 if (!gimple_call_builtin_p (gsi_stmt (*gsi
), BUILT_IN_NORMAL
))
1791 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
1794 blck_size
= gimple_call_arg (stmt
, size_arg
);
1795 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1798 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1802 val
= histogram
->hvalue
.counters
[0];
1803 count
= histogram
->hvalue
.counters
[1];
1804 all
= histogram
->hvalue
.counters
[2];
1805 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1807 /* We require that count is at least half of all; this means
1808 that for the transformation to fire the value must be constant
1809 at least 80% of time. */
1810 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1812 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1815 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1819 dest
= gimple_call_arg (stmt
, 0);
1820 dest_align
= get_pointer_alignment (dest
);
1821 fcode
= DECL_FUNCTION_CODE (gimple_call_fndecl (stmt
));
1824 case BUILT_IN_MEMCPY
:
1825 case BUILT_IN_MEMPCPY
:
1826 src
= gimple_call_arg (stmt
, 1);
1827 src_align
= get_pointer_alignment (src
);
1828 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1831 case BUILT_IN_MEMSET
:
1832 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1833 gimple_call_arg (stmt
, 1),
1837 case BUILT_IN_BZERO
:
1838 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1847 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1848 tree_val
= build_int_cst (get_gcov_type (), val
);
1852 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1853 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1855 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1856 TYPE_PRECISION (get_gcov_type ()), false));
1861 fprintf (dump_file
, "Single value %i stringop transformation on ",
1863 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1866 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1872 stringop_block_profile (gimple
*stmt
, unsigned int *expected_align
,
1873 HOST_WIDE_INT
*expected_size
)
1875 histogram_value histogram
;
1876 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1879 *expected_size
= -1;
1880 else if (!histogram
->hvalue
.counters
[1])
1882 *expected_size
= -1;
1883 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1888 size
= ((histogram
->hvalue
.counters
[0]
1889 + histogram
->hvalue
.counters
[1] / 2)
1890 / histogram
->hvalue
.counters
[1]);
1891 /* Even if we can hold bigger value in SIZE, INT_MAX
1892 is safe "infinity" for code generation strategies. */
1895 *expected_size
= size
;
1896 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1899 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1902 *expected_align
= 0;
1903 else if (!histogram
->hvalue
.counters
[0])
1905 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1906 *expected_align
= 0;
1913 count
= histogram
->hvalue
.counters
[0];
1915 while (!(count
& alignment
)
1916 && (alignment
* 2 * BITS_PER_UNIT
))
1918 *expected_align
= alignment
* BITS_PER_UNIT
;
1919 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1924 /* Find values inside STMT for that we want to measure histograms for
1925 division/modulo optimization. */
1928 gimple_divmod_values_to_profile (gimple
*stmt
, histogram_values
*values
)
1930 tree lhs
, divisor
, op0
, type
;
1931 histogram_value hist
;
1933 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1936 lhs
= gimple_assign_lhs (stmt
);
1937 type
= TREE_TYPE (lhs
);
1938 if (!INTEGRAL_TYPE_P (type
))
1941 switch (gimple_assign_rhs_code (stmt
))
1943 case TRUNC_DIV_EXPR
:
1944 case TRUNC_MOD_EXPR
:
1945 divisor
= gimple_assign_rhs2 (stmt
);
1946 op0
= gimple_assign_rhs1 (stmt
);
1948 values
->reserve (3);
1950 if (TREE_CODE (divisor
) == SSA_NAME
)
1951 /* Check for the case where the divisor is the same value most
1953 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1954 HIST_TYPE_SINGLE_VALUE
,
1957 /* For mod, check whether it is not often a noop (or replaceable by
1958 a few subtractions). */
1959 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1960 && TYPE_UNSIGNED (type
))
1963 /* Check for a special case where the divisor is power of 2. */
1964 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1968 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1969 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1971 hist
->hdata
.intvl
.int_start
= 0;
1972 hist
->hdata
.intvl
.steps
= 2;
1973 values
->quick_push (hist
);
1982 /* Find calls inside STMT for that we want to measure histograms for
1983 indirect/virtual call optimization. */
1986 gimple_indirect_call_to_profile (gimple
*stmt
, histogram_values
*values
)
1990 if (gimple_code (stmt
) != GIMPLE_CALL
1991 || gimple_call_internal_p (stmt
)
1992 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1995 callee
= gimple_call_fn (stmt
);
1997 values
->reserve (3);
1999 values
->quick_push (gimple_alloc_histogram_value (
2001 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
2002 HIST_TYPE_INDIR_CALL_TOPN
:
2003 HIST_TYPE_INDIR_CALL
,
2009 /* Find values inside STMT for that we want to measure histograms for
2010 string operations. */
2013 gimple_stringops_values_to_profile (gimple
*gs
, histogram_values
*values
)
2020 stmt
= dyn_cast
<gcall
*> (gs
);
2024 if (!gimple_call_builtin_p (gs
, BUILT_IN_NORMAL
))
2027 if (!interesting_stringop_to_profile_p (stmt
, &size_arg
))
2030 dest
= gimple_call_arg (stmt
, 0);
2031 blck_size
= gimple_call_arg (stmt
, size_arg
);
2033 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2035 values
->safe_push (gimple_alloc_histogram_value (cfun
,
2036 HIST_TYPE_SINGLE_VALUE
,
2038 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
2042 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2043 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
2047 /* Find values inside STMT for that we want to measure histograms and adds
2048 them to list VALUES. */
2051 gimple_values_to_profile (gimple
*stmt
, histogram_values
*values
)
2053 gimple_divmod_values_to_profile (stmt
, values
);
2054 gimple_stringops_values_to_profile (stmt
, values
);
2055 gimple_indirect_call_to_profile (stmt
, values
);
2059 gimple_find_values_to_profile (histogram_values
*values
)
2062 gimple_stmt_iterator gsi
;
2064 histogram_value hist
= NULL
;
2067 FOR_EACH_BB_FN (bb
, cfun
)
2068 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2069 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2071 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2073 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2077 case HIST_TYPE_INTERVAL
:
2078 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2081 case HIST_TYPE_POW2
:
2082 hist
->n_counters
= 2;
2085 case HIST_TYPE_SINGLE_VALUE
:
2086 hist
->n_counters
= 3;
2089 case HIST_TYPE_CONST_DELTA
:
2090 hist
->n_counters
= 4;
2093 case HIST_TYPE_INDIR_CALL
:
2094 hist
->n_counters
= 3;
2097 case HIST_TYPE_TIME_PROFILE
:
2098 hist
->n_counters
= 1;
2101 case HIST_TYPE_AVERAGE
:
2102 hist
->n_counters
= 2;
2106 hist
->n_counters
= 1;
2109 case HIST_TYPE_INDIR_CALL_TOPN
:
2110 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2118 fprintf (dump_file
, "Stmt ");
2119 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2120 dump_histogram_value (dump_file
, hist
);