Return to optim.c CVS log

Up to [Research Unix] / researchv9 / jerq / sgs / optim

Annotation of researchv9/jerq/sgs/optim/optim.c, revision 1.1

1.1     ! root        1: /*     static char  ID[] = "@(#) optim.c: 1.19 3/2/84";        */
        !             2: 
        !             3: /*     machine independent improvement routines */
        !             4: 
        !             5: #include "optim.h"
        !             6: 
        !             7: /* unit of allocatable space (in char *'s) */
        !             8: #ifndef NSPACE
        !             9: #define NSPACE 1024
        !            10: #endif
        !            11: 
        !            12: /* maximum number of labels referenced in a function */
        !            13: #ifndef NUMLBLS
        !            14: #define NUMLBLS        513
        !            15: #endif
        !            16: #define H_INCR 5
        !            17: #define N_LBLS (NUMLBLS / H_INCR * H_INCR + 1)
        !            18: 
        !            19: /* what to do if no input file specified */
        !            20: #ifndef NOFILE
        !            21: #define NOFILE()       /* by default, use stdin */
        !            22: #endif
        !            23: 
        !            24: /* what to report if file-opening fails */
        !            25: #ifndef FFILER
        !            26: #define FFILER(S)      "can't open %s\n"
        !            27: #endif
        !            28: 
        !            29: /* block of text */
        !            30: 
        !            31: typedef struct block {
        !            32:        struct block *next;     /* pointer to textually next block */
        !            33:        struct block *nextl;    /* pointer to next executed block if no br */
        !            34:        struct block *nextr;    /* pointer to next executed block if br */
        !            35:        struct block *ltest;    /* for loop termination tests */
        !            36:        NODE *firstn;           /* first text node of block */
        !            37:        NODE *lastn;            /* last text node of block */
        !            38:        short index;            /* block index for debugging purposes */
        !            39:        short length;           /* number of instructions in block */
        !            40:        short indeg;            /* number of text references */
        !            41:        short marked;           /* marker for various things */
        !            42: } BLOCK;
        !            43: 
        !            44: /* symbol table entry */
        !            45: 
        !            46: typedef struct {
        !            47:        char *cp;               /* the symbol */
        !            48:        BLOCK *bl;              /* the block it is defined in */
        !            49: } LBL;
        !            50: 
        !            51: /* data structures */
        !            52: 
        !            53: NODE n0;                       /* header for text list */
        !            54: NODE ntail = { NULL, NULL, TAIL };     /* trailer for text list */
        !            55: REF r0;                                /* header for non-text reference list */
        !            56: REF *lastref;                  /* pointer to last label reference */
        !            57: static BLOCK b0;               /* header for block list */
        !            58: static BLOCK * Lastb = NULL;   /* pointer to array of blocks previously
        !            59:                                ** allocated for bldgr()
        !            60:                                */
        !            61: static LBL *Lbltbl;            /* pointer to hash table of labels */
        !            62: static int Numlbls;            /* count of labels in hash table */
        !            63: static BLOCK *Prevb;           /* pointer to previous block during
        !            64:                                   traversal of list */
        !            65: int fnum = 0;                  /* function counter */
        !            66: int npass;                     /* pass-through-this-function counter */
        !            67: static int idx;                        /* block index (for debugging) */
        !            68: 
        !            69: /* space allocation control */
        !            70: 
        !            71: static struct space_t {        /* to manage space allocation */
        !            72:        struct space_t *next;
        !            73:        char *space[NSPACE - 1];
        !            74: } *s0 = NULL, **Space;
        !            75: static char *Lasta, *Lastx;    /* pointers into allocatable space */
        !            76: static long Maxu = 0, Maxm = 0, Maxa = 0;
        !            77: 
        !            78: /* statistic counters */
        !            79: 
        !            80: int ndisc = 0;                 /* instructions discarded */
        !            81: int ninst = 0;                 /* total instructions */
        !            82: static int nunr = 0;           /* unreachable instructions */
        !            83: int nmerge = 0;                        /* redundant instructions */
        !            84: static int nsave = 0;          /* branches saved */
        !            85: static int nrot = 0;           /* rotated loops */
        !            86: static int noptim = 0;         /* calls to optim */
        !            87: #define PCASES 13
        !            88: static int Pcase[PCASES + 1];  /* block types during reconstruction of text */
        !            89: static struct added {          /* to keep statistics on branches added */
        !            90:        struct added *next;
        !            91:        short fnum,
        !            92:        n_added;
        !            93: } a0, *lastadd = &a0;
        !            94: 
        !            95: /* debugging flags */
        !            96: 
        !            97: static int bflag = 0;          /* Blocks after initial construction */
        !            98: int cflag = 0;                 /* do Conservative Comtail */
        !            99: int dflag = 0;                 /* print live/Dead information if set */
        !           100: static int eflag = 0;          /* Execution trace */
        !           101: int hflag = 0;                 /* peepHole disable if set */
        !           102: static int lflag = 0;          /* Labels deleted */
        !           103: static int mflag = 0;          /* Merged suffixes found */
        !           104: static int pflag = 0;          /* Path reconstruction trace */
        !           105: int sflag = 0;                 /* Statistics (on stderr) */
        !           106: static int uflag = 0;          /* Unreachable code deleted */
        !           107: static int wflag = 0;          /* Window peephole trace */
        !           108: 
        !           109: /* for readability */
        !           110: 
        !           111: #ifdef MEMFCN  /* replace strncpy when memset is available (5.0 and after) */
        !           112: #define CLEAR(s, n)    (void) memset((char *)(s), 0, (int)(n))
        !           113: #else
        !           114: #define CLEAR(s, n)    (void) strncpy((char *)(s), "", (int)(n))
        !           115: #endif
        !           116: #define FATAL(S)       fatal((S), (char *)NULL)
        !           117: #define FLAG(L, LFLAG) case 'L': LFLAG = -1; continue;
        !           118: #define ALLB(b, s)     b = (s); b != NULL; b = b->next
        !           119: #define PRCASE(N)      if (pflag) { prcase(N, b); Pcase[N]++; }
        !           120: #define TOPOFBLOCK(p)  ((p) == NULL || islabel(p))
        !           121: #define TRACE(F)       if (eflag) PRINTF("%cStarting F[%d, %d]\n", \
        !           122:                            CC, fnum, npass)
        !           123: #define MPRINTF                if (mflag) PRINTF
        !           124: #define PRINDEX(P)     (b->P == NULL ? 0 : b->P->index)
        !           125: #define PSTAT(S, N)    if ((N) > 0) FPRINTF(stderr, (S), (N))
        !           126: #define FINDLBL(l)     lblhash((l), (BLOCK *)NULL)
        !           127: #define ADDLBL(l, b)   (void) lblhash((l), (b))
        !           128: #define ISUNCBL(b)     ((b)->length == 1 && isuncbr((b)->lastn))
        !           129: #define ISREMBL(b)     (ISUNCBL(b) && !ishb((b)->lastn))
        !           130: #define ISREMBR(p)     (isbr(p) && !ishb(p))
        !           131: #define RMBR(p)                (ndisc++, nsave++, DELNODE(p))
        !           132: /* TARGET follows branches until a non-branch is reached.  However,
        !           133: ** there is the danger that we will loop on ourselves if we encounter
        !           134: ** an infinite loop.  Solve the problem partially by preventing
        !           135: ** self-loops.
        !           136: */
        !           137: #define TARGET(b)      while (b->nextl != NULL && ISUNCBL(b->nextl) &&\
        !           138:                                b->nextl != b) b = b->nextl
        !           139: #define NEWBLK(n, type)        ((type *) xalloc((n) * sizeof(type)))
        !           140: 
        !           141: /* function declarations */
        !           142: 
        !           143: extern char *label_left();
        !           144: extern BLOCK *lblhash();
        !           145: extern void bldgr(), putbr(), rmunrch(), modrefs(), indegree(), mkltbl();
        !           146: #ifdef spflg
        !           147: extern char * yysflgs();
        !           148: #endif
        !           149: 
        !           150: /************************************************************************/
        !           151: 
        !           152:        int
        !           153: main(argc, argv) /* initialize, process parameters,  control processing, etc. */
        !           154:        int argc; register char *argv[]; {
        !           155: 
        !           156:        extern void mustopen();
        !           157:        char usrflag[10];
        !           158:        int ufl = 0, i, fileseen = 0;
        !           159: 
        !           160:        /* process parameters on command line */
        !           161: 
        !           162:        while (--argc > 0) {
        !           163:                if (**++argv != '-') { /* alternate file(s) */
        !           164:                        switch (fileseen) {
        !           165:                        case 0: /* none yet, open input file */
        !           166:                                mustopen(*argv, "r", stdin);
        !           167:                                fileseen++;
        !           168:                                continue;
        !           169:                        case 1: /* input seen, open output file */
        !           170:                                mustopen(*argv, "w", stdout);
        !           171:                                fileseen++;
        !           172:                                continue;
        !           173:                        }
        !           174:                        FATAL("too many filenames\n");
        !           175:                }
        !           176:                while ((i = *++*argv) != '\0') { /* debugging flags */
        !           177:                        switch (tolower(i)) {
        !           178:                        case 'i': /* alternate input file */
        !           179:                                if (--argc <= 0)
        !           180:                                        FATAL("no argument for -I option\n");
        !           181:                                mustopen(*++argv, "r", stdin);
        !           182:                                break;
        !           183:                        case 'o': /* alternate output file */
        !           184:                                if (--argc <= 0)
        !           185:                                        FATAL("no argument for -O option\n");
        !           186:                                mustopen(*++argv, "w", stdout);
        !           187:                                break;
        !           188:                        FLAG(b, bflag);
        !           189:                        FLAG(c, cflag); /* kill comtail */
        !           190:                        FLAG(d, dflag); /* display live/dead info */
        !           191:                        FLAG(e, eflag);
        !           192:                        FLAG(h, hflag); /* kill peephole optimizations */
        !           193:                        FLAG(l, lflag);
        !           194:                        FLAG(m, mflag);
        !           195:                        FLAG(n, noptim); /* kill optimization */
        !           196:                        FLAG(p, pflag);
        !           197:                        FLAG(r, nrot); /* kill loop rotations */
        !           198:                        FLAG(s, sflag);
        !           199:                        FLAG(u, uflag);
        !           200:                        FLAG(w, wflag);
        !           201:                        default:
        !           202: #ifdef spflg
        !           203:                                if(spflg(i)) {
        !           204:                                        *argv = yysflgs(*argv);
        !           205:                                }
        !           206:                                else
        !           207: #endif
        !           208:                                usrflag[ufl++] = i;
        !           209:                                continue;
        !           210:                        }
        !           211:                        break;
        !           212:                }
        !           213:        }
        !           214:        if (bflag | eflag | lflag | mflag | pflag | uflag | wflag)
        !           215:                setbuf(stdout, (char *)NULL); /* for easier debugging */
        !           216:        NOFILE(); /* if no input file specified */
        !           217: 
        !           218:        /* initialize everything */
        !           219: 
        !           220:        Lbltbl = NEWBLK(N_LBLS, LBL);
        !           221:        init();
        !           222:        usrflag[ufl] = '\0';
        !           223:        yyinit(usrflag);
        !           224: 
        !           225:        /* transfer to the machine dependent part */
        !           226: 
        !           227:        (void) yylex();
        !           228:        wrapup();
        !           229: 
        !           230:        /* print statistics if asked for */
        !           231: 
        !           232:        if (sflag) {
        !           233:                register struct added *a;
        !           234: 
        !           235:                for (a = a0.next; a != NULL; a = a->next)
        !           236:                        FPRINTF(stderr, "%d branch(es) added to function %d\n",
        !           237:                            a->n_added, a->fnum);
        !           238:                dstats();       /* machine dependent statistics */
        !           239:                PSTAT("%d unreachable instruction(s) deleted\n", nunr);
        !           240:                PSTAT("%d branch(es) saved\n", nsave);
        !           241:                PSTAT("%d instruction(s) merged\n", nmerge);
        !           242:                FPRINTF(stderr, "%d of %d total instructions discarded\n",
        !           243:                    ndisc, ninst);
        !           244:                PSTAT("%d loop(s) rotated\n", nrot);
        !           245:                FPRINTF(stderr,
        !           246:                "%ld bytes used, %ld allocated\n%d function(s), %d optim(s)\n",
        !           247:                    Maxm, Maxa, fnum - 1, noptim > 0 ? noptim : 0);
        !           248:                if (pflag && noptim > 0)
        !           249:                        for (FPRINTF(stderr, "case\tnumber\n"),
        !           250:                            i = 0; i <= PCASES; i++)
        !           251:                                FPRINTF(stderr, "%2d\t%3d\n", i, Pcase[i]);
        !           252:        }
        !           253:        return (0);
        !           254: }
        !           255: 
        !           256:        static void
        !           257: mustopen(name, dir, file) char *name, *dir; FILE *file; {
        !           258: 
        !           259:        if (freopen(name, dir, file) == NULL)
        !           260:                fatal(FFILER(name), name);
        !           261: }
        !           262: 
        !           263:        void
        !           264: init() { /* reset pointers, counters, etc for next function */
        !           265: 
        !           266:        register struct space_t *p, *pp;
        !           267:        long maxa = N_LBLS * sizeof(LBL);
        !           268: 
        !           269:        if (Lastb != NULL)              /* free bldgr's storage */
        !           270:            xfree((char *) Lastb);
        !           271:        Lastb = NULL;                   /* no memory now allocated */
        !           272: 
        !           273:        for (p = s0; p != NULL; p = pp) {
        !           274:                maxa += sizeof(struct space_t);
        !           275:                pp = p->next;
        !           276:                xfree((char *) p);
        !           277:        }
        !           278:        if ((Maxu += Numlbls * sizeof(LBL)) > Maxm)
        !           279:                Maxm = Maxu;
        !           280:        if (maxa > Maxa)
        !           281:                Maxa = maxa;
        !           282:        Maxu = 0;
        !           283:        Space = &s0;
        !           284:        s0 = NULL;
        !           285:        Lasta = Lastx = NULL;
        !           286:        n0.forw = &ntail;
        !           287:        ntail.back = &n0;
        !           288:        b0.firstn = b0.lastn = &n0;
        !           289:        r0.nextref = NULL;
        !           290:        lastref = &r0;
        !           291:        fnum++;
        !           292:        npass = 0;
        !           293: }
        !           294: 
        !           295:        void
        !           296: optim() { /* control improvement sequencing */
        !           297: 
        !           298:        if (noptim < 0)
        !           299:                return;
        !           300:        noptim++;
        !           301:        if (n0.forw != &ntail) {
        !           302: 
        !           303:                extern void rmlbls(), mrgbrs(), comtail(), reord(), rmbrs();
        !           304:                int onsave = nsave;
        !           305: 
        !           306:                rmlbls();       /* remove useless labels */
        !           307:                bldgr(true);    /* build flow graph and call bboptim */
        !           308:                mrgbrs();       /* merge branches to branches */
        !           309:                rmunrch(false); /* remove unreachable code, don't preserve
        !           310:                                ** block/node connectivity
        !           311:                                */
        !           312:                comtail();      /* remove common tails */
        !           313:                reord();        /* reorder code */
        !           314:                rmbrs();        /* remove redundant branches */
        !           315:                rmlbls();       /* remove useless labels */
        !           316: #ifdef LIVEDEAD
        !           317:                ldanal();       /* perform live/dead analysis */
        !           318: #endif
        !           319:                if (sflag && onsave > nsave) {
        !           320:                        register struct added *a = lastadd = lastadd->next =
        !           321:                            NEWBLK(1, struct added);
        !           322: 
        !           323:                        a->next = NULL;
        !           324:                        a->fnum = fnum;
        !           325:                        a->n_added = onsave - nsave;
        !           326:                }
        !           327:        }
        !           328:        npass++;
        !           329: }
        !           330: 
        !           331:        static void
        !           332: rmlbls() { /* remove unreferenced labels */
        !           333: 
        !           334:        register REF *r;
        !           335:        register NODE *p;
        !           336:        register char *s;
        !           337: 
        !           338:        TRACE(rmlbls);
        !           339: 
        !           340:        clrltbl();
        !           341: 
        !           342:        /* add references from data section */
        !           343: 
        !           344:        for (r = r0.nextref; r != NULL; r = r->nextref)
        !           345:                ADDLBL(r->lab, &b0);
        !           346: 
        !           347:        /* add references from branches in text section */
        !           348: 
        !           349:        for (ALLN(p))
        !           350:                if ((isbr(p) || ISLABREF(p)) && (s = getp(p)) != NULL)
        !           351:                        ADDLBL(s, &b0);
        !           352: 
        !           353:        /* delete non-hard labels that are not now in the label table */
        !           354: 
        !           355:        for (ALLN(p))
        !           356:                if (islabel(p) && !ishl(p) && FINDLBL(p->ops[0]) == NULL) {
        !           357:                        if (lflag)
        !           358:                                PRINTF("%clabel %s removed\n", CC, p->ops[0]);
        !           359:                        DELNODE(p);
        !           360:                }
        !           361: 
        !           362: }
        !           363: 
        !           364: /* This routine attempts to economize on space be allocating a hunk
        !           365: ** of storage big enough for all program blocks.  It deallocates that
        !           366: ** hunk on the next call in hopes it can be reused.
        !           367: */
        !           368: 
        !           369:        static void
        !           370: bldgr(opt) boolean opt; { /* build flow graph of procedure */
        !           371: 
        !           372:        register BLOCK *b = &b0;
        !           373:        register NODE *p;
        !           374: 
        !           375:        TRACE(bldgr);
        !           376: 
        !           377:        if (Lastb != NULL)              /* deallocate old array, if any */
        !           378:            xfree((char *)Lastb);
        !           379: 
        !           380:        /* Count number of blocks so we can allocate an array */
        !           381: 
        !           382:        idx = 0;                        /* use this to count blocks */
        !           383:        p = n0.forw;                    /* point at first node */
        !           384:        while (p != &ntail)
        !           385:        {
        !           386:            idx++;                      /* count one more block */
        !           387:            while (islabel(p))          /* skip leading labels */
        !           388:                p = p->forw;
        !           389:            
        !           390:            for ( ; p != &ntail && !islabel(p); p = p->forw) {
        !           391:                    if (isbr(p)) {
        !           392:                            p = p->forw;
        !           393:                            break;
        !           394:                    }
        !           395:            }
        !           396:        }
        !           397: 
        !           398:        /* idx is now the number of blocks.  Allocate array. */
        !           399: 
        !           400:        Lastb = (BLOCK *) xalloc(idx * sizeof(BLOCK));
        !           401: 
        !           402:        /* now build the flow graph */
        !           403: 
        !           404:        idx = 0;
        !           405:        b = b0.next = Lastb;            /* point at prospective first block */
        !           406:        for (p = n0.forw; p != &ntail; ) {
        !           407: 
        !           408:                register NODE *prevn = p->back;
        !           409: 
        !           410:                b->next = b + 1;        /* "next" will be physically next */
        !           411:                b->index = ++idx;
        !           412:                b->length = b->indeg = 0;
        !           413: 
        !           414:                /* a block starts with 0 or more labels */
        !           415: 
        !           416:                while (islabel(p))
        !           417:                        p = p->forw;
        !           418: 
        !           419:                /* followed by 0 or more non-branch instructions
        !           420:                   terminated with a branch or before another label */
        !           421: 
        !           422:                for ( ; p != &ntail && !islabel(p); p = p->forw) {
        !           423:                        b->length++;
        !           424:                        if (isbr(p)) {
        !           425:                                p = p->forw;
        !           426:                                break;
        !           427:                        }
        !           428:                }
        !           429:                if (opt) { /* do dependent basic-block optimization */
        !           430: 
        !           431:                        int omit = bboptim(prevn->forw, p->back);
        !           432:                        if (omit > b->length)
        !           433:                                omit = b->length;
        !           434:                        b->length -= omit;
        !           435:                        ndisc += omit;
        !           436:                }
        !           437:                b->lastn = p->back;
        !           438:                if ((b->firstn = prevn->forw) != p) /* if non-empty block */
        !           439:                        b++;            /* we will next do next block */
        !           440:        }
        !           441:        b[-1].next = NULL;              /* (assumes at least one block) next
        !           442:                                        ** pointer of last block we filled in
        !           443:                                        ** is NULL
        !           444:                                        */
        !           445: 
        !           446:        mkltbl(); /* make label table with only definitions */
        !           447: 
        !           448:        /* set branch pointers */
        !           449: 
        !           450:        for (ALLB(b, b0.next)) {
        !           451:                char *s;
        !           452: 
        !           453:                p = b->lastn;
        !           454:                b->nextl = b->next;
        !           455:                b->nextr = isbr(p) && (s = getp(p)) != NULL ?
        !           456:                    FINDLBL(s) : NULL;
        !           457:                if (isuncbr(p)) {
        !           458:                        b->nextl = b->nextr;
        !           459:                        b->nextr = NULL;
        !           460:                }
        !           461:                if (bflag) {
        !           462:                        PRINTF(
        !           463:                "%c\n%cblock %d (left: %d, right: %d, length: %d)\n%cfirst:\t",
        !           464:                            CC, CC, b->index, PRINDEX(nextl), PRINDEX(nextr),
        !           465:                            b->length, CC);
        !           466:                        prinst(b->firstn);
        !           467:                        PRINTF("%clast:\t", CC);
        !           468:                        prinst(p);
        !           469:                }
        !           470:        }
        !           471: }
        !           472: 
        !           473:        static void
        !           474: mrgbrs() { /* merge branches to unconditional branches */
        !           475: 
        !           476:        register BLOCK *b, *bb;
        !           477: 
        !           478:        TRACE(mrgbrs);
        !           479: 
        !           480:        /* merge unconditional branches to their destinations */
        !           481: 
        !           482:        for (ALLB(b, b0.next))
        !           483:                if ((bb = b->nextl) == b->next) { /* fall-through */
        !           484:                        if ((b = bb) == NULL)
        !           485:                                break;
        !           486:                }
        !           487:                else if (bb != NULL && bb != b &&
        !           488:                    islabel(b->firstn) && ISREMBL(b)) {
        !           489:                        ndisc++;
        !           490:                        nsave++;
        !           491:                        modrefs(b->lastn->back, b, bb);
        !           492:                }
        !           493: 
        !           494:        /*
        !           495:         * It is assumed that "ret" is an unconditional branch;
        !           496:         * that getp on a "ret" returns NULL; that this can be
        !           497:         * placed on an unconditional branch ("jbr");
        !           498:         * that prinst() will convert "jbr NULL" back to "ret";
        !           499:         * but that the NULL
        !           500:         * cannot be placed on a conditional branch ("jne").
        !           501:         * (NULL is also returned by a multi-way branch (switch).)
        !           502:         */
        !           503: 
        !           504:        for (ALLB(b, b0.next)) {
        !           505: 
        !           506:                char *t;
        !           507:                register NODE *p = b->lastn;
        !           508: 
        !           509:                if (!isbr(p))
        !           510:                        continue;
        !           511:                if (isuncbr(p))
        !           512:                        while ((bb = b->nextl) != NULL && bb != bb->nextl &&
        !           513:                            ISREMBL(bb)) {
        !           514:                                register NODE *pp = bb->lastn;
        !           515: 
        !           516:                                if ((t = getp(pp)) != NULL)
        !           517:                                        putp(p, t);
        !           518:                                else { /* pp is a dead-end */
        !           519: #ifdef MEMFCN
        !           520:                                        (void) memcpy((char *)p->ops,
        !           521:                                            (char *)pp->ops,
        !           522:                                            sizeof(pp->ops));
        !           523: #else
        !           524:                                        register char **b_p = p->ops,
        !           525:                                            **bb_p = pp->ops;
        !           526:                                        register int i = MAXOPS + 1;
        !           527:                                
        !           528:                                        while (--i >= 0)
        !           529:                                                *b_p++ = *bb_p++;
        !           530: #endif
        !           531:                                        p->op = pp->op;
        !           532:                                }
        !           533:                                b->nextl = bb->nextl;
        !           534:                        }
        !           535:                else
        !           536:                        while ((bb = b->nextr) != NULL && bb != bb->nextl &&
        !           537:                            ISREMBL(bb) && (t = getp(bb->lastn)) != NULL) {
        !           538:                                putp(p, t);
        !           539:                                b->nextr = bb->nextl;
        !           540:                        }
        !           541:        }
        !           542: }
        !           543: 
        !           544:        static void
        !           545: comtail() { /* merge common tails from code blocks */
        !           546: 
        !           547:        boolean changed;
        !           548: 
        !           549:        TRACE(comtail);
        !           550: 
        !           551:        do {
        !           552:                extern boolean chktail();
        !           553:                register BLOCK *bi, *bj, *bi0, *bj0;
        !           554: 
        !           555:                changed = false;
        !           556:                if (cflag) /* for conservative analysis only */
        !           557:                        indegree(); /* compute indegree (0 from bldgr()) */
        !           558:                for (ALLB(bi, b0.next)) { /* compute a key for each block */
        !           559:                        bi->marked = 0;
        !           560:                        if (bi->length == 1 && isbr(bi->lastn))
        !           561:                                continue;
        !           562:                        bi0 = bi;
        !           563:                        if (isbr(bi->lastn) && !isuncbr(bi->lastn)) {
        !           564:                                TARGET(bi0);
        !           565:                                bi->marked += bi0->lastn->op;
        !           566:                        }
        !           567:                        bi->marked += bi0->nextl - &b0;
        !           568:                }
        !           569:                for (ALLB(bi, b0.next)) {
        !           570:                        int cond_br;
        !           571: 
        !           572:                        if (!bi->marked)
        !           573:                                continue;
        !           574:                        for (ALLB(bj, bi->next)) {
        !           575:                                if (bi->marked != bj->marked)
        !           576:                                        continue; /* quick sieve on key */
        !           577:                                if (bi->nextr != bj->nextr)
        !           578:                                        continue;
        !           579:                                bi0 = bi; bj0 = bj;
        !           580:                                /* if both blocks end in conditional branches,
        !           581:                                 * look ahead for left targets */
        !           582:                                if (cond_br =
        !           583:                                    isbr(bj->lastn) && !isuncbr(bj->lastn)) {
        !           584:                                        if (bi->lastn->op != bj->lastn->op)
        !           585:                                                continue;
        !           586:                                        if(bi->nextr == NULL &&
        !           587:                                           !same(bi->lastn,bj->lastn))
        !           588:                                                continue;
        !           589:                                        TARGET(bi0);
        !           590:                                        TARGET(bj0);
        !           591:                                }
        !           592:                                /* blocks must fall through to same place */
        !           593:                                if (bi0->nextl != bj0->nextl)
        !           594:                                        continue;
        !           595:                                /* dead-end branches must have same text */
        !           596:                                if (bi0->nextl == NULL &&
        !           597:                                    !same(bi0->lastn, bj0->lastn))
        !           598:                                        continue;
        !           599:                                if (chktail(bi, bj, bi0->nextl) == true)
        !           600:                                         changed = true;
        !           601:                        }
        !           602:                }
        !           603:        } while (changed == true);
        !           604: }
        !           605: 
        !           606:        static boolean
        !           607: chktail(bi, bj, bl) /* merge tails of bi-> and bj-> */
        !           608:        register BLOCK *bi, *bj; BLOCK *bl; {
        !           609: 
        !           610:        extern void rmtail();
        !           611:        register BLOCK *bn;
        !           612:        NODE *pi = bi->lastn, *pj = bj->lastn, *firstn, *lastn, *pb = NULL;
        !           613:        int length = 0, isbri = 0, isbrj = 0;
        !           614: 
        !           615:        /* pi and pj scan backwards through blocks bi and bj 
        !           616:           until difference or no more code */
        !           617: 
        !           618:        if (isbr(pi)) { /* trailing branches have already been matched */
        !           619:                pb = pi;
        !           620:                pi = pi->back;
        !           621:                isbri++;
        !           622:        }
        !           623:        if (isbr(pj)) {
        !           624:                pb = pj;
        !           625:                pj = pj->back;
        !           626:                isbrj++;
        !           627:        }
        !           628:        for (firstn = lastn = pj; !TOPOFBLOCK(pi) && !TOPOFBLOCK(pj) &&
        !           629:           same(pi, pj) == true; length++) {
        !           630:                firstn = pj;
        !           631:                pi = (pi == bi->firstn) ? NULL : pi->back;
        !           632:                pj = (pj == bj->firstn) ? NULL : pj->back;
        !           633:        }
        !           634:        if (length == 0)
        !           635:                return (false);
        !           636: 
        !           637:        /* if blocks identical, change references to one to the other */
        !           638: 
        !           639:        if (TOPOFBLOCK(pi) && TOPOFBLOCK(pj)) {
        !           640:                isbri = 0;
        !           641:                modrefs(pj, bj, bn = bi);
        !           642:                MPRINTF("%cblock %d merged into block %d and deleted\n",
        !           643:                    CC, bj->index, bi->index);
        !           644:        }
        !           645: 
        !           646:        /*
        !           647:         * Conservative common-tail merging avoids adding a branch to
        !           648:         * achieve a merge.  It merges only blocks which join with no other
        !           649:         * blocks joining &at that point, so that the joining branch is merely
        !           650:         * raised above the common tail, and no new branch is added.
        !           651:         */
        !           652: 
        !           653:        else if (cflag && (bl == NULL || bl->indeg > 2))
        !           654:                return (false); /* conservative common tails */
        !           655: 
        !           656:        /* if one block is a tail of the other, remove the tail from the
        !           657:           larger block and make it reference the smaller */
        !           658: 
        !           659:        else if (TOPOFBLOCK(pi)) {
        !           660:                isbri = 0;
        !           661:                bj->lastn = pj;
        !           662:                bj->length -= length + isbrj;
        !           663:                bj->nextl = bn = bi;
        !           664:                rmtail(bj);
        !           665:        }
        !           666:        else if (TOPOFBLOCK(pj)) {
        !           667:                isbrj = 0;
        !           668:                bi->lastn = pi;
        !           669:                bi->length -= length + isbri;
        !           670:                bi->nextl = bn = bj;
        !           671:                rmtail(bi);
        !           672:        }
        !           673: 
        !           674:        /* otherwise make a new block, remove tails from common blocks and
        !           675:           make them reference the new block */
        !           676: 
        !           677:        else {
        !           678:                bi->lastn = pi;
        !           679:                bj->lastn = pj;
        !           680:                bi->length -= length + isbri;
        !           681:                bj->length -= length + isbrj;
        !           682:                bn = GETSTR(BLOCK);
        !           683:                *bn = *bj;
        !           684:                bn->firstn = firstn;
        !           685:                bn->lastn = lastn;
        !           686:                bn->length = length;
        !           687:                bn->index = ++idx;
        !           688:                bn->indeg = 2;
        !           689:                bi->nextl = bj->nextl = bj->next = bn;
        !           690:                bi->nextr = bj->nextr = NULL;
        !           691:                MPRINTF("%ctails of %d and %d merged into new block %d\n",
        !           692:                    CC, bi->index, bj->index, idx);
        !           693:        }
        !           694:        if (pb != NULL && !isbr(bn->lastn)) { /* save final branch */
        !           695:                ndisc--;
        !           696:                nsave--;
        !           697:                bn->length++;
        !           698:                pb->back = bn->lastn;
        !           699:                bn->lastn = bn->lastn->forw = pb;
        !           700:        }
        !           701: 
        !           702: #ifdef IDVAL
        !           703:        for (pb = bn->firstn; pb != NULL; pb = pb->forw) {
        !           704:                pb->uniqid = IDVAL;
        !           705:                if (pb == bn->lastn)
        !           706:                        break;
        !           707:        }
        !           708: #endif
        !           709: 
        !           710:        ndisc += length + isbri + isbrj;
        !           711:        nmerge += length;
        !           712:        nsave += isbri + isbrj; /* don't blame resequence for added branch */
        !           713:        MPRINTF("%c%d instruction(s) common to blocks %d and %d\n",
        !           714:            CC, length, bi->index, bj->index);
        !           715:        return (true);
        !           716: }
        !           717: 
        !           718:        static void
        !           719: rmtail(b) register BLOCK *b; { /* remove tail of b */
        !           720: 
        !           721:        b->nextr = NULL;
        !           722:        MPRINTF("%ctail of block %d deleted\n", CC, b->index);
        !           723: }
        !           724: 
        !           725:        static void
        !           726: modrefs(pi, bi, bj) /* change all refs from bi to bj */
        !           727:        register NODE *pi; register BLOCK *bi, *bj; {
        !           728: 
        !           729:        register BLOCK *b;
        !           730: 
        !           731:        if (pi != NULL) { /* transfer labels, if any, from bi to bj */
        !           732:                /* bi->firstn points to the first label to be transferred,
        !           733:                 * pi points to the last. */
        !           734:                bj->firstn->back = pi;
        !           735:                pi->forw = bj->firstn;
        !           736:                bj->firstn = bi->firstn;
        !           737:                for ( ; ; pi = pi->back) { /* update the label table */
        !           738:                        ADDLBL(pi->ops[0], bj);
        !           739:                        if (pi == bi->firstn)
        !           740:                                break;
        !           741:                }
        !           742:        }
        !           743:        for (ALLB(b, &b0)) { /* update the block structure */
        !           744:                if (b->next == bi)
        !           745:                        b->next = bi->next;
        !           746:                if (b->nextl == bi)
        !           747:                        b->nextl = bj;
        !           748:                if (b->nextr == bi)
        !           749:                        b->nextr = bj;
        !           750:        }
        !           751: }
        !           752: 
        !           753:        static void
        !           754: reord() { /* reorder code */
        !           755: 
        !           756:        extern BLOCK *reord1();
        !           757:        extern void findlt();
        !           758:        register BLOCK *b;
        !           759: 
        !           760:        TRACE(reord);
        !           761: 
        !           762:        for (ALLB(b, b0.next)) {
        !           763:                b->ltest = NULL;
        !           764:                b->marked = 0; /* mark all blocks as unprocessed */
        !           765:        }
        !           766:        indegree(); /* compute indegree */
        !           767: 
        !           768:        if (nrot >= 0)
        !           769:                findlt(); /* find rotatable loops */
        !           770: 
        !           771:        /* tie blocks back together */
        !           772: 
        !           773:        if (pflag)
        !           774:                PRINTF("%cblock\tleft\tright\tcase\tlabels\n", CC);
        !           775:        Prevb = &b0;
        !           776:        for (b = b0.next; b != NULL; )
        !           777:                b = reord1(b);
        !           778:        if (Prevb->nextl != NULL)
        !           779:            putbr(Prevb);
        !           780:        Prevb->lastn->forw = &ntail;
        !           781:        ntail.back = Prevb->lastn; /* tack on tail node to text list */
        !           782: 
        !           783:        mkltbl(); /* make label table with only definitions */
        !           784:        rmunrch(true); /* remove unreachable code */
        !           785: }
        !           786: 
        !           787:        static void
        !           788: indegree() { /* compute indegree */
        !           789: 
        !           790:        register BLOCK *b, *bb;
        !           791: 
        !           792:        for (ALLB(b, b0.next))
        !           793:                b->indeg = 0;
        !           794:        for (ALLB(b, b0.next)) { /* compute indegree */
        !           795:                if ((bb = b->nextl) != NULL)
        !           796:                        bb->indeg++;
        !           797:                if ((bb = b->nextr) != NULL)
        !           798:                        bb->indeg++;
        !           799:        }
        !           800: }
        !           801: 
        !           802:        static void
        !           803: findlt() { /* find rotatable loops */
        !           804: 
        !           805:        /*
        !           806:         * To identify the top and termination-test of a rotatable loop:
        !           807:         * Look at the target of an unconditional backward branch.
        !           808:         * If it has only one reference, then it isn't the start of a loop.
        !           809:         * Then look at all intermediate blocks in lexical order
        !           810:         * to find a conditional jump past the backward branch.
        !           811:         * This is a very simplistic heuristic approach, because the loop
        !           812:         * test is actually never made.
        !           813:         * But it seems to give reasonable results rather rapidly.
        !           814:         * If there is more than one exit from the loop,
        !           815:         * rotate at the exit nearest to the bottom,
        !           816:         * in order to keep the elements of a compound test near each
        !           817:         * other (in case of window optimization)
        !           818:         * and near the bottom (in case of span-dependent branches).
        !           819:         */
        !           820: 
        !           821:        register BLOCK *b, *bl, *bb, *br;
        !           822: 
        !           823:        if (bflag)
        !           824:                PRINTF("%cltests are:", CC);
        !           825:        for (ALLB(b, b0.next)) {
        !           826:                if (b->nextr != NULL || (bl = b->nextl) == NULL ||
        !           827:                    bl->indeg < 2 || bl->index > b->index || bl->ltest != NULL)
        !           828:                        continue;
        !           829:                for (bb = bl; bb != NULL && bb->index < b->index; bb = bb->next)
        !           830:                        if ((br = bb->nextr) != NULL && br->index > b->index)
        !           831:                                bl->ltest = bb;
        !           832:                if (bflag && bl->ltest != NULL)
        !           833:                        PRINTF(" %d/%d", bl->index, bl->ltest->index);
        !           834:        }
        !           835:        if (bflag)
        !           836:                PUTCHAR('\n');
        !           837: }
        !           838: 
        !           839: #define B_EXIT 2
        !           840: 
        !           841:        static BLOCK *
        !           842: reord1(b) register BLOCK *b; {
        !           843: 
        !           844:        extern BLOCK *nextbr();
        !           845:        extern void prcase();
        !           846:        register BLOCK *bl, *br, *blt;
        !           847: 
        !           848:        /* top of rotatable loop */
        !           849:        /* don't rotate unless there already must be a branch to the entry */
        !           850: 
        !           851:        if (b->ltest != NULL && b != Prevb->nextl &&
        !           852:            (bl = b->ltest->nextl)->ltest == NULL && !bl->marked) {
        !           853:                b->ltest = NULL;
        !           854:                nrot++;
        !           855:                return (bl);
        !           856:        }
        !           857: 
        !           858:        /* mark block as processed and tie it in */
        !           859: 
        !           860:        b->marked++;
        !           861:        if (b != Prevb->nextl)
        !           862:                putbr(Prevb);
        !           863:        Prevb->lastn->forw = b->firstn;
        !           864:        b->firstn->back = Prevb->lastn;
        !           865:        Prevb = b;
        !           866: 
        !           867:        /* dead-end block */
        !           868: 
        !           869:        if ((bl = b->nextl) == NULL) {
        !           870:                PRCASE(0);
        !           871:                return (nextbr(b));
        !           872:        }
        !           873: 
        !           874:        bl->indeg--;
        !           875:        if ((br = b->nextr) != NULL)
        !           876:                br->indeg--;
        !           877: 
        !           878:        /* top of rotatable loop */
        !           879: 
        !           880:        if ((blt = bl->ltest) != NULL && blt->nextl->ltest == NULL &&
        !           881:            !blt->nextl->marked && !blt->nextr->marked && outdeg(bl) <= 1) {
        !           882:                PRCASE(1);
        !           883:                b = blt->nextl;
        !           884:                bl->ltest = NULL;
        !           885:                nrot++;
        !           886:                return (b);
        !           887:        }
        !           888: 
        !           889:        if (br == NULL) { /* unconditional branch or conditional to dead-end */
        !           890: 
        !           891:                if (!bl->marked) { /* to unprocessed block */
        !           892: 
        !           893:                        if (bl->indeg <= 0) { /* with indeg 1 */
        !           894:                                PRCASE(2);
        !           895:                                return (bl);
        !           896:                        }
        !           897: 
        !           898:                        /* branch to block with indeg > 1
        !           899:                           that originally followed this one */
        !           900: 
        !           901:                        if (bl == b->next) {
        !           902:                                PRCASE(3);
        !           903:                                return (bl);
        !           904:                        }
        !           905: 
        !           906:                        /* branch to dead-end block */
        !           907: 
        !           908:                        if (bl->nextl == NULL) {
        !           909:                                PRCASE(4);
        !           910:                                return (bl);
        !           911:                        }
        !           912: 
        !           913:                }
        !           914: 
        !           915:                /* all other unconditional branches */
        !           916: 
        !           917:                PRCASE(5);
        !           918:                return (nextbr(b));
        !           919:        }
        !           920: 
        !           921:        /* conditional branch to processed block */
        !           922: 
        !           923:        if (br->marked && !bl->marked) {
        !           924: 
        !           925:                /* fall through to unprocessed block with indeg = 1 */
        !           926: 
        !           927:                if (bl->indeg <= 0) {
        !           928:                        PRCASE(6);
        !           929:                        return (bl);
        !           930:                }
        !           931: 
        !           932:                /* fall through to unprocessed block with indeg > 1
        !           933:                   that originally followed this one */
        !           934: 
        !           935:                if (bl == b->next) {
        !           936:                        PRCASE(7);
        !           937:                        return (bl);
        !           938:                }
        !           939:        }
        !           940: 
        !           941:        /* reversible conditional branch to unprocessed block,
        !           942:           fall through to processed block */
        !           943: 
        !           944:        if (bl->marked && !br->marked && isrev(b->lastn)) {
        !           945:                revbr(b->lastn);
        !           946:                putp(b->lastn, label_left(b));
        !           947:                b->nextr = b->nextl;
        !           948:                b->nextl = br;
        !           949:                PRCASE(8);
        !           950:                return (br->indeg <= 0 ? br : nextbr(b));
        !           951:        }
        !           952: 
        !           953:        /* all other conditional branches that have one leg or the
        !           954:           other going to processed blocks */
        !           955: 
        !           956:        if (bl->marked || br->marked) {
        !           957:                PRCASE(9);
        !           958:                return (nextbr(b));
        !           959:        }
        !           960: 
        !           961:        /* fall through to block with indeg = 1
        !           962:           but not if it is an unlabeled unconditional transfer */
        !           963: 
        !           964:        if (bl->indeg <= 0 && !(isuncbr(bl->firstn) && isrev(b->lastn))) {
        !           965:                PRCASE(10);
        !           966:                return (bl);
        !           967:        }
        !           968: 
        !           969:        /* reversible branch to block with indeg = 1 */
        !           970: 
        !           971:        if (br->indeg <= 0 && isrev(b->lastn)) {
        !           972:                revbr(b->lastn);
        !           973:                putp(b->lastn, label_left(b));
        !           974:                b->nextr = b->nextl;
        !           975:                b->nextl = br;
        !           976:                PRCASE(11);
        !           977:                return (br);
        !           978:        }
        !           979: 
        !           980:        /* fall through to block with indeg > 1 that
        !           981:           originally followed this block */
        !           982: 
        !           983:        if (bl == b->next) {
        !           984:                PRCASE(12);
        !           985:                return (bl);
        !           986:        }
        !           987: 
        !           988:        /* everything else */
        !           989: 
        !           990:        PRCASE(13);
        !           991:        return (nextbr(b));
        !           992: }
        !           993: 
        !           994: /* Routine outdeg works in conjunction with loop rotation.  It uses a
        !           995: ** heuristic to determine how many of the loop exit target's remaining
        !           996: ** incoming arcs are due to exits from the loop that is to be rotated.
        !           997: ** Outdeg is called with a pointer to the top-of-loop block.  It scans
        !           998: ** lexically through the blocks that follow the top (much like findlt())
        !           999: ** until
        !          1000: **     1) there is no next block
        !          1001: **     2) the "left" path points at the loop top, indicating the block
        !          1002: **             is the loop end
        !          1003: **     3) the new block's index is at or past the loop target (since
        !          1004: **             findlt calls something a loop exit when the block index
        !          1005: **             of the "right" path is beyond the loop end)
        !          1006: **
        !          1007: ** As we scan through the blocks lexically, we decrement the effective
        !          1008: ** indegree of the loop target whenever we find a "right" path that
        !          1009: ** goes to the target from an unmarked block.  (If the block was marked,
        !          1010: ** its contribution to indegree has already been accounted for.)
        !          1011: */
        !          1012: 
        !          1013:        static int
        !          1014: outdeg(top)
        !          1015: BLOCK * top;                           /* pointer to top of loop */
        !          1016: {
        !          1017:     BLOCK * target = top->ltest->nextr;        /* loop exit target */
        !          1018:     BLOCK * bp;                                /* scanning block pointer */
        !          1019:     int indegree = target->indeg;      /* in-degree of target block */
        !          1020: 
        !          1021:     /* As a short-circuit, discontinue searching when the new indegree
        !          1022:     ** is <= 1
        !          1023:     */
        !          1024: 
        !          1025:     if (indegree <= 1)
        !          1026:        return(indegree);
        !          1027:     
        !          1028:     for (bp = top;
        !          1029:              bp != NULL                /* have a block */
        !          1030:           && bp->nextl != top          /* it doesn't close the loop */
        !          1031:           && bp->index < target->index ; /* it isn't past the target */
        !          1032:         bp = bp->next)
        !          1033:     {
        !          1034:        if (
        !          1035:              ! bp->marked              /* the block is unmarked */
        !          1036:            && bp->nextr == target      /* it branches cond. to target */
        !          1037:            && --indegree <= 1          /* time to quit */
        !          1038:            )
        !          1039:            break;
        !          1040:     }
        !          1041: 
        !          1042:     return(indegree);                  /* return effective indegree */
        !          1043: }
        !          1044: 
        !          1045: 
        !          1046:        static void
        !          1047: prcase(n, b) int n; register BLOCK *b; { /* print information during reord */
        !          1048: 
        !          1049:        register NODE *p;
        !          1050: 
        !          1051:        PRINTF("%c%d\t%d\t%d\t%d", CC, b->index,
        !          1052:            PRINDEX(nextl), PRINDEX(nextr), n);
        !          1053:        for (p = b->firstn; islabel(p); p = p->forw)
        !          1054:                PRINTF("\t%s", p->ops[0]);
        !          1055:        PRINTF("\n");
        !          1056: }
        !          1057: 
        !          1058:        static BLOCK *
        !          1059: nextbr(b) register BLOCK *b; { /* select next block to process */
        !          1060: 
        !          1061:        register BLOCK *bb;
        !          1062: 
        !          1063:        /* first look for orphan blocks (no more references) from the top */
        !          1064: 
        !          1065:        for (ALLB(bb, b0.next))
        !          1066:                if (!bb->marked && bb->indeg <= 0)
        !          1067:                        return (bb);
        !          1068: 
        !          1069:        /* now look for unmarked block with live consequent (circularly) */
        !          1070: 
        !          1071:        for (bb = b->next; bb != b; bb = bb->next)
        !          1072:                if (bb == NULL) /* circular scan for next block */
        !          1073:                        bb = &b0;
        !          1074:                else if (!bb->marked &&
        !          1075:                    bb->nextl != NULL && !bb->nextl->marked)
        !          1076:                        return (bb);
        !          1077: 
        !          1078:        /* now look for any unmarked block (circularly) */
        !          1079: 
        !          1080:        for (bb = b->next; bb != b; bb = bb->next)
        !          1081:                if (bb == NULL) /* circular scan for next block */
        !          1082:                        bb = &b0;
        !          1083:                else if (!bb->marked)
        !          1084:                        return (bb);
        !          1085: 
        !          1086:        return (NULL); /* no more blocks to process */
        !          1087: }
        !          1088: 
        !          1089:        static void
        !          1090: putbr(b) register BLOCK *b; { /* append a branch to b->nextl onto b */
        !          1091: 
        !          1092:        register NODE *p, *pl = b->lastn;
        !          1093:        char *s;
        !          1094: 
        !          1095:        if (b == &b0 || isuncbr(pl))
        !          1096:                return;
        !          1097:        ndisc--;
        !          1098:        nsave--;
        !          1099:        b->length++;
        !          1100:        p = Saveop(0, (char *)NULL, 0, GHOST); /* make node but don't link */
        !          1101:        b->lastn = pl->forw = p; /* link at end of this block */
        !          1102:        p->back = pl;
        !          1103:        s = label_left(b); /* get destination label, in 2 steps */
        !          1104:        setbr(p, s); /* in case setbr is a macro which double-evaluates */
        !          1105: }
        !          1106: 
        !          1107:        static char *
        !          1108: label_left(b) register BLOCK *b; { /* get label of b->nextl */
        !          1109: 
        !          1110:        register NODE *pf, *p;
        !          1111:        register BLOCK *bl;
        !          1112: 
        !          1113:        if ((bl = b->nextl) == NULL)
        !          1114:                FATAL("label of nonexistent block requested\n");
        !          1115:        for ( ; ISUNCBL(bl) && bl->nextl != bl; bl = bl->nextl)
        !          1116:                if (bl->nextl == NULL) {
        !          1117: 
        !          1118:                        char *s = getp(bl->lastn);
        !          1119: 
        !          1120:                        if (s == NULL) /* no target */
        !          1121:                                break;
        !          1122:                        b->nextl = NULL; /* dead-end */
        !          1123:                        return (s);
        !          1124:                }
        !          1125:        b->nextl = bl; /* re-aim b at final target */
        !          1126:        pf = bl->firstn;
        !          1127:        if (islabel(pf) && !ishl(pf))
        !          1128:                return (pf->ops[0]);
        !          1129:        p = Saveop(0, newlab(), 0, GHOST); /* make node but don't link */
        !          1130:        p->forw = pf; /* link at beginning of this block */
        !          1131:        p->back = pf->back;
        !          1132:        if (bl->marked) /* this block already processed by reord */
        !          1133:                pf->back->forw = p;
        !          1134:        bl->firstn = pf->back = p;
        !          1135:        setlab(p);
        !          1136:        return (p->ops[0]);
        !          1137: }
        !          1138: 
        !          1139:        static void
        !          1140: rmunrch(preserve) boolean preserve; { /* remove unreachable code */
        !          1141: 
        !          1142:        extern void reach();
        !          1143:        register REF *r;
        !          1144:        register BLOCK *b, *prevb;
        !          1145: 
        !          1146:        TRACE(rmunrch);
        !          1147: 
        !          1148:        if (b0.next == NULL)
        !          1149:                return;
        !          1150:        for (ALLB(b, b0.next))
        !          1151:                b->marked = 0;
        !          1152:        reach(b0.next); /* mark all blocks reachable from initial block */
        !          1153: 
        !          1154:        /* mark all blocks reachable from hard-label blocks */
        !          1155: 
        !          1156:        for (ALLB(b, b0.next))
        !          1157:                if (!b->marked && ishlp(b->firstn))
        !          1158:                        reach(b);
        !          1159: 
        !          1160:        /* mark all blocks reachable from non-text references */
        !          1161: 
        !          1162:        for (r = r0.nextref; r != NULL; r = r->nextref)
        !          1163:                if ((b = FINDLBL(r->lab)) != NULL && !b->marked)
        !          1164:                        reach(b);
        !          1165: 
        !          1166:        for (ALLB(b, b0.next)) /* remove unmarked blocks */
        !          1167:                if (b->marked)
        !          1168:                        prevb = b;
        !          1169:                else {
        !          1170:                        ndisc += b->length;
        !          1171:                        if (ISUNCBL(b) && islabel(b->firstn))
        !          1172:                                nsave++;
        !          1173:                        else {
        !          1174:                                if (uflag)
        !          1175:                                        PRINTF("%cunreachable block %d removed\n",
        !          1176:                                            CC, b->index);
        !          1177:                                nunr += b->length;
        !          1178:                        }
        !          1179:                        if (preserve) { /* node sequence must be preserved */
        !          1180:                            b->firstn->back->forw = b->lastn->forw;
        !          1181:                            b->lastn->forw->back = b->firstn->back;
        !          1182:                        }
        !          1183:                        prevb->next = b->next;
        !          1184:                }
        !          1185: }
        !          1186: 
        !          1187:        static void
        !          1188: reach(b) register BLOCK *b; { /* recursively mark reachable blocks */
        !          1189: 
        !          1190:        register BLOCK *bb;
        !          1191: 
        !          1192:        b->marked++;
        !          1193: 
        !          1194:        /*
        !          1195:         * Link around the second of successive removable branches with same
        !          1196:         * op-codes; multi-way branches (switches) must be identical in text.
        !          1197:         */
        !          1198: 
        !          1199:        while ((bb = b->nextl) != NULL && !bb->marked && bb->length == 1 &&
        !          1200:            bb->lastn->op == b->lastn->op && ISREMBR(bb->lastn)) {
        !          1201:                if(!(isuncbr(bb->lastn) || 
        !          1202:                     bb->nextr != NULL || same(bb->lastn, b->lastn)))
        !          1203:                        break;
        !          1204:                b->nextl = bb->nextl;
        !          1205:        }
        !          1206:        if (bb != NULL && !bb->marked)
        !          1207:                reach(bb);
        !          1208:        if ((bb = b->nextr) != NULL && !bb->marked)
        !          1209:                reach(bb);
        !          1210: }
        !          1211: 
        !          1212:        static void
        !          1213: rmbrs() { /* remove redundant branches */
        !          1214: 
        !          1215:        register BLOCK *b, *bl;
        !          1216:        register NODE *p;
        !          1217: 
        !          1218:        TRACE(rmbrs);
        !          1219: 
        !          1220:        for (ALLB(b, b0.next))
        !          1221:                if ((bl = b->nextl) != NULL &&
        !          1222:                    (p = b->lastn)->forw == bl->firstn && ISREMBR(p)) {
        !          1223: 
        !          1224:                        /* delete unconditional branch ahead of target */
        !          1225: 
        !          1226:                        if (isuncbr(p)) {
        !          1227:                                RMBR(p);
        !          1228:                                continue;
        !          1229:                        }
        !          1230: 
        !          1231:                        /* delete conditional branch ahead of target
        !          1232:                           or ahead of unconditional branch to same target */
        !          1233: 
        !          1234:                        do {
        !          1235:                                if (b->nextr == bl || b->nextr == NULL &&
        !          1236:                                    bl->nextl == NULL && ISUNCBL(bl) &&
        !          1237:                                    sameaddr(p, bl->lastn)) {
        !          1238:                                        RMBR(p);
        !          1239:                                        break;
        !          1240:                                }
        !          1241:                        } while (    ISUNCBL(bl)
        !          1242:                                 &&  bl != bl->nextl    /* avoid self-loop */
        !          1243:                                 && (bl = bl->nextl) != NULL);
        !          1244:                }
        !          1245: }
        !          1246: /* ldanal -- perform live/dead analysis over flow graph
        !          1247: **
        !          1248: ** This routine calculates live/dead register information for the
        !          1249: ** entire flow graph in these steps:
        !          1250: **
        !          1251: **  1. Allocate temporary array to hold block-level live/dead info.
        !          1252: **     Initialize it.
        !          1253: **  2. On a block-wise basis, determine registers set and used by
        !          1254: **     each instruction.  Determine registers used and set by the
        !          1255: **     block.
        !          1256: **  3. Propagate register use/set information throughout the flow
        !          1257: **     graph blocks.
        !          1258: **  4. Propagate final information back through each block to
        !          1259: **     reflect correct live/dead information for each instruction.
        !          1260: **
        !          1261: **  We use the live/dead algorithm described in the Aho and Ullman
        !          1262: **  "dragon book".
        !          1263: */
        !          1264: 
        !          1265: #ifdef LIVEDEAD
        !          1266:        void
        !          1267: ldanal() { /* perform live-dead register analysis */
        !          1268: 
        !          1269:     typedef unsigned int LDREG;
        !          1270:     register BLOCK * b;                        /* pointer to current block */
        !          1271:     register NODE * p;                 /* pointer to current inst. node */
        !          1272:     struct ldinfo                      /* temporary block-level structure */
        !          1273:     {
        !          1274:        LDREG buses;                    /* registers used by block */
        !          1275:        LDREG bdef;                     /* registers defined (set) by block */
        !          1276:        LDREG bin;                      /* registers live coming into block */
        !          1277:        LDREG bout;                     /* registers live exiting block */
        !          1278:     };
        !          1279:     struct ldinfo * lddata;            /* array of data for each block */
        !          1280:     register struct ldinfo * ldptr;    /* pointer to one of the above */
        !          1281:     unsigned i;
        !          1282:     boolean changed;
        !          1283: 
        !          1284:     TRACE(ldanal);
        !          1285: 
        !          1286:     bldgr(false); /* update block structure but don't call bboptim */
        !          1287:     lddata = NEWBLK(idx + 1, struct ldinfo);
        !          1288: 
        !          1289: /* Initialize:  set the recently allocated array to zero.  The idea, here,
        !          1290: ** is that each entry in the array corresponds to one block in the flow
        !          1291: ** graph.  We assume that blocks have sequential index numbers and that
        !          1292: ** idx is the last index number.
        !          1293: */
        !          1294: 
        !          1295:     CLEAR(lddata, (idx + 1) * sizeof(struct ldinfo));
        !          1296: 
        !          1297: /* Step 2.  Calculate uses/def for each node and for the containing block. */
        !          1298: 
        !          1299:     for (ALLB(b,b0.next))
        !          1300:     {
        !          1301:        ldptr = lddata + b->index;
        !          1302:        for (p = b->lastn; !islabel(p); p = p->back)
        !          1303:        {
        !          1304:            p->nlive = uses(p) | LIVEREGS; /* what's used here, + always live */
        !          1305:            p->ndead = sets(p) & ~p->nlive; /* what's set, but not used, here */
        !          1306:            ldptr->buses = (p->nlive | (ldptr->buses & ~p->ndead)) & REGS;
        !          1307:                                        /* current live registers */
        !          1308:            ldptr->bdef = (p->ndead | (ldptr->bdef & ~p->nlive)) & REGS;
        !          1309:                                        /* current registers killed by block */
        !          1310: 
        !          1311:            if (p == b->firstn)         /* stop if reached first node */
        !          1312:                break;
        !          1313:        }
        !          1314: 
        !          1315:     }
        !          1316: 
        !          1317: /* Propagate live/dead data throughout the flow graph, using Aho and
        !          1318: ** Ullman algorithm.
        !          1319: */
        !          1320: 
        !          1321:     do
        !          1322:     {
        !          1323:        changed = false;                /* will continue until no changes */
        !          1324: 
        !          1325:        for (ALLB(b,b0.next))
        !          1326:        {
        !          1327:            LDREG in, out;
        !          1328: 
        !          1329:            if (b->nextr == NULL && (b->nextl == NULL || 
        !          1330:                                        (isbr(b->lastn) && !isuncbr(b->lastn))))
        !          1331:            {
        !          1332:            /* This case represents a return, or an unconditional indexed
        !          1333:            ** jump, or a switch.  If we had better connectivity in the
        !          1334:            ** flow graph, we could trace all successors correctly.  As
        !          1335:            ** things are, we have to assume the worst about what registers
        !          1336:            ** are live going into the next block.  For a return, this means
        !          1337:            ** those registers that can be used to return a value.  For
        !          1338:            ** others, we mark all registers live.
        !          1339:            */
        !          1340:                out = isret(b->lastn) ? RETREG : REGS;
        !          1341:            }
        !          1342:            else
        !          1343:            {
        !          1344:                /* OUT = union (of successors) IN */
        !          1345:                out = 0;                /* registers out of current block. */
        !          1346:                if (b->nextr != NULL)
        !          1347:                    out |= lddata[b->nextr->index].bin;
        !          1348:                if (b->nextl != NULL)
        !          1349:                    out |= lddata[b->nextl->index].bin;
        !          1350:            }
        !          1351: 
        !          1352:            ldptr = lddata + b->index;  /* point at data for current block */
        !          1353:            /* IN = OUT - DEF u USE */
        !          1354:            in = (out & ~ldptr->bdef) | ldptr->buses;
        !          1355: 
        !          1356:            /* see what changed */
        !          1357: 
        !          1358:            if (in != ldptr->bin || out != ldptr->bout)
        !          1359:            {
        !          1360:                changed = true;
        !          1361:                ldptr->bin = in;        /* set changed values */
        !          1362:                ldptr->bout = out;
        !          1363:            }
        !          1364:        } /* end for */
        !          1365:     } while (changed);
        !          1366: 
        !          1367: /* Now set the final live/dead (really, just live) information in
        !          1368: ** each node of each block.
        !          1369: */
        !          1370: 
        !          1371:     for (ALLB(b,b0.next))
        !          1372:     {
        !          1373:        /* go backward again through each block */
        !          1374:        /* initial live is outgoing regs of block */
        !          1375: 
        !          1376:        LDREG live = lddata[b->index].bout;
        !          1377:        for (p = b->lastn; !islabel(p); p = p->back)
        !          1378:        {
        !          1379:            LDREG newlive = (p->nlive | (live & ~p->ndead)) & REGS;
        !          1380:            p->nlive = live;            /* live for this node is what was
        !          1381:                                        ** live going into successor
        !          1382:                                        */
        !          1383:            live = newlive;             /* live for next node is whatever
        !          1384:                                        ** else we used, but didn't kill
        !          1385:                                        */
        !          1386:            if (p == b->firstn)
        !          1387:                break;                  /* quit if first node in block */
        !          1388:        }
        !          1389:     }
        !          1390: 
        !          1391:     xfree((char *) lddata);            /* free up temp. storage */
        !          1392: }
        !          1393: 
        !          1394: #endif /* def LIVEDEAD */
        !          1395: 
        !          1396: #ifdef PEEPHOLE
        !          1397: static NODE *pf;       /* pointer to first window node */
        !          1398: static NODE *opf;      /* pointer to predecessor of first window node */
        !          1399: static int wsize;      /* window size for peephole trace */
        !          1400: 
        !          1401: window(size, func) register int size; boolean (*func)(); { /* peephole scan */
        !          1402: 
        !          1403:        extern NODE *initw();
        !          1404:        register NODE *pl;
        !          1405:        register int i;
        !          1406: 
        !          1407:        TRACE(window);
        !          1408: 
        !          1409:        /* find first window */
        !          1410: 
        !          1411:        wsize = size;
        !          1412:        if ((pl = initw(n0.forw)) == NULL)
        !          1413:                return;
        !          1414: 
        !          1415:        /* move window through code */
        !          1416: 
        !          1417:        for (opf = pf->back; ; opf = pf->back) {
        !          1418:                if ((*func)(pf, pl) == true) {
        !          1419:                        if (wflag)
        !          1420:                                if (opf->forw == pl->forw)
        !          1421:                                        PRINTF("%cdeleted\n", CC);
        !          1422:                                else {
        !          1423:                                        PRINTF("%cchanged to:\n", CC);
        !          1424:                                        prwindow(opf->forw, size);
        !          1425:                                }
        !          1426:                        if (size > 1) {
        !          1427: 
        !          1428:                                /* move window back in case
        !          1429:                                   there is an overlapping improvement */
        !          1430: 
        !          1431:                                for (i = 2; i <= size; i++)
        !          1432:                                        if ((opf = opf->back) == &n0) {
        !          1433:                                                opf = n0.forw;
        !          1434:                                                break;
        !          1435:                                        }
        !          1436:                                if ((pl = initw(opf)) == NULL)
        !          1437:                                        return;
        !          1438:                                continue;
        !          1439:                        }
        !          1440:                }
        !          1441: 
        !          1442:                /* move window ahead */
        !          1443: 
        !          1444:                if ((pl = pl->forw) == &ntail)
        !          1445:                        return;
        !          1446:                pf = pf->forw;
        !          1447:                if (islabel(pl) && (pl = initw(pl->forw)) == NULL)
        !          1448:                        return;
        !          1449:        }
        !          1450: }
        !          1451: 
        !          1452:        static NODE *
        !          1453: initw(p) register NODE *p; { /* find first available window */
        !          1454: 
        !          1455:        register int i;
        !          1456: 
        !          1457:        if ((pf = p) == NULL)
        !          1458:                return (NULL);
        !          1459: 
        !          1460:        /* move p down until window is large enough */
        !          1461: 
        !          1462:        for (i = 1; i <= wsize; i++) {
        !          1463:                if (p == &ntail) /* no more windows */
        !          1464:                        return (NULL);
        !          1465:                if (islabel(p)) { /* restart scan */
        !          1466:                        pf = p->forw;
        !          1467:                        i = 0;
        !          1468:                }
        !          1469:                p = p->forw;
        !          1470:        }
        !          1471:        return (p->back);
        !          1472: }
        !          1473: 
        !          1474: wchange() { /* print window before change */
        !          1475: 
        !          1476:        if (wflag) {
        !          1477:                PRINTF("%cwindow:\n", CC);
        !          1478:                prwindow(opf->forw, wsize);
        !          1479:        }
        !          1480: }
        !          1481: 
        !          1482:        static
        !          1483: prwindow(p, size) /* print "size" instructions starting at p */
        !          1484:        register NODE *p; register int size; {
        !          1485: 
        !          1486:        for ( ; --size >= 0 && p != &ntail && !islabel(p); p = p->forw) {
        !          1487:                PUTCHAR(CC);
        !          1488: #ifdef LIVEDEAD
        !          1489:                PRINTF("(live: 0x%X)", p->nlive);
        !          1490: #endif
        !          1491:                prinst(p);
        !          1492:        }
        !          1493: }
        !          1494: #endif
        !          1495: 
        !          1496:        static void
        !          1497: mkltbl() { /* make label table with only definitions */
        !          1498: 
        !          1499:        register BLOCK *b;
        !          1500:        register NODE *p;
        !          1501: 
        !          1502:        clrltbl();
        !          1503: 
        !          1504:        /* add definitions from labels in text section */
        !          1505: 
        !          1506:        for (ALLB(b, b0.next))
        !          1507:                for (p = b->firstn; islabel(p); p = p->forw)
        !          1508:                        ADDLBL(p->ops[0], b);
        !          1509: }
        !          1510: 
        !          1511:        static
        !          1512: clrltbl() { /* clear label table */
        !          1513: 
        !          1514:        CLEAR(Lbltbl, N_LBLS * sizeof(LBL));
        !          1515:        Numlbls = 0;
        !          1516: }
        !          1517: 
        !          1518:        static BLOCK *
        !          1519: lblhash(l, b) register char *l; BLOCK *b; { /* add or find label in label table */
        !          1520: 
        !          1521:        register LBL *p;
        !          1522:        register int lh = 0, c;
        !          1523:        register char *ll = l;
        !          1524: 
        !          1525:        while ((c = *ll++) != '\0')
        !          1526:                lh += c;
        !          1527:        /*
        !          1528:         * The precheck on the third character avoids many superfluous
        !          1529:         * calls to strcmp when the hash table is fairly full.  The third
        !          1530:         * character is chosen because most compilers generate labels
        !          1531:         * with an invariant two-character prefix.  In a later version,
        !          1532:         * perhaps labels should be converted at the machine-dependent
        !          1533:         * level into unique integers instead of being stored as strings.
        !          1534:         */
        !          1535:        for (p = Lbltbl + lh % N_LBLS; p->cp != NULL &&
        !          1536:            (l[2] != p->cp[2] && l[1] != '\0' || strcmp(p->cp, l)); )
        !          1537:                if ((p -= H_INCR) < Lbltbl)
        !          1538:                        p += N_LBLS;
        !          1539:        if (b != NULL) { /* enter or overwrite the block entry */
        !          1540:                if (p->bl == NULL && ++Numlbls >= N_LBLS)
        !          1541:                        FATAL("too many labels\n");
        !          1542:                p->cp = l;
        !          1543:                p->bl = b;
        !          1544:        }
        !          1545:        return (p->bl);
        !          1546: }
        !          1547: 
        !          1548:        char *
        !          1549: getspace(n) register unsigned n; { /* return a pointer to "n" bytes */
        !          1550: 
        !          1551:        register char *p = Lasta;
        !          1552: 
        !          1553:        /* round up so pointers are always word-aligned */
        !          1554:        /* int conversions are to avoid call to software remaindering */
        !          1555: 
        !          1556:        n += sizeof(char *) - ((int) n % (int) sizeof(char *));
        !          1557:        Maxu += n;
        !          1558:        while ((Lasta += n) >= Lastx) {
        !          1559:                *Space = NEWBLK(1, struct space_t);
        !          1560:                p = Lasta = (char *) &(*Space)->space[0];
        !          1561:                Lastx = (char *) &(*Space)->space[NSPACE - 1];
        !          1562:                (*Space)->next = NULL;
        !          1563:                Space = &(*Space)->next;
        !          1564:        }
        !          1565:        return (p);
        !          1566: }
        !          1567: /* Branch shortening
        !          1568: **
        !          1569: ** This code shortens span-dependent branches with assistance from
        !          1570: ** machine dependent routines.  The interface is as follows:
        !          1571: **
        !          1572: **     bspan(flag)     is the entry point available to machine-
        !          1573: **                     dependent routines; the flag is true to print
        !          1574: **                     debugging information
        !          1575: **
        !          1576: **     BSHORTEN        symbol, defined in "defs"; enables all this
        !          1577: **
        !          1578: **     int instsize(node)
        !          1579: **                     routine or macro; returns upper bound on size of
        !          1580: **                     instruction in node in arbitrary units
        !          1581: **     void bshorten(node,dist)
        !          1582: **                     routine or macro; changes op at node to be
        !          1583: **                     shortened version of branch, based on (long)
        !          1584: **                     distance (dist) between branch and target
        !          1585: **
        !          1586: ** The algorithm proceeds in two passes over the blocks of the program.
        !          1587: ** The first pass calculates the relative PC (program counter) value for
        !          1588: ** the beginning of each block.  (Remember, labels are always at the
        !          1589: ** beginning of a block.)  Since branches are always at the end of blocks,
        !          1590: ** the assumption is that the machine's program counter register always
        !          1591: ** points to the beginning of the block following the branch when the
        !          1592: ** branch is executed.  (This assumption for the purpose of calculating
        !          1593: ** distances.)  Branches are assumed to be shortenable both forward and
        !          1594: ** backward.
        !          1595: **
        !          1596: ** The PC values for the blocks are kept in a dynamically allocated
        !          1597: ** array.  The array is size idx+2, where idx is the highest block
        !          1598: ** number.  The +2 accounts for not using array[0] (we index into
        !          1599: ** the array by block index numbers which are non-zero) and for one
        !          1600: ** additional entry at the end to contain the PC just after the
        !          1601: ** last block.
        !          1602: **
        !          1603: ** Pass two calculates distances between branches and their targets
        !          1604: ** and shortens branches which can be shortened.
        !          1605: */
        !          1606: 
        !          1607: #ifdef BSHORTEN
        !          1608: 
        !          1609: void
        !          1610: bspan(flag)                            /* shorten span-dependent branches */
        !          1611: boolean flag;                          /* true to print debug info. */
        !          1612: {
        !          1613:     long * bpc;                                /* point to array of PC's */
        !          1614:     register BLOCK * block;            /* block pointer */
        !          1615:     register NODE * node;              /* pointer for scanning block's nodes */
        !          1616:     BLOCK * target;                    /* branch target block */
        !          1617:     char * label;                      /* branch label string */
        !          1618:     long pc;                           /* current PC */
        !          1619:     long pcdiff;                       /* PC difference, branch to target */
        !          1620:     extern int instsize();             /* returns size of instruction */
        !          1621: 
        !          1622:     bldgr(false);                      /* build flow graph */
        !          1623: /* allocate array for block start PC's */
        !          1624: 
        !          1625:     bpc = (long *) xalloc( sizeof(long) * (idx+2));
        !          1626:     pc = 0;                            /* current PC */
        !          1627: 
        !          1628:     /* make first pass to compute PC at start of each block */
        !          1629: 
        !          1630:     if (flag)
        !          1631:        PRINTF("%c Block starting PC:\n", CC);
        !          1632: 
        !          1633:     for ( ALLB(block, b0.next) )
        !          1634:     {
        !          1635:        if (flag)
        !          1636:            PRINTF("%c\t%d\t%d\n", CC, block->index, pc);
        !          1637: 
        !          1638:        bpc[block->index] = pc;         /* current PC is block start PC */
        !          1639:        for (node = block->firstn ; ; node = node->forw)
        !          1640:        {
        !          1641:            pc += instsize(node);       /* increase PC by instruction size */
        !          1642:            if (node == block->lastn)
        !          1643:                break;                  /* done this block at last inst. */
        !          1644:        }
        !          1645:     }
        !          1646:     bpc[idx+1] = pc;                   /* set PC of non-existent next block */
        !          1647:     if (flag)
        !          1648:        PRINTF("%c\t(last)\t%d\n", CC, pc);
        !          1649:     /* Pass 2.  Try to shorten branches. */
        !          1650: 
        !          1651:     for ( ALLB(block, b0.next) )
        !          1652:     {
        !          1653:        if (isbr(block->lastn) && (label = getp(block->lastn)) != NULL)
        !          1654:        {
        !          1655:            /* Beware of non-existent target for branch */
        !          1656: 
        !          1657:            if((target = FINDLBL(label)) == NULL)
        !          1658:                pcdiff = ~((unsigned long) 0) >> 1; /* maximum offset */
        !          1659:            else
        !          1660:                pcdiff = bpc[target->index]     /* target PC */
        !          1661:                        - bpc[block->index + 1];
        !          1662:                                        /* branch PC (PC of next block */
        !          1663: 
        !          1664:            /* shorten branch if branch-to-target distance short enough */
        !          1665: 
        !          1666:            if (flag)
        !          1667:            {
        !          1668:                PRINTF("%c Difference:  %d -- Shorten:\t", CC, pcdiff);
        !          1669:                prinst(block->lastn);
        !          1670:            }
        !          1671:            bshorten(block->lastn,pcdiff);
        !          1672:        }
        !          1673:     }
        !          1674:     xfree((char *) bpc);               /* free up array */
        !          1675:     return;
        !          1676: }
        !          1677: 
        !          1678: #endif /* def BSHORTEN */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.