From patchwork Fri Nov 21 15:21:27 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Martin_Li=C5=A1ka?= X-Patchwork-Id: 413088 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 59030140180 for ; Sat, 22 Nov 2014 02:21:43 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:references :in-reply-to:content-type; q=dns; s=default; b=Am2eUYUwWsFazHlcl iE2UrooDzQu0k//ZpKC3pUrx8bnttUYLC0DvDcG6ulttDPRBwnmFDAONXlRrzX2A 7f/dl1ZE5Yyyo96pBNL7RMY6BSXKg1iGhYnqCsV7FkBkFxA4uY+Zfwf+ui2NXYJT L8JR6EoOYxSd6rCbqHnvnsB+dY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:references :in-reply-to:content-type; s=default; bh=OS7lZD8nEsRrSJhKAsaFjhV vpn8=; b=UvhS+vmZ2ysBdtru6LwJ2rBdgdNPO5dJEKNrUPbGzuqwEYtIbq67Cy9 CIRxwOCVAJF+zJawna+I1RbeuSZlfkZmD9cPIi5HhSx90FiYmt/FYDQZD/8FVUU8 AZYNnb1c8YlIypN9DYO2Wv8vyyqqbT38+PqeEjqNsq6tQfW1fysI= Received: (qmail 3763 invoked by alias); 21 Nov 2014 15:21:35 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 3749 invoked by uid 89); 21 Nov 2014 15:21:34 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.1 required=5.0 tests=AWL, BAYES_00 autolearn=ham version=3.3.2 X-HELO: mx2.suse.de Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Fri, 21 Nov 2014 15:21:31 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 6BBB5AB43 for ; Fri, 21 Nov 2014 15:21:28 +0000 (UTC) Message-ID: <546F5877.2050300@suse.cz> Date: Fri, 21 Nov 2014 16:21:27 +0100 From: =?UTF-8?B?TWFydGluIExpxaFrYQ==?= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0 MIME-Version: 1.0 To: gcc-patches@gcc.gnu.org Subject: Re: [PATCH 8/9] Negative numbers added for sreal class. References: <398814b6afe28679f16c5d4b9879accb7984b76b.1415911038.git.mliska@suse.cz> <546F202F.8090606@suse.cz> <546F4EB7.8060006@suse.cz> In-Reply-To: X-IsSubscribed: yes On 11/21/2014 04:02 PM, Richard Biener wrote: > On Fri, Nov 21, 2014 at 3:39 PM, Martin Liška wrote: > >> 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 > > -#define SREAL_MAX_EXP (INT_MAX / 4) > +#define SREAL_MAX_EXP (INT_MAX / 8) > > this change doesn't look necessary anymore? > > Btw, it's also odd that... > > #define SREAL_PART_BITS 32 > ... > #define SREAL_MIN_SIG ((uint64_t) 1 << (SREAL_PART_BITS - 1)) > #define SREAL_MAX_SIG (((uint64_t) 1 << SREAL_PART_BITS) - 1) > > thus all m_sig values fit in 32bits but we still use a uint64_t m_sig ... > (the implementation uses 64bit for internal computations, but still > the storage is wasteful?) > > Of course the way normalize() works requires that storage to be > 64bits to store unnormalized values. > > I'd say ok with the SREAL_MAX_EXP change reverted. > Hi. You are right, this change was done because I used one bit for m_negative (bitfield), not needed any more. Final version attached. Thank you, Martin > Thanks, > Richard. > > >> >>> 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 >>>>>> >>>>>> >>>> >> From b28e4264b5f9965ca5ab4f52ce6f4c9df00d4800 Mon Sep 17 00:00:00 2001 From: mliska Date: Fri, 21 Nov 2014 12:07:40 +0100 Subject: [PATCH 1/2] Negative numbers added for sreal class. gcc/ChangeLog: 2014-11-13 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.h: Definition of new functions added. --- gcc/predict.c | 30 ++++++++-------- gcc/sreal.c | 114 ++++++++++++++++++++++++++++++++++++++++++++-------------- gcc/sreal.h | 82 +++++++++++++++++++++++++++++++++++++----- 3 files changed, 174 insertions(+), 52 deletions(-) diff --git a/gcc/predict.c b/gcc/predict.c index 779af11..0cfe4a9 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 3f5456a..0337f9e 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; } @@ -208,30 +235,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 +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 461e28b..1362bf6 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.1.2