Re: Miscompilation of remainder expressions
On 1/19/07, Joe Buck [EMAIL PROTECTED] wrote: On Thu, Jan 18, 2007 at 05:36:23PM -0500, Robert Dewar wrote: Morten Welinder wrote: For sure a/b is undefined In C, it is. In assembler it is perfectly well defined, i.e., it traps. But how is the trap handler supposed to know the source of a given instruction? M. Sure it traps, but what happens when that trap occurs is of course O/S dependent, there is no guarantee of the effect. We're going around in circles. Everything has been said. What if we put together a Wiki page with the problem and possible solutions, as in a) do nothing, no big deal. This is what happens if no one contributes code in any case. b) add a flag to generate code to compute something like divisor == -1 ? 0 : rem(dividend,divisor) or divisor == rem(dividend,abs(divisor)) in an efficient way (cmov to avoid busting the pipeline) Note that cmov is not the right thing to use here (at least on ia32 and x86_64) as it is more expensive than compare and jump if not the probability of taking either way are the same (which I would not expect here, as divisor == -1 should be nearly never the case). That said, a transformation on the tree level would make it possible for VRP to optimize away the special casing. Richard.
Re: Miscompilation of remainder expressions
Ian Lance Taylor writes: Robert Dewar [EMAIL PROTECTED] writes: Ian Lance Taylor wrote: We do want to generate a trap for x / 0, of course. Really? Is this really defined to generate a trap in C? I would be surprised if so ... As far as I know, but I think it would be a surprising change for x / 0 to silently continue executing. But perhaps not a very important one. Java depends for correct execution on some divisions by zero (in libgcc) generating traps. For example, here's one in __udivmoddi4: if (d0 == 0) d0 = 1 / d0;/* Divide intentionally by zero. */ Andrew.
Re: Miscompilation of remainder expressions
On Thu, 18 Jan 2007, Andrew Haley wrote: | Robert Dewar writes: | Joe Buck wrote: | | (off topic!) | |On Wed, Jan 17, 2007 at 06:40:21PM -0500, Robert Dewar wrote: |H .. I wish some of the more important bugs in gcc received |the attention that this very unimportant issue is receiving :-) | |I guess the difference is that lots of people can understand |this issue. | |Yes, this phenomenon has been given a name, by Parkinson of Parkinson's |law fame: bike shed. | | Actually I don't think Parkinson uses this term. He states a similar | principle as: | | * THE LAW OF TRIVIALITY: The time spent on any item of a committee's | agenda will be in inverse proportion to the sum of money involved. | | Mm, but although the problem being dicussed here is trivial, some of | the proposed solutions aren't. As the saying goes, the cure is worse | than the disease. I would say that is a bit extreme. I don't think we're going to implement any of the solutions without giving people options to disable the correct instruction generation when they don't care about it. -- Gaby
Re: Miscompilation of remainder expressions
Andrew Haley wrote: Mm, but although the problem being dicussed here is trivial, some of the proposed solutions aren't. As the saying goes, the cure is worse than the disease. Indeed! Well whenever you have umpteen people all trying to solve a simple problem, things always get out of hand, and fixing a bug is definitely a case where too many cooks Andrew.
Re: Miscompilation of remainder expressions
Gabriel Dos Reis wrote: I would say that is a bit extreme. I don't think we're going to implement any of the solutions without giving people options to disable the correct instruction generation when they don't care about it. I would hesitate a bit about options in this general class of generate-wrong-code-i-don't-care I think such options should only be in place if you can really show a substantial effect. Point in case, GNAT put in a truly horrible overflow detection circuit very early on, that works by doing everything in double precision and range checking the results. This seemed so very inefficient that we made overflow checks off by default and provided an option (-gnato) to turn them on. But in practice, most large applications find that -gnato is not noticeably expensive, and probably at the very least it should have been made the default. P.S. it would seem that -ftrapv would be just what Ada needs, but our local gcc folks claim that -ftrapv is completely broken and unusable :-(
Re: Miscompilation of remainder expressions
For sure a/b is undefined In C, it is. In assembler it is perfectly well defined, i.e., it traps. But how is the trap handler supposed to know the source of a given instruction? M.
Re: Miscompilation of remainder expressions
On Wed, Jan 17, 2007 at 12:43:40AM +0100, Vincent Lefevre wrote: On 2007-01-16 21:27:42 +, Andrew Haley wrote: Ian Lance Taylor writes: I suspect that the best fix, in the sense of generating the best code, would be to do this at the tree level. That will give loop and VRP optimizations the best chance to eliminate the test for -1. Doing it during gimplification would be easy, if perhaps rather ugly. If there are indeed several processors with this oddity, then it would even make a certain degree of sense as a target-independent option. x86, x86-64, S/390, as far as I'm aware. and PowerPC G4 and G5, where I don't get a crash, but an incorrect result (as said on PR#30484). On PPC, the solution is to use divo. [1] followed by an unlikely conditional branch to out of line code to handle the corner cases. The question is: what do we do in the case of a divide by zero on PPC? Are there other architectures that do not trap? Gabriel [1] sadly gcc does not know about the overflow flag and (unless it has improved greatly since the last time I checked on a small ADA program) generates bloated and slow code when checking for overflow. This is not specific to the rs6000 backend.
Re: Miscompilation of remainder expressions
Ian Lance Taylor writes: Gabriel Dos Reis [EMAIL PROTECTED] writes: Ian, do you believe something along the line of # I mean, could not we generate the following for %: # # rem a b := #if abs(b) == 1 # return 0 #return machine-instruction a b # # On x86 processors that have conditional moves, why not do the equivalent # of # # neg_b = -b; # cmov(last result is negative,neg_b,b) # __machine_rem(a,b) # # Then there's no disruption of the pipeline. is workable for the affected targets? Sure, I think the only real issue is where the code should be inserted. From a performance/convenience angle, the best place to handle this is either libc or the kernel. Either of these can quite easily fix up the operands when a trap happens, with zero performance degradation of existing code. I don't think there's any need for gcc to be altered to handle this. Andrew.
Re: Miscompilation of remainder expressions
On Wed, 17 Jan 2007, Andrew Haley wrote: | Ian Lance Taylor writes: | Gabriel Dos Reis [EMAIL PROTECTED] writes: | |Ian, do you believe something along the line of | | # I mean, could not we generate the following for %: | # | # rem a b := | #if abs(b) == 1 | # return 0 | #return machine-instruction a b | # | # On x86 processors that have conditional moves, why not do the equivalent | # of | # | # neg_b = -b; | # cmov(last result is negative,neg_b,b) | # __machine_rem(a,b) | # | # Then there's no disruption of the pipeline. | |is workable for the affected targets? | | Sure, I think the only real issue is where the code should be | inserted. | | From a performance/convenience angle, the best place to handle this is | either libc or the kernel. Hmm, that is predicated on assumptions not convenient to users on targets that are not glibc-based or GNU/Linux-based. -- Gaby
Re: Miscompilation of remainder expressions
Andrew Haley wrote: Ian Lance Taylor writes: Gabriel Dos Reis [EMAIL PROTECTED] writes: Ian, do you believe something along the line of # I mean, could not we generate the following for %: # # rem a b := #if abs(b) == 1 # return 0 #return machine-instruction a b # # On x86 processors that have conditional moves, why not do the equivalent # of # # neg_b = -b; # cmov(last result is negative,neg_b,b) # __machine_rem(a,b) # # Then there's no disruption of the pipeline. is workable for the affected targets? Sure, I think the only real issue is where the code should be inserted. From a performance/convenience angle, the best place to handle this is either libc or the kernel. Either of these can quite easily fix up the operands when a trap happens, with zero performance degradation of existing code. I don't think there's any need for gcc to be altered to handle this. That only works if the operation causes a trap. On x86 this is the case, but Andrew Pinski told me on IM that this was not the case for PPC. David Daney
Re: Miscompilation of remainder expressions
Gabriel Dos Reis writes: On Wed, 17 Jan 2007, Andrew Haley wrote: | | From a performance/convenience angle, the best place to handle this is | either libc or the kernel. Hmm, that is predicated on assumptions not convenient to users on targets that are not glibc-based or GNU/Linux-based. Well, if GNU libc/Linux/whatever can fix this bug in libc or the kernel, so can anyone else. To a man with a hammer, all things look like a nail. It's very tempting for us in gcc-land always to fix things in gcc, not because it's technically the right place but because it's what we control ourselves. Andrew.
Re: Miscompilation of remainder expressions
David Daney writes: That only works if the operation causes a trap. Which it does in almost all cases. Let PPC do something different, if that's what really PPC needs. Andrew.
Re: Miscompilation of remainder expressions
On Wed, 17 Jan 2007, Andrew Haley wrote: | Gabriel Dos Reis writes: | On Wed, 17 Jan 2007, Andrew Haley wrote: | | | | | From a performance/convenience angle, the best place to handle this is | | either libc or the kernel. | | Hmm, that is predicated on assumptions not convenient to users | on targets that are not glibc-based or GNU/Linux-based. | | Well, if GNU libc/Linux/whatever can fix this bug in libc or the | kernel, so can anyone else. (1) people upgrde OS less frequently than compilers. (2) it is not at all obvious that the problem is in the libc or in the kernel. | To a man with a hammer, all things look like a nail. It's very | tempting for us in gcc-land always to fix things in gcc, not because | it's technically the right place but because it's what we control | ourselves. well, I'm unclear what your point is here, but certainly GCC is at fault for generating trapping instructions. So, we fix the problem in GCC, not because that is what we control ourselves, but we we failed to generate proper code. For the earlier point, for sure GCC provides necessary support routines for targets lacking proper instructions. This is not different. -- Gaby
Re: Miscompilation of remainder expressions
Gabriel Dos Reis writes: On Wed, 17 Jan 2007, Andrew Haley wrote: | Gabriel Dos Reis writes: | On Wed, 17 Jan 2007, Andrew Haley wrote: | | | | | From a performance/convenience angle, the best place to handle this is | | either libc or the kernel. | | Hmm, that is predicated on assumptions not convenient to users | on targets that are not glibc-based or GNU/Linux-based. | | Well, if GNU libc/Linux/whatever can fix this bug in libc or the | kernel, so can anyone else. (1) people upgrde OS less frequently than compilers. (2) it is not at all obvious that the problem is in the libc or in the kernel | To a man with a hammer, all things look like a nail. It's very | tempting for us in gcc-land always to fix things in gcc, not because | it's technically the right place but because it's what we control | ourselves. well, I'm unclear what your point is here, but certainly GCC is at fault for generating trapping instructions. So, we fix the problem in GCC, not because that is what we control ourselves, but we we failed to generate proper code. It's not a matter of whose fault it is; trying to apportion blame makes no sense. You could blame the library for passing on the signal, or the kernel for passing the signal to the library, or the compiler for generating the instruction in the first place. If we decide that the current behaviour is wrong, then we want to change the behaviour. If we want to do that, then we want do to so in the way that has the least cost for most programs and most users. Andrew.
Re: Miscompilation of remainder expressions
Andrew Haley wrote: From a performance/convenience angle, the best place to handle this is either libc or the kernel. Either of these can quite easily fix up the operands when a trap happens, with zero performance degradation of existing code. I don't think there's any need for gcc to be altered to handle this. Unfortunately this is only partially correct. As Vincent Lefe`vre mailto:[EMAIL PROTECTED] has noted in PR30484/, /PPC generates no trap but gives incorrect result: -2147483648 % -1 - -2147483648 A signal handler will not help here. Another problem is -ftrapv. You wouldn't want to kill traps on INT_MIN/-1 with -ftrapv, would you? GCC should be modified such that libc/kernel can distinguish INT_MIN/-1 from INT_MIN%-1. -- Michael Veksler http:///tx.technion.ac.il/~mveksler
Re: Miscompilation of remainder expressions
On Wed, 17 Jan 2007, Andrew Haley wrote: [...] | | To a man with a hammer, all things look like a nail. It's very | | tempting for us in gcc-land always to fix things in gcc, not because | | it's technically the right place but because it's what we control | | ourselves. | | well, I'm unclear what your point is here, but certainly GCC is | at fault for generating trapping instructions. | So, we fix the problem in GCC, not because that is what we control | ourselves, but we we failed to generate proper code. | | It's not a matter of whose fault it is; trying to apportion blame | makes no sense. we have a communication problem here. Nobody is trying to apportion blame. However, gcc is the tool that generates trapping instruction. It is unclear why it would be the responsability of the OS or libc to fix what GCC has generated in the first place. -- Gaby
Re: Miscompilation of remainder expressions
Gabriel Dos Reis writes: On Wed, 17 Jan 2007, Andrew Haley wrote: [...] | | To a man with a hammer, all things look like a nail. It's very | | tempting for us in gcc-land always to fix things in gcc, not because | | it's technically the right place but because it's what we control | | ourselves. | | well, I'm unclear what your point is here, but certainly GCC is | at fault for generating trapping instructions. | So, we fix the problem in GCC, not because that is what we control | ourselves, but we we failed to generate proper code. | | It's not a matter of whose fault it is; trying to apportion blame | makes no sense. we have a communication problem here. Nobody is trying to apportion blame. However, gcc is the tool that generates trapping instruction. It is unclear why it would be the responsability of the OS or libc to fix what GCC has generated in the first place. That makes no sense either. It's an engineering problem. We have a widget that does the wrong thing*. We have several ways to make it do the right thing, only one of which has no adverse impact on the existing users of the widget. Andrew. * (in some people's opinion)
Re: Miscompilation of remainder expressions
On Wed, Jan 17, 2007 at 05:48:34PM +, Andrew Haley wrote: From a performance/convenience angle, the best place to handle this is either libc or the kernel. Either of these can quite easily fix up the operands when a trap happens, with zero performance degradation of existing code. I don't think there's any need for gcc to be altered to handle this. How will the kernel know whether the overflow in the divide instruction is because the user's source code has a '%' and not a '/'? We generate the exact same instruction for i / minus_one(), after all, and in that case the trap really should be there. I suppose that the trap handler could try to analyze the code following the divide instruction; if the quotient result is never used and the divisor is -1, it could replace the remainder result with zero and return. But that would be rather hairy, if it is even feasible. Alternatively, the divide instruction could be marked somehow, but I have no idea how.
Re: Miscompilation of remainder expressions
On Wed, Jan 17, 2007 at 06:03:08PM +, Andrew Haley wrote: Gabriel Dos Reis writes: On Wed, 17 Jan 2007, Andrew Haley wrote: | | From a performance/convenience angle, the best place to handle this is | either libc or the kernel. Hmm, that is predicated on assumptions not convenient to users on targets that are not glibc-based or GNU/Linux-based. Well, if GNU libc/Linux/whatever can fix this bug in libc or the kernel, so can anyone else. If GCC winds up having to fix the bug in the compiler itself for PPC, then everyone could have the option of using a kernel fix or a compiler fix. But how are you going to do the kernel fix? What if the user did an integer divide and not a modulo? I suppose you could just say the result is undefined and patch up the quotient too.
RE: Miscompilation of remainder expressions
On 17 January 2007 19:09, Joe Buck wrote: On Wed, Jan 17, 2007 at 05:48:34PM +, Andrew Haley wrote: From a performance/convenience angle, the best place to handle this is either libc or the kernel. Either of these can quite easily fix up the operands when a trap happens, with zero performance degradation of existing code. I don't think there's any need for gcc to be altered to handle this. How will the kernel know whether the overflow in the divide instruction is because the user's source code has a '%' and not a '/'? We generate the exact same instruction for i / minus_one(), after all, and in that case the trap really should be there. I suppose that the trap handler could try to analyze the code following the divide instruction; if the quotient result is never used and the divisor is -1, it could replace the remainder result with zero and return. But that would be rather hairy, if it is even feasible. Alternatively, the divide instruction could be marked somehow, but I have no idea how. Didn't someone suggest a no-op prefix somewhere back up-thread? cheers, DaveK -- Can't think of a witty .sigline today
Re: Miscompilation of remainder expressions
On Wed, Jan 17, 2007 at 07:03:43PM +, Andrew Haley wrote: It's an engineering problem. We have a widget that does the wrong thing*. We have several ways to make it do the right thing, only one of which has no adverse impact on the existing users of the widget. * (in some people's opinion) Agreed, but the compiler is not just for GNU/Linux or glibc, and a trap-catching fix won't work everywhere (e.g. ppc).
Re: Miscompilation of remainder expressions
Joe Buck [EMAIL PROTECTED] writes: On Wed, Jan 17, 2007 at 05:48:34PM +, Andrew Haley wrote: From a performance/convenience angle, the best place to handle this is either libc or the kernel. Either of these can quite easily fix up the operands when a trap happens, with zero performance degradation of existing code. I don't think there's any need for gcc to be altered to handle this. How will the kernel know whether the overflow in the divide instruction is because the user's source code has a '%' and not a '/'? We generate the exact same instruction for i / minus_one(), after all, and in that case the trap really should be there. We don't need to generate a trap for INT_MIN / -1. That is undefined signed overflow. We can legitimately set the quotient register to INT_MIN while setting the remainder register to zero. (Hmmm, what should we do if -ftrapv is set? Probably generate a different code sequence in the compiler.) We do want to generate a trap for x / 0, of course. Ian
Re: Miscompilation of remainder expressions
On Wed, 17 Jan 2007, Andrew Haley wrote: | Gabriel Dos Reis writes: | On Wed, 17 Jan 2007, Andrew Haley wrote: | | [...] | | | | To a man with a hammer, all things look like a nail. It's very | | | tempting for us in gcc-land always to fix things in gcc, not because | | | it's technically the right place but because it's what we control | | | ourselves. | | | | well, I'm unclear what your point is here, but certainly GCC is | | at fault for generating trapping instructions. | | So, we fix the problem in GCC, not because that is what we control | | ourselves, but we we failed to generate proper code. | | | | It's not a matter of whose fault it is; trying to apportion blame | | makes no sense. | | we have a communication problem here. Nobody is trying to apportion | blame. However, gcc is the tool that generates trapping instruction. | It is unclear why it would be the responsability of the OS or libc | to fix what GCC has generated in the first place. | | That makes no sense either. | | It's an engineering problem. We have a widget that does the wrong | thing*. We have several ways to make it do the right thing, only one | of which has no adverse impact on the existing users of the widget. You believe there is one solution, except that it does not work for the supported target. But, I suppose that does not matter since you have decided that anything else does not make sense. -- Gaby
Re: Miscompilation of remainder expressions
Ian Lance Taylor wrote: Joe Buck [EMAIL PROTECTED] writes: How will the kernel know whether the overflow in the divide instruction is because the user's source code has a '%' and not a '/'? We generate the exact same instruction for i / minus_one(), after all, and in that case the trap really should be there. We don't need to generate a trap for INT_MIN / -1. That is undefined signed overflow. We can legitimately set the quotient register to INT_MIN while setting the remainder register to zero. (Hmmm, what should we do if -ftrapv is set? Probably generate a different code sequence in the compiler.) Simply let the kernel/libc set the overflow flag in this case, and let the compiler append an INTO instruction right after the idivl. We do want to generate a trap for x / 0, of course. Ian -- Michael Veksler http:///tx.technion.ac.il/~mveksler
Re: Miscompilation of remainder expressions
On Wed, Jan 17, 2007 at 11:17:36AM -0800, Ian Lance Taylor wrote: Joe Buck [EMAIL PROTECTED] writes: On Wed, Jan 17, 2007 at 05:48:34PM +, Andrew Haley wrote: From a performance/convenience angle, the best place to handle this is either libc or the kernel. Either of these can quite easily fix up the operands when a trap happens, with zero performance degradation of existing code. I don't think there's any need for gcc to be altered to handle this. How will the kernel know whether the overflow in the divide instruction is because the user's source code has a '%' and not a '/'? We generate the exact same instruction for i / minus_one(), after all, and in that case the trap really should be there. We don't need to generate a trap for INT_MIN / -1. That is undefined signed overflow. We can legitimately set the quotient register to INT_MIN while setting the remainder register to zero. (Hmmm, what should we do if -ftrapv is set? Probably generate a different code sequence in the compiler.) We do want to generate a trap for x / 0, of course. Then you have to fix the code generation for PPC, which never traps. All (?) 3-register arithmetic instructions have the option to set an overflow flag that you can check later. Gabriel
Re: Miscompilation of remainder expressions
Dave Korn wrote: On 17 January 2007 19:09, Joe Buck wrote: How will the kernel know whether the overflow in the divide instruction is because the user's source code has a '%' and not a '/'? We generate the exact same instruction for i / minus_one(), after all, and in that case the trap really should be there. ... Didn't someone suggest a no-op prefix somewhere back up-thread? Yes, there are two ideas (also documented in the PR): (1) IIRC idivl (%ecx) will use the eds segment register by default, so adding eds prefix will make no difference in semantics. To make it even more explicit it is possible to add two eds prefixes, just in case. If some code depends on a segmented memory model (I think that wine does), and it still wants to have GCC generate the new behavior, you'd have to use redundant prefixes such that eds ess idivl (%ecx) (I hope got the order right and the first prefix is redundant.) (2) The second option is to mark it in the executable in a different ELF section, like debug info or like C++ exception handling. This solution will make it workable only with the libc rather than the kernel modifications. -- Michael Veksler http:///tx.technion.ac.il/~mveksler
Re: Miscompilation of remainder expressions
Gabriel Dos Reis writes: On Wed, 17 Jan 2007, Andrew Haley wrote: | Gabriel Dos Reis writes: | On Wed, 17 Jan 2007, Andrew Haley wrote: | | [...] | | | | To a man with a hammer, all things look like a nail. It's very | | | tempting for us in gcc-land always to fix things in gcc, not because | | | it's technically the right place but because it's what we control | | | ourselves. | | | | well, I'm unclear what your point is here, but certainly GCC is | | at fault for generating trapping instructions. | | So, we fix the problem in GCC, not because that is what we control | | ourselves, but we we failed to generate proper code. | | | | It's not a matter of whose fault it is; trying to apportion blame | | makes no sense. | | we have a communication problem here. Nobody is trying to apportion | blame. However, gcc is the tool that generates trapping instruction. | It is unclear why it would be the responsability of the OS or libc | to fix what GCC has generated in the first place. | | That makes no sense either. | | It's an engineering problem. We have a widget that does the wrong | thing*. We have several ways to make it do the right thing, only one | of which has no adverse impact on the existing users of the widget. You believe there is one solution, except that it does not work for the supported target. Sorry, I don't understand what you mean by that. I've been thinking about why we see this so very differently, and it's dawned on me why that is. I first came across this architectural feature of the 8086 in the mid-1980s. To begin with, there was no divide overflow handler at all: the machine would simply crash. It took me a little while to figure out what was happening, but once I'd done so it was a simple matter to write a few lines of assembly language that fix up the operands and carry on. Fast-forward ten years or so and for the first time I come across unices running on an x86. And I was surprised to see that rather than fixing up the operands and continuing, the kernel punted the problem to the user's program, which usually responded by core dumping. OK, I thought, that must be what UNIX programmers want. This trap must be desired, because it is trivially easy to fixup and continue. Perhaps it's because programmers want to be alerted that there is a bug in their program. And that's what I thought until last week. :-) Andrew.
Re: Miscompilation of remainder expressions
On Wed, Jan 17, 2007 at 07:42:38PM +, Andrew Haley wrote: Gabriel Dos Reis writes: You believe there is one solution, except that it does not work for the supported target. Sorry, I don't understand what you mean by that. I suspect that he meant to write one supported target; it won't work for ppc.
Re: Miscompilation of remainder expressions
On Wed, 17 Jan 2007, Joe Buck wrote: | On Wed, Jan 17, 2007 at 07:42:38PM +, Andrew Haley wrote: | Gabriel Dos Reis writes: |You believe there is one solution, except that it does not work for |the supported target. | | Sorry, I don't understand what you mean by that. | | I suspect that he meant to write one supported target; it won't work | for ppc. yes, thank you. Sorry for mistyping. -- Gaby
Re: Miscompilation of remainder expressions
H .. I wish some of the more important bugs in gcc received the attention that this very unimportant issue is receiving :-) I guess the difference is that lots of people can understand this issue. Reminds me of the hullabaloo over the Pentium division problem. The fact of the matter was that the Pentium had many more serious problems, but they were not well known, and often much more complex to understand!
Re: Miscompilation of remainder expressions
Joe Buck wrote: If GCC winds up having to fix the bug in the compiler itself for PPC, then everyone could have the option of using a kernel fix or a compiler fix. But how are you going to do the kernel fix? What if the user did an integer divide and not a modulo? I suppose you could just say the result is undefined and patch up the quotient too. exactly! And if you want this undefined operation to do something defined, you can start another one of those long threads :-)
Re: Miscompilation of remainder expressions
Ian Lance Taylor wrote: We do want to generate a trap for x / 0, of course. Really? Is this really defined to generate a trap in C? I would be surprised if so ...
Re: Miscompilation of remainder expressions
Robert Dewar [EMAIL PROTECTED] writes: Ian Lance Taylor wrote: We do want to generate a trap for x / 0, of course. Really? Is this really defined to generate a trap in C? I would be surprised if so ... As far as I know, but I think it would be a surprising change for x / 0 to silently continue executing. But perhaps not a very important one. Ian
Re: Miscompilation of remainder expressions
Ian Lance Taylor [EMAIL PROTECTED] writes: | Robert Dewar [EMAIL PROTECTED] writes: | | Ian Lance Taylor wrote: | | We do want to generate a trap for x / 0, of course. | | Really? Is this really defined to generate a trap in C? | I would be surprised if so ... | | As far as I know, but I think it would be a surprising change for x / | 0 to silently continue executing. furthermore, limits has been defined so that numeric_limitsint::traps reports true when division by zero traps. // GCC only intrinsicly supports modulo integral types. The only remaining // integral exceptional values is division by zero. Only targets that do not // signal division by zero in some hard to ignore way should use false. #ifndef __glibcxx_integral_traps # define __glibcxx_integral_traps true #endif -- Gaby
Re: Miscompilation of remainder expressions
On Wed, Jan 17, 2007 at 04:15:08PM -0800, Ian Lance Taylor wrote: Robert Dewar [EMAIL PROTECTED] writes: Ian Lance Taylor wrote: We do want to generate a trap for x / 0, of course. Really? Is this really defined to generate a trap in C? I would be surprised if so ... As far as I know, but I think it would be a surprising change for x / 0 to silently continue executing. That's exactly what happens on PPC. But perhaps not a very important one. Indeed. Gabriel
Re: Miscompilation of remainder expressions
Ian Lance Taylor wrote: Robert Dewar [EMAIL PROTECTED] writes: Ian Lance Taylor wrote: We do want to generate a trap for x / 0, of course. Really? Is this really defined to generate a trap in C? I would be surprised if so ... As far as I know, but I think it would be a surprising change for x / 0 to silently continue executing. But perhaps not a very important one. It depends on the front-end language. For C, perhaps is would not matter. For Java, the language specification requires an ArithmaticException to be thrown. In libgcj this is done by having the operation trap and the trap handler generates the exception. Because libgcj already handles all of this, it was brought up that a similar runtime trap handler could easily be used for C. However as others have noted, the logistics of universally using a trap handler in C might be difficult. David Daney
Re: Miscompilation of remainder expressions
Gabriel Paubert [EMAIL PROTECTED] writes: | On Wed, Jan 17, 2007 at 04:15:08PM -0800, Ian Lance Taylor wrote: | Robert Dewar [EMAIL PROTECTED] writes: | | Ian Lance Taylor wrote: | |We do want to generate a trap for x / 0, of course. | | Really? Is this really defined to generate a trap in C? | I would be surprised if so ... | | As far as I know, but I think it would be a surprising change for x / | 0 to silently continue executing. | | | That's exactly what happens on PPC. Indeed, and Andrew Pinski corrected numeric_limitsint to reflect the reality on PPC for that specific case. C++ forces compilers to reveal their semantics for built-in types through numeric_limits. Every time you change the behaviour, you also implicilty break an ABI. -- Gaby
Re: Miscompilation of remainder expressions
On Wed, Jan 17, 2007 at 06:40:21PM -0500, Robert Dewar wrote: H .. I wish some of the more important bugs in gcc received the attention that this very unimportant issue is receiving :-) I guess the difference is that lots of people can understand this issue. Yes, this phenomenon has been given a name, by Parkinson of Parkinson's law fame: bike shed. Someone even made a web site dedicated to the phenomenon: http://www.bikeshed.org/ Parkinson shows how you can go in to the board of directors and get approval for building a multi-million or even billion dollar atomic power plant, but if you want to build a bike shed you will be tangled up in endless discussions. As for the issue at hand, we've basically exhausted it; every reasonable combination of solutions has been proposed, as well as don't fix it.
Re: Miscompilation of remainder expressions
On Jan 17, 2007, at 4:44 PM, Gabriel Dos Reis wrote: C++ forces compilers to reveal their semantics for built-in types through numeric_limits. Every time you change the behaviour, you also implicilty break an ABI. No, the ABI does not document that the answer never changes between translation units, only that for this translation unit, what the answer happens to be. If it said what you thought it said, you'd be able to quote it. If you think I'm wrong, I look forward to the quote. Consider the ABI document that says that the size of int is 4. One cannot meaningfully use a compiler flag to change the size of an int to something other than 4 because then, that flag breaks the ABI. An ABI document _can_ state that the answer to the question must be true for float, but, absent it stating that it is true, there isn't a document that says that it is true.
Re: Miscompilation of remainder expressions
On Wed, 17 Jan 2007, Mike Stump wrote: | On Jan 17, 2007, at 4:44 PM, Gabriel Dos Reis wrote: | C++ forces compilers to reveal their semantics for built-in types | through numeric_limits. Every time you change the behaviour, | you also implicilty break an ABI. | | No, the ABI does not document that the answer never changes between | translation units, only that for this translation unit, what the | answer happens to be. If it said what you thought it said, you'd be | able to quote it. If you think I'm wrong, I look forward to the quote. (1) the ABI I was talking about is that of libstdc++, not that of the processor. Sorry if that wasn't clearer (I switched to the library developer perspective, and should have made that clearer). Each time we make changes to libstdc++ ABI, people get very nervous. (2) numeric_limits cannot change from translation unit to translation unit, within the same program otherwise you break the ODR. I guess we all agree on that. -- Gaby
Re: Miscompilation of remainder expressions
On Jan 17, 2007, at 6:46 PM, Gabriel Dos Reis wrote: (1) the ABI I was talking about is that of libstdc++ (2) numeric_limits cannot change from translation unit to translation unit, within the same program otherwise you break the ODR. I guess we all agree on that. Doh! Did I ever say that I hate abi issues, this truly is plainly obvious... and yet I still missed it. Thanks. Anyway, that would just mean that any abi document that attempts a C+ + ABI must specify these answers. The issue is that if one implemented a new C++ compiler, attempting to match the ABI of the previous one, I think it'd be bad form to cheat off the actual implementation for the answer, rather the document should specify the answer. The issue reminds me of Sun's attempt to do a C+ abi that didn't talk about templates or EH, nice, but not as useful as one that does.
Re: Miscompilation of remainder expressions
Joe Buck wrote: (off topic!) On Wed, Jan 17, 2007 at 06:40:21PM -0500, Robert Dewar wrote: H .. I wish some of the more important bugs in gcc received the attention that this very unimportant issue is receiving :-) I guess the difference is that lots of people can understand this issue. Yes, this phenomenon has been given a name, by Parkinson of Parkinson's law fame: bike shed. Actually I don't think Parkinson uses this term. He states a similar principle as: * THE LAW OF TRIVIALITY: The time spent on any item of a committee's agenda will be in inverse proportion to the sum of money involved.
Re: Miscompilation of remainder expressions
Gabriel Paubert wrote: On Mon, Jan 15, 2007 at 10:34:23PM +0200, Michael Veksler wrote: Once the kernel sees the FP trap (whatever its i368 name is), it decodes the machine code and finds: idivl (%ecx). As far as I remember, this will put the result in two registers one for div_res and one for mod_res. Since MIN_INT/-1 is undefined, the kernel may put MIN_INT in div_res, and mod_res=1. Then return to the following instruction. Should I open a request for the kernel? No, because the instruction has actually two result values: - the remainder, which you could safely set to zero (not 1!) My typo, right. - the quotient, which is affected by the overflow and there may be compiler and languages that rely on the exception being generated. Right, there are languages besides C/C++ and compilers other than GCC, not to speak of assembly code. Solution: let GCC generate a redundant prefix, such as ecs. If ecs eds idivl (%ecx). or ecs ess idivl(%ecx) or ecs ecs idivl(%ecx) etc. generates a trap, only then will the kernel set the remainder to 0 and the quotient to MIN_INT. (Starting with i686 decoding redundant prefixes costs zero cycles, am I right?) The kernel cannot know whether you are going to use the quotient or not by simply decoding the instruction. It does not matter if quotient is used because in C/C++ its value is undefined. For -fwrapv -MIN_INT/-1 == -MIN_INT*-1 == -MIN_INT. For -ftrapv, then yes we want the signal (otherwise more instructions are required to trap on the overflow). Actually I believe that a%b and a%(-b) always return the same value if we follow the C99 specification. So if you are only interested in the remainder, you can simply use a%abs(b) instead of a%b. The overhead of abs() is really small. Compared to the slow idivl, abs could be negligible, right. However, abs does introduce new data dependence which might add a noticeable cost. My x86 assembly days have gone twelve years ago, so I can't remember: Is there an abs instruction in the i386 instruction set? If not, then adding a conditional branch for: a=a0?-a:a is not that cheap. It uses up branch-prediction resources, and if it misses predictions then branching can be quite slow (depending on e.g. pipeline depth). Such a change has to be benchmarked. People are not going to be happy if this makes their code regress by 5%. -- Michael Veksler http:///tx.technion.ac.il/~mveksler
Re: Miscompilation of remainder expressions
Compared to the slow idivl, abs could be negligible, right. However, abs does introduce new data dependence which might add a noticeable cost. Is there an abs instruction in the i386 instruction set? No, the closest thing (input in eax, output in edx) is cltq addl %edx, %eax xorl %eax, %edx But the register allocations constraints are pretty heavy considering that idivl already puts strain on the RA. Paolo
Re: Miscompilation of remainder expressions
Paolo Bonzini wrote: Compared to the slow idivl, abs could be negligible, right. However, abs does introduce new data dependence which might add a noticeable cost. Is there an abs instruction in the i386 instruction set? No, the closest thing (input in eax, output in edx) is cltq addl %edx, %eax xorl %eax, %edx But the register allocations constraints are pretty heavy considering that idivl already puts strain on the RA. Paolo Paolo, what does the cltq instruction do? I cannot find it in my x86 reference manuals...
Re: Miscompilation of remainder expressions
cltq addl %edx, %eax xorl %eax, %edx But the register allocations constraints are pretty heavy considering that idivl already puts strain on the RA. Paolo, what does the cltq instruction do? I cannot find it in my x86 reference manuals... Uhm, I meant cltd and it is the same as cdq in the intel syntax. cltq is an x86-64 instruction and it is the same as cdqe in the intel syntax. Paolo
Re: Miscompilation of remainder expressions
Michael Veksler writes: Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? All the best, This problem is quite rare in practice (otherwise there would be much more complaining). As such it may be too expensive, performance-wise, to fix in GCC. It seems as one of those classical things that can be worked-around in the kernel. I guess, or it can be fixed-up in user space. We already do this for the Java language. Andrew.
Re: Miscompilation of remainder expressions
Andrew Haley [EMAIL PROTECTED] writes: | Michael Veksler writes: | Roberto Bagnara wrote: | |Reading the thread Autoconf manual's coverage of signed integer |overflow portability I was horrified to discover about GCC's |miscompilation of the remainder expression that causes INT_MIN % -1 |to cause a SIGFPE on CPUs of the i386 family. Are there plans to |fix this bug (which, to me, looks quite serious)? |All the best, | | This problem is quite rare in practice (otherwise there would be | much more complaining). As such it may be too expensive, | performance-wise, to fix in GCC. It seems as one of those | classical things that can be worked-around in the kernel. | | I guess, or it can be fixed-up in user space. We already do this for | the Java language. Andrew pointed me to his implementation. I, however, have a question: why do we need to mess with signals at all? I mean, could not we generate the following for %: rem a b := if abs(b) == 1 return 0 return machine-instruction a b is there any other corner case that will trigger the trap? -- Gaby
Re: Miscompilation of remainder expressions
Gabriel Dos Reis writes: Andrew Haley [EMAIL PROTECTED] writes: | Michael Veksler writes: | Roberto Bagnara wrote: | |Reading the thread Autoconf manual's coverage of signed integer |overflow portability I was horrified to discover about GCC's |miscompilation of the remainder expression that causes INT_MIN % -1 |to cause a SIGFPE on CPUs of the i386 family. Are there plans to |fix this bug (which, to me, looks quite serious)? |All the best, | | This problem is quite rare in practice (otherwise there would be | much more complaining). As such it may be too expensive, | performance-wise, to fix in GCC. It seems as one of those | classical things that can be worked-around in the kernel. | | I guess, or it can be fixed-up in user space. We already do this for | the Java language. Andrew pointed me to his implementation. I, however, have a question: why do we need to mess with signals at all? I mean, could not we generate the following for %: rem a b := if abs(b) == 1 return 0 return machine-instruction a b is there any other corner case that will trigger the trap? I have tried it, and it is pretty expensive. It messes up the pipelines and it hides the % from the optimizer. IMO we should not do this by default, since it's such a nitpicky corner case. Andrew.
Re: Miscompilation of remainder expressions
Andrew Haley [EMAIL PROTECTED] writes: | Gabriel Dos Reis writes: | Andrew Haley [EMAIL PROTECTED] writes: | | | Michael Veksler writes: | | Roberto Bagnara wrote: | | | |Reading the thread Autoconf manual's coverage of signed integer | |overflow portability I was horrified to discover about GCC's | |miscompilation of the remainder expression that causes INT_MIN % -1 | |to cause a SIGFPE on CPUs of the i386 family. Are there plans to | |fix this bug (which, to me, looks quite serious)? | |All the best, | | | | This problem is quite rare in practice (otherwise there would be | | much more complaining). As such it may be too expensive, | | performance-wise, to fix in GCC. It seems as one of those | | classical things that can be worked-around in the kernel. | | | | I guess, or it can be fixed-up in user space. We already do this for | | the Java language. | | Andrew pointed me to his implementation. | I, however, have a question: why do we need to mess with signals at all? | I mean, could not we generate the following for %: | | rem a b := | if abs(b) == 1 |return 0 | return machine-instruction a b | | is there any other corner case that will trigger the trap? | | I have tried it, and it is pretty expensive. It messes up the | pipelines and it hides the % from the optimizer. Aha, thanks. | IMO we should not do this by default, since it's such a nitpicky | corner case. At this point, without having tried (C/C++) implementations and their effects on most software, I have no definitive opinion -- except that we do something about it. -- Gaby
Re: Miscompilation of remainder expressions
Andrew Haley wrote: Roberto Bagnara writes: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? No, there aren't. It would make more sense for you to wrap % in some code that checks for this, rather than for us to slow down every division for this one special case. With all due respect, I must say I am shocked. I always thought (and taught) that we, Free Software people, value standard conformance and getting things right. Now we have a bug that can shut down airplanes and dealing with it is (in extreme synthesis) assimilated to nitpicking. I have not found a mention of this bug in the Known Bugs section of http://gcc.gnu.org: perhaps I missed it, but I think it definitely should be brought to the attention of the users since, IMHO, no one really expects a remainder expression to cause a SIGFPE. I have also looked at the bug database, and I did not find any report concerning this bug, so I created one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30484 A final remark: I think that today the problem is safety, not speed. I don't think doing the right thing for remainder expression will have such a high cost with the help of the optimizer and, maybe, assistance from the kernel. But even if the cost turns out to be high, the actual state of things is unacceptable: mentioning the bug prominently in the documentation, trying to change the standard, ..., whatever; but not leaving things as they are. All the best, Roberto -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:[EMAIL PROTECTED]
Re: Miscompilation of remainder expressions
Roberto Bagnara writes: Andrew Haley wrote: Roberto Bagnara writes: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? No, there aren't. It would make more sense for you to wrap % in some code that checks for this, rather than for us to slow down every division for this one special case. With all due respect, I must say I am shocked. I always thought (and taught) that we, Free Software people, value standard conformance and getting things right. This is a disgreement about interpretation of the langauge in the standard, which is: The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined. When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.87) If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a. If the quotient a/b is *not* representable, is the behaviour of % well-defined or not? It doesn't say. Andrew.
Re: Miscompilation of remainder expressions
On Tuesday 16 January 2007 16:50, Andrew Haley wrote: Roberto Bagnara writes: Andrew Haley wrote: Roberto Bagnara writes: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? No, there aren't. It would make more sense for you to wrap % in some code that checks for this, rather than for us to slow down every division for this one special case. With all due respect, I must say I am shocked. I always thought (and taught) that we, Free Software people, value standard conformance and getting things right. This is a disgreement about interpretation of the langauge in the standard, which is: The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined. When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.87) If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a. If the quotient a/b is *not* representable, is the behaviour of % well-defined or not? It doesn't say. In ada/exp_ch4.adb you will find: -- Deal with annoying case of largest negative number remainder -- minus one. Gigi does not handle this case correctly, because -- it generates a divide instruction which may trap in this case. -- In fact the check is quite easy, if the right operand is -1, -- then the mod value is always 0, and we can just ignore the -- left operand completely in this case. Ada semantics require INT_MIN rem -1 to be zero. Best wishes, Duncan.
Re: Miscompilation of remainder expressions
Andrew Haley wrote: Roberto Bagnara writes: Andrew Haley wrote: Roberto Bagnara writes: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? No, there aren't. It would make more sense for you to wrap % in some code that checks for this, rather than for us to slow down every division for this one special case. With all due respect, I must say I am shocked. I always thought (and taught) that we, Free Software people, value standard conformance and getting things right. This is a disgreement about interpretation of the langauge in the standard, which is: The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined. When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.87) If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a. If the quotient a/b is *not* representable, is the behaviour of % well-defined or not? It doesn't say. To the point that, when a/b is not representable, raising SIGFPE for a%b is standard conformant behavior? Note however that I am not saying that the standard is not defective. Who knows how to write and submit C/C++ standard defect reports? Let us do that, assuming that such a report has not been submitted already. -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:[EMAIL PROTECTED]
Re: Miscompilation of remainder expressions
Roberto Bagnara writes: Andrew Haley wrote: If the quotient a/b is *not* representable, is the behaviour of % well-defined or not? It doesn't say. To the point that, when a/b is not representable, raising SIGFPE for a%b is standard conformant behavior? Note however that I am not saying that the standard is not defective. Who knows how to write and submit C/C++ standard defect reports? Let us do that, assuming that such a report has not been submitted already. It's already been done. Andrew.
Re: Miscompilation of remainder expressions
On 16/01/07, Duncan Sands [EMAIL PROTECTED] wrote:
On Tuesday 16 January 2007 16:50, Andrew Haley wrote:
Roberto Bagnara writes:
Andrew Haley wrote:
Roberto Bagnara writes:
Reading the thread Autoconf manual's coverage of signed integer
overflow portability I was horrified to discover about GCC's
miscompilation of the remainder expression that causes INT_MIN % -1
to cause a SIGFPE on CPUs of the i386 family. Are there plans to
fix this bug (which, to me, looks quite serious)?
No, there aren't. It would make more sense for you to wrap % in some
code that checks for this, rather than for us to slow down every division
for this one special case.
With all due respect, I must say I am shocked. I always thought
(and taught) that we, Free Software people, value standard conformance
and getting things right.
This is a disgreement about interpretation of the langauge in the
standard, which is:
The result of the / operator is the quotient from the division of the
first operand by the second; the result of the % operator is the
remainder. In both operations, if the value of the second operand is
zero, the behavior is undefined. When integers are divided, the result
of the / operator is the algebraic quotient with any fractional part
discarded.87) If the quotient a/b is representable, the expression
(a/b)*b + a%b shall equal a.
If the quotient a/b is *not* representable, is the behaviour of %
well-defined or not? It doesn't say.
In ada/exp_ch4.adb you will find:
-- Deal with annoying case of largest negative number remainder
-- minus one. Gigi does not handle this case correctly, because
-- it generates a divide instruction which may trap in this case.
-- In fact the check is quite easy, if the right operand is -1,
-- then the mod value is always 0, and we can just ignore the
-- left operand completely in this case.
Ada semantics require INT_MIN rem -1 to be zero.
FWIW,
[EMAIL PROTECTED]:~$ gcc --version
gcc (GCC) 4.0.3 (Ubuntu 4.0.3-1ubuntu5)
[EMAIL PROTECTED]:~$ cat test.c
#include limits.h
#include stdio.h
int main(void) {
int z = INT_MIN % -1;
printf(%d %% %d - %d\n, INT_MIN, -1, z);
return 0;
}
[EMAIL PROTECTED]:~$ gcc -Wall -Wextra test.c -o test
[EMAIL PROTECTED]:~$ ./test
-2147483648 % -1 - 0
[EMAIL PROTECTED]:~$ cat test.c
#include limits.h
#include stdio.h
int modulo(int dividend, int divisor)
{
return dividend % divisor;
}
int main(void) {
int z = modulo(INT_MIN, -1);
printf(%d %% %d - %d\n, INT_MIN, -1, z);
return 0;
}
[EMAIL PROTECTED]:~$ gcc -Wall -Wextra test.c -o test
[EMAIL PROTECTED]:~$ ./test
Floating point exception
[EMAIL PROTECTED]:~$ gcc -O2 -Wall -Wextra test.c -o test
[EMAIL PROTECTED]:~$ ./test
Floating point exception
[EMAIL PROTECTED]:~$ gcc -O3 -Wall -Wextra test.c -o test
[EMAIL PROTECTED]:~$ ./test
-2147483648 % -1 - 0
I don't know whether results are different in mainline.
Cheers,
Manuel.
Re: Miscompilation of remainder expressions
It's interesting that the same issue arose with GNAT, but we had no option to ignore the special case, since one of the official Ada validation test programs tested this case, and indeed as you see below there is a special test: function q (a, b : integer) return integer is begin return a rem b; end; generates Source recreated from tree for q (body) --- function q (a : integer; b : integer) return integer is begin [constraint_error when b = 0 divide by zero] return integer((if b = -1 then 0 else a rem b)); end q; And indeed this is a nasty hit in efficiency, though in practice the wide spread use of integer types with restricted ranges means that most of the time you know for example that the divisor cannot be negative.
Re: Miscompilation of remainder expressions
Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? All the best, Roberto P.S. I checked whether this bug affects my code and it does. Before yesterday I was completely unsuspecting of such a fundamental flaw... I wonder how many know about it. It's truly amazing for real code to be computing remainders in this domain ... seems a bad idea to me, since very few people are comfortably aware of what remainder means for such cases.
Re: Miscompilation of remainder expressions
Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? Seems ultra-non-serious to me, hard to believe this case appears in real code, despite surprising claim by Roberto.
Re: Miscompilation of remainder expressions
Robert Dewar wrote: Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? Seems ultra-non-serious to me, hard to believe this case appears in real code, despite surprising claim by Roberto. It seems to me that you would know that it is happening. If it hits you, you don't get hard to find wierd program results. Your program is killed by SIGFPE. David Daney
Re: Miscompilation of remainder expressions
Roberto Bagnara wrote: Andrew Haley wrote: Roberto Bagnara writes: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? No, there aren't. It would make more sense for you to wrap % in some code that checks for this, rather than for us to slow down every division for this one special case. With all due respect, I must say I am shocked. I always thought (and taught) that we, Free Software people, value standard conformance and getting things right. Now we have a bug that can shut down airplanes Please do not indulge in excessive rhetoric, planes do not get shut down by compiler bugs. If you really think that the integrity of avionics software depends on bug free compilers you have no idea what you are talking about (I would guess you are for example unfamiliar with DO-178B certification). Yes, it's a bug, is it a serious bug, no? Will real software be affected? no. Indeed I find any program that actually does this remainder operation in practice to be highly suspect. A final remark: I think that today the problem is safety, not speed. I don't think doing the right thing for remainder expression will have such a high cost with the help of the optimizer and, maybe, assistance from the kernel. But even if the cost turns out to be high, the actual state of things is unacceptable: mentioning the bug prominently in the documentation, trying to change the standard, ..., whatever; but not leaving things as they are. Yes, it should probably be fixed, but making a major fuss about it seems peculiar at best. I think it is perfectly reasonable for you to propose a patch to fix this if you are specially concerned, but don't expect the community to rush to fix this particular bug at high priority in response to this complaint. There are lots of known bugs far more important than this one.
Re: Miscompilation of remainder expressions
Roberto Bagnara wrote: To the point that, when a/b is not representable, raising SIGFPE for a%b is standard conformant behavior? possibly so .. Note however that I am not saying that the standard is not defective. Who knows how to write and submit C/C++ standard defect reports? Let us do that, assuming that such a report has not been submitted already. not clear that this is a defect, I would find it quite reasonable for the C standard to recognize this anticipatable case, and decide that a%b is undefined if a/b is undefined.
Re: Miscompilation of remainder expressions
On Tue, Jan 16, 2007 at 08:22:10AM -0600, Gabriel Dos Reis wrote: I mean, could not we generate the following for %: rem a b := if abs(b) == 1 return 0 return machine-instruction a b On x86 processors that have conditional moves, why not do the equivalent of neg_b = -b; cmov(last result is negative,neg_b,b) __machine_rem(a,b) Then there's no disruption of the pipeline.
Re: Miscompilation of remainder expressions
Robert Dewar wrote: Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? All the best, Roberto P.S. I checked whether this bug affects my code and it does. Before yesterday I was completely unsuspecting of such a fundamental flaw... I wonder how many know about it. It's truly amazing for real code to be computing remainders in this domain ... seems a bad idea to me, since very few people are comfortably aware of what remainder means for such cases. Everyone knows that dividing a number by -1 or 1 gives a 0 remainder. To the contrary, no one expects a%b to raise SIFPE when b != 0. -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:[EMAIL PROTECTED]
Re: Miscompilation of remainder expressions
Andrew Haley [EMAIL PROTECTED] writes: | Roberto Bagnara writes: | Andrew Haley wrote: |Roberto Bagnara writes: | | Reading the thread Autoconf manual's coverage of signed integer | overflow portability I was horrified to discover about GCC's | miscompilation of the remainder expression that causes INT_MIN % -1 | to cause a SIGFPE on CPUs of the i386 family. Are there plans to | fix this bug (which, to me, looks quite serious)? | |No, there aren't. It would make more sense for you to wrap % in some |code that checks for this, rather than for us to slow down every division |for this one special case. | | With all due respect, I must say I am shocked. I always thought | (and taught) that we, Free Software people, value standard conformance | and getting things right. | | This is a disgreement about interpretation of the langauge in the | standard, which is: | | The result of the / operator is the quotient from the division of the | first operand by the second; the result of the % operator is the | remainder. In both operations, if the value of the second operand is | zero, the behavior is undefined. When integers are divided, the result | of the / operator is the algebraic quotient with any fractional part | discarded.87) If the quotient a/b is representable, the expression | (a/b)*b + a%b shall equal a. | | If the quotient a/b is *not* representable, is the behaviour of % | well-defined or not? It doesn't say. Andrew and me exchanged (private) viewpoints of this yesterday. I would like to add something I forgot to say. By definition, the absolute value of a % b is always less than the absolute value of b. Consequently, a % b is always defined. -- Gaby
Re: Miscompilation of remainder expressions
Duncan Sands [EMAIL PROTECTED] writes: [...] | Ada semantics require INT_MIN rem -1 to be zero. I cannot see any other value as a result. -- Gaby
Re: Miscompilation of remainder expressions
Roberto Bagnara wrote: Robert Dewar wrote: Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? All the best, Roberto P.S. I checked whether this bug affects my code and it does. Before yesterday I was completely unsuspecting of such a fundamental flaw... I wonder how many know about it. It's truly amazing for real code to be computing remainders in this domain ... seems a bad idea to me, since very few people are comfortably aware of what remainder means for such cases. Everyone knows that dividing a number by -1 or 1 gives a 0 remainder. To the contrary, no one expects a%b to raise SIFPE when b != 0. On the contrary, since the beginning of time SIGFPE has been generated on GCC/x86/linux under these conditions. This is wildly known. Just because you just found out about it does not mean that 'no one' expects it. David Daney
Re: Miscompilation of remainder expressions
Robert Dewar wrote: Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? Seems ultra-non-serious to me, hard to believe this case appears in real code, despite surprising claim by Roberto. How do you test if a number is a multiple of another one? What about rounding toward zero to a multiple of k? I guess x - x%k looks like unreal code to you. -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:[EMAIL PROTECTED]
Re: Miscompilation of remainder expressions
Gabriel Paubert wrote: \ No, because the instruction has actually two result values: - the remainder, which you could safely set to zero (not 1!) - the quotient, which is affected by the overflow and there may be compiler and languages that rely on the exception being generated. But the division is undefined, programs have no right to rely on an exception being generated.
RE: Miscompilation of remainder expressions
On 16 January 2007 18:23, Robert Dewar wrote: Gabriel Paubert wrote: \ No, because the instruction has actually two result values: - the remainder, which you could safely set to zero (not 1!) - the quotient, which is affected by the overflow and there may be compiler and languages that rely on the exception being generated. But the division is undefined, programs have no right to rely on an exception being generated. It really depends whether you think of the % operator as being an atomic mathematical operation, or a compound function involving real division and multiplication and subtraction. I think the wording of the standard says only that the inequality (a/b)*b + a%b == a does not hold when (a/b) cannot be represented, but does not deny the modulo operator the option of just returning the correct result, which is representable. cheers, DaveK -- Can't think of a witty .sigline today
Re: Miscompilation of remainder expressions
Robert Dewar wrote: Roberto Bagnara wrote: Andrew Haley wrote: Roberto Bagnara writes: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? No, there aren't. It would make more sense for you to wrap % in some code that checks for this, rather than for us to slow down every division for this one special case. With all due respect, I must say I am shocked. I always thought (and taught) that we, Free Software people, value standard conformance and getting things right. Now we have a bug that can shut down airplanes Please do not indulge in excessive rhetoric, planes do not get shut down by compiler bugs. If you really think that the integrity of avionics software depends on bug free compilers you have no idea what you are talking about (I would guess you are for example unfamiliar with DO-178B certification). You are right: I am not familiar with DO-178B certification. Yes, it's a bug, is it a serious bug, no? Will real software be affected? no. Indeed I find any program that actually does this remainder operation in practice to be highly suspect. But I am not wrong if I say that a bug is a bug and must be fixed. I was answering to a message saying (basically) we won't fix it since there is a performance penalty to be paid. I do not feel to be excessively rhetoric if I say that others, not us, are said to knowingly disregard standards, whether it be for performance reasons or for other reasons. Of course, this is a matter of taste. A final remark: I think that today the problem is safety, not speed. I don't think doing the right thing for remainder expression will have such a high cost with the help of the optimizer and, maybe, assistance from the kernel. But even if the cost turns out to be high, the actual state of things is unacceptable: mentioning the bug prominently in the documentation, trying to change the standard, ..., whatever; but not leaving things as they are. Yes, it should probably be fixed, but making a major fuss about it seems peculiar at best. I think it is perfectly reasonable for you to propose a patch to fix this if you are specially concerned, but don't expect the community to rush to fix this particular bug at high priority in response to this complaint. I am sorry if I brought you to think that I am asking something for me. There is no longer a problem for me personally: I will simply stop using % in my projects (which, by the way are in C++) and will use custom functions instead. I have almost finished an Autoconf test to check for this bug. Most importantly, I am now perfectly aware of the problem. I have filed a couple of bug reports, one for GCC and the other for the Intel C/C++ compiler. I have been told that a C Standard Defect Report already exists on this subject. So, it is the end of the story, as far as I am personally concerned. Concerning the community (to which I belong, by the way) I propose that, to start with, the documentation is modified to mention this problem in a prominent way. The text can be borrowed from the new Autoconf's documentation that has been recently discussed on this list. There are lots of known bugs far more important than this one. Wow! I hope they are all in Bugzilla: the one we are talking about was apparently not there until a couple of hours ago. -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:[EMAIL PROTECTED]
Re: Miscompilation of remainder expressions
Dave Korn wrote: On 16 January 2007 18:23, Robert Dewar wrote: Gabriel Paubert wrote: \ No, because the instruction has actually two result values: - the remainder, which you could safely set to zero (not 1!) - the quotient, which is affected by the overflow and there may be compiler and languages that rely on the exception being generated. But the division is undefined, programs have no right to rely on an exception being generated. It really depends whether you think of the % operator as being an atomic mathematical operation, or a compound function involving real division and multiplication and subtraction. I think the wording of the standard says only that the inequality (a/b)*b + a%b == a does not hold when (a/b) cannot be represented, but does not deny the modulo operator the option of just returning the correct result, which is representable. I think you missed my point For sure a/b is undefined, so the trap routine does not have to worry about the case where the trap comes from a/b, it only has to worry about the case where the remainder is wanted, so setting the remainder is indeed safe. cheers, DaveK
Re: Miscompilation of remainder expressions
Roberto Bagnara wrote: I am sorry if I brought you to think that I am asking something for me. There is no longer a problem for me personally: I will simply stop using % in my projects (which, by the way are in C++) and will use custom functions instead. I have almost finished an Autoconf test to check for this bug. Most importantly, I am now perfectly aware of the problem. I have filed a couple of bug reports, one for GCC and the other for the Intel C/C++ compiler. I have been told that a C Standard Defect Report already exists on this subject. So, it is the end of the story, as far as I am personally concerned. Concerning the community (to which I belong, by the way) I propose that, to start with, the documentation is modified to mention this problem in a prominent way. The text can be borrowed from the new Autoconf's documentation that has been recently discussed on this list. OK, so sounds like this bug definitely is in the status of being of extremly low priority, since the only user who has ever cared about it so far doesn't care any more There are lots of known bugs far more important than this one. Wow! Are you *really* surprised by that statement above, if so it's pretty amazing. I hope they are all in Bugzilla: the one we are talking about was apparently not there until a couple of hours ago. Maybe they are may be not, it's not that critical, since there are lots of serious bugs that are not known. So you can never write programs that critically depend on compiler correctness.
RE: Miscompilation of remainder expressions
On 16 January 2007 18:42, Robert Dewar wrote: Dave Korn wrote: On 16 January 2007 18:23, Robert Dewar wrote: Gabriel Paubert wrote: \ No, because the instruction has actually two result values: - the remainder, which you could safely set to zero (not 1!) - the quotient, which is affected by the overflow and there may be compiler and languages that rely on the exception being generated. But the division is undefined, programs have no right to rely on an exception being generated. It really depends whether you think of the % operator as being an atomic mathematical operation, or a compound function involving real division and multiplication and subtraction. I think the wording of the standard says only that the inequality (a/b)*b + a%b == a does not hold when (a/b) cannot be represented, but does not deny the modulo operator the option of just returning the correct result, which is representable. I think you missed my point Oops, yeh. I was thinking of Andrew Haley's question about the wording of the language in the standard. cheers, DaveK -- Can't think of a witty .sigline today
Re: Miscompilation of remainder expressions
On Tue, Jan 16, 2007 at 12:05:12PM -0600, Gabriel Dos Reis wrote: By definition, the absolute value of a % b is always less than the absolute value of b. Consequently, a % b is always defined. Nitpick: for nonzero b.
Re: Miscompilation of remainder expressions
On Tue, 16 Jan 2007, Joe Buck wrote: | On Tue, Jan 16, 2007 at 12:05:12PM -0600, Gabriel Dos Reis wrote: | By definition, the absolute value of a % b is always less than the | absolute value of b. Consequently, a % b is always defined. | | Nitpick: for nonzero b. yes, I assumed that -- since the standard says that the result is undefined when b is zero. I should have repeated that assumption. -- Gaby
Re: Miscompilation of remainder expressions
David Daney wrote: Roberto Bagnara wrote: Robert Dewar wrote: Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? All the best, Roberto P.S. I checked whether this bug affects my code and it does. Before yesterday I was completely unsuspecting of such a fundamental flaw... I wonder how many know about it. It's truly amazing for real code to be computing remainders in this domain ... seems a bad idea to me, since very few people are comfortably aware of what remainder means for such cases. Everyone knows that dividing a number by -1 or 1 gives a 0 remainder. To the contrary, no one expects a%b to raise SIFPE when b != 0. On the contrary, since the beginning of time SIGFPE has been generated on GCC/x86/linux under these conditions. This is wildly known. Just because you just found out about it does not mean that 'no one' expects it. OK: so it is my fault. But even if it is so wildly known, I think the GCC documentation should still mention it, for the sake of the few morons like me that are unsuspecting. From http://en.wikipedia.org/wiki/SIGFPE A common oversight is to consider division by zero the only source of SIGFPE conditions. On some architectures (IA-32 included), integer division of INT_MIN, the smallest representable negative integer value, by -1 triggers the signal because the quotient, a positive number, is not representable. Hmmm, it says nothing about the remainder. Can some Google guru suggest how to prove or disprove the claim that what we are talking about is wildly known? -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:[EMAIL PROTECTED]
Re: Miscompilation of remainder expressions
Roberto Bagnara wrote: You are right: I am not familiar with DO-178B certification. Fair enough, but it means you should never use avionics code as an example in such discussions. No life has ever been lost due to a software bug in the realm of commercial aviation, and that was not achieved by trusting compilers to be bug free. Yes, it's a bug, is it a serious bug, no? Will real software be affected? no. Indeed I find any program that actually does this remainder operation in practice to be highly suspect. But I am not wrong if I say that a bug is a bug and must be fixed. must be fixed never means more than may be fixed if someone either gets enthusiastic enough to do it themselves, or is paid to fix it. Of course serious bugs usually fall into one of these categories in a reasonable time period.
Re: Miscompilation of remainder expressions
Roberto Bagnara wrote: Hmmm, it says nothing about the remainder. Can some Google guru suggest how to prove or disprove the claim that what we are talking about is wildly known? The point really is not how widely/wildly known the issue is. Really the thing we consider on gcc@ is: What is the 'best' thing for GCC and the GCC developers to do. I don't claim to speak for others, but until now this issue has not seemed all that pressing. And it still doesn't. David Daney
Re: Miscompilation of remainder expressions
On Tue, Jan 16, 2007 at 11:05:20AM -0800, David Daney wrote: Roberto Bagnara wrote: Hmmm, it says nothing about the remainder. Can some Google guru suggest how to prove or disprove the claim that what we are talking about is wildly known? The point really is not how widely/wildly known the issue is. Really the thing we consider on gcc@ is: What is the 'best' thing for GCC and the GCC developers to do. I don't claim to speak for others, but until now this issue has not seemed all that pressing. And it still doesn't. We can talk about this forever, but how about moving to a resolution? First off, is there a PR for this bug? Second, if it were to be fixed, what is the fix that minimizes the extra overhead? I suspect that many users would not want the fix if it slows down integer modulo significantly, or if they are already coding defensively because they know about the issue, but that some users *would* want it. The final solution would be a fix that is enabled by some flag. We can then have another argument as to the name of the flag and when it is enabled. I suggest that those who think this is a severe problem are the ones who are highly motivated to work on a solution. An efficient solution could be tricky: you don't want to disrupt pipelines, or interfere with optimizations that rely on recognizing that there is a modulo. I don't think anyone would object if there were a non-default option to ensure that anything % -1 is zero and does not trap, especially if the overhead were small. So Roberto, how about it? Would you like to work on that? Any other volunteers? You can't expect those who don't see it as a serious problem to volunteer, not with so many other open bugs.
Re: Miscompilation of remainder expressions
Andrew Haley wrote: Roberto Bagnara writes: Robert Dewar wrote: Yes, it's a bug, is it a serious bug, no? Will real software be affected? no. Indeed I find any program that actually does this remainder operation in practice to be highly suspect. But I am not wrong if I say that a bug is a bug and must be fixed. I was answering to a message saying (basically) we won't fix it since there is a performance penalty to be paid. It wasn't saying that. My opinion at the time was (and still is) that it probably isn't a bug, and there is a performance penalty to be paid for changing the behaviour, so we shouldn't fix it. If I had believed that it surely was a bug, then I wouldn't have made the performance argument: correctness first, then performance. Yes, of course, I think we all agree with that. Roberto was just misreading here Andrew.
Re: Miscompilation of remainder expressions
On 2007-01-16 12:31:00 -0500, Robert Dewar wrote: Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? Seems ultra-non-serious to me, hard to believe this case appears in real code, despite surprising claim by Roberto. What makes you think so? One never knows. We (the MPFR developers) found several compiler bugs concerning particular cases like that, which occurred in MPFR. One of them (in some gcc version) was 0 + LONG_MIN, which was different from LONG_MIN. Is 0 + LONG_MIN so different from INT_MIN % -1, for instance? -- Vincent Lefèvre [EMAIL PROTECTED] - Web: http://www.vinc17.org/ 100% accessible validated (X)HTML - Blog: http://www.vinc17.org/blog/ Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Re: Miscompilation of remainder expressions
Vincent Lefevre wrote: On 2007-01-16 12:31:00 -0500, Robert Dewar wrote: Roberto Bagnara wrote: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? Seems ultra-non-serious to me, hard to believe this case appears in real code, despite surprising claim by Roberto. What makes you think so? One never knows. We (the MPFR developers) found several compiler bugs concerning particular cases like that, which occurred in MPFR. One of them (in some gcc version) was 0 + LONG_MIN, which was different from LONG_MIN. Is 0 + LONG_MIN so different from INT_MIN % -1, for instance? The difference is that your program didn't get killed by SIGFPE, it just gave incorrect results. David Daney
Re: Miscompilation of remainder expressions
Joe Buck [EMAIL PROTECTED] writes: I suggest that those who think this is a severe problem are the ones who are highly motivated to work on a solution. An efficient solution could be tricky: you don't want to disrupt pipelines, or interfere with optimizations that rely on recognizing that there is a modulo. I suspect that the best fix, in the sense of generating the best code, would be to do this at the tree level. That will give loop and VRP optimizations the best chance to eliminate the test for -1. Doing it during gimplification would be easy, if perhaps rather ugly. If there are indeed several processors with this oddity, then it would even make a certain degree of sense as a target-independent option. If we think it's too ugly to do it in the target independent code, then it's trivial to do it by changing the divmodsi4 define_expand in config/i386/i386.md. Ian
Re: Miscompilation of remainder expressions
Ian Lance Taylor writes: Joe Buck [EMAIL PROTECTED] writes: I suggest that those who think this is a severe problem are the ones who are highly motivated to work on a solution. An efficient solution could be tricky: you don't want to disrupt pipelines, or interfere with optimizations that rely on recognizing that there is a modulo. I suspect that the best fix, in the sense of generating the best code, would be to do this at the tree level. That will give loop and VRP optimizations the best chance to eliminate the test for -1. Doing it during gimplification would be easy, if perhaps rather ugly. If there are indeed several processors with this oddity, then it would even make a certain degree of sense as a target-independent option. x86, x86-64, S/390, as far as I'm aware. Andrew.
Re: Miscompilation of remainder expressions
On 2007-01-16 15:50:09 +, Andrew Haley wrote: This is a disgreement about interpretation of the langauge in the standard, which is: The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined. When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.87) If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a. If the quotient a/b is *not* representable, is the behaviour of % well-defined or not? It doesn't say. The C standard already says the result of the % operator is the remainder. Then, If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a. is just redundant information. -- Vincent Lefèvre [EMAIL PROTECTED] - Web: http://www.vinc17.org/ 100% accessible validated (X)HTML - Blog: http://www.vinc17.org/blog/ Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Re: Miscompilation of remainder expressions
Andrew Haley wrote: Ian Lance Taylor writes: Joe Buck [EMAIL PROTECTED] writes: I suggest that those who think this is a severe problem are the ones who are highly motivated to work on a solution. An efficient solution could be tricky: you don't want to disrupt pipelines, or interfere with optimizations that rely on recognizing that there is a modulo. I suspect that the best fix, in the sense of generating the best code, would be to do this at the tree level. That will give loop and VRP optimizations the best chance to eliminate the test for -1. Doing it during gimplification would be easy, if perhaps rather ugly. If there are indeed several processors with this oddity, then it would even make a certain degree of sense as a target-independent option. x86, x86-64, S/390, as far as I'm aware. MIPS does *not* seem to suffer from this 'defect', so a target independent solution that caused MIPS to generate worse code would be bad. David Daney
Re: Miscompilation of remainder expressions
David Daney [EMAIL PROTECTED] writes: Andrew Haley wrote: Ian Lance Taylor writes: Joe Buck [EMAIL PROTECTED] writes: I suggest that those who think this is a severe problem are the ones who are highly motivated to work on a solution. An efficient solution could be tricky: you don't want to disrupt pipelines, or interfere with optimizations that rely on recognizing that there is a modulo. I suspect that the best fix, in the sense of generating the best code, would be to do this at the tree level. That will give loop and VRP optimizations the best chance to eliminate the test for -1. Doing it during gimplification would be easy, if perhaps rather ugly. If there are indeed several processors with this oddity, then it would even make a certain degree of sense as a target-independent option. x86, x86-64, S/390, as far as I'm aware. MIPS does *not* seem to suffer from this 'defect', so a target independent solution that caused MIPS to generate worse code would be bad. To be clear, in my opinion, this should always be selected by an option, it should never be default behaviour for any target. Ian
Re: Miscompilation of remainder expressions
On Tue, Jan 16, 2007 at 01:31:06PM -0800, David Daney wrote: Andrew Haley wrote: Ian Lance Taylor writes: I suspect that the best fix, in the sense of generating the best code, would be to do this at the tree level. That will give loop and VRP optimizations the best chance to eliminate the test for -1. Doing it during gimplification would be easy, if perhaps rather ugly. If there are indeed several processors with this oddity, then it would even make a certain degree of sense as a target-independent option. x86, x86-64, S/390, as far as I'm aware. MIPS does *not* seem to suffer from this 'defect', so a target independent solution that caused MIPS to generate worse code would be bad. Since at least three targets are affected, it would seem that doing it at the tree level is the right thing. The tree level code could consult a flag saying whether to jump through hoops to avoid faulting for i % -1. This flag would never be set for the MIPS, and would be set for x86, x86-64, or S/390 only if the user asks for it. If the flag is present, the operation would be treat i % j as either (j == -1 ? 0 : i rem j) or (i % abs(j)) or whatever other expression might yield the best code.
Re: Miscompilation of remainder expressions
Joe Buck [EMAIL PROTECTED] writes: | On Tue, Jan 16, 2007 at 11:05:20AM -0800, David Daney wrote: | Roberto Bagnara wrote: | | Hmmm, it says nothing about the remainder. Can some Google guru | suggest how to prove or disprove the claim that what we are | talking about is wildly known? | | | The point really is not how widely/wildly known the issue is. Really | the thing we consider on gcc@ is: What is the 'best' thing for GCC and | the GCC developers to do. | | I don't claim to speak for others, but until now this issue has not | seemed all that pressing. And it still doesn't. | | We can talk about this forever, but how about moving to a resolution? seconded. | First off, is there a PR for this bug? I believe this is target/30484. Ian, do you believe something along the line of # I mean, could not we generate the following for %: # # rem a b := #if abs(b) == 1 # return 0 #return machine-instruction a b # # On x86 processors that have conditional moves, why not do the equivalent # of # # neg_b = -b; # cmov(last result is negative,neg_b,b) # __machine_rem(a,b) # # Then there's no disruption of the pipeline. is workable for the affected targets? -- Gaby
Re: Miscompilation of remainder expressions
Gabriel Dos Reis [EMAIL PROTECTED] writes: Ian, do you believe something along the line of # I mean, could not we generate the following for %: # # rem a b := #if abs(b) == 1 # return 0 #return machine-instruction a b # # On x86 processors that have conditional moves, why not do the equivalent # of # # neg_b = -b; # cmov(last result is negative,neg_b,b) # __machine_rem(a,b) # # Then there's no disruption of the pipeline. is workable for the affected targets? Sure, I think the only real issue is where the code should be inserted. Ian
Re: Miscompilation of remainder expressions
On 2007-01-16 13:08:18 -0800, David Daney wrote: The difference is that your program didn't get killed by SIGFPE, it just gave incorrect results. An incorrect result is worse, but being killed by SIGFPE is still very bad. But I was mainly answering the claim hard to believe this case appears in real code. IMHO, INT_MIN % -1 can appear just as 0 + LONG_MIN can appear, just as LONG_MIN / 1 can appear. -- Vincent Lefèvre [EMAIL PROTECTED] - Web: http://www.vinc17.org/ 100% accessible validated (X)HTML - Blog: http://www.vinc17.org/blog/ Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Re: Miscompilation of remainder expressions
On 2007-01-16 21:27:42 +, Andrew Haley wrote: Ian Lance Taylor writes: I suspect that the best fix, in the sense of generating the best code, would be to do this at the tree level. That will give loop and VRP optimizations the best chance to eliminate the test for -1. Doing it during gimplification would be easy, if perhaps rather ugly. If there are indeed several processors with this oddity, then it would even make a certain degree of sense as a target-independent option. x86, x86-64, S/390, as far as I'm aware. and PowerPC G4 and G5, where I don't get a crash, but an incorrect result (as said on PR#30484). -- Vincent Lefèvre [EMAIL PROTECTED] - Web: http://www.vinc17.org/ 100% accessible validated (X)HTML - Blog: http://www.vinc17.org/blog/ Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Re: Miscompilation of remainder expressions
Vincent Lefevre [EMAIL PROTECTED] writes: | On 2007-01-16 13:41:16 -0800, Ian Lance Taylor wrote: | To be clear, in my opinion, this should always be selected by an | option, it should never be default behaviour for any target. | | I disagree. One should get correct results by default. Once we have an implemented solution, we can quibble over whether it should be on by default or not. That debate will be supported by sample of hard data. Once we have an implementation. -- Gaby
Re: Miscompilation of remainder expressions
Vincent Lefevre [EMAIL PROTECTED] writes: | On 2007-01-16 13:41:16 -0800, Ian Lance Taylor wrote: | To be clear, in my opinion, this should always be selected by an | option, it should never be default behaviour for any target. | | I disagree. One should get correct results by default. Once we have an implemented solution, we can quibble over whether it should be on by default or not. That debate will be supported by sample of hard data. Once we have an implementation. I wonder why the call to div/ldiv/lldiv says the behavior is undefined while % is defined, that seems wrong. The specific wording from the standard is If either part of the result cannot be represented, the behavior is undefined. So why is % different from those functions? -- Pinski
Re: Miscompilation of remainder expressions
Andrew Pinski [EMAIL PROTECTED] writes: | | Vincent Lefevre [EMAIL PROTECTED] writes: | | | On 2007-01-16 13:41:16 -0800, Ian Lance Taylor wrote: | | To be clear, in my opinion, this should always be selected by an | | option, it should never be default behaviour for any target. | | | | I disagree. One should get correct results by default. | | Once we have an implemented solution, we can quibble over whether it | should be on by default or not. That debate will be supported by | sample of hard data. Once we have an implementation. | | I wonder why the call to div/ldiv/lldiv says the behavior is undefined while | % is defined, that seems wrong. That is because div also has to compute the division too (which is undefined) % does not. | The specific wording from the standard is If either part of the result | cannot be represented, the behavior is undefined. So why is % different | from those functions? because % is not div, syntactically and semantically. -- Gaby
Re: Miscompilation of remainder expressions
On Tue, Jan 16, 2007 at 06:55:45PM -0500, Andrew Pinski wrote: Vincent Lefevre [EMAIL PROTECTED] writes: | On 2007-01-16 13:41:16 -0800, Ian Lance Taylor wrote: | To be clear, in my opinion, this should always be selected by an | option, it should never be default behaviour for any target. | | I disagree. One should get correct results by default. Once we have an implemented solution, we can quibble over whether it should be on by default or not. That debate will be supported by sample of hard data. Once we have an implementation. I wonder why the call to div/ldiv/lldiv says the behavior is undefined while % is defined, that seems wrong. The specific wording from the standard is If either part of the result cannot be represented, the behavior is undefined. So why is % different from those functions? Let's keep the two issues separate. Clearly some users want a solution; if people are willing to contribute a solution we should accept it. There appears to be controversy over the language requirement. If a solution is contributed, then the default setting of the switch (whether on or off by default) is a separate matter. We might even consider doing a survey: what do the users want? Benchmark wars might also have an impact. Does icc generate a SIGFPE? What's the effect on benchmarks? Some users might want to pay the price to be sure the trap is avoided, others might not.
Re: Miscompilation of remainder expressions
Hi Roberto, Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? If I understand correctly your problem, I was also battling with it a few days ago, and found 5.6/4 rather obscure, i.e., I'm not sure to understand what we can reasonably expect from the remainder operator when one or both operands are negative... Then, while fixing libstdc++/30416 I decided to be super-safe, that is only compute remainders of nonnegative operands... I would like to understand the issue better, however... Paolo.
Re: Miscompilation of remainder expressions
Roberto Bagnara writes: Reading the thread Autoconf manual's coverage of signed integer overflow portability I was horrified to discover about GCC's miscompilation of the remainder expression that causes INT_MIN % -1 to cause a SIGFPE on CPUs of the i386 family. Are there plans to fix this bug (which, to me, looks quite serious)? No, there aren't. It would make more sense for you to wrap % in some code that checks for this, rather than for us to slow down every division for this one special case. Andrew.
Re: Miscompilation of remainder expressions
Paolo Carlini writes: I would like to understand the issue better, however... What more is there to understand? It's an integer overflow. The processor generates a trap on integer overflows during division operations. Andrew.
