2 static char rcsid[] = "$Id: peephole.c,v 2.17 1994/06/24 10:40:38 ceriel Exp $";
20 * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
21 * See the copyright notice in the ACK home directory, in the file "Copyright".
23 * Author: Hans van Staveren
26 #undef CHK_HASH /* print numbers patterns are hashed to */
31 #define ILLHASH 0177777
32 short pathash[256]; /* table of indices into pattern[] */
34 int opind = 0; /* second index of next matrix */
35 byte transl[op_plast-op_pfirst+1][3] = {
36 /* LLP */ { op_LLP, op_lol, op_ldl },
37 /* LEP */ { op_LEP, op_loe, op_lde },
38 /* SLP */ { op_SLP, op_stl, op_sdl },
39 /* SEP */ { op_SEP, op_ste, op_sde }
42 opcheck(bp) register byte *bp; {
44 if (((*bp)&BMASK) >= op_pfirst)
45 *bp = transl[((*bp)&BMASK)-op_pfirst][opind];
49 * The hashing method used is believed to be reasonably efficient.
50 * A minor speed improvement could be obtained by keeping a boolean
51 * array telling which opcode has any patterns starting with it.
52 * Currently only about one third of the opcodes actually have a
53 * pattern starting with it, but they are the most common ones.
54 * Estimated improvement possible: about 2%
59 register byte *bp,*tp;
61 unsigned short hashvalue;
65 if (pointersize == wordsize)
67 else if (pointersize == 2*wordsize)
69 index = lastind; /* set by mktab */
76 i |= (*tp++&BMASK)<<8;
82 if ((*tp++&BMASK)==BMASK)
87 i |= (*tp++&BMASK)<<8;
91 if ((*tp++&BMASK)==BMASK)
96 * Now the special opcodes are filled
97 * in properly, we can hash the pattern
103 default: /* 3 or more */
104 hashvalue = (hashvalue<<4)^(*tp++&BMASK);
106 hashvalue = (hashvalue<<4)^(*tp++&BMASK);
108 hashvalue = (hashvalue<<4)^(*tp++&BMASK);
110 assert(hashvalue!= ILLHASH);
112 index = (bp[PO_NEXT]&BMASK)|(bp[PO_NEXT+1]<<8);
113 bp[PO_HASH] = hashvalue>>8;
115 bp[PO_NEXT] = pathash[hashvalue]&BMASK;
116 bp[PO_NEXT+1] = pathash[hashvalue]>>8;
117 pathash[hashvalue] = i;
119 fprintf(stderr,"%d\n",hashvalue);
125 static bool phashed = FALSE;
135 register num_p *npp,np;
139 madeopt = basicblock(&instrs);
140 for (npp=curpro.numhash;npp< &curpro.numhash[NNUMHASH]; npp++)
141 for (np = *npp; np != (num_p) 0; np=np->n_next) {
142 if (! np->n_line) continue;
143 if(np->n_line->l_next == (line_p) 0)
145 instr = np->n_line->l_next->l_instr&BMASK;
146 if (instr == op_lab || instr == op_bra)
147 np->n_repl = np->n_line->l_next->l_a.la_np;
149 if (basicblock(&np->n_line->l_next))
155 offset oabs(off) offset off; {
157 return(off >= 0 ? off : -off);
160 line_p repline(ev,patlen) eval_t ev; {
166 assert(ev.e_typ != EV_UNDEF);
169 if ((short) ev.e_v.e_con == ev.e_v.e_con) {
170 if (CANMINI((short) ev.e_v.e_con))
171 lp = newline((short) (ev.e_v.e_con)+Z_OPMINI);
173 lp = newline(OPSHORT);
174 lp->l_a.la_short = (short) ev.e_v.e_con;
177 lp = newline(OPOFFSET);
178 lp->l_a.la_offset = ev.e_v.e_con;
182 lp = newline(OPNUMLAB);
183 lp->l_a.la_np = ev.e_v.e_np;
185 default: /* fragment + offset */
187 * There is a slight problem here, because we have to
188 * map fragment+offset to symbol+offset.
189 * Fortunately the fragment we have must be the fragment
190 * of one of the symbols in the matchpattern.
191 * So a short search should do the job.
194 for (iap= &iargs[patlen-1]; iap >= iargs; iap--)
195 if (iap->ia_ev.e_typ == ev.e_typ) {
197 * Although lint complains, diff is not used
200 * The proof is left as an exercise to the
203 newdiff = oabs(iap->ia_sp->s_value-ev.e_v.e_con);
204 if (sp==(sym_p) 0 || newdiff < diff) {
209 assert(sp != (sym_p) 0);
211 lp = newline(OPSYMBOL);
214 diff = ev.e_v.e_con - sp->s_value;
215 if ((short) diff == diff) {
216 lp = newline(OPSVAL);
217 lp->l_a.la_sval.lasv_short = (short) diff;
218 lp->l_a.la_sval.lasv_sp = sp;
220 lp = newline(OPLVAL);
221 lp->l_a.la_lval.lalv_offset = diff;
222 lp->l_a.la_lval.lalv_sp = sp;
229 offset rotate(w,amount) offset w,amount; {
230 offset highmask,lowmask;
235 highmask = (offset)(-1) << amount;
238 highmask &= wordsize==2 ? 0xFFFF : 0xFF;
239 return(((w<<amount)&highmask)|((w>>(8*wordsize-amount))&lowmask));
242 eval_t undefres = { EV_UNDEF };
244 eval_t compute(pexp) register expr_p pexp; {
245 eval_t leaf1,leaf2,res;
250 switch(nparam[pexp->ex_operator]) {
254 leaf2 = compute(&enodes[pexp->ex_rnode]);
255 if (leaf2.e_typ == EV_UNDEF ||
256 nonumlab[pexp->ex_operator] && leaf2.e_typ == EV_NUMLAB ||
257 onlyconst[pexp->ex_operator] && leaf2.e_typ != EV_CONST)
260 leaf1 = compute(&enodes[pexp->ex_lnode]);
261 if (leaf1.e_typ == EV_UNDEF ||
262 nonumlab[pexp->ex_operator] && leaf1.e_typ == EV_NUMLAB ||
263 onlyconst[pexp->ex_operator] && leaf1.e_typ != EV_CONST)
269 res.e_typ = EV_CONST;
271 switch(pexp->ex_operator) {
275 res.e_v.e_con = (offset) pexp->ex_lnode;
278 return(iargs[pexp->ex_lnode - 1].ia_ev);
280 if (leaf1.e_typ != leaf2.e_typ)
282 if (leaf1.e_typ == EV_NUMLAB) {
283 if (leaf1.e_v.e_np == leaf2.e_v.e_np)
287 if (leaf1.e_v.e_con == leaf2.e_v.e_con)
291 if (leaf1.e_typ != leaf2.e_typ) {
295 if (leaf1.e_typ == EV_NUMLAB) {
296 if (leaf1.e_v.e_np != leaf2.e_v.e_np)
300 if (leaf1.e_v.e_con != leaf2.e_v.e_con)
304 if (leaf1.e_typ != leaf2.e_typ)
306 res.e_v.e_con = leaf1.e_v.e_con > leaf2.e_v.e_con;
309 if (leaf1.e_typ != leaf2.e_typ)
311 res.e_v.e_con = leaf1.e_v.e_con >= leaf2.e_v.e_con;
314 if (leaf1.e_typ != leaf2.e_typ)
316 res.e_v.e_con = leaf1.e_v.e_con < leaf2.e_v.e_con;
319 if (leaf1.e_typ != leaf2.e_typ)
321 res.e_v.e_con = leaf1.e_v.e_con <= leaf2.e_v.e_con;
324 if (leaf1.e_v.e_con != 0)
326 leaf2 = compute(&enodes[pexp->ex_rnode]);
327 if (leaf2.e_typ != EV_CONST)
331 if (leaf1.e_v.e_con == 0)
333 leaf2 = compute(&enodes[pexp->ex_rnode]);
334 if (leaf2.e_typ != EV_CONST)
338 res.e_v.e_con = leaf1.e_v.e_con | leaf2.e_v.e_con;
341 res.e_v.e_con = leaf1.e_v.e_con ^ leaf2.e_v.e_con;
344 res.e_v.e_con = leaf1.e_v.e_con & leaf2.e_v.e_con;
347 res.e_v.e_con = leaf1.e_v.e_con * leaf2.e_v.e_con;
350 res.e_v.e_con = leaf1.e_v.e_con / leaf2.e_v.e_con;
353 res.e_v.e_con = leaf1.e_v.e_con % leaf2.e_v.e_con;
356 res.e_v.e_con = leaf1.e_v.e_con << leaf2.e_v.e_con;
359 res.e_v.e_con = leaf1.e_v.e_con >> leaf2.e_v.e_con;
362 res.e_v.e_con = -leaf1.e_v.e_con;
365 res.e_v.e_con = !leaf1.e_v.e_con;
368 res.e_v.e_con = ~leaf1.e_v.e_con;
371 if (leaf1.e_typ >= EV_FRAG) {
372 if (leaf2.e_typ >= EV_FRAG)
374 res.e_typ = leaf1.e_typ;
376 res.e_typ = leaf2.e_typ;
377 res.e_v.e_con = leaf1.e_v.e_con + leaf2.e_v.e_con;
380 if (leaf1.e_typ >= EV_FRAG) {
381 if (leaf2.e_typ == EV_CONST)
382 res.e_typ = leaf1.e_typ;
383 else if (leaf2.e_typ != leaf1.e_typ)
385 } else if (leaf2.e_typ >= EV_FRAG)
387 res.e_v.e_con = leaf1.e_v.e_con - leaf2.e_v.e_con;
390 res.e_v.e_con = pointersize;
393 res.e_v.e_con = wordsize;
396 res.e_v.e_con = !inreg(leaf1.e_v.e_con);
399 leaf1 = compute(&enodes[pexp->ex_lnode]);
400 res.e_v.e_con = leaf1.e_typ != EV_UNDEF;
403 res.e_v.e_con = (leaf1.e_v.e_con ^ leaf2.e_v.e_con) >= 0;
406 if ((sp = iargs[pexp->ex_lnode - 1].ia_sp) != (sym_p) 0 &&
407 sp->s_rom != (offset *) 0) {
408 leaf2 = compute(&enodes[pexp->ex_rnode]);
409 if (leaf2.e_typ != EV_CONST ||
410 leaf2.e_v.e_con < 0 ||
411 leaf2.e_v.e_con >= MAXROM)
413 res.e_v.e_con = sp->s_rom[(int)(leaf2.e_v.e_con)];
419 for (i=leaf2.e_v.e_con - 1;i < 8*sizeof(offset); i++)
421 res.e_v.e_con = (leaf1.e_v.e_con&mask) == 0 ||
422 (leaf1.e_v.e_con&mask) == mask;
426 for (i=leaf2.e_v.e_con;i < 8*sizeof(offset); i++)
428 res.e_v.e_con = (leaf1.e_v.e_con&mask) == 0;
431 res.e_v.e_con = rotate(leaf1.e_v.e_con,leaf2.e_v.e_con);
438 extern bool special();
441 bool tryrepl(lpp,bp,patlen)
446 int rpllen,instr,rplval;
448 line_p replacement,*rlpp,tp;
450 rpllen = *bp++&BMASK;
451 if (rpllen == BMASK) {
452 rpllen = *bp++&BMASK;
453 rpllen |= (*bp++&BMASK)<<8;
456 if (rpllen == 1 && *bp == 0)
457 return(special(lpp,bp+1,patlen));
459 replacement = (line_p) 0;
463 rplval = *bp++&BMASK;
464 if (rplval == BMASK) {
465 rplval = (*bp++&BMASK);
466 rplval |= (*bp++&BMASK)<<8;
469 lp = repline(compute(&enodes[rplval]),patlen);
474 * One replacement instruction is generated,
475 * link in list and proceed with the next one.
479 lp->l_a.la_np->n_line = lp;
486 * Replace instructions matched by the created replacement
490 OPTIM((bp[0]&BMASK)|(bp[1]&BMASK)<<8);
491 for (lp= *lpp;patlen>0;patlen--,tp=lp,lp=lp->l_next)
493 tp->l_next = (line_p) 0;
497 while ( lp != (line_p) 0 ) {
505 bool trypat(lpp,bp,len)
515 patlen = *bp++&BMASK;
516 if (patlen == BMASK) {
517 patlen = *bp++&BMASK;
518 patlen |= (*bp++&BMASK)<<8;
529 * Length is ok, now check opcodes
532 for (i=0,lp= *lpp;i<patlen && lp != (line_p) 0;i++,lp=lp->l_next)
533 if (lp->l_instr != *bp++)
539 * opcodes are also correct, now comes the hard part
542 for(i=0,lp= *lpp,iap= iargs; i<patlen;i++,iap++,lp=lp->l_next) {
543 switch(lp->l_optyp) {
545 iap->ia_ev.e_typ = EV_UNDEF;
548 iap->ia_ev.e_typ = EV_CONST;
549 iap->ia_ev.e_v.e_con = (lp->l_optyp&BMASK)-Z_OPMINI;
552 iap->ia_ev.e_typ = EV_CONST;
553 iap->ia_ev.e_v.e_con = lp->l_a.la_short;
557 iap->ia_ev.e_typ = EV_CONST;
558 iap->ia_ev.e_v.e_con = lp->l_a.la_offset;
562 iap->ia_ev.e_typ = EV_NUMLAB;
563 iap->ia_ev.e_v.e_np = lp->l_a.la_np;
566 iap->ia_ev.e_typ = lp->l_a.la_sp->s_frag;
567 iap->ia_sp = lp->l_a.la_sp;
568 iap->ia_ev.e_v.e_con = lp->l_a.la_sp->s_value;
571 iap->ia_ev.e_typ = lp->l_a.la_sval.lasv_sp->s_frag;
572 iap->ia_sp = lp->l_a.la_sval.lasv_sp;
573 iap->ia_ev.e_v.e_con = lp->l_a.la_sval.lasv_sp->s_value + lp->l_a.la_sval.lasv_short;
577 iap->ia_ev.e_typ = lp->l_a.la_lval.lalv_sp->s_frag;
578 iap->ia_sp = lp->l_a.la_lval.lalv_sp;
579 iap->ia_ev.e_v.e_con = lp->l_a.la_lval.lalv_sp->s_value + lp->l_a.la_lval.lalv_offset;
587 i |= (*bp++&BMASK)<<8;
590 /* there is a condition */
591 result = compute(&enodes[i]);
592 if (result.e_typ != EV_CONST || result.e_v.e_con == 0)
595 return(tryrepl(lpp,bp,patlen));
599 basicblock(alpp) line_p *alpp; {
600 register line_p *lpp,lp;
601 unsigned short hash[3];
609 lpp = alpp; madeopt = FALSE;
610 while ((*lpp) != (line_p) 0 && ((*lpp)->l_instr&BMASK) != op_lab) {
613 hash[0] = lp->l_instr&BMASK;
615 if (lp != (line_p) 0) {
616 hash[1] = (hash[0]<<4)^(lp->l_instr&BMASK);
618 if (lp != (line_p) 0)
619 hash[2] = (hash[1]<<4)^(lp->l_instr&BMASK);
628 * hashvalues computed. Try for longest pattern first
632 index = pathash[hash[i]&BMASK];
634 bp = &pattern[index];
635 if((bp[PO_HASH]&BMASK) == (hash[i]>>8))
636 if(trypat(lpp,&bp[PO_MATCH],i+1)) {
639 i = 0; /* dirty way of double break */
642 index=(bp[PO_NEXT]&BMASK)|(bp[PO_NEXT+1]<<8);
648 /* probably loop in table */
649 fprintf(stderr, "Warning: possible loop in patterns; call an expert\n");
650 next = &((*lpp)->l_next);
659 while ((lp = *lpp) != (line_p) 0 && (lp->l_instr&BMASK) != op_lab) {
660 line_p b_repl, e_repl;
663 if ((cnt = (lp->l_instr & BMASK)) != op_loc && cnt != op_ldc) {
668 cnt = repl_mul(lp, &b_repl, &e_repl);
671 if (cnt > 0 && cnt <= repl_muls) {
673 e_repl->l_next = lp->l_next->l_next;
676 lpp = &e_repl->l_next;
680 while (b_repl != (line_p) 0) {
681 line_p n = b_repl->l_next;
697 register line_p next = lp->l_next;
706 if (! next) return 0;
707 if ((ins = (next->l_instr & BMASK)) != op_mli && ins != op_mlu) {
710 switch(next->l_optyp) {
714 sz = next->l_a.la_short;
718 sz = next->l_a.la_offset;
722 sz = (next->l_optyp & BMASK) - Z_OPMINI;
725 if (ins == op_loc && sz != wordsize) return 0;
726 if (ins == op_ldc && sz != 2*wordsize) return 0;
727 if (! repl_longmuls && sz != wordsize) return 0;
728 switch(lp->l_optyp) {
730 n = (long) lp->l_a.la_short;
734 n = lp->l_a.la_offset;
738 n = (long)((lp->l_optyp & BMASK) - Z_OPMINI);
742 #define newinstr(res, opcode, val) (*(res) = newline((short)(val)+Z_OPMINI), (*(res))->l_instr = (opcode))
745 /* first find "0*1*$" in n */
746 for (n1 = 0; n & 1; n>>=1) ++n1; /* count "1" bits */
748 for (n0 = 0; !(n & 1); n>>=1) /* count "0" bits */
755 newinstr(b, op_loc, n0); b = &((*b)->l_next);
756 newinstr(b, op_slu, sz); b = &((*b)->l_next);
759 } else if (n1 == 1) {
761 newinstr(b, op_dup, sz); b = &((*b)->l_next);
765 newinstr(b, op_exg, sz); b = &((*b)->l_next);
766 newinstr(b, op_dup, 2*sz); b = &((*b)->l_next);
767 newinstr(b, op_asp, sz); b = &((*b)->l_next);
768 newinstr(b, op_adu, sz); b = &((*b)->l_next);
769 newinstr(b, op_exg, sz); b = &((*b)->l_next);
773 newinstr(b, op_loc, n0+n1); b = &((*b)->l_next);
774 newinstr(b, op_slu, sz); b = &((*b)->l_next);
779 newinstr(b, op_dup, sz); b = &((*b)->l_next);
780 if (sz == wordsize) {
781 newinstr(b, op_loc, 0); b = &((*b)->l_next);
784 newinstr(b, op_ldc, 0); b = &((*b)->l_next);
786 newinstr(b, op_exg, sz); b = &((*b)->l_next);
790 newinstr(b, op_exg, sz); b = &((*b)->l_next);
791 newinstr(b, op_dup, 2*sz); b = &((*b)->l_next);
792 newinstr(b, op_asp, sz); b = &((*b)->l_next);
794 newinstr(b, op_sbu, sz); b = &((*b)->l_next);
795 newinstr(b, op_exg, sz); b = &((*b)->l_next);
798 newinstr(b, op_loc, n1); b = &((*b)->l_next);
799 newinstr(b, op_slu, sz); b = &((*b)->l_next);
801 newinstr(b, op_exg, sz); b = &((*b)->l_next);
802 newinstr(b, op_dup, 2*sz); b = &((*b)->l_next);
803 newinstr(b, op_asp, sz); b = &((*b)->l_next);
804 newinstr(b, op_adu, sz); b = &((*b)->l_next);
805 newinstr(b, op_exg, sz); b = &((*b)->l_next);
809 newinstr(b, op_loc, n0); b = &((*b)->l_next);
810 newinstr(b, op_slu, sz); b = &((*b)->l_next);
815 newinstr(b, op_asp, sz);
818 newinstr(b, sz == wordsize ? op_loc : op_ldc, 0);
821 return retval == 0 ? 1 : retval;