gcc/profile-count.c

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