gcc/tree.c

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