forked from riscvarchive/riscv-gcc
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgenautomata.c
9685 lines (8686 loc) · 296 KB
/
genautomata.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* Pipeline hazard description translator.
Copyright (C) 2000-2020 Free Software Foundation, Inc.
Written by Vladimir Makarov <[email protected]>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.
GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
/* References:
1. The finite state automaton based pipeline hazard recognizer and
instruction scheduler in GCC. V. Makarov. Proceedings of GCC
summit, 2003.
2. Detecting pipeline structural hazards quickly. T. Proebsting,
C. Fraser. Proceedings of ACM SIGPLAN-SIGACT Symposium on
Principles of Programming Languages, pages 280--286, 1994.
This article is a good start point to understand usage of finite
state automata for pipeline hazard recognizers. But I'd
recommend the 1st and 3rd article for more deep understanding.
3. Efficient Instruction Scheduling Using Finite State Automata:
V. Bala and N. Rubin, Proceedings of MICRO-28. This is the best
article about usage of finite state automata for pipeline hazard
recognizers.
The current implementation is described in the 1st article and it
is different from the 3rd article in the following:
1. New operator `|' (alternative) is permitted in functional unit
reservation which can be treated deterministically and
non-deterministically.
2. Possibility of usage of nondeterministic automata too.
3. Possibility to query functional unit reservations for given
automaton state.
4. Several constructions to describe impossible reservations
(`exclusion_set', `presence_set', `final_presence_set',
`absence_set', and `final_absence_set').
5. No reverse automata are generated. Trace instruction scheduling
requires this. It can be easily added in the future if we
really need this.
6. Union of automaton states are not generated yet. It is planned
to be implemented. Such feature is needed to make more accurate
interlock insn scheduling to get state describing functional
unit reservation in a joint CFG point. */
/* This file code processes constructions of machine description file
which describes automaton used for recognition of processor pipeline
hazards by insn scheduler and can be used for other tasks (such as
VLIW insn packing.
The translator functions `gen_cpu_unit', `gen_query_cpu_unit',
`gen_bypass', `gen_excl_set', `gen_presence_set',
`gen_final_presence_set', `gen_absence_set',
`gen_final_absence_set', `gen_automaton', `gen_automata_option',
`gen_reserv', `gen_insn_reserv' are called from file
`genattrtab.c'. They transform RTL constructions describing
automata in .md file into internal representation convenient for
further processing.
The translator major function `expand_automata' processes the
description internal representation into finite state automaton.
It can be divided on:
o checking correctness of the automaton pipeline description
(major function is `check_all_description').
o generating automaton (automata) from the description (major
function is `make_automaton').
o optional transformation of nondeterministic finite state
automata into deterministic ones if the alternative operator
`|' is treated nondeterministically in the description (major
function is NDFA_to_DFA).
o optional minimization of the finite state automata by merging
equivalent automaton states (major function is `minimize_DFA').
o forming tables (some as comb vectors) and attributes
representing the automata (functions output_..._table).
Function `write_automata' outputs the created finite state
automaton as different tables and functions which works with the
automata to inquire automaton state and to change its state. These
function are used by gcc instruction scheduler and may be some
other gcc code. */
#include "bconfig.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "obstack.h"
#include "errors.h"
#include "gensupport.h"
#include <math.h>
#include "fnmatch.h"
#ifndef CHAR_BIT
#define CHAR_BIT 8
#endif
/* Positions in machine description file. Now they are not used. But
they could be used in the future for better diagnostic messages. */
typedef int pos_t;
/* The following is element of vector of current (and planned in the
future) functional unit reservations. */
typedef unsigned HOST_WIDE_INT set_el_t;
/* Reservations of function units are represented by value of the following
type. */
typedef set_el_t *reserv_sets_t;
typedef const set_el_t *const_reserv_sets_t;
/* The following structure describes a ticker. */
struct ticker
{
/* The following member value is time of the ticker creation with
taking into account time when the ticker is off. Active time of
the ticker is current time minus the value. */
int modified_creation_time;
/* The following member value is time (incremented by one) when the
ticker was off. Zero value means that now the ticker is on. */
int incremented_off_time;
};
/* The ticker is represented by the following type. */
typedef struct ticker ticker_t;
/* The following type describes elements of output vectors. */
typedef HOST_WIDE_INT vect_el_t;
/* Forward declaration of structures of internal representation of
pipeline description based on NDFA. */
struct unit_decl;
struct bypass_decl;
struct result_decl;
struct automaton_decl;
struct unit_pattern_rel_decl;
struct reserv_decl;
struct insn_reserv_decl;
struct decl;
struct unit_regexp;
struct result_regexp;
struct reserv_regexp;
struct nothing_regexp;
struct sequence_regexp;
struct repeat_regexp;
struct allof_regexp;
struct oneof_regexp;
struct regexp;
struct description;
struct unit_set_el;
struct pattern_set_el;
struct pattern_reserv;
struct state;
struct alt_state;
struct arc;
struct ainsn;
struct automaton;
struct state_ainsn_table;
/* The following typedefs are for brevity. */
typedef struct unit_decl *unit_decl_t;
typedef const struct unit_decl *const_unit_decl_t;
typedef struct decl *decl_t;
typedef const struct decl *const_decl_t;
typedef struct regexp *regexp_t;
typedef struct unit_set_el *unit_set_el_t;
typedef struct pattern_set_el *pattern_set_el_t;
typedef struct pattern_reserv *pattern_reserv_t;
typedef struct alt_state *alt_state_t;
typedef struct state *state_t;
typedef const struct state *const_state_t;
typedef struct arc *arc_t;
typedef struct ainsn *ainsn_t;
typedef struct automaton *automaton_t;
typedef struct automata_list_el *automata_list_el_t;
typedef const struct automata_list_el *const_automata_list_el_t;
typedef struct state_ainsn_table *state_ainsn_table_t;
/* Undefined position. */
static pos_t no_pos = 0;
/* All IR is stored in the following obstack. */
static struct obstack irp;
/* Declare vector types for various data structures: */
typedef vec<vect_el_t> vla_hwint_t;
/* Forward declarations of functions used before their definitions, only. */
static regexp_t gen_regexp_sequence (const char *);
static void reserv_sets_or (reserv_sets_t, reserv_sets_t,
reserv_sets_t);
static reserv_sets_t get_excl_set (reserv_sets_t);
static int check_presence_pattern_sets (reserv_sets_t,
reserv_sets_t, int);
static int check_absence_pattern_sets (reserv_sets_t, reserv_sets_t,
int);
static arc_t first_out_arc (const_state_t);
static arc_t next_out_arc (arc_t);
/* Options with the following names can be set up in automata_option
construction. Because the strings occur more one time we use the
macros. */
#define NO_MINIMIZATION_OPTION "-no-minimization"
#define TIME_OPTION "-time"
#define STATS_OPTION "-stats"
#define V_OPTION "-v"
#define W_OPTION "-w"
#define NDFA_OPTION "-ndfa"
#define COLLAPSE_OPTION "-collapse-ndfa"
#define NO_COMB_OPTION "-no-comb-vect"
#define PROGRESS_OPTION "-progress"
/* The following flags are set up by function `initiate_automaton_gen'. */
/* Make automata with nondeterministic reservation by insns (`-ndfa'). */
static int ndfa_flag;
/* When making an NDFA, produce additional transitions that collapse
NDFA state into a deterministic one suitable for querying CPU units.
Provide advance-state transitions only for deterministic states. */
static int collapse_flag;
/* Do not make minimization of DFA (`-no-minimization'). */
static int no_minimization_flag;
/* Do not try to generate a comb vector (`-no-comb-vect'). */
static int no_comb_flag;
/* Value of this variable is number of automata being generated. The
actual number of automata may be less this value if there is not
sufficient number of units. This value is defined by argument of
option `-split' or by constructions automaton if the value is zero
(it is default value of the argument). */
static int split_argument;
/* Flag of output time statistics (`-time'). */
static int time_flag;
/* Flag of automata statistics (`-stats'). */
static int stats_flag;
/* Flag of creation of description file which contains description of
result automaton and statistics information (`-v'). */
static int v_flag;
/* Flag of output of a progress bar showing how many states were
generated so far for automaton being processed (`-progress'). */
static int progress_flag;
/* Flag of generating warning instead of error for non-critical errors
(`-w'). */
static int w_flag;
/* Output file for pipeline hazard recognizer (PHR) being generated.
The value is NULL if the file is not defined. */
static FILE *output_file;
/* Description file of PHR. The value is NULL if the file is not
created. */
static FILE *output_description_file;
/* PHR description file name. */
static char *output_description_file_name;
/* Value of the following variable is node representing description
being processed. This is start point of IR. */
static struct description *description;
/* This page contains description of IR structure (nodes). */
enum decl_mode
{
dm_unit,
dm_bypass,
dm_automaton,
dm_excl,
dm_presence,
dm_absence,
dm_reserv,
dm_insn_reserv
};
/* This describes define_cpu_unit and define_query_cpu_unit (see file
rtl.def). */
struct unit_decl
{
const char *name;
/* NULL if the automaton name is absent. */
const char *automaton_name;
/* If the following value is not zero, the cpu unit reservation is
described in define_query_cpu_unit. */
char query_p;
/* The following fields are defined by checker. */
/* The following field value is nonzero if the unit is used in an
regexp. */
char unit_is_used;
/* The following field value is order number (0, 1, ...) of given
unit. */
int unit_num;
/* The following field value is corresponding declaration of
automaton which was given in description. If the field value is
NULL then automaton in the unit declaration was absent. */
struct automaton_decl *automaton_decl;
/* The following field value is maximal cycle number (1, ...) on
which given unit occurs in insns. Zero value means that given
unit is not used in insns. */
int max_occ_cycle_num;
/* The following field value is minimal cycle number (0, ...) on
which given unit occurs in insns. -1 value means that given
unit is not used in insns. */
int min_occ_cycle_num;
/* The following list contains units which conflict with given
unit. */
unit_set_el_t excl_list;
/* The following list contains patterns which are required to
reservation of given unit. */
pattern_set_el_t presence_list;
pattern_set_el_t final_presence_list;
/* The following list contains patterns which should be not present
in reservation for given unit. */
pattern_set_el_t absence_list;
pattern_set_el_t final_absence_list;
/* The following is used only when `query_p' has nonzero value.
This is query number for the unit. */
int query_num;
/* The following is the last cycle on which the unit was checked for
correct distributions of units to automata in a regexp. */
int last_distribution_check_cycle;
/* The following fields are defined by automaton generator. */
/* The following field value is number of the automaton to which
given unit belongs. */
int corresponding_automaton_num;
/* If the following value is not zero, the cpu unit is present in a
`exclusion_set' or in right part of a `presence_set',
`final_presence_set', `absence_set', and
`final_absence_set'define_query_cpu_unit. */
char in_set_p;
};
/* This describes define_bypass (see file rtl.def). */
struct bypass_decl
{
int latency;
const char *out_pattern;
const char *in_pattern;
const char *bypass_guard_name;
/* The following fields are defined by checker. */
/* output and input insns of given bypass. */
struct insn_reserv_decl *out_insn_reserv;
struct insn_reserv_decl *in_insn_reserv;
/* The next bypass for given output insn. */
struct bypass_decl *next;
};
/* This describes define_automaton (see file rtl.def). */
struct automaton_decl
{
const char *name;
/* The following fields are defined by automaton generator. */
/* The following field value is nonzero if the automaton is used in
an regexp definition. */
char automaton_is_used;
/* The following fields are defined by checker. */
/* The following field value is the corresponding automaton. This
field is not NULL only if the automaton is present in unit
declarations and the automatic partition on automata is not
used. */
automaton_t corresponding_automaton;
};
/* This describes exclusion relations: exclusion_set (see file
rtl.def). */
struct excl_rel_decl
{
int all_names_num;
int first_list_length;
char *names [1];
};
/* This describes unit relations: [final_]presence_set or
[final_]absence_set (see file rtl.def). */
struct unit_pattern_rel_decl
{
int final_p;
int names_num;
int patterns_num;
char **names;
char ***patterns;
};
/* This describes define_reservation (see file rtl.def). */
struct reserv_decl
{
const char *name;
regexp_t regexp;
/* The following fields are defined by checker. */
/* The following field value is nonzero if the unit is used in an
regexp. */
char reserv_is_used;
/* The following field is used to check up cycle in expression
definition. */
int loop_pass_num;
};
/* This describes define_insn_reservation (see file rtl.def). */
struct insn_reserv_decl
{
rtx condexp;
int default_latency;
regexp_t regexp;
const char *name;
/* The following fields are defined by checker. */
/* The following field value is order number (0, 1, ...) of given
insn. */
int insn_num;
/* The following field value is list of bypasses in which given insn
is output insn. Bypasses with the same input insn stay one after
another in the list in the same order as their occurrences in the
description but the bypass without a guard stays always the last
in a row of bypasses with the same input insn. */
struct bypass_decl *bypass_list;
/* The following fields are defined by automaton generator. */
/* The following field is the insn regexp transformed that
the regexp has not optional regexp, repetition regexp, and an
reservation name (i.e. reservation identifiers are changed by the
corresponding regexp) and all alternations are the top level
of the regexp. The value can be NULL only if it is special
insn `cycle advancing'. */
regexp_t transformed_regexp;
/* The following field value is list of arcs marked given
insn. The field is used in transformation NDFA -> DFA. */
arc_t arcs_marked_by_insn;
/* The two following fields are used during minimization of a finite state
automaton. */
/* The field value is number of equivalence class of state into
which arc marked by given insn enters from a state (fixed during
an automaton minimization). */
int equiv_class_num;
/* The following member value is the list to automata which can be
changed by the insn issue. */
automata_list_el_t important_automata_list;
/* The following member is used to process insn once for output. */
int processed_p;
};
/* This contains a declaration mentioned above. */
struct decl
{
/* What node in the union? */
enum decl_mode mode;
pos_t pos;
union
{
struct unit_decl unit;
struct bypass_decl bypass;
struct automaton_decl automaton;
struct excl_rel_decl excl;
struct unit_pattern_rel_decl presence;
struct unit_pattern_rel_decl absence;
struct reserv_decl reserv;
struct insn_reserv_decl insn_reserv;
} decl;
};
/* The following structures represent parsed reservation strings. */
enum regexp_mode
{
rm_unit,
rm_reserv,
rm_nothing,
rm_sequence,
rm_repeat,
rm_allof,
rm_oneof
};
/* Cpu unit in reservation. */
struct unit_regexp
{
const char *name;
unit_decl_t unit_decl;
};
/* Define_reservation in a reservation. */
struct reserv_regexp
{
const char *name;
struct reserv_decl *reserv_decl;
};
/* Absence of reservation (represented by string `nothing'). */
struct nothing_regexp
{
/* This used to be empty but ISO C doesn't allow that. */
char unused;
};
/* Representation of reservations separated by ',' (see file
rtl.def). */
struct sequence_regexp
{
int regexps_num;
regexp_t regexps [1];
};
/* Representation of construction `repeat' (see file rtl.def). */
struct repeat_regexp
{
int repeat_num;
regexp_t regexp;
};
/* Representation of reservations separated by '+' (see file
rtl.def). */
struct allof_regexp
{
int regexps_num;
regexp_t regexps [1];
};
/* Representation of reservations separated by '|' (see file
rtl.def). */
struct oneof_regexp
{
int regexps_num;
regexp_t regexps [1];
};
/* Representation of a reservation string. */
struct regexp
{
/* What node in the union? */
enum regexp_mode mode;
pos_t pos;
union
{
struct unit_regexp unit;
struct reserv_regexp reserv;
struct nothing_regexp nothing;
struct sequence_regexp sequence;
struct repeat_regexp repeat;
struct allof_regexp allof;
struct oneof_regexp oneof;
} regexp;
};
/* Represents description of pipeline hazard description based on
NDFA. */
struct description
{
int decls_num, normal_decls_num;
/* The following fields are defined by checker. */
/* The following fields values are correspondingly number of all
units, query units, and insns in the description. */
int units_num;
int query_units_num;
int insns_num;
/* The following field value is max length (in cycles) of
reservations of insns. The field value is defined only for
correct programs. */
int max_insn_reserv_cycles;
/* The following fields are defined by automaton generator. */
/* The following field value is the first automaton. */
automaton_t first_automaton;
/* The following field is created by pipeline hazard parser and
contains all declarations. We allocate additional entries for
two special insns which are added by the automaton generator. */
decl_t decls [1];
};
/* The following nodes are created in automaton checker. */
/* The following nodes represent exclusion set for cpu units. Each
element is accessed through only one excl_list. */
struct unit_set_el
{
unit_decl_t unit_decl;
unit_set_el_t next_unit_set_el;
};
/* The following nodes represent presence or absence pattern for cpu
units. Each element is accessed through only one presence_list or
absence_list. */
struct pattern_set_el
{
/* The number of units in unit_decls. */
int units_num;
/* The units forming the pattern. */
struct unit_decl **unit_decls;
pattern_set_el_t next_pattern_set_el;
};
/* The following nodes are created in automaton generator. */
/* The following nodes represent presence or absence pattern for cpu
units. Each element is accessed through only one element of
unit_presence_set_table or unit_absence_set_table. */
struct pattern_reserv
{
reserv_sets_t reserv;
pattern_reserv_t next_pattern_reserv;
};
/* The following node type describes state automaton. The state may
be deterministic or non-deterministic. Non-deterministic state has
several component states which represent alternative cpu units
reservations. The state also is used for describing a
deterministic reservation of automaton insn. */
struct state
{
/* The following member value is nonzero if there is a transition by
cycle advancing. */
int new_cycle_p;
/* The following field is list of processor unit reservations on
each cycle. */
reserv_sets_t reservs;
/* The following field is unique number of given state between other
states. */
int unique_num;
/* The following field value is automaton to which given state
belongs. */
automaton_t automaton;
/* The following field value is the first arc output from given
state. */
arc_t first_out_arc;
unsigned int num_out_arcs;
/* The following field is used to form NDFA. */
char it_was_placed_in_stack_for_NDFA_forming;
/* The following field is used to form DFA. */
char it_was_placed_in_stack_for_DFA_forming;
/* The following field is used to transform NDFA to DFA and DFA
minimization. The field value is not NULL if the state is a
compound state. In this case the value of field `unit_sets_list'
is NULL. All states in the list are in the hash table. The list
is formed through field `next_sorted_alt_state'. We should
support only one level of nesting state. */
alt_state_t component_states;
/* The following field is used for passing graph of states. */
int pass_num;
/* The list of states belonging to one equivalence class is formed
with the aid of the following field. */
state_t next_equiv_class_state;
/* The two following fields are used during minimization of a finite
state automaton. */
int equiv_class_num_1, equiv_class_num_2;
/* The following field is used during minimization of a finite state
automaton. The field value is state corresponding to equivalence
class to which given state belongs. */
state_t equiv_class_state;
unsigned int *presence_signature;
/* The following field value is the order number of given state.
The states in final DFA is enumerated with the aid of the
following field. */
int order_state_num;
/* This member is used for passing states for searching minimal
delay time. */
int state_pass_num;
/* The following member is used to evaluate min issue delay of insn
for a state. */
int min_insn_issue_delay;
};
/* Automaton arc. */
struct arc
{
/* The following field refers for the state into which given arc
enters. */
state_t to_state;
/* The following field describes that the insn issue (with cycle
advancing for special insn `cycle advancing' and without cycle
advancing for others) makes transition from given state to
another given state. */
ainsn_t insn;
/* The following field value is the next arc output from the same
state. */
arc_t next_out_arc;
/* List of arcs marked given insn is formed with the following
field. The field is used in transformation NDFA -> DFA. */
arc_t next_arc_marked_by_insn;
};
/* The following node type describes a deterministic alternative in
non-deterministic state which characterizes cpu unit reservations
of automaton insn or which is part of NDFA. */
struct alt_state
{
/* The following field is a deterministic state which characterizes
unit reservations of the instruction. */
state_t state;
/* The following field refers to the next state which characterizes
unit reservations of the instruction. */
alt_state_t next_alt_state;
/* The following field refers to the next state in sorted list. */
alt_state_t next_sorted_alt_state;
};
/* The following node type describes insn of automaton. They are
labels of FA arcs. */
struct ainsn
{
/* The following field value is the corresponding insn declaration
of description. */
struct insn_reserv_decl *insn_reserv_decl;
/* The following field value is the next insn declaration for an
automaton. */
ainsn_t next_ainsn;
/* The following field is states which characterize automaton unit
reservations of the instruction. The value can be NULL only if it
is special insn `cycle advancing'. */
alt_state_t alt_states;
/* The following field is sorted list of states which characterize
automaton unit reservations of the instruction. The value can be
NULL only if it is special insn `cycle advancing'. */
alt_state_t sorted_alt_states;
/* The following field refers the next automaton insn with
the same reservations. */
ainsn_t next_same_reservs_insn;
/* The following field is flag of the first automaton insn with the
same reservations in the declaration list. Only arcs marked such
insn is present in the automaton. This significantly decreases
memory requirements especially when several automata are
formed. */
char first_insn_with_same_reservs;
/* The following member has nonzero value if there is arc from state of
the automaton marked by the ainsn. */
char arc_exists_p;
/* Cyclic list of insns of an equivalence class is formed with the
aid of the following field. */
ainsn_t next_equiv_class_insn;
/* The following field value is nonzero if the insn declaration is
the first insn declaration with given equivalence number. */
char first_ainsn_with_given_equivalence_num;
/* The following field is number of class of equivalence of insns.
It is necessary because many insns may be equivalent with the
point of view of pipeline hazards. */
int insn_equiv_class_num;
/* The following member value is TRUE if there is an arc in the
automaton marked by the insn into another state. In other
words, the insn can change the state of the automaton. */
int important_p;
};
/* The following describes an automaton for PHR. */
struct automaton
{
/* The following field value is the list of insn declarations for
given automaton. */
ainsn_t ainsn_list;
/* Pointers to the ainsns corresponding to the special reservations. */
ainsn_t advance_ainsn, collapse_ainsn;
/* The following field value is the corresponding automaton
declaration. This field is not NULL only if the automatic
partition on automata is not used. */
struct automaton_decl *corresponding_automaton_decl;
/* The following field value is the next automaton. */
automaton_t next_automaton;
/* The following field is start state of FA. There are not unit
reservations in the state. */
state_t start_state;
/* The following field value is number of equivalence classes of
insns (see field `insn_equiv_class_num' in
`insn_reserv_decl'). */
int insn_equiv_classes_num;
/* The following field value is number of states of final DFA. */
int achieved_states_num;
/* The following field value is the order number (0, 1, ...) of
given automaton. */
int automaton_order_num;
/* The following fields contain statistics information about
building automaton. */
int NDFA_states_num, DFA_states_num;
/* The following field value is defined only if minimization of DFA
is used. */
int minimal_DFA_states_num;
int NDFA_arcs_num, DFA_arcs_num;
/* The following field value is defined only if minimization of DFA
is used. */
int minimal_DFA_arcs_num;
/* The following member refers for two table state x ainsn -> int.
??? Above sentence is incomprehensible. */
state_ainsn_table_t trans_table;
/* The following member value is maximal value of min issue delay
for insns of the automaton. */
int max_min_delay;
/* Usually min issue delay is small and we can place several (2, 4,
8) elements in one vector element. So the compression factor can
be 1 (no compression), 2, 4, 8. */
int min_issue_delay_table_compression_factor;
/* Total number of locked states in this automaton. */
int locked_states;
};
/* The following is the element of the list of automata. */
struct automata_list_el
{
/* The automaton itself. */
automaton_t automaton;
/* The next automata set element. */
automata_list_el_t next_automata_list_el;
};
/* The following structure describes a table state X ainsn -> int(>= 0). */
struct state_ainsn_table
{
/* Automaton to which given table belongs. */
automaton_t automaton;
/* The following tree vectors for comb vector implementation of the
table. */
vla_hwint_t comb_vect;
vla_hwint_t check_vect;
vla_hwint_t base_vect;
/* This is simple implementation of the table. */
vla_hwint_t full_vect;
/* Minimal and maximal values of the previous vectors. */
int min_comb_vect_el_value, max_comb_vect_el_value;
int min_base_vect_el_value, max_base_vect_el_value;
};
/* Macros to access members of unions. Use only them for access to
union members of declarations and regexps. */
#if CHECKING_P && (GCC_VERSION >= 2007)
#define DECL_UNIT(d) __extension__ \
(({ __typeof (d) const _decl = (d); \
if (_decl->mode != dm_unit) \
decl_mode_check_failed (_decl->mode, "dm_unit", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.unit; }))
#define DECL_BYPASS(d) __extension__ \
(({ __typeof (d) const _decl = (d); \
if (_decl->mode != dm_bypass) \
decl_mode_check_failed (_decl->mode, "dm_bypass", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.bypass; }))
#define DECL_AUTOMATON(d) __extension__ \
(({ __typeof (d) const _decl = (d); \
if (_decl->mode != dm_automaton) \
decl_mode_check_failed (_decl->mode, "dm_automaton", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.automaton; }))
#define DECL_EXCL(d) __extension__ \
(({ __typeof (d) const _decl = (d); \
if (_decl->mode != dm_excl) \
decl_mode_check_failed (_decl->mode, "dm_excl", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.excl; }))
#define DECL_PRESENCE(d) __extension__ \
(({ __typeof (d) const _decl = (d); \
if (_decl->mode != dm_presence) \
decl_mode_check_failed (_decl->mode, "dm_presence", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.presence; }))
#define DECL_ABSENCE(d) __extension__ \
(({ __typeof (d) const _decl = (d); \
if (_decl->mode != dm_absence) \
decl_mode_check_failed (_decl->mode, "dm_absence", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.absence; }))
#define DECL_RESERV(d) __extension__ \
(({ __typeof (d) const _decl = (d); \
if (_decl->mode != dm_reserv) \
decl_mode_check_failed (_decl->mode, "dm_reserv", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.reserv; }))
#define DECL_INSN_RESERV(d) __extension__ \
(({ __typeof (d) const _decl = (d); \
if (_decl->mode != dm_insn_reserv) \
decl_mode_check_failed (_decl->mode, "dm_insn_reserv", \
__FILE__, __LINE__, __FUNCTION__); \
&(_decl)->decl.insn_reserv; }))
static const char *decl_name (enum decl_mode);
static void decl_mode_check_failed (enum decl_mode, const char *,
const char *, int, const char *)
ATTRIBUTE_NORETURN;
/* Return string representation of declaration mode MODE. */
static const char *
decl_name (enum decl_mode mode)
{
static char str [100];
if (mode == dm_unit)
return "dm_unit";
else if (mode == dm_bypass)
return "dm_bypass";
else if (mode == dm_automaton)
return "dm_automaton";
else if (mode == dm_excl)
return "dm_excl";
else if (mode == dm_presence)
return "dm_presence";
else if (mode == dm_absence)
return "dm_absence";
else if (mode == dm_reserv)
return "dm_reserv";
else if (mode == dm_insn_reserv)
return "dm_insn_reserv";
else
sprintf (str, "unknown (%d)", (int) mode);
return str;
}
/* The function prints message about unexpected declaration and finish
the program. */
static void
decl_mode_check_failed (enum decl_mode mode, const char *expected_mode_str,
const char *file, int line, const char *func)
{
fprintf
(stderr,
"\n%s: %d: error in %s: DECL check: expected decl %s, have %s\n",
file, line, func, expected_mode_str, decl_name (mode));
exit (1);
}
#define REGEXP_UNIT(r) __extension__ \
(({ struct regexp *const _regexp = (r); \
if (_regexp->mode != rm_unit) \
regexp_mode_check_failed (_regexp->mode, "rm_unit", \
__FILE__, __LINE__, __FUNCTION__); \
&(_regexp)->regexp.unit; }))
#define REGEXP_RESERV(r) __extension__ \
(({ struct regexp *const _regexp = (r); \
if (_regexp->mode != rm_reserv) \
regexp_mode_check_failed (_regexp->mode, "rm_reserv", \
__FILE__, __LINE__, __FUNCTION__); \
&(_regexp)->regexp.reserv; }))
#define REGEXP_SEQUENCE(r) __extension__ \