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