home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / pascal / src / pccaseop.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-16  |  14.5 KB  |  514 lines
  1. /*-
  2.  * Copyright (c) 1980 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #ifndef lint
  35. static char sccsid[] = "@(#)pccaseop.c    5.3 (Berkeley) 4/16/91";
  36. #endif /* not lint */
  37.  
  38. #include "whoami.h"
  39. #ifdef PC
  40.     /*
  41.      *    and the rest of the file
  42.      */
  43. #include "0.h"
  44. #include "tree.h"
  45. #include "objfmt.h"
  46. #include <pcc.h>
  47. #include "pc.h"
  48. #include "tmps.h"
  49. #include "tree_ty.h"
  50.  
  51.     /*
  52.      *    structure for a case: 
  53.      *        its constant label, line number (for errors), and location label.
  54.      */
  55. struct ct {
  56.     long    cconst;
  57.     int        cline;
  58.     int        clabel;
  59. };
  60.  
  61.     /*
  62.      *    the PCC_FORCE operator puts its operand into a register.
  63.      *    these to keep from thinking of it as r0 all over.
  64.      */
  65. #if defined(vax) || defined(tahoe)
  66. #   define    FORCENAME    "r0"
  67. #endif vax || tahoe
  68. #ifdef mc68000
  69. #   define    FORCENAME    "d0"
  70. #   define    ADDRTEMP    "a0"
  71. #endif mc68000
  72.  
  73.     /*
  74.      *    given a tree for a case statement, generate code for it.
  75.      *    this computes the expression into a register,
  76.      *    puts down the code for each of the cases,
  77.      *    and then decides how to do the case switching.
  78.      *    tcase    [0]    T_CASE
  79.      *        [1]    lineof "case"
  80.      *        [2]    expression
  81.      *        [3]    list of cased statements:
  82.      *            cstat    [0]    T_CSTAT
  83.      *                [1]    lineof ":"
  84.      *                [2]    list of constant labels
  85.      *                [3]    statement
  86.      */
  87. pccaseop( tcase )
  88.     WHI_CAS *tcase;
  89. {
  90.     struct nl    *exprtype;
  91.     struct nl    *exprnlp;
  92.     struct nl    *rangetype;
  93.     long    low;
  94.     long    high;
  95.     long    exprctype;
  96.     char     *swlabel;
  97.     char    *endlabel;
  98.     char    *label;
  99.     int        count;
  100.     struct tnode *cstatlp;
  101.     struct tnode *cstatp;
  102.     struct tnode *casep;
  103.     struct ct    *ctab;
  104.     struct ct    *ctp;
  105.     bool    nr;
  106.     long    goc;
  107.     int        casecmp();
  108.     bool    dupcases;
  109.  
  110.     goc = gocnt;
  111.     /*
  112.      *  find out the type of the case expression
  113.      *  even if the expression has errors (exprtype == NIL), continue.
  114.      */
  115.     line = tcase->line_no;
  116.     codeoff();
  117.     exprtype = rvalue( tcase->expr , NLNIL  , RREQ );
  118.     codeon();
  119.     if ( exprtype != NLNIL ) {
  120.     if ( isnta( exprtype , "bcsi" ) ) {
  121.         error("Case selectors cannot be %ss" , nameof( exprtype ) );
  122.         exprtype = NLNIL;
  123.     } else {
  124.         if ( exprtype -> class != RANGE ) {
  125.         rangetype = exprtype -> type;
  126.         } else {
  127.         rangetype = exprtype;
  128.         }
  129.         if ( rangetype == NLNIL ) {
  130.         exprtype = NLNIL;
  131.         } else {
  132.         low = rangetype -> range[0];
  133.         high = rangetype -> range[1];
  134.         }
  135.     }
  136.     }
  137.     if ( exprtype != NLNIL ) {
  138.         /*
  139.          *    compute and save the case expression.
  140.          *    also, put expression into a register
  141.          *    save its c-type and jump to the code to do the switch.
  142.          */
  143.     exprctype = p2type( exprtype );
  144.     exprnlp = tmpalloc( (long) (sizeof (long)), nl + T4INT , NOREG );
  145.     putRV((char *) 0 , cbn , exprnlp -> value[ NL_OFFS ] ,
  146.             exprnlp -> extra_flags , PCCT_INT );
  147.     (void) rvalue( tcase->expr , NLNIL , RREQ );
  148.     sconv((int) exprctype, (int) PCCT_INT);
  149.     putop( PCC_ASSIGN , PCCT_INT );
  150.     putop( PCC_FORCE , PCCT_INT );
  151.     putdot( filename , line );
  152.     swlabel = getlab();
  153.     putjbr( (long) swlabel );
  154.     }
  155.     /*
  156.      *  count the number of cases
  157.      *  and allocate table for cases, lines, and labels
  158.      *  default case goes in ctab[0].
  159.      */
  160.     count = 1;
  161.     for ( cstatlp = tcase->stmnt_list ; cstatlp != TR_NIL ;
  162.         cstatlp = cstatlp->list_node.next ) {
  163.     cstatp = cstatlp->list_node.list;
  164.     if ( cstatp == TR_NIL ) {
  165.         continue;
  166.     }
  167.     for ( casep = cstatp->c_stmnt.const_list ; casep != TR_NIL ;
  168.             casep = casep->list_node.next ) {
  169.         count++;
  170.     }
  171.     }
  172.     /*
  173.      */
  174.     ctab = (struct ct *) malloc( count * sizeof( struct ct ) );
  175.     if ( ctab == (struct ct *) 0 ) {
  176.     error("Ran out of memory (case)");
  177.     pexit( DIED );
  178.     }
  179.     /*
  180.      *  pick up default label and label for after case statement.
  181.      */
  182.     ctab[0].clabel = (int) getlab();
  183.     endlabel = getlab();
  184.     /*
  185.      *  generate code for each case
  186.      *  filling in ctab for each.
  187.      *  nr is for error if no case falls out bottom.
  188.      */
  189.     nr = TRUE;;
  190.     count = 0;
  191.     for ( cstatlp = tcase->stmnt_list ; cstatlp != TR_NIL ;
  192.         cstatlp = cstatlp->list_node.next ) {
  193.     cstatp = cstatlp->list_node.list;
  194.     if ( cstatp == TR_NIL ) {
  195.         continue;
  196.     }
  197.     line = cstatp->c_stmnt.line_no;
  198.     label = getlab();
  199.     for ( casep = cstatp->c_stmnt.const_list ; casep != TR_NIL ;
  200.             casep = casep->list_node.next ) {
  201.         gconst( casep->list_node.list );
  202.         if( exprtype == NLNIL || con.ctype == NIL ) {
  203.         continue;
  204.         }
  205.         if ( incompat( con.ctype , exprtype , TR_NIL ) ) {
  206.         cerror("Case label type clashed with case selector expression type");
  207.         continue;
  208.         }
  209.         if ( con.crval < low || con.crval > high ) {
  210.         error("Case label out of range");
  211.         continue;
  212.         }
  213.         count++;
  214.         ctab[ count ].cconst = con.crval;
  215.         ctab[ count ].cline = line;
  216.         ctab[ count ].clabel = (int) label;
  217.     }
  218.         /*
  219.          *    put out the statement
  220.          */
  221.     (void) putlab( label );
  222.     putcnt();
  223.     level++;
  224.     statement( cstatp->c_stmnt.stmnt );
  225.     nr = (nr && noreach)?TRUE:FALSE;
  226.     noreach = FALSE;
  227.     level--;
  228.     if (gotos[cbn]) {
  229.         ungoto();
  230.     }
  231.     putjbr( (long) endlabel );
  232.     }
  233.     noreach = nr;
  234.     /*
  235.      *    default action is to call error
  236.      */
  237.     (void) putlab( (char *) ctab[0].clabel );
  238.     putleaf( PCC_ICON , 0 , 0 , PCCM_ADDTYPE( PCCTM_FTN | PCCT_INT , PCCTM_PTR ) , "_CASERNG" );
  239.     putRV((char *) 0 , cbn , exprnlp -> value[ NL_OFFS ] ,
  240.             exprnlp -> extra_flags , PCCT_INT );
  241.     putop( PCC_CALL , PCCT_INT );
  242.     putdot( filename , line );
  243.     /*
  244.      *  sort the cases
  245.      */
  246.     qsort( &ctab[1] , count , sizeof (struct ct) , casecmp );
  247.     /*
  248.      *  check for duplicates
  249.      */
  250.     dupcases = FALSE;
  251.     for ( ctp = &ctab[1] ; ctp < &ctab[ count ] ; ctp++ ) {
  252.     if ( ctp[0].cconst == ctp[1].cconst ) {
  253.         error("Multiply defined label in case, lines %d and %d" ,
  254.             (char *) ctp[0].cline , (char *) ctp[1].cline );
  255.         dupcases = TRUE;
  256.     }
  257.     }
  258.     if ( dupcases ) {
  259.     return;
  260.     }
  261.     /*
  262.      *  choose a switch algorithm and implement it:
  263.      *    direct switch    >= 1/3 full and >= 4 cases.
  264.      *    binary switch    not direct switch and > 8 cases.
  265.      *    ifthenelse    not direct or binary switch.
  266.      */
  267.     (void) putlab( swlabel );
  268.     if ( ctab[ count ].cconst - ctab[1].cconst < 3 * count && count >= 4 ) {
  269.     directsw( ctab , count );
  270.     } else if ( count > 8 ) {
  271.     binarysw( ctab , count );
  272.     } else {
  273.     itesw( ctab , count );
  274.     }
  275.     (void) putlab( endlabel );
  276.     if ( goc != gocnt ) {
  277.         putcnt();
  278.     }
  279. }
  280.  
  281.     /*
  282.      *    direct switch
  283.      */
  284. directsw( ctab , count )
  285.     struct ct    *ctab;
  286.     int        count;
  287. {
  288.     int        fromlabel = (int) getlab();
  289.     long    i;
  290.     long    j;
  291.  
  292. #   ifdef vax
  293.     if (opt('J')) {
  294.         /*
  295.          *    We have a table of absolute addresses.
  296.          *
  297.          *    subl2    to make r0 a 0-origin byte offset.
  298.          *    cmpl    check against upper limit.
  299.          *    jlssu    error if out of bounds.
  300.          *    ashl    to make r0 a 0-origin long offset,
  301.          *    jmp    and indirect through it.
  302.          */
  303.         putprintf("    subl2    $%d,%s", 0, (int) ctab[1].cconst, (int) FORCENAME);
  304.         putprintf("    cmpl    $%d,%s", 0,
  305.             (int) (ctab[count].cconst - ctab[1].cconst),
  306.             (int) FORCENAME);
  307.         putprintf("    jlssu    %s%d", 0, (int) LABELPREFIX, ctab[0].clabel);
  308.         putprintf("    ashl    $2,%s,%s", 0, (int) FORCENAME, (int) FORCENAME);
  309.         putprintf("    jmp    *%s%d(%s)", 0,
  310.             (int) LABELPREFIX, fromlabel, (int) FORCENAME);
  311.     } else {
  312.         /*
  313.          *    We can use the VAX casel instruction with a table
  314.          *    of short relative offsets.
  315.          */
  316.         putprintf("    casel    %s,$%d,$%d" , 0 , (int) FORCENAME ,
  317.             (int) ctab[1].cconst ,
  318.             (int) (ctab[ count ].cconst - ctab[1].cconst ));
  319.     }
  320. #   endif vax
  321.  
  322. #   ifdef tahoe
  323.     if (opt('J')) {
  324.         /*
  325.          *    We have a table of absolute addresses.
  326.          *
  327.          *    subl2    to make r0 a 0-origin byte offset.
  328.          *    cmpl    check against upper limit.
  329.          *    jlssu    error if out of bounds.
  330.          *    shal    to make r0 a 0-origin long offset,
  331.          *    jmp    and indirect through it.
  332.          */
  333.         putprintf("    subl2    $%d,%s", 0, (int) ctab[1].cconst, (int) FORCENAME);
  334.         putprintf("    cmpl    $%d,%s", 0,
  335.             (int) (ctab[count].cconst - ctab[1].cconst),
  336.             (int) FORCENAME);
  337.         putprintf("    jlssu    %s%d", 0, (int) LABELPREFIX, ctab[0].clabel);
  338.         putprintf("    shal    $2,%s,%s", 0, (int) FORCENAME, (int) FORCENAME);
  339.         putprintf("    jmp    *%s%d(%s)", 0,
  340.             (int) LABELPREFIX, fromlabel, (int) FORCENAME);
  341.     } else {
  342.         /*
  343.          *    We can use the TAHOE casel instruction with a table
  344.          *    of short relative offsets.
  345.          */
  346.         putprintf("    casel    %s,$%d,$%d" , 0 , (int) FORCENAME ,
  347.             (int) ctab[1].cconst ,
  348.             (int) (ctab[ count ].cconst - ctab[1].cconst ));
  349.         putprintf("    .align 1", 0);
  350.     }
  351. #   endif tahoe
  352.  
  353. #   ifdef mc68000
  354.     /*
  355.      *    subl    to make d0 a 0-origin byte offset.
  356.      *    cmpl    check against upper limit.
  357.      *    bhi    error if out of bounds.
  358.      */
  359.     putprintf("    subl    #%d,%s", 0, ctab[1].cconst, FORCENAME);
  360.     putprintf("    cmpl    #%d,%s", 0,
  361.         ctab[count].cconst - ctab[1].cconst, FORCENAME);
  362.     putprintf("    bhi    %s%d", 0, LABELPREFIX, ctab[0].clabel);
  363.     if (opt('J')) {
  364.         /*
  365.          *    We have a table of absolute addresses.
  366.          *
  367.          *    asll    to make d0 a 0-origin long offset.
  368.          *    movl    pick up a jump-table entry
  369.          *    jmp    and indirect through it.
  370.          */
  371.         putprintf("    asll    #2,%s", 0, FORCENAME, FORCENAME);
  372.         putprintf("    movl    pc@(4,%s:l),%s", 0, FORCENAME, ADDRTEMP);
  373.         putprintf("    jmp    %s@", 0, ADDRTEMP);
  374.     } else {
  375.         /*
  376.          *    We have a table of relative addresses.
  377.          *
  378.          *    addw    to make d0 a 0-origin word offset.
  379.          *    movw    pick up a jump-table entry
  380.          *    jmp    and indirect through it.
  381.          */
  382.         putprintf("    addw    %s,%s", 0, FORCENAME, FORCENAME);
  383.         putprintf("    movw    pc@(6,%s:w),%s", 0, FORCENAME, FORCENAME);
  384.         putprintf("    jmp    pc@(2,%s:w)", 0, FORCENAME);
  385.     }
  386. #   endif mc68000
  387.     (void) putlab( (char *) fromlabel );
  388.     i = 1;
  389.     j = ctab[1].cconst;
  390.     while ( i <= count ) {
  391.     if ( j == ctab[ i ].cconst ) {
  392.         if (opt('J')) {
  393.         putprintf( "    .long    " , 1 );
  394.         putprintf( PREFIXFORMAT , 0 , (int) LABELPREFIX , ctab[ i ].clabel );
  395.         } else {
  396.         putprintf( "    .word    " , 1 );
  397.         putprintf( PREFIXFORMAT , 1 , (int) LABELPREFIX , ctab[ i ].clabel );
  398.         putprintf( "-" , 1 );
  399.         putprintf( PREFIXFORMAT , 0 , (int) LABELPREFIX , fromlabel );
  400.         }
  401.         i++;
  402.     } else {
  403.         if (opt('J')) {
  404.         putprintf( "    .long    " , 1 );
  405.         putprintf( PREFIXFORMAT , 0 , (int) LABELPREFIX , ctab[ 0 ].clabel );
  406.         } else {
  407.         putprintf( "    .word    " , 1 );
  408.         putprintf( PREFIXFORMAT , 1 , (int) LABELPREFIX , ctab[ 0 ].clabel );
  409.         putprintf( "-" , 1 );
  410.         putprintf( PREFIXFORMAT , 0 , (int) LABELPREFIX , fromlabel );
  411.         }
  412.     }
  413.     j++;
  414.     }
  415. #   if defined(vax) || defined(tahoe)
  416.         /*
  417.          *    execution continues here if value not in range of case.
  418.          */
  419.     if (!opt('J'))
  420.         putjbr( (long) ctab[0].clabel );
  421. #   endif vax || tahoe
  422. }
  423.  
  424.     /*
  425.      *    binary switch
  426.      *    special case out default label and start recursion.
  427.      */
  428. binarysw( ctab , count )
  429.     struct ct    *ctab;
  430.     int        count;
  431. {
  432.     
  433.     bsrecur( ctab[0].clabel , &ctab[0] , count );
  434. }
  435.  
  436.     /*
  437.      *    recursive log( count ) search.
  438.      */
  439. bsrecur( deflabel , ctab , count )
  440.     int        deflabel;
  441.     struct ct    *ctab;
  442.     int        count;
  443. {
  444.  
  445.     if ( count <= 0 ) {
  446.     putjbr((long) deflabel);
  447.     return;
  448.     } else if ( count == 1 ) {
  449. #    if defined(vax) || defined(tahoe)
  450.         putprintf("    cmpl    %s,$%d", 0, (int) FORCENAME, (int) ctab[1].cconst);
  451.         putprintf("    jeql    %s%d", 0, (int) LABELPREFIX, ctab[1].clabel);
  452.         putjbr((long) deflabel);
  453. #    endif vax || tahoe
  454. #    ifdef mc68000
  455.         putprintf("    cmpl    #%d,%s", 0, ctab[1].cconst, (int) FORCENAME);
  456.         putprintf("    jeq    L%d", 0, (int) LABELPREFIX, ctab[1].clabel);
  457.         putjbr((long) deflabel);
  458. #    endif mc68000
  459.     return;
  460.     } else {
  461.     int    half = ( count + 1 ) / 2;
  462.     int    gtrlabel = (int) getlab();
  463.  
  464. #    if defined(vax) || defined(tahoe)
  465.         putprintf("    cmpl    %s,$%d", 0, (int) FORCENAME, (int) ctab[half].cconst);
  466.         putprintf("    jgtr    %s%d", 0, (int) LABELPREFIX, gtrlabel);
  467.         putprintf("    jeql    %s%d", 0, (int) LABELPREFIX, ctab[half].clabel);
  468. #    endif vax || tahoe
  469. #    ifdef mc68000
  470.         putprintf("    cmpl    #%d,%s", 0, (int) ctab[half].cconst, (int) FORCENAME);
  471.         putprintf("    jgt    %s%d", 0, (int) LABELPREFIX, gtrlabel);
  472.         putprintf("    jeq    %s%d", 0, (int) LABELPREFIX, ctab[half].clabel);
  473. #    endif mc68000
  474.     bsrecur( deflabel , &ctab[0] , half - 1 );
  475.     (void) putlab((char *) gtrlabel);
  476.     bsrecur( deflabel , &ctab[ half ] , count - half );
  477.     return;
  478.     }
  479. }
  480.  
  481. itesw( ctab , count )
  482.     struct ct    *ctab;
  483.     int        count;
  484. {
  485.     int    i;
  486.  
  487.     for ( i = 1 ; i <= count ; i++ ) {
  488. #    if defined(vax) || defined(tahoe)
  489.         putprintf("    cmpl    %s,$%d", 0, (int) FORCENAME, (int) ctab[i].cconst);
  490.         putprintf("    jeql    %s%d", 0, (int) LABELPREFIX, ctab[i].clabel);
  491. #    endif vax || tahoe
  492. #    ifdef mc68000
  493.         putprintf("    cmpl    #%d,%s", 0, (int) ctab[i].cconst, (int) FORCENAME);
  494.         putprintf("    jeq    %s%d", 0, (int) LABELPREFIX, ctab[i].clabel);
  495. #    endif mc68000
  496.     }
  497.     putjbr((long) ctab[0].clabel);
  498.     return;
  499. }
  500. int
  501. casecmp( this , that )
  502.     struct ct     *this;
  503.     struct ct     *that;
  504. {
  505.     if ( this -> cconst < that -> cconst ) {
  506.     return -1;
  507.     } else if ( this -> cconst > that -> cconst ) {
  508.     return 1;
  509.     } else {
  510.     return 0;
  511.     }
  512. }
  513. #endif PC
  514.