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