gcc/profile-count.cc

   1 /* Profile counter container type.
   2    Copyright (C) 2017-2023 Free Software Foundation, Inc.
   3    Contributed by Jan Hubicka
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "profile-count.h"
  25 #include "options.h"
  26 #include "tree.h"
  27 #include "basic-block.h"
  28 #include "function.h"
  29 #include "cfg.h"
  30 #include "gimple.h"
  31 #include "data-streamer.h"
  32 #include "cgraph.h"
  33 #include "wide-int.h"
  34 #include "sreal.h"
  35
  36 /* Names from profile_quality enum values.  */
  37
  38 const char *profile_quality_names[] =
  39 {
  40   "uninitialized",
  41   "guessed_local",
  42   "guessed_global0",
  43   "guessed_global0adjusted",
  44   "guessed",
  45   "afdo",
  46   "adjusted",
  47   "precise"
  48 };
  49
  50 /* Get a string describing QUALITY.  */
  51
  52 const char *
  53 profile_quality_as_string (enum profile_quality quality)
  54 {
  55   return profile_quality_names[quality];
  56 }
  57
  58 /* Parse VALUE as profile quality and return true when a valid QUALITY.  */
  59
  60 bool
  61 parse_profile_quality (const char *value, profile_quality *quality)
  62 {
  63   for (unsigned i = 0; i < ARRAY_SIZE (profile_quality_names); i++)
  64     if (strcmp (profile_quality_names[i], value) == 0)
  65       {
  66         *quality = (profile_quality)i;
  67         return true;
  68       }
  69
  70   return false;
  71 }
  72
  73 /* Display names from profile_quality enum values.  */
  74
  75 const char *profile_quality_display_names[] =
  76 {
  77   NULL,
  78   "estimated locally",
  79   "estimated locally, globally 0",
  80   "estimated locally, globally 0 adjusted",
  81   "guessed",
  82   "auto FDO",
  83   "adjusted",
  84   "precise"
  85 };
  86
  87 /* Dump THIS to BUFFER.  */
  88
  89 void
  90 profile_count::dump (char *buffer, struct function *fun) const
  91 {
  92   if (!initialized_p ())
  93     sprintf (buffer, "uninitialized");
  94   else if (fun && initialized_p ()
  95            && fun->cfg
  96            && ENTRY_BLOCK_PTR_FOR_FN (fun)->count.initialized_p ())
  97     sprintf (buffer, "%" PRId64 " (%s, freq %.4f)", m_val,
  98              profile_quality_display_names[m_quality],
  99              to_sreal_scale (ENTRY_BLOCK_PTR_FOR_FN (fun)->count).to_double ());
 100   else
 101     sprintf (buffer, "%" PRId64 " (%s)", m_val,
 102              profile_quality_display_names[m_quality]);
 103 }
 104
 105 /* Dump THIS to F.  */
 106
 107 void
 108 profile_count::dump (FILE *f, struct function *fun) const
 109 {
 110   char buffer[64];
 111   dump (buffer, fun);
 112   fputs (buffer, f);
 113 }
 114
 115 /* Dump THIS to stderr.  */
 116
 117 void
 118 profile_count::debug () const
 119 {
 120   dump (stderr, cfun);
 121   fprintf (stderr, "\n");
 122 }
 123
 124 /* Return true if THIS differs from OTHER; tolerate small differences.  */
 125
 126 bool
 127 profile_count::differs_from_p (profile_count other) const
 128 {
 129   gcc_checking_assert (compatible_p (other));
 130   if (!initialized_p () || !other.initialized_p ())
 131     return initialized_p () != other.initialized_p ();
 132   if ((uint64_t)m_val - (uint64_t)other.m_val < 100
 133       || (uint64_t)other.m_val - (uint64_t)m_val < 100)
 134     return false;
 135   if (!other.m_val)
 136     return true;
 137   uint64_t ratio;
 138   safe_scale_64bit (m_val, 100, other.m_val, &ratio);
 139   return ratio < 99 || ratio > 101;
 140 }
 141
 142 /* Stream THIS from IB.  */
 143
 144 profile_count
 145 profile_count::stream_in (class lto_input_block *ib)
 146 {
 147   profile_count ret;
 148   ret.m_val = streamer_read_gcov_count (ib);
 149   ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
 150   return ret;
 151 }
 152
 153 /* Stream THIS to OB.  */
 154
 155 void
 156 profile_count::stream_out (struct output_block *ob)
 157 {
 158   streamer_write_gcov_count (ob, m_val);
 159   streamer_write_uhwi (ob, m_quality);
 160 }
 161
 162 /* Stream THIS to OB.  */
 163
 164 void
 165 profile_count::stream_out (struct lto_output_stream *ob)
 166 {
 167   streamer_write_gcov_count_stream (ob, m_val);
 168   streamer_write_uhwi_stream (ob, m_quality);
 169 }
 170
 171
 172 /* Output THIS to BUFFER.  */
 173
 174 void
 175 profile_probability::dump (char *buffer) const
 176 {
 177   if (!initialized_p ())
 178     sprintf (buffer, "uninitialized");
 179   else
 180     {
 181       /* Make difference between 0.00 as a roundoff error and actual 0.
 182          Similarly for 1.  */
 183       if (m_val == 0)
 184         buffer += sprintf (buffer, "never");
 185       else if (m_val == max_probability)
 186         buffer += sprintf (buffer, "always");
 187       else
 188         buffer += sprintf (buffer, "%3.1f%%", (double)m_val * 100 / max_probability);
 189
 190       if (m_quality == ADJUSTED)
 191         sprintf (buffer, " (adjusted)");
 192       else if (m_quality == AFDO)
 193         sprintf (buffer, " (auto FDO)");
 194       else if (m_quality == GUESSED)
 195         sprintf (buffer, " (guessed)");
 196     }
 197 }
 198
 199 /* Dump THIS to F.  */
 200
 201 void
 202 profile_probability::dump (FILE *f) const
 203 {
 204   char buffer[64];
 205   dump (buffer);
 206   fputs (buffer, f);
 207 }
 208
 209 /* Dump THIS to stderr.  */
 210
 211 void
 212 profile_probability::debug () const
 213 {
 214   dump (stderr);
 215   fprintf (stderr, "\n");
 216 }
 217
 218 /* Return true if THIS differs from OTHER; tolerate small differences.  */
 219
 220 bool
 221 profile_probability::differs_from_p (profile_probability other) const
 222 {
 223   if (!initialized_p () || !other.initialized_p ())
 224     return false;
 225   if ((uint64_t)m_val - (uint64_t)other.m_val < max_probability / 1000
 226       || (uint64_t)other.m_val - (uint64_t)max_probability < 1000)
 227     return false;
 228   if (!other.m_val)
 229     return true;
 230   int64_t ratio = (int64_t)m_val * 100 / other.m_val;
 231   return ratio < 99 || ratio > 101;
 232 }
 233
 234 /* Return true if THIS differs significantly from OTHER.  */
 235
 236 bool
 237 profile_probability::differs_lot_from_p (profile_probability other) const
 238 {
 239   if (!initialized_p () || !other.initialized_p ())
 240     return false;
 241   uint32_t d = m_val > other.m_val ? m_val - other.m_val : other.m_val - m_val;
 242   return d > max_probability / 2;
 243 }
 244
 245 /* Stream THIS from IB.  */
 246
 247 profile_probability
 248 profile_probability::stream_in (class lto_input_block *ib)
 249 {
 250   profile_probability ret;
 251   ret.m_val = streamer_read_uhwi (ib);
 252   ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
 253   return ret;
 254 }
 255
 256 /* Stream THIS to OB.  */
 257
 258 void
 259 profile_probability::stream_out (struct output_block *ob)
 260 {
 261   streamer_write_uhwi (ob, m_val);
 262   streamer_write_uhwi (ob, m_quality);
 263 }
 264
 265 /* Stream THIS to OB.  */
 266
 267 void
 268 profile_probability::stream_out (struct lto_output_stream *ob)
 269 {
 270   streamer_write_uhwi_stream (ob, m_val);
 271   streamer_write_uhwi_stream (ob, m_quality);
 272 }
 273
 274 /* Compute RES=(a*b + c/2)/c capping and return false if overflow happened.  */
 275
 276 bool
 277 slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
 278 {
 279   FIXED_WIDE_INT (128) tmp = a;
 280   wi::overflow_type overflow;
 281   tmp = wi::udiv_floor (wi::umul (tmp, b, &overflow) + (c / 2), c);
 282   gcc_checking_assert (!overflow);
 283   if (wi::fits_uhwi_p (tmp))
 284     {
 285       *res = tmp.to_uhwi ();
 286       return true;
 287     }
 288   *res = (uint64_t) -1;
 289   return false;
 290 }
 291
 292 /* Return count as frequency within FUN scaled in range 0 to REG_FREQ_MAX
 293    Used for legacy code and should not be used anymore.  */
 294
 295 int
 296 profile_count::to_frequency (struct function *fun) const
 297 {
 298   if (!initialized_p ())
 299     return BB_FREQ_MAX;
 300   if (*this == zero ())
 301     return 0;
 302   STATIC_ASSERT (REG_BR_PROB_BASE == BB_FREQ_MAX);
 303   gcc_assert (fun->cfg->count_max.initialized_p ());
 304   profile_probability prob = probability_in (fun->cfg->count_max);
 305   if (!prob.initialized_p ())
 306     return REG_BR_PROB_BASE;
 307   return prob.to_reg_br_prob_base ();
 308 }
 309
 310 /* Return count as frequency within FUN scaled in range 0 to CGRAPH_FREQ_MAX
 311    where CGRAPH_FREQ_BASE means that count equals to entry block count.
 312    Used for legacy code and should not be used anymore.  */
 313
 314 int
 315 profile_count::to_cgraph_frequency (profile_count entry_bb_count) const
 316 {
 317   if (!initialized_p () || !entry_bb_count.initialized_p ())
 318     return CGRAPH_FREQ_BASE;
 319   if (*this == zero ())
 320     return 0;
 321   gcc_checking_assert (entry_bb_count.initialized_p ());
 322   uint64_t scale;
 323   gcc_checking_assert (compatible_p (entry_bb_count));
 324   if (!safe_scale_64bit (!entry_bb_count.m_val ? m_val + 1 : m_val,
 325                          CGRAPH_FREQ_BASE, MAX (1, entry_bb_count.m_val), &scale))
 326     return CGRAPH_FREQ_MAX;
 327   return MIN (scale, CGRAPH_FREQ_MAX);
 328 }
 329
 330 /* Return THIS/IN as sreal value.  */
 331
 332 sreal
 333 profile_count::to_sreal_scale (profile_count in, bool *known) const
 334 {
 335   if (*this == zero ()
 336       && !(in == zero ()))
 337   {
 338     if (known)
 339       *known = true;
 340     return 0;
 341   }
 342   if (!initialized_p () || !in.initialized_p ())
 343     {
 344       if (known)
 345         *known = false;
 346       return 1;
 347     }
 348   if (known)
 349     *known = in.m_val != 0;
 350   if (*this == in)
 351     return 1;
 352   gcc_checking_assert (compatible_p (in));
 353   if (m_val == in.m_val)
 354     return 1;
 355   if (!in.m_val)
 356     return m_val * 4;
 357   return (sreal)m_val / (sreal)in.m_val;
 358 }
 359
 360 /* We want to scale profile across function boundary from NUM to DEN.
 361    Take care of the side case when DEN is zeros.  We still want to behave
 362    sanely here which means
 363      - scale to profile_count::zero () if NUM is profile_count::zero
 364      - do not affect anything if NUM == DEN
 365      - preserve counter value but adjust quality in other cases.  */
 366
 367 void
 368 profile_count::adjust_for_ipa_scaling (profile_count *num,
 369                                        profile_count *den)
 370 {
 371   /* Scaling is no-op if NUM and DEN are the same.  */
 372   if (*num == *den)
 373     return;
 374   /* Scaling to zero is always zero.  */
 375   if (*num == zero ())
 376     return;
 377   /* If den is non-zero we are safe.  */
 378   if (den->force_nonzero () == *den)
 379     return;
 380   /* Force both to non-zero so we do not push profiles to 0 when
 381      both num == 0 and den == 0.  */
 382   *den = den->force_nonzero ();
 383   *num = num->force_nonzero ();
 384 }
 385
 386 /* THIS is a count of bb which is known to be executed IPA times.
 387    Combine this information into bb counter.  This means returning IPA
 388    if it is nonzero, not changing anything if IPA is uninitialized
 389    and if IPA is zero, turning THIS into corresponding local profile with
 390    global0.  */
 391
 392 profile_count
 393 profile_count::combine_with_ipa_count (profile_count ipa)
 394 {
 395   if (!initialized_p ())
 396     return *this;
 397   ipa = ipa.ipa ();
 398   if (ipa.nonzero_p ())
 399     return ipa;
 400   if (!ipa.initialized_p () || *this == zero ())
 401     return *this;
 402   if (ipa == zero ())
 403     return this->global0 ();
 404   return this->global0adjusted ();
 405 }
 406
 407 /* Sae as profile_count::combine_with_ipa_count but within function with count
 408    IPA2.  */
 409 profile_count
 410 profile_count::combine_with_ipa_count_within (profile_count ipa,
 411                                               profile_count ipa2)
 412 {
 413   profile_count ret;
 414   if (!initialized_p ())
 415     return *this;
 416   if (ipa2.ipa () == ipa2 && ipa.initialized_p ())
 417     ret = ipa;
 418   else
 419     ret = combine_with_ipa_count (ipa);
 420   gcc_checking_assert (ret.compatible_p (ipa2));
 421   return ret;
 422 }
 423
 424 /* The profiling runtime uses gcov_type, which is usually 64bit integer.
 425    Conversions back and forth are used to read the coverage and get it
 426    into internal representation.  */
 427
 428 profile_count
 429 profile_count::from_gcov_type (gcov_type v, profile_quality quality)
 430   {
 431     profile_count ret;
 432     gcc_checking_assert (v >= 0);
 433     if (dump_file && v >= (gcov_type)max_count)
 434       fprintf (dump_file,
 435                "Capping gcov count %" PRId64 " to max_count %" PRId64 "\n",
 436                (int64_t) v, (int64_t) max_count);
 437     ret.m_val = MIN (v, (gcov_type)max_count);
 438     ret.m_quality = quality;
 439     return ret;
 440   }
 441
 442 /* COUNT1 times event happens with *THIS probability, COUNT2 times OTHER
 443    happens with COUNT2 probability.  Return probability that either *THIS or
 444    OTHER happens.  */
 445
 446 profile_probability
 447 profile_probability::combine_with_count (profile_count count1,
 448                                          profile_probability other,
 449                                          profile_count count2) const
 450 {
 451   /* If probabilities are same, we are done.
 452      If counts are nonzero we can distribute accordingly. In remaining
 453      cases just average the values and hope for the best.  */
 454   if (*this == other || count1 == count2
 455       || (count2 == profile_count::zero ()
 456           && !(count1 == profile_count::zero ())))
 457     return *this;
 458   if (count1 == profile_count::zero () && !(count2 == profile_count::zero ()))
 459     return other;
 460   else if (count1.nonzero_p () || count2.nonzero_p ())
 461     return *this * count1.probability_in (count1 + count2)
 462            + other * count2.probability_in (count1 + count2);
 463   else
 464     return *this * even () + other * even ();
 465 }
 466
 467 /* Return probability as sreal in range [0, 1].  */
 468
 469 sreal
 470 profile_probability::to_sreal () const
 471 {
 472   gcc_checking_assert (initialized_p ());
 473   return ((sreal)m_val) >> (n_bits - 2);
 474 }
 475
 476 /* Compute square root.  */
 477
 478 profile_probability
 479 profile_probability::sqrt () const
 480 {
 481   if (!initialized_p () || *this == never () || *this == always ())
 482     return *this;
 483   profile_probability ret = *this;
 484   ret.m_quality = MIN (ret.m_quality, ADJUSTED);
 485   uint32_t min_range = m_val;
 486   uint32_t max_range = max_probability;
 487   if (!m_val)
 488     max_range = 0;
 489   if (m_val == max_probability)
 490     min_range = max_probability;
 491   while (min_range != max_range)
 492     {
 493       uint32_t val = (min_range + max_range) / 2;
 494       uint32_t val2 = RDIV ((uint64_t)val * val, max_probability);
 495       if (val2 == m_val)
 496         min_range = max_range = m_val;
 497       else if (val2 > m_val)
 498         max_range = val - 1;
 499       else if (val2 < m_val)
 500         min_range = val + 1;
 501     }
 502   ret.m_val = min_range;
 503   return ret;
 504 }
 505
 506 /* Compute n-th power of THIS.  */
 507
 508 profile_probability
 509 profile_probability::pow (int n) const
 510 {
 511   if (n == 1 || !initialized_p ())
 512     return *this;
 513   if (!n)
 514     return profile_probability::always ();
 515   if (!nonzero_p ()
 516       || !(profile_probability::always () - *this).nonzero_p ())
 517     return *this;
 518   profile_probability ret = profile_probability::always ();
 519   profile_probability v = *this;
 520   int p = 1;
 521   while (true)
 522     {
 523       if (n & p)
 524         ret = ret * v;
 525       p <<= 1;
 526       if (p > n)
 527         break;
 528       v = v * v;
 529     }
 530   return ret;
 531 }