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