timetab.c

一个非常好的检索工具

/* $Id: timetab.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
/*
 This software is subject to the terms of the IBM Jikes Compiler
 License Agreement available at the following URL:
 http://www.ibm.com/research/jikes.
 Copyright (C) 1983, 1999, International Business Machines Corporation
 and others.  All Rights Reserved.
 You must accept the terms of that agreement to use this software.
*/
static char hostfile[] = __FILE__;

#include <string.h>
#include "common.h"
#include "header.h"

static int   default_saves = 0;
static short default_rule;

static BOOLEAN *is_terminal;

/*********************************************************************/
/*                            REMAP_SYMBOLS:                         */
/*********************************************************************/
/* We now remap the symbols in the unified Table based on frequency. */
/* We also remap the states based on frequency.                      */
/*********************************************************************/
static void remap_symbols(void)
{
    struct goto_header_type   go_to;
    struct shift_header_type  sh;
    struct reduce_header_type red;

    short *frequency_symbol,
          *frequency_count,
          *row_size;

    int symbol,
        state_no,
        i,
        j,
        k;

    ordered_state = Allocate_short_array(max_la_state + 1);
    symbol_map = Allocate_short_array(num_symbols + 1);
    is_terminal = Allocate_boolean_array(num_symbols + 1);
    frequency_symbol = Allocate_short_array(num_symbols + 1);
    frequency_count = Allocate_short_array(num_symbols + 1);
    row_size = Allocate_short_array(max_la_state + 1);

    fprintf(syslis, "\n");

/*********************************************************************/
/*     The variable FREQUENCY_SYMBOL is used to hold the symbols     */
/* in the grammar,  and the variable FREQUENCY_COUNT is used         */
/* correspondingly to hold the number of actions defined on each     */
/* symbol.                                                           */
/* ORDERED_STATE and ROW_SIZE are used in a similar fashion for      */
/* states.                                                           */
/*********************************************************************/
    for (i = 1; i <= num_symbols; i++)
    {
        frequency_symbol[i] = i;
        frequency_count[i] = 0;
    }
    for ALL_STATES(state_no)
    {
        ordered_state[state_no] = state_no;
        row_size[state_no] = 0;
        sh = shift[statset[state_no].shift_number];
        for (i = 1; i <= sh.size; i++)
        {
            row_size[state_no]++;
            symbol = SHIFT_SYMBOL(sh, i);
            frequency_count[symbol]++;
        }

        go_to =  statset[state_no].go_to;
        for (i = 1; i <= go_to.size; i++)
        {
            row_size[state_no]++;
            symbol = GOTO_SYMBOL(go_to, i);
            frequency_count[symbol]++;
        }

        red =  reduce[state_no];
        default_rule = REDUCE_RULE_NO(red, 0);
        for (i = 1; i <= red.size; i++)
        {
            if (REDUCE_RULE_NO(red, i) != default_rule)
            {
                row_size[state_no]++;
                symbol = REDUCE_SYMBOL(red, i);
                frequency_count[symbol]++;
            }
            else
                default_saves++;
        }
    }
    sprintf(msg_line,
            "Number of Reductions saved by default: %d", default_saves);
    PRNT(msg_line);

    for ALL_LA_STATES(state_no)
    {
        ordered_state[state_no] = state_no;
        row_size[state_no] = 0;
        sh = shift[lastats[state_no].shift_number];
        for (i = 1; i <= sh.size; i++)
        {
            row_size[state_no]++;
            symbol = SHIFT_SYMBOL(sh, i);
            frequency_count[symbol]++;
        }
        red =  lastats[state_no].reduce;
        default_rule = REDUCE_RULE_NO(red, 0);
        for (i = 1; i <= red.size; i++)
        {
            if (REDUCE_RULE_NO(red, i) != default_rule)
            {
                row_size[state_no]++;
                symbol = REDUCE_SYMBOL(red, i);
                frequency_count[symbol]++;
            }
            else
                default_saves++;
        }
    }

 /*********************************************************************/
 /*     The non-terminals are sorted in descending order based on the */
 /* number of actions defined on them.                                */
 /*     The terminals are sorted in descending order based on the     */
 /* number of actions defined on them.                                */
 /*********************************************************************/
    sortdes(frequency_symbol, frequency_count,
            1, num_terminals, max_la_state);

    sortdes(frequency_symbol, frequency_count,
            num_terminals + 1, num_symbols, max_la_state);

    for (last_symbol = num_symbols;
         last_symbol > num_terminals; last_symbol--)
         if (frequency_count[last_symbol] != 0)
             break;

/*********************************************************************/
/* We now merge the two sorted arrays of symbols giving precedence to*/
/* the terminals.  Note that we can guarantee that the terminal array*/
/* will be depleted first since it has precedence, and we know that  */
/* there exists at least one non-terminal: the accept non-terminal,  */
/* on which no action is defined.                                    */
/* As we merge the symbols, we keep track of which ones are terminals*/
/* and which ones are non-terminals.  We also keep track of the new  */
/* mapping for the symbols in SYMBOL_MAP.                            */
/*********************************************************************/
    i = 1;
    j = num_terminals + 1;
    k = 0;
    while (i <= num_terminals)
    {
        k++;
        if (frequency_count[i] >= frequency_count[j])
        {
            symbol = frequency_symbol[i];
            is_terminal[k] = TRUE;
            i++;
        }
        else
        {
            symbol = frequency_symbol[j];
            is_terminal[k] = FALSE;
            j++;
        }
        symbol_map[symbol] = k;
    }
    symbol_map[DEFAULT_SYMBOL] = DEFAULT_SYMBOL;

/*********************************************************************/
/* Process the remaining non-terminal and useless terminal symbols.  */
/*********************************************************************/
    for (; j <= num_symbols; j++)
    {
        k++;
        symbol = frequency_symbol[j];
        is_terminal[k] = FALSE;
        symbol_map[symbol] = k;
    }

    eoft_image = symbol_map[eoft_image];
    if (error_maps_bit)
    {
        error_image = symbol_map[error_image];
        eolt_image = symbol_map[eolt_image];
    }

/*********************************************************************/
/*    All symbol entries in the state automaton are updated based on */
/* the new mapping of the symbols.                                   */
/* The states are sorted in descending order based on the number of  */
/* actions defined on them.                                          */
/*********************************************************************/
    for ALL_STATES(state_no)
    {
        go_to =  statset[state_no].go_to;
        for (i = 1; i <= go_to.size; i++)    /* Remap Goto map */
            GOTO_SYMBOL(go_to, i) = symbol_map[GOTO_SYMBOL(go_to, i)];
        red =  reduce[state_no];
        for (i = 1; i <= red.size; i++)
            REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
    }

    for ALL_LA_STATES(state_no)
    {
        red =  lastats[state_no].reduce;
        for (i = 1; i <= red.size; i++)
            REDUCE_SYMBOL(red, i) = symbol_map[REDUCE_SYMBOL(red, i)];
    }

    for (i = 1; i <= num_shift_maps; i++)
    {
        sh = shift[i];
        for (j = 1; j <= sh.size; j++)
            SHIFT_SYMBOL(sh, j) = symbol_map[SHIFT_SYMBOL(sh, j)];
    }

    sortdes(ordered_state, row_size, 1, max_la_state, num_symbols);

    ffree(frequency_symbol);
    ffree(frequency_count);
    ffree(row_size);

    return;
}


