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
= make_rename_temp (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
= make_rename_temp (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
= make_rename_temp (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 SSA_NAME_DEF_STMT (result
) = phi
;
1279 gimple_call_set_lhs (icall_stmt
,
1280 make_ssa_name (SSA_NAME_VAR (result
), icall_stmt
));
1281 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1282 gimple_call_set_lhs (dcall_stmt
,
1283 make_ssa_name (SSA_NAME_VAR (result
), dcall_stmt
));
1284 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1287 /* Build an EH edge for the direct call if necessary. */
1288 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1290 && stmt_could_throw_p (dcall_stmt
))
1294 gimple_stmt_iterator psi
;
1296 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1297 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1298 if (e_eh
->flags
& EDGE_EH
)
1300 e
= make_edge (dcall_bb
, e_eh
->dest
, EDGE_EH
);
1301 for (psi
= gsi_start_phis (e_eh
->dest
);
1302 !gsi_end_p (psi
); gsi_next (&psi
))
1304 gimple phi
= gsi_stmt (psi
);
1305 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1306 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1314 For every checked indirect/virtual call determine if most common pid of
1315 function/class method has probability more than 50%. If yes modify code of
1320 gimple_ic_transform (gimple_stmt_iterator
*gsi
)
1322 gimple stmt
= gsi_stmt (*gsi
);
1323 histogram_value histogram
;
1324 gcov_type val
, count
, all
, bb_all
;
1327 struct cgraph_node
*direct_call
;
1329 if (gimple_code (stmt
) != GIMPLE_CALL
)
1332 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1335 if (gimple_call_internal_p (stmt
))
1338 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1342 val
= histogram
->hvalue
.counters
[0];
1343 count
= histogram
->hvalue
.counters
[1];
1344 all
= histogram
->hvalue
.counters
[2];
1345 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1347 if (4 * count
<= 3 * all
)
1350 bb_all
= gimple_bb (stmt
)->count
;
1351 /* The order of CHECK_COUNTER calls is important -
1352 since check_counter can correct the third parameter
1353 and we want to make count <= all <= bb_all. */
1354 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1355 || check_counter (stmt
, "ic", &count
, &all
, all
))
1359 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1362 direct_call
= find_func_by_funcdef_no ((int)val
);
1364 if (direct_call
== NULL
)
1367 if (!check_ic_target (stmt
, direct_call
))
1370 modify
= gimple_ic (stmt
, direct_call
, prob
, count
, all
);
1374 fprintf (dump_file
, "Indirect call -> direct call ");
1375 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1376 fprintf (dump_file
, "=> ");
1377 print_generic_expr (dump_file
, direct_call
->symbol
.decl
, TDF_SLIM
);
1378 fprintf (dump_file
, " transformation on insn ");
1379 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1380 fprintf (dump_file
, " to ");
1381 print_gimple_stmt (dump_file
, modify
, 0, TDF_SLIM
);
1382 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1383 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1389 /* Return true if the stringop CALL with FNDECL shall be profiled.
1390 SIZE_ARG be set to the argument index for the size of the string
1394 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1396 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1398 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1399 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1404 case BUILT_IN_MEMCPY
:
1405 case BUILT_IN_MEMPCPY
:
1407 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1408 INTEGER_TYPE
, VOID_TYPE
);
1409 case BUILT_IN_MEMSET
:
1411 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1412 INTEGER_TYPE
, VOID_TYPE
);
1413 case BUILT_IN_BZERO
:
1415 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1422 /* Convert stringop (..., vcall_size)
1424 if (vcall_size == icall_size)
1425 stringop (..., icall_size);
1427 stringop (..., vcall_size);
1428 assuming we'll propagate a true constant into ICALL_SIZE later. */
1431 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1432 gcov_type count
, gcov_type all
)
1434 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1435 tree tmp0
, tmp1
, tmpv
, vcall_size
, optype
;
1436 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1437 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1438 gimple_stmt_iterator gsi
;
1442 fndecl
= gimple_call_fndecl (vcall_stmt
);
1443 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1446 cond_bb
= gimple_bb (vcall_stmt
);
1447 gsi
= gsi_for_stmt (vcall_stmt
);
1449 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1450 optype
= TREE_TYPE (vcall_size
);
1452 tmpv
= create_tmp_var (optype
, "PROF");
1453 tmp0
= make_ssa_name (tmpv
, NULL
);
1454 tmp1
= make_ssa_name (tmpv
, NULL
);
1455 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1456 SSA_NAME_DEF_STMT (tmp0
) = tmp_stmt
;
1457 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1459 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1460 SSA_NAME_DEF_STMT (tmp1
) = tmp_stmt
;
1461 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1463 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1464 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1466 gimple_set_vdef (vcall_stmt
, NULL
);
1467 gimple_set_vuse (vcall_stmt
, NULL
);
1468 update_stmt (vcall_stmt
);
1469 icall_stmt
= gimple_copy (vcall_stmt
);
1470 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1471 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1474 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1475 e_ci
= split_block (cond_bb
, cond_stmt
);
1476 icall_bb
= e_ci
->dest
;
1477 icall_bb
->count
= count
;
1479 e_iv
= split_block (icall_bb
, icall_stmt
);
1480 vcall_bb
= e_iv
->dest
;
1481 vcall_bb
->count
= all
- count
;
1483 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1484 join_bb
= e_vj
->dest
;
1485 join_bb
->count
= all
;
1487 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1488 e_ci
->probability
= prob
;
1489 e_ci
->count
= count
;
1491 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1492 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1493 e_cv
->count
= all
- count
;
1497 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1498 e_ij
->probability
= REG_BR_PROB_BASE
;
1499 e_ij
->count
= count
;
1501 e_vj
->probability
= REG_BR_PROB_BASE
;
1502 e_vj
->count
= all
- count
;
1504 /* Insert PHI node for the call result if necessary. */
1505 if (gimple_call_lhs (vcall_stmt
)
1506 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1508 tree result
= gimple_call_lhs (vcall_stmt
);
1509 gimple phi
= create_phi_node (result
, join_bb
);
1510 SSA_NAME_DEF_STMT (result
) = phi
;
1511 gimple_call_set_lhs (vcall_stmt
,
1512 make_ssa_name (SSA_NAME_VAR (result
), vcall_stmt
));
1513 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1514 gimple_call_set_lhs (icall_stmt
,
1515 make_ssa_name (SSA_NAME_VAR (result
), icall_stmt
));
1516 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1519 /* Because these are all string op builtins, they're all nothrow. */
1520 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1521 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1524 /* Find values inside STMT for that we want to measure histograms for
1525 division/modulo optimization. */
1527 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1529 gimple stmt
= gsi_stmt (*gsi
);
1532 enum built_in_function fcode
;
1533 histogram_value histogram
;
1534 gcov_type count
, all
, val
;
1536 unsigned int dest_align
, src_align
;
1541 if (gimple_code (stmt
) != GIMPLE_CALL
)
1543 fndecl
= gimple_call_fndecl (stmt
);
1546 fcode
= DECL_FUNCTION_CODE (fndecl
);
1547 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1550 blck_size
= gimple_call_arg (stmt
, size_arg
);
1551 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1554 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1557 val
= histogram
->hvalue
.counters
[0];
1558 count
= histogram
->hvalue
.counters
[1];
1559 all
= histogram
->hvalue
.counters
[2];
1560 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1561 /* We require that count is at least half of all; this means
1562 that for the transformation to fire the value must be constant
1563 at least 80% of time. */
1564 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1566 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1569 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1572 dest
= gimple_call_arg (stmt
, 0);
1573 dest_align
= get_pointer_alignment (dest
);
1576 case BUILT_IN_MEMCPY
:
1577 case BUILT_IN_MEMPCPY
:
1578 src
= gimple_call_arg (stmt
, 1);
1579 src_align
= get_pointer_alignment (src
);
1580 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1583 case BUILT_IN_MEMSET
:
1584 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1585 gimple_call_arg (stmt
, 1),
1589 case BUILT_IN_BZERO
:
1590 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1598 tree_val
= build_int_cst_wide (get_gcov_type (),
1599 (unsigned HOST_WIDE_INT
) val
,
1600 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1603 fprintf (dump_file
, "Single value %i stringop transformation on ",
1605 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1607 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1613 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1614 HOST_WIDE_INT
*expected_size
)
1616 histogram_value histogram
;
1617 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1619 *expected_size
= -1;
1620 else if (!histogram
->hvalue
.counters
[1])
1622 *expected_size
= -1;
1623 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1628 size
= ((histogram
->hvalue
.counters
[0]
1629 + histogram
->hvalue
.counters
[1] / 2)
1630 / histogram
->hvalue
.counters
[1]);
1631 /* Even if we can hold bigger value in SIZE, INT_MAX
1632 is safe "infinity" for code generation strategies. */
1635 *expected_size
= size
;
1636 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1638 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1640 *expected_align
= 0;
1641 else if (!histogram
->hvalue
.counters
[0])
1643 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1644 *expected_align
= 0;
1651 count
= histogram
->hvalue
.counters
[0];
1653 while (!(count
& alignment
)
1654 && (alignment
* 2 * BITS_PER_UNIT
))
1656 *expected_align
= alignment
* BITS_PER_UNIT
;
1657 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1662 /* Find values inside STMT for that we want to measure histograms for
1663 division/modulo optimization. */
1665 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1667 tree lhs
, divisor
, op0
, type
;
1668 histogram_value hist
;
1670 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1673 lhs
= gimple_assign_lhs (stmt
);
1674 type
= TREE_TYPE (lhs
);
1675 if (!INTEGRAL_TYPE_P (type
))
1678 switch (gimple_assign_rhs_code (stmt
))
1680 case TRUNC_DIV_EXPR
:
1681 case TRUNC_MOD_EXPR
:
1682 divisor
= gimple_assign_rhs2 (stmt
);
1683 op0
= gimple_assign_rhs1 (stmt
);
1685 VEC_reserve (histogram_value
, heap
, *values
, 3);
1687 if (is_gimple_reg (divisor
))
1688 /* Check for the case where the divisor is the same value most
1690 VEC_quick_push (histogram_value
, *values
,
1691 gimple_alloc_histogram_value (cfun
,
1692 HIST_TYPE_SINGLE_VALUE
,
1695 /* For mod, check whether it is not often a noop (or replaceable by
1696 a few subtractions). */
1697 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1698 && TYPE_UNSIGNED (type
))
1701 /* Check for a special case where the divisor is power of 2. */
1702 VEC_quick_push (histogram_value
, *values
,
1703 gimple_alloc_histogram_value (cfun
, HIST_TYPE_POW2
,
1706 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1707 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1709 hist
->hdata
.intvl
.int_start
= 0;
1710 hist
->hdata
.intvl
.steps
= 2;
1711 VEC_quick_push (histogram_value
, *values
, hist
);
1720 /* Find calls inside STMT for that we want to measure histograms for
1721 indirect/virtual call optimization. */
1724 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1728 if (gimple_code (stmt
) != GIMPLE_CALL
1729 || gimple_call_internal_p (stmt
)
1730 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1733 callee
= gimple_call_fn (stmt
);
1735 VEC_reserve (histogram_value
, heap
, *values
, 3);
1737 VEC_quick_push (histogram_value
, *values
,
1738 gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1744 /* Find values inside STMT for that we want to measure histograms for
1745 string operations. */
1747 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1754 if (gimple_code (stmt
) != GIMPLE_CALL
)
1756 fndecl
= gimple_call_fndecl (stmt
);
1760 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1763 dest
= gimple_call_arg (stmt
, 0);
1764 blck_size
= gimple_call_arg (stmt
, size_arg
);
1766 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1768 VEC_safe_push (histogram_value
, heap
, *values
,
1769 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1771 VEC_safe_push (histogram_value
, heap
, *values
,
1772 gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1775 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1776 VEC_safe_push (histogram_value
, heap
, *values
,
1777 gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1781 /* Find values inside STMT for that we want to measure histograms and adds
1782 them to list VALUES. */
1785 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1787 gimple_divmod_values_to_profile (stmt
, values
);
1788 gimple_stringops_values_to_profile (stmt
, values
);
1789 gimple_indirect_call_to_profile (stmt
, values
);
1793 gimple_find_values_to_profile (histogram_values
*values
)
1796 gimple_stmt_iterator gsi
;
1798 histogram_value hist
= NULL
;
1802 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1803 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1805 FOR_EACH_VEC_ELT (histogram_value
, *values
, i
, hist
)
1809 case HIST_TYPE_INTERVAL
:
1810 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1813 case HIST_TYPE_POW2
:
1814 hist
->n_counters
= 2;
1817 case HIST_TYPE_SINGLE_VALUE
:
1818 hist
->n_counters
= 3;
1821 case HIST_TYPE_CONST_DELTA
:
1822 hist
->n_counters
= 4;
1825 case HIST_TYPE_INDIR_CALL
:
1826 hist
->n_counters
= 3;
1829 case HIST_TYPE_AVERAGE
:
1830 hist
->n_counters
= 2;
1834 hist
->n_counters
= 1;
1842 fprintf (dump_file
, "Stmt ");
1843 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1844 dump_histogram_value (dump_file
, hist
);