top.c 13 KB

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