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 RTL_EXPR:
 338         case PREDECREMENT_EXPR:
 339         case PREINCREMENT_EXPR:
 340         case POSTDECREMENT_EXPR:
 341         case POSTINCREMENT_EXPR:
 342           /* All of these have side-effects, no matter what their
 343              operands are.  */
 344           TREE_SIDE_EFFECTS (t) = 1;
 345           break;
 346
 347         default:
 348           break;
 349         }
 350       break;
 351     }
 352
 353   return t;
 354 }
 355 \f
 356 /* Return a new node with the same contents as NODE except that its
 357    TREE_CHAIN is zero and it has a fresh uid.  */
 358
 359 tree
 360 copy_node_stat (tree node MEM_STAT_DECL)
 361 {
 362   tree t;
 363   enum tree_code code = TREE_CODE (node);
 364   size_t length;
 365
 366 #ifdef ENABLE_CHECKING
 367   if (code == STATEMENT_LIST)
 368     abort ();
 369 #endif
 370
 371   length = tree_size (node);
 372   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
 373   memcpy (t, node, length);
 374
 375   TREE_CHAIN (t) = 0;
 376   TREE_ASM_WRITTEN (t) = 0;
 377   TREE_VISITED (t) = 0;
 378   t->common.ann = 0;
 379
 380   if (TREE_CODE_CLASS (code) == 'd')
 381     DECL_UID (t) = next_decl_uid++;
 382   else if (TREE_CODE_CLASS (code) == 't')
 383     {
 384       TYPE_UID (t) = next_type_uid++;
 385       /* The following is so that the debug code for
 386          the copy is different from the original type.
 387          The two statements usually duplicate each other
 388          (because they clear fields of the same union),
 389          but the optimizer should catch that.  */
 390       TYPE_SYMTAB_POINTER (t) = 0;
 391       TYPE_SYMTAB_ADDRESS (t) = 0;
 392     }
 393
 394   return t;
 395 }
 396
 397 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
 398    For example, this can copy a list made of TREE_LIST nodes.  */
 399
 400 tree
 401 copy_list (tree list)
 402 {
 403   tree head;
 404   tree prev, next;
 405
 406   if (list == 0)
 407     return 0;
 408
 409   head = prev = copy_node (list);
 410   next = TREE_CHAIN (list);
 411   while (next)
 412     {
 413       TREE_CHAIN (prev) = copy_node (next);
 414       prev = TREE_CHAIN (prev);
 415       next = TREE_CHAIN (next);
 416     }
 417   return head;
 418 }
 419
 420 \f
 421 /* Return a newly constructed INTEGER_CST node whose constant value
 422    is specified by the two ints LOW and HI.
 423    The TREE_TYPE is set to `int'.
 424
 425    This function should be used via the `build_int_2' macro.  */
 426
 427 tree
 428 build_int_2_wide (unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
 429 {
 430   tree t = make_node (INTEGER_CST);
 431
 432   TREE_INT_CST_LOW (t) = low;
 433   TREE_INT_CST_HIGH (t) = hi;
 434   TREE_TYPE (t) = integer_type_node;
 435   return t;
 436 }
 437
 438 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 439    are in a list pointed by VALS.  */
 440
 441 tree
 442 build_vector (tree type, tree vals)
 443 {
 444   tree v = make_node (VECTOR_CST);
 445   int over1 = 0, over2 = 0;
 446   tree link;
 447
 448   TREE_VECTOR_CST_ELTS (v) = vals;
 449   TREE_TYPE (v) = type;
 450
 451   /* Iterate through elements and check for overflow.  */
 452   for (link = vals; link; link = TREE_CHAIN (link))
 453     {
 454       tree value = TREE_VALUE (link);
 455
 456       over1 |= TREE_OVERFLOW (value);
 457       over2 |= TREE_CONSTANT_OVERFLOW (value);
 458     }
 459
 460   TREE_OVERFLOW (v) = over1;
 461   TREE_CONSTANT_OVERFLOW (v) = over2;
 462
 463   return v;
 464 }
 465
 466 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
 467    are in a list pointed to by VALS.  */
 468 tree
 469 build_constructor (tree type, tree vals)
 470 {
 471   tree c = make_node (CONSTRUCTOR);
 472   TREE_TYPE (c) = type;
 473   CONSTRUCTOR_ELTS (c) = vals;
 474
 475   /* ??? May not be necessary.  Mirrors what build does.  */
 476   if (vals)
 477     {
 478       TREE_SIDE_EFFECTS (c) = TREE_SIDE_EFFECTS (vals);
 479       TREE_READONLY (c) = TREE_READONLY (vals);
 480       TREE_CONSTANT (c) = TREE_CONSTANT (vals);
 481       TREE_INVARIANT (c) = TREE_INVARIANT (vals);
 482     }
 483
 484   return c;
 485 }
 486
 487 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
 488
 489 tree
 490 build_real (tree type, REAL_VALUE_TYPE d)
 491 {
 492   tree v;
 493   REAL_VALUE_TYPE *dp;
 494   int overflow = 0;
 495
 496   /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
 497      Consider doing it via real_convert now.  */
 498
 499   v = make_node (REAL_CST);
 500   dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
 501   memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
 502
 503   TREE_TYPE (v) = type;
 504   TREE_REAL_CST_PTR (v) = dp;
 505   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
 506   return v;
 507 }
 508
 509 /* Return a new REAL_CST node whose type is TYPE
 510    and whose value is the integer value of the INTEGER_CST node I.  */
 511
 512 REAL_VALUE_TYPE
 513 real_value_from_int_cst (tree type, tree i)
 514 {
 515   REAL_VALUE_TYPE d;
 516
 517   /* Clear all bits of the real value type so that we can later do
 518      bitwise comparisons to see if two values are the same.  */
 519   memset (&d, 0, sizeof d);
 520
 521   real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
 522                      TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
 523                      TYPE_UNSIGNED (TREE_TYPE (i)));
 524   return d;
 525 }
 526
 527 /* Given a tree representing an integer constant I, return a tree
 528    representing the same value as a floating-point constant of type TYPE.  */
 529
 530 tree
 531 build_real_from_int_cst (tree type, tree i)
 532 {
 533   tree v;
 534   int overflow = TREE_OVERFLOW (i);
 535
 536   v = build_real (type, real_value_from_int_cst (type, i));
 537
 538   TREE_OVERFLOW (v) |= overflow;
 539   TREE_CONSTANT_OVERFLOW (v) |= overflow;
 540   return v;
 541 }
 542
 543 /* Return a newly constructed STRING_CST node whose value is
 544    the LEN characters at STR.
 545    The TREE_TYPE is not initialized.  */
 546
 547 tree
 548 build_string (int len, const char *str)
 549 {
 550   tree s = make_node (STRING_CST);
 551
 552   TREE_STRING_LENGTH (s) = len;
 553   TREE_STRING_POINTER (s) = ggc_alloc_string (str, len);
 554
 555   return s;
 556 }
 557
 558 /* Return a newly constructed COMPLEX_CST node whose value is
 559    specified by the real and imaginary parts REAL and IMAG.
 560    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
 561    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
 562
 563 tree
 564 build_complex (tree type, tree real, tree imag)
 565 {
 566   tree t = make_node (COMPLEX_CST);
 567
 568   TREE_REALPART (t) = real;
 569   TREE_IMAGPART (t) = imag;
 570   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
 571   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
 572   TREE_CONSTANT_OVERFLOW (t)
 573     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
 574   return t;
 575 }
 576
 577 /* Build a newly constructed TREE_VEC node of length LEN.  */
 578
 579 tree
 580 make_tree_vec_stat (int len MEM_STAT_DECL)
 581 {
 582   tree t;
 583   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
 584
 585 #ifdef GATHER_STATISTICS
 586   tree_node_counts[(int) vec_kind]++;
 587   tree_node_sizes[(int) vec_kind] += length;
 588 #endif
 589
 590   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
 591
 592   memset (t, 0, length);
 593
 594   TREE_SET_CODE (t, TREE_VEC);
 595   TREE_VEC_LENGTH (t) = len;
 596
 597   return t;
 598 }
 599 \f
 600 /* Return 1 if EXPR is the integer constant zero or a complex constant
 601    of zero.  */
 602
 603 int
 604 integer_zerop (tree expr)
 605 {
 606   STRIP_NOPS (expr);
 607
 608   return ((TREE_CODE (expr) == INTEGER_CST
 609            && ! TREE_CONSTANT_OVERFLOW (expr)
 610            && TREE_INT_CST_LOW (expr) == 0
 611            && TREE_INT_CST_HIGH (expr) == 0)
 612           || (TREE_CODE (expr) == COMPLEX_CST
 613               && integer_zerop (TREE_REALPART (expr))
 614               && integer_zerop (TREE_IMAGPART (expr))));
 615 }
 616
 617 /* Return 1 if EXPR is the integer constant one or the corresponding
 618    complex constant.  */
 619
 620 int
 621 integer_onep (tree expr)
 622 {
 623   STRIP_NOPS (expr);
 624
 625   return ((TREE_CODE (expr) == INTEGER_CST
 626            && ! TREE_CONSTANT_OVERFLOW (expr)
 627            && TREE_INT_CST_LOW (expr) == 1
 628            && TREE_INT_CST_HIGH (expr) == 0)
 629           || (TREE_CODE (expr) == COMPLEX_CST
 630               && integer_onep (TREE_REALPART (expr))
 631               && integer_zerop (TREE_IMAGPART (expr))));
 632 }
 633
 634 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
 635    it contains.  Likewise for the corresponding complex constant.  */
 636
 637 int
 638 integer_all_onesp (tree expr)
 639 {
 640   int prec;
 641   int uns;
 642
 643   STRIP_NOPS (expr);
 644
 645   if (TREE_CODE (expr) == COMPLEX_CST
 646       && integer_all_onesp (TREE_REALPART (expr))
 647       && integer_zerop (TREE_IMAGPART (expr)))
 648     return 1;
 649
 650   else if (TREE_CODE (expr) != INTEGER_CST
 651            || TREE_CONSTANT_OVERFLOW (expr))
 652     return 0;
 653
 654   uns = TYPE_UNSIGNED (TREE_TYPE (expr));
 655   if (!uns)
 656     return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
 657             && TREE_INT_CST_HIGH (expr) == -1);
 658
 659   /* Note that using TYPE_PRECISION here is wrong.  We care about the
 660      actual bits, not the (arbitrary) range of the type.  */
 661   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
 662   if (prec >= HOST_BITS_PER_WIDE_INT)
 663     {
 664       HOST_WIDE_INT high_value;
 665       int shift_amount;
 666
 667       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
 668
 669       if (shift_amount > HOST_BITS_PER_WIDE_INT)
 670         /* Can not handle precisions greater than twice the host int size.  */
 671         abort ();
 672       else if (shift_amount == HOST_BITS_PER_WIDE_INT)
 673         /* Shifting by the host word size is undefined according to the ANSI
 674            standard, so we must handle this as a special case.  */
 675         high_value = -1;
 676       else
 677         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
 678
 679       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
 680               && TREE_INT_CST_HIGH (expr) == high_value);
 681     }
 682   else
 683     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
 684 }
 685
 686 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
 687    one bit on).  */
 688
 689 int
 690 integer_pow2p (tree expr)
 691 {
 692   int prec;
 693   HOST_WIDE_INT high, low;
 694
 695   STRIP_NOPS (expr);
 696
 697   if (TREE_CODE (expr) == COMPLEX_CST
 698       && integer_pow2p (TREE_REALPART (expr))
 699       && integer_zerop (TREE_IMAGPART (expr)))
 700     return 1;
 701
 702   if (TREE_CODE (expr) != INTEGER_CST || TREE_CONSTANT_OVERFLOW (expr))
 703     return 0;
 704
 705   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
 706           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
 707   high = TREE_INT_CST_HIGH (expr);
 708   low = TREE_INT_CST_LOW (expr);
 709
 710   /* First clear all bits that are beyond the type's precision in case
 711      we've been sign extended.  */
 712
 713   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
 714     ;
 715   else if (prec > HOST_BITS_PER_WIDE_INT)
 716     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 717   else
 718     {
 719       high = 0;
 720       if (prec < HOST_BITS_PER_WIDE_INT)
 721         low &= ~((HOST_WIDE_INT) (-1) << prec);
 722     }
 723
 724   if (high == 0 && low == 0)
 725     return 0;
 726
 727   return ((high == 0 && (low & (low - 1)) == 0)
 728           || (low == 0 && (high & (high - 1)) == 0));
 729 }
 730
 731 /* Return 1 if EXPR is an integer constant other than zero or a
 732    complex constant other than zero.  */
 733
 734 int
 735 integer_nonzerop (tree expr)
 736 {
 737   STRIP_NOPS (expr);
 738
 739   return ((TREE_CODE (expr) == INTEGER_CST
 740            && ! TREE_CONSTANT_OVERFLOW (expr)
 741            && (TREE_INT_CST_LOW (expr) != 0
 742                || TREE_INT_CST_HIGH (expr) != 0))
 743           || (TREE_CODE (expr) == COMPLEX_CST
 744               && (integer_nonzerop (TREE_REALPART (expr))
 745                   || integer_nonzerop (TREE_IMAGPART (expr)))));
 746 }
 747
 748 /* Return the power of two represented by a tree node known to be a
 749    power of two.  */
 750
 751 int
 752 tree_log2 (tree expr)
 753 {
 754   int prec;
 755   HOST_WIDE_INT high, low;
 756
 757   STRIP_NOPS (expr);
 758
 759   if (TREE_CODE (expr) == COMPLEX_CST)
 760     return tree_log2 (TREE_REALPART (expr));
 761
 762   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
 763           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
 764
 765   high = TREE_INT_CST_HIGH (expr);
 766   low = TREE_INT_CST_LOW (expr);
 767
 768   /* First clear all bits that are beyond the type's precision in case
 769      we've been sign extended.  */
 770
 771   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
 772     ;
 773   else if (prec > HOST_BITS_PER_WIDE_INT)
 774     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 775   else
 776     {
 777       high = 0;
 778       if (prec < HOST_BITS_PER_WIDE_INT)
 779         low &= ~((HOST_WIDE_INT) (-1) << prec);
 780     }
 781
 782   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
 783           : exact_log2 (low));
 784 }
 785
 786 /* Similar, but return the largest integer Y such that 2 ** Y is less
 787    than or equal to EXPR.  */
 788
 789 int
 790 tree_floor_log2 (tree expr)
 791 {
 792   int prec;
 793   HOST_WIDE_INT high, low;
 794
 795   STRIP_NOPS (expr);
 796
 797   if (TREE_CODE (expr) == COMPLEX_CST)
 798     return tree_log2 (TREE_REALPART (expr));
 799
 800   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
 801           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
 802
 803   high = TREE_INT_CST_HIGH (expr);
 804   low = TREE_INT_CST_LOW (expr);
 805
 806   /* First clear all bits that are beyond the type's precision in case
 807      we've been sign extended.  Ignore if type's precision hasn't been set
 808      since what we are doing is setting it.  */
 809
 810   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
 811     ;
 812   else if (prec > HOST_BITS_PER_WIDE_INT)
 813     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
 814   else
 815     {
 816       high = 0;
 817       if (prec < HOST_BITS_PER_WIDE_INT)
 818         low &= ~((HOST_WIDE_INT) (-1) << prec);
 819     }
 820
 821   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
 822           : floor_log2 (low));
 823 }
 824
 825 /* Return 1 if EXPR is the real constant zero.  */
 826
 827 int
 828 real_zerop (tree expr)
 829 {
 830   STRIP_NOPS (expr);
 831
 832   return ((TREE_CODE (expr) == REAL_CST
 833            && ! TREE_CONSTANT_OVERFLOW (expr)
 834            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
 835           || (TREE_CODE (expr) == COMPLEX_CST
 836               && real_zerop (TREE_REALPART (expr))
 837               && real_zerop (TREE_IMAGPART (expr))));
 838 }
 839
 840 /* Return 1 if EXPR is the real constant one in real or complex form.  */
 841
 842 int
 843 real_onep (tree expr)
 844 {
 845   STRIP_NOPS (expr);
 846
 847   return ((TREE_CODE (expr) == REAL_CST
 848            && ! TREE_CONSTANT_OVERFLOW (expr)
 849            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
 850           || (TREE_CODE (expr) == COMPLEX_CST
 851               && real_onep (TREE_REALPART (expr))
 852               && real_zerop (TREE_IMAGPART (expr))));
 853 }
 854
 855 /* Return 1 if EXPR is the real constant two.  */
 856
 857 int
 858 real_twop (tree expr)
 859 {
 860   STRIP_NOPS (expr);
 861
 862   return ((TREE_CODE (expr) == REAL_CST
 863            && ! TREE_CONSTANT_OVERFLOW (expr)
 864            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
 865           || (TREE_CODE (expr) == COMPLEX_CST
 866               && real_twop (TREE_REALPART (expr))
 867               && real_zerop (TREE_IMAGPART (expr))));
 868 }
 869
 870 /* Return 1 if EXPR is the real constant minus one.  */
 871
 872 int
 873 real_minus_onep (tree expr)
 874 {
 875   STRIP_NOPS (expr);
 876
 877   return ((TREE_CODE (expr) == REAL_CST
 878            && ! TREE_CONSTANT_OVERFLOW (expr)
 879            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
 880           || (TREE_CODE (expr) == COMPLEX_CST
 881               && real_minus_onep (TREE_REALPART (expr))
 882               && real_zerop (TREE_IMAGPART (expr))));
 883 }
 884
 885 /* Nonzero if EXP is a constant or a cast of a constant.  */
 886
 887 int
 888 really_constant_p (tree exp)
 889 {
 890   /* This is not quite the same as STRIP_NOPS.  It does more.  */
 891   while (TREE_CODE (exp) == NOP_EXPR
 892          || TREE_CODE (exp) == CONVERT_EXPR
 893          || TREE_CODE (exp) == NON_LVALUE_EXPR)
 894     exp = TREE_OPERAND (exp, 0);
 895   return TREE_CONSTANT (exp);
 896 }
 897 \f
 898 /* Return first list element whose TREE_VALUE is ELEM.
 899    Return 0 if ELEM is not in LIST.  */
 900
 901 tree
 902 value_member (tree elem, tree list)
 903 {
 904   while (list)
 905     {
 906       if (elem == TREE_VALUE (list))
 907         return list;
 908       list = TREE_CHAIN (list);
 909     }
 910   return NULL_TREE;
 911 }
 912
 913 /* Return first list element whose TREE_PURPOSE is ELEM.
 914    Return 0 if ELEM is not in LIST.  */
 915
 916 tree
 917 purpose_member (tree elem, tree list)
 918 {
 919   while (list)
 920     {
 921       if (elem == TREE_PURPOSE (list))
 922         return list;
 923       list = TREE_CHAIN (list);
 924     }
 925   return NULL_TREE;
 926 }
 927
 928 /* Return first list element whose BINFO_TYPE is ELEM.
 929    Return 0 if ELEM is not in LIST.  */
 930
 931 tree
 932 binfo_member (tree elem, tree list)
 933 {
 934   while (list)
 935     {
 936       if (elem == BINFO_TYPE (list))
 937         return list;
 938       list = TREE_CHAIN (list);
 939     }
 940   return NULL_TREE;
 941 }
 942
 943 /* Return nonzero if ELEM is part of the chain CHAIN.  */
 944
 945 int
 946 chain_member (tree elem, tree chain)
 947 {
 948   while (chain)
 949     {
 950       if (elem == chain)
 951         return 1;
 952       chain = TREE_CHAIN (chain);
 953     }
 954
 955   return 0;
 956 }
 957
 958 /* Return the length of a chain of nodes chained through TREE_CHAIN.
 959    We expect a null pointer to mark the end of the chain.
 960    This is the Lisp primitive `length'.  */
 961
 962 int
 963 list_length (tree t)
 964 {
 965   tree p = t;
 966 #ifdef ENABLE_TREE_CHECKING
 967   tree q = t;
 968 #endif
 969   int len = 0;
 970
 971   while (p)
 972     {
 973       p = TREE_CHAIN (p);
 974 #ifdef ENABLE_TREE_CHECKING
 975       if (len % 2)
 976         q = TREE_CHAIN (q);
 977       if (p == q)
 978         abort ();
 979 #endif
 980       len++;
 981     }
 982
 983   return len;
 984 }
 985
 986 /* Returns the number of FIELD_DECLs in TYPE.  */
 987
 988 int
 989 fields_length (tree type)
 990 {
 991   tree t = TYPE_FIELDS (type);
 992   int count = 0;
 993
 994   for (; t; t = TREE_CHAIN (t))
 995     if (TREE_CODE (t) == FIELD_DECL)
 996       ++count;
 997
 998   return count;
 999 }
1000
1001 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1002    by modifying the last node in chain 1 to point to chain 2.
1003    This is the Lisp primitive `nconc'.  */
1004
1005 tree
1006 chainon (tree op1, tree op2)
1007 {
1008   tree t1;
1009
1010   if (!op1)
1011     return op2;
1012   if (!op2)
1013     return op1;
1014
1015   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1016     continue;
1017   TREE_CHAIN (t1) = op2;
1018
1019 #ifdef ENABLE_TREE_CHECKING
1020   {
1021     tree t2;
1022     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1023       if (t2 == t1)
1024         abort ();  /* Circularity created.  */
1025   }
1026 #endif
1027
1028   return op1;
1029 }
1030
1031 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1032
1033 tree
1034 tree_last (tree chain)
1035 {
1036   tree next;
1037   if (chain)
1038     while ((next = TREE_CHAIN (chain)))
1039       chain = next;
1040   return chain;
1041 }
1042
1043 /* Reverse the order of elements in the chain T,
1044    and return the new head of the chain (old last element).  */
1045
1046 tree
1047 nreverse (tree t)
1048 {
1049   tree prev = 0, decl, next;
1050   for (decl = t; decl; decl = next)
1051     {
1052       next = TREE_CHAIN (decl);
1053       TREE_CHAIN (decl) = prev;
1054       prev = decl;
1055     }
1056   return prev;
1057 }
1058 \f
1059 /* Return a newly created TREE_LIST node whose
1060    purpose and value fields are PARM and VALUE.  */
1061
1062 tree
1063 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1064 {
1065   tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1066   TREE_PURPOSE (t) = parm;
1067   TREE_VALUE (t) = value;
1068   return t;
1069 }
1070
1071 /* Return a newly created TREE_LIST node whose
1072    purpose and value fields are PURPOSE and VALUE
1073    and whose TREE_CHAIN is CHAIN.  */
1074
1075 tree
1076 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1077 {
1078   tree node;
1079
1080   node = ggc_alloc_zone_stat (sizeof (struct tree_list),
1081                               tree_zone PASS_MEM_STAT);
1082
1083   memset (node, 0, sizeof (struct tree_common));
1084
1085 #ifdef GATHER_STATISTICS
1086   tree_node_counts[(int) x_kind]++;
1087   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1088 #endif
1089
1090   TREE_SET_CODE (node, TREE_LIST);
1091   TREE_CHAIN (node) = chain;
1092   TREE_PURPOSE (node) = purpose;
1093   TREE_VALUE (node) = value;
1094   return node;
1095 }
1096
1097 \f
1098 /* Return the size nominally occupied by an object of type TYPE
1099    when it resides in memory.  The value is measured in units of bytes,
1100    and its data type is that normally used for type sizes
1101    (which is the first type created by make_signed_type or
1102    make_unsigned_type).  */
1103
1104 tree
1105 size_in_bytes (tree type)
1106 {
1107   tree t;
1108
1109   if (type == error_mark_node)
1110     return integer_zero_node;
1111
1112   type = TYPE_MAIN_VARIANT (type);
1113   t = TYPE_SIZE_UNIT (type);
1114
1115   if (t == 0)
1116     {
1117       lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1118       return size_zero_node;
1119     }
1120
1121   if (TREE_CODE (t) == INTEGER_CST)
1122     force_fit_type (t, 0);
1123
1124   return t;
1125 }
1126
1127 /* Return the size of TYPE (in bytes) as a wide integer
1128    or return -1 if the size can vary or is larger than an integer.  */
1129
1130 HOST_WIDE_INT
1131 int_size_in_bytes (tree type)
1132 {
1133   tree t;
1134
1135   if (type == error_mark_node)
1136     return 0;
1137
1138   type = TYPE_MAIN_VARIANT (type);
1139   t = TYPE_SIZE_UNIT (type);
1140   if (t == 0
1141       || TREE_CODE (t) != INTEGER_CST
1142       || TREE_OVERFLOW (t)
1143       || TREE_INT_CST_HIGH (t) != 0
1144       /* If the result would appear negative, it's too big to represent.  */
1145       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1146     return -1;
1147
1148   return TREE_INT_CST_LOW (t);
1149 }
1150 \f
1151 /* Return the bit position of FIELD, in bits from the start of the record.
1152    This is a tree of type bitsizetype.  */
1153
1154 tree
1155 bit_position (tree field)
1156 {
1157   return bit_from_pos (DECL_FIELD_OFFSET (field),
1158                        DECL_FIELD_BIT_OFFSET (field));
1159 }
1160
1161 /* Likewise, but return as an integer.  Abort if it cannot be represented
1162    in that way (since it could be a signed value, we don't have the option
1163    of returning -1 like int_size_in_byte can.  */
1164
1165 HOST_WIDE_INT
1166 int_bit_position (tree field)
1167 {
1168   return tree_low_cst (bit_position (field), 0);
1169 }
1170 \f
1171 /* Return the byte position of FIELD, in bytes from the start of the record.
1172    This is a tree of type sizetype.  */
1173
1174 tree
1175 byte_position (tree field)
1176 {
1177   return byte_from_pos (DECL_FIELD_OFFSET (field),
1178                         DECL_FIELD_BIT_OFFSET (field));
1179 }
1180
1181 /* Likewise, but return as an integer.  Abort if it cannot be represented
1182    in that way (since it could be a signed value, we don't have the option
1183    of returning -1 like int_size_in_byte can.  */
1184
1185 HOST_WIDE_INT
1186 int_byte_position (tree field)
1187 {
1188   return tree_low_cst (byte_position (field), 0);
1189 }
1190 \f
1191 /* Return the strictest alignment, in bits, that T is known to have.  */
1192
1193 unsigned int
1194 expr_align (tree t)
1195 {
1196   unsigned int align0, align1;
1197
1198   switch (TREE_CODE (t))
1199     {
1200     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1201       /* If we have conversions, we know that the alignment of the
1202          object must meet each of the alignments of the types.  */
1203       align0 = expr_align (TREE_OPERAND (t, 0));
1204       align1 = TYPE_ALIGN (TREE_TYPE (t));
1205       return MAX (align0, align1);
1206
1207     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1208     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1209     case CLEANUP_POINT_EXPR:  case UNSAVE_EXPR:
1210       /* These don't change the alignment of an object.  */
1211       return expr_align (TREE_OPERAND (t, 0));
1212
1213     case COND_EXPR:
1214       /* The best we can do is say that the alignment is the least aligned
1215          of the two arms.  */
1216       align0 = expr_align (TREE_OPERAND (t, 1));
1217       align1 = expr_align (TREE_OPERAND (t, 2));
1218       return MIN (align0, align1);
1219
1220     case LABEL_DECL:     case CONST_DECL:
1221     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1222       if (DECL_ALIGN (t) != 0)
1223         return DECL_ALIGN (t);
1224       break;
1225
1226     case FUNCTION_DECL:
1227       return FUNCTION_BOUNDARY;
1228
1229     default:
1230       break;
1231     }
1232
1233   /* Otherwise take the alignment from that of the type.  */
1234   return TYPE_ALIGN (TREE_TYPE (t));
1235 }
1236 \f
1237 /* Return, as a tree node, the number of elements for TYPE (which is an
1238    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1239
1240 tree
1241 array_type_nelts (tree type)
1242 {
1243   tree index_type, min, max;
1244
1245   /* If they did it with unspecified bounds, then we should have already
1246      given an error about it before we got here.  */
1247   if (! TYPE_DOMAIN (type))
1248     return error_mark_node;
1249
1250   index_type = TYPE_DOMAIN (type);
1251   min = TYPE_MIN_VALUE (index_type);
1252   max = TYPE_MAX_VALUE (index_type);
1253
1254   return (integer_zerop (min)
1255           ? max
1256           : fold (build2 (MINUS_EXPR, TREE_TYPE (max), max, min)));
1257 }
1258 \f
1259 /* Return nonzero if arg is static -- a reference to an object in
1260    static storage.  This is not the same as the C meaning of `static'.  */
1261
1262 int
1263 staticp (tree arg)
1264 {
1265   switch (TREE_CODE (arg))
1266     {
1267     case FUNCTION_DECL:
1268       /* Nested functions aren't static, since taking their address
1269          involves a trampoline.  */
1270       return ((decl_function_context (arg) == 0 || DECL_NO_STATIC_CHAIN (arg))
1271               && ! DECL_NON_ADDR_CONST_P (arg));
1272
1273     case VAR_DECL:
1274       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1275               && ! DECL_THREAD_LOCAL (arg)
1276               && ! DECL_NON_ADDR_CONST_P (arg));
1277
1278     case CONSTRUCTOR:
1279       return TREE_STATIC (arg);
1280
1281     case LABEL_DECL:
1282     case STRING_CST:
1283       return 1;
1284
1285     case COMPONENT_REF:
1286       /* If the thing being referenced is not a field, then it is
1287          something language specific.  */
1288       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1289         return (*lang_hooks.staticp) (arg);
1290
1291       /* If we are referencing a bitfield, we can't evaluate an
1292          ADDR_EXPR at compile time and so it isn't a constant.  */
1293       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1294         return 0;
1295
1296       return staticp (TREE_OPERAND (arg, 0));
1297
1298     case BIT_FIELD_REF:
1299       return 0;
1300
1301 #if 0
1302        /* This case is technically correct, but results in setting
1303           TREE_CONSTANT on ADDR_EXPRs that cannot be evaluated at
1304           compile time.  */
1305     case INDIRECT_REF:
1306       return TREE_CONSTANT (TREE_OPERAND (arg, 0));
1307 #endif
1308
1309     case ARRAY_REF:
1310     case ARRAY_RANGE_REF:
1311       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1312           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1313         return staticp (TREE_OPERAND (arg, 0));
1314       else
1315         return 0;
1316
1317     default:
1318       if ((unsigned int) TREE_CODE (arg)
1319           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1320         return lang_hooks.staticp (arg);
1321       else
1322         return 0;
1323     }
1324 }
1325 \f
1326 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1327    Do this to any expression which may be used in more than one place,
1328    but must be evaluated only once.
1329
1330    Normally, expand_expr would reevaluate the expression each time.
1331    Calling save_expr produces something that is evaluated and recorded
1332    the first time expand_expr is called on it.  Subsequent calls to
1333    expand_expr just reuse the recorded value.
1334
1335    The call to expand_expr that generates code that actually computes
1336    the value is the first call *at compile time*.  Subsequent calls
1337    *at compile time* generate code to use the saved value.
1338    This produces correct result provided that *at run time* control
1339    always flows through the insns made by the first expand_expr
1340    before reaching the other places where the save_expr was evaluated.
1341    You, the caller of save_expr, must make sure this is so.
1342
1343    Constants, and certain read-only nodes, are returned with no
1344    SAVE_EXPR because that is safe.  Expressions containing placeholders
1345    are not touched; see tree.def for an explanation of what these
1346    are used for.  */
1347
1348 tree
1349 save_expr (tree expr)
1350 {
1351   tree t = fold (expr);
1352   tree inner;
1353
1354   /* If the tree evaluates to a constant, then we don't want to hide that
1355      fact (i.e. this allows further folding, and direct checks for constants).
1356      However, a read-only object that has side effects cannot be bypassed.
1357      Since it is no problem to reevaluate literals, we just return the
1358      literal node.  */
1359   inner = skip_simple_arithmetic (t);
1360
1361   if (TREE_INVARIANT (inner)
1362       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1363       || TREE_CODE (inner) == SAVE_EXPR
1364       || TREE_CODE (inner) == ERROR_MARK)
1365     return t;
1366
1367   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1368      it means that the size or offset of some field of an object depends on
1369      the value within another field.
1370
1371      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1372      and some variable since it would then need to be both evaluated once and
1373      evaluated more than once.  Front-ends must assure this case cannot
1374      happen by surrounding any such subexpressions in their own SAVE_EXPR
1375      and forcing evaluation at the proper time.  */
1376   if (contains_placeholder_p (inner))
1377     return t;
1378
1379   t = build3 (SAVE_EXPR, TREE_TYPE (expr), t, current_function_decl,
1380               NULL_TREE);
1381
1382   /* This expression might be placed ahead of a jump to ensure that the
1383      value was computed on both sides of the jump.  So make sure it isn't
1384      eliminated as dead.  */
1385   TREE_SIDE_EFFECTS (t) = 1;
1386   TREE_READONLY (t) = 1;
1387   TREE_INVARIANT (t) = 1;
1388   return t;
1389 }
1390
1391 /* Look inside EXPR and into any simple arithmetic operations.  Return
1392    the innermost non-arithmetic node.  */
1393
1394 tree
1395 skip_simple_arithmetic (tree expr)
1396 {
1397   tree inner;
1398
1399   /* We don't care about whether this can be used as an lvalue in this
1400      context.  */
1401   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
1402     expr = TREE_OPERAND (expr, 0);
1403
1404   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
1405      a constant, it will be more efficient to not make another SAVE_EXPR since
1406      it will allow better simplification and GCSE will be able to merge the
1407      computations if they actually occur.  */
1408   inner = expr;
1409   while (1)
1410     {
1411       if (TREE_CODE_CLASS (TREE_CODE (inner)) == '1')
1412         inner = TREE_OPERAND (inner, 0);
1413       else if (TREE_CODE_CLASS (TREE_CODE (inner)) == '2')
1414         {
1415           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
1416             inner = TREE_OPERAND (inner, 0);
1417           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
1418             inner = TREE_OPERAND (inner, 1);
1419           else
1420             break;
1421         }
1422       else
1423         break;
1424     }
1425
1426   return inner;
1427 }
1428
1429 /* Arrange for an expression to be expanded multiple independent
1430    times.  This is useful for cleanup actions, as the backend can
1431    expand them multiple times in different places.  */
1432
1433 tree
1434 unsave_expr (tree expr)
1435 {
1436   tree t;
1437
1438   /* If this is already protected, no sense in protecting it again.  */
1439   if (TREE_CODE (expr) == UNSAVE_EXPR)
1440     return expr;
1441
1442   t = build1 (UNSAVE_EXPR, TREE_TYPE (expr), expr);
1443   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (expr);
1444   return t;
1445 }
1446
1447 /* Returns the index of the first non-tree operand for CODE, or the number
1448    of operands if all are trees.  */
1449
1450 int
1451 first_rtl_op (enum tree_code code)
1452 {
1453   switch (code)
1454     {
1455     case SAVE_EXPR:
1456       return 2;
1457     case GOTO_SUBROUTINE_EXPR:
1458     case RTL_EXPR:
1459       return 0;
1460     case WITH_CLEANUP_EXPR:
1461       return 2;
1462     default:
1463       return TREE_CODE_LENGTH (code);
1464     }
1465 }
1466
1467 /* Return which tree structure is used by T.  */
1468
1469 enum tree_node_structure_enum
1470 tree_node_structure (tree t)
1471 {
1472   enum tree_code code = TREE_CODE (t);
1473
1474   switch (TREE_CODE_CLASS (code))
1475     {
1476     case 'd':   return TS_DECL;
1477     case 't':   return TS_TYPE;
1478     case 'r': case '<': case '1': case '2': case 'e': case 's':
1479       return TS_EXP;
1480     default:  /* 'c' and 'x' */
1481       break;
1482     }
1483   switch (code)
1484     {
1485       /* 'c' cases.  */
1486     case INTEGER_CST:           return TS_INT_CST;
1487     case REAL_CST:              return TS_REAL_CST;
1488     case COMPLEX_CST:           return TS_COMPLEX;
1489     case VECTOR_CST:            return TS_VECTOR;
1490     case STRING_CST:            return TS_STRING;
1491       /* 'x' cases.  */
1492     case ERROR_MARK:            return TS_COMMON;
1493     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
1494     case TREE_LIST:             return TS_LIST;
1495     case TREE_VEC:              return TS_VEC;
1496     case PHI_NODE:              return TS_PHI_NODE;
1497     case SSA_NAME:              return TS_SSA_NAME;
1498     case PLACEHOLDER_EXPR:      return TS_COMMON;
1499     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
1500     case BLOCK:                 return TS_BLOCK;
1501     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
1502
1503     default:
1504       abort ();
1505     }
1506 }
1507
1508 /* Perform any modifications to EXPR required when it is unsaved.  Does
1509    not recurse into EXPR's subtrees.  */
1510
1511 void
1512 unsave_expr_1 (tree expr)
1513 {
1514   switch (TREE_CODE (expr))
1515     {
1516     case SAVE_EXPR:
1517       if (! SAVE_EXPR_PERSISTENT_P (expr))
1518         SAVE_EXPR_RTL (expr) = 0;
1519       break;
1520
1521     case TARGET_EXPR:
1522       /* Don't mess with a TARGET_EXPR that hasn't been expanded.
1523          It's OK for this to happen if it was part of a subtree that
1524          isn't immediately expanded, such as operand 2 of another
1525          TARGET_EXPR.  */
1526       if (TREE_OPERAND (expr, 1))
1527         break;
1528
1529       TREE_OPERAND (expr, 1) = TREE_OPERAND (expr, 3);
1530       TREE_OPERAND (expr, 3) = NULL_TREE;
1531       break;
1532
1533     case RTL_EXPR:
1534       /* I don't yet know how to emit a sequence multiple times.  */
1535       if (RTL_EXPR_SEQUENCE (expr) != 0)
1536         abort ();
1537       break;
1538
1539     default:
1540       break;
1541     }
1542 }
1543
1544 /* Return 0 if it is safe to evaluate EXPR multiple times,
1545    return 1 if it is safe if EXPR is unsaved afterward, or
1546    return 2 if it is completely unsafe.
1547
1548    This assumes that CALL_EXPRs and TARGET_EXPRs are never replicated in
1549    an expression tree, so that it safe to unsave them and the surrounding
1550    context will be correct.
1551
1552    SAVE_EXPRs basically *only* appear replicated in an expression tree,
1553    occasionally across the whole of a function.  It is therefore only
1554    safe to unsave a SAVE_EXPR if you know that all occurrences appear
1555    below the UNSAVE_EXPR.
1556
1557    RTL_EXPRs consume their rtl during evaluation.  It is therefore
1558    never possible to unsave them.  */
1559
1560 int
1561 unsafe_for_reeval (tree expr)
1562 {
1563   int unsafeness = 0;
1564   enum tree_code code;
1565   int i, tmp, tmp2;
1566   tree exp;
1567   int first_rtl;
1568
1569   if (expr == NULL_TREE)
1570     return 1;
1571
1572   code = TREE_CODE (expr);
1573   first_rtl = first_rtl_op (code);
1574
1575   switch (code)
1576     {
1577     case SAVE_EXPR:
1578     case RTL_EXPR:
1579       return 2;
1580
1581       /* A label can only be emitted once.  */
1582     case LABEL_EXPR:
1583       return 1;
1584
1585     case BIND_EXPR:
1586       unsafeness = 1;
1587       break;
1588
1589     case TREE_LIST:
1590       for (exp = expr; exp != 0; exp = TREE_CHAIN (exp))
1591         {
1592           tmp = unsafe_for_reeval (TREE_VALUE (exp));
1593           unsafeness = MAX (tmp, unsafeness);
1594         }
1595
1596       return unsafeness;
1597
1598     case CALL_EXPR:
1599       tmp2 = unsafe_for_reeval (TREE_OPERAND (expr, 0));
1600       tmp = unsafe_for_reeval (TREE_OPERAND (expr, 1));
1601       return MAX (MAX (tmp, 1), tmp2);
1602
1603     case TARGET_EXPR:
1604       unsafeness = 1;
1605       break;
1606
1607     case EXIT_BLOCK_EXPR:
1608       /* EXIT_BLOCK_LABELED_BLOCK, a.k.a. TREE_OPERAND (expr, 0), holds
1609          a reference to an ancestor LABELED_BLOCK, so we need to avoid
1610          unbounded recursion in the 'e' traversal code below.  */
1611       exp = EXIT_BLOCK_RETURN (expr);
1612       return exp ? unsafe_for_reeval (exp) : 0;
1613
1614     default:
1615       tmp = lang_hooks.unsafe_for_reeval (expr);
1616       if (tmp >= 0)
1617         return tmp;
1618       break;
1619     }
1620
1621   switch (TREE_CODE_CLASS (code))
1622     {
1623     case 'c':  /* a constant */
1624     case 't':  /* a type node */
1625     case 'x':  /* something random, like an identifier or an ERROR_MARK.  */
1626     case 'd':  /* A decl node */
1627       return 0;
1628
1629     case 'e':  /* an expression */
1630     case 'r':  /* a reference */
1631     case 's':  /* an expression with side effects */
1632     case '<':  /* a comparison expression */
1633     case '2':  /* a binary arithmetic expression */
1634     case '1':  /* a unary arithmetic expression */
1635       for (i = first_rtl - 1; i >= 0; i--)
1636         {
1637           tmp = unsafe_for_reeval (TREE_OPERAND (expr, i));
1638           unsafeness = MAX (tmp, unsafeness);
1639         }
1640
1641       return unsafeness;
1642
1643     default:
1644       return 2;
1645     }
1646 }
1647 \f
1648 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
1649    or offset that depends on a field within a record.  */
1650
1651 bool
1652 contains_placeholder_p (tree exp)
1653 {
1654   enum tree_code code;
1655   int result;
1656
1657   if (!exp)
1658     return 0;
1659
1660   code = TREE_CODE (exp);
1661   if (code == PLACEHOLDER_EXPR)
1662     return 1;
1663
1664   switch (TREE_CODE_CLASS (code))
1665     {
1666     case 'r':
1667       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
1668          position computations since they will be converted into a
1669          WITH_RECORD_EXPR involving the reference, which will assume
1670          here will be valid.  */
1671       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1672
1673     case 'x':
1674       if (code == TREE_LIST)
1675         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
1676                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
1677       break;
1678
1679     case '1':
1680     case '2':  case '<':
1681     case 'e':
1682       switch (code)
1683         {
1684         case COMPOUND_EXPR:
1685           /* Ignoring the first operand isn't quite right, but works best.  */
1686           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
1687
1688         case COND_EXPR:
1689           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1690                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
1691                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
1692
1693         case SAVE_EXPR:
1694           /* If we already know this doesn't have a placeholder, don't
1695              check again.  */
1696           if (SAVE_EXPR_NOPLACEHOLDER (exp) || SAVE_EXPR_RTL (exp) != 0)
1697             return 0;
1698
1699           SAVE_EXPR_NOPLACEHOLDER (exp) = 1;
1700           result = CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1701           if (result)
1702             SAVE_EXPR_NOPLACEHOLDER (exp) = 0;
1703
1704           return result;
1705
1706         default:
1707           break;
1708         }
1709
1710       switch (first_rtl_op (code))
1711         {
1712         case 1:
1713           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1714         case 2:
1715           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1716                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
1717         default:
1718           return 0;
1719         }
1720
1721     default:
1722       return 0;
1723     }
1724   return 0;
1725 }
1726
1727 /* Return 1 if any part of the computation of TYPE involves a PLACEHOLDER_EXPR.
1728    This includes size, bounds, qualifiers (for QUAL_UNION_TYPE) and field
1729    positions.  */
1730
1731 bool
1732 type_contains_placeholder_p (tree type)
1733 {
1734   /* If the size contains a placeholder or the parent type (component type in
1735      the case of arrays) type involves a placeholder, this type does.  */
1736   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
1737       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
1738       || (TREE_TYPE (type) != 0
1739           && type_contains_placeholder_p (TREE_TYPE (type))))
1740     return 1;
1741
1742   /* Now do type-specific checks.  Note that the last part of the check above
1743      greatly limits what we have to do below.  */
1744   switch (TREE_CODE (type))
1745     {
1746     case VOID_TYPE:
1747     case COMPLEX_TYPE:
1748     case ENUMERAL_TYPE:
1749     case BOOLEAN_TYPE:
1750     case CHAR_TYPE:
1751     case POINTER_TYPE:
1752     case OFFSET_TYPE:
1753     case REFERENCE_TYPE:
1754     case METHOD_TYPE:
1755     case FILE_TYPE:
1756     case FUNCTION_TYPE:
1757       return 0;
1758
1759     case INTEGER_TYPE:
1760     case REAL_TYPE:
1761       /* Here we just check the bounds.  */
1762       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
1763               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
1764
1765     case ARRAY_TYPE:
1766     case SET_TYPE:
1767     case VECTOR_TYPE:
1768       /* We're already checked the component type (TREE_TYPE), so just check
1769          the index type.  */
1770       return type_contains_placeholder_p (TYPE_DOMAIN (type));
1771
1772     case RECORD_TYPE:
1773     case UNION_TYPE:
1774     case QUAL_UNION_TYPE:
1775       {
1776         static tree seen_types = 0;
1777         tree field;
1778         bool ret = 0;
1779
1780         /* We have to be careful here that we don't end up in infinite
1781            recursions due to a field of a type being a pointer to that type
1782            or to a mutually-recursive type.  So we store a list of record
1783            types that we've seen and see if this type is in them.  To save
1784            memory, we don't use a list for just one type.  Here we check
1785            whether we've seen this type before and store it if not.  */
1786         if (seen_types == 0)
1787           seen_types = type;
1788         else if (TREE_CODE (seen_types) != TREE_LIST)
1789           {
1790             if (seen_types == type)
1791               return 0;
1792
1793             seen_types = tree_cons (NULL_TREE, type,
1794                                     build_tree_list (NULL_TREE, seen_types));
1795           }
1796         else
1797           {
1798             if (value_member (type, seen_types) != 0)
1799               return 0;
1800
1801             seen_types = tree_cons (NULL_TREE, type, seen_types);
1802           }
1803
1804         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
1805           if (TREE_CODE (field) == FIELD_DECL
1806               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
1807                   || (TREE_CODE (type) == QUAL_UNION_TYPE
1808                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
1809                   || type_contains_placeholder_p (TREE_TYPE (field))))
1810             {
1811               ret = true;
1812               break;
1813             }
1814
1815         /* Now remove us from seen_types and return the result.  */
1816         if (seen_types == type)
1817           seen_types = 0;
1818         else
1819           seen_types = TREE_CHAIN (seen_types);
1820
1821         return ret;
1822       }
1823
1824     default:
1825       abort ();
1826     }
1827 }
1828
1829 /* Return 1 if EXP contains any expressions that produce cleanups for an
1830    outer scope to deal with.  Used by fold.  */
1831
1832 int
1833 has_cleanups (tree exp)
1834 {
1835   int i, nops, cmp;
1836
1837   if (! TREE_SIDE_EFFECTS (exp))
1838     return 0;
1839
1840   switch (TREE_CODE (exp))
1841     {
1842     case TARGET_EXPR:
1843     case GOTO_SUBROUTINE_EXPR:
1844     case WITH_CLEANUP_EXPR:
1845       return 1;
1846
1847     case CLEANUP_POINT_EXPR:
1848       return 0;
1849
1850     case CALL_EXPR:
1851       for (exp = TREE_OPERAND (exp, 1); exp; exp = TREE_CHAIN (exp))
1852         {
1853           cmp = has_cleanups (TREE_VALUE (exp));
1854           if (cmp)
1855             return cmp;
1856         }
1857       return 0;
1858
1859     case DECL_EXPR:
1860       return (DECL_INITIAL (DECL_EXPR_DECL (exp))
1861               && has_cleanups (DECL_INITIAL (DECL_EXPR_DECL (exp))));
1862
1863     default:
1864       break;
1865     }
1866
1867   /* This general rule works for most tree codes.  All exceptions should be
1868      handled above.  If this is a language-specific tree code, we can't
1869      trust what might be in the operand, so say we don't know
1870      the situation.  */
1871   if ((int) TREE_CODE (exp) >= (int) LAST_AND_UNUSED_TREE_CODE)
1872     return -1;
1873
1874   nops = first_rtl_op (TREE_CODE (exp));
1875   for (i = 0; i < nops; i++)
1876     if (TREE_OPERAND (exp, i) != 0)
1877       {
1878         int type = TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (exp, i)));
1879         if (type == 'e' || type == '<' || type == '1' || type == '2'
1880             || type == 'r' || type == 's')
1881           {
1882             cmp = has_cleanups (TREE_OPERAND (exp, i));
1883             if (cmp)
1884               return cmp;
1885           }
1886       }
1887
1888   return 0;
1889 }
1890 \f
1891 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
1892    return a tree with all occurrences of references to F in a
1893    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
1894    contains only arithmetic expressions or a CALL_EXPR with a
1895    PLACEHOLDER_EXPR occurring only in its arglist.  */
1896
1897 tree
1898 substitute_in_expr (tree exp, tree f, tree r)
1899 {
1900   enum tree_code code = TREE_CODE (exp);
1901   tree op0, op1, op2;
1902   tree new;
1903   tree inner;
1904
1905   /* We handle TREE_LIST and COMPONENT_REF separately.  */
1906   if (code == TREE_LIST)
1907     {
1908       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
1909       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
1910       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
1911         return exp;
1912
1913       return tree_cons (TREE_PURPOSE (exp), op1, op0);
1914     }
1915   else if (code == COMPONENT_REF)
1916    {
1917      /* If this expression is getting a value from a PLACEHOLDER_EXPR
1918         and it is the right field, replace it with R.  */
1919      for (inner = TREE_OPERAND (exp, 0);
1920           TREE_CODE_CLASS (TREE_CODE (inner)) == 'r';
1921           inner = TREE_OPERAND (inner, 0))
1922        ;
1923      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
1924          && TREE_OPERAND (exp, 1) == f)
1925        return r;
1926
1927      /* If this expression hasn't been completed let, leave it
1928         alone.  */
1929      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
1930        return exp;
1931
1932      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1933      if (op0 == TREE_OPERAND (exp, 0))
1934        return exp;
1935
1936      new = fold (build (code, TREE_TYPE (exp), op0, TREE_OPERAND (exp, 1),
1937                         NULL_TREE));
1938    }
1939   else
1940     switch (TREE_CODE_CLASS (code))
1941       {
1942       case 'c':
1943       case 'd':
1944         return exp;
1945
1946       case 'x':
1947       case '1':
1948       case '2':
1949       case '<':
1950       case 'e':
1951       case 'r':
1952         switch (first_rtl_op (code))
1953           {
1954           case 0:
1955             return exp;
1956
1957           case 1:
1958             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1959             if (op0 == TREE_OPERAND (exp, 0))
1960               return exp;
1961
1962             new = fold (build1 (code, TREE_TYPE (exp), op0));
1963             break;
1964
1965           case 2:
1966             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1967             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
1968
1969             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
1970               return exp;
1971
1972             new = fold (build2 (code, TREE_TYPE (exp), op0, op1));
1973             break;
1974
1975           case 3:
1976             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1977             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
1978             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
1979
1980             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
1981                 && op2 == TREE_OPERAND (exp, 2))
1982               return exp;
1983
1984             new = fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
1985             break;
1986
1987           default:
1988             abort ();
1989           }
1990         break;
1991
1992       default:
1993         abort ();
1994       }
1995
1996   TREE_READONLY (new) = TREE_READONLY (exp);
1997   return new;
1998 }
1999
2000 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2001    for it within OBJ, a tree that is an object or a chain of references.  */
2002
2003 tree
2004 substitute_placeholder_in_expr (tree exp, tree obj)
2005 {
2006   enum tree_code code = TREE_CODE (exp);
2007   tree op0, op1, op2, op3;
2008
2009   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2010      in the chain of OBJ.  */
2011   if (code == PLACEHOLDER_EXPR)
2012     {
2013       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2014       tree elt;
2015
2016       for (elt = obj; elt != 0;
2017            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2018                    || TREE_CODE (elt) == COND_EXPR)
2019                   ? TREE_OPERAND (elt, 1)
2020                   : (TREE_CODE_CLASS (TREE_CODE (elt)) == 'r'
2021                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '1'
2022                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '2'
2023                      || TREE_CODE_CLASS (TREE_CODE (elt)) == 'e')
2024                   ? TREE_OPERAND (elt, 0) : 0))
2025         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2026           return elt;
2027
2028       for (elt = obj; elt != 0;
2029            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2030                    || TREE_CODE (elt) == COND_EXPR)
2031                   ? TREE_OPERAND (elt, 1)
2032                   : (TREE_CODE_CLASS (TREE_CODE (elt)) == 'r'
2033                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '1'
2034                      || TREE_CODE_CLASS (TREE_CODE (elt)) == '2'
2035                      || TREE_CODE_CLASS (TREE_CODE (elt)) == 'e')
2036                   ? TREE_OPERAND (elt, 0) : 0))
2037         if (POINTER_TYPE_P (TREE_TYPE (elt))
2038             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2039                 == need_type))
2040           return fold (build1 (INDIRECT_REF, need_type, elt));
2041
2042       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2043          survives until RTL generation, there will be an error.  */
2044       return exp;
2045     }
2046
2047   /* TREE_LIST is special because we need to look at TREE_VALUE
2048      and TREE_CHAIN, not TREE_OPERANDS.  */
2049   else if (code == TREE_LIST)
2050     {
2051       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2052       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2053       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2054         return exp;
2055
2056       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2057     }
2058   else
2059     switch (TREE_CODE_CLASS (code))
2060       {
2061       case 'c':
2062       case 'd':
2063         return exp;
2064
2065       case 'x':
2066       case '1':
2067       case '2':
2068       case '<':
2069       case 'e':
2070       case 'r':
2071       case 's':
2072         switch (first_rtl_op (code))
2073           {
2074           case 0:
2075             return exp;
2076
2077           case 1:
2078             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2079             if (op0 == TREE_OPERAND (exp, 0))
2080               return exp;
2081             else
2082               return fold (build1 (code, TREE_TYPE (exp), op0));
2083
2084           case 2:
2085             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2086             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2087
2088             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2089               return exp;
2090             else
2091               return fold (build2 (code, TREE_TYPE (exp), op0, op1));
2092
2093           case 3:
2094             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2095             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2096             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2097
2098             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2099                 && op2 == TREE_OPERAND (exp, 2))
2100               return exp;
2101             else
2102               return fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
2103
2104           case 4:
2105             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2106             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2107             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2108             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2109
2110             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2111                 && op2 == TREE_OPERAND (exp, 2)
2112                 && op3 == TREE_OPERAND (exp, 3))
2113               return exp;
2114             else
2115               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2116
2117           default:
2118             abort ();
2119           }
2120         break;
2121
2122       default:
2123         abort ();
2124       }
2125 }
2126 \f
2127 /* Stabilize a reference so that we can use it any number of times
2128    without causing its operands to be evaluated more than once.
2129    Returns the stabilized reference.  This works by means of save_expr,
2130    so see the caveats in the comments about save_expr.
2131
2132    Also allows conversion expressions whose operands are references.
2133    Any other kind of expression is returned unchanged.  */
2134
2135 tree
2136 stabilize_reference (tree ref)
2137 {
2138   tree result;
2139   enum tree_code code = TREE_CODE (ref);
2140
2141   switch (code)
2142     {
2143     case VAR_DECL:
2144     case PARM_DECL:
2145     case RESULT_DECL:
2146       /* No action is needed in this case.  */
2147       return ref;
2148
2149     case NOP_EXPR:
2150     case CONVERT_EXPR:
2151     case FLOAT_EXPR:
2152     case FIX_TRUNC_EXPR:
2153     case FIX_FLOOR_EXPR:
2154     case FIX_ROUND_EXPR:
2155     case FIX_CEIL_EXPR:
2156       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2157       break;
2158
2159     case INDIRECT_REF:
2160       result = build_nt (INDIRECT_REF,
2161                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2162       break;
2163
2164     case COMPONENT_REF:
2165       result = build_nt (COMPONENT_REF,
2166                          stabilize_reference (TREE_OPERAND (ref, 0)),
2167                          TREE_OPERAND (ref, 1), NULL_TREE);
2168       break;
2169
2170     case BIT_FIELD_REF:
2171       result = build_nt (BIT_FIELD_REF,
2172                          stabilize_reference (TREE_OPERAND (ref, 0)),
2173                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2174                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2175       break;
2176
2177     case ARRAY_REF:
2178       result = build_nt (ARRAY_REF,
2179                          stabilize_reference (TREE_OPERAND (ref, 0)),
2180                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2181                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2182       break;
2183
2184     case ARRAY_RANGE_REF:
2185       result = build_nt (ARRAY_RANGE_REF,
2186                          stabilize_reference (TREE_OPERAND (ref, 0)),
2187                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2188                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2189       break;
2190
2191     case COMPOUND_EXPR:
2192       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2193          it wouldn't be ignored.  This matters when dealing with
2194          volatiles.  */
2195       return stabilize_reference_1 (ref);
2196
2197     case RTL_EXPR:
2198       result = build1 (INDIRECT_REF, TREE_TYPE (ref),
2199                        save_expr (build1 (ADDR_EXPR,
2200                                           build_pointer_type (TREE_TYPE (ref)),
2201                                           ref)));
2202       break;
2203
2204       /* If arg isn't a kind of lvalue we recognize, make no change.
2205          Caller should recognize the error for an invalid lvalue.  */
2206     default:
2207       return ref;
2208
2209     case ERROR_MARK:
2210       return error_mark_node;
2211     }
2212
2213   TREE_TYPE (result) = TREE_TYPE (ref);
2214   TREE_READONLY (result) = TREE_READONLY (ref);
2215   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2216   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2217
2218   return result;
2219 }
2220
2221 /* Subroutine of stabilize_reference; this is called for subtrees of
2222    references.  Any expression with side-effects must be put in a SAVE_EXPR
2223    to ensure that it is only evaluated once.
2224
2225    We don't put SAVE_EXPR nodes around everything, because assigning very
2226    simple expressions to temporaries causes us to miss good opportunities
2227    for optimizations.  Among other things, the opportunity to fold in the
2228    addition of a constant into an addressing mode often gets lost, e.g.
2229    "y[i+1] += x;".  In general, we take the approach that we should not make
2230    an assignment unless we are forced into it - i.e., that any non-side effect
2231    operator should be allowed, and that cse should take care of coalescing
2232    multiple utterances of the same expression should that prove fruitful.  */
2233
2234 tree
2235 stabilize_reference_1 (tree e)
2236 {
2237   tree result;
2238   enum tree_code code = TREE_CODE (e);
2239
2240   /* We cannot ignore const expressions because it might be a reference
2241      to a const array but whose index contains side-effects.  But we can
2242      ignore things that are actual constant or that already have been
2243      handled by this function.  */
2244
2245   if (TREE_INVARIANT (e))
2246     return e;
2247
2248   switch (TREE_CODE_CLASS (code))
2249     {
2250     case 'x':
2251     case 't':
2252     case 'd':
2253     case '<':
2254     case 's':
2255     case 'e':
2256     case 'r':
2257       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2258          so that it will only be evaluated once.  */
2259       /* The reference (r) and comparison (<) classes could be handled as
2260          below, but it is generally faster to only evaluate them once.  */
2261       if (TREE_SIDE_EFFECTS (e))
2262         return save_expr (e);
2263       return e;
2264
2265     case 'c':
2266       /* Constants need no processing.  In fact, we should never reach
2267          here.  */
2268       return e;
2269
2270     case '2':
2271       /* Division is slow and tends to be compiled with jumps,
2272          especially the division by powers of 2 that is often
2273          found inside of an array reference.  So do it just once.  */
2274       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2275           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2276           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2277           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2278         return save_expr (e);
2279       /* Recursively stabilize each operand.  */
2280       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2281                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2282       break;
2283
2284     case '1':
2285       /* Recursively stabilize each operand.  */
2286       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2287       break;
2288
2289     default:
2290       abort ();
2291     }
2292
2293   TREE_TYPE (result) = TREE_TYPE (e);
2294   TREE_READONLY (result) = TREE_READONLY (e);
2295   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2296   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2297   TREE_INVARIANT (result) = 1;
2298
2299   return result;
2300 }
2301 \f
2302 /* Low-level constructors for expressions.  */
2303
2304 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2305    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2306
2307 void
2308 recompute_tree_invarant_for_addr_expr (tree t)
2309 {
2310   tree node;
2311   bool tc = true, ti = true, se = false;
2312
2313   /* We started out assuming this address is both invariant and constant, but
2314      does not have side effects.  Now go down any handled components and see if
2315      any of them involve offsets that are either non-constant or non-invariant.
2316      Also check for side-effects.
2317
2318      ??? Note that this code makes no attempt to deal with the case where
2319      taking the address of something causes a copy due to misalignment.  */
2320
2321 #define UPDATE_TITCSE(NODE)  \
2322 do { tree _node = (NODE); \
2323      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2324      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2325      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2326
2327   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2328        node = TREE_OPERAND (node, 0))
2329     {
2330       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2331          array reference (probably made temporarily by the G++ front end),
2332          so ignore all the operands.  */
2333       if ((TREE_CODE (node) == ARRAY_REF
2334            || TREE_CODE (node) == ARRAY_RANGE_REF)
2335           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2336         {
2337           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2338           UPDATE_TITCSE (array_ref_low_bound (node));
2339           UPDATE_TITCSE (array_ref_element_size (node));
2340         }
2341       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2342          FIELD_DECL, apparently.  The G++ front end can put something else
2343          there, at least temporarily.  */
2344       else if (TREE_CODE (node) == COMPONENT_REF
2345                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2346         UPDATE_TITCSE (component_ref_field_offset (node));
2347       else if (TREE_CODE (node) == BIT_FIELD_REF)
2348         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2349     }
2350
2351   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2352      it.  If it's a decl, it's definitely invariant and it's constant if the
2353      decl is static.  (Taking the address of a volatile variable is not
2354      volatile.)  If it's a constant, the address is both invariant and
2355      constant.  Otherwise it's neither.  */
2356   if (TREE_CODE (node) == INDIRECT_REF)
2357     UPDATE_TITCSE (node);
2358   else if (DECL_P (node))
2359     {
2360       if (!staticp (node))
2361         tc = false;
2362     }
2363   else if (TREE_CODE_CLASS (TREE_CODE (node)) == 'c')
2364     ;
2365   else
2366     {
2367       ti = tc = false;
2368       se |= TREE_SIDE_EFFECTS (node);
2369     }
2370
2371   TREE_CONSTANT (t) = tc;
2372   TREE_INVARIANT (t) = ti;
2373   TREE_SIDE_EFFECTS (t) = se;
2374 #undef UPDATE_TITCSE
2375 }
2376
2377 /* Build an expression of code CODE, data type TYPE, and operands as
2378    specified.  Expressions and reference nodes can be created this way.
2379    Constants, decls, types and misc nodes cannot be.
2380
2381    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2382    enough for all extant tree codes.  These functions can be called
2383    directly (preferably!), but can also be obtained via GCC preprocessor
2384    magic within the build macro.  */
2385
2386 tree
2387 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2388 {
2389   tree t;
2390
2391 #ifdef ENABLE_CHECKING
2392   if (TREE_CODE_LENGTH (code) != 0)
2393     abort ();
2394 #endif
2395
2396   t = make_node_stat (code PASS_MEM_STAT);
2397   TREE_TYPE (t) = tt;
2398
2399   return t;
2400 }
2401
2402 tree
2403 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2404 {
2405   int length = sizeof (struct tree_exp);
2406 #ifdef GATHER_STATISTICS
2407   tree_node_kind kind;
2408 #endif
2409   tree t;
2410
2411 #ifdef GATHER_STATISTICS
2412   switch (TREE_CODE_CLASS (code))
2413     {
2414     case 's':  /* an expression with side effects */
2415       kind = s_kind;
2416       break;
2417     case 'r':  /* a reference */
2418       kind = r_kind;
2419       break;
2420     default:
2421       kind = e_kind;
2422       break;
2423     }
2424
2425   tree_node_counts[(int) kind]++;
2426   tree_node_sizes[(int) kind] += length;
2427 #endif
2428
2429 #ifdef ENABLE_CHECKING
2430   if (TREE_CODE_LENGTH (code) != 1)
2431     abort ();
2432 #endif /* ENABLE_CHECKING */
2433
2434   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
2435
2436   memset (t, 0, sizeof (struct tree_common));
2437
2438   TREE_SET_CODE (t, code);
2439
2440   TREE_TYPE (t) = type;
2441 #ifdef USE_MAPPED_LOCATION
2442   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2443 #else
2444   SET_EXPR_LOCUS (t, NULL);
2445 #endif
2446   TREE_COMPLEXITY (t) = 0;
2447   TREE_OPERAND (t, 0) = node;
2448   TREE_BLOCK (t) = NULL_TREE;
2449   if (node && !TYPE_P (node) && first_rtl_op (code) != 0)
2450     {
2451       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2452       TREE_READONLY (t) = TREE_READONLY (node);
2453     }
2454
2455   if (TREE_CODE_CLASS (code) == 's')
2456     TREE_SIDE_EFFECTS (t) = 1;
2457   else switch (code)
2458     {
2459     case INIT_EXPR:
2460     case MODIFY_EXPR:
2461     case VA_ARG_EXPR:
2462     case RTL_EXPR:
2463     case PREDECREMENT_EXPR:
2464     case PREINCREMENT_EXPR:
2465     case POSTDECREMENT_EXPR:
2466     case POSTINCREMENT_EXPR:
2467       /* All of these have side-effects, no matter what their
2468          operands are.  */
2469       TREE_SIDE_EFFECTS (t) = 1;
2470       TREE_READONLY (t) = 0;
2471       break;
2472
2473     case INDIRECT_REF:
2474       /* Whether a dereference is readonly has nothing to do with whether
2475          its operand is readonly.  */
2476       TREE_READONLY (t) = 0;
2477       break;
2478
2479     case ADDR_EXPR:
2480       if (node)
2481         recompute_tree_invarant_for_addr_expr (t);
2482       break;
2483
2484     default:
2485       if (TREE_CODE_CLASS (code) == '1' && node && !TYPE_P (node)
2486           && TREE_CONSTANT (node))
2487         TREE_CONSTANT (t) = 1;
2488       if (TREE_CODE_CLASS (code) == '1' && node && TREE_INVARIANT (node))
2489         TREE_INVARIANT (t) = 1;
2490       if (TREE_CODE_CLASS (code) == 'r' && node && TREE_THIS_VOLATILE (node))
2491         TREE_THIS_VOLATILE (t) = 1;
2492       break;
2493     }
2494
2495   return t;
2496 }
2497
2498 #define PROCESS_ARG(N)                  \
2499   do {                                  \
2500     TREE_OPERAND (t, N) = arg##N;       \
2501     if (arg##N &&!TYPE_P (arg##N) && fro > N) \
2502       {                                 \
2503         if (TREE_SIDE_EFFECTS (arg##N)) \
2504           side_effects = 1;             \
2505         if (!TREE_READONLY (arg##N))    \
2506           read_only = 0;                \
2507         if (!TREE_CONSTANT (arg##N))    \
2508           constant = 0;                 \
2509         if (!TREE_INVARIANT (arg##N))   \
2510           invariant = 0;                \
2511       }                                 \
2512   } while (0)
2513
2514 tree
2515 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2516 {
2517   bool constant, read_only, side_effects, invariant;
2518   tree t;
2519   int fro;
2520
2521 #ifdef ENABLE_CHECKING
2522   if (TREE_CODE_LENGTH (code) != 2)
2523     abort ();
2524 #endif
2525
2526   t = make_node_stat (code PASS_MEM_STAT);
2527   TREE_TYPE (t) = tt;
2528
2529   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2530      result based on those same flags for the arguments.  But if the
2531      arguments aren't really even `tree' expressions, we shouldn't be trying
2532      to do this.  */
2533   fro = first_rtl_op (code);
2534
2535   /* Expressions without side effects may be constant if their
2536      arguments are as well.  */
2537   constant = (TREE_CODE_CLASS (code) == '<'
2538               || TREE_CODE_CLASS (code) == '2');
2539   read_only = 1;
2540   side_effects = TREE_SIDE_EFFECTS (t);
2541   invariant = constant;
2542
2543   PROCESS_ARG(0);
2544   PROCESS_ARG(1);
2545
2546   TREE_READONLY (t) = read_only;
2547   TREE_CONSTANT (t) = constant;
2548   TREE_INVARIANT (t) = invariant;
2549   TREE_SIDE_EFFECTS (t) = side_effects;
2550   TREE_THIS_VOLATILE (t)
2551     = TREE_CODE_CLASS (code) == 'r' && arg0 && TREE_THIS_VOLATILE (arg0);
2552
2553   return t;
2554 }
2555
2556 tree
2557 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2558              tree arg2 MEM_STAT_DECL)
2559 {
2560   bool constant, read_only, side_effects, invariant;
2561   tree t;
2562   int fro;
2563
2564 #ifdef ENABLE_CHECKING
2565   if (TREE_CODE_LENGTH (code) != 3)
2566     abort ();
2567 #endif
2568
2569   t = make_node_stat (code PASS_MEM_STAT);
2570   TREE_TYPE (t) = tt;
2571
2572   fro = first_rtl_op (code);
2573
2574   side_effects = TREE_SIDE_EFFECTS (t);
2575
2576   PROCESS_ARG(0);
2577   PROCESS_ARG(1);
2578   PROCESS_ARG(2);
2579
2580   if (code == CALL_EXPR && !side_effects)
2581     {
2582       tree node;
2583       int i;
2584
2585       /* Calls have side-effects, except those to const or
2586          pure functions.  */
2587       i = call_expr_flags (t);
2588       if (!(i & (ECF_CONST | ECF_PURE)))
2589         side_effects = 1;
2590
2591       /* And even those have side-effects if their arguments do.  */
2592       else for (node = arg1; node; node = TREE_CHAIN (node))
2593         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2594           {
2595             side_effects = 1;
2596             break;
2597           }
2598     }
2599
2600   TREE_SIDE_EFFECTS (t) = side_effects;
2601   TREE_THIS_VOLATILE (t)
2602     = TREE_CODE_CLASS (code) == 'r' && arg0 && TREE_THIS_VOLATILE (arg0);
2603
2604   return t;
2605 }
2606
2607 tree
2608 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2609              tree arg2, tree arg3 MEM_STAT_DECL)
2610 {
2611   bool constant, read_only, side_effects, invariant;
2612   tree t;
2613   int fro;
2614
2615 #ifdef ENABLE_CHECKING
2616   if (TREE_CODE_LENGTH (code) != 4)
2617     abort ();
2618 #endif
2619
2620   t = make_node_stat (code PASS_MEM_STAT);
2621   TREE_TYPE (t) = tt;
2622
2623   fro = first_rtl_op (code);
2624
2625   side_effects = TREE_SIDE_EFFECTS (t);
2626
2627   PROCESS_ARG(0);
2628   PROCESS_ARG(1);
2629   PROCESS_ARG(2);
2630   PROCESS_ARG(3);
2631
2632   TREE_SIDE_EFFECTS (t) = side_effects;
2633   TREE_THIS_VOLATILE (t)
2634     = TREE_CODE_CLASS (code) == 'r' && arg0 && TREE_THIS_VOLATILE (arg0);
2635
2636   return t;
2637 }
2638
2639 /* Backup definition for non-gcc build compilers.  */
2640
2641 tree
2642 (build) (enum tree_code code, tree tt, ...)
2643 {
2644   tree t, arg0, arg1, arg2, arg3;
2645   int length = TREE_CODE_LENGTH (code);
2646   va_list p;
2647
2648   va_start (p, tt);
2649   switch (length)
2650     {
2651     case 0:
2652       t = build0 (code, tt);
2653       break;
2654     case 1:
2655       arg0 = va_arg (p, tree);
2656       t = build1 (code, tt, arg0);
2657       break;
2658     case 2:
2659       arg0 = va_arg (p, tree);
2660       arg1 = va_arg (p, tree);
2661       t = build2 (code, tt, arg0, arg1);
2662       break;
2663     case 3:
2664       arg0 = va_arg (p, tree);
2665       arg1 = va_arg (p, tree);
2666       arg2 = va_arg (p, tree);
2667       t = build3 (code, tt, arg0, arg1, arg2);
2668       break;
2669     case 4:
2670       arg0 = va_arg (p, tree);
2671       arg1 = va_arg (p, tree);
2672       arg2 = va_arg (p, tree);
2673       arg3 = va_arg (p, tree);
2674       t = build4 (code, tt, arg0, arg1, arg2, arg3);
2675       break;
2676     default:
2677       abort ();
2678     }
2679   va_end (p);
2680
2681   return t;
2682 }
2683
2684 /* Similar except don't specify the TREE_TYPE
2685    and leave the TREE_SIDE_EFFECTS as 0.
2686    It is permissible for arguments to be null,
2687    or even garbage if their values do not matter.  */
2688
2689 tree
2690 build_nt (enum tree_code code, ...)
2691 {
2692   tree t;
2693   int length;
2694   int i;
2695   va_list p;
2696
2697   va_start (p, code);
2698
2699   t = make_node (code);
2700   length = TREE_CODE_LENGTH (code);
2701
2702   for (i = 0; i < length; i++)
2703     TREE_OPERAND (t, i) = va_arg (p, tree);
2704
2705   va_end (p);
2706   return t;
2707 }
2708 \f
2709 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2710    We do NOT enter this node in any sort of symbol table.
2711
2712    layout_decl is used to set up the decl's storage layout.
2713    Other slots are initialized to 0 or null pointers.  */
2714
2715 tree
2716 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
2717 {
2718   tree t;
2719
2720   t = make_node_stat (code PASS_MEM_STAT);
2721
2722 /*  if (type == error_mark_node)
2723     type = integer_type_node; */
2724 /* That is not done, deliberately, so that having error_mark_node
2725    as the type can suppress useless errors in the use of this variable.  */
2726
2727   DECL_NAME (t) = name;
2728   TREE_TYPE (t) = type;
2729
2730   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2731     layout_decl (t, 0);
2732   else if (code == FUNCTION_DECL)
2733     DECL_MODE (t) = FUNCTION_MODE;
2734
2735   return t;
2736 }
2737 \f
2738 /* BLOCK nodes are used to represent the structure of binding contours
2739    and declarations, once those contours have been exited and their contents
2740    compiled.  This information is used for outputting debugging info.  */
2741
2742 tree
2743 build_block (tree vars, tree tags ATTRIBUTE_UNUSED, tree subblocks,
2744              tree supercontext, tree chain)
2745 {
2746   tree block = make_node (BLOCK);
2747
2748   BLOCK_VARS (block) = vars;
2749   BLOCK_SUBBLOCKS (block) = subblocks;
2750   BLOCK_SUPERCONTEXT (block) = supercontext;
2751   BLOCK_CHAIN (block) = chain;
2752   return block;
2753 }
2754
2755 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
2756 /* ??? gengtype doesn't handle conditionals */
2757 static GTY(()) tree last_annotated_node;
2758 #endif
2759
2760 #ifdef USE_MAPPED_LOCATION
2761
2762 expanded_location
2763 expand_location (source_location loc)
2764 {
2765   expanded_location xloc;
2766   if (loc == 0) { xloc.file = NULL; xloc.line = 0; }
2767   else
2768     {
2769       const struct line_map *map = linemap_lookup (&line_table, loc);
2770       xloc.file = map->to_file;
2771       xloc.line = SOURCE_LINE (map, loc);
2772     };
2773   return xloc;
2774 }
2775
2776 #else
2777
2778 /* Record the exact location where an expression or an identifier were
2779    encountered.  */
2780
2781 void
2782 annotate_with_file_line (tree node, const char *file, int line)
2783 {
2784   /* Roughly one percent of the calls to this function are to annotate
2785      a node with the same information already attached to that node!
2786      Just return instead of wasting memory.  */
2787   if (EXPR_LOCUS (node)
2788       && (EXPR_FILENAME (node) == file
2789           || ! strcmp (EXPR_FILENAME (node), file))
2790       && EXPR_LINENO (node) == line)
2791     {
2792       last_annotated_node = node;
2793       return;
2794     }
2795
2796   /* In heavily macroized code (such as GCC itself) this single
2797      entry cache can reduce the number of allocations by more
2798      than half.  */
2799   if (last_annotated_node
2800       && EXPR_LOCUS (last_annotated_node)
2801       && (EXPR_FILENAME (last_annotated_node) == file
2802           || ! strcmp (EXPR_FILENAME (last_annotated_node), file))
2803       && EXPR_LINENO (last_annotated_node) == line)
2804     {
2805       SET_EXPR_LOCUS (node, EXPR_LOCUS (last_annotated_node));
2806       return;
2807     }
2808
2809   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
2810   EXPR_LINENO (node) = line;
2811   EXPR_FILENAME (node) = file;
2812   last_annotated_node = node;
2813 }
2814
2815 void
2816 annotate_with_locus (tree node, location_t locus)
2817 {
2818   annotate_with_file_line (node, locus.file, locus.line);
2819 }
2820 #endif
2821 \f
2822 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2823    is ATTRIBUTE.  */
2824
2825 tree
2826 build_decl_attribute_variant (tree ddecl, tree attribute)
2827 {
2828   DECL_ATTRIBUTES (ddecl) = attribute;
2829   return ddecl;
2830 }
2831
2832 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2833    is ATTRIBUTE.
2834
2835    Record such modified types already made so we don't make duplicates.  */
2836
2837 tree
2838 build_type_attribute_variant (tree ttype, tree attribute)
2839 {
2840   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2841     {
2842       hashval_t hashcode = 0;
2843       tree ntype;
2844       enum tree_code code = TREE_CODE (ttype);
2845
2846       ntype = copy_node (ttype);
2847
2848       TYPE_POINTER_TO (ntype) = 0;
2849       TYPE_REFERENCE_TO (ntype) = 0;
2850       TYPE_ATTRIBUTES (ntype) = attribute;
2851
2852       /* Create a new main variant of TYPE.  */
2853       TYPE_MAIN_VARIANT (ntype) = ntype;
2854       TYPE_NEXT_VARIANT (ntype) = 0;
2855       set_type_quals (ntype, TYPE_UNQUALIFIED);
2856
2857       hashcode = iterative_hash_object (code, hashcode);
2858       if (TREE_TYPE (ntype))
2859         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
2860                                           hashcode);
2861       hashcode = attribute_hash_list (attribute, hashcode);
2862
2863       switch (TREE_CODE (ntype))
2864         {
2865         case FUNCTION_TYPE:
2866           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
2867           break;
2868         case ARRAY_TYPE:
2869           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
2870                                             hashcode);
2871           break;
2872         case INTEGER_TYPE:
2873           hashcode = iterative_hash_object
2874             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
2875           hashcode = iterative_hash_object
2876             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
2877           break;
2878         case REAL_TYPE:
2879           {
2880             unsigned int precision = TYPE_PRECISION (ntype);
2881             hashcode = iterative_hash_object (precision, hashcode);
2882           }
2883           break;
2884         default:
2885           break;
2886         }
2887
2888       ntype = type_hash_canon (hashcode, ntype);
2889       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
2890     }
2891
2892   return ttype;
2893 }
2894
2895 /* Return nonzero if IDENT is a valid name for attribute ATTR,
2896    or zero if not.
2897
2898    We try both `text' and `__text__', ATTR may be either one.  */
2899 /* ??? It might be a reasonable simplification to require ATTR to be only
2900    `text'.  One might then also require attribute lists to be stored in
2901    their canonicalized form.  */
2902
2903 int
2904 is_attribute_p (const char *attr, tree ident)
2905 {
2906   int ident_len, attr_len;
2907   const char *p;
2908
2909   if (TREE_CODE (ident) != IDENTIFIER_NODE)
2910     return 0;
2911
2912   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
2913     return 1;
2914
2915   p = IDENTIFIER_POINTER (ident);
2916   ident_len = strlen (p);
2917   attr_len = strlen (attr);
2918
2919   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
2920   if (attr[0] == '_')
2921     {
2922       if (attr[1] != '_'
2923           || attr[attr_len - 2] != '_'
2924           || attr[attr_len - 1] != '_')
2925         abort ();
2926       if (ident_len == attr_len - 4
2927           && strncmp (attr + 2, p, attr_len - 4) == 0)
2928         return 1;
2929     }
2930   else
2931     {
2932       if (ident_len == attr_len + 4
2933           && p[0] == '_' && p[1] == '_'
2934           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
2935           && strncmp (attr, p + 2, attr_len) == 0)
2936         return 1;
2937     }
2938
2939   return 0;
2940 }
2941
2942 /* Given an attribute name and a list of attributes, return a pointer to the
2943    attribute's list element if the attribute is part of the list, or NULL_TREE
2944    if not found.  If the attribute appears more than once, this only
2945    returns the first occurrence; the TREE_CHAIN of the return value should
2946    be passed back in if further occurrences are wanted.  */
2947
2948 tree
2949 lookup_attribute (const char *attr_name, tree list)
2950 {
2951   tree l;
2952
2953   for (l = list; l; l = TREE_CHAIN (l))
2954     {
2955       if (TREE_CODE (TREE_PURPOSE (l)) != IDENTIFIER_NODE)
2956         abort ();
2957       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
2958         return l;
2959     }
2960
2961   return NULL_TREE;
2962 }
2963
2964 /* Return an attribute list that is the union of a1 and a2.  */
2965
2966 tree
2967 merge_attributes (tree a1, tree a2)
2968 {
2969   tree attributes;
2970
2971   /* Either one unset?  Take the set one.  */
2972
2973   if ((attributes = a1) == 0)
2974     attributes = a2;
2975
2976   /* One that completely contains the other?  Take it.  */
2977
2978   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
2979     {
2980       if (attribute_list_contained (a2, a1))
2981         attributes = a2;
2982       else
2983         {
2984           /* Pick the longest list, and hang on the other list.  */
2985
2986           if (list_length (a1) < list_length (a2))
2987             attributes = a2, a2 = a1;
2988
2989           for (; a2 != 0; a2 = TREE_CHAIN (a2))
2990             {
2991               tree a;
2992               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2993                                          attributes);
2994                    a != NULL_TREE;
2995                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
2996                                          TREE_CHAIN (a)))
2997                 {
2998                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
2999                     break;
3000                 }
3001               if (a == NULL_TREE)
3002                 {
3003                   a1 = copy_node (a2);
3004                   TREE_CHAIN (a1) = attributes;
3005                   attributes = a1;
3006                 }
3007             }
3008         }
3009     }
3010   return attributes;
3011 }
3012
3013 /* Given types T1 and T2, merge their attributes and return
3014   the result.  */
3015
3016 tree
3017 merge_type_attributes (tree t1, tree t2)
3018 {
3019   return merge_attributes (TYPE_ATTRIBUTES (t1),
3020                            TYPE_ATTRIBUTES (t2));
3021 }
3022
3023 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3024    the result.  */
3025
3026 tree
3027 merge_decl_attributes (tree olddecl, tree newdecl)
3028 {
3029   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3030                            DECL_ATTRIBUTES (newdecl));
3031 }
3032
3033 #ifdef TARGET_DLLIMPORT_DECL_ATTRIBUTES
3034
3035 /* Specialization of merge_decl_attributes for various Windows targets.
3036
3037    This handles the following situation:
3038
3039      __declspec (dllimport) int foo;
3040      int foo;
3041
3042    The second instance of `foo' nullifies the dllimport.  */
3043
3044 tree
3045 merge_dllimport_decl_attributes (tree old, tree new)
3046 {
3047   tree a;
3048   int delete_dllimport_p;
3049
3050   old = DECL_ATTRIBUTES (old);
3051   new = DECL_ATTRIBUTES (new);
3052
3053   /* What we need to do here is remove from `old' dllimport if it doesn't
3054      appear in `new'.  dllimport behaves like extern: if a declaration is
3055      marked dllimport and a definition appears later, then the object
3056      is not dllimport'd.  */
3057   if (lookup_attribute ("dllimport", old) != NULL_TREE
3058       && lookup_attribute ("dllimport", new) == NULL_TREE)
3059     delete_dllimport_p = 1;
3060   else
3061     delete_dllimport_p = 0;
3062
3063   a = merge_attributes (old, new);
3064
3065   if (delete_dllimport_p)
3066     {
3067       tree prev, t;
3068
3069       /* Scan the list for dllimport and delete it.  */
3070       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3071         {
3072           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
3073             {
3074               if (prev == NULL_TREE)
3075                 a = TREE_CHAIN (a);
3076               else
3077                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3078               break;
3079             }
3080         }
3081     }
3082
3083   return a;
3084 }
3085
3086 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3087 \f
3088 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3089    of the various TYPE_QUAL values.  */
3090
3091 static void
3092 set_type_quals (tree type, int type_quals)
3093 {
3094   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3095   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3096   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3097 }
3098
3099 /* Returns true iff cand is equivalent to base with type_quals.  */
3100
3101 bool
3102 check_qualified_type (tree cand, tree base, int type_quals)
3103 {
3104   return (TYPE_QUALS (cand) == type_quals
3105           && TYPE_NAME (cand) == TYPE_NAME (base)
3106           /* Apparently this is needed for Objective-C.  */
3107           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3108           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3109                                    TYPE_ATTRIBUTES (base)));
3110 }
3111
3112 /* Return a version of the TYPE, qualified as indicated by the
3113    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3114    return NULL_TREE.  */
3115
3116 tree
3117 get_qualified_type (tree type, int type_quals)
3118 {
3119   tree t;
3120
3121   if (TYPE_QUALS (type) == type_quals)
3122     return type;
3123
3124   /* Search the chain of variants to see if there is already one there just
3125      like the one we need to have.  If so, use that existing one.  We must
3126      preserve the TYPE_NAME, since there is code that depends on this.  */
3127   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3128     if (check_qualified_type (t, type, type_quals))
3129       return t;
3130
3131   return NULL_TREE;
3132 }
3133
3134 /* Like get_qualified_type, but creates the type if it does not
3135    exist.  This function never returns NULL_TREE.  */
3136
3137 tree
3138 build_qualified_type (tree type, int type_quals)
3139 {
3140   tree t;
3141
3142   /* See if we already have the appropriate qualified variant.  */
3143   t = get_qualified_type (type, type_quals);
3144
3145   /* If not, build it.  */
3146   if (!t)
3147     {
3148       t = build_type_copy (type);
3149       set_type_quals (t, type_quals);
3150     }
3151
3152   return t;
3153 }
3154
3155 /* Create a new variant of TYPE, equivalent but distinct.
3156    This is so the caller can modify it.  */
3157
3158 tree
3159 build_type_copy (tree type)
3160 {
3161   tree t, m = TYPE_MAIN_VARIANT (type);
3162
3163   t = copy_node (type);
3164
3165   TYPE_POINTER_TO (t) = 0;
3166   TYPE_REFERENCE_TO (t) = 0;
3167
3168   /* Add this type to the chain of variants of TYPE.  */
3169   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3170   TYPE_NEXT_VARIANT (m) = t;
3171
3172   return t;
3173 }
3174 \f
3175 /* Hashing of types so that we don't make duplicates.
3176    The entry point is `type_hash_canon'.  */
3177
3178 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3179    with types in the TREE_VALUE slots), by adding the hash codes
3180    of the individual types.  */
3181
3182 unsigned int
3183 type_hash_list (tree list, hashval_t hashcode)
3184 {
3185   tree tail;
3186
3187   for (tail = list; tail; tail = TREE_CHAIN (tail))
3188     if (TREE_VALUE (tail) != error_mark_node)
3189       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3190                                         hashcode);
3191
3192   return hashcode;
3193 }
3194
3195 /* These are the Hashtable callback functions.  */
3196
3197 /* Returns true iff the types are equivalent.  */
3198
3199 static int
3200 type_hash_eq (const void *va, const void *vb)
3201 {
3202   const struct type_hash *a = va, *b = vb;
3203
3204   /* First test the things that are the same for all types.  */
3205   if (a->hash != b->hash
3206       || TREE_CODE (a->type) != TREE_CODE (b->type)
3207       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
3208       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3209                                  TYPE_ATTRIBUTES (b->type))
3210       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
3211       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
3212     return 0;
3213
3214   switch (TREE_CODE (a->type))
3215     {
3216     case VOID_TYPE:
3217     case COMPLEX_TYPE:
3218     case VECTOR_TYPE:
3219     case POINTER_TYPE:
3220     case REFERENCE_TYPE:
3221       return 1;
3222
3223     case ENUMERAL_TYPE:
3224       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
3225           && !(TYPE_VALUES (a->type)
3226                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
3227                && TYPE_VALUES (b->type)
3228                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
3229                && type_list_equal (TYPE_VALUES (a->type),
3230                                    TYPE_VALUES (b->type))))
3231         return 0;
3232
3233       /* ... fall through ... */
3234
3235     case INTEGER_TYPE:
3236     case REAL_TYPE:
3237     case BOOLEAN_TYPE:
3238     case CHAR_TYPE:
3239       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3240                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3241                                       TYPE_MAX_VALUE (b->type)))
3242               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3243                   && tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3244                                          TYPE_MIN_VALUE (b->type))));
3245
3246     case OFFSET_TYPE:
3247       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
3248
3249     case METHOD_TYPE:
3250       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
3251               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3252                   || (TYPE_ARG_TYPES (a->type)
3253                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3254                       && TYPE_ARG_TYPES (b->type)
3255                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3256                       && type_list_equal (TYPE_ARG_TYPES (a->type),
3257                                           TYPE_ARG_TYPES (b->type)))));
3258
3259     case ARRAY_TYPE:
3260     case SET_TYPE:
3261       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
3262
3263     case RECORD_TYPE:
3264     case UNION_TYPE:
3265     case QUAL_UNION_TYPE:
3266       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
3267               || (TYPE_FIELDS (a->type)
3268                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
3269                   && TYPE_FIELDS (b->type)
3270                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
3271                   && type_list_equal (TYPE_FIELDS (a->type),
3272                                       TYPE_FIELDS (b->type))));
3273
3274     case FUNCTION_TYPE:
3275       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3276               || (TYPE_ARG_TYPES (a->type)
3277                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3278                   && TYPE_ARG_TYPES (b->type)
3279                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3280                   && type_list_equal (TYPE_ARG_TYPES (a->type),
3281                                       TYPE_ARG_TYPES (b->type))));
3282
3283     default:
3284       return 0;
3285     }
3286 }
3287
3288 /* Return the cached hash value.  */
3289
3290 static hashval_t
3291 type_hash_hash (const void *item)
3292 {
3293   return ((const struct type_hash *) item)->hash;
3294 }
3295
3296 /* Look in the type hash table for a type isomorphic to TYPE.
3297    If one is found, return it.  Otherwise return 0.  */
3298
3299 tree
3300 type_hash_lookup (hashval_t hashcode, tree type)
3301 {
3302   struct type_hash *h, in;
3303
3304   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3305      must call that routine before comparing TYPE_ALIGNs.  */
3306   layout_type (type);
3307
3308   in.hash = hashcode;
3309   in.type = type;
3310
3311   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3312   if (h)
3313     return h->type;
3314   return NULL_TREE;
3315 }
3316
3317 /* Add an entry to the type-hash-table
3318    for a type TYPE whose hash code is HASHCODE.  */
3319
3320 void
3321 type_hash_add (hashval_t hashcode, tree type)
3322 {
3323   struct type_hash *h;
3324   void **loc;
3325
3326   h = ggc_alloc (sizeof (struct type_hash));
3327   h->hash = hashcode;
3328   h->type = type;
3329   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3330   *(struct type_hash **) loc = h;
3331 }
3332
3333 /* Given TYPE, and HASHCODE its hash code, return the canonical
3334    object for an identical type if one already exists.
3335    Otherwise, return TYPE, and record it as the canonical object.
3336
3337    To use this function, first create a type of the sort you want.
3338    Then compute its hash code from the fields of the type that
3339    make it different from other similar types.
3340    Then call this function and use the value.  */
3341
3342 tree
3343 type_hash_canon (unsigned int hashcode, tree type)
3344 {
3345   tree t1;
3346
3347   /* The hash table only contains main variants, so ensure that's what we're
3348      being passed.  */
3349   if (TYPE_MAIN_VARIANT (type) != type)
3350     abort ();
3351
3352   if (!lang_hooks.types.hash_types)
3353     return type;
3354
3355   /* See if the type is in the hash table already.  If so, return it.
3356      Otherwise, add the type.  */
3357   t1 = type_hash_lookup (hashcode, type);
3358   if (t1 != 0)
3359     {
3360 #ifdef GATHER_STATISTICS
3361       tree_node_counts[(int) t_kind]--;
3362       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3363 #endif
3364       return t1;
3365     }
3366   else
3367     {
3368       type_hash_add (hashcode, type);
3369       return type;
3370     }
3371 }
3372
3373 /* See if the data pointed to by the type hash table is marked.  We consider
3374    it marked if the type is marked or if a debug type number or symbol
3375    table entry has been made for the type.  This reduces the amount of
3376    debugging output and eliminates that dependency of the debug output on
3377    the number of garbage collections.  */
3378
3379 static int
3380 type_hash_marked_p (const void *p)
3381 {
3382   tree type = ((struct type_hash *) p)->type;
3383
3384   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3385 }
3386
3387 static void
3388 print_type_hash_statistics (void)
3389 {
3390   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3391            (long) htab_size (type_hash_table),
3392            (long) htab_elements (type_hash_table),
3393            htab_collisions (type_hash_table));
3394 }
3395
3396 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3397    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3398    by adding the hash codes of the individual attributes.  */
3399
3400 unsigned int
3401 attribute_hash_list (tree list, hashval_t hashcode)
3402 {
3403   tree tail;
3404
3405   for (tail = list; tail; tail = TREE_CHAIN (tail))
3406     /* ??? Do we want to add in TREE_VALUE too? */
3407     hashcode = iterative_hash_object
3408       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
3409   return hashcode;
3410 }
3411
3412 /* Given two lists of attributes, return true if list l2 is
3413    equivalent to l1.  */
3414
3415 int
3416 attribute_list_equal (tree l1, tree l2)
3417 {
3418   return attribute_list_contained (l1, l2)
3419          && attribute_list_contained (l2, l1);
3420 }
3421
3422 /* Given two lists of attributes, return true if list L2 is
3423    completely contained within L1.  */
3424 /* ??? This would be faster if attribute names were stored in a canonicalized
3425    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3426    must be used to show these elements are equivalent (which they are).  */
3427 /* ??? It's not clear that attributes with arguments will always be handled
3428    correctly.  */
3429
3430 int
3431 attribute_list_contained (tree l1, tree l2)
3432 {
3433   tree t1, t2;
3434
3435   /* First check the obvious, maybe the lists are identical.  */
3436   if (l1 == l2)
3437     return 1;
3438
3439   /* Maybe the lists are similar.  */
3440   for (t1 = l1, t2 = l2;
3441        t1 != 0 && t2 != 0
3442         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3443         && TREE_VALUE (t1) == TREE_VALUE (t2);
3444        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3445
3446   /* Maybe the lists are equal.  */
3447   if (t1 == 0 && t2 == 0)
3448     return 1;
3449
3450   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3451     {
3452       tree attr;
3453       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3454            attr != NULL_TREE;
3455            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3456                                     TREE_CHAIN (attr)))
3457         {
3458           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3459             break;
3460         }
3461
3462       if (attr == 0)
3463         return 0;
3464
3465       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3466         return 0;
3467     }
3468
3469   return 1;
3470 }
3471
3472 /* Given two lists of types
3473    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3474    return 1 if the lists contain the same types in the same order.
3475    Also, the TREE_PURPOSEs must match.  */
3476
3477 int
3478 type_list_equal (tree l1, tree l2)
3479 {
3480   tree t1, t2;
3481
3482   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3483     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3484         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3485             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3486                   && (TREE_TYPE (TREE_PURPOSE (t1))
3487                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3488       return 0;
3489
3490   return t1 == t2;
3491 }
3492
3493 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3494    given by TYPE.  If the argument list accepts variable arguments,
3495    then this function counts only the ordinary arguments.  */
3496
3497 int
3498 type_num_arguments (tree type)
3499 {
3500   int i = 0;
3501   tree t;
3502
3503   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3504     /* If the function does not take a variable number of arguments,
3505        the last element in the list will have type `void'.  */
3506     if (VOID_TYPE_P (TREE_VALUE (t)))
3507       break;
3508     else
3509       ++i;
3510
3511   return i;
3512 }
3513
3514 /* Nonzero if integer constants T1 and T2
3515    represent the same constant value.  */
3516
3517 int
3518 tree_int_cst_equal (tree t1, tree t2)
3519 {
3520   if (t1 == t2)
3521     return 1;
3522
3523   if (t1 == 0 || t2 == 0)
3524     return 0;
3525
3526   if (TREE_CODE (t1) == INTEGER_CST
3527       && TREE_CODE (t2) == INTEGER_CST
3528       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3529       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3530     return 1;
3531
3532   return 0;
3533 }
3534
3535 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3536    The precise way of comparison depends on their data type.  */
3537
3538 int
3539 tree_int_cst_lt (tree t1, tree t2)
3540 {
3541   if (t1 == t2)
3542     return 0;
3543
3544   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
3545     {
3546       int t1_sgn = tree_int_cst_sgn (t1);
3547       int t2_sgn = tree_int_cst_sgn (t2);
3548
3549       if (t1_sgn < t2_sgn)
3550         return 1;
3551       else if (t1_sgn > t2_sgn)
3552         return 0;
3553       /* Otherwise, both are non-negative, so we compare them as
3554          unsigned just in case one of them would overflow a signed
3555          type.  */
3556     }
3557   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
3558     return INT_CST_LT (t1, t2);
3559
3560   return INT_CST_LT_UNSIGNED (t1, t2);
3561 }
3562
3563 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3564
3565 int
3566 tree_int_cst_compare (tree t1, tree t2)
3567 {
3568   if (tree_int_cst_lt (t1, t2))
3569     return -1;
3570   else if (tree_int_cst_lt (t2, t1))
3571     return 1;
3572   else
3573     return 0;
3574 }
3575
3576 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
3577    the host.  If POS is zero, the value can be represented in a single
3578    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
3579    be represented in a single unsigned HOST_WIDE_INT.  */
3580
3581 int
3582 host_integerp (tree t, int pos)
3583 {
3584   return (TREE_CODE (t) == INTEGER_CST
3585           && ! TREE_OVERFLOW (t)
3586           && ((TREE_INT_CST_HIGH (t) == 0
3587                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3588               || (! pos && TREE_INT_CST_HIGH (t) == -1
3589                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
3590                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
3591               || (pos && TREE_INT_CST_HIGH (t) == 0)));
3592 }
3593
3594 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3595    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3596    be positive.  Abort if we cannot satisfy the above conditions.  */
3597
3598 HOST_WIDE_INT
3599 tree_low_cst (tree t, int pos)
3600 {
3601   if (host_integerp (t, pos))
3602     return TREE_INT_CST_LOW (t);
3603   else
3604     abort ();
3605 }
3606
3607 /* Return the most significant bit of the integer constant T.  */
3608
3609 int
3610 tree_int_cst_msb (tree t)
3611 {
3612   int prec;
3613   HOST_WIDE_INT h;
3614   unsigned HOST_WIDE_INT l;
3615
3616   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3617      actual bits, not the (arbitrary) range of the type.  */
3618   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3619   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3620                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3621   return (l & 1) == 1;
3622 }
3623
3624 /* Return an indication of the sign of the integer constant T.
3625    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3626    Note that -1 will never be returned it T's type is unsigned.  */
3627
3628 int
3629 tree_int_cst_sgn (tree t)
3630 {
3631   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3632     return 0;
3633   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
3634     return 1;
3635   else if (TREE_INT_CST_HIGH (t) < 0)
3636     return -1;
3637   else
3638     return 1;
3639 }
3640
3641 /* Compare two constructor-element-type constants.  Return 1 if the lists
3642    are known to be equal; otherwise return 0.  */
3643
3644 int
3645 simple_cst_list_equal (tree l1, tree l2)
3646 {
3647   while (l1 != NULL_TREE && l2 != NULL_TREE)
3648     {
3649       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3650         return 0;
3651
3652       l1 = TREE_CHAIN (l1);
3653       l2 = TREE_CHAIN (l2);
3654     }
3655
3656   return l1 == l2;
3657 }
3658
3659 /* Return truthvalue of whether T1 is the same tree structure as T2.
3660    Return 1 if they are the same.
3661    Return 0 if they are understandably different.
3662    Return -1 if either contains tree structure not understood by
3663    this function.  */
3664
3665 int
3666 simple_cst_equal (tree t1, tree t2)
3667 {
3668   enum tree_code code1, code2;
3669   int cmp;
3670   int i;
3671
3672   if (t1 == t2)
3673     return 1;
3674   if (t1 == 0 || t2 == 0)
3675     return 0;
3676
3677   code1 = TREE_CODE (t1);
3678   code2 = TREE_CODE (t2);
3679
3680   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3681     {
3682       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3683           || code2 == NON_LVALUE_EXPR)
3684         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3685       else
3686         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3687     }
3688
3689   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3690            || code2 == NON_LVALUE_EXPR)
3691     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3692
3693   if (code1 != code2)
3694     return 0;
3695
3696   switch (code1)
3697     {
3698     case INTEGER_CST:
3699       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3700               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3701
3702     case REAL_CST:
3703       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3704
3705     case STRING_CST:
3706       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3707               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3708                          TREE_STRING_LENGTH (t1)));
3709
3710     case CONSTRUCTOR:
3711       return simple_cst_list_equal (CONSTRUCTOR_ELTS (t1),
3712                                     CONSTRUCTOR_ELTS (t2));
3713
3714     case SAVE_EXPR:
3715       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3716
3717     case CALL_EXPR:
3718       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3719       if (cmp <= 0)
3720         return cmp;
3721       return
3722         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3723
3724     case TARGET_EXPR:
3725       /* Special case: if either target is an unallocated VAR_DECL,
3726          it means that it's going to be unified with whatever the
3727          TARGET_EXPR is really supposed to initialize, so treat it
3728          as being equivalent to anything.  */
3729       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3730            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3731            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3732           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3733               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3734               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3735         cmp = 1;
3736       else
3737         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3738
3739       if (cmp <= 0)
3740         return cmp;
3741
3742       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3743
3744     case WITH_CLEANUP_EXPR:
3745       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3746       if (cmp <= 0)
3747         return cmp;
3748
3749       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3750
3751     case COMPONENT_REF:
3752       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3753         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3754
3755       return 0;
3756
3757     case VAR_DECL:
3758     case PARM_DECL:
3759     case CONST_DECL:
3760     case FUNCTION_DECL:
3761       return 0;
3762
3763     default:
3764       break;
3765     }
3766
3767   /* This general rule works for most tree codes.  All exceptions should be
3768      handled above.  If this is a language-specific tree code, we can't
3769      trust what might be in the operand, so say we don't know
3770      the situation.  */
3771   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3772     return -1;
3773
3774   switch (TREE_CODE_CLASS (code1))
3775     {
3776     case '1':
3777     case '2':
3778     case '<':
3779     case 'e':
3780     case 'r':
3781     case 's':
3782       cmp = 1;
3783       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3784         {
3785           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3786           if (cmp <= 0)
3787             return cmp;
3788         }
3789
3790       return cmp;
3791
3792     default:
3793       return -1;
3794     }
3795 }
3796
3797 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
3798    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
3799    than U, respectively.  */
3800
3801 int
3802 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
3803 {
3804   if (tree_int_cst_sgn (t) < 0)
3805     return -1;
3806   else if (TREE_INT_CST_HIGH (t) != 0)
3807     return 1;
3808   else if (TREE_INT_CST_LOW (t) == u)
3809     return 0;
3810   else if (TREE_INT_CST_LOW (t) < u)
3811     return -1;
3812   else
3813     return 1;
3814 }
3815
3816 /* Return true if CODE represents an associative tree code.  Otherwise
3817    return false.  */
3818 bool
3819 associative_tree_code (enum tree_code code)
3820 {
3821   switch (code)
3822     {
3823     case BIT_IOR_EXPR:
3824     case BIT_AND_EXPR:
3825     case BIT_XOR_EXPR:
3826     case PLUS_EXPR:
3827     case MULT_EXPR:
3828     case MIN_EXPR:
3829     case MAX_EXPR:
3830       return true;
3831
3832     default:
3833       break;
3834     }
3835   return false;
3836 }
3837
3838 /* Return true if CODE represents an commutative tree code.  Otherwise
3839    return false.  */
3840 bool
3841 commutative_tree_code (enum tree_code code)
3842 {
3843   switch (code)
3844     {
3845     case PLUS_EXPR:
3846     case MULT_EXPR:
3847     case MIN_EXPR:
3848     case MAX_EXPR:
3849     case BIT_IOR_EXPR:
3850     case BIT_XOR_EXPR:
3851     case BIT_AND_EXPR:
3852     case NE_EXPR:
3853     case EQ_EXPR:
3854     case UNORDERED_EXPR:
3855     case ORDERED_EXPR:
3856     case UNEQ_EXPR:
3857     case LTGT_EXPR:
3858     case TRUTH_AND_EXPR:
3859     case TRUTH_XOR_EXPR:
3860     case TRUTH_OR_EXPR:
3861       return true;
3862
3863     default:
3864       break;
3865     }
3866   return false;
3867 }
3868
3869 /* Generate a hash value for an expression.  This can be used iteratively
3870    by passing a previous result as the "val" argument.
3871
3872    This function is intended to produce the same hash for expressions which
3873    would compare equal using operand_equal_p.  */
3874
3875 hashval_t
3876 iterative_hash_expr (tree t, hashval_t val)
3877 {
3878   int i;
3879   enum tree_code code;
3880   char class;
3881
3882   if (t == NULL_TREE)
3883     return iterative_hash_object (t, val);
3884
3885   code = TREE_CODE (t);
3886   class = TREE_CODE_CLASS (code);
3887
3888   if (class == 'd'
3889       || TREE_CODE (t) == VALUE_HANDLE)
3890     {
3891       /* Decls we can just compare by pointer.  */
3892       val = iterative_hash_object (t, val);
3893     }
3894   else if (class == 'c')
3895     {
3896       /* Alas, constants aren't shared, so we can't rely on pointer
3897          identity.  */
3898       if (code == INTEGER_CST)
3899         {
3900           val = iterative_hash_object (TREE_INT_CST_LOW (t), val);
3901           val = iterative_hash_object (TREE_INT_CST_HIGH (t), val);
3902         }
3903       else if (code == REAL_CST)
3904         {
3905           unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
3906
3907           val = iterative_hash (&val2, sizeof (unsigned int), val);
3908         }
3909       else if (code == STRING_CST)
3910         val = iterative_hash (TREE_STRING_POINTER (t),
3911                               TREE_STRING_LENGTH (t), val);
3912       else if (code == COMPLEX_CST)
3913         {
3914           val = iterative_hash_expr (TREE_REALPART (t), val);
3915           val = iterative_hash_expr (TREE_IMAGPART (t), val);
3916         }
3917       else if (code == VECTOR_CST)
3918         val = iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
3919       else
3920         abort ();
3921     }
3922   else if (IS_EXPR_CODE_CLASS (class))
3923     {
3924       val = iterative_hash_object (code, val);
3925
3926       /* Don't hash the type, that can lead to having nodes which
3927          compare equal according to operand_equal_p, but which
3928          have different hash codes.  */
3929       if (code == NOP_EXPR
3930           || code == CONVERT_EXPR
3931           || code == NON_LVALUE_EXPR)
3932         {
3933           /* Make sure to include signness in the hash computation.  */
3934           val += TYPE_UNSIGNED (TREE_TYPE (t));
3935           val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
3936         }
3937
3938       if (commutative_tree_code (code))
3939         {
3940           /* It's a commutative expression.  We want to hash it the same
3941              however it appears.  We do this by first hashing both operands
3942              and then rehashing based on the order of their independent
3943              hashes.  */
3944           hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
3945           hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
3946           hashval_t t;
3947
3948           if (one > two)
3949             t = one, one = two, two = t;
3950
3951           val = iterative_hash_object (one, val);
3952           val = iterative_hash_object (two, val);
3953         }
3954       else
3955         for (i = first_rtl_op (code) - 1; i >= 0; --i)
3956           val = iterative_hash_expr (TREE_OPERAND (t, i), val);
3957     }
3958   else if (code == TREE_LIST)
3959     {
3960       /* A list of expressions, for a CALL_EXPR or as the elements of a
3961          VECTOR_CST.  */
3962       for (; t; t = TREE_CHAIN (t))
3963         val = iterative_hash_expr (TREE_VALUE (t), val);
3964     }
3965   else if (code == SSA_NAME)
3966     {
3967       val = iterative_hash_object (SSA_NAME_VERSION (t), val);
3968       val = iterative_hash_expr (SSA_NAME_VAR (t), val);
3969     }
3970   else
3971     abort ();
3972
3973   return val;
3974 }
3975 \f
3976 /* Constructors for pointer, array and function types.
3977    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
3978    constructed by language-dependent code, not here.)  */
3979
3980 /* Construct, lay out and return the type of pointers to TO_TYPE with
3981    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
3982    reference all of memory. If such a type has already been
3983    constructed, reuse it.  */
3984
3985 tree
3986 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
3987                              bool can_alias_all)
3988 {
3989   tree t;
3990
3991   /* In some cases, languages will have things that aren't a POINTER_TYPE
3992      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
3993      In that case, return that type without regard to the rest of our
3994      operands.
3995
3996      ??? This is a kludge, but consistent with the way this function has
3997      always operated and there doesn't seem to be a good way to avoid this
3998      at the moment.  */
3999   if (TYPE_POINTER_TO (to_type) != 0
4000       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4001     return TYPE_POINTER_TO (to_type);
4002
4003   /* First, if we already have a type for pointers to TO_TYPE and it's
4004      the proper mode, use it.  */
4005   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4006     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4007       return t;
4008
4009   t = make_node (POINTER_TYPE);
4010
4011   TREE_TYPE (t) = to_type;
4012   TYPE_MODE (t) = mode;
4013   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4014   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4015   TYPE_POINTER_TO (to_type) = t;
4016
4017   /* Lay out the type.  This function has many callers that are concerned
4018      with expression-construction, and this simplifies them all.  */
4019   layout_type (t);
4020
4021   return t;
4022 }
4023
4024 /* By default build pointers in ptr_mode.  */
4025
4026 tree
4027 build_pointer_type (tree to_type)
4028 {
4029   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4030 }
4031
4032 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4033
4034 tree
4035 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4036                                bool can_alias_all)
4037 {
4038   tree t;
4039
4040   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4041      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4042      In that case, return that type without regard to the rest of our
4043      operands.
4044
4045      ??? This is a kludge, but consistent with the way this function has
4046      always operated and there doesn't seem to be a good way to avoid this
4047      at the moment.  */
4048   if (TYPE_REFERENCE_TO (to_type) != 0
4049       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4050     return TYPE_REFERENCE_TO (to_type);
4051
4052   /* First, if we already have a type for pointers to TO_TYPE and it's
4053      the proper mode, use it.  */
4054   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4055     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4056       return t;
4057
4058   t = make_node (REFERENCE_TYPE);
4059
4060   TREE_TYPE (t) = to_type;
4061   TYPE_MODE (t) = mode;
4062   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4063   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4064   TYPE_REFERENCE_TO (to_type) = t;
4065
4066   layout_type (t);
4067
4068   return t;
4069 }
4070
4071
4072 /* Build the node for the type of references-to-TO_TYPE by default
4073    in ptr_mode.  */
4074
4075 tree
4076 build_reference_type (tree to_type)
4077 {
4078   return build_reference_type_for_mode (to_type, ptr_mode, false);
4079 }
4080
4081 /* Build a type that is compatible with t but has no cv quals anywhere
4082    in its type, thus
4083
4084    const char *const *const *  ->  char ***.  */
4085
4086 tree
4087 build_type_no_quals (tree t)
4088 {
4089   switch (TREE_CODE (t))
4090     {
4091     case POINTER_TYPE:
4092       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4093                                           TYPE_MODE (t),
4094                                           TYPE_REF_CAN_ALIAS_ALL (t));
4095     case REFERENCE_TYPE:
4096       return
4097         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4098                                        TYPE_MODE (t),
4099                                        TYPE_REF_CAN_ALIAS_ALL (t));
4100     default:
4101       return TYPE_MAIN_VARIANT (t);
4102     }
4103 }
4104
4105 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4106    MAXVAL should be the maximum value in the domain
4107    (one less than the length of the array).
4108
4109    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4110    We don't enforce this limit, that is up to caller (e.g. language front end).
4111    The limit exists because the result is a signed type and we don't handle
4112    sizes that use more than one HOST_WIDE_INT.  */
4113
4114 tree
4115 build_index_type (tree maxval)
4116 {
4117   tree itype = make_node (INTEGER_TYPE);
4118
4119   TREE_TYPE (itype) = sizetype;
4120   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4121   TYPE_MIN_VALUE (itype) = size_zero_node;
4122   TYPE_MAX_VALUE (itype) = convert (sizetype, maxval);
4123   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4124   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4125   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4126   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4127   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4128
4129   if (host_integerp (maxval, 1))
4130     return type_hash_canon (tree_low_cst (maxval, 1), itype);
4131   else
4132     return itype;
4133 }
4134
4135 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
4136    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
4137    low bound LOWVAL and high bound HIGHVAL.
4138    if TYPE==NULL_TREE, sizetype is used.  */
4139
4140 tree
4141 build_range_type (tree type, tree lowval, tree highval)
4142 {
4143   tree itype = make_node (INTEGER_TYPE);
4144
4145   TREE_TYPE (itype) = type;
4146   if (type == NULL_TREE)
4147     type = sizetype;
4148
4149   TYPE_MIN_VALUE (itype) = convert (type, lowval);
4150   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
4151
4152   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
4153   TYPE_MODE (itype) = TYPE_MODE (type);
4154   TYPE_SIZE (itype) = TYPE_SIZE (type);
4155   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
4156   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
4157   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
4158
4159   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
4160     return type_hash_canon (tree_low_cst (highval, 0)
4161                             - tree_low_cst (lowval, 0),
4162                             itype);
4163   else
4164     return itype;
4165 }
4166
4167 /* Just like build_index_type, but takes lowval and highval instead
4168    of just highval (maxval).  */
4169
4170 tree
4171 build_index_2_type (tree lowval, tree highval)
4172 {
4173   return build_range_type (sizetype, lowval, highval);
4174 }
4175
4176 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
4177    and number of elements specified by the range of values of INDEX_TYPE.
4178    If such a type has already been constructed, reuse it.  */
4179
4180 tree
4181 build_array_type (tree elt_type, tree index_type)
4182 {
4183   tree t;
4184   hashval_t hashcode = 0;
4185
4186   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
4187     {
4188       error ("arrays of functions are not meaningful");
4189       elt_type = integer_type_node;
4190     }
4191
4192   t = make_node (ARRAY_TYPE);
4193   TREE_TYPE (t) = elt_type;
4194   TYPE_DOMAIN (t) = index_type;
4195
4196   if (index_type == 0)
4197     return t;
4198
4199   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
4200   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
4201   t = type_hash_canon (hashcode, t);
4202
4203   if (!COMPLETE_TYPE_P (t))
4204     layout_type (t);
4205   return t;
4206 }
4207
4208 /* Return the TYPE of the elements comprising
4209    the innermost dimension of ARRAY.  */
4210
4211 tree
4212 get_inner_array_type (tree array)
4213 {
4214   tree type = TREE_TYPE (array);
4215
4216   while (TREE_CODE (type) == ARRAY_TYPE)
4217     type = TREE_TYPE (type);
4218
4219   return type;
4220 }
4221
4222 /* Construct, lay out and return
4223    the type of functions returning type VALUE_TYPE
4224    given arguments of types ARG_TYPES.
4225    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
4226    are data type nodes for the arguments of the function.
4227    If such a type has already been constructed, reuse it.  */
4228
4229 tree
4230 build_function_type (tree value_type, tree arg_types)
4231 {
4232   tree t;
4233   hashval_t hashcode = 0;
4234
4235   if (TREE_CODE (value_type) == FUNCTION_TYPE)
4236     {
4237       error ("function return type cannot be function");
4238       value_type = integer_type_node;
4239     }
4240
4241   /* Make a node of the sort we want.  */
4242   t = make_node (FUNCTION_TYPE);
4243   TREE_TYPE (t) = value_type;
4244   TYPE_ARG_TYPES (t) = arg_types;
4245
4246   /* If we already have such a type, use the old one.  */
4247   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
4248   hashcode = type_hash_list (arg_types, hashcode);
4249   t = type_hash_canon (hashcode, t);
4250
4251   if (!COMPLETE_TYPE_P (t))
4252     layout_type (t);
4253   return t;
4254 }
4255
4256 /* Build a function type.  The RETURN_TYPE is the type returned by the
4257    function.  If additional arguments are provided, they are
4258    additional argument types.  The list of argument types must always
4259    be terminated by NULL_TREE.  */
4260
4261 tree
4262 build_function_type_list (tree return_type, ...)
4263 {
4264   tree t, args, last;
4265   va_list p;
4266
4267   va_start (p, return_type);
4268
4269   t = va_arg (p, tree);
4270   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
4271     args = tree_cons (NULL_TREE, t, args);
4272
4273   last = args;
4274   args = nreverse (args);
4275   TREE_CHAIN (last) = void_list_node;
4276   args = build_function_type (return_type, args);
4277
4278   va_end (p);
4279   return args;
4280 }
4281
4282 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
4283    and ARGTYPES (a TREE_LIST) are the return type and arguments types
4284    for the method.  An implicit additional parameter (of type
4285    pointer-to-BASETYPE) is added to the ARGTYPES.  */
4286
4287 tree
4288 build_method_type_directly (tree basetype,
4289                             tree rettype,
4290                             tree argtypes)
4291 {
4292   tree t;
4293   tree ptype;
4294   int hashcode = 0;
4295
4296   /* Make a node of the sort we want.  */
4297   t = make_node (METHOD_TYPE);
4298
4299   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4300   TREE_TYPE (t) = rettype;
4301   ptype = build_pointer_type (basetype);
4302
4303   /* The actual arglist for this function includes a "hidden" argument
4304      which is "this".  Put it into the list of argument types.  */
4305   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
4306   TYPE_ARG_TYPES (t) = argtypes;
4307
4308   /* If we already have such a type, use the old one.  */
4309   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4310   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
4311   hashcode = type_hash_list (argtypes, hashcode);
4312   t = type_hash_canon (hashcode, t);
4313
4314   if (!COMPLETE_TYPE_P (t))
4315     layout_type (t);
4316
4317   return t;
4318 }
4319
4320 /* Construct, lay out and return the type of methods belonging to class
4321    BASETYPE and whose arguments and values are described by TYPE.
4322    If that type exists already, reuse it.
4323    TYPE must be a FUNCTION_TYPE node.  */
4324
4325 tree
4326 build_method_type (tree basetype, tree type)
4327 {
4328   if (TREE_CODE (type) != FUNCTION_TYPE)
4329     abort ();
4330
4331   return build_method_type_directly (basetype,
4332                                      TREE_TYPE (type),
4333                                      TYPE_ARG_TYPES (type));
4334 }
4335
4336 /* Construct, lay out and return the type of offsets to a value
4337    of type TYPE, within an object of type BASETYPE.
4338    If a suitable offset type exists already, reuse it.  */
4339
4340 tree
4341 build_offset_type (tree basetype, tree type)
4342 {
4343   tree t;
4344   hashval_t hashcode = 0;
4345
4346   /* Make a node of the sort we want.  */
4347   t = make_node (OFFSET_TYPE);
4348
4349   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4350   TREE_TYPE (t) = type;
4351
4352   /* If we already have such a type, use the old one.  */
4353   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4354   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
4355   t = type_hash_canon (hashcode, t);
4356
4357   if (!COMPLETE_TYPE_P (t))
4358     layout_type (t);
4359
4360   return t;
4361 }
4362
4363 /* Create a complex type whose components are COMPONENT_TYPE.  */
4364
4365 tree
4366 build_complex_type (tree component_type)
4367 {
4368   tree t;
4369   hashval_t hashcode;
4370
4371   /* Make a node of the sort we want.  */
4372   t = make_node (COMPLEX_TYPE);
4373
4374   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
4375
4376   /* If we already have such a type, use the old one.  */
4377   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
4378   t = type_hash_canon (hashcode, t);
4379
4380   if (!COMPLETE_TYPE_P (t))
4381     layout_type (t);
4382
4383   /* If we are writing Dwarf2 output we need to create a name,
4384      since complex is a fundamental type.  */
4385   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
4386       && ! TYPE_NAME (t))
4387     {
4388       const char *name;
4389       if (component_type == char_type_node)
4390         name = "complex char";
4391       else if (component_type == signed_char_type_node)
4392         name = "complex signed char";
4393       else if (component_type == unsigned_char_type_node)
4394         name = "complex unsigned char";
4395       else if (component_type == short_integer_type_node)
4396         name = "complex short int";
4397       else if (component_type == short_unsigned_type_node)
4398         name = "complex short unsigned int";
4399       else if (component_type == integer_type_node)
4400         name = "complex int";
4401       else if (component_type == unsigned_type_node)
4402         name = "complex unsigned int";
4403       else if (component_type == long_integer_type_node)
4404         name = "complex long int";
4405       else if (component_type == long_unsigned_type_node)
4406         name = "complex long unsigned int";
4407       else if (component_type == long_long_integer_type_node)
4408         name = "complex long long int";
4409       else if (component_type == long_long_unsigned_type_node)
4410         name = "complex long long unsigned int";
4411       else
4412         name = 0;
4413
4414       if (name != 0)
4415         TYPE_NAME (t) = get_identifier (name);
4416     }
4417
4418   return build_qualified_type (t, TYPE_QUALS (component_type));
4419 }
4420 \f
4421 /* Return OP, stripped of any conversions to wider types as much as is safe.
4422    Converting the value back to OP's type makes a value equivalent to OP.
4423
4424    If FOR_TYPE is nonzero, we return a value which, if converted to
4425    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
4426
4427    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
4428    narrowest type that can hold the value, even if they don't exactly fit.
4429    Otherwise, bit-field references are changed to a narrower type
4430    only if they can be fetched directly from memory in that type.
4431
4432    OP must have integer, real or enumeral type.  Pointers are not allowed!
4433
4434    There are some cases where the obvious value we could return
4435    would regenerate to OP if converted to OP's type,
4436    but would not extend like OP to wider types.
4437    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
4438    For example, if OP is (unsigned short)(signed char)-1,
4439    we avoid returning (signed char)-1 if FOR_TYPE is int,
4440    even though extending that to an unsigned short would regenerate OP,
4441    since the result of extending (signed char)-1 to (int)
4442    is different from (int) OP.  */
4443
4444 tree
4445 get_unwidened (tree op, tree for_type)
4446 {
4447   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
4448   tree type = TREE_TYPE (op);
4449   unsigned final_prec
4450     = TYPE_PRECISION (for_type != 0 ? for_type : type);
4451   int uns
4452     = (for_type != 0 && for_type != type
4453        && final_prec > TYPE_PRECISION (type)
4454        && TYPE_UNSIGNED (type));
4455   tree win = op;
4456
4457   while (TREE_CODE (op) == NOP_EXPR)
4458     {
4459       int bitschange
4460         = TYPE_PRECISION (TREE_TYPE (op))
4461           - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
4462
4463       /* Truncations are many-one so cannot be removed.
4464          Unless we are later going to truncate down even farther.  */
4465       if (bitschange < 0
4466           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
4467         break;
4468
4469       /* See what's inside this conversion.  If we decide to strip it,
4470          we will set WIN.  */
4471       op = TREE_OPERAND (op, 0);
4472
4473       /* If we have not stripped any zero-extensions (uns is 0),
4474          we can strip any kind of extension.
4475          If we have previously stripped a zero-extension,
4476          only zero-extensions can safely be stripped.
4477          Any extension can be stripped if the bits it would produce
4478          are all going to be discarded later by truncating to FOR_TYPE.  */
4479
4480       if (bitschange > 0)
4481         {
4482           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
4483             win = op;
4484           /* TYPE_UNSIGNED says whether this is a zero-extension.
4485              Let's avoid computing it if it does not affect WIN
4486              and if UNS will not be needed again.  */
4487           if ((uns || TREE_CODE (op) == NOP_EXPR)
4488               && TYPE_UNSIGNED (TREE_TYPE (op)))
4489             {
4490               uns = 1;
4491               win = op;
4492             }
4493         }
4494     }
4495
4496   if (TREE_CODE (op) == COMPONENT_REF
4497       /* Since type_for_size always gives an integer type.  */
4498       && TREE_CODE (type) != REAL_TYPE
4499       /* Don't crash if field not laid out yet.  */
4500       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4501       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4502     {
4503       unsigned int innerprec
4504         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4505       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
4506                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4507       type = lang_hooks.types.type_for_size (innerprec, unsignedp);
4508
4509       /* We can get this structure field in the narrowest type it fits in.
4510          If FOR_TYPE is 0, do this only for a field that matches the
4511          narrower type exactly and is aligned for it
4512          The resulting extension to its nominal type (a fullword type)
4513          must fit the same conditions as for other extensions.  */
4514
4515       if (type != 0
4516           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
4517           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
4518           && (! uns || final_prec <= innerprec || unsignedp))
4519         {
4520           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4521                         TREE_OPERAND (op, 1), NULL_TREE);
4522           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4523           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4524         }
4525     }
4526
4527   return win;
4528 }
4529 \f
4530 /* Return OP or a simpler expression for a narrower value
4531    which can be sign-extended or zero-extended to give back OP.
4532    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
4533    or 0 if the value should be sign-extended.  */
4534
4535 tree
4536 get_narrower (tree op, int *unsignedp_ptr)
4537 {
4538   int uns = 0;
4539   int first = 1;
4540   tree win = op;
4541
4542   while (TREE_CODE (op) == NOP_EXPR)
4543     {
4544       int bitschange
4545         = (TYPE_PRECISION (TREE_TYPE (op))
4546            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
4547
4548       /* Truncations are many-one so cannot be removed.  */
4549       if (bitschange < 0)
4550         break;
4551
4552       /* See what's inside this conversion.  If we decide to strip it,
4553          we will set WIN.  */
4554
4555       if (bitschange > 0)
4556         {
4557           op = TREE_OPERAND (op, 0);
4558           /* An extension: the outermost one can be stripped,
4559              but remember whether it is zero or sign extension.  */
4560           if (first)
4561             uns = TYPE_UNSIGNED (TREE_TYPE (op));
4562           /* Otherwise, if a sign extension has been stripped,
4563              only sign extensions can now be stripped;
4564              if a zero extension has been stripped, only zero-extensions.  */
4565           else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
4566             break;
4567           first = 0;
4568         }
4569       else /* bitschange == 0 */
4570         {
4571           /* A change in nominal type can always be stripped, but we must
4572              preserve the unsignedness.  */
4573           if (first)
4574             uns = TYPE_UNSIGNED (TREE_TYPE (op));
4575           first = 0;
4576           op = TREE_OPERAND (op, 0);
4577         }
4578
4579       win = op;
4580     }
4581
4582   if (TREE_CODE (op) == COMPONENT_REF
4583       /* Since type_for_size always gives an integer type.  */
4584       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
4585       /* Ensure field is laid out already.  */
4586       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4587       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4588     {
4589       unsigned HOST_WIDE_INT innerprec
4590         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4591       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
4592                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4593       tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
4594
4595       /* We can get this structure field in a narrower type that fits it,
4596          but the resulting extension to its nominal type (a fullword type)
4597          must satisfy the same conditions as for other extensions.
4598
4599          Do this only for fields that are aligned (not bit-fields),
4600          because when bit-field insns will be used there is no
4601          advantage in doing this.  */
4602
4603       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4604           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
4605           && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
4606           && type != 0)
4607         {
4608           if (first)
4609             uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
4610           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4611                         TREE_OPERAND (op, 1), NULL_TREE);
4612           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4613           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4614         }
4615     }
4616   *unsignedp_ptr = uns;
4617   return win;
4618 }
4619 \f
4620 /* Nonzero if integer constant C has a value that is permissible
4621    for type TYPE (an INTEGER_TYPE).  */
4622
4623 int
4624 int_fits_type_p (tree c, tree type)
4625 {
4626   tree type_low_bound = TYPE_MIN_VALUE (type);
4627   tree type_high_bound = TYPE_MAX_VALUE (type);
4628   int ok_for_low_bound, ok_for_high_bound;
4629
4630   /* Perform some generic filtering first, which may allow making a decision
4631      even if the bounds are not constant.  First, negative integers never fit
4632      in unsigned types, */
4633   if ((TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
4634       /* Also, unsigned integers with top bit set never fit signed types.  */
4635       || (! TYPE_UNSIGNED (type)
4636           && TYPE_UNSIGNED (TREE_TYPE (c)) && tree_int_cst_msb (c)))
4637     return 0;
4638
4639   /* If at least one bound of the type is a constant integer, we can check
4640      ourselves and maybe make a decision. If no such decision is possible, but
4641      this type is a subtype, try checking against that.  Otherwise, use
4642      force_fit_type, which checks against the precision.
4643
4644      Compute the status for each possibly constant bound, and return if we see
4645      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
4646      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
4647      for "constant known to fit".  */
4648
4649   ok_for_low_bound = -1;
4650   ok_for_high_bound = -1;
4651
4652   /* Check if C >= type_low_bound.  */
4653   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
4654     {
4655       ok_for_low_bound = ! tree_int_cst_lt (c, type_low_bound);
4656       if (! ok_for_low_bound)
4657         return 0;
4658     }
4659
4660   /* Check if c <= type_high_bound.  */
4661   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
4662     {
4663       ok_for_high_bound = ! tree_int_cst_lt (type_high_bound, c);
4664       if (! ok_for_high_bound)
4665         return 0;
4666     }
4667
4668   /* If the constant fits both bounds, the result is known.  */
4669   if (ok_for_low_bound == 1 && ok_for_high_bound == 1)
4670     return 1;
4671
4672   /* If we haven't been able to decide at this point, there nothing more we
4673      can check ourselves here. Look at the base type if we have one.  */
4674   else if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != 0)
4675     return int_fits_type_p (c, TREE_TYPE (type));
4676
4677   /* Or to force_fit_type, if nothing else.  */
4678   else
4679     {
4680       c = copy_node (c);
4681       TREE_TYPE (c) = type;
4682       return !force_fit_type (c, 0);
4683     }
4684 }
4685
4686 /* Returns true if T is, contains, or refers to a type with variable
4687    size.  This concept is more general than that of C99 'variably
4688    modified types': in C99, a struct type is never variably modified
4689    because a VLA may not appear as a structure member.  However, in
4690    GNU C code like:
4691
4692      struct S { int i[f()]; };
4693
4694    is valid, and other languages may define similar constructs.  */
4695
4696 bool
4697 variably_modified_type_p (tree type)
4698 {
4699   tree t;
4700
4701   if (type == error_mark_node)
4702     return false;
4703
4704   /* If TYPE itself has variable size, it is variably modified.
4705
4706      We do not yet have a representation of the C99 '[*]' syntax.
4707      When a representation is chosen, this function should be modified
4708      to test for that case as well.  */
4709   t = TYPE_SIZE (type);
4710   if (t && t != error_mark_node && TREE_CODE (t) != INTEGER_CST)
4711     return true;
4712
4713   switch (TREE_CODE (type))
4714     {
4715     case POINTER_TYPE:
4716     case REFERENCE_TYPE:
4717     case ARRAY_TYPE:
4718     case SET_TYPE:
4719     case VECTOR_TYPE:
4720       if (variably_modified_type_p (TREE_TYPE (type)))
4721         return true;
4722       break;
4723
4724     case FUNCTION_TYPE:
4725     case METHOD_TYPE:
4726       /* If TYPE is a function type, it is variably modified if any of the
4727          parameters or the return type are variably modified.  */
4728       if (variably_modified_type_p (TREE_TYPE (type)))
4729           return true;
4730
4731       for (t = TYPE_ARG_TYPES (type);
4732            t && t != void_list_node;
4733            t = TREE_CHAIN (t))
4734         if (variably_modified_type_p (TREE_VALUE (t)))
4735           return true;
4736       break;
4737
4738     case INTEGER_TYPE:
4739     case REAL_TYPE:
4740     case ENUMERAL_TYPE:
4741     case BOOLEAN_TYPE:
4742     case CHAR_TYPE:
4743       /* Scalar types are variably modified if their end points
4744          aren't constant.  */
4745       t = TYPE_MIN_VALUE (type);
4746       if (t && t != error_mark_node && TREE_CODE (t) != INTEGER_CST)
4747         return true;
4748
4749       t = TYPE_MAX_VALUE (type);
4750       if (t && t != error_mark_node && TREE_CODE (t) != INTEGER_CST)
4751         return true;
4752       break;
4753
4754     case RECORD_TYPE:
4755     case UNION_TYPE:
4756     case QUAL_UNION_TYPE:
4757       /* We can't see if any of the field are variably-modified by the
4758          definition we normally use, since that would produce infinite
4759          recursion via pointers.  */
4760       /* This is variably modified if some field's type is.  */
4761       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
4762         if (TREE_CODE (t) == FIELD_DECL)
4763           {
4764             tree t1 = DECL_FIELD_OFFSET (t);
4765
4766             if (t1 && t1 != error_mark_node && TREE_CODE (t1) != INTEGER_CST)
4767               return true;
4768
4769             t1 = DECL_SIZE (t);
4770             if (t1 && t1 != error_mark_node && TREE_CODE (t1) != INTEGER_CST)
4771               return true;
4772           }
4773         break;
4774
4775     default:
4776       break;
4777     }
4778
4779   /* The current language may have other cases to check, but in general,
4780      all other types are not variably modified.  */
4781   return lang_hooks.tree_inlining.var_mod_type_p (type);
4782 }
4783
4784 /* Given a DECL or TYPE, return the scope in which it was declared, or
4785    NULL_TREE if there is no containing scope.  */
4786
4787 tree
4788 get_containing_scope (tree t)
4789 {
4790   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
4791 }
4792
4793 /* Return the innermost context enclosing DECL that is
4794    a FUNCTION_DECL, or zero if none.  */
4795
4796 tree
4797 decl_function_context (tree decl)
4798 {
4799   tree context;
4800
4801   if (TREE_CODE (decl) == ERROR_MARK)
4802     return 0;
4803
4804   if (TREE_CODE (decl) == SAVE_EXPR)
4805     context = SAVE_EXPR_CONTEXT (decl);
4806
4807   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
4808      where we look up the function at runtime.  Such functions always take
4809      a first argument of type 'pointer to real context'.
4810
4811      C++ should really be fixed to use DECL_CONTEXT for the real context,
4812      and use something else for the "virtual context".  */
4813   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
4814     context
4815       = TYPE_MAIN_VARIANT
4816         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
4817   else
4818     context = DECL_CONTEXT (decl);
4819
4820   while (context && TREE_CODE (context) != FUNCTION_DECL)
4821     {
4822       if (TREE_CODE (context) == BLOCK)
4823         context = BLOCK_SUPERCONTEXT (context);
4824       else
4825         context = get_containing_scope (context);
4826     }
4827
4828   return context;
4829 }
4830
4831 /* Return the innermost context enclosing DECL that is
4832    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
4833    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
4834
4835 tree
4836 decl_type_context (tree decl)
4837 {
4838   tree context = DECL_CONTEXT (decl);
4839
4840   while (context)
4841     switch (TREE_CODE (context))
4842       {
4843       case NAMESPACE_DECL:
4844       case TRANSLATION_UNIT_DECL:
4845         return NULL_TREE;
4846
4847       case RECORD_TYPE:
4848       case UNION_TYPE:
4849       case QUAL_UNION_TYPE:
4850         return context;
4851
4852       case TYPE_DECL:
4853       case FUNCTION_DECL:
4854         context = DECL_CONTEXT (context);
4855         break;
4856
4857       case BLOCK:
4858         context = BLOCK_SUPERCONTEXT (context);
4859         break;
4860
4861       default:
4862         abort ();
4863       }
4864
4865   return NULL_TREE;
4866 }
4867
4868 /* CALL is a CALL_EXPR.  Return the declaration for the function
4869    called, or NULL_TREE if the called function cannot be
4870    determined.  */
4871
4872 tree
4873 get_callee_fndecl (tree call)
4874 {
4875   tree addr;
4876
4877   /* It's invalid to call this function with anything but a
4878      CALL_EXPR.  */
4879   if (TREE_CODE (call) != CALL_EXPR)
4880     abort ();
4881
4882   /* The first operand to the CALL is the address of the function
4883      called.  */
4884   addr = TREE_OPERAND (call, 0);
4885
4886   STRIP_NOPS (addr);
4887
4888   /* If this is a readonly function pointer, extract its initial value.  */
4889   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
4890       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
4891       && DECL_INITIAL (addr))
4892     addr = DECL_INITIAL (addr);
4893
4894   /* If the address is just `&f' for some function `f', then we know
4895      that `f' is being called.  */
4896   if (TREE_CODE (addr) == ADDR_EXPR
4897       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
4898     return TREE_OPERAND (addr, 0);
4899
4900   /* We couldn't figure out what was being called.  Maybe the front
4901      end has some idea.  */
4902   return lang_hooks.lang_get_callee_fndecl (call);
4903 }
4904
4905 /* Print debugging information about tree nodes generated during the compile,
4906    and any language-specific information.  */
4907
4908 void
4909 dump_tree_statistics (void)
4910 {
4911 #ifdef GATHER_STATISTICS
4912   int i;
4913   int total_nodes, total_bytes;
4914 #endif
4915
4916   fprintf (stderr, "\n??? tree nodes created\n\n");
4917 #ifdef GATHER_STATISTICS
4918   fprintf (stderr, "Kind                   Nodes      Bytes\n");
4919   fprintf (stderr, "---------------------------------------\n");
4920   total_nodes = total_bytes = 0;
4921   for (i = 0; i < (int) all_kinds; i++)
4922     {
4923       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
4924                tree_node_counts[i], tree_node_sizes[i]);
4925       total_nodes += tree_node_counts[i];
4926       total_bytes += tree_node_sizes[i];
4927     }
4928   fprintf (stderr, "---------------------------------------\n");
4929   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
4930   fprintf (stderr, "---------------------------------------\n");
4931   ssanames_print_statistics ();
4932   phinodes_print_statistics ();
4933 #else
4934   fprintf (stderr, "(No per-node statistics)\n");
4935 #endif
4936   print_type_hash_statistics ();
4937   lang_hooks.print_statistics ();
4938 }
4939 \f
4940 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
4941
4942 /* Generate a crc32 of a string.  */
4943
4944 unsigned
4945 crc32_string (unsigned chksum, const char *string)
4946 {
4947   do
4948     {
4949       unsigned value = *string << 24;
4950       unsigned ix;
4951
4952       for (ix = 8; ix--; value <<= 1)
4953         {
4954           unsigned feedback;
4955
4956           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
4957           chksum <<= 1;
4958           chksum ^= feedback;
4959         }
4960     }
4961   while (*string++);
4962   return chksum;
4963 }
4964
4965 /* P is a string that will be used in a symbol.  Mask out any characters
4966    that are not valid in that context.  */
4967
4968 void
4969 clean_symbol_name (char *p)
4970 {
4971   for (; *p; p++)
4972     if (! (ISALNUM (*p)
4973 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
4974             || *p == '$'
4975 #endif
4976 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
4977             || *p == '.'
4978 #endif
4979            ))
4980       *p = '_';
4981 }
4982
4983 /* Generate a name for a function unique to this translation unit.
4984    TYPE is some string to identify the purpose of this function to the
4985    linker or collect2.  */
4986
4987 tree
4988 get_file_function_name_long (const char *type)
4989 {
4990   char *buf;
4991   const char *p;
4992   char *q;
4993
4994   if (first_global_object_name)
4995     p = first_global_object_name;
4996   else
4997     {
4998       /* We don't have anything that we know to be unique to this translation
4999          unit, so use what we do have and throw in some randomness.  */
5000       unsigned len;
5001       const char *name = weak_global_object_name;
5002       const char *file = main_input_filename;
5003
5004       if (! name)
5005         name = "";
5006       if (! file)
5007         file = input_filename;
5008
5009       len = strlen (file);
5010       q = alloca (9 * 2 + len + 1);
5011       memcpy (q, file, len + 1);
5012       clean_symbol_name (q);
5013
5014       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
5015                crc32_string (0, flag_random_seed));
5016
5017       p = q;
5018     }
5019
5020   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
5021
5022   /* Set up the name of the file-level functions we may need.
5023      Use a global object (which is already required to be unique over
5024      the program) rather than the file name (which imposes extra
5025      constraints).  */
5026   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
5027
5028   return get_identifier (buf);
5029 }
5030
5031 /* If KIND=='I', return a suitable global initializer (constructor) name.
5032    If KIND=='D', return a suitable global clean-up (destructor) name.  */
5033
5034 tree
5035 get_file_function_name (int kind)
5036 {
5037   char p[2];
5038
5039   p[0] = kind;
5040   p[1] = 0;
5041
5042   return get_file_function_name_long (p);
5043 }
5044 \f
5045 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
5046    The result is placed in BUFFER (which has length BIT_SIZE),
5047    with one bit in each char ('\000' or '\001').
5048
5049    If the constructor is constant, NULL_TREE is returned.
5050    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
5051
5052 tree
5053 get_set_constructor_bits (tree init, char *buffer, int bit_size)
5054 {
5055   int i;
5056   tree vals;
5057   HOST_WIDE_INT domain_min
5058     = tree_low_cst (TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (init))), 0);
5059   tree non_const_bits = NULL_TREE;
5060
5061   for (i = 0; i < bit_size; i++)
5062     buffer[i] = 0;
5063
5064   for (vals = TREE_OPERAND (init, 1);
5065        vals != NULL_TREE; vals = TREE_CHAIN (vals))
5066     {
5067       if (!host_integerp (TREE_VALUE (vals), 0)
5068           || (TREE_PURPOSE (vals) != NULL_TREE
5069               && !host_integerp (TREE_PURPOSE (vals), 0)))
5070         non_const_bits
5071           = tree_cons (TREE_PURPOSE (vals), TREE_VALUE (vals), non_const_bits);
5072       else if (TREE_PURPOSE (vals) != NULL_TREE)
5073         {
5074           /* Set a range of bits to ones.  */
5075           HOST_WIDE_INT lo_index
5076             = tree_low_cst (TREE_PURPOSE (vals), 0) - domain_min;
5077           HOST_WIDE_INT hi_index
5078             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
5079
5080           if (lo_index < 0 || lo_index >= bit_size
5081               || hi_index < 0 || hi_index >= bit_size)
5082             abort ();
5083           for (; lo_index <= hi_index; lo_index++)
5084             buffer[lo_index] = 1;
5085         }
5086       else
5087         {
5088           /* Set a single bit to one.  */
5089           HOST_WIDE_INT index
5090             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
5091           if (index < 0 || index >= bit_size)
5092             {
5093               error ("invalid initializer for bit string");
5094               return NULL_TREE;
5095             }
5096           buffer[index] = 1;
5097         }
5098     }
5099   return non_const_bits;
5100 }
5101
5102 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
5103    The result is placed in BUFFER (which is an array of bytes).
5104    If the constructor is constant, NULL_TREE is returned.
5105    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
5106
5107 tree
5108 get_set_constructor_bytes (tree init, unsigned char *buffer, int wd_size)
5109 {
5110   int i;
5111   int set_word_size = BITS_PER_UNIT;
5112   int bit_size = wd_size * set_word_size;
5113   int bit_pos = 0;
5114   unsigned char *bytep = buffer;
5115   char *bit_buffer = alloca (bit_size);
5116   tree non_const_bits = get_set_constructor_bits (init, bit_buffer, bit_size);
5117
5118   for (i = 0; i < wd_size; i++)
5119     buffer[i] = 0;
5120
5121   for (i = 0; i < bit_size; i++)
5122     {
5123       if (bit_buffer[i])
5124         {
5125           if (BYTES_BIG_ENDIAN)
5126             *bytep |= (1 << (set_word_size - 1 - bit_pos));
5127           else
5128             *bytep |= 1 << bit_pos;
5129         }
5130       bit_pos++;
5131       if (bit_pos >= set_word_size)
5132         bit_pos = 0, bytep++;
5133     }
5134   return non_const_bits;
5135 }
5136 \f
5137 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
5138
5139 /* Complain that the tree code of NODE does not match the expected 0
5140    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
5141    the caller.  */
5142
5143 void
5144 tree_check_failed (const tree node, const char *file,
5145                    int line, const char *function, ...)
5146 {
5147   va_list args;
5148   char *buffer;
5149   unsigned length = 0;
5150   int code;
5151
5152   va_start (args, function);
5153   while ((code = va_arg (args, int)))
5154     length += 4 + strlen (tree_code_name[code]);
5155   va_end (args);
5156   va_start (args, function);
5157   buffer = alloca (length);
5158   length = 0;
5159   while ((code = va_arg (args, int)))
5160     {
5161       if (length)
5162         {
5163           strcpy (buffer + length, " or ");
5164           length += 4;
5165         }
5166       strcpy (buffer + length, tree_code_name[code]);
5167       length += strlen (tree_code_name[code]);
5168     }
5169   va_end (args);
5170
5171   internal_error ("tree check: expected %s, have %s in %s, at %s:%d",
5172                   buffer, tree_code_name[TREE_CODE (node)],
5173                   function, trim_filename (file), line);
5174 }
5175
5176 /* Complain that the tree code of NODE does match the expected 0
5177    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
5178    the caller.  */
5179
5180 void
5181 tree_not_check_failed (const tree node, const char *file,
5182                        int line, const char *function, ...)
5183 {
5184   va_list args;
5185   char *buffer;
5186   unsigned length = 0;
5187   int code;
5188
5189   va_start (args, function);
5190   while ((code = va_arg (args, int)))
5191     length += 4 + strlen (tree_code_name[code]);
5192   va_end (args);
5193   va_start (args, function);
5194   buffer = alloca (length);
5195   length = 0;
5196   while ((code = va_arg (args, int)))
5197     {
5198       if (length)
5199         {
5200           strcpy (buffer + length, " or ");
5201           length += 4;
5202         }
5203       strcpy (buffer + length, tree_code_name[code]);
5204       length += strlen (tree_code_name[code]);
5205     }
5206   va_end (args);
5207
5208   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
5209                   buffer, tree_code_name[TREE_CODE (node)],
5210                   function, trim_filename (file), line);
5211 }
5212
5213 /* Similar to tree_check_failed, except that we check for a class of tree
5214    code, given in CL.  */
5215
5216 void
5217 tree_class_check_failed (const tree node, int cl, const char *file,
5218                          int line, const char *function)
5219 {
5220   internal_error
5221     ("tree check: expected class '%c', have '%c' (%s) in %s, at %s:%d",
5222      cl, TREE_CODE_CLASS (TREE_CODE (node)),
5223      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
5224 }
5225
5226 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
5227    (dynamically sized) vector.  */
5228
5229 void
5230 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
5231                            const char *function)
5232 {
5233   internal_error
5234     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
5235      idx + 1, len, function, trim_filename (file), line);
5236 }
5237
5238 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
5239    (dynamically sized) vector.  */
5240
5241 void
5242 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
5243                             const char *function)
5244 {
5245   internal_error
5246     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
5247      idx + 1, len, function, trim_filename (file), line);
5248 }
5249
5250 /* Similar to above, except that the check is for the bounds of the operand
5251    vector of an expression node.  */
5252
5253 void
5254 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
5255                            int line, const char *function)
5256 {
5257   internal_error
5258     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
5259      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
5260      function, trim_filename (file), line);
5261 }
5262 #endif /* ENABLE_TREE_CHECKING */
5263 \f
5264 /* For a new vector type node T, build the information necessary for
5265    debugging output.  */
5266
5267 static void
5268 finish_vector_type (tree t)
5269 {
5270   layout_type (t);
5271
5272   {
5273     tree index = build_int_2 (TYPE_VECTOR_SUBPARTS (t) - 1, 0);
5274     tree array = build_array_type (TREE_TYPE (t),
5275                                    build_index_type (index));
5276     tree rt = make_node (RECORD_TYPE);
5277
5278     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
5279     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
5280     layout_type (rt);
5281     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
5282     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
5283        the representation type, and we want to find that die when looking up
5284        the vector type.  This is most easily achieved by making the TYPE_UID
5285        numbers equal.  */
5286     TYPE_UID (rt) = TYPE_UID (t);
5287   }
5288 }
5289
5290 static tree
5291 make_or_reuse_type (unsigned size, int unsignedp)
5292 {
5293   if (size == INT_TYPE_SIZE)
5294     return unsignedp ? unsigned_type_node : integer_type_node;
5295   if (size == CHAR_TYPE_SIZE)
5296     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
5297   if (size == SHORT_TYPE_SIZE)
5298     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
5299   if (size == LONG_TYPE_SIZE)
5300     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
5301   if (size == LONG_LONG_TYPE_SIZE)
5302     return (unsignedp ? long_long_unsigned_type_node
5303             : long_long_integer_type_node);
5304
5305   if (unsignedp)
5306     return make_unsigned_type (size);
5307   else
5308     return make_signed_type (size);
5309 }
5310
5311 /* Create nodes for all integer types (and error_mark_node) using the sizes
5312    of C datatypes.  The caller should call set_sizetype soon after calling
5313    this function to select one of the types as sizetype.  */
5314
5315 void
5316 build_common_tree_nodes (int signed_char)
5317 {
5318   error_mark_node = make_node (ERROR_MARK);
5319   TREE_TYPE (error_mark_node) = error_mark_node;
5320
5321   initialize_sizetypes ();
5322
5323   /* Define both `signed char' and `unsigned char'.  */
5324   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
5325   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
5326
5327   /* Define `char', which is like either `signed char' or `unsigned char'
5328      but not the same as either.  */
5329   char_type_node
5330     = (signed_char
5331        ? make_signed_type (CHAR_TYPE_SIZE)
5332        : make_unsigned_type (CHAR_TYPE_SIZE));
5333
5334   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
5335   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
5336   integer_type_node = make_signed_type (INT_TYPE_SIZE);
5337   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
5338   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
5339   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
5340   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
5341   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
5342
5343   /* Define a boolean type.  This type only represents boolean values but
5344      may be larger than char depending on the value of BOOL_TYPE_SIZE.
5345      Front ends which want to override this size (i.e. Java) can redefine
5346      boolean_type_node before calling build_common_tree_nodes_2.  */
5347   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
5348   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
5349   TYPE_MAX_VALUE (boolean_type_node) = build_int_2 (1, 0);
5350   TREE_TYPE (TYPE_MAX_VALUE (boolean_type_node)) = boolean_type_node;
5351   TYPE_PRECISION (boolean_type_node) = 1;
5352
5353   /* Fill in the rest of the sized types.  Reuse existing type nodes
5354      when possible.  */
5355   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
5356   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
5357   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
5358   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
5359   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
5360
5361   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
5362   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
5363   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
5364   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
5365   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
5366
5367   access_public_node = get_identifier ("public");
5368   access_protected_node = get_identifier ("protected");
5369   access_private_node = get_identifier ("private");
5370 }
5371
5372 /* Call this function after calling build_common_tree_nodes and set_sizetype.
5373    It will create several other common tree nodes.  */
5374
5375 void
5376 build_common_tree_nodes_2 (int short_double)
5377 {
5378   /* Define these next since types below may used them.  */
5379   integer_zero_node = build_int_2 (0, 0);
5380   integer_one_node = build_int_2 (1, 0);
5381   integer_minus_one_node = build_int_2 (-1, -1);
5382
5383   size_zero_node = size_int (0);
5384   size_one_node = size_int (1);
5385   bitsize_zero_node = bitsize_int (0);
5386   bitsize_one_node = bitsize_int (1);
5387   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
5388
5389   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
5390   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
5391
5392   void_type_node = make_node (VOID_TYPE);
5393   layout_type (void_type_node);
5394
5395   /* We are not going to have real types in C with less than byte alignment,
5396      so we might as well not have any types that claim to have it.  */
5397   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
5398   TYPE_USER_ALIGN (void_type_node) = 0;
5399
5400   null_pointer_node = build_int_2 (0, 0);
5401   TREE_TYPE (null_pointer_node) = build_pointer_type (void_type_node);
5402   layout_type (TREE_TYPE (null_pointer_node));
5403
5404   ptr_type_node = build_pointer_type (void_type_node);
5405   const_ptr_type_node
5406     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
5407   fileptr_type_node = ptr_type_node;
5408
5409   float_type_node = make_node (REAL_TYPE);
5410   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
5411   layout_type (float_type_node);
5412
5413   double_type_node = make_node (REAL_TYPE);
5414   if (short_double)
5415     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
5416   else
5417     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
5418   layout_type (double_type_node);
5419
5420   long_double_type_node = make_node (REAL_TYPE);
5421   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
5422   layout_type (long_double_type_node);
5423
5424   float_ptr_type_node = build_pointer_type (float_type_node);
5425   double_ptr_type_node = build_pointer_type (double_type_node);
5426   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
5427   integer_ptr_type_node = build_pointer_type (integer_type_node);
5428
5429   complex_integer_type_node = make_node (COMPLEX_TYPE);
5430   TREE_TYPE (complex_integer_type_node) = integer_type_node;
5431   layout_type (complex_integer_type_node);
5432
5433   complex_float_type_node = make_node (COMPLEX_TYPE);
5434   TREE_TYPE (complex_float_type_node) = float_type_node;
5435   layout_type (complex_float_type_node);
5436
5437   complex_double_type_node = make_node (COMPLEX_TYPE);
5438   TREE_TYPE (complex_double_type_node) = double_type_node;
5439   layout_type (complex_double_type_node);
5440
5441   complex_long_double_type_node = make_node (COMPLEX_TYPE);
5442   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
5443   layout_type (complex_long_double_type_node);
5444
5445   {
5446     tree t = targetm.build_builtin_va_list ();
5447
5448     /* Many back-ends define record types without setting TYPE_NAME.
5449        If we copied the record type here, we'd keep the original
5450        record type without a name.  This breaks name mangling.  So,
5451        don't copy record types and let c_common_nodes_and_builtins()
5452        declare the type to be __builtin_va_list.  */
5453     if (TREE_CODE (t) != RECORD_TYPE)
5454       t = build_type_copy (t);
5455
5456     va_list_type_node = t;
5457   }
5458 }
5459
5460 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
5461    better way.
5462
5463    If we requested a pointer to a vector, build up the pointers that
5464    we stripped off while looking for the inner type.  Similarly for
5465    return values from functions.
5466
5467    The argument TYPE is the top of the chain, and BOTTOM is the
5468    new type which we will point to.  */
5469
5470 tree
5471 reconstruct_complex_type (tree type, tree bottom)
5472 {
5473   tree inner, outer;
5474
5475   if (POINTER_TYPE_P (type))
5476     {
5477       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5478       outer = build_pointer_type (inner);
5479     }
5480   else if (TREE_CODE (type) == ARRAY_TYPE)
5481     {
5482       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5483       outer = build_array_type (inner, TYPE_DOMAIN (type));
5484     }
5485   else if (TREE_CODE (type) == FUNCTION_TYPE)
5486     {
5487       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5488       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
5489     }
5490   else if (TREE_CODE (type) == METHOD_TYPE)
5491     {
5492       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5493       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
5494                                           inner,
5495                                           TYPE_ARG_TYPES (type));
5496     }
5497   else
5498     return bottom;
5499
5500   TYPE_READONLY (outer) = TYPE_READONLY (type);
5501   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
5502
5503   return outer;
5504 }
5505
5506 /* Returns a vector tree node given a vector mode and inner type.  */
5507 tree
5508 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
5509 {
5510   tree t;
5511   t = make_node (VECTOR_TYPE);
5512   TREE_TYPE (t) = innertype;
5513   TYPE_MODE (t) = mode;
5514   finish_vector_type (t);
5515   return t;
5516 }
5517
5518 /* Similarly, but takes inner type and units.  */
5519
5520 tree
5521 build_vector_type (tree innertype, int nunits)
5522 {
5523   enum machine_mode innermode = TYPE_MODE (innertype);
5524   enum machine_mode mode;
5525
5526   if (GET_MODE_CLASS (innermode) == MODE_FLOAT)
5527     mode = MIN_MODE_VECTOR_FLOAT;
5528   else
5529     mode = MIN_MODE_VECTOR_INT;
5530
5531   for (; mode != VOIDmode ; mode = GET_MODE_WIDER_MODE (mode))
5532     if (GET_MODE_NUNITS (mode) == nunits && GET_MODE_INNER (mode) == innermode)
5533       return build_vector_type_for_mode (innertype, mode);
5534
5535   return NULL_TREE;
5536 }
5537
5538 /* Given an initializer INIT, return TRUE if INIT is zero or some
5539    aggregate of zeros.  Otherwise return FALSE.  */
5540 bool
5541 initializer_zerop (tree init)
5542 {
5543   tree elt;
5544
5545   STRIP_NOPS (init);
5546
5547   switch (TREE_CODE (init))
5548     {
5549     case INTEGER_CST:
5550       return integer_zerop (init);
5551
5552     case REAL_CST:
5553       /* ??? Note that this is not correct for C4X float formats.  There,
5554          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
5555          negative exponent.  */
5556       return real_zerop (init)
5557         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
5558
5559     case COMPLEX_CST:
5560       return integer_zerop (init)
5561         || (real_zerop (init)
5562             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
5563             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
5564
5565     case VECTOR_CST:
5566       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
5567         if (!initializer_zerop (TREE_VALUE (elt)))
5568           return false;
5569       return true;
5570
5571     case CONSTRUCTOR:
5572       elt = CONSTRUCTOR_ELTS (init);
5573       if (elt == NULL_TREE)
5574         return true;
5575
5576       /* A set is empty only if it has no elements.  */
5577       if (TREE_CODE (TREE_TYPE (init)) == SET_TYPE)
5578         return false;
5579
5580       for (; elt ; elt = TREE_CHAIN (elt))
5581         if (! initializer_zerop (TREE_VALUE (elt)))
5582           return false;
5583       return true;
5584
5585     default:
5586       return false;
5587     }
5588 }
5589
5590 void
5591 add_var_to_bind_expr (tree bind_expr, tree var)
5592 {
5593   BIND_EXPR_VARS (bind_expr)
5594     = chainon (BIND_EXPR_VARS (bind_expr), var);
5595   if (BIND_EXPR_BLOCK (bind_expr))
5596     BLOCK_VARS (BIND_EXPR_BLOCK (bind_expr))
5597       = BIND_EXPR_VARS (bind_expr);
5598 }
5599
5600 /* Build an empty statement.  */
5601
5602 tree
5603 build_empty_stmt (void)
5604 {
5605   return build1 (NOP_EXPR, void_type_node, size_zero_node);
5606 }
5607
5608
5609 /* Return true if T (assumed to be a DECL) must be assigned a memory
5610    location.  */
5611
5612 bool
5613 needs_to_live_in_memory (tree t)
5614 {
5615   return (DECL_NEEDS_TO_LIVE_IN_MEMORY_INTERNAL (t)
5616           || TREE_STATIC (t)
5617           || DECL_EXTERNAL (t)
5618           || DECL_NONLOCAL (t)
5619           || (TREE_CODE (t) == RESULT_DECL
5620               && aggregate_value_p (t, current_function_decl))
5621           || decl_function_context (t) != current_function_decl);
5622 }
5623
5624 #include "gt-tree.h"