Subversion Repositories openrisc

/* Pipeline hazard description translator.

   Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005

   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 3, 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 COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

/* 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 "gensupport.h"

#include <math.h>

#include "hashtab.h"

#include "vec.h"

#ifndef CHAR_BIT

#define CHAR_BIT 8

#endif

/* 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 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;

/* Undefined position.  */

static pos_t no_pos = 0;

/* All IR is stored in the following obstack.  */

static struct obstack irp;

/* Declare vector types for various data structures: */

DEF_VEC_P(alt_state_t);

DEF_VEC_ALLOC_P(alt_state_t,heap);

DEF_VEC_P(ainsn_t);

DEF_VEC_ALLOC_P(ainsn_t,heap);

DEF_VEC_P(state_t);

DEF_VEC_ALLOC_P(state_t,heap);

DEF_VEC_P(decl_t);

DEF_VEC_ALLOC_P(decl_t,heap);

DEF_VEC_P(reserv_sets_t);

DEF_VEC_ALLOC_P(reserv_sets_t,heap);

DEF_VEC_I(vect_el_t);

DEF_VEC_ALLOC_I(vect_el_t, heap);

typedef VEC(vect_el_t,heap) *vla_hwint_t;

/* Forward declarations of functions used before their definitions, only.  */

static regexp_t gen_regexp_sequence    (const char *);

static void reserv_sets_or             (reserv_sets_t, reserv_sets_t,

                                        reserv_sets_t);

static reserv_sets_t get_excl_set      (reserv_sets_t);

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 arc_t first_out_arc             (state_t);

static arc_t next_out_arc              (arc_t);

/* 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

{

  const char *name;

  /* NULL if the automaton name is absent.  */

  const 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;

  const char *out_insn_name;

  const char *in_insn_name;

  const 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

{

  const 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

{

  const 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;

  const 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 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

{

  const char *name;

  unit_decl_t unit_decl;

};

/* Define_reservation in a reservation.  */

struct reserv_regexp

{

  const 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;

  unsigned int num_out_arcs;

  /* 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;

  unsigned int *presence_signature;

  /* 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 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_equivalence_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