author Tobias Girstmair Tue, 11 Dec 2018 00:38:43 +0000 (01:38 +0100) committer Tobias Girstmair Tue, 11 Dec 2018 00:44:37 +0000 (01:44 +0100)
using this we can save a few more cycles (code size not yet compared).
working principle:
we can distinguish which number to multiply by with the lower nibble
only. to have maximum overlap, use a decision tree to select where to
go. the upper nibble is then just a straight path (there is not much
to deduplicate).

worst case (roughly):
- mul-tree: 30cy tree + 5cy to load data[t]
- cpi-breq-rjmp: 37cy mul_xx + 5cy to load data[t]
- ldZ-ijmp: 28cy mul_xx + 10cy to load mul_jmptable[t]

 fakeasm.h patch | blob | blame | history foo.c patch | blob | blame | history

index e5485170173923c6bce356ee3c9c7e7e57d72afc..f06d5b4aa7b1592ff12d0e8132512b238e9740f4 100644 (file)
--- a/fakeasm.h
+++ b/fakeasm.h
@@ -20,6 +20,7 @@
#define LDI(x,n)  x = n;
#define SBRC(x,b) if (x & 1<<b) //skip if cleared => do if set
#define SBRS(x,b) if (!(x & 1<<b)) //skip if set => do if not
+#define CPSE(x,y) if (x != y) //compare, skip if equal
#define CLR(x)    x = 0;
#define RET       return;
#define RCALL    //pseudo
diff --git a/foo.c b/foo.c
--- a/foo.c
+++ b/foo.c
@@ -20,6 +20,15 @@ void *Z;     //r30 (Zlo)
/*...*/                //r31 (Zhi)
#define Mh x //mod3 vars
#define Ml t // -"-
+
+// .section .data
+u8 data[] = {
+       /*.byte*/ 0x84, 0x9d, 0xb0, 0x69, 0x9d, 0x84, 0x69, 0x58,
+       /*.byte*/ 0x75, 0x8c, 0xb0, 0x69, 0x8c, 0x75, 0x69, 0x58
+};
+
+// .section .text
+
//http://homepage.divms.uiowa.edu/~jones/bcd/mod.shtml
void mod3(void) {
// mod3(Mh.Ml) -> t
@@ -51,14 +60,30 @@ void mod3(void) {
RET
#undef tmp
}
+//.macro definitions for mul-tree:
+#define always(_bit) //nop; for when a test() is not necessary (see tree)
+#define never(_bit)  //nop; for when a test() is not necessary (see tree)
+#define test(_bit,_jmpto) \
+       SBRC    (t, _bit) \
+       RJMP    (_jmpto)
+#define shift16 \
+       LSR     (a2) \
+       ROR     (a1)
+#define shift8 /*top three bits don't need to be corrrect, so save cycles by not carrying*/ \
+       LSR     (a1)
+#define shift0 //nop; last shift is common
+       ADC     (a2, i1, carry) \
+       shift16
+#define add_shift8 /*ditto with carrying*/ \
+       shift8
+#define add_shift0 /*last shift is common*/ \
void g(void) {
// g(i, t) -> t
// tempvars: `x` and `_`
-static void* mul_jmptable[] = { // replaces data[] section at the top
-       &&mul_84, &&mul_9d, &&mul_b0, &&mul_69, &&mul_9d, &&mul_84, &&mul_69, &&mul_58,
-       &&mul_75, &&mul_8c, &&mul_b0, &&mul_69, &&mul_8c, &&mul_75, &&mul_69, &&mul_58
-       // addresses of mul_* stored in little endian (i.e. { lo(mul_84), hi(mul_84), ... })
-};
#define tmp _
ANDI    (t, 0x07)
MOV     (tmp, i2)
@@ -67,173 +92,128 @@ static void* mul_jmptable[] = { // replaces data[] section at the top
CPSE    (tmp, zero)
SUBI    (t, -8)
#undef tmp
+
+       #define tmp _
+       MOV     (tmp, t) //NOTE: must move value away from `t`, as that is also hi(X)
+       tmp = data[tmp];/*
+       LDI     Xhi, hi8(data)
+       LDI     Xlo, lo8(data)
+       ADD     Xlo, tmp  ;<-- the offset (formerly `t`) into data[]
+       LD      tmp, X */
+       MOV     (t, tmp)
+       #undef tmp
+
#define a1 x
#define a2 _
#define a0 t
CLR     (a2)
CLR     (a1)
-       goto *mul_jmptable[t]; /*
-         ;NOTE: optimize by placing *X and *Z below address 0xff and get rid of hi byte
-         LDI  Xlo, lo(mul_jmptable)
-         LDI  Xhi, hi(mul_jmptable)
-         LD   Zlo, X
-         SUBI Xlo, -1
-         LD   Zhi, X
-         IJMP Z */

-       //don't care about top three bits (so don't compute them => _)
-       mul_58: // ___1 1000 (24cy)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
+       /* decision tree multiplication saves cycles and (hopefully) reduces code size
+                            _xxx?
+                        /           \
+                  _xx?0                _xx1?
+                    |                    |
+                  _x?00                _x?01
+                /       \             /     \
+           _?000         _?100      _?001    _?101
+           /   \         /   \        |      /   \
+        _0000 _1000   _0100 _1100   _1001 _0101 _1101
+          |     |       |     |       |     |     |
+         ...   ...     ...   ...     ...   ...   ...
+          |     |       |     |       |     |     |
+          B0    58     84    8C      69     75    9D   */
+               test    (0, m____1)
+       m____0: shift16
+               never   (1)
+       m___00: shift16
+               test    (2, m__100)
+       m__000: shift16
+               test    (3, m_1000)
+       m_0000: shift16
+               always  (4)
+               always  (5)
+               never   (6)
+               shift8
+               always  (7)
+               RJMP    (end_mul) // calc'd 0xb0

-               LSR (a2)
-               ROR (a1)
-               LSR (a1)
-               LSR (a1)
-               RJMP    (endmul)
-       mul_69: // ___0 1001 (26cy)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
+               always  (4)
+               never   (5)
+               shift8
+               always  (6)
+               never   (7)
+               shift0
+               RJMP    (end_mul) // calc'd 0x58

-               LSR (a2)
-               ROR (a1)
-               LSR (a1)
-               LSR (a1)
-               RJMP    (endmul)
-       mul_75: // ___1 0101 (28cy)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
+               test    (3, m_1100)
+       m_0100: shift16
+               RJMP    (upper_8) //'ll calc 0x84

-               LSR (a2)
-               ROR (a1)
-               LSR (a1)
-               LSR (a1)
-               RJMP    (endmul)
-       mul_84: // ___0 0100 (22cy)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
+       upper_8: /* used twice, so deduplicated */
+               never   (4)
+               shift16
+               never   (5)
+               shift8
+               never   (6)
+               shift8
+               always  (7)
+               RJMP    (end_mul) // calc'd 0x8c

-               LSR (a2)
-               ROR (a1)
-               LSR (a1)
-               LSR (a1)
-               RJMP    (endmul)
-       mul_8c: // ___0 1100 (24cy)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
+               never   (1)
+       m___01: shift16
+               test    (2, m__101)
+       m__001: shift16
+               always  (3)
+               never   (4)
+               shift16
+               always  (5)
+               always  (6)
+               never   (7)
+               shift0
+               RJMP    (end_mul) // calc'd 0x69

-               LSR (a2)
-               ROR (a1)
-               LSR (a1)
-               LSR (a1)
-               RJMP    (endmul)
-       mul_9d: // ___1 1101 (28cy)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
+               test    (3, m_1101)
+       m_0101: shift16
+               always  (4)
+               always  (5)
+               always  (6)
+               never   (7)
+               shift0
+               RJMP    (end_mul) // calc'd 0x75

-               LSR (a2)
-               ROR (a1)
-               LSR (a1)
-               LSR (a1)
-               RJMP    (endmul)
-       mul_b0: // ___1 0000 (22cy)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
-               LSR (a2)
-               ROR (a1)
+               always  (4)
+               never   (5)
+               shift8
+               never   (6)
+               shift8
+               always  (7)
+               // calc'd 0x9d

-               LSR (a2)
-               ROR (a1)