gcc/ipa-profile.c

   1 /* Basic IPA optimizations based on profile.
   2    Copyright (C) 2003-2020 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,
 138             overall_size = 0;
 139
 140   fprintf (dump_file, "Histogram:\n");
 141   for (i = 0; i < histogram.length (); i++)
 142     {
 143       overall_time += histogram[i]->count * histogram[i]->time;
 144       overall_size += histogram[i]->size;
 145     }
 146   if (!overall_time)
 147     overall_time = 1;
 148   if (!overall_size)
 149     overall_size = 1;
 150   for (i = 0; i < histogram.length (); i++)
 151     {
 152       cumulated_time += histogram[i]->count * histogram[i]->time;
 153       cumulated_size += histogram[i]->size;
 154       fprintf (file, "  %" PRId64": time:%i (%2.2f) size:%i (%2.2f)\n",
 155                (int64_t) histogram[i]->count,
 156                histogram[i]->time,
 157                cumulated_time * 100.0 / overall_time,
 158                histogram[i]->size,
 159                cumulated_size * 100.0 / overall_size);
 160    }
 161 }
 162
 163 /* Structure containing speculative target information from profile.  */
 164
 165 struct speculative_call_target
 166 {
 167   speculative_call_target (unsigned int id = 0, int prob = 0)
 168     : target_id (id), target_probability (prob)
 169   {
 170   }
 171
 172   /* Profile_id of target obtained from profile.  */
 173   unsigned int target_id;
 174   /* Probability that call will land in function with target_id.  */
 175   unsigned int target_probability;
 176 };
 177
 178 class speculative_call_summary
 179 {
 180 public:
 181   speculative_call_summary () : speculative_call_targets ()
 182   {}
 183
 184   auto_vec<speculative_call_target> speculative_call_targets;
 185
 186   void dump (FILE *f);
 187
 188 };
 189
 190   /* Class to manage call summaries.  */
 191
 192 class ipa_profile_call_summaries
 193   : public call_summary<speculative_call_summary *>
 194 {
 195 public:
 196   ipa_profile_call_summaries (symbol_table *table)
 197     : call_summary<speculative_call_summary *> (table)
 198   {}
 199
 200   /* Duplicate info when an edge is cloned.  */
 201   virtual void duplicate (cgraph_edge *, cgraph_edge *,
 202                           speculative_call_summary *old_sum,
 203                           speculative_call_summary *new_sum);
 204 };
 205
 206 static ipa_profile_call_summaries *call_sums = NULL;
 207
 208 /* Dump all information in speculative call summary to F.  */
 209
 210 void
 211 speculative_call_summary::dump (FILE *f)
 212 {
 213   cgraph_node *n2;
 214
 215   unsigned spec_count = speculative_call_targets.length ();
 216   for (unsigned i = 0; i < spec_count; i++)
 217     {
 218       speculative_call_target item = speculative_call_targets[i];
 219       n2 = find_func_by_profile_id (item.target_id);
 220       if (n2)
 221         fprintf (f, "    The %i speculative target is %s with prob %3.2f\n", i,
 222                  n2->dump_name (),
 223                  item.target_probability / (float) REG_BR_PROB_BASE);
 224       else
 225         fprintf (f, "    The %i speculative target is %u with prob %3.2f\n", i,
 226                  item.target_id,
 227                  item.target_probability / (float) REG_BR_PROB_BASE);
 228     }
 229 }
 230
 231 /* Duplicate info when an edge is cloned.  */
 232
 233 void
 234 ipa_profile_call_summaries::duplicate (cgraph_edge *, cgraph_edge *,
 235                                        speculative_call_summary *old_sum,
 236                                        speculative_call_summary *new_sum)
 237 {
 238   if (!old_sum)
 239     return;
 240
 241   unsigned old_count = old_sum->speculative_call_targets.length ();
 242   if (!old_count)
 243     return;
 244
 245   new_sum->speculative_call_targets.reserve_exact (old_count);
 246   new_sum->speculative_call_targets.quick_grow_cleared (old_count);
 247
 248   for (unsigned i = 0; i < old_count; i++)
 249     {
 250       new_sum->speculative_call_targets[i]
 251         = old_sum->speculative_call_targets[i];
 252     }
 253 }
 254
 255 /* Collect histogram and speculative target summaries from CFG profiles.  */
 256
 257 static void
 258 ipa_profile_generate_summary (void)
 259 {
 260   struct cgraph_node *node;
 261   gimple_stmt_iterator gsi;
 262   basic_block bb;
 263
 264   hash_table<histogram_hash> hashtable (10);
 265
 266   gcc_checking_assert (!call_sums);
 267   call_sums = new ipa_profile_call_summaries (symtab);
 268
 269   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
 270     if (ENTRY_BLOCK_PTR_FOR_FN
 271           (DECL_STRUCT_FUNCTION (node->decl))->count.ipa_p ())
 272       FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
 273         {
 274           int time = 0;
 275           int size = 0;
 276           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 277             {
 278               gimple *stmt = gsi_stmt (gsi);
 279               if (gimple_code (stmt) == GIMPLE_CALL
 280                   && !gimple_call_fndecl (stmt))
 281                 {
 282                   histogram_value h;
 283                   h = gimple_histogram_value_of_type
 284                         (DECL_STRUCT_FUNCTION (node->decl),
 285                          stmt, HIST_TYPE_INDIR_CALL);
 286                   /* No need to do sanity check: gimple_ic_transform already
 287                      takes away bad histograms.  */
 288                   if (h)
 289                     {
 290                       gcov_type val, count, all;
 291                       struct cgraph_edge *e = node->get_edge (stmt);
 292                       if (e && !e->indirect_unknown_callee)
 293                         continue;
 294
 295                       speculative_call_summary *csum
 296                         = call_sums->get_create (e);
 297
 298                       for (unsigned j = 0; j < GCOV_TOPN_MAXIMUM_TRACKED_VALUES;
 299                            j++)
 300                         {
 301                           if (!get_nth_most_common_value (NULL, "indirect call",
 302                                                           h, &val, &count, &all,
 303                                                           j))
 304                             continue;
 305
 306                           if (val == 0 || count == 0)
 307                             continue;
 308
 309                           if (count > all)
 310                             {
 311                               if (dump_file)
 312                                 fprintf (dump_file,
 313                                          "Probability capped to 1\n");
 314                               count = all;
 315                             }
 316                           speculative_call_target item (
 317                             val, GCOV_COMPUTE_SCALE (count, all));
 318                           csum->speculative_call_targets.safe_push (item);
 319                         }
 320
 321                       gimple_remove_histogram_value
 322                          (DECL_STRUCT_FUNCTION (node->decl), stmt, h);
 323                     }
 324                 }
 325               time += estimate_num_insns (stmt, &eni_time_weights);
 326               size += estimate_num_insns (stmt, &eni_size_weights);
 327             }
 328           if (bb->count.ipa_p () && bb->count.initialized_p ())
 329             account_time_size (&hashtable, histogram,
 330                                bb->count.ipa ().to_gcov_type (),
 331                                time, size);
 332         }
 333   histogram.qsort (cmp_counts);
 334 }
 335
 336 /* Serialize the speculative summary info for LTO.  */
 337
 338 static void
 339 ipa_profile_write_edge_summary (lto_simple_output_block *ob,
 340                                 speculative_call_summary *csum)
 341 {
 342   unsigned len = 0;
 343
 344   len = csum->speculative_call_targets.length ();
 345
 346   gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES);
 347
 348   streamer_write_hwi_stream (ob->main_stream, len);
 349
 350   if (len)
 351     {
 352       unsigned spec_count = csum->speculative_call_targets.length ();
 353       for (unsigned i = 0; i < spec_count; i++)
 354         {
 355           speculative_call_target item = csum->speculative_call_targets[i];
 356           gcc_assert (item.target_id);
 357           streamer_write_hwi_stream (ob->main_stream, item.target_id);
 358           streamer_write_hwi_stream (ob->main_stream, item.target_probability);
 359         }
 360     }
 361 }
 362
 363 /* Serialize the ipa info for lto.  */
 364
 365 static void
 366 ipa_profile_write_summary (void)
 367 {
 368   struct lto_simple_output_block *ob
 369     = lto_create_simple_output_block (LTO_section_ipa_profile);
 370   unsigned int i;
 371
 372   streamer_write_uhwi_stream (ob->main_stream, histogram.length ());
 373   for (i = 0; i < histogram.length (); i++)
 374     {
 375       streamer_write_gcov_count_stream (ob->main_stream, histogram[i]->count);
 376       streamer_write_uhwi_stream (ob->main_stream, histogram[i]->time);
 377       streamer_write_uhwi_stream (ob->main_stream, histogram[i]->size);
 378     }
 379
 380   if (!call_sums)
 381     return;
 382
 383   /* Serialize speculative targets information.  */
 384   unsigned int count = 0;
 385   lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder;
 386   lto_symtab_encoder_iterator lsei;
 387   cgraph_node *node;
 388
 389   for (lsei = lsei_start_function_in_partition (encoder); !lsei_end_p (lsei);
 390        lsei_next_function_in_partition (&lsei))
 391     {
 392       node = lsei_cgraph_node (lsei);
 393       if (node->definition && node->has_gimple_body_p ()
 394           && node->indirect_calls)
 395         count++;
 396     }
 397
 398   streamer_write_uhwi_stream (ob->main_stream, count);
 399
 400   /* Process all of the functions.  */
 401   for (lsei = lsei_start_function_in_partition (encoder);
 402        !lsei_end_p (lsei) && count; lsei_next_function_in_partition (&lsei))
 403     {
 404       cgraph_node *node = lsei_cgraph_node (lsei);
 405       if (node->definition && node->has_gimple_body_p ()
 406           && node->indirect_calls)
 407         {
 408           int node_ref = lto_symtab_encoder_encode (encoder, node);
 409           streamer_write_uhwi_stream (ob->main_stream, node_ref);
 410
 411           for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
 412             {
 413               speculative_call_summary *csum = call_sums->get_create (e);
 414               ipa_profile_write_edge_summary (ob, csum);
 415             }
 416       }
 417     }
 418
 419   lto_destroy_simple_output_block (ob);
 420 }
 421
 422 /* Dump all profile summary data for all cgraph nodes and edges to file F.  */
 423
 424 static void
 425 ipa_profile_dump_all_summaries (FILE *f)
 426 {
 427   fprintf (dump_file,
 428            "\n========== IPA-profile speculative targets: ==========\n");
 429   cgraph_node *node;
 430   FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
 431     {
 432       fprintf (f, "\nSummary for node %s:\n", node->dump_name ());
 433       for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
 434         {
 435           fprintf (f, "  Summary for %s of indirect edge %d:\n",
 436                    e->caller->dump_name (), e->lto_stmt_uid);
 437           speculative_call_summary *csum = call_sums->get_create (e);
 438           csum->dump (f);
 439         }
 440     }
 441   fprintf (f, "\n\n");
 442 }
 443
 444 /* Read speculative targets information about edge for LTO WPA.  */
 445
 446 static void
 447 ipa_profile_read_edge_summary (class lto_input_block *ib, cgraph_edge *edge)
 448 {
 449   unsigned i, len;
 450
 451   len = streamer_read_hwi (ib);
 452   gcc_assert (len <= GCOV_TOPN_MAXIMUM_TRACKED_VALUES);
 453   speculative_call_summary *csum = call_sums->get_create (edge);
 454
 455   for (i = 0; i < len; i++)
 456   {
 457     unsigned int target_id = streamer_read_hwi (ib);
 458     int target_probability = streamer_read_hwi (ib);
 459     speculative_call_target item (target_id, target_probability);
 460     csum->speculative_call_targets.safe_push (item);
 461   }
 462 }
 463
 464 /* Read profile speculative targets section information for LTO WPA.  */
 465
 466 static void
 467 ipa_profile_read_summary_section (struct lto_file_decl_data *file_data,
 468                                   class lto_input_block *ib)
 469 {
 470   if (!ib)
 471     return;
 472
 473   lto_symtab_encoder_t encoder = file_data->symtab_node_encoder;
 474
 475   unsigned int count = streamer_read_uhwi (ib);
 476
 477   unsigned int i;
 478   unsigned int index;
 479   cgraph_node * node;
 480
 481   for (i = 0; i < count; i++)
 482     {
 483       index = streamer_read_uhwi (ib);
 484       encoder = file_data->symtab_node_encoder;
 485       node
 486         = dyn_cast<cgraph_node *> (lto_symtab_encoder_deref (encoder, index));
 487
 488       for (cgraph_edge *e = node->indirect_calls; e; e = e->next_callee)
 489         ipa_profile_read_edge_summary (ib, e);
 490     }
 491 }
 492
 493 /* Deserialize the IPA histogram and speculative targets summary info for LTO.
 494    */
 495
 496 static void
 497 ipa_profile_read_summary (void)
 498 {
 499   struct lto_file_decl_data ** file_data_vec
 500     = lto_get_file_decl_data ();
 501   struct lto_file_decl_data * file_data;
 502   int j = 0;
 503
 504   hash_table<histogram_hash> hashtable (10);
 505
 506   gcc_checking_assert (!call_sums);
 507   call_sums = new ipa_profile_call_summaries (symtab);
 508
 509   while ((file_data = file_data_vec[j++]))
 510     {
 511       const char *data;
 512       size_t len;
 513       class lto_input_block *ib
 514         = lto_create_simple_input_block (file_data,
 515                                          LTO_section_ipa_profile,
 516                                          &data, &len);
 517       if (ib)
 518         {
 519           unsigned int num = streamer_read_uhwi (ib);
 520           unsigned int n;
 521           for (n = 0; n < num; n++)
 522             {
 523               gcov_type count = streamer_read_gcov_count (ib);
 524               int time = streamer_read_uhwi (ib);
 525               int size = streamer_read_uhwi (ib);
 526               account_time_size (&hashtable, histogram,
 527                                  count, time, size);
 528             }
 529
 530           ipa_profile_read_summary_section (file_data, ib);
 531
 532           lto_destroy_simple_input_block (file_data,
 533                                           LTO_section_ipa_profile,
 534                                           ib, data, len);
 535         }
 536     }
 537   histogram.qsort (cmp_counts);
 538 }
 539
 540 /* Data used by ipa_propagate_frequency.  */
 541
 542 struct ipa_propagate_frequency_data
 543 {
 544   cgraph_node *function_symbol;
 545   bool maybe_unlikely_executed;
 546   bool maybe_executed_once;
 547   bool only_called_at_startup;
 548   bool only_called_at_exit;
 549 };
 550
 551 /* Worker for ipa_propagate_frequency_1.  */
 552
 553 static bool
 554 ipa_propagate_frequency_1 (struct cgraph_node *node, void *data)
 555 {
 556   struct ipa_propagate_frequency_data *d;
 557   struct cgraph_edge *edge;
 558
 559   d = (struct ipa_propagate_frequency_data *)data;
 560   for (edge = node->callers;
 561        edge && (d->maybe_unlikely_executed || d->maybe_executed_once
 562                 || d->only_called_at_startup || d->only_called_at_exit);
 563        edge = edge->next_caller)
 564     {
 565       if (edge->caller != d->function_symbol)
 566         {
 567           d->only_called_at_startup &= edge->caller->only_called_at_startup;
 568           /* It makes sense to put main() together with the static constructors.
 569              It will be executed for sure, but rest of functions called from
 570              main are definitely not at startup only.  */
 571           if (MAIN_NAME_P (DECL_NAME (edge->caller->decl)))
 572             d->only_called_at_startup = 0;
 573           d->only_called_at_exit &= edge->caller->only_called_at_exit;
 574         }
 575
 576       /* When profile feedback is available, do not try to propagate too hard;
 577          counts are already good guide on function frequencies and roundoff
 578          errors can make us to push function into unlikely section even when
 579          it is executed by the train run.  Transfer the function only if all
 580          callers are unlikely executed.  */
 581       if (profile_info
 582           && !(edge->callee->count.ipa () == profile_count::zero ())
 583           && (edge->caller->frequency != NODE_FREQUENCY_UNLIKELY_EXECUTED
 584               || (edge->caller->inlined_to
 585                   && edge->caller->inlined_to->frequency
 586                      != NODE_FREQUENCY_UNLIKELY_EXECUTED)))
 587           d->maybe_unlikely_executed = false;
 588       if (edge->count.ipa ().initialized_p ()
 589           && !edge->count.ipa ().nonzero_p ())
 590         continue;
 591       switch (edge->caller->frequency)
 592         {
 593         case NODE_FREQUENCY_UNLIKELY_EXECUTED:
 594           break;
 595         case NODE_FREQUENCY_EXECUTED_ONCE:
 596           {
 597             if (dump_file && (dump_flags & TDF_DETAILS))
 598               fprintf (dump_file, "  Called by %s that is executed once\n",
 599                        edge->caller->dump_name ());
 600             d->maybe_unlikely_executed = false;
 601             ipa_call_summary *s = ipa_call_summaries->get (edge);
 602             if (s != NULL && s->loop_depth)
 603               {
 604                 d->maybe_executed_once = false;
 605                 if (dump_file && (dump_flags & TDF_DETAILS))
 606                   fprintf (dump_file, "  Called in loop\n");
 607               }
 608             break;
 609           }
 610         case NODE_FREQUENCY_HOT:
 611         case NODE_FREQUENCY_NORMAL:
 612           if (dump_file && (dump_flags & TDF_DETAILS))
 613             fprintf (dump_file, "  Called by %s that is normal or hot\n",
 614                      edge->caller->dump_name ());
 615           d->maybe_unlikely_executed = false;
 616           d->maybe_executed_once = false;
 617           break;
 618         }
 619     }
 620   return edge != NULL;
 621 }
 622
 623 /* Return ture if NODE contains hot calls.  */
 624
 625 bool
 626 contains_hot_call_p (struct cgraph_node *node)
 627 {
 628   struct cgraph_edge *e;
 629   for (e = node->callees; e; e = e->next_callee)
 630     if (e->maybe_hot_p ())
 631       return true;
 632     else if (!e->inline_failed
 633              && contains_hot_call_p (e->callee))
 634       return true;
 635   for (e = node->indirect_calls; e; e = e->next_callee)
 636     if (e->maybe_hot_p ())
 637       return true;
 638   return false;
 639 }
 640
 641 /* See if the frequency of NODE can be updated based on frequencies of its
 642    callers.  */
 643 bool
 644 ipa_propagate_frequency (struct cgraph_node *node)
 645 {
 646   struct ipa_propagate_frequency_data d = {node, true, true, true, true};
 647   bool changed = false;
 648
 649   /* We cannot propagate anything useful about externally visible functions
 650      nor about virtuals.  */
 651   if (!node->local
 652       || node->alias
 653       || (opt_for_fn (node->decl, flag_devirtualize)
 654           && DECL_VIRTUAL_P (node->decl)))
 655     return false;
 656   gcc_assert (node->analyzed);
 657   if (dump_file && (dump_flags & TDF_DETAILS))
 658     fprintf (dump_file, "Processing frequency %s\n", node->dump_name ());
 659
 660   node->call_for_symbol_and_aliases (ipa_propagate_frequency_1, &d,
 661                                      true);
 662
 663   if ((d.only_called_at_startup && !d.only_called_at_exit)
 664       && !node->only_called_at_startup)
 665     {
 666        node->only_called_at_startup = true;
 667        if (dump_file)
 668          fprintf (dump_file, "Node %s promoted to only called at startup.\n",
 669                   node->dump_name ());
 670        changed = true;
 671     }
 672   if ((d.only_called_at_exit && !d.only_called_at_startup)
 673       && !node->only_called_at_exit)
 674     {
 675        node->only_called_at_exit = true;
 676        if (dump_file)
 677          fprintf (dump_file, "Node %s promoted to only called at exit.\n",
 678                   node->dump_name ());
 679        changed = true;
 680     }
 681
 682   /* With profile we can decide on hot/normal based on count.  */
 683   if (node->count. ipa().initialized_p ())
 684     {
 685       bool hot = false;
 686       if (!(node->count. ipa() == profile_count::zero ())
 687           && node->count. ipa() >= get_hot_bb_threshold ())
 688         hot = true;
 689       if (!hot)
 690         hot |= contains_hot_call_p (node);
 691       if (hot)
 692         {
 693           if (node->frequency != NODE_FREQUENCY_HOT)
 694             {
 695               if (dump_file)
 696                 fprintf (dump_file, "Node %s promoted to hot.\n",
 697                          node->dump_name ());
 698               node->frequency = NODE_FREQUENCY_HOT;
 699               return true;
 700             }
 701           return false;
 702         }
 703       else if (node->frequency == NODE_FREQUENCY_HOT)
 704         {
 705           if (dump_file)
 706             fprintf (dump_file, "Node %s reduced to normal.\n",
 707                      node->dump_name ());
 708           node->frequency = NODE_FREQUENCY_NORMAL;
 709           changed = true;
 710         }
 711     }
 712   /* These come either from profile or user hints; never update them.  */
 713   if (node->frequency == NODE_FREQUENCY_HOT
 714       || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
 715     return changed;
 716   if (d.maybe_unlikely_executed)
 717     {
 718       node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
 719       if (dump_file)
 720         fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
 721                  node->dump_name ());
 722       changed = true;
 723     }
 724   else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
 725     {
 726       node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
 727       if (dump_file)
 728         fprintf (dump_file, "Node %s promoted to executed once.\n",
 729                  node->dump_name ());
 730       changed = true;
 731     }
 732   return changed;
 733 }
 734
 735 /* Check that number of arguments of N agrees with E.
 736    Be conservative when summaries are not present.  */
 737
 738 static bool
 739 check_argument_count (struct cgraph_node *n, struct cgraph_edge *e)
 740 {
 741   if (!ipa_node_params_sum || !ipa_edge_args_sum)
 742     return true;
 743   class ipa_node_params *info = IPA_NODE_REF (n->function_symbol ());
 744   if (!info)
 745     return true;
 746   ipa_edge_args *e_info = IPA_EDGE_REF (e);
 747   if (!e_info)
 748     return true;
 749   if (ipa_get_param_count (info) != ipa_get_cs_argument_count (e_info)
 750       && (ipa_get_param_count (info) >= ipa_get_cs_argument_count (e_info)
 751           || !stdarg_p (TREE_TYPE (n->decl))))
 752     return false;
 753   return true;
 754 }
 755
 756 /* Simple ipa profile pass propagating frequencies across the callgraph.  */
 757
 758 static unsigned int
 759 ipa_profile (void)
 760 {
 761   struct cgraph_node **order;
 762   struct cgraph_edge *e;
 763   int order_pos;
 764   bool something_changed = false;
 765   int i;
 766   gcov_type overall_time = 0, cutoff = 0, cumulated = 0, overall_size = 0;
 767   struct cgraph_node *n,*n2;
 768   int nindirect = 0, ncommon = 0, nunknown = 0, nuseless = 0, nconverted = 0;
 769   int nmismatch = 0, nimpossible = 0;
 770   bool node_map_initialized = false;
 771   gcov_type threshold;
 772
 773   if (dump_file)
 774     dump_histogram (dump_file, histogram);
 775   for (i = 0; i < (int)histogram.length (); i++)
 776     {
 777       overall_time += histogram[i]->count * histogram[i]->time;
 778       overall_size += histogram[i]->size;
 779     }
 780   threshold = 0;
 781   if (overall_time)
 782     {
 783       gcc_assert (overall_size);
 784
 785       cutoff = (overall_time * param_hot_bb_count_ws_permille + 500) / 1000;
 786       for (i = 0; cumulated < cutoff; i++)
 787         {
 788           cumulated += histogram[i]->count * histogram[i]->time;
 789           threshold = histogram[i]->count;
 790         }
 791       if (!threshold)
 792         threshold = 1;
 793       if (dump_file)
 794         {
 795           gcov_type cumulated_time = 0, cumulated_size = 0;
 796
 797           for (i = 0;
 798                i < (int)histogram.length () && histogram[i]->count >= threshold;
 799                i++)
 800             {
 801               cumulated_time += histogram[i]->count * histogram[i]->time;
 802               cumulated_size += histogram[i]->size;
 803             }
 804           fprintf (dump_file, "Determined min count: %" PRId64
 805                    " Time:%3.2f%% Size:%3.2f%%\n",
 806                    (int64_t)threshold,
 807                    cumulated_time * 100.0 / overall_time,
 808                    cumulated_size * 100.0 / overall_size);
 809         }
 810
 811       if (in_lto_p)
 812         {
 813           if (dump_file)
 814             fprintf (dump_file, "Setting hotness threshold in LTO mode.\n");
 815           set_hot_bb_threshold (threshold);
 816         }
 817     }
 818   histogram.release ();
 819   histogram_pool.release ();
 820
 821   /* Produce speculative calls: we saved common target from profiling into
 822      e->target_id.  Now, at link time, we can look up corresponding
 823      function node and produce speculative call.  */
 824
 825   gcc_checking_assert (call_sums);
 826
 827   if (dump_file)
 828     {
 829       if (!node_map_initialized)
 830         init_node_map (false);
 831       node_map_initialized = true;
 832
 833       ipa_profile_dump_all_summaries (dump_file);
 834     }
 835
 836   FOR_EACH_DEFINED_FUNCTION (n)
 837     {
 838       bool update = false;
 839
 840       if (!opt_for_fn (n->decl, flag_ipa_profile))
 841         continue;
 842
 843       for (e = n->indirect_calls; e; e = e->next_callee)
 844         {
 845           if (n->count.initialized_p ())
 846             nindirect++;
 847
 848           speculative_call_summary *csum = call_sums->get_create (e);
 849           unsigned spec_count = csum->speculative_call_targets.length ();
 850           if (spec_count)
 851             {
 852               if (!node_map_initialized)
 853                 init_node_map (false);
 854               node_map_initialized = true;
 855               ncommon++;
 856
 857               if (in_lto_p)
 858                 {
 859                   if (dump_file)
 860                     {
 861                       fprintf (dump_file,
 862                                "Updating hotness threshold in LTO mode.\n");
 863                       fprintf (dump_file, "Updated min count: %" PRId64 "\n",
 864                                (int64_t) threshold / spec_count);
 865                     }
 866                   set_hot_bb_threshold (threshold / spec_count);
 867                 }
 868
 869               unsigned speculative_id = 0;
 870               profile_count orig = e->count;
 871               for (unsigned i = 0; i < spec_count; i++)
 872                 {
 873                   speculative_call_target item
 874                     = csum->speculative_call_targets[i];
 875                   n2 = find_func_by_profile_id (item.target_id);
 876                   if (n2)
 877                     {
 878                       if (dump_file)
 879                         {
 880                           fprintf (dump_file,
 881                                    "Indirect call -> direct call from"
 882                                    " other module %s => %s, prob %3.2f\n",
 883                                    n->dump_name (),
 884                                    n2->dump_name (),
 885                                    item.target_probability
 886                                      / (float) REG_BR_PROB_BASE);
 887                         }
 888                       if (item.target_probability < REG_BR_PROB_BASE / 2)
 889                         {
 890                           nuseless++;
 891                           if (dump_file)
 892                             fprintf (dump_file,
 893                                      "Not speculating: "
 894                                      "probability is too low.\n");
 895                         }
 896                       else if (!e->maybe_hot_p ())
 897                         {
 898                           nuseless++;
 899                           if (dump_file)
 900                             fprintf (dump_file,
 901                                      "Not speculating: call is cold.\n");
 902                         }
 903                       else if (n2->get_availability () <= AVAIL_INTERPOSABLE
 904                                && n2->can_be_discarded_p ())
 905                         {
 906                           nuseless++;
 907                           if (dump_file)
 908                             fprintf (dump_file,
 909                                      "Not speculating: target is overwritable "
 910                                      "and can be discarded.\n");
 911                         }
 912                       else if (!check_argument_count (n2, e))
 913                         {
 914                           nmismatch++;
 915                           if (dump_file)
 916                             fprintf (dump_file,
 917                                      "Not speculating: "
 918                                      "parameter count mismatch\n");
 919                         }
 920                       else if (e->indirect_info->polymorphic
 921                                && !opt_for_fn (n->decl, flag_devirtualize)
 922                                && !possible_polymorphic_call_target_p (e, n2))
 923                         {
 924                           nimpossible++;
 925                           if (dump_file)
 926                             fprintf (dump_file,
 927                                      "Not speculating: "
 928                                      "function is not in the polymorphic "
 929                                      "call target list\n");
 930                         }
 931                       else
 932                         {
 933                           /* Target may be overwritable, but profile says that
 934                              control flow goes to this particular implementation
 935                              of N2.  Speculate on the local alias to allow
 936                              inlining.  */
 937                           if (!n2->can_be_discarded_p ())
 938                             {
 939                               cgraph_node *alias;
 940                               alias = dyn_cast<cgraph_node *>
 941                                    (n2->noninterposable_alias ());
 942                               if (alias)
 943                                 n2 = alias;
 944                             }
 945                           nconverted++;
 946                           profile_probability prob
 947                                  = profile_probability::from_reg_br_prob_base
 948                                         (item.target_probability).adjusted ();
 949                           e->make_speculative (n2,
 950                                                orig.apply_probability (prob),
 951                                                speculative_id);
 952                           update = true;
 953                           speculative_id++;
 954                         }
 955                     }
 956                   else
 957                     {
 958                       if (dump_file)
 959                         fprintf (dump_file,
 960                                  "Function with profile-id %i not found.\n",
 961                                  item.target_id);
 962                       nunknown++;
 963                     }
 964                 }
 965             }
 966         }
 967       if (update)
 968         ipa_update_overall_fn_summary (n);
 969     }
 970   if (node_map_initialized)
 971     del_node_map ();
 972   if (dump_file && nindirect)
 973     fprintf (dump_file,
 974              "%i indirect calls trained.\n"
 975              "%i (%3.2f%%) have common target.\n"
 976              "%i (%3.2f%%) targets was not found.\n"
 977              "%i (%3.2f%%) targets had parameter count mismatch.\n"
 978              "%i (%3.2f%%) targets was not in polymorphic call target list.\n"
 979              "%i (%3.2f%%) speculations seems useless.\n"
 980              "%i (%3.2f%%) speculations produced.\n",
 981              nindirect,
 982              ncommon, ncommon * 100.0 / nindirect,
 983              nunknown, nunknown * 100.0 / nindirect,
 984              nmismatch, nmismatch * 100.0 / nindirect,
 985              nimpossible, nimpossible * 100.0 / nindirect,
 986              nuseless, nuseless * 100.0 / nindirect,
 987              nconverted, nconverted * 100.0 / nindirect);
 988
 989   order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
 990   order_pos = ipa_reverse_postorder (order);
 991   for (i = order_pos - 1; i >= 0; i--)
 992     {
 993       if (order[i]->local
 994           && opt_for_fn (order[i]->decl, flag_ipa_profile)
 995           && ipa_propagate_frequency (order[i]))
 996         {
 997           for (e = order[i]->callees; e; e = e->next_callee)
 998             if (e->callee->local && !e->callee->aux)
 999               {
1000                 something_changed = true;
1001                 e->callee->aux = (void *)1;
1002               }
1003         }
1004       order[i]->aux = NULL;
1005     }
1006
1007   while (something_changed)
1008     {
1009       something_changed = false;
1010       for (i = order_pos - 1; i >= 0; i--)
1011         {
1012           if (order[i]->aux
1013               && opt_for_fn (order[i]->decl, flag_ipa_profile)
1014               && ipa_propagate_frequency (order[i]))
1015             {
1016               for (e = order[i]->callees; e; e = e->next_callee)
1017                 if (e->callee->local && !e->callee->aux)
1018                   {
1019                     something_changed = true;
1020                     e->callee->aux = (void *)1;
1021                   }
1022             }
1023           order[i]->aux = NULL;
1024         }
1025     }
1026   free (order);
1027
1028   if (dump_file && (dump_flags & TDF_DETAILS))
1029     symtab->dump (dump_file);
1030
1031   delete call_sums;
1032   call_sums = NULL;
1033
1034   return 0;
1035 }
1036
1037 namespace {
1038
1039 const pass_data pass_data_ipa_profile =
1040 {
1041   IPA_PASS, /* type */
1042   "profile_estimate", /* name */
1043   OPTGROUP_NONE, /* optinfo_flags */
1044   TV_IPA_PROFILE, /* tv_id */
1045   0, /* properties_required */
1046   0, /* properties_provided */
1047   0, /* properties_destroyed */
1048   0, /* todo_flags_start */
1049   0, /* todo_flags_finish */
1050 };
1051
1052 class pass_ipa_profile : public ipa_opt_pass_d
1053 {
1054 public:
1055   pass_ipa_profile (gcc::context *ctxt)
1056     : ipa_opt_pass_d (pass_data_ipa_profile, ctxt,
1057                       ipa_profile_generate_summary, /* generate_summary */
1058                       ipa_profile_write_summary, /* write_summary */
1059                       ipa_profile_read_summary, /* read_summary */
1060                       NULL, /* write_optimization_summary */
1061                       NULL, /* read_optimization_summary */
1062                       NULL, /* stmt_fixup */
1063                       0, /* function_transform_todo_flags_start */
1064                       NULL, /* function_transform */
1065                       NULL) /* variable_transform */
1066   {}
1067
1068   /* opt_pass methods: */
1069   virtual bool gate (function *) { return flag_ipa_profile || in_lto_p; }
1070   virtual unsigned int execute (function *) { return ipa_profile (); }
1071
1072 }; // class pass_ipa_profile
1073
1074 } // anon namespace
1075
1076 ipa_opt_pass_d *
1077 make_pass_ipa_profile (gcc::context *ctxt)
1078 {
1079   return new pass_ipa_profile (ctxt);
1080 }