Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

[Nathan Sidwell]

The following reply was made to PR c/7284; it has been noted by GNATS.

From: Nathan Sidwell <nathan@acm.org>
To: Al Grant <AlGrant@myrealbox.com>
Cc: falk.hueffner@student.uni-tuebingen.de, nathan@gcc.gnu.org, algrant@acm.org, 
    gcc-bugs@gcc.gnu.org, gcc-prs@gcc.gnu.org, nobody@gcc.gnu.org, 
    gcc-gnats@gcc.gnu.org
Subject: Re: c/7284: incorrectly simplifies leftshift followed by signed 
         power-of-2 division
Date: Fri, 12 Jul 2002 17:37:53 +0100

 Al Grant wrote:
 > I read the C89 standard (and the C++ standard).
 you need to read more carefully.
 
 KnR 2 A7.8 says the same as C99,
 C++ says [5]/5 that if the result is not in the range of representable values,
 the behaviour is undefined.
 
 nathan
 -- 
 Dr Nathan Sidwell :: Computer Science Department :: Bristol University
            The voices in my head told me to say this
 nathan@acm.org  http://www.cs.bris.ac.uk/~nathan/  nathan@cs.bris.ac.uk

Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

[rearnsha]

Synopsis: incorrectly simplifies leftshift followed by signed power-of-2 division

State-Changed-From-To: closed->open
State-Changed-By: rearnsha
State-Changed-When: Thu Feb 13 16:06:23 2003
State-Changed-Why:
    I'm re-opening this report.  In c89 the text for << says
    
    The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros.
    
    It then goes on to qualify what this means when E1 is unsigned, but says nothing about the *interpretation* for the signed context (beyond what is specified above).  However, in a 2s complement environment it is possible to give a meaningful interpretation of the resulting value.
    
    DR#081 says that the meaning in the signed context is "implementation defined", but that is clearly very different from "undefined" as we have at present.
    
    At the very least we must document what left shift of a signed value means on our implementation.

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=7284

Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

[Nathan Sidwell]

The following reply was made to PR c/7284; it has been noted by GNATS.

From: Nathan Sidwell <nathan@codesourcery.com>
To: Al Grant <AlGrant@myrealbox.com>
Cc: nathan@cs.bris.ac.uk, falk.hueffner@student.uni-tuebingen.de,
   nathan@gcc.gnu.org, algrant@acm.org, gcc-bugs@gcc.gnu.org,
   gcc-prs@gcc.gnu.org, nobody@gcc.gnu.org, gcc-gnats@gcc.gnu.org
Subject: Re: c/7284: incorrectly simplifies leftshift followed by signed 
 power-of-2 division
Date: Fri, 12 Jul 2002 20:45:50 +0100

 Al Grant wrote:
 > 
 > >you need to read more carefully.
 > >KnR 2 A7.8 says the same as C99,
 > 
 > You need to read more carefully.  K&R2 says something quite different from C99.  It says that in the absence of overflow, the operation is equivalent to a
 > multiplication.  It does _not_ say that if the multiplication overflows the result of the shift is undefined, let alone that program behavior is undefined.
 oops, how did I manage to misread that? A7 says that 'most existing C
 implementations ignore overflow in evaluation of signed integral
 expressions and assignemnts, but this behaviour is not guaranteed.'
 
 > >C++ says [5]/5 that if the result is not in the range >of representable values,
 > >the behaviour is undefined.
 > 
 > But left-shift is an operation on the representation, i.e. the bit pattern.
 The *implementation* of left-shift is an operation on representation.
 The abstract left shift operation applies to values.
 
 >  For signed left-shift (in C89 and C++) it is not defined any other way.
 C++ says it that the bit pattern is left shifted and vacated bit positions
 are zero filled. That we agree on. What we disagree is what happens to 
 bits 'falling off the top' (be they zero or one). I contend that if the
 exact result (which will require 32+c bits to represent), is not
 representable in 32 bits, then the behaviour is undefined (as [5]/5
 says). You contend that the result is reduced modulo 2^32. But then
 why does C++ then go on to say 'if E1 is unsigned type ...' to specify
 such a modulo reduction for unsigned types?
 
 >  How is it meaningful to talk about the representability of operations on the representation, and say that the result of such an operation might be unrepresentable?
 the left shift is independant of bit length, it is the truncation of the
 exact result to a representable format which gives the problem.
 
 > Representability is a property of the integers as numbers.
 Representability is a property of representation formats.
 
 > It might be meaningful to think about the result of such an operation
 > having a representation that did not correspond to any value (e.g. was
 > a trap representation) but a non-valued representation is a  totally
 > different concept from a non-representable value.  Besides, there are
 > no such integer representations on the platform for which I reported
 > the bug.
 that would be valid implementation of undefined behaviour.
 
 nathan
 
 -- 
 Dr Nathan Sidwell   ::   http://www.codesourcery.com   ::   CodeSourcery LLC
          'But that's a lie.' - 'Yes it is. What's your point?'
 nathan@codesourcery.com : http://www.cs.bris.ac.uk/~nathan/ : nathan@acm.org

Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

