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