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           {
 349             if (dump_file && (dump_flags & TDF_DETAILS))
 350               fprintf (dump_file, "  Called by %s that is executed once\n",
 351                        edge->caller->name ());
 352             d->maybe_unlikely_executed = false;
 353             ipa_call_summary *s = ipa_call_summaries->get (edge);
 354             if (s != NULL && s->loop_depth)
 355               {
 356                 d->maybe_executed_once = false;
 357                 if (dump_file && (dump_flags & TDF_DETAILS))
 358                   fprintf (dump_file, "  Called in loop\n");
 359               }
 360             break;
 361           }
 362         case NODE_FREQUENCY_HOT:
 363         case NODE_FREQUENCY_NORMAL:
 364           if (dump_file && (dump_flags & TDF_DETAILS))
 365             fprintf (dump_file, "  Called by %s that is normal or hot\n",
 366                      edge->caller->name ());
 367           d->maybe_unlikely_executed = false;
 368           d->maybe_executed_once = false;
 369           break;
 370         }
 371     }
 372   return edge != NULL;
 373 }
 374
 375 /* Return ture if NODE contains hot calls.  */
 376
 377 bool
 378 contains_hot_call_p (struct cgraph_node *node)
 379 {
 380   struct cgraph_edge *e;
 381   for (e = node->callees; e; e = e->next_callee)
 382     if (e->maybe_hot_p ())
 383       return true;
 384     else if (!e->inline_failed
 385              && contains_hot_call_p (e->callee))
 386       return true;
 387   for (e = node->indirect_calls; e; e = e->next_callee)
 388     if (e->maybe_hot_p ())
 389       return true;
 390   return false;
 391 }
 392
 393 /* See if the frequency of NODE can be updated based on frequencies of its
 394    callers.  */
 395 bool
 396 ipa_propagate_frequency (struct cgraph_node *node)
 397 {
 398   struct ipa_propagate_frequency_data d = {node, true, true, true, true};
 399   bool changed = false;
 400
 401   /* We can not propagate anything useful about externally visible functions
 402      nor about virtuals.  */
 403   if (!node->local.local
 404       || node->alias
 405       || (opt_for_fn (node->decl, flag_devirtualize)
 406           && DECL_VIRTUAL_P (node->decl)))
 407     return false;
 408   gcc_assert (node->analyzed);
 409   if (dump_file && (dump_flags & TDF_DETAILS))
 410     fprintf (dump_file, "Processing frequency %s\n", node->name ());
 411
 412   node->call_for_symbol_and_aliases (ipa_propagate_frequency_1, &d,
 413                                      true);
 414
 415   if ((d.only_called_at_startup && !d.only_called_at_exit)
 416       && !node->only_called_at_startup)
 417     {
 418        node->only_called_at_startup = true;
 419        if (dump_file)
 420          fprintf (dump_file, "Node %s promoted to only called at startup.\n",
 421                   node->name ());
 422        changed = true;
 423     }
 424   if ((d.only_called_at_exit && !d.only_called_at_startup)
 425       && !node->only_called_at_exit)
 426     {
 427        node->only_called_at_exit = true;
 428        if (dump_file)
 429          fprintf (dump_file, "Node %s promoted to only called at exit.\n",
 430                   node->name ());
 431        changed = true;
 432     }
 433
 434   /* With profile we can decide on hot/normal based on count.  */
 435   if (node->count. ipa().initialized_p ())
 436     {
 437       bool hot = false;
 438       if (!(node->count. ipa() == profile_count::zero ())
 439           && node->count. ipa() >= get_hot_bb_threshold ())
 440         hot = true;
 441       if (!hot)
 442         hot |= contains_hot_call_p (node);
 443       if (hot)
 444         {
 445           if (node->frequency != NODE_FREQUENCY_HOT)
 446             {
 447               if (dump_file)
 448                 fprintf (dump_file, "Node %s promoted to hot.\n",
 449                          node->name ());
 450               node->frequency = NODE_FREQUENCY_HOT;
 451               return true;
 452             }
 453           return false;
 454         }
 455       else if (node->frequency == NODE_FREQUENCY_HOT)
 456         {
 457           if (dump_file)
 458             fprintf (dump_file, "Node %s reduced to normal.\n",
 459                      node->name ());
 460           node->frequency = NODE_FREQUENCY_NORMAL;
 461           changed = true;
 462         }
 463     }
 464   /* These come either from profile or user hints; never update them.  */
 465   if (node->frequency == NODE_FREQUENCY_HOT
 466       || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
 467     return changed;
 468   if (d.maybe_unlikely_executed)
 469     {
 470       node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
 471       if (dump_file)
 472         fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
 473                  node->name ());
 474       changed = true;
 475     }
 476   else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
 477     {
 478       node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
 479       if (dump_file)
 480         fprintf (dump_file, "Node %s promoted to executed once.\n",
 481                  node->name ());
 482       changed = true;
 483     }
 484   return changed;
 485 }
 486
 487 /* Simple ipa profile pass propagating frequencies across the callgraph.  */
 488
 489 static unsigned int
 490 ipa_profile (void)
 491 {
 492   struct cgraph_node **order;
 493   struct cgraph_edge *e;
 494   int order_pos;
 495   bool something_changed = false;
 496   int i;
 497   gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0;
 498   struct cgraph_node *n,*n2;
 499   int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0;
 500   int nmismatch = 0, nimpossible = 0;
 501   bool node_map_initialized = false;
 502
 503   if (dump_file)
 504     dump_histogram (dump_file, histogram);
 505   for (i = 0; i < (int)histogram.length (); i++)
 506     {
 507       overall_time += histogram[i]->count * histogram[i]->time;
 508       overall_size += histogram[i]->size;
 509     }
 510   if (overall_time)
 511     {
 512       gcov_type threshold;
 513
 514       gcc_assert (overall_size);
 515       if (dump_file)
 516         {
 517           gcov_type min, cumulated_time = 0, cumulated_size = 0;
 518
 519           fprintf (dump_file, "Overall time: %" PRId64"\n",
 520                    (int64_t)overall_time);
 521           min = get_hot_bb_threshold ();
 522           for (i = 0; i < (int)histogram.length () && histogram[i]->count >= min;
 523                i++)
 524             {
 525               cumulated_time += histogram[i]->count * histogram[i]->time;
 526               cumulated_size += histogram[i]->size;
 527             }
 528           fprintf (dump_file, "GCOV min count: %" PRId64
 529                    " Time:%3.2f%% Size:%3.2f%%\n",
 530                    (int64_t)min,
 531                    cumulated_time * 100.0 / overall_time,
 532                    cumulated_size * 100.0 / overall_size);
 533         }
 534       cutoff = (overall_time * PARAM_VALUE (HOT_BB_COUNT_WS_PERMILLE) + 500) / 1000;
 535       threshold = 0;
 536       for (i = 0; cumulated < cutoff; i++)
 537         {
 538           cumulated += histogram[i]->count * histogram[i]->time;
 539           threshold = histogram[i]->count;
 540         }
 541       if (!threshold)
 542         threshold = 1;
 543       if (dump_file)
 544         {
 545           gcov_type cumulated_time = 0, cumulated_size = 0;
 546
 547           for (i = 0;
 548                i < (int)histogram.length () && histogram[i]->count >= threshold;
 549                i++)
 550             {
 551               cumulated_time += histogram[i]->count * histogram[i]->time;
 552               cumulated_size += histogram[i]->size;
 553             }
 554           fprintf (dump_file, "Determined min count: %" PRId64
 555                    " Time:%3.2f%% Size:%3.2f%%\n",
 556                    (int64_t)threshold,
 557                    cumulated_time * 100.0 / overall_time,
 558                    cumulated_size * 100.0 / overall_size);
 559         }
 560       if (threshold > get_hot_bb_threshold ()
 561           || in_lto_p)
 562         {
 563           if (dump_file)
 564             fprintf (dump_file, "Threshold updated.\n");
 565           set_hot_bb_threshold (threshold);
 566         }
 567     }
 568   histogram.release ();
 569   histogram_pool.release ();
 570
 571   /* Produce speculative calls: we saved common traget from porfiling into
 572      e->common_target_id.  Now, at link time, we can look up corresponding
 573      function node and produce speculative call.  */
 574
 575   FOR_EACH_DEFINED_FUNCTION (n)
 576     {
 577       bool update = false;
 578
 579       if (!opt_for_fn (n->decl, flag_ipa_profile))
 580         continue;
 581
 582       for (e = n->indirect_calls; e; e = e->next_callee)
 583         {
 584           if (n->count.initialized_p ())
 585             nindirect++;
 586           if (e->indirect_info->common_target_id)
 587             {
 588               if (!node_map_initialized)
 589                 init_node_map (false);
 590               node_map_initialized = true;
 591               ncommon++;
 592               n2 = find_func_by_profile_id (e->indirect_info->common_target_id);
 593               if (n2)
 594                 {
 595                   if (dump_file)
 596                     {
 597                       fprintf (dump_file, "Indirect call -> direct call from"
 598                                " other module %s => %s, prob %3.2f\n",
 599                                n->dump_name (),
 600                                n2->dump_name (),
 601                                e->indirect_info->common_target_probability
 602                                / (float)REG_BR_PROB_BASE);
 603                     }
 604                   if (e->indirect_info->common_target_probability
 605                       < REG_BR_PROB_BASE / 2)
 606                     {
 607                       nuseless++;
 608                       if (dump_file)
 609                         fprintf (dump_file,
 610                                  "Not speculating: probability is too low.\n");
 611                     }
 612                   else if (!e->maybe_hot_p ())
 613                     {
 614                       nuseless++;
 615                       if (dump_file)
 616                         fprintf (dump_file,
 617                                  "Not speculating: call is cold.\n");
 618                     }
 619                   else if (n2->get_availability () <= AVAIL_INTERPOSABLE
 620                            && n2->can_be_discarded_p ())
 621                     {
 622                       nuseless++;
 623                       if (dump_file)
 624                         fprintf (dump_file,
 625                                  "Not speculating: target is overwritable "
 626                                  "and can be discarded.\n");
 627                     }
 628                   else if (ipa_node_params_sum && ipa_edge_args_sum
 629                            && (!vec_safe_is_empty
 630                                (IPA_NODE_REF (n2)->descriptors))
 631                            && ipa_get_param_count (IPA_NODE_REF (n2))
 632                               != ipa_get_cs_argument_count (IPA_EDGE_REF (e))
 633                             && (ipa_get_param_count (IPA_NODE_REF (n2))
 634                                 >= ipa_get_cs_argument_count (IPA_EDGE_REF (e))
 635                                 || !stdarg_p (TREE_TYPE (n2->decl))))
 636                     {
 637                       nmismatch++;
 638                       if (dump_file)
 639                         fprintf (dump_file,
 640                                  "Not speculating: "
 641                                  "parameter count mistmatch\n");
 642                     }
 643                   else if (e->indirect_info->polymorphic
 644                            && !opt_for_fn (n->decl, flag_devirtualize)
 645                            && !possible_polymorphic_call_target_p (e, n2))
 646                     {
 647                       nimpossible++;
 648                       if (dump_file)
 649                         fprintf (dump_file,
 650                                  "Not speculating: "
 651                                  "function is not in the polymorphic "
 652                                  "call target list\n");
 653                     }
 654                   else
 655                     {
 656                       /* Target may be overwritable, but profile says that
 657                          control flow goes to this particular implementation
 658                          of N2.  Speculate on the local alias to allow inlining.
 659                        */
 660                       if (!n2->can_be_discarded_p ())
 661                         {
 662                           cgraph_node *alias;
 663                           alias = dyn_cast<cgraph_node *> (n2->noninterposable_alias ());
 664                           if (alias)
 665                             n2 = alias;
 666                         }
 667                       nconverted++;
 668                       e->make_speculative
 669                         (n2,
 670                          e->count.apply_probability
 671                                      (e->indirect_info->common_target_probability));
 672                       update = true;
 673                     }
 674                 }
 675               else
 676                 {
 677                   if (dump_file)
 678                     fprintf (dump_file, "Function with profile-id %i not found.\n",
 679                              e->indirect_info->common_target_id);
 680                   nunknown++;
 681                 }
 682             }
 683          }
 684        if (update)
 685          ipa_update_overall_fn_summary (n);
 686      }
 687   if (node_map_initialized)
 688     del_node_map ();
 689   if (dump_file && nindirect)
 690     fprintf (dump_file,
 691              "%i indirect calls trained.\n"
 692              "%i (%3.2f%%) have common target.\n"
 693              "%i (%3.2f%%) targets was not found.\n"
 694              "%i (%3.2f%%) targets had parameter count mismatch.\n"
 695              "%i (%3.2f%%) targets was not in polymorphic call target list.\n"
 696              "%i (%3.2f%%) speculations seems useless.\n"
 697              "%i (%3.2f%%) speculations produced.\n",
 698              nindirect,
 699              ncommon, ncommon * 100.0 / nindirect,
 700              nunknown, nunknown * 100.0 / nindirect,
 701              nmismatch, nmismatch * 100.0 / nindirect,
 702              nimpossible, nimpossible * 100.0 / nindirect,
 703              nuseless, nuseless * 100.0 / nindirect,
 704              nconverted, nconverted * 100.0 / nindirect);
 705
 706   order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
 707   order_pos = ipa_reverse_postorder (order);
 708   for (i = order_pos - 1; i >= 0; i--)
 709     {
 710       if (order[i]->local.local
 711           && opt_for_fn (order[i]->decl, flag_ipa_profile)
 712           && ipa_propagate_frequency (order[i]))
 713         {
 714           for (e = order[i]->callees; e; e = e->next_callee)
 715             if (e->callee->local.local && !e->callee->aux)
 716               {
 717                 something_changed = true;
 718                 e->callee->aux = (void *)1;
 719               }
 720         }
 721       order[i]->aux = NULL;
 722     }
 723
 724   while (something_changed)
 725     {
 726       something_changed = false;
 727       for (i = order_pos - 1; i >= 0; i--)
 728         {
 729           if (order[i]->aux
 730               && opt_for_fn (order[i]->decl, flag_ipa_profile)
 731               && ipa_propagate_frequency (order[i]))
 732             {
 733               for (e = order[i]->callees; e; e = e->next_callee)
 734                 if (e->callee->local.local && !e->callee->aux)
 735                   {
 736                     something_changed = true;
 737                     e->callee->aux = (void *)1;
 738                   }
 739             }
 740           order[i]->aux = NULL;
 741         }
 742     }
 743   free (order);
 744   return 0;
 745 }
 746
 747 namespace {
 748
 749 const pass_data pass_data_ipa_profile =
 750 {
 751   IPA_PASS, /* type */
 752   "profile_estimate", /* name */
 753   OPTGROUP_NONE, /* optinfo_flags */
 754   TV_IPA_PROFILE, /* tv_id */
 755   0, /* properties_required */
 756   0, /* properties_provided */
 757   0, /* properties_destroyed */
 758   0, /* todo_flags_start */
 759   0, /* todo_flags_finish */
 760 };
 761
 762 class pass_ipa_profile : public ipa_opt_pass_d
 763 {
 764 public:
 765   pass_ipa_profile (gcc::context *ctxt)
 766     : ipa_opt_pass_d (pass_data_ipa_profile, ctxt,
 767                       ipa_profile_generate_summary, /* generate_summary */
 768                       ipa_profile_write_summary, /* write_summary */
 769                       ipa_profile_read_summary, /* read_summary */
 770                       NULL, /* write_optimization_summary */
 771                       NULL, /* read_optimization_summary */
 772                       NULL, /* stmt_fixup */
 773                       0, /* function_transform_todo_flags_start */
 774                       NULL, /* function_transform */
 775                       NULL) /* variable_transform */
 776   {}
 777
 778   /* opt_pass methods: */
 779   virtual bool gate (function *) { return flag_ipa_profile || in_lto_p; }
 780   virtual unsigned int execute (function *) { return ipa_profile (); }
 781
 782 }; // class pass_ipa_profile
 783
 784 } // anon namespace
 785
 786 ipa_opt_pass_d *
 787 make_pass_ipa_profile (gcc::context *ctxt)
 788 {
 789   return new pass_ipa_profile (ctxt);
 790 }