1 /* Transformations based on profile information for values.
2 Copyright (C) 2003-2013 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"
26 #include "hard-reg-set.h"
27 #include "basic-block.h"
28 #include "value-prof.h"
30 #include "insn-config.h"
35 #include "tree-flow.h"
36 #include "tree-flow-inline.h"
37 #include "diagnostic.h"
38 #include "gimple-pretty-print.h"
45 #include "pointer-set.h"
47 #include "data-streamer.h"
49 /* In this file value profile based optimizations are placed. Currently the
50 following optimizations are implemented (for more detailed descriptions
51 see comments at value_profile_transformations):
53 1) Division/modulo specialization. Provided that we can determine that the
54 operands of the division have some special properties, we may use it to
55 produce more effective code.
57 2) Indirect/virtual call specialization. If we can determine most
58 common function callee in indirect/virtual call. We can use this
59 information to improve code effectiveness (especially info for
62 3) Speculative prefetching. If we are able to determine that the difference
63 between addresses accessed by a memory reference is usually constant, we
64 may add the prefetch instructions.
65 FIXME: This transformation was removed together with RTL based value
69 Value profiling internals
70 ==========================
72 Every value profiling transformation starts with defining what values
73 to profile. There are different histogram types (see HIST_TYPE_* in
74 value-prof.h) and each transformation can request one or more histogram
75 types per GIMPLE statement. The function gimple_find_values_to_profile()
76 collects the values to profile in a vec, and adds the number of counters
77 required for the different histogram types.
79 For a -fprofile-generate run, the statements for which values should be
80 recorded, are instrumented in instrument_values(). The instrumentation
81 is done by helper functions that can be found in tree-profile.c, where
82 new types of histograms can be added if necessary.
84 After a -fprofile-use, the value profiling data is read back in by
85 compute_value_histograms() that translates the collected data to
86 histograms and attaches them to the profiled statements via
87 gimple_add_histogram_value(). Histograms are stored in a hash table
88 that is attached to every intrumented function, see VALUE_HISTOGRAMS
91 The value-profile transformations driver is the function
92 gimple_value_profile_transformations(). It traverses all statements in
93 the to-be-transformed function, and looks for statements with one or
94 more histograms attached to it. If a statement has histograms, the
95 transformation functions are called on the statement.
97 Limitations / FIXME / TODO:
98 * Only one histogram of each type can be associated with a statement.
99 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
100 (This type of histogram was originally used to implement a form of
101 stride profiling based speculative prefetching to improve SPEC2000
102 scores for memory-bound benchmarks, mcf and equake. However, this
103 was an RTL value-profiling transformation, and those have all been
105 * Some value profile transformations are done in builtins.c (?!)
106 * Updating of histograms needs some TLC.
107 * The value profiling code could be used to record analysis results
108 from non-profiling (e.g. VRP).
109 * Adding new profilers should be simplified, starting with a cleanup
110 of what-happens-where andwith making gimple_find_values_to_profile
111 and gimple_value_profile_transformations table-driven, perhaps...
114 static tree
gimple_divmod_fixed_value (gimple
, tree
, int, gcov_type
, gcov_type
);
115 static tree
gimple_mod_pow2 (gimple
, int, gcov_type
, gcov_type
);
116 static tree
gimple_mod_subtract (gimple
, int, int, int, gcov_type
, gcov_type
,
118 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
119 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
120 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
121 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
122 static bool gimple_ic_transform (gimple_stmt_iterator
*);
124 /* Allocate histogram value. */
126 static histogram_value
127 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
128 enum hist_type type
, gimple stmt
, tree value
)
130 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
131 hist
->hvalue
.value
= value
;
132 hist
->hvalue
.stmt
= stmt
;
137 /* Hash value for histogram. */
140 histogram_hash (const void *x
)
142 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
145 /* Return nonzero if statement for histogram_value X is Y. */
148 histogram_eq (const void *x
, const void *y
)
150 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
153 /* Set histogram for STMT. */
156 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
159 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
161 if (!VALUE_HISTOGRAMS (fun
))
162 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
164 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
165 htab_hash_pointer (stmt
),
166 hist
? INSERT
: NO_INSERT
);
170 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
176 /* Get histogram list for STMT. */
179 gimple_histogram_value (struct function
*fun
, gimple stmt
)
181 if (!VALUE_HISTOGRAMS (fun
))
183 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
184 htab_hash_pointer (stmt
));
187 /* Add histogram for STMT. */
190 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
191 histogram_value hist
)
193 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
194 set_histogram_value (fun
, stmt
, hist
);
198 /* Remove histogram HIST from STMT's histogram list. */
201 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
202 histogram_value hist
)
204 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
207 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
211 while (hist2
->hvalue
.next
!= hist
)
212 hist2
= hist2
->hvalue
.next
;
213 hist2
->hvalue
.next
= hist
->hvalue
.next
;
215 free (hist
->hvalue
.counters
);
216 #ifdef ENABLE_CHECKING
217 memset (hist
, 0xab, sizeof (*hist
));
223 /* Lookup histogram of type TYPE in the STMT. */
226 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
229 histogram_value hist
;
230 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
231 hist
= hist
->hvalue
.next
)
232 if (hist
->type
== type
)
237 /* Dump information about HIST to DUMP_FILE. */
240 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
244 case HIST_TYPE_INTERVAL
:
245 fprintf (dump_file
, "Interval counter range %d -- %d",
246 hist
->hdata
.intvl
.int_start
,
247 (hist
->hdata
.intvl
.int_start
248 + hist
->hdata
.intvl
.steps
- 1));
249 if (hist
->hvalue
.counters
)
252 fprintf(dump_file
, " [");
253 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
254 fprintf (dump_file
, " %d:"HOST_WIDEST_INT_PRINT_DEC
,
255 hist
->hdata
.intvl
.int_start
+ i
,
256 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
257 fprintf (dump_file
, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC
,
258 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
260 fprintf (dump_file
, ".\n");
264 fprintf (dump_file
, "Pow2 counter ");
265 if (hist
->hvalue
.counters
)
267 fprintf (dump_file
, "pow2:"HOST_WIDEST_INT_PRINT_DEC
268 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC
,
269 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
270 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
272 fprintf (dump_file
, ".\n");
275 case HIST_TYPE_SINGLE_VALUE
:
276 fprintf (dump_file
, "Single value ");
277 if (hist
->hvalue
.counters
)
279 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
280 " match:"HOST_WIDEST_INT_PRINT_DEC
281 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
282 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
283 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
284 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
286 fprintf (dump_file
, ".\n");
289 case HIST_TYPE_AVERAGE
:
290 fprintf (dump_file
, "Average value ");
291 if (hist
->hvalue
.counters
)
293 fprintf (dump_file
, "sum:"HOST_WIDEST_INT_PRINT_DEC
294 " times:"HOST_WIDEST_INT_PRINT_DEC
,
295 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
296 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
298 fprintf (dump_file
, ".\n");
302 fprintf (dump_file
, "IOR value ");
303 if (hist
->hvalue
.counters
)
305 fprintf (dump_file
, "ior:"HOST_WIDEST_INT_PRINT_DEC
,
306 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0]);
308 fprintf (dump_file
, ".\n");
311 case HIST_TYPE_CONST_DELTA
:
312 fprintf (dump_file
, "Constant delta ");
313 if (hist
->hvalue
.counters
)
315 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
316 " match:"HOST_WIDEST_INT_PRINT_DEC
317 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
318 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
319 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
320 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
322 fprintf (dump_file
, ".\n");
324 case HIST_TYPE_INDIR_CALL
:
325 fprintf (dump_file
, "Indirect call ");
326 if (hist
->hvalue
.counters
)
328 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
329 " match:"HOST_WIDEST_INT_PRINT_DEC
330 " all:"HOST_WIDEST_INT_PRINT_DEC
,
331 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
332 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
333 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
335 fprintf (dump_file
, ".\n");
342 /* Dump information about HIST to DUMP_FILE. */
345 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
350 bp
= bitpack_create (ob
->main_stream
);
351 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
352 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
353 streamer_write_bitpack (&bp
);
356 case HIST_TYPE_INTERVAL
:
357 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
358 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
363 for (i
= 0; i
< hist
->n_counters
; i
++)
364 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
365 if (hist
->hvalue
.next
)
366 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
368 /* Dump information about HIST to DUMP_FILE. */
371 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
374 unsigned int ncounters
= 0;
377 histogram_value new_val
;
379 histogram_value
*next_p
= NULL
;
383 bp
= streamer_read_bitpack (ib
);
384 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
385 next
= bp_unpack_value (&bp
, 1);
386 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
389 case HIST_TYPE_INTERVAL
:
390 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
391 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
392 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
396 case HIST_TYPE_AVERAGE
:
400 case HIST_TYPE_SINGLE_VALUE
:
401 case HIST_TYPE_INDIR_CALL
:
405 case HIST_TYPE_CONST_DELTA
:
415 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
416 new_val
->n_counters
= ncounters
;
417 for (i
= 0; i
< ncounters
; i
++)
418 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
420 gimple_add_histogram_value (cfun
, stmt
, new_val
);
423 next_p
= &new_val
->hvalue
.next
;
428 /* Dump all histograms attached to STMT to DUMP_FILE. */
431 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
433 histogram_value hist
;
434 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
435 dump_histogram_value (dump_file
, hist
);
438 /* Remove all histograms associated with STMT. */
441 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
444 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
445 gimple_remove_histogram_value (fun
, stmt
, val
);
448 /* Duplicate all histograms associates with OSTMT to STMT. */
451 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
452 struct function
*ofun
, gimple ostmt
)
455 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
457 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
458 memcpy (new_val
, val
, sizeof (*val
));
459 new_val
->hvalue
.stmt
= stmt
;
460 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
461 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
462 gimple_add_histogram_value (fun
, stmt
, new_val
);
467 /* Move all histograms associated with OSTMT to STMT. */
470 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
472 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
475 /* The following three statements can't be reordered,
476 because histogram hashtab relies on stmt field value
477 for finding the exact slot. */
478 set_histogram_value (fun
, ostmt
, NULL
);
479 for (; val
!= NULL
; val
= val
->hvalue
.next
)
480 val
->hvalue
.stmt
= stmt
;
481 set_histogram_value (fun
, stmt
, val
);
485 static bool error_found
= false;
487 /* Helper function for verify_histograms. For each histogram reachable via htab
488 walk verify that it was reached via statement walk. */
491 visit_hist (void **slot
, void *data
)
493 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
494 histogram_value hist
= *(histogram_value
*) slot
;
495 if (!pointer_set_contains (visited
, hist
))
497 error ("dead histogram");
498 dump_histogram_value (stderr
, hist
);
499 debug_gimple_stmt (hist
->hvalue
.stmt
);
506 /* Verify sanity of the histograms. */
509 verify_histograms (void)
512 gimple_stmt_iterator gsi
;
513 histogram_value hist
;
514 struct pointer_set_t
*visited_hists
;
517 visited_hists
= pointer_set_create ();
519 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
521 gimple stmt
= gsi_stmt (gsi
);
523 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
524 hist
= hist
->hvalue
.next
)
526 if (hist
->hvalue
.stmt
!= stmt
)
528 error ("Histogram value statement does not correspond to "
529 "the statement it is associated with");
530 debug_gimple_stmt (stmt
);
531 dump_histogram_value (stderr
, hist
);
534 pointer_set_insert (visited_hists
, hist
);
537 if (VALUE_HISTOGRAMS (cfun
))
538 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, visited_hists
);
539 pointer_set_destroy (visited_hists
);
541 internal_error ("verify_histograms failed");
544 /* Helper function for verify_histograms. For each histogram reachable via htab
545 walk verify that it was reached via statement walk. */
548 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
550 histogram_value hist
= *(histogram_value
*) slot
;
551 free (hist
->hvalue
.counters
);
552 #ifdef ENABLE_CHECKING
553 memset (hist
, 0xab, sizeof (*hist
));
560 free_histograms (void)
562 if (VALUE_HISTOGRAMS (cfun
))
564 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
565 htab_delete (VALUE_HISTOGRAMS (cfun
));
566 VALUE_HISTOGRAMS (cfun
) = NULL
;
571 /* The overall number of invocations of the counter should match
572 execution count of basic block. Report it as error rather than
573 internal error as it might mean that user has misused the profile
577 check_counter (gimple stmt
, const char * name
,
578 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
580 if (*all
!= bb_count
|| *count
> *all
)
583 locus
= (stmt
!= NULL
)
584 ? gimple_location (stmt
)
585 : DECL_SOURCE_LOCATION (current_function_decl
);
586 if (flag_profile_correction
)
588 inform (locus
, "correcting inconsistent value profile: "
589 "%s profiler overall count (%d) does not match BB count "
590 "(%d)", name
, (int)*all
, (int)bb_count
);
598 error_at (locus
, "corrupted value profile: %s "
599 "profile counter (%d out of %d) inconsistent with "
600 "basic-block count (%d)",
613 /* GIMPLE based transformations. */
616 gimple_value_profile_transformations (void)
619 gimple_stmt_iterator gsi
;
620 bool changed
= false;
624 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
626 gimple stmt
= gsi_stmt (gsi
);
627 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
633 fprintf (dump_file
, "Trying transformations on stmt ");
634 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
635 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
638 /* Transformations: */
639 /* The order of things in this conditional controls which
640 transformation is used when more than one is applicable. */
641 /* It is expected that any code added by the transformations
642 will be added before the current statement, and that the
643 current statement remain valid (although possibly
644 modified) upon return. */
645 if (gimple_mod_subtract_transform (&gsi
)
646 || gimple_divmod_fixed_value_transform (&gsi
)
647 || gimple_mod_pow2_value_transform (&gsi
)
648 || gimple_stringops_transform (&gsi
)
649 || gimple_ic_transform (&gsi
))
651 stmt
= gsi_stmt (gsi
);
653 /* Original statement may no longer be in the same block. */
654 if (bb
!= gimple_bb (stmt
))
656 bb
= gimple_bb (stmt
);
657 gsi
= gsi_for_stmt (stmt
);
672 /* Generate code for transformation 1 (with parent gimple assignment
673 STMT and probability of taking the optimal path PROB, which is
674 equivalent to COUNT/ALL within roundoff error). This generates the
675 result into a temp and returns the temp; it does not replace or
676 alter the original STMT. */
679 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
682 gimple stmt1
, stmt2
, stmt3
;
683 tree tmp0
, tmp1
, tmp2
;
684 gimple bb1end
, bb2end
, bb3end
;
685 basic_block bb
, bb2
, bb3
, bb4
;
686 tree optype
, op1
, op2
;
687 edge e12
, e13
, e23
, e24
, e34
;
688 gimple_stmt_iterator gsi
;
690 gcc_assert (is_gimple_assign (stmt
)
691 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
692 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
694 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
695 op1
= gimple_assign_rhs1 (stmt
);
696 op2
= gimple_assign_rhs2 (stmt
);
698 bb
= gimple_bb (stmt
);
699 gsi
= gsi_for_stmt (stmt
);
701 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
702 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
703 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
704 stmt2
= gimple_build_assign (tmp1
, op2
);
705 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
706 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
707 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
708 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
711 tmp2
= create_tmp_reg (optype
, "PROF");
712 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
714 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
717 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
719 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
723 /* Edge e23 connects bb2 to bb3, etc. */
724 e12
= split_block (bb
, bb1end
);
727 e23
= split_block (bb2
, bb2end
);
729 bb3
->count
= all
- count
;
730 e34
= split_block (bb3
, bb3end
);
734 e12
->flags
&= ~EDGE_FALLTHRU
;
735 e12
->flags
|= EDGE_FALSE_VALUE
;
736 e12
->probability
= prob
;
739 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
740 e13
->probability
= REG_BR_PROB_BASE
- prob
;
741 e13
->count
= all
- count
;
745 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
746 e24
->probability
= REG_BR_PROB_BASE
;
749 e34
->probability
= REG_BR_PROB_BASE
;
750 e34
->count
= all
- count
;
756 /* Do transform 1) on INSN if applicable. */
759 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
761 histogram_value histogram
;
763 gcov_type val
, count
, all
;
764 tree result
, value
, tree_val
;
768 stmt
= gsi_stmt (*si
);
769 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
772 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
775 code
= gimple_assign_rhs_code (stmt
);
777 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
780 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
781 HIST_TYPE_SINGLE_VALUE
);
785 value
= histogram
->hvalue
.value
;
786 val
= histogram
->hvalue
.counters
[0];
787 count
= histogram
->hvalue
.counters
[1];
788 all
= histogram
->hvalue
.counters
[2];
789 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
791 /* We require that count is at least half of all; this means
792 that for the transformation to fire the value must be constant
793 at least 50% of time (and 75% gives the guarantee of usage). */
794 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
796 || optimize_bb_for_size_p (gimple_bb (stmt
)))
799 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
802 /* Compute probability of taking the optimal path. */
804 prob
= GCOV_COMPUTE_SCALE (count
, all
);
808 tree_val
= build_int_cst_wide (get_gcov_type (),
809 (unsigned HOST_WIDE_INT
) val
,
810 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
811 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
815 fprintf (dump_file
, "Div/mod by constant ");
816 print_generic_expr (dump_file
, value
, TDF_SLIM
);
817 fprintf (dump_file
, "=");
818 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
819 fprintf (dump_file
, " transformation on insn ");
820 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
823 gimple_assign_set_rhs_from_tree (si
, result
);
824 update_stmt (gsi_stmt (*si
));
829 /* Generate code for transformation 2 (with parent gimple assign STMT and
830 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
831 within roundoff error). This generates the result into a temp and returns
832 the temp; it does not replace or alter the original STMT. */
834 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
836 gimple stmt1
, stmt2
, stmt3
, stmt4
;
838 gimple bb1end
, bb2end
, bb3end
;
839 basic_block bb
, bb2
, bb3
, bb4
;
840 tree optype
, op1
, op2
;
841 edge e12
, e13
, e23
, e24
, e34
;
842 gimple_stmt_iterator gsi
;
845 gcc_assert (is_gimple_assign (stmt
)
846 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
848 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
849 op1
= gimple_assign_rhs1 (stmt
);
850 op2
= gimple_assign_rhs2 (stmt
);
852 bb
= gimple_bb (stmt
);
853 gsi
= gsi_for_stmt (stmt
);
855 result
= create_tmp_reg (optype
, "PROF");
856 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
857 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
858 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
859 build_int_cst (optype
, -1));
860 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
861 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
862 NULL_TREE
, NULL_TREE
);
863 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
864 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
865 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
868 /* tmp2 == op2-1 inherited from previous block. */
869 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
870 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
873 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
875 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
879 /* Edge e23 connects bb2 to bb3, etc. */
880 e12
= split_block (bb
, bb1end
);
883 e23
= split_block (bb2
, bb2end
);
885 bb3
->count
= all
- count
;
886 e34
= split_block (bb3
, bb3end
);
890 e12
->flags
&= ~EDGE_FALLTHRU
;
891 e12
->flags
|= EDGE_FALSE_VALUE
;
892 e12
->probability
= prob
;
895 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
896 e13
->probability
= REG_BR_PROB_BASE
- prob
;
897 e13
->count
= all
- count
;
901 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
902 e24
->probability
= REG_BR_PROB_BASE
;
905 e34
->probability
= REG_BR_PROB_BASE
;
906 e34
->count
= all
- count
;
911 /* Do transform 2) on INSN if applicable. */
913 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
915 histogram_value histogram
;
917 gcov_type count
, wrong_values
, all
;
918 tree lhs_type
, result
, value
;
922 stmt
= gsi_stmt (*si
);
923 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
926 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
927 if (!INTEGRAL_TYPE_P (lhs_type
))
930 code
= gimple_assign_rhs_code (stmt
);
932 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
935 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
939 value
= histogram
->hvalue
.value
;
940 wrong_values
= histogram
->hvalue
.counters
[0];
941 count
= histogram
->hvalue
.counters
[1];
943 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
945 /* We require that we hit a power of 2 at least half of all evaluations. */
946 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
947 || count
< wrong_values
948 || optimize_bb_for_size_p (gimple_bb (stmt
)))
953 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
954 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
957 /* Compute probability of taking the optimal path. */
958 all
= count
+ wrong_values
;
960 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
964 prob
= GCOV_COMPUTE_SCALE (count
, all
);
968 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
970 gimple_assign_set_rhs_from_tree (si
, result
);
971 update_stmt (gsi_stmt (*si
));
976 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
977 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
978 supported and this is built into this interface. The probabilities of taking
979 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
980 COUNT2/ALL respectively within roundoff error). This generates the
981 result into a temp and returns the temp; it does not replace or alter
982 the original STMT. */
983 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
986 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
987 gcov_type count1
, gcov_type count2
, gcov_type all
)
989 gimple stmt1
, stmt2
, stmt3
;
991 gimple bb1end
, bb2end
= NULL
, bb3end
;
992 basic_block bb
, bb2
, bb3
, bb4
;
993 tree optype
, op1
, op2
;
994 edge e12
, e23
= 0, e24
, e34
, e14
;
995 gimple_stmt_iterator gsi
;
998 gcc_assert (is_gimple_assign (stmt
)
999 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1001 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1002 op1
= gimple_assign_rhs1 (stmt
);
1003 op2
= gimple_assign_rhs2 (stmt
);
1005 bb
= gimple_bb (stmt
);
1006 gsi
= gsi_for_stmt (stmt
);
1008 result
= create_tmp_reg (optype
, "PROF");
1009 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1010 stmt1
= gimple_build_assign (result
, op1
);
1011 stmt2
= gimple_build_assign (tmp1
, op2
);
1012 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1013 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1014 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1015 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1018 if (ncounts
) /* Assumed to be 0 or 1 */
1020 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
1021 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1022 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1023 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1027 /* Fallback case. */
1028 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
1030 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1034 /* Edge e23 connects bb2 to bb3, etc. */
1035 /* However block 3 is optional; if it is not there, references
1036 to 3 really refer to block 2. */
1037 e12
= split_block (bb
, bb1end
);
1039 bb2
->count
= all
- count1
;
1041 if (ncounts
) /* Assumed to be 0 or 1. */
1043 e23
= split_block (bb2
, bb2end
);
1045 bb3
->count
= all
- count1
- count2
;
1048 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1052 e12
->flags
&= ~EDGE_FALLTHRU
;
1053 e12
->flags
|= EDGE_FALSE_VALUE
;
1054 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1055 e12
->count
= all
- count1
;
1057 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1058 e14
->probability
= prob1
;
1059 e14
->count
= count1
;
1061 if (ncounts
) /* Assumed to be 0 or 1. */
1063 e23
->flags
&= ~EDGE_FALLTHRU
;
1064 e23
->flags
|= EDGE_FALSE_VALUE
;
1065 e23
->count
= all
- count1
- count2
;
1066 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1068 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1069 e24
->probability
= prob2
;
1070 e24
->count
= count2
;
1073 e34
->probability
= REG_BR_PROB_BASE
;
1074 e34
->count
= all
- count1
- count2
;
1080 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1083 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1085 histogram_value histogram
;
1086 enum tree_code code
;
1087 gcov_type count
, wrong_values
, all
;
1088 tree lhs_type
, result
;
1089 gcov_type prob1
, prob2
;
1090 unsigned int i
, steps
;
1091 gcov_type count1
, count2
;
1094 stmt
= gsi_stmt (*si
);
1095 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1098 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1099 if (!INTEGRAL_TYPE_P (lhs_type
))
1102 code
= gimple_assign_rhs_code (stmt
);
1104 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1107 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1113 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1114 all
+= histogram
->hvalue
.counters
[i
];
1116 wrong_values
+= histogram
->hvalue
.counters
[i
];
1117 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1118 steps
= histogram
->hdata
.intvl
.steps
;
1119 all
+= wrong_values
;
1120 count1
= histogram
->hvalue
.counters
[0];
1121 count2
= histogram
->hvalue
.counters
[1];
1123 /* Compute probability of taking the optimal path. */
1124 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1126 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1130 if (flag_profile_correction
&& count1
+ count2
> all
)
1131 all
= count1
+ count2
;
1133 gcc_assert (count1
+ count2
<= all
);
1135 /* We require that we use just subtractions in at least 50% of all
1138 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1140 count
+= histogram
->hvalue
.counters
[i
];
1141 if (count
* 2 >= all
)
1145 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1148 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1151 fprintf (dump_file
, "Mod subtract transformation on insn ");
1152 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1155 /* Compute probability of taking the optimal path(s). */
1158 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1159 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1166 /* In practice, "steps" is always 2. This interface reflects this,
1167 and will need to be changed if "steps" can change. */
1168 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1170 gimple_assign_set_rhs_from_tree (si
, result
);
1171 update_stmt (gsi_stmt (*si
));
1176 static pointer_map_t
*cgraph_node_map
;
1178 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1179 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1180 that the PROFILE_IDs was already assigned. */
1183 init_node_map (bool local
)
1185 struct cgraph_node
*n
;
1186 cgraph_node_map
= pointer_map_create ();
1188 FOR_EACH_DEFINED_FUNCTION (n
)
1189 if (cgraph_function_with_gimple_body_p (n
)
1190 && !cgraph_only_called_directly_p (n
))
1195 n
->profile_id
= coverage_compute_profile_id (n
);
1196 while ((val
= pointer_map_contains (cgraph_node_map
,
1197 (void *)(size_t)n
->profile_id
))
1201 fprintf (dump_file
, "Local profile-id %i conflict"
1202 " with nodes %s/%i %s/%i\n",
1204 cgraph_node_name (n
),
1206 symtab_node_name (*(symtab_node
*)val
),
1207 (*(symtab_node
*)val
)->symbol
.order
);
1208 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1211 else if (!n
->profile_id
)
1215 "Node %s/%i has no profile-id"
1216 " (profile feedback missing?)\n",
1217 cgraph_node_name (n
),
1221 else if ((val
= pointer_map_contains (cgraph_node_map
,
1222 (void *)(size_t)n
->profile_id
)))
1226 "Node %s/%i has IP profile-id %i conflict. "
1228 cgraph_node_name (n
),
1234 *pointer_map_insert (cgraph_node_map
,
1235 (void *)(size_t)n
->profile_id
) = (void *)n
;
1239 /* Delete the CGRAPH_NODE_MAP. */
1244 pointer_map_destroy (cgraph_node_map
);
1247 /* Return cgraph node for function with pid */
1250 find_func_by_profile_id (int profile_id
)
1252 void **val
= pointer_map_contains (cgraph_node_map
,
1253 (void *)(size_t)profile_id
);
1255 return (struct cgraph_node
*)*val
;
1260 /* Perform sanity check on the indirect call target. Due to race conditions,
1261 false function target may be attributed to an indirect call site. If the
1262 call expression type mismatches with the target function's type, expand_call
1263 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1264 Returns true if TARGET is considered ok for call CALL_STMT. */
1267 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1270 if (gimple_check_call_matching_types (call_stmt
, target
->symbol
.decl
, true))
1273 locus
= gimple_location (call_stmt
);
1274 inform (locus
, "Skipping target %s with mismatching types for icall ",
1275 cgraph_node_name (target
));
1279 /* Do transformation
1281 if (actual_callee_address == address_of_most_common_function/method)
1288 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1289 int prob
, gcov_type count
, gcov_type all
)
1291 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1292 tree tmp0
, tmp1
, tmp
;
1293 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1294 tree optype
= build_pointer_type (void_type_node
);
1295 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1296 gimple_stmt_iterator gsi
;
1299 cond_bb
= gimple_bb (icall_stmt
);
1300 gsi
= gsi_for_stmt (icall_stmt
);
1302 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1303 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1304 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1305 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1306 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1308 tmp
= fold_convert (optype
, build_addr (direct_call
->symbol
.decl
,
1309 current_function_decl
));
1310 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1311 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1313 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1314 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1316 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1317 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1318 update_stmt (icall_stmt
);
1319 dcall_stmt
= gimple_copy (icall_stmt
);
1320 gimple_call_set_fndecl (dcall_stmt
, direct_call
->symbol
.decl
);
1321 dflags
= flags_from_decl_or_type (direct_call
->symbol
.decl
);
1322 if ((dflags
& ECF_NORETURN
) != 0)
1323 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1324 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1327 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1328 e_cd
= split_block (cond_bb
, cond_stmt
);
1329 dcall_bb
= e_cd
->dest
;
1330 dcall_bb
->count
= count
;
1332 e_di
= split_block (dcall_bb
, dcall_stmt
);
1333 icall_bb
= e_di
->dest
;
1334 icall_bb
->count
= all
- count
;
1336 /* Do not disturb existing EH edges from the indirect call. */
1337 if (!stmt_ends_bb_p (icall_stmt
))
1338 e_ij
= split_block (icall_bb
, icall_stmt
);
1341 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1342 /* The indirect call might be noreturn. */
1345 e_ij
->probability
= REG_BR_PROB_BASE
;
1346 e_ij
->count
= all
- count
;
1347 e_ij
= single_pred_edge (split_edge (e_ij
));
1352 join_bb
= e_ij
->dest
;
1353 join_bb
->count
= all
;
1356 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1357 e_cd
->probability
= prob
;
1358 e_cd
->count
= count
;
1360 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1361 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1362 e_ci
->count
= all
- count
;
1368 if ((dflags
& ECF_NORETURN
) != 0)
1372 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1373 e_dj
->probability
= REG_BR_PROB_BASE
;
1374 e_dj
->count
= count
;
1376 e_ij
->count
= all
- count
;
1378 e_ij
->probability
= REG_BR_PROB_BASE
;
1381 /* Insert PHI node for the call result if necessary. */
1382 if (gimple_call_lhs (icall_stmt
)
1383 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1384 && (dflags
& ECF_NORETURN
) == 0)
1386 tree result
= gimple_call_lhs (icall_stmt
);
1387 gimple phi
= create_phi_node (result
, join_bb
);
1388 gimple_call_set_lhs (icall_stmt
,
1389 duplicate_ssa_name (result
, icall_stmt
));
1390 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1391 gimple_call_set_lhs (dcall_stmt
,
1392 duplicate_ssa_name (result
, dcall_stmt
));
1393 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1396 /* Build an EH edge for the direct call if necessary. */
1397 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1398 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1402 gimple_stmt_iterator psi
;
1404 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1405 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1406 if (e_eh
->flags
& EDGE_EH
)
1408 e
= make_edge (dcall_bb
, e_eh
->dest
, EDGE_EH
);
1409 for (psi
= gsi_start_phis (e_eh
->dest
);
1410 !gsi_end_p (psi
); gsi_next (&psi
))
1412 gimple phi
= gsi_stmt (psi
);
1413 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1414 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1422 For every checked indirect/virtual call determine if most common pid of
1423 function/class method has probability more than 50%. If yes modify code of
1428 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1430 gimple stmt
= gsi_stmt (*gsi
);
1431 histogram_value histogram
;
1432 gcov_type val
, count
, all
, bb_all
;
1433 struct cgraph_node
*direct_call
;
1435 if (gimple_code (stmt
) != GIMPLE_CALL
)
1438 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1441 if (gimple_call_internal_p (stmt
))
1444 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1448 val
= histogram
->hvalue
.counters
[0];
1449 count
= histogram
->hvalue
.counters
[1];
1450 all
= histogram
->hvalue
.counters
[2];
1452 bb_all
= gimple_bb (stmt
)->count
;
1453 /* The order of CHECK_COUNTER calls is important -
1454 since check_counter can correct the third parameter
1455 and we want to make count <= all <= bb_all. */
1456 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1457 || check_counter (stmt
, "ic", &count
, &all
, all
))
1459 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1463 if (4 * count
<= 3 * all
)
1466 direct_call
= find_func_by_profile_id ((int)val
);
1468 if (direct_call
== NULL
)
1474 fprintf (dump_file
, "Indirect call -> direct call from other module");
1475 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1476 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1482 if (!check_ic_target (stmt
, direct_call
))
1486 fprintf (dump_file
, "Indirect call -> direct call ");
1487 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1488 fprintf (dump_file
, "=> ");
1489 print_generic_expr (dump_file
, direct_call
->symbol
.decl
, TDF_SLIM
);
1490 fprintf (dump_file
, " transformation skipped because of type mismatch");
1491 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1493 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1499 fprintf (dump_file
, "Indirect call -> direct call ");
1500 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1501 fprintf (dump_file
, "=> ");
1502 print_generic_expr (dump_file
, direct_call
->symbol
.decl
, TDF_SLIM
);
1503 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1504 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1505 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1506 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1512 /* Return true if the stringop CALL with FNDECL shall be profiled.
1513 SIZE_ARG be set to the argument index for the size of the string
1517 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1519 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1521 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1522 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1527 case BUILT_IN_MEMCPY
:
1528 case BUILT_IN_MEMPCPY
:
1530 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1531 INTEGER_TYPE
, VOID_TYPE
);
1532 case BUILT_IN_MEMSET
:
1534 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1535 INTEGER_TYPE
, VOID_TYPE
);
1536 case BUILT_IN_BZERO
:
1538 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1545 /* Convert stringop (..., vcall_size)
1547 if (vcall_size == icall_size)
1548 stringop (..., icall_size);
1550 stringop (..., vcall_size);
1551 assuming we'll propagate a true constant into ICALL_SIZE later. */
1554 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1555 gcov_type count
, gcov_type all
)
1557 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1558 tree tmp0
, tmp1
, vcall_size
, optype
;
1559 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1560 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1561 gimple_stmt_iterator gsi
;
1565 fndecl
= gimple_call_fndecl (vcall_stmt
);
1566 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1569 cond_bb
= gimple_bb (vcall_stmt
);
1570 gsi
= gsi_for_stmt (vcall_stmt
);
1572 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1573 optype
= TREE_TYPE (vcall_size
);
1575 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1576 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1577 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1578 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1580 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1581 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1583 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1584 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1586 gimple_set_vdef (vcall_stmt
, NULL
);
1587 gimple_set_vuse (vcall_stmt
, NULL
);
1588 update_stmt (vcall_stmt
);
1589 icall_stmt
= gimple_copy (vcall_stmt
);
1590 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1591 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1594 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1595 e_ci
= split_block (cond_bb
, cond_stmt
);
1596 icall_bb
= e_ci
->dest
;
1597 icall_bb
->count
= count
;
1599 e_iv
= split_block (icall_bb
, icall_stmt
);
1600 vcall_bb
= e_iv
->dest
;
1601 vcall_bb
->count
= all
- count
;
1603 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1604 join_bb
= e_vj
->dest
;
1605 join_bb
->count
= all
;
1607 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1608 e_ci
->probability
= prob
;
1609 e_ci
->count
= count
;
1611 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1612 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1613 e_cv
->count
= all
- count
;
1617 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1618 e_ij
->probability
= REG_BR_PROB_BASE
;
1619 e_ij
->count
= count
;
1621 e_vj
->probability
= REG_BR_PROB_BASE
;
1622 e_vj
->count
= all
- count
;
1624 /* Insert PHI node for the call result if necessary. */
1625 if (gimple_call_lhs (vcall_stmt
)
1626 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1628 tree result
= gimple_call_lhs (vcall_stmt
);
1629 gimple phi
= create_phi_node (result
, join_bb
);
1630 gimple_call_set_lhs (vcall_stmt
,
1631 duplicate_ssa_name (result
, vcall_stmt
));
1632 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1633 gimple_call_set_lhs (icall_stmt
,
1634 duplicate_ssa_name (result
, icall_stmt
));
1635 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1638 /* Because these are all string op builtins, they're all nothrow. */
1639 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1640 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1643 /* Find values inside STMT for that we want to measure histograms for
1644 division/modulo optimization. */
1646 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1648 gimple stmt
= gsi_stmt (*gsi
);
1651 enum built_in_function fcode
;
1652 histogram_value histogram
;
1653 gcov_type count
, all
, val
;
1655 unsigned int dest_align
, src_align
;
1660 if (gimple_code (stmt
) != GIMPLE_CALL
)
1662 fndecl
= gimple_call_fndecl (stmt
);
1665 fcode
= DECL_FUNCTION_CODE (fndecl
);
1666 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1669 blck_size
= gimple_call_arg (stmt
, size_arg
);
1670 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1673 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1676 val
= histogram
->hvalue
.counters
[0];
1677 count
= histogram
->hvalue
.counters
[1];
1678 all
= histogram
->hvalue
.counters
[2];
1679 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1680 /* We require that count is at least half of all; this means
1681 that for the transformation to fire the value must be constant
1682 at least 80% of time. */
1683 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1685 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1688 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1691 dest
= gimple_call_arg (stmt
, 0);
1692 dest_align
= get_pointer_alignment (dest
);
1695 case BUILT_IN_MEMCPY
:
1696 case BUILT_IN_MEMPCPY
:
1697 src
= gimple_call_arg (stmt
, 1);
1698 src_align
= get_pointer_alignment (src
);
1699 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1702 case BUILT_IN_MEMSET
:
1703 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1704 gimple_call_arg (stmt
, 1),
1708 case BUILT_IN_BZERO
:
1709 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1717 tree_val
= build_int_cst_wide (get_gcov_type (),
1718 (unsigned HOST_WIDE_INT
) val
,
1719 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1722 fprintf (dump_file
, "Single value %i stringop transformation on ",
1724 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1726 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1732 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1733 HOST_WIDE_INT
*expected_size
)
1735 histogram_value histogram
;
1736 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1738 *expected_size
= -1;
1739 else if (!histogram
->hvalue
.counters
[1])
1741 *expected_size
= -1;
1742 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1747 size
= ((histogram
->hvalue
.counters
[0]
1748 + histogram
->hvalue
.counters
[1] / 2)
1749 / histogram
->hvalue
.counters
[1]);
1750 /* Even if we can hold bigger value in SIZE, INT_MAX
1751 is safe "infinity" for code generation strategies. */
1754 *expected_size
= size
;
1755 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1757 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1759 *expected_align
= 0;
1760 else if (!histogram
->hvalue
.counters
[0])
1762 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1763 *expected_align
= 0;
1770 count
= histogram
->hvalue
.counters
[0];
1772 while (!(count
& alignment
)
1773 && (alignment
* 2 * BITS_PER_UNIT
))
1775 *expected_align
= alignment
* BITS_PER_UNIT
;
1776 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1781 /* Find values inside STMT for that we want to measure histograms for
1782 division/modulo optimization. */
1784 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1786 tree lhs
, divisor
, op0
, type
;
1787 histogram_value hist
;
1789 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1792 lhs
= gimple_assign_lhs (stmt
);
1793 type
= TREE_TYPE (lhs
);
1794 if (!INTEGRAL_TYPE_P (type
))
1797 switch (gimple_assign_rhs_code (stmt
))
1799 case TRUNC_DIV_EXPR
:
1800 case TRUNC_MOD_EXPR
:
1801 divisor
= gimple_assign_rhs2 (stmt
);
1802 op0
= gimple_assign_rhs1 (stmt
);
1804 values
->reserve (3);
1806 if (TREE_CODE (divisor
) == SSA_NAME
)
1807 /* Check for the case where the divisor is the same value most
1809 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1810 HIST_TYPE_SINGLE_VALUE
,
1813 /* For mod, check whether it is not often a noop (or replaceable by
1814 a few subtractions). */
1815 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1816 && TYPE_UNSIGNED (type
))
1819 /* Check for a special case where the divisor is power of 2. */
1820 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1824 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1825 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1827 hist
->hdata
.intvl
.int_start
= 0;
1828 hist
->hdata
.intvl
.steps
= 2;
1829 values
->quick_push (hist
);
1838 /* Find calls inside STMT for that we want to measure histograms for
1839 indirect/virtual call optimization. */
1842 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1846 if (gimple_code (stmt
) != GIMPLE_CALL
1847 || gimple_call_internal_p (stmt
)
1848 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1851 callee
= gimple_call_fn (stmt
);
1853 values
->reserve (3);
1855 values
->quick_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1861 /* Find values inside STMT for that we want to measure histograms for
1862 string operations. */
1864 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1871 if (gimple_code (stmt
) != GIMPLE_CALL
)
1873 fndecl
= gimple_call_fndecl (stmt
);
1877 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1880 dest
= gimple_call_arg (stmt
, 0);
1881 blck_size
= gimple_call_arg (stmt
, size_arg
);
1883 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1885 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1886 HIST_TYPE_SINGLE_VALUE
,
1888 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1891 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1892 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1896 /* Find values inside STMT for that we want to measure histograms and adds
1897 them to list VALUES. */
1900 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1902 gimple_divmod_values_to_profile (stmt
, values
);
1903 gimple_stringops_values_to_profile (stmt
, values
);
1904 gimple_indirect_call_to_profile (stmt
, values
);
1908 gimple_find_values_to_profile (histogram_values
*values
)
1911 gimple_stmt_iterator gsi
;
1913 histogram_value hist
= NULL
;
1917 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1918 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1920 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1924 case HIST_TYPE_INTERVAL
:
1925 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1928 case HIST_TYPE_POW2
:
1929 hist
->n_counters
= 2;
1932 case HIST_TYPE_SINGLE_VALUE
:
1933 hist
->n_counters
= 3;
1936 case HIST_TYPE_CONST_DELTA
:
1937 hist
->n_counters
= 4;
1940 case HIST_TYPE_INDIR_CALL
:
1941 hist
->n_counters
= 3;
1944 case HIST_TYPE_AVERAGE
:
1945 hist
->n_counters
= 2;
1949 hist
->n_counters
= 1;
1957 fprintf (dump_file
, "Stmt ");
1958 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1959 dump_histogram_value (dump_file
, hist
);