Message ID | 546F202F.8090606@suse.cz |
---|---|
State | New |
Headers | show |
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 >>> >>> >
diff --git a/gcc/predict.c b/gcc/predict.c index 779af11..5b4c186 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 = 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; @@ -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 == sreal::zero ()) { 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::one () - 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::one () / real_br_prob_base; + real_almost_one = sreal::one () - 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 = 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..a581bed 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. @@ -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,64 @@ 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 double value of *this. */ +double +sreal::to_double () const +{ + int64_t sign = m_negative ? -1 : 1; + int64_t exp = m_exp; + + if (m_exp > 0) + { + double d = m_sig; + while (exp != 0) + { + if (exp > UINT64_BITS) + { + d *= INTTYPE_MAXIMUM (uint64_t); + exp -= UINT64_BITS; + } + else + { + d *= ((uint64_t)1 << exp); + exp = 0; + } + } + + return (double)sign * d; + } + if (exp < 0) + { + double d = m_sig; + while (exp != 0) + { + if (exp < -UINT64_BITS) + { + d /= INTTYPE_MAXIMUM (uint64_t); + exp += UINT64_BITS; + } + else + { + d /= ((uint64_t)1 << -exp); + exp = 0; + } + } + return (double)sign * d; + } + return (double)sign * m_sig; } /* Return *this + other. */ @@ -169,18 +219,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 +272,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; } @@ -208,30 +282,60 @@ 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 +344,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 +356,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 +366,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 461e28b..de8aa9c 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,9 +23,11 @@ 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) +#define SREAL_MAX_EXP (INT_MAX / 8) #define SREAL_BITS SREAL_PART_BITS @@ -34,13 +36,24 @@ 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; + double to_double () const; sreal operator+ (const sreal &other) const; sreal operator- (const sreal &other) const; @@ -49,21 +62,70 @@ 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: 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 +138,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 +171,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