gcc/tree.c

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