gcc/profile-count.c

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