gcc/ipa-profile.c

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