Two week soft poke. The 64 bit signed integer modulus is currently broken in gcc. I see two possible ways to fix this. - Fixing the assembly version. I tracked the algorithm back to Koren's text book "Computer Arithmetic Algorithms" section 3.2, and added defines rather than registers to make it a bit easier to read. - Applying the patch that's similar to the version Xilinx/AMD has been using. They reverted the assembly version, and use the stock version other bsps use.
The assembly version is a lot smaller, and uses 20-30% less instructions than the base version. Both of the provided patches were tested with the gcc torture tests. Showing stock version broken, and the patches fixing signed 64 bit integer modulus. Thanks, Sam On Sun, Oct 11, 2026 at 2:17 AM Sam Price <[email protected]> wrote: > libgcc's MicroBlaze __moddi3 has been wrong since the port landed in 2010. > It returns the wrong answer for most inputs, differently on each byte > order, > and for an LLONG_MIN dividend it either fails to terminate or returns > nonsense depending on the byte order. > > These are two ways to fix it, and you should apply one or the other, not > both. > Each applies to an unpatched master on its own; 2/2 is not a follow-on to > 1/2. > Both touch libgcc only. > > 1/2 Ramin Moussavi's fix to the existing assembly, with my additions. > 2/2 Delete the assembly and use the generic libgcc2.c version. > > I measured them rather than guessing, and would rather you chose. > > Which tests prove it > -------------------- > > Two, both already in the tree. I ran all 1685 of gcc.c-torture/execute at > -O2 on qemu-system-microblaze and qemu-system-microblazeel, machine > petalogix-s3adsp1800, against each of the three __moddi3 implementations. > Exactly two tests separate them: > > unpatched with 1/2 with 2/2 > pr50865.c be hangs pass pass > le abort pass pass > arith-rand-ll.c be abort pass pass > le abort pass pass > > all 1685 be 1631 pass 1633 pass 1633 pass > le 1631 pass 1633 pass 1633 pass > > pr50865.c is the one to look at. It is four lines of INT64_MIN % 1LL and > INT64_MIN % l1 -- the LLONG_MIN non-termination, which is defect 4 of the > four 1/2 lists -- and it has been in the tree since PR middle-end/50865 in > 2011. So an > in-tree execute test has been able to catch this for fifteen years. > arith-rand-ll.c reaches it differently, through its signed long long block > over 10000 random bitstrings checking r1 * yy + r2 == xx. > > No new test is needed to justify the fix. 1/2 also gives the same verdict > as > the generic C on every one of the 1685 on both byte orders, test by test > and > not just in total, so it recovers what the bug costs and changes nothing > else. > > Choosing between them > --------------------- > > 2/2 is tempting because hand-writing this helper is close to unique. > Across > libgcc, ia64 is the only other target with a moddi3 in assembly, and its > reason does not transfer: lib1funcs.S builds it out of the FP divide > sequence > from the Intel optimization guide, which is a hardware argument MicroBlaze > cannot make. visium supplies a C version, pa rebuilds the generic one for > a > 32-bit word, and arm/symbian, avr, bpf and nds32-mculib exclude the helper > outright. No other port hand-writes radix-2 soft division. A routine > almost > nobody felt the need to write by hand, and which was wrong for sixteen > years, > is a reasonable thing to delete. > > The measurements argue the other way, and the gap is a gap in algorithm > rather > than in how tightly each is written. The assembly is binary restoring > division, radix 2, one quotient bit an iteration -- Koren, Computer > Arithmetic > Algorithms, section 3.2, which 1/2 cites in its header and whose notation > its > comments use. The generic path is Knuth's Algorithm D, TAOCP volume 2 > section > 4.3.1: digit recurrence at radix 2^16 with quotient-digit estimation and > add-back, reached through __udivmoddi4 and longlong.h's __udiv_qrnnd_c. > That > is why the two differ by tens of percent rather than a constant factor, and > why the figures below are not a like-for-like comparison of two codings of > the > same method. > > 4701 vectors with expected values computed on the host, executed > instructions > counted exactly with -icount 0, the generic version at -O2 since that is > what > libgcc builds LIB2FUNCS at: > > code size executed insns > assembly __moddi3 44 be 2777735 le 2777672 > generic C at -O2 62 be 3995016 le 3988505 > + __udivmoddi4 be 1030 > le 1028 > total be 1092 +43.8% +43.6% > le 1090 > > About 25 times smaller and about 30% fewer instructions, some 258 a call. > On > an embedded target that is not close, so I recommend 1/2. Two caveats in > fairness to 2/2. __udivmoddi4 is shared, so a program already doing 64-bit > unsigned division links it anyway and the generic __moddi3 then costs 62 > instructions rather than 1092. > > And, more to the point, Xilinx already did 2/2. In their GCC fork, > 7090a49d007 of 2014-04-18 -- Nagaraju Mekala, "Removed moddi3 routinue" -- > deletes the file with the message "Using the default moddi3 function as the > existing implementation has many bugs". Its t-microblaze hunk is identical > to 2/2's. It was never sent here, so upstream has carried for twelve more > years a routine the vendor had already written off, and both their 4.8.3 > and > 13.3.0 trees have been on the generic path since. If you take 1/2, you are > reinstating something its own maintainer gave up on; that is defensible now > that it is correct and measured, but it should be a decision rather than an > oversight. > > The two also disagree for x % 0, undefined either way. The assembly > returns > zero, matching divsi3.S, modsi3.S, udivsi3.S and umodsi3.S. The generic > version returns the low word of the dividend, because libgcc2.c does > "d0 = 1 / d0" to provoke a hardware trap and on MicroBlaze that is a call > to > __udivsi3, which itself returns zero for a zero divisor -- so no trap, and > the > algorithm runs on with d0 still zero. Neither matches a core with hardware > divide, where a % b is a - (a / b) * b and a zero quotient makes a % 0 > give a; > that divergence predates this series and aligning it would touch all five > helpers. > > While on the subject of those four: it would be fair to wonder whether the > whole family is suspect. It is not. I checked the 32-bit pair at the same > extremes this series is about -- INT_MIN against INT_MAX, -INT_MAX, > INT_MIN, > INT_MAX-1, INT_MIN+1, 1 and 3, divide and modulo -- and divsi3.S and > modsi3.S > answer all of them correctly on both byte orders, against host-computed > expectations. They work on single registers, so they have neither the > register-pair hazard of defect 1 nor the 64-bit normalization of defect 4. > > What the existing tests do not reach > ------------------------------------ > > Those two tests catch the bug, but it would be misleading to let that > stand as > evidence the routine is well covered. Modelling the loop bit-exactly on > the > host and counting the states each operand stream reaches: > > iterations partial rem >= 2^63 |D| > = 2^63 > pr50865.c 256 0 0 > arith-rand-ll.c 331,380 0 0 > my own 4701-vector set 266,260 6 26 > > Neither in-tree test drives the partial remainder across the sign boundary > or > divides by LLONG_MIN. pr50865.c cannot: every divisor in it is 1, so the > partial remainder stays at zero. arith-rand-ll.c gets to |D| >= 2^62 411 > times and no further. That matters because the loop's keep-or-skip > decision > reads the sign bit of a 64-bit subtraction to settle an unsigned > comparison, > and the sign boundary is where one would look for that to break. > > It does not break, for a reason rather than by luck: D <= 2^63 since it is > the > magnitude of a signed 64-bit value, and the loop keeps 0 <= R < D, so R' - > D > lies in [-D, D-1] and is always in signed range, where the sign bit is the > sign of the true difference. The same bound is why no 65th remainder bit > is > needed. 1/2 states that where the comparison is. > > Reaching the state needs both magnitudes within a hair of 2^63. Sweeping > that > region exhaustively -- 67,108,864 cases -- the signed test never disagrees > with > a true unsigned compare, the invariant never breaks, no answer is wrong, > and > the partial remainder reaches exactly 2^63 and never more. All 8192 cases > that > get there have the dividend exactly LLONG_MIN; on the target both fixes > answer > all 8192 on both byte orders, and so does the generic C. > > So I am sending a test for it, separately from this series and not numbered > into it, because it tests the C semantics rather than either fix and is not > MicroBlaze specific: > > [PATCH] testsuite: cover 64-bit divide and modulo at the extremes of the > type > > Three operand pairs reach the state -- LLONG_MIN against LLONG_MAX, > -LLONG_MAX > and LLONG_MIN -- so it is a dozen lines in the shape of divmod-1.c, which > covers the same ground for signed char and signed short and stops below > long > long, where x % -1 at the minimum would be undefined. It applies to an > unpatched tree or on top of either fix. Unpatched it hangs on > microblaze-elf > and aborts on microblazeel-elf; it passes with either fix on both byte > orders, > and on the host. Take it or leave it independently of the choice above. > > What I am not proposing is putting these cases in arith-rand-ll.c: it is > built > on random bitstrings, so fixed corner values do not belong in it, and it is > shared by every target, which makes widening it a different conversation. > The > 4701- and 8192-vector sets stay out of the tree too -- they are development > scaffolding, and the three pairs are what carries the coverage. > > The wider point is about the suite rather than this patch. A test that > catches this has been in the tree since 2011, so the coverage was never the > problem; nobody was running it. I cannot prove that -- gcc-testresults > would > settle it and I could not reach its archive -- but across the whole of > gcc/testsuite only 13 files mention microblaze, almost all ChangeLogs, the > only real references are two dg-do compile tests, and there is no xfail > keyed > on microblaze anywhere. Not one execute test carries a microblaze marker. > > Nothing else in the suite is failing for the target, for what it is worth. > Besides the 1633 that pass, 35 do not link against my deliberately minimal > bare-metal runtime and 13 want __int128, decimal floating-point or x86 asm > -- > both of those being my harness having no notion of > dg-require-effective-target, rather than anything about MicroBlaze. Four > fail: one wants a real printf, and three test fixes that postdate GCC 12, > which is the compiler I have; two of those three are not in the 13.3 > testsuite at all. So there is no backlog of target bugs hiding behind this > one, which I had half expected to find. > > Provenance > ---------- > > The assembly fix in 1/2 is Ramin Moussavi's, from OpenADK, and 1/2 credits > him > in its first paragraph. He has agreed to my submitting it; I sign it off > because the additions are mine and he is not sending it himself. > > My additions reach the instruction stream, so here is what they cost: > > code size executed insns > his patch as sent 56 be 3607673 le 3607610 > 1/2 as sent here 44 be 2777735 le 2777672 > > Most of that is dropping the quotient. His patch fixes the return value so > that r3:r4 is returned instead of r29:r30, which leaves the quotient in > r29:r30 computed and never read; taking it out removes four instructions > from > the loop body, two from the setup and the four that spilled and reloaded > it, > and lets the loop tail collapse to a single BNEi for an eleventh. The > rest are > an unreferenced label with the BRI that only jumped over it, and a delay > slot > on the first zero test his version left empty. > > Beyond the code: comments rewritten, registers and labels named after the > reference, the divide-by-zero note, the invariant above, and a correction > to > his commit message -- it said big-endian got 30079 of 40420 values wrong > while > little-endian hung, but which failure mode appears first depends on the > order > of the vectors, since the routine both hangs and answers wrongly. > > Sam Price (2): > microblaze: fix the hand-written 64-bit signed modulo > microblaze: use the generic __moddi3 instead of the assembly one > > -- > 2.39.5 (Apple Git-154) > > -- Sincerely, Sam Price
