target-supports.exp (check_effective_target_mips_soft_float): Return true for MIPS16...
[official-gcc.git] / gcc / value-prof.c
blob124a3c866b1a25361301d7f22be3aafb0ab8f7ca
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
9 version.
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
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl.h"
25 #include "expr.h"
26 #include "hard-reg-set.h"
27 #include "basic-block.h"
28 #include "value-prof.h"
29 #include "output.h"
30 #include "flags.h"
31 #include "insn-config.h"
32 #include "recog.h"
33 #include "optabs.h"
34 #include "regs.h"
35 #include "ggc.h"
36 #include "tree-flow.h"
37 #include "tree-flow-inline.h"
38 #include "diagnostic.h"
39 #include "coverage.h"
40 #include "tree.h"
41 #include "gcov-io.h"
42 #include "cgraph.h"
43 #include "timevar.h"
44 #include "tree-pass.h"
45 #include "toplev.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
61 profiling.
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
66 inliner).
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;
100 hist->type = type;
101 return hist;
104 /* Hash value for histogram. */
106 static hashval_t
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. */
114 static int
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. */
122 static void
123 set_histogram_value (struct function *fun, tree stmt, histogram_value hist)
125 void **loc;
126 if (!hist && !VALUE_HISTOGRAMS (fun))
127 return;
128 if (!VALUE_HISTOGRAMS (fun))
129 VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
130 histogram_eq, NULL);
131 loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
132 htab_hash_pointer (stmt),
133 hist ? INSERT : NO_INSERT);
134 if (!hist)
136 if (loc)
137 htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
138 return;
140 *loc = hist;
143 /* Get histogram list for STMT. */
145 histogram_value
146 gimple_histogram_value (struct function *fun, tree stmt)
148 if (!VALUE_HISTOGRAMS (fun))
149 return NULL;
150 return htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
151 htab_hash_pointer (stmt));
154 /* Add histogram for STMT. */
156 void
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. */
165 void
166 gimple_remove_histogram_value (struct function *fun, tree stmt, histogram_value hist)
168 histogram_value hist2 = gimple_histogram_value (fun, stmt);
169 if (hist == hist2)
171 set_histogram_value (fun, stmt, hist->hvalue.next);
173 else
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));
182 #endif
183 free (hist);
186 /* Lookup histogram of type TYPE in the STMT. */
188 histogram_value
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)
194 return hist;
195 return NULL;
198 /* Dump information about HIST to DUMP_FILE. */
200 static void
201 dump_histogram_value (FILE *dump_file, histogram_value hist)
203 switch (hist->type)
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)
212 unsigned int i;
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");
222 break;
224 case HIST_TYPE_POW2:
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");
234 break;
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");
248 break;
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");
260 break;
262 case HIST_TYPE_IOR:
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");
270 break;
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");
284 break;
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");
297 break;
301 /* Dump all histograms attached to STMT to DUMP_FILE. */
303 void
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. */
313 void
314 gimple_remove_stmt_histograms (struct function *fun, tree stmt)
316 histogram_value val;
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. */
323 void
324 gimple_duplicate_stmt_histograms (struct function *fun, tree stmt,
325 struct function *ofun, tree ostmt)
327 histogram_value val;
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);
339 static bool error_found = false;
341 /* Helper function for verify_histograms. For each histogram reachable via htab
342 walk verify that it was reached via statement walk. */
344 static int
345 visit_hist (void **slot, void *data)
347 struct pointer_set_t *visited = (struct pointer_set_t *) data;
348 histogram_value hist = *(histogram_value *) slot;
349 if (!pointer_set_contains (visited, hist))
351 error ("Dead histogram");
352 dump_histogram_value (stderr, hist);
353 debug_generic_stmt (hist->hvalue.stmt);
354 error_found = true;
356 return 1;
359 /* Verify sanity of the histograms. */
361 void
362 verify_histograms (void)
364 basic_block bb;
365 block_stmt_iterator bsi;
366 histogram_value hist;
367 struct pointer_set_t *visited_hists;
369 error_found = false;
370 visited_hists = pointer_set_create ();
371 FOR_EACH_BB (bb)
372 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
374 tree stmt = bsi_stmt (bsi);
376 for (hist = gimple_histogram_value (cfun, stmt); hist; hist = hist->hvalue.next)
378 if (hist->hvalue.stmt != stmt)
380 error ("Histogram value statement does not correspond to statement"
381 " it is associated with");
382 debug_generic_stmt (stmt);
383 dump_histogram_value (stderr, hist);
384 error_found = true;
386 pointer_set_insert (visited_hists, hist);
389 if (VALUE_HISTOGRAMS (cfun))
390 htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists);
391 pointer_set_destroy (visited_hists);
392 if (error_found)
393 internal_error ("verify_histograms failed");
396 /* Helper function for verify_histograms. For each histogram reachable via htab
397 walk verify that it was reached via statement walk. */
399 static int
400 free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
402 histogram_value hist = *(histogram_value *) slot;
403 free (hist->hvalue.counters);
404 #ifdef ENABLE_CHECKING
405 memset (hist, 0xab, sizeof (*hist));
406 #endif
407 free (hist);
408 return 1;
411 void
412 free_histograms (void)
414 if (VALUE_HISTOGRAMS (cfun))
416 htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);
417 htab_delete (VALUE_HISTOGRAMS (cfun));
418 VALUE_HISTOGRAMS (cfun) = NULL;
422 /* The overall number of invocations of the counter should match execution count
423 of basic block. Report it as error rather than internal error as it might
424 mean that user has misused the profile somehow. */
425 static bool
426 check_counter (tree stmt, const char * name, gcov_type all, gcov_type bb_count)
428 if (all != bb_count)
430 location_t * locus;
431 locus = (stmt != NULL && EXPR_HAS_LOCATION (stmt)
432 ? EXPR_LOCUS (stmt)
433 : &DECL_SOURCE_LOCATION (current_function_decl));
434 error ("%HCorrupted value profile: %s profiler overall count (%d) does not match BB count (%d)",
435 locus, name, (int)all, (int)bb_count);
436 return true;
438 return false;
441 /* Tree based transformations. */
442 static bool
443 tree_value_profile_transformations (void)
445 basic_block bb;
446 block_stmt_iterator bsi;
447 bool changed = false;
449 FOR_EACH_BB (bb)
451 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
453 tree stmt = bsi_stmt (bsi);
454 histogram_value th = gimple_histogram_value (cfun, stmt);
455 if (!th)
456 continue;
458 if (dump_file)
460 fprintf (dump_file, "Trying transformations on stmt ");
461 print_generic_stmt (dump_file, stmt, TDF_SLIM);
462 dump_histograms_for_stmt (cfun, dump_file, stmt);
465 /* Transformations: */
466 /* The order of things in this conditional controls which
467 transformation is used when more than one is applicable. */
468 /* It is expected that any code added by the transformations
469 will be added before the current statement, and that the
470 current statement remain valid (although possibly
471 modified) upon return. */
472 if (flag_value_profile_transformations
473 && (tree_mod_subtract_transform (stmt)
474 || tree_divmod_fixed_value_transform (stmt)
475 || tree_mod_pow2_value_transform (stmt)
476 || tree_stringops_transform (&bsi)
477 || tree_ic_transform (stmt)))
479 stmt = bsi_stmt (bsi);
480 changed = true;
481 /* Original statement may no longer be in the same block. */
482 if (bb != bb_for_stmt (stmt))
484 bb = bb_for_stmt (stmt);
485 bsi = bsi_for_stmt (stmt);
491 if (changed)
493 counts_to_freqs ();
496 return changed;
499 /* Generate code for transformation 1 (with OPERATION, operands OP1
500 and OP2, whose value is expected to be VALUE, parent modify-expr STMT and
501 probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
502 within roundoff error). This generates the result into a temp and returns
503 the temp; it does not replace or alter the original STMT. */
504 static tree
505 tree_divmod_fixed_value (tree stmt, tree operation,
506 tree op1, tree op2, tree value, int prob, gcov_type count,
507 gcov_type all)
509 tree stmt1, stmt2, stmt3;
510 tree tmp1, tmp2, tmpv;
511 tree label_decl1 = create_artificial_label ();
512 tree label_decl2 = create_artificial_label ();
513 tree label1, label2;
514 tree bb1end, bb2end, bb3end;
515 basic_block bb, bb2, bb3, bb4;
516 tree optype = TREE_TYPE (operation);
517 edge e12, e13, e23, e24, e34;
518 block_stmt_iterator bsi;
520 bb = bb_for_stmt (stmt);
521 bsi = bsi_for_stmt (stmt);
523 tmpv = create_tmp_var (optype, "PROF");
524 tmp1 = create_tmp_var (optype, "PROF");
525 stmt1 = build_gimple_modify_stmt (tmpv, fold_convert (optype, value));
526 stmt2 = build_gimple_modify_stmt (tmp1, op2);
527 stmt3 = build3 (COND_EXPR, void_type_node,
528 build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
529 NULL_TREE, NULL_TREE);
530 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
531 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
532 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
533 bb1end = stmt3;
535 tmp2 = create_tmp_var (optype, "PROF");
536 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
537 stmt1 = build_gimple_modify_stmt (tmp2,
538 build2 (TREE_CODE (operation), optype,
539 op1, tmpv));
540 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
541 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
542 bb2end = stmt1;
544 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
545 stmt1 = build_gimple_modify_stmt (tmp2,
546 build2 (TREE_CODE (operation), optype,
547 op1, op2));
548 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
549 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
550 bb3end = stmt1;
552 /* Fix CFG. */
553 /* Edge e23 connects bb2 to bb3, etc. */
554 e12 = split_block (bb, bb1end);
555 bb2 = e12->dest;
556 bb2->count = count;
557 e23 = split_block (bb2, bb2end);
558 bb3 = e23->dest;
559 bb3->count = all - count;
560 e34 = split_block (bb3, bb3end);
561 bb4 = e34->dest;
562 bb4->count = all;
564 e12->flags &= ~EDGE_FALLTHRU;
565 e12->flags |= EDGE_FALSE_VALUE;
566 e12->probability = prob;
567 e12->count = count;
569 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
570 e13->probability = REG_BR_PROB_BASE - prob;
571 e13->count = all - count;
573 remove_edge (e23);
575 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
576 e24->probability = REG_BR_PROB_BASE;
577 e24->count = count;
579 e34->probability = REG_BR_PROB_BASE;
580 e34->count = all - count;
582 return tmp2;
585 /* Do transform 1) on INSN if applicable. */
586 static bool
587 tree_divmod_fixed_value_transform (tree stmt)
589 histogram_value histogram;
590 enum tree_code code;
591 gcov_type val, count, all;
592 tree modify, op, op1, op2, result, value, tree_val;
593 int prob;
595 modify = stmt;
596 if (TREE_CODE (stmt) == RETURN_EXPR
597 && TREE_OPERAND (stmt, 0)
598 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
599 modify = TREE_OPERAND (stmt, 0);
600 if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
601 return false;
602 op = GIMPLE_STMT_OPERAND (modify, 1);
603 if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
604 return false;
605 code = TREE_CODE (op);
607 if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
608 return false;
610 op1 = TREE_OPERAND (op, 0);
611 op2 = TREE_OPERAND (op, 1);
613 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
614 if (!histogram)
615 return false;
617 value = histogram->hvalue.value;
618 val = histogram->hvalue.counters[0];
619 count = histogram->hvalue.counters[1];
620 all = histogram->hvalue.counters[2];
621 gimple_remove_histogram_value (cfun, stmt, histogram);
623 /* We require that count is at least half of all; this means
624 that for the transformation to fire the value must be constant
625 at least 50% of time (and 75% gives the guarantee of usage). */
626 if (simple_cst_equal (op2, value) != 1 || 2 * count < all
627 || !maybe_hot_bb_p (bb_for_stmt (stmt)))
628 return false;
630 if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
631 return false;
633 /* Compute probability of taking the optimal path. */
634 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
636 tree_val = build_int_cst_wide (get_gcov_type (),
637 (unsigned HOST_WIDE_INT) val,
638 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
639 result = tree_divmod_fixed_value (stmt, op, op1, op2, tree_val, prob, count, all);
641 if (dump_file)
643 fprintf (dump_file, "Div/mod by constant ");
644 print_generic_expr (dump_file, value, TDF_SLIM);
645 fprintf (dump_file, "=");
646 print_generic_expr (dump_file, tree_val, TDF_SLIM);
647 fprintf (dump_file, " transformation on insn ");
648 print_generic_stmt (dump_file, stmt, TDF_SLIM);
651 GIMPLE_STMT_OPERAND (modify, 1) = result;
653 return true;
656 /* Generate code for transformation 2 (with OPERATION, operands OP1
657 and OP2, parent modify-expr STMT and probability of taking the optimal
658 path PROB, which is equivalent to COUNT/ALL within roundoff error).
659 This generates the result into a temp and returns
660 the temp; it does not replace or alter the original STMT. */
661 static tree
662 tree_mod_pow2 (tree stmt, tree operation, tree op1, tree op2, int prob,
663 gcov_type count, gcov_type all)
665 tree stmt1, stmt2, stmt3, stmt4;
666 tree tmp2, tmp3;
667 tree label_decl1 = create_artificial_label ();
668 tree label_decl2 = create_artificial_label ();
669 tree label1, label2;
670 tree bb1end, bb2end, bb3end;
671 basic_block bb, bb2, bb3, bb4;
672 tree optype = TREE_TYPE (operation);
673 edge e12, e13, e23, e24, e34;
674 block_stmt_iterator bsi;
675 tree result = create_tmp_var (optype, "PROF");
677 bb = bb_for_stmt (stmt);
678 bsi = bsi_for_stmt (stmt);
680 tmp2 = create_tmp_var (optype, "PROF");
681 tmp3 = create_tmp_var (optype, "PROF");
682 stmt2 = build_gimple_modify_stmt (tmp2,
683 build2 (PLUS_EXPR, optype, op2,
684 build_int_cst (optype, -1)));
685 stmt3 = build_gimple_modify_stmt (tmp3,
686 build2 (BIT_AND_EXPR, optype, tmp2, op2));
687 stmt4 = build3 (COND_EXPR, void_type_node,
688 build2 (NE_EXPR, boolean_type_node,
689 tmp3, build_int_cst (optype, 0)),
690 NULL_TREE, NULL_TREE);
691 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
692 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
693 bsi_insert_before (&bsi, stmt4, BSI_SAME_STMT);
694 bb1end = stmt4;
696 /* tmp2 == op2-1 inherited from previous block */
697 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
698 stmt1 = build_gimple_modify_stmt (result,
699 build2 (BIT_AND_EXPR, optype, op1, tmp2));
700 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
701 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
702 bb2end = stmt1;
704 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
705 stmt1 = build_gimple_modify_stmt (result,
706 build2 (TREE_CODE (operation), optype,
707 op1, op2));
708 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
709 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
710 bb3end = stmt1;
712 /* Fix CFG. */
713 /* Edge e23 connects bb2 to bb3, etc. */
714 e12 = split_block (bb, bb1end);
715 bb2 = e12->dest;
716 bb2->count = count;
717 e23 = split_block (bb2, bb2end);
718 bb3 = e23->dest;
719 bb3->count = all - count;
720 e34 = split_block (bb3, bb3end);
721 bb4 = e34->dest;
722 bb4->count = all;
724 e12->flags &= ~EDGE_FALLTHRU;
725 e12->flags |= EDGE_FALSE_VALUE;
726 e12->probability = prob;
727 e12->count = count;
729 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
730 e13->probability = REG_BR_PROB_BASE - prob;
731 e13->count = all - count;
733 remove_edge (e23);
735 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
736 e24->probability = REG_BR_PROB_BASE;
737 e24->count = count;
739 e34->probability = REG_BR_PROB_BASE;
740 e34->count = all - count;
742 return result;
745 /* Do transform 2) on INSN if applicable. */
746 static bool
747 tree_mod_pow2_value_transform (tree stmt)
749 histogram_value histogram;
750 enum tree_code code;
751 gcov_type count, wrong_values, all;
752 tree modify, op, op1, op2, result, value;
753 int prob;
755 modify = stmt;
756 if (TREE_CODE (stmt) == RETURN_EXPR
757 && TREE_OPERAND (stmt, 0)
758 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
759 modify = TREE_OPERAND (stmt, 0);
760 if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
761 return false;
762 op = GIMPLE_STMT_OPERAND (modify, 1);
763 if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
764 return false;
765 code = TREE_CODE (op);
767 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
768 return false;
770 op1 = TREE_OPERAND (op, 0);
771 op2 = TREE_OPERAND (op, 1);
773 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
774 if (!histogram)
775 return false;
777 value = histogram->hvalue.value;
778 wrong_values = histogram->hvalue.counters[0];
779 count = histogram->hvalue.counters[1];
781 gimple_remove_histogram_value (cfun, stmt, histogram);
783 /* We require that we hit a power of 2 at least half of all evaluations. */
784 if (simple_cst_equal (op2, value) != 1 || count < wrong_values
785 || !maybe_hot_bb_p (bb_for_stmt (stmt)))
786 return false;
788 if (dump_file)
790 fprintf (dump_file, "Mod power of 2 transformation on insn ");
791 print_generic_stmt (dump_file, stmt, TDF_SLIM);
794 /* Compute probability of taking the optimal path. */
795 all = count + wrong_values;
797 if (check_counter (stmt, "pow2", all, bb_for_stmt (stmt)->count))
798 return false;
800 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
802 result = tree_mod_pow2 (stmt, op, op1, op2, prob, count, all);
804 GIMPLE_STMT_OPERAND (modify, 1) = result;
806 return true;
809 /* Generate code for transformations 3 and 4 (with OPERATION, operands OP1
810 and OP2, parent modify-expr STMT, and NCOUNTS the number of cases to
811 support. Currently only NCOUNTS==0 or 1 is supported and this is
812 built into this interface. The probabilities of taking the optimal
813 paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
814 COUNT2/ALL respectively within roundoff error). This generates the
815 result into a temp and returns the temp; it does not replace or alter
816 the original STMT. */
817 /* FIXME: Generalize the interface to handle NCOUNTS > 1. */
819 static tree
820 tree_mod_subtract (tree stmt, tree operation, tree op1, tree op2,
821 int prob1, int prob2, int ncounts,
822 gcov_type count1, gcov_type count2, gcov_type all)
824 tree stmt1, stmt2, stmt3;
825 tree tmp1;
826 tree label_decl1 = create_artificial_label ();
827 tree label_decl2 = create_artificial_label ();
828 tree label_decl3 = create_artificial_label ();
829 tree label1, label2, label3;
830 tree bb1end, bb2end = NULL_TREE, bb3end;
831 basic_block bb, bb2, bb3, bb4;
832 tree optype = TREE_TYPE (operation);
833 edge e12, e23 = 0, e24, e34, e14;
834 block_stmt_iterator bsi;
835 tree result = create_tmp_var (optype, "PROF");
837 bb = bb_for_stmt (stmt);
838 bsi = bsi_for_stmt (stmt);
840 tmp1 = create_tmp_var (optype, "PROF");
841 stmt1 = build_gimple_modify_stmt (result, op1);
842 stmt2 = build_gimple_modify_stmt (tmp1, op2);
843 stmt3 = build3 (COND_EXPR, void_type_node,
844 build2 (LT_EXPR, boolean_type_node, result, tmp1),
845 NULL_TREE, NULL_TREE);
846 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
847 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
848 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
849 bb1end = stmt3;
851 if (ncounts) /* Assumed to be 0 or 1 */
853 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
854 stmt1 = build_gimple_modify_stmt (result,
855 build2 (MINUS_EXPR, optype,
856 result, tmp1));
857 stmt2 = build3 (COND_EXPR, void_type_node,
858 build2 (LT_EXPR, boolean_type_node, result, tmp1),
859 NULL_TREE, NULL_TREE);
860 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
861 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
862 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
863 bb2end = stmt2;
866 /* Fallback case. */
867 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
868 stmt1 = build_gimple_modify_stmt (result,
869 build2 (TREE_CODE (operation), optype,
870 result, tmp1));
871 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
872 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
873 bb3end = stmt1;
875 label3 = build1 (LABEL_EXPR, void_type_node, label_decl3);
876 bsi_insert_before (&bsi, label3, BSI_SAME_STMT);
878 /* Fix CFG. */
879 /* Edge e23 connects bb2 to bb3, etc. */
880 /* However block 3 is optional; if it is not there, references
881 to 3 really refer to block 2. */
882 e12 = split_block (bb, bb1end);
883 bb2 = e12->dest;
884 bb2->count = all - count1;
886 if (ncounts) /* Assumed to be 0 or 1. */
888 e23 = split_block (bb2, bb2end);
889 bb3 = e23->dest;
890 bb3->count = all - count1 - count2;
893 e34 = split_block (ncounts ? bb3 : bb2, bb3end);
894 bb4 = e34->dest;
895 bb4->count = all;
897 e12->flags &= ~EDGE_FALLTHRU;
898 e12->flags |= EDGE_FALSE_VALUE;
899 e12->probability = REG_BR_PROB_BASE - prob1;
900 e12->count = all - count1;
902 e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
903 e14->probability = prob1;
904 e14->count = count1;
906 if (ncounts) /* Assumed to be 0 or 1. */
908 e23->flags &= ~EDGE_FALLTHRU;
909 e23->flags |= EDGE_FALSE_VALUE;
910 e23->count = all - count1 - count2;
911 e23->probability = REG_BR_PROB_BASE - prob2;
913 e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
914 e24->probability = prob2;
915 e24->count = count2;
918 e34->probability = REG_BR_PROB_BASE;
919 e34->count = all - count1 - count2;
921 return result;
924 /* Do transforms 3) and 4) on INSN if applicable. */
925 static bool
926 tree_mod_subtract_transform (tree stmt)
928 histogram_value histogram;
929 enum tree_code code;
930 gcov_type count, wrong_values, all;
931 tree modify, op, op1, op2, result, value;
932 int prob1, prob2;
933 unsigned int i, steps;
934 gcov_type count1, count2;
936 modify = stmt;
937 if (TREE_CODE (stmt) == RETURN_EXPR
938 && TREE_OPERAND (stmt, 0)
939 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
940 modify = TREE_OPERAND (stmt, 0);
941 if (TREE_CODE (modify) != GIMPLE_MODIFY_STMT)
942 return false;
943 op = GIMPLE_STMT_OPERAND (modify, 1);
944 if (!INTEGRAL_TYPE_P (TREE_TYPE (op)))
945 return false;
946 code = TREE_CODE (op);
948 if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (TREE_TYPE (op)))
949 return false;
951 op1 = TREE_OPERAND (op, 0);
952 op2 = TREE_OPERAND (op, 1);
954 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
955 if (!histogram)
956 return false;
958 value = histogram->hvalue.value;
959 all = 0;
960 wrong_values = 0;
961 for (i = 0; i < histogram->hdata.intvl.steps; i++)
962 all += histogram->hvalue.counters[i];
964 wrong_values += histogram->hvalue.counters[i];
965 wrong_values += histogram->hvalue.counters[i+1];
966 steps = histogram->hdata.intvl.steps;
967 all += wrong_values;
968 count1 = histogram->hvalue.counters[0];
969 count2 = histogram->hvalue.counters[1];
971 /* Compute probability of taking the optimal path. */
972 if (check_counter (stmt, "interval", all, bb_for_stmt (stmt)->count))
974 gimple_remove_histogram_value (cfun, stmt, histogram);
975 return false;
978 /* We require that we use just subtractions in at least 50% of all
979 evaluations. */
980 count = 0;
981 for (i = 0; i < histogram->hdata.intvl.steps; i++)
983 count += histogram->hvalue.counters[i];
984 if (count * 2 >= all)
985 break;
987 if (i == steps
988 || !maybe_hot_bb_p (bb_for_stmt (stmt)))
989 return false;
991 gimple_remove_histogram_value (cfun, stmt, histogram);
992 if (dump_file)
994 fprintf (dump_file, "Mod subtract transformation on insn ");
995 print_generic_stmt (dump_file, stmt, TDF_SLIM);
998 /* Compute probability of taking the optimal path(s). */
999 prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
1000 prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
1002 /* In practice, "steps" is always 2. This interface reflects this,
1003 and will need to be changed if "steps" can change. */
1004 result = tree_mod_subtract (stmt, op, op1, op2, prob1, prob2, i,
1005 count1, count2, all);
1007 GIMPLE_STMT_OPERAND (modify, 1) = result;
1009 return true;
1012 static struct cgraph_node** pid_map = NULL;
1014 /* Initialize map of pids (pid -> cgraph node) */
1016 static void
1017 init_pid_map (void)
1019 struct cgraph_node *n;
1021 if (pid_map != NULL)
1022 return;
1024 pid_map
1025 = (struct cgraph_node**) xmalloc (sizeof (struct cgraph_node*) * cgraph_max_pid);
1027 for (n = cgraph_nodes; n; n = n->next)
1029 if (n->pid != -1)
1030 pid_map [n->pid] = n;
1034 /* Return cgraph node for function with pid */
1036 static inline struct cgraph_node*
1037 find_func_by_pid (int pid)
1039 init_pid_map ();
1041 return pid_map [pid];
1044 /* Do transformation
1046 if (actual_callee_addres == addres_of_most_common_function/method)
1047 do direct call
1048 else
1049 old call
1052 static tree
1053 tree_ic (tree stmt, tree call, struct cgraph_node* direct_call,
1054 int prob, gcov_type count, gcov_type all)
1056 tree stmt1, stmt2, stmt3;
1057 tree tmp1, tmpv, tmp;
1058 tree label_decl1 = create_artificial_label ();
1059 tree label_decl2 = create_artificial_label ();
1060 tree label1, label2;
1061 tree bb1end, bb2end, bb3end;
1062 tree new_call;
1063 basic_block bb, bb2, bb3, bb4;
1064 tree optype = build_pointer_type (void_type_node);
1065 edge e12, e13, e23, e24, e34;
1066 block_stmt_iterator bsi;
1067 int region;
1069 bb = bb_for_stmt (stmt);
1070 bsi = bsi_for_stmt (stmt);
1072 tmpv = create_tmp_var (optype, "PROF");
1073 tmp1 = create_tmp_var (optype, "PROF");
1074 stmt1 = build_gimple_modify_stmt (tmpv,
1075 unshare_expr (CALL_EXPR_FN (call)));
1076 tmp = fold_convert (optype, build_addr (direct_call->decl,
1077 current_function_decl));
1078 stmt2 = build_gimple_modify_stmt (tmp1, tmp);
1079 stmt3 = build3 (COND_EXPR, void_type_node,
1080 build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1081 NULL_TREE, NULL_TREE);
1082 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1083 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1084 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1085 bb1end = stmt3;
1087 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1088 stmt1 = unshare_expr (stmt);
1089 new_call = get_call_expr_in (stmt1);
1090 CALL_EXPR_FN (new_call) = build_addr (direct_call->decl,
1091 current_function_decl);
1092 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1093 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1094 bb2end = stmt1;
1096 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1097 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1098 bb3end = stmt;
1100 /* Fix CFG. */
1101 /* Edge e23 connects bb2 to bb3, etc. */
1102 e12 = split_block (bb, bb1end);
1103 bb2 = e12->dest;
1104 bb2->count = count;
1105 e23 = split_block (bb2, bb2end);
1106 bb3 = e23->dest;
1107 bb3->count = all - count;
1108 e34 = split_block (bb3, bb3end);
1109 bb4 = e34->dest;
1110 bb4->count = all;
1112 e12->flags &= ~EDGE_FALLTHRU;
1113 e12->flags |= EDGE_FALSE_VALUE;
1114 e12->probability = prob;
1115 e12->count = count;
1117 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1118 e13->probability = REG_BR_PROB_BASE - prob;
1119 e13->count = all - count;
1121 remove_edge (e23);
1123 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1124 e24->probability = REG_BR_PROB_BASE;
1125 e24->count = count;
1126 e34->probability = REG_BR_PROB_BASE;
1127 e34->count = all - count;
1129 /* Fix eh edges */
1130 region = lookup_stmt_eh_region (stmt);
1131 if (region >=0 && tree_could_throw_p (stmt1))
1133 add_stmt_to_eh_region (stmt1, region);
1134 make_eh_edges (stmt1);
1137 if (region >=0 && tree_could_throw_p (stmt))
1139 tree_purge_dead_eh_edges (bb4);
1140 make_eh_edges (stmt);
1143 return stmt1;
1147 For every checked indirect/virtual call determine if most common pid of
1148 function/class method has probability more than 50%. If yes modify code of
1149 this call to:
1152 static bool
1153 tree_ic_transform (tree stmt)
1155 histogram_value histogram;
1156 gcov_type val, count, all;
1157 int prob;
1158 tree call, callee, modify;
1159 struct cgraph_node *direct_call;
1161 call = get_call_expr_in (stmt);
1163 if (!call || TREE_CODE (call) != CALL_EXPR)
1164 return false;
1166 callee = CALL_EXPR_FN (call);
1168 if (TREE_CODE (callee) == ADDR_EXPR)
1169 return false;
1171 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1172 if (!histogram)
1173 return false;
1175 val = histogram->hvalue.counters [0];
1176 count = histogram->hvalue.counters [1];
1177 all = histogram->hvalue.counters [2];
1178 gimple_remove_histogram_value (cfun, stmt, histogram);
1180 if (4 * count <= 3 * all)
1181 return false;
1183 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1184 direct_call = find_func_by_pid ((int)val);
1186 if (direct_call == NULL)
1187 return false;
1189 modify = tree_ic (stmt, call, direct_call, prob, count, all);
1191 if (dump_file)
1193 fprintf (dump_file, "Indirect call -> direct call ");
1194 print_generic_expr (dump_file, call, TDF_SLIM);
1195 fprintf (dump_file, "=> ");
1196 print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1197 fprintf (dump_file, " transformation on insn ");
1198 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1199 fprintf (dump_file, " to ");
1200 print_generic_stmt (dump_file, modify, TDF_SLIM);
1203 return true;
1206 /* Return true if the stringop CALL with FNDECL shall be profiled. */
1207 static bool
1208 interesting_stringop_to_profile_p (tree fndecl, tree call)
1210 enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1212 if (fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_MEMCPY
1213 && fcode != BUILT_IN_BZERO)
1214 return false;
1216 switch (fcode)
1218 case BUILT_IN_MEMCPY:
1219 case BUILT_IN_MEMPCPY:
1220 return validate_arglist (call,
1221 POINTER_TYPE, POINTER_TYPE, INTEGER_TYPE,
1222 VOID_TYPE);
1223 case BUILT_IN_MEMSET:
1224 return validate_arglist (call,
1225 POINTER_TYPE, INTEGER_TYPE, INTEGER_TYPE,
1226 VOID_TYPE);
1227 case BUILT_IN_BZERO:
1228 return validate_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1229 VOID_TYPE);
1230 default:
1231 gcc_unreachable ();
1235 /* Convert stringop (..., size)
1236 into
1237 if (size == VALUE)
1238 stringop (...., VALUE);
1239 else
1240 stringop (...., size);
1241 assuming constant propagation of VALUE will happen later.
1243 static void
1244 tree_stringop_fixed_value (tree stmt, tree value, int prob, gcov_type count,
1245 gcov_type all)
1247 tree stmt1, stmt2, stmt3;
1248 tree tmp1, tmpv;
1249 tree label_decl1 = create_artificial_label ();
1250 tree label_decl2 = create_artificial_label ();
1251 tree label1, label2;
1252 tree bb1end, bb2end;
1253 basic_block bb, bb2, bb3, bb4;
1254 edge e12, e13, e23, e24, e34;
1255 block_stmt_iterator bsi;
1256 tree call = get_call_expr_in (stmt);
1257 tree blck_size = CALL_EXPR_ARG (call, 2);
1258 tree optype = TREE_TYPE (blck_size);
1259 int region;
1261 bb = bb_for_stmt (stmt);
1262 bsi = bsi_for_stmt (stmt);
1264 if (bsi_end_p (bsi))
1266 edge_iterator ei;
1267 for (ei = ei_start (bb->succs); (e34 = ei_safe_edge (ei)); )
1268 if (!e34->flags & EDGE_ABNORMAL)
1269 break;
1271 else
1273 e34 = split_block (bb, stmt);
1274 bsi = bsi_for_stmt (stmt);
1276 bb4 = e34->dest;
1278 tmpv = create_tmp_var (optype, "PROF");
1279 tmp1 = create_tmp_var (optype, "PROF");
1280 stmt1 = build_gimple_modify_stmt (tmpv, fold_convert (optype, value));
1281 stmt2 = build_gimple_modify_stmt (tmp1, blck_size);
1282 stmt3 = build3 (COND_EXPR, void_type_node,
1283 build2 (NE_EXPR, boolean_type_node, tmp1, tmpv),
1284 NULL_TREE, NULL_TREE);
1285 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1286 bsi_insert_before (&bsi, stmt2, BSI_SAME_STMT);
1287 bsi_insert_before (&bsi, stmt3, BSI_SAME_STMT);
1288 bb1end = stmt3;
1290 label1 = build1 (LABEL_EXPR, void_type_node, label_decl1);
1291 stmt1 = unshare_expr (stmt);
1292 call = get_call_expr_in (stmt1);
1293 CALL_EXPR_ARG (call, 2) = value;
1294 bsi_insert_before (&bsi, label1, BSI_SAME_STMT);
1295 bsi_insert_before (&bsi, stmt1, BSI_SAME_STMT);
1296 region = lookup_stmt_eh_region (stmt);
1297 if (region >= 0)
1298 add_stmt_to_eh_region (stmt1, region);
1299 bb2end = stmt1;
1300 label2 = build1 (LABEL_EXPR, void_type_node, label_decl2);
1301 bsi_insert_before (&bsi, label2, BSI_SAME_STMT);
1303 /* Fix CFG. */
1304 /* Edge e23 connects bb2 to bb3, etc. */
1305 e12 = split_block (bb, bb1end);
1306 bb2 = e12->dest;
1307 bb2->count = count;
1308 e23 = split_block (bb2, bb2end);
1309 bb3 = e23->dest;
1310 bb3->count = all - count;
1312 e12->flags &= ~EDGE_FALLTHRU;
1313 e12->flags |= EDGE_FALSE_VALUE;
1314 e12->probability = prob;
1315 e12->count = count;
1317 e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
1318 e13->probability = REG_BR_PROB_BASE - prob;
1319 e13->count = all - count;
1321 remove_edge (e23);
1323 e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
1324 e24->probability = REG_BR_PROB_BASE;
1325 e24->count = count;
1327 e34->probability = REG_BR_PROB_BASE;
1328 e34->count = all - count;
1331 /* Find values inside STMT for that we want to measure histograms for
1332 division/modulo optimization. */
1333 static bool
1334 tree_stringops_transform (block_stmt_iterator *bsi)
1336 tree stmt = bsi_stmt (*bsi);
1337 tree call = get_call_expr_in (stmt);
1338 tree fndecl;
1339 tree blck_size;
1340 enum built_in_function fcode;
1341 histogram_value histogram;
1342 gcov_type count, all, val;
1343 tree value;
1344 tree dest, src;
1345 unsigned int dest_align, src_align;
1346 int prob;
1347 tree tree_val;
1349 if (!call)
1350 return false;
1351 fndecl = get_callee_fndecl (call);
1352 if (!fndecl)
1353 return false;
1354 fcode = DECL_FUNCTION_CODE (fndecl);
1355 if (!interesting_stringop_to_profile_p (fndecl, call))
1356 return false;
1358 if (fcode == BUILT_IN_BZERO)
1359 blck_size = CALL_EXPR_ARG (call, 1);
1360 else
1361 blck_size = CALL_EXPR_ARG (call, 2);
1362 if (TREE_CODE (blck_size) == INTEGER_CST)
1363 return false;
1365 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1366 if (!histogram)
1367 return false;
1368 value = histogram->hvalue.value;
1369 val = histogram->hvalue.counters[0];
1370 count = histogram->hvalue.counters[1];
1371 all = histogram->hvalue.counters[2];
1372 gimple_remove_histogram_value (cfun, stmt, histogram);
1373 /* We require that count is at least half of all; this means
1374 that for the transformation to fire the value must be constant
1375 at least 80% of time. */
1376 if ((6 * count / 5) < all || !maybe_hot_bb_p (bb_for_stmt (stmt)))
1377 return false;
1378 if (check_counter (stmt, "value", all, bb_for_stmt (stmt)->count))
1379 return false;
1380 prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1381 dest = CALL_EXPR_ARG (call, 0);
1382 dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1383 switch (fcode)
1385 case BUILT_IN_MEMCPY:
1386 case BUILT_IN_MEMPCPY:
1387 src = CALL_EXPR_ARG (call, 1);
1388 src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1389 if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1390 return false;
1391 break;
1392 case BUILT_IN_MEMSET:
1393 if (!can_store_by_pieces (val, builtin_memset_read_str,
1394 CALL_EXPR_ARG (call, 1),
1395 dest_align, true))
1396 return false;
1397 break;
1398 case BUILT_IN_BZERO:
1399 if (!can_store_by_pieces (val, builtin_memset_read_str,
1400 integer_zero_node,
1401 dest_align, true))
1402 return false;
1403 break;
1404 default:
1405 gcc_unreachable ();
1407 tree_val = build_int_cst_wide (get_gcov_type (),
1408 (unsigned HOST_WIDE_INT) val,
1409 val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1410 if (dump_file)
1412 fprintf (dump_file, "Single value %i stringop transformation on ",
1413 (int)val);
1414 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1416 tree_stringop_fixed_value (stmt, tree_val, prob, count, all);
1418 return true;
1421 void
1422 stringop_block_profile (tree stmt, unsigned int *expected_align,
1423 HOST_WIDE_INT *expected_size)
1425 histogram_value histogram;
1426 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1427 if (!histogram)
1428 *expected_size = -1;
1429 else if (!histogram->hvalue.counters[1])
1431 *expected_size = -1;
1432 gimple_remove_histogram_value (cfun, stmt, histogram);
1434 else
1436 gcov_type size;
1437 size = ((histogram->hvalue.counters[0]
1438 + histogram->hvalue.counters[1] / 2)
1439 / histogram->hvalue.counters[1]);
1440 /* Even if we can hold bigger value in SIZE, INT_MAX
1441 is safe "infinity" for code generation strategies. */
1442 if (size > INT_MAX)
1443 size = INT_MAX;
1444 *expected_size = size;
1445 gimple_remove_histogram_value (cfun, stmt, histogram);
1447 histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1448 if (!histogram)
1449 *expected_align = 0;
1450 else if (!histogram->hvalue.counters[0])
1452 gimple_remove_histogram_value (cfun, stmt, histogram);
1453 *expected_align = 0;
1455 else
1457 gcov_type count;
1458 int alignment;
1460 count = histogram->hvalue.counters[0];
1461 alignment = 1;
1462 while (!(count & alignment)
1463 && (alignment * 2 * BITS_PER_UNIT))
1464 alignment <<= 1;
1465 *expected_align = alignment * BITS_PER_UNIT;
1466 gimple_remove_histogram_value (cfun, stmt, histogram);
1470 struct value_prof_hooks {
1471 /* Find list of values for which we want to measure histograms. */
1472 void (*find_values_to_profile) (histogram_values *);
1474 /* Identify and exploit properties of values that are hard to analyze
1475 statically. See value-prof.c for more detail. */
1476 bool (*value_profile_transformations) (void);
1479 /* Find values inside STMT for that we want to measure histograms for
1480 division/modulo optimization. */
1481 static void
1482 tree_divmod_values_to_profile (tree stmt, histogram_values *values)
1484 tree assign, lhs, rhs, divisor, op0, type;
1485 histogram_value hist;
1487 if (TREE_CODE (stmt) == RETURN_EXPR)
1488 assign = TREE_OPERAND (stmt, 0);
1489 else
1490 assign = stmt;
1492 if (!assign
1493 || TREE_CODE (assign) != GIMPLE_MODIFY_STMT)
1494 return;
1495 lhs = GIMPLE_STMT_OPERAND (assign, 0);
1496 type = TREE_TYPE (lhs);
1497 if (!INTEGRAL_TYPE_P (type))
1498 return;
1500 rhs = GIMPLE_STMT_OPERAND (assign, 1);
1501 switch (TREE_CODE (rhs))
1503 case TRUNC_DIV_EXPR:
1504 case TRUNC_MOD_EXPR:
1505 divisor = TREE_OPERAND (rhs, 1);
1506 op0 = TREE_OPERAND (rhs, 0);
1508 VEC_reserve (histogram_value, heap, *values, 3);
1510 if (is_gimple_reg (divisor))
1511 /* Check for the case where the divisor is the same value most
1512 of the time. */
1513 VEC_quick_push (histogram_value, *values,
1514 gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1515 stmt, divisor));
1517 /* For mod, check whether it is not often a noop (or replaceable by
1518 a few subtractions). */
1519 if (TREE_CODE (rhs) == TRUNC_MOD_EXPR
1520 && TYPE_UNSIGNED (type))
1522 tree val;
1523 /* Check for a special case where the divisor is power of 2. */
1524 VEC_quick_push (histogram_value, *values,
1525 gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1526 stmt, divisor));
1528 val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1529 hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1530 stmt, val);
1531 hist->hdata.intvl.int_start = 0;
1532 hist->hdata.intvl.steps = 2;
1533 VEC_quick_push (histogram_value, *values, hist);
1535 return;
1537 default:
1538 return;
1542 /* Find calls inside STMT for that we want to measure histograms for
1543 indirect/virtual call optimization. */
1545 static void
1546 tree_indirect_call_to_profile (tree stmt, histogram_values *values)
1548 tree call;
1549 tree callee;
1551 call = get_call_expr_in (stmt);
1553 if (!call || TREE_CODE (call) != CALL_EXPR)
1554 return;
1556 callee = CALL_EXPR_FN (call);
1558 if (TREE_CODE (callee) == ADDR_EXPR)
1559 return;
1561 VEC_reserve (histogram_value, heap, *values, 3);
1563 VEC_quick_push (histogram_value, *values,
1564 gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1565 stmt, callee));
1567 return;
1570 /* Find values inside STMT for that we want to measure histograms for
1571 string operations. */
1572 static void
1573 tree_stringops_values_to_profile (tree stmt, histogram_values *values)
1575 tree call = get_call_expr_in (stmt);
1576 tree fndecl;
1577 tree blck_size;
1578 tree dest;
1579 enum built_in_function fcode;
1581 if (!call)
1582 return;
1583 fndecl = get_callee_fndecl (call);
1584 if (!fndecl)
1585 return;
1586 fcode = DECL_FUNCTION_CODE (fndecl);
1588 if (!interesting_stringop_to_profile_p (fndecl, call))
1589 return;
1591 dest = CALL_EXPR_ARG (call, 0);
1592 if (fcode == BUILT_IN_BZERO)
1593 blck_size = CALL_EXPR_ARG (call, 1);
1594 else
1595 blck_size = CALL_EXPR_ARG (call, 2);
1597 if (TREE_CODE (blck_size) != INTEGER_CST)
1599 VEC_safe_push (histogram_value, heap, *values,
1600 gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1601 stmt, blck_size));
1602 VEC_safe_push (histogram_value, heap, *values,
1603 gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1604 stmt, blck_size));
1606 if (TREE_CODE (blck_size) != INTEGER_CST)
1607 VEC_safe_push (histogram_value, heap, *values,
1608 gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1609 stmt, dest));
1612 /* Find values inside STMT for that we want to measure histograms and adds
1613 them to list VALUES. */
1615 static void
1616 tree_values_to_profile (tree stmt, histogram_values *values)
1618 if (flag_value_profile_transformations)
1620 tree_divmod_values_to_profile (stmt, values);
1621 tree_stringops_values_to_profile (stmt, values);
1622 tree_indirect_call_to_profile (stmt, values);
1626 static void
1627 tree_find_values_to_profile (histogram_values *values)
1629 basic_block bb;
1630 block_stmt_iterator bsi;
1631 unsigned i;
1632 histogram_value hist = NULL;
1634 *values = NULL;
1635 FOR_EACH_BB (bb)
1636 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1637 tree_values_to_profile (bsi_stmt (bsi), values);
1639 for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
1641 switch (hist->type)
1643 case HIST_TYPE_INTERVAL:
1644 hist->n_counters = hist->hdata.intvl.steps + 2;
1645 break;
1647 case HIST_TYPE_POW2:
1648 hist->n_counters = 2;
1649 break;
1651 case HIST_TYPE_SINGLE_VALUE:
1652 hist->n_counters = 3;
1653 break;
1655 case HIST_TYPE_CONST_DELTA:
1656 hist->n_counters = 4;
1657 break;
1659 case HIST_TYPE_INDIR_CALL:
1660 hist->n_counters = 3;
1661 break;
1663 case HIST_TYPE_AVERAGE:
1664 hist->n_counters = 2;
1665 break;
1667 case HIST_TYPE_IOR:
1668 hist->n_counters = 1;
1669 break;
1671 default:
1672 gcc_unreachable ();
1674 if (dump_file)
1676 fprintf (dump_file, "Stmt ");
1677 print_generic_expr (dump_file, hist->hvalue.stmt, TDF_SLIM);
1678 dump_histogram_value (dump_file, hist);
1683 static struct value_prof_hooks tree_value_prof_hooks = {
1684 tree_find_values_to_profile,
1685 tree_value_profile_transformations
1688 void
1689 tree_register_value_prof_hooks (void)
1691 gcc_assert (current_ir_type () == IR_GIMPLE);
1692 value_prof_hooks = &tree_value_prof_hooks;
1695 /* IR-independent entry points. */
1696 void
1697 find_values_to_profile (histogram_values *values)
1699 (value_prof_hooks->find_values_to_profile) (values);
1702 bool
1703 value_profile_transformations (void)
1705 return (value_prof_hooks->value_profile_transformations) ();