gcc/ipa-profile.c

   1 /* Basic IPA optimizations based on profile.
   2    Copyright (C) 2003-2014 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 complette only with LTO,
  26      otherwise it contains information only about the current unit.
  27
  28      Similar histogram is also estimated by coverage runtime.  This histogram
  29      is not dependent on LTO, but it suffers from various defects; first
  30      gcov runtime is not weighting individual basic block by estimated execution
  31      time and second the merging of multiple runs makes assumption that the
  32      histogram distribution did not change.  Consequentely histogram constructed
  33      here may be more precise.
  34
  35      The information is used to set hot/cold thresholds.
  36    - Next speculative indirect call resolution is performed:  the local
  37      profile pass assigns profile-id to each function and provide us with a
  38      histogram specifying the most common target.  We look up the callgraph
  39      node corresponding to the target and produce a speculative call.
  40
  41      This call may or may not survive through IPA optimization based on decision
  42      of inliner.
  43    - Finally we propagate the following flags: unlikely executed, executed
  44      once, executed at startup and executed at exit.  These flags are used to
  45      control code size/performance threshold and and code placement (by producing
  46      .text.unlikely/.text.hot/.text.startup/.text.exit subsections).  */
  47 #include "config.h"
  48 #include "system.h"
  49 #include "coretypes.h"
  50 #include "tm.h"
  51 #include "tree.h"
  52 #include "cgraph.h"
  53 #include "tree-pass.h"
  54 #include "tree-ssa-alias.h"
  55 #include "internal-fn.h"
  56 #include "gimple-expr.h"
  57 #include "gimple.h"
  58 #include "gimple-iterator.h"
  59 #include "flags.h"
  60 #include "target.h"
  61 #include "tree-iterator.h"
  62 #include "ipa-utils.h"
  63 #include "profile.h"
  64 #include "params.h"
  65 #include "value-prof.h"
  66 #include "alloc-pool.h"
  67 #include "tree-inline.h"
  68 #include "lto-streamer.h"
  69 #include "data-streamer.h"
  70 #include "ipa-inline.h"
  71
  72 /* Entry in the histogram.  */
  73
  74 struct histogram_entry
  75 {
  76   gcov_type count;
  77   int time;
  78   int size;
  79 };
  80
  81 /* Histogram of profile values.
  82    The histogram is represented as an ordered vector of entries allocated via
  83    histogram_pool. During construction a separate hashtable is kept to lookup
  84    duplicate entries.  */
  85
  86 vec<histogram_entry *> histogram;
  87 static alloc_pool histogram_pool;
  88
  89 /* Hashtable support for storing SSA names hashed by their SSA_NAME_VAR.  */
  90
  91 struct histogram_hash : typed_noop_remove <histogram_entry>
  92 {
  93   typedef histogram_entry value_type;
  94   typedef histogram_entry compare_type;
  95   static inline hashval_t hash (const value_type *);
  96   static inline int equal (const value_type *, const compare_type *);
  97 };
  98
  99 inline hashval_t
 100 histogram_hash::hash (const histogram_entry *val)
 101 {
 102   return val->count;
 103 }
 104
 105 inline int
 106 histogram_hash::equal (const histogram_entry *val, const histogram_entry *val2)
 107 {
 108   return val->count == val2->count;
 109 }
 110
 111 /* Account TIME and SIZE executed COUNT times into HISTOGRAM.
 112    HASHTABLE is the on-side hash kept to avoid duplicates.  */
 113
 114 static void
 115 account_time_size (hash_table <histogram_hash> hashtable,
 116                    vec<histogram_entry *> &histogram,
 117                    gcov_type count, int time, int size)
 118 {
 119   histogram_entry key = {count, 0, 0};
 120   histogram_entry **val = hashtable.find_slot (&key, INSERT);
 121
 122   if (!*val)
 123     {
 124       *val = (histogram_entry *) pool_alloc (histogram_pool);
 125       **val = key;
 126       histogram.safe_push (*val);
 127     }
 128   (*val)->time += time;
 129   (*val)->size += size;
 130 }
 131
 132 int
 133 cmp_counts (const void *v1, const void *v2)
 134 {
 135   const histogram_entry *h1 = *(const histogram_entry * const *)v1;
 136   const histogram_entry *h2 = *(const histogram_entry * const *)v2;
 137   if (h1->count < h2->count)
 138     return 1;
 139   if (h1->count > h2->count)
 140     return -1;
 141   return 0;
 142 }
 143
 144 /* Dump HISTOGRAM to FILE.  */
 145
 146 static void
 147 dump_histogram (FILE *file, vec<histogram_entry *> histogram)
 148 {
 149   unsigned int i;
 150   gcov_type overall_time = 0, cumulated_time = 0, cumulated_size = 0, overall_size = 0;
 151
 152   fprintf (dump_file, "Histogram:\n");
 153   for (i = 0; i < histogram.length (); i++)
 154     {
 155       overall_time += histogram[i]->count * histogram[i]->time;
 156       overall_size += histogram[i]->size;
 157     }
 158   if (!overall_time)
 159     overall_time = 1;
 160   if (!overall_size)
 161     overall_size = 1;
 162   for (i = 0; i < histogram.length (); i++)
 163     {
 164       cumulated_time += histogram[i]->count * histogram[i]->time;
 165       cumulated_size += histogram[i]->size;
 166       fprintf (file, "  %"PRId64": time:%i (%2.2f) size:%i (%2.2f)\n",
 167                (int64_t) histogram[i]->count,
 168                histogram[i]->time,
 169                cumulated_time * 100.0 / overall_time,
 170                histogram[i]->size,
 171                cumulated_size * 100.0 / overall_size);
 172    }
 173 }
 174
 175 /* Collect histogram from CFG profiles.  */
 176
 177 static void
 178 ipa_profile_generate_summary (void)
 179 {
 180   struct cgraph_node *node;
 181   gimple_stmt_iterator gsi;
 182   hash_table <histogram_hash> hashtable;
 183   basic_block bb;
 184
 185   hashtable.create (10);
 186   histogram_pool = create_alloc_pool ("IPA histogram", sizeof (struct histogram_entry),
 187                                       10);
 188
 189   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
 190     FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 191       {
 192         int time = 0;
 193         int size = 0;
 194         for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 195           {
 196             gimple stmt = gsi_stmt (gsi);
 197             if (gimple_code (stmt) == GIMPLE_CALL
 198                 && !gimple_call_fndecl (stmt))
 199               {
 200                 histogram_value h;
 201                 h = gimple_histogram_value_of_type
 202                       (DECL_STRUCT_FUNCTION (node->decl),
 203                        stmt, HIST_TYPE_INDIR_CALL);
 204                 /* No need to do sanity check: gimple_ic_transform already
 205                    takes away bad histograms.  */
 206                 if (h)
 207                   {
 208                     /* counter 0 is target, counter 1 is number of execution we called target,
 209                        counter 2 is total number of executions.  */
 210                     if (h->hvalue.counters[2])
 211                       {
 212                         struct cgraph_edge * e = cgraph_edge (node, stmt);
 213                         if (e && !e->indirect_unknown_callee)
 214                           continue;
 215                         e->indirect_info->common_target_id
 216                           = h->hvalue.counters [0];
 217                         e->indirect_info->common_target_probability
 218                           = GCOV_COMPUTE_SCALE (h->hvalue.counters [1], h->hvalue.counters [2]);
 219                         if (e->indirect_info->common_target_probability > REG_BR_PROB_BASE)
 220                           {
 221                             if (dump_file)
 222                               fprintf (dump_file, "Probability capped to 1\n");
 223                             e->indirect_info->common_target_probability = REG_BR_PROB_BASE;
 224                           }
 225                       }
 226                     gimple_remove_histogram_value (DECL_STRUCT_FUNCTION (node->decl),
 227                                                     stmt, h);
 228                   }
 229               }
 230             time += estimate_num_insns (stmt, &eni_time_weights);
 231             size += estimate_num_insns (stmt, &eni_size_weights);
 232           }
 233         account_time_size (hashtable, histogram, bb->count, time, size);
 234       }
 235   hashtable.dispose ();
 236   histogram.qsort (cmp_counts);
 237 }
 238
 239 /* Serialize the ipa info for lto.  */
 240
 241 static void
 242 ipa_profile_write_summary (void)
 243 {
 244   struct lto_simple_output_block *ob
 245     = lto_create_simple_output_block (LTO_section_ipa_profile);
 246   unsigned int i;
 247
 248   streamer_write_uhwi_stream (ob->main_stream, histogram.length ());
 249   for (i = 0; i < histogram.length (); i++)
 250     {
 251       streamer_write_gcov_count_stream (ob->main_stream, histogram[i]->count);
 252       streamer_write_uhwi_stream (ob->main_stream, histogram[i]->time);
 253       streamer_write_uhwi_stream (ob->main_stream, histogram[i]->size);
 254     }
 255   lto_destroy_simple_output_block (ob);
 256 }
 257
 258 /* Deserialize the ipa info for lto.  */
 259
 260 static void
 261 ipa_profile_read_summary (void)
 262 {
 263   struct lto_file_decl_data ** file_data_vec
 264     = lto_get_file_decl_data ();
 265   struct lto_file_decl_data * file_data;
 266   hash_table <histogram_hash> hashtable;
 267   int j = 0;
 268
 269   hashtable.create (10);
 270   histogram_pool = create_alloc_pool ("IPA histogram", sizeof (struct histogram_entry),
 271                                       10);
 272
 273   while ((file_data = file_data_vec[j++]))
 274     {
 275       const char *data;
 276       size_t len;
 277       struct lto_input_block *ib
 278         = lto_create_simple_input_block (file_data,
 279                                          LTO_section_ipa_profile,
 280                                          &data, &len);
 281       if (ib)
 282         {
 283           unsigned int num = streamer_read_uhwi (ib);
 284           unsigned int n;
 285           for (n = 0; n < num; n++)
 286             {
 287               gcov_type count = streamer_read_gcov_count (ib);
 288               int time = streamer_read_uhwi (ib);
 289               int size = streamer_read_uhwi (ib);
 290               account_time_size (hashtable, histogram,
 291                                  count, time, size);
 292             }
 293           lto_destroy_simple_input_block (file_data,
 294                                           LTO_section_ipa_profile,
 295                                           ib, data, len);
 296         }
 297     }
 298   hashtable.dispose ();
 299   histogram.qsort (cmp_counts);
 300 }
 301
 302 /* Data used by ipa_propagate_frequency.  */
 303
 304 struct ipa_propagate_frequency_data
 305 {
 306   bool maybe_unlikely_executed;
 307   bool maybe_executed_once;
 308   bool only_called_at_startup;
 309   bool only_called_at_exit;
 310 };
 311
 312 /* Worker for ipa_propagate_frequency_1.  */
 313
 314 static bool
 315 ipa_propagate_frequency_1 (struct cgraph_node *node, void *data)
 316 {
 317   struct ipa_propagate_frequency_data *d;
 318   struct cgraph_edge *edge;
 319
 320   d = (struct ipa_propagate_frequency_data *)data;
 321   for (edge = node->callers;
 322        edge && (d->maybe_unlikely_executed || d->maybe_executed_once
 323                 || d->only_called_at_startup || d->only_called_at_exit);
 324        edge = edge->next_caller)
 325     {
 326       if (edge->caller != node)
 327         {
 328           d->only_called_at_startup &= edge->caller->only_called_at_startup;
 329           /* It makes sense to put main() together with the static constructors.
 330              It will be executed for sure, but rest of functions called from
 331              main are definitely not at startup only.  */
 332           if (MAIN_NAME_P (DECL_NAME (edge->caller->decl)))
 333             d->only_called_at_startup = 0;
 334           d->only_called_at_exit &= edge->caller->only_called_at_exit;
 335         }
 336
 337       /* When profile feedback is available, do not try to propagate too hard;
 338          counts are already good guide on function frequencies and roundoff
 339          errors can make us to push function into unlikely section even when
 340          it is executed by the train run.  Transfer the function only if all
 341          callers are unlikely executed.  */
 342       if (profile_info && flag_branch_probabilities
 343           && (edge->caller->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED
 344               || (edge->caller->global.inlined_to
 345                   && edge->caller->global.inlined_to->frequency
 346                      != NODE_FREQUENCY_UNLIKELY_EXECUTED)))
 347           d->maybe_unlikely_executed = false;
 348       if (!edge->frequency)
 349         continue;
 350       switch (edge->caller->frequency)
 351         {
 352         case NODE_FREQUENCY_UNLIKELY_EXECUTED:
 353           break;
 354         case NODE_FREQUENCY_EXECUTED_ONCE:
 355           if (dump_file && (dump_flags & TDF_DETAILS))
 356             fprintf (dump_file, "  Called by %s that is executed once\n",
 357                      edge->caller->name ());
 358           d->maybe_unlikely_executed = false;
 359           if (inline_edge_summary (edge)->loop_depth)
 360             {
 361               d->maybe_executed_once = false;
 362               if (dump_file && (dump_flags & TDF_DETAILS))
 363                 fprintf (dump_file, "  Called in loop\n");
 364             }
 365           break;
 366         case NODE_FREQUENCY_HOT:
 367         case NODE_FREQUENCY_NORMAL:
 368           if (dump_file && (dump_flags & TDF_DETAILS))
 369             fprintf (dump_file, "  Called by %s that is normal or hot\n",
 370                      edge->caller->name ());
 371           d->maybe_unlikely_executed = false;
 372           d->maybe_executed_once = false;
 373           break;
 374         }
 375     }
 376   return edge != NULL;
 377 }
 378
 379 /* Return ture if NODE contains hot calls.  */
 380
 381 bool
 382 contains_hot_call_p (struct cgraph_node *node)
 383 {
 384   struct cgraph_edge *e;
 385   for (e = node->callees; e; e = e->next_callee)
 386     if (cgraph_maybe_hot_edge_p (e))
 387       return true;
 388     else if (!e->inline_failed
 389              && contains_hot_call_p (e->callee))
 390       return true;
 391   for (e = node->indirect_calls; e; e = e->next_callee)
 392     if (cgraph_maybe_hot_edge_p (e))
 393       return true;
 394   return false;
 395 }
 396
 397 /* See if the frequency of NODE can be updated based on frequencies of its
 398    callers.  */
 399 bool
 400 ipa_propagate_frequency (struct cgraph_node *node)
 401 {
 402   struct ipa_propagate_frequency_data d = {true, true, true, true};
 403   bool changed = false;
 404
 405   /* We can not propagate anything useful about externally visible functions
 406      nor about virtuals.  */
 407   if (!node->local.local
 408       || node->alias
 409       || (flag_devirtualize && DECL_VIRTUAL_P (node->decl)))
 410     return false;
 411   gcc_assert (node->analyzed);
 412   if (dump_file && (dump_flags & TDF_DETAILS))
 413     fprintf (dump_file, "Processing frequency %s\n", node->name ());
 414
 415   cgraph_for_node_and_aliases (node, ipa_propagate_frequency_1, &d, true);
 416
 417   if ((d.only_called_at_startup && !d.only_called_at_exit)
 418       && !node->only_called_at_startup)
 419     {
 420        node->only_called_at_startup = true;
 421        if (dump_file)
 422          fprintf (dump_file, "Node %s promoted to only called at startup.\n",
 423                   node->name ());
 424        changed = true;
 425     }
 426   if ((d.only_called_at_exit && !d.only_called_at_startup)
 427       && !node->only_called_at_exit)
 428     {
 429        node->only_called_at_exit = true;
 430        if (dump_file)
 431          fprintf (dump_file, "Node %s promoted to only called at exit.\n",
 432                   node->name ());
 433        changed = true;
 434     }
 435
 436   /* With profile we can decide on hot/normal based on count.  */
 437   if (node->count)
 438     {
 439       bool hot = false;
 440       if (node->count >= get_hot_bb_threshold ())
 441         hot = true;
 442       if (!hot)
 443         hot |= contains_hot_call_p (node);
 444       if (hot)
 445         {
 446           if (node->frequency != NODE_FREQUENCY_HOT)
 447             {
 448               if (dump_file)
 449                 fprintf (dump_file, "Node %s promoted to hot.\n",
 450                          node->name ());
 451               node->frequency = NODE_FREQUENCY_HOT;
 452               return true;
 453             }
 454           return false;
 455         }
 456       else if (node->frequency == NODE_FREQUENCY_HOT)
 457         {
 458           if (dump_file)
 459             fprintf (dump_file, "Node %s reduced to normal.\n",
 460                      node->name ());
 461           node->frequency = NODE_FREQUENCY_NORMAL;
 462           changed = true;
 463         }
 464     }
 465   /* These come either from profile or user hints; never update them.  */
 466   if (node->frequency == NODE_FREQUENCY_HOT
 467       || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
 468     return changed;
 469   if (d.maybe_unlikely_executed)
 470     {
 471       node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
 472       if (dump_file)
 473         fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
 474                  node->name ());
 475       changed = true;
 476     }
 477   else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
 478     {
 479       node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
 480       if (dump_file)
 481         fprintf (dump_file, "Node %s promoted to executed once.\n",
 482                  node->name ());
 483       changed = true;
 484     }
 485   return changed;
 486 }
 487
 488 /* Simple ipa profile pass propagating frequencies across the callgraph.  */
 489
 490 static unsigned int
 491 ipa_profile (void)
 492 {
 493   struct cgraph_node **order;
 494   struct cgraph_edge *e;
 495   int order_pos;
 496   bool something_changed = false;
 497   int i;
 498   gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0;
 499   struct cgraph_node *n,*n2;
 500   int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 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   free_alloc_pool (histogram_pool);
 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       for (e = n->indirect_calls; e; e = e->next_callee)
 580         {
 581           if (n->count)
 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/%i => %s/%i, prob %3.2f\n",
 596                                xstrdup (n->name ()), n->order,
 597                                xstrdup (n2->name ()), n2->order,
 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 (!cgraph_maybe_hot_edge_p (e))
 610                     {
 611                       nuseless++;
 612                       if (dump_file)
 613                         fprintf (dump_file,
 614                                  "Not speculating: call is cold.\n");
 615                     }
 616                   else if (cgraph_function_body_availability (n2)
 617                            <= AVAIL_OVERWRITABLE
 618                            && symtab_can_be_discarded (n2))
 619                     {
 620                       nuseless++;
 621                       if (dump_file)
 622                         fprintf (dump_file,
 623                                  "Not speculating: target is overwritable "
 624                                  "and can be discarded.\n");
 625                     }
 626                   else
 627                     {
 628                       /* Target may be overwritable, but profile says that
 629                          control flow goes to this particular implementation
 630                          of N2.  Speculate on the local alias to allow inlining.
 631                        */
 632                       if (!symtab_can_be_discarded (n2))
 633                         {
 634                           cgraph_node *alias;
 635                           alias = cgraph (symtab_nonoverwritable_alias
 636                                            (n2));
 637                           if (alias)
 638                             n2 = alias;
 639                         }
 640                       nconverted++;
 641                       cgraph_turn_edge_to_speculative
 642                         (e, n2,
 643                          apply_scale (e->count,
 644                                       e->indirect_info->common_target_probability),
 645                          apply_scale (e->frequency,
 646                                       e->indirect_info->common_target_probability));
 647                       update = true;
 648                     }
 649                 }
 650               else
 651                 {
 652                   if (dump_file)
 653                     fprintf (dump_file, "Function with profile-id %i not found.\n",
 654                              e->indirect_info->common_target_id);
 655                   nunknown++;
 656                 }
 657             }
 658          }
 659        if (update)
 660          inline_update_overall_summary (n);
 661      }
 662   if (node_map_initialized)
 663     del_node_map ();
 664   if (dump_file && nindirect)
 665     fprintf (dump_file,
 666              "%i indirect calls trained.\n"
 667              "%i (%3.2f%%) have common target.\n"
 668              "%i (%3.2f%%) targets was not found.\n"
 669              "%i (%3.2f%%) speculations seems useless.\n"
 670              "%i (%3.2f%%) speculations produced.\n",
 671              nindirect,
 672              ncommon, ncommon * 100.0 / nindirect,
 673              nunknown, nunknown * 100.0 / nindirect,
 674              nuseless, nuseless * 100.0 / nindirect,
 675              nconverted, nconverted * 100.0 / nindirect);
 676
 677   order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 678   order_pos = ipa_reverse_postorder (order);
 679   for (i = order_pos - 1; i >= 0; i--)
 680     {
 681       if (order[i]->local.local && ipa_propagate_frequency (order[i]))
 682         {
 683           for (e = order[i]->callees; e; e = e->next_callee)
 684             if (e->callee->local.local && !e->callee->aux)
 685               {
 686                 something_changed = true;
 687                 e->callee->aux = (void *)1;
 688               }
 689         }
 690       order[i]->aux = NULL;
 691     }
 692
 693   while (something_changed)
 694     {
 695       something_changed = false;
 696       for (i = order_pos - 1; i >= 0; i--)
 697         {
 698           if (order[i]->aux && ipa_propagate_frequency (order[i]))
 699             {
 700               for (e = order[i]->callees; e; e = e->next_callee)
 701                 if (e->callee->local.local && !e->callee->aux)
 702                   {
 703                     something_changed = true;
 704                     e->callee->aux = (void *)1;
 705                   }
 706             }
 707           order[i]->aux = NULL;
 708         }
 709     }
 710   free (order);
 711   return 0;
 712 }
 713
 714 namespace {
 715
 716 const pass_data pass_data_ipa_profile =
 717 {
 718   IPA_PASS, /* type */
 719   "profile_estimate", /* name */
 720   OPTGROUP_NONE, /* optinfo_flags */
 721   true, /* has_execute */
 722   TV_IPA_PROFILE, /* tv_id */
 723   0, /* properties_required */
 724   0, /* properties_provided */
 725   0, /* properties_destroyed */
 726   0, /* todo_flags_start */
 727   0, /* todo_flags_finish */
 728 };
 729
 730 class pass_ipa_profile : public ipa_opt_pass_d
 731 {
 732 public:
 733   pass_ipa_profile (gcc::context *ctxt)
 734     : ipa_opt_pass_d (pass_data_ipa_profile, ctxt,
 735                       ipa_profile_generate_summary, /* generate_summary */
 736                       ipa_profile_write_summary, /* write_summary */
 737                       ipa_profile_read_summary, /* read_summary */
 738                       NULL, /* write_optimization_summary */
 739                       NULL, /* read_optimization_summary */
 740                       NULL, /* stmt_fixup */
 741                       0, /* function_transform_todo_flags_start */
 742                       NULL, /* function_transform */
 743                       NULL) /* variable_transform */
 744   {}
 745
 746   /* opt_pass methods: */
 747   virtual bool gate (function *) { return flag_ipa_profile; }
 748   virtual unsigned int execute (function *) { return ipa_profile (); }
 749
 750 }; // class pass_ipa_profile
 751
 752 } // anon namespace
 753
 754 ipa_opt_pass_d *
 755 make_pass_ipa_profile (gcc::context *ctxt)
 756 {
 757   return new pass_ipa_profile (ctxt);
 758 }