gcc/profile-count.cc

   1 /* Profile counter container type.
   2    Copyright (C) 2017-2024 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 F.  */
  88
  89 void
  90 profile_count::dump (FILE *f, struct function *fun) const
  91 {
  92   if (!initialized_p ())
  93     fprintf (f, "uninitialized");
  94   else if (fun && initialized_p ()
  95            && fun->cfg
  96            && ENTRY_BLOCK_PTR_FOR_FN (fun)->count.initialized_p ())
  97     fprintf (f, "%" 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     fprintf (f, "%" PRId64 " (%s)", m_val,
 102              profile_quality_display_names[m_quality]);
 103 }
 104
 105 /* Dump THIS to stderr.  */
 106
 107 void
 108 profile_count::debug () const
 109 {
 110   dump (stderr, cfun);
 111   fprintf (stderr, "\n");
 112 }
 113
 114 /* Return true if THIS differs from OTHER; tolerate small differences.  */
 115
 116 bool
 117 profile_count::differs_from_p (profile_count other) const
 118 {
 119   gcc_checking_assert (compatible_p (other));
 120   if (!initialized_p () || !other.initialized_p ())
 121     return initialized_p () != other.initialized_p ();
 122   if ((uint64_t)m_val - (uint64_t)other.m_val < 100
 123       || (uint64_t)other.m_val - (uint64_t)m_val < 100)
 124     return false;
 125   if (!other.m_val)
 126     return true;
 127   uint64_t ratio;
 128   safe_scale_64bit (m_val, 100, other.m_val, &ratio);
 129   return ratio < 99 || ratio > 101;
 130 }
 131
 132 /* Stream THIS from IB.  */
 133
 134 profile_count
 135 profile_count::stream_in (class lto_input_block *ib)
 136 {
 137   profile_count ret;
 138   ret.m_val = streamer_read_gcov_count (ib);
 139   ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
 140   return ret;
 141 }
 142
 143 /* Stream THIS to OB.  */
 144
 145 void
 146 profile_count::stream_out (struct output_block *ob)
 147 {
 148   streamer_write_gcov_count (ob, m_val);
 149   streamer_write_uhwi (ob, m_quality);
 150 }
 151
 152 /* Stream THIS to OB.  */
 153
 154 void
 155 profile_count::stream_out (struct lto_output_stream *ob)
 156 {
 157   streamer_write_gcov_count_stream (ob, m_val);
 158   streamer_write_uhwi_stream (ob, m_quality);
 159 }
 160
 161
 162 /* Output THIS to BUFFER.  */
 163
 164 void
 165 profile_probability::dump (char *buffer) const
 166 {
 167   if (!initialized_p ())
 168     sprintf (buffer, "uninitialized");
 169   else
 170     {
 171       /* Make difference between 0.00 as a roundoff error and actual 0.
 172          Similarly for 1.  */
 173       if (m_val == 0)
 174         buffer += sprintf (buffer, "never");
 175       else if (m_val == max_probability)
 176         buffer += sprintf (buffer, "always");
 177       else
 178         buffer += sprintf (buffer, "%3.1f%%", (double)m_val * 100 / max_probability);
 179
 180       if (m_quality == ADJUSTED)
 181         sprintf (buffer, " (adjusted)");
 182       else if (m_quality == AFDO)
 183         sprintf (buffer, " (auto FDO)");
 184       else if (m_quality == GUESSED)
 185         sprintf (buffer, " (guessed)");
 186     }
 187 }
 188
 189 /* Dump THIS to F.  */
 190
 191 void
 192 profile_probability::dump (FILE *f) const
 193 {
 194   char buffer[64];
 195   dump (buffer);
 196   fputs (buffer, f);
 197 }
 198
 199 /* Dump THIS to stderr.  */
 200
 201 void
 202 profile_probability::debug () const
 203 {
 204   dump (stderr);
 205   fprintf (stderr, "\n");
 206 }
 207
 208 /* Return true if THIS differs from OTHER; tolerate small differences.  */
 209
 210 bool
 211 profile_probability::differs_from_p (profile_probability other) const
 212 {
 213   if (!initialized_p () || !other.initialized_p ())
 214     return false;
 215   if ((uint64_t)m_val - (uint64_t)other.m_val < max_probability / 1000
 216       || (uint64_t)other.m_val - (uint64_t)max_probability < 1000)
 217     return false;
 218   if (!other.m_val)
 219     return true;
 220   int64_t ratio = (int64_t)m_val * 100 / other.m_val;
 221   return ratio < 99 || ratio > 101;
 222 }
 223
 224 /* Return true if THIS differs significantly from OTHER.  */
 225
 226 bool
 227 profile_probability::differs_lot_from_p (profile_probability other) const
 228 {
 229   if (!initialized_p () || !other.initialized_p ())
 230     return false;
 231   uint32_t d = m_val > other.m_val ? m_val - other.m_val : other.m_val - m_val;
 232   return d > max_probability / 2;
 233 }
 234
 235 /* Stream THIS from IB.  */
 236
 237 profile_probability
 238 profile_probability::stream_in (class lto_input_block *ib)
 239 {
 240   profile_probability ret;
 241   ret.m_val = streamer_read_uhwi (ib);
 242   ret.m_quality = (profile_quality) streamer_read_uhwi (ib);
 243   return ret;
 244 }
 245
 246 /* Stream THIS to OB.  */
 247
 248 void
 249 profile_probability::stream_out (struct output_block *ob)
 250 {
 251   streamer_write_uhwi (ob, m_val);
 252   streamer_write_uhwi (ob, m_quality);
 253 }
 254
 255 /* Stream THIS to OB.  */
 256
 257 void
 258 profile_probability::stream_out (struct lto_output_stream *ob)
 259 {
 260   streamer_write_uhwi_stream (ob, m_val);
 261   streamer_write_uhwi_stream (ob, m_quality);
 262 }
 263
 264 /* Compute RES=(a*b + c/2)/c capping and return false if overflow happened.  */
 265
 266 bool
 267 slow_safe_scale_64bit (uint64_t a, uint64_t b, uint64_t c, uint64_t *res)
 268 {
 269   FIXED_WIDE_INT (128) tmp = a;
 270   wi::overflow_type overflow;
 271   tmp = wi::udiv_floor (wi::umul (tmp, b, &overflow) + (c / 2), c);
 272   gcc_checking_assert (!overflow);
 273   if (wi::fits_uhwi_p (tmp))
 274     {
 275       *res = tmp.to_uhwi ();
 276       return true;
 277     }
 278   *res = (uint64_t) -1;
 279   return false;
 280 }
 281
 282 /* Return count as frequency within FUN scaled in range 0 to REG_FREQ_MAX
 283    Used for legacy code and should not be used anymore.  */
 284
 285 int
 286 profile_count::to_frequency (struct function *fun) const
 287 {
 288   if (!initialized_p ())
 289     return BB_FREQ_MAX;
 290   if (*this == zero ())
 291     return 0;
 292   STATIC_ASSERT (REG_BR_PROB_BASE == BB_FREQ_MAX);
 293   gcc_assert (fun->cfg->count_max.initialized_p ());
 294   profile_probability prob = probability_in (fun->cfg->count_max);
 295   if (!prob.initialized_p ())
 296     return REG_BR_PROB_BASE;
 297   return prob.to_reg_br_prob_base ();
 298 }
 299
 300 /* Return count as frequency within FUN scaled in range 0 to CGRAPH_FREQ_MAX
 301    where CGRAPH_FREQ_BASE means that count equals to entry block count.
 302    Used for legacy code and should not be used anymore.  */
 303
 304 int
 305 profile_count::to_cgraph_frequency (profile_count entry_bb_count) const
 306 {
 307   if (!initialized_p () || !entry_bb_count.initialized_p ())
 308     return CGRAPH_FREQ_BASE;
 309   if (*this == zero ())
 310     return 0;
 311   gcc_checking_assert (entry_bb_count.initialized_p ());
 312   uint64_t scale;
 313   gcc_checking_assert (compatible_p (entry_bb_count));
 314   if (!safe_scale_64bit (!entry_bb_count.m_val ? m_val + 1 : m_val,
 315                          CGRAPH_FREQ_BASE, MAX (1, entry_bb_count.m_val), &scale))
 316     return CGRAPH_FREQ_MAX;
 317   return MIN (scale, CGRAPH_FREQ_MAX);
 318 }
 319
 320 /* Return THIS/IN as sreal value.  */
 321
 322 sreal
 323 profile_count::to_sreal_scale (profile_count in, bool *known) const
 324 {
 325   if (*this == zero ()
 326       && !(in == zero ()))
 327   {
 328     if (known)
 329       *known = true;
 330     return 0;
 331   }
 332   if (!initialized_p () || !in.initialized_p ())
 333     {
 334       if (known)
 335         *known = false;
 336       return 1;
 337     }
 338   if (known)
 339     *known = in.m_val != 0;
 340   if (*this == in)
 341     return 1;
 342   gcc_checking_assert (compatible_p (in));
 343   if (m_val == in.m_val)
 344     return 1;
 345   if (!in.m_val)
 346     return m_val * 4;
 347   return (sreal)m_val / (sreal)in.m_val;
 348 }
 349
 350 /* We want to scale profile across function boundary from NUM to DEN.
 351    Take care of the side case when DEN is zeros.  We still want to behave
 352    sanely here which means
 353      - scale to profile_count::zero () if NUM is profile_count::zero
 354      - do not affect anything if NUM == DEN
 355      - preserve counter value but adjust quality in other cases.  */
 356
 357 void
 358 profile_count::adjust_for_ipa_scaling (profile_count *num,
 359                                        profile_count *den)
 360 {
 361   /* Scaling is no-op if NUM and DEN are the same.  */
 362   if (*num == *den)
 363     return;
 364   /* Scaling to zero is always zero.  */
 365   if (*num == zero ())
 366     return;
 367   /* If den is non-zero we are safe.  */
 368   if (den->force_nonzero () == *den)
 369     return;
 370   /* Force both to non-zero so we do not push profiles to 0 when
 371      both num == 0 and den == 0.  */
 372   *den = den->force_nonzero ();
 373   *num = num->force_nonzero ();
 374 }
 375
 376 /* THIS is a count of bb which is known to be executed IPA times.
 377    Combine this information into bb counter.  This means returning IPA
 378    if it is nonzero, not changing anything if IPA is uninitialized
 379    and if IPA is zero, turning THIS into corresponding local profile with
 380    global0.  */
 381
 382 profile_count
 383 profile_count::combine_with_ipa_count (profile_count ipa)
 384 {
 385   if (!initialized_p ())
 386     return *this;
 387   ipa = ipa.ipa ();
 388   if (ipa.nonzero_p ())
 389     return ipa;
 390   if (!ipa.initialized_p () || *this == zero ())
 391     return *this;
 392   if (ipa == zero ())
 393     return this->global0 ();
 394   return this->global0adjusted ();
 395 }
 396
 397 /* Sae as profile_count::combine_with_ipa_count but within function with count
 398    IPA2.  */
 399 profile_count
 400 profile_count::combine_with_ipa_count_within (profile_count ipa,
 401                                               profile_count ipa2)
 402 {
 403   profile_count ret;
 404   if (!initialized_p ())
 405     return *this;
 406   if (ipa2.ipa () == ipa2 && ipa.initialized_p ())
 407     ret = ipa;
 408   else
 409     ret = combine_with_ipa_count (ipa);
 410   gcc_checking_assert (ret.compatible_p (ipa2));
 411   return ret;
 412 }
 413
 414 /* The profiling runtime uses gcov_type, which is usually 64bit integer.
 415    Conversions back and forth are used to read the coverage and get it
 416    into internal representation.  */
 417
 418 profile_count
 419 profile_count::from_gcov_type (gcov_type v, profile_quality quality)
 420   {
 421     profile_count ret;
 422     gcc_checking_assert (v >= 0);
 423     if (dump_file && v >= (gcov_type)max_count)
 424       fprintf (dump_file,
 425                "Capping gcov count %" PRId64 " to max_count %" PRId64 "\n",
 426                (int64_t) v, (int64_t) max_count);
 427     ret.m_val = MIN (v, (gcov_type)max_count);
 428     ret.m_quality = quality;
 429     return ret;
 430   }
 431
 432 /* COUNT1 times event happens with *THIS probability, COUNT2 times OTHER
 433    happens with COUNT2 probability.  Return probability that either *THIS or
 434    OTHER happens.  */
 435
 436 profile_probability
 437 profile_probability::combine_with_count (profile_count count1,
 438                                          profile_probability other,
 439                                          profile_count count2) const
 440 {
 441   /* If probabilities are same, we are done.
 442      If counts are nonzero we can distribute accordingly. In remaining
 443      cases just average the values and hope for the best.  */
 444   if (*this == other || count1 == count2
 445       || (count2 == profile_count::zero ()
 446           && !(count1 == profile_count::zero ())))
 447     return *this;
 448   if (count1 == profile_count::zero () && !(count2 == profile_count::zero ()))
 449     return other;
 450   else if (count1.nonzero_p () || count2.nonzero_p ())
 451     return *this * count1.probability_in (count1 + count2)
 452            + other * count2.probability_in (count1 + count2);
 453   else
 454     return *this * even () + other * even ();
 455 }
 456
 457 /* Return probability as sreal in range [0, 1].  */
 458
 459 sreal
 460 profile_probability::to_sreal () const
 461 {
 462   gcc_checking_assert (initialized_p ());
 463   return ((sreal)m_val) >> (n_bits - 2);
 464 }
 465
 466 /* Compute square root.  */
 467
 468 profile_probability
 469 profile_probability::sqrt () const
 470 {
 471   if (!initialized_p () || *this == never () || *this == always ())
 472     return *this;
 473   profile_probability ret = *this;
 474   ret.m_quality = MIN (ret.m_quality, ADJUSTED);
 475   uint32_t min_range = m_val;
 476   uint32_t max_range = max_probability;
 477   if (!m_val)
 478     max_range = 0;
 479   if (m_val == max_probability)
 480     min_range = max_probability;
 481   while (min_range != max_range)
 482     {
 483       uint32_t val = (min_range + max_range) / 2;
 484       uint32_t val2 = RDIV ((uint64_t)val * val, max_probability);
 485       if (val2 == m_val)
 486         min_range = max_range = m_val;
 487       else if (val2 > m_val)
 488         max_range = val - 1;
 489       else if (val2 < m_val)
 490         min_range = val + 1;
 491     }
 492   ret.m_val = min_range;
 493   return ret;
 494 }
 495
 496 /* Compute n-th power of THIS.  */
 497
 498 profile_probability
 499 profile_probability::pow (int n) const
 500 {
 501   if (n == 1 || !initialized_p ())
 502     return *this;
 503   if (!n)
 504     return profile_probability::always ();
 505   if (!nonzero_p ()
 506       || !(profile_probability::always () - *this).nonzero_p ())
 507     return *this;
 508   profile_probability ret = profile_probability::always ();
 509   profile_probability v = *this;
 510   int p = 1;
 511   while (true)
 512     {
 513       if (n & p)
 514         ret = ret * v;
 515       p <<= 1;
 516       if (p > n)
 517         break;
 518       v = v * v;
 519     }
 520   return ret;
 521 }