Patch for automaton based pipeline hazard recognizer (part #2).
Vladimir Makarov
vmakarov@toke.toronto.redhat.com
Wed Jan 31 12:16:00 GMT 2001
This is the 1st part of file genautomata.c:
--------------------File genautomata.c-------------------------------
/* Routines to generate pipeline hazard recognition automata.
Copyright (C) 2000 Free Software Foundation, Inc.
Written by Vladimir Makarov <vmakarov@redhat.com>
This file is part of GNU CC.
GNU CC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version.
GNU CC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
/*====All the folowing code is pipeline hazard description translator.=======*/
#ifdef HAVE_ASSERT_H
#include <assert.h>
#else
#ifndef assert
#define assert(code) do { if ((code) == 0) abort ();} while (0)
#endif
#endif
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashtab.h"
#include "varray.h"
#ifdef HAVE_LIMITS_H
#include <limits.h>
#else
#ifndef CHAR_BIT
#define CHAR_BIT 8
#endif
#endif
/* Positions in machine description file. Now they are not used. */
typedef int pos_t;
typedef unsigned HOST_WIDE_INT set_el_t;
typedef set_el_t *reserv_sets_t;
/* The following structure represents variable length array (vla) of
pointers and HOST WIDE INTs. See commentaries for macros working
with vla. */
typedef struct {
size_t length; /* current size of vla. */
varray_type varray; /* container for vla. */
} vla_ptr_t;
typedef vla_ptr_t vla_hwint_t;
/* The following structure describes a ticker. */
struct ticker
{
/* The following member value is time of the ticker creation with
taking into account time when the ticker is off. Active time of
the ticker is current time minus the value. */
int modified_creation_time;
/* The following member value is time (incremented by one) when the
ticker was off. Zero value means that now the ticker is on. */
int incremented_off_time;
};
/* The ticker is represented by the following type. */
typedef struct ticker ticker_t;
/* The following type describes elements of output vectors. */
typedef HOST_WIDE_INT vect_el_t;
/* Forward declaration of structures of internal representation of
pipeline description based on NDFA. */
struct unit_decl;
struct bypass_decl;
struct result_decl;
struct automaton_decl;
struct unit_rel_decl;
struct reserv_decl;
struct insn_reserv_decl;
struct decl;
struct unit_regexp;
struct result_regexp;
struct reserv_regexp;
struct nothing_regexp;
struct sequence_regexp;
struct repeat_regexp;
struct allof_regexp;
struct oneof_regexp;
struct regexp;
struct description;
struct unit_set_el;
struct state;
struct alt_state;
struct arc;
struct ainsn;
struct automaton;
struct state_ainsn_table;
/* Prototypes of functions gen_cpu_unit, gen_query_cpu_unit,
gen_bypass, gen_excl_set, gen_presence_set, gen_absence_set,
gen_automaton, gen_automata_option, gen_reserv, gen_insn_reserv,
initiate_automaton_gen, expand_automata, write_automata are
described on the file top because the functions are called from
function `main'. */
static void *create_node PARAMS ((size_t));
static void *copy_node PARAMS ((void *, size_t));
static char *check_name PARAMS ((char *, pos_t));
static char *next_sep_el PARAMS ((char **, int, int));
static int n_sep_els PARAMS ((char *, int, int));
static char **get_str_vect PARAMS ((char *, int *, int, int));
static struct regexp *gen_regexp_el PARAMS ((char *));
static struct regexp *gen_regexp_repeat PARAMS ((char *));
static struct regexp *gen_regexp_allof PARAMS ((char *));
static struct regexp *gen_regexp_oneof PARAMS ((char *));
static struct regexp *gen_regexp_sequence PARAMS ((char *));
static struct regexp *gen_regexp PARAMS ((char *));
static unsigned string_hash PARAMS ((const char *));
static unsigned automaton_decl_hash PARAMS ((const void *));
static int automaton_decl_eq_p PARAMS ((const void *,
const void *));
static struct decl *insert_automaton_decl PARAMS ((struct decl *));
static struct decl *find_automaton_decl PARAMS ((char *));
static void initiate_automaton_decl_table PARAMS ((void));
static void finish_automaton_decl_table PARAMS ((void));
static unsigned insn_decl_hash PARAMS ((const void *));
static int insn_decl_eq_p PARAMS ((const void *,
const void *));
static struct decl *insert_insn_decl PARAMS ((struct decl *));
static struct decl *find_insn_decl PARAMS ((char *));
static void initiate_insn_decl_table PARAMS ((void));
static void finish_insn_decl_table PARAMS ((void));
static unsigned decl_hash PARAMS ((const void *));
static int decl_eq_p PARAMS ((const void *,
const void *));
static struct decl *insert_decl PARAMS ((struct decl *));
static struct decl *find_decl PARAMS ((char *));
static void initiate_decl_table PARAMS ((void));
static void finish_decl_table PARAMS ((void));
static struct unit_set_el *process_excls PARAMS ((char **, int, pos_t));
static void add_excls PARAMS ((struct unit_set_el *,
struct unit_set_el *,
pos_t));
static struct unit_set_el *process_presence_absence
PARAMS ((char **, int, pos_t, int));
static void add_presence_absence PARAMS ((struct unit_set_el *,
struct unit_set_el *,
pos_t, int));
static void process_decls PARAMS ((void));
static struct bypass_decl *find_bypass PARAMS ((struct bypass_decl *,
struct insn_reserv_decl *));
static void check_automaton_usage PARAMS ((void));
static struct regexp *process_regexp PARAMS ((struct regexp *));
static void process_regexp_decls PARAMS ((void));
static void check_usage PARAMS ((void));
static int loop_in_regexp PARAMS ((struct regexp *,
struct decl *));
static void check_loops_in_regexps PARAMS ((void));
static int process_regexp_cycles PARAMS ((struct regexp *, int));
static void evaluate_max_reserv_cycles PARAMS ((void));
static void check_all_description PARAMS ((void));
static ticker_t create_ticker PARAMS ((void));
static void ticker_off PARAMS ((ticker_t *));
static void ticker_on PARAMS ((ticker_t *));
static int active_time PARAMS ((ticker_t));
static void print_active_time PARAMS ((FILE *, ticker_t));
static void add_advance_cycle_insn_decl PARAMS ((void));
static struct alt_state *get_free_alt_state PARAMS ((void));
static void free_alt_state PARAMS ((struct alt_state *));
static void free_alt_states PARAMS ((struct alt_state *));
static int alt_state_cmp PARAMS ((const void *alt_state_ptr_1,
const void *alt_state_ptr_2));
static struct alt_state *uniq_sort_alt_states PARAMS ((struct alt_state *));
static int alt_states_eq PARAMS ((struct alt_state *,
struct alt_state *));
static void initiate_alt_states PARAMS ((void));
static void finish_alt_states PARAMS ((void));
static reserv_sets_t alloc_empty_reserv_sets PARAMS ((void));
static unsigned reserv_sets_hash_value PARAMS ((reserv_sets_t));
static int reserv_sets_cmp PARAMS ((reserv_sets_t,
reserv_sets_t));
static int reserv_sets_eq PARAMS ((reserv_sets_t,
reserv_sets_t));
static void set_unit_reserv PARAMS ((reserv_sets_t, int, int));
static int test_unit_reserv PARAMS ((reserv_sets_t, int, int));
static int it_is_empty_reserv_sets PARAMS ((reserv_sets_t))
ATTRIBUTE_UNUSED;
static int reserv_sets_are_intersected PARAMS ((reserv_sets_t,
reserv_sets_t));
static void reserv_sets_shift PARAMS ((reserv_sets_t,
reserv_sets_t));
static void reserv_sets_or PARAMS ((reserv_sets_t,
reserv_sets_t,
reserv_sets_t));
static void reserv_sets_and PARAMS ((reserv_sets_t,
reserv_sets_t,
reserv_sets_t))
ATTRIBUTE_UNUSED;
static void output_cycle_reservs PARAMS ((FILE *, reserv_sets_t,
int, int));
static void output_reserv_sets PARAMS ((FILE *, reserv_sets_t));
static struct state *get_free_state PARAMS ((int, struct automaton *));
static void free_state PARAMS ((struct state *));
static unsigned state_hash PARAMS ((const void *));
static int state_eq_p PARAMS ((const void *, const void *));
static struct state *insert_state PARAMS ((struct state *));
static void set_state_reserv PARAMS ((struct state *, int, int));
static int intersected_state_reservs_p PARAMS ((struct state *,
struct state *));
static struct state *states_union PARAMS ((struct state *,
struct state *));
static struct state *state_shift PARAMS ((struct state *));
static void initiate_states PARAMS ((void));
static void finish_states PARAMS ((void));
static void free_arc PARAMS ((struct arc *));
static void remove_arc PARAMS ((struct state *, struct arc *));
static struct arc *find_arc PARAMS ((struct state *, struct state *,
struct ainsn *));
static struct arc *add_arc PARAMS ((struct state *, struct state *,
struct ainsn *, int));
static struct arc *first_out_arc PARAMS ((struct state *));
static struct arc *next_out_arc PARAMS ((struct arc *));
static void initiate_arcs PARAMS ((void));
static void finish_arcs PARAMS ((void));
static void initiate_excl_sets PARAMS ((void));
static reserv_sets_t get_excl_set PARAMS ((reserv_sets_t));
static void initiate_presence_absence_sets PARAMS ((void));
static reserv_sets_t get_presence_absence_set PARAMS ((reserv_sets_t, int));
static struct regexp *copy_insn_regexp PARAMS ((struct regexp *));
static struct regexp *transform_1 PARAMS ((struct regexp *));
static struct regexp *transform_2 PARAMS ((struct regexp *));
static struct regexp *transform_3 PARAMS ((struct regexp *));
static struct regexp *regexp_transform_func
PARAMS ((struct regexp *, struct regexp *(*) (struct regexp *)));
static struct regexp *transform_regexp PARAMS ((struct regexp *));
static void transform_insn_regexps PARAMS ((void));
static int process_seq_for_forming_states PARAMS ((struct regexp *,
struct automaton *, int));
static void finish_forming_alt_state PARAMS ((struct alt_state *,
struct automaton *));
static void process_alts_for_forming_states PARAMS ((struct regexp *,
struct automaton *, int));
static void create_alt_states PARAMS ((struct automaton *));
static void form_ainsn_with_same_reservs PARAMS ((struct automaton *));
static void make_automaton PARAMS ((struct automaton *));
static void form_arcs_marked_by_insn PARAMS ((struct state *));
static void create_composed_state PARAMS ((struct state *, struct arc *,
vla_ptr_t *));
static void NDFA_to_DFA PARAMS ((struct automaton *));
static void pass_state_graph PARAMS ((struct state *,
void (*) (struct state *)));
static void pass_states PARAMS ((struct automaton *,
void (*) (struct state *)));
static void initiate_pass_states PARAMS ((void));
static void add_achieved_state PARAMS ((struct state *));
static int set_out_arc_insns_equiv_num PARAMS ((struct state *, int));
static void clear_arc_insns_equiv_num PARAMS ((struct state *));
static void copy_equiv_class PARAMS ((vla_ptr_t *to,
const vla_ptr_t *from));
static int state_is_differed PARAMS ((struct state *, int, int));
static struct state *init_equiv_class PARAMS ((struct state **states, int));
static void evaluate_equiv_classes PARAMS ((struct automaton *,
vla_ptr_t *));
static void merge_states PARAMS ((struct automaton *,
vla_ptr_t *));
static void set_new_cycle_flags PARAMS ((struct state *));
static void minimize_DFA PARAMS ((struct automaton *));
static void incr_states_and_arcs_nums PARAMS ((struct state *));
static void count_states_and_arcs PARAMS ((struct automaton *, int *,
int *));
static void build_automaton PARAMS ((struct automaton *));
static void set_order_state_num PARAMS ((struct state *));
static void enumerate_states PARAMS ((struct automaton *));
static struct ainsn *insert_ainsn_into_equiv_class PARAMS ((struct ainsn *,
struct ainsn *));
static void delete_ainsn_from_equiv_class PARAMS ((struct ainsn *));
static void process_insn_equiv_class PARAMS ((struct ainsn *,
struct arc **));
static void process_state_for_insn_equiv_partition PARAMS ((struct state *));
static void set_insn_equiv_classes PARAMS ((struct automaton *));
static double estimate_one_automaton_bound PARAMS ((void));
static int compare_max_occ_cycle_nums PARAMS ((const void *,
const void *));
static void units_to_automata_heuristic_distr PARAMS ((void));
static struct ainsn *create_ainsns PARAMS ((void));
static void units_to_automata_distr PARAMS ((void));
static void create_automata PARAMS ((void));
static void form_regexp PARAMS ((struct regexp *));
static const char *regexp_representation PARAMS ((struct regexp *));
static void finish_regexp_representation PARAMS ((void));
static void output_range_type PARAMS ((FILE *, long int, long int));
static void output_vect PARAMS ((vect_el_t *, int));
static void output_chip_member_name PARAMS ((FILE *, struct automaton *));
static void output_temp_chip_member_name PARAMS ((FILE *, struct automaton *));
static void output_translate_vect_name PARAMS ((FILE *, struct automaton *));
static void output_trans_full_vect_name PARAMS ((FILE *, struct automaton *));
static void output_trans_comb_vect_name PARAMS ((FILE *, struct automaton *));
static void output_trans_check_vect_name PARAMS ((FILE *, struct automaton *));
static void output_trans_base_vect_name PARAMS ((FILE *, struct automaton *));
static void output_state_alts_full_vect_name PARAMS ((FILE *,
struct automaton *));
static void output_state_alts_comb_vect_name PARAMS ((FILE *,
struct automaton *));
static void output_state_alts_check_vect_name PARAMS ((FILE *,
struct automaton *));
static void output_state_alts_base_vect_name PARAMS ((FILE *,
struct automaton *));
static void output_min_issue_delay_vect_name PARAMS ((FILE *,
struct automaton *));
static void output_dead_lock_vect_name PARAMS ((FILE *, struct automaton *));
static void output_reserved_units_table_name PARAMS ((FILE *,
struct automaton *));
static void output_state_member_type PARAMS ((FILE *, struct automaton *));
static void output_chip_definitions PARAMS ((void));
static void output_translate_vect PARAMS ((struct automaton *));
static int comb_vect_p PARAMS ((struct state_ainsn_table *));
static struct state_ainsn_table *create_state_ainsn_table
PARAMS ((struct automaton *));
static void output_state_ainsn_table
PARAMS ((struct state_ainsn_table *, char *,
void (*) (FILE *, struct automaton *),
void (*) (FILE *, struct automaton *),
void (*) (FILE *, struct automaton *),
void (*) (FILE *, struct automaton *)));
static void add_vect PARAMS ((struct state_ainsn_table *,
int, vect_el_t *, int));
static int out_state_arcs_num PARAMS ((struct state *));
static int compare_transition_els_num PARAMS ((const void *, const void *));
static void add_vect_el PARAMS ((vla_hwint_t *,
struct ainsn *, int));
static void add_states_vect_el PARAMS ((struct state *));
static void output_trans_table PARAMS ((struct automaton *));
static void output_state_alts_table PARAMS ((struct automaton *));
static void min_issue_delay_pass_states PARAMS ((struct state *,
struct ainsn *));
static int min_issue_delay PARAMS ((struct state *,
struct ainsn *));
static void initiate_min_issue_delay_pass_states PARAMS ((void));
static void output_min_issue_delay_table PARAMS ((struct automaton *));
static void output_dead_lock_vect PARAMS ((struct automaton *));
static void output_reserved_units_table PARAMS ((struct automaton *));
static void output_tables PARAMS ((void));
static void output_max_insn_queue_index_def PARAMS ((void));
static void output_internal_min_issue_delay_func PARAMS ((void));
static void output_internal_trans_func PARAMS ((void));
static void output_internal_insn_code_evaluation PARAMS ((const char *,
const char *, int));
static void output_dfa_insn_code_func PARAMS ((void));
static void output_trans_func PARAMS ((void));
static void output_internal_state_alts_func PARAMS ((void));
static void output_state_alts_func PARAMS ((void));
static void output_min_issue_delay_func PARAMS ((void));
static void output_internal_dead_lock_func PARAMS ((void));
static void output_dead_lock_func PARAMS ((void));
static void output_internal_reset_func PARAMS ((void));
static void output_size_func PARAMS ((void));
static void output_reset_func PARAMS ((void));
static void output_min_insn_conflict_delay_func PARAMS ((void));
static void output_internal_insn_latency_func PARAMS ((void));
static void output_insn_latency_func PARAMS ((void));
static void output_print_reservation_func PARAMS ((void));
static int units_cmp PARAMS ((const void *,
const void *));
static void output_get_cpu_unit_code_func PARAMS ((void));
static void output_cpu_unit_reservation_p PARAMS ((void));
static void output_dfa_start_func PARAMS ((void));
static void output_dfa_finish_func PARAMS ((void));
static void output_regexp PARAMS ((struct regexp *));
static void output_unit_set_el_list PARAMS ((struct unit_set_el *));
static void output_description PARAMS ((void));
static void output_automaton_name PARAMS ((FILE *,
struct automaton *));
static void output_automaton_units PARAMS ((struct automaton *));
static void add_state_reservs PARAMS ((struct state *));
static void output_state_arcs PARAMS ((struct state *));
static int state_reservs_cmp PARAMS ((const void *,
const void *));
static void remove_state_duplicate_reservs PARAMS ((void));
static void output_state PARAMS ((struct state *));
static void output_automaton_descriptions PARAMS ((void));
static void output_statistics PARAMS ((FILE *));
static void output_time_statistics PARAMS ((FILE *));
static void generate PARAMS ((void));
static void make_insn_alts_attr PARAMS ((void));
static void make_internal_dfa_insn_code_attr PARAMS ((void));
static void make_default_insn_latency_attr PARAMS ((void));
static void make_bypass_attr PARAMS ((void));
static const char *file_name_suffix PARAMS ((const char *));
static const char *base_file_name PARAMS ((const char *));
static void check_automata PARAMS ((void));
/* Undefined position. */
static pos_t no_pos = 0;
/* Macros for work with internal representation (IR) storage
manager. */
/* Start work with IR storage manager. */
#define IR_START_ALLOC() obstack_init (&irp)
/* Finish work with the storage manager. */
#define IR_STOP_ALLOC() obstack_free (&irp, NULL)
/* Allocate storage for IR of given size. */
#define IR_ALLOC(ptr, size, ptr_type) \
do \
{ \
obstack_make_room (&irp, size); ptr = (ptr_type) obstack_finish (&irp); \
} \
while (0);
/* Free storage of IR of given size. */
#define IR_FREE(ptr, size)
/* Start new IR object. */
#define IR_TOP_FINISH() ((void) obstack_finish (&irp))
/* Nullify current IR object. */
#define IR_TOP_NULLIFY()\
do {\
int length = obstack_object_size (&irp);\
obstack_blank_fast (&irp, -length);\
} while (0);
/* Shorten current IR object on given number bytes. */
#define IR_TOP_SHORTEN(length) obstack_blank_fast (&irp, -(length))
/* Return start address of current IR object. */
#define IR_TOP_BEGIN() obstack_base (&irp)
/* Return length of current IR object in bytes. */
#define IR_TOP_LENGTH() obstack_object_size (&irp)
/* Expand current IR object. */
#define IR_TOP_EXPAND(length) obstack_blank (&irp, length)
/* Add byte to the end of current IR object. */
#define IR_TOP_ADD_BYTE(b) obstack_1grow (&irp, b)
/* Add string to the end of current IR object. */
#define IR_TOP_ADD_STRING(str) obstack_grow (&irp, str, strlen (str) + 1)
/* Add memory of given length to the end of current IR object. */
#define IR_TOP_ADD_MEMORY(mem, length) obstack_grow (&irp, mem, length)
/* All IR is stored in the following obstack. */
static struct obstack irp;
/* This page contains code for work with variable length array (vla)
of pointers. We could be use only varray. But we add new lay
because we add elements very frequently and this could stress OS
allocator when varray is used only. */
/* Start work with vla. */
#define VLA_PTR_CREATE(vla, allocated_length, name) \
do \
{ \
vla_ptr_t *vla_ptr = &(vla); \
\
VARRAY_GENERIC_PTR_INIT (vla_ptr->varray, allocated_length, name);\
vla_ptr->length = 0; \
} \
while (0)
/* Finish work with the vla. */
#define VLA_PTR_DELETE(vla) VARRAY_FREE ((vla).varray)
/* Return start address of the vla. */
#define VLA_PTR_BEGIN(vla) ((void *) &VARRAY_GENERIC_PTR ((vla).varray, 0))
/* Address of the last element of the vla. Do not use side effects in
the macro argument. */
#define VLA_PTR_LAST(vla) (&VARRAY_GENERIC_PTR ((vla).varray, \
(vla).length - 1))
/* Nullify the vla. */
#define VLA_PTR_NULLIFY(vla) ((vla).length = 0)
/* Shorten the vla on given number bytes. */
#define VLA_PTR_SHORTEN(vla, n) ((vla).length -= (n))
/* Expand the vla on N elements. The values of new elements are
undefined. */
#define VLA_PTR_EXPAND(vla, n) \
do { \
vla_ptr_t *expand_vla_ptr = &(vla); \
size_t new_length = (n) + expand_vla_ptr->length; \
\
if (VARRAY_SIZE (expand_vla_ptr->varray) < new_length) \
VARRAY_GROW (expand_vla_ptr->varray, \
(new_length - expand_vla_ptr->length < 128 \
? expand_vla_ptr->length + 128 : new_length)); \
expand_vla_ptr->length = new_length; \
} while (0)
/* Add element to the end of the vla. */
#define VLA_PTR_ADD(vla, ptr) \
do { \
vla_ptr_t *vla_ptr = &(vla); \
\
VLA_PTR_EXPAND (*vla_ptr, 1); \
VARRAY_GENERIC_PTR (vla_ptr->varray, vla_ptr->length - 1) = (ptr);\
} while (0)
/* Length of the vla in elements. */
#define VLA_PTR_LENGTH(vla) ((vla).length)
/* N-th element of the vla. */
#define VLA_PTR(vla, n) VARRAY_GENERIC_PTR ((vla).varray, n)
/* The following macros are analogous to the previous ones but for
VLAs of HOST WIDE INTs. */
#define VLA_HWINT_CREATE(vla, allocated_length, name) \
do { \
vla_hwint_t *vla_ptr = &(vla); \
\
VARRAY_WIDE_INT_INIT (vla_ptr->varray, allocated_length, name); \
vla_ptr->length = 0; \
} while (0)
#define VLA_HWINT_DELETE(vla) VARRAY_FREE ((vla).varray)
#define VLA_HWINT_BEGIN(vla) (&VARRAY_WIDE_INT ((vla).varray, 0))
/* Do not use side effects in the macro argument. */
#define VLA_HWINT_LAST(vla) (&VARRAY_WIDE_INT ((vla).varray, \
(vla).length - 1))
#define VLA_HWINT_NULLIFY(vla) ((vla).length = 0)
#define VLA_HWINT_SHORTEN(vla, n) ((vla).length -= (n))
#define VLA_HWINT_EXPAND(vla, n) \
do { \
vla_hwint_t *expand_vla_ptr = &(vla); \
size_t new_length = (n) + expand_vla_ptr->length; \
\
if (VARRAY_SIZE (expand_vla_ptr->varray) < new_length) \
VARRAY_GROW (expand_vla_ptr->varray, \
(new_length - expand_vla_ptr->length < 128 \
? expand_vla_ptr->length + 128 : new_length)); \
expand_vla_ptr->length = new_length; \
} while (0)
#define VLA_HWINT_ADD(vla, ptr) \
do { \
vla_hwint_t *vla_ptr = &(vla); \
\
VLA_HWINT_EXPAND (*vla_ptr, 1); \
VARRAY_WIDE_INT (vla_ptr->varray, vla_ptr->length - 1) = (ptr); \
} while (0)
#define VLA_HWINT_LENGTH(vla) ((vla).length)
#define VLA_HWINT(vla, n) VARRAY_WIDE_INT ((vla).varray, n)
/* Standard designators for true and false values. */
#define FALSE 0
#define TRUE 1
/* Options with the following names can be set up in automata_option
construction. */
#define NO_MINIMIZATION_OPTION "-no-minimization"
#define W_OPTION "-w"
#define NDFA_OPTION "-ndfa"
/* The following flags are set up by function
`initiate_automaton_gen'. */
/* Make automata with nondetermenistic reservation by insns (`-ndfa'). */
static int ndfa_flag;
/* Do not make minimization of DFA (`-no-minimization'). */
static int no_minimization_flag;
/* Value of this variable is number of automata being generated. The
actual number of automata may be less this value if there is not
sufficient number of units. This value is defined by argument of
option `-split' or by constructions automaton if the value is zero
(it is default value of the argument). */
static int split_argument;
/* Flag of output time statistics (`-time'). */
static int time_flag;
/* Flag of creation of description file which contains description of
result automaton and statistics information (`-v'). */
static int v_flag;
/* Flag of generating warning instead of error for non-critical errors
(`-w'). */
static int w_flag;
/* Output file for pipeline hazard recognizer (PHR) being generated.
The value is NULL if the file is not defined. */
static FILE *output_file;
/* Description file of PHR. The value is NULL if the file is not
created. */
static FILE *output_description_file;
/* PHR description file name. */
static char *output_description_file_name;
/* Value of the following variable is node representing description
being processed. This is start point of IR. */
static struct description *description;
/* This page contains description of IR structure (nodes). */
enum decl_mode
{
dm_unit,
dm_bypass,
dm_automaton,
dm_excl,
dm_presence,
dm_absence,
dm_reserv,
dm_insn_reserv
};
/* This describes define_cpu_unit and define_query_cpu_unit (see file
rtl.def). */
struct unit_decl
{
char *name;
/* NULL if the automaton name is absent. */
char *automaton_name;
/* If the following value is not zero, the cpu unit reservation is
described in define_query_cpu_unit. */
char query_p;
/* The following fields are defined by checker. */
/* The following field value is TRUE if the unit is used in an
regexp. */
char unit_is_used;
/* The following field value is order number (0, 1, ...) of given
unit. */
int unit_num;
/* The following field value is corresponding declaration of
automaton which was given in description. If the field value is
NULL then automaton in the unit declaration was absent. */
struct automaton_decl *automaton_decl;
/* The following field value is maximal cycle number (1, ...) on
which given unit occurs in insns. Zero value means that given
unit is not used in insns. */
int max_occ_cycle_num;
/* The following list contains units which conflict with given
unit. */
struct unit_set_el *excl_list;
/* The following list contains units which are required to
reservation of given unit. */
struct unit_set_el *presence_list;
/* The following list contains units which should be not present in
reservation for given unit. */
struct unit_set_el *absence_list;
/* The following is used only when `query_p' is TRUE. This is query
number for the unit. */
int query_num;
/* The following fields are defined by automaton generator. */
/* The following field value is number of the automaton to which
given unit belongs. */
int corresponding_automaton_num;
};
/* This describes define_bypass (see file rtl.def). */
struct bypass_decl
{
int latency;
char *out_insn_name;
char *in_insn_name;
char *bypass_guard_name;
/* The following fields are defined by checker. */
/* output and input insns of given bypass. */
struct insn_reserv_decl *out_insn_reserv;
struct insn_reserv_decl *in_insn_reserv;
/* The next bypass for given output insn. */
struct bypass_decl *next;
};
/* This describes define_automaton (see file rtl.def). */
struct automaton_decl
{
char *name;
/* The following fields are defined by automaton generator. */
/* The following field value is TRUE if the automaton is used in an
regexp definition. */
char automaton_is_used;
/* The following fields are defined by checker. */
/* The following field value is the corresponding automaton. This
field is not NULL only if the automaton is present in unit
declarations and the automatic partition on automata is not
used. */
struct automaton *corresponding_automaton;
};
/* This describes unit relations: exclusion_set, presence_set, or
absence_set (see file rtl.def). */
struct unit_rel_decl
{
int names_num;
int first_list_length;
char *names [1];
};
/* This describes define_reservation (see file rtl.def). */
struct reserv_decl
{
char *name;
struct regexp *regexp;
/* The following fields are defined by checker. */
/* The following field value is TRUE if the unit is used in an
regexp. */
char reserv_is_used;
/* The following field is used to check up cycle in expression
definition. */
int loop_pass_num;
};
/* This describes define_insn_reservartion (see file rtl.def). */
struct insn_reserv_decl
{
rtx condexp;
int default_latency;
struct regexp *regexp;
char *name;
/* The following fields are defined by checker. */
/* The following field value is order number (0, 1, ...) of given
insn. */
int insn_num;
/* The following field value is list of bypasses in which given insn
is output insn. */
struct bypass_decl *bypass_list;
/* The following fields are defined by automaton generator. */
/* The following field is the insn regexp transformed that
the regexp has not optional regexp, repetition regexp, and an
reservation name (i.e. reservation identifiers are changed by the
corresponding regexp) and all alternations are the topest level
of the regexp. The value can be NULL only if it is special
insn `cycle advancing'. */
struct regexp *transformed_regexp;
/* The following field value is list of arcs marked given
insn. The field is used in transfromation NDFA -> DFA. */
struct arc *arcs_marked_by_insn;
/* The two following fields are used during minimization of a finite state
automaton. */
/* The field value is number of equivalence class of state into
which arc marked by given insn enters from a state (fixed during
an automaton minimization). */
int equiv_class_num;
/* The field value is state_alts of arc leaving a state (fixed
during an automaton minimization) and marked by given insn
enters. */
int state_alts;
};
/* This contains a declaration mentioned above. */
struct decl
{
/* What node in the union? */
enum decl_mode mode;
pos_t pos;
union
{
struct unit_decl unit;
struct bypass_decl bypass;
struct automaton_decl automaton;
struct unit_rel_decl excl;
struct unit_rel_decl presence;
struct unit_rel_decl absence;
struct reserv_decl reserv;
struct insn_reserv_decl insn_reserv;
} decl;
};
/* The following structures represent parsed reservation strings. */
enum regexp_mode
{
rm_unit,
rm_reserv,
rm_nothing,
rm_sequence,
rm_repeat,
rm_allof,
rm_oneof
};
/* Cpu unit in reservation. */
struct unit_regexp
{
char *name;
struct unit_decl *unit_decl;
};
/* Define_reservation in a reservation. */
struct reserv_regexp
{
char *name;
struct reserv_decl *reserv_decl;
};
/* Absence of reservation (represented by string `nothing'). */
struct nothing_regexp
{
/* This used to be empty but ISO C doesn't allow that. */
char unused;
};
/* Representation of reservations separated by ',' (see file
rtl.def). */
struct sequence_regexp
{
int regexps_num;
struct regexp *regexps [1];
};
/* Representation of construction `repeat' (see file rtl.def). */
struct repeat_regexp
{
int repeat_num;
struct regexp *regexp;
};
/* Representation of reservations separated by '+' (see file
rtl.def). */
struct allof_regexp
{
int regexps_num;
struct regexp *regexps [1];
};
/* Representation of reservations separated by '|' (see file
rtl.def). */
struct oneof_regexp
{
int regexps_num;
struct regexp *regexps [1];
};
/* Representation of a reservation string. */
struct regexp
{
/* What node in the union? */
enum regexp_mode mode;
pos_t pos;
union
{
struct unit_regexp unit;
struct reserv_regexp reserv;
struct nothing_regexp nothing;
struct sequence_regexp sequence;
struct repeat_regexp repeat;
struct allof_regexp allof;
struct oneof_regexp oneof;
} regexp;
};
/* Reperesents description of pipeline hazard description based on
NDFA. */
struct description
{
int decls_num;
/* The following fields are defined by checker. */
/* The following fields values are correspondingly number of all
units, query units, and insns in the description. */
int units_num;
int query_units_num;
int insns_num;
/* The following field value is max length (in cycles) of
reservations of insns. The field value is defined only for
correct programs. */
int max_insn_reserv_cycles;
/* The following fields are defined by automaton generator. */
/* The following field value is the first automaton. */
struct automaton *first_automaton;
/* The following field is created by pipeline hazard parser and
contains all declarations. We allocate additional entry for
special insn "cycle advancing" which is added by the automaton
generator. */
struct decl *decls [1];
};
/* The following nodes are created in automaton checker. */
/* The following nodes represent exclusion, presence, absence set for
cpu units. Each element are accessed through only one excl_list,
presence_list, absence_list. */
struct unit_set_el
{
struct unit_decl *unit_decl;
struct unit_set_el *next_unit_set_el;
};
/* The following nodes are created in automaton generator. */
/* The following node type describes state automaton. The state may
be deterministic or non-deterministic. Non-deterministic state has
several component states which represent alternative cpu units
reservations. The state also is used for describing a
deterministic reservation of automaton insn. */
struct state
{
/* The following member is TRUE if there is a transition by cycle
advancing. */
int new_cycle_p;
/* The following field is list of processor unit reservations on
each cycle. */
reserv_sets_t reservs;
/* The following field is unique number of given state between other
states. */
int unique_num;
/* The following field value is automaton to which given state
belongs. */
struct automaton *automaton;
/* The following field value is the first arc output from given
state. */
struct arc *first_out_arc;
/* The following field is used to form NDFA. */
char it_was_placed_in_stack_for_NDFA_forming;
/* The following field is used to form DFA. */
char it_was_placed_in_stack_for_DFA_forming;
/* The following field is used to transform NDFA to DFA. The field
value is not NULL if the state is a compound state. In this case
the value of field `unit_sets_list' is NULL. All states in the
list are in the hash table. The list is formed through field
`next_sorted_alt_state'. */
struct alt_state *component_states;
/* The following field is used for passing graph of states. */
int pass_num;
/* The list of states belonging to one equivalence class is formed
with the aid of the following field. */
struct state *next_equiv_class_state;
/* The two following fields are used during minimization of a finite
state automaton. */
int equiv_class_num_1, equiv_class_num_2;
/* The following field is used during minimization of a finite state
automaton. The field value is state corresponding to equivalence
class to which given state belongs. */
struct state *equiv_class_state;
/* The following field value is the order number of given state.
The states in final DFA is enumerated with the aid of the
following field. */
int order_state_num;
/* This member is used for passing states for searching minimal
delay time. */
int pass_number;
/* The following member is used to evaluate min issue delay of insn
for a state. */
int min_insn_issue_delay;
};
/* Automaton arc. */
struct arc
{
/* The following field refers for the state into which given arc
enters. */
struct state *to_state;
/* The following field describes that the insn issue (with cycle
advancing for special insn `cycle advancing' and without cycle
advancing for others) makes transition from given state to
another given state. */
struct ainsn *insn;
/* The following field value is the next arc output from the same
state. */
struct arc *next_out_arc;
/* List of arcs marked given insn is formed with the following
field. The field is used in transfromation NDFA -> DFA. */
struct arc *next_arc_marked_by_insn;
/* The following field is defined if NDFA_FLAG is FALSE. The member
value is number of alternative reservations which can be used for
transition for given state by given insn. */
int state_alts;
};
/* The following node type describes a deterministic alternative in
non-deterministic state which characterizes cpu unit reservations
of automaton insn or which is part of NDFA. */
struct alt_state
{
/* The following field is a determinist state which characterizes
unit reservations of the instruction. */
struct state *state;
/* The following field refers to the next state which characterizes
unit reservations of the instruction. */
struct alt_state *next_alt_state;
/* The following field refers to the next state in sorted list. */
struct alt_state *next_sorted_alt_state;
};
/* The following node type describes insn of automaton. They are
labels of FA arcs. */
struct ainsn
{
/* The following field value is the corresponding insn declaration
of description. */
struct insn_reserv_decl *insn_reserv_decl;
/* The following field value is the next insn declaration for an
automaton. */
struct ainsn *next_ainsn;
/* The following field is states which characterize automaton unit
reservations of the instruction. The value can be NULL only if it
is special insn `cycle advancing'. */
struct alt_state *alt_states;
/* The following field is sorted list of states which characterize
automaton unit reservations of the instruction. The value can be
NULL only if it is special insn `cycle advancing'. */
struct alt_state *sorted_alt_states;
/* The following field refers the next automaton insn with
the same reservations. */
struct ainsn *next_same_reservs_insn;
/* The following field is flag of the first automaton insn with the
same reservations in the declaration list. Only arcs marked such
insn is present in the automaton. This significantly decreases
memory requirements especially when several automata are
formed. */
char first_insn_with_same_reservs;
/* The following member has value TRUE if there is arc from state of
the automaton marked by the ainsn. */
char arc_exists_p;
/* Cyclic list of insns of a equivalence class is formed with the
aid of the following field. */
struct ainsn *next_equiv_class_insn;
/* The following field value is TRUE if the insn
declaration is the first insn declaration with given
equivalence number. */
char first_ainsn_with_given_equialence_num;
/* The following field is number of class of equivalence of insns.
It is necessary because many insns may be equivalent with the
point of view of pipeline hazards. */
int insn_equiv_class_num;
};
/* The folowing describes an automaton for PHR. */
struct automaton
{
/* The following field value is the list of insn declarations for
given automaton. */
struct ainsn *ainsn_list;
/* The following field value is the corresponding automaton
declaration. This field is not NULL only if the automatic
partition on automata is not used. */
struct automaton_decl *corresponding_automaton_decl;
/* The following field value is the next automaton. */
struct automaton *next_automaton;
/* The following field is start state of FA. There are not unit
reservations in the state. */
struct state *start_state;
/* The following field value is number of equivalence classes of
insns (see field `insn_equiv_class_num' in
`insn_reserv_decl'). */
int insn_equiv_classes_num;
/* The following field value is number of states of final DFA. */
int achieved_states_num;
/* The following field value is the order number (0, 1, ...) of
given automaton. */
int automaton_order_num;
/* The following fields contain statistics information about
building automaton. */
int NDFA_states_num, DFA_states_num;
/* The following field value is defined only if minimization of DFA
is used. */
int minimal_DFA_states_num;
int NDFA_arcs_num, DFA_arcs_num;
/* The following field value is defined only if minimization of DFA
is used. */
int minimal_DFA_arcs_num;
/* The following two members refer for two table state x ainsn ->
int. */
struct state_ainsn_table *trans_table;
struct state_ainsn_table *state_alts_table;
/* The following member value is maximal value of min issue delay
for insns of the automaton. */
int max_min_delay;
/* Usually min issue delay is small and we can place several (2, 4,
8) elements in one vector element. So the compression factor can
be 1 (no compression), 2, 4, 8. */
int min_issue_delay_table_compression_factor;
};
/* The following structure describes a table state X ainsn -> int(>= 0). */
struct state_ainsn_table
{
/* Automaton to which given table belongs. */
struct automaton *automaton;
/* The following tree vectors for comb vector implementation of the
table. */
vla_hwint_t comb_vect;
vla_hwint_t check_vect;
vla_hwint_t base_vect;
/* This is simple implementation of the table. */
vla_hwint_t full_vect;
/* Minimal and maximal values of the previous vectors. */
int min_comb_vect_el_value, max_comb_vect_el_value;
int min_base_vect_el_value, max_base_vect_el_value;
};
/* Create IR structure (node). */
static void *
create_node (size)
size_t size;
{
void *result;
IR_TOP_EXPAND (size);
result = IR_TOP_BEGIN ();
IR_TOP_FINISH ();
/* Default values of members are NULL and zero. */
memset (result, 0, size);
return result;
}
/* Copy IR structure (node). */
static void *
copy_node (from, size)
void *from;
size_t size;
{
void *result;
result = create_node (size);
memcpy (result, from, size);
return result;
}
/* The function checks that NAME does not contain ". */
static char *
check_name (name, pos)
char * name;
pos_t pos ATTRIBUTE_UNUSED;
{
char *str;
for (str = name; *str != '\0'; str++)
if (*str == '\"')
error ("Name `%s' contains quotes", name);
return name;
}
/* Pointers top all declartions during IR generation are stored in the
following. */
static vla_ptr_t decls;
/* Given a pointer to a (char *) and a separator, return a alloc'ed
string containing the next separated element, taking parentheses
into account if PAR_FLAG is TRUE. Advance the pointer to after the
string scanned, or the end-of-string. Return NULL if at end of
string. */
static char *
next_sep_el (pstr, sep, par_flag)
char **pstr;
int sep;
int par_flag;
{
char *out_str;
char *p;
int pars_num;
int n_spaces;
/* Remove leading whitespaces. */
while (isspace ((int) **pstr))
(*pstr)++;
if (**pstr == '\0')
return NULL;
n_spaces = 0;
for (pars_num = 0, p = *pstr; *p != '\0'; p++)
{
if (par_flag && *p == '(')
pars_num++;
else if (par_flag && *p == ')')
pars_num--;
else if (pars_num == 0 && *p == sep)
break;
if (pars_num == 0 && isspace ((int) *p))
n_spaces++;
else
{
for (; n_spaces != 0; n_spaces--)
IR_TOP_ADD_BYTE (p [-n_spaces]);
IR_TOP_ADD_BYTE (*p);
}
}
IR_TOP_ADD_BYTE ('\0');
out_str = IR_TOP_BEGIN ();
IR_TOP_FINISH ();
*pstr = p;
if (**pstr == sep)
(*pstr)++;
return out_str;
}
/* Given a string and a separator, return the number of separated
elements in it, taking parentheses into account if PAR_FLAG is
TRUE. Return 0 for the null string, -1 if parantheses is not
balanced. */
static int
n_sep_els (s, sep, par_flag)
char *s;
int sep;
int par_flag;
{
int n;
int pars_num;
if (*s == '\0')
return 0;
for (pars_num = 0, n = 1; *s; s++)
if (par_flag && *s == '(')
pars_num++;
else if (par_flag && *s == ')')
pars_num--;
else if (pars_num == 0 && *s == sep)
n++;
return (pars_num != 0 ? -1 : n);
}
/* Given a string and a separator, return vector of strings which are
elements in the string and number of elements through els_num.
Take parentheses into account if PAR_FLAG is TRUE. Return 0 for
the null string, -1 if parantheses are not balanced. */
static char **
get_str_vect (str, els_num, sep, par_flag)
char *str;
int *els_num;
int sep;
int par_flag;
{
int i;
char **vect;
char **pstr;
*els_num = n_sep_els (str, sep, par_flag);
if (*els_num <= 0)
return NULL;
IR_TOP_EXPAND (sizeof (char *) * (*els_num));
vect = (char **) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
pstr = &str;
for (i = 0; i < *els_num; i++)
vect [i] = next_sep_el (pstr, sep, par_flag);
assert (next_sep_el (pstr, sep, par_flag) == NULL);
return vect;
}
/* Process a DEFINE_CPU_UNIT.
This gives information about a unit contained in CPU. We fill a
struct unit_decl with information used later by `expand_automata'. */
static void
gen_cpu_unit (def)
rtx def;
{
struct decl *decl;
char **str_cpu_units;
int vect_length;
int i;
str_cpu_units = get_str_vect ((char *) XSTR (def, 0), &vect_length, ',',
FALSE);
if (str_cpu_units == NULL)
fatal ("invalid string `%s' in define_cpu_unit", XSTR (def, 0));
for (i = 0; i < vect_length; i++)
{
decl = create_node (sizeof (struct decl));
decl->mode = dm_unit;
decl->pos = 0;
decl->decl.unit.name = check_name (str_cpu_units [i], decl->pos);
decl->decl.unit.automaton_name = (char *) XSTR (def, 1);
decl->decl.unit.query_p = FALSE;
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
}
/* Process a DEFINE_QUERY_CPU_UNIT.
This gives information about a unit contained in CPU. We fill a
struct unit_decl with information used later by `expand_automata'. */
static void
gen_query_cpu_unit (def)
rtx def;
{
struct decl *decl;
char **str_cpu_units;
int vect_length;
int i;
str_cpu_units = get_str_vect ((char *) XSTR (def, 0), &vect_length, ',',
FALSE);
if (str_cpu_units == NULL)
fatal ("invalid string `%s' in define_query_cpu_unit", XSTR (def, 0));
for (i = 0; i < vect_length; i++)
{
decl = create_node (sizeof (struct decl));
decl->mode = dm_unit;
decl->pos = 0;
decl->decl.unit.name = check_name (str_cpu_units [i], decl->pos);
decl->decl.unit.automaton_name = (char *) XSTR (def, 1);
decl->decl.unit.query_p = TRUE;
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
}
/* Process a DEFINE_BYPASS.
This gives information about a unit contained in the CPU. We fill
in a struct bypass_decl with information used later by
`expand_automata'. */
static void
gen_bypass (def)
rtx def;
{
struct decl *decl;
char **out_insns;
int out_length;
char **in_insns;
int in_length;
int i, j;
out_insns = get_str_vect ((char *) XSTR (def, 1), &out_length, ',', FALSE);
if (out_insns == NULL)
fatal ("invalid string `%s' in define_bypass", XSTR (def, 1));
in_insns = get_str_vect ((char *) XSTR (def, 2), &in_length, ',', FALSE);
if (in_insns == NULL)
fatal ("invalid string `%s' in define_bypass", XSTR (def, 2));
for (i = 0; i < out_length; i++)
for (j = 0; j < in_length; j++)
{
decl = create_node (sizeof (struct decl));
decl->mode = dm_bypass;
decl->pos = 0;
decl->decl.bypass.latency = XINT (def, 0);
decl->decl.bypass.out_insn_name = out_insns [i];
decl->decl.bypass.in_insn_name = in_insns [j];
decl->decl.bypass.bypass_guard_name = (char *) XSTR (def, 3);
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
}
/* Process a EXCLUSION_SET.
This gives information about a cpu unit conflicts. We fill a
struct unit_rel_decl (excl) with information used later by
`expand_automata'. */
static void
gen_excl_set (def)
rtx def;
{
struct decl *decl;
char **first_str_cpu_units;
char **second_str_cpu_units;
int first_vect_length;
int length;
int i;
first_str_cpu_units
= get_str_vect ((char *) XSTR (def, 0), &first_vect_length, ',', FALSE);
if (first_str_cpu_units == NULL)
fatal ("invalid first string `%s' in exclusion_set", XSTR (def, 0));
second_str_cpu_units = get_str_vect ((char *) XSTR (def, 1), &length, ',',
FALSE);
if (second_str_cpu_units == NULL)
fatal ("invalid second string `%s' in exclusion_set", XSTR (def, 1));
length += first_vect_length;
decl = create_node (sizeof (struct decl) + (length - 1) * sizeof (char *));
decl->mode = dm_excl;
decl->pos = 0;
decl->decl.excl.names_num = length;
decl->decl.excl.first_list_length = first_vect_length;
for (i = 0; i < length; i++)
if (i < first_vect_length)
decl->decl.excl.names [i] = first_str_cpu_units [i];
else
decl->decl.excl.names [i]
= second_str_cpu_units [i - first_vect_length];
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
/* Process a PRESENCE_SET.
This gives information about a cpu unit reservation requirements.
We fill a struct unit_rel_decl (presence) with information used
later by `expand_automata'. */
static void
gen_presence_set (def)
rtx def;
{
struct decl *decl;
char **first_str_cpu_units;
char **second_str_cpu_units;
int first_vect_length;
int length;
int i;
first_str_cpu_units
= get_str_vect ((char *) XSTR (def, 0), &first_vect_length, ',', FALSE);
if (first_str_cpu_units == NULL)
fatal ("invalid first string `%s' in presence_set", XSTR (def, 0));
second_str_cpu_units = get_str_vect ((char *) XSTR (def, 1), &length, ',',
FALSE);
if (second_str_cpu_units == NULL)
fatal ("invalid second string `%s' in presence_set", XSTR (def, 1));
length += first_vect_length;
decl = create_node (sizeof (struct decl) + (length - 1) * sizeof (char *));
decl->mode = dm_presence;
decl->pos = 0;
decl->decl.presence.names_num = length;
decl->decl.presence.first_list_length = first_vect_length;
for (i = 0; i < length; i++)
if (i < first_vect_length)
decl->decl.presence.names [i] = first_str_cpu_units [i];
else
decl->decl.presence.names [i]
= second_str_cpu_units [i - first_vect_length];
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
/* Process a ABSENCE_SET.
This gives information about a cpu unit reservation requirements.
We fill a struct unit_rel_decl (absence) with information used
later by `expand_automata'. */
static void
gen_absence_set (def)
rtx def;
{
struct decl *decl;
char **first_str_cpu_units;
char **second_str_cpu_units;
int first_vect_length;
int length;
int i;
first_str_cpu_units
= get_str_vect ((char *) XSTR (def, 0), &first_vect_length, ',', FALSE);
if (first_str_cpu_units == NULL)
fatal ("invalid first string `%s' in absence_set", XSTR (def, 0));
second_str_cpu_units = get_str_vect ((char *) XSTR (def, 1), &length, ',',
FALSE);
if (second_str_cpu_units == NULL)
fatal ("invalid second string `%s' in absence_set", XSTR (def, 1));
length += first_vect_length;
decl = create_node (sizeof (struct decl) + (length - 1) * sizeof (char *));
decl->mode = dm_absence;
decl->pos = 0;
decl->decl.absence.names_num = length;
decl->decl.absence.first_list_length = first_vect_length;
for (i = 0; i < length; i++)
if (i < first_vect_length)
decl->decl.absence.names [i] = first_str_cpu_units [i];
else
decl->decl.absence.names [i]
= second_str_cpu_units [i - first_vect_length];
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
/* Process a DEFINE_AUTOMATON.
This gives information about a finite state automaton used for
recognizing pipeline hazards. We fill a struct automaton_decl
with information used later by `expand_automata'. */
static void
gen_automaton (def)
rtx def;
{
struct decl *decl;
char **str_automata;
int vect_length;
int i;
str_automata = get_str_vect ((char *) XSTR (def, 0), &vect_length, ',',
FALSE);
if (str_automata == NULL)
fatal ("invalid string `%s' in define_automaton", XSTR (def, 0));
for (i = 0; i < vect_length; i++)
{
decl = create_node (sizeof (struct decl));
decl->mode = dm_automaton;
decl->pos = 0;
decl->decl.automaton.name = check_name (str_automata [i], decl->pos);
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
}
/* Process a AUTOMATA_OPTION.
This gives information how to generate finite state automaton used
for recognizing pipeline hazards. */
static void
gen_automata_option (def)
rtx def;
{
if (strcmp ((char *) XSTR (def, 0), NO_MINIMIZATION_OPTION + 1) == 0)
no_minimization_flag = TRUE;
else if (strcmp ((char *) XSTR (def, 0), W_OPTION + 1) == 0)
w_flag = TRUE;
else if (strcmp ((char *) XSTR (def, 0), NDFA_OPTION + 1) == 0)
ndfa_flag = TRUE;
else
fatal ("invalid option `%s' in automata_option", XSTR (def, 0));
}
/* Name in reservation to denote absence reservation. */
#define NOTHING_NAME "nothing"
/* The following string contains original reservation string being
parsed. */
static char *reserv_str;
/* Parse an element in STR. */
static struct regexp *
gen_regexp_el (str)
char *str;
{
struct regexp *regexp;
int len;
if (*str == '(')
{
len = strlen (str);
if (str [len - 1] != ')')
fatal ("garbage after ) in reservation `%s'", reserv_str);
str [len - 1] = '\0';
regexp = gen_regexp_sequence (str + 1);
}
else if (strcmp (str, NOTHING_NAME) == 0)
{
regexp = create_node (sizeof (struct decl));
regexp->mode = rm_nothing;
}
else
{
regexp = create_node (sizeof (struct decl));
regexp->mode = rm_unit;
regexp->regexp.unit.name = str;
}
return regexp;
}
/* Parse construction `repeat' in STR. */
static struct regexp *
gen_regexp_repeat (str)
char *str;
{
struct regexp *regexp;
struct regexp *repeat;
char **repeat_vect;
int els_num;
int i;
repeat_vect = get_str_vect (str, &els_num, '*', TRUE);
if (repeat_vect == NULL)
fatal ("invalid `%s' in reservation `%s'", str, reserv_str);
if (els_num > 1)
{
regexp = gen_regexp_el (repeat_vect [0]);
for (i = 1; i < els_num; i++)
{
repeat = create_node (sizeof (struct regexp));
repeat->mode = rm_repeat;
repeat->regexp.repeat.regexp = regexp;
repeat->regexp.repeat.repeat_num = atoi (repeat_vect [i]);
if (repeat->regexp.repeat.repeat_num <= 1)
fatal ("repetition `%s' <= 1 in reservation `%s'",
str, reserv_str);
regexp = repeat;
}
return regexp;
}
else
return gen_regexp_el (str);
}
/* Parse reservation STR which possibly contains separator '+'. */
static struct regexp *
gen_regexp_allof (str)
char *str;
{
struct regexp *allof;
char **allof_vect;
int els_num;
int i;
allof_vect = get_str_vect (str, &els_num, '+', TRUE);
if (allof_vect == NULL)
fatal ("invalid `%s' in reservation `%s'", str, reserv_str);
if (els_num > 1)
{
allof = create_node (sizeof (struct regexp)
+ sizeof (struct regexp *) * (els_num - 1));
allof->mode = rm_allof;
allof->regexp.allof.regexps_num = els_num;
for (i = 0; i < els_num; i++)
allof->regexp.allof.regexps [i] = gen_regexp_repeat (allof_vect [i]);
return allof;
}
else
return gen_regexp_repeat (str);
}
/* Parse reservation STR which possibly contains separator '|'. */
static struct regexp *
gen_regexp_oneof (str)
char *str;
{
struct regexp *oneof;
char **oneof_vect;
int els_num;
int i;
oneof_vect = get_str_vect (str, &els_num, '|', TRUE);
if (oneof_vect == NULL)
fatal ("invalid `%s' in reservation `%s'", str, reserv_str);
if (els_num > 1)
{
oneof = create_node (sizeof (struct regexp)
+ sizeof (struct regexp *) * (els_num - 1));
oneof->mode = rm_oneof;
oneof->regexp.oneof.regexps_num = els_num;
for (i = 0; i < els_num; i++)
oneof->regexp.oneof.regexps [i] = gen_regexp_allof (oneof_vect [i]);
return oneof;
}
else
return gen_regexp_allof (str);
}
/* Parse reservation STR which possibly contains separator ','. */
static struct regexp *
gen_regexp_sequence (str)
char *str;
{
struct regexp *sequence;
char **sequence_vect;
int els_num;
int i;
sequence_vect = get_str_vect (str, &els_num, ',', TRUE);
if (els_num > 1)
{
sequence = create_node (sizeof (struct regexp)
+ sizeof (struct regexp *) * (els_num - 1));
sequence->mode = rm_sequence;
sequence->regexp.sequence.regexps_num = els_num;
for (i = 0; i < els_num; i++)
sequence->regexp.sequence.regexps [i]
= gen_regexp_oneof (sequence_vect [i]);
return sequence;
}
else
return gen_regexp_oneof (str);
}
/* Parse construction reservation STR. */
static struct regexp *
gen_regexp (str)
char *str;
{
reserv_str = str;
return gen_regexp_sequence (str);;
}
/* Process a DEFINE_RESERVATION.
This gives information about a reservation of cpu units. We fill
in a struct reserv_decl with information used later by
`expand_automata'. */
static void
gen_reserv (def)
rtx def;
{
struct decl *decl;
decl = create_node (sizeof (struct decl));
decl->mode = dm_reserv;
decl->pos = 0;
decl->decl.reserv.name = check_name ((char *) XSTR (def, 0), decl->pos);
decl->decl.reserv.regexp = gen_regexp ((char *) XSTR (def, 1));
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
/* Process a DEFINE_INSN_RESERVATION.
This gives information about the reservation of cpu units by an
insn. We fill a struct insn_reserv_decl with information used
later by `expand_automata'. */
static void
gen_insn_reserv (def)
rtx def;
{
struct decl *decl;
decl = create_node (sizeof (struct decl));
decl->mode = dm_insn_reserv;
decl->pos = 0;
decl->decl.insn_reserv.name = check_name ((char *) XSTR (def, 0), decl->pos);
decl->decl.insn_reserv.default_latency = XINT (def, 1);
decl->decl.insn_reserv.condexp = XEXP (def, 2);
decl->decl.insn_reserv.regexp = gen_regexp ((char *) XSTR (def, 3));
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
/* The function evaluates hash value (0..UINT_MAX) of string. */
static unsigned
string_hash (string)
const char *string;
{
unsigned result, i;
for (result = i = 0;*string++ != '\0'; i++)
result += ((unsigned char) *string << (i % CHAR_BIT));
return result;
}
/* This page contains abstract data `table of automaton declarations'.
Elements of the table is nodes representing automaton declarations.
Key of the table elements is name of given automaton. Rememeber
that automaton names have own space. */
/* The function evaluates hash value of a automaton declaration. The
function is used by abstract data `hashtab'. The function returns
hash value (0..UINT_MAX) of given automaton declaration. */
static unsigned
automaton_decl_hash (automaton_decl)
const void *automaton_decl;
{
const struct decl *decl = (struct decl *) automaton_decl;
assert (decl->mode == dm_automaton && decl->decl.automaton.name != NULL);
return string_hash (decl->decl.automaton.name);
}
/* The function tests automaton declarations on equality of their
keys. The function is used by abstract data `hashtab'. The
function returns 1 if the declarations have the same key, 0
otherwise. */
static int
automaton_decl_eq_p (automaton_decl_1, automaton_decl_2)
const void* automaton_decl_1;
const void* automaton_decl_2;
{
const struct decl *decl1 = (struct decl *) automaton_decl_1;
const struct decl *decl2 = (struct decl *) automaton_decl_2;
assert (decl1->mode == dm_automaton && decl1->decl.automaton.name != NULL
&& decl2->mode == dm_automaton
&& decl2->decl.automaton.name != NULL);
return strcmp (decl1->decl.automaton.name, decl2->decl.automaton.name) == 0;
}
/* The automaton declaration table itself is represented by the
following variable. */
static htab_t automaton_decl_table;
/* The function inserts automaton declaration into the table. The
function does nothing if an automaton declaration with the same key
exists already in the table. The function returns automaton
declaration node in the table with the same key as given automaton
declaration node. */
static struct decl *
insert_automaton_decl (automaton_decl)
struct decl *automaton_decl;
{
void **entry_ptr;
entry_ptr = htab_find_slot (automaton_decl_table, automaton_decl, TRUE);
if (*entry_ptr == NULL)
*entry_ptr = (void *) automaton_decl;
return (struct decl *) *entry_ptr;
}
/* The following variable value is node representing automaton
declaration. The node used for searching automaton declaration
with given name. */
static struct decl work_automaton_decl;
/* The function searches for automaton declaration in the table with
the same key as node representing name of the automaton
declaration. The function returns node found in the table, NULL if
such node does not exist in the table. */
static struct decl *
find_automaton_decl (name)
char *name;
{
void *entry;
work_automaton_decl.decl.automaton.name = name;
entry = htab_find (automaton_decl_table, &work_automaton_decl);
return (struct decl *) entry;
}
/* The function creates empty automaton declaration table and node
representing automaton declaration and used for searching automaton
declaration with given name. The function must be called only once
before any work with the automaton declaration table. */
static void
initiate_automaton_decl_table ()
{
work_automaton_decl.mode = dm_automaton;
automaton_decl_table = htab_create (10, automaton_decl_hash,
automaton_decl_eq_p, (htab_del) 0);
}
/* The function deletes the automaton declaration table. Only call of
function `initiate_automaton_decl_table' is possible immediately
after this function call. */
static void
finish_automaton_decl_table ()
{
htab_delete (automaton_decl_table);
}
/* This page contains abstract data `table of insn declarations'.
Elements of the table is nodes representing insn declarations. Key
of the table elements is name of given insn (in corresponding
define_insn_reservation). Rememeber that insn names have own
space. */
/* The function evaluates hash value of a insn declaration. The
function is used by abstract data `hashtab'. The function returns
hash value (0..UINT_MAX) of given insn declaration. */
static unsigned
insn_decl_hash (insn_decl)
const void *insn_decl;
{
const struct decl *decl = (struct decl *) insn_decl;
assert (decl->mode == dm_insn_reserv && decl->decl.insn_reserv.name != NULL);
return string_hash (decl->decl.insn_reserv.name);
}
/* The function tests insn declarations on equality of their keys.
The function is used by abstract data `hashtab'. The function
returns 1 if declarations have the same key, 0 otherwise. */
static int
insn_decl_eq_p (insn_decl_1, insn_decl_2)
const void *insn_decl_1;
const void *insn_decl_2;
{
const struct decl *decl1 = (struct decl *) insn_decl_1;
const struct decl *decl2 = (struct decl *) insn_decl_2;
assert (decl1->mode == dm_insn_reserv && decl1->decl.insn_reserv.name != NULL
&& decl2->mode == dm_insn_reserv
&& decl2->decl.insn_reserv.name != NULL);
return strcmp (decl1->decl.insn_reserv.name,
decl2->decl.insn_reserv.name) == 0;
}
/* The insn declaration table itself is represented by the following
variable. The table does not contain insn reservation
declarations. */
static htab_t insn_decl_table;
/* The function inserts insn declaration into the table. The function
does nothing if an insn declaration with the same key exists
already in the table. The function returns insn declaration node
in the table with the same key as given insn declaration node. */
static struct decl *
insert_insn_decl (insn_decl)
struct decl *insn_decl;
{
void **entry_ptr;
entry_ptr = htab_find_slot (insn_decl_table, insn_decl, TRUE);
if (*entry_ptr == NULL)
*entry_ptr = (void *) insn_decl;
return (struct decl *) *entry_ptr;
}
/* The following variable value is node representing insn reservation
declaration. The node used for searching insn reservation
declaration with given name. */
static struct decl work_insn_decl;
/* The function searches for insn reservation declaration in the table
with the same key as node representing name of the insn reservation
declaration. The function returns node found in the table, NULL if
such node does not exist in the table. */
static struct decl *
find_insn_decl (name)
char *name;
{
void *entry;
work_insn_decl.decl.insn_reserv.name = name;
entry = htab_find (insn_decl_table, &work_insn_decl);
return (struct decl *) entry;
}
/* The function creates empty insn declaration table and node
representing insn declaration and used for searching insn
declaration with given name. The function must be called only once
before any work with the insn declaration table. */
static void
initiate_insn_decl_table ()
{
work_insn_decl.mode = dm_insn_reserv;
insn_decl_table = htab_create (10, insn_decl_hash, insn_decl_eq_p,
(htab_del) 0);
}
/* The function deletes the insn declaration table. Only call of
function `initiate_insn_decl_table' is possible immediately after
this function call. */
static void
finish_insn_decl_table ()
{
htab_delete (insn_decl_table);
}
/* This page contains abstract data `table of declarations'. Elements
of the table is nodes representing declarations (of units and
reservations). Key of the table elements is names of given
declarations. */
/* The function evaluates hash value of a declaration. The function
is used by abstract data `hashtab'. The function returns hash
value (0..UINT_MAX) of given declaration. */
static unsigned
decl_hash (decl)
const void *decl;
{
const struct decl *d = (const struct decl *) decl;
assert ((d->mode == dm_unit && d->decl.unit.name)
|| (d->mode == dm_reserv && d->decl.reserv.name));
return string_hash (d->mode == dm_unit
? d->decl.unit.name : d->decl.reserv.name);
}
/* The function tests declarations on equality of their keys. The
function is used by abstract data `hashtab'. The function
returns 1 if the declarations have the same key, 0 otherwise. */
static int
decl_eq_p (decl_1, decl_2)
const void *decl_1;
const void *decl_2;
{
const struct decl *d1 = (const struct decl *) decl_1;
const struct decl *d2 = (const struct decl *) decl_2;
assert (((d1->mode == dm_unit && d1->decl.unit.name)
|| (d1->mode == dm_reserv && d1->decl.reserv.name))
&& ((d2->mode == dm_unit && d2->decl.unit.name)
|| (d2->mode == dm_reserv && d2->decl.reserv.name)));
return strcmp ((d1->mode == dm_unit
? d1->decl.unit.name : d1->decl.reserv.name),
(d2->mode == dm_unit
? d2->decl.unit.name : d2->decl.reserv.name)) == 0;
}
/* The declaration table itself is represented by the following
variable. */
static htab_t decl_table;
/* The function inserts declaration into the table. The function does
nothing if a declaration with the same key exists already in the
table. The function returns declaration node in the table with the
same key as given declaration node. */
static struct decl *
insert_decl (decl)
struct decl *decl;
{
void **entry_ptr;
entry_ptr = htab_find_slot (decl_table, decl, TRUE);
if (*entry_ptr == NULL)
*entry_ptr = (void *) decl;
return (struct decl *) *entry_ptr;
}
/* The following variable value is node representing declaration. The
node used for searching declaration with given name. */
static struct decl work_decl;
/* The function searches for declaration in the table with the same
key as node representing name of the declaration. The function
returns node found in the table, NULL if such node does not exist
in the table. */
static struct decl *
find_decl (name)
char *name;
{
void *entry;
work_decl.decl.unit.name = name;
entry = htab_find (decl_table, &work_decl);
return (struct decl *) entry;
}
/* The function creates empty declaration table and node representing
declaration and used for searching declaration with given name.
The function must be called only once before any work with the
declaration table. */
static void
initiate_decl_table ()
{
work_decl.mode = dm_unit;
decl_table = htab_create (10, decl_hash, decl_eq_p, (htab_del) 0);
}
/* The function deletes the declaration table. Only call of function
`initiate_declaration_table' is possible immediately after this
function call. */
static void
finish_decl_table ()
{
htab_delete (decl_table);
}
/* This page contains checker of pipeline hazard description. */
/* Checking NAMES in an exclusion clause vector and returning formed
unit_set_el_list. */
static struct unit_set_el *
process_excls (names, num, excl_pos)
char **names;
int num;
pos_t excl_pos ATTRIBUTE_UNUSED;
{
struct unit_set_el *el_list;
struct unit_set_el *last_el;
struct unit_set_el *new_el;
struct decl *decl_in_table;
int i;
el_list = NULL;
last_el = NULL;
for (i = 0; i < num; i++)
{
decl_in_table = find_decl (names [i]);
if (decl_in_table == NULL)
error ("unit `%s' in exclusion is not declared", names [i]);
else if (decl_in_table->mode != dm_unit)
error ("`%s' in exclusion is not unit", names [i]);
else
{
new_el = create_node (sizeof (struct unit_set_el));
new_el->unit_decl = &decl_in_table->decl.unit;
new_el->next_unit_set_el = NULL;
if (last_el == NULL)
el_list = last_el = new_el;
else
{
last_el->next_unit_set_el = new_el;
last_el = last_el->next_unit_set_el;
}
}
}
return el_list;
}
/* The function adds each element from SOURCE_LIST to the exclusion
list of the each element from DEST_LIST. Checking situation "unit
excludes itself". */
static void
add_excls (dest_list, source_list, excl_pos)
struct unit_set_el *dest_list;
struct unit_set_el *source_list;
pos_t excl_pos ATTRIBUTE_UNUSED;
{
struct unit_set_el *curr_dest_el;
struct unit_set_el *curr_source_el;
struct unit_set_el *curr_excl_list_unit;
struct unit_set_el *prev_excl_list_unit;
struct unit_set_el *copy;
for (curr_dest_el = dest_list;
curr_dest_el != NULL;
curr_dest_el = curr_dest_el->next_unit_set_el)
for (curr_source_el = source_list;
curr_source_el != NULL;
curr_source_el = curr_source_el->next_unit_set_el)
{
if (curr_dest_el->unit_decl == curr_source_el->unit_decl)
{
error ("unit `%s' excludes itself",
curr_source_el->unit_decl->name);
continue;
}
for (curr_excl_list_unit = curr_dest_el->unit_decl->excl_list,
prev_excl_list_unit = NULL;
curr_excl_list_unit != NULL;
prev_excl_list_unit = curr_excl_list_unit,
curr_excl_list_unit = curr_excl_list_unit->next_unit_set_el)
if (curr_excl_list_unit->unit_decl == curr_source_el->unit_decl)
break;
if (curr_excl_list_unit == NULL)
{
/* Element not found - insert. */
copy = copy_node (curr_source_el, sizeof (*curr_source_el));
copy->next_unit_set_el = NULL;
if (prev_excl_list_unit == NULL)
curr_dest_el->unit_decl->excl_list = copy;
else
prev_excl_list_unit->next_unit_set_el = copy;
}
}
}
/* Checking NAMES in an presence clause vector and returning formed
unit_set_el_list. The function is called only after processing all
exclusion sets. */
static struct unit_set_el *
process_presence_absence (names, num, req_pos, presence_p)
char **names;
int num;
pos_t req_pos ATTRIBUTE_UNUSED;
int presence_p;
{
struct unit_set_el *el_list;
struct unit_set_el *last_el;
struct unit_set_el *new_el;
struct decl *decl_in_table;
int i;
el_list = NULL;
last_el = NULL;
for (i = 0; i < num; i++)
{
decl_in_table = find_decl (names [i]);
if (decl_in_table == NULL)
error ((presence_p
? "unit `%s' in presence set is not declared"
: "unit `%s' in absence set is not declared"), names [i]);
else if (decl_in_table->mode != dm_unit)
error ((presence_p
? "`%s' in presence set is not unit"
: "`%s' in absence set is not unit"), names [i]);
else
{
new_el = create_node (sizeof (struct unit_set_el));
new_el->unit_decl = &decl_in_table->decl.unit;
new_el->next_unit_set_el = NULL;
if (last_el == NULL)
el_list = last_el = new_el;
else
{
last_el->next_unit_set_el = new_el;
last_el = last_el->next_unit_set_el;
}
}
}
return el_list;
}
/* The function adds each element from SOURCE_LIST to presence (if
PRESENCE_P) or absence list of the each element from DEST_LIST.
Checking situations "unit requires own presence", "unit requires
own absence", and "unit excludes and requires presence of ...".
Remember that we process absence sets only after all presence
sets. */
static void
add_presence_absence (dest_list, source_list, req_pos, presence_p)
struct unit_set_el *dest_list;
struct unit_set_el *source_list;
pos_t req_pos ATTRIBUTE_UNUSED;
int presence_p;
{
struct unit_set_el *curr_dest_el;
struct unit_set_el *curr_source_el;
struct unit_set_el *curr_list_unit;
struct unit_set_el *prev_list_unit;
struct unit_set_el *copy;
for (curr_dest_el = dest_list;
curr_dest_el != NULL;
curr_dest_el = curr_dest_el->next_unit_set_el)
for (curr_source_el = source_list;
curr_source_el != NULL;
curr_source_el = curr_source_el->next_unit_set_el)
{
if (curr_dest_el->unit_decl == curr_source_el->unit_decl)
{
error ((presence_p
? "unit `%s' requires own presence"
: "unit `%s' requires own absence"),
curr_source_el->unit_decl->name);
continue;
}
for (curr_list_unit = (presence_p
? curr_dest_el->unit_decl->presence_list
: curr_dest_el->unit_decl->absence_list),
prev_list_unit = NULL;
curr_list_unit != NULL;
prev_list_unit = curr_list_unit,
curr_list_unit = curr_list_unit->next_unit_set_el)
if (curr_list_unit->unit_decl == curr_source_el->unit_decl)
break;
if (curr_list_unit == NULL)
{
/* Element not found - insert if there is no error. */
int no_error_flag = TRUE;
if (presence_p)
for (curr_list_unit = curr_dest_el->unit_decl->excl_list;
curr_list_unit != NULL;
curr_list_unit = curr_list_unit->next_unit_set_el)
{
if (curr_source_el->unit_decl == curr_list_unit->unit_decl)
{
if (!w_flag)
{
error
("unit `%s' excludes and requires presence of `%s'",
curr_dest_el->unit_decl->name,
curr_source_el->unit_decl->name);
no_error_flag = FALSE;
}
else
warning
("unit `%s' excludes and requires presence of `%s'",
curr_dest_el->unit_decl->name,
curr_source_el->unit_decl->name);
}
}
else
for (curr_list_unit = curr_dest_el->unit_decl->presence_list;
curr_list_unit != NULL;
curr_list_unit = curr_list_unit->next_unit_set_el)
{
if (curr_source_el->unit_decl == curr_list_unit->unit_decl)
{
if (!w_flag)
{
error
("unit `%s' requires absence and presence of `%s'",
curr_dest_el->unit_decl->name,
curr_source_el->unit_decl->name);
no_error_flag = FALSE;
}
else
warning
("unit `%s' requires absence and presence of `%s'",
curr_dest_el->unit_decl->name,
curr_source_el->unit_decl->name);
}
}
if (no_error_flag)
{
copy = copy_node (curr_source_el, sizeof (*curr_source_el));
copy->next_unit_set_el = NULL;
if (prev_list_unit == NULL)
{
if (presence_p)
curr_dest_el->unit_decl->presence_list = copy;
else
curr_dest_el->unit_decl->absence_list = copy;
}
else
prev_list_unit->next_unit_set_el = copy;
}
}
}
}
/* The function searches for bypass with given IN_INSN_RESERV in given
BYPASS_LIST. */
static struct bypass_decl *
find_bypass (bypass_list, in_insn_reserv)
struct bypass_decl *bypass_list;
struct insn_reserv_decl *in_insn_reserv;
{
struct bypass_decl *curr_bypass;
for (curr_bypass = bypass_list;
curr_bypass != NULL;
curr_bypass = curr_bypass->next)
if (curr_bypass->in_insn_reserv == in_insn_reserv)
break;
return curr_bypass;
}
/* The function fixes warnings/errors `... already declared'
`... repeated declaration'. The function also fixes occurences of
undeclared automata name in unit declarations or absence of insn
name in unit declarations if there are automaton declarations. The
function checks bypasses and forms list of bypasses for each
(output) insn. */
static void
process_decls ()
{
struct decl *curr_decl;
struct decl *automaton_decl;
struct decl *decl_in_table;
struct decl *out_insn_reserv;
struct decl *in_insn_reserv;
struct bypass_decl *bypass;
int automaton_presence;
int i;
automaton_presence = FALSE;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_automaton)
{
automaton_presence = TRUE;
decl_in_table = insert_automaton_decl (curr_decl);
if (decl_in_table != curr_decl)
{
if (!w_flag)
error ("repeated declaration of automaton `%s'",
curr_decl->decl.automaton.name);
else
warning ("repeated declaration of automaton `%s'",
curr_decl->decl.automaton.name);
}
}
}
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv)
{
curr_decl->decl.insn_reserv.condexp
= check_attr_test (curr_decl->decl.insn_reserv.condexp, 0, 0);
if (curr_decl->decl.insn_reserv.default_latency < 0)
error ("define_insn_reservation `%s' has negative latency time",
curr_decl->decl.insn_reserv.name);
curr_decl->decl.insn_reserv.insn_num = description->insns_num;
description->insns_num++;
decl_in_table = insert_insn_decl (curr_decl);
if (decl_in_table != curr_decl)
error ("`%s' is already used as insn reservation name",
curr_decl->decl.insn_reserv.name);
}
else if (curr_decl->mode == dm_bypass)
{
if (curr_decl->decl.bypass.latency < 0)
error ("define_bypass `%s - %s' has negative latency time",
curr_decl->decl.bypass.out_insn_name,
curr_decl->decl.bypass.in_insn_name);
}
else if (curr_decl->mode == dm_unit || curr_decl->mode == dm_reserv)
{
if (curr_decl->mode == dm_unit)
{
curr_decl->decl.unit.automaton_decl = NULL;
if (curr_decl->decl.unit.automaton_name != NULL)
{
automaton_decl
= find_automaton_decl
(curr_decl->decl.unit.automaton_name);
if (automaton_decl == NULL)
error ("automaton `%s' is not declared",
curr_decl->decl.unit.automaton_name);
else
{
automaton_decl->decl.automaton.automaton_is_used = TRUE;
curr_decl->decl.unit.automaton_decl
= &automaton_decl->decl.automaton;
}
}
else if (automaton_presence)
error ("define_unit `%s' without automaton when one defined",
curr_decl->decl.unit.name);
curr_decl->decl.unit.unit_num = description->units_num;
description->units_num++;
if (strcmp (curr_decl->decl.unit.name, NOTHING_NAME) == 0)
{
error ("`%s' is declared as cpu unit", NOTHING_NAME);
continue;
}
decl_in_table = find_decl (curr_decl->decl.unit.name);
}
else
{
if (strcmp (curr_decl->decl.reserv.name, NOTHING_NAME) == 0)
{
error ("`%s' is declared as cpu reservation", NOTHING_NAME);
continue;
}
decl_in_table = find_decl (curr_decl->decl.reserv.name);
}
if (decl_in_table == NULL)
decl_in_table = insert_decl (curr_decl);
else
{
if (curr_decl->mode == dm_unit)
error ("repeated declaration of unit `%s'",
curr_decl->decl.unit.name);
else
error ("repeated declaration of reservation `%s'",
curr_decl->decl.reserv.name);
}
}
}
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_bypass)
{
out_insn_reserv
= find_insn_decl (curr_decl->decl.bypass.out_insn_name);
in_insn_reserv
= find_insn_decl (curr_decl->decl.bypass.in_insn_name);
if (out_insn_reserv == NULL)
error ("there is no insn reservation `%s'",
curr_decl->decl.bypass.out_insn_name);
else if (in_insn_reserv == NULL)
error ("there is no insn reservation `%s'",
curr_decl->decl.bypass.in_insn_name);
else
{
curr_decl->decl.bypass.out_insn_reserv
= &out_insn_reserv->decl.insn_reserv;
curr_decl->decl.bypass.in_insn_reserv
= &in_insn_reserv->decl.insn_reserv;
bypass
= find_bypass (out_insn_reserv->decl.insn_reserv.bypass_list,
curr_decl->decl.bypass.in_insn_reserv);
if (bypass != NULL)
{
if (curr_decl->decl.bypass.latency == bypass->latency)
{
if (!w_flag)
error
("the same bypass `%s - %s' is already defined",
curr_decl->decl.bypass.out_insn_name,
curr_decl->decl.bypass.in_insn_name);
else
warning
("the same bypass `%s - %s' is already defined",
curr_decl->decl.bypass.out_insn_name,
curr_decl->decl.bypass.in_insn_name);
}
else
error ("bypass `%s - %s' is already defined",
curr_decl->decl.bypass.out_insn_name,
curr_decl->decl.bypass.in_insn_name);
}
else
{
curr_decl->decl.bypass.next
= out_insn_reserv->decl.insn_reserv.bypass_list;
out_insn_reserv->decl.insn_reserv.bypass_list
= &curr_decl->decl.bypass;
}
}
}
}
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_excl)
{
struct unit_set_el *unit_set_el_list;
struct unit_set_el *unit_set_el_list_2;
unit_set_el_list
= process_excls (curr_decl->decl.excl.names,
curr_decl->decl.excl.first_list_length,
curr_decl->pos);
unit_set_el_list_2
= process_excls (&curr_decl->decl.excl.names
[curr_decl->decl.excl.first_list_length],
curr_decl->decl.excl.names_num
- curr_decl->decl.excl.first_list_length,
curr_decl->pos);
add_excls (unit_set_el_list, unit_set_el_list_2, curr_decl->pos);
add_excls (unit_set_el_list_2, unit_set_el_list, curr_decl->pos);
}
}
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_presence)
{
struct unit_set_el *unit_set_el_list;
struct unit_set_el *unit_set_el_list_2;
unit_set_el_list
= process_presence_absence
(curr_decl->decl.presence.names,
curr_decl->decl.presence.first_list_length,
curr_decl->pos, TRUE);
unit_set_el_list_2
= process_presence_absence
(&curr_decl->decl.presence.names
[curr_decl->decl.presence.first_list_length],
curr_decl->decl.presence.names_num
- curr_decl->decl.presence.first_list_length,
curr_decl->pos, TRUE);
add_presence_absence (unit_set_el_list, unit_set_el_list_2,
curr_decl->pos, TRUE);
}
}
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_absence)
{
struct unit_set_el *unit_set_el_list;
struct unit_set_el *unit_set_el_list_2;
unit_set_el_list
= process_presence_absence
(curr_decl->decl.presence.names,
curr_decl->decl.presence.first_list_length,
curr_decl->pos, FALSE);
unit_set_el_list_2
= process_presence_absence
(&curr_decl->decl.presence.names
[curr_decl->decl.presence.first_list_length],
curr_decl->decl.presence.names_num
- curr_decl->decl.presence.first_list_length,
curr_decl->pos, FALSE);
add_presence_absence (unit_set_el_list, unit_set_el_list_2,
curr_decl->pos, FALSE);
}
}
}
/* The following function checks that declared automaton is used. If
the automaton is not used, the function fixes error/warning. The
following function must be called only after `process_decls'. */
static void
check_automaton_usage ()
{
struct decl *curr_decl;
int i;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_automaton
&& !curr_decl->decl.automaton.automaton_is_used)
{
if (!w_flag)
error ("automaton `%s' is not used",
curr_decl->decl.automaton.name);
else
warning ("automaton `%s' is not used",
curr_decl->decl.automaton.name);
}
}
}
/* The following recursive function processes all regexp in order to
fix usage of units or reservations and to fix errors of undeclared
name. The function may change unit_regexp onto reserv_regexp.
Remember that reserv_regexp does not exist before the function
call. */
static struct regexp *
process_regexp (regexp)
struct regexp *regexp;
{
struct decl *decl_in_table;
struct regexp *new_regexp;
int i;
if (regexp->mode == rm_unit)
{
decl_in_table = find_decl (regexp->regexp.unit.name);
if (decl_in_table == NULL)
error ("undeclared unit or reservation `%s'",
regexp->regexp.unit.name);
else if (decl_in_table->mode == dm_unit)
{
decl_in_table->decl.unit.unit_is_used = TRUE;
regexp->regexp.unit.unit_decl = &decl_in_table->decl.unit;
}
else if (decl_in_table->mode == dm_reserv)
{
decl_in_table->decl.reserv.reserv_is_used = TRUE;
new_regexp = create_node (sizeof (struct regexp));
new_regexp->mode = rm_reserv;
new_regexp->pos = regexp->pos;
new_regexp->regexp.reserv.name = regexp->regexp.unit.name;
new_regexp->regexp.reserv.reserv_decl = &decl_in_table->decl.reserv;
regexp = new_regexp;
}
else
assert (FALSE);
}
else if (regexp->mode == rm_sequence)
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
regexp->regexp.sequence.regexps [i]
= process_regexp (regexp->regexp.sequence.regexps [i]);
else if (regexp->mode == rm_allof)
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
regexp->regexp.allof.regexps [i]
= process_regexp (regexp->regexp.allof.regexps [i]);
else if (regexp->mode == rm_oneof)
for (i = 0; i < regexp->regexp.oneof.regexps_num; i++)
regexp->regexp.oneof.regexps [i]
= process_regexp (regexp->regexp.oneof.regexps [i]);
else if (regexp->mode == rm_repeat)
regexp->regexp.repeat.regexp
= process_regexp (regexp->regexp.repeat.regexp);
else
assert (regexp->mode == rm_nothing);
return regexp;
}
/* The following function processes regexp of define_reservation and
define_insn_reservation with the aid of function
`process_regexp'. */
static void
process_regexp_decls ()
{
struct decl *curr_decl;
int i;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_reserv)
curr_decl->decl.reserv.regexp
= process_regexp (curr_decl->decl.reserv.regexp);
else if (curr_decl->mode == dm_insn_reserv)
curr_decl->decl.insn_reserv.regexp
= process_regexp (curr_decl->decl.insn_reserv.regexp);
}
}
/* The following function checks that declared unit is used. If the
unit is not used, the function fixes errors/warnings. The
following function must be called only after `process_decls',
`process_regexp_decls'. */
static void
check_usage ()
{
struct decl *curr_decl;
int i;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_unit && !curr_decl->decl.unit.unit_is_used)
{
if (!w_flag)
error ("unit `%s' is not used", curr_decl->decl.unit.name);
else
warning ("unit `%s' is not used", curr_decl->decl.unit.name);
}
else if (curr_decl->mode == dm_reserv
&& !curr_decl->decl.reserv.reserv_is_used)
{
if (!w_flag)
error ("reservation `%s' is not used",
curr_decl->decl.reserv.name);
else
warning ("reservation `%s' is not used",
curr_decl->decl.reserv.name);
}
}
}
/* The following variable value is number of reservation being
processed on loop recognition. */
static int current_loop_pass_num;
/* The following recursive function returns TRUE if REGEXP contains
given decl or reservations in given regexp refers for given
decl. */
static int
loop_in_regexp (regexp, start_decl)
struct regexp *regexp;
struct decl *start_decl;
{
int i;
if (regexp == NULL)
return FALSE;
if (regexp->mode == rm_unit)
return FALSE;
else if (regexp->mode == rm_reserv)
{
if (start_decl->mode == dm_reserv
&& regexp->regexp.reserv.reserv_decl == &start_decl->decl.reserv)
return TRUE;
else if (regexp->regexp.reserv.reserv_decl->loop_pass_num
== current_loop_pass_num)
/* declaration has been processed. */
return FALSE;
else
{
regexp->regexp.reserv.reserv_decl->loop_pass_num
= current_loop_pass_num;
return loop_in_regexp (regexp->regexp.reserv.reserv_decl->regexp,
start_decl);
}
}
else if (regexp->mode == rm_sequence)
{
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
if (loop_in_regexp (regexp->regexp.sequence.regexps [i], start_decl))
return TRUE;
return FALSE;
}
else if (regexp->mode == rm_allof)
{
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
if (loop_in_regexp (regexp->regexp.allof.regexps [i], start_decl))
return TRUE;
return FALSE;
}
else if (regexp->mode == rm_oneof)
{
for (i = 0; i < regexp->regexp.oneof.regexps_num; i++)
if (loop_in_regexp (regexp->regexp.oneof.regexps [i], start_decl))
return TRUE;
return FALSE;
}
else if (regexp->mode == rm_repeat)
return loop_in_regexp (regexp->regexp.repeat.regexp, start_decl);
else
{
assert (regexp->mode == rm_nothing);
return FALSE;
}
}
/* The following function fixes errors "cycle in definition ...". The
function uses function `loop_in_regexp' for that. */
static void
check_loops_in_regexps ()
{
struct decl *curr_decl;
int i;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_reserv)
curr_decl->decl.reserv.loop_pass_num = 0;
}
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
current_loop_pass_num = i;
if (curr_decl->mode == dm_reserv)
{
curr_decl->decl.reserv.loop_pass_num = current_loop_pass_num;
if (loop_in_regexp (curr_decl->decl.reserv.regexp, curr_decl))
{
assert (curr_decl->decl.reserv.regexp != NULL);
error ("cycle in definition of reservation `%s'",
curr_decl->decl.reserv.name);
}
}
}
}
/* The function recursively processes IR of reservation and defines
max and min cycle for reservation of unit and for result in the
reservation. */
static int
process_regexp_cycles (regexp, start_cycle)
struct regexp *regexp;
int start_cycle;
{
int i;
if (regexp->mode == rm_unit)
{
if (regexp->regexp.unit.unit_decl->max_occ_cycle_num < start_cycle)
regexp->regexp.unit.unit_decl->max_occ_cycle_num = start_cycle;
return start_cycle;
}
else if (regexp->mode == rm_reserv)
return process_regexp_cycles (regexp->regexp.reserv.reserv_decl->regexp,
start_cycle);
else if (regexp->mode == rm_repeat)
{
int current_repetition_num;
for (current_repetition_num = 0;
current_repetition_num < regexp->regexp.repeat.repeat_num;
current_repetition_num++)
start_cycle = process_regexp_cycles (regexp->regexp.repeat.regexp,
start_cycle) + 1;
return start_cycle;
}
else if (regexp->mode == rm_sequence)
{
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
start_cycle
= process_regexp_cycles (regexp->regexp.sequence.regexps [i],
start_cycle) + 1;
return start_cycle;
}
else if (regexp->mode == rm_allof)
{
int finish_cycle = 0;
int cycle;
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
{
cycle = process_regexp_cycles (regexp->regexp.allof.regexps [i],
start_cycle);
if (finish_cycle < cycle)
finish_cycle = cycle;
}
return finish_cycle;
}
else if (regexp->mode == rm_oneof)
{
int finish_cycle = 0;
int cycle;
for (i = 0; i < regexp->regexp.oneof.regexps_num; i++)
{
cycle = process_regexp_cycles (regexp->regexp.oneof.regexps [i],
start_cycle);
if (finish_cycle < cycle)
finish_cycle = cycle;
}
return finish_cycle;
}
else
{
assert (regexp->mode == rm_nothing);
return start_cycle;
}
}
/* The following function is called only for correct program. The
function defines max reservation of insns in cycles. */
static void
evaluate_max_reserv_cycles ()
{
int max_insn_cycles_num;
struct decl *curr_decl;
int i;
description->max_insn_reserv_cycles = 0;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv)
{
max_insn_cycles_num
= process_regexp_cycles (curr_decl->decl.insn_reserv.regexp, 0);
if (description->max_insn_reserv_cycles < max_insn_cycles_num)
description->max_insn_reserv_cycles = max_insn_cycles_num;
}
}
}
/* The following function calls functions for checking all
description. */
static void
check_all_description ()
{
process_decls ();
check_automaton_usage ();
process_regexp_decls ();
check_usage ();
check_loops_in_regexps ();
if (!have_error)
evaluate_max_reserv_cycles ();
}
/* The page contains abstract data `ticker'. */
/* The following function creates ticker and makes it active. */
static ticker_t
create_ticker ()
{
ticker_t ticker;
ticker.modified_creation_time = get_run_time ();
ticker.incremented_off_time = 0;
return ticker;
}
/* The following function switches off given ticker. */
static void
ticker_off (ticker)
ticker_t *ticker;
{
if (ticker->incremented_off_time == 0)
ticker->incremented_off_time = get_run_time () + 1;
}
/* The following function switches on given ticker. */
static void
ticker_on (ticker)
ticker_t *ticker;
{
if (ticker->incremented_off_time != 0)
{
ticker->modified_creation_time
+= get_run_time () - ticker->incremented_off_time + 1;
ticker->incremented_off_time = 0;
}
}
/* The following function returns current time in milliseconds since
the moment when given ticker was created. */
static int
active_time (ticker)
ticker_t ticker;
{
if (ticker.incremented_off_time != 0)
return ticker.incremented_off_time - 1 - ticker.modified_creation_time;
else
return get_run_time () - ticker.modified_creation_time;
}
/* The following function returns string representation of active time
of given ticker. The result is string representation of seconds
with accuracy of 1/100 second. Only result of the last call of the
function exists. Therefore the following code is not correct
printf ("parser time: %s\ngeneration time: %s\n",
active_time_string (parser_ticker),
active_time_string (generation_ticker));
Correct code has to be the following
printf ("parser time: %s\n", active_time_string (parser_ticker));
printf ("generation time: %s\n",
active_time_string (generation_ticker));
*/
static void
print_active_time (f, ticker)
FILE *f;
ticker_t ticker;
{
int msecs;
msecs = active_time (ticker);
fprintf (f, "%d.%06d", msecs / 1000000, msecs % 1000000);
}
/* The following variable value is number of automaton which are
really being created. This value is defined on the base of
argument of option `-split'. If the variable has zero value the
number of automata is defined by the constructions `%automaton'.
This case occures when option `-split' is absent or has zero
argument. If constructions `define_automaton' is absent only one
automaton is created. */
static int automata_num;
/* The following variable values are times of
o transformation of regular expressions
o building NDFA (DFA if !ndfa_flag)
o NDFA -> DFA (simply the same automaton if !ndfa_flag)
o DFA minimization
o building insn equivalence classes
o all previous ones
o code output */
static ticker_t transform_time;
static ticker_t NDFA_time;
static ticker_t NDFA_to_DFA_time;
static ticker_t minimize_time;
static ticker_t equiv_time;
static ticker_t automaton_generation_time;
static ticker_t output_time;
/* The following variable values are times of
all checking
all generation
all pipeline hazard translator work */
static ticker_t check_time;
static ticker_t generation_time;
static ticker_t all_time;
/* Pseudo insn decl which denotes advancing cycle. */
static struct decl *advance_cycle_insn_decl;
static void
add_advance_cycle_insn_decl ()
{
advance_cycle_insn_decl = create_node (sizeof (struct decl));
advance_cycle_insn_decl->mode = dm_insn_reserv;
advance_cycle_insn_decl->pos = no_pos;
advance_cycle_insn_decl->decl.insn_reserv.regexp = NULL;
advance_cycle_insn_decl->decl.insn_reserv.name = (char *) "$advance_cycle";
advance_cycle_insn_decl->decl.insn_reserv.insn_num = description->insns_num;
description->decls [description->decls_num] = advance_cycle_insn_decl;
description->decls_num++;
description->insns_num++;
num_dfa_decls++;
}
/* Abstract data `alternative states' which reperesents
nondeterministic nature of the description (see comments for
structures alt_state and state). */
/* List of free states. */
static struct alt_state *first_free_alt_state;
#ifndef NDEBUG
/* The following variables is maximal number of allocated nodes
alt_state. */
static int allocated_alt_states_num = 0;
#endif
/* The following function returns free node alt_state. It may be new
allocated node or node freed eralier. */
static struct alt_state *
get_free_alt_state ()
{
struct alt_state *result;
if (first_free_alt_state != NULL)
{
result = first_free_alt_state;
first_free_alt_state = first_free_alt_state->next_alt_state;
}
else
{
#ifndef NDEBUG
allocated_alt_states_num++;
#endif
result = create_node (sizeof (struct alt_state));
}
result->state = NULL;
result->next_alt_state = NULL;
result->next_sorted_alt_state = NULL;
return result;
}
/* The function frees node ALT_STATE. */
static void
free_alt_state (alt_state)
struct alt_state *alt_state;
{
if (alt_state == NULL)
return;
alt_state->next_alt_state = first_free_alt_state;
first_free_alt_state = alt_state;
}
/* The function frees list started with node ALT_STATE_LIST. */
static void
free_alt_states (alt_states_list)
struct alt_state *alt_states_list;
{
struct alt_state *current_alt_state;
struct alt_state *next_alt_state;
for (current_alt_state = alt_states_list;
current_alt_state != NULL;
current_alt_state = next_alt_state)
{
next_alt_state = current_alt_state->next_alt_state;
free_alt_state (current_alt_state);
}
}
/* The function compares unique numbers of alt states. */
static int
alt_state_cmp (alt_state_ptr_1, alt_state_ptr_2)
const void *alt_state_ptr_1;
const void *alt_state_ptr_2;
{
if ((*(struct alt_state **) alt_state_ptr_1)->state->unique_num
== (*(struct alt_state **) alt_state_ptr_2)->state->unique_num)
return 0;
else if ((*(struct alt_state **) alt_state_ptr_1)->state->unique_num
< (*(struct alt_state **) alt_state_ptr_2)->state->unique_num)
return -1;
else
return 1;
}
/* The function sorts ALT_STATES_LIST and removes duplicated alt
states from the list. The comparison key is alt state unique
number. */
static struct alt_state *
uniq_sort_alt_states (alt_states_list)
struct alt_state *alt_states_list;
{
struct alt_state *curr_alt_state;
vla_ptr_t alt_states;
size_t curr_index;
size_t prev_unique_state_index;
struct alt_state *result;
struct alt_state **result_ptr;
VLA_PTR_CREATE (alt_states, 150, "alt_states");
for (curr_alt_state = alt_states_list;
curr_alt_state != NULL;
curr_alt_state = curr_alt_state->next_alt_state)
VLA_PTR_ADD (alt_states, curr_alt_state);
qsort (VLA_PTR_BEGIN (alt_states), VLA_PTR_LENGTH (alt_states),
sizeof (struct alt_state *), alt_state_cmp);
if (VLA_PTR_LENGTH (alt_states) == 0)
result = NULL;
else
{
result_ptr = VLA_PTR_BEGIN (alt_states);
for (prev_unique_state_index = 0, curr_index = 1;
curr_index < VLA_PTR_LENGTH (alt_states);
curr_index++)
if (result_ptr [prev_unique_state_index]->state
!= result_ptr [curr_index]->state)
{
prev_unique_state_index++;
result_ptr [prev_unique_state_index] = result_ptr [curr_index];
}
#if 0
for (curr_index = prev_unique_state_index + 1;
curr_index < VLA_PTR_LENGTH (alt_states);
curr_index++)
free_alt_state (result_ptr [curr_index]);
#endif
VLA_PTR_SHORTEN (alt_states, curr_index - prev_unique_state_index - 1);
result_ptr = VLA_PTR_BEGIN (alt_states);
for (curr_index = 1;
curr_index < VLA_PTR_LENGTH (alt_states);
curr_index++)
result_ptr [curr_index - 1]->next_sorted_alt_state
= result_ptr [curr_index];
result_ptr [curr_index - 1]->next_sorted_alt_state = NULL;
result = *result_ptr;
}
VLA_PTR_DELETE (alt_states);
return result;
}
/* The function checks equality of alt state lists. Remember that the
lists must be already sorted by the previous function. */
static int
alt_states_eq (alt_states_1, alt_states_2)
struct alt_state *alt_states_1;
struct alt_state *alt_states_2;
{
while (alt_states_1 != NULL && alt_states_2 != NULL
&& alt_state_cmp (&alt_states_1, &alt_states_2) == 0)
{
alt_states_1 = alt_states_1->next_sorted_alt_state;
alt_states_2 = alt_states_2->next_sorted_alt_state;
}
return alt_states_1 == alt_states_2;
}
/* Initialization of the abstract data. */
static void
initiate_alt_states ()
{
first_free_alt_state = NULL;
}
/* Finishing work with the abstract data. */
static void
finish_alt_states ()
{
}
/* The page contains macros for work with bits strings. */
/* Set bit number bitno in the bit string. The macro is not side
effect proof. */
#define SET_BIT(bitstring, bitno) \
(((char *) (bitstring)) [(bitno) / CHAR_BIT] |= 1 << (bitno) % CHAR_BIT)
/* Test if bit number bitno in the bitstring is set. The macro is not
side effect proof. */
#define TEST_BIT(bitstring, bitno) \
(((char *) (bitstring)) [(bitno) / CHAR_BIT] >> (bitno) % CHAR_BIT & 1)
/* This page contains abstract data `state'. */
/* Maximal length of reservations in cycles (> 1). */
static int max_cycles_num;
/* Number of set elements (see type set_el_t) needed for
representation of one cycle reservation. It is depended on units
number. */
static int els_in_cycle_reserv;
/* Number of set elements (see type set_el_t) needed for
representation of maximal length reservation. Deterministic
reservation is stored as set (bit string) of length equal to the
variable value * number of bits in set_el_t. */
static int els_in_reservs;
/* VLA for representation of array of pointers to unit
declarations. */
static vla_ptr_t units_container;
/* The start address of the array. */
static struct unit_decl **units_array;
/* Empty reservation of maximal length. */
static reserv_sets_t empty_reserv;
/* The state table itself is represented by the following variable. */
static htab_t state_table;
/* VLA for representation of array of pointers to free nodes
`state'. */
static vla_ptr_t free_states;
static int curr_unique_state_num;
#ifndef NDEBUG
/* The following variables is maximal number of allocated nodes
`state'. */
static int allocated_states_num = 0;
#endif
/* Allocate new reservation set. */
static reserv_sets_t
alloc_empty_reserv_sets ()
{
reserv_sets_t result;
IR_TOP_EXPAND (els_in_reservs * sizeof (set_el_t));
result = (reserv_sets_t) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
memset (result, 0, els_in_reservs * sizeof (set_el_t));
return result;
}
/* Hash value of reservation set. */
static unsigned
reserv_sets_hash_value (reservs)
reserv_sets_t reservs;
{
unsigned int hash_value;
int unit_reserv_set_els_num;
set_el_t *unit_reserv_set_el_ptr;
hash_value = 0;
unit_reserv_set_els_num = els_in_reservs;
unit_reserv_set_el_ptr = reservs;
while (unit_reserv_set_els_num != 0)
{
unit_reserv_set_els_num--;
hash_value = ((hash_value >> (sizeof (unsigned) - 1) * CHAR_BIT)
| (hash_value << CHAR_BIT)) + *unit_reserv_set_el_ptr;
unit_reserv_set_el_ptr++;
}
return hash_value;
}
/* Comparison of given reservation sets. */
static int
reserv_sets_cmp (reservs_1, reservs_2)
reserv_sets_t reservs_1;
reserv_sets_t reservs_2;
{
int unit_reserv_set_els_num;
set_el_t *unit_reserv_set_el_ptr_1;
set_el_t *unit_reserv_set_el_ptr_2;
assert (reservs_1 != NULL && reservs_2 != NULL);
unit_reserv_set_els_num = els_in_reservs;
unit_reserv_set_el_ptr_1 = reservs_1;
unit_reserv_set_el_ptr_2 = reservs_2;
while (unit_reserv_set_els_num != 0
&& *unit_reserv_set_el_ptr_1 == *unit_reserv_set_el_ptr_2)
{
unit_reserv_set_els_num--;
unit_reserv_set_el_ptr_1++;
unit_reserv_set_el_ptr_2++;
}
if (unit_reserv_set_els_num == 0)
return 0;
else if (*unit_reserv_set_el_ptr_1 < *unit_reserv_set_el_ptr_2)
return -1;
else
return 1;
}
/* The function checks equality of the reservation sets. */
static int
reserv_sets_eq (reservs_1, reservs_2)
reserv_sets_t reservs_1;
reserv_sets_t reservs_2;
{
return reserv_sets_cmp (reservs_1, reservs_2) == 0;
}
/* Set up in the reservation set that unit with UNIT_NUM is used on
CYCLE_NUM. */
static void
set_unit_reserv (reservs, cycle_num, unit_num)
reserv_sets_t reservs;
int cycle_num;
int unit_num;
{
assert (cycle_num < max_cycles_num);
SET_BIT (reservs, cycle_num * els_in_cycle_reserv
* sizeof (set_el_t) * CHAR_BIT + unit_num);
}
/* Set up in the reservation set RESERVS that unit with UNIT_NUM is
used on CYCLE_NUM. */
static int
test_unit_reserv (reservs, cycle_num, unit_num)
reserv_sets_t reservs;
int cycle_num;
int unit_num;
{
assert (cycle_num < max_cycles_num);
return TEST_BIT (reservs, cycle_num * els_in_cycle_reserv
* sizeof (set_el_t) * CHAR_BIT + unit_num);
}
/* The function checks that the reservation set represents no one unit
reservation. */
static int
it_is_empty_reserv_sets (operand)
reserv_sets_t operand;
{
set_el_t *unit_reserv_set_el_ptr;
int unit_reserv_set_els_num;
assert (operand != NULL);
for (unit_reserv_set_els_num = els_in_reservs,
unit_reserv_set_el_ptr = operand;
unit_reserv_set_els_num != 0;
unit_reserv_set_el_ptr++, unit_reserv_set_els_num--)
if (*unit_reserv_set_el_ptr != 0)
return FALSE;
return TRUE;
}
/* The function checks that the reservation sets are intersected,
i.e. there is a unit reservation on a cycle in both reservation
sets. */
static int
reserv_sets_are_intersected (operand_1, operand_2)
reserv_sets_t operand_1;
reserv_sets_t operand_2;
{
set_el_t *curr_unit_set_el_ptr_1;
set_el_t *curr_unit_set_el_ptr_2;
set_el_t *curr_cycle_ptr_1;
set_el_t *curr_cycle_ptr_2;
int nonzero_p;
assert (operand_1 != NULL && operand_2 != NULL);
for (curr_unit_set_el_ptr_1 = operand_1, curr_unit_set_el_ptr_2 = operand_2;
curr_unit_set_el_ptr_1 < operand_1 + els_in_reservs;
curr_unit_set_el_ptr_1++, curr_unit_set_el_ptr_2++)
if (*curr_unit_set_el_ptr_1 & *curr_unit_set_el_ptr_2)
return TRUE;
for (curr_cycle_ptr_1 = operand_1, curr_cycle_ptr_2 = operand_2;
curr_cycle_ptr_1 < operand_1 + els_in_reservs;
curr_cycle_ptr_1 += els_in_cycle_reserv,
curr_cycle_ptr_2 += els_in_cycle_reserv)
{
for (curr_unit_set_el_ptr_1 = curr_cycle_ptr_1,
curr_unit_set_el_ptr_2 = get_excl_set (curr_cycle_ptr_2);
curr_unit_set_el_ptr_1 < curr_cycle_ptr_1 + els_in_cycle_reserv;
curr_unit_set_el_ptr_1++, curr_unit_set_el_ptr_2++)
if (*curr_unit_set_el_ptr_1 & *curr_unit_set_el_ptr_2)
return TRUE;
nonzero_p = FALSE;
for (curr_unit_set_el_ptr_1 = curr_cycle_ptr_1,
curr_unit_set_el_ptr_2
= get_presence_absence_set (curr_cycle_ptr_2, TRUE);
curr_unit_set_el_ptr_1 < curr_cycle_ptr_1 + els_in_cycle_reserv;
curr_unit_set_el_ptr_1++, curr_unit_set_el_ptr_2++)
if (*curr_unit_set_el_ptr_1 & *curr_unit_set_el_ptr_2)
break;
else if (*curr_unit_set_el_ptr_2 != 0)
nonzero_p = TRUE;
if (nonzero_p
&& curr_unit_set_el_ptr_1 >= curr_cycle_ptr_1 + els_in_cycle_reserv)
return TRUE;
for (curr_unit_set_el_ptr_1 = curr_cycle_ptr_1,
curr_unit_set_el_ptr_2
= get_presence_absence_set (curr_cycle_ptr_2, FALSE);
curr_unit_set_el_ptr_1 < curr_cycle_ptr_1 + els_in_cycle_reserv;
curr_unit_set_el_ptr_1++, curr_unit_set_el_ptr_2++)
/* It looks like code for exclusion but exclusion set is
made as symmetric relation preliminary. */
if (*curr_unit_set_el_ptr_1 & *curr_unit_set_el_ptr_2)
return TRUE;
}
return FALSE;
}
/* The function sets up RESULT bits by bits of OPERAND shifted on one
cpu cycle. The remaining bits of OPERAND (representing the last
cycle unit reservations) are not chenged. */
static void
reserv_sets_shift (result, operand)
reserv_sets_t result;
reserv_sets_t operand;
{
int i;
assert (result != NULL && operand != NULL && result != operand);
for (i = els_in_cycle_reserv; i < els_in_reservs; i++)
result [i - els_in_cycle_reserv] = operand [i];
}
/* OR of the reservation sets. */
static void
reserv_sets_or (result, operand_1, operand_2)
reserv_sets_t result;
reserv_sets_t operand_1;
reserv_sets_t operand_2;
{
set_el_t *curr_unit_set_el_ptr_1;
set_el_t *curr_unit_set_el_ptr_2;
set_el_t *curr_result_unit_set_el_ptr;
assert (result != NULL && operand_1 != NULL && operand_2 != NULL);
for (curr_unit_set_el_ptr_1 = operand_1, curr_unit_set_el_ptr_2 = operand_2,
curr_result_unit_set_el_ptr = result;
curr_unit_set_el_ptr_1 < operand_1 + els_in_reservs;
curr_unit_set_el_ptr_1++, curr_unit_set_el_ptr_2++,
curr_result_unit_set_el_ptr++)
*curr_result_unit_set_el_ptr
= *curr_unit_set_el_ptr_1 | *curr_unit_set_el_ptr_2;
}
/* AND of the reservation sets. */
static void
reserv_sets_and (result, operand_1, operand_2)
reserv_sets_t result;
reserv_sets_t operand_1;
reserv_sets_t operand_2;
{
set_el_t *curr_unit_set_el_ptr_1;
set_el_t *curr_unit_set_el_ptr_2;
set_el_t *curr_result_unit_set_el_ptr;
assert (result != NULL && operand_1 != NULL && operand_2 != NULL);
for (curr_unit_set_el_ptr_1 = operand_1, curr_unit_set_el_ptr_2 = operand_2,
curr_result_unit_set_el_ptr = result;
curr_unit_set_el_ptr_1 < operand_1 + els_in_reservs;
curr_unit_set_el_ptr_1++, curr_unit_set_el_ptr_2++,
curr_result_unit_set_el_ptr++)
*curr_result_unit_set_el_ptr
= *curr_unit_set_el_ptr_1 & *curr_unit_set_el_ptr_2;
}
/* The function outputs string representation of units reservation on
cycle START_CYCLE in the reservation set. The function uses repeat
construction if REPETITION_NUM > 1. */
static void
output_cycle_reservs (f, reservs, start_cycle, repetition_num)
FILE *f;
reserv_sets_t reservs;
int start_cycle;
int repetition_num;
{
int curr_unit_num;
int reserved_units_num;
reserved_units_num = 0;
for (curr_unit_num = 0;
curr_unit_num < description->units_num;
curr_unit_num++)
if (TEST_BIT (reservs, start_cycle * els_in_cycle_reserv
* sizeof (set_el_t) * CHAR_BIT + curr_unit_num))
reserved_units_num++;
assert (repetition_num > 0);
if (repetition_num != 1 && reserved_units_num > 1)
fprintf (f, "(");
reserved_units_num = 0;
for (curr_unit_num = 0;
curr_unit_num < description->units_num;
curr_unit_num++)
if (TEST_BIT (reservs, start_cycle * els_in_cycle_reserv
* sizeof (set_el_t) * CHAR_BIT + curr_unit_num))
{
if (reserved_units_num != 0)
fprintf (f, "+");
reserved_units_num++;
fprintf (f, "%s", units_array [curr_unit_num]->name);
}
if (reserved_units_num == 0)
fprintf (f, NOTHING_NAME);
assert (repetition_num > 0);
if (reserved_units_num != 0 && repetition_num != 1)
{
if (reserved_units_num > 1)
fprintf (f, ")");
fprintf (f, "*%d", repetition_num);
}
}
/* The function outputs string representation of units reservation in
the reservation set. */
static void
output_reserv_sets (f, reservs)
FILE *f;
reserv_sets_t reservs;
{
int start_cycle;
int curr_cycle_num;
int repetition_num;
int next_cycle_output_flag;
repetition_num = 0;
next_cycle_output_flag = FALSE;
for (curr_cycle_num = 0; curr_cycle_num < max_cycles_num; curr_cycle_num++)
if (repetition_num == 0)
{
repetition_num++;
start_cycle = curr_cycle_num;
}
else if (memcmp
((char *) reservs + start_cycle * els_in_cycle_reserv
* sizeof (set_el_t),
(char *) reservs + curr_cycle_num * els_in_cycle_reserv
* sizeof (set_el_t), els_in_cycle_reserv * sizeof (set_el_t))
== 0)
repetition_num++;
else
{
if (next_cycle_output_flag)
fprintf (f, ", ");
output_cycle_reservs (f, reservs, start_cycle, repetition_num);
next_cycle_output_flag = TRUE;
repetition_num = 1;
start_cycle = curr_cycle_num;
}
if (!next_cycle_output_flag)
{
if (next_cycle_output_flag)
fprintf (f, ", ");
output_cycle_reservs (f, reservs, start_cycle, repetition_num);
}
}
/* The following function returns free node state for AUTOMATON. It
may be new allocated node or node freed eralier. The function also
allocates reservation set if WITH_RESERVS==TRUE. */
static struct state *
get_free_state (with_reservs, automaton)
int with_reservs;
struct automaton *automaton;
{
struct state *result;
assert (max_cycles_num > 0 && automaton != NULL);
if (VLA_PTR_LENGTH (free_states) != 0)
{
result = VLA_PTR (free_states, VLA_PTR_LENGTH (free_states) - 1);
VLA_PTR_SHORTEN (free_states, 1);
result->automaton = automaton;
result->first_out_arc = NULL;
result->it_was_placed_in_stack_for_NDFA_forming = FALSE;
result->it_was_placed_in_stack_for_DFA_forming = FALSE;
result->component_states = NULL;
}
else
{
#ifndef NDEBUG
allocated_states_num++;
#endif
result = create_node (sizeof (struct state));
result->automaton = automaton;
result->first_out_arc = NULL;
result->unique_num = curr_unique_state_num;
curr_unique_state_num++;
}
if (with_reservs)
{
if (result->reservs == NULL)
result->reservs = alloc_empty_reserv_sets ();
else
memset (result->reservs, 0, els_in_reservs * sizeof (set_el_t));
}
return result;
}
/* The function frees node STATE. */
static void
free_state (state)
struct state *state;
{
free_alt_states (state->component_states);
VLA_PTR_ADD (free_states, state);
}
/* Hash value of STATE. If STATE represents deterministic state it is
simply hash value of the corresponding reservation set. Otherwise
it is formed from hash values of the component deterministic
states. One more key is order number of state automaton. */
static unsigned
state_hash (state)
const void *state;
{
unsigned int hash_value;
struct alt_state *curr_alt_state;
if (((struct state *) state)->component_states == NULL)
hash_value = reserv_sets_hash_value (((struct state *) state)->reservs);
else
{
hash_value = 0;
for (curr_alt_state = ((struct state *) state)->component_states;
curr_alt_state != NULL;
curr_alt_state = curr_alt_state->next_sorted_alt_state)
hash_value = (((hash_value >> (sizeof (unsigned) - 1) * CHAR_BIT)
| (hash_value << CHAR_BIT))
+ curr_alt_state->state->unique_num);
}
hash_value = (((hash_value >> (sizeof (unsigned) - 1) * CHAR_BIT)
| (hash_value << CHAR_BIT))
+ ((struct state *) state)->automaton->automaton_order_num);
return hash_value;
}
/* Return true if the states are the same. */
static int
state_eq_p (state_1, state_2)
const void *state_1;
const void *state_2;
{
struct alt_state *curr_alt_state_1;
struct alt_state *curr_alt_state_2;
if (((struct state *) state_1)->automaton
!= ((struct state *) state_2)->automaton)
return FALSE;
else if (((struct state *) state_1)->component_states == NULL
&& ((struct state *) state_2)->component_states == NULL)
return reserv_sets_eq (((struct state *) state_1)->reservs,
((struct state *) state_2)->reservs);
else if (((struct state *) state_1)->component_states != NULL
&& ((struct state *) state_2)->component_states != NULL)
{
for (curr_alt_state_1 = ((struct state *) state_1)->component_states,
curr_alt_state_2 = ((struct state *) state_2)->component_states;
curr_alt_state_1 != NULL && curr_alt_state_2 != NULL;
curr_alt_state_1 = curr_alt_state_1->next_sorted_alt_state,
curr_alt_state_2 = curr_alt_state_2->next_sorted_alt_state)
/* All state in the list must be already in the hash table.
Also the lists must be sorted. */
if (curr_alt_state_1->state != curr_alt_state_2->state)
return FALSE;
return curr_alt_state_1 == curr_alt_state_2;
}
else
return FALSE;
}
/* Insert STATE into the state table. */
static struct state *
insert_state (state)
struct state *state;
{
void **entry_ptr;
entry_ptr = htab_find_slot (state_table, (void *) state, TRUE);
if (*entry_ptr == NULL)
*entry_ptr = (void *) state;
return (struct state *) *entry_ptr;
}
/* Add reservation of unit with UNIT_NUM on cycle CYCLE_NUM to
deterministic STATE. */
static void
set_state_reserv (state, cycle_num, unit_num)
struct state *state;
int cycle_num;
int unit_num;
{
set_unit_reserv (state->reservs, cycle_num, unit_num);
}
/* Return TRUE if the deterministic states contains a reservation of
the same cpu unit on the same cpu cycle. */
static int
intersected_state_reservs_p (state1, state2)
struct state *state1;
struct state *state2;
{
assert (state1->automaton == state2->automaton);
return reserv_sets_are_intersected (state1->reservs, state2->reservs);
}
/* Return deterministic state (inserted into the table) which
representing the automaton state whic is union of reservations of
deterministic states. */
static struct state *
states_union (state1, state2)
struct state *state1;
struct state *state2;
{
struct state *result;
struct state *state_in_table;
assert (state1->automaton == state2->automaton);
result = get_free_state (TRUE, state1->automaton);
reserv_sets_or (result->reservs, state1->reservs, state2->reservs);
state_in_table = insert_state (result);
if (result != state_in_table)
{
free_state (result);
result = state_in_table;
}
return result;
}
/* Return deterministic state (inserted into the table) which
represent the automaton state is obtained from deterministic STATE
by advancing cpu cycle. */
static struct state *
state_shift (state)
struct state *state;
{
struct state *result;
struct state *state_in_table;
result = get_free_state (TRUE, state->automaton);
reserv_sets_shift (result->reservs, state->reservs);
state_in_table = insert_state (result);
if (result != state_in_table)
{
free_state (result);
result = state_in_table;
}
return result;
}
/* Initialization of the abstract data. */
static void
initiate_states ()
{
struct decl *curr_decl;
int i;
VLA_PTR_CREATE (units_container, description->units_num, "units_container");
units_array = VLA_PTR_BEGIN (units_container);
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_unit)
units_array [curr_decl->decl.unit.unit_num] = &curr_decl->decl.unit;
}
max_cycles_num = description->max_insn_reserv_cycles;
if (max_cycles_num == 0)
max_cycles_num++;
els_in_cycle_reserv
= ((description->units_num + sizeof (set_el_t) * CHAR_BIT - 1)
/ (sizeof (set_el_t) * CHAR_BIT));
els_in_reservs = els_in_cycle_reserv * max_cycles_num;
curr_unique_state_num = 0;
initiate_alt_states ();
VLA_PTR_CREATE (free_states, 1500, "free states");
state_table = htab_create (1500, state_hash, state_eq_p, (htab_del) 0);
empty_reserv = alloc_empty_reserv_sets ();
}
/* Finisging work with the abstract data. */
static void
finish_states ()
{
VLA_PTR_DELETE (units_container);
htab_delete (state_table);
VLA_PTR_DELETE (free_states);
finish_alt_states ();
}
/* Abstract data `arcs'. */
/* List of free arcs. */
static struct arc *first_free_arc;
#ifndef NDEBUG
/* The following variables is maximal number of allocated nodes
`arc'. */
static int allocated_arcs_num = 0;
#endif
/* The function frees node ARC. */
static void
free_arc (arc)
struct arc *arc;
{
arc->next_out_arc = first_free_arc;
first_free_arc = arc;
}
/* The function removes and frees ARC staring from FROM_STATE. */
static void
remove_arc (from_state, arc)
struct state *from_state;
struct arc *arc;
{
struct arc *prev_arc;
struct arc *curr_arc;
assert (arc != NULL);
for (prev_arc = NULL, curr_arc = from_state->first_out_arc;
curr_arc != NULL;
prev_arc = curr_arc, curr_arc = curr_arc->next_out_arc)
if (curr_arc == arc)
break;
assert (curr_arc != NULL);
if (prev_arc == NULL)
from_state->first_out_arc = arc->next_out_arc;
else
prev_arc->next_out_arc = arc->next_out_arc;
free_arc (arc);
}
/* The functions returns arc with given characteristics (or NULL if
the arc does not exist). */
static struct arc *
find_arc (from_state, to_state, insn)
struct state *from_state;
struct state *to_state;
struct ainsn *insn;
{
struct arc *curr_arc;
for (curr_arc = first_out_arc (from_state);
curr_arc != NULL;
curr_arc = next_out_arc (curr_arc))
{
if (curr_arc->to_state == to_state && curr_arc->insn == insn)
return curr_arc;
}
return NULL;
}
/* The function adds arc from FROM_STATE to TO_STATE marked by AINSN
and with given STATE_ALTS. The function returns added arc (or
already existing arc). */
static struct arc *
add_arc (from_state, to_state, ainsn, state_alts)
struct state *from_state;
struct state *to_state;
struct ainsn *ainsn;
int state_alts;
{
struct arc *new_arc;
new_arc = find_arc (from_state, to_state, ainsn);
if (new_arc != NULL)
return new_arc;
if (first_free_arc == NULL)
{
#ifndef NDEBUG
allocated_arcs_num++;
#endif
new_arc = create_node (sizeof (struct arc));
new_arc->to_state = NULL;
new_arc->insn = NULL;
new_arc->next_out_arc = NULL;
}
else
{
new_arc = first_free_arc;
first_free_arc = first_free_arc->next_out_arc;
}
new_arc->to_state = to_state;
new_arc->insn = ainsn;
ainsn->arc_exists_p = TRUE;
new_arc->next_out_arc = from_state->first_out_arc;
from_state->first_out_arc = new_arc;
new_arc->next_arc_marked_by_insn = NULL;
new_arc->state_alts = state_alts;
return new_arc;
}
/* The function returns the first arc starting from STATE. */
static struct arc *
first_out_arc (state)
struct state *state;
{
return state->first_out_arc;
}
/* The function returns next out arc after ARC. */
static struct arc *
next_out_arc (arc)
struct arc *arc;
{
return arc->next_out_arc;
}
/* Initialization of the abstract data. */
static void
initiate_arcs ()
{
first_free_arc = NULL;
}
/* Finishing work with the abstract data. */
static void
finish_arcs ()
{
}
/* The page contains abstract data for work with exclusion sets (see
exclusion_set in file rtl.def). */
/* The following variable refers to an exclusion set returned by
get_excl_set. This is bit string of length equal to cpu units
number. If exclusion set for given unit contains 1 for a unit,
then simultaneous reservation of the units is prohibited. */
static reserv_sets_t excl_set;
/* The array contains exclusion sets for each unit. */
static reserv_sets_t *unit_excl_set_table;
/* The following function forms the array containing exclusion sets
for each unit. */
static void
initiate_excl_sets ()
{
struct decl *curr_decl;
reserv_sets_t unit_excl_set;
struct unit_set_el *curr_unit_set_el;
int i;
IR_TOP_EXPAND (els_in_cycle_reserv * sizeof (set_el_t));
excl_set = (reserv_sets_t) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
IR_TOP_EXPAND (description->units_num * sizeof (reserv_sets_t));
unit_excl_set_table = (reserv_sets_t *) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
/* Evaluate unit exclusion sets. */
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_unit)
{
IR_TOP_EXPAND (els_in_cycle_reserv * sizeof (set_el_t));
unit_excl_set = (reserv_sets_t) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
memset (unit_excl_set, 0, els_in_cycle_reserv * sizeof (set_el_t));
for (curr_unit_set_el = curr_decl->decl.unit.excl_list;
curr_unit_set_el != NULL;
curr_unit_set_el = curr_unit_set_el->next_unit_set_el)
SET_BIT (unit_excl_set, curr_unit_set_el->unit_decl->unit_num);
unit_excl_set_table [curr_decl->decl.unit.unit_num] = unit_excl_set;
}
}
}
/* The function sets up and return EXCL_SET which is union of
exclusion sets for each unit in IN_SET. */
static reserv_sets_t
get_excl_set (in_set)
reserv_sets_t in_set;
{
int excl_char_num;
int chars_num;
int i;
int unit_num;
int curr_unit_num;
chars_num = els_in_cycle_reserv * sizeof (set_el_t);
memset (excl_set, 0, chars_num);
for (excl_char_num = 0; excl_char_num < chars_num; excl_char_num++)
if (((unsigned char *) in_set) [excl_char_num])
for (i = CHAR_BIT - 1; i >= 0; i--)
if ((((unsigned char *) in_set) [excl_char_num] >> i) & 1)
{
unit_num = excl_char_num * CHAR_BIT + i;
if (unit_num >= description->units_num)
return excl_set;
for (curr_unit_num = 0;
curr_unit_num < els_in_cycle_reserv;
curr_unit_num++)
{
excl_set [curr_unit_num]
|= unit_excl_set_table [unit_num] [curr_unit_num];
}
}
return excl_set;
}
/* The page contains abstract data for work with presence/absence sets
(see presence_set/absence_set in file rtl.def). */
/* The following variables refer to correspondingly an presence and an
absence set returned by get_presence_absence_set. This is bit
string of length equal to cpu units number. */
static reserv_sets_t presence_set, absence_set;
/* The following arrays contain correspondingly presence and absence
sets for each unit. */
static reserv_sets_t *unit_presence_set_table, *unit_absence_set_table;
/* The following function forms the array containing presence and
absence sets for each unit */
static void
initiate_presence_absence_sets ()
{
struct decl *curr_decl;
reserv_sets_t unit_presence_set, unit_absence_set;
struct unit_set_el *curr_unit_set_el;
int i;
IR_TOP_EXPAND (els_in_cycle_reserv * sizeof (set_el_t));
presence_set = (reserv_sets_t) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
IR_TOP_EXPAND (description->units_num * sizeof (reserv_sets_t));
unit_presence_set_table = (reserv_sets_t *) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
IR_TOP_EXPAND (els_in_cycle_reserv * sizeof (set_el_t));
absence_set = (reserv_sets_t) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
IR_TOP_EXPAND (description->units_num * sizeof (reserv_sets_t));
unit_absence_set_table = (reserv_sets_t *) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
/* Evaluate unit presence/absence sets. */
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_unit)
{
IR_TOP_EXPAND (els_in_cycle_reserv * sizeof (set_el_t));
unit_presence_set = (reserv_sets_t) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
memset (unit_presence_set, 0,
els_in_cycle_reserv * sizeof (set_el_t));
for (curr_unit_set_el = curr_decl->decl.unit.presence_list;
curr_unit_set_el != NULL;
curr_unit_set_el = curr_unit_set_el->next_unit_set_el)
SET_BIT (unit_presence_set, curr_unit_set_el->unit_decl->unit_num);
unit_presence_set_table [curr_decl->decl.unit.unit_num]
= unit_presence_set;
IR_TOP_EXPAND (els_in_cycle_reserv * sizeof (set_el_t));
unit_absence_set = (reserv_sets_t) IR_TOP_BEGIN ();
IR_TOP_FINISH ();
memset (unit_absence_set, 0,
els_in_cycle_reserv * sizeof (set_el_t));
for (curr_unit_set_el = curr_decl->decl.unit.absence_list;
curr_unit_set_el != NULL;
curr_unit_set_el = curr_unit_set_el->next_unit_set_el)
SET_BIT (unit_absence_set, curr_unit_set_el->unit_decl->unit_num);
unit_absence_set_table [curr_decl->decl.unit.unit_num]
= unit_absence_set;
}
}
}
/* The function sets up and return PRESENCE_SET (if PRESENCE_P) or
ABSENCE_SET which is union of corresponding sets for each unit in
IN_SET. */
static reserv_sets_t
get_presence_absence_set (in_set, presence_p)
reserv_sets_t in_set;
int presence_p;
{
int char_num;
int chars_num;
int i;
int unit_num;
int curr_unit_num;
chars_num = els_in_cycle_reserv * sizeof (set_el_t);
if (presence_p)
memset (presence_set, 0, chars_num);
else
memset (absence_set, 0, chars_num);
for (char_num = 0; char_num < chars_num; char_num++)
if (((unsigned char *) in_set) [char_num])
for (i = CHAR_BIT - 1; i >= 0; i--)
if ((((unsigned char *) in_set) [char_num] >> i) & 1)
{
unit_num = char_num * CHAR_BIT + i;
if (unit_num >= description->units_num)
return (presence_p ? presence_set : absence_set);
for (curr_unit_num = 0;
curr_unit_num < els_in_cycle_reserv;
curr_unit_num++)
if (presence_p)
presence_set [curr_unit_num]
|= unit_presence_set_table [unit_num] [curr_unit_num];
else
absence_set [curr_unit_num]
|= unit_absence_set_table [unit_num] [curr_unit_num];
}
return (presence_p ? presence_set : absence_set);
}
/* This page contains code for transformation of original reservations
described in .md file. The main goal of transformations is
simplifying reservation and lifting up all `|' on the top of IR
reservation representation. */
/* The following function makes copy of IR representation of
reservation. The function also substitutes all reservations
defined by define_reservation by corresponding value during making
the copy. */
static struct regexp *
copy_insn_regexp (regexp)
struct regexp *regexp;
{
struct regexp * result;
int i;
if (regexp->mode == rm_reserv)
result = copy_insn_regexp (regexp->regexp.reserv.reserv_decl->regexp);
else if (regexp->mode == rm_unit)
result = copy_node (regexp, sizeof (struct regexp));
else if (regexp->mode == rm_repeat)
{
result = copy_node (regexp, sizeof (struct regexp));
result->regexp.repeat.regexp
= copy_insn_regexp (regexp->regexp.repeat.regexp);
}
else if (regexp->mode == rm_sequence)
{
result = copy_node (regexp,
sizeof (struct regexp) + sizeof (struct regexp *)
* (regexp->regexp.sequence.regexps_num - 1));
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
result->regexp.sequence.regexps [i]
= copy_insn_regexp (regexp->regexp.sequence.regexps [i]);
}
else if (regexp->mode == rm_allof)
{
result = copy_node (regexp,
sizeof (struct regexp) + sizeof (struct regexp *)
* (regexp->regexp.allof.regexps_num - 1));
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
result->regexp.allof.regexps [i]
= copy_insn_regexp (regexp->regexp.allof.regexps [i]);
}
else if (regexp->mode == rm_oneof)
{
result = copy_node (regexp,
sizeof (struct regexp) + sizeof (struct regexp *)
* (regexp->regexp.oneof.regexps_num - 1));
for (i = 0; i < regexp->regexp.oneof.regexps_num; i++)
result->regexp.oneof.regexps [i]
= copy_insn_regexp (regexp->regexp.oneof.regexps [i]);
}
else
{
assert (regexp->mode == rm_nothing);
result = copy_node (regexp, sizeof (struct regexp));
}
return result;
}
/* The following variable is set up TRUE if a transformation has been
applied. */
static int regexp_transformed_p;
/* The function makes transformation
A*N -> A, A, ... */
static struct regexp *
transform_1 (regexp)
struct regexp *regexp;
{
int curr_regexp_num;
int repeat_num;
struct regexp *operand;
pos_t pos;
if (regexp->mode == rm_repeat)
{
repeat_num = regexp->regexp.repeat.repeat_num;
assert (repeat_num > 1);
operand = regexp->regexp.repeat.regexp;
pos = regexp->mode;
regexp = create_node (sizeof (struct regexp) + sizeof (struct regexp *)
* (repeat_num - 1));
regexp->mode = rm_sequence;
regexp->pos = pos;
regexp->regexp.sequence.regexps_num = repeat_num;
for (curr_regexp_num = 0;
curr_regexp_num < repeat_num;
curr_regexp_num++)
regexp->regexp.sequence.regexps [curr_regexp_num]
= copy_insn_regexp (operand);
regexp_transformed_p = TRUE;
}
return regexp;
}
/* The function makes transformations
...,(A,B,...),C,... -> ...,A,B,...,C,...
...+(A+B+...)+C+... -> ...+A+B+...+C+...
...|(A|B|...)|C|... -> ...|A|B|...|C|... */
static struct regexp *
transform_2 (regexp)
struct regexp *regexp;
{
if (regexp->mode == rm_sequence)
{
struct regexp *sequence;
struct regexp *result;
int sequence_index;
int i, j;
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
if (regexp->regexp.sequence.regexps [i]->mode == rm_sequence)
{
sequence_index = i;
sequence = regexp->regexp.sequence.regexps [i];
break;
}
if (i < regexp->regexp.sequence.regexps_num)
{
assert (sequence->regexp.sequence.regexps_num > 1
&& regexp->regexp.sequence.regexps_num > 1);
result = create_node (sizeof (struct regexp)
+ sizeof (struct regexp *)
* (regexp->regexp.sequence.regexps_num
+ sequence->regexp.sequence.regexps_num
- 2));
result->mode = rm_sequence;
result->pos = regexp->pos;
result->regexp.sequence.regexps_num
= (regexp->regexp.sequence.regexps_num
+ sequence->regexp.sequence.regexps_num - 1);
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
if (i < sequence_index)
result->regexp.sequence.regexps [i]
= copy_insn_regexp (regexp->regexp.sequence.regexps [i]);
else if (i > sequence_index)
result->regexp.sequence.regexps
[i + sequence->regexp.sequence.regexps_num - 1]
= copy_insn_regexp (regexp->regexp.sequence.regexps [i]);
else
for (j = 0; j < sequence->regexp.sequence.regexps_num; j++)
result->regexp.sequence.regexps [i + j]
= copy_insn_regexp (sequence->regexp.sequence.regexps [j]);
regexp_transformed_p = TRUE;
regexp = result;
}
}
else if (regexp->mode == rm_allof)
{
struct regexp *allof;
struct regexp *result;
int allof_index;
int i, j;
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
if (regexp->regexp.allof.regexps [i]->mode == rm_allof)
{
allof_index = i;
allof = regexp->regexp.allof.regexps [i];
break;
}
if (i < regexp->regexp.allof.regexps_num)
{
assert (allof->regexp.allof.regexps_num > 1
&& regexp->regexp.allof.regexps_num > 1);
result = create_node (sizeof (struct regexp)
+ sizeof (struct regexp *)
* (regexp->regexp.allof.regexps_num
+ allof->regexp.allof.regexps_num - 2));
result->mode = rm_allof;
result->pos = regexp->pos;
result->regexp.allof.regexps_num
= (regexp->regexp.allof.regexps_num
+ allof->regexp.allof.regexps_num - 1);
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
if (i < allof_index)
result->regexp.allof.regexps [i]
= copy_insn_regexp (regexp->regexp.allof.regexps [i]);
else if (i > allof_index)
result->regexp.allof.regexps
[i + allof->regexp.allof.regexps_num - 1]
= copy_insn_regexp (regexp->regexp.allof.regexps [i]);
else
for (j = 0; j < allof->regexp.allof.regexps_num; j++)
result->regexp.allof.regexps [i + j]
= copy_insn_regexp (allof->regexp.allof.regexps [j]);
regexp_transformed_p = TRUE;
regexp = result;
}
}
else if (regexp->mode == rm_oneof)
{
struct regexp *oneof;
struct regexp *result;
int oneof_index;
int i, j;
for (i = 0; i < regexp->regexp.oneof.regexps_num; i++)
if (regexp->regexp.oneof.regexps [i]->mode == rm_oneof)
{
oneof_index = i;
oneof = regexp->regexp.oneof.regexps [i];
break;
}
if (i < regexp->regexp.oneof.regexps_num)
{
assert (oneof->regexp.oneof.regexps_num > 1
&& regexp->regexp.oneof.regexps_num > 1);
result = create_node (sizeof (struct regexp)
+ sizeof (struct regexp *)
* (regexp->regexp.oneof.regexps_num
+ oneof->regexp.oneof.regexps_num - 2));
result->mode = rm_oneof;
result->pos = regexp->pos;
result->regexp.oneof.regexps_num
= (regexp->regexp.oneof.regexps_num
+ oneof->regexp.oneof.regexps_num - 1);
for (i = 0; i < regexp->regexp.oneof.regexps_num; i++)
if (i < oneof_index)
result->regexp.oneof.regexps [i]
= copy_insn_regexp (regexp->regexp.oneof.regexps [i]);
else if (i > oneof_index)
result->regexp.oneof.regexps
[i + oneof->regexp.oneof.regexps_num - 1]
= copy_insn_regexp (regexp->regexp.oneof.regexps [i]);
else
for (j = 0; j < oneof->regexp.oneof.regexps_num; j++)
result->regexp.oneof.regexps [i + j]
= copy_insn_regexp (oneof->regexp.oneof.regexps [j]);
regexp_transformed_p = TRUE;
regexp = result;
}
}
return regexp;
}
/* The function makes transformations
...,A|B|...,C,... -> (...,A,C,...)|(...,B,C,...)|...
...+(A|B|...)+C+... -> (...+A+C+...)|(...+B+C+...)|... */
static struct regexp *
transform_3 (regexp)
struct regexp *regexp;
{
if (regexp->mode == rm_sequence)
{
struct regexp *oneof;
int oneof_index;
struct regexp *result;
struct regexp *sequence;
int i, j;
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
if (regexp->regexp.sequence.regexps [i]->mode == rm_oneof)
{
oneof_index = i;
oneof = regexp->regexp.sequence.regexps [i];
break;
}
if (i < regexp->regexp.sequence.regexps_num)
{
assert (oneof->regexp.oneof.regexps_num > 1
&& regexp->regexp.sequence.regexps_num > 1);
result = create_node (sizeof (struct regexp)
+ sizeof (struct regexp *)
* (oneof->regexp.oneof.regexps_num - 1));
result->mode = rm_oneof;
result->pos = regexp->pos;
result->regexp.oneof.regexps_num = oneof->regexp.oneof.regexps_num;
for (i = 0; i < result->regexp.oneof.regexps_num; i++)
{
sequence
= create_node (sizeof (struct regexp)
+ sizeof (struct regexp *)
* (regexp->regexp.sequence.regexps_num - 1));
sequence->mode = rm_sequence;
sequence->pos = regexp->pos;
sequence->regexp.sequence.regexps_num
= regexp->regexp.sequence.regexps_num;
result->regexp.oneof.regexps [i] = sequence;
for (j = 0; j < sequence->regexp.sequence.regexps_num; j++)
if (j != oneof_index)
sequence->regexp.sequence.regexps [j]
= copy_insn_regexp (regexp->regexp.sequence.regexps [j]);
else
sequence->regexp.sequence.regexps [j]
= copy_insn_regexp (oneof->regexp.oneof.regexps [i]);
}
regexp_transformed_p = TRUE;
regexp = result;
}
}
else if (regexp->mode == rm_allof)
{
struct regexp *oneof;
int oneof_index;
struct regexp *result;
struct regexp *allof;
int i, j;
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
if (regexp->regexp.allof.regexps [i]->mode == rm_oneof)
{
oneof_index = i;
oneof = regexp->regexp.allof.regexps [i];
break;
}
if (i < regexp->regexp.allof.regexps_num)
{
assert (oneof->regexp.oneof.regexps_num > 1
&& regexp->regexp.allof.regexps_num > 1);
result = create_node (sizeof (struct regexp)
+ sizeof (struct regexp *)
* (oneof->regexp.oneof.regexps_num - 1));
result->mode = rm_oneof;
result->pos = regexp->pos;
result->regexp.oneof.regexps_num = oneof->regexp.oneof.regexps_num;
for (i = 0; i < result->regexp.oneof.regexps_num; i++)
{
allof
= create_node (sizeof (struct regexp)
+ sizeof (struct regexp *)
* (regexp->regexp.allof.regexps_num - 1));
allof->mode = rm_allof;
allof->pos = regexp->pos;
allof->regexp.allof.regexps_num
= regexp->regexp.allof.regexps_num;
result->regexp.oneof.regexps [i] = allof;
for (j = 0; j < allof->regexp.allof.regexps_num; j++)
if (j != oneof_index)
allof->regexp.allof.regexps [j]
= copy_insn_regexp (regexp->regexp.allof.regexps [j]);
else
allof->regexp.allof.regexps [j]
= copy_insn_regexp (oneof->regexp.oneof.regexps [i]);
}
regexp_transformed_p = TRUE;
regexp = result;
}
}
return regexp;
}
/* The function traverses IR of reservation and applies transformations
implemented by FUNC. */
static struct regexp *
regexp_transform_func (regexp, func)
struct regexp *regexp;
struct regexp *(*func) PARAMS ((struct regexp *regexp));
{
int i;
if (regexp->mode == rm_sequence)
for (i = 0; i < regexp->regexp.sequence.regexps_num; i++)
regexp->regexp.sequence.regexps [i]
= regexp_transform_func (regexp->regexp.sequence.regexps [i], func);
else if (regexp->mode == rm_allof)
for (i = 0; i < regexp->regexp.allof.regexps_num; i++)
regexp->regexp.allof.regexps [i]
= regexp_transform_func (regexp->regexp.allof.regexps [i], func);
else if (regexp->mode == rm_oneof)
for (i = 0; i < regexp->regexp.oneof.regexps_num; i++)
regexp->regexp.oneof.regexps [i]
= regexp_transform_func (regexp->regexp.oneof.regexps [i], func);
else if (regexp->mode == rm_repeat)
regexp->regexp.repeat.regexp
= regexp_transform_func (regexp->regexp.repeat.regexp, func);
else
assert (regexp->mode == rm_nothing || regexp->mode == rm_unit);
return (*func) (regexp);
}
/* The function applies all transformations for IR representation of
reservation REGEXP. */
static struct regexp *
transform_regexp (regexp)
struct regexp *regexp;
{
regexp = regexp_transform_func (regexp, transform_1);
do
{
regexp_transformed_p = FALSE;
regexp = regexp_transform_func (regexp, transform_2);
regexp = regexp_transform_func (regexp, transform_3);
}
while (regexp_transformed_p);
return regexp;
}
/* The function applys all transformations for reservations of all
insn declarations. */
static void
transform_insn_regexps ()
{
struct decl *curr_decl;
int i;
for (i = 0; i < description->decls_num; i++)
{
curr_decl = description->decls [i];
if (curr_decl->mode == dm_insn_reserv
&& curr_decl != advance_cycle_insn_decl)
curr_decl->decl.insn_reserv.transformed_regexp
= transform_regexp (copy_insn_regexp
(curr_decl->decl.insn_reserv.regexp));
}
}
More information about the Gcc-patches
mailing list