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