1 /*-------------------------------------------------------------------------
3 pcodepeep.c - post code generation
4 Written By - Scott Dattalo scott@dattalo.com
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19 -------------------------------------------------------------------------*/
23 #include "common.h" // Include everything in the SDCC src directory
31 pCodeOp *newpCodeOpWild(int id, pCodePeep *pcp, pCodeOp *subtype);
32 pCode *newpCodeWild(int pCodeID, pCodeOp *optional_operand, pCodeOp *optional_label);
33 pCode * findNextInstruction(pCode *pc);
34 char *Safe_strdup(char *str);
37 /****************************************************************/
39 * rootRules - defined in SDCCpeep.c
40 * This is a pointer to the (parsed) peephole rules that are
41 * defined in peep.def.
44 extern peepRule *rootRules;
47 /****************************************************************/
48 /****************************************************************/
56 typedef struct pCodePeepSnippets
63 static pCodePeepSnippets *peepSnippets=NULL;
66 void printpCodeString(FILE *of, pCode *pc, int max)
70 while(pc && (i++<max)) {
76 /*-----------------------------------------------------------------*/
77 /* _DLL * DLL_append */
79 /* Append a _DLL object to the end of a _DLL (doubly linked list) */
80 /* If The list to which we want to append is non-existant then one */
81 /* is created. Other wise, the end of the list is sought out and */
82 /* a new DLL object is appended to it. In either case, the void */
83 /* *data is added to the newly created DLL object. */
84 /*-----------------------------------------------------------------*/
86 static void * DLL_append(_DLL *list, _DLL *next)
91 /* If there's no list, then create one: */
93 next->next = next->prev = NULL;
98 /* Search for the end of the list. */
103 /* Now append the new DLL object */
114 /*-----------------------------------------------------------------
116 pCode peephole optimization
119 The pCode "peep hole" optimization is not too unlike the peep hole
120 optimization in SDCCpeeph.c. The major difference is that here we
121 use pCode's whereas there we use ASCII strings. The advantage with
122 pCode's is that we can ascertain flow information in the instructions
126 <FIX ME> - elaborate...
128 -----------------------------------------------------------------*/
131 /*-----------------------------------------------------------------*/
133 /*-----------------------------------------------------------------*/
134 int pCodePeepCompare(pCode *pc, pCodePeep *pcp)
139 for( pcto=pcp->target; pcto; pcto=pcto->next) {
141 pcfrom = findNextInstruction(pcfrom);
144 (PCI(pcfrom)->op == PCI(pcto)->op ||
145 PCI(pcto)->op == POC_WILD))
152 /*-----------------------------------------------------------------*/
154 /*-----------------------------------------------------------------*/
155 void pCodePeepSearch(pCodePeep *snippet)
163 /* compare the chain to the pCode that we've
164 got so far. If a match is found, then replace
167 for(pb = the_pFile->pbHead; pb; pb = pb->next) {
168 for(pc = pb->pcHead; pc; pc = pc->next) {
169 pCodePeepCompare(pc,snippet);
177 pBlock *pBlockAppend(pBlock *pb1, pBlock *pb2)
194 void pCodePeepInit(void)
199 pCodePeepSnippets *pcps;
201 /* Declare a peep code snippet */
202 /* <FIXME> do I really need a separate struct just to DLL the snippets? */
203 /* e.g. I could put the DLL into the pCodePeep structure */
204 pcps = Safe_calloc(1,sizeof(pCodePeepSnippets));
205 pcp = pcps->peep = Safe_calloc(1,sizeof(pCodePeep));
206 peepSnippets = DLL_append((_DLL*)peepSnippets,(_DLL*)pcps);
209 pb = newpCodeChain(NULL, 'W', newpCode(POC_MOVWF, newpCodeOpWild(0,pcp,newpCodeOp(NULL,PO_GPR_REGISTER))) );
210 addpCode2pBlock( pb, newpCode(POC_MOVFW, newpCodeOpWild(0,pcp,newpCodeOp(NULL,PO_GPR_REGISTER))) );
214 pcp->replace = newpCodeChain(NULL, 'W',newpCode(POC_MOVWF, newpCodeOpWild(0,pcp,newpCodeOp(NULL,PO_GPR_REGISTER))) );
216 /* Allocate space to store pointers to the wildcard variables */
218 pcp->vars = Safe_calloc(pcp->nvars, sizeof(char *));
219 pcp->nwildpCodes = 0;
220 pcp->wildpCodes = NULL;
222 pcp->postFalseCond = PCC_Z;
223 pcp->postTrueCond = PCC_NONE;
225 fprintf(stderr,"Peep rule\nTarget:\n");
226 printpCodeString(stderr,pcp->target->pcHead, 10);
227 fprintf(stderr,"Replaced with:\n");
228 printpCodeString(stderr,pcp->replace->pcHead, 10);
230 /* Now for another peep example */
231 pcps = Safe_calloc(1,sizeof(pCodePeepSnippets));
232 pcp = pcps->peep = Safe_calloc(1,sizeof(pCodePeep));
233 peepSnippets = DLL_append((_DLL*)peepSnippets,(_DLL*)pcps);
240 pcwb = newpCodeOpWild(0,pcp,newpCodeOpBit(NULL,-1));
241 pb = newpCodeChain(NULL, 'W',newpCode(POC_BTFSC,pcwb));
243 pcl = newpCodeOpLabel(-1);
244 pcw = newpCodeOpWild(1, pcp, pcl);
245 addpCode2pBlock( pb, newpCode(POC_GOTO, pcw));
246 addpCode2pBlock( pb, newpCodeWild(0,NULL,NULL));
247 addpCode2pBlock( pb, newpCodeWild(1,NULL,pcw));
252 pb = newpCodeChain(NULL, 'W',newpCode(POC_BTFSS, pcwb));
253 addpCode2pBlock( pb, newpCodeWild(0,NULL,NULL));
254 addpCode2pBlock( pb, newpCodeWild(1,NULL,pcw));
258 /* Allocate space to store pointers to the wildcard variables */
260 pcp->vars = Safe_calloc(pcp->nvars, sizeof(char *));
261 pcp->nwildpCodes = 2;
262 pcp->wildpCodes = Safe_calloc(pcp->nwildpCodes, sizeof(pCode *));
264 pcp->postFalseCond = PCC_NONE;
265 pcp->postTrueCond = PCC_NONE;
279 /* Now for another peep example */
280 pcps = Safe_calloc(1,sizeof(pCodePeepSnippets));
281 pcp = pcps->peep = Safe_calloc(1,sizeof(pCodePeep));
282 peepSnippets = DLL_append((_DLL*)peepSnippets,(_DLL*)pcps);
287 pcw = newpCodeOpWild(0,pcp,newpCodeOp(NULL,PO_GPR_REGISTER));
289 pb = newpCodeChain(NULL, 'W', newpCode(POC_MOVWF, pcw));
290 addpCode2pBlock( pb, newpCode(POC_MOVWF, pcw));
294 pb = newpCodeChain(NULL, 'W',newpCode(POC_MOVWF, pcw));
298 /* Allocate space to store pointers to the wildcard variables */
300 pcp->vars = Safe_calloc(pcp->nvars, sizeof(char *));
301 pcp->nwildpCodes = 0;
302 pcp->wildpCodes = NULL;
304 pcp->postFalseCond = PCC_NONE;
305 pcp->postTrueCond = PCC_NONE;
313 /*-----------------------------------------------------------------*/
314 /* pCodeSearchCondition - Search a pCode chain for a 'condition' */
316 /* return conditions */
317 /* 1 - The Condition was found for a pCode's input */
318 /* 0 - No matching condition was found for the whole chain */
319 /* -1 - The Condition was found for a pCode's output */
321 /*-----------------------------------------------------------------*/
322 int pCodeSearchCondition(pCode *pc, unsigned int cond)
327 /* If we reach a function end (presumably an end since we most
328 probably began the search in the middle of a function), then
329 the condition was not found. */
330 if(pc->type == PC_FUNCTION)
333 if(pc->type == PC_OPCODE) {
334 if(PCI(pc)->inCond & cond)
336 if(PCI(pc)->outCond & cond)
345 /*-----------------------------------------------------------------*/
346 /* pCodePeepMatchLine - Compare source and destination pCodes to */
347 /* see they're the same. */
348 /*-----------------------------------------------------------------*/
349 int pCodePeepMatchLine(pCodePeep *peepBlock, pCode *pcs, pCode *pcd)
351 int index; // index into wild card arrays
353 if(pcs->type == pcd->type) {
355 if(pcs->type == PC_OPCODE) {
357 /* If the opcodes don't match then the line doesn't match */
358 if(PCI(pcs)->op != PCI(pcd)->op)
361 fprintf(stderr,"%s comparing\n",__FUNCTION__);
362 pcs->print(stderr,pcs);
363 pcd->print(stderr,pcd);
365 /* Compare the operands */
367 if (PCI(pcd)->pcop->type == PO_WILD) {
368 index = PCOW(PCI(pcd)->pcop)->id;
370 fprintf(stderr,"destination is wild\n");
371 #ifdef DEBUG_PCODEPEEP
372 if (index > peepBlock->nvars) {
373 fprintf(stderr,"%s - variables exceeded\n",__FUNCTION__);
377 PCOW(PCI(pcd)->pcop)->matched = PCI(pcs)->pcop;
381 if(PCI(pcs)->pcop->type == PO_GPR_TEMP)
382 n = PCOR(PCI(pcs)->pcop)->r->name;
384 n = PCI(pcs)->pcop->name;
386 if(peepBlock->vars[index])
387 return (strcmp(peepBlock->vars[index],n) == 0);
389 peepBlock->vars[index] = n; //PCI(pcs)->pcop->name;
395 /* The pcd has no operand. Lines match if pcs has no operand either*/
396 return (PCI(pcs)->pcop == NULL);
401 if((pcd->type == PC_WILD) && (pcs->type == PC_OPCODE)) {
405 index = PCW(pcd)->id;
407 fprintf(stderr,"%s comparing wild cards\n",__FUNCTION__);
408 pcs->print(stderr,pcs);
409 pcd->print(stderr,pcd);
411 peepBlock->wildpCodes[PCW(pcd)->id] = pcs;
413 /* Check for a label associated with this wild pCode */
414 // If the wild card has a label, make sure the source code does too.
415 if(PCW(pcd)->label) {
419 labindex = PCOW(PCW(pcd)->label)->id;
420 if(peepBlock->vars[labindex] == NULL) {
421 // First time to encounter this label
422 peepBlock->vars[labindex] = PCL(pcs->label->pc)->label;
423 fprintf(stderr,"first time for a label\n");
425 if(strcmp(peepBlock->vars[labindex],PCL(pcs->label->pc)->label) != 0) {
426 fprintf(stderr,"labels don't match\n");
429 fprintf(stderr,"matched a label\n");
434 if(PCW(pcd)->operand) {
435 PCOW(PCI(pcd)->pcop)->matched = PCI(pcs)->pcop;
436 if(peepBlock->vars[index]) {
437 int i = (strcmp(peepBlock->vars[index],PCI(pcs)->pcop->name) == 0);
439 fprintf(stderr," (matched)\n");
441 fprintf(stderr," (no match: wild card operand mismatch\n");
442 fprintf(stderr," peepblock= %s, pcodeop= %s\n",
443 peepBlock->vars[index],
444 PCI(pcs)->pcop->name);
448 peepBlock->vars[index] = PCI(pcs)->pcop->name;
453 pcs = findNextInstruction(pcs->next);
455 fprintf(stderr," (next to match)\n");
456 pcs->print(stderr,pcs);
459 return 1; /* wild card matches */
465 /*-----------------------------------------------------------------*/
466 /*-----------------------------------------------------------------*/
467 void pCodePeepClrVars(pCodePeep *pcp)
472 for(i=0;i<pcp->nvars; i++)
477 /*-----------------------------------------------------------------*/
478 /*-----------------------------------------------------------------*/
479 void pCodeInsertAfter(pCode *pc1, pCode *pc2)
485 pc2->next = pc1->next;
487 pc1->next->prev = pc2;
494 /*-----------------------------------------------------------------*/
495 /* pCodeOpCopy - copy a pcode operator */
496 /*-----------------------------------------------------------------*/
497 static pCodeOp *pCodeOpCopy(pCodeOp *pcop)
499 pCodeOp *pcopnew=NULL;
507 pcopnew = Safe_calloc(1,sizeof(pCodeOpBit) );
508 PCOB(pcopnew)->bit = PCOB(pcop)->bit;
509 PCOB(pcopnew)->inBitSpace = PCOB(pcop)->inBitSpace;
514 /* Here we expand the wild card into the appropriate type: */
515 /* By recursively calling pCodeOpCopy */
516 if(PCOW(pcop)->matched)
517 pcopnew = pCodeOpCopy(PCOW(pcop)->matched);
520 pcopnew = pCodeOpCopy(PCOW(pcop)->subtype);
521 pcopnew->name = Safe_strdup(PCOW(pcop)->pcp->vars[PCOW(pcop)->id]);
522 fprintf(stderr,"copied a wild op named %s\n",pcopnew->name);
529 pcopnew = Safe_calloc(1,sizeof(pCodeOpLabel) );
530 PCOLAB(pcopnew)->key = PCOLAB(pcop)->key;
535 pcopnew = Safe_calloc(1,sizeof(pCodeOpLit) );
536 PCOL(pcopnew)->lit = PCOL(pcop)->lit;
539 case PO_GPR_REGISTER:
541 case PO_SFR_REGISTER:
550 pcopnew = Safe_calloc(1,sizeof(pCodeOp) );
554 pcopnew->type = pcop->type;
555 pcopnew->name = Safe_strdup(pcop->name);
561 /*-----------------------------------------------------------------*/
562 /* pCodeCopy - copy a pcode */
563 /*-----------------------------------------------------------------*/
564 static pCode *pCodeCopy(pCode *pc)
569 pcnew = newpCode(pc->type,pc->pcop);
572 /*-----------------------------------------------------------------*/
573 /*-----------------------------------------------------------------*/
574 void pCodeDeleteChain(pCode *f,pCode *t)
579 fprintf(stderr,"delete pCode:\n");
587 /*-----------------------------------------------------------------*/
588 /*-----------------------------------------------------------------*/
589 int pCodePeepMatchRule(pCode *pc)
591 pCodePeep *peepBlock;
596 peeprules = (_DLL *)peepSnippets;
599 peepBlock = ((pCodePeepSnippets*)peeprules)->peep;
600 pCodePeepClrVars(peepBlock);
603 pct = peepBlock->target->pcHead;
607 if(! (matched = pCodePeepMatchLine(peepBlock, pcin,pct)))
610 pcin = findNextInstruction(pcin->next);
613 fprintf(stderr," matched\n");
615 fprintf(stderr," end of code\n");
617 fprintf(stderr," end of rule\n");
620 if(matched && pcin) {
622 /* So far we matched the rule up to the point of the conditions .
623 * In other words, all of the opcodes match. Now we need to see
624 * if the post conditions are satisfied.
625 * First we check the 'postFalseCond'. This means that we check
626 * to see if any of the subsequent pCode's in the pCode chain
627 * following the point just past where we have matched depend on
628 * the `postFalseCond' as input then we abort the match
630 fprintf(stderr," matched rule so far, now checking conditions\n");
631 if (peepBlock->postFalseCond &&
632 (pCodeSearchCondition(pcin,peepBlock->postFalseCond) > 0) )
636 if(matched && pcin) {
642 /* We matched a rule! Now we have to go through and remove the
643 inefficient code with the optimized version */
645 fprintf(stderr, "Found a pcode peep match:\nRule:\n");
646 printpCodeString(stderr,peepBlock->target->pcHead,10);
647 fprintf(stderr,"first thing matched\n");
648 pc->print(stderr,pc);
649 fprintf(stderr,"last thing matched\n");
650 pcin->print(stderr,pcin);
652 /* Unlink the original code */
655 pcin->prev = pc->prev;
656 pCodeDeleteChain(pc,pcin);
658 /* Generate the replacement code */
660 pcr = peepBlock->replace->pcHead; // This is the replacement code
663 /* If the replace pcode is an instruction with an operand, */
664 /* then duplicate the operand (and expand wild cards in the process). */
665 if(pcr->type == PC_OPCODE) {
667 pcop = pCodeOpCopy(PCI(pcr)->pcop);
669 pCodeInsertAfter(pc, newpCode(PCI(pcr)->op,pcop));
670 } else if (pcr->type == PC_WILD) {
671 pCodeInsertAfter(pc,peepBlock->wildpCodes[PCW(pcr)->id]);
676 pc->print(stderr,pc);
683 peeprules = peeprules->next;