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