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
multiplier(ulong d,int p,uvlong * mp)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
sdiv(ulong d,ulong * mp,int * sp)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
udiv(ulong d,ulong * mp,int * sp,int * pp)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
sdivgen(Node * l,Node * r,Node * ax,Node * dx)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
udivgen(Node * l,Node * r,Node * ax,Node * dx)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
sext(Node * d,Node * s,Node * l)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
sdiv2(long c,int v,Node * l,Node * n)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
smod2(long c,int v,Node * l,Node * n)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 }
207