gcc/tree.c

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