blob: b68c63c60b51be980e535ee4fb43bf5aa8e718ec [file] [log] [blame]
/* Pipeline hazard description translator.
Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
Written by Vladimir Makarov <vmakarov@redhat.com>
This file is part of GCC.
GCC 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.
GCC 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 GCC; see the file COPYING. If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
/* References:
1. Detecting pipeline structural hazards quickly. T. Proebsting,
C. Fraser. Proceedings of ACM SIGPLAN-SIGACT Symposium on
Principles of Programming Languages, pages 280--286, 1994.
This article is a good start point to understand usage of finite
state automata for pipeline hazard recognizers. But I'd
recommend the 2nd article for more deep understanding.
2. Efficient Instruction Scheduling Using Finite State Automata:
V. Bala and N. Rubin, Proceedings of MICRO-28. This is the best
article about usage of finite state automata for pipeline hazard
recognizers.
The current implementation is different from the 2nd article in the
following:
1. New operator `|' (alternative) is permitted in functional unit
reservation which can be treated deterministically and
non-deterministically.
2. Possibility of usage of nondeterministic automata too.
3. Possibility to query functional unit reservations for given
automaton state.
4. Several constructions to describe impossible reservations
(`exclusion_set', `presence_set', `final_presence_set',
`absence_set', and `final_absence_set').
5. No reverse automata are generated. Trace instruction scheduling
requires this. It can be easily added in the future if we
really need this.
6. Union of automaton states are not generated yet. It is planned
to be implemented. Such feature is needed to make more accurate
interlock insn scheduling to get state describing functional
unit reservation in a joint CFG point. */
/* This file code processes constructions of machine description file
which describes automaton used for recognition of processor pipeline
hazards by insn scheduler and can be used for other tasks (such as
VLIW insn packing.
The translator functions `gen_cpu_unit', `gen_query_cpu_unit',
`gen_bypass', `gen_excl_set', `gen_presence_set',
`gen_final_presence_set', `gen_absence_set',
`gen_final_absence_set', `gen_automaton', `gen_automata_option',
`gen_reserv', `gen_insn_reserv' are called from file
`genattrtab.c'. They transform RTL constructions describing
automata in .md file into internal representation convenient for
further processing.
The translator major function `expand_automata' processes the
description internal representation into finite state automaton.
It can be divided on:
o checking correctness of the automaton pipeline description
(major function is `check_all_description').
o generating automaton (automata) from the description (major
function is `make_automaton').
o optional transformation of nondeterministic finite state
automata into deterministic ones if the alternative operator
`|' is treated nondeterministically in the description (major
function is NDFA_to_DFA).
o optional minimization of the finite state automata by merging
equivalent automaton states (major function is `minimize_DFA').
o forming tables (some as comb vectors) and attributes
representing the automata (functions output_..._table).
Function `write_automata' outputs the created finite state
automaton as different tables and functions which works with the
automata to inquire automaton state and to change its state. These
function are used by gcc instruction scheduler and may be some
other gcc code. */
#include "bconfig.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "obstack.h"
#include "errors.h"
#include <math.h>
#include "hashtab.h"
#include "varray.h"
#ifndef CHAR_BIT
#define CHAR_BIT 8
#endif
#include "genattrtab.h"
/* Positions in machine description file. Now they are not used. But
they could be used in the future for better diagnostic messages. */
typedef int pos_t;
/* The following is element of vector of current (and planned in the
future) functional unit reservations. */
typedef unsigned HOST_WIDE_INT set_el_t;
/* Reservations of function units are represented by value of the following
type. */
typedef set_el_t *reserv_sets_t;
/* The following structure represents variable length array (vla) of
pointers and HOST WIDE INTs. 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. */
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_pattern_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 pattern_set_el;
struct pattern_reserv;
struct state;
struct alt_state;
struct arc;
struct ainsn;
struct automaton;
struct state_ainsn_table;
/* The following typedefs are for brevity. */
typedef struct unit_decl *unit_decl_t;
typedef struct decl *decl_t;
typedef struct regexp *regexp_t;
typedef struct unit_set_el *unit_set_el_t;
typedef struct pattern_set_el *pattern_set_el_t;
typedef struct pattern_reserv *pattern_reserv_t;
typedef struct alt_state *alt_state_t;
typedef struct state *state_t;
typedef struct arc *arc_t;
typedef struct ainsn *ainsn_t;
typedef struct automaton *automaton_t;
typedef struct automata_list_el *automata_list_el_t;
typedef struct state_ainsn_table *state_ainsn_table_t;
/* Prototypes of functions gen_cpu_unit, gen_query_cpu_unit,
gen_bypass, gen_excl_set, gen_presence_set, gen_final_presence_set,
gen_absence_set, gen_final_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 (size_t);
static void *copy_node (const void *, size_t);
static char *check_name (char *, pos_t);
static char *next_sep_el (char **, int, int);
static int n_sep_els (char *, int, int);
static char **get_str_vect (char *, int *, int, int);
static void gen_presence_absence_set (rtx, int, int);
static regexp_t gen_regexp_el (char *);
static regexp_t gen_regexp_repeat (char *);
static regexp_t gen_regexp_allof (char *);
static regexp_t gen_regexp_oneof (char *);
static regexp_t gen_regexp_sequence (char *);
static regexp_t gen_regexp (char *);
static unsigned string_hash (const char *);
static unsigned automaton_decl_hash (const void *);
static int automaton_decl_eq_p (const void *,
const void *);
static decl_t insert_automaton_decl (decl_t);
static decl_t find_automaton_decl (char *);
static void initiate_automaton_decl_table (void);
static void finish_automaton_decl_table (void);
static hashval_t insn_decl_hash (const void *);
static int insn_decl_eq_p (const void *,
const void *);
static decl_t insert_insn_decl (decl_t);
static decl_t find_insn_decl (char *);
static void initiate_insn_decl_table (void);
static void finish_insn_decl_table (void);
static hashval_t decl_hash (const void *);
static int decl_eq_p (const void *,
const void *);
static decl_t insert_decl (decl_t);
static decl_t find_decl (char *);
static void initiate_decl_table (void);
static void finish_decl_table (void);
static unit_set_el_t process_excls (char **, int, pos_t);
static void add_excls (unit_set_el_t, unit_set_el_t,
pos_t);
static unit_set_el_t process_presence_absence_names
(char **, int, pos_t,
int, int);
static pattern_set_el_t process_presence_absence_patterns
(char ***, int, pos_t,
int, int);
static void add_presence_absence (unit_set_el_t,
pattern_set_el_t,
pos_t, int, int);
static void process_decls (void);
static struct bypass_decl *find_bypass (struct bypass_decl *,
struct insn_reserv_decl *);
static void check_automaton_usage (void);
static regexp_t process_regexp (regexp_t);
static void process_regexp_decls (void);
static void check_usage (void);
static int loop_in_regexp (regexp_t, decl_t);
static void check_loops_in_regexps (void);
static void process_regexp_cycles (regexp_t, int, int,
int *, int *);
static void evaluate_max_reserv_cycles (void);
static void check_all_description (void);
static ticker_t create_ticker (void);
static void ticker_off (ticker_t *);
static void ticker_on (ticker_t *);
static int active_time (ticker_t);
static void print_active_time (FILE *, ticker_t);
static void add_advance_cycle_insn_decl (void);
static alt_state_t get_free_alt_state (void);
static void free_alt_state (alt_state_t);
static void free_alt_states (alt_state_t);
static int alt_state_cmp (const void *alt_state_ptr_1,
const void *alt_state_ptr_2);
static alt_state_t uniq_sort_alt_states (alt_state_t);
static int alt_states_eq (alt_state_t, alt_state_t);
static void initiate_alt_states (void);
static void finish_alt_states (void);
static reserv_sets_t alloc_empty_reserv_sets (void);
static unsigned reserv_sets_hash_value (reserv_sets_t);
static int reserv_sets_cmp (reserv_sets_t, reserv_sets_t);
static int reserv_sets_eq (reserv_sets_t, reserv_sets_t);
static void set_unit_reserv (reserv_sets_t, int, int);
static int test_unit_reserv (reserv_sets_t, int, int);
static int it_is_empty_reserv_sets (reserv_sets_t)
ATTRIBUTE_UNUSED;
static int reserv_sets_are_intersected (reserv_sets_t, reserv_sets_t);
static void reserv_sets_shift (reserv_sets_t, reserv_sets_t);
static void reserv_sets_or (reserv_sets_t, reserv_sets_t,
reserv_sets_t);
static void reserv_sets_and (reserv_sets_t, reserv_sets_t,
reserv_sets_t)
ATTRIBUTE_UNUSED;
static void output_cycle_reservs (FILE *, reserv_sets_t,
int, int);
static void output_reserv_sets (FILE *, reserv_sets_t);
static state_t get_free_state (int, automaton_t);
static void free_state (state_t);
static hashval_t state_hash (const void *);
static int state_eq_p (const void *, const void *);
static state_t insert_state (state_t);
static void set_state_reserv (state_t, int, int);
static int intersected_state_reservs_p (state_t, state_t);
static state_t states_union (state_t, state_t, reserv_sets_t);
static state_t state_shift (state_t, reserv_sets_t);
static void initiate_states (void);
static void finish_states (void);
static void free_arc (arc_t);
static void remove_arc (state_t, arc_t);
static arc_t find_arc (state_t, state_t, ainsn_t);
static arc_t add_arc (state_t, state_t, ainsn_t, int);
static arc_t first_out_arc (state_t);
static arc_t next_out_arc (arc_t);
static void initiate_arcs (void);
static void finish_arcs (void);
static automata_list_el_t get_free_automata_list_el (void);
static void free_automata_list_el (automata_list_el_t);
static void free_automata_list (automata_list_el_t);
static hashval_t automata_list_hash (const void *);
static int automata_list_eq_p (const void *, const void *);
static void initiate_automata_lists (void);
static void automata_list_start (void);
static void automata_list_add (automaton_t);
static automata_list_el_t automata_list_finish (void);
static void finish_automata_lists (void);
static void initiate_excl_sets (void);
static reserv_sets_t get_excl_set (reserv_sets_t);
static pattern_reserv_t form_reserv_sets_list (pattern_set_el_t);
static void initiate_presence_absence_pattern_sets (void);
static int check_presence_pattern_sets (reserv_sets_t,
reserv_sets_t, int);
static int check_absence_pattern_sets (reserv_sets_t, reserv_sets_t,
int);
static regexp_t copy_insn_regexp (regexp_t);
static regexp_t transform_1 (regexp_t);
static regexp_t transform_2 (regexp_t);
static regexp_t transform_3 (regexp_t);
static regexp_t regexp_transform_func
(regexp_t, regexp_t (*) (regexp_t));
static regexp_t transform_regexp (regexp_t);
static void transform_insn_regexps (void);
static void store_alt_unit_usage (regexp_t, regexp_t, int, int);
static void check_regexp_units_distribution (const char *, regexp_t);
static void check_unit_distributions_to_automata (void);
static int process_seq_for_forming_states (regexp_t, automaton_t,
int);
static void finish_forming_alt_state (alt_state_t,
automaton_t);
static void process_alts_for_forming_states (regexp_t,
automaton_t, int);
static void create_alt_states (automaton_t);
static void form_ainsn_with_same_reservs (automaton_t);
static reserv_sets_t form_reservs_matter (automaton_t);
static void make_automaton (automaton_t);
static void form_arcs_marked_by_insn (state_t);
static int create_composed_state (state_t, arc_t, vla_ptr_t *);
static void NDFA_to_DFA (automaton_t);
static void pass_state_graph (state_t, void (*) (state_t));
static void pass_states (automaton_t,
void (*) (state_t));
static void initiate_pass_states (void);
static void add_achieved_state (state_t);
static int set_out_arc_insns_equiv_num (state_t, int);
static void clear_arc_insns_equiv_num (state_t);
static void copy_equiv_class (vla_ptr_t *to,
const vla_ptr_t *from);
static int first_cycle_unit_presence (state_t, int);
static int state_is_differed (state_t, state_t, int, int);
static state_t init_equiv_class (state_t *states, int);
static int partition_equiv_class (state_t *, int,
vla_ptr_t *, int *);
static void evaluate_equiv_classes (automaton_t, vla_ptr_t *);
static void merge_states (automaton_t, vla_ptr_t *);
static void set_new_cycle_flags (state_t);
static void minimize_DFA (automaton_t);
static void incr_states_and_arcs_nums (state_t);
static void count_states_and_arcs (automaton_t, int *, int *);
static void build_automaton (automaton_t);
static void set_order_state_num (state_t);
static void enumerate_states (automaton_t);
static ainsn_t insert_ainsn_into_equiv_class (ainsn_t, ainsn_t);
static void delete_ainsn_from_equiv_class (ainsn_t);
static void process_insn_equiv_class (ainsn_t, arc_t *);
static void process_state_for_insn_equiv_partition (state_t);
static void set_insn_equiv_classes (automaton_t);
static double estimate_one_automaton_bound (void);
static int compare_max_occ_cycle_nums (const void *,
const void *);
static void units_to_automata_heuristic_distr (void);
static ainsn_t create_ainsns (void);
static void units_to_automata_distr (void);
static void create_automata (void);
static void form_regexp (regexp_t);
static const char *regexp_representation (regexp_t);
static void finish_regexp_representation (void);
static void output_range_type (FILE *, long int, long int);
static int longest_path_length (state_t);
static void process_state_longest_path_length (state_t);
static void output_dfa_max_issue_rate (void);
static void output_vect (vect_el_t *, int);
static void output_chip_member_name (FILE *, automaton_t);
static void output_temp_chip_member_name (FILE *, automaton_t);
static void output_translate_vect_name (FILE *, automaton_t);
static void output_trans_full_vect_name (FILE *, automaton_t);
static void output_trans_comb_vect_name (FILE *, automaton_t);
static void output_trans_check_vect_name (FILE *, automaton_t);
static void output_trans_base_vect_name (FILE *, automaton_t);
static void output_state_alts_full_vect_name (FILE *, automaton_t);
static void output_state_alts_comb_vect_name (FILE *, automaton_t);
static void output_state_alts_check_vect_name (FILE *, automaton_t);
static void output_state_alts_base_vect_name (FILE *, automaton_t);
static void output_min_issue_delay_vect_name (FILE *, automaton_t);
static void output_dead_lock_vect_name (FILE *, automaton_t);
static void output_reserved_units_table_name (FILE *, automaton_t);
static void output_state_member_type (FILE *, automaton_t);
static void output_chip_definitions (void);
static void output_translate_vect (automaton_t);
static int comb_vect_p (state_ainsn_table_t);
static state_ainsn_table_t create_state_ainsn_table (automaton_t);
static void output_state_ainsn_table
(state_ainsn_table_t, char *, void (*) (FILE *, automaton_t),
void (*) (FILE *, automaton_t), void (*) (FILE *, automaton_t),
void (*) (FILE *, automaton_t));
static void add_vect (state_ainsn_table_t,
int, vect_el_t *, int);
static int out_state_arcs_num (state_t);
static int compare_transition_els_num (const void *, const void *);
static void add_vect_el (vla_hwint_t *,
ainsn_t, int);
static void add_states_vect_el (state_t);
static void output_trans_table (automaton_t);
static void output_state_alts_table (automaton_t);
static int min_issue_delay_pass_states (state_t, ainsn_t);
static int min_issue_delay (state_t, ainsn_t);
static void initiate_min_issue_delay_pass_states (void);
static void output_min_issue_delay_table (automaton_t);
static void output_dead_lock_vect (automaton_t);
static void output_reserved_units_table (automaton_t);
static void output_tables (void);
static void output_max_insn_queue_index_def (void);
static void output_insn_code_cases (void (*) (automata_list_el_t));
static void output_automata_list_min_issue_delay_code (automata_list_el_t);
static void output_internal_min_issue_delay_func (void);
static void output_automata_list_transition_code (automata_list_el_t);
static void output_internal_trans_func (void);
static void output_internal_insn_code_evaluation (const char *,
const char *, int);
static void output_dfa_insn_code_func (void);
static void output_trans_func (void);
static void output_automata_list_state_alts_code (automata_list_el_t);
static void output_internal_state_alts_func (void);
static void output_state_alts_func (void);
static void output_min_issue_delay_func (void);
static void output_internal_dead_lock_func (void);
static void output_dead_lock_func (void);
static void output_internal_reset_func (void);
static void output_size_func (void);
static void output_reset_func (void);
static void output_min_insn_conflict_delay_func (void);
static void output_internal_insn_latency_func (void);
static void output_insn_latency_func (void);
static void output_print_reservation_func (void);
static int units_cmp (const void *,
const void *);
static void output_get_cpu_unit_code_func (void);
static void output_cpu_unit_reservation_p (void);
static void output_dfa_clean_insn_cache_func (void);
static void output_dfa_start_func (void);
static void output_dfa_finish_func (void);
static void output_regexp (regexp_t );
static void output_unit_set_el_list (unit_set_el_t);
static void output_pattern_set_el_list (pattern_set_el_t);
static void output_description (void);
static void output_automaton_name (FILE *, automaton_t);
static void output_automaton_units (automaton_t);
static void add_state_reservs (state_t);
static void output_state_arcs (state_t);
static int state_reservs_cmp (const void *,
const void *);
static void remove_state_duplicate_reservs (void);
static void output_state (state_t);
static void output_automaton_descriptions (void);
static void output_statistics (FILE *);
static void output_time_statistics (FILE *);
static void generate (void);
static void make_insn_alts_attr (void);
static void make_internal_dfa_insn_code_attr (void);
static void make_default_insn_latency_attr (void);
static void make_bypass_attr (void);
static const char *file_name_suffix (const char *);
static const char *base_file_name (const char *);
static void check_automata_insn_issues (void);
static void add_automaton_state (state_t);
static void form_important_insn_automata_lists (void);
/* Undefined position. */
static pos_t no_pos = 0;
/* 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 *const _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 *const _expand_vla_ptr = &(vla); \
const 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 *const _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 *const _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))
#define VLA_HWINT_NULLIFY(vla) ((vla).length = 0)
#define VLA_HWINT_EXPAND(vla, n) \
do { \
vla_hwint_t *const _expand_vla_ptr = &(vla); \
const 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 *const _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)
/* Options with the following names can be set up in automata_option
construction. Because the strings occur more one time we use the
macros. */
#define NO_MINIMIZATION_OPTION "-no-minimization"
#define TIME_OPTION "-time"
#define V_OPTION "-v"
#define W_OPTION "-w"
#define NDFA_OPTION "-ndfa"
#define PROGRESS_OPTION "-progress"
/* The following flags are set up by function `initiate_automaton_gen'. */
/* Make automata with nondeterministic 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 output of a progress bar showing how many states were
generated so far for automaton being processed (`-progress'). */
static int progress_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 nonzero 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 field value is minimal cycle number (0, ...) on
which given unit occurs in insns. -1 value means that given
unit is not used in insns. */
int min_occ_cycle_num;
/* The following list contains units which conflict with given
unit. */
unit_set_el_t excl_list;
/* The following list contains patterns which are required to
reservation of given unit. */
pattern_set_el_t presence_list;
pattern_set_el_t final_presence_list;
/* The following list contains patterns which should be not present
in reservation for given unit. */
pattern_set_el_t absence_list;
pattern_set_el_t final_absence_list;
/* The following is used only when `query_p' has nonzero value.
This is query number for the unit. */
int query_num;
/* The following is the last cycle on which the unit was checked for
correct distributions of units to automata in a regexp. */
int last_distribution_check_cycle;
/* 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;
/* If the following value is not zero, the cpu unit is present in a
`exclusion_set' or in right part of a `presence_set',
`final_presence_set', `absence_set', and
`final_absence_set'define_query_cpu_unit. */
char in_set_p;
};
/* 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 nonzero 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. */
automaton_t corresponding_automaton;
};
/* This describes exclusion relations: exclusion_set (see file
rtl.def). */
struct excl_rel_decl
{
int all_names_num;
int first_list_length;
char *names [1];
};
/* This describes unit relations: [final_]presence_set or
[final_]absence_set (see file rtl.def). */
struct unit_pattern_rel_decl
{
int final_p;
int names_num;
int patterns_num;
char **names;
char ***patterns;
};
/* This describes define_reservation (see file rtl.def). */
struct reserv_decl
{
char *name;
regexp_t regexp;
/* The following fields are defined by checker. */
/* The following field value is nonzero 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_reservation (see file rtl.def). */
struct insn_reserv_decl
{
rtx condexp;
int default_latency;
regexp_t 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'. */
regexp_t transformed_regexp;
/* The following field value is list of arcs marked given
insn. The field is used in transformation NDFA -> DFA. */
arc_t 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;
/* The following member value is the list to automata which can be
changed by the insn issue. */
automata_list_el_t important_automata_list;
/* The following member is used to process insn once for output. */
int processed_p;
};
/* 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 excl_rel_decl excl;
struct unit_pattern_rel_decl presence;
struct unit_pattern_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;
unit_decl_t 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;
regexp_t regexps [1];
};
/* Representation of construction `repeat' (see file rtl.def). */
struct repeat_regexp
{
int repeat_num;
regexp_t regexp;
};
/* Representation of reservations separated by '+' (see file
rtl.def). */
struct allof_regexp
{
int regexps_num;
regexp_t regexps [1];
};
/* Representation of reservations separated by '|' (see file
rtl.def). */
struct oneof_regexp
{
int regexps_num;
regexp_t 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;
};
/* Represents 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. */
automaton_t 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. */
decl_t decls [1];
};
/* The following nodes are created in automaton checker. */
/* The following nodes represent exclusion set for cpu units. Each
element is accessed through only one excl_list. */
struct unit_set_el
{
unit_decl_t unit_decl;
unit_set_el_t next_unit_set_el;
};
/* The following nodes represent presence or absence pattern for cpu
units. Each element is accessed through only one presence_list or
absence_list. */
struct pattern_set_el
{
/* The number of units in unit_decls. */
int units_num;
/* The units forming the pattern. */
struct unit_decl **unit_decls;
pattern_set_el_t next_pattern_set_el;
};
/* The following nodes are created in automaton generator. */
/* The following nodes represent presence or absence pattern for cpu
units. Each element is accessed through only one element of
unit_presence_set_table or unit_absence_set_table. */
struct pattern_reserv
{
reserv_sets_t reserv;
pattern_reserv_t next_pattern_reserv;
};
/* 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 value is nonzero 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. */
automaton_t automaton;
/* The following field value is the first arc output from given
state. */
arc_t 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 and DFA
minimization. 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'. We should
support only one level of nesting state. */
alt_state_t 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. */
state_t 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. */
state_t 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 state_pass_num;
/* The following member is used to evaluate min issue delay of insn
for a state. */
int min_insn_issue_delay;
/* The following member is used to evaluate max issue rate of the
processor. The value of the member is maximal length of the path
from given state no containing arcs marked by special insn `cycle
advancing'. */
int longest_path_length;
};
/* The following macro is an initial value of member
`longest_path_length' of a state. */
#define UNDEFINED_LONGEST_PATH_LENGTH -1
/* Automaton arc. */
struct arc
{
/* The following field refers for the state into which given arc
enters. */
state_t 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. */
ainsn_t insn;
/* The following field value is the next arc output from the same
state. */
arc_t next_out_arc;
/* List of arcs marked given insn is formed with the following
field. The field is used in transformation NDFA -> DFA. */
arc_t next_arc_marked_by_insn;
/* The following field is defined if NDFA_FLAG is zero. 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 deterministic state which characterizes
unit reservations of the instruction. */
state_t state;
/* The following field refers to the next state which characterizes
unit reservations of the instruction. */
alt_state_t next_alt_state;
/* The following field refers to the next state in sorted list. */
alt_state_t 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. */
ainsn_t 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'. */
alt_state_t 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'. */
alt_state_t sorted_alt_states;
/* The following field refers the next automaton insn with
the same reservations. */
ainsn_t 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 nonzero value if there is arc from state of
the automaton marked by the ainsn. */
char arc_exists_p;
/* Cyclic list of insns of an equivalence class is formed with the
aid of the following field. */
ainsn_t next_equiv_class_insn;
/* The following field value is nonzero 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 following member value is TRUE if there is an arc in the
automaton marked by the insn into another state. In other
words, the insn can change the state of the automaton. */
int important_p;
};
/* The following describes an automaton for PHR. */
struct automaton
{
/* The following field value is the list of insn declarations for
given automaton. */
ainsn_t 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. */
automaton_t next_automaton;
/* The following field is start state of FA. There are not unit
reservations in the state. */
state_t 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. */
state_ainsn_table_t trans_table;
state_ainsn_table_t 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 is the element of the list of automata. */
struct automata_list_el
{
/* The automaton itself. */
automaton_t automaton;
/* The next automata set element. */
automata_list_el_t next_automata_list_el;
};
/* The following structure describes a table state X ainsn -> int(>= 0). */
struct state_ainsn_table
{
/* Automaton to which given table belongs. */
automaton_t 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;
};
/* Macros to access members of unions. Use only them for access to
union members of declarations and regexps. */
#if defined ENABLE_CHECKING && (GCC_VERSION >= 2007)
#define DECL_UNIT(d) __extension__ \
(({ struct decl *const _decl = (d); \
if (_decl->mode != dm_unit) \
decl_mode_check_failed (_decl->mode, "dm_unit", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.unit; }))
#define DECL_BYPASS(d) __extension__ \
(({ struct decl *const _decl = (d); \
if (_decl->mode != dm_bypass) \
decl_mode_check_failed (_decl->mode, "dm_bypass", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.bypass; }))
#define DECL_AUTOMATON(d) __extension__ \
(({ struct decl *const _decl = (d); \
if (_decl->mode != dm_automaton) \
decl_mode_check_failed (_decl->mode, "dm_automaton", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.automaton; }))
#define DECL_EXCL(d) __extension__ \
(({ struct decl *const _decl = (d); \
if (_decl->mode != dm_excl) \
decl_mode_check_failed (_decl->mode, "dm_excl", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.excl; }))
#define DECL_PRESENCE(d) __extension__ \
(({ struct decl *const _decl = (d); \
if (_decl->mode != dm_presence) \
decl_mode_check_failed (_decl->mode, "dm_presence", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.presence; }))
#define DECL_ABSENCE(d) __extension__ \
(({ struct decl *const _decl = (d); \
if (_decl->mode != dm_absence) \
decl_mode_check_failed (_decl->mode, "dm_absence", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.absence; }))
#define DECL_RESERV(d) __extension__ \
(({ struct decl *const _decl = (d); \
if (_decl->mode != dm_reserv) \
decl_mode_check_failed (_decl->mode, "dm_reserv", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.reserv; }))
#define DECL_INSN_RESERV(d) __extension__ \
(({ struct decl *const _decl = (d); \
if (_decl->mode != dm_insn_reserv) \
decl_mode_check_failed (_decl->mode, "dm_insn_reserv", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.insn_reserv; }))
static const char *decl_name (enum decl_mode);
static void decl_mode_check_failed (enum decl_mode, const char *,
const char *, int, const char *);
/* Return string representation of declaration mode MODE. */
static const char *
decl_name (enum decl_mode mode)
{
static char str [100];
if (mode == dm_unit)
return "dm_unit";
else if (mode == dm_bypass)
return "dm_bypass";
else if (mode == dm_automaton)
return "dm_automaton";
else if (mode == dm_excl)
return "dm_excl";
else if (mode == dm_presence)
return "dm_presence";
else if (mode == dm_absence)
return "dm_absence";
else if (mode == dm_reserv)
return "dm_reserv";
else if (mode == dm_insn_reserv)
return "dm_insn_reserv";
else
sprintf (str, "unknown (%d)", (int) mode);
return str;
}
/* The function prints message about unexpected declaration and finish
the program. */
static void
decl_mode_check_failed (enum decl_mode mode, const char *expected_mode_str,
const char *file, int line, const char *func)
{
fprintf
(stderr,
"\n%s: %d: error in %s: DECL check: expected decl %s, have %s\n",
file, line, func, expected_mode_str, decl_name (mode));
exit (1);
}
#define REGEXP_UNIT(r) __extension__ \
(({ struct regexp *const _regexp = (r); \
if (_regexp->mode != rm_unit) \
regexp_mode_check_failed (_regexp->mode, "rm_unit", \
__FILE__, __LINE__, __FUNCTION__); \
&(_regexp)->regexp.unit; }))
#define REGEXP_RESERV(r) __extension__ \
(({ struct regexp *const _regexp = (r); \
if (_regexp->mode != rm_reserv) \
regexp_mode_check_failed (_regexp->mode, "rm_reserv", \
__FILE__, __LINE__, __FUNCTION__); \
&(_regexp)->regexp.reserv; }))
#define REGEXP_SEQUENCE(r) __extension__ \
(({ struct regexp *const _regexp = (r); \
if (_regexp->mode != rm_sequence) \
regexp_mode_check_failed (_regexp->mode, "rm_sequence", \
__FILE__, __LINE__, __FUNCTION__); \
&(_regexp)->regexp.sequence; }))
#define REGEXP_REPEAT(r) __extension__ \
(({ struct regexp *const _regexp = (r); \
if (_regexp->mode != rm_repeat) \
regexp_mode_check_failed (_regexp->mode, "rm_repeat", \
__FILE__, __LINE__, __FUNCTION__); \
&(_regexp)->regexp.repeat; }))
#define REGEXP_ALLOF(r) __extension__ \
(({ struct regexp *const _regexp = (r); \
if (_regexp->mode != rm_allof) \
regexp_mode_check_failed (_regexp->mode, "rm_allof", \
__FILE__, __LINE__, __FUNCTION__); \
&(_regexp)->regexp.allof; }))
#define REGEXP_ONEOF(r) __extension__ \
(({ struct regexp *const _regexp = (r); \
if (_regexp->mode != rm_oneof) \
regexp_mode_check_failed (_regexp->mode, "rm_oneof", \
__FILE__, __LINE__, __FUNCTION__); \
&(_regexp)->regexp.oneof; }))
static const char *regexp_name (enum regexp_mode);
static void regexp_mode_check_failed (enum regexp_mode, const char *,
const char *, int,
const char *);
/* Return string representation of regexp mode MODE. */
static const char *
regexp_name (enum regexp_mode mode)
{
static char str [100];
if (mode == rm_unit)
return "rm_unit";
else if (mode == rm_reserv)
return "rm_reserv";
else if (mode == rm_nothing)
return "rm_nothing";
else if (mode == rm_sequence)
return "rm_sequence";
else if (mode == rm_repeat)
return "rm_repeat";
else if (mode == rm_allof)
return "rm_allof";
else if (mode == rm_oneof)
return "rm_oneof";
else
sprintf (str, "unknown (%d)", (int) mode);
return str;
}
/* The function prints message about unexpected regexp and finish the
program. */
static void
regexp_mode_check_failed (enum regexp_mode mode,
const char *expected_mode_str,
const char *file, int line, const char *func)
{
fprintf
(stderr,
"\n%s: %d: error in %s: REGEXP check: expected decl %s, have %s\n",
file, line, func, expected_mode_str, regexp_name (mode));
exit (1);
}
#else /* #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007) */
#define DECL_UNIT(d) (&(d)->decl.unit)
#define DECL_BYPASS(d) (&(d)->decl.bypass)
#define DECL_AUTOMATON(d) (&(d)->decl.automaton)
#define DECL_EXCL(d) (&(d)->decl.excl)
#define DECL_PRESENCE(d) (&(d)->decl.presence)
#define DECL_ABSENCE(d) (&(d)->decl.absence)
#define DECL_RESERV(d) (&(d)->decl.reserv)
#define DECL_INSN_RESERV(d) (&(d)->decl.insn_reserv)
#define REGEXP_UNIT(r) (&(r)->regexp.unit)
#define REGEXP_RESERV(r) (&(r)->regexp.reserv)
#define REGEXP_SEQUENCE(r) (&(r)->regexp.sequence)
#define REGEXP_REPEAT(r) (&(r)->regexp.repeat)
#define REGEXP_ALLOF(r) (&(r)->regexp.allof)
#define REGEXP_ONEOF(r) (&(r)->regexp.oneof)
#endif /* #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007) */
/* Create IR structure (node). */
static void *
create_node (size_t size)
{
void *result;
obstack_blank (&irp, size);
result = obstack_base (&irp);
obstack_finish (&irp);
/* Default values of members are NULL and zero. */
memset (result, 0, size);
return result;
}
/* Copy IR structure (node). */
static void *
copy_node (const void *from, size_t size)
{
void *const result = create_node (size);
memcpy (result, from, size);
return result;
}
/* The function checks that NAME does not contain quotes (`"'). */
static char *
check_name (char * name, pos_t pos ATTRIBUTE_UNUSED)
{
const char *str;
for (str = name; *str != '\0'; str++)
if (*str == '\"')
error ("Name `%s' contains quotes", name);
return name;
}
/* Pointers to all declarations during IR generation are stored in the
following. */
static vla_ptr_t decls;
/* Given a pointer to a (char *) and a separator, return an alloc'ed
string containing the next separated element, taking parentheses
into account if PAR_FLAG has nonzero value. 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 (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--)
obstack_1grow (&irp, p [-n_spaces]);
obstack_1grow (&irp, *p);
}
}
obstack_1grow (&irp, '\0');
out_str = obstack_base (&irp);
obstack_finish (&irp);
*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 has
nonzero value. Return 0 for the null string, -1 if parentheses is
not balanced. */
static int
n_sep_els (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 PAREN_P has nonzero value. The
function also inserts the end marker NULL at the end of vector.
Return 0 for the null string, -1 if parentheses are not balanced. */
static char **
get_str_vect (char *str, int *els_num, int sep, int paren_p)
{
int i;
char **vect;
char **pstr;
*els_num = n_sep_els (str, sep, paren_p);
if (*els_num <= 0)
return NULL;
obstack_blank (&irp, sizeof (char *) * (*els_num + 1));
vect = (char **) obstack_base (&irp);
obstack_finish (&irp);
pstr = &str;
for (i = 0; i < *els_num; i++)
vect [i] = next_sep_el (pstr, sep, paren_p);
if (next_sep_el (pstr, sep, paren_p) != NULL)
abort ();
vect [i] = 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'. */
void
gen_cpu_unit (rtx def)
{
decl_t 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_UNIT (decl)->name = check_name (str_cpu_units [i], decl->pos);
DECL_UNIT (decl)->automaton_name = (char *) XSTR (def, 1);
DECL_UNIT (decl)->query_p = 0;
DECL_UNIT (decl)->min_occ_cycle_num = -1;
DECL_UNIT (decl)->in_set_p = 0;
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'. */
void
gen_query_cpu_unit (rtx def)
{
decl_t 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_UNIT (decl)->name = check_name (str_cpu_units [i], decl->pos);
DECL_UNIT (decl)->automaton_name = (char *) XSTR (def, 1);
DECL_UNIT (decl)->query_p = 1;
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'. */
void
gen_bypass (rtx def)
{
decl_t 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_BYPASS (decl)->latency = XINT (def, 0);
DECL_BYPASS (decl)->out_insn_name = out_insns [i];
DECL_BYPASS (decl)->in_insn_name = in_insns [j];
DECL_BYPASS (decl)->bypass_guard_name = (char *) XSTR (def, 3);
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
}
/* Process an EXCLUSION_SET.
This gives information about a cpu unit conflicts. We fill a
struct excl_rel_decl (excl) with information used later by
`expand_automata'. */
void
gen_excl_set (rtx def)
{
decl_t 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_EXCL (decl)->all_names_num = length;
DECL_EXCL (decl)->first_list_length = first_vect_length;
for (i = 0; i < length; i++)
if (i < first_vect_length)
DECL_EXCL (decl)->names [i] = first_str_cpu_units [i];
else
DECL_EXCL (decl)->names [i]
= second_str_cpu_units [i - first_vect_length];
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
/* Process a PRESENCE_SET, a FINAL_PRESENCE_SET, an ABSENCE_SET,
FINAL_ABSENCE_SET (it is depended on PRESENCE_P and FINAL_P).
This gives information about a cpu unit reservation requirements.
We fill a struct unit_pattern_rel_decl with information used later
by `expand_automata'. */
static void
gen_presence_absence_set (rtx def, int presence_p, int final_p)
{
decl_t decl;
char **str_cpu_units;
char ***str_patterns;
int cpu_units_length;
int length;
int patterns_length;
int i;
str_cpu_units = get_str_vect ((char *) XSTR (def, 0), &cpu_units_length, ',',
FALSE);
if (str_cpu_units == NULL)
fatal ((presence_p
? (final_p
? "invalid first string `%s' in final_presence_set"
: "invalid first string `%s' in presence_set")
: (final_p
? "invalid first string `%s' in final_absence_set"
: "invalid first string `%s' in absence_set")),
XSTR (def, 0));
str_patterns = (char ***) get_str_vect ((char *) XSTR (def, 1),
&patterns_length, ',', FALSE);
if (str_patterns == NULL)
fatal ((presence_p
? (final_p
? "invalid second string `%s' in final_presence_set"
: "invalid second string `%s' in presence_set")
: (final_p
? "invalid second string `%s' in final_absence_set"
: "invalid second string `%s' in absence_set")), XSTR (def, 1));
for (i = 0; i < patterns_length; i++)
{
str_patterns [i] = get_str_vect ((char *) str_patterns [i], &length, ' ',
FALSE);
if (str_patterns [i] == NULL)
abort ();
}
decl = create_node (sizeof (struct decl));
decl->pos = 0;
if (presence_p)
{
decl->mode = dm_presence;
DECL_PRESENCE (decl)->names_num = cpu_units_length;
DECL_PRESENCE (decl)->names = str_cpu_units;
DECL_PRESENCE (decl)->patterns = str_patterns;
DECL_PRESENCE (decl)->patterns_num = patterns_length;
DECL_PRESENCE (decl)->final_p = final_p;
}
else
{
decl->mode = dm_absence;
DECL_ABSENCE (decl)->names_num = cpu_units_length;
DECL_ABSENCE (decl)->names = str_cpu_units;
DECL_ABSENCE (decl)->patterns = str_patterns;
DECL_ABSENCE (decl)->patterns_num = patterns_length;
DECL_ABSENCE (decl)->final_p = final_p;
}
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_pattern_rel_decl (presence) with information
used later by `expand_automata'. */
void
gen_presence_set (rtx def)
{
gen_presence_absence_set (def, TRUE, FALSE);
}
/* Process a FINAL_PRESENCE_SET.
This gives information about a cpu unit reservation requirements.
We fill a struct unit_pattern_rel_decl (presence) with information
used later by `expand_automata'. */
void
gen_final_presence_set (rtx def)
{
gen_presence_absence_set (def, TRUE, TRUE);
}
/* Process an ABSENCE_SET.
This gives information about a cpu unit reservation requirements.
We fill a struct unit_pattern_rel_decl (absence) with information
used later by `expand_automata'. */
void
gen_absence_set (rtx def)
{
gen_presence_absence_set (def, FALSE, FALSE);
}
/* Process a FINAL_ABSENCE_SET.
This gives information about a cpu unit reservation requirements.
We fill a struct unit_pattern_rel_decl (absence) with information
used later by `expand_automata'. */
void
gen_final_absence_set (rtx def)
{
gen_presence_absence_set (def, FALSE, TRUE);
}
/* 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'. */
void
gen_automaton (rtx def)
{
decl_t 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_AUTOMATON (decl)->name = check_name (str_automata [i], decl->pos);
VLA_PTR_ADD (decls, decl);
num_dfa_decls++;
}
}
/* Process an AUTOMATA_OPTION.
This gives information how to generate finite state automaton used
for recognizing pipeline hazards. */
void
gen_automata_option (rtx def)
{
if (strcmp (XSTR (def, 0), NO_MINIMIZATION_OPTION + 1) == 0)
no_minimization_flag = 1;
else if (strcmp (XSTR (def, 0), TIME_OPTION + 1) == 0)
time_flag = 1;
else if (strcmp (XSTR (def, 0), V_OPTION + 1) == 0)
v_flag = 1;
else if (strcmp (XSTR (def, 0), W_OPTION + 1) == 0)
w_flag = 1;
else if (strcmp (XSTR (def, 0), NDFA_OPTION + 1) == 0)
ndfa_flag = 1;
else if (strcmp (XSTR (def, 0), PROGRESS_OPTION + 1) == 0)
progress_flag = 1;
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 regexp_t
gen_regexp_el (char *str)
{
regexp_t 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_UNIT (regexp)->name = str;
}
return regexp;
}
/* Parse construction `repeat' in STR. */
static regexp_t
gen_regexp_repeat (char *str)
{
regexp_t regexp;
regexp_t 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;
REGEXP_REPEAT (repeat)->regexp = regexp;
REGEXP_REPEAT (repeat)->repeat_num = atoi (repeat_vect [i]);
if (REGEXP_REPEAT (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 regexp_t
gen_regexp_allof (char *str)
{
regexp_t 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 (regexp_t) * (els_num - 1));
allof->mode = rm_allof;
REGEXP_ALLOF (allof)->regexps_num = els_num;
for (i = 0; i < els_num; i++)
REGEXP_ALLOF (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 regexp_t
gen_regexp_oneof (char *str)
{
regexp_t 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 (regexp_t) * (els_num - 1));
oneof->mode = rm_oneof;
REGEXP_ONEOF (oneof)->regexps_num = els_num;
for (i = 0; i < els_num; i++)
REGEXP_ONEOF (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 regexp_t
gen_regexp_sequence (char *str)
{
regexp_t 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 (regexp_t) * (els_num - 1));
sequence->mode = rm_sequence;
REGEXP_SEQUENCE (sequence)->regexps_num = els_num;
for (i = 0; i < els_num; i++)
REGEXP_SEQUENCE (sequence)->regexps [i]
= gen_regexp_oneof (sequence_vect [i]);
return sequence;
}
else
return gen_regexp_oneof (str);
}
/* Parse construction reservation STR. */
static regexp_t
gen_regexp (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'. */
void
gen_reserv (rtx def)
{
decl_t decl;
decl = create_node (sizeof (struct decl));
decl->mode = dm_reserv;
decl->pos = 0;
DECL_RESERV (decl)->name = check_name ((char *) XSTR (def, 0), decl->pos);
DECL_RESERV (decl)->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'. */
void
gen_insn_reserv (rtx def)
{
decl_t decl;
decl = create_node (sizeof (struct decl));
decl->mode = dm_insn_reserv;
decl->pos = 0;
DECL_INSN_RESERV (decl)->name
= check_name ((char *) XSTR (def, 0), decl->pos);
DECL_INSN_RESERV (decl)->default_latency = XINT (def, 1);
DECL_INSN_RESERV (decl)->condexp = XEXP (def, 2);
DECL_INSN_RESERV (decl)->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 (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. Remember
that automaton names have own space. */
/* The function evaluates hash value of an automaton declaration. The
function is used by abstract data `hashtab'. The function returns
hash value (0..UINT_MAX) of given automaton declaration. */
static hashval_t
automaton_decl_hash (const void *automaton_decl)
{
const decl_t decl = (decl_t) automaton_decl;
if (decl->mode == dm_automaton && DECL_AUTOMATON (decl)->name == NULL)
abort ();
return string_hash (DECL_AUTOMATON (decl)->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 (const void* automaton_decl_1,
const void* automaton_decl_2)
{
const decl_t decl1 = (decl_t) automaton_decl_1;
const decl_t decl2 = (decl_t) automaton_decl_2;
if (decl1->mode != dm_automaton || DECL_AUTOMATON (decl1)->name == NULL
|| decl2->mode != dm_automaton || DECL_AUTOMATON (decl2)->name == NULL)
abort ();
return strcmp (DECL_AUTOMATON (decl1)->name,
DECL_AUTOMATON (decl2)->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 decl_t
insert_automaton_decl (decl_t automaton_decl)
{
void **entry_ptr;
entry_ptr = htab_find_slot (automaton_decl_table, automaton_decl, 1);
if (*entry_ptr == NULL)
*entry_ptr = (void *) automaton_decl;
return (decl_t) *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 decl_t
find_automaton_decl (char *name)
{
void *entry;
work_automaton_decl.mode = dm_automaton;
DECL_AUTOMATON (&work_automaton_decl)->name = name;
entry = htab_find (automaton_decl_table, &work_automaton_decl);
return (decl_t) 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 (void)
{
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 (void)
{
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). Remember that insn names have own
space. */
/* The function evaluates hash value of an insn declaration. The
function is used by abstract data `hashtab'. The function returns
hash value (0..UINT_MAX) of given insn declaration. */
static hashval_t
insn_decl_hash (const void *insn_decl)
{
const decl_t decl = (decl_t) insn_decl;
if (decl->mode != dm_insn_reserv || DECL_INSN_RESERV (decl)->name == NULL)
abort ();
return string_hash (DECL_INSN_RESERV (decl)->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 (const void *insn_decl_1, const void *insn_decl_2)
{
const decl_t decl1 = (decl_t) insn_decl_1;
const decl_t decl2 = (decl_t) insn_decl_2;
if (decl1->mode != dm_insn_reserv || DECL_INSN_RESERV (decl1)->name == NULL
|| decl2->mode != dm_insn_reserv
|| DECL_INSN_RESERV (decl2)->name == NULL)
abort ();
return strcmp (DECL_INSN_RESERV (decl1)->name,
DECL_INSN_RESERV (decl2)->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 decl_t
insert_insn_decl (decl_t insn_decl)
{
void **entry_ptr;
entry_ptr = htab_find_slot (insn_decl_table, insn_decl, 1);
if (*entry_ptr == NULL)
*entry_ptr = (void *) insn_decl;
return (decl_t) *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 decl_t
find_insn_decl (char *name)
{
void *entry;
work_insn_decl.mode = dm_insn_reserv;
DECL_INSN_RESERV (&work_insn_decl)->name = name;
entry = htab_find (insn_decl_table, &work_insn_decl);
return (decl_t) 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 (void)
{
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 (void)
{
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 hashval_t
decl_hash (const void *decl)
{
const decl_t d = (const decl_t) decl;
if ((d->mode != dm_unit || DECL_UNIT (d)->name == NULL)
&& (d->mode != dm_reserv || DECL_RESERV (d)->name == NULL))
abort ();
return string_hash (d->mode == dm_unit
? DECL_UNIT (d)->name : DECL_RESERV (d)->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 (const void *decl_1, const void *decl_2)
{
const decl_t d1 = (const decl_t) decl_1;
const decl_t d2 = (const decl_t) decl_2;
if (((d1->mode != dm_unit || DECL_UNIT (d1)->name == NULL)
&& (d1->mode != dm_reserv || DECL_RESERV (d1)->name == NULL))
|| ((d2->mode != dm_unit || DECL_UNIT (d2)->name == NULL)
&& (d2->mode != dm_reserv || DECL_RESERV (d2)->name == NULL)))
abort ();
return strcmp ((d1->mode == dm_unit
? DECL_UNIT (d1)->name : DECL_RESERV (d1)->name),
(d2->mode == dm_unit
? DECL_UNIT (d2)->name : DECL_RESERV (d2)->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 decl_t
insert_decl (decl_t decl)
{
void **entry_ptr;
entry_ptr = htab_find_slot (decl_table, decl, 1);
if (*entry_ptr == NULL)
*entry_ptr = (void *) decl;
return (decl_t) *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 decl_t
find_decl (char *name)
{
void *entry;
work_decl.mode = dm_unit;
DECL_UNIT (&work_decl)->name = name;
entry = htab_find (decl_table, &work_decl);
return (decl_t) 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 (void)
{
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 (void)
{
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 unit_set_el_t
process_excls (char **names, int num, pos_t excl_pos ATTRIBUTE_UNUSED)
{
unit_set_el_t el_list;
unit_set_el_t last_el;
unit_set_el_t new_el;
decl_t 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_UNIT (decl_in_table);
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 (unit_set_el_t dest_list, unit_set_el_t source_list,
pos_t excl_pos ATTRIBUTE_UNUSED)
{
unit_set_el_t dst;
unit_set_el_t src;
unit_set_el_t curr_el;
unit_set_el_t prev_el;
unit_set_el_t copy;
for (dst = dest_list; dst != NULL; dst = dst->next_unit_set_el)
for (src = source_list; src != NULL; src = src->next_unit_set_el)
{
if (dst->unit_decl == src->unit_decl)
{
error ("unit `%s' excludes itself", src->unit_decl->name);
continue;
}
if (dst->unit_decl->automaton_name != NULL
&& src->unit_decl->automaton_name != NULL
&& strcmp (dst->unit_decl->automaton_name,
src->unit_decl->automaton_name) != 0)
{
error ("units `%s' and `%s' in exclusion set belong to different automata",
src->unit_decl->name, dst->unit_decl->name);
continue;
}
for (curr_el = dst->unit_decl->excl_list, prev_el = NULL;
curr_el != NULL;
prev_el = curr_el, curr_el = curr_el->next_unit_set_el)
if (curr_el->unit_decl == src->unit_decl)
break;
if (curr_el == NULL)
{
/* Element not found - insert. */
copy = copy_node (src, sizeof (*src));
copy->next_unit_set_el = NULL;
if (prev_el == NULL)
dst->unit_decl->excl_list = copy;
else
prev_el->next_unit_set_el = copy;
}
}
}
/* Checking NAMES in presence/absence clause and returning the
formed unit_set_el_list. The function is called only after
processing all exclusion sets. */
static unit_set_el_t
process_presence_absence_names (char **names, int num,
pos_t req_pos ATTRIBUTE_UNUSED,
int presence_p, int final_p)
{
unit_set_el_t el_list;
unit_set_el_t last_el;
unit_set_el_t new_el;
decl_t 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
? (final_p
? "unit `%s' in final presence set is not declared"
: "unit `%s' in presence set is not declared")
: (final_p
? "unit `%s' in final absence 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
? (final_p
? "`%s' in final presence set is not unit"
: "`%s' in presence set is not unit")
: (final_p
? "`%s' in final absence 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_UNIT (decl_in_table);
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;
}
/* Checking NAMES in patterns of a presence/absence clause and
returning the formed pattern_set_el_list. The function is called
only after processing all exclusion sets. */
static pattern_set_el_t
process_presence_absence_patterns (char ***patterns, int num,
pos_t req_pos ATTRIBUTE_UNUSED,
int presence_p, int final_p)
{
pattern_set_el_t el_list;
pattern_set_el_t last_el;
pattern_set_el_t new_el;
decl_t decl_in_table;
int i, j;
el_list = NULL;
last_el = NULL;
for (i = 0; i < num; i++)
{
for (j = 0; patterns [i] [j] != NULL; j++)
;
new_el = create_node (sizeof (struct pattern_set_el)
+ sizeof (struct unit_decl *) * j);
new_el->unit_decls
= (struct unit_decl **) ((char *) new_el
+ sizeof (struct pattern_set_el));
new_el->next_pattern_set_el = NULL;
if (last_el == NULL)
el_list = last_el = new_el;
else
{
last_el->next_pattern_set_el = new_el;
last_el = last_el->next_pattern_set_el;
}
new_el->units_num = 0;
for (j = 0; patterns [i] [j] != NULL; j++)
{
decl_in_table = find_decl (patterns [i] [j]);
if (decl_in_table == NULL)
error ((presence_p
? (final_p
? "unit `%s' in final presence set is not declared"
: "unit `%s' in presence set is not declared")
: (final_p
? "unit `%s' in final absence set is not declared"
: "unit `%s' in absence set is not declared")),
patterns [i] [j]);
else if (decl_in_table->mode != dm_unit)
error ((presence_p
? (final_p
? "`%s' in final presence set is not unit"
: "`%s' in presence set is not unit")
: (final_p
? "`%s' in final absence set is not unit"
: "`%s' in absence set is not unit")),
patterns [i] [j]);
else
{
new_el->unit_decls [new_el->units_num]
= DECL_UNIT (decl_in_table);
new_el->units_num++;
}
}
}
return el_list;
}
/* The function adds each element from PATTERN_LIST to presence (if
PRESENCE_P) or absence list of the each element from DEST_LIST.
Checking situations "unit requires own absence", and "unit excludes
and requires presence of ...", "unit requires absence and presence
of ...", "units in (final) presence set belong to different
automata", and "units in (final) absence set belong to different
automata". Remember that we process absence sets only after all
presence sets. */
static void
add_presence_absence (unit_set_el_t dest_list,
pattern_set_el_t pattern_list,
pos_t req_pos ATTRIBUTE_UNUSED,
int presence_p, int final_p)
{
unit_set_el_t dst;
pattern_set_el_t pat;
struct unit_decl *unit;
unit_set_el_t curr_excl_el;
pattern_set_el_t curr_pat_el;
pattern_set_el_t prev_el;
pattern_set_el_t copy;
int i;
int no_error_flag;
for (dst = dest_list; dst != NULL; dst = dst->next_unit_set_el)
for (pat = pattern_list; pat != NULL; pat = pat->next_pattern_set_el)
{
for (i = 0; i < pat->units_num; i++)
{
unit = pat->unit_decls [i];
if (dst->unit_decl == unit && pat->units_num == 1 && !presence_p)
{
error ("unit `%s' requires own absence", unit->name);
continue;
}
if (dst->unit_decl->automaton_name != NULL
&& unit->automaton_name != NULL
&& strcmp (dst->unit_decl->automaton_name,
unit->automaton_name) != 0)
{
error ((presence_p
? (final_p
? "units `%s' and `%s' in final presence set belong to different automata"
: "units `%s' and `%s' in presence set belong to different automata")
: (final_p
? "units `%s' and `%s' in final absence set belong to different automata"
: "units `%s' and `%s' in absence set belong to different automata")),
unit->name, dst->unit_decl->name);
continue;
}
no_error_flag = 1;
if (presence_p)
for (curr_excl_el = dst->unit_decl->excl_list;
curr_excl_el != NULL;
curr_excl_el = curr_excl_el->next_unit_set_el)
{
if (unit == curr_excl_el->unit_decl && pat->units_num == 1)
{
if (!w_flag)
{
error ("unit `%s' excludes and requires presence of `%s'",
dst->unit_decl->name, unit->name);
no_error_flag = 0;
}
else
warning
("unit `%s' excludes and requires presence of `%s'",
dst->unit_decl->name, unit->name);
}
}
else if (pat->units_num == 1)
for (curr_pat_el = dst->unit_decl->presence_list;
curr_pat_el != NULL;
curr_pat_el = curr_pat_el->next_pattern_set_el)
if (curr_pat_el->units_num == 1
&& unit == curr_pat_el->unit_decls [0])
{
if (!w_flag)
{
error
("unit `%s' requires absence and presence of `%s'",
dst->unit_decl->name, unit->name);
no_error_flag = 0;
}
else
warning
("unit `%s' requires absence and presence of `%s'",
dst->unit_decl->name, unit->name);
}
if (no_error_flag)
{
for (prev_el = (presence_p
? (final_p
? dst->unit_decl->final_presence_list
: dst->unit_decl->final_presence_list)
: (final_p
? dst->unit_decl->final_absence_list
: dst->unit_decl->absence_list));
prev_el != NULL && prev_el->next_pattern_set_el != NULL;
prev_el = prev_el->next_pattern_set_el)
;
copy = copy_node (pat, sizeof (*pat));
copy->next_pattern_set_el = NULL;
if (prev_el == NULL)
{
if (presence_p)
{
if (final_p)
dst->unit_decl->final_presence_list = copy;
else
dst->unit_decl->presence_list = copy;
}
else if (final_p)
dst->unit_decl->final_absence_list = copy;
else
dst->unit_decl->absence_list = copy;
}
else
prev_el->next_pattern_set_el = copy;
}
}
}
}
/* The function searches for bypass with given IN_INSN_RESERV in given
BYPASS_LIST. */
static struct bypass_decl *
find_bypass (struct bypass_decl *bypass_list,
struct insn_reserv_decl *in_insn_reserv)
{
struct bypass_decl *bypass;
for (bypass = bypass_list; bypass != NULL; bypass = bypass->next)
if (bypass->in_insn_reserv == in_insn_reserv)
break;
return bypass;
}
/* The function processes pipeline description declarations, checks
their correctness, and forms exclusion/presence/absence sets. */
static void
process_decls (void)
{
decl_t decl;
decl_t automaton_decl;
decl_t decl_in_table;
decl_t out_insn_reserv;
decl_t in_insn_reserv;
struct bypass_decl *bypass;
int automaton_presence;
int i;
/* Checking repeated automata declarations. */
automaton_presence = 0;
for (i = 0; i < description->decls_num; i++)
{
decl = description->decls [i];
if (decl->mode == dm_automaton)
{
automaton_presence = 1;
decl_in_table = insert_automaton_decl (decl);
if (decl_in_table != decl)
{
if (!w_flag)
error ("repeated declaration of automaton `%s'",
DECL_AUTOMATON (decl)->name);
else
warning ("repeated declaration of automaton `%s'",
DECL_AUTOMATON (decl)->name);
}
}
}
/* Checking undeclared automata, repeated declarations (except for
automata) and correctness of their attributes (insn latency times
etc.). */
for (i = 0; i < description->decls_num; i++)
{
decl = description->decls [i];
if (decl->mode == dm_insn_reserv)
{
DECL_INSN_RESERV (decl)->condexp
= check_attr_test (DECL_INSN_RESERV (decl)->condexp, 0, 0);
if (DECL_INSN_RESERV (decl)->default_latency < 0)
error ("define_insn_reservation `%s' has negative latency time",
DECL_INSN_RESERV (decl)->name);
DECL_INSN_RESERV (decl)->insn_num = description->insns_num;
description->insns_num++;
decl_in_table = insert_insn_decl (decl);
if (decl_in_table != decl)
error ("`%s' is already used as insn reservation name",
DECL_INSN_RESERV (decl)->name);
}
else if (decl->mode == dm_bypass)
{
if (DECL_BYPASS (decl)->latency < 0)
error ("define_bypass `%s - %s' has negative latency time",
DECL_BYPASS (decl)->out_insn_name,
DECL_BYPASS (decl)->in_insn_name);
}
else if (decl->mode == dm_unit || decl->mode == dm_reserv)
{
if (decl->mode == dm_unit)
{
DECL_UNIT (decl)->automaton_decl = NULL;
if (DECL_UNIT (decl)->automaton_name != NULL)
{
automaton_decl
= find_automaton_decl (DECL_UNIT (decl)->automaton_name);
if (automaton_decl == NULL)
error ("automaton `%s' is not declared",
DECL_UNIT (decl)->automaton_name);
else
{
DECL_AUTOMATON (automaton_decl)->automaton_is_used = 1;
DECL_UNIT (decl)->automaton_decl
= DECL_AUTOMATON (automaton_decl);
}
}
else if (automaton_presence)
error ("define_unit `%s' without automaton when one defined",
DECL_UNIT (decl)->name);
DECL_UNIT (decl)->unit_num = description->units_num;
description->units_num++;
if (strcmp (DECL_UNIT (decl)->name, NOTHING_NAME) == 0)
{
error ("`%s' is declared as cpu unit", NOTHING_NAME);
continue;
}
decl_in_table = find_decl (DECL_UNIT (decl)->name);
}
else
{
if (strcmp (DECL_RESERV (decl)->name, NOTHING_NAME) == 0)
{
error ("`%s' is declared as cpu reservation", NOTHING_NAME);
continue;
}
decl_in_table = find_decl (DECL_RESERV (decl)->name);
}
if (decl_in_table == NULL)
decl_in_table = insert_decl (decl);
else
{
if (decl->mode == dm_unit)
error ("repeated declaration of unit `%s'",
DECL_UNIT (decl)->name);
else
error ("repeated declaration of reservation `%s'",
DECL_RESERV (decl)->name);
}
}
}
/* Check bypasses and form list of bypasses for each (output)
insn. */
for (i = 0; i < description->decls_num; i++)
{
decl = description->decls [i];
if (decl->mode == dm_bypass)
{
out_insn_reserv = find_insn_decl (DECL_BYPASS (decl)->out_insn_name);
in_insn_reserv = find_insn_decl (DECL_BYPASS (decl)->in_insn_name);
if (out_insn_reserv == NULL)
error ("there is no insn reservation `%s'",
DECL_BYPASS (decl)->out_insn_name);
else if (in_insn_reserv == NULL)
error ("there is no insn reservation `%s'",
DECL_BYPASS (decl)->in_insn_name);
else
{
DECL_BYPASS (decl)->out_insn_reserv
= DECL_INSN_RESERV (out_insn_reserv);
DECL_BYPASS (decl)->in_insn_reserv
= DECL_INSN_RESERV (in_insn_reserv);
bypass
= find_bypass (DECL_INSN_RESERV (out_insn_reserv)->bypass_list,
DECL_BYPASS (decl)->in_insn_reserv);
if (bypass != NULL)
{
if (DECL_BYPASS (decl)->latency == bypass->latency)
{
if (!w_flag)
error
("the same bypass `%s - %s' is already defined",
DECL_BYPASS (decl)->out_insn_name,
DECL_BYPASS (decl)->in_insn_name);
else
warning
("the same bypass `%s - %s' is already defined",
DECL_BYPASS (decl)->out_insn_name,
DECL_BYPASS (decl)->in_insn_name);
}
else
error ("bypass `%s - %s' is already defined",
DECL_BYPASS (decl)->out_insn_name,
DECL_BYPASS (decl)->in_insn_name);
}
else
{
DECL_BYPASS (decl)->next
= DECL_INSN_RESERV (out_insn_reserv)->bypass_list;
DECL_INSN_RESERV (out_insn_reserv)->bypass_list
= DECL_BYPASS (decl);
}
}
}
}
/* Check exclusion set declarations and form exclusion sets. */
for (i = 0; i < description->decls_num; i++)
{
decl = description->decls [i];
if (decl->mode == dm_excl)
{
unit_set_el_t unit_set_el_list;
unit_set_el_t unit_set_el_list_2;
unit_set_el_list
= process_excls (DECL_EXCL (decl)->names,
DECL_EXCL (decl)->first_list_length, decl->pos);
unit_set_el_list_2
= process_excls (&DECL_EXCL (decl)->names
[DECL_EXCL (decl)->first_list_length],
DECL_EXCL (decl)->all_names_num
- DECL_EXCL (decl)->first_list_length,
decl->pos);
add_excls (unit_set_el_list, unit_set_el_list_2, decl->pos);
add_excls (unit_set_el_list_2, unit_set_el_list, decl->pos);
}
}
/* Check presence set declarations and form presence sets. */
for (i = 0; i < description->decls_num; i++)
{
decl = description->decls [i];
if (decl->mode == dm_presence)
{
unit_set_el_t unit_set_el_list;
pattern_set_el_t pattern_set_el_list;
unit_set_el_list
= process_presence_absence_names
(DECL_PRESENCE (decl)->names, DECL_PRESENCE (decl)->names_num,
decl->pos, TRUE, DECL_PRESENCE (decl)->final_p);
pattern_set_el_list
= process_presence_absence_patterns
(DECL_PRESENCE (decl)->patterns,
DECL_PRESENCE (decl)->patterns_num,
decl->pos, TRUE, DECL_PRESENCE (decl)->final_p);
add_presence_absence (unit_set_el_list, pattern_set_el_list,
decl->pos, TRUE,
DECL_PRESENCE (decl)->final_p);
}
}
/* Check absence set declarations and form absence sets. */
for (i = 0; i < description->decls_num; i++)
{
decl = description->decls [i];
if (decl->mode == dm_absence)
{
unit_set_el_t unit_set_el_list;
pattern_set_el_t pattern_set_el_list;
unit_set_el_list
= process_presence_absence_names
(DECL_ABSENCE (decl)->names, DECL_ABSENCE (decl)->names_num,
decl->pos, FALSE, DECL_ABSENCE (decl)->final_p);
pattern_set_el_list
= process_presence_absence_patterns
(DECL_ABSENCE (decl)->patterns,
DECL_ABSENCE (decl)->patterns_num,
decl->pos, FALSE, DECL_ABSENCE (decl)->final_p);
add_presence_absence (unit_set_el_list, pattern_set_el_list,
decl->pos, FALSE,
DECL_ABSENCE (decl)->final_p);
}
}
}
/* 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 (void)
{
decl_t decl;
int i;
for (i = 0; i < description->decls_num; i++)
{
decl = description->decls [i];
if (decl->mode == dm_automaton
&& !DECL_AUTOMATON (decl)->automaton_is_used)
{
if (!w_flag)
error ("automaton `%s' is not used", DECL_AUTOMATON (decl)->name);
else
warning ("automaton `%s' is not used",
DECL_AUTOMATON (decl)->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 regexp_t
process_regexp (regexp_t regexp)
{
decl_t decl_in_table;
regexp_t new_regexp;
int i;
if (regexp->mode == rm_unit)
{
decl_in_table = find_decl (REGEXP_UNIT (regexp)->name);
if (decl_in_table == NULL)
error ("undeclared unit or reservation `%s'",
REGEXP_UNIT (regexp)->name);
else if (decl_in_table->mode == dm_unit)
{
DECL_UNIT (decl_in_table)->unit_is_used = 1;
REGEXP_UNIT (regexp)->unit_decl = DECL_UNIT (decl_in_table);
}
else if (decl_in_table->mode == dm_reserv)
{
DECL_RESERV (decl_in_table)->reserv_is_used = 1;
new_regexp = create_node (sizeof (struct regexp));
new_regexp->mode = rm_reserv;
new_regexp->pos = regexp->pos;
REGEXP_RESERV (new_regexp)->name = REGEXP_UNIT (regexp)->name;
REGEXP_RESERV (new_regexp)->reserv_decl
= DECL_RESERV (decl_in_table);
regexp = new_regexp;
}
else
abort ();
}
else if (regexp