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