[PATCH 8/9] Negative numbers added for sreal class.
Richard Biener
richard.guenther@gmail.com
Fri Nov 21 12:18:00 GMT 2014
On Fri, Nov 21, 2014 at 12:21 PM, Martin Liška <mliska@suse.cz> wrote:
> On 11/14/2014 11:48 AM, Richard Biener wrote:
>>
>> On Thu, Nov 13, 2014 at 1:35 PM, mliska <mliska@suse.cz> wrote:
>>>
>>> gcc/ChangeLog:
>>>
>>> 2014-11-13 Martin Liska <mliska@suse.cz>
>>>
>>> * 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
>>> <http://www.gnu.org/licenses/>. */
>>>
>>> -/* 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);
}
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)?
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.
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
>>>
>>>
>
More information about the Gcc-patches
mailing list