gcc/ipa-profile.c

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