OSDN Git Service

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