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