OSDN Git Service

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