Hi,
during some debugging I noticed that GPC generates very hairy code for the `mod' operator with signed arguments. A closer look revealed that the code contains a lot of branching on conditions which can be determined on compile time, and most surprisingly, the value of X mod Y is recomputed _twice_, if X is negative. (I've attached a commented assembler dump.)
This may be partially a back-end problem (CSE?), but I feel there's something wrong in the relevant code in gpc-common.c (build_pascal_binary_op) as well. `exp1 mod exp2' gets translated into something like
exp2 <= 0 ? error : exp1 >= 0 ? exp1 mod exp2 : ((-exp1) mod exp2) == 0 ? 0 : exp2 - (-exp1) mod exp2
This arranges that both arguments supplied to the "internal mod" are non-negative, but this information is not passed on -- the arguments are still declared as signed types, which apparently makes the back-end to produce the mess it does. I've done a little test: the following replacement for `mod', which differs from the built-in one essentially just by the type-casts to `Cardinal',
inline operator xmod (X, Y: Integer) = Z: Integer; begin if Y <= 0 then RuntimeError (714); if X >= 0 then Z := Cardinal (X) mod Y else begin Z := Cardinal (-X) mod Y; if Z <> 0 then Z := Y - Z end end;
indeed generates a better code, it measures about 15% faster for positive X and more than twice faster for negative X. YMMV. If this is possible in user code, it should work in the compiler internals as well :)
The result type of the whole `mod' expression looks dubious too. IIUIC, `exp1 mod exp2' inherits the type of exp1. Now, the result of `mod' is guaranteed to be nonnegative and to fit in the type of exp2 (or more precisely, it is in 0 .. High (type of (exp2)) - 1), whereas it needn't have anything to do with the type of exp1: consider
var X, Z: Integer; Y: LongInt;
begin X := -8; Y := High (LongInt); Z := X mod Y { -> overflow } end
Or am I missing something?
Emil
(BTW, where is fjf434c.pas?)
Emil Jerabek wrote:
during some debugging I noticed that GPC generates very hairy code for the `mod' operator with signed arguments. A closer look revealed that the code contains a lot of branching on conditions which can be determined on compile time, and most surprisingly, the value of X mod Y is recomputed _twice_, if X is negative. (I've attached a commented assembler dump.)
I might be interesting to note that not all Pascal compilers follow the ISO 7185 Pascal standard for the mod operator. The standard states:
"Evaluation of a term of the form x mod y is an error if y is less than or equal to zero; otherwise there is an integer k such that x mod y satisfies the following relation:
0 <= x mod y = x - k * y < y."
But on page 6-5 of the Delphi 3 Object Pascal Language Guide, we read:
"The mod operator returns the remainder obtained by dividing its two operands; that is,
I mod J = I - (I div J) * J
The sign of the result of mod is the same as the sign of I. A runtime error occurs if J is zero."
That is, in Delphi (1) J < 0 is allowed and (2) I mod J < 0 if I < 0.
A nasty trap if you are porting code from Delphi (or some other Pascal compilers) !
Adriaan van Os
Adriaan van Os wrote:
... snip ...
I might be interesting to note that not all Pascal compilers follow the ISO 7185 Pascal standard for the mod operator. The standard states:
"Evaluation of a term of the form x mod y is an error if y is less than or equal to zero; otherwise there is an integer k such that x mod y satisfies the following relation:
0 <= x mod y = x - k * y < y."
But on page 6-5 of the Delphi 3 Object Pascal Language Guide, we read:
"The mod operator returns the remainder obtained by dividing its two operands; that is,
I mod J = I - (I div J) * J
The sign of the result of mod is the same as the sign of I. A runtime error occurs if J is zero."
That is, in Delphi (1) J < 0 is allowed and (2) I mod J < 0 if I < 0.
A nasty trap if you are porting code from Delphi (or some other Pascal compilers) !
This is the result of Borland ignoring the standard. There is no excuse, because the standard was available long before the first Turbo Pascal. The drafts were published in Pascal News in the mid '70s. It is one of the reasons many will not consider Delphi/Borland/Turbo to be Pascal.
The purpose of a standard is to ensure that programs and programmers can count on the standardized behavior.
Emil Jerabek wrote:
during some debugging I noticed that GPC generates very hairy code for the `mod' operator with signed arguments. A closer look revealed that the code contains a lot of branching on conditions which can be determined on compile time, and most surprisingly, the value of X mod Y is recomputed _twice_, if X is negative. (I've attached a commented assembler dump.)
This may be partially a back-end problem (CSE?), but I feel there's something wrong in the relevant code in gpc-common.c (build_pascal_binary_op) as well.
I don't know if CSE is suppose to find this case, but at least is better to do it in the front-end indeed. (All it takes is a `save_expr' which I'm putting in now.)
`exp1 mod exp2' gets translated into something like
exp2 <= 0 ? error : exp1 >= 0 ? exp1 mod exp2 : ((-exp1) mod exp2) == 0 ? 0 : exp2 - (-exp1) mod exp2
This arranges that both arguments supplied to the "internal mod" are non-negative, but this information is not passed on -- the arguments are still declared as signed types, which apparently makes the back-end to produce the mess it does.
Right. I've changed it to unsigned types now, and it simplifies the generated code.
The result type of the whole `mod' expression looks dubious too. IIUIC, `exp1 mod exp2' inherits the type of exp1. Now, the result of `mod' is guaranteed to be nonnegative and to fit in the type of exp2 (or more precisely, it is in 0 .. High (type of (exp2)) - 1), whereas it needn't have anything to do with the type of exp1: consider
var X, Z: Integer; Y: LongInt;
begin X := -8; Y := High (LongInt); Z := X mod Y { -> overflow } end
True. (Though, of course, GPC currently doesn't check for overflows generally, so it won't detect this one either, but in other situations, using the other type should lead to correct results.)
(BTW, where is fjf434c.pas?)
Oh, I had put it aside to work on another problem it caused on some platforms (but didn't actually get around to it). Now I'm putting it back to see if these changes have any effect on that problem. (According to first quick tests, they seem to. :-)
CBFalconer wrote:
Adriaan van Os wrote:
I might be interesting to note that not all Pascal compilers follow the ISO 7185 Pascal standard for the mod operator. The standard states:
[...]
This is the result of Borland ignoring the standard. There is no excuse, because the standard was available long before the first Turbo Pascal. The drafts were published in Pascal News in the mid '70s. It is one of the reasons many will not consider Delphi/Borland/Turbo to be Pascal.
That's another reason why GPC's `mod' implementation is so hairy (because it emulates Borland's in `--borland-pascal') ...
Frank
Frank Heckenbach wrote:
CBFalconer wrote:
Adriaan van Os wrote:
I might be interesting to note that not all Pascal compilers follow the ISO 7185 Pascal standard for the mod operator. The standard states:
[...]
This is the result of Borland ignoring the standard. There is no excuse, because the standard was available long before the first Turbo Pascal. The drafts were published in Pascal News in the mid '70s. It is one of the reasons many will not consider Delphi/Borland/Turbo to be Pascal.
That's another reason why GPC's `mod' implementation is so hairy (because it emulates Borland's in `--borland-pascal') ...
It looks like there is still a problem in the compiler for constant expressions using the mod operator.
program modulo( Output); var i, j, m : integer; begin i := -10; j := 100; m := i mod j; Writeln( ' m = ', i: 3, ' mod ', j: 3, ' = ', m: 3); Writeln( '-10 mod 100 = ', -10 mod 100 :3); end.
[P18:~] adriaan% gp --standard-pascal modulo.pas [P18:~] adriaan% ./modulo m = -10 mod 100 = 90 -10 mod 100 = -10
[P18:~] adriaan% gpc -v Reading specs from /Developer/Pascal/gpc346u4/lib/gcc/i386-apple-darwin9/3.4.6/specs Configured with: ../gcc-3.4.6/configure --enable-languages=pascal,c --enable-threads=posix --disable-nls --target=i386-apple-darwin9 --host=i386-apple-darwin9 --build=i386-apple-darwin9 --prefix=/Developer/Pascal/gpc346u4 --with-arch=pentium-m --with-tune=prescott Thread model: posix gpc version 20070904, based on gcc-3.4.6
Regards,
Adriaan van Os
Le 22/10/2010 13:57, Adriaan van Os a écrit :
Frank Heckenbach wrote:
CBFalconer wrote:
Adriaan van Os wrote:
I might be interesting to note that not all Pascal compilers follow the ISO 7185 Pascal standard for the mod operator. The standard states:
[...]
This is the result of Borland ignoring the standard. There is no excuse, because the standard was available long before the first Turbo Pascal. The drafts were published in Pascal News in the mid '70s. It is one of the reasons many will not consider Delphi/Borland/Turbo to be Pascal.
That's another reason why GPC's `mod' implementation is so hairy (because it emulates Borland's in `--borland-pascal') ...
It looks like there is still a problem in the compiler for constant expressions using the mod operator.
program modulo( Output); var i, j, m : integer; begin i := -10; j := 100; m := i mod j; Writeln( ' m = ', i: 3, ' mod ', j: 3, ' = ', m: 3); Writeln( '-10 mod 100 = ', -10 mod 100 :3); end.
[P18:~] adriaan% gp --standard-pascal modulo.pas [P18:~] adriaan% ./modulo m = -10 mod 100 = 90 -10 mod 100 = -10
No, this is a problem of precedence of operators. mod, being a "kind of" division operator, has precedence on -, an additive operator, in standard pascal. simply replace the penultimate line by
Writeln( '(-10) mod 100 = ', (-10) mod 100 :3);
and the result is correct.
Maurice
Hello.
I disagree somewhat. In this case the '-' is a unary operator, not an additive operator. A unary operator should evaluate before any other operator, at least in this case. The -10 should evaluate immediately as the simple value it is. Then the mod operator is evaluated. So you should not have to put any parenthesis around -10 to obtain the correct result.
Regards Lennart Thelander
On 10-10-22 19.51, "Maurice Lombardi" Maurice.Lombardi@ujf-grenoble.fr wrote:
Le 22/10/2010 13:57, Adriaan van Os a écrit :
Frank Heckenbach wrote:
CBFalconer wrote:
Adriaan van Os wrote:
I might be interesting to note that not all Pascal compilers follow the ISO 7185 Pascal standard for the mod operator. The standard states:
[...]
This is the result of Borland ignoring the standard. There is no excuse, because the standard was available long before the first Turbo Pascal. The drafts were published in Pascal News in the mid '70s. It is one of the reasons many will not consider Delphi/Borland/Turbo to be Pascal.
That's another reason why GPC's `mod' implementation is so hairy (because it emulates Borland's in `--borland-pascal') ...
It looks like there is still a problem in the compiler for constant expressions using the mod operator.
program modulo( Output); var i, j, m : integer; begin i := -10; j := 100; m := i mod j; Writeln( ' m = ', i: 3, ' mod ', j: 3, ' = ', m: 3); Writeln( '-10 mod 100 = ', -10 mod 100 :3); end.
[P18:~] adriaan% gp --standard-pascal modulo.pas [P18:~] adriaan% ./modulo m = -10 mod 100 = 90 -10 mod 100 = -10
No, this is a problem of precedence of operators. mod, being a "kind of" division operator, has precedence on -, an additive operator, in standard pascal. simply replace the penultimate line by
Writeln( '(-10) mod 100 = ', (-10) mod 100 :3);
and the result is correct.
Maurice
Lennart Thelander wrote:
I disagree somewhat. In this case the '-' is a unary operator, not an additive operator. A unary operator should evaluate before any other operator, at least in this case. The -10 should evaluate immediately as the simple value it is. Then the mod operator is evaluated. So you should not have to put any parenthesis around -10 to obtain the correct result.
Well, that's your personal opinion which is shared by C and related languages, including Borland Pascal.
But Adriaan explicitly asked about standard Pascal which follows the mathematical convention (see ISO 7185, 6.7.1) where there's no special priority of unary operators, e.g. in mathematics -2^2 equals -4, not 4.
Frank
Frank Heckenbach wrote:
Lennart Thelander wrote:
I disagree somewhat. In this case the '-' is a unary operator, not an additive operator. A unary operator should evaluate before any other operator, at least in this case. The -10 should evaluate immediately as the simple value it is. Then the mod operator is evaluated. So you should not have to put any parenthesis around -10 to obtain the correct result.
Well, that's your personal opinion which is shared by C and related languages, including Borland Pascal.
But Adriaan explicitly asked about standard Pascal which follows the mathematical convention (see ISO 7185, 6.7.1) where there's no special priority of unary operators, e.g. in mathematics -2^2 equals -4, not 4.
You are right. But I wonder how many Pascal programmers are wrong here.... It is very tricky. What about a compiler warning ?
Another example:
program unary; begin writeln( -2 shr 1) end.
[P18:~] adriaan% gp --borland-pascal unary.pas [P18:~] adriaan% ./unary -1
[P18:~] adriaan% fpc -Mtp unary.pas Free Pascal Compiler version 2.5.1 [2010/10/19] for i386 Copyright (c) 1993-2010 by Florian Klaempfl Target OS: Darwin for i386 Compiling unary.pas Assembling unary Linking unary 6 lines compiled, 0.1 sec [P18:~] adriaan% ./unary 9223372036854775807
Regards,
Adriaan van Os
Hi,
On 10/25/10, Adriaan van Os gpc@microbizz.nl wrote:
But Adriaan explicitly asked about standard Pascal
You are right. But I wonder how many Pascal programmers are wrong here.... It is very tricky. What about a compiler warning ?
C:\BLAH [ GPC ] >gpc --classic-pascal -s -O adrian.pas -o adrian.exe -Wall -Wextra adrian.pas: In main program: adrian.pas:3: error: syntax error before `shr'
Consider that your warning. ISO doesn't support "shr". ;-) In all seriousness, I would doubt the FPC answer would ever be considered correct in this context (heh, 9 gazillion from "-2 shr 1"? highly unlikely). I'm sure they'll be glad for a test case / bug report.
{ gp -s -O unary } { GPC 20070904, GCC 3.4.4 + DJGPP } { d:\fpc242\bin\go32v2\fpc -XXs -Os -al unary } program unary; begin writeln( -1 ); {-1} writeln( 2 shr 1 ); { 1} writeln((-2)shr 1 ); {GPC: -1 FPC: 9223372036854775807} writeln(-(2 shr 1)); {-1} writeln( -2 shr 1 ); {GPC: -1 FPC: 9223372036854775807} writeln( -2 div 2 ); {-1} end.
I know this was meant to be a trivial case, and I'm probably stating the extremely obvious, but ... just use Pascal's "div", that's what it's for. Using BP's "shr" here (presumably same as x86's "sar" instruction, which is what ANSI C ">>" uses, right??) is probably a misguided case of premature optimization. Granted, as long as it works for you ... but it's clearly not totally extremely obvious nor totally portable. However, I'm no mathematician and hadn't truly stumbled upon nor understood this previously myself.
On 25 Oct 2010, at 10:43, Rugxulo wrote:
In all seriousness, I would doubt the FPC answer would ever be considered correct in this context (heh, 9 gazillion from "-2 shr 1"? highly unlikely). I'm sure they'll be glad for a test case / bug report.
Yes, that's definitely a compiler bug. Kylix also returns the same results as GPC.
Jonas
On 25 Oct 2010, at 11:10, Jonas Maebe wrote:
On 25 Oct 2010, at 10:43, Rugxulo wrote:
In all seriousness, I would doubt the FPC answer would ever be considered correct in this context (heh, 9 gazillion from "-2 shr 1"? highly unlikely). I'm sure they'll be glad for a test case / bug report.
Yes, that's definitely a compiler bug. Kylix also returns the same results as GPC.
Actually, it's rather strange: "shr" is a logical shift right (both in FPC and Borland Pascal, and I assume also in GPC) as opposed to an arithmetic shift right. So I guess that Kylix and GPC also perform a 64 bit logical shift right on the value, but then unlike FPC truncate the result back to 32 bits. Otherwise I'm not sure where the "-1" comes from when doing "(-2)shr 1".
Jonas
On 25 Oct 2010 at 11:21, Jonas Maebe wrote:
On 25 Oct 2010, at 11:10, Jonas Maebe wrote:
On 25 Oct 2010, at 10:43, Rugxulo wrote:
In all seriousness, I would doubt the FPC answer would ever be considered correct in this context (heh, 9 gazillion from "-2 shr 1"? highly unlikely). I'm sure they'll be glad for a test case / bug report.
Yes, that's definitely a compiler bug. Kylix also returns the same results as GPC.
Actually, it's rather strange: "shr" is a logical shift right (both in FPC and Borland Pascal, and I assume also in GPC) as opposed to an arithmetic shift right. So I guess that Kylix and GPC also perform a 64 bit logical shift right on the value, but then unlike FPC truncate the result back to 32 bits. Otherwise I'm not sure where the "-1" comes from when doing "(-2)shr 1".
I don't much understand what all this is about, but for what it's worth, here are my results with Delphi (3, 4, and 7) and BP 7.0.
program unary; begin writeln( -1 ); { -1 } writeln( 2 shr 1 ); { 1 } writeln((-2)shr 1 ); { -1; BP7=2147483647 } writeln(-(2 shr 1)); { -1 } writeln( -2 shr 1 ); { -1; BP7=2147483647 } writeln( -2 div 2 ); { -1 } end.
Best regards, The Chief -------- Prof. Abimbola A. Olowofoyeku (The African Chief) web: http://www.greatchief.plus.com/
Le 25/10/2010 12:13, Prof A Olowofoyeku (The African Chief) a écrit :
On 25 Oct 2010 at 11:21, Jonas Maebe wrote:
Actually, it's rather strange: "shr" is a logical shift right (both in FPC and Borland Pascal, and I assume also in GPC) as opposed to an arithmetic shift right. So I guess that Kylix and GPC also perform a 64 bit logical shift right on the value, but then unlike FPC truncate the result back to 32 bits. Otherwise I'm not sure where the "-1" comes from when doing "(-2)shr 1".
I don't much understand what all this is about, but for what it's worth, here are my results with Delphi (3, 4, and 7) and BP 7.0.
program unary; begin writeln( -1 ); { -1 } writeln( 2 shr 1 ); { 1 } writeln((-2)shr 1 ); { -1; BP7=2147483647 } writeln(-(2 shr 1)); { -1 } writeln( -2 shr 1 ); { -1; BP7=2147483647 } writeln( -2 div 2 ); { -1 } end.
This means that GPC does an arithmetical right shift (i.e. propagating the 1 (or 0) in the leftmost (highest weight) position), while BP does a logical right shift. It seems more sound to use an arithmetical shift for integer and a logical shift for cardinal. Standard does not help since it does not define the shift operators. C (and BP?) are too mind confused to enforce this point.
Maurice
Maurice Lombardi wrote:
Le 25/10/2010 12:13, Prof A Olowofoyeku (The African Chief) a écrit :
On 25 Oct 2010 at 11:21, Jonas Maebe wrote:
Actually, it's rather strange: "shr" is a logical shift right (both in FPC and Borland Pascal, and I assume also in GPC) as opposed to an arithmetic shift right. So I guess that Kylix and GPC also perform a 64 bit logical shift right on the value, but then unlike FPC truncate the result back to 32 bits. Otherwise I'm not sure where the "-1" comes from when doing "(-2)shr 1".
I don't much understand what all this is about, but for what it's worth, here are my results with Delphi (3, 4, and 7) and BP 7.0.
program unary; begin writeln( -1 ); { -1 } writeln( 2 shr 1 ); { 1 } writeln((-2)shr 1 ); { -1; BP7=2147483647 } writeln(-(2 shr 1)); { -1 } writeln( -2 shr 1 ); { -1; BP7=2147483647 } writeln( -2 div 2 ); { -1 } end.
This means that GPC does an arithmetical right shift (i.e. propagating the 1 (or 0) in the leftmost (highest weight) position), while BP does a logical right shift. It seems more sound to use an arithmetical shift for integer and a logical shift for cardinal. Standard does not help since it does not define the shift operators. C (and BP?) are too mind confused to enforce this point.
Ah, that adds an interesting case, mentioned here http://en.wikipedia.org/wiki/Arithmetic_shift, namely the arithmetic shift right of -1.
program arithmeticshift; begin writeln( -(1 shr 1)); writeln( -1 shr 1); writeln( (-1) shr 1) end.
GPC prints 0 0 -1
FPC prints 0 9223372036854775807 9223372036854775807
Regards,
Adriaan van Os
On 25 Oct 2010 at 14:30, Adriaan van Os wrote:
[...]
Ah, that adds an interesting case, mentioned here http://en.wikipedia.org/wiki/Arithmetic_shift, namely the arithmetic shift right of -1.
program arithmeticshift; begin writeln( -(1 shr 1)); writeln( -1 shr 1); writeln( (-1) shr 1) end.
GPC prints 0 0 -1
FPC prints 0 9223372036854775807 9223372036854775807
Delphi (3, 4, 7) prints 0 -1 -1
BP7 prints 0 2147483647 2147483647
Best regards, The Chief -------- Prof. Abimbola A. Olowofoyeku (The African Chief) web: http://www.greatchief.plus.com/
Hi,
On 10/25/10, Maurice Lombardi Maurice.Lombardi@ujf-grenoble.fr wrote:
This means that GPC does an arithmetical right shift (i.e. propagating the 1 (or 0) in the leftmost (highest weight) position), while BP does a logical right shift.
Right, so GPC does it the same as C (no surprise, GCC-based).
It seems more sound to use an arithmetical shift for integer and a logical shift for cardinal.
Right, so shifting a signed number should keep the sign. (Though "cardinal" isn't standard Pascal, comes from Modula-2, and Wirth removed it for Oberon).
Tell me if this helps demonstrate anything:
--- snip ---
CR equ 13 LF equ 10
org 100h
mov eax,-2 ; = 0xFFFFFFFE shr eax,1 call hexdword ; EAX = 0x7FFFFFFF call newline
mov eax,-2 sar eax,1 call hexdword ; EAX = 0xFFFFFFFF call newline
int 20h ; exit
hexdword: mov ecx,8 ; 32/4 .begin: rol eax,4 push eax and al,0Fh cmp al,10 sbb al,69h das int 29h ; putchar(AL) pop eax loop .begin ret
newline: mov al,CR int 29h mov al,LF int 29h ret
-
Adriaan van Os -
CBFalconer -
Emil Jerabek -
Frank Heckenbach -
Frank Heckenbach -
Jonas Maebe -
Lennart Thelander -
Maurice Lombardi -
Prof A Olowofoyeku (The African Chief) -
Rugxulo