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
);
705 update_stmt (gsi_stmt (*si
));
710 /* Generate code for transformation 2 (with parent gimple assign STMT and
711 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
712 within roundoff error). This generates the result into a temp and returns
713 the temp; it does not replace or alter the original STMT. */
715 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
717 gimple stmt1
, stmt2
, stmt3
, stmt4
;
718 tree tmp2
, tmp3
, tmpv
;
719 gimple bb1end
, bb2end
, bb3end
;
720 basic_block bb
, bb2
, bb3
, bb4
;
721 tree optype
, op1
, op2
;
722 edge e12
, e13
, e23
, e24
, e34
;
723 gimple_stmt_iterator gsi
;
726 gcc_assert (is_gimple_assign (stmt
)
727 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
729 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
730 op1
= gimple_assign_rhs1 (stmt
);
731 op2
= gimple_assign_rhs2 (stmt
);
733 bb
= gimple_bb (stmt
);
734 gsi
= gsi_for_stmt (stmt
);
736 result
= make_rename_temp (optype
, "PROF");
737 tmpv
= create_tmp_var (optype
, "PROF");
738 tmp2
= make_ssa_name (tmpv
, NULL
);
739 tmp3
= make_ssa_name (tmpv
, NULL
);
740 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
741 build_int_cst (optype
, -1));
742 SSA_NAME_DEF_STMT (tmp2
) = stmt2
;
743 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
744 SSA_NAME_DEF_STMT (tmp3
) = stmt3
;
745 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
746 NULL_TREE
, NULL_TREE
);
747 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
748 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
749 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
752 /* tmp2 == op2-1 inherited from previous block. */
753 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
754 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
757 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
759 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
763 /* Edge e23 connects bb2 to bb3, etc. */
764 e12
= split_block (bb
, bb1end
);
767 e23
= split_block (bb2
, bb2end
);
769 bb3
->count
= all
- count
;
770 e34
= split_block (bb3
, bb3end
);
774 e12
->flags
&= ~EDGE_FALLTHRU
;
775 e12
->flags
|= EDGE_FALSE_VALUE
;
776 e12
->probability
= prob
;
779 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
780 e13
->probability
= REG_BR_PROB_BASE
- prob
;
781 e13
->count
= all
- count
;
785 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
786 e24
->probability
= REG_BR_PROB_BASE
;
789 e34
->probability
= REG_BR_PROB_BASE
;
790 e34
->count
= all
- count
;
795 /* Do transform 2) on INSN if applicable. */
797 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
799 histogram_value histogram
;
801 gcov_type count
, wrong_values
, all
;
802 tree lhs_type
, result
, value
;
806 stmt
= gsi_stmt (*si
);
807 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
810 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
811 if (!INTEGRAL_TYPE_P (lhs_type
))
814 code
= gimple_assign_rhs_code (stmt
);
816 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
819 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
823 value
= histogram
->hvalue
.value
;
824 wrong_values
= histogram
->hvalue
.counters
[0];
825 count
= histogram
->hvalue
.counters
[1];
827 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
829 /* We require that we hit a power of 2 at least half of all evaluations. */
830 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
831 || count
< wrong_values
832 || optimize_bb_for_size_p (gimple_bb (stmt
)))
837 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
838 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
841 /* Compute probability of taking the optimal path. */
842 all
= count
+ wrong_values
;
844 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
848 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
852 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
854 gimple_assign_set_rhs_from_tree (si
, result
);
855 update_stmt (gsi_stmt (*si
));
860 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
861 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
862 supported and this is built into this interface. The probabilities of taking
863 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
864 COUNT2/ALL respectively within roundoff error). This generates the
865 result into a temp and returns the temp; it does not replace or alter
866 the original STMT. */
867 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
870 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
871 gcov_type count1
, gcov_type count2
, gcov_type all
)
873 gimple stmt1
, stmt2
, stmt3
;
875 gimple bb1end
, bb2end
= NULL
, bb3end
;
876 basic_block bb
, bb2
, bb3
, bb4
;
877 tree optype
, op1
, op2
;
878 edge e12
, e23
= 0, e24
, e34
, e14
;
879 gimple_stmt_iterator gsi
;
882 gcc_assert (is_gimple_assign (stmt
)
883 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
885 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
886 op1
= gimple_assign_rhs1 (stmt
);
887 op2
= gimple_assign_rhs2 (stmt
);
889 bb
= gimple_bb (stmt
);
890 gsi
= gsi_for_stmt (stmt
);
892 result
= make_rename_temp (optype
, "PROF");
893 tmp1
= make_ssa_name (create_tmp_var (optype
, "PROF"), NULL
);
894 stmt1
= gimple_build_assign (result
, op1
);
895 stmt2
= gimple_build_assign (tmp1
, op2
);
896 SSA_NAME_DEF_STMT (tmp1
) = stmt2
;
897 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
898 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
899 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
900 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
903 if (ncounts
) /* Assumed to be 0 or 1 */
905 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
906 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
907 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
908 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
913 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
915 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
919 /* Edge e23 connects bb2 to bb3, etc. */
920 /* However block 3 is optional; if it is not there, references
921 to 3 really refer to block 2. */
922 e12
= split_block (bb
, bb1end
);
924 bb2
->count
= all
- count1
;
926 if (ncounts
) /* Assumed to be 0 or 1. */
928 e23
= split_block (bb2
, bb2end
);
930 bb3
->count
= all
- count1
- count2
;
933 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
937 e12
->flags
&= ~EDGE_FALLTHRU
;
938 e12
->flags
|= EDGE_FALSE_VALUE
;
939 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
940 e12
->count
= all
- count1
;
942 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
943 e14
->probability
= prob1
;
946 if (ncounts
) /* Assumed to be 0 or 1. */
948 e23
->flags
&= ~EDGE_FALLTHRU
;
949 e23
->flags
|= EDGE_FALSE_VALUE
;
950 e23
->count
= all
- count1
- count2
;
951 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
953 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
954 e24
->probability
= prob2
;
958 e34
->probability
= REG_BR_PROB_BASE
;
959 e34
->count
= all
- count1
- count2
;
965 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
968 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
970 histogram_value histogram
;
972 gcov_type count
, wrong_values
, all
;
973 tree lhs_type
, result
;
974 gcov_type prob1
, prob2
;
975 unsigned int i
, steps
;
976 gcov_type count1
, count2
;
979 stmt
= gsi_stmt (*si
);
980 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
983 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
984 if (!INTEGRAL_TYPE_P (lhs_type
))
987 code
= gimple_assign_rhs_code (stmt
);
989 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
992 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
998 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
999 all
+= histogram
->hvalue
.counters
[i
];
1001 wrong_values
+= histogram
->hvalue
.counters
[i
];
1002 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1003 steps
= histogram
->hdata
.intvl
.steps
;
1004 all
+= wrong_values
;
1005 count1
= histogram
->hvalue
.counters
[0];
1006 count2
= histogram
->hvalue
.counters
[1];
1008 /* Compute probability of taking the optimal path. */
1009 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1011 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1015 if (flag_profile_correction
&& count1
+ count2
> all
)
1016 all
= count1
+ count2
;
1018 gcc_assert (count1
+ count2
<= all
);
1020 /* We require that we use just subtractions in at least 50% of all
1023 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1025 count
+= histogram
->hvalue
.counters
[i
];
1026 if (count
* 2 >= all
)
1030 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1033 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1036 fprintf (dump_file
, "Mod subtract transformation on insn ");
1037 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1040 /* Compute probability of taking the optimal path(s). */
1043 prob1
= (count1
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1044 prob2
= (count2
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1051 /* In practice, "steps" is always 2. This interface reflects this,
1052 and will need to be changed if "steps" can change. */
1053 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1055 gimple_assign_set_rhs_from_tree (si
, result
);
1056 update_stmt (gsi_stmt (*si
));
1061 static struct cgraph_node
** pid_map
= NULL
;
1063 /* Initialize map of pids (pid -> cgraph node) */
1068 struct cgraph_node
*n
;
1070 if (pid_map
!= NULL
)
1073 pid_map
= XCNEWVEC (struct cgraph_node
*, cgraph_max_pid
);
1075 for (n
= cgraph_nodes
; n
; n
= n
->next
)
1078 pid_map
[n
->pid
] = n
;
1082 /* Return cgraph node for function with pid */
1084 static inline struct cgraph_node
*
1085 find_func_by_pid (int pid
)
1089 return pid_map
[pid
];
1092 /* Do transformation
1094 if (actual_callee_address == address_of_most_common_function/method)
1101 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1102 int prob
, gcov_type count
, gcov_type all
)
1104 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1105 tree tmp0
, tmp1
, tmpv
, tmp
;
1106 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
;
1107 tree optype
= build_pointer_type (void_type_node
);
1108 edge e_cd
, e_ci
, e_di
, e_dj
, e_ij
;
1109 gimple_stmt_iterator gsi
;
1112 cond_bb
= gimple_bb (icall_stmt
);
1113 gsi
= gsi_for_stmt (icall_stmt
);
1115 tmpv
= create_tmp_reg (optype
, "PROF");
1116 tmp0
= make_ssa_name (tmpv
, NULL
);
1117 tmp1
= make_ssa_name (tmpv
, NULL
);
1118 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1119 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1120 SSA_NAME_DEF_STMT (tmp0
) = load_stmt
;
1121 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1123 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1124 current_function_decl
));
1125 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1126 SSA_NAME_DEF_STMT (tmp1
) = load_stmt
;
1127 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1129 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1130 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1132 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1133 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1134 update_stmt (icall_stmt
);
1135 dcall_stmt
= gimple_copy (icall_stmt
);
1136 gimple_call_set_fndecl (dcall_stmt
, direct_call
->decl
);
1137 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1140 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1141 e_cd
= split_block (cond_bb
, cond_stmt
);
1142 dcall_bb
= e_cd
->dest
;
1143 dcall_bb
->count
= count
;
1145 e_di
= split_block (dcall_bb
, dcall_stmt
);
1146 icall_bb
= e_di
->dest
;
1147 icall_bb
->count
= all
- count
;
1149 e_ij
= split_block (icall_bb
, icall_stmt
);
1150 join_bb
= e_ij
->dest
;
1151 join_bb
->count
= all
;
1153 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1154 e_cd
->probability
= prob
;
1155 e_cd
->count
= count
;
1157 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1158 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1159 e_ci
->count
= all
- count
;
1163 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1164 e_dj
->probability
= REG_BR_PROB_BASE
;
1165 e_dj
->count
= count
;
1167 e_ij
->probability
= REG_BR_PROB_BASE
;
1168 e_ij
->count
= all
- count
;
1170 /* Insert PHI node for the call result if necessary. */
1171 if (gimple_call_lhs (icall_stmt
)
1172 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
)
1174 tree result
= gimple_call_lhs (icall_stmt
);
1175 gimple phi
= create_phi_node (result
, join_bb
);
1176 SSA_NAME_DEF_STMT (result
) = phi
;
1177 gimple_call_set_lhs (icall_stmt
,
1178 make_ssa_name (SSA_NAME_VAR (result
), icall_stmt
));
1179 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1180 gimple_call_set_lhs (dcall_stmt
,
1181 make_ssa_name (SSA_NAME_VAR (result
), dcall_stmt
));
1182 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1186 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1189 if (stmt_could_throw_p (dcall_stmt
))
1191 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1192 make_eh_edges (dcall_stmt
);
1195 gcc_assert (stmt_could_throw_p (icall_stmt
));
1196 make_eh_edges (icall_stmt
);
1198 /* The old EH edges are sill on the join BB, purge them. */
1199 gimple_purge_dead_eh_edges (join_bb
);
1206 For every checked indirect/virtual call determine if most common pid of
1207 function/class method has probability more than 50%. If yes modify code of
1212 gimple_ic_transform (gimple stmt
)
1214 histogram_value histogram
;
1215 gcov_type val
, count
, all
, bb_all
;
1219 struct cgraph_node
*direct_call
;
1221 if (gimple_code (stmt
) != GIMPLE_CALL
)
1224 callee
= gimple_call_fn (stmt
);
1226 if (TREE_CODE (callee
) == FUNCTION_DECL
)
1229 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1233 val
= histogram
->hvalue
.counters
[0];
1234 count
= histogram
->hvalue
.counters
[1];
1235 all
= histogram
->hvalue
.counters
[2];
1236 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1238 if (4 * count
<= 3 * all
)
1241 bb_all
= gimple_bb (stmt
)->count
;
1242 /* The order of CHECK_COUNTER calls is important -
1243 since check_counter can correct the third parameter
1244 and we want to make count <= all <= bb_all. */
1245 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1246 || check_counter (stmt
, "ic", &count
, &all
, all
))
1250 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1253 direct_call
= find_func_by_pid ((int)val
);
1255 if (direct_call
== NULL
)
1258 modify
= gimple_ic (stmt
, direct_call
, prob
, count
, all
);
1262 fprintf (dump_file
, "Indirect call -> direct call ");
1263 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1264 fprintf (dump_file
, "=> ");
1265 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1266 fprintf (dump_file
, " transformation on insn ");
1267 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1268 fprintf (dump_file
, " to ");
1269 print_gimple_stmt (dump_file
, modify
, 0, TDF_SLIM
);
1270 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1271 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1277 /* Return true if the stringop CALL with FNDECL shall be profiled.
1278 SIZE_ARG be set to the argument index for the size of the string
1282 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1284 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1286 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1287 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1292 case BUILT_IN_MEMCPY
:
1293 case BUILT_IN_MEMPCPY
:
1295 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1296 INTEGER_TYPE
, VOID_TYPE
);
1297 case BUILT_IN_MEMSET
:
1299 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1300 INTEGER_TYPE
, VOID_TYPE
);
1301 case BUILT_IN_BZERO
:
1303 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1310 /* Convert stringop (..., vcall_size)
1312 if (vcall_size == icall_size)
1313 stringop (..., icall_size);
1315 stringop (..., vcall_size);
1316 assuming we'll propagate a true constant into ICALL_SIZE later. */
1319 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1320 gcov_type count
, gcov_type all
)
1322 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1323 tree tmp0
, tmp1
, tmpv
, vcall_size
, optype
;
1324 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1325 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1326 gimple_stmt_iterator gsi
;
1330 fndecl
= gimple_call_fndecl (vcall_stmt
);
1331 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1334 cond_bb
= gimple_bb (vcall_stmt
);
1335 gsi
= gsi_for_stmt (vcall_stmt
);
1337 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1338 optype
= TREE_TYPE (vcall_size
);
1340 tmpv
= create_tmp_var (optype
, "PROF");
1341 tmp0
= make_ssa_name (tmpv
, NULL
);
1342 tmp1
= make_ssa_name (tmpv
, NULL
);
1343 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1344 SSA_NAME_DEF_STMT (tmp0
) = tmp_stmt
;
1345 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1347 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1348 SSA_NAME_DEF_STMT (tmp1
) = tmp_stmt
;
1349 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1351 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1352 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1354 gimple_set_vdef (vcall_stmt
, NULL
);
1355 gimple_set_vuse (vcall_stmt
, NULL
);
1356 update_stmt (vcall_stmt
);
1357 icall_stmt
= gimple_copy (vcall_stmt
);
1358 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1359 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1362 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1363 e_ci
= split_block (cond_bb
, cond_stmt
);
1364 icall_bb
= e_ci
->dest
;
1365 icall_bb
->count
= count
;
1367 e_iv
= split_block (icall_bb
, icall_stmt
);
1368 vcall_bb
= e_iv
->dest
;
1369 vcall_bb
->count
= all
- count
;
1371 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1372 join_bb
= e_vj
->dest
;
1373 join_bb
->count
= all
;
1375 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1376 e_ci
->probability
= prob
;
1377 e_ci
->count
= count
;
1379 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1380 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1381 e_cv
->count
= all
- count
;
1385 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1386 e_ij
->probability
= REG_BR_PROB_BASE
;
1387 e_ij
->count
= count
;
1389 e_vj
->probability
= REG_BR_PROB_BASE
;
1390 e_vj
->count
= all
- count
;
1392 /* Because these are all string op builtins, they're all nothrow. */
1393 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1394 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1397 /* Find values inside STMT for that we want to measure histograms for
1398 division/modulo optimization. */
1400 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1402 gimple stmt
= gsi_stmt (*gsi
);
1405 enum built_in_function fcode
;
1406 histogram_value histogram
;
1407 gcov_type count
, all
, val
;
1409 unsigned int dest_align
, src_align
;
1414 if (gimple_code (stmt
) != GIMPLE_CALL
)
1416 fndecl
= gimple_call_fndecl (stmt
);
1419 fcode
= DECL_FUNCTION_CODE (fndecl
);
1420 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1423 blck_size
= gimple_call_arg (stmt
, size_arg
);
1424 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1427 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1430 val
= histogram
->hvalue
.counters
[0];
1431 count
= histogram
->hvalue
.counters
[1];
1432 all
= histogram
->hvalue
.counters
[2];
1433 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1434 /* We require that count is at least half of all; this means
1435 that for the transformation to fire the value must be constant
1436 at least 80% of time. */
1437 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1439 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1442 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1445 dest
= gimple_call_arg (stmt
, 0);
1446 dest_align
= get_pointer_alignment (dest
, BIGGEST_ALIGNMENT
);
1449 case BUILT_IN_MEMCPY
:
1450 case BUILT_IN_MEMPCPY
:
1451 src
= gimple_call_arg (stmt
, 1);
1452 src_align
= get_pointer_alignment (src
, BIGGEST_ALIGNMENT
);
1453 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1456 case BUILT_IN_MEMSET
:
1457 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1458 gimple_call_arg (stmt
, 1),
1462 case BUILT_IN_BZERO
:
1463 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1471 tree_val
= build_int_cst_wide (get_gcov_type (),
1472 (unsigned HOST_WIDE_INT
) val
,
1473 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1476 fprintf (dump_file
, "Single value %i stringop transformation on ",
1478 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1480 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1486 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1487 HOST_WIDE_INT
*expected_size
)
1489 histogram_value histogram
;
1490 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1492 *expected_size
= -1;
1493 else if (!histogram
->hvalue
.counters
[1])
1495 *expected_size
= -1;
1496 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1501 size
= ((histogram
->hvalue
.counters
[0]
1502 + histogram
->hvalue
.counters
[1] / 2)
1503 / histogram
->hvalue
.counters
[1]);
1504 /* Even if we can hold bigger value in SIZE, INT_MAX
1505 is safe "infinity" for code generation strategies. */
1508 *expected_size
= size
;
1509 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1511 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1513 *expected_align
= 0;
1514 else if (!histogram
->hvalue
.counters
[0])
1516 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1517 *expected_align
= 0;
1524 count
= histogram
->hvalue
.counters
[0];
1526 while (!(count
& alignment
)
1527 && (alignment
* 2 * BITS_PER_UNIT
))
1529 *expected_align
= alignment
* BITS_PER_UNIT
;
1530 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1534 struct value_prof_hooks
{
1535 /* Find list of values for which we want to measure histograms. */
1536 void (*find_values_to_profile
) (histogram_values
*);
1538 /* Identify and exploit properties of values that are hard to analyze
1539 statically. See value-prof.c for more detail. */
1540 bool (*value_profile_transformations
) (void);
1543 /* Find values inside STMT for that we want to measure histograms for
1544 division/modulo optimization. */
1546 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1548 tree lhs
, divisor
, op0
, type
;
1549 histogram_value hist
;
1551 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1554 lhs
= gimple_assign_lhs (stmt
);
1555 type
= TREE_TYPE (lhs
);
1556 if (!INTEGRAL_TYPE_P (type
))
1559 switch (gimple_assign_rhs_code (stmt
))
1561 case TRUNC_DIV_EXPR
:
1562 case TRUNC_MOD_EXPR
:
1563 divisor
= gimple_assign_rhs2 (stmt
);
1564 op0
= gimple_assign_rhs1 (stmt
);
1566 VEC_reserve (histogram_value
, heap
, *values
, 3);
1568 if (is_gimple_reg (divisor
))
1569 /* Check for the case where the divisor is the same value most
1571 VEC_quick_push (histogram_value
, *values
,
1572 gimple_alloc_histogram_value (cfun
,
1573 HIST_TYPE_SINGLE_VALUE
,
1576 /* For mod, check whether it is not often a noop (or replaceable by
1577 a few subtractions). */
1578 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1579 && TYPE_UNSIGNED (type
))
1582 /* Check for a special case where the divisor is power of 2. */
1583 VEC_quick_push (histogram_value
, *values
,
1584 gimple_alloc_histogram_value (cfun
, HIST_TYPE_POW2
,
1587 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1588 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1590 hist
->hdata
.intvl
.int_start
= 0;
1591 hist
->hdata
.intvl
.steps
= 2;
1592 VEC_quick_push (histogram_value
, *values
, hist
);
1601 /* Find calls inside STMT for that we want to measure histograms for
1602 indirect/virtual call optimization. */
1605 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1609 if (gimple_code (stmt
) != GIMPLE_CALL
1610 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1613 callee
= gimple_call_fn (stmt
);
1615 VEC_reserve (histogram_value
, heap
, *values
, 3);
1617 VEC_quick_push (histogram_value
, *values
,
1618 gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1624 /* Find values inside STMT for that we want to measure histograms for
1625 string operations. */
1627 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1634 if (gimple_code (stmt
) != GIMPLE_CALL
)
1636 fndecl
= gimple_call_fndecl (stmt
);
1640 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1643 dest
= gimple_call_arg (stmt
, 0);
1644 blck_size
= gimple_call_arg (stmt
, size_arg
);
1646 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1648 VEC_safe_push (histogram_value
, heap
, *values
,
1649 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1651 VEC_safe_push (histogram_value
, heap
, *values
,
1652 gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1655 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1656 VEC_safe_push (histogram_value
, heap
, *values
,
1657 gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1661 /* Find values inside STMT for that we want to measure histograms and adds
1662 them to list VALUES. */
1665 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1667 if (flag_value_profile_transformations
)
1669 gimple_divmod_values_to_profile (stmt
, values
);
1670 gimple_stringops_values_to_profile (stmt
, values
);
1671 gimple_indirect_call_to_profile (stmt
, values
);
1676 gimple_find_values_to_profile (histogram_values
*values
)
1679 gimple_stmt_iterator gsi
;
1681 histogram_value hist
= NULL
;
1685 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1686 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1688 FOR_EACH_VEC_ELT (histogram_value
, *values
, i
, hist
)
1692 case HIST_TYPE_INTERVAL
:
1693 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1696 case HIST_TYPE_POW2
:
1697 hist
->n_counters
= 2;
1700 case HIST_TYPE_SINGLE_VALUE
:
1701 hist
->n_counters
= 3;
1704 case HIST_TYPE_CONST_DELTA
:
1705 hist
->n_counters
= 4;
1708 case HIST_TYPE_INDIR_CALL
:
1709 hist
->n_counters
= 3;
1712 case HIST_TYPE_AVERAGE
:
1713 hist
->n_counters
= 2;
1717 hist
->n_counters
= 1;
1725 fprintf (dump_file
, "Stmt ");
1726 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1727 dump_histogram_value (dump_file
, hist
);
1732 static struct value_prof_hooks gimple_value_prof_hooks
= {
1733 gimple_find_values_to_profile
,
1734 gimple_value_profile_transformations
1738 gimple_register_value_prof_hooks (void)
1740 gcc_assert (current_ir_type () == IR_GIMPLE
);
1741 value_prof_hooks
= &gimple_value_prof_hooks
;
1744 /* IR-independent entry points. */
1746 find_values_to_profile (histogram_values
*values
)
1748 (value_prof_hooks
->find_values_to_profile
) (values
);
1752 value_profile_transformations (void)
1754 return (value_prof_hooks
->value_profile_transformations
) ();