usr/src/cmd/pi/pccaseop.c

/* Copyright (c) 1980 Regents of the University of California */

static  char sccsid[] = "@(#)pccaseop.c 1.4 10/8/80";

#include "whoami.h"
#ifdef PC
    /*
     *  and the rest of the file
     */
#include "0.h"
#include "tree.h"
#include "objfmt.h"
#include "pcops.h"
#include "pc.h"

    /*
     *  structure for a case:
     *      its constant label, line number (for errors), and location label.
     */
struct ct {
    long        cconst;
    int         cline;
    int         clabel;
};

    /*
     *  the P2FORCE operator puts its operand into a register.
     *  these to keep from thinking of it as r0 all over.
     */
#define FORCENAME       "r0"
#define FORCENUMBER     0

    /*
     *  given a tree for a case statement, generate code for it.
     *  this computes the expression into a register,
     *  puts down the code for each of the cases,
     *  and then decides how to do the case switching.
     *  tcase   [0]     T_CASE
     *          [1]     lineof "case"
     *          [2]     expression
     *          [3]     list of cased statements:
     *                  cstat   [0]     T_CSTAT
     *                          [1]     lineof ":"
     *                          [2]     list of constant labels
     *                          [3]     statement
     */
pccaseop( tcase )
    int *tcase;
{
    struct nl   *exprtype;
    struct nl   *rangetype;
    long        low;
    long        high;
    long        exprctype;
    long        swlabel;
    long        endlabel;
    long        label;
    long        count;
    long        *cstatlp;
    long        *cstatp;
    long        *casep;
    struct ct   *ctab;
    struct ct   *ctp;
    long        i;
    long        nr;
    long        goc;
    int         casecmp();
    bool        dupcases;

    goc = gocnt;
        /*
         *  find out the type of the case expression
         *  even if the expression has errors (exprtype == NIL), continue.
         */
    line = tcase[1];
    exprtype = rvalue( (int *) tcase[2] , NIL  , RREQ );
    if ( exprtype != NIL ) {
        if ( isnta( exprtype , "bcsi" ) ) {
            error("Case selectors cannot be %ss" , nameof( exprtype ) );
            exprtype = NIL;
        } else {
            if ( exprtype -> class != RANGE ) {
                rangetype = exprtype -> type;
            } else {
                rangetype = exprtype;
            }
            if ( rangetype == NIL ) {
                exprtype = NIL;
            } else {
                low = rangetype -> range[0];
                high = rangetype -> range[1];
            }
        }
    }
    if ( exprtype != NIL ) {
            /*
             *  put expression into a register
             *  save its c-type and jump to the code to do the switch.
             */
        putop( P2FORCE , P2INT );
        putdot( filename , line );
        exprctype = p2type( exprtype );
        swlabel = getlab();
        putjbr( swlabel );
    }
        /*
         *  count the number of cases
         *  and allocate table for cases, lines, and labels
         *  default case goes in ctab[0].
         */
    count = 1;
    for ( cstatlp = tcase[3] ; cstatlp != NIL ; cstatlp = cstatlp[2] ) {
        cstatp = cstatlp[1];
        if ( cstatp == NIL ) {
            continue;
        }
        for ( casep = cstatp[2] ; casep != NIL ; casep = casep[2] ) {
            count++;
        }
    }
        /*
         */
    ctab = (struct ct *) malloc( count * sizeof( struct ct ) );
    if ( ctab == (struct ct *) 0 ) {
        error("Ran out of memory (case)");
        pexit( DIED );
    }
        /*
         *  pick up default label and label for after case statement.
         */
    ctab[0].clabel = getlab();
    endlabel = getlab();
        /*
         *  generate code for each case
         *  filling in ctab for each.
         *  nr is for error if no case falls out bottom.
         */
    nr = 1;
    count = 0;
    for ( cstatlp = tcase[3] ; cstatlp != NIL ; cstatlp = cstatlp[2] ) {
        cstatp = cstatlp[1];
        if ( cstatp == NIL ) {
            continue;
        }
        line = cstatp[1];
        label = getlab();
        for ( casep = cstatp[2] ; casep != NIL ; casep = casep[2] ) {
            gconst( casep[1] );
            if( exprtype == NIL || con.ctype == NIL ) {
                continue;
            }
            if ( incompat( con.ctype , exprtype , NIL ) ) {
                cerror("Case label type clashed with case selector expression type");
                continue;
            }
            if ( con.crval < low || con.crval > high ) {
                error("Case label out of range");
                continue;
            }
            count++;
            ctab[ count ].cconst = con.crval;
            ctab[ count ].cline = line;
            ctab[ count ].clabel = label;
        }
            /*
             *  put out the statement
             */
        putlab( label );
        putcnt();
        level++;
        statement( cstatp[3] );
        nr &= noreach;
        noreach = 0;
        level--;
        if (gotos[cbn]) {
                ungoto();
        }
        putjbr( endlabel );
    }
    noreach = nr;
        /*
         *      default action is to call error
         */
    putlab( ctab[0].clabel );
    putleaf( P2ICON , 0 , 0 , ADDTYPE( P2FTN | P2INT , P2PTR ) , "_ERROR" );
    putleaf( P2ICON , ECASE , 0 , P2INT , 0 );
    putleaf( P2REG , FORCENUMBER , 0 , P2INT , 0 );
    putop( P2LISTOP , P2INT );
    putop( P2CALL , P2INT );
    putdot( filename , line );
        /*
         *  sort the cases
         */
    qsort( &ctab[1] , count , sizeof (struct ct) , casecmp );
        /*
         *  check for duplicates
         */
    dupcases = FALSE;
    for ( ctp = &ctab[1] ; ctp < &ctab[ count ] ; ctp++ ) {
        if ( ctp[0].cconst == ctp[1].cconst ) {
            error("Multiply defined label in case, lines %d and %d" ,
                    ctp[0].cline , ctp[1].cline );
            dupcases = TRUE;
        }
    }
    if ( dupcases ) {
        return;
    }
        /*
         *  choose a switch algorithm and implement it:
         *      direct switch   >= 1/3 full and >= 4 cases.
         *      binary switch   not direct switch and > 8 cases.
         *      ifthenelse      not direct or binary switch.
         */
    putlab( swlabel );
    if ( ctab[ count ].cconst - ctab[1].cconst < 3 * count && count >= 4 ) {
        directsw( ctab , count );
    } else if ( count > 8 ) {
        binarysw( ctab , count );
    } else {
        itesw( ctab , count );
    }
    putlab( endlabel );
    if ( goc != gocnt ) {
            putcnt();
    }
}

    /*
     *  direct switch
     */
