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