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