4 * Based on: Granlund, T.; Montgomery, P.L.
5 * "Division by Invariant Integers using Multiplication".
6 * SIGPLAN Notices, Vol. 29, June 1994, page 61.
9 #define TN(n) ((uvlong)1 << (n))
14 multiplier(ulong d, int p, uvlong *mp)
17 uvlong mlo, mhi, tlo, thi;
19 l = topbit(d - 1) + 1;
20 mlo = (((TN(l) - d) << 32) / d) + T32;
22 mhi = (((TN(l) + 1 - d) << 32) / d) + T32;
24 mhi = (TN(32 + l) + TN(32 + l - p)) / d;
25 /*assert(mlo < mhi);*/
40 sdiv(ulong d, ulong *mp, int *sp)
45 s = multiplier(d, 32 - 1, &m);
55 udiv(ulong d, ulong *mp, int *sp, int *pp)
60 s = multiplier(d, 32, &m);
67 s = multiplier(d, 32 - p, &m);
83 sdivgen(Node *l, Node *r, Node *ax, Node *dx)
93 //print("a=%d i=%ld s=%d m=%lux\n", a, (long)r->vconst, s, m);
94 gins(AMOVL, nodconst(m), ax);
99 gins(ASHRL, nodconst(31), ax);
100 gins(ASARL, nodconst(s), dx);
107 udivgen(Node *l, Node *r, Node *ax, Node *dx)
113 a = udiv(r->vconst, &m, &s, &t);
114 //print("a=%ud i=%ld p=%d s=%d m=%lux\n", a, (long)r->vconst, t, s, m);
117 gins(ASHRL, nodconst(t), ax);
118 gins(AMOVL, nodconst(m), dx);
122 if(l->op != OREGISTER) {
123 regalloc(&nod, l, Z);
124 gins(AMOVL, l, &nod);
127 gins(AMOVL, nodconst(m), ax);
130 gins(ARCRL, nodconst(1), dx);
135 gins(AMOVL, nodconst(m), ax);
139 gins(ASHRL, nodconst(s), dx);
143 sext(Node *d, Node *s, Node *l)
145 if(s->reg == D_AX && !nodreg(d, Z, D_DX)) {
152 gins(ASARL, nodconst(31), d);
157 sdiv2(long c, int v, Node *l, Node *n)
164 gins(AANDL, nodconst((1 << v) - 1), &nod);
165 gins(AADDL, &nod, n);
169 gins(ACMPL, n, nodconst(0x80000000));
170 gins(ASBBL, nodconst(-1), n);
172 gins(ASARL, nodconst(v), n);
179 smod2(long c, int v, Node *l, Node *n)
191 gins(AXORL, &nod, n);
192 gins(ASUBL, &nod, n);
195 gins(AANDL, nodconst((1 << v) - 1), &nod);
196 gins(AADDL, &nod, n);
197 gins(AANDL, nodconst((1 << v) - 1), n);
198 gins(ASUBL, &nod, n);
201 gins(AANDL, nodconst(1), n);
202 gins(AXORL, &nod, n);
203 gins(ASUBL, &nod, n);