Incorrect simplification of signed (n << 24) / (1 << 23) to a single left shift. Should sign-extend from bit 8. Release: 3.1 Environment: SunOS 5.5.1 Generic_103640-31 sun4u sparc SUNW,Ultra-5_10 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.
State-Changed-From-To: open->closed State-Changed-Why: not a bug. for signed types, if 'n << c' overflows, the behaviour is undefined.
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.
From: "Al Grant" <AlGrant@myrealbox.com> To: falk.hueffner@student.uni-tuebingen.de 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: Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division Date: Fri, 12 Jul 2002 16:09:44 +0000 > On 12/07/2002 15:12:01 nathan wrote: > >Synopsis: incorrectly simplifies leftshift followed by signed power-of-2= =20 > >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. >=20 > 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. >=20 > 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). =20 You are referring to C99. gcc was not defining __STDC_VERSION__, so C89, n= ot C99, is surely the relevant standard. The behaviour happens even if I= explicitly set -std=3Dc89, or if I use g++ 3.1, and you cannot justify e= ither of those by reference to C99.
From: "Al Grant" <AlGrant@myrealbox.com> To: falk.hueffner@student.uni-tuebingen.de 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: Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division Date: Fri, 12 Jul 2002 16:50:21 +0000 >Right, I just assumed it to be very unlikely that this was changed to >be undefined in C99.=20 So did I, otherwise I would have checked it! >I don't have the C89 standard; could you perhaps >cite the passage that shows this was defined >behaviour in C89? 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. It then goes on to say "If E1 has an unsigned type..." and notes that it is= equivalent to a multiplication. 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 "0x000= 00080 left-shifted 24 bit positions", it is clearly 0x80000000 (of the sa= me type). So it's defined unless the standard says otherwise, which only= C99 seems to. There's no reason given to treat it specially if it happens to represent a = negative signed number. This is not a case of an ideal signed arithmetic= operation producing some result in the ideal integers that cannot be rep= resented in the particular signed type, so the undefinedness in that case= doesn't apply here.
From: "Al Grant" <AlGrant@myrealbox.com> To: nathan@compsci.bristol.ac.uk 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: Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division Date: Fri, 12 Jul 2002 17:06:44 +0000 >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 equivalen= t 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 und= efined. >C++ says [5]/5 that if the result is not in the range >of representable va= lues, >the behaviour is undefined. But left-shift is an operation on the representation, i.e. the bit pattern.= For signed left-shift (in C89 and C++) it is not defined any other way.= How is it meaningful to talk about the representability of operations o= n the representation, and say that the result of such an operation might = be unrepresentable? Representability is a property of the integers as numbers. It might be meaningful to think about the result of such an operation havin= g a representation that did not correspond to any value (e.g. was a trap = representation) but a non-valued representation is a totally different c= oncept from a non-representable value. Besides, there are no such intege= r representations on the platform for which I reported the bug.
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
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
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
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
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
From: "Al Grant" <AlGrant@myrealbox.com> To: nathan@codesourcery.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: Re: c/7284: incorrectly simplifies leftshift followed by signed power-of-2 division Date: Mon, 15 Jul 2002 11:44:05 +0000 >> But left-shift is an operation on the >>representation, i.e. the bit pat= tern. >The *implementation* of left-shift is an operation on representation. >The abstract left shift operation applies to values. It applies to bit patterns. =20 Going back to K&R2 A7.8, they say=20 "The value of E1 << E2 is E1 (interpreted as a bit pattern) left-shifted E2 bits; in the absence of overflow, this is equivalent to multiplication by 2**E2." Now if left-shift was an abstract operation, why=20 didn't they just say "The value of E1 << E2 is E1 multiplied by 2**E2" Do you think K&R intended signed left-shift to result in undefined behavior? I rather think they expected it to do some well-defined operation on the machine representation, with tr= uncation implicit, but not one that could be standardised. >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=20 >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? I never said they should be reduced modulo 2**32. My claim all along has been that this is a function on representations and that some bits are implicitly discarded because that's what a bitwise shift does. It may be implementation-defined (as Falk Hueffner points out, this = is clarified by the=20 response to DR #081) but you have got to define it. What _is_ your impleme= ntation definition of the behavior on signed left shift? The definition for unsigned types in terms of a multiplication merely states an equivalence between an operation on the representation and an operation on the integers, which cannot be directly stated for the signed left shift because of the various different signed representations in existence. >> Representability is a property of the integers as numbers. >Representability is a property of representation formats. A given representation defines a boolean function on integers, namely whether they are representable or not. The point is that an operation on representations always has a representabl= e result.
State-Changed-From-To: closed->open 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.
Hello, I can confirm that the simplification in question is still occuring on gcc 3.3 branch and mainline (20030525). Dara
See Dara's comment, I think this is just a documentation problem though.
Actually, there's a slightly larger problem; if the result is *implementation-defined*, it probably shouldn't vary depending on optimization level, which I believe it currently does. :-( Unless it's OK to say "Our implementation defines this to be undefined", which seems rather bogus.
Subject: Re: incorrectly simplifies leftshift followed by signed power-of-2 division > if the result is *implementation-defined*, it probably > shouldn't vary depending on optimization level "Implementation" includes the specific set of command-line options. See C99 3.10.
Subject: Re: incorrectly simplifies leftshift followed by signed power-of-2 division > > if the result is *implementation-defined*, it probably > > shouldn't vary depending on optimization level > > "Implementation" includes the specific set of command-line > options. See C99 3.10. > Even if I bought that idea (and I don't particularly in this case): 1) We are talking about C90 specified behaviour 2) An implementation still has to document what the behaviour is for each option (that's the "defined" bit :-) What we have at present is -O gives undefined behaviour... R.
Subject: Bug 7284 CVSROOT: /cvs/gcc Module name: gcc Changes by: jsm28@gcc.gnu.org 2004-07-22 20:33:34 Modified files: gcc : ChangeLog fold-const.c gcc/testsuite : ChangeLog Added files: gcc/testsuite/gcc.c-torture/execute: pr7284-1.c Log message: PR c/7284 * fold-const.c (extract_muldiv_1): Do not treat signed left shift as multiplication. testsuite: * gcc.c-torture/execute/pr7284-1.c: New test. Patches: http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.4642&r2=2.4643 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fold-const.c.diff?cvsroot=gcc&r1=1.428&r2=1.429 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.4038&r2=1.4039 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.c-torture/execute/pr7284-1.c.diff?cvsroot=gcc&r1=NONE&r2=1.1
Fixed for 3.5.0.