1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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"
32 #include "insn-config.h"
37 #include "tree-flow.h"
38 #include "tree-flow-inline.h"
39 #include "diagnostic.h"
40 #include "tree-pretty-print.h"
41 #include "gimple-pretty-print.h"
47 #include "tree-pass.h"
49 #include "pointer-set.h"
51 static struct value_prof_hooks
*value_prof_hooks
;
53 /* In this file value profile based optimizations are placed. Currently the
54 following optimizations are implemented (for more detailed descriptions
55 see comments at value_profile_transformations):
57 1) Division/modulo specialization. Provided that we can determine that the
58 operands of the division have some special properties, we may use it to
59 produce more effective code.
60 2) Speculative prefetching. If we are able to determine that the difference
61 between addresses accessed by a memory reference is usually constant, we
62 may add the prefetch instructions.
63 FIXME: This transformation was removed together with RTL based value
66 3) Indirect/virtual call specialization. If we can determine most
67 common function callee in indirect/virtual call. We can use this
68 information to improve code effectiveness (especially info for
71 Every such optimization should add its requirements for profiled values to
72 insn_values_to_profile function. This function is called from branch_prob
73 in profile.c and the requested values are instrumented by it in the first
74 compilation with -fprofile-arcs. The optimization may then read the
75 gathered data in the second compilation with -fbranch-probabilities.
77 The measured data is pointed to from the histograms
78 field of the statement annotation of the instrumented insns. It is
79 kept as a linked list of struct histogram_value_t's, which contain the
80 same information as above. */
83 static tree
gimple_divmod_fixed_value (gimple
, tree
, int, gcov_type
, gcov_type
);
84 static tree
gimple_mod_pow2 (gimple
, int, gcov_type
, gcov_type
);
85 static tree
gimple_mod_subtract (gimple
, int, int, int, gcov_type
, gcov_type
,
87 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
88 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
89 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
90 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
91 static bool gimple_ic_transform (gimple
);
93 /* Allocate histogram value. */
95 static histogram_value
96 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
97 enum hist_type type
, gimple stmt
, tree value
)
99 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
100 hist
->hvalue
.value
= value
;
101 hist
->hvalue
.stmt
= stmt
;
106 /* Hash value for histogram. */
109 histogram_hash (const void *x
)
111 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
114 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
117 histogram_eq (const void *x
, const void *y
)
119 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
122 /* Set histogram for STMT. */
125 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
128 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
130 if (!VALUE_HISTOGRAMS (fun
))
131 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
133 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
134 htab_hash_pointer (stmt
),
135 hist
? INSERT
: NO_INSERT
);
139 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
145 /* Get histogram list for STMT. */
148 gimple_histogram_value (struct function
*fun
, gimple stmt
)
150 if (!VALUE_HISTOGRAMS (fun
))
152 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
153 htab_hash_pointer (stmt
));
156 /* Add histogram for STMT. */
159 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
160 histogram_value hist
)
162 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
163 set_histogram_value (fun
, stmt
, hist
);
167 /* Remove histogram HIST from STMT's histogram list. */
170 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
171 histogram_value hist
)
173 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
176 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
180 while (hist2
->hvalue
.next
!= hist
)
181 hist2
= hist2
->hvalue
.next
;
182 hist2
->hvalue
.next
= hist
->hvalue
.next
;
184 free (hist
->hvalue
.counters
);
185 #ifdef ENABLE_CHECKING
186 memset (hist
, 0xab, sizeof (*hist
));
192 /* Lookup histogram of type TYPE in the STMT. */
195 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
198 histogram_value hist
;
199 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
200 hist
= hist
->hvalue
.next
)
201 if (hist
->type
== type
)
206 /* Dump information about HIST to DUMP_FILE. */
209 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
213 case HIST_TYPE_INTERVAL
:
214 fprintf (dump_file
, "Interval counter range %d -- %d",
215 hist
->hdata
.intvl
.int_start
,
216 (hist
->hdata
.intvl
.int_start
217 + hist
->hdata
.intvl
.steps
- 1));
218 if (hist
->hvalue
.counters
)
221 fprintf(dump_file
, " [");
222 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
223 fprintf (dump_file
, " %d:"HOST_WIDEST_INT_PRINT_DEC
,
224 hist
->hdata
.intvl
.int_start
+ i
,
225 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
226 fprintf (dump_file
, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC
,
227 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
229 fprintf (dump_file
, ".\n");
233 fprintf (dump_file
, "Pow2 counter ");
234 if (hist
->hvalue
.counters
)
236 fprintf (dump_file
, "pow2:"HOST_WIDEST_INT_PRINT_DEC
237 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC
,
238 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
239 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
241 fprintf (dump_file
, ".\n");
244 case HIST_TYPE_SINGLE_VALUE
:
245 fprintf (dump_file
, "Single value ");
246 if (hist
->hvalue
.counters
)
248 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
249 " match:"HOST_WIDEST_INT_PRINT_DEC
250 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
251 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
252 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
253 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
255 fprintf (dump_file
, ".\n");
258 case HIST_TYPE_AVERAGE
:
259 fprintf (dump_file
, "Average value ");
260 if (hist
->hvalue
.counters
)
262 fprintf (dump_file
, "sum:"HOST_WIDEST_INT_PRINT_DEC
263 " times:"HOST_WIDEST_INT_PRINT_DEC
,
264 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
265 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
267 fprintf (dump_file
, ".\n");
271 fprintf (dump_file
, "IOR value ");
272 if (hist
->hvalue
.counters
)
274 fprintf (dump_file
, "ior:"HOST_WIDEST_INT_PRINT_DEC
,
275 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0]);
277 fprintf (dump_file
, ".\n");
280 case HIST_TYPE_CONST_DELTA
:
281 fprintf (dump_file
, "Constant delta ");
282 if (hist
->hvalue
.counters
)
284 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
285 " match:"HOST_WIDEST_INT_PRINT_DEC
286 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
287 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
288 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
289 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
291 fprintf (dump_file
, ".\n");
293 case HIST_TYPE_INDIR_CALL
:
294 fprintf (dump_file
, "Indirect call ");
295 if (hist
->hvalue
.counters
)
297 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
298 " match:"HOST_WIDEST_INT_PRINT_DEC
299 " all:"HOST_WIDEST_INT_PRINT_DEC
,
300 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
301 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
302 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
304 fprintf (dump_file
, ".\n");
309 /* Dump all histograms attached to STMT to DUMP_FILE. */
312 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
314 histogram_value hist
;
315 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
316 dump_histogram_value (dump_file
, hist
);
319 /* Remove all histograms associated with STMT. */
322 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
325 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
326 gimple_remove_histogram_value (fun
, stmt
, val
);
329 /* Duplicate all histograms associates with OSTMT to STMT. */
332 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
333 struct function
*ofun
, gimple ostmt
)
336 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
338 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
339 memcpy (new_val
, val
, sizeof (*val
));
340 new_val
->hvalue
.stmt
= stmt
;
341 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
342 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
343 gimple_add_histogram_value (fun
, stmt
, new_val
);
348 /* Move all histograms associated with OSTMT to STMT. */
351 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
353 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
356 /* The following three statements can't be reordered,
357 because histogram hashtab relies on stmt field value
358 for finding the exact slot. */
359 set_histogram_value (fun
, ostmt
, NULL
);
360 for (; val
!= NULL
; val
= val
->hvalue
.next
)
361 val
->hvalue
.stmt
= stmt
;
362 set_histogram_value (fun
, stmt
, val
);
366 static bool error_found
= false;
368 /* Helper function for verify_histograms. For each histogram reachable via htab
369 walk verify that it was reached via statement walk. */
372 visit_hist (void **slot
, void *data
)
374 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
375 histogram_value hist
= *(histogram_value
*) slot
;
376 if (!pointer_set_contains (visited
, hist
))
378 error ("Dead histogram");
379 dump_histogram_value (stderr
, hist
);
380 debug_gimple_stmt (hist
->hvalue
.stmt
);
387 /* Verify sanity of the histograms. */
390 verify_histograms (void)
393 gimple_stmt_iterator gsi
;
394 histogram_value hist
;
395 struct pointer_set_t
*visited_hists
;
398 visited_hists
= pointer_set_create ();
400 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
402 gimple stmt
= gsi_stmt (gsi
);
404 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
405 hist
= hist
->hvalue
.next
)
407 if (hist
->hvalue
.stmt
!= stmt
)
409 error ("Histogram value statement does not correspond to "
410 "the statement it is associated with");
411 debug_gimple_stmt (stmt
);
412 dump_histogram_value (stderr
, hist
);
415 pointer_set_insert (visited_hists
, hist
);
418 if (VALUE_HISTOGRAMS (cfun
))
419 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, visited_hists
);
420 pointer_set_destroy (visited_hists
);
422 internal_error ("verify_histograms failed");
425 /* Helper function for verify_histograms. For each histogram reachable via htab
426 walk verify that it was reached via statement walk. */
429 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
431 histogram_value hist
= *(histogram_value
*) slot
;
432 free (hist
->hvalue
.counters
);
433 #ifdef ENABLE_CHECKING
434 memset (hist
, 0xab, sizeof (*hist
));
441 free_histograms (void)
443 if (VALUE_HISTOGRAMS (cfun
))
445 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
446 htab_delete (VALUE_HISTOGRAMS (cfun
));
447 VALUE_HISTOGRAMS (cfun
) = NULL
;
452 /* The overall number of invocations of the counter should match
453 execution count of basic block. Report it as error rather than
454 internal error as it might mean that user has misused the profile
458 check_counter (gimple stmt
, const char * name
,
459 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
461 if (*all
!= bb_count
|| *count
> *all
)
464 locus
= (stmt
!= NULL
)
465 ? gimple_location (stmt
)
466 : DECL_SOURCE_LOCATION (current_function_decl
);
467 if (flag_profile_correction
)
469 inform (locus
, "Correcting inconsistent value profile: "
470 "%s profiler overall count (%d) does not match BB count "
471 "(%d)", name
, (int)*all
, (int)bb_count
);
479 error_at (locus
, "Corrupted value profile: %s "
480 "profiler overall count (%d) does not match BB count (%d)",
481 name
, (int)*all
, (int)bb_count
);
490 /* GIMPLE based transformations. */
493 gimple_value_profile_transformations (void)
496 gimple_stmt_iterator gsi
;
497 bool changed
= false;
501 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
503 gimple stmt
= gsi_stmt (gsi
);
504 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
510 fprintf (dump_file
, "Trying transformations on stmt ");
511 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
512 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
515 /* Transformations: */
516 /* The order of things in this conditional controls which
517 transformation is used when more than one is applicable. */
518 /* It is expected that any code added by the transformations
519 will be added before the current statement, and that the
520 current statement remain valid (although possibly
521 modified) upon return. */
522 if (flag_value_profile_transformations
523 && (gimple_mod_subtract_transform (&gsi
)
524 || gimple_divmod_fixed_value_transform (&gsi
)
525 || gimple_mod_pow2_value_transform (&gsi
)
526 || gimple_stringops_transform (&gsi
)
527 || gimple_ic_transform (stmt
)))
529 stmt
= gsi_stmt (gsi
);
531 /* Original statement may no longer be in the same block. */
532 if (bb
!= gimple_bb (stmt
))
534 bb
= gimple_bb (stmt
);
535 gsi
= gsi_for_stmt (stmt
);
550 /* Generate code for transformation 1 (with parent gimple assignment
551 STMT and probability of taking the optimal path PROB, which is
552 equivalent to COUNT/ALL within roundoff error). This generates the
553 result into a temp and returns the temp; it does not replace or
554 alter the original STMT. */
557 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
560 gimple stmt1
, stmt2
, stmt3
;
561 tree tmp0
, tmp1
, tmp2
, tmpv
;
562 gimple bb1end
, bb2end
, bb3end
;
563 basic_block bb
, bb2
, bb3
, bb4
;
564 tree optype
, op1
, op2
;
565 edge e12
, e13
, e23
, e24
, e34
;
566 gimple_stmt_iterator gsi
;
568 gcc_assert (is_gimple_assign (stmt
)
569 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
570 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
572 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
573 op1
= gimple_assign_rhs1 (stmt
);
574 op2
= gimple_assign_rhs2 (stmt
);
576 bb
= gimple_bb (stmt
);
577 gsi
= gsi_for_stmt (stmt
);
579 tmpv
= create_tmp_reg (optype
, "PROF");
580 tmp0
= make_ssa_name (tmpv
, NULL
);
581 tmp1
= make_ssa_name (tmpv
, NULL
);
582 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
583 SSA_NAME_DEF_STMT (tmp0
) = stmt1
;
584 stmt2
= gimple_build_assign (tmp1
, op2
);
585 SSA_NAME_DEF_STMT (tmp1
) = stmt2
;
586 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
587 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
588 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
589 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
592 tmp2
= make_rename_temp (optype
, "PROF");
593 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
595 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
598 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
600 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
604 /* Edge e23 connects bb2 to bb3, etc. */
605 e12
= split_block (bb
, bb1end
);
608 e23
= split_block (bb2
, bb2end
);
610 bb3
->count
= all
- count
;
611 e34
= split_block (bb3
, bb3end
);
615 e12
->flags
&= ~EDGE_FALLTHRU
;
616 e12
->flags
|= EDGE_FALSE_VALUE
;
617 e12
->probability
= prob
;
620 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
621 e13
->probability
= REG_BR_PROB_BASE
- prob
;
622 e13
->count
= all
- count
;
626 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
627 e24
->probability
= REG_BR_PROB_BASE
;
630 e34
->probability
= REG_BR_PROB_BASE
;
631 e34
->count
= all
- count
;
637 /* Do transform 1) on INSN if applicable. */
640 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
642 histogram_value histogram
;
644 gcov_type val
, count
, all
;
645 tree result
, value
, tree_val
;
649 stmt
= gsi_stmt (*si
);
650 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
653 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
656 code
= gimple_assign_rhs_code (stmt
);
658 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
661 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
662 HIST_TYPE_SINGLE_VALUE
);
666 value
= histogram
->hvalue
.value
;
667 val
= histogram
->hvalue
.counters
[0];
668 count
= histogram
->hvalue
.counters
[1];
669 all
= histogram
->hvalue
.counters
[2];
670 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
672 /* We require that count is at least half of all; this means
673 that for the transformation to fire the value must be constant
674 at least 50% of time (and 75% gives the guarantee of usage). */
675 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
677 || optimize_bb_for_size_p (gimple_bb (stmt
)))
680 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
683 /* Compute probability of taking the optimal path. */
685 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
689 tree_val
= build_int_cst_wide (get_gcov_type (),
690 (unsigned HOST_WIDE_INT
) val
,
691 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
692 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
696 fprintf (dump_file
, "Div/mod by constant ");
697 print_generic_expr (dump_file
, value
, TDF_SLIM
);
698 fprintf (dump_file
, "=");
699 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
700 fprintf (dump_file
, " transformation on insn ");
701 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
704 gimple_assign_set_rhs_from_tree (si
, result
);
709 /* Generate code for transformation 2 (with parent gimple assign STMT and
710 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
711 within roundoff error). This generates the result into a temp and returns
712 the temp; it does not replace or alter the original STMT. */
714 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
716 gimple stmt1
, stmt2
, stmt3
, stmt4
;
717 tree tmp2
, tmp3
, tmpv
;
718 gimple bb1end
, bb2end
, bb3end
;
719 basic_block bb
, bb2
, bb3
, bb4
;
720 tree optype
, op1
, op2
;
721 edge e12
, e13
, e23
, e24
, e34
;
722 gimple_stmt_iterator gsi
;
725 gcc_assert (is_gimple_assign (stmt
)
726 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
728 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
729 op1
= gimple_assign_rhs1 (stmt
);
730 op2
= gimple_assign_rhs2 (stmt
);
732 bb
= gimple_bb (stmt
);
733 gsi
= gsi_for_stmt (stmt
);
735 result
= make_rename_temp (optype
, "PROF");
736 tmpv
= create_tmp_var (optype
, "PROF");
737 tmp2
= make_ssa_name (tmpv
, NULL
);
738 tmp3
= make_ssa_name (tmpv
, NULL
);
739 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
740 build_int_cst (optype
, -1));
741 SSA_NAME_DEF_STMT (tmp2
) = stmt2
;
742 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
743 SSA_NAME_DEF_STMT (tmp3
) = stmt3
;
744 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
745 NULL_TREE
, NULL_TREE
);
746 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
747 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
748 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
751 /* tmp2 == op2-1 inherited from previous block. */
752 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
753 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
756 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
758 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
762 /* Edge e23 connects bb2 to bb3, etc. */
763 e12
= split_block (bb
, bb1end
);
766 e23
= split_block (bb2
, bb2end
);
768 bb3
->count
= all
- count
;
769 e34
= split_block (bb3
, bb3end
);
773 e12
->flags
&= ~EDGE_FALLTHRU
;
774 e12
->flags
|= EDGE_FALSE_VALUE
;
775 e12
->probability
= prob
;
778 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
779 e13
->probability
= REG_BR_PROB_BASE
- prob
;
780 e13
->count
= all
- count
;
784 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
785 e24
->probability
= REG_BR_PROB_BASE
;
788 e34
->probability
= REG_BR_PROB_BASE
;
789 e34
->count
= all
- count
;
794 /* Do transform 2) on INSN if applicable. */
796 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
798 histogram_value histogram
;
800 gcov_type count
, wrong_values
, all
;
801 tree lhs_type
, result
, value
;
805 stmt
= gsi_stmt (*si
);
806 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
809 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
810 if (!INTEGRAL_TYPE_P (lhs_type
))
813 code
= gimple_assign_rhs_code (stmt
);
815 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
818 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
822 value
= histogram
->hvalue
.value
;
823 wrong_values
= histogram
->hvalue
.counters
[0];
824 count
= histogram
->hvalue
.counters
[1];
826 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
828 /* We require that we hit a power of 2 at least half of all evaluations. */
829 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
830 || count
< wrong_values
831 || optimize_bb_for_size_p (gimple_bb (stmt
)))
836 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
837 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
840 /* Compute probability of taking the optimal path. */
841 all
= count
+ wrong_values
;
843 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
847 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
851 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
853 gimple_assign_set_rhs_from_tree (si
, result
);
858 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
859 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
860 supported and this is built into this interface. The probabilities of taking
861 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
862 COUNT2/ALL respectively within roundoff error). This generates the
863 result into a temp and returns the temp; it does not replace or alter
864 the original STMT. */
865 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
868 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
869 gcov_type count1
, gcov_type count2
, gcov_type all
)
871 gimple stmt1
, stmt2
, stmt3
;
873 gimple bb1end
, bb2end
= NULL
, bb3end
;
874 basic_block bb
, bb2
, bb3
, bb4
;
875 tree optype
, op1
, op2
;
876 edge e12
, e23
= 0, e24
, e34
, e14
;
877 gimple_stmt_iterator gsi
;
880 gcc_assert (is_gimple_assign (stmt
)
881 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
883 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
884 op1
= gimple_assign_rhs1 (stmt
);
885 op2
= gimple_assign_rhs2 (stmt
);
887 bb
= gimple_bb (stmt
);
888 gsi
= gsi_for_stmt (stmt
);
890 result
= make_rename_temp (optype
, "PROF");
891 tmp1
= make_ssa_name (create_tmp_var (optype
, "PROF"), NULL
);
892 stmt1
= gimple_build_assign (result
, op1
);
893 stmt2
= gimple_build_assign (tmp1
, op2
);
894 SSA_NAME_DEF_STMT (tmp1
) = stmt2
;
895 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
896 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
897 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
898 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
901 if (ncounts
) /* Assumed to be 0 or 1 */
903 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
904 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
905 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
906 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
911 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
913 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
917 /* Edge e23 connects bb2 to bb3, etc. */
918 /* However block 3 is optional; if it is not there, references
919 to 3 really refer to block 2. */
920 e12
= split_block (bb
, bb1end
);
922 bb2
->count
= all
- count1
;
924 if (ncounts
) /* Assumed to be 0 or 1. */
926 e23
= split_block (bb2
, bb2end
);
928 bb3
->count
= all
- count1
- count2
;
931 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
935 e12
->flags
&= ~EDGE_FALLTHRU
;
936 e12
->flags
|= EDGE_FALSE_VALUE
;
937 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
938 e12
->count
= all
- count1
;
940 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
941 e14
->probability
= prob1
;
944 if (ncounts
) /* Assumed to be 0 or 1. */
946 e23
->flags
&= ~EDGE_FALLTHRU
;
947 e23
->flags
|= EDGE_FALSE_VALUE
;
948 e23
->count
= all
- count1
- count2
;
949 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
951 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
952 e24
->probability
= prob2
;
956 e34
->probability
= REG_BR_PROB_BASE
;
957 e34
->count
= all
- count1
- count2
;
963 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
966 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
968 histogram_value histogram
;
970 gcov_type count
, wrong_values
, all
;
971 tree lhs_type
, result
;
972 gcov_type prob1
, prob2
;
973 unsigned int i
, steps
;
974 gcov_type count1
, count2
;
977 stmt
= gsi_stmt (*si
);
978 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
981 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
982 if (!INTEGRAL_TYPE_P (lhs_type
))
985 code
= gimple_assign_rhs_code (stmt
);
987 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
990 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
996 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
997 all
+= histogram
->hvalue
.counters
[i
];
999 wrong_values
+= histogram
->hvalue
.counters
[i
];
1000 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1001 steps
= histogram
->hdata
.intvl
.steps
;
1002 all
+= wrong_values
;
1003 count1
= histogram
->hvalue
.counters
[0];
1004 count2
= histogram
->hvalue
.counters
[1];
1006 /* Compute probability of taking the optimal path. */
1007 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1009 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1013 if (flag_profile_correction
&& count1
+ count2
> all
)
1014 all
= count1
+ count2
;
1016 gcc_assert (count1
+ count2
<= all
);
1018 /* We require that we use just subtractions in at least 50% of all
1021 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1023 count
+= histogram
->hvalue
.counters
[i
];
1024 if (count
* 2 >= all
)
1028 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1031 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1034 fprintf (dump_file
, "Mod subtract transformation on insn ");
1035 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1038 /* Compute probability of taking the optimal path(s). */
1041 prob1
= (count1
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1042 prob2
= (count2
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1049 /* In practice, "steps" is always 2. This interface reflects this,
1050 and will need to be changed if "steps" can change. */
1051 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1053 gimple_assign_set_rhs_from_tree (si
, result
);
1058 static struct cgraph_node
** pid_map
= NULL
;
1060 /* Initialize map of pids (pid -> cgraph node) */
1065 struct cgraph_node
*n
;
1067 if (pid_map
!= NULL
)
1070 pid_map
= XCNEWVEC (struct cgraph_node
*, cgraph_max_pid
);
1072 for (n
= cgraph_nodes
; n
; n
= n
->next
)
1075 pid_map
[n
->pid
] = n
;
1079 /* Return cgraph node for function with pid */
1081 static inline struct cgraph_node
*
1082 find_func_by_pid (int pid
)
1086 return pid_map
[pid
];
1089 /* Do transformation
1091 if (actual_callee_address == address_of_most_common_function/method)
1098 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1099 int prob
, gcov_type count
, gcov_type all
)
1101 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1102 tree tmp0
, tmp1
, tmpv
, tmp
;
1103 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
;
1104 tree optype
= build_pointer_type (void_type_node
);
1105 edge e_cd
, e_ci
, e_di
, e_dj
, e_ij
;
1106 gimple_stmt_iterator gsi
;
1109 cond_bb
= gimple_bb (icall_stmt
);
1110 gsi
= gsi_for_stmt (icall_stmt
);
1112 tmpv
= create_tmp_reg (optype
, "PROF");
1113 tmp0
= make_ssa_name (tmpv
, NULL
);
1114 tmp1
= make_ssa_name (tmpv
, NULL
);
1115 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1116 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1117 SSA_NAME_DEF_STMT (tmp0
) = load_stmt
;
1118 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1120 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1121 current_function_decl
));
1122 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1123 SSA_NAME_DEF_STMT (tmp1
) = load_stmt
;
1124 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1126 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1127 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1129 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1130 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1131 update_stmt (icall_stmt
);
1132 dcall_stmt
= gimple_copy (icall_stmt
);
1133 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1134 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1137 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1138 e_cd
= split_block (cond_bb
, cond_stmt
);
1139 dcall_bb
= e_cd
->dest
;
1140 dcall_bb
->count
= count
;
1142 e_di
= split_block (dcall_bb
, dcall_stmt
);
1143 icall_bb
= e_di
->dest
;
1144 icall_bb
->count
= all
- count
;
1146 e_ij
= split_block (icall_bb
, icall_stmt
);
1147 join_bb
= e_ij
->dest
;
1148 join_bb
->count
= all
;
1150 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1151 e_cd
->probability
= prob
;
1152 e_cd
->count
= count
;
1154 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1155 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1156 e_ci
->count
= all
- count
;
1160 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1161 e_dj
->probability
= REG_BR_PROB_BASE
;
1162 e_dj
->count
= count
;
1164 e_ij
->probability
= REG_BR_PROB_BASE
;
1165 e_ij
->count
= all
- count
;
1167 /* Insert PHI node for the call result if necessary. */
1168 if (gimple_call_lhs (icall_stmt
)
1169 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
)
1171 tree result
= gimple_call_lhs (icall_stmt
);
1172 gimple phi
= create_phi_node (result
, join_bb
);
1173 SSA_NAME_DEF_STMT (result
) = phi
;
1174 gimple_call_set_lhs (icall_stmt
,
1175 make_ssa_name (SSA_NAME_VAR (result
), icall_stmt
));
1176 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1177 gimple_call_set_lhs (dcall_stmt
,
1178 make_ssa_name (SSA_NAME_VAR (result
), dcall_stmt
));
1179 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1183 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1186 if (stmt_could_throw_p (dcall_stmt
))
1188 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1189 make_eh_edges (dcall_stmt
);
1192 gcc_assert (stmt_could_throw_p (icall_stmt
));
1193 make_eh_edges (icall_stmt
);
1195 /* The old EH edges are sill on the join BB, purge them. */
1196 gimple_purge_dead_eh_edges (join_bb
);
1203 For every checked indirect/virtual call determine if most common pid of
1204 function/class method has probability more than 50%. If yes modify code of
1209 gimple_ic_transform (gimple stmt
)
1211 histogram_value histogram
;
1212 gcov_type val
, count
, all
, bb_all
;
1216 struct cgraph_node
*direct_call
;
1218 if (gimple_code (stmt
) != GIMPLE_CALL
)
1221 callee
= gimple_call_fn (stmt
);
1223 if (TREE_CODE (callee
) == FUNCTION_DECL
)
1226 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1230 val
= histogram
->hvalue
.counters
[0];
1231 count
= histogram
->hvalue
.counters
[1];
1232 all
= histogram
->hvalue
.counters
[2];
1233 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1235 if (4 * count
<= 3 * all
)
1238 bb_all
= gimple_bb (stmt
)->count
;
1239 /* The order of CHECK_COUNTER calls is important -
1240 since check_counter can correct the third parameter
1241 and we want to make count <= all <= bb_all. */
1242 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1243 || check_counter (stmt
, "ic", &count
, &all
, all
))
1247 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1250 direct_call
= find_func_by_pid ((int)val
);
1252 if (direct_call
== NULL
)
1255 modify
= gimple_ic (stmt
, direct_call
, prob
, count
, all
);
1259 fprintf (dump_file
, "Indirect call -> direct call ");
1260 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1261 fprintf (dump_file
, "=> ");
1262 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1263 fprintf (dump_file
, " transformation on insn ");
1264 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1265 fprintf (dump_file
, " to ");
1266 print_gimple_stmt (dump_file
, modify
, 0, TDF_SLIM
);
1267 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1268 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1274 /* Return true if the stringop CALL with FNDECL shall be profiled.
1275 SIZE_ARG be set to the argument index for the size of the string
1279 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1281 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1283 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1284 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1289 case BUILT_IN_MEMCPY
:
1290 case BUILT_IN_MEMPCPY
:
1292 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1293 INTEGER_TYPE
, VOID_TYPE
);
1294 case BUILT_IN_MEMSET
:
1296 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1297 INTEGER_TYPE
, VOID_TYPE
);
1298 case BUILT_IN_BZERO
:
1300 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1307 /* Convert stringop (..., vcall_size)
1309 if (vcall_size == icall_size)
1310 stringop (..., icall_size);
1312 stringop (..., vcall_size);
1313 assuming we'll propagate a true constant into ICALL_SIZE later. */
1316 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1317 gcov_type count
, gcov_type all
)
1319 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1320 tree tmp0
, tmp1
, tmpv
, vcall_size
, optype
;
1321 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1322 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1323 gimple_stmt_iterator gsi
;
1327 fndecl
= gimple_call_fndecl (vcall_stmt
);
1328 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1331 cond_bb
= gimple_bb (vcall_stmt
);
1332 gsi
= gsi_for_stmt (vcall_stmt
);
1334 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1335 optype
= TREE_TYPE (vcall_size
);
1337 tmpv
= create_tmp_var (optype
, "PROF");
1338 tmp0
= make_ssa_name (tmpv
, NULL
);
1339 tmp1
= make_ssa_name (tmpv
, NULL
);
1340 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1341 SSA_NAME_DEF_STMT (tmp0
) = tmp_stmt
;
1342 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1344 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1345 SSA_NAME_DEF_STMT (tmp1
) = tmp_stmt
;
1346 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1348 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1349 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1351 gimple_set_vdef (vcall_stmt
, NULL
);
1352 gimple_set_vuse (vcall_stmt
, NULL
);
1353 update_stmt (vcall_stmt
);
1354 icall_stmt
= gimple_copy (vcall_stmt
);
1355 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1356 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1359 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1360 e_ci
= split_block (cond_bb
, cond_stmt
);
1361 icall_bb
= e_ci
->dest
;
1362 icall_bb
->count
= count
;
1364 e_iv
= split_block (icall_bb
, icall_stmt
);
1365 vcall_bb
= e_iv
->dest
;
1366 vcall_bb
->count
= all
- count
;
1368 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1369 join_bb
= e_vj
->dest
;
1370 join_bb
->count
= all
;
1372 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1373 e_ci
->probability
= prob
;
1374 e_ci
->count
= count
;
1376 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1377 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1378 e_cv
->count
= all
- count
;
1382 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1383 e_ij
->probability
= REG_BR_PROB_BASE
;
1384 e_ij
->count
= count
;
1386 e_vj
->probability
= REG_BR_PROB_BASE
;
1387 e_vj
->count
= all
- count
;
1389 /* Because these are all string op builtins, they're all nothrow. */
1390 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1391 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1394 /* Find values inside STMT for that we want to measure histograms for
1395 division/modulo optimization. */
1397 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1399 gimple stmt
= gsi_stmt (*gsi
);
1402 enum built_in_function fcode
;
1403 histogram_value histogram
;
1404 gcov_type count
, all
, val
;
1406 unsigned int dest_align
, src_align
;
1411 if (gimple_code (stmt
) != GIMPLE_CALL
)
1413 fndecl
= gimple_call_fndecl (stmt
);
1416 fcode
= DECL_FUNCTION_CODE (fndecl
);
1417 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1420 blck_size
= gimple_call_arg (stmt
, size_arg
);
1421 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1424 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1427 val
= histogram
->hvalue
.counters
[0];
1428 count
= histogram
->hvalue
.counters
[1];
1429 all
= histogram
->hvalue
.counters
[2];
1430 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1431 /* We require that count is at least half of all; this means
1432 that for the transformation to fire the value must be constant
1433 at least 80% of time. */
1434 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1436 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1439 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1442 dest
= gimple_call_arg (stmt
, 0);
1443 dest_align
= get_pointer_alignment (dest
, BIGGEST_ALIGNMENT
);
1446 case BUILT_IN_MEMCPY
:
1447 case BUILT_IN_MEMPCPY
:
1448 src
= gimple_call_arg (stmt
, 1);
1449 src_align
= get_pointer_alignment (src
, BIGGEST_ALIGNMENT
);
1450 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1453 case BUILT_IN_MEMSET
:
1454 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1455 gimple_call_arg (stmt
, 1),
1459 case BUILT_IN_BZERO
:
1460 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1468 tree_val
= build_int_cst_wide (get_gcov_type (),
1469 (unsigned HOST_WIDE_INT
) val
,
1470 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1473 fprintf (dump_file
, "Single value %i stringop transformation on ",
1475 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1477 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1483 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1484 HOST_WIDE_INT
*expected_size
)
1486 histogram_value histogram
;
1487 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1489 *expected_size
= -1;
1490 else if (!histogram
->hvalue
.counters
[1])
1492 *expected_size
= -1;
1493 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1498 size
= ((histogram
->hvalue
.counters
[0]
1499 + histogram
->hvalue
.counters
[1] / 2)
1500 / histogram
->hvalue
.counters
[1]);
1501 /* Even if we can hold bigger value in SIZE, INT_MAX
1502 is safe "infinity" for code generation strategies. */
1505 *expected_size
= size
;
1506 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1508 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1510 *expected_align
= 0;
1511 else if (!histogram
->hvalue
.counters
[0])
1513 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1514 *expected_align
= 0;
1521 count
= histogram
->hvalue
.counters
[0];
1523 while (!(count
& alignment
)
1524 && (alignment
* 2 * BITS_PER_UNIT
))
1526 *expected_align
= alignment
* BITS_PER_UNIT
;
1527 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1531 struct value_prof_hooks
{
1532 /* Find list of values for which we want to measure histograms. */
1533 void (*find_values_to_profile
) (histogram_values
*);
1535 /* Identify and exploit properties of values that are hard to analyze
1536 statically. See value-prof.c for more detail. */
1537 bool (*value_profile_transformations
) (void);
1540 /* Find values inside STMT for that we want to measure histograms for
1541 division/modulo optimization. */
1543 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1545 tree lhs
, divisor
, op0
, type
;
1546 histogram_value hist
;
1548 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1551 lhs
= gimple_assign_lhs (stmt
);
1552 type
= TREE_TYPE (lhs
);
1553 if (!INTEGRAL_TYPE_P (type
))
1556 switch (gimple_assign_rhs_code (stmt
))
1558 case TRUNC_DIV_EXPR
:
1559 case TRUNC_MOD_EXPR
:
1560 divisor
= gimple_assign_rhs2 (stmt
);
1561 op0
= gimple_assign_rhs1 (stmt
);
1563 VEC_reserve (histogram_value
, heap
, *values
, 3);
1565 if (is_gimple_reg (divisor
))
1566 /* Check for the case where the divisor is the same value most
1568 VEC_quick_push (histogram_value
, *values
,
1569 gimple_alloc_histogram_value (cfun
,
1570 HIST_TYPE_SINGLE_VALUE
,
1573 /* For mod, check whether it is not often a noop (or replaceable by
1574 a few subtractions). */
1575 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1576 && TYPE_UNSIGNED (type
))
1579 /* Check for a special case where the divisor is power of 2. */
1580 VEC_quick_push (histogram_value
, *values
,
1581 gimple_alloc_histogram_value (cfun
, HIST_TYPE_POW2
,
1584 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1585 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1587 hist
->hdata
.intvl
.int_start
= 0;
1588 hist
->hdata
.intvl
.steps
= 2;
1589 VEC_quick_push (histogram_value
, *values
, hist
);
1598 /* Find calls inside STMT for that we want to measure histograms for
1599 indirect/virtual call optimization. */
1602 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1606 if (gimple_code (stmt
) != GIMPLE_CALL
1607 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1610 callee
= gimple_call_fn (stmt
);
1612 VEC_reserve (histogram_value
, heap
, *values
, 3);
1614 VEC_quick_push (histogram_value
, *values
,
1615 gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1621 /* Find values inside STMT for that we want to measure histograms for
1622 string operations. */
1624 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1631 if (gimple_code (stmt
) != GIMPLE_CALL
)
1633 fndecl
= gimple_call_fndecl (stmt
);
1637 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1640 dest
= gimple_call_arg (stmt
, 0);
1641 blck_size
= gimple_call_arg (stmt
, size_arg
);
1643 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1645 VEC_safe_push (histogram_value
, heap
, *values
,
1646 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1648 VEC_safe_push (histogram_value
, heap
, *values
,
1649 gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1652 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1653 VEC_safe_push (histogram_value
, heap
, *values
,
1654 gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1658 /* Find values inside STMT for that we want to measure histograms and adds
1659 them to list VALUES. */
1662 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1664 if (flag_value_profile_transformations
)
1666 gimple_divmod_values_to_profile (stmt
, values
);
1667 gimple_stringops_values_to_profile (stmt
, values
);
1668 gimple_indirect_call_to_profile (stmt
, values
);
1673 gimple_find_values_to_profile (histogram_values
*values
)
1676 gimple_stmt_iterator gsi
;
1678 histogram_value hist
= NULL
;
1682 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1683 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1685 FOR_EACH_VEC_ELT (histogram_value
, *values
, i
, hist
)
1689 case HIST_TYPE_INTERVAL
:
1690 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1693 case HIST_TYPE_POW2
:
1694 hist
->n_counters
= 2;
1697 case HIST_TYPE_SINGLE_VALUE
:
1698 hist
->n_counters
= 3;
1701 case HIST_TYPE_CONST_DELTA
:
1702 hist
->n_counters
= 4;
1705 case HIST_TYPE_INDIR_CALL
:
1706 hist
->n_counters
= 3;
1709 case HIST_TYPE_AVERAGE
:
1710 hist
->n_counters
= 2;
1714 hist
->n_counters
= 1;
1722 fprintf (dump_file
, "Stmt ");
1723 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1724 dump_histogram_value (dump_file
, hist
);
1729 static struct value_prof_hooks gimple_value_prof_hooks
= {
1730 gimple_find_values_to_profile
,
1731 gimple_value_profile_transformations
1735 gimple_register_value_prof_hooks (void)
1737 gcc_assert (current_ir_type () == IR_GIMPLE
);
1738 value_prof_hooks
= &gimple_value_prof_hooks
;
1741 /* IR-independent entry points. */
1743 find_values_to_profile (histogram_values
*values
)
1745 (value_prof_hooks
->find_values_to_profile
) (values
);
1749 value_profile_transformations (void)
1751 return (value_prof_hooks
->value_profile_transformations
) ();