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