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