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 }