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)
