From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 5720 invoked by alias); 21 Feb 2006 15:43:24 -0000 Received: (qmail 5706 invoked by uid 22791); 21 Feb 2006 15:43:23 -0000 X-Spam-Check-By: sourceware.org Received: from atrey.karlin.mff.cuni.cz (HELO atrey.karlin.mff.cuni.cz) (195.113.31.123) by sourceware.org (qpsmtpd/0.31) with ESMTP; Tue, 21 Feb 2006 15:43:20 +0000 Received: by atrey.karlin.mff.cuni.cz (Postfix, from userid 29025) id 01B3D4B401D; Tue, 21 Feb 2006 16:43:18 +0100 (CET) Date: Tue, 21 Feb 2006 15:43:00 -0000 From: Zdenek Dvorak To: Roger Sayle Cc: Paolo Bonzini , gcc-patches@gcc.gnu.org, rth@redhat.com Subject: Re: Patch ping Message-ID: <20060221154317.GA27569@atrey.karlin.mff.cuni.cz> References: <20060221091531.GA26781@atrey.karlin.mff.cuni.cz> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.9i Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2006-02/txt/msg01687.txt.bz2 Hello, > I believe that the last sixty years of digital computation have > decisively shown the superiority of two's complement arithmetic > for representing signed integers as binary, and convenient for > interconversion with unsigned values. yes, this is why I have chosen to use it (well, why I haven't considered any other in the first place). > You should treat double_int like you would a TImode. For example, -1 > should be represented by both the high an low words containing all one > bits. This is quite orthogonal issue to whether to use two's complement arithmetic or something else. As far as I understand, this is the main point of your objection, so I will focus on it. There are several basic properties I want double_int to satisfy: 1) it is possible to represent numbers with smaller precision than 2 * HOST_BITS_PER_WIDE_INT 2) it is not neccessary to distinguish between signed and unsigned values in functions that perform arithmetics modulo 2^precision (+, -, *, negation,...) 3) each number has only one possible representation. I will for now assume that we agree on that these are desirable; if not, I will present my arguments on this issue in the followup mail(s). 1) and 3) leave us with basically three choices of how to represent the numbers; avoiding long explanation, let us demonstrate these on examples, say we want to represent 8-bit values: -- (a): unsigned 127 = signed 127 = {0, 127} unsigned 255 = signed -1 = {0, 255} -- (b) unsigned 127 = signed 127 = {0, 127} unsigned 255 = signed -1 = {-1, -1} -- (c) unsigned 127 = signed 127 = {0, 127} unsigned 255 = {0,255} signed -1 = {-1, -1} My choice is (a). Your choice seems to be either (b) or (c), you are not quite clear about it. By property 2, it would be nice for signed and unsigned numbers with the same precision to have the same representation (use the same range of numbers); this leaves only (a) and (b) as possibilities. Regardless of the choice, because of 3) you need to have some normalization of the results of the operation -- e.g., in representation (b), 127 + 127 = 254 = {-1, -2}, but add_double would return {0,254}. In representation (a), -1 + -1 = -2 = {0,254}, but add_double would return {0, 510}. For (a), this normalization is X & MASK. For (b), it is if (X & (1<< (prec - 1)) == 0) ? X & MASK : X | ~MASK. Between (a) and (b), I have chosen (a) as the normalization is simpler. > + /* Returns true if CST is minus one in precision of MASK. */ > + > + static inline bool > + double_int_minus_one_p (double_int mask, double_int cst) > + { > + return (DI_LOW (cst) == DI_LOW (mask) > + && DI_HIGH (cst) == DI_HIGH (mask)); > + } > > Then you wouldn't need a mask to test for minus one! > > + /* Returns true if SCALE is negative in precision of MASK. */ > + > + bool > + double_int_negative_p (double_int mask, double_int scale) > + { > + if (DI_HIGH (mask)) > + return (DI_HIGH (scale) & ~(DI_HIGH (mask) >> 1)) != 0; > + else > + return (DI_LOW (scale) & ~(DI_LOW (mask) >> 1)) != 0; > + } > > And you wouldn't have to do pass in a mask to determine whether > a value is negative. yes, this is about the only real advantage of the representation (b). > You would be able to implement a signed comparison, which is > not so mysteriously missing from from your patch. You would still need to distinguish between signed and unsigned versions of the comparison, at the very least for numbers whose precision is exactly 2 * HOST_BITS_PER_WIDE_INT. The reason I do not implement signed comparison is that I do not need it anywhere, not because it would be somehow fundamentally harder than the unsigned case. > But most importantly.... > > + mul_double (DI_LOW (a), DI_HIGH (a), > + DI_LOW (b), DI_HIGH (b), &lo, &hi); > ... > + add_double (DI_LOW (a), DI_HIGH (a), > + DI_LOW (b), DI_HIGH (b), &lo, &hi); > ... > + neg_double (DI_LOW (a), DI_HIGH (a), &lo, &hi); > ... > + div_and_round_double (FLOOR_DIV_EXPR, true, > + DI_LOW (a), DI_HIGH (a), > + DI_LOW (b), DI_HIGH (b), > + &lo, &hi, &rem_lo, &rem_hi); > > You'll now get the correct results out of all of these routines, which > assume the same sign-extended two's complement representation of > integers as used in the rest of the compiler, and the vast majority > of the rest of the planet. Regardless of whether the representation you choose is (a), (b), or (c), you need to do some normalization of the result. This is simplest for (a) -- just mask out bits outside of the precision, more complicated for (b) -- you need to do sign extension, and even more quite complex for (c) (you need to distinguish between the signed and unsigned cases). Zdenek