OSDN Git Service

9109286587c64802bbcef4abfb7819f27be3e1eb
[pf3gnuchains/gcc-fork.git] / gcc / value-prof.c
1 /* Transformations based on profile information for values.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009  Free Software
3    Foundation, Inc.
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>.  */
20
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 "coverage.h"
41 #include "tree.h"
42 #include "gcov-io.h"
43 #include "cgraph.h"
44 #include "timevar.h"
45 #include "tree-pass.h"
46 #include "toplev.h"
47 #include "pointer-set.h"
48
49 static struct value_prof_hooks *value_prof_hooks;
50
51 /* In this file value profile based optimizations are placed.  Currently the
52    following optimizations are implemented (for more detailed descriptions
53    see comments at value_profile_transformations):
54
55    1) Division/modulo specialization.  Provided that we can determine that the
56       operands of the division have some special properties, we may use it to
57       produce more effective code.
58    2) Speculative prefetching.  If we are able to determine that the difference
59       between addresses accessed by a memory reference is usually constant, we
60       may add the prefetch instructions.
61       FIXME: This transformation was removed together with RTL based value
62       profiling.
63
64    3) Indirect/virtual call specialization. If we can determine most
65       common function callee in indirect/virtual call. We can use this
66       information to improve code effectiveness (especially info for
67       inliner).
68
69    Every such optimization should add its requirements for profiled values to
70    insn_values_to_profile function.  This function is called from branch_prob
71    in profile.c and the requested values are instrumented by it in the first
72    compilation with -fprofile-arcs.  The optimization may then read the
73    gathered data in the second compilation with -fbranch-probabilities.
74
75    The measured data is pointed to from the histograms
76    field of the statement annotation of the instrumented insns.  It is
77    kept as a linked list of struct histogram_value_t's, which contain the
78    same information as above.  */
79
80
81 static tree gimple_divmod_fixed_value (gimple, tree, int, gcov_type, gcov_type);
82 static tree gimple_mod_pow2 (gimple, int, gcov_type, gcov_type);
83 static tree gimple_mod_subtract (gimple, int, int, int, gcov_type, gcov_type,
84                                  gcov_type);
85 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
86 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
87 static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
88 static bool gimple_stringops_transform (gimple_stmt_iterator *);
89 static bool gimple_ic_transform (gimple);
90
91 /* Allocate histogram value.  */
92
93 static histogram_value
94 gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
95                               enum hist_type type, gimple stmt, tree value)
96 {
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;
102 }
103
104 /* Hash value for histogram.  */
105
106 static hashval_t
107 histogram_hash (const void *x)
108 {
109   return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);
110 }
111
112 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y.  */
113
114 static int
115 histogram_eq (const void *x, const void *y)
116 {
117   return ((const_histogram_value) x)->hvalue.stmt == (const_gimple) y;
118 }
119
120 /* Set histogram for STMT.  */
121
122 static void
123 set_histogram_value (struct function *fun, gimple stmt, histogram_value hist)
124 {
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)
135     {
136       if (loc)
137         htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
138       return;
139     }
140   *loc = hist;
141 }
142
143 /* Get histogram list for STMT.  */
144
145 histogram_value
146 gimple_histogram_value (struct function *fun, gimple stmt)
147 {
148   if (!VALUE_HISTOGRAMS (fun))
149     return NULL;
150   return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
151                                                 htab_hash_pointer (stmt));
152 }
153
154 /* Add histogram for STMT.  */
155
156 void
157 gimple_add_histogram_value (struct function *fun, gimple stmt,
158                             histogram_value hist)
159 {
160   hist->hvalue.next = gimple_histogram_value (fun, stmt);
161   set_histogram_value (fun, stmt, hist);
162 }
163
164
165 /* Remove histogram HIST from STMT's histogram list.  */
166
167 void
168 gimple_remove_histogram_value (struct function *fun, gimple stmt,
169                                histogram_value hist)
170 {
171   histogram_value hist2 = gimple_histogram_value (fun, stmt);
172   if (hist == hist2)
173     {
174       set_histogram_value (fun, stmt, hist->hvalue.next);
175     }
176   else
177     {
178       while (hist2->hvalue.next != hist)
179         hist2 = hist2->hvalue.next;
180       hist2->hvalue.next = hist->hvalue.next;
181     }
182   free (hist->hvalue.counters);
183 #ifdef ENABLE_CHECKING
184   memset (hist, 0xab, sizeof (*hist));
185 #endif
186   free (hist);
187 }
188
189
190 /* Lookup histogram of type TYPE in the STMT.  */
191
192 histogram_value
193 gimple_histogram_value_of_type (struct function *fun, gimple stmt,
194                                 enum hist_type type)
195 {
196   histogram_value hist;
197   for (hist = gimple_histogram_value (fun, stmt); hist;
198        hist = hist->hvalue.next)
199     if (hist->type == type)
200       return hist;
201   return NULL;
202 }
203
204 /* Dump information about HIST to DUMP_FILE.  */
205
206 static void
207 dump_histogram_value (FILE *dump_file, histogram_value hist)
208 {
209   switch (hist->type)
210     {
211     case HIST_TYPE_INTERVAL:
212       fprintf (dump_file, "Interval counter range %d -- %d",
213                hist->hdata.intvl.int_start,
214                (hist->hdata.intvl.int_start
215                 + hist->hdata.intvl.steps - 1));
216       if (hist->hvalue.counters)
217         {
218            unsigned int i;
219            fprintf(dump_file, " [");
220            for (i = 0; i < hist->hdata.intvl.steps; i++)
221              fprintf (dump_file, " %d:"HOST_WIDEST_INT_PRINT_DEC,
222                       hist->hdata.intvl.int_start + i,
223                       (HOST_WIDEST_INT) hist->hvalue.counters[i]);
224            fprintf (dump_file, " ] outside range:"HOST_WIDEST_INT_PRINT_DEC,
225                     (HOST_WIDEST_INT) hist->hvalue.counters[i]);
226         }
227       fprintf (dump_file, ".\n");
228       break;
229
230     case HIST_TYPE_POW2:
231       fprintf (dump_file, "Pow2 counter ");
232       if (hist->hvalue.counters)
233         {
234            fprintf (dump_file, "pow2:"HOST_WIDEST_INT_PRINT_DEC
235                     " nonpow2:"HOST_WIDEST_INT_PRINT_DEC,
236                     (HOST_WIDEST_INT) hist->hvalue.counters[0],
237                     (HOST_WIDEST_INT) hist->hvalue.counters[1]);
238         }
239       fprintf (dump_file, ".\n");
240       break;
241
242     case HIST_TYPE_SINGLE_VALUE:
243       fprintf (dump_file, "Single value ");
244       if (hist->hvalue.counters)
245         {
246            fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
247                     " match:"HOST_WIDEST_INT_PRINT_DEC
248                     " wrong:"HOST_WIDEST_INT_PRINT_DEC,
249                     (HOST_WIDEST_INT) hist->hvalue.counters[0],
250                     (HOST_WIDEST_INT) hist->hvalue.counters[1],
251                     (HOST_WIDEST_INT) hist->hvalue.counters[2]);
252         }
253       fprintf (dump_file, ".\n");
254       break;
255
256     case HIST_TYPE_AVERAGE:
257       fprintf (dump_file, "Average value ");
258       if (hist->hvalue.counters)
259         {
260            fprintf (dump_file, "sum:"HOST_WIDEST_INT_PRINT_DEC
261                     " times:"HOST_WIDEST_INT_PRINT_DEC,
262                     (HOST_WIDEST_INT) hist->hvalue.counters[0],
263                     (HOST_WIDEST_INT) hist->hvalue.counters[1]);
264         }
265       fprintf (dump_file, ".\n");
266       break;
267
268     case HIST_TYPE_IOR:
269       fprintf (dump_file, "IOR value ");
270       if (hist->hvalue.counters)
271         {
272            fprintf (dump_file, "ior:"HOST_WIDEST_INT_PRINT_DEC,
273                     (HOST_WIDEST_INT) hist->hvalue.counters[0]);
274         }
275       fprintf (dump_file, ".\n");
276       break;
277
278     case HIST_TYPE_CONST_DELTA:
279       fprintf (dump_file, "Constant delta ");
280       if (hist->hvalue.counters)
281         {
282            fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
283                     " match:"HOST_WIDEST_INT_PRINT_DEC
284                     " wrong:"HOST_WIDEST_INT_PRINT_DEC,
285                     (HOST_WIDEST_INT) hist->hvalue.counters[0],
286                     (HOST_WIDEST_INT) hist->hvalue.counters[1],
287                     (HOST_WIDEST_INT) hist->hvalue.counters[2]);
288         }
289       fprintf (dump_file, ".\n");
290       break;
291     case HIST_TYPE_INDIR_CALL:
292       fprintf (dump_file, "Indirect call ");
293       if (hist->hvalue.counters)
294         {
295            fprintf (dump_file, "value:"HOST_WIDEST_INT_PRINT_DEC
296                     " match:"HOST_WIDEST_INT_PRINT_DEC
297                     " all:"HOST_WIDEST_INT_PRINT_DEC,
298                     (HOST_WIDEST_INT) hist->hvalue.counters[0],
299                     (HOST_WIDEST_INT) hist->hvalue.counters[1],
300                     (HOST_WIDEST_INT) hist->hvalue.counters[2]);
301         }
302       fprintf (dump_file, ".\n");
303       break;
304    }
305 }
306
307 /* Dump all histograms attached to STMT to DUMP_FILE.  */
308
309 void
310 dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple stmt)
311 {
312   histogram_value hist;
313   for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
314    dump_histogram_value (dump_file, hist);
315 }
316
317 /* Remove all histograms associated with STMT.  */
318
319 void
320 gimple_remove_stmt_histograms (struct function *fun, gimple stmt)
321 {
322   histogram_value val;
323   while ((val = gimple_histogram_value (fun, stmt)) != NULL)
324     gimple_remove_histogram_value (fun, stmt, val);
325 }
326
327 /* Duplicate all histograms associates with OSTMT to STMT.  */
328
329 void
330 gimple_duplicate_stmt_histograms (struct function *fun, gimple stmt,
331                                   struct function *ofun, gimple ostmt)
332 {
333   histogram_value val;
334   for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
335     {
336       histogram_value new_val = gimple_alloc_histogram_value (fun, val->type, NULL, NULL);
337       memcpy (new_val, val, sizeof (*val));
338       new_val->hvalue.stmt = stmt;
339       new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
340       memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
341       gimple_add_histogram_value (fun, stmt, new_val);
342     }
343 }
344
345
346 /* Move all histograms associated with OSTMT to STMT.  */
347
348 void
349 gimple_move_stmt_histograms (struct function *fun, gimple stmt, gimple ostmt)
350 {
351   histogram_value val = gimple_histogram_value (fun, ostmt);
352   if (val)
353     {
354       /* The following three statements can't be reordered,
355          because histogram hashtab relies on stmt field value
356          for finding the exact slot. */
357       set_histogram_value (fun, ostmt, NULL);
358       for (; val != NULL; val = val->hvalue.next)
359         val->hvalue.stmt = stmt;
360       set_histogram_value (fun, stmt, val);
361     }
362 }
363
364 static bool error_found = false;
365
366 /* Helper function for verify_histograms.  For each histogram reachable via htab
367    walk verify that it was reached via statement walk.  */
368
369 static int
370 visit_hist (void **slot, void *data)
371 {
372   struct pointer_set_t *visited = (struct pointer_set_t *) data;
373   histogram_value hist = *(histogram_value *) slot;
374   if (!pointer_set_contains (visited, hist))
375     {
376       error ("Dead histogram");
377       dump_histogram_value (stderr, hist);
378       debug_gimple_stmt (hist->hvalue.stmt);
379       error_found = true;
380     }
381   return 1;
382 }
383
384
385 /* Verify sanity of the histograms.  */
386
387 void
388 verify_histograms (void)
389 {
390   basic_block bb;
391   gimple_stmt_iterator gsi;
392   histogram_value hist;
393   struct pointer_set_t *visited_hists;
394
395   error_found = false;
396   visited_hists = pointer_set_create ();
397   FOR_EACH_BB (bb)
398     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
399       {
400         gimple stmt = gsi_stmt (gsi);
401
402         for (hist = gimple_histogram_value (cfun, stmt); hist;
403              hist = hist->hvalue.next)
404           {
405             if (hist->hvalue.stmt != stmt)
406               {
407                 error ("Histogram value statement does not correspond to "
408                        "the statement it is associated with");
409                 debug_gimple_stmt (stmt);
410                 dump_histogram_value (stderr, hist);
411                 error_found = true;
412               }
413             pointer_set_insert (visited_hists, hist);
414           }
415       }
416   if (VALUE_HISTOGRAMS (cfun))
417     htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, visited_hists);
418   pointer_set_destroy (visited_hists);
419   if (error_found)
420     internal_error ("verify_histograms failed");
421 }
422
423 /* Helper function for verify_histograms.  For each histogram reachable via htab
424    walk verify that it was reached via statement walk.  */
425
426 static int
427 free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
428 {
429   histogram_value hist = *(histogram_value *) slot;
430   free (hist->hvalue.counters);
431 #ifdef ENABLE_CHECKING
432   memset (hist, 0xab, sizeof (*hist));
433 #endif
434   free (hist);
435   return 1;
436 }
437
438 void
439 free_histograms (void)
440 {
441   if (VALUE_HISTOGRAMS (cfun))
442     {
443       htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);
444       htab_delete (VALUE_HISTOGRAMS (cfun));
445       VALUE_HISTOGRAMS (cfun) = NULL;
446     }
447 }
448
449
450 /* The overall number of invocations of the counter should match
451    execution count of basic block.  Report it as error rather than
452    internal error as it might mean that user has misused the profile
453    somehow.  */
454
455 static bool
456 check_counter (gimple stmt, const char * name,
457                gcov_type *count, gcov_type *all, gcov_type bb_count)
458 {
459   if (*all != bb_count || *count > *all)
460     {
461       location_t locus;
462       locus = (stmt != NULL)
463               ? gimple_location (stmt)
464               : DECL_SOURCE_LOCATION (current_function_decl);
465       if (flag_profile_correction)
466         {
467           inform (locus, "Correcting inconsistent value profile: "
468                   "%s profiler overall count (%d) does not match BB count "
469                   "(%d)", name, (int)*all, (int)bb_count);
470           *all = bb_count;
471           if (*count > *all)
472             *count = *all;
473           return false;
474         }
475       else
476         {
477           error_at (locus, "Corrupted value profile: %s "
478                     "profiler overall count (%d) does not match BB count (%d)",
479                     name, (int)*all, (int)bb_count);
480           return true;
481         }
482     }
483
484   return false;
485 }
486
487
488 /* GIMPLE based transformations. */
489
490 static bool
491 gimple_value_profile_transformations (void)
492 {
493   basic_block bb;
494   gimple_stmt_iterator gsi;
495   bool changed = false;
496
497   FOR_EACH_BB (bb)
498     {
499       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
500         {
501           gimple stmt = gsi_stmt (gsi);
502           histogram_value th = gimple_histogram_value (cfun, stmt);
503           if (!th)
504             continue;
505
506           if (dump_file)
507             {
508               fprintf (dump_file, "Trying transformations on stmt ");
509               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
510               dump_histograms_for_stmt (cfun, dump_file, stmt);
511             }
512
513           /* Transformations:  */
514           /* The order of things in this conditional controls which
515              transformation is used when more than one is applicable.  */
516           /* It is expected that any code added by the transformations
517              will be added before the current statement, and that the
518              current statement remain valid (although possibly
519              modified) upon return.  */
520           if (flag_value_profile_transformations
521               && (gimple_mod_subtract_transform (&gsi)
522                   || gimple_divmod_fixed_value_transform (&gsi)
523                   || gimple_mod_pow2_value_transform (&gsi)
524                   || gimple_stringops_transform (&gsi)
525                   || gimple_ic_transform (stmt)))
526             {
527               stmt = gsi_stmt (gsi);
528               changed = true;
529               /* Original statement may no longer be in the same block. */
530               if (bb != gimple_bb (stmt))
531                 {
532                   bb = gimple_bb (stmt);
533                   gsi = gsi_for_stmt (stmt);
534                 }
535             }
536         }
537     }
538
539   if (changed)
540     {
541       counts_to_freqs ();
542     }
543
544   return changed;
545 }
546
547
548 /* Generate code for transformation 1 (with parent gimple assignment
549    STMT and probability of taking the optimal path PROB, which is
550    equivalent to COUNT/ALL within roundoff error).  This generates the
551    result into a temp and returns the temp; it does not replace or
552    alter the original STMT.  */
553
554 static tree
555 gimple_divmod_fixed_value (gimple stmt, tree value, int prob, gcov_type count,
556                            gcov_type all)
557 {
558   gimple stmt1, stmt2, stmt3;
559   tree tmp1, tmp2, tmpv;
560   gimple bb1end, bb2end, bb3end;
561   basic_block bb, bb2, bb3, bb4;
562   tree optype, op1, op2;
563   edge e12, e13, e23, e24, e34;
564   gimple_stmt_iterator gsi;
565
566   gcc_assert (is_gimple_assign (stmt)
567               && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
568                   || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));
569
570   optype = TREE_TYPE (gimple_assign_lhs (stmt));
571   op1 = gimple_assign_rhs1 (stmt);
572   op2 = gimple_assign_rhs2 (stmt);
573
574   bb = gimple_bb (stmt);
575   gsi = gsi_for_stmt (stmt);
576
577   tmpv = create_tmp_var (optype, "PROF");
578   tmp1 = create_tmp_var (optype, "PROF");
579   stmt1 = gimple_build_assign (tmpv, fold_convert (optype, value));
580   stmt2 = gimple_build_assign (tmp1, op2);
581   stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE);
582   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
583   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
584   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
585   bb1end = stmt3;
586
587   tmp2 = create_tmp_var (optype, "PROF");
588   stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,
589                                         op1, tmpv);
590   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
591   bb2end = stmt1;
592
593   stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), tmp2,
594                                         op1, op2);
595   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
596   bb3end = stmt1;
597
598   /* Fix CFG. */
599   /* Edge e23 connects bb2 to bb3, etc. */
600   e12 = split_block (bb, bb1end);
601   bb2 = e12->dest;
602   bb2->count = count;
603   e23 = split_block (bb2, bb2end);
604   bb3 = e23->dest;
605   bb3->count = all - count;
606   e34 = split_block (bb3, bb3end);
607   bb4 = e34->dest;
608   bb4->count = all;
609
610   e12->flags &= ~EDGE_FALLTHRU;
611   e12->flags |= EDGE_FALSE_VALUE;
612   e12->probability = prob;
613   e12->count = count;
614
615   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
616   e13->probability = REG_BR_PROB_BASE - prob;
617   e13->count = all - count;
618
619   remove_edge (e23);
620   
621   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
622   e24->probability = REG_BR_PROB_BASE;
623   e24->count = count;
624
625   e34->probability = REG_BR_PROB_BASE;
626   e34->count = all - count;
627
628   return tmp2;
629 }
630
631
632 /* Do transform 1) on INSN if applicable.  */
633
634 static bool
635 gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
636 {
637   histogram_value histogram;
638   enum tree_code code;
639   gcov_type val, count, all;
640   tree result, value, tree_val;
641   gcov_type prob;
642   gimple stmt;
643
644   stmt = gsi_stmt (*si);
645   if (gimple_code (stmt) != GIMPLE_ASSIGN)
646     return false;
647
648   if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
649     return false;
650
651   code = gimple_assign_rhs_code (stmt);
652   
653   if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
654     return false;
655
656   histogram = gimple_histogram_value_of_type (cfun, stmt,
657                                               HIST_TYPE_SINGLE_VALUE);
658   if (!histogram)
659     return false;
660
661   value = histogram->hvalue.value;
662   val = histogram->hvalue.counters[0];
663   count = histogram->hvalue.counters[1];
664   all = histogram->hvalue.counters[2];
665   gimple_remove_histogram_value (cfun, stmt, histogram);
666
667   /* We require that count is at least half of all; this means
668      that for the transformation to fire the value must be constant
669      at least 50% of time (and 75% gives the guarantee of usage).  */
670   if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
671       || 2 * count < all
672       || optimize_bb_for_size_p (gimple_bb (stmt)))
673     return false;
674
675   if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
676     return false;
677
678   /* Compute probability of taking the optimal path.  */
679   if (all > 0)
680     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
681   else
682     prob = 0;
683
684   tree_val = build_int_cst_wide (get_gcov_type (),
685                                  (unsigned HOST_WIDE_INT) val,
686                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
687   result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all);
688
689   if (dump_file)
690     {
691       fprintf (dump_file, "Div/mod by constant ");
692       print_generic_expr (dump_file, value, TDF_SLIM);
693       fprintf (dump_file, "=");
694       print_generic_expr (dump_file, tree_val, TDF_SLIM);
695       fprintf (dump_file, " transformation on insn ");
696       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
697     }
698
699   gimple_assign_set_rhs_from_tree (si, result);
700
701   return true;
702 }
703
704 /* Generate code for transformation 2 (with parent gimple assign STMT and
705    probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
706    within roundoff error).  This generates the result into a temp and returns 
707    the temp; it does not replace or alter the original STMT.  */
708 static tree
709 gimple_mod_pow2 (gimple stmt, int prob, gcov_type count, gcov_type all)
710 {
711   gimple stmt1, stmt2, stmt3, stmt4;
712   tree tmp2, tmp3;
713   gimple bb1end, bb2end, bb3end;
714   basic_block bb, bb2, bb3, bb4;
715   tree optype, op1, op2;
716   edge e12, e13, e23, e24, e34;
717   gimple_stmt_iterator gsi;
718   tree result;
719
720   gcc_assert (is_gimple_assign (stmt)
721               && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
722
723   optype = TREE_TYPE (gimple_assign_lhs (stmt));
724   op1 = gimple_assign_rhs1 (stmt);
725   op2 = gimple_assign_rhs2 (stmt);
726
727   bb = gimple_bb (stmt);
728   gsi = gsi_for_stmt (stmt);
729
730   result = create_tmp_var (optype, "PROF");
731   tmp2 = create_tmp_var (optype, "PROF");
732   tmp3 = create_tmp_var (optype, "PROF");
733   stmt2 = gimple_build_assign_with_ops (PLUS_EXPR, tmp2, op2,
734                                         build_int_cst (optype, -1));
735   stmt3 = gimple_build_assign_with_ops (BIT_AND_EXPR, tmp3, tmp2, op2);
736   stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0),
737                              NULL_TREE, NULL_TREE);
738   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
739   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
740   gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT);
741   bb1end = stmt4;
742
743   /* tmp2 == op2-1 inherited from previous block.  */
744   stmt1 = gimple_build_assign_with_ops (BIT_AND_EXPR, result, op1, tmp2);
745   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
746   bb2end = stmt1;
747
748   stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
749                                         op1, op2);
750   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
751   bb3end = stmt1;
752
753   /* Fix CFG. */
754   /* Edge e23 connects bb2 to bb3, etc. */
755   e12 = split_block (bb, bb1end);
756   bb2 = e12->dest;
757   bb2->count = count;
758   e23 = split_block (bb2, bb2end);
759   bb3 = e23->dest;
760   bb3->count = all - count;
761   e34 = split_block (bb3, bb3end);
762   bb4 = e34->dest;
763   bb4->count = all;
764
765   e12->flags &= ~EDGE_FALLTHRU;
766   e12->flags |= EDGE_FALSE_VALUE;
767   e12->probability = prob;
768   e12->count = count;
769
770   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
771   e13->probability = REG_BR_PROB_BASE - prob;
772   e13->count = all - count;
773
774   remove_edge (e23);
775   
776   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
777   e24->probability = REG_BR_PROB_BASE;
778   e24->count = count;
779
780   e34->probability = REG_BR_PROB_BASE;
781   e34->count = all - count;
782
783   return result;
784 }
785
786 /* Do transform 2) on INSN if applicable.  */
787 static bool
788 gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
789 {
790   histogram_value histogram;
791   enum tree_code code;
792   gcov_type count, wrong_values, all;
793   tree lhs_type, result, value;
794   gcov_type prob;
795   gimple stmt;
796
797   stmt = gsi_stmt (*si);
798   if (gimple_code (stmt) != GIMPLE_ASSIGN)
799     return false;
800
801   lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
802   if (!INTEGRAL_TYPE_P (lhs_type))
803     return false;
804
805   code = gimple_assign_rhs_code (stmt);
806   
807   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
808     return false;
809
810   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
811   if (!histogram)
812     return false;
813
814   value = histogram->hvalue.value;
815   wrong_values = histogram->hvalue.counters[0];
816   count = histogram->hvalue.counters[1];
817
818   gimple_remove_histogram_value (cfun, stmt, histogram);
819
820   /* We require that we hit a power of 2 at least half of all evaluations.  */
821   if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
822       || count < wrong_values
823       || optimize_bb_for_size_p (gimple_bb (stmt)))
824     return false;
825
826   if (dump_file)
827     {
828       fprintf (dump_file, "Mod power of 2 transformation on insn ");
829       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
830     }
831
832   /* Compute probability of taking the optimal path.  */
833   all = count + wrong_values;
834
835   if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
836     return false;
837
838   if (all > 0)
839     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
840   else
841     prob = 0;
842
843   result = gimple_mod_pow2 (stmt, prob, count, all);
844
845   gimple_assign_set_rhs_from_tree (si, result);
846
847   return true;
848 }
849
850 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
851    NCOUNTS the number of cases to support.  Currently only NCOUNTS==0 or 1 is
852    supported and this is built into this interface.  The probabilities of taking
853    the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
854    COUNT2/ALL respectively within roundoff error).  This generates the 
855    result into a temp and returns the temp; it does not replace or alter 
856    the original STMT.  */
857 /* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
858
859 static tree
860 gimple_mod_subtract (gimple stmt, int prob1, int prob2, int ncounts,
861                      gcov_type count1, gcov_type count2, gcov_type all)
862 {
863   gimple stmt1, stmt2, stmt3;
864   tree tmp1;
865   gimple bb1end, bb2end = NULL, bb3end;
866   basic_block bb, bb2, bb3, bb4;
867   tree optype, op1, op2;
868   edge e12, e23 = 0, e24, e34, e14;
869   gimple_stmt_iterator gsi;
870   tree result;
871
872   gcc_assert (is_gimple_assign (stmt)
873               && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
874
875   optype = TREE_TYPE (gimple_assign_lhs (stmt));
876   op1 = gimple_assign_rhs1 (stmt);
877   op2 = gimple_assign_rhs2 (stmt);
878
879   bb = gimple_bb (stmt);
880   gsi = gsi_for_stmt (stmt);
881
882   result = create_tmp_var (optype, "PROF");
883   tmp1 = create_tmp_var (optype, "PROF");
884   stmt1 = gimple_build_assign (result, op1);
885   stmt2 = gimple_build_assign (tmp1, op2);
886   stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
887   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
888   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
889   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
890   bb1end = stmt3;
891
892   if (ncounts)  /* Assumed to be 0 or 1 */
893     {
894       stmt1 = gimple_build_assign_with_ops (MINUS_EXPR, result, result, tmp1);
895       stmt2 = 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       bb2end = stmt2;
899     }
900
901   /* Fallback case. */
902   stmt1 = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), result,
903                                         result, tmp1);
904   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
905   bb3end = stmt1;
906
907   /* Fix CFG. */
908   /* Edge e23 connects bb2 to bb3, etc. */
909   /* However block 3 is optional; if it is not there, references
910      to 3 really refer to block 2. */
911   e12 = split_block (bb, bb1end);
912   bb2 = e12->dest;
913   bb2->count = all - count1;
914     
915   if (ncounts)  /* Assumed to be 0 or 1.  */
916     {
917       e23 = split_block (bb2, bb2end);
918       bb3 = e23->dest;
919       bb3->count = all - count1 - count2;
920     }
921
922   e34 = split_block (ncounts ? bb3 : bb2, bb3end);
923   bb4 = e34->dest;
924   bb4->count = all;
925
926   e12->flags &= ~EDGE_FALLTHRU;
927   e12->flags |= EDGE_FALSE_VALUE;
928   e12->probability = REG_BR_PROB_BASE - prob1;
929   e12->count = all - count1;
930
931   e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
932   e14->probability = prob1;
933   e14->count = count1;
934
935   if (ncounts)  /* Assumed to be 0 or 1.  */
936     {
937       e23->flags &= ~EDGE_FALLTHRU;
938       e23->flags |= EDGE_FALSE_VALUE;
939       e23->count = all - count1 - count2;
940       e23->probability = REG_BR_PROB_BASE - prob2;
941
942       e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
943       e24->probability = prob2;
944       e24->count = count2;
945     }
946
947   e34->probability = REG_BR_PROB_BASE;
948   e34->count = all - count1 - count2;
949
950   return result;
951 }
952
953
954 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable.  */
955
956 static bool
957 gimple_mod_subtract_transform (gimple_stmt_iterator *si)
958 {
959   histogram_value histogram;
960   enum tree_code code;
961   gcov_type count, wrong_values, all;
962   tree lhs_type, result, value;
963   gcov_type prob1, prob2;
964   unsigned int i, steps;
965   gcov_type count1, count2;
966   gimple stmt;
967
968   stmt = gsi_stmt (*si);
969   if (gimple_code (stmt) != GIMPLE_ASSIGN)
970     return false;
971
972   lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
973   if (!INTEGRAL_TYPE_P (lhs_type))
974     return false;
975
976   code = gimple_assign_rhs_code (stmt);
977   
978   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
979     return false;
980
981   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
982   if (!histogram)
983     return false;
984
985   value = histogram->hvalue.value;
986   all = 0;
987   wrong_values = 0;
988   for (i = 0; i < histogram->hdata.intvl.steps; i++)
989     all += histogram->hvalue.counters[i];
990
991   wrong_values += histogram->hvalue.counters[i];
992   wrong_values += histogram->hvalue.counters[i+1];
993   steps = histogram->hdata.intvl.steps;
994   all += wrong_values;
995   count1 = histogram->hvalue.counters[0];
996   count2 = histogram->hvalue.counters[1];
997
998   /* Compute probability of taking the optimal path.  */
999   if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count))
1000     {
1001       gimple_remove_histogram_value (cfun, stmt, histogram);
1002       return false;
1003     }
1004
1005   if (flag_profile_correction && count1 + count2 > all)
1006       all = count1 + count2;
1007
1008   gcc_assert (count1 + count2 <= all);
1009
1010   /* We require that we use just subtractions in at least 50% of all
1011      evaluations.  */
1012   count = 0;
1013   for (i = 0; i < histogram->hdata.intvl.steps; i++)
1014     {
1015       count += histogram->hvalue.counters[i];
1016       if (count * 2 >= all)
1017         break;
1018     }
1019   if (i == steps
1020       || optimize_bb_for_size_p (gimple_bb (stmt)))
1021     return false;
1022
1023   gimple_remove_histogram_value (cfun, stmt, histogram);
1024   if (dump_file)
1025     {
1026       fprintf (dump_file, "Mod subtract transformation on insn ");
1027       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1028     }
1029
1030   /* Compute probability of taking the optimal path(s).  */
1031   if (all > 0)
1032     {
1033       prob1 = (count1 * REG_BR_PROB_BASE + all / 2) / all;
1034       prob2 = (count2 * REG_BR_PROB_BASE + all / 2) / all;
1035     }
1036   else
1037     {
1038       prob1 = prob2 = 0;
1039     }
1040
1041   /* In practice, "steps" is always 2.  This interface reflects this,
1042      and will need to be changed if "steps" can change.  */
1043   result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all);
1044
1045   gimple_assign_set_rhs_from_tree (si, result);
1046
1047   return true;
1048 }
1049
1050 static struct cgraph_node** pid_map = NULL;
1051
1052 /* Initialize map of pids (pid -> cgraph node) */
1053
1054 static void 
1055 init_pid_map (void)
1056 {
1057   struct cgraph_node *n;
1058
1059   if (pid_map != NULL)
1060     return;
1061
1062   pid_map = XCNEWVEC (struct cgraph_node*, cgraph_max_pid);
1063
1064   for (n = cgraph_nodes; n; n = n->next)
1065     {
1066       if (n->pid != -1)
1067         pid_map [n->pid] = n;
1068     }
1069 }
1070
1071 /* Return cgraph node for function with pid */
1072
1073 static inline struct cgraph_node*
1074 find_func_by_pid (int   pid)
1075 {
1076   init_pid_map ();
1077
1078   return pid_map [pid];
1079 }
1080
1081 /* Do transformation
1082
1083   if (actual_callee_address == address_of_most_common_function/method)
1084     do direct call
1085   else
1086     old call
1087  */
1088
1089 static gimple
1090 gimple_ic (gimple icall_stmt, struct cgraph_node *direct_call, 
1091            int prob, gcov_type count, gcov_type all)
1092 {
1093   gimple dcall_stmt, load_stmt, cond_stmt;
1094   tree tmp1, tmpv, tmp;
1095   basic_block cond_bb, dcall_bb, icall_bb, join_bb;
1096   tree optype = build_pointer_type (void_type_node);
1097   edge e_cd, e_ci, e_di, e_dj, e_ij;
1098   gimple_stmt_iterator gsi;
1099   int lp_nr;
1100
1101   cond_bb = gimple_bb (icall_stmt);
1102   gsi = gsi_for_stmt (icall_stmt);
1103
1104   tmpv = create_tmp_var (optype, "PROF");
1105   tmp1 = create_tmp_var (optype, "PROF");
1106   tmp = unshare_expr (gimple_call_fn (icall_stmt));
1107   load_stmt = gimple_build_assign (tmpv, tmp);
1108   gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1109
1110   tmp = fold_convert (optype, build_addr (direct_call->decl, 
1111                                           current_function_decl));
1112   load_stmt = gimple_build_assign (tmp1, tmp);
1113   gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1114
1115   cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE);
1116   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1117
1118   dcall_stmt = gimple_copy (icall_stmt);
1119   gimple_call_set_fndecl (dcall_stmt, direct_call->decl);
1120   gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT);
1121
1122   /* Fix CFG. */
1123   /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1124   e_cd = split_block (cond_bb, cond_stmt);
1125   dcall_bb = e_cd->dest;
1126   dcall_bb->count = count;
1127
1128   e_di = split_block (dcall_bb, dcall_stmt);
1129   icall_bb = e_di->dest;
1130   icall_bb->count = all - count;
1131
1132   e_ij = split_block (icall_bb, icall_stmt);
1133   join_bb = e_ij->dest;
1134   join_bb->count = all;
1135
1136   e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1137   e_cd->probability = prob;
1138   e_cd->count = count;
1139
1140   e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
1141   e_ci->probability = REG_BR_PROB_BASE - prob;
1142   e_ci->count = all - count;
1143
1144   remove_edge (e_di);
1145   
1146   e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
1147   e_dj->probability = REG_BR_PROB_BASE;
1148   e_dj->count = count;
1149
1150   e_ij->probability = REG_BR_PROB_BASE;
1151   e_ij->count = all - count;
1152
1153   /* Fix eh edges */
1154   lp_nr = lookup_stmt_eh_lp (icall_stmt);
1155   if (lp_nr != 0)
1156     {
1157       gimple_purge_dead_eh_edges (join_bb);
1158
1159       if (stmt_could_throw_p (dcall_stmt))
1160         {
1161           add_stmt_to_eh_lp (dcall_stmt, lp_nr);
1162           make_eh_edges (dcall_stmt);
1163         }
1164
1165       gcc_assert (stmt_could_throw_p (icall_stmt));
1166       make_eh_edges (icall_stmt);
1167     }
1168
1169   return dcall_stmt;
1170 }
1171
1172 /*
1173   For every checked indirect/virtual call determine if most common pid of
1174   function/class method has probability more than 50%. If yes modify code of
1175   this call to:
1176  */
1177
1178 static bool
1179 gimple_ic_transform (gimple stmt)
1180 {
1181   histogram_value histogram;
1182   gcov_type val, count, all, bb_all;
1183   gcov_type prob;
1184   tree callee;
1185   gimple modify;
1186   struct cgraph_node *direct_call;
1187   
1188   if (gimple_code (stmt) != GIMPLE_CALL)
1189     return false;
1190
1191   callee = gimple_call_fn (stmt);
1192
1193   if (TREE_CODE (callee) == FUNCTION_DECL)
1194     return false;
1195
1196   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1197   if (!histogram)
1198     return false;
1199
1200   val = histogram->hvalue.counters [0];
1201   count = histogram->hvalue.counters [1];
1202   all = histogram->hvalue.counters [2];
1203   gimple_remove_histogram_value (cfun, stmt, histogram);
1204
1205   if (4 * count <= 3 * all)
1206     return false;
1207
1208   bb_all = gimple_bb (stmt)->count;
1209   /* The order of CHECK_COUNTER calls is important - 
1210      since check_counter can correct the third parameter
1211      and we want to make count <= all <= bb_all. */
1212   if ( check_counter (stmt, "ic", &all, &bb_all, bb_all)
1213       || check_counter (stmt, "ic", &count, &all, all))
1214     return false;
1215
1216   if (all > 0)
1217     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1218   else
1219     prob = 0;
1220   direct_call = find_func_by_pid ((int)val);
1221
1222   if (direct_call == NULL)
1223     return false;
1224
1225   modify = gimple_ic (stmt, direct_call, prob, count, all);
1226
1227   if (dump_file)
1228     {
1229       fprintf (dump_file, "Indirect call -> direct call ");
1230       print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1231       fprintf (dump_file, "=> ");
1232       print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1233       fprintf (dump_file, " transformation on insn ");
1234       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1235       fprintf (dump_file, " to ");
1236       print_gimple_stmt (dump_file, modify, 0, TDF_SLIM);
1237       fprintf (dump_file, "hist->count "HOST_WIDEST_INT_PRINT_DEC
1238                " hist->all "HOST_WIDEST_INT_PRINT_DEC"\n", count, all);
1239     }
1240
1241   return true;
1242 }
1243
1244 /* Return true if the stringop CALL with FNDECL shall be profiled.  */
1245 static bool
1246 interesting_stringop_to_profile_p (tree fndecl, gimple call)
1247 {
1248   enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1249
1250   if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY
1251       && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO)
1252     return false;
1253
1254   switch (fcode)
1255     {
1256      case BUILT_IN_MEMCPY:
1257      case BUILT_IN_MEMPCPY:
1258        return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
1259                                        INTEGER_TYPE, VOID_TYPE);
1260      case BUILT_IN_MEMSET:
1261        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1262                                       INTEGER_TYPE, VOID_TYPE);
1263      case BUILT_IN_BZERO:
1264        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1265                                        VOID_TYPE);
1266      default:
1267        gcc_unreachable ();
1268     }
1269 }
1270
1271 /* Convert   stringop (..., vcall_size)
1272    into 
1273    if (vcall_size == icall_size)
1274      stringop (..., icall_size);
1275    else
1276      stringop (..., vcall_size);
1277    assuming we'll propagate a true constant into ICALL_SIZE later.  */
1278
1279 static void
1280 gimple_stringop_fixed_value (gimple vcall_stmt, tree icall_size, int prob,
1281                              gcov_type count, gcov_type all)
1282 {
1283   gimple tmp_stmt, cond_stmt, icall_stmt;
1284   tree tmp1, tmpv, vcall_size, optype;
1285   basic_block cond_bb, icall_bb, vcall_bb, join_bb;
1286   edge e_ci, e_cv, e_iv, e_ij, e_vj;
1287   gimple_stmt_iterator gsi;
1288
1289   cond_bb = gimple_bb (vcall_stmt);
1290   gsi = gsi_for_stmt (vcall_stmt);
1291
1292   vcall_size = gimple_call_arg (vcall_stmt, 2);
1293   optype = TREE_TYPE (vcall_size);
1294
1295   tmpv = create_tmp_var (optype, "PROF");
1296   tmp1 = create_tmp_var (optype, "PROF");
1297   tmp_stmt = gimple_build_assign (tmpv, fold_convert (optype, icall_size));
1298   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1299
1300   tmp_stmt = gimple_build_assign (tmp1, vcall_size);
1301   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1302
1303   cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmpv, NULL_TREE, NULL_TREE);
1304   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1305
1306   icall_stmt = gimple_copy (vcall_stmt);
1307   gimple_call_set_arg (icall_stmt, 2, icall_size);
1308   gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT);
1309
1310   /* Fix CFG. */
1311   /* Edge e_ci connects cond_bb to icall_bb, etc. */
1312   e_ci = split_block (cond_bb, cond_stmt);
1313   icall_bb = e_ci->dest;
1314   icall_bb->count = count;
1315
1316   e_iv = split_block (icall_bb, icall_stmt);
1317   vcall_bb = e_iv->dest;
1318   vcall_bb->count = all - count;
1319
1320   e_vj = split_block (vcall_bb, vcall_stmt);
1321   join_bb = e_vj->dest;
1322   join_bb->count = all;
1323
1324   e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1325   e_ci->probability = prob;
1326   e_ci->count = count;
1327
1328   e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE);
1329   e_cv->probability = REG_BR_PROB_BASE - prob;
1330   e_cv->count = all - count;
1331
1332   remove_edge (e_iv);
1333   
1334   e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU);
1335   e_ij->probability = REG_BR_PROB_BASE;
1336   e_ij->count = count;
1337
1338   e_vj->probability = REG_BR_PROB_BASE;
1339   e_vj->count = all - count;
1340
1341   /* Because these are all string op builtins, they're all nothrow.  */
1342   gcc_assert (!stmt_could_throw_p (vcall_stmt));
1343   gcc_assert (!stmt_could_throw_p (icall_stmt));
1344 }
1345
1346 /* Find values inside STMT for that we want to measure histograms for
1347    division/modulo optimization.  */
1348 static bool
1349 gimple_stringops_transform (gimple_stmt_iterator *gsi)
1350 {
1351   gimple stmt = gsi_stmt (*gsi);
1352   tree fndecl;
1353   tree blck_size;
1354   enum built_in_function fcode;
1355   histogram_value histogram;
1356   gcov_type count, all, val;
1357   tree value;
1358   tree dest, src;
1359   unsigned int dest_align, src_align;
1360   gcov_type prob;
1361   tree tree_val;
1362
1363   if (gimple_code (stmt) != GIMPLE_CALL)
1364     return false;
1365   fndecl = gimple_call_fndecl (stmt);
1366   if (!fndecl)
1367     return false;
1368   fcode = DECL_FUNCTION_CODE (fndecl);
1369   if (!interesting_stringop_to_profile_p (fndecl, stmt))
1370     return false;
1371
1372   if (fcode == BUILT_IN_BZERO)
1373     blck_size = gimple_call_arg (stmt, 1);
1374   else
1375     blck_size = gimple_call_arg (stmt, 2);
1376   if (TREE_CODE (blck_size) == INTEGER_CST)
1377     return false;
1378
1379   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1380   if (!histogram)
1381     return false;
1382   value = histogram->hvalue.value;
1383   val = histogram->hvalue.counters[0];
1384   count = histogram->hvalue.counters[1];
1385   all = histogram->hvalue.counters[2];
1386   gimple_remove_histogram_value (cfun, stmt, histogram);
1387   /* We require that count is at least half of all; this means
1388      that for the transformation to fire the value must be constant
1389      at least 80% of time.  */
1390   if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1391     return false;
1392   if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1393     return false;
1394   if (all > 0)
1395     prob = (count * REG_BR_PROB_BASE + all / 2) / all;
1396   else
1397     prob = 0;
1398   dest = gimple_call_arg (stmt, 0);
1399   dest_align = get_pointer_alignment (dest, BIGGEST_ALIGNMENT);
1400   switch (fcode)
1401     {
1402     case BUILT_IN_MEMCPY:
1403     case BUILT_IN_MEMPCPY:
1404       src = gimple_call_arg (stmt, 1);
1405       src_align = get_pointer_alignment (src, BIGGEST_ALIGNMENT);
1406       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1407         return false;
1408       break;
1409     case BUILT_IN_MEMSET:
1410       if (!can_store_by_pieces (val, builtin_memset_read_str,
1411                                 gimple_call_arg (stmt, 1),
1412                                 dest_align, true))
1413         return false;
1414       break;
1415     case BUILT_IN_BZERO:
1416       if (!can_store_by_pieces (val, builtin_memset_read_str,
1417                                 integer_zero_node,
1418                                 dest_align, true))
1419         return false;
1420       break;
1421     default:
1422       gcc_unreachable ();
1423     }
1424   tree_val = build_int_cst_wide (get_gcov_type (),
1425                                  (unsigned HOST_WIDE_INT) val,
1426                                  val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1);
1427   if (dump_file)
1428     {
1429       fprintf (dump_file, "Single value %i stringop transformation on ",
1430                (int)val);
1431       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1432     }
1433   gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
1434   
1435   return true;
1436 }
1437
1438 void
1439 stringop_block_profile (gimple stmt, unsigned int *expected_align,
1440                         HOST_WIDE_INT *expected_size)
1441 {
1442   histogram_value histogram;
1443   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1444   if (!histogram)
1445     *expected_size = -1;
1446   else if (!histogram->hvalue.counters[1])
1447     {
1448       *expected_size = -1;
1449       gimple_remove_histogram_value (cfun, stmt, histogram);
1450     }
1451   else
1452     {
1453       gcov_type size;
1454       size = ((histogram->hvalue.counters[0]
1455               + histogram->hvalue.counters[1] / 2)
1456                / histogram->hvalue.counters[1]);
1457       /* Even if we can hold bigger value in SIZE, INT_MAX
1458          is safe "infinity" for code generation strategies.  */
1459       if (size > INT_MAX)
1460         size = INT_MAX;
1461       *expected_size = size;
1462       gimple_remove_histogram_value (cfun, stmt, histogram);
1463     }
1464   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1465   if (!histogram)
1466     *expected_align = 0;
1467   else if (!histogram->hvalue.counters[0])
1468     {
1469       gimple_remove_histogram_value (cfun, stmt, histogram);
1470       *expected_align = 0;
1471     }
1472   else
1473     {
1474       gcov_type count;
1475       int alignment;
1476
1477       count = histogram->hvalue.counters[0];
1478       alignment = 1;
1479       while (!(count & alignment)
1480              && (alignment * 2 * BITS_PER_UNIT))
1481         alignment <<= 1;
1482       *expected_align = alignment * BITS_PER_UNIT;
1483       gimple_remove_histogram_value (cfun, stmt, histogram);
1484     }
1485 }
1486
1487 struct value_prof_hooks {
1488   /* Find list of values for which we want to measure histograms.  */
1489   void (*find_values_to_profile) (histogram_values *);
1490
1491   /* Identify and exploit properties of values that are hard to analyze
1492      statically.  See value-prof.c for more detail.  */
1493   bool (*value_profile_transformations) (void);  
1494 };
1495 \f
1496 /* Find values inside STMT for that we want to measure histograms for
1497    division/modulo optimization.  */
1498 static void
1499 gimple_divmod_values_to_profile (gimple stmt, histogram_values *values)
1500 {
1501   tree lhs, divisor, op0, type;
1502   histogram_value hist;
1503
1504   if (gimple_code (stmt) != GIMPLE_ASSIGN)
1505     return;
1506
1507   lhs = gimple_assign_lhs (stmt);
1508   type = TREE_TYPE (lhs);
1509   if (!INTEGRAL_TYPE_P (type))
1510     return;
1511
1512   switch (gimple_assign_rhs_code (stmt))
1513     {
1514     case TRUNC_DIV_EXPR:
1515     case TRUNC_MOD_EXPR:
1516       divisor = gimple_assign_rhs2 (stmt);
1517       op0 = gimple_assign_rhs1 (stmt);
1518
1519       VEC_reserve (histogram_value, heap, *values, 3);
1520
1521       if (is_gimple_reg (divisor))
1522         /* Check for the case where the divisor is the same value most
1523            of the time.  */
1524         VEC_quick_push (histogram_value, *values,
1525                         gimple_alloc_histogram_value (cfun,
1526                                                       HIST_TYPE_SINGLE_VALUE,
1527                                                       stmt, divisor));
1528
1529       /* For mod, check whether it is not often a noop (or replaceable by
1530          a few subtractions).  */
1531       if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
1532           && TYPE_UNSIGNED (type))
1533         {
1534           tree val;
1535           /* Check for a special case where the divisor is power of 2.  */
1536           VEC_quick_push (histogram_value, *values,
1537                           gimple_alloc_histogram_value (cfun, HIST_TYPE_POW2,
1538                                                         stmt, divisor));
1539
1540           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1541           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
1542                                                stmt, val);
1543           hist->hdata.intvl.int_start = 0;
1544           hist->hdata.intvl.steps = 2;
1545           VEC_quick_push (histogram_value, *values, hist);
1546         }
1547       return;
1548
1549     default:
1550       return;
1551     }
1552 }
1553
1554 /* Find calls inside STMT for that we want to measure histograms for 
1555    indirect/virtual call optimization. */ 
1556
1557 static void
1558 gimple_indirect_call_to_profile (gimple stmt, histogram_values *values)
1559 {
1560   tree callee;
1561
1562   if (gimple_code (stmt) != GIMPLE_CALL
1563       || gimple_call_fndecl (stmt) != NULL_TREE)
1564     return;
1565
1566   callee = gimple_call_fn (stmt);
1567
1568   VEC_reserve (histogram_value, heap, *values, 3);
1569
1570   VEC_quick_push (histogram_value, *values, 
1571                   gimple_alloc_histogram_value (cfun, HIST_TYPE_INDIR_CALL,
1572                                                 stmt, callee));
1573
1574   return;
1575 }
1576
1577 /* Find values inside STMT for that we want to measure histograms for
1578    string operations.  */
1579 static void
1580 gimple_stringops_values_to_profile (gimple stmt, histogram_values *values)
1581 {
1582   tree fndecl;
1583   tree blck_size;
1584   tree dest;
1585   enum built_in_function fcode;
1586
1587   if (gimple_code (stmt) != GIMPLE_CALL)
1588     return;
1589   fndecl = gimple_call_fndecl (stmt);
1590   if (!fndecl)
1591     return;
1592   fcode = DECL_FUNCTION_CODE (fndecl);
1593
1594   if (!interesting_stringop_to_profile_p (fndecl, stmt))
1595     return;
1596
1597   dest = gimple_call_arg (stmt, 0);
1598   if (fcode == BUILT_IN_BZERO)
1599     blck_size = gimple_call_arg (stmt, 1);
1600   else
1601     blck_size = gimple_call_arg (stmt, 2);
1602
1603   if (TREE_CODE (blck_size) != INTEGER_CST)
1604     {
1605       VEC_safe_push (histogram_value, heap, *values,
1606                      gimple_alloc_histogram_value (cfun, HIST_TYPE_SINGLE_VALUE,
1607                                                    stmt, blck_size));
1608       VEC_safe_push (histogram_value, heap, *values,
1609                      gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
1610                                                    stmt, blck_size));
1611     }
1612   if (TREE_CODE (blck_size) != INTEGER_CST)
1613     VEC_safe_push (histogram_value, heap, *values,
1614                    gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
1615                                                  stmt, dest));
1616 }
1617
1618 /* Find values inside STMT for that we want to measure histograms and adds
1619    them to list VALUES.  */
1620
1621 static void
1622 gimple_values_to_profile (gimple stmt, histogram_values *values)
1623 {
1624   if (flag_value_profile_transformations)
1625     {
1626       gimple_divmod_values_to_profile (stmt, values);
1627       gimple_stringops_values_to_profile (stmt, values);
1628       gimple_indirect_call_to_profile (stmt, values);
1629     }
1630 }
1631
1632 static void
1633 gimple_find_values_to_profile (histogram_values *values)
1634 {
1635   basic_block bb;
1636   gimple_stmt_iterator gsi;
1637   unsigned i;
1638   histogram_value hist = NULL;
1639
1640   *values = NULL;
1641   FOR_EACH_BB (bb)
1642     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1643       gimple_values_to_profile (gsi_stmt (gsi), values);
1644   
1645   for (i = 0; VEC_iterate (histogram_value, *values, i, hist); i++)
1646     {
1647       switch (hist->type)
1648         {
1649         case HIST_TYPE_INTERVAL:
1650           hist->n_counters = hist->hdata.intvl.steps + 2;
1651           break;
1652
1653         case HIST_TYPE_POW2:
1654           hist->n_counters = 2;
1655           break;
1656
1657         case HIST_TYPE_SINGLE_VALUE:
1658           hist->n_counters = 3;
1659           break;
1660
1661         case HIST_TYPE_CONST_DELTA:
1662           hist->n_counters = 4;
1663           break;
1664
1665         case HIST_TYPE_INDIR_CALL:
1666           hist->n_counters = 3;
1667           break;
1668
1669         case HIST_TYPE_AVERAGE:
1670           hist->n_counters = 2;
1671           break;
1672
1673         case HIST_TYPE_IOR:
1674           hist->n_counters = 1;
1675           break;
1676
1677         default:
1678           gcc_unreachable ();
1679         }
1680       if (dump_file)
1681         {
1682           fprintf (dump_file, "Stmt ");
1683           print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
1684           dump_histogram_value (dump_file, hist);
1685         }
1686     }
1687 }
1688
1689 static struct value_prof_hooks gimple_value_prof_hooks = {
1690   gimple_find_values_to_profile,
1691   gimple_value_profile_transformations
1692 };
1693
1694 void
1695 gimple_register_value_prof_hooks (void)
1696 {
1697   gcc_assert (current_ir_type () == IR_GIMPLE);
1698   value_prof_hooks = &gimple_value_prof_hooks;
1699 }
1700 \f
1701 /* IR-independent entry points.  */
1702 void
1703 find_values_to_profile (histogram_values *values)
1704 {
1705   (value_prof_hooks->find_values_to_profile) (values);
1706 }
1707
1708 bool
1709 value_profile_transformations (void)
1710 {
1711   return (value_prof_hooks->value_profile_transformations) ();
1712 }
1713 \f