utils/Burg/trim.c

   1 char rcsid_trim[] = "$Id$";
   2
   3 #include <stdio.h>
   4 #include "b.h"
   5 #include "fe.h"
   6
   7 Relation *allpairs;
   8
   9 int trimflag = 0;
  10 int debugTrim = 0;
  11
  12 static void siblings ARGS((int, int));
  13 static void findAllNexts ARGS((void));
  14 static Relation *newAllPairs ARGS((void));
  15
  16 static void
  17 siblings(i, j) int i; int j;
  18 {
  19         int k;
  20         List pl;
  21         DeltaCost Max;
  22         int foundmax;
  23
  24         allpairs[i][j].sibComputed = 1;
  25
  26         if (i == 1) {
  27                 return; /* never trim start symbol */
  28         }
  29         if (i==j) {
  30                 return;
  31         }
  32
  33         ZEROCOST(Max);
  34         foundmax = 0;
  35
  36         for (k = 1; k < max_nonterminal; k++) {
  37                 DeltaCost tmp;
  38
  39                 if (k==i || k==j) {
  40                         continue;
  41                 }
  42                 if (!allpairs[k][i].rule) {
  43                         continue;
  44                 }
  45                 if (!allpairs[k][j].rule) {
  46                         return;
  47                 }
  48                 ASSIGNCOST(tmp, allpairs[k][j].chain);
  49                 MINUSCOST(tmp, allpairs[k][i].chain);
  50                 if (foundmax) {
  51                         if (LESSCOST(Max, tmp)) {
  52                                 ASSIGNCOST(Max, tmp);
  53                         }
  54                 } else {
  55                         foundmax = 1;
  56                         ASSIGNCOST(Max, tmp);
  57                 }
  58         }
  59
  60         for (pl = rules; pl; pl = pl->next) {
  61                 Rule p = (Rule) pl->x;
  62                 Operator op = p->pat->op;
  63                 List oprule;
  64                 DeltaCost Min;
  65                 int foundmin;
  66
  67                 if (!op) {
  68                         continue;
  69                 }
  70                 switch (op->arity) {
  71                 case 0:
  72                         continue;
  73                 case 1:
  74                         if (!allpairs[p->pat->children[0]->num ][ i].rule) {
  75                                 continue;
  76                         }
  77                         foundmin = 0;
  78                         for (oprule = op->table->rules; oprule; oprule = oprule->next) {
  79                                 Rule s = (Rule) oprule->x;
  80                                 DeltaPtr Cx;
  81                                 DeltaPtr Csj;
  82                                 DeltaPtr Cpi;
  83                                 DeltaCost tmp;
  84
  85                                 if (!allpairs[p->lhs->num ][ s->lhs->num].rule
  86                                  || !allpairs[s->pat->children[0]->num ][ j].rule) {
  87                                         continue;
  88                                 }
  89                                 Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
  90                                 Csj= allpairs[s->pat->children[0]->num ][ j].chain;
  91                                 Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
  92                                 ASSIGNCOST(tmp, Cx);
  93                                 ADDCOST(tmp, s->delta);
  94                                 ADDCOST(tmp, Csj);
  95                                 MINUSCOST(tmp, Cpi);
  96                                 MINUSCOST(tmp, p->delta);
  97                                 if (foundmin) {
  98                                         if (LESSCOST(tmp, Min)) {
  99                                                 ASSIGNCOST(Min, tmp);
 100                                         }
 101                                 } else {
 102                                         foundmin = 1;
 103                                         ASSIGNCOST(Min, tmp);
 104                                 }
 105                         }
 106                         if (!foundmin) {
 107                                 return;
 108                         }
 109                         if (foundmax) {
 110                                 if (LESSCOST(Max, Min)) {
 111                                         ASSIGNCOST(Max, Min);
 112                                 }
 113                         } else {
 114                                 foundmax = 1;
 115                                 ASSIGNCOST(Max, Min);
 116                         }
 117                         break;
 118                 case 2:
 119                 /* do first dimension */
 120                 if (allpairs[p->pat->children[0]->num ][ i].rule) {
 121                         foundmin = 0;
 122                         for (oprule = op->table->rules; oprule; oprule = oprule->next) {
 123                                 Rule s = (Rule) oprule->x;
 124                                 DeltaPtr Cx;
 125                                 DeltaPtr Cb;
 126                                 DeltaPtr Csj;
 127                                 DeltaPtr Cpi;
 128                                 DeltaCost tmp;
 129
 130                                 if (allpairs[p->lhs->num ][ s->lhs->num].rule
 131                                  && allpairs[s->pat->children[0]->num ][ j].rule
 132                                  && allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].rule) {
 133                                         Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
 134                                         Csj= allpairs[s->pat->children[0]->num ][ j].chain;
 135                                         Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
 136                                         Cb = allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].chain;
 137                                         ASSIGNCOST(tmp, Cx);
 138                                         ADDCOST(tmp, s->delta);
 139                                         ADDCOST(tmp, Csj);
 140                                         ADDCOST(tmp, Cb);
 141                                         MINUSCOST(tmp, Cpi);
 142                                         MINUSCOST(tmp, p->delta);
 143                                         if (foundmin) {
 144                                                 if (LESSCOST(tmp, Min)) {
 145                                                         ASSIGNCOST(Min, tmp);
 146                                                 }
 147                                         } else {
 148                                                 foundmin = 1;
 149                                                 ASSIGNCOST(Min, tmp);
 150                                         }
 151                                 }
 152                         }
 153                         if (!foundmin) {
 154                                 return;
 155                         }
 156                         if (foundmax) {
 157                                 if (LESSCOST(Max, Min)) {
 158                                         ASSIGNCOST(Max, Min);
 159                                 }
 160                         } else {
 161                                 foundmax = 1;
 162                                 ASSIGNCOST(Max, Min);
 163                         }
 164                 }
 165                 /* do second dimension */
 166                 if (allpairs[p->pat->children[1]->num ][ i].rule) {
 167                         foundmin = 0;
 168                         for (oprule = op->table->rules; oprule; oprule = oprule->next) {
 169                                 Rule s = (Rule) oprule->x;
 170                                 DeltaPtr Cx;
 171                                 DeltaPtr Cb;
 172                                 DeltaPtr Csj;
 173                                 DeltaPtr Cpi;
 174                                 DeltaCost tmp;
 175
 176                                 if (allpairs[p->lhs->num ][ s->lhs->num].rule
 177                                  && allpairs[s->pat->children[1]->num ][ j].rule
 178                                  && allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].rule) {
 179                                         Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
 180                                         Csj= allpairs[s->pat->children[1]->num ][ j].chain;
 181                                         Cpi= allpairs[p->pat->children[1]->num ][ i].chain;
 182                                         Cb = allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].chain;
 183                                         ASSIGNCOST(tmp, Cx);
 184                                         ADDCOST(tmp, s->delta);
 185                                         ADDCOST(tmp, Csj);
 186                                         ADDCOST(tmp, Cb);
 187                                         MINUSCOST(tmp, Cpi);
 188                                         MINUSCOST(tmp, p->delta);
 189                                         if (foundmin) {
 190                                                 if (LESSCOST(tmp, Min)) {
 191                                                         ASSIGNCOST(Min, tmp);
 192                                                 }
 193                                         } else {
 194                                                 foundmin = 1;
 195                                                 ASSIGNCOST(Min, tmp);
 196                                         }
 197                                 }
 198                         }
 199                         if (!foundmin) {
 200                                 return;
 201                         }
 202                         if (foundmax) {
 203                                 if (LESSCOST(Max, Min)) {
 204                                         ASSIGNCOST(Max, Min);
 205                                 }
 206                         } else {
 207                                 foundmax = 1;
 208                                 ASSIGNCOST(Max, Min);
 209                         }
 210                 }
 211                 break;
 212                 default:
 213                         assert(0);
 214                 }
 215         }
 216         allpairs[i ][ j].sibFlag = foundmax;
 217         ASSIGNCOST(allpairs[i ][ j].sibling, Max);
 218 }
 219
 220 static void
 221 findAllNexts()
 222 {
 223         int i,j;
 224         int last;
 225
 226         for (i = 1; i < max_nonterminal; i++) {
 227                 last = 0;
 228                 for (j = 1; j < max_nonterminal; j++) {
 229                         if (allpairs[i ][j].rule) {
 230                                 allpairs[i ][ last].nextchain = j;
 231                                 last = j;
 232                         }
 233                 }
 234         }
 235         /*
 236         for (i = 1; i < max_nonterminal; i++) {
 237                 last = 0;
 238                 for (j = 1; j < max_nonterminal; j++) {
 239                         if (allpairs[i ][j].sibFlag) {
 240                                 allpairs[i ][ last].nextsibling = j;
 241                                 last = j;
 242                         }
 243                 }
 244         }
 245         */
 246 }
 247
 248 static Relation *
 249 newAllPairs()
 250 {
 251         int i;
 252         Relation *rv;
 253
 254         rv = (Relation*) zalloc(max_nonterminal * sizeof(Relation));
 255         for (i = 0; i < max_nonterminal; i++) {
 256                 rv[i] = (Relation) zalloc(max_nonterminal * sizeof(struct relation));
 257         }
 258         return rv;
 259 }
 260
 261 void
 262 findAllPairs()
 263 {
 264         List pl;
 265         int changes;
 266         int j;
 267
 268         allpairs = newAllPairs();
 269         for (pl = chainrules; pl; pl = pl->next) {
 270                 Rule p = (Rule) pl->x;
 271                 NonTerminalNum rhs = p->pat->children[0]->num;
 272                 NonTerminalNum lhs = p->lhs->num;
 273                 Relation r = &allpairs[lhs ][ rhs];
 274
 275                 if (LESSCOST(p->delta, r->chain)) {
 276                         ASSIGNCOST(r->chain, p->delta);
 277                         r->rule = p;
 278                 }
 279         }
 280         for (j = 1; j < max_nonterminal; j++) {
 281                 Relation r = &allpairs[j ][ j];
 282                 ZEROCOST(r->chain);
 283                 r->rule = &stub_rule;
 284         }
 285         changes = 1;
 286         while (changes) {
 287                 changes = 0;
 288                 for (pl = chainrules; pl; pl = pl->next) {
 289                         Rule p = (Rule) pl->x;
 290                         NonTerminalNum rhs = p->pat->children[0]->num;
 291                         NonTerminalNum lhs = p->lhs->num;
 292                         int i;
 293
 294                         for (i = 1; i < max_nonterminal; i++) {
 295                                 Relation r = &allpairs[rhs ][ i];
 296                                 Relation s = &allpairs[lhs ][ i];
 297                                 DeltaCost dc;
 298                                 if (!r->rule) {
 299                                         continue;
 300                                 }
 301                                 ASSIGNCOST(dc, p->delta);
 302                                 ADDCOST(dc, r->chain);
 303                                 if (!s->rule || LESSCOST(dc, s->chain)) {
 304                                         s->rule = p;
 305                                         ASSIGNCOST(s->chain, dc);
 306                                         changes = 1;
 307                                 }
 308                         }
 309                 }
 310         }
 311         findAllNexts();
 312 }
 313
 314 void
 315 trim(t) Item_Set t;
 316 {
 317         int m,n;
 318         static short *vec = 0;
 319         int last;
 320
 321         assert(!t->closed);
 322         debug(debugTrim, printf("Begin Trim\n"));
 323         debug(debugTrim, dumpItem_Set(t));
 324
 325         last = 0;
 326         if (!vec) {
 327                 vec = (short*) zalloc(max_nonterminal * sizeof(*vec));
 328         }
 329         for (m = 1; m < max_nonterminal; m++) {
 330                 if (t->virgin[m].rule) {
 331                         vec[last++] = m;
 332                 }
 333         }
 334         for (m = 0; m < last; m++) {
 335                 DeltaCost tmp;
 336                 int j;
 337                 int i;
 338
 339                 i = vec[m];
 340
 341                 for (j = allpairs[i ][ 0].nextchain; j; j = allpairs[i ][ j].nextchain) {
 342
 343                         if (i == j) {
 344                                 continue;
 345                         }
 346                         if (!t->virgin[j].rule) {
 347                                 continue;
 348                         }
 349                         ASSIGNCOST(tmp, t->virgin[j].delta);
 350                         ADDCOST(tmp, allpairs[i ][ j].chain);
 351                         if (!LESSCOST(t->virgin[i].delta, tmp)) {
 352                                 t->virgin[i].rule = 0;
 353                                 ZEROCOST(t->virgin[i].delta);
 354                                 debug(debugTrim, printf("Trimmed Chain (%d,%d)\n", i,j));
 355                                 goto outer;
 356                         }
 357
 358                 }
 359                 if (!trimflag) {
 360                         continue;
 361                 }
 362                 for (n = 0; n < last; n++) {
 363                         j = vec[n];
 364                         if (i == j) {
 365                                 continue;
 366                         }
 367
 368                         if (!t->virgin[j].rule) {
 369                                 continue;
 370                         }
 371
 372                         if (!allpairs[i][j].sibComputed) {
 373                                 siblings(i,j);
 374                         }
 375                         if (!allpairs[i][j].sibFlag) {
 376                                 continue;
 377                         }
 378                         ASSIGNCOST(tmp, t->virgin[j].delta);
 379                         ADDCOST(tmp, allpairs[i ][ j].sibling);
 380                         if (!LESSCOST(t->virgin[i].delta, tmp)) {
 381                                 t->virgin[i].rule = 0;
 382                                 ZEROCOST(t->virgin[i].delta);
 383                                 goto outer;
 384                         }
 385                 }
 386
 387                 outer: ;
 388         }
 389
 390         debug(debugTrim, dumpItem_Set(t));
 391         debug(debugTrim, printf("End Trim\n"));
 392 }
 393
 394 void
 395 dumpRelation(r) Relation r;
 396 {
 397         printf("{ %d %ld %d %ld }", r->rule->erulenum, (long) r->chain, r->sibFlag, (long) r->sibling);
 398 }
 399
 400 void
 401 dumpAllPairs()
 402 {
 403         int i,j;
 404
 405         printf("Dumping AllPairs\n");
 406         for (i = 1; i < max_nonterminal; i++) {
 407                 for (j = 1; j < max_nonterminal; j++) {
 408                         dumpRelation(&allpairs[i ][j]);
 409                 }
 410                 printf("\n");
 411         }
 412 }