OSDN Git Service

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