#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) ((uvlong)1 << (n))#define T31 TN(31)#define T32 TN(32) intmultiplier(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;} intsdiv(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;} intudiv(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; }} voidsdivgen(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);} voidudivgen(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);} voidsext(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); }} voidsdiv2(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);} voidsmod2(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);}
#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) ((uvlong)1 << (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);
}