contrib/gcc-8.0/gcc/ipa-profile.c

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