home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V6 / usr / source / c / c20.c < prev    next >
Encoding:
C/C++ Source or Header  |  1975-07-18  |  11.3 KB  |  674 lines
  1. #
  2. /*
  3.  *     C object code improver
  4.  */
  5.  
  6. #include "c2h.c"
  7.  
  8. struct optab optab[] {
  9.     "jbr",    JBR,
  10.     "jeq",    CBR | JEQ<<8,
  11.     "jne",    CBR | JNE<<8,
  12.     "jle",    CBR | JLE<<8,
  13.     "jge",    CBR | JGE<<8,
  14.     "jlt",    CBR | JLT<<8,
  15.     "jgt",    CBR | JGT<<8,
  16.     "jlo",    CBR | JLO<<8,
  17.     "jhi",    CBR | JHI<<8,
  18.     "jlos",    CBR | JLOS<<8,
  19.     "jhis",    CBR | JHIS<<8,
  20.     "jmp",    JMP,
  21.     ".globl",EROU,
  22.     "mov",    MOV,
  23.     "clr",    CLR,
  24.     "com",    COM,
  25.     "inc",    INC,
  26.     "dec",    DEC,
  27.     "neg",    NEG,
  28.     "tst",    TST,
  29.     "asr",    ASR,
  30.     "asl",    ASL,
  31.     "sxt",    SXT,
  32.     "cmp",    CMP,
  33.     "add",    ADD,
  34.     "sub",    SUB,
  35.     "bit",    BIT,
  36.     "bic",    BIC,
  37.     "bis",    BIS,
  38.     "mul",    MUL,
  39.     "ash",    ASH,
  40.     "xor",    XOR,
  41.     ".text",TEXT,
  42.     ".data",DATA,
  43.     ".bss",    BSS,
  44.     ".even",EVEN,
  45.     "movf",    MOVF,
  46.     "movof",MOVOF,
  47.     "movfo",MOVFO,
  48.     "addf",    ADDF,
  49.     "subf",    SUBF,
  50.     "divf",    DIVF,
  51.     "mulf",    MULF,
  52.     "clrf",    CLRF,
  53.     "cmpf",    CMPF,
  54.     "negf",    NEGF,
  55.     "tstf",    TSTF,
  56.     "cfcc",    CFCC,
  57.     "sob",    SOB,
  58.     "jsr",    JSR,
  59.     ".end",    END,
  60.     0,    0};
  61.  
  62. char    revbr[] { JNE, JEQ, JGT, JLT, JGE, JLE, JHIS, JLOS, JHI, JLO };
  63. int    isn    20000;
  64.  
  65. main(argc, argv)
  66. char **argv;
  67. {
  68.     register int niter, maxiter, isend;
  69.     extern end;
  70.     extern fin, fout;
  71.     int nflag;
  72.  
  73.     if (argc>1 && argv[1][0]=='+') {
  74.         argc--;
  75.         argv++;
  76.         debug++;
  77.     }
  78.     if (argc>1 && argv[1][0]=='-') {
  79.         argc--;
  80.         argv++;
  81.         nflag++;
  82.     }
  83.     if (argc>1) {
  84.         if ((fin = open(argv[1], 0)) < 0) {
  85.             printf("C2: can't find %s\n", argv[1]);
  86.             exit(1);
  87.         }
  88.     } else
  89.         fin = dup(0);
  90.     if (argc>2) {
  91.         if ((fout = creat(argv[2], 0666)) < 0) {
  92.             fout = 1;
  93.             printf("C2: can't create %s\n", argv[2]);
  94.             exit(1);
  95.         }
  96.     } else
  97.         fout = dup(1);
  98.     lasta = firstr = lastr = sbrk(2);
  99.     maxiter = 0;
  100.     opsetup();
  101.     do {
  102.         isend = input();
  103.         movedat();
  104.         niter = 0;
  105.         do {
  106.             refcount();
  107.             do {
  108.                 iterate();
  109.                 clearreg();
  110.                 niter++;
  111.             } while (nchange);
  112.             comjump();
  113.             rmove();
  114.         } while (nchange || jumpsw());
  115.         addsob();
  116.         output();
  117.         if (niter > maxiter)
  118.             maxiter = niter;
  119.         lasta = firstr;
  120.     } while (isend);
  121.     flush();
  122.     fout = 2;
  123.     if (nflag) {
  124.         printf("%d iterations\n", maxiter);
  125.         printf("%d jumps to jumps\n", nbrbr);
  126.         printf("%d inst. after jumps\n", iaftbr);
  127.         printf("%d jumps to .+2\n", njp1);
  128.         printf("%d redundant labels\n", nrlab);
  129.         printf("%d cross-jumps\n", nxjump);
  130.         printf("%d code motions\n", ncmot);
  131.         printf("%d branches reversed\n", nrevbr);
  132.         printf("%d redundant moves\n", redunm);
  133.         printf("%d simplified addresses\n", nsaddr);
  134.         printf("%d loops inverted\n", loopiv);
  135.         printf("%d redundant jumps\n", nredunj);
  136.         printf("%d common seqs before jmp's\n", ncomj);
  137.         printf("%d skips over jumps\n", nskip);
  138.         printf("%d sob's added\n", nsob);
  139.         printf("%d redundant tst's\n", nrtst);
  140.         printf("%d literals eliminated\n", nlit);
  141.         printf("%dK core\n", ((lastr+01777)>>10)&077);
  142.         flush();
  143.     }
  144.     exit(0);
  145. }
  146.  
  147. input()
  148. {
  149.     register struct node *p, *lastp;
  150.     register int op;
  151.  
  152.     lastp = &first;
  153.     for (;;) {
  154.         op = getline();
  155.         switch (op.op) {
  156.     
  157.         case LABEL:
  158.             p = alloc(sizeof first);
  159.             if (line[0] == 'L') {
  160.                 p->combop = LABEL;
  161.                 p->labno = getnum(line+1);
  162.                 p->code = 0;
  163.             } else {
  164.                 p->combop = DLABEL;
  165.                 p->labno = 0;
  166.                 p->code = copy(line);
  167.             }
  168.             break;
  169.     
  170.         case JBR:
  171.         case CBR:
  172.         case JMP:
  173.         case JSW:
  174.             p = alloc(sizeof first);
  175.             p->combop = op;
  176.             if (*curlp=='L' && (p->labno = getnum(curlp+1)))
  177.                 p->code = 0;
  178.             else {
  179.                 p->labno = 0;
  180.                 p->code = copy(curlp);
  181.             }
  182.             break;
  183.  
  184.         default:
  185.             p = alloc(sizeof first);
  186.             p->combop = op;
  187.             p->labno = 0;
  188.             p->code = copy(curlp);
  189.             break;
  190.  
  191.         }
  192.         p->forw = 0;
  193.         p->back = lastp;
  194.         lastp->forw = p;
  195.         lastp = p;
  196.         p->ref = 0;
  197.         if (op==EROU)
  198.             return(1);
  199.         if (op==END)
  200.             return(0);
  201.     }
  202. }
  203.  
  204. getline()
  205. {
  206.     register char *lp;
  207.     register c;
  208.  
  209.     lp = line;
  210.     while (c = getchar()) {
  211.         if (c==':') {
  212.             *lp++ = 0;
  213.             return(LABEL);
  214.         }
  215.         if (c=='\n') {
  216.             *lp++ = 0;
  217.             return(oplook());
  218.         }
  219.         *lp++ = c;
  220.     }
  221.     *lp++ = 0;
  222.     return(END);
  223. }
  224.  
  225. getnum(ap)
  226. char *ap;
  227. {
  228.     register char *p;
  229.     register n, c;
  230.  
  231.     p = ap;
  232.     n = 0;
  233.     while ((c = *p++) >= '0' && c <= '9')
  234.         n = n*10 + c - '0';
  235.     if (*--p != 0)
  236.         return(0);
  237.     return(n);
  238. }
  239.  
  240. output()
  241. {
  242.     register struct node *t;
  243.     register struct optab *op;
  244.     register int byte;
  245.  
  246.     t = &first;
  247.     while (t = t->forw) switch (t->op) {
  248.  
  249.     case END:
  250.         return;
  251.  
  252.     case LABEL:
  253.         printf("L%d:", t->labno);
  254.         continue;
  255.  
  256.     case DLABEL:
  257.         printf("%s:", t->code);
  258.         continue;
  259.  
  260.     default:
  261.         if ((byte = t->subop) == BYTE)
  262.             t->subop = 0;
  263.         for (op = optab; op->opstring!=0; op++) 
  264.             if (op->opcode == t->combop) {
  265.                 printf("%s", op->opstring);
  266.                 if (byte==BYTE)
  267.                     printf("b");
  268.                 break;
  269.             }
  270.         if (t->code) {
  271.             reducelit(t);
  272.             printf("\t%s\n", t->code);
  273.         } else if (t->op==JBR || t->op==CBR)
  274.             printf("\tL%d\n", t->labno);
  275.         else
  276.             printf("\n");
  277.         continue;
  278.  
  279.     case JSW:
  280.         printf("L%d\n", t->labno);
  281.         continue;
  282.  
  283.     case SOB:
  284.         printf("sob    %s,L%d\n", t->code, t->labno);
  285.         continue;
  286.  
  287.     case 0:
  288.         if (t->code)
  289.             printf("%s", t->code);
  290.         printf("\n");
  291.         continue;
  292.     }
  293. }
  294.  
  295. /*
  296.  * Notice addresses of the form
  297.  * $xx,xx(r)
  298.  * and replace them with (pc),xx(r)
  299.  *     -- Thanx and a tip of the Hatlo hat to Bliss-11.
  300.  */
  301. reducelit(at)
  302. struct node *at;
  303. {
  304.     register char *c1, *c2;
  305.     char *c2s;
  306.     register struct node *t;
  307.  
  308.     t = at;
  309.     if (*t->code != '$')
  310.         return;
  311.     c1 = t->code;
  312.     while (*c1 != ',')
  313.         if (*c1++ == '\0')
  314.             return;
  315.     c2s = c1;
  316.     c1++;
  317.     if (*c1=='*')
  318.         c1++;
  319.     c2 = t->code+1;
  320.     while (*c1++ == *c2++);
  321.     if (*--c1!='(' || *--c2!=',')
  322.         return;
  323.     t->code = copy("(pc)", c2s);
  324.     nlit++;
  325. }
  326.  
  327. copy(ap)
  328. char *ap;
  329. {
  330.     register char *p, *np;
  331.     char *onp;
  332.     register n;
  333.     int na;
  334.  
  335.     na = nargs();
  336.     p = ap;
  337.     n = 0;
  338.     if (*p==0)
  339.         return(0);
  340.     do
  341.         n++;
  342.     while (*p++);
  343.     if (na>1) {
  344.         p = (&ap)[1];
  345.         while (*p++)
  346.             n++;
  347.     }
  348.     onp = np = alloc(n);
  349.     p = ap;
  350.     while (*np++ = *p++);
  351.     if (na>1) {
  352.         p = (&ap)[1];
  353.         np--;
  354.         while (*np++ = *p++);
  355.     }
  356.     return(onp);
  357. }
  358.  
  359. opsetup()
  360. {
  361.     register struct optab *optp, **ophp;
  362.     register char *p;
  363.  
  364.     for (optp = optab; p = optp->opstring; optp++) {
  365.         ophp = &ophash[(((p[0]<<3)+(p[1]<<1)+p[2])&077777) % OPHS];
  366.         while (*ophp++)
  367.             if (ophp > &ophash[OPHS])
  368.                 ophp = ophash;
  369.         *--ophp = optp;
  370.     }
  371. }
  372.  
  373. oplook()
  374. {
  375.     register struct optab *optp;
  376.     register char *lp, *op;
  377.     static char tmpop[32];
  378.     struct optab **ophp;
  379.  
  380.     op = tmpop;
  381.     for (lp = line; *lp && *lp!=' ' && *lp!='\t';)
  382.         *op++ = *lp++;
  383.     *op++ = 0;
  384.     while (*lp=='\t' || *lp==' ')
  385.         lp++;
  386.     curlp = lp;
  387.     ophp = &ophash[(((tmpop[0]<<3)+(tmpop[1]<<1)+tmpop[2])&077777) % OPHS];
  388.     while (optp = *ophp) {
  389.         op = optp->opstring;
  390.         lp = tmpop;
  391.         while (*lp == *op++)
  392.             if (*lp++ == 0)
  393.                 return(optp->opcode);
  394.         if (*lp++=='b' && *lp++==0 && *--op==0)
  395.             return(optp->opcode + (BYTE<<8));
  396.         ophp++;
  397.         if (ophp >= &ophash[OPHS])
  398.             ophp = ophash;
  399.     }
  400.     if (line[0]=='L') {
  401.         lp = &line[1];
  402.         while (*lp)
  403.             if (*lp<'0' || *lp++>'9')
  404.                 return(0);
  405.         curlp = line;
  406.         return(JSW);
  407.     }
  408.     curlp = line;
  409.     return(0);
  410. }
  411.  
  412. refcount()
  413. {
  414.     register struct node *p, *lp;
  415.     static struct node *labhash[LABHS];
  416.     register struct node **hp;
  417.  
  418.     for (hp = labhash; hp < &labhash[LABHS];)
  419.         *hp++ = 0;
  420.     for (p = first.forw; p!=0; p = p->forw)
  421.         if (p->op==LABEL) {
  422.             labhash[p->labno % LABHS] = p;
  423.             p->refc = 0;
  424.         }
  425.     for (p = first.forw; p!=0; p = p->forw) {
  426.         if (p->op==JBR || p->op==CBR || p->op==JSW) {
  427.             p->ref = 0;
  428.             lp = labhash[p->labno % LABHS];
  429.             if (lp==0 || p->labno!=lp->labno)
  430.             for (lp = first.forw; lp!=0; lp = lp->forw) {
  431.                 if (lp->op==LABEL && p->labno==lp->labno)
  432.                     break;
  433.             }
  434.             if (lp) {
  435.                 hp = nonlab(lp)->back;
  436.                 if (hp!=lp) {
  437.                     p->labno = hp->labno;
  438.                     lp = hp;
  439.                 }
  440.                 p->ref = lp;
  441.                 lp->refc++;
  442.             }
  443.         }
  444.     }
  445.     for (p = first.forw; p!=0; p = p->forw)
  446.         if (p->op==LABEL && p->refc==0
  447.          && (lp = nonlab(p))->op && lp->op!=JSW)
  448.             decref(p);
  449. }
  450.  
  451. iterate()
  452. {
  453.     register struct node *p, *rp, *p1;
  454.  
  455.     nchange = 0;
  456.     for (p = first.forw; p!=0; p = p->forw) {
  457.         if ((p->op==JBR||p->op==CBR||p->op==JSW) && p->ref) {
  458.             rp = nonlab(p->ref);
  459.             if (rp->op==JBR && rp->labno && p!=rp) {
  460.                 nbrbr++;
  461.                 p->labno = rp->labno;
  462.                 decref(p->ref);
  463.                 rp->ref->refc++;
  464.                 p->ref = rp->ref;
  465.                 nchange++;
  466.             }
  467.         }
  468.         if (p->op==CBR && (p1 = p->forw)->op==JBR) {
  469.             rp = p->ref;
  470.             do
  471.                 rp = rp->back;
  472.             while (rp->op==LABEL);
  473.             if (rp==p1) {
  474.                 decref(p->ref);
  475.                 p->ref = p1->ref;
  476.                 p->labno = p1->labno;
  477.                 p1->forw->back = p;
  478.                 p->forw = p1->forw;
  479.                 p->subop = revbr[p->subop];
  480.                 nchange++;
  481.                 nskip++;
  482.             }
  483.         }
  484.         if (p->op==JBR || p->op==JMP) {
  485.             while (p->forw && p->forw->op!=LABEL
  486.                 && p->forw->op!=EROU && p->forw->op!=END) {
  487.                 nchange++;
  488.                 iaftbr++;
  489.                 if (p->forw->ref)
  490.                     decref(p->forw->ref);
  491.                 p->forw = p->forw->forw;
  492.                 p->forw->back = p;
  493.             }
  494.             rp = p->forw;
  495.             while (rp && rp->op==LABEL) {
  496.                 if (p->ref == rp) {
  497.                     p->back->forw = p->forw;
  498.                     p->forw->back = p->back;
  499.                     p = p->back;
  500.                     decref(rp);
  501.                     nchange++;
  502.                     njp1++;
  503.                     break;
  504.                 }
  505.                 rp = rp->forw;
  506.             }
  507.             xjump(p);
  508.             p = codemove(p);
  509.         }
  510.     }
  511. }
  512.  
  513. xjump(ap)
  514. {
  515.     register int *p1, *p2, *p3;
  516.     int nxj;
  517.  
  518.     nxj = 0;
  519.     p1 = ap;
  520.     if ((p2 = p1->ref)==0)
  521.         return(0);
  522.     for (;;) {
  523.         while ((p1 = p1->back) && p1->op==LABEL);
  524.         while ((p2 = p2->back) && p2->op==LABEL);
  525.         if (!equop(p1, p2) || p1==p2)
  526.             return(nxj);
  527.         p3 = insertl(p2);
  528.         p1->combop = JBR;
  529.         p1->ref = p3;
  530.         p1->labno = p3->labno;
  531.         p1->code = 0;
  532.         nxj++;
  533.         nxjump++;
  534.         nchange++;
  535.     }
  536. }
  537.  
  538. insertl(ap)
  539. struct node *ap;
  540. {
  541.     register struct node *lp, *op;
  542.  
  543.     op = ap;
  544.     if (op->op == LABEL) {
  545.         op->refc++;
  546.         return(op);
  547.     }
  548.     if (op->back->op == LABEL) {
  549.         op = op->back;
  550.         op->refc++;
  551.         return(op);
  552.     }
  553.     lp = alloc(sizeof first);
  554.     lp->combop = LABEL;
  555.     lp->labno = isn++;
  556.     lp->ref = 0;
  557.     lp->code = 0;
  558.     lp->refc = 1;
  559.     lp->back = op->back;
  560.     lp->forw = op;
  561.     op->back->forw = lp;
  562.     op->back = lp;
  563.     return(lp);
  564. }
  565.  
  566. codemove(ap)
  567. struct node *ap;
  568. {
  569.     register struct node *p1, *p2, *p3;
  570.     struct node *t, *tl;
  571.     int n;
  572.  
  573.     p1 = ap;
  574.     if (p1->op!=JBR || (p2 = p1->ref)==0)
  575.         return(p1);
  576.     while (p2->op == LABEL)
  577.         if ((p2 = p2->back) == 0)
  578.             return(p1);
  579.     if (p2->op!=JBR && p2->op!=JMP)
  580.         goto ivloop;
  581.     p2 = p2->forw;
  582.     p3 = p1->ref;
  583.     while (p3) {
  584.         if (p3->op==JBR || p3->op==JMP) {
  585.             if (p1==p3)
  586.                 return(p1);
  587.             ncmot++;
  588.             nchange++;
  589.             p1->back->forw = p2;
  590.             p1->forw->back = p3;
  591.             p2->back->forw = p3->forw;
  592.             p3->forw->back = p2->back;
  593.             p2->back = p1->back;
  594.             p3->forw = p1->forw;
  595.             decref(p1->ref);
  596.             return(p2);
  597.         } else
  598.             p3 = p3->forw;
  599.     }
  600.     return(p1);
  601. ivloop:
  602.     if (p1->forw->op!=LABEL)
  603.         return(p1);
  604.     p3 = p2 = p2->forw;
  605.     n = 16;
  606.     do {
  607.         if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
  608.             return(p1);
  609.     } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
  610.     do 
  611.         if ((p1 = p1->back) == 0)
  612.             return(ap);
  613.     while (p1!=p3);
  614.     p1 = ap;
  615.     tl = insertl(p1);
  616.     p3->subop = revbr[p3->subop];
  617.     decref(p3->ref);
  618.     p2->back->forw = p1;
  619.     p3->forw->back = p1;
  620.     p1->back->forw = p2;
  621.     p1->forw->back = p3;
  622.     t = p1->back;
  623.     p1->back = p2->back;
  624.     p2->back = t;
  625.     t = p1->forw;
  626.     p1->forw = p3->forw;
  627.     p3->forw = t;
  628.     p2 = insertl(p1->forw);
  629.     p3->labno = p2->labno;
  630.     p3->ref = p2;
  631.     decref(tl);
  632.     if (tl->refc<=0)
  633.         nrlab--;
  634.     loopiv++;
  635.     nchange++;
  636.     return(p3);
  637. }
  638.  
  639. comjump()
  640. {
  641.     register struct node *p1, *p2, *p3;
  642.  
  643.     for (p1 = first.forw; p1!=0; p1 = p1->forw)
  644.         if (p1->op==JBR && (p2 = p1->ref) && p2->refc > 1)
  645.             for (p3 = p1->forw; p3!=0; p3 = p3->forw)
  646.                 if (p3->op==JBR && p3->ref == p2)
  647.                     backjmp(p1, p3);
  648. }
  649.  
  650. backjmp(ap1, ap2)
  651. struct node *ap1, *ap2;
  652. {
  653.     register struct node *p1, *p2, *p3;
  654.  
  655.     p1 = ap1;
  656.     p2 = ap2;
  657.     for(;;) {
  658.         while ((p1 = p1->back) && p1->op==LABEL);
  659.         p2 = p2->back;
  660.         if (equop(p1, p2)) {
  661.             p3 = insertl(p1);
  662.             p2->back->forw = p2->forw;
  663.             p2->forw->back = p2->back;
  664.             p2 = p2->forw;
  665.             decref(p2->ref);
  666.             p2->labno = p3->labno;
  667.             p2->ref = p3;
  668.             nchange++;
  669.             ncomj++;
  670.         } else
  671.             return;
  672.     }
  673. }
  674.