I pushed a branch containing "hopefully" standard compliant overflow checks. Its in arne/of. I had to change a few places outside of bignum.h in order to get it all working with inlines.
The switch from macro to inlines actually changed semantics, since the INT_TYPE_* macros were actually used both with int and unsigned int. Naturally, the inline functions fail to detect an overflow there, since INT_TYPE is 64 bit and calculations do not overflow.
Maybe someone can try to compile and run verify on something other than amd64 with gcc?
arne
Good work! Unfortunately I cannot compile the bignum.h macros with Clang since the expansion order seems different (looks like type2 is not expanded):
In file included from /Users/jonasw/hacks/Pike/git/pike79/src/modules/Gmp/mpz_glue.c:37: /Users/jonasw/hacks/Pike/git/pike79/src/bignum.h:179:1: error: expected ';' at end of declaration GEN_OF2(64, 128) ^ /Users/jonasw/hacks/Pike/git/pike79/src/bignum.h:175:25: note: expanded from macro 'GEN_OF2' #define GEN_OF2(s1, s2) _GEN_OF2(INT ## s1, INT ## s2, s1)\ ^ /Users/jonasw/hacks/Pike/git/pike79/src/bignum.h:49:20: note: expanded from macro '_GEN_OF2' unsigned type2 res; \ ^
Changing the GEN_OF2 definition to use PIKE_CONCAT() simply shifts the problem to resolving MIN_long (which I guess should say MIN_INT128) so the expansion troubles aren't trivial to fix.
Ah, this was rather a case where "unsigned __int128_t" wasn't a valid type. Commenting out the INT128 support gives a complete build with no unexpected warnings but math is still broken:
Pike v7.9 release 5 running Hilfe v3.5 (Incremental Pike Frontend)
-0x80000000;
(1) Result: 2147483648
Yes, I guess I was a little too optimistic about __int128_t. The corresponding unsigned is __uint128_t and the combination with unsigned does not work (even in gcc). So I guess I will have to drop that for now.
I tried the branch with clang 3.2. It compiles fine and bignums seem ok. Since that version supports __int128, I also tried the versions without 128 bit integers (GEN_OF1(64)) and those also seem ok.
Which clang version are you using?
arne
On Tue, 1 Jan 2013, Jonas Walld�n @ Pike developers forum wrote:
Ah, this was rather a case where "unsigned __int128_t" wasn't a valid type. Commenting out the INT128 support gives a complete build with no unexpected warnings but math is still broken:
Pike v7.9 release 5 running Hilfe v3.5 (Incremental Pike Frontend)
-0x80000000;
(1) Result: 2147483648
Bignums in general work (and they did before too), but there are edge cases that breaks:
Pike v7.9 release 5 running Hilfe v3.5 (Incremental Pike Frontend)
-0x7fffffff;
(1) Result: -2147483647
-0x7fffffff - 1;
(2) Result: 2147483648
-0x7fffffff - 2;
(3) Result: -2147483649
Does (2) above produce a negative result in your build? I'm using the clang from Xcode 4.5 which identifies itself like this:
$ clang --version Apple clang version 4.1 (tags/Apple/clang-421.11.66) (based on LLVM 3.1svn) Target: x86_64-apple-darwin12.2.0 Thread model: posix
My clang says
clang version 3.2 (tags/RELEASE_32/final) Target: x86_64-pc-linux-gnu Thread model: posix
The edge case works fine here. I compiled pike --without-machine-code, will try without, too.
On Tue, 1 Jan 2013, Jonas Walld�n @ Pike developers forum wrote:
Bignums in general work (and they did before too), but there are edge cases that breaks:
Pike v7.9 release 5 running Hilfe v3.5 (Incremental Pike Frontend)
-0x7fffffff;
(1) Result: -2147483647
-0x7fffffff - 1;
(2) Result: 2147483648
-0x7fffffff - 2;
(3) Result: -2147483649
Does (2) above produce a negative result in your build? I'm using the clang from Xcode 4.5 which identifies itself like this:
$ clang --version Apple clang version 4.1 (tags/Apple/clang-421.11.66) (based on LLVM 3.1svn) Target: x86_64-apple-darwin12.2.0 Thread model: posix
Compiling with machine code breaks it for me, too.
On Wed, 2 Jan 2013, Arne Goedeke wrote:
My clang says
clang version 3.2 (tags/RELEASE_32/final) Target: x86_64-pc-linux-gnu Thread model: posix
The edge case works fine here. I compiled pike --without-machine-code, will try without, too.
On Tue, 1 Jan 2013, Jonas Walld�n @ Pike developers forum wrote:
Bignums in general work (and they did before too), but there are edge cases that breaks:
Pike v7.9 release 5 running Hilfe v3.5 (Incremental Pike Frontend)
-0x7fffffff;
(1) Result: -2147483647
-0x7fffffff - 1;
(2) Result: 2147483648
-0x7fffffff - 2;
(3) Result: -2147483649
Does (2) above produce a negative result in your build? I'm using the clang from Xcode 4.5 which identifies itself like this:
$ clang --version Apple clang version 4.1 (tags/Apple/clang-421.11.66) (based on LLVM 3.1svn) Target: x86_64-apple-darwin12.2.0 Thread model: posix
I get some testsuite failures that I believe are new and looks related to the bignum changes. Overall it would be good if we could stabilize the testsuite to 0 failures. There are some type system issues that have been around for a long time.
Which branch? My fix for that was on Arne's branch. If that is stable I guess it's time to merge it into 7.9.
The 7.9 master branch.
/home/nilsson/pike/src/testsuite.in:84: Test 62 (shift 2) failed (expected compile warning). 1: mixed a() { '\3434523423423523423423423423';} 2:
/home/nilsson/pike/src/testsuite.in:85: Test 63 (shift 0) (CRNL) failed (expected compile warning). 1: mixed a() { "\3434523423423523423423423423";} 2:
/home/nilsson/pike/src/testsuite.in:86: Test 64 (shift 1) (CRNL) failed (expected compile warning). 1: mixed a() { "\d109827346981234561823743412654";} 2:
/home/nilsson/pike/src/testsuite.in:87: Test 65 (shift 2) (CRNL) failed (expected compile warning). 1: mixed a() { "\x109a27bc69e256c83deaa34c26b4";} 2:
/home/nilsson/pike/src/testsuite.in:103: Test 81 (shift 0) (CRNL) failed. 1: mixed a() { 2: // Suppress warnings. 3: class handler { 4: void compile_warning (string file, int line, string err) {}; 5: }; 6: return compile_string("string s = "\3434523423423523423423423423";", 7: "-", handler())()->s; 8: ; } 9: mixed b() { return "\37777777777"; } 10:
o->a(): "\u9c4e2713" o->b(): "\uffffffff" /home/nilsson/pike/src/testsuite.in:111: Test 82 (shift 1) (CRNL) failed. 1: mixed a() { 2: // Suppress warnings. 3: class handler { 4: void compile_warning (string file, int line, string err) {}; 5: }; 6: return compile_string("int i = '\3434523423423523423423423423';", 7: "-", handler())()->i; 8: ; } 9: mixed b() { return -1; } 10:
o->a(): -1672599789 o->b(): -1
I think it would be ok to merge it into 7.9. If noone sees any problems with it, I can go ahead and do that. I would squash a couple of commits and give them reasonable commit messages, since I did not bother at the time.
On Thu, 3 Jan 2013, Jonas Walld�n @ Pike developers forum wrote:
I saw all of those too but they should be resolved on the "of" branch.
I can't reproduce the problem on the main branch:
| Pike v7.9 release 5 running Hilfe v3.5 (Incremental Pike Frontend) | > -0x7fffffff; | (1) Result: -2147483647 | > -0x7fffffff - 1; | (2) Result: -2147483648 | > -0x7fffffff - 2; | (3) Result: -2147483649 | > Pike.get_runtime_info(); | (4) Result: ([ /* 6 elements */ | "abi": 64, | "auto_bignum": 1, | "bytecode_method": "amd64", | "float_size": 64, | "int_size": 64, | "native_byteorder": 1234 | ])
Don't know if there could be other peep.in rules that take precedence or vary randomly. I know that one of the other bugs that I fixed (tNStr) didn't show up every compile.
The fix I did for F_NEG_NUMBER begs the question whether 0x80000000 is a valid argument for negation. I would assume not and that would point to an missing overflow check in peep.in similar to some of the other NUMBER rules. That doesn't explain your working case but I guess you need to trace the opcodes to be sure whether it's the same situation I ran into.
The parameters to F_xxx have type INT32, so a number that can not be repesented as an INT32 is not a valid argument.
The following patch tries to address some missing overflow checks. It fixes the example of -1 -0x7fffffff and _maybe_ others. Some of the checks might not be necessary, though.
arne
diff --git a/src/peep.in b/src/peep.in index c311069..bdc03ba 100644 --- a/src/peep.in +++ b/src/peep.in @@ -39,8 +39,8 @@ CONST1 NEGATE : CONST_1 CONST_1 NEGATE : CONST1 NUMBER NEGATE : NEG_NUMBER($1a) NEG_NUMBER NEGATE : NUMBER ($1a) -NUMBER [(-$1a) > 0] : NEG_NUMBER (-$1a) -NEG_NUMBER [(-$1a) >= 0] : NUMBER (-$1a) +NUMBER [ !INT32_NEG_OVERFLOW($1a) && (-$1a) > 0] : NEG_NUMBER (-$1a) +NEG_NUMBER [ !INT32_NEG_OVERFLOW($1a) && (-$1a) >= 0] : NUMBER (-$1a) NEGATE NEGATE : COMPL COMPL : NEGATE CONST_1 ADD_INTS : COMPL @@ -277,7 +277,7 @@ CONST_1 INDEX: NEG_INT_INDEX (1) CONST1 INDEX: POS_INT_INDEX (1) NUMBER INDEX: POS_INT_INDEX ($1a) NEG_NUMBER INDEX: NEG_INT_INDEX ($1a) -POS_INT_INDEX [$1a < 0]: NEG_INT_INDEX (-$1a) +POS_INT_INDEX [$1a < 0 && !INT32_NEG_OVERFLOW($1a) ]: NEG_INT_INDEX (-$1a) NEG_INT_INDEX [-$1a >= 0]: POS_INT_INDEX (-$1a)
BRANCH_WHEN_ZERO BRANCH LABEL ($1a): BRANCH_WHEN_NON_ZERO($2a) LABEL($1a) @@ -365,15 +365,15 @@ LOCAL VOLATILE_RETURN : RETURN_LOCAL($1a)
NUMBER ADD_INT [ !INT32_ADD_OVERFLOW($1a, $2a) ] : NUMBER($1a+$2a) NUMBER ADD_NEG_INT [ !INT32_SUB_OVERFLOW($1a, $2a) ]: NUMBER($1a-$2a) -NEG_NUMBER ADD_INT [ !INT32_ADD_OVERFLOW(-$1a, $2a) ]: NUMBER(-$1a+$2a) -NEG_NUMBER ADD_NEG_INT [ !INT32_SUB_OVERFLOW(-$1a, $2a) ]: NUMBER(-$1a-$2a) +NEG_NUMBER ADD_INT [ !INT32_SUB_OVERFLOW($2a, $1a) ]: NUMBER($2a-$1a) +NEG_NUMBER ADD_NEG_INT [ !INT32_NEG_OVERFLOW($1a) && !INT32_SUB_OVERFLOW(-$1a, $2a) ]: NUMBER(-$1a-$2a)
CONST0 ADD_INT : NUMBER($2a) CONST0 ADD_NEG_INT : NEG_NUMBER($2a) CONST1 ADD_INT [($2a+1) > 0] : NUMBER($2a+1) -CONST1 ADD_NEG_INT : NEG_NUMBER($2a-1) -CONST_1 ADD_INT : NUMBER($2a-1) -CONST_1 ADD_NEG_INT [($2a+1) > 0] : NEG_NUMBER($2a+1) +CONST1 ADD_NEG_INT [ !INT32_SUB_OVERFLOW($2a, 1) ] : NEG_NUMBER($2a-1) +CONST_1 ADD_INT [ !INT32_SUB_OVERFLOW($2a, 1) ] : NUMBER($2a-1) +CONST_1 ADD_NEG_INT [ !INT32_ADD_OVERFLOW($2a, 1) && ($2a+1) > 0] : NEG_NUMBER($2a+1) CONST0 LOCAL ADD_INTS : LOCAL($2a) CONST0 LOCAL NEGATE ADD_INTS : LOCAL($2a) NEGATE CONST0 GLOBAL ADD_INTS : GLOBAL($2a)
-NUMBER [(-$1a) > 0] : NEG_NUMBER (-$1a) -NEG_NUMBER [(-$1a) >= 0] : NUMBER (-$1a) +NUMBER [ !INT32_NEG_OVERFLOW($1a) && (-$1a) > 0] : NEG_NUMBER (-$1a) +NEG_NUMBER [ !INT32_NEG_OVERFLOW($1a) && (-$1a) >= 0] : NUMBER (-$1a)
Hmm, the above changes hints that the problem is caused by a more aggressive C-compiler, that transcribes
(-X) > 0 and (-X) >= 0
with
X <= 0 and X < 0
which are usually equvivalent, except for X == MIN_INT.
Yes, exactly. Since overflow cannot happen (sic!), its equivalent. I have not seen this problem with gcc, I am building with clang currently.
On Sun, 6 Jan 2013, Henrik Grubbstr�m (Lysator) @ Pike (-) developers forum wrote:
-NUMBER [(-$1a) > 0] : NEG_NUMBER (-$1a) -NEG_NUMBER [(-$1a) >= 0] : NUMBER (-$1a) +NUMBER [ !INT32_NEG_OVERFLOW($1a) && (-$1a) > 0] : NEG_NUMBER (-$1a) +NEG_NUMBER [ !INT32_NEG_OVERFLOW($1a) && (-$1a) >= 0] : NUMBER (-$1a)
Hmm, the above changes hints that the problem is caused by a more aggressive C-compiler, that transcribes
(-X) > 0 and (-X) >= 0
with
X <= 0 and X < 0
which are usually equvivalent, except for X == MIN_INT.
pike-devel@lists.lysator.liu.se
-
Arne Goedeke -
Henrik Grubbstr�m (Lysator) ＠ Pike (-) developers forum -
Jonas Walld�n ＠ Pike developers forum
-
Marcus Comstedt (ACROSS) (Hail Ilpalazzo!) ＠ Pike (-) developers forum
-
Martin Nilsson (Opera Mini - AFK!) ＠ Pike (-) developers forum
-
Mirar ＠ Pike developers forum