home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V6 / usr / source / c / c12.c < prev    next >
Encoding:
C/C++ Source or Header  |  1975-07-18  |  11.6 KB  |  622 lines
  1. #
  2. /*
  3.  *        C compiler part 2 -- expression optimizer
  4.  *
  5.  */
  6.  
  7. #include "c1h.c"
  8.  
  9. optim(atree)
  10. struct tnode *atree;
  11. {
  12.     register op, dope;
  13.     int d1, d2;
  14.     struct tnode *t;
  15.     register struct tnode *tree;
  16.  
  17.     if ((tree=atree)==0)
  18.         return(0);
  19.     if ((op = tree->op)==0)
  20.         return(tree);
  21.     if (op==NAME && tree->class==AUTO) {
  22.         tree->class = OFFS;
  23.         tree->regno = 5;
  24.         tree->offset = tree->nloc;
  25.     }
  26.     dope = opdope[op];
  27.     if ((dope&LEAF) != 0)
  28.         return(tree);
  29.     if ((dope&BINARY) == 0)
  30.         return(unoptim(tree));
  31.     /* is known to be binary */
  32.     if (tree->type==CHAR)
  33.         tree->type = INT;
  34.     if ((dope&COMMUTE)!=0) {
  35.     acomm:    d1 = tree->type;
  36.         tree = acommute(tree);
  37.         tree->type = d1;
  38.         /*
  39.          * PDP-11 special:
  40.          * replace a&b by a NAND ~ b.
  41.          * This will be undone when in
  42.          * truth-value context.
  43.          */
  44.         if (tree->op!=AND)
  45.             return(tree);
  46.         tree->op = NAND;
  47.         tree->tr2 = block(1, COMPL, tree->tr2->type, 0, tree->tr2);
  48.     }
  49.     again:
  50.     tree->tr1 = optim(tree->tr1);
  51.     tree->tr2 = optim(tree->tr2);
  52.     if ((dope&RELAT) != 0) {
  53.         if ((d1=degree(tree->tr1)) < (d2=degree(tree->tr2))
  54.          || d1==d2 && tree->tr1->op==NAME && tree->tr2->op!=NAME) {
  55.             t = tree->tr1;
  56.             tree->tr1 = tree->tr2;
  57.             tree->tr2 = t;
  58.             tree->op = maprel[op-EQUAL];
  59.         }
  60.         if (tree->tr1->type==CHAR && tree->tr2->op==CON
  61.          && (dcalc(tree->tr1) <= 12 || tree->tr1->op==STAR)
  62.          && tree->tr2->value <= 127 && tree->tr2->value >= 0)
  63.             tree->tr2->type = CHAR;
  64.     }
  65.     d1 = max(degree(tree->tr1), islong(tree->type));
  66.     d2 = max(degree(tree->tr2), 0);
  67.     if (tree->tr1->type==LONG && dope&RELAT)
  68.         d1 = 10;
  69.     switch (op) {
  70.  
  71.     case LTIMES:
  72.     case LDIV:
  73.     case LMOD:
  74.     case LASTIMES:
  75.     case LASDIV:
  76.     case LASMOD:
  77.         tree->degree = 10;
  78.         break;
  79.  
  80.     /*
  81.      * PDP-11 special:
  82.      * generate new =&~ operator out of =&
  83.      * by complementing the RHS.
  84.      */
  85.     case ASSAND:
  86.         op = ASSNAND;
  87.         tree->op = op;
  88.         tree->tr2 = block(2, COMPL, tree->tr2->type, 0, tree->tr2);
  89.         goto again;
  90.  
  91.     case NAND:
  92.         if (isconstant(tree->tr2) && tree->tr2->value==0)
  93.             return(tree->tr1);
  94.         goto def;
  95.  
  96.     case CALL:
  97.         tree->degree = 10;
  98.         break;
  99.  
  100.     case QUEST:
  101.     case COLON:
  102.         tree->degree = max(d1, d2);
  103.         break;
  104.  
  105.     case MINUS:
  106.         if (t = isconstant(tree->tr2)) {
  107.             tree->op = PLUS;
  108.             if (t->type==DOUBLE)
  109.                 /* PDP-11 FP representation */
  110.                 t->value =^ 0100000;
  111.             else
  112.                 t->value = -t->value;
  113.             goto acomm;
  114.         }
  115.         goto def;
  116.  
  117.     case DIVIDE:
  118.     case ASDIV:
  119.     case ASTIMES:
  120.         if (tree->tr2->op==CON && tree->tr2->value==1)
  121.             return(tree->tr1);
  122.         if (ispow2(tree) == 0) {
  123.  
  124.         case MOD:
  125.         case ASMOD:
  126.             d1 =+ 2;
  127.             d2 =+ 2;
  128.         }
  129.         if (tree->type==LONG)
  130.             return(hardlongs(tree));
  131.         goto constant;
  132.  
  133.     case LSHIFT:
  134.     case RSHIFT:
  135.     case ASRSH:
  136.     case ASLSH:
  137.         if (tree->tr2->op==CON && tree->tr2->value==0)
  138.             return(tree->tr1);
  139.         /*
  140.          * PDP-11 special: turn right shifts into negative
  141.          * left shifts
  142.          */
  143.         if (op==LSHIFT||op==ASLSH)
  144.             goto constant;
  145.         if (tree->tr2->op==CON && tree->tr2->value==1)
  146.             goto constant;
  147.         op =+ (LSHIFT-RSHIFT);
  148.         tree->op = op;
  149.         tree->tr2 = block(1, NEG, tree->type, 0, tree->tr2);
  150.         goto again;
  151.  
  152.     constant:
  153.         if (tree->tr1->op==CON && tree->tr2->op==CON) {
  154.             const(op, &tree->tr1->value, tree->tr2->value);
  155.             return(tree->tr1);
  156.         }
  157.  
  158.  
  159.     def:
  160.     default:
  161.         tree->degree = d1==d2? d1+islong(tree->type): max(d1, d2);
  162.         break;
  163.     }
  164.     return(tree);
  165. }
  166.  
  167. unoptim(atree)
  168. struct tnode *atree;
  169. {
  170.     register struct tnode *subtre, *tree;
  171.     register int *p;
  172.     double static fv;
  173.     struct { int integer; };
  174.  
  175.     if ((tree=atree)==0)
  176.         return(0);
  177.     if (tree->op==CBRANCH) {
  178.         tree->btree = optim(tree->btree);
  179.         return(tree);
  180.     }
  181.     subtre = tree->tr1 = optim(tree->tr1);
  182.     switch (tree->op) {
  183.  
  184.     case FSEL:
  185.         tree->tr1 = block(2, RSHIFT, INT, 0, subtre,
  186.             block(1, CON, INT, 0, tree->bitoffs));
  187.         tree->op = AND;
  188.         tree->type = INT;
  189.         tree->tr2 = block(1, CON, INT, 0, (1<<tree->flen)-1);
  190.         return(optim(tree));
  191.  
  192.     case AMPER:
  193.         if (subtre->op==STAR)
  194.             return(subtre->tr1);
  195.         if (subtre->op==NAME && subtre->class == OFFS) {
  196.             p = block(2, PLUS, tree->type, 1, subtre, tree);
  197.             subtre->type = tree->type;
  198.             tree->op = CON;
  199.             tree->type = INT;
  200.             tree->degree = 0;
  201.             tree->value = subtre->offset;
  202.             subtre->class = REG;
  203.             subtre->nloc = subtre->regno;
  204.             subtre->offset = 0;
  205.             return(p);
  206.         }
  207.         break;
  208.  
  209.     case STAR:
  210.         if (subtre->op==AMPER)
  211.             return(subtre->tr1);
  212.         if (subtre->op==NAME && subtre->class==REG) {
  213.             subtre->type = tree->type;
  214.             subtre->class = OFFS;
  215.             subtre->regno = subtre->nloc;
  216.             return(subtre);
  217.         }
  218.         p = subtre->tr1;
  219.         if ((subtre->op==INCAFT||subtre->op==DECBEF)&&tree->type!=LONG
  220.          && p->op==NAME && p->class==REG && p->type==subtre->type) {
  221.             p->type = tree->type;
  222.             p->op = subtre->op==INCAFT? AUTOI: AUTOD;
  223.             return(p);
  224.         }
  225.         if (subtre->op==PLUS && p->op==NAME && p->class==REG) {
  226.             if (subtre->tr2->op==CON) {
  227.                 p->offset =+ subtre->tr2->value;
  228.                 p->class = OFFS;
  229.                 p->type = tree->type;
  230.                 p->regno = p->nloc;
  231.                 return(p);
  232.             }
  233.             if (subtre->tr2->op==AMPER) {
  234.                 subtre = subtre->tr2->tr1;
  235.                 subtre->class =+ XOFFS-EXTERN;
  236.                 subtre->regno = p->nloc;
  237.                 subtre->type = tree->type;
  238.                 return(subtre);
  239.             }
  240.         }
  241.         break;
  242.     case EXCLA:
  243.         if ((opdope[subtre->op]&RELAT)==0)
  244.             break;
  245.         tree = subtre;
  246.         tree->op = notrel[tree->op-EQUAL];
  247.         break;
  248.  
  249.     case NEG:
  250.     case COMPL:
  251.         if (tree->type==CHAR)
  252.             tree->type = INT;
  253.         if (tree->op == subtre->op)
  254.             return(subtre->tr1);
  255.         if (subtre->op==ITOL) {
  256.             subtre->op = tree->op;
  257.             subtre->type = INT;
  258.             tree->op = ITOL;
  259.         }
  260.     }
  261.     if (subtre->op == CON) switch(tree->op) {
  262.  
  263.     case NEG:
  264.         subtre->value = -subtre->value;
  265.         return(subtre);
  266.  
  267.     case COMPL:
  268.         subtre->value = ~subtre->value;
  269.         return(subtre);
  270.  
  271.     case ITOF:
  272.         fv = subtre->value;
  273.         p = &fv;
  274.         p++;
  275.         if (*p++==0 && *p++==0 && *p++==0) {
  276.             subtre->type = DOUBLE;
  277.             subtre->value = fv.integer;
  278.             subtre->op = SFCON;
  279.             return(subtre);
  280.         }
  281.         break;
  282.     }
  283.     tree->degree = max(islong(tree->type), degree(subtre));
  284.     return(tree);
  285. }
  286.  
  287. struct acl {
  288.     int nextl;
  289.     int nextn;
  290.     struct tnode *nlist[20];
  291.     struct tnode *llist[21];
  292. };
  293.  
  294. acommute(atree)
  295. {
  296.     struct acl acl;
  297.     int d, i, op, flt;
  298.     register struct tnode *t1, **t2, *tree;
  299.     struct tnode *t;
  300.  
  301.     acl.nextl = 0;
  302.     acl.nextn = 0;
  303.     tree = atree;
  304.     op = tree->op;
  305.     flt = isfloat(tree);
  306.     insert(op, tree, &acl);
  307.     acl.nextl--;
  308.     t2 = &acl.llist[acl.nextl];
  309.     if (!flt) {
  310.         /* put constants together */
  311.         for (i=acl.nextl;i>0&&t2[0]->op==CON&&t2[-1]->op==CON;i--) {
  312.             acl.nextl--;
  313.             t2--;
  314.             const(op, &t2[0]->value, t2[1]->value);
  315.         }
  316.     }
  317.     if (op==PLUS || op==OR) {
  318.         /* toss out "+0" */
  319.         if (acl.nextl>0 && (t1 = isconstant(*t2)) && t1->value==0) {
  320.             acl.nextl--;
  321.             t2--;
  322.         }
  323.         if (acl.nextl <= 0)
  324.             return(*t2);
  325.         /* subsume constant in "&x+c" */
  326.         if (op==PLUS && t2[0]->op==CON && t2[-1]->op==AMPER) {
  327.             t2--;
  328.             t2[0]->tr1->offset =+ t2[1]->value;
  329.             acl.nextl--;
  330.         }
  331.     } else if (op==TIMES || op==AND) {
  332.         t1 = acl.llist[acl.nextl];
  333.         if (t1->op==CON) {
  334.             if (t1->value==0)
  335.                 return(t1);
  336.             if (op==TIMES && t1->value==1 && acl.nextl>0)
  337.                 if (--acl.nextl <= 0)
  338.                     return(acl.llist[0]);
  339.         }
  340.     }
  341.     if (op==PLUS && !flt)
  342.         distrib(&acl);
  343.     tree = *(t2 = &acl.llist[0]);
  344.     d = max(degree(tree), islong(tree->type));
  345.     if (op==TIMES && !flt)
  346.         d++;
  347.     for (i=0; i<acl.nextl; i++) {
  348.         t1 = acl.nlist[i];
  349.         t1->tr2 = t = *++t2;
  350.         t1->degree = d = d==degree(t)? d+islong(t1->type): max(d, degree(t));
  351.         t1->tr1 = tree;
  352.         tree = t1;
  353.         if (tree->type==LONG) {
  354.             if (tree->op==TIMES)
  355.                 tree = hardlongs(tree);
  356.             else if (tree->op==PLUS && (t = isconstant(tree->tr1))
  357.                    && t->value < 0) {
  358.                 tree->op = MINUS;
  359.                 t->value = - t->value;
  360.                 t = tree->tr1;
  361.                 tree->tr1 = tree->tr2;
  362.                 tree->tr2 = t;
  363.             }
  364.         }
  365.     }
  366.     if (tree->op==TIMES && ispow2(tree))
  367.         tree->degree = max(degree(tree->tr1), islong(tree->type));
  368.     return(tree);
  369. }
  370.  
  371. distrib(list)
  372. struct acl *list;
  373. {
  374. /*
  375.  * Find a list member of the form c1c2*x such
  376.  * that c1c2 divides no other such constant, is divided by
  377.  * at least one other (say in the form c1*y), and which has
  378.  * fewest divisors. Reduce this pair to c1*(y+c2*x)
  379.  * and iterate until no reductions occur.
  380.  */
  381.     register struct tnode **p1, **p2;
  382.     struct tnode *t;
  383.     int ndmaj, ndmin;
  384.     struct tnode **dividend, **divisor;
  385.     struct tnode **maxnod, **mindiv;
  386.  
  387.     loop:
  388.     maxnod = &list->llist[list->nextl];
  389.     ndmaj = 1000;
  390.     dividend = 0;
  391.     for (p1 = list->llist; p1 <= maxnod; p1++) {
  392.         if ((*p1)->op!=TIMES || (*p1)->tr2->op!=CON)
  393.             continue;
  394.         ndmin = 0;
  395.         for (p2 = list->llist; p2 <= maxnod; p2++) {
  396.             if (p1==p2 || (*p2)->op!=TIMES || (*p2)->tr2->op!=CON)
  397.                 continue;
  398.             if ((*p1)->tr2->value == (*p2)->tr2->value) {
  399.                 (*p2)->tr2 = (*p1)->tr1;
  400.                 (*p2)->op = PLUS;
  401.                 (*p1)->tr1 = (*p2);
  402.                 *p1 = optim(*p1);
  403.                 squash(p2, maxnod);
  404.                 list->nextl--;
  405.                 goto loop;
  406.             }
  407.             if (((*p2)->tr2->value % (*p1)->tr2->value) == 0)
  408.                 goto contmaj;
  409.             if (((*p1)->tr2->value % (*p2)->tr2->value) == 0) {
  410.                 ndmin++;
  411.                 mindiv = p2;
  412.             }
  413.         }
  414.         if (ndmin > 0 && ndmin < ndmaj) {
  415.             ndmaj = ndmin;
  416.             dividend = p1;
  417.             divisor = mindiv;
  418.         }
  419.     contmaj:;
  420.     }
  421.     if (dividend==0)
  422.         return;
  423.     t = list->nlist[--list->nextn];
  424.     p1 = dividend;
  425.     p2 = divisor;
  426.     t->op = PLUS;
  427.     t->type = (*p1)->type;
  428.     t->tr1 = (*p1);
  429.     t->tr2 = (*p2)->tr1;
  430.     (*p1)->tr2->value =/ (*p2)->tr2->value;
  431.     (*p2)->tr1 = t;
  432.     t = optim(*p2);
  433.     if (p1 < p2) {
  434.         *p1 = t;
  435.         squash(p2, maxnod);
  436.     } else {
  437.         *p2 = t;
  438.         squash(p1, maxnod);
  439.     }
  440.     list->nextl--;
  441.     goto loop;
  442. }
  443.  
  444. squash(p, maxp)
  445. struct tnode **p, **maxp;
  446. {
  447.     register struct tnode **np;
  448.  
  449.     for (np = p; np < maxp; np++)
  450.         *np = *(np+1);
  451. }
  452.  
  453. const(op, vp, av)
  454. int *vp;
  455. {
  456.     register int v;
  457.  
  458.     v = av;
  459.     switch (op) {
  460.  
  461.     case PLUS:
  462.         *vp =+ v;
  463.         return;
  464.  
  465.     case TIMES:
  466.         *vp =* v;
  467.         return;
  468.  
  469.     case AND:
  470.         *vp =& v;
  471.         return;
  472.  
  473.     case OR:
  474.         *vp =| v;
  475.         return;
  476.  
  477.     case EXOR:
  478.         *vp =^ v;
  479.         return;
  480.  
  481.     case DIVIDE:
  482.     case MOD:
  483.         if (v==0)
  484.             error("Divide check");
  485.         else
  486.             if (op==DIVIDE)
  487.                 *vp =/ v;
  488.             else
  489.                 *vp =% v;
  490.         return;
  491.  
  492.     case RSHIFT:
  493.         *vp =>> v;
  494.         return;
  495.  
  496.     case LSHIFT:
  497.         *vp =<< v;
  498.         return;
  499.  
  500.     case NAND:
  501.         *vp =& ~ v;
  502.         return;
  503.     }
  504.     error("C error: const");
  505. }
  506.  
  507. insert(op, atree, alist)
  508. struct acl *alist;
  509. {
  510.     register d;
  511.     register struct acl *list;
  512.     register struct tnode *tree;
  513.     int d1, i;
  514.     struct tnode *t;
  515.  
  516.     tree = atree;
  517.     list = alist;
  518.     if (tree->op == op) {
  519.     ins:    list->nlist[list->nextn++] = tree;
  520.         insert(op, tree->tr1, list);
  521.         insert(op, tree->tr2, list);
  522.         return;
  523.     }
  524.     tree = optim(tree);
  525.     if (tree->op == op)
  526.         goto ins;
  527.     if (!isfloat(tree)) {
  528.         /* c1*(x+c2) -> c1*x+c1*c2 */
  529.         if ((tree->op==TIMES||tree->op==LSHIFT)
  530.           && tree->tr2->op==CON && tree->tr2->value>0
  531.           && tree->tr1->op==PLUS && tree->tr1->tr2->op==CON) {
  532.             d = tree->tr2->value;
  533.             if (tree->op==TIMES)
  534.                 tree->tr2->value =* tree->tr1->tr2->value;
  535.             else
  536.                 tree->tr2->value = tree->tr1->tr2->value << d;
  537.             tree->tr1->tr2->value = d;
  538.             tree->tr1->op = tree->op;
  539.             tree->op = PLUS;
  540.             if (op==PLUS)
  541.                 goto ins;
  542.         }
  543.     }
  544.     d = degree(tree);
  545.     for (i=0; i<list->nextl; i++) {
  546.         if ((d1=degree(list->llist[i]))<d) {
  547.             t = list->llist[i];
  548.             list->llist[i] = tree;
  549.             tree = t;
  550.             d = d1;
  551.         }
  552.     }
  553.     list->llist[list->nextl++] = tree;
  554. }
  555.  
  556. block(an, args)
  557. {
  558.     register int *p;
  559.     int *oldp;
  560.     register *argp, n;
  561.  
  562.     oldp = p = spacep;
  563.     n = an+3;
  564.     argp = &args;
  565.     do
  566.         *p++ = *argp++;
  567.     while (--n);
  568.     if (p >= &treespace[ossiz]) {
  569.         error("Exp. ov. pass 2");
  570.         exit(1);
  571.     }
  572.     spacep = p;
  573.     return(oldp);
  574. }
  575.  
  576. islong(t)
  577. {
  578.     if (t==LONG)
  579.         return(2);
  580.     return(1);
  581. }
  582.  
  583. isconstant(at)
  584. struct tnode *at;
  585. {
  586.     register struct tnode *t;
  587.  
  588.     t = at;
  589.     if (t->op==CON || t->op==SFCON)
  590.         return(t);
  591.     if (t->op==ITOL && t->tr1->op==CON)
  592.         return(t->tr1);
  593.     return(0);
  594. }
  595.  
  596. hardlongs(at)
  597. struct tnode *at;
  598. {
  599.     register struct tnode *t;
  600.  
  601.     t = at;
  602.     switch(t->op) {
  603.  
  604.     case TIMES:
  605.     case DIVIDE:
  606.     case MOD:
  607.         t->op =+ LTIMES-TIMES;
  608.         break;
  609.  
  610.     case ASTIMES:
  611.     case ASDIV:
  612.     case ASMOD:
  613.         t->op =+ LASTIMES-ASTIMES;
  614.         t->tr1 = block(1, AMPER, LONG+PTR, 0, t->tr1);
  615.         break;
  616.  
  617.     default:
  618.         return(t);
  619.     }
  620.     return(optim(t));
  621. }
  622.