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 CONST_DECL:
1493       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1494               ? arg : NULL);
1495
1496     case CONSTRUCTOR:
1497       return TREE_STATIC (arg) ? arg : NULL;
1498
1499     case LABEL_DECL:
1500     case STRING_CST:
1501       return arg;
1502
1503     case COMPONENT_REF:
1504       /* If the thing being referenced is not a field, then it is
1505          something language specific.  */
1506       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1507         return (*lang_hooks.staticp) (arg);
1508
1509       /* If we are referencing a bitfield, we can't evaluate an
1510          ADDR_EXPR at compile time and so it isn't a constant.  */
1511       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1512         return NULL;
1513
1514       return staticp (TREE_OPERAND (arg, 0));
1515
1516     case BIT_FIELD_REF:
1517       return NULL;
1518
1519     case MISALIGNED_INDIRECT_REF:
1520     case ALIGN_INDIRECT_REF:
1521     case INDIRECT_REF:
1522       return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
1523
1524     case ARRAY_REF:
1525     case ARRAY_RANGE_REF:
1526       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1527           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1528         return staticp (TREE_OPERAND (arg, 0));
1529       else
1530         return false;
1531
1532     default:
1533       if ((unsigned int) TREE_CODE (arg)
1534           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1535         return lang_hooks.staticp (arg);
1536       else
1537         return NULL;
1538     }
1539 }
1540 \f
1541 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1542    Do this to any expression which may be used in more than one place,
1543    but must be evaluated only once.
1544
1545    Normally, expand_expr would reevaluate the expression each time.
1546    Calling save_expr produces something that is evaluated and recorded
1547    the first time expand_expr is called on it.  Subsequent calls to
1548    expand_expr just reuse the recorded value.
1549
1550    The call to expand_expr that generates code that actually computes
1551    the value is the first call *at compile time*.  Subsequent calls
1552    *at compile time* generate code to use the saved value.
1553    This produces correct result provided that *at run time* control
1554    always flows through the insns made by the first expand_expr
1555    before reaching the other places where the save_expr was evaluated.
1556    You, the caller of save_expr, must make sure this is so.
1557
1558    Constants, and certain read-only nodes, are returned with no
1559    SAVE_EXPR because that is safe.  Expressions containing placeholders
1560    are not touched; see tree.def for an explanation of what these
1561    are used for.  */
1562
1563 tree
1564 save_expr (tree expr)
1565 {
1566   tree t = fold (expr);
1567   tree inner;
1568
1569   /* If the tree evaluates to a constant, then we don't want to hide that
1570      fact (i.e. this allows further folding, and direct checks for constants).
1571      However, a read-only object that has side effects cannot be bypassed.
1572      Since it is no problem to reevaluate literals, we just return the
1573      literal node.  */
1574   inner = skip_simple_arithmetic (t);
1575
1576   if (TREE_INVARIANT (inner)
1577       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1578       || TREE_CODE (inner) == SAVE_EXPR
1579       || TREE_CODE (inner) == ERROR_MARK)
1580     return t;
1581
1582   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1583      it means that the size or offset of some field of an object depends on
1584      the value within another field.
1585
1586      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1587      and some variable since it would then need to be both evaluated once and
1588      evaluated more than once.  Front-ends must assure this case cannot
1589      happen by surrounding any such subexpressions in their own SAVE_EXPR
1590      and forcing evaluation at the proper time.  */
1591   if (contains_placeholder_p (inner))
1592     return t;
1593
1594   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
1595
1596   /* This expression might be placed ahead of a jump to ensure that the
1597      value was computed on both sides of the jump.  So make sure it isn't
1598      eliminated as dead.  */
1599   TREE_SIDE_EFFECTS (t) = 1;
1600   TREE_INVARIANT (t) = 1;
1601   return t;
1602 }
1603
1604 /* Look inside EXPR and into any simple arithmetic operations.  Return
1605    the innermost non-arithmetic node.  */
1606
1607 tree
1608 skip_simple_arithmetic (tree expr)
1609 {
1610   tree inner;
1611
1612   /* We don't care about whether this can be used as an lvalue in this
1613      context.  */
1614   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
1615     expr = TREE_OPERAND (expr, 0);
1616
1617   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
1618      a constant, it will be more efficient to not make another SAVE_EXPR since
1619      it will allow better simplification and GCSE will be able to merge the
1620      computations if they actually occur.  */
1621   inner = expr;
1622   while (1)
1623     {
1624       if (UNARY_CLASS_P (inner))
1625         inner = TREE_OPERAND (inner, 0);
1626       else if (BINARY_CLASS_P (inner))
1627         {
1628           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
1629             inner = TREE_OPERAND (inner, 0);
1630           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
1631             inner = TREE_OPERAND (inner, 1);
1632           else
1633             break;
1634         }
1635       else
1636         break;
1637     }
1638
1639   return inner;
1640 }
1641
1642 /* Returns the index of the first non-tree operand for CODE, or the number
1643    of operands if all are trees.  */
1644
1645 int
1646 first_rtl_op (enum tree_code code)
1647 {
1648   switch (code)
1649     {
1650     default:
1651       return TREE_CODE_LENGTH (code);
1652     }
1653 }
1654
1655 /* Return which tree structure is used by T.  */
1656
1657 enum tree_node_structure_enum
1658 tree_node_structure (tree t)
1659 {
1660   enum tree_code code = TREE_CODE (t);
1661
1662   switch (TREE_CODE_CLASS (code))
1663     {
1664     case tcc_declaration:
1665       return TS_DECL;
1666     case tcc_type:
1667       return TS_TYPE;
1668     case tcc_reference:
1669     case tcc_comparison:
1670     case tcc_unary:
1671     case tcc_binary:
1672     case tcc_expression:
1673     case tcc_statement:
1674       return TS_EXP;
1675     default:  /* tcc_constant and tcc_exceptional */
1676       break;
1677     }
1678   switch (code)
1679     {
1680       /* tcc_constant cases.  */
1681     case INTEGER_CST:           return TS_INT_CST;
1682     case REAL_CST:              return TS_REAL_CST;
1683     case COMPLEX_CST:           return TS_COMPLEX;
1684     case VECTOR_CST:            return TS_VECTOR;
1685     case STRING_CST:            return TS_STRING;
1686       /* tcc_exceptional cases.  */
1687     case ERROR_MARK:            return TS_COMMON;
1688     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
1689     case TREE_LIST:             return TS_LIST;
1690     case TREE_VEC:              return TS_VEC;
1691     case PHI_NODE:              return TS_PHI_NODE;
1692     case SSA_NAME:              return TS_SSA_NAME;
1693     case PLACEHOLDER_EXPR:      return TS_COMMON;
1694     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
1695     case BLOCK:                 return TS_BLOCK;
1696     case TREE_BINFO:            return TS_BINFO;
1697     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
1698
1699     default:
1700       gcc_unreachable ();
1701     }
1702 }
1703 \f
1704 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
1705    or offset that depends on a field within a record.  */
1706
1707 bool
1708 contains_placeholder_p (tree exp)
1709 {
1710   enum tree_code code;
1711
1712   if (!exp)
1713     return 0;
1714
1715   code = TREE_CODE (exp);
1716   if (code == PLACEHOLDER_EXPR)
1717     return 1;
1718
1719   switch (TREE_CODE_CLASS (code))
1720     {
1721     case tcc_reference:
1722       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
1723          position computations since they will be converted into a
1724          WITH_RECORD_EXPR involving the reference, which will assume
1725          here will be valid.  */
1726       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1727
1728     case tcc_exceptional:
1729       if (code == TREE_LIST)
1730         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
1731                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
1732       break;
1733
1734     case tcc_unary:
1735     case tcc_binary:
1736     case tcc_comparison:
1737     case tcc_expression:
1738       switch (code)
1739         {
1740         case COMPOUND_EXPR:
1741           /* Ignoring the first operand isn't quite right, but works best.  */
1742           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
1743
1744         case COND_EXPR:
1745           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1746                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
1747                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
1748
1749         default:
1750           break;
1751         }
1752
1753       switch (first_rtl_op (code))
1754         {
1755         case 1:
1756           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
1757         case 2:
1758           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
1759                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
1760         default:
1761           return 0;
1762         }
1763
1764     default:
1765       return 0;
1766     }
1767   return 0;
1768 }
1769
1770 /* Return true if any part of the computation of TYPE involves a
1771    PLACEHOLDER_EXPR.  This includes size, bounds, qualifiers
1772    (for QUAL_UNION_TYPE) and field positions.  */
1773
1774 static bool
1775 type_contains_placeholder_1 (tree type)
1776 {
1777   /* If the size contains a placeholder or the parent type (component type in
1778      the case of arrays) type involves a placeholder, this type does.  */
1779   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
1780       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
1781       || (TREE_TYPE (type) != 0
1782           && type_contains_placeholder_p (TREE_TYPE (type))))
1783     return true;
1784
1785   /* Now do type-specific checks.  Note that the last part of the check above
1786      greatly limits what we have to do below.  */
1787   switch (TREE_CODE (type))
1788     {
1789     case VOID_TYPE:
1790     case COMPLEX_TYPE:
1791     case ENUMERAL_TYPE:
1792     case BOOLEAN_TYPE:
1793     case CHAR_TYPE:
1794     case POINTER_TYPE:
1795     case OFFSET_TYPE:
1796     case REFERENCE_TYPE:
1797     case METHOD_TYPE:
1798     case FILE_TYPE:
1799     case FUNCTION_TYPE:
1800       return false;
1801
1802     case INTEGER_TYPE:
1803     case REAL_TYPE:
1804       /* Here we just check the bounds.  */
1805       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
1806               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
1807
1808     case ARRAY_TYPE:
1809     case SET_TYPE:
1810     case VECTOR_TYPE:
1811       /* We're already checked the component type (TREE_TYPE), so just check
1812          the index type.  */
1813       return type_contains_placeholder_p (TYPE_DOMAIN (type));
1814
1815     case RECORD_TYPE:
1816     case UNION_TYPE:
1817     case QUAL_UNION_TYPE:
1818       {
1819         tree field;
1820
1821         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
1822           if (TREE_CODE (field) == FIELD_DECL
1823               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
1824                   || (TREE_CODE (type) == QUAL_UNION_TYPE
1825                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
1826                   || type_contains_placeholder_p (TREE_TYPE (field))))
1827             return true;
1828
1829         return false;
1830       }
1831
1832     default:
1833       gcc_unreachable ();
1834     }
1835 }
1836
1837 bool
1838 type_contains_placeholder_p (tree type)
1839 {
1840   bool result;
1841
1842   /* If the contains_placeholder_bits field has been initialized,
1843      then we know the answer.  */
1844   if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
1845     return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
1846
1847   /* Indicate that we've seen this type node, and the answer is false.
1848      This is what we want to return if we run into recursion via fields.  */
1849   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
1850
1851   /* Compute the real value.  */
1852   result = type_contains_placeholder_1 (type);
1853
1854   /* Store the real value.  */
1855   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
1856
1857   return result;
1858 }
1859 \f
1860 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
1861    return a tree with all occurrences of references to F in a
1862    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
1863    contains only arithmetic expressions or a CALL_EXPR with a
1864    PLACEHOLDER_EXPR occurring only in its arglist.  */
1865
1866 tree
1867 substitute_in_expr (tree exp, tree f, tree r)
1868 {
1869   enum tree_code code = TREE_CODE (exp);
1870   tree op0, op1, op2;
1871   tree new;
1872   tree inner;
1873
1874   /* We handle TREE_LIST and COMPONENT_REF separately.  */
1875   if (code == TREE_LIST)
1876     {
1877       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
1878       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
1879       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
1880         return exp;
1881
1882       return tree_cons (TREE_PURPOSE (exp), op1, op0);
1883     }
1884   else if (code == COMPONENT_REF)
1885    {
1886      /* If this expression is getting a value from a PLACEHOLDER_EXPR
1887         and it is the right field, replace it with R.  */
1888      for (inner = TREE_OPERAND (exp, 0);
1889           REFERENCE_CLASS_P (inner);
1890           inner = TREE_OPERAND (inner, 0))
1891        ;
1892      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
1893          && TREE_OPERAND (exp, 1) == f)
1894        return r;
1895
1896      /* If this expression hasn't been completed let, leave it alone.  */
1897      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
1898        return exp;
1899
1900      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1901      if (op0 == TREE_OPERAND (exp, 0))
1902        return exp;
1903
1904      new = fold (build3 (COMPONENT_REF, TREE_TYPE (exp),
1905                          op0, TREE_OPERAND (exp, 1), NULL_TREE));
1906    }
1907   else
1908     switch (TREE_CODE_CLASS (code))
1909       {
1910       case tcc_constant:
1911       case tcc_declaration:
1912         return exp;
1913
1914       case tcc_exceptional:
1915       case tcc_unary:
1916       case tcc_binary:
1917       case tcc_comparison:
1918       case tcc_expression:
1919       case tcc_reference:
1920         switch (first_rtl_op (code))
1921           {
1922           case 0:
1923             return exp;
1924
1925           case 1:
1926             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1927             if (op0 == TREE_OPERAND (exp, 0))
1928               return exp;
1929
1930             new = fold (build1 (code, TREE_TYPE (exp), op0));
1931             break;
1932
1933           case 2:
1934             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1935             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
1936
1937             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
1938               return exp;
1939
1940             new = fold (build2 (code, TREE_TYPE (exp), op0, op1));
1941             break;
1942
1943           case 3:
1944             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
1945             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
1946             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
1947
1948             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
1949                 && op2 == TREE_OPERAND (exp, 2))
1950               return exp;
1951
1952             new = fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
1953             break;
1954
1955           default:
1956             gcc_unreachable ();
1957           }
1958         break;
1959
1960       default:
1961         gcc_unreachable ();
1962       }
1963
1964   TREE_READONLY (new) = TREE_READONLY (exp);
1965   return new;
1966 }
1967
1968 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
1969    for it within OBJ, a tree that is an object or a chain of references.  */
1970
1971 tree
1972 substitute_placeholder_in_expr (tree exp, tree obj)
1973 {
1974   enum tree_code code = TREE_CODE (exp);
1975   tree op0, op1, op2, op3;
1976
1977   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
1978      in the chain of OBJ.  */
1979   if (code == PLACEHOLDER_EXPR)
1980     {
1981       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
1982       tree elt;
1983
1984       for (elt = obj; elt != 0;
1985            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
1986                    || TREE_CODE (elt) == COND_EXPR)
1987                   ? TREE_OPERAND (elt, 1)
1988                   : (REFERENCE_CLASS_P (elt)
1989                      || UNARY_CLASS_P (elt)
1990                      || BINARY_CLASS_P (elt)
1991                      || EXPRESSION_CLASS_P (elt))
1992                   ? TREE_OPERAND (elt, 0) : 0))
1993         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
1994           return elt;
1995
1996       for (elt = obj; elt != 0;
1997            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
1998                    || TREE_CODE (elt) == COND_EXPR)
1999                   ? TREE_OPERAND (elt, 1)
2000                   : (REFERENCE_CLASS_P (elt)
2001                      || UNARY_CLASS_P (elt)
2002                      || BINARY_CLASS_P (elt)
2003                      || EXPRESSION_CLASS_P (elt))
2004                   ? TREE_OPERAND (elt, 0) : 0))
2005         if (POINTER_TYPE_P (TREE_TYPE (elt))
2006             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2007                 == need_type))
2008           return fold (build1 (INDIRECT_REF, need_type, elt));
2009
2010       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2011          survives until RTL generation, there will be an error.  */
2012       return exp;
2013     }
2014
2015   /* TREE_LIST is special because we need to look at TREE_VALUE
2016      and TREE_CHAIN, not TREE_OPERANDS.  */
2017   else if (code == TREE_LIST)
2018     {
2019       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2020       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2021       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2022         return exp;
2023
2024       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2025     }
2026   else
2027     switch (TREE_CODE_CLASS (code))
2028       {
2029       case tcc_constant:
2030       case tcc_declaration:
2031         return exp;
2032
2033       case tcc_exceptional:
2034       case tcc_unary:
2035       case tcc_binary:
2036       case tcc_comparison:
2037       case tcc_expression:
2038       case tcc_reference:
2039       case tcc_statement:
2040         switch (first_rtl_op (code))
2041           {
2042           case 0:
2043             return exp;
2044
2045           case 1:
2046             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2047             if (op0 == TREE_OPERAND (exp, 0))
2048               return exp;
2049             else
2050               return fold (build1 (code, TREE_TYPE (exp), op0));
2051
2052           case 2:
2053             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2054             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2055
2056             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2057               return exp;
2058             else
2059               return fold (build2 (code, TREE_TYPE (exp), op0, op1));
2060
2061           case 3:
2062             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2063             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2064             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2065
2066             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2067                 && op2 == TREE_OPERAND (exp, 2))
2068               return exp;
2069             else
2070               return fold (build3 (code, TREE_TYPE (exp), op0, op1, op2));
2071
2072           case 4:
2073             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2074             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2075             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2076             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2077
2078             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2079                 && op2 == TREE_OPERAND (exp, 2)
2080                 && op3 == TREE_OPERAND (exp, 3))
2081               return exp;
2082             else
2083               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2084
2085           default:
2086             gcc_unreachable ();
2087           }
2088         break;
2089
2090       default:
2091         gcc_unreachable ();
2092       }
2093 }
2094 \f
2095 /* Stabilize a reference so that we can use it any number of times
2096    without causing its operands to be evaluated more than once.
2097    Returns the stabilized reference.  This works by means of save_expr,
2098    so see the caveats in the comments about save_expr.
2099
2100    Also allows conversion expressions whose operands are references.
2101    Any other kind of expression is returned unchanged.  */
2102
2103 tree
2104 stabilize_reference (tree ref)
2105 {
2106   tree result;
2107   enum tree_code code = TREE_CODE (ref);
2108
2109   switch (code)
2110     {
2111     case VAR_DECL:
2112     case PARM_DECL:
2113     case RESULT_DECL:
2114       /* No action is needed in this case.  */
2115       return ref;
2116
2117     case NOP_EXPR:
2118     case CONVERT_EXPR:
2119     case FLOAT_EXPR:
2120     case FIX_TRUNC_EXPR:
2121     case FIX_FLOOR_EXPR:
2122     case FIX_ROUND_EXPR:
2123     case FIX_CEIL_EXPR:
2124       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2125       break;
2126
2127     case INDIRECT_REF:
2128       result = build_nt (INDIRECT_REF,
2129                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2130       break;
2131
2132     case COMPONENT_REF:
2133       result = build_nt (COMPONENT_REF,
2134                          stabilize_reference (TREE_OPERAND (ref, 0)),
2135                          TREE_OPERAND (ref, 1), NULL_TREE);
2136       break;
2137
2138     case BIT_FIELD_REF:
2139       result = build_nt (BIT_FIELD_REF,
2140                          stabilize_reference (TREE_OPERAND (ref, 0)),
2141                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2142                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2143       break;
2144
2145     case ARRAY_REF:
2146       result = build_nt (ARRAY_REF,
2147                          stabilize_reference (TREE_OPERAND (ref, 0)),
2148                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2149                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2150       break;
2151
2152     case ARRAY_RANGE_REF:
2153       result = build_nt (ARRAY_RANGE_REF,
2154                          stabilize_reference (TREE_OPERAND (ref, 0)),
2155                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2156                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2157       break;
2158
2159     case COMPOUND_EXPR:
2160       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2161          it wouldn't be ignored.  This matters when dealing with
2162          volatiles.  */
2163       return stabilize_reference_1 (ref);
2164
2165       /* If arg isn't a kind of lvalue we recognize, make no change.
2166          Caller should recognize the error for an invalid lvalue.  */
2167     default:
2168       return ref;
2169
2170     case ERROR_MARK:
2171       return error_mark_node;
2172     }
2173
2174   TREE_TYPE (result) = TREE_TYPE (ref);
2175   TREE_READONLY (result) = TREE_READONLY (ref);
2176   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2177   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2178
2179   return result;
2180 }
2181
2182 /* Subroutine of stabilize_reference; this is called for subtrees of
2183    references.  Any expression with side-effects must be put in a SAVE_EXPR
2184    to ensure that it is only evaluated once.
2185
2186    We don't put SAVE_EXPR nodes around everything, because assigning very
2187    simple expressions to temporaries causes us to miss good opportunities
2188    for optimizations.  Among other things, the opportunity to fold in the
2189    addition of a constant into an addressing mode often gets lost, e.g.
2190    "y[i+1] += x;".  In general, we take the approach that we should not make
2191    an assignment unless we are forced into it - i.e., that any non-side effect
2192    operator should be allowed, and that cse should take care of coalescing
2193    multiple utterances of the same expression should that prove fruitful.  */
2194
2195 tree
2196 stabilize_reference_1 (tree e)
2197 {
2198   tree result;
2199   enum tree_code code = TREE_CODE (e);
2200
2201   /* We cannot ignore const expressions because it might be a reference
2202      to a const array but whose index contains side-effects.  But we can
2203      ignore things that are actual constant or that already have been
2204      handled by this function.  */
2205
2206   if (TREE_INVARIANT (e))
2207     return e;
2208
2209   switch (TREE_CODE_CLASS (code))
2210     {
2211     case tcc_exceptional:
2212     case tcc_type:
2213     case tcc_declaration:
2214     case tcc_comparison:
2215     case tcc_statement:
2216     case tcc_expression:
2217     case tcc_reference:
2218       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2219          so that it will only be evaluated once.  */
2220       /* The reference (r) and comparison (<) classes could be handled as
2221          below, but it is generally faster to only evaluate them once.  */
2222       if (TREE_SIDE_EFFECTS (e))
2223         return save_expr (e);
2224       return e;
2225
2226     case tcc_constant:
2227       /* Constants need no processing.  In fact, we should never reach
2228          here.  */
2229       return e;
2230
2231     case tcc_binary:
2232       /* Division is slow and tends to be compiled with jumps,
2233          especially the division by powers of 2 that is often
2234          found inside of an array reference.  So do it just once.  */
2235       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2236           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2237           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2238           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2239         return save_expr (e);
2240       /* Recursively stabilize each operand.  */
2241       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2242                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2243       break;
2244
2245     case tcc_unary:
2246       /* Recursively stabilize each operand.  */
2247       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2248       break;
2249
2250     default:
2251       gcc_unreachable ();
2252     }
2253
2254   TREE_TYPE (result) = TREE_TYPE (e);
2255   TREE_READONLY (result) = TREE_READONLY (e);
2256   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2257   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2258   TREE_INVARIANT (result) = 1;
2259
2260   return result;
2261 }
2262 \f
2263 /* Low-level constructors for expressions.  */
2264
2265 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2266    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2267
2268 void
2269 recompute_tree_invarant_for_addr_expr (tree t)
2270 {
2271   tree node;
2272   bool tc = true, ti = true, se = false;
2273
2274   /* We started out assuming this address is both invariant and constant, but
2275      does not have side effects.  Now go down any handled components and see if
2276      any of them involve offsets that are either non-constant or non-invariant.
2277      Also check for side-effects.
2278
2279      ??? Note that this code makes no attempt to deal with the case where
2280      taking the address of something causes a copy due to misalignment.  */
2281
2282 #define UPDATE_TITCSE(NODE)  \
2283 do { tree _node = (NODE); \
2284      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2285      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2286      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2287
2288   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2289        node = TREE_OPERAND (node, 0))
2290     {
2291       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2292          array reference (probably made temporarily by the G++ front end),
2293          so ignore all the operands.  */
2294       if ((TREE_CODE (node) == ARRAY_REF
2295            || TREE_CODE (node) == ARRAY_RANGE_REF)
2296           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2297         {
2298           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2299           if (TREE_OPERAND (node, 2))
2300             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2301           if (TREE_OPERAND (node, 3))
2302             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2303         }
2304       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2305          FIELD_DECL, apparently.  The G++ front end can put something else
2306          there, at least temporarily.  */
2307       else if (TREE_CODE (node) == COMPONENT_REF
2308                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2309         {
2310           if (TREE_OPERAND (node, 2))
2311             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2312         }
2313       else if (TREE_CODE (node) == BIT_FIELD_REF)
2314         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2315     }
2316
2317   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2318      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2319      invariant and constant if the decl is static.  It's also invariant if it's
2320      a decl in the current function.  Taking the address of a volatile variable
2321      is not volatile.  If it's a constant, the address is both invariant and
2322      constant.  Otherwise it's neither.  */
2323   if (TREE_CODE (node) == INDIRECT_REF)
2324     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2325   else if (DECL_P (node))
2326     {
2327       if (staticp (node))
2328         ;
2329       else if (decl_function_context (node) == current_function_decl)
2330         tc = false;
2331       else
2332         ti = tc = false;
2333     }
2334   else if (CONSTANT_CLASS_P (node))
2335     ;
2336   else
2337     {
2338       ti = tc = false;
2339       se |= TREE_SIDE_EFFECTS (node);
2340     }
2341
2342   TREE_CONSTANT (t) = tc;
2343   TREE_INVARIANT (t) = ti;
2344   TREE_SIDE_EFFECTS (t) = se;
2345 #undef UPDATE_TITCSE
2346 }
2347
2348 /* Build an expression of code CODE, data type TYPE, and operands as
2349    specified.  Expressions and reference nodes can be created this way.
2350    Constants, decls, types and misc nodes cannot be.
2351
2352    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2353    enough for all extant tree codes.  These functions can be called
2354    directly (preferably!), but can also be obtained via GCC preprocessor
2355    magic within the build macro.  */
2356
2357 tree
2358 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2359 {
2360   tree t;
2361
2362   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2363
2364   t = make_node_stat (code PASS_MEM_STAT);
2365   TREE_TYPE (t) = tt;
2366
2367   return t;
2368 }
2369
2370 tree
2371 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2372 {
2373   int length = sizeof (struct tree_exp);
2374 #ifdef GATHER_STATISTICS
2375   tree_node_kind kind;
2376 #endif
2377   tree t;
2378
2379 #ifdef GATHER_STATISTICS
2380   switch (TREE_CODE_CLASS (code))
2381     {
2382     case tcc_statement:  /* an expression with side effects */
2383       kind = s_kind;
2384       break;
2385     case tcc_reference:  /* a reference */
2386       kind = r_kind;
2387       break;
2388     default:
2389       kind = e_kind;
2390       break;
2391     }
2392
2393   tree_node_counts[(int) kind]++;
2394   tree_node_sizes[(int) kind] += length;
2395 #endif
2396
2397   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2398
2399   t = ggc_alloc_zone_stat (length, tree_zone PASS_MEM_STAT);
2400
2401   memset (t, 0, sizeof (struct tree_common));
2402
2403   TREE_SET_CODE (t, code);
2404
2405   TREE_TYPE (t) = type;
2406 #ifdef USE_MAPPED_LOCATION
2407   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2408 #else
2409   SET_EXPR_LOCUS (t, NULL);
2410 #endif
2411   TREE_COMPLEXITY (t) = 0;
2412   TREE_OPERAND (t, 0) = node;
2413   TREE_BLOCK (t) = NULL_TREE;
2414   if (node && !TYPE_P (node) && first_rtl_op (code) != 0)
2415     {
2416       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2417       TREE_READONLY (t) = TREE_READONLY (node);
2418     }
2419
2420   if (TREE_CODE_CLASS (code) == tcc_statement)
2421     TREE_SIDE_EFFECTS (t) = 1;
2422   else switch (code)
2423     {
2424     case INIT_EXPR:
2425     case MODIFY_EXPR:
2426     case VA_ARG_EXPR:
2427     case PREDECREMENT_EXPR:
2428     case PREINCREMENT_EXPR:
2429     case POSTDECREMENT_EXPR:
2430     case POSTINCREMENT_EXPR:
2431       /* All of these have side-effects, no matter what their
2432          operands are.  */
2433       TREE_SIDE_EFFECTS (t) = 1;
2434       TREE_READONLY (t) = 0;
2435       break;
2436
2437     case MISALIGNED_INDIRECT_REF:
2438     case ALIGN_INDIRECT_REF:
2439     case INDIRECT_REF:
2440       /* Whether a dereference is readonly has nothing to do with whether
2441          its operand is readonly.  */
2442       TREE_READONLY (t) = 0;
2443       break;
2444
2445     case ADDR_EXPR:
2446       if (node)
2447         recompute_tree_invarant_for_addr_expr (t);
2448       break;
2449
2450     default:
2451       if (TREE_CODE_CLASS (code) == tcc_unary
2452           && node && !TYPE_P (node)
2453           && TREE_CONSTANT (node))
2454         TREE_CONSTANT (t) = 1;
2455       if (TREE_CODE_CLASS (code) == tcc_unary
2456           && node && TREE_INVARIANT (node))
2457         TREE_INVARIANT (t) = 1;
2458       if (TREE_CODE_CLASS (code) == tcc_reference
2459           && node && TREE_THIS_VOLATILE (node))
2460         TREE_THIS_VOLATILE (t) = 1;
2461       break;
2462     }
2463
2464   return t;
2465 }
2466
2467 #define PROCESS_ARG(N)                  \
2468   do {                                  \
2469     TREE_OPERAND (t, N) = arg##N;       \
2470     if (arg##N &&!TYPE_P (arg##N) && fro > N) \
2471       {                                 \
2472         if (TREE_SIDE_EFFECTS (arg##N)) \
2473           side_effects = 1;             \
2474         if (!TREE_READONLY (arg##N))    \
2475           read_only = 0;                \
2476         if (!TREE_CONSTANT (arg##N))    \
2477           constant = 0;                 \
2478         if (!TREE_INVARIANT (arg##N))   \
2479           invariant = 0;                \
2480       }                                 \
2481   } while (0)
2482
2483 tree
2484 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2485 {
2486   bool constant, read_only, side_effects, invariant;
2487   tree t;
2488   int fro;
2489
2490   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2491
2492   t = make_node_stat (code PASS_MEM_STAT);
2493   TREE_TYPE (t) = tt;
2494
2495   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2496      result based on those same flags for the arguments.  But if the
2497      arguments aren't really even `tree' expressions, we shouldn't be trying
2498      to do this.  */
2499   fro = first_rtl_op (code);
2500
2501   /* Expressions without side effects may be constant if their
2502      arguments are as well.  */
2503   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2504               || TREE_CODE_CLASS (code) == tcc_binary);
2505   read_only = 1;
2506   side_effects = TREE_SIDE_EFFECTS (t);
2507   invariant = constant;
2508
2509   PROCESS_ARG(0);
2510   PROCESS_ARG(1);
2511
2512   TREE_READONLY (t) = read_only;
2513   TREE_CONSTANT (t) = constant;
2514   TREE_INVARIANT (t) = invariant;
2515   TREE_SIDE_EFFECTS (t) = side_effects;
2516   TREE_THIS_VOLATILE (t)
2517     = (TREE_CODE_CLASS (code) == tcc_reference
2518        && arg0 && TREE_THIS_VOLATILE (arg0));
2519
2520   return t;
2521 }
2522
2523 tree
2524 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2525              tree arg2 MEM_STAT_DECL)
2526 {
2527   bool constant, read_only, side_effects, invariant;
2528   tree t;
2529   int fro;
2530
2531   gcc_assert (TREE_CODE_LENGTH (code) == 3);
2532
2533   t = make_node_stat (code PASS_MEM_STAT);
2534   TREE_TYPE (t) = tt;
2535
2536   fro = first_rtl_op (code);
2537
2538   side_effects = TREE_SIDE_EFFECTS (t);
2539
2540   PROCESS_ARG(0);
2541   PROCESS_ARG(1);
2542   PROCESS_ARG(2);
2543
2544   if (code == CALL_EXPR && !side_effects)
2545     {
2546       tree node;
2547       int i;
2548
2549       /* Calls have side-effects, except those to const or
2550          pure functions.  */
2551       i = call_expr_flags (t);
2552       if (!(i & (ECF_CONST | ECF_PURE)))
2553         side_effects = 1;
2554
2555       /* And even those have side-effects if their arguments do.  */
2556       else for (node = arg1; node; node = TREE_CHAIN (node))
2557         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2558           {
2559             side_effects = 1;
2560             break;
2561           }
2562     }
2563
2564   TREE_SIDE_EFFECTS (t) = side_effects;
2565   TREE_THIS_VOLATILE (t)
2566     = (TREE_CODE_CLASS (code) == tcc_reference
2567        && arg0 && TREE_THIS_VOLATILE (arg0));
2568
2569   return t;
2570 }
2571
2572 tree
2573 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2574              tree arg2, tree arg3 MEM_STAT_DECL)
2575 {
2576   bool constant, read_only, side_effects, invariant;
2577   tree t;
2578   int fro;
2579
2580   gcc_assert (TREE_CODE_LENGTH (code) == 4);
2581
2582   t = make_node_stat (code PASS_MEM_STAT);
2583   TREE_TYPE (t) = tt;
2584
2585   fro = first_rtl_op (code);
2586
2587   side_effects = TREE_SIDE_EFFECTS (t);
2588
2589   PROCESS_ARG(0);
2590   PROCESS_ARG(1);
2591   PROCESS_ARG(2);
2592   PROCESS_ARG(3);
2593
2594   TREE_SIDE_EFFECTS (t) = side_effects;
2595   TREE_THIS_VOLATILE (t)
2596     = (TREE_CODE_CLASS (code) == tcc_reference
2597        && arg0 && TREE_THIS_VOLATILE (arg0));
2598
2599   return t;
2600 }
2601
2602 /* Backup definition for non-gcc build compilers.  */
2603
2604 tree
2605 (build) (enum tree_code code, tree tt, ...)
2606 {
2607   tree t, arg0, arg1, arg2, arg3;
2608   int length = TREE_CODE_LENGTH (code);
2609   va_list p;
2610
2611   va_start (p, tt);
2612   switch (length)
2613     {
2614     case 0:
2615       t = build0 (code, tt);
2616       break;
2617     case 1:
2618       arg0 = va_arg (p, tree);
2619       t = build1 (code, tt, arg0);
2620       break;
2621     case 2:
2622       arg0 = va_arg (p, tree);
2623       arg1 = va_arg (p, tree);
2624       t = build2 (code, tt, arg0, arg1);
2625       break;
2626     case 3:
2627       arg0 = va_arg (p, tree);
2628       arg1 = va_arg (p, tree);
2629       arg2 = va_arg (p, tree);
2630       t = build3 (code, tt, arg0, arg1, arg2);
2631       break;
2632     case 4:
2633       arg0 = va_arg (p, tree);
2634       arg1 = va_arg (p, tree);
2635       arg2 = va_arg (p, tree);
2636       arg3 = va_arg (p, tree);
2637       t = build4 (code, tt, arg0, arg1, arg2, arg3);
2638       break;
2639     default:
2640       gcc_unreachable ();
2641     }
2642   va_end (p);
2643
2644   return t;
2645 }
2646
2647 /* Similar except don't specify the TREE_TYPE
2648    and leave the TREE_SIDE_EFFECTS as 0.
2649    It is permissible for arguments to be null,
2650    or even garbage if their values do not matter.  */
2651
2652 tree
2653 build_nt (enum tree_code code, ...)
2654 {
2655   tree t;
2656   int length;
2657   int i;
2658   va_list p;
2659
2660   va_start (p, code);
2661
2662   t = make_node (code);
2663   length = TREE_CODE_LENGTH (code);
2664
2665   for (i = 0; i < length; i++)
2666     TREE_OPERAND (t, i) = va_arg (p, tree);
2667
2668   va_end (p);
2669   return t;
2670 }
2671 \f
2672 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
2673    We do NOT enter this node in any sort of symbol table.
2674
2675    layout_decl is used to set up the decl's storage layout.
2676    Other slots are initialized to 0 or null pointers.  */
2677
2678 tree
2679 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
2680 {
2681   tree t;
2682
2683   t = make_node_stat (code PASS_MEM_STAT);
2684
2685 /*  if (type == error_mark_node)
2686     type = integer_type_node; */
2687 /* That is not done, deliberately, so that having error_mark_node
2688    as the type can suppress useless errors in the use of this variable.  */
2689
2690   DECL_NAME (t) = name;
2691   TREE_TYPE (t) = type;
2692
2693   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
2694     layout_decl (t, 0);
2695   else if (code == FUNCTION_DECL)
2696     DECL_MODE (t) = FUNCTION_MODE;
2697
2698   /* Set default visibility to whatever the user supplied with
2699      visibility_specified depending on #pragma GCC visibility.  */
2700   DECL_VISIBILITY (t) = default_visibility;
2701   DECL_VISIBILITY_SPECIFIED (t) = visibility_options.inpragma;
2702
2703   return t;
2704 }
2705 \f
2706 /* BLOCK nodes are used to represent the structure of binding contours
2707    and declarations, once those contours have been exited and their contents
2708    compiled.  This information is used for outputting debugging info.  */
2709
2710 tree
2711 build_block (tree vars, tree tags ATTRIBUTE_UNUSED, tree subblocks,
2712              tree supercontext, tree chain)
2713 {
2714   tree block = make_node (BLOCK);
2715
2716   BLOCK_VARS (block) = vars;
2717   BLOCK_SUBBLOCKS (block) = subblocks;
2718   BLOCK_SUPERCONTEXT (block) = supercontext;
2719   BLOCK_CHAIN (block) = chain;
2720   return block;
2721 }
2722
2723 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
2724 /* ??? gengtype doesn't handle conditionals */
2725 static GTY(()) tree last_annotated_node;
2726 #endif
2727
2728 #ifdef USE_MAPPED_LOCATION
2729
2730 expanded_location
2731 expand_location (source_location loc)
2732 {
2733   expanded_location xloc;
2734   if (loc == 0) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
2735   else
2736     {
2737       const struct line_map *map = linemap_lookup (&line_table, loc);
2738       xloc.file = map->to_file;
2739       xloc.line = SOURCE_LINE (map, loc);
2740       xloc.column = SOURCE_COLUMN (map, loc);
2741     };
2742   return xloc;
2743 }
2744
2745 #else
2746
2747 /* Record the exact location where an expression or an identifier were
2748    encountered.  */
2749
2750 void
2751 annotate_with_file_line (tree node, const char *file, int line)
2752 {
2753   /* Roughly one percent of the calls to this function are to annotate
2754      a node with the same information already attached to that node!
2755      Just return instead of wasting memory.  */
2756   if (EXPR_LOCUS (node)
2757       && (EXPR_FILENAME (node) == file
2758           || ! strcmp (EXPR_FILENAME (node), file))
2759       && EXPR_LINENO (node) == line)
2760     {
2761       last_annotated_node = node;
2762       return;
2763     }
2764
2765   /* In heavily macroized code (such as GCC itself) this single
2766      entry cache can reduce the number of allocations by more
2767      than half.  */
2768   if (last_annotated_node
2769       && EXPR_LOCUS (last_annotated_node)
2770       && (EXPR_FILENAME (last_annotated_node) == file
2771           || ! strcmp (EXPR_FILENAME (last_annotated_node), file))
2772       && EXPR_LINENO (last_annotated_node) == line)
2773     {
2774       SET_EXPR_LOCUS (node, EXPR_LOCUS (last_annotated_node));
2775       return;
2776     }
2777
2778   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
2779   EXPR_LINENO (node) = line;
2780   EXPR_FILENAME (node) = file;
2781   last_annotated_node = node;
2782 }
2783
2784 void
2785 annotate_with_locus (tree node, location_t locus)
2786 {
2787   annotate_with_file_line (node, locus.file, locus.line);
2788 }
2789 #endif
2790 \f
2791 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
2792    is ATTRIBUTE.  */
2793
2794 tree
2795 build_decl_attribute_variant (tree ddecl, tree attribute)
2796 {
2797   DECL_ATTRIBUTES (ddecl) = attribute;
2798   return ddecl;
2799 }
2800
2801 /* Borrowed from hashtab.c iterative_hash implementation.  */
2802 #define mix(a,b,c) \
2803 { \
2804   a -= b; a -= c; a ^= (c>>13); \
2805   b -= c; b -= a; b ^= (a<< 8); \
2806   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
2807   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
2808   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
2809   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
2810   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
2811   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
2812   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
2813 }
2814
2815
2816 /* Produce good hash value combining VAL and VAL2.  */
2817 static inline hashval_t
2818 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
2819 {
2820   /* the golden ratio; an arbitrary value.  */
2821   hashval_t a = 0x9e3779b9;
2822
2823   mix (a, val, val2);
2824   return val2;
2825 }
2826
2827 /* Produce good hash value combining PTR and VAL2.  */
2828 static inline hashval_t
2829 iterative_hash_pointer (void *ptr, hashval_t val2)
2830 {
2831   if (sizeof (ptr) == sizeof (hashval_t))
2832     return iterative_hash_hashval_t ((size_t) ptr, val2);
2833   else
2834     {
2835       hashval_t a = (hashval_t) (size_t) ptr;
2836       /* Avoid warnings about shifting of more than the width of the type on
2837          hosts that won't execute this path.  */
2838       int zero = 0;
2839       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
2840       mix (a, b, val2);
2841       return val2;
2842     }
2843 }
2844
2845 /* Produce good hash value combining VAL and VAL2.  */
2846 static inline hashval_t
2847 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
2848 {
2849   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
2850     return iterative_hash_hashval_t (val, val2);
2851   else
2852     {
2853       hashval_t a = (hashval_t) val;
2854       /* Avoid warnings about shifting of more than the width of the type on
2855          hosts that won't execute this path.  */
2856       int zero = 0;
2857       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
2858       mix (a, b, val2);
2859       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
2860         {
2861           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
2862           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
2863           mix (a, b, val2);
2864         }
2865       return val2;
2866     }
2867 }
2868
2869 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
2870    is ATTRIBUTE.
2871
2872    Record such modified types already made so we don't make duplicates.  */
2873
2874 tree
2875 build_type_attribute_variant (tree ttype, tree attribute)
2876 {
2877   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
2878     {
2879       hashval_t hashcode = 0;
2880       tree ntype;
2881       enum tree_code code = TREE_CODE (ttype);
2882
2883       ntype = copy_node (ttype);
2884
2885       TYPE_POINTER_TO (ntype) = 0;
2886       TYPE_REFERENCE_TO (ntype) = 0;
2887       TYPE_ATTRIBUTES (ntype) = attribute;
2888
2889       /* Create a new main variant of TYPE.  */
2890       TYPE_MAIN_VARIANT (ntype) = ntype;
2891       TYPE_NEXT_VARIANT (ntype) = 0;
2892       set_type_quals (ntype, TYPE_UNQUALIFIED);
2893
2894       hashcode = iterative_hash_object (code, hashcode);
2895       if (TREE_TYPE (ntype))
2896         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
2897                                           hashcode);
2898       hashcode = attribute_hash_list (attribute, hashcode);
2899
2900       switch (TREE_CODE (ntype))
2901         {
2902         case FUNCTION_TYPE:
2903           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
2904           break;
2905         case ARRAY_TYPE:
2906           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
2907                                             hashcode);
2908           break;
2909         case INTEGER_TYPE:
2910           hashcode = iterative_hash_object
2911             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
2912           hashcode = iterative_hash_object
2913             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
2914           break;
2915         case REAL_TYPE:
2916           {
2917             unsigned int precision = TYPE_PRECISION (ntype);
2918             hashcode = iterative_hash_object (precision, hashcode);
2919           }
2920           break;
2921         default:
2922           break;
2923         }
2924
2925       ntype = type_hash_canon (hashcode, ntype);
2926       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
2927     }
2928
2929   return ttype;
2930 }
2931
2932 /* Return nonzero if IDENT is a valid name for attribute ATTR,
2933    or zero if not.
2934
2935    We try both `text' and `__text__', ATTR may be either one.  */
2936 /* ??? It might be a reasonable simplification to require ATTR to be only
2937    `text'.  One might then also require attribute lists to be stored in
2938    their canonicalized form.  */
2939
2940 int
2941 is_attribute_p (const char *attr, tree ident)
2942 {
2943   int ident_len, attr_len;
2944   const char *p;
2945
2946   if (TREE_CODE (ident) != IDENTIFIER_NODE)
2947     return 0;
2948
2949   if (strcmp (attr, IDENTIFIER_POINTER (ident)) == 0)
2950     return 1;
2951
2952   p = IDENTIFIER_POINTER (ident);
2953   ident_len = strlen (p);
2954   attr_len = strlen (attr);
2955
2956   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
2957   if (attr[0] == '_')
2958     {
2959       gcc_assert (attr[1] == '_');
2960       gcc_assert (attr[attr_len - 2] == '_');
2961       gcc_assert (attr[attr_len - 1] == '_');
2962       gcc_assert (attr[1] == '_');
2963       if (ident_len == attr_len - 4
2964           && strncmp (attr + 2, p, attr_len - 4) == 0)
2965         return 1;
2966     }
2967   else
2968     {
2969       if (ident_len == attr_len + 4
2970           && p[0] == '_' && p[1] == '_'
2971           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
2972           && strncmp (attr, p + 2, attr_len) == 0)
2973         return 1;
2974     }
2975
2976   return 0;
2977 }
2978
2979 /* Given an attribute name and a list of attributes, return a pointer to the
2980    attribute's list element if the attribute is part of the list, or NULL_TREE
2981    if not found.  If the attribute appears more than once, this only
2982    returns the first occurrence; the TREE_CHAIN of the return value should
2983    be passed back in if further occurrences are wanted.  */
2984
2985 tree
2986 lookup_attribute (const char *attr_name, tree list)
2987 {
2988   tree l;
2989
2990   for (l = list; l; l = TREE_CHAIN (l))
2991     {
2992       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
2993       if (is_attribute_p (attr_name, TREE_PURPOSE (l)))
2994         return l;
2995     }
2996
2997   return NULL_TREE;
2998 }
2999
3000 /* Return an attribute list that is the union of a1 and a2.  */
3001
3002 tree
3003 merge_attributes (tree a1, tree a2)
3004 {
3005   tree attributes;
3006
3007   /* Either one unset?  Take the set one.  */
3008
3009   if ((attributes = a1) == 0)
3010     attributes = a2;
3011
3012   /* One that completely contains the other?  Take it.  */
3013
3014   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3015     {
3016       if (attribute_list_contained (a2, a1))
3017         attributes = a2;
3018       else
3019         {
3020           /* Pick the longest list, and hang on the other list.  */
3021
3022           if (list_length (a1) < list_length (a2))
3023             attributes = a2, a2 = a1;
3024
3025           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3026             {
3027               tree a;
3028               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3029                                          attributes);
3030                    a != NULL_TREE;
3031                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3032                                          TREE_CHAIN (a)))
3033                 {
3034                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
3035                     break;
3036                 }
3037               if (a == NULL_TREE)
3038                 {
3039                   a1 = copy_node (a2);
3040                   TREE_CHAIN (a1) = attributes;
3041                   attributes = a1;
3042                 }
3043             }
3044         }
3045     }
3046   return attributes;
3047 }
3048
3049 /* Given types T1 and T2, merge their attributes and return
3050   the result.  */
3051
3052 tree
3053 merge_type_attributes (tree t1, tree t2)
3054 {
3055   return merge_attributes (TYPE_ATTRIBUTES (t1),
3056                            TYPE_ATTRIBUTES (t2));
3057 }
3058
3059 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3060    the result.  */
3061
3062 tree
3063 merge_decl_attributes (tree olddecl, tree newdecl)
3064 {
3065   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3066                            DECL_ATTRIBUTES (newdecl));
3067 }
3068
3069 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3070
3071 /* Specialization of merge_decl_attributes for various Windows targets.
3072
3073    This handles the following situation:
3074
3075      __declspec (dllimport) int foo;
3076      int foo;
3077
3078    The second instance of `foo' nullifies the dllimport.  */
3079
3080 tree
3081 merge_dllimport_decl_attributes (tree old, tree new)
3082 {
3083   tree a;
3084   int delete_dllimport_p;
3085
3086   old = DECL_ATTRIBUTES (old);
3087   new = DECL_ATTRIBUTES (new);
3088
3089   /* What we need to do here is remove from `old' dllimport if it doesn't
3090      appear in `new'.  dllimport behaves like extern: if a declaration is
3091      marked dllimport and a definition appears later, then the object
3092      is not dllimport'd.  */
3093   if (lookup_attribute ("dllimport", old) != NULL_TREE
3094       && lookup_attribute ("dllimport", new) == NULL_TREE)
3095     delete_dllimport_p = 1;
3096   else
3097     delete_dllimport_p = 0;
3098
3099   a = merge_attributes (old, new);
3100
3101   if (delete_dllimport_p)
3102     {
3103       tree prev, t;
3104
3105       /* Scan the list for dllimport and delete it.  */
3106       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3107         {
3108           if (is_attribute_p ("dllimport", TREE_PURPOSE (t)))
3109             {
3110               if (prev == NULL_TREE)
3111                 a = TREE_CHAIN (a);
3112               else
3113                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3114               break;
3115             }
3116         }
3117     }
3118
3119   return a;
3120 }
3121
3122 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3123    struct attribute_spec.handler.  */
3124
3125 tree
3126 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3127                       bool *no_add_attrs)
3128 {
3129   tree node = *pnode;
3130
3131   /* These attributes may apply to structure and union types being created,
3132      but otherwise should pass to the declaration involved.  */
3133   if (!DECL_P (node))
3134     {
3135       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3136                    | (int) ATTR_FLAG_ARRAY_NEXT))
3137         {
3138           *no_add_attrs = true;
3139           return tree_cons (name, args, NULL_TREE);
3140         }
3141       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3142         {
3143           warning ("%qs attribute ignored", IDENTIFIER_POINTER (name));
3144           *no_add_attrs = true;
3145         }
3146
3147       return NULL_TREE;
3148     }
3149
3150   /* Report error on dllimport ambiguities seen now before they cause
3151      any damage.  */
3152   if (is_attribute_p ("dllimport", name))
3153     {
3154       /* Like MS, treat definition of dllimported variables and
3155          non-inlined functions on declaration as syntax errors.  We
3156          allow the attribute for function definitions if declared
3157          inline.  */
3158       if (TREE_CODE (node) == FUNCTION_DECL  && DECL_INITIAL (node)
3159           && !DECL_DECLARED_INLINE_P (node))
3160         {
3161           error ("%Jfunction %qD definition is marked dllimport.", node, node);
3162           *no_add_attrs = true;
3163         }
3164
3165       else if (TREE_CODE (node) == VAR_DECL)
3166         {
3167           if (DECL_INITIAL (node))
3168             {
3169               error ("%Jvariable %qD definition is marked dllimport.",
3170                      node, node);
3171               *no_add_attrs = true;
3172             }
3173
3174           /* `extern' needn't be specified with dllimport.
3175              Specify `extern' now and hope for the best.  Sigh.  */
3176           DECL_EXTERNAL (node) = 1;
3177           /* Also, implicitly give dllimport'd variables declared within
3178              a function global scope, unless declared static.  */
3179           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3180             TREE_PUBLIC (node) = 1;
3181         }
3182     }
3183
3184   /*  Report error if symbol is not accessible at global scope.  */
3185   if (!TREE_PUBLIC (node)
3186       && (TREE_CODE (node) == VAR_DECL
3187           || TREE_CODE (node) == FUNCTION_DECL))
3188     {
3189       error ("%Jexternal linkage required for symbol %qD because of "
3190              "%qs attribute.", node, node, IDENTIFIER_POINTER (name));
3191       *no_add_attrs = true;
3192     }
3193
3194   return NULL_TREE;
3195 }
3196
3197 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3198 \f
3199 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3200    of the various TYPE_QUAL values.  */
3201
3202 static void
3203 set_type_quals (tree type, int type_quals)
3204 {
3205   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3206   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3207   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3208 }
3209
3210 /* Returns true iff cand is equivalent to base with type_quals.  */
3211
3212 bool
3213 check_qualified_type (tree cand, tree base, int type_quals)
3214 {
3215   return (TYPE_QUALS (cand) == type_quals
3216           && TYPE_NAME (cand) == TYPE_NAME (base)
3217           /* Apparently this is needed for Objective-C.  */
3218           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3219           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3220                                    TYPE_ATTRIBUTES (base)));
3221 }
3222
3223 /* Return a version of the TYPE, qualified as indicated by the
3224    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3225    return NULL_TREE.  */
3226
3227 tree
3228 get_qualified_type (tree type, int type_quals)
3229 {
3230   tree t;
3231
3232   if (TYPE_QUALS (type) == type_quals)
3233     return type;
3234
3235   /* Search the chain of variants to see if there is already one there just
3236      like the one we need to have.  If so, use that existing one.  We must
3237      preserve the TYPE_NAME, since there is code that depends on this.  */
3238   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3239     if (check_qualified_type (t, type, type_quals))
3240       return t;
3241
3242   return NULL_TREE;
3243 }
3244
3245 /* Like get_qualified_type, but creates the type if it does not
3246    exist.  This function never returns NULL_TREE.  */
3247
3248 tree
3249 build_qualified_type (tree type, int type_quals)
3250 {
3251   tree t;
3252
3253   /* See if we already have the appropriate qualified variant.  */
3254   t = get_qualified_type (type, type_quals);
3255
3256   /* If not, build it.  */
3257   if (!t)
3258     {
3259       t = build_variant_type_copy (type);
3260       set_type_quals (t, type_quals);
3261     }
3262
3263   return t;
3264 }
3265
3266 /* Create a new distinct copy of TYPE.  The new type is made its own
3267    MAIN_VARIANT.  */
3268
3269 tree
3270 build_distinct_type_copy (tree type)
3271 {
3272   tree t = copy_node (type);
3273
3274   TYPE_POINTER_TO (t) = 0;
3275   TYPE_REFERENCE_TO (t) = 0;
3276
3277   /* Make it its own variant.  */
3278   TYPE_MAIN_VARIANT (t) = t;
3279   TYPE_NEXT_VARIANT (t) = 0;
3280
3281   return t;
3282 }
3283
3284 /* Create a new variant of TYPE, equivalent but distinct.
3285    This is so the caller can modify it.  */
3286
3287 tree
3288 build_variant_type_copy (tree type)
3289 {
3290   tree t, m = TYPE_MAIN_VARIANT (type);
3291
3292   t = build_distinct_type_copy (type);
3293
3294   /* Add the new type to the chain of variants of TYPE.  */
3295   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3296   TYPE_NEXT_VARIANT (m) = t;
3297   TYPE_MAIN_VARIANT (t) = m;
3298
3299   return t;
3300 }
3301 \f
3302 /* Hashing of types so that we don't make duplicates.
3303    The entry point is `type_hash_canon'.  */
3304
3305 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
3306    with types in the TREE_VALUE slots), by adding the hash codes
3307    of the individual types.  */
3308
3309 unsigned int
3310 type_hash_list (tree list, hashval_t hashcode)
3311 {
3312   tree tail;
3313
3314   for (tail = list; tail; tail = TREE_CHAIN (tail))
3315     if (TREE_VALUE (tail) != error_mark_node)
3316       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
3317                                         hashcode);
3318
3319   return hashcode;
3320 }
3321
3322 /* These are the Hashtable callback functions.  */
3323
3324 /* Returns true iff the types are equivalent.  */
3325
3326 static int
3327 type_hash_eq (const void *va, const void *vb)
3328 {
3329   const struct type_hash *a = va, *b = vb;
3330
3331   /* First test the things that are the same for all types.  */
3332   if (a->hash != b->hash
3333       || TREE_CODE (a->type) != TREE_CODE (b->type)
3334       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
3335       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
3336                                  TYPE_ATTRIBUTES (b->type))
3337       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
3338       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
3339     return 0;
3340
3341   switch (TREE_CODE (a->type))
3342     {
3343     case VOID_TYPE:
3344     case COMPLEX_TYPE:
3345     case VECTOR_TYPE:
3346     case POINTER_TYPE:
3347     case REFERENCE_TYPE:
3348       return 1;
3349
3350     case ENUMERAL_TYPE:
3351       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
3352           && !(TYPE_VALUES (a->type)
3353                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
3354                && TYPE_VALUES (b->type)
3355                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
3356                && type_list_equal (TYPE_VALUES (a->type),
3357                                    TYPE_VALUES (b->type))))
3358         return 0;
3359
3360       /* ... fall through ... */
3361
3362     case INTEGER_TYPE:
3363     case REAL_TYPE:
3364     case BOOLEAN_TYPE:
3365     case CHAR_TYPE:
3366       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
3367                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
3368                                       TYPE_MAX_VALUE (b->type)))
3369               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
3370                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
3371                                          TYPE_MIN_VALUE (b->type))));
3372
3373     case OFFSET_TYPE:
3374       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
3375
3376     case METHOD_TYPE:
3377       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
3378               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3379                   || (TYPE_ARG_TYPES (a->type)
3380                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3381                       && TYPE_ARG_TYPES (b->type)
3382                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3383                       && type_list_equal (TYPE_ARG_TYPES (a->type),
3384                                           TYPE_ARG_TYPES (b->type)))));
3385
3386     case ARRAY_TYPE:
3387     case SET_TYPE:
3388       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
3389
3390     case RECORD_TYPE:
3391     case UNION_TYPE:
3392     case QUAL_UNION_TYPE:
3393       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
3394               || (TYPE_FIELDS (a->type)
3395                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
3396                   && TYPE_FIELDS (b->type)
3397                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
3398                   && type_list_equal (TYPE_FIELDS (a->type),
3399                                       TYPE_FIELDS (b->type))));
3400
3401     case FUNCTION_TYPE:
3402       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
3403               || (TYPE_ARG_TYPES (a->type)
3404                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
3405                   && TYPE_ARG_TYPES (b->type)
3406                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
3407                   && type_list_equal (TYPE_ARG_TYPES (a->type),
3408                                       TYPE_ARG_TYPES (b->type))));
3409
3410     default:
3411       return 0;
3412     }
3413 }
3414
3415 /* Return the cached hash value.  */
3416
3417 static hashval_t
3418 type_hash_hash (const void *item)
3419 {
3420   return ((const struct type_hash *) item)->hash;
3421 }
3422
3423 /* Look in the type hash table for a type isomorphic to TYPE.
3424    If one is found, return it.  Otherwise return 0.  */
3425
3426 tree
3427 type_hash_lookup (hashval_t hashcode, tree type)
3428 {
3429   struct type_hash *h, in;
3430
3431   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
3432      must call that routine before comparing TYPE_ALIGNs.  */
3433   layout_type (type);
3434
3435   in.hash = hashcode;
3436   in.type = type;
3437
3438   h = htab_find_with_hash (type_hash_table, &in, hashcode);
3439   if (h)
3440     return h->type;
3441   return NULL_TREE;
3442 }
3443
3444 /* Add an entry to the type-hash-table
3445    for a type TYPE whose hash code is HASHCODE.  */
3446
3447 void
3448 type_hash_add (hashval_t hashcode, tree type)
3449 {
3450   struct type_hash *h;
3451   void **loc;
3452
3453   h = ggc_alloc (sizeof (struct type_hash));
3454   h->hash = hashcode;
3455   h->type = type;
3456   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
3457   *(struct type_hash **) loc = h;
3458 }
3459
3460 /* Given TYPE, and HASHCODE its hash code, return the canonical
3461    object for an identical type if one already exists.
3462    Otherwise, return TYPE, and record it as the canonical object.
3463
3464    To use this function, first create a type of the sort you want.
3465    Then compute its hash code from the fields of the type that
3466    make it different from other similar types.
3467    Then call this function and use the value.  */
3468
3469 tree
3470 type_hash_canon (unsigned int hashcode, tree type)
3471 {
3472   tree t1;
3473
3474   /* The hash table only contains main variants, so ensure that's what we're
3475      being passed.  */
3476   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
3477
3478   if (!lang_hooks.types.hash_types)
3479     return type;
3480
3481   /* See if the type is in the hash table already.  If so, return it.
3482      Otherwise, add the type.  */
3483   t1 = type_hash_lookup (hashcode, type);
3484   if (t1 != 0)
3485     {
3486 #ifdef GATHER_STATISTICS
3487       tree_node_counts[(int) t_kind]--;
3488       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
3489 #endif
3490       return t1;
3491     }
3492   else
3493     {
3494       type_hash_add (hashcode, type);
3495       return type;
3496     }
3497 }
3498
3499 /* See if the data pointed to by the type hash table is marked.  We consider
3500    it marked if the type is marked or if a debug type number or symbol
3501    table entry has been made for the type.  This reduces the amount of
3502    debugging output and eliminates that dependency of the debug output on
3503    the number of garbage collections.  */
3504
3505 static int
3506 type_hash_marked_p (const void *p)
3507 {
3508   tree type = ((struct type_hash *) p)->type;
3509
3510   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
3511 }
3512
3513 static void
3514 print_type_hash_statistics (void)
3515 {
3516   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
3517            (long) htab_size (type_hash_table),
3518            (long) htab_elements (type_hash_table),
3519            htab_collisions (type_hash_table));
3520 }
3521
3522 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
3523    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
3524    by adding the hash codes of the individual attributes.  */
3525
3526 unsigned int
3527 attribute_hash_list (tree list, hashval_t hashcode)
3528 {
3529   tree tail;
3530
3531   for (tail = list; tail; tail = TREE_CHAIN (tail))
3532     /* ??? Do we want to add in TREE_VALUE too? */
3533     hashcode = iterative_hash_object
3534       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
3535   return hashcode;
3536 }
3537
3538 /* Given two lists of attributes, return true if list l2 is
3539    equivalent to l1.  */
3540
3541 int
3542 attribute_list_equal (tree l1, tree l2)
3543 {
3544   return attribute_list_contained (l1, l2)
3545          && attribute_list_contained (l2, l1);
3546 }
3547
3548 /* Given two lists of attributes, return true if list L2 is
3549    completely contained within L1.  */
3550 /* ??? This would be faster if attribute names were stored in a canonicalized
3551    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
3552    must be used to show these elements are equivalent (which they are).  */
3553 /* ??? It's not clear that attributes with arguments will always be handled
3554    correctly.  */
3555
3556 int
3557 attribute_list_contained (tree l1, tree l2)
3558 {
3559   tree t1, t2;
3560
3561   /* First check the obvious, maybe the lists are identical.  */
3562   if (l1 == l2)
3563     return 1;
3564
3565   /* Maybe the lists are similar.  */
3566   for (t1 = l1, t2 = l2;
3567        t1 != 0 && t2 != 0
3568         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
3569         && TREE_VALUE (t1) == TREE_VALUE (t2);
3570        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
3571
3572   /* Maybe the lists are equal.  */
3573   if (t1 == 0 && t2 == 0)
3574     return 1;
3575
3576   for (; t2 != 0; t2 = TREE_CHAIN (t2))
3577     {
3578       tree attr;
3579       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
3580            attr != NULL_TREE;
3581            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
3582                                     TREE_CHAIN (attr)))
3583         {
3584           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
3585             break;
3586         }
3587
3588       if (attr == 0)
3589         return 0;
3590
3591       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
3592         return 0;
3593     }
3594
3595   return 1;
3596 }
3597
3598 /* Given two lists of types
3599    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
3600    return 1 if the lists contain the same types in the same order.
3601    Also, the TREE_PURPOSEs must match.  */
3602
3603 int
3604 type_list_equal (tree l1, tree l2)
3605 {
3606   tree t1, t2;
3607
3608   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
3609     if (TREE_VALUE (t1) != TREE_VALUE (t2)
3610         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
3611             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
3612                   && (TREE_TYPE (TREE_PURPOSE (t1))
3613                       == TREE_TYPE (TREE_PURPOSE (t2))))))
3614       return 0;
3615
3616   return t1 == t2;
3617 }
3618
3619 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
3620    given by TYPE.  If the argument list accepts variable arguments,
3621    then this function counts only the ordinary arguments.  */
3622
3623 int
3624 type_num_arguments (tree type)
3625 {
3626   int i = 0;
3627   tree t;
3628
3629   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
3630     /* If the function does not take a variable number of arguments,
3631        the last element in the list will have type `void'.  */
3632     if (VOID_TYPE_P (TREE_VALUE (t)))
3633       break;
3634     else
3635       ++i;
3636
3637   return i;
3638 }
3639
3640 /* Nonzero if integer constants T1 and T2
3641    represent the same constant value.  */
3642
3643 int
3644 tree_int_cst_equal (tree t1, tree t2)
3645 {
3646   if (t1 == t2)
3647     return 1;
3648
3649   if (t1 == 0 || t2 == 0)
3650     return 0;
3651
3652   if (TREE_CODE (t1) == INTEGER_CST
3653       && TREE_CODE (t2) == INTEGER_CST
3654       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3655       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
3656     return 1;
3657
3658   return 0;
3659 }
3660
3661 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
3662    The precise way of comparison depends on their data type.  */
3663
3664 int
3665 tree_int_cst_lt (tree t1, tree t2)
3666 {
3667   if (t1 == t2)
3668     return 0;
3669
3670   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
3671     {
3672       int t1_sgn = tree_int_cst_sgn (t1);
3673       int t2_sgn = tree_int_cst_sgn (t2);
3674
3675       if (t1_sgn < t2_sgn)
3676         return 1;
3677       else if (t1_sgn > t2_sgn)
3678         return 0;
3679       /* Otherwise, both are non-negative, so we compare them as
3680          unsigned just in case one of them would overflow a signed
3681          type.  */
3682     }
3683   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
3684     return INT_CST_LT (t1, t2);
3685
3686   return INT_CST_LT_UNSIGNED (t1, t2);
3687 }
3688
3689 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
3690
3691 int
3692 tree_int_cst_compare (tree t1, tree t2)
3693 {
3694   if (tree_int_cst_lt (t1, t2))
3695     return -1;
3696   else if (tree_int_cst_lt (t2, t1))
3697     return 1;
3698   else
3699     return 0;
3700 }
3701
3702 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
3703    the host.  If POS is zero, the value can be represented in a single
3704    HOST_WIDE_INT.  If POS is nonzero, the value must be positive and can
3705    be represented in a single unsigned HOST_WIDE_INT.  */
3706
3707 int
3708 host_integerp (tree t, int pos)
3709 {
3710   return (TREE_CODE (t) == INTEGER_CST
3711           && ! TREE_OVERFLOW (t)
3712           && ((TREE_INT_CST_HIGH (t) == 0
3713                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
3714               || (! pos && TREE_INT_CST_HIGH (t) == -1
3715                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
3716                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
3717               || (pos && TREE_INT_CST_HIGH (t) == 0)));
3718 }
3719
3720 /* Return the HOST_WIDE_INT least significant bits of T if it is an
3721    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
3722    be positive.  Abort if we cannot satisfy the above conditions.  */
3723
3724 HOST_WIDE_INT
3725 tree_low_cst (tree t, int pos)
3726 {
3727   gcc_assert (host_integerp (t, pos));
3728   return TREE_INT_CST_LOW (t);
3729 }
3730
3731 /* Return the most significant bit of the integer constant T.  */
3732
3733 int
3734 tree_int_cst_msb (tree t)
3735 {
3736   int prec;
3737   HOST_WIDE_INT h;
3738   unsigned HOST_WIDE_INT l;
3739
3740   /* Note that using TYPE_PRECISION here is wrong.  We care about the
3741      actual bits, not the (arbitrary) range of the type.  */
3742   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
3743   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
3744                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
3745   return (l & 1) == 1;
3746 }
3747
3748 /* Return an indication of the sign of the integer constant T.
3749    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
3750    Note that -1 will never be returned it T's type is unsigned.  */
3751
3752 int
3753 tree_int_cst_sgn (tree t)
3754 {
3755   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
3756     return 0;
3757   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
3758     return 1;
3759   else if (TREE_INT_CST_HIGH (t) < 0)
3760     return -1;
3761   else
3762     return 1;
3763 }
3764
3765 /* Compare two constructor-element-type constants.  Return 1 if the lists
3766    are known to be equal; otherwise return 0.  */
3767
3768 int
3769 simple_cst_list_equal (tree l1, tree l2)
3770 {
3771   while (l1 != NULL_TREE && l2 != NULL_TREE)
3772     {
3773       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
3774         return 0;
3775
3776       l1 = TREE_CHAIN (l1);
3777       l2 = TREE_CHAIN (l2);
3778     }
3779
3780   return l1 == l2;
3781 }
3782
3783 /* Return truthvalue of whether T1 is the same tree structure as T2.
3784    Return 1 if they are the same.
3785    Return 0 if they are understandably different.
3786    Return -1 if either contains tree structure not understood by
3787    this function.  */
3788
3789 int
3790 simple_cst_equal (tree t1, tree t2)
3791 {
3792   enum tree_code code1, code2;
3793   int cmp;
3794   int i;
3795
3796   if (t1 == t2)
3797     return 1;
3798   if (t1 == 0 || t2 == 0)
3799     return 0;
3800
3801   code1 = TREE_CODE (t1);
3802   code2 = TREE_CODE (t2);
3803
3804   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
3805     {
3806       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3807           || code2 == NON_LVALUE_EXPR)
3808         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3809       else
3810         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
3811     }
3812
3813   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
3814            || code2 == NON_LVALUE_EXPR)
3815     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
3816
3817   if (code1 != code2)
3818     return 0;
3819
3820   switch (code1)
3821     {
3822     case INTEGER_CST:
3823       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
3824               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
3825
3826     case REAL_CST:
3827       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
3828
3829     case STRING_CST:
3830       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3831               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3832                          TREE_STRING_LENGTH (t1)));
3833
3834     case CONSTRUCTOR:
3835       return simple_cst_list_equal (CONSTRUCTOR_ELTS (t1),
3836                                     CONSTRUCTOR_ELTS (t2));
3837
3838     case SAVE_EXPR:
3839       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3840
3841     case CALL_EXPR:
3842       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3843       if (cmp <= 0)
3844         return cmp;
3845       return
3846         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3847
3848     case TARGET_EXPR:
3849       /* Special case: if either target is an unallocated VAR_DECL,
3850          it means that it's going to be unified with whatever the
3851          TARGET_EXPR is really supposed to initialize, so treat it
3852          as being equivalent to anything.  */
3853       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
3854            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
3855            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
3856           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
3857               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
3858               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
3859         cmp = 1;
3860       else
3861         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3862
3863       if (cmp <= 0)
3864         return cmp;
3865
3866       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3867
3868     case WITH_CLEANUP_EXPR:
3869       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3870       if (cmp <= 0)
3871         return cmp;
3872
3873       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
3874
3875     case COMPONENT_REF:
3876       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
3877         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3878
3879       return 0;
3880
3881     case VAR_DECL:
3882     case PARM_DECL:
3883     case CONST_DECL:
3884     case FUNCTION_DECL:
3885       return 0;
3886
3887     default:
3888       break;
3889     }
3890
3891   /* This general rule works for most tree codes.  All exceptions should be
3892      handled above.  If this is a language-specific tree code, we can't
3893      trust what might be in the operand, so say we don't know
3894      the situation.  */
3895   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
3896     return -1;
3897
3898   switch (TREE_CODE_CLASS (code1))
3899     {
3900     case tcc_unary:
3901     case tcc_binary:
3902     case tcc_comparison:
3903     case tcc_expression:
3904     case tcc_reference:
3905     case tcc_statement:
3906       cmp = 1;
3907       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
3908         {
3909           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
3910           if (cmp <= 0)
3911             return cmp;
3912         }
3913
3914       return cmp;
3915
3916     default:
3917       return -1;
3918     }
3919 }
3920
3921 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
3922    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
3923    than U, respectively.  */
3924
3925 int
3926 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
3927 {
3928   if (tree_int_cst_sgn (t) < 0)
3929     return -1;
3930   else if (TREE_INT_CST_HIGH (t) != 0)
3931     return 1;
3932   else if (TREE_INT_CST_LOW (t) == u)
3933     return 0;
3934   else if (TREE_INT_CST_LOW (t) < u)
3935     return -1;
3936   else
3937     return 1;
3938 }
3939
3940 /* Return true if CODE represents an associative tree code.  Otherwise
3941    return false.  */
3942 bool
3943 associative_tree_code (enum tree_code code)
3944 {
3945   switch (code)
3946     {
3947     case BIT_IOR_EXPR:
3948     case BIT_AND_EXPR:
3949     case BIT_XOR_EXPR:
3950     case PLUS_EXPR:
3951     case MULT_EXPR:
3952     case MIN_EXPR:
3953     case MAX_EXPR:
3954       return true;
3955
3956     default:
3957       break;
3958     }
3959   return false;
3960 }
3961
3962 /* Return true if CODE represents an commutative tree code.  Otherwise
3963    return false.  */
3964 bool
3965 commutative_tree_code (enum tree_code code)
3966 {
3967   switch (code)
3968     {
3969     case PLUS_EXPR:
3970     case MULT_EXPR:
3971     case MIN_EXPR:
3972     case MAX_EXPR:
3973     case BIT_IOR_EXPR:
3974     case BIT_XOR_EXPR:
3975     case BIT_AND_EXPR:
3976     case NE_EXPR:
3977     case EQ_EXPR:
3978     case UNORDERED_EXPR:
3979     case ORDERED_EXPR:
3980     case UNEQ_EXPR:
3981     case LTGT_EXPR:
3982     case TRUTH_AND_EXPR:
3983     case TRUTH_XOR_EXPR:
3984     case TRUTH_OR_EXPR:
3985       return true;
3986
3987     default:
3988       break;
3989     }
3990   return false;
3991 }
3992
3993 /* Generate a hash value for an expression.  This can be used iteratively
3994    by passing a previous result as the "val" argument.
3995
3996    This function is intended to produce the same hash for expressions which
3997    would compare equal using operand_equal_p.  */
3998
3999 hashval_t
4000 iterative_hash_expr (tree t, hashval_t val)
4001 {
4002   int i;
4003   enum tree_code code;
4004   char class;
4005
4006   if (t == NULL_TREE)
4007     return iterative_hash_pointer (t, val);
4008
4009   code = TREE_CODE (t);
4010
4011   switch (code)
4012     {
4013     /* Alas, constants aren't shared, so we can't rely on pointer
4014        identity.  */
4015     case INTEGER_CST:
4016       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4017       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4018     case REAL_CST:
4019       {
4020         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4021
4022         return iterative_hash_hashval_t (val2, val);
4023       }
4024     case STRING_CST:
4025       return iterative_hash (TREE_STRING_POINTER (t),
4026                              TREE_STRING_LENGTH (t), val);
4027     case COMPLEX_CST:
4028       val = iterative_hash_expr (TREE_REALPART (t), val);
4029       return iterative_hash_expr (TREE_IMAGPART (t), val);
4030     case VECTOR_CST:
4031       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4032
4033     case SSA_NAME:
4034     case VALUE_HANDLE:
4035       /* we can just compare by pointer.  */
4036       return iterative_hash_pointer (t, val);
4037
4038     case TREE_LIST:
4039       /* A list of expressions, for a CALL_EXPR or as the elements of a
4040          VECTOR_CST.  */
4041       for (; t; t = TREE_CHAIN (t))
4042         val = iterative_hash_expr (TREE_VALUE (t), val);
4043       return val;
4044     default:
4045       class = TREE_CODE_CLASS (code);
4046
4047       if (class == tcc_declaration)
4048         {
4049           /* Decls we can just compare by pointer.  */
4050           val = iterative_hash_pointer (t, val);
4051         }
4052       else
4053         {
4054           gcc_assert (IS_EXPR_CODE_CLASS (class));
4055
4056           val = iterative_hash_object (code, val);
4057
4058           /* Don't hash the type, that can lead to having nodes which
4059              compare equal according to operand_equal_p, but which
4060              have different hash codes.  */
4061           if (code == NOP_EXPR
4062               || code == CONVERT_EXPR
4063               || code == NON_LVALUE_EXPR)
4064             {
4065               /* Make sure to include signness in the hash computation.  */
4066               val += TYPE_UNSIGNED (TREE_TYPE (t));
4067               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4068             }
4069
4070           else if (commutative_tree_code (code))
4071             {
4072               /* It's a commutative expression.  We want to hash it the same
4073                  however it appears.  We do this by first hashing both operands
4074                  and then rehashing based on the order of their independent
4075                  hashes.  */
4076               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4077               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4078               hashval_t t;
4079
4080               if (one > two)
4081                 t = one, one = two, two = t;
4082
4083               val = iterative_hash_hashval_t (one, val);
4084               val = iterative_hash_hashval_t (two, val);
4085             }
4086           else
4087             for (i = first_rtl_op (code) - 1; i >= 0; --i)
4088               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4089         }
4090       return val;
4091       break;
4092     }
4093 }
4094 \f
4095 /* Constructors for pointer, array and function types.
4096    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4097    constructed by language-dependent code, not here.)  */
4098
4099 /* Construct, lay out and return the type of pointers to TO_TYPE with
4100    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4101    reference all of memory. If such a type has already been
4102    constructed, reuse it.  */
4103
4104 tree
4105 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4106                              bool can_alias_all)
4107 {
4108   tree t;
4109
4110   /* In some cases, languages will have things that aren't a POINTER_TYPE
4111      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4112      In that case, return that type without regard to the rest of our
4113      operands.
4114
4115      ??? This is a kludge, but consistent with the way this function has
4116      always operated and there doesn't seem to be a good way to avoid this
4117      at the moment.  */
4118   if (TYPE_POINTER_TO (to_type) != 0
4119       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4120     return TYPE_POINTER_TO (to_type);
4121
4122   /* First, if we already have a type for pointers to TO_TYPE and it's
4123      the proper mode, use it.  */
4124   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4125     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4126       return t;
4127
4128   t = make_node (POINTER_TYPE);
4129
4130   TREE_TYPE (t) = to_type;
4131   TYPE_MODE (t) = mode;
4132   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4133   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4134   TYPE_POINTER_TO (to_type) = t;
4135
4136   /* Lay out the type.  This function has many callers that are concerned
4137      with expression-construction, and this simplifies them all.  */
4138   layout_type (t);
4139
4140   return t;
4141 }
4142
4143 /* By default build pointers in ptr_mode.  */
4144
4145 tree
4146 build_pointer_type (tree to_type)
4147 {
4148   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4149 }
4150
4151 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4152
4153 tree
4154 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4155                                bool can_alias_all)
4156 {
4157   tree t;
4158
4159   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4160      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4161      In that case, return that type without regard to the rest of our
4162      operands.
4163
4164      ??? This is a kludge, but consistent with the way this function has
4165      always operated and there doesn't seem to be a good way to avoid this
4166      at the moment.  */
4167   if (TYPE_REFERENCE_TO (to_type) != 0
4168       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4169     return TYPE_REFERENCE_TO (to_type);
4170
4171   /* First, if we already have a type for pointers to TO_TYPE and it's
4172      the proper mode, use it.  */
4173   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4174     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4175       return t;
4176
4177   t = make_node (REFERENCE_TYPE);
4178
4179   TREE_TYPE (t) = to_type;
4180   TYPE_MODE (t) = mode;
4181   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4182   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4183   TYPE_REFERENCE_TO (to_type) = t;
4184
4185   layout_type (t);
4186
4187   return t;
4188 }
4189
4190
4191 /* Build the node for the type of references-to-TO_TYPE by default
4192    in ptr_mode.  */
4193
4194 tree
4195 build_reference_type (tree to_type)
4196 {
4197   return build_reference_type_for_mode (to_type, ptr_mode, false);
4198 }
4199
4200 /* Build a type that is compatible with t but has no cv quals anywhere
4201    in its type, thus
4202
4203    const char *const *const *  ->  char ***.  */
4204
4205 tree
4206 build_type_no_quals (tree t)
4207 {
4208   switch (TREE_CODE (t))
4209     {
4210     case POINTER_TYPE:
4211       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4212                                           TYPE_MODE (t),
4213                                           TYPE_REF_CAN_ALIAS_ALL (t));
4214     case REFERENCE_TYPE:
4215       return
4216         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4217                                        TYPE_MODE (t),
4218                                        TYPE_REF_CAN_ALIAS_ALL (t));
4219     default:
4220       return TYPE_MAIN_VARIANT (t);
4221     }
4222 }
4223
4224 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4225    MAXVAL should be the maximum value in the domain
4226    (one less than the length of the array).
4227
4228    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4229    We don't enforce this limit, that is up to caller (e.g. language front end).
4230    The limit exists because the result is a signed type and we don't handle
4231    sizes that use more than one HOST_WIDE_INT.  */
4232
4233 tree
4234 build_index_type (tree maxval)
4235 {
4236   tree itype = make_node (INTEGER_TYPE);
4237
4238   TREE_TYPE (itype) = sizetype;
4239   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4240   TYPE_MIN_VALUE (itype) = size_zero_node;
4241   TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
4242   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4243   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4244   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4245   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4246   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4247
4248   if (host_integerp (maxval, 1))
4249     return type_hash_canon (tree_low_cst (maxval, 1), itype);
4250   else
4251     return itype;
4252 }
4253
4254 /* Builds a signed or unsigned integer type of precision PRECISION.
4255    Used for C bitfields whose precision does not match that of
4256    built-in target types.  */
4257 tree
4258 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
4259                                 int unsignedp)
4260 {
4261   tree itype = make_node (INTEGER_TYPE);
4262
4263   TYPE_PRECISION (itype) = precision;
4264
4265   if (unsignedp)
4266     fixup_unsigned_type (itype);
4267   else
4268     fixup_signed_type (itype);
4269
4270   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
4271     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
4272
4273   return itype;
4274 }
4275
4276 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
4277    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
4278    low bound LOWVAL and high bound HIGHVAL.
4279    if TYPE==NULL_TREE, sizetype is used.  */
4280
4281 tree
4282 build_range_type (tree type, tree lowval, tree highval)
4283 {
4284   tree itype = make_node (INTEGER_TYPE);
4285
4286   TREE_TYPE (itype) = type;
4287   if (type == NULL_TREE)
4288     type = sizetype;
4289
4290   TYPE_MIN_VALUE (itype) = convert (type, lowval);
4291   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
4292
4293   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
4294   TYPE_MODE (itype) = TYPE_MODE (type);
4295   TYPE_SIZE (itype) = TYPE_SIZE (type);
4296   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
4297   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
4298   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
4299
4300   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
4301     return type_hash_canon (tree_low_cst (highval, 0)
4302                             - tree_low_cst (lowval, 0),
4303                             itype);
4304   else
4305     return itype;
4306 }
4307
4308 /* Just like build_index_type, but takes lowval and highval instead
4309    of just highval (maxval).  */
4310
4311 tree
4312 build_index_2_type (tree lowval, tree highval)
4313 {
4314   return build_range_type (sizetype, lowval, highval);
4315 }
4316
4317 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
4318    and number of elements specified by the range of values of INDEX_TYPE.
4319    If such a type has already been constructed, reuse it.  */
4320
4321 tree
4322 build_array_type (tree elt_type, tree index_type)
4323 {
4324   tree t;
4325   hashval_t hashcode = 0;
4326
4327   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
4328     {
4329       error ("arrays of functions are not meaningful");
4330       elt_type = integer_type_node;
4331     }
4332
4333   t = make_node (ARRAY_TYPE);
4334   TREE_TYPE (t) = elt_type;
4335   TYPE_DOMAIN (t) = index_type;
4336
4337   if (index_type == 0)
4338     return t;
4339
4340   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
4341   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
4342   t = type_hash_canon (hashcode, t);
4343
4344   if (!COMPLETE_TYPE_P (t))
4345     layout_type (t);
4346   return t;
4347 }
4348
4349 /* Return the TYPE of the elements comprising
4350    the innermost dimension of ARRAY.  */
4351
4352 tree
4353 get_inner_array_type (tree array)
4354 {
4355   tree type = TREE_TYPE (array);
4356
4357   while (TREE_CODE (type) == ARRAY_TYPE)
4358     type = TREE_TYPE (type);
4359
4360   return type;
4361 }
4362
4363 /* Construct, lay out and return
4364    the type of functions returning type VALUE_TYPE
4365    given arguments of types ARG_TYPES.
4366    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
4367    are data type nodes for the arguments of the function.
4368    If such a type has already been constructed, reuse it.  */
4369
4370 tree
4371 build_function_type (tree value_type, tree arg_types)
4372 {
4373   tree t;
4374   hashval_t hashcode = 0;
4375
4376   if (TREE_CODE (value_type) == FUNCTION_TYPE)
4377     {
4378       error ("function return type cannot be function");
4379       value_type = integer_type_node;
4380     }
4381
4382   /* Make a node of the sort we want.  */
4383   t = make_node (FUNCTION_TYPE);
4384   TREE_TYPE (t) = value_type;
4385   TYPE_ARG_TYPES (t) = arg_types;
4386
4387   /* If we already have such a type, use the old one.  */
4388   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
4389   hashcode = type_hash_list (arg_types, hashcode);
4390   t = type_hash_canon (hashcode, t);
4391
4392   if (!COMPLETE_TYPE_P (t))
4393     layout_type (t);
4394   return t;
4395 }
4396
4397 /* Build a function type.  The RETURN_TYPE is the type returned by the
4398    function.  If additional arguments are provided, they are
4399    additional argument types.  The list of argument types must always
4400    be terminated by NULL_TREE.  */
4401
4402 tree
4403 build_function_type_list (tree return_type, ...)
4404 {
4405   tree t, args, last;
4406   va_list p;
4407
4408   va_start (p, return_type);
4409
4410   t = va_arg (p, tree);
4411   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
4412     args = tree_cons (NULL_TREE, t, args);
4413
4414   last = args;
4415   args = nreverse (args);
4416   TREE_CHAIN (last) = void_list_node;
4417   args = build_function_type (return_type, args);
4418
4419   va_end (p);
4420   return args;
4421 }
4422
4423 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
4424    and ARGTYPES (a TREE_LIST) are the return type and arguments types
4425    for the method.  An implicit additional parameter (of type
4426    pointer-to-BASETYPE) is added to the ARGTYPES.  */
4427
4428 tree
4429 build_method_type_directly (tree basetype,
4430                             tree rettype,
4431                             tree argtypes)
4432 {
4433   tree t;
4434   tree ptype;
4435   int hashcode = 0;
4436
4437   /* Make a node of the sort we want.  */
4438   t = make_node (METHOD_TYPE);
4439
4440   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4441   TREE_TYPE (t) = rettype;
4442   ptype = build_pointer_type (basetype);
4443
4444   /* The actual arglist for this function includes a "hidden" argument
4445      which is "this".  Put it into the list of argument types.  */
4446   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
4447   TYPE_ARG_TYPES (t) = argtypes;
4448
4449   /* If we already have such a type, use the old one.  */
4450   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4451   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
4452   hashcode = type_hash_list (argtypes, hashcode);
4453   t = type_hash_canon (hashcode, t);
4454
4455   if (!COMPLETE_TYPE_P (t))
4456     layout_type (t);
4457
4458   return t;
4459 }
4460
4461 /* Construct, lay out and return the type of methods belonging to class
4462    BASETYPE and whose arguments and values are described by TYPE.
4463    If that type exists already, reuse it.
4464    TYPE must be a FUNCTION_TYPE node.  */
4465
4466 tree
4467 build_method_type (tree basetype, tree type)
4468 {
4469   gcc_assert (TREE_CODE (type) == FUNCTION_TYPE);
4470
4471   return build_method_type_directly (basetype,
4472                                      TREE_TYPE (type),
4473                                      TYPE_ARG_TYPES (type));
4474 }
4475
4476 /* Construct, lay out and return the type of offsets to a value
4477    of type TYPE, within an object of type BASETYPE.
4478    If a suitable offset type exists already, reuse it.  */
4479
4480 tree
4481 build_offset_type (tree basetype, tree type)
4482 {
4483   tree t;
4484   hashval_t hashcode = 0;
4485
4486   /* Make a node of the sort we want.  */
4487   t = make_node (OFFSET_TYPE);
4488
4489   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
4490   TREE_TYPE (t) = type;
4491
4492   /* If we already have such a type, use the old one.  */
4493   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
4494   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
4495   t = type_hash_canon (hashcode, t);
4496
4497   if (!COMPLETE_TYPE_P (t))
4498     layout_type (t);
4499
4500   return t;
4501 }
4502
4503 /* Create a complex type whose components are COMPONENT_TYPE.  */
4504
4505 tree
4506 build_complex_type (tree component_type)
4507 {
4508   tree t;
4509   hashval_t hashcode;
4510
4511   /* Make a node of the sort we want.  */
4512   t = make_node (COMPLEX_TYPE);
4513
4514   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
4515
4516   /* If we already have such a type, use the old one.  */
4517   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
4518   t = type_hash_canon (hashcode, t);
4519
4520   if (!COMPLETE_TYPE_P (t))
4521     layout_type (t);
4522
4523   /* If we are writing Dwarf2 output we need to create a name,
4524      since complex is a fundamental type.  */
4525   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
4526       && ! TYPE_NAME (t))
4527     {
4528       const char *name;
4529       if (component_type == char_type_node)
4530         name = "complex char";
4531       else if (component_type == signed_char_type_node)
4532         name = "complex signed char";
4533       else if (component_type == unsigned_char_type_node)
4534         name = "complex unsigned char";
4535       else if (component_type == short_integer_type_node)
4536         name = "complex short int";
4537       else if (component_type == short_unsigned_type_node)
4538         name = "complex short unsigned int";
4539       else if (component_type == integer_type_node)
4540         name = "complex int";
4541       else if (component_type == unsigned_type_node)
4542         name = "complex unsigned int";
4543       else if (component_type == long_integer_type_node)
4544         name = "complex long int";
4545       else if (component_type == long_unsigned_type_node)
4546         name = "complex long unsigned int";
4547       else if (component_type == long_long_integer_type_node)
4548         name = "complex long long int";
4549       else if (component_type == long_long_unsigned_type_node)
4550         name = "complex long long unsigned int";
4551       else
4552         name = 0;
4553
4554       if (name != 0)
4555         TYPE_NAME (t) = get_identifier (name);
4556     }
4557
4558   return build_qualified_type (t, TYPE_QUALS (component_type));
4559 }
4560 \f
4561 /* Return OP, stripped of any conversions to wider types as much as is safe.
4562    Converting the value back to OP's type makes a value equivalent to OP.
4563
4564    If FOR_TYPE is nonzero, we return a value which, if converted to
4565    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
4566
4567    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
4568    narrowest type that can hold the value, even if they don't exactly fit.
4569    Otherwise, bit-field references are changed to a narrower type
4570    only if they can be fetched directly from memory in that type.
4571
4572    OP must have integer, real or enumeral type.  Pointers are not allowed!
4573
4574    There are some cases where the obvious value we could return
4575    would regenerate to OP if converted to OP's type,
4576    but would not extend like OP to wider types.
4577    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
4578    For example, if OP is (unsigned short)(signed char)-1,
4579    we avoid returning (signed char)-1 if FOR_TYPE is int,
4580    even though extending that to an unsigned short would regenerate OP,
4581    since the result of extending (signed char)-1 to (int)
4582    is different from (int) OP.  */
4583
4584 tree
4585 get_unwidened (tree op, tree for_type)
4586 {
4587   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
4588   tree type = TREE_TYPE (op);
4589   unsigned final_prec
4590     = TYPE_PRECISION (for_type != 0 ? for_type : type);
4591   int uns
4592     = (for_type != 0 && for_type != type
4593        && final_prec > TYPE_PRECISION (type)
4594        && TYPE_UNSIGNED (type));
4595   tree win = op;
4596
4597   while (TREE_CODE (op) == NOP_EXPR)
4598     {
4599       int bitschange
4600         = TYPE_PRECISION (TREE_TYPE (op))
4601           - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
4602
4603       /* Truncations are many-one so cannot be removed.
4604          Unless we are later going to truncate down even farther.  */
4605       if (bitschange < 0
4606           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
4607         break;
4608
4609       /* See what's inside this conversion.  If we decide to strip it,
4610          we will set WIN.  */
4611       op = TREE_OPERAND (op, 0);
4612
4613       /* If we have not stripped any zero-extensions (uns is 0),
4614          we can strip any kind of extension.
4615          If we have previously stripped a zero-extension,
4616          only zero-extensions can safely be stripped.
4617          Any extension can be stripped if the bits it would produce
4618          are all going to be discarded later by truncating to FOR_TYPE.  */
4619
4620       if (bitschange > 0)
4621         {
4622           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
4623             win = op;
4624           /* TYPE_UNSIGNED says whether this is a zero-extension.
4625              Let's avoid computing it if it does not affect WIN
4626              and if UNS will not be needed again.  */
4627           if ((uns || TREE_CODE (op) == NOP_EXPR)
4628               && TYPE_UNSIGNED (TREE_TYPE (op)))
4629             {
4630               uns = 1;
4631               win = op;
4632             }
4633         }
4634     }
4635
4636   if (TREE_CODE (op) == COMPONENT_REF
4637       /* Since type_for_size always gives an integer type.  */
4638       && TREE_CODE (type) != REAL_TYPE
4639       /* Don't crash if field not laid out yet.  */
4640       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4641       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4642     {
4643       unsigned int innerprec
4644         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4645       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
4646                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4647       type = lang_hooks.types.type_for_size (innerprec, unsignedp);
4648
4649       /* We can get this structure field in the narrowest type it fits in.
4650          If FOR_TYPE is 0, do this only for a field that matches the
4651          narrower type exactly and is aligned for it
4652          The resulting extension to its nominal type (a fullword type)
4653          must fit the same conditions as for other extensions.  */
4654
4655       if (type != 0
4656           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
4657           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
4658           && (! uns || final_prec <= innerprec || unsignedp))
4659         {
4660           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4661                         TREE_OPERAND (op, 1), NULL_TREE);
4662           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4663           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4664         }
4665     }
4666
4667   return win;
4668 }
4669 \f
4670 /* Return OP or a simpler expression for a narrower value
4671    which can be sign-extended or zero-extended to give back OP.
4672    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
4673    or 0 if the value should be sign-extended.  */
4674
4675 tree
4676 get_narrower (tree op, int *unsignedp_ptr)
4677 {
4678   int uns = 0;
4679   int first = 1;
4680   tree win = op;
4681   bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op));
4682
4683   while (TREE_CODE (op) == NOP_EXPR)
4684     {
4685       int bitschange
4686         = (TYPE_PRECISION (TREE_TYPE (op))
4687            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
4688
4689       /* Truncations are many-one so cannot be removed.  */
4690       if (bitschange < 0)
4691         break;
4692
4693       /* See what's inside this conversion.  If we decide to strip it,
4694          we will set WIN.  */
4695
4696       if (bitschange > 0)
4697         {
4698           op = TREE_OPERAND (op, 0);
4699           /* An extension: the outermost one can be stripped,
4700              but remember whether it is zero or sign extension.  */
4701           if (first)
4702             uns = TYPE_UNSIGNED (TREE_TYPE (op));
4703           /* Otherwise, if a sign extension has been stripped,
4704              only sign extensions can now be stripped;
4705              if a zero extension has been stripped, only zero-extensions.  */
4706           else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
4707             break;
4708           first = 0;
4709         }
4710       else /* bitschange == 0 */
4711         {
4712           /* A change in nominal type can always be stripped, but we must
4713              preserve the unsignedness.  */
4714           if (first)
4715             uns = TYPE_UNSIGNED (TREE_TYPE (op));
4716           first = 0;
4717           op = TREE_OPERAND (op, 0);
4718           /* Keep trying to narrow, but don't assign op to win if it
4719              would turn an integral type into something else.  */
4720           if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p)
4721             continue;
4722         }
4723
4724       win = op;
4725     }
4726
4727   if (TREE_CODE (op) == COMPONENT_REF
4728       /* Since type_for_size always gives an integer type.  */
4729       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
4730       /* Ensure field is laid out already.  */
4731       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
4732       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
4733     {
4734       unsigned HOST_WIDE_INT innerprec
4735         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
4736       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
4737                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
4738       tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
4739
4740       /* We can get this structure field in a narrower type that fits it,
4741          but the resulting extension to its nominal type (a fullword type)
4742          must satisfy the same conditions as for other extensions.
4743
4744          Do this only for fields that are aligned (not bit-fields),
4745          because when bit-field insns will be used there is no
4746          advantage in doing this.  */
4747
4748       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
4749           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
4750           && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
4751           && type != 0)
4752         {
4753           if (first)
4754             uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
4755           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
4756                         TREE_OPERAND (op, 1), NULL_TREE);
4757           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
4758           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
4759         }
4760     }
4761   *unsignedp_ptr = uns;
4762   return win;
4763 }
4764 \f
4765 /* Nonzero if integer constant C has a value that is permissible
4766    for type TYPE (an INTEGER_TYPE).  */
4767
4768 int
4769 int_fits_type_p (tree c, tree type)
4770 {
4771   tree type_low_bound = TYPE_MIN_VALUE (type);
4772   tree type_high_bound = TYPE_MAX_VALUE (type);
4773   int ok_for_low_bound, ok_for_high_bound;
4774
4775   /* Perform some generic filtering first, which may allow making a decision
4776      even if the bounds are not constant.  First, negative integers never fit
4777      in unsigned types, */
4778   if ((TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
4779       /* Also, unsigned integers with top bit set never fit signed types.  */
4780       || (! TYPE_UNSIGNED (type)
4781           && TYPE_UNSIGNED (TREE_TYPE (c)) && tree_int_cst_msb (c)))
4782     return 0;
4783
4784   /* If at least one bound of the type is a constant integer, we can check
4785      ourselves and maybe make a decision. If no such decision is possible, but
4786      this type is a subtype, try checking against that.  Otherwise, use
4787      force_fit_type, which checks against the precision.
4788
4789      Compute the status for each possibly constant bound, and return if we see
4790      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
4791      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
4792      for "constant known to fit".  */
4793
4794   ok_for_low_bound = -1;
4795   ok_for_high_bound = -1;
4796
4797   /* Check if C >= type_low_bound.  */
4798   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
4799     {
4800       ok_for_low_bound = ! tree_int_cst_lt (c, type_low_bound);
4801       if (! ok_for_low_bound)
4802         return 0;
4803     }
4804
4805   /* Check if c <= type_high_bound.  */
4806   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
4807     {
4808       ok_for_high_bound = ! tree_int_cst_lt (type_high_bound, c);
4809       if (! ok_for_high_bound)
4810         return 0;
4811     }
4812
4813   /* If the constant fits both bounds, the result is known.  */
4814   if (ok_for_low_bound == 1 && ok_for_high_bound == 1)
4815     return 1;
4816
4817   /* If we haven't been able to decide at this point, there nothing more we
4818      can check ourselves here. Look at the base type if we have one.  */
4819   else if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != 0)
4820     return int_fits_type_p (c, TREE_TYPE (type));
4821
4822   /* Or to force_fit_type, if nothing else.  */
4823   else
4824     {
4825       c = copy_node (c);
4826       TREE_TYPE (c) = type;
4827       c = force_fit_type (c, -1, false, false);
4828       return !TREE_OVERFLOW (c);
4829     }
4830 }
4831
4832 /* Subprogram of following function.  Called by walk_tree.
4833
4834    Return *TP if it is an automatic variable or parameter of the
4835    function passed in as DATA.  */
4836
4837 static tree
4838 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
4839 {
4840   tree fn = (tree) data;
4841
4842   if (TYPE_P (*tp))
4843     *walk_subtrees = 0;
4844
4845   else if (DECL_P (*tp)
4846            && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
4847     return *tp;
4848
4849   return NULL_TREE;
4850 }
4851
4852 /* Returns true if T is, contains, or refers to a type with variable
4853    size.  If FN is nonzero, only return true if a modifier of the type
4854    or position of FN is a variable or parameter inside FN.
4855
4856    This concept is more general than that of C99 'variably modified types':
4857    in C99, a struct type is never variably modified because a VLA may not
4858    appear as a structure member.  However, in GNU C code like:
4859
4860      struct S { int i[f()]; };
4861
4862    is valid, and other languages may define similar constructs.  */
4863
4864 bool
4865 variably_modified_type_p (tree type, tree fn)
4866 {
4867   tree t;
4868
4869 /* Test if T is either variable (if FN is zero) or an expression containing
4870    a variable in FN.  */
4871 #define RETURN_TRUE_IF_VAR(T)                                           \
4872   do { tree _t = (T);                                                   \
4873     if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST    \
4874         && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL)))        \
4875       return true;  } while (0)
4876
4877   if (type == error_mark_node)
4878     return false;
4879
4880   /* If TYPE itself has variable size, it is variably modified.
4881
4882      We do not yet have a representation of the C99 '[*]' syntax.
4883      When a representation is chosen, this function should be modified
4884      to test for that case as well.  */
4885   RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
4886   RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT(type));
4887
4888   switch (TREE_CODE (type))
4889     {
4890     case POINTER_TYPE:
4891     case REFERENCE_TYPE:
4892     case ARRAY_TYPE:
4893     case SET_TYPE:
4894     case VECTOR_TYPE:
4895       if (variably_modified_type_p (TREE_TYPE (type), fn))
4896         return true;
4897       break;
4898
4899     case FUNCTION_TYPE:
4900     case METHOD_TYPE:
4901       /* If TYPE is a function type, it is variably modified if any of the
4902          parameters or the return type are variably modified.  */
4903       if (variably_modified_type_p (TREE_TYPE (type), fn))
4904           return true;
4905
4906       for (t = TYPE_ARG_TYPES (type);
4907            t && t != void_list_node;
4908            t = TREE_CHAIN (t))
4909         if (variably_modified_type_p (TREE_VALUE (t), fn))
4910           return true;
4911       break;
4912
4913     case INTEGER_TYPE:
4914     case REAL_TYPE:
4915     case ENUMERAL_TYPE:
4916     case BOOLEAN_TYPE:
4917     case CHAR_TYPE:
4918       /* Scalar types are variably modified if their end points
4919          aren't constant.  */
4920       RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
4921       RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
4922       break;
4923
4924     case RECORD_TYPE:
4925     case UNION_TYPE:
4926     case QUAL_UNION_TYPE:
4927       /* We can't see if any of the field are variably-modified by the
4928          definition we normally use, since that would produce infinite
4929          recursion via pointers.  */
4930       /* This is variably modified if some field's type is.  */
4931       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
4932         if (TREE_CODE (t) == FIELD_DECL)
4933           {
4934             RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
4935             RETURN_TRUE_IF_VAR (DECL_SIZE (t));
4936             RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
4937
4938             if (TREE_CODE (type) == QUAL_UNION_TYPE)
4939               RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
4940           }
4941         break;
4942
4943     default:
4944       break;
4945     }
4946
4947   /* The current language may have other cases to check, but in general,
4948      all other types are not variably modified.  */
4949   return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
4950
4951 #undef RETURN_TRUE_IF_VAR
4952 }
4953
4954 /* Given a DECL or TYPE, return the scope in which it was declared, or
4955    NULL_TREE if there is no containing scope.  */
4956
4957 tree
4958 get_containing_scope (tree t)
4959 {
4960   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
4961 }
4962
4963 /* Return the innermost context enclosing DECL that is
4964    a FUNCTION_DECL, or zero if none.  */
4965
4966 tree
4967 decl_function_context (tree decl)
4968 {
4969   tree context;
4970
4971   if (TREE_CODE (decl) == ERROR_MARK)
4972     return 0;
4973
4974   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
4975      where we look up the function at runtime.  Such functions always take
4976      a first argument of type 'pointer to real context'.
4977
4978      C++ should really be fixed to use DECL_CONTEXT for the real context,
4979      and use something else for the "virtual context".  */
4980   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
4981     context
4982       = TYPE_MAIN_VARIANT
4983         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
4984   else
4985     context = DECL_CONTEXT (decl);
4986
4987   while (context && TREE_CODE (context) != FUNCTION_DECL)
4988     {
4989       if (TREE_CODE (context) == BLOCK)
4990         context = BLOCK_SUPERCONTEXT (context);
4991       else
4992         context = get_containing_scope (context);
4993     }
4994
4995   return context;
4996 }
4997
4998 /* Return the innermost context enclosing DECL that is
4999    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5000    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
5001
5002 tree
5003 decl_type_context (tree decl)
5004 {
5005   tree context = DECL_CONTEXT (decl);
5006
5007   while (context)
5008     switch (TREE_CODE (context))
5009       {
5010       case NAMESPACE_DECL:
5011       case TRANSLATION_UNIT_DECL:
5012         return NULL_TREE;
5013
5014       case RECORD_TYPE:
5015       case UNION_TYPE:
5016       case QUAL_UNION_TYPE:
5017         return context;
5018
5019       case TYPE_DECL:
5020       case FUNCTION_DECL:
5021         context = DECL_CONTEXT (context);
5022         break;
5023
5024       case BLOCK:
5025         context = BLOCK_SUPERCONTEXT (context);
5026         break;
5027
5028       default:
5029         gcc_unreachable ();
5030       }
5031
5032   return NULL_TREE;
5033 }
5034
5035 /* CALL is a CALL_EXPR.  Return the declaration for the function
5036    called, or NULL_TREE if the called function cannot be
5037    determined.  */
5038
5039 tree
5040 get_callee_fndecl (tree call)
5041 {
5042   tree addr;
5043
5044   /* It's invalid to call this function with anything but a
5045      CALL_EXPR.  */
5046   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5047
5048   /* The first operand to the CALL is the address of the function
5049      called.  */
5050   addr = TREE_OPERAND (call, 0);
5051
5052   STRIP_NOPS (addr);
5053
5054   /* If this is a readonly function pointer, extract its initial value.  */
5055   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5056       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5057       && DECL_INITIAL (addr))
5058     addr = DECL_INITIAL (addr);
5059
5060   /* If the address is just `&f' for some function `f', then we know
5061      that `f' is being called.  */
5062   if (TREE_CODE (addr) == ADDR_EXPR
5063       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5064     return TREE_OPERAND (addr, 0);
5065
5066   /* We couldn't figure out what was being called.  Maybe the front
5067      end has some idea.  */
5068   return lang_hooks.lang_get_callee_fndecl (call);
5069 }
5070
5071 /* Print debugging information about tree nodes generated during the compile,
5072    and any language-specific information.  */
5073
5074 void
5075 dump_tree_statistics (void)
5076 {
5077 #ifdef GATHER_STATISTICS
5078   int i;
5079   int total_nodes, total_bytes;
5080 #endif
5081
5082   fprintf (stderr, "\n??? tree nodes created\n\n");
5083 #ifdef GATHER_STATISTICS
5084   fprintf (stderr, "Kind                   Nodes      Bytes\n");
5085   fprintf (stderr, "---------------------------------------\n");
5086   total_nodes = total_bytes = 0;
5087   for (i = 0; i < (int) all_kinds; i++)
5088     {
5089       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5090                tree_node_counts[i], tree_node_sizes[i]);
5091       total_nodes += tree_node_counts[i];
5092       total_bytes += tree_node_sizes[i];
5093     }
5094   fprintf (stderr, "---------------------------------------\n");
5095   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5096   fprintf (stderr, "---------------------------------------\n");
5097   ssanames_print_statistics ();
5098   phinodes_print_statistics ();
5099 #else
5100   fprintf (stderr, "(No per-node statistics)\n");
5101 #endif
5102   print_type_hash_statistics ();
5103   lang_hooks.print_statistics ();
5104 }
5105 \f
5106 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
5107
5108 /* Generate a crc32 of a string.  */
5109
5110 unsigned
5111 crc32_string (unsigned chksum, const char *string)
5112 {
5113   do
5114     {
5115       unsigned value = *string << 24;
5116       unsigned ix;
5117
5118       for (ix = 8; ix--; value <<= 1)
5119         {
5120           unsigned feedback;
5121
5122           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
5123           chksum <<= 1;
5124           chksum ^= feedback;
5125         }
5126     }
5127   while (*string++);
5128   return chksum;
5129 }
5130
5131 /* P is a string that will be used in a symbol.  Mask out any characters
5132    that are not valid in that context.  */
5133
5134 void
5135 clean_symbol_name (char *p)
5136 {
5137   for (; *p; p++)
5138     if (! (ISALNUM (*p)
5139 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
5140             || *p == '$'
5141 #endif
5142 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
5143             || *p == '.'
5144 #endif
5145            ))
5146       *p = '_';
5147 }
5148
5149 /* Generate a name for a function unique to this translation unit.
5150    TYPE is some string to identify the purpose of this function to the
5151    linker or collect2.  */
5152
5153 tree
5154 get_file_function_name_long (const char *type)
5155 {
5156   char *buf;
5157   const char *p;
5158   char *q;
5159
5160   if (first_global_object_name)
5161     p = first_global_object_name;
5162   else
5163     {
5164       /* We don't have anything that we know to be unique to this translation
5165          unit, so use what we do have and throw in some randomness.  */
5166       unsigned len;
5167       const char *name = weak_global_object_name;
5168       const char *file = main_input_filename;
5169
5170       if (! name)
5171         name = "";
5172       if (! file)
5173         file = input_filename;
5174
5175       len = strlen (file);
5176       q = alloca (9 * 2 + len + 1);
5177       memcpy (q, file, len + 1);
5178       clean_symbol_name (q);
5179
5180       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
5181                crc32_string (0, flag_random_seed));
5182
5183       p = q;
5184     }
5185
5186   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
5187
5188   /* Set up the name of the file-level functions we may need.
5189      Use a global object (which is already required to be unique over
5190      the program) rather than the file name (which imposes extra
5191      constraints).  */
5192   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
5193
5194   return get_identifier (buf);
5195 }
5196
5197 /* If KIND=='I', return a suitable global initializer (constructor) name.
5198    If KIND=='D', return a suitable global clean-up (destructor) name.  */
5199
5200 tree
5201 get_file_function_name (int kind)
5202 {
5203   char p[2];
5204
5205   p[0] = kind;
5206   p[1] = 0;
5207
5208   return get_file_function_name_long (p);
5209 }
5210 \f
5211 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
5212    The result is placed in BUFFER (which has length BIT_SIZE),
5213    with one bit in each char ('\000' or '\001').
5214
5215    If the constructor is constant, NULL_TREE is returned.
5216    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
5217
5218 tree
5219 get_set_constructor_bits (tree init, char *buffer, int bit_size)
5220 {
5221   int i;
5222   tree vals;
5223   HOST_WIDE_INT domain_min
5224     = tree_low_cst (TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (init))), 0);
5225   tree non_const_bits = NULL_TREE;
5226
5227   for (i = 0; i < bit_size; i++)
5228     buffer[i] = 0;
5229
5230   for (vals = TREE_OPERAND (init, 1);
5231        vals != NULL_TREE; vals = TREE_CHAIN (vals))
5232     {
5233       if (!host_integerp (TREE_VALUE (vals), 0)
5234           || (TREE_PURPOSE (vals) != NULL_TREE
5235               && !host_integerp (TREE_PURPOSE (vals), 0)))
5236         non_const_bits
5237           = tree_cons (TREE_PURPOSE (vals), TREE_VALUE (vals), non_const_bits);
5238       else if (TREE_PURPOSE (vals) != NULL_TREE)
5239         {
5240           /* Set a range of bits to ones.  */
5241           HOST_WIDE_INT lo_index
5242             = tree_low_cst (TREE_PURPOSE (vals), 0) - domain_min;
5243           HOST_WIDE_INT hi_index
5244             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
5245
5246           gcc_assert (lo_index >= 0);
5247           gcc_assert (lo_index < bit_size);
5248           gcc_assert (hi_index >= 0);
5249           gcc_assert (hi_index < bit_size);
5250           for (; lo_index <= hi_index; lo_index++)
5251             buffer[lo_index] = 1;
5252         }
5253       else
5254         {
5255           /* Set a single bit to one.  */
5256           HOST_WIDE_INT index
5257             = tree_low_cst (TREE_VALUE (vals), 0) - domain_min;
5258           if (index < 0 || index >= bit_size)
5259             {
5260               error ("invalid initializer for bit string");
5261               return NULL_TREE;
5262             }
5263           buffer[index] = 1;
5264         }
5265     }
5266   return non_const_bits;
5267 }
5268
5269 /* Expand (the constant part of) a SET_TYPE CONSTRUCTOR node.
5270    The result is placed in BUFFER (which is an array of bytes).
5271    If the constructor is constant, NULL_TREE is returned.
5272    Otherwise, a TREE_LIST of the non-constant elements is emitted.  */
5273
5274 tree
5275 get_set_constructor_bytes (tree init, unsigned char *buffer, int wd_size)
5276 {
5277   int i;
5278   int set_word_size = BITS_PER_UNIT;
5279   int bit_size = wd_size * set_word_size;
5280   int bit_pos = 0;
5281   unsigned char *bytep = buffer;
5282   char *bit_buffer = alloca (bit_size);
5283   tree non_const_bits = get_set_constructor_bits (init, bit_buffer, bit_size);
5284
5285   for (i = 0; i < wd_size; i++)
5286     buffer[i] = 0;
5287
5288   for (i = 0; i < bit_size; i++)
5289     {
5290       if (bit_buffer[i])
5291         {
5292           if (BYTES_BIG_ENDIAN)
5293             *bytep |= (1 << (set_word_size - 1 - bit_pos));
5294           else
5295             *bytep |= 1 << bit_pos;
5296         }
5297       bit_pos++;
5298       if (bit_pos >= set_word_size)
5299         bit_pos = 0, bytep++;
5300     }
5301   return non_const_bits;
5302 }
5303 \f
5304 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
5305
5306 /* Complain that the tree code of NODE does not match the expected 0
5307    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
5308    the caller.  */
5309
5310 void
5311 tree_check_failed (const tree node, const char *file,
5312                    int line, const char *function, ...)
5313 {
5314   va_list args;
5315   char *buffer;
5316   unsigned length = 0;
5317   int code;
5318
5319   va_start (args, function);
5320   while ((code = va_arg (args, int)))
5321     length += 4 + strlen (tree_code_name[code]);
5322   va_end (args);
5323   va_start (args, function);
5324   buffer = alloca (length);
5325   length = 0;
5326   while ((code = va_arg (args, int)))
5327     {
5328       if (length)
5329         {
5330           strcpy (buffer + length, " or ");
5331           length += 4;
5332         }
5333       strcpy (buffer + length, tree_code_name[code]);
5334       length += strlen (tree_code_name[code]);
5335     }
5336   va_end (args);
5337
5338   internal_error ("tree check: expected %s, have %s in %s, at %s:%d",
5339                   buffer, tree_code_name[TREE_CODE (node)],
5340                   function, trim_filename (file), line);
5341 }
5342
5343 /* Complain that the tree code of NODE does match the expected 0
5344    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
5345    the caller.  */
5346
5347 void
5348 tree_not_check_failed (const tree node, const char *file,
5349                        int line, const char *function, ...)
5350 {
5351   va_list args;
5352   char *buffer;
5353   unsigned length = 0;
5354   int code;
5355
5356   va_start (args, function);
5357   while ((code = va_arg (args, int)))
5358     length += 4 + strlen (tree_code_name[code]);
5359   va_end (args);
5360   va_start (args, function);
5361   buffer = alloca (length);
5362   length = 0;
5363   while ((code = va_arg (args, int)))
5364     {
5365       if (length)
5366         {
5367           strcpy (buffer + length, " or ");
5368           length += 4;
5369         }
5370       strcpy (buffer + length, tree_code_name[code]);
5371       length += strlen (tree_code_name[code]);
5372     }
5373   va_end (args);
5374
5375   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
5376                   buffer, tree_code_name[TREE_CODE (node)],
5377                   function, trim_filename (file), line);
5378 }
5379
5380 /* Similar to tree_check_failed, except that we check for a class of tree
5381    code, given in CL.  */
5382
5383 void
5384 tree_class_check_failed (const tree node, const enum tree_code_class cl,
5385                          const char *file, int line, const char *function)
5386 {
5387   internal_error
5388     ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
5389      TREE_CODE_CLASS_STRING (cl),
5390      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
5391      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
5392 }
5393
5394 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
5395    (dynamically sized) vector.  */
5396
5397 void
5398 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
5399                            const char *function)
5400 {
5401   internal_error
5402     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
5403      idx + 1, len, function, trim_filename (file), line);
5404 }
5405
5406 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
5407    (dynamically sized) vector.  */
5408
5409 void
5410 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
5411                             const char *function)
5412 {
5413   internal_error
5414     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
5415      idx + 1, len, function, trim_filename (file), line);
5416 }
5417
5418 /* Similar to above, except that the check is for the bounds of the operand
5419    vector of an expression node.  */
5420
5421 void
5422 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
5423                            int line, const char *function)
5424 {
5425   internal_error
5426     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
5427      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
5428      function, trim_filename (file), line);
5429 }
5430 #endif /* ENABLE_TREE_CHECKING */
5431 \f
5432 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
5433    and mapped to the machine mode MODE.  Initialize its fields and build
5434    the information necessary for debugging output.  */
5435
5436 static tree
5437 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
5438 {
5439   tree t = make_node (VECTOR_TYPE);
5440
5441   TREE_TYPE (t) = innertype;
5442   TYPE_VECTOR_SUBPARTS (t) = nunits;
5443   TYPE_MODE (t) = mode;
5444   layout_type (t);
5445
5446   {
5447     tree index = build_int_cst (NULL_TREE, nunits - 1);
5448     tree array = build_array_type (innertype, build_index_type (index));
5449     tree rt = make_node (RECORD_TYPE);
5450
5451     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
5452     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
5453     layout_type (rt);
5454     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
5455     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
5456        the representation type, and we want to find that die when looking up
5457        the vector type.  This is most easily achieved by making the TYPE_UID
5458        numbers equal.  */
5459     TYPE_UID (rt) = TYPE_UID (t);
5460   }
5461
5462   return t;
5463 }
5464
5465 static tree
5466 make_or_reuse_type (unsigned size, int unsignedp)
5467 {
5468   if (size == INT_TYPE_SIZE)
5469     return unsignedp ? unsigned_type_node : integer_type_node;
5470   if (size == CHAR_TYPE_SIZE)
5471     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
5472   if (size == SHORT_TYPE_SIZE)
5473     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
5474   if (size == LONG_TYPE_SIZE)
5475     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
5476   if (size == LONG_LONG_TYPE_SIZE)
5477     return (unsignedp ? long_long_unsigned_type_node
5478             : long_long_integer_type_node);
5479
5480   if (unsignedp)
5481     return make_unsigned_type (size);
5482   else
5483     return make_signed_type (size);
5484 }
5485
5486 /* Create nodes for all integer types (and error_mark_node) using the sizes
5487    of C datatypes.  The caller should call set_sizetype soon after calling
5488    this function to select one of the types as sizetype.  */
5489
5490 void
5491 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
5492 {
5493   error_mark_node = make_node (ERROR_MARK);
5494   TREE_TYPE (error_mark_node) = error_mark_node;
5495
5496   initialize_sizetypes (signed_sizetype);
5497
5498   /* Define both `signed char' and `unsigned char'.  */
5499   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
5500   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
5501
5502   /* Define `char', which is like either `signed char' or `unsigned char'
5503      but not the same as either.  */
5504   char_type_node
5505     = (signed_char
5506        ? make_signed_type (CHAR_TYPE_SIZE)
5507        : make_unsigned_type (CHAR_TYPE_SIZE));
5508
5509   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
5510   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
5511   integer_type_node = make_signed_type (INT_TYPE_SIZE);
5512   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
5513   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
5514   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
5515   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
5516   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
5517
5518   /* Define a boolean type.  This type only represents boolean values but
5519      may be larger than char depending on the value of BOOL_TYPE_SIZE.
5520      Front ends which want to override this size (i.e. Java) can redefine
5521      boolean_type_node before calling build_common_tree_nodes_2.  */
5522   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
5523   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
5524   TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
5525   TYPE_PRECISION (boolean_type_node) = 1;
5526
5527   /* Fill in the rest of the sized types.  Reuse existing type nodes
5528      when possible.  */
5529   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
5530   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
5531   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
5532   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
5533   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
5534
5535   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
5536   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
5537   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
5538   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
5539   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
5540
5541   access_public_node = get_identifier ("public");
5542   access_protected_node = get_identifier ("protected");
5543   access_private_node = get_identifier ("private");
5544 }
5545
5546 /* Call this function after calling build_common_tree_nodes and set_sizetype.
5547    It will create several other common tree nodes.  */
5548
5549 void
5550 build_common_tree_nodes_2 (int short_double)
5551 {
5552   /* Define these next since types below may used them.  */
5553   integer_zero_node = build_int_cst (NULL_TREE, 0);
5554   integer_one_node = build_int_cst (NULL_TREE, 1);
5555   integer_minus_one_node = build_int_cst (NULL_TREE, -1);
5556
5557   size_zero_node = size_int (0);
5558   size_one_node = size_int (1);
5559   bitsize_zero_node = bitsize_int (0);
5560   bitsize_one_node = bitsize_int (1);
5561   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
5562
5563   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
5564   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
5565
5566   void_type_node = make_node (VOID_TYPE);
5567   layout_type (void_type_node);
5568
5569   /* We are not going to have real types in C with less than byte alignment,
5570      so we might as well not have any types that claim to have it.  */
5571   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
5572   TYPE_USER_ALIGN (void_type_node) = 0;
5573
5574   null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
5575   layout_type (TREE_TYPE (null_pointer_node));
5576
5577   ptr_type_node = build_pointer_type (void_type_node);
5578   const_ptr_type_node
5579     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
5580   fileptr_type_node = ptr_type_node;
5581
5582   float_type_node = make_node (REAL_TYPE);
5583   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
5584   layout_type (float_type_node);
5585
5586   double_type_node = make_node (REAL_TYPE);
5587   if (short_double)
5588     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
5589   else
5590     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
5591   layout_type (double_type_node);
5592
5593   long_double_type_node = make_node (REAL_TYPE);
5594   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
5595   layout_type (long_double_type_node);
5596
5597   float_ptr_type_node = build_pointer_type (float_type_node);
5598   double_ptr_type_node = build_pointer_type (double_type_node);
5599   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
5600   integer_ptr_type_node = build_pointer_type (integer_type_node);
5601
5602   complex_integer_type_node = make_node (COMPLEX_TYPE);
5603   TREE_TYPE (complex_integer_type_node) = integer_type_node;
5604   layout_type (complex_integer_type_node);
5605
5606   complex_float_type_node = make_node (COMPLEX_TYPE);
5607   TREE_TYPE (complex_float_type_node) = float_type_node;
5608   layout_type (complex_float_type_node);
5609
5610   complex_double_type_node = make_node (COMPLEX_TYPE);
5611   TREE_TYPE (complex_double_type_node) = double_type_node;
5612   layout_type (complex_double_type_node);
5613
5614   complex_long_double_type_node = make_node (COMPLEX_TYPE);
5615   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
5616   layout_type (complex_long_double_type_node);
5617
5618   {
5619     tree t = targetm.build_builtin_va_list ();
5620
5621     /* Many back-ends define record types without setting TYPE_NAME.
5622        If we copied the record type here, we'd keep the original
5623        record type without a name.  This breaks name mangling.  So,
5624        don't copy record types and let c_common_nodes_and_builtins()
5625        declare the type to be __builtin_va_list.  */
5626     if (TREE_CODE (t) != RECORD_TYPE)
5627       t = build_variant_type_copy (t);
5628
5629     va_list_type_node = t;
5630   }
5631 }
5632
5633 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
5634    better way.
5635
5636    If we requested a pointer to a vector, build up the pointers that
5637    we stripped off while looking for the inner type.  Similarly for
5638    return values from functions.
5639
5640    The argument TYPE is the top of the chain, and BOTTOM is the
5641    new type which we will point to.  */
5642
5643 tree
5644 reconstruct_complex_type (tree type, tree bottom)
5645 {
5646   tree inner, outer;
5647
5648   if (POINTER_TYPE_P (type))
5649     {
5650       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5651       outer = build_pointer_type (inner);
5652     }
5653   else if (TREE_CODE (type) == ARRAY_TYPE)
5654     {
5655       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5656       outer = build_array_type (inner, TYPE_DOMAIN (type));
5657     }
5658   else if (TREE_CODE (type) == FUNCTION_TYPE)
5659     {
5660       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5661       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
5662     }
5663   else if (TREE_CODE (type) == METHOD_TYPE)
5664     {
5665       tree argtypes;
5666       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
5667       /* The build_method_type_directly() routine prepends 'this' to argument list,
5668          so we must compensate by getting rid of it.  */
5669       argtypes = TYPE_ARG_TYPES (type);
5670       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
5671                                           inner,
5672                                           TYPE_ARG_TYPES (type));
5673       TYPE_ARG_TYPES (outer) = argtypes;
5674     }
5675   else
5676     return bottom;
5677
5678   TYPE_READONLY (outer) = TYPE_READONLY (type);
5679   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
5680
5681   return outer;
5682 }
5683
5684 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
5685    the inner type.  */
5686 tree
5687 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
5688 {
5689   int nunits;
5690
5691   switch (GET_MODE_CLASS (mode))
5692     {
5693     case MODE_VECTOR_INT:
5694     case MODE_VECTOR_FLOAT:
5695       nunits = GET_MODE_NUNITS (mode);
5696       break;
5697
5698     case MODE_INT:
5699       /* Check that there are no leftover bits.  */
5700       gcc_assert (GET_MODE_BITSIZE (mode)
5701                   % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
5702
5703       nunits = GET_MODE_BITSIZE (mode)
5704                / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
5705       break;
5706
5707     default:
5708       gcc_unreachable ();
5709     }
5710
5711   return make_vector_type (innertype, nunits, mode);
5712 }
5713
5714 /* Similarly, but takes the inner type and number of units, which must be
5715    a power of two.  */
5716
5717 tree
5718 build_vector_type (tree innertype, int nunits)
5719 {
5720   return make_vector_type (innertype, nunits, VOIDmode);
5721 }
5722
5723 /* Given an initializer INIT, return TRUE if INIT is zero or some
5724    aggregate of zeros.  Otherwise return FALSE.  */
5725 bool
5726 initializer_zerop (tree init)
5727 {
5728   tree elt;
5729
5730   STRIP_NOPS (init);
5731
5732   switch (TREE_CODE (init))
5733     {
5734     case INTEGER_CST:
5735       return integer_zerop (init);
5736
5737     case REAL_CST:
5738       /* ??? Note that this is not correct for C4X float formats.  There,
5739          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
5740          negative exponent.  */
5741       return real_zerop (init)
5742         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
5743
5744     case COMPLEX_CST:
5745       return integer_zerop (init)
5746         || (real_zerop (init)
5747             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
5748             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
5749
5750     case VECTOR_CST:
5751       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
5752         if (!initializer_zerop (TREE_VALUE (elt)))
5753           return false;
5754       return true;
5755
5756     case CONSTRUCTOR:
5757       elt = CONSTRUCTOR_ELTS (init);
5758       if (elt == NULL_TREE)
5759         return true;
5760
5761       /* A set is empty only if it has no elements.  */
5762       if (TREE_CODE (TREE_TYPE (init)) == SET_TYPE)
5763         return false;
5764
5765       for (; elt ; elt = TREE_CHAIN (elt))
5766         if (! initializer_zerop (TREE_VALUE (elt)))
5767           return false;
5768       return true;
5769
5770     default:
5771       return false;
5772     }
5773 }
5774
5775 void
5776 add_var_to_bind_expr (tree bind_expr, tree var)
5777 {
5778   BIND_EXPR_VARS (bind_expr)
5779     = chainon (BIND_EXPR_VARS (bind_expr), var);
5780   if (BIND_EXPR_BLOCK (bind_expr))
5781     BLOCK_VARS (BIND_EXPR_BLOCK (bind_expr))
5782       = BIND_EXPR_VARS (bind_expr);
5783 }
5784
5785 /* Build an empty statement.  */
5786
5787 tree
5788 build_empty_stmt (void)
5789 {
5790   return build1 (NOP_EXPR, void_type_node, size_zero_node);
5791 }
5792
5793
5794 /* Returns true if it is possible to prove that the index of
5795    an array access REF (an ARRAY_REF expression) falls into the
5796    array bounds.  */
5797
5798 bool
5799 in_array_bounds_p (tree ref)
5800 {
5801   tree idx = TREE_OPERAND (ref, 1);
5802   tree min, max;
5803
5804   if (TREE_CODE (idx) != INTEGER_CST)
5805     return false;
5806
5807   min = array_ref_low_bound (ref);
5808   max = array_ref_up_bound (ref);
5809   if (!min
5810       || !max
5811       || TREE_CODE (min) != INTEGER_CST
5812       || TREE_CODE (max) != INTEGER_CST)
5813     return false;
5814
5815   if (tree_int_cst_lt (idx, min)
5816       || tree_int_cst_lt (max, idx))
5817     return false;
5818
5819   return true;
5820 }
5821
5822 /* Return true if T (assumed to be a DECL) is a global variable.  */
5823
5824 bool
5825 is_global_var (tree t)
5826 {
5827   return (TREE_STATIC (t) || DECL_EXTERNAL (t));
5828 }
5829
5830 /* Return true if T (assumed to be a DECL) must be assigned a memory
5831    location.  */
5832
5833 bool
5834 needs_to_live_in_memory (tree t)
5835 {
5836   return (TREE_ADDRESSABLE (t)
5837           || is_global_var (t)
5838           || (TREE_CODE (t) == RESULT_DECL
5839               && aggregate_value_p (t, current_function_decl)));
5840 }
5841
5842 /* There are situations in which a language considers record types
5843    compatible which have different field lists.  Decide if two fields
5844    are compatible.  It is assumed that the parent records are compatible.  */
5845
5846 bool
5847 fields_compatible_p (tree f1, tree f2)
5848 {
5849   if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
5850                         DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
5851     return false;
5852
5853   if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
5854                         DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
5855     return false;
5856
5857   if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
5858     return false;
5859
5860   return true;
5861 }
5862
5863 /* Locate within RECORD a field that is compatible with ORIG_FIELD.  */
5864
5865 tree
5866 find_compatible_field (tree record, tree orig_field)
5867 {
5868   tree f;
5869
5870   for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
5871     if (TREE_CODE (f) == FIELD_DECL
5872         && fields_compatible_p (f, orig_field))
5873       return f;
5874
5875   /* ??? Why isn't this on the main fields list?  */
5876   f = TYPE_VFIELD (record);
5877   if (f && TREE_CODE (f) == FIELD_DECL
5878       && fields_compatible_p (f, orig_field))
5879     return f;
5880
5881   /* ??? We should abort here, but Java appears to do Bad Things
5882      with inherited fields.  */
5883   return orig_field;
5884 }
5885
5886 /* Return value of a constant X.  */
5887
5888 HOST_WIDE_INT
5889 int_cst_value (tree x)
5890 {
5891   unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
5892   unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
5893   bool negative = ((val >> (bits - 1)) & 1) != 0;
5894
5895   gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
5896
5897   if (negative)
5898     val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
5899   else
5900     val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
5901
5902   return val;
5903 }
5904
5905 /* Returns the greatest common divisor of A and B, which must be
5906    INTEGER_CSTs.  */
5907
5908 tree
5909 tree_fold_gcd (tree a, tree b)
5910 {
5911   tree a_mod_b;
5912   tree type = TREE_TYPE (a);
5913
5914   gcc_assert (TREE_CODE (a) == INTEGER_CST);
5915   gcc_assert (TREE_CODE (b) == INTEGER_CST);
5916
5917   if (integer_zerop (a))
5918     return b;
5919
5920   if (integer_zerop (b))
5921     return a;
5922
5923   if (tree_int_cst_sgn (a) == -1)
5924     a = fold (build2 (MULT_EXPR, type, a,
5925                       convert (type, integer_minus_one_node)));
5926
5927   if (tree_int_cst_sgn (b) == -1)
5928     b = fold (build2 (MULT_EXPR, type, b,
5929                       convert (type, integer_minus_one_node)));
5930
5931   while (1)
5932     {
5933       a_mod_b = fold (build2 (CEIL_MOD_EXPR, type, a, b));
5934
5935       if (!TREE_INT_CST_LOW (a_mod_b)
5936           && !TREE_INT_CST_HIGH (a_mod_b))
5937         return b;
5938
5939       a = b;
5940       b = a_mod_b;
5941     }
5942 }
5943
5944 /* Returns unsigned variant of TYPE.  */
5945
5946 tree
5947 unsigned_type_for (tree type)
5948 {
5949   return lang_hooks.types.unsigned_type (type);
5950 }
5951
5952 /* Returns signed variant of TYPE.  */
5953
5954 tree
5955 signed_type_for (tree type)
5956 {
5957   return lang_hooks.types.signed_type (type);
5958 }
5959
5960 #include "gt-tree.h"