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