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