1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "hard-reg-set.h"
27 #include "basic-block.h"
28 #include "value-prof.h"
31 #include "insn-config.h"
36 #include "tree-flow.h"
37 #include "tree-flow-inline.h"
38 #include "diagnostic.h"
44 #include "tree-pass.h"
46 #include "pointer-set.h"
48 static struct value_prof_hooks *value_prof_hooks;
50 /* In this file value profile based optimizations are placed. Currently the
51 following optimizations are implemented (for more detailed descriptions
52 see comments at value_profile_transformations):
54 1) Division/modulo specialization. Provided that we can determine that the
55 operands of the division have some special properties, we may use it to
56 produce more effective code.
57 2) Speculative prefetching. If we are able to determine that the difference
58 between addresses accessed by a memory reference is usually constant, we
59 may add the prefetch instructions.
60 FIXME: This transformation was removed together with RTL based value
63 3) Indirect/virtual call specialization. If we can determine most
64 common function callee in indirect/virtual call. We can use this
65 information to improve code effectiveness (especially info for
68 Every such optimization should add its requirements for profiled values to
69 insn_values_to_profile function. This function is called from branch_prob
70 in profile.c and the requested values are instrumented by it in the first
71 compilation with -fprofile-arcs. The optimization may then read the
72 gathered data in the second compilation with -fbranch-probabilities.
74 The measured data is pointed to from the histograms
75 field of the statement annotation of the instrumented insns. It is
76 kept as a linked list of struct histogram_value_t's, which contain the
77 same information as above. */
80 static tree tree_divmod_fixed_value (tree, tree, tree, tree,
81 tree, int, gcov_type, gcov_type);
82 static tree tree_mod_pow2 (tree, tree, tree, tree, int, gcov_type, gcov_type);
83 static tree tree_mod_subtract (tree, tree, tree, tree, int, int, int,
84 gcov_type, gcov_type, gcov_type);
85 static bool tree_divmod_fixed_value_transform (tree);
86 static bool tree_mod_pow2_value_transform (tree);
87 static bool tree_mod_subtract_transform (tree);
88 static bool tree_stringops_transform (block_stmt_iterator *);
89 static bool tree_ic_transform (tree);
91 /* Allocate histogram value. */
93 static histogram_value
94 gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
95 enum hist_type type, tree stmt, tree value)
97 histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
98 hist->hvalue.value = value;
99 hist->hvalue.stmt = stmt;
104 /* Hash value for histogram. */
107 histogram_hash (const void *x)
109 return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);
112 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
115 histogram_eq (const void *x, const void *y)
117 return ((const_histogram_value) x)->hvalue.stmt == (const_tree)y;
120 /* Set histogram for STMT. */
123 set_histogram_value (struct function *fun, tree stmt, histogram_value hist)
126 if (!hist && !VALUE_HISTOGRAMS (fun))
128 if (!VALUE_HISTOGRAMS (fun))
129 VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
131 loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
132 htab_hash_pointer (stmt),
133 hist ? INSERT : NO_INSERT);
137 htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
143 /* Get histogram list for STMT. */
146 gimple_histogram_value (struct function *fun, tree stmt)
148 if (!VALUE_HISTOGRAMS (fun))
150 return htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
151 htab_hash_pointer (stmt));
154 /* Add histogram for STMT. */
157 gimple_add_histogram_value (struct function *fun, tree stmt, histogram_value hist)
159 hist->hvalue.next = gimple_histogram_value (fun, stmt);
160 set_histogram_value (fun, stmt, hist);
163 /* Remove histogram HIST from STMT's histogram list. */
166 gimple_remove_histogram_value (struct function *fun, tree stmt, histogram_value hist)
168 histogram_value hist2 = gimple_histogram_value (fun, stmt);
171 set_histogram_value (fun, stmt, hist->hvalue.next);
175 while (hist2->hvalue.next != hist)
176 hist2 = hist2->hvalue.next;
177 hist2->hvalue.next = hist->hvalue.next;
179 free (hist->hvalue.counters);
180 #ifdef ENABLE_CHECKING
181 memset (hist, 0xab, sizeof (*hist));
186 /* Lookup histogram of type TYPE in the STMT. */
189 gimple_histogram_value_of_type (struct function *fun, tree stmt, enum hist_type type)
191 histogram_value hist;
192 for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
193 if (hist->type == type)
198 /* Dump information about HIST to DUMP_FILE. */
201 dump_histogram_value (FILE *dump_file, histogram_value hist)
205 case HIST_TYPE_INTERVAL:
206 fprintf (dump_file, "Interval counter range %d -- %d",
207 hist->hdata.intvl.int_start,
208 (hist->hdata.intvl.int_start
209 + hist->hdata.intvl.steps - 1));
210 if (hist->hvalue.counters)
213 fprintf(dump_file, " [");
214 for (i = 0; i < hist->hdata.intvl.steps; i++)
215 fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC,
216 hist->hdata.intvl.int_start + i,
217 (HOST_WIDEST_INT) hist->hvalue.counters[i]);
218 fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC,
219 (HOST_WIDEST_INT) hist->hvalue.counters[i]);
221 fprintf (dump_file, ".\n");
225 fprintf (dump_file, "Pow2 counter ");
226 if (hist->hvalue.counters)
228 fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC
229 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC,
230 (HOST_WIDEST_INT) hist->hvalue.counters[0],
231 (HOST_WIDEST_INT) hist->hvalue.counters[1]);
233 fprintf (dump_file, ".\n");
236 case HIST_TYPE_SINGLE_VALUE:
237 fprintf (dump_file, "Single value ");
238 if (hist->hvalue.counters)
240 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
241 " match:"HOST_WIDEST_INT_PRINT_DEC
242 " wrong:"HOST_WIDEST_INT_PRINT_DEC,
243 (HOST_WIDEST_INT) hist->hvalue.counters[0],
244 (HOST_WIDEST_INT) hist->hvalue.counters[1],
245 (HOST_WIDEST_INT) hist->hvalue.counters[2]);
247 fprintf (dump_file, ".\n");
250 case HIST_TYPE_AVERAGE:
251 fprintf (dump_file, "Average value ");
252 if (hist->hvalue.counters)
254 fprintf (dump_file, "sum:"HOST_WIDEST_INT_PRINT_DEC
255 " times:"HOST_WIDEST_INT_PRINT_DEC,
256 (HOST_WIDEST_INT) hist->hvalue.counters[0],
257 (HOST_WIDEST_INT) hist->hvalue.counters[1]);
259 fprintf (dump_file, ".\n");
263 fprintf (dump_file, "IOR value ");
264 if (hist->hvalue.counters)
266 fprintf (dump_file, "ior:"HOST_WIDEST_INT_PRINT_DEC,
267 (HOST_WIDEST_INT) hist->hvalue.counters[0]);
269 fprintf (dump_file, ".\n");
272 case HIST_TYPE_CONST_DELTA:
273 fprintf (dump_file, "Constant delta ");
274 if (hist->hvalue.counters)
276 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
277 " match:"HOST_WIDEST_INT_PRINT_DEC
278 " wrong:"HOST_WIDEST_INT_PRINT_DEC,
279 (HOST_WIDEST_INT) hist->hvalue.counters[0],
280 (HOST_WIDEST_INT) hist->hvalue.counters[1],
281 (HOST_WIDEST_INT) hist->hvalue.counters[2]);
283 fprintf (dump_file, ".\n");
285 case HIST_TYPE_INDIR_CALL:
286 fprintf (dump_file, "Indirect call ");
287 if (hist->hvalue.counters)
289 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
290 " match:"HOST_WIDEST_INT_PRINT_DEC
291 " all:"HOST_WIDEST_INT_PRINT_DEC,
292 (HOST_WIDEST_INT) hist->hvalue.counters[0],
293 (HOST_WIDEST_INT) hist->hvalue.counters[1],
294 (HOST_WIDEST_INT) hist->hvalue.counters[2]);
296 fprintf (dump_file, ".\n");
301 /* Dump all histograms attached to STMT to DUMP_FILE. */
304 dump_histograms_for_stmt (struct function *fun, FILE *dump_file, tree stmt)
306 histogram_value hist;
307 for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
308 dump_histogram_value (dump_file, hist);
311 /* Remove all histograms associated with STMT. */
314 gimple_remove_stmt_histograms (struct function *fun, tree stmt)
317 while ((val = gimple_histogram_value (fun, stmt)) != NULL)
318 gimple_remove_histogram_value (fun, stmt, val);
321 /* Duplicate all histograms associates with OSTMT to STMT. */
324 gimple_duplicate_stmt_histograms (struct function *fun, tree stmt,
325 struct function *ofun, tree ostmt)
328 for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
330 histogram_value new = gimple_alloc_histogram_value (fun, val->type, NULL, NULL);
331 memcpy (new, val, sizeof (*val));
332 new->hvalue.stmt = stmt;
333 new->hvalue.counters = xmalloc (sizeof (*new->hvalue.counters) * new->n_counters);
334 memcpy (new->hvalue.counters, val->hvalue.counters, sizeof (*new->hvalue.counters) * new->n_counters);
335 gimple_add_histogram_value (fun, stmt, new);
340 /* Move all histograms associated with OSTMT to STMT. */
343 gimple_move_stmt_histograms (struct function *fun, tree stmt, tree ostmt)
345 histogram_value val = gimple_histogram_value (fun, ostmt);
348 /* The following three statements can't be reordered,
349 because histogram hashtab relies on stmt field value
350 for finding the exact slot. */
351 set_histogram_value (fun, ostmt, NULL);
352 for (; val != NULL; val = val->hvalue.next)
353 val->hvalue.stmt = stmt;
354 set_histogram_value (fun, stmt, val);
358 static bool error_found = false;
360 /* Helper function for verify_histograms. For each histogram reachable via htab
361 walk verify that it was reached via statement walk. */
364 visit_hist (void **slot, void *data)
366 struct pointer_set_t *visited = (struct pointer_set_t *) data;
367 histogram_value hist = *(histogram_value *) slot;
368 if (!pointer_set_contains (visited, hist))
370 error ("Dead histogram");
371 dump_histogram_value (stderr, hist);
372 debug_generic_stmt (hist->hvalue.stmt);
378 /* Verify sanity of the histograms. */
381 verify_histograms (void)
384 block_stmt_iterator bsi;
385 histogram_value hist;
386 struct pointer_set_t *visited_hists;
389 visited_hists = pointer_set_create ();
391 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
393 tree stmt = bsi_stmt (bsi);
395 for (hist = gimple_histogram_value (cfun, stmt); hist; hist = hist->hvalue.next)
397 if (hist->hvalue.stmt != stmt)
399 error ("Histogram value statement does not correspond to statement"
400 " it is associated with");
401 debug_generic_stmt (stmt);
402 dump_histogram_value (stderr, hist);
405 pointer_set_insert (visited_hists, hist);
408 if (VALUE_HISTOGRAMS (cfun))
409 htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists);
410 pointer_set_destroy (visited_hists);
412 internal_error ("verify_histograms failed");
415 /* Helper function for verify_histograms. For each histogram reachable via htab
416 walk verify that it was reached via statement walk. */
419 free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
421 histogram_value hist = *(histogram_value *) slot;
422 free (hist->hvalue.counters);
423 #ifdef ENABLE_CHECKING
424 memset (hist, 0xab, sizeof (*hist));
431 free_histograms (void)
433 if (VALUE_HISTOGRAMS (cfun))
435 htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);
436 htab_delete (VALUE_HISTOGRAMS (cfun));
437 VALUE_HISTOGRAMS (cfun) = NULL;
441 /* The overall number of invocations of the counter should match execution count
442 of basic block. Report it as error rather than internal error as it might
443 mean that user has misused the profile somehow. */
445 check_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count)
450 locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt)
452 : &DECL_SOURCE_LOCATION (current_function_decl));
453 error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)",
454 locus, name, (int)all, (int)bb_count);
460 /* Tree based transformations. */
462 tree_value_profile_transformations (void)
465 block_stmt_iterator bsi;
466 bool changed = false;
470 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
472 tree stmt = bsi_stmt (bsi);
473 histogram_value th = gimple_histogram_value (cfun, stmt);
479 fprintf (dump_file, "Trying transformations on stmt ");
480 print_generic_stmt (dump_file, stmt, TDF_SLIM);
481 dump_histograms_for_stmt (cfun, dump_file, stmt);
484 /* Transformations: */
485 /* The order of things in this conditional controls which
486 transformation is used when more than one is applicable. */
487 /* It is expected that any code added by the transformations
488 will be added before the current statement, and that the
489 current statement remain valid (although possibly
490 modified) upon return. */
491 if (flag_value_profile_transformations
492 && (tree_mod_subtract_transform (stmt)
493 || tree_divmod_fixed_value_transform (stmt)
494 || tree_mod_pow2_value_transform (stmt)
495 || tree_stringops_transform (&bsi)
496 || tree_ic_transform (stmt)))
498 stmt = bsi_stmt (bsi);
500 /* Original statement may no longer be in the same block. */
501 if (bb != bb_for_stmt (stmt))
503 bb = bb_for_stmt (stmt);
504 bsi = bsi_for_stmt (stmt);
518 /* Generate code for transformation 1 (with OPERATION, operands OP1
519 and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
520 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
521 within roundoff error). This generates the result into a temp and returns
522 the temp; it does not replace or alter the original STMT. */
524 tree_divmod_fixed_value (tree stmt, tree operation,
525 tree op1, tree op2, tree value, int prob, gcov_type count,
528 tree stmt1, stmt2, stmt3;
529 tree tmp1, tmp2, tmpv;
530 tree label_decl1 = create_artificial_label ();
531 tree label_decl2 = create_artificial_label ();
533 tree bb1end, bb2end, bb3end;
534 basic_block bb, bb2, bb3, bb4;
535 tree optype = TREE_TYPE (operation);
536 edge e12, e13, e23, e24, e34;
537 block_stmt_iterator bsi;
539 bb = bb_for_stmt (stmt);
540 bsi = bsi_for_stmt (stmt);
542 tmpv = create_tmp_var (optype, "PROF");
543 tmp1 = create_tmp_var (optype, "PROF");
544 stmt1 = build_gimple_modify_stmt (tmpv, fold_convert (optype, value));
545 stmt2 = build_gimple_modify_stmt (tmp1, op2);
546 stmt3 = build3 (COND_EXPR, void_type_node,
547 build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
548 NULL_TREE, NULL_TREE);
549 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
550 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
551 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
554 tmp2 = create_tmp_var (optype, "PROF");
555 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
556 stmt1 = build_gimple_modify_stmt (tmp2,
557 build2 (TREE_CODE (operation), optype,
559 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
560 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
563 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
564 stmt1 = build_gimple_modify_stmt (tmp2,
565 build2 (TREE_CODE (operation), optype,
567 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
568 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
572 /* Edge e23 connects bb2 to bb3, etc. */
573 e12 = split_block (bb, bb1end);
576 e23 = split_block (bb2, bb2end);
578 bb3->count = all - count;
579 e34 = split_block (bb3, bb3end);
583 e12->flags &= ~EDGE_FALLTHRU;
584 e12->flags |= EDGE_FALSE_VALUE;
585 e12->probability = prob;
588 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
589 e13->probability = REG_BR_PROB_BASE - prob;
590 e13->count = all - count;
594 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
595 e24->probability = REG_BR_PROB_BASE;
598 e34->probability = REG_BR_PROB_BASE;
599 e34->count = all - count;
604 /* Do transform 1) on INSN if applicable. */
606 tree_divmod_fixed_value_transform (tree stmt)
608 histogram_value histogram;
610 gcov_type val, count, all;
611 tree modify, op, op1, op2, result, value, tree_val;
615 if (TREE_CODE (stmt) == RETURN_EXPR
616 && TREE_OPERAND (stmt, 0)
617 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
618 modify = TREE_OPERAND (stmt, 0);
619 if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
621 op = GIMPLE_STMT_OPERAND (modify, 1);
622 if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
624 code = TREE_CODE (op);
626 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
629 op1 = TREE_OPERAND (op, 0);
630 op2 = TREE_OPERAND (op, 1);
632 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
636 value = histogram->hvalue.value;
637 val = histogram->hvalue.counters[0];
638 count = histogram->hvalue.counters[1];
639 all = histogram->hvalue.counters[2];
640 gimple_remove_histogram_value (cfun, stmt, histogram);
642 /* We require that count is at least half of all; this means
643 that for the transformation to fire the value must be constant
644 at least 50% of time (and 75% gives the guarantee of usage). */
645 if (simple_cst_equal (op2, value) != 1 || 2 * count < all
646 || !maybe_hot_bb_p (bb_for_stmt (stmt)))
649 if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
652 /* Compute probability of taking the optimal path. */
653 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
655 tree_val = build_int_cst_wide (get_gcov_type (),
656 (unsigned HOST_WIDE_INT) val,
657 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
658 result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all);
662 fprintf (dump_file, "Div/mod by constant ");
663 print_generic_expr (dump_file, value, TDF_SLIM);
664 fprintf (dump_file, "=");
665 print_generic_expr (dump_file, tree_val, TDF_SLIM);
666 fprintf (dump_file, " transformation on insn ");
667 print_generic_stmt (dump_file, stmt, TDF_SLIM);
670 GIMPLE_STMT_OPERAND (modify, 1) = result;
675 /* Generate code for transformation 2 (with OPERATION, operands OP1
676 and OP2, parent modify-expr STMT and probability of taking the optimal
677 path PROB, which is equivalent to COUNT/ALL within roundoff error).
678 This generates the result into a temp and returns
679 the temp; it does not replace or alter the original STMT. */
681 tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob,
682 gcov_type count, gcov_type all)
684 tree stmt1, stmt2, stmt3, stmt4;
686 tree label_decl1 = create_artificial_label ();
687 tree label_decl2 = create_artificial_label ();
689 tree bb1end, bb2end, bb3end;
690 basic_block bb, bb2, bb3, bb4;
691 tree optype = TREE_TYPE (operation);
692 edge e12, e13, e23, e24, e34;
693 block_stmt_iterator bsi;
694 tree result = create_tmp_var (optype, "PROF");
696 bb = bb_for_stmt (stmt);
697 bsi = bsi_for_stmt (stmt);
699 tmp2 = create_tmp_var (optype, "PROF");
700 tmp3 = create_tmp_var (optype, "PROF");
701 stmt2 = build_gimple_modify_stmt (tmp2,
702 build2 (PLUS_EXPR, optype, op2,
703 build_int_cst (optype, -1)));
704 stmt3 = build_gimple_modify_stmt (tmp3,
705 build2 (BIT_AND_EXPR, optype, tmp2, op2));
706 stmt4 = build3 (COND_EXPR, void_type_node,
707 build2 (NE_EXPR, boolean_type_node,
708 tmp3, build_int_cst (optype, 0)),
709 NULL_TREE, NULL_TREE);
710 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
711 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
712 bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT);
715 /* tmp2 == op2-1 inherited from previous block */
716 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
717 stmt1 = build_gimple_modify_stmt (result,
718 build2 (BIT_AND_EXPR, optype, op1, tmp2));
719 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
720 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
723 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
724 stmt1 = build_gimple_modify_stmt (result,
725 build2 (TREE_CODE (operation), optype,
727 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
728 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
732 /* Edge e23 connects bb2 to bb3, etc. */
733 e12 = split_block (bb, bb1end);
736 e23 = split_block (bb2, bb2end);
738 bb3->count = all - count;
739 e34 = split_block (bb3, bb3end);
743 e12->flags &= ~EDGE_FALLTHRU;
744 e12->flags |= EDGE_FALSE_VALUE;
745 e12->probability = prob;
748 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
749 e13->probability = REG_BR_PROB_BASE - prob;
750 e13->count = all - count;
754 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
755 e24->probability = REG_BR_PROB_BASE;
758 e34->probability = REG_BR_PROB_BASE;
759 e34->count = all - count;
764 /* Do transform 2) on INSN if applicable. */
766 tree_mod_pow2_value_transform (tree stmt)
768 histogram_value histogram;
770 gcov_type count, wrong_values, all;
771 tree modify, op, op1, op2, result, value;
775 if (TREE_CODE (stmt) == RETURN_EXPR
776 && TREE_OPERAND (stmt, 0)
777 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
778 modify = TREE_OPERAND (stmt, 0);
779 if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
781 op = GIMPLE_STMT_OPERAND (modify, 1);
782 if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
784 code = TREE_CODE (op);
786 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
789 op1 = TREE_OPERAND (op, 0);
790 op2 = TREE_OPERAND (op, 1);
792 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
796 value = histogram->hvalue.value;
797 wrong_values = histogram->hvalue.counters[0];
798 count = histogram->hvalue.counters[1];
800 gimple_remove_histogram_value (cfun, stmt, histogram);
802 /* We require that we hit a power of 2 at least half of all evaluations. */
803 if (simple_cst_equal (op2, value) != 1 || count < wrong_values
804 || !maybe_hot_bb_p (bb_for_stmt (stmt)))
809 fprintf (dump_file, "Mod power of 2 transformation on insn ");
810 print_generic_stmt (dump_file, stmt, TDF_SLIM);
813 /* Compute probability of taking the optimal path. */
814 all = count + wrong_values;
816 if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
819 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
821 result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
823 GIMPLE_STMT_OPERAND (modify, 1) = result;
828 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
829 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
830 support. Currently only NCOUNTS==0 or 1 is supported and this is
831 built into this interface. The probabilities of taking the optimal
832 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
833 COUNT2/ALL respectively within roundoff error). This generates the
834 result into a temp and returns the temp; it does not replace or alter
835 the original STMT. */
836 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
839 tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2,
840 int prob1, int prob2, int ncounts,
841 gcov_type count1, gcov_type count2, gcov_type all)
843 tree stmt1, stmt2, stmt3;
845 tree label_decl1 = create_artificial_label ();
846 tree label_decl2 = create_artificial_label ();
847 tree label_decl3 = create_artificial_label ();
848 tree label1, label2, label3;
849 tree bb1end, bb2end = NULL_TREE, bb3end;
850 basic_block bb, bb2, bb3, bb4;
851 tree optype = TREE_TYPE (operation);
852 edge e12, e23 = 0, e24, e34, e14;
853 block_stmt_iterator bsi;
854 tree result = create_tmp_var (optype, "PROF");
856 bb = bb_for_stmt (stmt);
857 bsi = bsi_for_stmt (stmt);
859 tmp1 = create_tmp_var (optype, "PROF");
860 stmt1 = build_gimple_modify_stmt (result, op1);
861 stmt2 = build_gimple_modify_stmt (tmp1, op2);
862 stmt3 = build3 (COND_EXPR, void_type_node,
863 build2 (LT_EXPR, boolean_type_node, result, tmp1),
864 NULL_TREE, NULL_TREE);
865 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
866 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
867 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
870 if (ncounts) /* Assumed to be 0 or 1 */
872 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
873 stmt1 = build_gimple_modify_stmt (result,
874 build2 (MINUS_EXPR, optype,
876 stmt2 = build3 (COND_EXPR, void_type_node,
877 build2 (LT_EXPR, boolean_type_node, result, tmp1),
878 NULL_TREE, NULL_TREE);
879 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
880 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
881 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
886 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
887 stmt1 = build_gimple_modify_stmt (result,
888 build2 (TREE_CODE (operation), optype,
890 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
891 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
894 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
895 bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
898 /* Edge e23 connects bb2 to bb3, etc. */
899 /* However block 3 is optional; if it is not there, references
900 to 3 really refer to block 2. */
901 e12 = split_block (bb, bb1end);
903 bb2->count = all - count1;
905 if (ncounts) /* Assumed to be 0 or 1. */
907 e23 = split_block (bb2, bb2end);
909 bb3->count = all - count1 - count2;
912 e34 = split_block (ncounts ? bb3 : bb2, bb3end);
916 e12->flags &= ~EDGE_FALLTHRU;
917 e12->flags |= EDGE_FALSE_VALUE;
918 e12->probability = REG_BR_PROB_BASE - prob1;
919 e12->count = all - count1;
921 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
922 e14->probability = prob1;
925 if (ncounts) /* Assumed to be 0 or 1. */
927 e23->flags &= ~EDGE_FALLTHRU;
928 e23->flags |= EDGE_FALSE_VALUE;
929 e23->count = all - count1 - count2;
930 e23->probability = REG_BR_PROB_BASE - prob2;
932 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
933 e24->probability = prob2;
937 e34->probability = REG_BR_PROB_BASE;
938 e34->count = all - count1 - count2;
943 /* Do transforms 3) and 4) on INSN if applicable. */
945 tree_mod_subtract_transform (tree stmt)
947 histogram_value histogram;
949 gcov_type count, wrong_values, all;
950 tree modify, op, op1, op2, result, value;
952 unsigned int i, steps;
953 gcov_type count1, count2;
956 if (TREE_CODE (stmt) == RETURN_EXPR
957 && TREE_OPERAND (stmt, 0)
958 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
959 modify = TREE_OPERAND (stmt, 0);
960 if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
962 op = GIMPLE_STMT_OPERAND (modify, 1);
963 if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
965 code = TREE_CODE (op);
967 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
970 op1 = TREE_OPERAND (op, 0);
971 op2 = TREE_OPERAND (op, 1);
973 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
977 value = histogram->hvalue.value;
980 for (i = 0; i < histogram->hdata.intvl.steps; i++)
981 all += histogram->hvalue.counters[i];
983 wrong_values += histogram->hvalue.counters[i];
984 wrong_values += histogram->hvalue.counters[i+1];
985 steps = histogram->hdata.intvl.steps;
987 count1 = histogram->hvalue.counters[0];
988 count2 = histogram->hvalue.counters[1];
990 /* Compute probability of taking the optimal path. */
991 if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
993 gimple_remove_histogram_value (cfun, stmt, histogram);
997 /* We require that we use just subtractions in at least 50% of all
1000 for (i = 0; i < histogram->hdata.intvl.steps; i++)
1002 count += histogram->hvalue.counters[i];
1003 if (count * 2 >= all)
1007 || !maybe_hot_bb_p (bb_for_stmt (stmt)))
1010 gimple_remove_histogram_value (cfun, stmt, histogram);
1013 fprintf (dump_file, "Mod subtract transformation on insn ");
1014 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1017 /* Compute probability of taking the optimal path(s). */
1018 prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
1019 prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
1021 /* In practice, "steps" is always 2. This interface reflects this,
1022 and will need to be changed if "steps" can change. */
1023 result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
1024 count1, count2, all);
1026 GIMPLE_STMT_OPERAND (modify, 1) = result;
1031 static struct cgraph_node** pid_map = NULL;
1033 /* Initialize map of pids (pid -> cgraph node) */
1038 struct cgraph_node *n;
1040 if (pid_map != NULL)
1044 = (struct cgraph_node**) xmalloc (sizeof (struct cgraph_node*) * cgraph_max_pid);
1046 for (n = cgraph_nodes; n; n = n->next)
1049 pid_map [n->pid] = n;
1053 /* Return cgraph node for function with pid */
1055 static inline struct cgraph_node*
1056 find_func_by_pid (int pid)
1060 return pid_map [pid];
1063 /* Do transformation
1065 if (actual_callee_addres == addres_of_most_common_function/method)
1072 tree_ic (tree stmt, tree call, struct cgraph_node* direct_call,
1073 int prob, gcov_type count, gcov_type all)
1075 tree stmt1, stmt2, stmt3;
1076 tree tmp1, tmpv, tmp;
1077 tree label_decl1 = create_artificial_label ();
1078 tree label_decl2 = create_artificial_label ();
1079 tree label1, label2;
1080 tree bb1end, bb2end, bb3end;
1082 basic_block bb, bb2, bb3, bb4;
1083 tree optype = build_pointer_type (void_type_node);
1084 edge e12, e13, e23, e24, e34;
1085 block_stmt_iterator bsi;
1088 bb = bb_for_stmt (stmt);
1089 bsi = bsi_for_stmt (stmt);
1091 tmpv = create_tmp_var (optype, "PROF");
1092 tmp1 = create_tmp_var (optype, "PROF");
1093 stmt1 = build_gimple_modify_stmt (tmpv,
1094 unshare_expr (CALL_EXPR_FN (call)));
1095 tmp = fold_convert (optype, build_addr (direct_call->decl,
1096 current_function_decl));
1097 stmt2 = build_gimple_modify_stmt (tmp1, tmp);
1098 stmt3 = build3 (COND_EXPR, void_type_node,
1099 build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1100 NULL_TREE, NULL_TREE);
1101 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1102 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1103 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1106 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1107 stmt1 = unshare_expr (stmt);
1108 new_call = get_call_expr_in (stmt1);
1109 CALL_EXPR_FN (new_call) = build_addr (direct_call->decl,
1110 current_function_decl);
1111 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1112 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1115 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1116 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1120 /* Edge e23 connects bb2 to bb3, etc. */
1121 e12 = split_block (bb, bb1end);
1124 e23 = split_block (bb2, bb2end);
1126 bb3->count = all - count;
1127 e34 = split_block (bb3, bb3end);
1131 e12->flags &= ~EDGE_FALLTHRU;
1132 e12->flags |= EDGE_FALSE_VALUE;
1133 e12->probability = prob;
1136 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1137 e13->probability = REG_BR_PROB_BASE - prob;
1138 e13->count = all - count;
1142 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1143 e24->probability = REG_BR_PROB_BASE;
1145 e34->probability = REG_BR_PROB_BASE;
1146 e34->count = all - count;
1149 region = lookup_stmt_eh_region (stmt);
1150 if (region >=0 && tree_could_throw_p (stmt1))
1152 add_stmt_to_eh_region (stmt1, region);
1153 make_eh_edges (stmt1);
1156 if (region >=0 && tree_could_throw_p (stmt))
1158 tree_purge_dead_eh_edges (bb4);
1159 make_eh_edges (stmt);
1166 For every checked indirect/virtual call determine if most common pid of
1167 function/class method has probability more than 50%. If yes modify code of
1172 tree_ic_transform (tree stmt)
1174 histogram_value histogram;
1175 gcov_type val, count, all;
1177 tree call, callee, modify;
1178 struct cgraph_node *direct_call;
1180 call = get_call_expr_in (stmt);
1182 if (!call || TREE_CODE (call) != CALL_EXPR)
1185 callee = CALL_EXPR_FN (call);
1187 if (TREE_CODE (callee) == ADDR_EXPR)
1190 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1194 val = histogram->hvalue.counters [0];
1195 count = histogram->hvalue.counters [1];
1196 all = histogram->hvalue.counters [2];
1197 gimple_remove_histogram_value (cfun, stmt, histogram);
1199 if (4 * count <= 3 * all)
1202 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1203 direct_call = find_func_by_pid ((int)val);
1205 if (direct_call == NULL)
1208 modify = tree_ic (stmt, call, direct_call, prob, count, all);
1212 fprintf (dump_file, "Indirect call -> direct call ");
1213 print_generic_expr (dump_file, call, TDF_SLIM);
1214 fprintf (dump_file, "=> ");
1215 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1216 fprintf (dump_file, " transformation on insn ");
1217 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1218 fprintf (dump_file, " to ");
1219 print_generic_stmt (dump_file, modify, TDF_SLIM);
1220 fprintf (dump_file, "hist->count %llu hist->all %llu\n", count, all);
1226 /* Return true if the stringop CALL with FNDECL shall be profiled. */
1228 interesting_stringop_to_profile_p (tree fndecl, tree call)
1230 enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1232 if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY
1233 && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO)
1238 case BUILT_IN_MEMCPY:
1239 case BUILT_IN_MEMPCPY:
1240 return validate_arglist (call,
1241 POINTER_TYPE, POINTER_TYPE, INTEGER_TYPE,
1243 case BUILT_IN_MEMSET:
1244 return validate_arglist (call,
1245 POINTER_TYPE, INTEGER_TYPE, INTEGER_TYPE,
1247 case BUILT_IN_BZERO:
1248 return validate_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1255 /* Convert stringop (..., size)
1258 stringop (...., VALUE);
1260 stringop (...., size);
1261 assuming constant propagation of VALUE will happen later.
1264 tree_stringop_fixed_value (tree stmt, tree value, int prob, gcov_type count,
1267 tree stmt1, stmt2, stmt3;
1269 tree label_decl1 = create_artificial_label ();
1270 tree label_decl2 = create_artificial_label ();
1271 tree label1, label2;
1272 tree bb1end, bb2end;
1273 basic_block bb, bb2, bb3, bb4;
1274 edge e12, e13, e23, e24, e34;
1275 block_stmt_iterator bsi;
1276 tree call = get_call_expr_in (stmt);
1277 tree blck_size = CALL_EXPR_ARG (call, 2);
1278 tree optype = TREE_TYPE (blck_size);
1281 bb = bb_for_stmt (stmt);
1282 bsi = bsi_for_stmt (stmt);
1284 if (bsi_end_p (bsi))
1287 for (ei = ei_start (bb->succs); (e34 = ei_safe_edge (ei)); )
1288 if (!e34->flags & EDGE_ABNORMAL)
1293 e34 = split_block (bb, stmt);
1294 bsi = bsi_for_stmt (stmt);
1298 tmpv = create_tmp_var (optype, "PROF");
1299 tmp1 = create_tmp_var (optype, "PROF");
1300 stmt1 = build_gimple_modify_stmt (tmpv, fold_convert (optype, value));
1301 stmt2 = build_gimple_modify_stmt (tmp1, blck_size);
1302 stmt3 = build3 (COND_EXPR, void_type_node,
1303 build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1304 NULL_TREE, NULL_TREE);
1305 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1306 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1307 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1310 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1311 stmt1 = unshare_expr (stmt);
1312 call = get_call_expr_in (stmt1);
1313 CALL_EXPR_ARG (call, 2) = value;
1314 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1315 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1316 region = lookup_stmt_eh_region (stmt);
1318 add_stmt_to_eh_region (stmt1, region);
1320 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1321 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1324 /* Edge e23 connects bb2 to bb3, etc. */
1325 e12 = split_block (bb, bb1end);
1328 e23 = split_block (bb2, bb2end);
1330 bb3->count = all - count;
1332 e12->flags &= ~EDGE_FALLTHRU;
1333 e12->flags |= EDGE_FALSE_VALUE;
1334 e12->probability = prob;
1337 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1338 e13->probability = REG_BR_PROB_BASE - prob;
1339 e13->count = all - count;
1343 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1344 e24->probability = REG_BR_PROB_BASE;
1347 e34->probability = REG_BR_PROB_BASE;
1348 e34->count = all - count;
1351 /* Find values inside STMT for that we want to measure histograms for
1352 division/modulo optimization. */
1354 tree_stringops_transform (block_stmt_iterator *bsi)
1356 tree stmt = bsi_stmt (*bsi);
1357 tree call = get_call_expr_in (stmt);
1360 enum built_in_function fcode;
1361 histogram_value histogram;
1362 gcov_type count, all, val;
1365 unsigned int dest_align, src_align;
1371 fndecl = get_callee_fndecl (call);
1374 fcode = DECL_FUNCTION_CODE (fndecl);
1375 if (!interesting_stringop_to_profile_p (fndecl, call))
1378 if (fcode == BUILT_IN_BZERO)
1379 blck_size = CALL_EXPR_ARG (call, 1);
1381 blck_size = CALL_EXPR_ARG (call, 2);
1382 if (TREE_CODE (blck_size) == INTEGER_CST)
1385 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1388 value = histogram->hvalue.value;
1389 val = histogram->hvalue.counters[0];
1390 count = histogram->hvalue.counters[1];
1391 all = histogram->hvalue.counters[2];
1392 gimple_remove_histogram_value (cfun, stmt, histogram);
1393 /* We require that count is at least half of all; this means
1394 that for the transformation to fire the value must be constant
1395 at least 80% of time. */
1396 if ((6 * count / 5) < all || !maybe_hot_bb_p (bb_for_stmt (stmt)))
1398 if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
1400 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1401 dest = CALL_EXPR_ARG (call, 0);
1402 dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1405 case BUILT_IN_MEMCPY:
1406 case BUILT_IN_MEMPCPY:
1407 src = CALL_EXPR_ARG (call, 1);
1408 src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1409 if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1412 case BUILT_IN_MEMSET:
1413 if (!can_store_by_pieces (val, builtin_memset_read_str,
1414 CALL_EXPR_ARG (call, 1),
1418 case BUILT_IN_BZERO:
1419 if (!can_store_by_pieces (val, builtin_memset_read_str,
1427 tree_val = build_int_cst_wide (get_gcov_type (),
1428 (unsigned HOST_WIDE_INT) val,
1429 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1432 fprintf (dump_file, "Single value %i stringop transformation on ",
1434 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1436 tree_stringop_fixed_value (stmt, tree_val, prob, count, all);
1442 stringop_block_profile (tree stmt, unsigned int *expected_align,
1443 HOST_WIDE_INT *expected_size)
1445 histogram_value histogram;
1446 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1448 *expected_size = -1;
1449 else if (!histogram->hvalue.counters[1])
1451 *expected_size = -1;
1452 gimple_remove_histogram_value (cfun, stmt, histogram);
1457 size = ((histogram->hvalue.counters[0]
1458 + histogram->hvalue.counters[1] / 2)
1459 / histogram->hvalue.counters[1]);
1460 /* Even if we can hold bigger value in SIZE, INT_MAX
1461 is safe "infinity" for code generation strategies. */
1464 *expected_size = size;
1465 gimple_remove_histogram_value (cfun, stmt, histogram);
1467 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1469 *expected_align = 0;
1470 else if (!histogram->hvalue.counters[0])
1472 gimple_remove_histogram_value (cfun, stmt, histogram);
1473 *expected_align = 0;
1480 count = histogram->hvalue.counters[0];
1482 while (!(count & alignment)
1483 && (alignment * 2 * BITS_PER_UNIT))
1485 *expected_align = alignment * BITS_PER_UNIT;
1486 gimple_remove_histogram_value (cfun, stmt, histogram);
1490 struct value_prof_hooks {
1491 /* Find list of values for which we want to measure histograms. */
1492 void (*find_values_to_profile) (histogram_values *);
1494 /* Identify and exploit properties of values that are hard to analyze
1495 statically. See value-prof.c for more detail. */
1496 bool (*value_profile_transformations) (void);
1499 /* Find values inside STMT for that we want to measure histograms for
1500 division/modulo optimization. */
1502 tree_divmod_values_to_profile (tree stmt, histogram_values *values)
1504 tree assign, lhs, rhs, divisor, op0, type;
1505 histogram_value hist;
1507 if (TREE_CODE (stmt) == RETURN_EXPR)
1508 assign = TREE_OPERAND (stmt, 0);
1513 || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1515 lhs = GIMPLE_STMT_OPERAND (assign, 0);
1516 type = TREE_TYPE (lhs);
1517 if (!INTEGRAL_TYPE_P (type))
1520 rhs = GIMPLE_STMT_OPERAND (assign, 1);
1521 switch (TREE_CODE (rhs))
1523 case TRUNC_DIV_EXPR:
1524 case TRUNC_MOD_EXPR:
1525 divisor = TREE_OPERAND (rhs, 1);
1526 op0 = TREE_OPERAND (rhs, 0);
1528 VEC_reserve (histogram_value, heap, *values, 3);
1530 if (is_gimple_reg (divisor))
1531 /* Check for the case where the divisor is the same value most
1533 VEC_quick_push (histogram_value, *values,
1534 gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1537 /* For mod, check whether it is not often a noop (or replaceable by
1538 a few subtractions). */
1539 if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
1540 && TYPE_UNSIGNED (type))
1543 /* Check for a special case where the divisor is power of 2. */
1544 VEC_quick_push (histogram_value, *values,
1545 gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1548 val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1549 hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1551 hist->hdata.intvl.int_start = 0;
1552 hist->hdata.intvl.steps = 2;
1553 VEC_quick_push (histogram_value, *values, hist);
1562 /* Find calls inside STMT for that we want to measure histograms for
1563 indirect/virtual call optimization. */
1566 tree_indirect_call_to_profile (tree stmt, histogram_values *values)
1571 call = get_call_expr_in (stmt);
1573 if (!call || TREE_CODE (call) != CALL_EXPR)
1576 callee = CALL_EXPR_FN (call);
1578 if (TREE_CODE (callee) == ADDR_EXPR)
1581 VEC_reserve (histogram_value, heap, *values, 3);
1583 VEC_quick_push (histogram_value, *values,
1584 gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1590 /* Find values inside STMT for that we want to measure histograms for
1591 string operations. */
1593 tree_stringops_values_to_profile (tree stmt, histogram_values *values)
1595 tree call = get_call_expr_in (stmt);
1599 enum built_in_function fcode;
1603 fndecl = get_callee_fndecl (call);
1606 fcode = DECL_FUNCTION_CODE (fndecl);
1608 if (!interesting_stringop_to_profile_p (fndecl, call))
1611 dest = CALL_EXPR_ARG (call, 0);
1612 if (fcode == BUILT_IN_BZERO)
1613 blck_size = CALL_EXPR_ARG (call, 1);
1615 blck_size = CALL_EXPR_ARG (call, 2);
1617 if (TREE_CODE (blck_size) != INTEGER_CST)
1619 VEC_safe_push (histogram_value, heap, *values,
1620 gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1622 VEC_safe_push (histogram_value, heap, *values,
1623 gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1626 if (TREE_CODE (blck_size) != INTEGER_CST)
1627 VEC_safe_push (histogram_value, heap, *values,
1628 gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1632 /* Find values inside STMT for that we want to measure histograms and adds
1633 them to list VALUES. */
1636 tree_values_to_profile (tree stmt, histogram_values *values)
1638 if (flag_value_profile_transformations)
1640 tree_divmod_values_to_profile (stmt, values);
1641 tree_stringops_values_to_profile (stmt, values);
1642 tree_indirect_call_to_profile (stmt, values);
1647 tree_find_values_to_profile (histogram_values *values)
1650 block_stmt_iterator bsi;
1652 histogram_value hist = NULL;
1656 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1657 tree_values_to_profile (bsi_stmt (bsi), values);
1659 for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
1663 case HIST_TYPE_INTERVAL:
1664 hist->n_counters = hist->hdata.intvl.steps + 2;
1667 case HIST_TYPE_POW2:
1668 hist->n_counters = 2;
1671 case HIST_TYPE_SINGLE_VALUE:
1672 hist->n_counters = 3;
1675 case HIST_TYPE_CONST_DELTA:
1676 hist->n_counters = 4;
1679 case HIST_TYPE_INDIR_CALL:
1680 hist->n_counters = 3;
1683 case HIST_TYPE_AVERAGE:
1684 hist->n_counters = 2;
1688 hist->n_counters = 1;
1696 fprintf (dump_file, "Stmt ");
1697 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
1698 dump_histogram_value (dump_file, hist);
1703 static struct value_prof_hooks tree_value_prof_hooks = {
1704 tree_find_values_to_profile,
1705 tree_value_profile_transformations
1709 tree_register_value_prof_hooks (void)
1711 gcc_assert (current_ir_type () == IR_GIMPLE);
1712 value_prof_hooks = &tree_value_prof_hooks;
1715 /* IR-independent entry points. */
1717 find_values_to_profile (histogram_values *values)
1719 (value_prof_hooks->find_values_to_profile) (values);
1723 value_profile_transformations (void)
1725 return (value_prof_hooks->value_profile_transformations) ();