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