directsw( ctab , count )
    struct ct   *ctab;
    int         count;
{
    int         fromlabel = getlab();
    long        i;
    long        j;

    putprintf( "        casel   %s,$%d,$%d" , 0 , FORCENAME ,
            ctab[1].cconst , ctab[ count ].cconst - ctab[1].cconst );
    putlab( fromlabel );
    i = 1;
    j = ctab[1].cconst;
    while ( i <= count ) {
        if ( j == ctab[ i ].cconst ) {
            putprintf( "        .word   " , 1 );
            putprintf( PREFIXFORMAT , 1 , LABELPREFIX , ctab[ i ].clabel );
            putprintf( "-" , 1 );
            putprintf( PREFIXFORMAT , 0 , LABELPREFIX , fromlabel );
            i++;
        } else {
            putprintf( "        .word   " , 1 );
            putprintf( PREFIXFORMAT , 1 , LABELPREFIX , ctab[ 0 ].clabel );
            putprintf( "-" , 1 );
            putprintf( PREFIXFORMAT , 0 , LABELPREFIX , fromlabel );
        }
        j++;
    }
    putjbr( ctab[0].clabel );
}

    /*
     *  binary switch
     *  special case out default label and start recursion.
     */
binarysw( ctab , count )
    struct ct   *ctab;
    int         count;
{

    bsrecur( ctab[0].clabel , &ctab[0] , count );
}

    /*
     *  recursive log( count ) search.
     */
bsrecur( deflabel , ctab , count )
    int         deflabel;
    struct ct   *ctab;
    int         count;
{

    if ( count <= 0 ) {
        putprintf( "    jbr     L%d" , 0 , deflabel );
        return;
    } else if ( count == 1 ) {
        putprintf( "    cmpl    %s,$%d" , 0 , FORCENAME , ctab[1].cconst );
        putprintf( "    jeql    L%d" , 0 , ctab[1].clabel );
        putprintf( "    jbr     L%d" , 0 , deflabel );
        return;
    } else {
        int     half = ( count + 1 ) / 2;
        int     gtrlabel = getlab();

        putprintf( "    cmpl    %s,$%d" , 0 , FORCENAME , ctab[ half ].cconst );
        putprintf( "    jgtr    L%d" , 0 , gtrlabel );
        putprintf( "    jeql    L%d" , 0 , ctab[ half ].clabel );
        bsrecur( deflabel , &ctab[0] , half - 1 );
        putprintf( "L%d:" , 0 , gtrlabel );
        bsrecur( deflabel , &ctab[ half ] , count - half );
        return;
    }
}

itesw( ctab , count )
    struct ct   *ctab;
    int         count;
{
    int i;

    for ( i = 1 ; i <= count ; i++ ) {
        putprintf( "    cmpl    %s,$%d" , 0 , FORCENAME , ctab[ i ].cconst );
        putprintf( "    jeql    L%d" , 0 , ctab[ i ].clabel );
    }
    putprintf( "        jbr     L%d" , 0 , ctab[0].clabel );
    return;
}
int
casecmp( this , that )
    struct ct   *this;
    struct ct   *that;
{
    if ( this -> cconst < that -> cconst ) {
        return -1;
    } else if ( this -> cconst > that -> cconst ) {
        return 1;
    } else {
        return 0;
    }
}
#endif PC