OSDN Git Service

09a963304632474367607b9bde8e2470552fea0c
[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; }
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     };
2770   return xloc;
2771 }
2772
2773 #else
2774
2775 /* Record the exact location where an expression or an identifier were
2776    encountered.  */
2777
2778 void
2779 annotate_with_file_line (tree node, const char *file, int line)
2780 {
2781   /* Roughly one percent of the calls to this function are to annotate
2782      a node with the same information already attached to that node!
2783      Just return instead of wasting memory.  */
2784   if (EXPR_LOCUS (node)
2785       && (EXPR_FILENAME (node) == file
2786           || ! strcmp (EXPR_FILENAME (node), file))
2787       && EXPR_LINENO (node) == line)
2788     {
2789       last_annotated_node = node;
2790       return;
2791     }
2792
2793   /* In heavily macroized code (such as GCC itself) this single
2794      entry cache can reduce the number of allocations by more
2795      than half.  */
2796   if (last_annotated_node
2797       && EXPR_LOCUS (last_annotated_node)
2798       && (EXPR_FILENAME (last_annotated_node) == file
2799           || ! strcmp (EXPR_FILENAME (last_annotated_node), file))
2800       && EXPR_LINENO (last_annotated_node) == line)
2801     {
2802       SET_EXPR_LOCUS (node, EXPR_LOCUS (last_annotated_node));
2803       return;
2804     }
2805
2806   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
2807   EXPR_LINENO (node) = line;
2808   EXPR_FILENAME (node) = file;
2809   last_annotated_node = node;
2810 }
2811
2812 void
2813 annotate_with_locus (tree node, location_t locus)
2814 {
2815   annotate_with_file_line (node, locus.file, locus.line);
2816 }
2817 #endif
2818 \f
2819 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2820    is ATTRIBUTE.  */
2821
2822 tree
2823 build_decl_attribute_variant (tree ddecl, tree attribute)
2824 {
2825   DECL_ATTRIBUTES (ddecl) = attribute;
2826   return ddecl;
2827 }
2828
2829 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2830    is ATTRIBUTE.
2831
2832    Record such modified types already made so we don't make duplicates.  */
2833
2834 tree
2835 build_type_attribute_variant (tree ttype, tree attribute)
2836 {
2837   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2838     {
2839       hashval_t hashcode = 0;
2840       tree ntype;
2841       enum tree_code code = TREE_CODE (ttype);
2842
2843       ntype = copy_node (ttype);
2844
2845       TYPE_POINTER_TO (ntype) = 0;
2846       TYPE_REFERENCE_TO (ntype) = 0;
2847       TYPE_ATTRIBUTES (ntype) = attribute;
2848
2849       /* Create a new main variant of TYPE.  */
2850       TYPE_MAIN_VARIANT (ntype) = ntype;
2851       TYPE_NEXT_VARIANT (ntype) = 0;
2852       set_type_quals (ntype, TYPE_UNQUALIFIED);
2853
2854       hashcode = iterative_hash_object (code, hashcode);
2855       if (TREE_TYPE (ntype))
2856         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
2857                                           hashcode);
2858       hashcode = attribute_hash_list (attribute, hashcode);
2859
2860       switch (TREE_CODE (ntype))
2861         {
2862         case FUNCTION_TYPE:
2863           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
2864           break;
2865         case ARRAY_TYPE:
2866           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
2867                                             hashcode);
2868           break;
2869         case INTEGER_TYPE:
2870           hashcode = iterative_hash_object
2871             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
2872           hashcode = iterative_hash_object
2873             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
2874           break;
2875         case REAL_TYPE:
2876           {
2877             unsigned int precision = TYPE_PRECISION (ntype);
2878             hashcode = iterative_hash_object (precision, hashcode);
2879           }
2880           break;
2881         default:
2882           break;
2883         }
2884
2885       ntype = type_hash_canon (hashcode, ntype);
2886       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
2887     }
2888
2889   return ttype;
2890 }
2891
2892 /* Return nonzero if IDENT is a valid name for attribute ATTR,
2893    or zero if not.
2894
2895    We try both `text' and `__text__', ATTR may be either one.  */
2896 /* ??? It might be a reasonable simplification to require ATTR to be only
2897    `text'.  One might then also require attribute lists to be stored in
2898    their canonicalized form.  */
2899
2900 int
2901 is_attribute_p (const char *attr, tree ident)
2902 {
2903   int ident_len, attr_len;
2904   const char *p;
2905
2906   if (TREE_CODE (ident) != IDENTIFIER_NODE)
2907     return 0;
2908
2909   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
2910     return 1;
2911
2912   p = IDENTIFIER_POINTER (ident);
2913   ident_len = strlen (p);
2914   attr_len = strlen (attr);
2915
2916   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
2917   if (attr[0] == '_')
2918     {
2919       if (attr[1] != '_'
2920           || attr[attr_len - 2] != '_'
2921           || attr[attr_len - 1] != '_')
2922         abort ();
2923       if (ident_len == attr_len - 4
2924           && strncmp (attr + 2, p, attr_len - 4) == 0)
2925         return 1;
2926     }
2927   else
2928     {
2929       if (ident_len == attr_len + 4
2930           && p[0] == '_' && p[1] == '_'
2931           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
2932           && strncmp (attr, p + 2, attr_len) == 0)
2933         return 1;
2934     }
2935
2936   return 0;
2937 }
2938
2939 /* Given an attribute name and a list of attributes, return a pointer to the
2940    attribute's list element if the attribute is part of the list, or NULL_TREE
2941    if not found.  If the attribute appears more than once, this only
2942    returns the first occurrence; the TREE_CHAIN of the return value should
2943    be passed back in if further occurrences are wanted.  */
2944
2945 tree
2946 lookup_attribute (const char *attr_name, tree list)
2947 {
2948   tree l;
2949
2950   for (l = list; l; l = TREE_CHAIN (l))
2951     {
2952       if (TREE_CODE (TREE_PURPOSE (l)) != IDENTIFIER_NODE)
2953         abort ();
2954       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
2955         return l;
2956     }
2957
2958   return NULL_TREE;
2959 }
2960
2961 /* Return an attribute list that is the union of a1 and a2.  */
2962
2963 tree
2964 merge_attributes (tree a1, tree a2)
2965 {
2966   tree attributes;
2967
2968   /* Either one unset?  Take the set one.  */
2969
2970   if ((attributes = a1) == 0)
2971     attributes = a2;
2972
2973   /* One that completely contains the other?  Take it.  */
2974
2975   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
2976     {
2977       if (attribute_list_contained (a2, a1))
2978         attributes = a2;
2979       else
2980         {
2981           /* Pick the longest list, and hang on the other list.  */
2982
2983           if (list_length (a1) < list_length (a2))
2984             attributes = a2, a2 = a1;
2985
2986           for (; a2 != 0; a2 = TREE_CHAIN (a2))
2987             {
2988               tree a;
2989               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2990                                          attributes);
2991                    a != NULL_TREE;
2992                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2993                                          TREE_CHAIN (a)))
2994                 {
2995                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
2996                     break;
2997                 }
2998               if (a == NULL_TREE)
2999                 {
3000                   a1 = copy_node (a2);
3001                   TREE_CHAIN (a1) = attributes;
3002                   attributes = a1;
3003                 }
3004             }
3005         }
3006     }
3007   return attributes;
3008 }
3009
3010 /* Given types T1 and T2, merge their attributes and return
3011   the result.  */
3012
3013 tree
3014 merge_type_attributes (tree t1, tree t2)
3015 {
3016   return merge_attributes (TYPE_ATTRIBUTES (t1),
3017                            TYPE_ATTRIBUTES (t2));
3018 }
3019
3020 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3021    the result.  */
3022
3023 tree
3024 merge_decl_attributes (tree olddecl, tree newdecl)
3025 {
3026   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3027                            DECL_ATTRIBUTES (newdecl));
3028 }
3029
3030 #ifdef TARGET_DLLIMPORT_DECL_ATTRIBUTES
3031
3032 /* Specialization of merge_decl_attributes for various Windows targets.
3033
3034    This handles the following situation:
3035
3036      __declspec (dllimport) int foo;
3037      int foo;
3038
3039    The second instance of `foo' nullifies the dllimport.  */
3040
3041 tree
3042 merge_dllimport_decl_attributes (tree old, tree new)
3043 {
3044   tree a;
3045   int delete_dllimport_p;
3046
3047   old = DECL_ATTRIBUTES (old);
3048   new = DECL_ATTRIBUTES (new);
3049
3050   /* What we need to do here is remove from `old' dllimport if it doesn't
3051      appear in `new'.  dllimport behaves like extern: if a declaration is
3052      marked dllimport and a definition appears later, then the object
3053      is not dllimport'd.  */
3054   if (lookup_attribute ("dllimport", old) != NULL_TREE
3055       && lookup_attribute ("dllimport", new) == NULL_TREE)
3056     delete_dllimport_p = 1;
3057   else
3058     delete_dllimport_p = 0;
3059
3060   a = merge_attributes (old, new);
3061
3062   if (delete_dllimport_p)
3063     {
3064       tree prev, t;
3065
3066       /* Scan the list for dllimport and delete it.  */
3067       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3068         {
3069           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
3070             {
3071               if (prev == NULL_TREE)
3072                 a = TREE_CHAIN (a);
3073               else
3074                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3075               break;
3076             }
3077         }
3078     }
3079
3080   return a;
3081 }
3082
3083 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3084 \f
3085 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3086    of the various TYPE_QUAL values.  */
3087
3088 static void
3089 set_type_quals (tree type, int type_quals)
3090 {
3091   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3092   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3093   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3094 }
3095
3096 /* Returns true iff cand is equivalent to base with type_quals.  */
3097
3098 bool
3099 check_qualified_type (tree cand, tree base, int type_quals)
3100 {
3101   return (TYPE_QUALS (cand) == type_quals
3102           && TYPE_NAME (cand) == TYPE_NAME (base)
3103           /* Apparently this is needed for Objective-C.  */
3104           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3105           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3106                                    TYPE_ATTRIBUTES (base)));
3107 }
3108
3109 /* Return a version of the TYPE, qualified as indicated by the
3110    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3111    return NULL_TREE.  */
3112
3113 tree
3114 get_qualified_type (tree type, int type_quals)
3115 {
3116   tree t;
3117
3118   if (TYPE_QUALS (type) == type_quals)
3119     return type;
3120
3121   /* Search the chain of variants to see if there is already one there just
3122      like the one we need to have.  If so, use that existing one.  We must
3123      preserve the TYPE_NAME, since there is code that depends on this.  */
3124   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3125     if (check_qualified_type (t, type, type_quals))
3126       return t;
3127
3128   return NULL_TREE;
3129 }
3130
3131 /* Like get_qualified_type, but creates the type if it does not
3132    exist.  This function never returns NULL_TREE.  */
3133
3134 tree
3135 build_qualified_type (tree type, int type_quals)
3136 {
3137   tree t;
3138
3139   /* See if we already have the appropriate qualified variant.  */
3140   t = get_qualified_type (type, type_quals);
3141
3142   /* If not, build it.  */
3143   if (!t)
3144     {
3145       t = build_type_copy (type);
3146       set_type_quals (t, type_quals);
3147     }
3148
3149   return t;
3150 }
3151
3152 /* Create a new variant of TYPE, equivalent but distinct.
3153    This is so the caller can modify it.  */
3154
3155 tree
3156 build_type_copy (tree type)
3157 {
3158   tree t, m = TYPE_MAIN_VARIANT (type);
3159
3160   t = copy_node (type);
3161
3162   TYPE_POINTER_TO (t) = 0;
3163   TYPE_REFERENCE_TO (t) = 0;
3164
3165   /* Add this type to the chain of variants of TYPE.  */
3166   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3167   TYPE_NEXT_VARIANT (m) = t;
3168
3169   return t;
3170 }
3171 \f
3172 /* Hashing of types so that we don't make duplicates.
3173    The entry point is `type_hash_canon'.  */
3174
3175 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3176    with types in the TREE_VALUE slots), by adding the hash codes
3177    of the individual types.  */
3178
3179 unsigned int
3180 type_hash_list (tree list, hashval_t hashcode)
3181 {
3182   tree tail;
3183
3184   for (tail = list; tail; tail = TREE_CHAIN (tail))
3185     if (TREE_VALUE (tail) != error_mark_node)
3186       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3187                                         hashcode);
3188
3189   return hashcode;
3190 }
3191
3192 /* These are the Hashtable callback functions.  */
3193
3194 /* Returns true iff the types are equivalent.  */
3195
3196 static int
3197 type_hash_eq (const void *va, const void *vb)
3198 {
3199   const struct type_hash *a = va, *b = vb;
3200
3201   /* First test the things that are the same for all types.  */
3202   if (a->hash != b->hash
3203       || TREE_CODE (a->type) != TREE_CODE (b->type)
3204       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
3205       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3206                                  TYPE_ATTRIBUTES (b->type))
3207       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
3208       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
3209     return 0;
3210
3211   switch (TREE_CODE (a->type))
3212     {
3213     case VOID_TYPE:
3214     case COMPLEX_TYPE:
3215     case VECTOR_TYPE:
3216     case POINTER_TYPE:
3217     case REFERENCE_TYPE:
3218       return 1;
3219
3220     case ENUMERAL_TYPE:
3221       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
3222           && !(TYPE_VALUES (a->type)
3223                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
3224                && TYPE_VALUES (b->type)
3225                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
3226                && type_list_equal (TYPE_VALUES (a->type),
3227                                    TYPE_VALUES (b->type))))
3228         return 0;
3229
3230       /* ... fall through ... */
3231
3232     case INTEGER_TYPE:
3233     case REAL_TYPE:
3234     case BOOLEAN_TYPE:
3235     case CHAR_TYPE:
3236       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3237                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3238                                       TYPE_MAX_VALUE (b->type)))
3239               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3240                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3241                                          TYPE_MIN_VALUE (b->type))));
3242
3243     case OFFSET_TYPE:
3244       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
3245
3246     case METHOD_TYPE:
3247       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
3248               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3249                   || (TYPE_ARG_TYPES (a->type)
3250                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3251                       && TYPE_ARG_TYPES (b->type)
3252                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3253                       && type_list_equal (TYPE_ARG_TYPES (a->type),
3254                                           TYPE_ARG_TYPES (b->type)))));
3255                                                                       
3256     case ARRAY_TYPE:
3257     case SET_TYPE:
3258       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
3259
3260     case RECORD_TYPE:
3261     case UNION_TYPE:
3262     case QUAL_UNION_TYPE:
3263       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
3264               || (TYPE_FIELDS (a->type)
3265                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
3266                   && TYPE_FIELDS (b->type)
3267                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
3268                   && type_list_equal (TYPE_FIELDS (a->type),
3269                                       TYPE_FIELDS (b->type))));
3270
3271     case FUNCTION_TYPE:
3272       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3273               || (TYPE_ARG_TYPES (a->type)
3274                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3275                   && TYPE_ARG_TYPES (b->type)
3276                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3277                   && type_list_equal (TYPE_ARG_TYPES (a->type),
3278                                       TYPE_ARG_TYPES (b->type))));
3279
3280     default:
3281       return 0;
3282     }
3283 }
3284
3285 /* Return the cached hash value.  */
3286
3287 static hashval_t
3288 type_hash_hash (const void *item)
3289 {
3290   return ((const struct type_hash *) item)->hash;
3291 }
3292
3293 /* Look in the type hash table for a type isomorphic to TYPE.
3294    If one is found, return it.  Otherwise return 0.  */
3295
3296 tree
3297 type_hash_lookup (hashval_t hashcode, tree type)
3298 {
3299   struct type_hash *h, in;
3300
3301   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3302      must call that routine before comparing TYPE_ALIGNs.  */
3303   layout_type (type);
3304
3305   in.hash = hashcode;
3306   in.type = type;
3307
3308   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3309   if (h)
3310     return h->type;
3311   return NULL_TREE;
3312 }
3313
3314 /* Add an entry to the type-hash-table
3315    for a type TYPE whose hash code is HASHCODE.  */
3316
3317 void
3318 type_hash_add (hashval_t hashcode, tree type)
3319 {
3320   struct type_hash *h;
3321   void **loc;
3322
3323   h = ggc_alloc (sizeof (struct type_hash));
3324   h->hash = hashcode;
3325   h->type = type;
3326   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3327   *(struct type_hash **) loc = h;
3328 }
3329
3330 /* Given TYPE, and HASHCODE its hash code, return the canonical
3331    object for an identical type if one already exists.
3332    Otherwise, return TYPE, and record it as the canonical object.
3333
3334    To use this function, first create a type of the sort you want.
3335    Then compute its hash code from the fields of the type that
3336    make it different from other similar types.
3337    Then call this function and use the value.  */
3338
3339 tree
3340 type_hash_canon (unsigned int hashcode, tree type)
3341 {
3342   tree t1;
3343
3344   /* The hash table only contains main variants, so ensure that's what we're
3345      being passed.  */
3346   if (TYPE_MAIN_VARIANT (type) != type)
3347     abort ();
3348
3349   if (!lang_hooks.types.hash_types)
3350     return type;
3351
3352   /* See if the type is in the hash table already.  If so, return it.
3353      Otherwise, add the type.  */
3354   t1 = type_hash_lookup (hashcode, type);
3355   if (t1 != 0)
3356     {
3357 #ifdef GATHER_STATISTICS
3358       tree_node_counts[(int) t_kind]--;
3359       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3360 #endif
3361       return t1;
3362     }
3363   else
3364     {
3365       type_hash_add (hashcode, type);
3366       return type;
3367     }
3368 }
3369
3370 /* See if the data pointed to by the type hash table is marked.  We consider
3371    it marked if the type is marked or if a debug type number or symbol
3372    table entry has been made for the type.  This reduces the amount of
3373    debugging output and eliminates that dependency of the debug output on
3374    the number of garbage collections.  */
3375
3376 static int
3377 type_hash_marked_p (const void *p)
3378 {
3379   tree type = ((struct type_hash *) p)->type;
3380
3381   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3382 }
3383
3384 static void
3385 print_type_hash_statistics (void)
3386 {
3387   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3388            (long) htab_size (type_hash_table),
3389            (long) htab_elements (type_hash_table),
3390            htab_collisions (type_hash_table));
3391 }
3392
3393 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3394    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3395    by adding the hash codes of the individual attributes.  */
3396
3397 unsigned int
3398 attribute_hash_list (tree list, hashval_t hashcode)
3399 {
3400   tree tail;
3401
3402   for (tail = list; tail; tail = TREE_CHAIN (tail))
3403     /* ??? Do we want to add in TREE_VALUE too? */
3404     hashcode = iterative_hash_object
3405       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
3406   return hashcode;
3407 }
3408
3409 /* Given two lists of attributes, return true if list l2 is
3410    equivalent to l1.  */
3411
3412 int
3413 attribute_list_equal (tree l1, tree l2)
3414 {
3415   return attribute_list_contained (l1, l2)
3416          && attribute_list_contained (l2, l1);
3417 }
3418
3419 /* Given two lists of attributes, return true if list L2 is
3420    completely contained within L1.  */
3421 /* ??? This would be faster if attribute names were stored in a canonicalized
3422    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3423    must be used to show these elements are equivalent (which they are).  */
3424 /* ??? It's not clear that attributes with arguments will always be handled
3425    correctly.  */
3426
3427 int
3428 attribute_list_contained (tree l1, tree l2)
3429 {
3430   tree t1, t2;
3431
3432   /* First check the obvious, maybe the lists are identical.  */
3433   if (l1 == l2)
3434     return 1;
3435
3436   /* Maybe the lists are similar.  */
3437   for (t1 = l1, t2 = l2;
3438        t1 != 0 && t2 != 0
3439         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3440         && TREE_VALUE (t1) == TREE_VALUE (t2);
3441        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3442
3443   /* Maybe the lists are equal.  */
3444   if (t1 == 0 && t2 == 0)
3445     return 1;
3446
3447   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3448     {
3449       tree attr;
3450       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3451            attr != NULL_TREE;
3452            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3453                                     TREE_CHAIN (attr)))
3454         {
3455           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3456             break;
3457         }
3458
3459       if (attr == 0)
3460         return 0;
3461
3462       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3463         return 0;
3464     }
3465
3466   return 1;
3467 }
3468
3469 /* Given two lists of types
3470    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3471    return 1 if the lists contain the same types in the same order.
3472    Also, the TREE_PURPOSEs must match.  */
3473
3474 int
3475 type_list_equal (tree l1, tree l2)
3476 {
3477   tree t1, t2;
3478
3479   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3480     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3481         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3482             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3483                   && (TREE_TYPE (TREE_PURPOSE (t1))
3484                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3485       return 0;
3486
3487   return t1 == t2;
3488 }
3489
3490 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3491    given by TYPE.  If the argument list accepts variable arguments,
3492    then this function counts only the ordinary arguments.  */
3493
3494 int
3495 type_num_arguments (tree type)
3496 {
3497   int i = 0;
3498   tree t;
3499
3500   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3501     /* If the function does not take a variable number of arguments,
3502        the last element in the list will have type `void'.  */
3503     if (VOID_TYPE_P (TREE_VALUE (t)))
3504       break;
3505     else
3506       ++i;
3507
3508   return i;
3509 }
3510
3511 /* Nonzero if integer constants T1 and T2
3512    represent the same constant value.  */
3513
3514 int
3515 tree_int_cst_equal (tree t1, tree t2)
3516 {
3517   if (t1 == t2)
3518     return 1;
3519
3520   if (t1 == 0 || t2 == 0)
3521     return 0;
3522
3523   if (TREE_CODE (t1) == INTEGER_CST
3524       && TREE_CODE (t2) == INTEGER_CST
3525       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3526       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3527     return 1;
3528
3529   return 0;
3530 }
3531
3532 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3533    The precise way of comparison depends on their data type.  */
3534
3535 int
3536 tree_int_cst_lt (tree t1, tree t2)
3537 {
3538   if (t1 == t2)
3539     return 0;
3540
3541   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
3542     {
3543       int t1_sgn = tree_int_cst_sgn (t1);
3544       int t2_sgn = tree_int_cst_sgn (t2);
3545
3546       if (t1_sgn < t2_sgn)
3547         return 1;
3548       else if (t1_sgn > t2_sgn)
3549         return 0;
3550       /* Otherwise, both are non-negative, so we compare them as
3551          unsigned just in case one of them would overflow a signed
3552          type.  */
3553     }
3554   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
3555     return INT_CST_LT (t1, t2);
3556
3557   return INT_CST_LT_UNSIGNED (t1, t2);
3558 }
3559
3560 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3561
3562 int
3563 tree_int_cst_compare (tree t1, tree t2)
3564 {
3565   if (tree_int_cst_lt (t1, t2))
3566     return -1;
3567   else if (tree_int_cst_lt (t2, t1))
3568     return 1;
3569   else
3570     return 0;
3571 }
3572
3573 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
3574    the host.  If POS is zero, the value can be represented in a single
3575    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
3576    be represented in a single unsigned HOST_WIDE_INT.  */
3577
3578 int
3579 host_integerp (tree t, int pos)
3580 {
3581   return (TREE_CODE (t) == INTEGER_CST
3582           && ! TREE_OVERFLOW (t)
3583           && ((TREE_INT_CST_HIGH (t) == 0
3584                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3585               || (! pos && TREE_INT_CST_HIGH (t) == -1
3586                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
3587                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
3588               || (pos && TREE_INT_CST_HIGH (t) == 0)));
3589 }
3590
3591 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3592    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3593    be positive.  Abort if we cannot satisfy the above conditions.  */
3594
3595 HOST_WIDE_INT
3596 tree_low_cst (tree t, int pos)
3597 {
3598   if (host_integerp (t, pos))
3599     return TREE_INT_CST_LOW (t);
3600   else
3601     abort ();
3602 }
3603
3604 /* Return the most significant bit of the integer constant T.  */
3605
3606 int
3607 tree_int_cst_msb (tree t)
3608 {
3609   int prec;
3610   HOST_WIDE_INT h;
3611   unsigned HOST_WIDE_INT l;
3612
3613   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3614      actual bits, not the (arbitrary) range of the type.  */
3615   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3616   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3617                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3618   return (l & 1) == 1;
3619 }
3620
3621 /* Return an indication of the sign of the integer constant T.
3622    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3623    Note that -1 will never be returned it T's type is unsigned.  */
3624
3625 int
3626 tree_int_cst_sgn (tree t)
3627 {
3628   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3629     return 0;
3630   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
3631     return 1;
3632   else if (TREE_INT_CST_HIGH (t) < 0)
3633     return -1;
3634   else
3635     return 1;
3636 }
3637
3638 /* Compare two constructor-element-type constants.  Return 1 if the lists
3639    are known to be equal; otherwise return 0.  */
3640
3641 int
3642 simple_cst_list_equal (tree l1, tree l2)
3643 {
3644   while (l1 != NULL_TREE && l2 != NULL_TREE)
3645     {
3646       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3647         return 0;
3648
3649       l1 = TREE_CHAIN (l1);
3650       l2 = TREE_CHAIN (l2);
3651     }
3652
3653   return l1 == l2;
3654 }
3655
3656 /* Return truthvalue of whether T1 is the same tree structure as T2.
3657    Return 1 if they are the same.
3658    Return 0 if they are understandably different.
3659    Return -1 if either contains tree structure not understood by
3660    this function.  */
3661
3662 int
3663 simple_cst_equal (tree t1, tree t2)
3664 {
3665   enum tree_code code1, code2;
3666   int cmp;
3667   int i;
3668
3669   if (t1 == t2)
3670     return 1;
3671   if (t1 == 0 || t2 == 0)
3672     return 0;
3673
3674   code1 = TREE_CODE (t1);
3675   code2 = TREE_CODE (t2);
3676
3677   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3678     {
3679       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3680           || code2 == NON_LVALUE_EXPR)
3681         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3682       else
3683         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3684     }
3685
3686   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3687            || code2 == NON_LVALUE_EXPR)
3688     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3689
3690   if (code1 != code2)
3691     return 0;
3692
3693   switch (code1)
3694     {
3695     case INTEGER_CST:
3696       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3697               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3698
3699     case REAL_CST:
3700       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3701
3702     case STRING_CST:
3703       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3704               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3705                          TREE_STRING_LENGTH (t1)));
3706
3707     case CONSTRUCTOR:
3708       return simple_cst_list_equal (CONSTRUCTOR_ELTS (t1), 
3709                                     CONSTRUCTOR_ELTS (t2));
3710
3711     case SAVE_EXPR:
3712       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3713
3714     case CALL_EXPR:
3715       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3716       if (cmp <= 0)
3717         return cmp;
3718       return
3719         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3720
3721     case TARGET_EXPR:
3722       /* Special case: if either target is an unallocated VAR_DECL,
3723          it means that it's going to be unified with whatever the
3724          TARGET_EXPR is really supposed to initialize, so treat it
3725          as being equivalent to anything.  */
3726       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3727            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3728            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3729           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3730               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3731               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3732         cmp = 1;
3733       else
3734         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3735
3736       if (cmp <= 0)
3737         return cmp;
3738
3739       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3740
3741     case WITH_CLEANUP_EXPR:
3742       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3743       if (cmp <= 0)
3744         return cmp;
3745
3746       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3747
3748     case COMPONENT_REF:
3749       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3750         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3751
3752       return 0;
3753
3754     case VAR_DECL:
3755     case PARM_DECL:
3756     case CONST_DECL:
3757     case FUNCTION_DECL:
3758       return 0;
3759
3760     default:
3761       break;
3762     }
3763
3764   /* This general rule works for most tree codes.  All exceptions should be
3765      handled above.  If this is a language-specific tree code, we can't
3766      trust what might be in the operand, so say we don't know
3767      the situation.  */
3768   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3769     return -1;
3770
3771   switch (TREE_CODE_CLASS (code1))
3772     {
3773     case '1':
3774     case '2':
3775     case '<':
3776     case 'e':
3777     case 'r':
3778     case 's':
3779       cmp = 1;
3780       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3781         {
3782           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3783           if (cmp <= 0)
3784             return cmp;
3785         }
3786
3787       return cmp;
3788
3789     default:
3790       return -1;
3791     }
3792 }
3793
3794 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
3795    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
3796    than U, respectively.  */
3797
3798 int
3799 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
3800 {
3801   if (tree_int_cst_sgn (t) < 0)
3802     return -1;
3803   else if (TREE_INT_CST_HIGH (t) != 0)
3804     return 1;
3805   else if (TREE_INT_CST_LOW (t) == u)
3806     return 0;
3807   else if (TREE_INT_CST_LOW (t) < u)
3808     return -1;
3809   else
3810     return 1;
3811 }
3812
3813 /* Return true if CODE represents an associative tree code.  Otherwise
3814    return false.  */
3815 bool
3816 associative_tree_code (enum tree_code code)
3817 {
3818   switch (code)
3819     {
3820     case BIT_IOR_EXPR:
3821     case BIT_AND_EXPR:
3822     case BIT_XOR_EXPR:
3823     case PLUS_EXPR:
3824     case MULT_EXPR:
3825     case MIN_EXPR:
3826     case MAX_EXPR:
3827       return true;
3828
3829     default:
3830       break;
3831     }
3832   return false;
3833 }
3834
3835 /* Return true if CODE represents an commutative tree code.  Otherwise
3836    return false.  */
3837 bool
3838 commutative_tree_code (enum tree_code code)
3839 {
3840   switch (code)
3841     {
3842     case PLUS_EXPR:
3843     case MULT_EXPR:
3844     case MIN_EXPR:
3845     case MAX_EXPR:
3846     case BIT_IOR_EXPR:
3847     case BIT_XOR_EXPR:
3848     case BIT_AND_EXPR:
3849     case NE_EXPR:
3850     case EQ_EXPR:
3851     case UNORDERED_EXPR:
3852     case ORDERED_EXPR:
3853     case UNEQ_EXPR:
3854     case LTGT_EXPR:
3855     case TRUTH_AND_EXPR:
3856     case TRUTH_XOR_EXPR:
3857     case TRUTH_OR_EXPR:
3858       return true;
3859
3860     default:
3861       break;
3862     }
3863   return false;
3864 }
3865
3866 /* Generate a hash value for an expression.  This can be used iteratively
3867    by passing a previous result as the "val" argument.
3868
3869    This function is intended to produce the same hash for expressions which
3870    would compare equal using operand_equal_p.  */
3871
3872 hashval_t
3873 iterative_hash_expr (tree t, hashval_t val)
3874 {
3875   int i;
3876   enum tree_code code;
3877   char class;
3878
3879   if (t == NULL_TREE)
3880     return iterative_hash_object (t, val);
3881
3882   code = TREE_CODE (t);
3883   class = TREE_CODE_CLASS (code);
3884
3885   if (class == 'd'
3886       || TREE_CODE (t) == VALUE_HANDLE)
3887     {
3888       /* Decls we can just compare by pointer.  */
3889       val = iterative_hash_object (t, val);
3890     }
3891   else if (class == 'c')
3892     {
3893       /* Alas, constants aren't shared, so we can't rely on pointer
3894          identity.  */
3895       if (code == INTEGER_CST)
3896         {
3897           val = iterative_hash_object (TREE_INT_CST_LOW (t), val);
3898           val = iterative_hash_object (TREE_INT_CST_HIGH (t), val);
3899         }
3900       else if (code == REAL_CST)
3901         {
3902           unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
3903
3904           val = iterative_hash (&val2, sizeof (unsigned int), val);
3905         }
3906       else if (code == STRING_CST)
3907         val = iterative_hash (TREE_STRING_POINTER (t),
3908                               TREE_STRING_LENGTH (t), val);
3909       else if (code == COMPLEX_CST)
3910         {
3911           val = iterative_hash_expr (TREE_REALPART (t), val);
3912           val = iterative_hash_expr (TREE_IMAGPART (t), val);
3913         }
3914       else if (code == VECTOR_CST)
3915         val = iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
3916       else
3917         abort ();
3918     }
3919   else if (IS_EXPR_CODE_CLASS (class))
3920     {
3921       val = iterative_hash_object (code, val);
3922
3923       /* Don't hash the type, that can lead to having nodes which
3924          compare equal according to operand_equal_p, but which
3925          have different hash codes.  */
3926       if (code == NOP_EXPR
3927           || code == CONVERT_EXPR
3928           || code == NON_LVALUE_EXPR)
3929         {
3930           /* Make sure to include signness in the hash computation.  */
3931           val += TYPE_UNSIGNED (TREE_TYPE (t));
3932           val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
3933         }
3934
3935       if (commutative_tree_code (code))
3936         {
3937           /* It's a commutative expression.  We want to hash it the same
3938              however it appears.  We do this by first hashing both operands
3939              and then rehashing based on the order of their independent
3940              hashes.  */
3941           hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
3942           hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
3943           hashval_t t;
3944
3945           if (one > two)
3946             t = one, one = two, two = t;
3947
3948           val = iterative_hash_object (one, val);
3949           val = iterative_hash_object (two, val);
3950         }
3951       else
3952         for (i = first_rtl_op (code) - 1; i >= 0; --i)
3953           val = iterative_hash_expr (TREE_OPERAND (t, i), val);
3954     }
3955   else if (code == TREE_LIST)
3956     {
3957       /* A list of expressions, for a CALL_EXPR or as the elements of a
3958          VECTOR_CST.  */
3959       for (; t; t = TREE_CHAIN (t))
3960         val = iterative_hash_expr (TREE_VALUE (t), val);
3961     }
3962   else if (code == SSA_NAME)
3963     {
3964       val = iterative_hash_object (SSA_NAME_VERSION (t), val);
3965       val = iterative_hash_expr (SSA_NAME_VAR (t), val);
3966     }
3967   else
3968     abort ();
3969
3970   return val;
3971 }
3972 \f
3973 /* Constructors for pointer, array and function types.
3974    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
3975    constructed by language-dependent code, not here.)  */
3976
3977 /* Construct, lay out and return the type of pointers to TO_TYPE with
3978    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
3979    reference all of memory. If such a type has already been
3980    constructed, reuse it.  */
3981
3982 tree
3983 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
3984                              bool can_alias_all)
3985 {
3986   tree t;
3987
3988   /* In some cases, languages will have things that aren't a POINTER_TYPE
3989      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
3990      In that case, return that type without regard to the rest of our
3991      operands.
3992
3993      ??? This is a kludge, but consistent with the way this function has
3994      always operated and there doesn't seem to be a good way to avoid this
3995      at the moment.  */
3996   if (TYPE_POINTER_TO (to_type) != 0
3997       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
3998     return TYPE_POINTER_TO (to_type);
3999
4000   /* First, if we already have a type for pointers to TO_TYPE and it's
4001      the proper mode, use it.  */
4002   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4003     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4004       return t;
4005
4006   t = make_node (POINTER_TYPE);
4007
4008   TREE_TYPE (t) = to_type;
4009   TYPE_MODE (t) = mode;
4010   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4011   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4012   TYPE_POINTER_TO (to_type) = t;
4013
4014   /* Lay out the type.  This function has many callers that are concerned
4015      with expression-construction, and this simplifies them all.  */
4016   layout_type (t);
4017
4018   return t;
4019 }
4020
4021 /* By default build pointers in ptr_mode.  */
4022
4023 tree
4024 build_pointer_type (tree to_type)
4025 {
4026   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4027 }
4028
4029 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4030
4031 tree
4032 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4033                                bool can_alias_all)
4034 {
4035   tree t;
4036
4037   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4038      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4039      In that case, return that type without regard to the rest of our
4040      operands.
4041
4042      ??? This is a kludge, but consistent with the way this function has
4043      always operated and there doesn't seem to be a good way to avoid this
4044      at the moment.  */
4045   if (TYPE_REFERENCE_TO (to_type) != 0
4046       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4047     return TYPE_REFERENCE_TO (to_type);
4048
4049   /* First, if we already have a type for pointers to TO_TYPE and it's
4050      the proper mode, use it.  */
4051   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4052     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4053       return t;
4054
4055   t = make_node (REFERENCE_TYPE);
4056
4057   TREE_TYPE (t) = to_type;
4058   TYPE_MODE (t) = mode;
4059   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4060   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4061   TYPE_REFERENCE_TO (to_type) = t;
4062
4063   layout_type (t);
4064
4065   return t;
4066 }
4067
4068
4069 /* Build the node for the type of references-to-TO_TYPE by default
4070    in ptr_mode.  */
4071
4072 tree
4073 build_reference_type (tree to_type)
4074 {
4075   return build_reference_type_for_mode (to_type, ptr_mode, false);
4076 }
4077
4078 /* Build a type that is compatible with t but has no cv quals anywhere
4079    in its type, thus
4080
4081    const char *const *const *  ->  char ***.  */
4082
4083 tree
4084 build_type_no_quals (tree t)
4085 {
4086   switch (TREE_CODE (t))
4087     {
4088     case POINTER_TYPE:
4089       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4090                                           TYPE_MODE (t),
4091                                           TYPE_REF_CAN_ALIAS_ALL (t));
4092     case REFERENCE_TYPE:
4093       return
4094         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4095                                        TYPE_MODE (t),
4096                                        TYPE_REF_CAN_ALIAS_ALL (t));
4097     default:
4098       return TYPE_MAIN_VARIANT (t);
4099     }
4100 }
4101
4102 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4103    MAXVAL should be the maximum value in the domain
4104    (one less than the length of the array).
4105
4106    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4107    We don't enforce this limit, that is up to caller (e.g. language front end).
4108    The limit exists because the result is a signed type and we don't handle
4109    sizes that use more than one HOST_WIDE_INT.  */
4110
4111 tree
4112 build_index_type (tree maxval)
4113 {
4114   tree itype = make_node (INTEGER_TYPE);
4115
4116   TREE_TYPE (itype) = sizetype;
4117   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4118   TYPE_MIN_VALUE (itype) = size_zero_node;
4119   TYPE_MAX_VALUE (itype) = convert (sizetype, maxval);
4120   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4121   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4122   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4123   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4124   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4125
4126   if (host_integerp (maxval, 1))
4127     return type_hash_canon (tree_low_cst (maxval, 1), itype);
4128   else
4129     return itype;
4130 }
4131
4132 /* Builds a signed or unsigned integer type of precision PRECISION.
4133    Used for C bitfields whose precision does not match that of
4134    built-in target types.  */
4135 tree
4136 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
4137                                 int unsignedp)
4138 {
4139   tree itype = make_node (INTEGER_TYPE);
4140
4141   TYPE_PRECISION (itype) = precision;
4142
4143   if (unsignedp)
4144     fixup_unsigned_type (itype);
4145   else
4146     fixup_signed_type (itype);
4147
4148   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
4149     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
4150
4151   return itype;
4152 }
4153
4154 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
4155    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
4156    low bound LOWVAL and high bound HIGHVAL.
4157    if TYPE==NULL_TREE, sizetype is used.  */
4158
4159 tree
4160 build_range_type (tree type, tree lowval, tree highval)
4161 {
4162   tree itype = make_node (INTEGER_TYPE);
4163
4164   TREE_TYPE (itype) = type;
4165   if (type == NULL_TREE)
4166     type = sizetype;
4167
4168   TYPE_MIN_VALUE (itype) = convert (type, lowval);
4169   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
4170
4171   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
4172   TYPE_MODE (itype) = TYPE_MODE (type);
4173   TYPE_SIZE (itype) = TYPE_SIZE (type);
4174   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
4175   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
4176   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
4177
4178   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
4179     return type_hash_canon (tree_low_cst (highval, 0)
4180                             - tree_low_cst (lowval, 0),
4181                             itype);
4182   else
4183     return itype;
4184 }
4185
4186 /* Just like build_index_type, but takes lowval and highval instead
4187    of just highval (maxval).  */
4188
4189 tree
4190 build_index_2_type (tree lowval, tree highval)
4191 {
4192   return build_range_type (sizetype, lowval, highval);
4193 }
4194
4195 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
4196    and number of elements specified by the range of values of INDEX_TYPE.
4197    If such a type has already been constructed, reuse it.  */
4198
4199 tree
4200 build_array_type (tree elt_type, tree index_type)
4201 {
4202   tree t;
4203   hashval_t hashcode = 0;
4204
4205   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
4206     {
4207       error ("arrays of functions are not meaningful");
4208       elt_type = integer_type_node;
4209     }
4210
4211   t = make_node (ARRAY_TYPE);
4212   TREE_TYPE (t) = elt_type;
4213   TYPE_DOMAIN (t) = index_type;
4214
4215   if (index_type == 0)
4216     return t;
4217
4218   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
4219   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
4220   t = type_hash_canon (hashcode, t);
4221
4222   if (!COMPLETE_TYPE_P (t))
4223     layout_type (t);
4224   return t;
4225 }
4226
4227 /* Return the TYPE of the elements comprising
4228    the innermost dimension of ARRAY.  */
4229
4230 tree
4231 get_inner_array_type (tree array)
4232 {
4233   tree type = TREE_TYPE (array);
4234
4235   while (TREE_CODE (type) == ARRAY_TYPE)
4236     type = TREE_TYPE (type);
4237
4238   return type;
4239 }
4240
4241 /* Construct, lay out and return
4242    the type of functions returning type VALUE_TYPE
4243    given arguments of types ARG_TYPES.
4244    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
4245    are data type nodes for the arguments of the function.
4246    If such a type has already been constructed, reuse it.  */
4247
4248 tree
4249 build_function_type (tree value_type, tree arg_types)
4250 {
4251   tree t;
4252   hashval_t hashcode = 0;
4253
4254   if (TREE_CODE (value_type) == FUNCTION_TYPE)
4255     {
4256       error ("function return type cannot be function");
4257       value_type = integer_type_node;
4258     }
4259
4260   /* Make a node of the sort we want.  */
4261   t = make_node (FUNCTION_TYPE);
4262   TREE_TYPE (t) = value_type;
4263   TYPE_ARG_TYPES (t) = arg_types;
4264
4265   /* If we already have such a type, use the old one.  */
4266   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
4267   hashcode = type_hash_list (arg_types, hashcode);
4268   t = type_hash_canon (hashcode, t);
4269
4270   if (!COMPLETE_TYPE_P (t))
4271     layout_type (t);
4272   return t;
4273 }
4274
4275 /* Build a function type.  The RETURN_TYPE is the type returned by the
4276    function.  If additional arguments are provided, they are
4277    additional argument types.  The list of argument types must always
4278    be terminated by NULL_TREE.  */
4279
4280 tree
4281 build_function_type_list (tree return_type, ...)
4282 {
4283   tree t, args, last;
4284   va_list p;
4285
4286   va_start (p, return_type);
4287
4288   t = va_arg (p, tree);
4289   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
4290     args = tree_cons (NULL_TREE, t, args);
4291
4292   last = args;
4293   args = nreverse (args);
4294   TREE_CHAIN (last) = void_list_node;
4295   args = build_function_type (return_type, args);
4296
4297   va_end (p);
4298   return args;
4299 }
4300
4301 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
4302    and ARGTYPES (a TREE_LIST) are the return type and arguments types
4303    for the method.  An implicit additional parameter (of type
4304    pointer-to-BASETYPE) is added to the ARGTYPES.  */
4305
4306 tree
4307 build_method_type_directly (tree basetype,
4308                             tree rettype,
4309                             tree argtypes)
4310 {
4311   tree t;
4312   tree ptype;
4313   int hashcode = 0;
4314
4315   /* Make a node of the sort we want.  */
4316   t = make_node (METHOD_TYPE);
4317
4318   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4319   TREE_TYPE (t) = rettype;
4320   ptype = build_pointer_type (basetype);
4321
4322   /* The actual arglist for this function includes a "hidden" argument
4323      which is "this".  Put it into the list of argument types.  */
4324   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
4325   TYPE_ARG_TYPES (t) = argtypes;
4326
4327   /* If we already have such a type, use the old one.  */
4328   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4329   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
4330   hashcode = type_hash_list (argtypes, hashcode);
4331   t = type_hash_canon (hashcode, t);
4332
4333   if (!COMPLETE_TYPE_P (t))
4334     layout_type (t);
4335
4336   return t;
4337 }
4338
4339 /* Construct, lay out and return the type of methods belonging to class
4340    BASETYPE and whose arguments and values are described by TYPE.
4341    If that type exists already, reuse it.
4342    TYPE must be a FUNCTION_TYPE node.  */
4343
4344 tree
4345 build_method_type (tree basetype, tree type)
4346 {
4347   if (TREE_CODE (type) != FUNCTION_TYPE)
4348     abort ();
4349
4350   return build_method_type_directly (basetype, 
4351                                      TREE_TYPE (type),
4352                                      TYPE_ARG_TYPES (type));
4353 }
4354
4355 /* Construct, lay out and return the type of offsets to a value
4356    of type TYPE, within an object of type BASETYPE.
4357    If a suitable offset type exists already, reuse it.  */
4358
4359 tree
4360 build_offset_type (tree basetype, tree type)
4361 {
4362   tree t;
4363   hashval_t hashcode = 0;
4364
4365   /* Make a node of the sort we want.  */
4366   t = make_node (OFFSET_TYPE);
4367
4368   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4369   TREE_TYPE (t) = type;
4370
4371   /* If we already have such a type, use the old one.  */
4372   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4373   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
4374   t = type_hash_canon (hashcode, t);
4375
4376   if (!COMPLETE_TYPE_P (t))
4377     layout_type (t);
4378
4379   return t;
4380 }
4381
4382 /* Create a complex type whose components are COMPONENT_TYPE.  */
4383
4384 tree
4385 build_complex_type (tree component_type)
4386 {
4387   tree t;
4388   hashval_t hashcode;
4389
4390   /* Make a node of the sort we want.  */
4391   t = make_node (COMPLEX_TYPE);
4392
4393   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
4394
4395   /* If we already have such a type, use the old one.  */
4396   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
4397   t = type_hash_canon (hashcode, t);
4398
4399   if (!COMPLETE_TYPE_P (t))
4400     layout_type (t);
4401
4402   /* If we are writing Dwarf2 output we need to create a name,
4403      since complex is a fundamental type.  */
4404   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
4405       && ! TYPE_NAME (t))
4406     {
4407       const char *name;
4408       if (component_type == char_type_node)
4409         name = "complex char";
4410       else if (component_type == signed_char_type_node)
4411         name = "complex signed char";
4412       else if (component_type == unsigned_char_type_node)
4413         name = "complex unsigned char";
4414       else if (component_type == short_integer_type_node)
4415         name = "complex short int";
4416       else if (component_type == short_unsigned_type_node)
4417         name = "complex short unsigned int";
4418       else if (component_type == integer_type_node)
4419         name = "complex int";
4420       else if (component_type == unsigned_type_node)
4421         name = "complex unsigned int";
4422       else if (component_type == long_integer_type_node)
4423         name = "complex long int";
4424       else if (component_type == long_unsigned_type_node)
4425         name = "complex long unsigned int";
4426       else if (component_type == long_long_integer_type_node)
4427         name = "complex long long int";
4428       else if (component_type == long_long_unsigned_type_node)
4429         name = "complex long long unsigned int";
4430       else
4431         name = 0;
4432
4433       if (name != 0)
4434         TYPE_NAME (t) = get_identifier (name);
4435     }
4436
4437   return build_qualified_type (t, TYPE_QUALS (component_type));
4438 }
4439 \f
4440 /* Return OP, stripped of any conversions to wider types as much as is safe.
4441    Converting the value back to OP's type makes a value equivalent to OP.
4442
4443    If FOR_TYPE is nonzero, we return a value which, if converted to
4444    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
4445
4446    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
4447    narrowest type that can hold the value, even if they don't exactly fit.
4448    Otherwise, bit-field references are changed to a narrower type
4449    only if they can be fetched directly from memory in that type.
4450
4451    OP must have integer, real or enumeral type.  Pointers are not allowed!
4452
4453    There are some cases where the obvious value we could return
4454    would regenerate to OP if converted to OP's type,
4455    but would not extend like OP to wider types.
4456    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
4457    For example, if OP is (unsigned short)(signed char)-1,
4458    we avoid returning (signed char)-1 if FOR_TYPE is int,
4459    even though extending that to an unsigned short would regenerate OP,
4460    since the result of extending (signed char)-1 to (int)
4461    is different from (int) OP.  */
4462
4463 tree
4464 get_unwidened (tree op, tree for_type)
4465 {
4466   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */