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