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