modules/src/em_opt/findworst.c

   1 #ifndef NORCSID
   2 static char rcsidp3[] = "$Id: findworst.c,v 2.8 1994/06/24 11:14:04 ceriel Exp $";
   3 #endif
   4
   5 #include "parser.h"
   6
   7 #define UPDATEWORST(backups) if(backups>mostbackups) mostbackups = backups;
   8
   9 PRIVATE int leftmatch();
  10 PRIVATE int rightmatch();
  11
  12 findworst(patt,repl)
  13         struct mnems patt,repl;
  14 {
  15         /*
  16         /* Find the pattern that requires the most backup of output queue.
  17         /* Let repl be r1 r2 ... rn. All these are already on the output queue.
  18         /* Possibilities in order of most backup first are:
  19         /* a)   pattern of form: p1 .... pb r1 r2 .... rn pc ... pd
  20         /*      i.e. <repl> completely in pattern.
  21         /*      requires a backup of b+n instructions
  22         /*      and a goto to state 0.
  23         /* b)   pattern of form: p1 .... pb r1 r2 .... ri
  24         /*      i.e. a prefix of <repl> ends a pattern.
  25         /*      requires a backup of b+n instructions
  26         /*      and a goto to state 0.
  27         /* c)   pattern of form: ri ri+1 ... rn pc ... pd
  28         /*      i.e. a suffix of <repl> starts a pattern.
  29         /*      requires a backup of j-i+1 instructions and a goto to state 0.
  30         /* d)   pattern of the form: ri ri+1 ... rj
  31         /*      i.e. a substring of <repl> is a complete pattern
  32         /*      requires a backup of j-i+1 instructions and a goto to state 0.
  33         */
  34         int n = repl.m_len;
  35         int diff = patt.m_len - repl.m_len;
  36         int first,i,j;
  37         int s;
  38         int mostbackups = 0;
  39         if(n==0) {
  40                 fprintf(ofile,"\t\tOO_mkrepl(0,%d,%d);\n",diff,maxpattern-1);
  41                 return;
  42         }
  43         for(s=1;s<=higheststate;s++) {
  44                 /* only match complete patterns */
  45                 if(actions[s]==(struct action *)NULL)
  46                         continue;
  47                 /* look for case a */
  48                 if(first=rightmatch(patterns[s],repl,1,n)) {
  49                         UPDATEWORST(first-1+n);
  50                 }
  51                 /* look for case b */
  52                 for(i=n-1;i;i--) {
  53                         if((first=rightmatch(patterns[s],repl,1,i)) &&
  54                            (first+i-1==patterns[s].m_len)) {
  55                                 UPDATEWORST(first-1+n);
  56                         }
  57                 }
  58                 /* look for case c */
  59                 for(i=2;i<=n;i++) {
  60                         if((first=leftmatch(patterns[s],repl,i,n)) &&
  61                            (first==1)) {
  62                                 UPDATEWORST(n-i+1);
  63                         }
  64                 }
  65                 /* look for case d */
  66                 for(i=2;i<=n;i++) {
  67                         for(j=n-1;j>i;j--) {
  68                                 if((first=leftmatch(patterns[s],repl,i,j)) &&
  69                                    (first==1)&&
  70                                    (j-i+1 == patterns[s].m_len)) {
  71                                         UPDATEWORST(n-i+1);
  72                                 }
  73                         }
  74                 }
  75         }
  76         fprintf(ofile,"\t\tOO_mkrepl(%d,%d,%d);\n",n,diff,mostbackups);
  77 }
  78
  79 findfail(state,resout,rescpy,resgto)
  80         int state;
  81         int *resout, *rescpy, *resgto;
  82 {
  83         /*
  84         /* If pattern matching fails in 'state', how many outputs and how many
  85         /* push backs are requires. If pattern is of the form p1 p2 .... pn
  86         /* look for patterns of the form p2 p3 ... pn; then p3 p4 ... pn; etc.
  87         /* The first such match of the form pi pi+1 ... pn requires an output
  88         /* of p1 p2 ... pi-1 and a push back of pn pn-1 ... pi.
  89         */
  90         int s,i;
  91         struct state *p;
  92         int istrans;
  93         int n = patterns[state].m_len;
  94         for(i=2;i<=n;i++) {
  95                 for(s=1;s<=higheststate;s++) {
  96                         /* exclude those on transitions from this state */
  97                         istrans = 0;
  98                         for(p=states[state];p!=(struct state *)NULL;p=p->next)
  99                                 if(s==p->goto_state)
 100                                         istrans++;
 101                         if(istrans)
 102                                 continue;
 103                         if((leftmatch(patterns[s],patterns[state],i,n)==1)&&
 104                                 patterns[s].m_len==(n-i+1)) {
 105                                         *resout = i-1;
 106                                         *rescpy = n-i+1;
 107                                         *resgto = s;
 108                                         return;
 109                                 }
 110                 }
 111         }
 112         *resout = n;
 113         *rescpy = 0;
 114         *resgto = 0;
 115 }
 116
 117 PRIVATE int
 118 leftmatch(patt,repl,i,j)
 119         struct mnems patt,repl;
 120         int i,j;
 121 {
 122         /*
 123         /* Return the first complete match of the mnems <ri,ri+1,..,rj> of
 124         /* 'repl' in the mnems of 'patt'.  Find the leftmost match.
 125         /* Return 0 if fails.
 126         */
 127         int lenrij = j-i+1;
 128         int lastpos = patt.m_len - lenrij + 1;
 129         int k,n;
 130         for(k=1;k<=lastpos;k++) {
 131                 for(n=1;n<=lenrij;n++) {
 132                         if(patt.m_elems[(k+n-1)-1]->op_code != repl.m_elems[(i+n-1)-1]->op_code)
 133                                 break;
 134                 }
 135                 if(n>lenrij) {
 136                         return(k);
 137                 }
 138         }
 139         return(0);
 140 }
 141
 142 PRIVATE int
 143 rightmatch(patt,repl,i,j)
 144         struct mnems patt,repl;
 145         int i,j;
 146 {
 147         /*
 148         /* Return the first complete match of the mnems <ri,ri+1,..,rj> of
 149         /* 'repl' in the mnems of 'patt'.  Find the rightmost match.
 150         /* Return 0 if fails.
 151         */
 152         int lenrij = j-i+1;
 153         int lastpos = patt.m_len - lenrij + 1;
 154         int k,n;
 155         for(k=lastpos;k>=1;k--) {
 156                 for(n=1;n<=lenrij;n++) {
 157                         if(patt.m_elems[(k+n-1)-1]->op_code != repl.m_elems[(i+n-1)-1]->op_code)
 158                                 break;
 159                 }
 160                 if(n>lenrij) {
 161                         return(k);
 162                 }
 163         }
 164         return(0);
 165 }