1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005 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
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmpv
,
527 fold_convert (optype
, value
));
528 stmt2
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp1
, op2
);
529 stmt3
= build3 (COND_EXPR
, void_type_node
,
530 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
531 build1 (GOTO_EXPR
, void_type_node
, label_decl2
),
532 build1 (GOTO_EXPR
, void_type_node
, label_decl1
));
533 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
534 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
535 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
538 tmp2
= create_tmp_var (optype
, "PROF");
539 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
540 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp2
,
541 build2 (TREE_CODE (operation
), optype
, op1
, tmpv
));
542 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
543 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
546 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
547 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp2
,
548 build2 (TREE_CODE (operation
), optype
, op1
, op2
));
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
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp2
,
684 build2 (PLUS_EXPR
, optype
, op2
, build_int_cst (optype
, -1)));
685 stmt3
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp3
,
686 build2 (BIT_AND_EXPR
, optype
, tmp2
, op2
));
687 stmt4
= build3 (COND_EXPR
, void_type_node
,
688 build2 (NE_EXPR
, boolean_type_node
,
689 tmp3
, build_int_cst (optype
, 0)),
690 build1 (GOTO_EXPR
, void_type_node
, label_decl2
),
691 build1 (GOTO_EXPR
, void_type_node
, label_decl1
));
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
= build2 (GIMPLE_MODIFY_STMT
, optype
, 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
= build2 (GIMPLE_MODIFY_STMT
, optype
, result
,
707 build2 (TREE_CODE (operation
), optype
, op1
, op2
));
708 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
709 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
713 /* Edge e23 connects bb2 to bb3, etc. */
714 e12
= split_block (bb
, bb1end
);
717 e23
= split_block (bb2
, bb2end
);
719 bb3
->count
= all
- count
;
720 e34
= split_block (bb3
, bb3end
);
724 e12
->flags
&= ~EDGE_FALLTHRU
;
725 e12
->flags
|= EDGE_FALSE_VALUE
;
726 e12
->probability
= prob
;
729 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
730 e13
->probability
= REG_BR_PROB_BASE
- prob
;
731 e13
->count
= all
- count
;
735 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
736 e24
->probability
= REG_BR_PROB_BASE
;
739 e34
->probability
= REG_BR_PROB_BASE
;
740 e34
->count
= all
- count
;
745 /* Do transform 2) on INSN if applicable. */
747 tree_mod_pow2_value_transform (tree stmt
)
749 histogram_value histogram
;
751 gcov_type count
, wrong_values
, all
;
752 tree modify
, op
, op1
, op2
, result
, value
;
756 if (TREE_CODE (stmt
) == RETURN_EXPR
757 && TREE_OPERAND (stmt
, 0)
758 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
759 modify
= TREE_OPERAND (stmt
, 0);
760 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
762 op
= GIMPLE_STMT_OPERAND (modify
, 1);
763 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
765 code
= TREE_CODE (op
);
767 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (TREE_TYPE (op
)))
770 op1
= TREE_OPERAND (op
, 0);
771 op2
= TREE_OPERAND (op
, 1);
773 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
777 value
= histogram
->hvalue
.value
;
778 wrong_values
= histogram
->hvalue
.counters
[0];
779 count
= histogram
->hvalue
.counters
[1];
781 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
783 /* We require that we hit a power of 2 at least half of all evaluations. */
784 if (simple_cst_equal (op2
, value
) != 1 || count
< wrong_values
785 || !maybe_hot_bb_p (bb_for_stmt (stmt
)))
790 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
791 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
794 /* Compute probability of taking the optimal path. */
795 all
= count
+ wrong_values
;
797 if (check_counter (stmt
, "pow2", all
, bb_for_stmt (stmt
)->count
))
800 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
802 result
= tree_mod_pow2 (stmt
, op
, op1
, op2
, prob
, count
, all
);
804 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
809 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
810 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
811 support. Currently only NCOUNTS==0 or 1 is supported and this is
812 built into this interface. The probabilities of taking the optimal
813 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
814 COUNT2/ALL respectively within roundoff error). This generates the
815 result into a temp and returns the temp; it does not replace or alter
816 the original STMT. */
817 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
820 tree_mod_subtract (tree stmt
, tree operation
, tree op1
, tree op2
,
821 int prob1
, int prob2
, int ncounts
,
822 gcov_type count1
, gcov_type count2
, gcov_type all
)
824 tree stmt1
, stmt2
, stmt3
;
826 tree label_decl1
= create_artificial_label ();
827 tree label_decl2
= create_artificial_label ();
828 tree label_decl3
= create_artificial_label ();
829 tree label1
, label2
, label3
;
830 tree bb1end
, bb2end
= NULL_TREE
, bb3end
;
831 basic_block bb
, bb2
, bb3
, bb4
;
832 tree optype
= TREE_TYPE (operation
);
833 edge e12
, e23
= 0, e24
, e34
, e14
;
834 block_stmt_iterator bsi
;
835 tree result
= create_tmp_var (optype
, "PROF");
837 bb
= bb_for_stmt (stmt
);
838 bsi
= bsi_for_stmt (stmt
);
840 tmp1
= create_tmp_var (optype
, "PROF");
841 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, result
, op1
);
842 stmt2
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp1
, op2
);
843 stmt3
= build3 (COND_EXPR
, void_type_node
,
844 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
845 build1 (GOTO_EXPR
, void_type_node
, label_decl3
),
846 build1 (GOTO_EXPR
, void_type_node
,
847 ncounts
? label_decl1
: label_decl2
));
848 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
849 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
850 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
853 if (ncounts
) /* Assumed to be 0 or 1 */
855 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
856 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, result
,
857 build2 (MINUS_EXPR
, optype
, result
, tmp1
));
858 stmt2
= build3 (COND_EXPR
, void_type_node
,
859 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
860 build1 (GOTO_EXPR
, void_type_node
, label_decl3
),
861 build1 (GOTO_EXPR
, void_type_node
, label_decl2
));
862 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
863 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
864 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
869 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
870 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, result
,
871 build2 (TREE_CODE (operation
), optype
, result
, tmp1
));
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
;
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
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmpv
,
1076 unshare_expr (TREE_OPERAND (call
, 0)));
1077 stmt2
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp1
,
1078 fold_convert (optype
, build_addr (direct_call
->decl
,
1079 current_function_decl
)));
1080 stmt3
= build3 (COND_EXPR
, void_type_node
,
1081 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
1082 build1 (GOTO_EXPR
, void_type_node
, label_decl2
),
1083 build1 (GOTO_EXPR
, void_type_node
, label_decl1
));
1084 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1085 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1086 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1089 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1090 stmt1
= unshare_expr (stmt
);
1091 new_call
= get_call_expr_in (stmt1
);
1092 TREE_OPERAND (new_call
, 0) = build_addr (direct_call
->decl
,
1093 current_function_decl
);
1094 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1095 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1098 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1099 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1103 /* Edge e23 connects bb2 to bb3, etc. */
1104 e12
= split_block (bb
, bb1end
);
1107 e23
= split_block (bb2
, bb2end
);
1109 bb3
->count
= all
- count
;
1110 e34
= split_block (bb3
, bb3end
);
1114 e12
->flags
&= ~EDGE_FALLTHRU
;
1115 e12
->flags
|= EDGE_FALSE_VALUE
;
1116 e12
->probability
= prob
;
1119 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
1120 e13
->probability
= REG_BR_PROB_BASE
- prob
;
1121 e13
->count
= all
- count
;
1125 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
1126 e24
->probability
= REG_BR_PROB_BASE
;
1128 e34
->probability
= REG_BR_PROB_BASE
;
1129 e34
->count
= all
- count
;
1132 region
= lookup_stmt_eh_region (stmt
);
1133 if (region
>=0 && tree_could_throw_p (stmt1
))
1135 add_stmt_to_eh_region (stmt1
, region
);
1136 make_eh_edges (stmt1
);
1139 if (region
>=0 && tree_could_throw_p (stmt
))
1141 tree_purge_dead_eh_edges (bb4
);
1142 make_eh_edges (stmt
);
1149 For every checked indirect/virtual call determine if most common pid of
1150 function/class method has probability more than 50%. If yes modify code of
1155 tree_ic_transform (tree stmt
)
1157 histogram_value histogram
;
1158 gcov_type val
, count
, all
;
1160 tree call
, callee
, modify
;
1161 struct cgraph_node
*direct_call
;
1163 call
= get_call_expr_in (stmt
);
1165 if (!call
|| TREE_CODE (call
) != CALL_EXPR
)
1168 callee
= TREE_OPERAND (call
, 0);
1170 if (TREE_CODE (callee
) == ADDR_EXPR
)
1173 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1177 val
= histogram
->hvalue
.counters
[0];
1178 count
= histogram
->hvalue
.counters
[1];
1179 all
= histogram
->hvalue
.counters
[2];
1180 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1182 if (4 * count
<= 3 * all
)
1185 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1186 direct_call
= find_func_by_pid ((int)val
);
1188 if (direct_call
== NULL
)
1191 modify
= tree_ic (stmt
, call
, direct_call
, prob
, count
, all
);
1195 fprintf (dump_file
, "Indirect call -> direct call ");
1196 print_generic_expr (dump_file
, call
, TDF_SLIM
);
1197 fprintf (dump_file
, "=> ");
1198 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1199 fprintf (dump_file
, " transformation on insn ");
1200 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1201 fprintf (dump_file
, " to ");
1202 print_generic_stmt (dump_file
, modify
, TDF_SLIM
);
1208 /* Return true if the stringop FNDECL with ARGLIST shall be profiled. */
1210 interesting_stringop_to_profile_p (tree fndecl
, tree arglist
)
1212 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1214 if (fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_MEMCPY
1215 && fcode
!= BUILT_IN_BZERO
)
1220 case BUILT_IN_MEMCPY
:
1221 case BUILT_IN_MEMPCPY
:
1222 return validate_arglist (arglist
,
1223 POINTER_TYPE
, POINTER_TYPE
, INTEGER_TYPE
,
1225 case BUILT_IN_MEMSET
:
1226 return validate_arglist (arglist
,
1227 POINTER_TYPE
, INTEGER_TYPE
, INTEGER_TYPE
,
1229 case BUILT_IN_BZERO
:
1230 return validate_arglist (arglist
, POINTER_TYPE
, INTEGER_TYPE
,
1237 /* Convert stringop (..., size)
1240 stringop (...., VALUE);
1242 stringop (...., size);
1243 assuming constant propagation of VALUE will happen later.
1246 tree_stringop_fixed_value (tree stmt
, tree value
, int prob
, gcov_type count
,
1249 tree stmt1
, stmt2
, stmt3
;
1251 tree label_decl1
= create_artificial_label ();
1252 tree label_decl2
= create_artificial_label ();
1253 tree label1
, label2
;
1254 tree bb1end
, bb2end
;
1255 basic_block bb
, bb2
, bb3
, bb4
;
1256 edge e12
, e13
, e23
, e24
, e34
;
1257 block_stmt_iterator bsi
;
1258 tree call
= get_call_expr_in (stmt
);
1259 tree arglist
= TREE_OPERAND (call
, 1);
1260 tree blck_size
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist
)));
1261 tree optype
= TREE_TYPE (blck_size
);
1264 bb
= bb_for_stmt (stmt
);
1265 bsi
= bsi_for_stmt (stmt
);
1267 if (bsi_end_p (bsi
))
1270 for (ei
= ei_start (bb
->succs
); (e34
= ei_safe_edge (ei
)); )
1271 if (!e34
->flags
& EDGE_ABNORMAL
)
1276 e34
= split_block (bb
, stmt
);
1277 bsi
= bsi_for_stmt (stmt
);
1281 tmpv
= create_tmp_var (optype
, "PROF");
1282 tmp1
= create_tmp_var (optype
, "PROF");
1283 stmt1
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmpv
,
1284 fold_convert (optype
, value
));
1285 stmt2
= build2 (GIMPLE_MODIFY_STMT
, optype
, tmp1
, blck_size
);
1286 stmt3
= build3 (COND_EXPR
, void_type_node
,
1287 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
1288 build1 (GOTO_EXPR
, void_type_node
, label_decl2
),
1289 build1 (GOTO_EXPR
, void_type_node
, label_decl1
));
1290 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1291 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1292 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1295 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1296 stmt1
= unshare_expr (stmt
);
1297 call
= get_call_expr_in (stmt1
);
1298 arglist
= TREE_OPERAND (call
, 1);
1299 TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist
))) = value
;
1300 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1301 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1302 region
= lookup_stmt_eh_region (stmt
);
1304 add_stmt_to_eh_region (stmt1
, region
);
1306 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1307 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1310 /* Edge e23 connects bb2 to bb3, etc. */
1311 e12
= split_block (bb
, bb1end
);
1314 e23
= split_block (bb2
, bb2end
);
1316 bb3
->count
= all
- count
;
1318 e12
->flags
&= ~EDGE_FALLTHRU
;
1319 e12
->flags
|= EDGE_FALSE_VALUE
;
1320 e12
->probability
= prob
;
1323 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
1324 e13
->probability
= REG_BR_PROB_BASE
- prob
;
1325 e13
->count
= all
- count
;
1329 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
1330 e24
->probability
= REG_BR_PROB_BASE
;
1333 e34
->probability
= REG_BR_PROB_BASE
;
1334 e34
->count
= all
- count
;
1337 /* Find values inside STMT for that we want to measure histograms for
1338 division/modulo optimization. */
1340 tree_stringops_transform (block_stmt_iterator
*bsi
)
1342 tree stmt
= bsi_stmt (*bsi
);
1343 tree call
= get_call_expr_in (stmt
);
1347 enum built_in_function fcode
;
1348 histogram_value histogram
;
1349 gcov_type count
, all
, val
;
1352 unsigned int dest_align
, src_align
;
1358 fndecl
= get_callee_fndecl (call
);
1361 fcode
= DECL_FUNCTION_CODE (fndecl
);
1362 arglist
= TREE_OPERAND (call
, 1);
1363 if (!interesting_stringop_to_profile_p (fndecl
, arglist
))
1366 if (fcode
== BUILT_IN_BZERO
)
1367 blck_size
= TREE_VALUE (TREE_CHAIN (arglist
));
1369 blck_size
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist
)));
1370 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1373 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1376 value
= histogram
->hvalue
.value
;
1377 val
= histogram
->hvalue
.counters
[0];
1378 count
= histogram
->hvalue
.counters
[1];
1379 all
= histogram
->hvalue
.counters
[2];
1380 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1381 /* We require that count is at least half of all; this means
1382 that for the transformation to fire the value must be constant
1383 at least 80% of time. */
1384 if ((6 * count
/ 5) < all
|| !maybe_hot_bb_p (bb_for_stmt (stmt
)))
1386 if (check_counter (stmt
, "value", all
, bb_for_stmt (stmt
)->count
))
1388 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1389 dest
= TREE_VALUE (arglist
);
1390 dest_align
= get_pointer_alignment (dest
, BIGGEST_ALIGNMENT
);
1393 case BUILT_IN_MEMCPY
:
1394 case BUILT_IN_MEMPCPY
:
1395 src
= TREE_VALUE (TREE_CHAIN (arglist
));
1396 src_align
= get_pointer_alignment (src
, BIGGEST_ALIGNMENT
);
1397 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1400 case BUILT_IN_MEMSET
:
1401 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1402 TREE_VALUE (TREE_CHAIN (arglist
)),
1406 case BUILT_IN_BZERO
:
1407 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1415 tree_val
= build_int_cst_wide (get_gcov_type (),
1416 (unsigned HOST_WIDE_INT
) val
,
1417 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1420 fprintf (dump_file
, "Single value %i stringop transformation on ",
1422 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1424 tree_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1430 stringop_block_profile (tree stmt
, unsigned int *expected_align
,
1431 HOST_WIDE_INT
*expected_size
)
1433 histogram_value histogram
;
1434 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1436 *expected_size
= -1;
1437 else if (!histogram
->hvalue
.counters
[1])
1439 *expected_size
= -1;
1440 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1445 size
= ((histogram
->hvalue
.counters
[0]
1446 + histogram
->hvalue
.counters
[1] / 2)
1447 / histogram
->hvalue
.counters
[1]);
1448 /* Even if we can hold bigger value in SIZE, INT_MAX
1449 is safe "infinity" for code generation strategies. */
1452 *expected_size
= size
;
1453 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1455 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1457 *expected_align
= 0;
1458 else if (!histogram
->hvalue
.counters
[0])
1460 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1461 *expected_align
= 0;
1468 count
= histogram
->hvalue
.counters
[0];
1470 while (!(count
& alignment
)
1471 && (alignment
* 2 * BITS_PER_UNIT
))
1473 *expected_align
= alignment
* BITS_PER_UNIT
;
1474 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1478 struct value_prof_hooks
{
1479 /* Find list of values for which we want to measure histograms. */
1480 void (*find_values_to_profile
) (histogram_values
*);
1482 /* Identify and exploit properties of values that are hard to analyze
1483 statically. See value-prof.c for more detail. */
1484 bool (*value_profile_transformations
) (void);
1487 /* Find values inside STMT for that we want to measure histograms for
1488 division/modulo optimization. */
1490 tree_divmod_values_to_profile (tree stmt
, histogram_values
*values
)
1492 tree assign
, lhs
, rhs
, divisor
, op0
, type
;
1493 histogram_value hist
;
1495 if (TREE_CODE (stmt
) == RETURN_EXPR
)
1496 assign
= TREE_OPERAND (stmt
, 0);
1501 || TREE_CODE (assign
) != GIMPLE_MODIFY_STMT
)
1503 lhs
= GIMPLE_STMT_OPERAND (assign
, 0);
1504 type
= TREE_TYPE (lhs
);
1505 if (!INTEGRAL_TYPE_P (type
))
1508 rhs
= GIMPLE_STMT_OPERAND (assign
, 1);
1509 switch (TREE_CODE (rhs
))
1511 case TRUNC_DIV_EXPR
:
1512 case TRUNC_MOD_EXPR
:
1513 divisor
= TREE_OPERAND (rhs
, 1);
1514 op0
= TREE_OPERAND (rhs
, 0);
1516 VEC_reserve (histogram_value
, heap
, *values
, 3);
1518 if (is_gimple_reg (divisor
))
1519 /* Check for the case where the divisor is the same value most
1521 VEC_quick_push (histogram_value
, *values
,
1522 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1525 /* For mod, check whether it is not often a noop (or replaceable by
1526 a few subtractions). */
1527 if (TREE_CODE (rhs
) == TRUNC_MOD_EXPR
1528 && TYPE_UNSIGNED (type
))
1531 /* Check for a special case where the divisor is power of 2. */
1532 VEC_quick_push (histogram_value
, *values
,
1533 gimple_alloc_histogram_value (cfun
, HIST_TYPE_POW2
,
1536 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1537 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1539 hist
->hdata
.intvl
.int_start
= 0;
1540 hist
->hdata
.intvl
.steps
= 2;
1541 VEC_quick_push (histogram_value
, *values
, hist
);
1550 /* Find calls inside STMT for that we want to measure histograms for
1551 indirect/virtual call optimization. */
1554 tree_indirect_call_to_profile (tree stmt
, histogram_values
*values
)
1559 call
= get_call_expr_in (stmt
);
1561 if (!call
|| TREE_CODE (call
) != CALL_EXPR
)
1564 callee
= TREE_OPERAND (call
, 0);
1566 if (TREE_CODE (callee
) == ADDR_EXPR
)
1569 VEC_reserve (histogram_value
, heap
, *values
, 3);
1571 VEC_quick_push (histogram_value
, *values
,
1572 gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1578 /* Find values inside STMT for that we want to measure histograms for
1579 string operations. */
1581 tree_stringops_values_to_profile (tree stmt
, histogram_values
*values
)
1583 tree call
= get_call_expr_in (stmt
);
1588 enum built_in_function fcode
;
1592 fndecl
= get_callee_fndecl (call
);
1595 fcode
= DECL_FUNCTION_CODE (fndecl
);
1596 arglist
= TREE_OPERAND (call
, 1);
1598 if (!interesting_stringop_to_profile_p (fndecl
, arglist
))
1601 dest
= TREE_VALUE (arglist
);
1602 if (fcode
== BUILT_IN_BZERO
)
1603 blck_size
= TREE_VALUE (TREE_CHAIN (arglist
));
1605 blck_size
= TREE_VALUE (TREE_CHAIN (TREE_CHAIN (arglist
)));
1607 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1609 VEC_safe_push (histogram_value
, heap
, *values
,
1610 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1612 VEC_safe_push (histogram_value
, heap
, *values
,
1613 gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1616 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1617 VEC_safe_push (histogram_value
, heap
, *values
,
1618 gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1622 /* Find values inside STMT for that we want to measure histograms and adds
1623 them to list VALUES. */
1626 tree_values_to_profile (tree stmt
, histogram_values
*values
)
1628 if (flag_value_profile_transformations
)
1630 tree_divmod_values_to_profile (stmt
, values
);
1631 tree_stringops_values_to_profile (stmt
, values
);
1632 tree_indirect_call_to_profile (stmt
, values
);
1637 tree_find_values_to_profile (histogram_values
*values
)
1640 block_stmt_iterator bsi
;
1642 histogram_value hist
= NULL
;
1646 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1647 tree_values_to_profile (bsi_stmt (bsi
), values
);
1649 for (i
= 0; VEC_iterate (histogram_value
, *values
, i
, hist
); i
++)
1653 case HIST_TYPE_INTERVAL
:
1654 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1657 case HIST_TYPE_POW2
:
1658 hist
->n_counters
= 2;
1661 case HIST_TYPE_SINGLE_VALUE
:
1662 hist
->n_counters
= 3;
1665 case HIST_TYPE_CONST_DELTA
:
1666 hist
->n_counters
= 4;
1669 case HIST_TYPE_INDIR_CALL
:
1670 hist
->n_counters
= 3;
1673 case HIST_TYPE_AVERAGE
:
1674 hist
->n_counters
= 2;
1678 hist
->n_counters
= 1;
1686 fprintf (dump_file
, "Stmt ");
1687 print_generic_expr (dump_file
, hist
->hvalue
.stmt
, TDF_SLIM
);
1688 dump_histogram_value (dump_file
, hist
);
1693 static struct value_prof_hooks tree_value_prof_hooks
= {
1694 tree_find_values_to_profile
,
1695 tree_value_profile_transformations
1699 tree_register_value_prof_hooks (void)
1701 gcc_assert (current_ir_type () == IR_GIMPLE
);
1702 value_prof_hooks
= &tree_value_prof_hooks
;
1705 /* IR-independent entry points. */
1707 find_values_to_profile (histogram_values
*values
)
1709 (value_prof_hooks
->find_values_to_profile
) (values
);
1713 value_profile_transformations (void)
1715 return (value_prof_hooks
->value_profile_transformations
) ();