1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "value-prof.h"
31 #include "insn-config.h"
36 #include "tree-flow.h"
37 #include "tree-flow-inline.h"
38 #include "diagnostic.h"
39 #include "gimple-pretty-print.h"
46 #include "pointer-set.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");
340 /* Dump all histograms attached to STMT to DUMP_FILE. */
343 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
345 histogram_value hist
;
346 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
347 dump_histogram_value (dump_file
, hist
);
350 /* Remove all histograms associated with STMT. */
353 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
356 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
357 gimple_remove_histogram_value (fun
, stmt
, val
);
360 /* Duplicate all histograms associates with OSTMT to STMT. */
363 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
364 struct function
*ofun
, gimple ostmt
)
367 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
369 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
370 memcpy (new_val
, val
, sizeof (*val
));
371 new_val
->hvalue
.stmt
= stmt
;
372 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
373 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
374 gimple_add_histogram_value (fun
, stmt
, new_val
);
379 /* Move all histograms associated with OSTMT to STMT. */
382 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
384 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
387 /* The following three statements can't be reordered,
388 because histogram hashtab relies on stmt field value
389 for finding the exact slot. */
390 set_histogram_value (fun
, ostmt
, NULL
);
391 for (; val
!= NULL
; val
= val
->hvalue
.next
)
392 val
->hvalue
.stmt
= stmt
;
393 set_histogram_value (fun
, stmt
, val
);
397 static bool error_found
= false;
399 /* Helper function for verify_histograms. For each histogram reachable via htab
400 walk verify that it was reached via statement walk. */
403 visit_hist (void **slot
, void *data
)
405 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
406 histogram_value hist
= *(histogram_value
*) slot
;
407 if (!pointer_set_contains (visited
, hist
))
409 error ("dead histogram");
410 dump_histogram_value (stderr
, hist
);
411 debug_gimple_stmt (hist
->hvalue
.stmt
);
418 /* Verify sanity of the histograms. */
421 verify_histograms (void)
424 gimple_stmt_iterator gsi
;
425 histogram_value hist
;
426 struct pointer_set_t
*visited_hists
;
429 visited_hists
= pointer_set_create ();
431 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
433 gimple stmt
= gsi_stmt (gsi
);
435 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
436 hist
= hist
->hvalue
.next
)
438 if (hist
->hvalue
.stmt
!= stmt
)
440 error ("Histogram value statement does not correspond to "
441 "the statement it is associated with");
442 debug_gimple_stmt (stmt
);
443 dump_histogram_value (stderr
, hist
);
446 pointer_set_insert (visited_hists
, hist
);
449 if (VALUE_HISTOGRAMS (cfun
))
450 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, visited_hists
);
451 pointer_set_destroy (visited_hists
);
453 internal_error ("verify_histograms failed");
456 /* Helper function for verify_histograms. For each histogram reachable via htab
457 walk verify that it was reached via statement walk. */
460 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
462 histogram_value hist
= *(histogram_value
*) slot
;
463 free (hist
->hvalue
.counters
);
464 #ifdef ENABLE_CHECKING
465 memset (hist
, 0xab, sizeof (*hist
));
472 free_histograms (void)
474 if (VALUE_HISTOGRAMS (cfun
))
476 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
477 htab_delete (VALUE_HISTOGRAMS (cfun
));
478 VALUE_HISTOGRAMS (cfun
) = NULL
;
483 /* The overall number of invocations of the counter should match
484 execution count of basic block. Report it as error rather than
485 internal error as it might mean that user has misused the profile
489 check_counter (gimple stmt
, const char * name
,
490 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
492 if (*all
!= bb_count
|| *count
> *all
)
495 locus
= (stmt
!= NULL
)
496 ? gimple_location (stmt
)
497 : DECL_SOURCE_LOCATION (current_function_decl
);
498 if (flag_profile_correction
)
500 inform (locus
, "correcting inconsistent value profile: "
501 "%s profiler overall count (%d) does not match BB count "
502 "(%d)", name
, (int)*all
, (int)bb_count
);
510 error_at (locus
, "corrupted value profile: %s "
511 "profile counter (%d out of %d) inconsistent with "
512 "basic-block count (%d)",
525 /* GIMPLE based transformations. */
528 gimple_value_profile_transformations (void)
531 gimple_stmt_iterator gsi
;
532 bool changed
= false;
536 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
538 gimple stmt
= gsi_stmt (gsi
);
539 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
545 fprintf (dump_file
, "Trying transformations on stmt ");
546 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
547 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
550 /* Transformations: */
551 /* The order of things in this conditional controls which
552 transformation is used when more than one is applicable. */
553 /* It is expected that any code added by the transformations
554 will be added before the current statement, and that the
555 current statement remain valid (although possibly
556 modified) upon return. */
557 if (gimple_mod_subtract_transform (&gsi
)
558 || gimple_divmod_fixed_value_transform (&gsi
)
559 || gimple_mod_pow2_value_transform (&gsi
)
560 || gimple_stringops_transform (&gsi
)
561 || gimple_ic_transform (&gsi
))
563 stmt
= gsi_stmt (gsi
);
565 /* Original statement may no longer be in the same block. */
566 if (bb
!= gimple_bb (stmt
))
568 bb
= gimple_bb (stmt
);
569 gsi
= gsi_for_stmt (stmt
);
584 /* Generate code for transformation 1 (with parent gimple assignment
585 STMT and probability of taking the optimal path PROB, which is
586 equivalent to COUNT/ALL within roundoff error). This generates the
587 result into a temp and returns the temp; it does not replace or
588 alter the original STMT. */
591 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
594 gimple stmt1
, stmt2
, stmt3
;
595 tree tmp0
, tmp1
, tmp2
;
596 gimple bb1end
, bb2end
, bb3end
;
597 basic_block bb
, bb2
, bb3
, bb4
;
598 tree optype
, op1
, op2
;
599 edge e12
, e13
, e23
, e24
, e34
;
600 gimple_stmt_iterator gsi
;
602 gcc_assert (is_gimple_assign (stmt
)
603 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
604 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
606 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
607 op1
= gimple_assign_rhs1 (stmt
);
608 op2
= gimple_assign_rhs2 (stmt
);
610 bb
= gimple_bb (stmt
);
611 gsi
= gsi_for_stmt (stmt
);
613 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
614 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
615 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
616 stmt2
= gimple_build_assign (tmp1
, op2
);
617 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
618 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
619 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
620 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
623 tmp2
= create_tmp_reg (optype
, "PROF");
624 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
626 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
629 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
631 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
635 /* Edge e23 connects bb2 to bb3, etc. */
636 e12
= split_block (bb
, bb1end
);
639 e23
= split_block (bb2
, bb2end
);
641 bb3
->count
= all
- count
;
642 e34
= split_block (bb3
, bb3end
);
646 e12
->flags
&= ~EDGE_FALLTHRU
;
647 e12
->flags
|= EDGE_FALSE_VALUE
;
648 e12
->probability
= prob
;
651 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
652 e13
->probability
= REG_BR_PROB_BASE
- prob
;
653 e13
->count
= all
- count
;
657 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
658 e24
->probability
= REG_BR_PROB_BASE
;
661 e34
->probability
= REG_BR_PROB_BASE
;
662 e34
->count
= all
- count
;
668 /* Do transform 1) on INSN if applicable. */
671 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
673 histogram_value histogram
;
675 gcov_type val
, count
, all
;
676 tree result
, value
, tree_val
;
680 stmt
= gsi_stmt (*si
);
681 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
684 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
687 code
= gimple_assign_rhs_code (stmt
);
689 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
692 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
693 HIST_TYPE_SINGLE_VALUE
);
697 value
= histogram
->hvalue
.value
;
698 val
= histogram
->hvalue
.counters
[0];
699 count
= histogram
->hvalue
.counters
[1];
700 all
= histogram
->hvalue
.counters
[2];
701 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
703 /* We require that count is at least half of all; this means
704 that for the transformation to fire the value must be constant
705 at least 50% of time (and 75% gives the guarantee of usage). */
706 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
708 || optimize_bb_for_size_p (gimple_bb (stmt
)))
711 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
714 /* Compute probability of taking the optimal path. */
716 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
720 tree_val
= build_int_cst_wide (get_gcov_type (),
721 (unsigned HOST_WIDE_INT
) val
,
722 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
723 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
727 fprintf (dump_file
, "Div/mod by constant ");
728 print_generic_expr (dump_file
, value
, TDF_SLIM
);
729 fprintf (dump_file
, "=");
730 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
731 fprintf (dump_file
, " transformation on insn ");
732 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
735 gimple_assign_set_rhs_from_tree (si
, result
);
736 update_stmt (gsi_stmt (*si
));
741 /* Generate code for transformation 2 (with parent gimple assign STMT and
742 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
743 within roundoff error). This generates the result into a temp and returns
744 the temp; it does not replace or alter the original STMT. */
746 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
748 gimple stmt1
, stmt2
, stmt3
, stmt4
;
750 gimple bb1end
, bb2end
, bb3end
;
751 basic_block bb
, bb2
, bb3
, bb4
;
752 tree optype
, op1
, op2
;
753 edge e12
, e13
, e23
, e24
, e34
;
754 gimple_stmt_iterator gsi
;
757 gcc_assert (is_gimple_assign (stmt
)
758 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
760 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
761 op1
= gimple_assign_rhs1 (stmt
);
762 op2
= gimple_assign_rhs2 (stmt
);
764 bb
= gimple_bb (stmt
);
765 gsi
= gsi_for_stmt (stmt
);
767 result
= create_tmp_reg (optype
, "PROF");
768 tmp2
= make_temp_ssa_name (optype
, NULL
, "PROF");
769 tmp3
= make_temp_ssa_name (optype
, NULL
, "PROF");
770 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
771 build_int_cst (optype
, -1));
772 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
773 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
774 NULL_TREE
, NULL_TREE
);
775 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
776 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
777 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
780 /* tmp2 == op2-1 inherited from previous block. */
781 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
782 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
785 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
787 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
791 /* Edge e23 connects bb2 to bb3, etc. */
792 e12
= split_block (bb
, bb1end
);
795 e23
= split_block (bb2
, bb2end
);
797 bb3
->count
= all
- count
;
798 e34
= split_block (bb3
, bb3end
);
802 e12
->flags
&= ~EDGE_FALLTHRU
;
803 e12
->flags
|= EDGE_FALSE_VALUE
;
804 e12
->probability
= prob
;
807 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
808 e13
->probability
= REG_BR_PROB_BASE
- prob
;
809 e13
->count
= all
- count
;
813 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
814 e24
->probability
= REG_BR_PROB_BASE
;
817 e34
->probability
= REG_BR_PROB_BASE
;
818 e34
->count
= all
- count
;
823 /* Do transform 2) on INSN if applicable. */
825 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
827 histogram_value histogram
;
829 gcov_type count
, wrong_values
, all
;
830 tree lhs_type
, result
, value
;
834 stmt
= gsi_stmt (*si
);
835 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
838 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
839 if (!INTEGRAL_TYPE_P (lhs_type
))
842 code
= gimple_assign_rhs_code (stmt
);
844 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
847 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
851 value
= histogram
->hvalue
.value
;
852 wrong_values
= histogram
->hvalue
.counters
[0];
853 count
= histogram
->hvalue
.counters
[1];
855 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
857 /* We require that we hit a power of 2 at least half of all evaluations. */
858 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
859 || count
< wrong_values
860 || optimize_bb_for_size_p (gimple_bb (stmt
)))
865 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
866 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
869 /* Compute probability of taking the optimal path. */
870 all
= count
+ wrong_values
;
872 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
876 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
880 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
882 gimple_assign_set_rhs_from_tree (si
, result
);
883 update_stmt (gsi_stmt (*si
));
888 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
889 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
890 supported and this is built into this interface. The probabilities of taking
891 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
892 COUNT2/ALL respectively within roundoff error). This generates the
893 result into a temp and returns the temp; it does not replace or alter
894 the original STMT. */
895 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
898 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
899 gcov_type count1
, gcov_type count2
, gcov_type all
)
901 gimple stmt1
, stmt2
, stmt3
;
903 gimple bb1end
, bb2end
= NULL
, bb3end
;
904 basic_block bb
, bb2
, bb3
, bb4
;
905 tree optype
, op1
, op2
;
906 edge e12
, e23
= 0, e24
, e34
, e14
;
907 gimple_stmt_iterator gsi
;
910 gcc_assert (is_gimple_assign (stmt
)
911 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
913 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
914 op1
= gimple_assign_rhs1 (stmt
);
915 op2
= gimple_assign_rhs2 (stmt
);
917 bb
= gimple_bb (stmt
);
918 gsi
= gsi_for_stmt (stmt
);
920 result
= create_tmp_reg (optype
, "PROF");
921 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
922 stmt1
= gimple_build_assign (result
, op1
);
923 stmt2
= gimple_build_assign (tmp1
, op2
);
924 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
925 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
926 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
927 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
930 if (ncounts
) /* Assumed to be 0 or 1 */
932 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
933 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
934 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
935 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
940 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
942 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
946 /* Edge e23 connects bb2 to bb3, etc. */
947 /* However block 3 is optional; if it is not there, references
948 to 3 really refer to block 2. */
949 e12
= split_block (bb
, bb1end
);
951 bb2
->count
= all
- count1
;
953 if (ncounts
) /* Assumed to be 0 or 1. */
955 e23
= split_block (bb2
, bb2end
);
957 bb3
->count
= all
- count1
- count2
;
960 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
964 e12
->flags
&= ~EDGE_FALLTHRU
;
965 e12
->flags
|= EDGE_FALSE_VALUE
;
966 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
967 e12
->count
= all
- count1
;
969 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
970 e14
->probability
= prob1
;
973 if (ncounts
) /* Assumed to be 0 or 1. */
975 e23
->flags
&= ~EDGE_FALLTHRU
;
976 e23
->flags
|= EDGE_FALSE_VALUE
;
977 e23
->count
= all
- count1
- count2
;
978 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
980 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
981 e24
->probability
= prob2
;
985 e34
->probability
= REG_BR_PROB_BASE
;
986 e34
->count
= all
- count1
- count2
;
992 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
995 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
997 histogram_value histogram
;
999 gcov_type count
, wrong_values
, all
;
1000 tree lhs_type
, result
;
1001 gcov_type prob1
, prob2
;
1002 unsigned int i
, steps
;
1003 gcov_type count1
, count2
;
1006 stmt
= gsi_stmt (*si
);
1007 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1010 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1011 if (!INTEGRAL_TYPE_P (lhs_type
))
1014 code
= gimple_assign_rhs_code (stmt
);
1016 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1019 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1025 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1026 all
+= histogram
->hvalue
.counters
[i
];
1028 wrong_values
+= histogram
->hvalue
.counters
[i
];
1029 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1030 steps
= histogram
->hdata
.intvl
.steps
;
1031 all
+= wrong_values
;
1032 count1
= histogram
->hvalue
.counters
[0];
1033 count2
= histogram
->hvalue
.counters
[1];
1035 /* Compute probability of taking the optimal path. */
1036 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1038 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1042 if (flag_profile_correction
&& count1
+ count2
> all
)
1043 all
= count1
+ count2
;
1045 gcc_assert (count1
+ count2
<= all
);
1047 /* We require that we use just subtractions in at least 50% of all
1050 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1052 count
+= histogram
->hvalue
.counters
[i
];
1053 if (count
* 2 >= all
)
1057 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1060 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1063 fprintf (dump_file
, "Mod subtract transformation on insn ");
1064 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1067 /* Compute probability of taking the optimal path(s). */
1070 prob1
= (count1
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1071 prob2
= (count2
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1078 /* In practice, "steps" is always 2. This interface reflects this,
1079 and will need to be changed if "steps" can change. */
1080 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1082 gimple_assign_set_rhs_from_tree (si
, result
);
1083 update_stmt (gsi_stmt (*si
));
1088 static vec
<cgraph_node_ptr
> cgraph_node_map
1091 /* Initialize map from FUNCDEF_NO to CGRAPH_NODE. */
1094 init_node_map (void)
1096 struct cgraph_node
*n
;
1098 if (get_last_funcdef_no ())
1099 cgraph_node_map
.safe_grow_cleared (get_last_funcdef_no ());
1101 FOR_EACH_FUNCTION (n
)
1103 if (DECL_STRUCT_FUNCTION (n
->symbol
.decl
))
1104 cgraph_node_map
[DECL_STRUCT_FUNCTION (n
->symbol
.decl
)->funcdef_no
] = n
;
1108 /* Delete the CGRAPH_NODE_MAP. */
1113 cgraph_node_map
.release ();
1116 /* Return cgraph node for function with pid */
1118 static inline struct cgraph_node
*
1119 find_func_by_funcdef_no (int func_id
)
1121 int max_id
= get_last_funcdef_no ();
1122 if (func_id
>= max_id
|| cgraph_node_map
[func_id
] == NULL
)
1124 if (flag_profile_correction
)
1125 inform (DECL_SOURCE_LOCATION (current_function_decl
),
1126 "Inconsistent profile: indirect call target (%d) does not exist", func_id
);
1128 error ("Inconsistent profile: indirect call target (%d) does not exist", func_id
);
1133 return cgraph_node_map
[func_id
];
1136 /* Perform sanity check on the indirect call target. Due to race conditions,
1137 false function target may be attributed to an indirect call site. If the
1138 call expression type mismatches with the target function's type, expand_call
1139 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1140 Returns true if TARGET is considered ok for call CALL_STMT. */
1143 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1146 if (gimple_check_call_matching_types (call_stmt
, target
->symbol
.decl
))
1149 locus
= gimple_location (call_stmt
);
1150 inform (locus
, "Skipping target %s with mismatching types for icall ",
1151 cgraph_node_name (target
));
1155 /* Do transformation
1157 if (actual_callee_address == address_of_most_common_function/method)
1164 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1165 int prob
, gcov_type count
, gcov_type all
)
1167 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1168 tree tmp0
, tmp1
, tmp
;
1169 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1170 tree optype
= build_pointer_type (void_type_node
);
1171 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1172 gimple_stmt_iterator gsi
;
1175 cond_bb
= gimple_bb (icall_stmt
);
1176 gsi
= gsi_for_stmt (icall_stmt
);
1178 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1179 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1180 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1181 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1182 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1184 tmp
= fold_convert (optype
, build_addr (direct_call
->symbol
.decl
,
1185 current_function_decl
));
1186 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1187 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1189 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1190 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1192 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1193 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1194 update_stmt (icall_stmt
);
1195 dcall_stmt
= gimple_copy (icall_stmt
);
1196 gimple_call_set_fndecl (dcall_stmt
, direct_call
->symbol
.decl
);
1197 dflags
= flags_from_decl_or_type (direct_call
->symbol
.decl
);
1198 if ((dflags
& ECF_NORETURN
) != 0)
1199 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1200 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1203 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1204 e_cd
= split_block (cond_bb
, cond_stmt
);
1205 dcall_bb
= e_cd
->dest
;
1206 dcall_bb
->count
= count
;
1208 e_di
= split_block (dcall_bb
, dcall_stmt
);
1209 icall_bb
= e_di
->dest
;
1210 icall_bb
->count
= all
- count
;
1212 /* Do not disturb existing EH edges from the indirect call. */
1213 if (!stmt_ends_bb_p (icall_stmt
))
1214 e_ij
= split_block (icall_bb
, icall_stmt
);
1217 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1218 /* The indirect call might be noreturn. */
1221 e_ij
->probability
= REG_BR_PROB_BASE
;
1222 e_ij
->count
= all
- count
;
1223 e_ij
= single_pred_edge (split_edge (e_ij
));
1228 join_bb
= e_ij
->dest
;
1229 join_bb
->count
= all
;
1232 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1233 e_cd
->probability
= prob
;
1234 e_cd
->count
= count
;
1236 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1237 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1238 e_ci
->count
= all
- count
;
1244 if ((dflags
& ECF_NORETURN
) != 0)
1248 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1249 e_dj
->probability
= REG_BR_PROB_BASE
;
1250 e_dj
->count
= count
;
1252 e_ij
->count
= all
- count
;
1254 e_ij
->probability
= REG_BR_PROB_BASE
;
1257 /* Insert PHI node for the call result if necessary. */
1258 if (gimple_call_lhs (icall_stmt
)
1259 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1260 && (dflags
& ECF_NORETURN
) == 0)
1262 tree result
= gimple_call_lhs (icall_stmt
);
1263 gimple phi
= create_phi_node (result
, join_bb
);
1264 gimple_call_set_lhs (icall_stmt
,
1265 duplicate_ssa_name (result
, icall_stmt
));
1266 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1267 gimple_call_set_lhs (dcall_stmt
,
1268 duplicate_ssa_name (result
, dcall_stmt
));
1269 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1272 /* Build an EH edge for the direct call if necessary. */
1273 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1275 && stmt_could_throw_p (dcall_stmt
))
1279 gimple_stmt_iterator psi
;
1281 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1282 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1283 if (e_eh
->flags
& EDGE_EH
)
1285 e
= make_edge (dcall_bb
, e_eh
->dest
, EDGE_EH
);
1286 for (psi
= gsi_start_phis (e_eh
->dest
);
1287 !gsi_end_p (psi
); gsi_next (&psi
))
1289 gimple phi
= gsi_stmt (psi
);
1290 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1291 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1299 For every checked indirect/virtual call determine if most common pid of
1300 function/class method has probability more than 50%. If yes modify code of
1305 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1307 gimple stmt
= gsi_stmt (*gsi
);
1308 histogram_value histogram
;
1309 gcov_type val
, count
, all
, bb_all
;
1312 struct cgraph_node
*direct_call
;
1314 if (gimple_code (stmt
) != GIMPLE_CALL
)
1317 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1320 if (gimple_call_internal_p (stmt
))
1323 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1327 val
= histogram
->hvalue
.counters
[0];
1328 count
= histogram
->hvalue
.counters
[1];
1329 all
= histogram
->hvalue
.counters
[2];
1330 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1332 if (4 * count
<= 3 * all
)
1335 bb_all
= gimple_bb (stmt
)->count
;
1336 /* The order of CHECK_COUNTER calls is important -
1337 since check_counter can correct the third parameter
1338 and we want to make count <= all <= bb_all. */
1339 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1340 || check_counter (stmt
, "ic", &count
, &all
, all
))
1344 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1347 direct_call
= find_func_by_funcdef_no ((int)val
);
1349 if (direct_call
== NULL
)
1352 if (!check_ic_target (stmt
, direct_call
))
1355 modify
= gimple_ic (stmt
, direct_call
, prob
, count
, all
);
1359 fprintf (dump_file
, "Indirect call -> direct call ");
1360 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1361 fprintf (dump_file
, "=> ");
1362 print_generic_expr (dump_file
, direct_call
->symbol
.decl
, TDF_SLIM
);
1363 fprintf (dump_file
, " transformation on insn ");
1364 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1365 fprintf (dump_file
, " to ");
1366 print_gimple_stmt (dump_file
, modify
, 0, TDF_SLIM
);
1367 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1368 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1374 /* Return true if the stringop CALL with FNDECL shall be profiled.
1375 SIZE_ARG be set to the argument index for the size of the string
1379 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1381 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1383 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1384 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1389 case BUILT_IN_MEMCPY
:
1390 case BUILT_IN_MEMPCPY
:
1392 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1393 INTEGER_TYPE
, VOID_TYPE
);
1394 case BUILT_IN_MEMSET
:
1396 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1397 INTEGER_TYPE
, VOID_TYPE
);
1398 case BUILT_IN_BZERO
:
1400 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1407 /* Convert stringop (..., vcall_size)
1409 if (vcall_size == icall_size)
1410 stringop (..., icall_size);
1412 stringop (..., vcall_size);
1413 assuming we'll propagate a true constant into ICALL_SIZE later. */
1416 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1417 gcov_type count
, gcov_type all
)
1419 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1420 tree tmp0
, tmp1
, vcall_size
, optype
;
1421 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1422 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1423 gimple_stmt_iterator gsi
;
1427 fndecl
= gimple_call_fndecl (vcall_stmt
);
1428 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1431 cond_bb
= gimple_bb (vcall_stmt
);
1432 gsi
= gsi_for_stmt (vcall_stmt
);
1434 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1435 optype
= TREE_TYPE (vcall_size
);
1437 tmp0
= make_temp_ssa_name (optype
, NULL
, "PROF");
1438 tmp1
= make_temp_ssa_name (optype
, NULL
, "PROF");
1439 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1440 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1442 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1443 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1445 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1446 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1448 gimple_set_vdef (vcall_stmt
, NULL
);
1449 gimple_set_vuse (vcall_stmt
, NULL
);
1450 update_stmt (vcall_stmt
);
1451 icall_stmt
= gimple_copy (vcall_stmt
);
1452 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1453 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1456 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1457 e_ci
= split_block (cond_bb
, cond_stmt
);
1458 icall_bb
= e_ci
->dest
;
1459 icall_bb
->count
= count
;
1461 e_iv
= split_block (icall_bb
, icall_stmt
);
1462 vcall_bb
= e_iv
->dest
;
1463 vcall_bb
->count
= all
- count
;
1465 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1466 join_bb
= e_vj
->dest
;
1467 join_bb
->count
= all
;
1469 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1470 e_ci
->probability
= prob
;
1471 e_ci
->count
= count
;
1473 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1474 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1475 e_cv
->count
= all
- count
;
1479 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1480 e_ij
->probability
= REG_BR_PROB_BASE
;
1481 e_ij
->count
= count
;
1483 e_vj
->probability
= REG_BR_PROB_BASE
;
1484 e_vj
->count
= all
- count
;
1486 /* Insert PHI node for the call result if necessary. */
1487 if (gimple_call_lhs (vcall_stmt
)
1488 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1490 tree result
= gimple_call_lhs (vcall_stmt
);
1491 gimple phi
= create_phi_node (result
, join_bb
);
1492 gimple_call_set_lhs (vcall_stmt
,
1493 duplicate_ssa_name (result
, vcall_stmt
));
1494 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1495 gimple_call_set_lhs (icall_stmt
,
1496 duplicate_ssa_name (result
, icall_stmt
));
1497 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1500 /* Because these are all string op builtins, they're all nothrow. */
1501 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1502 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1505 /* Find values inside STMT for that we want to measure histograms for
1506 division/modulo optimization. */
1508 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1510 gimple stmt
= gsi_stmt (*gsi
);
1513 enum built_in_function fcode
;
1514 histogram_value histogram
;
1515 gcov_type count
, all
, val
;
1517 unsigned int dest_align
, src_align
;
1522 if (gimple_code (stmt
) != GIMPLE_CALL
)
1524 fndecl
= gimple_call_fndecl (stmt
);
1527 fcode
= DECL_FUNCTION_CODE (fndecl
);
1528 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1531 blck_size
= gimple_call_arg (stmt
, size_arg
);
1532 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1535 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1538 val
= histogram
->hvalue
.counters
[0];
1539 count
= histogram
->hvalue
.counters
[1];
1540 all
= histogram
->hvalue
.counters
[2];
1541 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1542 /* We require that count is at least half of all; this means
1543 that for the transformation to fire the value must be constant
1544 at least 80% of time. */
1545 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1547 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1550 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1553 dest
= gimple_call_arg (stmt
, 0);
1554 dest_align
= get_pointer_alignment (dest
);
1557 case BUILT_IN_MEMCPY
:
1558 case BUILT_IN_MEMPCPY
:
1559 src
= gimple_call_arg (stmt
, 1);
1560 src_align
= get_pointer_alignment (src
);
1561 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1564 case BUILT_IN_MEMSET
:
1565 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1566 gimple_call_arg (stmt
, 1),
1570 case BUILT_IN_BZERO
:
1571 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1579 tree_val
= build_int_cst_wide (get_gcov_type (),
1580 (unsigned HOST_WIDE_INT
) val
,
1581 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1584 fprintf (dump_file
, "Single value %i stringop transformation on ",
1586 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1588 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1594 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1595 HOST_WIDE_INT
*expected_size
)
1597 histogram_value histogram
;
1598 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1600 *expected_size
= -1;
1601 else if (!histogram
->hvalue
.counters
[1])
1603 *expected_size
= -1;
1604 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1609 size
= ((histogram
->hvalue
.counters
[0]
1610 + histogram
->hvalue
.counters
[1] / 2)
1611 / histogram
->hvalue
.counters
[1]);
1612 /* Even if we can hold bigger value in SIZE, INT_MAX
1613 is safe "infinity" for code generation strategies. */
1616 *expected_size
= size
;
1617 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1619 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1621 *expected_align
= 0;
1622 else if (!histogram
->hvalue
.counters
[0])
1624 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1625 *expected_align
= 0;
1632 count
= histogram
->hvalue
.counters
[0];
1634 while (!(count
& alignment
)
1635 && (alignment
* 2 * BITS_PER_UNIT
))
1637 *expected_align
= alignment
* BITS_PER_UNIT
;
1638 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1643 /* Find values inside STMT for that we want to measure histograms for
1644 division/modulo optimization. */
1646 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1648 tree lhs
, divisor
, op0
, type
;
1649 histogram_value hist
;
1651 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1654 lhs
= gimple_assign_lhs (stmt
);
1655 type
= TREE_TYPE (lhs
);
1656 if (!INTEGRAL_TYPE_P (type
))
1659 switch (gimple_assign_rhs_code (stmt
))
1661 case TRUNC_DIV_EXPR
:
1662 case TRUNC_MOD_EXPR
:
1663 divisor
= gimple_assign_rhs2 (stmt
);
1664 op0
= gimple_assign_rhs1 (stmt
);
1666 values
->reserve (3);
1668 if (TREE_CODE (divisor
) == SSA_NAME
)
1669 /* Check for the case where the divisor is the same value most
1671 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1672 HIST_TYPE_SINGLE_VALUE
,
1675 /* For mod, check whether it is not often a noop (or replaceable by
1676 a few subtractions). */
1677 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1678 && TYPE_UNSIGNED (type
))
1681 /* Check for a special case where the divisor is power of 2. */
1682 values
->quick_push (gimple_alloc_histogram_value (cfun
,
1686 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1687 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1689 hist
->hdata
.intvl
.int_start
= 0;
1690 hist
->hdata
.intvl
.steps
= 2;
1691 values
->quick_push (hist
);
1700 /* Find calls inside STMT for that we want to measure histograms for
1701 indirect/virtual call optimization. */
1704 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1708 if (gimple_code (stmt
) != GIMPLE_CALL
1709 || gimple_call_internal_p (stmt
)
1710 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1713 callee
= gimple_call_fn (stmt
);
1715 values
->reserve (3);
1717 values
->quick_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1723 /* Find values inside STMT for that we want to measure histograms for
1724 string operations. */
1726 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1733 if (gimple_code (stmt
) != GIMPLE_CALL
)
1735 fndecl
= gimple_call_fndecl (stmt
);
1739 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1742 dest
= gimple_call_arg (stmt
, 0);
1743 blck_size
= gimple_call_arg (stmt
, size_arg
);
1745 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1747 values
->safe_push (gimple_alloc_histogram_value (cfun
,
1748 HIST_TYPE_SINGLE_VALUE
,
1750 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1753 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1754 values
->safe_push (gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1758 /* Find values inside STMT for that we want to measure histograms and adds
1759 them to list VALUES. */
1762 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1764 gimple_divmod_values_to_profile (stmt
, values
);
1765 gimple_stringops_values_to_profile (stmt
, values
);
1766 gimple_indirect_call_to_profile (stmt
, values
);
1770 gimple_find_values_to_profile (histogram_values
*values
)
1773 gimple_stmt_iterator gsi
;
1775 histogram_value hist
= NULL
;
1779 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1780 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1782 FOR_EACH_VEC_ELT (*values
, i
, hist
)
1786 case HIST_TYPE_INTERVAL
:
1787 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1790 case HIST_TYPE_POW2
:
1791 hist
->n_counters
= 2;
1794 case HIST_TYPE_SINGLE_VALUE
:
1795 hist
->n_counters
= 3;
1798 case HIST_TYPE_CONST_DELTA
:
1799 hist
->n_counters
= 4;
1802 case HIST_TYPE_INDIR_CALL
:
1803 hist
->n_counters
= 3;
1806 case HIST_TYPE_AVERAGE
:
1807 hist
->n_counters
= 2;
1811 hist
->n_counters
= 1;
1819 fprintf (dump_file
, "Stmt ");
1820 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1821 dump_histogram_value (dump_file
, hist
);