OSDN Git Service

f4e052c4c6a7bce50ee451aa6099878e052d186f
[pf3gnuchains/gcc-fork.git] / gcc / tree.c
1 /* Language-independent node constructors for parse phase of GNU compiler.
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 /* This file contains the low level primitives for operating on tree nodes,
23    including allocation, list operations, interning of identifiers,
24    construction of data type nodes and statement nodes,
25    and construction of type conversion nodes.  It also contains
26    tables index by tree code that describe how to take apart
27    nodes of that code.
28
29    It is intended to be language-independent, but occasionally
30    calls language-dependent routines defined (for C) in typecheck.c.  */
31
32 #include "config.h"
33 #include "system.h"
34 #include "coretypes.h"
35 #include "tm.h"
36 #include "flags.h"
37 #include "tree.h"
38 #include "real.h"
39 #include "tm_p.h"
40 #include "function.h"
41 #include "obstack.h"
42 #include "toplev.h"
43 #include "ggc.h"
44 #include "hashtab.h"
45 #include "output.h"
46 #include "target.h"
47 #include "langhooks.h"
48 #include "tree-iterator.h"
49 #include "basic-block.h"
50 #include "tree-flow.h"
51 #include "params.h"
52 #include "pointer-set.h"
53
54 /* Each tree code class has an associated string representation.
55    These must correspond to the tree_code_class entries.  */
56
57 const char *const tree_code_class_strings[] =
58 {
59   "exceptional",
60   "constant",
61   "type",
62   "declaration",
63   "reference",
64   "comparison",
65   "unary",
66   "binary",
67   "statement",
68   "expression",
69 };
70
71 /* obstack.[ch] explicitly declined to prototype this.  */
72 extern int _obstack_allocated_p (struct obstack *h, void *obj);
73
74 #ifdef GATHER_STATISTICS
75 /* Statistics-gathering stuff.  */
76
77 int tree_node_counts[(int) all_kinds];
78 int tree_node_sizes[(int) all_kinds];
79
80 /* Keep in sync with tree.h:enum tree_node_kind.  */
81 static const char * const tree_node_kind_names[] = {
82   "decls",
83   "types",
84   "blocks",
85   "stmts",
86   "refs",
87   "exprs",
88   "constants",
89   "identifiers",
90   "perm_tree_lists",
91   "temp_tree_lists",
92   "vecs",
93   "binfos",
94   "phi_nodes",
95   "ssa names",
96   "random kinds",
97   "lang_decl kinds",
98   "lang_type kinds"
99 };
100 #endif /* GATHER_STATISTICS */
101
102 /* Unique id for next decl created.  */
103 static GTY(()) int next_decl_uid;
104 /* Unique id for next type created.  */
105 static GTY(()) int next_type_uid = 1;
106
107 /* Since we cannot rehash a type after it is in the table, we have to
108    keep the hash code.  */
109
110 struct type_hash GTY(())
111 {
112   unsigned long hash;
113   tree type;
114 };
115
116 /* Initial size of the hash table (rounded to next prime).  */
117 #define TYPE_HASH_INITIAL_SIZE 1000
118
119 /* Now here is the hash table.  When recording a type, it is added to
120    the slot whose index is the hash code.  Note that the hash table is
121    used for several kinds of types (function types, array types and
122    array index range types, for now).  While all these live in the
123    same table, they are completely independent, and the hash code is
124    computed differently for each of these.  */
125
126 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
127      htab_t type_hash_table;
128
129 /* Hash table and temporary node for larger integer const values.  */
130 static GTY (()) tree int_cst_node;
131 static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
132      htab_t int_cst_hash_table;
133
134 /* General tree->tree mapping  structure for use in hash tables.  */
135
136 struct tree_map GTY(())
137 {
138   hashval_t hash;
139   tree from;
140   tree to;
141 };
142
143 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) 
144      htab_t debug_expr_for_decl;
145
146 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) 
147      htab_t value_expr_for_decl;
148
149 static void set_type_quals (tree, int);
150 static int type_hash_eq (const void *, const void *);
151 static hashval_t type_hash_hash (const void *);
152 static int tree_map_eq (const void *, const void *);
153 static hashval_t tree_map_hash (const void *);
154 static hashval_t int_cst_hash_hash (const void *);
155 static int int_cst_hash_eq (const void *, const void *);
156 static void print_type_hash_statistics (void);
157 static void print_debug_expr_statistics (void);
158 static void print_value_expr_statistics (void);
159 static tree make_vector_type (tree, int, enum machine_mode);
160 static int type_hash_marked_p (const void *);
161 static int tree_map_marked_p (const void *);
162 static unsigned int type_hash_list (tree, hashval_t);
163 static unsigned int attribute_hash_list (tree, hashval_t);
164
165 tree global_trees[TI_MAX];
166 tree integer_types[itk_none];
167
168 \f
169 /* Init tree.c.  */
170
171 void
172 init_ttree (void)
173 {
174   /* Initialize the hash table of types.  */
175   type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
176                                      type_hash_eq, 0);
177
178   debug_expr_for_decl = htab_create_ggc (512, tree_map_hash,
179                                          tree_map_eq, 0);
180
181   value_expr_for_decl = htab_create_ggc (512, tree_map_hash,
182                                          tree_map_eq, 0);
183
184   int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash,
185                                         int_cst_hash_eq, NULL);
186   
187   int_cst_node = make_node (INTEGER_CST);
188
189 }
190
191 \f
192 /* The name of the object as the assembler will see it (but before any
193    translations made by ASM_OUTPUT_LABELREF).  Often this is the same
194    as DECL_NAME.  It is an IDENTIFIER_NODE.  */
195 tree
196 decl_assembler_name (tree decl)
197 {
198   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
199     lang_hooks.set_decl_assembler_name (decl);
200   return DECL_CHECK (decl)->decl.assembler_name;
201 }
202
203 /* Compute the number of bytes occupied by a tree with code CODE.
204    This function cannot be used for TREE_VEC, PHI_NODE, or STRING_CST
205    codes, which are of variable length.  */
206 size_t
207 tree_code_size (enum tree_code code)
208 {
209   switch (TREE_CODE_CLASS (code))
210     {
211     case tcc_declaration:  /* A decl node */
212       return sizeof (struct tree_decl);
213
214     case tcc_type:  /* a type node */
215       return sizeof (struct tree_type);
216
217     case tcc_reference:   /* a reference */
218     case tcc_expression:  /* an expression */
219     case tcc_statement:   /* an expression with side effects */
220     case tcc_comparison:  /* a comparison expression */
221     case tcc_unary:       /* a unary arithmetic expression */
222     case tcc_binary:      /* a binary arithmetic expression */
223       return (sizeof (struct tree_exp)
224               + (TREE_CODE_LENGTH (code) - 1) * sizeof (char *));
225
226     case tcc_constant:  /* a constant */
227       switch (code)
228         {
229         case INTEGER_CST:       return sizeof (struct tree_int_cst);
230         case REAL_CST:          return sizeof (struct tree_real_cst);
231         case COMPLEX_CST:       return sizeof (struct tree_complex);
232         case VECTOR_CST:        return sizeof (struct tree_vector);
233         case STRING_CST:        gcc_unreachable ();
234         default:
235           return lang_hooks.tree_size (code);
236         }
237
238     case tcc_exceptional:  /* something random, like an identifier.  */
239       switch (code)
240         {
241         case IDENTIFIER_NODE:   return lang_hooks.identifier_size;
242         case TREE_LIST:         return sizeof (struct tree_list);
243
244         case ERROR_MARK:
245         case PLACEHOLDER_EXPR:  return sizeof (struct tree_common);
246
247         case TREE_VEC:
248         case PHI_NODE:          gcc_unreachable ();
249
250         case SSA_NAME:          return sizeof (struct tree_ssa_name);
251
252         case STATEMENT_LIST:    return sizeof (struct tree_statement_list);
253         case BLOCK:             return sizeof (struct tree_block);
254         case VALUE_HANDLE:      return sizeof (struct tree_value_handle);
255
256         default:
257           return lang_hooks.tree_size (code);
258         }
259
260     default:
261       gcc_unreachable ();
262     }
263 }
264
265 /* Compute the number of bytes occupied by NODE.  This routine only
266    looks at TREE_CODE, except for PHI_NODE and TREE_VEC nodes.  */
267 size_t
268 tree_size (tree node)
269 {
270   enum tree_code code = TREE_CODE (node);
271   switch (code)
272     {
273     case PHI_NODE:
274       return (sizeof (struct tree_phi_node)
275               + (PHI_ARG_CAPACITY (node) - 1) * sizeof (struct phi_arg_d));
276
277     case TREE_BINFO:
278       return (offsetof (struct tree_binfo, base_binfos)
279               + VEC_embedded_size (tree, BINFO_N_BASE_BINFOS (node)));
280
281     case TREE_VEC:
282       return (sizeof (struct tree_vec)
283               + (TREE_VEC_LENGTH (node) - 1) * sizeof(char *));
284
285     case STRING_CST:
286       return sizeof (struct tree_string) + TREE_STRING_LENGTH (node) - 1;
287
288     default:
289       return tree_code_size (code);
290     }
291 }
292
293 /* Return a newly allocated node of code CODE.  For decl and type
294    nodes, some other fields are initialized.  The rest of the node is
295    initialized to zero.  This function cannot be used for PHI_NODE or
296    TREE_VEC nodes, which is enforced by asserts in tree_code_size.
297
298    Achoo!  I got a code in the node.  */
299
300 tree
301 make_node_stat (enum tree_code code MEM_STAT_DECL)
302 {
303   tree t;
304   enum tree_code_class type = TREE_CODE_CLASS (code);
305   size_t length = tree_code_size (code);
306 #ifdef GATHER_STATISTICS
307   tree_node_kind kind;
308
309   switch (type)
310     {
311     case tcc_declaration:  /* A decl node */
312       kind = d_kind;
313       break;
314
315     case tcc_type:  /* a type node */
316       kind = t_kind;
317       break;
318
319     case tcc_statement:  /* an expression with side effects */
320       kind = s_kind;
321       break;
322
323     case tcc_reference:  /* a reference */
324       kind = r_kind;
325       break;
326
327     case tcc_expression:  /* an expression */
328     case tcc_comparison:  /* a comparison expression */
329     case tcc_unary:  /* a unary arithmetic expression */
330     case tcc_binary:  /* a binary arithmetic expression */
331       kind = e_kind;
332       break;
333
334     case tcc_constant:  /* a constant */
335       kind = c_kind;
336       break;
337
338     case tcc_exceptional:  /* something random, like an identifier.  */
339       switch (code)
340         {
341         case IDENTIFIER_NODE:
342           kind = id_kind;
343           break;
344
345         case TREE_VEC:;
346           kind = vec_kind;
347           break;
348
349         case TREE_BINFO:
350           kind = binfo_kind;
351           break;
352
353         case PHI_NODE:
354           kind = phi_kind;
355           break;
356
357         case SSA_NAME:
358           kind = ssa_name_kind;
359           break;
360
361         case BLOCK:
362           kind = b_kind;
363           break;
364
365         default:
366           kind = x_kind;
367           break;
368         }
369       break;
370       
371     default:
372       gcc_unreachable ();
373     }
374
375   tree_node_counts[(int) kind]++;
376   tree_node_sizes[(int) kind] += length;
377 #endif
378
379   if (code == IDENTIFIER_NODE)
380     t = ggc_alloc_zone_pass_stat (length, &tree_id_zone);
381   else
382     t = ggc_alloc_zone_pass_stat (length, &tree_zone);
383
384   memset (t, 0, length);
385
386   TREE_SET_CODE (t, code);
387
388   switch (type)
389     {
390     case tcc_statement:
391       TREE_SIDE_EFFECTS (t) = 1;
392       break;
393
394     case tcc_declaration:
395       if (code != FUNCTION_DECL)
396         DECL_ALIGN (t) = 1;
397       DECL_USER_ALIGN (t) = 0;
398       DECL_IN_SYSTEM_HEADER (t) = in_system_header;
399       DECL_SOURCE_LOCATION (t) = input_location;
400       DECL_UID (t) = next_decl_uid++;
401
402       /* We have not yet computed the alias set for this declaration.  */
403       DECL_POINTER_ALIAS_SET (t) = -1;
404       break;
405
406     case tcc_type:
407       TYPE_UID (t) = next_type_uid++;
408       TYPE_ALIGN (t) = char_type_node ? TYPE_ALIGN (char_type_node) : 0;
409       TYPE_USER_ALIGN (t) = 0;
410       TYPE_MAIN_VARIANT (t) = t;
411
412       /* Default to no attributes for type, but let target change that.  */
413       TYPE_ATTRIBUTES (t) = NULL_TREE;
414       targetm.set_default_type_attributes (t);
415
416       /* We have not yet computed the alias set for this type.  */
417       TYPE_ALIAS_SET (t) = -1;
418       break;
419
420     case tcc_constant:
421       TREE_CONSTANT (t) = 1;
422       TREE_INVARIANT (t) = 1;
423       break;
424
425     case tcc_expression:
426       switch (code)
427         {
428         case INIT_EXPR:
429         case MODIFY_EXPR:
430         case VA_ARG_EXPR:
431         case PREDECREMENT_EXPR:
432         case PREINCREMENT_EXPR:
433         case POSTDECREMENT_EXPR:
434         case POSTINCREMENT_EXPR:
435           /* All of these have side-effects, no matter what their
436              operands are.  */
437           TREE_SIDE_EFFECTS (t) = 1;
438           break;
439
440         default:
441           break;
442         }
443       break;
444
445     default:
446       /* Other classes need no special treatment.  */
447       break;
448     }
449
450   return t;
451 }
452 \f
453 /* Return a new node with the same contents as NODE except that its
454    TREE_CHAIN is zero and it has a fresh uid.  */
455
456 tree
457 copy_node_stat (tree node MEM_STAT_DECL)
458 {
459   tree t;
460   enum tree_code code = TREE_CODE (node);
461   size_t length;
462
463   gcc_assert (code != STATEMENT_LIST);
464
465   length = tree_size (node);
466   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
467   memcpy (t, node, length);
468
469   TREE_CHAIN (t) = 0;
470   TREE_ASM_WRITTEN (t) = 0;
471   TREE_VISITED (t) = 0;
472   t->common.ann = 0;
473
474   if (TREE_CODE_CLASS (code) == tcc_declaration)
475     {
476       DECL_UID (t) = next_decl_uid++;
477       if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL)
478           && DECL_HAS_VALUE_EXPR_P (node))
479         {
480           SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
481           DECL_HAS_VALUE_EXPR_P (t) = 1;
482         }
483       
484     }
485   else if (TREE_CODE_CLASS (code) == tcc_type)
486     {
487       TYPE_UID (t) = next_type_uid++;
488       /* The following is so that the debug code for
489          the copy is different from the original type.
490          The two statements usually duplicate each other
491          (because they clear fields of the same union),
492          but the optimizer should catch that.  */
493       TYPE_SYMTAB_POINTER (t) = 0;
494       TYPE_SYMTAB_ADDRESS (t) = 0;
495       
496       /* Do not copy the values cache.  */
497       if (TYPE_CACHED_VALUES_P(t))
498         {
499           TYPE_CACHED_VALUES_P (t) = 0;
500           TYPE_CACHED_VALUES (t) = NULL_TREE;
501         }
502     }
503
504   return t;
505 }
506
507 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
508    For example, this can copy a list made of TREE_LIST nodes.  */
509
510 tree
511 copy_list (tree list)
512 {
513   tree head;
514   tree prev, next;
515
516   if (list == 0)
517     return 0;
518
519   head = prev = copy_node (list);
520   next = TREE_CHAIN (list);
521   while (next)
522     {
523       TREE_CHAIN (prev) = copy_node (next);
524       prev = TREE_CHAIN (prev);
525       next = TREE_CHAIN (next);
526     }
527   return head;
528 }
529
530 \f
531 /* Create an INT_CST node with a LOW value sign extended.  */
532
533 tree
534 build_int_cst (tree type, HOST_WIDE_INT low)
535 {
536   return build_int_cst_wide (type, low, low < 0 ? -1 : 0);
537 }
538
539 /* Create an INT_CST node with a LOW value zero extended.  */
540
541 tree
542 build_int_cstu (tree type, unsigned HOST_WIDE_INT low)
543 {
544   return build_int_cst_wide (type, low, 0);
545 }
546
547 /* Create an INT_CST node with a LOW value in TYPE.  The value is sign extended
548    if it is negative.  This function is similar to build_int_cst, but
549    the extra bits outside of the type precision are cleared.  Constants
550    with these extra bits may confuse the fold so that it detects overflows
551    even in cases when they do not occur, and in general should be avoided.
552    We cannot however make this a default behavior of build_int_cst without
553    more intrusive changes, since there are parts of gcc that rely on the extra
554    precision of the integer constants.  */
555
556 tree
557 build_int_cst_type (tree type, HOST_WIDE_INT low)
558 {
559   unsigned HOST_WIDE_INT val = (unsigned HOST_WIDE_INT) low;
560   unsigned HOST_WIDE_INT hi, mask;
561   unsigned bits;
562   bool signed_p;
563   bool negative;
564
565   if (!type)
566     type = integer_type_node;
567
568   bits = TYPE_PRECISION (type);
569   signed_p = !TYPE_UNSIGNED (type);
570
571   if (bits >= HOST_BITS_PER_WIDE_INT)
572     negative = (low < 0);
573   else
574     {
575       /* If the sign bit is inside precision of LOW, use it to determine
576          the sign of the constant.  */
577       negative = ((val >> (bits - 1)) & 1) != 0;
578
579       /* Mask out the bits outside of the precision of the constant.  */
580       mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
581
582       if (signed_p && negative)
583         val |= ~mask;
584       else
585         val &= mask;
586     }
587
588   /* Determine the high bits.  */
589   hi = (negative ? ~(unsigned HOST_WIDE_INT) 0 : 0);
590
591   /* For unsigned type we need to mask out the bits outside of the type
592      precision.  */
593   if (!signed_p)
594     {
595       if (bits <= HOST_BITS_PER_WIDE_INT)
596         hi = 0;
597       else
598         {
599           bits -= HOST_BITS_PER_WIDE_INT;
600           mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
601           hi &= mask;
602         }
603     }
604
605   return build_int_cst_wide (type, val, hi);
606 }
607
608 /* These are the hash table functions for the hash table of INTEGER_CST
609    nodes of a sizetype.  */
610
611 /* Return the hash code code X, an INTEGER_CST.  */
612
613 static hashval_t
614 int_cst_hash_hash (const void *x)
615 {
616   tree t = (tree) x;
617
618   return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
619           ^ htab_hash_pointer (TREE_TYPE (t)));
620 }
621
622 /* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
623    is the same as that given by *Y, which is the same.  */
624
625 static int
626 int_cst_hash_eq (const void *x, const void *y)
627 {
628   tree xt = (tree) x;
629   tree yt = (tree) y;
630
631   return (TREE_TYPE (xt) == TREE_TYPE (yt)
632           && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
633           && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt));
634 }
635
636 /* Create an INT_CST node of TYPE and value HI:LOW.  If TYPE is NULL,
637    integer_type_node is used.  The returned node is always shared.
638    For small integers we use a per-type vector cache, for larger ones
639    we use a single hash table.  */
640
641 tree
642 build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
643 {
644   tree t;
645   int ix = -1;
646   int limit = 0;
647
648   if (!type)
649     type = integer_type_node;
650
651   switch (TREE_CODE (type))
652     {
653     case POINTER_TYPE:
654     case REFERENCE_TYPE:
655       /* Cache NULL pointer.  */
656       if (!hi && !low)
657         {
658           limit = 1;
659           ix = 0;
660         }
661       break;
662
663     case BOOLEAN_TYPE:
664       /* Cache false or true.  */
665       limit = 2;
666       if (!hi && low < 2)
667         ix = low;
668       break;
669
670     case INTEGER_TYPE:
671     case CHAR_TYPE:
672     case OFFSET_TYPE:
673       if (TYPE_UNSIGNED (type))
674         {
675           /* Cache 0..N */
676           limit = INTEGER_SHARE_LIMIT;
677           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
678             ix = low;
679         }
680       else
681         {
682           /* Cache -1..N */
683           limit = INTEGER_SHARE_LIMIT + 1;
684           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
685             ix = low + 1;
686           else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
687             ix = 0;
688         }
689       break;
690     default:
691       break;
692     }
693
694   if (ix >= 0)
695     {
696       /* Look for it in the type's vector of small shared ints.  */
697       if (!TYPE_CACHED_VALUES_P (type))
698         {
699           TYPE_CACHED_VALUES_P (type) = 1;
700           TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
701         }
702
703       t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
704       if (t)
705         {
706           /* Make sure no one is clobbering the shared constant.  */
707           gcc_assert (TREE_TYPE (t) == type);
708           gcc_assert (TREE_INT_CST_LOW (t) == low);
709           gcc_assert (TREE_INT_CST_HIGH (t) == hi);
710         }
711       else
712         {
713           /* Create a new shared int.  */
714           t = make_node (INTEGER_CST);
715
716           TREE_INT_CST_LOW (t) = low;
717           TREE_INT_CST_HIGH (t) = hi;
718           TREE_TYPE (t) = type;
719           
720           TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
721         }
722     }
723   else
724     {
725       /* Use the cache of larger shared ints.  */
726       void **slot;
727
728       TREE_INT_CST_LOW (int_cst_node) = low;
729       TREE_INT_CST_HIGH (int_cst_node) = hi;
730       TREE_TYPE (int_cst_node) = type;
731
732       slot = htab_find_slot (int_cst_hash_table, int_cst_node, INSERT);
733       t = *slot;
734       if (!t)
735         {
736           /* Insert this one into the hash table.  */
737           t = int_cst_node;
738           *slot = t;
739           /* Make a new node for next time round.  */
740           int_cst_node = make_node (INTEGER_CST);
741         }
742     }
743
744   return t;
745 }
746
747 /* Builds an integer constant in TYPE such that lowest BITS bits are ones
748    and the rest are zeros.  */
749
750 tree
751 build_low_bits_mask (tree type, unsigned bits)
752 {
753   unsigned HOST_WIDE_INT low;
754   HOST_WIDE_INT high;
755   unsigned HOST_WIDE_INT all_ones = ~(unsigned HOST_WIDE_INT) 0;
756
757   gcc_assert (bits <= TYPE_PRECISION (type));
758
759   if (bits == TYPE_PRECISION (type)
760       && !TYPE_UNSIGNED (type))
761     {
762       /* Sign extended all-ones mask.  */
763       low = all_ones;
764       high = -1;
765     }
766   else if (bits <= HOST_BITS_PER_WIDE_INT)
767     {
768       low = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
769       high = 0;
770     }
771   else
772     {
773       bits -= HOST_BITS_PER_WIDE_INT;
774       low = all_ones;
775       high = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
776     }
777
778   return build_int_cst_wide (type, low, high);
779 }
780
781 /* Checks that X is integer constant that can be expressed in (unsigned)
782    HOST_WIDE_INT without loss of precision.  */
783
784 bool
785 cst_and_fits_in_hwi (tree x)
786 {
787   if (TREE_CODE (x) != INTEGER_CST)
788     return false;
789
790   if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
791     return false;
792
793   return (TREE_INT_CST_HIGH (x) == 0
794           || TREE_INT_CST_HIGH (x) == -1);
795 }
796
797 /* Return a new VECTOR_CST node whose type is TYPE and whose values
798    are in a list pointed by VALS.  */
799
800 tree
801 build_vector (tree type, tree vals)
802 {
803   tree v = make_node (VECTOR_CST);
804   int over1 = 0, over2 = 0;
805   tree link;
806
807   TREE_VECTOR_CST_ELTS (v) = vals;
808   TREE_TYPE (v) = type;
809
810   /* Iterate through elements and check for overflow.  */
811   for (link = vals; link; link = TREE_CHAIN (link))
812     {
813       tree value = TREE_VALUE (link);
814
815       over1 |= TREE_OVERFLOW (value);
816       over2 |= TREE_CONSTANT_OVERFLOW (value);
817     }
818
819   TREE_OVERFLOW (v) = over1;
820   TREE_CONSTANT_OVERFLOW (v) = over2;
821
822   return v;
823 }
824
825 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
826    are in a list pointed to by VALS.  */
827 tree
828 build_constructor (tree type, tree vals)
829 {
830   tree c = make_node (CONSTRUCTOR);
831   TREE_TYPE (c) = type;
832   CONSTRUCTOR_ELTS (c) = vals;
833
834   /* ??? May not be necessary.  Mirrors what build does.  */
835   if (vals)
836     {
837       TREE_SIDE_EFFECTS (c) = TREE_SIDE_EFFECTS (vals);
838       TREE_READONLY (c) = TREE_READONLY (vals);
839       TREE_CONSTANT (c) = TREE_CONSTANT (vals);
840       TREE_INVARIANT (c) = TREE_INVARIANT (vals);
841     }
842
843   return c;
844 }
845
846 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
847
848 tree
849 build_real (tree type, REAL_VALUE_TYPE d)
850 {
851   tree v;
852   REAL_VALUE_TYPE *dp;
853   int overflow = 0;
854
855   /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
856      Consider doing it via real_convert now.  */
857
858   v = make_node (REAL_CST);
859   dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
860   memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
861
862   TREE_TYPE (v) = type;
863   TREE_REAL_CST_PTR (v) = dp;
864   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
865   return v;
866 }
867
868 /* Return a new REAL_CST node whose type is TYPE
869    and whose value is the integer value of the INTEGER_CST node I.  */
870
871 REAL_VALUE_TYPE
872 real_value_from_int_cst (tree type, tree i)
873 {
874   REAL_VALUE_TYPE d;
875
876   /* Clear all bits of the real value type so that we can later do
877      bitwise comparisons to see if two values are the same.  */
878   memset (&d, 0, sizeof d);
879
880   real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
881                      TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
882                      TYPE_UNSIGNED (TREE_TYPE (i)));
883   return d;
884 }
885
886 /* Given a tree representing an integer constant I, return a tree
887    representing the same value as a floating-point constant of type TYPE.  */
888
889 tree
890 build_real_from_int_cst (tree type, tree i)
891 {
892   tree v;
893   int overflow = TREE_OVERFLOW (i);
894
895   v = build_real (type, real_value_from_int_cst (type, i));
896
897   TREE_OVERFLOW (v) |= overflow;
898   TREE_CONSTANT_OVERFLOW (v) |= overflow;
899   return v;
900 }
901
902 /* Return a newly constructed STRING_CST node whose value is
903    the LEN characters at STR.
904    The TREE_TYPE is not initialized.  */
905
906 tree
907 build_string (int len, const char *str)
908 {
909   tree s;
910   size_t length;
911   
912   length = len + sizeof (struct tree_string);
913
914 #ifdef GATHER_STATISTICS
915   tree_node_counts[(int) c_kind]++;
916   tree_node_sizes[(int) c_kind] += length;
917 #endif  
918
919   s = ggc_alloc_tree (length);
920
921   memset (s, 0, sizeof (struct tree_common));
922   TREE_SET_CODE (s, STRING_CST);
923   TREE_STRING_LENGTH (s) = len;
924   memcpy ((char *) TREE_STRING_POINTER (s), str, len);
925   ((char *) TREE_STRING_POINTER (s))[len] = '\0';
926
927   return s;
928 }
929
930 /* Return a newly constructed COMPLEX_CST node whose value is
931    specified by the real and imaginary parts REAL and IMAG.
932    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
933    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
934
935 tree
936 build_complex (tree type, tree real, tree imag)
937 {
938   tree t = make_node (COMPLEX_CST);
939
940   TREE_REALPART (t) = real;
941   TREE_IMAGPART (t) = imag;
942   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
943   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
944   TREE_CONSTANT_OVERFLOW (t)
945     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
946   return t;
947 }
948
949 /* Build a BINFO with LEN language slots.  */
950
951 tree
952 make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
953 {
954   tree t;
955   size_t length = (offsetof (struct tree_binfo, base_binfos)
956                    + VEC_embedded_size (tree, base_binfos));
957
958 #ifdef GATHER_STATISTICS
959   tree_node_counts[(int) binfo_kind]++;
960   tree_node_sizes[(int) binfo_kind] += length;
961 #endif
962
963   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
964
965   memset (t, 0, offsetof (struct tree_binfo, base_binfos));
966
967   TREE_SET_CODE (t, TREE_BINFO);
968
969   VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos);
970
971   return t;
972 }
973
974
975 /* Build a newly constructed TREE_VEC node of length LEN.  */
976
977 tree
978 make_tree_vec_stat (int len MEM_STAT_DECL)
979 {
980   tree t;
981   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
982
983 #ifdef GATHER_STATISTICS
984   tree_node_counts[(int) vec_kind]++;
985   tree_node_sizes[(int) vec_kind] += length;
986 #endif
987
988   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
989
990   memset (t, 0, length);
991
992   TREE_SET_CODE (t, TREE_VEC);
993   TREE_VEC_LENGTH (t) = len;
994
995   return t;
996 }
997 \f
998 /* Return 1 if EXPR is the integer constant zero or a complex constant
999    of zero.  */
1000
1001 int
1002 integer_zerop (tree expr)
1003 {
1004   STRIP_NOPS (expr);
1005
1006   return ((TREE_CODE (expr) == INTEGER_CST
1007            && ! TREE_CONSTANT_OVERFLOW (expr)
1008            && TREE_INT_CST_LOW (expr) == 0
1009            && TREE_INT_CST_HIGH (expr) == 0)
1010           || (TREE_CODE (expr) == COMPLEX_CST
1011               && integer_zerop (TREE_REALPART (expr))
1012               && integer_zerop (TREE_IMAGPART (expr))));
1013 }
1014
1015 /* Return 1 if EXPR is the integer constant one or the corresponding
1016    complex constant.  */
1017
1018 int
1019 integer_onep (tree expr)
1020 {
1021   STRIP_NOPS (expr);
1022
1023   return ((TREE_CODE (expr) == INTEGER_CST
1024            && ! TREE_CONSTANT_OVERFLOW (expr)
1025            && TREE_INT_CST_LOW (expr) == 1
1026            && TREE_INT_CST_HIGH (expr) == 0)
1027           || (TREE_CODE (expr) == COMPLEX_CST
1028               && integer_onep (TREE_REALPART (expr))
1029               && integer_zerop (TREE_IMAGPART (expr))));
1030 }
1031
1032 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
1033    it contains.  Likewise for the corresponding complex constant.  */
1034
1035 int
1036 integer_all_onesp (tree expr)
1037 {
1038   int prec;
1039   int uns;
1040
1041   STRIP_NOPS (expr);
1042
1043   if (TREE_CODE (expr) == COMPLEX_CST
1044       && integer_all_onesp (TREE_REALPART (expr))
1045       && integer_zerop (TREE_IMAGPART (expr)))
1046     return 1;
1047
1048   else if (TREE_CODE (expr) != INTEGER_CST
1049            || TREE_CONSTANT_OVERFLOW (expr))
1050     return 0;
1051
1052   uns = TYPE_UNSIGNED (TREE_TYPE (expr));
1053   if (!uns)
1054     return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1055             && TREE_INT_CST_HIGH (expr) == -1);
1056
1057   /* Note that using TYPE_PRECISION here is wrong.  We care about the
1058      actual bits, not the (arbitrary) range of the type.  */
1059   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
1060   if (prec >= HOST_BITS_PER_WIDE_INT)
1061     {
1062       HOST_WIDE_INT high_value;
1063       int shift_amount;
1064
1065       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
1066
1067       /* Can not handle precisions greater than twice the host int size.  */
1068       gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT);
1069       if (shift_amount == HOST_BITS_PER_WIDE_INT)
1070         /* Shifting by the host word size is undefined according to the ANSI
1071            standard, so we must handle this as a special case.  */
1072         high_value = -1;
1073       else
1074         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
1075
1076       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1077               && TREE_INT_CST_HIGH (expr) == high_value);
1078     }
1079   else
1080     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
1081 }
1082
1083 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
1084    one bit on).  */
1085
1086 int
1087 integer_pow2p (tree expr)
1088 {
1089   int prec;
1090   HOST_WIDE_INT high, low;
1091
1092   STRIP_NOPS (expr);
1093
1094   if (TREE_CODE (expr) == COMPLEX_CST
1095       && integer_pow2p (TREE_REALPART (expr))
1096       && integer_zerop (TREE_IMAGPART (expr)))
1097     return 1;
1098
1099   if (TREE_CODE (expr) != INTEGER_CST || TREE_CONSTANT_OVERFLOW (expr))
1100     return 0;
1101
1102   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1103           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1104   high = TREE_INT_CST_HIGH (expr);
1105   low = TREE_INT_CST_LOW (expr);
1106
1107   /* First clear all bits that are beyond the type's precision in case
1108      we've been sign extended.  */
1109
1110   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1111     ;
1112   else if (prec > HOST_BITS_PER_WIDE_INT)
1113     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1114   else
1115     {
1116       high = 0;
1117       if (prec < HOST_BITS_PER_WIDE_INT)
1118         low &= ~((HOST_WIDE_INT) (-1) << prec);
1119     }
1120
1121   if (high == 0 && low == 0)
1122     return 0;
1123
1124   return ((high == 0 && (low & (low - 1)) == 0)
1125           || (low == 0 && (high & (high - 1)) == 0));
1126 }
1127
1128 /* Return 1 if EXPR is an integer constant other than zero or a
1129    complex constant other than zero.  */
1130
1131 int
1132 integer_nonzerop (tree expr)
1133 {
1134   STRIP_NOPS (expr);
1135
1136   return ((TREE_CODE (expr) == INTEGER_CST
1137            && ! TREE_CONSTANT_OVERFLOW (expr)
1138            && (TREE_INT_CST_LOW (expr) != 0
1139                || TREE_INT_CST_HIGH (expr) != 0))
1140           || (TREE_CODE (expr) == COMPLEX_CST
1141               && (integer_nonzerop (TREE_REALPART (expr))
1142                   || integer_nonzerop (TREE_IMAGPART (expr)))));
1143 }
1144
1145 /* Return the power of two represented by a tree node known to be a
1146    power of two.  */
1147
1148 int
1149 tree_log2 (tree expr)
1150 {
1151   int prec;
1152   HOST_WIDE_INT high, low;
1153
1154   STRIP_NOPS (expr);
1155
1156   if (TREE_CODE (expr) == COMPLEX_CST)
1157     return tree_log2 (TREE_REALPART (expr));
1158
1159   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1160           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1161
1162   high = TREE_INT_CST_HIGH (expr);
1163   low = TREE_INT_CST_LOW (expr);
1164
1165   /* First clear all bits that are beyond the type's precision in case
1166      we've been sign extended.  */
1167
1168   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1169     ;
1170   else if (prec > HOST_BITS_PER_WIDE_INT)
1171     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1172   else
1173     {
1174       high = 0;
1175       if (prec < HOST_BITS_PER_WIDE_INT)
1176         low &= ~((HOST_WIDE_INT) (-1) << prec);
1177     }
1178
1179   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
1180           : exact_log2 (low));
1181 }
1182
1183 /* Similar, but return the largest integer Y such that 2 ** Y is less
1184    than or equal to EXPR.  */
1185
1186 int
1187 tree_floor_log2 (tree expr)
1188 {
1189   int prec;
1190   HOST_WIDE_INT high, low;
1191
1192   STRIP_NOPS (expr);
1193
1194   if (TREE_CODE (expr) == COMPLEX_CST)
1195     return tree_log2 (TREE_REALPART (expr));
1196
1197   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1198           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1199
1200   high = TREE_INT_CST_HIGH (expr);
1201   low = TREE_INT_CST_LOW (expr);
1202
1203   /* First clear all bits that are beyond the type's precision in case
1204      we've been sign extended.  Ignore if type's precision hasn't been set
1205      since what we are doing is setting it.  */
1206
1207   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
1208     ;
1209   else if (prec > HOST_BITS_PER_WIDE_INT)
1210     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1211   else
1212     {
1213       high = 0;
1214       if (prec < HOST_BITS_PER_WIDE_INT)
1215         low &= ~((HOST_WIDE_INT) (-1) << prec);
1216     }
1217
1218   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
1219           : floor_log2 (low));
1220 }
1221
1222 /* Return 1 if EXPR is the real constant zero.  */
1223
1224 int
1225 real_zerop (tree expr)
1226 {
1227   STRIP_NOPS (expr);
1228
1229   return ((TREE_CODE (expr) == REAL_CST
1230            && ! TREE_CONSTANT_OVERFLOW (expr)
1231            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
1232           || (TREE_CODE (expr) == COMPLEX_CST
1233               && real_zerop (TREE_REALPART (expr))
1234               && real_zerop (TREE_IMAGPART (expr))));
1235 }
1236
1237 /* Return 1 if EXPR is the real constant one in real or complex form.  */
1238
1239 int
1240 real_onep (tree expr)
1241 {
1242   STRIP_NOPS (expr);
1243
1244   return ((TREE_CODE (expr) == REAL_CST
1245            && ! TREE_CONSTANT_OVERFLOW (expr)
1246            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1247           || (TREE_CODE (expr) == COMPLEX_CST
1248               && real_onep (TREE_REALPART (expr))
1249               && real_zerop (TREE_IMAGPART (expr))));
1250 }
1251
1252 /* Return 1 if EXPR is the real constant two.  */
1253
1254 int
1255 real_twop (tree expr)
1256 {
1257   STRIP_NOPS (expr);
1258
1259   return ((TREE_CODE (expr) == REAL_CST
1260            && ! TREE_CONSTANT_OVERFLOW (expr)
1261            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1262           || (TREE_CODE (expr) == COMPLEX_CST
1263               && real_twop (TREE_REALPART (expr))
1264               && real_zerop (TREE_IMAGPART (expr))));
1265 }
1266
1267 /* Return 1 if EXPR is the real constant minus one.  */
1268
1269 int
1270 real_minus_onep (tree expr)
1271 {
1272   STRIP_NOPS (expr);
1273
1274   return ((TREE_CODE (expr) == REAL_CST
1275            && ! TREE_CONSTANT_OVERFLOW (expr)
1276            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
1277           || (TREE_CODE (expr) == COMPLEX_CST
1278               && real_minus_onep (TREE_REALPART (expr))
1279               && real_zerop (TREE_IMAGPART (expr))));
1280 }
1281
1282 /* Nonzero if EXP is a constant or a cast of a constant.  */
1283
1284 int
1285 really_constant_p (tree exp)
1286 {
1287   /* This is not quite the same as STRIP_NOPS.  It does more.  */
1288   while (TREE_CODE (exp) == NOP_EXPR
1289          || TREE_CODE (exp) == CONVERT_EXPR
1290          || TREE_CODE (exp) == NON_LVALUE_EXPR)
1291     exp = TREE_OPERAND (exp, 0);
1292   return TREE_CONSTANT (exp);
1293 }
1294 \f
1295 /* Return first list element whose TREE_VALUE is ELEM.
1296    Return 0 if ELEM is not in LIST.  */
1297
1298 tree
1299 value_member (tree elem, tree list)
1300 {
1301   while (list)
1302     {
1303       if (elem == TREE_VALUE (list))
1304         return list;
1305       list = TREE_CHAIN (list);
1306     }
1307   return NULL_TREE;
1308 }
1309
1310 /* Return first list element whose TREE_PURPOSE is ELEM.
1311    Return 0 if ELEM is not in LIST.  */
1312
1313 tree
1314 purpose_member (tree elem, tree list)
1315 {
1316   while (list)
1317     {
1318       if (elem == TREE_PURPOSE (list))
1319         return list;
1320       list = TREE_CHAIN (list);
1321     }
1322   return NULL_TREE;
1323 }
1324
1325 /* Return nonzero if ELEM is part of the chain CHAIN.  */
1326
1327 int
1328 chain_member (tree elem, tree chain)
1329 {
1330   while (chain)
1331     {
1332       if (elem == chain)
1333         return 1;
1334       chain = TREE_CHAIN (chain);
1335     }
1336
1337   return 0;
1338 }
1339
1340 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1341    We expect a null pointer to mark the end of the chain.
1342    This is the Lisp primitive `length'.  */
1343
1344 int
1345 list_length (tree t)
1346 {
1347   tree p = t;
1348 #ifdef ENABLE_TREE_CHECKING
1349   tree q = t;
1350 #endif
1351   int len = 0;
1352
1353   while (p)
1354     {
1355       p = TREE_CHAIN (p);
1356 #ifdef ENABLE_TREE_CHECKING
1357       if (len % 2)
1358         q = TREE_CHAIN (q);
1359       gcc_assert (p != q);
1360 #endif
1361       len++;
1362     }
1363
1364   return len;
1365 }
1366
1367 /* Returns the number of FIELD_DECLs in TYPE.  */
1368
1369 int
1370 fields_length (tree type)
1371 {
1372   tree t = TYPE_FIELDS (type);
1373   int count = 0;
1374
1375   for (; t; t = TREE_CHAIN (t))
1376     if (TREE_CODE (t) == FIELD_DECL)
1377       ++count;
1378
1379   return count;
1380 }
1381
1382 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1383    by modifying the last node in chain 1 to point to chain 2.
1384    This is the Lisp primitive `nconc'.  */
1385
1386 tree
1387 chainon (tree op1, tree op2)
1388 {
1389   tree t1;
1390
1391   if (!op1)
1392     return op2;
1393   if (!op2)
1394     return op1;
1395
1396   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1397     continue;
1398   TREE_CHAIN (t1) = op2;
1399
1400 #ifdef ENABLE_TREE_CHECKING
1401   {
1402     tree t2;
1403     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1404       gcc_assert (t2 != t1);
1405   }
1406 #endif
1407
1408   return op1;
1409 }
1410
1411 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1412
1413 tree
1414 tree_last (tree chain)
1415 {
1416   tree next;
1417   if (chain)
1418     while ((next = TREE_CHAIN (chain)))
1419       chain = next;
1420   return chain;
1421 }
1422
1423 /* Reverse the order of elements in the chain T,
1424    and return the new head of the chain (old last element).  */
1425
1426 tree
1427 nreverse (tree t)
1428 {
1429   tree prev = 0, decl, next;
1430   for (decl = t; decl; decl = next)
1431     {
1432       next = TREE_CHAIN (decl);
1433       TREE_CHAIN (decl) = prev;
1434       prev = decl;
1435     }
1436   return prev;
1437 }
1438 \f
1439 /* Return a newly created TREE_LIST node whose
1440    purpose and value fields are PARM and VALUE.  */
1441
1442 tree
1443 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1444 {
1445   tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1446   TREE_PURPOSE (t) = parm;
1447   TREE_VALUE (t) = value;
1448   return t;
1449 }
1450
1451 /* Return a newly created TREE_LIST node whose
1452    purpose and value fields are PURPOSE and VALUE
1453    and whose TREE_CHAIN is CHAIN.  */
1454
1455 tree
1456 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1457 {
1458   tree node;
1459
1460   node = ggc_alloc_zone_pass_stat (sizeof (struct tree_list), &tree_zone);
1461
1462   memset (node, 0, sizeof (struct tree_common));
1463
1464 #ifdef GATHER_STATISTICS
1465   tree_node_counts[(int) x_kind]++;
1466   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1467 #endif
1468
1469   TREE_SET_CODE (node, TREE_LIST);
1470   TREE_CHAIN (node) = chain;
1471   TREE_PURPOSE (node) = purpose;
1472   TREE_VALUE (node) = value;
1473   return node;
1474 }
1475
1476 \f
1477 /* Return the size nominally occupied by an object of type TYPE
1478    when it resides in memory.  The value is measured in units of bytes,
1479    and its data type is that normally used for type sizes
1480    (which is the first type created by make_signed_type or
1481    make_unsigned_type).  */
1482
1483 tree
1484 size_in_bytes (tree type)
1485 {
1486   tree t;
1487
1488   if (type == error_mark_node)
1489     return integer_zero_node;
1490
1491   type = TYPE_MAIN_VARIANT (type);
1492   t = TYPE_SIZE_UNIT (type);
1493
1494   if (t == 0)
1495     {
1496       lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1497       return size_zero_node;
1498     }
1499
1500   if (TREE_CODE (t) == INTEGER_CST)
1501     t = force_fit_type (t, 0, false, false);
1502
1503   return t;
1504 }
1505
1506 /* Return the size of TYPE (in bytes) as a wide integer
1507    or return -1 if the size can vary or is larger than an integer.  */
1508
1509 HOST_WIDE_INT
1510 int_size_in_bytes (tree type)
1511 {
1512   tree t;
1513
1514   if (type == error_mark_node)
1515     return 0;
1516
1517   type = TYPE_MAIN_VARIANT (type);
1518   t = TYPE_SIZE_UNIT (type);
1519   if (t == 0
1520       || TREE_CODE (t) != INTEGER_CST
1521       || TREE_OVERFLOW (t)
1522       || TREE_INT_CST_HIGH (t) != 0
1523       /* If the result would appear negative, it's too big to represent.  */
1524       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1525     return -1;
1526
1527   return TREE_INT_CST_LOW (t);
1528 }
1529 \f
1530 /* Return the bit position of FIELD, in bits from the start of the record.
1531    This is a tree of type bitsizetype.  */
1532
1533 tree
1534 bit_position (tree field)
1535 {
1536   return bit_from_pos (DECL_FIELD_OFFSET (field),
1537                        DECL_FIELD_BIT_OFFSET (field));
1538 }
1539
1540 /* Likewise, but return as an integer.  It must be representable in
1541    that way (since it could be a signed value, we don't have the
1542    option of returning -1 like int_size_in_byte can.  */
1543
1544 HOST_WIDE_INT
1545 int_bit_position (tree field)
1546 {
1547   return tree_low_cst (bit_position (field), 0);
1548 }
1549 \f
1550 /* Return the byte position of FIELD, in bytes from the start of the record.
1551    This is a tree of type sizetype.  */
1552
1553 tree
1554 byte_position (tree field)
1555 {
1556   return byte_from_pos (DECL_FIELD_OFFSET (field),
1557                         DECL_FIELD_BIT_OFFSET (field));
1558 }
1559
1560 /* Likewise, but return as an integer.  It must be representable in
1561    that way (since it could be a signed value, we don't have the
1562    option of returning -1 like int_size_in_byte can.  */
1563
1564 HOST_WIDE_INT
1565 int_byte_position (tree field)
1566 {
1567   return tree_low_cst (byte_position (field), 0);
1568 }
1569 \f
1570 /* Return the strictest alignment, in bits, that T is known to have.  */
1571
1572 unsigned int
1573 expr_align (tree t)
1574 {
1575   unsigned int align0, align1;
1576
1577   switch (TREE_CODE (t))
1578     {
1579     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1580       /* If we have conversions, we know that the alignment of the
1581          object must meet each of the alignments of the types.  */
1582       align0 = expr_align (TREE_OPERAND (t, 0));
1583       align1 = TYPE_ALIGN (TREE_TYPE (t));
1584       return MAX (align0, align1);
1585
1586     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1587     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1588     case CLEANUP_POINT_EXPR:
1589       /* These don't change the alignment of an object.  */
1590       return expr_align (TREE_OPERAND (t, 0));
1591
1592     case COND_EXPR:
1593       /* The best we can do is say that the alignment is the least aligned
1594          of the two arms.  */
1595       align0 = expr_align (TREE_OPERAND (t, 1));
1596       align1 = expr_align (TREE_OPERAND (t, 2));
1597       return MIN (align0, align1);
1598
1599     case LABEL_DECL:     case CONST_DECL:
1600     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1601       if (DECL_ALIGN (t) != 0)
1602         return DECL_ALIGN (t);
1603       break;
1604
1605     case FUNCTION_DECL:
1606       return FUNCTION_BOUNDARY;
1607
1608     default:
1609       break;
1610     }
1611
1612   /* Otherwise take the alignment from that of the type.  */
1613   return TYPE_ALIGN (TREE_TYPE (t));
1614 }
1615 \f
1616 /* Return, as a tree node, the number of elements for TYPE (which is an
1617    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1618
1619 tree
1620 array_type_nelts (tree type)
1621 {
1622   tree index_type, min, max;
1623
1624   /* If they did it with unspecified bounds, then we should have already
1625      given an error about it before we got here.  */
1626   if (! TYPE_DOMAIN (type))
1627     return error_mark_node;
1628
1629   index_type = TYPE_DOMAIN (type);
1630   min = TYPE_MIN_VALUE (index_type);
1631   max = TYPE_MAX_VALUE (index_type);
1632
1633   return (integer_zerop (min)
1634           ? max
1635           : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
1636 }
1637 \f
1638 /* If arg is static -- a reference to an object in static storage -- then
1639    return the object.  This is not the same as the C meaning of `static'.
1640    If arg isn't static, return NULL.  */
1641
1642 tree
1643 staticp (tree arg)
1644 {
1645   switch (TREE_CODE (arg))
1646     {
1647     case FUNCTION_DECL:
1648       /* Nested functions are static, even though taking their address will
1649          involve a trampoline as we unnest the nested function and create
1650          the trampoline on the tree level.  */
1651       return arg;
1652
1653     case VAR_DECL:
1654       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1655               && ! DECL_THREAD_LOCAL_P (arg)
1656               && ! DECL_NON_ADDR_CONST_P (arg)
1657               ? arg : NULL);
1658
1659     case CONST_DECL:
1660       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1661               ? arg : NULL);
1662
1663     case CONSTRUCTOR:
1664       return TREE_STATIC (arg) ? arg : NULL;
1665
1666     case LABEL_DECL:
1667     case STRING_CST:
1668       return arg;
1669
1670     case COMPONENT_REF:
1671       /* If the thing being referenced is not a field, then it is
1672          something language specific.  */
1673       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1674         return (*lang_hooks.staticp) (arg);
1675
1676       /* If we are referencing a bitfield, we can't evaluate an
1677          ADDR_EXPR at compile time and so it isn't a constant.  */
1678       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1679         return NULL;
1680
1681       return staticp (TREE_OPERAND (arg, 0));
1682
1683     case BIT_FIELD_REF:
1684       return NULL;
1685
1686     case MISALIGNED_INDIRECT_REF:
1687     case ALIGN_INDIRECT_REF:
1688     case INDIRECT_REF:
1689       return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
1690
1691     case ARRAY_REF:
1692     case ARRAY_RANGE_REF:
1693       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1694           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1695         return staticp (TREE_OPERAND (arg, 0));
1696       else
1697         return false;
1698
1699     default:
1700       if ((unsigned int) TREE_CODE (arg)
1701           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1702         return lang_hooks.staticp (arg);
1703       else
1704         return NULL;
1705     }
1706 }
1707 \f
1708 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1709    Do this to any expression which may be used in more than one place,
1710    but must be evaluated only once.
1711
1712    Normally, expand_expr would reevaluate the expression each time.
1713    Calling save_expr produces something that is evaluated and recorded
1714    the first time expand_expr is called on it.  Subsequent calls to
1715    expand_expr just reuse the recorded value.
1716
1717    The call to expand_expr that generates code that actually computes
1718    the value is the first call *at compile time*.  Subsequent calls
1719    *at compile time* generate code to use the saved value.
1720    This produces correct result provided that *at run time* control
1721    always flows through the insns made by the first expand_expr
1722    before reaching the other places where the save_expr was evaluated.
1723    You, the caller of save_expr, must make sure this is so.
1724
1725    Constants, and certain read-only nodes, are returned with no
1726    SAVE_EXPR because that is safe.  Expressions containing placeholders
1727    are not touched; see tree.def for an explanation of what these
1728    are used for.  */
1729
1730 tree
1731 save_expr (tree expr)
1732 {
1733   tree t = fold (expr);
1734   tree inner;
1735
1736   /* If the tree evaluates to a constant, then we don't want to hide that
1737      fact (i.e. this allows further folding, and direct checks for constants).
1738      However, a read-only object that has side effects cannot be bypassed.
1739      Since it is no problem to reevaluate literals, we just return the
1740      literal node.  */
1741   inner = skip_simple_arithmetic (t);
1742
1743   if (TREE_INVARIANT (inner)
1744       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1745       || TREE_CODE (inner) == SAVE_EXPR
1746       || TREE_CODE (inner) == ERROR_MARK)
1747     return t;
1748
1749   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1750      it means that the size or offset of some field of an object depends on
1751      the value within another field.
1752
1753      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1754      and some variable since it would then need to be both evaluated once and
1755      evaluated more than once.  Front-ends must assure this case cannot
1756      happen by surrounding any such subexpressions in their own SAVE_EXPR
1757      and forcing evaluation at the proper time.  */
1758   if (contains_placeholder_p (inner))
1759     return t;
1760
1761   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
1762
1763   /* This expression might be placed ahead of a jump to ensure that the
1764      value was computed on both sides of the jump.  So make sure it isn't
1765      eliminated as dead.  */
1766   TREE_SIDE_EFFECTS (t) = 1;
1767   TREE_INVARIANT (t) = 1;
1768   return t;
1769 }
1770
1771 /* Look inside EXPR and into any simple arithmetic operations.  Return
1772    the innermost non-arithmetic node.  */
1773
1774 tree
1775 skip_simple_arithmetic (tree expr)
1776 {
1777   tree inner;
1778
1779   /* We don't care about whether this can be used as an lvalue in this
1780      context.  */
1781   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
1782     expr = TREE_OPERAND (expr, 0);
1783
1784   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
1785      a constant, it will be more efficient to not make another SAVE_EXPR since
1786      it will allow better simplification and GCSE will be able to merge the
1787      computations if they actually occur.  */
1788   inner = expr;
1789   while (1)
1790     {
1791       if (UNARY_CLASS_P (inner))
1792         inner = TREE_OPERAND (inner, 0);
1793       else if (BINARY_CLASS_P (inner))
1794         {
1795           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
1796             inner = TREE_OPERAND (inner, 0);
1797           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
1798             inner = TREE_OPERAND (inner, 1);
1799           else
1800             break;
1801         }
1802       else
1803         break;
1804     }
1805
1806   return inner;
1807 }
1808
1809 /* Return which tree structure is used by T.  */
1810
1811 enum tree_node_structure_enum
1812 tree_node_structure (tree t)
1813 {
1814   enum tree_code code = TREE_CODE (t);
1815
1816   switch (TREE_CODE_CLASS (code))
1817     {
1818     case tcc_declaration:
1819       return TS_DECL;
1820     case tcc_type:
1821       return TS_TYPE;
1822     case tcc_reference:
1823     case tcc_comparison:
1824     case tcc_unary:
1825     case tcc_binary:
1826     case tcc_expression:
1827     case tcc_statement:
1828       return TS_EXP;
1829     default:  /* tcc_constant and tcc_exceptional */
1830       break;
1831     }
1832   switch (code)
1833     {
1834       /* tcc_constant cases.  */
1835     case INTEGER_CST:           return TS_INT_CST;
1836     case REAL_CST:              return TS_REAL_CST;
1837     case COMPLEX_CST:           return TS_COMPLEX;
1838     case VECTOR_CST:            return TS_VECTOR;
1839     case STRING_CST:            return TS_STRING;
1840       /* tcc_exceptional cases.  */
1841     case ERROR_MARK:            return TS_COMMON;
1842     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
1843     case TREE_LIST:             return TS_LIST;
1844     case TREE_VEC:              return TS_VEC;
1845     case PHI_NODE:              return TS_PHI_NODE;
1846     case SSA_NAME:              return TS_SSA_NAME;
1847     case PLACEHOLDER_EXPR:      return TS_COMMON;
1848     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
1849     case BLOCK:                 return TS_BLOCK;
1850     case TREE_BINFO:            return TS_BINFO;
1851     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
1852
1853     default:
1854       gcc_unreachable ();
1855     }
1856 }
1857 \f
1858 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
1859    or offset that depends on a field within a record.  */
1860
1861 bool
1862 contains_placeholder_p (tree exp)
1863 {
1864   enum tree_code code;
1865
1866   if (!exp)
1867     return 0;
1868
1869   code = TREE_CODE (exp);
1870   if (code == PLACEHOLDER_EXPR)
1871     return 1;
1872
1873   switch (TREE_CODE_CLASS (code))
1874     {
1875     case tcc_reference:
1876       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
1877          position computations since they will be converted into a
1878          WITH_RECORD_EXPR involving the reference, which will assume
1879          here will be valid.  */
1880       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1881
1882     case tcc_exceptional:
1883       if (code == TREE_LIST)
1884         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
1885                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
1886       break;
1887
1888     case tcc_unary:
1889     case tcc_binary:
1890     case tcc_comparison:
1891     case tcc_expression:
1892       switch (code)
1893         {
1894         case COMPOUND_EXPR:
1895           /* Ignoring the first operand isn't quite right, but works best.  */
1896           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
1897
1898         case COND_EXPR:
1899           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1900                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
1901                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
1902
1903         default:
1904           break;
1905         }
1906
1907       switch (TREE_CODE_LENGTH (code))
1908         {
1909         case 1:
1910           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1911         case 2:
1912           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1913                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
1914         default:
1915           return 0;
1916         }
1917
1918     default:
1919       return 0;
1920     }
1921   return 0;
1922 }
1923
1924 /* Return true if any part of the computation of TYPE involves a
1925    PLACEHOLDER_EXPR.  This includes size, bounds, qualifiers
1926    (for QUAL_UNION_TYPE) and field positions.  */
1927
1928 static bool
1929 type_contains_placeholder_1 (tree type)
1930 {
1931   /* If the size contains a placeholder or the parent type (component type in
1932      the case of arrays) type involves a placeholder, this type does.  */
1933   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
1934       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
1935       || (TREE_TYPE (type) != 0
1936           && type_contains_placeholder_p (TREE_TYPE (type))))
1937     return true;
1938
1939   /* Now do type-specific checks.  Note that the last part of the check above
1940      greatly limits what we have to do below.  */
1941   switch (TREE_CODE (type))
1942     {
1943     case VOID_TYPE:
1944     case COMPLEX_TYPE:
1945     case ENUMERAL_TYPE:
1946     case BOOLEAN_TYPE:
1947     case CHAR_TYPE:
1948     case POINTER_TYPE:
1949     case OFFSET_TYPE:
1950     case REFERENCE_TYPE:
1951     case METHOD_TYPE:
1952     case FUNCTION_TYPE:
1953     case VECTOR_TYPE:
1954       return false;
1955
1956     case INTEGER_TYPE:
1957     case REAL_TYPE:
1958       /* Here we just check the bounds.  */
1959       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
1960               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
1961
1962     case ARRAY_TYPE:
1963       /* We're already checked the component type (TREE_TYPE), so just check
1964          the index type.  */
1965       return type_contains_placeholder_p (TYPE_DOMAIN (type));
1966
1967     case RECORD_TYPE:
1968     case UNION_TYPE:
1969     case QUAL_UNION_TYPE:
1970       {
1971         tree field;
1972
1973         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
1974           if (TREE_CODE (field) == FIELD_DECL
1975               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
1976                   || (TREE_CODE (type) == QUAL_UNION_TYPE
1977                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
1978                   || type_contains_placeholder_p (TREE_TYPE (field))))
1979             return true;
1980
1981         return false;
1982       }
1983
1984     default:
1985       gcc_unreachable ();
1986     }
1987 }
1988
1989 bool
1990 type_contains_placeholder_p (tree type)
1991 {
1992   bool result;
1993
1994   /* If the contains_placeholder_bits field has been initialized,
1995      then we know the answer.  */
1996   if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
1997     return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
1998
1999   /* Indicate that we've seen this type node, and the answer is false.
2000      This is what we want to return if we run into recursion via fields.  */
2001   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
2002
2003   /* Compute the real value.  */
2004   result = type_contains_placeholder_1 (type);
2005
2006   /* Store the real value.  */
2007   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
2008
2009   return result;
2010 }
2011 \f
2012 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
2013    return a tree with all occurrences of references to F in a
2014    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
2015    contains only arithmetic expressions or a CALL_EXPR with a
2016    PLACEHOLDER_EXPR occurring only in its arglist.  */
2017
2018 tree
2019 substitute_in_expr (tree exp, tree f, tree r)
2020 {
2021   enum tree_code code = TREE_CODE (exp);
2022   tree op0, op1, op2;
2023   tree new;
2024   tree inner;
2025
2026   /* We handle TREE_LIST and COMPONENT_REF separately.  */
2027   if (code == TREE_LIST)
2028     {
2029       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
2030       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
2031       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2032         return exp;
2033
2034       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2035     }
2036   else if (code == COMPONENT_REF)
2037    {
2038      /* If this expression is getting a value from a PLACEHOLDER_EXPR
2039         and it is the right field, replace it with R.  */
2040      for (inner = TREE_OPERAND (exp, 0);
2041           REFERENCE_CLASS_P (inner);
2042           inner = TREE_OPERAND (inner, 0))
2043        ;
2044      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2045          && TREE_OPERAND (exp, 1) == f)
2046        return r;
2047
2048      /* If this expression hasn't been completed let, leave it alone.  */
2049      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
2050        return exp;
2051
2052      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2053      if (op0 == TREE_OPERAND (exp, 0))
2054        return exp;
2055
2056      new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp),
2057                         op0, TREE_OPERAND (exp, 1), NULL_TREE);
2058    }
2059   else
2060     switch (TREE_CODE_CLASS (code))
2061       {
2062       case tcc_constant:
2063       case tcc_declaration:
2064         return exp;
2065
2066       case tcc_exceptional:
2067       case tcc_unary:
2068       case tcc_binary:
2069       case tcc_comparison:
2070       case tcc_expression:
2071       case tcc_reference:
2072         switch (TREE_CODE_LENGTH (code))
2073           {
2074           case 0:
2075             return exp;
2076
2077           case 1:
2078             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2079             if (op0 == TREE_OPERAND (exp, 0))
2080               return exp;
2081
2082             new = fold_build1 (code, TREE_TYPE (exp), op0);
2083             break;
2084
2085           case 2:
2086             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2087             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2088
2089             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2090               return exp;
2091
2092             new = fold_build2 (code, TREE_TYPE (exp), op0, op1);
2093             break;
2094
2095           case 3:
2096             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2097             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2098             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2099
2100             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2101                 && op2 == TREE_OPERAND (exp, 2))
2102               return exp;
2103
2104             new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2105             break;
2106
2107           default:
2108             gcc_unreachable ();
2109           }
2110         break;
2111
2112       default:
2113         gcc_unreachable ();
2114       }
2115
2116   TREE_READONLY (new) = TREE_READONLY (exp);
2117   return new;
2118 }
2119
2120 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2121    for it within OBJ, a tree that is an object or a chain of references.  */
2122
2123 tree
2124 substitute_placeholder_in_expr (tree exp, tree obj)
2125 {
2126   enum tree_code code = TREE_CODE (exp);
2127   tree op0, op1, op2, op3;
2128
2129   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2130      in the chain of OBJ.  */
2131   if (code == PLACEHOLDER_EXPR)
2132     {
2133       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2134       tree elt;
2135
2136       for (elt = obj; elt != 0;
2137            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2138                    || TREE_CODE (elt) == COND_EXPR)
2139                   ? TREE_OPERAND (elt, 1)
2140                   : (REFERENCE_CLASS_P (elt)
2141                      || UNARY_CLASS_P (elt)
2142                      || BINARY_CLASS_P (elt)
2143                      || EXPRESSION_CLASS_P (elt))
2144                   ? TREE_OPERAND (elt, 0) : 0))
2145         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2146           return elt;
2147
2148       for (elt = obj; elt != 0;
2149            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2150                    || TREE_CODE (elt) == COND_EXPR)
2151                   ? TREE_OPERAND (elt, 1)
2152                   : (REFERENCE_CLASS_P (elt)
2153                      || UNARY_CLASS_P (elt)
2154                      || BINARY_CLASS_P (elt)
2155                      || EXPRESSION_CLASS_P (elt))
2156                   ? TREE_OPERAND (elt, 0) : 0))
2157         if (POINTER_TYPE_P (TREE_TYPE (elt))
2158             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2159                 == need_type))
2160           return fold_build1 (INDIRECT_REF, need_type, elt);
2161
2162       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2163          survives until RTL generation, there will be an error.  */
2164       return exp;
2165     }
2166
2167   /* TREE_LIST is special because we need to look at TREE_VALUE
2168      and TREE_CHAIN, not TREE_OPERANDS.  */
2169   else if (code == TREE_LIST)
2170     {
2171       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2172       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2173       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2174         return exp;
2175
2176       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2177     }
2178   else
2179     switch (TREE_CODE_CLASS (code))
2180       {
2181       case tcc_constant:
2182       case tcc_declaration:
2183         return exp;
2184
2185       case tcc_exceptional:
2186       case tcc_unary:
2187       case tcc_binary:
2188       case tcc_comparison:
2189       case tcc_expression:
2190       case tcc_reference:
2191       case tcc_statement:
2192         switch (TREE_CODE_LENGTH (code))
2193           {
2194           case 0:
2195             return exp;
2196
2197           case 1:
2198             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2199             if (op0 == TREE_OPERAND (exp, 0))
2200               return exp;
2201             else
2202               return fold_build1 (code, TREE_TYPE (exp), op0);
2203
2204           case 2:
2205             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2206             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2207
2208             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2209               return exp;
2210             else
2211               return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2212
2213           case 3:
2214             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2215             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2216             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2217
2218             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2219                 && op2 == TREE_OPERAND (exp, 2))
2220               return exp;
2221             else
2222               return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2223
2224           case 4:
2225             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2226             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2227             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2228             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2229
2230             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2231                 && op2 == TREE_OPERAND (exp, 2)
2232                 && op3 == TREE_OPERAND (exp, 3))
2233               return exp;
2234             else
2235               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2236
2237           default:
2238             gcc_unreachable ();
2239           }
2240         break;
2241
2242       default:
2243         gcc_unreachable ();
2244       }
2245 }
2246 \f
2247 /* Stabilize a reference so that we can use it any number of times
2248    without causing its operands to be evaluated more than once.
2249    Returns the stabilized reference.  This works by means of save_expr,
2250    so see the caveats in the comments about save_expr.
2251
2252    Also allows conversion expressions whose operands are references.
2253    Any other kind of expression is returned unchanged.  */
2254
2255 tree
2256 stabilize_reference (tree ref)
2257 {
2258   tree result;
2259   enum tree_code code = TREE_CODE (ref);
2260
2261   switch (code)
2262     {
2263     case VAR_DECL:
2264     case PARM_DECL:
2265     case RESULT_DECL:
2266       /* No action is needed in this case.  */
2267       return ref;
2268
2269     case NOP_EXPR:
2270     case CONVERT_EXPR:
2271     case FLOAT_EXPR:
2272     case FIX_TRUNC_EXPR:
2273     case FIX_FLOOR_EXPR:
2274     case FIX_ROUND_EXPR:
2275     case FIX_CEIL_EXPR:
2276       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2277       break;
2278
2279     case INDIRECT_REF:
2280       result = build_nt (INDIRECT_REF,
2281                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2282       break;
2283
2284     case COMPONENT_REF:
2285       result = build_nt (COMPONENT_REF,
2286                          stabilize_reference (TREE_OPERAND (ref, 0)),
2287                          TREE_OPERAND (ref, 1), NULL_TREE);
2288       break;
2289
2290     case BIT_FIELD_REF:
2291       result = build_nt (BIT_FIELD_REF,
2292                          stabilize_reference (TREE_OPERAND (ref, 0)),
2293                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2294                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2295       break;
2296
2297     case ARRAY_REF:
2298       result = build_nt (ARRAY_REF,
2299                          stabilize_reference (TREE_OPERAND (ref, 0)),
2300                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2301                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2302       break;
2303
2304     case ARRAY_RANGE_REF:
2305       result = build_nt (ARRAY_RANGE_REF,
2306                          stabilize_reference (TREE_OPERAND (ref, 0)),
2307                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2308                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2309       break;
2310
2311     case COMPOUND_EXPR:
2312       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2313          it wouldn't be ignored.  This matters when dealing with
2314          volatiles.  */
2315       return stabilize_reference_1 (ref);
2316
2317       /* If arg isn't a kind of lvalue we recognize, make no change.
2318          Caller should recognize the error for an invalid lvalue.  */
2319     default:
2320       return ref;
2321
2322     case ERROR_MARK:
2323       return error_mark_node;
2324     }
2325
2326   TREE_TYPE (result) = TREE_TYPE (ref);
2327   TREE_READONLY (result) = TREE_READONLY (ref);
2328   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2329   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2330
2331   return result;
2332 }
2333
2334 /* Subroutine of stabilize_reference; this is called for subtrees of
2335    references.  Any expression with side-effects must be put in a SAVE_EXPR
2336    to ensure that it is only evaluated once.
2337
2338    We don't put SAVE_EXPR nodes around everything, because assigning very
2339    simple expressions to temporaries causes us to miss good opportunities
2340    for optimizations.  Among other things, the opportunity to fold in the
2341    addition of a constant into an addressing mode often gets lost, e.g.
2342    "y[i+1] += x;".  In general, we take the approach that we should not make
2343    an assignment unless we are forced into it - i.e., that any non-side effect
2344    operator should be allowed, and that cse should take care of coalescing
2345    multiple utterances of the same expression should that prove fruitful.  */
2346
2347 tree
2348 stabilize_reference_1 (tree e)
2349 {
2350   tree result;
2351   enum tree_code code = TREE_CODE (e);
2352
2353   /* We cannot ignore const expressions because it might be a reference
2354      to a const array but whose index contains side-effects.  But we can
2355      ignore things that are actual constant or that already have been
2356      handled by this function.  */
2357
2358   if (TREE_INVARIANT (e))
2359     return e;
2360
2361   switch (TREE_CODE_CLASS (code))
2362     {
2363     case tcc_exceptional:
2364     case tcc_type:
2365     case tcc_declaration:
2366     case tcc_comparison:
2367     case tcc_statement:
2368     case tcc_expression:
2369     case tcc_reference:
2370       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2371          so that it will only be evaluated once.  */
2372       /* The reference (r) and comparison (<) classes could be handled as
2373          below, but it is generally faster to only evaluate them once.  */
2374       if (TREE_SIDE_EFFECTS (e))
2375         return save_expr (e);
2376       return e;
2377
2378     case tcc_constant:
2379       /* Constants need no processing.  In fact, we should never reach
2380          here.  */
2381       return e;
2382
2383     case tcc_binary:
2384       /* Division is slow and tends to be compiled with jumps,
2385          especially the division by powers of 2 that is often
2386          found inside of an array reference.  So do it just once.  */
2387       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2388           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2389           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2390           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2391         return save_expr (e);
2392       /* Recursively stabilize each operand.  */
2393       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2394                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2395       break;
2396
2397     case tcc_unary:
2398       /* Recursively stabilize each operand.  */
2399       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2400       break;
2401
2402     default:
2403       gcc_unreachable ();
2404     }
2405
2406   TREE_TYPE (result) = TREE_TYPE (e);
2407   TREE_READONLY (result) = TREE_READONLY (e);
2408   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2409   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2410   TREE_INVARIANT (result) = 1;
2411
2412   return result;
2413 }
2414 \f
2415 /* Low-level constructors for expressions.  */
2416
2417 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2418    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2419
2420 void
2421 recompute_tree_invarant_for_addr_expr (tree t)
2422 {
2423   tree node;
2424   bool tc = true, ti = true, se = false;
2425
2426   /* We started out assuming this address is both invariant and constant, but
2427      does not have side effects.  Now go down any handled components and see if
2428      any of them involve offsets that are either non-constant or non-invariant.
2429      Also check for side-effects.
2430
2431      ??? Note that this code makes no attempt to deal with the case where
2432      taking the address of something causes a copy due to misalignment.  */
2433
2434 #define UPDATE_TITCSE(NODE)  \
2435 do { tree _node = (NODE); \
2436      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2437      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2438      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2439
2440   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2441        node = TREE_OPERAND (node, 0))
2442     {
2443       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2444          array reference (probably made temporarily by the G++ front end),
2445          so ignore all the operands.  */
2446       if ((TREE_CODE (node) == ARRAY_REF
2447            || TREE_CODE (node) == ARRAY_RANGE_REF)
2448           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2449         {
2450           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2451           if (TREE_OPERAND (node, 2))
2452             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2453           if (TREE_OPERAND (node, 3))
2454             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2455         }
2456       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2457          FIELD_DECL, apparently.  The G++ front end can put something else
2458          there, at least temporarily.  */
2459       else if (TREE_CODE (node) == COMPONENT_REF
2460                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2461         {
2462           if (TREE_OPERAND (node, 2))
2463             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2464         }
2465       else if (TREE_CODE (node) == BIT_FIELD_REF)
2466         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2467     }
2468
2469   node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2470
2471   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2472      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2473      invariant and constant if the decl is static.  It's also invariant if it's
2474      a decl in the current function.  Taking the address of a volatile variable
2475      is not volatile.  If it's a constant, the address is both invariant and
2476      constant.  Otherwise it's neither.  */
2477   if (TREE_CODE (node) == INDIRECT_REF)
2478     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2479   else if (DECL_P (node))
2480     {
2481       if (staticp (node))
2482         ;
2483       else if (decl_function_context (node) == current_function_decl
2484                /* Addresses of thread-local variables are invariant.  */
2485                || (TREE_CODE (node) == VAR_DECL
2486                    && DECL_THREAD_LOCAL_P (node)))
2487         tc = false;
2488       else
2489         ti = tc = false;
2490     }
2491   else if (CONSTANT_CLASS_P (node))
2492     ;
2493   else
2494     {
2495       ti = tc = false;
2496       se |= TREE_SIDE_EFFECTS (node);
2497     }
2498
2499   TREE_CONSTANT (t) = tc;
2500   TREE_INVARIANT (t) = ti;
2501   TREE_SIDE_EFFECTS (t) = se;
2502 #undef UPDATE_TITCSE
2503 }
2504
2505 /* Build an expression of code CODE, data type TYPE, and operands as
2506    specified.  Expressions and reference nodes can be created this way.
2507    Constants, decls, types and misc nodes cannot be.
2508
2509    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2510    enough for all extant tree codes.  These functions can be called
2511    directly (preferably!), but can also be obtained via GCC preprocessor
2512    magic within the build macro.  */
2513
2514 tree
2515 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2516 {
2517   tree t;
2518
2519   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2520
2521   t = make_node_stat (code PASS_MEM_STAT);
2522   TREE_TYPE (t) = tt;
2523
2524   return t;
2525 }
2526
2527 tree
2528 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2529 {
2530   int length = sizeof (struct tree_exp);
2531 #ifdef GATHER_STATISTICS
2532   tree_node_kind kind;
2533 #endif
2534   tree t;
2535
2536 #ifdef GATHER_STATISTICS
2537   switch (TREE_CODE_CLASS (code))
2538     {
2539     case tcc_statement:  /* an expression with side effects */
2540       kind = s_kind;
2541       break;
2542     case tcc_reference:  /* a reference */
2543       kind = r_kind;
2544       break;
2545     default:
2546       kind = e_kind;
2547       break;
2548     }
2549
2550   tree_node_counts[(int) kind]++;
2551   tree_node_sizes[(int) kind] += length;
2552 #endif
2553
2554   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2555
2556   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2557
2558   memset (t, 0, sizeof (struct tree_common));
2559
2560   TREE_SET_CODE (t, code);
2561
2562   TREE_TYPE (t) = type;
2563 #ifdef USE_MAPPED_LOCATION
2564   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2565 #else
2566   SET_EXPR_LOCUS (t, NULL);
2567 #endif
2568   TREE_COMPLEXITY (t) = 0;
2569   TREE_OPERAND (t, 0) = node;
2570   TREE_BLOCK (t) = NULL_TREE;
2571   if (node && !TYPE_P (node))
2572     {
2573       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2574       TREE_READONLY (t) = TREE_READONLY (node);
2575     }
2576
2577   if (TREE_CODE_CLASS (code) == tcc_statement)
2578     TREE_SIDE_EFFECTS (t) = 1;
2579   else switch (code)
2580     {
2581     case VA_ARG_EXPR:
2582       /* All of these have side-effects, no matter what their
2583          operands are.  */
2584       TREE_SIDE_EFFECTS (t) = 1;
2585       TREE_READONLY (t) = 0;
2586       break;
2587
2588     case MISALIGNED_INDIRECT_REF:
2589     case ALIGN_INDIRECT_REF:
2590     case INDIRECT_REF:
2591       /* Whether a dereference is readonly has nothing to do with whether
2592          its operand is readonly.  */
2593       TREE_READONLY (t) = 0;
2594       break;
2595
2596     case ADDR_EXPR:
2597       if (node)
2598         recompute_tree_invarant_for_addr_expr (t);
2599       break;
2600
2601     default:
2602       if (TREE_CODE_CLASS (code) == tcc_unary
2603           && node && !TYPE_P (node)
2604           && TREE_CONSTANT (node))
2605         TREE_CONSTANT (t) = 1;
2606       if (TREE_CODE_CLASS (code) == tcc_unary
2607           && node && TREE_INVARIANT (node))
2608         TREE_INVARIANT (t) = 1;
2609       if (TREE_CODE_CLASS (code) == tcc_reference
2610           && node && TREE_THIS_VOLATILE (node))
2611         TREE_THIS_VOLATILE (t) = 1;
2612       break;
2613     }
2614
2615   return t;
2616 }
2617
2618 #define PROCESS_ARG(N)                  \
2619   do {                                  \
2620     TREE_OPERAND (t, N) = arg##N;       \
2621     if (arg##N &&!TYPE_P (arg##N))      \
2622       {                                 \
2623         if (TREE_SIDE_EFFECTS (arg##N)) \
2624           side_effects = 1;             \
2625         if (!TREE_READONLY (arg##N))    \
2626           read_only = 0;                \
2627         if (!TREE_CONSTANT (arg##N))    \
2628           constant = 0;                 \
2629         if (!TREE_INVARIANT (arg##N))   \
2630           invariant = 0;                \
2631       }                                 \
2632   } while (0)
2633
2634 tree
2635 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2636 {
2637   bool constant, read_only, side_effects, invariant;
2638   tree t;
2639
2640   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2641
2642   t = make_node_stat (code PASS_MEM_STAT);
2643   TREE_TYPE (t) = tt;
2644
2645   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2646      result based on those same flags for the arguments.  But if the
2647      arguments aren't really even `tree' expressions, we shouldn't be trying
2648      to do this.  */
2649
2650   /* Expressions without side effects may be constant if their
2651      arguments are as well.  */
2652   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2653               || TREE_CODE_CLASS (code) == tcc_binary);
2654   read_only = 1;
2655   side_effects = TREE_SIDE_EFFECTS (t);
2656   invariant = constant;
2657
2658   PROCESS_ARG(0);
2659   PROCESS_ARG(1);
2660
2661   TREE_READONLY (t) = read_only;
2662   TREE_CONSTANT (t) = constant;
2663   TREE_INVARIANT (t) = invariant;
2664   TREE_SIDE_EFFECTS (t) = side_effects;
2665   TREE_THIS_VOLATILE (t)
2666     = (TREE_CODE_CLASS (code) == tcc_reference
2667        && arg0 && TREE_THIS_VOLATILE (arg0));
2668
2669   return t;
2670 }
2671
2672 tree
2673 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2674              tree arg2 MEM_STAT_DECL)
2675 {
2676   bool constant, read_only, side_effects, invariant;
2677   tree t;
2678
2679   gcc_assert (TREE_CODE_LENGTH (code) == 3);
2680
2681   t = make_node_stat (code PASS_MEM_STAT);
2682   TREE_TYPE (t) = tt;
2683
2684   side_effects = TREE_SIDE_EFFECTS (t);
2685
2686   PROCESS_ARG(0);
2687   PROCESS_ARG(1);
2688   PROCESS_ARG(2);
2689
2690   if (code == CALL_EXPR && !side_effects)
2691     {
2692       tree node;
2693       int i;
2694
2695       /* Calls have side-effects, except those to const or
2696          pure functions.  */
2697       i = call_expr_flags (t);
2698       if (!(i & (ECF_CONST | ECF_PURE)))
2699         side_effects = 1;
2700
2701       /* And even those have side-effects if their arguments do.  */
2702       else for (node = arg1; node; node = TREE_CHAIN (node))
2703         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2704           {
2705             side_effects = 1;
2706             break;
2707           }
2708     }
2709
2710   TREE_SIDE_EFFECTS (t) = side_effects;
2711   TREE_THIS_VOLATILE (t)
2712     = (TREE_CODE_CLASS (code) == tcc_reference
2713        && arg0 && TREE_THIS_VOLATILE (arg0));
2714
2715   return t;
2716 }
2717
2718 tree
2719 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2720              tree arg2, tree arg3 MEM_STAT_DECL)
2721 {
2722   bool constant, read_only, side_effects, invariant;
2723   tree t;
2724
2725   gcc_assert (TREE_CODE_LENGTH (code) == 4);
2726
2727   t = make_node_stat (code PASS_MEM_STAT);
2728   TREE_TYPE (t) = tt;
2729
2730   side_effects = TREE_SIDE_EFFECTS (t);
2731
2732   PROCESS_ARG(0);
2733   PROCESS_ARG(1);
2734   PROCESS_ARG(2);
2735   PROCESS_ARG(3);
2736
2737   TREE_SIDE_EFFECTS (t) = side_effects;
2738   TREE_THIS_VOLATILE (t)
2739     = (TREE_CODE_CLASS (code) == tcc_reference
2740        && arg0 && TREE_THIS_VOLATILE (arg0));
2741
2742   return t;
2743 }
2744
2745 tree
2746 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2747              tree arg2, tree arg3, tree arg4, tree arg5,
2748              tree arg6 MEM_STAT_DECL)
2749 {
2750   bool constant, read_only, side_effects, invariant;
2751   tree t;
2752
2753   gcc_assert (code == TARGET_MEM_REF);
2754
2755   t = make_node_stat (code PASS_MEM_STAT);
2756   TREE_TYPE (t) = tt;
2757
2758   side_effects = TREE_SIDE_EFFECTS (t);
2759
2760   PROCESS_ARG(0);
2761   PROCESS_ARG(1);
2762   PROCESS_ARG(2);
2763   PROCESS_ARG(3);
2764   PROCESS_ARG(4);
2765   PROCESS_ARG(5);
2766   PROCESS_ARG(6);
2767
2768   TREE_SIDE_EFFECTS (t) = side_effects;
2769   TREE_THIS_VOLATILE (t) = 0;
2770
2771   return t;
2772 }
2773
2774 /* Backup definition for non-gcc build compilers.  */
2775
2776 tree
2777 (build) (enum tree_code code, tree tt, ...)
2778 {
2779   tree t, arg0, arg1, arg2, arg3, arg4, arg5, arg6;
2780   int length = TREE_CODE_LENGTH (code);
2781   va_list p;
2782
2783   va_start (p, tt);
2784   switch (length)
2785     {
2786     case 0:
2787       t = build0 (code, tt);
2788       break;
2789     case 1:
2790       arg0 = va_arg (p, tree);
2791       t = build1 (code, tt, arg0);
2792       break;
2793     case 2:
2794       arg0 = va_arg (p, tree);
2795       arg1 = va_arg (p, tree);
2796       t = build2 (code, tt, arg0, arg1);
2797       break;
2798     case 3:
2799       arg0 = va_arg (p, tree);
2800       arg1 = va_arg (p, tree);
2801       arg2 = va_arg (p, tree);
2802       t = build3 (code, tt, arg0, arg1, arg2);
2803       break;
2804     case 4:
2805       arg0 = va_arg (p, tree);
2806       arg1 = va_arg (p, tree);
2807       arg2 = va_arg (p, tree);
2808       arg3 = va_arg (p, tree);
2809       t = build4 (code, tt, arg0, arg1, arg2, arg3);
2810       break;
2811     case 7:
2812       arg0 = va_arg (p, tree);
2813       arg1 = va_arg (p, tree);
2814       arg2 = va_arg (p, tree);
2815       arg3 = va_arg (p, tree);
2816       arg4 = va_arg (p, tree);
2817       arg5 = va_arg (p, tree);
2818       arg6 = va_arg (p, tree);
2819       t = build7 (code, tt, arg0, arg1, arg2, arg3, arg4, arg5, arg6);
2820       break;
2821     default:
2822       gcc_unreachable ();
2823     }
2824   va_end (p);
2825
2826   return t;
2827 }
2828
2829 /* Similar except don't specify the TREE_TYPE
2830    and leave the TREE_SIDE_EFFECTS as 0.
2831    It is permissible for arguments to be null,
2832    or even garbage if their values do not matter.  */
2833
2834 tree
2835 build_nt (enum tree_code code, ...)
2836 {
2837   tree t;
2838   int length;
2839   int i;
2840   va_list p;
2841
2842   va_start (p, code);
2843
2844   t = make_node (code);
2845   length = TREE_CODE_LENGTH (code);
2846
2847   for (i = 0; i < length; i++)
2848     TREE_OPERAND (t, i) = va_arg (p, tree);
2849
2850   va_end (p);
2851   return t;
2852 }
2853 \f
2854 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2855    We do NOT enter this node in any sort of symbol table.
2856
2857    layout_decl is used to set up the decl's storage layout.
2858    Other slots are initialized to 0 or null pointers.  */
2859
2860 tree
2861 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
2862 {
2863   tree t;
2864
2865   t = make_node_stat (code PASS_MEM_STAT);
2866
2867 /*  if (type == error_mark_node)
2868     type = integer_type_node; */
2869 /* That is not done, deliberately, so that having error_mark_node
2870    as the type can suppress useless errors in the use of this variable.  */
2871
2872   DECL_NAME (t) = name;
2873   TREE_TYPE (t) = type;
2874
2875   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2876     layout_decl (t, 0);
2877   else if (code == FUNCTION_DECL)
2878     DECL_MODE (t) = FUNCTION_MODE;
2879
2880   /* Set default visibility to whatever the user supplied with
2881      visibility_specified depending on #pragma GCC visibility.  */
2882   DECL_VISIBILITY (t) = default_visibility;
2883   DECL_VISIBILITY_SPECIFIED (t) = visibility_options.inpragma;
2884
2885   return t;
2886 }
2887
2888 /* Builds and returns function declaration with NAME and TYPE.  */
2889
2890 tree
2891 build_fn_decl (const char *name, tree type)
2892 {
2893   tree id = get_identifier (name);
2894   tree decl = build_decl (FUNCTION_DECL, id, type);
2895
2896   DECL_EXTERNAL (decl) = 1;
2897   TREE_PUBLIC (decl) = 1;
2898   DECL_ARTIFICIAL (decl) = 1;
2899   TREE_NOTHROW (decl) = 1;
2900
2901   return decl;
2902 }
2903
2904 \f
2905 /* BLOCK nodes are used to represent the structure of binding contours
2906    and declarations, once those contours have been exited and their contents
2907    compiled.  This information is used for outputting debugging info.  */
2908
2909 tree
2910 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
2911 {
2912   tree block = make_node (BLOCK);
2913
2914   BLOCK_VARS (block) = vars;
2915   BLOCK_SUBBLOCKS (block) = subblocks;
2916   BLOCK_SUPERCONTEXT (block) = supercontext;
2917   BLOCK_CHAIN (block) = chain;
2918   return block;
2919 }
2920
2921 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
2922 /* ??? gengtype doesn't handle conditionals */
2923 static GTY(()) tree last_annotated_node;
2924 #endif
2925
2926 #ifdef USE_MAPPED_LOCATION
2927
2928 expanded_location
2929 expand_location (source_location loc)
2930 {
2931   expanded_location xloc;
2932   if (loc == 0) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
2933   else
2934     {
2935       const struct line_map *map = linemap_lookup (&line_table, loc);
2936       xloc.file = map->to_file;
2937       xloc.line = SOURCE_LINE (map, loc);
2938       xloc.column = SOURCE_COLUMN (map, loc);
2939     };
2940   return xloc;
2941 }
2942
2943 #else
2944
2945 /* Record the exact location where an expression or an identifier were
2946    encountered.  */
2947
2948 void
2949 annotate_with_file_line (tree node, const char *file, int line)
2950 {
2951   /* Roughly one percent of the calls to this function are to annotate
2952      a node with the same information already attached to that node!
2953      Just return instead of wasting memory.  */
2954   if (EXPR_LOCUS (node)
2955       && (EXPR_FILENAME (node) == file
2956           || ! strcmp (EXPR_FILENAME (node), file))
2957       && EXPR_LINENO (node) == line)
2958     {
2959       last_annotated_node = node;
2960       return;
2961     }
2962
2963   /* In heavily macroized code (such as GCC itself) this single
2964      entry cache can reduce the number of allocations by more
2965      than half.  */
2966   if (last_annotated_node
2967       && EXPR_LOCUS (last_annotated_node)
2968       && (EXPR_FILENAME (last_annotated_node) == file
2969           || ! strcmp (EXPR_FILENAME (last_annotated_node), file))
2970       && EXPR_LINENO (last_annotated_node) == line)
2971     {
2972       SET_EXPR_LOCUS (node, EXPR_LOCUS (last_annotated_node));
2973       return;
2974     }
2975
2976   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
2977   EXPR_LINENO (node) = line;
2978   EXPR_FILENAME (node) = file;
2979   last_annotated_node = node;
2980 }
2981
2982 void
2983 annotate_with_locus (tree node, location_t locus)
2984 {
2985   annotate_with_file_line (node, locus.file, locus.line);
2986 }
2987 #endif
2988 \f
2989 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2990    is ATTRIBUTE.  */
2991
2992 tree
2993 build_decl_attribute_variant (tree ddecl, tree attribute)
2994 {
2995   DECL_ATTRIBUTES (ddecl) = attribute;
2996   return ddecl;
2997 }
2998
2999 /* Borrowed from hashtab.c iterative_hash implementation.  */
3000 #define mix(a,b,c) \
3001 { \
3002   a -= b; a -= c; a ^= (c>>13); \
3003   b -= c; b -= a; b ^= (a<< 8); \
3004   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3005   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3006   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3007   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3008   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3009   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3010   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3011 }
3012
3013
3014 /* Produce good hash value combining VAL and VAL2.  */
3015 static inline hashval_t
3016 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3017 {
3018   /* the golden ratio; an arbitrary value.  */
3019   hashval_t a = 0x9e3779b9;
3020
3021   mix (a, val, val2);
3022   return val2;
3023 }
3024
3025 /* Produce good hash value combining PTR and VAL2.  */
3026 static inline hashval_t
3027 iterative_hash_pointer (void *ptr, hashval_t val2)
3028 {
3029   if (sizeof (ptr) == sizeof (hashval_t))
3030     return iterative_hash_hashval_t ((size_t) ptr, val2);
3031   else
3032     {
3033       hashval_t a = (hashval_t) (size_t) ptr;
3034       /* Avoid warnings about shifting of more than the width of the type on
3035          hosts that won't execute this path.  */
3036       int zero = 0;
3037       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3038       mix (a, b, val2);
3039       return val2;
3040     }
3041 }
3042
3043 /* Produce good hash value combining VAL and VAL2.  */
3044 static inline hashval_t
3045 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3046 {
3047   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3048     return iterative_hash_hashval_t (val, val2);
3049   else
3050     {
3051       hashval_t a = (hashval_t) val;
3052       /* Avoid warnings about shifting of more than the width of the type on
3053          hosts that won't execute this path.  */
3054       int zero = 0;
3055       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3056       mix (a, b, val2);
3057       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3058         {
3059           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3060           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3061           mix (a, b, val2);
3062         }
3063       return val2;
3064     }
3065 }
3066
3067 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3068    is ATTRIBUTE.
3069
3070    Record such modified types already made so we don't make duplicates.  */
3071
3072 tree
3073 build_type_attribute_variant (tree ttype, tree attribute)
3074 {
3075   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3076     {
3077       hashval_t hashcode = 0;
3078       tree ntype;
3079       enum tree_code code = TREE_CODE (ttype);
3080
3081       ntype = copy_node (ttype);
3082
3083       TYPE_POINTER_TO (ntype) = 0;
3084       TYPE_REFERENCE_TO (ntype) = 0;
3085       TYPE_ATTRIBUTES (ntype) = attribute;
3086
3087       /* Create a new main variant of TYPE.  */
3088       TYPE_MAIN_VARIANT (ntype) = ntype;
3089       TYPE_NEXT_VARIANT (ntype) = 0;
3090       set_type_quals (ntype, TYPE_UNQUALIFIED);
3091
3092       hashcode = iterative_hash_object (code, hashcode);
3093       if (TREE_TYPE (ntype))
3094         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3095                                           hashcode);
3096       hashcode = attribute_hash_list (attribute, hashcode);
3097
3098       switch (TREE_CODE (ntype))
3099         {
3100         case FUNCTION_TYPE:
3101           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3102           break;
3103         case ARRAY_TYPE:
3104           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3105                                             hashcode);
3106           break;
3107         case INTEGER_TYPE:
3108           hashcode = iterative_hash_object
3109             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3110           hashcode = iterative_hash_object
3111             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3112           break;
3113         case REAL_TYPE:
3114           {
3115             unsigned int precision = TYPE_PRECISION (ntype);
3116             hashcode = iterative_hash_object (precision, hashcode);
3117           }
3118           break;
3119         default:
3120           break;
3121         }
3122
3123       ntype = type_hash_canon (hashcode, ntype);
3124       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
3125     }
3126
3127   return ttype;
3128 }
3129
3130
3131 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3132    or zero if not.
3133
3134    We try both `text' and `__text__', ATTR may be either one.  */
3135 /* ??? It might be a reasonable simplification to require ATTR to be only
3136    `text'.  One might then also require attribute lists to be stored in
3137    their canonicalized form.  */
3138
3139 static int
3140 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3141 {
3142   int ident_len;
3143   const char *p;
3144
3145   if (TREE_CODE (ident) != IDENTIFIER_NODE)
3146     return 0;
3147   
3148   p = IDENTIFIER_POINTER (ident);
3149   ident_len = IDENTIFIER_LENGTH (ident);
3150   
3151   if (ident_len == attr_len
3152       && strcmp (attr, p) == 0)
3153     return 1;
3154
3155   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
3156   if (attr[0] == '_')
3157     {
3158       gcc_assert (attr[1] == '_');
3159       gcc_assert (attr[attr_len - 2] == '_');
3160       gcc_assert (attr[attr_len - 1] == '_');
3161       gcc_assert (attr[1] == '_');
3162       if (ident_len == attr_len - 4
3163           && strncmp (attr + 2, p, attr_len - 4) == 0)
3164         return 1;
3165     }
3166   else
3167     {
3168       if (ident_len == attr_len + 4
3169           && p[0] == '_' && p[1] == '_'
3170           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3171           && strncmp (attr, p + 2, attr_len) == 0)
3172         return 1;
3173     }
3174
3175   return 0;
3176 }
3177
3178 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3179    or zero if not.
3180
3181    We try both `text' and `__text__', ATTR may be either one.  */
3182
3183 int
3184 is_attribute_p (const char *attr, tree ident)
3185 {
3186   return is_attribute_with_length_p (attr, strlen (attr), ident);
3187 }
3188
3189 /* Given an attribute name and a list of attributes, return a pointer to the
3190    attribute's list element if the attribute is part of the list, or NULL_TREE
3191    if not found.  If the attribute appears more than once, this only
3192    returns the first occurrence; the TREE_CHAIN of the return value should
3193    be passed back in if further occurrences are wanted.  */
3194
3195 tree
3196 lookup_attribute (const char *attr_name, tree list)
3197 {
3198   tree l;
3199   size_t attr_len = strlen (attr_name);
3200
3201   for (l = list; l; l = TREE_CHAIN (l))
3202     {
3203       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3204       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3205         return l;
3206     }
3207
3208   return NULL_TREE;
3209 }
3210
3211 /* Return an attribute list that is the union of a1 and a2.  */
3212
3213 tree
3214 merge_attributes (tree a1, tree a2)
3215 {
3216   tree attributes;
3217
3218   /* Either one unset?  Take the set one.  */
3219
3220   if ((attributes = a1) == 0)
3221     attributes = a2;
3222
3223   /* One that completely contains the other?  Take it.  */
3224
3225   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3226     {
3227       if (attribute_list_contained (a2, a1))
3228         attributes = a2;
3229       else
3230         {
3231           /* Pick the longest list, and hang on the other list.  */
3232
3233           if (list_length (a1) < list_length (a2))
3234             attributes = a2, a2 = a1;
3235
3236           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3237             {
3238               tree a;
3239               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3240                                          attributes);
3241                    a != NULL_TREE;
3242                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3243                                          TREE_CHAIN (a)))
3244                 {
3245                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
3246                     break;
3247                 }
3248               if (a == NULL_TREE)
3249                 {
3250                   a1 = copy_node (a2);
3251                   TREE_CHAIN (a1) = attributes;
3252                   attributes = a1;
3253                 }
3254             }
3255         }
3256     }
3257   return attributes;
3258 }
3259
3260 /* Given types T1 and T2, merge their attributes and return
3261   the result.  */
3262
3263 tree
3264 merge_type_attributes (tree t1, tree t2)
3265 {
3266   return merge_attributes (TYPE_ATTRIBUTES (t1),
3267                            TYPE_ATTRIBUTES (t2));
3268 }
3269
3270 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3271    the result.  */
3272
3273 tree
3274 merge_decl_attributes (tree olddecl, tree newdecl)
3275 {
3276   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3277                            DECL_ATTRIBUTES (newdecl));
3278 }
3279
3280 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3281
3282 /* Specialization of merge_decl_attributes for various Windows targets.
3283
3284    This handles the following situation:
3285
3286      __declspec (dllimport) int foo;
3287      int foo;
3288
3289    The second instance of `foo' nullifies the dllimport.  */
3290
3291 tree
3292 merge_dllimport_decl_attributes (tree old, tree new)
3293 {
3294   tree a;
3295   int delete_dllimport_p;
3296
3297   old = DECL_ATTRIBUTES (old);
3298   new = DECL_ATTRIBUTES (new);
3299
3300   /* What we need to do here is remove from `old' dllimport if it doesn't
3301      appear in `new'.  dllimport behaves like extern: if a declaration is
3302      marked dllimport and a definition appears later, then the object
3303      is not dllimport'd.  */
3304   if (lookup_attribute ("dllimport", old) != NULL_TREE
3305       && lookup_attribute ("dllimport", new) == NULL_TREE)
3306     delete_dllimport_p = 1;
3307   else
3308     delete_dllimport_p = 0;
3309
3310   a = merge_attributes (old, new);
3311
3312   if (delete_dllimport_p)
3313     {
3314       tree prev, t;
3315
3316       /* Scan the list for dllimport and delete it.  */
3317       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3318         {
3319           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
3320             {
3321               if (prev == NULL_TREE)
3322                 a = TREE_CHAIN (a);
3323               else
3324                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3325               break;
3326             }
3327         }
3328     }
3329
3330   return a;
3331 }
3332
3333 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3334    struct attribute_spec.handler.  */
3335
3336 tree
3337 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3338                       bool *no_add_attrs)
3339 {
3340   tree node = *pnode;
3341
3342   /* These attributes may apply to structure and union types being created,
3343      but otherwise should pass to the declaration involved.  */
3344   if (!DECL_P (node))
3345     {
3346       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3347                    | (int) ATTR_FLAG_ARRAY_NEXT))
3348         {
3349           *no_add_attrs = true;
3350           return tree_cons (name, args, NULL_TREE);
3351         }
3352       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3353         {
3354           warning (OPT_Wattributes, "%qs attribute ignored",
3355                    IDENTIFIER_POINTER (name));
3356           *no_add_attrs = true;
3357         }
3358
3359       return NULL_TREE;
3360     }
3361
3362   /* Report error on dllimport ambiguities seen now before they cause
3363      any damage.  */
3364   if (is_attribute_p ("dllimport", name))
3365     {
3366       /* Like MS, treat definition of dllimported variables and
3367          non-inlined functions on declaration as syntax errors.  We
3368          allow the attribute for function definitions if declared
3369          inline.  */
3370       if (TREE_CODE (node) == FUNCTION_DECL  && DECL_INITIAL (node)
3371           && !DECL_DECLARED_INLINE_P (node))
3372         {
3373           error ("function %q+D definition is marked dllimport", node);
3374           *no_add_attrs = true;
3375         }
3376
3377       else if (TREE_CODE (node) == VAR_DECL)
3378         {
3379           if (DECL_INITIAL (node))
3380             {
3381               error ("variable %q+D definition is marked dllimport",
3382                      node);
3383               *no_add_attrs = true;
3384             }
3385
3386           /* `extern' needn't be specified with dllimport.
3387              Specify `extern' now and hope for the best.  Sigh.  */
3388           DECL_EXTERNAL (node) = 1;
3389           /* Also, implicitly give dllimport'd variables declared within
3390              a function global scope, unless declared static.  */
3391           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3392             TREE_PUBLIC (node) = 1;
3393         }
3394     }
3395
3396   /*  Report error if symbol is not accessible at global scope.  */
3397   if (!TREE_PUBLIC (node)
3398       && (TREE_CODE (node) == VAR_DECL
3399           || TREE_CODE (node) == FUNCTION_DECL))
3400     {
3401       error ("external linkage required for symbol %q+D because of "
3402              "%qs attribute", node, IDENTIFIER_POINTER (name));
3403       *no_add_attrs = true;
3404     }
3405
3406   return NULL_TREE;
3407 }
3408
3409 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3410 \f
3411 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3412    of the various TYPE_QUAL values.  */
3413
3414 static void
3415 set_type_quals (tree type, int type_quals)
3416 {
3417   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3418   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3419   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3420 }
3421
3422 /* Returns true iff cand is equivalent to base with type_quals.  */
3423
3424 bool
3425 check_qualified_type (tree cand, tree base, int type_quals)
3426 {
3427   return (TYPE_QUALS (cand) == type_quals
3428           && TYPE_NAME (cand) == TYPE_NAME (base)
3429           /* Apparently this is needed for Objective-C.  */
3430           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3431           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3432                                    TYPE_ATTRIBUTES (base)));
3433 }
3434
3435 /* Return a version of the TYPE, qualified as indicated by the
3436    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3437    return NULL_TREE.  */
3438
3439 tree
3440 get_qualified_type (tree type, int type_quals)
3441 {
3442   tree t;
3443
3444   if (TYPE_QUALS (type) == type_quals)
3445     return type;
3446
3447   /* Search the chain of variants to see if there is already one there just
3448      like the one we need to have.  If so, use that existing one.  We must
3449      preserve the TYPE_NAME, since there is code that depends on this.  */
3450   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3451     if (check_qualified_type (t, type, type_quals))
3452       return t;
3453
3454   return NULL_TREE;
3455 }
3456
3457 /* Like get_qualified_type, but creates the type if it does not
3458    exist.  This function never returns NULL_TREE.  */
3459
3460 tree
3461 build_qualified_type (tree type, int type_quals)
3462 {
3463   tree t;
3464
3465   /* See if we already have the appropriate qualified variant.  */
3466   t = get_qualified_type (type, type_quals);
3467
3468   /* If not, build it.  */
3469   if (!t)
3470     {
3471       t = build_variant_type_copy (type);
3472       set_type_quals (t, type_quals);
3473     }
3474
3475   return t;
3476 }
3477
3478 /* Create a new distinct copy of TYPE.  The new type is made its own
3479    MAIN_VARIANT.  */
3480
3481 tree
3482 build_distinct_type_copy (tree type)
3483 {
3484   tree t = copy_node (type);
3485   
3486   TYPE_POINTER_TO (t) = 0;
3487   TYPE_REFERENCE_TO (t) = 0;
3488
3489   /* Make it its own variant.  */
3490   TYPE_MAIN_VARIANT (t) = t;
3491   TYPE_NEXT_VARIANT (t) = 0;
3492   
3493   return t;
3494 }
3495
3496 /* Create a new variant of TYPE, equivalent but distinct.
3497    This is so the caller can modify it.  */
3498
3499 tree
3500 build_variant_type_copy (tree type)
3501 {
3502   tree t, m = TYPE_MAIN_VARIANT (type);
3503
3504   t = build_distinct_type_copy (type);
3505   
3506   /* Add the new type to the chain of variants of TYPE.  */
3507   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3508   TYPE_NEXT_VARIANT (m) = t;
3509   TYPE_MAIN_VARIANT (t) = m;
3510
3511   return t;
3512 }
3513 \f
3514 /* Return true if the from tree in both tree maps are equal.  */
3515
3516 static int
3517 tree_map_eq (const void *va, const void *vb)
3518 {
3519   const struct tree_map  *a = va, *b = vb;
3520   return (a->from == b->from);
3521 }
3522
3523 /* Hash a from tree in a tree_map.  */
3524
3525 static hashval_t
3526 tree_map_hash (const void *item)
3527 {
3528   return (((const struct tree_map *) item)->hash);
3529 }
3530
3531 /* Return true if this tree map structure is marked for garbage collection
3532    purposes.  We simply return true if the from tree is marked, so that this
3533    structure goes away when the from tree goes away.  */
3534
3535 static int
3536 tree_map_marked_p (const void *p)
3537 {
3538   tree from = ((struct tree_map *) p)->from;
3539
3540   return ggc_marked_p (from);
3541 }
3542
3543 /* Print out the statistics for the DECL_DEBUG_EXPR hash table.  */
3544
3545 static void
3546 print_debug_expr_statistics (void)
3547 {
3548   fprintf (stderr, "DECL_DEBUG_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3549            (long) htab_size (debug_expr_for_decl),
3550            (long) htab_elements (debug_expr_for_decl),
3551            htab_collisions (debug_expr_for_decl));
3552 }
3553
3554 /* Print out the statistics for the DECL_VALUE_EXPR hash table.  */
3555
3556 static void
3557 print_value_expr_statistics (void)
3558 {
3559   fprintf (stderr, "DECL_VALUE_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3560            (long) htab_size (value_expr_for_decl),
3561            (long) htab_elements (value_expr_for_decl),
3562            htab_collisions (value_expr_for_decl));
3563 }
3564 /* Lookup a debug expression for FROM, and return it if we find one.  */
3565
3566 tree 
3567 decl_debug_expr_lookup (tree from)
3568 {
3569   struct tree_map *h, in;
3570   in.from = from;
3571
3572   h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
3573   if (h)
3574     return h->to;
3575   return NULL_TREE;
3576 }
3577
3578 /* Insert a mapping FROM->TO in the debug expression hashtable.  */
3579
3580 void
3581 decl_debug_expr_insert (tree from, tree to)
3582 {
3583   struct tree_map *h;
3584   void **loc;
3585
3586   h = ggc_alloc (sizeof (struct tree_map));
3587   h->hash = htab_hash_pointer (from);
3588   h->from = from;
3589   h->to = to;
3590   loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
3591   *(struct tree_map **) loc = h;
3592 }  
3593
3594 /* Lookup a value expression for FROM, and return it if we find one.  */
3595
3596 tree 
3597 decl_value_expr_lookup (tree from)
3598 {
3599   struct tree_map *h, in;
3600   in.from = from;
3601
3602   h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
3603   if (h)
3604     return h->to;
3605   return NULL_TREE;
3606 }
3607
3608 /* Insert a mapping FROM->TO in the value expression hashtable.  */
3609
3610 void
3611 decl_value_expr_insert (tree from, tree to)
3612 {
3613   struct tree_map *h;
3614   void **loc;
3615
3616   h = ggc_alloc (sizeof (struct tree_map));
3617   h->hash = htab_hash_pointer (from);
3618   h->from = from;
3619   h->to = to;
3620   loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
3621   *(struct tree_map **) loc = h;
3622 }
3623
3624 /* Hashing of types so that we don't make duplicates.
3625    The entry point is `type_hash_canon'.  */
3626
3627 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3628    with types in the TREE_VALUE slots), by adding the hash codes
3629    of the individual types.  */
3630
3631 unsigned int
3632 type_hash_list (tree list, hashval_t hashcode)
3633 {
3634   tree tail;
3635
3636   for (tail = list; tail; tail = TREE_CHAIN (tail))
3637     if (TREE_VALUE (tail) != error_mark_node)
3638       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3639                                         hashcode);
3640
3641   return hashcode;
3642 }
3643
3644 /* These are the Hashtable callback functions.  */
3645
3646 /* Returns true iff the types are equivalent.  */
3647
3648 static int
3649 type_hash_eq (const void *va, const void *vb)
3650 {
3651   const struct type_hash *a = va, *b = vb;
3652
3653   /* First test the things that are the same for all types.  */
3654   if (a->hash != b->hash
3655       || TREE_CODE (a->type) != TREE_CODE (b->type)
3656       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
3657       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3658                                  TYPE_ATTRIBUTES (b->type))
3659       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
3660       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
3661     return 0;
3662
3663   switch (TREE_CODE (a->type))
3664     {
3665     case VOID_TYPE:
3666     case COMPLEX_TYPE:
3667     case POINTER_TYPE:
3668     case REFERENCE_TYPE:
3669       return 1;
3670
3671     case VECTOR_TYPE:
3672       return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
3673
3674     case ENUMERAL_TYPE:
3675       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
3676           && !(TYPE_VALUES (a->type)
3677                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
3678                && TYPE_VALUES (b->type)
3679                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
3680                && type_list_equal (TYPE_VALUES (a->type),
3681                                    TYPE_VALUES (b->type))))
3682         return 0;
3683
3684       /* ... fall through ... */
3685
3686     case INTEGER_TYPE:
3687     case REAL_TYPE:
3688     case BOOLEAN_TYPE:
3689     case CHAR_TYPE:
3690       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3691                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3692                                       TYPE_MAX_VALUE (b->type)))
3693               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3694                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3695                                          TYPE_MIN_VALUE (b->type))));
3696
3697     case OFFSET_TYPE:
3698       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
3699
3700     case METHOD_TYPE:
3701       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
3702               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3703                   || (TYPE_ARG_TYPES (a->type)
3704                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3705                       && TYPE_ARG_TYPES (b->type)
3706                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3707                       && type_list_equal (TYPE_ARG_TYPES (a->type),
3708                                           TYPE_ARG_TYPES (b->type)))));
3709
3710     case ARRAY_TYPE:
3711       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
3712
3713     case RECORD_TYPE:
3714     case UNION_TYPE:
3715     case QUAL_UNION_TYPE:
3716       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
3717               || (TYPE_FIELDS (a->type)
3718                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
3719                   && TYPE_FIELDS (b->type)
3720                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
3721                   && type_list_equal (TYPE_FIELDS (a->type),
3722                                       TYPE_FIELDS (b->type))));
3723
3724     case FUNCTION_TYPE:
3725       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3726               || (TYPE_ARG_TYPES (a->type)
3727                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3728                   && TYPE_ARG_TYPES (b->type)
3729                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3730                   && type_list_equal (TYPE_ARG_TYPES (a->type),
3731                                       TYPE_ARG_TYPES (b->type))));
3732
3733     default:
3734       return 0;
3735     }
3736 }
3737
3738 /* Return the cached hash value.  */
3739
3740 static hashval_t
3741 type_hash_hash (const void *item)
3742 {
3743   return ((const struct type_hash *) item)->hash;
3744 }
3745
3746 /* Look in the type hash table for a type isomorphic to TYPE.
3747    If one is found, return it.  Otherwise return 0.  */
3748
3749 tree
3750 type_hash_lookup (hashval_t hashcode, tree type)
3751 {
3752   struct type_hash *h, in;
3753
3754   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3755      must call that routine before comparing TYPE_ALIGNs.  */
3756   layout_type (type);
3757
3758   in.hash = hashcode;
3759   in.type = type;
3760
3761   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3762   if (h)
3763     return h->type;
3764   return NULL_TREE;
3765 }
3766
3767 /* Add an entry to the type-hash-table
3768    for a type TYPE whose hash code is HASHCODE.  */
3769
3770 void
3771 type_hash_add (hashval_t hashcode, tree type)
3772 {
3773   struct type_hash *h;
3774   void **loc;
3775
3776   h = ggc_alloc (sizeof (struct type_hash));
3777   h->hash = hashcode;
3778   h->type = type;
3779   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3780   *(struct type_hash **) loc = h;
3781 }
3782
3783 /* Given TYPE, and HASHCODE its hash code, return the canonical
3784    object for an identical type if one already exists.
3785    Otherwise, return TYPE, and record it as the canonical object.
3786
3787    To use this function, first create a type of the sort you want.
3788    Then compute its hash code from the fields of the type that
3789    make it different from other similar types.
3790    Then call this function and use the value.  */
3791
3792 tree
3793 type_hash_canon (unsigned int hashcode, tree type)
3794 {
3795   tree t1;
3796
3797   /* The hash table only contains main variants, so ensure that's what we're
3798      being passed.  */
3799   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
3800
3801   if (!lang_hooks.types.hash_types)
3802     return type;
3803
3804   /* See if the type is in the hash table already.  If so, return it.
3805      Otherwise, add the type.  */
3806   t1 = type_hash_lookup (hashcode, type);
3807   if (t1 != 0)
3808     {
3809 #ifdef GATHER_STATISTICS
3810       tree_node_counts[(int) t_kind]--;
3811       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3812 #endif
3813       return t1;
3814     }
3815   else
3816     {
3817       type_hash_add (hashcode, type);
3818       return type;
3819     }
3820 }
3821
3822 /* See if the data pointed to by the type hash table is marked.  We consider
3823    it marked if the type is marked or if a debug type number or symbol
3824    table entry has been made for the type.  This reduces the amount of
3825    debugging output and eliminates that dependency of the debug output on
3826    the number of garbage collections.  */
3827
3828 static int
3829 type_hash_marked_p (const void *p)
3830 {
3831   tree type = ((struct type_hash *) p)->type;
3832
3833   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3834 }
3835
3836 static void
3837 print_type_hash_statistics (void)
3838 {
3839   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3840            (long) htab_size (type_hash_table),
3841            (long) htab_elements (type_hash_table),
3842            htab_collisions (type_hash_table));
3843 }
3844
3845 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3846    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3847    by adding the hash codes of the individual attributes.  */
3848
3849 unsigned int
3850 attribute_hash_list (tree list, hashval_t hashcode)
3851 {
3852   tree tail;
3853
3854   for (tail = list; tail; tail = TREE_CHAIN (tail))
3855     /* ??? Do we want to add in TREE_VALUE too? */
3856     hashcode = iterative_hash_object
3857       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
3858   return hashcode;
3859 }
3860
3861 /* Given two lists of attributes, return true if list l2 is
3862    equivalent to l1.  */
3863
3864 int
3865 attribute_list_equal (tree l1, tree l2)
3866 {
3867   return attribute_list_contained (l1, l2)
3868          && attribute_list_contained (l2, l1);
3869 }
3870
3871 /* Given two lists of attributes, return true if list L2 is
3872    completely contained within L1.  */
3873 /* ??? This would be faster if attribute names were stored in a canonicalized
3874    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3875    must be used to show these elements are equivalent (which they are).  */
3876 /* ??? It's not clear that attributes with arguments will always be handled
3877    correctly.  */
3878
3879 int
3880 attribute_list_contained (tree l1, tree l2)
3881 {
3882   tree t1, t2;
3883
3884   /* First check the obvious, maybe the lists are identical.  */
3885   if (l1 == l2)
3886     return 1;
3887
3888   /* Maybe the lists are similar.  */
3889   for (t1 = l1, t2 = l2;
3890        t1 != 0 && t2 != 0
3891         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3892         && TREE_VALUE (t1) == TREE_VALUE (t2);
3893        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3894
3895   /* Maybe the lists are equal.  */
3896   if (t1 == 0 && t2 == 0)
3897     return 1;
3898
3899   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3900     {
3901       tree attr;
3902       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3903            attr != NULL_TREE;
3904            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3905                                     TREE_CHAIN (attr)))
3906         {
3907           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3908             break;
3909         }
3910
3911       if (attr == 0)
3912         return 0;
3913
3914       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3915         return 0;
3916     }
3917
3918   return 1;
3919 }
3920
3921 /* Given two lists of types
3922    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3923    return 1 if the lists contain the same types in the same order.
3924    Also, the TREE_PURPOSEs must match.  */
3925
3926 int
3927 type_list_equal (tree l1, tree l2)
3928 {
3929   tree t1, t2;
3930
3931   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3932     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3933         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3934             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3935                   && (TREE_TYPE (TREE_PURPOSE (t1))
3936                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3937       return 0;
3938
3939   return t1 == t2;
3940 }
3941
3942 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3943    given by TYPE.  If the argument list accepts variable arguments,
3944    then this function counts only the ordinary arguments.  */
3945
3946 int
3947 type_num_arguments (tree type)
3948 {
3949   int i = 0;
3950   tree t;
3951
3952   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3953     /* If the function does not take a variable number of arguments,
3954        the last element in the list will have type `void'.  */
3955     if (VOID_TYPE_P (TREE_VALUE (t)))
3956       break;
3957     else
3958       ++i;
3959
3960   return i;
3961 }
3962
3963 /* Nonzero if integer constants T1 and T2
3964    represent the same constant value.  */
3965
3966 int
3967 tree_int_cst_equal (tree t1, tree t2)
3968 {
3969   if (t1 == t2)
3970     return 1;
3971
3972   if (t1 == 0 || t2 == 0)
3973     return 0;
3974
3975   if (TREE_CODE (t1) == INTEGER_CST
3976       && TREE_CODE (t2) == INTEGER_CST
3977       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3978       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3979     return 1;
3980
3981   return 0;
3982 }
3983
3984 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3985    The precise way of comparison depends on their data type.  */
3986
3987 int
3988 tree_int_cst_lt (tree t1, tree t2)
3989 {
3990   if (t1 == t2)
3991     return 0;
3992
3993   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
3994     {
3995       int t1_sgn = tree_int_cst_sgn (t1);
3996       int t2_sgn = tree_int_cst_sgn (t2);
3997
3998       if (t1_sgn < t2_sgn)
3999         return 1;
4000       else if (t1_sgn > t2_sgn)
4001         return 0;
4002       /* Otherwise, both are non-negative, so we compare them as
4003          unsigned just in case one of them would overflow a signed
4004          type.  */
4005     }
4006   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4007     return INT_CST_LT (t1, t2);
4008
4009   return INT_CST_LT_UNSIGNED (t1, t2);
4010 }
4011
4012 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
4013
4014 int
4015 tree_int_cst_compare (tree t1, tree t2)
4016 {
4017   if (tree_int_cst_lt (t1, t2))
4018     return -1;
4019   else if (tree_int_cst_lt (t2, t1))
4020     return 1;
4021   else
4022     return 0;
4023 }
4024
4025 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4026    the host.  If POS is zero, the value can be represented in a single
4027    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
4028    be represented in a single unsigned HOST_WIDE_INT.  */
4029
4030 int
4031 host_integerp (tree t, int pos)
4032 {
4033   return (TREE_CODE (t) == INTEGER_CST
4034           && ! TREE_OVERFLOW (t)
4035           && ((TREE_INT_CST_HIGH (t) == 0
4036                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4037               || (! pos && TREE_INT_CST_HIGH (t) == -1
4038                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4039                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
4040               || (pos && TREE_INT_CST_HIGH (t) == 0)));
4041 }
4042
4043 /* Return the HOST_WIDE_INT least significant bits of T if it is an
4044    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
4045    be positive.  We must be able to satisfy the above conditions.  */
4046
4047 HOST_WIDE_INT
4048 tree_low_cst (tree t, int pos)
4049 {
4050   gcc_assert (host_integerp (t, pos));
4051   return TREE_INT_CST_LOW (t);
4052 }
4053
4054 /* Return the most significant bit of the integer constant T.  */
4055
4056 int
4057 tree_int_cst_msb (tree t)
4058 {
4059   int prec;
4060   HOST_WIDE_INT h;
4061   unsigned HOST_WIDE_INT l;
4062
4063   /* Note that using TYPE_PRECISION here is wrong.  We care about the
4064      actual bits, not the (arbitrary) range of the type.  */
4065   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
4066   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
4067                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
4068   return (l & 1) == 1;
4069 }
4070
4071 /* Return an indication of the sign of the integer constant T.
4072    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
4073    Note that -1 will never be returned it T's type is unsigned.  */
4074
4075 int
4076 tree_int_cst_sgn (tree t)
4077 {
4078   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
4079     return 0;
4080   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
4081     return 1;
4082   else if (TREE_INT_CST_HIGH (t) < 0)
4083     return -1;
4084   else
4085     return 1;
4086 }
4087
4088 /* Compare two constructor-element-type constants.  Return 1 if the lists
4089    are known to be equal; otherwise return 0.  */
4090
4091 int
4092 simple_cst_list_equal (tree l1, tree l2)
4093 {
4094   while (l1 != NULL_TREE && l2 != NULL_TREE)
4095     {
4096       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
4097         return 0;
4098
4099       l1 = TREE_CHAIN (l1);
4100       l2 = TREE_CHAIN (l2);
4101     }
4102
4103   return l1 == l2;
4104 }
4105
4106 /* Return truthvalue of whether T1 is the same tree structure as T2.
4107    Return 1 if they are the same.
4108    Return 0 if they are understandably different.
4109    Return -1 if either contains tree structure not understood by
4110    this function.  */
4111
4112 int
4113 simple_cst_equal (tree t1, tree t2)
4114 {
4115   enum tree_code code1, code2;
4116   int cmp;
4117   int i;
4118
4119   if (t1 == t2)
4120     return 1;
4121   if (t1 == 0 || t2 == 0)
4122     return 0;
4123
4124   code1 = TREE_CODE (t1);
4125   code2 = TREE_CODE (t2);
4126
4127   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
4128     {
4129       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4130           || code2 == NON_LVALUE_EXPR)
4131         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4132       else
4133         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
4134     }
4135
4136   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4137            || code2 == NON_LVALUE_EXPR)
4138     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
4139
4140   if (code1 != code2)
4141     return 0;
4142
4143   switch (code1)
4144     {
4145     case INTEGER_CST:
4146       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4147               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
4148
4149     case REAL_CST:
4150       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
4151
4152     case STRING_CST:
4153       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
4154               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
4155                          TREE_STRING_LENGTH (t1)));
4156
4157     case CONSTRUCTOR:
4158       return simple_cst_list_equal (CONSTRUCTOR_ELTS (t1),
4159                                     CONSTRUCTOR_ELTS (t2));
4160
4161     case SAVE_EXPR:
4162       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4163
4164     case CALL_EXPR:
4165       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4166       if (cmp <= 0)
4167         return cmp;
4168       return
4169         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4170
4171     case TARGET_EXPR:
4172       /* Special case: if either target is an unallocated VAR_DECL,
4173          it means that it's going to be unified with whatever the
4174          TARGET_EXPR is really supposed to initialize, so treat it
4175          as being equivalent to anything.  */
4176       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
4177            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
4178            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
4179           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
4180               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
4181               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
4182         cmp = 1;
4183       else
4184         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4185
4186       if (cmp <= 0)
4187         return cmp;
4188
4189       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4190
4191     case WITH_CLEANUP_EXPR:
4192       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4193       if (cmp <= 0)
4194         return cmp;
4195
4196       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
4197
4198     case COMPONENT_REF:
4199       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
4200         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4201
4202       return 0;
4203
4204     case VAR_DECL:
4205     case PARM_DECL:
4206     case CONST_DECL:
4207     case FUNCTION_DECL:
4208       return 0;
4209
4210     default:
4211       break;
4212     }
4213
4214   /* This general rule works for most tree codes.  All exceptions should be
4215      handled above.  If this is a language-specific tree code, we can't
4216      trust what might be in the operand, so say we don't know
4217      the situation.  */
4218   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
4219     return -1;
4220
4221   switch (TREE_CODE_CLASS (code1))
4222     {
4223     case tcc_unary:
4224     case tcc_binary:
4225     case tcc_comparison:
4226     case tcc_expression:
4227     case tcc_reference:
4228     case tcc_statement:
4229       cmp = 1;
4230       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
4231         {
4232           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
4233           if (cmp <= 0)
4234             return cmp;
4235         }
4236
4237       return cmp;
4238
4239     default:
4240       return -1;
4241     }
4242 }
4243
4244 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
4245    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
4246    than U, respectively.  */
4247
4248 int
4249 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
4250 {
4251   if (tree_int_cst_sgn (t) < 0)
4252     return -1;
4253   else if (TREE_INT_CST_HIGH (t) != 0)
4254     return 1;
4255   else if (TREE_INT_CST_LOW (t) == u)
4256     return 0;
4257   else if (TREE_INT_CST_LOW (t) < u)
4258     return -1;
4259   else
4260     return 1;
4261 }
4262
4263 /* Return true if CODE represents an associative tree code.  Otherwise
4264    return false.  */
4265 bool
4266 associative_tree_code (enum tree_code code)
4267 {
4268   switch (code)
4269     {
4270     case BIT_IOR_EXPR:
4271     case BIT_AND_EXPR:
4272     case BIT_XOR_EXPR:
4273     case PLUS_EXPR:
4274     case MULT_EXPR:
4275     case MIN_EXPR:
4276     case MAX_EXPR:
4277       return true;
4278
4279     default:
4280       break;
4281     }
4282   return false;
4283 }
4284
4285 /* Return true if CODE represents a commutative tree code.  Otherwise
4286    return false.  */
4287 bool
4288 commutative_tree_code (enum tree_code code)
4289 {
4290   switch (code)
4291     {
4292     case PLUS_EXPR:
4293     case MULT_EXPR:
4294     case MIN_EXPR:
4295     case MAX_EXPR:
4296     case BIT_IOR_EXPR:
4297     case BIT_XOR_EXPR:
4298     case BIT_AND_EXPR:
4299     case NE_EXPR:
4300     case EQ_EXPR:
4301     case UNORDERED_EXPR:
4302     case ORDERED_EXPR:
4303     case UNEQ_EXPR:
4304     case LTGT_EXPR:
4305     case TRUTH_AND_EXPR:
4306     case TRUTH_XOR_EXPR:
4307     case TRUTH_OR_EXPR:
4308       return true;
4309
4310     default:
4311       break;
4312     }
4313   return false;
4314 }
4315
4316 /* Generate a hash value for an expression.  This can be used iteratively
4317    by passing a previous result as the "val" argument.
4318
4319    This function is intended to produce the same hash for expressions which
4320    would compare equal using operand_equal_p.  */
4321
4322 hashval_t
4323 iterative_hash_expr (tree t, hashval_t val)
4324 {
4325   int i;
4326   enum tree_code code;
4327   char class;
4328
4329   if (t == NULL_TREE)
4330     return iterative_hash_pointer (t, val);
4331
4332   code = TREE_CODE (t);
4333
4334   switch (code)
4335     {
4336     /* Alas, constants aren't shared, so we can't rely on pointer
4337        identity.  */
4338     case INTEGER_CST:
4339       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4340       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4341     case REAL_CST:
4342       {
4343         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4344
4345         return iterative_hash_hashval_t (val2, val);
4346       }
4347     case STRING_CST:
4348       return iterative_hash (TREE_STRING_POINTER (t),
4349                              TREE_STRING_LENGTH (t), val);
4350     case COMPLEX_CST:
4351       val = iterative_hash_expr (TREE_REALPART (t), val);
4352       return iterative_hash_expr (TREE_IMAGPART (t), val);
4353     case VECTOR_CST:
4354       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4355
4356     case SSA_NAME:
4357     case VALUE_HANDLE:
4358       /* we can just compare by pointer.  */
4359       return iterative_hash_pointer (t, val);
4360
4361     case TREE_LIST:
4362       /* A list of expressions, for a CALL_EXPR or as the elements of a
4363          VECTOR_CST.  */
4364       for (; t; t = TREE_CHAIN (t))
4365         val = iterative_hash_expr (TREE_VALUE (t), val);
4366       return val;
4367     case FUNCTION_DECL:
4368       /* When referring to a built-in FUNCTION_DECL, use the
4369          __builtin__ form.  Otherwise nodes that compare equal
4370          according to operand_equal_p might get different
4371          hash codes.  */
4372       if (DECL_BUILT_IN (t))
4373         {
4374           val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)], 
4375                                       val);
4376           return val;
4377         }
4378       /* else FALL THROUGH */
4379     default:
4380       class = TREE_CODE_CLASS (code);
4381
4382       if (class == tcc_declaration)
4383         {
4384           /* Otherwise, we can just compare decls by pointer.  */
4385           val = iterative_hash_pointer (t, val);
4386         }
4387       else
4388         {
4389           gcc_assert (IS_EXPR_CODE_CLASS (class));
4390           
4391           val = iterative_hash_object (code, val);
4392
4393           /* Don't hash the type, that can lead to having nodes which
4394              compare equal according to operand_equal_p, but which
4395              have different hash codes.  */
4396           if (code == NOP_EXPR
4397               || code == CONVERT_EXPR
4398               || code == NON_LVALUE_EXPR)
4399             {
4400               /* Make sure to include signness in the hash computation.  */
4401               val += TYPE_UNSIGNED (TREE_TYPE (t));
4402               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4403             }
4404
4405           else if (commutative_tree_code (code))
4406             {
4407               /* It's a commutative expression.  We want to hash it the same
4408                  however it appears.  We do this by first hashing both operands
4409                  and then rehashing based on the order of their independent
4410                  hashes.  */
4411               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4412               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4413               hashval_t t;
4414
4415               if (one > two)
4416                 t = one, one = two, two = t;
4417
4418               val = iterative_hash_hashval_t (one, val);
4419               val = iterative_hash_hashval_t (two, val);
4420             }
4421           else
4422             for (i = TREE_CODE_LENGTH (code) - 1; i >= 0; --i)
4423               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4424         }
4425       return val;
4426       break;
4427     }
4428 }
4429 \f
4430 /* Constructors for pointer, array and function types.
4431    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4432    constructed by language-dependent code, not here.)  */
4433
4434 /* Construct, lay out and return the type of pointers to TO_TYPE with
4435    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4436    reference all of memory. If such a type has already been
4437    constructed, reuse it.  */
4438
4439 tree
4440 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4441                              bool can_alias_all)
4442 {
4443   tree t;
4444
4445   /* In some cases, languages will have things that aren't a POINTER_TYPE
4446      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4447      In that case, return that type without regard to the rest of our
4448      operands.
4449
4450      ??? This is a kludge, but consistent with the way this function has
4451      always operated and there doesn't seem to be a good way to avoid this
4452      at the moment.  */
4453   if (TYPE_POINTER_TO (to_type) != 0
4454       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4455     return TYPE_POINTER_TO (to_type);
4456
4457   /* First, if we already have a type for pointers to TO_TYPE and it's
4458      the proper mode, use it.  */
4459   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4460     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4461       return t;
4462
4463   t = make_node (POINTER_TYPE);
4464
4465   TREE_TYPE (t) = to_type;
4466   TYPE_MODE (t) = mode;
4467   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4468   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4469   TYPE_POINTER_TO (to_type) = t;
4470
4471   /* Lay out the type.  This function has many callers that are concerned