mul.c 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428
  1. #include "gc.h"
  2. typedef struct Malg Malg;
  3. typedef struct Mparam Mparam;
  4. struct Malg
  5. {
  6. char vals[10];
  7. };
  8. struct Mparam
  9. {
  10. ulong value;
  11. char alg;
  12. char neg;
  13. char shift;
  14. char arg;
  15. char off;
  16. };
  17. static Mparam multab[32];
  18. static int mulptr;
  19. static Malg malgs[] =
  20. {
  21. {0, 100},
  22. {-1, 1, 100},
  23. {-9, -5, -3, 3, 5, 9, 100},
  24. {6, 10, 12, 18, 20, 24, 36, 40, 72, 100},
  25. {-8, -4, -2, 2, 4, 8, 100},
  26. };
  27. /*
  28. * return position of lowest 1
  29. */
  30. int
  31. lowbit(ulong v)
  32. {
  33. int s, i;
  34. ulong m;
  35. s = 0;
  36. m = 0xFFFFFFFFUL;
  37. for(i = 16; i > 0; i >>= 1) {
  38. m >>= i;
  39. if((v & m) == 0) {
  40. v >>= i;
  41. s += i;
  42. }
  43. }
  44. return s;
  45. }
  46. void
  47. genmuladd(Node *d, Node *s, int m, Node *a)
  48. {
  49. Node nod;
  50. nod.op = OINDEX;
  51. nod.left = a;
  52. nod.right = s;
  53. nod.scale = m;
  54. nod.type = types[TIND];
  55. nod.xoffset = 0;
  56. xcom(&nod);
  57. gopcode(OADDR, d->type, &nod, d);
  58. }
  59. void
  60. mulparam(ulong m, Mparam *mp)
  61. {
  62. int c, i, j, n, o, q, s;
  63. int bc, bi, bn, bo, bq, bs, bt;
  64. char *p;
  65. long u;
  66. ulong t;
  67. bc = bq = 10;
  68. bi = bn = bo = bs = bt = 0;
  69. for(i = 0; i < nelem(malgs); i++) {
  70. for(p = malgs[i].vals, j = 0; (o = p[j]) < 100; j++)
  71. for(s = 0; s < 2; s++) {
  72. c = 10;
  73. q = 10;
  74. u = m - o;
  75. if(u == 0)
  76. continue;
  77. if(s) {
  78. o = -o;
  79. if(o > 0)
  80. continue;
  81. u = -u;
  82. }
  83. n = lowbit(u);
  84. t = (ulong)u >> n;
  85. switch(i) {
  86. case 0:
  87. if(t == 1) {
  88. c = s + 1;
  89. q = 0;
  90. break;
  91. }
  92. switch(t) {
  93. case 3:
  94. case 5:
  95. case 9:
  96. c = s + 1;
  97. if(n)
  98. c++;
  99. q = 0;
  100. break;
  101. }
  102. if(s)
  103. break;
  104. switch(t) {
  105. case 15:
  106. case 25:
  107. case 27:
  108. case 45:
  109. case 81:
  110. c = 2;
  111. if(n)
  112. c++;
  113. q = 1;
  114. break;
  115. }
  116. break;
  117. case 1:
  118. if(t == 1) {
  119. c = 3;
  120. q = 3;
  121. break;
  122. }
  123. switch(t) {
  124. case 3:
  125. case 5:
  126. case 9:
  127. c = 3;
  128. q = 2;
  129. break;
  130. }
  131. break;
  132. case 2:
  133. if(t == 1) {
  134. c = 3;
  135. q = 2;
  136. break;
  137. }
  138. break;
  139. case 3:
  140. if(s)
  141. break;
  142. if(t == 1) {
  143. c = 3;
  144. q = 1;
  145. break;
  146. }
  147. break;
  148. case 4:
  149. if(t == 1) {
  150. c = 3;
  151. q = 0;
  152. break;
  153. }
  154. break;
  155. }
  156. if(c < bc || (c == bc && q > bq)) {
  157. bc = c;
  158. bi = i;
  159. bn = n;
  160. bo = o;
  161. bq = q;
  162. bs = s;
  163. bt = t;
  164. }
  165. }
  166. }
  167. mp->value = m;
  168. if(bc <= 3) {
  169. mp->alg = bi;
  170. mp->shift = bn;
  171. mp->off = bo;
  172. mp->neg = bs;
  173. mp->arg = bt;
  174. }
  175. else
  176. mp->alg = -1;
  177. }
  178. int
  179. m0(int a)
  180. {
  181. switch(a) {
  182. case -2:
  183. case 2:
  184. return 2;
  185. case -3:
  186. case 3:
  187. return 2;
  188. case -4:
  189. case 4:
  190. return 4;
  191. case -5:
  192. case 5:
  193. return 4;
  194. case 6:
  195. return 2;
  196. case -8:
  197. case 8:
  198. return 8;
  199. case -9:
  200. case 9:
  201. return 8;
  202. case 10:
  203. return 4;
  204. case 12:
  205. return 2;
  206. case 15:
  207. return 2;
  208. case 18:
  209. return 8;
  210. case 20:
  211. return 4;
  212. case 24:
  213. return 2;
  214. case 25:
  215. return 4;
  216. case 27:
  217. return 2;
  218. case 36:
  219. return 8;
  220. case 40:
  221. return 4;
  222. case 45:
  223. return 4;
  224. case 72:
  225. return 8;
  226. case 81:
  227. return 8;
  228. }
  229. diag(Z, "bad m0");
  230. return 0;
  231. }
  232. int
  233. m1(int a)
  234. {
  235. switch(a) {
  236. case 15:
  237. return 4;
  238. case 25:
  239. return 4;
  240. case 27:
  241. return 8;
  242. case 45:
  243. return 8;
  244. case 81:
  245. return 8;
  246. }
  247. diag(Z, "bad m1");
  248. return 0;
  249. }
  250. int
  251. m2(int a)
  252. {
  253. switch(a) {
  254. case 6:
  255. return 2;
  256. case 10:
  257. return 2;
  258. case 12:
  259. return 4;
  260. case 18:
  261. return 2;
  262. case 20:
  263. return 4;
  264. case 24:
  265. return 8;
  266. case 36:
  267. return 4;
  268. case 40:
  269. return 8;
  270. case 72:
  271. return 8;
  272. }
  273. diag(Z, "bad m2");
  274. return 0;
  275. }
  276. void
  277. shiftit(Type *t, Node *s, Node *d)
  278. {
  279. long c;
  280. c = (long)s->vconst & 31;
  281. switch(c) {
  282. case 0:
  283. break;
  284. case 1:
  285. gopcode(OADD, t, d, d);
  286. break;
  287. default:
  288. gopcode(OASHL, t, s, d);
  289. }
  290. }
  291. static int
  292. mulgen1(ulong v, Node *n)
  293. {
  294. int i, o;
  295. Mparam *p;
  296. Node nod, nods;
  297. for(i = 0; i < nelem(multab); i++) {
  298. p = &multab[i];
  299. if(p->value == v)
  300. goto found;
  301. }
  302. p = &multab[mulptr];
  303. if(++mulptr == nelem(multab))
  304. mulptr = 0;
  305. mulparam(v, p);
  306. found:
  307. // print("v=%.lx a=%d n=%d s=%d g=%d o=%d \n", p->value, p->alg, p->neg, p->shift, p->arg, p->off);
  308. if(p->alg < 0)
  309. return 0;
  310. nods = *nodconst(p->shift);
  311. o = OADD;
  312. if(p->alg > 0) {
  313. regalloc(&nod, n, Z);
  314. if(p->off < 0)
  315. o = OSUB;
  316. }
  317. switch(p->alg) {
  318. case 0:
  319. switch(p->arg) {
  320. case 1:
  321. shiftit(n->type, &nods, n);
  322. break;
  323. case 15:
  324. case 25:
  325. case 27:
  326. case 45:
  327. case 81:
  328. genmuladd(n, n, m1(p->arg), n);
  329. /* fall thru */
  330. case 3:
  331. case 5:
  332. case 9:
  333. genmuladd(n, n, m0(p->arg), n);
  334. shiftit(n->type, &nods, n);
  335. break;
  336. default:
  337. goto bad;
  338. }
  339. if(p->neg == 1)
  340. gins(ANEGL, Z, n);
  341. break;
  342. case 1:
  343. switch(p->arg) {
  344. case 1:
  345. gmove(n, &nod);
  346. shiftit(n->type, &nods, &nod);
  347. break;
  348. case 3:
  349. case 5:
  350. case 9:
  351. genmuladd(&nod, n, m0(p->arg), n);
  352. shiftit(n->type, &nods, &nod);
  353. break;
  354. default:
  355. goto bad;
  356. }
  357. if(p->neg)
  358. gopcode(o, n->type, &nod, n);
  359. else {
  360. gopcode(o, n->type, n, &nod);
  361. gmove(&nod, n);
  362. }
  363. break;
  364. case 2:
  365. genmuladd(&nod, n, m0(p->off), n);
  366. shiftit(n->type, &nods, n);
  367. goto comop;
  368. case 3:
  369. genmuladd(&nod, n, m0(p->off), n);
  370. shiftit(n->type, &nods, n);
  371. genmuladd(n, &nod, m2(p->off), n);
  372. break;
  373. case 4:
  374. genmuladd(&nod, n, m0(p->off), nodconst(0));
  375. shiftit(n->type, &nods, n);
  376. goto comop;
  377. default:
  378. diag(Z, "bad mul alg");
  379. break;
  380. comop:
  381. if(p->neg) {
  382. gopcode(o, n->type, n, &nod);
  383. gmove(&nod, n);
  384. }
  385. else
  386. gopcode(o, n->type, &nod, n);
  387. }
  388. if(p->alg > 0)
  389. regfree(&nod);
  390. return 1;
  391. bad:
  392. diag(Z, "mulgen botch");
  393. return 1;
  394. }
  395. void
  396. mulgen(Type *t, Node *r, Node *n)
  397. {
  398. if(!mulgen1(r->vconst, n))
  399. gopcode(OMUL, t, r, n);
  400. }