1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "double-int.h"
34 #include "fold-const.h"
35 #include "tree-nested.h"
39 #include "hard-reg-set.h"
43 #include "dominance.h"
45 #include "basic-block.h"
46 #include "value-prof.h"
48 #include "insn-config.h"
50 #include "insn-codes.h"
53 #include "tree-ssa-alias.h"
54 #include "internal-fn.h"
56 #include "gimple-expr.h"
60 #include "gimple-iterator.h"
61 #include "gimple-ssa.h"
63 #include "tree-phinodes.h"
64 #include "ssa-iterators.h"
65 #include "stringpool.h"
66 #include "tree-ssanames.h"
67 #include "diagnostic.h"
68 #include "gimple-pretty-print.h"
76 #include "plugin-api.h"
79 #include "data-streamer.h"
81 #include "tree-nested.h"
83 #include "tree-chkp.h"
85 /* In this file value profile based optimizations are placed. Currently the
86 following optimizations are implemented (for more detailed descriptions
87 see comments at value_profile_transformations):
89 1) Division/modulo specialization. Provided that we can determine that the
90 operands of the division have some special properties, we may use it to
91 produce more effective code.
93 2) Indirect/virtual call specialization. If we can determine most
94 common function callee in indirect/virtual call. We can use this
95 information to improve code effectiveness (especially info for
98 3) Speculative prefetching. If we are able to determine that the difference
99 between addresses accessed by a memory reference is usually constant, we
100 may add the prefetch instructions.
101 FIXME: This transformation was removed together with RTL based value
105 Value profiling internals
106 ==========================
108 Every value profiling transformation starts with defining what values
109 to profile. There are different histogram types (see HIST_TYPE_* in
110 value-prof.h) and each transformation can request one or more histogram
111 types per GIMPLE statement. The function gimple_find_values_to_profile()
112 collects the values to profile in a vec, and adds the number of counters
113 required for the different histogram types.
115 For a -fprofile-generate run, the statements for which values should be
116 recorded, are instrumented in instrument_values(). The instrumentation
117 is done by helper functions that can be found in tree-profile.c, where
118 new types of histograms can be added if necessary.
120 After a -fprofile-use, the value profiling data is read back in by
121 compute_value_histograms() that translates the collected data to
122 histograms and attaches them to the profiled statements via
123 gimple_add_histogram_value(). Histograms are stored in a hash table
124 that is attached to every intrumented function, see VALUE_HISTOGRAMS
127 The value-profile transformations driver is the function
128 gimple_value_profile_transformations(). It traverses all statements in
129 the to-be-transformed function, and looks for statements with one or
130 more histograms attached to it. If a statement has histograms, the
131 transformation functions are called on the statement.
133 Limitations / FIXME / TODO:
134 * Only one histogram of each type can be associated with a statement.
135 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
136 (This type of histogram was originally used to implement a form of
137 stride profiling based speculative prefetching to improve SPEC2000
138 scores for memory-bound benchmarks, mcf and equake. However, this
139 was an RTL value-profiling transformation, and those have all been
141 * Some value profile transformations are done in builtins.c (?!)
142 * Updating of histograms needs some TLC.
143 * The value profiling code could be used to record analysis results
144 from non-profiling (e.g. VRP).
145 * Adding new profilers should be simplified, starting with a cleanup
146 of what-happens-where andwith making gimple_find_values_to_profile
147 and gimple_value_profile_transformations table-driven, perhaps...
150 static tree
gimple_divmod_fixed_value (gassign
*, tree
, int, gcov_type
,
152 static tree
gimple_mod_pow2 (gassign
*, int, gcov_type
, gcov_type
);
153 static tree
gimple_mod_subtract (gassign
*, int, int, int, gcov_type
,
154 gcov_type
, gcov_type
);
155 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
156 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
157 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
158 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
159 static bool gimple_ic_transform (gimple_stmt_iterator
*);
161 /* Allocate histogram value. */
164 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
165 enum hist_type type
, gimple stmt
, tree value
)
167 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
168 hist
->hvalue
.value
= value
;
169 hist
->hvalue
.stmt
= stmt
;
174 /* Hash value for histogram. */
177 histogram_hash (const void *x
)
179 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
182 /* Return nonzero if statement for histogram_value X is Y. */
185 histogram_eq (const void *x
, const void *y
)
187 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
190 /* Set histogram for STMT. */
193 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
196 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
198 if (!VALUE_HISTOGRAMS (fun
))
199 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
201 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
202 htab_hash_pointer (stmt
),
203 hist
? INSERT
: NO_INSERT
);
207 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
213 /* Get histogram list for STMT. */
216 gimple_histogram_value (struct function
*fun
, gimple stmt
)
218 if (!VALUE_HISTOGRAMS (fun
))
220 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
221 htab_hash_pointer (stmt
));
224 /* Add histogram for STMT. */
227 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
228 histogram_value hist
)
230 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
231 set_histogram_value (fun
, stmt
, hist
);
236 /* Remove histogram HIST from STMT's histogram list. */
239 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
240 histogram_value hist
)
242 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
245 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
249 while (hist2
->hvalue
.next
!= hist
)
250 hist2
= hist2
->hvalue
.next
;
251 hist2
->hvalue
.next
= hist
->hvalue
.next
;
253 free (hist
->hvalue
.counters
);
254 #ifdef ENABLE_CHECKING
255 memset (hist
, 0xab, sizeof (*hist
));
261 /* Lookup histogram of type TYPE in the STMT. */
264 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
267 histogram_value hist
;
268 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
269 hist
= hist
->hvalue
.next
)
270 if (hist
->type
== type
)
275 /* Dump information about HIST to DUMP_FILE. */
278 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
282 case HIST_TYPE_INTERVAL
:
283 fprintf (dump_file
, "Interval counter range %d -- %d",
284 hist
->hdata
.intvl
.int_start
,
285 (hist
->hdata
.intvl
.int_start
286 + hist
->hdata
.intvl
.steps
- 1));
287 if (hist
->hvalue
.counters
)
290 fprintf (dump_file
, " [");
291 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
292 fprintf (dump_file
, " %d:%"PRId64
,
293 hist
->hdata
.intvl
.int_start
+ i
,
294 (int64_t) hist
->hvalue
.counters
[i
]);
295 fprintf (dump_file
, " ] outside range:%"PRId64
,
296 (int64_t) hist
->hvalue
.counters
[i
]);
298 fprintf (dump_file
, ".\n");
302 fprintf (dump_file
, "Pow2 counter ");
303 if (hist
->hvalue
.counters
)
305 fprintf (dump_file
, "pow2:%"PRId64
307 (int64_t) hist
->hvalue
.counters
[0],
308 (int64_t) hist
->hvalue
.counters
[1]);
310 fprintf (dump_file
, ".\n");
313 case HIST_TYPE_SINGLE_VALUE
:
314 fprintf (dump_file
, "Single value ");
315 if (hist
->hvalue
.counters
)
317 fprintf (dump_file
, "value:%"PRId64
320 (int64_t) hist
->hvalue
.counters
[0],
321 (int64_t) hist
->hvalue
.counters
[1],
322 (int64_t) hist
->hvalue
.counters
[2]);
324 fprintf (dump_file
, ".\n");
327 case HIST_TYPE_AVERAGE
:
328 fprintf (dump_file
, "Average value ");
329 if (hist
->hvalue
.counters
)
331 fprintf (dump_file
, "sum:%"PRId64
333 (int64_t) hist
->hvalue
.counters
[0],
334 (int64_t) hist
->hvalue
.counters
[1]);
336 fprintf (dump_file
, ".\n");
340 fprintf (dump_file
, "IOR value ");
341 if (hist
->hvalue
.counters
)
343 fprintf (dump_file
, "ior:%"PRId64
,
344 (int64_t) hist
->hvalue
.counters
[0]);
346 fprintf (dump_file
, ".\n");
349 case HIST_TYPE_CONST_DELTA
:
350 fprintf (dump_file
, "Constant delta ");
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_INDIR_CALL
:
363 fprintf (dump_file
, "Indirect call ");
364 if (hist
->hvalue
.counters
)
366 fprintf (dump_file
, "value:%"PRId64
369 (int64_t) hist
->hvalue
.counters
[0],
370 (int64_t) hist
->hvalue
.counters
[1],
371 (int64_t) hist
->hvalue
.counters
[2]);
373 fprintf (dump_file
, ".\n");
375 case HIST_TYPE_TIME_PROFILE
:
376 fprintf (dump_file
, "Time profile ");
377 if (hist
->hvalue
.counters
)
379 fprintf (dump_file
, "time:%"PRId64
,
380 (int64_t) hist
->hvalue
.counters
[0]);
382 fprintf (dump_file
, ".\n");
384 case HIST_TYPE_INDIR_CALL_TOPN
:
385 fprintf (dump_file
, "Indirect call topn ");
386 if (hist
->hvalue
.counters
)
390 fprintf (dump_file
, "accu:%"PRId64
, hist
->hvalue
.counters
[0]);
391 for (i
= 1; i
< (GCOV_ICALL_TOPN_VAL
<< 2); i
+= 2)
393 fprintf (dump_file
, " target:%"PRId64
" value:%"PRId64
,
394 (int64_t) hist
->hvalue
.counters
[i
],
395 (int64_t) hist
->hvalue
.counters
[i
+1]);
398 fprintf (dump_file
, ".\n");
405 /* Dump information about HIST to DUMP_FILE. */
408 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
413 bp
= bitpack_create (ob
->main_stream
);
414 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
415 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
416 streamer_write_bitpack (&bp
);
419 case HIST_TYPE_INTERVAL
:
420 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
421 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
426 for (i
= 0; i
< hist
->n_counters
; i
++)
427 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
428 if (hist
->hvalue
.next
)
429 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
431 /* Dump information about HIST to DUMP_FILE. */
434 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
437 unsigned int ncounters
= 0;
440 histogram_value new_val
;
442 histogram_value
*next_p
= NULL
;
446 bp
= streamer_read_bitpack (ib
);
447 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
448 next
= bp_unpack_value (&bp
, 1);
449 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
452 case HIST_TYPE_INTERVAL
:
453 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
454 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
455 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
459 case HIST_TYPE_AVERAGE
:
463 case HIST_TYPE_SINGLE_VALUE
:
464 case HIST_TYPE_INDIR_CALL
:
468 case HIST_TYPE_CONST_DELTA
:
473 case HIST_TYPE_TIME_PROFILE
:
477 case HIST_TYPE_INDIR_CALL_TOPN
:
478 ncounters
= (GCOV_ICALL_TOPN_VAL
<< 2) + 1;
484 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
485 new_val
->n_counters
= ncounters
;
486 for (i
= 0; i
< ncounters
; i
++)
487 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
489 gimple_add_histogram_value (cfun
, stmt
, new_val
);
492 next_p
= &new_val
->hvalue
.next
;
497 /* Dump all histograms attached to STMT to DUMP_FILE. */
500 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
502 histogram_value hist
;
503 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
504 dump_histogram_value (dump_file
, hist
);
507 /* Remove all histograms associated with STMT. */
510 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
513 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
514 gimple_remove_histogram_value (fun
, stmt
, val
);
517 /* Duplicate all histograms associates with OSTMT to STMT. */
520 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
521 struct function
*ofun
, gimple ostmt
)
524 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
526 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
527 memcpy (new_val
, val
, sizeof (*val
));
528 new_val
->hvalue
.stmt
= stmt
;
529 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
530 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
531 gimple_add_histogram_value (fun
, stmt
, new_val
);
536 /* Move all histograms associated with OSTMT to STMT. */
539 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
541 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
544 /* The following three statements can't be reordered,
545 because histogram hashtab relies on stmt field value
546 for finding the exact slot. */
547 set_histogram_value (fun
, ostmt
, NULL
);
548 for (; val
!= NULL
; val
= val
->hvalue
.next
)
549 val
->hvalue
.stmt
= stmt
;
550 set_histogram_value (fun
, stmt
, val
);
554 static bool error_found
= false;
556 /* Helper function for verify_histograms. For each histogram reachable via htab
557 walk verify that it was reached via statement walk. */
560 visit_hist (void **slot
, void *data
)
562 hash_set
<histogram_value
> *visited
= (hash_set
<histogram_value
> *) data
;
563 histogram_value hist
= *(histogram_value
*) slot
;
565 if (!visited
->contains (hist
)
566 && hist
->type
!= HIST_TYPE_TIME_PROFILE
)
568 error ("dead histogram");
569 dump_histogram_value (stderr
, hist
);
570 debug_gimple_stmt (hist
->hvalue
.stmt
);
577 /* Verify sanity of the histograms. */
580 verify_histograms (void)
583 gimple_stmt_iterator gsi
;
584 histogram_value hist
;
587 hash_set
<histogram_value
> visited_hists
;
588 FOR_EACH_BB_FN (bb
, cfun
)
589 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
591 gimple stmt
= gsi_stmt (gsi
);
593 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
594 hist
= hist
->hvalue
.next
)
596 if (hist
->hvalue
.stmt
!= stmt
)
598 error ("Histogram value statement does not correspond to "
599 "the statement it is associated with");
600 debug_gimple_stmt (stmt
);
601 dump_histogram_value (stderr
, hist
);
604 visited_hists
.add (hist
);
607 if (VALUE_HISTOGRAMS (cfun
))
608 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, &visited_hists
);
610 internal_error ("verify_histograms failed");
613 /* Helper function for verify_histograms. For each histogram reachable via htab
614 walk verify that it was reached via statement walk. */
617 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
619 histogram_value hist
= *(histogram_value
*) slot
;
620 free (hist
->hvalue
.counters
);
621 #ifdef ENABLE_CHECKING
622 memset (hist
, 0xab, sizeof (*hist
));
629 free_histograms (void)
631 if (VALUE_HISTOGRAMS (cfun
))
633 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
634 htab_delete (VALUE_HISTOGRAMS (cfun
));
635 VALUE_HISTOGRAMS (cfun
) = NULL
;
640 /* The overall number of invocations of the counter should match
641 execution count of basic block. Report it as error rather than
642 internal error as it might mean that user has misused the profile
646 check_counter (gimple stmt
, const char * name
,
647 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
649 if (*all
!= bb_count
|| *count
> *all
)
652 locus
= (stmt
!= NULL
)
653 ? gimple_location (stmt
)
654 : DECL_SOURCE_LOCATION (current_function_decl
);
655 if (flag_profile_correction
)
657 if (dump_enabled_p ())
658 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
659 "correcting inconsistent value profile: %s "
660 "profiler overall count (%d) does not match BB "
661 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
669 error_at (locus
, "corrupted value profile: %s "
670 "profile counter (%d out of %d) inconsistent with "
671 "basic-block count (%d)",
684 /* GIMPLE based transformations. */
687 gimple_value_profile_transformations (void)
690 gimple_stmt_iterator gsi
;
691 bool changed
= false;
693 FOR_EACH_BB_FN (bb
, cfun
)
695 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
697 gimple stmt
= gsi_stmt (gsi
);
698 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
704 fprintf (dump_file
, "Trying transformations on stmt ");
705 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
706 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
709 /* Transformations: */
710 /* The order of things in this conditional controls which
711 transformation is used when more than one is applicable. */
712 /* It is expected that any code added by the transformations
713 will be added before the current statement, and that the
714 current statement remain valid (although possibly
715 modified) upon return. */
716 if (gimple_mod_subtract_transform (&gsi
)
717 || gimple_divmod_fixed_value_transform (&gsi
)
718 || gimple_mod_pow2_value_transform (&gsi
)
719 || gimple_stringops_transform (&gsi
)
720 || gimple_ic_transform (&gsi
))
722 stmt
= gsi_stmt (gsi
);
724 /* Original statement may no longer be in the same block. */
725 if (bb
!= gimple_bb (stmt
))
727 bb
= gimple_bb (stmt
);
728 gsi
= gsi_for_stmt (stmt
);
743 /* Generate code for transformation 1 (with parent gimple assignment
744 STMT and probability of taking the optimal path PROB, which is
745 equivalent to COUNT/ALL within roundoff error). This generates the
746 result into a temp and returns the temp; it does not replace or
747 alter the original STMT. */
750 gimple_divmod_fixed_value (gassign
*stmt
, tree value
, int prob
,
751 gcov_type count
, gcov_type all
)
753 gassign
*stmt1
, *stmt2
;
755 tree tmp0
, tmp1
, tmp2
;
756 gimple bb1end
, bb2end
, bb3end
;
757 basic_block bb
, bb2
, bb3
, bb4
;
758 tree optype
, op1
, op2
;
759 edge e12
, e13
, e23
, e24
, e34
;
760 gimple_stmt_iterator gsi
;
762 gcc_assert (is_gimple_assign (stmt
)
763 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
764 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
766 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
767 op1
= gimple_assign_rhs1 (stmt
);
768 op2
= gimple_assign_rhs2 (stmt
);
770 bb
= gimple_bb (stmt
);
771 gsi
= gsi_for_stmt (stmt
);
773 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
774 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
775 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
776 stmt2
= gimple_build_assign (tmp1
, op2
);
777 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
778 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
779 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
780 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
783 tmp2
= create_tmp_reg (optype
, "PROF");
784 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, tmp0
);
785 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
788 stmt1
= gimple_build_assign (tmp2
, gimple_assign_rhs_code (stmt
), op1
, op2
);
789 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
793 /* Edge e23 connects bb2 to bb3, etc. */
794 e12
= split_block (bb
, bb1end
);
797 e23
= split_block (bb2
, bb2end
);
799 bb3
->count
= all
- count
;
800 e34
= split_block (bb3
, bb3end
);
804 e12
->flags
&= ~EDGE_FALLTHRU
;
805 e12
->flags
|= EDGE_FALSE_VALUE
;
806 e12
->probability
= prob
;
809 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
810 e13
->probability
= REG_BR_PROB_BASE
- prob
;
811 e13
->count
= all
- count
;
815 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
816 e24
->probability
= REG_BR_PROB_BASE
;
819 e34
->probability
= REG_BR_PROB_BASE
;
820 e34
->count
= all
- count
;
826 /* Do transform 1) on INSN if applicable. */
829 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
831 histogram_value histogram
;
833 gcov_type val
, count
, all
;
834 tree result
, value
, tree_val
;
838 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
842 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
845 code
= gimple_assign_rhs_code (stmt
);
847 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
850 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
851 HIST_TYPE_SINGLE_VALUE
);
855 value
= histogram
->hvalue
.value
;
856 val
= histogram
->hvalue
.counters
[0];
857 count
= histogram
->hvalue
.counters
[1];
858 all
= histogram
->hvalue
.counters
[2];
859 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
861 /* We require that count is at least half of all; this means
862 that for the transformation to fire the value must be constant
863 at least 50% of time (and 75% gives the guarantee of usage). */
864 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
866 || optimize_bb_for_size_p (gimple_bb (stmt
)))
869 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
872 /* Compute probability of taking the optimal path. */
874 prob
= GCOV_COMPUTE_SCALE (count
, all
);
878 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
879 tree_val
= build_int_cst (get_gcov_type (), val
);
883 a
[0] = (unsigned HOST_WIDE_INT
) val
;
884 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
886 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
887 TYPE_PRECISION (get_gcov_type ()), false));
889 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
893 fprintf (dump_file
, "Div/mod by constant ");
894 print_generic_expr (dump_file
, value
, TDF_SLIM
);
895 fprintf (dump_file
, "=");
896 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
897 fprintf (dump_file
, " transformation on insn ");
898 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
901 gimple_assign_set_rhs_from_tree (si
, result
);
902 update_stmt (gsi_stmt (*si
));
907 /* Generate code for transformation 2 (with parent gimple assign STMT and
908 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
909 within roundoff error). This generates the result into a temp and returns
910 the temp; it does not replace or alter the original STMT. */
912 gimple_mod_pow2 (gassign
*stmt
, int prob
, gcov_type count
, gcov_type all
)
914 gassign
*stmt1
, *stmt2
, *stmt3
;
917 gimple bb1end
, bb2end
, bb3end
;
918 basic_block bb
, bb2
, bb3
, bb4
;
919 tree optype
, op1
, op2
;
920 edge e12
, e13
, e23
, e24
, e34
;
921 gimple_stmt_iterator gsi
;
924 gcc_assert (is_gimple_assign (stmt
)
925 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
927 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
928 op1
= gimple_assign_rhs1 (stmt
);
929 op2
= gimple_assign_rhs2 (stmt
);
931 bb
= gimple_bb (stmt
);
932 gsi
= gsi_for_stmt (stmt
);
934 result
= create_tmp_reg (optype
, "PROF");
935 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
936 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
937 stmt2
= gimple_build_assign (tmp2
, PLUS_EXPR
, op2
,
938 build_int_cst (optype
, -1));
939 stmt3
= gimple_build_assign (tmp3
, BIT_AND_EXPR
, tmp2
, op2
);
940 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
941 NULL_TREE
, NULL_TREE
);
942 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
943 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
944 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
947 /* tmp2 == op2-1 inherited from previous block. */
948 stmt1
= gimple_build_assign (result
, BIT_AND_EXPR
, op1
, tmp2
);
949 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
952 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
954 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
958 /* Edge e23 connects bb2 to bb3, etc. */
959 e12
= split_block (bb
, bb1end
);
962 e23
= split_block (bb2
, bb2end
);
964 bb3
->count
= all
- count
;
965 e34
= split_block (bb3
, bb3end
);
969 e12
->flags
&= ~EDGE_FALLTHRU
;
970 e12
->flags
|= EDGE_FALSE_VALUE
;
971 e12
->probability
= prob
;
974 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
975 e13
->probability
= REG_BR_PROB_BASE
- prob
;
976 e13
->count
= all
- count
;
980 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
981 e24
->probability
= REG_BR_PROB_BASE
;
984 e34
->probability
= REG_BR_PROB_BASE
;
985 e34
->count
= all
- count
;
990 /* Do transform 2) on INSN if applicable. */
992 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
994 histogram_value histogram
;
996 gcov_type count
, wrong_values
, all
;
997 tree lhs_type
, result
, value
;
1001 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1005 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1006 if (!INTEGRAL_TYPE_P (lhs_type
))
1009 code
= gimple_assign_rhs_code (stmt
);
1011 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1014 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
1018 value
= histogram
->hvalue
.value
;
1019 wrong_values
= histogram
->hvalue
.counters
[0];
1020 count
= histogram
->hvalue
.counters
[1];
1022 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1024 /* We require that we hit a power of 2 at least half of all evaluations. */
1025 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
1026 || count
< wrong_values
1027 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1032 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
1033 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1036 /* Compute probability of taking the optimal path. */
1037 all
= count
+ wrong_values
;
1039 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
1043 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1047 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
1049 gimple_assign_set_rhs_from_tree (si
, result
);
1050 update_stmt (gsi_stmt (*si
));
1055 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1056 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
1057 supported and this is built into this interface. The probabilities of taking
1058 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1059 COUNT2/ALL respectively within roundoff error). This generates the
1060 result into a temp and returns the temp; it does not replace or alter
1061 the original STMT. */
1062 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
1065 gimple_mod_subtract (gassign
*stmt
, int prob1
, int prob2
, int ncounts
,
1066 gcov_type count1
, gcov_type count2
, gcov_type all
)
1072 gimple bb1end
, bb2end
= NULL
, bb3end
;
1073 basic_block bb
, bb2
, bb3
, bb4
;
1074 tree optype
, op1
, op2
;
1075 edge e12
, e23
= 0, e24
, e34
, e14
;
1076 gimple_stmt_iterator gsi
;
1079 gcc_assert (is_gimple_assign (stmt
)
1080 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1082 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1083 op1
= gimple_assign_rhs1 (stmt
);
1084 op2
= gimple_assign_rhs2 (stmt
);
1086 bb
= gimple_bb (stmt
);
1087 gsi
= gsi_for_stmt (stmt
);
1089 result
= create_tmp_reg (optype
, "PROF");
1090 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1091 stmt1
= gimple_build_assign (result
, op1
);
1092 stmt2
= gimple_build_assign (tmp1
, op2
);
1093 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1094 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1095 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1096 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1099 if (ncounts
) /* Assumed to be 0 or 1 */
1101 stmt1
= gimple_build_assign (result
, MINUS_EXPR
, result
, tmp1
);
1102 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1103 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1104 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1108 /* Fallback case. */
1109 stmt1
= gimple_build_assign (result
, gimple_assign_rhs_code (stmt
),
1111 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1115 /* Edge e23 connects bb2 to bb3, etc. */
1116 /* However block 3 is optional; if it is not there, references
1117 to 3 really refer to block 2. */
1118 e12
= split_block (bb
, bb1end
);
1120 bb2
->count
= all
- count1
;
1122 if (ncounts
) /* Assumed to be 0 or 1. */
1124 e23
= split_block (bb2
, bb2end
);
1126 bb3
->count
= all
- count1
- count2
;
1129 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1133 e12
->flags
&= ~EDGE_FALLTHRU
;
1134 e12
->flags
|= EDGE_FALSE_VALUE
;
1135 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1136 e12
->count
= all
- count1
;
1138 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1139 e14
->probability
= prob1
;
1140 e14
->count
= count1
;
1142 if (ncounts
) /* Assumed to be 0 or 1. */
1144 e23
->flags
&= ~EDGE_FALLTHRU
;
1145 e23
->flags
|= EDGE_FALSE_VALUE
;
1146 e23
->count
= all
- count1
- count2
;
1147 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1149 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1150 e24
->probability
= prob2
;
1151 e24
->count
= count2
;
1154 e34
->probability
= REG_BR_PROB_BASE
;
1155 e34
->count
= all
- count1
- count2
;
1161 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1164 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1166 histogram_value histogram
;
1167 enum tree_code code
;
1168 gcov_type count
, wrong_values
, all
;
1169 tree lhs_type
, result
;
1170 gcov_type prob1
, prob2
;
1171 unsigned int i
, steps
;
1172 gcov_type count1
, count2
;
1175 stmt
= dyn_cast
<gassign
*> (gsi_stmt (*si
));
1179 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1180 if (!INTEGRAL_TYPE_P (lhs_type
))
1183 code
= gimple_assign_rhs_code (stmt
);
1185 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1188 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1194 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1195 all
+= histogram
->hvalue
.counters
[i
];
1197 wrong_values
+= histogram
->hvalue
.counters
[i
];
1198 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1199 steps
= histogram
->hdata
.intvl
.steps
;
1200 all
+= wrong_values
;
1201 count1
= histogram
->hvalue
.counters
[0];
1202 count2
= histogram
->hvalue
.counters
[1];
1204 /* Compute probability of taking the optimal path. */
1205 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1207 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1211 if (flag_profile_correction
&& count1
+ count2
> all
)
1212 all
= count1
+ count2
;
1214 gcc_assert (count1
+ count2
<= all
);
1216 /* We require that we use just subtractions in at least 50% of all
1219 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1221 count
+= histogram
->hvalue
.counters
[i
];
1222 if (count
* 2 >= all
)
1226 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1229 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1232 fprintf (dump_file
, "Mod subtract transformation on insn ");
1233 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1236 /* Compute probability of taking the optimal path(s). */
1239 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1240 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1247 /* In practice, "steps" is always 2. This interface reflects this,
1248 and will need to be changed if "steps" can change. */
1249 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1251 gimple_assign_set_rhs_from_tree (si
, result
);
1252 update_stmt (gsi_stmt (*si
));
1257 struct profile_id_traits
: default_hashmap_traits
1259 template<typename T
>
1263 return e
.m_key
== UINT_MAX
;
1266 template<typename T
> static bool is_empty (T
&e
) { return e
.m_key
== 0; }
1267 template<typename T
> static void mark_deleted (T
&e
) { e
.m_key
= UINT_MAX
; }
1268 template<typename T
> static void mark_empty (T
&e
) { e
.m_key
= 0; }
1271 static hash_map
<unsigned int, cgraph_node
*, profile_id_traits
> *
1272 cgraph_node_map
= 0;
1274 /* Returns true if node graph is initialized. This
1275 is used to test if profile_id has been created
1276 for cgraph_nodes. */
1279 coverage_node_map_initialized_p (void)
1281 return cgraph_node_map
!= 0;
1284 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1285 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1286 that the PROFILE_IDs was already assigned. */
1289 init_node_map (bool local
)
1291 struct cgraph_node
*n
;
1293 = new hash_map
<unsigned int, cgraph_node
*, profile_id_traits
>;
1295 FOR_EACH_DEFINED_FUNCTION (n
)
1296 if (n
->has_gimple_body_p ())
1301 n
->profile_id
= coverage_compute_profile_id (n
);
1302 while ((val
= cgraph_node_map
->get (n
->profile_id
))
1306 fprintf (dump_file
, "Local profile-id %i conflict"
1307 " with nodes %s/%i %s/%i\n",
1313 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1316 else if (!n
->profile_id
)
1320 "Node %s/%i has no profile-id"
1321 " (profile feedback missing?)\n",
1326 else if ((val
= cgraph_node_map
->get (n
->profile_id
)))
1330 "Node %s/%i has IP profile-id %i conflict. "
1338 cgraph_node_map
->put (n
->profile_id
, n
);
1342 /* Delete the CGRAPH_NODE_MAP. */
1347 delete cgraph_node_map
;
1350 /* Return cgraph node for function with pid */
1353 find_func_by_profile_id (int profile_id
)
1355 cgraph_node
**val
= cgraph_node_map
->get (profile_id
);
1362 /* Perform sanity check on the indirect call target. Due to race conditions,
1363 false function target may be attributed to an indirect call site. If the
1364 call expression type mismatches with the target function's type, expand_call
1365 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1366 Returns true if TARGET is considered ok for call CALL_STMT. */
1369 check_ic_target (gcall
*call_stmt
, struct cgraph_node
*target
)
1372 if (gimple_check_call_matching_types (call_stmt
, target
->decl
, true))
1375 locus
= gimple_location (call_stmt
);
1376 if (dump_enabled_p ())
1377 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1378 "Skipping target %s with mismatching types for icall\n",
1383 /* Do transformation
1385 if (actual_callee_address == address_of_most_common_function/method)
1392 gimple_ic (gcall
*icall_stmt
, struct cgraph_node
*direct_call
,
1393 int prob
, gcov_type count
, gcov_type all
)
1398 gcall
*iretbnd_stmt
= NULL
;
1399 tree tmp0
, tmp1
, tmp
;
1400 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1401 tree optype
= build_pointer_type (void_type_node
);
1402 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1403 gimple_stmt_iterator gsi
;
1407 gimple_stmt_iterator psi
;
1409 cond_bb
= gimple_bb (icall_stmt
);
1410 gsi
= gsi_for_stmt (icall_stmt
);
1412 if (gimple_call_with_bounds_p (icall_stmt
) && gimple_call_lhs (icall_stmt
))
1413 iretbnd_stmt
= chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt
));
1415 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1416 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1417 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1418 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1419 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1421 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1422 current_function_decl
));
1423 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1424 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1426 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1427 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1429 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1430 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1431 update_stmt (icall_stmt
);
1432 dcall_stmt
= as_a
<gcall
*> (gimple_copy (icall_stmt
));
1433 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1434 dflags
= flags_from_decl_or_type (direct_call
->decl
);
1435 if ((dflags
& ECF_NORETURN
) != 0)
1436 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1437 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1440 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1441 e_cd
= split_block (cond_bb
, cond_stmt
);
1442 dcall_bb
= e_cd
->dest
;
1443 dcall_bb
->count
= count
;
1445 e_di
= split_block (dcall_bb
, dcall_stmt
);
1446 icall_bb
= e_di
->dest
;
1447 icall_bb
->count
= all
- count
;
1449 /* Do not disturb existing EH edges from the indirect call. */
1450 if (!stmt_ends_bb_p (icall_stmt
))
1451 e_ij
= split_block (icall_bb
, icall_stmt
);
1454 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1455 /* The indirect call might be noreturn. */
1458 e_ij
->probability
= REG_BR_PROB_BASE
;
1459 e_ij
->count
= all
- count
;
1460 e_ij
= single_pred_edge (split_edge (e_ij
));
1465 join_bb
= e_ij
->dest
;
1466 join_bb
->count
= all
;
1469 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1470 e_cd
->probability
= prob
;
1471 e_cd
->count
= count
;
1473 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1474 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1475 e_ci
->count
= all
- count
;
1481 if ((dflags
& ECF_NORETURN
) != 0)
1485 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1486 e_dj
->probability
= REG_BR_PROB_BASE
;
1487 e_dj
->count
= count
;
1489 e_ij
->count
= all
- count
;
1491 e_ij
->probability
= REG_BR_PROB_BASE
;
1494 /* Insert PHI node for the call result if necessary. */
1495 if (gimple_call_lhs (icall_stmt
)
1496 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1497 && (dflags
& ECF_NORETURN
) == 0)
1499 tree result
= gimple_call_lhs (icall_stmt
);
1500 gphi
*phi
= create_phi_node (result
, join_bb
);
1501 gimple_call_set_lhs (icall_stmt
,
1502 duplicate_ssa_name (result
, icall_stmt
));
1503 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1504 gimple_call_set_lhs (dcall_stmt
,
1505 duplicate_ssa_name (result
, dcall_stmt
));
1506 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1508 /* If indirect call has following BUILT_IN_CHKP_BNDRET
1509 call then we need to make it's copy for the direct
1513 if (gimple_call_lhs (iretbnd_stmt
))
1517 gimple_set_vdef (iretbnd_stmt
, NULL_TREE
);
1518 gimple_set_vuse (iretbnd_stmt
, NULL_TREE
);
1519 update_stmt (iretbnd_stmt
);
1521 result
= gimple_call_lhs (iretbnd_stmt
);
1522 phi
= create_phi_node (result
, join_bb
);
1524 copy
= gimple_copy (iretbnd_stmt
);
1525 gimple_call_set_arg (copy
, 0,
1526 gimple_call_lhs (dcall_stmt
));
1527 gimple_call_set_lhs (copy
, duplicate_ssa_name (result
, copy
));
1528 gsi_insert_on_edge (e_dj
, copy
);
1529 add_phi_arg (phi
, gimple_call_lhs (copy
),
1530 e_dj
, UNKNOWN_LOCATION
);
1532 gimple_call_set_arg (iretbnd_stmt
, 0,
1533 gimple_call_lhs (icall_stmt
));
1534 gimple_call_set_lhs (iretbnd_stmt
,
1535 duplicate_ssa_name (result
, iretbnd_stmt
));
1536 psi
= gsi_for_stmt (iretbnd_stmt
);
1537 gsi_remove (&psi
, false);
1538 gsi_insert_on_edge (e_ij
, iretbnd_stmt
);
1539 add_phi_arg (phi
, gimple_call_lhs (iretbnd_stmt
),
1540 e_ij
, UNKNOWN_LOCATION
);
1542 gsi_commit_one_edge_insert (e_dj
, NULL
);
1543 gsi_commit_one_edge_insert (e_ij
, NULL
);
1547 psi
= gsi_for_stmt (iretbnd_stmt
);
1548 gsi_remove (&psi
, true);
1553 /* Build an EH edge for the direct call if necessary. */
1554 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1555 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1557 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1560 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1561 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1563 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1564 for (gphi_iterator psi
= gsi_start_phis (e_eh
->dest
);
1565 !gsi_end_p (psi
); gsi_next (&psi
))
1567 gphi
*phi
= psi
.phi ();
1568 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1569 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1576 For every checked indirect/virtual call determine if most common pid of
1577 function/class method has probability more than 50%. If yes modify code of
1582 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1585 histogram_value histogram
;
1586 gcov_type val
, count
, all
, bb_all
;
1587 struct cgraph_node
*direct_call
;
1589 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1593 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1596 if (gimple_call_internal_p (stmt
))
1599 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1603 val
= histogram
->hvalue
.counters
[0];
1604 count
= histogram
->hvalue
.counters
[1];
1605 all
= histogram
->hvalue
.counters
[2];
1607 bb_all
= gimple_bb (stmt
)->count
;
1608 /* The order of CHECK_COUNTER calls is important -
1609 since check_counter can correct the third parameter
1610 and we want to make count <= all <= bb_all. */
1611 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1612 || check_counter (stmt
, "ic", &count
, &all
, all
))
1614 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1618 if (4 * count
<= 3 * all
)
1621 direct_call
= find_func_by_profile_id ((int)val
);
1623 if (direct_call
== NULL
)
1629 fprintf (dump_file
, "Indirect call -> direct call from other module");
1630 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1631 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1637 if (!check_ic_target (stmt
, direct_call
))
1641 fprintf (dump_file
, "Indirect call -> direct call ");
1642 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1643 fprintf (dump_file
, "=> ");
1644 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1645 fprintf (dump_file
, " transformation skipped because of type mismatch");
1646 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1648 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1654 fprintf (dump_file
, "Indirect call -> direct call ");
1655 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1656 fprintf (dump_file
, "=> ");
1657 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1658 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1659 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1660 fprintf (dump_file
, "hist->count %"PRId64
1661 " hist->all %"PRId64
"\n", count
, all
);
1667 /* Return true if the stringop CALL with FNDECL shall be profiled.
1668 SIZE_ARG be set to the argument index for the size of the string
1672 interesting_stringop_to_profile_p (tree fndecl
, gcall
*call
, int *size_arg
)
1674 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1676 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1677 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1682 case BUILT_IN_MEMCPY
:
1683 case BUILT_IN_MEMPCPY
:
1685 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1686 INTEGER_TYPE
, VOID_TYPE
);
1687 case BUILT_IN_MEMSET
:
1689 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1690 INTEGER_TYPE
, VOID_TYPE
);
1691 case BUILT_IN_BZERO
:
1693 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1700 /* Convert stringop (..., vcall_size)
1702 if (vcall_size == icall_size)
1703 stringop (..., icall_size);
1705 stringop (..., vcall_size);
1706 assuming we'll propagate a true constant into ICALL_SIZE later. */
1709 gimple_stringop_fixed_value (gcall
*vcall_stmt
, tree icall_size
, int prob
,
1710 gcov_type count
, gcov_type all
)
1715 tree tmp0
, tmp1
, vcall_size
, optype
;
1716 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1717 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1718 gimple_stmt_iterator gsi
;
1722 fndecl
= gimple_call_fndecl (vcall_stmt
);
1723 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1726 cond_bb
= gimple_bb (vcall_stmt
);
1727 gsi
= gsi_for_stmt (vcall_stmt
);
1729 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1730 optype
= TREE_TYPE (vcall_size
);
1732 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1733 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1734 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1735 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1737 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1738 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1740 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1741 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1743 gimple_set_vdef (vcall_stmt
, NULL
);
1744 gimple_set_vuse (vcall_stmt
, NULL
);
1745 update_stmt (vcall_stmt
);
1746 icall_stmt
= as_a
<gcall
*> (gimple_copy (vcall_stmt
));
1747 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1748 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1751 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1752 e_ci
= split_block (cond_bb
, cond_stmt
);
1753 icall_bb
= e_ci
->dest
;
1754 icall_bb
->count
= count
;
1756 e_iv
= split_block (icall_bb
, icall_stmt
);
1757 vcall_bb
= e_iv
->dest
;
1758 vcall_bb
->count
= all
- count
;
1760 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1761 join_bb
= e_vj
->dest
;
1762 join_bb
->count
= all
;
1764 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1765 e_ci
->probability
= prob
;
1766 e_ci
->count
= count
;
1768 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1769 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1770 e_cv
->count
= all
- count
;
1774 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1775 e_ij
->probability
= REG_BR_PROB_BASE
;
1776 e_ij
->count
= count
;
1778 e_vj
->probability
= REG_BR_PROB_BASE
;
1779 e_vj
->count
= all
- count
;
1781 /* Insert PHI node for the call result if necessary. */
1782 if (gimple_call_lhs (vcall_stmt
)
1783 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1785 tree result
= gimple_call_lhs (vcall_stmt
);
1786 gphi
*phi
= create_phi_node (result
, join_bb
);
1787 gimple_call_set_lhs (vcall_stmt
,
1788 duplicate_ssa_name (result
, vcall_stmt
));
1789 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1790 gimple_call_set_lhs (icall_stmt
,
1791 duplicate_ssa_name (result
, icall_stmt
));
1792 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1795 /* Because these are all string op builtins, they're all nothrow. */
1796 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1797 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1800 /* Find values inside STMT for that we want to measure histograms for
1801 division/modulo optimization. */
1803 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1808 enum built_in_function fcode
;
1809 histogram_value histogram
;
1810 gcov_type count
, all
, val
;
1812 unsigned int dest_align
, src_align
;
1817 stmt
= dyn_cast
<gcall
*> (gsi_stmt (*gsi
));
1820 fndecl
= gimple_call_fndecl (stmt
);
1823 fcode
= DECL_FUNCTION_CODE (fndecl
);
1824 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1827 blck_size
= gimple_call_arg (stmt
, size_arg
);
1828 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1831 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1834 val
= histogram
->hvalue
.counters
[0];
1835 count
= histogram
->hvalue
.counters
[1];
1836 all
= histogram
->hvalue
.counters
[2];
1837 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1838 /* We require that count is at least half of all; this means
1839 that for the transformation to fire the value must be constant
1840 at least 80% of time. */
1841 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1843 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1846 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1849 dest
= gimple_call_arg (stmt
, 0);
1850 dest_align
= get_pointer_alignment (dest
);
1853 case BUILT_IN_MEMCPY
:
1854 case BUILT_IN_MEMPCPY
:
1855 src
= gimple_call_arg (stmt
, 1);
1856 src_align
= get_pointer_alignment (src
);
1857 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1860 case BUILT_IN_MEMSET
:
1861 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1862 gimple_call_arg (stmt
, 1),
1866 case BUILT_IN_BZERO
:
1867 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1875 if (sizeof (gcov_type
) == sizeof (HOST_WIDE_INT
))
1876 tree_val
= build_int_cst (get_gcov_type (), val
);
1880 a
[0] = (unsigned HOST_WIDE_INT
) val
;
1881 a
[1] = val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1;
1883 tree_val
= wide_int_to_tree (get_gcov_type (), wide_int::from_array (a
, 2,
1884 TYPE_PRECISION (get_gcov_type ()), false));
1889 fprintf (dump_file
, "Single value %i stringop transformation on ",
1891 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1893 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1899 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1900 HOST_WIDE_INT
*expected_size
)
1902 histogram_value histogram
;
1903 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1905 *expected_size
= -1;
1906 else if (!histogram
->hvalue
.counters
[1])
1908 *expected_size
= -1;
1909 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1914 size
= ((histogram
->hvalue
.counters
[0]
1915 + histogram
->hvalue
.counters
[1] / 2)
1916 / histogram
->hvalue
.counters
[1]);
1917 /* Even if we can hold bigger value in SIZE, INT_MAX
1918 is safe "infinity" for code generation strategies. */
1921 *expected_size
= size
;
1922 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1924 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1926 *expected_align
= 0;
1927 else if (!histogram
->hvalue
.counters
[0])
1929 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1930 *expected_align
= 0;
1937 count
= histogram
->hvalue
.counters
[0];
1939 while (!(count
& alignment
)
1940 && (alignment
* 2 * BITS_PER_UNIT
))
1942 *expected_align
= alignment
* BITS_PER_UNIT
;
1943 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1948 /* Find values inside STMT for that we want to measure histograms for
1949 division/modulo optimization. */
1951 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1953 tree lhs
, divisor
, op0
, type
;
1954 histogram_value hist
;
1956 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1959 lhs
= gimple_assign_lhs (stmt
);
1960 type
= TREE_TYPE (lhs
);
1961 if (!INTEGRAL_TYPE_P (type
))
1964 switch (gimple_assign_rhs_code (stmt
))
1966 case TRUNC_DIV_EXPR
:
1967 case TRUNC_MOD_EXPR
:
1968 divisor
= gimple_assign_rhs2 (stmt
);
1969 op0
= gimple_assign_rhs1 (stmt
);
1971 values
->reserve (3);
1973 if (TREE_CODE (divisor
) == SSA_NAME
)
1974 /* Check for the case where the divisor is the same value most
1976 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1977 HIST_TYPE_SINGLE_VALUE
,
1980 /* For mod, check whether it is not often a noop (or replaceable by
1981 a few subtractions). */
1982 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1983 && TYPE_UNSIGNED (type
))
1986 /* Check for a special case where the divisor is power of 2. */
1987 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1991 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1992 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1994 hist
->hdata
.intvl
.int_start
= 0;
1995 hist
->hdata
.intvl
.steps
= 2;
1996 values
->quick_push (hist
);
2005 /* Find calls inside STMT for that we want to measure histograms for
2006 indirect/virtual call optimization. */
2009 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
2013 if (gimple_code (stmt
) != GIMPLE_CALL
2014 || gimple_call_internal_p (stmt
)
2015 || gimple_call_fndecl (stmt
) != NULL_TREE
)
2018 callee
= gimple_call_fn (stmt
);
2020 values
->reserve (3);
2022 values
->quick_push (gimple_alloc_histogram_value (
2024 PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE
) ?
2025 HIST_TYPE_INDIR_CALL_TOPN
:
2026 HIST_TYPE_INDIR_CALL
,
2032 /* Find values inside STMT for that we want to measure histograms for
2033 string operations. */
2035 gimple_stringops_values_to_profile (gimple gs
, histogram_values
*values
)
2043 stmt
= dyn_cast
<gcall
*> (gs
);
2046 fndecl
= gimple_call_fndecl (stmt
);
2050 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
2053 dest
= gimple_call_arg (stmt
, 0);
2054 blck_size
= gimple_call_arg (stmt
, size_arg
);
2056 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2058 values
->safe_push (gimple_alloc_histogram_value (cfun
,
2059 HIST_TYPE_SINGLE_VALUE
,
2061 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
2064 if (TREE_CODE (blck_size
) != INTEGER_CST
)
2065 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
2069 /* Find values inside STMT for that we want to measure histograms and adds
2070 them to list VALUES. */
2073 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
2075 gimple_divmod_values_to_profile (stmt
, values
);
2076 gimple_stringops_values_to_profile (stmt
, values
);
2077 gimple_indirect_call_to_profile (stmt
, values
);
2081 gimple_find_values_to_profile (histogram_values
*values
)
2084 gimple_stmt_iterator gsi
;
2086 histogram_value hist
= NULL
;
2089 FOR_EACH_BB_FN (bb
, cfun
)
2090 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2091 gimple_values_to_profile (gsi_stmt (gsi
), values
);
2093 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_TIME_PROFILE
, 0, 0));
2095 FOR_EACH_VEC_ELT (*values
, i
, hist
)
2099 case HIST_TYPE_INTERVAL
:
2100 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
2103 case HIST_TYPE_POW2
:
2104 hist
->n_counters
= 2;
2107 case HIST_TYPE_SINGLE_VALUE
:
2108 hist
->n_counters
= 3;
2111 case HIST_TYPE_CONST_DELTA
:
2112 hist
->n_counters
= 4;
2115 case HIST_TYPE_INDIR_CALL
:
2116 hist
->n_counters
= 3;
2119 case HIST_TYPE_TIME_PROFILE
:
2120 hist
->n_counters
= 1;
2123 case HIST_TYPE_AVERAGE
:
2124 hist
->n_counters
= 2;
2128 hist
->n_counters
= 1;
2131 case HIST_TYPE_INDIR_CALL_TOPN
:
2132 hist
->n_counters
= GCOV_ICALL_TOPN_NCOUNTS
;
2140 fprintf (dump_file
, "Stmt ");
2141 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
2142 dump_histogram_value (dump_file
, hist
);