1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "value-prof.h"
31 #include "insn-config.h"
36 #include "tree-flow.h"
37 #include "tree-flow-inline.h"
38 #include "diagnostic.h"
39 #include "tree-pretty-print.h"
40 #include "gimple-pretty-print.h"
46 #include "tree-pass.h"
47 #include "pointer-set.h"
50 /* In this file value profile based optimizations are placed. Currently the
51 following optimizations are implemented (for more detailed descriptions
52 see comments at value_profile_transformations):
54 1) Division/modulo specialization. Provided that we can determine that the
55 operands of the division have some special properties, we may use it to
56 produce more effective code.
57 2) Speculative prefetching. If we are able to determine that the difference
58 between addresses accessed by a memory reference is usually constant, we
59 may add the prefetch instructions.
60 FIXME: This transformation was removed together with RTL based value
63 3) Indirect/virtual call specialization. If we can determine most
64 common function callee in indirect/virtual call. We can use this
65 information to improve code effectiveness (especially info for
68 Every such optimization should add its requirements for profiled values to
69 insn_values_to_profile function. This function is called from branch_prob
70 in profile.c and the requested values are instrumented by it in the first
71 compilation with -fprofile-arcs. The optimization may then read the
72 gathered data in the second compilation with -fbranch-probabilities.
74 The measured data is pointed to from the histograms
75 field of the statement annotation of the instrumented insns. It is
76 kept as a linked list of struct histogram_value_t's, which contain the
77 same information as above. */
80 static tree
gimple_divmod_fixed_value (gimple
, tree
, int, gcov_type
, gcov_type
);
81 static tree
gimple_mod_pow2 (gimple
, int, gcov_type
, gcov_type
);
82 static tree
gimple_mod_subtract (gimple
, int, int, int, gcov_type
, gcov_type
,
84 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*);
85 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator
*);
86 static bool gimple_mod_subtract_transform (gimple_stmt_iterator
*);
87 static bool gimple_stringops_transform (gimple_stmt_iterator
*);
88 static bool gimple_ic_transform (gimple
);
90 /* Allocate histogram value. */
92 static histogram_value
93 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
94 enum hist_type type
, gimple stmt
, tree value
)
96 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
97 hist
->hvalue
.value
= value
;
98 hist
->hvalue
.stmt
= stmt
;
103 /* Hash value for histogram. */
106 histogram_hash (const void *x
)
108 return htab_hash_pointer (((const_histogram_value
)x
)->hvalue
.stmt
);
111 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
114 histogram_eq (const void *x
, const void *y
)
116 return ((const_histogram_value
) x
)->hvalue
.stmt
== (const_gimple
) y
;
119 /* Set histogram for STMT. */
122 set_histogram_value (struct function
*fun
, gimple stmt
, histogram_value hist
)
125 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
127 if (!VALUE_HISTOGRAMS (fun
))
128 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
130 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
131 htab_hash_pointer (stmt
),
132 hist
? INSERT
: NO_INSERT
);
136 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
142 /* Get histogram list for STMT. */
145 gimple_histogram_value (struct function
*fun
, gimple stmt
)
147 if (!VALUE_HISTOGRAMS (fun
))
149 return (histogram_value
) htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
150 htab_hash_pointer (stmt
));
153 /* Add histogram for STMT. */
156 gimple_add_histogram_value (struct function
*fun
, gimple stmt
,
157 histogram_value hist
)
159 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
160 set_histogram_value (fun
, stmt
, hist
);
164 /* Remove histogram HIST from STMT's histogram list. */
167 gimple_remove_histogram_value (struct function
*fun
, gimple stmt
,
168 histogram_value hist
)
170 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
173 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
177 while (hist2
->hvalue
.next
!= hist
)
178 hist2
= hist2
->hvalue
.next
;
179 hist2
->hvalue
.next
= hist
->hvalue
.next
;
181 free (hist
->hvalue
.counters
);
182 #ifdef ENABLE_CHECKING
183 memset (hist
, 0xab, sizeof (*hist
));
189 /* Lookup histogram of type TYPE in the STMT. */
192 gimple_histogram_value_of_type (struct function
*fun
, gimple stmt
,
195 histogram_value hist
;
196 for (hist
= gimple_histogram_value (fun
, stmt
); hist
;
197 hist
= hist
->hvalue
.next
)
198 if (hist
->type
== type
)
203 /* Dump information about HIST to DUMP_FILE. */
206 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
210 case HIST_TYPE_INTERVAL
:
211 fprintf (dump_file
, "Interval counter range %d -- %d",
212 hist
->hdata
.intvl
.int_start
,
213 (hist
->hdata
.intvl
.int_start
214 + hist
->hdata
.intvl
.steps
- 1));
215 if (hist
->hvalue
.counters
)
218 fprintf(dump_file
, " [");
219 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
220 fprintf (dump_file
, " %d:"HOST_WIDEST_INT_PRINT_DEC
,
221 hist
->hdata
.intvl
.int_start
+ i
,
222 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
223 fprintf (dump_file
, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC
,
224 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
226 fprintf (dump_file
, ".\n");
230 fprintf (dump_file
, "Pow2 counter ");
231 if (hist
->hvalue
.counters
)
233 fprintf (dump_file
, "pow2:"HOST_WIDEST_INT_PRINT_DEC
234 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC
,
235 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
236 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
238 fprintf (dump_file
, ".\n");
241 case HIST_TYPE_SINGLE_VALUE
:
242 fprintf (dump_file
, "Single value ");
243 if (hist
->hvalue
.counters
)
245 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
246 " match:"HOST_WIDEST_INT_PRINT_DEC
247 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
248 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
249 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
250 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
252 fprintf (dump_file
, ".\n");
255 case HIST_TYPE_AVERAGE
:
256 fprintf (dump_file
, "Average value ");
257 if (hist
->hvalue
.counters
)
259 fprintf (dump_file
, "sum:"HOST_WIDEST_INT_PRINT_DEC
260 " times:"HOST_WIDEST_INT_PRINT_DEC
,
261 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
262 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
264 fprintf (dump_file
, ".\n");
268 fprintf (dump_file
, "IOR value ");
269 if (hist
->hvalue
.counters
)
271 fprintf (dump_file
, "ior:"HOST_WIDEST_INT_PRINT_DEC
,
272 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0]);
274 fprintf (dump_file
, ".\n");
277 case HIST_TYPE_CONST_DELTA
:
278 fprintf (dump_file
, "Constant delta ");
279 if (hist
->hvalue
.counters
)
281 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
282 " match:"HOST_WIDEST_INT_PRINT_DEC
283 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
284 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
285 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
286 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
288 fprintf (dump_file
, ".\n");
290 case HIST_TYPE_INDIR_CALL
:
291 fprintf (dump_file
, "Indirect call ");
292 if (hist
->hvalue
.counters
)
294 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
295 " match:"HOST_WIDEST_INT_PRINT_DEC
296 " all:"HOST_WIDEST_INT_PRINT_DEC
,
297 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
298 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
299 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
301 fprintf (dump_file
, ".\n");
306 /* Dump all histograms attached to STMT to DUMP_FILE. */
309 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, gimple stmt
)
311 histogram_value hist
;
312 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
313 dump_histogram_value (dump_file
, hist
);
316 /* Remove all histograms associated with STMT. */
319 gimple_remove_stmt_histograms (struct function
*fun
, gimple stmt
)
322 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
323 gimple_remove_histogram_value (fun
, stmt
, val
);
326 /* Duplicate all histograms associates with OSTMT to STMT. */
329 gimple_duplicate_stmt_histograms (struct function
*fun
, gimple stmt
,
330 struct function
*ofun
, gimple ostmt
)
333 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
335 histogram_value new_val
= gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
336 memcpy (new_val
, val
, sizeof (*val
));
337 new_val
->hvalue
.stmt
= stmt
;
338 new_val
->hvalue
.counters
= XNEWVAR (gcov_type
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
339 memcpy (new_val
->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new_val
->hvalue
.counters
) * new_val
->n_counters
);
340 gimple_add_histogram_value (fun
, stmt
, new_val
);
345 /* Move all histograms associated with OSTMT to STMT. */
348 gimple_move_stmt_histograms (struct function
*fun
, gimple stmt
, gimple ostmt
)
350 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
353 /* The following three statements can't be reordered,
354 because histogram hashtab relies on stmt field value
355 for finding the exact slot. */
356 set_histogram_value (fun
, ostmt
, NULL
);
357 for (; val
!= NULL
; val
= val
->hvalue
.next
)
358 val
->hvalue
.stmt
= stmt
;
359 set_histogram_value (fun
, stmt
, val
);
363 static bool error_found
= false;
365 /* Helper function for verify_histograms. For each histogram reachable via htab
366 walk verify that it was reached via statement walk. */
369 visit_hist (void **slot
, void *data
)
371 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
372 histogram_value hist
= *(histogram_value
*) slot
;
373 if (!pointer_set_contains (visited
, hist
))
375 error ("dead histogram");
376 dump_histogram_value (stderr
, hist
);
377 debug_gimple_stmt (hist
->hvalue
.stmt
);
384 /* Verify sanity of the histograms. */
387 verify_histograms (void)
390 gimple_stmt_iterator gsi
;
391 histogram_value hist
;
392 struct pointer_set_t
*visited_hists
;
395 visited_hists
= pointer_set_create ();
397 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
399 gimple stmt
= gsi_stmt (gsi
);
401 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
;
402 hist
= hist
->hvalue
.next
)
404 if (hist
->hvalue
.stmt
!= stmt
)
406 error ("Histogram value statement does not correspond to "
407 "the statement it is associated with");
408 debug_gimple_stmt (stmt
);
409 dump_histogram_value (stderr
, hist
);
412 pointer_set_insert (visited_hists
, hist
);
415 if (VALUE_HISTOGRAMS (cfun
))
416 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, visited_hists
);
417 pointer_set_destroy (visited_hists
);
419 internal_error ("verify_histograms failed");
422 /* Helper function for verify_histograms. For each histogram reachable via htab
423 walk verify that it was reached via statement walk. */
426 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
428 histogram_value hist
= *(histogram_value
*) slot
;
429 free (hist
->hvalue
.counters
);
430 #ifdef ENABLE_CHECKING
431 memset (hist
, 0xab, sizeof (*hist
));
438 free_histograms (void)
440 if (VALUE_HISTOGRAMS (cfun
))
442 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
443 htab_delete (VALUE_HISTOGRAMS (cfun
));
444 VALUE_HISTOGRAMS (cfun
) = NULL
;
449 /* The overall number of invocations of the counter should match
450 execution count of basic block. Report it as error rather than
451 internal error as it might mean that user has misused the profile
455 check_counter (gimple stmt
, const char * name
,
456 gcov_type
*count
, gcov_type
*all
, gcov_type bb_count
)
458 if (*all
!= bb_count
|| *count
> *all
)
461 locus
= (stmt
!= NULL
)
462 ? gimple_location (stmt
)
463 : DECL_SOURCE_LOCATION (current_function_decl
);
464 if (flag_profile_correction
)
466 inform (locus
, "correcting inconsistent value profile: "
467 "%s profiler overall count (%d) does not match BB count "
468 "(%d)", name
, (int)*all
, (int)bb_count
);
476 error_at (locus
, "corrupted value profile: %s "
477 "profile counter (%d out of %d) inconsistent with "
478 "basic-block count (%d)",
491 /* GIMPLE based transformations. */
494 gimple_value_profile_transformations (void)
497 gimple_stmt_iterator gsi
;
498 bool changed
= false;
502 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
504 gimple stmt
= gsi_stmt (gsi
);
505 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
511 fprintf (dump_file
, "Trying transformations on stmt ");
512 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
513 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
516 /* Transformations: */
517 /* The order of things in this conditional controls which
518 transformation is used when more than one is applicable. */
519 /* It is expected that any code added by the transformations
520 will be added before the current statement, and that the
521 current statement remain valid (although possibly
522 modified) upon return. */
523 if (flag_value_profile_transformations
524 && (gimple_mod_subtract_transform (&gsi
)
525 || gimple_divmod_fixed_value_transform (&gsi
)
526 || gimple_mod_pow2_value_transform (&gsi
)
527 || gimple_stringops_transform (&gsi
)
528 || gimple_ic_transform (stmt
)))
530 stmt
= gsi_stmt (gsi
);
532 /* Original statement may no longer be in the same block. */
533 if (bb
!= gimple_bb (stmt
))
535 bb
= gimple_bb (stmt
);
536 gsi
= gsi_for_stmt (stmt
);
551 /* Generate code for transformation 1 (with parent gimple assignment
552 STMT and probability of taking the optimal path PROB, which is
553 equivalent to COUNT/ALL within roundoff error). This generates the
554 result into a temp and returns the temp; it does not replace or
555 alter the original STMT. */
558 gimple_divmod_fixed_value (gimple stmt
, tree value
, int prob
, gcov_type count
,
561 gimple stmt1
, stmt2
, stmt3
;
562 tree tmp0
, tmp1
, tmp2
, tmpv
;
563 gimple bb1end
, bb2end
, bb3end
;
564 basic_block bb
, bb2
, bb3
, bb4
;
565 tree optype
, op1
, op2
;
566 edge e12
, e13
, e23
, e24
, e34
;
567 gimple_stmt_iterator gsi
;
569 gcc_assert (is_gimple_assign (stmt
)
570 && (gimple_assign_rhs_code (stmt
) == TRUNC_DIV_EXPR
571 || gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
));
573 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
574 op1
= gimple_assign_rhs1 (stmt
);
575 op2
= gimple_assign_rhs2 (stmt
);
577 bb
= gimple_bb (stmt
);
578 gsi
= gsi_for_stmt (stmt
);
580 tmpv
= create_tmp_reg (optype
, "PROF");
581 tmp0
= make_ssa_name (tmpv
, NULL
);
582 tmp1
= make_ssa_name (tmpv
, NULL
);
583 stmt1
= gimple_build_assign (tmp0
, fold_convert (optype
, value
));
584 SSA_NAME_DEF_STMT (tmp0
) = stmt1
;
585 stmt2
= gimple_build_assign (tmp1
, op2
);
586 SSA_NAME_DEF_STMT (tmp1
) = stmt2
;
587 stmt3
= gimple_build_cond (NE_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
588 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
589 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
590 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
593 tmp2
= make_rename_temp (optype
, "PROF");
594 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
596 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
599 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), tmp2
,
601 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
605 /* Edge e23 connects bb2 to bb3, etc. */
606 e12
= split_block (bb
, bb1end
);
609 e23
= split_block (bb2
, bb2end
);
611 bb3
->count
= all
- count
;
612 e34
= split_block (bb3
, bb3end
);
616 e12
->flags
&= ~EDGE_FALLTHRU
;
617 e12
->flags
|= EDGE_FALSE_VALUE
;
618 e12
->probability
= prob
;
621 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
622 e13
->probability
= REG_BR_PROB_BASE
- prob
;
623 e13
->count
= all
- count
;
627 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
628 e24
->probability
= REG_BR_PROB_BASE
;
631 e34
->probability
= REG_BR_PROB_BASE
;
632 e34
->count
= all
- count
;
638 /* Do transform 1) on INSN if applicable. */
641 gimple_divmod_fixed_value_transform (gimple_stmt_iterator
*si
)
643 histogram_value histogram
;
645 gcov_type val
, count
, all
;
646 tree result
, value
, tree_val
;
650 stmt
= gsi_stmt (*si
);
651 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
654 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt
))))
657 code
= gimple_assign_rhs_code (stmt
);
659 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
662 histogram
= gimple_histogram_value_of_type (cfun
, stmt
,
663 HIST_TYPE_SINGLE_VALUE
);
667 value
= histogram
->hvalue
.value
;
668 val
= histogram
->hvalue
.counters
[0];
669 count
= histogram
->hvalue
.counters
[1];
670 all
= histogram
->hvalue
.counters
[2];
671 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
673 /* We require that count is at least half of all; this means
674 that for the transformation to fire the value must be constant
675 at least 50% of time (and 75% gives the guarantee of usage). */
676 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
678 || optimize_bb_for_size_p (gimple_bb (stmt
)))
681 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
684 /* Compute probability of taking the optimal path. */
686 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
690 tree_val
= build_int_cst_wide (get_gcov_type (),
691 (unsigned HOST_WIDE_INT
) val
,
692 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
693 result
= gimple_divmod_fixed_value (stmt
, tree_val
, prob
, count
, all
);
697 fprintf (dump_file
, "Div/mod by constant ");
698 print_generic_expr (dump_file
, value
, TDF_SLIM
);
699 fprintf (dump_file
, "=");
700 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
701 fprintf (dump_file
, " transformation on insn ");
702 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
705 gimple_assign_set_rhs_from_tree (si
, result
);
706 update_stmt (gsi_stmt (*si
));
711 /* Generate code for transformation 2 (with parent gimple assign STMT and
712 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
713 within roundoff error). This generates the result into a temp and returns
714 the temp; it does not replace or alter the original STMT. */
716 gimple_mod_pow2 (gimple stmt
, int prob
, gcov_type count
, gcov_type all
)
718 gimple stmt1
, stmt2
, stmt3
, stmt4
;
719 tree tmp2
, tmp3
, tmpv
;
720 gimple bb1end
, bb2end
, bb3end
;
721 basic_block bb
, bb2
, bb3
, bb4
;
722 tree optype
, op1
, op2
;
723 edge e12
, e13
, e23
, e24
, e34
;
724 gimple_stmt_iterator gsi
;
727 gcc_assert (is_gimple_assign (stmt
)
728 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
730 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
731 op1
= gimple_assign_rhs1 (stmt
);
732 op2
= gimple_assign_rhs2 (stmt
);
734 bb
= gimple_bb (stmt
);
735 gsi
= gsi_for_stmt (stmt
);
737 result
= make_rename_temp (optype
, "PROF");
738 tmpv
= create_tmp_var (optype
, "PROF");
739 tmp2
= make_ssa_name (tmpv
, NULL
);
740 tmp3
= make_ssa_name (tmpv
, NULL
);
741 stmt2
= gimple_build_assign_with_ops (PLUS_EXPR
, tmp2
, op2
,
742 build_int_cst (optype
, -1));
743 SSA_NAME_DEF_STMT (tmp2
) = stmt2
;
744 stmt3
= gimple_build_assign_with_ops (BIT_AND_EXPR
, tmp3
, tmp2
, op2
);
745 SSA_NAME_DEF_STMT (tmp3
) = stmt3
;
746 stmt4
= gimple_build_cond (NE_EXPR
, tmp3
, build_int_cst (optype
, 0),
747 NULL_TREE
, NULL_TREE
);
748 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
749 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
750 gsi_insert_before (&gsi
, stmt4
, GSI_SAME_STMT
);
753 /* tmp2 == op2-1 inherited from previous block. */
754 stmt1
= gimple_build_assign_with_ops (BIT_AND_EXPR
, result
, op1
, tmp2
);
755 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
758 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
760 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
764 /* Edge e23 connects bb2 to bb3, etc. */
765 e12
= split_block (bb
, bb1end
);
768 e23
= split_block (bb2
, bb2end
);
770 bb3
->count
= all
- count
;
771 e34
= split_block (bb3
, bb3end
);
775 e12
->flags
&= ~EDGE_FALLTHRU
;
776 e12
->flags
|= EDGE_FALSE_VALUE
;
777 e12
->probability
= prob
;
780 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
781 e13
->probability
= REG_BR_PROB_BASE
- prob
;
782 e13
->count
= all
- count
;
786 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
787 e24
->probability
= REG_BR_PROB_BASE
;
790 e34
->probability
= REG_BR_PROB_BASE
;
791 e34
->count
= all
- count
;
796 /* Do transform 2) on INSN if applicable. */
798 gimple_mod_pow2_value_transform (gimple_stmt_iterator
*si
)
800 histogram_value histogram
;
802 gcov_type count
, wrong_values
, all
;
803 tree lhs_type
, result
, value
;
807 stmt
= gsi_stmt (*si
);
808 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
811 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
812 if (!INTEGRAL_TYPE_P (lhs_type
))
815 code
= gimple_assign_rhs_code (stmt
);
817 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
820 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
824 value
= histogram
->hvalue
.value
;
825 wrong_values
= histogram
->hvalue
.counters
[0];
826 count
= histogram
->hvalue
.counters
[1];
828 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
830 /* We require that we hit a power of 2 at least half of all evaluations. */
831 if (simple_cst_equal (gimple_assign_rhs2 (stmt
), value
) != 1
832 || count
< wrong_values
833 || optimize_bb_for_size_p (gimple_bb (stmt
)))
838 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
839 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
842 /* Compute probability of taking the optimal path. */
843 all
= count
+ wrong_values
;
845 if (check_counter (stmt
, "pow2", &count
, &all
, gimple_bb (stmt
)->count
))
849 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
853 result
= gimple_mod_pow2 (stmt
, prob
, count
, all
);
855 gimple_assign_set_rhs_from_tree (si
, result
);
856 update_stmt (gsi_stmt (*si
));
861 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
862 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
863 supported and this is built into this interface. The probabilities of taking
864 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
865 COUNT2/ALL respectively within roundoff error). This generates the
866 result into a temp and returns the temp; it does not replace or alter
867 the original STMT. */
868 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
871 gimple_mod_subtract (gimple stmt
, int prob1
, int prob2
, int ncounts
,
872 gcov_type count1
, gcov_type count2
, gcov_type all
)
874 gimple stmt1
, stmt2
, stmt3
;
876 gimple bb1end
, bb2end
= NULL
, bb3end
;
877 basic_block bb
, bb2
, bb3
, bb4
;
878 tree optype
, op1
, op2
;
879 edge e12
, e23
= 0, e24
, e34
, e14
;
880 gimple_stmt_iterator gsi
;
883 gcc_assert (is_gimple_assign (stmt
)
884 && gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
);
886 optype
= TREE_TYPE (gimple_assign_lhs (stmt
));
887 op1
= gimple_assign_rhs1 (stmt
);
888 op2
= gimple_assign_rhs2 (stmt
);
890 bb
= gimple_bb (stmt
);
891 gsi
= gsi_for_stmt (stmt
);
893 result
= make_rename_temp (optype
, "PROF");
894 tmp1
= make_ssa_name (create_tmp_var (optype
, "PROF"), NULL
);
895 stmt1
= gimple_build_assign (result
, op1
);
896 stmt2
= gimple_build_assign (tmp1
, op2
);
897 SSA_NAME_DEF_STMT (tmp1
) = stmt2
;
898 stmt3
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
899 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
900 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
901 gsi_insert_before (&gsi
, stmt3
, GSI_SAME_STMT
);
904 if (ncounts
) /* Assumed to be 0 or 1 */
906 stmt1
= gimple_build_assign_with_ops (MINUS_EXPR
, result
, result
, tmp1
);
907 stmt2
= gimple_build_cond (LT_EXPR
, result
, tmp1
, NULL_TREE
, NULL_TREE
);
908 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
909 gsi_insert_before (&gsi
, stmt2
, GSI_SAME_STMT
);
914 stmt1
= gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt
), result
,
916 gsi_insert_before (&gsi
, stmt1
, GSI_SAME_STMT
);
920 /* Edge e23 connects bb2 to bb3, etc. */
921 /* However block 3 is optional; if it is not there, references
922 to 3 really refer to block 2. */
923 e12
= split_block (bb
, bb1end
);
925 bb2
->count
= all
- count1
;
927 if (ncounts
) /* Assumed to be 0 or 1. */
929 e23
= split_block (bb2
, bb2end
);
931 bb3
->count
= all
- count1
- count2
;
934 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
938 e12
->flags
&= ~EDGE_FALLTHRU
;
939 e12
->flags
|= EDGE_FALSE_VALUE
;
940 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
941 e12
->count
= all
- count1
;
943 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
944 e14
->probability
= prob1
;
947 if (ncounts
) /* Assumed to be 0 or 1. */
949 e23
->flags
&= ~EDGE_FALLTHRU
;
950 e23
->flags
|= EDGE_FALSE_VALUE
;
951 e23
->count
= all
- count1
- count2
;
952 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
954 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
955 e24
->probability
= prob2
;
959 e34
->probability
= REG_BR_PROB_BASE
;
960 e34
->count
= all
- count1
- count2
;
966 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
969 gimple_mod_subtract_transform (gimple_stmt_iterator
*si
)
971 histogram_value histogram
;
973 gcov_type count
, wrong_values
, all
;
974 tree lhs_type
, result
;
975 gcov_type prob1
, prob2
;
976 unsigned int i
, steps
;
977 gcov_type count1
, count2
;
980 stmt
= gsi_stmt (*si
);
981 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
984 lhs_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
985 if (!INTEGRAL_TYPE_P (lhs_type
))
988 code
= gimple_assign_rhs_code (stmt
);
990 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (lhs_type
))
993 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
999 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1000 all
+= histogram
->hvalue
.counters
[i
];
1002 wrong_values
+= histogram
->hvalue
.counters
[i
];
1003 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
1004 steps
= histogram
->hdata
.intvl
.steps
;
1005 all
+= wrong_values
;
1006 count1
= histogram
->hvalue
.counters
[0];
1007 count2
= histogram
->hvalue
.counters
[1];
1009 /* Compute probability of taking the optimal path. */
1010 if (check_counter (stmt
, "interval", &count1
, &all
, gimple_bb (stmt
)->count
))
1012 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1016 if (flag_profile_correction
&& count1
+ count2
> all
)
1017 all
= count1
+ count2
;
1019 gcc_assert (count1
+ count2
<= all
);
1021 /* We require that we use just subtractions in at least 50% of all
1024 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1026 count
+= histogram
->hvalue
.counters
[i
];
1027 if (count
* 2 >= all
)
1031 || optimize_bb_for_size_p (gimple_bb (stmt
)))
1034 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1037 fprintf (dump_file
, "Mod subtract transformation on insn ");
1038 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1041 /* Compute probability of taking the optimal path(s). */
1044 prob1
= (count1
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1045 prob2
= (count2
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1052 /* In practice, "steps" is always 2. This interface reflects this,
1053 and will need to be changed if "steps" can change. */
1054 result
= gimple_mod_subtract (stmt
, prob1
, prob2
, i
, count1
, count2
, all
);
1056 gimple_assign_set_rhs_from_tree (si
, result
);
1057 update_stmt (gsi_stmt (*si
));
1062 static VEC(cgraph_node_ptr
, heap
) *cgraph_node_map
= NULL
;
1064 /* Initialize map from FUNCDEF_NO to CGRAPH_NODE. */
1067 init_node_map (void)
1069 struct cgraph_node
*n
;
1071 if (get_last_funcdef_no ())
1072 VEC_safe_grow_cleared (cgraph_node_ptr
, heap
,
1073 cgraph_node_map
, get_last_funcdef_no ());
1075 FOR_EACH_FUNCTION (n
)
1077 if (DECL_STRUCT_FUNCTION (n
->symbol
.decl
))
1078 VEC_replace (cgraph_node_ptr
, cgraph_node_map
,
1079 DECL_STRUCT_FUNCTION (n
->symbol
.decl
)->funcdef_no
, n
);
1083 /* Delete the CGRAPH_NODE_MAP. */
1088 VEC_free (cgraph_node_ptr
, heap
, cgraph_node_map
);
1089 cgraph_node_map
= NULL
;
1092 /* Return cgraph node for function with pid */
1094 static inline struct cgraph_node
*
1095 find_func_by_funcdef_no (int func_id
)
1097 int max_id
= get_last_funcdef_no ();
1098 if (func_id
>= max_id
|| VEC_index (cgraph_node_ptr
,
1102 if (flag_profile_correction
)
1103 inform (DECL_SOURCE_LOCATION (current_function_decl
),
1104 "Inconsistent profile: indirect call target (%d) does not exist", func_id
);
1106 error ("Inconsistent profile: indirect call target (%d) does not exist", func_id
);
1111 return VEC_index (cgraph_node_ptr
, cgraph_node_map
, func_id
);
1114 /* Perform sanity check on the indirect call target. Due to race conditions,
1115 false function target may be attributed to an indirect call site. If the
1116 call expression type mismatches with the target function's type, expand_call
1117 may ICE. Here we only do very minimal sanity check just to make compiler happy.
1118 Returns true if TARGET is considered ok for call CALL_STMT. */
1121 check_ic_target (gimple call_stmt
, struct cgraph_node
*target
)
1124 if (gimple_check_call_matching_types (call_stmt
, target
->symbol
.decl
))
1127 locus
= gimple_location (call_stmt
);
1128 inform (locus
, "Skipping target %s with mismatching types for icall ",
1129 cgraph_node_name (target
));
1133 /* Do transformation
1135 if (actual_callee_address == address_of_most_common_function/method)
1142 gimple_ic (gimple icall_stmt
, struct cgraph_node
*direct_call
,
1143 int prob
, gcov_type count
, gcov_type all
)
1145 gimple dcall_stmt
, load_stmt
, cond_stmt
;
1146 tree tmp0
, tmp1
, tmpv
, tmp
;
1147 basic_block cond_bb
, dcall_bb
, icall_bb
, join_bb
= NULL
;
1148 tree optype
= build_pointer_type (void_type_node
);
1149 edge e_cd
, e_ci
, e_di
, e_dj
= NULL
, e_ij
;
1150 gimple_stmt_iterator gsi
;
1153 cond_bb
= gimple_bb (icall_stmt
);
1154 gsi
= gsi_for_stmt (icall_stmt
);
1156 tmpv
= create_tmp_reg (optype
, "PROF");
1157 tmp0
= make_ssa_name (tmpv
, NULL
);
1158 tmp1
= make_ssa_name (tmpv
, NULL
);
1159 tmp
= unshare_expr (gimple_call_fn (icall_stmt
));
1160 load_stmt
= gimple_build_assign (tmp0
, tmp
);
1161 SSA_NAME_DEF_STMT (tmp0
) = load_stmt
;
1162 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1164 tmp
= fold_convert (optype
, build_addr (direct_call
->symbol
.decl
,
1165 current_function_decl
));
1166 load_stmt
= gimple_build_assign (tmp1
, tmp
);
1167 SSA_NAME_DEF_STMT (tmp1
) = load_stmt
;
1168 gsi_insert_before (&gsi
, load_stmt
, GSI_SAME_STMT
);
1170 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1171 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1173 gimple_set_vdef (icall_stmt
, NULL_TREE
);
1174 gimple_set_vuse (icall_stmt
, NULL_TREE
);
1175 update_stmt (icall_stmt
);
1176 dcall_stmt
= gimple_copy (icall_stmt
);
1177 gimple_call_set_fndecl (dcall_stmt
, direct_call
->symbol
.decl
);
1178 dflags
= flags_from_decl_or_type (direct_call
->symbol
.decl
);
1179 if ((dflags
& ECF_NORETURN
) != 0)
1180 gimple_call_set_lhs (dcall_stmt
, NULL_TREE
);
1181 gsi_insert_before (&gsi
, dcall_stmt
, GSI_SAME_STMT
);
1184 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1185 e_cd
= split_block (cond_bb
, cond_stmt
);
1186 dcall_bb
= e_cd
->dest
;
1187 dcall_bb
->count
= count
;
1189 e_di
= split_block (dcall_bb
, dcall_stmt
);
1190 icall_bb
= e_di
->dest
;
1191 icall_bb
->count
= all
- count
;
1193 /* Do not disturb existing EH edges from the indirect call. */
1194 if (!stmt_ends_bb_p (icall_stmt
))
1195 e_ij
= split_block (icall_bb
, icall_stmt
);
1198 e_ij
= find_fallthru_edge (icall_bb
->succs
);
1199 /* The indirect call might be noreturn. */
1202 e_ij
->probability
= REG_BR_PROB_BASE
;
1203 e_ij
->count
= all
- count
;
1204 e_ij
= single_pred_edge (split_edge (e_ij
));
1209 join_bb
= e_ij
->dest
;
1210 join_bb
->count
= all
;
1213 e_cd
->flags
= (e_cd
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1214 e_cd
->probability
= prob
;
1215 e_cd
->count
= count
;
1217 e_ci
= make_edge (cond_bb
, icall_bb
, EDGE_FALSE_VALUE
);
1218 e_ci
->probability
= REG_BR_PROB_BASE
- prob
;
1219 e_ci
->count
= all
- count
;
1225 if ((dflags
& ECF_NORETURN
) != 0)
1229 e_dj
= make_edge (dcall_bb
, join_bb
, EDGE_FALLTHRU
);
1230 e_dj
->probability
= REG_BR_PROB_BASE
;
1231 e_dj
->count
= count
;
1233 e_ij
->count
= all
- count
;
1235 e_ij
->probability
= REG_BR_PROB_BASE
;
1238 /* Insert PHI node for the call result if necessary. */
1239 if (gimple_call_lhs (icall_stmt
)
1240 && TREE_CODE (gimple_call_lhs (icall_stmt
)) == SSA_NAME
1241 && (dflags
& ECF_NORETURN
) == 0)
1243 tree result
= gimple_call_lhs (icall_stmt
);
1244 gimple phi
= create_phi_node (result
, join_bb
);
1245 SSA_NAME_DEF_STMT (result
) = phi
;
1246 gimple_call_set_lhs (icall_stmt
,
1247 make_ssa_name (SSA_NAME_VAR (result
), icall_stmt
));
1248 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1249 gimple_call_set_lhs (dcall_stmt
,
1250 make_ssa_name (SSA_NAME_VAR (result
), dcall_stmt
));
1251 add_phi_arg (phi
, gimple_call_lhs (dcall_stmt
), e_dj
, UNKNOWN_LOCATION
);
1254 /* Build an EH edge for the direct call if necessary. */
1255 lp_nr
= lookup_stmt_eh_lp (icall_stmt
);
1257 && stmt_could_throw_p (dcall_stmt
))
1261 gimple_stmt_iterator psi
;
1263 add_stmt_to_eh_lp (dcall_stmt
, lp_nr
);
1264 FOR_EACH_EDGE (e_eh
, ei
, icall_bb
->succs
)
1265 if (e_eh
->flags
& EDGE_EH
)
1267 e
= make_edge (dcall_bb
, e_eh
->dest
, EDGE_EH
);
1268 for (psi
= gsi_start_phis (e_eh
->dest
);
1269 !gsi_end_p (psi
); gsi_next (&psi
))
1271 gimple phi
= gsi_stmt (psi
);
1272 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
),
1273 PHI_ARG_DEF_FROM_EDGE (phi
, e_eh
));
1281 For every checked indirect/virtual call determine if most common pid of
1282 function/class method has probability more than 50%. If yes modify code of
1287 gimple_ic_transform (gimple stmt
)
1289 histogram_value histogram
;
1290 gcov_type val
, count
, all
, bb_all
;
1293 struct cgraph_node
*direct_call
;
1295 if (gimple_code (stmt
) != GIMPLE_CALL
)
1298 if (gimple_call_fndecl (stmt
) != NULL_TREE
)
1301 if (gimple_call_internal_p (stmt
))
1304 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1308 val
= histogram
->hvalue
.counters
[0];
1309 count
= histogram
->hvalue
.counters
[1];
1310 all
= histogram
->hvalue
.counters
[2];
1311 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1313 if (4 * count
<= 3 * all
)
1316 bb_all
= gimple_bb (stmt
)->count
;
1317 /* The order of CHECK_COUNTER calls is important -
1318 since check_counter can correct the third parameter
1319 and we want to make count <= all <= bb_all. */
1320 if ( check_counter (stmt
, "ic", &all
, &bb_all
, bb_all
)
1321 || check_counter (stmt
, "ic", &count
, &all
, all
))
1325 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1328 direct_call
= find_func_by_funcdef_no ((int)val
);
1330 if (direct_call
== NULL
)
1333 if (!check_ic_target (stmt
, direct_call
))
1336 modify
= gimple_ic (stmt
, direct_call
, prob
, count
, all
);
1340 fprintf (dump_file
, "Indirect call -> direct call ");
1341 print_generic_expr (dump_file
, gimple_call_fn (stmt
), TDF_SLIM
);
1342 fprintf (dump_file
, "=> ");
1343 print_generic_expr (dump_file
, direct_call
->symbol
.decl
, TDF_SLIM
);
1344 fprintf (dump_file
, " transformation on insn ");
1345 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1346 fprintf (dump_file
, " to ");
1347 print_gimple_stmt (dump_file
, modify
, 0, TDF_SLIM
);
1348 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1349 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1355 /* Return true if the stringop CALL with FNDECL shall be profiled.
1356 SIZE_ARG be set to the argument index for the size of the string
1360 interesting_stringop_to_profile_p (tree fndecl
, gimple call
, int *size_arg
)
1362 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1364 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1365 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1370 case BUILT_IN_MEMCPY
:
1371 case BUILT_IN_MEMPCPY
:
1373 return validate_gimple_arglist (call
, POINTER_TYPE
, POINTER_TYPE
,
1374 INTEGER_TYPE
, VOID_TYPE
);
1375 case BUILT_IN_MEMSET
:
1377 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1378 INTEGER_TYPE
, VOID_TYPE
);
1379 case BUILT_IN_BZERO
:
1381 return validate_gimple_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1388 /* Convert stringop (..., vcall_size)
1390 if (vcall_size == icall_size)
1391 stringop (..., icall_size);
1393 stringop (..., vcall_size);
1394 assuming we'll propagate a true constant into ICALL_SIZE later. */
1397 gimple_stringop_fixed_value (gimple vcall_stmt
, tree icall_size
, int prob
,
1398 gcov_type count
, gcov_type all
)
1400 gimple tmp_stmt
, cond_stmt
, icall_stmt
;
1401 tree tmp0
, tmp1
, tmpv
, vcall_size
, optype
;
1402 basic_block cond_bb
, icall_bb
, vcall_bb
, join_bb
;
1403 edge e_ci
, e_cv
, e_iv
, e_ij
, e_vj
;
1404 gimple_stmt_iterator gsi
;
1408 fndecl
= gimple_call_fndecl (vcall_stmt
);
1409 if (!interesting_stringop_to_profile_p (fndecl
, vcall_stmt
, &size_arg
))
1412 cond_bb
= gimple_bb (vcall_stmt
);
1413 gsi
= gsi_for_stmt (vcall_stmt
);
1415 vcall_size
= gimple_call_arg (vcall_stmt
, size_arg
);
1416 optype
= TREE_TYPE (vcall_size
);
1418 tmpv
= create_tmp_var (optype
, "PROF");
1419 tmp0
= make_ssa_name (tmpv
, NULL
);
1420 tmp1
= make_ssa_name (tmpv
, NULL
);
1421 tmp_stmt
= gimple_build_assign (tmp0
, fold_convert (optype
, icall_size
));
1422 SSA_NAME_DEF_STMT (tmp0
) = tmp_stmt
;
1423 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1425 tmp_stmt
= gimple_build_assign (tmp1
, vcall_size
);
1426 SSA_NAME_DEF_STMT (tmp1
) = tmp_stmt
;
1427 gsi_insert_before (&gsi
, tmp_stmt
, GSI_SAME_STMT
);
1429 cond_stmt
= gimple_build_cond (EQ_EXPR
, tmp1
, tmp0
, NULL_TREE
, NULL_TREE
);
1430 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1432 gimple_set_vdef (vcall_stmt
, NULL
);
1433 gimple_set_vuse (vcall_stmt
, NULL
);
1434 update_stmt (vcall_stmt
);
1435 icall_stmt
= gimple_copy (vcall_stmt
);
1436 gimple_call_set_arg (icall_stmt
, size_arg
, icall_size
);
1437 gsi_insert_before (&gsi
, icall_stmt
, GSI_SAME_STMT
);
1440 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1441 e_ci
= split_block (cond_bb
, cond_stmt
);
1442 icall_bb
= e_ci
->dest
;
1443 icall_bb
->count
= count
;
1445 e_iv
= split_block (icall_bb
, icall_stmt
);
1446 vcall_bb
= e_iv
->dest
;
1447 vcall_bb
->count
= all
- count
;
1449 e_vj
= split_block (vcall_bb
, vcall_stmt
);
1450 join_bb
= e_vj
->dest
;
1451 join_bb
->count
= all
;
1453 e_ci
->flags
= (e_ci
->flags
& ~EDGE_FALLTHRU
) | EDGE_TRUE_VALUE
;
1454 e_ci
->probability
= prob
;
1455 e_ci
->count
= count
;
1457 e_cv
= make_edge (cond_bb
, vcall_bb
, EDGE_FALSE_VALUE
);
1458 e_cv
->probability
= REG_BR_PROB_BASE
- prob
;
1459 e_cv
->count
= all
- count
;
1463 e_ij
= make_edge (icall_bb
, join_bb
, EDGE_FALLTHRU
);
1464 e_ij
->probability
= REG_BR_PROB_BASE
;
1465 e_ij
->count
= count
;
1467 e_vj
->probability
= REG_BR_PROB_BASE
;
1468 e_vj
->count
= all
- count
;
1470 /* Insert PHI node for the call result if necessary. */
1471 if (gimple_call_lhs (vcall_stmt
)
1472 && TREE_CODE (gimple_call_lhs (vcall_stmt
)) == SSA_NAME
)
1474 tree result
= gimple_call_lhs (vcall_stmt
);
1475 gimple phi
= create_phi_node (result
, join_bb
);
1476 SSA_NAME_DEF_STMT (result
) = phi
;
1477 gimple_call_set_lhs (vcall_stmt
,
1478 make_ssa_name (SSA_NAME_VAR (result
), vcall_stmt
));
1479 add_phi_arg (phi
, gimple_call_lhs (vcall_stmt
), e_vj
, UNKNOWN_LOCATION
);
1480 gimple_call_set_lhs (icall_stmt
,
1481 make_ssa_name (SSA_NAME_VAR (result
), icall_stmt
));
1482 add_phi_arg (phi
, gimple_call_lhs (icall_stmt
), e_ij
, UNKNOWN_LOCATION
);
1485 /* Because these are all string op builtins, they're all nothrow. */
1486 gcc_assert (!stmt_could_throw_p (vcall_stmt
));
1487 gcc_assert (!stmt_could_throw_p (icall_stmt
));
1490 /* Find values inside STMT for that we want to measure histograms for
1491 division/modulo optimization. */
1493 gimple_stringops_transform (gimple_stmt_iterator
*gsi
)
1495 gimple stmt
= gsi_stmt (*gsi
);
1498 enum built_in_function fcode
;
1499 histogram_value histogram
;
1500 gcov_type count
, all
, val
;
1502 unsigned int dest_align
, src_align
;
1507 if (gimple_code (stmt
) != GIMPLE_CALL
)
1509 fndecl
= gimple_call_fndecl (stmt
);
1512 fcode
= DECL_FUNCTION_CODE (fndecl
);
1513 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1516 blck_size
= gimple_call_arg (stmt
, size_arg
);
1517 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1520 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1523 val
= histogram
->hvalue
.counters
[0];
1524 count
= histogram
->hvalue
.counters
[1];
1525 all
= histogram
->hvalue
.counters
[2];
1526 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1527 /* We require that count is at least half of all; this means
1528 that for the transformation to fire the value must be constant
1529 at least 80% of time. */
1530 if ((6 * count
/ 5) < all
|| optimize_bb_for_size_p (gimple_bb (stmt
)))
1532 if (check_counter (stmt
, "value", &count
, &all
, gimple_bb (stmt
)->count
))
1535 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1538 dest
= gimple_call_arg (stmt
, 0);
1539 dest_align
= get_pointer_alignment (dest
);
1542 case BUILT_IN_MEMCPY
:
1543 case BUILT_IN_MEMPCPY
:
1544 src
= gimple_call_arg (stmt
, 1);
1545 src_align
= get_pointer_alignment (src
);
1546 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1549 case BUILT_IN_MEMSET
:
1550 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1551 gimple_call_arg (stmt
, 1),
1555 case BUILT_IN_BZERO
:
1556 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1564 tree_val
= build_int_cst_wide (get_gcov_type (),
1565 (unsigned HOST_WIDE_INT
) val
,
1566 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1569 fprintf (dump_file
, "Single value %i stringop transformation on ",
1571 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1573 gimple_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1579 stringop_block_profile (gimple stmt
, unsigned int *expected_align
,
1580 HOST_WIDE_INT
*expected_size
)
1582 histogram_value histogram
;
1583 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1585 *expected_size
= -1;
1586 else if (!histogram
->hvalue
.counters
[1])
1588 *expected_size
= -1;
1589 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1594 size
= ((histogram
->hvalue
.counters
[0]
1595 + histogram
->hvalue
.counters
[1] / 2)
1596 / histogram
->hvalue
.counters
[1]);
1597 /* Even if we can hold bigger value in SIZE, INT_MAX
1598 is safe "infinity" for code generation strategies. */
1601 *expected_size
= size
;
1602 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1604 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1606 *expected_align
= 0;
1607 else if (!histogram
->hvalue
.counters
[0])
1609 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1610 *expected_align
= 0;
1617 count
= histogram
->hvalue
.counters
[0];
1619 while (!(count
& alignment
)
1620 && (alignment
* 2 * BITS_PER_UNIT
))
1622 *expected_align
= alignment
* BITS_PER_UNIT
;
1623 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1628 /* Find values inside STMT for that we want to measure histograms for
1629 division/modulo optimization. */
1631 gimple_divmod_values_to_profile (gimple stmt
, histogram_values
*values
)
1633 tree lhs
, divisor
, op0
, type
;
1634 histogram_value hist
;
1636 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1639 lhs
= gimple_assign_lhs (stmt
);
1640 type
= TREE_TYPE (lhs
);
1641 if (!INTEGRAL_TYPE_P (type
))
1644 switch (gimple_assign_rhs_code (stmt
))
1646 case TRUNC_DIV_EXPR
:
1647 case TRUNC_MOD_EXPR
:
1648 divisor
= gimple_assign_rhs2 (stmt
);
1649 op0
= gimple_assign_rhs1 (stmt
);
1651 VEC_reserve (histogram_value
, heap
, *values
, 3);
1653 if (is_gimple_reg (divisor
))
1654 /* Check for the case where the divisor is the same value most
1656 VEC_quick_push (histogram_value
, *values
,
1657 gimple_alloc_histogram_value (cfun
,
1658 HIST_TYPE_SINGLE_VALUE
,
1661 /* For mod, check whether it is not often a noop (or replaceable by
1662 a few subtractions). */
1663 if (gimple_assign_rhs_code (stmt
) == TRUNC_MOD_EXPR
1664 && TYPE_UNSIGNED (type
))
1667 /* Check for a special case where the divisor is power of 2. */
1668 VEC_quick_push (histogram_value
, *values
,
1669 gimple_alloc_histogram_value (cfun
, HIST_TYPE_POW2
,
1672 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1673 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1675 hist
->hdata
.intvl
.int_start
= 0;
1676 hist
->hdata
.intvl
.steps
= 2;
1677 VEC_quick_push (histogram_value
, *values
, hist
);
1686 /* Find calls inside STMT for that we want to measure histograms for
1687 indirect/virtual call optimization. */
1690 gimple_indirect_call_to_profile (gimple stmt
, histogram_values
*values
)
1694 if (gimple_code (stmt
) != GIMPLE_CALL
1695 || gimple_call_internal_p (stmt
)
1696 || gimple_call_fndecl (stmt
) != NULL_TREE
)
1699 callee
= gimple_call_fn (stmt
);
1701 VEC_reserve (histogram_value
, heap
, *values
, 3);
1703 VEC_quick_push (histogram_value
, *values
,
1704 gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1710 /* Find values inside STMT for that we want to measure histograms for
1711 string operations. */
1713 gimple_stringops_values_to_profile (gimple stmt
, histogram_values
*values
)
1720 if (gimple_code (stmt
) != GIMPLE_CALL
)
1722 fndecl
= gimple_call_fndecl (stmt
);
1726 if (!interesting_stringop_to_profile_p (fndecl
, stmt
, &size_arg
))
1729 dest
= gimple_call_arg (stmt
, 0);
1730 blck_size
= gimple_call_arg (stmt
, size_arg
);
1732 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1734 VEC_safe_push (histogram_value
, heap
, *values
,
1735 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1737 VEC_safe_push (histogram_value
, heap
, *values
,
1738 gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1741 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1742 VEC_safe_push (histogram_value
, heap
, *values
,
1743 gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1747 /* Find values inside STMT for that we want to measure histograms and adds
1748 them to list VALUES. */
1751 gimple_values_to_profile (gimple stmt
, histogram_values
*values
)
1753 if (flag_value_profile_transformations
)
1755 gimple_divmod_values_to_profile (stmt
, values
);
1756 gimple_stringops_values_to_profile (stmt
, values
);
1757 gimple_indirect_call_to_profile (stmt
, values
);
1762 gimple_find_values_to_profile (histogram_values
*values
)
1765 gimple_stmt_iterator gsi
;
1767 histogram_value hist
= NULL
;
1771 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1772 gimple_values_to_profile (gsi_stmt (gsi
), values
);
1774 FOR_EACH_VEC_ELT (histogram_value
, *values
, i
, hist
)
1778 case HIST_TYPE_INTERVAL
:
1779 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1782 case HIST_TYPE_POW2
:
1783 hist
->n_counters
= 2;
1786 case HIST_TYPE_SINGLE_VALUE
:
1787 hist
->n_counters
= 3;
1790 case HIST_TYPE_CONST_DELTA
:
1791 hist
->n_counters
= 4;
1794 case HIST_TYPE_INDIR_CALL
:
1795 hist
->n_counters
= 3;
1798 case HIST_TYPE_AVERAGE
:
1799 hist
->n_counters
= 2;
1803 hist
->n_counters
= 1;
1811 fprintf (dump_file
, "Stmt ");
1812 print_gimple_stmt (dump_file
, hist
->hvalue
.stmt
, 0, TDF_SLIM
);
1813 dump_histogram_value (dump_file
, hist
);