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