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, 2006
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 /* This file contains the low level primitives for operating on tree nodes,
  24    including allocation, list operations, interning of identifiers,
  25    construction of data type nodes and statement nodes,
  26    and construction of type conversion nodes.  It also contains
  27    tables index by tree code that describe how to take apart
  28    nodes of that code.
  29
  30    It is intended to be language-independent, but occasionally
  31    calls language-dependent routines defined (for C) in typecheck.c.  */
  32
  33 #include "config.h"
  34 #include "system.h"
  35 #include "coretypes.h"
  36 #include "tm.h"
  37 #include "flags.h"
  38 #include "tree.h"
  39 #include "real.h"
  40 #include "tm_p.h"
  41 #include "function.h"
  42 #include "obstack.h"
  43 #include "toplev.h"
  44 #include "ggc.h"
  45 #include "hashtab.h"
  46 #include "output.h"
  47 #include "target.h"
  48 #include "langhooks.h"
  49 #include "tree-iterator.h"
  50 #include "basic-block.h"
  51 #include "tree-flow.h"
  52 #include "params.h"
  53 #include "pointer-set.h"
  54
  55 /* Each tree code class has an associated string representation.
  56    These must correspond to the tree_code_class entries.  */
  57
  58 const char *const tree_code_class_strings[] =
  59 {
  60   "exceptional",
  61   "constant",
  62   "type",
  63   "declaration",
  64   "reference",
  65   "comparison",
  66   "unary",
  67   "binary",
  68   "statement",
  69   "expression",
  70 };
  71
  72 /* obstack.[ch] explicitly declined to prototype this.  */
  73 extern int _obstack_allocated_p (struct obstack *h, void *obj);
  74
  75 #ifdef GATHER_STATISTICS
  76 /* Statistics-gathering stuff.  */
  77
  78 int tree_node_counts[(int) all_kinds];
  79 int tree_node_sizes[(int) all_kinds];
  80
  81 /* Keep in sync with tree.h:enum tree_node_kind.  */
  82 static const char * const tree_node_kind_names[] = {
  83   "decls",
  84   "types",
  85   "blocks",
  86   "stmts",
  87   "refs",
  88   "exprs",
  89   "constants",
  90   "identifiers",
  91   "perm_tree_lists",
  92   "temp_tree_lists",
  93   "vecs",
  94   "binfos",
  95   "phi_nodes",
  96   "ssa names",
  97   "constructors",
  98   "random kinds",
  99   "lang_decl kinds",
 100   "lang_type kinds",
 101   "omp clauses"
 102 };
 103 #endif /* GATHER_STATISTICS */
 104
 105 /* Unique id for next decl created.  */
 106 static GTY(()) int next_decl_uid;
 107 /* Unique id for next type created.  */
 108 static GTY(()) int next_type_uid = 1;
 109
 110 /* Since we cannot rehash a type after it is in the table, we have to
 111    keep the hash code.  */
 112
 113 struct type_hash GTY(())
 114 {
 115   unsigned long hash;
 116   tree type;
 117 };
 118
 119 /* Initial size of the hash table (rounded to next prime).  */
 120 #define TYPE_HASH_INITIAL_SIZE 1000
 121
 122 /* Now here is the hash table.  When recording a type, it is added to
 123    the slot whose index is the hash code.  Note that the hash table is
 124    used for several kinds of types (function types, array types and
 125    array index range types, for now).  While all these live in the
 126    same table, they are completely independent, and the hash code is
 127    computed differently for each of these.  */
 128
 129 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
 130      htab_t type_hash_table;
 131
 132 /* Hash table and temporary node for larger integer const values.  */
 133 static GTY (()) tree int_cst_node;
 134 static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
 135      htab_t int_cst_hash_table;
 136
 137 /* General tree->tree mapping  structure for use in hash tables.  */
 138
 139
 140 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 141      htab_t debug_expr_for_decl;
 142
 143 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 144      htab_t value_expr_for_decl;
 145
 146 static GTY ((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
 147   htab_t init_priority_for_decl;
 148
 149 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 150   htab_t restrict_base_for_decl;
 151
 152 struct tree_int_map GTY(())
 153 {
 154   tree from;
 155   unsigned short to;
 156 };
 157 static unsigned int tree_int_map_hash (const void *);
 158 static int tree_int_map_eq (const void *, const void *);
 159 static int tree_int_map_marked_p (const void *);
 160 static void set_type_quals (tree, int);
 161 static int type_hash_eq (const void *, const void *);
 162 static hashval_t type_hash_hash (const void *);
 163 static hashval_t int_cst_hash_hash (const void *);
 164 static int int_cst_hash_eq (const void *, const void *);
 165 static void print_type_hash_statistics (void);
 166 static void print_debug_expr_statistics (void);
 167 static void print_value_expr_statistics (void);
 168 static tree make_vector_type (tree, int, enum machine_mode);
 169 static int type_hash_marked_p (const void *);
 170 static unsigned int type_hash_list (tree, hashval_t);
 171 static unsigned int attribute_hash_list (tree, hashval_t);
 172
 173 tree global_trees[TI_MAX];
 174 tree integer_types[itk_none];
 175
 176 unsigned char tree_contains_struct[256][64];
 177
 178 /* Number of operands for each OpenMP clause.  */
 179 unsigned const char omp_clause_num_ops[] =
 180 {
 181   0, /* OMP_CLAUSE_ERROR  */
 182   1, /* OMP_CLAUSE_PRIVATE  */
 183   1, /* OMP_CLAUSE_SHARED  */
 184   1, /* OMP_CLAUSE_FIRSTPRIVATE  */
 185   1, /* OMP_CLAUSE_LASTPRIVATE  */
 186   4, /* OMP_CLAUSE_REDUCTION  */
 187   1, /* OMP_CLAUSE_COPYIN  */
 188   1, /* OMP_CLAUSE_COPYPRIVATE  */
 189   1, /* OMP_CLAUSE_IF  */
 190   1, /* OMP_CLAUSE_NUM_THREADS  */
 191   1, /* OMP_CLAUSE_SCHEDULE  */
 192   0, /* OMP_CLAUSE_NOWAIT  */
 193   0, /* OMP_CLAUSE_ORDERED  */
 194   0  /* OMP_CLAUSE_DEFAULT  */
 195 };
 196
 197 const char * const omp_clause_code_name[] =
 198 {
 199   "error_clause",
 200   "private",
 201   "shared",
 202   "firstprivate",
 203   "lastprivate",
 204   "reduction",
 205   "copyin",
 206   "copyprivate",
 207   "if",
 208   "num_threads",
 209   "schedule",
 210   "nowait",
 211   "ordered",
 212   "default"
 213 };
 214 \f
 215 /* Init tree.c.  */
 216
 217 void
 218 init_ttree (void)
 219 {
 220   /* Initialize the hash table of types.  */
 221   type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
 222                                      type_hash_eq, 0);
 223
 224   debug_expr_for_decl = htab_create_ggc (512, tree_map_hash,
 225                                          tree_map_eq, 0);
 226
 227   value_expr_for_decl = htab_create_ggc (512, tree_map_hash,
 228                                          tree_map_eq, 0);
 229   init_priority_for_decl = htab_create_ggc (512, tree_int_map_hash,
 230                                             tree_int_map_eq, 0);
 231   restrict_base_for_decl = htab_create_ggc (256, tree_map_hash,
 232                                             tree_map_eq, 0);
 233
 234   int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash,
 235                                         int_cst_hash_eq, NULL);
 236
 237   int_cst_node = make_node (INTEGER_CST);
 238
 239   tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON] = 1;
 240   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_NON_COMMON] = 1;
 241   tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON] = 1;
 242
 243
 244   tree_contains_struct[CONST_DECL][TS_DECL_COMMON] = 1;
 245   tree_contains_struct[VAR_DECL][TS_DECL_COMMON] = 1;
 246   tree_contains_struct[PARM_DECL][TS_DECL_COMMON] = 1;
 247   tree_contains_struct[RESULT_DECL][TS_DECL_COMMON] = 1;
 248   tree_contains_struct[FUNCTION_DECL][TS_DECL_COMMON] = 1;
 249   tree_contains_struct[TYPE_DECL][TS_DECL_COMMON] = 1;
 250   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_COMMON] = 1;
 251   tree_contains_struct[LABEL_DECL][TS_DECL_COMMON] = 1;
 252   tree_contains_struct[FIELD_DECL][TS_DECL_COMMON] = 1;
 253
 254
 255   tree_contains_struct[CONST_DECL][TS_DECL_WRTL] = 1;
 256   tree_contains_struct[VAR_DECL][TS_DECL_WRTL] = 1;
 257   tree_contains_struct[PARM_DECL][TS_DECL_WRTL] = 1;
 258   tree_contains_struct[RESULT_DECL][TS_DECL_WRTL] = 1;
 259   tree_contains_struct[FUNCTION_DECL][TS_DECL_WRTL] = 1;
 260   tree_contains_struct[LABEL_DECL][TS_DECL_WRTL] = 1;
 261
 262   tree_contains_struct[CONST_DECL][TS_DECL_MINIMAL] = 1;
 263   tree_contains_struct[VAR_DECL][TS_DECL_MINIMAL] = 1;
 264   tree_contains_struct[PARM_DECL][TS_DECL_MINIMAL] = 1;
 265   tree_contains_struct[RESULT_DECL][TS_DECL_MINIMAL] = 1;
 266   tree_contains_struct[FUNCTION_DECL][TS_DECL_MINIMAL] = 1;
 267   tree_contains_struct[TYPE_DECL][TS_DECL_MINIMAL] = 1;
 268   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_MINIMAL] = 1;
 269   tree_contains_struct[LABEL_DECL][TS_DECL_MINIMAL] = 1;
 270   tree_contains_struct[FIELD_DECL][TS_DECL_MINIMAL] = 1;
 271   tree_contains_struct[STRUCT_FIELD_TAG][TS_DECL_MINIMAL] = 1;
 272   tree_contains_struct[NAME_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
 273   tree_contains_struct[SYMBOL_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
 274
 275   tree_contains_struct[STRUCT_FIELD_TAG][TS_MEMORY_TAG] = 1;
 276   tree_contains_struct[NAME_MEMORY_TAG][TS_MEMORY_TAG] = 1;
 277   tree_contains_struct[SYMBOL_MEMORY_TAG][TS_MEMORY_TAG] = 1;
 278
 279   tree_contains_struct[STRUCT_FIELD_TAG][TS_STRUCT_FIELD_TAG] = 1;
 280
 281   tree_contains_struct[VAR_DECL][TS_DECL_WITH_VIS] = 1;
 282   tree_contains_struct[FUNCTION_DECL][TS_DECL_WITH_VIS] = 1;
 283   tree_contains_struct[TYPE_DECL][TS_DECL_WITH_VIS] = 1;
 284   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_WITH_VIS] = 1;
 285
 286   tree_contains_struct[VAR_DECL][TS_VAR_DECL] = 1;
 287   tree_contains_struct[FIELD_DECL][TS_FIELD_DECL] = 1;
 288   tree_contains_struct[PARM_DECL][TS_PARM_DECL] = 1;
 289   tree_contains_struct[LABEL_DECL][TS_LABEL_DECL] = 1;
 290   tree_contains_struct[RESULT_DECL][TS_RESULT_DECL] = 1;
 291   tree_contains_struct[CONST_DECL][TS_CONST_DECL] = 1;
 292   tree_contains_struct[TYPE_DECL][TS_TYPE_DECL] = 1;
 293   tree_contains_struct[FUNCTION_DECL][TS_FUNCTION_DECL] = 1;
 294
 295   lang_hooks.init_ts ();
 296 }
 297
 298 \f
 299 /* The name of the object as the assembler will see it (but before any
 300    translations made by ASM_OUTPUT_LABELREF).  Often this is the same
 301    as DECL_NAME.  It is an IDENTIFIER_NODE.  */
 302 tree
 303 decl_assembler_name (tree decl)
 304 {
 305   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 306     lang_hooks.set_decl_assembler_name (decl);
 307   return DECL_WITH_VIS_CHECK (decl)->decl_with_vis.assembler_name;
 308 }
 309
 310 /* Compute the number of bytes occupied by a tree with code CODE.
 311    This function cannot be used for TREE_VEC, PHI_NODE, or STRING_CST
 312    codes, which are of variable length.  */
 313 size_t
 314 tree_code_size (enum tree_code code)
 315 {
 316   switch (TREE_CODE_CLASS (code))
 317     {
 318     case tcc_declaration:  /* A decl node */
 319       {
 320         switch (code)
 321           {
 322           case FIELD_DECL:
 323             return sizeof (struct tree_field_decl);
 324           case PARM_DECL:
 325             return sizeof (struct tree_parm_decl);
 326           case VAR_DECL:
 327             return sizeof (struct tree_var_decl);
 328           case LABEL_DECL:
 329             return sizeof (struct tree_label_decl);
 330           case RESULT_DECL:
 331             return sizeof (struct tree_result_decl);
 332           case CONST_DECL:
 333             return sizeof (struct tree_const_decl);
 334           case TYPE_DECL:
 335             return sizeof (struct tree_type_decl);
 336           case FUNCTION_DECL:
 337             return sizeof (struct tree_function_decl);
 338           case NAME_MEMORY_TAG:
 339           case SYMBOL_MEMORY_TAG:
 340             return sizeof (struct tree_memory_tag);
 341           case STRUCT_FIELD_TAG:
 342             return sizeof (struct tree_struct_field_tag);
 343           default:
 344             return sizeof (struct tree_decl_non_common);
 345           }
 346       }
 347
 348     case tcc_type:  /* a type node */
 349       return sizeof (struct tree_type);
 350
 351     case tcc_reference:   /* a reference */
 352     case tcc_expression:  /* an expression */
 353     case tcc_statement:   /* an expression with side effects */
 354     case tcc_comparison:  /* a comparison expression */
 355     case tcc_unary:       /* a unary arithmetic expression */
 356     case tcc_binary:      /* a binary arithmetic expression */
 357       return (sizeof (struct tree_exp)
 358               + (TREE_CODE_LENGTH (code) - 1) * sizeof (char *));
 359
 360     case tcc_constant:  /* a constant */
 361       switch (code)
 362         {
 363         case INTEGER_CST:       return sizeof (struct tree_int_cst);
 364         case REAL_CST:          return sizeof (struct tree_real_cst);
 365         case COMPLEX_CST:       return sizeof (struct tree_complex);
 366         case VECTOR_CST:        return sizeof (struct tree_vector);
 367         case STRING_CST:        gcc_unreachable ();
 368         default:
 369           return lang_hooks.tree_size (code);
 370         }
 371
 372     case tcc_exceptional:  /* something random, like an identifier.  */
 373       switch (code)
 374         {
 375         case IDENTIFIER_NODE:   return lang_hooks.identifier_size;
 376         case TREE_LIST:         return sizeof (struct tree_list);
 377
 378         case ERROR_MARK:
 379         case PLACEHOLDER_EXPR:  return sizeof (struct tree_common);
 380
 381         case TREE_VEC:
 382         case OMP_CLAUSE:
 383         case PHI_NODE:          gcc_unreachable ();
 384
 385         case SSA_NAME:          return sizeof (struct tree_ssa_name);
 386
 387         case STATEMENT_LIST:    return sizeof (struct tree_statement_list);
 388         case BLOCK:             return sizeof (struct tree_block);
 389         case VALUE_HANDLE:      return sizeof (struct tree_value_handle);
 390         case CONSTRUCTOR:       return sizeof (struct tree_constructor);
 391
 392         default:
 393           return lang_hooks.tree_size (code);
 394         }
 395
 396     default:
 397       gcc_unreachable ();
 398     }
 399 }
 400
 401 /* Compute the number of bytes occupied by NODE.  This routine only
 402    looks at TREE_CODE, except for PHI_NODE and TREE_VEC nodes.  */
 403 size_t
 404 tree_size (tree node)
 405 {
 406   enum tree_code code = TREE_CODE (node);
 407   switch (code)
 408     {
 409     case PHI_NODE:
 410       return (sizeof (struct tree_phi_node)
 411               + (PHI_ARG_CAPACITY (node) - 1) * sizeof (struct phi_arg_d));
 412
 413     case TREE_BINFO:
 414       return (offsetof (struct tree_binfo, base_binfos)
 415               + VEC_embedded_size (tree, BINFO_N_BASE_BINFOS (node)));
 416
 417     case TREE_VEC:
 418       return (sizeof (struct tree_vec)
 419               + (TREE_VEC_LENGTH (node) - 1) * sizeof(char *));
 420
 421     case STRING_CST:
 422       return sizeof (struct tree_string) + TREE_STRING_LENGTH (node) - 1;
 423
 424     case OMP_CLAUSE:
 425       return (sizeof (struct tree_omp_clause)
 426               + (omp_clause_num_ops[OMP_CLAUSE_CODE (node)] - 1)
 427                 * sizeof (tree));
 428
 429     default:
 430       return tree_code_size (code);
 431     }
 432 }
 433
 434 /* Return a newly allocated node of code CODE.  For decl and type
 435    nodes, some other fields are initialized.  The rest of the node is
 436    initialized to zero.  This function cannot be used for PHI_NODE,
 437    TREE_VEC or OMP_CLAUSE nodes, which is enforced by asserts in
 438    tree_code_size.
 439
 440    Achoo!  I got a code in the node.  */
 441
 442 tree
 443 make_node_stat (enum tree_code code MEM_STAT_DECL)
 444 {
 445   tree t;
 446   enum tree_code_class type = TREE_CODE_CLASS (code);
 447   size_t length = tree_code_size (code);
 448 #ifdef GATHER_STATISTICS
 449   tree_node_kind kind;
 450
 451   switch (type)
 452     {
 453     case tcc_declaration:  /* A decl node */
 454       kind = d_kind;
 455       break;
 456
 457     case tcc_type:  /* a type node */
 458       kind = t_kind;
 459       break;
 460
 461     case tcc_statement:  /* an expression with side effects */
 462       kind = s_kind;
 463       break;
 464
 465     case tcc_reference:  /* a reference */
 466       kind = r_kind;
 467       break;
 468
 469     case tcc_expression:  /* an expression */
 470     case tcc_comparison:  /* a comparison expression */
 471     case tcc_unary:  /* a unary arithmetic expression */
 472     case tcc_binary:  /* a binary arithmetic expression */
 473       kind = e_kind;
 474       break;
 475
 476     case tcc_constant:  /* a constant */
 477       kind = c_kind;
 478       break;
 479
 480     case tcc_exceptional:  /* something random, like an identifier.  */
 481       switch (code)
 482         {
 483         case IDENTIFIER_NODE:
 484           kind = id_kind;
 485           break;
 486
 487         case TREE_VEC:
 488           kind = vec_kind;
 489           break;
 490
 491         case TREE_BINFO:
 492           kind = binfo_kind;
 493           break;
 494
 495         case PHI_NODE:
 496           kind = phi_kind;
 497           break;
 498
 499         case SSA_NAME:
 500           kind = ssa_name_kind;
 501           break;
 502
 503         case BLOCK:
 504           kind = b_kind;
 505           break;
 506
 507         case CONSTRUCTOR:
 508           kind = constr_kind;
 509           break;
 510
 511         default:
 512           kind = x_kind;
 513           break;
 514         }
 515       break;
 516
 517     default:
 518       gcc_unreachable ();
 519     }
 520
 521   tree_node_counts[(int) kind]++;
 522   tree_node_sizes[(int) kind] += length;
 523 #endif
 524
 525   if (code == IDENTIFIER_NODE)
 526     t = ggc_alloc_zone_pass_stat (length, &tree_id_zone);
 527   else
 528     t = ggc_alloc_zone_pass_stat (length, &tree_zone);
 529
 530   memset (t, 0, length);
 531
 532   TREE_SET_CODE (t, code);
 533
 534   switch (type)
 535     {
 536     case tcc_statement:
 537       TREE_SIDE_EFFECTS (t) = 1;
 538       break;
 539
 540     case tcc_declaration:
 541       if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
 542         DECL_IN_SYSTEM_HEADER (t) = in_system_header;
 543       if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
 544         {
 545           if (code != FUNCTION_DECL)
 546             DECL_ALIGN (t) = 1;
 547           DECL_USER_ALIGN (t) = 0;
 548           /* We have not yet computed the alias set for this declaration.  */
 549           DECL_POINTER_ALIAS_SET (t) = -1;
 550         }
 551       DECL_SOURCE_LOCATION (t) = input_location;
 552       DECL_UID (t) = next_decl_uid++;
 553
 554       break;
 555
 556     case tcc_type:
 557       TYPE_UID (t) = next_type_uid++;
 558       TYPE_ALIGN (t) = BITS_PER_UNIT;
 559       TYPE_USER_ALIGN (t) = 0;
 560       TYPE_MAIN_VARIANT (t) = t;
 561
 562       /* Default to no attributes for type, but let target change that.  */
 563       TYPE_ATTRIBUTES (t) = NULL_TREE;
 564       targetm.set_default_type_attributes (t);
 565
 566       /* We have not yet computed the alias set for this type.  */
 567       TYPE_ALIAS_SET (t) = -1;
 568       break;
 569
 570     case tcc_constant:
 571       TREE_CONSTANT (t) = 1;
 572       TREE_INVARIANT (t) = 1;
 573       break;
 574
 575     case tcc_expression:
 576       switch (code)
 577         {
 578         case INIT_EXPR:
 579         case MODIFY_EXPR:
 580         case VA_ARG_EXPR:
 581         case PREDECREMENT_EXPR:
 582         case PREINCREMENT_EXPR:
 583         case POSTDECREMENT_EXPR:
 584         case POSTINCREMENT_EXPR:
 585           /* All of these have side-effects, no matter what their
 586              operands are.  */
 587           TREE_SIDE_EFFECTS (t) = 1;
 588           break;
 589
 590         default:
 591           break;
 592         }
 593       break;
 594
 595     default:
 596       /* Other classes need no special treatment.  */
 597       break;
 598     }
 599
 600   return t;
 601 }
 602 \f
 603 /* Return a new node with the same contents as NODE except that its
 604    TREE_CHAIN is zero and it has a fresh uid.  */
 605
 606 tree
 607 copy_node_stat (tree node MEM_STAT_DECL)
 608 {
 609   tree t;
 610   enum tree_code code = TREE_CODE (node);
 611   size_t length;
 612
 613   gcc_assert (code != STATEMENT_LIST);
 614
 615   length = tree_size (node);
 616   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
 617   memcpy (t, node, length);
 618
 619   TREE_CHAIN (t) = 0;
 620   TREE_ASM_WRITTEN (t) = 0;
 621   TREE_VISITED (t) = 0;
 622   t->common.ann = 0;
 623
 624   if (TREE_CODE_CLASS (code) == tcc_declaration)
 625     {
 626       DECL_UID (t) = next_decl_uid++;
 627       if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL)
 628           && DECL_HAS_VALUE_EXPR_P (node))
 629         {
 630           SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
 631           DECL_HAS_VALUE_EXPR_P (t) = 1;
 632         }
 633       if (TREE_CODE (node) == VAR_DECL && DECL_HAS_INIT_PRIORITY_P (node))
 634         {
 635           SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
 636           DECL_HAS_INIT_PRIORITY_P (t) = 1;
 637         }
 638       if (TREE_CODE (node) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (node))
 639         {
 640           SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node));
 641           DECL_BASED_ON_RESTRICT_P (t) = 1;
 642         }
 643     }
 644   else if (TREE_CODE_CLASS (code) == tcc_type)
 645     {
 646       TYPE_UID (t) = next_type_uid++;
 647       /* The following is so that the debug code for
 648          the copy is different from the original type.
 649          The two statements usually duplicate each other
 650          (because they clear fields of the same union),
 651          but the optimizer should catch that.  */
 652       TYPE_SYMTAB_POINTER (t) = 0;
 653       TYPE_SYMTAB_ADDRESS (t) = 0;
 654
 655       /* Do not copy the values cache.  */
 656       if (TYPE_CACHED_VALUES_P(t))
 657         {
 658           TYPE_CACHED_VALUES_P (t) = 0;
 659           TYPE_CACHED_VALUES (t) = NULL_TREE;
 660         }
 661     }
 662
 663   return t;
 664 }
 665
 666 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
 667    For example, this can copy a list made of TREE_LIST nodes.  */
 668
 669 tree
 670 copy_list (tree list)
 671 {
 672   tree head;
 673   tree prev, next;
 674
 675   if (list == 0)
 676     return 0;
 677
 678   head = prev = copy_node (list);
 679   next = TREE_CHAIN (list);
 680   while (next)
 681     {
 682       TREE_CHAIN (prev) = copy_node (next);
 683       prev = TREE_CHAIN (prev);
 684       next = TREE_CHAIN (next);
 685     }
 686   return head;
 687 }
 688
 689 \f
 690 /* Create an INT_CST node with a LOW value sign extended.  */
 691
 692 tree
 693 build_int_cst (tree type, HOST_WIDE_INT low)
 694 {
 695   return build_int_cst_wide (type, low, low < 0 ? -1 : 0);
 696 }
 697
 698 /* Create an INT_CST node with a LOW value zero extended.  */
 699
 700 tree
 701 build_int_cstu (tree type, unsigned HOST_WIDE_INT low)
 702 {
 703   return build_int_cst_wide (type, low, 0);
 704 }
 705
 706 /* Create an INT_CST node with a LOW value in TYPE.  The value is sign extended
 707    if it is negative.  This function is similar to build_int_cst, but
 708    the extra bits outside of the type precision are cleared.  Constants
 709    with these extra bits may confuse the fold so that it detects overflows
 710    even in cases when they do not occur, and in general should be avoided.
 711    We cannot however make this a default behavior of build_int_cst without
 712    more intrusive changes, since there are parts of gcc that rely on the extra
 713    precision of the integer constants.  */
 714
 715 tree
 716 build_int_cst_type (tree type, HOST_WIDE_INT low)
 717 {
 718   unsigned HOST_WIDE_INT val = (unsigned HOST_WIDE_INT) low;
 719   unsigned HOST_WIDE_INT hi, mask;
 720   unsigned bits;
 721   bool signed_p;
 722   bool negative;
 723
 724   if (!type)
 725     type = integer_type_node;
 726
 727   bits = TYPE_PRECISION (type);
 728   signed_p = !TYPE_UNSIGNED (type);
 729
 730   if (bits >= HOST_BITS_PER_WIDE_INT)
 731     negative = (low < 0);
 732   else
 733     {
 734       /* If the sign bit is inside precision of LOW, use it to determine
 735          the sign of the constant.  */
 736       negative = ((val >> (bits - 1)) & 1) != 0;
 737
 738       /* Mask out the bits outside of the precision of the constant.  */
 739       mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
 740
 741       if (signed_p && negative)
 742         val |= ~mask;
 743       else
 744         val &= mask;
 745     }
 746
 747   /* Determine the high bits.  */
 748   hi = (negative ? ~(unsigned HOST_WIDE_INT) 0 : 0);
 749
 750   /* For unsigned type we need to mask out the bits outside of the type
 751      precision.  */
 752   if (!signed_p)
 753     {
 754       if (bits <= HOST_BITS_PER_WIDE_INT)
 755         hi = 0;
 756       else
 757         {
 758           bits -= HOST_BITS_PER_WIDE_INT;
 759           mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
 760           hi &= mask;
 761         }
 762     }
 763
 764   return build_int_cst_wide (type, val, hi);
 765 }
 766
 767 /* These are the hash table functions for the hash table of INTEGER_CST
 768    nodes of a sizetype.  */
 769
 770 /* Return the hash code code X, an INTEGER_CST.  */
 771
 772 static hashval_t
 773 int_cst_hash_hash (const void *x)
 774 {
 775   tree t = (tree) x;
 776
 777   return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
 778           ^ htab_hash_pointer (TREE_TYPE (t)));
 779 }
 780
 781 /* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
 782    is the same as that given by *Y, which is the same.  */
 783
 784 static int
 785 int_cst_hash_eq (const void *x, const void *y)
 786 {
 787   tree xt = (tree) x;
 788   tree yt = (tree) y;
 789
 790   return (TREE_TYPE (xt) == TREE_TYPE (yt)
 791           && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
 792           && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt));
 793 }
 794
 795 /* Create an INT_CST node of TYPE and value HI:LOW.  If TYPE is NULL,
 796    integer_type_node is used.  The returned node is always shared.
 797    For small integers we use a per-type vector cache, for larger ones
 798    we use a single hash table.  */
 799
 800 tree
 801 build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
 802 {
 803   tree t;
 804   int ix = -1;
 805   int limit = 0;
 806
 807   if (!type)
 808     type = integer_type_node;
 809
 810   switch (TREE_CODE (type))
 811     {
 812     case POINTER_TYPE:
 813     case REFERENCE_TYPE:
 814       /* Cache NULL pointer.  */
 815       if (!hi && !low)
 816         {
 817           limit = 1;
 818           ix = 0;
 819         }
 820       break;
 821
 822     case BOOLEAN_TYPE:
 823       /* Cache false or true.  */
 824       limit = 2;
 825       if (!hi && low < 2)
 826         ix = low;
 827       break;
 828
 829     case INTEGER_TYPE:
 830     case OFFSET_TYPE:
 831       if (TYPE_UNSIGNED (type))
 832         {
 833           /* Cache 0..N */
 834           limit = INTEGER_SHARE_LIMIT;
 835           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 836             ix = low;
 837         }
 838       else
 839         {
 840           /* Cache -1..N */
 841           limit = INTEGER_SHARE_LIMIT + 1;
 842           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 843             ix = low + 1;
 844           else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
 845             ix = 0;
 846         }
 847       break;
 848     default:
 849       break;
 850     }
 851
 852   if (ix >= 0)
 853     {
 854       /* Look for it in the type's vector of small shared ints.  */
 855       if (!TYPE_CACHED_VALUES_P (type))
 856         {
 857           TYPE_CACHED_VALUES_P (type) = 1;
 858           TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
 859         }
 860
 861       t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
 862       if (t)
 863         {
 864           /* Make sure no one is clobbering the shared constant.  */
 865           gcc_assert (TREE_TYPE (t) == type);
 866           gcc_assert (TREE_INT_CST_LOW (t) == low);
 867           gcc_assert (TREE_INT_CST_HIGH (t) == hi);
 868         }
 869       else
 870         {
 871           /* Create a new shared int.  */
 872           t = make_node (INTEGER_CST);
 873
 874           TREE_INT_CST_LOW (t) = low;
 875           TREE_INT_CST_HIGH (t) = hi;
 876           TREE_TYPE (t) = type;
 877
 878           TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
 879         }
 880     }
 881   else
 882     {
 883       /* Use the cache of larger shared ints.  */
 884       void **slot;
 885
 886       TREE_INT_CST_LOW (int_cst_node) = low;
 887       TREE_INT_CST_HIGH (int_cst_node) = hi;
 888       TREE_TYPE (int_cst_node) = type;
 889
 890       slot = htab_find_slot (int_cst_hash_table, int_cst_node, INSERT);
 891       t = *slot;
 892       if (!t)
 893         {
 894           /* Insert this one into the hash table.  */
 895           t = int_cst_node;
 896           *slot = t;
 897           /* Make a new node for next time round.  */
 898           int_cst_node = make_node (INTEGER_CST);
 899         }
 900     }
 901
 902   return t;
 903 }
 904
 905 /* Builds an integer constant in TYPE such that lowest BITS bits are ones
 906    and the rest are zeros.  */
 907
 908 tree
 909 build_low_bits_mask (tree type, unsigned bits)
 910 {
 911   unsigned HOST_WIDE_INT low;
 912   HOST_WIDE_INT high;
 913   unsigned HOST_WIDE_INT all_ones = ~(unsigned HOST_WIDE_INT) 0;
 914
 915   gcc_assert (bits <= TYPE_PRECISION (type));
 916
 917   if (bits == TYPE_PRECISION (type)
 918       && !TYPE_UNSIGNED (type))
 919     {
 920       /* Sign extended all-ones mask.  */
 921       low = all_ones;
 922       high = -1;
 923     }
 924   else if (bits <= HOST_BITS_PER_WIDE_INT)
 925     {
 926       low = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
 927       high = 0;
 928     }
 929   else
 930     {
 931       bits -= HOST_BITS_PER_WIDE_INT;
 932       low = all_ones;
 933       high = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
 934     }
 935
 936   return build_int_cst_wide (type, low, high);
 937 }
 938
 939 /* Checks that X is integer constant that can be expressed in (unsigned)
 940    HOST_WIDE_INT without loss of precision.  */
 941
 942 bool
 943 cst_and_fits_in_hwi (tree x)
 944 {
 945   if (TREE_CODE (x) != INTEGER_CST)
 946     return false;
 947
 948   if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
 949     return false;
 950
 951   return (TREE_INT_CST_HIGH (x) == 0
 952           || TREE_INT_CST_HIGH (x) == -1);
 953 }
 954
 955 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 956    are in a list pointed to by VALS.  */
 957
 958 tree
 959 build_vector (tree type, tree vals)
 960 {
 961   tree v = make_node (VECTOR_CST);
 962   int over1 = 0, over2 = 0;
 963   tree link;
 964
 965   TREE_VECTOR_CST_ELTS (v) = vals;
 966   TREE_TYPE (v) = type;
 967
 968   /* Iterate through elements and check for overflow.  */
 969   for (link = vals; link; link = TREE_CHAIN (link))
 970     {
 971       tree value = TREE_VALUE (link);
 972
 973       over1 |= TREE_OVERFLOW (value);
 974       over2 |= TREE_CONSTANT_OVERFLOW (value);
 975     }
 976
 977   TREE_OVERFLOW (v) = over1;
 978   TREE_CONSTANT_OVERFLOW (v) = over2;
 979
 980   return v;
 981 }
 982
 983 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 984    are extracted from V, a vector of CONSTRUCTOR_ELT.  */
 985
 986 tree
 987 build_vector_from_ctor (tree type, VEC(constructor_elt,gc) *v)
 988 {
 989   tree list = NULL_TREE;
 990   unsigned HOST_WIDE_INT idx;
 991   tree value;
 992
 993   FOR_EACH_CONSTRUCTOR_VALUE (v, idx, value)
 994     list = tree_cons (NULL_TREE, value, list);
 995   return build_vector (type, nreverse (list));
 996 }
 997
 998 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
 999    are in the VEC pointed to by VALS.  */
