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
, tmpv
;
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 tmpv
= create_tmp_reg (optype
, "PROF");
614 tmp0
= make_ssa_name (tmpv
, NULL
);
615 tmp1
= make_ssa_name (tmpv
, NULL
);
616 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
617 SSA_NAME_DEF_STMT (tmp0
) = stmt1
;
618 stmt2
= gimple_build_assign (tmp1
, op2
);
619 SSA_NAME_DEF_STMT (tmp1
) = stmt2
;
620 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
621 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
622 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
623 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
626 tmp2
= create_tmp_reg (optype
, "PROF");
627 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
629 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
632 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
634 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
638 /* Edge e23 connects bb2 to bb3, etc. */
639 e12
= split_block (bb
, bb1end
);
642 e23
= split_block (bb2
, bb2end
);
644 bb3
->count
= all
- count
;
645 e34
= split_block (bb3
, bb3end
);
649 e12
->flags
&= ~EDGE_FALLTHRU
;
650 e12
->flags
|= EDGE_FALSE_VALUE
;
651 e12
->probability
= prob
;
654 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
655 e13
->probability
= REG_BR_PROB_BASE
- prob
;
656 e13
->count
= all
- count
;
660 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
661 e24
->probability
= REG_BR_PROB_BASE
;
664 e34
->probability
= REG_BR_PROB_BASE
;
665 e34
->count
= all
- count
;
671 /* Do transform 1) on INSN if applicable. */
674 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
676 histogram_value histogram
;
678 gcov_type val
, count
, all
;
679 tree result
, value
, tree_val
;
683 stmt
= gsi_stmt (*si
);
684 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
687 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
690 code
= gimple_assign_rhs_code (stmt
);
692 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
695 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
696 HIST_TYPE_SINGLE_VALUE
);
700 value
= histogram
->hvalue
.value
;
701 val
= histogram
->hvalue
.counters
[0];
702 count
= histogram
->hvalue
.counters
[1];
703 all
= histogram
->hvalue
.counters
[2];
704 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
706 /* We require that count is at least half of all; this means
707 that for the transformation to fire the value must be constant
708 at least 50% of time (and 75% gives the guarantee of usage). */
709 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
711 || optimize_bb_for_size_p (gimple_bb (stmt
)))
714 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
717 /* Compute probability of taking the optimal path. */
719 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
723 tree_val
= build_int_cst_wide (get_gcov_type (),
724 (unsigned HOST_WIDE_INT
) val
,
725 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
726 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
730 fprintf (dump_file
, "Div/mod by constant ");
731 print_generic_expr (dump_file
, value
, TDF_SLIM
);
732 fprintf (dump_file
, "=");
733 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
734 fprintf (dump_file
, " transformation on insn ");
735 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
738 gimple_assign_set_rhs_from_tree (si
, result
);
739 update_stmt (gsi_stmt (*si
));
744 /* Generate code for transformation 2 (with parent gimple assign STMT and
745 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
746 within roundoff error). This generates the result into a temp and returns
747 the temp; it does not replace or alter the original STMT. */
749 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
751 gimple stmt1
, stmt2
, stmt3
, stmt4
;
752 tree tmp2
, tmp3
, tmpv
;
753 gimple bb1end
, bb2end
, bb3end
;
754 basic_block bb
, bb2
, bb3
, bb4
;
755 tree optype
, op1
, op2
;
756 edge e12
, e13
, e23
, e24
, e34
;
757 gimple_stmt_iterator gsi
;
760 gcc_assert (is_gimple_assign (stmt
)
761 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
763 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
764 op1
= gimple_assign_rhs1 (stmt
);
765 op2
= gimple_assign_rhs2 (stmt
);
767 bb
= gimple_bb (stmt
);
768 gsi
= gsi_for_stmt (stmt
);
770 result
= create_tmp_reg (optype
, "PROF");
771 tmpv
= create_tmp_var (optype
, "PROF");
772 tmp2
= make_ssa_name (tmpv
, NULL
);
773 tmp3
= make_ssa_name (tmpv
, NULL
);
774 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
775 build_int_cst (optype
, -1));
776 SSA_NAME_DEF_STMT (tmp2
) = stmt2
;
777 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
778 SSA_NAME_DEF_STMT (tmp3
) = stmt3
;
779 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
780 NULL_TREE
, NULL_TREE
);
781 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
782 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
783 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
786 /* tmp2 == op2-1 inherited from previous block. */
787 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
788 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
791 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
793 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
797 /* Edge e23 connects bb2 to bb3, etc. */
798 e12
= split_block (bb
, bb1end
);
801 e23
= split_block (bb2
, bb2end
);
803 bb3
->count
= all
- count
;
804 e34
= split_block (bb3
, bb3end
);
808 e12
->flags
&= ~EDGE_FALLTHRU
;
809 e12
->flags
|= EDGE_FALSE_VALUE
;
810 e12
->probability
= prob
;
813 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
814 e13
->probability
= REG_BR_PROB_BASE
- prob
;
815 e13
->count
= all
- count
;
819 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
820 e24
->probability
= REG_BR_PROB_BASE
;
823 e34
->probability
= REG_BR_PROB_BASE
;
824 e34
->count
= all
- count
;
829 /* Do transform 2) on INSN if applicable. */
831 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
833 histogram_value histogram
;
835 gcov_type count
, wrong_values
, all
;
836 tree lhs_type
, result
, value
;
840 stmt
= gsi_stmt (*si
);
841 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
844 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
845 if (!INTEGRAL_TYPE_P (lhs_type
))
848 code
= gimple_assign_rhs_code (stmt
);
850 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
853 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
857 value
= histogram
->hvalue
.value
;
858 wrong_values
= histogram
->hvalue
.counters
[0];
859 count
= histogram
->hvalue
.counters
[1];
861 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
863 /* We require that we hit a power of 2 at least half of all evaluations. */
864 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
865 || count
< wrong_values
866 || optimize_bb_for_size_p (gimple_bb (stmt
)))
871 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
872 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
875 /* Compute probability of taking the optimal path. */
876 all
= count
+ wrong_values
;
878 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
882 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
886 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
888 gimple_assign_set_rhs_from_tree (si
, result
);
889 update_stmt (gsi_stmt (*si
));
894 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
895 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
896 supported and this is built into this interface. The probabilities of taking
897 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
898 COUNT2/ALL respectively within roundoff error). This generates the
899 result into a temp and returns the temp; it does not replace or alter
900 the original STMT. */
901 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
904 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
905 gcov_type count1
, gcov_type count2
, gcov_type all
)
907 gimple stmt1
, stmt2
, stmt3
;
909 gimple bb1end
, bb2end
= NULL
, bb3end
;
910 basic_block bb
, bb2
, bb3
, bb4
;
911 tree optype
, op1
, op2
;
912 edge e12
, e23
= 0, e24
, e34
, e14
;
913 gimple_stmt_iterator gsi
;
916 gcc_assert (is_gimple_assign (stmt
)
917 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
919 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
920 op1
= gimple_assign_rhs1 (stmt
);
921 op2
= gimple_assign_rhs2 (stmt
);
923 bb
= gimple_bb (stmt
);
924 gsi
= gsi_for_stmt (stmt
);
926 result
= create_tmp_reg (optype
, "PROF");
927 tmp1
= make_ssa_name (create_tmp_var (optype
, "PROF"), NULL
);
928 stmt1
= gimple_build_assign (result
, op1
);
929 stmt2
= gimple_build_assign (tmp1
, op2
);
930 SSA_NAME_DEF_STMT (tmp1
) = stmt2
;
931 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
932 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
933 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
934 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
937 if (ncounts
) /* Assumed to be 0 or 1 */
939 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
940 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
941 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
942 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
947 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
949 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
953 /* Edge e23 connects bb2 to bb3, etc. */
954 /* However block 3 is optional; if it is not there, references
955 to 3 really refer to block 2. */
956 e12
= split_block (bb
, bb1end
);
958 bb2
->count
= all
- count1
;
960 if (ncounts
) /* Assumed to be 0 or 1. */
962 e23
= split_block (bb2
, bb2end
);
964 bb3
->count
= all
- count1
- count2
;
967 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
971 e12
->flags
&= ~EDGE_FALLTHRU
;
972 e12
->flags
|= EDGE_FALSE_VALUE
;
973 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
974 e12
->count
= all
- count1
;
976 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
977 e14
->probability
= prob1
;
980 if (ncounts
) /* Assumed to be 0 or 1. */
982 e23
->flags
&= ~EDGE_FALLTHRU
;
983 e23
->flags
|= EDGE_FALSE_VALUE
;
984 e23
->count
= all
- count1
- count2
;
985 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
987 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
988 e24
->probability
= prob2
;
992 e34
->probability
= REG_BR_PROB_BASE
;
993 e34
->count
= all
- count1
- count2
;
999 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
1002 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
1004 histogram_value histogram
;
1005 enum tree_code code
;
1006 gcov_type count
, wrong_values
, all
;
1007 tree lhs_type
, result
;
1008 gcov_type prob1
, prob2
;
1009 unsigned int i
, steps
;
1010 gcov_type count1
, count2
;
1013 stmt
= gsi_stmt (*si
);
1014 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1017 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1018 if (!INTEGRAL_TYPE_P (lhs_type
))
1021 code
= gimple_assign_rhs_code (stmt
);
1023 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
1026 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
1032 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1033 all
+= histogram
->hvalue
.counters
[i
];
1035 wrong_values
+= histogram
->hvalue
.counters
[i
];
1036 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1037 steps
= histogram
->hdata
.intvl
.steps
;
1038 all
+= wrong_values
;
1039 count1
= histogram
->hvalue
.counters
[0];
1040 count2
= histogram
->hvalue
.counters
[1];
1042 /* Compute probability of taking the optimal path. */
1043 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1045 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1049 if (flag_profile_correction
&& count1
+ count2
> all
)
1050 all
= count1
+ count2
;
1052 gcc_assert (count1
+ count2
<= all
);
1054 /* We require that we use just subtractions in at least 50% of all
1057 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1059 count
+= histogram
->hvalue
.counters
[i
];
1060 if (count
* 2 >= all
)
1064 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1067 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1070 fprintf (dump_file
, "Mod subtract transformation on insn ");
1071 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1074 /* Compute probability of taking the optimal path(s). */
1077 prob1
= (count1
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1078 prob2
= (count2
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1085 /* In practice, "steps" is always 2. This interface reflects this,
1086 and will need to be changed if "steps" can change. */
1087 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1089 gimple_assign_set_rhs_from_tree (si
, result
);
1090 update_stmt (gsi_stmt (*si
));
1095 static VEC(cgraph_node_ptr
, heap
) *cgraph_node_map
= NULL
;
1097 /* Initialize map from FUNCDEF_NO to CGRAPH_NODE. */
1100 init_node_map (void)
1102 struct cgraph_node
*n
;
1104 if (get_last_funcdef_no ())
1105 VEC_safe_grow_cleared (cgraph_node_ptr
, heap
,
1106 cgraph_node_map
, get_last_funcdef_no ());
1108 FOR_EACH_FUNCTION (n
)
1110 if (DECL_STRUCT_FUNCTION (n
->symbol
.decl
))
1111 VEC_replace (cgraph_node_ptr
, cgraph_node_map
,
1112 DECL_STRUCT_FUNCTION (n
->symbol
.decl
)->funcdef_no
, n
);
1116 /* Delete the CGRAPH_NODE_MAP. */
1121 VEC_free (cgraph_node_ptr
, heap
, cgraph_node_map
);
1122 cgraph_node_map
= NULL
;
1125 /* Return cgraph node for function with pid */
1127 static inline struct cgraph_node
*
1128 find_func_by_funcdef_no (int func_id
)
1130 int max_id
= get_last_funcdef_no ();
1131 if (func_id
>= max_id
|| VEC_index (cgraph_node_ptr
,
1135 if (flag_profile_correction
)
1136 inform (DECL_SOURCE_LOCATION (current_function_decl
),
1137 "Inconsistent profile: indirect call target (%d) does not exist", func_id
);
1139 error ("Inconsistent profile: indirect call target (%d) does not exist", func_id
);
1144 return VEC_index (cgraph_node_ptr
, cgraph_node_map
, func_id
);
1147 /* Perform sanity check on the indirect call target. Due to race conditions,
1148 false function target may be attributed to an indirect call site. If the
1149 call expression type mismatches with the target function's type, expand_call
1150 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1151 Returns true if TARGET is considered ok for call CALL_STMT. */
1154 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1157 if (gimple_check_call_matching_types (call_stmt
, target
->symbol
.decl
))
1160 locus
= gimple_location (call_stmt
);
1161 inform (locus
, "Skipping target %s with mismatching types for icall ",
1162 cgraph_node_name (target
));
1166 /* Do transformation
1168 if (actual_callee_address == address_of_most_common_function/method)
1175 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1176 int prob
, gcov_type count
, gcov_type all
)
1178 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1179 tree tmp0
, tmp1
, tmpv
, tmp
;
1180 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1181 tree optype
= build_pointer_type (void_type_node
);
1182 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1183 gimple_stmt_iterator gsi
;
1186 cond_bb
= gimple_bb (icall_stmt
);
1187 gsi
= gsi_for_stmt (icall_stmt
);
1189 tmpv
= create_tmp_reg (optype
, "PROF");
1190 tmp0
= make_ssa_name (tmpv
, NULL
);
1191 tmp1
= make_ssa_name (tmpv
, NULL
);
1192 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1193 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1194 SSA_NAME_DEF_STMT (tmp0
) = load_stmt
;
1195 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1197 tmp
= fold_convert (optype
, build_addr (direct_call
->symbol
.decl
,
1198 current_function_decl
));
1199 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1200 SSA_NAME_DEF_STMT (tmp1
) = load_stmt
;
1201 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1203 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1204 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1206 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1207 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1208 update_stmt (icall_stmt
);
1209 dcall_stmt
= gimple_copy (icall_stmt
);
1210 gimple_call_set_fndecl (dcall_stmt
, direct_call
->symbol
.decl
);
1211 dflags
= flags_from_decl_or_type (direct_call
->symbol
.decl
);
1212 if ((dflags
& ECF_NORETURN
) != 0)
1213 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1214 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1217 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1218 e_cd
= split_block (cond_bb
, cond_stmt
);
1219 dcall_bb
= e_cd
->dest
;
1220 dcall_bb
->count
= count
;
1222 e_di
= split_block (dcall_bb
, dcall_stmt
);
1223 icall_bb
= e_di
->dest
;
1224 icall_bb
->count
= all
- count
;
1226 /* Do not disturb existing EH edges from the indirect call. */
1227 if (!stmt_ends_bb_p (icall_stmt
))
1228 e_ij
= split_block (icall_bb
, icall_stmt
);
1231 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1232 /* The indirect call might be noreturn. */
1235 e_ij
->probability
= REG_BR_PROB_BASE
;
1236 e_ij
->count
= all
- count
;
1237 e_ij
= single_pred_edge (split_edge (e_ij
));
1242 join_bb
= e_ij
->dest
;
1243 join_bb
->count
= all
;
1246 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1247 e_cd
->probability
= prob
;
1248 e_cd
->count
= count
;
1250 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1251 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1252 e_ci
->count
= all
- count
;
1258 if ((dflags
& ECF_NORETURN
) != 0)
1262 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1263 e_dj
->probability
= REG_BR_PROB_BASE
;
1264 e_dj
->count
= count
;
1266 e_ij
->count
= all
- count
;
1268 e_ij
->probability
= REG_BR_PROB_BASE
;
1271 /* Insert PHI node for the call result if necessary. */
1272 if (gimple_call_lhs (icall_stmt
)
1273 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1274 && (dflags
& ECF_NORETURN
) == 0)
1276 tree result
= gimple_call_lhs (icall_stmt
);
1277 gimple phi
= create_phi_node (result
, join_bb
);
1278 gimple_call_set_lhs (icall_stmt
,
1279 make_ssa_name (SSA_NAME_VAR (result
), icall_stmt
));
1280 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1281 gimple_call_set_lhs (dcall_stmt
,
1282 make_ssa_name (SSA_NAME_VAR (result
), dcall_stmt
));
1283 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1286 /* Build an EH edge for the direct call if necessary. */
1287 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1289 && stmt_could_throw_p (dcall_stmt
))
1293 gimple_stmt_iterator psi
;
1295 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1296 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1297 if (e_eh
->flags
& EDGE_EH
)
1299 e
= make_edge (dcall_bb
, e_eh
->dest
, EDGE_EH
);
1300 for (psi
= gsi_start_phis (e_eh
->dest
);
1301 !gsi_end_p (psi
); gsi_next (&psi
))
1303 gimple phi
= gsi_stmt (psi
);
1304 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1305 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1313 For every checked indirect/virtual call determine if most common pid of
1314 function/class method has probability more than 50%. If yes modify code of
1319 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1321 gimple stmt
= gsi_stmt (*gsi
);
1322 histogram_value histogram
;
1323 gcov_type val
, count
, all
, bb_all
;
1326 struct cgraph_node
*direct_call
;
1328 if (gimple_code (stmt
) != GIMPLE_CALL
)
1331 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1334 if (gimple_call_internal_p (stmt
))
1337 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1341 val
= histogram
->hvalue
.counters
[0];
1342 count
= histogram
->hvalue
.counters
[1];
1343 all
= histogram
->hvalue
.counters
[2];
1344 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1346 if (4 * count
<= 3 * all
)
1349 bb_all
= gimple_bb (stmt
)->count
;
1350 /* The order of CHECK_COUNTER calls is important -
1351 since check_counter can correct the third parameter
1352 and we want to make count <= all <= bb_all. */
1353 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1354 || check_counter (stmt
, "ic", &count
, &all
, all
))
1358 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1361 direct_call
= find_func_by_funcdef_no ((int)val
);
1363 if (direct_call
== NULL
)
1366 if (!check_ic_target (stmt
, direct_call
))
1369 modify
= gimple_ic (stmt
, direct_call
, prob
, count
, all
);
1373 fprintf (dump_file
, "Indirect call -> direct call ");
1374 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1375 fprintf (dump_file
, "=> ");
1376 print_generic_expr (dump_file
, direct_call
->symbol
.decl
, TDF_SLIM
);
1377 fprintf (dump_file
, " transformation on insn ");
1378 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1379 fprintf (dump_file
, " to ");
1380 print_gimple_stmt (dump_file
, modify
, 0, TDF_SLIM
);
1381 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1382 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1388 /* Return true if the stringop CALL with FNDECL shall be profiled.
1389 SIZE_ARG be set to the argument index for the size of the string
1393 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1395 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1397 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1398 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1403 case BUILT_IN_MEMCPY
:
1404 case BUILT_IN_MEMPCPY
:
1406 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1407 INTEGER_TYPE
, VOID_TYPE
);
1408 case BUILT_IN_MEMSET
:
1410 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1411 INTEGER_TYPE
, VOID_TYPE
);
1412 case BUILT_IN_BZERO
:
1414 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1421 /* Convert stringop (..., vcall_size)
1423 if (vcall_size == icall_size)
1424 stringop (..., icall_size);
1426 stringop (..., vcall_size);
1427 assuming we'll propagate a true constant into ICALL_SIZE later. */
1430 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1431 gcov_type count
, gcov_type all
)
1433 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1434 tree tmp0
, tmp1
, tmpv
, vcall_size
, optype
;
1435 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1436 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1437 gimple_stmt_iterator gsi
;
1441 fndecl
= gimple_call_fndecl (vcall_stmt
);
1442 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1445 cond_bb
= gimple_bb (vcall_stmt
);
1446 gsi
= gsi_for_stmt (vcall_stmt
);
1448 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1449 optype
= TREE_TYPE (vcall_size
);
1451 tmpv
= create_tmp_var (optype
, "PROF");
1452 tmp0
= make_ssa_name (tmpv
, NULL
);
1453 tmp1
= make_ssa_name (tmpv
, NULL
);
1454 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1455 SSA_NAME_DEF_STMT (tmp0
) = tmp_stmt
;
1456 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1458 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1459 SSA_NAME_DEF_STMT (tmp1
) = tmp_stmt
;
1460 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1462 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1463 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1465 gimple_set_vdef (vcall_stmt
, NULL
);
1466 gimple_set_vuse (vcall_stmt
, NULL
);
1467 update_stmt (vcall_stmt
);
1468 icall_stmt
= gimple_copy (vcall_stmt
);
1469 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1470 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1473 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1474 e_ci
= split_block (cond_bb
, cond_stmt
);
1475 icall_bb
= e_ci
->dest
;
1476 icall_bb
->count
= count
;
1478 e_iv
= split_block (icall_bb
, icall_stmt
);
1479 vcall_bb
= e_iv
->dest
;
1480 vcall_bb
->count
= all
- count
;
1482 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1483 join_bb
= e_vj
->dest
;
1484 join_bb
->count
= all
;
1486 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1487 e_ci
->probability
= prob
;
1488 e_ci
->count
= count
;
1490 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1491 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1492 e_cv
->count
= all
- count
;
1496 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1497 e_ij
->probability
= REG_BR_PROB_BASE
;
1498 e_ij
->count
= count
;
1500 e_vj
->probability
= REG_BR_PROB_BASE
;
1501 e_vj
->count
= all
- count
;
1503 /* Insert PHI node for the call result if necessary. */
1504 if (gimple_call_lhs (vcall_stmt
)
1505 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1507 tree result
= gimple_call_lhs (vcall_stmt
);
1508 gimple phi
= create_phi_node (result
, join_bb
);
1509 gimple_call_set_lhs (vcall_stmt
,
1510 make_ssa_name (SSA_NAME_VAR (result
), vcall_stmt
));
1511 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1512 gimple_call_set_lhs (icall_stmt
,
1513 make_ssa_name (SSA_NAME_VAR (result
), icall_stmt
));
1514 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1517 /* Because these are all string op builtins, they're all nothrow. */
1518 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1519 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1522 /* Find values inside STMT for that we want to measure histograms for
1523 division/modulo optimization. */
1525 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1527 gimple stmt
= gsi_stmt (*gsi
);
1530 enum built_in_function fcode
;
1531 histogram_value histogram
;
1532 gcov_type count
, all
, val
;
1534 unsigned int dest_align
, src_align
;
1539 if (gimple_code (stmt
) != GIMPLE_CALL
)
1541 fndecl
= gimple_call_fndecl (stmt
);
1544 fcode
= DECL_FUNCTION_CODE (fndecl
);
1545 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1548 blck_size
= gimple_call_arg (stmt
, size_arg
);
1549 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1552 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1555 val
= histogram
->hvalue
.counters
[0];
1556 count
= histogram
->hvalue
.counters
[1];
1557 all
= histogram
->hvalue
.counters
[2];
1558 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1559 /* We require that count is at least half of all; this means
1560 that for the transformation to fire the value must be constant
1561 at least 80% of time. */
1562 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1564 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1567 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1570 dest
= gimple_call_arg (stmt
, 0);
1571 dest_align
= get_pointer_alignment (dest
);
1574 case BUILT_IN_MEMCPY
:
1575 case BUILT_IN_MEMPCPY
:
1576 src
= gimple_call_arg (stmt
, 1);
1577 src_align
= get_pointer_alignment (src
);
1578 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1581 case BUILT_IN_MEMSET
:
1582 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1583 gimple_call_arg (stmt
, 1),
1587 case BUILT_IN_BZERO
:
1588 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1596 tree_val
= build_int_cst_wide (get_gcov_type (),
1597 (unsigned HOST_WIDE_INT
) val
,
1598 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1601 fprintf (dump_file
, "Single value %i stringop transformation on ",
1603 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1605 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1611 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1612 HOST_WIDE_INT
*expected_size
)
1614 histogram_value histogram
;
1615 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1617 *expected_size
= -1;
1618 else if (!histogram
->hvalue
.counters
[1])
1620 *expected_size
= -1;
1621 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1626 size
= ((histogram
->hvalue
.counters
[0]
1627 + histogram
->hvalue
.counters
[1] / 2)
1628 / histogram
->hvalue
.counters
[1]);
1629 /* Even if we can hold bigger value in SIZE, INT_MAX
1630 is safe "infinity" for code generation strategies. */
1633 *expected_size
= size
;
1634 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1636 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1638 *expected_align
= 0;
1639 else if (!histogram
->hvalue
.counters
[0])
1641 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1642 *expected_align
= 0;
1649 count
= histogram
->hvalue
.counters
[0];
1651 while (!(count
& alignment
)
1652 && (alignment
* 2 * BITS_PER_UNIT
))
1654 *expected_align
= alignment
* BITS_PER_UNIT
;
1655 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1660 /* Find values inside STMT for that we want to measure histograms for
1661 division/modulo optimization. */
1663 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1665 tree lhs
, divisor
, op0
, type
;
1666 histogram_value hist
;
1668 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1671 lhs
= gimple_assign_lhs (stmt
);
1672 type
= TREE_TYPE (lhs
);
1673 if (!INTEGRAL_TYPE_P (type
))
1676 switch (gimple_assign_rhs_code (stmt
))
1678 case TRUNC_DIV_EXPR
:
1679 case TRUNC_MOD_EXPR
:
1680 divisor
= gimple_assign_rhs2 (stmt
);
1681 op0
= gimple_assign_rhs1 (stmt
);
1683 VEC_reserve (histogram_value
, heap
, *values
, 3);
1685 if (is_gimple_reg (divisor
))
1686 /* Check for the case where the divisor is the same value most
1688 VEC_quick_push (histogram_value
, *values
,
1689 gimple_alloc_histogram_value (cfun
,
1690 HIST_TYPE_SINGLE_VALUE
,
1693 /* For mod, check whether it is not often a noop (or replaceable by
1694 a few subtractions). */
1695 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1696 && TYPE_UNSIGNED (type
))
1699 /* Check for a special case where the divisor is power of 2. */
1700 VEC_quick_push (histogram_value
, *values
,
1701 gimple_alloc_histogram_value (cfun
, HIST_TYPE_POW2
,
1704 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1705 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1707 hist
->hdata
.intvl
.int_start
= 0;
1708 hist
->hdata
.intvl
.steps
= 2;
1709 VEC_quick_push (histogram_value
, *values
, hist
);
1718 /* Find calls inside STMT for that we want to measure histograms for
1719 indirect/virtual call optimization. */
1722 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1726 if (gimple_code (stmt
) != GIMPLE_CALL
1727 || gimple_call_internal_p (stmt
)
1728 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1731 callee
= gimple_call_fn (stmt
);
1733 VEC_reserve (histogram_value
, heap
, *values
, 3);
1735 VEC_quick_push (histogram_value
, *values
,
1736 gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1742 /* Find values inside STMT for that we want to measure histograms for
1743 string operations. */
1745 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1752 if (gimple_code (stmt
) != GIMPLE_CALL
)
1754 fndecl
= gimple_call_fndecl (stmt
);
1758 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1761 dest
= gimple_call_arg (stmt
, 0);
1762 blck_size
= gimple_call_arg (stmt
, size_arg
);
1764 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1766 VEC_safe_push (histogram_value
, heap
, *values
,
1767 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1769 VEC_safe_push (histogram_value
, heap
, *values
,
1770 gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1773 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1774 VEC_safe_push (histogram_value
, heap
, *values
,
1775 gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1779 /* Find values inside STMT for that we want to measure histograms and adds
1780 them to list VALUES. */
1783 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1785 gimple_divmod_values_to_profile (stmt
, values
);
1786 gimple_stringops_values_to_profile (stmt
, values
);
1787 gimple_indirect_call_to_profile (stmt
, values
);
1791 gimple_find_values_to_profile (histogram_values
*values
)
1794 gimple_stmt_iterator gsi
;
1796 histogram_value hist
= NULL
;
1800 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1801 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1803 FOR_EACH_VEC_ELT (histogram_value
, *values
, i
, hist
)
1807 case HIST_TYPE_INTERVAL
:
1808 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1811 case HIST_TYPE_POW2
:
1812 hist
->n_counters
= 2;
1815 case HIST_TYPE_SINGLE_VALUE
:
1816 hist
->n_counters
= 3;
1819 case HIST_TYPE_CONST_DELTA
:
1820 hist
->n_counters
= 4;
1823 case HIST_TYPE_INDIR_CALL
:
1824 hist
->n_counters
= 3;
1827 case HIST_TYPE_AVERAGE
:
1828 hist
->n_counters
= 2;
1832 hist
->n_counters
= 1;
1840 fprintf (dump_file
, "Stmt ");
1841 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1842 dump_histogram_value (dump_file
, hist
);