1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "value-prof.h"
32 #include "insn-config.h"
37 #include "tree-flow.h"
38 #include "tree-flow-inline.h"
39 #include "diagnostic.h"
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 (((const_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 ((const_histogram_value
) x
)->hvalue
.stmt
== (const_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 (histogram_value
) 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
= XNEWVAR (gcov_type
, 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);
341 /* Move all histograms associated with OSTMT to STMT. */
344 gimple_move_stmt_histograms (struct function
*fun
, tree stmt
, tree ostmt
)
346 histogram_value val
= gimple_histogram_value (fun
, ostmt
);
349 /* The following three statements can't be reordered,
350 because histogram hashtab relies on stmt field value
351 for finding the exact slot. */
352 set_histogram_value (fun
, ostmt
, NULL
);
353 for (; val
!= NULL
; val
= val
->hvalue
.next
)
354 val
->hvalue
.stmt
= stmt
;
355 set_histogram_value (fun
, stmt
, val
);
359 static bool error_found
= false;
361 /* Helper function for verify_histograms. For each histogram reachable via htab
362 walk verify that it was reached via statement walk. */
365 visit_hist (void **slot
, void *data
)
367 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
368 histogram_value hist
= *(histogram_value
*) slot
;
369 if (!pointer_set_contains (visited
, hist
))
371 error ("Dead histogram");
372 dump_histogram_value (stderr
, hist
);
373 debug_generic_stmt (hist
->hvalue
.stmt
);
379 /* Verify sanity of the histograms. */
382 verify_histograms (void)
385 block_stmt_iterator bsi
;
386 histogram_value hist
;
387 struct pointer_set_t
*visited_hists
;
390 visited_hists
= pointer_set_create ();
392 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
394 tree stmt
= bsi_stmt (bsi
);
396 for (hist
= gimple_histogram_value (cfun
, stmt
); hist
; hist
= hist
->hvalue
.next
)
398 if (hist
->hvalue
.stmt
!= stmt
)
400 error ("Histogram value statement does not correspond to statement"
401 " it is associated with");
402 debug_generic_stmt (stmt
);
403 dump_histogram_value (stderr
, hist
);
406 pointer_set_insert (visited_hists
, hist
);
409 if (VALUE_HISTOGRAMS (cfun
))
410 htab_traverse (VALUE_HISTOGRAMS (cfun
), visit_hist
, visited_hists
);
411 pointer_set_destroy (visited_hists
);
413 internal_error ("verify_histograms failed");
416 /* Helper function for verify_histograms. For each histogram reachable via htab
417 walk verify that it was reached via statement walk. */
420 free_hist (void **slot
, void *data ATTRIBUTE_UNUSED
)
422 histogram_value hist
= *(histogram_value
*) slot
;
423 free (hist
->hvalue
.counters
);
424 #ifdef ENABLE_CHECKING
425 memset (hist
, 0xab, sizeof (*hist
));
432 free_histograms (void)
434 if (VALUE_HISTOGRAMS (cfun
))
436 htab_traverse (VALUE_HISTOGRAMS (cfun
), free_hist
, NULL
);
437 htab_delete (VALUE_HISTOGRAMS (cfun
));
438 VALUE_HISTOGRAMS (cfun
) = NULL
;
442 /* The overall number of invocations of the counter should match execution count
443 of basic block. Report it as error rather than internal error as it might
444 mean that user has misused the profile somehow. */
446 check_counter (tree stmt
, const char * name
, gcov_type all
, gcov_type bb_count
)
451 locus
= (stmt
!= NULL
&& EXPR_HAS_LOCATION (stmt
)
453 : &DECL_SOURCE_LOCATION (current_function_decl
));
454 error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)",
455 locus
, name
, (int)all
, (int)bb_count
);
461 /* Tree based transformations. */
463 tree_value_profile_transformations (void)
466 block_stmt_iterator bsi
;
467 bool changed
= false;
471 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
473 tree stmt
= bsi_stmt (bsi
);
474 histogram_value th
= gimple_histogram_value (cfun
, stmt
);
480 fprintf (dump_file
, "Trying transformations on stmt ");
481 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
482 dump_histograms_for_stmt (cfun
, dump_file
, stmt
);
485 /* Transformations: */
486 /* The order of things in this conditional controls which
487 transformation is used when more than one is applicable. */
488 /* It is expected that any code added by the transformations
489 will be added before the current statement, and that the
490 current statement remain valid (although possibly
491 modified) upon return. */
492 if (flag_value_profile_transformations
493 && (tree_mod_subtract_transform (stmt
)
494 || tree_divmod_fixed_value_transform (stmt
)
495 || tree_mod_pow2_value_transform (stmt
)
496 || tree_stringops_transform (&bsi
)
497 || tree_ic_transform (stmt
)))
499 stmt
= bsi_stmt (bsi
);
501 /* Original statement may no longer be in the same block. */
502 if (bb
!= bb_for_stmt (stmt
))
504 bb
= bb_for_stmt (stmt
);
505 bsi
= bsi_for_stmt (stmt
);
519 /* Generate code for transformation 1 (with OPERATION, operands OP1
520 and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
521 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
522 within roundoff error). This generates the result into a temp and returns
523 the temp; it does not replace or alter the original STMT. */
525 tree_divmod_fixed_value (tree stmt
, tree operation
,
526 tree op1
, tree op2
, tree value
, int prob
, gcov_type count
,
529 tree stmt1
, stmt2
, stmt3
;
530 tree tmp1
, tmp2
, tmpv
;
531 tree label_decl1
= create_artificial_label ();
532 tree label_decl2
= create_artificial_label ();
534 tree bb1end
, bb2end
, bb3end
;
535 basic_block bb
, bb2
, bb3
, bb4
;
536 tree optype
= TREE_TYPE (operation
);
537 edge e12
, e13
, e23
, e24
, e34
;
538 block_stmt_iterator bsi
;
540 bb
= bb_for_stmt (stmt
);
541 bsi
= bsi_for_stmt (stmt
);
543 tmpv
= create_tmp_var (optype
, "PROF");
544 tmp1
= create_tmp_var (optype
, "PROF");
545 stmt1
= build_gimple_modify_stmt (tmpv
, fold_convert (optype
, value
));
546 stmt2
= build_gimple_modify_stmt (tmp1
, op2
);
547 stmt3
= build3 (COND_EXPR
, void_type_node
,
548 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
549 NULL_TREE
, NULL_TREE
);
550 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
551 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
552 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
555 tmp2
= create_tmp_var (optype
, "PROF");
556 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
557 stmt1
= build_gimple_modify_stmt (tmp2
,
558 build2 (TREE_CODE (operation
), optype
,
560 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
561 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
564 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
565 stmt1
= build_gimple_modify_stmt (tmp2
,
566 build2 (TREE_CODE (operation
), optype
,
568 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
569 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
573 /* Edge e23 connects bb2 to bb3, etc. */
574 e12
= split_block (bb
, bb1end
);
577 e23
= split_block (bb2
, bb2end
);
579 bb3
->count
= all
- count
;
580 e34
= split_block (bb3
, bb3end
);
584 e12
->flags
&= ~EDGE_FALLTHRU
;
585 e12
->flags
|= EDGE_FALSE_VALUE
;
586 e12
->probability
= prob
;
589 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
590 e13
->probability
= REG_BR_PROB_BASE
- prob
;
591 e13
->count
= all
- count
;
595 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
596 e24
->probability
= REG_BR_PROB_BASE
;
599 e34
->probability
= REG_BR_PROB_BASE
;
600 e34
->count
= all
- count
;
605 /* Do transform 1) on INSN if applicable. */
607 tree_divmod_fixed_value_transform (tree stmt
)
609 histogram_value histogram
;
611 gcov_type val
, count
, all
;
612 tree modify
, op
, op1
, op2
, result
, value
, tree_val
;
616 if (TREE_CODE (stmt
) == RETURN_EXPR
617 && TREE_OPERAND (stmt
, 0)
618 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
619 modify
= TREE_OPERAND (stmt
, 0);
620 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
622 op
= GIMPLE_STMT_OPERAND (modify
, 1);
623 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
625 code
= TREE_CODE (op
);
627 if (code
!= TRUNC_DIV_EXPR
&& code
!= TRUNC_MOD_EXPR
)
630 op1
= TREE_OPERAND (op
, 0);
631 op2
= TREE_OPERAND (op
, 1);
633 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
637 value
= histogram
->hvalue
.value
;
638 val
= histogram
->hvalue
.counters
[0];
639 count
= histogram
->hvalue
.counters
[1];
640 all
= histogram
->hvalue
.counters
[2];
641 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
643 /* We require that count is at least half of all; this means
644 that for the transformation to fire the value must be constant
645 at least 50% of time (and 75% gives the guarantee of usage). */
646 if (simple_cst_equal (op2
, value
) != 1 || 2 * count
< all
647 || !maybe_hot_bb_p (bb_for_stmt (stmt
)))
650 if (check_counter (stmt
, "value", all
, bb_for_stmt (stmt
)->count
))
653 /* Compute probability of taking the optimal path. */
655 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
659 tree_val
= build_int_cst_wide (get_gcov_type (),
660 (unsigned HOST_WIDE_INT
) val
,
661 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
662 result
= tree_divmod_fixed_value (stmt
, op
, op1
, op2
, tree_val
, prob
, count
, all
);
666 fprintf (dump_file
, "Div/mod by constant ");
667 print_generic_expr (dump_file
, value
, TDF_SLIM
);
668 fprintf (dump_file
, "=");
669 print_generic_expr (dump_file
, tree_val
, TDF_SLIM
);
670 fprintf (dump_file
, " transformation on insn ");
671 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
674 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
679 /* Generate code for transformation 2 (with OPERATION, operands OP1
680 and OP2, parent modify-expr STMT and probability of taking the optimal
681 path PROB, which is equivalent to COUNT/ALL within roundoff error).
682 This generates the result into a temp and returns
683 the temp; it does not replace or alter the original STMT. */
685 tree_mod_pow2 (tree stmt
, tree operation
, tree op1
, tree op2
, int prob
,
686 gcov_type count
, gcov_type all
)
688 tree stmt1
, stmt2
, stmt3
, stmt4
;
690 tree label_decl1
= create_artificial_label ();
691 tree label_decl2
= create_artificial_label ();
693 tree bb1end
, bb2end
, bb3end
;
694 basic_block bb
, bb2
, bb3
, bb4
;
695 tree optype
= TREE_TYPE (operation
);
696 edge e12
, e13
, e23
, e24
, e34
;
697 block_stmt_iterator bsi
;
698 tree result
= create_tmp_var (optype
, "PROF");
700 bb
= bb_for_stmt (stmt
);
701 bsi
= bsi_for_stmt (stmt
);
703 tmp2
= create_tmp_var (optype
, "PROF");
704 tmp3
= create_tmp_var (optype
, "PROF");
705 stmt2
= build_gimple_modify_stmt (tmp2
,
706 build2 (PLUS_EXPR
, optype
, op2
,
707 build_int_cst (optype
, -1)));
708 stmt3
= build_gimple_modify_stmt (tmp3
,
709 build2 (BIT_AND_EXPR
, optype
, tmp2
, op2
));
710 stmt4
= build3 (COND_EXPR
, void_type_node
,
711 build2 (NE_EXPR
, boolean_type_node
,
712 tmp3
, build_int_cst (optype
, 0)),
713 NULL_TREE
, NULL_TREE
);
714 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
715 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
716 bsi_insert_before (&bsi
, stmt4
, BSI_SAME_STMT
);
719 /* tmp2 == op2-1 inherited from previous block */
720 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
721 stmt1
= build_gimple_modify_stmt (result
,
722 build2 (BIT_AND_EXPR
, optype
, op1
, tmp2
));
723 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
724 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
727 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
728 stmt1
= build_gimple_modify_stmt (result
,
729 build2 (TREE_CODE (operation
), optype
,
731 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
732 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
736 /* Edge e23 connects bb2 to bb3, etc. */
737 e12
= split_block (bb
, bb1end
);
740 e23
= split_block (bb2
, bb2end
);
742 bb3
->count
= all
- count
;
743 e34
= split_block (bb3
, bb3end
);
747 e12
->flags
&= ~EDGE_FALLTHRU
;
748 e12
->flags
|= EDGE_FALSE_VALUE
;
749 e12
->probability
= prob
;
752 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
753 e13
->probability
= REG_BR_PROB_BASE
- prob
;
754 e13
->count
= all
- count
;
758 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
759 e24
->probability
= REG_BR_PROB_BASE
;
762 e34
->probability
= REG_BR_PROB_BASE
;
763 e34
->count
= all
- count
;
768 /* Do transform 2) on INSN if applicable. */
770 tree_mod_pow2_value_transform (tree stmt
)
772 histogram_value histogram
;
774 gcov_type count
, wrong_values
, all
;
775 tree modify
, op
, op1
, op2
, result
, value
;
779 if (TREE_CODE (stmt
) == RETURN_EXPR
780 && TREE_OPERAND (stmt
, 0)
781 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
782 modify
= TREE_OPERAND (stmt
, 0);
783 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
785 op
= GIMPLE_STMT_OPERAND (modify
, 1);
786 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
788 code
= TREE_CODE (op
);
790 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (TREE_TYPE (op
)))
793 op1
= TREE_OPERAND (op
, 0);
794 op2
= TREE_OPERAND (op
, 1);
796 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_POW2
);
800 value
= histogram
->hvalue
.value
;
801 wrong_values
= histogram
->hvalue
.counters
[0];
802 count
= histogram
->hvalue
.counters
[1];
804 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
806 /* We require that we hit a power of 2 at least half of all evaluations. */
807 if (simple_cst_equal (op2
, value
) != 1 || count
< wrong_values
808 || !maybe_hot_bb_p (bb_for_stmt (stmt
)))
813 fprintf (dump_file
, "Mod power of 2 transformation on insn ");
814 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
817 /* Compute probability of taking the optimal path. */
818 all
= count
+ wrong_values
;
820 if (check_counter (stmt
, "pow2", all
, bb_for_stmt (stmt
)->count
))
824 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
828 result
= tree_mod_pow2 (stmt
, op
, op1
, op2
, prob
, count
, all
);
830 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
835 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
836 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
837 support. Currently only NCOUNTS==0 or 1 is supported and this is
838 built into this interface. The probabilities of taking the optimal
839 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
840 COUNT2/ALL respectively within roundoff error). This generates the
841 result into a temp and returns the temp; it does not replace or alter
842 the original STMT. */
843 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
846 tree_mod_subtract (tree stmt
, tree operation
, tree op1
, tree op2
,
847 int prob1
, int prob2
, int ncounts
,
848 gcov_type count1
, gcov_type count2
, gcov_type all
)
850 tree stmt1
, stmt2
, stmt3
;
852 tree label_decl1
= create_artificial_label ();
853 tree label_decl2
= create_artificial_label ();
854 tree label_decl3
= create_artificial_label ();
855 tree label1
, label2
, label3
;
856 tree bb1end
, bb2end
= NULL_TREE
, bb3end
;
857 basic_block bb
, bb2
, bb3
, bb4
;
858 tree optype
= TREE_TYPE (operation
);
859 edge e12
, e23
= 0, e24
, e34
, e14
;
860 block_stmt_iterator bsi
;
861 tree result
= create_tmp_var (optype
, "PROF");
863 bb
= bb_for_stmt (stmt
);
864 bsi
= bsi_for_stmt (stmt
);
866 tmp1
= create_tmp_var (optype
, "PROF");
867 stmt1
= build_gimple_modify_stmt (result
, op1
);
868 stmt2
= build_gimple_modify_stmt (tmp1
, op2
);
869 stmt3
= build3 (COND_EXPR
, void_type_node
,
870 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
871 NULL_TREE
, NULL_TREE
);
872 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
873 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
874 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
877 if (ncounts
) /* Assumed to be 0 or 1 */
879 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
880 stmt1
= build_gimple_modify_stmt (result
,
881 build2 (MINUS_EXPR
, optype
,
883 stmt2
= build3 (COND_EXPR
, void_type_node
,
884 build2 (LT_EXPR
, boolean_type_node
, result
, tmp1
),
885 NULL_TREE
, NULL_TREE
);
886 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
887 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
888 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
893 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
894 stmt1
= build_gimple_modify_stmt (result
,
895 build2 (TREE_CODE (operation
), optype
,
897 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
898 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
901 label3
= build1 (LABEL_EXPR
, void_type_node
, label_decl3
);
902 bsi_insert_before (&bsi
, label3
, BSI_SAME_STMT
);
905 /* Edge e23 connects bb2 to bb3, etc. */
906 /* However block 3 is optional; if it is not there, references
907 to 3 really refer to block 2. */
908 e12
= split_block (bb
, bb1end
);
910 bb2
->count
= all
- count1
;
912 if (ncounts
) /* Assumed to be 0 or 1. */
914 e23
= split_block (bb2
, bb2end
);
916 bb3
->count
= all
- count1
- count2
;
919 e34
= split_block (ncounts
? bb3
: bb2
, bb3end
);
923 e12
->flags
&= ~EDGE_FALLTHRU
;
924 e12
->flags
|= EDGE_FALSE_VALUE
;
925 e12
->probability
= REG_BR_PROB_BASE
- prob1
;
926 e12
->count
= all
- count1
;
928 e14
= make_edge (bb
, bb4
, EDGE_TRUE_VALUE
);
929 e14
->probability
= prob1
;
932 if (ncounts
) /* Assumed to be 0 or 1. */
934 e23
->flags
&= ~EDGE_FALLTHRU
;
935 e23
->flags
|= EDGE_FALSE_VALUE
;
936 e23
->count
= all
- count1
- count2
;
937 e23
->probability
= REG_BR_PROB_BASE
- prob2
;
939 e24
= make_edge (bb2
, bb4
, EDGE_TRUE_VALUE
);
940 e24
->probability
= prob2
;
944 e34
->probability
= REG_BR_PROB_BASE
;
945 e34
->count
= all
- count1
- count2
;
950 /* Do transforms 3) and 4) on INSN if applicable. */
952 tree_mod_subtract_transform (tree stmt
)
954 histogram_value histogram
;
956 gcov_type count
, wrong_values
, all
;
957 tree modify
, op
, op1
, op2
, result
, value
;
958 gcov_type prob1
, prob2
;
959 unsigned int i
, steps
;
960 gcov_type count1
, count2
;
963 if (TREE_CODE (stmt
) == RETURN_EXPR
964 && TREE_OPERAND (stmt
, 0)
965 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
966 modify
= TREE_OPERAND (stmt
, 0);
967 if (TREE_CODE (modify
) != GIMPLE_MODIFY_STMT
)
969 op
= GIMPLE_STMT_OPERAND (modify
, 1);
970 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
)))
972 code
= TREE_CODE (op
);
974 if (code
!= TRUNC_MOD_EXPR
|| !TYPE_UNSIGNED (TREE_TYPE (op
)))
977 op1
= TREE_OPERAND (op
, 0);
978 op2
= TREE_OPERAND (op
, 1);
980 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INTERVAL
);
984 value
= histogram
->hvalue
.value
;
987 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
988 all
+= histogram
->hvalue
.counters
[i
];
990 wrong_values
+= histogram
->hvalue
.counters
[i
];
991 wrong_values
+= histogram
->hvalue
.counters
[i
+1];
992 steps
= histogram
->hdata
.intvl
.steps
;
994 count1
= histogram
->hvalue
.counters
[0];
995 count2
= histogram
->hvalue
.counters
[1];
997 /* Compute probability of taking the optimal path. */
998 if (check_counter (stmt
, "interval", all
, bb_for_stmt (stmt
)->count
))
1000 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1004 /* We require that we use just subtractions in at least 50% of all
1007 for (i
= 0; i
< histogram
->hdata
.intvl
.steps
; i
++)
1009 count
+= histogram
->hvalue
.counters
[i
];
1010 if (count
* 2 >= all
)
1014 || !maybe_hot_bb_p (bb_for_stmt (stmt
)))
1017 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1020 fprintf (dump_file
, "Mod subtract transformation on insn ");
1021 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1024 /* Compute probability of taking the optimal path(s). */
1027 prob1
= (count1
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1028 prob2
= (count2
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1035 /* In practice, "steps" is always 2. This interface reflects this,
1036 and will need to be changed if "steps" can change. */
1037 result
= tree_mod_subtract (stmt
, op
, op1
, op2
, prob1
, prob2
, i
,
1038 count1
, count2
, all
);
1040 GIMPLE_STMT_OPERAND (modify
, 1) = result
;
1045 static struct cgraph_node
** pid_map
= NULL
;
1047 /* Initialize map of pids (pid -> cgraph node) */
1052 struct cgraph_node
*n
;
1054 if (pid_map
!= NULL
)
1058 = (struct cgraph_node
**) xmalloc (sizeof (struct cgraph_node
*) * cgraph_max_pid
);
1060 for (n
= cgraph_nodes
; n
; n
= n
->next
)
1063 pid_map
[n
->pid
] = n
;
1067 /* Return cgraph node for function with pid */
1069 static inline struct cgraph_node
*
1070 find_func_by_pid (int pid
)
1074 return pid_map
[pid
];
1077 /* Do transformation
1079 if (actual_callee_address == address_of_most_common_function/method)
1086 tree_ic (tree stmt
, tree call
, struct cgraph_node
* direct_call
,
1087 int prob
, gcov_type count
, gcov_type all
)
1089 tree stmt1
, stmt2
, stmt3
;
1090 tree tmp1
, tmpv
, tmp
;
1091 tree label_decl1
= create_artificial_label ();
1092 tree label_decl2
= create_artificial_label ();
1093 tree label1
, label2
;
1094 tree bb1end
, bb2end
, bb3end
;
1096 basic_block bb
, bb2
, bb3
, bb4
;
1097 tree optype
= build_pointer_type (void_type_node
);
1098 edge e12
, e13
, e23
, e24
, e34
;
1099 block_stmt_iterator bsi
;
1102 bb
= bb_for_stmt (stmt
);
1103 bsi
= bsi_for_stmt (stmt
);
1105 tmpv
= create_tmp_var (optype
, "PROF");
1106 tmp1
= create_tmp_var (optype
, "PROF");
1107 stmt1
= build_gimple_modify_stmt (tmpv
,
1108 unshare_expr (CALL_EXPR_FN (call
)));
1109 tmp
= fold_convert (optype
, build_addr (direct_call
->decl
,
1110 current_function_decl
));
1111 stmt2
= build_gimple_modify_stmt (tmp1
, tmp
);
1112 stmt3
= build3 (COND_EXPR
, void_type_node
,
1113 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
1114 NULL_TREE
, NULL_TREE
);
1115 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1116 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1117 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1120 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1121 stmt1
= unshare_expr (stmt
);
1122 new_call
= get_call_expr_in (stmt1
);
1123 CALL_EXPR_FN (new_call
) = build_addr (direct_call
->decl
,
1124 current_function_decl
);
1125 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1126 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1129 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1130 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1134 /* Edge e23 connects bb2 to bb3, etc. */
1135 e12
= split_block (bb
, bb1end
);
1138 e23
= split_block (bb2
, bb2end
);
1140 bb3
->count
= all
- count
;
1141 e34
= split_block (bb3
, bb3end
);
1145 e12
->flags
&= ~EDGE_FALLTHRU
;
1146 e12
->flags
|= EDGE_FALSE_VALUE
;
1147 e12
->probability
= prob
;
1150 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
1151 e13
->probability
= REG_BR_PROB_BASE
- prob
;
1152 e13
->count
= all
- count
;
1156 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
1157 e24
->probability
= REG_BR_PROB_BASE
;
1159 e34
->probability
= REG_BR_PROB_BASE
;
1160 e34
->count
= all
- count
;
1163 region
= lookup_stmt_eh_region (stmt
);
1164 if (region
>=0 && tree_could_throw_p (stmt1
))
1166 add_stmt_to_eh_region (stmt1
, region
);
1167 make_eh_edges (stmt1
);
1170 if (region
>=0 && tree_could_throw_p (stmt
))
1172 tree_purge_dead_eh_edges (bb4
);
1173 make_eh_edges (stmt
);
1180 For every checked indirect/virtual call determine if most common pid of
1181 function/class method has probability more than 50%. If yes modify code of
1186 tree_ic_transform (tree stmt
)
1188 histogram_value histogram
;
1189 gcov_type val
, count
, all
;
1191 tree call
, callee
, modify
;
1192 struct cgraph_node
*direct_call
;
1194 call
= get_call_expr_in (stmt
);
1196 if (!call
|| TREE_CODE (call
) != CALL_EXPR
)
1199 callee
= CALL_EXPR_FN (call
);
1201 if (TREE_CODE (callee
) == ADDR_EXPR
)
1204 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_INDIR_CALL
);
1208 val
= histogram
->hvalue
.counters
[0];
1209 count
= histogram
->hvalue
.counters
[1];
1210 all
= histogram
->hvalue
.counters
[2];
1211 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1213 if (4 * count
<= 3 * all
)
1217 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1220 direct_call
= find_func_by_pid ((int)val
);
1222 if (direct_call
== NULL
)
1225 modify
= tree_ic (stmt
, call
, direct_call
, prob
, count
, all
);
1229 fprintf (dump_file
, "Indirect call -> direct call ");
1230 print_generic_expr (dump_file
, call
, TDF_SLIM
);
1231 fprintf (dump_file
, "=> ");
1232 print_generic_expr (dump_file
, direct_call
->decl
, TDF_SLIM
);
1233 fprintf (dump_file
, " transformation on insn ");
1234 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1235 fprintf (dump_file
, " to ");
1236 print_generic_stmt (dump_file
, modify
, TDF_SLIM
);
1237 fprintf (dump_file
, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1238 " hist->all "HOST_WIDEST_INT_PRINT_DEC
"\n", count
, all
);
1244 /* Return true if the stringop CALL with FNDECL shall be profiled. */
1246 interesting_stringop_to_profile_p (tree fndecl
, tree call
)
1248 enum built_in_function fcode
= DECL_FUNCTION_CODE (fndecl
);
1250 if (fcode
!= BUILT_IN_MEMCPY
&& fcode
!= BUILT_IN_MEMPCPY
1251 && fcode
!= BUILT_IN_MEMSET
&& fcode
!= BUILT_IN_BZERO
)
1256 case BUILT_IN_MEMCPY
:
1257 case BUILT_IN_MEMPCPY
:
1258 return validate_arglist (call
,
1259 POINTER_TYPE
, POINTER_TYPE
, INTEGER_TYPE
,
1261 case BUILT_IN_MEMSET
:
1262 return validate_arglist (call
,
1263 POINTER_TYPE
, INTEGER_TYPE
, INTEGER_TYPE
,
1265 case BUILT_IN_BZERO
:
1266 return validate_arglist (call
, POINTER_TYPE
, INTEGER_TYPE
,
1273 /* Convert stringop (..., size)
1276 stringop (...., VALUE);
1278 stringop (...., size);
1279 assuming constant propagation of VALUE will happen later.
1282 tree_stringop_fixed_value (tree stmt
, tree value
, int prob
, gcov_type count
,
1285 tree stmt1
, stmt2
, stmt3
;
1287 tree label_decl1
= create_artificial_label ();
1288 tree label_decl2
= create_artificial_label ();
1289 tree label1
, label2
;
1290 tree bb1end
, bb2end
;
1291 basic_block bb
, bb2
, bb3
, bb4
;
1292 edge e12
, e13
, e23
, e24
, e34
;
1293 block_stmt_iterator bsi
;
1294 tree call
= get_call_expr_in (stmt
);
1295 tree blck_size
= CALL_EXPR_ARG (call
, 2);
1296 tree optype
= TREE_TYPE (blck_size
);
1299 bb
= bb_for_stmt (stmt
);
1300 bsi
= bsi_for_stmt (stmt
);
1302 if (bsi_end_p (bsi
))
1305 for (ei
= ei_start (bb
->succs
); (e34
= ei_safe_edge (ei
)); )
1306 if (!e34
->flags
& EDGE_ABNORMAL
)
1311 e34
= split_block (bb
, stmt
);
1312 bsi
= bsi_for_stmt (stmt
);
1316 tmpv
= create_tmp_var (optype
, "PROF");
1317 tmp1
= create_tmp_var (optype
, "PROF");
1318 stmt1
= build_gimple_modify_stmt (tmpv
, fold_convert (optype
, value
));
1319 stmt2
= build_gimple_modify_stmt (tmp1
, blck_size
);
1320 stmt3
= build3 (COND_EXPR
, void_type_node
,
1321 build2 (NE_EXPR
, boolean_type_node
, tmp1
, tmpv
),
1322 NULL_TREE
, NULL_TREE
);
1323 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1324 bsi_insert_before (&bsi
, stmt2
, BSI_SAME_STMT
);
1325 bsi_insert_before (&bsi
, stmt3
, BSI_SAME_STMT
);
1328 label1
= build1 (LABEL_EXPR
, void_type_node
, label_decl1
);
1329 stmt1
= unshare_expr (stmt
);
1330 call
= get_call_expr_in (stmt1
);
1331 CALL_EXPR_ARG (call
, 2) = value
;
1332 bsi_insert_before (&bsi
, label1
, BSI_SAME_STMT
);
1333 bsi_insert_before (&bsi
, stmt1
, BSI_SAME_STMT
);
1334 region
= lookup_stmt_eh_region (stmt
);
1336 add_stmt_to_eh_region (stmt1
, region
);
1338 label2
= build1 (LABEL_EXPR
, void_type_node
, label_decl2
);
1339 bsi_insert_before (&bsi
, label2
, BSI_SAME_STMT
);
1342 /* Edge e23 connects bb2 to bb3, etc. */
1343 e12
= split_block (bb
, bb1end
);
1346 e23
= split_block (bb2
, bb2end
);
1348 bb3
->count
= all
- count
;
1350 e12
->flags
&= ~EDGE_FALLTHRU
;
1351 e12
->flags
|= EDGE_FALSE_VALUE
;
1352 e12
->probability
= prob
;
1355 e13
= make_edge (bb
, bb3
, EDGE_TRUE_VALUE
);
1356 e13
->probability
= REG_BR_PROB_BASE
- prob
;
1357 e13
->count
= all
- count
;
1361 e24
= make_edge (bb2
, bb4
, EDGE_FALLTHRU
);
1362 e24
->probability
= REG_BR_PROB_BASE
;
1365 e34
->probability
= REG_BR_PROB_BASE
;
1366 e34
->count
= all
- count
;
1369 /* Find values inside STMT for that we want to measure histograms for
1370 division/modulo optimization. */
1372 tree_stringops_transform (block_stmt_iterator
*bsi
)
1374 tree stmt
= bsi_stmt (*bsi
);
1375 tree call
= get_call_expr_in (stmt
);
1378 enum built_in_function fcode
;
1379 histogram_value histogram
;
1380 gcov_type count
, all
, val
;
1383 unsigned int dest_align
, src_align
;
1389 fndecl
= get_callee_fndecl (call
);
1392 fcode
= DECL_FUNCTION_CODE (fndecl
);
1393 if (!interesting_stringop_to_profile_p (fndecl
, call
))
1396 if (fcode
== BUILT_IN_BZERO
)
1397 blck_size
= CALL_EXPR_ARG (call
, 1);
1399 blck_size
= CALL_EXPR_ARG (call
, 2);
1400 if (TREE_CODE (blck_size
) == INTEGER_CST
)
1403 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_SINGLE_VALUE
);
1406 value
= histogram
->hvalue
.value
;
1407 val
= histogram
->hvalue
.counters
[0];
1408 count
= histogram
->hvalue
.counters
[1];
1409 all
= histogram
->hvalue
.counters
[2];
1410 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1411 /* We require that count is at least half of all; this means
1412 that for the transformation to fire the value must be constant
1413 at least 80% of time. */
1414 if ((6 * count
/ 5) < all
|| !maybe_hot_bb_p (bb_for_stmt (stmt
)))
1416 if (check_counter (stmt
, "value", all
, bb_for_stmt (stmt
)->count
))
1419 prob
= (count
* REG_BR_PROB_BASE
+ all
/ 2) / all
;
1422 dest
= CALL_EXPR_ARG (call
, 0);
1423 dest_align
= get_pointer_alignment (dest
, BIGGEST_ALIGNMENT
);
1426 case BUILT_IN_MEMCPY
:
1427 case BUILT_IN_MEMPCPY
:
1428 src
= CALL_EXPR_ARG (call
, 1);
1429 src_align
= get_pointer_alignment (src
, BIGGEST_ALIGNMENT
);
1430 if (!can_move_by_pieces (val
, MIN (dest_align
, src_align
)))
1433 case BUILT_IN_MEMSET
:
1434 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1435 CALL_EXPR_ARG (call
, 1),
1439 case BUILT_IN_BZERO
:
1440 if (!can_store_by_pieces (val
, builtin_memset_read_str
,
1448 tree_val
= build_int_cst_wide (get_gcov_type (),
1449 (unsigned HOST_WIDE_INT
) val
,
1450 val
>> (HOST_BITS_PER_WIDE_INT
- 1) >> 1);
1453 fprintf (dump_file
, "Single value %i stringop transformation on ",
1455 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1457 tree_stringop_fixed_value (stmt
, tree_val
, prob
, count
, all
);
1463 stringop_block_profile (tree stmt
, unsigned int *expected_align
,
1464 HOST_WIDE_INT
*expected_size
)
1466 histogram_value histogram
;
1467 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_AVERAGE
);
1469 *expected_size
= -1;
1470 else if (!histogram
->hvalue
.counters
[1])
1472 *expected_size
= -1;
1473 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1478 size
= ((histogram
->hvalue
.counters
[0]
1479 + histogram
->hvalue
.counters
[1] / 2)
1480 / histogram
->hvalue
.counters
[1]);
1481 /* Even if we can hold bigger value in SIZE, INT_MAX
1482 is safe "infinity" for code generation strategies. */
1485 *expected_size
= size
;
1486 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1488 histogram
= gimple_histogram_value_of_type (cfun
, stmt
, HIST_TYPE_IOR
);
1490 *expected_align
= 0;
1491 else if (!histogram
->hvalue
.counters
[0])
1493 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1494 *expected_align
= 0;
1501 count
= histogram
->hvalue
.counters
[0];
1503 while (!(count
& alignment
)
1504 && (alignment
* 2 * BITS_PER_UNIT
))
1506 *expected_align
= alignment
* BITS_PER_UNIT
;
1507 gimple_remove_histogram_value (cfun
, stmt
, histogram
);
1511 struct value_prof_hooks
{
1512 /* Find list of values for which we want to measure histograms. */
1513 void (*find_values_to_profile
) (histogram_values
*);
1515 /* Identify and exploit properties of values that are hard to analyze
1516 statically. See value-prof.c for more detail. */
1517 bool (*value_profile_transformations
) (void);
1520 /* Find values inside STMT for that we want to measure histograms for
1521 division/modulo optimization. */
1523 tree_divmod_values_to_profile (tree stmt
, histogram_values
*values
)
1525 tree assign
, lhs
, rhs
, divisor
, op0
, type
;
1526 histogram_value hist
;
1528 if (TREE_CODE (stmt
) == RETURN_EXPR
)
1529 assign
= TREE_OPERAND (stmt
, 0);
1534 || TREE_CODE (assign
) != GIMPLE_MODIFY_STMT
)
1536 lhs
= GIMPLE_STMT_OPERAND (assign
, 0);
1537 type
= TREE_TYPE (lhs
);
1538 if (!INTEGRAL_TYPE_P (type
))
1541 rhs
= GIMPLE_STMT_OPERAND (assign
, 1);
1542 switch (TREE_CODE (rhs
))
1544 case TRUNC_DIV_EXPR
:
1545 case TRUNC_MOD_EXPR
:
1546 divisor
= TREE_OPERAND (rhs
, 1);
1547 op0
= TREE_OPERAND (rhs
, 0);
1549 VEC_reserve (histogram_value
, heap
, *values
, 3);
1551 if (is_gimple_reg (divisor
))
1552 /* Check for the case where the divisor is the same value most
1554 VEC_quick_push (histogram_value
, *values
,
1555 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1558 /* For mod, check whether it is not often a noop (or replaceable by
1559 a few subtractions). */
1560 if (TREE_CODE (rhs
) == TRUNC_MOD_EXPR
1561 && TYPE_UNSIGNED (type
))
1564 /* Check for a special case where the divisor is power of 2. */
1565 VEC_quick_push (histogram_value
, *values
,
1566 gimple_alloc_histogram_value (cfun
, HIST_TYPE_POW2
,
1569 val
= build2 (TRUNC_DIV_EXPR
, type
, op0
, divisor
);
1570 hist
= gimple_alloc_histogram_value (cfun
, HIST_TYPE_INTERVAL
,
1572 hist
->hdata
.intvl
.int_start
= 0;
1573 hist
->hdata
.intvl
.steps
= 2;
1574 VEC_quick_push (histogram_value
, *values
, hist
);
1583 /* Find calls inside STMT for that we want to measure histograms for
1584 indirect/virtual call optimization. */
1587 tree_indirect_call_to_profile (tree stmt
, histogram_values
*values
)
1592 call
= get_call_expr_in (stmt
);
1594 if (!call
|| TREE_CODE (call
) != CALL_EXPR
)
1597 callee
= CALL_EXPR_FN (call
);
1599 if (TREE_CODE (callee
) == ADDR_EXPR
)
1602 VEC_reserve (histogram_value
, heap
, *values
, 3);
1604 VEC_quick_push (histogram_value
, *values
,
1605 gimple_alloc_histogram_value (cfun
, HIST_TYPE_INDIR_CALL
,
1611 /* Find values inside STMT for that we want to measure histograms for
1612 string operations. */
1614 tree_stringops_values_to_profile (tree stmt
, histogram_values
*values
)
1616 tree call
= get_call_expr_in (stmt
);
1620 enum built_in_function fcode
;
1624 fndecl
= get_callee_fndecl (call
);
1627 fcode
= DECL_FUNCTION_CODE (fndecl
);
1629 if (!interesting_stringop_to_profile_p (fndecl
, call
))
1632 dest
= CALL_EXPR_ARG (call
, 0);
1633 if (fcode
== BUILT_IN_BZERO
)
1634 blck_size
= CALL_EXPR_ARG (call
, 1);
1636 blck_size
= CALL_EXPR_ARG (call
, 2);
1638 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1640 VEC_safe_push (histogram_value
, heap
, *values
,
1641 gimple_alloc_histogram_value (cfun
, HIST_TYPE_SINGLE_VALUE
,
1643 VEC_safe_push (histogram_value
, heap
, *values
,
1644 gimple_alloc_histogram_value (cfun
, HIST_TYPE_AVERAGE
,
1647 if (TREE_CODE (blck_size
) != INTEGER_CST
)
1648 VEC_safe_push (histogram_value
, heap
, *values
,
1649 gimple_alloc_histogram_value (cfun
, HIST_TYPE_IOR
,
1653 /* Find values inside STMT for that we want to measure histograms and adds
1654 them to list VALUES. */
1657 tree_values_to_profile (tree stmt
, histogram_values
*values
)
1659 if (flag_value_profile_transformations
)
1661 tree_divmod_values_to_profile (stmt
, values
);
1662 tree_stringops_values_to_profile (stmt
, values
);
1663 tree_indirect_call_to_profile (stmt
, values
);
1668 tree_find_values_to_profile (histogram_values
*values
)
1671 block_stmt_iterator bsi
;
1673 histogram_value hist
= NULL
;
1677 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1678 tree_values_to_profile (bsi_stmt (bsi
), values
);
1680 for (i
= 0; VEC_iterate (histogram_value
, *values
, i
, hist
); i
++)
1684 case HIST_TYPE_INTERVAL
:
1685 hist
->n_counters
= hist
->hdata
.intvl
.steps
+ 2;
1688 case HIST_TYPE_POW2
:
1689 hist
->n_counters
= 2;
1692 case HIST_TYPE_SINGLE_VALUE
:
1693 hist
->n_counters
= 3;
1696 case HIST_TYPE_CONST_DELTA
:
1697 hist
->n_counters
= 4;
1700 case HIST_TYPE_INDIR_CALL
:
1701 hist
->n_counters
= 3;
1704 case HIST_TYPE_AVERAGE
:
1705 hist
->n_counters
= 2;
1709 hist
->n_counters
= 1;
1717 fprintf (dump_file
, "Stmt ");
1718 print_generic_expr (dump_file
, hist
->hvalue
.stmt
, TDF_SLIM
);
1719 dump_histogram_value (dump_file
, hist
);
1724 static struct value_prof_hooks tree_value_prof_hooks
= {
1725 tree_find_values_to_profile
,
1726 tree_value_profile_transformations
1730 tree_register_value_prof_hooks (void)
1732 gcc_assert (current_ir_type () == IR_GIMPLE
);
1733 value_prof_hooks
= &tree_value_prof_hooks
;
1736 /* IR-independent entry points. */
1738 find_values_to_profile (histogram_values
*values
)
1740 (value_prof_hooks
->find_values_to_profile
) (values
);
1744 value_profile_transformations (void)
1746 return (value_prof_hooks
->value_profile_transformations
) ();