gcc/profile-count.h

   1 /* Profile counter container type.
   2    Copyright (C) 2017 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 #ifndef GCC_PROFILE_COUNT_H
  22 #define GCC_PROFILE_COUNT_H
  23
  24 /* Quality of the proflie count.  Because gengtype does not support enums
  25    inside of clases, this is in global namespace.  */
  26 enum profile_count_quality {
  27   /* Profile is based on static branch prediction heuristics.  It may or may
  28      not reflect the reality.  */
  29   count_guessed = 0,
  30   /* Profile was determined by autofdo.  */
  31   count_afdo = 1,
  32   /* Profile was originally based on feedback but it was adjusted
  33      by code duplicating optimization.  It may not precisely reflect the
  34      particular code path.  */
  35   count_adjusted = 2,
  36   /* Profile was read from profile feedback or determined by accurate static
  37      method.  */
  38   count_read = 3
  39 };
  40
  41 /* The base value for branch probability notes and edge probabilities.  */
  42 #define REG_BR_PROB_BASE  10000
  43
  44 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
  45
  46 /* Main data type to hold profile counters in GCC.  In most cases profile
  47    counts originate from profile feedback. They are 64bit integers
  48    representing number of executions during the train run.
  49    As the profile is maintained during the compilation, many adjustments are
  50    made.  Not all transformations can be made precisely, most importantly
  51    when code is being duplicated.  It also may happen that part of CFG has
  52    profile counts known while other do not - for example when LTO optimizing
  53    partly profiled program or when profile was lost due to COMDAT merging.
  54
  55    For this reason profile_count tracks more information than
  56    just unsigned integer and it is also ready for profile mismatches.
  57    The API of this data type represent operations that are natural
  58    on profile counts - sum, difference and operation with scales and
  59    probabilities.  All operations are safe by never getting negative counts
  60    and they do end up in uninitialized scale if any of the parameters is
  61    uninitialized.
  62
  63    All comparsions that are three state and handling of probabilities.  Thus
  64    a < b is not equal to !(a >= b).
  65
  66    The following pre-defined counts are available:
  67
  68    profile_count::zero ()  for code that is known to execute zero times at
  69       runtime (this can be detected statically i.e. for paths leading to
  70       abort ();
  71    profile_count::one () for code that is known to execute once (such as
  72       main () function
  73    profile_count::uninitialized ()  for unknown execution count.
  74
  75  */
  76
  77 class GTY(()) profile_count
  78 {
  79   /* Use 62bit to hold basic block counters.  Should be at least
  80      64bit.  Although a counter cannot be negative, we use a signed
  81      type to hold various extra stages.  */
  82
  83   static const int n_bits = 62;
  84   static const uint64_t max_count = ((uint64_t) 1 << n_bits) - 2;
  85   static const uint64_t uninitialized_count = ((uint64_t) 1 << n_bits) - 1;
  86
  87   uint64_t m_val : n_bits;
  88   enum profile_count_quality m_quality : 2;
  89
  90   /* Assume numbers smaller than this to multiply.  This is set to make
  91      testsuite pass, in future we may implement precise multiplication in higer
  92      rangers.  */
  93   static const int64_t max_safe_multiplier = 131072;
  94 public:
  95
  96   /* Used for counters which are expected to be never executed.  */
  97   static profile_count zero ()
  98     {
  99       return from_gcov_type (0);
 100     }
 101   static profile_count one ()
 102     {
 103       return from_gcov_type (1);
 104     }
 105   /* Value of counters which has not been initialized. Either because
 106      initialization did not happen yet or because profile is unknown.  */
 107   static profile_count uninitialized ()
 108     {
 109       profile_count c;
 110       c.m_val = uninitialized_count;
 111       c.m_quality = count_guessed;
 112       return c;
 113     }
 114
 115   /* The profiling runtime uses gcov_type, which is usually 64bit integer.
 116      Conversions back and forth are used to read the coverage and get it
 117      into internal representation.  */
 118   static profile_count from_gcov_type (gcov_type v)
 119     {
 120       profile_count ret;
 121       gcc_checking_assert (v >= 0 && (uint64_t) v <= max_count);
 122       ret.m_val = v;
 123       ret.m_quality = count_read;
 124       return ret;
 125     }
 126
 127   /* Conversion to gcov_type is lossy.  */
 128   gcov_type to_gcov_type () const
 129     {
 130       gcc_checking_assert (initialized_p ());
 131       return m_val;
 132     }
 133
 134   /* Return true if value has been initialized.  */
 135   bool initialized_p () const
 136     {
 137       return m_val != uninitialized_count;
 138     }
 139   /* Return true if value can be trusted.  */
 140   bool reliable_p () const
 141     {
 142       return initialized_p ();
 143     }
 144
 145   /* Basic operations.  */
 146   bool operator== (const profile_count &other) const
 147     {
 148       return m_val == other.m_val && m_quality == other.m_quality;
 149     }
 150   profile_count operator+ (const profile_count &other) const
 151     {
 152       if (other == profile_count::zero ())
 153         return *this;
 154       if (*this == profile_count::zero ())
 155         return other;
 156       if (!initialized_p () || !other.initialized_p ())
 157         return profile_count::uninitialized ();
 158
 159       profile_count ret;
 160       ret.m_val = m_val + other.m_val;
 161       ret.m_quality = MIN (m_quality, other.m_quality);
 162       return ret;
 163     }
 164   profile_count &operator+= (const profile_count &other)
 165     {
 166       if (other == profile_count::zero ())
 167         return *this;
 168       if (*this == profile_count::zero ())
 169         {
 170           *this = other;
 171           return *this;
 172         }
 173       if (!initialized_p () || !other.initialized_p ())
 174         return *this = profile_count::uninitialized ();
 175       else
 176         {
 177           m_val += other.m_val;
 178           m_quality = MIN (m_quality, other.m_quality);
 179         }
 180       return *this;
 181     }
 182   profile_count operator- (const profile_count &other) const
 183     {
 184       if (*this == profile_count::zero () || other == profile_count::zero ())
 185         return *this;
 186       if (!initialized_p () || !other.initialized_p ())
 187         return profile_count::uninitialized ();
 188       profile_count ret;
 189       ret.m_val = m_val >= other.m_val ? m_val - other.m_val : 0;
 190       ret.m_quality = MIN (m_quality, other.m_quality);
 191       return ret;
 192     }
 193   profile_count &operator-= (const profile_count &other)
 194     {
 195       if (*this == profile_count::zero () || other == profile_count::zero ())
 196         return *this;
 197       if (!initialized_p () || !other.initialized_p ())
 198         return *this = profile_count::uninitialized ();
 199       else
 200         {
 201           m_val = m_val >= other.m_val ? m_val - other.m_val: 0;
 202           m_quality = MIN (m_quality, other.m_quality);
 203         }
 204       return *this;
 205     }
 206
 207   /* Return false if profile_count is bogus.  */
 208   bool verify () const
 209     {
 210       return m_val != uninitialized_count || m_quality == count_guessed;
 211     }
 212
 213   /* Comparsions are three-state and conservative.  False is returned if
 214      the inequality can not be decided.  */
 215   bool operator< (const profile_count &other) const
 216     {
 217       return initialized_p () && other.initialized_p () && m_val < other.m_val;
 218     }
 219   bool operator> (const profile_count &other) const
 220     {
 221       return initialized_p () && other.initialized_p () && m_val > other.m_val;
 222     }
 223   bool operator< (const gcov_type other) const
 224     {
 225       gcc_checking_assert (other >= 0);
 226       return initialized_p () && m_val < (uint64_t) other;
 227     }
 228   bool operator> (const gcov_type other) const
 229     {
 230       gcc_checking_assert (other >= 0);
 231       return initialized_p () && m_val > (uint64_t) other;
 232     }
 233
 234   bool operator<= (const profile_count &other) const
 235     {
 236       return initialized_p () && other.initialized_p () && m_val <= other.m_val;
 237     }
 238   bool operator>= (const profile_count &other) const
 239     {
 240       return initialized_p () && m_val >= other.m_val;
 241     }
 242   bool operator<= (const gcov_type other) const
 243     {
 244       gcc_checking_assert (other >= 0);
 245       return initialized_p () && m_val <= (uint64_t) other;
 246     }
 247   bool operator>= (const gcov_type other) const
 248     {
 249       gcc_checking_assert (other >= 0);
 250       return initialized_p () && m_val >= (uint64_t) other;
 251     }
 252
 253   /* PROB is a probability in scale 0...REG_BR_PROB_BASE.  Scale counter
 254      accordingly.  */
 255   profile_count apply_probability (int prob) const
 256     {
 257       gcc_checking_assert (prob >= 0 && prob <= REG_BR_PROB_BASE);
 258       if (m_val == 0)
 259         return *this;
 260       if (!initialized_p ())
 261         return profile_count::uninitialized ();
 262       profile_count ret;
 263       ret.m_val = RDIV (m_val * prob, REG_BR_PROB_BASE);
 264       ret.m_quality = MIN (m_quality, count_adjusted);
 265       return ret;
 266     }
 267   /* Return *THIS * NUM / DEN.  */
 268   profile_count apply_scale (int64_t num, int64_t den) const
 269     {
 270       if (m_val == 0)
 271         return *this;
 272       if (!initialized_p ())
 273         return profile_count::uninitialized ();
 274       profile_count ret;
 275       gcc_checking_assert (num >= 0 && den > 0);
 276       /* FIXME: shrink wrapping violates this sanity check.  */
 277       gcc_checking_assert ((num <= REG_BR_PROB_BASE
 278                             || den <= REG_BR_PROB_BASE) || 1);
 279       ret.m_val = RDIV (m_val * num, den);
 280       ret.m_quality = MIN (m_quality, count_adjusted);
 281       return ret;
 282     }
 283   profile_count apply_scale (profile_count num, profile_count den) const
 284     {
 285       if (m_val == 0)
 286         return *this;
 287       if (num.m_val == 0)
 288         return num;
 289       if (!initialized_p () || !num.initialized_p () || !den.initialized_p ())
 290         return profile_count::uninitialized ();
 291       gcc_checking_assert (den > 0);
 292       if (num == den)
 293         return *this;
 294
 295       profile_count ret;
 296       /* Take care for overflows!  */
 297       if (num.m_val < max_safe_multiplier || m_val < max_safe_multiplier)
 298         ret.m_val = RDIV (m_val * num.m_val, den.m_val);
 299       else
 300         ret.m_val = RDIV (m_val * RDIV (num.m_val * max_safe_multiplier,
 301                                         den.m_val), max_safe_multiplier);
 302       ret.m_quality = MIN (m_quality, count_adjusted);
 303       return ret;
 304     }
 305
 306   /* Return probability of event with counter THIS within event with counter
 307      OVERALL.  */
 308   int probability_in (profile_count overall)
 309     {
 310       if (!m_val)
 311         return 0;
 312       if (!initialized_p () || !overall.initialized_p ())
 313         return REG_BR_PROB_BASE / 2;
 314       if (overall < *this)
 315         return REG_BR_PROB_BASE;
 316       if (!overall.m_val)
 317         return REG_BR_PROB_BASE / 2;
 318       return RDIV (m_val * REG_BR_PROB_BASE, overall.m_val);
 319     }
 320
 321   /* Output THIS to F.  */
 322   void dump (FILE *f) const;
 323
 324   /* Print THIS to stderr.  */
 325   void debug () const;
 326
 327   /* Return true if THIS is known to differ significantly from OTHER.  */
 328   bool differs_from_p (profile_count other) const;
 329
 330   /* LTO streaming support.  */
 331   static profile_count stream_in (struct lto_input_block *);
 332   void stream_out (struct output_block *);
 333   void stream_out (struct lto_output_stream *);
 334 };
 335 #endif