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 } 207