gcc/tree.c

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