top.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646
  1. /* $Header$ */
  2. /*
  3. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  4. * See the copyright notice in the ACK home directory, in the file "Copyright".
  5. */
  6. #include <stdio.h>
  7. #include "gen.h"
  8. #include "top.h"
  9. #include "queue.h"
  10. /* STANDARD MACHINE-INDEPENT C CODE *************/
  11. extern char *lstrip();
  12. extern instr_p newinstr();
  13. extern instr_p read_instr();
  14. extern instr_p gen_instr();
  15. extern char *eval_templ();
  16. extern instr_p malloc();
  17. struct variable var[NRVARS+1];
  18. struct variable ANY; /* ANY symbol matching any instruction */
  19. char *REST; /* Opcode of first instruction not matched by current pattern */
  20. #include "gen.c"
  21. /* Macros for efficiency: */
  22. #define is_white(c) ( (c) == ' ' || (c) == '\t')
  23. /* Skip white space in the unprocessed part of instruction 'ip' */
  24. #define skip_white(ip) while (is_white(*(ip)->rest_line)) (ip)->rest_line++
  25. main()
  26. {
  27. optimize();
  28. exit(0);
  29. }
  30. /* Optimize the standard input.
  31. * The optimizer uses a moving window. The instructions in the current
  32. * window are matched against a set of patterns generated from the
  33. * machine description table. If the match fails, the first instruction of
  34. * the window is moved to a back-up queue and a new instruction is
  35. * read from the input and appended to the end of the window.
  36. * If a matching pattern is found (and its operands etc. are ok),
  37. * the instructions at the head of the window are replaced by new
  38. * instructions, as indicated in the descriptor table; a new window
  39. * is created, consisting of the back-up instructions and the new
  40. * instructions and the rest of the old window. So effectively the
  41. * window moves a bit to the left after every hit. Hence sequences of
  42. * optimizations like:
  43. * movl r0,x ; cmpl $0,x -> movl r0,x ; tstl x -> movl r0,x
  44. * are captured without having a separate pattern for "movl ; cmpl".
  45. *
  46. * Whenever the backup queue exceeds some threshold, its first instruction
  47. * is written to the output and is removed.
  48. */
  49. optimize()
  50. {
  51. struct queue_t windowq, backupq;
  52. queue window, backup;
  53. instr_p ip;
  54. bool change;
  55. window = &windowq;
  56. backup = &backupq;
  57. empty_queue(window);
  58. empty_queue(backup);
  59. fill_window(window,MIN_WINDOW_SIZE);
  60. while (!empty(window)) {
  61. if (try_hashentry(hashtab[hash(window)],window) ||
  62. try_hashentry(hashany,window)) {
  63. join_queues(backup,window);
  64. } else {
  65. ip = qhead(window);
  66. remove_head(window);
  67. add(backup,ip);
  68. if (qlength(backup) > MIN_WINDOW_SIZE) {
  69. write_first(backup);
  70. }
  71. }
  72. fill_window(window,MIN_WINDOW_SIZE);
  73. }
  74. while (!empty(backup)) write_first(backup);
  75. }
  76. bool try_hashentry(list,window)
  77. int *list;
  78. queue window;
  79. {
  80. register int *pp;
  81. patdescr_p p;
  82. for (pp = list; *pp != -1; pp++) {
  83. p = &patterns[*pp];
  84. if (check_pattern(p,window) &&
  85. check_operands(p,window) &&
  86. check_constraint(*pp)) {
  87. xform(p,window);
  88. return TRUE;
  89. }
  90. }
  91. return FALSE;
  92. }
  93. /* TEMP. */
  94. /* int hash(w)
  95. queue w;
  96. {
  97. instr_p ip;
  98. ip = qhead(w);
  99. return ip->opc[0] % 31;
  100. }
  101. */
  102. int hash(w)
  103. queue w;
  104. {
  105. register char *p;
  106. register sum,i;
  107. instr_p ip;
  108. ip = qhead(w);
  109. /* for (sum=0,p=ip->opc;*p;p++)
  110. sum += *p;
  111. */
  112. for (sum=i=0,p=ip->opc;*p;i += 3)
  113. sum += (*p++)<<(i&03);
  114. return(sum%128);
  115. }
  116. /* Fill the working window until it contains at least 'len' items.
  117. * When end-of-file is encountered it may contain fewer items.
  118. */
  119. fill_window(w,len)
  120. register queue w;
  121. {
  122. register instr_p ip;
  123. while(qlength(w) < len) {
  124. if ((ip = read_instr()) == NIL) break;
  125. ip->rest_line = ip->line;
  126. set_opcode(ip);
  127. add(w,ip);
  128. }
  129. }
  130. write_first(w)
  131. queue w;
  132. {
  133. register instr_p ip = qhead(w);
  134. fputs(ip->line, stdout);
  135. remove_head(w);
  136. oldinstr(ip);
  137. }
  138. /* Try to recognize the opcode part of an instruction */
  139. set_opcode(ip)
  140. register instr_p ip;
  141. {
  142. register char *p,*q;
  143. char *qlim;
  144. if (ip->state == JUNK) return;
  145. skip_white(ip);
  146. p = ip->rest_line;
  147. if (*p == LABEL_STARTER) {
  148. strcpy(ip->opc,"labdef");
  149. ip->state = ONLY_OPC;
  150. return;
  151. }
  152. q = ip->opc;
  153. qlim = q + MAX_OPC_LEN;
  154. while(*p != OPC_TERMINATOR && *p != '\n') {
  155. if (q == qlim) {
  156. ip->state = JUNK;
  157. return;
  158. }
  159. *q++ = *p++;
  160. }
  161. *q = '\0';
  162. ip->rest_line = p;
  163. ip->state = (well_shaped(ip->opc) ? ONLY_OPC : JUNK);
  164. }
  165. /* Check if pattern 'p' matches the current input */
  166. bool check_pattern(p,w)
  167. patdescr_p p;
  168. queue w;
  169. {
  170. register idescr_p id_p;
  171. idescr_p idlim;
  172. register instr_p ip;
  173. ip = qhead(w);
  174. ANY.vstate = UNINSTANTIATED;
  175. idlim = &p->pat[p->patlen];
  176. for (id_p = p->pat; id_p < idlim; id_p++) {
  177. if (ip == NIL || ip->state == JUNK) return FALSE;
  178. if (id_p->opcode == (char *) 0) {
  179. unify(ip->opc,&ANY);
  180. } else {
  181. if (strcmp(ip->opc,id_p->opcode) != 0) return FALSE;
  182. }
  183. ip = next(ip);
  184. }
  185. REST = ip->opc;
  186. return TRUE;
  187. }
  188. bool check_operands(p,w)
  189. patdescr_p p;
  190. queue w;
  191. {
  192. register instr_p ip;
  193. register idescr_p id_p;
  194. int n;
  195. /* fprintf(stderr,"try pattern %d\n",p-patterns); */
  196. clear_vars();
  197. for (id_p = p->pat, ip = qhead(w); id_p < &p->pat[p->patlen];
  198. id_p++, ip = next(ip)) {
  199. assert(ip != NIL);
  200. if (ip->state == JUNK ||
  201. (ip->state == ONLY_OPC && !split_operands(ip))) {
  202. return FALSE;
  203. }
  204. for (n = 0; n < MAXOP; n++) {
  205. if (!opmatch(&id_p->templates[n],ip->op[n])) {
  206. return FALSE;
  207. }
  208. }
  209. }
  210. /* fprintf(stderr,"yes\n"); */
  211. return TRUE;
  212. }
  213. /* Reset all variables to uninstantiated */
  214. clear_vars()
  215. {
  216. register v;
  217. for (v = 1; v <= NRVARS; v++) var[v].vstate = UNINSTANTIATED;
  218. }
  219. /* See if operand 's' matches the operand described by template 't'.
  220. * As a side effect, any uninstantiated variables used in the
  221. * template may become instantiated. For such a variable we also
  222. * check if it satisfies the constraint imposed on it in the
  223. * mode-definitions part of the table.
  224. */
  225. bool opmatch(t,s)
  226. templ_p t;
  227. char *s;
  228. {
  229. char *l, buf[MAXOPLEN];
  230. bool was_instantiated;
  231. int vno;
  232. vno = t->varno;
  233. if (vno == -1 || s[0] == '\0' ) {
  234. return (vno == -1 && s[0] == '\0');
  235. }
  236. was_instantiated = (var[vno].vstate == INSTANTIATED);
  237. strcpy(buf,s);
  238. if ( (l=lstrip(buf,t->lctxt)) != NULLSTRING && rstrip(l,t->rctxt)) {
  239. return vno == 0 || (unify(l,&var[vno]) &&
  240. (was_instantiated || tok_chk(vno)));
  241. }
  242. return FALSE;
  243. }
  244. /* Try to recognize the operands of an instruction */
  245. bool split_operands(ip)
  246. register instr_p ip;
  247. {
  248. register int i;
  249. bool res;
  250. if (strcmp(ip->opc,"labdef") ==0) {
  251. labeldef(ip);
  252. } else {
  253. for (i = 0; operand(ip,i) && op_separator(ip); i++);
  254. }
  255. res = remainder_empty(ip);
  256. ip->state = (res ? DONE : JUNK);
  257. return res;
  258. }
  259. labeldef(ip)
  260. register instr_p ip;
  261. {
  262. register char *p;
  263. int oplen;
  264. p = ip->rest_line;
  265. while( *p != LABEL_TERMINATOR) p++;
  266. oplen = p - ip->rest_line;
  267. if (oplen == 0 || oplen > MAXOPLEN) return;
  268. strncpy(ip->op[0],ip->rest_line,oplen);
  269. ip->op[0][oplen] = '\0';
  270. ip->rest_line = ++p;
  271. return;
  272. }
  273. /* Try to recognize the next operand of instruction 'ip' */
  274. bool operand(ip,n)
  275. register instr_p ip;
  276. {
  277. register char *p;
  278. int oplen;
  279. skip_white(ip);
  280. p = ip->rest_line;
  281. while( *p != OP_SEPARATOR && *p != '\n') p++;
  282. oplen = p - ip->rest_line;
  283. if (oplen == 0 || oplen > MAXOPLEN) return FALSE;
  284. strncpy(ip->op[n],ip->rest_line,oplen);
  285. ip->op[n][oplen] = '\0';
  286. ip->rest_line = p;
  287. return TRUE;
  288. }
  289. /* See if the unprocessed part of instruction 'ip' is empty
  290. * (or contains only white space).
  291. */
  292. bool remainder_empty(ip)
  293. instr_p ip;
  294. {
  295. skip_white(ip);
  296. return *ip->rest_line == '\n';
  297. }
  298. /* Try to match 'ctxt' at the beginning of string 'str'. If this
  299. * succeeds then return a pointer to the rest (unmatched part) of 'str'.
  300. */
  301. char *lstrip(str,ctxt)
  302. register char *str, *ctxt;
  303. {
  304. assert(ctxt != NULLSTRING);
  305. while (*str != '\0' && *str == *ctxt) {
  306. str++;
  307. ctxt++;
  308. }
  309. return (*ctxt == '\0' ? str : NULLSTRING);
  310. }
  311. /* Try to match 'ctxt' at the end of 'str'. If this succeeds then
  312. * replace truncate 'str'.
  313. */
  314. bool rstrip(str,ctxt)
  315. char *str,*ctxt;
  316. {
  317. register char *s, *c;
  318. for (s = str; *s != '\0'; s++);
  319. for (c = ctxt; *c != '\0'; c++);
  320. while (c >= ctxt) {
  321. if (s < str || *s != *c--) return FALSE;
  322. *s-- = '\0';
  323. }
  324. return TRUE;
  325. }
  326. /* Try to unify variable 'v' with string 'str'. If the variable
  327. * was instantiated the unification only succeeds if the variable
  328. * and the string match; else the unification succeeds and the
  329. * variable becomes instantiated to the string.
  330. */
  331. bool unify(str,v)
  332. char *str;
  333. register struct variable *v;
  334. {
  335. if (v->vstate == UNINSTANTIATED) {
  336. v->vstate = INSTANTIATED;
  337. strcpy(v->value,str);
  338. return TRUE;
  339. } else {
  340. return strcmp(v->value,str) == 0;
  341. }
  342. }
  343. /* Transform the working window according to pattern 'p' */
  344. xform(p,w)
  345. patdescr_p p;
  346. queue w;
  347. {
  348. register instr_p ip;
  349. int i;
  350. for (i = 0; i < p->patlen; i++) {
  351. ip = qhead(w);
  352. remove_head(w);
  353. oldinstr(ip);
  354. }
  355. replacement(p,w);
  356. }
  357. /* Generate the replacement for pattern 'p' and insert it
  358. * at the front of the working window.
  359. * Note that we generate instructions in reverser order.
  360. */
  361. replacement(p,w)
  362. register patdescr_p p;
  363. queue w;
  364. {
  365. register idescr_p id_p;
  366. for (id_p = &p->repl[p->replen-1]; id_p >= p->repl; id_p--) {
  367. insert(w,gen_instr(id_p));
  368. }
  369. }
  370. /* Generate an instruction described by 'id_p'.
  371. * We build a 'line' for the new instruction and call set_opcode()
  372. * to re-recognize its opcode. Hence generated instructions are treated
  373. * in exactly the same way as normal instructions that are just read in.
  374. */
  375. instr_p gen_instr(id_p)
  376. idescr_p id_p;
  377. {
  378. char *opc;
  379. instr_p ip;
  380. register templ_p t;
  381. register char *s;
  382. bool islabdef;
  383. int n;
  384. static char tmp[] = "x";
  385. ip = newinstr();
  386. s = ip->line;
  387. opc = id_p->opcode;
  388. if (opc == (char *) 0) opc = ANY.value;
  389. if (strcmp(opc,"labdef") == 0) {
  390. islabdef = TRUE;
  391. s[0] = '\0';
  392. } else {
  393. strcpy(s,opc);
  394. tmp[0] = OPC_TERMINATOR;
  395. strcat(s,tmp);
  396. islabdef = FALSE;
  397. }
  398. for (n = 0; n < MAXOP;) {
  399. t = &id_p->templates[n++];
  400. if (t->varno == -1) break;
  401. strcat(s,t->lctxt);
  402. if (t->varno != 0) strcat(s,var[t->varno].value);
  403. strcat(s,t->rctxt);
  404. if (n<MAXOP && id_p->templates[n].varno!=-1) {
  405. tmp[0] = OP_SEPARATOR;
  406. strcat(s,tmp);
  407. }
  408. }
  409. if (islabdef) {
  410. tmp[0] = LABEL_TERMINATOR;
  411. strcat(s,tmp);
  412. }
  413. strcat(s,"\n");
  414. ip->rest_line = ip->line;
  415. set_opcode(ip);
  416. return ip;
  417. }
  418. /* Reading and writing instructions.
  419. * An instruction is assumed to be on one line. The line
  420. * is copied to the 'line' field of an instruction struct,
  421. * terminated by a \n and \0. If the line is too long (>MAXLINELEN),
  422. * it is split into pieces of length MAXLINELEN and the state of
  423. * each such struct is set to JUNK (so it will not be optimized).
  424. */
  425. static bool junk_state = FALSE; /* TRUE while processing a very long line */
  426. instr_p read_instr()
  427. {
  428. instr_p ip;
  429. register int c;
  430. register char *p;
  431. register FILE *inp = stdin;
  432. char *plim;
  433. ip = newinstr();
  434. plim = &ip->line[MAXLINELEN];
  435. if (( c = getc(inp)) == EOF) return NIL;
  436. for (p = ip->line; p < plim;) {
  437. *p++ = c;
  438. if (c == '\n') {
  439. *p = '\0';
  440. if (junk_state) ip->state = JUNK;
  441. junk_state = FALSE;
  442. return ip;
  443. }
  444. c = getc(inp);
  445. }
  446. ungetc(c,inp);
  447. *p = '\0';
  448. junk_state = ip->state = JUNK;
  449. return ip;
  450. }
  451. /* Core allocation.
  452. * As all instruction struct have the same size we can re-use every struct.
  453. * We maintain a pool of free instruction structs.
  454. */
  455. static instr_p instr_pool;
  456. int nr_mallocs = 0; /* for statistics */
  457. instr_p newinstr()
  458. {
  459. register instr_p ip;
  460. int i;
  461. if (instr_pool == NIL) {
  462. instr_pool = malloc(sizeof(struct instruction));
  463. nr_mallocs++;
  464. }
  465. assert(instr_pool != NIL);
  466. ip = instr_pool;
  467. instr_pool = instr_pool->fw;
  468. ip->fw = ip->bw = NIL;
  469. ip->rest_line = NULLSTRING;
  470. ip->line[0] = ip->opc[0] = '\0';
  471. ip->state = ONLY_OPC;
  472. for (i = 0; i < MAXOP; i++) ip->op[i][0] = '\0';
  473. return ip;
  474. }
  475. oldinstr(ip)
  476. instr_p ip;
  477. {
  478. ip->fw = instr_pool;
  479. instr_pool = ip;
  480. }
  481. /* Debugging stuff */
  482. badassertion(file,line)
  483. char *file;
  484. unsigned line;
  485. {
  486. fprintf(stderr,"assertion failed file %s, line %u\n",file,line);
  487. error("assertion");
  488. }
  489. /* VARARGS1 */
  490. error(s,a)
  491. char *s,*a;
  492. {
  493. fprintf(stderr,s,a);
  494. fprintf(stderr,"\n");
  495. _cleanup();
  496. abort();
  497. exit(-1);
  498. }
  499. /* Low level routines */
  500. bool op_separator(ip)
  501. instr_p ip;
  502. {
  503. skip_white(ip);
  504. if (*(ip->rest_line) == OP_SEPARATOR) {
  505. ip->rest_line++;
  506. return TRUE;
  507. } else {
  508. return FALSE;
  509. }
  510. }
  511. bool well_shaped(opc)
  512. char *opc;
  513. {
  514. return is_letter(opc[0]);
  515. }
  516. bool is_letter(c)
  517. {
  518. return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
  519. }
  520. /* is_white(c) : turned into a macro, see beginning of file */