1000 tree
1001 build_constructor (tree type, VEC(constructor_elt,gc) *vals)
1002 {
1003   tree c = make_node (CONSTRUCTOR);
1004   TREE_TYPE (c) = type;
1005   CONSTRUCTOR_ELTS (c) = vals;
1006   return c;
1007 }
1008
1009 /* Build a CONSTRUCTOR node made of a single initializer, with the specified
1010    INDEX and VALUE.  */
1011 tree
1012 build_constructor_single (tree type, tree index, tree value)
1013 {
1014   VEC(constructor_elt,gc) *v;
1015   constructor_elt *elt;
1016   tree t;
1017
1018   v = VEC_alloc (constructor_elt, gc, 1);
1019   elt = VEC_quick_push (constructor_elt, v, NULL);
1020   elt->index = index;
1021   elt->value = value;
1022
1023   t = build_constructor (type, v);
1024   TREE_CONSTANT (t) = TREE_CONSTANT (value);
1025   return t;
1026 }
1027
1028
1029 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1030    are in a list pointed to by VALS.  */
1031 tree
1032 build_constructor_from_list (tree type, tree vals)
1033 {
1034   tree t, val;
1035   VEC(constructor_elt,gc) *v = NULL;
1036   bool constant_p = true;
1037
1038   if (vals)
1039     {
1040       v = VEC_alloc (constructor_elt, gc, list_length (vals));
1041       for (t = vals; t; t = TREE_CHAIN (t))
1042         {
1043           constructor_elt *elt = VEC_quick_push (constructor_elt, v, NULL);
1044           val = TREE_VALUE (t);
1045           elt->index = TREE_PURPOSE (t);
1046           elt->value = val;
1047           if (!TREE_CONSTANT (val))
1048             constant_p = false;
1049         }
1050     }
1051
1052   t = build_constructor (type, v);
1053   TREE_CONSTANT (t) = constant_p;
1054   return t;
1055 }
1056
1057
1058 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
1059
1060 tree
1061 build_real (tree type, REAL_VALUE_TYPE d)
1062 {
1063   tree v;
1064   REAL_VALUE_TYPE *dp;
1065   int overflow = 0;
1066
1067   /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
1068      Consider doing it via real_convert now.  */
1069
1070   v = make_node (REAL_CST);
1071   dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
1072   memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
1073
1074   TREE_TYPE (v) = type;
1075   TREE_REAL_CST_PTR (v) = dp;
1076   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
1077   return v;
1078 }
1079
1080 /* Return a new REAL_CST node whose type is TYPE
1081    and whose value is the integer value of the INTEGER_CST node I.  */
1082
1083 REAL_VALUE_TYPE
1084 real_value_from_int_cst (tree type, tree i)
1085 {
1086   REAL_VALUE_TYPE d;
1087
1088   /* Clear all bits of the real value type so that we can later do
1089      bitwise comparisons to see if two values are the same.  */
1090   memset (&d, 0, sizeof d);
1091
1092   real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
1093                      TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
1094                      TYPE_UNSIGNED (TREE_TYPE (i)));
1095   return d;
1096 }
1097
1098 /* Given a tree representing an integer constant I, return a tree
1099    representing the same value as a floating-point constant of type TYPE.  */
1100
1101 tree
1102 build_real_from_int_cst (tree type, tree i)
1103 {
1104   tree v;
1105   int overflow = TREE_OVERFLOW (i);
1106
1107   v = build_real (type, real_value_from_int_cst (type, i));
1108
1109   TREE_OVERFLOW (v) |= overflow;
1110   TREE_CONSTANT_OVERFLOW (v) |= overflow;
1111   return v;
1112 }
1113
1114 /* Return a newly constructed STRING_CST node whose value is
1115    the LEN characters at STR.
1116    The TREE_TYPE is not initialized.  */
1117
1118 tree
1119 build_string (int len, const char *str)
1120 {
1121   tree s;
1122   size_t length;
1123
1124   length = len + sizeof (struct tree_string);
1125
1126 #ifdef GATHER_STATISTICS
1127   tree_node_counts[(int) c_kind]++;
1128   tree_node_sizes[(int) c_kind] += length;
1129 #endif
1130
1131   s = ggc_alloc_tree (length);
1132
1133   memset (s, 0, sizeof (struct tree_common));
1134   TREE_SET_CODE (s, STRING_CST);
1135   TREE_CONSTANT (s) = 1;
1136   TREE_INVARIANT (s) = 1;
1137   TREE_STRING_LENGTH (s) = len;
1138   memcpy ((char *) TREE_STRING_POINTER (s), str, len);
1139   ((char *) TREE_STRING_POINTER (s))[len] = '\0';
1140
1141   return s;
1142 }
1143
1144 /* Return a newly constructed COMPLEX_CST node whose value is
1145    specified by the real and imaginary parts REAL and IMAG.
1146    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
1147    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
1148
1149 tree
1150 build_complex (tree type, tree real, tree imag)
1151 {
1152   tree t = make_node (COMPLEX_CST);
1153
1154   TREE_REALPART (t) = real;
1155   TREE_IMAGPART (t) = imag;
1156   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
1157   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
1158   TREE_CONSTANT_OVERFLOW (t)
1159     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
1160   return t;
1161 }
1162
1163 /* Build a BINFO with LEN language slots.  */
1164
1165 tree
1166 make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
1167 {
1168   tree t;
1169   size_t length = (offsetof (struct tree_binfo, base_binfos)
1170                    + VEC_embedded_size (tree, base_binfos));
1171
1172 #ifdef GATHER_STATISTICS
1173   tree_node_counts[(int) binfo_kind]++;
1174   tree_node_sizes[(int) binfo_kind] += length;
1175 #endif
1176
1177   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1178
1179   memset (t, 0, offsetof (struct tree_binfo, base_binfos));
1180
1181   TREE_SET_CODE (t, TREE_BINFO);
1182
1183   VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos);
1184
1185   return t;
1186 }
1187
1188
1189 /* Build a newly constructed TREE_VEC node of length LEN.  */
1190
1191 tree
1192 make_tree_vec_stat (int len MEM_STAT_DECL)
1193 {
1194   tree t;
1195   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
1196
1197 #ifdef GATHER_STATISTICS
1198   tree_node_counts[(int) vec_kind]++;
1199   tree_node_sizes[(int) vec_kind] += length;
1200 #endif
1201
1202   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1203
1204   memset (t, 0, length);
1205
1206   TREE_SET_CODE (t, TREE_VEC);
1207   TREE_VEC_LENGTH (t) = len;
1208
1209   return t;
1210 }
1211 \f
1212 /* Return 1 if EXPR is the integer constant zero or a complex constant
1213    of zero.  */
1214
1215 int
1216 integer_zerop (tree expr)
1217 {
1218   STRIP_NOPS (expr);
1219
1220   return ((TREE_CODE (expr) == INTEGER_CST
1221            && TREE_INT_CST_LOW (expr) == 0
1222            && TREE_INT_CST_HIGH (expr) == 0)
1223           || (TREE_CODE (expr) == COMPLEX_CST
1224               && integer_zerop (TREE_REALPART (expr))
1225               && integer_zerop (TREE_IMAGPART (expr))));
1226 }
1227
1228 /* Return 1 if EXPR is the integer constant one or the corresponding
1229    complex constant.  */
1230
1231 int
1232 integer_onep (tree expr)
1233 {
1234   STRIP_NOPS (expr);
1235
1236   return ((TREE_CODE (expr) == INTEGER_CST
1237            && TREE_INT_CST_LOW (expr) == 1
1238            && TREE_INT_CST_HIGH (expr) == 0)
1239           || (TREE_CODE (expr) == COMPLEX_CST
1240               && integer_onep (TREE_REALPART (expr))
1241               && integer_zerop (TREE_IMAGPART (expr))));
1242 }
1243
1244 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
1245    it contains.  Likewise for the corresponding complex constant.  */
1246
1247 int
1248 integer_all_onesp (tree expr)
1249 {
1250   int prec;
1251   int uns;
1252
1253   STRIP_NOPS (expr);
1254
1255   if (TREE_CODE (expr) == COMPLEX_CST
1256       && integer_all_onesp (TREE_REALPART (expr))
1257       && integer_zerop (TREE_IMAGPART (expr)))
1258     return 1;
1259
1260   else if (TREE_CODE (expr) != INTEGER_CST)
1261     return 0;
1262
1263   uns = TYPE_UNSIGNED (TREE_TYPE (expr));
1264   if (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1265       && TREE_INT_CST_HIGH (expr) == -1)
1266     return 1;
1267   if (!uns)
1268     return 0;
1269
1270   /* Note that using TYPE_PRECISION here is wrong.  We care about the
1271      actual bits, not the (arbitrary) range of the type.  */
1272   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
1273   if (prec >= HOST_BITS_PER_WIDE_INT)
1274     {
1275       HOST_WIDE_INT high_value;
1276       int shift_amount;
1277
1278       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
1279
1280       /* Can not handle precisions greater than twice the host int size.  */
1281       gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT);
1282       if (shift_amount == HOST_BITS_PER_WIDE_INT)
1283         /* Shifting by the host word size is undefined according to the ANSI
1284            standard, so we must handle this as a special case.  */
1285         high_value = -1;
1286       else
1287         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
1288
1289       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1290               && TREE_INT_CST_HIGH (expr) == high_value);
1291     }
1292   else
1293     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
1294 }
1295
1296 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
1297    one bit on).  */
1298
1299 int
1300 integer_pow2p (tree expr)
1301 {
1302   int prec;
1303   HOST_WIDE_INT high, low;
1304
1305   STRIP_NOPS (expr);
1306
1307   if (TREE_CODE (expr) == COMPLEX_CST
1308       && integer_pow2p (TREE_REALPART (expr))
1309       && integer_zerop (TREE_IMAGPART (expr)))
1310     return 1;
1311
1312   if (TREE_CODE (expr) != INTEGER_CST)
1313     return 0;
1314
1315   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1316           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1317   high = TREE_INT_CST_HIGH (expr);
1318   low = TREE_INT_CST_LOW (expr);
1319
1320   /* First clear all bits that are beyond the type's precision in case
1321      we've been sign extended.  */
1322
1323   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1324     ;
1325   else if (prec > HOST_BITS_PER_WIDE_INT)
1326     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1327   else
1328     {
1329       high = 0;
1330       if (prec < HOST_BITS_PER_WIDE_INT)
1331         low &= ~((HOST_WIDE_INT) (-1) << prec);
1332     }
1333
1334   if (high == 0 && low == 0)
1335     return 0;
1336
1337   return ((high == 0 && (low & (low - 1)) == 0)
1338           || (low == 0 && (high & (high - 1)) == 0));
1339 }
1340
1341 /* Return 1 if EXPR is an integer constant other than zero or a
1342    complex constant other than zero.  */
1343
1344 int
1345 integer_nonzerop (tree expr)
1346 {
1347   STRIP_NOPS (expr);
1348
1349   return ((TREE_CODE (expr) == INTEGER_CST
1350            && (TREE_INT_CST_LOW (expr) != 0
1351                || TREE_INT_CST_HIGH (expr) != 0))
1352           || (TREE_CODE (expr) == COMPLEX_CST
1353               && (integer_nonzerop (TREE_REALPART (expr))
1354                   || integer_nonzerop (TREE_IMAGPART (expr)))));
1355 }
1356
1357 /* Return the power of two represented by a tree node known to be a
1358    power of two.  */
1359
1360 int
1361 tree_log2 (tree expr)
1362 {
1363   int prec;
1364   HOST_WIDE_INT high, low;
1365
1366   STRIP_NOPS (expr);
1367
1368   if (TREE_CODE (expr) == COMPLEX_CST)
1369     return tree_log2 (TREE_REALPART (expr));
1370
1371   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1372           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1373
1374   high = TREE_INT_CST_HIGH (expr);
1375   low = TREE_INT_CST_LOW (expr);
1376
1377   /* First clear all bits that are beyond the type's precision in case
1378      we've been sign extended.  */
1379
1380   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1381     ;
1382   else if (prec > HOST_BITS_PER_WIDE_INT)
1383     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1384   else
1385     {
1386       high = 0;
1387       if (prec < HOST_BITS_PER_WIDE_INT)
1388         low &= ~((HOST_WIDE_INT) (-1) << prec);
1389     }
1390
1391   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
1392           : exact_log2 (low));
1393 }
1394
1395 /* Similar, but return the largest integer Y such that 2 ** Y is less
1396    than or equal to EXPR.  */
1397
1398 int
1399 tree_floor_log2 (tree expr)
1400 {
1401   int prec;
1402   HOST_WIDE_INT high, low;
1403
1404   STRIP_NOPS (expr);
1405
1406   if (TREE_CODE (expr) == COMPLEX_CST)
1407     return tree_log2 (TREE_REALPART (expr));
1408
1409   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1410           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1411
1412   high = TREE_INT_CST_HIGH (expr);
1413   low = TREE_INT_CST_LOW (expr);
1414
1415   /* First clear all bits that are beyond the type's precision in case
1416      we've been sign extended.  Ignore if type's precision hasn't been set
1417      since what we are doing is setting it.  */
1418
1419   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
1420     ;
1421   else if (prec > HOST_BITS_PER_WIDE_INT)
1422     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1423   else
1424     {
1425       high = 0;
1426       if (prec < HOST_BITS_PER_WIDE_INT)
1427         low &= ~((HOST_WIDE_INT) (-1) << prec);
1428     }
1429
1430   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
1431           : floor_log2 (low));
1432 }
1433
1434 /* Return 1 if EXPR is the real constant zero.  */
1435
1436 int
1437 real_zerop (tree expr)
1438 {
1439   STRIP_NOPS (expr);
1440
1441   return ((TREE_CODE (expr) == REAL_CST
1442            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
1443           || (TREE_CODE (expr) == COMPLEX_CST
1444               && real_zerop (TREE_REALPART (expr))
1445               && real_zerop (TREE_IMAGPART (expr))));
1446 }
1447
1448 /* Return 1 if EXPR is the real constant one in real or complex form.  */
1449
1450 int
1451 real_onep (tree expr)
1452 {
1453   STRIP_NOPS (expr);
1454
1455   return ((TREE_CODE (expr) == REAL_CST
1456            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1457           || (TREE_CODE (expr) == COMPLEX_CST
1458               && real_onep (TREE_REALPART (expr))
1459               && real_zerop (TREE_IMAGPART (expr))));
1460 }
1461
1462 /* Return 1 if EXPR is the real constant two.  */
1463
1464 int
1465 real_twop (tree expr)
1466 {
1467   STRIP_NOPS (expr);
1468
1469   return ((TREE_CODE (expr) == REAL_CST
1470            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1471           || (TREE_CODE (expr) == COMPLEX_CST
1472               && real_twop (TREE_REALPART (expr))
1473               && real_zerop (TREE_IMAGPART (expr))));
1474 }
1475
1476 /* Return 1 if EXPR is the real constant minus one.  */
1477
1478 int
1479 real_minus_onep (tree expr)
1480 {
1481   STRIP_NOPS (expr);
1482
1483   return ((TREE_CODE (expr) == REAL_CST
1484            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
1485           || (TREE_CODE (expr) == COMPLEX_CST
1486               && real_minus_onep (TREE_REALPART (expr))
1487               && real_zerop (TREE_IMAGPART (expr))));
1488 }
1489
1490 /* Nonzero if EXP is a constant or a cast of a constant.  */
1491
1492 int
1493 really_constant_p (tree exp)
1494 {
1495   /* This is not quite the same as STRIP_NOPS.  It does more.  */
1496   while (TREE_CODE (exp) == NOP_EXPR
1497          || TREE_CODE (exp) == CONVERT_EXPR
1498          || TREE_CODE (exp) == NON_LVALUE_EXPR)
1499     exp = TREE_OPERAND (exp, 0);
1500   return TREE_CONSTANT (exp);
1501 }
1502 \f
1503 /* Return first list element whose TREE_VALUE is ELEM.
1504    Return 0 if ELEM is not in LIST.  */
1505
1506 tree
1507 value_member (tree elem, tree list)
1508 {
1509   while (list)
1510     {
1511       if (elem == TREE_VALUE (list))
1512         return list;
1513       list = TREE_CHAIN (list);
1514     }
1515   return NULL_TREE;
1516 }
1517
1518 /* Return first list element whose TREE_PURPOSE is ELEM.
1519    Return 0 if ELEM is not in LIST.  */
1520
1521 tree
1522 purpose_member (tree elem, tree list)
1523 {
1524   while (list)
1525     {
1526       if (elem == TREE_PURPOSE (list))
1527         return list;
1528       list = TREE_CHAIN (list);
1529     }
1530   return NULL_TREE;
1531 }
1532
1533 /* Return nonzero if ELEM is part of the chain CHAIN.  */
1534
1535 int
1536 chain_member (tree elem, tree chain)
1537 {
1538   while (chain)
1539     {
1540       if (elem == chain)
1541         return 1;
1542       chain = TREE_CHAIN (chain);
1543     }
1544
1545   return 0;
1546 }
1547
1548 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1549    We expect a null pointer to mark the end of the chain.
1550    This is the Lisp primitive `length'.  */
1551
1552 int
1553 list_length (tree t)
1554 {
1555   tree p = t;
1556 #ifdef ENABLE_TREE_CHECKING
1557   tree q = t;
1558 #endif
1559   int len = 0;
1560
1561   while (p)
1562     {
1563       p = TREE_CHAIN (p);
1564 #ifdef ENABLE_TREE_CHECKING
1565       if (len % 2)
1566         q = TREE_CHAIN (q);
1567       gcc_assert (p != q);
1568 #endif
1569       len++;
1570     }
1571
1572   return len;
1573 }
1574
1575 /* Returns the number of FIELD_DECLs in TYPE.  */
1576
1577 int
1578 fields_length (tree type)
1579 {
1580   tree t = TYPE_FIELDS (type);
1581   int count = 0;
1582
1583   for (; t; t = TREE_CHAIN (t))
1584     if (TREE_CODE (t) == FIELD_DECL)
1585       ++count;
1586
1587   return count;
1588 }
1589
1590 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1591    by modifying the last node in chain 1 to point to chain 2.
1592    This is the Lisp primitive `nconc'.  */
1593
1594 tree
1595 chainon (tree op1, tree op2)
1596 {
1597   tree t1;
1598
1599   if (!op1)
1600     return op2;
1601   if (!op2)
1602     return op1;
1603
1604   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1605     continue;
1606   TREE_CHAIN (t1) = op2;
1607
1608 #ifdef ENABLE_TREE_CHECKING
1609   {
1610     tree t2;
1611     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1612       gcc_assert (t2 != t1);
1613   }
1614 #endif
1615
1616   return op1;
1617 }
1618
1619 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1620
1621 tree
1622 tree_last (tree chain)
1623 {
1624   tree next;
1625   if (chain)
1626     while ((next = TREE_CHAIN (chain)))
1627       chain = next;
1628   return chain;
1629 }
1630
1631 /* Reverse the order of elements in the chain T,
1632    and return the new head of the chain (old last element).  */
1633
1634 tree
1635 nreverse (tree t)
1636 {
1637   tree prev = 0, decl, next;
1638   for (decl = t; decl; decl = next)
1639     {
1640       next = TREE_CHAIN (decl);
1641       TREE_CHAIN (decl) = prev;
1642       prev = decl;
1643     }
1644   return prev;
1645 }
1646 \f
1647 /* Return a newly created TREE_LIST node whose
1648    purpose and value fields are PARM and VALUE.  */
1649
1650 tree
1651 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1652 {
1653   tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1654   TREE_PURPOSE (t) = parm;
1655   TREE_VALUE (t) = value;
1656   return t;
1657 }
1658
1659 /* Return a newly created TREE_LIST node whose
1660    purpose and value fields are PURPOSE and VALUE
1661    and whose TREE_CHAIN is CHAIN.  */
1662
1663 tree
1664 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1665 {
1666   tree node;
1667
1668   node = ggc_alloc_zone_pass_stat (sizeof (struct tree_list), &tree_zone);
1669
1670   memset (node, 0, sizeof (struct tree_common));
1671
1672 #ifdef GATHER_STATISTICS
1673   tree_node_counts[(int) x_kind]++;
1674   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1675 #endif
1676
1677   TREE_SET_CODE (node, TREE_LIST);
1678   TREE_CHAIN (node) = chain;
1679   TREE_PURPOSE (node) = purpose;
1680   TREE_VALUE (node) = value;
1681   return node;
1682 }
1683
1684 \f
1685 /* Return the size nominally occupied by an object of type TYPE
1686    when it resides in memory.  The value is measured in units of bytes,
1687    and its data type is that normally used for type sizes
1688    (which is the first type created by make_signed_type or
1689    make_unsigned_type).  */
1690
1691 tree
1692 size_in_bytes (tree type)
1693 {
1694   tree t;
1695
1696   if (type == error_mark_node)
1697     return integer_zero_node;
1698
1699   type = TYPE_MAIN_VARIANT (type);
1700   t = TYPE_SIZE_UNIT (type);
1701
1702   if (t == 0)
1703     {
1704       lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1705       return size_zero_node;
1706     }
1707
1708   if (TREE_CODE (t) == INTEGER_CST)
1709     t = force_fit_type (t, 0, false, false);
1710
1711   return t;
1712 }
1713
1714 /* Return the size of TYPE (in bytes) as a wide integer
1715    or return -1 if the size can vary or is larger than an integer.  */
1716
1717 HOST_WIDE_INT
1718 int_size_in_bytes (tree type)
1719 {
1720   tree t;
1721
1722   if (type == error_mark_node)
1723     return 0;
1724
1725   type = TYPE_MAIN_VARIANT (type);
1726   t = TYPE_SIZE_UNIT (type);
1727   if (t == 0
1728       || TREE_CODE (t) != INTEGER_CST
1729       || TREE_INT_CST_HIGH (t) != 0
1730       /* If the result would appear negative, it's too big to represent.  */
1731       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1732     return -1;
1733
1734   return TREE_INT_CST_LOW (t);
1735 }
1736
1737 /* Return the maximum size of TYPE (in bytes) as a wide integer
1738    or return -1 if the size can vary or is larger than an integer.  */
1739
1740 HOST_WIDE_INT
1741 max_int_size_in_bytes (tree type)
1742 {
1743   HOST_WIDE_INT size = -1;
1744   tree size_tree;
1745
1746   /* If this is an array type, check for a possible MAX_SIZE attached.  */
1747
1748   if (TREE_CODE (type) == ARRAY_TYPE)
1749     {
1750       size_tree = TYPE_ARRAY_MAX_SIZE (type);
1751
1752       if (size_tree && host_integerp (size_tree, 1))
1753         size = tree_low_cst (size_tree, 1);
1754     }
1755
1756   /* If we still haven't been able to get a size, see if the language
1757      can compute a maximum size.  */
1758
1759   if (size == -1)
1760     {
1761       size_tree = lang_hooks.types.max_size (type);
1762
1763       if (size_tree && host_integerp (size_tree, 1))
1764         size = tree_low_cst (size_tree, 1);
1765     }
1766
1767   return size;
1768 }
1769 \f
1770 /* Return the bit position of FIELD, in bits from the start of the record.
1771    This is a tree of type bitsizetype.  */
1772
1773 tree
1774 bit_position (tree field)
1775 {
1776   return bit_from_pos (DECL_FIELD_OFFSET (field),
1777                        DECL_FIELD_BIT_OFFSET (field));
1778 }
1779
1780 /* Likewise, but return as an integer.  It must be representable in
1781    that way (since it could be a signed value, we don't have the
1782    option of returning -1 like int_size_in_byte can.  */
1783
1784 HOST_WIDE_INT
1785 int_bit_position (tree field)
1786 {
1787   return tree_low_cst (bit_position (field), 0);
1788 }
1789 \f
1790 /* Return the byte position of FIELD, in bytes from the start of the record.
1791    This is a tree of type sizetype.  */
1792
1793 tree
1794 byte_position (tree field)
1795 {
1796   return byte_from_pos (DECL_FIELD_OFFSET (field),
1797                         DECL_FIELD_BIT_OFFSET (field));
1798 }
1799
1800 /* Likewise, but return as an integer.  It must be representable in
1801    that way (since it could be a signed value, we don't have the
1802    option of returning -1 like int_size_in_byte can.  */
1803
1804 HOST_WIDE_INT
1805 int_byte_position (tree field)
1806 {
1807   return tree_low_cst (byte_position (field), 0);
1808 }
1809 \f
1810 /* Return the strictest alignment, in bits, that T is known to have.  */
1811
1812 unsigned int
1813 expr_align (tree t)
1814 {
1815   unsigned int align0, align1;
1816
1817   switch (TREE_CODE (t))
1818     {
1819     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1820       /* If we have conversions, we know that the alignment of the
1821          object must meet each of the alignments of the types.  */
1822       align0 = expr_align (TREE_OPERAND (t, 0));
1823       align1 = TYPE_ALIGN (TREE_TYPE (t));
1824       return MAX (align0, align1);
1825
1826     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1827     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1828     case CLEANUP_POINT_EXPR:
1829       /* These don't change the alignment of an object.  */
1830       return expr_align (TREE_OPERAND (t, 0));
1831
1832     case COND_EXPR:
1833       /* The best we can do is say that the alignment is the least aligned
1834          of the two arms.  */
1835       align0 = expr_align (TREE_OPERAND (t, 1));
1836       align1 = expr_align (TREE_OPERAND (t, 2));
1837       return MIN (align0, align1);
1838
1839     case LABEL_DECL:     case CONST_DECL:
1840     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1841       if (DECL_ALIGN (t) != 0)
1842         return DECL_ALIGN (t);
1843       break;
1844
1845     case FUNCTION_DECL:
1846       return FUNCTION_BOUNDARY;
1847
1848     default:
1849       break;
1850     }
1851
1852   /* Otherwise take the alignment from that of the type.  */
1853   return TYPE_ALIGN (TREE_TYPE (t));
1854 }
1855 \f
1856 /* Return, as a tree node, the number of elements for TYPE (which is an
1857    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1858
1859 tree
1860 array_type_nelts (tree type)
1861 {
1862   tree index_type, min, max;
1863
1864   /* If they did it with unspecified bounds, then we should have already
1865      given an error about it before we got here.  */
1866   if (! TYPE_DOMAIN (type))
1867     return error_mark_node;
1868
1869   index_type = TYPE_DOMAIN (type);
1870   min = TYPE_MIN_VALUE (index_type);
1871   max = TYPE_MAX_VALUE (index_type);
1872
1873   return (integer_zerop (min)
1874           ? max
1875           : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
1876 }
1877 \f
1878 /* If arg is static -- a reference to an object in static storage -- then
1879    return the object.  This is not the same as the C meaning of `static'.
1880    If arg isn't static, return NULL.  */
1881
1882 tree
1883 staticp (tree arg)
1884 {
1885   switch (TREE_CODE (arg))
1886     {
1887     case FUNCTION_DECL:
1888       /* Nested functions are static, even though taking their address will
1889          involve a trampoline as we unnest the nested function and create
1890          the trampoline on the tree level.  */
1891       return arg;
1892
1893     case VAR_DECL:
1894       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1895               && ! DECL_THREAD_LOCAL_P (arg)
1896               && ! DECL_DLLIMPORT_P (arg)
1897               ? arg : NULL);
1898
1899     case CONST_DECL:
1900       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1901               ? arg : NULL);
1902
1903     case CONSTRUCTOR:
1904       return TREE_STATIC (arg) ? arg : NULL;
1905
1906     case LABEL_DECL:
1907     case STRING_CST:
1908       return arg;
1909
1910     case COMPONENT_REF:
1911       /* If the thing being referenced is not a field, then it is
1912          something language specific.  */
1913       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1914         return (*lang_hooks.staticp) (arg);
1915
1916       /* If we are referencing a bitfield, we can't evaluate an
1917          ADDR_EXPR at compile time and so it isn't a constant.  */
1918       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1919         return NULL;
1920
1921       return staticp (TREE_OPERAND (arg, 0));
1922
1923     case BIT_FIELD_REF:
1924       return NULL;
1925
1926     case MISALIGNED_INDIRECT_REF:
1927     case ALIGN_INDIRECT_REF:
1928     case INDIRECT_REF:
1929       return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
1930
1931     case ARRAY_REF:
1932     case ARRAY_RANGE_REF:
1933       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1934           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1935         return staticp (TREE_OPERAND (arg, 0));
1936       else
1937         return false;
1938
1939     default:
1940       if ((unsigned int) TREE_CODE (arg)
1941           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1942         return lang_hooks.staticp (arg);
1943       else
1944         return NULL;
1945     }
1946 }
1947 \f
1948 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1949    Do this to any expression which may be used in more than one place,
1950    but must be evaluated only once.
1951
1952    Normally, expand_expr would reevaluate the expression each time.
1953    Calling save_expr produces something that is evaluated and recorded
1954    the first time expand_expr is called on it.  Subsequent calls to
1955    expand_expr just reuse the recorded value.
1956
1957    The call to expand_expr that generates code that actually computes
1958    the value is the first call *at compile time*.  Subsequent calls
1959    *at compile time* generate code to use the saved value.
1960    This produces correct result provided that *at run time* control
1961    always flows through the insns made by the first expand_expr
1962    before reaching the other places where the save_expr was evaluated.
1963    You, the caller of save_expr, must make sure this is so.
1964
1965    Constants, and certain read-only nodes, are returned with no
1966    SAVE_EXPR because that is safe.  Expressions containing placeholders
1967    are not touched; see tree.def for an explanation of what these
1968    are used for.  */
1969
1970 tree
1971 save_expr (tree expr)
1972 {
1973   tree t = fold (expr);
1974   tree inner;
1975
1976   /* If the tree evaluates to a constant, then we don't want to hide that
1977      fact (i.e. this allows further folding, and direct checks for constants).
1978      However, a read-only object that has side effects cannot be bypassed.
1979      Since it is no problem to reevaluate literals, we just return the
1980      literal node.  */
1981   inner = skip_simple_arithmetic (t);
1982
1983   if (TREE_INVARIANT (inner)
1984       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1985       || TREE_CODE (inner) == SAVE_EXPR
1986       || TREE_CODE (inner) == ERROR_MARK)
1987     return t;
1988
1989   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1990      it means that the size or offset of some field of an object depends on
1991      the value within another field.
1992
1993      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1994      and some variable since it would then need to be both evaluated once and
1995      evaluated more than once.  Front-ends must assure this case cannot
1996      happen by surrounding any such subexpressions in their own SAVE_EXPR
1997      and forcing evaluation at the proper time.  */
1998   if (contains_placeholder_p (inner))
1999     return t;
2000
2001   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
2002
2003   /* This expression might be placed ahead of a jump to ensure that the
2004      value was computed on both sides of the jump.  So make sure it isn't
2005      eliminated as dead.  */
2006   TREE_SIDE_EFFECTS (t) = 1;
2007   TREE_INVARIANT (t) = 1;
2008   return t;
2009 }
2010
2011 /* Look inside EXPR and into any simple arithmetic operations.  Return
2012    the innermost non-arithmetic node.  */
2013
2014 tree
2015 skip_simple_arithmetic (tree expr)
2016 {
2017   tree inner;
2018
2019   /* We don't care about whether this can be used as an lvalue in this
2020      context.  */
2021   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
2022     expr = TREE_OPERAND (expr, 0);
2023
2024   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
2025      a constant, it will be more efficient to not make another SAVE_EXPR since
2026      it will allow better simplification and GCSE will be able to merge the
2027      computations if they actually occur.  */
2028   inner = expr;
2029   while (1)
2030     {
2031       if (UNARY_CLASS_P (inner))
2032         inner = TREE_OPERAND (inner, 0);
2033       else if (BINARY_CLASS_P (inner))
2034         {
2035           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
2036             inner = TREE_OPERAND (inner, 0);
2037           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
2038             inner = TREE_OPERAND (inner, 1);
2039           else
2040             break;
2041         }
2042       else
2043         break;
2044     }
2045
2046   return inner;
2047 }
2048
2049 /* Return which tree structure is used by T.  */
2050
2051 enum tree_node_structure_enum
2052 tree_node_structure (tree t)
2053 {
2054   enum tree_code code = TREE_CODE (t);
2055
2056   switch (TREE_CODE_CLASS (code))
2057     {
2058     case tcc_declaration:
2059       {
2060         switch (code)
2061           {
2062           case FIELD_DECL:
2063             return TS_FIELD_DECL;
2064           case PARM_DECL:
2065             return TS_PARM_DECL;
2066           case VAR_DECL:
2067             return TS_VAR_DECL;
2068           case LABEL_DECL:
2069             return TS_LABEL_DECL;
2070           case RESULT_DECL:
2071             return TS_RESULT_DECL;
2072           case CONST_DECL:
2073             return TS_CONST_DECL;
2074           case TYPE_DECL:
2075             return TS_TYPE_DECL;
2076           case FUNCTION_DECL:
2077             return TS_FUNCTION_DECL;
2078           case SYMBOL_MEMORY_TAG:
2079           case NAME_MEMORY_TAG:
2080           case STRUCT_FIELD_TAG:
2081             return TS_MEMORY_TAG;
2082           default:
2083             return TS_DECL_NON_COMMON;
2084           }
2085       }
2086     case tcc_type:
2087       return TS_TYPE;
2088     case tcc_reference:
2089     case tcc_comparison:
2090     case tcc_unary:
2091     case tcc_binary:
2092     case tcc_expression:
2093     case tcc_statement:
2094       return TS_EXP;
2095     default:  /* tcc_constant and tcc_exceptional */
2096       break;
2097     }
2098   switch (code)
2099     {
2100       /* tcc_constant cases.  */
2101     case INTEGER_CST:           return TS_INT_CST;
2102     case REAL_CST:              return TS_REAL_CST;
2103     case COMPLEX_CST:           return TS_COMPLEX;
2104     case VECTOR_CST:            return TS_VECTOR;
2105     case STRING_CST:            return TS_STRING;
2106       /* tcc_exceptional cases.  */
2107     case ERROR_MARK:            return TS_COMMON;
2108     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
2109     case TREE_LIST:             return TS_LIST;
2110     case TREE_VEC:              return TS_VEC;
2111     case PHI_NODE:              return TS_PHI_NODE;
2112     case SSA_NAME:              return TS_SSA_NAME;
2113     case PLACEHOLDER_EXPR:      return TS_COMMON;
2114     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
2115     case BLOCK:                 return TS_BLOCK;
2116     case CONSTRUCTOR:           return TS_CONSTRUCTOR;
2117     case TREE_BINFO:            return TS_BINFO;
2118     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
2119     case OMP_CLAUSE:            return TS_OMP_CLAUSE;
2120
2121     default:
2122       gcc_unreachable ();
2123     }
2124 }
2125 \f
2126 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
2127    or offset that depends on a field within a record.  */
2128
2129 bool
2130 contains_placeholder_p (tree exp)
2131 {
2132   enum tree_code code;
2133
2134   if (!exp)
2135     return 0;
2136
2137   code = TREE_CODE (exp);
2138   if (code == PLACEHOLDER_EXPR)
2139     return 1;
2140
2141   switch (TREE_CODE_CLASS (code))
2142     {
2143     case tcc_reference:
2144       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
2145          position computations since they will be converted into a
2146          WITH_RECORD_EXPR involving the reference, which will assume
2147          here will be valid.  */
2148       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2149
2150     case tcc_exceptional:
2151       if (code == TREE_LIST)
2152         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
2153                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
2154       break;
2155
2156     case tcc_unary:
2157     case tcc_binary:
2158     case tcc_comparison:
2159     case tcc_expression:
2160       switch (code)
2161         {
2162         case COMPOUND_EXPR:
2163           /* Ignoring the first operand isn't quite right, but works best.  */
2164           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2165
2166         case COND_EXPR:
2167           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2168                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
2169                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
2170
2171         case CALL_EXPR:
2172           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2173
2174         default:
2175           break;
2176         }
2177
2178       switch (TREE_CODE_LENGTH (code))
2179         {
2180         case 1:
2181           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2182         case 2:
2183           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2184                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
2185         default:
2186           return 0;
2187         }
2188
2189     default:
2190       return 0;
2191     }
2192   return 0;
2193 }
2194
2195 /* Return true if any part of the computation of TYPE involves a
2196    PLACEHOLDER_EXPR.  This includes size, bounds, qualifiers
2197    (for QUAL_UNION_TYPE) and field positions.  */
2198
2199 static bool
2200 type_contains_placeholder_1 (tree type)
2201 {
2202   /* If the size contains a placeholder or the parent type (component type in
2203      the case of arrays) type involves a placeholder, this type does.  */
2204   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
2205       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
2206       || (TREE_TYPE (type) != 0
2207           && type_contains_placeholder_p (TREE_TYPE (type))))
2208     return true;
2209
2210   /* Now do type-specific checks.  Note that the last part of the check above
2211      greatly limits what we have to do below.  */
2212   switch (TREE_CODE (type))
2213     {
2214     case VOID_TYPE:
2215     case COMPLEX_TYPE:
2216     case ENUMERAL_TYPE:
2217     case BOOLEAN_TYPE:
2218     case POINTER_TYPE:
2219     case OFFSET_TYPE:
2220     case REFERENCE_TYPE:
2221     case METHOD_TYPE:
2222     case FUNCTION_TYPE:
2223     case VECTOR_TYPE:
2224       return false;
2225
2226     case INTEGER_TYPE:
2227     case REAL_TYPE:
2228       /* Here we just check the bounds.  */
2229       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
2230               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
2231
2232     case ARRAY_TYPE:
2233       /* We're already checked the component type (TREE_TYPE), so just check
2234          the index type.  */
2235       return type_contains_placeholder_p (TYPE_DOMAIN (type));
2236
2237     case RECORD_TYPE:
2238     case UNION_TYPE:
2239     case QUAL_UNION_TYPE:
2240       {
2241         tree field;
2242
2243         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2244           if (TREE_CODE (field) == FIELD_DECL
2245               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
2246                   || (TREE_CODE (type) == QUAL_UNION_TYPE
2247                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
2248                   || type_contains_placeholder_p (TREE_TYPE (field))))
2249             return true;
2250
2251         return false;
2252       }
2253
2254     default:
2255       gcc_unreachable ();
2256     }
2257 }
2258
2259 bool
2260 type_contains_placeholder_p (tree type)
2261 {
2262   bool result;
2263
2264   /* If the contains_placeholder_bits field has been initialized,
2265      then we know the answer.  */
2266   if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
2267     return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
2268
2269   /* Indicate that we've seen this type node, and the answer is false.
2270      This is what we want to return if we run into recursion via fields.  */
2271   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
2272
2273   /* Compute the real value.  */
2274   result = type_contains_placeholder_1 (type);
2275
2276   /* Store the real value.  */
2277   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
2278
2279   return result;
2280 }
2281 \f
2282 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
2283    return a tree with all occurrences of references to F in a
2284    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
2285    contains only arithmetic expressions or a CALL_EXPR with a
2286    PLACEHOLDER_EXPR occurring only in its arglist.  */
2287
2288 tree
2289 substitute_in_expr (tree exp, tree f, tree r)
2290 {
2291   enum tree_code code = TREE_CODE (exp);
2292   tree op0, op1, op2, op3;
2293   tree new;
2294   tree inner;
2295
2296   /* We handle TREE_LIST and COMPONENT_REF separately.  */
2297   if (code == TREE_LIST)
2298     {
2299       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
2300       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
2301       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2302         return exp;
2303
2304       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2305     }
2306   else if (code == COMPONENT_REF)
2307    {
2308      /* If this expression is getting a value from a PLACEHOLDER_EXPR
2309         and it is the right field, replace it with R.  */
2310      for (inner = TREE_OPERAND (exp, 0);
2311           REFERENCE_CLASS_P (inner);
2312           inner = TREE_OPERAND (inner, 0))
2313        ;
2314      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2315          && TREE_OPERAND (exp, 1) == f)
2316        return r;
2317
2318      /* If this expression hasn't been completed let, leave it alone.  */
2319      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
2320        return exp;
2321
2322      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2323      if (op0 == TREE_OPERAND (exp, 0))
2324        return exp;
2325
2326      new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp),
2327                         op0, TREE_OPERAND (exp, 1), NULL_TREE);
2328    }
2329   else
2330     switch (TREE_CODE_CLASS (code))
2331       {
2332       case tcc_constant:
2333       case tcc_declaration:
2334         return exp;
2335
2336       case tcc_exceptional:
2337       case tcc_unary:
2338       case tcc_binary:
2339       case tcc_comparison:
2340       case tcc_expression:
2341       case tcc_reference:
2342         switch (TREE_CODE_LENGTH (code))
2343           {
2344           case 0:
2345             return exp;
2346
2347           case 1:
2348             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2349             if (op0 == TREE_OPERAND (exp, 0))
2350               return exp;
2351
2352             new = fold_build1 (code, TREE_TYPE (exp), op0);
2353             break;
2354
2355           case 2:
2356             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2357             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2358
2359             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2360               return exp;
2361
2362             new = fold_build2 (code, TREE_TYPE (exp), op0, op1);
2363             break;
2364
2365           case 3:
2366             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2367             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2368             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2369
2370             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2371                 && op2 == TREE_OPERAND (exp, 2))
2372               return exp;
2373
2374             new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2375             break;
2376
2377           case 4:
2378             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2379             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2380             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2381             op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r);
2382
2383             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2384                 && op2 == TREE_OPERAND (exp, 2)
2385                 && op3 == TREE_OPERAND (exp, 3))
2386               return exp;
2387
2388             new = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2389             break;
2390
2391           default:
2392             gcc_unreachable ();
2393           }
2394         break;
2395
2396       default:
2397         gcc_unreachable ();
2398       }
2399
2400   TREE_READONLY (new) = TREE_READONLY (exp);
2401   return new;
2402 }
2403
2404 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2405    for it within OBJ, a tree that is an object or a chain of references.  */
2406
2407 tree
2408 substitute_placeholder_in_expr (tree exp, tree obj)
2409 {
2410   enum tree_code code = TREE_CODE (exp);
2411   tree op0, op1, op2, op3;
2412
2413   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2414      in the chain of OBJ.  */
2415   if (code == PLACEHOLDER_EXPR)
2416     {
2417       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2418       tree elt;
2419
2420       for (elt = obj; elt != 0;
2421            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2422                    || TREE_CODE (elt) == COND_EXPR)
2423                   ? TREE_OPERAND (elt, 1)
2424                   : (REFERENCE_CLASS_P (elt)
2425                      || UNARY_CLASS_P (elt)
2426                      || BINARY_CLASS_P (elt)
2427                      || EXPRESSION_CLASS_P (elt))
2428                   ? TREE_OPERAND (elt, 0) : 0))
2429         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2430           return elt;
2431
2432       for (elt = obj; elt != 0;
2433            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2434                    || TREE_CODE (elt) == COND_EXPR)
2435                   ? TREE_OPERAND (elt, 1)
2436                   : (REFERENCE_CLASS_P (elt)
2437                      || UNARY_CLASS_P (elt)
2438                      || BINARY_CLASS_P (elt)
2439                      || EXPRESSION_CLASS_P (elt))
2440                   ? TREE_OPERAND (elt, 0) : 0))
2441         if (POINTER_TYPE_P (TREE_TYPE (elt))
2442             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2443                 == need_type))
2444           return fold_build1 (INDIRECT_REF, need_type, elt);
2445
2446       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2447          survives until RTL generation, there will be an error.  */
2448       return exp;
2449     }
2450
2451   /* TREE_LIST is special because we need to look at TREE_VALUE
2452      and TREE_CHAIN, not TREE_OPERANDS.  */
2453   else if (code == TREE_LIST)
2454     {
2455       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2456       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2457       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2458         return exp;
2459
2460       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2461     }
2462   else
2463     switch (TREE_CODE_CLASS (code))
2464       {
2465       case tcc_constant:
2466       case tcc_declaration:
2467         return exp;
2468
2469       case tcc_exceptional:
2470       case tcc_unary:
2471       case tcc_binary:
2472       case tcc_comparison:
2473       case tcc_expression:
2474       case tcc_reference:
2475       case tcc_statement:
2476         switch (TREE_CODE_LENGTH (code))
2477           {
2478           case 0:
2479             return exp;
2480
2481           case 1:
2482             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2483             if (op0 == TREE_OPERAND (exp, 0))
2484               return exp;
2485             else
2486               return fold_build1 (code, TREE_TYPE (exp), op0);
2487
2488           case 2:
2489             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2490             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2491
2492             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2493               return exp;
2494             else
2495               return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2496
2497           case 3:
2498             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2499             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2500             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2501
2502             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2503                 && op2 == TREE_OPERAND (exp, 2))
2504               return exp;
2505             else
2506               return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2507
2508           case 4:
2509             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2510             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2511             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2512             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2513
2514             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2515                 && op2 == TREE_OPERAND (exp, 2)
2516                 && op3 == TREE_OPERAND (exp, 3))
2517               return exp;
2518             else
2519               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2520
2521           default:
2522             gcc_unreachable ();
2523           }
2524         break;
2525
2526       default:
2527         gcc_unreachable ();
2528       }
2529 }
2530 \f
2531 /* Stabilize a reference so that we can use it any number of times
2532    without causing its operands to be evaluated more than once.
2533    Returns the stabilized reference.  This works by means of save_expr,
2534    so see the caveats in the comments about save_expr.
2535
2536    Also allows conversion expressions whose operands are references.
2537    Any other kind of expression is returned unchanged.  */
2538
2539 tree
2540 stabilize_reference (tree ref)
2541 {
2542   tree result;
2543   enum tree_code code = TREE_CODE (ref);
2544
2545   switch (code)
2546     {
2547     case VAR_DECL:
2548     case PARM_DECL:
2549     case RESULT_DECL:
2550       /* No action is needed in this case.  */
2551       return ref;
2552
2553     case NOP_EXPR:
2554     case CONVERT_EXPR:
2555     case FLOAT_EXPR:
2556     case FIX_TRUNC_EXPR:
2557     case FIX_FLOOR_EXPR:
2558     case FIX_ROUND_EXPR:
2559     case FIX_CEIL_EXPR:
2560       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2561       break;
2562
2563     case INDIRECT_REF:
2564       result = build_nt (INDIRECT_REF,
2565                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2566       break;
2567
2568     case COMPONENT_REF:
2569       result = build_nt (COMPONENT_REF,
2570                          stabilize_reference (TREE_OPERAND (ref, 0)),
2571                          TREE_OPERAND (ref, 1), NULL_TREE);
2572       break;
2573
2574     case BIT_FIELD_REF:
2575       result = build_nt (BIT_FIELD_REF,
2576                          stabilize_reference (TREE_OPERAND (ref, 0)),
2577                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2578                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2579       break;
2580
2581     case ARRAY_REF:
2582       result = build_nt (ARRAY_REF,
2583                          stabilize_reference (TREE_OPERAND (ref, 0)),
2584                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2585                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2586       break;
2587
2588     case ARRAY_RANGE_REF:
2589       result = build_nt (ARRAY_RANGE_REF,
2590                          stabilize_reference (TREE_OPERAND (ref, 0)),
2591                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2592                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2593       break;
2594
2595     case COMPOUND_EXPR:
2596       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2597          it wouldn't be ignored.  This matters when dealing with
2598          volatiles.  */
2599       return stabilize_reference_1 (ref);
2600
2601       /* If arg isn't a kind of lvalue we recognize, make no change.
2602          Caller should recognize the error for an invalid lvalue.  */
2603     default:
2604       return ref;
2605
2606     case ERROR_MARK:
2607       return error_mark_node;
2608     }
2609
2610   TREE_TYPE (result) = TREE_TYPE (ref);
2611   TREE_READONLY (result) = TREE_READONLY (ref);
2612   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2613   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2614
2615   return result;
2616 }
2617
2618 /* Subroutine of stabilize_reference; this is called for subtrees of
2619    references.  Any expression with side-effects must be put in a SAVE_EXPR
2620    to ensure that it is only evaluated once.
2621
2622    We don't put SAVE_EXPR nodes around everything, because assigning very
2623    simple expressions to temporaries causes us to miss good opportunities
2624    for optimizations.  Among other things, the opportunity to fold in the
2625    addition of a constant into an addressing mode often gets lost, e.g.
2626    "y[i+1] += x;".  In general, we take the approach that we should not make
2627    an assignment unless we are forced into it - i.e., that any non-side effect
2628    operator should be allowed, and that cse should take care of coalescing
2629    multiple utterances of the same expression should that prove fruitful.  */
2630
2631 tree
2632 stabilize_reference_1 (tree e)
2633 {
2634   tree result;
2635   enum tree_code code = TREE_CODE (e);
2636
2637   /* We cannot ignore const expressions because it might be a reference
2638      to a const array but whose index contains side-effects.  But we can
2639      ignore things that are actual constant or that already have been
2640      handled by this function.  */
2641
2642   if (TREE_INVARIANT (e))
2643     return e;
2644
2645   switch (TREE_CODE_CLASS (code))
2646     {
2647     case tcc_exceptional:
2648     case tcc_type:
2649     case tcc_declaration:
2650     case tcc_comparison:
2651     case tcc_statement:
2652     case tcc_expression:
2653     case tcc_reference:
2654       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2655          so that it will only be evaluated once.  */
2656       /* The reference (r) and comparison (<) classes could be handled as
2657          below, but it is generally faster to only evaluate them once.  */
2658       if (TREE_SIDE_EFFECTS (e))
2659         return save_expr (e);
2660       return e;
2661
2662     case tcc_constant:
2663       /* Constants need no processing.  In fact, we should never reach
2664          here.  */
2665       return e;
2666
2667     case tcc_binary:
2668       /* Division is slow and tends to be compiled with jumps,
2669          especially the division by powers of 2 that is often
2670          found inside of an array reference.  So do it just once.  */
2671       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2672           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2673           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2674           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2675         return save_expr (e);
2676       /* Recursively stabilize each operand.  */
2677       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2678                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2679       break;
2680
2681     case tcc_unary:
2682       /* Recursively stabilize each operand.  */
2683       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2684       break;
2685
2686     default:
2687       gcc_unreachable ();
2688     }
2689
2690   TREE_TYPE (result) = TREE_TYPE (e);
2691   TREE_READONLY (result) = TREE_READONLY (e);
2692   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2693   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2694   TREE_INVARIANT (result) = 1;
2695
2696   return result;
2697 }
2698 \f
2699 /* Low-level constructors for expressions.  */
2700
2701 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2702    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2703
2704 void
2705 recompute_tree_invariant_for_addr_expr (tree t)
2706 {
2707   tree node;
2708   bool tc = true, ti = true, se = false;
2709
2710   /* We started out assuming this address is both invariant and constant, but
2711      does not have side effects.  Now go down any handled components and see if
2712      any of them involve offsets that are either non-constant or non-invariant.
2713      Also check for side-effects.
2714
2715      ??? Note that this code makes no attempt to deal with the case where
2716      taking the address of something causes a copy due to misalignment.  */
2717
2718 #define UPDATE_TITCSE(NODE)  \
2719 do { tree _node = (NODE); \
2720      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2721      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2722      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2723
2724   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2725        node = TREE_OPERAND (node, 0))
2726     {
2727       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2728          array reference (probably made temporarily by the G++ front end),
2729          so ignore all the operands.  */
2730       if ((TREE_CODE (node) == ARRAY_REF
2731            || TREE_CODE (node) == ARRAY_RANGE_REF)
2732           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2733         {
2734           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2735           if (TREE_OPERAND (node, 2))
2736             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2737           if (TREE_OPERAND (node, 3))
2738             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2739         }
2740       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2741          FIELD_DECL, apparently.  The G++ front end can put something else
2742          there, at least temporarily.  */
2743       else if (TREE_CODE (node) == COMPONENT_REF
2744                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2745         {
2746           if (TREE_OPERAND (node, 2))
2747             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2748         }
2749       else if (TREE_CODE (node) == BIT_FIELD_REF)
2750         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2751     }
2752
2753   node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2754
2755   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2756      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2757      invariant and constant if the decl is static.  It's also invariant if it's
2758      a decl in the current function.  Taking the address of a volatile variable
2759      is not volatile.  If it's a constant, the address is both invariant and
2760      constant.  Otherwise it's neither.  */
2761   if (TREE_CODE (node) == INDIRECT_REF)
2762     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2763   else if (DECL_P (node))
2764     {
2765       if (staticp (node))
2766         ;
2767       else if (decl_function_context (node) == current_function_decl
2768                /* Addresses of thread-local variables are invariant.  */
2769                || (TREE_CODE (node) == VAR_DECL
2770                    && DECL_THREAD_LOCAL_P (node)))
2771         tc = false;
2772       else
2773         ti = tc = false;
2774     }
2775   else if (CONSTANT_CLASS_P (node))
2776     ;
2777   else
2778     {
2779       ti = tc = false;
2780       se |= TREE_SIDE_EFFECTS (node);
2781     }
2782
2783   TREE_CONSTANT (t) = tc;
2784   TREE_INVARIANT (t) = ti;
2785   TREE_SIDE_EFFECTS (t) = se;
2786 #undef UPDATE_TITCSE
2787 }
2788
2789 /* Build an expression of code CODE, data type TYPE, and operands as
2790    specified.  Expressions and reference nodes can be created this way.
2791    Constants, decls, types and misc nodes cannot be.
2792
2793    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2794    enough for all extant tree codes.  */
2795
2796 tree
2797 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2798 {
2799   tree t;
2800
2801   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2802
2803   t = make_node_stat (code PASS_MEM_STAT);
2804   TREE_TYPE (t) = tt;
2805
2806   return t;
2807 }
2808
2809 tree
2810 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2811 {
2812   int length = sizeof (struct tree_exp);
2813 #ifdef GATHER_STATISTICS
2814   tree_node_kind kind;
2815 #endif
2816   tree t;
2817
2818 #ifdef GATHER_STATISTICS
2819   switch (TREE_CODE_CLASS (code))
2820     {
2821     case tcc_statement:  /* an expression with side effects */
2822       kind = s_kind;
2823       break;
2824     case tcc_reference:  /* a reference */
2825       kind = r_kind;
2826       break;
2827     default:
2828       kind = e_kind;
2829       break;
2830     }
2831
2832   tree_node_counts[(int) kind]++;
2833   tree_node_sizes[(int) kind] += length;
2834 #endif
2835
2836   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2837
2838   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2839
2840   memset (t, 0, sizeof (struct tree_common));
2841
2842   TREE_SET_CODE (t, code);
2843
2844   TREE_TYPE (t) = type;
2845 #ifdef USE_MAPPED_LOCATION
2846   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2847 #else
2848   SET_EXPR_LOCUS (t, NULL);
2849 #endif
2850   TREE_COMPLEXITY (t) = 0;
2851   TREE_OPERAND (t, 0) = node;
2852   TREE_BLOCK (t) = NULL_TREE;
2853   if (node && !TYPE_P (node))
2854     {
2855       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2856       TREE_READONLY (t) = TREE_READONLY (node);
2857     }
2858
2859   if (TREE_CODE_CLASS (code) == tcc_statement)
2860     TREE_SIDE_EFFECTS (t) = 1;
2861   else switch (code)
2862     {
2863     case VA_ARG_EXPR:
2864       /* All of these have side-effects, no matter what their
2865          operands are.  */
2866       TREE_SIDE_EFFECTS (t) = 1;
2867       TREE_READONLY (t) = 0;
2868       break;
2869
2870     case MISALIGNED_INDIRECT_REF:
2871     case ALIGN_INDIRECT_REF:
2872     case INDIRECT_REF:
2873       /* Whether a dereference is readonly has nothing to do with whether
2874          its operand is readonly.  */
2875       TREE_READONLY (t) = 0;
2876       break;
2877
2878     case ADDR_EXPR:
2879       if (node)
2880         recompute_tree_invariant_for_addr_expr (t);
2881       break;
2882
2883     default:
2884       if (TREE_CODE_CLASS (code) == tcc_unary
2885           && node && !TYPE_P (node)
2886           && TREE_CONSTANT (node))
2887         TREE_CONSTANT (t) = 1;
2888       if (TREE_CODE_CLASS (code) == tcc_unary
2889           && node && TREE_INVARIANT (node))
2890         TREE_INVARIANT (t) = 1;
2891       if (TREE_CODE_CLASS (code) == tcc_reference
2892           && node && TREE_THIS_VOLATILE (node))
2893         TREE_THIS_VOLATILE (t) = 1;
2894       break;
2895     }
2896
2897   return t;
2898 }
2899
2900 #define PROCESS_ARG(N)                  \
2901   do {                                  \
2902     TREE_OPERAND (t, N) = arg##N;       \
2903     if (arg##N &&!TYPE_P (arg##N))      \
2904       {                                 \
2905         if (TREE_SIDE_EFFECTS (arg##N)) \
2906           side_effects = 1;             \
2907         if (!TREE_READONLY (arg##N))    \
2908           read_only = 0;                \
2909         if (!TREE_CONSTANT (arg##N))    \
2910           constant = 0;                 \
2911         if (!TREE_INVARIANT (arg##N))   \
2912           invariant = 0;                \
2913       }                                 \
2914   } while (0)
2915
2916 tree
2917 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2918 {
2919   bool constant, read_only, side_effects, invariant;
2920   tree t;
2921
2922   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2923
2924   t = make_node_stat (code PASS_MEM_STAT);
2925   TREE_TYPE (t) = tt;
2926
2927   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2928      result based on those same flags for the arguments.  But if the
2929      arguments aren't really even `tree' expressions, we shouldn't be trying
2930      to do this.  */
2931
2932   /* Expressions without side effects may be constant if their
2933      arguments are as well.  */
2934   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2935               || TREE_CODE_CLASS (code) == tcc_binary);
2936   read_only = 1;
2937   side_effects = TREE_SIDE_EFFECTS (t);
2938   invariant = constant;
2939
2940   PROCESS_ARG(0);
2941   PROCESS_ARG(1);
2942
2943   TREE_READONLY (t) = read_only;
2944   TREE_CONSTANT (t) = constant;
2945   TREE_INVARIANT (t) = invariant;
2946   TREE_SIDE_EFFECTS (t) = side_effects;
2947   TREE_THIS_VOLATILE (t)
2948     = (TREE_CODE_CLASS (code) == tcc_reference
2949        && arg0 && TREE_THIS_VOLATILE (arg0));
2950
2951   return t;
2952 }
2953
2954 tree
2955 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2956              tree arg2 MEM_STAT_DECL)
2957 {
2958   bool constant, read_only, side_effects, invariant;
2959   tree t;
2960
2961   gcc_assert (TREE_CODE_LENGTH (code) == 3);
2962
2963   t = make_node_stat (code PASS_MEM_STAT);
2964   TREE_TYPE (t) = tt;
2965
2966   side_effects = TREE_SIDE_EFFECTS (t);
2967
2968   PROCESS_ARG(0);
2969   PROCESS_ARG(1);
2970   PROCESS_ARG(2);
2971
2972   if (code == CALL_EXPR && !side_effects)
2973     {
2974       tree node;
2975       int i;
2976
2977       /* Calls have side-effects, except those to const or
2978          pure functions.  */
2979       i = call_expr_flags (t);
2980       if (!(i & (ECF_CONST | ECF_PURE)))
2981         side_effects = 1;
2982
2983       /* And even those have side-effects if their arguments do.  */
2984       else for (node = arg1; node; node = TREE_CHAIN (node))
2985         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2986           {
2987             side_effects = 1;
2988             break;
2989           }
2990     }
2991
2992   TREE_SIDE_EFFECTS (t) = side_effects;
2993   TREE_THIS_VOLATILE (t)
2994     = (TREE_CODE_CLASS (code) == tcc_reference
2995        && arg0 && TREE_THIS_VOLATILE (arg0));
2996
2997   return t;
2998 }
2999
3000 tree
3001 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3002              tree arg2, tree arg3 MEM_STAT_DECL)
3003 {
3004   bool constant, read_only, side_effects, invariant;
3005   tree t;
3006
3007   gcc_assert (TREE_CODE_LENGTH (code) == 4);
3008
3009   t = make_node_stat (code PASS_MEM_STAT);
3010   TREE_TYPE (t) = tt;
3011
3012   side_effects = TREE_SIDE_EFFECTS (t);
3013
3014   PROCESS_ARG(0);
3015   PROCESS_ARG(1);
3016   PROCESS_ARG(2);
3017   PROCESS_ARG(3);
3018
3019   TREE_SIDE_EFFECTS (t) = side_effects;
3020   TREE_THIS_VOLATILE (t)
3021     = (TREE_CODE_CLASS (code) == tcc_reference
3022        && arg0 && TREE_THIS_VOLATILE (arg0));
3023
3024   return t;
3025 }
3026
3027 tree
3028 build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3029              tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
3030 {
3031   bool constant, read_only, side_effects, invariant;
3032   tree t;
3033
3034   gcc_assert (TREE_CODE_LENGTH (code) == 5);
3035
3036   t = make_node_stat (code PASS_MEM_STAT);
3037   TREE_TYPE (t) = tt;
3038
3039   side_effects = TREE_SIDE_EFFECTS (t);
3040
3041   PROCESS_ARG(0);
3042   PROCESS_ARG(1);
3043   PROCESS_ARG(2);
3044   PROCESS_ARG(3);
3045   PROCESS_ARG(4);
3046
3047   TREE_SIDE_EFFECTS (t) = side_effects;
3048   TREE_THIS_VOLATILE (t)
3049     = (TREE_CODE_CLASS (code) == tcc_reference
3050        && arg0 && TREE_THIS_VOLATILE (arg0));
3051
3052   return t;
3053 }
3054
3055 tree
3056 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3057              tree arg2, tree arg3, tree arg4, tree arg5,
3058              tree arg6 MEM_STAT_DECL)
3059 {
3060   bool constant, read_only, side_effects, invariant;
3061   tree t;
3062
3063   gcc_assert (code == TARGET_MEM_REF);
3064
3065   t = make_node_stat (code PASS_MEM_STAT);
3066   TREE_TYPE (t) = tt;
3067
3068   side_effects = TREE_SIDE_EFFECTS (t);
3069
3070   PROCESS_ARG(0);
3071   PROCESS_ARG(1);
3072   PROCESS_ARG(2);
3073   PROCESS_ARG(3);
3074   PROCESS_ARG(4);
3075   PROCESS_ARG(5);
3076   PROCESS_ARG(6);
3077
3078   TREE_SIDE_EFFECTS (t) = side_effects;
3079   TREE_THIS_VOLATILE (t) = 0;
3080
3081   return t;
3082 }
3083
3084 /* Similar except don't specify the TREE_TYPE
3085    and leave the TREE_SIDE_EFFECTS as 0.
3086    It is permissible for arguments to be null,
3087    or even garbage if their values do not matter.  */
3088
3089 tree
3090 build_nt (enum tree_code code, ...)
3091 {
3092   tree t;
3093   int length;
3094   int i;
3095   va_list p;
3096
3097   va_start (p, code);
3098
3099   t = make_node (code);
3100   length = TREE_CODE_LENGTH (code);
3101
3102   for (i = 0; i < length; i++)
3103     TREE_OPERAND (t, i) = va_arg (p, tree);
3104
3105   va_end (p);
3106   return t;
3107 }
3108 \f
3109 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
3110    We do NOT enter this node in any sort of symbol table.
3111
3112    layout_decl is used to set up the decl's storage layout.
3113    Other slots are initialized to 0 or null pointers.  */
3114
3115 tree
3116 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
3117 {
3118   tree t;
3119
3120   t = make_node_stat (code PASS_MEM_STAT);
3121
3122 /*  if (type == error_mark_node)
3123     type = integer_type_node; */
3124 /* That is not done, deliberately, so that having error_mark_node
3125    as the type can suppress useless errors in the use of this variable.  */
3126
3127   DECL_NAME (t) = name;
3128   TREE_TYPE (t) = type;
3129
3130   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3131     layout_decl (t, 0);
3132   else if (code == FUNCTION_DECL)
3133     DECL_MODE (t) = FUNCTION_MODE;
3134
3135   if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
3136     {
3137       /* Set default visibility to whatever the user supplied with
3138          visibility_specified depending on #pragma GCC visibility.  */
3139       DECL_VISIBILITY (t) = default_visibility;
3140       DECL_VISIBILITY_SPECIFIED (t) = visibility_options.inpragma;
3141     }
3142
3143   return t;
3144 }
3145
3146 /* Builds and returns function declaration with NAME and TYPE.  */
3147
3148 tree
3149 build_fn_decl (const char *name, tree type)
3150 {
3151   tree id = get_identifier (name);
3152   tree decl = build_decl (FUNCTION_DECL, id, type);
3153
3154   DECL_EXTERNAL (decl) = 1;
3155   TREE_PUBLIC (decl) = 1;
3156   DECL_ARTIFICIAL (decl) = 1;
3157   TREE_NOTHROW (decl) = 1;
3158
3159   return decl;
3160 }
3161
3162 \f
3163 /* BLOCK nodes are used to represent the structure of binding contours
3164    and declarations, once those contours have been exited and their contents
3165    compiled.  This information is used for outputting debugging info.  */
3166
3167 tree
3168 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
3169 {
3170   tree block = make_node (BLOCK);
3171
3172   BLOCK_VARS (block) = vars;
3173   BLOCK_SUBBLOCKS (block) = subblocks;
3174   BLOCK_SUPERCONTEXT (block) = supercontext;
3175   BLOCK_CHAIN (block) = chain;
3176   return block;
3177 }
3178
3179 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
3180 /* ??? gengtype doesn't handle conditionals */
3181 static GTY(()) source_locus last_annotated_node;
3182 #endif
3183
3184 #ifdef USE_MAPPED_LOCATION
3185
3186 expanded_location
3187 expand_location (source_location loc)
3188 {
3189   expanded_location xloc;
3190   if (loc == 0) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
3191   else
3192     {
3193       const struct line_map *map = linemap_lookup (&line_table, loc);
3194       xloc.file = map->to_file;
3195       xloc.line = SOURCE_LINE (map, loc);
3196       xloc.column = SOURCE_COLUMN (map, loc);
3197     };
3198   return xloc;
3199 }
3200
3201 #else
3202
3203 /* Record the exact location where an expression or an identifier were
3204    encountered.  */
3205
3206 void
3207 annotate_with_file_line (tree node, const char *file, int line)
3208 {
3209   /* Roughly one percent of the calls to this function are to annotate
3210      a node with the same information already attached to that node!
3211      Just return instead of wasting memory.  */
3212   if (EXPR_LOCUS (node)
3213       && EXPR_LINENO (node) == line
3214       && (EXPR_FILENAME (node) == file
3215           || !strcmp (EXPR_FILENAME (node), file)))
3216     {
3217       last_annotated_node = EXPR_LOCUS (node);
3218       return;
3219     }
3220
3221   /* In heavily macroized code (such as GCC itself) this single
3222      entry cache can reduce the number of allocations by more
3223      than half.  */
3224   if (last_annotated_node
3225       && last_annotated_node->line == line
3226       && (last_annotated_node->file == file
3227           || !strcmp (last_annotated_node->file, file)))
3228     {
3229       SET_EXPR_LOCUS (node, last_annotated_node);
3230       return;
3231     }
3232
3233   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
3234   EXPR_LINENO (node) = line;
3235   EXPR_FILENAME (node) = file;
3236   last_annotated_node = EXPR_LOCUS (node);
3237 }
3238
3239 void
3240 annotate_with_locus (tree node, location_t locus)
3241 {
3242   annotate_with_file_line (node, locus.file, locus.line);
3243 }
3244 #endif
3245 \f
3246 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3247    is ATTRIBUTE.  */
3248
3249 tree
3250 build_decl_attribute_variant (tree ddecl, tree attribute)
3251 {
3252   DECL_ATTRIBUTES (ddecl) = attribute;
3253   return ddecl;
3254 }
3255
3256 /* Borrowed from hashtab.c iterative_hash implementation.  */
3257 #define mix(a,b,c) \
3258 { \
3259   a -= b; a -= c; a ^= (c>>13); \
3260   b -= c; b -= a; b ^= (a<< 8); \
3261   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3262   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3263   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3264   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3265   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3266   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3267   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3268 }
3269
3270
3271 /* Produce good hash value combining VAL and VAL2.  */
3272 static inline hashval_t
3273 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3274 {
3275   /* the golden ratio; an arbitrary value.  */
3276   hashval_t a = 0x9e3779b9;
3277
3278   mix (a, val, val2);
3279   return val2;
3280 }
3281
3282 /* Produce good hash value combining PTR and VAL2.  */
3283 static inline hashval_t
3284 iterative_hash_pointer (void *ptr, hashval_t val2)
3285 {
3286   if (sizeof (ptr) == sizeof (hashval_t))
3287     return iterative_hash_hashval_t ((size_t) ptr, val2);
3288   else
3289     {
3290       hashval_t a = (hashval_t) (size_t) ptr;
3291       /* Avoid warnings about shifting of more than the width of the type on
3292          hosts that won't execute this path.  */
3293       int zero = 0;
3294       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3295       mix (a, b, val2);
3296       return val2;
3297     }
3298 }
3299
3300 /* Produce good hash value combining VAL and VAL2.  */
3301 static inline hashval_t
3302 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3303 {
3304   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3305     return iterative_hash_hashval_t (val, val2);
3306   else
3307     {
3308       hashval_t a = (hashval_t) val;
3309       /* Avoid warnings about shifting of more than the width of the type on
3310          hosts that won't execute this path.  */
3311       int zero = 0;
3312       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3313       mix (a, b, val2);
3314       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3315         {
3316           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3317           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3318           mix (a, b, val2);
3319         }
3320       return val2;
3321     }
3322 }
3323
3324 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3325    is ATTRIBUTE.
3326
3327    Record such modified types already made so we don't make duplicates.  */
3328
3329 tree
3330 build_type_attribute_variant (tree ttype, tree attribute)
3331 {
3332   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3333     {
3334       hashval_t hashcode = 0;
3335       tree ntype;
3336       enum tree_code code = TREE_CODE (ttype);
3337
3338       ntype = copy_node (ttype);
3339
3340       TYPE_POINTER_TO (ntype) = 0;
3341       TYPE_REFERENCE_TO (ntype) = 0;
3342       TYPE_ATTRIBUTES (ntype) = attribute;
3343
3344       /* Create a new main variant of TYPE.  */
3345       TYPE_MAIN_VARIANT (ntype) = ntype;
3346       TYPE_NEXT_VARIANT (ntype) = 0;
3347       set_type_quals (ntype, TYPE_UNQUALIFIED);
3348
3349       hashcode = iterative_hash_object (code, hashcode);
3350       if (TREE_TYPE (ntype))
3351         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3352                                           hashcode);
3353       hashcode = attribute_hash_list (attribute, hashcode);
3354
3355       switch (TREE_CODE (ntype))
3356         {
3357         case FUNCTION_TYPE:
3358           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3359           break;
3360         case ARRAY_TYPE:
3361           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3362                                             hashcode);
3363           break;
3364         case INTEGER_TYPE:
3365           hashcode = iterative_hash_object
3366             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3367           hashcode = iterative_hash_object
3368             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3369           break;
3370         case REAL_TYPE:
3371           {
3372             unsigned int precision = TYPE_PRECISION (ntype);
3373             hashcode = iterative_hash_object (precision, hashcode);
3374           }
3375           break;
3376         default:
3377           break;
3378         }
3379
3380       ntype = type_hash_canon (hashcode, ntype);
3381       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
3382     }
3383
3384   return ttype;
3385 }
3386
3387
3388 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3389    or zero if not.
3390
3391    We try both `text' and `__text__', ATTR may be either one.  */
3392 /* ??? It might be a reasonable simplification to require ATTR to be only
3393    `text'.  One might then also require attribute lists to be stored in
3394    their canonicalized form.  */
3395
3396 static int
3397 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3398 {
3399   int ident_len;
3400   const char *p;
3401
3402   if (TREE_CODE (ident) != IDENTIFIER_NODE)
3403     return 0;
3404
3405   p = IDENTIFIER_POINTER (ident);
3406   ident_len = IDENTIFIER_LENGTH (ident);
3407
3408   if (ident_len == attr_len
3409       && strcmp (attr, p) == 0)
3410     return 1;
3411
3412   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
3413   if (attr[0] == '_')
3414     {
3415       gcc_assert (attr[1] == '_');
3416       gcc_assert (attr[attr_len - 2] == '_');
3417       gcc_assert (attr[attr_len - 1] == '_');
3418       gcc_assert (attr[1] == '_');
3419       if (ident_len == attr_len - 4
3420           && strncmp (attr + 2, p, attr_len - 4) == 0)
3421         return 1;
3422     }
3423   else
3424     {
3425       if (ident_len == attr_len + 4
3426           && p[0] == '_' && p[1] == '_'
3427           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3428           && strncmp (attr, p + 2, attr_len) == 0)
3429         return 1;
3430     }
3431
3432   return 0;
3433 }
3434
3435 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3436    or zero if not.
3437
3438    We try both `text' and `__text__', ATTR may be either one.  */
3439
3440 int
3441 is_attribute_p (const char *attr, tree ident)
3442 {
3443   return is_attribute_with_length_p (attr, strlen (attr), ident);
3444 }
3445
3446 /* Given an attribute name and a list of attributes, return a pointer to the
3447    attribute's list element if the attribute is part of the list, or NULL_TREE
3448    if not found.  If the attribute appears more than once, this only
3449    returns the first occurrence; the TREE_CHAIN of the return value should
3450    be passed back in if further occurrences are wanted.  */
3451
3452 tree
3453 lookup_attribute (const char *attr_name, tree list)
3454 {
3455   tree l;
3456   size_t attr_len = strlen (attr_name);
3457
3458   for (l = list; l; l = TREE_CHAIN (l))
3459     {
3460       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3461       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3462         return l;
3463     }
3464
3465   return NULL_TREE;
3466 }
3467
3468 /* Return an attribute list that is the union of a1 and a2.  */
3469
3470 tree
3471 merge_attributes (tree a1, tree a2)
3472 {
3473   tree attributes;
3474
3475   /* Either one unset?  Take the set one.  */
3476
3477   if ((attributes = a1) == 0)
3478     attributes = a2;
3479
3480   /* One that completely contains the other?  Take it.  */
3481
3482   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3483     {
3484       if (attribute_list_contained (a2, a1))
3485         attributes = a2;
3486       else
3487         {
3488           /* Pick the longest list, and hang on the other list.  */
3489
3490           if (list_length (a1) < list_length (a2))
3491             attributes = a2, a2 = a1;
3492
3493           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3494             {
3495               tree a;
3496               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3497                                          attributes);
3498                    a != NULL_TREE;
3499                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3500                                          TREE_CHAIN (a)))
3501                 {
3502                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
3503                     break;
3504                 }
3505               if (a == NULL_TREE)
3506                 {
3507                   a1 = copy_node (a2);
3508                   TREE_CHAIN (a1) = attributes;
3509                   attributes = a1;
3510                 }
3511             }
3512         }
3513     }
3514   return attributes;
3515 }
3516
3517 /* Given types T1 and T2, merge their attributes and return
3518   the result.  */
3519
3520 tree
3521 merge_type_attributes (tree t1, tree t2)
3522 {
3523   return merge_attributes (TYPE_ATTRIBUTES (t1),
3524                            TYPE_ATTRIBUTES (t2));
3525 }
3526
3527 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3528    the result.  */
3529
3530 tree
3531 merge_decl_attributes (tree olddecl, tree newdecl)
3532 {
3533   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3534                            DECL_ATTRIBUTES (newdecl));
3535 }
3536
3537 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3538
3539 /* Specialization of merge_decl_attributes for various Windows targets.
3540
3541    This handles the following situation:
3542
3543      __declspec (dllimport) int foo;
3544      int foo;
3545
3546    The second instance of `foo' nullifies the dllimport.  */
3547
3548 tree
3549 merge_dllimport_decl_attributes (tree old, tree new)
3550 {
3551   tree a;
3552   int delete_dllimport_p = 1;
3553
3554   /* What we need to do here is remove from `old' dllimport if it doesn't
3555      appear in `new'.  dllimport behaves like extern: if a declaration is
3556      marked dllimport and a definition appears later, then the object
3557      is not dllimport'd.  We also remove a `new' dllimport if the old list
3558      contains dllexport:  dllexport always overrides dllimport, regardless
3559      of the order of declaration.  */
3560   if (!VAR_OR_FUNCTION_DECL_P (new))
3561     delete_dllimport_p = 0;
3562   else if (DECL_DLLIMPORT_P (new)
3563            && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old)))
3564     {
3565       DECL_DLLIMPORT_P (new) = 0;
3566       warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: "
3567               "dllimport ignored", new);
3568     }
3569   else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new))
3570     {
3571       /* Warn about overriding a symbol that has already been used. eg:
3572            extern int __attribute__ ((dllimport)) foo;
3573            int* bar () {return &foo;}
3574            int foo;
3575       */
3576       if (TREE_USED (old))
3577         {
3578           warning (0, "%q+D redeclared without dllimport attribute "
3579                    "after being referenced with dll linkage", new);
3580           /* If we have used a variable's address with dllimport linkage,
3581               keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the
3582               decl may already have had TREE_INVARIANT and TREE_CONSTANT
3583               computed.
3584               We still remove the attribute so that assembler code refers
3585               to '&foo rather than '_imp__foo'.  */
3586           if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old))
3587             DECL_DLLIMPORT_P (new) = 1;
3588         }
3589
3590       /* Let an inline definition silently override the external reference,
3591          but otherwise warn about attribute inconsistency.  */
3592       else if (TREE_CODE (new) == VAR_DECL
3593                || !DECL_DECLARED_INLINE_P (new))
3594         warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: "
3595                   "previous dllimport ignored", new);
3596     }
3597   else
3598     delete_dllimport_p = 0;
3599
3600   a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new));
3601
3602   if (delete_dllimport_p)
3603     {
3604       tree prev, t;
3605       const size_t attr_len = strlen ("dllimport");
3606
3607       /* Scan the list for dllimport and delete it.  */
3608       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3609         {
3610           if (is_attribute_with_length_p ("dllimport", attr_len,
3611                                           TREE_PURPOSE (t)))
3612             {
3613               if (prev == NULL_TREE)
3614                 a = TREE_CHAIN (a);
3615               else
3616                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3617               break;
3618             }
3619         }
3620     }
3621
3622   return a;
3623 }
3624
3625 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3626    struct attribute_spec.handler.  */
3627
3628 tree
3629 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3630                       bool *no_add_attrs)
3631 {
3632   tree node = *pnode;
3633
3634   /* These attributes may apply to structure and union types being created,
3635      but otherwise should pass to the declaration involved.  */
3636   if (!DECL_P (node))
3637     {
3638       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3639                    | (int) ATTR_FLAG_ARRAY_NEXT))
3640         {
3641           *no_add_attrs = true;
3642           return tree_cons (name, args, NULL_TREE);
3643         }
3644       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3645         {
3646           warning (OPT_Wattributes, "%qs attribute ignored",
3647                    IDENTIFIER_POINTER (name));
3648           *no_add_attrs = true;
3649         }
3650
3651       return NULL_TREE;
3652     }
3653
3654   /* Report error on dllimport ambiguities seen now before they cause
3655      any damage.  */
3656   if (is_attribute_p ("dllimport", name))
3657     {
3658       /* Honor any target-specific overrides. */
3659       if (!targetm.valid_dllimport_attribute_p (node))
3660         *no_add_attrs = true;
3661
3662      else if (TREE_CODE (node) == FUNCTION_DECL
3663                 && DECL_DECLARED_INLINE_P (node))
3664         {
3665           warning (OPT_Wattributes, "inline function %q+D declared as "
3666                   " dllimport: attribute ignored", node);
3667           *no_add_attrs = true;
3668         }
3669       /* Like MS, treat definition of dllimported variables and
3670          non-inlined functions on declaration as syntax errors. */
3671      else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node))
3672         {
3673           error ("function %q+D definition is marked dllimport", node);
3674           *no_add_attrs = true;
3675         }
3676
3677      else if (TREE_CODE (node) == VAR_DECL)
3678         {
3679           if (DECL_INITIAL (node))
3680             {
3681               error ("variable %q+D definition is marked dllimport",
3682                      node);
3683               *no_add_attrs = true;
3684             }
3685
3686           /* `extern' needn't be specified with dllimport.
3687              Specify `extern' now and hope for the best.  Sigh.  */
3688           DECL_EXTERNAL (node) = 1;
3689           /* Also, implicitly give dllimport'd variables declared within
3690              a function global scope, unless declared static.  */
3691           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3692             TREE_PUBLIC (node) = 1;
3693         }
3694
3695       if (*no_add_attrs == false)
3696         DECL_DLLIMPORT_P (node) = 1;
3697     }
3698
3699   /*  Report error if symbol is not accessible at global scope.  */
3700   if (!TREE_PUBLIC (node)
3701       && (TREE_CODE (node) == VAR_DECL
3702           || TREE_CODE (node) == FUNCTION_DECL))
3703     {
3704       error ("external linkage required for symbol %q+D because of "
3705              "%qs attribute", node, IDENTIFIER_POINTER (name));
3706       *no_add_attrs = true;
3707     }
3708
3709   return NULL_TREE;
3710 }
3711
3712 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3713 \f
3714 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3715    of the various TYPE_QUAL values.  */
3716
3717 static void
3718 set_type_quals (tree type, int type_quals)
3719 {
3720   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3721   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3722   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3723 }
3724
3725 /* Returns true iff cand is equivalent to base with type_quals.  */
3726
3727 bool
3728 check_qualified_type (tree cand, tree base, int type_quals)
3729 {
3730   return (TYPE_QUALS (cand) == type_quals
3731           && TYPE_NAME (cand) == TYPE_NAME (base)
3732           /* Apparently this is needed for Objective-C.  */
3733           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3734           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3735                                    TYPE_ATTRIBUTES (base)));
3736 }
3737
3738 /* Return a version of the TYPE, qualified as indicated by the
3739    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3740    return NULL_TREE.  */
3741
3742 tree
3743 get_qualified_type (tree type, int type_quals)
3744 {
3745   tree t;
3746
3747   if (TYPE_QUALS (type) == type_quals)
3748     return type;
3749
3750   /* Search the chain of variants to see if there is already one there just
3751      like