top.c 13 KB

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