Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 1 
#include "gc.h"
2 
 
3 
/*
4 
 * Based on: Granlund, T.; Montgomery, P.L.
5 
 * "Division by Invariant Integers using Multiplication".
6 
 * SIGPLAN Notices, Vol. 29, June 1994, page 61.
7 
 */
8 
 
9 
#define	TN(n)	((uvlong)1 << (n))
10 
#define	T31	TN(31)
11 
#define	T32	TN(32)
12 
 
13 
int
14 
multiplier(ulong d, int p, uvlong *mp)
15 
{
16 
	int l;
17 
	uvlong mlo, mhi, tlo, thi;
18 
 
19 
	l = topbit(d - 1) + 1;
20 
	mlo = (((TN(l) - d) << 32) / d) + T32;
21 
	if(l + p == 64)
22 
		mhi = (((TN(l) + 1 - d) << 32) / d) + T32;
23 
	else
24 
		mhi = (TN(32 + l) + TN(32 + l - p)) / d;
25 
	assert(mlo < mhi);
26 
	while(l > 0) {
27 
		tlo = mlo >> 1;
28 
		thi = mhi >> 1;
29 
		if(tlo == thi)
30 
			break;
31 
		mlo = tlo;
32 
		mhi = thi;
33 
		l--;
34 
	}
35 
	*mp = mhi;
36 
	return l;
37 
}
38 
 
39 
int
40 
sdiv(ulong d, ulong *mp, int *sp)
41 
{
42 
	int s;
43 
	uvlong m;
44 
 
45 
	s = multiplier(d, 32 - 1, &m);
46 
	*mp = m;
47 
	*sp = s;
48 
	if(m >= T31)
49 
		return 1;
50 
	else
51 
		return 0;
52 
}
53 
 
54 
int
55 
udiv(ulong d, ulong *mp, int *sp, int *pp)
56 
{
57 
	int p, s;
58 
	uvlong m;
59 
 
60 
	s = multiplier(d, 32, &m);
61 
	p = 0;
62 
	if(m >= T32) {
63 
		while((d & 1) == 0) {
64 
			d >>= 1;
65 
			p++;
66 
		}
67 
		s = multiplier(d, 32 - p, &m);
68 
	}
69 
	*mp = m;
70 
	*pp = p;
71 
	if(m >= T32) {
72 
		assert(p == 0);
73 
		*sp = s - 1;
74 
		return 1;
75 
	}
76 
	else {
77 
		*sp = s;
78 
		return 0;
79 
	}
80 
}
81 
 
82 
void
83 
sdivgen(Node *l, Node *r, Node *ax, Node *dx)
84 
{
85 
	int a, s;
86 
	ulong m;
87 
	vlong c;
88 
 
89 
	c = r->vconst;
90 
	if(c < 0)
91 
		c = -c;
92 
	a = sdiv(c, &m, &s);
93 
//print("a=%d i=%ld s=%d m=%lux\n", a, (long)r->vconst, s, m);
94 
	gins(AMOVL, nodconst(m), ax);
95 
	gins(AIMULL, l, Z);
96 
	gins(AMOVL, l, ax);
97 
	if(a)
98 
		gins(AADDL, ax, dx);
99 
	gins(ASHRL, nodconst(31), ax);
100 
	gins(ASARL, nodconst(s), dx);
101 
	gins(AADDL, ax, dx);
102 
	if(r->vconst < 0)
103 
		gins(ANEGL, Z, dx);
104 
}
105 
 
106 
void
107 
udivgen(Node *l, Node *r, Node *ax, Node *dx)
108 
{
109 
	int a, s, t;
110 
	ulong m;
111 
	Node nod;
112 
 
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);
115 
	if(t != 0) {
116 
		gins(AMOVL, l, ax);
117 
		gins(ASHRL, nodconst(t), ax);
118 
		gins(AMOVL, nodconst(m), dx);
119 
		gins(AMULL, dx, Z);
120 
	}
121 
	else if(a) {
122 
		if(l->op != OREGISTER) {
123 
			regalloc(&nod, l, Z);
124 
			gins(AMOVL, l, &nod);
125 
			l = &nod;
126 
		}
127 
		gins(AMOVL, nodconst(m), ax);
128 
		gins(AMULL, l, Z);
129 
		gins(AADDL, l, dx);
130 
		gins(ARCRL, nodconst(1), dx);
131 
		if(l == &nod)
132 
			regfree(l);
133 
	}
134 
	else {
135 
		gins(AMOVL, nodconst(m), ax);
136 
		gins(AMULL, l, Z);
137 
	}
138 
	if(s != 0)
139 
		gins(ASHRL, nodconst(s), dx);
140 
}
141 
 
142 
void
143 
sext(Node *d, Node *s, Node *l)
144 
{
145 
	if(s->reg == D_AX && !nodreg(d, Z, D_DX)) {
146 
		reg[D_DX]++;
147 
		gins(ACDQ, Z, Z);
148 
	}
149 
	else {
150 
		regalloc(d, l, Z);
151 
		gins(AMOVL, s, d);
152 
		gins(ASARL, nodconst(31), d);
153 
	}
154 
}
155 
 
156 
void
157 
sdiv2(long c, int v, Node *l, Node *n)
158 
{
159 
	Node nod;
160 
 
161 
	if(v > 0) {
162 
		if(v > 1) {
163 
			sext(&nod, n, l);
164 
			gins(AANDL, nodconst((1 << v) - 1), &nod);
165 
			gins(AADDL, &nod, n);
166 
			regfree(&nod);
167 
		}
168 
		else {
169 
			gins(ACMPL, n, nodconst(0x80000000));
170 
			gins(ASBBL, nodconst(-1), n);
171 
		}
172 
		gins(ASARL, nodconst(v), n);
173 
	}
174 
	if(c < 0)
175 
		gins(ANEGL, Z, n);
176 
}
177 
 
178 
void
179 
smod2(long c, int v, Node *l, Node *n)
180 
{
181 
	Node nod;
182 
 
183 
	if(c == 1) {
184 
		zeroregm(n);
185 
		return;
186 
	}
187 
 
188 
	sext(&nod, n, l);
189 
	if(v == 0) {
190 
		zeroregm(n);
191 
		gins(AXORL, &nod, n);
192 
		gins(ASUBL, &nod, n);
193 
	}
194 
	else if(v > 1) {
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);
199 
	}
200 
	else {
201 
		gins(AANDL, nodconst(1), n);
202 
		gins(AXORL, &nod, n);
203 
		gins(ASUBL, &nod, n);
204 
	}
205 
	regfree(&nod);
206 
}