gcc/ipa-profile.c

   1 /* Basic IPA optimizations based on profile.
   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 /* ipa-profile pass implements the following analysis propagating profille
  21    inter-procedurally.
  22
  23    - Count histogram construction.  This is a histogram analyzing how much
  24      time is spent executing statements with a given execution count read
  25      from profile feedback. This histogram is complete only with LTO,
  26      otherwise it contains information only about the current unit.
  27
  28      Similar histogram is also estimated by coverage runtime.  This histogram
  29      is not dependent on LTO, but it suffers from various defects; first
  30      gcov runtime is not weighting individual basic block by estimated execution
  31      time and second the merging of multiple runs makes assumption that the
  32      histogram distribution did not change.  Consequentely histogram constructed
  33      here may be more precise.
  34
  35      The information is used to set hot/cold thresholds.
  36    - Next speculative indirect call resolution is performed:  the local
  37      profile pass assigns profile-id to each function and provide us with a
  38      histogram specifying the most common target.  We look up the callgraph
  39      node corresponding to the target and produce a speculative call.
  40
  41      This call may or may not survive through IPA optimization based on decision
  42      of inliner.
  43    - Finally we propagate the following flags: unlikely executed, executed
  44      once, executed at startup and executed at exit.  These flags are used to
  45      control code size/performance threshold and and code placement (by producing
  46      .text.unlikely/.text.hot/.text.startup/.text.exit subsections).  */
  47 #include "config.h"
  48 #include "system.h"
  49 #include "coretypes.h"
  50 #include "tm.h"
  51 #include "hash-set.h"
  52 #include "machmode.h"
  53 #include "vec.h"
  54 #include "double-int.h"
  55 #include "input.h"
  56 #include "alias.h"
  57 #include "symtab.h"
  58 #include "wide-int.h"
  59 #include "inchash.h"
  60 #include "tree.h"
  61 #include "fold-const.h"
  62 #include "predict.h"
  63 #include "dominance.h"
  64 #include "cfg.h"
  65 #include "basic-block.h"
  66 #include "hash-map.h"
  67 #include "is-a.h"
  68 #include "plugin-api.h"
  69 #include "hard-reg-set.h"
  70 #include "input.h"
  71 #include "function.h"
  72 #include "ipa-ref.h"
  73 #include "cgraph.h"
  74 #include "tree-pass.h"
  75 #include "tree-ssa-alias.h"
  76 #include "internal-fn.h"
  77 #include "gimple-expr.h"
  78 #include "gimple.h"
  79 #include "gimple-iterator.h"
  80 #include "flags.h"
  81 #include "target.h"
  82 #include "tree-iterator.h"
  83 #include "ipa-utils.h"
  84 #include "profile.h"
  85 #include "params.h"
  86 #include "value-prof.h"
  87 #include "alloc-pool.h"
  88 #include "tree-inline.h"
  89 #include "lto-streamer.h"
  90 #include "data-streamer.h"
  91 #include "symbol-summary.h"
  92 #include "ipa-prop.h"
  93 #include "ipa-inline.h"
  94
  95 /* Entry in the histogram.  */
  96
  97 struct histogram_entry
  98 {
  99   gcov_type count;
 100   int time;
 101   int size;
 102 };
 103
 104 /* Histogram of profile values.
 105    The histogram is represented as an ordered vector of entries allocated via
 106    histogram_pool. During construction a separate hashtable is kept to lookup
 107    duplicate entries.  */
 108
 109 vec<histogram_entry *> histogram;
 110 static alloc_pool histogram_pool;
 111
 112 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR.  */
 113
 114 struct histogram_hash : typed_noop_remove <histogram_entry>
 115 {
 116   typedef histogram_entry value_type;
 117   typedef histogram_entry compare_type;
 118   static inline hashval_t hash (const value_type *);
 119   static inline int equal (const value_type *, const compare_type *);
 120 };
 121
 122 inline hashval_t
 123 histogram_hash::hash (const histogram_entry *val)
 124 {
 125   return val->count;
 126 }
 127
 128 inline int
 129 histogram_hash::equal (const histogram_entry *val, const histogram_entry *val2)
 130 {
 131   return val->count == val2->count;
 132 }
 133
 134 /* Account TIME and SIZE executed COUNT times into HISTOGRAM.
 135    HASHTABLE is the on-side hash kept to avoid duplicates.  */
 136
 137 static void
 138 account_time_size (hash_table<histogram_hash> *hashtable,
 139                    vec<histogram_entry *> &histogram,
 140                    gcov_type count, int time, int size)
 141 {
 142   histogram_entry key = {count, 0, 0};
 143   histogram_entry **val = hashtable->find_slot (&key, INSERT);
 144
 145   if (!*val)
 146     {
 147       *val = (histogram_entry *) pool_alloc (histogram_pool);
 148       **val = key;
 149       histogram.safe_push (*val);
 150     }
 151   (*val)->time += time;
 152   (*val)->size += size;
 153 }
 154
 155 int
 156 cmp_counts (const void *v1, const void *v2)
 157 {
 158   const histogram_entry *h1 = *(const histogram_entry * const *)v1;
 159   const histogram_entry *h2 = *(const histogram_entry * const *)v2;
 160   if (h1->count < h2->count)
 161     return 1;
 162   if (h1->count > h2->count)
 163     return -1;
 164   return 0;
 165 }
 166
 167 /* Dump HISTOGRAM to FILE.  */
 168
 169 static void
 170 dump_histogram (FILE *file, vec<histogram_entry *> histogram)
 171 {
 172   unsigned int i;
 173   gcov_type overall_time = 0, cumulated_time = 0, cumulated_size = 0, overall_size = 0;
 174
 175   fprintf (dump_file, "Histogram:\n");
 176   for (i = 0; i < histogram.length (); i++)
 177     {
 178       overall_time += histogram[i]->count * histogram[i]->time;
 179       overall_size += histogram[i]->size;
 180     }
 181   if (!overall_time)
 182     overall_time = 1;
 183   if (!overall_size)
 184     overall_size = 1;
 185   for (i = 0; i < histogram.length (); i++)
 186     {
 187       cumulated_time += histogram[i]->count * histogram[i]->time;
 188       cumulated_size += histogram[i]->size;
 189       fprintf (file, "  %"PRId64": time:%i (%2.2f) size:%i (%2.2f)\n",
 190                (int64_t) histogram[i]->count,
 191                histogram[i]->time,
 192                cumulated_time * 100.0 / overall_time,
 193                histogram[i]->size,
 194                cumulated_size * 100.0 / overall_size);
 195    }
 196 }
 197
 198 /* Collect histogram from CFG profiles.  */
 199
 200 static void
 201 ipa_profile_generate_summary (void)
 202 {
 203   struct cgraph_node *node;
 204   gimple_stmt_iterator gsi;
 205   basic_block bb;
 206
 207   hash_table<histogram_hash> hashtable (10);
 208   histogram_pool = create_alloc_pool ("IPA histogram", sizeof (struct histogram_entry),
 209                                       10);
 210
 211   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
 212     FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 213       {
 214         int time = 0;
 215         int size = 0;
 216         for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 217           {
 218             gimple stmt = gsi_stmt (gsi);
 219             if (gimple_code (stmt) == GIMPLE_CALL
 220                 && !gimple_call_fndecl (stmt))
 221               {
 222                 histogram_value h;
 223                 h = gimple_histogram_value_of_type
 224                       (DECL_STRUCT_FUNCTION (node->decl),
 225                        stmt, HIST_TYPE_INDIR_CALL);
 226                 /* No need to do sanity check: gimple_ic_transform already
 227                    takes away bad histograms.  */
 228                 if (h)
 229                   {
 230                     /* counter 0 is target, counter 1 is number of execution we called target,
 231                        counter 2 is total number of executions.  */
 232                     if (h->hvalue.counters[2])
 233                       {
 234                         struct cgraph_edge * e = node->get_edge (stmt);
 235                         if (e && !e->indirect_unknown_callee)
 236                           continue;
 237                         e->indirect_info->common_target_id
 238                           = h->hvalue.counters [0];
 239                         e->indirect_info->common_target_probability
 240                           = GCOV_COMPUTE_SCALE (h->hvalue.counters [1], h->hvalue.counters [2]);
 241                         if (e->indirect_info->common_target_probability > REG_BR_PROB_BASE)
 242                           {
 243                             if (dump_file)
 244                               fprintf (dump_file, "Probability capped to 1\n");
 245                             e->indirect_info->common_target_probability = REG_BR_PROB_BASE;
 246                           }
 247                       }
 248                     gimple_remove_histogram_value (DECL_STRUCT_FUNCTION (node->decl),
 249                                                     stmt, h);
 250                   }
 251               }
 252             time += estimate_num_insns (stmt, &eni_time_weights);
 253             size += estimate_num_insns (stmt, &eni_size_weights);
 254           }
 255         account_time_size (&hashtable, histogram, bb->count, time, size);
 256       }
 257   histogram.qsort (cmp_counts);
 258 }
 259
 260 /* Serialize the ipa info for lto.  */
 261
 262 static void
 263 ipa_profile_write_summary (void)
 264 {
 265   struct lto_simple_output_block *ob
 266     = lto_create_simple_output_block (LTO_section_ipa_profile);
 267   unsigned int i;
 268
 269   streamer_write_uhwi_stream (ob->main_stream, histogram.length ());
 270   for (i = 0; i < histogram.length (); i++)
 271     {
 272       streamer_write_gcov_count_stream (ob->main_stream, histogram[i]->count);
 273       streamer_write_uhwi_stream (ob->main_stream, histogram[i]->time);
 274       streamer_write_uhwi_stream (ob->main_stream, histogram[i]->size);
 275     }
 276   lto_destroy_simple_output_block (ob);
 277 }
 278
 279 /* Deserialize the ipa info for lto.  */
 280
 281 static void
 282 ipa_profile_read_summary (void)
 283 {
 284   struct lto_file_decl_data ** file_data_vec
 285     = lto_get_file_decl_data ();
 286   struct lto_file_decl_data * file_data;
 287   int j = 0;
 288
 289   hash_table<histogram_hash> hashtable (10);
 290   histogram_pool = create_alloc_pool ("IPA histogram", sizeof (struct histogram_entry),
 291                                       10);
 292
 293   while ((file_data = file_data_vec[j++]))
 294     {
 295       const char *data;
 296       size_t len;
 297       struct lto_input_block *ib
 298         = lto_create_simple_input_block (file_data,
 299                                          LTO_section_ipa_profile,
 300                                          &data, &len);
 301       if (ib)
 302         {
 303           unsigned int num = streamer_read_uhwi (ib);
 304           unsigned int n;
 305           for (n = 0; n < num; n++)
 306             {
 307               gcov_type count = streamer_read_gcov_count (ib);
 308               int time = streamer_read_uhwi (ib);
 309               int size = streamer_read_uhwi (ib);
 310               account_time_size (&hashtable, histogram,
 311                                  count, time, size);
 312             }
 313           lto_destroy_simple_input_block (file_data,
 314                                           LTO_section_ipa_profile,
 315                                           ib, data, len);
 316         }
 317     }
 318   histogram.qsort (cmp_counts);
 319 }
 320
 321 /* Data used by ipa_propagate_frequency.  */
 322
 323 struct ipa_propagate_frequency_data
 324 {
 325   bool maybe_unlikely_executed;
 326   bool maybe_executed_once;
 327   bool only_called_at_startup;
 328   bool only_called_at_exit;
 329 };
 330
 331 /* Worker for ipa_propagate_frequency_1.  */
 332
 333 static bool
 334 ipa_propagate_frequency_1 (struct cgraph_node *node, void *data)
 335 {
 336   struct ipa_propagate_frequency_data *d;
 337   struct cgraph_edge *edge;
 338
 339   d = (struct ipa_propagate_frequency_data *)data;
 340   for (edge = node->callers;
 341        edge && (d->maybe_unlikely_executed || d->maybe_executed_once
 342                 || d->only_called_at_startup || d->only_called_at_exit);
 343        edge = edge->next_caller)
 344     {
 345       if (edge->caller != node)
 346         {
 347           d->only_called_at_startup &= edge->caller->only_called_at_startup;
 348           /* It makes sense to put main() together with the static constructors.
 349              It will be executed for sure, but rest of functions called from
 350              main are definitely not at startup only.  */
 351           if (MAIN_NAME_P (DECL_NAME (edge->caller->decl)))
 352             d->only_called_at_startup = 0;
 353           d->only_called_at_exit &= edge->caller->only_called_at_exit;
 354         }
 355
 356       /* When profile feedback is available, do not try to propagate too hard;
 357          counts are already good guide on function frequencies and roundoff
 358          errors can make us to push function into unlikely section even when
 359          it is executed by the train run.  Transfer the function only if all
 360          callers are unlikely executed.  */
 361       if (profile_info && flag_branch_probabilities
 362           && (edge->caller->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED
 363               || (edge->caller->global.inlined_to
 364                   && edge->caller->global.inlined_to->frequency
 365                      != NODE_FREQUENCY_UNLIKELY_EXECUTED)))
 366           d->maybe_unlikely_executed = false;
 367       if (!edge->frequency)
 368         continue;
 369       switch (edge->caller->frequency)
 370         {
 371         case NODE_FREQUENCY_UNLIKELY_EXECUTED:
 372           break;
 373         case NODE_FREQUENCY_EXECUTED_ONCE:
 374           if (dump_file && (dump_flags & TDF_DETAILS))
 375             fprintf (dump_file, "  Called by %s that is executed once\n",
 376                      edge->caller->name ());
 377           d->maybe_unlikely_executed = false;
 378           if (inline_edge_summary (edge)->loop_depth)
 379             {
 380               d->maybe_executed_once = false;
 381               if (dump_file && (dump_flags & TDF_DETAILS))
 382                 fprintf (dump_file, "  Called in loop\n");
 383             }
 384           break;
 385         case NODE_FREQUENCY_HOT:
 386         case NODE_FREQUENCY_NORMAL:
 387           if (dump_file && (dump_flags & TDF_DETAILS))
 388             fprintf (dump_file, "  Called by %s that is normal or hot\n",
 389                      edge->caller->name ());
 390           d->maybe_unlikely_executed = false;
 391           d->maybe_executed_once = false;
 392           break;
 393         }
 394     }
 395   return edge != NULL;
 396 }
 397
 398 /* Return ture if NODE contains hot calls.  */
 399
 400 bool
 401 contains_hot_call_p (struct cgraph_node *node)
 402 {
 403   struct cgraph_edge *e;
 404   for (e = node->callees; e; e = e->next_callee)
 405     if (e->maybe_hot_p ())
 406       return true;
 407     else if (!e->inline_failed
 408              && contains_hot_call_p (e->callee))
 409       return true;
 410   for (e = node->indirect_calls; e; e = e->next_callee)
 411     if (e->maybe_hot_p ())
 412       return true;
 413   return false;
 414 }
 415
 416 /* See if the frequency of NODE can be updated based on frequencies of its
 417    callers.  */
 418 bool
 419 ipa_propagate_frequency (struct cgraph_node *node)
 420 {
 421   struct ipa_propagate_frequency_data d = {true, true, true, true};
 422   bool changed = false;
 423
 424   /* We can not propagate anything useful about externally visible functions
 425      nor about virtuals.  */
 426   if (!node->local.local
 427       || node->alias
 428       || (opt_for_fn (node->decl, flag_devirtualize)
 429           && DECL_VIRTUAL_P (node->decl)))
 430     return false;
 431   gcc_assert (node->analyzed);
 432   if (dump_file && (dump_flags & TDF_DETAILS))
 433     fprintf (dump_file, "Processing frequency %s\n", node->name ());
 434
 435   node->call_for_symbol_thunks_and_aliases (ipa_propagate_frequency_1, &d,
 436                                             true);
 437
 438   if ((d.only_called_at_startup && !d.only_called_at_exit)
 439       && !node->only_called_at_startup)
 440     {
 441        node->only_called_at_startup = true;
 442        if (dump_file)
 443          fprintf (dump_file, "Node %s promoted to only called at startup.\n",
 444                   node->name ());
 445        changed = true;
 446     }
 447   if ((d.only_called_at_exit && !d.only_called_at_startup)
 448       && !node->only_called_at_exit)
 449     {
 450        node->only_called_at_exit = true;
 451        if (dump_file)
 452          fprintf (dump_file, "Node %s promoted to only called at exit.\n",
 453                   node->name ());
 454        changed = true;
 455     }
 456
 457   /* With profile we can decide on hot/normal based on count.  */
 458   if (node->count)
 459     {
 460       bool hot = false;
 461       if (node->count >= get_hot_bb_threshold ())
 462         hot = true;
 463       if (!hot)
 464         hot |= contains_hot_call_p (node);
 465       if (hot)
 466         {
 467           if (node->frequency != NODE_FREQUENCY_HOT)
 468             {
 469               if (dump_file)
 470                 fprintf (dump_file, "Node %s promoted to hot.\n",
 471                          node->name ());
 472               node->frequency = NODE_FREQUENCY_HOT;
 473               return true;
 474             }
 475           return false;
 476         }
 477       else if (node->frequency == NODE_FREQUENCY_HOT)
 478         {
 479           if (dump_file)
 480             fprintf (dump_file, "Node %s reduced to normal.\n",
 481                      node->name ());
 482           node->frequency = NODE_FREQUENCY_NORMAL;
 483           changed = true;
 484         }
 485     }
 486   /* These come either from profile or user hints; never update them.  */
 487   if (node->frequency == NODE_FREQUENCY_HOT
 488       || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
 489     return changed;
 490   if (d.maybe_unlikely_executed)
 491     {
 492       node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
 493       if (dump_file)
 494         fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
 495                  node->name ());
 496       changed = true;
 497     }
 498   else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
 499     {
 500       node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
 501       if (dump_file)
 502         fprintf (dump_file, "Node %s promoted to executed once.\n",
 503                  node->name ());
 504       changed = true;
 505     }
 506   return changed;
 507 }
 508
 509 /* Simple ipa profile pass propagating frequencies across the callgraph.  */
 510
 511 static unsigned int
 512 ipa_profile (void)
 513 {
 514   struct cgraph_node **order;
 515   struct cgraph_edge *e;
 516   int order_pos;
 517   bool something_changed = false;
 518   int i;
 519   gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0;
 520   struct cgraph_node *n,*n2;
 521   int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0;
 522   bool node_map_initialized = false;
 523
 524   if (dump_file)
 525     dump_histogram (dump_file, histogram);
 526   for (i = 0; i < (int)histogram.length (); i++)
 527     {
 528       overall_time += histogram[i]->count * histogram[i]->time;
 529       overall_size += histogram[i]->size;
 530     }
 531   if (overall_time)
 532     {
 533       gcov_type threshold;
 534
 535       gcc_assert (overall_size);
 536       if (dump_file)
 537         {
 538           gcov_type min, cumulated_time = 0, cumulated_size = 0;
 539
 540           fprintf (dump_file, "Overall time: %"PRId64"\n",
 541                    (int64_t)overall_time);
 542           min = get_hot_bb_threshold ();
 543           for (i = 0; i < (int)histogram.length () && histogram[i]->count >= min;
 544                i++)
 545             {
 546               cumulated_time += histogram[i]->count * histogram[i]->time;
 547               cumulated_size += histogram[i]->size;
 548             }
 549           fprintf (dump_file, "GCOV min count: %"PRId64
 550                    " Time:%3.2f%% Size:%3.2f%%\n",
 551                    (int64_t)min,
 552                    cumulated_time * 100.0 / overall_time,
 553                    cumulated_size * 100.0 / overall_size);
 554         }
 555       cutoff = (overall_time * PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE) + 500) / 1000;
 556       threshold = 0;
 557       for (i = 0; cumulated < cutoff; i++)
 558         {
 559           cumulated += histogram[i]->count * histogram[i]->time;
 560           threshold = histogram[i]->count;
 561         }
 562       if (!threshold)
 563         threshold = 1;
 564       if (dump_file)
 565         {
 566           gcov_type cumulated_time = 0, cumulated_size = 0;
 567
 568           for (i = 0;
 569                i < (int)histogram.length () && histogram[i]->count >= threshold;
 570                i++)
 571             {
 572               cumulated_time += histogram[i]->count * histogram[i]->time;
 573               cumulated_size += histogram[i]->size;
 574             }
 575           fprintf (dump_file, "Determined min count: %"PRId64
 576                    " Time:%3.2f%% Size:%3.2f%%\n",
 577                    (int64_t)threshold,
 578                    cumulated_time * 100.0 / overall_time,
 579                    cumulated_size * 100.0 / overall_size);
 580         }
 581       if (threshold > get_hot_bb_threshold ()
 582           || in_lto_p)
 583         {
 584           if (dump_file)
 585             fprintf (dump_file, "Threshold updated.\n");
 586           set_hot_bb_threshold (threshold);
 587         }
 588     }
 589   histogram.release ();
 590   free_alloc_pool (histogram_pool);
 591
 592   /* Produce speculative calls: we saved common traget from porfiling into
 593      e->common_target_id.  Now, at link time, we can look up corresponding
 594      function node and produce speculative call.  */
 595
 596   FOR_EACH_DEFINED_FUNCTION (n)
 597     {
 598       bool update = false;
 599
 600       for (e = n->indirect_calls; e; e = e->next_callee)
 601         {
 602           if (n->count)
 603             nindirect++;
 604           if (e->indirect_info->common_target_id)
 605             {
 606               if (!node_map_initialized)
 607                 init_node_map (false);
 608               node_map_initialized = true;
 609               ncommon++;
 610               n2 = find_func_by_profile_id (e->indirect_info->common_target_id);
 611               if (n2)
 612                 {
 613                   if (dump_file)
 614                     {
 615                       fprintf (dump_file, "Indirect call -> direct call from"
 616                                " other module %s/%i => %s/%i, prob %3.2f\n",
 617                                xstrdup_for_dump (n->name ()), n->order,
 618                                xstrdup_for_dump (n2->name ()), n2->order,
 619                                e->indirect_info->common_target_probability
 620                                / (float)REG_BR_PROB_BASE);
 621                     }
 622                   if (e->indirect_info->common_target_probability
 623                       < REG_BR_PROB_BASE / 2)
 624                     {
 625                       nuseless++;
 626                       if (dump_file)
 627                         fprintf (dump_file,
 628                                  "Not speculating: probability is too low.\n");
 629                     }
 630                   else if (!e->maybe_hot_p ())
 631                     {
 632                       nuseless++;
 633                       if (dump_file)
 634                         fprintf (dump_file,
 635                                  "Not speculating: call is cold.\n");
 636                     }
 637                   else if (n2->get_availability () <= AVAIL_INTERPOSABLE
 638                            && n2->can_be_discarded_p ())
 639                     {
 640                       nuseless++;
 641                       if (dump_file)
 642                         fprintf (dump_file,
 643                                  "Not speculating: target is overwritable "
 644                                  "and can be discarded.\n");
 645                     }
 646                   else
 647                     {
 648                       /* Target may be overwritable, but profile says that
 649                          control flow goes to this particular implementation
 650                          of N2.  Speculate on the local alias to allow inlining.
 651                        */
 652                       if (!n2->can_be_discarded_p ())
 653                         {
 654                           cgraph_node *alias;
 655                           alias = dyn_cast<cgraph_node *> (n2->noninterposable_alias ());
 656                           if (alias)
 657                             n2 = alias;
 658                         }
 659                       nconverted++;
 660                       e->make_speculative
 661                         (n2,
 662                          apply_scale (e->count,
 663                                       e->indirect_info->common_target_probability),
 664                          apply_scale (e->frequency,
 665                                       e->indirect_info->common_target_probability));
 666                       update = true;
 667                     }
 668                 }
 669               else
 670                 {
 671                   if (dump_file)
 672                     fprintf (dump_file, "Function with profile-id %i not found.\n",
 673                              e->indirect_info->common_target_id);
 674                   nunknown++;
 675                 }
 676             }
 677          }
 678        if (update)
 679          inline_update_overall_summary (n);
 680      }
 681   if (node_map_initialized)
 682     del_node_map ();
 683   if (dump_file && nindirect)
 684     fprintf (dump_file,
 685              "%i indirect calls trained.\n"
 686              "%i (%3.2f%%) have common target.\n"
 687              "%i (%3.2f%%) targets was not found.\n"
 688              "%i (%3.2f%%) speculations seems useless.\n"
 689              "%i (%3.2f%%) speculations produced.\n",
 690              nindirect,
 691              ncommon, ncommon * 100.0 / nindirect,
 692              nunknown, nunknown * 100.0 / nindirect,
 693              nuseless, nuseless * 100.0 / nindirect,
 694              nconverted, nconverted * 100.0 / nindirect);
 695
 696   order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
 697   order_pos = ipa_reverse_postorder (order);
 698   for (i = order_pos - 1; i >= 0; i--)
 699     {
 700       if (order[i]->local.local && ipa_propagate_frequency (order[i]))
 701         {
 702           for (e = order[i]->callees; e; e = e->next_callee)
 703             if (e->callee->local.local && !e->callee->aux)
 704               {
 705                 something_changed = true;
 706                 e->callee->aux = (void *)1;
 707               }
 708         }
 709       order[i]->aux = NULL;
 710     }
 711
 712   while (something_changed)
 713     {
 714       something_changed = false;
 715       for (i = order_pos - 1; i >= 0; i--)
 716         {
 717           if (order[i]->aux && ipa_propagate_frequency (order[i]))
 718             {
 719               for (e = order[i]->callees; e; e = e->next_callee)
 720                 if (e->callee->local.local && !e->callee->aux)
 721                   {
 722                     something_changed = true;
 723                     e->callee->aux = (void *)1;
 724                   }
 725             }
 726           order[i]->aux = NULL;
 727         }
 728     }
 729   free (order);
 730   return 0;
 731 }
 732
 733 namespace {
 734
 735 const pass_data pass_data_ipa_profile =
 736 {
 737   IPA_PASS, /* type */
 738   "profile_estimate", /* name */
 739   OPTGROUP_NONE, /* optinfo_flags */
 740   TV_IPA_PROFILE, /* tv_id */
 741   0, /* properties_required */
 742   0, /* properties_provided */
 743   0, /* properties_destroyed */
 744   0, /* todo_flags_start */
 745   0, /* todo_flags_finish */
 746 };
 747
 748 class pass_ipa_profile : public ipa_opt_pass_d
 749 {
 750 public:
 751   pass_ipa_profile (gcc::context *ctxt)
 752     : ipa_opt_pass_d (pass_data_ipa_profile, ctxt,
 753                       ipa_profile_generate_summary, /* generate_summary */
 754                       ipa_profile_write_summary, /* write_summary */
 755                       ipa_profile_read_summary, /* read_summary */
 756                       NULL, /* write_optimization_summary */
 757                       NULL, /* read_optimization_summary */
 758                       NULL, /* stmt_fixup */
 759                       0, /* function_transform_todo_flags_start */
 760                       NULL, /* function_transform */
 761                       NULL) /* variable_transform */
 762   {}
 763
 764   /* opt_pass methods: */
 765   virtual bool gate (function *) { return flag_ipa_profile || in_lto_p; }
 766   virtual unsigned int execute (function *) { return ipa_profile (); }
 767
 768 }; // class pass_ipa_profile
 769
 770 } // anon namespace
 771
 772 ipa_opt_pass_d *
 773 make_pass_ipa_profile (gcc::context *ctxt)
 774 {
 775   return new pass_ipa_profile (ctxt);
 776 }