Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / value-prof.c
1 /* Transformations based on profile information for values.
2    Copyright (C) 2003-2015 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>.  */
19
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "hash-set.h"
25 #include "machmode.h"
26 #include "vec.h"
27 #include "double-int.h"
28 #include "input.h"
29 #include "alias.h"
30 #include "symtab.h"
31 #include "wide-int.h"
32 #include "inchash.h"
33 #include "tree.h"
34 #include "fold-const.h"
35 #include "tree-nested.h"
36 #include "calls.h"
37 #include "rtl.h"
38 #include "hashtab.h"
39 #include "hard-reg-set.h"
40 #include "function.h"
41 #include "flags.h"
42 #include "statistics.h"
43 #include "real.h"
44 #include "fixed-value.h"
45 #include "insn-config.h"
46 #include "expmed.h"
47 #include "dojump.h"
48 #include "explow.h"
49 #include "emit-rtl.h"
50 #include "varasm.h"
51 #include "stmt.h"
52 #include "expr.h"
53 #include "predict.h"
54 #include "dominance.h"
55 #include "cfg.h"
56 #include "basic-block.h"
57 #include "value-prof.h"
58 #include "recog.h"
59 #include "insn-codes.h"
60 #include "optabs.h"
61 #include "regs.h"
62 #include "tree-ssa-alias.h"
63 #include "internal-fn.h"
64 #include "tree-eh.h"
65 #include "gimple-expr.h"
66 #include "is-a.h"
67 #include "gimple.h"
68 #include "gimplify.h"
69 #include "gimple-iterator.h"
70 #include "gimple-ssa.h"
71 #include "tree-cfg.h"
72 #include "tree-phinodes.h"
73 #include "ssa-iterators.h"
74 #include "stringpool.h"
75 #include "tree-ssanames.h"
76 #include "diagnostic.h"
77 #include "gimple-pretty-print.h"
78 #include "coverage.h"
79 #include "gcov-io.h"
80 #include "timevar.h"
81 #include "dumpfile.h"
82 #include "profile.h"
83 #include "hash-map.h"
84 #include "plugin-api.h"
85 #include "ipa-ref.h"
86 #include "cgraph.h"
87 #include "data-streamer.h"
88 #include "builtins.h"
89 #include "params.h"
90 #include "tree-chkp.h"
91
92 /* In this file value profile based optimizations are placed.  Currently the
93    following optimizations are implemented (for more detailed descriptions
94    see comments at value_profile_transformations):
95
96    1) Division/modulo specialization.  Provided that we can determine that the
97       operands of the division have some special properties, we may use it to
98       produce more effective code.
99
100    2) Indirect/virtual call specialization. If we can determine most
101       common function callee in indirect/virtual call. We can use this
102       information to improve code effectiveness (especially info for
103       the inliner).
104
105    3) Speculative prefetching.  If we are able to determine that the difference
106       between addresses accessed by a memory reference is usually constant, we
107       may add the prefetch instructions.
108       FIXME: This transformation was removed together with RTL based value
109       profiling.
110
111
112    Value profiling internals
113    ==========================
114
115    Every value profiling transformation starts with defining what values
116    to profile.  There are different histogram types (see HIST_TYPE_* in
117    value-prof.h) and each transformation can request one or more histogram
118    types per GIMPLE statement.  The function gimple_find_values_to_profile()
119    collects the values to profile in a vec, and adds the number of counters
120    required for the different histogram types.
121
122    For a -fprofile-generate run, the statements for which values should be
123    recorded, are instrumented in instrument_values().  The instrumentation
124    is done by helper functions that can be found in tree-profile.c, where
125    new types of histograms can be added if necessary.
126
127    After a -fprofile-use, the value profiling data is read back in by
128    compute_value_histograms() that translates the collected data to
129    histograms and attaches them to the profiled statements via
130    gimple_add_histogram_value().  Histograms are stored in a hash table
131    that is attached to every intrumented function, see VALUE_HISTOGRAMS
132    in function.h.
133    
134    The value-profile transformations driver is the function
135    gimple_value_profile_transformations().  It traverses all statements in
136    the to-be-transformed function, and looks for statements with one or
137    more histograms attached to it.  If a statement has histograms, the
138    transformation functions are called on the statement.
139
140    Limitations / FIXME / TODO:
141    * Only one histogram of each type can be associated with a statement.
142    * Currently, HIST_TYPE_CONST_DELTA is not implemented.
143      (This type of histogram was originally used to implement a form of
144      stride profiling based speculative prefetching to improve SPEC2000
145      scores for memory-bound benchmarks, mcf and equake.  However, this
146      was an RTL value-profiling transformation, and those have all been
147      removed.)
148    * Some value profile transformations are done in builtins.c (?!)
149    * Updating of histograms needs some TLC.
150    * The value profiling code could be used to record analysis results
151      from non-profiling (e.g. VRP).
152    * Adding new profilers should be simplified, starting with a cleanup
153      of what-happens-where andwith making gimple_find_values_to_profile
154      and gimple_value_profile_transformations table-driven, perhaps...
155 */
156
157 static tree gimple_divmod_fixed_value (gassign *, tree, int, gcov_type,
158                                        gcov_type);
159 static tree gimple_mod_pow2 (gassign *, int, gcov_type, gcov_type);
160 static tree gimple_mod_subtract (gassign *, int, int, int, gcov_type,
161                                  gcov_type, gcov_type);
162 static bool gimple_divmod_fixed_value_transform (gimple_stmt_iterator *);
163 static bool gimple_mod_pow2_value_transform (gimple_stmt_iterator *);
164 static bool gimple_mod_subtract_transform (gimple_stmt_iterator *);
165 static bool gimple_stringops_transform (gimple_stmt_iterator *);
166 static bool gimple_ic_transform (gimple_stmt_iterator *);
167
168 /* Allocate histogram value.  */
169
170 histogram_value
171 gimple_alloc_histogram_value (struct function *fun ATTRIBUTE_UNUSED,
172                               enum hist_type type, gimple stmt, tree value)
173 {
174    histogram_value hist = (histogram_value) xcalloc (1, sizeof (*hist));
175    hist->hvalue.value = value;
176    hist->hvalue.stmt = stmt;
177    hist->type = type;
178    return hist;
179 }
180
181 /* Hash value for histogram.  */
182
183 static hashval_t
184 histogram_hash (const void *x)
185 {
186   return htab_hash_pointer (((const_histogram_value)x)->hvalue.stmt);
187 }
188
189 /* Return nonzero if statement for histogram_value X is Y.  */
190
191 static int
192 histogram_eq (const void *x, const void *y)
193 {
194   return ((const_histogram_value) x)->hvalue.stmt == (const_gimple) y;
195 }
196
197 /* Set histogram for STMT.  */
198
199 static void
200 set_histogram_value (struct function *fun, gimple stmt, histogram_value hist)
201 {
202   void **loc;
203   if (!hist && !VALUE_HISTOGRAMS (fun))
204     return;
205   if (!VALUE_HISTOGRAMS (fun))
206     VALUE_HISTOGRAMS (fun) = htab_create (1, histogram_hash,
207                                            histogram_eq, NULL);
208   loc = htab_find_slot_with_hash (VALUE_HISTOGRAMS (fun), stmt,
209                                   htab_hash_pointer (stmt),
210                                   hist ? INSERT : NO_INSERT);
211   if (!hist)
212     {
213       if (loc)
214         htab_clear_slot (VALUE_HISTOGRAMS (fun), loc);
215       return;
216     }
217   *loc = hist;
218 }
219
220 /* Get histogram list for STMT.  */
221
222 histogram_value
223 gimple_histogram_value (struct function *fun, gimple stmt)
224 {
225   if (!VALUE_HISTOGRAMS (fun))
226     return NULL;
227   return (histogram_value) htab_find_with_hash (VALUE_HISTOGRAMS (fun), stmt,
228                                                 htab_hash_pointer (stmt));
229 }
230
231 /* Add histogram for STMT.  */
232
233 void
234 gimple_add_histogram_value (struct function *fun, gimple stmt,
235                             histogram_value hist)
236 {
237   hist->hvalue.next = gimple_histogram_value (fun, stmt);
238   set_histogram_value (fun, stmt, hist);
239   hist->fun = fun;
240 }
241
242
243 /* Remove histogram HIST from STMT's histogram list.  */
244
245 void
246 gimple_remove_histogram_value (struct function *fun, gimple stmt,
247                                histogram_value hist)
248 {
249   histogram_value hist2 = gimple_histogram_value (fun, stmt);
250   if (hist == hist2)
251     {
252       set_histogram_value (fun, stmt, hist->hvalue.next);
253     }
254   else
255     {
256       while (hist2->hvalue.next != hist)
257         hist2 = hist2->hvalue.next;
258       hist2->hvalue.next = hist->hvalue.next;
259     }
260   free (hist->hvalue.counters);
261 #ifdef ENABLE_CHECKING
262   memset (hist, 0xab, sizeof (*hist));
263 #endif
264   free (hist);
265 }
266
267
268 /* Lookup histogram of type TYPE in the STMT.  */
269
270 histogram_value
271 gimple_histogram_value_of_type (struct function *fun, gimple stmt,
272                                 enum hist_type type)
273 {
274   histogram_value hist;
275   for (hist = gimple_histogram_value (fun, stmt); hist;
276        hist = hist->hvalue.next)
277     if (hist->type == type)
278       return hist;
279   return NULL;
280 }
281
282 /* Dump information about HIST to DUMP_FILE.  */
283
284 static void
285 dump_histogram_value (FILE *dump_file, histogram_value hist)
286 {
287   switch (hist->type)
288     {
289     case HIST_TYPE_INTERVAL:
290       fprintf (dump_file, "Interval counter range %d -- %d",
291                hist->hdata.intvl.int_start,
292                (hist->hdata.intvl.int_start
293                 + hist->hdata.intvl.steps - 1));
294       if (hist->hvalue.counters)
295         {
296            unsigned int i;
297            fprintf (dump_file, " [");
298            for (i = 0; i < hist->hdata.intvl.steps; i++)
299              fprintf (dump_file, " %d:%"PRId64,
300                       hist->hdata.intvl.int_start + i,
301                       (int64_t) hist->hvalue.counters[i]);
302            fprintf (dump_file, " ] outside range:%"PRId64,
303                     (int64_t) hist->hvalue.counters[i]);
304         }
305       fprintf (dump_file, ".\n");
306       break;
307
308     case HIST_TYPE_POW2:
309       fprintf (dump_file, "Pow2 counter ");
310       if (hist->hvalue.counters)
311         {
312            fprintf (dump_file, "pow2:%"PRId64
313                     " nonpow2:%"PRId64,
314                     (int64_t) hist->hvalue.counters[0],
315                     (int64_t) hist->hvalue.counters[1]);
316         }
317       fprintf (dump_file, ".\n");
318       break;
319
320     case HIST_TYPE_SINGLE_VALUE:
321       fprintf (dump_file, "Single value ");
322       if (hist->hvalue.counters)
323         {
324            fprintf (dump_file, "value:%"PRId64
325                     " match:%"PRId64
326                     " wrong:%"PRId64,
327                     (int64_t) hist->hvalue.counters[0],
328                     (int64_t) hist->hvalue.counters[1],
329                     (int64_t) hist->hvalue.counters[2]);
330         }
331       fprintf (dump_file, ".\n");
332       break;
333
334     case HIST_TYPE_AVERAGE:
335       fprintf (dump_file, "Average value ");
336       if (hist->hvalue.counters)
337         {
338            fprintf (dump_file, "sum:%"PRId64
339                     " times:%"PRId64,
340                     (int64_t) hist->hvalue.counters[0],
341                     (int64_t) hist->hvalue.counters[1]);
342         }
343       fprintf (dump_file, ".\n");
344       break;
345
346     case HIST_TYPE_IOR:
347       fprintf (dump_file, "IOR value ");
348       if (hist->hvalue.counters)
349         {
350            fprintf (dump_file, "ior:%"PRId64,
351                     (int64_t) hist->hvalue.counters[0]);
352         }
353       fprintf (dump_file, ".\n");
354       break;
355
356     case HIST_TYPE_CONST_DELTA:
357       fprintf (dump_file, "Constant delta ");
358       if (hist->hvalue.counters)
359         {
360            fprintf (dump_file, "value:%"PRId64
361                     " match:%"PRId64
362                     " wrong:%"PRId64,
363                     (int64_t) hist->hvalue.counters[0],
364                     (int64_t) hist->hvalue.counters[1],
365                     (int64_t) hist->hvalue.counters[2]);
366         }
367       fprintf (dump_file, ".\n");
368       break;
369     case HIST_TYPE_INDIR_CALL:
370       fprintf (dump_file, "Indirect call ");
371       if (hist->hvalue.counters)
372         {
373            fprintf (dump_file, "value:%"PRId64
374                     " match:%"PRId64
375                     " all:%"PRId64,
376                     (int64_t) hist->hvalue.counters[0],
377                     (int64_t) hist->hvalue.counters[1],
378                     (int64_t) hist->hvalue.counters[2]);
379         }
380       fprintf (dump_file, ".\n");
381       break;
382     case HIST_TYPE_TIME_PROFILE:
383       fprintf (dump_file, "Time profile ");
384       if (hist->hvalue.counters)
385       {
386         fprintf (dump_file, "time:%"PRId64,
387                  (int64_t) hist->hvalue.counters[0]);
388       }
389       fprintf (dump_file, ".\n");
390       break;
391     case HIST_TYPE_INDIR_CALL_TOPN:
392       fprintf (dump_file, "Indirect call topn ");
393       if (hist->hvalue.counters)
394         {
395            int i;
396
397            fprintf (dump_file, "accu:%"PRId64, hist->hvalue.counters[0]);
398            for (i = 1; i < (GCOV_ICALL_TOPN_VAL << 2); i += 2)
399              {
400                fprintf (dump_file, " target:%"PRId64 " value:%"PRId64,
401                        (int64_t) hist->hvalue.counters[i],
402                        (int64_t) hist->hvalue.counters[i+1]);
403              }
404         }
405       fprintf (dump_file, ".\n");
406       break;
407     case HIST_TYPE_MAX:
408       gcc_unreachable ();
409    }
410 }
411
412 /* Dump information about HIST to DUMP_FILE.  */
413
414 void
415 stream_out_histogram_value (struct output_block *ob, histogram_value hist)
416 {
417   struct bitpack_d bp;
418   unsigned int i;
419
420   bp = bitpack_create (ob->main_stream);
421   bp_pack_enum (&bp, hist_type, HIST_TYPE_MAX, hist->type);
422   bp_pack_value (&bp, hist->hvalue.next != NULL, 1);
423   streamer_write_bitpack (&bp);
424   switch (hist->type)
425     {
426     case HIST_TYPE_INTERVAL:
427       streamer_write_hwi (ob, hist->hdata.intvl.int_start);
428       streamer_write_uhwi (ob, hist->hdata.intvl.steps);
429       break;
430     default:
431       break;
432     }
433   for (i = 0; i < hist->n_counters; i++)
434     streamer_write_gcov_count (ob, hist->hvalue.counters[i]);
435   if (hist->hvalue.next)
436     stream_out_histogram_value (ob, hist->hvalue.next);
437 }
438 /* Dump information about HIST to DUMP_FILE.  */
439
440 void
441 stream_in_histogram_value (struct lto_input_block *ib, gimple stmt)
442 {
443   enum hist_type type;
444   unsigned int ncounters = 0;
445   struct bitpack_d bp;
446   unsigned int i;
447   histogram_value new_val;
448   bool next;
449   histogram_value *next_p = NULL;
450
451   do
452     {
453       bp = streamer_read_bitpack (ib);
454       type = bp_unpack_enum (&bp, hist_type, HIST_TYPE_MAX);
455       next = bp_unpack_value (&bp, 1);
456       new_val = gimple_alloc_histogram_value (cfun, type, stmt, NULL);
457       switch (type)
458         {
459         case HIST_TYPE_INTERVAL:
460           new_val->hdata.intvl.int_start = streamer_read_hwi (ib);
461           new_val->hdata.intvl.steps = streamer_read_uhwi (ib);
462           ncounters = new_val->hdata.intvl.steps + 2;
463           break;
464
465         case HIST_TYPE_POW2:
466         case HIST_TYPE_AVERAGE:
467           ncounters = 2;
468           break;
469
470         case HIST_TYPE_SINGLE_VALUE:
471         case HIST_TYPE_INDIR_CALL:
472           ncounters = 3;
473           break;
474
475         case HIST_TYPE_CONST_DELTA:
476           ncounters = 4;
477           break;
478
479         case HIST_TYPE_IOR:
480         case HIST_TYPE_TIME_PROFILE:
481           ncounters = 1;
482           break;
483
484         case HIST_TYPE_INDIR_CALL_TOPN:
485           ncounters = (GCOV_ICALL_TOPN_VAL << 2) + 1;
486           break;
487
488         case HIST_TYPE_MAX:
489           gcc_unreachable ();
490         }
491       new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * ncounters);
492       new_val->n_counters = ncounters;
493       for (i = 0; i < ncounters; i++)
494         new_val->hvalue.counters[i] = streamer_read_gcov_count (ib);
495       if (!next_p)
496         gimple_add_histogram_value (cfun, stmt, new_val);
497       else
498         *next_p = new_val;
499       next_p = &new_val->hvalue.next;
500     }
501   while (next);
502 }
503
504 /* Dump all histograms attached to STMT to DUMP_FILE.  */
505
506 void
507 dump_histograms_for_stmt (struct function *fun, FILE *dump_file, gimple stmt)
508 {
509   histogram_value hist;
510   for (hist = gimple_histogram_value (fun, stmt); hist; hist = hist->hvalue.next)
511     dump_histogram_value (dump_file, hist);
512 }
513
514 /* Remove all histograms associated with STMT.  */
515
516 void
517 gimple_remove_stmt_histograms (struct function *fun, gimple stmt)
518 {
519   histogram_value val;
520   while ((val = gimple_histogram_value (fun, stmt)) != NULL)
521     gimple_remove_histogram_value (fun, stmt, val);
522 }
523
524 /* Duplicate all histograms associates with OSTMT to STMT.  */
525
526 void
527 gimple_duplicate_stmt_histograms (struct function *fun, gimple stmt,
528                                   struct function *ofun, gimple ostmt)
529 {
530   histogram_value val;
531   for (val = gimple_histogram_value (ofun, ostmt); val != NULL; val = val->hvalue.next)
532     {
533       histogram_value new_val = gimple_alloc_histogram_value (fun, val->type, NULL, NULL);
534       memcpy (new_val, val, sizeof (*val));
535       new_val->hvalue.stmt = stmt;
536       new_val->hvalue.counters = XNEWVAR (gcov_type, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
537       memcpy (new_val->hvalue.counters, val->hvalue.counters, sizeof (*new_val->hvalue.counters) * new_val->n_counters);
538       gimple_add_histogram_value (fun, stmt, new_val);
539     }
540 }
541
542
543 /* Move all histograms associated with OSTMT to STMT.  */
544
545 void
546 gimple_move_stmt_histograms (struct function *fun, gimple stmt, gimple ostmt)
547 {
548   histogram_value val = gimple_histogram_value (fun, ostmt);
549   if (val)
550     {
551       /* The following three statements can't be reordered,
552          because histogram hashtab relies on stmt field value
553          for finding the exact slot. */
554       set_histogram_value (fun, ostmt, NULL);
555       for (; val != NULL; val = val->hvalue.next)
556         val->hvalue.stmt = stmt;
557       set_histogram_value (fun, stmt, val);
558     }
559 }
560
561 static bool error_found = false;
562
563 /* Helper function for verify_histograms.  For each histogram reachable via htab
564    walk verify that it was reached via statement walk.  */
565
566 static int
567 visit_hist (void **slot, void *data)
568 {
569   hash_set<histogram_value> *visited = (hash_set<histogram_value> *) data;
570   histogram_value hist = *(histogram_value *) slot;
571
572   if (!visited->contains (hist)
573       && hist->type != HIST_TYPE_TIME_PROFILE)
574     {
575       error ("dead histogram");
576       dump_histogram_value (stderr, hist);
577       debug_gimple_stmt (hist->hvalue.stmt);
578       error_found = true;
579     }
580   return 1;
581 }
582
583
584 /* Verify sanity of the histograms.  */
585
586 DEBUG_FUNCTION void
587 verify_histograms (void)
588 {
589   basic_block bb;
590   gimple_stmt_iterator gsi;
591   histogram_value hist;
592
593   error_found = false;
594   hash_set<histogram_value> visited_hists;
595   FOR_EACH_BB_FN (bb, cfun)
596     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
597       {
598         gimple stmt = gsi_stmt (gsi);
599
600         for (hist = gimple_histogram_value (cfun, stmt); hist;
601              hist = hist->hvalue.next)
602           {
603             if (hist->hvalue.stmt != stmt)
604               {
605                 error ("Histogram value statement does not correspond to "
606                        "the statement it is associated with");
607                 debug_gimple_stmt (stmt);
608                 dump_histogram_value (stderr, hist);
609                 error_found = true;
610               }
611             visited_hists.add (hist);
612           }
613       }
614   if (VALUE_HISTOGRAMS (cfun))
615     htab_traverse (VALUE_HISTOGRAMS (cfun), visit_hist, &visited_hists);
616   if (error_found)
617     internal_error ("verify_histograms failed");
618 }
619
620 /* Helper function for verify_histograms.  For each histogram reachable via htab
621    walk verify that it was reached via statement walk.  */
622
623 static int
624 free_hist (void **slot, void *data ATTRIBUTE_UNUSED)
625 {
626   histogram_value hist = *(histogram_value *) slot;
627   free (hist->hvalue.counters);
628 #ifdef ENABLE_CHECKING
629   memset (hist, 0xab, sizeof (*hist));
630 #endif
631   free (hist);
632   return 1;
633 }
634
635 void
636 free_histograms (void)
637 {
638   if (VALUE_HISTOGRAMS (cfun))
639     {
640       htab_traverse (VALUE_HISTOGRAMS (cfun), free_hist, NULL);
641       htab_delete (VALUE_HISTOGRAMS (cfun));
642       VALUE_HISTOGRAMS (cfun) = NULL;
643     }
644 }
645
646
647 /* The overall number of invocations of the counter should match
648    execution count of basic block.  Report it as error rather than
649    internal error as it might mean that user has misused the profile
650    somehow.  */
651
652 static bool
653 check_counter (gimple stmt, const char * name,
654                gcov_type *count, gcov_type *all, gcov_type bb_count)
655 {
656   if (*all != bb_count || *count > *all)
657     {
658       location_t locus;
659       locus = (stmt != NULL)
660               ? gimple_location (stmt)
661               : DECL_SOURCE_LOCATION (current_function_decl);
662       if (flag_profile_correction)
663         {
664           if (dump_enabled_p ())
665             dump_printf_loc (MSG_MISSED_OPTIMIZATION, locus,
666                              "correcting inconsistent value profile: %s "
667                              "profiler overall count (%d) does not match BB "
668                              "count (%d)\n", name, (int)*all, (int)bb_count);
669           *all = bb_count;
670           if (*count > *all)
671             *count = *all;
672           return false;
673         }
674       else
675         {
676           error_at (locus, "corrupted value profile: %s "
677                     "profile counter (%d out of %d) inconsistent with "
678                     "basic-block count (%d)",
679                     name,
680                     (int) *count,
681                     (int) *all,
682                     (int) bb_count);
683           return true;
684         }
685     }
686
687   return false;
688 }
689
690
691 /* GIMPLE based transformations. */
692
693 bool
694 gimple_value_profile_transformations (void)
695 {
696   basic_block bb;
697   gimple_stmt_iterator gsi;
698   bool changed = false;
699
700   FOR_EACH_BB_FN (bb, cfun)
701     {
702       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
703         {
704           gimple stmt = gsi_stmt (gsi);
705           histogram_value th = gimple_histogram_value (cfun, stmt);
706           if (!th)
707             continue;
708
709           if (dump_file)
710             {
711               fprintf (dump_file, "Trying transformations on stmt ");
712               print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
713               dump_histograms_for_stmt (cfun, dump_file, stmt);
714             }
715
716           /* Transformations:  */
717           /* The order of things in this conditional controls which
718              transformation is used when more than one is applicable.  */
719           /* It is expected that any code added by the transformations
720              will be added before the current statement, and that the
721              current statement remain valid (although possibly
722              modified) upon return.  */
723           if (gimple_mod_subtract_transform (&gsi)
724               || gimple_divmod_fixed_value_transform (&gsi)
725               || gimple_mod_pow2_value_transform (&gsi)
726               || gimple_stringops_transform (&gsi)
727               || gimple_ic_transform (&gsi))
728             {
729               stmt = gsi_stmt (gsi);
730               changed = true;
731               /* Original statement may no longer be in the same block. */
732               if (bb != gimple_bb (stmt))
733                 {
734                   bb = gimple_bb (stmt);
735                   gsi = gsi_for_stmt (stmt);
736                 }
737             }
738         }
739     }
740
741   if (changed)
742     {
743       counts_to_freqs ();
744     }
745
746   return changed;
747 }
748
749
750 /* Generate code for transformation 1 (with parent gimple assignment
751    STMT and probability of taking the optimal path PROB, which is
752    equivalent to COUNT/ALL within roundoff error).  This generates the
753    result into a temp and returns the temp; it does not replace or
754    alter the original STMT.  */
755
756 static tree
757 gimple_divmod_fixed_value (gassign *stmt, tree value, int prob,
758                            gcov_type count, gcov_type all)
759 {
760   gassign *stmt1, *stmt2;
761   gcond *stmt3;
762   tree tmp0, tmp1, tmp2;
763   gimple bb1end, bb2end, bb3end;
764   basic_block bb, bb2, bb3, bb4;
765   tree optype, op1, op2;
766   edge e12, e13, e23, e24, e34;
767   gimple_stmt_iterator gsi;
768
769   gcc_assert (is_gimple_assign (stmt)
770               && (gimple_assign_rhs_code (stmt) == TRUNC_DIV_EXPR
771                   || gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR));
772
773   optype = TREE_TYPE (gimple_assign_lhs (stmt));
774   op1 = gimple_assign_rhs1 (stmt);
775   op2 = gimple_assign_rhs2 (stmt);
776
777   bb = gimple_bb (stmt);
778   gsi = gsi_for_stmt (stmt);
779
780   tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
781   tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
782   stmt1 = gimple_build_assign (tmp0, fold_convert (optype, value));
783   stmt2 = gimple_build_assign (tmp1, op2);
784   stmt3 = gimple_build_cond (NE_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
785   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
786   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
787   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
788   bb1end = stmt3;
789
790   tmp2 = create_tmp_reg (optype, "PROF");
791   stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (stmt), op1, tmp0);
792   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
793   bb2end = stmt1;
794
795   stmt1 = gimple_build_assign (tmp2, gimple_assign_rhs_code (stmt), op1, op2);
796   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
797   bb3end = stmt1;
798
799   /* Fix CFG. */
800   /* Edge e23 connects bb2 to bb3, etc. */
801   e12 = split_block (bb, bb1end);
802   bb2 = e12->dest;
803   bb2->count = count;
804   e23 = split_block (bb2, bb2end);
805   bb3 = e23->dest;
806   bb3->count = all - count;
807   e34 = split_block (bb3, bb3end);
808   bb4 = e34->dest;
809   bb4->count = all;
810
811   e12->flags &= ~EDGE_FALLTHRU;
812   e12->flags |= EDGE_FALSE_VALUE;
813   e12->probability = prob;
814   e12->count = count;
815
816   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
817   e13->probability = REG_BR_PROB_BASE - prob;
818   e13->count = all - count;
819
820   remove_edge (e23);
821
822   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
823   e24->probability = REG_BR_PROB_BASE;
824   e24->count = count;
825
826   e34->probability = REG_BR_PROB_BASE;
827   e34->count = all - count;
828
829   return tmp2;
830 }
831
832
833 /* Do transform 1) on INSN if applicable.  */
834
835 static bool
836 gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si)
837 {
838   histogram_value histogram;
839   enum tree_code code;
840   gcov_type val, count, all;
841   tree result, value, tree_val;
842   gcov_type prob;
843   gassign *stmt;
844
845   stmt = dyn_cast <gassign *> (gsi_stmt (*si));
846   if (!stmt)
847     return false;
848
849   if (!INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt))))
850     return false;
851
852   code = gimple_assign_rhs_code (stmt);
853
854   if (code != TRUNC_DIV_EXPR && code != TRUNC_MOD_EXPR)
855     return false;
856
857   histogram = gimple_histogram_value_of_type (cfun, stmt,
858                                               HIST_TYPE_SINGLE_VALUE);
859   if (!histogram)
860     return false;
861
862   value = histogram->hvalue.value;
863   val = histogram->hvalue.counters[0];
864   count = histogram->hvalue.counters[1];
865   all = histogram->hvalue.counters[2];
866   gimple_remove_histogram_value (cfun, stmt, histogram);
867
868   /* We require that count is at least half of all; this means
869      that for the transformation to fire the value must be constant
870      at least 50% of time (and 75% gives the guarantee of usage).  */
871   if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
872       || 2 * count < all
873       || optimize_bb_for_size_p (gimple_bb (stmt)))
874     return false;
875
876   if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
877     return false;
878
879   /* Compute probability of taking the optimal path.  */
880   if (all > 0)
881     prob = GCOV_COMPUTE_SCALE (count, all);
882   else
883     prob = 0;
884
885   if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
886     tree_val = build_int_cst (get_gcov_type (), val);
887   else
888     {
889       HOST_WIDE_INT a[2];
890       a[0] = (unsigned HOST_WIDE_INT) val;
891       a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
892
893       tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
894         TYPE_PRECISION (get_gcov_type ()), false));
895     }
896   result = gimple_divmod_fixed_value (stmt, tree_val, prob, count, all);
897
898   if (dump_file)
899     {
900       fprintf (dump_file, "Div/mod by constant ");
901       print_generic_expr (dump_file, value, TDF_SLIM);
902       fprintf (dump_file, "=");
903       print_generic_expr (dump_file, tree_val, TDF_SLIM);
904       fprintf (dump_file, " transformation on insn ");
905       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
906     }
907
908   gimple_assign_set_rhs_from_tree (si, result);
909   update_stmt (gsi_stmt (*si));
910
911   return true;
912 }
913
914 /* Generate code for transformation 2 (with parent gimple assign STMT and
915    probability of taking the optimal path PROB, which is equivalent to COUNT/ALL
916    within roundoff error).  This generates the result into a temp and returns
917    the temp; it does not replace or alter the original STMT.  */
918 static tree
919 gimple_mod_pow2 (gassign *stmt, int prob, gcov_type count, gcov_type all)
920 {
921   gassign *stmt1, *stmt2, *stmt3;
922   gcond *stmt4;
923   tree tmp2, tmp3;
924   gimple bb1end, bb2end, bb3end;
925   basic_block bb, bb2, bb3, bb4;
926   tree optype, op1, op2;
927   edge e12, e13, e23, e24, e34;
928   gimple_stmt_iterator gsi;
929   tree result;
930
931   gcc_assert (is_gimple_assign (stmt)
932               && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
933
934   optype = TREE_TYPE (gimple_assign_lhs (stmt));
935   op1 = gimple_assign_rhs1 (stmt);
936   op2 = gimple_assign_rhs2 (stmt);
937
938   bb = gimple_bb (stmt);
939   gsi = gsi_for_stmt (stmt);
940
941   result = create_tmp_reg (optype, "PROF");
942   tmp2 = make_temp_ssa_name (optype, NULL, "PROF");
943   tmp3 = make_temp_ssa_name (optype, NULL, "PROF");
944   stmt2 = gimple_build_assign (tmp2, PLUS_EXPR, op2,
945                                build_int_cst (optype, -1));
946   stmt3 = gimple_build_assign (tmp3, BIT_AND_EXPR, tmp2, op2);
947   stmt4 = gimple_build_cond (NE_EXPR, tmp3, build_int_cst (optype, 0),
948                              NULL_TREE, NULL_TREE);
949   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
950   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
951   gsi_insert_before (&gsi, stmt4, GSI_SAME_STMT);
952   bb1end = stmt4;
953
954   /* tmp2 == op2-1 inherited from previous block.  */
955   stmt1 = gimple_build_assign (result, BIT_AND_EXPR, op1, tmp2);
956   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
957   bb2end = stmt1;
958
959   stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (stmt),
960                                op1, op2);
961   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
962   bb3end = stmt1;
963
964   /* Fix CFG. */
965   /* Edge e23 connects bb2 to bb3, etc. */
966   e12 = split_block (bb, bb1end);
967   bb2 = e12->dest;
968   bb2->count = count;
969   e23 = split_block (bb2, bb2end);
970   bb3 = e23->dest;
971   bb3->count = all - count;
972   e34 = split_block (bb3, bb3end);
973   bb4 = e34->dest;
974   bb4->count = all;
975
976   e12->flags &= ~EDGE_FALLTHRU;
977   e12->flags |= EDGE_FALSE_VALUE;
978   e12->probability = prob;
979   e12->count = count;
980
981   e13 = make_edge (bb, bb3, EDGE_TRUE_VALUE);
982   e13->probability = REG_BR_PROB_BASE - prob;
983   e13->count = all - count;
984
985   remove_edge (e23);
986
987   e24 = make_edge (bb2, bb4, EDGE_FALLTHRU);
988   e24->probability = REG_BR_PROB_BASE;
989   e24->count = count;
990
991   e34->probability = REG_BR_PROB_BASE;
992   e34->count = all - count;
993
994   return result;
995 }
996
997 /* Do transform 2) on INSN if applicable.  */
998 static bool
999 gimple_mod_pow2_value_transform (gimple_stmt_iterator *si)
1000 {
1001   histogram_value histogram;
1002   enum tree_code code;
1003   gcov_type count, wrong_values, all;
1004   tree lhs_type, result, value;
1005   gcov_type prob;
1006   gassign *stmt;
1007
1008   stmt = dyn_cast <gassign *> (gsi_stmt (*si));
1009   if (!stmt)
1010     return false;
1011
1012   lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
1013   if (!INTEGRAL_TYPE_P (lhs_type))
1014     return false;
1015
1016   code = gimple_assign_rhs_code (stmt);
1017
1018   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
1019     return false;
1020
1021   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_POW2);
1022   if (!histogram)
1023     return false;
1024
1025   value = histogram->hvalue.value;
1026   wrong_values = histogram->hvalue.counters[0];
1027   count = histogram->hvalue.counters[1];
1028
1029   gimple_remove_histogram_value (cfun, stmt, histogram);
1030
1031   /* We require that we hit a power of 2 at least half of all evaluations.  */
1032   if (simple_cst_equal (gimple_assign_rhs2 (stmt), value) != 1
1033       || count < wrong_values
1034       || optimize_bb_for_size_p (gimple_bb (stmt)))
1035     return false;
1036
1037   if (dump_file)
1038     {
1039       fprintf (dump_file, "Mod power of 2 transformation on insn ");
1040       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1041     }
1042
1043   /* Compute probability of taking the optimal path.  */
1044   all = count + wrong_values;
1045
1046   if (check_counter (stmt, "pow2", &count, &all, gimple_bb (stmt)->count))
1047     return false;
1048
1049   if (all > 0)
1050     prob = GCOV_COMPUTE_SCALE (count, all);
1051   else
1052     prob = 0;
1053
1054   result = gimple_mod_pow2 (stmt, prob, count, all);
1055
1056   gimple_assign_set_rhs_from_tree (si, result);
1057   update_stmt (gsi_stmt (*si));
1058
1059   return true;
1060 }
1061
1062 /* Generate code for transformations 3 and 4 (with parent gimple assign STMT, and
1063    NCOUNTS the number of cases to support.  Currently only NCOUNTS==0 or 1 is
1064    supported and this is built into this interface.  The probabilities of taking
1065    the optimal paths are PROB1 and PROB2, which are equivalent to COUNT1/ALL and
1066    COUNT2/ALL respectively within roundoff error).  This generates the
1067    result into a temp and returns the temp; it does not replace or alter
1068    the original STMT.  */
1069 /* FIXME: Generalize the interface to handle NCOUNTS > 1.  */
1070
1071 static tree
1072 gimple_mod_subtract (gassign *stmt, int prob1, int prob2, int ncounts,
1073                      gcov_type count1, gcov_type count2, gcov_type all)
1074 {
1075   gassign *stmt1;
1076   gimple stmt2;
1077   gcond *stmt3;
1078   tree tmp1;
1079   gimple bb1end, bb2end = NULL, bb3end;
1080   basic_block bb, bb2, bb3, bb4;
1081   tree optype, op1, op2;
1082   edge e12, e23 = 0, e24, e34, e14;
1083   gimple_stmt_iterator gsi;
1084   tree result;
1085
1086   gcc_assert (is_gimple_assign (stmt)
1087               && gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR);
1088
1089   optype = TREE_TYPE (gimple_assign_lhs (stmt));
1090   op1 = gimple_assign_rhs1 (stmt);
1091   op2 = gimple_assign_rhs2 (stmt);
1092
1093   bb = gimple_bb (stmt);
1094   gsi = gsi_for_stmt (stmt);
1095
1096   result = create_tmp_reg (optype, "PROF");
1097   tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
1098   stmt1 = gimple_build_assign (result, op1);
1099   stmt2 = gimple_build_assign (tmp1, op2);
1100   stmt3 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
1101   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1102   gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
1103   gsi_insert_before (&gsi, stmt3, GSI_SAME_STMT);
1104   bb1end = stmt3;
1105
1106   if (ncounts)  /* Assumed to be 0 or 1 */
1107     {
1108       stmt1 = gimple_build_assign (result, MINUS_EXPR, result, tmp1);
1109       stmt2 = gimple_build_cond (LT_EXPR, result, tmp1, NULL_TREE, NULL_TREE);
1110       gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1111       gsi_insert_before (&gsi, stmt2, GSI_SAME_STMT);
1112       bb2end = stmt2;
1113     }
1114
1115   /* Fallback case. */
1116   stmt1 = gimple_build_assign (result, gimple_assign_rhs_code (stmt),
1117                                result, tmp1);
1118   gsi_insert_before (&gsi, stmt1, GSI_SAME_STMT);
1119   bb3end = stmt1;
1120
1121   /* Fix CFG. */
1122   /* Edge e23 connects bb2 to bb3, etc. */
1123   /* However block 3 is optional; if it is not there, references
1124      to 3 really refer to block 2. */
1125   e12 = split_block (bb, bb1end);
1126   bb2 = e12->dest;
1127   bb2->count = all - count1;
1128
1129   if (ncounts)  /* Assumed to be 0 or 1.  */
1130     {
1131       e23 = split_block (bb2, bb2end);
1132       bb3 = e23->dest;
1133       bb3->count = all - count1 - count2;
1134     }
1135
1136   e34 = split_block (ncounts ? bb3 : bb2, bb3end);
1137   bb4 = e34->dest;
1138   bb4->count = all;
1139
1140   e12->flags &= ~EDGE_FALLTHRU;
1141   e12->flags |= EDGE_FALSE_VALUE;
1142   e12->probability = REG_BR_PROB_BASE - prob1;
1143   e12->count = all - count1;
1144
1145   e14 = make_edge (bb, bb4, EDGE_TRUE_VALUE);
1146   e14->probability = prob1;
1147   e14->count = count1;
1148
1149   if (ncounts)  /* Assumed to be 0 or 1.  */
1150     {
1151       e23->flags &= ~EDGE_FALLTHRU;
1152       e23->flags |= EDGE_FALSE_VALUE;
1153       e23->count = all - count1 - count2;
1154       e23->probability = REG_BR_PROB_BASE - prob2;
1155
1156       e24 = make_edge (bb2, bb4, EDGE_TRUE_VALUE);
1157       e24->probability = prob2;
1158       e24->count = count2;
1159     }
1160
1161   e34->probability = REG_BR_PROB_BASE;
1162   e34->count = all - count1 - count2;
1163
1164   return result;
1165 }
1166
1167
1168 /* Do transforms 3) and 4) on the statement pointed-to by SI if applicable.  */
1169
1170 static bool
1171 gimple_mod_subtract_transform (gimple_stmt_iterator *si)
1172 {
1173   histogram_value histogram;
1174   enum tree_code code;
1175   gcov_type count, wrong_values, all;
1176   tree lhs_type, result;
1177   gcov_type prob1, prob2;
1178   unsigned int i, steps;
1179   gcov_type count1, count2;
1180   gassign *stmt;
1181
1182   stmt = dyn_cast <gassign *> (gsi_stmt (*si));
1183   if (!stmt)
1184     return false;
1185
1186   lhs_type = TREE_TYPE (gimple_assign_lhs (stmt));
1187   if (!INTEGRAL_TYPE_P (lhs_type))
1188     return false;
1189
1190   code = gimple_assign_rhs_code (stmt);
1191
1192   if (code != TRUNC_MOD_EXPR || !TYPE_UNSIGNED (lhs_type))
1193     return false;
1194
1195   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INTERVAL);
1196   if (!histogram)
1197     return false;
1198
1199   all = 0;
1200   wrong_values = 0;
1201   for (i = 0; i < histogram->hdata.intvl.steps; i++)
1202     all += histogram->hvalue.counters[i];
1203
1204   wrong_values += histogram->hvalue.counters[i];
1205   wrong_values += histogram->hvalue.counters[i+1];
1206   steps = histogram->hdata.intvl.steps;
1207   all += wrong_values;
1208   count1 = histogram->hvalue.counters[0];
1209   count2 = histogram->hvalue.counters[1];
1210
1211   /* Compute probability of taking the optimal path.  */
1212   if (check_counter (stmt, "interval", &count1, &all, gimple_bb (stmt)->count))
1213     {
1214       gimple_remove_histogram_value (cfun, stmt, histogram);
1215       return false;
1216     }
1217
1218   if (flag_profile_correction && count1 + count2 > all)
1219       all = count1 + count2;
1220
1221   gcc_assert (count1 + count2 <= all);
1222
1223   /* We require that we use just subtractions in at least 50% of all
1224      evaluations.  */
1225   count = 0;
1226   for (i = 0; i < histogram->hdata.intvl.steps; i++)
1227     {
1228       count += histogram->hvalue.counters[i];
1229       if (count * 2 >= all)
1230         break;
1231     }
1232   if (i == steps
1233       || optimize_bb_for_size_p (gimple_bb (stmt)))
1234     return false;
1235
1236   gimple_remove_histogram_value (cfun, stmt, histogram);
1237   if (dump_file)
1238     {
1239       fprintf (dump_file, "Mod subtract transformation on insn ");
1240       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1241     }
1242
1243   /* Compute probability of taking the optimal path(s).  */
1244   if (all > 0)
1245     {
1246       prob1 = GCOV_COMPUTE_SCALE (count1, all);
1247       prob2 = GCOV_COMPUTE_SCALE (count2, all);
1248     }
1249   else
1250     {
1251       prob1 = prob2 = 0;
1252     }
1253
1254   /* In practice, "steps" is always 2.  This interface reflects this,
1255      and will need to be changed if "steps" can change.  */
1256   result = gimple_mod_subtract (stmt, prob1, prob2, i, count1, count2, all);
1257
1258   gimple_assign_set_rhs_from_tree (si, result);
1259   update_stmt (gsi_stmt (*si));
1260
1261   return true;
1262 }
1263
1264 struct profile_id_traits : default_hashmap_traits
1265 {
1266   template<typename T>
1267   static bool
1268   is_deleted (T &e)
1269     {
1270       return e.m_key == UINT_MAX;
1271     }
1272
1273   template<typename T> static bool is_empty (T &e) { return e.m_key == 0; }
1274   template<typename T> static void mark_deleted (T &e) { e.m_key = UINT_MAX; }
1275   template<typename T> static void mark_empty (T &e) { e.m_key = 0; }
1276 };
1277
1278 static hash_map<unsigned int, cgraph_node *, profile_id_traits> *
1279 cgraph_node_map = 0;
1280
1281 /* Returns true if node graph is initialized. This
1282    is used to test if profile_id has been created
1283    for cgraph_nodes.  */
1284
1285 bool
1286 coverage_node_map_initialized_p (void)
1287 {
1288   return cgraph_node_map != 0;
1289 }
1290
1291 /* Initialize map from PROFILE_ID to CGRAPH_NODE.
1292    When LOCAL is true, the PROFILE_IDs are computed.  when it is false we assume
1293    that the PROFILE_IDs was already assigned.  */
1294
1295 void
1296 init_node_map (bool local)
1297 {
1298   struct cgraph_node *n;
1299   cgraph_node_map
1300     = new hash_map<unsigned int, cgraph_node *, profile_id_traits>;
1301
1302   FOR_EACH_DEFINED_FUNCTION (n)
1303     if (n->has_gimple_body_p ())
1304       {
1305         cgraph_node **val;
1306         if (local)
1307           {
1308             n->profile_id = coverage_compute_profile_id (n);
1309             while ((val = cgraph_node_map->get (n->profile_id))
1310                    || !n->profile_id)
1311               {
1312                 if (dump_file)
1313                   fprintf (dump_file, "Local profile-id %i conflict"
1314                            " with nodes %s/%i %s/%i\n",
1315                            n->profile_id,
1316                            n->name (),
1317                            n->order,
1318                            (*val)->name (),
1319                            (*val)->order);
1320                 n->profile_id = (n->profile_id + 1) & 0x7fffffff;
1321               }
1322           }
1323         else if (!n->profile_id)
1324           {
1325             if (dump_file)
1326               fprintf (dump_file,
1327                        "Node %s/%i has no profile-id"
1328                        " (profile feedback missing?)\n",
1329                        n->name (),
1330                        n->order);
1331             continue;
1332           }
1333         else if ((val = cgraph_node_map->get (n->profile_id)))
1334           {
1335             if (dump_file)
1336               fprintf (dump_file,
1337                        "Node %s/%i has IP profile-id %i conflict. "
1338                        "Giving up.\n",
1339                        n->name (),
1340                        n->order,
1341                        n->profile_id);
1342             *val = NULL;
1343             continue;
1344           }
1345         cgraph_node_map->put (n->profile_id, n);
1346       }
1347 }
1348
1349 /* Delete the CGRAPH_NODE_MAP.  */
1350
1351 void
1352 del_node_map (void)
1353 {
1354   delete cgraph_node_map;
1355 }
1356
1357 /* Return cgraph node for function with pid */
1358
1359 struct cgraph_node*
1360 find_func_by_profile_id (int profile_id)
1361 {
1362   cgraph_node **val = cgraph_node_map->get (profile_id);
1363   if (val)
1364     return *val;
1365   else
1366     return NULL;
1367 }
1368
1369 /* Perform sanity check on the indirect call target. Due to race conditions,
1370    false function target may be attributed to an indirect call site. If the
1371    call expression type mismatches with the target function's type, expand_call
1372    may ICE. Here we only do very minimal sanity check just to make compiler happy.
1373    Returns true if TARGET is considered ok for call CALL_STMT.  */
1374
1375 bool
1376 check_ic_target (gcall *call_stmt, struct cgraph_node *target)
1377 {
1378    location_t locus;
1379    if (gimple_check_call_matching_types (call_stmt, target->decl, true))
1380      return true;
1381
1382    locus =  gimple_location (call_stmt);
1383    if (dump_enabled_p ())
1384      dump_printf_loc (MSG_MISSED_OPTIMIZATION, locus,
1385                       "Skipping target %s with mismatching types for icall\n",
1386                       target->name ());
1387    return false;
1388 }
1389
1390 /* Do transformation
1391
1392   if (actual_callee_address == address_of_most_common_function/method)
1393     do direct call
1394   else
1395     old call
1396  */
1397
1398 gcall *
1399 gimple_ic (gcall *icall_stmt, struct cgraph_node *direct_call,
1400            int prob, gcov_type count, gcov_type all)
1401 {
1402   gcall *dcall_stmt;
1403   gassign *load_stmt;
1404   gcond *cond_stmt;
1405   gcall *iretbnd_stmt = NULL;
1406   tree tmp0, tmp1, tmp;
1407   basic_block cond_bb, dcall_bb, icall_bb, join_bb = NULL;
1408   tree optype = build_pointer_type (void_type_node);
1409   edge e_cd, e_ci, e_di, e_dj = NULL, e_ij;
1410   gimple_stmt_iterator gsi;
1411   int lp_nr, dflags;
1412   edge e_eh, e;
1413   edge_iterator ei;
1414   gimple_stmt_iterator psi;
1415
1416   cond_bb = gimple_bb (icall_stmt);
1417   gsi = gsi_for_stmt (icall_stmt);
1418
1419   if (gimple_call_with_bounds_p (icall_stmt) && gimple_call_lhs (icall_stmt))
1420     iretbnd_stmt = chkp_retbnd_call_by_val (gimple_call_lhs (icall_stmt));
1421
1422   tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
1423   tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
1424   tmp = unshare_expr (gimple_call_fn (icall_stmt));
1425   load_stmt = gimple_build_assign (tmp0, tmp);
1426   gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1427
1428   tmp = fold_convert (optype, build_addr (direct_call->decl,
1429                                           current_function_decl));
1430   load_stmt = gimple_build_assign (tmp1, tmp);
1431   gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
1432
1433   cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1434   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1435
1436   gimple_set_vdef (icall_stmt, NULL_TREE);
1437   gimple_set_vuse (icall_stmt, NULL_TREE);
1438   update_stmt (icall_stmt);
1439   dcall_stmt = as_a <gcall *> (gimple_copy (icall_stmt));
1440   gimple_call_set_fndecl (dcall_stmt, direct_call->decl);
1441   dflags = flags_from_decl_or_type (direct_call->decl);
1442   if ((dflags & ECF_NORETURN) != 0)
1443     gimple_call_set_lhs (dcall_stmt, NULL_TREE);
1444   gsi_insert_before (&gsi, dcall_stmt, GSI_SAME_STMT);
1445
1446   /* Fix CFG. */
1447   /* Edge e_cd connects cond_bb to dcall_bb, etc; note the first letters. */
1448   e_cd = split_block (cond_bb, cond_stmt);
1449   dcall_bb = e_cd->dest;
1450   dcall_bb->count = count;
1451
1452   e_di = split_block (dcall_bb, dcall_stmt);
1453   icall_bb = e_di->dest;
1454   icall_bb->count = all - count;
1455
1456   /* Do not disturb existing EH edges from the indirect call.  */
1457   if (!stmt_ends_bb_p (icall_stmt))
1458     e_ij = split_block (icall_bb, icall_stmt);
1459   else
1460     {
1461       e_ij = find_fallthru_edge (icall_bb->succs);
1462       /* The indirect call might be noreturn.  */
1463       if (e_ij != NULL)
1464         {
1465           e_ij->probability = REG_BR_PROB_BASE;
1466           e_ij->count = all - count;
1467           e_ij = single_pred_edge (split_edge (e_ij));
1468         }
1469     }
1470   if (e_ij != NULL)
1471     {
1472       join_bb = e_ij->dest;
1473       join_bb->count = all;
1474     }
1475
1476   e_cd->flags = (e_cd->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1477   e_cd->probability = prob;
1478   e_cd->count = count;
1479
1480   e_ci = make_edge (cond_bb, icall_bb, EDGE_FALSE_VALUE);
1481   e_ci->probability = REG_BR_PROB_BASE - prob;
1482   e_ci->count = all - count;
1483
1484   remove_edge (e_di);
1485
1486   if (e_ij != NULL)
1487     {
1488       if ((dflags & ECF_NORETURN) != 0)
1489         e_ij->count = all;
1490       else
1491         {
1492           e_dj = make_edge (dcall_bb, join_bb, EDGE_FALLTHRU);
1493           e_dj->probability = REG_BR_PROB_BASE;
1494           e_dj->count = count;
1495
1496           e_ij->count = all - count;
1497         }
1498       e_ij->probability = REG_BR_PROB_BASE;
1499     }
1500
1501   /* Insert PHI node for the call result if necessary.  */
1502   if (gimple_call_lhs (icall_stmt)
1503       && TREE_CODE (gimple_call_lhs (icall_stmt)) == SSA_NAME
1504       && (dflags & ECF_NORETURN) == 0)
1505     {
1506       tree result = gimple_call_lhs (icall_stmt);
1507       gphi *phi = create_phi_node (result, join_bb);
1508       gimple_call_set_lhs (icall_stmt,
1509                            duplicate_ssa_name (result, icall_stmt));
1510       add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1511       gimple_call_set_lhs (dcall_stmt,
1512                            duplicate_ssa_name (result, dcall_stmt));
1513       add_phi_arg (phi, gimple_call_lhs (dcall_stmt), e_dj, UNKNOWN_LOCATION);
1514
1515       /* If indirect call has following BUILT_IN_CHKP_BNDRET
1516          call then we need to make it's copy for the direct
1517          call.  */
1518       if (iretbnd_stmt)
1519         {
1520           if (gimple_call_lhs (iretbnd_stmt))
1521             {
1522               gimple copy;
1523
1524               gimple_set_vdef (iretbnd_stmt, NULL_TREE);
1525               gimple_set_vuse (iretbnd_stmt, NULL_TREE);
1526               update_stmt (iretbnd_stmt);
1527
1528               result = gimple_call_lhs (iretbnd_stmt);
1529               phi = create_phi_node (result, join_bb);
1530
1531               copy = gimple_copy (iretbnd_stmt);
1532               gimple_call_set_arg (copy, 0,
1533                                    gimple_call_lhs (dcall_stmt));
1534               gimple_call_set_lhs (copy, duplicate_ssa_name (result, copy));
1535               gsi_insert_on_edge (e_dj, copy);
1536               add_phi_arg (phi, gimple_call_lhs (copy),
1537                            e_dj, UNKNOWN_LOCATION);
1538
1539               gimple_call_set_arg (iretbnd_stmt, 0,
1540                                    gimple_call_lhs (icall_stmt));
1541               gimple_call_set_lhs (iretbnd_stmt,
1542                                    duplicate_ssa_name (result, iretbnd_stmt));
1543               psi = gsi_for_stmt (iretbnd_stmt);
1544               gsi_remove (&psi, false);
1545               gsi_insert_on_edge (e_ij, iretbnd_stmt);
1546               add_phi_arg (phi, gimple_call_lhs (iretbnd_stmt),
1547                            e_ij, UNKNOWN_LOCATION);
1548
1549               gsi_commit_one_edge_insert (e_dj, NULL);
1550               gsi_commit_one_edge_insert (e_ij, NULL);
1551             }
1552           else
1553             {
1554               psi = gsi_for_stmt (iretbnd_stmt);
1555               gsi_remove (&psi, true);
1556             }
1557         }
1558     }
1559
1560   /* Build an EH edge for the direct call if necessary.  */
1561   lp_nr = lookup_stmt_eh_lp (icall_stmt);
1562   if (lp_nr > 0 && stmt_could_throw_p (dcall_stmt))
1563     {
1564       add_stmt_to_eh_lp (dcall_stmt, lp_nr);
1565     }
1566
1567   FOR_EACH_EDGE (e_eh, ei, icall_bb->succs)
1568     if (e_eh->flags & (EDGE_EH | EDGE_ABNORMAL))
1569       {
1570         e = make_edge (dcall_bb, e_eh->dest, e_eh->flags);
1571         for (gphi_iterator psi = gsi_start_phis (e_eh->dest);
1572              !gsi_end_p (psi); gsi_next (&psi))
1573           {
1574             gphi *phi = psi.phi ();
1575             SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e),
1576                      PHI_ARG_DEF_FROM_EDGE (phi, e_eh));
1577           }
1578        }
1579   return dcall_stmt;
1580 }
1581
1582 /*
1583   For every checked indirect/virtual call determine if most common pid of
1584   function/class method has probability more than 50%. If yes modify code of
1585   this call to:
1586  */
1587
1588 static bool
1589 gimple_ic_transform (gimple_stmt_iterator *gsi)
1590 {
1591   gcall *stmt;
1592   histogram_value histogram;
1593   gcov_type val, count, all, bb_all;
1594   struct cgraph_node *direct_call;
1595
1596   stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1597   if (!stmt)
1598     return false;
1599
1600   if (gimple_call_fndecl (stmt) != NULL_TREE)
1601     return false;
1602
1603   if (gimple_call_internal_p (stmt))
1604     return false;
1605
1606   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_INDIR_CALL);
1607   if (!histogram)
1608     return false;
1609
1610   val = histogram->hvalue.counters [0];
1611   count = histogram->hvalue.counters [1];
1612   all = histogram->hvalue.counters [2];
1613
1614   bb_all = gimple_bb (stmt)->count;
1615   /* The order of CHECK_COUNTER calls is important -
1616      since check_counter can correct the third parameter
1617      and we want to make count <= all <= bb_all. */
1618   if ( check_counter (stmt, "ic", &all, &bb_all, bb_all)
1619       || check_counter (stmt, "ic", &count, &all, all))
1620     {
1621       gimple_remove_histogram_value (cfun, stmt, histogram);
1622       return false;
1623     }
1624
1625   if (4 * count <= 3 * all)
1626     return false;
1627
1628   direct_call = find_func_by_profile_id ((int)val);
1629
1630   if (direct_call == NULL)
1631     {
1632       if (val)
1633         {
1634           if (dump_file)
1635             {
1636               fprintf (dump_file, "Indirect call -> direct call from other module");
1637               print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1638               fprintf (dump_file, "=> %i (will resolve only with LTO)\n", (int)val);
1639             }
1640         }
1641       return false;
1642     }
1643
1644   if (!check_ic_target (stmt, direct_call))
1645     {
1646       if (dump_file)
1647         {
1648           fprintf (dump_file, "Indirect call -> direct call ");
1649           print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1650           fprintf (dump_file, "=> ");
1651           print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1652           fprintf (dump_file, " transformation skipped because of type mismatch");
1653           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1654         }
1655       gimple_remove_histogram_value (cfun, stmt, histogram);
1656       return false;
1657     }
1658
1659   if (dump_file)
1660     {
1661       fprintf (dump_file, "Indirect call -> direct call ");
1662       print_generic_expr (dump_file, gimple_call_fn (stmt), TDF_SLIM);
1663       fprintf (dump_file, "=> ");
1664       print_generic_expr (dump_file, direct_call->decl, TDF_SLIM);
1665       fprintf (dump_file, " transformation on insn postponned to ipa-profile");
1666       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1667       fprintf (dump_file, "hist->count %"PRId64
1668                " hist->all %"PRId64"\n", count, all);
1669     }
1670
1671   return true;
1672 }
1673
1674 /* Return true if the stringop CALL with FNDECL shall be profiled.
1675    SIZE_ARG be set to the argument index for the size of the string
1676    operation.
1677 */
1678 static bool
1679 interesting_stringop_to_profile_p (tree fndecl, gcall *call, int *size_arg)
1680 {
1681   enum built_in_function fcode = DECL_FUNCTION_CODE (fndecl);
1682
1683   if (fcode != BUILT_IN_MEMCPY && fcode != BUILT_IN_MEMPCPY
1684       && fcode != BUILT_IN_MEMSET && fcode != BUILT_IN_BZERO)
1685     return false;
1686
1687   switch (fcode)
1688     {
1689      case BUILT_IN_MEMCPY:
1690      case BUILT_IN_MEMPCPY:
1691        *size_arg = 2;
1692        return validate_gimple_arglist (call, POINTER_TYPE, POINTER_TYPE,
1693                                        INTEGER_TYPE, VOID_TYPE);
1694      case BUILT_IN_MEMSET:
1695        *size_arg = 2;
1696        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1697                                       INTEGER_TYPE, VOID_TYPE);
1698      case BUILT_IN_BZERO:
1699        *size_arg = 1;
1700        return validate_gimple_arglist (call, POINTER_TYPE, INTEGER_TYPE,
1701                                        VOID_TYPE);
1702      default:
1703        gcc_unreachable ();
1704     }
1705 }
1706
1707 /* Convert   stringop (..., vcall_size)
1708    into
1709    if (vcall_size == icall_size)
1710      stringop (..., icall_size);
1711    else
1712      stringop (..., vcall_size);
1713    assuming we'll propagate a true constant into ICALL_SIZE later.  */
1714
1715 static void
1716 gimple_stringop_fixed_value (gcall *vcall_stmt, tree icall_size, int prob,
1717                              gcov_type count, gcov_type all)
1718 {
1719   gassign *tmp_stmt;
1720   gcond *cond_stmt;
1721   gcall *icall_stmt;
1722   tree tmp0, tmp1, vcall_size, optype;
1723   basic_block cond_bb, icall_bb, vcall_bb, join_bb;
1724   edge e_ci, e_cv, e_iv, e_ij, e_vj;
1725   gimple_stmt_iterator gsi;
1726   tree fndecl;
1727   int size_arg;
1728
1729   fndecl = gimple_call_fndecl (vcall_stmt);
1730   if (!interesting_stringop_to_profile_p (fndecl, vcall_stmt, &size_arg))
1731     gcc_unreachable ();
1732
1733   cond_bb = gimple_bb (vcall_stmt);
1734   gsi = gsi_for_stmt (vcall_stmt);
1735
1736   vcall_size = gimple_call_arg (vcall_stmt, size_arg);
1737   optype = TREE_TYPE (vcall_size);
1738
1739   tmp0 = make_temp_ssa_name (optype, NULL, "PROF");
1740   tmp1 = make_temp_ssa_name (optype, NULL, "PROF");
1741   tmp_stmt = gimple_build_assign (tmp0, fold_convert (optype, icall_size));
1742   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1743
1744   tmp_stmt = gimple_build_assign (tmp1, vcall_size);
1745   gsi_insert_before (&gsi, tmp_stmt, GSI_SAME_STMT);
1746
1747   cond_stmt = gimple_build_cond (EQ_EXPR, tmp1, tmp0, NULL_TREE, NULL_TREE);
1748   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
1749
1750   gimple_set_vdef (vcall_stmt, NULL);
1751   gimple_set_vuse (vcall_stmt, NULL);
1752   update_stmt (vcall_stmt);
1753   icall_stmt = as_a <gcall *> (gimple_copy (vcall_stmt));
1754   gimple_call_set_arg (icall_stmt, size_arg, icall_size);
1755   gsi_insert_before (&gsi, icall_stmt, GSI_SAME_STMT);
1756
1757   /* Fix CFG. */
1758   /* Edge e_ci connects cond_bb to icall_bb, etc. */
1759   e_ci = split_block (cond_bb, cond_stmt);
1760   icall_bb = e_ci->dest;
1761   icall_bb->count = count;
1762
1763   e_iv = split_block (icall_bb, icall_stmt);
1764   vcall_bb = e_iv->dest;
1765   vcall_bb->count = all - count;
1766
1767   e_vj = split_block (vcall_bb, vcall_stmt);
1768   join_bb = e_vj->dest;
1769   join_bb->count = all;
1770
1771   e_ci->flags = (e_ci->flags & ~EDGE_FALLTHRU) | EDGE_TRUE_VALUE;
1772   e_ci->probability = prob;
1773   e_ci->count = count;
1774
1775   e_cv = make_edge (cond_bb, vcall_bb, EDGE_FALSE_VALUE);
1776   e_cv->probability = REG_BR_PROB_BASE - prob;
1777   e_cv->count = all - count;
1778
1779   remove_edge (e_iv);
1780
1781   e_ij = make_edge (icall_bb, join_bb, EDGE_FALLTHRU);
1782   e_ij->probability = REG_BR_PROB_BASE;
1783   e_ij->count = count;
1784
1785   e_vj->probability = REG_BR_PROB_BASE;
1786   e_vj->count = all - count;
1787
1788   /* Insert PHI node for the call result if necessary.  */
1789   if (gimple_call_lhs (vcall_stmt)
1790       && TREE_CODE (gimple_call_lhs (vcall_stmt)) == SSA_NAME)
1791     {
1792       tree result = gimple_call_lhs (vcall_stmt);
1793       gphi *phi = create_phi_node (result, join_bb);
1794       gimple_call_set_lhs (vcall_stmt,
1795                            duplicate_ssa_name (result, vcall_stmt));
1796       add_phi_arg (phi, gimple_call_lhs (vcall_stmt), e_vj, UNKNOWN_LOCATION);
1797       gimple_call_set_lhs (icall_stmt,
1798                            duplicate_ssa_name (result, icall_stmt));
1799       add_phi_arg (phi, gimple_call_lhs (icall_stmt), e_ij, UNKNOWN_LOCATION);
1800     }
1801
1802   /* Because these are all string op builtins, they're all nothrow.  */
1803   gcc_assert (!stmt_could_throw_p (vcall_stmt));
1804   gcc_assert (!stmt_could_throw_p (icall_stmt));
1805 }
1806
1807 /* Find values inside STMT for that we want to measure histograms for
1808    division/modulo optimization.  */
1809 static bool
1810 gimple_stringops_transform (gimple_stmt_iterator *gsi)
1811 {
1812   gcall *stmt;
1813   tree fndecl;
1814   tree blck_size;
1815   enum built_in_function fcode;
1816   histogram_value histogram;
1817   gcov_type count, all, val;
1818   tree dest, src;
1819   unsigned int dest_align, src_align;
1820   gcov_type prob;
1821   tree tree_val;
1822   int size_arg;
1823
1824   stmt = dyn_cast <gcall *> (gsi_stmt (*gsi));
1825   if (!stmt)
1826     return false;
1827   fndecl = gimple_call_fndecl (stmt);
1828   if (!fndecl)
1829     return false;
1830   fcode = DECL_FUNCTION_CODE (fndecl);
1831   if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
1832     return false;
1833
1834   blck_size = gimple_call_arg (stmt, size_arg);
1835   if (TREE_CODE (blck_size) == INTEGER_CST)
1836     return false;
1837
1838   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_SINGLE_VALUE);
1839   if (!histogram)
1840     return false;
1841   val = histogram->hvalue.counters[0];
1842   count = histogram->hvalue.counters[1];
1843   all = histogram->hvalue.counters[2];
1844   gimple_remove_histogram_value (cfun, stmt, histogram);
1845   /* We require that count is at least half of all; this means
1846      that for the transformation to fire the value must be constant
1847      at least 80% of time.  */
1848   if ((6 * count / 5) < all || optimize_bb_for_size_p (gimple_bb (stmt)))
1849     return false;
1850   if (check_counter (stmt, "value", &count, &all, gimple_bb (stmt)->count))
1851     return false;
1852   if (all > 0)
1853     prob = GCOV_COMPUTE_SCALE (count, all);
1854   else
1855     prob = 0;
1856   dest = gimple_call_arg (stmt, 0);
1857   dest_align = get_pointer_alignment (dest);
1858   switch (fcode)
1859     {
1860     case BUILT_IN_MEMCPY:
1861     case BUILT_IN_MEMPCPY:
1862       src = gimple_call_arg (stmt, 1);
1863       src_align = get_pointer_alignment (src);
1864       if (!can_move_by_pieces (val, MIN (dest_align, src_align)))
1865         return false;
1866       break;
1867     case BUILT_IN_MEMSET:
1868       if (!can_store_by_pieces (val, builtin_memset_read_str,
1869                                 gimple_call_arg (stmt, 1),
1870                                 dest_align, true))
1871         return false;
1872       break;
1873     case BUILT_IN_BZERO:
1874       if (!can_store_by_pieces (val, builtin_memset_read_str,
1875                                 integer_zero_node,
1876                                 dest_align, true))
1877         return false;
1878       break;
1879     default:
1880       gcc_unreachable ();
1881     }
1882   if (sizeof (gcov_type) == sizeof (HOST_WIDE_INT))
1883     tree_val = build_int_cst (get_gcov_type (), val);
1884   else
1885     {
1886       HOST_WIDE_INT a[2];
1887       a[0] = (unsigned HOST_WIDE_INT) val;
1888       a[1] = val >> (HOST_BITS_PER_WIDE_INT - 1) >> 1;
1889
1890       tree_val = wide_int_to_tree (get_gcov_type (), wide_int::from_array (a, 2,
1891         TYPE_PRECISION (get_gcov_type ()), false));
1892     }
1893
1894   if (dump_file)
1895     {
1896       fprintf (dump_file, "Single value %i stringop transformation on ",
1897                (int)val);
1898       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
1899     }
1900   gimple_stringop_fixed_value (stmt, tree_val, prob, count, all);
1901
1902   return true;
1903 }
1904
1905 void
1906 stringop_block_profile (gimple stmt, unsigned int *expected_align,
1907                         HOST_WIDE_INT *expected_size)
1908 {
1909   histogram_value histogram;
1910   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_AVERAGE);
1911   if (!histogram)
1912     *expected_size = -1;
1913   else if (!histogram->hvalue.counters[1])
1914     {
1915       *expected_size = -1;
1916       gimple_remove_histogram_value (cfun, stmt, histogram);
1917     }
1918   else
1919     {
1920       gcov_type size;
1921       size = ((histogram->hvalue.counters[0]
1922               + histogram->hvalue.counters[1] / 2)
1923                / histogram->hvalue.counters[1]);
1924       /* Even if we can hold bigger value in SIZE, INT_MAX
1925          is safe "infinity" for code generation strategies.  */
1926       if (size > INT_MAX)
1927         size = INT_MAX;
1928       *expected_size = size;
1929       gimple_remove_histogram_value (cfun, stmt, histogram);
1930     }
1931   histogram = gimple_histogram_value_of_type (cfun, stmt, HIST_TYPE_IOR);
1932   if (!histogram)
1933     *expected_align = 0;
1934   else if (!histogram->hvalue.counters[0])
1935     {
1936       gimple_remove_histogram_value (cfun, stmt, histogram);
1937       *expected_align = 0;
1938     }
1939   else
1940     {
1941       gcov_type count;
1942       int alignment;
1943
1944       count = histogram->hvalue.counters[0];
1945       alignment = 1;
1946       while (!(count & alignment)
1947              && (alignment * 2 * BITS_PER_UNIT))
1948         alignment <<= 1;
1949       *expected_align = alignment * BITS_PER_UNIT;
1950       gimple_remove_histogram_value (cfun, stmt, histogram);
1951     }
1952 }
1953
1954 \f
1955 /* Find values inside STMT for that we want to measure histograms for
1956    division/modulo optimization.  */
1957 static void
1958 gimple_divmod_values_to_profile (gimple stmt, histogram_values *values)
1959 {
1960   tree lhs, divisor, op0, type;
1961   histogram_value hist;
1962
1963   if (gimple_code (stmt) != GIMPLE_ASSIGN)
1964     return;
1965
1966   lhs = gimple_assign_lhs (stmt);
1967   type = TREE_TYPE (lhs);
1968   if (!INTEGRAL_TYPE_P (type))
1969     return;
1970
1971   switch (gimple_assign_rhs_code (stmt))
1972     {
1973     case TRUNC_DIV_EXPR:
1974     case TRUNC_MOD_EXPR:
1975       divisor = gimple_assign_rhs2 (stmt);
1976       op0 = gimple_assign_rhs1 (stmt);
1977
1978       values->reserve (3);
1979
1980       if (TREE_CODE (divisor) == SSA_NAME)
1981         /* Check for the case where the divisor is the same value most
1982            of the time.  */
1983         values->quick_push (gimple_alloc_histogram_value (cfun,
1984                                                       HIST_TYPE_SINGLE_VALUE,
1985                                                       stmt, divisor));
1986
1987       /* For mod, check whether it is not often a noop (or replaceable by
1988          a few subtractions).  */
1989       if (gimple_assign_rhs_code (stmt) == TRUNC_MOD_EXPR
1990           && TYPE_UNSIGNED (type))
1991         {
1992           tree val;
1993           /* Check for a special case where the divisor is power of 2.  */
1994           values->quick_push (gimple_alloc_histogram_value (cfun,
1995                                                             HIST_TYPE_POW2,
1996                                                             stmt, divisor));
1997
1998           val = build2 (TRUNC_DIV_EXPR, type, op0, divisor);
1999           hist = gimple_alloc_histogram_value (cfun, HIST_TYPE_INTERVAL,
2000                                                stmt, val);
2001           hist->hdata.intvl.int_start = 0;
2002           hist->hdata.intvl.steps = 2;
2003           values->quick_push (hist);
2004         }
2005       return;
2006
2007     default:
2008       return;
2009     }
2010 }
2011
2012 /* Find calls inside STMT for that we want to measure histograms for
2013    indirect/virtual call optimization. */
2014
2015 static void
2016 gimple_indirect_call_to_profile (gimple stmt, histogram_values *values)
2017 {
2018   tree callee;
2019
2020   if (gimple_code (stmt) != GIMPLE_CALL
2021       || gimple_call_internal_p (stmt)
2022       || gimple_call_fndecl (stmt) != NULL_TREE)
2023     return;
2024
2025   callee = gimple_call_fn (stmt);
2026
2027   values->reserve (3);
2028
2029   values->quick_push (gimple_alloc_histogram_value (
2030                         cfun,
2031                         PARAM_VALUE (PARAM_INDIR_CALL_TOPN_PROFILE) ?
2032                           HIST_TYPE_INDIR_CALL_TOPN :
2033                           HIST_TYPE_INDIR_CALL,
2034                         stmt, callee));
2035
2036   return;
2037 }
2038
2039 /* Find values inside STMT for that we want to measure histograms for
2040    string operations.  */
2041 static void
2042 gimple_stringops_values_to_profile (gimple gs, histogram_values *values)
2043 {
2044   gcall *stmt;
2045   tree fndecl;
2046   tree blck_size;
2047   tree dest;
2048   int size_arg;
2049
2050   stmt = dyn_cast <gcall *> (gs);
2051   if (!stmt)
2052     return;
2053   fndecl = gimple_call_fndecl (stmt);
2054   if (!fndecl)
2055     return;
2056
2057   if (!interesting_stringop_to_profile_p (fndecl, stmt, &size_arg))
2058     return;
2059
2060   dest = gimple_call_arg (stmt, 0);
2061   blck_size = gimple_call_arg (stmt, size_arg);
2062
2063   if (TREE_CODE (blck_size) != INTEGER_CST)
2064     {
2065       values->safe_push (gimple_alloc_histogram_value (cfun,
2066                                                        HIST_TYPE_SINGLE_VALUE,
2067                                                        stmt, blck_size));
2068       values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_AVERAGE,
2069                                                        stmt, blck_size));
2070     }
2071   if (TREE_CODE (blck_size) != INTEGER_CST)
2072     values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_IOR,
2073                                                      stmt, dest));
2074 }
2075
2076 /* Find values inside STMT for that we want to measure histograms and adds
2077    them to list VALUES.  */
2078
2079 static void
2080 gimple_values_to_profile (gimple stmt, histogram_values *values)
2081 {
2082   gimple_divmod_values_to_profile (stmt, values);
2083   gimple_stringops_values_to_profile (stmt, values);
2084   gimple_indirect_call_to_profile (stmt, values);
2085 }
2086
2087 void
2088 gimple_find_values_to_profile (histogram_values *values)
2089 {
2090   basic_block bb;
2091   gimple_stmt_iterator gsi;
2092   unsigned i;
2093   histogram_value hist = NULL;
2094   values->create (0);
2095
2096   FOR_EACH_BB_FN (bb, cfun)
2097     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2098       gimple_values_to_profile (gsi_stmt (gsi), values);
2099
2100   values->safe_push (gimple_alloc_histogram_value (cfun, HIST_TYPE_TIME_PROFILE, 0, 0));
2101
2102   FOR_EACH_VEC_ELT (*values, i, hist)
2103     {
2104       switch (hist->type)
2105         {
2106         case HIST_TYPE_INTERVAL:
2107           hist->n_counters = hist->hdata.intvl.steps + 2;
2108           break;
2109
2110         case HIST_TYPE_POW2:
2111           hist->n_counters = 2;
2112           break;
2113
2114         case HIST_TYPE_SINGLE_VALUE:
2115           hist->n_counters = 3;
2116           break;
2117
2118         case HIST_TYPE_CONST_DELTA:
2119           hist->n_counters = 4;
2120           break;
2121
2122         case HIST_TYPE_INDIR_CALL:
2123           hist->n_counters = 3;
2124           break;
2125
2126         case HIST_TYPE_TIME_PROFILE:
2127           hist->n_counters = 1;
2128           break;
2129
2130         case HIST_TYPE_AVERAGE:
2131           hist->n_counters = 2;
2132           break;
2133
2134         case HIST_TYPE_IOR:
2135           hist->n_counters = 1;
2136           break;
2137
2138         case HIST_TYPE_INDIR_CALL_TOPN:
2139           hist->n_counters = GCOV_ICALL_TOPN_NCOUNTS;
2140           break;
2141
2142         default:
2143           gcc_unreachable ();
2144         }
2145       if (dump_file)
2146         {
2147           fprintf (dump_file, "Stmt ");
2148           print_gimple_stmt (dump_file, hist->hvalue.stmt, 0, TDF_SLIM);
2149           dump_histogram_value (dump_file, hist);
2150         }
2151     }
2152 }