On 11/21/2014 01:03 PM, Richard Biener wrote: > On Fri, Nov 21, 2014 at 12:21 PM, Martin Liška wrote: >> On 11/14/2014 11:48 AM, Richard Biener wrote: >>> >>> On Thu, Nov 13, 2014 at 1:35 PM, mliska wrote: >>>> >>>> gcc/ChangeLog: >>>> >>>> 2014-11-13 Martin Liska >>>> >>>> * predict.c (propagate_freq): More elegant sreal API is used. >>>> (estimate_bb_frequencies): New static constants defined by sreal >>>> replace precomputed ones. >>>> * sreal.c (sreal::normalize): New function. >>>> (sreal::to_int): Likewise. >>>> (sreal::operator+): Likewise. >>>> (sreal::operator-): Likewise. >>>> * sreal.h: Definition of new functions added. >>> >>> >>> Please use gcc_checking_assert()s everywhere. sreal is supposed >>> to be fast... (I see it has current uses of gcc_assert - you may want >>> to mass-convert them as a followup). >>> >>>> --- >>>> gcc/predict.c | 30 +++++++++++------------- >>>> gcc/sreal.c | 56 ++++++++++++++++++++++++++++++++++++-------- >>>> gcc/sreal.h | 75 >>>> ++++++++++++++++++++++++++++++++++++++++++++++++++++------- >>>> 3 files changed, 126 insertions(+), 35 deletions(-) >>>> >>>> diff --git a/gcc/predict.c b/gcc/predict.c >>>> index 0215e91..0f640f5 100644 >>>> --- a/gcc/predict.c >>>> +++ b/gcc/predict.c >>>> @@ -82,7 +82,7 @@ along with GCC; see the file COPYING3. If not see >>>> >>>> /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, >>>> 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */ >>>> -static sreal real_zero, real_one, real_almost_one, real_br_prob_base, >>>> +static sreal real_almost_one, real_br_prob_base, >>>> real_inv_br_prob_base, real_one_half, real_bb_freq_max; >>>> >>>> static void combine_predictions_for_insn (rtx_insn *, basic_block); >>>> @@ -2528,13 +2528,13 @@ propagate_freq (basic_block head, bitmap tovisit) >>>> bb->count = bb->frequency = 0; >>>> } >>>> >>>> - BLOCK_INFO (head)->frequency = real_one; >>>> + BLOCK_INFO (head)->frequency = sreal::one (); >>>> last = head; >>>> for (bb = head; bb; bb = nextbb) >>>> { >>>> edge_iterator ei; >>>> - sreal cyclic_probability = real_zero; >>>> - sreal frequency = real_zero; >>>> + sreal cyclic_probability = sreal::zero (); >>>> + sreal frequency = sreal::zero (); >>>> >>>> nextbb = BLOCK_INFO (bb)->next; >>>> BLOCK_INFO (bb)->next = NULL; >>>> @@ -2559,13 +2559,13 @@ propagate_freq (basic_block head, bitmap tovisit) >>>> * BLOCK_INFO (e->src)->frequency / >>>> REG_BR_PROB_BASE); */ >>>> >>>> - sreal tmp (e->probability, 0); >>>> + sreal tmp = e->probability; >>>> tmp *= BLOCK_INFO (e->src)->frequency; >>>> tmp *= real_inv_br_prob_base; >>>> frequency += tmp; >>>> } >>>> >>>> - if (cyclic_probability == real_zero) >>>> + if (cyclic_probability == sreal::zero ()) >>>> { >>>> BLOCK_INFO (bb)->frequency = frequency; >>>> } >>>> @@ -2577,7 +2577,7 @@ propagate_freq (basic_block head, bitmap tovisit) >>>> /* BLOCK_INFO (bb)->frequency = frequency >>>> / (1 - cyclic_probability) >>>> */ >>>> >>>> - cyclic_probability = real_one - cyclic_probability; >>>> + cyclic_probability = sreal::one () - cyclic_probability; >>>> BLOCK_INFO (bb)->frequency = frequency / >>>> cyclic_probability; >>>> } >>>> } >>>> @@ -2591,7 +2591,7 @@ propagate_freq (basic_block head, bitmap tovisit) >>>> = ((e->probability * BLOCK_INFO (bb)->frequency) >>>> / REG_BR_PROB_BASE); */ >>>> >>>> - sreal tmp (e->probability, 0); >>>> + sreal tmp = e->probability; >>>> tmp *= BLOCK_INFO (bb)->frequency; >>>> EDGE_INFO (e)->back_edge_prob = tmp * real_inv_br_prob_base; >>>> } >>>> @@ -2873,13 +2873,11 @@ estimate_bb_frequencies (bool force) >>>> if (!real_values_initialized) >>>> { >>>> real_values_initialized = 1; >>>> - real_zero = sreal (0, 0); >>>> - real_one = sreal (1, 0); >>>> - real_br_prob_base = sreal (REG_BR_PROB_BASE, 0); >>>> - real_bb_freq_max = sreal (BB_FREQ_MAX, 0); >>>> + real_br_prob_base = REG_BR_PROB_BASE; >>>> + real_bb_freq_max = BB_FREQ_MAX; >>>> real_one_half = sreal (1, -1); >>>> - real_inv_br_prob_base = real_one / real_br_prob_base; >>>> - real_almost_one = real_one - real_inv_br_prob_base; >>>> + real_inv_br_prob_base = sreal::one () / real_br_prob_base; >>>> + real_almost_one = sreal::one () - real_inv_br_prob_base; >>>> } >>>> >>>> mark_dfs_back_edges (); >>>> @@ -2897,7 +2895,7 @@ estimate_bb_frequencies (bool force) >>>> >>>> FOR_EACH_EDGE (e, ei, bb->succs) >>>> { >>>> - EDGE_INFO (e)->back_edge_prob = sreal (e->probability, 0); >>>> + EDGE_INFO (e)->back_edge_prob = e->probability; >>>> EDGE_INFO (e)->back_edge_prob *= real_inv_br_prob_base; >>>> } >>>> } >>>> @@ -2906,7 +2904,7 @@ estimate_bb_frequencies (bool force) >>>> to outermost to examine frequencies for back edges. */ >>>> estimate_loops (); >>>> >>>> - freq_max = real_zero; >>>> + freq_max = sreal::zero (); >>>> FOR_EACH_BB_FN (bb, cfun) >>>> if (freq_max < BLOCK_INFO (bb)->frequency) >>>> freq_max = BLOCK_INFO (bb)->frequency; >>>> diff --git a/gcc/sreal.c b/gcc/sreal.c >>>> index 3f5456a..89b9c4d 100644 >>>> --- a/gcc/sreal.c >>>> +++ b/gcc/sreal.c >>>> @@ -1,4 +1,4 @@ >>>> -/* Simple data type for positive real numbers for the GNU compiler. >>>> +/* Simple data type for real numbers for the GNU compiler. >>>> Copyright (C) 2002-2014 Free Software Foundation, Inc. >>>> >>>> This file is part of GCC. >>>> @@ -17,7 +17,7 @@ You should have received a copy of the GNU General >>>> Public License >>>> along with GCC; see the file COPYING3. If not see >>>> . */ >>>> >>>> -/* This library supports positive real numbers and 0; >>>> +/* This library supports real numbers; >>>> inf and nan are NOT supported. >>>> It is written to be simple and fast. >>>> >>>> @@ -102,6 +102,7 @@ sreal::normalize () >>>> { >>>> if (m_sig == 0) >>>> { >>>> + m_negative = 0; >>>> m_exp = -SREAL_MAX_EXP; >>>> } >>>> else if (m_sig < SREAL_MIN_SIG) >>>> @@ -153,15 +154,17 @@ sreal::normalize () >>>> int64_t >>>> sreal::to_int () const >>>> { >>>> + int64_t sign = m_negative ? -1 : 1; >>>> + >>>> if (m_exp <= -SREAL_BITS) >>>> return 0; >>>> if (m_exp >= SREAL_PART_BITS) >>>> - return INTTYPE_MAXIMUM (int64_t); >>>> + return sign * INTTYPE_MAXIMUM (int64_t); >>>> if (m_exp > 0) >>>> - return m_sig << m_exp; >>>> + return sign * (m_sig << m_exp); >>>> if (m_exp < 0) >>>> - return m_sig >> -m_exp; >>>> - return m_sig; >>>> + return sign * (m_sig >> -m_exp); >>>> + return sign * m_sig; >>>> } >>>> >>>> /* Return *this + other. */ >>>> @@ -169,9 +172,19 @@ sreal::to_int () const >>>> sreal >>>> sreal::operator+ (const sreal &other) const >>>> { >>>> + const sreal *a_p = this, *b_p = &other, *bb; >>>> + >>>> + if (m_negative && !other.m_negative) >>>> + return other + *a_p; >>>> + >>>> + if (!m_negative && other.m_negative) >>>> + return *a_p - -other; >>>> + >>>> + gcc_assert (m_negative == other.m_negative); >>>> + >>>> int dexp; >>>> sreal tmp, r; >>>> -const sreal *a_p = this, *b_p = &other, *bb; >>>> + r.m_negative = a_p->m_negative; >>>> >>>> if (*a_p < *b_p) >>>> { >>>> @@ -211,10 +224,30 @@ sreal::operator- (const sreal &other) const >>>> int dexp; >>>> sreal tmp, r; >>>> const sreal *bb; >>>> + const sreal *a_p = this; >>>> + >>>> + /* -a - b => -a + (-b). */ >>>> + if (m_negative && !other.m_negative) >>>> + return *a_p + -other; >>>> >>>> - gcc_assert (*this >= other); >>>> + /* a - (-b) => a + b. */ >>>> + if (!m_negative && other.m_negative) >>>> + return *a_p + -other; >>>> + >>>> + gcc_assert (m_negative == other.m_negative); >>>> + >>>> + /* We want to substract a smaller number from bigger >>>> + for nonegative numbers. */ >>>> + if (!m_negative && *this < other) >>>> + return -(other - *this); >>>> + >>>> + /* Example: -2 - (-3) => 3 - 2 */ >>>> + if (m_negative && *this > other) >>>> + return -other - -(*this); >>>> >>>> dexp = m_exp - other.m_exp; >>>> + >>>> + r.m_negative = m_negative; >>>> r.m_exp = m_exp; >>>> if (dexp > SREAL_BITS) >>>> { >>>> @@ -240,7 +273,7 @@ sreal::operator- (const sreal &other) const >>>> sreal >>>> sreal::operator* (const sreal &other) const >>>> { >>>> -sreal r; >>>> + sreal r; >>>> if (m_sig < SREAL_MIN_SIG || other.m_sig < SREAL_MIN_SIG) >>>> { >>>> r.m_sig = 0; >>>> @@ -252,6 +285,8 @@ sreal r; >>>> r.m_exp = m_exp + other.m_exp; >>>> r.normalize (); >>>> } >>>> + >>>> + r.m_negative = m_negative ^ other.m_negative; >>>> return r; >>>> } >>>> >>>> @@ -261,9 +296,10 @@ sreal >>>> sreal::operator/ (const sreal &other) const >>>> { >>>> gcc_assert (other.m_sig != 0); >>>> -sreal r; >>>> + sreal r; >>>> r.m_sig = (m_sig << SREAL_PART_BITS) / other.m_sig; >>>> r.m_exp = m_exp - other.m_exp - SREAL_PART_BITS; >>>> + r.m_negative = m_negative ^ other.m_negative; >>>> r.normalize (); >>>> return r; >>>> } >>>> diff --git a/gcc/sreal.h b/gcc/sreal.h >>>> index 461e28b..bfed3c7 100644 >>>> --- a/gcc/sreal.h >>>> +++ b/gcc/sreal.h >>>> @@ -1,4 +1,4 @@ >>>> -/* Definitions for simple data type for positive real numbers. >>>> +/* Definitions for simple data type for real numbers. >>>> Copyright (C) 2002-2014 Free Software Foundation, Inc. >>>> >>>> This file is part of GCC. >>>> @@ -25,7 +25,7 @@ along with GCC; see the file COPYING3. If not see >>>> >>>> #define SREAL_MIN_SIG ((uint64_t) 1 << (SREAL_PART_BITS - 1)) >>>> #define SREAL_MAX_SIG (((uint64_t) 1 << SREAL_PART_BITS) - 1) >>>> -#define SREAL_MAX_EXP (INT_MAX / 4) >>>> +#define SREAL_MAX_EXP (INT_MAX / 8) >>>> >>>> #define SREAL_BITS SREAL_PART_BITS >>>> >>>> @@ -34,10 +34,21 @@ class sreal >>>> { >>>> public: >>>> /* Construct an uninitialized sreal. */ >>>> - sreal () : m_sig (-1), m_exp (-1) {} >>>> + sreal () : m_sig (-1), m_exp (-1), m_negative (0) {} >>>> >>>> /* Construct a sreal. */ >>>> - sreal (uint64_t sig, int exp) : m_sig (sig), m_exp (exp) { normalize >>>> (); } >>>> + sreal (int64_t sig, int exp = 0) : m_exp (exp) >>>> + { >>>> + m_negative = sig < 0; >>>> + >>>> + // TODO: speed up >>>> + if (sig < 0) >>>> + sig = -sig; >>> >>> >>> also undefined behavior for sig == int64_min ... >>> >>>> + >>>> + m_sig = (uint64_t) sig; >>> >>> >>> any reason for not making m_sig signed and using the sign of m_sig >>> as sign of the sreal? >>> >>>> + >>>> + normalize (); >>>> + } >>>> >>>> void dump (FILE *) const; >>>> int64_t to_int () const; >>>> @@ -49,13 +60,58 @@ public: >>>> >>>> bool operator< (const sreal &other) const >>>> { >>>> - return m_exp < other.m_exp >>>> + if (m_negative != other.m_negative) >>>> + return m_negative > other.m_negative; >>>> + >>>> + bool r = m_exp < other.m_exp >>>> || (m_exp == other.m_exp && m_sig < other.m_sig); >>>> + >>>> + return m_negative ? !r : r; >>>> } >>>> >>>> bool operator== (const sreal &other) const >>>> { >>>> - return m_exp == other.m_exp && m_sig == other.m_sig; >>>> + return m_exp == other.m_exp && m_sig == other.m_sig >>>> + && m_negative == other.m_negative; >>>> + } >>>> + >>>> + sreal operator- () const >>>> + { >>>> + if (m_sig == 0) >>>> + return *this; >>>> + >>>> + sreal tmp = *this; >>>> + tmp.m_negative = !tmp.m_negative; >>>> + >>>> + return tmp; >>>> + } >>>> + >>>> + sreal shift (int sig) const >>>> + { >>>> + sreal tmp = *this; >>>> + tmp.m_sig += sig; >>>> + >>>> + return tmp; >>>> + } >>>> + >>>> + /* Return zero constant. */ >>>> + inline static sreal zero () >>>> + { >>>> + static const sreal zero = sreal (0); >>>> + return zero; >>>> + } >>>> + >>>> + /* Return one constant. */ >>>> + inline static sreal one () >>>> + { >>>> + static const sreal one = sreal (1); >>>> + return one; >>>> + } >>>> + >>>> + /* Global minimum sreal can hold. */ >>>> + inline static sreal min () >>>> + { >>>> + return sreal (LONG_MIN, 0); >>>> } >>>> >>>> private: >>>> @@ -63,7 +119,8 @@ private: >>>> void shift_right (int amount); >>>> >>>> uint64_t m_sig; /* Significant. */ >>>> - signed int m_exp; /* Exponent. */ >>>> + signed int m_exp: 31; /* Exponent. */ >>>> + unsigned int m_negative: 1; /* Negative sign. */ >>> >>> >>> As this gets padded to 2 * 64bits I wonder if it is necessary to >>> get the slowdowns for using bitfields here. I'd have just used >>> >>> uint64_t m_sig; /* Significant. */ >>> signed int m_exp; /* Exponent. */ >>> bool m_negative; >>> >>> or making m_sig signed... >>> >>> Thanks, >>> Richard. >> >> >> Hello. >> >> I tries to fix all notes I was given in this thread. There's list of >> updates: >> 1) signedless_{plus}|{minus} was introduced and there's no more recursion >> coming from operator+|-. >> 2) Bitfields are not used. >> 3) New function to_double is added. >> 4) gcc_assert is converted to gcc_checking_assert. >> >> With having this patch applied I was able to reach the same time (difference >> is in noise level) for Inkscape WPA phase. >> >> What do you think about it? > > What's the point of sreal::zero and sreal::one when sreal (0) and > sreal (1) work and when you could add > > sreal& operator=(int64_t sig) { new sreal (this) (sig); } > > ? > > + /* Global minimum sreal can hold. */ > + inline static sreal min () > + { > + return sreal (LONG_MIN, 0); > } Hello. Ok, this is simplified, one can use sreal a = 12345 and it works ;) > that's a new API, right? There is no max () and I think that using > LONG_MIN here is asking for trouble (host dependence). The > comment in the file says the max should be > sreal (SREAL_MAX_SIG, SREAL_MAX_EXP) and the min > sreal (-SREAL_MAX_SIG, SREAL_MAX_EXP)? > Sure, sreal can store much bigger(smaller) numbers :) > Where do you need sreal::to_double? The host shouldn't perform > double calculations so it can be only for dumping? In which case > the user should have used sreal::dump (), maybe with extra > arguments. > That new function was request from Honza, only for debugging purpose. I agree that dump should this kind of job. If no other problem, I will run tests once more and commit it. Thanks, Martin > Otherwise looks good to me and sorry for not noticing the above > earlier. > > Thanks, > Richard. > >> Thanks, >> Martin >> >> >>>> }; >>>> >>>> extern void debug (sreal &ref); >>>> @@ -76,12 +133,12 @@ inline sreal &operator+= (sreal &a, const sreal &b) >>>> >>>> inline sreal &operator-= (sreal &a, const sreal &b) >>>> { >>>> -return a = a - b; >>>> + return a = a - b; >>>> } >>>> >>>> inline sreal &operator/= (sreal &a, const sreal &b) >>>> { >>>> -return a = a / b; >>>> + return a = a / b; >>>> } >>>> >>>> inline sreal &operator*= (sreal &a, const sreal &b) >>>> -- >>>> 2.1.2 >>>> >>>> >>