Return to livereg.c CVS log

Up to [Research Unix] / researchv9 / cmd / sun / c2

Annotation of researchv9/cmd/sun/c2/livereg.c, revision 1.1

1.1     ! root        1: 
        !             2: #ifndef lint
        !             3: static char sccsid[] = "@(#)livereg.c 1.1 86/02/03 Copyr 1985 Sun Micro";
        !             4: #endif
        !             5: 
        !             6: /*
        !             7:  * Copyright (c) 1985 by Sun Microsystems, Inc.
        !             8:  */
        !             9: 
        !            10: #include "as.h"
        !            11: #include "c2.h"
        !            12: 
        !            13: #define MAXLIVE 10000
        !            14: NODE *heap_o_nodes[MAXLIVE];
        !            15: NODE **nextnode = heap_o_nodes;
        !            16: int nlive = 0;
        !            17: 
        !            18: static void
        !            19: pushlive( m )
        !            20:     NODE *m;
        !            21: {
        !            22:     if (++nlive>MAXLIVE) sys_error("nursury overflow\n");
        !            23:     *(nextnode++) = m;
        !            24: }
        !            25: 
        !            26: static NODE *
        !            27: poplive()
        !            28: {
        !            29:     if (nlive<=0) return (NODE *)NULL;
        !            30:     nlive--;
        !            31:     return *(--nextnode);
        !            32: }
        !            33: 
        !            34: #define killreg(m) (m)
        !            35: 
        !            36: regmask
        !            37: compute_meet( mp, ll, lr )
        !            38:     NODE *mp;
        !            39:     regmask ll, lr;
        !            40: {
        !            41:     /* the liveset compuation of a "meet" node: conditional branch */
        !            42:     /* return ((ll|lr)&~killreg(mp->rset))|mp->ruse; */
        !            43:     return (addmask(submask(addmask(ll, lr) , killreg(mp->rset)), mp->ruse));
        !            44: }
        !            45: 
        !            46: regmask
        !            47: compute_indirect( mp )
        !            48:     NODE *mp;
        !            49: {
        !            50:     register NODE *np = mp->forw->forw;
        !            51:     regmask r; 
        !            52: 
        !            53:     r  = regmask0;
        !            54:     while (np->op==OP_CSWITCH){
        !            55:        r = addmask( r, np->rlive);
        !            56:        np=np->forw;
        !            57:     }
        !            58:     /* return (r&~killreg(mp->rset)) | mp->ruse; */
        !            59:     return ( addmask( submask( r, killreg(mp->rset) ), mp->ruse ));
        !            60: }
        !            61: 
        !            62: regmask
        !            63: compute_normal( mp, ll )
        !            64:     NODE *mp;
        !            65:     regmask ll;
        !            66: {
        !            67:     /* the liveset compuattion of a normal, boring instruction */
        !            68:     /* return (ll & ~killreg(mp->rset)) | mp->ruse ; */
        !            69:     return ( addmask( submask( ll, killreg(mp->rset)), mp->ruse));
        !            70: }
        !            71: 
        !            72: livereg(){
        !            73:     /*
        !            74:      * Each node in the program has a field called rlive; this is where
        !            75:      * we keep track of registers and pieces of registers that will
        !            76:      * be used before they're next written. This set represents the state
        !            77:      * of the registers BEFORE entering the node.
        !            78:      * Here's our strategy:
        !            79:      *  A) find all the return nodes: they kill all register except d0/d1.
        !            80:      *     put them on the stack. as well as unconditional jumps ( this gets
        !            81:      *     us into all loops, and will get better when we get smarter. )
        !            82:      *  B) if the stack is empty, we're done; else take a node off the stack.
        !            83:      *  C) look at the predecessor node. It is one of these:
        !            84:      *    i) a label: has the same liveset as its successor. Find all of the
        !            85:      *       uses of the label we can, and for each, compute:
        !            86:      *       a) if an unconditional branch, then liveset  is same as label's. If
        !            87:      *          it is different, change it and put it on the stack. 
        !            88:      *          (Stacking may be superfluous here...we'll see).
        !            89:      *       b) a binary (conditional) branch. compute liveset as the product
        !            90:      *          of the livesets of its successors, plus the registers it reads,
        !            91:      *          less those it writes . If this set changes
        !            92:      *          from previous value, put the node on the stack.
        !            93:      *       c) A multiway branch: same as binary branch.
        !            94:      *   ii) an unconditional branch: liveset does not depend on successor.
        !            95:      *       go back to step B).
        !            96:      *  iii) a conditional branch. Compute as i.b) above.  <If value 
        !            97:      *       does not change , go back to step B and get a new node, 
        !            98:      *       else continue.> <<-- this may be wrong.
        !            99:      *   iv) a multiway branch: same as conditional branch.
        !           100:      *    v) a straight-line instruction: liveset is successor liveset, plus
        !           101:      *       registers it sets, less those it reads. continue back.
        !           102:      * D) Loop on step (C) until we either stop because of a stable branch,
        !           103:      *    ( see C.ii , C.iii), or until we fall off the beginning. Then
        !           104:      *    go back to B.
        !           105:      */
        !           106: 
        !           107:     register NODE * p, *puse, *csw;
        !           108:     regmask l, newl;
        !           109: 
        !           110:     for (p=first.forw; p != &first; p=p->forw){
        !           111:        /*
        !           112:         * recompute live sets starting from null sets --
        !           113:         * This is a last-minute kludge for 3.0, to patch over a
        !           114:         * problem that occurs in content() (failure to update
        !           115:         * live sets when a constant or memory reference is replaced
        !           116:         * by a register).  Remove the following assignment when the
        !           117:         * problem is fixed correctly.
        !           118:         */
        !           119:        p->rlive = regmask0;
        !           120:        if (p->op == OP_EXIT){
        !           121:            p->rlive = compute_normal( p, regmask_all );
        !           122:            p->rlive = submask( p->rlive, MAKERMASK( CCREG, LR) );
        !           123:            p->rlive = submask( p->rlive, MAKERMASK( FPCCREG, LR) );
        !           124:            p->rlive = submask( p->rlive, MAKERMASK( FP0REG, LR) );
        !           125:            p->rlive = submask( p->rlive, MAKERMASK( FP0REG+1, LR) );
        !           126:            p->rlive = submask( p->rlive, MAKERMASK( A0REG, LR) );
        !           127:            p->rlive = submask( p->rlive, MAKERMASK( A0REG+1, LR) );
        !           128:            pushlive( p );
        !           129:        } else if (p->op==OP_JUMP && p->subop==JALL){
        !           130:            pushlive( p );
        !           131:        } else if (p->op==OP_BRANCH){
        !           132:            p->rlive = regmask_all; /* don't know -- must consider all live */
        !           133:            pushlive( p );
        !           134:        }
        !           135:     }
        !           136: 
        !           137:     while ((p=poplive())!=NULL){
        !           138:        l = p->rlive; 
        !           139:        while( (p=p->back) != &first ){
        !           140:            switch (p->op){
        !           141:            case OP_LABEL:
        !           142:                p->rlive = l;
        !           143:                for (puse=p->luse; puse ; puse=puse->lnext){
        !           144:                    /* its a jump */
        !           145:                    if (puse->op ==OP_CSWITCH){
        !           146:                        /* part of a multi-way branch */
        !           147:                        if (!samemask( puse->rlive, l )){
        !           148:                            csw = puse;
        !           149:                            puse->rlive=l;
        !           150:                            while (csw->op != OP_JUMP)
        !           151:                                csw=csw->back;
        !           152:                            /* now found indirect jump */
        !           153:                            newl = compute_indirect(csw);
        !           154:                            if (!samemask( csw->rlive , newl) ){
        !           155:                                csw->rlive = newl;
        !           156:                                pushlive( csw );
        !           157:                            }
        !           158:                        }
        !           159:                        continue;
        !           160:                    } else if (puse->subop == JALL){
        !           161:                        newl = l;
        !           162:                    } else {
        !           163:                        newl = compute_meet( puse, puse->forw->rlive, l);
        !           164:                    }
        !           165:                    if (!samemask( puse->rlive , newl) ){
        !           166:                        puse->rlive = newl;
        !           167:                        pushlive( puse );
        !           168:                    }
        !           169:                }
        !           170:                continue;
        !           171:            case OP_JUMP:
        !           172:            case OP_DJMP:
        !           173:                if (p->subop == JALL)
        !           174:                    goto popnew;
        !           175:                else if (p->subop == JIND){
        !           176:                    newl = compute_indirect( p );
        !           177:                }else{
        !           178:                    newl = compute_meet( p,p->forw->rlive, p->luse->rlive );
        !           179:                }
        !           180:                p->rlive = l = newl;
        !           181:                continue;
        !           182:            case OP_CSWITCH:
        !           183:                goto popnew;
        !           184:            case OP_BRANCH:
        !           185:                /* know nothing about its behavior--guess the worst*/
        !           186:                l = regmask_all;
        !           187:                continue;
        !           188:            case OP_EXIT:
        !           189:                goto popnew;
        !           190:            default:
        !           191:                l = p->rlive = compute_normal( p, l);
        !           192:                continue;
        !           193:            }
        !           194:        }
        !           195:     popnew:;
        !           196:     }
        !           197: }

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