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, 2004 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 #include "tree-iterator.h"
  49 #include "basic-block.h"
  50 #include "tree-flow.h"
  51
  52 /* obstack.[ch] explicitly declined to prototype this.  */
  53 extern int _obstack_allocated_p (struct obstack *h, void *obj);
  54
  55 #ifdef GATHER_STATISTICS
  56 /* Statistics-gathering stuff.  */
  57
  58 int tree_node_counts[(int) all_kinds];
  59 int tree_node_sizes[(int) all_kinds];
  60
  61 /* Keep in sync with tree.h:enum tree_node_kind.  */
  62 static const char * const tree_node_kind_names[] = {
  63   "decls",
  64   "types",
  65   "blocks",
  66   "stmts",
  67   "refs",
  68   "exprs",
  69   "constants",
  70   "identifiers",
  71   "perm_tree_lists",
  72   "temp_tree_lists",
  73   "vecs",
  74   "phi_nodes",
  75   "ssa names",
  76   "random kinds",
  77   "lang_decl kinds",
  78   "lang_type kinds"
  79 };
  80 #endif /* GATHER_STATISTICS */
  81
  82 /* Unique id for next decl created.  */
  83 static GTY(()) int next_decl_uid;
  84 /* Unique id for next type created.  */
  85 static GTY(()) int next_type_uid = 1;
  86
  87 /* Since we cannot rehash a type after it is in the table, we have to
  88    keep the hash code.  */
  89
  90 struct type_hash GTY(())
  91 {
  92   unsigned long hash;
  93   tree type;
  94 };
  95
  96 /* Initial size of the hash table (rounded to next prime).  */
  97 #define TYPE_HASH_INITIAL_SIZE 1000
  98
  99 /* Now here is the hash table.  When recording a type, it is added to
 100    the slot whose index is the hash code.  Note that the hash table is
 101    used for several kinds of types (function types, array types and
 102    array index range types, for now).  While all these live in the
 103    same table, they are completely independent, and the hash code is
 104    computed differently for each of these.  */
 105
 106 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
 107      htab_t type_hash_table;
 108
 109 static void set_type_quals (tree, int);
 110 static int type_hash_eq (const void *, const void *);
 111 static hashval_t type_hash_hash (const void *);
 112 static void print_type_hash_statistics (void);
 113 static void finish_vector_type (tree);
 114 static int type_hash_marked_p (const void *);
 115 static unsigned int type_hash_list (tree, hashval_t);
 116 static unsigned int attribute_hash_list (tree, hashval_t);
 117
 118 tree global_trees[TI_MAX];
 119 tree integer_types[itk_none];
 120 \f
 121 /* Init tree.c.  */
 122
 123 void
 124 init_ttree (void)
 125 {
 126   /* Initialize the hash table of types.  */
 127   type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
 128                                      type_hash_eq, 0);
 129 }
 130
 131 \f
 132 /* The name of the object as the assembler will see it (but before any
 133    translations made by ASM_OUTPUT_LABELREF).  Often this is the same
 134    as DECL_NAME.  It is an IDENTIFIER_NODE.  */
 135 tree
 136 decl_assembler_name (tree decl)
 137 {
 138   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 139     lang_hooks.set_decl_assembler_name (decl);
 140   return DECL_CHECK (decl)->decl.assembler_name;
 141 }
 142
 143 /* Compute the number of bytes occupied by 'node'.  This routine only
 144    looks at TREE_CODE and, if the code is TREE_VEC, TREE_VEC_LENGTH.  */
 145 size_t
 146 tree_size (tree node)
 147 {
 148   enum tree_code code = TREE_CODE (node);
 149
 150   switch (TREE_CODE_CLASS (code))
 151     {
 152     case 'd':  /* A decl node */
 153       return sizeof (struct tree_decl);
 154
 155     case 't':  /* a type node */
 156       return sizeof (struct tree_type);
 157
 158     case 'r':  /* a reference */
 159     case 'e':  /* an expression */
 160     case 's':  /* an expression with side effects */
 161     case '<':  /* a comparison expression */
 162     case '1':  /* a unary arithmetic expression */
 163     case '2':  /* a binary arithmetic expression */
 164       return (sizeof (struct tree_exp)
 165               + TREE_CODE_LENGTH (code) * sizeof (char *) - sizeof (char *));
 166
 167     case 'c':  /* a constant */
 168       switch (code)
 169         {
 170         case INTEGER_CST:       return sizeof (struct tree_int_cst);
 171         case REAL_CST:          return sizeof (struct tree_real_cst);
 172         case COMPLEX_CST:       return sizeof (struct tree_complex);
 173         case VECTOR_CST:        return sizeof (struct tree_vector);
 174         case STRING_CST:        return sizeof (struct tree_string);
 175         default:
 176           return lang_hooks.tree_size (code);
 177         }
 178
 179     case 'x':  /* something random, like an identifier.  */
 180       switch (code)
 181         {
 182         case IDENTIFIER_NODE:   return lang_hooks.identifier_size;
 183         case TREE_LIST:         return sizeof (struct tree_list);
 184         case TREE_VEC:          return (sizeof (struct tree_vec)
 185                                         + TREE_VEC_LENGTH(node) * sizeof(char *)
 186                                         - sizeof (char *));
 187
 188         case ERROR_MARK:
 189         case PLACEHOLDER_EXPR:  return sizeof (struct tree_common);
 190
 191         case PHI_NODE:          return (sizeof (struct tree_phi_node)
 192                                         + (PHI_ARG_CAPACITY (node) - 1) *
 193                                         sizeof (struct phi_arg_d));
 194
 195         case SSA_NAME:          return sizeof (struct tree_ssa_name);
 196
 197         case STATEMENT_LIST:    return sizeof (struct tree_statement_list);
 198         case BLOCK:             return sizeof (struct tree_block);
 199         case VALUE_HANDLE:      return sizeof (struct tree_value_handle);
 200
 201         default:
 202           return lang_hooks.tree_size (code);
 203         }
 204
 205     default:
 206       abort ();
 207     }
 208 }
 209
 210 /* Return a newly allocated node of code CODE.
 211    For decl and type nodes, some other fields are initialized.
 212    The rest of the node is initialized to zero.
 213
 214    Achoo!  I got a code in the node.  */
 215
 216 tree
 217 make_node_stat (enum tree_code code MEM_STAT_DECL)
 218 {
 219   tree t;
 220   int type = TREE_CODE_CLASS (code);
 221   size_t length;
 222 #ifdef GATHER_STATISTICS
 223   tree_node_kind kind;
 224 #endif
 225   struct tree_common ttmp;
 226
 227   /* We can't allocate a TREE_VEC, PHI_NODE, or STRING_CST
 228      without knowing how many elements it will have.  */
 229   if (code == TREE_VEC || code == PHI_NODE)
 230     abort ();
 231
 232   TREE_SET_CODE ((tree)&ttmp, code);
 233   length = tree_size ((tree)&ttmp);
 234
 235 #ifdef GATHER_STATISTICS
 236   switch (type)
 237     {
 238     case 'd':  /* A decl node */
 239       kind = d_kind;
 240       break;
 241
 242     case 't':  /* a type node */
 243       kind = t_kind;
 244       break;
 245
 246     case 's':  /* an expression with side effects */
 247       kind = s_kind;
 248       break;
 249
 250     case 'r':  /* a reference */
 251       kind = r_kind;
 252       break;
 253
 254     case 'e':  /* an expression */
 255     case '<':  /* a comparison expression */
 256     case '1':  /* a unary arithmetic expression */
 257     case '2':  /* a binary arithmetic expression */
 258       kind = e_kind;
 259       break;
 260
 261     case 'c':  /* a constant */
 262       kind = c_kind;
 263       break;
 264
 265     case 'x':  /* something random, like an identifier.  */
 266       if (code == IDENTIFIER_NODE)
 267         kind = id_kind;
 268       else if (code == TREE_VEC)
 269         kind = vec_kind;
 270       else if (code == PHI_NODE)
 271         kind = phi_kind;
 272       else if (code == SSA_NAME)
 273         kind = ssa_name_kind;
 274       else if (code == BLOCK)
 275         kind = b_kind;
 276       else
 277         kind = x_kind;
 278       break;
 279
 280     default:
 281       abort ();
 282     }
 283
 284   tree_node_counts[(int) kind]++;
 285   tree_node_sizes[(int) kind] += length;
 286 #endif
 287
 288   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
 289
 290   memset (t, 0, length);
 291
 292   TREE_SET_CODE (t, code);
 293
 294   switch (type)
 295     {
 296     case 's':
 297       TREE_SIDE_EFFECTS (t) = 1;
 298       break;
 299
 300     case 'd':
 301       if (code != FUNCTION_DECL)
 302         DECL_ALIGN (t) = 1;
 303       DECL_USER_ALIGN (t) = 0;
 304       DECL_IN_SYSTEM_HEADER (t) = in_system_header;
 305       DECL_SOURCE_LOCATION (t) = input_location;
 306       DECL_UID (t) = next_decl_uid++;
 307
 308       /* We have not yet computed the alias set for this declaration.  */
 309       DECL_POINTER_ALIAS_SET (t) = -1;
 310       break;
 311
 312     case 't':
 313       TYPE_UID (t) = next_type_uid++;
 314       TYPE_ALIGN (t) = char_type_node ? TYPE_ALIGN (char_type_node) : 0;
 315       TYPE_USER_ALIGN (t) = 0;
 316       TYPE_MAIN_VARIANT (t) = t;
 317
 318       /* Default to no attributes for type, but let target change that.  */
 319       TYPE_ATTRIBUTES (t) = NULL_TREE;
 320       targetm.set_default_type_attributes (t);
 321
 322       /* We have not yet computed the alias set for this type.  */
 323       TYPE_ALIAS_SET (t) = -1;
 324       break;
 325
 326     case 'c':
 327       TREE_CONSTANT (t) = 1;
 328       TREE_INVARIANT (t) = 1;
 329       break;
 330
 331     case 'e':
 332       switch (code)
 333         {
 334         case INIT_EXPR:
 335         case MODIFY_EXPR:
 336         case VA_ARG_EXPR:
 337         case PREDECREMENT_EXPR:
 338         case PREINCREMENT_EXPR:
 339         case POSTDECREMENT_EXPR:
 340         case POSTINCREMENT_EXPR:
 341           /* All of these have side-effects, no matter what their
 342              operands are.  */
 343           TREE_SIDE_EFFECTS (t) = 1;
 344           break;
 345
 346         default:
 347           break;
 348         }
 349       break;
 350     }
 351
 352   return t;
 353 }
 354 \f
 355 /* Return a new node with the same contents as NODE except that its
 356    TREE_CHAIN is zero and it has a fresh uid.  */
 357
 358 tree
 359 copy_node_stat (tree node MEM_STAT_DECL)
 360 {
 361   tree t;
 362   enum tree_code code = TREE_CODE (node);
 363   size_t length;
 364
 365 #ifdef ENABLE_CHECKING
 366   if (code == STATEMENT_LIST)
 367     abort ();
 368 #endif
 369
 370   length = tree_size (node);
 371   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
 372   memcpy (t, node, length);
 373
 374   TREE_CHAIN (t) = 0;
 375   TREE_ASM_WRITTEN (t) = 0;
 376   TREE_VISITED (t) = 0;
 377   t->common.ann = 0;
 378
 379   if (TREE_CODE_CLASS (code) == 'd')
 380     DECL_UID (t) = next_decl_uid++;
 381   else if (TREE_CODE_CLASS (code) == 't')
 382     {
 383       TYPE_UID (t) = next_type_uid++;
 384       /* The following is so that the debug code for
 385          the copy is different from the original type.
 386          The two statements usually duplicate each other
 387          (because they clear fields of the same union),
 388          but the optimizer should catch that.  */
 389       TYPE_SYMTAB_POINTER (t) = 0;
 390       TYPE_SYMTAB_ADDRESS (t) = 0;
 391     }
 392
 393   return t;
 394 }
 395
 396 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
 397    For example, this can copy a list made of TREE_LIST nodes.  */
 398
 399 tree
 400 copy_list (tree list)
 401 {
 402   tree head;
 403   tree prev, next;
 404
 405   if (list == 0)
 406     return 0;
 407
 408   head = prev = copy_node (list);
 409   next = TREE_CHAIN (list);
 410   while (next)
 411     {
 412       TREE_CHAIN (prev) = copy_node (next);
 413       prev = TREE_CHAIN (prev);
 414       next = TREE_CHAIN (next);
 415     }
 416   return head;
 417 }
 418
 419 \f
 420 /* Return a newly constructed INTEGER_CST node whose constant value
 421    is specified by the two ints LOW and HI.
 422    The TREE_TYPE is set to `int'.
 423
 424    This function should be used via the `build_int_2' macro.  */
 425
 426 tree
 427 build_int_2_wide (unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
 428 {
 429   tree t = make_node (INTEGER_CST);
 430
 431   TREE_INT_CST_LOW (t) = low;
 432   TREE_INT_CST_HIGH (t) = hi;
 433   TREE_TYPE (t) = integer_type_node;
 434   return t;
 435 }
 436
 437 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 438    are in a list pointed by VALS.  */
 439
 440 tree
 441 build_vector (tree type, tree vals)
 442 {
 443   tree v = make_node (VECTOR_CST);
 444   int over1 = 0, over2 = 0;
 445   tree link;
 446
 447   TREE_VECTOR_CST_ELTS (v) = vals;
 448   TREE_TYPE (v) = type;
 449
 450   /* Iterate through elements and check for overflow.  */
 451   for (link = vals; link; link = TREE_CHAIN (link))
 452     {
 453       tree value = TREE_VALUE (link);
 454
 455       over1 |= TREE_OVERFLOW (value);
 456       over2 |= TREE_CONSTANT_OVERFLOW (value);
 457     }
 458
 459   TREE_OVERFLOW (v) = over1;
 460   TREE_CONSTANT_OVERFLOW (v) = over2;
 461
 462   return v;
 463 }
 464
 465 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
 466    are in a list pointed to by VALS.  */
 467 tree
 468 build_constructor (tree type, tree vals)
 469 {
 470   tree c = make_node (CONSTRUCTOR);
 471   TREE_TYPE (c) = type;
 472   CONSTRUCTOR_ELTS (c) = vals;
 473
 474   /* ??? May not be necessary.  Mirrors what build does.  */
 475   if (vals)
 476     {
 477       TREE_SIDE_EFFECTS (c) = TREE_SIDE_EFFECTS (vals);
 478       TREE_READONLY (c) = TREE_READONLY (vals);
 479       TREE_CONSTANT (c) = TREE_CONSTANT (vals);
 480       TREE_INVARIANT (c) = TREE_INVARIANT (vals);
 481     }
 482
 483   return c;
 484 }
 485
 486 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
 487
 488 tree
 489 build_real (tree type, REAL_VALUE_TYPE d)
 490 {
 491   tree v;
 492   REAL_VALUE_TYPE *dp;
 493   int overflow = 0;
 494
 495   /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
 496      Consider doing it via real_convert now.  */
 497
 498   v = make_node (REAL_CST);
 499   dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
 500   memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
 501
 502   TREE_TYPE (v) = type;
 503   TREE_REAL_CST_PTR (v) = dp;
 504   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
 505   return v;
 506 }
 507
 508 /* Return a new REAL_CST node whose type is TYPE
 509    and whose value is the integer value of the INTEGER_CST node I.  */
 510
 511 REAL_VALUE_TYPE
 512 real_value_from_int_cst (tree type, tree i)
 513 {
 514   REAL_VALUE_TYPE d;
 515
 516   /* Clear all bits of the real value type so that we can later do
 517      bitwise comparisons to see if two values are the same.  */
 518   memset (&d, 0, sizeof d);
 519
 520   real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
 521                      TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
 522                      TYPE_UNSIGNED (TREE_TYPE (i)));
 523   return d;
 524 }
 525
 526 /* Given a tree representing an integer constant I, return a tree
 527    representing the same value as a floating-point constant of type TYPE.  */
 528
 529 tree
 530 build_real_from_int_cst (tree type, tree i)
 531 {
 532   tree v;
 533   int overflow = TREE_OVERFLOW (i);
 534
 535   v = build_real (type, real_value_from_int_cst (type, i));
 536
 537   TREE_OVERFLOW (v) |= overflow;
 538   TREE_CONSTANT_OVERFLOW (v) |= overflow;
 539   return v;
 540 }
 541
 542 /* Return a newly constructed STRING_CST node whose value is
 543    the LEN characters at STR.
 544    The TREE_TYPE is not initialized.  */
 545
 546 tree
 547 build_string (int len, const char *str)
 548 {
 549   tree s = make_node (STRING_CST);
 550
 551   TREE_STRING_LENGTH (s) = len;
 552   TREE_STRING_POINTER (s) = ggc_alloc_string (str, len);
 553
 554   return s;
 555 }
 556
 557 /* Return a newly constructed COMPLEX_CST node whose value is
 558    specified by the real and imaginary parts REAL and IMAG.
 559    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
 560    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
 561
 562 tree
 563 build_complex (tree type, tree real, tree imag)
 564 {
 565   tree t = make_node (COMPLEX_CST);
 566
 567   TREE_REALPART (t) = real;
 568   TREE_IMAGPART (t) = imag;
 569   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
 570   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
 571   TREE_CONSTANT_OVERFLOW (t)
 572     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
 573   return t;
 574 }
 575
 576 /* Build a newly constructed TREE_VEC node of length LEN.  */
 577
 578 tree
 579 make_tree_vec_stat (int len MEM_STAT_DECL)
 580 {
 581   tree t;
 582   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
 583
 584 #ifdef GATHER_STATISTICS
 585   tree_node_counts[(int) vec_kind]++;
 586   tree_node_sizes[(int) vec_kind] += length;
 587 #endif
 588
 589   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
 590
 591   memset (t, 0, length);
 592
 593   TREE_SET_CODE (t, TREE_VEC);
 594   TREE_VEC_LENGTH (t) = len;
 595
 596   return t;
 597 }
 598 \f
 599 /* Return 1 if EXPR is the integer constant zero or a complex constant
 600    of zero.  */
 601
 602 int
 603 integer_zerop (tree expr)
 604 {
 605   STRIP_NOPS (expr);
 606
 607   return ((TREE_CODE (expr) == INTEGER_CST
 608            && ! TREE_CONSTANT_OVERFLOW (expr)
 609            && TREE_INT_CST_LOW (expr) == 0
 610            && TREE_INT_CST_HIGH (expr) == 0)
 611           || (TREE_CODE (expr) == COMPLEX_CST
 612               && integer_zerop (TREE_REALPART (expr))
 613               && integer_zerop (TREE_IMAGPART (expr))));
 614 }
 615
 616 /* Return 1 if EXPR is the integer constant one or the corresponding
 617    complex constant.  */
 618
 619 int
 620 integer_onep (tree expr)
 621 {
 622   STRIP_NOPS (expr);
 623
 624   return ((TREE_CODE (expr) == INTEGER_CST
 625            && ! TREE_CONSTANT_OVERFLOW (expr)
 626            && TREE_INT_CST_LOW (expr) == 1
 627            && TREE_INT_CST_HIGH (expr) == 0)
 628           || (TREE_CODE (expr) == COMPLEX_CST
 629               && integer_onep (TREE_REALPART (expr))
 630               && integer_zerop (TREE_IMAGPART (expr))));
 631 }
 632
 633 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
 634    it contains.  Likewise for the corresponding complex constant.  */
 635
 636 int
 637 integer_all_onesp (tree expr)
 638 {
 639   int prec;
 640   int uns;
 641
 642   STRIP_NOPS (expr);
 643
 644   if (TREE_CODE (expr) == COMPLEX_CST
 645       && integer_all_onesp (TREE_REALPART (expr))
 646       && integer_zerop (TREE_IMAGPART (expr)))
 647     return 1;
 648
 649   else if (TREE_CODE (expr) != INTEGER_CST
 650            || TREE_CONSTANT_OVERFLOW (expr))
 651     return 0;
 652
 653   uns = TYPE_UNSIGNED (TREE_TYPE (expr));
 654   if (!uns)
 655     return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
 656             && TREE_INT_CST_HIGH (expr) == -1);
 657
 658   /* Note that using TYPE_PRECISION here is wrong.  We care about the
 659      actual bits, not the (arbitrary) range of the type.  */
 660   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
 661   if (prec >= HOST_BITS_PER_WIDE_INT)
 662     {
 663       HOST_WIDE_INT high_value;
 664       int shift_amount;
 665
 666       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
 667
 668       if (shift_amount > HOST_BITS_PER_WIDE_INT)
 669         /* Can not handle precisions greater than twice the host int size.  */
 670         abort ();
 671       else if (shift_amount == HOST_BITS_PER_WIDE_INT)
 672         /* Shifting by the host word size is undefined according to the ANSI
 673            standard, so we must handle this as a special case.  */
 674         high_value = -1;
 675       else
 676         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
 677
 678       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
 679               && TREE_INT_CST_HIGH (expr) == high_value);
 680     }
 681   else
 682     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
 683 }
 684
 685 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
 686    one bit on).  */
 687
 688 int
 689 integer_pow2p (tree expr)
 690 {
 691   int prec;
 692   HOST_WIDE_INT high, low;
 693
 694   STRIP_NOPS (expr);
 695
 696   if (TREE_CODE (expr) == COMPLEX_CST
 697       && integer_pow2p (TREE_REALPART (expr))
 698       && integer_zerop (TREE_IMAGPART (expr)))
 699     return 1;
 700
 701   if (TREE_CODE (expr) != INTEGER_CST || TREE_CONSTANT_OVERFLOW (expr))
 702     return 0;
 703
 704   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
 705           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
 706   high = TREE_INT_CST_HIGH (expr);
 707   low = TREE_INT_CST_LOW (expr);
 708
 709   /* First clear all bits that are beyond the type's precision in case
 710      we've been sign extended.  */
 711
 712   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
 713     ;
 714   else if (prec > HOST_BITS_PER_WIDE_INT)
 715     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 716   else
 717     {
 718       high = 0;
 719       if (prec < HOST_BITS_PER_WIDE_INT)
 720         low &= ~((HOST_WIDE_INT) (-1) << prec);
 721     }
 722
 723   if (high == 0 && low == 0)
 724     return 0;
 725
 726   return ((high == 0 && (low & (low - 1)) == 0)
 727           || (low == 0 && (high & (high - 1)) == 0));
 728 }
 729
 730 /* Return 1 if EXPR is an integer constant other than zero or a
 731    complex constant other than zero.  */
 732
 733 int
 734 integer_nonzerop (tree expr)
 735 {
 736   STRIP_NOPS (expr);
 737
 738   return ((TREE_CODE (expr) == INTEGER_CST
 739            && ! TREE_CONSTANT_OVERFLOW (expr)
 740            && (TREE_INT_CST_LOW (expr) != 0
 741                || TREE_INT_CST_HIGH (expr) != 0))
 742           || (TREE_CODE (expr) == COMPLEX_CST
 743               && (integer_nonzerop (TREE_REALPART (expr))
 744                   || integer_nonzerop (TREE_IMAGPART (expr)))));
 745 }
 746
 747 /* Return the power of two represented by a tree node known to be a
 748    power of two.  */
 749
 750 int
 751 tree_log2 (tree expr)
 752 {
 753   int prec;
 754   HOST_WIDE_INT high, low;
 755
 756   STRIP_NOPS (expr);
 757
 758   if (TREE_CODE (expr) == COMPLEX_CST)
 759     return tree_log2 (TREE_REALPART (expr));
 760
 761   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
 762           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
 763
 764   high = TREE_INT_CST_HIGH (expr);
 765   low = TREE_INT_CST_LOW (expr);
 766
 767   /* First clear all bits that are beyond the type's precision in case
 768      we've been sign extended.  */
 769
 770   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
 771     ;
 772   else if (prec > HOST_BITS_PER_WIDE_INT)
 773     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 774   else
 775     {
 776       high = 0;
 777       if (prec < HOST_BITS_PER_WIDE_INT)
 778         low &= ~((HOST_WIDE_INT) (-1) << prec);
 779     }
 780
 781   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
 782           : exact_log2 (low));
 783 }
 784
 785 /* Similar, but return the largest integer Y such that 2 ** Y is less
 786    than or equal to EXPR.  */
 787
 788 int
 789 tree_floor_log2 (tree expr)
 790 {
 791   int prec;
 792   HOST_WIDE_INT high, low;
 793
 794   STRIP_NOPS (expr);
 795
 796   if (TREE_CODE (expr) == COMPLEX_CST)
 797     return tree_log2 (TREE_REALPART (expr));
 798
 799   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
 800           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
 801
 802   high = TREE_INT_CST_HIGH (expr);
 803   low = TREE_INT_CST_LOW (expr);
 804
 805   /* First clear all bits that are beyond the type's precision in case
 806      we've been sign extended.  Ignore if type's precision hasn't been set
 807      since what we are doing is setting it.  */
 808
 809   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
 810     ;
 811   else if (prec > HOST_BITS_PER_WIDE_INT)
 812     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 813   else
 814     {
 815       high = 0;
 816       if (prec < HOST_BITS_PER_WIDE_INT)
 817         low &= ~((HOST_WIDE_INT) (-1) << prec);
 818     }
 819
 820   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
 821           : floor_log2 (low));
 822 }
 823
 824 /* Return 1 if EXPR is the real constant zero.  */
 825
 826 int
 827 real_zerop (tree expr)
 828 {
 829   STRIP_NOPS (expr);
 830
 831   return ((TREE_CODE (expr) == REAL_CST
 832            && ! TREE_CONSTANT_OVERFLOW (expr)
 833            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
 834           || (TREE_CODE (expr) == COMPLEX_CST
 835               && real_zerop (TREE_REALPART (expr))
 836               && real_zerop (TREE_IMAGPART (expr))));
 837 }
 838
 839 /* Return 1 if EXPR is the real constant one in real or complex form.  */
 840
 841 int
 842 real_onep (tree expr)
 843 {
 844   STRIP_NOPS (expr);
 845
 846   return ((TREE_CODE (expr) == REAL_CST
 847            && ! TREE_CONSTANT_OVERFLOW (expr)
 848            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
 849           || (TREE_CODE (expr) == COMPLEX_CST
 850               && real_onep (TREE_REALPART (expr))
 851               && real_zerop (TREE_IMAGPART (expr))));
 852 }
 853
 854 /* Return 1 if EXPR is the real constant two.  */
 855
 856 int
 857 real_twop (tree expr)
 858 {
 859   STRIP_NOPS (expr);
 860
 861   return ((TREE_CODE (expr) == REAL_CST
 862            && ! TREE_CONSTANT_OVERFLOW (expr)
 863            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
 864           || (TREE_CODE (expr) == COMPLEX_CST
 865               && real_twop (TREE_REALPART (expr))
 866               && real_zerop (TREE_IMAGPART (expr))));
 867 }
 868
 869 /* Return 1 if EXPR is the real constant minus one.  */
 870
 871 int
 872 real_minus_onep (tree expr)
 873 {
 874   STRIP_NOPS (expr);
 875
 876   return ((TREE_CODE (expr) == REAL_CST
 877            && ! TREE_CONSTANT_OVERFLOW (expr)
 878            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
 879           || (TREE_CODE (expr) == COMPLEX_CST
 880               && real_minus_onep (TREE_REALPART (expr))
 881               && real_zerop (TREE_IMAGPART (expr))));
 882 }
 883
 884 /* Nonzero if EXP is a constant or a cast of a constant.  */
 885
 886 int
 887 really_constant_p (tree exp)
 888 {
 889   /* This is not quite the same as STRIP_NOPS.  It does more.  */
 890   while (TREE_CODE (exp) == NOP_EXPR
 891          || TREE_CODE (exp) == CONVERT_EXPR
 892          || TREE_CODE (exp) == NON_LVALUE_EXPR)
 893     exp = TREE_OPERAND (exp, 0);
 894   return TREE_CONSTANT (exp);
 895 }
 896 \f
 897 /* Return first list element whose TREE_VALUE is ELEM.
 898    Return 0 if ELEM is not in LIST.  */
 899
 900 tree
 901 value_member (tree elem, tree list)
 902 {
 903   while (list)
 904     {
 905       if (elem == TREE_VALUE (list))
 906         return list;
 907       list = TREE_CHAIN (list);
 908     }
 909   return NULL_TREE;
 910 }
 911
 912 /* Return first list element whose TREE_PURPOSE is ELEM.
 913    Return 0 if ELEM is not in LIST.  */
 914
 915 tree
 916 purpose_member (tree elem, tree list)
 917 {
 918   while (list)
 919     {
 920       if (elem == TREE_PURPOSE (list))
 921         return list;
 922       list = TREE_CHAIN (list);
 923     }
 924   return NULL_TREE;
 925 }
 926
 927 /* Return first list element whose BINFO_TYPE is ELEM.
 928    Return 0 if ELEM is not in LIST.  */
 929
 930 tree
 931 binfo_member (tree elem, tree list)
 932 {
 933   while (list)
 934     {
 935       if (elem == BINFO_TYPE (list))
 936         return list;
 937       list = TREE_CHAIN (list);
 938     }
 939   return NULL_TREE;
 940 }
 941
 942 /* Return nonzero if ELEM is part of the chain CHAIN.  */
 943
 944 int
 945 chain_member (tree elem, tree chain)
 946 {
 947   while (chain)
 948     {
 949       if (elem == chain)
 950         return 1;
 951       chain = TREE_CHAIN (chain);
 952     }
 953
 954   return 0;
 955 }
 956
 957 /* Return the length of a chain of nodes chained through TREE_CHAIN.
 958    We expect a null pointer to mark the end of the chain.
 959    This is the Lisp primitive `length'.  */
 960
 961 int
 962 list_length (tree t)
 963 {
 964   tree p = t;
 965 #ifdef ENABLE_TREE_CHECKING
 966   tree q = t;
 967 #endif
 968   int len = 0;
 969
 970   while (p)
 971     {
 972       p = TREE_CHAIN (p);
 973 #ifdef ENABLE_TREE_CHECKING
 974       if (len % 2)
 975         q = TREE_CHAIN (q);
 976       if (p == q)
 977         abort ();
 978 #endif
 979       len++;
 980     }
 981
 982   return len;
 983 }
 984
 985 /* Returns the number of FIELD_DECLs in TYPE.  */
 986
 987 int
 988 fields_length (tree type)
 989 {
 990   tree t = TYPE_FIELDS (type);
 991   int count = 0;
 992
 993   for (; t; t = TREE_CHAIN (t))
 994     if (TREE_CODE (t) == FIELD_DECL)
 995       ++count;
 996
 997   return count;
 998 }
 999
1000 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1001    by modifying the last node in chain 1 to point to chain 2.
1002    This is the Lisp primitive `nconc'.  */
1003
1004 tree
1005 chainon (tree op1, tree op2)
1006 {
1007   tree t1;
1008
1009   if (!op1)
1010     return op2;
1011   if (!op2)
1012     return op1;
1013
1014   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1015     continue;
1016   TREE_CHAIN (t1) = op2;
1017
1018 #ifdef ENABLE_TREE_CHECKING
1019   {
1020     tree t2;
1021     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1022       if (t2 == t1)
1023         abort ();  /* Circularity created.  */
1024   }
1025 #endif
1026
1027   return op1;
1028 }
1029
1030 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1031
1032 tree
1033 tree_last (tree chain)
1034 {
1035   tree next;
1036   if (chain)
1037     while ((next = TREE_CHAIN (chain)))
1038       chain = next;
1039   return chain;
1040 }
1041
1042 /* Reverse the order of elements in the chain T,
1043    and return the new head of the chain (old last element).  */
1044
1045 tree
1046 nreverse (tree t)
1047 {
1048   tree prev = 0, decl, next;
1049   for (decl = t; decl; decl = next)
1050     {
1051       next = TREE_CHAIN (decl);
1052       TREE_CHAIN (decl) = prev;
1053       prev = decl;
1054     }
1055   return prev;
1056 }
1057 \f
1058 /* Return a newly created TREE_LIST node whose
1059    purpose and value fields are PARM and VALUE.  */
1060
1061 tree
1062 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1063 {
1064   tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1065   TREE_PURPOSE (t) = parm;
1066   TREE_VALUE (t) = value;
1067   return t;
1068 }
1069
1070 /* Return a newly created TREE_LIST node whose
1071    purpose and value fields are PURPOSE and VALUE
1072    and whose TREE_CHAIN is CHAIN.  */
1073
1074 tree
1075 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1076 {
1077   tree node;
1078
1079   node = ggc_alloc_zone_stat (sizeof (struct tree_list),
1080                               tree_zone PASS_MEM_STAT);
1081
1082   memset (node, 0, sizeof (struct tree_common));
1083
1084 #ifdef GATHER_STATISTICS
1085   tree_node_counts[(int) x_kind]++;
1086   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1087 #endif
1088
1089   TREE_SET_CODE (node, TREE_LIST);
1090   TREE_CHAIN (node) = chain;
1091   TREE_PURPOSE (node) = purpose;
1092   TREE_VALUE (node) = value;
1093   return node;
1094 }
1095
1096 \f
1097 /* Return the size nominally occupied by an object of type TYPE
1098    when it resides in memory.  The value is measured in units of bytes,
1099    and its data type is that normally used for type sizes
1100    (which is the first type created by make_signed_type or
1101    make_unsigned_type).  */
1102
1103 tree
1104 size_in_bytes (tree type)
1105 {
1106   tree t;
1107
1108   if (type == error_mark_node)
1109     return integer_zero_node;
1110
1111   type = TYPE_MAIN_VARIANT (type);
1112   t = TYPE_SIZE_UNIT (type);
1113
1114   if (t == 0)
1115     {
1116       lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1117       return size_zero_node;
1118     }
1119
1120   if (TREE_CODE (t) == INTEGER_CST)
1121     force_fit_type (t, 0);
1122
1123   return t;
1124 }
1125
1126 /* Return the size of TYPE (in bytes) as a wide integer
1127    or return -1 if the size can vary or is larger than an integer.  */
1128
1129 HOST_WIDE_INT
1130 int_size_in_bytes (tree type)
1131 {
1132   tree t;
1133
1134   if (type == error_mark_node)
1135     return 0;
1136
1137   type = TYPE_MAIN_VARIANT (type);
1138   t = TYPE_SIZE_UNIT (type);
1139   if (t == 0
1140       || TREE_CODE (t) != INTEGER_CST
1141       || TREE_OVERFLOW (t)
1142       || TREE_INT_CST_HIGH (t) != 0
1143       /* If the result would appear negative, it's too big to represent.  */
1144       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1145     return -1;
1146
1147   return TREE_INT_CST_LOW (t);
1148 }
1149 \f
1150 /* Return the bit position of FIELD, in bits from the start of the record.
1151    This is a tree of type bitsizetype.  */
1152
1153 tree
1154 bit_position (tree field)
1155 {
1156   return bit_from_pos (DECL_FIELD_OFFSET (field),
1157                        DECL_FIELD_BIT_OFFSET (field));
1158 }
1159
1160 /* Likewise, but return as an integer.  Abort if it cannot be represented
1161    in that way (since it could be a signed value, we don't have the option
1162    of returning -1 like int_size_in_byte can.  */
1163
1164 HOST_WIDE_INT
1165 int_bit_position (tree field)
1166 {
1167   return tree_low_cst (bit_position (field), 0);
1168 }
1169 \f
1170 /* Return the byte position of FIELD, in bytes from the start of the record.
1171    This is a tree of type sizetype.  */
1172
1173 tree
1174 byte_position (tree field)
1175 {
1176   return byte_from_pos (DECL_FIELD_OFFSET (field),
1177                         DECL_FIELD_BIT_OFFSET (field));
1178 }
1179
1180 /* Likewise, but return as an integer.  Abort if it cannot be represented
1181    in that way (since it could be a signed value, we don't have the option
1182    of returning -1 like int_size_in_byte can.  */
1183
1184 HOST_WIDE_INT
1185 int_byte_position (tree field)
1186 {
1187   return tree_low_cst (byte_position (field), 0);
1188 }
1189 \f
1190 /* Return the strictest alignment, in bits, that T is known to have.  */
1191
1192 unsigned int
1193 expr_align (tree t)
1194 {
1195   unsigned int align0, align1;
1196
1197   switch (TREE_CODE (t))
1198     {
1199     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1200       /* If we have conversions, we know that the alignment of the
1201          object must meet each of the alignments of the types.  */
1202       align0 = expr_align (TREE_OPERAND (t, 0));
1203       align1 = TYPE_ALIGN (TREE_TYPE (t));
1204       return MAX (align0, align1);
1205
1206     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1207     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1208     case CLEANUP_POINT_EXPR:  case UNSAVE_EXPR:
1209       /* These don't change the alignment of an object.  */
1210       return expr_align (TREE_OPERAND (t, 0));
1211
1212     case COND_EXPR:
1213       /* The best we can do is say that the alignment is the least aligned
1214          of the two arms.  */
1215       align0 = expr_align (TREE_OPERAND (t, 1));
1216       align1 = expr_align (TREE_OPERAND (t, 2));
1217       return MIN (align0, align1);
1218
1219     case LABEL_DECL:     case CONST_DECL:
1220     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1221       if (DECL_ALIGN (t) != 0)
1222         return DECL_ALIGN (t);
1223       break;
1224
1225     case FUNCTION_DECL:
1226       return FUNCTION_BOUNDARY;
1227
1228     default:
1229       break;
1230     }
1231
1232   /* Otherwise take the alignment from that of the type.  */
1233   return TYPE_ALIGN (TREE_TYPE (t));
1234 }
1235 \f
1236 /* Return, as a tree node, the number of elements for TYPE (which is an
1237    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1238
1239 tree
1240 array_type_nelts (tree type)
1241 {
1242   tree index_type, min, max;
1243
1244   /* If they did it with unspecified bounds, then we should have already
1245      given an error about it before we got here.  */
1246   if (! TYPE_DOMAIN (type))
1247     return error_mark_node;
1248
1249   index_type = TYPE_DOMAIN (type);
1250   min = TYPE_MIN_VALUE (index_type);
1251   max = TYPE_MAX_VALUE (index_type);
1252
1253   return (integer_zerop (min)
1254           ? max
1255           : fold (build2 (MINUS_EXPR, TREE_TYPE (max), max, min)));
1256 }
1257 \f
1258 /* Return nonzero if arg is static -- a reference to an object in
1259    static storage.  This is not the same as the C meaning of `static'.  */
1260
1261 int
1262 staticp (tree arg)
1263 {
1264   switch (TREE_CODE (arg))
1265     {
1266     case FUNCTION_DECL:
1267       /* Nested functions aren't static, since taking their address
1268          involves a trampoline.  */
1269       return ((decl_function_context (arg) == 0 || DECL_NO_STATIC_CHAIN (arg))
1270               && ! DECL_NON_ADDR_CONST_P (arg));
1271
1272     case VAR_DECL:
1273       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1274               && ! DECL_THREAD_LOCAL (arg)
1275               && ! DECL_NON_ADDR_CONST_P (arg));
1276
1277     case CONSTRUCTOR:
1278       return TREE_STATIC (arg);
1279
1280     case LABEL_DECL:
1281     case STRING_CST:
1282       return 1;
1283
1284     case COMPONENT_REF:
1285       /* If the thing being referenced is not a field, then it is
1286          something language specific.  */
1287       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1288         return (*lang_hooks.staticp) (arg);
1289
1290       /* If we are referencing a bitfield, we can't evaluate an
1291          ADDR_EXPR at compile time and so it isn't a constant.  */
1292       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1293         return 0;
1294
1295       return staticp (TREE_OPERAND (arg, 0));
1296
1297     case BIT_FIELD_REF:
1298       return 0;
1299
1300 #if 0
1301        /* This case is technically correct, but results in setting
1302           TREE_CONSTANT on ADDR_EXPRs that cannot be evaluated at
1303           compile time.  */
1304     case INDIRECT_REF:
1305       return TREE_CONSTANT (TREE_OPERAND (arg, 0));
1306 #endif
1307
1308     case ARRAY_REF:
1309     case ARRAY_RANGE_REF:
1310       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1311           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1312         return staticp (TREE_OPERAND (arg, 0));
1313       else
1314         return 0;
1315
1316     default:
1317       if ((unsigned int) TREE_CODE (arg)
1318           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1319         return lang_hooks.staticp (arg);
1320       else
1321         return 0;
1322     }
1323 }
1324 \f
1325 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1326    Do this to any expression which may be used in more than one place,
1327    but must be evaluated only once.
1328
1329    Normally, expand_expr would reevaluate the expression each time.
1330    Calling save_expr produces something that is evaluated and recorded
1331    the first time expand_expr is called on it.  Subsequent calls to
1332    expand_expr just reuse the recorded value.
1333
1334    The call to expand_expr that generates code that actually computes
1335    the value is the first call *at compile time*.  Subsequent calls
1336    *at compile time* generate code to use the saved value.
1337    This produces correct result provided that *at run time* control
1338    always flows through the insns made by the first expand_expr
1339    before reaching the other places where the save_expr was evaluated.
1340    You, the caller of save_expr, must make sure this is so.
1341
1342    Constants, and certain read-only nodes, are returned with no
1343    SAVE_EXPR because that is safe.  Expressions containing placeholders
1344    are not touched; see tree.def for an explanation of what these
1345    are used for.  */
1346
1347 tree
1348 save_expr (tree expr)
1349 {
1350   tree t = fold (expr);
1351   tree inner;
1352
1353   /* If the tree evaluates to a constant, then we don't want to hide that
1354      fact (i.e. this allows further folding, and direct checks for constants).
1355      However, a read-only object that has side effects cannot be bypassed.
1356      Since it is no problem to reevaluate literals, we just return the
1357      literal node.  */
1358   inner = skip_simple_arithmetic (t);
1359
1360   if (TREE_INVARIANT (inner)
1361       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1362       || TREE_CODE (inner) == SAVE_EXPR
1363       || TREE_CODE (inner) == ERROR_MARK)
1364     return t;
1365
1366   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1367      it means that the size or offset of some field of an object depends on
1368      the value within another field.
1369
1370      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1371      and some variable since it would then need to be both evaluated once and
1372      evaluated more than once.  Front-ends must assure this case cannot
1373      happen by surrounding any such subexpressions in their own SAVE_EXPR
1374      and forcing evaluation at the proper time.  */
1375   if (contains_placeholder_p (inner))
1376     return t;
1377
1378   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
1379
1380   /* This expression might be placed ahead of a jump to ensure that the
1381      value was computed on both sides of the jump.  So make sure it isn't
1382      eliminated as dead.  */
1383   TREE_SIDE_EFFECTS (t) = 1;
1384   TREE_READONLY (t) = 1;
1385   TREE_INVARIANT (t) = 1;
1386   return t;
1387 }
1388
1389 /* Look inside EXPR and into any simple arithmetic operations.  Return
1390    the innermost non-arithmetic node.  */
1391
1392 tree
1393 skip_simple_arithmetic (tree expr)
1394 {
1395   tree inner;
1396
1397   /* We don't care about whether this can be used as an lvalue in this
1398      context.  */
1399   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
1400     expr = TREE_OPERAND (expr, 0);
1401
1402   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
1403      a constant, it will be more efficient to not make another SAVE_EXPR since
1404      it will allow better simplification and GCSE will be able to merge the
1405      computations if they actually occur.  */
1406   inner = expr;
1407   while (1)
1408     {
1409       if (TREE_CODE_CLASS (TREE_CODE (inner)) == '1')
1410         inner = TREE_OPERAND (inner, 0);
1411       else if (TREE_CODE_CLASS (TREE_CODE (inner)) == '2')
1412         {
1413           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
1414             inner = TREE_OPERAND (inner, 0);
1415           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
1416             inner = TREE_OPERAND (inner, 1);
1417           else
1418             break;
1419         }
1420       else
1421         break;
1422     }
1423
1424   return inner;
1425 }
1426
1427 /* Arrange for an expression to be expanded multiple independent
1428    times.  This is useful for cleanup actions, as the backend can
1429    expand them multiple times in different places.  */
1430
1431 tree
1432 unsave_expr (tree expr)
1433 {
1434   tree t;
1435
1436   /* If this is already protected, no sense in protecting it again.  */
1437   if (TREE_CODE (expr) == UNSAVE_EXPR)
1438     return expr;
1439
1440   t = build1 (UNSAVE_EXPR, TREE_TYPE (expr), expr);
1441   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (expr);
1442   return t;
1443 }
1444
1445 /* Returns the index of the first non-tree operand for CODE, or the number
1446    of operands if all are trees.  */
1447
1448 int
1449 first_rtl_op (enum tree_code code)
1450 {
1451   switch (code)
1452     {
1453     case GOTO_SUBROUTINE_EXPR:
1454       return 0;
1455     case WITH_CLEANUP_EXPR:
1456       return 2;
1457     default:
1458       return TREE_CODE_LENGTH (code);
1459     }
1460 }
1461
1462 /* Return which tree structure is used by T.  */
1463
1464 enum tree_node_structure_enum
1465 tree_node_structure (tree t)
1466 {
1467   enum tree_code code = TREE_CODE (t);
1468
1469   switch (TREE_CODE_CLASS (code))
1470     {
1471     case 'd':   return TS_DECL;
1472     case 't':   return TS_TYPE;
1473     case 'r': case '<': case '1': case '2': case 'e': case 's':
1474       return TS_EXP;
1475     default:  /* 'c' and 'x' */
1476       break;
1477     }
1478   switch (code)
1479     {
1480       /* 'c' cases.  */
1481     case INTEGER_CST:           return TS_INT_CST;
1482     case REAL_CST:              return TS_REAL_CST;
1483     case COMPLEX_CST:           return TS_COMPLEX;
1484     case VECTOR_CST:            return TS_VECTOR;
1485     case STRING_CST:            return TS_STRING;
1486       /* 'x' cases.  */
1487     case ERROR_MARK:            return TS_COMMON;
1488     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
1489     case TREE_LIST:             return TS_LIST;
1490     case TREE_VEC:              return TS_VEC;
1491     case PHI_NODE:              return TS_PHI_NODE;
1492     case SSA_NAME:              return TS_SSA_NAME;
1493     case PLACEHOLDER_EXPR:      return TS_COMMON;
1494     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
1495     case BLOCK:                 return TS_BLOCK;
1496     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
1497
1498     default:
1499       abort ();
1500     }
1501 }
1502
1503 /* Perform any modifications to EXPR required when it is unsaved.  Does
1504    not recurse into EXPR's subtrees.  */
1505
1506 void
1507 unsave_expr_1 (tree expr)
1508 {
1509   switch (TREE_CODE (expr))
1510     {
1511     case TARGET_EXPR:
1512       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
1513          It's OK for this to happen if it was part of a subtree that
1514          isn't immediately expanded, such as operand 2 of another
1515          TARGET_EXPR.  */
1516       if (TREE_OPERAND (expr, 1))
1517         break;
1518
1519       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
1520       TREE_OPERAND (expr, 3) = NULL_TREE;
1521       break;
1522
1523     default:
1524       break;
1525     }
1526 }
1527
1528 /* Return 0 if it is safe to evaluate EXPR multiple times,
1529    return 1 if it is safe if EXPR is unsaved afterward, or
1530    return 2 if it is completely unsafe.
1531
1532    This assumes that CALL_EXPRs and TARGET_EXPRs are never replicated in
1533    an expression tree, so that it safe to unsave them and the surrounding
1534    context will be correct.
1535
1536    SAVE_EXPRs basically *only* appear replicated in an expression tree,
1537    occasionally across the whole of a function.  It is therefore only
1538    safe to unsave a SAVE_EXPR if you know that all occurrences appear
1539    below the UNSAVE_EXPR.  */
1540
1541 int
1542 unsafe_for_reeval (tree expr)
1543 {
1544   int unsafeness = 0;
1545   enum tree_code code;
1546   int i, tmp, tmp2;
1547   tree exp;
1548   int first_rtl;
1549
1550   if (expr == NULL_TREE)
1551     return 1;
1552
1553   code = TREE_CODE (expr);
1554   first_rtl = first_rtl_op (code);
1555
1556   switch (code)
1557     {
1558     case SAVE_EXPR:
1559       return 2;
1560
1561       /* A label can only be emitted once.  */
1562     case LABEL_EXPR:
1563       return 1;
1564
1565     case BIND_EXPR:
1566       unsafeness = 1;
1567       break;
1568
1569     case TREE_LIST:
1570       for (exp = expr; exp != 0; exp = TREE_CHAIN (exp))
1571         {
1572           tmp = unsafe_for_reeval (TREE_VALUE (exp));
1573           unsafeness = MAX (tmp, unsafeness);
1574         }
1575
1576       return unsafeness;
1577
1578     case CALL_EXPR:
1579       tmp2 = unsafe_for_reeval (TREE_OPERAND (expr, 0));
1580       tmp = unsafe_for_reeval (TREE_OPERAND (expr, 1));
1581       return MAX (MAX (tmp, 1), tmp2);
1582
1583     case TARGET_EXPR:
1584       unsafeness = 1;
1585       break;
1586
1587     case EXIT_BLOCK_EXPR:
1588       /* EXIT_BLOCK_LABELED_BLOCK, a.k.a. TREE_OPERAND (expr, 0), holds
1589          a reference to an ancestor LABELED_BLOCK, so we need to avoid
1590          unbounded recursion in the 'e' traversal code below.  */
1591       exp = EXIT_BLOCK_RETURN (expr);
1592       return exp ? unsafe_for_reeval (exp) : 0;
1593
1594     default:
1595       tmp = lang_hooks.unsafe_for_reeval (expr);
1596       if (tmp >= 0)
1597         return tmp;
1598       break;
1599     }
1600
1601   switch (TREE_CODE_CLASS (code))
1602     {
1603     case 'c':  /* a constant */
1604     case 't':  /* a type node */
1605     case 'x':  /* something random, like an identifier or an ERROR_MARK.  */
1606     case 'd':  /* A decl node */
1607       return 0;
1608
1609     case 'e':  /* an expression */
1610     case 'r':  /* a reference */
1611     case 's':  /* an expression with side effects */
1612     case '<':  /* a comparison expression */
1613     case '2':  /* a binary arithmetic expression */
1614     case '1':  /* a unary arithmetic expression */
1615       for (i = first_rtl - 1; i >= 0; i--)
1616         {
1617           tmp = unsafe_for_reeval (TREE_OPERAND (expr, i));
1618           unsafeness = MAX (tmp, unsafeness);
1619         }
1620
1621       return unsafeness;
1622
1623     default:
1624       return 2;
1625     }
1626 }
1627 \f
1628 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
1629    or offset that depends on a field within a record.  */
1630
1631 bool
1632 contains_placeholder_p (tree exp)
1633 {
1634   enum tree_code code;
1635
1636   if (!exp)
1637     return 0;
1638
1639   code = TREE_CODE (exp);
1640   if (code == PLACEHOLDER_EXPR)
1641     return 1;
1642
1643   switch (TREE_CODE_CLASS (code))
1644     {
1645     case 'r':
1646       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
1647          position computations since they will be converted into a
1648          WITH_RECORD_EXPR involving the reference, which will assume
1649          here will be valid.  */
1650       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1651
1652     case 'x':
1653       if (code == TREE_LIST)
1654         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
1655                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
1656       break;
1657
1658     case '1':
1659     case '2':  case '<':
1660     case 'e':
1661       switch (code)
1662         {
1663         case COMPOUND_EXPR:
1664           /* Ignoring the first operand isn't quite right, but works best.  */
1665           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
1666
1667         case COND_EXPR:
1668           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1669                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
1670                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
1671
1672         default:
1673           break;
1674         }
1675
1676       switch (first_rtl_op (code))
1677         {
1678         case 1:
1679           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1680         case 2:
1681           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1682                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
1683         default:
1684           return 0;
1685         }
1686
1687     default:
1688       return 0;
1689     }
1690   return 0;
1691 }
1692
1693 /* Return 1 if any part of the computation of TYPE involves a PLACEHOLDER_EXPR.
1694    This includes size, bounds, qualifiers (for QUAL_UNION_TYPE) and field
1695    positions.  */
1696
1697 bool
1698 type_contains_placeholder_p (tree type)
1699 {
1700   /* If the size contains a placeholder or the parent type (component type in
1701      the case of arrays) type involves a placeholder, this type does.  */
1702   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
1703       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
1704       || (TREE_TYPE (type) != 0
1705           && type_contains_placeholder_p (TREE_TYPE (type))))
1706     return 1;
1707
1708   /* Now do type-specific checks.  Note that the last part of the check above
1709      greatly limits what we have to do below.  */
1710   switch (TREE_CODE (type))
1711     {
1712     case VOID_TYPE:
1713     case COMPLEX_TYPE:
1714     case ENUMERAL_TYPE:
1715     case BOOLEAN_TYPE:
1716     case CHAR_TYPE:
1717     case POINTER_TYPE:
1718     case OFFSET_TYPE:
1719     case REFERENCE_TYPE:
1720     case METHOD_TYPE:
1721     case FILE_TYPE:
1722     case FUNCTION_TYPE:
1723       return 0;
1724
1725     case INTEGER_TYPE:
1726     case REAL_TYPE:
1727       /* Here we just check the bounds.  */
1728       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
1729               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
1730
1731     case ARRAY_TYPE:
1732     case SET_TYPE:
1733     case VECTOR_TYPE:
1734       /* We're already checked the component type (TREE_TYPE), so just check
1735          the index type.  */
1736       return type_contains_placeholder_p (TYPE_DOMAIN (type));
1737
1738     case RECORD_TYPE:
1739     case UNION_TYPE:
1740     case QUAL_UNION_TYPE:
1741       {
1742         static tree seen_types = 0;
1743         tree field;
1744         bool ret = 0;
1745
1746         /* We have to be careful here that we don't end up in infinite
1747            recursions due to a field of a type being a pointer to that type
1748            or to a mutually-recursive type.  So we store a list of record
1749            types that we've seen and see if this type is in them.  To save
1750            memory, we don't use a list for just one type.  Here we check
1751            whether we've seen this type before and store it if not.  */
1752         if (seen_types == 0)
1753           seen_types = type;
1754         else if (TREE_CODE (seen_types) != TREE_LIST)
1755           {
1756             if (seen_types == type)
1757               return 0;
1758
1759             seen_types = tree_cons (NULL_TREE, type,
1760                                     build_tree_list (NULL_TREE, seen_types));
1761           }
1762         else
1763           {
1764             if (value_member (type, seen_types) != 0)
1765               return 0;
1766
1767             seen_types = tree_cons (NULL_TREE, type, seen_types);
1768           }
1769
1770         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
1771           if (TREE_CODE (field) == FIELD_DECL
1772               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
1773                   || (TREE_CODE (type) == QUAL_UNION_TYPE
1774                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
1775                   || type_contains_placeholder_p (TREE_TYPE (field))))
1776             {
1777               ret = true;
1778               break;
1779             }
1780
1781         /* Now remove us from seen_types and return the result.  */
1782         if (seen_types == type)
1783           seen_types = 0;
1784         else
1785           seen_types = TREE_CHAIN (seen_types);
1786
1787         return ret;
1788       }
1789
1790     default:
1791       abort ();
1792     }
1793 }
1794
1795 /* Return 1 if EXP contains any expressions that produce cleanups for an
1796    outer scope to deal with.  Used by fold.  */
1797
1798 int
1799 has_cleanups (tree exp)
1800 {
1801   int i, nops, cmp;
1802
1803   if (! TREE_SIDE_EFFECTS (exp))
1804     return 0;
1805
1806   switch (TREE_CODE (exp))
1807     {
1808     case TARGET_EXPR:
1809     case GOTO_SUBROUTINE_EXPR:
1810     case WITH_CLEANUP_EXPR:
1811       return 1;
1812
1813     case CLEANUP_POINT_EXPR:
1814       return 0;
1815
1816     case CALL_EXPR:
1817       for (exp = TREE_OPERAND (exp, 1); exp; exp = TREE_CHAIN (exp))
1818         {
1819           cmp = has_cleanups (TREE_VALUE (exp));
1820           if (cmp)
1821             return cmp;
1822         }
1823       return 0;
1824
1825     case DECL_EXPR:
1826       return (DECL_INITIAL (DECL_EXPR_DECL (exp))
1827               && has_cleanups (DECL_INITIAL (DECL_EXPR_DECL (exp))));
1828
1829     default:
1830       break;
1831     }
1832
1833   /* This general rule works for most tree codes.  All exceptions should be
1834      handled above.  If this is a language-specific tree code, we can't
1835      trust what might be in the operand, so say we don't know
1836      the situation.  */
1837   if ((int) TREE_CODE (exp) >= (int) LAST_AND_UNUSED_TREE_CODE)
1838     return -1;
1839
1840   nops = first_rtl_op (TREE_CODE (exp));
1841   for (i = 0; i < nops; i++)
1842     if (TREE_OPERAND (exp, i) != 0)
1843       {
1844         int type = TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (exp, i)));
1845         if (type == 'e' || type == '<' || type == '1' || type == '2'
1846             || type == 'r' || type == 's')
1847           {
1848             cmp = has_cleanups (TREE_OPERAND (exp, i));
1849             if (cmp)
1850               return cmp;
1851           }
1852       }
1853
1854   return 0;
1855 }
1856 \f
1857 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
1858    return a tree with all occurrences of references to F in a
1859    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
1860    contains only arithmetic expressions or a CALL_EXPR with a
1861    PLACEHOLDER_EXPR occurring only in its arglist.  */
1862
1863 tree
1864 substitute_in_expr (tree exp, tree f, tree r)
1865 {
1866   enum tree_code code = TREE_CODE (exp);
1867   tree op0, op1, op2;
1868   tree new;
1869   tree inner;
1870
1871   /* We handle TREE_LIST and COMPONENT_REF separately.  */
1872   if (code == TREE_LIST)
1873     {
1874       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
1875       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
1876       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
1877         return exp;
1878
1879       return tree_cons (TREE_PURPOSE (exp), op1, op0);
1880     }
1881   else if (code == COMPONENT_REF)
1882    {
1883      /* If this expression is getting a value from a PLACEHOLDER_EXPR
1884         and it is the right field, replace it with R.  */
1885      for (inner = TREE_OPERAND (exp, 0);
1886           TREE_CODE_CLASS (TREE_CODE (inner)) == 'r';
1887           inner = TREE_OPERAND (inner, 0))
1888        ;
1889      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
1890          && TREE_OPERAND (exp, 1) == f)
1891        return r;
1892
1893      /* If this expression hasn't been completed let, leave it
1894         alone.  */
1895      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
1896        return exp;
1897
1898      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1899      if (op0 == TREE_OPERAND (exp, 0))
1900        return exp;
1901
1902      new = fold (build (code, TREE_TYPE (exp), op0, TREE_OPERAND (exp, 1),
1903                         NULL_TREE));
1904    }
1905   else
1906     switch (TREE_CODE_CLASS (code))
1907       {
1908       case 'c':
1909       case 'd':
1910         return exp;
1911
1912       case 'x':
1913       case '1':
1914       case '2':
1915       case '<':
1916       case 'e':
1917       case 'r':
1918         switch (first_rtl_op (code))
1919           {
1920           case 0:
1921             return exp;
1922
1923           case 1:
1924             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1925             if (op0 == TREE_OPERAND (exp, 0))
1926               return exp;
1927
1928             new = fold (build1 (code, TREE_TYPE (exp), op0));
1929             break;
1930
1931           case 2:
1932             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1933             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
1934
1935             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
1936               return exp;
1937
1938             new = fold (build2 (code, TREE_TYPE (exp), op0, op1));
1939             break;
1940
1941           case 3:
1942             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1943             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
1944             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
1945
1946             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
1947                 && op2 == TREE_OPERAND (exp, 2))
1948               return exp;
1949
1950             new = fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
1951             break;
1952
1953           default:
1954             abort ();
1955           }
1956         break;
1957
1958       default:
1959         abort ();
1960       }
1961
1962   TREE_READONLY (new) = TREE_READONLY (exp);
1963   return new;
1964 }
1965
1966 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
1967    for it within OBJ, a tree that is an object or a chain of references.  */
1968
1969 tree
1970 substitute_placeholder_in_expr (tree exp, tree obj)
1971 {
1972   enum tree_code code = TREE_CODE (exp);
1973   tree op0, op1, op2, op3;
1974
1975   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
1976      in the chain of OBJ.  */
1977   if (code == PLACEHOLDER_EXPR)
1978     {
1979       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
1980       tree elt;
1981
1982       for (elt = obj; elt != 0;
1983            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
1984                    || TREE_CODE (elt) == COND_EXPR)
1985                   ? TREE_OPERAND (elt, 1)
1986                   : (TREE_CODE_CLASS (TREE_CODE (elt)) == 'r'
1987                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '1'
1988                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '2'
1989                      || TREE_CODE_CLASS (TREE_CODE (elt)) == 'e')
1990                   ? TREE_OPERAND (elt, 0) : 0))
1991         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
1992           return elt;
1993
1994       for (elt = obj; elt != 0;
1995            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
1996                    || TREE_CODE (elt) == COND_EXPR)
1997                   ? TREE_OPERAND (elt, 1)
1998                   : (TREE_CODE_CLASS (TREE_CODE (elt)) == 'r'
1999                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '1'
2000                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '2'
2001                      || TREE_CODE_CLASS (TREE_CODE (elt)) == 'e')
2002                   ? TREE_OPERAND (elt, 0) : 0))
2003         if (POINTER_TYPE_P (TREE_TYPE (elt))
2004             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2005                 == need_type))
2006           return fold (build1 (INDIRECT_REF, need_type, elt));
2007
2008       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2009          survives until RTL generation, there will be an error.  */
2010       return exp;
2011     }
2012
2013   /* TREE_LIST is special because we need to look at TREE_VALUE
2014      and TREE_CHAIN, not TREE_OPERANDS.  */
2015   else if (code == TREE_LIST)
2016     {
2017       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2018       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2019       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2020         return exp;
2021
2022       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2023     }
2024   else
2025     switch (TREE_CODE_CLASS (code))
2026       {
2027       case 'c':
2028       case 'd':
2029         return exp;
2030
2031       case 'x':
2032       case '1':
2033       case '2':
2034       case '<':
2035       case 'e':
2036       case 'r':
2037       case 's':
2038         switch (first_rtl_op (code))
2039           {
2040           case 0:
2041             return exp;
2042
2043           case 1:
2044             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2045             if (op0 == TREE_OPERAND (exp, 0))
2046               return exp;
2047             else
2048               return fold (build1 (code, TREE_TYPE (exp), op0));
2049
2050           case 2:
2051             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2052             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2053
2054             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2055               return exp;
2056             else
2057               return fold (build2 (code, TREE_TYPE (exp), op0, op1));
2058
2059           case 3:
2060             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2061             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2062             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2063
2064             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2065                 && op2 == TREE_OPERAND (exp, 2))
2066               return exp;
2067             else
2068               return fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
2069
2070           case 4:
2071             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2072             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2073             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2074             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2075
2076             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2077                 && op2 == TREE_OPERAND (exp, 2)
2078                 && op3 == TREE_OPERAND (exp, 3))
2079               return exp;
2080             else
2081               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2082
2083           default:
2084             abort ();
2085           }
2086         break;
2087
2088       default:
2089         abort ();
2090       }
2091 }
2092 \f
2093 /* Stabilize a reference so that we can use it any number of times
2094    without causing its operands to be evaluated more than once.
2095    Returns the stabilized reference.  This works by means of save_expr,
2096    so see the caveats in the comments about save_expr.
2097
2098    Also allows conversion expressions whose operands are references.
2099    Any other kind of expression is returned unchanged.  */
2100
2101 tree
2102 stabilize_reference (tree ref)
2103 {
2104   tree result;
2105   enum tree_code code = TREE_CODE (ref);
2106
2107   switch (code)
2108     {
2109     case VAR_DECL:
2110     case PARM_DECL:
2111     case RESULT_DECL:
2112       /* No action is needed in this case.  */
2113       return ref;
2114
2115     case NOP_EXPR:
2116     case CONVERT_EXPR:
2117     case FLOAT_EXPR:
2118     case FIX_TRUNC_EXPR:
2119     case FIX_FLOOR_EXPR:
2120     case FIX_ROUND_EXPR:
2121     case FIX_CEIL_EXPR:
2122       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2123       break;
2124
2125     case INDIRECT_REF:
2126       result = build_nt (INDIRECT_REF,
2127                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2128       break;
2129
2130     case COMPONENT_REF:
2131       result = build_nt (COMPONENT_REF,
2132                          stabilize_reference (TREE_OPERAND (ref, 0)),
2133                          TREE_OPERAND (ref, 1), NULL_TREE);
2134       break;
2135
2136     case BIT_FIELD_REF:
2137       result = build_nt (BIT_FIELD_REF,
2138                          stabilize_reference (TREE_OPERAND (ref, 0)),
2139                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2140                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2141       break;
2142
2143     case ARRAY_REF:
2144       result = build_nt (ARRAY_REF,
2145                          stabilize_reference (TREE_OPERAND (ref, 0)),
2146                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2147                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2148       break;
2149
2150     case ARRAY_RANGE_REF:
2151       result = build_nt (ARRAY_RANGE_REF,
2152                          stabilize_reference (TREE_OPERAND (ref, 0)),
2153                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2154                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2155       break;
2156
2157     case COMPOUND_EXPR:
2158       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2159          it wouldn't be ignored.  This matters when dealing with
2160          volatiles.  */
2161       return stabilize_reference_1 (ref);
2162
2163       /* If arg isn't a kind of lvalue we recognize, make no change.
2164          Caller should recognize the error for an invalid lvalue.  */
2165     default:
2166       return ref;
2167
2168     case ERROR_MARK:
2169       return error_mark_node;
2170     }
2171
2172   TREE_TYPE (result) = TREE_TYPE (ref);
2173   TREE_READONLY (result) = TREE_READONLY (ref);
2174   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2175   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2176
2177   return result;
2178 }
2179
2180 /* Subroutine of stabilize_reference; this is called for subtrees of
2181    references.  Any expression with side-effects must be put in a SAVE_EXPR
2182    to ensure that it is only evaluated once.
2183
2184    We don't put SAVE_EXPR nodes around everything, because assigning very
2185    simple expressions to temporaries causes us to miss good opportunities
2186    for optimizations.  Among other things, the opportunity to fold in the
2187    addition of a constant into an addressing mode often gets lost, e.g.
2188    "y[i+1] += x;".  In general, we take the approach that we should not make
2189    an assignment unless we are forced into it - i.e., that any non-side effect
2190    operator should be allowed, and that cse should take care of coalescing
2191    multiple utterances of the same expression should that prove fruitful.  */
2192
2193 tree
2194 stabilize_reference_1 (tree e)
2195 {
2196   tree result;
2197   enum tree_code code = TREE_CODE (e);
2198
2199   /* We cannot ignore const expressions because it might be a reference
2200      to a const array but whose index contains side-effects.  But we can
2201      ignore things that are actual constant or that already have been
2202      handled by this function.  */
2203
2204   if (TREE_INVARIANT (e))
2205     return e;
2206
2207   switch (TREE_CODE_CLASS (code))
2208     {
2209     case 'x':
2210     case 't':
2211     case 'd':
2212     case '<':
2213     case 's':
2214     case 'e':
2215     case 'r':
2216       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2217          so that it will only be evaluated once.  */
2218       /* The reference (r) and comparison (<) classes could be handled as
2219          below, but it is generally faster to only evaluate them once.  */
2220       if (TREE_SIDE_EFFECTS (e))
2221         return save_expr (e);
2222       return e;
2223
2224     case 'c':
2225       /* Constants need no processing.  In fact, we should never reach
2226          here.  */
2227       return e;
2228
2229     case '2':
2230       /* Division is slow and tends to be compiled with jumps,
2231          especially the division by powers of 2 that is often
2232          found inside of an array reference.  So do it just once.  */
2233       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2234           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2235           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2236           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2237         return save_expr (e);
2238       /* Recursively stabilize each operand.  */
2239       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2240                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2241       break;
2242
2243     case '1':
2244       /* Recursively stabilize each operand.  */
2245       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2246       break;
2247
2248     default:
2249       abort ();
2250     }
2251
2252   TREE_TYPE (result) = TREE_TYPE (e);
2253   TREE_READONLY (result) = TREE_READONLY (e);
2254   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2255   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2256   TREE_INVARIANT (result) = 1;
2257
2258   return result;
2259 }
2260 \f
2261 /* Low-level constructors for expressions.  */
2262
2263 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2264    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2265
2266 void
2267 recompute_tree_invarant_for_addr_expr (tree t)
2268 {
2269   tree node;
2270   bool tc = true, ti = true, se = false;
2271
2272   /* We started out assuming this address is both invariant and constant, but
2273      does not have side effects.  Now go down any handled components and see if
2274      any of them involve offsets that are either non-constant or non-invariant.
2275      Also check for side-effects.
2276
2277      ??? Note that this code makes no attempt to deal with the case where
2278      taking the address of something causes a copy due to misalignment.  */
2279
2280 #define UPDATE_TITCSE(NODE)  \
2281 do { tree _node = (NODE); \
2282      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2283      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2284      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2285
2286   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2287        node = TREE_OPERAND (node, 0))
2288     {
2289       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2290          array reference (probably made temporarily by the G++ front end),
2291          so ignore all the operands.  */
2292       if ((TREE_CODE (node) == ARRAY_REF
2293            || TREE_CODE (node) == ARRAY_RANGE_REF)
2294           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2295         {
2296           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2297           UPDATE_TITCSE (array_ref_low_bound (node));
2298           UPDATE_TITCSE (array_ref_element_size (node));
2299         }
2300       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2301          FIELD_DECL, apparently.  The G++ front end can put something else
2302          there, at least temporarily.  */
2303       else if (TREE_CODE (node) == COMPONENT_REF
2304                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2305         UPDATE_TITCSE (component_ref_field_offset (node));
2306       else if (TREE_CODE (node) == BIT_FIELD_REF)
2307         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2308     }
2309
2310   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2311      it.  If it's a decl, it's definitely invariant and it's constant if the
2312      decl is static.  (Taking the address of a volatile variable is not
2313      volatile.)  If it's a constant, the address is both invariant and
2314      constant.  Otherwise it's neither.  */
2315   if (TREE_CODE (node) == INDIRECT_REF)
2316     UPDATE_TITCSE (node);
2317   else if (DECL_P (node))
2318     {
2319       if (!staticp (node))
2320         tc = false;
2321     }
2322   else if (TREE_CODE_CLASS (TREE_CODE (node)) == 'c')
2323     ;
2324   else
2325     {
2326       ti = tc = false;
2327       se |= TREE_SIDE_EFFECTS (node);
2328     }
2329
2330   TREE_CONSTANT (t) = tc;
2331   TREE_INVARIANT (t) = ti;
2332   TREE_SIDE_EFFECTS (t) = se;
2333 #undef UPDATE_TITCSE
2334 }
2335
2336 /* Build an expression of code CODE, data type TYPE, and operands as
2337    specified.  Expressions and reference nodes can be created this way.
2338    Constants, decls, types and misc nodes cannot be.
2339
2340    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2341    enough for all extant tree codes.  These functions can be called
2342    directly (preferably!), but can also be obtained via GCC preprocessor
2343    magic within the build macro.  */
2344
2345 tree
2346 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2347 {
2348   tree t;
2349
2350 #ifdef ENABLE_CHECKING
2351   if (TREE_CODE_LENGTH (code) != 0)
2352     abort ();
2353 #endif
2354
2355   t = make_node_stat (code PASS_MEM_STAT);
2356   TREE_TYPE (t) = tt;
2357
2358   return t;
2359 }
2360
2361 tree
2362 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2363 {
2364   int length = sizeof (struct tree_exp);
2365 #ifdef GATHER_STATISTICS
2366   tree_node_kind kind;
2367 #endif
2368   tree t;
2369
2370 #ifdef GATHER_STATISTICS
2371   switch (TREE_CODE_CLASS (code))
2372     {
2373     case 's':  /* an expression with side effects */
2374       kind = s_kind;
2375       break;
2376     case 'r':  /* a reference */
2377       kind = r_kind;
2378       break;
2379     default:
2380       kind = e_kind;
2381       break;
2382     }
2383
2384   tree_node_counts[(int) kind]++;
2385   tree_node_sizes[(int) kind] += length;
2386 #endif
2387
2388 #ifdef ENABLE_CHECKING
2389   if (TREE_CODE_LENGTH (code) != 1)
2390     abort ();
2391 #endif /* ENABLE_CHECKING */
2392
2393   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
2394
2395   memset (t, 0, sizeof (struct tree_common));
2396
2397   TREE_SET_CODE (t, code);
2398
2399   TREE_TYPE (t) = type;
2400 #ifdef USE_MAPPED_LOCATION
2401   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2402 #else
2403   SET_EXPR_LOCUS (t, NULL);
2404 #endif
2405   TREE_COMPLEXITY (t) = 0;
2406   TREE_OPERAND (t, 0) = node;
2407   TREE_BLOCK (t) = NULL_TREE;
2408   if (node && !TYPE_P (node) && first_rtl_op (code) != 0)
2409     {
2410       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2411       TREE_READONLY (t) = TREE_READONLY (node);
2412     }
2413
2414   if (TREE_CODE_CLASS (code) == 's')
2415     TREE_SIDE_EFFECTS (t) = 1;
2416   else switch (code)
2417     {
2418     case INIT_EXPR:
2419     case MODIFY_EXPR:
2420     case VA_ARG_EXPR:
2421     case PREDECREMENT_EXPR:
2422     case PREINCREMENT_EXPR:
2423     case POSTDECREMENT_EXPR:
2424     case POSTINCREMENT_EXPR:
2425       /* All of these have side-effects, no matter what their
2426          operands are.  */
2427       TREE_SIDE_EFFECTS (t) = 1;
2428       TREE_READONLY (t) = 0;
2429       break;
2430
2431     case INDIRECT_REF:
2432       /* Whether a dereference is readonly has nothing to do with whether
2433          its operand is readonly.  */
2434       TREE_READONLY (t) = 0;
2435       break;
2436
2437     case ADDR_EXPR:
2438       if (node)
2439         recompute_tree_invarant_for_addr_expr (t);
2440       break;
2441
2442     default:
2443       if (TREE_CODE_CLASS (code) == '1' && node && !TYPE_P (node)
2444           && TREE_CONSTANT (node))
2445         TREE_CONSTANT (t) = 1;
2446       if (TREE_CODE_CLASS (code) == '1' && node && TREE_INVARIANT (node))
2447         TREE_INVARIANT (t) = 1;
2448       if (TREE_CODE_CLASS (code) == 'r' && node && TREE_THIS_VOLATILE (node))
2449         TREE_THIS_VOLATILE (t) = 1;
2450       break;
2451     }
2452
2453   return t;
2454 }
2455
2456 #define PROCESS_ARG(N)                  \
2457   do {                                  \
2458     TREE_OPERAND (t, N) = arg##N;       \
2459     if (arg##N &&!TYPE_P (arg##N) && fro > N) \
2460       {                                 \
2461         if (TREE_SIDE_EFFECTS (arg##N)) \
2462           side_effects = 1;             \
2463         if (!TREE_READONLY (arg##N))    \
2464           read_only = 0;                \
2465         if (!TREE_CONSTANT (arg##N))    \
2466           constant = 0;                 \
2467         if (!TREE_INVARIANT (arg##N))   \
2468           invariant = 0;                \
2469       }                                 \
2470   } while (0)
2471
2472 tree
2473 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2474 {
2475   bool constant, read_only, side_effects, invariant;
2476   tree t;
2477   int fro;
2478
2479 #ifdef ENABLE_CHECKING
2480   if (TREE_CODE_LENGTH (code) != 2)
2481     abort ();
2482 #endif
2483
2484   t = make_node_stat (code PASS_MEM_STAT);
2485   TREE_TYPE (t) = tt;
2486
2487   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2488      result based on those same flags for the arguments.  But if the
2489      arguments aren't really even `tree' expressions, we shouldn't be trying
2490      to do this.  */
2491   fro = first_rtl_op (code);
2492
2493   /* Expressions without side effects may be constant if their
2494      arguments are as well.  */
2495   constant = (TREE_CODE_CLASS (code) == '<'
2496               || TREE_CODE_CLASS (code) == '2');
2497   read_only = 1;
2498   side_effects = TREE_SIDE_EFFECTS (t);
2499   invariant = constant;
2500
2501   PROCESS_ARG(0);
2502   PROCESS_ARG(1);
2503
2504   TREE_READONLY (t) = read_only;
2505   TREE_CONSTANT (t) = constant;
2506   TREE_INVARIANT (t) = invariant;
2507   TREE_SIDE_EFFECTS (t) = side_effects;
2508   TREE_THIS_VOLATILE (t)
2509     = TREE_CODE_CLASS (code) == 'r' && arg0 && TREE_THIS_VOLATILE (arg0);
2510
2511   return t;
2512 }
2513
2514 tree
2515 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2516              tree arg2 MEM_STAT_DECL)
2517 {
2518   bool constant, read_only, side_effects, invariant;
2519   tree t;
2520   int fro;
2521
2522 #ifdef ENABLE_CHECKING
2523   if (TREE_CODE_LENGTH (code) != 3)
2524     abort ();
2525 #endif
2526
2527   t = make_node_stat (code PASS_MEM_STAT);
2528   TREE_TYPE (t) = tt;
2529
2530   fro = first_rtl_op (code);
2531
2532   side_effects = TREE_SIDE_EFFECTS (t);
2533
2534   PROCESS_ARG(0);
2535   PROCESS_ARG(1);
2536   PROCESS_ARG(2);
2537
2538   if (code == CALL_EXPR && !side_effects)
2539     {
2540       tree node;
2541       int i;
2542
2543       /* Calls have side-effects, except those to const or
2544          pure functions.  */
2545       i = call_expr_flags (t);
2546       if (!(i & (ECF_CONST | ECF_PURE)))
2547         side_effects = 1;
2548
2549       /* And even those have side-effects if their arguments do.  */
2550       else for (node = arg1; node; node = TREE_CHAIN (node))
2551         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2552           {
2553             side_effects = 1;
2554             break;
2555           }
2556     }
2557
2558   TREE_SIDE_EFFECTS (t) = side_effects;
2559   TREE_THIS_VOLATILE (t)
2560     = TREE_CODE_CLASS (code) == 'r' && arg0 && TREE_THIS_VOLATILE (arg0);
2561
2562   return t;
2563 }
2564
2565 tree
2566 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2567              tree arg2, tree arg3 MEM_STAT_DECL)
2568 {
2569   bool constant, read_only, side_effects, invariant;
2570   tree t;
2571   int fro;
2572
2573 #ifdef ENABLE_CHECKING
2574   if (TREE_CODE_LENGTH (code) != 4)
2575     abort ();
2576 #endif
2577
2578   t = make_node_stat (code PASS_MEM_STAT);
2579   TREE_TYPE (t) = tt;
2580
2581   fro = first_rtl_op (code);
2582
2583   side_effects = TREE_SIDE_EFFECTS (t);
2584
2585   PROCESS_ARG(0);
2586   PROCESS_ARG(1);
2587   PROCESS_ARG(2);
2588   PROCESS_ARG(3);
2589
2590   TREE_SIDE_EFFECTS (t) = side_effects;
2591   TREE_THIS_VOLATILE (t)
2592     = TREE_CODE_CLASS (code) == 'r' && arg0 && TREE_THIS_VOLATILE (arg0);
2593
2594   return t;
2595 }
2596
2597 /* Backup definition for non-gcc build compilers.  */
2598
2599 tree
2600 (build) (enum tree_code code, tree tt, ...)
2601 {
2602   tree t, arg0, arg1, arg2, arg3;
2603   int length = TREE_CODE_LENGTH (code);
2604   va_list p;
2605
2606   va_start (p, tt);
2607   switch (length)
2608     {
2609     case 0:
2610       t = build0 (code, tt);
2611       break;
2612     case 1:
2613       arg0 = va_arg (p, tree);
2614       t = build1 (code, tt, arg0);
2615       break;
2616     case 2:
2617       arg0 = va_arg (p, tree);
2618       arg1 = va_arg (p, tree);
2619       t = build2 (code, tt, arg0, arg1);
2620       break;
2621     case 3:
2622       arg0 = va_arg (p, tree);
2623       arg1 = va_arg (p, tree);
2624       arg2 = va_arg (p, tree);
2625       t = build3 (code, tt, arg0, arg1, arg2);
2626       break;
2627     case 4:
2628       arg0 = va_arg (p, tree);
2629       arg1 = va_arg (p, tree);
2630       arg2 = va_arg (p, tree);
2631       arg3 = va_arg (p, tree);
2632       t = build4 (code, tt, arg0, arg1, arg2, arg3);
2633       break;
2634     default:
2635       abort ();
2636     }
2637   va_end (p);
2638
2639   return t;
2640 }
2641
2642 /* Similar except don't specify the TREE_TYPE
2643    and leave the TREE_SIDE_EFFECTS as 0.
2644    It is permissible for arguments to be null,
2645    or even garbage if their values do not matter.  */
2646
2647 tree
2648 build_nt (enum tree_code code, ...)
2649 {
2650   tree t;
2651   int length;
2652   int i;
2653   va_list p;
2654
2655   va_start (p, code);
2656
2657   t = make_node (code);
2658   length = TREE_CODE_LENGTH (code);
2659
2660   for (i = 0; i < length; i++)
2661     TREE_OPERAND (t, i) = va_arg (p, tree);
2662
2663   va_end (p);
2664   return t;
2665 }
2666 \f
2667 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2668    We do NOT enter this node in any sort of symbol table.
2669
2670    layout_decl is used to set up the decl's storage layout.
2671    Other slots are initialized to 0 or null pointers.  */
2672
2673 tree
2674 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
2675 {
2676   tree t;
2677
2678   t = make_node_stat (code PASS_MEM_STAT);
2679
2680 /*  if (type == error_mark_node)
2681     type = integer_type_node; */
2682 /* That is not done, deliberately, so that having error_mark_node
2683    as the type can suppress useless errors in the use of this variable.  */
2684
2685   DECL_NAME (t) = name;
2686   TREE_TYPE (t) = type;
2687
2688   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2689     layout_decl (t, 0);
2690   else if (code == FUNCTION_DECL)
2691     DECL_MODE (t) = FUNCTION_MODE;
2692
2693   return t;
2694 }
2695 \f
2696 /* BLOCK nodes are used to represent the structure of binding contours
2697    and declarations, once those contours have been exited and their contents
2698    compiled.  This information is used for outputting debugging info.  */
2699
2700 tree
2701 build_block (tree vars, tree tags ATTRIBUTE_UNUSED, tree subblocks,
2702              tree supercontext, tree chain)
2703 {
2704   tree block = make_node (BLOCK);
2705
2706   BLOCK_VARS (block) = vars;
2707   BLOCK_SUBBLOCKS (block) = subblocks;
2708   BLOCK_SUPERCONTEXT (block) = supercontext;
2709   BLOCK_CHAIN (block) = chain;
2710   return block;
2711 }
2712
2713 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
2714 /* ??? gengtype doesn't handle conditionals */
2715 static GTY(()) tree last_annotated_node;
2716 #endif
2717
2718 #ifdef USE_MAPPED_LOCATION
2719
2720 expanded_location
2721 expand_location (source_location loc)
2722 {
2723   expanded_location xloc;
2724   if (loc == 0) { xloc.file = NULL; xloc.line = 0; }
2725   else
2726     {
2727       const struct line_map *map = linemap_lookup (&line_table, loc);
2728       xloc.file = map->to_file;
2729       xloc.line = SOURCE_LINE (map, loc);
2730     };
2731   return xloc;
2732 }
2733
2734 #else
2735
2736 /* Record the exact location where an expression or an identifier were
2737    encountered.  */
2738
2739 void
2740 annotate_with_file_line (tree node, const char *file, int line)
2741 {
2742   /* Roughly one percent of the calls to this function are to annotate
2743      a node with the same information already attached to that node!
2744      Just return instead of wasting memory.  */
2745   if (EXPR_LOCUS (node)
2746       && (EXPR_FILENAME (node) == file
2747           || ! strcmp (EXPR_FILENAME (node), file))
2748       && EXPR_LINENO (node) == line)
2749     {
2750       last_annotated_node = node;
2751       return;
2752     }
2753
2754   /* In heavily macroized code (such as GCC itself) this single
2755      entry cache can reduce the number of allocations by more
2756      than half.  */
2757   if (last_annotated_node
2758       && EXPR_LOCUS (last_annotated_node)
2759       && (EXPR_FILENAME (last_annotated_node) == file
2760           || ! strcmp (EXPR_FILENAME (last_annotated_node), file))
2761       && EXPR_LINENO (last_annotated_node) == line)
2762     {
2763       SET_EXPR_LOCUS (node, EXPR_LOCUS (last_annotated_node));
2764       return;
2765     }
2766
2767   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
2768   EXPR_LINENO (node) = line;
2769   EXPR_FILENAME (node) = file;
2770   last_annotated_node = node;
2771 }
2772
2773 void
2774 annotate_with_locus (tree node, location_t locus)
2775 {
2776   annotate_with_file_line (node, locus.file, locus.line);
2777 }
2778 #endif
2779 \f
2780 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2781    is ATTRIBUTE.  */
2782
2783 tree
2784 build_decl_attribute_variant (tree ddecl, tree attribute)
2785 {
2786   DECL_ATTRIBUTES (ddecl) = attribute;
2787   return ddecl;
2788 }
2789
2790 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2791    is ATTRIBUTE.
2792
2793    Record such modified types already made so we don't make duplicates.  */
2794
2795 tree
2796 build_type_attribute_variant (tree ttype, tree attribute)
2797 {
2798   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2799     {
2800       hashval_t hashcode = 0;
2801       tree ntype;
2802       enum tree_code code = TREE_CODE (ttype);
2803
2804       ntype = copy_node (ttype);
2805
2806       TYPE_POINTER_TO (ntype) = 0;
2807       TYPE_REFERENCE_TO (ntype) = 0;
2808       TYPE_ATTRIBUTES (ntype) = attribute;
2809
2810       /* Create a new main variant of TYPE.  */
2811       TYPE_MAIN_VARIANT (ntype) = ntype;
2812       TYPE_NEXT_VARIANT (ntype) = 0;
2813       set_type_quals (ntype, TYPE_UNQUALIFIED);
2814
2815       hashcode = iterative_hash_object (code, hashcode);
2816       if (TREE_TYPE (ntype))
2817         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
2818                                           hashcode);
2819       hashcode = attribute_hash_list (attribute, hashcode);
2820
2821       switch (TREE_CODE (ntype))
2822         {
2823         case FUNCTION_TYPE:
2824           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
2825           break;
2826         case ARRAY_TYPE:
2827           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
2828                                             hashcode);
2829           break;
2830         case INTEGER_TYPE:
2831           hashcode = iterative_hash_object
2832             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
2833           hashcode = iterative_hash_object
2834             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
2835           break;
2836         case REAL_TYPE:
2837           {
2838             unsigned int precision = TYPE_PRECISION (ntype);
2839             hashcode = iterative_hash_object (precision, hashcode);
2840           }
2841           break;
2842         default:
2843           break;
2844         }
2845
2846       ntype = type_hash_canon (hashcode, ntype);
2847       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
2848     }
2849
2850   return ttype;
2851 }
2852
2853 /* Return nonzero if IDENT is a valid name for attribute ATTR,
2854    or zero if not.
2855
2856    We try both `text' and `__text__', ATTR may be either one.  */
2857 /* ??? It might be a reasonable simplification to require ATTR to be only
2858    `text'.  One might then also require attribute lists to be stored in
2859    their canonicalized form.  */
2860
2861 int
2862 is_attribute_p (const char *attr, tree ident)
2863 {
2864   int ident_len, attr_len;
2865   const char *p;
2866
2867   if (TREE_CODE (ident) != IDENTIFIER_NODE)
2868     return 0;
2869
2870   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
2871     return 1;
2872
2873   p = IDENTIFIER_POINTER (ident);
2874   ident_len = strlen (p);
2875   attr_len = strlen (attr);
2876
2877   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
2878   if (attr[0] == '_')
2879     {
2880       if (attr[1] != '_'
2881           || attr[attr_len - 2] != '_'
2882           || attr[attr_len - 1] != '_')
2883         abort ();
2884       if (ident_len == attr_len - 4
2885           && strncmp (attr + 2, p, attr_len - 4) == 0)
2886         return 1;
2887     }
2888   else
2889     {
2890       if (ident_len == attr_len + 4
2891           && p[0] == '_' && p[1] == '_'
2892           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
2893           && strncmp (attr, p + 2, attr_len) == 0)
2894         return 1;
2895     }
2896
2897   return 0;
2898 }
2899
2900 /* Given an attribute name and a list of attributes, return a pointer to the
2901    attribute's list element if the attribute is part of the list, or NULL_TREE
2902    if not found.  If the attribute appears more than once, this only
2903    returns the first occurrence; the TREE_CHAIN of the return value should
2904    be passed back in if further occurrences are wanted.  */
2905
2906 tree
2907 lookup_attribute (const char *attr_name, tree list)
2908 {
2909   tree l;
2910
2911   for (l = list; l; l = TREE_CHAIN (l))
2912     {
2913       if (TREE_CODE (TREE_PURPOSE (l)) != IDENTIFIER_NODE)
2914         abort ();
2915       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
2916         return l;
2917     }
2918
2919   return NULL_TREE;
2920 }
2921
2922 /* Return an attribute list that is the union of a1 and a2.  */
2923
2924 tree
2925 merge_attributes (tree a1, tree a2)
2926 {
2927   tree attributes;
2928
2929   /* Either one unset?  Take the set one.  */
2930
2931   if ((attributes = a1) == 0)
2932     attributes = a2;
2933
2934   /* One that completely contains the other?  Take it.  */
2935
2936   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
2937     {
2938       if (attribute_list_contained (a2, a1))
2939         attributes = a2;
2940       else
2941         {
2942           /* Pick the longest list, and hang on the other list.  */
2943
2944           if (list_length (a1) < list_length (a2))
2945             attributes = a2, a2 = a1;
2946
2947           for (; a2 != 0; a2 = TREE_CHAIN (a2))
2948             {
2949               tree a;
2950               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2951                                          attributes);
2952                    a != NULL_TREE;
2953                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2954                                          TREE_CHAIN (a)))
2955                 {
2956                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
2957                     break;
2958                 }
2959               if (a == NULL_TREE)
2960                 {
2961                   a1 = copy_node (a2);
2962                   TREE_CHAIN (a1) = attributes;
2963                   attributes = a1;
2964                 }
2965             }
2966         }
2967     }
2968   return attributes;
2969 }
2970
2971 /* Given types T1 and T2, merge their attributes and return
2972   the result.  */
2973
2974 tree
2975 merge_type_attributes (tree t1, tree t2)
2976 {
2977   return merge_attributes (TYPE_ATTRIBUTES (t1),
2978                            TYPE_ATTRIBUTES (t2));
2979 }
2980
2981 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
2982    the result.  */
2983
2984 tree
2985 merge_decl_attributes (tree olddecl, tree newdecl)
2986 {
2987   return merge_attributes (DECL_ATTRIBUTES (olddecl),
2988                            DECL_ATTRIBUTES (newdecl));
2989 }
2990
2991 #ifdef TARGET_DLLIMPORT_DECL_ATTRIBUTES
2992
2993 /* Specialization of merge_decl_attributes for various Windows targets.
2994
2995    This handles the following situation:
2996
2997      __declspec (dllimport) int foo;
2998      int foo;
2999
3000    The second instance of `foo' nullifies the dllimport.  */
3001
3002 tree
3003 merge_dllimport_decl_attributes (tree old, tree new)
3004 {
3005   tree a;
3006   int delete_dllimport_p;
3007
3008   old = DECL_ATTRIBUTES (old);
3009   new = DECL_ATTRIBUTES (new);
3010
3011   /* What we need to do here is remove from `old' dllimport if it doesn't
3012      appear in `new'.  dllimport behaves like extern: if a declaration is
3013      marked dllimport and a definition appears later, then the object
3014      is not dllimport'd.  */
3015   if (lookup_attribute ("dllimport", old) != NULL_TREE
3016       && lookup_attribute ("dllimport", new) == NULL_TREE)
3017     delete_dllimport_p = 1;
3018   else
3019     delete_dllimport_p = 0;
3020
3021   a = merge_attributes (old, new);
3022
3023   if (delete_dllimport_p)
3024     {
3025       tree prev, t;
3026
3027       /* Scan the list for dllimport and delete it.  */
3028       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3029         {
3030           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
3031             {
3032               if (prev == NULL_TREE)
3033                 a = TREE_CHAIN (a);
3034               else
3035                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3036               break;
3037             }
3038         }
3039     }
3040
3041   return a;
3042 }
3043
3044 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3045 \f
3046 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3047    of the various TYPE_QUAL values.  */
3048
3049 static void
3050 set_type_quals (tree type, int type_quals)
3051 {
3052   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3053   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3054   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3055 }
3056
3057 /* Returns true iff cand is equivalent to base with type_quals.  */
3058
3059 bool
3060 check_qualified_type (tree cand, tree base, int type_quals)
3061 {
3062   return (TYPE_QUALS (cand) == type_quals
3063           && TYPE_NAME (cand) == TYPE_NAME (base)
3064           /* Apparently this is needed for Objective-C.  */
3065           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3066           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3067                                    TYPE_ATTRIBUTES (base)));
3068 }
3069
3070 /* Return a version of the TYPE, qualified as indicated by the
3071    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3072    return NULL_TREE.  */
3073
3074 tree
3075 get_qualified_type (tree type, int type_quals)
3076 {
3077   tree t;
3078
3079   if (TYPE_QUALS (type) == type_quals)
3080     return type;
3081
3082   /* Search the chain of variants to see if there is already one there just
3083      like the one we need to have.  If so, use that existing one.  We must
3084      preserve the TYPE_NAME, since there is code that depends on this.  */
3085   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3086     if (check_qualified_type (t, type, type_quals))
3087       return t;
3088
3089   return NULL_TREE;
3090 }
3091
3092 /* Like get_qualified_type, but creates the type if it does not
3093    exist.  This function never returns NULL_TREE.  */
3094
3095 tree
3096 build_qualified_type (tree type, int type_quals)
3097 {
3098   tree t;
3099
3100   /* See if we already have the appropriate qualified variant.  */
3101   t = get_qualified_type (type, type_quals);
3102
3103   /* If not, build it.  */
3104   if (!t)
3105     {
3106       t = build_type_copy (type);
3107       set_type_quals (t, type_quals);
3108     }
3109
3110   return t;
3111 }
3112
3113 /* Create a new variant of TYPE, equivalent but distinct.
3114    This is so the caller can modify it.  */
3115
3116 tree
3117 build_type_copy (tree type)
3118 {
3119   tree t, m = TYPE_MAIN_VARIANT (type);
3120
3121   t = copy_node (type);
3122
3123   TYPE_POINTER_TO (t) = 0;
3124   TYPE_REFERENCE_TO (t) = 0;
3125
3126   /* Add this type to the chain of variants of TYPE.  */
3127   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3128   TYPE_NEXT_VARIANT (m) = t;
3129
3130   return t;
3131 }
3132 \f
3133 /* Hashing of types so that we don't make duplicates.
3134    The entry point is `type_hash_canon'.  */
3135
3136 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3137    with types in the TREE_VALUE slots), by adding the hash codes
3138    of the individual types.  */
3139
3140 unsigned int
3141 type_hash_list (tree list, hashval_t hashcode)
3142 {
3143   tree tail;
3144
3145   for (tail = list; tail; tail = TREE_CHAIN (tail))
3146     if (TREE_VALUE (tail) != error_mark_node)
3147       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3148                                         hashcode);
3149
3150   return hashcode;
3151 }
3152
3153 /* These are the Hashtable callback functions.  */
3154
3155 /* Returns true iff the types are equivalent.  */
3156
3157 static int
3158 type_hash_eq (const void *va, const void *vb)
3159 {
3160   const struct type_hash *a = va, *b = vb;
3161
3162   /* First test the things that are the same for all types.  */
3163   if (a->hash != b->hash
3164       || TREE_CODE (a->type) != TREE_CODE (b->type)
3165       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
3166       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3167                                  TYPE_ATTRIBUTES (b->type))
3168       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
3169       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
3170     return 0;
3171
3172   switch (TREE_CODE (a->type))
3173     {
3174     case VOID_TYPE:
3175     case COMPLEX_TYPE:
3176     case VECTOR_TYPE:
3177     case POINTER_TYPE:
3178     case REFERENCE_TYPE:
3179       return 1;
3180
3181     case ENUMERAL_TYPE:
3182       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
3183           && !(TYPE_VALUES (a->type)
3184                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
3185                && TYPE_VALUES (b->type)
3186                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
3187                && type_list_equal (TYPE_VALUES (a->type),
3188                                    TYPE_VALUES (b->type))))
3189         return 0;
3190
3191       /* ... fall through ... */
3192
3193     case INTEGER_TYPE:
3194     case REAL_TYPE:
3195     case BOOLEAN_TYPE:
3196     case CHAR_TYPE:
3197       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3198                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3199                                       TYPE_MAX_VALUE (b->type)))
3200               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3201                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3202                                          TYPE_MIN_VALUE (b->type))));
3203
3204     case OFFSET_TYPE:
3205       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
3206
3207     case METHOD_TYPE:
3208       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
3209               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3210                   || (TYPE_ARG_TYPES (a->type)
3211                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3212                       && TYPE_ARG_TYPES (b->type)
3213                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3214                       && type_list_equal (TYPE_ARG_TYPES (a->type),
3215                                           TYPE_ARG_TYPES (b->type)))));
3216
3217     case ARRAY_TYPE:
3218     case SET_TYPE:
3219       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
3220
3221     case RECORD_TYPE:
3222     case UNION_TYPE:
3223     case QUAL_UNION_TYPE:
3224       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
3225               || (TYPE_FIELDS (a->type)
3226                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
3227                   && TYPE_FIELDS (b->type)
3228                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
3229                   && type_list_equal (TYPE_FIELDS (a->type),
3230                                       TYPE_FIELDS (b->type))));
3231
3232     case FUNCTION_TYPE:
3233       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3234               || (TYPE_ARG_TYPES (a->type)
3235                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3236                   && TYPE_ARG_TYPES (b->type)
3237                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3238                   && type_list_equal (TYPE_ARG_TYPES (a->type),
3239                                       TYPE_ARG_TYPES (b->type))));
3240
3241     default:
3242       return 0;
3243     }
3244 }
3245
3246 /* Return the cached hash value.  */
3247
3248 static hashval_t
3249 type_hash_hash (const void *item)
3250 {
3251   return ((const struct type_hash *) item)->hash;
3252 }
3253
3254 /* Look in the type hash table for a type isomorphic to TYPE.
3255    If one is found, return it.  Otherwise return 0.  */
3256
3257 tree
3258 type_hash_lookup (hashval_t hashcode, tree type)
3259 {
3260   struct type_hash *h, in;
3261
3262   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3263      must call that routine before comparing TYPE_ALIGNs.  */
3264   layout_type (type);
3265
3266   in.hash = hashcode;
3267   in.type = type;
3268
3269   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3270   if (h)
3271     return h->type;
3272   return NULL_TREE;
3273 }
3274
3275 /* Add an entry to the type-hash-table
3276    for a type TYPE whose hash code is HASHCODE.  */
3277
3278 void
3279 type_hash_add (hashval_t hashcode, tree type)
3280 {
3281   struct type_hash *h;
3282   void **loc;
3283
3284   h = ggc_alloc (sizeof (struct type_hash));
3285   h->hash = hashcode;
3286   h->type = type;
3287   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3288   *(struct type_hash **) loc = h;
3289 }
3290
3291 /* Given TYPE, and HASHCODE its hash code, return the canonical
3292    object for an identical type if one already exists.
3293    Otherwise, return TYPE, and record it as the canonical object.
3294
3295    To use this function, first create a type of the sort you want.
3296    Then compute its hash code from the fields of the type that
3297    make it different from other similar types.
3298    Then call this function and use the value.  */
3299
3300 tree
3301 type_hash_canon (unsigned int hashcode, tree type)
3302 {
3303   tree t1;
3304
3305   /* The hash table only contains main variants, so ensure that's what we're
3306      being passed.  */
3307   if (TYPE_MAIN_VARIANT (type) != type)
3308     abort ();
3309
3310   if (!lang_hooks.types.hash_types)
3311     return type;
3312
3313   /* See if the type is in the hash table already.  If so, return it.
3314      Otherwise, add the type.  */
3315   t1 = type_hash_lookup (hashcode, type);
3316   if (t1 != 0)
3317     {
3318 #ifdef GATHER_STATISTICS
3319       tree_node_counts[(int) t_kind]--;
3320       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3321 #endif
3322       return t1;
3323     }
3324   else
3325     {
3326       type_hash_add (hashcode, type);
3327       return type;
3328     }
3329 }
3330
3331 /* See if the data pointed to by the type hash table is marked.  We consider
3332    it marked if the type is marked or if a debug type number or symbol
3333    table entry has been made for the type.  This reduces the amount of
3334    debugging output and eliminates that dependency of the debug output on
3335    the number of garbage collections.  */
3336
3337 static int
3338 type_hash_marked_p (const void *p)
3339 {
3340   tree type = ((struct type_hash *) p)->type;
3341
3342   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3343 }
3344
3345 static void
3346 print_type_hash_statistics (void)
3347 {
3348   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3349            (long) htab_size (type_hash_table),
3350            (long) htab_elements (type_hash_table),
3351            htab_collisions (type_hash_table));
3352 }
3353
3354 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3355    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3356    by adding the hash codes of the individual attributes.  */
3357
3358 unsigned int
3359 attribute_hash_list (tree list, hashval_t hashcode)
3360 {
3361   tree tail;
3362
3363   for (tail = list; tail; tail = TREE_CHAIN (tail))
3364     /* ??? Do we want to add in TREE_VALUE too? */
3365     hashcode = iterative_hash_object
3366       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
3367   return hashcode;
3368 }
3369
3370 /* Given two lists of attributes, return true if list l2 is
3371    equivalent to l1.  */
3372
3373 int
3374 attribute_list_equal (tree l1, tree l2)
3375 {
3376   return attribute_list_contained (l1, l2)
3377          && attribute_list_contained (l2, l1);
3378 }
3379
3380 /* Given two lists of attributes, return true if list L2 is
3381    completely contained within L1.  */
3382 /* ??? This would be faster if attribute names were stored in a canonicalized
3383    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3384    must be used to show these elements are equivalent (which they are).  */
3385 /* ??? It's not clear that attributes with arguments will always be handled
3386    correctly.  */
3387
3388 int
3389 attribute_list_contained (tree l1, tree l2)
3390 {
3391   tree t1, t2;
3392
3393   /* First check the obvious, maybe the lists are identical.  */
3394   if (l1 == l2)
3395     return 1;
3396
3397   /* Maybe the lists are similar.  */
3398   for (t1 = l1, t2 = l2;
3399        t1 != 0 && t2 != 0
3400         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3401         && TREE_VALUE (t1) == TREE_VALUE (t2);
3402        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3403
3404   /* Maybe the lists are equal.  */
3405   if (t1 == 0 && t2 == 0)
3406     return 1;
3407
3408   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3409     {
3410       tree attr;
3411       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3412            attr != NULL_TREE;
3413            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3414                                     TREE_CHAIN (attr)))
3415         {
3416           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3417             break;
3418         }
3419
3420       if (attr == 0)
3421         return 0;
3422
3423       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3424         return 0;
3425     }
3426
3427   return 1;
3428 }
3429
3430 /* Given two lists of types
3431    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3432    return 1 if the lists contain the same types in the same order.
3433    Also, the TREE_PURPOSEs must match.  */
3434
3435 int
3436 type_list_equal (tree l1, tree l2)
3437 {
3438   tree t1, t2;
3439
3440   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3441     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3442         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3443             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3444                   && (TREE_TYPE (TREE_PURPOSE (t1))
3445                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3446       return 0;
3447
3448   return t1 == t2;
3449 }
3450
3451 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3452    given by TYPE.  If the argument list accepts variable arguments,
3453    then this function counts only the ordinary arguments.  */
3454
3455 int
3456 type_num_arguments (tree type)
3457 {
3458   int i = 0;
3459   tree t;
3460
3461   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3462     /* If the function does not take a variable number of arguments,
3463        the last element in the list will have type `void'.  */
3464     if (VOID_TYPE_P (TREE_VALUE (t)))
3465       break;
3466     else
3467       ++i;
3468
3469   return i;
3470 }
3471
3472 /* Nonzero if integer constants T1 and T2
3473    represent the same constant value.  */
3474
3475 int
3476 tree_int_cst_equal (tree t1, tree t2)
3477 {
3478   if (t1 == t2)
3479     return 1;
3480
3481   if (t1 == 0 || t2 == 0)
3482     return 0;
3483
3484   if (TREE_CODE (t1) == INTEGER_CST
3485       && TREE_CODE (t2) == INTEGER_CST
3486       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3487       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3488     return 1;
3489
3490   return 0;
3491 }
3492
3493 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3494    The precise way of comparison depends on their data type.  */
3495
3496 int
3497 tree_int_cst_lt (tree t1, tree t2)
3498 {
3499   if (t1 == t2)
3500     return 0;
3501
3502   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
3503     {
3504       int t1_sgn = tree_int_cst_sgn (t1);
3505       int t2_sgn = tree_int_cst_sgn (t2);
3506
3507       if (t1_sgn < t2_sgn)
3508         return 1;
3509       else if (t1_sgn > t2_sgn)
3510         return 0;
3511       /* Otherwise, both are non-negative, so we compare them as
3512          unsigned just in case one of them would overflow a signed
3513          type.  */
3514     }
3515   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
3516     return INT_CST_LT (t1, t2);
3517
3518   return INT_CST_LT_UNSIGNED (t1, t2);
3519 }
3520
3521 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3522
3523 int
3524 tree_int_cst_compare (tree t1, tree t2)
3525 {
3526   if (tree_int_cst_lt (t1, t2))
3527     return -1;
3528   else if (tree_int_cst_lt (t2, t1))
3529     return 1;
3530   else
3531     return 0;
3532 }
3533
3534 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
3535    the host.  If POS is zero, the value can be represented in a single
3536    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
3537    be represented in a single unsigned HOST_WIDE_INT.  */
3538
3539 int
3540 host_integerp (tree t, int pos)
3541 {
3542   return (TREE_CODE (t) == INTEGER_CST
3543           && ! TREE_OVERFLOW (t)
3544           && ((TREE_INT_CST_HIGH (t) == 0
3545                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3546               || (! pos && TREE_INT_CST_HIGH (t) == -1
3547                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
3548                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
3549               || (pos && TREE_INT_CST_HIGH (t) == 0)));
3550 }
3551
3552 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3553    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3554    be positive.  Abort if we cannot satisfy the above conditions.  */
3555
3556 HOST_WIDE_INT
3557 tree_low_cst (tree t, int pos)
3558 {
3559   if (host_integerp (t, pos))
3560     return TREE_INT_CST_LOW (t);
3561   else
3562     abort ();
3563 }
3564
3565 /* Return the most significant bit of the integer constant T.  */
3566
3567 int
3568 tree_int_cst_msb (tree t)
3569 {
3570   int prec;
3571   HOST_WIDE_INT h;
3572   unsigned HOST_WIDE_INT l;
3573
3574   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3575      actual bits, not the (arbitrary) range of the type.  */
3576   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3577   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3578                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3579   return (l & 1) == 1;
3580 }
3581
3582 /* Return an indication of the sign of the integer constant T.
3583    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3584    Note that -1 will never be returned it T's type is unsigned.  */
3585
3586 int
3587 tree_int_cst_sgn (tree t)
3588 {
3589   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3590     return 0;
3591   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
3592     return 1;
3593   else if (TREE_INT_CST_HIGH (t) < 0)
3594     return -1;
3595   else
3596     return 1;
3597 }
3598
3599 /* Compare two constructor-element-type constants.  Return 1 if the lists
3600    are known to be equal; otherwise return 0.  */
3601
3602 int
3603 simple_cst_list_equal (tree l1, tree l2)
3604 {
3605   while (l1 != NULL_TREE && l2 != NULL_TREE)
3606     {
3607       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3608         return 0;
3609
3610       l1 = TREE_CHAIN (l1);
3611       l2 = TREE_CHAIN (l2);
3612     }
3613
3614   return l1 == l2;
3615 }
3616
3617 /* Return truthvalue of whether T1 is the same tree structure as T2.
3618    Return 1 if they are the same.
3619    Return 0 if they are understandably different.
3620    Return -1 if either contains tree structure not understood by
3621    this function.  */
3622
3623 int
3624 simple_cst_equal (tree t1, tree t2)
3625 {
3626   enum tree_code code1, code2;
3627   int cmp;
3628   int i;
3629
3630   if (t1 == t2)
3631     return 1;
3632   if (t1 == 0 || t2 == 0)
3633     return 0;
3634
3635   code1 = TREE_CODE (t1);
3636   code2 = TREE_CODE (t2);
3637
3638   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3639     {
3640       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3641           || code2 == NON_LVALUE_EXPR)
3642         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3643       else
3644         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3645     }
3646
3647   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3648            || code2 == NON_LVALUE_EXPR)
3649     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3650
3651   if (code1 != code2)
3652     return 0;
3653
3654   switch (code1)
3655     {
3656     case INTEGER_CST:
3657       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3658               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3659
3660     case REAL_CST:
3661       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3662
3663     case STRING_CST:
3664       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3665               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3666                          TREE_STRING_LENGTH (t1)));
3667
3668     case CONSTRUCTOR:
3669       return simple_cst_list_equal (CONSTRUCTOR_ELTS (t1),
3670                                     CONSTRUCTOR_ELTS (t2));
3671
3672     case SAVE_EXPR:
3673       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3674
3675     case CALL_EXPR:
3676       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3677       if (cmp <= 0)
3678         return cmp;
3679       return
3680         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3681
3682     case TARGET_EXPR:
3683       /* Special case: if either target is an unallocated VAR_DECL,
3684          it means that it's going to be unified with whatever the
3685          TARGET_EXPR is really supposed to initialize, so treat it
3686          as being equivalent to anything.  */
3687       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3688            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3689            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3690           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3691               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3692               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3693         cmp = 1;
3694       else
3695         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3696
3697       if (cmp <= 0)
3698         return cmp;
3699
3700       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3701
3702     case WITH_CLEANUP_EXPR:
3703       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3704       if (cmp <= 0)
3705         return cmp;
3706
3707       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3708
3709     case COMPONENT_REF:
3710       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3711         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3712
3713       return 0;
3714
3715     case VAR_DECL:
3716     case PARM_DECL:
3717     case CONST_DECL:
3718     case FUNCTION_DECL:
3719       return 0;
3720
3721     default:
3722       break;
3723     }
3724
3725   /* This general rule works for most tree codes.  All exceptions should be
3726      handled above.  If this is a language-specific tree code, we can't
3727      trust what might be in the operand, so say we don't know
3728      the situation.  */
3729   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3730     return -1;
3731
3732   switch (TREE_CODE_CLASS (code1))
3733     {
3734     case '1':
3735     case '2':
3736     case '<':
3737     case 'e':
3738     case 'r':
3739     case 's':
3740       cmp = 1;
3741       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3742         {
3743           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3744           if (cmp <= 0)
3745             return cmp;
3746         }
3747
3748       return cmp;
3749
3750     default:
3751       return -1;
3752     }