OSDN Git Service

2007-05-14 Dave Korn <dave.korn@artimi.com>
[pf3gnuchains/gcc-fork.git] / gcc / genautomata.c
1 /* Pipeline hazard description translator.
2    Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2007
3    Free Software Foundation, Inc.
4
5    Written by Vladimir Makarov <vmakarov@redhat.com>
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 2, or (at your option) any
12 later version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING.  If not, write to the Free
21 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 02110-1301, USA.  */
23
24 /* References:
25
26    1. Detecting pipeline structural hazards quickly. T. Proebsting,
27       C. Fraser. Proceedings of ACM SIGPLAN-SIGACT Symposium on
28       Principles of Programming Languages, pages 280--286, 1994.
29
30       This article is a good start point to understand usage of finite
31       state automata for pipeline hazard recognizers.  But I'd
32       recommend the 2nd article for more deep understanding.
33
34    2. Efficient Instruction Scheduling Using Finite State Automata:
35       V. Bala and N. Rubin, Proceedings of MICRO-28.  This is the best
36       article about usage of finite state automata for pipeline hazard
37       recognizers.
38
39    The current implementation is different from the 2nd article in the
40    following:
41
42    1. New operator `|' (alternative) is permitted in functional unit
43       reservation which can be treated deterministically and
44       non-deterministically.
45
46    2. Possibility of usage of nondeterministic automata too.
47
48    3. Possibility to query functional unit reservations for given
49       automaton state.
50
51    4. Several constructions to describe impossible reservations
52       (`exclusion_set', `presence_set', `final_presence_set',
53       `absence_set', and `final_absence_set').
54
55    5. No reverse automata are generated.  Trace instruction scheduling
56       requires this.  It can be easily added in the future if we
57       really need this.
58
59    6. Union of automaton states are not generated yet.  It is planned
60       to be implemented.  Such feature is needed to make more accurate
61       interlock insn scheduling to get state describing functional
62       unit reservation in a joint CFG point.  */
63
64 /* This file code processes constructions of machine description file
65    which describes automaton used for recognition of processor pipeline
66    hazards by insn scheduler and can be used for other tasks (such as
67    VLIW insn packing.
68
69    The translator functions `gen_cpu_unit', `gen_query_cpu_unit',
70    `gen_bypass', `gen_excl_set', `gen_presence_set',
71    `gen_final_presence_set', `gen_absence_set',
72    `gen_final_absence_set', `gen_automaton', `gen_automata_option',
73    `gen_reserv', `gen_insn_reserv' are called from file
74    `genattrtab.c'.  They transform RTL constructions describing
75    automata in .md file into internal representation convenient for
76    further processing.
77
78    The translator major function `expand_automata' processes the
79    description internal representation into finite state automaton.
80    It can be divided on:
81
82      o checking correctness of the automaton pipeline description
83        (major function is `check_all_description').
84
85      o generating automaton (automata) from the description (major
86        function is `make_automaton').
87
88      o optional transformation of nondeterministic finite state
89        automata into deterministic ones if the alternative operator
90        `|' is treated nondeterministically in the description (major
91        function is NDFA_to_DFA).
92
93      o optional minimization of the finite state automata by merging
94        equivalent automaton states (major function is `minimize_DFA').
95
96      o forming tables (some as comb vectors) and attributes
97        representing the automata (functions output_..._table).
98
99    Function `write_automata' outputs the created finite state
100    automaton as different tables and functions which works with the
101    automata to inquire automaton state and to change its state.  These
102    function are used by gcc instruction scheduler and may be some
103    other gcc code.  */
104
105 #include "bconfig.h"
106 #include "system.h"
107 #include "coretypes.h"
108 #include "tm.h"
109 #include "rtl.h"
110 #include "obstack.h"
111 #include "errors.h"
112 #include "gensupport.h"
113
114 #include <math.h>
115 #include "hashtab.h"
116 #include "vec.h"
117
118 #ifndef CHAR_BIT
119 #define CHAR_BIT 8
120 #endif
121
122 /* Positions in machine description file.  Now they are not used.  But
123    they could be used in the future for better diagnostic messages.  */
124 typedef int pos_t;
125
126 /* The following is element of vector of current (and planned in the
127    future) functional unit reservations.  */
128 typedef unsigned HOST_WIDE_INT set_el_t;
129
130 /* Reservations of function units are represented by value of the following
131    type.  */
132 typedef set_el_t *reserv_sets_t;
133
134 /* The following structure describes a ticker.  */
135 struct ticker
136 {
137   /* The following member value is time of the ticker creation with
138      taking into account time when the ticker is off.  Active time of
139      the ticker is current time minus the value.  */
140   int modified_creation_time;
141   /* The following member value is time (incremented by one) when the
142      ticker was off.  Zero value means that now the ticker is on.  */
143   int incremented_off_time;
144 };
145
146 /* The ticker is represented by the following type.  */
147 typedef struct ticker ticker_t;
148
149 /* The following type describes elements of output vectors.  */
150 typedef HOST_WIDE_INT vect_el_t;
151
152 /* Forward declaration of structures of internal representation of
153    pipeline description based on NDFA.  */
154
155 struct unit_decl;
156 struct bypass_decl;
157 struct result_decl;
158 struct automaton_decl;
159 struct unit_pattern_rel_decl;
160 struct reserv_decl;
161 struct insn_reserv_decl;
162 struct decl;
163 struct unit_regexp;
164 struct result_regexp;
165 struct reserv_regexp;
166 struct nothing_regexp;
167 struct sequence_regexp;
168 struct repeat_regexp;
169 struct allof_regexp;
170 struct oneof_regexp;
171 struct regexp;
172 struct description;
173 struct unit_set_el;
174 struct pattern_set_el;
175 struct pattern_reserv;
176 struct state;
177 struct alt_state;
178 struct arc;
179 struct ainsn;
180 struct automaton;
181 struct state_ainsn_table;
182
183 /* The following typedefs are for brevity.  */
184 typedef struct unit_decl *unit_decl_t;
185 typedef struct decl *decl_t;
186 typedef struct regexp *regexp_t;
187 typedef struct unit_set_el *unit_set_el_t;
188 typedef struct pattern_set_el *pattern_set_el_t;
189 typedef struct pattern_reserv *pattern_reserv_t;
190 typedef struct alt_state *alt_state_t;
191 typedef struct state *state_t;
192 typedef struct arc *arc_t;
193 typedef struct ainsn *ainsn_t;
194 typedef struct automaton *automaton_t;
195 typedef struct automata_list_el *automata_list_el_t;
196 typedef struct state_ainsn_table *state_ainsn_table_t;
197
198 /* Undefined position.  */
199 static pos_t no_pos = 0;
200
201 /* All IR is stored in the following obstack.  */
202 static struct obstack irp;
203
204 \f
205 /* Declare vector types for various data structures: */
206
207 DEF_VEC_P(alt_state_t);
208 DEF_VEC_ALLOC_P(alt_state_t,heap);
209 DEF_VEC_P(ainsn_t);
210 DEF_VEC_ALLOC_P(ainsn_t,heap);
211 DEF_VEC_P(state_t);
212 DEF_VEC_ALLOC_P(state_t,heap);
213 DEF_VEC_P(decl_t);
214 DEF_VEC_ALLOC_P(decl_t,heap);
215 DEF_VEC_P(reserv_sets_t);
216 DEF_VEC_ALLOC_P(reserv_sets_t,heap);
217
218 DEF_VEC_I(vect_el_t);
219 DEF_VEC_ALLOC_I(vect_el_t, heap);
220 typedef VEC(vect_el_t,heap) *vla_hwint_t;
221 \f
222 /* Forward declarations of functions used before their definitions, only.  */
223 static regexp_t gen_regexp_sequence    (const char *);
224 static void reserv_sets_or             (reserv_sets_t, reserv_sets_t,
225                                         reserv_sets_t);
226 static reserv_sets_t get_excl_set      (reserv_sets_t);
227 static int check_presence_pattern_sets (reserv_sets_t,
228                                         reserv_sets_t, int);
229 static int check_absence_pattern_sets  (reserv_sets_t, reserv_sets_t,
230                                         int);
231 static arc_t first_out_arc             (state_t);
232 static arc_t next_out_arc              (arc_t);
233
234 \f
235
236 /* Options with the following names can be set up in automata_option
237    construction.  Because the strings occur more one time we use the
238    macros.  */
239
240 #define NO_MINIMIZATION_OPTION "-no-minimization"
241 #define TIME_OPTION "-time"
242 #define STATS_OPTION "-stats"
243 #define V_OPTION "-v"
244 #define W_OPTION "-w"
245 #define NDFA_OPTION "-ndfa"
246 #define PROGRESS_OPTION "-progress"
247
248 /* The following flags are set up by function `initiate_automaton_gen'.  */
249
250 /* Make automata with nondeterministic reservation by insns (`-ndfa').  */
251 static int ndfa_flag;
252
253 /* Do not make minimization of DFA (`-no-minimization').  */
254 static int no_minimization_flag;
255
256 /* Value of this variable is number of automata being generated.  The
257    actual number of automata may be less this value if there is not
258    sufficient number of units.  This value is defined by argument of
259    option `-split' or by constructions automaton if the value is zero
260    (it is default value of the argument).  */
261 static int split_argument;
262
263 /* Flag of output time statistics (`-time').  */
264 static int time_flag;
265
266 /* Flag of automata statistics (`-stats').  */
267 static int stats_flag;
268
269 /* Flag of creation of description file which contains description of
270    result automaton and statistics information (`-v').  */
271 static int v_flag;
272
273 /* Flag of output of a progress bar showing how many states were
274    generated so far for automaton being processed (`-progress').  */
275 static int progress_flag;
276
277 /* Flag of generating warning instead of error for non-critical errors
278    (`-w').  */
279 static int w_flag;
280
281
282 /* Output file for pipeline hazard recognizer (PHR) being generated.
283    The value is NULL if the file is not defined.  */
284 static FILE *output_file;
285
286 /* Description file of PHR.  The value is NULL if the file is not
287    created.  */
288 static FILE *output_description_file;
289
290 /* PHR description file name.  */
291 static char *output_description_file_name;
292
293 /* Value of the following variable is node representing description
294    being processed.  This is start point of IR.  */
295 static struct description *description;
296
297 \f
298
299 /* This page contains description of IR structure (nodes).  */
300
301 enum decl_mode
302 {
303   dm_unit,
304   dm_bypass,
305   dm_automaton,
306   dm_excl,
307   dm_presence,
308   dm_absence,
309   dm_reserv,
310   dm_insn_reserv
311 };
312
313 /* This describes define_cpu_unit and define_query_cpu_unit (see file
314    rtl.def).  */
315 struct unit_decl
316 {
317   const char *name;
318   /* NULL if the automaton name is absent.  */
319   const char *automaton_name;
320   /* If the following value is not zero, the cpu unit reservation is
321      described in define_query_cpu_unit.  */
322   char query_p;
323
324   /* The following fields are defined by checker.  */
325
326   /* The following field value is nonzero if the unit is used in an
327      regexp.  */
328   char unit_is_used;
329
330   /* The following field value is order number (0, 1, ...) of given
331      unit.  */
332   int unit_num;
333   /* The following field value is corresponding declaration of
334      automaton which was given in description.  If the field value is
335      NULL then automaton in the unit declaration was absent.  */
336   struct automaton_decl *automaton_decl;
337   /* The following field value is maximal cycle number (1, ...) on
338      which given unit occurs in insns.  Zero value means that given
339      unit is not used in insns.  */
340   int max_occ_cycle_num;
341   /* The following field value is minimal cycle number (0, ...) on
342      which given unit occurs in insns.  -1 value means that given
343      unit is not used in insns.  */
344   int min_occ_cycle_num;
345   /* The following list contains units which conflict with given
346      unit.  */
347   unit_set_el_t excl_list;
348   /* The following list contains patterns which are required to
349      reservation of given unit.  */
350   pattern_set_el_t presence_list;
351   pattern_set_el_t final_presence_list;
352   /* The following list contains patterns which should be not present
353      in reservation for given unit.  */
354   pattern_set_el_t absence_list;
355   pattern_set_el_t final_absence_list;
356   /* The following is used only when `query_p' has nonzero value.
357      This is query number for the unit.  */
358   int query_num;
359   /* The following is the last cycle on which the unit was checked for
360      correct distributions of units to automata in a regexp.  */
361   int last_distribution_check_cycle;
362
363   /* The following fields are defined by automaton generator.  */
364
365   /* The following field value is number of the automaton to which
366      given unit belongs.  */
367   int corresponding_automaton_num;
368   /* If the following value is not zero, the cpu unit is present in a
369      `exclusion_set' or in right part of a `presence_set',
370      `final_presence_set', `absence_set', and
371      `final_absence_set'define_query_cpu_unit.  */
372   char in_set_p;
373 };
374
375 /* This describes define_bypass (see file rtl.def).  */
376 struct bypass_decl
377 {
378   int latency;
379   const char *out_insn_name;
380   const char *in_insn_name;
381   const char *bypass_guard_name;
382
383   /* The following fields are defined by checker.  */
384
385   /* output and input insns of given bypass.  */
386   struct insn_reserv_decl *out_insn_reserv;
387   struct insn_reserv_decl *in_insn_reserv;
388   /* The next bypass for given output insn.  */
389   struct bypass_decl *next;
390 };
391
392 /* This describes define_automaton (see file rtl.def).  */
393 struct automaton_decl
394 {
395   const char *name;
396
397   /* The following fields are defined by automaton generator.  */
398
399   /* The following field value is nonzero if the automaton is used in
400      an regexp definition.  */
401   char automaton_is_used;
402
403   /* The following fields are defined by checker.  */
404
405   /* The following field value is the corresponding automaton.  This
406      field is not NULL only if the automaton is present in unit
407      declarations and the automatic partition on automata is not
408      used.  */
409   automaton_t corresponding_automaton;
410 };
411
412 /* This describes exclusion relations: exclusion_set (see file
413    rtl.def).  */
414 struct excl_rel_decl
415 {
416   int all_names_num;
417   int first_list_length;
418   char *names [1];
419 };
420
421 /* This describes unit relations: [final_]presence_set or
422    [final_]absence_set (see file rtl.def).  */
423 struct unit_pattern_rel_decl
424 {
425   int final_p;
426   int names_num;
427   int patterns_num;
428   char **names;
429   char ***patterns;
430 };
431
432 /* This describes define_reservation (see file rtl.def).  */
433 struct reserv_decl
434 {
435   const char *name;
436   regexp_t regexp;
437
438   /* The following fields are defined by checker.  */
439
440   /* The following field value is nonzero if the unit is used in an
441      regexp.  */
442   char reserv_is_used;
443   /* The following field is used to check up cycle in expression
444      definition.  */
445   int loop_pass_num;
446 };
447
448 /* This describes define_insn_reservation (see file rtl.def).  */
449 struct insn_reserv_decl
450 {
451   rtx condexp;
452   int default_latency;
453   regexp_t regexp;
454   const char *name;
455
456   /* The following fields are defined by checker.  */
457
458   /* The following field value is order number (0, 1, ...) of given
459      insn.  */
460   int insn_num;
461   /* The following field value is list of bypasses in which given insn
462      is output insn.  */
463   struct bypass_decl *bypass_list;
464
465   /* The following fields are defined by automaton generator.  */
466
467   /* The following field is the insn regexp transformed that
468      the regexp has not optional regexp, repetition regexp, and an
469      reservation name (i.e. reservation identifiers are changed by the
470      corresponding regexp) and all alternations are the topest level
471      of the regexp.  The value can be NULL only if it is special
472      insn `cycle advancing'.  */
473   regexp_t transformed_regexp;
474   /* The following field value is list of arcs marked given
475      insn.  The field is used in transformation NDFA -> DFA.  */
476   arc_t arcs_marked_by_insn;
477   /* The two following fields are used during minimization of a finite state
478      automaton.  */
479   /* The field value is number of equivalence class of state into
480      which arc marked by given insn enters from a state (fixed during
481      an automaton minimization).  */
482   int equiv_class_num;
483   /* The following member value is the list to automata which can be
484      changed by the insn issue.  */
485   automata_list_el_t important_automata_list;
486   /* The following member is used to process insn once for output.  */
487   int processed_p;
488 };
489
490 /* This contains a declaration mentioned above.  */
491 struct decl
492 {
493   /* What node in the union? */
494   enum decl_mode mode;
495   pos_t pos;
496   union
497   {
498     struct unit_decl unit;
499     struct bypass_decl bypass;
500     struct automaton_decl automaton;
501     struct excl_rel_decl excl;
502     struct unit_pattern_rel_decl presence;
503     struct unit_pattern_rel_decl absence;
504     struct reserv_decl reserv;
505     struct insn_reserv_decl insn_reserv;
506   } decl;
507 };
508
509 /* The following structures represent parsed reservation strings.  */
510 enum regexp_mode
511 {
512   rm_unit,
513   rm_reserv,
514   rm_nothing,
515   rm_sequence,
516   rm_repeat,
517   rm_allof,
518   rm_oneof
519 };
520
521 /* Cpu unit in reservation.  */
522 struct unit_regexp
523 {
524   const char *name;
525   unit_decl_t unit_decl;
526 };
527
528 /* Define_reservation in a reservation.  */
529 struct reserv_regexp
530 {
531   const char *name;
532   struct reserv_decl *reserv_decl;
533 };
534
535 /* Absence of reservation (represented by string `nothing').  */
536 struct nothing_regexp
537 {
538   /* This used to be empty but ISO C doesn't allow that.  */
539   char unused;
540 };
541
542 /* Representation of reservations separated by ',' (see file
543    rtl.def).  */
544 struct sequence_regexp
545 {
546   int regexps_num;
547   regexp_t regexps [1];
548 };
549
550 /* Representation of construction `repeat' (see file rtl.def).  */
551 struct repeat_regexp
552 {
553   int repeat_num;
554   regexp_t regexp;
555 };
556
557 /* Representation of reservations separated by '+' (see file
558    rtl.def).  */
559 struct allof_regexp
560 {
561   int regexps_num;
562   regexp_t regexps [1];
563 };
564
565 /* Representation of reservations separated by '|' (see file
566    rtl.def).  */
567 struct oneof_regexp
568 {
569   int regexps_num;
570   regexp_t regexps [1];
571 };
572
573 /* Representation of a reservation string.  */
574 struct regexp
575 {
576   /* What node in the union? */
577   enum regexp_mode mode;
578   pos_t pos;
579   union
580   {
581     struct unit_regexp unit;
582     struct reserv_regexp reserv;
583     struct nothing_regexp nothing;
584     struct sequence_regexp sequence;
585     struct repeat_regexp repeat;
586     struct allof_regexp allof;
587     struct oneof_regexp oneof;
588   } regexp;
589 };
590
591 /* Represents description of pipeline hazard description based on
592    NDFA.  */
593 struct description
594 {
595   int decls_num;
596
597   /* The following fields are defined by checker.  */
598
599   /* The following fields values are correspondingly number of all
600      units, query units, and insns in the description.  */
601   int units_num;
602   int query_units_num;
603   int insns_num;
604   /* The following field value is max length (in cycles) of
605      reservations of insns.  The field value is defined only for
606      correct programs.  */
607   int max_insn_reserv_cycles;
608
609   /* The following fields are defined by automaton generator.  */
610
611   /* The following field value is the first automaton.  */
612   automaton_t first_automaton;
613
614   /* The following field is created by pipeline hazard parser and
615      contains all declarations.  We allocate additional entry for
616      special insn "cycle advancing" which is added by the automaton
617      generator.  */
618   decl_t decls [1];
619 };
620
621
622 /* The following nodes are created in automaton checker.  */
623
624 /* The following nodes represent exclusion set for cpu units.  Each
625    element is accessed through only one excl_list.  */
626 struct unit_set_el
627 {
628   unit_decl_t unit_decl;
629   unit_set_el_t next_unit_set_el;
630 };
631
632 /* The following nodes represent presence or absence pattern for cpu
633    units.  Each element is accessed through only one presence_list or
634    absence_list.  */
635 struct pattern_set_el
636 {
637   /* The number of units in unit_decls.  */
638   int units_num;
639   /* The units forming the pattern.  */
640   struct unit_decl **unit_decls;
641   pattern_set_el_t next_pattern_set_el;
642 };
643
644
645 /* The following nodes are created in automaton generator.  */
646
647
648 /* The following nodes represent presence or absence pattern for cpu
649    units.  Each element is accessed through only one element of
650    unit_presence_set_table or unit_absence_set_table.  */
651 struct pattern_reserv
652 {
653   reserv_sets_t reserv;
654   pattern_reserv_t next_pattern_reserv;
655 };
656
657 /* The following node type describes state automaton.  The state may
658    be deterministic or non-deterministic.  Non-deterministic state has
659    several component states which represent alternative cpu units
660    reservations.  The state also is used for describing a
661    deterministic reservation of automaton insn.  */
662 struct state
663 {
664   /* The following member value is nonzero if there is a transition by
665      cycle advancing.  */
666   int new_cycle_p;
667   /* The following field is list of processor unit reservations on
668      each cycle.  */
669   reserv_sets_t reservs;
670   /* The following field is unique number of given state between other
671      states.  */
672   int unique_num;
673   /* The following field value is automaton to which given state
674      belongs.  */
675   automaton_t automaton;
676   /* The following field value is the first arc output from given
677      state.  */
678   arc_t first_out_arc;
679   unsigned int num_out_arcs;
680   /* The following field is used to form NDFA.  */
681   char it_was_placed_in_stack_for_NDFA_forming;
682   /* The following field is used to form DFA.  */
683   char it_was_placed_in_stack_for_DFA_forming;
684   /* The following field is used to transform NDFA to DFA and DFA
685      minimization.  The field value is not NULL if the state is a
686      compound state.  In this case the value of field `unit_sets_list'
687      is NULL.  All states in the list are in the hash table.  The list
688      is formed through field `next_sorted_alt_state'.  We should
689      support only one level of nesting state.  */
690   alt_state_t component_states;
691   /* The following field is used for passing graph of states.  */
692   int pass_num;
693   /* The list of states belonging to one equivalence class is formed
694      with the aid of the following field.  */
695   state_t next_equiv_class_state;
696   /* The two following fields are used during minimization of a finite
697      state automaton.  */
698   int equiv_class_num_1, equiv_class_num_2;
699   /* The following field is used during minimization of a finite state
700      automaton.  The field value is state corresponding to equivalence
701      class to which given state belongs.  */
702   state_t equiv_class_state;
703   unsigned int *presence_signature;
704   /* The following field value is the order number of given state.
705      The states in final DFA is enumerated with the aid of the
706      following field.  */
707   int order_state_num;
708   /* This member is used for passing states for searching minimal
709      delay time.  */
710   int state_pass_num;
711   /* The following member is used to evaluate min issue delay of insn
712      for a state.  */
713   int min_insn_issue_delay;
714 };
715
716 /* Automaton arc.  */
717 struct arc
718 {
719   /* The following field refers for the state into which given arc
720      enters.  */
721   state_t to_state;
722   /* The following field describes that the insn issue (with cycle
723      advancing for special insn `cycle advancing' and without cycle
724      advancing for others) makes transition from given state to
725      another given state.  */
726   ainsn_t insn;
727   /* The following field value is the next arc output from the same
728      state.  */
729   arc_t next_out_arc;
730   /* List of arcs marked given insn is formed with the following
731      field.  The field is used in transformation NDFA -> DFA.  */
732   arc_t next_arc_marked_by_insn;
733 };
734
735 /* The following node type describes a deterministic alternative in
736    non-deterministic state which characterizes cpu unit reservations
737    of automaton insn or which is part of NDFA.  */
738 struct alt_state
739 {
740   /* The following field is a deterministic state which characterizes
741      unit reservations of the instruction.  */
742   state_t state;
743   /* The following field refers to the next state which characterizes
744      unit reservations of the instruction.  */
745   alt_state_t next_alt_state;
746   /* The following field refers to the next state in sorted list.  */
747   alt_state_t next_sorted_alt_state;
748 };
749
750 /* The following node type describes insn of automaton.  They are
751    labels of FA arcs.  */
752 struct ainsn
753 {
754   /* The following field value is the corresponding insn declaration
755      of description.  */
756   struct insn_reserv_decl *insn_reserv_decl;
757   /* The following field value is the next insn declaration for an
758      automaton.  */
759   ainsn_t next_ainsn;
760   /* The following field is states which characterize automaton unit
761      reservations of the instruction.  The value can be NULL only if it
762      is special insn `cycle advancing'.  */
763   alt_state_t alt_states;
764   /* The following field is sorted list of states which characterize
765      automaton unit reservations of the instruction.  The value can be
766      NULL only if it is special insn `cycle advancing'.  */
767   alt_state_t sorted_alt_states;
768   /* The following field refers the next automaton insn with
769      the same reservations.  */
770   ainsn_t next_same_reservs_insn;
771   /* The following field is flag of the first automaton insn with the
772      same reservations in the declaration list.  Only arcs marked such
773      insn is present in the automaton.  This significantly decreases
774      memory requirements especially when several automata are
775      formed.  */
776   char first_insn_with_same_reservs;
777   /* The following member has nonzero value if there is arc from state of
778      the automaton marked by the ainsn.  */
779   char arc_exists_p;
780   /* Cyclic list of insns of an equivalence class is formed with the
781      aid of the following field.  */
782   ainsn_t next_equiv_class_insn;
783   /* The following field value is nonzero if the insn declaration is
784      the first insn declaration with given equivalence number.  */
785   char first_ainsn_with_given_equivalence_num;
786   /* The following field is number of class of equivalence of insns.
787      It is necessary because many insns may be equivalent with the
788      point of view of pipeline hazards.  */
789   int insn_equiv_class_num;
790   /* The following member value is TRUE if there is an arc in the
791      automaton marked by the insn into another state.  In other
792      words, the insn can change the state of the automaton.  */
793   int important_p;
794 };
795
796 /* The following describes an automaton for PHR.  */
797 struct automaton
798 {
799   /* The following field value is the list of insn declarations for
800      given automaton.  */
801   ainsn_t ainsn_list;
802   /* The following field value is the corresponding automaton
803      declaration.  This field is not NULL only if the automatic
804      partition on automata is not used.  */
805   struct automaton_decl *corresponding_automaton_decl;
806   /* The following field value is the next automaton.  */
807   automaton_t next_automaton;
808   /* The following field is start state of FA.  There are not unit
809      reservations in the state.  */
810   state_t start_state;
811   /* The following field value is number of equivalence classes of
812      insns (see field `insn_equiv_class_num' in
813      `insn_reserv_decl').  */
814   int insn_equiv_classes_num;
815   /* The following field value is number of states of final DFA.  */
816   int achieved_states_num;
817   /* The following field value is the order number (0, 1, ...) of
818      given automaton.  */
819   int automaton_order_num;
820   /* The following fields contain statistics information about
821      building automaton.  */
822   int NDFA_states_num, DFA_states_num;
823   /* The following field value is defined only if minimization of DFA
824      is used.  */
825   int minimal_DFA_states_num;
826   int NDFA_arcs_num, DFA_arcs_num;
827   /* The following field value is defined only if minimization of DFA
828      is used.  */
829   int minimal_DFA_arcs_num;
830   /* The following member refers for two table state x ainsn -> int.
831      ??? Above sentence is incomprehensible.  */
832   state_ainsn_table_t trans_table;
833   /* The following member value is maximal value of min issue delay
834      for insns of the automaton.  */
835   int max_min_delay;
836   /* Usually min issue delay is small and we can place several (2, 4,
837      8) elements in one vector element.  So the compression factor can
838      be 1 (no compression), 2, 4, 8.  */
839   int min_issue_delay_table_compression_factor;
840   /* Total number of locked states in this automaton.  */
841   int locked_states;
842 };
843
844 /* The following is the element of the list of automata.  */
845 struct automata_list_el
846 {
847   /* The automaton itself.  */
848   automaton_t automaton;
849   /* The next automata set element.  */
850   automata_list_el_t next_automata_list_el;
851 };
852
853 /* The following structure describes a table state X ainsn -> int(>= 0).  */
854 struct state_ainsn_table
855 {
856   /* Automaton to which given table belongs.  */
857   automaton_t automaton;
858   /* The following tree vectors for comb vector implementation of the
859      table.  */
860   vla_hwint_t comb_vect;
861   vla_hwint_t check_vect;
862   vla_hwint_t base_vect;
863   /* This is simple implementation of the table.  */
864   vla_hwint_t full_vect;
865   /* Minimal and maximal values of the previous vectors.  */
866   int min_comb_vect_el_value, max_comb_vect_el_value;
867   int min_base_vect_el_value, max_base_vect_el_value;
868 };
869
870 /* Macros to access members of unions.  Use only them for access to
871    union members of declarations and regexps.  */
872
873 #if defined ENABLE_CHECKING && (GCC_VERSION >= 2007)
874
875 #define DECL_UNIT(d) __extension__                                      \
876 (({ struct decl *const _decl = (d);                                     \
877      if (_decl->mode != dm_unit)                                        \
878        decl_mode_check_failed (_decl->mode, "dm_unit",                  \
879                                __FILE__, __LINE__, __FUNCTION__);       \
880      &(_decl)->decl.unit; }))
881
882 #define DECL_BYPASS(d) __extension__                                    \
883 (({ struct decl *const _decl = (d);                                     \
884      if (_decl->mode != dm_bypass)                                      \
885        decl_mode_check_failed (_decl->mode, "dm_bypass",                \
886                                __FILE__, __LINE__, __FUNCTION__);       \
887      &(_decl)->decl.bypass; }))
888
889 #define DECL_AUTOMATON(d) __extension__                                 \
890 (({ struct decl *const _decl = (d);                                     \
891      if (_decl->mode != dm_automaton)                                   \
892        decl_mode_check_failed (_decl->mode, "dm_automaton",             \
893                                __FILE__, __LINE__, __FUNCTION__);       \
894      &(_decl)->decl.automaton; }))
895
896 #define DECL_EXCL(d) __extension__                                      \
897 (({ struct decl *const _decl = (d);                                     \
898      if (_decl->mode != dm_excl)                                        \
899        decl_mode_check_failed (_decl->mode, "dm_excl",                  \
900                                __FILE__, __LINE__, __FUNCTION__);       \
901      &(_decl)->decl.excl; }))
902
903 #define DECL_PRESENCE(d) __extension__                                  \
904 (({ struct decl *const _decl = (d);                                     \
905      if (_decl->mode != dm_presence)                                    \
906        decl_mode_check_failed (_decl->mode, "dm_presence",              \
907                                __FILE__, __LINE__, __FUNCTION__);       \
908      &(_decl)->decl.presence; }))
909
910 #define DECL_ABSENCE(d) __extension__                                   \
911 (({ struct decl *const _decl = (d);                                     \
912      if (_decl->mode != dm_absence)                                     \
913        decl_mode_check_failed (_decl->mode, "dm_absence",               \
914                                __FILE__, __LINE__, __FUNCTION__);       \
915      &(_decl)->decl.absence; }))
916
917 #define DECL_RESERV(d) __extension__                                    \
918 (({ struct decl *const _decl = (d);                                     \
919      if (_decl->mode != dm_reserv)                                      \
920        decl_mode_check_failed (_decl->mode, "dm_reserv",                \
921                                __FILE__, __LINE__, __FUNCTION__);       \
922      &(_decl)->decl.reserv; }))
923
924 #define DECL_INSN_RESERV(d) __extension__                               \
925 (({ struct decl *const _decl = (d);                                     \
926      if (_decl->mode != dm_insn_reserv)                                 \
927        decl_mode_check_failed (_decl->mode, "dm_insn_reserv",           \
928                                __FILE__, __LINE__, __FUNCTION__);       \
929      &(_decl)->decl.insn_reserv; }))
930
931 static const char *decl_name (enum decl_mode);
932 static void decl_mode_check_failed (enum decl_mode, const char *,
933                                     const char *, int, const char *)
934      ATTRIBUTE_NORETURN;
935
936 /* Return string representation of declaration mode MODE.  */
937 static const char *
938 decl_name (enum decl_mode mode)
939 {
940   static char str [100];
941
942   if (mode == dm_unit)
943     return "dm_unit";
944   else if (mode == dm_bypass)
945     return "dm_bypass";
946   else if (mode == dm_automaton)
947     return "dm_automaton";
948   else if (mode == dm_excl)
949     return "dm_excl";
950   else if (mode == dm_presence)
951     return "dm_presence";
952   else if (mode == dm_absence)
953     return "dm_absence";
954   else if (mode == dm_reserv)
955     return "dm_reserv";
956   else if (mode == dm_insn_reserv)
957     return "dm_insn_reserv";
958   else
959     sprintf (str, "unknown (%d)", (int) mode);
960   return str;
961 }
962
963 /* The function prints message about unexpected declaration and finish
964    the program.  */
965 static void
966 decl_mode_check_failed (enum decl_mode mode, const char *expected_mode_str,
967                         const char *file, int line, const char *func)
968 {
969   fprintf
970     (stderr,
971      "\n%s: %d: error in %s: DECL check: expected decl %s, have %s\n",
972      file, line, func, expected_mode_str, decl_name (mode));
973   exit (1);
974 }
975
976
977 #define REGEXP_UNIT(r) __extension__                                    \
978 (({ struct regexp *const _regexp = (r);                                 \
979      if (_regexp->mode != rm_unit)                                      \
980        regexp_mode_check_failed (_regexp->mode, "rm_unit",              \
981                                __FILE__, __LINE__, __FUNCTION__);       \
982      &(_regexp)->regexp.unit; }))
983
984 #define REGEXP_RESERV(r) __extension__                                  \
985 (({ struct regexp *const _regexp = (r);                                 \
986      if (_regexp->mode != rm_reserv)                                    \
987        regexp_mode_check_failed (_regexp->mode, "rm_reserv",            \
988                                __FILE__, __LINE__, __FUNCTION__);       \
989      &(_regexp)->regexp.reserv; }))
990
991 #define REGEXP_SEQUENCE(r) __extension__                                \
992 (({ struct regexp *const _regexp = (r);                                 \
993      if (_regexp->mode != rm_sequence)                                  \
994        regexp_mode_check_failed (_regexp->mode, "rm_sequence",          \
995                                __FILE__, __LINE__, __FUNCTION__);       \
996      &(_regexp)->regexp.sequence; }))
997
998 #define REGEXP_REPEAT(r) __extension__                                  \
999 (({ struct regexp *const _regexp = (r);                                 \
1000      if (_regexp->mode != rm_repeat)                                    \
1001        regexp_mode_check_failed (_regexp->mode, "rm_repeat",            \
1002                                __FILE__, __LINE__, __FUNCTION__);       \
1003      &(_regexp)->regexp.repeat; }))
1004
1005 #define REGEXP_ALLOF(r) __extension__                                   \
1006 (({ struct regexp *const _regexp = (r);                                 \
1007      if (_regexp->mode != rm_allof)                                     \
1008        regexp_mode_check_failed (_regexp->mode, "rm_allof",             \
1009                                __FILE__, __LINE__, __FUNCTION__);       \
1010      &(_regexp)->regexp.allof; }))
1011
1012 #define REGEXP_ONEOF(r) __extension__                                   \
1013 (({ struct regexp *const _regexp = (r);                                 \
1014      if (_regexp->mode != rm_oneof)                                     \
1015        regexp_mode_check_failed (_regexp->mode, "rm_oneof",             \
1016                                __FILE__, __LINE__, __FUNCTION__);       \
1017      &(_regexp)->regexp.oneof; }))
1018
1019 static const char *regexp_name (enum regexp_mode);
1020 static void regexp_mode_check_failed (enum regexp_mode, const char *,
1021                                       const char *, int,
1022                                       const char *) ATTRIBUTE_NORETURN;
1023
1024
1025 /* Return string representation of regexp mode MODE.  */
1026 static const char *
1027 regexp_name (enum regexp_mode mode)
1028 {
1029   switch (mode)
1030     {
1031     case rm_unit:
1032       return "rm_unit";
1033     case rm_reserv:
1034       return "rm_reserv";
1035     case rm_nothing:
1036       return "rm_nothing";
1037     case rm_sequence:
1038       return "rm_sequence";
1039     case rm_repeat:
1040       return "rm_repeat";
1041     case rm_allof:
1042       return "rm_allof";
1043     case rm_oneof:
1044       return "rm_oneof";
1045     default:
1046       gcc_unreachable ();
1047     }
1048 }
1049
1050 /* The function prints message about unexpected regexp and finish the
1051    program.  */
1052 static void
1053 regexp_mode_check_failed (enum regexp_mode mode,
1054                           const char *expected_mode_str,
1055                           const char *file, int line, const char *func)
1056 {
1057   fprintf
1058     (stderr,
1059      "\n%s: %d: error in %s: REGEXP check: expected decl %s, have %s\n",
1060      file, line, func, expected_mode_str, regexp_name (mode));
1061   exit (1);
1062 }
1063
1064 #else /* #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007) */
1065
1066 #define DECL_UNIT(d) (&(d)->decl.unit)
1067 #define DECL_BYPASS(d) (&(d)->decl.bypass)
1068 #define DECL_AUTOMATON(d) (&(d)->decl.automaton)
1069 #define DECL_EXCL(d) (&(d)->decl.excl)
1070 #define DECL_PRESENCE(d) (&(d)->decl.presence)
1071 #define DECL_ABSENCE(d) (&(d)->decl.absence)
1072 #define DECL_RESERV(d) (&(d)->decl.reserv)
1073 #define DECL_INSN_RESERV(d) (&(d)->decl.insn_reserv)
1074
1075 #define REGEXP_UNIT(r) (&(r)->regexp.unit)
1076 #define REGEXP_RESERV(r) (&(r)->regexp.reserv)
1077 #define REGEXP_SEQUENCE(r) (&(r)->regexp.sequence)
1078 #define REGEXP_REPEAT(r) (&(r)->regexp.repeat)
1079 #define REGEXP_ALLOF(r) (&(r)->regexp.allof)
1080 #define REGEXP_ONEOF(r) (&(r)->regexp.oneof)
1081
1082 #endif /* #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007) */
1083
1084 /* Create IR structure (node).  */
1085 static void *
1086 create_node (size_t size)
1087 {
1088   void *result;
1089
1090   obstack_blank (&irp, size);
1091   result = obstack_base (&irp);
1092   obstack_finish (&irp);
1093   /* Default values of members are NULL and zero.  */
1094   memset (result, 0, size);
1095   return result;
1096 }
1097
1098 /* Copy IR structure (node).  */
1099 static void *
1100 copy_node (const void *from, size_t size)
1101 {
1102   void *const result = create_node (size);
1103   memcpy (result, from, size);
1104   return result;
1105 }
1106
1107 /* The function checks that NAME does not contain quotes (`"').  */
1108 static const char *
1109 check_name (const char * name, pos_t pos ATTRIBUTE_UNUSED)
1110 {
1111   const char *str;
1112
1113   for (str = name; *str != '\0'; str++)
1114     if (*str == '\"')
1115       error ("Name `%s' contains quotes", name);
1116   return name;
1117 }
1118
1119 /* Pointers to all declarations during IR generation are stored in the
1120    following.  */
1121 static VEC(decl_t,heap) *decls;
1122
1123 /* Given a pointer to a (char *) and a separator, return an alloc'ed
1124    string containing the next separated element, taking parentheses
1125    into account if PAR_FLAG has nonzero value.  Advance the pointer to
1126    after the string scanned, or the end-of-string.  Return NULL if at
1127    end of string.  */
1128 static char *
1129 next_sep_el (const char **pstr, int sep, int par_flag)
1130 {
1131   char *out_str;
1132   const char *p;
1133   int pars_num;
1134   int n_spaces;
1135
1136   /* Remove leading whitespaces.  */
1137   while (ISSPACE ((int) **pstr))
1138     (*pstr)++;
1139
1140   if (**pstr == '\0')
1141     return NULL;
1142
1143   n_spaces = 0;
1144   for (pars_num = 0, p = *pstr; *p != '\0'; p++)
1145     {
1146       if (par_flag && *p == '(')
1147         pars_num++;
1148       else if (par_flag && *p == ')')
1149         pars_num--;
1150       else if (pars_num == 0 && *p == sep)
1151         break;
1152       if (pars_num == 0 && ISSPACE ((int) *p))
1153         n_spaces++;
1154       else
1155         {
1156           for (; n_spaces != 0; n_spaces--)
1157             obstack_1grow (&irp, p [-n_spaces]);
1158           obstack_1grow (&irp, *p);
1159         }
1160     }
1161   obstack_1grow (&irp, '\0');
1162   out_str = obstack_base (&irp);
1163   obstack_finish (&irp);
1164
1165   *pstr = p;
1166   if (**pstr == sep)
1167     (*pstr)++;
1168
1169   return out_str;
1170 }
1171
1172 /* Given a string and a separator, return the number of separated
1173    elements in it, taking parentheses into account if PAR_FLAG has
1174    nonzero value.  Return 0 for the null string, -1 if parentheses is
1175    not balanced.  */
1176 static int
1177 n_sep_els (const char *s, int sep, int par_flag)
1178 {
1179   int n;
1180   int pars_num;
1181
1182   if (*s == '\0')
1183     return 0;
1184
1185   for (pars_num = 0, n = 1; *s; s++)
1186     if (par_flag && *s == '(')
1187       pars_num++;
1188     else if (par_flag && *s == ')')
1189       pars_num--;
1190     else if (pars_num == 0 && *s == sep)
1191       n++;
1192
1193   return (pars_num != 0 ? -1 : n);
1194 }
1195
1196 /* Given a string and a separator, return vector of strings which are
1197    elements in the string and number of elements through els_num.
1198    Take parentheses into account if PAREN_P has nonzero value.  The
1199    function also inserts the end marker NULL at the end of vector.
1200    Return 0 for the null string, -1 if parentheses are not balanced.  */
1201 static char **
1202 get_str_vect (const char *str, int *els_num, int sep, int paren_p)
1203 {
1204   int i;
1205   char **vect;
1206   const char **pstr;
1207   char *trail;
1208
1209   *els_num = n_sep_els (str, sep, paren_p);
1210   if (*els_num <= 0)
1211     return NULL;
1212   obstack_blank (&irp, sizeof (char *) * (*els_num + 1));
1213   vect = (char **) obstack_base (&irp);
1214   obstack_finish (&irp);
1215   pstr = &str;
1216   for (i = 0; i < *els_num; i++)
1217     vect [i] = next_sep_el (pstr, sep, paren_p);
1218   trail = next_sep_el (pstr, sep, paren_p);
1219   gcc_assert (!trail);
1220   vect [i] = NULL;
1221   return vect;
1222 }
1223
1224 /* Process a DEFINE_CPU_UNIT.
1225
1226    This gives information about a unit contained in CPU.  We fill a
1227    struct unit_decl with information used later by `expand_automata'.  */
1228 static void
1229 gen_cpu_unit (rtx def)
1230 {
1231   decl_t decl;
1232   char **str_cpu_units;
1233   int vect_length;
1234   int i;
1235
1236   str_cpu_units = get_str_vect (XSTR (def, 0), &vect_length, ',', FALSE);
1237   if (str_cpu_units == NULL)
1238     fatal ("invalid string `%s' in define_cpu_unit", XSTR (def, 0));
1239   for (i = 0; i < vect_length; i++)
1240     {
1241       decl = create_node (sizeof (struct decl));
1242       decl->mode = dm_unit;
1243       decl->pos = 0;
1244       DECL_UNIT (decl)->name = check_name (str_cpu_units [i], decl->pos);
1245       DECL_UNIT (decl)->automaton_name = XSTR (def, 1);
1246       DECL_UNIT (decl)->query_p = 0;
1247       DECL_UNIT (decl)->min_occ_cycle_num = -1;
1248       DECL_UNIT (decl)->in_set_p = 0;
1249       VEC_safe_push (decl_t,heap, decls, decl);
1250     }
1251 }
1252
1253 /* Process a DEFINE_QUERY_CPU_UNIT.
1254
1255    This gives information about a unit contained in CPU.  We fill a
1256    struct unit_decl with information used later by `expand_automata'.  */
1257 static void
1258 gen_query_cpu_unit (rtx def)
1259 {
1260   decl_t decl;
1261   char **str_cpu_units;
1262   int vect_length;
1263   int i;
1264
1265   str_cpu_units = get_str_vect (XSTR (def, 0), &vect_length, ',',
1266                                 FALSE);
1267   if (str_cpu_units == NULL)
1268     fatal ("invalid string `%s' in define_query_cpu_unit", XSTR (def, 0));
1269   for (i = 0; i < vect_length; i++)
1270     {
1271       decl = create_node (sizeof (struct decl));
1272       decl->mode = dm_unit;
1273       decl->pos = 0;
1274       DECL_UNIT (decl)->name = check_name (str_cpu_units [i], decl->pos);
1275       DECL_UNIT (decl)->automaton_name = XSTR (def, 1);
1276       DECL_UNIT (decl)->query_p = 1;
1277       VEC_safe_push (decl_t,heap, decls, decl);
1278     }
1279 }
1280
1281 /* Process a DEFINE_BYPASS.
1282
1283    This gives information about a unit contained in the CPU.  We fill
1284    in a struct bypass_decl with information used later by
1285    `expand_automata'.  */
1286 static void
1287 gen_bypass (rtx def)
1288 {
1289   decl_t decl;
1290   char **out_insns;
1291   int out_length;
1292   char **in_insns;
1293   int in_length;
1294   int i, j;
1295
1296   out_insns = get_str_vect (XSTR (def, 1), &out_length, ',', FALSE);
1297   if (out_insns == NULL)
1298     fatal ("invalid string `%s' in define_bypass", XSTR (def, 1));
1299   in_insns = get_str_vect (XSTR (def, 2), &in_length, ',', FALSE);
1300   if (in_insns == NULL)
1301     fatal ("invalid string `%s' in define_bypass", XSTR (def, 2));
1302   for (i = 0; i < out_length; i++)
1303     for (j = 0; j < in_length; j++)
1304       {
1305         decl = create_node (sizeof (struct decl));
1306         decl->mode = dm_bypass;
1307         decl->pos = 0;
1308         DECL_BYPASS (decl)->latency = XINT (def, 0);
1309         DECL_BYPASS (decl)->out_insn_name = out_insns [i];
1310         DECL_BYPASS (decl)->in_insn_name = in_insns [j];
1311         DECL_BYPASS (decl)->bypass_guard_name = XSTR (def, 3);
1312         VEC_safe_push (decl_t,heap, decls, decl);
1313       }
1314 }
1315
1316 /* Process an EXCLUSION_SET.
1317
1318    This gives information about a cpu unit conflicts.  We fill a
1319    struct excl_rel_decl (excl) with information used later by
1320    `expand_automata'.  */
1321 static void
1322 gen_excl_set (rtx def)
1323 {
1324   decl_t decl;
1325   char **first_str_cpu_units;
1326   char **second_str_cpu_units;
1327   int first_vect_length;
1328   int length;
1329   int i;
1330
1331   first_str_cpu_units
1332     = get_str_vect (XSTR (def, 0), &first_vect_length, ',', FALSE);
1333   if (first_str_cpu_units == NULL)
1334     fatal ("invalid first string `%s' in exclusion_set", XSTR (def, 0));
1335   second_str_cpu_units = get_str_vect (XSTR (def, 1), &length, ',',
1336                                        FALSE);
1337   if (second_str_cpu_units == NULL)
1338     fatal ("invalid second string `%s' in exclusion_set", XSTR (def, 1));
1339   length += first_vect_length;
1340   decl = create_node (sizeof (struct decl) + (length - 1) * sizeof (char *));
1341   decl->mode = dm_excl;
1342   decl->pos = 0;
1343   DECL_EXCL (decl)->all_names_num = length;
1344   DECL_EXCL (decl)->first_list_length = first_vect_length;
1345   for (i = 0; i < length; i++)
1346     if (i < first_vect_length)
1347       DECL_EXCL (decl)->names [i] = first_str_cpu_units [i];
1348     else
1349       DECL_EXCL (decl)->names [i]
1350         = second_str_cpu_units [i - first_vect_length];
1351   VEC_safe_push (decl_t,heap, decls, decl);
1352 }
1353
1354 /* Process a PRESENCE_SET, a FINAL_PRESENCE_SET, an ABSENCE_SET,
1355    FINAL_ABSENCE_SET (it is depended on PRESENCE_P and FINAL_P).
1356
1357    This gives information about a cpu unit reservation requirements.
1358    We fill a struct unit_pattern_rel_decl with information used later
1359    by `expand_automata'.  */
1360 static void
1361 gen_presence_absence_set (rtx def, int presence_p, int final_p)
1362 {
1363   decl_t decl;
1364   char **str_cpu_units;
1365   char **str_pattern_lists;
1366   char ***str_patterns;
1367   int cpu_units_length;
1368   int length;
1369   int patterns_length;
1370   int i;
1371
1372   str_cpu_units = get_str_vect (XSTR (def, 0), &cpu_units_length, ',',
1373                                 FALSE);
1374   if (str_cpu_units == NULL)
1375     fatal ((presence_p
1376             ? (final_p
1377                ? "invalid first string `%s' in final_presence_set"
1378                : "invalid first string `%s' in presence_set")
1379             : (final_p
1380                ? "invalid first string `%s' in final_absence_set"
1381                : "invalid first string `%s' in absence_set")),
1382            XSTR (def, 0));
1383   str_pattern_lists = get_str_vect (XSTR (def, 1),
1384                                     &patterns_length, ',', FALSE);
1385   if (str_pattern_lists == NULL)
1386     fatal ((presence_p
1387             ? (final_p
1388                ? "invalid second string `%s' in final_presence_set"
1389                : "invalid second string `%s' in presence_set")
1390             : (final_p
1391                ? "invalid second string `%s' in final_absence_set"
1392                : "invalid second string `%s' in absence_set")), XSTR (def, 1));
1393   str_patterns = obstack_alloc (&irp, patterns_length * sizeof (char **));
1394   for (i = 0; i < patterns_length; i++)
1395     {
1396       str_patterns [i] = get_str_vect (str_pattern_lists [i],
1397                                        &length, ' ', FALSE);
1398       gcc_assert (str_patterns [i]);
1399     }
1400   decl = create_node (sizeof (struct decl));
1401   decl->pos = 0;
1402   if (presence_p)
1403     {
1404       decl->mode = dm_presence;
1405       DECL_PRESENCE (decl)->names_num = cpu_units_length;
1406       DECL_PRESENCE (decl)->names = str_cpu_units;
1407       DECL_PRESENCE (decl)->patterns = str_patterns;
1408       DECL_PRESENCE (decl)->patterns_num = patterns_length;
1409       DECL_PRESENCE (decl)->final_p = final_p;
1410     }
1411   else
1412     {
1413       decl->mode = dm_absence;
1414       DECL_ABSENCE (decl)->names_num = cpu_units_length;
1415       DECL_ABSENCE (decl)->names = str_cpu_units;
1416       DECL_ABSENCE (decl)->patterns = str_patterns;
1417       DECL_ABSENCE (decl)->patterns_num = patterns_length;
1418       DECL_ABSENCE (decl)->final_p = final_p;
1419     }
1420   VEC_safe_push (decl_t,heap, decls, decl);
1421 }
1422
1423 /* Process a PRESENCE_SET.
1424
1425     This gives information about a cpu unit reservation requirements.
1426    We fill a struct unit_pattern_rel_decl (presence) with information
1427    used later by `expand_automata'.  */
1428 static void
1429 gen_presence_set (rtx def)
1430 {
1431   gen_presence_absence_set (def, TRUE, FALSE);
1432 }
1433
1434 /* Process a FINAL_PRESENCE_SET.
1435
1436    This gives information about a cpu unit reservation requirements.
1437    We fill a struct unit_pattern_rel_decl (presence) with information
1438    used later by `expand_automata'.  */
1439 static void
1440 gen_final_presence_set (rtx def)
1441 {
1442   gen_presence_absence_set (def, TRUE, TRUE);
1443 }
1444
1445 /* Process an ABSENCE_SET.
1446
1447    This gives information about a cpu unit reservation requirements.
1448    We fill a struct unit_pattern_rel_decl (absence) with information
1449    used later by `expand_automata'.  */
1450 static void
1451 gen_absence_set (rtx def)
1452 {
1453   gen_presence_absence_set (def, FALSE, FALSE);
1454 }
1455
1456 /* Process a FINAL_ABSENCE_SET.
1457
1458    This gives information about a cpu unit reservation requirements.
1459    We fill a struct unit_pattern_rel_decl (absence) with information
1460    used later by `expand_automata'.  */
1461 static void
1462 gen_final_absence_set (rtx def)
1463 {
1464   gen_presence_absence_set (def, FALSE, TRUE);
1465 }
1466
1467 /* Process a DEFINE_AUTOMATON.
1468
1469    This gives information about a finite state automaton used for
1470    recognizing pipeline hazards.  We fill a struct automaton_decl
1471    with information used later by `expand_automata'.  */
1472 static void
1473 gen_automaton (rtx def)
1474 {
1475   decl_t decl;
1476   char **str_automata;
1477   int vect_length;
1478   int i;
1479
1480   str_automata = get_str_vect (XSTR (def, 0), &vect_length, ',', FALSE);
1481   if (str_automata == NULL)
1482     fatal ("invalid string `%s' in define_automaton", XSTR (def, 0));
1483   for (i = 0; i < vect_length; i++)
1484     {
1485       decl = create_node (sizeof (struct decl));
1486       decl->mode = dm_automaton;
1487       decl->pos = 0;
1488       DECL_AUTOMATON (decl)->name = check_name (str_automata [i], decl->pos);
1489       VEC_safe_push (decl_t,heap, decls, decl);
1490     }
1491 }
1492
1493 /* Process an AUTOMATA_OPTION.
1494
1495    This gives information how to generate finite state automaton used
1496    for recognizing pipeline hazards.  */
1497 static void
1498 gen_automata_option (rtx def)
1499 {
1500   if (strcmp (XSTR (def, 0), NO_MINIMIZATION_OPTION + 1) == 0)
1501     no_minimization_flag = 1;
1502   else if (strcmp (XSTR (def, 0), TIME_OPTION + 1) == 0)
1503     time_flag = 1;
1504   else if (strcmp (XSTR (def, 0), STATS_OPTION + 1) == 0)
1505     stats_flag = 1;
1506   else if (strcmp (XSTR (def, 0), V_OPTION + 1) == 0)
1507     v_flag = 1;
1508   else if (strcmp (XSTR (def, 0), W_OPTION + 1) == 0)
1509     w_flag = 1;
1510   else if (strcmp (XSTR (def, 0), NDFA_OPTION + 1) == 0)
1511     ndfa_flag = 1;
1512   else if (strcmp (XSTR (def, 0), PROGRESS_OPTION + 1) == 0)
1513     progress_flag = 1;
1514   else
1515     fatal ("invalid option `%s' in automata_option", XSTR (def, 0));
1516 }
1517
1518 /* Name in reservation to denote absence reservation.  */
1519 #define NOTHING_NAME "nothing"
1520
1521 /* The following string contains original reservation string being
1522    parsed.  */
1523 static const char *reserv_str;
1524
1525 /* Parse an element in STR.  */
1526 static regexp_t
1527 gen_regexp_el (const char *str)
1528 {
1529   regexp_t regexp;
1530   char *dstr;
1531   int len;
1532
1533   if (*str == '(')
1534     {
1535       len = strlen (str);
1536       if (str [len - 1] != ')')
1537         fatal ("garbage after ) in reservation `%s'", reserv_str);
1538       dstr = alloca (len - 1);
1539       memcpy (dstr, str + 1, len - 2);
1540       dstr [len-2] = '\0';
1541       regexp = gen_regexp_sequence (dstr);
1542     }
1543   else if (strcmp (str, NOTHING_NAME) == 0)
1544     {
1545       regexp = create_node (sizeof *regexp);
1546       regexp->mode = rm_nothing;
1547     }
1548   else
1549     {
1550       regexp = create_node (sizeof *regexp);
1551       regexp->mode = rm_unit;
1552       REGEXP_UNIT (regexp)->name = str;
1553     }
1554   return regexp;
1555 }
1556
1557 /* Parse construction `repeat' in STR.  */
1558 static regexp_t
1559 gen_regexp_repeat (const char *str)
1560 {
1561   regexp_t regexp;
1562   regexp_t repeat;
1563   char **repeat_vect;
1564   int els_num;
1565   int i;
1566
1567   repeat_vect = get_str_vect (str, &els_num, '*', TRUE);
1568   if (repeat_vect == NULL)
1569     fatal ("invalid `%s' in reservation `%s'", str, reserv_str);
1570   if (els_num > 1)
1571     {
1572       regexp = gen_regexp_el (repeat_vect [0]);
1573       for (i = 1; i < els_num; i++)
1574         {
1575           repeat = create_node (sizeof (struct regexp));
1576           repeat->mode = rm_repeat;
1577           REGEXP_REPEAT (repeat)->regexp = regexp;
1578           REGEXP_REPEAT (repeat)->repeat_num = atoi (repeat_vect [i]);
1579           if (REGEXP_REPEAT (repeat)->repeat_num <= 1)
1580             fatal ("repetition `%s' <= 1 in reservation `%s'",
1581                    str, reserv_str);
1582           regexp = repeat;
1583         }
1584       return regexp;
1585     }
1586   else
1587     return gen_regexp_el (str);
1588 }
1589
1590 /* Parse reservation STR which possibly contains separator '+'.  */
1591 static regexp_t
1592 gen_regexp_allof (const char *str)
1593 {
1594   regexp_t allof;
1595   char **allof_vect;
1596   int els_num;
1597   int i;
1598
1599   allof_vect = get_str_vect (str, &els_num, '+', TRUE);
1600   if (allof_vect == NULL)
1601     fatal ("invalid `%s' in reservation `%s'", str, reserv_str);
1602   if (els_num > 1)
1603     {
1604       allof = create_node (sizeof (struct regexp)
1605                            + sizeof (regexp_t) * (els_num - 1));
1606       allof->mode = rm_allof;
1607       REGEXP_ALLOF (allof)->regexps_num = els_num;
1608       for (i = 0; i < els_num; i++)
1609         REGEXP_ALLOF (allof)->regexps [i] = gen_regexp_repeat (allof_vect [i]);
1610       return allof;
1611     }
1612   else
1613     return gen_regexp_repeat (str);
1614 }
1615
1616 /* Parse reservation STR which possibly contains separator '|'.  */
1617 static regexp_t
1618 gen_regexp_oneof (const char *str)
1619 {
1620   regexp_t oneof;
1621   char **oneof_vect;
1622   int els_num;
1623   int i;
1624
1625   oneof_vect = get_str_vect (str, &els_num, '|', TRUE);
1626   if (oneof_vect == NULL)
1627     fatal ("invalid `%s' in reservation `%s'", str, reserv_str);
1628   if (els_num > 1)
1629     {
1630       oneof = create_node (sizeof (struct regexp)
1631                            + sizeof (regexp_t) * (els_num - 1));
1632       oneof->mode = rm_oneof;
1633       REGEXP_ONEOF (oneof)->regexps_num = els_num;
1634       for (i = 0; i < els_num; i++)
1635         REGEXP_ONEOF (oneof)->regexps [i] = gen_regexp_allof (oneof_vect [i]);
1636       return oneof;
1637     }
1638   else
1639     return gen_regexp_allof (str);
1640 }
1641
1642 /* Parse reservation STR which possibly contains separator ','.  */
1643 static regexp_t
1644 gen_regexp_sequence (const char *str)
1645 {
1646   regexp_t sequence;
1647   char **sequence_vect;
1648   int els_num;
1649   int i;
1650
1651   sequence_vect = get_str_vect (str, &els_num, ',', TRUE);
1652   if (els_num > 1)
1653     {
1654       sequence = create_node (sizeof (struct regexp)
1655                               + sizeof (regexp_t) * (els_num - 1));
1656       sequence->mode = rm_sequence;
1657       REGEXP_SEQUENCE (sequence)->regexps_num = els_num;
1658       for (i = 0; i < els_num; i++)
1659         REGEXP_SEQUENCE (sequence)->regexps [i]
1660           = gen_regexp_oneof (sequence_vect [i]);
1661       return sequence;
1662     }
1663   else
1664     return gen_regexp_oneof (str);
1665 }
1666
1667 /* Parse construction reservation STR.  */
1668 static regexp_t
1669 gen_regexp (const char *str)
1670 {
1671   reserv_str = str;
1672   return gen_regexp_sequence (str);;
1673 }
1674
1675 /* Process a DEFINE_RESERVATION.
1676
1677    This gives information about a reservation of cpu units.  We fill
1678    in a struct reserv_decl with information used later by
1679    `expand_automata'.  */
1680 static void
1681 gen_reserv (rtx def)
1682 {
1683   decl_t decl;
1684
1685   decl = create_node (sizeof (struct decl));
1686   decl->mode = dm_reserv;
1687   decl->pos = 0;
1688   DECL_RESERV (decl)->name = check_name (XSTR (def, 0), decl->pos);
1689   DECL_RESERV (decl)->regexp = gen_regexp (XSTR (def, 1));
1690   VEC_safe_push (decl_t,heap, decls, decl);
1691 }
1692
1693 /* Process a DEFINE_INSN_RESERVATION.
1694
1695    This gives information about the reservation of cpu units by an
1696    insn.  We fill a struct insn_reserv_decl with information used
1697    later by `expand_automata'.  */
1698 static void
1699 gen_insn_reserv (rtx def)
1700 {
1701   decl_t decl;
1702
1703   decl = create_node (sizeof (struct decl));
1704   decl->mode = dm_insn_reserv;
1705   decl->pos = 0;
1706   DECL_INSN_RESERV (decl)->name
1707     = check_name (XSTR (def, 0), decl->pos);
1708   DECL_INSN_RESERV (decl)->default_latency = XINT (def, 1);
1709   DECL_INSN_RESERV (decl)->condexp = XEXP (def, 2);
1710   DECL_INSN_RESERV (decl)->regexp = gen_regexp (XSTR (def, 3));
1711   VEC_safe_push (decl_t,heap, decls, decl);
1712 }
1713
1714 \f
1715
1716 /* The function evaluates hash value (0..UINT_MAX) of string.  */
1717 static unsigned
1718 string_hash (const char *string)
1719 {
1720   unsigned result, i;
1721
1722   for (result = i = 0;*string++ != '\0'; i++)
1723     result += ((unsigned char) *string << (i % CHAR_BIT));
1724   return result;
1725 }
1726
1727 \f
1728
1729 /* This page contains abstract data `table of automaton declarations'.
1730    Elements of the table is nodes representing automaton declarations.
1731    Key of the table elements is name of given automaton.  Remember
1732    that automaton names have own space.  */
1733
1734 /* The function evaluates hash value of an automaton declaration.  The
1735    function is used by abstract data `hashtab'.  The function returns
1736    hash value (0..UINT_MAX) of given automaton declaration.  */
1737 static hashval_t
1738 automaton_decl_hash (const void *automaton_decl)
1739 {
1740   const decl_t decl = (decl_t) automaton_decl;
1741
1742   gcc_assert (decl->mode != dm_automaton
1743               || DECL_AUTOMATON (decl)->name);
1744   return string_hash (DECL_AUTOMATON (decl)->name);
1745 }
1746
1747 /* The function tests automaton declarations on equality of their
1748    keys.  The function is used by abstract data `hashtab'.  The
1749    function returns 1 if the declarations have the same key, 0
1750    otherwise.  */
1751 static int
1752 automaton_decl_eq_p (const void* automaton_decl_1,
1753                      const void* automaton_decl_2)
1754 {
1755   const decl_t decl1 = (decl_t) automaton_decl_1;
1756   const decl_t decl2 = (decl_t) automaton_decl_2;
1757
1758   gcc_assert (decl1->mode == dm_automaton
1759               && DECL_AUTOMATON (decl1)->name
1760               && decl2->mode == dm_automaton
1761               && DECL_AUTOMATON (decl2)->name);
1762   return strcmp (DECL_AUTOMATON (decl1)->name,
1763                  DECL_AUTOMATON (decl2)->name) == 0;
1764 }
1765
1766 /* The automaton declaration table itself is represented by the
1767    following variable.  */
1768 static htab_t automaton_decl_table;
1769
1770 /* The function inserts automaton declaration into the table.  The
1771    function does nothing if an automaton declaration with the same key
1772    exists already in the table.  The function returns automaton
1773    declaration node in the table with the same key as given automaton
1774    declaration node.  */
1775 static decl_t
1776 insert_automaton_decl (decl_t automaton_decl)
1777 {
1778   void **entry_ptr;
1779
1780   entry_ptr = htab_find_slot (automaton_decl_table, automaton_decl, 1);
1781   if (*entry_ptr == NULL)
1782     *entry_ptr = (void *) automaton_decl;
1783   return (decl_t) *entry_ptr;
1784 }
1785
1786 /* The following variable value is node representing automaton
1787    declaration.  The node used for searching automaton declaration
1788    with given name.  */
1789 static struct decl work_automaton_decl;
1790
1791 /* The function searches for automaton declaration in the table with
1792    the same key as node representing name of the automaton
1793    declaration.  The function returns node found in the table, NULL if
1794    such node does not exist in the table.  */
1795 static decl_t
1796 find_automaton_decl (const char *name)
1797 {
1798   void *entry;
1799
1800   work_automaton_decl.mode = dm_automaton;
1801   DECL_AUTOMATON (&work_automaton_decl)->name = name;
1802   entry = htab_find (automaton_decl_table, &work_automaton_decl);
1803   return (decl_t) entry;
1804 }
1805
1806 /* The function creates empty automaton declaration table and node
1807    representing automaton declaration and used for searching automaton
1808    declaration with given name.  The function must be called only once
1809    before any work with the automaton declaration table.  */
1810 static void
1811 initiate_automaton_decl_table (void)
1812 {
1813   work_automaton_decl.mode = dm_automaton;
1814   automaton_decl_table = htab_create (10, automaton_decl_hash,
1815                                       automaton_decl_eq_p, (htab_del) 0);
1816 }
1817
1818 /* The function deletes the automaton declaration table.  Only call of
1819    function `initiate_automaton_decl_table' is possible immediately
1820    after this function call.  */
1821 static void
1822 finish_automaton_decl_table (void)
1823 {
1824   htab_delete (automaton_decl_table);
1825 }
1826
1827 \f
1828
1829 /* This page contains abstract data `table of insn declarations'.
1830    Elements of the table is nodes representing insn declarations.  Key
1831    of the table elements is name of given insn (in corresponding
1832    define_insn_reservation).  Remember that insn names have own
1833    space.  */
1834
1835 /* The function evaluates hash value of an insn declaration.  The
1836    function is used by abstract data `hashtab'.  The function returns
1837    hash value (0..UINT_MAX) of given insn declaration.  */
1838 static hashval_t
1839 insn_decl_hash (const void *insn_decl)
1840 {
1841   const decl_t decl = (decl_t) insn_decl;
1842
1843   gcc_assert (decl->mode == dm_insn_reserv
1844               && DECL_INSN_RESERV (decl)->name);
1845   return string_hash (DECL_INSN_RESERV (decl)->name);
1846 }
1847
1848 /* The function tests insn declarations on equality of their keys.
1849    The function is used by abstract data `hashtab'.  The function
1850    returns 1 if declarations have the same key, 0 otherwise.  */
1851 static int
1852 insn_decl_eq_p (const void *insn_decl_1, const void *insn_decl_2)
1853 {
1854   const decl_t decl1 = (decl_t) insn_decl_1;
1855   const decl_t decl2 = (decl_t) insn_decl_2;
1856
1857   gcc_assert (decl1->mode == dm_insn_reserv
1858               && DECL_INSN_RESERV (decl1)->name
1859               && decl2->mode == dm_insn_reserv
1860               && DECL_INSN_RESERV (decl2)->name);
1861   return strcmp (DECL_INSN_RESERV (decl1)->name,
1862                  DECL_INSN_RESERV (decl2)->name) == 0;
1863 }
1864
1865 /* The insn declaration table itself is represented by the following
1866    variable.  The table does not contain insn reservation
1867    declarations.  */
1868 static htab_t insn_decl_table;
1869
1870 /* The function inserts insn declaration into the table.  The function
1871    does nothing if an insn declaration with the same key exists
1872    already in the table.  The function returns insn declaration node
1873    in the table with the same key as given insn declaration node.  */
1874 static decl_t
1875 insert_insn_decl (decl_t insn_decl)
1876 {
1877   void **entry_ptr;
1878
1879   entry_ptr = htab_find_slot (insn_decl_table, insn_decl, 1);
1880   if (*entry_ptr == NULL)
1881     *entry_ptr = (void *) insn_decl;
1882   return (decl_t) *entry_ptr;
1883 }
1884
1885 /* The following variable value is node representing insn reservation
1886    declaration.  The node used for searching insn reservation
1887    declaration with given name.  */
1888 static struct decl work_insn_decl;
1889
1890 /* The function searches for insn reservation declaration in the table
1891    with the same key as node representing name of the insn reservation
1892    declaration.  The function returns node found in the table, NULL if
1893    such node does not exist in the table.  */
1894 static decl_t
1895 find_insn_decl (const char *name)
1896 {
1897   void *entry;
1898
1899   work_insn_decl.mode = dm_insn_reserv;
1900   DECL_INSN_RESERV (&work_insn_decl)->name = name;
1901   entry = htab_find (insn_decl_table, &work_insn_decl);
1902   return (decl_t) entry;
1903 }
1904
1905 /* The function creates empty insn declaration table and node
1906    representing insn declaration and used for searching insn
1907    declaration with given name.  The function must be called only once
1908    before any work with the insn declaration table.  */
1909 static void
1910 initiate_insn_decl_table (void)
1911 {
1912   work_insn_decl.mode = dm_insn_reserv;
1913   insn_decl_table = htab_create (10, insn_decl_hash, insn_decl_eq_p,
1914                                  (htab_del) 0);
1915 }
1916
1917 /* The function deletes the insn declaration table.  Only call of
1918    function `initiate_insn_decl_table' is possible immediately after
1919    this function call.  */
1920 static void
1921 finish_insn_decl_table (void)
1922 {
1923   htab_delete (insn_decl_table);
1924 }
1925
1926 \f
1927
1928 /* This page contains abstract data `table of declarations'.  Elements
1929    of the table is nodes representing declarations (of units and
1930    reservations).  Key of the table elements is names of given
1931    declarations.  */
1932
1933 /* The function evaluates hash value of a declaration.  The function
1934    is used by abstract data `hashtab'.  The function returns hash
1935    value (0..UINT_MAX) of given declaration.  */
1936 static hashval_t
1937 decl_hash (const void *decl)
1938 {
1939   const decl_t d = (const decl_t) decl;
1940
1941   gcc_assert ((d->mode == dm_unit && DECL_UNIT (d)->name)
1942               || (d->mode == dm_reserv && DECL_RESERV (d)->name));
1943   return string_hash (d->mode == dm_unit
1944                       ? DECL_UNIT (d)->name : DECL_RESERV (d)->name);
1945 }
1946
1947 /* The function tests declarations on equality of their keys.  The
1948    function is used by abstract data 'hashtab'.  The function
1949    returns 1 if the declarations have the same key, 0 otherwise.  */
1950 static int
1951 decl_eq_p (const void *decl_1, const void *decl_2)
1952 {
1953   const decl_t d1 = (const decl_t) decl_1;
1954   const decl_t d2 = (const decl_t) decl_2;
1955
1956   gcc_assert ((d1->mode == dm_unit && DECL_UNIT (d1)->name)
1957               || (d1->mode == dm_reserv && DECL_RESERV (d1)->name));
1958   gcc_assert ((d2->mode == dm_unit && DECL_UNIT (d2)->name)
1959               || (d2->mode == dm_reserv && DECL_RESERV (d2)->name));
1960   return strcmp ((d1->mode == dm_unit
1961                   ? DECL_UNIT (d1)->name : DECL_RESERV (d1)->name),
1962                  (d2->mode == dm_unit
1963                   ? DECL_UNIT (d2)->name : DECL_RESERV (d2)->name)) == 0;
1964 }
1965
1966 /* The declaration table itself is represented by the following
1967    variable.  */
1968 static htab_t decl_table;
1969
1970 /* The function inserts declaration into the table.  The function does
1971    nothing if a declaration with the same key exists already in the
1972    table.  The function returns declaration node in the table with the
1973    same key as given declaration node.  */
1974
1975 static decl_t
1976 insert_decl (decl_t decl)
1977 {
1978   void **entry_ptr;
1979
1980   entry_ptr = htab_find_slot (decl_table, decl, 1);
1981   if (*entry_ptr == NULL)
1982     *entry_ptr = (void *) decl;
1983   return (decl_t) *entry_ptr;
1984 }
1985
1986 /* The following variable value is node representing declaration.  The
1987    node used for searching declaration with given name.  */
1988 static struct decl work_decl;
1989
1990 /* The function searches for declaration in the table with the same
1991    key as node representing name of the declaration.  The function
1992    returns node found in the table, NULL if such node does not exist
1993    in the table.  */
1994 static decl_t
1995 find_decl (const char *name)
1996 {
1997   void *entry;
1998
1999   work_decl.mode = dm_unit;
2000   DECL_UNIT (&work_decl)->name = name;
2001   entry = htab_find (decl_table, &work_decl);
2002   return (decl_t) entry;
2003 }
2004
2005 /* The function creates empty declaration table and node representing
2006    declaration and used for searching declaration with given name.
2007    The function must be called only once before any work with the
2008    declaration table.  */
2009 static void
2010 initiate_decl_table (void)
2011 {
2012   work_decl.mode = dm_unit;
2013   decl_table = htab_create (10, decl_hash, decl_eq_p, (htab_del) 0);
2014 }
2015
2016 /* The function deletes the declaration table.  Only call of function
2017    `initiate_declaration_table' is possible immediately after this
2018    function call.  */
2019 static void
2020 finish_decl_table (void)
2021 {
2022   htab_delete (decl_table);
2023 }
2024
2025 \f
2026
2027 /* This page contains checker of pipeline hazard description.  */
2028
2029 /* Checking NAMES in an exclusion clause vector and returning formed
2030    unit_set_el_list.  */
2031 static unit_set_el_t
2032 process_excls (char **names, int num, pos_t excl_pos ATTRIBUTE_UNUSED)
2033 {
2034   unit_set_el_t el_list;
2035   unit_set_el_t last_el;
2036   unit_set_el_t new_el;
2037   decl_t decl_in_table;
2038   int i;
2039
2040   el_list = NULL;
2041   last_el = NULL;
2042   for (i = 0; i < num; i++)
2043     {
2044       decl_in_table = find_decl (names [i]);
2045       if (decl_in_table == NULL)
2046         error ("unit `%s' in exclusion is not declared", names [i]);
2047       else if (decl_in_table->mode != dm_unit)
2048         error ("`%s' in exclusion is not unit", names [i]);
2049       else
2050         {
2051           new_el = create_node (sizeof (struct unit_set_el));
2052           new_el->unit_decl = DECL_UNIT (decl_in_table);
2053           new_el->next_unit_set_el = NULL;
2054           if (last_el == NULL)
2055             el_list = last_el = new_el;
2056           else
2057             {
2058               last_el->next_unit_set_el = new_el;
2059               last_el = last_el->next_unit_set_el;
2060             }
2061         }
2062     }
2063   return el_list;
2064 }
2065
2066 /* The function adds each element from SOURCE_LIST to the exclusion
2067    list of the each element from DEST_LIST.  Checking situation "unit
2068    excludes itself".  */
2069 static void
2070 add_excls (unit_set_el_t dest_list, unit_set_el_t source_list,
2071            pos_t excl_pos ATTRIBUTE_UNUSED)
2072 {
2073   unit_set_el_t dst;
2074   unit_set_el_t src;
2075   unit_set_el_t curr_el;
2076   unit_set_el_t prev_el;
2077   unit_set_el_t copy;
2078
2079   for (dst = dest_list; dst != NULL; dst = dst->next_unit_set_el)
2080     for (src = source_list; src != NULL; src = src->next_unit_set_el)
2081       {
2082         if (dst->unit_decl == src->unit_decl)
2083           {
2084             error ("unit `%s' excludes itself", src->unit_decl->name);
2085             continue;
2086           }
2087         if (dst->unit_decl->automaton_name != NULL
2088             && src->unit_decl->automaton_name != NULL
2089             && strcmp (dst->unit_decl->automaton_name,
2090                        src->unit_decl->automaton_name) != 0)
2091           {
2092             error ("units `%s' and `%s' in exclusion set belong to different automata",
2093                    src->unit_decl->name, dst->unit_decl->name);
2094             continue;
2095           }
2096         for (curr_el = dst->unit_decl->excl_list, prev_el = NULL;
2097              curr_el != NULL;
2098              prev_el = curr_el, curr_el = curr_el->next_unit_set_el)
2099           if (curr_el->unit_decl == src->unit_decl)
2100             break;
2101         if (curr_el == NULL)
2102           {
2103             /* Element not found - insert.  */
2104             copy = copy_node (src, sizeof (*src));
2105             copy->next_unit_set_el = NULL;
2106             if (prev_el == NULL)
2107               dst->unit_decl->excl_list = copy;
2108             else
2109               prev_el->next_unit_set_el = copy;
2110         }
2111     }
2112 }
2113
2114 /* Checking NAMES in presence/absence clause and returning the
2115    formed unit_set_el_list.  The function is called only after
2116    processing all exclusion sets.  */
2117 static unit_set_el_t
2118 process_presence_absence_names (char **names, int num,
2119                                 pos_t req_pos ATTRIBUTE_UNUSED,
2120                                 int presence_p, int final_p)
2121 {
2122   unit_set_el_t el_list;
2123   unit_set_el_t last_el;
2124   unit_set_el_t new_el;
2125   decl_t decl_in_table;
2126   int i;
2127
2128   el_list = NULL;
2129   last_el = NULL;
2130   for (i = 0; i < num; i++)
2131     {
2132       decl_in_table = find_decl (names [i]);
2133       if (decl_in_table == NULL)
2134         error ((presence_p
2135                 ? (final_p
2136                    ? "unit `%s' in final presence set is not declared"
2137                    : "unit `%s' in presence set is not declared")
2138                 : (final_p
2139                    ? "unit `%s' in final absence set is not declared"
2140                    : "unit `%s' in absence set is not declared")), names [i]);
2141       else if (decl_in_table->mode != dm_unit)
2142         error ((presence_p
2143                 ? (final_p
2144                    ? "`%s' in final presence set is not unit"
2145                    : "`%s' in presence set is not unit")
2146                 : (final_p
2147                    ? "`%s' in final absence set is not unit"
2148                    : "`%s' in absence set is not unit")), names [i]);
2149       else
2150         {
2151           new_el = create_node (sizeof (struct unit_set_el));
2152           new_el->unit_decl = DECL_UNIT (decl_in_table);
2153           new_el->next_unit_set_el = NULL;
2154           if (last_el == NULL)
2155             el_list = last_el = new_el;
2156           else
2157             {
2158               last_el->next_unit_set_el = new_el;
2159               last_el = last_el->next_unit_set_el;
2160             }
2161         }
2162     }
2163   return el_list;
2164 }
2165
2166 /* Checking NAMES in patterns of a presence/absence clause and
2167    returning the formed pattern_set_el_list.  The function is called
2168    only after processing all exclusion sets.  */
2169 static pattern_set_el_t
2170 process_presence_absence_patterns (char ***patterns, int num,
2171                                    pos_t req_pos ATTRIBUTE_UNUSED,
2172                                    int presence_p, int final_p)
2173 {
2174   pattern_set_el_t el_list;
2175   pattern_set_el_t last_el;
2176   pattern_set_el_t new_el;
2177   decl_t decl_in_table;
2178   int i, j;
2179
2180   el_list = NULL;
2181   last_el = NULL;
2182   for (i = 0; i < num; i++)
2183     {
2184       for (j = 0; patterns [i] [j] != NULL; j++)
2185         ;
2186       new_el = create_node (sizeof (struct pattern_set_el)
2187                             + sizeof (struct unit_decl *) * j);
2188       new_el->unit_decls
2189         = (struct unit_decl **) ((char *) new_el
2190                                  + sizeof (struct pattern_set_el));
2191       new_el->next_pattern_set_el = NULL;
2192       if (last_el == NULL)
2193         el_list = last_el = new_el;
2194       else
2195         {
2196           last_el->next_pattern_set_el = new_el;
2197           last_el = last_el->next_pattern_set_el;
2198         }
2199       new_el->units_num = 0;
2200       for (j = 0; patterns [i] [j] != NULL; j++)
2201         {
2202           decl_in_table = find_decl (patterns [i] [j]);
2203           if (decl_in_table == NULL)
2204             error ((presence_p
2205                     ? (final_p
2206                        ? "unit `%s' in final presence set is not declared"
2207                        : "unit `%s' in presence set is not declared")
2208                     : (final_p
2209                        ? "unit `%s' in final absence set is not declared"
2210                        : "unit `%s' in absence set is not declared")),
2211                    patterns [i] [j]);
2212           else if (decl_in_table->mode != dm_unit)
2213             error ((presence_p
2214                     ? (final_p
2215                        ? "`%s' in final presence set is not unit"
2216                        : "`%s' in presence set is not unit")
2217                     : (final_p
2218                        ? "`%s' in final absence set is not unit"
2219                        : "`%s' in absence set is not unit")),
2220                    patterns [i] [j]);
2221           else
2222             {
2223               new_el->unit_decls [new_el->units_num]
2224                 = DECL_UNIT (decl_in_table);
2225               new_el->units_num++;
2226             }
2227         }
2228     }
2229   return el_list;
2230 }
2231
2232 /* The function adds each element from PATTERN_LIST to presence (if
2233    PRESENCE_P) or absence list of the each element from DEST_LIST.
2234    Checking situations "unit requires own absence", and "unit excludes
2235    and requires presence of ...", "unit requires absence and presence
2236    of ...", "units in (final) presence set belong to different
2237    automata", and "units in (final) absence set belong to different
2238    automata".  Remember that we process absence sets only after all
2239    presence sets.  */
2240 static void
2241 add_presence_absence (unit_set_el_t dest_list,
2242                       pattern_set_el_t pattern_list,
2243                       pos_t req_pos ATTRIBUTE_UNUSED,
2244                       int presence_p, int final_p)
2245 {
2246   unit_set_el_t dst;
2247   pattern_set_el_t pat;
2248   struct unit_decl *unit;
2249   unit_set_el_t curr_excl_el;
2250   pattern_set_el_t curr_pat_el;
2251   pattern_set_el_t prev_el;
2252   pattern_set_el_t copy;
2253   int i;
2254   int no_error_flag;
2255
2256   for (dst = dest_list; dst != NULL; dst = dst->next_unit_set_el)
2257     for (pat = pattern_list; pat != NULL; pat = pat->next_pattern_set_el)
2258       {
2259         for (i = 0; i < pat->units_num; i++)
2260           {
2261             unit = pat->unit_decls [i];
2262             if (dst->unit_decl == unit && pat->units_num == 1 && !presence_p)
2263               {
2264                 error ("unit `%s' requires own absence", unit->name);
2265                 continue;
2266               }
2267             if (dst->unit_decl->automaton_name != NULL
2268                 && unit->automaton_name != NULL
2269                 && strcmp (dst->unit_decl->automaton_name,
2270                            unit->automaton_name) != 0)
2271               {
2272                 error ((presence_p
2273                         ? (final_p
2274                            ? "units `%s' and `%s' in final presence set belong to different automata"
2275                            : "units `%s' and `%s' in presence set belong to different automata")
2276                         : (final_p
2277                            ? "units `%s' and `%s' in final absence set belong to different automata"
2278                            : "units `%s' and `%s' in absence set belong to different automata")),
2279                        unit->name, dst->unit_decl->name);
2280                 continue;
2281               }
2282             no_error_flag = 1;
2283             if (presence_p)
2284               for (curr_excl_el = dst->unit_decl->excl_list;
2285                    curr_excl_el != NULL;
2286                    curr_excl_el = curr_excl_el->next_unit_set_el)
2287                 {
2288                   if (unit == curr_excl_el->unit_decl && pat->units_num == 1)
2289                     {
2290                       if (!w_flag)
2291                         {
2292                           error ("unit `%s' excludes and requires presence of `%s'",
2293                                  dst->unit_decl->name, unit->name);
2294                           no_error_flag = 0;
2295                         }
2296                       else
2297                         warning
2298                           (0, "unit `%s' excludes and requires presence of `%s'",
2299                            dst->unit_decl->name, unit->name);
2300                     }
2301                 }
2302             else if (pat->units_num == 1)
2303               for (curr_pat_el = dst->unit_decl->presence_list;
2304                    curr_pat_el != NULL;
2305                    curr_pat_el = curr_pat_el->next_pattern_set_el)
2306                 if (curr_pat_el->units_num == 1
2307                     && unit == curr_pat_el->unit_decls [0])
2308                   {
2309                     if (!w_flag)
2310                       {
2311                         error
2312                           ("unit `%s' requires absence and presence of `%s'",
2313                            dst->unit_decl->name, unit->name);
2314                         no_error_flag = 0;
2315                       }
2316                     else
2317                       warning
2318                         (0, "unit `%s' requires absence and presence of `%s'",
2319                          dst->unit_decl->name, unit->name);
2320                   }
2321             if (no_error_flag)
2322               {
2323                 for (prev_el = (presence_p
2324                                 ? (final_p
2325                                    ? dst->unit_decl->final_presence_list
2326                                    : dst->unit_decl->final_presence_list)
2327                                 : (final_p
2328                                    ? dst->unit_decl->final_absence_list
2329                                    : dst->unit_decl->absence_list));
2330                      prev_el != NULL && prev_el->next_pattern_set_el != NULL;
2331                      prev_el = prev_el->next_pattern_set_el)
2332                   ;
2333                 copy = copy_node (pat, sizeof (*pat));
2334                 copy->next_pattern_set_el = NULL;
2335                 if (prev_el == NULL)
2336                   {
2337                     if (presence_p)
2338                       {
2339                         if (final_p)
2340                           dst->unit_decl->final_presence_list = copy;
2341                         else
2342                           dst->unit_decl->presence_list = copy;
2343                       }
2344                     else if (final_p)
2345                       dst->unit_decl->final_absence_list = copy;
2346                     else
2347                       dst->unit_decl->absence_list = copy;
2348                   }
2349                 else
2350                   prev_el->next_pattern_set_el = copy;
2351               }
2352           }
2353       }
2354 }
2355
2356
2357 /* The function searches for bypass with given IN_INSN_RESERV in given
2358    BYPASS_LIST.  */
2359 static struct bypass_decl *
2360 find_bypass (struct bypass_decl *bypass_list,
2361              struct insn_reserv_decl *in_insn_reserv)
2362 {
2363   struct bypass_decl *bypass;
2364
2365   for (bypass = bypass_list; bypass != NULL; bypass = bypass->next)
2366     if (bypass->in_insn_reserv == in_insn_reserv)
2367       break;
2368   return bypass;
2369 }
2370
2371 /* The function processes pipeline description declarations, checks
2372    their correctness, and forms exclusion/presence/absence sets.  */
2373 static void
2374 process_decls (void)
2375 {
2376   decl_t decl;
2377   decl_t automaton_decl;
2378   decl_t decl_in_table;
2379   decl_t out_insn_reserv;
2380   decl_t in_insn_reserv;
2381   struct bypass_decl *bypass;
2382   int automaton_presence;
2383   int i;
2384
2385   /* Checking repeated automata declarations.  */
2386   automaton_presence = 0;
2387   for (i = 0; i < description->decls_num; i++)
2388     {
2389       decl = description->decls [i];
2390       if (decl->mode == dm_automaton)
2391         {
2392           automaton_presence = 1;
2393           decl_in_table = insert_automaton_decl (decl);
2394           if (decl_in_table != decl)
2395             {
2396               if (!w_flag)
2397                 error ("repeated declaration of automaton `%s'",
2398                        DECL_AUTOMATON (decl)->name);
2399               else
2400                 warning (0, "repeated declaration of automaton `%s'",
2401                          DECL_AUTOMATON (decl)->name);
2402             }
2403         }
2404     }
2405   /* Checking undeclared automata, repeated declarations (except for
2406      automata) and correctness of their attributes (insn latency times
2407      etc.).  */
2408   for (i = 0; i < description->decls_num; i++)
2409     {
2410       decl = description->decls [i];
2411       if (decl->mode == dm_insn_reserv)
2412         {
2413           if (DECL_INSN_RESERV (decl)->default_latency < 0)
2414             error ("define_insn_reservation `%s' has negative latency time",
2415                    DECL_INSN_RESERV (decl)->name);
2416           DECL_INSN_RESERV (decl)->insn_num = description->insns_num;
2417           description->insns_num++;
2418           decl_in_table = insert_insn_decl (decl);
2419           if (decl_in_table != decl)
2420             error ("`%s' is already used as insn reservation name",
2421                    DECL_INSN_RESERV (decl)->name);
2422         }
2423       else if (decl->mode == dm_bypass)
2424         {
2425           if (DECL_BYPASS (decl)->latency < 0)
2426             error ("define_bypass `%s - %s' has negative latency time",
2427                    DECL_BYPASS (decl)->out_insn_name,
2428                    DECL_BYPASS (decl)->in_insn_name);
2429         }
2430       else if (decl->mode == dm_unit || decl->mode == dm_reserv)
2431         {
2432           if (decl->mode == dm_unit)
2433             {
2434               DECL_UNIT (decl)->automaton_decl = NULL;
2435               if (DECL_UNIT (decl)->automaton_name != NULL)
2436                 {
2437                   automaton_decl
2438                     = find_automaton_decl (DECL_UNIT (decl)->automaton_name);
2439                   if (automaton_decl == NULL)
2440                     error ("automaton `%s' is not declared",
2441                            DECL_UNIT (decl)->automaton_name);
2442                   else
2443                     {
2444                       DECL_AUTOMATON (automaton_decl)->automaton_is_used = 1;
2445                       DECL_UNIT (decl)->automaton_decl
2446                         = DECL_AUTOMATON (automaton_decl);
2447                     }
2448                 }
2449               else if (automaton_presence)
2450                 error ("define_unit `%s' without automaton when one defined",
2451                        DECL_UNIT (decl)->name);
2452               DECL_UNIT (decl)->unit_num = description->units_num;
2453               description->units_num++;
2454               if (strcmp (DECL_UNIT (decl)->name, NOTHING_NAME) == 0)
2455                 {
2456                   error ("`%s' is declared as cpu unit", NOTHING_NAME);
2457                   continue;
2458                 }
2459               decl_in_table = find_decl (DECL_UNIT (decl)->name);
2460             }
2461           else
2462             {
2463               if (strcmp (DECL_RESERV (decl)->name, NOTHING_NAME) == 0)
2464                 {
2465                   error ("`%s' is declared as cpu reservation", NOTHING_NAME);
2466                   continue;
2467                 }
2468               decl_in_table = find_decl (DECL_RESERV (decl)->name);
2469             }
2470           if (decl_in_table == NULL)
2471             decl_in_table = insert_decl (decl);
2472           else
2473             {
2474               if (decl->mode == dm_unit)
2475                 error ("repeated declaration of unit `%s'",
2476                        DECL_UNIT (decl)->name);
2477               else
2478                 error ("repeated declaration of reservation `%s'",
2479                        DECL_RESERV (decl)->name);
2480             }
2481         }
2482     }
2483   /* Check bypasses and form list of bypasses for each (output)
2484      insn.  */
2485   for (i = 0; i < description->decls_num; i++)
2486     {
2487       decl = description->decls [i];
2488       if (decl->mode == dm_bypass)
2489         {
2490           out_insn_reserv = find_insn_decl (DECL_BYPASS (decl)->out_insn_name);
2491           in_insn_reserv = find_insn_decl (DECL_BYPASS (decl)->in_insn_name);
2492           if (out_insn_reserv == NULL)
2493             error ("there is no insn reservation `%s'",
2494                    DECL_BYPASS (decl)->out_insn_name);
2495           else if (in_insn_reserv == NULL)
2496             error ("there is no insn reservation `%s'",
2497                    DECL_BYPASS (decl)->in_insn_name);
2498           else
2499             {
2500               DECL_BYPASS (decl)->out_insn_reserv
2501                 = DECL_INSN_RESERV (out_insn_reserv);
2502               DECL_BYPASS (decl)->in_insn_reserv
2503                 = DECL_INSN_RESERV (in_insn_reserv);
2504               bypass
2505                 = find_bypass (DECL_INSN_RESERV (out_insn_reserv)->bypass_list,
2506                                DECL_BYPASS (decl)->in_insn_reserv);
2507               if (bypass != NULL)
2508                 {
2509                   if (DECL_BYPASS (decl)->latency == bypass->latency)
2510                     {
2511                       if (!w_flag)
2512                         error
2513                           ("the same bypass `%s - %s' is already defined",
2514                            DECL_BYPASS (decl)->out_insn_name,
2515                            DECL_BYPASS (decl)->in_insn_name);
2516                       else
2517                         warning
2518                           (0, "the same bypass `%s - %s' is already defined",
2519                            DECL_BYPASS (decl)->out_insn_name,
2520                            DECL_BYPASS (decl)->in_insn_name);
2521                     }
2522                   else
2523                     error ("bypass `%s - %s' is already defined",
2524                            DECL_BYPASS (decl)->out_insn_name,
2525                            DECL_BYPASS (decl)->in_insn_name);
2526                 }
2527               else
2528                 {
2529                   DECL_BYPASS (decl)->next
2530                     = DECL_INSN_RESERV (out_insn_reserv)->bypass_list;
2531                   DECL_INSN_RESERV (out_insn_reserv)->bypass_list
2532                     = DECL_BYPASS (decl);
2533                 }
2534             }
2535         }
2536     }
2537
2538   /* Check exclusion set declarations and form exclusion sets.  */
2539   for (i = 0; i < description->decls_num; i++)
2540     {
2541       decl = description->decls [i];
2542       if (decl->mode == dm_excl)
2543         {
2544           unit_set_el_t unit_set_el_list;
2545           unit_set_el_t unit_set_el_list_2;
2546
2547           unit_set_el_list
2548             = process_excls (DECL_EXCL (decl)->names,
2549                              DECL_EXCL (decl)->first_list_length, decl->pos);
2550           unit_set_el_list_2
2551             = process_excls (&DECL_EXCL (decl)->names
2552                              [DECL_EXCL (decl)->first_list_length],
2553                              DECL_EXCL (decl)->all_names_num
2554                              - DECL_EXCL (decl)->first_list_length,
2555                              decl->pos);
2556           add_excls (unit_set_el_list, unit_set_el_list_2, decl->pos);
2557           add_excls (unit_set_el_list_2, unit_set_el_list, decl->pos);
2558         }
2559     }
2560
2561   /* Check presence set declarations and form presence sets.  */
2562   for (i = 0; i < description->decls_num; i++)
2563     {
2564       decl = description->decls [i];
2565       if (decl->mode == dm_presence)
2566         {
2567           unit_set_el_t unit_set_el_list;
2568           pattern_set_el_t pattern_set_el_list;
2569
2570           unit_set_el_list
2571             = process_presence_absence_names
2572               (DECL_PRESENCE (decl)->names, DECL_PRESENCE (decl)->names_num,
2573                decl->pos, TRUE, DECL_PRESENCE (decl)->final_p);
2574           pattern_set_el_list
2575             = process_presence_absence_patterns
2576               (DECL_PRESENCE (decl)->patterns,
2577                DECL_PRESENCE (decl)->patterns_num,
2578                decl->pos, TRUE, DECL_PRESENCE (decl)->final_p);
2579           add_presence_absence (unit_set_el_list, pattern_set_el_list,
2580                                 decl->pos, TRUE,
2581                                 DECL_PRESENCE (decl)->final_p);
2582         }
2583     }
2584
2585   /* Check absence set declarations and form absence sets.  */
2586   for (i = 0; i < description->decls_num; i++)
2587     {
2588       decl = description->decls [i];
2589       if (decl->mode == dm_absence)
2590         {
2591           unit_set_el_t unit_set_el_list;
2592           pattern_set_el_t pattern_set_el_list;
2593
2594           unit_set_el_list
2595             = process_presence_absence_names
2596               (DECL_ABSENCE (decl)->names, DECL_ABSENCE (decl)->names_num,
2597                decl->pos, FALSE, DECL_ABSENCE (decl)->final_p);
2598           pattern_set_el_list
2599             = process_presence_absence_patterns
2600               (DECL_ABSENCE (decl)->patterns,
2601                DECL_ABSENCE (decl)->patterns_num,
2602                decl->pos, FALSE, DECL_ABSENCE (decl)->final_p);
2603           add_presence_absence (unit_set_el_list, pattern_set_el_list,
2604                                 decl->pos, FALSE,
2605                                 DECL_ABSENCE (decl)->final_p);
2606         }
2607     }
2608 }
2609
2610 /* The following function checks that declared automaton is used.  If
2611    the automaton is not used, the function fixes error/warning.  The
2612    following function must be called only after `process_decls'.  */
2613 static void
2614 check_automaton_usage (void)
2615 {
2616   decl_t decl;
2617   int i;
2618
2619   for (i = 0; i < description->decls_num; i++)
2620     {
2621       decl = description->decls [i];
2622       if (decl->mode == dm_automaton
2623           && !DECL_AUTOMATON (decl)->automaton_is_used)
2624         {
2625           if (!w_flag)
2626             error ("automaton `%s' is not used", DECL_AUTOMATON (decl)->name);
2627           else
2628             warning (0, "automaton `%s' is not used",
2629                      DECL_AUTOMATON (decl)->name);
2630         }
2631     }
2632 }
2633
2634 /* The following recursive function processes all regexp in order to
2635    fix usage of units or reservations and to fix errors of undeclared
2636    name.  The function may change unit_regexp onto reserv_regexp.
2637    Remember that reserv_regexp does not exist before the function
2638    call.  */
2639 static regexp_t
2640 process_regexp (regexp_t regexp)
2641 {
2642   decl_t decl_in_table;
2643   regexp_t new_regexp;
2644   int i;
2645
2646   switch (regexp->mode)
2647     {
2648     case rm_unit:
2649       decl_in_table = find_decl (REGEXP_UNIT (regexp)->name);
2650       if (decl_in_table == NULL)
2651         error ("undeclared unit or reservation `%s'",
2652                REGEXP_UNIT (regexp)->name);
2653       else
2654         switch (decl_in_table->mode)
2655           {
2656           case dm_unit:
2657             DECL_UNIT (decl_in_table)->unit_is_used = 1;
2658             REGEXP_UNIT (regexp)->unit_decl = DECL_UNIT (decl_in_table);
2659             break;
2660
2661           case dm_reserv:
2662             DECL_RESERV (decl_in_table)->reserv_is_used = 1;
2663             new_regexp = create_node (sizeof (struct regexp));
2664             new_regexp->mode = rm_reserv;
2665             new_regexp->pos = regexp->pos;
2666             REGEXP_RESERV (new_regexp)->name = REGEXP_UNIT (regexp)->name;
2667             REGEXP_RESERV (new_regexp)->reserv_decl
2668               = DECL_RESERV (decl_in_table);
2669             regexp = new_regexp;
2670             break;
2671
2672           default:
2673             gcc_unreachable ();
2674         }
2675       break;
2676     case rm_sequence:
2677       for (i = 0; i <REGEXP_SEQUENCE (regexp)->regexps_num; i++)
2678         REGEXP_SEQUENCE (regexp)->regexps [i]
2679           = process_regexp (REGEXP_SEQUENCE (regexp)->regexps [i]);
2680       break;
2681     case rm_allof:
2682       for (i = 0; i < REGEXP_ALLOF (regexp)->regexps_num; i++)
2683         REGEXP_ALLOF (regexp)->regexps [i]
2684           = process_regexp (REGEXP_ALLOF (regexp)->regexps [i]);
2685       break;
2686     case rm_oneof:
2687       for (i = 0; i < REGEXP_ONEOF (regexp)->regexps_num; i++)
2688         REGEXP_ONEOF (regexp)->regexps [i]
2689           = process_regexp (REGEXP_ONEOF (regexp)->regexps [i]);
2690       break;
2691     case rm_repeat:
2692       REGEXP_REPEAT (regexp)->regexp
2693         = process_regexp (REGEXP_REPEAT (regexp)->regexp);
2694       break;
2695     case rm_nothing:
2696       break;
2697     default:
2698       gcc_unreachable ();
2699     }
2700   return regexp;
2701 }
2702
2703 /* The following function processes regexp of define_reservation and
2704    define_insn_reservation with the aid of function
2705    `process_regexp'.  */
2706 static void
2707 process_regexp_decls (void)
2708 {
2709   decl_t decl;
2710   int i;
2711
2712   for (i = 0; i < description->decls_num; i++)
2713     {
2714       decl = description->decls [i];
2715       if (decl->mode == dm_reserv)
2716         DECL_RESERV (decl)->regexp
2717           = process_regexp (DECL_RESERV (decl)->regexp);
2718       else if (decl->mode == dm_insn_reserv)
2719         DECL_INSN_RESERV (decl)->regexp
2720           = process_regexp (DECL_INSN_RESERV (decl)->regexp);
2721     }
2722 }
2723
2724 /* The following function checks that declared unit is used.  If the
2725    unit is not used, the function fixes errors/warnings.  The
2726    following function must be called only after `process_decls',
2727    `process_regexp_decls'.  */
2728 static void
2729 check_usage (void)
2730 {
2731   decl_t decl;
2732   int i;
2733
2734   for (i = 0; i < description->decls_num; i++)
2735     {
2736       decl = description->decls [i];
2737       if (decl->mode == dm_unit && !DECL_UNIT (decl)->unit_is_used)
2738         {
2739           if (!w_flag)
2740             error ("unit `%s' is not used", DECL_UNIT (decl)->name);
2741           else
2742             warning (0, "unit `%s' is not used", DECL_UNIT (decl)->name);
2743         }
2744       else if (decl->mode == dm_reserv && !DECL_RESERV (decl)->reserv_is_used)
2745         {
2746           if (!w_flag)
2747             error ("reservation `%s' is not used", DECL_RESERV (decl)->name);
2748           else
2749             warning (0, "reservation `%s' is not used", DECL_RESERV (decl)->name);
2750         }
2751     }
2752 }
2753
2754 /* The following variable value is number of reservation being
2755    processed on loop recognition.  */
2756 static int curr_loop_pass_num;
2757
2758 /* The following recursive function returns nonzero value if REGEXP
2759    contains given decl or reservations in given regexp refers for
2760    given decl.  */
2761 static int
2762 loop_in_regexp (regexp_t regexp, decl_t start_decl)
2763 {
2764   int i;
2765
2766   if (regexp == NULL)
2767     return 0;
2768   switch (regexp->mode)
2769     {
2770       case rm_unit:
2771         return 0;
2772
2773     case rm_reserv:
2774       if (start_decl->mode == dm_reserv
2775           && REGEXP_RESERV (regexp)->reserv_decl == DECL_RESERV (start_decl))
2776         return 1;
2777       else if (REGEXP_RESERV (regexp)->reserv_decl->loop_pass_num
2778                == curr_loop_pass_num)
2779         /* declaration has been processed.  */
2780         return 0;
2781       else
2782         {
2783           REGEXP_RESERV (regexp)->reserv_decl->loop_pass_num
2784             = curr_loop_pass_num;
2785           return loop_in_regexp (REGEXP_RESERV (regexp)->reserv_decl->regexp,
2786                                  start_decl);
2787         }
2788
2789     case rm_sequence:
2790       for (i = 0; i <REGEXP_SEQUENCE (regexp)->regexps_num; i++)
2791         if (loop_in_regexp (REGEXP_SEQUENCE (regexp)->regexps [i], start_decl))
2792           return 1;
2793       return 0;
2794
2795     case rm_allof:
2796       for (i = 0; i < REGEXP_ALLOF (regexp)->regexps_num; i++)
2797         if (loop_in_regexp (REGEXP_ALLOF (regexp)->regexps [i], start_decl))
2798           return 1;
2799       return 0;
2800
2801     case rm_oneof:
2802       for (i = 0; i < REGEXP_ONEOF (regexp)->regexps_num; i++)
2803         if (loop_in_regexp (REGEXP_ONEOF (regexp)->regexps [i], start_decl))
2804           return 1;
2805       return 0;
2806
2807     case rm_repeat:
2808       return loop_in_regexp (REGEXP_REPEAT (regexp)->regexp, start_decl);
2809
2810     case rm_nothing:
2811       return 0;
2812
2813     default:
2814       gcc_unreachable ();
2815     }
2816 }
2817
2818 /* The following function fixes errors "cycle in definition ...".  The
2819    function uses function `loop_in_regexp' for that.  */
2820 static void
2821 check_loops_in_regexps (void)
2822 {
2823   decl_t decl;
2824   int i;
2825
2826   for (i = 0; i < description->decls_num; i++)
2827     {
2828       decl = description->decls [i];
2829       if (decl->mode == dm_reserv)
2830         DECL_RESERV (decl)->loop_pass_num = 0;
2831     }
2832   for (i = 0; i < description->decls_num; i++)
2833     {
2834       decl = description->decls [i];
2835       curr_loop_pass_num = i;
2836
2837       if (decl->mode == dm_reserv)
2838           {
2839             DECL_RESERV (decl)->loop_pass_num = curr_loop_pass_num;
2840             if (loop_in_regexp (DECL_RESERV (decl)->regexp, decl))
2841               {
2842                 gcc_assert (DECL_RESERV (decl)->regexp);
2843                 error ("cycle in definition of reservation `%s'",
2844                        DECL_RESERV (decl)->name);
2845               }
2846           }
2847     }
2848 }
2849
2850 /* The function recursively processes IR of reservation and defines
2851    max and min cycle for reservation of unit.  */
2852 static void
2853 process_regexp_cycles (regexp_t regexp, int max_start_cycle,
2854                        int min_start_cycle, int *max_finish_cycle,
2855                        int *min_finish_cycle)
2856 {
2857   int i;
2858
2859   switch (regexp->mode)
2860     {
2861     case rm_unit:
2862       if (REGEXP_UNIT (regexp)->unit_decl->max_occ_cycle_num < max_start_cycle)
2863         REGEXP_UNIT (regexp)->unit_decl->max_occ_cycle_num = max_start_cycle;
2864       if (REGEXP_UNIT (regexp)->unit_decl->min_occ_cycle_num > min_start_cycle
2865           || REGEXP_UNIT (regexp)->unit_decl->min_occ_cycle_num == -1)
2866         REGEXP_UNIT (regexp)->unit_decl->min_occ_cycle_num = min_start_cycle;
2867       *max_finish_cycle = max_start_cycle;
2868       *min_finish_cycle = min_start_cycle;
2869       break;
2870
2871     case rm_reserv:
2872       process_regexp_cycles (REGEXP_RESERV (regexp)->reserv_decl->regexp,
2873                              max_start_cycle, min_start_cycle,
2874                              max_finish_cycle, min_finish_cycle);
2875       break;
2876
2877     case rm_repeat:
2878       for (i = 0; i < REGEXP_REPEAT (regexp)->repeat_num; i++)
2879         {
2880           process_regexp_cycles (REGEXP_REPEAT (regexp)->regexp,
2881                                  max_start_cycle, min_start_cycle,
2882                                  max_finish_cycle, min_finish_cycle);
2883           max_start_cycle = *max_finish_cycle + 1;
2884           min_start_cycle = *min_finish_cycle + 1;
2885         }
2886       break;
2887
2888     case rm_sequence:
2889       for (i = 0; i <REGEXP_SEQUENCE (regexp)->regexps_num; i++)
2890         {
2891           process_regexp_cycles (REGEXP_SEQUENCE (regexp)->regexps [i],
2892                                  max_start_cycle, min_start_cycle,
2893                                  max_finish_cycle, min_finish_cycle);
2894           max_start_cycle = *max_finish_cycle + 1;
2895           min_start_cycle = *min_finish_cycle + 1;
2896         }
2897       break;
2898
2899     case rm_allof:
2900       {
2901         int max_cycle = 0;
2902         int min_cycle = 0;
2903         
2904         for (i = 0; i < REGEXP_ALLOF (regexp)->regexps_num; i++)
2905           {
2906             process_regexp_cycles (REGEXP_ALLOF (regexp)->regexps [i],
2907                                    max_start_cycle, min_start_cycle,
2908                                    max_finish_cycle, min_finish_cycle);
2909             if (max_cycle < *max_finish_cycle)
2910               max_cycle = *max_finish_cycle;
2911             if (i == 0 || min_cycle > *min_finish_cycle)
2912               min_cycle = *min_finish_cycle;
2913           }
2914         *max_finish_cycle = max_cycle;
2915         *min_finish_cycle = min_cycle;
2916       }
2917       break;
2918
2919     case rm_oneof:
2920       {
2921         int max_cycle = 0;
2922         int min_cycle = 0;
2923         
2924         for (i = 0; i < REGEXP_ONEOF (regexp)->regexps_num; i++)
2925           {
2926             process_regexp_cycles (REGEXP_ONEOF (regexp)->regexps [i],
2927                                    max_start_cycle, min_start_cycle,
2928                                    max_finish_cycle, min_finish_cycle);
2929             if (max_cycle < *max_finish_cycle)
2930               max_cycle = *max_finish_cycle;
2931             if (i == 0 || min_cycle > *min_finish_cycle)
2932               min_cycle = *min_finish_cycle;
2933           }
2934         *max_finish_cycle = max_cycle;
2935         *min_finish_cycle = min_cycle;
2936       }
2937       break;
2938
2939     case rm_nothing:
2940       *max_finish_cycle = max_start_cycle;
2941       *min_finish_cycle = min_start_cycle;
2942       break;
2943
2944     default:
2945       gcc_unreachable ();
2946     }
2947 }
2948
2949 /* The following function is called only for correct program.  The
2950    function defines max reservation of insns in cycles.  */
2951 static void
2952 evaluate_max_reserv_cycles (void)
2953 {
2954   int max_insn_cycles_num;
2955   int min_insn_cycles_num;
2956   decl_t decl;
2957   int i;
2958
2959   description->max_insn_reserv_cycles = 0;
2960   for (i = 0; i < description->decls_num; i++)
2961     {
2962       decl = description->decls [i];
2963       if (decl->mode == dm_insn_reserv)
2964       {
2965         process_regexp_cycles (DECL_INSN_RESERV (decl)->regexp, 0, 0,
2966                                &max_insn_cycles_num, &min_insn_cycles_num);
2967         if (description->max_insn_reserv_cycles < max_insn_cycles_num)
2968           description->max_insn_reserv_cycles = max_insn_cycles_num;
2969       }
2970     }
2971   description->max_insn_reserv_cycles++;
2972 }
2973
2974 /* The following function calls functions for checking all
2975    description.  */
2976 static void
2977 check_all_description (void)
2978 {
2979   process_decls ();
2980   check_automaton_usage ();
2981   process_regexp_decls ();
2982   check_usage ();
2983   check_loops_in_regexps ();
2984   if (!have_error)
2985     evaluate_max_reserv_cycles ();
2986 }
2987
2988 \f
2989
2990 /* The page contains abstract data `ticker'.  This data is used to
2991    report time of different phases of building automata.  It is
2992    possibly to write a description for which automata will be built
2993    during several minutes even on fast machine.  */
2994
2995 /* The following function creates ticker and makes it active.  */
2996 static ticker_t
2997 create_ticker (void)
2998 {
2999   ticker_t ticker;
3000
3001   ticker.modified_creation_time = get_run_time ();
3002   ticker.incremented_off_time = 0;
3003   return ticker;
3004 }
3005
3006 /* The following function switches off given ticker.  */
3007 static void
3008 ticker_off (ticker_t *ticker)
3009 {
3010   if (ticker->incremented_off_time == 0)
3011     ticker->incremented_off_time = get_run_time () + 1;
3012 }
3013
3014 /* The following function switches on given ticker.  */
3015 static void
3016 ticker_on (ticker_t *ticker)
3017 {
3018   if (ticker->incremented_off_time != 0)
3019     {
3020       ticker->modified_creation_time
3021         += get_run_time () - ticker->incremented_off_time + 1;
3022       ticker->incremented_off_time = 0;
3023     }
3024 }
3025
3026 /* The following function returns current time in milliseconds since
3027    the moment when given ticker was created.  */
3028 static int
3029 active_time (ticker_t ticker)
3030 {
3031   if (ticker.incremented_off_time != 0)
3032     return ticker.incremented_off_time - 1 - ticker.modified_creation_time;
3033   else
3034     return get_run_time () - ticker.modified_creation_time;
3035 }
3036
3037 /* The following function returns string representation of active time
3038    of given ticker.  The result is string representation of seconds
3039    with accuracy of 1/100 second.  Only result of the last call of the
3040    function exists.  Therefore the following code is not correct
3041
3042       printf ("parser time: %s\ngeneration time: %s\n",
3043               active_time_string (parser_ticker),
3044               active_time_string (generation_ticker));
3045
3046    Correct code has to be the following
3047
3048       printf ("parser time: %s\n", active_time_string (parser_ticker));
3049       printf ("generation time: %s\n",
3050               active_time_string (generation_ticker));
3051
3052 */
3053 static void
3054 print_active_time (FILE *f, ticker_t ticker)
3055 {
3056   int msecs;
3057
3058   msecs = active_time (ticker);
3059   fprintf (f, "%d.%06d", msecs / 1000000, msecs % 1000000);
3060 }
3061
3062 \f
3063
3064 /* The following variable value is number of automaton which are
3065    really being created.  This value is defined on the base of
3066    argument of option `-split'.  If the variable has zero value the
3067    number of automata is defined by the constructions `%automaton'.
3068    This case occurs when option `-split' is absent or has zero
3069    argument.  If constructions `define_automaton' is absent only one
3070    automaton is created.  */
3071 static int automata_num;
3072
3073 /* The following variable values are times of
3074        o transformation of regular expressions
3075        o building NDFA (DFA if !ndfa_flag)
3076        o NDFA -> DFA   (simply the same automaton if !ndfa_flag)
3077        o DFA minimization
3078        o building insn equivalence classes
3079        o all previous ones
3080        o code output */
3081 static ticker_t transform_time;
3082 static ticker_t NDFA_time;
3083 static ticker_t NDFA_to_DFA_time;
3084 static ticker_t minimize_time;
3085 static ticker_t equiv_time;
3086 static ticker_t automaton_generation_time;
3087 static ticker_t output_time;
3088
3089 /* The following variable values are times of
3090        all checking
3091        all generation
3092        all pipeline hazard translator work */
3093 static ticker_t check_time;
3094 static ticker_t generation_time;
3095 static ticker_t all_time;
3096
3097 \f
3098
3099 /* Pseudo insn decl which denotes advancing cycle.  */
3100 static decl_t advance_cycle_insn_decl;
3101 static void
3102 add_advance_cycle_insn_decl (void)
3103 {
3104   advance_cycle_insn_decl = create_node (sizeof (struct decl));
3105   advance_cycle_insn_decl->mode = dm_insn_reserv;
3106   advance_cycle_insn_decl->pos = no_pos;
3107   DECL_INSN_RESERV (advance_cycle_insn_decl)->regexp = NULL;
3108   DECL_INSN_RESERV (advance_cycle_insn_decl)->name = "$advance_cycle";
3109   DECL_INSN_RESERV (advance_cycle_insn_decl)->insn_num
3110     = description->insns_num;
3111   description->decls [description->decls_num] = advance_cycle_insn_decl;
3112   description->decls_num++;
3113   description->insns_num++;
3114 }
3115
3116 \f
3117 /* Abstract data `alternative states' which represents
3118    nondeterministic nature of the description (see comments for
3119    structures alt_state and state).  */
3120
3121 /* List of free states.  */
3122 static alt_state_t first_free_alt_state;
3123
3124 #ifndef NDEBUG
3125 /* The following variables is maximal number of allocated nodes
3126    alt_state.  */
3127 static int allocated_alt_states_num = 0;
3128 #endif
3129
3130 /* The following function returns free node alt_state.  It may be new
3131    allocated node or node freed earlier.  */
3132 static alt_state_t
3133 get_free_alt_state (void)
3134 {
3135   alt_state_t result;
3136
3137   if (first_free_alt_state != NULL)
3138     {
3139       result = first_free_alt_state;
3140       first_free_alt_state = first_free_alt_state->next_alt_state;
3141     }
3142   else
3143     {
3144 #ifndef NDEBUG
3145       allocated_alt_states_num++;
3146 #endif
3147       result = create_node (sizeof (struct alt_state));
3148     }
3149   result->state = NULL;
3150   result->next_alt_state = NULL;
3151   result->next_sorted_alt_state = NULL;
3152   return result;
3153 }
3154
3155 /* The function frees node ALT_STATE.  */
3156 static void
3157 free_alt_state (alt_state_t alt_state)
3158 {
3159   if (alt_state == NULL)
3160     return;
3161   alt_state->next_alt_state = first_free_alt_state;
3162   first_free_alt_state = alt_state;
3163 }
3164
3165 /* The function frees list started with node ALT_STATE_LIST.  */
3166 static void
3167 free_alt_states (alt_state_t alt_states_list)
3168 {
3169   alt_state_t curr_alt_state;
3170   alt_state_t next_alt_state;
3171
3172   for (curr_alt_state = alt_states_list;
3173        curr_alt_state != NULL;
3174        curr_alt_state = next_alt_state)
3175     {
3176       next_alt_state = curr_alt_state->next_alt_state;
3177       free_alt_state (curr_alt_state);
3178     }
3179 }
3180
3181 /* The function compares unique numbers of alt states.  */
3182 static int
3183 alt_state_cmp (const void *alt_state_ptr_1, const void *alt_state_ptr_2)
3184 {
3185   if ((*(alt_state_t *) alt_state_ptr_1)->state->unique_num
3186       == (*(alt_state_t *) alt_state_ptr_2)->state->unique_num)
3187     return 0;
3188   else if ((*(alt_state_t *) alt_state_ptr_1)->state->unique_num
3189            < (*(alt_state_t *) alt_state_ptr_2)->state->unique_num)
3190     return -1;
3191   else
3192     return 1;
3193 }
3194
3195 /* The function sorts ALT_STATES_LIST and removes duplicated alt
3196    states from the list.  The comparison key is alt state unique
3197    number.  */
3198
3199 static alt_state_t
3200 uniq_sort_alt_states (alt_state_t alt_states_list)
3201 {
3202   alt_state_t curr_alt_state;
3203   VEC(alt_state_t,heap) *alt_states;
3204   size_t i;
3205   size_t prev_unique_state_ind;
3206   alt_state_t result;
3207
3208   if (alt_states_list == 0)
3209     return 0;
3210   if (alt_states_list->next_alt_state == 0)
3211     return alt_states_list;
3212
3213   alt_states = VEC_alloc (alt_state_t,heap, 150);
3214   for (curr_alt_state = alt_states_list;
3215        curr_alt_state != NULL;
3216        curr_alt_state = curr_alt_state->next_alt_state)
3217     VEC_safe_push (alt_state_t,heap, alt_states, curr_alt_state);
3218
3219   qsort (VEC_address (alt_state_t, alt_states),
3220          VEC_length  (alt_state_t, alt_states),
3221          sizeof (alt_state_t), alt_state_cmp);
3222
3223   prev_unique_state_ind = 0;
3224   for (i = 1; i < VEC_length (alt_state_t, alt_states); i++)
3225     if (VEC_index (alt_state_t, alt_states, prev_unique_state_ind)->state
3226         != VEC_index (alt_state_t, alt_states, i)->state)
3227       {
3228         prev_unique_state_ind++;
3229         VEC_replace (alt_state_t, alt_states, prev_unique_state_ind,
3230                      VEC_index (alt_state_t, alt_states, i));
3231       }
3232   VEC_truncate (alt_state_t, alt_states, prev_unique_state_ind + 1);
3233
3234   for (i = 1; i < VEC_length (alt_state_t, alt_states); i++)
3235     VEC_index (alt_state_t, alt_states, i-1)->next_sorted_alt_state
3236       = VEC_index (alt_state_t, alt_states, i);
3237   VEC_last (alt_state_t, alt_states)->next_sorted_alt_state = 0;
3238
3239   result = VEC_index (alt_state_t, alt_states, 0);
3240
3241   VEC_free (alt_state_t,heap, alt_states);
3242   return result;
3243 }
3244
3245 /* The function checks equality of alt state lists.  Remember that the
3246    lists must be already sorted by the previous function.  */
3247 static int
3248 alt_states_eq (alt_state_t alt_states_1, alt_state_t alt_states_2)
3249 {
3250   while (alt_states_1 != NULL && alt_states_2 != NULL
3251          && alt_state_cmp (&alt_states_1, &alt_states_2) == 0)
3252     {
3253       alt_states_1 = alt_states_1->next_sorted_alt_state;
3254       alt_states_2 = alt_states_2->next_sorted_alt_state;
3255     }
3256   return alt_states_1 == alt_states_2;
3257 }
3258
3259 /* Initialization of the abstract data.  */
3260 static void
3261 initiate_alt_states (void)
3262 {
3263   first_free_alt_state = NULL;
3264 }
3265
3266 /* Finishing work with the abstract data.  */
3267 static void
3268 finish_alt_states (void)
3269 {
3270 }
3271
3272 \f
3273
3274 /* The page contains macros for work with bits strings.  We could use
3275    standard gcc bitmap or sbitmap but it would result in difficulties
3276    of building canadian cross.  */
3277
3278 /* Set bit number bitno in the bit string.  The macro is not side
3279    effect proof.  */
3280 #define SET_BIT(bitstring, bitno)                                         \
3281   (((char *) (bitstring)) [(bitno) / CHAR_BIT] |= 1 << (bitno) % CHAR_BIT)
3282
3283 #define CLEAR_BIT(bitstring, bitno)                                       \
3284   (((char *) (bitstring)) [(bitno) / CHAR_BIT] &= ~(1 << (bitno) % CHAR_BIT))
3285
3286 /* Test if bit number bitno in the bitstring is set.  The macro is not
3287    side effect proof.  */
3288 #define TEST_BIT(bitstring, bitno)                                        \
3289   (((char *) (bitstring)) [(bitno) / CHAR_BIT] >> (bitno) % CHAR_BIT & 1)
3290
3291 \f
3292
3293 /* This page contains abstract data `state'.  */
3294
3295 /* Maximal length of reservations in cycles (>= 1).  */
3296 static int max_cycles_num;
3297
3298 /* Number of set elements (see type set_el_t) needed for
3299    representation of one cycle reservation.  It is depended on units
3300    number.  */
3301 static int els_in_cycle_reserv;
3302
3303 /* Number of set elements (see type set_el_t) needed for
3304    representation of maximal length reservation.  Deterministic
3305    reservation is stored as set (bit string) of length equal to the
3306    variable value * number of bits in set_el_t.  */
3307 static int els_in_reservs;
3308
3309 /* Array of pointers to unit declarations.  */
3310 static unit_decl_t *units_array;
3311
3312 /* Temporary reservation of maximal length.  */
3313 static reserv_sets_t temp_reserv;
3314
3315 /* The state table itself is represented by the following variable.  */
3316 static htab_t state_table;
3317
3318 /* Linked list of free 'state' structures to be recycled.  The
3319    next_equiv_class_state pointer is borrowed for a free list.  */
3320 static state_t first_free_state;
3321
3322 static int curr_unique_state_num;
3323
3324 #ifndef NDEBUG
3325 /* The following variables is maximal number of allocated nodes
3326    `state'.  */
3327 static int allocated_states_num = 0;
3328 #endif
3329
3330 /* Allocate new reservation set.  */
3331 static reserv_sets_t
3332 alloc_empty_reserv_sets (void)
3333 {
3334   reserv_sets_t result;
3335
3336   obstack_blank (&irp, els_in_reservs * sizeof (set_el_t));
3337   result = (reserv_sets_t) obstack_base (&irp);
3338   obstack_finish (&irp);
3339   memset (result, 0, els_in_reservs * sizeof (set_el_t));
3340   return result;
3341 }
3342
3343 /* Hash value of reservation set.  */
3344 static unsigned
3345 reserv_sets_hash_value (reserv_sets_t reservs)
3346 {
3347   set_el_t hash_value;
3348   unsigned result;
3349   int reservs_num, i;
3350   set_el_t *reserv_ptr;
3351
3352   hash_value = 0;
3353   reservs_num = els_in_reservs;
3354   reserv_ptr = reservs;
3355   i = 0;
3356   while (reservs_num != 0)
3357     {
3358       reservs_num--;
3359       hash_value += ((*reserv_ptr >> i)
3360                      | (*reserv_ptr << (sizeof (set_el_t) * CHAR_BIT - i)));
3361       i++;
3362       if (i == sizeof (set_el_t) * CHAR_BIT)
3363         i = 0;
3364       reserv_ptr++;
3365     }
3366   if (sizeof (set_el_t) <= sizeof (unsigned))
3367     return hash_value;
3368   result = 0;
3369   for (i = sizeof (set_el_t); i > 0; i -= sizeof (unsigned) - 1)
3370     {
3371       result += (unsigned) hash_value;
3372       hash_value >>= (sizeof (unsigned) - 1) * CHAR_BIT;
3373     }
3374   return result;
3375 }
3376
3377 /* Comparison of given reservation sets.  */
3378 static int
3379 reserv_sets_cmp (reserv_sets_t reservs_1, reserv_sets_t reservs_2)
3380 {
3381   int reservs_num;
3382   set_el_t *reserv_ptr_1;
3383   set_el_t *reserv_ptr_2;
3384
3385   gcc_assert (reservs_1 && reservs_2);
3386   reservs_num = els_in_reservs;
3387   reserv_ptr_1 = reservs_1;
3388   reserv_ptr_2 = reservs_2;
3389   while (reservs_num != 0 && *reserv_ptr_1 == *reserv_ptr_2)
3390     {
3391       reservs_num--;
3392       reserv_ptr_1++;
3393       reserv_ptr_2++;
3394     }
3395   if (reservs_num == 0)
3396     return 0;
3397   else if (*reserv_ptr_1 < *reserv_ptr_2)
3398     return -1;
3399   else
3400     return 1;
3401 }
3402
3403 /* The function checks equality of the reservation sets.  */
3404 static int
3405 reserv_sets_eq (reserv_sets_t reservs_1, reserv_sets_t reservs_2)
3406 {
3407   return reserv_sets_cmp (reservs_1, reservs_2) == 0;
3408 }
3409
3410 /* Set up in the reservation set that unit with UNIT_NUM is used on
3411    CYCLE_NUM.  */
3412 static void
3413 set_unit_reserv (reserv_sets_t reservs, int cycle_num, int unit_num)
3414 {
3415   gcc_assert (cycle_num < max_cycles_num);
3416   SET_BIT (reservs, cycle_num * els_in_cycle_reserv
3417            * sizeof (set_el_t) * CHAR_BIT + unit_num);
3418 }
3419
3420 /* Set up in the reservation set RESERVS that unit with UNIT_NUM is
3421    used on CYCLE_NUM.  */
3422 static int
3423 test_unit_reserv (reserv_sets_t reservs, int cycle_num, int unit_num)
3424 {
3425   gcc_assert (cycle_num < max_cycles_num);
3426   return TEST_BIT (reservs, cycle_num * els_in_cycle_reserv
3427                    * sizeof (set_el_t) * CHAR_BIT + unit_num);
3428 }
3429
3430 /* The function checks that the reservation sets are intersected,
3431    i.e. there is a unit reservation on a cycle in both reservation
3432    sets.  */
3433 static int
3434 reserv_sets_are_intersected (reserv_sets_t operand_1,
3435                              reserv_sets_t operand_2)
3436 {
3437   set_el_t *el_ptr_1;
3438   set_el_t *el_ptr_2;
3439   set_el_t *cycle_ptr_1;
3440   set_el_t *cycle_ptr_2;
3441
3442   gcc_assert (operand_1 && operand_2);
3443   for (el_ptr_1 = operand_1, el_ptr_2 = operand_2;
3444        el_ptr_1 < operand_1 + els_in_reservs;
3445        el_ptr_1++, el_ptr_2++)
3446     if (*el_ptr_1 & *el_ptr_2)
3447       return 1;
3448   reserv_sets_or (temp_reserv, operand_1, operand_2);
3449   for (cycle_ptr_1 = operand_1, cycle_ptr_2 = operand_2;
3450        cycle_ptr_1 < operand_1 + els_in_reservs;
3451        cycle_ptr_1 += els_in_cycle_reserv, cycle_ptr_2 += els_in_cycle_reserv)
3452     {
3453       for (el_ptr_1 = cycle_ptr_1, el_ptr_2 = get_excl_set (cycle_ptr_2);
3454            el_ptr_1 < cycle_ptr_1 + els_in_cycle_reserv;
3455            el_ptr_1++, el_ptr_2++)
3456         if (*el_ptr_1 & *el_ptr_2)
3457           return 1;
3458       if (!check_presence_pattern_sets (cycle_ptr_1, cycle_ptr_2, FALSE))
3459         return 1;
3460       if (!check_presence_pattern_sets (temp_reserv + (cycle_ptr_2
3461                                                        - operand_2),
3462                                         cycle_ptr_2, TRUE))
3463         return 1;
3464       if (!check_absence_pattern_sets (cycle_ptr_1, cycle_ptr_2, FALSE))
3465         return 1;
3466       if (!check_absence_pattern_sets (temp_reserv + (cycle_ptr_2 - operand_2),
3467                                        cycle_ptr_2, TRUE))
3468         return 1;
3469     }
3470   return 0;
3471 }
3472
3473 /* The function sets up RESULT bits by bits of OPERAND shifted on one
3474    cpu cycle.  The remaining bits of OPERAND (representing the last
3475    cycle unit reservations) are not changed.  */
3476 static void
3477 reserv_sets_shift (reserv_sets_t result, reserv_sets_t operand)
3478 {
3479   int i;
3480
3481   gcc_assert (result && operand && result != operand);
3482   for (i = els_in_cycle_reserv; i < els_in_reservs; i++)
3483     result [i - els_in_cycle_reserv] = operand [i];
3484 }
3485
3486 /* OR of the reservation sets.  */
3487 static void
3488 reserv_sets_or (reserv_sets_t result, reserv_sets_t operand_1,
3489                 reserv_sets_t operand_2)
3490 {
3491   set_el_t *el_ptr_1;
3492   set_el_t *el_ptr_2;
3493   set_el_t *result_set_el_ptr;
3494
3495   gcc_assert (result && operand_1 && operand_2);
3496   for (el_ptr_1 = operand_1, el_ptr_2 = operand_2, result_set_el_ptr = result;
3497        el_ptr_1 < operand_1 + els_in_reservs;
3498        el_ptr_1++, el_ptr_2++, result_set_el_ptr++)
3499     *result_set_el_ptr = *el_ptr_1 | *el_ptr_2;
3500 }
3501
3502 /* AND of the reservation sets.  */
3503 static void
3504 reserv_sets_and (reserv_sets_t result, reserv_sets_t operand_1,
3505                 reserv_sets_t operand_2)
3506 {
3507   set_el_t *el_ptr_1;
3508   set_el_t *el_ptr_2;
3509   set_el_t *result_set_el_ptr;
3510
3511   gcc_assert (result && operand_1 && operand_2);
3512   for (el_ptr_1 = operand_1, el_ptr_2 = operand_2, result_set_el_ptr = result;
3513        el_ptr_1 < operand_1 + els_in_reservs;
3514        el_ptr_1++, el_ptr_2++, result_set_el_ptr++)
3515     *result_set_el_ptr = *el_ptr_1 & *el_ptr_2;
3516 }
3517
3518 /* The function outputs string representation of units reservation on
3519    cycle START_CYCLE in the reservation set.  The function uses repeat