home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / c / c12.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-05-16  |  20.2 KB  |  1,081 lines
  1. #
  2. /*
  3.  *        C compiler part 2 -- expression optimizer
  4.  *
  5.  */
  6.  
  7. #include "c1.h"
  8.  
  9. optim(atree)
  10. struct tnode *atree;
  11. {
  12.     struct { int intx[4]; };
  13.     register op, dope;
  14.     int d1, d2;
  15.     struct tnode *t;
  16.     register struct tnode *tree;
  17.  
  18.     if ((tree=atree)==0)
  19.         return(0);
  20.     if ((op = tree->op)==0)
  21.         return(tree);
  22.     if (op==NAME && tree->class==AUTO) {
  23.         tree->class = OFFS;
  24.         tree->regno = 5;
  25.         tree->offset = tree->nloc;
  26.     }
  27.     dope = opdope[op];
  28.     if ((dope&LEAF) != 0) {
  29.         if (op==FCON
  30.          && tree->fvalue.intx[1]==0
  31.          && tree->fvalue.intx[2]==0
  32.          && tree->fvalue.intx[3]==0) {
  33.             tree->op = SFCON;
  34.             tree->value = tree->fvalue.intx[0];
  35.         }
  36.         return(tree);
  37.     }
  38.     if ((dope&BINARY) == 0)
  39.         return(unoptim(tree));
  40.     /* is known to be binary */
  41.     if (tree->type==CHAR)
  42.         tree->type = INT;
  43.     switch(op) {
  44.     /*
  45.      * PDP-11 special:
  46.      * generate new =&~ operator out of =&
  47.      * by complementing the RHS.
  48.      */
  49.     case ASAND:
  50.         tree->op = ASANDN;
  51.         tree->tr2 = tnode(COMPL, tree->tr2->type, tree->tr2);
  52.         break;
  53.  
  54.     /*
  55.      * On the PDP-11, int->ptr via multiplication
  56.      * Longs are just truncated.
  57.      */
  58.     case LTOP:
  59.         tree->op = ITOP;
  60.         tree->tr1 = unoptim(tnode(LTOI,INT,tree->tr1));
  61.     case ITOP:
  62.         tree->op = TIMES;
  63.         break;
  64.  
  65.     case MINUS:
  66.         if ((t = isconstant(tree->tr2)) && (t->type!=UNSIGN || tree->type!=LONG)) {
  67.             tree->op = PLUS;
  68.             if (t->type==DOUBLE)
  69.                 /* PDP-11 FP representation */
  70.                 t->value =^ 0100000;
  71.             else
  72.                 t->value = -t->value;
  73.         }
  74.         break;
  75.     }
  76.     op = tree->op;
  77.     dope = opdope[op];
  78.     if (dope&LVALUE && tree->tr1->op==FSEL)
  79.         return(lvfield(tree));
  80.     if ((dope&COMMUTE)!=0) {
  81.         d1 = tree->type;
  82.         tree = acommute(tree);
  83.         if (tree->op == op)
  84.             tree->type = d1;
  85.         /*
  86.          * PDP-11 special:
  87.          * replace a&b by a ANDN ~ b.
  88.          * This will be undone when in
  89.          * truth-value context.
  90.          */
  91.         if (tree->op!=AND)
  92.             return(tree);
  93.         /*
  94.          * long & pos-int is simpler
  95.          */
  96.         if (tree->type==LONG && tree->tr2->op==ITOL
  97.          && (tree->tr2->tr1->op==CON && tree->tr2->tr1->value>=0
  98.            || tree->tr2->tr1->type==UNSIGN)) {
  99.             tree->type = UNSIGN;
  100.             t = tree->tr2;
  101.             tree->tr2 = tree->tr2->tr1;
  102.             t->tr1 = tree;
  103.             tree->tr1 = tnode(LTOI, UNSIGN, tree->tr1);
  104.             return(optim(t));
  105.         }
  106.         /*
  107.          * Keep constants to the right
  108.          */
  109.         if ((tree->tr1->op==ITOL && tree->tr1->tr1->op==CON)
  110.           || tree->tr1->op==LCON) {
  111.             t = tree->tr1;
  112.             tree->tr1 = tree->tr2;
  113.             tree->tr2 = t;
  114.         }
  115.         tree->op = ANDN;
  116.         op = ANDN;
  117.         tree->tr2 = tnode(COMPL, tree->tr2->type, tree->tr2);
  118.     }
  119.     again:
  120.     tree->tr1 = optim(tree->tr1);
  121.     tree->tr2 = optim(tree->tr2);
  122.     if (tree->type == LONG) {
  123.         t = lconst(tree->op, tree->tr1, tree->tr2);
  124.         if (t)
  125.             return(t);
  126.     }
  127.     if ((dope&RELAT) != 0) {
  128.         if ((d1=degree(tree->tr1)) < (d2=degree(tree->tr2))
  129.          || d1==d2 && tree->tr1->op==NAME && tree->tr2->op!=NAME) {
  130.             t = tree->tr1;
  131.             tree->tr1 = tree->tr2;
  132.             tree->tr2 = t;
  133.             tree->op = maprel[op-EQUAL];
  134.         }
  135.         if (tree->tr1->type==CHAR && tree->tr2->op==CON
  136.          && (dcalc(tree->tr1, 0) <= 12 || tree->tr1->op==STAR)
  137.          && tree->tr2->value <= 127 && tree->tr2->value >= 0)
  138.             tree->tr2->type = CHAR;
  139.     }
  140.     d1 = max(degree(tree->tr1), islong(tree->type));
  141.     d2 = max(degree(tree->tr2), 0);
  142.     switch (op) {
  143.  
  144.     /*
  145.      * In assignment to fields, treat all-zero and all-1 specially.
  146.      */
  147.     case FSELA:
  148.         if (tree->tr2->op==CON && tree->tr2->value==0) {
  149.             tree->op = ASAND;
  150.             tree->tr2->value = ~tree->mask;
  151.             return(optim(tree));
  152.         }
  153.         if (tree->tr2->op==CON && tree->mask==tree->tr2->value) {
  154.             tree->op = ASOR;
  155.             return(optim(tree));
  156.         }
  157.  
  158.     case LTIMES:
  159.     case LDIV:
  160.     case LMOD:
  161.     case LASTIMES:
  162.     case LASDIV:
  163.     case LASMOD:
  164.         tree->degree = 10;
  165.         break;
  166.  
  167.     case ANDN:
  168.         if (isconstant(tree->tr2) && tree->tr2->value==0) {
  169.             return(tree->tr1);
  170.         }
  171.         goto def;
  172.  
  173.     case CALL:
  174.         tree->degree = 10;
  175.         break;
  176.  
  177.     case QUEST:
  178.     case COLON:
  179.         tree->degree = max(d1, d2);
  180.         break;
  181.  
  182.     case DIVIDE:
  183.     case ASDIV:
  184.     case ASTIMES:
  185.     case PTOI:
  186.         if (tree->tr2->op==CON && tree->tr2->value==1)
  187.             return(tree->tr1);
  188.     case MOD:
  189.     case ASMOD:
  190.         if (tree->tr1->type==UNSIGN && ispow2(tree))
  191.             return(pow2(tree));
  192.         if ((op==MOD||op==ASMOD) && tree->type==DOUBLE) {
  193.             error("Floating %% not defined");
  194.             tree->type = INT;
  195.         }
  196.     case ULSH:
  197.     case ASULSH:
  198.         d1 =+ 2;
  199.         d2 =+ 2;
  200.         if (tree->type==LONG)
  201.             return(hardlongs(tree));
  202.         goto constant;
  203.  
  204.     case LSHIFT:
  205.     case RSHIFT:
  206.     case ASRSH:
  207.     case ASLSH:
  208.         if (tree->tr2->op==CON && tree->tr2->value==0) {
  209.             return(tree->tr1);
  210.         }
  211.         /*
  212.          * PDP-11 special: turn right shifts into negative
  213.          * left shifts
  214.          */
  215.         if (tree->type == LONG) {
  216.             d1++;
  217.             d2++;
  218.         }
  219.         if (op==LSHIFT||op==ASLSH)
  220.             goto constant;
  221.         if (tree->tr2->op==CON && tree->tr2->value==1
  222.          && tree->tr1->type!=UNSIGN)
  223.             goto constant;
  224.         op =+ (LSHIFT-RSHIFT);
  225.         tree->op = op;
  226.         tree->tr2 = tnode(NEG, tree->type, tree->tr2);
  227.         if (tree->tr1->type==UNSIGN) {
  228.             if (tree->op==LSHIFT)
  229.                 tree->op = ULSH;
  230.             else if (tree->op==ASLSH)
  231.                 tree->op = ASULSH;
  232.         }
  233.         goto again;
  234.  
  235.     constant:
  236.         if (tree->tr1->op==CON && tree->tr2->op==CON) {
  237.             const(op, &tree->tr1->value, tree->tr2->value);
  238.             return(tree->tr1);
  239.         }
  240.  
  241.  
  242.     def:
  243.     default:
  244.         if (dope&RELAT) {
  245.             if (tree->tr1->type==LONG)    /* long relations are a mess */
  246.                 d1 = 10;
  247.             if (opdope[tree->tr1->op]&RELAT && tree->tr2->op==CON
  248.              && tree->tr2->value==0) {
  249.                 tree = tree->tr1;
  250.                 switch(op) {
  251.                 case GREATEQ:
  252.                     return(&cone);
  253.                 case LESS:
  254.                     return(&czero);
  255.                 case LESSEQ:
  256.                 case EQUAL:
  257.                     tree->op = notrel[tree->op-EQUAL];
  258.                 }
  259.                 return(tree);
  260.             }
  261.         }
  262.         tree->degree = d1==d2? d1+islong(tree->type): max(d1, d2);
  263.         break;
  264.     }
  265.     return(tree);
  266. }
  267.  
  268. unoptim(atree)
  269. struct tnode *atree;
  270. {
  271.     struct { int intx[4]; };
  272.     register struct tnode *subtre, *tree;
  273.     register int *p;
  274.     double static fv;
  275.     struct ftconst *fp;
  276.  
  277.     if ((tree=atree)==0)
  278.         return(0);
  279.     again:
  280.     if (tree->op==AMPER && tree->tr1->op==STAR) {
  281.         subtre = tree->tr1->tr1;
  282.         subtre->type = tree->type;
  283.         return(optim(subtre));
  284.     }
  285.     subtre = tree->tr1 = optim(tree->tr1);
  286.     switch (tree->op) {
  287.  
  288.     case ITOL:
  289.         if (subtre->op==CON && subtre->type==INT && subtre->value<0) {
  290.             subtre = getblk(sizeof(struct lconst));
  291.             subtre->op = LCON;
  292.             subtre->type = LONG;
  293.             subtre->lvalue = tree->tr1->value;
  294.             return(subtre);
  295.         }
  296.         break;
  297.  
  298.     case FTOI:
  299.         if (tree->type==UNSIGN) {
  300.             tree->op = FTOL;
  301.             tree->type = LONG;
  302.             tree = tnode(LTOI, UNSIGN, tree);
  303.         }
  304.         break;
  305.  
  306.     case LTOF:
  307.         if (subtre->op==LCON) {
  308.             tree = getblk(sizeof(*fp));
  309.             tree->op = FCON;
  310.             tree->type = DOUBLE;
  311.             tree->value = isn++;
  312.             tree->fvalue = subtre->lvalue;
  313.             return(optim(tree));
  314.         }
  315.         break;
  316.  
  317.     case ITOF:
  318.         if (tree->tr1->type==UNSIGN) {
  319.             tree->tr1 = tnode(ITOL, LONG, tree->tr1);
  320.             tree->op = LTOF;
  321.             tree = optim(tree);
  322.         }
  323.         if (subtre->op!=CON)
  324.             break;
  325.         fv = subtre->value;
  326.         p = &fv;
  327.         p++;
  328.         if (*p++==0 && *p++==0 && *p++==0) {
  329.             tree = getblk(sizeof(*fp));
  330.             tree->op = SFCON;
  331.             tree->type = DOUBLE;
  332.             tree->value = * (int *) &fv;
  333.             tree->fvalue = fv;
  334.             return(tree);
  335.         }
  336.         break;
  337.  
  338.     case ITOC:
  339.         p = tree->tr1;
  340.         /*
  341.          * Sign-extend PDP-11 characters
  342.          */
  343.         if (p->op==CON) {
  344.             p->value = p->value << 8 >> 8;
  345.             return(p);
  346.         } else if (p->op==NAME) {
  347.             p->type = CHAR;
  348.             return(p);
  349.         }
  350.         break;
  351.  
  352.     case LTOI:
  353.         p = tree->tr1;
  354.         switch (p->op) {
  355.  
  356.         case LCON:
  357.             p->op = CON;
  358.             p->type = tree->type;
  359.             p->value = p->lvalue;
  360.             return(p);
  361.  
  362.         case NAME:
  363.             p->offset =+ 2;
  364.             p->type = tree->type;
  365.             return(p);
  366.  
  367.         case STAR:
  368.             p->type = tree->type;
  369.             p->tr1->type = tree->type+PTR;
  370.             p->tr1 = tnode(PLUS, tree->type, p->tr1, tconst(2, INT));
  371.             return(optim(p));
  372.  
  373.         case ITOL:
  374.             return(p->tr1);
  375.  
  376.         case PLUS:
  377.         case MINUS:
  378.         case AND:
  379.         case ANDN:
  380.         case OR:
  381.         case EXOR:
  382.             p->tr2 = tnode(LTOI, tree->type, p->tr2);
  383.         case NEG:
  384.         case COMPL:
  385.             p->tr1 = tnode(LTOI, tree->type, p->tr1);
  386.             p->type = tree->type;
  387.             return(optim(p));
  388.         }
  389.         break;
  390.  
  391.     case FSEL:
  392.         tree->op = AND;
  393.         tree->tr1 = tree->tr2->tr1;
  394.         tree->tr2->tr1 = subtre;
  395.         tree->tr2->op = RSHIFT;
  396.         tree->tr1->value = (1 << tree->tr1->value) - 1;
  397.         return(optim(tree));
  398.  
  399.     case FSELR:
  400.         tree->op = LSHIFT;
  401.         tree->type = UNSIGN;
  402.         tree->tr1 = tree->tr2;
  403.         tree->tr1->op = AND;
  404.         tree->tr2 = tree->tr2->tr2;
  405.         tree->tr1->tr2 = subtre;
  406.         tree->tr1->tr1->value = (1 << tree->tr1->tr1->value) -1;
  407.         return(optim(tree));
  408.  
  409.     case AMPER:
  410.         if (subtre->op==STAR)
  411.             return(subtre->tr1);
  412.         if (subtre->op==NAME && subtre->class == OFFS) {
  413.             p = tnode(PLUS, tree->type, subtre, tree);
  414.             subtre->type = tree->type;
  415.             tree->op = CON;
  416.             tree->type = INT;
  417.             tree->degree = 0;
  418.             tree->value = subtre->offset;
  419.             subtre->class = REG;
  420.             subtre->nloc = subtre->regno;
  421.             subtre->offset = 0;
  422.             return(optim(p));
  423.         }
  424.         break;
  425.  
  426.     case STAR:
  427.         if (subtre->op==AMPER) {
  428.             subtre->tr1->type = tree->type;
  429.             return(subtre->tr1);
  430.         }
  431.         if (tree->type==STRUCT)
  432.             break;
  433.         if (subtre->op==NAME && subtre->class==REG) {
  434.             subtre->type = tree->type;
  435.             subtre->class = OFFS;
  436.             subtre->regno = subtre->nloc;
  437.             return(subtre);
  438.         }
  439.         p = subtre->tr1;
  440.         if ((subtre->op==INCAFT||subtre->op==DECBEF)&&tree->type!=LONG
  441.          && p->op==NAME && p->class==REG && p->type==subtre->type) {
  442.             p->type = tree->type;
  443.             p->op = subtre->op==INCAFT? AUTOI: AUTOD;
  444.             return(p);
  445.         }
  446.         if (subtre->op==PLUS && p->op==NAME && p->class==REG) {
  447.             if (subtre->tr2->op==CON) {
  448.                 p->offset =+ subtre->tr2->value;
  449.                 p->class = OFFS;
  450.                 p->type = tree->type;
  451.                 p->regno = p->nloc;
  452.                 return(p);
  453.             }
  454.             if (subtre->tr2->op==AMPER) {
  455.                 subtre = subtre->tr2->tr1;
  456.                 subtre->class =+ XOFFS-EXTERN;
  457.                 subtre->regno = p->nloc;
  458.                 subtre->type = tree->type;
  459.                 return(subtre);
  460.             }
  461.         }
  462.         break;
  463.     case EXCLA:
  464.         if ((opdope[subtre->op]&RELAT)==0)
  465.             break;
  466.         tree = subtre;
  467.         tree->op = notrel[tree->op-EQUAL];
  468.         break;
  469.  
  470.     case COMPL:
  471.         if (tree->type==CHAR)
  472.             tree->type = INT;
  473.         if (tree->op == subtre->op)
  474.             return(subtre->tr1);
  475.         if (subtre->op==CON) {
  476.             subtre->value = ~subtre->value;
  477.             return(subtre);
  478.         }
  479.         if (subtre->op==LCON) {
  480.             subtre->lvalue = ~subtre->lvalue;
  481.             return(subtre);
  482.         }
  483.         if (subtre->op==ITOL) {
  484.             if (subtre->tr1->op==CON) {
  485.                 tree = getblk(sizeof(struct lconst));
  486.                 tree->op = LCON;
  487.                 tree->type = LONG;
  488.                 if (subtre->tr1->type==UNSIGN)
  489.                     tree->lvalue = ~(long)(unsigned)subtre->tr1->value;
  490.                 else
  491.                     tree->lvalue = ~subtre->tr1->value;
  492.                 return(tree);
  493.             }
  494.             if (subtre->tr1->type==UNSIGN)
  495.                 break;
  496.             subtre->op = tree->op;
  497.             subtre->type = subtre->tr1->type;
  498.             tree->op = ITOL;
  499.             tree->type = LONG;
  500.             goto again;
  501.         }
  502.  
  503.     case NEG:
  504.         if (tree->type==CHAR)
  505.             tree->type = INT;
  506.         if (tree->op==subtre->op)
  507.             return(subtre->tr1);
  508.         if (subtre->op==CON) {
  509.             subtre->value = -subtre->value;
  510.             return(subtre);
  511.         }
  512.         if (subtre->op==LCON) {
  513.             subtre->lvalue = -subtre->lvalue;
  514.             return(subtre);
  515.         }
  516.         if (subtre->op==ITOL && subtre->tr1->op==CON) {
  517.             tree = getblk(sizeof(struct lconst));
  518.             tree->op = LCON;
  519.             tree->type = LONG;
  520.             if (subtre->tr1->type==UNSIGN)
  521.                 tree->lvalue = -(long)(unsigned)subtre->tr1->value;
  522.             else
  523.                 tree->lvalue = -subtre->tr1->value;
  524.             return(tree);
  525.         }
  526.         /*
  527.          * PDP-11 FP negation
  528.          */
  529.         if (subtre->op==SFCON) {
  530.             subtre->value =^ 0100000;
  531.             subtre->fvalue.intx[0] =^ 0100000;
  532.             return(subtre);
  533.         }
  534.         if (subtre->op==FCON) {
  535.             subtre->fvalue.intx[0] =^ 0100000;
  536.             return(subtre);
  537.         }
  538.     }
  539.     if ((opdope[tree->op]&LEAF)==0)
  540.         tree->degree = max(islong(tree->type), degree(subtre));
  541.     return(tree);
  542. }
  543.  
  544. /*
  545.  * Deal with assignments to partial-word fields.
  546.  * The game is that select(x) =+ y turns into
  547.  * select(x =+ select(y)) where the shifts and masks
  548.  * are chosen properly.  The outer select
  549.  * is discarded where the value doesn't matter.
  550.  * Sadly, overflow is undetected on =+ and the like.
  551.  * Pure assignment is handled specially.
  552.  */
  553.  
  554. lvfield(at)
  555. struct tnode *at;
  556. {
  557.     register struct tnode *t, *t1;
  558.     register struct fasgn *t2;
  559.  
  560.     t = at;
  561.     switch (t->op) {
  562.  
  563.     case ASSIGN:
  564.         t2 = getblk(sizeof(*t2));
  565.         t2->op = FSELA;
  566.         t2->type = UNSIGN;
  567.         t1 = t->tr1->tr2;
  568.         t2->mask = ((1<<t1->tr1->value)-1)<<t1->tr2->value;
  569.         t2->tr1 = t->tr1;
  570.         t2->tr2 = t->tr2;
  571.         t = t2;
  572.  
  573.     case ASANDN:
  574.     case ASPLUS:
  575.     case ASMINUS:
  576.     case ASOR:
  577.     case ASXOR:
  578.     case INCBEF:
  579.     case INCAFT:
  580.     case DECBEF:
  581.     case DECAFT:
  582.         t1 = t->tr1;
  583.         t1->op = FSELR;
  584.         t->tr1 = t1->tr1;
  585.         t1->tr1 = t->tr2;
  586.         t->tr2 = t1;
  587.         t1 = t1->tr2;
  588.         t1 = tnode(COMMA, INT, tconst(t1->tr1->value, INT),
  589.             tconst(t1->tr2->value, INT));
  590.         return(optim(tnode(FSELT, UNSIGN, t, t1)));
  591.  
  592.     }
  593.     error("Unimplemented field operator");
  594.     return(t);
  595. }
  596.  
  597. #define    LSTSIZ    20
  598. struct acl {
  599.     int nextl;
  600.     int nextn;
  601.     struct tnode *nlist[LSTSIZ];
  602.     struct tnode *llist[LSTSIZ+1];
  603. };
  604.  
  605. acommute(atree)
  606. {
  607.     struct acl acl;
  608.     int d, i, op, flt, d1;
  609.     register struct tnode *t1, **t2, *tree;
  610.     struct tnode *t;
  611.  
  612.     acl.nextl = 0;
  613.     acl.nextn = 0;
  614.     tree = atree;
  615.     op = tree->op;
  616.     flt = isfloat(tree);
  617.     insert(op, tree, &acl);
  618.     acl.nextl--;
  619.     t2 = &acl.llist[acl.nextl];
  620.     if (!flt) {
  621.         /* put constants together */
  622.         for (i=acl.nextl; i>0; i--) {
  623.             if (t2[0]->op==CON && t2[-1]->op==CON) {
  624.                 acl.nextl--;
  625.                 t2--;
  626.                 const(op, &t2[0]->value, t2[1]->value);
  627.             } else if (t = lconst(op, t2[-1], t2[0])) {
  628.                 acl.nextl--;
  629.                 t2--;
  630.                 t2[0] = t;
  631.             }
  632.         }
  633.     }
  634.     if (op==PLUS || op==OR) {
  635.         /* toss out "+0" */
  636.         if (acl.nextl>0 && (t1 = isconstant(*t2)) && t1->value==0
  637.          || (*t2)->op==LCON && (*t2)->lvalue==0) {
  638.             acl.nextl--;
  639.             t2--;
  640.         }
  641.         if (acl.nextl <= 0) {
  642.             if ((*t2)->type==CHAR)
  643.                 *t2 = tnode(LOAD, tree->type, *t2, NULL);
  644.             (*t2)->type = tree->type;
  645.             return(*t2);
  646.         }
  647.         /* subsume constant in "&x+c" */
  648.         if (op==PLUS && t2[0]->op==CON && t2[-1]->op==AMPER) {
  649.             t2--;
  650.             t2[0]->tr1->offset =+ t2[1]->value;
  651.             acl.nextl--;
  652.         }
  653.     } else if (op==TIMES || op==AND) {
  654.         t1 = acl.llist[acl.nextl];
  655.         if (t1->op==CON) {
  656.             if (t1->value==0)
  657.                 return(t1);
  658.             if (op==TIMES && t1->value==1 && acl.nextl>0)
  659.                 if (--acl.nextl <= 0) {
  660.                     t1 = acl.llist[0];
  661.                     if (tree->type == UNSIGN)
  662.                         t1->type = tree->type;
  663.                     return(t1);
  664.                 }
  665.         }
  666.     }
  667.     if (op==PLUS && !flt)
  668.         distrib(&acl);
  669.     tree = *(t2 = &acl.llist[0]);
  670.     d = max(degree(tree), islong(tree->type));
  671.     if (op==TIMES && !flt)
  672.         d++;
  673.     for (i=0; i<acl.nextl; i++) {
  674.         t1 = acl.nlist[i];
  675.         t1->tr2 = t = *++t2;
  676.         d1 = degree(t);
  677.         /*
  678.          * PDP-11 strangeness:
  679.          * rt. op of ^ must be in a register.
  680.          */
  681.         if (op==EXOR && dcalc(t, 0)<=12) {
  682.             t1->tr2 = t = optim(tnode(LOAD, t->type, t));
  683.             d1 = t->degree;
  684.         }
  685.         t1->degree = d = d==d1? d+islong(t1->type): max(d, d1);
  686.         t1->tr1 = tree;
  687.         tree = t1;
  688.         if (tree->type==LONG) {
  689.             if (tree->op==TIMES)
  690.                 tree = hardlongs(tree);
  691.             else if (tree->op==PLUS && (t = isconstant(tree->tr1))
  692.                    && t->value < 0 && t->type!=UNSIGN) {
  693.                 tree->op = MINUS;
  694.                 t->value = - t->value;
  695.                 t = tree->tr1;
  696.                 tree->tr1 = tree->tr2;
  697.                 tree->tr2 = t;
  698.             }
  699.         }
  700.     }
  701.     if (tree->op==TIMES && ispow2(tree))
  702.         tree->degree = max(degree(tree->tr1), islong(tree->type));
  703.     return(tree);
  704. }
  705.  
  706. distrib(list)
  707. struct acl *list;
  708. {
  709. /*
  710.  * Find a list member of the form c1c2*x such
  711.  * that c1c2 divides no other such constant, is divided by
  712.  * at least one other (say in the form c1*y), and which has
  713.  * fewest divisors. Reduce this pair to c1*(y+c2*x)
  714.  * and iterate until no reductions occur.
  715.  */
  716.     register struct tnode **p1, **p2;
  717.     struct tnode *t;
  718.     int ndmaj, ndmin;
  719.     struct tnode **dividend, **divisor;
  720.     struct tnode **maxnod, **mindiv;
  721.  
  722.     loop:
  723.     maxnod = &list->llist[list->nextl];
  724.     ndmaj = 1000;
  725.     dividend = 0;
  726.     for (p1 = list->llist; p1 <= maxnod; p1++) {
  727.         if ((*p1)->op!=TIMES || (*p1)->tr2->op!=CON)
  728.             continue;
  729.         ndmin = 0;
  730.         for (p2 = list->llist; p2 <= maxnod; p2++) {
  731.             if (p1==p2 || (*p2)->op!=TIMES || (*p2)->tr2->op!=CON)
  732.                 continue;
  733.             if ((*p1)->tr2->value == (*p2)->tr2->value) {
  734.                 (*p2)->tr2 = (*p1)->tr1;
  735.                 (*p2)->op = PLUS;
  736.                 (*p1)->tr1 = (*p2);
  737.                 *p1 = optim(*p1);
  738.                 squash(p2, maxnod);
  739.                 list->nextl--;
  740.                 goto loop;
  741.             }
  742.             if (((*p2)->tr2->value % (*p1)->tr2->value) == 0)
  743.                 goto contmaj;
  744.             if (((*p1)->tr2->value % (*p2)->tr2->value) == 0) {
  745.                 ndmin++;
  746.                 mindiv = p2;
  747.             }
  748.         }
  749.         if (ndmin > 0 && ndmin < ndmaj) {
  750.             ndmaj = ndmin;
  751.             dividend = p1;
  752.             divisor = mindiv;
  753.         }
  754.     contmaj:;
  755.     }
  756.     if (dividend==0)
  757.         return;
  758.     t = list->nlist[--list->nextn];
  759.     p1 = dividend;
  760.     p2 = divisor;
  761.     t->op = PLUS;
  762.     t->type = (*p1)->type;
  763.     t->tr1 = (*p1);
  764.     t->tr2 = (*p2)->tr1;
  765.     (*p1)->tr2->value =/ (*p2)->tr2->value;
  766.     (*p2)->tr1 = t;
  767.     t = optim(*p2);
  768.     if (p1 < p2) {
  769.         *p1 = t;
  770.         squash(p2, maxnod);
  771.     } else {
  772.         *p2 = t;
  773.         squash(p1, maxnod);
  774.     }
  775.     list->nextl--;
  776.     goto loop;
  777. }
  778.  
  779. squash(p, maxp)
  780. struct tnode **p, **maxp;
  781. {
  782.     register struct tnode **np;
  783.  
  784.     for (np = p; np < maxp; np++)
  785.         *np = *(np+1);
  786. }
  787.  
  788. const(op, vp, av)
  789. int *vp;
  790. {
  791.     register int v;
  792.     struct { unsigned u;};
  793.  
  794.     v = av;
  795.     switch (op) {
  796.  
  797.     case PTOI:
  798.         (*vp).u =/ v;
  799.         return;
  800.  
  801.     case PLUS:
  802.         *vp =+ v;
  803.         return;
  804.  
  805.     case TIMES:
  806.         *vp =* v;
  807.         return;
  808.  
  809.     case AND:
  810.         *vp =& v;
  811.         return;
  812.  
  813.     case OR:
  814.         *vp =| v;
  815.         return;
  816.  
  817.     case EXOR:
  818.         *vp =^ v;
  819.         return;
  820.  
  821.     case DIVIDE:
  822.     case MOD:
  823.         if (v==0)
  824.             error("Divide check");
  825.         else
  826.             if (op==DIVIDE)
  827.                 *vp =/ v;
  828.             else
  829.                 *vp =% v;
  830.         return;
  831.  
  832.     case RSHIFT:
  833.         *vp =>> v;
  834.         return;
  835.  
  836.     case LSHIFT:
  837.         *vp =<< v;
  838.         return;
  839.  
  840.     case ANDN:
  841.         *vp =& ~ v;
  842.         return;
  843.     }
  844.     error("C error: const");
  845. }
  846.  
  847. struct tnode *
  848. lconst(op, lp, rp)
  849. register struct tnode *lp, *rp;
  850. {
  851.     long l, r;
  852.  
  853.     if (lp->op==LCON)
  854.         l = lp->lvalue;
  855.     else if (lp->op==ITOL && lp->tr1->op==CON) {
  856.         if (lp->tr1->type==INT)
  857.             l = lp->tr1->value;
  858.         else
  859.             l = (unsigned)lp->tr1->value;
  860.     } else
  861.         return(0);
  862.     if (rp->op==LCON)
  863.         r = rp->lvalue;
  864.     else if (rp->op==ITOL && rp->tr1->op==CON) {
  865.         if (rp->tr1->type==INT)
  866.             r = rp->tr1->value;
  867.         else
  868.             r = (unsigned)rp->tr1->value;
  869.     } else
  870.         return(0);
  871.     switch (op) {
  872.  
  873.     case PLUS:
  874.         l += r;
  875.         break;
  876.  
  877.     case MINUS:
  878.         l -= r;
  879.         break;
  880.  
  881.     case TIMES:
  882.     case LTIMES:
  883.         l *= r;
  884.         break;
  885.  
  886.     case DIVIDE:
  887.     case LDIV:
  888.         if (r==0)
  889.             error("Divide check");
  890.         else
  891.             l /= r;
  892.         break;
  893.  
  894.     case MOD:
  895.     case LMOD:
  896.         if (r==0)
  897.             error("Divide check");
  898.         else
  899.             l %= r;
  900.         break;
  901.  
  902.     case AND:
  903.         l &= r;
  904.         break;
  905.  
  906.     case ANDN:
  907.         l &= ~r;
  908.         break;
  909.  
  910.     case OR:
  911.         l |= r;
  912.         break;
  913.  
  914.     case EXOR:
  915.         l ^= r;
  916.         break;
  917.  
  918.     case LSHIFT:
  919.         l <<= r;
  920.         break;
  921.  
  922.     case RSHIFT:
  923.         l >>= r;
  924.         break;
  925.  
  926.     default:
  927.         return(0);
  928.     }
  929.     if (lp->op==LCON) {
  930.         lp->lvalue = l;
  931.         return(lp);
  932.     }
  933.     lp = getblk(sizeof(struct lconst));
  934.     lp->op = LCON;
  935.     lp->type = LONG;
  936.     lp->lvalue = l;
  937.     return(lp);
  938. }
  939.  
  940. insert(op, atree, alist)
  941. struct acl *alist;
  942. {
  943.     register d;
  944.     register struct acl *list;
  945.     register struct tnode *tree;
  946.     int d1, i;
  947.     struct tnode *t;
  948.  
  949.     tree = atree;
  950.     list = alist;
  951. ins:
  952.     if (tree->op != op)
  953.         tree = optim(tree);
  954.     if (tree->op == op && list->nextn < LSTSIZ-2) {
  955.         list->nlist[list->nextn++] = tree;
  956.         insert(op, tree->tr1, list);
  957.         insert(op, tree->tr2, list);
  958.         return;
  959.     }
  960.     if (!isfloat(tree)) {
  961.         /* c1*(x+c2) -> c1*x+c1*c2 */
  962.         if ((tree->op==TIMES||tree->op==LSHIFT)
  963.           && tree->tr2->op==CON && tree->tr2->value>0
  964.           && tree->tr1->op==PLUS && tree->tr1->tr2->op==CON) {
  965.             d = tree->tr2->value;
  966.             if (tree->op==TIMES)
  967.                 tree->tr2->value =* tree->tr1->tr2->value;
  968.             else
  969.                 tree->tr2->value = tree->tr1->tr2->value << d;
  970.             tree->tr1->tr2->value = d;
  971.             tree->tr1->op = tree->op;
  972.             tree->op = PLUS;
  973.             tree = optim(tree);
  974.             if (op==PLUS)
  975.                 goto ins;
  976.         }
  977.     }
  978.     d = degree(tree);
  979.     for (i=0; i<list->nextl; i++) {
  980.         if ((d1=degree(list->llist[i]))<d) {
  981.             t = list->llist[i];
  982.             list->llist[i] = tree;
  983.             tree = t;
  984.             d = d1;
  985.         }
  986.     }
  987.     list->llist[list->nextl++] = tree;
  988. }
  989.  
  990. tnode(op, type, tr1, tr2)
  991. struct tnode *tr1, *tr2;
  992. {
  993.     register struct tnode *p;
  994.  
  995.     p = getblk(sizeof(*p));
  996.     p->op = op;
  997.     p->type = type;
  998.     p->degree = 0;
  999.     p->tr1 = tr1;
  1000.     if (opdope[op]&BINARY)
  1001.         p->tr2 = tr2;
  1002.     else
  1003.         p->tr2 = NULL;
  1004.     return(p);
  1005. }
  1006.  
  1007. tconst(val, type)
  1008. {
  1009.     register struct tconst *p;
  1010.  
  1011.     p = getblk(sizeof(*p));
  1012.     p->op = CON;
  1013.     p->type = type;
  1014.     p->value = val;
  1015.     return(p);
  1016. }
  1017.  
  1018. getblk(size)
  1019. {
  1020.     register *p;
  1021.  
  1022.     if (size&01)
  1023.         abort();
  1024.     p = curbase;
  1025.     if ((curbase =+ size) >= coremax) {
  1026.         if (sbrk(1024) == -1) {
  1027.             error("Out of space-- c1");
  1028.             exit(1);
  1029.         }
  1030.         coremax =+ 1024;
  1031.     }
  1032.     return(p);
  1033. }
  1034.  
  1035. islong(t)
  1036. {
  1037.     if (t==LONG)
  1038.         return(2);
  1039.     return(1);
  1040. }
  1041.  
  1042. isconstant(at)
  1043. struct tnode *at;
  1044. {
  1045.     register struct tnode *t;
  1046.  
  1047.     t = at;
  1048.     if (t->op==CON || t->op==SFCON)
  1049.         return(t);
  1050.     if (t->op==ITOL && t->tr1->op==CON)
  1051.         return(t->tr1);
  1052.     return(0);
  1053. }
  1054.  
  1055. hardlongs(at)
  1056. struct tnode *at;
  1057. {
  1058.     register struct tnode *t;
  1059.  
  1060.     t = at;
  1061.     switch(t->op) {
  1062.  
  1063.     case TIMES:
  1064.     case DIVIDE:
  1065.     case MOD:
  1066.         t->op =+ LTIMES-TIMES;
  1067.         break;
  1068.  
  1069.     case ASTIMES:
  1070.     case ASDIV:
  1071.     case ASMOD:
  1072.         t->op =+ LASTIMES-ASTIMES;
  1073.         t->tr1 = tnode(AMPER, LONG+PTR, t->tr1);
  1074.         break;
  1075.  
  1076.     default:
  1077.         return(t);
  1078.     }
  1079.     return(optim(t));
  1080. }
  1081.