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