gcc/ipa-profile.c

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