/*********************************************************************/
/*                          OVERLAP_TABLES:                          */
/*********************************************************************/
/* We now overlap the State automaton table, or more precisely,  we  */
/* compute the starting position in a vector where each of its rows  */
/* may be placed without clobbering elements in another row.         */
/* The starting positions are stored in the vector STATE_INDEX.      */
/*********************************************************************/
static void overlap_tables(void)
{
    struct goto_header_type  go_to;
    struct shift_header_type  sh;
    struct reduce_header_type red;

    short *symbol_list;

    int symbol,
        state_no,
        root_symbol,
        max_indx,
        indx,
        percentage,
        k_bytes,
        k,
        i;

    long num_bytes;

    state_index = Allocate_int_array(max_la_state + 1);

    symbol_list = Allocate_short_array(num_symbols + 1);

    num_entries -= default_saves;
    increment_size = MAX((num_entries*increment/100), (num_symbols + 1));
    table_size = MIN((num_entries + increment_size), MAX_TABLE_SIZE);

/*********************************************************************/
/* Allocate space for table, and initialize the AVAIL_POOL list.     */
/* The variable FIRST_INDEX keeps track of the first element in the  */
/* doubly-linked list, and LAST_ELEMENT keeps track of the last      */
/* element in the list.                                              */
/* The variable MAX_INDX is used to keep track of the maximum        */
/* starting position for a row that has been used.                   */
/*********************************************************************/
    next = Allocate_int_array(table_size + 1);
    previous = Allocate_int_array(table_size + 1);

    first_index = 1;
    next[first_index] = first_index + 1; /* Should be constant-folded */
    previous[first_index] = NIL;
    for (indx = 2; indx < (int) table_size; indx++)
    {
        next[indx] = indx + 1;
        previous[indx] = indx - 1;
    }
    last_index = table_size;
    previous[last_index] = last_index - 1;
    next[last_index] = NIL;

    max_indx = first_index;

/*********************************************************************/
/* We now iterate over all the states in their new sorted order as   */
/* indicated by the variable STATE_NO, and deternime an "overlap"    */
/* position for them.                                                */
/*********************************************************************/
    for (k = 1; k <= (int) max_la_state; k++)
    {
        state_no = ordered_state[k];

/*********************************************************************/
/* First, we iterate over all actions defined in STATE_NO, and       */
/* create a set with all the symbols involved.                       */
/*********************************************************************/
        root_symbol = NIL;
        if (state_no > (int) num_states)
        {
            sh = shift[lastats[state_no].shift_number];
            red = lastats[state_no].reduce;
        }
        else
        {
            go_to = statset[state_no].go_to;
            for (i = 1; i <= go_to.size; i++)
            {
                symbol = GOTO_SYMBOL(go_to, i);
                symbol_list[symbol] = root_symbol;
                root_symbol = symbol;
            }
            sh = shift[statset[state_no].shift_number];
            red = reduce[state_no];
        }

        for (i = 1; i <= sh.size; i++)
        {
            symbol = SHIFT_SYMBOL(sh, i);
            symbol_list[symbol] = root_symbol;
            root_symbol = symbol;
        }
        symbol_list[0] = root_symbol;