Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / read-rtl.c
1 /* RTL reader for GCC.
2    Copyright (C) 1987-2015 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3.  If not see
18 <http://www.gnu.org/licenses/>.  */
19
20 #include "bconfig.h"
21
22 /* Disable rtl checking; it conflicts with the iterator handling.  */
23 #undef ENABLE_RTL_CHECKING
24
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "rtl.h"
29 #include "obstack.h"
30 #include "hashtab.h"
31 #include "read-md.h"
32 #include "gensupport.h"
33
34 /* One element in a singly-linked list of (integer, string) pairs.  */
35 struct map_value {
36   struct map_value *next;
37   int number;
38   const char *string;
39 };
40
41 /* Maps an iterator or attribute name to a list of (integer, string) pairs.
42    The integers are iterator values; the strings are either C conditions
43    or attribute values.  */
44 struct mapping {
45   /* The name of the iterator or attribute.  */
46   const char *name;
47
48   /* The group (modes or codes) to which the iterator or attribute belongs.  */
49   struct iterator_group *group;
50
51   /* The list of (integer, string) pairs.  */
52   struct map_value *values;
53
54   /* For iterators, records the current value of the iterator.  */
55   struct map_value *current_value;
56 };
57
58 /* Vector definitions for the above.  */
59 typedef struct mapping *mapping_ptr;
60
61 /* A structure for abstracting the common parts of iterators.  */
62 struct iterator_group {
63   /* Tables of "mapping" structures, one for attributes and one for
64      iterators.  */
65   htab_t attrs, iterators;
66
67   /* Treat the given string as the name of a standard mode, etc., and
68      return its integer value.  */
69   int (*find_builtin) (const char *);
70
71   /* Make the given pointer use the given iterator value.  */
72   void (*apply_iterator) (void *, int);
73 };
74
75 /* Records one use of an iterator.  */
76 struct iterator_use {
77   /* The iterator itself.  */
78   struct mapping *iterator;
79
80   /* The location of the use, as passed to the apply_iterator callback.  */
81   void *ptr;
82 };
83
84 /* Vector definitions for the above.  */
85 typedef struct iterator_use iterator_use;
86
87 /* Records one use of an attribute (the "<[iterator:]attribute>" syntax)
88    in a non-string rtx field.  */
89 struct attribute_use {
90   /* The group that describes the use site.  */
91   struct iterator_group *group;
92
93   /* The name of the attribute, possibly with an "iterator:" prefix.  */
94   const char *value;
95
96   /* The location of the use, as passed to GROUP's apply_iterator callback.  */
97   void *ptr;
98 };
99
100 /* Vector definitions for the above.  */
101 typedef struct attribute_use attribute_use;
102
103 /* This struct is used to link subst_attr named ATTR_NAME with
104    corresponding define_subst named ITER_NAME.  */
105 struct subst_attr_to_iter_mapping
106 {
107     char *attr_name;
108     char *iter_name;
109 };
110
111 /* Hash-table to store links between subst-attributes and
112    define_substs.  */
113 htab_t subst_attr_to_iter_map = NULL;
114 /* This global stores name of subst-iterator which is currently being
115    processed.  */
116 const char *current_iterator_name;
117
118 static void validate_const_int (const char *);
119 static rtx read_rtx_code (const char *);
120 static rtx read_nested_rtx (void);
121 static rtx read_rtx_variadic (rtx);
122
123 /* The mode and code iterator structures.  */
124 static struct iterator_group modes, codes, ints, substs;
125
126 /* All iterators used in the current rtx.  */
127 static vec<mapping_ptr> current_iterators;
128
129 /* The list of all iterator uses in the current rtx.  */
130 static vec<iterator_use> iterator_uses;
131
132 /* The list of all attribute uses in the current rtx.  */
133 static vec<attribute_use> attribute_uses;
134
135 /* Implementations of the iterator_group callbacks for modes.  */
136
137 static int
138 find_mode (const char *name)
139 {
140   int i;
141
142   for (i = 0; i < NUM_MACHINE_MODES; i++)
143     if (strcmp (GET_MODE_NAME (i), name) == 0)
144       return i;
145
146   fatal_with_file_and_line ("unknown mode `%s'", name);
147 }
148
149 static void
150 apply_mode_iterator (void *loc, int mode)
151 {
152   PUT_MODE ((rtx) loc, (machine_mode) mode);
153 }
154
155 /* Implementations of the iterator_group callbacks for codes.  */
156
157 static int
158 find_code (const char *name)
159 {
160   int i;
161
162   for (i = 0; i < NUM_RTX_CODE; i++)
163     if (strcmp (GET_RTX_NAME (i), name) == 0)
164       return i;
165
166   fatal_with_file_and_line ("unknown rtx code `%s'", name);
167 }
168
169 static void
170 apply_code_iterator (void *loc, int code)
171 {
172   PUT_CODE ((rtx) loc, (enum rtx_code) code);
173 }
174
175 /* Implementations of the iterator_group callbacks for ints.  */
176
177 /* Since GCC does not construct a table of valid constants,
178    we have to accept any int as valid.  No cross-checking can
179    be done.  */
180
181 static int
182 find_int (const char *name)
183 {
184   validate_const_int (name);
185   return atoi (name);
186 }
187
188 static void
189 apply_int_iterator (void *loc, int value)
190 {
191   *(int *)loc = value;
192 }
193
194 /* This routine adds attribute or does nothing depending on VALUE.  When
195    VALUE is 1, it does nothing - the first duplicate of original
196    template is kept untouched when it's subjected to a define_subst.
197    When VALUE isn't 1, the routine modifies RTL-template LOC, adding
198    attribute, named exactly as define_subst, which later will be
199    applied.  If such attribute has already been added, then no the
200    routine has no effect.  */
201 static void
202 apply_subst_iterator (void *loc, int value)
203 {
204   rtx rt = (rtx)loc;
205   rtx new_attr;
206   rtvec attrs_vec, new_attrs_vec;
207   int i;
208   if (value == 1)
209     return;
210   gcc_assert (GET_CODE (rt) == DEFINE_INSN
211               || GET_CODE (rt) == DEFINE_EXPAND);
212
213   attrs_vec = XVEC (rt, 4);
214
215   /* If we've already added attribute 'current_iterator_name', then we
216      have nothing to do now.  */
217   if (attrs_vec)
218     {
219       for (i = 0; i < GET_NUM_ELEM (attrs_vec); i++)
220         {
221           if (strcmp (XSTR (attrs_vec->elem[i], 0), current_iterator_name) == 0)
222             return;
223         }
224     }
225
226   /* Add attribute with subst name - it serves as a mark for
227      define_subst which later would be applied to this pattern.  */
228   new_attr = rtx_alloc (SET_ATTR);
229   PUT_CODE (new_attr, SET_ATTR);
230   XSTR (new_attr, 0) = xstrdup (current_iterator_name);
231   XSTR (new_attr, 1) = xstrdup ("yes");
232
233   if (!attrs_vec)
234     {
235       new_attrs_vec = rtvec_alloc (1);
236       new_attrs_vec->elem[0] = new_attr;
237     }
238   else
239     {
240       new_attrs_vec = rtvec_alloc (GET_NUM_ELEM (attrs_vec) + 1);
241       memcpy (&new_attrs_vec->elem[0], &attrs_vec->elem[0],
242               GET_NUM_ELEM (attrs_vec) * sizeof (rtx));
243       new_attrs_vec->elem[GET_NUM_ELEM (attrs_vec)] = new_attr;
244     }
245   XVEC (rt, 4) = new_attrs_vec;
246 }
247
248 /* Map subst-attribute ATTR to subst iterator ITER.  */
249
250 static void
251 bind_subst_iter_and_attr (const char *iter, const char *attr)
252 {
253   struct subst_attr_to_iter_mapping *value;
254   void **slot;
255   if (!subst_attr_to_iter_map)
256     subst_attr_to_iter_map =
257       htab_create (1, leading_string_hash, leading_string_eq_p, 0);
258   value = XNEW (struct subst_attr_to_iter_mapping);
259   value->attr_name = xstrdup (attr);
260   value->iter_name = xstrdup (iter);
261   slot = htab_find_slot (subst_attr_to_iter_map, value, INSERT);
262   *slot = value;
263 }
264
265 /* Return name of a subst-iterator, corresponding to subst-attribute ATTR.  */
266
267 static char*
268 find_subst_iter_by_attr (const char *attr)
269 {
270   char *iter_name = NULL;
271   struct subst_attr_to_iter_mapping *value;
272   value = (struct subst_attr_to_iter_mapping*)
273     htab_find (subst_attr_to_iter_map, &attr);
274   if (value)
275     iter_name = value->iter_name;
276   return iter_name;
277 }
278
279 /* Map attribute string P to its current value.  Return null if the attribute
280    isn't known.  */
281
282 static struct map_value *
283 map_attr_string (const char *p)
284 {
285   const char *attr;
286   struct mapping *iterator;
287   unsigned int i;
288   struct mapping *m;
289   struct map_value *v;
290   int iterator_name_len;
291
292   /* Peel off any "iterator:" prefix.  Set ATTR to the start of the
293      attribute name.  */
294   attr = strchr (p, ':');
295   if (attr == 0)
296     {
297       iterator_name_len = -1;
298       attr = p;
299     }
300   else
301     {
302       iterator_name_len = attr - p;
303       attr++;
304     }
305
306   FOR_EACH_VEC_ELT (current_iterators, i, iterator)
307     {
308       /* If an iterator name was specified, check that it matches.  */
309       if (iterator_name_len >= 0
310           && (strncmp (p, iterator->name, iterator_name_len) != 0
311               || iterator->name[iterator_name_len] != 0))
312         continue;
313
314       /* Find the attribute specification.  */
315       m = (struct mapping *) htab_find (iterator->group->attrs, &attr);
316       if (m)
317         {
318           /* In contrast to code/mode/int iterators, attributes of subst
319              iterators are linked to one specific subst-iterator.  So, if
320              we are dealing with subst-iterator, we should check if it's
321              the one which linked with the given attribute.  */
322           if (iterator->group == &substs)
323             {
324               char *iter_name = find_subst_iter_by_attr (attr);
325               if (strcmp (iter_name, iterator->name) != 0)
326                 continue;
327             }
328           /* Find the attribute value associated with the current
329              iterator value.  */
330           for (v = m->values; v; v = v->next)
331             if (v->number == iterator->current_value->number)
332               return v;
333         }
334     }
335   return NULL;
336 }
337
338 /* Apply the current iterator values to STRING.  Return the new string
339    if any changes were needed, otherwise return STRING itself.  */
340
341 static const char *
342 apply_iterator_to_string (const char *string)
343 {
344   char *base, *copy, *p, *start, *end;
345   struct map_value *v;
346
347   if (string == 0)
348     return string;
349
350   base = p = copy = ASTRDUP (string);
351   while ((start = strchr (p, '<')) && (end = strchr (start, '>')))
352     {
353       p = start + 1;
354
355       *end = 0;
356       v = map_attr_string (p);
357       *end = '>';
358       if (v == 0)
359         continue;
360
361       /* Add everything between the last copied byte and the '<',
362          then add in the attribute value.  */
363       obstack_grow (&string_obstack, base, start - base);
364       obstack_grow (&string_obstack, v->string, strlen (v->string));
365       base = end + 1;
366     }
367   if (base != copy)
368     {
369       obstack_grow (&string_obstack, base, strlen (base) + 1);
370       copy = XOBFINISH (&string_obstack, char *);
371       copy_md_ptr_loc (copy, string);
372       return copy;
373     }
374   return string;
375 }
376
377 /* Return a deep copy of X, substituting the current iterator
378    values into any strings.  */
379
380 static rtx
381 copy_rtx_for_iterators (rtx original)
382 {
383   const char *format_ptr, *p;
384   int i, j;
385   rtx x;
386
387   if (original == 0)
388     return original;
389
390   /* Create a shallow copy of ORIGINAL.  */
391   x = rtx_alloc (GET_CODE (original));
392   memcpy (x, original, RTX_CODE_SIZE (GET_CODE (original)));
393
394   /* Change each string and recursively change each rtx.  */
395   format_ptr = GET_RTX_FORMAT (GET_CODE (original));
396   for (i = 0; format_ptr[i] != 0; i++)
397     switch (format_ptr[i])
398       {
399       case 'T':
400         while (XTMPL (x, i) != (p = apply_iterator_to_string (XTMPL (x, i))))
401           XTMPL (x, i) = p;
402         break;
403
404       case 'S':
405       case 's':
406         while (XSTR (x, i) != (p = apply_iterator_to_string (XSTR (x, i))))
407           XSTR (x, i) = p;
408         break;
409
410       case 'e':
411         XEXP (x, i) = copy_rtx_for_iterators (XEXP (x, i));
412         break;
413
414       case 'V':
415       case 'E':
416         if (XVEC (original, i))
417           {
418             XVEC (x, i) = rtvec_alloc (XVECLEN (original, i));
419             for (j = 0; j < XVECLEN (x, i); j++)
420               XVECEXP (x, i, j)
421                 = copy_rtx_for_iterators (XVECEXP (original, i, j));
422           }
423         break;
424
425       default:
426         break;
427       }
428   return x;
429 }
430
431 /* Return a condition that must satisfy both ORIGINAL and EXTRA.  If ORIGINAL
432    has the form "&& ..." (as used in define_insn_and_splits), assume that
433    EXTRA is already satisfied.  Empty strings are treated like "true".  */
434
435 static const char *
436 add_condition_to_string (const char *original, const char *extra)
437 {
438   if (original != 0 && original[0] == '&' && original[1] == '&')
439     return original;
440   return join_c_conditions (original, extra);
441 }
442
443 /* Like add_condition, but applied to all conditions in rtx X.  */
444
445 static void
446 add_condition_to_rtx (rtx x, const char *extra)
447 {
448   switch (GET_CODE (x))
449     {
450     case DEFINE_INSN:
451     case DEFINE_EXPAND:
452     case DEFINE_SUBST:
453       XSTR (x, 2) = add_condition_to_string (XSTR (x, 2), extra);
454       break;
455
456     case DEFINE_SPLIT:
457     case DEFINE_PEEPHOLE:
458     case DEFINE_PEEPHOLE2:
459     case DEFINE_COND_EXEC:
460       XSTR (x, 1) = add_condition_to_string (XSTR (x, 1), extra);
461       break;
462
463     case DEFINE_INSN_AND_SPLIT:
464       XSTR (x, 2) = add_condition_to_string (XSTR (x, 2), extra);
465       XSTR (x, 4) = add_condition_to_string (XSTR (x, 4), extra);
466       break;
467
468     default:
469       break;
470     }
471 }
472
473 /* Apply the current iterator values to all attribute_uses.  */
474
475 static void
476 apply_attribute_uses (void)
477 {
478   struct map_value *v;
479   attribute_use *ause;
480   unsigned int i;
481
482   FOR_EACH_VEC_ELT (attribute_uses, i, ause)
483     {
484       v = map_attr_string (ause->value);
485       if (!v)
486         fatal_with_file_and_line ("unknown iterator value `%s'", ause->value);
487       ause->group->apply_iterator (ause->ptr,
488                                    ause->group->find_builtin (v->string));
489     }
490 }
491
492 /* A htab_traverse callback for iterators.  Add all used iterators
493    to current_iterators.  */
494
495 static int
496 add_current_iterators (void **slot, void *data ATTRIBUTE_UNUSED)
497 {
498   struct mapping *iterator;
499
500   iterator = (struct mapping *) *slot;
501   if (iterator->current_value)
502     current_iterators.safe_push (iterator);
503   return 1;
504 }
505
506 /* Expand all iterators in the current rtx, which is given as ORIGINAL.
507    Build a list of expanded rtxes in the EXPR_LIST pointed to by QUEUE.  */
508
509 static void
510 apply_iterators (rtx original, rtx *queue)
511 {
512   unsigned int i;
513   const char *condition;
514   iterator_use *iuse;
515   struct mapping *iterator;
516   struct map_value *v;
517   rtx x;
518
519   if (iterator_uses.is_empty ())
520     {
521       /* Raise an error if any attributes were used.  */
522       apply_attribute_uses ();
523       XEXP (*queue, 0) = original;
524       XEXP (*queue, 1) = NULL_RTX;
525       return;
526     }
527
528   /* Clear out the iterators from the previous run.  */
529   FOR_EACH_VEC_ELT (current_iterators, i, iterator)
530     iterator->current_value = NULL;
531   current_iterators.truncate (0);
532
533   /* Mark the iterators that we need this time.  */
534   FOR_EACH_VEC_ELT (iterator_uses, i, iuse)
535     iuse->iterator->current_value = iuse->iterator->values;
536
537   /* Get the list of iterators that are in use, preserving the
538      definition order within each group.  */
539   htab_traverse (modes.iterators, add_current_iterators, NULL);
540   htab_traverse (codes.iterators, add_current_iterators, NULL);
541   htab_traverse (ints.iterators, add_current_iterators, NULL);
542   htab_traverse (substs.iterators, add_current_iterators, NULL);
543   gcc_assert (!current_iterators.is_empty ());
544
545   for (;;)
546     {
547       /* Apply the current iterator values.  Accumulate a condition to
548          say when the resulting rtx can be used.  */
549       condition = "";
550       FOR_EACH_VEC_ELT (iterator_uses, i, iuse)
551         {
552           if (iuse->iterator->group == &substs)
553             continue;
554           v = iuse->iterator->current_value;
555           iuse->iterator->group->apply_iterator (iuse->ptr, v->number);
556           condition = join_c_conditions (condition, v->string);
557         }
558       apply_attribute_uses ();
559       x = copy_rtx_for_iterators (original);
560       add_condition_to_rtx (x, condition);
561
562       /* We apply subst iterator after RTL-template is copied, as during
563          subst-iterator processing, we could add an attribute to the
564          RTL-template, and we don't want to do it in the original one.  */
565       FOR_EACH_VEC_ELT (iterator_uses, i, iuse)
566         {
567           v = iuse->iterator->current_value;
568           if (iuse->iterator->group == &substs)
569             {
570               iuse->ptr = x;
571               current_iterator_name = iuse->iterator->name;
572               iuse->iterator->group->apply_iterator (iuse->ptr, v->number);
573             }
574         }
575       /* Add the new rtx to the end of the queue.  */
576       XEXP (*queue, 0) = x;
577       XEXP (*queue, 1) = NULL_RTX;
578
579       /* Lexicographically increment the iterator value sequence.
580          That is, cycle through iterator values, starting from the right,
581          and stopping when one of them doesn't wrap around.  */
582       i = current_iterators.length ();
583       for (;;)
584         {
585           if (i == 0)
586             return;
587           i--;
588           iterator = current_iterators[i];
589           iterator->current_value = iterator->current_value->next;
590           if (iterator->current_value)
591             break;
592           iterator->current_value = iterator->values;
593         }
594
595       /* At least one more rtx to go.  Allocate room for it.  */
596       XEXP (*queue, 1) = rtx_alloc (EXPR_LIST);
597       queue = &XEXP (*queue, 1);
598     }
599 }
600
601 /* Add a new "mapping" structure to hashtable TABLE.  NAME is the name
602    of the mapping and GROUP is the group to which it belongs.  */
603
604 static struct mapping *
605 add_mapping (struct iterator_group *group, htab_t table, const char *name)
606 {
607   struct mapping *m;
608   void **slot;
609
610   m = XNEW (struct mapping);
611   m->name = xstrdup (name);
612   m->group = group;
613   m->values = 0;
614   m->current_value = NULL;
615
616   slot = htab_find_slot (table, m, INSERT);
617   if (*slot != 0)
618     fatal_with_file_and_line ("`%s' already defined", name);
619
620   *slot = m;
621   return m;
622 }
623
624 /* Add the pair (NUMBER, STRING) to a list of map_value structures.
625    END_PTR points to the current null terminator for the list; return
626    a pointer the new null terminator.  */
627
628 static struct map_value **
629 add_map_value (struct map_value **end_ptr, int number, const char *string)
630 {
631   struct map_value *value;
632
633   value = XNEW (struct map_value);
634   value->next = 0;
635   value->number = number;
636   value->string = string;
637
638   *end_ptr = value;
639   return &value->next;
640 }
641
642 /* Do one-time initialization of the mode and code attributes.  */
643
644 static void
645 initialize_iterators (void)
646 {
647   struct mapping *lower, *upper;
648   struct map_value **lower_ptr, **upper_ptr;
649   char *copy, *p;
650   int i;
651
652   modes.attrs = htab_create (13, leading_string_hash, leading_string_eq_p, 0);
653   modes.iterators = htab_create (13, leading_string_hash,
654                                  leading_string_eq_p, 0);
655   modes.find_builtin = find_mode;
656   modes.apply_iterator = apply_mode_iterator;
657
658   codes.attrs = htab_create (13, leading_string_hash, leading_string_eq_p, 0);
659   codes.iterators = htab_create (13, leading_string_hash,
660                                  leading_string_eq_p, 0);
661   codes.find_builtin = find_code;
662   codes.apply_iterator = apply_code_iterator;
663
664   ints.attrs = htab_create (13, leading_string_hash, leading_string_eq_p, 0);
665   ints.iterators = htab_create (13, leading_string_hash,
666                                  leading_string_eq_p, 0);
667   ints.find_builtin = find_int;
668   ints.apply_iterator = apply_int_iterator;
669
670   substs.attrs = htab_create (13, leading_string_hash, leading_string_eq_p, 0);
671   substs.iterators = htab_create (13, leading_string_hash,
672                                  leading_string_eq_p, 0);
673   substs.find_builtin = find_int; /* We don't use it, anyway.  */
674   substs.apply_iterator = apply_subst_iterator;
675
676   lower = add_mapping (&modes, modes.attrs, "mode");
677   upper = add_mapping (&modes, modes.attrs, "MODE");
678   lower_ptr = &lower->values;
679   upper_ptr = &upper->values;
680   for (i = 0; i < MAX_MACHINE_MODE; i++)
681     {
682       copy = xstrdup (GET_MODE_NAME (i));
683       for (p = copy; *p != 0; p++)
684         *p = TOLOWER (*p);
685
686       upper_ptr = add_map_value (upper_ptr, i, GET_MODE_NAME (i));
687       lower_ptr = add_map_value (lower_ptr, i, copy);
688     }
689
690   lower = add_mapping (&codes, codes.attrs, "code");
691   upper = add_mapping (&codes, codes.attrs, "CODE");
692   lower_ptr = &lower->values;
693   upper_ptr = &upper->values;
694   for (i = 0; i < NUM_RTX_CODE; i++)
695     {
696       copy = xstrdup (GET_RTX_NAME (i));
697       for (p = copy; *p != 0; p++)
698         *p = TOUPPER (*p);
699
700       lower_ptr = add_map_value (lower_ptr, i, GET_RTX_NAME (i));
701       upper_ptr = add_map_value (upper_ptr, i, copy);
702     }
703 }
704 \f
705 /* Provide a version of a function to read a long long if the system does
706    not provide one.  */
707 #if HOST_BITS_PER_WIDE_INT > HOST_BITS_PER_LONG && !defined(HAVE_ATOLL) && !defined(HAVE_ATOQ)
708 HOST_WIDE_INT atoll (const char *);
709
710 HOST_WIDE_INT
711 atoll (const char *p)
712 {
713   int neg = 0;
714   HOST_WIDE_INT tmp_wide;
715
716   while (ISSPACE (*p))
717     p++;
718   if (*p == '-')
719     neg = 1, p++;
720   else if (*p == '+')
721     p++;
722
723   tmp_wide = 0;
724   while (ISDIGIT (*p))
725     {
726       HOST_WIDE_INT new_wide = tmp_wide*10 + (*p - '0');
727       if (new_wide < tmp_wide)
728         {
729           /* Return INT_MAX equiv on overflow.  */
730           tmp_wide = (~(unsigned HOST_WIDE_INT) 0) >> 1;
731           break;
732         }
733       tmp_wide = new_wide;
734       p++;
735     }
736
737   if (neg)
738     tmp_wide = -tmp_wide;
739   return tmp_wide;
740 }
741 #endif
742 \f
743 /* Process a define_conditions directive, starting with the optional
744    space after the "define_conditions".  The directive looks like this:
745
746      (define_conditions [
747         (number "string")
748         (number "string")
749         ...
750      ])
751
752    It's not intended to appear in machine descriptions.  It is
753    generated by (the program generated by) genconditions.c, and
754    slipped in at the beginning of the sequence of MD files read by
755    most of the other generators.  */
756 static void
757 read_conditions (void)
758 {
759   int c;
760
761   c = read_skip_spaces ();
762   if (c != '[')
763     fatal_expected_char ('[', c);
764
765   while ( (c = read_skip_spaces ()) != ']')
766     {
767       struct md_name name;
768       char *expr;
769       int value;
770
771       if (c != '(')
772         fatal_expected_char ('(', c);
773
774       read_name (&name);
775       validate_const_int (name.string);
776       value = atoi (name.string);
777
778       c = read_skip_spaces ();
779       if (c != '"')
780         fatal_expected_char ('"', c);
781       expr = read_quoted_string ();
782
783       c = read_skip_spaces ();
784       if (c != ')')
785         fatal_expected_char (')', c);
786
787       add_c_test (expr, value);
788     }
789 }
790
791 static void
792 validate_const_int (const char *string)
793 {
794   const char *cp;
795   int valid = 1;
796
797   cp = string;
798   while (*cp && ISSPACE (*cp))
799     cp++;
800   if (*cp == '-' || *cp == '+')
801     cp++;
802   if (*cp == 0)
803     valid = 0;
804   for (; *cp; cp++)
805     if (! ISDIGIT (*cp))
806       {
807         valid = 0;
808         break;
809       }
810   if (!valid)
811     fatal_with_file_and_line ("invalid decimal constant \"%s\"\n", string);
812 }
813
814 static void
815 validate_const_wide_int (const char *string)
816 {
817   const char *cp;
818   int valid = 1;
819
820   cp = string;
821   while (*cp && ISSPACE (*cp))
822     cp++;
823   /* Skip the leading 0x.  */
824   if (cp[0] == '0' || cp[1] == 'x')
825     cp += 2;
826   else
827     valid = 0;
828   if (*cp == 0)
829     valid = 0;
830   for (; *cp; cp++)
831     if (! ISXDIGIT (*cp))
832       valid = 0;
833   if (!valid)
834     fatal_with_file_and_line ("invalid hex constant \"%s\"\n", string);
835 }
836
837 /* Record that PTR uses iterator ITERATOR.  */
838
839 static void
840 record_iterator_use (struct mapping *iterator, void *ptr)
841 {
842   struct iterator_use iuse = {iterator, ptr};
843   iterator_uses.safe_push (iuse);
844 }
845
846 /* Record that PTR uses attribute VALUE, which must match a built-in
847    value from group GROUP.  */
848
849 static void
850 record_attribute_use (struct iterator_group *group, void *ptr,
851                       const char *value)
852 {
853   struct attribute_use ause = {group, value, ptr};
854   attribute_uses.safe_push (ause);
855 }
856
857 /* Interpret NAME as either a built-in value, iterator or attribute
858    for group GROUP.  PTR is the value to pass to GROUP's apply_iterator
859    callback.  */
860
861 static void
862 record_potential_iterator_use (struct iterator_group *group, void *ptr,
863                                const char *name)
864 {
865   struct mapping *m;
866   size_t len;
867
868   len = strlen (name);
869   if (name[0] == '<' && name[len - 1] == '>')
870     {
871       /* Copy the attribute string into permanent storage, without the
872          angle brackets around it.  */
873       obstack_grow0 (&string_obstack, name + 1, len - 2);
874       record_attribute_use (group, ptr, XOBFINISH (&string_obstack, char *));
875     }
876   else
877     {
878       m = (struct mapping *) htab_find (group->iterators, &name);
879       if (m != 0)
880         record_iterator_use (m, ptr);
881       else
882         group->apply_iterator (ptr, group->find_builtin (name));
883     }
884 }
885
886 /* Finish reading a declaration of the form:
887
888        (define... <name> [<value1> ... <valuen>])
889
890    from the MD file, where each <valuei> is either a bare symbol name or a
891    "(<name> <string>)" pair.  The "(define..." part has already been read.
892
893    Represent the declaration as a "mapping" structure; add it to TABLE
894    (which belongs to GROUP) and return it.  */
895
896 static struct mapping *
897 read_mapping (struct iterator_group *group, htab_t table)
898 {
899   struct md_name name;
900   struct mapping *m;
901   struct map_value **end_ptr;
902   const char *string;
903   int number, c;
904
905   /* Read the mapping name and create a structure for it.  */
906   read_name (&name);
907   m = add_mapping (group, table, name.string);
908
909   c = read_skip_spaces ();
910   if (c != '[')
911     fatal_expected_char ('[', c);
912
913   /* Read each value.  */
914   end_ptr = &m->values;
915   c = read_skip_spaces ();
916   do
917     {
918       if (c != '(')
919         {
920           /* A bare symbol name that is implicitly paired to an
921              empty string.  */
922           unread_char (c);
923           read_name (&name);
924           string = "";
925         }
926       else
927         {
928           /* A "(name string)" pair.  */
929           read_name (&name);
930           string = read_string (false);
931           c = read_skip_spaces ();
932           if (c != ')')
933             fatal_expected_char (')', c);
934         }
935       number = group->find_builtin (name.string);
936       end_ptr = add_map_value (end_ptr, number, string);
937       c = read_skip_spaces ();
938     }
939   while (c != ']');
940
941   return m;
942 }
943
944 /* For iterator with name ATTR_NAME generate define_attr with values
945    'yes' and 'no'.  This attribute is used to mark templates to which
946    define_subst ATTR_NAME should be applied.  This attribute is set and
947    defined implicitly and automatically.  */
948 static void
949 add_define_attr_for_define_subst (const char *attr_name, rtx *queue)
950 {
951   rtx const_str, return_rtx;
952
953   return_rtx = rtx_alloc (DEFINE_ATTR);
954   PUT_CODE (return_rtx, DEFINE_ATTR);
955
956   const_str = rtx_alloc (CONST_STRING);
957   PUT_CODE (const_str, CONST_STRING);
958   XSTR (const_str, 0) = xstrdup ("no");
959
960   XSTR (return_rtx, 0) = xstrdup (attr_name);
961   XSTR (return_rtx, 1) = xstrdup ("no,yes");
962   XEXP (return_rtx, 2) = const_str;
963
964   XEXP (*queue, 0) = return_rtx;
965   XEXP (*queue, 1) = NULL_RTX;
966 }
967
968 /* This routine generates DEFINE_SUBST_ATTR expression with operands
969    ATTR_OPERANDS and places it to QUEUE.  */
970 static void
971 add_define_subst_attr (const char **attr_operands, rtx *queue)
972 {
973   rtx return_rtx;
974   int i;
975
976   return_rtx = rtx_alloc (DEFINE_SUBST_ATTR);
977   PUT_CODE (return_rtx, DEFINE_SUBST_ATTR);
978
979   for (i = 0; i < 4; i++)
980     XSTR (return_rtx, i) = xstrdup (attr_operands[i]);
981
982   XEXP (*queue, 0) = return_rtx;
983   XEXP (*queue, 1) = NULL_RTX;
984 }
985
986 /* Read define_subst_attribute construction.  It has next form:
987         (define_subst_attribute <attribute_name> <iterator_name> <value1> <value2>)
988    Attribute is substituted with value1 when no subst is applied and with
989    value2 in the opposite case.
990    Attributes are added to SUBST_ATTRS_TABLE.
991    In case the iterator is encountered for the first time, it's added to
992    SUBST_ITERS_TABLE.  Also, implicit define_attr is generated.  */
993
994 static void
995 read_subst_mapping (htab_t subst_iters_table, htab_t subst_attrs_table,
996                     rtx *queue)
997 {
998   struct mapping *m;
999   struct map_value **end_ptr;
1000   const char *attr_operands[4];
1001   rtx * queue_elem = queue;
1002   int i;
1003
1004   for (i = 0; i < 4; i++)
1005     attr_operands[i] = read_string (false);
1006
1007   add_define_subst_attr (attr_operands, queue_elem);
1008
1009   bind_subst_iter_and_attr (attr_operands[1], attr_operands[0]);
1010
1011   m = (struct mapping *) htab_find (substs.iterators, &attr_operands[1]);
1012   if (!m)
1013     {
1014       m = add_mapping (&substs, subst_iters_table, attr_operands[1]);
1015       end_ptr = &m->values;
1016       end_ptr = add_map_value (end_ptr, 1, "");
1017       end_ptr = add_map_value (end_ptr, 2, "");
1018
1019       /* Add element to the queue.  */
1020       XEXP (*queue, 1) = rtx_alloc (EXPR_LIST);
1021       queue_elem = &XEXP (*queue, 1);
1022
1023       add_define_attr_for_define_subst (attr_operands[1], queue_elem);
1024     }
1025
1026   m = add_mapping (&substs, subst_attrs_table, attr_operands[0]);
1027   end_ptr = &m->values;
1028   end_ptr = add_map_value (end_ptr, 1, attr_operands[2]);
1029   end_ptr = add_map_value (end_ptr, 2, attr_operands[3]);
1030 }
1031
1032 /* Check newly-created code iterator ITERATOR to see whether every code has the
1033    same format.  */
1034
1035 static void
1036 check_code_iterator (struct mapping *iterator)
1037 {
1038   struct map_value *v;
1039   enum rtx_code bellwether;
1040
1041   bellwether = (enum rtx_code) iterator->values->number;
1042   for (v = iterator->values->next; v != 0; v = v->next)
1043     if (strcmp (GET_RTX_FORMAT (bellwether), GET_RTX_FORMAT (v->number)) != 0)
1044       fatal_with_file_and_line ("code iterator `%s' combines "
1045                                 "different rtx formats", iterator->name);
1046 }
1047
1048 /* Read an rtx-related declaration from the MD file, given that it
1049    starts with directive name RTX_NAME.  Return true if it expands to
1050    one or more rtxes (as defined by rtx.def).  When returning true,
1051    store the list of rtxes as an EXPR_LIST in *X.  */
1052
1053 bool
1054 read_rtx (const char *rtx_name, rtx *x)
1055 {
1056   static rtx queue_head;
1057
1058   /* Do one-time initialization.  */
1059   if (queue_head == 0)
1060     {
1061       initialize_iterators ();
1062       queue_head = rtx_alloc (EXPR_LIST);
1063     }
1064
1065   /* Handle various rtx-related declarations that aren't themselves
1066      encoded as rtxes.  */
1067   if (strcmp (rtx_name, "define_conditions") == 0)
1068     {
1069       read_conditions ();
1070       return false;
1071     }
1072   if (strcmp (rtx_name, "define_mode_attr") == 0)
1073     {
1074       read_mapping (&modes, modes.attrs);
1075       return false;
1076     }
1077   if (strcmp (rtx_name, "define_mode_iterator") == 0)
1078     {
1079       read_mapping (&modes, modes.iterators);
1080       return false;
1081     }
1082   if (strcmp (rtx_name, "define_code_attr") == 0)
1083     {
1084       read_mapping (&codes, codes.attrs);
1085       return false;
1086     }
1087   if (strcmp (rtx_name, "define_code_iterator") == 0)
1088     {
1089       check_code_iterator (read_mapping (&codes, codes.iterators));
1090       return false;
1091     }
1092   if (strcmp (rtx_name, "define_int_attr") == 0)
1093     {
1094       read_mapping (&ints, ints.attrs);
1095       return false;
1096     }
1097   if (strcmp (rtx_name, "define_int_iterator") == 0)
1098     {
1099       read_mapping (&ints, ints.iterators);
1100       return false;
1101     }
1102   if (strcmp (rtx_name, "define_subst_attr") == 0)
1103     {
1104       read_subst_mapping (substs.iterators, substs.attrs, &queue_head);
1105       *x = queue_head;
1106
1107       /* READ_SUBST_MAPPING could generate a new DEFINE_ATTR.  Return
1108          TRUE to process it.  */
1109       return true;
1110     }
1111
1112   apply_iterators (read_rtx_code (rtx_name), &queue_head);
1113   iterator_uses.truncate (0);
1114   attribute_uses.truncate (0);
1115
1116   *x = queue_head;
1117   return true;
1118 }
1119
1120 /* Subroutine of read_rtx and read_nested_rtx.  CODE_NAME is the name of
1121    either an rtx code or a code iterator.  Parse the rest of the rtx and
1122    return it.  */
1123
1124 static rtx
1125 read_rtx_code (const char *code_name)
1126 {
1127   int i;
1128   RTX_CODE code;
1129   struct mapping *iterator, *m;
1130   const char *format_ptr;
1131   struct md_name name;
1132   rtx return_rtx;
1133   int c;
1134   HOST_WIDE_INT tmp_wide;
1135   char *str;
1136   char *start, *end, *ptr;
1137   char tmpstr[256];
1138
1139   /* Linked list structure for making RTXs: */
1140   struct rtx_list
1141     {
1142       struct rtx_list *next;
1143       rtx value;                /* Value of this node.  */
1144     };
1145
1146   /* If this code is an iterator, build the rtx using the iterator's
1147      first value.  */
1148   iterator = (struct mapping *) htab_find (codes.iterators, &code_name);
1149   if (iterator != 0)
1150     code = (enum rtx_code) iterator->values->number;
1151   else
1152     code = (enum rtx_code) codes.find_builtin (code_name);
1153
1154   /* If we end up with an insn expression then we free this space below.  */
1155   return_rtx = rtx_alloc (code);
1156   format_ptr = GET_RTX_FORMAT (code);
1157   memset (return_rtx, 0, RTX_CODE_SIZE (code));
1158   PUT_CODE (return_rtx, code);
1159
1160   if (iterator)
1161     record_iterator_use (iterator, return_rtx);
1162
1163   /* If what follows is `: mode ', read it and
1164      store the mode in the rtx.  */
1165
1166   i = read_skip_spaces ();
1167   if (i == ':')
1168     {
1169       read_name (&name);
1170       record_potential_iterator_use (&modes, return_rtx, name.string);
1171     }
1172   else
1173     unread_char (i);
1174
1175   for (i = 0; format_ptr[i] != 0; i++)
1176     switch (format_ptr[i])
1177       {
1178         /* 0 means a field for internal use only.
1179            Don't expect it to be present in the input.  */
1180       case '0':
1181         if (code == REG)
1182           ORIGINAL_REGNO (return_rtx) = REGNO (return_rtx);
1183         break;
1184
1185       case 'e':
1186       case 'u':
1187         XEXP (return_rtx, i) = read_nested_rtx ();
1188         break;
1189
1190       case 'V':
1191         /* 'V' is an optional vector: if a closeparen follows,
1192            just store NULL for this element.  */
1193         c = read_skip_spaces ();
1194         unread_char (c);
1195         if (c == ')')
1196           {
1197             XVEC (return_rtx, i) = 0;
1198             break;
1199           }
1200         /* Now process the vector.  */
1201
1202       case 'E':
1203         {
1204           /* Obstack to store scratch vector in.  */
1205           struct obstack vector_stack;
1206           int list_counter = 0;
1207           rtvec return_vec = NULL_RTVEC;
1208
1209           c = read_skip_spaces ();
1210           if (c != '[')
1211             fatal_expected_char ('[', c);
1212
1213           /* Add expressions to a list, while keeping a count.  */
1214           obstack_init (&vector_stack);
1215           while ((c = read_skip_spaces ()) && c != ']')
1216             {
1217               if (c == EOF)
1218                 fatal_expected_char (']', c);
1219               unread_char (c);
1220               list_counter++;
1221               obstack_ptr_grow (&vector_stack, read_nested_rtx ());
1222             }
1223           if (list_counter > 0)
1224             {
1225               return_vec = rtvec_alloc (list_counter);
1226               memcpy (&return_vec->elem[0], obstack_finish (&vector_stack),
1227                       list_counter * sizeof (rtx));
1228             }
1229           else if (format_ptr[i] == 'E')
1230             fatal_with_file_and_line ("vector must have at least one element");
1231           XVEC (return_rtx, i) = return_vec;
1232           obstack_free (&vector_stack, NULL);
1233           /* close bracket gotten */
1234         }
1235         break;
1236
1237       case 'S':
1238       case 'T':
1239       case 's':
1240         {
1241           char *stringbuf;
1242           int star_if_braced;
1243
1244           c = read_skip_spaces ();
1245           unread_char (c);
1246           if (c == ')')
1247             {
1248               /* 'S' fields are optional and should be NULL if no string
1249                  was given.  Also allow normal 's' and 'T' strings to be
1250                  omitted, treating them in the same way as empty strings.  */
1251               XSTR (return_rtx, i) = (format_ptr[i] == 'S' ? NULL : "");
1252               break;
1253             }
1254
1255           /* The output template slot of a DEFINE_INSN,
1256              DEFINE_INSN_AND_SPLIT, or DEFINE_PEEPHOLE automatically
1257              gets a star inserted as its first character, if it is
1258              written with a brace block instead of a string constant.  */
1259           star_if_braced = (format_ptr[i] == 'T');
1260
1261           stringbuf = read_string (star_if_braced);
1262
1263           /* For insn patterns, we want to provide a default name
1264              based on the file and line, like "*foo.md:12", if the
1265              given name is blank.  These are only for define_insn and
1266              define_insn_and_split, to aid debugging.  */
1267           if (*stringbuf == '\0'
1268               && i == 0
1269               && (GET_CODE (return_rtx) == DEFINE_INSN
1270                   || GET_CODE (return_rtx) == DEFINE_INSN_AND_SPLIT))
1271             {
1272               char line_name[20];
1273               const char *fn = (read_md_filename ? read_md_filename : "rtx");
1274               const char *slash;
1275               for (slash = fn; *slash; slash ++)
1276                 if (*slash == '/' || *slash == '\\' || *slash == ':')
1277                   fn = slash + 1;
1278               obstack_1grow (&string_obstack, '*');
1279               obstack_grow (&string_obstack, fn, strlen (fn));
1280               sprintf (line_name, ":%d", read_md_lineno);
1281               obstack_grow (&string_obstack, line_name, strlen (line_name)+1);
1282               stringbuf = XOBFINISH (&string_obstack, char *);
1283             }
1284
1285           /* Find attr-names in the string.  */
1286           ptr = &tmpstr[0];
1287           end = stringbuf;
1288           while ((start = strchr (end, '<')) && (end  = strchr (start, '>')))
1289             {
1290               if ((end - start - 1 > 0)
1291                   && (end - start - 1 < (int)sizeof (tmpstr)))
1292                 {
1293                   strncpy (tmpstr, start+1, end-start-1);
1294                   tmpstr[end-start-1] = 0;
1295                   end++;
1296                 }
1297               else
1298                 break;
1299               m = (struct mapping *) htab_find (substs.attrs, &ptr);
1300               if (m != 0)
1301                 {
1302                   /* Here we should find linked subst-iter.  */
1303                   str = find_subst_iter_by_attr (ptr);
1304                   if (str)
1305                     m = (struct mapping *) htab_find (substs.iterators, &str);
1306                   else
1307                     m = 0;
1308                 }
1309               if (m != 0)
1310                 record_iterator_use (m, return_rtx);
1311             }
1312
1313           if (star_if_braced)
1314             XTMPL (return_rtx, i) = stringbuf;
1315           else
1316             XSTR (return_rtx, i) = stringbuf;
1317         }
1318         break;
1319
1320       case 'w':
1321         read_name (&name);
1322         validate_const_int (name.string);
1323 #if HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_INT
1324         tmp_wide = atoi (name.string);
1325 #else
1326 #if HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_LONG
1327         tmp_wide = atol (name.string);
1328 #else
1329         /* Prefer atoll over atoq, since the former is in the ISO C99 standard.
1330            But prefer not to use our hand-rolled function above either.  */
1331 #if defined(HAVE_ATOLL) || !defined(HAVE_ATOQ)
1332         tmp_wide = atoll (name.string);
1333 #else
1334         tmp_wide = atoq (name.string);
1335 #endif
1336 #endif
1337 #endif
1338         XWINT (return_rtx, i) = tmp_wide;
1339         break;
1340
1341       case 'i':
1342       case 'n':
1343         /* Can be an iterator or an integer constant.  */
1344         read_name (&name);
1345         record_potential_iterator_use (&ints, &XINT (return_rtx, i),
1346                                        name.string);
1347         break;
1348
1349       default:
1350         gcc_unreachable ();
1351       }
1352
1353   if (CONST_WIDE_INT_P (return_rtx))
1354     {
1355       read_name (&name);
1356       validate_const_wide_int (name.string);
1357       {
1358         const char *s = name.string;
1359         int len;
1360         int index = 0;
1361         int gs = HOST_BITS_PER_WIDE_INT/4;
1362         int pos;
1363         char * buf = XALLOCAVEC (char, gs + 1);
1364         unsigned HOST_WIDE_INT wi;
1365         int wlen;
1366
1367         /* Skip the leading spaces.  */
1368         while (*s && ISSPACE (*s))
1369           s++;
1370
1371         /* Skip the leading 0x.  */
1372         gcc_assert (s[0] == '0');
1373         gcc_assert (s[1] == 'x');
1374         s += 2;
1375
1376         len = strlen (s);
1377         pos = len - gs;
1378         wlen = (len + gs - 1) / gs;     /* Number of words needed */
1379
1380         return_rtx = const_wide_int_alloc (wlen);
1381
1382         while (pos > 0)
1383           {
1384 #if HOST_BITS_PER_WIDE_INT == 64
1385             sscanf (s + pos, "%16" HOST_WIDE_INT_PRINT "x", &wi);
1386 #else
1387             sscanf (s + pos, "%8" HOST_WIDE_INT_PRINT "x", &wi);
1388 #endif
1389             CWI_ELT (return_rtx, index++) = wi;
1390             pos -= gs;
1391           }
1392         strncpy (buf, s, gs - pos);
1393         buf [gs - pos] = 0;
1394         sscanf (buf, "%" HOST_WIDE_INT_PRINT "x", &wi);
1395         CWI_ELT (return_rtx, index++) = wi;
1396         /* TODO: After reading, do we want to canonicalize with:
1397            value = lookup_const_wide_int (value); ? */
1398       }
1399     }
1400
1401   c = read_skip_spaces ();
1402   /* Syntactic sugar for AND and IOR, allowing Lisp-like
1403      arbitrary number of arguments for them.  */
1404   if (c == '('
1405       && (GET_CODE (return_rtx) == AND
1406           || GET_CODE (return_rtx) == IOR))
1407     return read_rtx_variadic (return_rtx);
1408
1409   unread_char (c);
1410   return return_rtx;
1411 }
1412
1413 /* Read a nested rtx construct from the MD file and return it.  */
1414
1415 static rtx
1416 read_nested_rtx (void)
1417 {
1418   struct md_name name;
1419   int c;
1420   rtx return_rtx;
1421
1422   c = read_skip_spaces ();
1423   if (c != '(')
1424     fatal_expected_char ('(', c);
1425
1426   read_name (&name);
1427   if (strcmp (name.string, "nil") == 0)
1428     return_rtx = NULL;
1429   else
1430     return_rtx = read_rtx_code (name.string);
1431
1432   c = read_skip_spaces ();
1433   if (c != ')')
1434     fatal_expected_char (')', c);
1435
1436   return return_rtx;
1437 }
1438
1439 /* Mutually recursive subroutine of read_rtx which reads
1440    (thing x1 x2 x3 ...) and produces RTL as if
1441    (thing x1 (thing x2 (thing x3 ...)))  had been written.
1442    When called, FORM is (thing x1 x2), and the file position
1443    is just past the leading parenthesis of x3.  Only works
1444    for THINGs which are dyadic expressions, e.g. AND, IOR.  */
1445 static rtx
1446 read_rtx_variadic (rtx form)
1447 {
1448   char c = '(';
1449   rtx p = form, q;
1450
1451   do
1452     {
1453       unread_char (c);
1454
1455       q = rtx_alloc (GET_CODE (p));
1456       PUT_MODE (q, GET_MODE (p));
1457
1458       XEXP (q, 0) = XEXP (p, 1);
1459       XEXP (q, 1) = read_nested_rtx ();
1460
1461       XEXP (p, 1) = q;
1462       p = q;
1463       c = read_skip_spaces ();
1464     }
1465   while (c == '(');
1466   unread_char (c);
1467   return form;
1468 }