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