[v4, Resend] MIPS: lib: csum_partial: more instruction paral

[chenj]

Computing sum introduces true data dependency. This patch removes some
true data depdendencies, hence instruction level parallelism is
improved.

This patch brings at most 50% csum performance gain on Loongson 3a
processor in our test.

One example about how this patch works is in CSUM_BIGCHUNK1:
// ** original ** vs ** patch applied **
ADDC(sum, t0) ADDC(t0, t1)
ADDC(sum, t1) ADDC(t2, t3)
ADDC(sum, t2) ADDC(sum, t0)
ADDC(sum, t3) ADDC(sum, t2)

In the original implementation, each ADDC(sum, ...) references the sum
value updated by previous ADDC.

With patch applied, the first two ADDC operations are independent,
hence can be executed simultaneously if possible.

Another example is in the "copy and sum calculating chunk":
// ** original ** vs ** patch applied **
STORE(t0, UNIT(0) ... STORE(t0, UNIT(0) ...
ADDC(sum, t0) ADDC(t0, t1)
STORE(t1, UNIT(1) ... STORE(t1, UNIT(1) ...
ADDC(sum, t1) ADDC(sum, t0)
STORE(t2, UNIT(2) ... STORE(t2, UNIT(2) ...
ADDC(sum, t2) ADDC(t2, t3)
STORE(t3, UNIT(3) ... STORE(t3, UNIT(3) ...
ADDC(sum, t3) ADDC(sum, t2)

With patch applied, the first and third ADDC are independent.

Signed-off-by: chenj <***@lemote.com>
---
1. The result can be found at
http://dev.lemote.com/files/upload/software/csum-opti/csum-opti-benchmark.html
And is generated by a userspace test program:
http://dev.lemote.com/files/upload/software/csum-opti/csum-test.tar.gz

[v2: amend commit message]
[v3: further amend commit message]
[v4: amend commit message & sign-off my patch]

arch/mips/lib/csum_partial.S | 38 +++++++++++++++++++-------------------
1 file changed, 19 insertions(+), 19 deletions(-)

diff --git a/arch/mips/lib/csum_partial.S b/arch/mips/lib/csum_partial.S
index 9901237..6cea101 100644
--- a/arch/mips/lib/csum_partial.S
+++ b/arch/mips/lib/csum_partial.S
@@ -76,10 +76,10 @@
LOAD _t1, (offset + UNIT(1))(src); \
LOAD _t2, (offset + UNIT(2))(src); \
LOAD _t3, (offset + UNIT(3))(src); \
+ ADDC(_t0, _t1); \
+ ADDC(_t2, _t3); \
ADDC(sum, _t0); \
- ADDC(sum, _t1); \
- ADDC(sum, _t2); \
- ADDC(sum, _t3)
+ ADDC(sum, _t2)

#ifdef USE_DOUBLE
#define CSUM_BIGCHUNK(src, offset, sum, _t0, _t1, _t2, _t3) \
@@ -501,21 +501,21 @@ LEAF(csum_partial)
SUB len, len, 8*NBYTES
ADD src, src, 8*NBYTES
STORE(t0, UNIT(0)(dst), .Ls_exc\@)
- ADDC(sum, t0)
+ ADDC(t0, t1)
STORE(t1, UNIT(1)(dst), .Ls_exc\@)
- ADDC(sum, t1)
+ ADDC(sum, t0)
STORE(t2, UNIT(2)(dst), .Ls_exc\@)
- ADDC(sum, t2)
+ ADDC(t2, t3)
STORE(t3, UNIT(3)(dst), .Ls_exc\@)
- ADDC(sum, t3)
+ ADDC(sum, t2)
STORE(t4, UNIT(4)(dst), .Ls_exc\@)
- ADDC(sum, t4)
+ ADDC(t4, t5)
STORE(t5, UNIT(5)(dst), .Ls_exc\@)
- ADDC(sum, t5)
+ ADDC(sum, t4)
STORE(t6, UNIT(6)(dst), .Ls_exc\@)
- ADDC(sum, t6)
+ ADDC(t6, t7)
STORE(t7, UNIT(7)(dst), .Ls_exc\@)
- ADDC(sum, t7)
+ ADDC(sum, t6)
.set reorder /* DADDI_WAR */
ADD dst, dst, 8*NBYTES
bgez len, 1b
@@ -541,13 +541,13 @@ LEAF(csum_partial)
SUB len, len, 4*NBYTES
ADD src, src, 4*NBYTES
STORE(t0, UNIT(0)(dst), .Ls_exc\@)
- ADDC(sum, t0)
+ ADDC(t0, t1)
STORE(t1, UNIT(1)(dst), .Ls_exc\@)
- ADDC(sum, t1)
+ ADDC(sum, t0)
STORE(t2, UNIT(2)(dst), .Ls_exc\@)
- ADDC(sum, t2)
+ ADDC(t2, t3)
STORE(t3, UNIT(3)(dst), .Ls_exc\@)
- ADDC(sum, t3)
+ ADDC(sum, t2)
.set reorder /* DADDI_WAR */
ADD dst, dst, 4*NBYTES
beqz len, .Ldone\@
@@ -646,13 +646,13 @@ LEAF(csum_partial)
nop # improves slotting
#endif
STORE(t0, UNIT(0)(dst), .Ls_exc\@)
- ADDC(sum, t0)
+ ADDC(t0, t1)
STORE(t1, UNIT(1)(dst), .Ls_exc\@)
- ADDC(sum, t1)
+ ADDC(sum, t0)
STORE(t2, UNIT(2)(dst), .Ls_exc\@)
- ADDC(sum, t2)
+ ADDC(t2, t3)
STORE(t3, UNIT(3)(dst), .Ls_exc\@)
- ADDC(sum, t3)
+ ADDC(sum, t2)
.set reorder /* DADDI_WAR */
ADD dst, dst, 4*NBYTES
bne len, rem, 1b

[cee1]

Computing sum introduces true data dependency. This patch removes som=

e

true data depdendencies, hence instruction level parallelism is
improved.
This patch brings at most 50% csum performance gain on Loongson 3a
processor in our test.
// ** original ** vs ** patch applied **
ADDC(sum, t0) ADDC(t0, t1)
ADDC(sum, t1) ADDC(t2, t3)
ADDC(sum, t2) ADDC(sum, t0)
ADDC(sum, t3) ADDC(sum, t2)

=46ollowing is the math behind the above transformation, i.e. math proo=
f
of equalization of the left and right.

=46or convenience of expression:
1. Mark "ADDC(A, B)" as "A =E7=83=AB B", then
A =E7=83=AB B =3D (A + B >=3D 2^64) ? A + B - 2^64 + 1 : A+B

2. Mark 2^64 as @

What we prove is:
sum =E7=83=AB A =E7=83=AB B =3D=3D sum =E7=83=AB (A =E7=83=AB B)

There are two add operations in "sum =E7=83=AB A =E7=83=AB B". Accordin=
g to whether
each add op overflows, there are four cases:
Case 1: The first add op overflows, the second **not**

Case 2: The first add op does **not** overflow, the second does

Case 3: Both the first and the second add op overflow

Case 4: **Neither** the first nor the second add op overflow


=3D=3D=3D=3D
Case 1: The first add op overflows, the second **not**, that means:
1 sum + A >=3D @
2 sum + A - @ + 1 + B < @
sum =E7=83=AB A =E7=83=AB B =3D sum + A + B - @ + 1

If A + B >=3D @:
=3D> A =E7=83=AB B =3D A + B - @ + 1

Q: sum + (A =E7=83=AB B) =3D sum + A + B - @ + 1 OVERFLOWS=EF=BC=
=9F(i.e. sum + A
+ B - @ + 1 >=3D @)
sum =E7=83=AB (A =E7=83=AB B) =3D sum + A + B - @ + 1 # see =
(2)

If A + B < @:
=3D> A =E7=83=AB B =3D A + B

Q: sum + (A =E7=83=AB B) =3D sum + A + B OVERFLOWS?
sum + A + B >=3D @ + B >=3D @ # adds B to both sides of (1)
=3D> sum =E7=83=AB (A =E7=83=AB B) =3D sum + A + B - @ + 1


=3D=3D=3D=3D
Case 2: The first add op does **not** overflow, the second does, that m=
eans:
1 sum + A < @
2 sum + A + B >=3D @
sum =E7=83=AB A =E7=83=AB B =3D sum + A + B - @ + 1

If A + B >=3D @:
=3D> A =E7=83=AB B =3D A + B - @ + 1

Q: sum + (A =E7=83=AB B) =3D sum + A + B - @ + 1 OVERFLOWS?
sum + A + B - @ + 1 < @ + B - @ + 1 # adds 'B-@+1' to both
sides of (1)
=3D> sum + A + B - @ + 1 < B + 1 <=3D @
=3D> sum + A + B - @ + 1 < @
=3D> sum =E7=83=AB (A =E7=83=AB B) =3D sum + A + B - @ + 1

If A + B < @:
=3D> A =E7=83=AB B =3D A + B

Q: sum + (A =E7=83=AB B) =3D sum + A + B OVERFLOWS?
sum =E7=83=AB (A =E7=83=AB B) =3D sum + A + B - @ + 1 # see =
(2)


=3D=3D=3D=3D
Case 3: Both the first and the second add op overflow, that means:
1 sum + A >=3D @
2 sum + A + B - @ + 1 >=3D @
sum =E7=83=AB A =E7=83=AB B =3D sum + A + B - 2@ + 2

3 A + B >=3D 2@ - 1 - sum # transformed from (2)
1 + sum <=3D @
=3D> @ + 1 + sum <=3D 2@
=3D> @ <=3D 2@ - 1 - sum
=3D> @ <=3D 2@ - 1 - sum <=3D A + B # see (3)
=3D> A + B >=3D @
=3D> A =E7=83=AB B =3D A + B - @ + 1

Q: sum + (A =E7=83=AB B) =3D sum + A + B - @ + 1 OVERFLOWS?
sum =E7=83=AB (A =E7=83=AB B) =3D sum + A + B - 2@ + 2 # see (2)


=3D=3D=3D=3D
Case 4: Neither the first nor the second add op overflow, that means:
1 sum + A < @
2 sum + A + B < @
sum =E7=83=AB A =E7=83=AB B =3D sum + A + B

A + B < @ - sum <=3D @ # transformed from (2)
=3D> A + B < @
=3D> A =E7=83=AB B =3D A + B

Q: sum + (A =E7=83=AB B) =3D sum + A + B OVERFLOWS?
sum =E7=83=AB (A =E7=83=AB B) =3D sum + A + B # see (2)


Conclusion: sum =E7=83=AB A =E7=83=AB B =3D=3D sum =E7=83=AB (A =E7=83=AB=
B)


--=20
Regards,

- cee1

[cee1]

Hi Ralf,

Are you happy with the patch and the math explanation? Then it may be
merged? :-)



---
Regards,

- cee1