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"
36 #include "diagnostic.h"
37 #include "gimple-pretty-print.h"
44 #include "pointer-set.h"
46 #include "data-streamer.h"
48 /* In this file value profile based optimizations are placed. Currently the
49 following optimizations are implemented (for more detailed descriptions
50 see comments at value_profile_transformations):
52 1) Division/modulo specialization. Provided that we can determine that the
53 operands of the division have some special properties, we may use it to
54 produce more effective code.
56 2) Indirect/virtual call specialization. If we can determine most
57 common function callee in indirect/virtual call. We can use this
58 information to improve code effectiveness (especially info for
61 3) Speculative prefetching. If we are able to determine that the difference
62 between addresses accessed by a memory reference is usually constant, we
63 may add the prefetch instructions.
64 FIXME: This transformation was removed together with RTL based value
68 Value profiling internals
69 ==========================
71 Every value profiling transformation starts with defining what values
72 to profile. There are different histogram types (see HIST_TYPE_* in
73 value-prof.h) and each transformation can request one or more histogram
74 types per GIMPLE statement. The function gimple_find_values_to_profile()
75 collects the values to profile in a vec, and adds the number of counters
76 required for the different histogram types.
78 For a -fprofile-generate run, the statements for which values should be
79 recorded, are instrumented in instrument_values(). The instrumentation
80 is done by helper functions that can be found in tree-profile.c, where
81 new types of histograms can be added if necessary.
83 After a -fprofile-use, the value profiling data is read back in by
84 compute_value_histograms() that translates the collected data to
85 histograms and attaches them to the profiled statements via
86 gimple_add_histogram_value(). Histograms are stored in a hash table
87 that is attached to every intrumented function, see VALUE_HISTOGRAMS
90 The value-profile transformations driver is the function
91 gimple_value_profile_transformations(). It traverses all statements in
92 the to-be-transformed function, and looks for statements with one or
93 more histograms attached to it. If a statement has histograms, the
94 transformation functions are called on the statement.
96 Limitations / FIXME / TODO:
97 * Only one histogram of each type can be associated with a statement.
98 * Currently, HIST_TYPE_CONST_DELTA is not implemented.
99 (This type of histogram was originally used to implement a form of
100 stride profiling based speculative prefetching to improve SPEC2000
101 scores for memory-bound benchmarks, mcf and equake. However, this
102 was an RTL value-profiling transformation, and those have all been
104 * Some value profile transformations are done in builtins.c (?!)
105 * Updating of histograms needs some TLC.
106 * The value profiling code could be used to record analysis results
107 from non-profiling (e.g. VRP).
108 * Adding new profilers should be simplified, starting with a cleanup
109 of what-happens-where andwith making gimple_find_values_to_profile
110 and gimple_value_profile_transformations table-driven, perhaps...
113 static tree
gimple_divmod_fixed_value (gimple
, tree
, int, gcov_type
, gcov_type
);
114 static tree
gimple_mod_pow2 (gimple
, int, gcov_type
, gcov_type
);
115 static tree
gimple_mod_subtract (gimple
, int, int, int, gcov_type
, gcov_type
,
117 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
118 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
119 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
120 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
121 static bool gimple_ic_transform (gimple_stmt_iterator
*);
123 /* Allocate histogram value. */
125 static histogram_value
126 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
127 enum hist_type type
, gimple stmt
, tree value
)
129 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
130 hist
->hvalue
.value
= value
;
131 hist
->hvalue
.stmt
= stmt
;
136 /* Hash value for histogram. */
139 histogram_hash (const void *x
)
141 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
144 /* Return nonzero if statement for histogram_value X is Y. */
147 histogram_eq (const void *x
, const void *y
)
149 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
152 /* Set histogram for STMT. */
155 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
158 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
160 if (!VALUE_HISTOGRAMS (fun
))
161 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
163 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
164 htab_hash_pointer (stmt
),
165 hist
? INSERT
: NO_INSERT
);
169 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
175 /* Get histogram list for STMT. */
178 gimple_histogram_value (struct function
*fun
, gimple stmt
)
180 if (!VALUE_HISTOGRAMS (fun
))
182 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
183 htab_hash_pointer (stmt
));
186 /* Add histogram for STMT. */
189 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
190 histogram_value hist
)
192 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
193 set_histogram_value (fun
, stmt
, hist
);
197 /* Remove histogram HIST from STMT's histogram list. */
200 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
201 histogram_value hist
)
203 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
206 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
210 while (hist2
->hvalue
.next
!= hist
)
211 hist2
= hist2
->hvalue
.next
;
212 hist2
->hvalue
.next
= hist
->hvalue
.next
;
214 free (hist
->hvalue
.counters
);
215 #ifdef ENABLE_CHECKING
216 memset (hist
, 0xab, sizeof (*hist
));
222 /* Lookup histogram of type TYPE in the STMT. */
225 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
228 histogram_value hist
;
229 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
230 hist
= hist
->hvalue
.next
)
231 if (hist
->type
== type
)
236 /* Dump information about HIST to DUMP_FILE. */
239 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
243 case HIST_TYPE_INTERVAL
:
244 fprintf (dump_file
, "Interval counter range %d -- %d",
245 hist
->hdata
.intvl
.int_start
,
246 (hist
->hdata
.intvl
.int_start
247 + hist
->hdata
.intvl
.steps
- 1));
248 if (hist
->hvalue
.counters
)
251 fprintf (dump_file
, " [");
252 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
253 fprintf (dump_file
, " %d:"HOST_WIDEST_INT_PRINT_DEC
,
254 hist
->hdata
.intvl
.int_start
+ i
,
255 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
256 fprintf (dump_file
, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC
,
257 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
259 fprintf (dump_file
, ".\n");
263 fprintf (dump_file
, "Pow2 counter ");
264 if (hist
->hvalue
.counters
)
266 fprintf (dump_file
, "pow2:"HOST_WIDEST_INT_PRINT_DEC
267 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC
,
268 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
269 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
271 fprintf (dump_file
, ".\n");
274 case HIST_TYPE_SINGLE_VALUE
:
275 fprintf (dump_file
, "Single value ");
276 if (hist
->hvalue
.counters
)
278 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
279 " match:"HOST_WIDEST_INT_PRINT_DEC
280 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
281 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
282 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
283 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
285 fprintf (dump_file
, ".\n");
288 case HIST_TYPE_AVERAGE
:
289 fprintf (dump_file
, "Average value ");
290 if (hist
->hvalue
.counters
)
292 fprintf (dump_file
, "sum:"HOST_WIDEST_INT_PRINT_DEC
293 " times:"HOST_WIDEST_INT_PRINT_DEC
,
294 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
295 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
297 fprintf (dump_file
, ".\n");
301 fprintf (dump_file
, "IOR value ");
302 if (hist
->hvalue
.counters
)
304 fprintf (dump_file
, "ior:"HOST_WIDEST_INT_PRINT_DEC
,
305 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0]);
307 fprintf (dump_file
, ".\n");
310 case HIST_TYPE_CONST_DELTA
:
311 fprintf (dump_file
, "Constant delta ");
312 if (hist
->hvalue
.counters
)
314 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
315 " match:"HOST_WIDEST_INT_PRINT_DEC
316 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
317 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
318 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
319 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
321 fprintf (dump_file
, ".\n");
323 case HIST_TYPE_INDIR_CALL
:
324 fprintf (dump_file
, "Indirect call ");
325 if (hist
->hvalue
.counters
)
327 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
328 " match:"HOST_WIDEST_INT_PRINT_DEC
329 " all:"HOST_WIDEST_INT_PRINT_DEC
,
330 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
331 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
332 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
334 fprintf (dump_file
, ".\n");
341 /* Dump information about HIST to DUMP_FILE. */
344 stream_out_histogram_value (struct output_block
*ob
, histogram_value hist
)
349 bp
= bitpack_create (ob
->main_stream
);
350 bp_pack_enum (&bp
, hist_type
, HIST_TYPE_MAX
, hist
->type
);
351 bp_pack_value (&bp
, hist
->hvalue
.next
!= NULL
, 1);
352 streamer_write_bitpack (&bp
);
355 case HIST_TYPE_INTERVAL
:
356 streamer_write_hwi (ob
, hist
->hdata
.intvl
.int_start
);
357 streamer_write_uhwi (ob
, hist
->hdata
.intvl
.steps
);
362 for (i
= 0; i
< hist
->n_counters
; i
++)
363 streamer_write_gcov_count (ob
, hist
->hvalue
.counters
[i
]);
364 if (hist
->hvalue
.next
)
365 stream_out_histogram_value (ob
, hist
->hvalue
.next
);
367 /* Dump information about HIST to DUMP_FILE. */
370 stream_in_histogram_value (struct lto_input_block
*ib
, gimple stmt
)
373 unsigned int ncounters
= 0;
376 histogram_value new_val
;
378 histogram_value
*next_p
= NULL
;
382 bp
= streamer_read_bitpack (ib
);
383 type
= bp_unpack_enum (&bp
, hist_type
, HIST_TYPE_MAX
);
384 next
= bp_unpack_value (&bp
, 1);
385 new_val
= gimple_alloc_histogram_value (cfun
, type
, stmt
, NULL
);
388 case HIST_TYPE_INTERVAL
:
389 new_val
->hdata
.intvl
.int_start
= streamer_read_hwi (ib
);
390 new_val
->hdata
.intvl
.steps
= streamer_read_uhwi (ib
);
391 ncounters
= new_val
->hdata
.intvl
.steps
+ 2;
395 case HIST_TYPE_AVERAGE
:
399 case HIST_TYPE_SINGLE_VALUE
:
400 case HIST_TYPE_INDIR_CALL
:
404 case HIST_TYPE_CONST_DELTA
:
414 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * ncounters
);
415 new_val
->n_counters
= ncounters
;
416 for (i
= 0; i
< ncounters
; i
++)
417 new_val
->hvalue
.counters
[i
] = streamer_read_gcov_count (ib
);
419 gimple_add_histogram_value (cfun
, stmt
, new_val
);
422 next_p
= &new_val
->hvalue
.next
;
427 /* Dump all histograms attached to STMT to DUMP_FILE. */
430 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
432 histogram_value hist
;
433 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
434 dump_histogram_value (dump_file
, hist
);
437 /* Remove all histograms associated with STMT. */
440 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
443 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
444 gimple_remove_histogram_value (fun
, stmt
, val
);
447 /* Duplicate all histograms associates with OSTMT to STMT. */
450 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
451 struct function
*ofun
, gimple ostmt
)
454 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
456 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
457 memcpy (new_val
, val
, sizeof (*val
));
458 new_val
->hvalue
.stmt
= stmt
;
459 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
460 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
461 gimple_add_histogram_value (fun
, stmt
, new_val
);
466 /* Move all histograms associated with OSTMT to STMT. */
469 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
471 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
474 /* The following three statements can't be reordered,
475 because histogram hashtab relies on stmt field value
476 for finding the exact slot. */
477 set_histogram_value (fun
, ostmt
, NULL
);
478 for (; val
!= NULL
; val
= val
->hvalue
.next
)
479 val
->hvalue
.stmt
= stmt
;
480 set_histogram_value (fun
, stmt
, val
);
484 static bool error_found
= false;
486 /* Helper function for verify_histograms. For each histogram reachable via htab
487 walk verify that it was reached via statement walk. */
490 visit_hist (void **slot
, void *data
)
492 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
493 histogram_value hist
= *(histogram_value
*) slot
;
494 if (!pointer_set_contains (visited
, hist
))
496 error ("dead histogram");
497 dump_histogram_value (stderr
, hist
);
498 debug_gimple_stmt (hist
->hvalue
.stmt
);
505 /* Verify sanity of the histograms. */
508 verify_histograms (void)
511 gimple_stmt_iterator gsi
;
512 histogram_value hist
;
513 struct pointer_set_t
*visited_hists
;
516 visited_hists
= pointer_set_create ();
518 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
520 gimple stmt
= gsi_stmt (gsi
);
522 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
523 hist
= hist
->hvalue
.next
)
525 if (hist
->hvalue
.stmt
!= stmt
)
527 error ("Histogram value statement does not correspond to "
528 "the statement it is associated with");
529 debug_gimple_stmt (stmt
);
530 dump_histogram_value (stderr
, hist
);
533 pointer_set_insert (visited_hists
, hist
);
536 if (VALUE_HISTOGRAMS (cfun
))
537 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, visited_hists
);
538 pointer_set_destroy (visited_hists
);
540 internal_error ("verify_histograms failed");
543 /* Helper function for verify_histograms. For each histogram reachable via htab
544 walk verify that it was reached via statement walk. */
547 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
549 histogram_value hist
= *(histogram_value
*) slot
;
550 free (hist
->hvalue
.counters
);
551 #ifdef ENABLE_CHECKING
552 memset (hist
, 0xab, sizeof (*hist
));
559 free_histograms (void)
561 if (VALUE_HISTOGRAMS (cfun
))
563 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
564 htab_delete (VALUE_HISTOGRAMS (cfun
));
565 VALUE_HISTOGRAMS (cfun
) = NULL
;
570 /* The overall number of invocations of the counter should match
571 execution count of basic block. Report it as error rather than
572 internal error as it might mean that user has misused the profile
576 check_counter (gimple stmt
, const char * name
,
577 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
579 if (*all
!= bb_count
|| *count
> *all
)
582 locus
= (stmt
!= NULL
)
583 ? gimple_location (stmt
)
584 : DECL_SOURCE_LOCATION (current_function_decl
);
585 if (flag_profile_correction
)
587 if (dump_enabled_p ())
588 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
589 "correcting inconsistent value profile: %s "
590 "profiler overall count (%d) does not match BB "
591 "count (%d)\n", name
, (int)*all
, (int)bb_count
);
599 error_at (locus
, "corrupted value profile: %s "
600 "profile counter (%d out of %d) inconsistent with "
601 "basic-block count (%d)",
614 /* GIMPLE based transformations. */
617 gimple_value_profile_transformations (void)
620 gimple_stmt_iterator gsi
;
621 bool changed
= false;
625 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
627 gimple stmt
= gsi_stmt (gsi
);
628 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
634 fprintf (dump_file
, "Trying transformations on stmt ");
635 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
636 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
639 /* Transformations: */
640 /* The order of things in this conditional controls which
641 transformation is used when more than one is applicable. */
642 /* It is expected that any code added by the transformations
643 will be added before the current statement, and that the
644 current statement remain valid (although possibly
645 modified) upon return. */
646 if (gimple_mod_subtract_transform (&gsi
)
647 || gimple_divmod_fixed_value_transform (&gsi
)
648 || gimple_mod_pow2_value_transform (&gsi
)
649 || gimple_stringops_transform (&gsi
)
650 || gimple_ic_transform (&gsi
))
652 stmt
= gsi_stmt (gsi
);
654 /* Original statement may no longer be in the same block. */
655 if (bb
!= gimple_bb (stmt
))
657 bb
= gimple_bb (stmt
);
658 gsi
= gsi_for_stmt (stmt
);
673 /* Generate code for transformation 1 (with parent gimple assignment
674 STMT and probability of taking the optimal path PROB, which is
675 equivalent to COUNT/ALL within roundoff error). This generates the
676 result into a temp and returns the temp; it does not replace or
677 alter the original STMT. */
680 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
683 gimple stmt1
, stmt2
, stmt3
;
684 tree tmp0
, tmp1
, tmp2
;
685 gimple bb1end
, bb2end
, bb3end
;
686 basic_block bb
, bb2
, bb3
, bb4
;
687 tree optype
, op1
, op2
;
688 edge e12
, e13
, e23
, e24
, e34
;
689 gimple_stmt_iterator gsi
;
691 gcc_assert (is_gimple_assign (stmt
)
692 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
693 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
695 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
696 op1
= gimple_assign_rhs1 (stmt
);
697 op2
= gimple_assign_rhs2 (stmt
);
699 bb
= gimple_bb (stmt
);
700 gsi
= gsi_for_stmt (stmt
);
702 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
703 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
704 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
705 stmt2
= gimple_build_assign (tmp1
, op2
);
706 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
707 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
708 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
709 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
712 tmp2
= create_tmp_reg (optype
, "PROF");
713 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
715 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
718 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
720 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
724 /* Edge e23 connects bb2 to bb3, etc. */
725 e12
= split_block (bb
, bb1end
);
728 e23
= split_block (bb2
, bb2end
);
730 bb3
->count
= all
- count
;
731 e34
= split_block (bb3
, bb3end
);
735 e12
->flags
&= ~EDGE_FALLTHRU
;
736 e12
->flags
|= EDGE_FALSE_VALUE
;
737 e12
->probability
= prob
;
740 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
741 e13
->probability
= REG_BR_PROB_BASE
- prob
;
742 e13
->count
= all
- count
;
746 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
747 e24
->probability
= REG_BR_PROB_BASE
;
750 e34
->probability
= REG_BR_PROB_BASE
;
751 e34
->count
= all
- count
;
757 /* Do transform 1) on INSN if applicable. */
760 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
762 histogram_value histogram
;
764 gcov_type val
, count
, all
;
765 tree result
, value
, tree_val
;
769 stmt
= gsi_stmt (*si
);
770 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
773 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
776 code
= gimple_assign_rhs_code (stmt
);
778 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
781 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
782 HIST_TYPE_SINGLE_VALUE
);
786 value
= histogram
->hvalue
.value
;
787 val
= histogram
->hvalue
.counters
[0];
788 count
= histogram
->hvalue
.counters
[1];
789 all
= histogram
->hvalue
.counters
[2];
790 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
792 /* We require that count is at least half of all; this means
793 that for the transformation to fire the value must be constant
794 at least 50% of time (and 75% gives the guarantee of usage). */
795 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
797 || optimize_bb_for_size_p (gimple_bb (stmt
)))
800 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
803 /* Compute probability of taking the optimal path. */
805 prob
= GCOV_COMPUTE_SCALE (count
, all
);
809 tree_val
= build_int_cst_wide (get_gcov_type (),
810 (unsigned HOST_WIDE_INT
) val
,
811 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
812 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
816 fprintf (dump_file
, "Div/mod by constant ");
817 print_generic_expr (dump_file
, value
, TDF_SLIM
);
818 fprintf (dump_file
, "=");
819 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
820 fprintf (dump_file
, " transformation on insn ");
821 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
824 gimple_assign_set_rhs_from_tree (si
, result
);
825 update_stmt (gsi_stmt (*si
));
830 /* Generate code for transformation 2 (with parent gimple assign STMT and
831 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
832 within roundoff error). This generates the result into a temp and returns
833 the temp; it does not replace or alter the original STMT. */
835 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
837 gimple stmt1
, stmt2
, stmt3
, stmt4
;
839 gimple bb1end
, bb2end
, bb3end
;
840 basic_block bb
, bb2
, bb3
, bb4
;
841 tree optype
, op1
, op2
;
842 edge e12
, e13
, e23
, e24
, e34
;
843 gimple_stmt_iterator gsi
;
846 gcc_assert (is_gimple_assign (stmt
)
847 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
849 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
850 op1
= gimple_assign_rhs1 (stmt
);
851 op2
= gimple_assign_rhs2 (stmt
);
853 bb
= gimple_bb (stmt
);
854 gsi
= gsi_for_stmt (stmt
);
856 result
= create_tmp_reg (optype
, "PROF");
857 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
858 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
859 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
860 build_int_cst (optype
, -1));
861 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
862 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
863 NULL_TREE
, NULL_TREE
);
864 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
865 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
866 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
869 /* tmp2 == op2-1 inherited from previous block. */
870 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
871 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
874 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
876 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
880 /* Edge e23 connects bb2 to bb3, etc. */
881 e12
= split_block (bb
, bb1end
);
884 e23
= split_block (bb2
, bb2end
);
886 bb3
->count
= all
- count
;
887 e34
= split_block (bb3
, bb3end
);
891 e12
->flags
&= ~EDGE_FALLTHRU
;
892 e12
->flags
|= EDGE_FALSE_VALUE
;
893 e12
->probability
= prob
;
896 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
897 e13
->probability
= REG_BR_PROB_BASE
- prob
;
898 e13
->count
= all
- count
;
902 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
903 e24
->probability
= REG_BR_PROB_BASE
;
906 e34
->probability
= REG_BR_PROB_BASE
;
907 e34
->count
= all
- count
;
912 /* Do transform 2) on INSN if applicable. */
914 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
916 histogram_value histogram
;
918 gcov_type count
, wrong_values
, all
;
919 tree lhs_type
, result
, value
;
923 stmt
= gsi_stmt (*si
);
924 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
927 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
928 if (!INTEGRAL_TYPE_P (lhs_type
))
931 code
= gimple_assign_rhs_code (stmt
);
933 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
936 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
940 value
= histogram
->hvalue
.value
;
941 wrong_values
= histogram
->hvalue
.counters
[0];
942 count
= histogram
->hvalue
.counters
[1];
944 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
946 /* We require that we hit a power of 2 at least half of all evaluations. */
947 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
948 || count
< wrong_values
949 || optimize_bb_for_size_p (gimple_bb (stmt
)))
954 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
955 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
958 /* Compute probability of taking the optimal path. */
959 all
= count
+ wrong_values
;
961 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
965 prob
= GCOV_COMPUTE_SCALE (count
, all
);
969 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
971 gimple_assign_set_rhs_from_tree (si
, result
);
972 update_stmt (gsi_stmt (*si
));
977 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
978 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
979 supported and this is built into this interface. The probabilities of taking
980 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
981 COUNT2/ALL respectively within roundoff error). This generates the
982 result into a temp and returns the temp; it does not replace or alter
983 the original STMT. */
984 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
987 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
988 gcov_type count1
, gcov_type count2
, gcov_type all
)
990 gimple stmt1
, stmt2
, stmt3
;
992 gimple bb1end
, bb2end
= NULL
, bb3end
;
993 basic_block bb
, bb2
, bb3
, bb4
;
994 tree optype
, op1
, op2
;
995 edge e12
, e23
= 0, e24
, e34
, e14
;
996 gimple_stmt_iterator gsi
;
999 gcc_assert (is_gimple_assign (stmt
)
1000 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
1002 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
1003 op1
= gimple_assign_rhs1 (stmt
);
1004 op2
= gimple_assign_rhs2 (stmt
);
1006 bb
= gimple_bb (stmt
);
1007 gsi
= gsi_for_stmt (stmt
);
1009 result
= create_tmp_reg (optype
, "PROF");
1010 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1011 stmt1
= gimple_build_assign (result
, op1
);
1012 stmt2
= gimple_build_assign (tmp1
, op2
);
1013 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1014 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1015 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1016 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
1019 if (ncounts
) /* Assumed to be 0 or 1 */
1021 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
1022 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
1023 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1024 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
1028 /* Fallback case. */
1029 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
1031 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
1035 /* Edge e23 connects bb2 to bb3, etc. */
1036 /* However block 3 is optional; if it is not there, references
1037 to 3 really refer to block 2. */
1038 e12
= split_block (bb
, bb1end
);
1040 bb2
->count
= all
- count1
;
1042 if (ncounts
) /* Assumed to be 0 or 1. */
1044 e23
= split_block (bb2
, bb2end
);
1046 bb3
->count
= all
- count1
- count2
;
1049 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
1053 e12
->flags
&= ~EDGE_FALLTHRU
;
1054 e12
->flags
|= EDGE_FALSE_VALUE
;
1055 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
1056 e12
->count
= all
- count1
;
1058 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
1059 e14
->probability
= prob1
;
1060 e14
->count
= count1
;
1062 if (ncounts
) /* Assumed to be 0 or 1. */
1064 e23
->flags
&= ~EDGE_FALLTHRU
;
1065 e23
->flags
|= EDGE_FALSE_VALUE
;
1066 e23
->count
= all
- count1
- count2
;
1067 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
1069 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
1070 e24
->probability
= prob2
;
1071 e24
->count
= count2
;
1074 e34
->probability
= REG_BR_PROB_BASE
;
1075 e34
->count
= all
- count1
- count2
;
1081 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1084 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1086 histogram_value histogram
;
1087 enum tree_code code
;
1088 gcov_type count
, wrong_values
, all
;
1089 tree lhs_type
, result
;
1090 gcov_type prob1
, prob2
;
1091 unsigned int i
, steps
;
1092 gcov_type count1
, count2
;
1095 stmt
= gsi_stmt (*si
);
1096 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1099 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1100 if (!INTEGRAL_TYPE_P (lhs_type
))
1103 code
= gimple_assign_rhs_code (stmt
);
1105 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1108 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1114 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1115 all
+= histogram
->hvalue
.counters
[i
];
1117 wrong_values
+= histogram
->hvalue
.counters
[i
];
1118 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1119 steps
= histogram
->hdata
.intvl
.steps
;
1120 all
+= wrong_values
;
1121 count1
= histogram
->hvalue
.counters
[0];
1122 count2
= histogram
->hvalue
.counters
[1];
1124 /* Compute probability of taking the optimal path. */
1125 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1127 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1131 if (flag_profile_correction
&& count1
+ count2
> all
)
1132 all
= count1
+ count2
;
1134 gcc_assert (count1
+ count2
<= all
);
1136 /* We require that we use just subtractions in at least 50% of all
1139 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1141 count
+= histogram
->hvalue
.counters
[i
];
1142 if (count
* 2 >= all
)
1146 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1149 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1152 fprintf (dump_file
, "Mod subtract transformation on insn ");
1153 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1156 /* Compute probability of taking the optimal path(s). */
1159 prob1
= GCOV_COMPUTE_SCALE (count1
, all
);
1160 prob2
= GCOV_COMPUTE_SCALE (count2
, all
);
1167 /* In practice, "steps" is always 2. This interface reflects this,
1168 and will need to be changed if "steps" can change. */
1169 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1171 gimple_assign_set_rhs_from_tree (si
, result
);
1172 update_stmt (gsi_stmt (*si
));
1177 static pointer_map_t
*cgraph_node_map
;
1179 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1180 When LOCAL is true, the PROFILE_IDs are computed. when it is false we assume
1181 that the PROFILE_IDs was already assigned. */
1184 init_node_map (bool local
)
1186 struct cgraph_node
*n
;
1187 cgraph_node_map
= pointer_map_create ();
1189 FOR_EACH_DEFINED_FUNCTION (n
)
1190 if (cgraph_function_with_gimple_body_p (n
)
1191 && !cgraph_only_called_directly_p (n
))
1196 n
->profile_id
= coverage_compute_profile_id (n
);
1197 while ((val
= pointer_map_contains (cgraph_node_map
,
1198 (void *)(size_t)n
->profile_id
))
1202 fprintf (dump_file
, "Local profile-id %i conflict"
1203 " with nodes %s/%i %s/%i\n",
1205 cgraph_node_name (n
),
1207 symtab_node_name (*(symtab_node
*)val
),
1208 (*(symtab_node
*)val
)->symbol
.order
);
1209 n
->profile_id
= (n
->profile_id
+ 1) & 0x7fffffff;
1212 else if (!n
->profile_id
)
1216 "Node %s/%i has no profile-id"
1217 " (profile feedback missing?)\n",
1218 cgraph_node_name (n
),
1222 else if ((val
= pointer_map_contains (cgraph_node_map
,
1223 (void *)(size_t)n
->profile_id
)))
1227 "Node %s/%i has IP profile-id %i conflict. "
1229 cgraph_node_name (n
),
1235 *pointer_map_insert (cgraph_node_map
,
1236 (void *)(size_t)n
->profile_id
) = (void *)n
;
1240 /* Delete the CGRAPH_NODE_MAP. */
1245 pointer_map_destroy (cgraph_node_map
);
1248 /* Return cgraph node for function with pid */
1251 find_func_by_profile_id (int profile_id
)
1253 void **val
= pointer_map_contains (cgraph_node_map
,
1254 (void *)(size_t)profile_id
);
1256 return (struct cgraph_node
*)*val
;
1261 /* Perform sanity check on the indirect call target. Due to race conditions,
1262 false function target may be attributed to an indirect call site. If the
1263 call expression type mismatches with the target function's type, expand_call
1264 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1265 Returns true if TARGET is considered ok for call CALL_STMT. */
1268 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1271 if (gimple_check_call_matching_types (call_stmt
, target
->symbol
.decl
, true))
1274 locus
= gimple_location (call_stmt
);
1275 if (dump_enabled_p ())
1276 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, locus
,
1277 "Skipping target %s with mismatching types for icall\n",
1278 cgraph_node_name (target
));
1282 /* Do transformation
1284 if (actual_callee_address == address_of_most_common_function/method)
1291 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1292 int prob
, gcov_type count
, gcov_type all
)
1294 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1295 tree tmp0
, tmp1
, tmp
;
1296 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1297 tree optype
= build_pointer_type (void_type_node
);
1298 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1299 gimple_stmt_iterator gsi
;
1303 gimple_stmt_iterator psi
;
1305 cond_bb
= gimple_bb (icall_stmt
);
1306 gsi
= gsi_for_stmt (icall_stmt
);
1308 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1309 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1310 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1311 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1312 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1314 tmp
= fold_convert (optype
, build_addr (direct_call
->symbol
.decl
,
1315 current_function_decl
));
1316 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1317 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1319 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1320 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1322 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1323 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1324 update_stmt (icall_stmt
);
1325 dcall_stmt
= gimple_copy (icall_stmt
);
1326 gimple_call_set_fndecl (dcall_stmt
, direct_call
->symbol
.decl
);
1327 dflags
= flags_from_decl_or_type (direct_call
->symbol
.decl
);
1328 if ((dflags
& ECF_NORETURN
) != 0)
1329 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1330 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1333 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1334 e_cd
= split_block (cond_bb
, cond_stmt
);
1335 dcall_bb
= e_cd
->dest
;
1336 dcall_bb
->count
= count
;
1338 e_di
= split_block (dcall_bb
, dcall_stmt
);
1339 icall_bb
= e_di
->dest
;
1340 icall_bb
->count
= all
- count
;
1342 /* Do not disturb existing EH edges from the indirect call. */
1343 if (!stmt_ends_bb_p (icall_stmt
))
1344 e_ij
= split_block (icall_bb
, icall_stmt
);
1347 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1348 /* The indirect call might be noreturn. */
1351 e_ij
->probability
= REG_BR_PROB_BASE
;
1352 e_ij
->count
= all
- count
;
1353 e_ij
= single_pred_edge (split_edge (e_ij
));
1358 join_bb
= e_ij
->dest
;
1359 join_bb
->count
= all
;
1362 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1363 e_cd
->probability
= prob
;
1364 e_cd
->count
= count
;
1366 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1367 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1368 e_ci
->count
= all
- count
;
1374 if ((dflags
& ECF_NORETURN
) != 0)
1378 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1379 e_dj
->probability
= REG_BR_PROB_BASE
;
1380 e_dj
->count
= count
;
1382 e_ij
->count
= all
- count
;
1384 e_ij
->probability
= REG_BR_PROB_BASE
;
1387 /* Insert PHI node for the call result if necessary. */
1388 if (gimple_call_lhs (icall_stmt
)
1389 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1390 && (dflags
& ECF_NORETURN
) == 0)
1392 tree result
= gimple_call_lhs (icall_stmt
);
1393 gimple phi
= create_phi_node (result
, join_bb
);
1394 gimple_call_set_lhs (icall_stmt
,
1395 duplicate_ssa_name (result
, icall_stmt
));
1396 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1397 gimple_call_set_lhs (dcall_stmt
,
1398 duplicate_ssa_name (result
, dcall_stmt
));
1399 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1402 /* Build an EH edge for the direct call if necessary. */
1403 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1404 if (lp_nr
> 0 && stmt_could_throw_p (dcall_stmt
))
1406 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1409 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1410 if (e_eh
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
1412 e
= make_edge (dcall_bb
, e_eh
->dest
, e_eh
->flags
);
1413 for (psi
= gsi_start_phis (e_eh
->dest
);
1414 !gsi_end_p (psi
); gsi_next (&psi
))
1416 gimple phi
= gsi_stmt (psi
);
1417 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1418 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1425 For every checked indirect/virtual call determine if most common pid of
1426 function/class method has probability more than 50%. If yes modify code of
1431 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1433 gimple stmt
= gsi_stmt (*gsi
);
1434 histogram_value histogram
;
1435 gcov_type val
, count
, all
, bb_all
;
1436 struct cgraph_node
*direct_call
;
1438 if (gimple_code (stmt
) != GIMPLE_CALL
)
1441 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1444 if (gimple_call_internal_p (stmt
))
1447 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1451 val
= histogram
->hvalue
.counters
[0];
1452 count
= histogram
->hvalue
.counters
[1];
1453 all
= histogram
->hvalue
.counters
[2];
1455 bb_all
= gimple_bb (stmt
)->count
;
1456 /* The order of CHECK_COUNTER calls is important -
1457 since check_counter can correct the third parameter
1458 and we want to make count <= all <= bb_all. */
1459 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1460 || check_counter (stmt
, "ic", &count
, &all
, all
))
1462 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1466 if (4 * count
<= 3 * all
)
1469 direct_call
= find_func_by_profile_id ((int)val
);
1471 if (direct_call
== NULL
)
1477 fprintf (dump_file
, "Indirect call -> direct call from other module");
1478 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1479 fprintf (dump_file
, "=> %i (will resolve only with LTO)\n", (int)val
);
1485 if (!check_ic_target (stmt
, direct_call
))
1489 fprintf (dump_file
, "Indirect call -> direct call ");
1490 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1491 fprintf (dump_file
, "=> ");
1492 print_generic_expr (dump_file
, direct_call
->symbol
.decl
, TDF_SLIM
);
1493 fprintf (dump_file
, " transformation skipped because of type mismatch");
1494 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1496 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1502 fprintf (dump_file
, "Indirect call -> direct call ");
1503 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1504 fprintf (dump_file
, "=> ");
1505 print_generic_expr (dump_file
, direct_call
->symbol
.decl
, TDF_SLIM
);
1506 fprintf (dump_file
, " transformation on insn postponned to ipa-profile");
1507 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1508 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1509 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1515 /* Return true if the stringop CALL with FNDECL shall be profiled.
1516 SIZE_ARG be set to the argument index for the size of the string
1520 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1522 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1524 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1525 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1530 case BUILT_IN_MEMCPY
:
1531 case BUILT_IN_MEMPCPY
:
1533 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1534 INTEGER_TYPE
, VOID_TYPE
);
1535 case BUILT_IN_MEMSET
:
1537 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1538 INTEGER_TYPE
, VOID_TYPE
);
1539 case BUILT_IN_BZERO
:
1541 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1548 /* Convert stringop (..., vcall_size)
1550 if (vcall_size == icall_size)
1551 stringop (..., icall_size);
1553 stringop (..., vcall_size);
1554 assuming we'll propagate a true constant into ICALL_SIZE later. */
1557 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1558 gcov_type count
, gcov_type all
)
1560 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1561 tree tmp0
, tmp1
, vcall_size
, optype
;
1562 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1563 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1564 gimple_stmt_iterator gsi
;
1568 fndecl
= gimple_call_fndecl (vcall_stmt
);
1569 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1572 cond_bb
= gimple_bb (vcall_stmt
);
1573 gsi
= gsi_for_stmt (vcall_stmt
);
1575 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1576 optype
= TREE_TYPE (vcall_size
);
1578 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1579 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1580 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1581 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1583 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1584 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1586 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1587 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1589 gimple_set_vdef (vcall_stmt
, NULL
);
1590 gimple_set_vuse (vcall_stmt
, NULL
);
1591 update_stmt (vcall_stmt
);
1592 icall_stmt
= gimple_copy (vcall_stmt
);
1593 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1594 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1597 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1598 e_ci
= split_block (cond_bb
, cond_stmt
);
1599 icall_bb
= e_ci
->dest
;
1600 icall_bb
->count
= count
;
1602 e_iv
= split_block (icall_bb
, icall_stmt
);
1603 vcall_bb
= e_iv
->dest
;
1604 vcall_bb
->count
= all
- count
;
1606 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1607 join_bb
= e_vj
->dest
;
1608 join_bb
->count
= all
;
1610 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1611 e_ci
->probability
= prob
;
1612 e_ci
->count
= count
;
1614 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1615 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1616 e_cv
->count
= all
- count
;
1620 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1621 e_ij
->probability
= REG_BR_PROB_BASE
;
1622 e_ij
->count
= count
;
1624 e_vj
->probability
= REG_BR_PROB_BASE
;
1625 e_vj
->count
= all
- count
;
1627 /* Insert PHI node for the call result if necessary. */
1628 if (gimple_call_lhs (vcall_stmt
)
1629 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1631 tree result
= gimple_call_lhs (vcall_stmt
);
1632 gimple phi
= create_phi_node (result
, join_bb
);
1633 gimple_call_set_lhs (vcall_stmt
,
1634 duplicate_ssa_name (result
, vcall_stmt
));
1635 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1636 gimple_call_set_lhs (icall_stmt
,
1637 duplicate_ssa_name (result
, icall_stmt
));
1638 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1641 /* Because these are all string op builtins, they're all nothrow. */
1642 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1643 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1646 /* Find values inside STMT for that we want to measure histograms for
1647 division/modulo optimization. */
1649 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1651 gimple stmt
= gsi_stmt (*gsi
);
1654 enum built_in_function fcode
;
1655 histogram_value histogram
;
1656 gcov_type count
, all
, val
;
1658 unsigned int dest_align
, src_align
;
1663 if (gimple_code (stmt
) != GIMPLE_CALL
)
1665 fndecl
= gimple_call_fndecl (stmt
);
1668 fcode
= DECL_FUNCTION_CODE (fndecl
);
1669 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1672 blck_size
= gimple_call_arg (stmt
, size_arg
);
1673 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1676 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1679 val
= histogram
->hvalue
.counters
[0];
1680 count
= histogram
->hvalue
.counters
[1];
1681 all
= histogram
->hvalue
.counters
[2];
1682 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1683 /* We require that count is at least half of all; this means
1684 that for the transformation to fire the value must be constant
1685 at least 80% of time. */
1686 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1688 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1691 prob
= GCOV_COMPUTE_SCALE (count
, all
);
1694 dest
= gimple_call_arg (stmt
, 0);
1695 dest_align
= get_pointer_alignment (dest
);
1698 case BUILT_IN_MEMCPY
:
1699 case BUILT_IN_MEMPCPY
:
1700 src
= gimple_call_arg (stmt
, 1);
1701 src_align
= get_pointer_alignment (src
);
1702 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1705 case BUILT_IN_MEMSET
:
1706 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1707 gimple_call_arg (stmt
, 1),
1711 case BUILT_IN_BZERO
:
1712 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1720 tree_val
= build_int_cst_wide (get_gcov_type (),
1721 (unsigned HOST_WIDE_INT
) val
,
1722 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1725 fprintf (dump_file
, "Single value %i stringop transformation on ",
1727 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1729 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1735 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1736 HOST_WIDE_INT
*expected_size
)
1738 histogram_value histogram
;
1739 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1741 *expected_size
= -1;
1742 else if (!histogram
->hvalue
.counters
[1])
1744 *expected_size
= -1;
1745 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1750 size
= ((histogram
->hvalue
.counters
[0]
1751 + histogram
->hvalue
.counters
[1] / 2)
1752 / histogram
->hvalue
.counters
[1]);
1753 /* Even if we can hold bigger value in SIZE, INT_MAX
1754 is safe "infinity" for code generation strategies. */
1757 *expected_size
= size
;
1758 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1760 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1762 *expected_align
= 0;
1763 else if (!histogram
->hvalue
.counters
[0])
1765 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1766 *expected_align
= 0;
1773 count
= histogram
->hvalue
.counters
[0];
1775 while (!(count
& alignment
)
1776 && (alignment
* 2 * BITS_PER_UNIT
))
1778 *expected_align
= alignment
* BITS_PER_UNIT
;
1779 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1784 /* Find values inside STMT for that we want to measure histograms for
1785 division/modulo optimization. */
1787 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1789 tree lhs
, divisor
, op0
, type
;
1790 histogram_value hist
;
1792 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1795 lhs
= gimple_assign_lhs (stmt
);
1796 type
= TREE_TYPE (lhs
);
1797 if (!INTEGRAL_TYPE_P (type
))
1800 switch (gimple_assign_rhs_code (stmt
))
1802 case TRUNC_DIV_EXPR
:
1803 case TRUNC_MOD_EXPR
:
1804 divisor
= gimple_assign_rhs2 (stmt
);
1805 op0
= gimple_assign_rhs1 (stmt
);
1807 values
->reserve (3);
1809 if (TREE_CODE (divisor
) == SSA_NAME
)
1810 /* Check for the case where the divisor is the same value most
1812 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1813 HIST_TYPE_SINGLE_VALUE
,
1816 /* For mod, check whether it is not often a noop (or replaceable by
1817 a few subtractions). */
1818 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1819 && TYPE_UNSIGNED (type
))
1822 /* Check for a special case where the divisor is power of 2. */
1823 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1827 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1828 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1830 hist
->hdata
.intvl
.int_start
= 0;
1831 hist
->hdata
.intvl
.steps
= 2;
1832 values
->quick_push (hist
);
1841 /* Find calls inside STMT for that we want to measure histograms for
1842 indirect/virtual call optimization. */
1845 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1849 if (gimple_code (stmt
) != GIMPLE_CALL
1850 || gimple_call_internal_p (stmt
)
1851 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1854 callee
= gimple_call_fn (stmt
);
1856 values
->reserve (3);
1858 values
->quick_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1864 /* Find values inside STMT for that we want to measure histograms for
1865 string operations. */
1867 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1874 if (gimple_code (stmt
) != GIMPLE_CALL
)
1876 fndecl
= gimple_call_fndecl (stmt
);
1880 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1883 dest
= gimple_call_arg (stmt
, 0);
1884 blck_size
= gimple_call_arg (stmt
, size_arg
);
1886 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1888 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1889 HIST_TYPE_SINGLE_VALUE
,
1891 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1894 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1895 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1899 /* Find values inside STMT for that we want to measure histograms and adds
1900 them to list VALUES. */
1903 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1905 gimple_divmod_values_to_profile (stmt
, values
);
1906 gimple_stringops_values_to_profile (stmt
, values
);
1907 gimple_indirect_call_to_profile (stmt
, values
);
1911 gimple_find_values_to_profile (histogram_values
*values
)
1914 gimple_stmt_iterator gsi
;
1916 histogram_value hist
= NULL
;
1920 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1921 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1923 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1927 case HIST_TYPE_INTERVAL
:
1928 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1931 case HIST_TYPE_POW2
:
1932 hist
->n_counters
= 2;
1935 case HIST_TYPE_SINGLE_VALUE
:
1936 hist
->n_counters
= 3;
1939 case HIST_TYPE_CONST_DELTA
:
1940 hist
->n_counters
= 4;
1943 case HIST_TYPE_INDIR_CALL
:
1944 hist
->n_counters
= 3;
1947 case HIST_TYPE_AVERAGE
:
1948 hist
->n_counters
= 2;
1952 hist
->n_counters
= 1;
1960 fprintf (dump_file
, "Stmt ");
1961 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1962 dump_histogram_value (dump_file
, hist
);