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"
44 #include "insn-codes.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
50 #include "gimple-expr.h"
54 #include "gimple-iterator.h"
55 #include "gimple-ssa.h"
57 #include "tree-phinodes.h"
58 #include "ssa-iterators.h"
59 #include "stringpool.h"
60 #include "tree-ssanames.h"
61 #include "diagnostic.h"
62 #include "gimple-pretty-print.h"
70 #include "plugin-api.h"
73 #include "data-streamer.h"
75 #include "tree-nested.h"
77 #include "tree-chkp.h"
79 /* In this file value profile based optimizations are placed. Currently the
80 following optimizations are implemented (for more detailed descriptions
81 see comments at value_profile_transformations):
83 1) Division/modulo specialization. Provided that we can determine that the
84 operands of the division have some special properties, we may use it to
85 produce more effective code.
87 2) Indirect/virtual call specialization. If we can determine most
88 common function callee in indirect/virtual call. We can use this
89 information to improve code effectiveness (especially info for
92 3) Speculative prefetching. If we are able to determine that the difference
93 between addresses accessed by a memory reference is usually constant, we
94 may add the prefetch instructions.
95 FIXME: This transformation was removed together with RTL based value
99 Value profiling internals
100 ==========================
102 Every value profiling transformation starts with defining what values
103 to profile. There are different histogram types (see HIST_TYPE_* in
104 value-prof.h) and each transformation can request one or more histogram
105 types per GIMPLE statement. The function gimple_find_values_to_profile()
106 collects the values to profile in a vec, and adds the number of counters
107 required for the different histogram types.
109 For a -fprofile-generate run, the statements for which values should be
110 recorded, are instrumented in instrument_values(). The instrumentation
111 is done by helper functions that can be found in tree-profile.c, where
112 new types of histograms can be added if necessary.
114 After a -fprofile-use, the value profiling data is read back in by
115 compute_value_histograms() that translates the collected data to
116 histograms and attaches them to the profiled statements via
117 gimple_add_histogram_value(). Histograms are stored in a hash table
118 that is attached to every intrumented function, see VALUE_HISTOGRAMS
121 The value-profile transformations driver is the function
122 gimple_value_profile_transformations(). It traverses all statements in
123 the to-be-transformed function, and looks for statements with one or
124 more histograms attached to it. If a statement has histograms, the
125 transformation functions are called on the statement.
127 Limitations / FIXME / TODO:
128 * Only one histogram of each type can be associated with a statement.
129 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
130 (This type of histogram was originally used to implement a form of
131 stride profiling based speculative prefetching to improve SPEC2000
132 scores for memory-bound benchmarks, mcf and equake. However, this
133 was an RTL value-profiling transformation, and those have all been
135 * Some value profile transformations are done in builtins.c (?!)
136 * Updating of histograms needs some TLC.
137 * The value profiling code could be used to record analysis results
138 from non-profiling (e.g. VRP).
139 * Adding new profilers should be simplified, starting with a cleanup
140 of what-happens-where andwith making gimple_find_values_to_profile
141 and gimple_value_profile_transformations table-driven, perhaps...
144 static tree
gimple_divmod_fixed_value (gassign
*, tree
, int, gcov_type
,
146 static tree
gimple_mod_pow2 (gassign
*, int, gcov_type
, gcov_type
);
147 static tree
gimple_mod_subtract (gassign
*, int, int, int, gcov_type
,
148 gcov_type
, gcov_type
);
149 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
150 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
151 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
152 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
153 static bool gimple_ic_transform (gimple_stmt_iterator
*);
155 /* Allocate histogram value. */
158 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
159 enum hist_type type
, gimple stmt
, tree value
)
161 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
162 hist
->hvalue
.value
= value
;
163 hist
->hvalue
.stmt
= stmt
;
168 /* Hash value for histogram. */
171 histogram_hash (const void *x
)
173 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
176 /* Return nonzero if statement for histogram_value X is Y. */
179 histogram_eq (const void *x
, const void *y
)
181 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
184 /* Set histogram for STMT. */
187 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
190 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
192 if (!VALUE_HISTOGRAMS (fun
))
193 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
195 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
196 htab_hash_pointer (stmt
),
197 hist
? INSERT
: NO_INSERT
);
201 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
207 /* Get histogram list for STMT. */
210 gimple_histogram_value (struct function
*fun
, gimple stmt
)
212 if (!VALUE_HISTOGRAMS (fun
))
214 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
215 htab_hash_pointer (stmt
));
218 /* Add histogram for STMT. */
221 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
222 histogram_value hist
)
224 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
225 set_histogram_value (fun
, stmt
, hist
);
230 /* Remove histogram HIST from STMT's histogram list. */
233 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
234 histogram_value hist
)
236 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
239 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
243 while (hist2
->hvalue
.next
!= hist
)
244 hist2
= hist2
->hvalue
.next
;
245 hist2
->hvalue
.next
= hist
->hvalue
.next
;
247 free (hist
->hvalue
.counters
);
248 #ifdef ENABLE_CHECKING
249 memset (hist
, 0xab, sizeof (*hist
));
255 /* Lookup histogram of type TYPE in the STMT. */
258 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
261 histogram_value hist
;
262 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
263 hist
= hist
->hvalue
.next
)
264 if (hist
->type
== type
)
269 /* Dump information about HIST to DUMP_FILE. */
272 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
276 case HIST_TYPE_INTERVAL
:
277 fprintf (dump_file
, "Interval counter range %d -- %d",
278 hist
->hdata
.intvl
.int_start
,
279 (hist
->hdata
.intvl
.int_start
280 + hist
->hdata
.intvl
.steps
- 1));
281 if (hist
->hvalue
.counters
)
284 fprintf (dump_file
, " [");
285 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
286 fprintf (dump_file
, " %d:%"PRId64
,
287 hist
->hdata
.intvl
.int_start
+ i
,
288 (int64_t) hist
->hvalue
.counters
[i
]);
289 fprintf (dump_file
, " ] outside range:%"PRId64
,
290 (int64_t) hist
->hvalue
.counters
[i
]);
292 fprintf (dump_file
, ".\n");
296 fprintf (dump_file
, "Pow2 counter ");
297 if (hist
->hvalue
.counters
)
299 fprintf (dump_file
, "pow2:%"PRId64
301 (int64_t) hist
->hvalue
.counters
[0],
302 (int64_t) hist
->hvalue
.counters
[1]);
304 fprintf (dump_file
, ".\n");
307 case HIST_TYPE_SINGLE_VALUE
:
308 fprintf (dump_file
, "Single value ");
309 if (hist
->hvalue
.counters
)
311 fprintf (dump_file
, "value:%"PRId64
314 (int64_t) hist
->hvalue
.counters
[0],
315 (int64_t) hist
->hvalue
.counters
[1],
316 (int64_t) hist
->hvalue
.counters
[2]);
318 fprintf (dump_file
, ".\n");
321 case HIST_TYPE_AVERAGE
:
322 fprintf (dump_file
, "Average value ");
323 if (hist
->hvalue
.counters
)
325 fprintf (dump_file
, "sum:%"PRId64
327 (int64_t) hist
->hvalue
.counters
[0],
328 (int64_t) hist
->hvalue
.counters
[1]);
330 fprintf (dump_file
, ".\n");
334 fprintf (dump_file
, "IOR value ");
335 if (hist
->hvalue
.counters
)
337 fprintf (dump_file
, "ior:%"PRId64
,
338 (int64_t) hist
->hvalue
.counters
[0]);
340 fprintf (dump_file
, ".\n");
343 case HIST_TYPE_CONST_DELTA
:
344 fprintf (dump_file
, "Constant delta ");
345 if (hist
->hvalue
.counters
)
347 fprintf (dump_file
, "value:%"PRId64
350 (int64_t) hist
->hvalue
.counters
[0],
351 (int64_t) hist
->hvalue
.counters
[1],
352 (int64_t) hist
->hvalue
.counters
[2]);
354 fprintf (dump_file
, ".\n");
356 case HIST_TYPE_INDIR_CALL
:
357 fprintf (dump_file
, "Indirect call ");
358 if (hist
->hvalue
.counters
)
360 fprintf (dump_file
, "value:%"PRId64
363 (int64_t) hist
->hvalue
.counters
[0],
364 (int64_t) hist
->hvalue
.counters
[1],
365 (int64_t) hist
->hvalue
.counters
[2]);
367 fprintf (dump_file
, ".\n");
369 case HIST_TYPE_TIME_PROFILE
:
370 fprintf (dump_file
, "Time profile ");
371 if (hist
->hvalue
.counters
)
373 fprintf (dump_file
, "time:%"PRId64
,
374 (int64_t) hist
->hvalue
.counters
[0]);
376 fprintf (dump_file
, ".\n");
378 case HIST_TYPE_INDIR_CALL_TOPN
:
379 fprintf (dump_file
, "Indirect call topn ");
380 if (hist
->hvalue
.counters
)
384 fprintf (dump_file
, "accu:%"PRId64
, hist
->hvalue
.counters
[0]);
385 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
387 fprintf (dump_file
, " target:%"PRId64
" value:%"PRId64
,
388 (int64_t) hist
->hvalue
.counters
[i
],
389 (int64_t) hist
->hvalue
.counters
[i
+1]);
392 fprintf (dump_file
, ".\n");
399 /* Dump information about HIST to DUMP_FILE. */
402 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
407 bp
= bitpack_create (ob
->main_stream
);
408 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
409 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
410 streamer_write_bitpack (&bp
);
413 case HIST_TYPE_INTERVAL
:
414 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
415 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
420 for (i
= 0; i
< hist
->n_counters
; i
++)
421 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
422 if (hist
->hvalue
.next
)
423 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
425 /* Dump information about HIST to DUMP_FILE. */
428 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
431 unsigned int ncounters
= 0;
434 histogram_value new_val
;
436 histogram_value
*next_p
= NULL
;
440 bp
= streamer_read_bitpack (ib
);
441 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
442 next
= bp_unpack_value (&bp
, 1);
443 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
446 case HIST_TYPE_INTERVAL
:
447 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
448 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
449 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
453 case HIST_TYPE_AVERAGE
:
457 case HIST_TYPE_SINGLE_VALUE
:
458 case HIST_TYPE_INDIR_CALL
:
462 case HIST_TYPE_CONST_DELTA
:
467 case HIST_TYPE_TIME_PROFILE
:
471 case HIST_TYPE_INDIR_CALL_TOPN
:
472 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
478 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
479 new_val
->n_counters
= ncounters
;
480 for (i
= 0; i
< ncounters
; i
++)
481 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
483 gimple_add_histogram_value (cfun
, stmt
, new_val
);
486 next_p
= &new_val
->hvalue
.next
;
491 /* Dump all histograms attached to STMT to DUMP_FILE. */
494 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
496 histogram_value hist
;
497 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
498 dump_histogram_value (dump_file
, hist
);
501 /* Remove all histograms associated with STMT. */
504 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
507 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
508 gimple_remove_histogram_value (fun
, stmt
, val
);
511 /* Duplicate all histograms associates with OSTMT to STMT. */
514 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
515 struct function
*ofun
, gimple ostmt
)
518 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
520 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
521 memcpy (new_val
, val
, sizeof (*val
));
522 new_val
->hvalue
.stmt
= stmt
;
523 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
524 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
525 gimple_add_histogram_value (fun
, stmt
, new_val
);
530 /* Move all histograms associated with OSTMT to STMT. */
533 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
535 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
538 /* The following three statements can't be reordered,
539 because histogram hashtab relies on stmt field value
540 for finding the exact slot. */
541 set_histogram_value (fun
, ostmt
, NULL
);
542 for (; val
!= NULL
; val
= val
->hvalue
.next
)
543 val
->hvalue
.stmt
= stmt
;
544 set_histogram_value (fun
, stmt
, val
);
548 static bool error_found
= false;
550 /* Helper function for verify_histograms. For each histogram reachable via htab
551 walk verify that it was reached via statement walk. */
554 visit_hist (void **slot
, void *data
)
556 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
557 histogram_value hist
= *(histogram_value
*) slot
;
559 if (!visited
->contains (hist
)
560 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
562 error ("dead histogram");
563 dump_histogram_value (stderr
, hist
);
564 debug_gimple_stmt (hist
->hvalue
.stmt
);
571 /* Verify sanity of the histograms. */
574 verify_histograms (void)
577 gimple_stmt_iterator gsi
;
578 histogram_value hist
;
581 hash_set
<histogram_value
> visited_hists
;
582 FOR_EACH_BB_FN (bb
, cfun
)
583 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
585 gimple stmt
= gsi_stmt (gsi
);
587 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
588 hist
= hist
->hvalue
.next
)
590 if (hist
->hvalue
.stmt
!= stmt
)
592 error ("Histogram value statement does not correspond to "
593 "the statement it is associated with");
594 debug_gimple_stmt (stmt
);
595 dump_histogram_value (stderr
, hist
);
598 visited_hists
.add (hist
);
601 if (VALUE_HISTOGRAMS (cfun
))
602 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
604 internal_error ("verify_histograms failed");
607 /* Helper function for verify_histograms. For each histogram reachable via htab
608 walk verify that it was reached via statement walk. */
611 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
613 histogram_value hist
= *(histogram_value
*) slot
;
614 free (hist
->hvalue
.counters
);
615 #ifdef ENABLE_CHECKING
616 memset (hist
, 0xab, sizeof (*hist
));
623 free_histograms (void)
625 if (VALUE_HISTOGRAMS (cfun
))
627 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
628 htab_delete (VALUE_HISTOGRAMS (cfun
));
629 VALUE_HISTOGRAMS (cfun
) = NULL
;
634 /* The overall number of invocations of the counter should match
635 execution count of basic block. Report it as error rather than
636 internal error as it might mean that user has misused the profile
640 check_counter (gimple stmt
, const char * name
,
641 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
643 if (*all
!= bb_count
|| *count
> *all
)
646 locus
= (stmt
!= NULL
)
647 ? gimple_location (stmt
)
648 : DECL_SOURCE_LOCATION (current_function_decl
);
649 if (flag_profile_correction
)
651 if (dump_enabled_p ())
652 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
653 "correcting inconsistent value profile: %s "
654 "profiler overall count (%d) does not match BB "
655 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
663 error_at (locus
, "corrupted value profile: %s "
664 "profile counter (%d out of %d) inconsistent with "
665 "basic-block count (%d)",
678 /* GIMPLE based transformations. */
681 gimple_value_profile_transformations (void)
684 gimple_stmt_iterator gsi
;
685 bool changed
= false;
687 FOR_EACH_BB_FN (bb
, cfun
)
689 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
691 gimple stmt
= gsi_stmt (gsi
);
692 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
698 fprintf (dump_file
, "Trying transformations on stmt ");
699 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
700 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
703 /* Transformations: */
704 /* The order of things in this conditional controls which
705 transformation is used when more than one is applicable. */
706 /* It is expected that any code added by the transformations
707 will be added before the current statement, and that the
708 current statement remain valid (although possibly
709 modified) upon return. */
710 if (gimple_mod_subtract_transform (&gsi
)
711 || gimple_divmod_fixed_value_transform (&gsi
)
712 || gimple_mod_pow2_value_transform (&gsi
)
713 || gimple_stringops_transform (&gsi
)
714 || gimple_ic_transform (&gsi
))
716 stmt
= gsi_stmt (gsi
);
718 /* Original statement may no longer be in the same block. */
719 if (bb
!= gimple_bb (stmt
))
721 bb
= gimple_bb (stmt
);
722 gsi
= gsi_for_stmt (stmt
);
737 /* Generate code for transformation 1 (with parent gimple assignment
738 STMT and probability of taking the optimal path PROB, which is
739 equivalent to COUNT/ALL within roundoff error). This generates the
740 result into a temp and returns the temp; it does not replace or
741 alter the original STMT. */
744 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, int prob
,
745 gcov_type count
, gcov_type all
)
747 gassign
*stmt1
, *stmt2
;
749 tree tmp0
, tmp1
, tmp2
;
750 gimple bb1end
, bb2end
, bb3end
;
751 basic_block bb
, bb2
, bb3
, bb4
;
752 tree optype
, op1
, op2
;
753 edge e12
, e13
, e23
, e24
, e34
;
754 gimple_stmt_iterator gsi
;
756 gcc_assert (is_gimple_assign (stmt
)
757 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
758 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
760 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
761 op1
= gimple_assign_rhs1 (stmt
);
762 op2
= gimple_assign_rhs2 (stmt
);
764 bb
= gimple_bb (stmt
);
765 gsi
= gsi_for_stmt (stmt
);
767 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
768 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
769 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
770 stmt2
= gimple_build_assign (tmp1
, op2
);
771 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
772 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
773 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
774 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
777 tmp2
= create_tmp_reg (optype
, "PROF");
778 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
780 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
783 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
785 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
789 /* Edge e23 connects bb2 to bb3, etc. */
790 e12
= split_block (bb
, bb1end
);
793 e23
= split_block (bb2
, bb2end
);
795 bb3
->count
= all
- count
;
796 e34
= split_block (bb3
, bb3end
);
800 e12
->flags
&= ~EDGE_FALLTHRU
;
801 e12
->flags
|= EDGE_FALSE_VALUE
;
802 e12
->probability
= prob
;
805 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
806 e13
->probability
= REG_BR_PROB_BASE
- prob
;
807 e13
->count
= all
- count
;
811 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
812 e24
->probability
= REG_BR_PROB_BASE
;
815 e34
->probability
= REG_BR_PROB_BASE
;
816 e34
->count
= all
- count
;
822 /* Do transform 1) on INSN if applicable. */
825 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
827 histogram_value histogram
;
829 gcov_type val
, count
, all
;
830 tree result
, value
, tree_val
;
834 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
838 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
841 code
= gimple_assign_rhs_code (stmt
);
843 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
846 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
847 HIST_TYPE_SINGLE_VALUE
);
851 value
= histogram
->hvalue
.value
;
852 val
= histogram
->hvalue
.counters
[0];
853 count
= histogram
->hvalue
.counters
[1];
854 all
= histogram
->hvalue
.counters
[2];
855 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
857 /* We require that count is at least half of all; this means
858 that for the transformation to fire the value must be constant
859 at least 50% of time (and 75% gives the guarantee of usage). */
860 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
862 || optimize_bb_for_size_p (gimple_bb (stmt
)))
865 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
868 /* Compute probability of taking the optimal path. */
870 prob
= GCOV_COMPUTE_SCALE (count
, all
);
874 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
875 tree_val
= build_int_cst (get_gcov_type (), val
);
879 a
[0] = (unsigned HOST_WIDE_INT
) val
;
880 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
882 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
883 TYPE_PRECISION (get_gcov_type ()), false));
885 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
889 fprintf (dump_file
, "Div/mod by constant ");
890 print_generic_expr (dump_file
, value
, TDF_SLIM
);
891 fprintf (dump_file
, "=");
892 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
893 fprintf (dump_file
, " transformation on insn ");
894 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
897 gimple_assign_set_rhs_from_tree (si
, result
);
898 update_stmt (gsi_stmt (*si
));
903 /* Generate code for transformation 2 (with parent gimple assign STMT and
904 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
905 within roundoff error). This generates the result into a temp and returns
906 the temp; it does not replace or alter the original STMT. */
908 gimple_mod_pow2 (gassign
*stmt
, int prob
, gcov_type count
, gcov_type all
)
910 gassign
*stmt1
, *stmt2
, *stmt3
;
913 gimple bb1end
, bb2end
, bb3end
;
914 basic_block bb
, bb2
, bb3
, bb4
;
915 tree optype
, op1
, op2
;
916 edge e12
, e13
, e23
, e24
, e34
;
917 gimple_stmt_iterator gsi
;
920 gcc_assert (is_gimple_assign (stmt
)
921 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
923 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
924 op1
= gimple_assign_rhs1 (stmt
);
925 op2
= gimple_assign_rhs2 (stmt
);
927 bb
= gimple_bb (stmt
);
928 gsi
= gsi_for_stmt (stmt
);
930 result
= create_tmp_reg (optype
, "PROF");
931 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
932 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
933 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
934 build_int_cst (optype
, -1));
935 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
936 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
937 NULL_TREE
, NULL_TREE
);
938 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
939 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
940 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
943 /* tmp2 == op2-1 inherited from previous block. */
944 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
945 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
948 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
950 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
954 /* Edge e23 connects bb2 to bb3, etc. */
955 e12
= split_block (bb
, bb1end
);
958 e23
= split_block (bb2
, bb2end
);
960 bb3
->count
= all
- count
;
961 e34
= split_block (bb3
, bb3end
);
965 e12
->flags
&= ~EDGE_FALLTHRU
;
966 e12
->flags
|= EDGE_FALSE_VALUE
;
967 e12
->probability
= prob
;
970 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
971 e13
->probability
= REG_BR_PROB_BASE
- prob
;
972 e13
->count
= all
- count
;
976 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
977 e24
->probability
= REG_BR_PROB_BASE
;
980 e34
->probability
= REG_BR_PROB_BASE
;
981 e34
->count
= all
- count
;
986 /* Do transform 2) on INSN if applicable. */
988 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
990 histogram_value histogram
;
992 gcov_type count
, wrong_values
, all
;
993 tree lhs_type
, result
, value
;
997 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1001 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1002 if (!INTEGRAL_TYPE_P (lhs_type
))
1005 code
= gimple_assign_rhs_code (stmt
);
1007 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1010 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
1014 value
= histogram
->hvalue
.value
;
1015 wrong_values
= histogram
->hvalue
.counters
[0];
1016 count
= histogram
->hvalue
.counters
[1];
1018 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1020 /* We require that we hit a power of 2 at least half of all evaluations. */
1021 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
1022 || count
< wrong_values
1023 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1028 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
1029 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1032 /* Compute probability of taking the optimal path. */
1033 all
= count
+ wrong_values
;
1035 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1039 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1043 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1045 gimple_assign_set_rhs_from_tree (si
, result
);
1046 update_stmt (gsi_stmt (*si
));
1051 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1052 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1053 supported and this is built into this interface. The probabilities of taking
1054 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1055 COUNT2/ALL respectively within roundoff error). This generates the
1056 result into a temp and returns the temp; it does not replace or alter
1057 the original STMT. */
1058 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1061 gimple_mod_subtract (gassign
*stmt
, int prob1
, int prob2
, int ncounts
,
1062 gcov_type count1
, gcov_type count2
, gcov_type all
)
1068 gimple bb1end
, bb2end
= NULL
, bb3end
;
1069 basic_block bb
, bb2
, bb3
, bb4
;
1070 tree optype
, op1
, op2
;
1071 edge e12
, e23
= 0, e24
, e34
, e14
;
1072 gimple_stmt_iterator gsi
;
1075 gcc_assert (is_gimple_assign (stmt
)
1076 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1078 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1079 op1
= gimple_assign_rhs1 (stmt
);
1080 op2
= gimple_assign_rhs2 (stmt
);
1082 bb
= gimple_bb (stmt
);
1083 gsi
= gsi_for_stmt (stmt
);
1085 result
= create_tmp_reg (optype
, "PROF");
1086 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1087 stmt1
= gimple_build_assign (result
, op1
);
1088 stmt2
= gimple_build_assign (tmp1
, op2
);
1089 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1090 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1091 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1092 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1095 if (ncounts
) /* Assumed to be 0 or 1 */
1097 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
1098 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1099 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1100 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1104 /* Fallback case. */
1105 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
1107 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1111 /* Edge e23 connects bb2 to bb3, etc. */
1112 /* However block 3 is optional; if it is not there, references
1113 to 3 really refer to block 2. */
1114 e12
= split_block (bb
, bb1end
);
1116 bb2
->count
= all
- count1
;
1118 if (ncounts
) /* Assumed to be 0 or 1. */
1120 e23
= split_block (bb2
, bb2end
);
1122 bb3
->count
= all
- count1
- count2
;
1125 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1129 e12
->flags
&= ~EDGE_FALLTHRU
;
1130 e12
->flags
|= EDGE_FALSE_VALUE
;
1131 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1132 e12
->count
= all
- count1
;
1134 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1135 e14
->probability
= prob1
;
1136 e14
->count
= count1
;
1138 if (ncounts
) /* Assumed to be 0 or 1. */
1140 e23
->flags
&= ~EDGE_FALLTHRU
;
1141 e23
->flags
|= EDGE_FALSE_VALUE
;
1142 e23
->count
= all
- count1
- count2
;
1143 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1145 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1146 e24
->probability
= prob2
;
1147 e24
->count
= count2
;
1150 e34
->probability
= REG_BR_PROB_BASE
;
1151 e34
->count
= all
- count1
- count2
;
1157 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1160 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1162 histogram_value histogram
;
1163 enum tree_code code
;
1164 gcov_type count
, wrong_values
, all
;
1165 tree lhs_type
, result
;
1166 gcov_type prob1
, prob2
;
1167 unsigned int i
, steps
;
1168 gcov_type count1
, count2
;
1171 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1175 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1176 if (!INTEGRAL_TYPE_P (lhs_type
))
1179 code
= gimple_assign_rhs_code (stmt
);
1181 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1184 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1190 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1191 all
+= histogram
->hvalue
.counters
[i
];
1193 wrong_values
+= histogram
->hvalue
.counters
[i
];
1194 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1195 steps
= histogram
->hdata
.intvl
.steps
;
1196 all
+= wrong_values
;
1197 count1
= histogram
->hvalue
.counters
[0];
1198 count2
= histogram
->hvalue
.counters
[1];
1200 /* Compute probability of taking the optimal path. */
1201 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1203 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1207 if (flag_profile_correction
&& count1
+ count2
> all
)
1208 all
= count1
+ count2
;
1210 gcc_assert (count1
+ count2
<= all
);
1212 /* We require that we use just subtractions in at least 50% of all
1215 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1217 count
+= histogram
->hvalue
.counters
[i
];
1218 if (count
* 2 >= all
)
1222 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1225 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1228 fprintf (dump_file
, "Mod subtract transformation on insn ");
1229 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1232 /* Compute probability of taking the optimal path(s). */
1235 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1236 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1243 /* In practice, "steps" is always 2. This interface reflects this,
1244 and will need to be changed if "steps" can change. */
1245 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1247 gimple_assign_set_rhs_from_tree (si
, result
);
1248 update_stmt (gsi_stmt (*si
));
1253 struct profile_id_traits
: default_hashmap_traits
1255 template<typename T
>
1259 return e
.m_key
== UINT_MAX
;
1262 template<typename T
> static bool is_empty (T
&e
) { return e
.m_key
== 0; }
1263 template<typename T
> static void mark_deleted (T
&e
) { e
.m_key
= UINT_MAX
; }
1264 template<typename T
> static void mark_empty (T
&e
) { e
.m_key
= 0; }
1267 static hash_map
<unsigned int, cgraph_node
*, profile_id_traits
> *
1268 cgraph_node_map
= 0;
1270 /* Returns true if node graph is initialized. This
1271 is used to test if profile_id has been created
1272 for cgraph_nodes. */
1275 coverage_node_map_initialized_p (void)
1277 return cgraph_node_map
!= 0;
1280 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1281 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1282 that the PROFILE_IDs was already assigned. */
1285 init_node_map (bool local
)
1287 struct cgraph_node
*n
;
1289 = new hash_map
<unsigned int, cgraph_node
*, profile_id_traits
>;
1291 FOR_EACH_DEFINED_FUNCTION (n
)
1292 if (n
->has_gimple_body_p ())
1297 n
->profile_id
= coverage_compute_profile_id (n
);
1298 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1302 fprintf (dump_file
, "Local profile-id %i conflict"
1303 " with nodes %s/%i %s/%i\n",
1309 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1312 else if (!n
->profile_id
)
1316 "Node %s/%i has no profile-id"
1317 " (profile feedback missing?)\n",
1322 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1326 "Node %s/%i has IP profile-id %i conflict. "
1334 cgraph_node_map
->put (n
->profile_id
, n
);
1338 /* Delete the CGRAPH_NODE_MAP. */
1343 delete cgraph_node_map
;
1346 /* Return cgraph node for function with pid */
1349 find_func_by_profile_id (int profile_id
)
1351 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1358 /* Perform sanity check on the indirect call target. Due to race conditions,
1359 false function target may be attributed to an indirect call site. If the
1360 call expression type mismatches with the target function's type, expand_call
1361 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1362 Returns true if TARGET is considered ok for call CALL_STMT. */
1365 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1368 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1371 locus
= gimple_location (call_stmt
);
1372 if (dump_enabled_p ())
1373 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1374 "Skipping target %s with mismatching types for icall\n",
1379 /* Do transformation
1381 if (actual_callee_address == address_of_most_common_function/method)
1388 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1389 int prob
, gcov_type count
, gcov_type all
)
1394 gcall
*iretbnd_stmt
= NULL
;
1395 tree tmp0
, tmp1
, tmp
;
1396 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1397 tree optype
= build_pointer_type (void_type_node
);
1398 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1399 gimple_stmt_iterator gsi
;
1403 gimple_stmt_iterator psi
;
1405 cond_bb
= gimple_bb (icall_stmt
);
1406 gsi
= gsi_for_stmt (icall_stmt
);
1408 if (gimple_call_with_bounds_p (icall_stmt
) && gimple_call_lhs (icall_stmt
))
1409 iretbnd_stmt
= chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt
));
1411 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1412 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1413 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1414 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1415 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1417 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1418 current_function_decl
));
1419 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1420 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1422 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1423 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1425 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1426 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1427 update_stmt (icall_stmt
);
1428 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1429 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1430 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1431 if ((dflags
& ECF_NORETURN
) != 0)
1432 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1433 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1436 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1437 e_cd
= split_block (cond_bb
, cond_stmt
);
1438 dcall_bb
= e_cd
->dest
;
1439 dcall_bb
->count
= count
;
1441 e_di
= split_block (dcall_bb
, dcall_stmt
);
1442 icall_bb
= e_di
->dest
;
1443 icall_bb
->count
= all
- count
;
1445 /* Do not disturb existing EH edges from the indirect call. */
1446 if (!stmt_ends_bb_p (icall_stmt
))
1447 e_ij
= split_block (icall_bb
, icall_stmt
);
1450 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1451 /* The indirect call might be noreturn. */
1454 e_ij
->probability
= REG_BR_PROB_BASE
;
1455 e_ij
->count
= all
- count
;
1456 e_ij
= single_pred_edge (split_edge (e_ij
));
1461 join_bb
= e_ij
->dest
;
1462 join_bb
->count
= all
;
1465 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1466 e_cd
->probability
= prob
;
1467 e_cd
->count
= count
;
1469 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1470 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1471 e_ci
->count
= all
- count
;
1477 if ((dflags
& ECF_NORETURN
) != 0)
1481 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1482 e_dj
->probability
= REG_BR_PROB_BASE
;
1483 e_dj
->count
= count
;
1485 e_ij
->count
= all
- count
;
1487 e_ij
->probability
= REG_BR_PROB_BASE
;
1490 /* Insert PHI node for the call result if necessary. */
1491 if (gimple_call_lhs (icall_stmt
)
1492 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1493 && (dflags
& ECF_NORETURN
) == 0)
1495 tree result
= gimple_call_lhs (icall_stmt
);
1496 gphi
*phi
= create_phi_node (result
, join_bb
);
1497 gimple_call_set_lhs (icall_stmt
,
1498 duplicate_ssa_name (result
, icall_stmt
));
1499 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1500 gimple_call_set_lhs (dcall_stmt
,
1501 duplicate_ssa_name (result
, dcall_stmt
));
1502 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1504 /* If indirect call has following BUILT_IN_CHKP_BNDRET
1505 call then we need to make it's copy for the direct
1509 if (gimple_call_lhs (iretbnd_stmt
))
1513 gimple_set_vdef (iretbnd_stmt
, NULL_TREE
);
1514 gimple_set_vuse (iretbnd_stmt
, NULL_TREE
);
1515 update_stmt (iretbnd_stmt
);
1517 result
= gimple_call_lhs (iretbnd_stmt
);
1518 phi
= create_phi_node (result
, join_bb
);
1520 copy
= gimple_copy (iretbnd_stmt
);
1521 gimple_call_set_arg (copy
, 0,
1522 gimple_call_lhs (dcall_stmt
));
1523 gimple_call_set_lhs (copy
, duplicate_ssa_name (result
, copy
));
1524 gsi_insert_on_edge (e_dj
, copy
);
1525 add_phi_arg (phi
, gimple_call_lhs (copy
),
1526 e_dj
, UNKNOWN_LOCATION
);
1528 gimple_call_set_arg (iretbnd_stmt
, 0,
1529 gimple_call_lhs (icall_stmt
));
1530 gimple_call_set_lhs (iretbnd_stmt
,
1531 duplicate_ssa_name (result
, iretbnd_stmt
));
1532 psi
= gsi_for_stmt (iretbnd_stmt
);
1533 gsi_remove (&psi
, false);
1534 gsi_insert_on_edge (e_ij
, iretbnd_stmt
);
1535 add_phi_arg (phi
, gimple_call_lhs (iretbnd_stmt
),
1536 e_ij
, UNKNOWN_LOCATION
);
1538 gsi_commit_one_edge_insert (e_dj
, NULL
);
1539 gsi_commit_one_edge_insert (e_ij
, NULL
);
1543 psi
= gsi_for_stmt (iretbnd_stmt
);
1544 gsi_remove (&psi
, true);
1549 /* Build an EH edge for the direct call if necessary. */
1550 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1551 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1553 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1556 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1557 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1559 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1560 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1561 !gsi_end_p (psi
); gsi_next (&psi
))
1563 gphi
*phi
= psi
.phi ();
1564 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1565 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1572 For every checked indirect/virtual call determine if most common pid of
1573 function/class method has probability more than 50%. If yes modify code of
1578 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1581 histogram_value histogram
;
1582 gcov_type val
, count
, all
, bb_all
;
1583 struct cgraph_node
*direct_call
;
1585 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1589 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1592 if (gimple_call_internal_p (stmt
))
1595 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1599 val
= histogram
->hvalue
.counters
[0];
1600 count
= histogram
->hvalue
.counters
[1];
1601 all
= histogram
->hvalue
.counters
[2];
1603 bb_all
= gimple_bb (stmt
)->count
;
1604 /* The order of CHECK_COUNTER calls is important -
1605 since check_counter can correct the third parameter
1606 and we want to make count <= all <= bb_all. */
1607 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1608 || check_counter (stmt
, "ic", &count
, &all
, all
))
1610 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1614 if (4 * count
<= 3 * all
)
1617 direct_call
= find_func_by_profile_id ((int)val
);
1619 if (direct_call
== NULL
)
1625 fprintf (dump_file
, "Indirect call -> direct call from other module");
1626 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1627 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1633 if (!check_ic_target (stmt
, direct_call
))
1637 fprintf (dump_file
, "Indirect call -> direct call ");
1638 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1639 fprintf (dump_file
, "=> ");
1640 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1641 fprintf (dump_file
, " transformation skipped because of type mismatch");
1642 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1644 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1650 fprintf (dump_file
, "Indirect call -> direct call ");
1651 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1652 fprintf (dump_file
, "=> ");
1653 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1654 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1655 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1656 fprintf (dump_file
, "hist->count %"PRId64
1657 " hist->all %"PRId64
"\n", count
, all
);
1663 /* Return true if the stringop CALL with FNDECL shall be profiled.
1664 SIZE_ARG be set to the argument index for the size of the string
1668 interesting_stringop_to_profile_p (tree fndecl
, gcall
*call
, int *size_arg
)
1670 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1672 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1673 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1678 case BUILT_IN_MEMCPY
:
1679 case BUILT_IN_MEMPCPY
:
1681 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1682 INTEGER_TYPE
, VOID_TYPE
);
1683 case BUILT_IN_MEMSET
:
1685 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1686 INTEGER_TYPE
, VOID_TYPE
);
1687 case BUILT_IN_BZERO
:
1689 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1696 /* Convert stringop (..., vcall_size)
1698 if (vcall_size == icall_size)
1699 stringop (..., icall_size);
1701 stringop (..., vcall_size);
1702 assuming we'll propagate a true constant into ICALL_SIZE later. */
1705 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, int prob
,
1706 gcov_type count
, gcov_type all
)
1711 tree tmp0
, tmp1
, vcall_size
, optype
;
1712 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1713 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1714 gimple_stmt_iterator gsi
;
1718 fndecl
= gimple_call_fndecl (vcall_stmt
);
1719 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1722 cond_bb
= gimple_bb (vcall_stmt
);
1723 gsi
= gsi_for_stmt (vcall_stmt
);
1725 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1726 optype
= TREE_TYPE (vcall_size
);
1728 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1729 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1730 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1731 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1733 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1734 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1736 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1737 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1739 gimple_set_vdef (vcall_stmt
, NULL
);
1740 gimple_set_vuse (vcall_stmt
, NULL
);
1741 update_stmt (vcall_stmt
);
1742 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1743 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1744 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1747 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1748 e_ci
= split_block (cond_bb
, cond_stmt
);
1749 icall_bb
= e_ci
->dest
;
1750 icall_bb
->count
= count
;
1752 e_iv
= split_block (icall_bb
, icall_stmt
);
1753 vcall_bb
= e_iv
->dest
;
1754 vcall_bb
->count
= all
- count
;
1756 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1757 join_bb
= e_vj
->dest
;
1758 join_bb
->count
= all
;
1760 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1761 e_ci
->probability
= prob
;
1762 e_ci
->count
= count
;
1764 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1765 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1766 e_cv
->count
= all
- count
;
1770 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1771 e_ij
->probability
= REG_BR_PROB_BASE
;
1772 e_ij
->count
= count
;
1774 e_vj
->probability
= REG_BR_PROB_BASE
;
1775 e_vj
->count
= all
- count
;
1777 /* Insert PHI node for the call result if necessary. */
1778 if (gimple_call_lhs (vcall_stmt
)
1779 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1781 tree result
= gimple_call_lhs (vcall_stmt
);
1782 gphi
*phi
= create_phi_node (result
, join_bb
);
1783 gimple_call_set_lhs (vcall_stmt
,
1784 duplicate_ssa_name (result
, vcall_stmt
));
1785 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1786 gimple_call_set_lhs (icall_stmt
,
1787 duplicate_ssa_name (result
, icall_stmt
));
1788 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1791 /* Because these are all string op builtins, they're all nothrow. */
1792 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1793 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1796 /* Find values inside STMT for that we want to measure histograms for
1797 division/modulo optimization. */
1799 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1804 enum built_in_function fcode
;
1805 histogram_value histogram
;
1806 gcov_type count
, all
, val
;
1808 unsigned int dest_align
, src_align
;
1813 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1816 fndecl
= gimple_call_fndecl (stmt
);
1819 fcode
= DECL_FUNCTION_CODE (fndecl
);
1820 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1823 blck_size
= gimple_call_arg (stmt
, size_arg
);
1824 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1827 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1830 val
= histogram
->hvalue
.counters
[0];
1831 count
= histogram
->hvalue
.counters
[1];
1832 all
= histogram
->hvalue
.counters
[2];
1833 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1834 /* We require that count is at least half of all; this means
1835 that for the transformation to fire the value must be constant
1836 at least 80% of time. */
1837 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1839 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1842 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1845 dest
= gimple_call_arg (stmt
, 0);
1846 dest_align
= get_pointer_alignment (dest
);
1849 case BUILT_IN_MEMCPY
:
1850 case BUILT_IN_MEMPCPY
:
1851 src
= gimple_call_arg (stmt
, 1);
1852 src_align
= get_pointer_alignment (src
);
1853 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1856 case BUILT_IN_MEMSET
:
1857 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1858 gimple_call_arg (stmt
, 1),
1862 case BUILT_IN_BZERO
:
1863 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1871 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1872 tree_val
= build_int_cst (get_gcov_type (), val
);
1876 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1877 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1879 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1880 TYPE_PRECISION (get_gcov_type ()), false));
1885 fprintf (dump_file
, "Single value %i stringop transformation on ",
1887 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1889 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1895 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1896 HOST_WIDE_INT
*expected_size
)
1898 histogram_value histogram
;
1899 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1901 *expected_size
= -1;
1902 else if (!histogram
->hvalue
.counters
[1])
1904 *expected_size
= -1;
1905 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1910 size
= ((histogram
->hvalue
.counters
[0]
1911 + histogram
->hvalue
.counters
[1] / 2)
1912 / histogram
->hvalue
.counters
[1]);
1913 /* Even if we can hold bigger value in SIZE, INT_MAX
1914 is safe "infinity" for code generation strategies. */
1917 *expected_size
= size
;
1918 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1920 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1922 *expected_align
= 0;
1923 else if (!histogram
->hvalue
.counters
[0])
1925 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1926 *expected_align
= 0;
1933 count
= histogram
->hvalue
.counters
[0];
1935 while (!(count
& alignment
)
1936 && (alignment
* 2 * BITS_PER_UNIT
))
1938 *expected_align
= alignment
* BITS_PER_UNIT
;
1939 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1944 /* Find values inside STMT for that we want to measure histograms for
1945 division/modulo optimization. */
1947 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1949 tree lhs
, divisor
, op0
, type
;
1950 histogram_value hist
;
1952 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1955 lhs
= gimple_assign_lhs (stmt
);
1956 type
= TREE_TYPE (lhs
);
1957 if (!INTEGRAL_TYPE_P (type
))
1960 switch (gimple_assign_rhs_code (stmt
))
1962 case TRUNC_DIV_EXPR
:
1963 case TRUNC_MOD_EXPR
:
1964 divisor
= gimple_assign_rhs2 (stmt
);
1965 op0
= gimple_assign_rhs1 (stmt
);
1967 values
->reserve (3);
1969 if (TREE_CODE (divisor
) == SSA_NAME
)
1970 /* Check for the case where the divisor is the same value most
1972 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1973 HIST_TYPE_SINGLE_VALUE
,
1976 /* For mod, check whether it is not often a noop (or replaceable by
1977 a few subtractions). */
1978 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1979 && TYPE_UNSIGNED (type
))
1982 /* Check for a special case where the divisor is power of 2. */
1983 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1987 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1988 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1990 hist
->hdata
.intvl
.int_start
= 0;
1991 hist
->hdata
.intvl
.steps
= 2;
1992 values
->quick_push (hist
);
2001 /* Find calls inside STMT for that we want to measure histograms for
2002 indirect/virtual call optimization. */
2005 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
2009 if (gimple_code (stmt
) != GIMPLE_CALL
2010 || gimple_call_internal_p (stmt
)
2011 || gimple_call_fndecl (stmt
) != NULL_TREE
)
2014 callee
= gimple_call_fn (stmt
);
2016 values
->reserve (3);
2018 values
->quick_push (gimple_alloc_histogram_value (
2020 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
2021 HIST_TYPE_INDIR_CALL_TOPN
:
2022 HIST_TYPE_INDIR_CALL
,
2028 /* Find values inside STMT for that we want to measure histograms for
2029 string operations. */
2031 gimple_stringops_values_to_profile (gimple gs
, histogram_values
*values
)
2039 stmt
= dyn_cast
<gcall
*> (gs
);
2042 fndecl
= gimple_call_fndecl (stmt
);
2046 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
2049 dest
= gimple_call_arg (stmt
, 0);
2050 blck_size
= gimple_call_arg (stmt
, size_arg
);
2052 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2054 values
->safe_push (gimple_alloc_histogram_value (cfun
,
2055 HIST_TYPE_SINGLE_VALUE
,
2057 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
2060 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2061 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
2065 /* Find values inside STMT for that we want to measure histograms and adds
2066 them to list VALUES. */
2069 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
2071 gimple_divmod_values_to_profile (stmt
, values
);
2072 gimple_stringops_values_to_profile (stmt
, values
);
2073 gimple_indirect_call_to_profile (stmt
, values
);
2077 gimple_find_values_to_profile (histogram_values
*values
)
2080 gimple_stmt_iterator gsi
;
2082 histogram_value hist
= NULL
;
2085 FOR_EACH_BB_FN (bb
, cfun
)
2086 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2087 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2089 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2091 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2095 case HIST_TYPE_INTERVAL
:
2096 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2099 case HIST_TYPE_POW2
:
2100 hist
->n_counters
= 2;
2103 case HIST_TYPE_SINGLE_VALUE
:
2104 hist
->n_counters
= 3;
2107 case HIST_TYPE_CONST_DELTA
:
2108 hist
->n_counters
= 4;
2111 case HIST_TYPE_INDIR_CALL
:
2112 hist
->n_counters
= 3;
2115 case HIST_TYPE_TIME_PROFILE
:
2116 hist
->n_counters
= 1;
2119 case HIST_TYPE_AVERAGE
:
2120 hist
->n_counters
= 2;
2124 hist
->n_counters
= 1;
2127 case HIST_TYPE_INDIR_CALL_TOPN
:
2128 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2136 fprintf (dump_file
, "Stmt ");
2137 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2138 dump_histogram_value (dump_file
, hist
);