[Falk Hueffner]

The following reply was made to PR c/7284; it has been noted by GNATS.

From: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>
To: "Al Grant" <AlGrant@myrealbox.com>
Cc: nathan@gcc.gnu.org,  algrant@acm.org,  gcc-bugs@gcc.gnu.org,
	  gcc-prs@gcc.gnu.org,  nobody@gcc.gnu.org,  gcc-gnats@gcc.gnu.org
Subject: Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division
Date: 12 Jul 2002 19:01:43 +0200

 "Al Grant" <AlGrant@myrealbox.com> writes:
 
 > 3.3.7 (something else in ISO, maybe 6.3.7)
 > 
 >   The result of E1 << E2 is E1 left-shifted E2 bit
 >   positions; vacated bits are filled with zeros.
 > 
 > For signed types it says nothing more.
 > 
 > Now if signed left-shift is defined at all, in terms of the
 > representation, I don't see there's any lack of definition in
 > "0x00000080 left-shifted 24 bit positions", it is clearly 0x80000000
 > (of the same type).  So it's defined unless the standard says
 > otherwise, which only C99 seems to.
 
 Defect Report #081 seems to be of interest here
 (http://wwwold.dkuug.dk/JTC1/SC22/WG14/www/docs/dr_081.html). It
 basically states that the behaviour is implementation defined (for any
 signed left shift, not just this case).
 
 -- 
 	Falk

Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

[Falk Hueffner]

The following reply was made to PR c/7284; it has been noted by GNATS.

From: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>
To: "Al Grant" <AlGrant@myrealbox.com>
Cc: nathan@gcc.gnu.org,  algrant@acm.org,  gcc-bugs@gcc.gnu.org,
	  gcc-prs@gcc.gnu.org,  nobody@gcc.gnu.org,  gcc-gnats@gcc.gnu.org
Subject: Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division
Date: 12 Jul 2002 18:18:14 +0200

 "Al Grant" <AlGrant@myrealbox.com> writes:
 
 > > On 12/07/2002 15:12:01 nathan wrote:
 > > >Synopsis: incorrectly simplifies leftshift followed by signed power-of-2 
 > > >division
 > > >
 > > >State-Changed-From-To: open->closed
 > > >State-Changed-By: nathan
 > > >State-Changed-When: Fri Jul 12 07:12:01 2002
 > > >State-Changed-Why:
 > > >not a bug. for signed types, if 'n << c' overflows, the
 > > >behaviour is undefined.
 > > 
 > > There is no "overflow" in my sample code.  The operation of shifting 128 24 bits to the left on a
 > > 32-bit machine produces the bit pattern 0x80000000.
 > > No bits overflow.
 > > 
 > > The fact that a positive number may become negative when
 > > left-shifted is a property of the twos complement representation.
 > > The standard does not define signed left shift in terms of
 > > multiplication and certainly doesn't say that it is undefined when
 > > the apparently equivalent multiplication would be undefined.
 > 
 > >Before refering to the standard, you should probably >read it.
 > 
 > I read the C89 standard (and the C++ standard).  
 
 > You are referring to C99.  gcc was not defining __STDC_VERSION__, so
 > C89, not C99, is surely the relevant standard.  The behaviour
 > happens even if I explicitly set -std=c89, or if I use g++ 3.1, and
 > you cannot justify either of those by reference to C99.
 
 Right, I just assumed it to be very unlikely that this was changed to
 be undefined in C99. I don't have the C89 standard; could you perhaps
 cite the passage that shows this was defined behaviour in C89?
 
 -- 
 	Falk

Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

[Falk Hueffner]

The following reply was made to PR c/7284; it has been noted by GNATS.

From: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>
To: "Al Grant" <AlGrant@myrealbox.com>
Cc: nathan@gcc.gnu.org,  algrant@acm.org,  gcc-bugs@gcc.gnu.org,
	  gcc-prs@gcc.gnu.org,  nobody@gcc.gnu.org,  gcc-gnats@gcc.gnu.org
Subject: Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division
Date: 12 Jul 2002 17:13:48 +0200

 "Al Grant" <AlGrant@myrealbox.com> writes:
 
 > On 12/07/2002 15:12:01 nathan wrote:
 > >Synopsis: incorrectly simplifies leftshift followed by signed power-of-2 
 > >division
 > >
 > >State-Changed-From-To: open->closed
 > >State-Changed-By: nathan
 > >State-Changed-When: Fri Jul 12 07:12:01 2002
 > >State-Changed-Why:
 > >not a bug. for signed types, if 'n << c' overflows, the
 > >behaviour is undefined.
 > 
 > There is no "overflow" in my sample code.  The operation of shifting 128 24 bits to the left on a
 > 32-bit machine produces the bit pattern 0x80000000.
 > No bits overflow.
 > 
 > The fact that a positive number may become negative when
 > left-shifted is a property of the twos complement representation.
 > The standard does not define signed left shift in terms of
 > multiplication and certainly doesn't say that it is undefined when
 > the apparently equivalent multiplication would be undefined.
 
 Before refering to the standard, you should probably read it.
 
 6.5.7.4:
 
 "The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated
 bits are filled with zeros. If E1 has a signed type and nonnegative
 value, and E1 * 2^E2 is representable in the result type, then that
 is the resulting value; otherwise, the behavior is undefined."
 
 -- 
 	Falk

Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

[Al Grant]

The following reply was made to PR c/7284; it has been noted by GNATS.

From: "Al Grant" <AlGrant@myrealbox.com>
To: nathan@gcc.gnu.org,
	algrant@acm.org,
	gcc-bugs@gcc.gnu.org,
	gcc-prs@gcc.gnu.org,
	nobody@gcc.gnu.org,
	gcc-gnats@gcc.gnu.org
Cc:  
Subject: Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division
Date: Fri, 12 Jul 2002 15:00:34 +0000

 On 12/07/2002 15:12:01 nathan wrote:
 >Synopsis: incorrectly simplifies leftshift followed by signed power-of-2 
 >division
 >
 >State-Changed-From-To: open->closed
 >State-Changed-By: nathan
 >State-Changed-When: Fri Jul 12 07:12:01 2002
 >State-Changed-Why:
 >not a bug. for signed types, if 'n << c' overflows, the
 >behaviour is undefined.
 
 There is no "overflow" in my sample code.  The operation of shifting 128 24=
  bits to the left on a
 32-bit machine produces the bit pattern 0x80000000.
 No bits overflow.
 
 The fact that a positive number may become negative when left-shifted is a =
 property of the twos complement representation.  The standard does not de=
 fine signed left shift in terms of multiplication and certainly doesn't s=
 ay that it is undefined when the apparently equivalent multiplication wou=
 ld be undefined.
 
 

Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

[nathan]

Synopsis: incorrectly simplifies leftshift followed by signed power-of-2 division

State-Changed-From-To: open->closed
State-Changed-By: nathan
State-Changed-When: Fri Jul 12 07:12:01 2002
State-Changed-Why:
    not a bug. for signed types, if 'n << c' overflows, the
    behaviour is undefined.

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=7284

c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division

[algrant]

>Number:         7284
>Category:       c
>Synopsis:       incorrectly simplifies leftshift followed by signed power-of-2 division
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          wrong-code
>Submitter-Id:   net
>Arrival-Date:   Fri Jul 12 04:26:00 PDT 2002
>Closed-Date:
>Last-Modified:
>Originator:     Al Grant
>Release:        3.1
>Organization:
>Environment:
SunOS 5.5.1 Generic_103640-31 sun4u sparc SUNW,Ultra-5_10
>Description:
Incorrect simplification of signed 

  (n << 24) / (1 << 23)

to a single left shift.  Should sign-extend from bit 8.
>How-To-Repeat:
#include <stdio.h>
int f(int n) { return (n<<24) / (1<<23); }
int main(void) { 
  if (f(128) != -256) printf("Broken\n"); return 0; }
>Fix:
Replace with left shift followed by signed right shift.
This can be done in source as a workaround.
>Release-Note:
>Audit-Trail:
>Unformatted: