From fd27ffab14e3b7c131cc2e454edcd11c9cc53c2e Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Mon, 24 Nov 2014 11:41:18 +0100 Subject: [PATCH] [PATCH 1/2] Negative numbers added for sreal class. * predict.c (propagate_freq): More elegant sreal API is used. (estimate_bb_frequencies): Precomputed constants replaced by integer constants. * sreal.c (sreal::normalize): New function. (sreal::to_int): Likewise. (sreal::operator+): Likewise. (sreal::operator-): Likewise. (sreal::signedless_plus): Likewise. (sreal::signedless_minus): Likewise. (sreal::operator/): Negative number support is added. * sreal.h: Definition of new functions added. (inline sreal operator<<): New function. (inline sreal operator>>): Likewise. From-SVN: r218008 --- gcc/ChangeLog | 16 +++++++ gcc/predict.c | 30 +++++++------ gcc/sreal.c | 114 ++++++++++++++++++++++++++++++++++++++------------ gcc/sreal.h | 82 ++++++++++++++++++++++++++++++++---- 4 files changed, 190 insertions(+), 52 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 562ef8a0582..48dccf32d8e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,19 @@ +2014-11-24 Martin Liska + + * predict.c (propagate_freq): More elegant sreal API is used. + (estimate_bb_frequencies): Precomputed constants replaced by integer + constants. + * sreal.c (sreal::normalize): New function. + (sreal::to_int): Likewise. + (sreal::operator+): Likewise. + (sreal::operator-): Likewise. + (sreal::signedless_plus): Likewise. + (sreal::signedless_minus): Likewise. + (sreal::operator/): Negative number support is added. + * sreal.h: Definition of new functions added. + (inline sreal operator<<): New function. + (inline sreal operator>>): Likewise. + 2014-11-24 Kyrylo Tkachov * config/aarch64/aarch64-protos.h (struct tune_params): Add diff --git a/gcc/predict.c b/gcc/predict.c index 779af115b2a..0cfe4a93a31 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); @@ -2541,13 +2541,13 @@ propagate_freq (basic_block head, bitmap tovisit) bb->count = bb->frequency = 0; } - BLOCK_INFO (head)->frequency = real_one; + BLOCK_INFO (head)->frequency = 1; last = head; for (bb = head; bb; bb = nextbb) { edge_iterator ei; - sreal cyclic_probability = real_zero; - sreal frequency = real_zero; + sreal cyclic_probability = 0; + sreal frequency = 0; nextbb = BLOCK_INFO (bb)->next; BLOCK_INFO (bb)->next = NULL; @@ -2572,13 +2572,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 == 0) { BLOCK_INFO (bb)->frequency = frequency; } @@ -2590,7 +2590,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 (1) - cyclic_probability; BLOCK_INFO (bb)->frequency = frequency / cyclic_probability; } } @@ -2604,7 +2604,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; } @@ -2886,13 +2886,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 (1) / real_br_prob_base; + real_almost_one = sreal (1) - real_inv_br_prob_base; } mark_dfs_back_edges (); @@ -2910,7 +2908,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; } } @@ -2919,7 +2917,7 @@ estimate_bb_frequencies (bool force) to outermost to examine frequencies for back edges. */ estimate_loops (); - freq_max = real_zero; + freq_max = 0; 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 3f5456ac2e3..0337f9e540c 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. @@ -82,12 +82,12 @@ debug (sreal *ptr) void sreal::shift_right (int s) { - gcc_assert (s > 0); - gcc_assert (s <= SREAL_BITS); + gcc_checking_assert (s > 0); + gcc_checking_assert (s <= SREAL_BITS); /* Exponent should never be so large because shift_right is used only by sreal_add and sreal_sub ant thus the number cannot be shifted out from exponent range. */ - gcc_assert (m_exp + s <= SREAL_MAX_EXP); + gcc_checking_assert (m_exp + s <= SREAL_MAX_EXP); m_exp += s; @@ -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,18 +172,40 @@ sreal::to_int () const sreal sreal::operator+ (const sreal &other) const { - int dexp; - sreal tmp, r; -const sreal *a_p = this, *b_p = &other, *bb; + const sreal *a_p = this, *b_p = &other; - if (*a_p < *b_p) + if (a_p->m_negative && !b_p->m_negative) + std::swap (a_p, b_p); + + /* a + -b => a - b. */ + if (!a_p->m_negative && b_p->m_negative) { - const sreal *swap; - swap = a_p; - a_p = b_p; - b_p = swap; + sreal tmp = -(*b_p); + if (*a_p < tmp) + return signedless_minus (tmp, *a_p, false); + else + return signedless_minus (*a_p, tmp, true); } + gcc_checking_assert (a_p->m_negative == b_p->m_negative); + + sreal r = signedless_plus (*a_p, *b_p, a_p->m_negative); + + return r; +} + +sreal +sreal::signedless_plus (const sreal &a, const sreal &b, bool negative) +{ + const sreal *bb; + sreal r, tmp; + int dexp; + const sreal *a_p = &a; + const sreal *b_p = &b; + + if (*a_p < *b_p) + std::swap (a_p, b_p); + dexp = a_p->m_exp - b_p->m_exp; r.m_exp = a_p->m_exp; if (dexp > SREAL_BITS) @@ -200,6 +225,8 @@ const sreal *a_p = this, *b_p = &other, *bb; r.m_sig = a_p->m_sig + bb->m_sig; r.normalize (); + + r.m_negative = negative; return r; } @@ -207,31 +234,61 @@ const sreal *a_p = this, *b_p = &other, *bb; sreal sreal::operator- (const sreal &other) const +{ + /* -a - b => -a + (-b). */ + if (m_negative && !other.m_negative) + return signedless_plus (*this, -other, true); + + /* a - (-b) => a + b. */ + if (!m_negative && other.m_negative) + return signedless_plus (*this, -other, false); + + gcc_checking_assert (m_negative == other.m_negative); + + /* We want to substract a smaller number from bigger + for nonegative numbers. */ + if (!m_negative && *this < other) + return -signedless_minus (other, *this, true); + + /* Example: -2 - (-3) => 3 - 2 */ + if (m_negative && *this > other) + return signedless_minus (-other, -(*this), true); + + sreal r = signedless_minus (*this, other, m_negative); + + return r; +} + +sreal +sreal::signedless_minus (const sreal &a, const sreal &b, bool negative) { int dexp; sreal tmp, r; const sreal *bb; + const sreal *a_p = &a; + const sreal *b_p = &b; - gcc_assert (*this >= other); + dexp = a_p->m_exp - b_p->m_exp; - dexp = m_exp - other.m_exp; - r.m_exp = m_exp; + r.m_exp = a_p->m_exp; if (dexp > SREAL_BITS) { - r.m_sig = m_sig; + r.m_sig = a_p->m_sig; return r; } if (dexp == 0) - bb = &other; + bb = b_p; else { - tmp = other; + tmp = *b_p; tmp.shift_right (dexp); bb = &tmp; } - r.m_sig = m_sig - bb->m_sig; + r.m_sig = a_p->m_sig - bb->m_sig; r.normalize (); + + r.m_negative = negative; return r; } @@ -240,7 +297,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 +309,8 @@ sreal r; r.m_exp = m_exp + other.m_exp; r.normalize (); } + + r.m_negative = m_negative ^ other.m_negative; return r; } @@ -260,10 +319,11 @@ sreal r; sreal sreal::operator/ (const sreal &other) const { - gcc_assert (other.m_sig != 0); -sreal r; + gcc_checking_assert (other.m_sig != 0); + 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 461e28b3d26..1362bf66866 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. @@ -23,6 +23,8 @@ along with GCC; see the file COPYING3. If not see /* SREAL_PART_BITS has to be an even number. */ #define SREAL_PART_BITS 32 +#define UINT64_BITS 64 + #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) @@ -34,14 +36,23 @@ 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; + + if (sig < 0) + sig = -sig; + + m_sig = (uint64_t) sig; + + normalize (); + } void dump (FILE *) const; int64_t to_int () const; - sreal operator+ (const sreal &other) const; sreal operator- (const sreal &other) const; sreal operator* (const sreal &other) const; @@ -49,21 +60,64 @@ 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; + } + + /* Global minimum sreal can hold. */ + inline static sreal min () + { + static sreal min = sreal (-SREAL_MAX_SIG, SREAL_MAX_EXP); + return min; + } + + /* Global minimum sreal can hold. */ + inline static sreal max () + { + static sreal max = sreal (SREAL_MAX_SIG, SREAL_MAX_EXP); + return max; } private: void normalize (); void shift_right (int amount); - uint64_t m_sig; /* Significant. */ + static sreal signedless_plus (const sreal &a, const sreal &b, bool negative); + static sreal signedless_minus (const sreal &a, const sreal &b, bool negative); + + uint64_t m_sig; /* Significant. */ signed int m_exp; /* Exponent. */ + bool m_negative; /* Negative sign. */ }; extern void debug (sreal &ref); @@ -76,12 +130,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) @@ -109,4 +163,14 @@ inline bool operator>= (const sreal &a, const sreal &b) return a == b || a > b; } +inline sreal operator<< (const sreal &a, int exp) +{ + return a.shift (exp); +} + +inline sreal operator>> (const sreal &a, int exp) +{ + return a.shift (-exp); +} + #endif -- 2.30.2