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 PARM 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 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
1894           op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
1895           if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
1896             return exp;
1897
1898           new = fold (build (code, TREE_TYPE (exp), op0, op1));
1899           break;
1900
1901         case 3:
1902           /* It cannot be that anything inside a SAVE_EXPR contains a
1903              PLACEHOLDER_EXPR.  */
1904           if (code == SAVE_EXPR)
1905             return exp;
1906
1907           else if (code == CALL_EXPR)
1908             {
1909               op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
1910               if (op1 == TREE_OPERAND (exp, 1))
1911                 return exp;
1912
1913               return build (code, TREE_TYPE (exp),
1914                             TREE_OPERAND (exp, 0), op1, NULL_TREE);
1915             }
1916
1917           else if (code != COND_EXPR)
1918             abort ();
1919
1920           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
1921           op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
1922           op2 = substitute_in_expr (TREE_OPERAND (exp, 2), f, r);
1923           if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
1924               && op2 == TREE_OPERAND (exp, 2))
1925             return exp;
1926
1927           new = fold (build (code, TREE_TYPE (exp), op0, op1, op2));
1928           break;
1929
1930         default:
1931           abort ();
1932         }
1933
1934       break;
1935
1936     case 'r':
1937       switch (code)
1938         {
1939         case COMPONENT_REF:
1940           /* If this expression is getting a value from a PLACEHOLDER_EXPR
1941              and it is the right field, replace it with R.  */
1942           for (inner = TREE_OPERAND (exp, 0);
1943                TREE_CODE_CLASS (TREE_CODE (inner)) == 'r';
1944                inner = TREE_OPERAND (inner, 0))
1945             ;
1946           if (TREE_CODE (inner) == PLACEHOLDER_EXPR
1947               && TREE_OPERAND (exp, 1) == f)
1948             return r;
1949
1950           /* If this expression hasn't been completed let, leave it
1951              alone.  */
1952           if (TREE_CODE (inner) == PLACEHOLDER_EXPR
1953               && TREE_TYPE (inner) == 0)
1954             return exp;
1955
1956           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
1957           if (op0 == TREE_OPERAND (exp, 0))
1958             return exp;
1959
1960           new = fold (build (code, TREE_TYPE (exp), op0,
1961                              TREE_OPERAND (exp, 1)));
1962           break;
1963
1964         case BIT_FIELD_REF:
1965           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
1966           op1 = substitute_in_expr (TREE_OPERAND (exp, 1), f, r);
1967           op2 = substitute_in_expr (TREE_OPERAND (exp, 2), f, r);
1968           if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
1969               && op2 == TREE_OPERAND (exp, 2))
1970             return exp;
1971
1972           new = fold (build (code, TREE_TYPE (exp), op0, op1, op2));
1973           break;
1974
1975         case INDIRECT_REF:
1976         case BUFFER_REF:
1977           op0 = substitute_in_expr (TREE_OPERAND (exp, 0), f, r);
1978           if (op0 == TREE_OPERAND (exp, 0))
1979             return exp;
1980
1981           new = fold (build1 (code, TREE_TYPE (exp), op0));
1982           break;
1983
1984         default:
1985           abort ();
1986         }
1987       break;
1988
1989     default:
1990       abort ();
1991     }
1992
1993   TREE_READONLY (new) = TREE_READONLY (exp);
1994   return new;
1995 }
1996 \f
1997 /* Stabilize a reference so that we can use it any number of times
1998    without causing its operands to be evaluated more than once.
1999    Returns the stabilized reference.  This works by means of save_expr,
2000    so see the caveats in the comments about save_expr.
2001
2002    Also allows conversion expressions whose operands are references.
2003    Any other kind of expression is returned unchanged.  */
2004
2005 tree
2006 stabilize_reference (ref)
2007      tree ref;
2008 {
2009   tree result;
2010   enum tree_code code = TREE_CODE (ref);
2011
2012   switch (code)
2013     {
2014     case VAR_DECL:
2015     case PARM_DECL:
2016     case RESULT_DECL:
2017       /* No action is needed in this case.  */
2018       return ref;
2019
2020     case NOP_EXPR:
2021     case CONVERT_EXPR:
2022     case FLOAT_EXPR:
2023     case FIX_TRUNC_EXPR:
2024     case FIX_FLOOR_EXPR:
2025     case FIX_ROUND_EXPR:
2026     case FIX_CEIL_EXPR:
2027       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2028       break;
2029
2030     case INDIRECT_REF:
2031       result = build_nt (INDIRECT_REF,
2032                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2033       break;
2034
2035     case COMPONENT_REF:
2036       result = build_nt (COMPONENT_REF,
2037                          stabilize_reference (TREE_OPERAND (ref, 0)),
2038                          TREE_OPERAND (ref, 1));
2039       break;
2040
2041     case BIT_FIELD_REF:
2042       result = build_nt (BIT_FIELD_REF,
2043                          stabilize_reference (TREE_OPERAND (ref, 0)),
2044                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2045                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2046       break;
2047
2048     case ARRAY_REF:
2049       result = build_nt (ARRAY_REF,
2050                          stabilize_reference (TREE_OPERAND (ref, 0)),
2051                          stabilize_reference_1 (TREE_OPERAND (ref, 1)));
2052       break;
2053
2054     case ARRAY_RANGE_REF:
2055       result = build_nt (ARRAY_RANGE_REF,
2056                          stabilize_reference (TREE_OPERAND (ref, 0)),
2057                          stabilize_reference_1 (TREE_OPERAND (ref, 1)));
2058       break;
2059
2060     case COMPOUND_EXPR:
2061       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2062          it wouldn't be ignored.  This matters when dealing with
2063          volatiles.  */
2064       return stabilize_reference_1 (ref);
2065
2066     case RTL_EXPR:
2067       result = build1 (INDIRECT_REF, TREE_TYPE (ref),
2068                        save_expr (build1 (ADDR_EXPR,
2069                                           build_pointer_type (TREE_TYPE (ref)),
2070                                           ref)));
2071       break;
2072
2073       /* If arg isn't a kind of lvalue we recognize, make no change.
2074          Caller should recognize the error for an invalid lvalue.  */
2075     default:
2076       return ref;
2077
2078     case ERROR_MARK:
2079       return error_mark_node;
2080     }
2081
2082   TREE_TYPE (result) = TREE_TYPE (ref);
2083   TREE_READONLY (result) = TREE_READONLY (ref);
2084   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2085   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2086
2087   return result;
2088 }
2089
2090 /* Subroutine of stabilize_reference; this is called for subtrees of
2091    references.  Any expression with side-effects must be put in a SAVE_EXPR
2092    to ensure that it is only evaluated once.
2093
2094    We don't put SAVE_EXPR nodes around everything, because assigning very
2095    simple expressions to temporaries causes us to miss good opportunities
2096    for optimizations.  Among other things, the opportunity to fold in the
2097    addition of a constant into an addressing mode often gets lost, e.g.
2098    "y[i+1] += x;".  In general, we take the approach that we should not make
2099    an assignment unless we are forced into it - i.e., that any non-side effect
2100    operator should be allowed, and that cse should take care of coalescing
2101    multiple utterances of the same expression should that prove fruitful.  */
2102
2103 tree
2104 stabilize_reference_1 (e)
2105      tree e;
2106 {
2107   tree result;
2108   enum tree_code code = TREE_CODE (e);
2109
2110   /* We cannot ignore const expressions because it might be a reference
2111      to a const array but whose index contains side-effects.  But we can
2112      ignore things that are actual constant or that already have been
2113      handled by this function.  */
2114
2115   if (TREE_CONSTANT (e) || code == SAVE_EXPR)
2116     return e;
2117
2118   switch (TREE_CODE_CLASS (code))
2119     {
2120     case 'x':
2121     case 't':
2122     case 'd':
2123     case 'b':
2124     case '<':
2125     case 's':
2126     case 'e':
2127     case 'r':
2128       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2129          so that it will only be evaluated once.  */
2130       /* The reference (r) and comparison (<) classes could be handled as
2131          below, but it is generally faster to only evaluate them once.  */
2132       if (TREE_SIDE_EFFECTS (e))
2133         return save_expr (e);
2134       return e;
2135
2136     case 'c':
2137       /* Constants need no processing.  In fact, we should never reach
2138          here.  */
2139       return e;
2140
2141     case '2':
2142       /* Division is slow and tends to be compiled with jumps,
2143          especially the division by powers of 2 that is often
2144          found inside of an array reference.  So do it just once.  */
2145       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2146           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2147           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2148           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2149         return save_expr (e);
2150       /* Recursively stabilize each operand.  */
2151       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2152                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2153       break;
2154
2155     case '1':
2156       /* Recursively stabilize each operand.  */
2157       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2158       break;
2159
2160     default:
2161       abort ();
2162     }
2163
2164   TREE_TYPE (result) = TREE_TYPE (e);
2165   TREE_READONLY (result) = TREE_READONLY (e);
2166   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2167   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2168
2169   return result;
2170 }
2171 \f
2172 /* Low-level constructors for expressions.  */
2173
2174 /* Build an expression of code CODE, data type TYPE,
2175    and operands as specified by the arguments ARG1 and following arguments.
2176    Expressions and reference nodes can be created this way.
2177    Constants, decls, types and misc nodes cannot be.  */
2178
2179 tree
2180 build VPARAMS ((enum tree_code code, tree tt, ...))
2181 {
2182   tree t;
2183   int length;
2184   int i;
2185   int fro;
2186   int constant;
2187
2188   VA_OPEN (p, tt);
2189   VA_FIXEDARG (p, enum tree_code, code);
2190   VA_FIXEDARG (p, tree, tt);
2191
2192   t = make_node (code);
2193   length = TREE_CODE_LENGTH (code);
2194   TREE_TYPE (t) = tt;
2195
2196   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2197      result based on those same flags for the arguments.  But if the
2198      arguments aren't really even `tree' expressions, we shouldn't be trying
2199      to do this.  */
2200   fro = first_rtl_op (code);
2201
2202   /* Expressions without side effects may be constant if their
2203      arguments are as well.  */
2204   constant = (TREE_CODE_CLASS (code) == '<'
2205               || TREE_CODE_CLASS (code) == '1'
2206               || TREE_CODE_CLASS (code) == '2'
2207               || TREE_CODE_CLASS (code) == 'c');
2208
2209   if (length == 2)
2210     {
2211       /* This is equivalent to the loop below, but faster.  */
2212       tree arg0 = va_arg (p, tree);
2213       tree arg1 = va_arg (p, tree);
2214
2215       TREE_OPERAND (t, 0) = arg0;
2216       TREE_OPERAND (t, 1) = arg1;
2217       TREE_READONLY (t) = 1;
2218       if (arg0 && fro > 0)
2219         {
2220           if (TREE_SIDE_EFFECTS (arg0))
2221             TREE_SIDE_EFFECTS (t) = 1;
2222           if (!TREE_READONLY (arg0))
2223             TREE_READONLY (t) = 0;
2224           if (!TREE_CONSTANT (arg0))
2225             constant = 0;
2226         }
2227
2228       if (arg1 && fro > 1)
2229         {
2230           if (TREE_SIDE_EFFECTS (arg1))
2231             TREE_SIDE_EFFECTS (t) = 1;
2232           if (!TREE_READONLY (arg1))
2233             TREE_READONLY (t) = 0;
2234           if (!TREE_CONSTANT (arg1))
2235             constant = 0;
2236         }
2237     }
2238   else if (length == 1)
2239     {
2240       tree arg0 = va_arg (p, tree);
2241
2242       /* The only one-operand cases we handle here are those with side-effects.
2243          Others are handled with build1.  So don't bother checked if the
2244          arg has side-effects since we'll already have set it.
2245
2246          ??? This really should use build1 too.  */
2247       if (TREE_CODE_CLASS (code) != 's')
2248         abort ();
2249       TREE_OPERAND (t, 0) = arg0;
2250     }
2251   else
2252     {
2253       for (i = 0; i < length; i++)
2254         {
2255           tree operand = va_arg (p, tree);
2256
2257           TREE_OPERAND (t, i) = operand;
2258           if (operand && fro > i)
2259             {
2260               if (TREE_SIDE_EFFECTS (operand))
2261                 TREE_SIDE_EFFECTS (t) = 1;
2262               if (!TREE_CONSTANT (operand))
2263                 constant = 0;
2264             }
2265         }
2266     }
2267   VA_CLOSE (p);
2268
2269   TREE_CONSTANT (t) = constant;
2270   return t;
2271 }
2272
2273 /* Same as above, but only builds for unary operators.
2274    Saves lions share of calls to `build'; cuts down use
2275    of varargs, which is expensive for RISC machines.  */
2276
2277 tree
2278 build1 (code, type, node)
2279      enum tree_code code;
2280      tree type;
2281      tree node;
2282 {
2283   int length = sizeof (struct tree_exp);
2284 #ifdef GATHER_STATISTICS
2285   tree_node_kind kind;
2286 #endif
2287   tree t;
2288
2289 #ifdef GATHER_STATISTICS
2290   switch (TREE_CODE_CLASS (code))
2291     {
2292     case 's':  /* an expression with side effects */
2293       kind = s_kind;
2294       break;
2295     case 'r':  /* a reference */
2296       kind = r_kind;
2297       break;
2298     default:
2299       kind = e_kind;
2300       break;
2301     }
2302
2303   tree_node_counts[(int) kind]++;
2304   tree_node_sizes[(int) kind] += length;
2305 #endif
2306
2307 #ifdef ENABLE_CHECKING
2308   if (TREE_CODE_CLASS (code) == '2'
2309       || TREE_CODE_CLASS (code) == '<'
2310       || TREE_CODE_LENGTH (code) != 1)
2311     abort ();
2312 #endif /* ENABLE_CHECKING */
2313
2314   t = ggc_alloc_tree (length);
2315
2316   memset ((PTR) t, 0, sizeof (struct tree_common));
2317
2318   TREE_SET_CODE (t, code);
2319
2320   TREE_TYPE (t) = type;
2321   TREE_COMPLEXITY (t) = 0;
2322   TREE_OPERAND (t, 0) = node;
2323   if (node && first_rtl_op (code) != 0)
2324     {
2325       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2326       TREE_READONLY (t) = TREE_READONLY (node);
2327     }
2328
2329   if (TREE_CODE_CLASS (code) == 's')
2330     TREE_SIDE_EFFECTS (t) = 1;
2331   else switch (code)
2332     {
2333     case INIT_EXPR:
2334     case MODIFY_EXPR:
2335     case VA_ARG_EXPR:
2336     case RTL_EXPR:
2337     case PREDECREMENT_EXPR:
2338     case PREINCREMENT_EXPR:
2339     case POSTDECREMENT_EXPR:
2340     case POSTINCREMENT_EXPR:
2341       /* All of these have side-effects, no matter what their
2342          operands are.  */
2343       TREE_SIDE_EFFECTS (t) = 1;
2344       TREE_READONLY (t) = 0;
2345       break;
2346
2347     case INDIRECT_REF:
2348       /* Whether a dereference is readonly has nothing to do with whether
2349          its operand is readonly.  */
2350       TREE_READONLY (t) = 0;
2351       break;
2352
2353     default:
2354       if (TREE_CODE_CLASS (code) == '1' && node && TREE_CONSTANT (node))
2355         TREE_CONSTANT (t) = 1;
2356       break;
2357     }
2358
2359   return t;
2360 }
2361
2362 /* Similar except don't specify the TREE_TYPE
2363    and leave the TREE_SIDE_EFFECTS as 0.
2364    It is permissible for arguments to be null,
2365    or even garbage if their values do not matter.  */
2366
2367 tree
2368 build_nt VPARAMS ((enum tree_code code, ...))
2369 {
2370   tree t;
2371   int length;
2372   int i;
2373
2374   VA_OPEN (p, code);
2375   VA_FIXEDARG (p, enum tree_code, code);
2376
2377   t = make_node (code);
2378   length = TREE_CODE_LENGTH (code);
2379
2380   for (i = 0; i < length; i++)
2381     TREE_OPERAND (t, i) = va_arg (p, tree);
2382
2383   VA_CLOSE (p);
2384   return t;
2385 }
2386 \f
2387 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2388    We do NOT enter this node in any sort of symbol table.
2389
2390    layout_decl is used to set up the decl's storage layout.
2391    Other slots are initialized to 0 or null pointers.  */
2392
2393 tree
2394 build_decl (code, name, type)
2395      enum tree_code code;
2396      tree name, type;
2397 {
2398   tree t;
2399
2400   t = make_node (code);
2401
2402 /*  if (type == error_mark_node)
2403     type = integer_type_node; */
2404 /* That is not done, deliberately, so that having error_mark_node
2405    as the type can suppress useless errors in the use of this variable.  */
2406
2407   DECL_NAME (t) = name;
2408   TREE_TYPE (t) = type;
2409
2410   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2411     layout_decl (t, 0);
2412   else if (code == FUNCTION_DECL)
2413     DECL_MODE (t) = FUNCTION_MODE;
2414
2415   return t;
2416 }
2417 \f
2418 /* BLOCK nodes are used to represent the structure of binding contours
2419    and declarations, once those contours have been exited and their contents
2420    compiled.  This information is used for outputting debugging info.  */
2421
2422 tree
2423 build_block (vars, tags, subblocks, supercontext, chain)
2424      tree vars, tags ATTRIBUTE_UNUSED, subblocks, supercontext, chain;
2425 {
2426   tree block = make_node (BLOCK);
2427
2428   BLOCK_VARS (block) = vars;
2429   BLOCK_SUBBLOCKS (block) = subblocks;
2430   BLOCK_SUPERCONTEXT (block) = supercontext;
2431   BLOCK_CHAIN (block) = chain;
2432   return block;
2433 }
2434
2435 /* EXPR_WITH_FILE_LOCATION are used to keep track of the exact
2436    location where an expression or an identifier were encountered. It
2437    is necessary for languages where the frontend parser will handle
2438    recursively more than one file (Java is one of them).  */
2439
2440 tree
2441 build_expr_wfl (node, file, line, col)
2442      tree node;
2443      const char *file;
2444      int line, col;
2445 {
2446   static const char *last_file = 0;
2447   static tree last_filenode = NULL_TREE;
2448   tree wfl = make_node (EXPR_WITH_FILE_LOCATION);
2449
2450   EXPR_WFL_NODE (wfl) = node;
2451   EXPR_WFL_SET_LINECOL (wfl, line, col);
2452   if (file != last_file)
2453     {
2454       last_file = file;
2455       last_filenode = file ? get_identifier (file) : NULL_TREE;
2456     }
2457
2458   EXPR_WFL_FILENAME_NODE (wfl) = last_filenode;
2459   if (node)
2460     {
2461       TREE_SIDE_EFFECTS (wfl) = TREE_SIDE_EFFECTS (node);
2462       TREE_TYPE (wfl) = TREE_TYPE (node);
2463     }
2464
2465   return wfl;
2466 }
2467 \f
2468 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2469    is ATTRIBUTE.  */
2470
2471 tree
2472 build_decl_attribute_variant (ddecl, attribute)
2473      tree ddecl, attribute;
2474 {
2475   DECL_ATTRIBUTES (ddecl) = attribute;
2476   return ddecl;
2477 }
2478
2479 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2480    is ATTRIBUTE.
2481
2482    Record such modified types already made so we don't make duplicates.  */
2483
2484 tree
2485 build_type_attribute_variant (ttype, attribute)
2486      tree ttype, attribute;
2487 {
2488   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2489     {
2490       unsigned int hashcode;
2491       tree ntype;
2492
2493       ntype = copy_node (ttype);
2494
2495       TYPE_POINTER_TO (ntype) = 0;
2496       TYPE_REFERENCE_TO (ntype) = 0;
2497       TYPE_ATTRIBUTES (ntype) = attribute;
2498
2499       /* Create a new main variant of TYPE.  */
2500       TYPE_MAIN_VARIANT (ntype) = ntype;
2501       TYPE_NEXT_VARIANT (ntype) = 0;
2502       set_type_quals (ntype, TYPE_UNQUALIFIED);
2503
2504       hashcode = (TYPE_HASH (TREE_CODE (ntype))
2505                   + TYPE_HASH (TREE_TYPE (ntype))
2506                   + attribute_hash_list (attribute));
2507
2508       switch (TREE_CODE (ntype))
2509         {
2510         case FUNCTION_TYPE:
2511           hashcode += TYPE_HASH (TYPE_ARG_TYPES (ntype));
2512           break;
2513         case ARRAY_TYPE:
2514           hashcode += TYPE_HASH (TYPE_DOMAIN (ntype));
2515           break;
2516         case INTEGER_TYPE:
2517           hashcode += TYPE_HASH (TYPE_MAX_VALUE (ntype));
2518           break;
2519         case REAL_TYPE:
2520           hashcode += TYPE_HASH (TYPE_PRECISION (ntype));
2521           break;
2522         default:
2523           break;
2524         }
2525
2526       ntype = type_hash_canon (hashcode, ntype);
2527       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
2528     }
2529
2530   return ttype;
2531 }
2532
2533 /* Return nonzero if IDENT is a valid name for attribute ATTR,
2534    or zero if not.
2535
2536    We try both `text' and `__text__', ATTR may be either one.  */
2537 /* ??? It might be a reasonable simplification to require ATTR to be only
2538    `text'.  One might then also require attribute lists to be stored in
2539    their canonicalized form.  */
2540
2541 int
2542 is_attribute_p (attr, ident)
2543      const char *attr;
2544      tree ident;
2545 {
2546   int ident_len, attr_len;
2547   const char *p;
2548
2549   if (TREE_CODE (ident) != IDENTIFIER_NODE)
2550     return 0;
2551
2552   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
2553     return 1;
2554
2555   p = IDENTIFIER_POINTER (ident);
2556   ident_len = strlen (p);
2557   attr_len = strlen (attr);
2558
2559   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
2560   if (attr[0] == '_')
2561     {
2562       if (attr[1] != '_'
2563           || attr[attr_len - 2] != '_'
2564           || attr[attr_len - 1] != '_')
2565         abort ();
2566       if (ident_len == attr_len - 4
2567           && strncmp (attr + 2, p, attr_len - 4) == 0)
2568         return 1;
2569     }
2570   else
2571     {
2572       if (ident_len == attr_len + 4
2573           && p[0] == '_' && p[1] == '_'
2574           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
2575           && strncmp (attr, p + 2, attr_len) == 0)
2576         return 1;
2577     }
2578
2579   return 0;
2580 }
2581
2582 /* Given an attribute name and a list of attributes, return a pointer to the
2583    attribute's list element if the attribute is part of the list, or NULL_TREE
2584    if not found.  If the attribute appears more than once, this only
2585    returns the first occurrence; the TREE_CHAIN of the return value should
2586    be passed back in if further occurrences are wanted.  */
2587
2588 tree
2589 lookup_attribute (attr_name, list)
2590      const char *attr_name;
2591      tree list;
2592 {
2593   tree l;
2594
2595   for (l = list; l; l = TREE_CHAIN (l))
2596     {
2597       if (TREE_CODE (TREE_PURPOSE (l)) != IDENTIFIER_NODE)
2598         abort ();
2599       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
2600         return l;
2601     }
2602
2603   return NULL_TREE;
2604 }
2605
2606 /* Return an attribute list that is the union of a1 and a2.  */
2607
2608 tree
2609 merge_attributes (a1, a2)
2610      tree a1, a2;
2611 {
2612   tree attributes;
2613
2614   /* Either one unset?  Take the set one.  */
2615
2616   if ((attributes = a1) == 0)
2617     attributes = a2;
2618
2619   /* One that completely contains the other?  Take it.  */
2620
2621   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
2622     {
2623       if (attribute_list_contained (a2, a1))
2624         attributes = a2;
2625       else
2626         {
2627           /* Pick the longest list, and hang on the other list.  */
2628
2629           if (list_length (a1) < list_length (a2))
2630             attributes = a2, a2 = a1;
2631
2632           for (; a2 != 0; a2 = TREE_CHAIN (a2))
2633             {
2634               tree a;
2635               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2636                                          attributes);
2637                    a != NULL_TREE;
2638                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2639                                          TREE_CHAIN (a)))
2640                 {
2641                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
2642                     break;
2643                 }
2644               if (a == NULL_TREE)
2645                 {
2646                   a1 = copy_node (a2);
2647                   TREE_CHAIN (a1) = attributes;
2648                   attributes = a1;
2649                 }
2650             }
2651         }
2652     }
2653   return attributes;
2654 }
2655
2656 /* Given types T1 and T2, merge their attributes and return
2657   the result.  */
2658
2659 tree
2660 merge_type_attributes (t1, t2)
2661      tree t1, t2;
2662 {
2663   return merge_attributes (TYPE_ATTRIBUTES (t1),
2664                            TYPE_ATTRIBUTES (t2));
2665 }
2666
2667 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
2668    the result.  */
2669
2670 tree
2671 merge_decl_attributes (olddecl, newdecl)
2672      tree olddecl, newdecl;
2673 {
2674   return merge_attributes (DECL_ATTRIBUTES (olddecl),
2675                            DECL_ATTRIBUTES (newdecl));
2676 }
2677
2678 #ifdef TARGET_DLLIMPORT_DECL_ATTRIBUTES
2679
2680 /* Specialization of merge_decl_attributes for various Windows targets.
2681
2682    This handles the following situation:
2683
2684      __declspec (dllimport) int foo;
2685      int foo;
2686
2687    The second instance of `foo' nullifies the dllimport.  */
2688
2689 tree
2690 merge_dllimport_decl_attributes (old, new)
2691      tree old;
2692      tree new;
2693 {
2694   tree a;
2695   int delete_dllimport_p;
2696
2697   old = DECL_ATTRIBUTES (old);
2698   new = DECL_ATTRIBUTES (new);
2699
2700   /* What we need to do here is remove from `old' dllimport if it doesn't
2701      appear in `new'.  dllimport behaves like extern: if a declaration is
2702      marked dllimport and a definition appears later, then the object
2703      is not dllimport'd.  */
2704   if (lookup_attribute ("dllimport", old) != NULL_TREE
2705       && lookup_attribute ("dllimport", new) == NULL_TREE)
2706     delete_dllimport_p = 1;
2707   else
2708     delete_dllimport_p = 0;
2709
2710   a = merge_attributes (old, new);
2711
2712   if (delete_dllimport_p)
2713     {
2714       tree prev, t;
2715
2716       /* Scan the list for dllimport and delete it.  */
2717       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
2718         {
2719           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
2720             {
2721               if (prev == NULL_TREE)
2722                 a = TREE_CHAIN (a);
2723               else
2724                 TREE_CHAIN (prev) = TREE_CHAIN (t);
2725               break;
2726             }
2727         }
2728     }
2729
2730   return a;
2731 }
2732
2733 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
2734 \f
2735 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
2736    of the various TYPE_QUAL values.  */
2737
2738 static void
2739 set_type_quals (type, type_quals)
2740      tree type;
2741      int type_quals;
2742 {
2743   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
2744   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
2745   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
2746 }
2747
2748 /* Return a version of the TYPE, qualified as indicated by the
2749    TYPE_QUALS, if one exists.  If no qualified version exists yet,
2750    return NULL_TREE.  */
2751
2752 tree
2753 get_qualified_type (type, type_quals)
2754      tree type;
2755      int type_quals;
2756 {
2757   tree t;
2758
2759   /* Search the chain of variants to see if there is already one there just
2760      like the one we need to have.  If so, use that existing one.  We must
2761      preserve the TYPE_NAME, since there is code that depends on this.  */
2762   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
2763     if (TYPE_QUALS (t) == type_quals && TYPE_NAME (t) == TYPE_NAME (type)
2764         && TYPE_CONTEXT (t) == TYPE_CONTEXT (type))
2765       return t;
2766
2767   return NULL_TREE;
2768 }
2769
2770 /* Like get_qualified_type, but creates the type if it does not
2771    exist.  This function never returns NULL_TREE.  */
2772
2773 tree
2774 build_qualified_type (type, type_quals)
2775      tree type;
2776      int type_quals;
2777 {
2778   tree t;
2779
2780   /* See if we already have the appropriate qualified variant.  */
2781   t = get_qualified_type (type, type_quals);
2782
2783   /* If not, build it.  */
2784   if (!t)
2785     {
2786       t = build_type_copy (type);
2787       set_type_quals (t, type_quals);
2788     }
2789
2790   return t;
2791 }
2792
2793 /* Create a new variant of TYPE, equivalent but distinct.
2794    This is so the caller can modify it.  */
2795
2796 tree
2797 build_type_copy (type)
2798      tree type;
2799 {
2800   tree t, m = TYPE_MAIN_VARIANT (type);
2801
2802   t = copy_node (type);
2803
2804   TYPE_POINTER_TO (t) = 0;
2805   TYPE_REFERENCE_TO (t) = 0;
2806
2807   /* Add this type to the chain of variants of TYPE.  */
2808   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
2809   TYPE_NEXT_VARIANT (m) = t;
2810
2811   return t;
2812 }
2813 \f
2814 /* Hashing of types so that we don't make duplicates.
2815    The entry point is `type_hash_canon'.  */
2816
2817 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
2818    with types in the TREE_VALUE slots), by adding the hash codes
2819    of the individual types.  */
2820
2821 unsigned int
2822 type_hash_list (list)
2823      tree list;
2824 {
2825   unsigned int hashcode;
2826   tree tail;
2827
2828   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
2829     hashcode += TYPE_HASH (TREE_VALUE (tail));
2830
2831   return hashcode;
2832 }
2833
2834 /* These are the Hashtable callback functions.  */
2835
2836 /* Returns true if the types are equal.  */
2837
2838 static int
2839 type_hash_eq (va, vb)
2840      const void *va;
2841      const void *vb;
2842 {
2843   const struct type_hash *a = va, *b = vb;
2844   if (a->hash == b->hash
2845       && TREE_CODE (a->type) == TREE_CODE (b->type)
2846       && TREE_TYPE (a->type) == TREE_TYPE (b->type)
2847       && attribute_list_equal (TYPE_ATTRIBUTES (a->type),
2848                                TYPE_ATTRIBUTES (b->type))
2849       && TYPE_ALIGN (a->type) == TYPE_ALIGN (b->type)
2850       && (TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
2851           || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
2852                                  TYPE_MAX_VALUE (b->type)))
2853       && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
2854           || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
2855                                  TYPE_MIN_VALUE (b->type)))
2856       /* Note that TYPE_DOMAIN is TYPE_ARG_TYPES for FUNCTION_TYPE.  */
2857       && (TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type)
2858           || (TYPE_DOMAIN (a->type)
2859               && TREE_CODE (TYPE_DOMAIN (a->type)) == TREE_LIST
2860               && TYPE_DOMAIN (b->type)
2861               && TREE_CODE (TYPE_DOMAIN (b->type)) == TREE_LIST
2862               && type_list_equal (TYPE_DOMAIN (a->type),
2863                                   TYPE_DOMAIN (b->type)))))
2864     return 1;
2865   return 0;
2866 }
2867
2868 /* Return the cached hash value.  */
2869
2870 static hashval_t
2871 type_hash_hash (item)
2872      const void *item;
2873 {
2874   return ((const struct type_hash *) item)->hash;
2875 }
2876
2877 /* Look in the type hash table for a type isomorphic to TYPE.
2878    If one is found, return it.  Otherwise return 0.  */
2879
2880 tree
2881 type_hash_lookup (hashcode, type)
2882      unsigned int hashcode;
2883      tree type;
2884 {
2885   struct type_hash *h, in;
2886
2887   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
2888      must call that routine before comparing TYPE_ALIGNs.  */
2889   layout_type (type);
2890
2891   in.hash = hashcode;
2892   in.type = type;
2893
2894   h = htab_find_with_hash (type_hash_table, &in, hashcode);
2895   if (h)
2896     return h->type;
2897   return NULL_TREE;
2898 }
2899
2900 /* Add an entry to the type-hash-table
2901    for a type TYPE whose hash code is HASHCODE.  */
2902
2903 void
2904 type_hash_add (hashcode, type)
2905      unsigned int hashcode;
2906      tree type;
2907 {
2908   struct type_hash *h;
2909   void **loc;
2910
2911   h = (struct type_hash *) ggc_alloc (sizeof (struct type_hash));
2912   h->hash = hashcode;
2913   h->type = type;
2914   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
2915   *(struct type_hash **) loc = h;
2916 }
2917
2918 /* Given TYPE, and HASHCODE its hash code, return the canonical
2919    object for an identical type if one already exists.
2920    Otherwise, return TYPE, and record it as the canonical object
2921    if it is a permanent object.
2922
2923    To use this function, first create a type of the sort you want.
2924    Then compute its hash code from the fields of the type that
2925    make it different from other similar types.
2926    Then call this function and use the value.
2927    This function frees the type you pass in if it is a duplicate.  */
2928
2929 /* Set to 1 to debug without canonicalization.  Never set by program.  */
2930 int debug_no_type_hash = 0;
2931
2932 tree
2933 type_hash_canon (hashcode, type)
2934      unsigned int hashcode;
2935      tree type;
2936 {
2937   tree t1;
2938
2939   if (debug_no_type_hash)
2940     return type;
2941
2942   /* See if the type is in the hash table already.  If so, return it.
2943      Otherwise, add the type.  */
2944   t1 = type_hash_lookup (hashcode, type);
2945   if (t1 != 0)
2946     {
2947 #ifdef GATHER_STATISTICS
2948       tree_node_counts[(int) t_kind]--;
2949       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
2950 #endif
2951       return t1;
2952     }
2953   else
2954     {
2955       type_hash_add (hashcode, type);
2956       return type;
2957     }
2958 }
2959
2960 /* See if the data pointed to by the type hash table is marked.  We consider
2961    it marked if the type is marked or if a debug type number or symbol
2962    table entry has been made for the type.  This reduces the amount of
2963    debugging output and eliminates that dependency of the debug output on
2964    the number of garbage collections.  */
2965
2966 static int
2967 type_hash_marked_p (p)
2968      const void *p;
2969 {
2970   tree type = ((struct type_hash *) p)->type;
2971
2972   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
2973 }
2974
2975 static void
2976 print_type_hash_statistics ()
2977 {
2978   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
2979            (long) htab_size (type_hash_table),
2980            (long) htab_elements (type_hash_table),
2981            htab_collisions (type_hash_table));
2982 }
2983
2984 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
2985    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
2986    by adding the hash codes of the individual attributes.  */
2987
2988 unsigned int
2989 attribute_hash_list (list)
2990      tree list;
2991 {
2992   unsigned int hashcode;
2993   tree tail;
2994
2995   for (hashcode = 0, tail = list; tail; tail = TREE_CHAIN (tail))
2996     /* ??? Do we want to add in TREE_VALUE too? */
2997     hashcode += TYPE_HASH (TREE_PURPOSE (tail));
2998   return hashcode;
2999 }
3000
3001 /* Given two lists of attributes, return true if list l2 is
3002    equivalent to l1.  */
3003
3004 int
3005 attribute_list_equal (l1, l2)
3006      tree l1, l2;
3007 {
3008   return attribute_list_contained (l1, l2)
3009          && attribute_list_contained (l2, l1);
3010 }
3011
3012 /* Given two lists of attributes, return true if list L2 is
3013    completely contained within L1.  */
3014 /* ??? This would be faster if attribute names were stored in a canonicalized
3015    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3016    must be used to show these elements are equivalent (which they are).  */
3017 /* ??? It's not clear that attributes with arguments will always be handled
3018    correctly.  */
3019
3020 int
3021 attribute_list_contained (l1, l2)
3022      tree l1, l2;
3023 {
3024   tree t1, t2;
3025
3026   /* First check the obvious, maybe the lists are identical.  */
3027   if (l1 == l2)
3028     return 1;
3029
3030   /* Maybe the lists are similar.  */
3031   for (t1 = l1, t2 = l2;
3032        t1 != 0 && t2 != 0
3033         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3034         && TREE_VALUE (t1) == TREE_VALUE (t2);
3035        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3036
3037   /* Maybe the lists are equal.  */
3038   if (t1 == 0 && t2 == 0)
3039     return 1;
3040
3041   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3042     {
3043       tree attr;
3044       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3045            attr != NULL_TREE;
3046            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3047                                     TREE_CHAIN (attr)))
3048         {
3049           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3050             break;
3051         }
3052
3053       if (attr == 0)
3054         return 0;
3055
3056       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3057         return 0;
3058     }
3059
3060   return 1;
3061 }
3062
3063 /* Given two lists of types
3064    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3065    return 1 if the lists contain the same types in the same order.
3066    Also, the TREE_PURPOSEs must match.  */
3067
3068 int
3069 type_list_equal (l1, l2)
3070      tree l1, l2;
3071 {
3072   tree t1, t2;
3073
3074   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3075     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3076         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3077             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3078                   && (TREE_TYPE (TREE_PURPOSE (t1))
3079                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3080       return 0;
3081
3082   return t1 == t2;
3083 }
3084
3085 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3086    given by TYPE.  If the argument list accepts variable arguments,
3087    then this function counts only the ordinary arguments.  */
3088
3089 int
3090 type_num_arguments (type)
3091      tree type;
3092 {
3093   int i = 0;
3094   tree t;
3095
3096   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3097     /* If the function does not take a variable number of arguments,
3098        the last element in the list will have type `void'.  */
3099     if (VOID_TYPE_P (TREE_VALUE (t)))
3100       break;
3101     else
3102       ++i;
3103
3104   return i;
3105 }
3106
3107 /* Nonzero if integer constants T1 and T2
3108    represent the same constant value.  */
3109
3110 int
3111 tree_int_cst_equal (t1, t2)
3112      tree t1, t2;
3113 {
3114   if (t1 == t2)
3115     return 1;
3116
3117   if (t1 == 0 || t2 == 0)
3118     return 0;
3119
3120   if (TREE_CODE (t1) == INTEGER_CST
3121       && TREE_CODE (t2) == INTEGER_CST
3122       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3123       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3124     return 1;
3125
3126   return 0;
3127 }
3128
3129 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3130    The precise way of comparison depends on their data type.  */
3131
3132 int
3133 tree_int_cst_lt (t1, t2)
3134      tree t1, t2;
3135 {
3136   if (t1 == t2)
3137     return 0;
3138
3139   if (TREE_UNSIGNED (TREE_TYPE (t1)) != TREE_UNSIGNED (TREE_TYPE (t2)))
3140     {
3141       int t1_sgn = tree_int_cst_sgn (t1);
3142       int t2_sgn = tree_int_cst_sgn (t2);
3143
3144       if (t1_sgn < t2_sgn)
3145         return 1;
3146       else if (t1_sgn > t2_sgn)
3147         return 0;
3148       /* Otherwise, both are non-negative, so we compare them as
3149          unsigned just in case one of them would overflow a signed
3150          type.  */
3151     }
3152   else if (! TREE_UNSIGNED (TREE_TYPE (t1)))
3153     return INT_CST_LT (t1, t2);
3154
3155   return INT_CST_LT_UNSIGNED (t1, t2);
3156 }
3157
3158 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3159
3160 int
3161 tree_int_cst_compare (t1, t2)
3162      tree t1;
3163      tree t2;
3164 {
3165   if (tree_int_cst_lt (t1, t2))
3166     return -1;
3167   else if (tree_int_cst_lt (t2, t1))
3168     return 1;
3169   else
3170     return 0;
3171 }
3172
3173 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
3174    the host.  If POS is zero, the value can be represented in a single
3175    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
3176    be represented in a single unsigned HOST_WIDE_INT.  */
3177
3178 int
3179 host_integerp (t, pos)
3180      tree t;
3181      int pos;
3182 {
3183   return (TREE_CODE (t) == INTEGER_CST
3184           && ! TREE_OVERFLOW (t)
3185           && ((TREE_INT_CST_HIGH (t) == 0
3186                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3187               || (! pos && TREE_INT_CST_HIGH (t) == -1
3188                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
3189                   && ! TREE_UNSIGNED (TREE_TYPE (t)))
3190               || (pos && TREE_INT_CST_HIGH (t) == 0)));
3191 }
3192
3193 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3194    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3195    be positive.  Abort if we cannot satisfy the above conditions.  */
3196
3197 HOST_WIDE_INT
3198 tree_low_cst (t, pos)
3199      tree t;
3200      int pos;
3201 {
3202   if (host_integerp (t, pos))
3203     return TREE_INT_CST_LOW (t);
3204   else
3205     abort ();
3206 }
3207
3208 /* Return an indication of the sign of the integer constant T.
3209    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3210    Note that -1 will never be returned it T's type is unsigned.  */
3211
3212 int
3213 tree_int_cst_sgn (t)
3214      tree t;
3215 {
3216   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3217     return 0;
3218   else if (TREE_UNSIGNED (TREE_TYPE (t)))
3219     return 1;
3220   else if (TREE_INT_CST_HIGH (t) < 0)
3221     return -1;
3222   else
3223     return 1;
3224 }
3225
3226 /* Compare two constructor-element-type constants.  Return 1 if the lists
3227    are known to be equal; otherwise return 0.  */
3228
3229 int
3230 simple_cst_list_equal (l1, l2)
3231      tree l1, l2;
3232 {
3233   while (l1 != NULL_TREE && l2 != NULL_TREE)
3234     {
3235       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3236         return 0;
3237
3238       l1 = TREE_CHAIN (l1);
3239       l2 = TREE_CHAIN (l2);
3240     }
3241
3242   return l1 == l2;
3243 }
3244
3245 /* Return truthvalue of whether T1 is the same tree structure as T2.
3246    Return 1 if they are the same.
3247    Return 0 if they are understandably different.
3248    Return -1 if either contains tree structure not understood by
3249    this function.  */
3250
3251 int
3252 simple_cst_equal (t1, t2)
3253      tree t1, t2;
3254 {
3255   enum tree_code code1, code2;
3256   int cmp;
3257   int i;
3258
3259   if (t1 == t2)
3260     return 1;
3261   if (t1 == 0 || t2 == 0)
3262     return 0;
3263
3264   code1 = TREE_CODE (t1);
3265   code2 = TREE_CODE (t2);
3266
3267   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3268     {
3269       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3270           || code2 == NON_LVALUE_EXPR)
3271         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3272       else
3273         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3274     }
3275
3276   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3277            || code2 == NON_LVALUE_EXPR)
3278     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3279
3280   if (code1 != code2)
3281     return 0;
3282
3283   switch (code1)
3284     {
3285     case INTEGER_CST:
3286       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3287               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3288
3289     case REAL_CST:
3290       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3291
3292     case STRING_CST:
3293       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3294               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3295                          TREE_STRING_LENGTH (t1)));
3296
3297     case CONSTRUCTOR:
3298       if (CONSTRUCTOR_ELTS (t1) == CONSTRUCTOR_ELTS (t2))
3299         return 1;
3300       else
3301         abort ();
3302
3303     case SAVE_EXPR:
3304       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3305
3306     case CALL_EXPR:
3307       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3308       if (cmp <= 0)
3309         return cmp;
3310       return
3311         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3312
3313     case TARGET_EXPR:
3314       /* Special case: if either target is an unallocated VAR_DECL,
3315          it means that it's going to be unified with whatever the
3316          TARGET_EXPR is really supposed to initialize, so treat it
3317          as being equivalent to anything.  */
3318       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3319            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3320            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3321           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3322               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3323               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3324         cmp = 1;
3325       else
3326         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3327
3328       if (cmp <= 0)
3329         return cmp;
3330
3331       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3332
3333     case WITH_CLEANUP_EXPR:
3334       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3335       if (cmp <= 0)
3336         return cmp;
3337
3338       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3339
3340     case COMPONENT_REF:
3341       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3342         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3343
3344       return 0;
3345
3346     case VAR_DECL:
3347     case PARM_DECL:
3348     case CONST_DECL:
3349     case FUNCTION_DECL:
3350       return 0;
3351
3352     default:
3353       break;
3354     }
3355
3356   /* This general rule works for most tree codes.  All exceptions should be
3357      handled above.  If this is a language-specific tree code, we can't
3358      trust what might be in the operand, so say we don't know
3359      the situation.  */
3360   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3361     return -1;
3362
3363   switch (TREE_CODE_CLASS (code1))
3364     {
3365     case '1':
3366     case '2':
3367     case '<':
3368     case 'e':
3369     case 'r':
3370     case 's':
3371       cmp = 1;
3372       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3373         {
3374           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3375           if (cmp <= 0)
3376             return cmp;
3377         }
3378
3379       return cmp;
3380
3381     default:
3382       return -1;
3383     }
3384 }
3385
3386 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
3387    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
3388    than U, respectively.  */
3389
3390 int
3391 compare_tree_int (t, u)
3392      tree t;
3393      unsigned HOST_WIDE_INT u;
3394 {
3395   if (tree_int_cst_sgn (t) < 0)
3396     return -1;
3397   else if (TREE_INT_CST_HIGH (t) != 0)
3398     return 1;
3399   else if (TREE_INT_CST_LOW (t) == u)
3400     return 0;
3401   else if (TREE_INT_CST_LOW (t) < u)
3402     return -1;
3403   else
3404     return 1;
3405 }
3406 \f
3407 /* Constructors for pointer, array and function types.
3408    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
3409    constructed by language-dependent code, not here.)  */
3410
3411 /* Construct, lay out and return the type of pointers to TO_TYPE
3412    with mode MODE. If such a type has already been constructed,
3413    reuse it.  */
3414
3415 tree
3416 build_pointer_type_for_mode (to_type, mode)
3417      tree to_type;
3418      enum machine_mode mode;
3419 {
3420   tree t = TYPE_POINTER_TO (to_type);
3421
3422   /* First, if we already have a type for pointers to TO_TYPE, use it.  */
3423   if (t != 0 && mode == ptr_mode)
3424     return t;
3425
3426   t = make_node (POINTER_TYPE);
3427
3428   TREE_TYPE (t) = to_type;
3429   TYPE_MODE (t) = mode;
3430
3431   /* Record this type as the pointer to TO_TYPE.  */
3432   if (mode == ptr_mode)
3433   TYPE_POINTER_TO (to_type) = t;
3434
3435   /* Lay out the type.  This function has many callers that are concerned
3436      with expression-construction, and this simplifies them all.
3437      Also, it guarantees the TYPE_SIZE is in the same obstack as the type.  */
3438   layout_type (t);
3439
3440   return t;
3441 }
3442
3443 /* By default build pointers in ptr_mode.  */
3444
3445 tree
3446 build_pointer_type (to_type)
3447      tree to_type;
3448 {
3449   return build_pointer_type_for_mode (to_type, ptr_mode);
3450 }
3451
3452 /* Construct, lay out and return the type of references to TO_TYPE
3453    with mode MODE. If such a type has already been constructed,
3454    reuse it.  */
3455
3456 tree
3457 build_reference_type_for_mode (to_type, mode)
3458      tree to_type;
3459      enum machine_mode mode;
3460 {
3461   tree t = TYPE_REFERENCE_TO (to_type);
3462
3463   /* First, if we already have a type for pointers to TO_TYPE, use it.  */
3464   if (t != 0 && mode == ptr_mode)
3465     return t;
3466
3467   t = make_node (REFERENCE_TYPE);
3468
3469   TREE_TYPE (t) = to_type;
3470   TYPE_MODE (t) = mode;
3471
3472   /* Record this type as the pointer to TO_TYPE.  */
3473   if (mode == ptr_mode)
3474   TYPE_REFERENCE_TO (to_type) = t;
3475
3476   layout_type (t);
3477
3478   return t;
3479 }
3480
3481
3482 /* Build the node for the type of references-to-TO_TYPE by default
3483    in ptr_mode.  */
3484
3485 tree
3486 build_reference_type (to_type)
3487      tree to_type;
3488 {
3489   return build_reference_type_for_mode (to_type, ptr_mode);
3490 }
3491
3492 /* Build a type that is compatible with t but has no cv quals anywhere
3493    in its type, thus
3494
3495    const char *const *const *  ->  char ***.  */
3496
3497 tree
3498 build_type_no_quals (t)
3499      tree t;
3500 {
3501   switch (TREE_CODE (t))
3502     {
3503     case POINTER_TYPE:
3504       return build_pointer_type (build_type_no_quals (TREE_TYPE (t)));
3505     case REFERENCE_TYPE:
3506       return build_reference_type (build_type_no_quals (TREE_TYPE (t)));
3507     default:
3508       return TYPE_MAIN_VARIANT (t);
3509     }
3510 }
3511
3512 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
3513    MAXVAL should be the maximum value in the domain
3514    (one less than the length of the array).
3515
3516    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
3517    We don't enforce this limit, that is up to caller (e.g. language front end).
3518    The limit exists because the result is a signed type and we don't handle
3519    sizes that use more than one HOST_WIDE_INT.  */
3520
3521 tree
3522 build_index_type (maxval)
3523      tree maxval;
3524 {
3525   tree itype = make_node (INTEGER_TYPE);
3526
3527   TREE_TYPE (itype) = sizetype;
3528   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
3529   TYPE_MIN_VALUE (itype) = size_zero_node;
3530   TYPE_MAX_VALUE (itype) = convert (sizetype, maxval);
3531   TYPE_MODE (itype) = TYPE_MODE (sizetype);
3532   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
3533   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
3534   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
3535   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
3536
3537   if (host_integerp (maxval, 1))
3538     return type_hash_canon (tree_low_cst (maxval, 1), itype);
3539   else
3540     return itype;
3541 }
3542
3543 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
3544    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
3545    low bound LOWVAL and high bound HIGHVAL.
3546    if TYPE==NULL_TREE, sizetype is used.  */
3547
3548 tree
3549 build_range_type (type, lowval, highval)
3550      tree type, lowval, highval;
3551 {
3552   tree itype = make_node (INTEGER_TYPE);
3553
3554   TREE_TYPE (itype) = type;
3555   if (type == NULL_TREE)
3556     type = sizetype;
3557
3558   TYPE_MIN_VALUE (itype) = convert (type, lowval);
3559   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
3560
3561   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
3562   TYPE_MODE (itype) = TYPE_MODE (type);
3563   TYPE_SIZE (itype) = TYPE_SIZE (type);
3564   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
3565   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
3566   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
3567
3568   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
3569     return type_hash_canon (tree_low_cst (highval, 0)
3570                             - tree_low_cst (lowval, 0),
3571                             itype);
3572   else
3573     return itype;
3574 }
3575
3576 /* Just like build_index_type, but takes lowval and highval instead
3577    of just highval (maxval).  */
3578
3579 tree
3580 build_index_2_type (lowval, highval)
3581      tree lowval, highval;
3582 {
3583   return build_range_type (sizetype, lowval, highval);
3584 }
3585
3586 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
3587    and number of elements specified by the range of values of INDEX_TYPE.
3588    If such a type has already been constructed, reuse it.  */
3589
3590 tree
3591 build_array_type (elt_type, index_type)
3592      tree elt_type, index_type;
3593 {
3594   tree t;
3595   unsigned int hashcode;
3596
3597   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
3598     {
3599       error ("arrays of functions are not meaningful");
3600       elt_type = integer_type_node;
3601     }
3602
3603   /* Make sure TYPE_POINTER_TO (elt_type) is filled in.  */
3604   build_pointer_type (elt_type);
3605
3606   /* Allocate the array after the pointer type,
3607      in case we free it in type_hash_canon.  */
3608   t = make_node (ARRAY_TYPE);
3609   TREE_TYPE (t) = elt_type;
3610   TYPE_DOMAIN (t) = index_type;
3611
3612   if (index_type == 0)
3613     {
3614       return t;
3615     }
3616
3617   hashcode = TYPE_HASH (elt_type) + TYPE_HASH (index_type);
3618   t = type_hash_canon (hashcode, t);
3619
3620   if (!COMPLETE_TYPE_P (t))
3621     layout_type (t);
3622   return t;
3623 }
3624
3625 /* Return the TYPE of the elements comprising
3626    the innermost dimension of ARRAY.  */
3627
3628 tree
3629 get_inner_array_type (array)
3630      tree array;
3631 {
3632   tree type = TREE_TYPE (array);
3633
3634   while (TREE_CODE (type) == ARRAY_TYPE)
3635     type = TREE_TYPE (type);
3636
3637   return type;
3638 }
3639
3640 /* Construct, lay out and return
3641    the type of functions returning type VALUE_TYPE
3642    given arguments of types ARG_TYPES.
3643    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
3644    are data type nodes for the arguments of the function.
3645    If such a type has already been constructed, reuse it.  */
3646
3647 tree
3648 build_function_type (value_type, arg_types)
3649      tree value_type, arg_types;
3650 {
3651   tree t;
3652   unsigned int hashcode;
3653
3654   if (TREE_CODE (value_type) == FUNCTION_TYPE)
3655     {
3656       error ("function return type cannot be function");
3657       value_type = integer_type_node;
3658     }
3659
3660   /* Make a node of the sort we want.  */
3661   t = make_node (FUNCTION_TYPE);
3662   TREE_TYPE (t) = value_type;
3663   TYPE_ARG_TYPES (t) = arg_types;
3664
3665   /* If we already have such a type, use the old one and free this one.  */
3666   hashcode = TYPE_HASH (value_type) + type_hash_list (arg_types);
3667   t = type_hash_canon (hashcode, t);
3668
3669   if (!COMPLETE_TYPE_P (t))
3670     layout_type (t);
3671   return t;
3672 }
3673
3674 /* Build a function type.  The RETURN_TYPE is the type retured by the
3675    function.  If additional arguments are provided, they are
3676    additional argument types.  The list of argument types must always
3677    be terminated by NULL_TREE.  */
3678
3679 tree
3680 build_function_type_list VPARAMS ((tree return_type, ...))
3681 {
3682   tree t, args, last;
3683
3684   VA_OPEN (p, return_type);
3685   VA_FIXEDARG (p, tree, return_type);
3686
3687   t = va_arg (p, tree);
3688   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
3689     args = tree_cons (NULL_TREE, t, args);
3690
3691   last = args;
3692   args = nreverse (args);
3693   TREE_CHAIN (last) = void_list_node;
3694   args = build_function_type (return_type, args);
3695
3696   VA_CLOSE (p);
3697   return args;
3698 }
3699
3700 /* Construct, lay out and return the type of methods belonging to class
3701    BASETYPE and whose arguments and values are described by TYPE.
3702    If that type exists already, reuse it.
3703    TYPE must be a FUNCTION_TYPE node.  */
3704
3705 tree
3706 build_method_type (basetype, type)
3707      tree basetype, type;
3708 {
3709   tree t;
3710   unsigned int hashcode;
3711
3712   /* Make a node of the sort we want.  */
3713   t = make_node (METHOD_TYPE);
3714
3715   if (TREE_CODE (type) != FUNCTION_TYPE)
3716     abort ();
3717
3718   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
3719   TREE_TYPE (t) = TREE_TYPE (type);
3720
3721   /* The actual arglist for this function includes a "hidden" argument
3722      which is "this".  Put it into the list of argument types.  */
3723
3724   TYPE_ARG_TYPES (t)
3725     = tree_cons (NULL_TREE,
3726                  build_pointer_type (basetype), TYPE_ARG_TYPES (type));
3727
3728   /* If we already have such a type, use the old one and free this one.  */
3729   hashcode = TYPE_HASH (basetype) + TYPE_HASH (type);
3730   t = type_hash_canon (hashcode, t);
3731
3732   if (!COMPLETE_TYPE_P (t))
3733     layout_type (t);
3734
3735   return t;
3736 }
3737
3738 /* Construct, lay out and return the type of offsets to a value
3739    of type TYPE, within an object of type BASETYPE.
3740    If a suitable offset type exists already, reuse it.  */
3741
3742 tree
3743 build_offset_type (basetype, type)
3744      tree basetype, type;
3745 {
3746   tree t;
3747   unsigned int hashcode;
3748
3749   /* Make a node of the sort we want.  */
3750   t = make_node (OFFSET_TYPE);
3751
3752   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
3753   TREE_TYPE (t) = type;
3754
3755   /* If we already have such a type, use the old one and free this one.  */
3756   hashcode = TYPE_HASH (basetype) + TYPE_HASH (type);
3757   t = type_hash_canon (hashcode, t);
3758
3759   if (!COMPLETE_TYPE_P (t))
3760     layout_type (t);
3761
3762   return t;
3763 }
3764
3765 /* Create a complex type whose components are COMPONENT_TYPE.  */
3766
3767 tree
3768 build_complex_type (component_type)
3769      tree component_type;
3770 {
3771   tree t;
3772   unsigned int hashcode;
3773
3774   /* Make a node of the sort we want.  */
3775   t = make_node (COMPLEX_TYPE);
3776
3777   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
3778   set_type_quals (t, TYPE_QUALS (component_type));
3779
3780   /* If we already have such a type, use the old one and free this one.  */
3781   hashcode = TYPE_HASH (component_type);
3782   t = type_hash_canon (hashcode, t);
3783
3784   if (!COMPLETE_TYPE_P (t))
3785     layout_type (t);
3786
3787   /* If we are writing Dwarf2 output we need to create a name,
3788      since complex is a fundamental type.  */
3789   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
3790       && ! TYPE_NAME (t))
3791     {
3792       const char *name;
3793       if (component_type == char_type_node)
3794         name = "complex char";
3795       else if (component_type == signed_char_type_node)
3796         name = "complex signed char";
3797       else if (component_type == unsigned_char_type_node)
3798         name = "complex unsigned char";
3799       else if (component_type == short_integer_type_node)
3800         name = "complex short int";
3801       else if (component_type == short_unsigned_type_node)
3802         name = "complex short unsigned int";
3803       else if (component_type == integer_type_node)
3804         name = "complex int";
3805       else if (component_type == unsigned_type_node)
3806         name = "complex unsigned int";
3807       else if (component_type == long_integer_type_node)
3808         name = "complex long int";
3809       else if (component_type == long_unsigned_type_node)
3810         name = "complex long unsigned int";
3811       else if (component_type == long_long_integer_type_node)
3812         name = "complex long long int";
3813       else if (component_type == long_long_unsigned_type_node)
3814         name = "complex long long unsigned int";
3815       else
3816         name = 0;
3817
3818       if (name != 0)
3819         TYPE_NAME (t) = get_identifier (name);
3820     }
3821
3822   return t;
3823 }
3824 \f
3825 /* Return OP, stripped of any conversions to wider types as much as is safe.
3826    Converting the value back to OP's type makes a value equivalent to OP.
3827
3828    If FOR_TYPE is nonzero, we return a value which, if converted to
3829    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
3830
3831    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
3832    narrowest type that can hold the value, even if they don't exactly fit.
3833    Otherwise, bit-field references are changed to a narrower type
3834    only if they can be fetched directly from memory in that type.
3835
3836    OP must have integer, real or enumeral type.  Pointers are not allowed!
3837
3838    There are some cases where the obvious value we could return
3839    would regenerate to OP if converted to OP's type,
3840    but would not extend like OP to wider types.
3841    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
3842    For example, if OP is (unsigned short)(signed char)-1,
3843    we avoid returning (signed char)-1 if FOR_TYPE is int,
3844    even though extending that to an unsigned short would regenerate OP,
3845    since the result of extending (signed char)-1 to (int)
3846    is different from (int) OP.  */
3847
3848 tree
3849 get_unwidened (op, for_type)
3850      tree op;
3851      tree for_type;
3852 {
3853   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
3854   tree type = TREE_TYPE (op);
3855   unsigned final_prec
3856     = TYPE_PRECISION (for_type != 0 ? for_type : type);
3857   int uns
3858     = (for_type != 0 && for_type != type
3859        && final_prec > TYPE_PRECISION (type)
3860        && TREE_UNSIGNED (type));
3861   tree win = op;
3862
3863   while (TREE_CODE (op) == NOP_EXPR)
3864     {
3865       int bitschange
3866         = TYPE_PRECISION (TREE_TYPE (op))
3867           - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
3868
3869       /* Truncations are many-one so cannot be removed.
3870          Unless we are later going to truncate down even farther.  */
3871       if (bitschange < 0
3872           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
3873         break;
3874
3875       /* See what's inside this conversion.  If we decide to strip it,
3876          we will set WIN.  */
3877       op = TREE_OPERAND (op, 0);
3878
3879       /* If we have not stripped any zero-extensions (uns is 0),
3880          we can strip any kind of extension.
3881          If we have previously stripped a zero-extension,
3882          only zero-extensions can safely be stripped.
3883          Any extension can be stripped if the bits it would produce
3884          are all going to be discarded later by truncating to FOR_TYPE.  */
3885
3886       if (bitschange > 0)
3887         {
3888           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
3889             win = op;
3890           /* TREE_UNSIGNED says whether this is a zero-extension.
3891              Let's avoid computing it if it does not affect WIN
3892              and if UNS will not be needed again.  */
3893           if ((uns || TREE_CODE (op) == NOP_EXPR)
3894               && TREE_UNSIGNED (TREE_TYPE (op)))
3895             {
3896               uns = 1;
3897               win = op;
3898             }
3899         }
3900     }
3901
3902   if (TREE_CODE (op) == COMPONENT_REF
3903       /* Since type_for_size always gives an integer type.  */
3904       && TREE_CODE (type) != REAL_TYPE
3905       /* Don't crash if field not laid out yet.  */
3906       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
3907       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
3908     {
3909       unsigned int innerprec
3910         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
3911       int unsignedp = TREE_UNSIGNED (TREE_OPERAND (op, 1));
3912       type = (*lang_hooks.types.type_for_size) (innerprec, unsignedp);
3913
3914       /* We can get this structure field in the narrowest type it fits in.
3915          If FOR_TYPE is 0, do this only for a field that matches the
3916          narrower type exactly and is aligned for it
3917          The resulting extension to its nominal type (a fullword type)
3918          must fit the same conditions as for other extensions.  */
3919
3920       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
3921           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
3922           && (! uns || final_prec <= innerprec || unsignedp)
3923           && type != 0)
3924         {
3925           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
3926                        TREE_OPERAND (op, 1));
3927           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
3928           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
3929         }
3930     }
3931
3932   return win;
3933 }
3934 \f
3935 /* Return OP or a simpler expression for a narrower value
3936    which can be sign-extended or zero-extended to give back OP.
3937    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
3938    or 0 if the value should be sign-extended.  */
3939
3940 tree
3941 get_narrower (op, unsignedp_ptr)
3942      tree op;
3943      int *unsignedp_ptr;
3944 {
3945   int uns = 0;
3946   int first = 1;
3947   tree win = op;
3948
3949   while (TREE_CODE (op) == NOP_EXPR)
3950     {
3951       int bitschange
3952         = (TYPE_PRECISION (TREE_TYPE (op))
3953            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
3954
3955       /* Truncations are many-one so cannot be removed.  */
3956       if (bitschange < 0)
3957         break;
3958
3959       /* See what's inside this conversion.  If we decide to strip it,
3960          we will set WIN.  */
3961       op = TREE_OPERAND (op, 0);
3962
3963       if (bitschange > 0)
3964         {
3965           /* An extension: the outermost one can be stripped,
3966              but remember whether it is zero or sign extension.  */
3967           if (first)
3968             uns = TREE_UNSIGNED (TREE_TYPE (op));
3969           /* Otherwise, if a sign extension has been stripped,
3970              only sign extensions can now be stripped;
3971              if a zero extension has been stripped, only zero-extensions.  */
3972           else if (uns != TREE_UNSIGNED (TREE_TYPE (op)))
3973             break;
3974           first = 0;
3975         }
3976       else /* bitschange == 0 */
3977         {
3978           /* A change in nominal type can always be stripped, but we must
3979              preserve the unsignedness.  */
3980           if (first)
3981             uns = TREE_UNSIGNED (TREE_TYPE (op));
3982           first = 0;
3983         }
3984
3985       win = op;
3986     }
3987
3988   if (TREE_CODE (op) == COMPONENT_REF
3989       /* Since type_for_size always gives an integer type.  */
3990       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
3991       /* Ensure field is laid out already.  */
3992       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0)
3993     {
3994       unsigned HOST_WIDE_INT innerprec
3995         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
3996       tree type = (*lang_hooks.types.type_for_size) (innerprec,
3997                                                      TREE_UNSIGNED (op));
3998
3999       /* We can get this structure field in a narrower type that fits it,
4000          but the resulting extension to its nominal type (a fullword type)
4001          must satisfy the same conditions as for other extensions.
4002
4003          Do this only for fields that are aligned (not bit-fields),
4004          because when bit-field insns will be used there is no
4005          advantage in doing this.  */
4006
4007       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4008           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
4009           && (first || uns == TREE_UNSIGNED (TREE_OPERAND (op, 1)))
4010           && type != 0)
4011         {
4012           if (first)
4013             uns = TREE_UNSIGNED (TREE_OPERAND (op, 1));
4014           win = build (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4015                        TREE_OPERAND (op, 1));
4016           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4017           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4018         }
4019     }
4020   *unsignedp_ptr = uns;
4021   return win;
4022 }
4023 \f
4024 /* Nonzero if integer constant C has a value that is permissible
4025    for type TYPE (an INTEGER_TYPE).  */
4026
4027 int
4028 int_fits_type_p (c, type)
4029      tree c, type;
4030 {
4031   /* If the bounds of the type are integers, we can check ourselves.
4032      If not, but this type is a subtype, try checking against that.
4033      Otherwise, use force_fit_type, which checks against the precision.  */
4034   if (TYPE_MAX_VALUE (type) != NULL_TREE
4035       && TYPE_MIN_VALUE (type) != NULL_TREE
4036       && TREE_CODE (TYPE_MAX_VALUE (type)) == INTEGER_CST
4037       && TREE_CODE (TYPE_MIN_VALUE (type)) == INTEGER_CST)
4038     {
4039       if (TREE_UNSIGNED (type))
4040         return (! INT_CST_LT_UNSIGNED (TYPE_MAX_VALUE (type), c)
4041                 && ! INT_CST_LT_UNSIGNED (c, TYPE_MIN_VALUE (type))
4042                 /* Negative ints never fit unsigned types.  */
4043                 && ! (TREE_INT_CST_HIGH (c) < 0
4044                       && ! TREE_UNSIGNED (TREE_TYPE (c))));
4045       else
4046         return (! INT_CST_LT (TYPE_MAX_VALUE (type), c)
4047                 && ! INT_CST_LT (c, TYPE_MIN_VALUE (type))
4048                 /* Unsigned ints with top bit set never fit signed types.  */
4049                 && ! (TREE_INT_CST_HIGH (c) < 0
4050                       && TREE_UNSIGNED (TREE_TYPE (c))));
4051     }
4052   else if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != 0)
4053     return int_fits_type_p (c, TREE_TYPE (type));
4054   else
4055     {
4056       c = copy_node (c);
4057       TREE_TYPE (c) = type;
4058       return !force_fit_type (c, 0);
4059     }
4060 }
4061
4062 /* Returns true if T is, contains, or refers to a type with variable
4063    size.  This concept is more general than that of C99 'variably
4064    modified types': in C99, a struct type is never variably modified
4065    because a VLA may not appear as a structure member.  However, in
4066    GNU C code like:
4067
4068      struct S { int i[f()]; };
4069
4070    is valid, and other languages may define similar constructs.  */
4071
4072 bool
4073 variably_modified_type_p (type)
4074      tree type;
4075 {
4076   if (type == error_mark_node)
4077     return false;
4078
4079   /* If TYPE itself has variable size, it is variably modified.
4080
4081      We do not yet have a representation of the C99 '[*]' syntax.
4082      When a representation is chosen, this function should be modified
4083      to test for that case as well.  */
4084   if (TYPE_SIZE (type)
4085       && TYPE_SIZE (type) != error_mark_node
4086       && TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST)
4087     return true;
4088
4089   /* If TYPE is a pointer or reference, it is variably modified if
4090      the type pointed to is variably modified.  */
4091   if ((TREE_CODE (type) == POINTER_TYPE
4092        || TREE_CODE (type) == REFERENCE_TYPE)
4093       && variably_modified_type_p (TREE_TYPE (type)))
4094     return true;
4095
4096   /* If TYPE is an array, it is variably modified if the array
4097      elements are.  (Note that the VLA case has already been checked
4098      above.)  */
4099   if (TREE_CODE (type) == ARRAY_TYPE
4100       && variably_modified_type_p (TREE_TYPE (type)))
4101     return true;
4102
4103   /* If TYPE is a function type, it is variably modified if any of the
4104      parameters or the return type are variably modified.  */
4105   if (TREE_CODE (type) == FUNCTION_TYPE
4106       || TREE_CODE (type) == METHOD_TYPE)
4107     {
4108       tree parm;
4109
4110       if (variably_modified_type_p (TREE_TYPE (type)))
4111         return true;
4112       for (parm = TYPE_ARG_TYPES (type);
4113            parm && parm != void_list_node;
4114            parm = TREE_CHAIN (parm))
4115         if (variably_modified_type_p (TREE_VALUE (parm)))
4116           return true;
4117     }
4118
4119   /* The current language may have other cases to check, but in general,
4120      all other types are not variably modified.  */
4121   return (*lang_hooks.tree_inlining.var_mod_type_p) (type);
4122 }
4123
4124 /* Given a DECL or TYPE, return the scope in which it was declared, or
4125    NULL_TREE if there is no containing scope.  */
4126
4127 tree
4128 get_containing_scope (t)
4129      tree t;
4130 {
4131   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
4132 }
4133
4134 /* Return the innermost context enclosing DECL that is
4135    a FUNCTION_DECL, or zero if none.  */
4136
4137 tree
4138 decl_function_context (decl)
4139      tree decl;
4140 {
4141   tree context;
4142
4143   if (TREE_CODE (decl) == ERROR_MARK)
4144     return 0;
4145
4146   if (TREE_CODE (decl) == SAVE_EXPR)
4147     context = SAVE_EXPR_CONTEXT (decl);
4148
4149   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
4150      where we look up the function at runtime.  Such functions always take
4151      a first argument of type 'pointer to real context'.
4152
4153      C++ should really be fixed to use DECL_CONTEXT for the real context,
4154      and use something else for the "virtual context".  */
4155   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
4156     context
4157       = TYPE_MAIN_VARIANT
4158         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
4159   else
4160     context = DECL_CONTEXT (decl);
4161
4162   while (context && TREE_CODE (context) != FUNCTION_DECL)
4163     {
4164       if (TREE_CODE (context) == BLOCK)
4165         context = BLOCK_SUPERCONTEXT (context);
4166       else
4167         context = get_containing_scope (context);
4168     }
4169
4170   return context;
4171 }
4172
4173 /* Return the innermost context enclosing DECL that is
4174    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
4175    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
4176
4177 tree
4178 decl_type_context (decl)
4179      tree decl;
4180 {
4181   tree context = DECL_CONTEXT (decl);
4182
4183   while (context)
4184     {
4185       if (TREE_CODE (context) == NAMESPACE_DECL)
4186         return NULL_TREE;
4187
4188       if (TREE_CODE (context) == RECORD_TYPE
4189           || TREE_CODE (context) == UNION_TYPE
4190           || TREE_CODE (context) == QUAL_UNION_TYPE)
4191         return context;
4192
4193       if (TREE_CODE (context) == TYPE_DECL
4194           || TREE_CODE (context) == FUNCTION_DECL)
4195         context = DECL_CONTEXT (context);
4196
4197       else if (TREE_CODE (context) == BLOCK)
4198         context = BLOCK_SUPERCONTEXT (context);
4199
4200       else
4201         /* Unhandled CONTEXT!?  */
4202         abort ();
4203     }
4204   return NULL_TREE;
4205 }
4206
4207 /* CALL is a CALL_EXPR.  Return the declaration for the function
4208    called, or NULL_TREE if the called function cannot be
4209    determined.  */
4210
4211 tree
4212 get_callee_fndecl (call)
4213      tree call;
4214 {
4215   tree addr;
4216
4217   /* It's invalid to call this function with anything but a
4218      CALL_EXPR.  */
4219   if (TREE_CODE (call) != CALL_EXPR)
4220     abort ();
4221
4222   /* The first operand to the CALL is the address of the function
4223      called.  */
4224   addr = TREE_OPERAND (call, 0);
4225
4226   STRIP_NOPS (addr);
4227
4228   /* If this is a readonly function pointer, extract its initial value.  */
4229   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
4230       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
4231       && DECL_INITIAL (addr))
4232     addr = DECL_INITIAL (addr);
4233
4234   /* If the address is just `&f' for some function `f', then we know
4235      that `f' is being called.  */
4236   if (TREE_CODE (addr) == ADDR_EXPR
4237       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
4238     return TREE_OPERAND (addr, 0);
4239
4240   /* We couldn't figure out what was being called.  */
4241   return NULL_TREE;
4242 }
4243
4244 /* Print debugging information about the obstack O, named STR.  */
4245
4246 void
4247 print_obstack_statistics (str, o)
4248      const char *str;
4249      struct obstack *o;
4250 {
4251   struct _obstack_chunk *chunk = o->chunk;
4252   int n_chunks = 1;
4253   int n_alloc = 0;
4254
4255   n_alloc += o->next_free - chunk->contents;
4256   chunk = chunk->prev;
4257   while (chunk)
4258     {
4259       n_chunks += 1;
4260       n_alloc += chunk->limit - &chunk->contents[0];
4261       chunk = chunk->prev;
4262     }
4263   fprintf (stderr, "obstack %s: %u bytes, %d chunks\n",
4264            str, n_alloc, n_chunks);
4265 }
4266
4267 /* Print debugging information about tree nodes generated during the compile,
4268    and any language-specific information.  */
4269
4270 void
4271 dump_tree_statistics ()
4272 {
4273 #ifdef GATHER_STATISTICS
4274   int i;
4275   int total_nodes, total_bytes;
4276 #endif
4277
4278   fprintf (stderr, "\n??? tree nodes created\n\n");
4279 #ifdef GATHER_STATISTICS
4280   fprintf (stderr, "Kind                  Nodes     Bytes\n");
4281   fprintf (stderr, "-------------------------------------\n");
4282   total_nodes = total_bytes = 0;
4283   for (i = 0; i < (int) all_kinds; i++)
4284     {
4285       fprintf (stderr, "%-20s %6d %9d\n", tree_node_kind_names[i],
4286                tree_node_counts[i], tree_node_sizes[i]);
4287       total_nodes += tree_node_counts[i];
4288       total_bytes += tree_node_sizes[i];
4289     }
4290   fprintf (stderr, "-------------------------------------\n");
4291   fprintf (stderr, "%-20s %6d %9d\n", "Total", total_nodes, total_bytes);
4292   fprintf (stderr, "-------------------------------------\n");
4293 #else
4294   fprintf (stderr, "(No per-node statistics)\n");
4295 #endif
4296   print_type_hash_statistics ();
4297   (*lang_hooks.print_statistics) ();
4298 }
4299 \f
4300 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
4301
4302 /* Appends 6 random characters to TEMPLATE to (hopefully) avoid name
4303    clashes in cases where we can't reliably choose a unique name.
4304
4305    Derived from mkstemp.c in libiberty.  */
4306
4307 static void
4308 append_random_chars (template)
4309      char *template;
4310 {
4311   static const char letters[]
4312     = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
4313   static unsigned HOST_WIDE_INT value;
4314   unsigned HOST_WIDE_INT v;
4315
4316   if (! value)
4317     {
4318       struct stat st;
4319
4320       /* VALUE should be unique for each file and must not change between
4321          compiles since this can cause bootstrap comparison errors.  */
4322
4323       if (stat (main_input_filename, &st) < 0)
4324         {
4325           /* This can happen when preprocessed text is shipped between
4326              machines, e.g. with bug reports.  Assume that uniqueness
4327              isn't actually an issue.  */
4328           value = 1;
4329         }
4330       else
4331         {
4332           /* In VMS, ino is an array, so we have to use both values.  We
4333              conditionalize that.  */
4334 #ifdef VMS
4335 #define INO_TO_INT(INO) ((int) (INO)[1] << 16 ^ (int) (INO)[2])
4336 #else
4337 #define INO_TO_INT(INO) INO
4338 #endif
4339           value = st.st_dev ^ INO_TO_INT (st.st_ino) ^ st.st_mtime;
4340         }
4341     }
4342
4343   template += strlen (template);
4344
4345   v = value;
4346
4347   /* Fill in the random bits.  */
4348   template[0] = letters[v % 62];
4349   v /= 62;
4350   template[1] = letters[v % 62];
4351   v /= 62;
4352   template[2] = letters[v % 62];
4353   v /= 62;
4354   template[3] = letters[v % 62];
4355   v /= 62;
4356   template[4] = letters[v % 62];
4357   v /= 62;
4358   template[5] = letters[v % 62];
4359
4360   template[6] = '\0';
4361 }
4362
4363 /* P is a string that will be used in a symbol.  Mask out any characters
4364    that are not valid in that context.  */
4365
4366 void
4367 clean_symbol_name (p)
4368      char *p;
4369 {
4370   for (; *p; p++)
4371     if (! (ISALNUM (*p)
4372 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
4373             || *p == '$'
4374 #endif
4375 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
4376             || *p == '.'
4377 #endif
4378            ))
4379       *p = '_';
4380 }
4381
4382 /* Generate a name for a function unique to this translation unit.
4383    TYPE is some string to identify the purpose of this function to the
4384    linker or collect2.  */
4385
4386 tree
4387 get_file_function_name_long (type)
4388      const char *type;
4389 {
4390   char *buf;
4391   const char *p;
4392   char *q;
4393
4394   if (first_global_object_name)
4395     p = first_global_object_name;
4396   else
4397     {
4398       /* We don't have anything that we know to be unique to this translation
4399          unit, so use what we do have and throw in some randomness.  */
4400
4401       const char *name = weak_global_object_name;
4402       const char *file = main_input_filename;
4403
4404       if (! name)
4405         name = "";
4406       if (! file)
4407         file = input_filename;
4408
4409       q = (char *) alloca (7 + strlen (name) + strlen (file));
4410
4411       sprintf (q, "%s%s", name, file);
4412       append_random_chars (q);
4413       p = q;
4414     }
4415
4416   buf = (char *) alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p)
4417                          + strlen (type));
4418
4419   /* Set up the name of the file-level functions we may need.
4420      Use a global object (which is already required to be unique over
4421      the program) rather than the file name (which imposes extra
4422      constraints).  */
4423   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
4424
4425   /* Don't need to pull weird characters out of global names.  */
4426   if (p != first_global_object_name)
4427     clean_symbol_name (buf + 11);
4428
4429   return get_identifier (buf);
4430 }
4431
4432 /* If KIND=='I', return a suitable global initializer (constructor) name.
4433    If KIND=='D', return a suitable global clean-up (destructor) name.  */
4434
4435 tree
4436 get_file_function_name (kind)
4437      int kind;
4438 {
4439   char p[2];
4440
4441   p[0] = kind;
4442   p[1] = 0;
4443
4444   return get_file_function_name_long (p);
4445 }
4446 \f
4447 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4448    The result is placed in BUFFER (which has length BIT_SIZE),
4449    with one bit in each char ('\000' or '\001').
4450
4451    If the constructor is constant, NULL_TREE is returned.
4452    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4453
4454 tree
4455 get_set_constructor_bits (init, buffer, bit_size)
4456      tree init;
4457      char *buffer;
4458      int bit_size;
4459 {
4460   int i;
4461   tree vals;
4462   HOST_WIDE_INT domain_min
4463     = tree_low_cst (TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (init))), 0);
4464   tree non_const_bits = NULL_TREE;
4465
4466   for (i = 0; i < bit_size; i++)
4467     buffer[i] = 0;
4468
4469   for (vals = TREE_OPERAND (init, 1);
4470        vals != NULL_TREE; vals = TREE_CHAIN (vals))
4471     {
4472       if (!host_integerp (TREE_VALUE (vals), 0)
4473           || (TREE_PURPOSE (vals) != NULL_TREE
4474               && !host_integerp (TREE_PURPOSE (vals), 0)))
4475         non_const_bits
4476           = tree_cons (TREE_PURPOSE (vals), TREE_VALUE (vals), non_const_bits);
4477       else if (TREE_PURPOSE (vals) != NULL_TREE)
4478         {
4479           /* Set a range of bits to ones.  */
4480           HOST_WIDE_INT lo_index
4481             = tree_low_cst (TREE_PURPOSE (vals), 0) - domain_min;
4482           HOST_WIDE_INT hi_index
4483             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4484
4485           if (lo_index < 0 || lo_index >= bit_size
4486               || hi_index < 0 || hi_index >= bit_size)
4487             abort ();
4488           for (; lo_index <= hi_index; lo_index++)
4489             buffer[lo_index] = 1;
4490         }
4491       else
4492         {
4493           /* Set a single bit to one.  */
4494           HOST_WIDE_INT index
4495             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
4496           if (index < 0 || index >= bit_size)
4497             {
4498               error ("invalid initializer for bit string");
4499               return NULL_TREE;
4500             }
4501           buffer[index] = 1;
4502         }
4503     }
4504   return non_const_bits;
4505 }
4506
4507 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
4508    The result is placed in BUFFER (which is an array of bytes).
4509    If the constructor is constant, NULL_TREE is returned.
4510    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
4511
4512 tree
4513 get_set_constructor_bytes (init, buffer, wd_size)
4514      tree init;
4515      unsigned char *buffer;
4516      int wd_size;
4517 {
4518   int i;
4519   int set_word_size = BITS_PER_UNIT;
4520   int bit_size = wd_size * set_word_size;
4521   int bit_pos = 0;
4522   unsigned char *bytep = buffer;
4523   char *bit_buffer = (char *) alloca (bit_size);
4524   tree non_const_bits = get_set_constructor_bits (init, bit_buffer, bit_size);
4525
4526   for (i = 0; i < wd_size; i++)
4527     buffer[i] = 0;
4528
4529   for (i = 0; i < bit_size; i++)
4530     {
4531       if (bit_buffer[i])
4532         {
4533           if (BYTES_BIG_ENDIAN)
4534             *bytep |= (1 << (set_word_size - 1 - bit_pos));
4535           else
4536             *bytep |= 1 << bit_pos;
4537         }
4538       bit_pos++;
4539       if (bit_pos >= set_word_size)
4540         bit_pos = 0, bytep++;
4541     }
4542   return non_const_bits;
4543 }
4544 \f
4545 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
4546 /* Complain that the tree code of NODE does not match the expected CODE.
4547    FILE, LINE, and FUNCTION are of the caller.  */
4548
4549 void
4550 tree_check_failed (node, code, file, line, function)
4551      const tree node;
4552      enum tree_code code;
4553      const char *file;
4554      int line;
4555      const char *function;
4556 {
4557   internal_error ("tree check: expected %s, have %s in %s, at %s:%d",
4558                   tree_code_name[code], tree_code_name[TREE_CODE (node)],
4559                   function, trim_filename (file), line);
4560 }
4561
4562 /* Similar to above, except that we check for a class of tree
4563    code, given in CL.  */
4564
4565 void
4566 tree_class_check_failed (node, cl, file, line, function)
4567      const tree node;
4568      int cl;
4569      const char *file;
4570      int line;
4571      const char *function;
4572 {
4573   internal_error
4574     ("tree check: expected class '%c', have '%c' (%s) in %s, at %s:%d",
4575      cl, TREE_CODE_CLASS (TREE_CODE (node)),
4576      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
4577 }
4578
4579 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
4580    (dynamically sized) vector.  */
4581
4582 void
4583 tree_vec_elt_check_failed (idx, len, file, line, function)
4584      int idx;
4585      int len;
4586      const char *file;
4587      int line;
4588      const char *function;
4589 {
4590   internal_error
4591     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
4592      idx + 1, len, function, trim_filename (file), line);
4593 }
4594
4595 #endif /* ENABLE_TREE_CHECKING */
4596 \f
4597 /* For a new vector type node T, build the information necessary for
4598    debugging output.  */
4599
4600 static void
4601 finish_vector_type (t)
4602      tree t;
4603 {
4604   layout_type (t);
4605
4606   {
4607     tree index = build_int_2 (TYPE_VECTOR_SUBPARTS (t) - 1, 0);
4608     tree array = build_array_type (TREE_TYPE (t),
4609                                    build_index_type (index));
4610     tree rt = make_node (RECORD_TYPE);
4611
4612     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
4613     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
4614     layout_type (rt);
4615     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
4616     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
4617        the representation type, and we want to find that die when looking up
4618        the vector type.  This is most easily achieved by making the TYPE_UID
4619        numbers equal.  */
4620     TYPE_UID (rt) = TYPE_UID (t);
4621   }
4622 }
4623
4624 /* Create nodes for all integer types (and error_mark_node) using the sizes
4625    of C datatypes.  The caller should call set_sizetype soon after calling
4626    this function to select one of the types as sizetype.  */
4627
4628 void
4629 build_common_tree_nodes (signed_char)
4630      int signed_char;
4631 {
4632   error_mark_node = make_node (ERROR_MARK);
4633   TREE_TYPE (error_mark_node) = error_mark_node;
4634
4635   initialize_sizetypes ();
4636
4637   /* Define both `signed char' and `unsigned char'.  */
4638   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
4639   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
4640
4641   /* Define `char', which is like either `signed char' or `unsigned char'
4642      but not the same as either.  */
4643   char_type_node
4644     = (signed_char
4645        ? make_signed_type (CHAR_TYPE_SIZE)
4646        : make_unsigned_type (CHAR_TYPE_SIZE));
4647
4648   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
4649   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
4650   integer_type_node = make_signed_type (INT_TYPE_SIZE);
4651   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
4652   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
4653   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
4654   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
4655   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
4656
4657   intQI_type_node = make_signed_type (GET_MODE_BITSIZE (QImode));
4658   intHI_type_node = make_signed_type (GET_MODE_BITSIZE (HImode));
4659   intSI_type_node = make_signed_type (GET_MODE_BITSIZE (SImode));
4660   intDI_type_node = make_signed_type (GET_MODE_BITSIZE (DImode));
4661   intTI_type_node = make_signed_type (GET_MODE_BITSIZE (TImode));
4662
4663   unsigned_intQI_type_node = make_unsigned_type (GET_MODE_BITSIZE (QImode));
4664   unsigned_intHI_type_node = make_unsigned_type (GET_MODE_BITSIZE (HImode));
4665   unsigned_intSI_type_node = make_unsigned_type (GET_MODE_BITSIZE (SImode));
4666   unsigned_intDI_type_node = make_unsigned_type (GET_MODE_BITSIZE (DImode));
4667   unsigned_intTI_type_node = make_unsigned_type (GET_MODE_BITSIZE (TImode));
4668 }
4669
4670 /* Call this function after calling build_common_tree_nodes and set_sizetype.
4671    It will create several other common tree nodes.  */
4672
4673 void
4674 build_common_tree_nodes_2 (short_double)
4675      int short_double;
4676 {
4677   /* Define these next since types below may used them.  */
4678   integer_zero_node = build_int_2 (0, 0);
4679   integer_one_node = build_int_2 (1, 0);
4680   integer_minus_one_node = build_int_2 (-1, -1);
4681
4682   size_zero_node = size_int (0);
4683   size_one_node = size_int (1);
4684   bitsize_zero_node = bitsize_int (0);
4685   bitsize_one_node = bitsize_int (1);
4686   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
4687
4688   void_type_node = make_node (VOID_TYPE);
4689   layout_type (void_type_node);
4690
4691   /* We are not going to have real types in C with less than byte alignment,
4692      so we might as well not have any types that claim to have it.  */
4693   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
4694   TYPE_USER_ALIGN (void_type_node) = 0;
4695
4696   null_pointer_node = build_int_2 (0, 0);
4697   TREE_TYPE (null_pointer_node) = build_pointer_type (void_type_node);
4698   layout_type (TREE_TYPE (null_pointer_node));
4699
4700   ptr_type_node = build_pointer_type (void_type_node);
4701   const_ptr_type_node
4702     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
4703
4704   float_type_node = make_node (REAL_TYPE);
4705   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
4706   layout_type (float_type_node);
4707
4708   double_type_node = make_node (REAL_TYPE);
4709   if (short_double)
4710     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
4711   else
4712     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
4713   layout_type (double_type_node);
4714
4715   long_double_type_node = make_node (REAL_TYPE);
4716   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
4717   layout_type (long_double_type_node);
4718
4719   complex_integer_type_node = make_node (COMPLEX_TYPE);
4720   TREE_TYPE (complex_integer_type_node) = integer_type_node;
4721   layout_type (complex_integer_type_node);
4722
4723   complex_float_type_node = make_node (COMPLEX_TYPE);
4724   TREE_TYPE (complex_float_type_node) = float_type_node;
4725   layout_type (complex_float_type_node);
4726
4727   complex_double_type_node = make_node (COMPLEX_TYPE);
4728   TREE_TYPE (complex_double_type_node) = double_type_node;
4729   layout_type (complex_double_type_node);
4730
4731   complex_long_double_type_node = make_node (COMPLEX_TYPE);
4732   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
4733   layout_type (complex_long_double_type_node);
4734
4735   {
4736     tree t;
4737     BUILD_VA_LIST_TYPE (t);
4738
4739     /* Many back-ends define record types without seting TYPE_NAME.
4740        If we copied the record type here, we'd keep the original
4741        record type without a name.  This breaks name mangling.  So,
4742        don't copy record types and let c_common_nodes_and_builtins()
4743        declare the type to be __builtin_va_list.  */
4744     if (TREE_CODE (t) != RECORD_TYPE)
4745       t = build_type_copy (t);
4746
4747     va_list_type_node = t;
4748   }
4749
4750   unsigned_V4SI_type_node
4751     = make_vector (V4SImode, unsigned_intSI_type_node, 1);
4752   unsigned_V2HI_type_node
4753     = make_vector (V2HImode, unsigned_intHI_type_node, 1);
4754   unsigned_V2SI_type_node
4755     = make_vector (V2SImode, unsigned_intSI_type_node, 1);
4756   unsigned_V2DI_type_node
4757     = make_vector (V2DImode, unsigned_intDI_type_node, 1);
4758   unsigned_V4HI_type_node
4759     = make_vector (V4HImode, unsigned_intHI_type_node, 1);
4760   unsigned_V8QI_type_node
4761     = make_vector (V8QImode, unsigned_intQI_type_node, 1);
4762   unsigned_V8HI_type_node
4763     = make_vector (V8HImode, unsigned_intHI_type_node, 1);
4764   unsigned_V16QI_type_node
4765     = make_vector (V16QImode, unsigned_intQI_type_node, 1);
4766   unsigned_V1DI_type_node
4767     = make_vector (V1DImode, unsigned_intDI_type_node, 1);
4768
4769   V16SF_type_node = make_vector (V16SFmode, float_type_node, 0);
4770   V4SF_type_node = make_vector (V4SFmode, float_type_node, 0);
4771   V4SI_type_node = make_vector (V4SImode, intSI_type_node, 0);
4772   V2HI_type_node = make_vector (V2HImode, intHI_type_node, 0);
4773   V2SI_type_node = make_vector (V2SImode, intSI_type_node, 0);
4774   V2DI_type_node = make_vector (V2DImode, intDI_type_node, 0);
4775   V4HI_type_node = make_vector (V4HImode, intHI_type_node, 0);
4776   V8QI_type_node = make_vector (V8QImode, intQI_type_node, 0);
4777   V8HI_type_node = make_vector (V8HImode, intHI_type_node, 0);
4778   V2SF_type_node = make_vector (V2SFmode, float_type_node, 0);
4779   V2DF_type_node = make_vector (V2DFmode, double_type_node, 0);
4780   V16QI_type_node = make_vector (V16QImode, intQI_type_node, 0);
4781   V1DI_type_node = make_vector (V1DImode, intDI_type_node, 0);
4782 }
4783
4784 /* Returns a vector tree node given a vector mode, the inner type, and
4785    the signness.  */
4786
4787 static tree
4788 make_vector (mode, innertype, unsignedp)
4789      enum machine_mode mode;
4790      tree innertype;
4791      int unsignedp;
4792 {
4793   tree t;
4794
4795   t = make_node (VECTOR_TYPE);
4796   TREE_TYPE (t) = innertype;
4797   TYPE_MODE (t) = mode;
4798   TREE_UNSIGNED (TREE_TYPE (t)) = unsignedp;
4799   finish_vector_type (t);
4800
4801   return t;
4802 }
4803
4804 /* Given an initializer INIT, return TRUE if INIT is zero or some
4805    aggregate of zeros.  Otherwise return FALSE.  */
4806
4807 bool
4808 initializer_zerop (init)
4809      tree init;
4810 {
4811   STRIP_NOPS (init);
4812
4813   switch (TREE_CODE (init))
4814     {
4815     case INTEGER_CST:
4816       return integer_zerop (init);
4817     case REAL_CST:
4818       return real_zerop (init)
4819         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
4820     case COMPLEX_CST:
4821       return integer_zerop (init)
4822         || (real_zerop (init)
4823             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
4824             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
4825     case CONSTRUCTOR:
4826       {
4827         if (AGGREGATE_TYPE_P (TREE_TYPE (init)))
4828           {
4829             tree aggr_init = TREE_OPERAND (init, 1);
4830
4831             while (aggr_init)
4832               {
4833                 if (! initializer_zerop (TREE_VALUE (aggr_init)))
4834                   return false;
4835                 aggr_init = TREE_CHAIN (aggr_init);
4836               }
4837             return true;
4838           }
4839         return false;
4840       }
4841     default:
4842       return false;
4843     }
4844 }
4845
4846 #include "gt-tree.h"