recog.c (split_all_insns): Remove dead code.
[official-gcc.git] / gcc / value-prof.c
blobb0cc13bb9aaa438265e0d8c53afa93ca1e58cc26
1 /* Transformations based on profile information for values.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
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
15 for more details.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "expr.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "value-prof.h"
30 #include "output.h"
31 #include "flags.h"
32 #include "insn-config.h"
33 #include "recog.h"
34 #include "optabs.h"
35 #include "regs.h"
36 #include "ggc.h"
37 #include "tree-flow.h"
38 #include "tree-flow-inline.h"
39 #include "diagnostic.h"
40 #include "tree-pretty-print.h"
41 #include "gimple-pretty-print.h"
42 #include "coverage.h"
43 #include "tree.h"
44 #include "gcov-io.h"
45 #include "cgraph.h"
46 #include "timevar.h"
47 #include "tree-pass.h"
48 #include "toplev.h"
49 #include "pointer-set.h"
51 static struct value_prof_hooks *value_prof_hooks;
53 /* In this file value profile based optimizations are placed. Currently the
54 following optimizations are implemented (for more detailed descriptions
55 see comments at value_profile_transformations):
57 1) Division/modulo specialization. Provided that we can determine that the
58 operands of the division have some special properties, we may use it to
59 produce more effective code.
60 2) Speculative prefetching. If we are able to determine that the difference
61 between addresses accessed by a memory reference is usually constant, we
62 may add the prefetch instructions.
63 FIXME: This transformation was removed together with RTL based value
64 profiling.
66 3) Indirect/virtual call specialization. If we can determine most
67 common function callee in indirect/virtual call. We can use this
68 information to improve code effectiveness (especially info for
69 inliner).
71 Every such optimization should add its requirements for profiled values to
72 insn_values_to_profile function. This function is called from branch_prob
73 in profile.c and the requested values are instrumented by it in the first
74 compilation with -fprofile-arcs. The optimization may then read the
75 gathered data in the second compilation with -fbranch-probabilities.
77 The measured data is pointed to from the histograms
78 field of the statement annotation of the instrumented insns. It is
79 kept as a linked list of struct histogram_value_t's, which contain the
80 same information as above. */
83 static tree gimple_divmod_fixed_value (gimple, tree, int, gcov_type, gcov_type);
84 static tree gimple_mod_pow2 (gimple, int, gcov_type, gcov_type);
85 static tree gimple_mod_subtract (gimple, int, int, int, gcov_type, gcov_type,
86 gcov_type);
87 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
88 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
89 static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
90 static bool gimple_stringops_transform (gimple_stmt_iterator *);
91 static bool gimple_ic_transform (gimple);
93 /* Allocate histogram value. */
95 static histogram_value
96 gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
97 enum hist_type type, gimple stmt, tree value)
99 histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
100 hist->hvalue.value = value;
101 hist->hvalue.stmt = stmt;
102 hist->type = type;
103 return hist;
106 /* Hash value for histogram. */
108 static hashval_t
109 histogram_hash (const void *x)
111 return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);
114 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
116 static int
117 histogram_eq (const void *x, const void *y)
119 return ((const_histogram_value) x)->hvalue.stmt == (const_gimple) y;
122 /* Set histogram for STMT. */
124 static void
125 set_histogram_value (struct function *fun, gimple stmt, histogram_value hist)
127 void **loc;
128 if (!hist && !VALUE_HISTOGRAMS (fun))
129 return;
130 if (!VALUE_HISTOGRAMS (fun))
131 VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
132 histogram_eq, NULL);
133 loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
134 htab_hash_pointer (stmt),
135 hist ? INSERT : NO_INSERT);
136 if (!hist)
138 if (loc)
139 htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
140 return;
142 *loc = hist;
145 /* Get histogram list for STMT. */
147 histogram_value
148 gimple_histogram_value (struct function *fun, gimple stmt)
150 if (!VALUE_HISTOGRAMS (fun))
151 return NULL;
152 return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
153 htab_hash_pointer (stmt));
156 /* Add histogram for STMT. */
158 void
159 gimple_add_histogram_value (struct function *fun, gimple stmt,
160 histogram_value hist)
162 hist->hvalue.next = gimple_histogram_value (fun, stmt);
163 set_histogram_value (fun, stmt, hist);
167 /* Remove histogram HIST from STMT's histogram list. */
169 void
170 gimple_remove_histogram_value (struct function *fun, gimple stmt,
171 histogram_value hist)
173 histogram_value hist2 = gimple_histogram_value (fun, stmt);
174 if (hist == hist2)
176 set_histogram_value (fun, stmt, hist->hvalue.next);
178 else
180 while (hist2->hvalue.next != hist)
181 hist2 = hist2->hvalue.next;
182 hist2->hvalue.next = hist->hvalue.next;
184 free (hist->hvalue.counters);
185 #ifdef ENABLE_CHECKING
186 memset (hist, 0xab, sizeof (*hist));
187 #endif
188 free (hist);
192 /* Lookup histogram of type TYPE in the STMT. */
194 histogram_value
195 gimple_histogram_value_of_type (struct function *fun, gimple stmt,
196 enum hist_type type)
198 histogram_value hist;
199 for (hist = gimple_histogram_value (fun, stmt); hist;
200 hist = hist->hvalue.next)
201 if (hist->type == type)
202 return hist;
203 return NULL;
206 /* Dump information about HIST to DUMP_FILE. */
208 static void
209 dump_histogram_value (FILE *dump_file, histogram_value hist)
211 switch (hist->type)
213 case HIST_TYPE_INTERVAL:
214 fprintf (dump_file, "Interval counter range %d -- %d",
215 hist->hdata.intvl.int_start,
216 (hist->hdata.intvl.int_start
217 + hist->hdata.intvl.steps - 1));
218 if (hist->hvalue.counters)
220 unsigned int i;
221 fprintf(dump_file, " [");
222 for (i = 0; i < hist->hdata.intvl.steps; i++)
223 fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC,
224 hist->hdata.intvl.int_start + i,
225 (HOST_WIDEST_INT) hist->hvalue.counters[i]);
226 fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC,
227 (HOST_WIDEST_INT) hist->hvalue.counters[i]);
229 fprintf (dump_file, ".\n");
230 break;
232 case HIST_TYPE_POW2:
233 fprintf (dump_file, "Pow2 counter ");
234 if (hist->hvalue.counters)
236 fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC
237 " nonpow2:"HOST_WIDEST_INT_PRINT_DEC,
238 (HOST_WIDEST_INT) hist->hvalue.counters[0],
239 (HOST_WIDEST_INT) hist->hvalue.counters[1]);
241 fprintf (dump_file, ".\n");
242 break;
244 case HIST_TYPE_SINGLE_VALUE:
245 fprintf (dump_file, "Single value ");
246 if (hist->hvalue.counters)
248 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
249 " match:"HOST_WIDEST_INT_PRINT_DEC
250 " wrong:"HOST_WIDEST_INT_PRINT_DEC,
251 (HOST_WIDEST_INT) hist->hvalue.counters[0],
252 (HOST_WIDEST_INT) hist->hvalue.counters[1],
253 (HOST_WIDEST_INT) hist->hvalue.counters[2]);
255 fprintf (dump_file, ".\n");
256 break;
258 case HIST_TYPE_AVERAGE:
259 fprintf (dump_file, "Average value ");
260 if (hist->hvalue.counters)
262 fprintf (dump_file, "sum:"HOST_WIDEST_INT_PRINT_DEC
263 " times:"HOST_WIDEST_INT_PRINT_DEC,
264 (HOST_WIDEST_INT) hist->hvalue.counters[0],
265 (HOST_WIDEST_INT) hist->hvalue.counters[1]);
267 fprintf (dump_file, ".\n");
268 break;
270 case HIST_TYPE_IOR:
271 fprintf (dump_file, "IOR value ");
272 if (hist->hvalue.counters)
274 fprintf (dump_file, "ior:"HOST_WIDEST_INT_PRINT_DEC,
275 (HOST_WIDEST_INT) hist->hvalue.counters[0]);
277 fprintf (dump_file, ".\n");
278 break;
280 case HIST_TYPE_CONST_DELTA:
281 fprintf (dump_file, "Constant delta ");
282 if (hist->hvalue.counters)
284 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
285 " match:"HOST_WIDEST_INT_PRINT_DEC
286 " wrong:"HOST_WIDEST_INT_PRINT_DEC,
287 (HOST_WIDEST_INT) hist->hvalue.counters[0],
288 (HOST_WIDEST_INT) hist->hvalue.counters[1],
289 (HOST_WIDEST_INT) hist->hvalue.counters[2]);
291 fprintf (dump_file, ".\n");
292 break;
293 case HIST_TYPE_INDIR_CALL:
294 fprintf (dump_file, "Indirect call ");
295 if (hist->hvalue.counters)
297 fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
298 " match:"HOST_WIDEST_INT_PRINT_DEC
299 " all:"HOST_WIDEST_INT_PRINT_DEC,
300 (HOST_WIDEST_INT) hist->hvalue.counters[0],
301 (HOST_WIDEST_INT) hist->hvalue.counters[1],
302 (HOST_WIDEST_INT) hist->hvalue.counters[2]);
304 fprintf (dump_file, ".\n");
305 break;
309 /* Dump all histograms attached to STMT to DUMP_FILE. */
311 void
312 dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple stmt)
314 histogram_value hist;
315 for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
316 dump_histogram_value (dump_file, hist);
319 /* Remove all histograms associated with STMT. */
321 void
322 gimple_remove_stmt_histograms (struct function *fun, gimple stmt)
324 histogram_value val;
325 while ((val = gimple_histogram_value (fun, stmt)) != NULL)
326 gimple_remove_histogram_value (fun, stmt, val);
329 /* Duplicate all histograms associates with OSTMT to STMT. */
331 void
332 gimple_duplicate_stmt_histograms (struct function *fun, gimple stmt,
333 struct function *ofun, gimple ostmt)
335 histogram_value val;
336 for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
338 histogram_value new_val = gimple_alloc_histogram_value (fun, val->type, NULL, NULL);
339 memcpy (new_val, val, sizeof (*val));
340 new_val->hvalue.stmt = stmt;
341 new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
342 memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
343 gimple_add_histogram_value (fun, stmt, new_val);
348 /* Move all histograms associated with OSTMT to STMT. */
350 void
351 gimple_move_stmt_histograms (struct function *fun, gimple stmt, gimple ostmt)
353 histogram_value val = gimple_histogram_value (fun, ostmt);
354 if (val)
356 /* The following three statements can't be reordered,
357 because histogram hashtab relies on stmt field value
358 for finding the exact slot. */
359 set_histogram_value (fun, ostmt, NULL);
360 for (; val != NULL; val = val->hvalue.next)
361 val->hvalue.stmt = stmt;
362 set_histogram_value (fun, stmt, val);
366 static bool error_found = false;
368 /* Helper function for verify_histograms. For each histogram reachable via htab
369 walk verify that it was reached via statement walk. */
371 static int
372 visit_hist (void **slot, void *data)
374 struct pointer_set_t *visited = (struct pointer_set_t *) data;
375 histogram_value hist = *(histogram_value *) slot;
376 if (!pointer_set_contains (visited, hist))
378 error ("Dead histogram");
379 dump_histogram_value (stderr, hist);
380 debug_gimple_stmt (hist->hvalue.stmt);
381 error_found = true;
383 return 1;
387 /* Verify sanity of the histograms. */
389 DEBUG_FUNCTION void
390 verify_histograms (void)
392 basic_block bb;
393 gimple_stmt_iterator gsi;
394 histogram_value hist;
395 struct pointer_set_t *visited_hists;
397 error_found = false;
398 visited_hists = pointer_set_create ();
399 FOR_EACH_BB (bb)
400 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
402 gimple stmt = gsi_stmt (gsi);
404 for (hist = gimple_histogram_value (cfun, stmt); hist;
405 hist = hist->hvalue.next)
407 if (hist->hvalue.stmt != stmt)
409 error ("Histogram value statement does not correspond to "
410 "the statement it is associated with");
411 debug_gimple_stmt (stmt);
412 dump_histogram_value (stderr, hist);
413 error_found = true;
415 pointer_set_insert (visited_hists, hist);
418 if (VALUE_HISTOGRAMS (cfun))
419 htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists);
420 pointer_set_destroy (visited_hists);
421 if (error_found)
422 internal_error ("verify_histograms failed");
425 /* Helper function for verify_histograms. For each histogram reachable via htab
426 walk verify that it was reached via statement walk. */
428 static int
429 free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
431 histogram_value hist = *(histogram_value *) slot;
432 free (hist->hvalue.counters);
433 #ifdef ENABLE_CHECKING
434 memset (hist, 0xab, sizeof (*hist));
435 #endif
436 free (hist);
437 return 1;
440 void
441 free_histograms (void)
443 if (VALUE_HISTOGRAMS (cfun))
445 htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);
446 htab_delete (VALUE_HISTOGRAMS (cfun));
447 VALUE_HISTOGRAMS (cfun) = NULL;
452 /* The overall number of invocations of the counter should match
453 execution count of basic block. Report it as error rather than
454 internal error as it might mean that user has misused the profile
455 somehow. */
457 static bool
458 check_counter (gimple stmt, const char * name,
459 gcov_type *count, gcov_type *all, gcov_type bb_count)
461 if (*all != bb_count || *count > *all)
463 location_t locus;
464 locus = (stmt != NULL)
465 ? gimple_location (stmt)
466 : DECL_SOURCE_LOCATION (current_function_decl);
467 if (flag_profile_correction)
469 inform (locus, "Correcting inconsistent value profile: "
470 "%s profiler overall count (%d) does not match BB count "
471 "(%d)", name, (int)*all, (int)bb_count);
472 *all = bb_count;
473 if (*count > *all)
474 *count = *all;
475 return false;
477 else
479 error_at (locus, "Corrupted value profile: %s "
480 "profiler overall count (%d) does not match BB count (%d)",
481 name, (int)*all, (int)bb_count);
482 return true;
486 return false;
490 /* GIMPLE based transformations. */
492 static bool
493 gimple_value_profile_transformations (void)
495 basic_block bb;
496 gimple_stmt_iterator gsi;
497 bool changed = false;
499 FOR_EACH_BB (bb)
501 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
503 gimple stmt = gsi_stmt (gsi);
504 histogram_value th = gimple_histogram_value (cfun, stmt);
505 if (!th)
506 continue;
508 if (dump_file)
510 fprintf (dump_file, "Trying transformations on stmt ");
511 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
512 dump_histograms_for_stmt (cfun, dump_file, stmt);
515 /* Transformations: */
516 /* The order of things in this conditional controls which
517 transformation is used when more than one is applicable. */
518 /* It is expected that any code added by the transformations
519 will be added before the current statement, and that the
520 current statement remain valid (although possibly
521 modified) upon return. */
522 if (flag_value_profile_transformations
523 && (gimple_mod_subtract_transform (&gsi)
524 || gimple_divmod_fixed_value_transform (&gsi)
525 || gimple_mod_pow2_value_transform (&gsi)
526 || gimple_stringops_transform (&gsi)
527 || gimple_ic_transform (stmt)))
529 stmt = gsi_stmt (gsi);
530 changed = true;
531 /* Original statement may no longer be in the same block. */
532 if (bb != gimple_bb (stmt))
534 bb = gimple_bb (stmt);
535 gsi = gsi_for_stmt (stmt);
541 if (changed)
543 counts_to_freqs ();
546 return changed;
550 /* Generate code for transformation 1 (with parent gimple assignment
551 STMT and probability of taking the optimal path PROB, which is
552 equivalent to COUNT/ALL within roundoff error). This generates the
553 result into a temp and returns the temp; it does not replace or
554 alter the original STMT. */
556 static tree
557 gimple_divmod_fixed_value (gimple stmt, tree value, int prob, gcov_type count,
558 gcov_type all)
560 gimple stmt1, stmt2, stmt3;
561 tree tmp0, tmp1, tmp2, tmpv;
562 gimple bb1end, bb2end, bb3end;
563 basic_block bb, bb2, bb3, bb4;
564 tree optype, op1, op2;
565 edge e12, e13, e23, e24, e34;
566 gimple_stmt_iterator gsi;
568 gcc_assert (is_gimple_assign (stmt)
569 && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
570 || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));
572 optype = TREE_TYPE (gimple_assign_lhs (stmt));
573 op1 = gimple_assign_rhs1 (stmt);
574 op2 = gimple_assign_rhs2 (stmt);
576 bb = gimple_bb (stmt);
577 gsi = gsi_for_stmt (stmt);
579 tmpv = create_tmp_reg (optype, "PROF");
580 tmp0 = make_ssa_name (tmpv, NULL);
581 tmp1 = make_ssa_name (tmpv, NULL);
582 stmt1 = gimple_build_assign (tmp0, fold_convert (optype, value));
583 SSA_NAME_DEF_STMT (tmp0) = stmt1;
584 stmt2 = gimple_build_assign (tmp1, op2);
585 SSA_NAME_DEF_STMT (tmp1) = stmt2;
586 stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
587 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
588 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
589 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
590 bb1end = stmt3;
592 tmp2 = make_rename_temp (optype, "PROF");
593 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,
594 op1, tmp0);
595 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
596 bb2end = stmt1;
598 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,
599 op1, op2);
600 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
601 bb3end = stmt1;
603 /* Fix CFG. */
604 /* Edge e23 connects bb2 to bb3, etc. */
605 e12 = split_block (bb, bb1end);
606 bb2 = e12->dest;
607 bb2->count = count;
608 e23 = split_block (bb2, bb2end);
609 bb3 = e23->dest;
610 bb3->count = all - count;
611 e34 = split_block (bb3, bb3end);
612 bb4 = e34->dest;
613 bb4->count = all;
615 e12->flags &= ~EDGE_FALLTHRU;
616 e12->flags |= EDGE_FALSE_VALUE;
617 e12->probability = prob;
618 e12->count = count;
620 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
621 e13->probability = REG_BR_PROB_BASE - prob;
622 e13->count = all - count;
624 remove_edge (e23);
626 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
627 e24->probability = REG_BR_PROB_BASE;
628 e24->count = count;
630 e34->probability = REG_BR_PROB_BASE;
631 e34->count = all - count;
633 return tmp2;
637 /* Do transform 1) on INSN if applicable. */
639 static bool
640 gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
642 histogram_value histogram;
643 enum tree_code code;
644 gcov_type val, count, all;
645 tree result, value, tree_val;
646 gcov_type prob;
647 gimple stmt;
649 stmt = gsi_stmt (*si);
650 if (gimple_code (stmt) != GIMPLE_ASSIGN)
651 return false;
653 if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
654 return false;
656 code = gimple_assign_rhs_code (stmt);
658 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
659 return false;
661 histogram = gimple_histogram_value_of_type (cfun, stmt,
662 HIST_TYPE_SINGLE_VALUE);
663 if (!histogram)
664 return false;
666 value = histogram->hvalue.value;
667 val = histogram->hvalue.counters[0];
668 count = histogram->hvalue.counters[1];
669 all = histogram->hvalue.counters[2];
670 gimple_remove_histogram_value (cfun, stmt, histogram);
672 /* We require that count is at least half of all; this means
673 that for the transformation to fire the value must be constant
674 at least 50% of time (and 75% gives the guarantee of usage). */
675 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
676 || 2 * count < all
677 || optimize_bb_for_size_p (gimple_bb (stmt)))
678 return false;
680 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
681 return false;
683 /* Compute probability of taking the optimal path. */
684 if (all > 0)
685 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
686 else
687 prob = 0;
689 tree_val = build_int_cst_wide (get_gcov_type (),
690 (unsigned HOST_WIDE_INT) val,
691 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
692 result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all);
694 if (dump_file)
696 fprintf (dump_file, "Div/mod by constant ");
697 print_generic_expr (dump_file, value, TDF_SLIM);
698 fprintf (dump_file, "=");
699 print_generic_expr (dump_file, tree_val, TDF_SLIM);
700 fprintf (dump_file, " transformation on insn ");
701 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
704 gimple_assign_set_rhs_from_tree (si, result);
706 return true;
709 /* Generate code for transformation 2 (with parent gimple assign STMT and
710 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
711 within roundoff error). This generates the result into a temp and returns
712 the temp; it does not replace or alter the original STMT. */
713 static tree
714 gimple_mod_pow2 (gimple stmt, int prob, gcov_type count, gcov_type all)
716 gimple stmt1, stmt2, stmt3, stmt4;
717 tree tmp2, tmp3, tmpv;
718 gimple bb1end, bb2end, bb3end;
719 basic_block bb, bb2, bb3, bb4;
720 tree optype, op1, op2;
721 edge e12, e13, e23, e24, e34;
722 gimple_stmt_iterator gsi;
723 tree result;
725 gcc_assert (is_gimple_assign (stmt)
726 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
728 optype = TREE_TYPE (gimple_assign_lhs (stmt));
729 op1 = gimple_assign_rhs1 (stmt);
730 op2 = gimple_assign_rhs2 (stmt);
732 bb = gimple_bb (stmt);
733 gsi = gsi_for_stmt (stmt);
735 result = make_rename_temp (optype, "PROF");
736 tmpv = create_tmp_var (optype, "PROF");
737 tmp2 = make_ssa_name (tmpv, NULL);
738 tmp3 = make_ssa_name (tmpv, NULL);
739 stmt2 = gimple_build_assign_with_ops (PLUS_EXPR, tmp2, op2,
740 build_int_cst (optype, -1));
741 SSA_NAME_DEF_STMT (tmp2) = stmt2;
742 stmt3 = gimple_build_assign_with_ops (BIT_AND_EXPR, tmp3, tmp2, op2);
743 SSA_NAME_DEF_STMT (tmp3) = stmt3;
744 stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0),
745 NULL_TREE, NULL_TREE);
746 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
747 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
748 gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT);
749 bb1end = stmt4;
751 /* tmp2 == op2-1 inherited from previous block. */
752 stmt1 = gimple_build_assign_with_ops (BIT_AND_EXPR, result, op1, tmp2);
753 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
754 bb2end = stmt1;
756 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
757 op1, op2);
758 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
759 bb3end = stmt1;
761 /* Fix CFG. */
762 /* Edge e23 connects bb2 to bb3, etc. */
763 e12 = split_block (bb, bb1end);
764 bb2 = e12->dest;
765 bb2->count = count;
766 e23 = split_block (bb2, bb2end);
767 bb3 = e23->dest;
768 bb3->count = all - count;
769 e34 = split_block (bb3, bb3end);
770 bb4 = e34->dest;
771 bb4->count = all;
773 e12->flags &= ~EDGE_FALLTHRU;
774 e12->flags |= EDGE_FALSE_VALUE;
775 e12->probability = prob;
776 e12->count = count;
778 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
779 e13->probability = REG_BR_PROB_BASE - prob;
780 e13->count = all - count;
782 remove_edge (e23);
784 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
785 e24->probability = REG_BR_PROB_BASE;
786 e24->count = count;
788 e34->probability = REG_BR_PROB_BASE;
789 e34->count = all - count;
791 return result;
794 /* Do transform 2) on INSN if applicable. */
795 static bool
796 gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
798 histogram_value histogram;
799 enum tree_code code;
800 gcov_type count, wrong_values, all;
801 tree lhs_type, result, value;
802 gcov_type prob;
803 gimple stmt;
805 stmt = gsi_stmt (*si);
806 if (gimple_code (stmt) != GIMPLE_ASSIGN)
807 return false;
809 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
810 if (!INTEGRAL_TYPE_P (lhs_type))
811 return false;
813 code = gimple_assign_rhs_code (stmt);
815 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
816 return false;
818 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
819 if (!histogram)
820 return false;
822 value = histogram->hvalue.value;
823 wrong_values = histogram->hvalue.counters[0];
824 count = histogram->hvalue.counters[1];
826 gimple_remove_histogram_value (cfun, stmt, histogram);
828 /* We require that we hit a power of 2 at least half of all evaluations. */
829 if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
830 || count < wrong_values
831 || optimize_bb_for_size_p (gimple_bb (stmt)))
832 return false;
834 if (dump_file)
836 fprintf (dump_file, "Mod power of 2 transformation on insn ");
837 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
840 /* Compute probability of taking the optimal path. */
841 all = count + wrong_values;
843 if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
844 return false;
846 if (all > 0)
847 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
848 else
849 prob = 0;
851 result = gimple_mod_pow2 (stmt, prob, count, all);
853 gimple_assign_set_rhs_from_tree (si, result);
855 return true;
858 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
859 NCOUNTS the number of cases to support. Currently only NCOUNTS==0 or 1 is
860 supported and this is built into this interface. The probabilities of taking
861 the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
862 COUNT2/ALL respectively within roundoff error). This generates the
863 result into a temp and returns the temp; it does not replace or alter
864 the original STMT. */
865 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
867 static tree
868 gimple_mod_subtract (gimple stmt, int prob1, int prob2, int ncounts,
869 gcov_type count1, gcov_type count2, gcov_type all)
871 gimple stmt1, stmt2, stmt3;
872 tree tmp1;
873 gimple bb1end, bb2end = NULL, bb3end;
874 basic_block bb, bb2, bb3, bb4;
875 tree optype, op1, op2;
876 edge e12, e23 = 0, e24, e34, e14;
877 gimple_stmt_iterator gsi;
878 tree result;
880 gcc_assert (is_gimple_assign (stmt)
881 && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
883 optype = TREE_TYPE (gimple_assign_lhs (stmt));
884 op1 = gimple_assign_rhs1 (stmt);
885 op2 = gimple_assign_rhs2 (stmt);
887 bb = gimple_bb (stmt);
888 gsi = gsi_for_stmt (stmt);
890 result = make_rename_temp (optype, "PROF");
891 tmp1 = make_ssa_name (create_tmp_var (optype, "PROF"), NULL);
892 stmt1 = gimple_build_assign (result, op1);
893 stmt2 = gimple_build_assign (tmp1, op2);
894 SSA_NAME_DEF_STMT (tmp1) = stmt2;
895 stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
896 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
897 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
898 gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
899 bb1end = stmt3;
901 if (ncounts) /* Assumed to be 0 or 1 */
903 stmt1 = gimple_build_assign_with_ops (MINUS_EXPR, result, result, tmp1);
904 stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
905 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
906 gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
907 bb2end = stmt2;
910 /* Fallback case. */
911 stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
912 result, tmp1);
913 gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
914 bb3end = stmt1;
916 /* Fix CFG. */
917 /* Edge e23 connects bb2 to bb3, etc. */
918 /* However block 3 is optional; if it is not there, references
919 to 3 really refer to block 2. */
920 e12 = split_block (bb, bb1end);
921 bb2 = e12->dest;
922 bb2->count = all - count1;
924 if (ncounts) /* Assumed to be 0 or 1. */
926 e23 = split_block (bb2, bb2end);
927 bb3 = e23->dest;
928 bb3->count = all - count1 - count2;
931 e34 = split_block (ncounts ? bb3 : bb2, bb3end);
932 bb4 = e34->dest;
933 bb4->count = all;
935 e12->flags &= ~EDGE_FALLTHRU;
936 e12->flags |= EDGE_FALSE_VALUE;
937 e12->probability = REG_BR_PROB_BASE - prob1;
938 e12->count = all - count1;
940 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
941 e14->probability = prob1;
942 e14->count = count1;
944 if (ncounts) /* Assumed to be 0 or 1. */
946 e23->flags &= ~EDGE_FALLTHRU;
947 e23->flags |= EDGE_FALSE_VALUE;
948 e23->count = all - count1 - count2;
949 e23->probability = REG_BR_PROB_BASE - prob2;
951 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
952 e24->probability = prob2;
953 e24->count = count2;
956 e34->probability = REG_BR_PROB_BASE;
957 e34->count = all - count1 - count2;
959 return result;
963 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable. */
965 static bool
966 gimple_mod_subtract_transform (gimple_stmt_iterator *si)
968 histogram_value histogram;
969 enum tree_code code;
970 gcov_type count, wrong_values, all;
971 tree lhs_type, result;
972 gcov_type prob1, prob2;
973 unsigned int i, steps;
974 gcov_type count1, count2;
975 gimple stmt;
977 stmt = gsi_stmt (*si);
978 if (gimple_code (stmt) != GIMPLE_ASSIGN)
979 return false;
981 lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
982 if (!INTEGRAL_TYPE_P (lhs_type))
983 return false;
985 code = gimple_assign_rhs_code (stmt);
987 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
988 return false;
990 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
991 if (!histogram)
992 return false;
994 all = 0;
995 wrong_values = 0;
996 for (i = 0; i < histogram->hdata.intvl.steps; i++)
997 all += histogram->hvalue.counters[i];
999 wrong_values += histogram->hvalue.counters[i];
1000 wrong_values += histogram->hvalue.counters[i+1];
1001 steps = histogram->hdata.intvl.steps;
1002 all += wrong_values;
1003 count1 = histogram->hvalue.counters[0];
1004 count2 = histogram->hvalue.counters[1];
1006 /* Compute probability of taking the optimal path. */
1007 if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count))
1009 gimple_remove_histogram_value (cfun, stmt, histogram);
1010 return false;
1013 if (flag_profile_correction && count1 + count2 > all)
1014 all = count1 + count2;
1016 gcc_assert (count1 + count2 <= all);
1018 /* We require that we use just subtractions in at least 50% of all
1019 evaluations. */
1020 count = 0;
1021 for (i = 0; i < histogram->hdata.intvl.steps; i++)
1023 count += histogram->hvalue.counters[i];
1024 if (count * 2 >= all)
1025 break;
1027 if (i == steps
1028 || optimize_bb_for_size_p (gimple_bb (stmt)))
1029 return false;
1031 gimple_remove_histogram_value (cfun, stmt, histogram);
1032 if (dump_file)
1034 fprintf (dump_file, "Mod subtract transformation on insn ");
1035 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1038 /* Compute probability of taking the optimal path(s). */
1039 if (all > 0)
1041 prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
1042 prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
1044 else
1046 prob1 = prob2 = 0;
1049 /* In practice, "steps" is always 2. This interface reflects this,
1050 and will need to be changed if "steps" can change. */
1051 result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all);
1053 gimple_assign_set_rhs_from_tree (si, result);
1055 return true;
1058 static struct cgraph_node** pid_map = NULL;
1060 /* Initialize map of pids (pid -> cgraph node) */
1062 static void
1063 init_pid_map (void)
1065 struct cgraph_node *n;
1067 if (pid_map != NULL)
1068 return;
1070 pid_map = XCNEWVEC (struct cgraph_node*, cgraph_max_pid);
1072 for (n = cgraph_nodes; n; n = n->next)
1074 if (n->pid != -1)
1075 pid_map [n->pid] = n;
1079 /* Return cgraph node for function with pid */
1081 static inline struct cgraph_node*
1082 find_func_by_pid (int pid)
1084 init_pid_map ();
1086 return pid_map [pid];
1089 /* Do transformation
1091 if (actual_callee_address == address_of_most_common_function/method)
1092 do direct call
1093 else
1094 old call
1097 static gimple
1098 gimple_ic (gimple icall_stmt, struct cgraph_node *direct_call,
1099 int prob, gcov_type count, gcov_type all)
1101 gimple dcall_stmt, load_stmt, cond_stmt;
1102 tree tmp0, tmp1, tmpv, tmp;
1103 basic_block cond_bb, dcall_bb, icall_bb, join_bb;
1104 tree optype = build_pointer_type (void_type_node);
1105 edge e_cd, e_ci, e_di, e_dj, e_ij;
1106 gimple_stmt_iterator gsi;
1107 int lp_nr;
1109 cond_bb = gimple_bb (icall_stmt);
1110 gsi = gsi_for_stmt (icall_stmt);
1112 tmpv = create_tmp_reg (optype, "PROF");
1113 tmp0 = make_ssa_name (tmpv, NULL);
1114 tmp1 = make_ssa_name (tmpv, NULL);
1115 tmp = unshare_expr (gimple_call_fn (icall_stmt));
1116 load_stmt = gimple_build_assign (tmp0, tmp);
1117 SSA_NAME_DEF_STMT (tmp0) = load_stmt;
1118 gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1120 tmp = fold_convert (optype, build_addr (direct_call->decl,
1121 current_function_decl));
1122 load_stmt = gimple_build_assign (tmp1, tmp);
1123 SSA_NAME_DEF_STMT (tmp1) = load_stmt;
1124 gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1126 cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1127 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1129 gimple_set_vdef (icall_stmt, NULL_TREE);
1130 gimple_set_vuse (icall_stmt, NULL_TREE);
1131 update_stmt (icall_stmt);
1132 dcall_stmt = gimple_copy (icall_stmt);
1133 gimple_call_set_fndecl (dcall_stmt, direct_call->decl);
1134 gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT);
1136 /* Fix CFG. */
1137 /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1138 e_cd = split_block (cond_bb, cond_stmt);
1139 dcall_bb = e_cd->dest;
1140 dcall_bb->count = count;
1142 e_di = split_block (dcall_bb, dcall_stmt);
1143 icall_bb = e_di->dest;
1144 icall_bb->count = all - count;
1146 e_ij = split_block (icall_bb, icall_stmt);
1147 join_bb = e_ij->dest;
1148 join_bb->count = all;
1150 e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1151 e_cd->probability = prob;
1152 e_cd->count = count;
1154 e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
1155 e_ci->probability = REG_BR_PROB_BASE - prob;
1156 e_ci->count = all - count;
1158 remove_edge (e_di);
1160 e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
1161 e_dj->probability = REG_BR_PROB_BASE;
1162 e_dj->count = count;
1164 e_ij->probability = REG_BR_PROB_BASE;
1165 e_ij->count = all - count;
1167 /* Insert PHI node for the call result if necessary. */
1168 if (gimple_call_lhs (icall_stmt)
1169 && TREE_CODE (gimple_call_lhs (icall_stmt)) == SSA_NAME)
1171 tree result = gimple_call_lhs (icall_stmt);
1172 gimple phi = create_phi_node (result, join_bb);
1173 SSA_NAME_DEF_STMT (result) = phi;
1174 gimple_call_set_lhs (icall_stmt,
1175 make_ssa_name (SSA_NAME_VAR (result), icall_stmt));
1176 add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1177 gimple_call_set_lhs (dcall_stmt,
1178 make_ssa_name (SSA_NAME_VAR (result), dcall_stmt));
1179 add_phi_arg (phi, gimple_call_lhs (dcall_stmt), e_dj, UNKNOWN_LOCATION);
1182 /* Fix eh edges */
1183 lp_nr = lookup_stmt_eh_lp (icall_stmt);
1184 if (lp_nr != 0)
1186 if (stmt_could_throw_p (dcall_stmt))
1188 add_stmt_to_eh_lp (dcall_stmt, lp_nr);
1189 make_eh_edges (dcall_stmt);
1192 gcc_assert (stmt_could_throw_p (icall_stmt));
1193 make_eh_edges (icall_stmt);
1195 /* The old EH edges are sill on the join BB, purge them. */
1196 gimple_purge_dead_eh_edges (join_bb);
1199 return dcall_stmt;
1203 For every checked indirect/virtual call determine if most common pid of
1204 function/class method has probability more than 50%. If yes modify code of
1205 this call to:
1208 static bool
1209 gimple_ic_transform (gimple stmt)
1211 histogram_value histogram;
1212 gcov_type val, count, all, bb_all;
1213 gcov_type prob;
1214 tree callee;
1215 gimple modify;
1216 struct cgraph_node *direct_call;
1218 if (gimple_code (stmt) != GIMPLE_CALL)
1219 return false;
1221 callee = gimple_call_fn (stmt);
1223 if (TREE_CODE (callee) == FUNCTION_DECL)
1224 return false;
1226 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1227 if (!histogram)
1228 return false;
1230 val = histogram->hvalue.counters [0];
1231 count = histogram->hvalue.counters [1];
1232 all = histogram->hvalue.counters [2];
1233 gimple_remove_histogram_value (cfun, stmt, histogram);
1235 if (4 * count <= 3 * all)
1236 return false;
1238 bb_all = gimple_bb (stmt)->count;
1239 /* The order of CHECK_COUNTER calls is important -
1240 since check_counter can correct the third parameter
1241 and we want to make count <= all <= bb_all. */
1242 if ( check_counter (stmt, "ic", &all, &bb_all, bb_all)
1243 || check_counter (stmt, "ic", &count, &all, all))
1244 return false;
1246 if (all > 0)
1247 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1248 else
1249 prob = 0;
1250 direct_call = find_func_by_pid ((int)val);
1252 if (direct_call == NULL)
1253 return false;
1255 modify = gimple_ic (stmt, direct_call, prob, count, all);
1257 if (dump_file)
1259 fprintf (dump_file, "Indirect call -> direct call ");
1260 print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1261 fprintf (dump_file, "=> ");
1262 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1263 fprintf (dump_file, " transformation on insn ");
1264 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1265 fprintf (dump_file, " to ");
1266 print_gimple_stmt (dump_file, modify, 0, TDF_SLIM);
1267 fprintf (dump_file, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1268 " hist->all "HOST_WIDEST_INT_PRINT_DEC"\n", count, all);
1271 return true;
1274 /* Return true if the stringop CALL with FNDECL shall be profiled.
1275 SIZE_ARG be set to the argument index for the size of the string
1276 operation.
1278 static bool
1279 interesting_stringop_to_profile_p (tree fndecl, gimple call, int *size_arg)
1281 enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1283 if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY
1284 && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO)
1285 return false;
1287 switch (fcode)
1289 case BUILT_IN_MEMCPY:
1290 case BUILT_IN_MEMPCPY:
1291 *size_arg = 2;
1292 return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
1293 INTEGER_TYPE, VOID_TYPE);
1294 case BUILT_IN_MEMSET:
1295 *size_arg = 2;
1296 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1297 INTEGER_TYPE, VOID_TYPE);
1298 case BUILT_IN_BZERO:
1299 *size_arg = 1;
1300 return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1301 VOID_TYPE);
1302 default:
1303 gcc_unreachable ();
1307 /* Convert stringop (..., vcall_size)
1308 into
1309 if (vcall_size == icall_size)
1310 stringop (..., icall_size);
1311 else
1312 stringop (..., vcall_size);
1313 assuming we'll propagate a true constant into ICALL_SIZE later. */
1315 static void
1316 gimple_stringop_fixed_value (gimple vcall_stmt, tree icall_size, int prob,
1317 gcov_type count, gcov_type all)
1319 gimple tmp_stmt, cond_stmt, icall_stmt;
1320 tree tmp0, tmp1, tmpv, vcall_size, optype;
1321 basic_block cond_bb, icall_bb, vcall_bb, join_bb;
1322 edge e_ci, e_cv, e_iv, e_ij, e_vj;
1323 gimple_stmt_iterator gsi;
1324 tree fndecl;
1325 int size_arg;
1327 fndecl = gimple_call_fndecl (vcall_stmt);
1328 if (!interesting_stringop_to_profile_p (fndecl, vcall_stmt, &size_arg))
1329 gcc_unreachable();
1331 cond_bb = gimple_bb (vcall_stmt);
1332 gsi = gsi_for_stmt (vcall_stmt);
1334 vcall_size = gimple_call_arg (vcall_stmt, size_arg);
1335 optype = TREE_TYPE (vcall_size);
1337 tmpv = create_tmp_var (optype, "PROF");
1338 tmp0 = make_ssa_name (tmpv, NULL);
1339 tmp1 = make_ssa_name (tmpv, NULL);
1340 tmp_stmt = gimple_build_assign (tmp0, fold_convert (optype, icall_size));
1341 SSA_NAME_DEF_STMT (tmp0) = tmp_stmt;
1342 gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1344 tmp_stmt = gimple_build_assign (tmp1, vcall_size);
1345 SSA_NAME_DEF_STMT (tmp1) = tmp_stmt;
1346 gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1348 cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1349 gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1351 gimple_set_vdef (vcall_stmt, NULL);
1352 gimple_set_vuse (vcall_stmt, NULL);
1353 update_stmt (vcall_stmt);
1354 icall_stmt = gimple_copy (vcall_stmt);
1355 gimple_call_set_arg (icall_stmt, size_arg, icall_size);
1356 gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT);
1358 /* Fix CFG. */
1359 /* Edge e_ci connects cond_bb to icall_bb, etc. */
1360 e_ci = split_block (cond_bb, cond_stmt);
1361 icall_bb = e_ci->dest;
1362 icall_bb->count = count;
1364 e_iv = split_block (icall_bb, icall_stmt);
1365 vcall_bb = e_iv->dest;
1366 vcall_bb->count = all - count;
1368 e_vj = split_block (vcall_bb, vcall_stmt);
1369 join_bb = e_vj->dest;
1370 join_bb->count = all;
1372 e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1373 e_ci->probability = prob;
1374 e_ci->count = count;
1376 e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE);
1377 e_cv->probability = REG_BR_PROB_BASE - prob;
1378 e_cv->count = all - count;
1380 remove_edge (e_iv);
1382 e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU);
1383 e_ij->probability = REG_BR_PROB_BASE;
1384 e_ij->count = count;
1386 e_vj->probability = REG_BR_PROB_BASE;
1387 e_vj->count = all - count;
1389 /* Because these are all string op builtins, they're all nothrow. */
1390 gcc_assert (!stmt_could_throw_p (vcall_stmt));
1391 gcc_assert (!stmt_could_throw_p (icall_stmt));
1394 /* Find values inside STMT for that we want to measure histograms for
1395 division/modulo optimization. */
1396 static bool
1397 gimple_stringops_transform (gimple_stmt_iterator *gsi)
1399 gimple stmt = gsi_stmt (*gsi);
1400 tree fndecl;
1401 tree blck_size;
1402 enum built_in_function fcode;
1403 histogram_value histogram;
1404 gcov_type count, all, val;
1405 tree dest, src;
1406 unsigned int dest_align, src_align;
1407 gcov_type prob;
1408 tree tree_val;
1409 int size_arg;
1411 if (gimple_code (stmt) != GIMPLE_CALL)
1412 return false;
1413 fndecl = gimple_call_fndecl (stmt);
1414 if (!fndecl)
1415 return false;
1416 fcode = DECL_FUNCTION_CODE (fndecl);
1417 if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
1418 return false;
1420 blck_size = gimple_call_arg (stmt, size_arg);
1421 if (TREE_CODE (blck_size) == INTEGER_CST)
1422 return false;
1424 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1425 if (!histogram)
1426 return false;
1427 val = histogram->hvalue.counters[0];
1428 count = histogram->hvalue.counters[1];
1429 all = histogram->hvalue.counters[2];
1430 gimple_remove_histogram_value (cfun, stmt, histogram);
1431 /* We require that count is at least half of all; this means
1432 that for the transformation to fire the value must be constant
1433 at least 80% of time. */
1434 if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1435 return false;
1436 if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1437 return false;
1438 if (all > 0)
1439 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1440 else
1441 prob = 0;
1442 dest = gimple_call_arg (stmt, 0);
1443 dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1444 switch (fcode)
1446 case BUILT_IN_MEMCPY:
1447 case BUILT_IN_MEMPCPY:
1448 src = gimple_call_arg (stmt, 1);
1449 src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1450 if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1451 return false;
1452 break;
1453 case BUILT_IN_MEMSET:
1454 if (!can_store_by_pieces (val, builtin_memset_read_str,
1455 gimple_call_arg (stmt, 1),
1456 dest_align, true))
1457 return false;
1458 break;
1459 case BUILT_IN_BZERO:
1460 if (!can_store_by_pieces (val, builtin_memset_read_str,
1461 integer_zero_node,
1462 dest_align, true))
1463 return false;
1464 break;
1465 default:
1466 gcc_unreachable ();
1468 tree_val = build_int_cst_wide (get_gcov_type (),
1469 (unsigned HOST_WIDE_INT) val,
1470 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1471 if (dump_file)
1473 fprintf (dump_file, "Single value %i stringop transformation on ",
1474 (int)val);
1475 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1477 gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
1479 return true;
1482 void
1483 stringop_block_profile (gimple stmt, unsigned int *expected_align,
1484 HOST_WIDE_INT *expected_size)
1486 histogram_value histogram;
1487 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1488 if (!histogram)
1489 *expected_size = -1;
1490 else if (!histogram->hvalue.counters[1])
1492 *expected_size = -1;
1493 gimple_remove_histogram_value (cfun, stmt, histogram);
1495 else
1497 gcov_type size;
1498 size = ((histogram->hvalue.counters[0]
1499 + histogram->hvalue.counters[1] / 2)
1500 / histogram->hvalue.counters[1]);
1501 /* Even if we can hold bigger value in SIZE, INT_MAX
1502 is safe "infinity" for code generation strategies. */
1503 if (size > INT_MAX)
1504 size = INT_MAX;
1505 *expected_size = size;
1506 gimple_remove_histogram_value (cfun, stmt, histogram);
1508 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1509 if (!histogram)
1510 *expected_align = 0;
1511 else if (!histogram->hvalue.counters[0])
1513 gimple_remove_histogram_value (cfun, stmt, histogram);
1514 *expected_align = 0;
1516 else
1518 gcov_type count;
1519 int alignment;
1521 count = histogram->hvalue.counters[0];
1522 alignment = 1;
1523 while (!(count & alignment)
1524 && (alignment * 2 * BITS_PER_UNIT))
1525 alignment <<= 1;
1526 *expected_align = alignment * BITS_PER_UNIT;
1527 gimple_remove_histogram_value (cfun, stmt, histogram);
1531 struct value_prof_hooks {
1532 /* Find list of values for which we want to measure histograms. */
1533 void (*find_values_to_profile) (histogram_values *);
1535 /* Identify and exploit properties of values that are hard to analyze
1536 statically. See value-prof.c for more detail. */
1537 bool (*value_profile_transformations) (void);
1540 /* Find values inside STMT for that we want to measure histograms for
1541 division/modulo optimization. */
1542 static void
1543 gimple_divmod_values_to_profile (gimple stmt, histogram_values *values)
1545 tree lhs, divisor, op0, type;
1546 histogram_value hist;
1548 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1549 return;
1551 lhs = gimple_assign_lhs (stmt);
1552 type = TREE_TYPE (lhs);
1553 if (!INTEGRAL_TYPE_P (type))
1554 return;
1556 switch (gimple_assign_rhs_code (stmt))
1558 case TRUNC_DIV_EXPR:
1559 case TRUNC_MOD_EXPR:
1560 divisor = gimple_assign_rhs2 (stmt);
1561 op0 = gimple_assign_rhs1 (stmt);
1563 VEC_reserve (histogram_value, heap, *values, 3);
1565 if (is_gimple_reg (divisor))
1566 /* Check for the case where the divisor is the same value most
1567 of the time. */
1568 VEC_quick_push (histogram_value, *values,
1569 gimple_alloc_histogram_value (cfun,
1570 HIST_TYPE_SINGLE_VALUE,
1571 stmt, divisor));
1573 /* For mod, check whether it is not often a noop (or replaceable by
1574 a few subtractions). */
1575 if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
1576 && TYPE_UNSIGNED (type))
1578 tree val;
1579 /* Check for a special case where the divisor is power of 2. */
1580 VEC_quick_push (histogram_value, *values,
1581 gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1582 stmt, divisor));
1584 val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1585 hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1586 stmt, val);
1587 hist->hdata.intvl.int_start = 0;
1588 hist->hdata.intvl.steps = 2;
1589 VEC_quick_push (histogram_value, *values, hist);
1591 return;
1593 default:
1594 return;
1598 /* Find calls inside STMT for that we want to measure histograms for
1599 indirect/virtual call optimization. */
1601 static void
1602 gimple_indirect_call_to_profile (gimple stmt, histogram_values *values)
1604 tree callee;
1606 if (gimple_code (stmt) != GIMPLE_CALL
1607 || gimple_call_fndecl (stmt) != NULL_TREE)
1608 return;
1610 callee = gimple_call_fn (stmt);
1612 VEC_reserve (histogram_value, heap, *values, 3);
1614 VEC_quick_push (histogram_value, *values,
1615 gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1616 stmt, callee));
1618 return;
1621 /* Find values inside STMT for that we want to measure histograms for
1622 string operations. */
1623 static void
1624 gimple_stringops_values_to_profile (gimple stmt, histogram_values *values)
1626 tree fndecl;
1627 tree blck_size;
1628 tree dest;
1629 int size_arg;
1631 if (gimple_code (stmt) != GIMPLE_CALL)
1632 return;
1633 fndecl = gimple_call_fndecl (stmt);
1634 if (!fndecl)
1635 return;
1637 if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
1638 return;
1640 dest = gimple_call_arg (stmt, 0);
1641 blck_size = gimple_call_arg (stmt, size_arg);
1643 if (TREE_CODE (blck_size) != INTEGER_CST)
1645 VEC_safe_push (histogram_value, heap, *values,
1646 gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1647 stmt, blck_size));
1648 VEC_safe_push (histogram_value, heap, *values,
1649 gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1650 stmt, blck_size));
1652 if (TREE_CODE (blck_size) != INTEGER_CST)
1653 VEC_safe_push (histogram_value, heap, *values,
1654 gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1655 stmt, dest));
1658 /* Find values inside STMT for that we want to measure histograms and adds
1659 them to list VALUES. */
1661 static void
1662 gimple_values_to_profile (gimple stmt, histogram_values *values)
1664 if (flag_value_profile_transformations)
1666 gimple_divmod_values_to_profile (stmt, values);
1667 gimple_stringops_values_to_profile (stmt, values);
1668 gimple_indirect_call_to_profile (stmt, values);
1672 static void
1673 gimple_find_values_to_profile (histogram_values *values)
1675 basic_block bb;
1676 gimple_stmt_iterator gsi;
1677 unsigned i;
1678 histogram_value hist = NULL;
1680 *values = NULL;
1681 FOR_EACH_BB (bb)
1682 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1683 gimple_values_to_profile (gsi_stmt (gsi), values);
1685 FOR_EACH_VEC_ELT (histogram_value, *values, i, hist)
1687 switch (hist->type)
1689 case HIST_TYPE_INTERVAL:
1690 hist->n_counters = hist->hdata.intvl.steps + 2;
1691 break;
1693 case HIST_TYPE_POW2:
1694 hist->n_counters = 2;
1695 break;
1697 case HIST_TYPE_SINGLE_VALUE:
1698 hist->n_counters = 3;
1699 break;
1701 case HIST_TYPE_CONST_DELTA:
1702 hist->n_counters = 4;
1703 break;
1705 case HIST_TYPE_INDIR_CALL:
1706 hist->n_counters = 3;
1707 break;
1709 case HIST_TYPE_AVERAGE:
1710 hist->n_counters = 2;
1711 break;
1713 case HIST_TYPE_IOR:
1714 hist->n_counters = 1;
1715 break;
1717 default:
1718 gcc_unreachable ();
1720 if (dump_file)
1722 fprintf (dump_file, "Stmt ");
1723 print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
1724 dump_histogram_value (dump_file, hist);
1729 static struct value_prof_hooks gimple_value_prof_hooks = {
1730 gimple_find_values_to_profile,
1731 gimple_value_profile_transformations
1734 void
1735 gimple_register_value_prof_hooks (void)
1737 gcc_assert (current_ir_type () == IR_GIMPLE);
1738 value_prof_hooks = &gimple_value_prof_hooks;
1741 /* IR-independent entry points. */
1742 void
1743 find_values_to_profile (histogram_values *values)
1745 (value_prof_hooks->find_values_to_profile) (values);
1748 bool
1749 value_profile_transformations (void)
1751 return (value_prof_hooks->value_profile_transformations) ();