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 /* Given a type node TYPE and a TYPE_QUALIFIER_SET, return a type for
2997    the same kind of data as TYPE describes.  Variants point to the
2998    "main variant" (which has no qualifiers set) via TYPE_MAIN_VARIANT,
2999    and it points to a chain of other variants so that duplicate
3000    variants are never made.  Only main variants should ever appear as
3001    types of expressions.  */
3002
3003 tree
3004 build_qualified_type (type, type_quals)
3005      tree type;
3006      int type_quals;
3007 {
3008   register tree t;
3009
3010   /* Search the chain of variants to see if there is already one there just
3011      like the one we need to have.  If so, use that existing one.  We must
3012      preserve the TYPE_NAME, since there is code that depends on this.  */
3013
3014   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3015     if (TYPE_QUALS (t) == type_quals && TYPE_NAME (t) == TYPE_NAME (type))
3016       return t;
3017
3018   /* We need a new one.  */
3019   t = build_type_copy (type);
3020   set_type_quals (t, type_quals);
3021   return t;
3022 }
3023
3024 /* Create a new variant of TYPE, equivalent but distinct.
3025    This is so the caller can modify it.  */
3026
3027 tree
3028 build_type_copy (type)
3029      tree type;
3030 {
3031   register tree t, m = TYPE_MAIN_VARIANT (type);
3032
3033   t = copy_node (type);
3034
3035   TYPE_POINTER_TO (t) = 0;
3036   TYPE_REFERENCE_TO (t) = 0;
3037
3038   /* Add this type to the chain of variants of TYPE.  */
3039   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3040   TYPE_NEXT_VARIANT (m) = t;
3041
3042   return t;
3043 }
3044 \f
3045 /* Hashing of types so that we don't make duplicates.
3046    The entry point is `type_hash_canon'.  */
3047
3048 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3049    with types in the TREE_VALUE slots), by adding the hash codes
3050    of the individual types.  */
3051
3052 unsigned int
3053 type_hash_list (list)
3054      tree list;
3055 {
3056   unsigned int hashcode;
3057   register tree tail;
3058
3059   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
3060     hashcode += TYPE_HASH (TREE_VALUE (tail));
3061
3062   return hashcode;
3063 }
3064
3065 /* These are the Hashtable callback functions.  */
3066
3067 /* Returns true if the types are equal.  */
3068
3069 static int
3070 type_hash_eq (va, vb)
3071      const void *va;
3072      const void *vb;
3073 {
3074   const struct type_hash *a = va, *b = vb;
3075   if (a->hash == b->hash
3076       && TREE_CODE (a->type) == TREE_CODE (b->type)
3077       && TREE_TYPE (a->type) == TREE_TYPE (b->type)
3078       && attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3079                                TYPE_ATTRIBUTES (b->type))
3080       && TYPE_ALIGN (a->type) == TYPE_ALIGN (b->type)
3081       && (TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3082           || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3083                                  TYPE_MAX_VALUE (b->type)))
3084       && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3085           || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3086                                  TYPE_MIN_VALUE (b->type)))
3087       /* Note that TYPE_DOMAIN is TYPE_ARG_TYPES for FUNCTION_TYPE.  */
3088       && (TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type)
3089           || (TYPE_DOMAIN (a->type)
3090               && TREE_CODE (TYPE_DOMAIN (a->type)) == TREE_LIST
3091               && TYPE_DOMAIN (b->type)
3092               && TREE_CODE (TYPE_DOMAIN (b->type)) == TREE_LIST
3093               && type_list_equal (TYPE_DOMAIN (a->type),
3094                                   TYPE_DOMAIN (b->type)))))
3095     return 1;
3096   return 0;
3097 }
3098
3099 /* Return the cached hash value.  */
3100
3101 static unsigned int
3102 type_hash_hash (item)
3103      const void *item;
3104 {
3105   return ((const struct type_hash *) item)->hash;
3106 }
3107
3108 /* Look in the type hash table for a type isomorphic to TYPE.
3109    If one is found, return it.  Otherwise return 0.  */
3110
3111 tree
3112 type_hash_lookup (hashcode, type)
3113      unsigned int hashcode;
3114      tree type;
3115 {
3116   struct type_hash *h, in;
3117
3118   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3119      must call that routine before comparing TYPE_ALIGNs.  */
3120   layout_type (type);
3121
3122   in.hash = hashcode;
3123   in.type = type;
3124
3125   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3126   if (h)
3127     return h->type;
3128   return NULL_TREE;
3129 }
3130
3131 /* Add an entry to the type-hash-table
3132    for a type TYPE whose hash code is HASHCODE.  */
3133
3134 void
3135 type_hash_add (hashcode, type)
3136      unsigned int hashcode;
3137      tree type;
3138 {
3139   struct type_hash *h;
3140   void **loc;
3141
3142   h = (struct type_hash *) permalloc (sizeof (struct type_hash));
3143   h->hash = hashcode;
3144   h->type = type;
3145   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3146   *(struct type_hash **) loc = h;
3147 }
3148
3149 /* Given TYPE, and HASHCODE its hash code, return the canonical
3150    object for an identical type if one already exists.
3151    Otherwise, return TYPE, and record it as the canonical object
3152    if it is a permanent object.
3153
3154    To use this function, first create a type of the sort you want.
3155    Then compute its hash code from the fields of the type that
3156    make it different from other similar types.
3157    Then call this function and use the value.
3158    This function frees the type you pass in if it is a duplicate.  */
3159
3160 /* Set to 1 to debug without canonicalization.  Never set by program.  */
3161 int debug_no_type_hash = 0;
3162
3163 tree
3164 type_hash_canon (hashcode, type)
3165      unsigned int hashcode;
3166      tree type;
3167 {
3168   tree t1;
3169
3170   if (debug_no_type_hash)
3171     return type;
3172
3173   t1 = type_hash_lookup (hashcode, type);
3174   if (t1 != 0)
3175     {
3176 #ifdef GATHER_STATISTICS
3177       tree_node_counts[(int) t_kind]--;
3178       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3179 #endif
3180       return t1;
3181     }
3182
3183   /* If this is a permanent type, record it for later reuse.  */
3184   type_hash_add (hashcode, type);
3185
3186   return type;
3187 }
3188
3189 /* Callback function for htab_traverse.  */
3190
3191 static int
3192 mark_hash_entry (entry, param)
3193      void **entry;
3194      void *param ATTRIBUTE_UNUSED;
3195 {
3196   struct type_hash *p = *(struct type_hash **) entry;
3197
3198   ggc_mark_tree (p->type);
3199
3200   /* Continue scan.  */
3201   return 1;
3202 }
3203
3204 /* Mark ARG (which is really a htab_t *) for GC.  */
3205
3206 static void
3207 mark_type_hash (arg)
3208      void *arg;
3209 {
3210   htab_t t = *(htab_t *) arg;
3211
3212   htab_traverse (t, mark_hash_entry, 0);
3213 }
3214
3215 /* Mark the hashtable slot pointed to by ENTRY (which is really a
3216    `tree**') for GC.  */
3217
3218 static int
3219 mark_tree_hashtable_entry (entry, data)
3220      void **entry;
3221      void *data ATTRIBUTE_UNUSED;
3222 {
3223   ggc_mark_tree ((tree) *entry);
3224   return 1;
3225 }
3226
3227 /* Mark ARG (which is really a htab_t whose slots are trees) for
3228    GC.  */
3229
3230 void
3231 mark_tree_hashtable (arg)
3232      void *arg;
3233 {
3234   htab_t t = *(htab_t *) arg;
3235   htab_traverse (t, mark_tree_hashtable_entry, 0);
3236 }
3237
3238 static void
3239 print_type_hash_statistics ()
3240 {
3241   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3242            (long) htab_size (type_hash_table),
3243            (long) htab_elements (type_hash_table),
3244            htab_collisions (type_hash_table));
3245 }
3246
3247 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3248    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3249    by adding the hash codes of the individual attributes.  */
3250
3251 unsigned int
3252 attribute_hash_list (list)
3253      tree list;
3254 {
3255   unsigned int hashcode;
3256   register tree tail;
3257
3258   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
3259     /* ??? Do we want to add in TREE_VALUE too? */
3260     hashcode += TYPE_HASH (TREE_PURPOSE (tail));
3261   return hashcode;
3262 }
3263
3264 /* Given two lists of attributes, return true if list l2 is
3265    equivalent to l1.  */
3266
3267 int
3268 attribute_list_equal (l1, l2)
3269      tree l1, l2;
3270 {
3271    return attribute_list_contained (l1, l2)
3272           && attribute_list_contained (l2, l1);
3273 }
3274
3275 /* Given two lists of attributes, return true if list L2 is
3276    completely contained within L1.  */
3277 /* ??? This would be faster if attribute names were stored in a canonicalized
3278    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3279    must be used to show these elements are equivalent (which they are).  */
3280 /* ??? It's not clear that attributes with arguments will always be handled
3281    correctly.  */
3282
3283 int
3284 attribute_list_contained (l1, l2)
3285      tree l1, l2;
3286 {
3287   register tree t1, t2;
3288
3289   /* First check the obvious, maybe the lists are identical.  */
3290   if (l1 == l2)
3291     return 1;
3292
3293   /* Maybe the lists are similar.  */
3294   for (t1 = l1, t2 = l2;
3295        t1 != 0 && t2 != 0
3296         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3297         && TREE_VALUE (t1) == TREE_VALUE (t2);
3298        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3299
3300   /* Maybe the lists are equal.  */
3301   if (t1 == 0 && t2 == 0)
3302      return 1;
3303
3304   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3305     {
3306       tree attr
3307         = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3308
3309       if (attr == 0)
3310         return 0;
3311
3312       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3313         return 0;
3314     }
3315
3316   return 1;
3317 }
3318
3319 /* Given two lists of types
3320    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3321    return 1 if the lists contain the same types in the same order.
3322    Also, the TREE_PURPOSEs must match.  */
3323
3324 int
3325 type_list_equal (l1, l2)
3326      tree l1, l2;
3327 {
3328   register tree t1, t2;
3329
3330   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3331     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3332         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3333             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3334                   && (TREE_TYPE (TREE_PURPOSE (t1))
3335                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3336       return 0;
3337
3338   return t1 == t2;
3339 }
3340
3341 /* Nonzero if integer constants T1 and T2
3342    represent the same constant value.  */
3343
3344 int
3345 tree_int_cst_equal (t1, t2)
3346      tree t1, t2;
3347 {
3348   if (t1 == t2)
3349     return 1;
3350
3351   if (t1 == 0 || t2 == 0)
3352     return 0;
3353
3354   if (TREE_CODE (t1) == INTEGER_CST
3355       && TREE_CODE (t2) == INTEGER_CST
3356       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3357       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3358     return 1;
3359
3360   return 0;
3361 }
3362
3363 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3364    The precise way of comparison depends on their data type.  */
3365
3366 int
3367 tree_int_cst_lt (t1, t2)
3368      tree t1, t2;
3369 {
3370   if (t1 == t2)
3371     return 0;
3372
3373   if (! TREE_UNSIGNED (TREE_TYPE (t1)))
3374     return INT_CST_LT (t1, t2);
3375
3376   return INT_CST_LT_UNSIGNED (t1, t2);
3377 }
3378
3379 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3380
3381 int
3382 tree_int_cst_compare (t1, t2)
3383      tree t1;
3384      tree t2;
3385 {
3386   if (tree_int_cst_lt (t1, t2))
3387     return -1;
3388   else if (tree_int_cst_lt (t2, t1))
3389     return 1;
3390   else
3391     return 0;
3392 }
3393
3394 /* Return 1 if T is an INTEGER_CST that can be represented in a single
3395    HOST_WIDE_INT value.  If POS is nonzero, the result must be positive.  */
3396
3397 int
3398 host_integerp (t, pos)
3399      tree t;
3400      int pos;
3401 {
3402   return (TREE_CODE (t) == INTEGER_CST
3403           && ! TREE_OVERFLOW (t)
3404           && ((TREE_INT_CST_HIGH (t) == 0
3405                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3406               || (! pos && TREE_INT_CST_HIGH (t) == -1
3407                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
3408               || (! pos && TREE_INT_CST_HIGH (t) == 0
3409                   && TREE_UNSIGNED (TREE_TYPE (t)))));
3410 }
3411
3412 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3413    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3414    be positive.  Abort if we cannot satisfy the above conditions.  */
3415
3416 HOST_WIDE_INT
3417 tree_low_cst (t, pos)
3418      tree t;
3419      int pos;
3420 {
3421   if (host_integerp (t, pos))
3422     return TREE_INT_CST_LOW (t);
3423   else
3424     abort ();
3425 }
3426
3427 /* Return the most significant bit of the integer constant T.  */
3428
3429 int
3430 tree_int_cst_msb (t)
3431      tree t;
3432 {
3433   register int prec;
3434   HOST_WIDE_INT h;
3435   unsigned HOST_WIDE_INT l;
3436
3437   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3438      actual bits, not the (arbitrary) range of the type.  */
3439   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3440   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3441                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3442   return (l & 1) == 1;
3443 }
3444
3445 /* Return an indication of the sign of the integer constant T.
3446    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3447    Note that -1 will never be returned it T's type is unsigned.  */
3448
3449 int
3450 tree_int_cst_sgn (t)
3451      tree t;
3452 {
3453   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3454     return 0;
3455   else if (TREE_UNSIGNED (TREE_TYPE (t)))
3456     return 1;
3457   else if (TREE_INT_CST_HIGH (t) < 0)
3458     return -1;
3459   else
3460     return 1;
3461 }
3462
3463 /* Compare two constructor-element-type constants.  Return 1 if the lists
3464    are known to be equal; otherwise return 0.  */
3465
3466 int
3467 simple_cst_list_equal (l1, l2)
3468      tree l1, l2;
3469 {
3470   while (l1 != NULL_TREE && l2 != NULL_TREE)
3471     {
3472       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3473         return 0;
3474
3475       l1 = TREE_CHAIN (l1);
3476       l2 = TREE_CHAIN (l2);
3477     }
3478
3479   return l1 == l2;
3480 }
3481
3482 /* Return truthvalue of whether T1 is the same tree structure as T2.
3483    Return 1 if they are the same.
3484    Return 0 if they are understandably different.
3485    Return -1 if either contains tree structure not understood by
3486    this function.  */
3487
3488 int
3489 simple_cst_equal (t1, t2)
3490      tree t1, t2;
3491 {
3492   register enum tree_code code1, code2;
3493   int cmp;
3494   int i;
3495
3496   if (t1 == t2)
3497     return 1;
3498   if (t1 == 0 || t2 == 0)
3499     return 0;
3500
3501   code1 = TREE_CODE (t1);
3502   code2 = TREE_CODE (t2);
3503
3504   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3505     {
3506       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3507           || code2 == NON_LVALUE_EXPR)
3508         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3509       else
3510         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3511     }
3512
3513   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3514            || code2 == NON_LVALUE_EXPR)
3515     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3516
3517   if (code1 != code2)
3518     return 0;
3519
3520   switch (code1)
3521     {
3522     case INTEGER_CST:
3523       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3524               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3525
3526     case REAL_CST:
3527       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3528
3529     case STRING_CST:
3530       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3531               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3532                          TREE_STRING_LENGTH (t1)));
3533
3534     case CONSTRUCTOR:
3535       if (CONSTRUCTOR_ELTS (t1) == CONSTRUCTOR_ELTS (t2))
3536         return 1;
3537       else
3538         abort ();
3539
3540     case SAVE_EXPR:
3541       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3542
3543     case CALL_EXPR:
3544       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3545       if (cmp <= 0)
3546         return cmp;
3547       return
3548         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3549
3550     case TARGET_EXPR:
3551       /* Special case: if either target is an unallocated VAR_DECL,
3552          it means that it's going to be unified with whatever the
3553          TARGET_EXPR is really supposed to initialize, so treat it
3554          as being equivalent to anything.  */
3555       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3556            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3557            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3558           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3559               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3560               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3561         cmp = 1;
3562       else
3563         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3564
3565       if (cmp <= 0)
3566         return cmp;
3567
3568       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3569
3570     case WITH_CLEANUP_EXPR:
3571       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3572       if (cmp <= 0)
3573         return cmp;
3574
3575       return simple_cst_equal (TREE_OPERAND (t1, 2), TREE_OPERAND (t1, 2));
3576
3577     case COMPONENT_REF:
3578       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3579         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3580
3581       return 0;
3582
3583     case VAR_DECL:
3584     case PARM_DECL:
3585     case CONST_DECL:
3586     case FUNCTION_DECL:
3587       return 0;
3588
3589     default:
3590       break;
3591     }
3592
3593   /* This general rule works for most tree codes.  All exceptions should be
3594      handled above.  If this is a language-specific tree code, we can't
3595      trust what might be in the operand, so say we don't know
3596      the situation.  */
3597   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3598     return -1;
3599
3600   switch (TREE_CODE_CLASS (code1))
3601     {
3602     case '1':
3603     case '2':
3604     case '<':
3605     case 'e':
3606     case 'r':
3607     case 's':
3608       cmp = 1;
3609       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3610         {
3611           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3612           if (cmp <= 0)
3613             return cmp;
3614         }
3615
3616       return cmp;
3617
3618     default:
3619       return -1;
3620     }
3621 }
3622
3623 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
3624    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
3625    than U, respectively.  */
3626
3627 int
3628 compare_tree_int (t, u)
3629      tree t;
3630      unsigned int u;
3631 {
3632   if (tree_int_cst_sgn (t) < 0)
3633     return -1;
3634   else if (TREE_INT_CST_HIGH (t) != 0)
3635     return 1;
3636   else if (TREE_INT_CST_LOW (t) == u)
3637     return 0;
3638   else if (TREE_INT_CST_LOW (t) < u)
3639     return -1;
3640   else
3641     return 1;
3642 }
3643 \f
3644 /* Constructors for pointer, array and function types.
3645    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
3646    constructed by language-dependent code, not here.)  */
3647
3648 /* Construct, lay out and return the type of pointers to TO_TYPE.
3649    If such a type has already been constructed, reuse it.  */
3650
3651 tree
3652 build_pointer_type (to_type)
3653      tree to_type;
3654 {
3655   register tree t = TYPE_POINTER_TO (to_type);
3656
3657   /* First, if we already have a type for pointers to TO_TYPE, use it.  */
3658
3659   if (t != 0)
3660     return t;
3661
3662   /* We need a new one.  */
3663   t = make_node (POINTER_TYPE);
3664
3665   TREE_TYPE (t) = to_type;
3666
3667   /* Record this type as the pointer to TO_TYPE.  */
3668   TYPE_POINTER_TO (to_type) = t;
3669
3670   /* Lay out the type.  This function has many callers that are concerned
3671      with expression-construction, and this simplifies them all.
3672      Also, it guarantees the TYPE_SIZE is in the same obstack as the type.  */
3673   layout_type (t);
3674
3675   return t;
3676 }
3677
3678 /* Build the node for the type of references-to-TO_TYPE.  */
3679
3680 tree
3681 build_reference_type (to_type)
3682      tree to_type;
3683 {
3684   register tree t = TYPE_REFERENCE_TO (to_type);
3685
3686   /* First, if we already have a type for pointers to TO_TYPE, use it.  */
3687
3688   if (t)
3689     return t;
3690
3691   /* We need a new one.  */
3692   t = make_node (REFERENCE_TYPE);
3693
3694   TREE_TYPE (t) = to_type;
3695
3696   /* Record this type as the pointer to TO_TYPE.  */
3697   TYPE_REFERENCE_TO (to_type) = t;
3698
3699   layout_type (t);
3700
3701   return t;
3702 }
3703
3704 /* Build a type that is compatible with t but has no cv quals anywhere
3705    in its type, thus
3706
3707    const char *const *const *  ->  char ***.  */
3708
3709 tree
3710 build_type_no_quals (t)
3711   tree t;
3712 {
3713   switch (TREE_CODE (t))
3714     {
3715     case POINTER_TYPE:
3716       return build_pointer_type (build_type_no_quals (TREE_TYPE (t)));
3717     case REFERENCE_TYPE:
3718       return build_reference_type (build_type_no_quals (TREE_TYPE (t)));
3719     default:
3720       return TYPE_MAIN_VARIANT (t);
3721     }
3722 }
3723
3724 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
3725    MAXVAL should be the maximum value in the domain
3726    (one less than the length of the array).
3727
3728    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
3729    We don't enforce this limit, that is up to caller (e.g. language front end).
3730    The limit exists because the result is a signed type and we don't handle
3731    sizes that use more than one HOST_WIDE_INT.  */
3732
3733 tree
3734 build_index_type (maxval)
3735      tree maxval;
3736 {
3737   register tree itype = make_node (INTEGER_TYPE);
3738
3739   TREE_TYPE (itype) = sizetype;
3740   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
3741   TYPE_MIN_VALUE (itype) = size_zero_node;
3742   TYPE_MAX_VALUE (itype) = convert (sizetype, maxval);
3743   TYPE_MODE (itype) = TYPE_MODE (sizetype);
3744   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
3745   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
3746   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
3747   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
3748
3749   if (host_integerp (maxval, 1))
3750     return type_hash_canon (tree_low_cst (maxval, 1), itype);
3751   else
3752     return itype;
3753 }
3754
3755 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
3756    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
3757    low bound LOWVAL and high bound HIGHVAL.
3758    if TYPE==NULL_TREE, sizetype is used.  */
3759
3760 tree
3761 build_range_type (type, lowval, highval)
3762      tree type, lowval, highval;
3763 {
3764   register tree itype = make_node (INTEGER_TYPE);
3765
3766   TREE_TYPE (itype) = type;
3767   if (type == NULL_TREE)
3768     type = sizetype;
3769
3770   TYPE_MIN_VALUE (itype) = convert (type, lowval);
3771   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
3772
3773   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
3774   TYPE_MODE (itype) = TYPE_MODE (type);
3775   TYPE_SIZE (itype) = TYPE_SIZE (type);
3776   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
3777   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
3778   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
3779
3780   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
3781     return type_hash_canon (tree_low_cst (highval, 0)
3782                             - tree_low_cst (lowval, 0),
3783                             itype);
3784   else
3785     return itype;
3786 }
3787
3788 /* Just like build_index_type, but takes lowval and highval instead
3789    of just highval (maxval).  */
3790
3791 tree
3792 build_index_2_type (lowval,highval)
3793      tree lowval, highval;
3794 {
3795   return build_range_type (sizetype, lowval, highval);
3796 }
3797
3798 /* Return nonzero iff ITYPE1 and ITYPE2 are equal (in the LISP sense).
3799    Needed because when index types are not hashed, equal index types
3800    built at different times appear distinct, even though structurally,
3801    they are not.  */
3802
3803 int
3804 index_type_equal (itype1, itype2)
3805      tree itype1, itype2;
3806 {
3807   if (TREE_CODE (itype1) != TREE_CODE (itype2))
3808     return 0;
3809
3810   if (TREE_CODE (itype1) == INTEGER_TYPE)
3811     {
3812       if (TYPE_PRECISION (itype1) != TYPE_PRECISION (itype2)
3813           || TYPE_MODE (itype1) != TYPE_MODE (itype2)
3814           || simple_cst_equal (TYPE_SIZE (itype1), TYPE_SIZE (itype2)) != 1
3815           || TYPE_ALIGN (itype1) != TYPE_ALIGN (itype2))
3816         return 0;
3817
3818       if (1 == simple_cst_equal (TYPE_MIN_VALUE (itype1),
3819                                  TYPE_MIN_VALUE (itype2))
3820           && 1 == simple_cst_equal (TYPE_MAX_VALUE (itype1),
3821                                     TYPE_MAX_VALUE (itype2)))
3822         return 1;
3823     }
3824
3825   return 0;
3826 }
3827
3828 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
3829    and number of elements specified by the range of values of INDEX_TYPE.
3830    If such a type has already been constructed, reuse it.  */
3831
3832 tree
3833 build_array_type (elt_type, index_type)
3834      tree elt_type, index_type;
3835 {
3836   register tree t;
3837   unsigned int hashcode;
3838
3839   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
3840     {
3841       error ("arrays of functions are not meaningful");
3842       elt_type = integer_type_node;
3843     }
3844
3845   /* Make sure TYPE_POINTER_TO (elt_type) is filled in.  */
3846   build_pointer_type (elt_type);
3847
3848   /* Allocate the array after the pointer type,
3849      in case we free it in type_hash_canon.  */
3850   t = make_node (ARRAY_TYPE);
3851   TREE_TYPE (t) = elt_type;
3852   TYPE_DOMAIN (t) = index_type;
3853
3854   if (index_type == 0)
3855     {
3856       return t;
3857     }
3858
3859   hashcode = TYPE_HASH (elt_type) + TYPE_HASH (index_type);
3860   t = type_hash_canon (hashcode, t);
3861
3862   if (!COMPLETE_TYPE_P (t))
3863     layout_type (t);
3864   return t;
3865 }
3866
3867 /* Return the TYPE of the elements comprising
3868    the innermost dimension of ARRAY.  */
3869
3870 tree
3871 get_inner_array_type (array)
3872     tree array;
3873 {
3874   tree type = TREE_TYPE (array);
3875
3876   while (TREE_CODE (type) == ARRAY_TYPE)
3877     type = TREE_TYPE (type);
3878
3879   return type;
3880 }
3881
3882 /* Construct, lay out and return
3883    the type of functions returning type VALUE_TYPE
3884    given arguments of types ARG_TYPES.
3885    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
3886    are data type nodes for the arguments of the function.
3887    If such a type has already been constructed, reuse it.  */
3888
3889 tree
3890 build_function_type (value_type, arg_types)
3891      tree value_type, arg_types;
3892 {
3893   register tree t;
3894   unsigned int hashcode;
3895
3896   if (TREE_CODE (value_type) == FUNCTION_TYPE)
3897     {
3898       error ("function return type cannot be function");
3899       value_type = integer_type_node;
3900     }
3901
3902   /* Make a node of the sort we want.  */
3903   t = make_node (FUNCTION_TYPE);
3904   TREE_TYPE (t) = value_type;
3905   TYPE_ARG_TYPES (t) = arg_types;
3906
3907   /* If we already have such a type, use the old one and free this one.  */
3908   hashcode = TYPE_HASH (value_type) + type_hash_list (arg_types);
3909   t = type_hash_canon (hashcode, t);
3910
3911   if (!COMPLETE_TYPE_P (t))
3912     layout_type (t);
3913   return t;
3914 }
3915
3916 /* Construct, lay out and return the type of methods belonging to class
3917    BASETYPE and whose arguments and values are described by TYPE.
3918    If that type exists already, reuse it.
3919    TYPE must be a FUNCTION_TYPE node.  */
3920
3921 tree
3922 build_method_type (basetype, type)
3923      tree basetype, type;
3924 {
3925   register tree t;
3926   unsigned int hashcode;
3927
3928   /* Make a node of the sort we want.  */
3929   t = make_node (METHOD_TYPE);
3930
3931   if (TREE_CODE (type) != FUNCTION_TYPE)
3932     abort ();
3933
3934   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
3935   TREE_TYPE (t) = TREE_TYPE (type);
3936
3937   /* The actual arglist for this function includes a "hidden" argument
3938      which is "this".  Put it into the list of argument types.  */
3939
3940   TYPE_ARG_TYPES (t)
3941     = tree_cons (NULL_TREE,
3942                  build_pointer_type (basetype), TYPE_ARG_TYPES (type));
3943
3944   /* If we already have such a type, use the old one and free this one.  */
3945   hashcode = TYPE_HASH (basetype) + TYPE_HASH (type);
3946   t = type_hash_canon (hashcode, t);
3947
3948   if (!COMPLETE_TYPE_P (t))
3949     layout_type (t);
3950
3951   return t;
3952 }
3953
3954 /* Construct, lay out and return the type of offsets to a value
3955    of type TYPE, within an object of type BASETYPE.
3956    If a suitable offset type exists already, reuse it.  */
3957
3958 tree
3959 build_offset_type (basetype, type)
3960      tree basetype, type;
3961 {
3962   register tree t;
3963   unsigned int hashcode;
3964
3965   /* Make a node of the sort we want.  */
3966   t = make_node (OFFSET_TYPE);
3967
3968   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
3969   TREE_TYPE (t) = type;
3970
3971   /* If we already have such a type, use the old one and free this one.  */
3972   hashcode = TYPE_HASH (basetype) + TYPE_HASH (type);
3973   t = type_hash_canon (hashcode, t);
3974
3975   if (!COMPLETE_TYPE_P (t))
3976     layout_type (t);
3977
3978   return t;
3979 }
3980
3981 /* Create a complex type whose components are COMPONENT_TYPE.  */
3982
3983 tree
3984 build_complex_type (component_type)
3985      tree component_type;
3986 {
3987   register tree t;
3988   unsigned int hashcode;
3989
3990   /* Make a node of the sort we want.  */
3991   t = make_node (COMPLEX_TYPE);
3992
3993   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
3994   set_type_quals (t, TYPE_QUALS (component_type));
3995
3996   /* If we already have such a type, use the old one and free this one.  */
3997   hashcode = TYPE_HASH (component_type);
3998   t = type_hash_canon (hashcode, t);
3999
4000   if (!COMPLETE_TYPE_P (t))
4001     layout_type (t);
4002
4003   /* If we are writing Dwarf2 output we need to create a name,
4004      since complex is a fundamental type.  */
4005   if (write_symbols == DWARF2_DEBUG && ! TYPE_NAME (t))
4006     {
4007       const char *name;
4008       if (component_type == char_type_node)
4009         name = "complex char";
4010       else if (component_type == signed_char_type_node)
4011         name = "complex signed char";
4012       else if (component_type == unsigned_char_type_node)
4013         name = "complex unsigned char";
4014       else if (component_type == short_integer_type_node)
4015         name = "complex short int";
4016       else if (component_type == short_unsigned_type_node)
4017         name = "complex short unsigned int";
4018       else if (component_type == integer_type_node)
4019         name = "complex int";
4020       else if (component_type == unsigned_type_node)
4021         name = "complex unsigned int";
4022       else if (component_type == long_integer_type_node)
4023         name = "complex long int";
4024       else if (component_type == long_unsigned_type_node)
4025         name = "complex long unsigned int";
4026       else if (component_type == long_long_integer_type_node)
4027         name = "complex long long int";
4028       else if (component_type == long_long_unsigned_type_node)
4029         name = "complex long long unsigned int";
4030       else
4031         name = 0;
4032
4033       if (name != 0)
4034         TYPE_NAME (t) = get_identifier (name);
4035     }
4036
4037   return t;
4038 }
4039 \f
4040 /* Return OP, stripped of any conversions to wider types as much as is safe.
4041    Converting the value back to OP's type makes a value equivalent to OP.
4042
4043    If FOR_TYPE is nonzero, we return a value which, if converted to
4044    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
4045
4046    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
4047    narrowest type that can hold the value, even if they don't exactly fit.
4048    Otherwise, bit-field references are changed to a narrower type
4049    only if they can be fetched directly from memory in that type.
4050
4051    OP must have integer, real or enumeral type.  Pointers are not allowed!
4052
4053    There are some cases where the obvious value we could return
4054    would regenerate to OP if converted to OP's type,
4055    but would not extend like OP to wider types.
4056    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
4057    For example, if OP is (unsigned short)(signed char)-1,
4058    we avoid returning (signed char)-1 if FOR_TYPE is int,
4059    even though extending that to an unsigned short would regenerate OP,
4060    since the result of extending (signed char)-1 to (int)
4061    is different from (int) OP.  */
4062
4063 tree
4064 get_unwidened (op, for_type)
4065      register tree op;
4066      tree for_type;
4067 {
4068   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
4069   register tree type = TREE_TYPE (op);
4070   register unsigned final_prec
4071     = TYPE_PRECISION (for_type != 0 ? for_type : type);
4072   register int uns
4073     = (for_type != 0 && for_type != type
4074        && final_prec > TYPE_PRECISION (type)
4075        && TREE_UNSIGNED (type));
4076   register tree win = op;
4077
4078   while (TREE_CODE (op) == NOP_EXPR)
4079     {
4080       register int bitschange
4081         = TYPE_PRECISION (TREE_TYPE (op))
4082           - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
4083
4084       /* Truncations are many-one so cannot be removed.
4085          Unless we are later going to truncate down even farther.  */
4086       if (bitschange < 0
4087           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
4088         break;
4089
4090       /* See what's inside this conversion.  If we decide to strip it,
4091          we will set WIN.  */
4092       op = TREE_OPERAND (op, 0);
4093
4094       /* If we have not stripped any zero-extensions (uns is 0),
4095          we can strip any kind of extension.
4096          If we have previously stripped a zero-extension,
4097          only zero-extensions can safely be stripped.
4098          Any extension can be stripped if the bits it would produce
4099          are all going to be discarded later by truncating to FOR_TYPE.  */
4100
4101       if (bitschange > 0)
4102         {
4103           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
4104             win = op;
4105           /* TREE_UNSIGNED says whether this is a zero-extension.
4106              Let's avoid computing it if it does not affect WIN
4107              and if UNS will not be needed again.  */
4108           if ((uns || TREE_CODE (op) == NOP_EXPR)
4109               && TREE_UNSIGNED (TREE_TYPE (op)))
4110             {
4111               uns = 1;
4112               win = op;
4113             }
4114         }
4115     }
4116
4117   if (TREE_CODE (op) == COMPONENT_REF
4118       /* Since type_for_size always gives an integer type.  */
4119       && TREE_CODE (type) != REAL_TYPE
4120       /* Don't crash if field not laid out yet.  */
4121       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4122       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4123     {
4124       unsigned int innerprec
4125         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4126
4127       type = type_for_size (innerprec, TREE_UNSIGNED (TREE_OPERAND (op, 1)));
4128
4129       /* We can get this structure field in the narrowest type it fits in.
4130          If FOR_TYPE is 0, do this only for a field that matches the
4131          narrower type exactly and is aligned for it
4132          The resulting extension to its nominal type (a fullword type)
4133          must fit the same conditions as for other extensions.  */
4134
4135       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4136           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
4137           && (! uns || final_prec <= innerprec
4138               || TREE_UNSIGNED (TREE_OPERAND (op, 1)))
4139           && type != 0)
4140         {
4141           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4142                        TREE_OPERAND (op, 1));
4143           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4144           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4145         }
4146     }
4147
4148   return win;
4149 }
4150 \f
4151 /* Return OP or a simpler expression for a narrower value
4152    which can be sign-extended or zero-extended to give back OP.
4153    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
4154    or 0 if the value should be sign-extended.  */
4155
4156 tree
4157 get_narrower (op, unsignedp_ptr)
4158      register tree op;
4159      int *unsignedp_ptr;
4160 {
4161   register int uns = 0;
4162   int first = 1;
4163   register tree win = op;
4164
4165   while (TREE_CODE (op) == NOP_EXPR)
4166     {
4167       register int bitschange
4168         = (TYPE_PRECISION (TREE_TYPE (op))
4169            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
4170
4171       /* Truncations are many-one so cannot be removed.  */
4172       if (bitschange < 0)
4173         break;
4174
4175       /* See what's inside this conversion.  If we decide to strip it,
4176          we will set WIN.  */
4177       op = TREE_OPERAND (op, 0);
4178
4179       if (bitschange > 0)
4180         {
4181           /* An extension: the outermost one can be stripped,
4182              but remember whether it is zero or sign extension.  */
4183           if (first)
4184             uns = TREE_UNSIGNED (TREE_TYPE (op));
4185           /* Otherwise, if a sign extension has been stripped,
4186              only sign extensions can now be stripped;
4187              if a zero extension has been stripped, only zero-extensions.  */
4188           else if (uns != TREE_UNSIGNED (TREE_TYPE (op)))
4189             break;
4190           first = 0;
4191         }
4192       else /* bitschange == 0 */
4193         {
4194           /* A change in nominal type can always be stripped, but we must
4195              preserve the unsignedness.  */
4196           if (first)
4197             uns = TREE_UNSIGNED (TREE_TYPE (op));
4198           first = 0;
4199         }
4200
4201       win = op;
4202     }
4203
4204   if (TREE_CODE (op) == COMPONENT_REF
4205       /* Since type_for_size always gives an integer type.  */
4206       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
4207       /* Ensure field is laid out already.  */
4208       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0)
4209     {
4210       unsigned HOST_WIDE_INT innerprec
4211         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4212       tree type = type_for_size (innerprec, TREE_UNSIGNED (op));
4213
4214       /* We can get this structure field in a narrower type that fits it,
4215          but the resulting extension to its nominal type (a fullword type)
4216          must satisfy the same conditions as for other extensions.
4217
4218          Do this only for fields that are aligned (not bit-fields),
4219          because when bit-field insns will be used there is no
4220          advantage in doing this.  */
4221
4222       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4223           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
4224           && (first || uns == TREE_UNSIGNED (TREE_OPERAND (op, 1)))
4225           && type != 0)
4226         {
4227           if (first)
4228             uns = TREE_UNSIGNED (TREE_OPERAND (op, 1));
4229           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4230                        TREE_OPERAND (op, 1));
4231           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4232           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4233         }
4234     }
4235   *unsignedp_ptr = uns;
4236   return win;
4237 }
4238 \f
4239 /* Nonzero if integer constant C has a value that is permissible
4240    for type TYPE (an INTEGER_TYPE).  */
4241
4242 int
4243 int_fits_type_p (c, type)
4244      tree c, type;
4245 {
4246   /* If the bounds of the type are integers, we can check ourselves.
4247      Otherwise,. use force_fit_type, which checks against the precision.  */
4248   if (TYPE_MAX_VALUE (type) != NULL_TREE
4249       && TYPE_MIN_VALUE (type) != NULL_TREE
4250       && TREE_CODE (TYPE_MAX_VALUE (type)) == INTEGER_CST
4251       && TREE_CODE (TYPE_MIN_VALUE (type)) == INTEGER_CST)
4252     {
4253       if (TREE_UNSIGNED (type))
4254         return (! INT_CST_LT_UNSIGNED (TYPE_MAX_VALUE (type), c)
4255                 && ! INT_CST_LT_UNSIGNED (c, TYPE_MIN_VALUE (type))
4256                 /* Negative ints never fit unsigned types.  */
4257                 && ! (TREE_INT_CST_HIGH (c) < 0
4258                       && ! TREE_UNSIGNED (TREE_TYPE (c))));
4259       else
4260         return (! INT_CST_LT (TYPE_MAX_VALUE (type), c)
4261                 && ! INT_CST_LT (c, TYPE_MIN_VALUE (type))
4262                 /* Unsigned ints with top bit set never fit signed types.  */
4263                 && ! (TREE_INT_CST_HIGH (c) < 0
4264                       && TREE_UNSIGNED (TREE_TYPE (c))));
4265     }
4266   else
4267     {
4268       c = copy_node (c);
4269       TREE_TYPE (c) = type;
4270       return !force_fit_type (c, 0);
4271     }
4272 }
4273
4274 /* Given a DECL or TYPE, return the scope in which it was declared, or
4275    NULL_TREE if there is no containing scope.  */
4276
4277 tree
4278 get_containing_scope (t)
4279      tree t;
4280 {
4281   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
4282 }
4283
4284 /* Return the innermost context enclosing DECL that is
4285    a FUNCTION_DECL, or zero if none.  */
4286
4287 tree
4288 decl_function_context (decl)
4289      tree decl;
4290 {
4291   tree context;
4292
4293   if (TREE_CODE (decl) == ERROR_MARK)
4294     return 0;
4295
4296   if (TREE_CODE (decl) == SAVE_EXPR)
4297     context = SAVE_EXPR_CONTEXT (decl);
4298
4299   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
4300      where we look up the function at runtime.  Such functions always take
4301      a first argument of type 'pointer to real context'.
4302
4303      C++ should really be fixed to use DECL_CONTEXT for the real context,
4304      and use something else for the "virtual context".  */
4305   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
4306     context
4307       = TYPE_MAIN_VARIANT
4308         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
4309   else
4310     context = DECL_CONTEXT (decl);
4311
4312   while (context && TREE_CODE (context) != FUNCTION_DECL)
4313     {
4314       if (TREE_CODE (context) == BLOCK)
4315         context = BLOCK_SUPERCONTEXT (context);
4316       else
4317         context = get_containing_scope (context);
4318     }
4319
4320   return context;
4321 }
4322
4323 /* Return the innermost context enclosing DECL that is
4324    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
4325    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
4326
4327 tree
4328 decl_type_context (decl)
4329      tree decl;
4330 {
4331   tree context = DECL_CONTEXT (decl);
4332
4333   while (context)
4334     {
4335       if (TREE_CODE (context) == RECORD_TYPE
4336           || TREE_CODE (context) == UNION_TYPE
4337           || TREE_CODE (context) == QUAL_UNION_TYPE)
4338         return context;
4339
4340       if (TREE_CODE (context) == TYPE_DECL
4341           || TREE_CODE (context) == FUNCTION_DECL)
4342         context = DECL_CONTEXT (context);
4343
4344       else if (TREE_CODE (context) == BLOCK)
4345         context = BLOCK_SUPERCONTEXT (context);
4346
4347       else
4348         /* Unhandled CONTEXT!?  */
4349         abort ();
4350     }
4351   return NULL_TREE;
4352 }
4353
4354 /* CALL is a CALL_EXPR.  Return the declaration for the function
4355    called, or NULL_TREE if the called function cannot be
4356    determined.  */
4357
4358 tree
4359 get_callee_fndecl (call)
4360      tree call;
4361 {
4362   tree addr;
4363
4364   /* It's invalid to call this function with anything but a
4365      CALL_EXPR.  */
4366   if (TREE_CODE (call) != CALL_EXPR)
4367     abort ();
4368
4369   /* The first operand to the CALL is the address of the function
4370      called.  */
4371   addr = TREE_OPERAND (call, 0);
4372
4373   STRIP_NOPS (addr);
4374
4375   /* If this is a readonly function pointer, extract its initial value.  */
4376   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
4377       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
4378       && DECL_INITIAL (addr))
4379     addr = DECL_INITIAL (addr);
4380
4381   /* If the address is just `&f' for some function `f', then we know
4382      that `f' is being called.  */
4383   if (TREE_CODE (addr) == ADDR_EXPR
4384       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
4385     return TREE_OPERAND (addr, 0);
4386
4387   /* We couldn't figure out what was being called.  */
4388   return NULL_TREE;
4389 }
4390
4391 /* Print debugging information about the obstack O, named STR.  */
4392
4393 void
4394 print_obstack_statistics (str, o)
4395      const char *str;
4396      struct obstack *o;
4397 {
4398   struct _obstack_chunk *chunk = o->chunk;
4399   int n_chunks = 1;
4400   int n_alloc = 0;
4401
4402   n_alloc += o->next_free - chunk->contents;
4403   chunk = chunk->prev;
4404   while (chunk)
4405     {
4406       n_chunks += 1;
4407       n_alloc += chunk->limit - &chunk->contents[0];
4408       chunk = chunk->prev;
4409     }
4410   fprintf (stderr, "obstack %s: %u bytes, %d chunks\n",
4411            str, n_alloc, n_chunks);
4412 }
4413
4414 /* Print debugging information about tree nodes generated during the compile,
4415    and any language-specific information.  */
4416
4417 void
4418 dump_tree_statistics ()
4419 {
4420 #ifdef GATHER_STATISTICS
4421   int i;
4422   int total_nodes, total_bytes;
4423 #endif
4424
4425   fprintf (stderr, "\n??? tree nodes created\n\n");
4426 #ifdef GATHER_STATISTICS
4427   fprintf (stderr, "Kind                  Nodes     Bytes\n");
4428   fprintf (stderr, "-------------------------------------\n");
4429   total_nodes = total_bytes = 0;
4430   for (i = 0; i < (int) all_kinds; i++)
4431     {
4432       fprintf (stderr, "%-20s %6d %9d\n", tree_node_kind_names[i],
4433                tree_node_counts[i], tree_node_sizes[i]);
4434       total_nodes += tree_node_counts[i];
4435       total_bytes += tree_node_sizes[i];
4436     }
4437   fprintf (stderr, "%-20s        %9d\n", "identifier names", id_string_size);
4438   fprintf (stderr, "-------------------------------------\n");
4439   fprintf (stderr, "%-20s %6d %9d\n", "Total", total_nodes, total_bytes);
4440   fprintf (stderr, "-------------------------------------\n");
4441 #else
4442   fprintf (stderr, "(No per-node statistics)\n");
4443 #endif
4444   print_obstack_statistics ("permanent_obstack", &permanent_obstack);
4445   print_type_hash_statistics ();
4446   print_lang_statistics ();
4447 }
4448 \f
4449 #define FILE_FUNCTION_PREFIX_LEN 9
4450
4451 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
4452
4453 /* Appends 6 random characters to TEMPLATE to (hopefully) avoid name
4454    clashes in cases where we can't reliably choose a unique name.
4455
4456    Derived from mkstemp.c in libiberty.  */
4457
4458 static void
4459 append_random_chars (template)
4460      char *template;
4461 {
4462   static const char letters[]
4463     = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
4464   static unsigned HOST_WIDE_INT value;
4465   unsigned HOST_WIDE_INT v;
4466
4467 #ifdef HAVE_GETTIMEOFDAY
4468   struct timeval tv;
4469 #endif
4470
4471   template += strlen (template);
4472
4473 #ifdef HAVE_GETTIMEOFDAY
4474   /* Get some more or less random data.  */
4475   gettimeofday (&tv, NULL);
4476   value += ((unsigned HOST_WIDE_INT) tv.tv_usec << 16) ^ tv.tv_sec ^ getpid ();
4477 #else
4478   value += getpid ();
4479 #endif
4480
4481   v = value;
4482
4483   /* Fill in the random bits.  */
4484   template[0] = letters[v % 62];
4485   v /= 62;
4486   template[1] = letters[v % 62];
4487   v /= 62;
4488   template[2] = letters[v % 62];
4489   v /= 62;
4490   template[3] = letters[v % 62];
4491   v /= 62;
4492   template[4] = letters[v % 62];
4493   v /= 62;
4494   template[5] = letters[v % 62];
4495
4496   template[6] = '\0';
4497 }
4498
4499 /* P is a string that will be used in a symbol.  Mask out any characters
4500    that are not valid in that context.  */
4501
4502 void
4503 clean_symbol_name (p)
4504      char *p;
4505 {
4506   for (; *p; p++)
4507     if (! (ISDIGIT(*p)
4508 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
4509             || *p == '$'
4510 #endif
4511 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
4512             || *p == '.'
4513 #endif
4514             || ISUPPER (*p)
4515             || ISLOWER (*p)))
4516       *p = '_';
4517 }
4518
4519 /* Generate a name for a function unique to this translation unit.
4520    TYPE is some string to identify the purpose of this function to the
4521    linker or collect2.  */
4522
4523 tree
4524 get_file_function_name_long (type)
4525      const char *type;
4526 {
4527   char *buf;
4528   const char *p;
4529   char *q;
4530
4531   if (first_global_object_name)
4532     p = first_global_object_name;
4533   else
4534     {
4535       /* We don't have anything that we know to be unique to this translation
4536          unit, so use what we do have and throw in some randomness.  */
4537
4538       const char *name = weak_global_object_name;
4539       const char *file = main_input_filename;
4540
4541       if (! name)
4542         name = "";
4543       if (! file)
4544         file = input_filename;
4545
4546       q = (char *) alloca (7 + strlen (name) + strlen (file));
4547
4548       sprintf (q, "%s%s", name, file);
4549       append_random_chars (q);
4550       p = q;
4551     }
4552
4553   buf = (char *) alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p)
4554                          + strlen (type));
4555
4556   /* Set up the name of the file-level functions we may need.
4557      Use a global object (which is already required to be unique over
4558      the program) rather than the file name (which imposes extra
4559      constraints).  */
4560   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
4561
4562   /* Don't need to pull weird characters out of global names.  */
4563   if (p != first_global_object_name)
4564     clean_symbol_name (buf + 11);
4565
4566   return get_identifier (buf);
4567 }
4568
4569 /* If KIND=='I', return a suitable global initializer (constructor) name.
4570    If KIND=='D', return a suitable global clean-up (destructor) name.  */
4571
4572 tree
4573 get_file_function_name (kind)
4574      int kind;
4575 {
4576   char p[2];
4577
4578   p[0] = kind;
4579   p[1] = 0;
4580
4581   return get_file_function_name_long (p);
4582 }
4583 \f
4584 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4585    The result is placed in BUFFER (which has length BIT_SIZE),
4586    with one bit in each char ('\000' or '\001').
4587
4588    If the constructor is constant, NULL_TREE is returned.
4589    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4590
4591 tree
4592 get_set_constructor_bits (init, buffer, bit_size)
4593      tree init;
4594      char *buffer;
4595      int bit_size;
4596 {
4597   int i;
4598   tree vals;
4599   HOST_WIDE_INT domain_min
4600     = tree_low_cst (TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (init))), 0);
4601   tree non_const_bits = NULL_TREE;
4602
4603   for (i = 0; i < bit_size; i++)
4604     buffer[i] = 0;
4605
4606   for (vals = TREE_OPERAND (init, 1);
4607        vals != NULL_TREE; vals = TREE_CHAIN (vals))
4608     {
4609       if (!host_integerp (TREE_VALUE (vals), 0)
4610           || (TREE_PURPOSE (vals) != NULL_TREE
4611               && !host_integerp (TREE_PURPOSE (vals), 0)))
4612         non_const_bits
4613           = tree_cons (TREE_PURPOSE (vals), TREE_VALUE (vals), non_const_bits);
4614       else if (TREE_PURPOSE (vals) != NULL_TREE)
4615         {
4616           /* Set a range of bits to ones.  */
4617           HOST_WIDE_INT lo_index
4618             = tree_low_cst (TREE_PURPOSE (vals), 0) - domain_min;
4619           HOST_WIDE_INT hi_index
4620             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4621
4622           if (lo_index < 0 || lo_index >= bit_size
4623               || hi_index < 0 || hi_index >= bit_size)
4624             abort ();
4625           for (; lo_index <= hi_index; lo_index++)
4626             buffer[lo_index] = 1;
4627         }
4628       else
4629         {
4630           /* Set a single bit to one.  */
4631           HOST_WIDE_INT index
4632             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4633           if (index < 0 || index >= bit_size)
4634             {
4635               error ("invalid initializer for bit string");
4636               return NULL_TREE;
4637             }
4638           buffer[index] = 1;
4639         }
4640     }
4641   return non_const_bits;
4642 }
4643
4644 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4645    The result is placed in BUFFER (which is an array of bytes).
4646    If the constructor is constant, NULL_TREE is returned.
4647    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4648
4649 tree
4650 get_set_constructor_bytes (init, buffer, wd_size)
4651      tree init;
4652      unsigned char *buffer;
4653      int wd_size;
4654 {
4655   int i;
4656   int set_word_size = BITS_PER_UNIT;
4657   int bit_size = wd_size * set_word_size;
4658   int bit_pos = 0;
4659   unsigned char *bytep = buffer;
4660   char *bit_buffer = (char *) alloca (bit_size);
4661   tree non_const_bits = get_set_constructor_bits (init, bit_buffer, bit_size);
4662
4663   for (i = 0; i < wd_size; i++)
4664     buffer[i] = 0;
4665
4666   for (i = 0; i < bit_size; i++)
4667     {
4668       if (bit_buffer[i])
4669         {
4670           if (BYTES_BIG_ENDIAN)
4671             *bytep |= (1 << (set_word_size - 1 - bit_pos));
4672           else
4673             *bytep |= 1 << bit_pos;
4674         }
4675       bit_pos++;
4676       if (bit_pos >= set_word_size)
4677         bit_pos = 0, bytep++;
4678     }
4679   return non_const_bits;
4680 }
4681 \f
4682 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
4683 /* Complain that the tree code of NODE does not match the expected CODE.
4684    FILE, LINE, and FUNCTION are of the caller.  */
4685
4686 void
4687 tree_check_failed (node, code, file, line, function)
4688      const tree node;
4689      enum tree_code code;
4690      const char *file;
4691      int line;
4692      const char *function;
4693 {
4694   internal_error ("Tree check: expected %s, have %s in %s, at %s:%d",
4695                   tree_code_name[code], tree_code_name[TREE_CODE (node)],
4696                   function, trim_filename (file), line);
4697 }
4698
4699 /* Similar to above, except that we check for a class of tree
4700    code, given in CL.  */
4701
4702 void
4703 tree_class_check_failed (node, cl, file, line, function)
4704      const tree node;
4705      int cl;
4706      const char *file;
4707      int line;
4708      const char *function;
4709 {
4710   internal_error
4711     ("Tree check: expected class '%c', have '%c' (%s) in %s, at %s:%d",
4712      cl, TREE_CODE_CLASS (TREE_CODE (node)),
4713      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
4714 }
4715
4716 #endif /* ENABLE_TREE_CHECKING */
4717 \f
4718 /* For a new vector type node T, build the information necessary for
4719    debuggint output.  */
4720
4721 static void
4722 finish_vector_type (t)
4723      tree t;
4724 {
4725   layout_type (t);
4726
4727   {
4728     tree index = build_int_2 (TYPE_VECTOR_SUBPARTS (t) - 1, 0);
4729     tree array = build_array_type (TREE_TYPE (t),
4730                                    build_index_type (index));
4731     tree rt = make_node (RECORD_TYPE);
4732
4733     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
4734     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
4735     layout_type (rt);
4736     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
4737     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
4738        the representation type, and we want to find that die when looking up
4739        the vector type.  This is most easily achieved by making the TYPE_UID
4740        numbers equal.  */
4741     TYPE_UID (rt) = TYPE_UID (t);
4742   }
4743 }
4744
4745 /* Create nodes for all integer types (and error_mark_node) using the sizes
4746    of C datatypes.  The caller should call set_sizetype soon after calling
4747    this function to select one of the types as sizetype.  */
4748
4749 void
4750 build_common_tree_nodes (signed_char)
4751      int signed_char;
4752 {
4753   error_mark_node = make_node (ERROR_MARK);
4754   TREE_TYPE (error_mark_node) = error_mark_node;
4755
4756   initialize_sizetypes ();
4757
4758   /* Define both `signed char' and `unsigned char'.  */
4759   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
4760   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
4761
4762   /* Define `char', which is like either `signed char' or `unsigned char'
4763      but not the same as either.  */
4764   char_type_node
4765     = (signed_char
4766        ? make_signed_type (CHAR_TYPE_SIZE)
4767        : make_unsigned_type (CHAR_TYPE_SIZE));
4768
4769   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
4770   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
4771   integer_type_node = make_signed_type (INT_TYPE_SIZE);
4772   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
4773   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
4774   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
4775   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
4776   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
4777
4778   intQI_type_node = make_signed_type (GET_MODE_BITSIZE (QImode));
4779   intHI_type_node = make_signed_type (GET_MODE_BITSIZE (HImode));
4780   intSI_type_node = make_signed_type (GET_MODE_BITSIZE (SImode));
4781   intDI_type_node = make_signed_type (GET_MODE_BITSIZE (DImode));
4782   intTI_type_node = make_signed_type (GET_MODE_BITSIZE (TImode));
4783
4784   unsigned_intQI_type_node = make_unsigned_type (GET_MODE_BITSIZE (QImode));
4785   unsigned_intHI_type_node = make_unsigned_type (GET_MODE_BITSIZE (HImode));
4786   unsigned_intSI_type_node = make_unsigned_type (GET_MODE_BITSIZE (SImode));
4787   unsigned_intDI_type_node = make_unsigned_type (GET_MODE_BITSIZE (DImode));
4788   unsigned_intTI_type_node = make_unsigned_type (GET_MODE_BITSIZE (TImode));
4789 }
4790
4791 /* Call this function after calling build_common_tree_nodes and set_sizetype.
4792    It will create several other common tree nodes.  */
4793
4794 void
4795 build_common_tree_nodes_2 (short_double)
4796      int short_double;
4797 {
4798   /* Define these next since types below may used them.  */
4799   integer_zero_node = build_int_2 (0, 0);
4800   integer_one_node = build_int_2 (1, 0);
4801   integer_minus_one_node = build_int_2 (-1, -1);
4802
4803   size_zero_node = size_int (0);
4804   size_one_node = size_int (1);
4805   bitsize_zero_node = bitsize_int (0);
4806   bitsize_one_node = bitsize_int (1);
4807   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
4808
4809   void_type_node = make_node (VOID_TYPE);
4810   layout_type (void_type_node);
4811
4812   /* We are not going to have real types in C with less than byte alignment,
4813      so we might as well not have any types that claim to have it.  */
4814   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
4815   TYPE_USER_ALIGN (void_type_node) = 0;
4816
4817   null_pointer_node = build_int_2 (0, 0);
4818   TREE_TYPE (null_pointer_node) = build_pointer_type (void_type_node);
4819   layout_type (TREE_TYPE (null_pointer_node));
4820
4821   ptr_type_node = build_pointer_type (void_type_node);
4822   const_ptr_type_node
4823     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
4824
4825   float_type_node = make_node (REAL_TYPE);
4826   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
4827   layout_type (float_type_node);
4828
4829   double_type_node = make_node (REAL_TYPE);
4830   if (short_double)
4831     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
4832   else
4833     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
4834   layout_type (double_type_node);
4835
4836   long_double_type_node = make_node (REAL_TYPE);
4837   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
4838   layout_type (long_double_type_node);
4839
4840   complex_integer_type_node = make_node (COMPLEX_TYPE);
4841   TREE_TYPE (complex_integer_type_node) = integer_type_node;
4842   layout_type (complex_integer_type_node);
4843
4844   complex_float_type_node = make_node (COMPLEX_TYPE);
4845   TREE_TYPE (complex_float_type_node) = float_type_node;
4846   layout_type (complex_float_type_node);
4847
4848   complex_double_type_node = make_node (COMPLEX_TYPE);
4849   TREE_TYPE (complex_double_type_node) = double_type_node;
4850   layout_type (complex_double_type_node);
4851
4852   complex_long_double_type_node = make_node (COMPLEX_TYPE);
4853   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
4854   layout_type (complex_long_double_type_node);
4855
4856   {
4857     tree t;
4858     BUILD_VA_LIST_TYPE (t);
4859
4860     /* Many back-ends define record types without seting TYPE_NAME.
4861        If we copied the record type here, we'd keep the original
4862        record type without a name.  This breaks name mangling.  So,
4863        don't copy record types and let c_common_nodes_and_builtins()
4864        declare the type to be __builtin_va_list.  */
4865     if (TREE_CODE (t) != RECORD_TYPE)
4866       t = build_type_copy (t);
4867
4868     va_list_type_node = t;
4869   }
4870
4871   V4SF_type_node = make_node (VECTOR_TYPE);
4872   TREE_TYPE (V4SF_type_node) = float_type_node;
4873   TYPE_MODE (V4SF_type_node) = V4SFmode;
4874   finish_vector_type (V4SF_type_node);
4875
4876   V4SI_type_node = make_node (VECTOR_TYPE);
4877   TREE_TYPE (V4SI_type_node) = intSI_type_node;
4878   TYPE_MODE (V4SI_type_node) = V4SImode;
4879   finish_vector_type (V4SI_type_node);
4880
4881   V2SI_type_node = make_node (VECTOR_TYPE);
4882   TREE_TYPE (V2SI_type_node) = intSI_type_node;
4883   TYPE_MODE (V2SI_type_node) = V2SImode;
4884   finish_vector_type (V2SI_type_node);
4885
4886   V4HI_type_node = make_node (VECTOR_TYPE);
4887   TREE_TYPE (V4HI_type_node) = intHI_type_node;
4888   TYPE_MODE (V4HI_type_node) = V4HImode;
4889   finish_vector_type (V4HI_type_node);
4890
4891   V8QI_type_node = make_node (VECTOR_TYPE);
4892   TREE_TYPE (V8QI_type_node) = intQI_type_node;
4893   TYPE_MODE (V8QI_type_node) = V8QImode;
4894   finish_vector_type (V8QI_type_node);
4895 }