123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206 |
- #include "gc.h"
- /*
- * Based on: Granlund, T.; Montgomery, P.L.
- * "Division by Invariant Integers using Multiplication".
- * SIGPLAN Notices, Vol. 29, June 1994, page 61.
- */
- #define TN(n) (1ULL << (n))
- #define T31 TN(31)
- #define T32 TN(32)
- int
- multiplier(ulong d, int p, uvlong *mp)
- {
- int l;
- uvlong mlo, mhi, tlo, thi;
- l = topbit(d - 1) + 1;
- mlo = (((TN(l) - d) << 32) / d) + T32;
- if(l + p == 64)
- mhi = (((TN(l) + 1 - d) << 32) / d) + T32;
- else
- mhi = (TN(32 + l) + TN(32 + l - p)) / d;
- assert(mlo < mhi);
- while(l > 0) {
- tlo = mlo >> 1;
- thi = mhi >> 1;
- if(tlo == thi)
- break;
- mlo = tlo;
- mhi = thi;
- l--;
- }
- *mp = mhi;
- return l;
- }
- int
- sdiv(ulong d, ulong *mp, int *sp)
- {
- int s;
- uvlong m;
- s = multiplier(d, 32 - 1, &m);
- *mp = m;
- *sp = s;
- if(m >= T31)
- return 1;
- else
- return 0;
- }
- int
- udiv(ulong d, ulong *mp, int *sp, int *pp)
- {
- int p, s;
- uvlong m;
- s = multiplier(d, 32, &m);
- p = 0;
- if(m >= T32) {
- while((d & 1) == 0) {
- d >>= 1;
- p++;
- }
- s = multiplier(d, 32 - p, &m);
- }
- *mp = m;
- *pp = p;
- if(m >= T32) {
- assert(p == 0);
- *sp = s - 1;
- return 1;
- }
- else {
- *sp = s;
- return 0;
- }
- }
- void
- sdivgen(Node *l, Node *r, Node *ax, Node *dx)
- {
- int a, s;
- ulong m;
- vlong c;
- c = r->vconst;
- if(c < 0)
- c = -c;
- a = sdiv(c, &m, &s);
- //print("a=%d i=%ld s=%d m=%lux\n", a, (long)r->vconst, s, m);
- gins(AMOVL, nodconst(m), ax);
- gins(AIMULL, l, Z);
- gins(AMOVL, l, ax);
- if(a)
- gins(AADDL, ax, dx);
- gins(ASHRL, nodconst(31), ax);
- gins(ASARL, nodconst(s), dx);
- gins(AADDL, ax, dx);
- if(r->vconst < 0)
- gins(ANEGL, Z, dx);
- }
- void
- udivgen(Node *l, Node *r, Node *ax, Node *dx)
- {
- int a, s, t;
- ulong m;
- Node nod;
- a = udiv(r->vconst, &m, &s, &t);
- //print("a=%ud i=%ld p=%d s=%d m=%lux\n", a, (long)r->vconst, t, s, m);
- if(t != 0) {
- gins(AMOVL, l, ax);
- gins(ASHRL, nodconst(t), ax);
- gins(AMOVL, nodconst(m), dx);
- gins(AMULL, dx, Z);
- }
- else if(a) {
- if(l->op != OREGISTER) {
- regalloc(&nod, l, Z);
- gins(AMOVL, l, &nod);
- l = &nod;
- }
- gins(AMOVL, nodconst(m), ax);
- gins(AMULL, l, Z);
- gins(AADDL, l, dx);
- gins(ARCRL, nodconst(1), dx);
- if(l == &nod)
- regfree(l);
- }
- else {
- gins(AMOVL, nodconst(m), ax);
- gins(AMULL, l, Z);
- }
- if(s != 0)
- gins(ASHRL, nodconst(s), dx);
- }
- void
- sext(Node *d, Node *s, Node *l)
- {
- if(s->reg == D_AX && !nodreg(d, Z, D_DX)) {
- reg[D_DX]++;
- gins(ACDQ, Z, Z);
- }
- else {
- regalloc(d, l, Z);
- gins(AMOVL, s, d);
- gins(ASARL, nodconst(31), d);
- }
- }
- void
- sdiv2(long c, int v, Node *l, Node *n)
- {
- Node nod;
- if(v > 0) {
- if(v > 1) {
- sext(&nod, n, l);
- gins(AANDL, nodconst((1 << v) - 1), &nod);
- gins(AADDL, &nod, n);
- regfree(&nod);
- }
- else {
- gins(ACMPL, n, nodconst(0x80000000));
- gins(ASBBL, nodconst(-1), n);
- }
- gins(ASARL, nodconst(v), n);
- }
- if(c < 0)
- gins(ANEGL, Z, n);
- }
- void
- smod2(long c, int v, Node *l, Node *n)
- {
- Node nod;
- if(c == 1) {
- zeroregm(n);
- return;
- }
- sext(&nod, n, l);
- if(v == 0) {
- zeroregm(n);
- gins(AXORL, &nod, n);
- gins(ASUBL, &nod, n);
- }
- else if(v > 1) {
- gins(AANDL, nodconst((1 << v) - 1), &nod);
- gins(AADDL, &nod, n);
- gins(AANDL, nodconst((1 << v) - 1), n);
- gins(ASUBL, &nod, n);
- }
- else {
- gins(AANDL, nodconst(1), n);
- gins(AXORL, &nod, n);
- gins(ASUBL, &nod, n);
- }
- regfree(&nod);
- }
|