4.3BSD - /usr/ingres/source/decomp/aggregate.c

   1: # include   <ingres.h>
   2: # include   <tree.h>
   3: # include   <symbol.h>
   4: # include   "globs.h"
   5: # include   <sccs.h>
   6: # include   <errors.h>
   7: 
   8: SCCSID(@(#)aggregate.c	8.3	2/8/85)
   9: 
  10: 
  11: 
  12: 
  13: /*
  14: **	AGGREGATE - replace aggregates with their values
  15: **
  16: **	Aggregate attempts to optimize aggregate processing
  17: **	wherever possible. It replaces aggregates with their
  18: **	values, and links aggregate functions which have
  19: **	identical by-lists together.
  20: **
  21: **	Note that for the sake of this code, A "prime"
  22: **	aggregate is one in which duplicates are removed.
  23: **	These are COUNTU, SUMU, and AVGU.
  24: **
  25: **	Aggregate first forms a list of all aggregates in
  26: **	the order they should be processed.
  27: **
  28: **	For each aggregate, it looks at all other aggregates
  29: **	to see if there are two simple aggregates
  30: **	or if there is another aggregate funtion with the
  31: **	same by-list.
  32: **
  33: **	An attempt is made to run
  34: **	as many aggregates as possible at once. This can be
  35: **	done only if two or more aggregates have the same
  36: **	qualifications and in the case of aggregate functions,
  37: **	they must have identical by-lists.
  38: **	Even then, certain combinations
  39: **	of aggregates cannot occure together. The list is
  40: **	itemized later in the code.
  41: **
  42: **	Aggregate calls BYEVAL or AGEVAL to actually process
  43: **	aggregate functions or aggregates respectively.
  44: **
  45: **	Trace Flags:
  46: **		40
  47: */
  48: 
  49: aggregate(root)
  50: QTREE   *root;
  51: {
  52:     struct agglist  alist[MAXAGG + 1];
  53:     QTREE       *rlist[MAXAGG + 1];
  54:     struct agglist  *al, *al1;
  55:     register QTREE  *agg, *aop1, *r;
  56:     QTREE       *aop, *agg1;
  57:     int     i, simple_agg, varmap;
  58:     int     attcnt, anyagg, attoff, twidth;
  59:     QTREE       *makavar(), *agspace();
  60:     extern char *rangename();
  61:     extern QTREE    *ageval();
  62:     extern QTREE    *byeval();
  63: 
  64:     al = alist;
  65:     De.de_aggnext = al;
  66:     De.de_agglim = &al[MAXAGG];
  67: 
  68:     findagg(&root, root);   /* generate list of all aggregates */
  69:     De.de_aggnext->agpoint = 0; /* mark end of the list */
  70:     anyagg = 0;
  71: 
  72:     varmap = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
  73: 
  74:     /* process each aggregate */
  75:     for (;agg = al->agpoint; al++)
  76:     {
  77:         /* is this still an aggregate? */
  78:         if (agg->sym.type != AGHEAD)
  79:             continue;
  80:         mapvar(agg, 0); /* map the aggregate tree */
  81:         anyagg++;
  82: 
  83:         De.de_sourcevar = bitpos(agg->sym.value.sym_root.lvarm | agg->sym.value.sym_root.rvarm);
  84: #		ifdef xDTR1
  85:         if (tTf(40, 4))
  86:             printf("De.de_sourcevar=%d,rel=%s\n", De.de_sourcevar, rangename(De.de_sourcevar));
  87: #		endif
  88: 
  89:         simple_agg = (agg->left->sym.type == AOP);  /* TRUE if no bylist */
  90:         aop = agg->left;    /* assume it was TRUE */
  91: #		ifdef xDTR1
  92:         if (tTf(40, 0))
  93:             printf("%s\n", simple_agg ? "agg" : "agg-func");
  94: #		endif
  95:         if (simple_agg)
  96:         {
  97:             /* simple aggregate */
  98:             rlist[0] = agspace(aop);
  99:             twidth = aop->sym.value.sym_op.opfrml & I1MASK; /* init width to the width of the aggregate */
 100:         }
 101:         else
 102:         {
 103:             attoff = agg->left->left->sym.value.sym_resdom.resno + 2;
 104:             aop = aop->right;   /* find the AOP node */
 105:             /* assign  new source variable for aggregate */
 106:             al->agvarno = getrange(&varmap);
 107:             /* compute width of bylist + count field */
 108:             twidth = findwid(agg->left) + 4;
 109: 
 110:             /* make sure the aggregate does not exceed max dimensions */
 111:             if (chkwidth(aop, &twidth, attoff))
 112:                 derror(AGFTOBIG);
 113:         }
 114:         attcnt = 1; /* one aggregate so far */
 115: 
 116:         /* look for another identical aggregate */
 117:         for (al1 = al + 1; agg1 = al1->agpoint; al1++)
 118:         {
 119: 
 120:             /* if agg is nested inside agg1 then ignore it */
 121:             if (al->agfather == agg1 || agg1->sym.type != AGHEAD)
 122:             {
 123:                 continue;
 124:             }
 125: 
 126:             /* split aggs and agg-func apart */
 127:             /* check for identical aggregate */
 128:             if (simple_agg)
 129:             {
 130:                 aop1 = agg1->left;  /* find AOP node */
 131: 
 132:                 if (aop1->sym.type != AOP)
 133:                     continue;   /* not a simple agg */
 134: 
 135:                 /* make sure they can be run together */
 136:                 if (checkagg(agg, aop, agg1, aop1) == 0)
 137:                     continue;
 138: 
 139:                 if ((i = sameagg(agg, aop1, attcnt)) >= 0)
 140:                 {
 141:                     /* found identical aggregate to rlist[i] */
 142:                     r = rlist[i];
 143:                 }
 144:                 else
 145:                 {
 146:                     /* put this agg in with the others */
 147: 
 148:                     /* first make sure it won't exceed tuple length */
 149:                     if (chkwidth(aop1, &twidth, 0))
 150:                         continue;   /* can't be included */
 151:                     r = rlist[attcnt++] = agspace(aop1);
 152: 
 153:                     /* connect into tree */
 154:                     aop1->left = agg->left;
 155:                     agg->left = aop1;
 156:                 }
 157:             }
 158:             else
 159:             {
 160:                 /* aggregate function */
 161:                 if (!sameafcn(agg->left->left, agg1->left->left))
 162:                     continue;
 163: 
 164:                 aop1 = agg1->left->right;   /* find AOP */
 165: 
 166: 
 167:                 if (checkagg(agg, aop, agg1, aop1) == 0)
 168:                 {
 169:                     /* same by-lists but they can't be run together */
 170:                     continue;
 171:                 }
 172: 
 173:                 if ((i = sameagg(agg, aop1, attcnt)) < 0)
 174:                 {
 175:                     /* make sure there is room */
 176:                     if (chkwidth(aop1, &twidth, attcnt + attoff))
 177:                         continue;
 178: 
 179:                     /* add aggregate into tree */
 180:                     i = attcnt++;
 181: 
 182:                     aop1->left = agg->left->right;
 183:                     agg->left->right = aop1;
 184:                 }
 185: 
 186:                 r = makavar(aop1, al->agvarno, i + attoff);
 187:             }
 188:             /* replace aggregate in original tree with its value */
 189:             *(al1->father) = r;
 190: 
 191:             /* remove aggregate from local list */
 192:             agg1->sym.type = -1;
 193: #			ifdef xDTR1
 194:             if (tTf(40, 3))
 195:                 printf("including aghead %x\n", agg1);
 196: #			endif
 197:         }
 198: 
 199:         /* process aggregate */
 200:         if (simple_agg)
 201:         {
 202:             rlist[attcnt] = 0;
 203:             ageval(agg, rlist); /* pass tree and result list */
 204:             r = rlist[0];
 205:         }
 206:         else
 207:         {
 208:             opt_bylist(alist, agg);
 209:             byeval(al->agfather, agg, al->agvarno);
 210:             r = makavar(aop, al->agvarno, attoff);
 211:         }
 212:         /*
 213: 		** Link result into tree. al->father hold the address
 214: 		** &(tree->left) or &(tree->right).
 215: 		*/
 216:         *(al->father) = r;
 217: #		ifdef xDTR1
 218:         if (tTf(40, 4))
 219:         {
 220:             printf("agg value\n");
 221:             treepr(*(al->father));
 222:         }
 223: #		endif
 224:     }
 225:     if (anyagg)
 226:     {
 227:         opt_bylist(alist, root);
 228:         mapvar(root, 0);    /* remap main tree */
 229:     }
 230: }
 231: /*
 232: **	findagg builds a list of all aggregates
 233: **	in the tree. It finds them by leftmost
 234: **	innermost first.
 235: **
 236: **	The parameters represent:
 237: **		nodep:	the address of the node pointing to you
 238: **				eg. &(tree->left) or &(tree->right)
 239: **		agf:	the root node. or if we are inside
 240: **			a nested aggregate, the AGHEAD node
 241: */
 242: 
 243: findagg(nodep,  agf)
 244: QTREE   **nodep;
 245: QTREE   *agf;
 246: {
 247:     register QTREE      *q, *f;
 248:     register struct agglist *list;
 249:     int         agg;
 250: 
 251:     if ((q = *nodep) == NULL)
 252:         return;
 253: 
 254:     f = agf;
 255:     if (agg = (q->sym.type == AGHEAD))
 256:         f = q;  /* this aggregate is now the father root */
 257: 
 258:     /* find all aggregates below */
 259:     findagg(&(q->left), f);
 260:     findagg(&(q->right), f);
 261: 
 262:     /* if this is an aggregate, put it on the list */
 263:     if (agg)
 264:     {
 265:         if (De.de_aggnext >= De.de_agglim)
 266:             derror(TOOMANYAGGS);
 267:         list = De.de_aggnext;
 268:         list->father = nodep;
 269:         list->agpoint = q;
 270:         list->agfather = agf;
 271:         De.de_aggnext++;
 272:     }
 273: }
 274: /*
 275: **	Agspace allocates space for the result of
 276: **	a simple aggregate.
 277: */
 278: 
 279: QTREE *
 280: agspace(aop)
 281: QTREE   *aop;
 282: {
 283:     register QTREE  *a, *r;
 284:     register int    length;
 285:     extern char *need();
 286: 
 287:     a = aop;
 288:     length = a->sym.value.sym_op.opfrml & I1MASK;
 289:     r = (QTREE *) need(De.de_qbuf, length + QT_HDR_SIZ);
 290:     r->left = r->right = 0;
 291:     r->sym.type = a->sym.value.sym_op.opfrmt;
 292:     r->sym.len = length;
 293: 
 294:     return (r);
 295: }
 296: /*
 297: ** Chkwidth -- make sure that the inclusion of another aggregate will
 298: **	not exceed the system limit. This means that the total width
 299: **	cannot exceed MAXTUP and the number of domains cannot exceed MAXDOM-1
 300: */
 301: 
 302: chkwidth(aop, widthp, domno)
 303: QTREE   *aop;
 304: int *widthp;
 305: int domno;
 306: {
 307:     register int    width;
 308: 
 309:     width = *widthp;
 310: 
 311: #	ifdef xDTR1
 312:     if (tTf(40, 10))
 313:         printf("agg width %d,dom %d\n", width, domno);
 314: #	endif
 315: 
 316:     width += (aop->sym.value.sym_op.opfrml & I1MASK);
 317: 
 318:     if (width > MAXTUP || domno > MAXDOM - 1)
 319:         return (1);
 320: 
 321:     *widthp = width;
 322:     return (0);
 323: }
 324: /*
 325: **	Determine whether an aggregate is prime
 326: **	or a don't care aggregate. Returns TRUE
 327: **	if COUNTU,SUMU,AVGU,MIN,MAX,ANY.
 328: **	Returns false if COUNT,SUM,AVG.
 329: */
 330: 
 331: cprime(aop)
 332: QTREE   *aop;
 333: {
 334:     register int    i;
 335: 
 336:     i = TRUE;
 337:     switch (aop->sym.value.sym_op.opno)
 338:     {
 339:       case opCOUNT:
 340:       case opSUM:
 341:       case opAVG:
 342:         i = FALSE;
 343:     }
 344:     return (i);
 345: }
 346: /*
 347: **	Getrange find a free slot in the range table
 348: **	for an aggregate function.
 349: **
 350: **	If there are no free slots,derror is called
 351: */
 352: 
 353: getrange(varmap)
 354: int *varmap;
 355: {
 356:     register int    i, map, bit;
 357: 
 358:     map = *varmap;
 359: 
 360:     for (i = 0; i < MAXRANGE; i++)
 361:     {
 362:         /* if slot is used, continue */
 363:         if ((bit = 1 << i) & map)
 364:             continue;
 365: 
 366:         map |= bit; /* "or" bit into the map */
 367:         *varmap = map;
 368: 
 369: #		ifdef xDTR1
 370:         if (tTf(40, 10))
 371:             printf("Assn var %d, map %o\n", i, map);
 372: #		endif
 373: 
 374:         return (i);
 375:     }
 376:     derror(NODESCAG);
 377:     return  (-1);
 378: }
 379: 
 380: 
 381: checkagg(aghead1, aop1, aghead2, aop2)
 382: QTREE   *aghead1;
 383: QTREE   *aop1;
 384: QTREE   *aghead2;
 385: QTREE   *aop2;
 386: {
 387:     register QTREE  *aop_1, *aop_2, *agg1;
 388:     int     ok;
 389: 
 390:     /* two aggregate functions can be run together
 391: 	** according to the following table:
 392: 	**
 393: 	**		prime	!prime	don't care
 394: 	**
 395: 	** prime	afcn?	never	afcn?
 396: 	** !prime	never	always	always
 397: 	** don't care	afcn?	always	always
 398: 	**
 399: 	** don't care includes: ANY, MIN, MAX
 400: 	** afcn? means only if a-fcn's are identical
 401: 	*/
 402: 
 403:     aop_1 = aop1;
 404:     aop_2 = aop2;
 405:     agg1 = aghead1;
 406: 
 407:     if (!prime(aop_1) && !prime(aop_2))
 408:         ok = TRUE;
 409:     else
 410:         if (sameafcn(aop_1->right, aop_2->right))
 411:             ok = cprime(aop_1) && cprime(aop_2);
 412:         else
 413:             ok = FALSE;
 414:     /* The two aggregates must range over the same variables */
 415:     if ((agg1->sym.value.sym_root.lvarm | agg1->sym.value.sym_root.rvarm) != (aghead2->sym.value.sym_root.lvarm | aghead2->sym.value.sym_root.rvarm))
 416:         ok = FALSE;
 417: 
 418: 
 419:     /* check the qualifications */
 420:     if (ok)
 421:         ok = sameafcn(agg1->right, aghead2->right);
 422:     return (ok);
 423: }
 424: 
 425: 
 426: sameagg(aghead, newaop, agg_depth)
 427: QTREE   *aghead;
 428: QTREE   *newaop;
 429: int agg_depth;
 430: {
 431:     register QTREE  *agg, *newa;
 432:     register int    i;
 433: 
 434:     agg = aghead;
 435:     newa = newaop;
 436:     agg = agg->left;
 437:     if (agg->sym.type == BYHEAD)
 438:         agg = agg->right;
 439: 
 440:     /* agg now points to first aggregate */
 441:     for (i = 1; agg; agg = agg->left, i++)
 442:         if (sameafcn(agg->right, newa->right) && agg->sym.value.sym_resdom.resno == newa->sym.value.sym_op.opno)
 443:         {
 444: #			ifdef xDTR1
 445:             if (tTf(40, 6))
 446:                 printf("found identical aop %x\n", newa);
 447: #			endif
 448:             return (agg_depth - i);
 449:         }
 450: 
 451:     /* no match */
 452:     return (-1);
 453: }
 454: 
 455: 
 456: 
 457: 
 458: opt_bylist(alist, root)
 459: struct agglist  *alist;
 460: QTREE       *root;
 461: {
 462:     register struct agglist *al;
 463:     register QTREE      *agg;
 464:     register struct hitlist *hl;
 465:     QTREE           **tpr, *tree, *lnodv[MAXDOM+2];
 466:     struct hitlist      hlist[30];
 467:     int         anyop, i, usedmap, vars, treemap;
 468: 
 469:     /* compute bitmap of all possible vars in tree (can include xtra vars) */
 470:     treemap = root->sym.value.sym_root.lvarm | root->sym.value.sym_root.rvarm;
 471:     anyop = FALSE;
 472: 
 473:     /* scan the list of aggregates looking for one nested in root */
 474:     for (al = alist; (agg = al->agpoint) && agg != root; al++)
 475:     {
 476:         if (agg->sym.type == AGHEAD && agg->left->sym.type == BYHEAD &&
 477:                 al->agfather == root)
 478:         {
 479: 
 480:             /* this aggregate function is nested in root */
 481: 
 482:             /* make sure it has some vars of interest */
 483:             if ((treemap & varfind(agg->left->left, (QTREE *)NULL)) == 0)
 484:                 continue;
 485: 
 486: #			ifdef xDTR1
 487:             if (tTf(40, 11))
 488:             {
 489:                 printf("nested agg\n");
 490:                 treepr(agg);
 491:             }
 492: #			endif
 493: 
 494:             /* form list of bydomains */
 495:             lnodv[lnode(agg->left->left, lnodv, 0)] = 0;
 496:             usedmap = 0;
 497: 
 498:             De.de_hnext = &hlist[0];
 499:             De.de_hlimit = &hlist[30];
 500: 
 501:             /* find all possible replacements */
 502:             vars = modtree(&root, lnodv, &usedmap);
 503: 
 504:             /*
 505: 			** All references to a variable must be replaced
 506: 			** in order to use this aggregates by-domains.
 507: 			*/
 508:             if (usedmap && ((vars & usedmap) == 0))
 509:             {
 510: #				ifdef xDTR1
 511:                 if (tTf(40, 7))
 512:                     printf("Committed\n");
 513: #				endif
 514:                 /* success. Committ the tree changes */
 515:                 De.de_hnext->trepr = NULL;
 516: 
 517:                 for (hl = &hlist[0]; tpr = hl->trepr; hl++)
 518:                 {
 519:                     /* get bydomain number */
 520:                     i = hl->byno;
 521: 
 522:                     /* get node being replaced */
 523:                     tree = *tpr;
 524: 
 525:                     /* if it is already a var, just change it */
 526:                     if (tree->sym.type == VAR)
 527:                     {
 528:                         tree->sym.value.sym_var.varno = al->agvarno;
 529:                         tree->sym.value.sym_var.attno = i + 2;
 530:                     }
 531:                     else
 532:                         *tpr = makavar(lnodv[i], al->agvarno, i + 2);
 533: 
 534:                     anyop = TRUE;
 535: #					ifdef xDTR1
 536:                     if (tTf(40, 7))
 537:                     {
 538:                         printf("modified tree\n");
 539:                         treepr(*tpr);
 540:                     }
 541: #					endif
 542:                 }
 543:             }
 544:             /* vars is now a map of the variables in the root */
 545:             treemap = vars;
 546:         }
 547:     }
 548: 
 549:     /* if any changes were made, get rid of the unnecessary links */
 550:     if (anyop)
 551:         chklink(root);
 552: }
 553: 
 554: 
 555: 
 556: 
 557: modtree(pnode, lnodv, replmap)
 558: QTREE   **pnode;
 559: QTREE   *lnodv[];
 560: int *replmap;
 561: {
 562:     register QTREE  *tree;
 563:     register int    vars, i;
 564:     QTREE       *afcn;
 565: 
 566:     /* point up current node */
 567:     if ((tree = *pnode) == NULL)
 568:         return (0);
 569: 
 570:     /* examine each by-list for match on this subtree */
 571:     for (i = 0; afcn = lnodv[i]; i++)
 572:     {
 573:         if (sameafcn(tree, afcn->right))
 574:         {
 575: #			ifdef xDTR1
 576:             if (tTf(40, 9))
 577:             {
 578:                 printf("potential Jackpot");
 579:                 treepr(tree);
 580:             }
 581: #			endif
 582:             vars = varfind(tree, (QTREE *)NULL);
 583:             if (De.de_hnext == De.de_hlimit)
 584:                 return (vars);  /* no more room */
 585: 
 586:             /* record what needs to be done */
 587:             De.de_hnext->trepr = pnode;
 588:             De.de_hnext->byno = i;
 589:             De.de_hnext++;
 590:             *replmap |= vars;
 591:             return (0);
 592:         }
 593:     }
 594:     if (tree->sym.type == VAR)
 595:         return (01 << tree->sym.value.sym_var.varno);
 596: 
 597:     /* try the subtrees */
 598:     vars = modtree(&(tree->left), lnodv, replmap);
 599:     if ((vars & *replmap) == 0)
 600:         vars |= modtree(&(tree->right), lnodv, replmap);
 601: 
 602:     return (vars);
 603: }
 604: 
 605: 
 606: chklink(root)
 607: QTREE   *root;
 608: {
 609:     register QTREE  *r, *b, *last;
 610: 
 611:     last = root;
 612: 
 613:     for (r = last->right; r->sym.type != QLEND; r = r->right)
 614:     {
 615:         /* if this is an EQ node then check for an unnecessary compare */
 616:         if ((b = r->left)->sym.type == BOP && b->sym.value.sym_op.opno == opEQ)
 617:         {
 618:             if (sameafcn(b->left, b->right))
 619:             {
 620: #				ifdef xDTR1
 621:                 if (tTf(40, 5))
 622:                 {
 623:                     printf("unnec clause\n");
 624:                     treepr(b);
 625:                 }
 626: #				endif
 627:                 last->right = r->right;
 628:                 continue;
 629:             }
 630:         }
 631:         last = r;
 632:     }
 633: }
 634: 
 635: 
 636: 
 637: sameafcn(q1, q2)
 638: QTREE *q1, *q2;
 639: {
 640: 
 641:     register QTREE  *t1, *t2;
 642:     register int    len;
 643:     int     type;
 644: 
 645:     t1 = q1;
 646:     t2 = q2;
 647: 
 648:     if (!(t1 && t2))
 649:         return(!(t1 || t2));
 650:     len = (t1->sym.len & I1MASK) + SYM_HDR_SIZ;
 651:     type = t1->sym.type;
 652:     if (type == VAR)
 653:         len = sizeof(struct varnode);
 654:     if (type == AND)
 655:         len = 2;
 656:     if (!bequal(&t1->sym.type, &t2->sym.type, len))
 657:         return(0);
 658:     return(sameafcn(t1->left,t2->left) && sameafcn(t1->right,t2->right));
 659: }
 660: /*
 661: **	varfind -- find all variables in the tree pointed to by "root".
 662: **		Examine all parts of the tree except aggregates. For
 663: **		aggregates, ignore simple aggregate and look only
 664: **		at the by-lists of aggregate functions. If the aggregate
 665: **		is "aghead" then ignore it. There is no reason to look
 666: **		at yourself!!!!
 667: **		This routine is called by byeval() to determine
 668: **		whether to link the aggregate to the root tree.
 669: **
 670: **	Curiosity note: since the tree being examined has not been
 671: **	processed by decomp yet, ckvar does not need to be called
 672: **	since the var could not have been altered.
 673: */
 674: 
 675: varfind(root, aghead)
 676: QTREE   *root;
 677: QTREE   *aghead;
 678: {
 679:     register QTREE  *tree;
 680:     register int    type;
 681: 
 682:     if ((tree = root) == NULL)
 683:         return (0);
 684: 
 685:     if ((type = tree->sym.type) == AGHEAD)
 686:     {
 687:         /* ignore if it matches aghead */
 688:         if (tree == aghead)
 689:             return (0);
 690:         /* if this is an aggregate function, look at bylist */
 691:         tree = tree->left;
 692:         if ((type = tree->sym.type) != BYHEAD)
 693:             return (0);
 694:     }
 695: 
 696:     if (type == VAR)
 697:         return (1 << tree->sym.value.sym_var.varno);
 698: 
 699:     return (varfind(tree->left, aghead) | varfind(tree->right, aghead));
 700: }

Defined functions