genfast.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 585 行 · 第 1/2 页

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
*               DESCRIBE IT HERE!
*
****************************************************************************/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
#include "yacc.h"
#include "alloc.h"

enum {
    ACTION_REDUCE       = 0x8000,
    ACTION_UNIT         = 0x4000,
    ACTION_NULL         = 0
};

#define static

typedef unsigned short  action_t;

static unsigned         maxTerminal;
static unsigned         maxNonTerminal;

typedef struct {
    unsigned            num_entries;
    unsigned            min;
    unsigned            max;
    unsigned            index;
    action_t            *action_vector;
} av_info;

typedef struct compressed_action {
    action_t            action;
    unsigned short      index;
} compressed_action;

static void assignAllTokenValues( void )
{
    unsigned i;
    unsigned ntoken;

    ntoken = MaxTerminalTokenValue();
    ++ntoken;
    maxTerminal = ntoken;
    for( i = nterm; i < nsym; ++i ) {
        symtab[i]->token = ntoken++;
    }
    maxNonTerminal = ntoken;
}

static unsigned insertIntoBitVector( byte **bv, unsigned *bs, byte *v, unsigned size )
{
    int i;
    int s;
    int ls;
    char *p;

    if( *bv == NULL ) {
        *bs = size;
        *bv = MALLOC( size, byte );
        memcpy( *bv, v, size );
        return( 0 );
    }
    p = *bv;
    ls = *bs;
    s = ( ls - size ) + 1;
    for( i = 0; i < s; ++i ) {
        if( memcmp( &p[i], v, size ) == 0 ) {
            // bitvector was found inside large vector
            return( i );
        }
    }
    for( i = size; i > 0; --i ) {
        if( memcmp( &p[ls-i], v, i ) == 0 ) {
            // bitvector has some common bits with the end of the large vector
            *bs += size - i;
            p = REALLOC( p, *bs, byte );
            *bv = p;
            memcpy( &p[ls], &v[i], size - i );
            return( ls - i );
        }
    }
    // bitvector has no common bits with large vector
    *bs += size;
    p = REALLOC( p, *bs, byte );
    *bv = p;
    memcpy( &p[ls], v, size );
    return( ls );
}

static int actcmp( action_t *a1, compressed_action * ca, unsigned num_comp,
                                unsigned size )
{
    action_t v1,v2;
    unsigned i;

    for( i = 0; i < num_comp; ++i, ++ ca ) {
        if( ca->index >= size ) break;
        v2 = ca->action;
        // NB Know v2 != ACTION_NULL
        v1 = a1[ca->index];
        if( v1 == ACTION_NULL ) {
            continue;
        }
        if( v1 != v2 ) {
            return( ca->index+1 );
        }
    }
    return( 0 );
}

static void actcpy( action_t *a1, compressed_action * ca, unsigned num_comp )
{
    int i;

    for( i = 0; i < num_comp; ++i, ++ ca ) {
        a1[ca->index] = ca->action;
    }
}

static action_t * actextend( action_t * a, unsigned * psize, unsigned incr )
{
    unsigned    i;

    i = *psize;
    *psize += incr;
    if( *psize == 0 ) {
        a = MALLOC( incr, action_t );
    } else {
        a = REALLOC( a, *psize, action_t );
    }
    while( i < *psize ) {
        a[i++] = ACTION_NULL;
    }
    return( a );
}

static unsigned actcompress( compressed_action * ca, action_t * a, unsigned size )
{
    unsigned    i;
    unsigned    num_actions;

    num_actions = 0;
    for( i = 0; i < size; ++i ) {
        if( a[i] != ACTION_NULL ) {
            ca[num_actions].action = a[i];
            ca[num_actions].index = i;
            ++ num_actions;
        }
    }
    return( num_actions );
}

static unsigned insertIntoActionVector( action_t **bv, unsigned *bs,
                                compressed_action * ca, unsigned num_actions,
                                unsigned size )
{
    int i;
    int s;
    int ls;
    action_t c;
    action_t *p;

    if( num_actions == 0 ) {
        // no action items!
        return( 0 );
    }
    if( *bs == 0 ) {
        *bv = actextend( *bv, bs, size );
        actcpy( *bv, ca, num_actions );
        return( 0 );
    }
    p = *bv;
    ls = *bs;
    s = ( ls - size ) + 1;
    for( i = 0; i < s; ++i ) {
        // try a quick check with the last element that failed (may fail again!)
        c = p[i+ca[0].index];
        // we know v[bi-1] != ACTION_NULL
        if( c != ACTION_NULL && c != ca[0].action ) {
            continue;
        }
        if( actcmp( &p[i], ca, num_actions, size ) == 0 ) {
            // action vector was found inside large vector
            actcpy( &p[i], ca, num_actions );
            return( i );
        }
    }
    for( i = size; i > 0; --i ) {
        if( actcmp( &p[ls-i], ca, num_actions, i ) == 0 ) {
            // action vector has some common actions with the end of the large vector
            p = actextend( p, bs, size - i );
            *bv = p;
            actcpy( &p[ls-i], ca, num_actions );
            return( ls - i );
        }
    }
    // action vector has no common actions with large vector
    p = actextend( p, bs, size );
    *bv = p;
    actcpy( &p[ls], ca, num_actions );
    return( ls );
}

static action_t reduceaction( a_state *state, a_reduce_action *raction )
{
    action_t action;
    a_pro *pro;

    action = ACTION_REDUCE;
    pro = raction->pro;
    if( pro->unit && ! IsDontOptimize( *state ) ) {
        action |= ACTION_UNIT;
    }
    action |= pro->pidx;
    return( action );
}

static int cmp_action( const void *v1, const void *v2 )
{
    av_info **p1 = (av_info **) v1;
    av_info **p2 = (av_info **) v2;
    av_info *s1 = *p1;
    av_info *s2 = *p2;
    unsigned n1, n2;
    unsigned ne1, ne2;
    unsigned mx1, mx2;
    unsigned mn1, mn2;

    ne1 = s1->num_entries;
    ne2 = s2->num_entries;
    if( ne1 == 0 ) {
        if( ne2 == 0 ) {
            return( 0 );
        }
        return( 1 );
    }
    if( ne2 == 0 ) {
        return( -1 );
    }
    mx1 = s1->max;
    mx2 = s2->max;
    mn1 = s1->min;
    mn2 = s2->min;
    n1 = ( mx1 - mn1 ) + 1;
    n2 = ( mx2 - mn2 ) + 1;
    if( n1 < n2 ) {
        return( 1 );
    }
    if( n1 > n2 ) {
        return( -1 );
    }
    if( ne1 < ne2 ) {
        return( -1 );
    }
    if( ne1 > ne2 ) {
        return( 1 );
    }
    if( mx1 < mx2 ) {
        return( -1 );
    }
    if( mx1 > mx2 ) {
        return( 1 );