1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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"
45 #include "tree-pass.h"
47 #include "pointer-set.h"
49 static struct value_prof_hooks
*value_prof_hooks
;
51 /* In this file value profile based optimizations are placed. Currently the
52 following optimizations are implemented (for more detailed descriptions
53 see comments at value_profile_transformations):
55 1) Division/modulo specialization. Provided that we can determine that the
56 operands of the division have some special properties, we may use it to
57 produce more effective code.
58 2) Speculative prefetching. If we are able to determine that the difference
59 between addresses accessed by a memory reference is usually constant, we
60 may add the prefetch instructions.
61 FIXME: This transformation was removed together with RTL based value
64 3) Indirect/virtual call specialization. If we can determine most
65 common function callee in indirect/virtual call. We can use this
66 information to improve code effectiveness (especially info for
69 Every such optimization should add its requirements for profiled values to
70 insn_values_to_profile function. This function is called from branch_prob
71 in profile.c and the requested values are instrumented by it in the first
72 compilation with -fprofile-arcs. The optimization may then read the
73 gathered data in the second compilation with -fbranch-probabilities.
75 The measured data is pointed to from the histograms
76 field of the statement annotation of the instrumented insns. It is
77 kept as a linked list of struct histogram_value_t's, which contain the
78 same information as above. */
81 static tree
tree_divmod_fixed_value (tree
, tree
, tree
, tree
,
82 tree
, int, gcov_type
, gcov_type
);
83 static tree
tree_mod_pow2 (tree
, tree
, tree
, tree
, int, gcov_type
, gcov_type
);
84 static tree
tree_mod_subtract (tree
, tree
, tree
, tree
, int, int, int,
85 gcov_type
, gcov_type
, gcov_type
);
86 static bool tree_divmod_fixed_value_transform (tree
);
87 static bool tree_mod_pow2_value_transform (tree
);
88 static bool tree_mod_subtract_transform (tree
);
89 static bool tree_stringops_transform (block_stmt_iterator
*);
90 static bool tree_ic_transform (tree
);
92 /* Allocate histogram value. */
94 static histogram_value
95 gimple_alloc_histogram_value (struct function
*fun ATTRIBUTE_UNUSED
,
96 enum hist_type type
, tree stmt
, tree value
)
98 histogram_value hist
= (histogram_value
) xcalloc (1, sizeof (*hist
));
99 hist
->hvalue
.value
= value
;
100 hist
->hvalue
.stmt
= stmt
;
105 /* Hash value for histogram. */
108 histogram_hash (const void *x
)
110 return htab_hash_pointer (((histogram_value
)x
)->hvalue
.stmt
);
113 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
116 histogram_eq (const void *x
, const void *y
)
118 return ((histogram_value
) x
)->hvalue
.stmt
== (tree
)y
;
121 /* Set histogram for STMT. */
124 set_histogram_value (struct function
*fun
, tree stmt
, histogram_value hist
)
127 if (!hist
&& !VALUE_HISTOGRAMS (fun
))
129 if (!VALUE_HISTOGRAMS (fun
))
130 VALUE_HISTOGRAMS (fun
) = htab_create (1, histogram_hash
,
132 loc
= htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
133 htab_hash_pointer (stmt
),
134 hist
? INSERT
: NO_INSERT
);
138 htab_clear_slot (VALUE_HISTOGRAMS (fun
), loc
);
144 /* Get histogram list for STMT. */
147 gimple_histogram_value (struct function
*fun
, tree stmt
)
149 if (!VALUE_HISTOGRAMS (fun
))
151 return htab_find_with_hash (VALUE_HISTOGRAMS (fun
), stmt
,
152 htab_hash_pointer (stmt
));
155 /* Add histogram for STMT. */
158 gimple_add_histogram_value (struct function
*fun
, tree stmt
, histogram_value hist
)
160 hist
->hvalue
.next
= gimple_histogram_value (fun
, stmt
);
161 set_histogram_value (fun
, stmt
, hist
);
164 /* Remove histogram HIST from STMT's histogram list. */
167 gimple_remove_histogram_value (struct function
*fun
, tree stmt
, histogram_value hist
)
169 histogram_value hist2
= gimple_histogram_value (fun
, stmt
);
172 set_histogram_value (fun
, stmt
, hist
->hvalue
.next
);
176 while (hist2
->hvalue
.next
!= hist
)
177 hist2
= hist2
->hvalue
.next
;
178 hist2
->hvalue
.next
= hist
->hvalue
.next
;
180 free (hist
->hvalue
.counters
);
181 #ifdef ENABLE_CHECKING
182 memset (hist
, 0xab, sizeof (*hist
));
187 /* Lookup histogram of type TYPE in the STMT. */
190 gimple_histogram_value_of_type (struct function
*fun
, tree stmt
, enum hist_type type
)
192 histogram_value hist
;
193 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
194 if (hist
->type
== type
)
199 /* Dump information about HIST to DUMP_FILE. */
202 dump_histogram_value (FILE *dump_file
, histogram_value hist
)
206 case HIST_TYPE_INTERVAL
:
207 fprintf (dump_file
, "Interval counter range %d -- %d",
208 hist
->hdata
.intvl
.int_start
,
209 (hist
->hdata
.intvl
.int_start
210 + hist
->hdata
.intvl
.steps
- 1));
211 if (hist
->hvalue
.counters
)
214 fprintf(dump_file
, " [");
215 for (i
= 0; i
< hist
->hdata
.intvl
.steps
; i
++)
216 fprintf (dump_file
, " %d:"HOST_WIDEST_INT_PRINT_DEC
,
217 hist
->hdata
.intvl
.int_start
+ i
,
218 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
219 fprintf (dump_file
, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC
,
220 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[i
]);
222 fprintf (dump_file
, ".\n");
226 fprintf (dump_file
, "Pow2 counter ");
227 if (hist
->hvalue
.counters
)
229 fprintf (dump_file
, "pow2:"HOST_WIDEST_INT_PRINT_DEC
230 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC
,
231 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
232 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
234 fprintf (dump_file
, ".\n");
237 case HIST_TYPE_SINGLE_VALUE
:
238 fprintf (dump_file
, "Single value ");
239 if (hist
->hvalue
.counters
)
241 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
242 " match:"HOST_WIDEST_INT_PRINT_DEC
243 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
244 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
245 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
246 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
248 fprintf (dump_file
, ".\n");
251 case HIST_TYPE_AVERAGE
:
252 fprintf (dump_file
, "Average value ");
253 if (hist
->hvalue
.counters
)
255 fprintf (dump_file
, "sum:"HOST_WIDEST_INT_PRINT_DEC
256 " times:"HOST_WIDEST_INT_PRINT_DEC
,
257 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
258 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1]);
260 fprintf (dump_file
, ".\n");
264 fprintf (dump_file
, "IOR value ");
265 if (hist
->hvalue
.counters
)
267 fprintf (dump_file
, "ior:"HOST_WIDEST_INT_PRINT_DEC
,
268 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0]);
270 fprintf (dump_file
, ".\n");
273 case HIST_TYPE_CONST_DELTA
:
274 fprintf (dump_file
, "Constant delta ");
275 if (hist
->hvalue
.counters
)
277 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
278 " match:"HOST_WIDEST_INT_PRINT_DEC
279 " wrong:"HOST_WIDEST_INT_PRINT_DEC
,
280 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
281 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
282 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
284 fprintf (dump_file
, ".\n");
286 case HIST_TYPE_INDIR_CALL
:
287 fprintf (dump_file
, "Indirect call ");
288 if (hist
->hvalue
.counters
)
290 fprintf (dump_file
, "value:"HOST_WIDEST_INT_PRINT_DEC
291 " match:"HOST_WIDEST_INT_PRINT_DEC
292 " all:"HOST_WIDEST_INT_PRINT_DEC
,
293 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[0],
294 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[1],
295 (HOST_WIDEST_INT
) hist
->hvalue
.counters
[2]);
297 fprintf (dump_file
, ".\n");
302 /* Dump all histograms attached to STMT to DUMP_FILE. */
305 dump_histograms_for_stmt (struct function
*fun
, FILE *dump_file
, tree stmt
)
307 histogram_value hist
;
308 for (hist
= gimple_histogram_value (fun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
309 dump_histogram_value (dump_file
, hist
);
312 /* Remove all histograms associated with STMT. */
315 gimple_remove_stmt_histograms (struct function
*fun
, tree stmt
)
318 while ((val
= gimple_histogram_value (fun
, stmt
)) != NULL
)
319 gimple_remove_histogram_value (fun
, stmt
, val
);
322 /* Duplicate all histograms associates with OSTMT to STMT. */
325 gimple_duplicate_stmt_histograms (struct function
*fun
, tree stmt
,
326 struct function
*ofun
, tree ostmt
)
329 for (val
= gimple_histogram_value (ofun
, ostmt
); val
!= NULL
; val
= val
->hvalue
.next
)
331 histogram_value
new = gimple_alloc_histogram_value (fun
, val
->type
, NULL
, NULL
);
332 memcpy (new, val
, sizeof (*val
));
333 new->hvalue
.stmt
= stmt
;
334 new->hvalue
.counters
= xmalloc (sizeof (*new->hvalue
.counters
) * new->n_counters
);
335 memcpy (new->hvalue
.counters
, val
->hvalue
.counters
, sizeof (*new->hvalue
.counters
) * new->n_counters
);
336 gimple_add_histogram_value (fun
, stmt
, new);
340 static bool error_found
= false;
342 /* Helper function for verify_histograms. For each histogram reachable via htab
343 walk verify that it was reached via statement walk. */
346 visit_hist (void **slot
, void *data
)
348 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
349 histogram_value hist
= *(histogram_value
*) slot
;
350 if (!pointer_set_contains (visited
, hist
))
352 error ("Dead histogram");
353 dump_histogram_value (stderr
, hist
);
354 debug_generic_stmt (hist
->hvalue
.stmt
);
360 /* Verify sanity of the histograms. */
363 verify_histograms (void)
366 block_stmt_iterator bsi
;
367 histogram_value hist
;
368 struct pointer_set_t
*visited_hists
;
371 visited_hists
= pointer_set_create ();
373 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
375 tree stmt
= bsi_stmt (bsi
);
377 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
379 if (hist
->hvalue
.stmt
!= stmt
)
381 error ("Histogram value statement does not correspond to statement"
382 " it is associated with");
383 debug_generic_stmt (stmt
);
384 dump_histogram_value (stderr
, hist
);
387 pointer_set_insert (visited_hists
, hist
);
390 if (VALUE_HISTOGRAMS (cfun
))
391 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, visited_hists
);
392 pointer_set_destroy (visited_hists
);
394 internal_error ("verify_histograms failed");
397 /* Helper function for verify_histograms. For each histogram reachable via htab
398 walk verify that it was reached via statement walk. */
401 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
403 histogram_value hist
= *(histogram_value
*) slot
;
404 free (hist
->hvalue
.counters
);
405 #ifdef ENABLE_CHECKING
406 memset (hist
, 0xab, sizeof (*hist
));
413 free_histograms (void)
415 if (VALUE_HISTOGRAMS (cfun
))
417 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
418 htab_delete (VALUE_HISTOGRAMS (cfun
));
419 VALUE_HISTOGRAMS (cfun
) = NULL
;
423 /* The overall number of invocations of the counter should match execution count
424 of basic block. Report it as error rather than internal error as it might
425 mean that user has misused the profile somehow. */
427 check_counter (tree stmt
, const char * name
, gcov_type all
, gcov_type bb_count
)
432 locus
= (stmt
!= NULL
&& EXPR_HAS_LOCATION (stmt
)
434 : &DECL_SOURCE_LOCATION (current_function_decl
));
435 error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)",
436 locus
, name
, (int)all
, (int)bb_count
);
442 /* Tree based transformations. */
444 tree_value_profile_transformations (void)
447 block_stmt_iterator bsi
;
448 bool changed
= false;
452 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
454 tree stmt
= bsi_stmt (bsi
);
455 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
461 fprintf (dump_file
, "Trying transformations on stmt ");
462 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
463 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
466 /* Transformations: */
467 /* The order of things in this conditional controls which
468 transformation is used when more than one is applicable. */
469 /* It is expected that any code added by the transformations
470 will be added before the current statement, and that the
471 current statement remain valid (although possibly
472 modified) upon return. */
473 if (flag_value_profile_transformations
474 && (tree_mod_subtract_transform (stmt
)
475 || tree_divmod_fixed_value_transform (stmt
)
476 || tree_mod_pow2_value_transform (stmt
)
477 || tree_stringops_transform (&bsi
)
478 || tree_ic_transform (stmt
)))
480 stmt
= bsi_stmt (bsi
);
482 /* Original statement may no longer be in the same block. */
483 if (bb
!= bb_for_stmt (stmt
))
485 bb
= bb_for_stmt (stmt
);
486 bsi
= bsi_for_stmt (stmt
);
500 /* Generate code for transformation 1 (with OPERATION, operands OP1
501 and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
502 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
503 within roundoff error). This generates the result into a temp and returns
504 the temp; it does not replace or alter the original STMT. */
506 tree_divmod_fixed_value (tree stmt
, tree operation
,
507 tree op1
, tree op2
, tree value
, int prob
, gcov_type count
,
510 tree stmt1
, stmt2
, stmt3
;
511 tree tmp1
, tmp2
, tmpv
;
512 tree label_decl1
= create_artificial_label ();
513 tree label_decl2
= create_artificial_label ();
515 tree bb1end
, bb2end
, bb3end
;
516 basic_block bb
, bb2
, bb3
, bb4
;
517 tree optype
= TREE_TYPE (operation
);
518 edge e12
, e13
, e23
, e24
, e34
;
519 block_stmt_iterator bsi
;
521 bb
= bb_for_stmt (stmt
);
522 bsi
= bsi_for_stmt (stmt
);
524 tmpv
= create_tmp_var (optype
, "PROF");
525 tmp1
= create_tmp_var (optype
, "PROF");
526 stmt1
= build_gimple_modify_stmt (tmpv
, fold_convert (optype
, value
));
527 stmt2
= build_gimple_modify_stmt (tmp1
, op2
);
528 stmt3
= build3 (COND_EXPR
, void_type_node
,
529 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
530 NULL_TREE
, NULL_TREE
);
531 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
532 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
533 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
536 tmp2
= create_tmp_var (optype
, "PROF");
537 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
538 stmt1
= build_gimple_modify_stmt (tmp2
,
539 build2 (TREE_CODE (operation
), optype
,
541 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
542 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
545 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
546 stmt1
= build_gimple_modify_stmt (tmp2
,
547 build2 (TREE_CODE (operation
), optype
,
549 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
550 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
554 /* Edge e23 connects bb2 to bb3, etc. */
555 e12
= split_block (bb
, bb1end
);
558 e23
= split_block (bb2
, bb2end
);
560 bb3
->count
= all
- count
;
561 e34
= split_block (bb3
, bb3end
);
565 e12
->flags
&= ~EDGE_FALLTHRU
;
566 e12
->flags
|= EDGE_FALSE_VALUE
;
567 e12
->probability
= prob
;
570 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
571 e13
->probability
= REG_BR_PROB_BASE
- prob
;
572 e13
->count
= all
- count
;
576 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
577 e24
->probability
= REG_BR_PROB_BASE
;
580 e34
->probability
= REG_BR_PROB_BASE
;
581 e34
->count
= all
- count
;
586 /* Do transform 1) on INSN if applicable. */
588 tree_divmod_fixed_value_transform (tree stmt
)
590 histogram_value histogram
;
592 gcov_type val
, count
, all
;
593 tree modify
, op
, op1
, op2
, result
, value
, tree_val
;
597 if (TREE_CODE (stmt
) == RETURN_EXPR
598 && TREE_OPERAND (stmt
, 0)
599 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
600 modify
= TREE_OPERAND (stmt
, 0);
601 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
603 op
= GIMPLE_STMT_OPERAND (modify
, 1);
604 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
606 code
= TREE_CODE (op
);
608 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
611 op1
= TREE_OPERAND (op
, 0);
612 op2
= TREE_OPERAND (op
, 1);
614 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
618 value
= histogram
->hvalue
.value
;
619 val
= histogram
->hvalue
.counters
[0];
620 count
= histogram
->hvalue
.counters
[1];
621 all
= histogram
->hvalue
.counters
[2];
622 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
624 /* We require that count is at least half of all; this means
625 that for the transformation to fire the value must be constant
626 at least 50% of time (and 75% gives the guarantee of usage). */
627 if (simple_cst_equal (op2
, value
) != 1 || 2 * count
< all
628 || !maybe_hot_bb_p (bb_for_stmt (stmt
)))
631 if (check_counter (stmt
, "value", all
, bb_for_stmt (stmt
)->count
))
634 /* Compute probability of taking the optimal path. */
635 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
637 tree_val
= build_int_cst_wide (get_gcov_type (),
638 (unsigned HOST_WIDE_INT
) val
,
639 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
640 result
= tree_divmod_fixed_value (stmt
, op
, op1
, op2
, tree_val
, prob
, count
, all
);
644 fprintf (dump_file
, "Div/mod by constant ");
645 print_generic_expr (dump_file
, value
, TDF_SLIM
);
646 fprintf (dump_file
, "=");
647 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
648 fprintf (dump_file
, " transformation on insn ");
649 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
652 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
657 /* Generate code for transformation 2 (with OPERATION, operands OP1
658 and OP2, parent modify-expr STMT and probability of taking the optimal
659 path PROB, which is equivalent to COUNT/ALL within roundoff error).
660 This generates the result into a temp and returns
661 the temp; it does not replace or alter the original STMT. */
663 tree_mod_pow2 (tree stmt
, tree operation
, tree op1
, tree op2
, int prob
,
664 gcov_type count
, gcov_type all
)
666 tree stmt1
, stmt2
, stmt3
, stmt4
;
668 tree label_decl1
= create_artificial_label ();
669 tree label_decl2
= create_artificial_label ();
671 tree bb1end
, bb2end
, bb3end
;
672 basic_block bb
, bb2
, bb3
, bb4
;
673 tree optype
= TREE_TYPE (operation
);
674 edge e12
, e13
, e23
, e24
, e34
;
675 block_stmt_iterator bsi
;
676 tree result
= create_tmp_var (optype
, "PROF");
678 bb
= bb_for_stmt (stmt
);
679 bsi
= bsi_for_stmt (stmt
);
681 tmp2
= create_tmp_var (optype
, "PROF");
682 tmp3
= create_tmp_var (optype
, "PROF");
683 stmt2
= build_gimple_modify_stmt (tmp2
,
684 build2 (PLUS_EXPR
, optype
, op2
,
685 build_int_cst (optype
, -1)));
686 stmt3
= build_gimple_modify_stmt (tmp3
,
687 build2 (BIT_AND_EXPR
, optype
, tmp2
, op2
));
688 stmt4
= build3 (COND_EXPR
, void_type_node
,
689 build2 (NE_EXPR
, boolean_type_node
,
690 tmp3
, build_int_cst (optype
, 0)),
691 NULL_TREE
, NULL_TREE
);
692 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
693 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
694 bsi_insert_before (&bsi
, stmt4
, BSI_SAME_STMT
);
697 /* tmp2 == op2-1 inherited from previous block */
698 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
699 stmt1
= build_gimple_modify_stmt (result
,
700 build2 (BIT_AND_EXPR
, optype
, op1
, tmp2
));
701 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
702 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
705 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
706 stmt1
= build_gimple_modify_stmt (result
,
707 build2 (TREE_CODE (operation
), optype
,
709 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
710 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
714 /* Edge e23 connects bb2 to bb3, etc. */
715 e12
= split_block (bb
, bb1end
);
718 e23
= split_block (bb2
, bb2end
);
720 bb3
->count
= all
- count
;
721 e34
= split_block (bb3
, bb3end
);
725 e12
->flags
&= ~EDGE_FALLTHRU
;
726 e12
->flags
|= EDGE_FALSE_VALUE
;
727 e12
->probability
= prob
;
730 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
731 e13
->probability
= REG_BR_PROB_BASE
- prob
;
732 e13
->count
= all
- count
;
736 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
737 e24
->probability
= REG_BR_PROB_BASE
;
740 e34
->probability
= REG_BR_PROB_BASE
;
741 e34
->count
= all
- count
;
746 /* Do transform 2) on INSN if applicable. */
748 tree_mod_pow2_value_transform (tree stmt
)
750 histogram_value histogram
;
752 gcov_type count
, wrong_values
, all
;
753 tree modify
, op
, op1
, op2
, result
, value
;
757 if (TREE_CODE (stmt
) == RETURN_EXPR
758 && TREE_OPERAND (stmt
, 0)
759 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
760 modify
= TREE_OPERAND (stmt
, 0);
761 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
763 op
= GIMPLE_STMT_OPERAND (modify
, 1);
764 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
766 code
= TREE_CODE (op
);
768 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (TREE_TYPE (op
)))
771 op1
= TREE_OPERAND (op
, 0);
772 op2
= TREE_OPERAND (op
, 1);
774 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
778 value
= histogram
->hvalue
.value
;
779 wrong_values
= histogram
->hvalue
.counters
[0];
780 count
= histogram
->hvalue
.counters
[1];
782 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
784 /* We require that we hit a power of 2 at least half of all evaluations. */
785 if (simple_cst_equal (op2
, value
) != 1 || count
< wrong_values
786 || !maybe_hot_bb_p (bb_for_stmt (stmt
)))
791 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
792 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
795 /* Compute probability of taking the optimal path. */
796 all
= count
+ wrong_values
;
798 if (check_counter (stmt
, "pow2", all
, bb_for_stmt (stmt
)->count
))
801 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
803 result
= tree_mod_pow2 (stmt
, op
, op1
, op2
, prob
, count
, all
);
805 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
810 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
811 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
812 support. Currently only NCOUNTS==0 or 1 is supported and this is
813 built into this interface. The probabilities of taking the optimal
814 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
815 COUNT2/ALL respectively within roundoff error). This generates the
816 result into a temp and returns the temp; it does not replace or alter
817 the original STMT. */
818 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
821 tree_mod_subtract (tree stmt
, tree operation
, tree op1
, tree op2
,
822 int prob1
, int prob2
, int ncounts
,
823 gcov_type count1
, gcov_type count2
, gcov_type all
)
825 tree stmt1
, stmt2
, stmt3
;
827 tree label_decl1
= create_artificial_label ();
828 tree label_decl2
= create_artificial_label ();
829 tree label_decl3
= create_artificial_label ();
830 tree label1
, label2
, label3
;
831 tree bb1end
, bb2end
= NULL_TREE
, bb3end
;
832 basic_block bb
, bb2
, bb3
, bb4
;
833 tree optype
= TREE_TYPE (operation
);
834 edge e12
, e23
= 0, e24
, e34
, e14
;
835 block_stmt_iterator bsi
;
836 tree result
= create_tmp_var (optype
, "PROF");
838 bb
= bb_for_stmt (stmt
);
839 bsi
= bsi_for_stmt (stmt
);
841 tmp1
= create_tmp_var (optype
, "PROF");
842 stmt1
= build_gimple_modify_stmt (result
, op1
);
843 stmt2
= build_gimple_modify_stmt (tmp1
, op2
);
844 stmt3
= build3 (COND_EXPR
, void_type_node
,
845 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
846 NULL_TREE
, NULL_TREE
);
847 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
848 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
849 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
852 if (ncounts
) /* Assumed to be 0 or 1 */
854 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
855 stmt1
= build_gimple_modify_stmt (result
,
856 build2 (MINUS_EXPR
, optype
,
858 stmt2
= build3 (COND_EXPR
, void_type_node
,
859 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
860 NULL_TREE
, NULL_TREE
);
861 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
862 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
863 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
868 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
869 stmt1
= build_gimple_modify_stmt (result
,
870 build2 (TREE_CODE (operation
), optype
,
872 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
873 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
876 label3
= build1 (LABEL_EXPR
, void_type_node
, label_decl3
);
877 bsi_insert_before (&bsi
, label3
, BSI_SAME_STMT
);
880 /* Edge e23 connects bb2 to bb3, etc. */
881 /* However block 3 is optional; if it is not there, references
882 to 3 really refer to block 2. */
883 e12
= split_block (bb
, bb1end
);
885 bb2
->count
= all
- count1
;
887 if (ncounts
) /* Assumed to be 0 or 1. */
889 e23
= split_block (bb2
, bb2end
);
891 bb3
->count
= all
- count1
- count2
;
894 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
898 e12
->flags
&= ~EDGE_FALLTHRU
;
899 e12
->flags
|= EDGE_FALSE_VALUE
;
900 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
901 e12
->count
= all
- count1
;
903 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
904 e14
->probability
= prob1
;
907 if (ncounts
) /* Assumed to be 0 or 1. */
909 e23
->flags
&= ~EDGE_FALLTHRU
;
910 e23
->flags
|= EDGE_FALSE_VALUE
;
911 e23
->count
= all
- count1
- count2
;
912 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
914 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
915 e24
->probability
= prob2
;
919 e34
->probability
= REG_BR_PROB_BASE
;
920 e34
->count
= all
- count1
- count2
;
925 /* Do transforms 3) and 4) on INSN if applicable. */
927 tree_mod_subtract_transform (tree stmt
)
929 histogram_value histogram
;
931 gcov_type count
, wrong_values
, all
;
932 tree modify
, op
, op1
, op2
, result
, value
;
934 unsigned int i
, steps
;
935 gcov_type count1
, count2
;
938 if (TREE_CODE (stmt
) == RETURN_EXPR
939 && TREE_OPERAND (stmt
, 0)
940 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
941 modify
= TREE_OPERAND (stmt
, 0);
942 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
944 op
= GIMPLE_STMT_OPERAND (modify
, 1);
945 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
947 code
= TREE_CODE (op
);
949 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (TREE_TYPE (op
)))
952 op1
= TREE_OPERAND (op
, 0);
953 op2
= TREE_OPERAND (op
, 1);
955 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
959 value
= histogram
->hvalue
.value
;
962 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
963 all
+= histogram
->hvalue
.counters
[i
];
965 wrong_values
+= histogram
->hvalue
.counters
[i
];
966 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
967 steps
= histogram
->hdata
.intvl
.steps
;
969 count1
= histogram
->hvalue
.counters
[0];
970 count2
= histogram
->hvalue
.counters
[1];
972 /* Compute probability of taking the optimal path. */
973 if (check_counter (stmt
, "interval", all
, bb_for_stmt (stmt
)->count
))
975 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
979 /* We require that we use just subtractions in at least 50% of all
982 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
984 count
+= histogram
->hvalue
.counters
[i
];
985 if (count
* 2 >= all
)
989 || !maybe_hot_bb_p (bb_for_stmt (stmt
)))
992 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
995 fprintf (dump_file
, "Mod subtract transformation on insn ");
996 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
999 /* Compute probability of taking the optimal path(s). */
1000 prob1
= (count1
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1001 prob2
= (count2
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1003 /* In practice, "steps" is always 2. This interface reflects this,
1004 and will need to be changed if "steps" can change. */
1005 result
= tree_mod_subtract (stmt
, op
, op1
, op2
, prob1
, prob2
, i
,
1006 count1
, count2
, all
);
1008 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
1013 static struct cgraph_node
** pid_map
= NULL
;
1015 /* Initialize map of pids (pid -> cgraph node) */
1020 struct cgraph_node
*n
;
1022 if (pid_map
!= NULL
)
1026 = (struct cgraph_node
**) xmalloc (sizeof (struct cgraph_node
*) * cgraph_max_pid
);
1028 for (n
= cgraph_nodes
; n
; n
= n
->next
)
1031 pid_map
[n
->pid
] = n
;
1035 /* Return cgraph node for function with pid */
1037 static inline struct cgraph_node
*
1038 find_func_by_pid (int pid
)
1042 return pid_map
[pid
];
1045 /* Do transformation
1047 if (actual_callee_addres == addres_of_most_common_function/method)
1054 tree_ic (tree stmt
, tree call
, struct cgraph_node
* direct_call
,
1055 int prob
, gcov_type count
, gcov_type all
)
1057 tree stmt1
, stmt2
, stmt3
;
1058 tree tmp1
, tmpv
, tmp
;
1059 tree label_decl1
= create_artificial_label ();
1060 tree label_decl2
= create_artificial_label ();
1061 tree label1
, label2
;
1062 tree bb1end
, bb2end
, bb3end
;
1064 basic_block bb
, bb2
, bb3
, bb4
;
1065 tree optype
= build_pointer_type (void_type_node
);
1066 edge e12
, e13
, e23
, e24
, e34
;
1067 block_stmt_iterator bsi
;
1070 bb
= bb_for_stmt (stmt
);
1071 bsi
= bsi_for_stmt (stmt
);
1073 tmpv
= create_tmp_var (optype
, "PROF");
1074 tmp1
= create_tmp_var (optype
, "PROF");
1075 stmt1
= build_gimple_modify_stmt (tmpv
,
1076 unshare_expr (CALL_EXPR_FN (call
)));
1077 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1078 current_function_decl
));
1079 stmt2
= build_gimple_modify_stmt (tmp1
, tmp
);
1080 stmt3
= build3 (COND_EXPR
, void_type_node
,
1081 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
1082 NULL_TREE
, NULL_TREE
);
1083 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1084 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1085 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1088 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1089 stmt1
= unshare_expr (stmt
);
1090 new_call
= get_call_expr_in (stmt1
);
1091 CALL_EXPR_FN (new_call
) = build_addr (direct_call
->decl
,
1092 current_function_decl
);
1093 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1094 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1097 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1098 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1102 /* Edge e23 connects bb2 to bb3, etc. */
1103 e12
= split_block (bb
, bb1end
);
1106 e23
= split_block (bb2
, bb2end
);
1108 bb3
->count
= all
- count
;
1109 e34
= split_block (bb3
, bb3end
);
1113 e12
->flags
&= ~EDGE_FALLTHRU
;
1114 e12
->flags
|= EDGE_FALSE_VALUE
;
1115 e12
->probability
= prob
;
1118 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
1119 e13
->probability
= REG_BR_PROB_BASE
- prob
;
1120 e13
->count
= all
- count
;
1124 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
1125 e24
->probability
= REG_BR_PROB_BASE
;
1127 e34
->probability
= REG_BR_PROB_BASE
;
1128 e34
->count
= all
- count
;
1131 region
= lookup_stmt_eh_region (stmt
);
1132 if (region
>=0 && tree_could_throw_p (stmt1
))
1134 add_stmt_to_eh_region (stmt1
, region
);
1135 make_eh_edges (stmt1
);
1138 if (region
>=0 && tree_could_throw_p (stmt
))
1140 tree_purge_dead_eh_edges (bb4
);
1141 make_eh_edges (stmt
);
1148 For every checked indirect/virtual call determine if most common pid of
1149 function/class method has probability more than 50%. If yes modify code of
1154 tree_ic_transform (tree stmt
)
1156 histogram_value histogram
;
1157 gcov_type val
, count
, all
;
1159 tree call
, callee
, modify
;
1160 struct cgraph_node
*direct_call
;
1162 call
= get_call_expr_in (stmt
);
1164 if (!call
|| TREE_CODE (call
) != CALL_EXPR
)
1167 callee
= CALL_EXPR_FN (call
);
1169 if (TREE_CODE (callee
) == ADDR_EXPR
)
1172 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1176 val
= histogram
->hvalue
.counters
[0];
1177 count
= histogram
->hvalue
.counters
[1];
1178 all
= histogram
->hvalue
.counters
[2];
1179 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1181 if (4 * count
<= 3 * all
)
1184 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1185 direct_call
= find_func_by_pid ((int)val
);
1187 if (direct_call
== NULL
)
1190 modify
= tree_ic (stmt
, call
, direct_call
, prob
, count
, all
);
1194 fprintf (dump_file
, "Indirect call -> direct call ");
1195 print_generic_expr (dump_file
, call
, TDF_SLIM
);
1196 fprintf (dump_file
, "=> ");
1197 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1198 fprintf (dump_file
, " transformation on insn ");
1199 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1200 fprintf (dump_file
, " to ");
1201 print_generic_stmt (dump_file
, modify
, TDF_SLIM
);
1207 /* Return true if the stringop CALL with FNDECL shall be profiled. */
1209 interesting_stringop_to_profile_p (tree fndecl
, tree call
)
1211 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1213 if (fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_MEMCPY
1214 && fcode
!= BUILT_IN_BZERO
)
1219 case BUILT_IN_MEMCPY
:
1220 case BUILT_IN_MEMPCPY
:
1221 return validate_arglist (call
,
1222 POINTER_TYPE
, POINTER_TYPE
, INTEGER_TYPE
,
1224 case BUILT_IN_MEMSET
:
1225 return validate_arglist (call
,
1226 POINTER_TYPE
, INTEGER_TYPE
, INTEGER_TYPE
,
1228 case BUILT_IN_BZERO
:
1229 return validate_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1236 /* Convert stringop (..., size)
1239 stringop (...., VALUE);
1241 stringop (...., size);
1242 assuming constant propagation of VALUE will happen later.
1245 tree_stringop_fixed_value (tree stmt
, tree value
, int prob
, gcov_type count
,
1248 tree stmt1
, stmt2
, stmt3
;
1250 tree label_decl1
= create_artificial_label ();
1251 tree label_decl2
= create_artificial_label ();
1252 tree label1
, label2
;
1253 tree bb1end
, bb2end
;
1254 basic_block bb
, bb2
, bb3
, bb4
;
1255 edge e12
, e13
, e23
, e24
, e34
;
1256 block_stmt_iterator bsi
;
1257 tree call
= get_call_expr_in (stmt
);
1258 tree blck_size
= CALL_EXPR_ARG (call
, 2);
1259 tree optype
= TREE_TYPE (blck_size
);
1262 bb
= bb_for_stmt (stmt
);
1263 bsi
= bsi_for_stmt (stmt
);
1265 if (bsi_end_p (bsi
))
1268 for (ei
= ei_start (bb
->succs
); (e34
= ei_safe_edge (ei
)); )
1269 if (!e34
->flags
& EDGE_ABNORMAL
)
1274 e34
= split_block (bb
, stmt
);
1275 bsi
= bsi_for_stmt (stmt
);
1279 tmpv
= create_tmp_var (optype
, "PROF");
1280 tmp1
= create_tmp_var (optype
, "PROF");
1281 stmt1
= build_gimple_modify_stmt (tmpv
, fold_convert (optype
, value
));
1282 stmt2
= build_gimple_modify_stmt (tmp1
, blck_size
);
1283 stmt3
= build3 (COND_EXPR
, void_type_node
,
1284 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
1285 NULL_TREE
, NULL_TREE
);
1286 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1287 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1288 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1291 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1292 stmt1
= unshare_expr (stmt
);
1293 call
= get_call_expr_in (stmt1
);
1294 CALL_EXPR_ARG (call
, 2) = value
;
1295 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1296 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1297 region
= lookup_stmt_eh_region (stmt
);
1299 add_stmt_to_eh_region (stmt1
, region
);
1301 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1302 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1305 /* Edge e23 connects bb2 to bb3, etc. */
1306 e12
= split_block (bb
, bb1end
);
1309 e23
= split_block (bb2
, bb2end
);
1311 bb3
->count
= all
- count
;
1313 e12
->flags
&= ~EDGE_FALLTHRU
;
1314 e12
->flags
|= EDGE_FALSE_VALUE
;
1315 e12
->probability
= prob
;
1318 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
1319 e13
->probability
= REG_BR_PROB_BASE
- prob
;
1320 e13
->count
= all
- count
;
1324 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
1325 e24
->probability
= REG_BR_PROB_BASE
;
1328 e34
->probability
= REG_BR_PROB_BASE
;
1329 e34
->count
= all
- count
;
1332 /* Find values inside STMT for that we want to measure histograms for
1333 division/modulo optimization. */
1335 tree_stringops_transform (block_stmt_iterator
*bsi
)
1337 tree stmt
= bsi_stmt (*bsi
);
1338 tree call
= get_call_expr_in (stmt
);
1341 enum built_in_function fcode
;
1342 histogram_value histogram
;
1343 gcov_type count
, all
, val
;
1346 unsigned int dest_align
, src_align
;
1352 fndecl
= get_callee_fndecl (call
);
1355 fcode
= DECL_FUNCTION_CODE (fndecl
);
1356 if (!interesting_stringop_to_profile_p (fndecl
, call
))
1359 if (fcode
== BUILT_IN_BZERO
)
1360 blck_size
= CALL_EXPR_ARG (call
, 1);
1362 blck_size
= CALL_EXPR_ARG (call
, 2);
1363 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1366 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1369 value
= histogram
->hvalue
.value
;
1370 val
= histogram
->hvalue
.counters
[0];
1371 count
= histogram
->hvalue
.counters
[1];
1372 all
= histogram
->hvalue
.counters
[2];
1373 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1374 /* We require that count is at least half of all; this means
1375 that for the transformation to fire the value must be constant
1376 at least 80% of time. */
1377 if ((6 * count
/ 5) < all
|| !maybe_hot_bb_p (bb_for_stmt (stmt
)))
1379 if (check_counter (stmt
, "value", all
, bb_for_stmt (stmt
)->count
))
1381 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1382 dest
= CALL_EXPR_ARG (call
, 0);
1383 dest_align
= get_pointer_alignment (dest
, BIGGEST_ALIGNMENT
);
1386 case BUILT_IN_MEMCPY
:
1387 case BUILT_IN_MEMPCPY
:
1388 src
= CALL_EXPR_ARG (call
, 1);
1389 src_align
= get_pointer_alignment (src
, BIGGEST_ALIGNMENT
);
1390 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1393 case BUILT_IN_MEMSET
:
1394 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1395 CALL_EXPR_ARG (call
, 1),
1399 case BUILT_IN_BZERO
:
1400 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1408 tree_val
= build_int_cst_wide (get_gcov_type (),
1409 (unsigned HOST_WIDE_INT
) val
,
1410 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1413 fprintf (dump_file
, "Single value %i stringop transformation on ",
1415 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1417 tree_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1423 stringop_block_profile (tree stmt
, unsigned int *expected_align
,
1424 HOST_WIDE_INT
*expected_size
)
1426 histogram_value histogram
;
1427 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1429 *expected_size
= -1;
1430 else if (!histogram
->hvalue
.counters
[1])
1432 *expected_size
= -1;
1433 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1438 size
= ((histogram
->hvalue
.counters
[0]
1439 + histogram
->hvalue
.counters
[1] / 2)
1440 / histogram
->hvalue
.counters
[1]);
1441 /* Even if we can hold bigger value in SIZE, INT_MAX
1442 is safe "infinity" for code generation strategies. */
1445 *expected_size
= size
;
1446 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1448 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1450 *expected_align
= 0;
1451 else if (!histogram
->hvalue
.counters
[0])
1453 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1454 *expected_align
= 0;
1461 count
= histogram
->hvalue
.counters
[0];
1463 while (!(count
& alignment
)
1464 && (alignment
* 2 * BITS_PER_UNIT
))
1466 *expected_align
= alignment
* BITS_PER_UNIT
;
1467 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1471 struct value_prof_hooks
{
1472 /* Find list of values for which we want to measure histograms. */
1473 void (*find_values_to_profile
) (histogram_values
*);
1475 /* Identify and exploit properties of values that are hard to analyze
1476 statically. See value-prof.c for more detail. */
1477 bool (*value_profile_transformations
) (void);
1480 /* Find values inside STMT for that we want to measure histograms for
1481 division/modulo optimization. */
1483 tree_divmod_values_to_profile (tree stmt
, histogram_values
*values
)
1485 tree assign
, lhs
, rhs
, divisor
, op0
, type
;
1486 histogram_value hist
;
1488 if (TREE_CODE (stmt
) == RETURN_EXPR
)
1489 assign
= TREE_OPERAND (stmt
, 0);
1494 || TREE_CODE (assign
) != GIMPLE_MODIFY_STMT
)
1496 lhs
= GIMPLE_STMT_OPERAND (assign
, 0);
1497 type
= TREE_TYPE (lhs
);
1498 if (!INTEGRAL_TYPE_P (type
))
1501 rhs
= GIMPLE_STMT_OPERAND (assign
, 1);
1502 switch (TREE_CODE (rhs
))
1504 case TRUNC_DIV_EXPR
:
1505 case TRUNC_MOD_EXPR
:
1506 divisor
= TREE_OPERAND (rhs
, 1);
1507 op0
= TREE_OPERAND (rhs
, 0);
1509 VEC_reserve (histogram_value
, heap
, *values
, 3);
1511 if (is_gimple_reg (divisor
))
1512 /* Check for the case where the divisor is the same value most
1514 VEC_quick_push (histogram_value
, *values
,
1515 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1518 /* For mod, check whether it is not often a noop (or replaceable by
1519 a few subtractions). */
1520 if (TREE_CODE (rhs
) == TRUNC_MOD_EXPR
1521 && TYPE_UNSIGNED (type
))
1524 /* Check for a special case where the divisor is power of 2. */
1525 VEC_quick_push (histogram_value
, *values
,
1526 gimple_alloc_histogram_value (cfun
, HIST_TYPE_POW2
,
1529 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1530 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1532 hist
->hdata
.intvl
.int_start
= 0;
1533 hist
->hdata
.intvl
.steps
= 2;
1534 VEC_quick_push (histogram_value
, *values
, hist
);
1543 /* Find calls inside STMT for that we want to measure histograms for
1544 indirect/virtual call optimization. */
1547 tree_indirect_call_to_profile (tree stmt
, histogram_values
*values
)
1552 call
= get_call_expr_in (stmt
);
1554 if (!call
|| TREE_CODE (call
) != CALL_EXPR
)
1557 callee
= CALL_EXPR_FN (call
);
1559 if (TREE_CODE (callee
) == ADDR_EXPR
)
1562 VEC_reserve (histogram_value
, heap
, *values
, 3);
1564 VEC_quick_push (histogram_value
, *values
,
1565 gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1571 /* Find values inside STMT for that we want to measure histograms for
1572 string operations. */
1574 tree_stringops_values_to_profile (tree stmt
, histogram_values
*values
)
1576 tree call
= get_call_expr_in (stmt
);
1580 enum built_in_function fcode
;
1584 fndecl
= get_callee_fndecl (call
);
1587 fcode
= DECL_FUNCTION_CODE (fndecl
);
1589 if (!interesting_stringop_to_profile_p (fndecl
, call
))
1592 dest
= CALL_EXPR_ARG (call
, 0);
1593 if (fcode
== BUILT_IN_BZERO
)
1594 blck_size
= CALL_EXPR_ARG (call
, 1);
1596 blck_size
= CALL_EXPR_ARG (call
, 2);
1598 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1600 VEC_safe_push (histogram_value
, heap
, *values
,
1601 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1603 VEC_safe_push (histogram_value
, heap
, *values
,
1604 gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1607 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1608 VEC_safe_push (histogram_value
, heap
, *values
,
1609 gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1613 /* Find values inside STMT for that we want to measure histograms and adds
1614 them to list VALUES. */
1617 tree_values_to_profile (tree stmt
, histogram_values
*values
)
1619 if (flag_value_profile_transformations
)
1621 tree_divmod_values_to_profile (stmt
, values
);
1622 tree_stringops_values_to_profile (stmt
, values
);
1623 tree_indirect_call_to_profile (stmt
, values
);
1628 tree_find_values_to_profile (histogram_values
*values
)
1631 block_stmt_iterator bsi
;
1633 histogram_value hist
= NULL
;
1637 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1638 tree_values_to_profile (bsi_stmt (bsi
), values
);
1640 for (i
= 0; VEC_iterate (histogram_value
, *values
, i
, hist
); i
++)
1644 case HIST_TYPE_INTERVAL
:
1645 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1648 case HIST_TYPE_POW2
:
1649 hist
->n_counters
= 2;
1652 case HIST_TYPE_SINGLE_VALUE
:
1653 hist
->n_counters
= 3;
1656 case HIST_TYPE_CONST_DELTA
:
1657 hist
->n_counters
= 4;
1660 case HIST_TYPE_INDIR_CALL
:
1661 hist
->n_counters
= 3;
1664 case HIST_TYPE_AVERAGE
:
1665 hist
->n_counters
= 2;
1669 hist
->n_counters
= 1;
1677 fprintf (dump_file
, "Stmt ");
1678 print_generic_expr (dump_file
, hist
->hvalue
.stmt
, TDF_SLIM
);
1679 dump_histogram_value (dump_file
, hist
);
1684 static struct value_prof_hooks tree_value_prof_hooks
= {
1685 tree_find_values_to_profile
,
1686 tree_value_profile_transformations
1690 tree_register_value_prof_hooks (void)
1692 gcc_assert (current_ir_type () == IR_GIMPLE
);
1693 value_prof_hooks
= &tree_value_prof_hooks
;
1696 /* IR-independent entry points. */
1698 find_values_to_profile (histogram_values
*values
)
1700 (value_prof_hooks
->find_values_to_profile
) (values
);
1704 value_profile_transformations (void)
1706 return (value_prof_hooks
->value_profile_transformations
) ();