Return to optim.c CVS log

Up to [MW Coherent from dump] / coherent / d / bin / cc / c / n2

Annotation of coherent/d/bin/cc/c/n2/optim.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * C compiler.
        !             3:  * Jump and shape optimization.
        !             4:  * Jump to jump, etc.
        !             5:  * Common sequences.
        !             6:  * Cross jumping.
        !             7:  */
        !             8: #ifdef   vax
        !             9: #include "INC$LIB:cc2.h"
        !            10: #else
        !            11: #include "cc2.h"
        !            12: #endif
        !            13: 
        !            14: #define        NLHASH  64
        !            15: #define        LHMASK  077
        !            16: 
        !            17: static INS     *labhash[NLHASH];
        !            18: 
        !            19: /*
        !            20:  * Shuffle segments,
        !            21:  * Move all non 'SHRI' segments to the front,
        !            22:  * then squash any extra switches out of the stream.
        !            23:  * This is necessary to make code that is together in
        !            24:  * memory together in the 'ins' lists.
        !            25:  */
        !            26: shuffle()
        !            27: {
        !            28:        register INS    *fp, *ip;
        !            29:        register INS    *niloc;
        !            30:        INS             *bep, *bfp;
        !            31:        register int    curseg;
        !            32: 
        !            33:        niloc = &ins;
        !            34:        for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
        !            35:                if (ip->i_type != ENTER)
        !            36:                        continue;
        !            37:                bfp = ip;
        !            38:                do {
        !            39:                        ip = ip->i_fp;
        !            40:                } while (ip->i_type != ENTER);
        !            41:                if (bfp != ins.i_fp) {
        !            42:                        bep = ip;
        !            43:                        ip = bfp->i_bp;
        !            44:                        bfp->i_bp->i_fp = bep->i_fp;
        !            45:                        bep->i_fp->i_bp = bfp->i_bp;
        !            46:                        niloc->i_fp->i_bp = bep;
        !            47:                        bfp->i_bp = niloc;
        !            48:                        bep->i_fp = niloc->i_fp;
        !            49:                        niloc->i_fp = bfp;
        !            50:                        niloc = bep;
        !            51:                }
        !            52:        }
        !            53:        curseg = dotseg;
        !            54:        for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
        !            55:                if (ip->i_type != ENTER)
        !            56:                        continue;
        !            57:                while ((fp=ip->i_fp)!=&ins && fp->i_type==ENTER)
        !            58:                        ip = deleteins(ip, ip->i_fp)->i_fp;
        !            59:                if (ip->i_seg == curseg) {
        !            60:                        ip = deleteins(ip, ip->i_fp);
        !            61:                        continue;
        !            62:                }
        !            63:                curseg = ip->i_seg;
        !            64:        }
        !            65: }
        !            66: 
        !            67: /*
        !            68:  * Delete node ip.
        !            69:  * Return a pointer to the previous node.
        !            70:  * Merge any line number references onto ip1.
        !            71:  */
        !            72: INS *
        !            73: deleteins(ip, ip1)
        !            74: register INS   *ip;
        !            75: INS            *ip1;
        !            76: {
        !            77:        register INS    *bp, *fp;
        !            78: 
        !            79:        mrgdbgt(ip, ip1);
        !            80:        if ((ip->i_type==JUMP || ip->i_type==LLLINK) && ((fp=ip->i_ip)!=NULL))
        !            81:                decrefc(fp);
        !            82:        bp = ip->i_bp;
        !            83:        fp = ip->i_fp;
        !            84:        bp->i_fp = fp;
        !            85:        fp->i_bp = bp;
        !            86:        free((char *) ip);
        !            87:        return (bp);
        !            88: }
        !            89: 
        !            90: /*
        !            91:  * Decrement the reference count on a label.
        !            92:  * Delete it if the label is now unreferenced.
        !            93:  * It is a fatal error to hand this routine a non label.
        !            94:  */
        !            95: decrefc(ip)
        !            96: register INS   *ip;
        !            97: {
        !            98:        if (ip->i_type != LLABEL)
        !            99:                cbotch("decrefc passed non label");
        !           100:        if (--ip->i_refc == 0)
        !           101:                deleteins(ip, ip->i_fp);
        !           102: }
        !           103: 
        !           104: /*
        !           105:  * Set up label reference counts and delete any unused labels.
        !           106:  */
        !           107: labels()
        !           108: {
        !           109:        register INS    *fp, *ip, *lp;
        !           110:        INS             *findlab();
        !           111:        register int    curseg, i;
        !           112: 
        !           113:        for (i=0; i<NLHASH; ++i)
        !           114:                labhash[i] = NULL;
        !           115:        curseg = dotseg;
        !           116:        for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
        !           117:                if (ip->i_type == ENTER)
        !           118:                        curseg = ip->i_seg;
        !           119:                else if (ip->i_type == LLABEL) {
        !           120:                        ip->i_refc = 0;
        !           121:                        /*
        !           122:                         * Hack the reference count on the
        !           123:                         * label if it is the label on a switch
        !           124:                         * table to prevent it from being deleted
        !           125:                         * by the next bit of code. Kludgy.
        !           126:                         */
        !           127:                        if (curseg != SCODE)
        !           128:                                ++ip->i_refc;
        !           129:                        else if ((fp=ip->i_fp) != &ins) {
        !           130:                                if (fp->i_type == LLLINK)
        !           131:                                        ++ip->i_refc;
        !           132:                                else if (fp->i_type == CODE
        !           133:                                     &&  fp->i_op >= ZBYTE
        !           134:                                     &&  fp->i_op <= ZGPTR)
        !           135:                                        ++ip->i_refc;
        !           136:                        }
        !           137:                        labhash[ip->i_labno&LHMASK] = ip;
        !           138:                }
        !           139:        }
        !           140:        for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
        !           141:                if (ip->i_type!=JUMP && ip->i_type!=LLLINK)
        !           142:                        continue;
        !           143:                if ((lp=findlab(ip->i_labno)) != NULL) {
        !           144:                        while ((fp=lp->i_fp)!=&ins && fp->i_type==LLABEL)
        !           145:                                lp = fp;
        !           146:                        ip->i_labno = lp->i_labno;
        !           147:                        ++lp->i_refc;
        !           148:                }
        !           149:                ip->i_ip = lp;
        !           150:        }
        !           151:        for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
        !           152:                if (ip->i_type!=LLABEL || ip->i_refc!=0)
        !           153:                        continue;
        !           154:                ip = deleteins(ip, ip->i_fp);
        !           155:                ++nlabdel;
        !           156:        }
        !           157: }
        !           158: 
        !           159: /*
        !           160:  * Find label.
        !           161:  * Quick test using hashtable.
        !           162:  * Long linear search if that fails.
        !           163:  */
        !           164: INS *
        !           165: findlab(n)
        !           166: register int   n;
        !           167: {
        !           168:        register INS    *lp;
        !           169: 
        !           170:        if ((lp=labhash[n&LHMASK])!=NULL && lp->i_labno==n)
        !           171:                return (lp);
        !           172:        for (lp=ins.i_fp; lp!=&ins; lp=lp->i_fp)
        !           173:                if (lp->i_type==LLABEL && lp->i_labno==n)
        !           174:                        return (lp);
        !           175:        return (NULL);
        !           176: }
        !           177: 
        !           178: /*
        !           179:  * Delete dead code.
        !           180:  * Dead code begins after an unconditional jump and continues
        !           181:  * until the next label, segment change or the EPILOG.
        !           182:  */
        !           183: deadcode()
        !           184: {
        !           185:        register INS    *fp, *ip;
        !           186:        register int    t;
        !           187: 
        !           188:        for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
        !           189:                t = ip->i_type;
        !           190:                if (t == LLLINK) {      /* Switch table */
        !           191:                        while ((fp=ip->i_fp) != &ins && (fp->i_type == LLLINK
        !           192:                          || (fp->i_type == CODE && opinfo[fp->i_op].op_style
        !           193:                          == OF_WORD)))
        !           194:                                ip = fp;
        !           195:                } else if (t != JUMP || ip->i_rel != UNCON)
        !           196:                        continue;
        !           197:                fp = ip->i_fp;
        !           198:                while (fp != &ins) {
        !           199:                        t = fp->i_type;
        !           200:                        if (t==LLABEL || t==EPILOG || t==ENTER)
        !           201:                                break;
        !           202:                        fp = deleteins(fp, fp->i_fp)->i_fp;
        !           203:                        ++ndead;
        !           204:                        ++changes;
        !           205:                }
        !           206:        }
        !           207: }
        !           208: 
        !           209: /*
        !           210:  * Fix some of the more common funny things
        !           211:  * associated with jump instructions and labels.
        !           212:  * There are more things that could be done.
        !           213:  * These five things should get most of the common things.
        !           214:  */
        !           215: fixbr()
        !           216: {
        !           217:        register INS    *ip, *ip1, *ip2;
        !           218:        INS             *ip3, *ip4;
        !           219:        int             t;
        !           220: 
        !           221: again:
        !           222:        for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
        !           223:                t = ip->i_type;
        !           224:                /* Jump to jump. */
        !           225:                if ((t==JUMP && ischnrel(ip->i_rel)) || t==LLLINK) {
        !           226:                        ip1 = ip->i_ip;
        !           227:                        if (ip1 != NULL) {
        !           228:                                ip2 = ip1;
        !           229:                                for (;;) {
        !           230:                                        while (ip2->i_type == LLABEL)
        !           231:                                                ip2 = ip2->i_fp;
        !           232:                                        if (ip2->i_type!=JUMP
        !           233:                                        ||  ip2->i_rel!=UNCON)
        !           234:                                                break;
        !           235:                                        ip3 = ip2->i_ip;
        !           236:                                        if (ip3==NULL
        !           237:                                         || ip3==ip1
        !           238:                                         || ip3==ip2->i_bp)
        !           239:                                                break;
        !           240:                                        ip2 = ip3;
        !           241:                                }
        !           242:                                ip2 = ip2->i_bp;
        !           243:                                if (ip1 != ip2) {
        !           244:                                        decrefc(ip1);
        !           245:                                        increfc(ip2);
        !           246:                                        ip->i_labno = ip2->i_labno;
        !           247:                                        ip->i_ip = ip2;
        !           248:                                        ++nbrbr;
        !           249:                                        ++changes;
        !           250:                                }
        !           251:                        }
        !           252:                }
        !           253:                /* Reversible jump over unconditional jump. */
        !           254:                if (t==JUMP && isrevrel(ip->i_rel)) {
        !           255:                        ip1 = ip->i_fp;
        !           256:                        if (ip1->i_type==JUMP && ip1->i_rel==UNCON) {
        !           257:                                ip2 = ip1->i_fp;
        !           258:                                if (ip2->i_type==LLABEL && ip->i_ip==ip2) {
        !           259:                                        ip1->i_rel = revrel(ip->i_rel);
        !           260:                                        deleteins(ip, ip1);
        !           261:                                        ++ncbrbr;
        !           262:                                        ++changes;
        !           263:                                        goto again;
        !           264:                                }
        !           265:                        }
        !           266:                }
        !           267:                /* Jump to next instruction. */
        !           268:                if (t==JUMP && ip->i_ip==ip->i_fp) {
        !           269:                        deleteins(ip, ip->i_fp);
        !           270:                        ++nbrnext;
        !           271:                        ++changes;
        !           272:                        goto again;
        !           273:                }
        !           274:                /*
        !           275:                 * The preceding optimizations do not change the code order,
        !           276:                 * so they can be executed even if VNOOPT.
        !           277:                 * The following optimizations do change the code order,
        !           278:                 * so they are suppressed if VNOOPT.
        !           279:                 */
        !           280:                if (isvariant(VNOOPT))
        !           281:                        continue;
        !           282:                /*
        !           283:                 * [ip]JUMP L1; [ip1]L2:...; [ip2]L1:...; [ip3]JUMP L2; ...
        !           284:                 * becomes [ip2]L1:...; [ip1]L2:...; [ip]JUMP L1; ...
        !           285:                 * Saves a jump in every for loop.
        !           286:                 */
        !           287:                if (t==JUMP && ip->i_rel==UNCON) {
        !           288:                        ip1 = ip->i_fp;
        !           289:                        if (ip1!=&ins && ip1->i_type==LLABEL) {
        !           290:                                ip2 = NULL;
        !           291:                                for (ip3=ip1->i_fp; ip3!=&ins; ip3=ip3->i_fp) {
        !           292:                                        if (ip3->i_type==LLABEL
        !           293:                                           && ip->i_ip==ip3)
        !           294:                                                ip2 = ip3;
        !           295:                                        else if (ip2!=NULL
        !           296:                                              && ip3->i_type==JUMP
        !           297:                                              && ip3->i_rel==UNCON
        !           298:                                              && ip3->i_ip==ip1) {
        !           299:                                                ip4 = ip2->i_bp;
        !           300:                                                ip->i_bp->i_fp = ip2;
        !           301:                                                ip3->i_bp->i_fp = ip1;
        !           302:                                                ip4->i_fp = ip;
        !           303:                                                ip->i_fp = ip3;
        !           304:                                                ip2->i_bp = ip->i_bp;
        !           305:                                                ip1->i_bp = ip3->i_bp;
        !           306:                                                ip->i_bp = ip4;
        !           307:                                                ip3->i_bp = ip;
        !           308:                                                deleteins(ip3, ip1);
        !           309:                                                ++nexbr;
        !           310:                                                ++changes;
        !           311:                                                goto again;
        !           312:                                        }
        !           313:                                }
        !           314:                        }
        !           315:                }
        !           316:                /*
        !           317:                 * [ip] JUMP L1; <code1>; [ip2] JUMP L2; [ip1] L1: <code2>; [ip3] L2:
        !           318:                 * becomes [ip1] L1: <code2>; [ip] JUMP L2; <code1>; [ip3] L2:
        !           319:                 * Saves a jump in every switch and restores natural code order.
        !           320:                 * <code2> often ends in JUMP or LLLINK, in which case JUMP L2
        !           321:                 * gets optimized out later.
        !           322:                 */
        !           323:                if (t==JUMP && ip->i_rel==UNCON && precedes(ip, ip->i_ip)) {
        !           324:                        ip1 = ip->i_ip;
        !           325:                        ip2 = ip1->i_bp;
        !           326:                        if (ip2->i_type==JUMP && ip2->i_rel==UNCON
        !           327:                            && precedes(ip1, ip2->i_ip)) {
        !           328:                                ip3 = ip2->i_ip;
        !           329:                                /* Rearrange the code. */
        !           330:                                ip->i_bp->i_fp = ip1;
        !           331:                                ip3->i_bp->i_fp = ip;
        !           332:                                ip2->i_fp = ip3;
        !           333:                                ip1->i_bp = ip->i_bp;
        !           334:                                ip->i_bp = ip3->i_bp;
        !           335:                                ip3->i_bp = ip2;
        !           336:                                /* Change JUMP L1 at ip into JUMP L2. */
        !           337:                                ip->i_ip = ip3;
        !           338:                                ip->i_labno = ip3->i_labno;
        !           339:                                increfc(ip3);
        !           340:                                decrefc(ip1);
        !           341:                                /* Delete the now extraneous JUMP. */
        !           342:                                deleteins(ip2, ip3);
        !           343:                                ++nexbr;
        !           344:                                ++changes;
        !           345:                                goto again;
        !           346:                        }
        !           347:                }
        !           348:        }
        !           349: }
        !           350: 
        !           351: /*
        !           352:  * Return true iff ip1 precedes ip2 in the INS node chain.
        !           353:  */
        !           354: static
        !           355: precedes(ip1, ip2)
        !           356: register INS *ip1, *ip2;
        !           357: {
        !           358:        while ((ip1 = ip1->i_fp) != &ins)
        !           359:                if (ip1 == ip2)
        !           360:                        return(1);
        !           361:        return(0);
        !           362: }
        !           363: 
        !           364: /*
        !           365:  * Increment the reference count on a label.
        !           366:  * It is a fatal error to hand this routine a non label.
        !           367:  */
        !           368: increfc(ip)
        !           369: register INS   *ip;
        !           370: {
        !           371:        if (ip->i_type != LLABEL)
        !           372:                cbotch("increfc passed non label");
        !           373:        ++ip->i_refc;
        !           374: }
        !           375: 
        !           376: /*
        !           377:  * Insert a label.
        !           378:  * It has been 'increfc'ed.
        !           379:  * Return pointer to the new label.
        !           380:  */
        !           381: INS *
        !           382: inslab(ip)
        !           383: register INS   *ip;
        !           384: {
        !           385:        register INS    *lp, *bp;
        !           386: 
        !           387:        if (ip->i_type == LLABEL) {
        !           388:                increfc(ip);
        !           389:                return (ip);
        !           390:        }
        !           391:        lp = (INS *) malloc(sizeof(INS));
        !           392:        if (lp != NULL) {
        !           393:                lp->i_type = LLABEL;
        !           394:                lp->i_labno = newlab();
        !           395:                lp->i_sp = NULL;
        !           396:                lp->i_refc = 1;
        !           397:                bp = ip->i_bp;
        !           398:                bp->i_fp = lp;
        !           399:                lp->i_fp = ip;
        !           400:                ip->i_bp = lp;
        !           401:                lp->i_bp = bp;
        !           402:        }
        !           403:        return (lp);
        !           404: }
        !           405: 
        !           406: /*
        !           407:  * Cross jumps.
        !           408:  * If the same code precedes an unconditional jump and
        !           409:  * the label to which it jumps, replace the former with
        !           410:  * a jump to a new local label.
        !           411:  */
        !           412: xjumps()
        !           413: {
        !           414:        register INS    *ip, *lp;
        !           415: 
        !           416:        for (ip=ins.i_fp; ip!=&ins; ip=ip->i_fp) {
        !           417:                if (ip->i_type!=JUMP || ip->i_rel!=UNCON
        !           418:                || (lp = ip->i_ip)==NULL)
        !           419:                        continue;
        !           420:                if (!docomseq(lp, ip, &nxjump))
        !           421:                        return;
        !           422:        }
        !           423: }
        !           424: 
        !           425: /*
        !           426:  * Compare two nodes.
        !           427:  * True return if the same.
        !           428:  * Never called on strange stuff
        !           429:  * or labels.
        !           430:  */
        !           431: xeq(ip1, ip2)
        !           432: register INS   *ip1, *ip2;
        !           433: {
        !           434:        register int    t;
        !           435: 
        !           436:        if ((t=ip1->i_type) != ip2->i_type)
        !           437:                return (0);
        !           438:        if (t==JUMP || t==LLLINK) {
        !           439:                if (ip1->i_labno != ip2->i_labno)
        !           440:                        return (0);
        !           441:                if (t==JUMP && ip1->i_rel!=ip2->i_rel)
        !           442:                        return (0);
        !           443:                return (1);
        !           444:        }
        !           445:        if (t != CODE)
        !           446:                cbotch("xeq");
        !           447:        if (ip1->i_op != ip2->i_op)
        !           448:                return (0);
        !           449:        if (ip1->i_naddr != ip2->i_naddr)
        !           450:                return (0);
        !           451:        return (cmpfield(ip1, ip2));
        !           452: }
        !           453: 
        !           454: /*
        !           455:  * Detect common sequences before jumps.
        !           456:  * When found, replace the later with a jump to a new
        !           457:  * local label preceding the former.
        !           458:  */
        !           459: comseq()
        !           460: {
        !           461:        register INS    *ip, *xp, *yp;
        !           462: 
        !           463:        for (xp=ins.i_fp; xp!=&ins; xp=xp->i_fp) {
        !           464:                if (xp->i_type!=JUMP || xp->i_rel!=UNCON)
        !           465:                        continue;
        !           466:                ip = xp->i_ip;
        !           467:                if (ip==NULL || ip->i_type != LLABEL)
        !           468:                        continue;
        !           469:                for (yp=xp->i_fp; yp!=&ins; yp=yp->i_fp) {
        !           470:                        if (yp->i_type==JUMP && yp->i_rel==UNCON
        !           471:                        &&  yp->i_ip==ip) {
        !           472:                                if (!docomseq(xp, yp, &ncomseq))
        !           473:                                        return;
        !           474:                        }
        !           475:                }
        !           476:        }
        !           477: }
        !           478: 
        !           479: 
        !           480: /*
        !           481:  * Back up through the code looking for valid cross jumps.
        !           482:  * When found, insert a new local label before the first
        !           483:  * and change the second into an unconditional jump to it.
        !           484:  * Called from xjumps and comseq.
        !           485:  * Returns 0 if the new node allocation fails.
        !           486:  */
        !           487: docomseq(xp, yp, countp)
        !           488: register INS *xp, *yp;
        !           489: int *countp;
        !           490: {
        !           491:        for (;;) {
        !           492:                xp = xp->i_bp;
        !           493:                if (xp==&ins || xp->i_type==LLABEL || xp->i_type==LLLINK)
        !           494:                        break;
        !           495:                yp = yp->i_bp;
        !           496:                if (yp==&ins || yp->i_type==LLABEL || yp->i_type==LLLINK
        !           497:                             || xeq(xp, yp)==0)
        !           498:                        break;
        !           499:                xp = inslab(xp);
        !           500:                if (xp == NULL)
        !           501:                        return (0);
        !           502:                mrgdbgt(yp, xp->i_fp);
        !           503:                if ((yp->i_type==JUMP || yp->i_type==LLLINK) && yp->i_ip!=NULL)
        !           504:                        decrefc(yp->i_ip);
        !           505:                yp->i_type = JUMP;
        !           506:                yp->i_labno = xp->i_labno;
        !           507:                yp->i_sp = NULL;
        !           508:                yp->i_ip = xp;
        !           509:                yp->i_rel = UNCON;
        !           510:                yp->i_long = 0;
        !           511:                ++*countp;
        !           512:                ++changes;
        !           513:        }
        !           514:        return(1);
        !           515: }

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