Move support/tools/* back into utils
llvm-svn: 8875
diff --git a/llvm/utils/Burg/trim.c b/llvm/utils/Burg/trim.c
new file mode 100644
index 0000000..05ee2d0
--- /dev/null
+++ b/llvm/utils/Burg/trim.c
@@ -0,0 +1,412 @@
+char rcsid_trim[] = "$Id$";
+
+#include <stdio.h>
+#include "b.h"
+#include "fe.h"
+
+Relation *allpairs;
+
+int trimflag = 0;
+int debugTrim = 0;
+
+static void siblings ARGS((int, int));
+static void findAllNexts ARGS((void));
+static Relation *newAllPairs ARGS((void));
+
+static void
+siblings(i, j) int i; int j;
+{
+ int k;
+ List pl;
+ DeltaCost Max;
+ int foundmax;
+
+ allpairs[i][j].sibComputed = 1;
+
+ if (i == 1) {
+ return; /* never trim start symbol */
+ }
+ if (i==j) {
+ return;
+ }
+
+ ZEROCOST(Max);
+ foundmax = 0;
+
+ for (k = 1; k < max_nonterminal; k++) {
+ DeltaCost tmp;
+
+ if (k==i || k==j) {
+ continue;
+ }
+ if (!allpairs[k][i].rule) {
+ continue;
+ }
+ if (!allpairs[k][j].rule) {
+ return;
+ }
+ ASSIGNCOST(tmp, allpairs[k][j].chain);
+ MINUSCOST(tmp, allpairs[k][i].chain);
+ if (foundmax) {
+ if (LESSCOST(Max, tmp)) {
+ ASSIGNCOST(Max, tmp);
+ }
+ } else {
+ foundmax = 1;
+ ASSIGNCOST(Max, tmp);
+ }
+ }
+
+ for (pl = rules; pl; pl = pl->next) {
+ Rule p = (Rule) pl->x;
+ Operator op = p->pat->op;
+ List oprule;
+ DeltaCost Min;
+ int foundmin;
+
+ if (!op) {
+ continue;
+ }
+ switch (op->arity) {
+ case 0:
+ continue;
+ case 1:
+ if (!allpairs[p->pat->children[0]->num ][ i].rule) {
+ continue;
+ }
+ foundmin = 0;
+ for (oprule = op->table->rules; oprule; oprule = oprule->next) {
+ Rule s = (Rule) oprule->x;
+ DeltaPtr Cx;
+ DeltaPtr Csj;
+ DeltaPtr Cpi;
+ DeltaCost tmp;
+
+ if (!allpairs[p->lhs->num ][ s->lhs->num].rule
+ || !allpairs[s->pat->children[0]->num ][ j].rule) {
+ continue;
+ }
+ Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
+ Csj= allpairs[s->pat->children[0]->num ][ j].chain;
+ Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
+ ASSIGNCOST(tmp, Cx);
+ ADDCOST(tmp, s->delta);
+ ADDCOST(tmp, Csj);
+ MINUSCOST(tmp, Cpi);
+ MINUSCOST(tmp, p->delta);
+ if (foundmin) {
+ if (LESSCOST(tmp, Min)) {
+ ASSIGNCOST(Min, tmp);
+ }
+ } else {
+ foundmin = 1;
+ ASSIGNCOST(Min, tmp);
+ }
+ }
+ if (!foundmin) {
+ return;
+ }
+ if (foundmax) {
+ if (LESSCOST(Max, Min)) {
+ ASSIGNCOST(Max, Min);
+ }
+ } else {
+ foundmax = 1;
+ ASSIGNCOST(Max, Min);
+ }
+ break;
+ case 2:
+ /* do first dimension */
+ if (allpairs[p->pat->children[0]->num ][ i].rule) {
+ foundmin = 0;
+ for (oprule = op->table->rules; oprule; oprule = oprule->next) {
+ Rule s = (Rule) oprule->x;
+ DeltaPtr Cx;
+ DeltaPtr Cb;
+ DeltaPtr Csj;
+ DeltaPtr Cpi;
+ DeltaCost tmp;
+
+ if (allpairs[p->lhs->num ][ s->lhs->num].rule
+ && allpairs[s->pat->children[0]->num ][ j].rule
+ && allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].rule) {
+ Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
+ Csj= allpairs[s->pat->children[0]->num ][ j].chain;
+ Cpi= allpairs[p->pat->children[0]->num ][ i].chain;
+ Cb = allpairs[s->pat->children[1]->num ][ p->pat->children[1]->num].chain;
+ ASSIGNCOST(tmp, Cx);
+ ADDCOST(tmp, s->delta);
+ ADDCOST(tmp, Csj);
+ ADDCOST(tmp, Cb);
+ MINUSCOST(tmp, Cpi);
+ MINUSCOST(tmp, p->delta);
+ if (foundmin) {
+ if (LESSCOST(tmp, Min)) {
+ ASSIGNCOST(Min, tmp);
+ }
+ } else {
+ foundmin = 1;
+ ASSIGNCOST(Min, tmp);
+ }
+ }
+ }
+ if (!foundmin) {
+ return;
+ }
+ if (foundmax) {
+ if (LESSCOST(Max, Min)) {
+ ASSIGNCOST(Max, Min);
+ }
+ } else {
+ foundmax = 1;
+ ASSIGNCOST(Max, Min);
+ }
+ }
+ /* do second dimension */
+ if (allpairs[p->pat->children[1]->num ][ i].rule) {
+ foundmin = 0;
+ for (oprule = op->table->rules; oprule; oprule = oprule->next) {
+ Rule s = (Rule) oprule->x;
+ DeltaPtr Cx;
+ DeltaPtr Cb;
+ DeltaPtr Csj;
+ DeltaPtr Cpi;
+ DeltaCost tmp;
+
+ if (allpairs[p->lhs->num ][ s->lhs->num].rule
+ && allpairs[s->pat->children[1]->num ][ j].rule
+ && allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].rule) {
+ Cx = allpairs[p->lhs->num ][ s->lhs->num].chain;
+ Csj= allpairs[s->pat->children[1]->num ][ j].chain;
+ Cpi= allpairs[p->pat->children[1]->num ][ i].chain;
+ Cb = allpairs[s->pat->children[0]->num ][ p->pat->children[0]->num].chain;
+ ASSIGNCOST(tmp, Cx);
+ ADDCOST(tmp, s->delta);
+ ADDCOST(tmp, Csj);
+ ADDCOST(tmp, Cb);
+ MINUSCOST(tmp, Cpi);
+ MINUSCOST(tmp, p->delta);
+ if (foundmin) {
+ if (LESSCOST(tmp, Min)) {
+ ASSIGNCOST(Min, tmp);
+ }
+ } else {
+ foundmin = 1;
+ ASSIGNCOST(Min, tmp);
+ }
+ }
+ }
+ if (!foundmin) {
+ return;
+ }
+ if (foundmax) {
+ if (LESSCOST(Max, Min)) {
+ ASSIGNCOST(Max, Min);
+ }
+ } else {
+ foundmax = 1;
+ ASSIGNCOST(Max, Min);
+ }
+ }
+ break;
+ default:
+ assert(0);
+ }
+ }
+ allpairs[i ][ j].sibFlag = foundmax;
+ ASSIGNCOST(allpairs[i ][ j].sibling, Max);
+}
+
+static void
+findAllNexts()
+{
+ int i,j;
+ int last;
+
+ for (i = 1; i < max_nonterminal; i++) {
+ last = 0;
+ for (j = 1; j < max_nonterminal; j++) {
+ if (allpairs[i ][j].rule) {
+ allpairs[i ][ last].nextchain = j;
+ last = j;
+ }
+ }
+ }
+ /*
+ for (i = 1; i < max_nonterminal; i++) {
+ last = 0;
+ for (j = 1; j < max_nonterminal; j++) {
+ if (allpairs[i ][j].sibFlag) {
+ allpairs[i ][ last].nextsibling = j;
+ last = j;
+ }
+ }
+ }
+ */
+}
+
+static Relation *
+newAllPairs()
+{
+ int i;
+ Relation *rv;
+
+ rv = (Relation*) zalloc(max_nonterminal * sizeof(Relation));
+ for (i = 0; i < max_nonterminal; i++) {
+ rv[i] = (Relation) zalloc(max_nonterminal * sizeof(struct relation));
+ }
+ return rv;
+}
+
+void
+findAllPairs()
+{
+ List pl;
+ int changes;
+ int j;
+
+ allpairs = newAllPairs();
+ for (pl = chainrules; pl; pl = pl->next) {
+ Rule p = (Rule) pl->x;
+ NonTerminalNum rhs = p->pat->children[0]->num;
+ NonTerminalNum lhs = p->lhs->num;
+ Relation r = &allpairs[lhs ][ rhs];
+
+ if (LESSCOST(p->delta, r->chain)) {
+ ASSIGNCOST(r->chain, p->delta);
+ r->rule = p;
+ }
+ }
+ for (j = 1; j < max_nonterminal; j++) {
+ Relation r = &allpairs[j ][ j];
+ ZEROCOST(r->chain);
+ r->rule = &stub_rule;
+ }
+ changes = 1;
+ while (changes) {
+ changes = 0;
+ for (pl = chainrules; pl; pl = pl->next) {
+ Rule p = (Rule) pl->x;
+ NonTerminalNum rhs = p->pat->children[0]->num;
+ NonTerminalNum lhs = p->lhs->num;
+ int i;
+
+ for (i = 1; i < max_nonterminal; i++) {
+ Relation r = &allpairs[rhs ][ i];
+ Relation s = &allpairs[lhs ][ i];
+ DeltaCost dc;
+ if (!r->rule) {
+ continue;
+ }
+ ASSIGNCOST(dc, p->delta);
+ ADDCOST(dc, r->chain);
+ if (!s->rule || LESSCOST(dc, s->chain)) {
+ s->rule = p;
+ ASSIGNCOST(s->chain, dc);
+ changes = 1;
+ }
+ }
+ }
+ }
+ findAllNexts();
+}
+
+void
+trim(t) Item_Set t;
+{
+ int m,n;
+ static short *vec = 0;
+ int last;
+
+ assert(!t->closed);
+ debug(debugTrim, printf("Begin Trim\n"));
+ debug(debugTrim, dumpItem_Set(t));
+
+ last = 0;
+ if (!vec) {
+ vec = (short*) zalloc(max_nonterminal * sizeof(*vec));
+ }
+ for (m = 1; m < max_nonterminal; m++) {
+ if (t->virgin[m].rule) {
+ vec[last++] = m;
+ }
+ }
+ for (m = 0; m < last; m++) {
+ DeltaCost tmp;
+ int j;
+ int i;
+
+ i = vec[m];
+
+ for (j = allpairs[i ][ 0].nextchain; j; j = allpairs[i ][ j].nextchain) {
+
+ if (i == j) {
+ continue;
+ }
+ if (!t->virgin[j].rule) {
+ continue;
+ }
+ ASSIGNCOST(tmp, t->virgin[j].delta);
+ ADDCOST(tmp, allpairs[i ][ j].chain);
+ if (!LESSCOST(t->virgin[i].delta, tmp)) {
+ t->virgin[i].rule = 0;
+ ZEROCOST(t->virgin[i].delta);
+ debug(debugTrim, printf("Trimmed Chain (%d,%d)\n", i,j));
+ goto outer;
+ }
+
+ }
+ if (!trimflag) {
+ continue;
+ }
+ for (n = 0; n < last; n++) {
+ j = vec[n];
+ if (i == j) {
+ continue;
+ }
+
+ if (!t->virgin[j].rule) {
+ continue;
+ }
+
+ if (!allpairs[i][j].sibComputed) {
+ siblings(i,j);
+ }
+ if (!allpairs[i][j].sibFlag) {
+ continue;
+ }
+ ASSIGNCOST(tmp, t->virgin[j].delta);
+ ADDCOST(tmp, allpairs[i ][ j].sibling);
+ if (!LESSCOST(t->virgin[i].delta, tmp)) {
+ t->virgin[i].rule = 0;
+ ZEROCOST(t->virgin[i].delta);
+ goto outer;
+ }
+ }
+
+ outer: ;
+ }
+
+ debug(debugTrim, dumpItem_Set(t));
+ debug(debugTrim, printf("End Trim\n"));
+}
+
+void
+dumpRelation(r) Relation r;
+{
+ printf("{ %d %ld %d %ld }", r->rule->erulenum, (long) r->chain, r->sibFlag, (long) r->sibling);
+}
+
+void
+dumpAllPairs()
+{
+ int i,j;
+
+ printf("Dumping AllPairs\n");
+ for (i = 1; i < max_nonterminal; i++) {
+ for (j = 1; j < max_nonterminal; j++) {
+ dumpRelation(&allpairs[i ][j]);
+ }
+ printf("\n");
+ }
+}