gcc/tree.c

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