1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
25 #include "tree-nested.h"
29 #include "hard-reg-set.h"
37 #include "dominance.h"
39 #include "basic-block.h"
40 #include "value-prof.h"
42 #include "insn-config.h"
46 #include "tree-ssa-alias.h"
47 #include "internal-fn.h"
49 #include "gimple-expr.h"
53 #include "gimple-iterator.h"
54 #include "gimple-ssa.h"
56 #include "tree-phinodes.h"
57 #include "ssa-iterators.h"
58 #include "stringpool.h"
59 #include "tree-ssanames.h"
60 #include "diagnostic.h"
61 #include "gimple-pretty-print.h"
68 #include "data-streamer.h"
70 #include "tree-nested.h"
73 /* In this file value profile based optimizations are placed. Currently the
74 following optimizations are implemented (for more detailed descriptions
75 see comments at value_profile_transformations):
77 1) Division/modulo specialization. Provided that we can determine that the
78 operands of the division have some special properties, we may use it to
79 produce more effective code.
81 2) Indirect/virtual call specialization. If we can determine most
82 common function callee in indirect/virtual call. We can use this
83 information to improve code effectiveness (especially info for
86 3) Speculative prefetching. If we are able to determine that the difference
87 between addresses accessed by a memory reference is usually constant, we
88 may add the prefetch instructions.
89 FIXME: This transformation was removed together with RTL based value
93 Value profiling internals
94 ==========================
96 Every value profiling transformation starts with defining what values
97 to profile. There are different histogram types (see HIST_TYPE_* in
98 value-prof.h) and each transformation can request one or more histogram
99 types per GIMPLE statement. The function gimple_find_values_to_profile()
100 collects the values to profile in a vec, and adds the number of counters
101 required for the different histogram types.
103 For a -fprofile-generate run, the statements for which values should be
104 recorded, are instrumented in instrument_values(). The instrumentation
105 is done by helper functions that can be found in tree-profile.c, where
106 new types of histograms can be added if necessary.
108 After a -fprofile-use, the value profiling data is read back in by
109 compute_value_histograms() that translates the collected data to
110 histograms and attaches them to the profiled statements via
111 gimple_add_histogram_value(). Histograms are stored in a hash table
112 that is attached to every intrumented function, see VALUE_HISTOGRAMS
115 The value-profile transformations driver is the function
116 gimple_value_profile_transformations(). It traverses all statements in
117 the to-be-transformed function, and looks for statements with one or
118 more histograms attached to it. If a statement has histograms, the
119 transformation functions are called on the statement.
121 Limitations / FIXME / TODO:
122 * Only one histogram of each type can be associated with a statement.
123 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
124 (This type of histogram was originally used to implement a form of
125 stride profiling based speculative prefetching to improve SPEC2000
126 scores for memory-bound benchmarks, mcf and equake. However, this
127 was an RTL value-profiling transformation, and those have all been
129 * Some value profile transformations are done in builtins.c (?!)
130 * Updating of histograms needs some TLC.
131 * The value profiling code could be used to record analysis results
132 from non-profiling (e.g. VRP).
133 * Adding new profilers should be simplified, starting with a cleanup
134 of what-happens-where andwith making gimple_find_values_to_profile
135 and gimple_value_profile_transformations table-driven, perhaps...
138 static tree
gimple_divmod_fixed_value (gimple
, tree
, int, gcov_type
, gcov_type
);
139 static tree
gimple_mod_pow2 (gimple
, int, gcov_type
, gcov_type
);
140 static tree
gimple_mod_subtract (gimple
, int, int, int, gcov_type
, gcov_type
,
142 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
143 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
144 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
145 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
146 static bool gimple_ic_transform (gimple_stmt_iterator
*);
148 /* Allocate histogram value. */
151 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
152 enum hist_type type
, gimple stmt
, tree value
)
154 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
155 hist
->hvalue
.value
= value
;
156 hist
->hvalue
.stmt
= stmt
;
161 /* Hash value for histogram. */
164 histogram_hash (const void *x
)
166 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
169 /* Return nonzero if statement for histogram_value X is Y. */
172 histogram_eq (const void *x
, const void *y
)
174 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
177 /* Set histogram for STMT. */
180 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
183 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
185 if (!VALUE_HISTOGRAMS (fun
))
186 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
188 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
189 htab_hash_pointer (stmt
),
190 hist
? INSERT
: NO_INSERT
);
194 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
200 /* Get histogram list for STMT. */
203 gimple_histogram_value (struct function
*fun
, gimple stmt
)
205 if (!VALUE_HISTOGRAMS (fun
))
207 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
208 htab_hash_pointer (stmt
));
211 /* Add histogram for STMT. */
214 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
215 histogram_value hist
)
217 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
218 set_histogram_value (fun
, stmt
, hist
);
223 /* Remove histogram HIST from STMT's histogram list. */
226 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
227 histogram_value hist
)
229 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
232 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
236 while (hist2
->hvalue
.next
!= hist
)
237 hist2
= hist2
->hvalue
.next
;
238 hist2
->hvalue
.next
= hist
->hvalue
.next
;
240 free (hist
->hvalue
.counters
);
241 #ifdef ENABLE_CHECKING
242 memset (hist
, 0xab, sizeof (*hist
));
248 /* Lookup histogram of type TYPE in the STMT. */
251 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
254 histogram_value hist
;
255 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
256 hist
= hist
->hvalue
.next
)
257 if (hist
->type
== type
)
262 /* Dump information about HIST to DUMP_FILE. */
265 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
269 case HIST_TYPE_INTERVAL
:
270 fprintf (dump_file
, "Interval counter range %d -- %d",
271 hist
->hdata
.intvl
.int_start
,
272 (hist
->hdata
.intvl
.int_start
273 + hist
->hdata
.intvl
.steps
- 1));
274 if (hist
->hvalue
.counters
)
277 fprintf (dump_file
, " [");
278 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
279 fprintf (dump_file
, " %d:%"PRId64
,
280 hist
->hdata
.intvl
.int_start
+ i
,
281 (int64_t) hist
->hvalue
.counters
[i
]);
282 fprintf (dump_file
, " ] outside range:%"PRId64
,
283 (int64_t) hist
->hvalue
.counters
[i
]);
285 fprintf (dump_file
, ".\n");
289 fprintf (dump_file
, "Pow2 counter ");
290 if (hist
->hvalue
.counters
)
292 fprintf (dump_file
, "pow2:%"PRId64
294 (int64_t) hist
->hvalue
.counters
[0],
295 (int64_t) hist
->hvalue
.counters
[1]);
297 fprintf (dump_file
, ".\n");
300 case HIST_TYPE_SINGLE_VALUE
:
301 fprintf (dump_file
, "Single value ");
302 if (hist
->hvalue
.counters
)
304 fprintf (dump_file
, "value:%"PRId64
307 (int64_t) hist
->hvalue
.counters
[0],
308 (int64_t) hist
->hvalue
.counters
[1],
309 (int64_t) hist
->hvalue
.counters
[2]);
311 fprintf (dump_file
, ".\n");
314 case HIST_TYPE_AVERAGE
:
315 fprintf (dump_file
, "Average value ");
316 if (hist
->hvalue
.counters
)
318 fprintf (dump_file
, "sum:%"PRId64
320 (int64_t) hist
->hvalue
.counters
[0],
321 (int64_t) hist
->hvalue
.counters
[1]);
323 fprintf (dump_file
, ".\n");
327 fprintf (dump_file
, "IOR value ");
328 if (hist
->hvalue
.counters
)
330 fprintf (dump_file
, "ior:%"PRId64
,
331 (int64_t) hist
->hvalue
.counters
[0]);
333 fprintf (dump_file
, ".\n");
336 case HIST_TYPE_CONST_DELTA
:
337 fprintf (dump_file
, "Constant delta ");
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_INDIR_CALL
:
350 fprintf (dump_file
, "Indirect call ");
351 if (hist
->hvalue
.counters
)
353 fprintf (dump_file
, "value:%"PRId64
356 (int64_t) hist
->hvalue
.counters
[0],
357 (int64_t) hist
->hvalue
.counters
[1],
358 (int64_t) hist
->hvalue
.counters
[2]);
360 fprintf (dump_file
, ".\n");
362 case HIST_TYPE_TIME_PROFILE
:
363 fprintf (dump_file
, "Time profile ");
364 if (hist
->hvalue
.counters
)
366 fprintf (dump_file
, "time:%"PRId64
,
367 (int64_t) hist
->hvalue
.counters
[0]);
369 fprintf (dump_file
, ".\n");
371 case HIST_TYPE_INDIR_CALL_TOPN
:
372 fprintf (dump_file
, "Indirect call topn ");
373 if (hist
->hvalue
.counters
)
377 fprintf (dump_file
, "accu:%"PRId64
, hist
->hvalue
.counters
[0]);
378 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
380 fprintf (dump_file
, " target:%"PRId64
" value:%"PRId64
,
381 (int64_t) hist
->hvalue
.counters
[i
],
382 (int64_t) hist
->hvalue
.counters
[i
+1]);
385 fprintf (dump_file
, ".\n");
392 /* Dump information about HIST to DUMP_FILE. */
395 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
400 bp
= bitpack_create (ob
->main_stream
);
401 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
402 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
403 streamer_write_bitpack (&bp
);
406 case HIST_TYPE_INTERVAL
:
407 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
408 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
413 for (i
= 0; i
< hist
->n_counters
; i
++)
414 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
415 if (hist
->hvalue
.next
)
416 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
418 /* Dump information about HIST to DUMP_FILE. */
421 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
424 unsigned int ncounters
= 0;
427 histogram_value new_val
;
429 histogram_value
*next_p
= NULL
;
433 bp
= streamer_read_bitpack (ib
);
434 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
435 next
= bp_unpack_value (&bp
, 1);
436 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
439 case HIST_TYPE_INTERVAL
:
440 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
441 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
442 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
446 case HIST_TYPE_AVERAGE
:
450 case HIST_TYPE_SINGLE_VALUE
:
451 case HIST_TYPE_INDIR_CALL
:
455 case HIST_TYPE_CONST_DELTA
:
460 case HIST_TYPE_TIME_PROFILE
:
464 case HIST_TYPE_INDIR_CALL_TOPN
:
465 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
471 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
472 new_val
->n_counters
= ncounters
;
473 for (i
= 0; i
< ncounters
; i
++)
474 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
476 gimple_add_histogram_value (cfun
, stmt
, new_val
);
479 next_p
= &new_val
->hvalue
.next
;
484 /* Dump all histograms attached to STMT to DUMP_FILE. */
487 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
489 histogram_value hist
;
490 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
491 dump_histogram_value (dump_file
, hist
);
494 /* Remove all histograms associated with STMT. */
497 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
500 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
501 gimple_remove_histogram_value (fun
, stmt
, val
);
504 /* Duplicate all histograms associates with OSTMT to STMT. */
507 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
508 struct function
*ofun
, gimple ostmt
)
511 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
513 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
514 memcpy (new_val
, val
, sizeof (*val
));
515 new_val
->hvalue
.stmt
= stmt
;
516 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
517 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
518 gimple_add_histogram_value (fun
, stmt
, new_val
);
523 /* Move all histograms associated with OSTMT to STMT. */
526 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
528 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
531 /* The following three statements can't be reordered,
532 because histogram hashtab relies on stmt field value
533 for finding the exact slot. */
534 set_histogram_value (fun
, ostmt
, NULL
);
535 for (; val
!= NULL
; val
= val
->hvalue
.next
)
536 val
->hvalue
.stmt
= stmt
;
537 set_histogram_value (fun
, stmt
, val
);
541 static bool error_found
= false;
543 /* Helper function for verify_histograms. For each histogram reachable via htab
544 walk verify that it was reached via statement walk. */
547 visit_hist (void **slot
, void *data
)
549 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
550 histogram_value hist
= *(histogram_value
*) slot
;
552 if (!visited
->contains (hist
)
553 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
555 error ("dead histogram");
556 dump_histogram_value (stderr
, hist
);
557 debug_gimple_stmt (hist
->hvalue
.stmt
);
564 /* Verify sanity of the histograms. */
567 verify_histograms (void)
570 gimple_stmt_iterator gsi
;
571 histogram_value hist
;
574 hash_set
<histogram_value
> visited_hists
;
575 FOR_EACH_BB_FN (bb
, cfun
)
576 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
578 gimple stmt
= gsi_stmt (gsi
);
580 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
581 hist
= hist
->hvalue
.next
)
583 if (hist
->hvalue
.stmt
!= stmt
)
585 error ("Histogram value statement does not correspond to "
586 "the statement it is associated with");
587 debug_gimple_stmt (stmt
);
588 dump_histogram_value (stderr
, hist
);
591 visited_hists
.add (hist
);
594 if (VALUE_HISTOGRAMS (cfun
))
595 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
597 internal_error ("verify_histograms failed");
600 /* Helper function for verify_histograms. For each histogram reachable via htab
601 walk verify that it was reached via statement walk. */
604 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
606 histogram_value hist
= *(histogram_value
*) slot
;
607 free (hist
->hvalue
.counters
);
608 #ifdef ENABLE_CHECKING
609 memset (hist
, 0xab, sizeof (*hist
));
616 free_histograms (void)
618 if (VALUE_HISTOGRAMS (cfun
))
620 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
621 htab_delete (VALUE_HISTOGRAMS (cfun
));
622 VALUE_HISTOGRAMS (cfun
) = NULL
;
627 /* The overall number of invocations of the counter should match
628 execution count of basic block. Report it as error rather than
629 internal error as it might mean that user has misused the profile
633 check_counter (gimple stmt
, const char * name
,
634 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
636 if (*all
!= bb_count
|| *count
> *all
)
639 locus
= (stmt
!= NULL
)
640 ? gimple_location (stmt
)
641 : DECL_SOURCE_LOCATION (current_function_decl
);
642 if (flag_profile_correction
)
644 if (dump_enabled_p ())
645 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
646 "correcting inconsistent value profile: %s "
647 "profiler overall count (%d) does not match BB "
648 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
656 error_at (locus
, "corrupted value profile: %s "
657 "profile counter (%d out of %d) inconsistent with "
658 "basic-block count (%d)",
671 /* GIMPLE based transformations. */
674 gimple_value_profile_transformations (void)
677 gimple_stmt_iterator gsi
;
678 bool changed
= false;
680 FOR_EACH_BB_FN (bb
, cfun
)
682 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
684 gimple stmt
= gsi_stmt (gsi
);
685 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
691 fprintf (dump_file
, "Trying transformations on stmt ");
692 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
693 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
696 /* Transformations: */
697 /* The order of things in this conditional controls which
698 transformation is used when more than one is applicable. */
699 /* It is expected that any code added by the transformations
700 will be added before the current statement, and that the
701 current statement remain valid (although possibly
702 modified) upon return. */
703 if (gimple_mod_subtract_transform (&gsi
)
704 || gimple_divmod_fixed_value_transform (&gsi
)
705 || gimple_mod_pow2_value_transform (&gsi
)
706 || gimple_stringops_transform (&gsi
)
707 || gimple_ic_transform (&gsi
))
709 stmt
= gsi_stmt (gsi
);
711 /* Original statement may no longer be in the same block. */
712 if (bb
!= gimple_bb (stmt
))
714 bb
= gimple_bb (stmt
);
715 gsi
= gsi_for_stmt (stmt
);
730 /* Generate code for transformation 1 (with parent gimple assignment
731 STMT and probability of taking the optimal path PROB, which is
732 equivalent to COUNT/ALL within roundoff error). This generates the
733 result into a temp and returns the temp; it does not replace or
734 alter the original STMT. */
737 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
740 gimple stmt1
, stmt2
, stmt3
;
741 tree tmp0
, tmp1
, tmp2
;
742 gimple bb1end
, bb2end
, bb3end
;
743 basic_block bb
, bb2
, bb3
, bb4
;
744 tree optype
, op1
, op2
;
745 edge e12
, e13
, e23
, e24
, e34
;
746 gimple_stmt_iterator gsi
;
748 gcc_assert (is_gimple_assign (stmt
)
749 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
750 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
752 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
753 op1
= gimple_assign_rhs1 (stmt
);
754 op2
= gimple_assign_rhs2 (stmt
);
756 bb
= gimple_bb (stmt
);
757 gsi
= gsi_for_stmt (stmt
);
759 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
760 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
761 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
762 stmt2
= gimple_build_assign (tmp1
, op2
);
763 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
764 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
765 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
766 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
769 tmp2
= create_tmp_reg (optype
, "PROF");
770 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
772 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
775 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
777 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
781 /* Edge e23 connects bb2 to bb3, etc. */
782 e12
= split_block (bb
, bb1end
);
785 e23
= split_block (bb2
, bb2end
);
787 bb3
->count
= all
- count
;
788 e34
= split_block (bb3
, bb3end
);
792 e12
->flags
&= ~EDGE_FALLTHRU
;
793 e12
->flags
|= EDGE_FALSE_VALUE
;
794 e12
->probability
= prob
;
797 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
798 e13
->probability
= REG_BR_PROB_BASE
- prob
;
799 e13
->count
= all
- count
;
803 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
804 e24
->probability
= REG_BR_PROB_BASE
;
807 e34
->probability
= REG_BR_PROB_BASE
;
808 e34
->count
= all
- count
;
814 /* Do transform 1) on INSN if applicable. */
817 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
819 histogram_value histogram
;
821 gcov_type val
, count
, all
;
822 tree result
, value
, tree_val
;
826 stmt
= gsi_stmt (*si
);
827 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
830 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
833 code
= gimple_assign_rhs_code (stmt
);
835 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
838 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
839 HIST_TYPE_SINGLE_VALUE
);
843 value
= histogram
->hvalue
.value
;
844 val
= histogram
->hvalue
.counters
[0];
845 count
= histogram
->hvalue
.counters
[1];
846 all
= histogram
->hvalue
.counters
[2];
847 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
849 /* We require that count is at least half of all; this means
850 that for the transformation to fire the value must be constant
851 at least 50% of time (and 75% gives the guarantee of usage). */
852 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
854 || optimize_bb_for_size_p (gimple_bb (stmt
)))
857 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
860 /* Compute probability of taking the optimal path. */
862 prob
= GCOV_COMPUTE_SCALE (count
, all
);
866 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
867 tree_val
= build_int_cst (get_gcov_type (), val
);
871 a
[0] = (unsigned HOST_WIDE_INT
) val
;
872 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
874 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
875 TYPE_PRECISION (get_gcov_type ()), false));
877 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
881 fprintf (dump_file
, "Div/mod by constant ");
882 print_generic_expr (dump_file
, value
, TDF_SLIM
);
883 fprintf (dump_file
, "=");
884 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
885 fprintf (dump_file
, " transformation on insn ");
886 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
889 gimple_assign_set_rhs_from_tree (si
, result
);
890 update_stmt (gsi_stmt (*si
));
895 /* Generate code for transformation 2 (with parent gimple assign STMT and
896 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
897 within roundoff error). This generates the result into a temp and returns
898 the temp; it does not replace or alter the original STMT. */
900 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
902 gimple stmt1
, stmt2
, stmt3
, stmt4
;
904 gimple bb1end
, bb2end
, bb3end
;
905 basic_block bb
, bb2
, bb3
, bb4
;
906 tree optype
, op1
, op2
;
907 edge e12
, e13
, e23
, e24
, e34
;
908 gimple_stmt_iterator gsi
;
911 gcc_assert (is_gimple_assign (stmt
)
912 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
914 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
915 op1
= gimple_assign_rhs1 (stmt
);
916 op2
= gimple_assign_rhs2 (stmt
);
918 bb
= gimple_bb (stmt
);
919 gsi
= gsi_for_stmt (stmt
);
921 result
= create_tmp_reg (optype
, "PROF");
922 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
923 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
924 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
925 build_int_cst (optype
, -1));
926 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
927 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
928 NULL_TREE
, NULL_TREE
);
929 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
930 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
931 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
934 /* tmp2 == op2-1 inherited from previous block. */
935 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
936 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
939 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
941 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
945 /* Edge e23 connects bb2 to bb3, etc. */
946 e12
= split_block (bb
, bb1end
);
949 e23
= split_block (bb2
, bb2end
);
951 bb3
->count
= all
- count
;
952 e34
= split_block (bb3
, bb3end
);
956 e12
->flags
&= ~EDGE_FALLTHRU
;
957 e12
->flags
|= EDGE_FALSE_VALUE
;
958 e12
->probability
= prob
;
961 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
962 e13
->probability
= REG_BR_PROB_BASE
- prob
;
963 e13
->count
= all
- count
;
967 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
968 e24
->probability
= REG_BR_PROB_BASE
;
971 e34
->probability
= REG_BR_PROB_BASE
;
972 e34
->count
= all
- count
;
977 /* Do transform 2) on INSN if applicable. */
979 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
981 histogram_value histogram
;
983 gcov_type count
, wrong_values
, all
;
984 tree lhs_type
, result
, value
;
988 stmt
= gsi_stmt (*si
);
989 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
992 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
993 if (!INTEGRAL_TYPE_P (lhs_type
))
996 code
= gimple_assign_rhs_code (stmt
);
998 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1001 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
1005 value
= histogram
->hvalue
.value
;
1006 wrong_values
= histogram
->hvalue
.counters
[0];
1007 count
= histogram
->hvalue
.counters
[1];
1009 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1011 /* We require that we hit a power of 2 at least half of all evaluations. */
1012 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
1013 || count
< wrong_values
1014 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1019 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
1020 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1023 /* Compute probability of taking the optimal path. */
1024 all
= count
+ wrong_values
;
1026 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1030 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1034 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1036 gimple_assign_set_rhs_from_tree (si
, result
);
1037 update_stmt (gsi_stmt (*si
));
1042 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1043 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1044 supported and this is built into this interface. The probabilities of taking
1045 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1046 COUNT2/ALL respectively within roundoff error). This generates the
1047 result into a temp and returns the temp; it does not replace or alter
1048 the original STMT. */
1049 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1052 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
1053 gcov_type count1
, gcov_type count2
, gcov_type all
)
1055 gimple stmt1
, stmt2
, stmt3
;
1057 gimple bb1end
, bb2end
= NULL
, bb3end
;
1058 basic_block bb
, bb2
, bb3
, bb4
;
1059 tree optype
, op1
, op2
;
1060 edge e12
, e23
= 0, e24
, e34
, e14
;
1061 gimple_stmt_iterator gsi
;
1064 gcc_assert (is_gimple_assign (stmt
)
1065 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1067 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1068 op1
= gimple_assign_rhs1 (stmt
);
1069 op2
= gimple_assign_rhs2 (stmt
);
1071 bb
= gimple_bb (stmt
);
1072 gsi
= gsi_for_stmt (stmt
);
1074 result
= create_tmp_reg (optype
, "PROF");
1075 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1076 stmt1
= gimple_build_assign (result
, op1
);
1077 stmt2
= gimple_build_assign (tmp1
, op2
);
1078 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1079 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1080 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1081 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1084 if (ncounts
) /* Assumed to be 0 or 1 */
1086 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
1087 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1088 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1089 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1093 /* Fallback case. */
1094 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
1096 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1100 /* Edge e23 connects bb2 to bb3, etc. */
1101 /* However block 3 is optional; if it is not there, references
1102 to 3 really refer to block 2. */
1103 e12
= split_block (bb
, bb1end
);
1105 bb2
->count
= all
- count1
;
1107 if (ncounts
) /* Assumed to be 0 or 1. */
1109 e23
= split_block (bb2
, bb2end
);
1111 bb3
->count
= all
- count1
- count2
;
1114 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1118 e12
->flags
&= ~EDGE_FALLTHRU
;
1119 e12
->flags
|= EDGE_FALSE_VALUE
;
1120 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1121 e12
->count
= all
- count1
;
1123 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1124 e14
->probability
= prob1
;
1125 e14
->count
= count1
;
1127 if (ncounts
) /* Assumed to be 0 or 1. */
1129 e23
->flags
&= ~EDGE_FALLTHRU
;
1130 e23
->flags
|= EDGE_FALSE_VALUE
;
1131 e23
->count
= all
- count1
- count2
;
1132 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1134 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1135 e24
->probability
= prob2
;
1136 e24
->count
= count2
;
1139 e34
->probability
= REG_BR_PROB_BASE
;
1140 e34
->count
= all
- count1
- count2
;
1146 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1149 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1151 histogram_value histogram
;
1152 enum tree_code code
;
1153 gcov_type count
, wrong_values
, all
;
1154 tree lhs_type
, result
;
1155 gcov_type prob1
, prob2
;
1156 unsigned int i
, steps
;
1157 gcov_type count1
, count2
;
1160 stmt
= gsi_stmt (*si
);
1161 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1164 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1165 if (!INTEGRAL_TYPE_P (lhs_type
))
1168 code
= gimple_assign_rhs_code (stmt
);
1170 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1173 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1179 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1180 all
+= histogram
->hvalue
.counters
[i
];
1182 wrong_values
+= histogram
->hvalue
.counters
[i
];
1183 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1184 steps
= histogram
->hdata
.intvl
.steps
;
1185 all
+= wrong_values
;
1186 count1
= histogram
->hvalue
.counters
[0];
1187 count2
= histogram
->hvalue
.counters
[1];
1189 /* Compute probability of taking the optimal path. */
1190 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1192 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1196 if (flag_profile_correction
&& count1
+ count2
> all
)
1197 all
= count1
+ count2
;
1199 gcc_assert (count1
+ count2
<= all
);
1201 /* We require that we use just subtractions in at least 50% of all
1204 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1206 count
+= histogram
->hvalue
.counters
[i
];
1207 if (count
* 2 >= all
)
1211 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1214 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1217 fprintf (dump_file
, "Mod subtract transformation on insn ");
1218 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1221 /* Compute probability of taking the optimal path(s). */
1224 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1225 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1232 /* In practice, "steps" is always 2. This interface reflects this,
1233 and will need to be changed if "steps" can change. */
1234 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1236 gimple_assign_set_rhs_from_tree (si
, result
);
1237 update_stmt (gsi_stmt (*si
));
1242 struct profile_id_traits
: default_hashmap_traits
1244 template<typename T
>
1248 return e
.m_key
== UINT_MAX
;
1251 template<typename T
> static bool is_empty (T
&e
) { return e
.m_key
== 0; }
1252 template<typename T
> static void mark_deleted (T
&e
) { e
.m_key
= UINT_MAX
; }
1253 template<typename T
> static void mark_empty (T
&e
) { e
.m_key
= 0; }
1256 static hash_map
<unsigned int, cgraph_node
*, profile_id_traits
> *
1257 cgraph_node_map
= 0;
1259 /* Returns true if node graph is initialized. This
1260 is used to test if profile_id has been created
1261 for cgraph_nodes. */
1264 coverage_node_map_initialized_p (void)
1266 return cgraph_node_map
!= 0;
1269 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1270 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1271 that the PROFILE_IDs was already assigned. */
1274 init_node_map (bool local
)
1276 struct cgraph_node
*n
;
1278 = new hash_map
<unsigned int, cgraph_node
*, profile_id_traits
>;
1280 FOR_EACH_DEFINED_FUNCTION (n
)
1281 if (n
->has_gimple_body_p ())
1286 n
->profile_id
= coverage_compute_profile_id (n
);
1287 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1291 fprintf (dump_file
, "Local profile-id %i conflict"
1292 " with nodes %s/%i %s/%i\n",
1298 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1301 else if (!n
->profile_id
)
1305 "Node %s/%i has no profile-id"
1306 " (profile feedback missing?)\n",
1311 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1315 "Node %s/%i has IP profile-id %i conflict. "
1323 cgraph_node_map
->put (n
->profile_id
, n
);
1327 /* Delete the CGRAPH_NODE_MAP. */
1332 delete cgraph_node_map
;
1335 /* Return cgraph node for function with pid */
1338 find_func_by_profile_id (int profile_id
)
1340 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1347 /* Perform sanity check on the indirect call target. Due to race conditions,
1348 false function target may be attributed to an indirect call site. If the
1349 call expression type mismatches with the target function's type, expand_call
1350 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1351 Returns true if TARGET is considered ok for call CALL_STMT. */
1354 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1357 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1360 locus
= gimple_location (call_stmt
);
1361 if (dump_enabled_p ())
1362 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1363 "Skipping target %s with mismatching types for icall\n",
1368 /* Do transformation
1370 if (actual_callee_address == address_of_most_common_function/method)
1377 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1378 int prob
, gcov_type count
, gcov_type all
)
1380 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1381 tree tmp0
, tmp1
, tmp
;
1382 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1383 tree optype
= build_pointer_type (void_type_node
);
1384 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1385 gimple_stmt_iterator gsi
;
1389 gimple_stmt_iterator psi
;
1391 cond_bb
= gimple_bb (icall_stmt
);
1392 gsi
= gsi_for_stmt (icall_stmt
);
1394 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1395 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1396 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1397 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1398 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1400 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1401 current_function_decl
));
1402 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1403 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1405 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1406 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1408 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1409 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1410 update_stmt (icall_stmt
);
1411 dcall_stmt
= gimple_copy (icall_stmt
);
1412 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1413 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1414 if ((dflags
& ECF_NORETURN
) != 0)
1415 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1416 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1419 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1420 e_cd
= split_block (cond_bb
, cond_stmt
);
1421 dcall_bb
= e_cd
->dest
;
1422 dcall_bb
->count
= count
;
1424 e_di
= split_block (dcall_bb
, dcall_stmt
);
1425 icall_bb
= e_di
->dest
;
1426 icall_bb
->count
= all
- count
;
1428 /* Do not disturb existing EH edges from the indirect call. */
1429 if (!stmt_ends_bb_p (icall_stmt
))
1430 e_ij
= split_block (icall_bb
, icall_stmt
);
1433 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1434 /* The indirect call might be noreturn. */
1437 e_ij
->probability
= REG_BR_PROB_BASE
;
1438 e_ij
->count
= all
- count
;
1439 e_ij
= single_pred_edge (split_edge (e_ij
));
1444 join_bb
= e_ij
->dest
;
1445 join_bb
->count
= all
;
1448 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1449 e_cd
->probability
= prob
;
1450 e_cd
->count
= count
;
1452 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1453 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1454 e_ci
->count
= all
- count
;
1460 if ((dflags
& ECF_NORETURN
) != 0)
1464 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1465 e_dj
->probability
= REG_BR_PROB_BASE
;
1466 e_dj
->count
= count
;
1468 e_ij
->count
= all
- count
;
1470 e_ij
->probability
= REG_BR_PROB_BASE
;
1473 /* Insert PHI node for the call result if necessary. */
1474 if (gimple_call_lhs (icall_stmt
)
1475 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1476 && (dflags
& ECF_NORETURN
) == 0)
1478 tree result
= gimple_call_lhs (icall_stmt
);
1479 gimple phi
= create_phi_node (result
, join_bb
);
1480 gimple_call_set_lhs (icall_stmt
,
1481 duplicate_ssa_name (result
, icall_stmt
));
1482 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1483 gimple_call_set_lhs (dcall_stmt
,
1484 duplicate_ssa_name (result
, dcall_stmt
));
1485 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1488 /* Build an EH edge for the direct call if necessary. */
1489 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1490 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1492 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1495 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1496 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1498 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1499 for (psi
= gsi_start_phis (e_eh
->dest
);
1500 !gsi_end_p (psi
); gsi_next (&psi
))
1502 gimple phi
= gsi_stmt (psi
);
1503 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1504 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1511 For every checked indirect/virtual call determine if most common pid of
1512 function/class method has probability more than 50%. If yes modify code of
1517 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1519 gimple stmt
= gsi_stmt (*gsi
);
1520 histogram_value histogram
;
1521 gcov_type val
, count
, all
, bb_all
;
1522 struct cgraph_node
*direct_call
;
1524 if (gimple_code (stmt
) != GIMPLE_CALL
)
1527 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1530 if (gimple_call_internal_p (stmt
))
1533 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1537 val
= histogram
->hvalue
.counters
[0];
1538 count
= histogram
->hvalue
.counters
[1];
1539 all
= histogram
->hvalue
.counters
[2];
1541 bb_all
= gimple_bb (stmt
)->count
;
1542 /* The order of CHECK_COUNTER calls is important -
1543 since check_counter can correct the third parameter
1544 and we want to make count <= all <= bb_all. */
1545 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1546 || check_counter (stmt
, "ic", &count
, &all
, all
))
1548 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1552 if (4 * count
<= 3 * all
)
1555 direct_call
= find_func_by_profile_id ((int)val
);
1557 if (direct_call
== NULL
)
1563 fprintf (dump_file
, "Indirect call -> direct call from other module");
1564 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1565 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1571 if (!check_ic_target (stmt
, direct_call
))
1575 fprintf (dump_file
, "Indirect call -> direct call ");
1576 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1577 fprintf (dump_file
, "=> ");
1578 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1579 fprintf (dump_file
, " transformation skipped because of type mismatch");
1580 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1582 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1588 fprintf (dump_file
, "Indirect call -> direct call ");
1589 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1590 fprintf (dump_file
, "=> ");
1591 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1592 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1593 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1594 fprintf (dump_file
, "hist->count %"PRId64
1595 " hist->all %"PRId64
"\n", count
, all
);
1601 /* Return true if the stringop CALL with FNDECL shall be profiled.
1602 SIZE_ARG be set to the argument index for the size of the string
1606 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1608 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1610 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1611 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1616 case BUILT_IN_MEMCPY
:
1617 case BUILT_IN_MEMPCPY
:
1619 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1620 INTEGER_TYPE
, VOID_TYPE
);
1621 case BUILT_IN_MEMSET
:
1623 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1624 INTEGER_TYPE
, VOID_TYPE
);
1625 case BUILT_IN_BZERO
:
1627 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1634 /* Convert stringop (..., vcall_size)
1636 if (vcall_size == icall_size)
1637 stringop (..., icall_size);
1639 stringop (..., vcall_size);
1640 assuming we'll propagate a true constant into ICALL_SIZE later. */
1643 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1644 gcov_type count
, gcov_type all
)
1646 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1647 tree tmp0
, tmp1
, vcall_size
, optype
;
1648 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1649 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1650 gimple_stmt_iterator gsi
;
1654 fndecl
= gimple_call_fndecl (vcall_stmt
);
1655 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1658 cond_bb
= gimple_bb (vcall_stmt
);
1659 gsi
= gsi_for_stmt (vcall_stmt
);
1661 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1662 optype
= TREE_TYPE (vcall_size
);
1664 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1665 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1666 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1667 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1669 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1670 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1672 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1673 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1675 gimple_set_vdef (vcall_stmt
, NULL
);
1676 gimple_set_vuse (vcall_stmt
, NULL
);
1677 update_stmt (vcall_stmt
);
1678 icall_stmt
= gimple_copy (vcall_stmt
);
1679 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1680 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1683 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1684 e_ci
= split_block (cond_bb
, cond_stmt
);
1685 icall_bb
= e_ci
->dest
;
1686 icall_bb
->count
= count
;
1688 e_iv
= split_block (icall_bb
, icall_stmt
);
1689 vcall_bb
= e_iv
->dest
;
1690 vcall_bb
->count
= all
- count
;
1692 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1693 join_bb
= e_vj
->dest
;
1694 join_bb
->count
= all
;
1696 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1697 e_ci
->probability
= prob
;
1698 e_ci
->count
= count
;
1700 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1701 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1702 e_cv
->count
= all
- count
;
1706 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1707 e_ij
->probability
= REG_BR_PROB_BASE
;
1708 e_ij
->count
= count
;
1710 e_vj
->probability
= REG_BR_PROB_BASE
;
1711 e_vj
->count
= all
- count
;
1713 /* Insert PHI node for the call result if necessary. */
1714 if (gimple_call_lhs (vcall_stmt
)
1715 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1717 tree result
= gimple_call_lhs (vcall_stmt
);
1718 gimple phi
= create_phi_node (result
, join_bb
);
1719 gimple_call_set_lhs (vcall_stmt
,
1720 duplicate_ssa_name (result
, vcall_stmt
));
1721 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1722 gimple_call_set_lhs (icall_stmt
,
1723 duplicate_ssa_name (result
, icall_stmt
));
1724 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1727 /* Because these are all string op builtins, they're all nothrow. */
1728 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1729 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1732 /* Find values inside STMT for that we want to measure histograms for
1733 division/modulo optimization. */
1735 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1737 gimple stmt
= gsi_stmt (*gsi
);
1740 enum built_in_function fcode
;
1741 histogram_value histogram
;
1742 gcov_type count
, all
, val
;
1744 unsigned int dest_align
, src_align
;
1749 if (gimple_code (stmt
) != GIMPLE_CALL
)
1751 fndecl
= gimple_call_fndecl (stmt
);
1754 fcode
= DECL_FUNCTION_CODE (fndecl
);
1755 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1758 blck_size
= gimple_call_arg (stmt
, size_arg
);
1759 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1762 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1765 val
= histogram
->hvalue
.counters
[0];
1766 count
= histogram
->hvalue
.counters
[1];
1767 all
= histogram
->hvalue
.counters
[2];
1768 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1769 /* We require that count is at least half of all; this means
1770 that for the transformation to fire the value must be constant
1771 at least 80% of time. */
1772 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1774 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1777 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1780 dest
= gimple_call_arg (stmt
, 0);
1781 dest_align
= get_pointer_alignment (dest
);
1784 case BUILT_IN_MEMCPY
:
1785 case BUILT_IN_MEMPCPY
:
1786 src
= gimple_call_arg (stmt
, 1);
1787 src_align
= get_pointer_alignment (src
);
1788 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1791 case BUILT_IN_MEMSET
:
1792 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1793 gimple_call_arg (stmt
, 1),
1797 case BUILT_IN_BZERO
:
1798 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1806 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1807 tree_val
= build_int_cst (get_gcov_type (), val
);
1811 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1812 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1814 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1815 TYPE_PRECISION (get_gcov_type ()), false));
1820 fprintf (dump_file
, "Single value %i stringop transformation on ",
1822 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1824 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1830 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1831 HOST_WIDE_INT
*expected_size
)
1833 histogram_value histogram
;
1834 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1836 *expected_size
= -1;
1837 else if (!histogram
->hvalue
.counters
[1])
1839 *expected_size
= -1;
1840 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1845 size
= ((histogram
->hvalue
.counters
[0]
1846 + histogram
->hvalue
.counters
[1] / 2)
1847 / histogram
->hvalue
.counters
[1]);
1848 /* Even if we can hold bigger value in SIZE, INT_MAX
1849 is safe "infinity" for code generation strategies. */
1852 *expected_size
= size
;
1853 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1855 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1857 *expected_align
= 0;
1858 else if (!histogram
->hvalue
.counters
[0])
1860 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1861 *expected_align
= 0;
1868 count
= histogram
->hvalue
.counters
[0];
1870 while (!(count
& alignment
)
1871 && (alignment
* 2 * BITS_PER_UNIT
))
1873 *expected_align
= alignment
* BITS_PER_UNIT
;
1874 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1879 /* Find values inside STMT for that we want to measure histograms for
1880 division/modulo optimization. */
1882 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1884 tree lhs
, divisor
, op0
, type
;
1885 histogram_value hist
;
1887 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1890 lhs
= gimple_assign_lhs (stmt
);
1891 type
= TREE_TYPE (lhs
);
1892 if (!INTEGRAL_TYPE_P (type
))
1895 switch (gimple_assign_rhs_code (stmt
))
1897 case TRUNC_DIV_EXPR
:
1898 case TRUNC_MOD_EXPR
:
1899 divisor
= gimple_assign_rhs2 (stmt
);
1900 op0
= gimple_assign_rhs1 (stmt
);
1902 values
->reserve (3);
1904 if (TREE_CODE (divisor
) == SSA_NAME
)
1905 /* Check for the case where the divisor is the same value most
1907 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1908 HIST_TYPE_SINGLE_VALUE
,
1911 /* For mod, check whether it is not often a noop (or replaceable by
1912 a few subtractions). */
1913 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1914 && TYPE_UNSIGNED (type
))
1917 /* Check for a special case where the divisor is power of 2. */
1918 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1922 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1923 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1925 hist
->hdata
.intvl
.int_start
= 0;
1926 hist
->hdata
.intvl
.steps
= 2;
1927 values
->quick_push (hist
);
1936 /* Find calls inside STMT for that we want to measure histograms for
1937 indirect/virtual call optimization. */
1940 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1944 if (gimple_code (stmt
) != GIMPLE_CALL
1945 || gimple_call_internal_p (stmt
)
1946 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1949 callee
= gimple_call_fn (stmt
);
1951 values
->reserve (3);
1953 values
->quick_push (gimple_alloc_histogram_value (
1955 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
1956 HIST_TYPE_INDIR_CALL_TOPN
:
1957 HIST_TYPE_INDIR_CALL
,
1963 /* Find values inside STMT for that we want to measure histograms for
1964 string operations. */
1966 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1973 if (gimple_code (stmt
) != GIMPLE_CALL
)
1975 fndecl
= gimple_call_fndecl (stmt
);
1979 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1982 dest
= gimple_call_arg (stmt
, 0);
1983 blck_size
= gimple_call_arg (stmt
, size_arg
);
1985 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1987 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1988 HIST_TYPE_SINGLE_VALUE
,
1990 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1993 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1994 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1998 /* Find values inside STMT for that we want to measure histograms and adds
1999 them to list VALUES. */
2002 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
2004 gimple_divmod_values_to_profile (stmt
, values
);
2005 gimple_stringops_values_to_profile (stmt
, values
);
2006 gimple_indirect_call_to_profile (stmt
, values
);
2010 gimple_find_values_to_profile (histogram_values
*values
)
2013 gimple_stmt_iterator gsi
;
2015 histogram_value hist
= NULL
;
2018 FOR_EACH_BB_FN (bb
, cfun
)
2019 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2020 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2022 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2024 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2028 case HIST_TYPE_INTERVAL
:
2029 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2032 case HIST_TYPE_POW2
:
2033 hist
->n_counters
= 2;
2036 case HIST_TYPE_SINGLE_VALUE
:
2037 hist
->n_counters
= 3;
2040 case HIST_TYPE_CONST_DELTA
:
2041 hist
->n_counters
= 4;
2044 case HIST_TYPE_INDIR_CALL
:
2045 hist
->n_counters
= 3;
2048 case HIST_TYPE_TIME_PROFILE
:
2049 hist
->n_counters
= 1;
2052 case HIST_TYPE_AVERAGE
:
2053 hist
->n_counters
= 2;
2057 hist
->n_counters
= 1;
2060 case HIST_TYPE_INDIR_CALL_TOPN
:
2061 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2069 fprintf (dump_file
, "Stmt ");
2070 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2071 dump_histogram_value (dump_file
, hist
);