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