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   /* Do not waste bytes provided by padding of struct tree_string.  */
1125   length = len + offsetof (struct tree_string, str) + 1;
1126
1127 #ifdef GATHER_STATISTICS
1128   tree_node_counts[(int) c_kind]++;
1129   tree_node_sizes[(int) c_kind] += length;
1130 #endif
1131
1132   s = ggc_alloc_tree (length);
1133
1134   memset (s, 0, sizeof (struct tree_common));
1135   TREE_SET_CODE (s, STRING_CST);
1136   TREE_CONSTANT (s) = 1;
1137   TREE_INVARIANT (s) = 1;
1138   TREE_STRING_LENGTH (s) = len;
1139   memcpy ((char *) TREE_STRING_POINTER (s), str, len);
1140   ((char *) TREE_STRING_POINTER (s))[len] = '\0';
1141
1142   return s;
1143 }
1144
1145 /* Return a newly constructed COMPLEX_CST node whose value is
1146    specified by the real and imaginary parts REAL and IMAG.
1147    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
1148    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
1149
1150 tree
1151 build_complex (tree type, tree real, tree imag)
1152 {
1153   tree t = make_node (COMPLEX_CST);
1154
1155   TREE_REALPART (t) = real;
1156   TREE_IMAGPART (t) = imag;
1157   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
1158   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
1159   TREE_CONSTANT_OVERFLOW (t)
1160     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
1161   return t;
1162 }
1163
1164 /* Build a BINFO with LEN language slots.  */
1165
1166 tree
1167 make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
1168 {
1169   tree t;
1170   size_t length = (offsetof (struct tree_binfo, base_binfos)
1171                    + VEC_embedded_size (tree, base_binfos));
1172
1173 #ifdef GATHER_STATISTICS
1174   tree_node_counts[(int) binfo_kind]++;
1175   tree_node_sizes[(int) binfo_kind] += length;
1176 #endif
1177
1178   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1179
1180   memset (t, 0, offsetof (struct tree_binfo, base_binfos));
1181
1182   TREE_SET_CODE (t, TREE_BINFO);
1183
1184   VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos);
1185
1186   return t;
1187 }
1188
1189
1190 /* Build a newly constructed TREE_VEC node of length LEN.  */
1191
1192 tree
1193 make_tree_vec_stat (int len MEM_STAT_DECL)
1194 {
1195   tree t;
1196   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
1197
1198 #ifdef GATHER_STATISTICS
1199   tree_node_counts[(int) vec_kind]++;
1200   tree_node_sizes[(int) vec_kind] += length;
1201 #endif
1202
1203   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1204
1205   memset (t, 0, length);
1206
1207   TREE_SET_CODE (t, TREE_VEC);
1208   TREE_VEC_LENGTH (t) = len;
1209
1210   return t;
1211 }
1212 \f
1213 /* Return 1 if EXPR is the integer constant zero or a complex constant
1214    of zero.  */
1215
1216 int
1217 integer_zerop (tree expr)
1218 {
1219   STRIP_NOPS (expr);
1220
1221   return ((TREE_CODE (expr) == INTEGER_CST
1222            && TREE_INT_CST_LOW (expr) == 0
1223            && TREE_INT_CST_HIGH (expr) == 0)
1224           || (TREE_CODE (expr) == COMPLEX_CST
1225               && integer_zerop (TREE_REALPART (expr))
1226               && integer_zerop (TREE_IMAGPART (expr))));
1227 }
1228
1229 /* Return 1 if EXPR is the integer constant one or the corresponding
1230    complex constant.  */
1231
1232 int
1233 integer_onep (tree expr)
1234 {
1235   STRIP_NOPS (expr);
1236
1237   return ((TREE_CODE (expr) == INTEGER_CST
1238            && TREE_INT_CST_LOW (expr) == 1
1239            && TREE_INT_CST_HIGH (expr) == 0)
1240           || (TREE_CODE (expr) == COMPLEX_CST
1241               && integer_onep (TREE_REALPART (expr))
1242               && integer_zerop (TREE_IMAGPART (expr))));
1243 }
1244
1245 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
1246    it contains.  Likewise for the corresponding complex constant.  */
1247
1248 int
1249 integer_all_onesp (tree expr)
1250 {
1251   int prec;
1252   int uns;
1253
1254   STRIP_NOPS (expr);
1255
1256   if (TREE_CODE (expr) == COMPLEX_CST
1257       && integer_all_onesp (TREE_REALPART (expr))
1258       && integer_zerop (TREE_IMAGPART (expr)))
1259     return 1;
1260
1261   else if (TREE_CODE (expr) != INTEGER_CST)
1262     return 0;
1263
1264   uns = TYPE_UNSIGNED (TREE_TYPE (expr));
1265   if (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1266       && TREE_INT_CST_HIGH (expr) == -1)
1267     return 1;
1268   if (!uns)
1269     return 0;
1270
1271   /* Note that using TYPE_PRECISION here is wrong.  We care about the
1272      actual bits, not the (arbitrary) range of the type.  */
1273   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
1274   if (prec >= HOST_BITS_PER_WIDE_INT)
1275     {
1276       HOST_WIDE_INT high_value;
1277       int shift_amount;
1278
1279       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
1280
1281       /* Can not handle precisions greater than twice the host int size.  */
1282       gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT);
1283       if (shift_amount == HOST_BITS_PER_WIDE_INT)
1284         /* Shifting by the host word size is undefined according to the ANSI
1285            standard, so we must handle this as a special case.  */
1286         high_value = -1;
1287       else
1288         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
1289
1290       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1291               && TREE_INT_CST_HIGH (expr) == high_value);
1292     }
1293   else
1294     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
1295 }
1296
1297 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
1298    one bit on).  */
1299
1300 int
1301 integer_pow2p (tree expr)
1302 {
1303   int prec;
1304   HOST_WIDE_INT high, low;
1305
1306   STRIP_NOPS (expr);
1307
1308   if (TREE_CODE (expr) == COMPLEX_CST
1309       && integer_pow2p (TREE_REALPART (expr))
1310       && integer_zerop (TREE_IMAGPART (expr)))
1311     return 1;
1312
1313   if (TREE_CODE (expr) != INTEGER_CST)
1314     return 0;
1315
1316   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1317           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1318   high = TREE_INT_CST_HIGH (expr);
1319   low = TREE_INT_CST_LOW (expr);
1320
1321   /* First clear all bits that are beyond the type's precision in case
1322      we've been sign extended.  */
1323
1324   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1325     ;
1326   else if (prec > HOST_BITS_PER_WIDE_INT)
1327     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1328   else
1329     {
1330       high = 0;
1331       if (prec < HOST_BITS_PER_WIDE_INT)
1332         low &= ~((HOST_WIDE_INT) (-1) << prec);
1333     }
1334
1335   if (high == 0 && low == 0)
1336     return 0;
1337
1338   return ((high == 0 && (low & (low - 1)) == 0)
1339           || (low == 0 && (high & (high - 1)) == 0));
1340 }
1341
1342 /* Return 1 if EXPR is an integer constant other than zero or a
1343    complex constant other than zero.  */
1344
1345 int
1346 integer_nonzerop (tree expr)
1347 {
1348   STRIP_NOPS (expr);
1349
1350   return ((TREE_CODE (expr) == INTEGER_CST
1351            && (TREE_INT_CST_LOW (expr) != 0
1352                || TREE_INT_CST_HIGH (expr) != 0))
1353           || (TREE_CODE (expr) == COMPLEX_CST
1354               && (integer_nonzerop (TREE_REALPART (expr))
1355                   || integer_nonzerop (TREE_IMAGPART (expr)))));
1356 }
1357
1358 /* Return the power of two represented by a tree node known to be a
1359    power of two.  */
1360
1361 int
1362 tree_log2 (tree expr)
1363 {
1364   int prec;
1365   HOST_WIDE_INT high, low;
1366
1367   STRIP_NOPS (expr);
1368
1369   if (TREE_CODE (expr) == COMPLEX_CST)
1370     return tree_log2 (TREE_REALPART (expr));
1371
1372   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1373           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1374
1375   high = TREE_INT_CST_HIGH (expr);
1376   low = TREE_INT_CST_LOW (expr);
1377
1378   /* First clear all bits that are beyond the type's precision in case
1379      we've been sign extended.  */
1380
1381   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1382     ;
1383   else if (prec > HOST_BITS_PER_WIDE_INT)
1384     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1385   else
1386     {
1387       high = 0;
1388       if (prec < HOST_BITS_PER_WIDE_INT)
1389         low &= ~((HOST_WIDE_INT) (-1) << prec);
1390     }
1391
1392   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
1393           : exact_log2 (low));
1394 }
1395
1396 /* Similar, but return the largest integer Y such that 2 ** Y is less
1397    than or equal to EXPR.  */
1398
1399 int
1400 tree_floor_log2 (tree expr)
1401 {
1402   int prec;
1403   HOST_WIDE_INT high, low;
1404
1405   STRIP_NOPS (expr);
1406
1407   if (TREE_CODE (expr) == COMPLEX_CST)
1408     return tree_log2 (TREE_REALPART (expr));
1409
1410   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1411           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1412
1413   high = TREE_INT_CST_HIGH (expr);
1414   low = TREE_INT_CST_LOW (expr);
1415
1416   /* First clear all bits that are beyond the type's precision in case
1417      we've been sign extended.  Ignore if type's precision hasn't been set
1418      since what we are doing is setting it.  */
1419
1420   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
1421     ;
1422   else if (prec > HOST_BITS_PER_WIDE_INT)
1423     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1424   else
1425     {
1426       high = 0;
1427       if (prec < HOST_BITS_PER_WIDE_INT)
1428         low &= ~((HOST_WIDE_INT) (-1) << prec);
1429     }
1430
1431   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
1432           : floor_log2 (low));
1433 }
1434
1435 /* Return 1 if EXPR is the real constant zero.  */
1436
1437 int
1438 real_zerop (tree expr)
1439 {
1440   STRIP_NOPS (expr);
1441
1442   return ((TREE_CODE (expr) == REAL_CST
1443            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
1444           || (TREE_CODE (expr) == COMPLEX_CST
1445               && real_zerop (TREE_REALPART (expr))
1446               && real_zerop (TREE_IMAGPART (expr))));
1447 }
1448
1449 /* Return 1 if EXPR is the real constant one in real or complex form.  */
1450
1451 int
1452 real_onep (tree expr)
1453 {
1454   STRIP_NOPS (expr);
1455
1456   return ((TREE_CODE (expr) == REAL_CST
1457            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1458           || (TREE_CODE (expr) == COMPLEX_CST
1459               && real_onep (TREE_REALPART (expr))
1460               && real_zerop (TREE_IMAGPART (expr))));
1461 }
1462
1463 /* Return 1 if EXPR is the real constant two.  */
1464
1465 int
1466 real_twop (tree expr)
1467 {
1468   STRIP_NOPS (expr);
1469
1470   return ((TREE_CODE (expr) == REAL_CST
1471            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1472           || (TREE_CODE (expr) == COMPLEX_CST
1473               && real_twop (TREE_REALPART (expr))
1474               && real_zerop (TREE_IMAGPART (expr))));
1475 }
1476
1477 /* Return 1 if EXPR is the real constant minus one.  */
1478
1479 int
1480 real_minus_onep (tree expr)
1481 {
1482   STRIP_NOPS (expr);
1483
1484   return ((TREE_CODE (expr) == REAL_CST
1485            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
1486           || (TREE_CODE (expr) == COMPLEX_CST
1487               && real_minus_onep (TREE_REALPART (expr))
1488               && real_zerop (TREE_IMAGPART (expr))));
1489 }
1490
1491 /* Nonzero if EXP is a constant or a cast of a constant.  */
1492
1493 int
1494 really_constant_p (tree exp)
1495 {
1496   /* This is not quite the same as STRIP_NOPS.  It does more.  */
1497   while (TREE_CODE (exp) == NOP_EXPR
1498          || TREE_CODE (exp) == CONVERT_EXPR
1499          || TREE_CODE (exp) == NON_LVALUE_EXPR)
1500     exp = TREE_OPERAND (exp, 0);
1501   return TREE_CONSTANT (exp);
1502 }
1503 \f
1504 /* Return first list element whose TREE_VALUE is ELEM.
1505    Return 0 if ELEM is not in LIST.  */
1506
1507 tree
1508 value_member (tree elem, tree list)
1509 {
1510   while (list)
1511     {
1512       if (elem == TREE_VALUE (list))
1513         return list;
1514       list = TREE_CHAIN (list);
1515     }
1516   return NULL_TREE;
1517 }
1518
1519 /* Return first list element whose TREE_PURPOSE is ELEM.
1520    Return 0 if ELEM is not in LIST.  */
1521
1522 tree
1523 purpose_member (tree elem, tree list)
1524 {
1525   while (list)
1526     {
1527       if (elem == TREE_PURPOSE (list))
1528         return list;
1529       list = TREE_CHAIN (list);
1530     }
1531   return NULL_TREE;
1532 }
1533
1534 /* Return nonzero if ELEM is part of the chain CHAIN.  */
1535
1536 int
1537 chain_member (tree elem, tree chain)
1538 {
1539   while (chain)
1540     {
1541       if (elem == chain)
1542         return 1;
1543       chain = TREE_CHAIN (chain);
1544     }
1545
1546   return 0;
1547 }
1548
1549 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1550    We expect a null pointer to mark the end of the chain.
1551    This is the Lisp primitive `length'.  */
1552
1553 int
1554 list_length (tree t)
1555 {
1556   tree p = t;
1557 #ifdef ENABLE_TREE_CHECKING
1558   tree q = t;
1559 #endif
1560   int len = 0;
1561
1562   while (p)
1563     {
1564       p = TREE_CHAIN (p);
1565 #ifdef ENABLE_TREE_CHECKING
1566       if (len % 2)
1567         q = TREE_CHAIN (q);
1568       gcc_assert (p != q);
1569 #endif
1570       len++;
1571     }
1572
1573   return len;
1574 }
1575
1576 /* Returns the number of FIELD_DECLs in TYPE.  */
1577
1578 int
1579 fields_length (tree type)
1580 {
1581   tree t = TYPE_FIELDS (type);
1582   int count = 0;
1583
1584   for (; t; t = TREE_CHAIN (t))
1585     if (TREE_CODE (t) == FIELD_DECL)
1586       ++count;
1587
1588   return count;
1589 }
1590
1591 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1592    by modifying the last node in chain 1 to point to chain 2.
1593    This is the Lisp primitive `nconc'.  */
1594
1595 tree
1596 chainon (tree op1, tree op2)
1597 {
1598   tree t1;
1599
1600   if (!op1)
1601     return op2;
1602   if (!op2)
1603     return op1;
1604
1605   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1606     continue;
1607   TREE_CHAIN (t1) = op2;
1608
1609 #ifdef ENABLE_TREE_CHECKING
1610   {
1611     tree t2;
1612     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1613       gcc_assert (t2 != t1);
1614   }
1615 #endif
1616
1617   return op1;
1618 }
1619
1620 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1621
1622 tree
1623 tree_last (tree chain)
1624 {
1625   tree next;
1626   if (chain)
1627     while ((next = TREE_CHAIN (chain)))
1628       chain = next;
1629   return chain;
1630 }
1631
1632 /* Reverse the order of elements in the chain T,
1633    and return the new head of the chain (old last element).  */
1634
1635 tree
1636 nreverse (tree t)
1637 {
1638   tree prev = 0, decl, next;
1639   for (decl = t; decl; decl = next)
1640     {
1641       next = TREE_CHAIN (decl);
1642       TREE_CHAIN (decl) = prev;
1643       prev = decl;
1644     }
1645   return prev;
1646 }
1647 \f
1648 /* Return a newly created TREE_LIST node whose
1649    purpose and value fields are PARM and VALUE.  */
1650
1651 tree
1652 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1653 {
1654   tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1655   TREE_PURPOSE (t) = parm;
1656   TREE_VALUE (t) = value;
1657   return t;
1658 }
1659
1660 /* Return a newly created TREE_LIST node whose
1661    purpose and value fields are PURPOSE and VALUE
1662    and whose TREE_CHAIN is CHAIN.  */
1663
1664 tree
1665 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1666 {
1667   tree node;
1668
1669   node = ggc_alloc_zone_pass_stat (sizeof (struct tree_list), &tree_zone);
1670
1671   memset (node, 0, sizeof (struct tree_common));
1672
1673 #ifdef GATHER_STATISTICS
1674   tree_node_counts[(int) x_kind]++;
1675   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1676 #endif
1677
1678   TREE_SET_CODE (node, TREE_LIST);
1679   TREE_CHAIN (node) = chain;
1680   TREE_PURPOSE (node) = purpose;
1681   TREE_VALUE (node) = value;
1682   return node;
1683 }
1684
1685 \f
1686 /* Return the size nominally occupied by an object of type TYPE
1687    when it resides in memory.  The value is measured in units of bytes,
1688    and its data type is that normally used for type sizes
1689    (which is the first type created by make_signed_type or
1690    make_unsigned_type).  */
1691
1692 tree
1693 size_in_bytes (tree type)
1694 {
1695   tree t;
1696
1697   if (type == error_mark_node)
1698     return integer_zero_node;
1699
1700   type = TYPE_MAIN_VARIANT (type);
1701   t = TYPE_SIZE_UNIT (type);
1702
1703   if (t == 0)
1704     {
1705       lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1706       return size_zero_node;
1707     }
1708
1709   if (TREE_CODE (t) == INTEGER_CST)
1710     t = force_fit_type (t, 0, false, false);
1711
1712   return t;
1713 }
1714
1715 /* Return the size of TYPE (in bytes) as a wide integer
1716    or return -1 if the size can vary or is larger than an integer.  */
1717
1718 HOST_WIDE_INT
1719 int_size_in_bytes (tree type)
1720 {
1721   tree t;
1722
1723   if (type == error_mark_node)
1724     return 0;
1725
1726   type = TYPE_MAIN_VARIANT (type);
1727   t = TYPE_SIZE_UNIT (type);
1728   if (t == 0
1729       || TREE_CODE (t) != INTEGER_CST
1730       || TREE_INT_CST_HIGH (t) != 0
1731       /* If the result would appear negative, it's too big to represent.  */
1732       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1733     return -1;
1734
1735   return TREE_INT_CST_LOW (t);
1736 }
1737
1738 /* Return the maximum size of TYPE (in bytes) as a wide integer
1739    or return -1 if the size can vary or is larger than an integer.  */
1740
1741 HOST_WIDE_INT
1742 max_int_size_in_bytes (tree type)
1743 {
1744   HOST_WIDE_INT size = -1;
1745   tree size_tree;
1746
1747   /* If this is an array type, check for a possible MAX_SIZE attached.  */
1748
1749   if (TREE_CODE (type) == ARRAY_TYPE)
1750     {
1751       size_tree = TYPE_ARRAY_MAX_SIZE (type);
1752
1753       if (size_tree && host_integerp (size_tree, 1))
1754         size = tree_low_cst (size_tree, 1);
1755     }
1756
1757   /* If we still haven't been able to get a size, see if the language
1758      can compute a maximum size.  */
1759
1760   if (size == -1)
1761     {
1762       size_tree = lang_hooks.types.max_size (type);
1763
1764       if (size_tree && host_integerp (size_tree, 1))
1765         size = tree_low_cst (size_tree, 1);
1766     }
1767
1768   return size;
1769 }
1770 \f
1771 /* Return the bit position of FIELD, in bits from the start of the record.
1772    This is a tree of type bitsizetype.  */
1773
1774 tree
1775 bit_position (tree field)
1776 {
1777   return bit_from_pos (DECL_FIELD_OFFSET (field),
1778                        DECL_FIELD_BIT_OFFSET (field));
1779 }
1780
1781 /* Likewise, but return as an integer.  It must be representable in
1782    that way (since it could be a signed value, we don't have the
1783    option of returning -1 like int_size_in_byte can.  */
1784
1785 HOST_WIDE_INT
1786 int_bit_position (tree field)
1787 {
1788   return tree_low_cst (bit_position (field), 0);
1789 }
1790 \f
1791 /* Return the byte position of FIELD, in bytes from the start of the record.
1792    This is a tree of type sizetype.  */
1793
1794 tree
1795 byte_position (tree field)
1796 {
1797   return byte_from_pos (DECL_FIELD_OFFSET (field),
1798                         DECL_FIELD_BIT_OFFSET (field));
1799 }
1800
1801 /* Likewise, but return as an integer.  It must be representable in
1802    that way (since it could be a signed value, we don't have the
1803    option of returning -1 like int_size_in_byte can.  */
1804
1805 HOST_WIDE_INT
1806 int_byte_position (tree field)
1807 {
1808   return tree_low_cst (byte_position (field), 0);
1809 }
1810 \f
1811 /* Return the strictest alignment, in bits, that T is known to have.  */
1812
1813 unsigned int
1814 expr_align (tree t)
1815 {
1816   unsigned int align0, align1;
1817
1818   switch (TREE_CODE (t))
1819     {
1820     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1821       /* If we have conversions, we know that the alignment of the
1822          object must meet each of the alignments of the types.  */
1823       align0 = expr_align (TREE_OPERAND (t, 0));
1824       align1 = TYPE_ALIGN (TREE_TYPE (t));
1825       return MAX (align0, align1);
1826
1827     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1828     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1829     case CLEANUP_POINT_EXPR:
1830       /* These don't change the alignment of an object.  */
1831       return expr_align (TREE_OPERAND (t, 0));
1832
1833     case COND_EXPR:
1834       /* The best we can do is say that the alignment is the least aligned
1835          of the two arms.  */
1836       align0 = expr_align (TREE_OPERAND (t, 1));
1837       align1 = expr_align (TREE_OPERAND (t, 2));
1838       return MIN (align0, align1);
1839
1840     case LABEL_DECL:     case CONST_DECL:
1841     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1842       if (DECL_ALIGN (t) != 0)
1843         return DECL_ALIGN (t);
1844       break;
1845
1846     case FUNCTION_DECL:
1847       return FUNCTION_BOUNDARY;
1848
1849     default:
1850       break;
1851     }
1852
1853   /* Otherwise take the alignment from that of the type.  */
1854   return TYPE_ALIGN (TREE_TYPE (t));
1855 }
1856 \f
1857 /* Return, as a tree node, the number of elements for TYPE (which is an
1858    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1859
1860 tree
1861 array_type_nelts (tree type)
1862 {
1863   tree index_type, min, max;
1864
1865   /* If they did it with unspecified bounds, then we should have already
1866      given an error about it before we got here.  */
1867   if (! TYPE_DOMAIN (type))
1868     return error_mark_node;
1869
1870   index_type = TYPE_DOMAIN (type);
1871   min = TYPE_MIN_VALUE (index_type);
1872   max = TYPE_MAX_VALUE (index_type);
1873
1874   return (integer_zerop (min)
1875           ? max
1876           : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
1877 }
1878 \f
1879 /* If arg is static -- a reference to an object in static storage -- then
1880    return the object.  This is not the same as the C meaning of `static'.
1881    If arg isn't static, return NULL.  */
1882
1883 tree
1884 staticp (tree arg)
1885 {
1886   switch (TREE_CODE (arg))
1887     {
1888     case FUNCTION_DECL:
1889       /* Nested functions are static, even though taking their address will
1890          involve a trampoline as we unnest the nested function and create
1891          the trampoline on the tree level.  */
1892       return arg;
1893
1894     case VAR_DECL:
1895       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1896               && ! DECL_THREAD_LOCAL_P (arg)
1897               && ! DECL_DLLIMPORT_P (arg)
1898               ? arg : NULL);
1899
1900     case CONST_DECL:
1901       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1902               ? arg : NULL);
1903
1904     case CONSTRUCTOR:
1905       return TREE_STATIC (arg) ? arg : NULL;
1906
1907     case LABEL_DECL:
1908     case STRING_CST:
1909       return arg;
1910
1911     case COMPONENT_REF:
1912       /* If the thing being referenced is not a field, then it is
1913          something language specific.  */
1914       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1915         return (*lang_hooks.staticp) (arg);
1916
1917       /* If we are referencing a bitfield, we can't evaluate an
1918          ADDR_EXPR at compile time and so it isn't a constant.  */
1919       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1920         return NULL;
1921
1922       return staticp (TREE_OPERAND (arg, 0));
1923
1924     case BIT_FIELD_REF:
1925       return NULL;
1926
1927     case MISALIGNED_INDIRECT_REF:
1928     case ALIGN_INDIRECT_REF:
1929     case INDIRECT_REF:
1930       return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
1931
1932     case ARRAY_REF:
1933     case ARRAY_RANGE_REF:
1934       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1935           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1936         return staticp (TREE_OPERAND (arg, 0));
1937       else
1938         return false;
1939
1940     default:
1941       if ((unsigned int) TREE_CODE (arg)
1942           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1943         return lang_hooks.staticp (arg);
1944       else
1945         return NULL;
1946     }
1947 }
1948 \f
1949 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1950    Do this to any expression which may be used in more than one place,
1951    but must be evaluated only once.
1952
1953    Normally, expand_expr would reevaluate the expression each time.
1954    Calling save_expr produces something that is evaluated and recorded
1955    the first time expand_expr is called on it.  Subsequent calls to
1956    expand_expr just reuse the recorded value.
1957
1958    The call to expand_expr that generates code that actually computes
1959    the value is the first call *at compile time*.  Subsequent calls
1960    *at compile time* generate code to use the saved value.
1961    This produces correct result provided that *at run time* control
1962    always flows through the insns made by the first expand_expr
1963    before reaching the other places where the save_expr was evaluated.
1964    You, the caller of save_expr, must make sure this is so.
1965
1966    Constants, and certain read-only nodes, are returned with no
1967    SAVE_EXPR because that is safe.  Expressions containing placeholders
1968    are not touched; see tree.def for an explanation of what these
1969    are used for.  */
1970
1971 tree
1972 save_expr (tree expr)
1973 {
1974   tree t = fold (expr);
1975   tree inner;
1976
1977   /* If the tree evaluates to a constant, then we don't want to hide that
1978      fact (i.e. this allows further folding, and direct checks for constants).
1979      However, a read-only object that has side effects cannot be bypassed.
1980      Since it is no problem to reevaluate literals, we just return the
1981      literal node.  */
1982   inner = skip_simple_arithmetic (t);
1983
1984   if (TREE_INVARIANT (inner)
1985       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1986       || TREE_CODE (inner) == SAVE_EXPR
1987       || TREE_CODE (inner) == ERROR_MARK)
1988     return t;
1989
1990   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1991      it means that the size or offset of some field of an object depends on
1992      the value within another field.
1993
1994      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1995      and some variable since it would then need to be both evaluated once and
1996      evaluated more than once.  Front-ends must assure this case cannot
1997      happen by surrounding any such subexpressions in their own SAVE_EXPR
1998      and forcing evaluation at the proper time.  */
1999   if (contains_placeholder_p (inner))
2000     return t;
2001
2002   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
2003
2004   /* This expression might be placed ahead of a jump to ensure that the
2005      value was computed on both sides of the jump.  So make sure it isn't
2006      eliminated as dead.  */
2007   TREE_SIDE_EFFECTS (t) = 1;
2008   TREE_INVARIANT (t) = 1;
2009   return t;
2010 }
2011
2012 /* Look inside EXPR and into any simple arithmetic operations.  Return
2013    the innermost non-arithmetic node.  */
2014
2015 tree
2016 skip_simple_arithmetic (tree expr)
2017 {
2018   tree inner;
2019
2020   /* We don't care about whether this can be used as an lvalue in this
2021      context.  */
2022   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
2023     expr = TREE_OPERAND (expr, 0);
2024
2025   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
2026      a constant, it will be more efficient to not make another SAVE_EXPR since
2027      it will allow better simplification and GCSE will be able to merge the
2028      computations if they actually occur.  */
2029   inner = expr;
2030   while (1)
2031     {
2032       if (UNARY_CLASS_P (inner))
2033         inner = TREE_OPERAND (inner, 0);
2034       else if (BINARY_CLASS_P (inner))
2035         {
2036           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
2037             inner = TREE_OPERAND (inner, 0);
2038           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
2039             inner = TREE_OPERAND (inner, 1);
2040           else
2041             break;
2042         }
2043       else
2044         break;
2045     }
2046
2047   return inner;
2048 }
2049
2050 /* Return which tree structure is used by T.  */
2051
2052 enum tree_node_structure_enum
2053 tree_node_structure (tree t)
2054 {
2055   enum tree_code code = TREE_CODE (t);
2056
2057   switch (TREE_CODE_CLASS (code))
2058     {
2059     case tcc_declaration:
2060       {
2061         switch (code)
2062           {
2063           case FIELD_DECL:
2064             return TS_FIELD_DECL;
2065           case PARM_DECL:
2066             return TS_PARM_DECL;
2067           case VAR_DECL:
2068             return TS_VAR_DECL;
2069           case LABEL_DECL:
2070             return TS_LABEL_DECL;
2071           case RESULT_DECL:
2072             return TS_RESULT_DECL;
2073           case CONST_DECL:
2074             return TS_CONST_DECL;
2075           case TYPE_DECL:
2076             return TS_TYPE_DECL;
2077           case FUNCTION_DECL:
2078             return TS_FUNCTION_DECL;
2079           case SYMBOL_MEMORY_TAG:
2080           case NAME_MEMORY_TAG:
2081           case STRUCT_FIELD_TAG:
2082             return TS_MEMORY_TAG;
2083           default:
2084             return TS_DECL_NON_COMMON;
2085           }
2086       }
2087     case tcc_type:
2088       return TS_TYPE;
2089     case tcc_reference:
2090     case tcc_comparison:
2091     case tcc_unary:
2092     case tcc_binary:
2093     case tcc_expression:
2094     case tcc_statement:
2095       return TS_EXP;
2096     default:  /* tcc_constant and tcc_exceptional */
2097       break;
2098     }
2099   switch (code)
2100     {
2101       /* tcc_constant cases.  */
2102     case INTEGER_CST:           return TS_INT_CST;
2103     case REAL_CST:              return TS_REAL_CST;
2104     case COMPLEX_CST:           return TS_COMPLEX;
2105     case VECTOR_CST:            return TS_VECTOR;
2106     case STRING_CST:            return TS_STRING;
2107       /* tcc_exceptional cases.  */
2108     case ERROR_MARK:            return TS_COMMON;
2109     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
2110     case TREE_LIST:             return TS_LIST;
2111     case TREE_VEC:              return TS_VEC;
2112     case PHI_NODE:              return TS_PHI_NODE;
2113     case SSA_NAME:              return TS_SSA_NAME;
2114     case PLACEHOLDER_EXPR:      return TS_COMMON;
2115     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
2116     case BLOCK:                 return TS_BLOCK;
2117     case CONSTRUCTOR:           return TS_CONSTRUCTOR;
2118     case TREE_BINFO:            return TS_BINFO;
2119     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
2120     case OMP_CLAUSE:            return TS_OMP_CLAUSE;
2121
2122     default:
2123       gcc_unreachable ();
2124     }
2125 }
2126 \f
2127 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
2128    or offset that depends on a field within a record.  */
2129
2130 bool
2131 contains_placeholder_p (tree exp)
2132 {
2133   enum tree_code code;
2134
2135   if (!exp)
2136     return 0;
2137
2138   code = TREE_CODE (exp);
2139   if (code == PLACEHOLDER_EXPR)
2140     return 1;
2141
2142   switch (TREE_CODE_CLASS (code))
2143     {
2144     case tcc_reference:
2145       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
2146          position computations since they will be converted into a
2147          WITH_RECORD_EXPR involving the reference, which will assume
2148          here will be valid.  */
2149       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2150
2151     case tcc_exceptional:
2152       if (code == TREE_LIST)
2153         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
2154                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
2155       break;
2156
2157     case tcc_unary:
2158     case tcc_binary:
2159     case tcc_comparison:
2160     case tcc_expression:
2161       switch (code)
2162         {
2163         case COMPOUND_EXPR:
2164           /* Ignoring the first operand isn't quite right, but works best.  */
2165           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2166
2167         case COND_EXPR:
2168           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2169                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
2170                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
2171
2172         case CALL_EXPR:
2173           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2174
2175         default:
2176           break;
2177         }
2178
2179       switch (TREE_CODE_LENGTH (code))
2180         {
2181         case 1:
2182           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2183         case 2:
2184           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2185                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
2186         default:
2187           return 0;
2188         }
2189
2190     default:
2191       return 0;
2192     }
2193   return 0;
2194 }
2195
2196 /* Return true if any part of the computation of TYPE involves a
2197    PLACEHOLDER_EXPR.  This includes size, bounds, qualifiers
2198    (for QUAL_UNION_TYPE) and field positions.  */
2199
2200 static bool
2201 type_contains_placeholder_1 (tree type)
2202 {
2203   /* If the size contains a placeholder or the parent type (component type in
2204      the case of arrays) type involves a placeholder, this type does.  */
2205   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
2206       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
2207       || (TREE_TYPE (type) != 0
2208           && type_contains_placeholder_p (TREE_TYPE (type))))
2209     return true;
2210
2211   /* Now do type-specific checks.  Note that the last part of the check above
2212      greatly limits what we have to do below.  */
2213   switch (TREE_CODE (type))
2214     {
2215     case VOID_TYPE:
2216     case COMPLEX_TYPE:
2217     case ENUMERAL_TYPE:
2218     case BOOLEAN_TYPE:
2219     case POINTER_TYPE:
2220     case OFFSET_TYPE:
2221     case REFERENCE_TYPE:
2222     case METHOD_TYPE:
2223     case FUNCTION_TYPE:
2224     case VECTOR_TYPE:
2225       return false;
2226
2227     case INTEGER_TYPE:
2228     case REAL_TYPE:
2229       /* Here we just check the bounds.  */
2230       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
2231               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
2232
2233     case ARRAY_TYPE:
2234       /* We're already checked the component type (TREE_TYPE), so just check
2235          the index type.  */
2236       return type_contains_placeholder_p (TYPE_DOMAIN (type));
2237
2238     case RECORD_TYPE:
2239     case UNION_TYPE:
2240     case QUAL_UNION_TYPE:
2241       {
2242         tree field;
2243
2244         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2245           if (TREE_CODE (field) == FIELD_DECL
2246               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
2247                   || (TREE_CODE (type) == QUAL_UNION_TYPE
2248                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
2249                   || type_contains_placeholder_p (TREE_TYPE (field))))
2250             return true;
2251
2252         return false;
2253       }
2254
2255     default:
2256       gcc_unreachable ();
2257     }
2258 }
2259
2260 bool
2261 type_contains_placeholder_p (tree type)
2262 {
2263   bool result;
2264
2265   /* If the contains_placeholder_bits field has been initialized,
2266      then we know the answer.  */
2267   if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
2268     return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
2269
2270   /* Indicate that we've seen this type node, and the answer is false.
2271      This is what we want to return if we run into recursion via fields.  */
2272   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
2273
2274   /* Compute the real value.  */
2275   result = type_contains_placeholder_1 (type);
2276
2277   /* Store the real value.  */
2278   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
2279
2280   return result;
2281 }
2282 \f
2283 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
2284    return a tree with all occurrences of references to F in a
2285    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
2286    contains only arithmetic expressions or a CALL_EXPR with a
2287    PLACEHOLDER_EXPR occurring only in its arglist.  */
2288
2289 tree
2290 substitute_in_expr (tree exp, tree f, tree r)
2291 {
2292   enum tree_code code = TREE_CODE (exp);
2293   tree op0, op1, op2, op3;
2294   tree new;
2295   tree inner;
2296
2297   /* We handle TREE_LIST and COMPONENT_REF separately.  */
2298   if (code == TREE_LIST)
2299     {
2300       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
2301       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
2302       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2303         return exp;
2304
2305       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2306     }
2307   else if (code == COMPONENT_REF)
2308    {
2309      /* If this expression is getting a value from a PLACEHOLDER_EXPR
2310         and it is the right field, replace it with R.  */
2311      for (inner = TREE_OPERAND (exp, 0);
2312           REFERENCE_CLASS_P (inner);
2313           inner = TREE_OPERAND (inner, 0))
2314        ;
2315      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2316          && TREE_OPERAND (exp, 1) == f)
2317        return r;
2318
2319      /* If this expression hasn't been completed let, leave it alone.  */
2320      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
2321        return exp;
2322
2323      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2324      if (op0 == TREE_OPERAND (exp, 0))
2325        return exp;
2326
2327      new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp),
2328                         op0, TREE_OPERAND (exp, 1), NULL_TREE);
2329    }
2330   else
2331     switch (TREE_CODE_CLASS (code))
2332       {
2333       case tcc_constant:
2334       case tcc_declaration:
2335         return exp;
2336
2337       case tcc_exceptional:
2338       case tcc_unary:
2339       case tcc_binary:
2340       case tcc_comparison:
2341       case tcc_expression:
2342       case tcc_reference:
2343         switch (TREE_CODE_LENGTH (code))
2344           {
2345           case 0:
2346             return exp;
2347
2348           case 1:
2349             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2350             if (op0 == TREE_OPERAND (exp, 0))
2351               return exp;
2352
2353             new = fold_build1 (code, TREE_TYPE (exp), op0);
2354             break;
2355
2356           case 2:
2357             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2358             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2359
2360             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2361               return exp;
2362
2363             new = fold_build2 (code, TREE_TYPE (exp), op0, op1);
2364             break;
2365
2366           case 3:
2367             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2368             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2369             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2370
2371             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2372                 && op2 == TREE_OPERAND (exp, 2))
2373               return exp;
2374
2375             new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2376             break;
2377
2378           case 4:
2379             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2380             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2381             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2382             op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r);
2383
2384             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2385                 && op2 == TREE_OPERAND (exp, 2)
2386                 && op3 == TREE_OPERAND (exp, 3))
2387               return exp;
2388
2389             new = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2390             break;
2391
2392           default:
2393             gcc_unreachable ();
2394           }
2395         break;
2396
2397       default:
2398         gcc_unreachable ();
2399       }
2400
2401   TREE_READONLY (new) = TREE_READONLY (exp);
2402   return new;
2403 }
2404
2405 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2406    for it within OBJ, a tree that is an object or a chain of references.  */
2407
2408 tree
2409 substitute_placeholder_in_expr (tree exp, tree obj)
2410 {
2411   enum tree_code code = TREE_CODE (exp);
2412   tree op0, op1, op2, op3;
2413
2414   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2415      in the chain of OBJ.  */
2416   if (code == PLACEHOLDER_EXPR)
2417     {
2418       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2419       tree elt;
2420
2421       for (elt = obj; elt != 0;
2422            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2423                    || TREE_CODE (elt) == COND_EXPR)
2424                   ? TREE_OPERAND (elt, 1)
2425                   : (REFERENCE_CLASS_P (elt)
2426                      || UNARY_CLASS_P (elt)
2427                      || BINARY_CLASS_P (elt)
2428                      || EXPRESSION_CLASS_P (elt))
2429                   ? TREE_OPERAND (elt, 0) : 0))
2430         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2431           return elt;
2432
2433       for (elt = obj; elt != 0;
2434            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2435                    || TREE_CODE (elt) == COND_EXPR)
2436                   ? TREE_OPERAND (elt, 1)
2437                   : (REFERENCE_CLASS_P (elt)
2438                      || UNARY_CLASS_P (elt)
2439                      || BINARY_CLASS_P (elt)
2440                      || EXPRESSION_CLASS_P (elt))
2441                   ? TREE_OPERAND (elt, 0) : 0))
2442         if (POINTER_TYPE_P (TREE_TYPE (elt))
2443             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2444                 == need_type))
2445           return fold_build1 (INDIRECT_REF, need_type, elt);
2446
2447       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2448          survives until RTL generation, there will be an error.  */
2449       return exp;
2450     }
2451
2452   /* TREE_LIST is special because we need to look at TREE_VALUE
2453      and TREE_CHAIN, not TREE_OPERANDS.  */
2454   else if (code == TREE_LIST)
2455     {
2456       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2457       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2458       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2459         return exp;
2460
2461       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2462     }
2463   else
2464     switch (TREE_CODE_CLASS (code))
2465       {
2466       case tcc_constant:
2467       case tcc_declaration:
2468         return exp;
2469
2470       case tcc_exceptional:
2471       case tcc_unary:
2472       case tcc_binary:
2473       case tcc_comparison:
2474       case tcc_expression:
2475       case tcc_reference:
2476       case tcc_statement:
2477         switch (TREE_CODE_LENGTH (code))
2478           {
2479           case 0:
2480             return exp;
2481
2482           case 1:
2483             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2484             if (op0 == TREE_OPERAND (exp, 0))
2485               return exp;
2486             else
2487               return fold_build1 (code, TREE_TYPE (exp), op0);
2488
2489           case 2:
2490             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2491             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2492
2493             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2494               return exp;
2495             else
2496               return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2497
2498           case 3:
2499             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2500             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2501             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2502
2503             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2504                 && op2 == TREE_OPERAND (exp, 2))
2505               return exp;
2506             else
2507               return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2508
2509           case 4:
2510             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2511             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2512             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2513             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2514
2515             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2516                 && op2 == TREE_OPERAND (exp, 2)
2517                 && op3 == TREE_OPERAND (exp, 3))
2518               return exp;
2519             else
2520               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2521
2522           default:
2523             gcc_unreachable ();
2524           }
2525         break;
2526
2527       default:
2528         gcc_unreachable ();
2529       }
2530 }
2531 \f
2532 /* Stabilize a reference so that we can use it any number of times
2533    without causing its operands to be evaluated more than once.
2534    Returns the stabilized reference.  This works by means of save_expr,
2535    so see the caveats in the comments about save_expr.
2536
2537    Also allows conversion expressions whose operands are references.
2538    Any other kind of expression is returned unchanged.  */
2539
2540 tree
2541 stabilize_reference (tree ref)
2542 {
2543   tree result;
2544   enum tree_code code = TREE_CODE (ref);
2545
2546   switch (code)
2547     {
2548     case VAR_DECL:
2549     case PARM_DECL:
2550     case RESULT_DECL:
2551       /* No action is needed in this case.  */
2552       return ref;
2553
2554     case NOP_EXPR:
2555     case CONVERT_EXPR:
2556     case FLOAT_EXPR:
2557     case FIX_TRUNC_EXPR:
2558     case FIX_FLOOR_EXPR:
2559     case FIX_ROUND_EXPR:
2560     case FIX_CEIL_EXPR:
2561       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2562       break;
2563
2564     case INDIRECT_REF:
2565       result = build_nt (INDIRECT_REF,
2566                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2567       break;
2568
2569     case COMPONENT_REF:
2570       result = build_nt (COMPONENT_REF,
2571                          stabilize_reference (TREE_OPERAND (ref, 0)),
2572                          TREE_OPERAND (ref, 1), NULL_TREE);
2573       break;
2574
2575     case BIT_FIELD_REF:
2576       result = build_nt (BIT_FIELD_REF,
2577                          stabilize_reference (TREE_OPERAND (ref, 0)),
2578                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2579                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2580       break;
2581
2582     case ARRAY_REF:
2583       result = build_nt (ARRAY_REF,
2584                          stabilize_reference (TREE_OPERAND (ref, 0)),
2585                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2586                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2587       break;
2588
2589     case ARRAY_RANGE_REF:
2590       result = build_nt (ARRAY_RANGE_REF,
2591                          stabilize_reference (TREE_OPERAND (ref, 0)),
2592                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2593                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2594       break;
2595
2596     case COMPOUND_EXPR:
2597       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2598          it wouldn't be ignored.  This matters when dealing with
2599          volatiles.  */
2600       return stabilize_reference_1 (ref);
2601
2602       /* If arg isn't a kind of lvalue we recognize, make no change.
2603          Caller should recognize the error for an invalid lvalue.  */
2604     default:
2605       return ref;
2606
2607     case ERROR_MARK:
2608       return error_mark_node;
2609     }
2610
2611   TREE_TYPE (result) = TREE_TYPE (ref);
2612   TREE_READONLY (result) = TREE_READONLY (ref);
2613   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2614   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2615
2616   return result;
2617 }
2618
2619 /* Subroutine of stabilize_reference; this is called for subtrees of
2620    references.  Any expression with side-effects must be put in a SAVE_EXPR
2621    to ensure that it is only evaluated once.
2622
2623    We don't put SAVE_EXPR nodes around everything, because assigning very
2624    simple expressions to temporaries causes us to miss good opportunities
2625    for optimizations.  Among other things, the opportunity to fold in the
2626    addition of a constant into an addressing mode often gets lost, e.g.
2627    "y[i+1] += x;".  In general, we take the approach that we should not make
2628    an assignment unless we are forced into it - i.e., that any non-side effect
2629    operator should be allowed, and that cse should take care of coalescing
2630    multiple utterances of the same expression should that prove fruitful.  */
2631
2632 tree
2633 stabilize_reference_1 (tree e)
2634 {
2635   tree result;
2636   enum tree_code code = TREE_CODE (e);
2637
2638   /* We cannot ignore const expressions because it might be a reference
2639      to a const array but whose index contains side-effects.  But we can
2640      ignore things that are actual constant or that already have been
2641      handled by this function.  */
2642
2643   if (TREE_INVARIANT (e))
2644     return e;
2645
2646   switch (TREE_CODE_CLASS (code))
2647     {
2648     case tcc_exceptional:
2649     case tcc_type:
2650     case tcc_declaration:
2651     case tcc_comparison:
2652     case tcc_statement:
2653     case tcc_expression:
2654     case tcc_reference:
2655       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2656          so that it will only be evaluated once.  */
2657       /* The reference (r) and comparison (<) classes could be handled as
2658          below, but it is generally faster to only evaluate them once.  */
2659       if (TREE_SIDE_EFFECTS (e))
2660         return save_expr (e);
2661       return e;
2662
2663     case tcc_constant:
2664       /* Constants need no processing.  In fact, we should never reach
2665          here.  */
2666       return e;
2667
2668     case tcc_binary:
2669       /* Division is slow and tends to be compiled with jumps,
2670          especially the division by powers of 2 that is often
2671          found inside of an array reference.  So do it just once.  */
2672       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2673           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2674           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2675           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2676         return save_expr (e);
2677       /* Recursively stabilize each operand.  */
2678       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2679                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2680       break;
2681
2682     case tcc_unary:
2683       /* Recursively stabilize each operand.  */
2684       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2685       break;
2686
2687     default:
2688       gcc_unreachable ();
2689     }
2690
2691   TREE_TYPE (result) = TREE_TYPE (e);
2692   TREE_READONLY (result) = TREE_READONLY (e);
2693   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2694   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2695   TREE_INVARIANT (result) = 1;
2696
2697   return result;
2698 }
2699 \f
2700 /* Low-level constructors for expressions.  */
2701
2702 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2703    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2704
2705 void
2706 recompute_tree_invariant_for_addr_expr (tree t)
2707 {
2708   tree node;
2709   bool tc = true, ti = true, se = false;
2710
2711   /* We started out assuming this address is both invariant and constant, but
2712      does not have side effects.  Now go down any handled components and see if
2713      any of them involve offsets that are either non-constant or non-invariant.
2714      Also check for side-effects.
2715
2716      ??? Note that this code makes no attempt to deal with the case where
2717      taking the address of something causes a copy due to misalignment.  */
2718
2719 #define UPDATE_TITCSE(NODE)  \
2720 do { tree _node = (NODE); \
2721      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2722      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2723      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2724
2725   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2726        node = TREE_OPERAND (node, 0))
2727     {
2728       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2729          array reference (probably made temporarily by the G++ front end),
2730          so ignore all the operands.  */
2731       if ((TREE_CODE (node) == ARRAY_REF
2732            || TREE_CODE (node) == ARRAY_RANGE_REF)
2733           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2734         {
2735           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2736           if (TREE_OPERAND (node, 2))
2737             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2738           if (TREE_OPERAND (node, 3))
2739             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2740         }
2741       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2742          FIELD_DECL, apparently.  The G++ front end can put something else
2743          there, at least temporarily.  */
2744       else if (TREE_CODE (node) == COMPONENT_REF
2745                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2746         {
2747           if (TREE_OPERAND (node, 2))
2748             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2749         }
2750       else if (TREE_CODE (node) == BIT_FIELD_REF)
2751         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2752     }
2753
2754   node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2755
2756   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2757      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2758      invariant and constant if the decl is static.  It's also invariant if it's
2759      a decl in the current function.  Taking the address of a volatile variable
2760      is not volatile.  If it's a constant, the address is both invariant and
2761      constant.  Otherwise it's neither.  */
2762   if (TREE_CODE (node) == INDIRECT_REF)
2763     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2764   else if (DECL_P (node))
2765     {
2766       if (staticp (node))
2767         ;
2768       else if (decl_function_context (node) == current_function_decl
2769                /* Addresses of thread-local variables are invariant.  */
2770                || (TREE_CODE (node) == VAR_DECL
2771                    && DECL_THREAD_LOCAL_P (node)))
2772         tc = false;
2773       else
2774         ti = tc = false;
2775     }
2776   else if (CONSTANT_CLASS_P (node))
2777     ;
2778   else
2779     {
2780       ti = tc = false;
2781       se |= TREE_SIDE_EFFECTS (node);
2782     }
2783
2784   TREE_CONSTANT (t) = tc;
2785   TREE_INVARIANT (t) = ti;
2786   TREE_SIDE_EFFECTS (t) = se;
2787 #undef UPDATE_TITCSE
2788 }
2789
2790 /* Build an expression of code CODE, data type TYPE, and operands as
2791    specified.  Expressions and reference nodes can be created this way.
2792    Constants, decls, types and misc nodes cannot be.
2793
2794    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2795    enough for all extant tree codes.  */
2796
2797 tree
2798 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2799 {
2800   tree t;
2801
2802   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2803
2804   t = make_node_stat (code PASS_MEM_STAT);
2805   TREE_TYPE (t) = tt;
2806
2807   return t;
2808 }
2809
2810 tree
2811 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2812 {
2813   int length = sizeof (struct tree_exp);
2814 #ifdef GATHER_STATISTICS
2815   tree_node_kind kind;
2816 #endif
2817   tree t;
2818
2819 #ifdef GATHER_STATISTICS
2820   switch (TREE_CODE_CLASS (code))
2821     {
2822     case tcc_statement:  /* an expression with side effects */
2823       kind = s_kind;
2824       break;
2825     case tcc_reference:  /* a reference */
2826       kind = r_kind;
2827       break;
2828     default:
2829       kind = e_kind;
2830       break;
2831     }
2832
2833   tree_node_counts[(int) kind]++;
2834   tree_node_sizes[(int) kind] += length;
2835 #endif
2836
2837   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2838
2839   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2840
2841   memset (t, 0, sizeof (struct tree_common));
2842
2843   TREE_SET_CODE (t, code);
2844
2845   TREE_TYPE (t) = type;
2846 #ifdef USE_MAPPED_LOCATION
2847   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2848 #else
2849   SET_EXPR_LOCUS (t, NULL);
2850 #endif
2851   TREE_COMPLEXITY (t) = 0;
2852   TREE_OPERAND (t, 0) = node;
2853   TREE_BLOCK (t) = NULL_TREE;
2854   if (node && !TYPE_P (node))
2855     {
2856       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2857       TREE_READONLY (t) = TREE_READONLY (node);
2858     }
2859
2860   if (TREE_CODE_CLASS (code) == tcc_statement)
2861     TREE_SIDE_EFFECTS (t) = 1;
2862   else switch (code)
2863     {
2864     case VA_ARG_EXPR:
2865       /* All of these have side-effects, no matter what their
2866          operands are.  */
2867       TREE_SIDE_EFFECTS (t) = 1;
2868       TREE_READONLY (t) = 0;
2869       break;
2870
2871     case MISALIGNED_INDIRECT_REF:
2872     case ALIGN_INDIRECT_REF:
2873     case INDIRECT_REF:
2874       /* Whether a dereference is readonly has nothing to do with whether
2875          its operand is readonly.  */
2876       TREE_READONLY (t) = 0;
2877       break;
2878
2879     case ADDR_EXPR:
2880       if (node)
2881         recompute_tree_invariant_for_addr_expr (t);
2882       break;
2883
2884     default:
2885       if (TREE_CODE_CLASS (code) == tcc_unary
2886           && node && !TYPE_P (node)
2887           && TREE_CONSTANT (node))
2888         TREE_CONSTANT (t) = 1;
2889       if (TREE_CODE_CLASS (code) == tcc_unary
2890           && node && TREE_INVARIANT (node))
2891         TREE_INVARIANT (t) = 1;
2892       if (TREE_CODE_CLASS (code) == tcc_reference
2893           && node && TREE_THIS_VOLATILE (node))
2894         TREE_THIS_VOLATILE (t) = 1;
2895       break;
2896     }
2897
2898   return t;
2899 }
2900
2901 #define PROCESS_ARG(N)                  \
2902   do {                                  \
2903     TREE_OPERAND (t, N) = arg##N;       \
2904     if (arg##N &&!TYPE_P (arg##N))      \
2905       {                                 \
2906         if (TREE_SIDE_EFFECTS (arg##N)) \
2907           side_effects = 1;             \
2908         if (!TREE_READONLY (arg##N))    \
2909           read_only = 0;                \
2910         if (!TREE_CONSTANT (arg##N))    \
2911           constant = 0;                 \
2912         if (!TREE_INVARIANT (arg##N))   \
2913           invariant = 0;                \
2914       }                                 \
2915   } while (0)
2916
2917 tree
2918 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2919 {
2920   bool constant, read_only, side_effects, invariant;
2921   tree t;
2922
2923   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2924
2925   t = make_node_stat (code PASS_MEM_STAT);
2926   TREE_TYPE (t) = tt;
2927
2928   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2929      result based on those same flags for the arguments.  But if the
2930      arguments aren't really even `tree' expressions, we shouldn't be trying
2931      to do this.  */
2932
2933   /* Expressions without side effects may be constant if their
2934      arguments are as well.  */
2935   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2936               || TREE_CODE_CLASS (code) == tcc_binary);
2937   read_only = 1;
2938   side_effects = TREE_SIDE_EFFECTS (t);
2939   invariant = constant;
2940
2941   PROCESS_ARG(0);
2942   PROCESS_ARG(1);
2943
2944   TREE_READONLY (t) = read_only;
2945   TREE_CONSTANT (t) = constant;
2946   TREE_INVARIANT (t) = invariant;
2947   TREE_SIDE_EFFECTS (t) = side_effects;
2948   TREE_THIS_VOLATILE (t)
2949     = (TREE_CODE_CLASS (code) == tcc_reference
2950        && arg0 && TREE_THIS_VOLATILE (arg0));
2951
2952   return t;
2953 }
2954
2955 tree
2956 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2957              tree arg2 MEM_STAT_DECL)
2958 {
2959   bool constant, read_only, side_effects, invariant;
2960   tree t;
2961
2962   gcc_assert (TREE_CODE_LENGTH (code) == 3);
2963
2964   t = make_node_stat (code PASS_MEM_STAT);
2965   TREE_TYPE (t) = tt;
2966
2967   side_effects = TREE_SIDE_EFFECTS (t);
2968
2969   PROCESS_ARG(0);
2970   PROCESS_ARG(1);
2971   PROCESS_ARG(2);
2972
2973   if (code == CALL_EXPR && !side_effects)
2974     {
2975       tree node;
2976       int i;
2977
2978       /* Calls have side-effects, except those to const or
2979          pure functions.  */
2980       i = call_expr_flags (t);
2981       if (!(i & (ECF_CONST | ECF_PURE)))
2982         side_effects = 1;
2983
2984       /* And even those have side-effects if their arguments do.  */
2985       else for (node = arg1; node; node = TREE_CHAIN (node))
2986         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2987           {
2988             side_effects = 1;
2989             break;
2990           }
2991     }
2992
2993   TREE_SIDE_EFFECTS (t) = side_effects;
2994   TREE_THIS_VOLATILE (t)
2995     = (TREE_CODE_CLASS (code) == tcc_reference
2996        && arg0 && TREE_THIS_VOLATILE (arg0));
2997
2998   return t;
2999 }
3000
3001 tree
3002 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3003              tree arg2, tree arg3 MEM_STAT_DECL)
3004 {
3005   bool constant, read_only, side_effects, invariant;
3006   tree t;
3007
3008   gcc_assert (TREE_CODE_LENGTH (code) == 4);
3009
3010   t = make_node_stat (code PASS_MEM_STAT);
3011   TREE_TYPE (t) = tt;
3012
3013   side_effects = TREE_SIDE_EFFECTS (t);
3014
3015   PROCESS_ARG(0);
3016   PROCESS_ARG(1);
3017   PROCESS_ARG(2);
3018   PROCESS_ARG(3);
3019
3020   TREE_SIDE_EFFECTS (t) = side_effects;
3021   TREE_THIS_VOLATILE (t)
3022     = (TREE_CODE_CLASS (code) == tcc_reference
3023        && arg0 && TREE_THIS_VOLATILE (arg0));
3024
3025   return t;
3026 }
3027
3028 tree
3029 build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3030              tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
3031 {
3032   bool constant, read_only, side_effects, invariant;
3033   tree t;
3034
3035   gcc_assert (TREE_CODE_LENGTH (code) == 5);
3036
3037   t = make_node_stat (code PASS_MEM_STAT);
3038   TREE_TYPE (t) = tt;
3039
3040   side_effects = TREE_SIDE_EFFECTS (t);
3041
3042   PROCESS_ARG(0);
3043   PROCESS_ARG(1);
3044   PROCESS_ARG(2);
3045   PROCESS_ARG(3);
3046   PROCESS_ARG(4);
3047
3048   TREE_SIDE_EFFECTS (t) = side_effects;
3049   TREE_THIS_VOLATILE (t)
3050     = (TREE_CODE_CLASS (code) == tcc_reference
3051        && arg0 && TREE_THIS_VOLATILE (arg0));
3052
3053   return t;
3054 }
3055
3056 tree
3057 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3058              tree arg2, tree arg3, tree arg4, tree arg5,
3059              tree arg6 MEM_STAT_DECL)
3060 {
3061   bool constant, read_only, side_effects, invariant;
3062   tree t;
3063
3064   gcc_assert (code == TARGET_MEM_REF);
3065
3066   t = make_node_stat (code PASS_MEM_STAT);
3067   TREE_TYPE (t) = tt;
3068
3069   side_effects = TREE_SIDE_EFFECTS (t);
3070
3071   PROCESS_ARG(0);
3072   PROCESS_ARG(1);
3073   PROCESS_ARG(2);
3074   PROCESS_ARG(3);
3075   PROCESS_ARG(4);
3076   PROCESS_ARG(5);
3077   PROCESS_ARG(6);
3078
3079   TREE_SIDE_EFFECTS (t) = side_effects;
3080   TREE_THIS_VOLATILE (t) = 0;
3081
3082   return t;
3083 }
3084
3085 /* Similar except don't specify the TREE_TYPE
3086    and leave the TREE_SIDE_EFFECTS as 0.
3087    It is permissible for arguments to be null,
3088    or even garbage if their values do not matter.  */
3089
3090 tree
3091 build_nt (enum tree_code code, ...)
3092 {
3093   tree t;
3094   int length;
3095   int i;
3096   va_list p;
3097
3098   va_start (p, code);
3099
3100   t = make_node (code);
3101   length = TREE_CODE_LENGTH (code);
3102
3103   for (i = 0; i < length; i++)
3104     TREE_OPERAND (t, i) = va_arg (p, tree);
3105
3106   va_end (p);
3107   return t;
3108 }
3109 \f
3110 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
3111    We do NOT enter this node in any sort of symbol table.
3112
3113    layout_decl is used to set up the decl's storage layout.
3114    Other slots are initialized to 0 or null pointers.  */
3115
3116 tree
3117 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
3118 {
3119   tree t;
3120
3121   t = make_node_stat (code PASS_MEM_STAT);
3122
3123 /*  if (type == error_mark_node)
3124     type = integer_type_node; */
3125 /* That is not done, deliberately, so that having error_mark_node
3126    as the type can suppress useless errors in the use of this variable.  */
3127
3128   DECL_NAME (t) = name;
3129   TREE_TYPE (t) = type;
3130
3131   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3132     layout_decl (t, 0);
3133   else if (code == FUNCTION_DECL)
3134     DECL_MODE (t) = FUNCTION_MODE;
3135
3136   if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
3137     {
3138       /* Set default visibility to whatever the user supplied with
3139          visibility_specified depending on #pragma GCC visibility.  */
3140       DECL_VISIBILITY (t) = default_visibility;
3141       DECL_VISIBILITY_SPECIFIED (t) = visibility_options.inpragma;
3142     }
3143
3144   return t;
3145 }
3146
3147 /* Builds and returns function declaration with NAME and TYPE.  */
3148
3149 tree
3150 build_fn_decl (const char *name, tree type)
3151 {
3152   tree id = get_identifier (name);
3153   tree decl = build_decl (FUNCTION_DECL, id, type);
3154
3155   DECL_EXTERNAL (decl) = 1;
3156   TREE_PUBLIC (decl) = 1;
3157   DECL_ARTIFICIAL (decl) = 1;
3158   TREE_NOTHROW (decl) = 1;
3159
3160   return decl;
3161 }
3162
3163 \f
3164 /* BLOCK nodes are used to represent the structure of binding contours
3165    and declarations, once those contours have been exited and their contents
3166    compiled.  This information is used for outputting debugging info.  */
3167
3168 tree
3169 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
3170 {
3171   tree block = make_node (BLOCK);
3172
3173   BLOCK_VARS (block) = vars;
3174   BLOCK_SUBBLOCKS (block) = subblocks;
3175   BLOCK_SUPERCONTEXT (block) = supercontext;
3176   BLOCK_CHAIN (block) = chain;
3177   return block;
3178 }
3179
3180 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
3181 /* ??? gengtype doesn't handle conditionals */
3182 static GTY(()) source_locus last_annotated_node;
3183 #endif
3184
3185 #ifdef USE_MAPPED_LOCATION
3186
3187 expanded_location
3188 expand_location (source_location loc)
3189 {
3190   expanded_location xloc;
3191   if (loc == 0) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
3192   else
3193     {
3194       const struct line_map *map = linemap_lookup (&line_table, loc);
3195       xloc.file = map->to_file;
3196       xloc.line = SOURCE_LINE (map, loc);
3197       xloc.column = SOURCE_COLUMN (map, loc);
3198     };
3199   return xloc;
3200 }
3201
3202 #else
3203
3204 /* Record the exact location where an expression or an identifier were
3205    encountered.  */
3206
3207 void
3208 annotate_with_file_line (tree node, const char *file, int line)
3209 {
3210   /* Roughly one percent of the calls to this function are to annotate
3211      a node with the same information already attached to that node!
3212      Just return instead of wasting memory.  */
3213   if (EXPR_LOCUS (node)
3214       && EXPR_LINENO (node) == line
3215       && (EXPR_FILENAME (node) == file
3216           || !strcmp (EXPR_FILENAME (node), file)))
3217     {
3218       last_annotated_node = EXPR_LOCUS (node);
3219       return;
3220     }
3221
3222   /* In heavily macroized code (such as GCC itself) this single
3223      entry cache can reduce the number of allocations by more
3224      than half.  */
3225   if (last_annotated_node
3226       && last_annotated_node->line == line
3227       && (last_annotated_node->file == file
3228           || !strcmp (last_annotated_node->file, file)))
3229     {
3230       SET_EXPR_LOCUS (node, last_annotated_node);
3231       return;
3232     }
3233
3234   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
3235   EXPR_LINENO (node) = line;
3236   EXPR_FILENAME (node) = file;
3237   last_annotated_node = EXPR_LOCUS (node);
3238 }
3239
3240 void
3241 annotate_with_locus (tree node, location_t locus)
3242 {
3243   annotate_with_file_line (node, locus.file, locus.line);
3244 }
3245 #endif
3246 \f
3247 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3248    is ATTRIBUTE.  */
3249
3250 tree
3251 build_decl_attribute_variant (tree ddecl, tree attribute)
3252 {
3253   DECL_ATTRIBUTES (ddecl) = attribute;
3254   return ddecl;
3255 }
3256
3257 /* Borrowed from hashtab.c iterative_hash implementation.  */
3258 #define mix(a,b,c) \
3259 { \
3260   a -= b; a -= c; a ^= (c>>13); \
3261   b -= c; b -= a; b ^= (a<< 8); \
3262   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3263   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3264   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3265   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3266   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3267   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3268   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3269 }
3270
3271
3272 /* Produce good hash value combining VAL and VAL2.  */
3273 static inline hashval_t
3274 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3275 {
3276   /* the golden ratio; an arbitrary value.  */
3277   hashval_t a = 0x9e3779b9;
3278
3279   mix (a, val, val2);
3280   return val2;
3281 }
3282
3283 /* Produce good hash value combining PTR and VAL2.  */
3284 static inline hashval_t
3285 iterative_hash_pointer (void *ptr, hashval_t val2)
3286 {
3287   if (sizeof (ptr) == sizeof (hashval_t))
3288     return iterative_hash_hashval_t ((size_t) ptr, val2);
3289   else
3290     {
3291       hashval_t a = (hashval_t) (size_t) ptr;
3292       /* Avoid warnings about shifting of more than the width of the type on
3293          hosts that won't execute this path.  */
3294       int zero = 0;
3295       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3296       mix (a, b, val2);
3297       return val2;
3298     }
3299 }
3300
3301 /* Produce good hash value combining VAL and VAL2.  */
3302 static inline hashval_t
3303 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3304 {
3305   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3306     return iterative_hash_hashval_t (val, val2);
3307   else
3308     {
3309       hashval_t a = (hashval_t) val;
3310       /* Avoid warnings about shifting of more than the width of the type on
3311          hosts that won't execute this path.  */
3312       int zero = 0;
3313       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3314       mix (a, b, val2);
3315       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3316         {
3317           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3318           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3319           mix (a, b, val2);
3320         }
3321       return val2;
3322     }
3323 }
3324
3325 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3326    is ATTRIBUTE.
3327
3328    Record such modified types already made so we don't make duplicates.  */
3329
3330 tree
3331 build_type_attribute_variant (tree ttype, tree attribute)
3332 {
3333   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3334     {
3335       hashval_t hashcode = 0;
3336       tree ntype;
3337       enum tree_code code = TREE_CODE (ttype);
3338
3339       ntype = copy_node (ttype);
3340
3341       TYPE_POINTER_TO (ntype) = 0;
3342       TYPE_REFERENCE_TO (ntype) = 0;
3343       TYPE_ATTRIBUTES (ntype) = attribute;
3344
3345       /* Create a new main variant of TYPE.  */
3346       TYPE_MAIN_VARIANT (ntype) = ntype;
3347       TYPE_NEXT_VARIANT (ntype) = 0;
3348       set_type_quals (ntype, TYPE_UNQUALIFIED);
3349
3350       hashcode = iterative_hash_object (code, hashcode);
3351       if (TREE_TYPE (ntype))
3352         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3353                                           hashcode);
3354       hashcode = attribute_hash_list (attribute, hashcode);
3355
3356       switch (TREE_CODE (ntype))
3357         {
3358         case FUNCTION_TYPE:
3359           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3360           break;
3361         case ARRAY_TYPE:
3362           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3363                                             hashcode);
3364           break;
3365         case INTEGER_TYPE:
3366           hashcode = iterative_hash_object
3367             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3368           hashcode = iterative_hash_object
3369             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3370           break;
3371         case REAL_TYPE:
3372           {
3373             unsigned int precision = TYPE_PRECISION (ntype);
3374             hashcode = iterative_hash_object (precision, hashcode);
3375           }
3376           break;
3377         default:
3378           break;
3379         }
3380
3381       ntype = type_hash_canon (hashcode, ntype);
3382       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
3383     }
3384
3385   return ttype;
3386 }
3387
3388
3389 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3390    or zero if not.
3391
3392    We try both `text' and `__text__', ATTR may be either one.  */
3393 /* ??? It might be a reasonable simplification to require ATTR to be only
3394    `text'.  One might then also require attribute lists to be stored in
3395    their canonicalized form.  */
3396
3397 static int
3398 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3399 {
3400   int ident_len;
3401   const char *p;
3402
3403   if (TREE_CODE (ident) != IDENTIFIER_NODE)
3404     return 0;
3405
3406   p = IDENTIFIER_POINTER (ident);
3407   ident_len = IDENTIFIER_LENGTH (ident);
3408
3409   if (ident_len == attr_len
3410       && strcmp (attr, p) == 0)
3411     return 1;
3412
3413   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
3414   if (attr[0] == '_')
3415     {
3416       gcc_assert (attr[1] == '_');
3417       gcc_assert (attr[attr_len - 2] == '_');
3418       gcc_assert (attr[attr_len - 1] == '_');
3419       gcc_assert (attr[1] == '_');
3420       if (ident_len == attr_len - 4
3421           && strncmp (attr + 2, p, attr_len - 4) == 0)
3422         return 1;
3423     }
3424   else
3425     {
3426       if (ident_len == attr_len + 4
3427           && p[0] == '_' && p[1] == '_'
3428           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3429           && strncmp (attr, p + 2, attr_len) == 0)
3430         return 1;
3431     }
3432
3433   return 0;
3434 }
3435
3436 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3437    or zero if not.
3438
3439    We try both `text' and `__text__', ATTR may be either one.  */
3440
3441 int
3442 is_attribute_p (const char *attr, tree ident)
3443 {
3444   return is_attribute_with_length_p (attr, strlen (attr), ident);
3445 }
3446
3447 /* Given an attribute name and a list of attributes, return a pointer to the
3448    attribute's list element if the attribute is part of the list, or NULL_TREE
3449    if not found.  If the attribute appears more than once, this only
3450    returns the first occurrence; the TREE_CHAIN of the return value should
3451    be passed back in if further occurrences are wanted.  */
3452
3453 tree
3454 lookup_attribute (const char *attr_name, tree list)
3455 {
3456   tree l;
3457   size_t attr_len = strlen (attr_name);
3458
3459   for (l = list; l; l = TREE_CHAIN (l))
3460     {
3461       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3462       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3463         return l;
3464     }
3465
3466   return NULL_TREE;
3467 }
3468
3469 /* Return an attribute list that is the union of a1 and a2.  */
3470
3471 tree
3472 merge_attributes (tree a1, tree a2)
3473 {
3474   tree attributes;
3475
3476   /* Either one unset?  Take the set one.  */
3477
3478   if ((attributes = a1) == 0)
3479     attributes = a2;
3480
3481   /* One that completely contains the other?  Take it.  */
3482
3483   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3484     {
3485       if (attribute_list_contained (a2, a1))
3486         attributes = a2;
3487       else
3488         {
3489           /* Pick the longest list, and hang on the other list.  */
3490
3491           if (list_length (a1) < list_length (a2))
3492             attributes = a2, a2 = a1;
3493
3494           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3495             {
3496               tree a;
3497               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3498                                          attributes);
3499                    a != NULL_TREE;
3500                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3501                                          TREE_CHAIN (a)))
3502                 {
3503                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
3504                     break;
3505                 }
3506               if (a == NULL_TREE)
3507                 {
3508                   a1 = copy_node (a2);
3509                   TREE_CHAIN (a1) = attributes;
3510                   attributes = a1;
3511                 }
3512             }
3513         }
3514     }
3515   return attributes;
3516 }
3517
3518 /* Given types T1 and T2, merge their attributes and return
3519   the result.  */
3520
3521 tree
3522 merge_type_attributes (tree t1, tree t2)
3523 {
3524   return merge_attributes (TYPE_ATTRIBUTES (t1),
3525                            TYPE_ATTRIBUTES (t2));
3526 }
3527
3528 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3529    the result.  */
3530
3531 tree
3532 merge_decl_attributes (tree olddecl, tree newdecl)
3533 {
3534   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3535                            DECL_ATTRIBUTES (newdecl));
3536 }
3537
3538 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3539
3540 /* Specialization of merge_decl_attributes for various Windows targets.
3541
3542    This handles the following situation:
3543
3544      __declspec (dllimport) int foo;
3545      int foo;
3546
3547    The second instance of `foo' nullifies the dllimport.  */
3548
3549 tree
3550 merge_dllimport_decl_attributes (tree old, tree new)
3551 {
3552   tree a;
3553   int delete_dllimport_p = 1;
3554
3555   /* What we need to do here is remove from `old' dllimport if it doesn't
3556      appear in `new'.  dllimport behaves like extern: if a declaration is
3557      marked dllimport and a definition appears later, then the object
3558      is not dllimport'd.  We also remove a `new' dllimport if the old list
3559      contains dllexport:  dllexport always overrides dllimport, regardless
3560      of the order of declaration.  */
3561   if (!VAR_OR_FUNCTION_DECL_P (new))
3562     delete_dllimport_p = 0;
3563   else if (DECL_DLLIMPORT_P (new)
3564            && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old)))
3565     {
3566       DECL_DLLIMPORT_P (new) = 0;
3567       warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: "
3568               "dllimport ignored", new);
3569     }
3570   else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new))
3571     {
3572       /* Warn about overriding a symbol that has already been used. eg:
3573            extern int __attribute__ ((dllimport)) foo;
3574            int* bar () {return &foo;}
3575            int foo;
3576       */
3577       if (TREE_USED (old))
3578         {
3579           warning (0, "%q+D redeclared without dllimport attribute "
3580                    "after being referenced with dll linkage", new);
3581           /* If we have used a variable's address with dllimport linkage,
3582               keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the
3583               decl may already have had TREE_INVARIANT and TREE_CONSTANT
3584               computed.
3585               We still remove the attribute so that assembler code refers
3586               to '&foo rather than '_imp__foo'.  */
3587           if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old))
3588             DECL_DLLIMPORT_P (new) = 1;
3589         }
3590
3591       /* Let an inline definition silently override the external reference,
3592          but otherwise warn about attribute inconsistency.  */
3593       else if (TREE_CODE (new) == VAR_DECL
3594                || !DECL_DECLARED_INLINE_P (new))
3595         warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: "
3596                   "previous dllimport ignored", new);
3597     }
3598   else
3599     delete_dllimport_p = 0;
3600
3601   a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new));
3602
3603   if (delete_dllimport_p)
3604     {
3605       tree prev, t;
3606       const size_t attr_len = strlen ("dllimport");
3607
3608       /* Scan the list for dllimport and delete it.  */
3609       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3610         {
3611           if (is_attribute_with_length_p ("dllimport", attr_len,
3612                                           TREE_PURPOSE (t)))
3613             {
3614               if (prev == NULL_TREE)
3615                 a = TREE_CHAIN (a);
3616               else
3617                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3618               break;
3619             }
3620         }
3621     }
3622
3623   return a;
3624 }
3625
3626 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3627    struct attribute_spec.handler.  */
3628
3629 tree
3630 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3631                       bool *no_add_attrs)
3632 {
3633   tree node = *pnode;
3634
3635   /* These attributes may apply to structure and union types being created,
3636      but otherwise should pass to the declaration involved.  */
3637   if (!DECL_P (node))
3638     {
3639       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3640                    | (int) ATTR_FLAG_ARRAY_NEXT))
3641         {
3642           *no_add_attrs = true;
3643           return tree_cons (name, args, NULL_TREE);
3644         }
3645       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3646         {
3647           warning (OPT_Wattributes, "%qs attribute ignored",
3648                    IDENTIFIER_POINTER (name));
3649           *no_add_attrs = true;
3650         }
3651
3652       return NULL_TREE;
3653     }
3654
3655   /* Report error on dllimport ambiguities seen now before they cause
3656      any damage.  */
3657   if (is_attribute_p ("dllimport", name))
3658     {
3659       /* Honor any target-specific overrides. */
3660       if (!targetm.valid_dllimport_attribute_p (node))
3661         *no_add_attrs = true;
3662
3663      else if (TREE_CODE (node) == FUNCTION_DECL
3664                 && DECL_DECLARED_INLINE_P (node))
3665         {
3666           warning (OPT_Wattributes, "inline function %q+D declared as "
3667                   " dllimport: attribute ignored", node);
3668           *no_add_attrs = true;
3669         }
3670       /* Like MS, treat definition of dllimported variables and
3671          non-inlined functions on declaration as syntax errors. */
3672      else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node))
3673         {
3674           error ("function %q+D definition is marked dllimport", node);
3675           *no_add_attrs = true;
3676         }
3677
3678      else if (TREE_CODE (node) == VAR_DECL)
3679         {
3680           if (DECL_INITIAL (node))
3681             {
3682               error ("variable %q+D definition is marked dllimport",
3683                      node);
3684               *no_add_attrs = true;
3685             }
3686
3687           /* `extern' needn't be specified with dllimport.
3688              Specify `extern' now and hope for the best.  Sigh.  */
3689           DECL_EXTERNAL (node) = 1;
3690           /* Also, implicitly give dllimport'd variables declared within
3691              a function global scope, unless declared static.  */
3692           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3693             TREE_PUBLIC (node) = 1;
3694         }
3695
3696       if (*no_add_attrs == false)
3697         DECL_DLLIMPORT_P (node) = 1;
3698     }
3699
3700   /*  Report error if symbol is not accessible at global scope.  */
3701   if (!TREE_PUBLIC (node)
3702       && (TREE_CODE (node) == VAR_DECL
3703           || TREE_CODE (node) == FUNCTION_DECL))
3704     {
3705       error ("external linkage required for symbol %q+D because of "
3706              "%qs attribute", node, IDENTIFIER_POINTER (name));
3707       *no_add_attrs = true;
3708     }
3709
3710   return NULL_TREE;
3711 }
3712
3713 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3714 \f
3715 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3716    of the various TYPE_QUAL values.  */
3717
3718 static void
3719 set_type_quals (tree type, int type_quals)
3720 {
3721   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3722   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3723   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3724 }
3725
3726 /* Returns true iff cand is equivalent to base with type_quals.  */
3727
3728 bool
3729 check_qualified_type (tree cand, tree base, int type_quals)
3730 {
3731   return (TYPE_QUALS (cand) == type_quals
3732           && TYPE_NAME (cand) == TYPE_NAME (base)
3733           /* Apparently this is needed for Objective-C.  */
3734           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3735           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3736                                    TYPE_ATTRIBUTES (base)));
3737 }
3738
3739 /* Return a version of the TYPE, qualified as indicated by the
3740    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3741    return NULL_TREE.  */
3742
3743 tree
3744 get_qualified_type (tree type, int type_quals)
3745 {
3746   tree t;
3747
3748   if (TYPE_QUALS (type) == type_quals)
3749     return type;
3750
3751   /* Search the chain of variants to see if there is already one there just
3752      like the one we need to have.  If so, use that existing one.  We must
3753      preserve the TYPE_NAME, since there is code that depends on this.  */
3754   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3755     if (check_qualified_type (t, type, type_quals))
3756       return t;
3757
3758   return NULL_TREE;
3759 }
3760
3761 /* Like get_qualified_type, but creates the type if it does not
3762    exist.  This function never returns NULL_TREE.  */
3763
3764 tree
3765 build_qualified_type (tree type, int type_quals)
3766 {
3767   tree t;
3768
3769   /* See if we already have the appropriate qualified variant.  */
3770   t = get_qualified_type (type, type_quals);
3771
3772   /* If not, build it.  */
3773   if (!t)
3774     {
3775       t = build_variant_type_copy (type);
3776       set_type_quals (t, type_quals);
3777     }
3778
3779   return t;
3780 }
3781
3782 /* Create a new distinct copy of TYPE.  The new type is made its own
3783    MAIN_VARIANT.  */
3784
3785 tree
3786 build_distinct_type_copy (tree type)
3787 {
3788   tree t = copy_node (type);
3789
3790   TYPE_POINTER_TO (t) = 0;
3791   TYPE_REFERENCE_TO (t) = 0;
3792
3793   /* Make it its own variant.  */
3794   TYPE_MAIN_VARIANT (t) = t;
3795   TYPE_NEXT_VARIANT (t) = 0;
3796
3797   return t;
3798 }
3799
3800 /* Create a new variant of TYPE, equivalent but distinct.
3801    This is so the caller can modify it.  */
3802
3803 tree
3804 build_variant_type_copy (tree type)
3805 {
3806   tree t, m = TYPE_MAIN_VARIANT (type);
3807
3808   t = build_distinct_type_copy (type);
3809
3810   /* Add the new type to the chain of variants of TYPE.  */
3811   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3812   TYPE_NEXT_VARIANT (m) = t;
3813   TYPE_MAIN_VARIANT (t) = m;
3814
3815   return t;
3816 }
3817 \f
3818 /* Return true if the from tree in both tree maps are equal.  */
3819
3820 int
3821 tree_map_eq (const void *va, const void *vb)
3822 {
3823   const struct tree_map  *a = va, *b = vb;
3824   return (a->from == b->from);
3825 }
3826
3827 /* Hash a from tree in a tree_map.  */
3828
3829 unsigned int
3830 tree_map_hash (const void *item)
3831 {
3832   return (((const struct tree_map *) item)->hash);
3833 }
3834
3835 /* Return true if this tree map structure is marked for garbage collection
3836    purposes.  We simply return true if the from tree is marked, so that this
3837    structure goes away when the from tree goes away.  */
3838
3839 int
3840 tree_map_marked_p (const void *p)
3841 {
3842   tree from = ((struct tree_map *) p)->from;
3843
3844   return ggc_marked_p (from);
3845 }
3846
3847 /* Return true if the trees in the tree_int_map *'s VA and VB are equal.  */
3848
3849 static int
3850 tree_int_map_eq (const void *va, const void *vb)
3851 {
3852   const struct tree_int_map  *a = va, *b = vb;
3853   return (a->from == b->from);
3854 }
3855
3856 /* Hash a from tree in the tree_int_map * ITEM.  */
3857
3858 static unsigned int
3859 tree_int_map_hash (const void *item)
3860 {
3861   return htab_hash_pointer (((const struct tree_int_map *)item)->from);
3862 }
3863
3864 /* Return true if this tree int map structure is marked for garbage collection
3865    purposes.  We simply return true if the from tree_int_map *P's from tree is marked, so that this
3866    structure goes away when the from tree goes away.  */
3867
3868 static int
3869 tree_int_map_marked_p (const void *p)
3870 {
3871   tree from = ((struct tree_int_map *) p)->from;
3872
3873   return ggc_marked_p (from);
3874 }
3875 /* Lookup an init priority for FROM, and return it if we find one.  */
3876
3877 unsigned short
3878 decl_init_priority_lookup (tree from)
3879 {
3880   struct tree_int_map *h, in;
3881   in.from = from;
3882
3883   h = htab_find_with_hash (init_priority_for_decl,
3884                            &in, htab_hash_pointer (from));
3885   if (h)
3886     return h->to;
3887   return 0;
3888 }
3889
3890 /* Insert a mapping FROM->TO in the init priority hashtable.  */
3891
3892 void
3893 decl_init_priority_insert (tree from, unsigned short to)
3894 {
3895   struct tree_int_map *h;
3896   void **loc;
3897
3898   h = ggc_alloc (sizeof (struct tree_int_map));
3899   h->from = from;
3900   h->to = to;
3901   loc = htab_find_slot_with_hash (init_priority_for_decl, h,
3902                                   htab_hash_pointer (from), INSERT);
3903   *(struct tree_int_map **) loc = h;
3904 }
3905
3906 /* Look up a restrict qualified base decl for FROM.  */
3907
3908 tree
3909 decl_restrict_base_lookup (tree from)
3910 {
3911   struct tree_map *h;
3912   struct tree_map in;
3913
3914   in.from = from;
3915   h = htab_find_with_hash (restrict_base_for_decl, &in,
3916                            htab_hash_pointer (from));
3917   return h ? h->to : NULL_TREE;
3918 }
3919
3920 /* Record the restrict qualified base TO for FROM.  */
3921
3922 void
3923 decl_restrict_base_insert (tree from, tree to)
3924 {
3925   struct tree_map *h;
3926   void **loc;
3927
3928   h = ggc_alloc (sizeof (struct tree_map));
3929   h->hash = htab_hash_pointer (from);
3930   h->from = from;
3931   h->to = to;
3932   loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT);
3933   *(struct tree_map **) loc = h;
3934 }
3935
3936 /* Print out the statistics for the DECL_DEBUG_EXPR hash table.  */
3937
3938 static void
3939 print_debug_expr_statistics (void)
3940 {
3941   fprintf (stderr, "DECL_DEBUG_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3942            (long) htab_size (debug_expr_for_decl),
3943            (long) htab_elements (debug_expr_for_decl),
3944            htab_collisions (debug_expr_for_decl));
3945 }
3946
3947 /* Print out the statistics for the DECL_VALUE_EXPR hash table.  */
3948
3949 static void
3950 print_value_expr_statistics (void)
3951 {
3952   fprintf (stderr, "DECL_VALUE_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3953            (long) htab_size (value_expr_for_decl),
3954            (long) htab_elements (value_expr_for_decl),
3955            htab_collisions (value_expr_for_decl));
3956 }
3957
3958 /* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but
3959    don't print anything if the table is empty.  */
3960
3961 static void
3962 print_restrict_base_statistics (void)
3963 {
3964   if (htab_elements (restrict_base_for_decl) != 0)
3965     fprintf (stderr,
3966              "RESTRICT_BASE    hash: size %ld, %ld elements, %f collisions\n",
3967              (long) htab_size (restrict_base_for_decl),
3968              (long) htab_elements (restrict_base_for_decl),
3969              htab_collisions (restrict_base_for_decl));
3970 }
3971
3972 /* Lookup a debug expression for FROM, and return it if we find one.  */
3973
3974 tree
3975 decl_debug_expr_lookup (tree from)
3976 {
3977   struct tree_map *h, in;
3978   in.from = from;
3979
3980   h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
3981   if (h)
3982     return h->to;
3983   return NULL_TREE;
3984 }
3985
3986 /* Insert a mapping FROM->TO in the debug expression hashtable.  */
3987
3988 void
3989 decl_debug_expr_insert (tree from, tree to)
3990 {
3991   struct tree_map *h;
3992   void **loc;
3993
3994   h = ggc_alloc (sizeof (struct tree_map));
3995   h->hash = htab_hash_pointer (from);
3996   h->from = from;
3997   h->to = to;
3998   loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
3999   *(struct tree_map **) loc = h;
4000 }
4001
4002 /* Lookup a value expression for FROM, and return it if we find one.  */
4003
4004 tree
4005 decl_value_expr_lookup (tree from)
4006 {
4007   struct tree_map *h, in;
4008   in.from = from;
4009
4010   h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
4011   if (h)
4012     return h->to;
4013   return NULL_TREE;
4014 }
4015
4016 /* Insert a mapping FROM->TO in the value expression hashtable.  */
4017
4018 void
4019 decl_value_expr_insert (tree from, tree to)
4020 {
4021   struct tree_map *h;
4022   void **loc;
4023
4024   h = ggc_alloc (sizeof (struct tree_map));
4025   h->hash = htab_hash_pointer (from);
4026   h->from = from;
4027   h->to = to;
4028   loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
4029   *(struct tree_map **) loc = h;
4030 }
4031
4032 /* Hashing of types so that we don't make duplicates.
4033    The entry point is `type_hash_canon'.  */
4034
4035 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
4036    with types in the TREE_VALUE slots), by adding the hash codes
4037    of the individual types.  */
4038
4039 unsigned int
4040 type_hash_list (tree list, hashval_t hashcode)
4041 {
4042   tree tail;
4043
4044   for (tail = list; tail; tail = TREE_CHAIN (tail))
4045     if (TREE_VALUE (tail) != error_mark_node)
4046       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
4047                                         hashcode);
4048
4049   return hashcode;
4050 }
4051
4052 /* These are the Hashtable callback functions.  */
4053
4054 /* Returns true iff the types are equivalent.  */
4055
4056 static int
4057 type_hash_eq (const void *va, const void *vb)
4058 {
4059   const struct type_hash *a = va, *b = vb;
4060
4061   /* First test the things that are the same for all types.  */
4062   if (a->hash != b->hash
4063       || TREE_CODE (a->type) != TREE_CODE (b->type)
4064       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
4065       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
4066                                  TYPE_ATTRIBUTES (b->type))
4067       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
4068       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
4069     return 0;
4070
4071   switch (TREE_CODE (a->type))
4072     {
4073     case VOID_TYPE:
4074     case COMPLEX_TYPE:
4075     case POINTER_TYPE:
4076     case REFERENCE_TYPE:
4077       return 1;
4078
4079     case VECTOR_TYPE:
4080       return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
4081
4082     case ENUMERAL_TYPE:
4083       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
4084           && !(TYPE_VALUES (a->type)
4085                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
4086                && TYPE_VALUES (b->type)
4087                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
4088                && type_list_equal (TYPE_VALUES (a->type),
4089                                    TYPE_VALUES (b->type))))
4090         return 0;
4091
4092       /* ... fall through ... */
4093
4094     case INTEGER_TYPE:
4095     case REAL_TYPE:
4096     case BOOLEAN_TYPE:
4097       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
4098                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
4099                                       TYPE_MAX_VALUE (b->type)))
4100               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
4101                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
4102                                          TYPE_MIN_VALUE (b->type))));
4103
4104     case OFFSET_TYPE:
4105       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
4106
4107     case METHOD_TYPE:
4108       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
4109               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4110                   || (TYPE_ARG_TYPES (a->type)
4111                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4112                       && TYPE_ARG_TYPES (b->type)
4113                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4114                       && type_list_equal (TYPE_ARG_TYPES (a->type),
4115                                           TYPE_ARG_TYPES (b->type)))));
4116
4117     case ARRAY_TYPE:
4118       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
4119
4120     case RECORD_TYPE:
4121     case UNION_TYPE:
4122     case QUAL_UNION_TYPE:
4123       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
4124               || (TYPE_FIELDS (a->type)
4125                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
4126                   && TYPE_FIELDS (b->type)
4127                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
4128                   && type_list_equal (TYPE_FIELDS (a->type),
4129                                       TYPE_FIELDS (b->type))));
4130
4131     case FUNCTION_TYPE:
4132       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4133               || (TYPE_ARG_TYPES (a->type)
4134                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4135                   && TYPE_ARG_TYPES (b->type)
4136                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4137                   && type_list_equal (TYPE_ARG_TYPES (a->type),
4138                                       TYPE_ARG_TYPES (b->type))));
4139
4140     default:
4141       return 0;
4142     }
4143 }
4144
4145 /* Return the cached hash value.  */
4146
4147 static hashval_t
4148 type_hash_hash (const void *item)
4149 {
4150   return ((const struct type_hash *) item)->hash;
4151 }
4152
4153 /* Look in the type hash table for a type isomorphic to TYPE.
4154    If one is found, return it.  Otherwise return 0.  */
4155
4156 tree
4157 type_hash_lookup (hashval_t hashcode, tree type)
4158 {
4159   struct type_hash *h, in;
4160
4161   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
4162      must call that routine before comparing TYPE_ALIGNs.  */
4163   layout_type (type);
4164
4165   in.hash = hashcode;
4166   in.type = type;
4167
4168   h = htab_find_with_hash (type_hash_table, &in, hashcode);
4169   if (h)
4170     return h->type;
4171   return NULL_TREE;
4172 }
4173
4174 /* Add an entry to the type-hash-table
4175    for a type TYPE whose hash code is HASHCODE.  */
4176
4177 void
4178 type_hash_add (hashval_t hashcode, tree type)
4179 {
4180   struct type_hash *h;
4181   void **loc;
4182
4183   h = ggc_alloc (sizeof (struct type_hash));
4184   h->hash = hashcode;
4185   h->type = type;
4186   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
4187   *(struct type_hash **) loc = h;
4188 }
4189
4190 /* Given TYPE, and HASHCODE its hash code, return the canonical
4191    object for an identical type if one already exists.
4192    Otherwise, return TYPE, and record it as the canonical object.
4193
4194    To use this function, first create a type of the sort you want.
4195    Then compute its hash code from the fields of the type that
4196    make it different from other similar types.
4197    Then call this function and use the value.  */
4198
4199 tree
4200 type_hash_canon (unsigned int hashcode, tree type)
4201 {
4202   tree t1;
4203
4204   /* The hash table only contains main variants, so ensure that's what we're
4205      being passed.  */
4206   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
4207
4208   if (!lang_hooks.types.hash_types)
4209     return type;
4210
4211   /* See if the type is in the hash table already.  If so, return it.
4212      Otherwise, add the type.  */
4213   t1 = type_hash_lookup (hashcode, type);
4214   if (t1 != 0)
4215     {
4216 #ifdef GATHER_STATISTICS
4217       tree_node_counts[(int) t_kind]--;
4218       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
4219 #endif
4220       return t1;
4221     }
4222   else
4223     {
4224       type_hash_add (hashcode, type);
4225       return type;
4226     }
4227 }
4228
4229 /* See if the data pointed to by the type hash table is marked.  We consider
4230    it marked if the type is marked or if a debug type number or symbol
4231    table entry has been made for the type.  This reduces the amount of
4232    debugging output and eliminates that dependency of the debug output on
4233    the number of garbage collections.  */
4234
4235 static int
4236 type_hash_marked_p (const void *p)
4237 {
4238   tree type = ((struct type_hash *) p)->type;
4239
4240   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
4241 }
4242
4243 static void
4244 print_type_hash_statistics (void)
4245 {
4246   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
4247            (long) htab_size (type_hash_table),
4248            (long) htab_elements (type_hash_table),
4249            htab_collisions (type_hash_table));
4250 }
4251
4252 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
4253    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
4254    by adding the hash codes of the individual attributes.  */
4255
4256 unsigned int
4257 attribute_hash_list (tree list, hashval_t hashcode)
4258 {
4259   tree tail;
4260
4261   for (tail = list; tail; tail = TREE_CHAIN (tail))
4262     /* ??? Do we want to add in TREE_VALUE too? */
4263     hashcode = iterative_hash_object
4264       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
4265   return hashcode;
4266 }
4267
4268 /* Given two lists of attributes, return true if list l2 is
4269    equivalent to l1.  */
4270
4271 int
4272 attribute_list_equal (tree l1, tree l2)
4273 {
4274   return attribute_list_contained (l1, l2)
4275          && attribute_list_contained (l2, l1);
4276 }
4277
4278 /* Given two lists of attributes, return true if list L2 is
4279    completely contained within L1.  */
4280 /* ??? This would be faster if attribute names were stored in a canonicalized
4281    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
4282    must be used to show these elements are equivalent (which they are).  */
4283 /* ??? It's not clear that attributes with arguments will always be handled
4284    correctly.  */
4285
4286 int
4287 attribute_list_contained (tree l1, tree l2)
4288 {
4289   tree t1, t2;
4290
4291   /* First check the obvious, maybe the lists are identical.  */
4292   if (l1 == l2)
4293     return 1;
4294
4295   /* Maybe the lists are similar.  */
4296   for (t1 = l1, t2 = l2;
4297        t1 != 0 && t2 != 0
4298         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
4299         && TREE_VALUE (t1) == TREE_VALUE (t2);
4300        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
4301
4302   /* Maybe the lists are equal.  */
4303   if (t1 == 0 && t2 == 0)
4304     return 1;
4305
4306   for (; t2 != 0; t2 = TREE_CHAIN (t2))
4307     {
4308       tree attr;
4309       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
4310            attr != NULL_TREE;
4311            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
4312                                     TREE_CHAIN (attr)))
4313         {
4314           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
4315             break;
4316         }
4317
4318       if (attr == 0)
4319         return 0;
4320
4321       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
4322         return 0;
4323     }
4324
4325   return 1;
4326 }
4327
4328 /* Given two lists of types
4329    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
4330    return 1 if the lists contain the same types in the same order.
4331    Also, the TREE_PURPOSEs must match.  */
4332
4333 int
4334 type_list_equal (tree l1, tree l2)
4335 {
4336   tree t1, t2;
4337
4338   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
4339     if (TREE_VALUE (t1) != TREE_VALUE (t2)
4340         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
4341             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
4342                   && (TREE_TYPE (TREE_PURPOSE (t1))
4343                       == TREE_TYPE (TREE_PURPOSE (t2))))))
4344       return 0;
4345
4346   return t1 == t2;
4347 }
4348
4349 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
4350    given by TYPE.  If the argument list accepts variable arguments,
4351    then this function counts only the ordinary arguments.  */
4352
4353 int
4354 type_num_arguments (tree type)
4355 {
4356   int i = 0;
4357   tree t;
4358
4359   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
4360     /* If the function does not take a variable number of arguments,
4361        the last element in the list will have type `void'.  */
4362     if (VOID_TYPE_P (TREE_VALUE (t)))
4363       break;
4364     else
4365       ++i;
4366
4367   return i;
4368 }
4369
4370 /* Nonzero if integer constants T1 and T2
4371    represent the same constant value.  */
4372
4373 int
4374 tree_int_cst_equal (tree t1, tree t2)
4375 {
4376   if (t1 == t2)
4377     return 1;
4378
4379   if (t1 == 0 || t2 == 0)
4380     return 0;
4381
4382   if (TREE_CODE (t1) == INTEGER_CST
4383       && TREE_CODE (t2) == INTEGER_CST
4384       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4385       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
4386     return 1;
4387
4388   return 0;
4389 }
4390
4391 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
4392    The precise way of comparison depends on their data type.  */
4393
4394 int
4395 tree_int_cst_lt (tree t1, tree t2)
4396 {
4397   if (t1 == t2)
4398     return 0;
4399
4400   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
4401     {
4402       int t1_sgn = tree_int_cst_sgn (t1);
4403       int t2_sgn = tree_int_cst_sgn (t2);
4404
4405       if (t1_sgn < t2_sgn)
4406         return 1;
4407       else if (t1_sgn > t2_sgn)
4408         return 0;
4409       /* Otherwise, both are non-negative, so we compare them as
4410          unsigned just in case one of them would overflow a signed
4411          type.  */
4412     }
4413   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4414     return INT_CST_LT (t1, t2);
4415
4416   return INT_CST_LT_UNSIGNED (t1, t2);
4417 }
4418
4419 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
4420
4421 int
4422 tree_int_cst_compare (tree t1, tree t2)
4423 {
4424   if (tree_int_cst_lt (t1, t2))
4425     return -1;
4426   else if (tree_int_cst_lt (t2, t1))
4427     return 1;
4428   else
4429     return 0;
4430 }
4431
4432 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4433    the host.  If POS is zero, the value can be represented in a single
4434    HOST_WIDE_INT.  If POS is nonzero, the value must be non-negative and can
4435    be represented in a single unsigned HOST_WIDE_INT.  */
4436
4437 int
4438 host_integerp (tree t, int pos)
4439 {
4440   return (TREE_CODE (t) == INTEGER_CST
4441           && ((TREE_INT_CST_HIGH (t) == 0
4442                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4443               || (! pos && TREE_INT_CST_HIGH (t) == -1
4444                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4445                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
4446               || (pos && TREE_INT_CST_HIGH (t) == 0)));
4447 }
4448
4449 /* Return the HOST_WIDE_INT least significant bits of T if it is an
4450    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
4451    be non-negative.  We must be able to satisfy the above conditions.  */
4452
4453 HOST_WIDE_INT
4454 tree_low_cst (tree t, int pos)
4455 {
4456   gcc_assert (host_integerp (t, pos));
4457   return TREE_INT_CST_LOW (t);
4458 }
4459
4460 /* Return the most significant bit of the integer constant T.  */
4461
4462 int
4463 tree_int_cst_msb (tree t)
4464 {
4465   int prec;
4466   HOST_WIDE_INT h;
4467   unsigned HOST_WIDE_INT l;
4468
4469   /* Note that using TYPE_PRECISION here is wrong.  We care about the
4470      actual bits, not the (arbitrary) range of the type.  */
4471   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
4472   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
4473                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
4474   return (l & 1) == 1;
4475 }
4476
4477 /* Return an indication of the sign of the integer constant T.
4478    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
4479    Note that -1 will never be returned if T's type is unsigned.  */
4480
4481 int
4482 tree_int_cst_sgn (tree t)
4483 {
4484   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
4485     return 0;
4486   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
4487     return 1;
4488   else if (TREE_INT_CST_HIGH (t) < 0)
4489     return -1;
4490   else
4491     return 1;
4492 }
4493
4494 /* Compare two constructor-element-type constants.  Return 1 if the lists
4495    are known to be equal; otherwise return 0.  */
4496
4497 int
4498 simple_cst_list_equal (tree l1, tree l2)
4499 {
4500   while (l1 != NULL_TREE && l2 != NULL_TREE)
4501     {
4502       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
4503         return 0;
4504
4505       l1 = TREE_CHAIN (l1);
4506       l2 = TREE_CHAIN (l2);
4507     }
4508
4509   return l1 == l2;
4510 }
4511
4512 /* Return truthvalue of whether T1 is the same tree structure as T2.
4513    Return 1 if they are the same.
4514    Return 0 if they are understandably different.
4515    Return -1 if either contains tree structure not understood by
4516    this function.  */
4517
4518 int
4519 simple_cst_equal (tree t1, tree t2)
4520 {
4521   enum tree_code code1, code2;
4522   int cmp;
4523   int i;
4524
4525   if (t1 == t2)
4526     return 1;
4527   if (t1 == 0 || t2 == 0)
4528     return 0;
4529
4530   code1 = TREE_CODE (t1);
4531   code2 = TREE_CODE (t2);
4532
4533   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
4534     {
4535       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4536           || code2 == NON_LVALUE_EXPR)
4537         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4538       else
4539         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
4540     }
4541
4542   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4543            || code2 == NON_LVALUE_EXPR)
4544     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
4545
4546   if (code1 != code2)
4547     return 0;
4548
4549   switch (code1)
4550     {
4551     case INTEGER_CST:
4552       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4553               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
4554
4555     case REAL_CST:
4556       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
4557
4558     case STRING_CST:
4559       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
4560               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
4561                          TREE_STRING_LENGTH (t1)));
4562
4563     case CONSTRUCTOR:
4564       {
4565         unsigned HOST_WIDE_INT idx;
4566         VEC(constructor_elt, gc) *v1 = CONSTRUCTOR_ELTS (t1);
4567         VEC(constructor_elt, gc) *v2 = CONSTRUCTOR_ELTS (t2);
4568
4569         if (VEC_length (constructor_elt, v1) != VEC_length (constructor_elt, v2))
4570           return false;
4571
4572         for (idx = 0; idx < VEC_length (constructor_elt, v1); ++idx)
4573           /* ??? Should we handle also fields here? */
4574           if (!simple_cst_equal (VEC_index (constructor_elt, v1, idx)->value,
4575                                  VEC_index (constructor_elt, v2, idx)->value))
4576             return false;
4577         return true;
4578       }
4579
4580     case SAVE_EXPR:
4581       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4582
4583     case CALL_EXPR:
4584       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4585       if (cmp <= 0)
4586         return cmp;
4587       return
4588         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4589
4590     case TARGET_EXPR:
4591       /* Special case: if either target is an unallocated VAR_DECL,
4592          it means that it's going to be unified with whatever the
4593          TARGET_EXPR is really supposed to initialize, so treat it
4594          as being equivalent to anything.  */
4595       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
4596            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
4597            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
4598           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
4599               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
4600               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
4601         cmp = 1;
4602       else
4603         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4604
4605       if (cmp <= 0)
4606         return cmp;
4607
4608       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4609
4610     case WITH_CLEANUP_EXPR:
4611       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4612       if (cmp <= 0)
4613         return cmp;
4614
4615       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
4616
4617     case COMPONENT_REF:
4618       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
4619         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4620
4621       return 0;
4622
4623     case VAR_DECL:
4624     case PARM_DECL:
4625     case CONST_DECL:
4626     case FUNCTION_DECL:
4627       return 0;
4628
4629     default:
4630       break;
4631     }
4632
4633   /* This general rule works for most tree codes.  All exceptions should be
4634      handled above.  If this is a language-specific tree code, we can't
4635      trust what might be in the operand, so say we don't know
4636      the situation.  */
4637   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
4638     return -1;
4639
4640   switch (TREE_CODE_CLASS (code1))
4641     {
4642     case tcc_unary:
4643     case tcc_binary:
4644     case tcc_comparison:
4645     case tcc_expression:
4646     case tcc_reference:
4647     case tcc_statement:
4648       cmp = 1;
4649       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
4650         {
4651           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
4652           if (cmp <= 0)
4653             return cmp;
4654         }
4655
4656       return cmp;
4657
4658     default:
4659       return -1;
4660     }
4661 }
4662
4663 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
4664    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
4665    than U, respectively.  */
4666
4667 int
4668 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
4669 {
4670   if (tree_int_cst_sgn (t) < 0)
4671     return -1;
4672   else if (TREE_INT_CST_HIGH (t) != 0)
4673     return 1;
4674   else if (TREE_INT_CST_LOW (t) == u)
4675     return 0;
4676   else if (TREE_INT_CST_LOW (t) < u)
4677     return -1;
4678   else
4679     return 1;
4680 }
4681
4682 /* Return true if CODE represents an associative tree code.  Otherwise
4683    return false.  */
4684 bool
4685 associative_tree_code (enum tree_code code)
4686 {
4687   switch (code)
4688     {
4689     case BIT_IOR_EXPR:
4690     case BIT_AND_EXPR:
4691     case BIT_XOR_EXPR:
4692     case PLUS_EXPR:
4693     case MULT_EXPR:
4694     case MIN_EXPR:
4695     case MAX_EXPR:
4696       return true;
4697
4698     default:
4699       break;
4700     }
4701   return false;
4702 }
4703
4704 /* Return true if CODE represents a commutative tree code.  Otherwise
4705    return false.  */
4706 bool
4707 commutative_tree_code (enum tree_code code)
4708 {
4709   switch (code)
4710     {
4711     case PLUS_EXPR:
4712     case MULT_EXPR:
4713     case MIN_EXPR:
4714     case MAX_EXPR:
4715     case BIT_IOR_EXPR:
4716     case BIT_XOR_EXPR:
4717     case BIT_AND_EXPR:
4718     case NE_EXPR:
4719     case EQ_EXPR:
4720     case UNORDERED_EXPR:
4721     case ORDERED_EXPR:
4722     case UNEQ_EXPR:
4723     case LTGT_EXPR:
4724     case TRUTH_AND_EXPR:
4725     case TRUTH_XOR_EXPR:
4726     case TRUTH_OR_EXPR:
4727       return true;
4728
4729     default:
4730       break;
4731     }
4732   return false;
4733 }
4734
4735 /* Generate a hash value for an expression.  This can be used iteratively
4736    by passing a previous result as the "val" argument.
4737
4738    This function is intended to produce the same hash for expressions which
4739    would compare equal using operand_equal_p.  */
4740
4741 hashval_t
4742 iterative_hash_expr (tree t, hashval_t val)
4743 {
4744   int i;
4745   enum tree_code code;
4746   char class;
4747
4748   if (t == NULL_TREE)
4749     return iterative_hash_pointer (t, val);
4750
4751   code = TREE_CODE (t);
4752
4753   switch (code)
4754     {
4755     /* Alas, constants aren't shared, so we can't rely on pointer
4756        identity.  */
4757     case INTEGER_CST:
4758       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4759       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4760     case REAL_CST:
4761       {
4762         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4763
4764         return iterative_hash_hashval_t (val2, val);
4765       }
4766     case STRING_CST:
4767       return iterative_hash (TREE_STRING_POINTER (t),
4768                              TREE_STRING_LENGTH (t), val);
4769     case COMPLEX_CST:
4770       val = iterative_hash_expr (TREE_REALPART (t), val);
4771       return iterative_hash_expr (TREE_IMAGPART (t), val);
4772     case VECTOR_CST:
4773       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4774
4775     case SSA_NAME:
4776     case VALUE_HANDLE:
4777       /* we can just compare by pointer.  */
4778       return iterative_hash_pointer (t, val);
4779
4780     case TREE_LIST:
4781       /* A list of expressions, for a CALL_EXPR or as the elements of a
4782          VECTOR_CST.  */
4783       for (; t; t = TREE_CHAIN (t))
4784         val = iterative_hash_expr (TREE_VALUE (t), val);
4785       return val;
4786     case CONSTRUCTOR:
4787       {
4788         unsigned HOST_WIDE_INT idx;
4789         tree field, value;
4790         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value)
4791           {
4792             val = iterative_hash_expr (field, val);
4793             val = iterative_hash_expr (value, val);
4794           }
4795         return val;
4796       }
4797     case FUNCTION_DECL:
4798       /* When referring to a built-in FUNCTION_DECL, use the
4799          __builtin__ form.  Otherwise nodes that compare equal
4800          according to operand_equal_p might get different
4801          hash codes.  */
4802       if (DECL_BUILT_IN (t))
4803         {
4804           val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)],
4805                                       val);
4806           return val;
4807         }
4808       /* else FALL THROUGH */
4809     default:
4810       class = TREE_CODE_CLASS (code);
4811
4812       if (class == tcc_declaration)
4813         {
4814           /* DECL's have a unique ID */
4815           val = iterative_hash_host_wide_int (DECL_UID (t), val);
4816         }
4817       else
4818         {
4819           gcc_assert (IS_EXPR_CODE_CLASS (class));
4820
4821           val = iterative_hash_object (code, val);
4822
4823           /* Don't hash the type, that can lead to having nodes which
4824              compare equal according to operand_equal_p, but which
4825              have different hash codes.  */
4826           if (code == NOP_EXPR
4827               || code == CONVERT_EXPR
4828               || code == NON_LVALUE_EXPR)
4829             {
4830               /* Make sure to include signness in the hash computation.  */
4831               val += TYPE_UNSIGNED (TREE_TYPE (t));
4832               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4833             }
4834
4835           else if (commutative_tree_code (code))
4836             {
4837               /* It's a commutative expression.  We want to hash it the same
4838                  however it appears.  We do this by first hashing both operands
4839                  and then rehashing based on the order of their independent
4840                  hashes.  */
4841               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4842               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4843               hashval_t t;
4844
4845               if (one > two)
4846                 t = one, one = two, two = t;
4847
4848               val = iterative_hash_hashval_t (one, val);
4849               val = iterative_hash_hashval_t (two, val);
4850             }
4851           else
4852             for (i = TREE_CODE_LENGTH (code) - 1; i >= 0; --i)
4853               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4854         }
4855       return val;
4856       break;
4857     }
4858 }
4859 \f
4860 /* Constructors for pointer, array and function types.
4861    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4862    constructed by language-dependent code, not here.)  */
4863
4864 /* Construct, lay out and return the type of pointers to TO_TYPE with
4865    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4866    reference all of memory. If such a type has already been
4867    constructed, reuse it.  */
4868
4869 tree
4870 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4871                              bool can_alias_all)
4872 {
4873   tree t;
4874
4875   if (to_type == error_mark_node)
4876     return error_mark_node;
4877
4878   /* In some cases, languages will have things that aren't a POINTER_TYPE
4879      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4880      In that case, return that type without regard to the rest of our
4881      operands.
4882
4883      ??? This is a kludge, but consistent with the way this function has
4884      always operated and there doesn't seem to be a good way to avoid this
4885      at the moment.  */
4886   if (TYPE_POINTER_TO (to_type) != 0
4887       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4888     return TYPE_POINTER_TO (to_type);
4889
4890   /* First, if we already have a type for pointers to TO_TYPE and it's
4891      the proper mode, use it.  */
4892   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4893     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4894       return t;
4895
4896   t = make_node (POINTER_TYPE);
4897
4898   TREE_TYPE (t) = to_type;
4899   TYPE_MODE (t) = mode;
4900   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4901   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4902   TYPE_POINTER_TO (to_type) = t;
4903
4904   /* Lay out the type.  This function has many callers that are concerned
4905      with expression-construction, and this simplifies them all.  */
4906   layout_type (t);
4907
4908   return t;
4909 }
4910
4911 /* By default build pointers in ptr_mode.  */
4912
4913 tree
4914 build_pointer_type (tree to_type)
4915 {
4916   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4917 }
4918
4919 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4920
4921 tree
4922 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4923                                bool can_alias_all)
4924 {
4925   tree t;
4926
4927   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4928      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4929      In that case, return that type without regard to the rest of our
4930      operands.
4931
4932      ??? This is a kludge, but consistent with the way this function has
4933      always operated and there doesn't seem to be a good way to avoid this
4934      at the moment.  */
4935   if (TYPE_REFERENCE_TO (to_type) != 0
4936       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4937     return TYPE_REFERENCE_TO (to_type);
4938
4939   /* First, if we already have a type for pointers to TO_TYPE and it's
4940      the proper mode, use it.  */
4941   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4942     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4943       return t;
4944
4945   t = make_node (REFERENCE_TYPE);
4946
4947   TREE_TYPE (t) = to_type;
4948   TYPE_MODE (t) = mode;
4949   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4950   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4951   TYPE_REFERENCE_TO (to_type) = t;
4952
4953   layout_type (t);
4954
4955   return t;
4956 }
4957
4958
4959 /* Build the node for the type of references-to-TO_TYPE by default
4960    in ptr_mode.  */
4961
4962 tree
4963 build_reference_type (tree to_type)
4964 {
4965   return build_reference_type_for_mode (to_type, ptr_mode, false);
4966 }
4967
4968 /* Build a type that is compatible with t but has no cv quals anywhere
4969    in its type, thus
4970
4971    const char *const *const *  ->  char ***.  */
4972
4973 tree
4974 build_type_no_quals (tree t)
4975 {
4976   switch (TREE_CODE (t))
4977     {
4978     case POINTER_TYPE:
4979       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4980                                           TYPE_MODE (t),
4981                                           TYPE_REF_CAN_ALIAS_ALL (t));
4982     case REFERENCE_TYPE:
4983       return
4984         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4985                                        TYPE_MODE (t),
4986                                        TYPE_REF_CAN_ALIAS_ALL (t));
4987     default:
4988       return TYPE_MAIN_VARIANT (t);
4989     }
4990 }
4991
4992 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4993    MAXVAL should be the maximum value in the domain
4994    (one less than the length of the array).
4995
4996    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4997    We don't enforce this limit, that is up to caller (e.g. language front end).
4998    The limit exists because the result is a signed type and we don't handle
4999    sizes that use more than one HOST_WIDE_INT.  */
5000
5001 tree
5002 build_index_type (tree maxval)
5003 {
5004   tree itype = make_node (INTEGER_TYPE);
5005
5006   TREE_TYPE (itype) = sizetype;
5007   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
5008   TYPE_MIN_VALUE (itype) = size_zero_node;
5009   TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
5010   TYPE_MODE (itype) = TYPE_MODE (sizetype);
5011   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
5012   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
5013   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
5014   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
5015
5016   if (host_integerp (maxval, 1))
5017     return type_hash_canon (tree_low_cst (maxval, 1), itype);
5018   else
5019     return itype;
5020 }
5021
5022 /* Builds a signed or unsigned integer type of precision PRECISION.
5023    Used for C bitfields whose precision does not match that of
5024    built-in target types.  */
5025 tree
5026 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
5027                                 int unsignedp)
5028 {
5029   tree itype = make_node (INTEGER_TYPE);
5030
5031   TYPE_PRECISION (itype) = precision;
5032
5033   if (unsignedp)
5034     fixup_unsigned_type (itype);
5035   else
5036     fixup_signed_type (itype);
5037
5038   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
5039     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
5040
5041   return itype;
5042 }
5043
5044 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
5045    ENUMERAL_TYPE or BOOLEAN_TYPE), with low bound LOWVAL and
5046    high bound HIGHVAL.  If TYPE is NULL, sizetype is used.  */
5047
5048 tree
5049 build_range_type (tree type, tree lowval, tree highval)
5050 {
5051   tree itype = make_node (INTEGER_TYPE);
5052
5053   TREE_TYPE (itype) = type;
5054   if (type == NULL_TREE)
5055     type = sizetype;
5056
5057   TYPE_MIN_VALUE (itype) = fold_convert (type, lowval);
5058   TYPE_MAX_VALUE (itype) = highval ? fold_convert (type, highval) : NULL;
5059
5060   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
5061   TYPE_MODE (itype) = TYPE_MODE (type);
5062   TYPE_SIZE (itype) = TYPE_SIZE (type);
5063   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
5064   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
5065   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
5066
5067   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
5068     return type_hash_canon (tree_low_cst (highval, 0)
5069                             - tree_low_cst (lowval, 0),
5070                             itype);
5071   else
5072     return itype;
5073 }
5074
5075 /* Just like build_index_type, but takes lowval and highval instead
5076    of just highval (maxval).  */
5077
5078 tree
5079 build_index_2_type (tree lowval, tree highval)
5080 {
5081   return build_range_type (sizetype, lowval, highval);
5082 }
5083
5084 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
5085    and number of elements specified by the range of values of INDEX_TYPE.
5086    If such a type has already been constructed, reuse it.  */
5087
5088 tree
5089 build_array_type (tree elt_type, tree index_type)
5090 {
5091   tree t;
5092   hashval_t hashcode = 0;
5093
5094   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
5095     {
5096       error ("arrays of functions are not meaningful");
5097       elt_type = integer_type_node;
5098     }
5099
5100   t = make_node (ARRAY_TYPE);
5101   TREE_TYPE (t) = elt_type;
5102   TYPE_DOMAIN (t) = index_type;
5103
5104   if (index_type == 0)
5105     {
5106       layout_type (t);
5107       return t;
5108     }
5109
5110   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
5111   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
5112   t = type_hash_canon (hashcode, t);
5113
5114   if (!COMPLETE_TYPE_P (t))
5115     layout_type (t);
5116   return t;
5117 }
5118
5119 /* Return the TYPE of the elements comprising
5120    the innermost dimension of ARRAY.  */
5121
5122 tree
5123 get_inner_array_type (tree array)
5124 {
5125   tree type = TREE_TYPE (array);
5126
5127   while (TREE_CODE (type) == ARRAY_TYPE)
5128     type = TREE_TYPE (type);
5129
5130   return type;
5131 }
5132
5133 /* Construct, lay out and return
5134    the type of functions returning type VALUE_TYPE
5135    given arguments of types ARG_TYPES.
5136    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
5137    are data type nodes for the arguments of the function.
5138    If such a type has already been constructed, reuse it.  */
5139
5140 tree
5141 build_function_type (tree value_type, tree arg_types)
5142 {
5143   tree t;
5144   hashval_t hashcode = 0;
5145
5146   if (TREE_CODE (value_type) == FUNCTION_TYPE)
5147     {
5148       error ("function return type cannot be function");
5149       value_type = integer_type_node;
5150     }
5151
5152   /* Make a node of the sort we want.  */
5153   t = make_node (FUNCTION_TYPE);
5154   TREE_TYPE (t) = value_type;
5155   TYPE_ARG_TYPES (t) = arg_types;
5156
5157   /* If we already have such a type, use the old one.  */
5158   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
5159   hashcode = type_hash_list (arg_types, hashcode);
5160   t = type_hash_canon (hashcode, t);
5161
5162   if (!COMPLETE_TYPE_P (t))
5163     layout_type (t);
5164   return t;
5165 }
5166
5167 /* Build a function type.  The RETURN_TYPE is the type returned by the
5168    function.  If additional arguments are provided, they are
5169    additional argument types.  The list of argument types must always
5170    be terminated by NULL_TREE.  */
5171
5172 tree
5173 build_function_type_list (tree return_type, ...)
5174 {
5175   tree t, args, last;
5176   va_list p;
5177
5178   va_start (p, return_type);
5179
5180   t = va_arg (p, tree);
5181   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
5182     args = tree_cons (NULL_TREE, t, args);
5183
5184   if (args == NULL_TREE)
5185     args = void_list_node;
5186   else
5187     {
5188       last = args;
5189       args = nreverse (args);
5190       TREE_CHAIN (last) = void_list_node;
5191     }
5192   args = build_function_type (return_type, args);
5193
5194   va_end (p);
5195   return args;
5196 }
5197
5198 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
5199    and ARGTYPES (a TREE_LIST) are the return type and arguments types
5200    for the method.  An implicit additional parameter (of type
5201    pointer-to-BASETYPE) is added to the ARGTYPES.  */
5202
5203 tree
5204 build_method_type_directly (tree basetype,
5205                             tree rettype,
5206                             tree argtypes)
5207 {
5208   tree t;
5209   tree ptype;
5210   int hashcode = 0;
5211
5212   /* Make a node of the sort we want.  */
5213   t = make_node (METHOD_TYPE);
5214
5215   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5216   TREE_TYPE (t) = rettype;
5217   ptype = build_pointer_type (basetype);
5218
5219   /* The actual arglist for this function includes a "hidden" argument
5220      which is "this".  Put it into the list of argument types.  */
5221   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
5222   TYPE_ARG_TYPES (t) = argtypes;
5223
5224   /* If we already have such a type, use the old one.  */
5225   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5226   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
5227   hashcode = type_hash_list (argtypes, hashcode);
5228   t = type_hash_canon (hashcode, t);
5229
5230   if (!COMPLETE_TYPE_P (t))
5231     layout_type (t);
5232
5233   return t;
5234 }
5235
5236 /* Construct, lay out and return the type of methods belonging to class
5237    BASETYPE and whose arguments and values are described by TYPE.
5238    If that type exists already, reuse it.
5239    TYPE must be a FUNCTION_TYPE node.  */
5240
5241 tree
5242 build_method_type (tree basetype, tree type)
5243 {
5244   gcc_assert (TREE_CODE (type) == FUNCTION_TYPE);
5245
5246   return build_method_type_directly (basetype,
5247                                      TREE_TYPE (type),
5248                                      TYPE_ARG_TYPES (type));
5249 }
5250
5251 /* Construct, lay out and return the type of offsets to a value
5252    of type TYPE, within an object of type BASETYPE.
5253    If a suitable offset type exists already, reuse it.  */
5254
5255 tree
5256 build_offset_type (tree basetype, tree type)
5257 {
5258   tree t;
5259   hashval_t hashcode = 0;
5260
5261   /* Make a node of the sort we want.  */
5262   t = make_node (OFFSET_TYPE);
5263
5264   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5265   TREE_TYPE (t) = type;
5266
5267   /* If we already have such a type, use the old one.  */
5268   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5269   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
5270   t = type_hash_canon (hashcode, t);
5271
5272   if (!COMPLETE_TYPE_P (t))
5273     layout_type (t);
5274
5275   return t;
5276 }
5277
5278 /* Create a complex type whose components are COMPONENT_TYPE.  */
5279
5280 tree
5281 build_complex_type (tree component_type)
5282 {
5283   tree t;
5284   hashval_t hashcode;
5285
5286   /* Make a node of the sort we want.  */
5287   t = make_node (COMPLEX_TYPE);
5288
5289   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
5290
5291   /* If we already have such a type, use the old one.  */
5292   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
5293   t = type_hash_canon (hashcode, t);
5294
5295   if (!COMPLETE_TYPE_P (t))
5296     layout_type (t);
5297
5298   /* If we are writing Dwarf2 output we need to create a name,
5299      since complex is a fundamental type.  */
5300   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
5301       && ! TYPE_NAME (t))
5302     {
5303       const char *name;
5304       if (component_type == char_type_node)
5305         name = "complex char";
5306       else if (component_type == signed_char_type_node)
5307         name = "complex signed char";
5308       else if (component_type == unsigned_char_type_node)
5309         name = "complex unsigned char";
5310       else if (component_type == short_integer_type_node)
5311         name = "complex short int";
5312       else if (component_type == short_unsigned_type_node)
5313         name = "complex short unsigned int";
5314       else if (component_type == integer_type_node)
5315         name = "complex int";
5316       else if (component_type == unsigned_type_node)
5317         name = "complex unsigned int";
5318       else if (component_type == long_integer_type_node)
5319         name = "complex long int";
5320       else if (component_type == long_unsigned_type_node)
5321         name = "complex long unsigned int";
5322       else if (component_type == long_long_integer_type_node)
5323         name = "complex long long int";
5324       else if (component_type == long_long_unsigned_type_node)
5325         name = "complex long long unsigned int";
5326       else
5327         name = 0;
5328
5329       if (name != 0)
5330         TYPE_NAME (t) = get_identifier (name);
5331     }
5332
5333   return build_qualified_type (t, TYPE_QUALS (component_type));
5334 }
5335 \f
5336 /* Return OP, stripped of any conversions to wider types as much as is safe.
5337    Converting the value back to OP's type makes a value equivalent to OP.
5338
5339    If FOR_TYPE is nonzero, we return a value which, if converted to
5340    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
5341
5342    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
5343    narrowest type that can hold the value, even if they don't exactly fit.
5344    Otherwise, bit-field references are changed to a narrower type
5345    only if they can be fetched directly from memory in that type.
5346
5347    OP must have integer, real or enumeral type.  Pointers are not allowed!
5348
5349    There are some cases where the obvious value we could return
5350    would regenerate to OP if converted to OP's type,
5351    but would not extend like OP to wider types.
5352    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
5353    For example, if OP is (unsigned short)(signed char)-1,
5354    we avoid returning (signed char)-1 if FOR_TYPE is int,
5355    even though extending that to an unsigned short would regenerate OP,
5356    since the result of extending (signed char)-1 to (int)
5357    is different from (int) OP.  */
5358
5359 tree
5360 get_unwidened (tree op, tree for_type)
5361 {
5362   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
5363   tree type = TREE_TYPE (op);
5364   unsigned final_prec
5365     = TYPE_PRECISION (for_type != 0 ? for_type : type);
5366   int uns
5367     = (for_type != 0 && for_type != type
5368        && final_prec > TYPE_PRECISION (type)
5369        && TYPE_UNSIGNED (type));
5370   tree win = op;
5371
5372   while (TREE_CODE (op) == NOP_EXPR
5373          || TREE_CODE (op) == CONVERT_EXPR)
5374     {
5375       int bitschange;
5376
5377       /* TYPE_PRECISION on vector types has different meaning
5378          (TYPE_VECTOR_SUBPARTS) and casts from vectors are view conversions,
5379          so avoid them here.  */
5380       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == VECTOR_TYPE)
5381         break;
5382
5383       bitschange = TYPE_PRECISION (TREE_TYPE (op))
5384                    - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
5385
5386       /* Truncations are many-one so cannot be removed.
5387          Unless we are later going to truncate down even farther.  */
5388       if (bitschange < 0
5389           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
5390         break;
5391
5392       /* See what's inside this conversion.  If we decide to strip it,
5393          we will set WIN.  */
5394       op = TREE_OPERAND (op, 0);
5395
5396       /* If we have not stripped any zero-extensions (uns is 0),
5397          we can strip any kind of extension.
5398          If we have previously stripped a zero-extension,
5399          only zero-extensions can safely be stripped.
5400          Any extension can be stripped if the bits it would produce
5401          are all going to be discarded later by truncating to FOR_TYPE.  */
5402
5403       if (bitschange > 0)
5404         {
5405           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
5406             win = op;
5407           /* TYPE_UNSIGNED says whether this is a zero-extension.
5408              Let's avoid computing it if it does not affect WIN
5409              and if UNS will not be needed again.  */
5410           if ((uns
5411                || TREE_CODE (op) == NOP_EXPR
5412                || TREE_CODE (op) == CONVERT_EXPR)
5413               && TYPE_UNSIGNED (TREE_TYPE (op)))
5414             {
5415               uns = 1;
5416               win = op;
5417             }
5418         }
5419     }
5420
5421   if (TREE_CODE (op) == COMPONENT_REF
5422       /* Since type_for_size always gives an integer type.  */
5423       && TREE_CODE (type) != REAL_TYPE
5424       /* Don't crash if field not laid out yet.  */
5425       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5426       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5427     {
5428       unsigned int innerprec
5429         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5430       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5431                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5432       type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5433
5434       /* We can get this structure field in the narrowest type it fits in.
5435          If FOR_TYPE is 0, do this only for a field that matches the
5436          narrower type exactly and is aligned for it
5437          The resulting extension to its nominal type (a fullword type)
5438          must fit the same conditions as for other extensions.  */
5439
5440       if (type != 0
5441           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
5442           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
5443           && (! uns || final_prec <= innerprec || unsignedp))
5444         {
5445           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5446                         TREE_OPERAND (op, 1), NULL_TREE);
5447           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5448           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5449         }
5450     }
5451
5452   return win;
5453 }
5454 \f
5455 /* Return OP or a simpler expression for a narrower value
5456    which can be sign-extended or zero-extended to give back OP.
5457    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
5458    or 0 if the value should be sign-extended.  */
5459
5460 tree
5461 get_narrower (tree op, int *unsignedp_ptr)
5462 {
5463   int uns = 0;
5464   int first = 1;
5465   tree win = op;
5466   bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op));
5467
5468   while (TREE_CODE (op) == NOP_EXPR)
5469     {
5470       int bitschange
5471         = (TYPE_PRECISION (TREE_TYPE (op))
5472            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
5473
5474       /* Truncations are many-one so cannot be removed.  */
5475       if (bitschange < 0)
5476         break;
5477
5478       /* See what's inside this conversion.  If we decide to strip it,
5479          we will set WIN.  */
5480
5481       if (bitschange > 0)
5482         {
5483           op = TREE_OPERAND (op, 0);
5484           /* An extension: the outermost one can be stripped,
5485              but remember whether it is zero or sign extension.  */
5486           if (first)
5487             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5488           /* Otherwise, if a sign extension has been stripped,
5489              only sign extensions can now be stripped;
5490              if a zero extension has been stripped, only zero-extensions.  */
5491           else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
5492             break;
5493           first = 0;
5494         }
5495       else /* bitschange == 0 */
5496         {
5497           /* A change in nominal type can always be stripped, but we must
5498              preserve the unsignedness.  */
5499           if (first)
5500             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5501           first = 0;
5502           op = TREE_OPERAND (op, 0);
5503           /* Keep trying to narrow, but don't assign op to win if it
5504              would turn an integral type into something else.  */
5505           if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p)
5506             continue;
5507         }
5508
5509       win = op;
5510     }
5511
5512   if (TREE_CODE (op) == COMPONENT_REF
5513       /* Since type_for_size always gives an integer type.  */
5514       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
5515       /* Ensure field is laid out already.  */
5516       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5517       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5518     {
5519       unsigned HOST_WIDE_INT innerprec
5520         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5521       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5522                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5523       tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5524
5525       /* We can get this structure field in a narrower type that fits it,
5526          but the resulting extension to its nominal type (a fullword type)
5527          must satisfy the same conditions as for other extensions.
5528
5529          Do this only for fields that are aligned (not bit-fields),
5530          because when bit-field insns will be used there is no
5531          advantage in doing this.  */
5532
5533       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
5534           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
5535           && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
5536           && type != 0)
5537         {
5538           if (first)
5539             uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
5540           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5541                         TREE_OPERAND (op, 1), NULL_TREE);
5542           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5543           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5544         }
5545     }
5546   *unsignedp_ptr = uns;
5547   return win;
5548 }
5549 \f
5550 /* Nonzero if integer constant C has a value that is permissible
5551    for type TYPE (an INTEGER_TYPE).  */
5552
5553 int
5554 int_fits_type_p (tree c, tree type)
5555 {
5556   tree type_low_bound = TYPE_MIN_VALUE (type);
5557   tree type_high_bound = TYPE_MAX_VALUE (type);
5558   bool ok_for_low_bound, ok_for_high_bound;
5559   tree tmp;
5560
5561   /* If at least one bound of the type is a constant integer, we can check
5562      ourselves and maybe make a decision. If no such decision is possible, but
5563      this type is a subtype, try checking against that.  Otherwise, use
5564      force_fit_type, which checks against the precision.
5565
5566      Compute the status for each possibly constant bound, and return if we see
5567      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
5568      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
5569      for "constant known to fit".  */
5570
5571   /* Check if C >= type_low_bound.  */
5572   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
5573     {
5574       if (tree_int_cst_lt (c, type_low_bound))
5575         return 0;
5576       ok_for_low_bound = true;
5577     }
5578   else
5579     ok_for_low_bound = false;
5580
5581   /* Check if c <= type_high_bound.  */
5582   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
5583     {
5584       if (tree_int_cst_lt (type_high_bound, c))
5585         return 0;
5586       ok_for_high_bound = true;
5587     }
5588   else
5589     ok_for_high_bound = false;
5590
5591   /* If the constant fits both bounds, the result is known.  */
5592   if (ok_for_low_bound && ok_for_high_bound)
5593     return 1;
5594
5595   /* Perform some generic filtering which may allow making a decision
5596      even if the bounds are not constant.  First, negative integers
5597      never fit in unsigned types, */
5598   if (TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
5599     return 0;
5600
5601   /* Second, narrower types always fit in wider ones.  */
5602   if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (c)))
5603     return 1;
5604
5605   /* Third, unsigned integers with top bit set never fit signed types.  */
5606   if (! TYPE_UNSIGNED (type)
5607       && TYPE_UNSIGNED (TREE_TYPE (c))
5608       && tree_int_cst_msb (c))
5609     return 0;
5610
5611   /* If we haven't been able to decide at this point, there nothing more we
5612      can check ourselves here.  Look at the base type if we have one and it
5613      has the same precision.  */
5614   if (TREE_CODE (type) == INTEGER_TYPE
5615       && TREE_TYPE (type) != 0
5616       && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (type)))
5617     return int_fits_type_p (c, TREE_TYPE (type));
5618
5619   /* Or to force_fit_type, if nothing else.  */
5620   tmp = copy_node (c);
5621   TREE_TYPE (tmp) = type;
5622   tmp = force_fit_type (tmp, -1, false, false);
5623   return TREE_INT_CST_HIGH (tmp) == TREE_INT_CST_HIGH (c)
5624          && TREE_INT_CST_LOW (tmp) == TREE_INT_CST_LOW (c);
5625 }
5626
5627 /* Subprogram of following function.  Called by walk_tree.
5628
5629    Return *TP if it is an automatic variable or parameter of the
5630    function passed in as DATA.  */
5631
5632 static tree
5633 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
5634 {
5635   tree fn = (tree) data;
5636
5637   if (TYPE_P (*tp))
5638     *walk_subtrees = 0;
5639
5640   else if (DECL_P (*tp)
5641            && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
5642     return *tp;
5643
5644   return NULL_TREE;
5645 }
5646
5647 /* Returns true if T is, contains, or refers to a type with variable
5648    size.  For METHOD_TYPEs and FUNCTION_TYPEs we exclude the
5649    arguments, but not the return type.  If FN is nonzero, only return
5650    true if a modifier of the type or position of FN is a variable or
5651    parameter inside FN.
5652
5653    This concept is more general than that of C99 'variably modified types':
5654    in C99, a struct type is never variably modified because a VLA may not
5655    appear as a structure member.  However, in GNU C code like:
5656
5657      struct S { int i[f()]; };
5658
5659    is valid, and other languages may define similar constructs.  */
5660
5661 bool
5662 variably_modified_type_p (tree type, tree fn)
5663 {
5664   tree t;
5665
5666 /* Test if T is either variable (if FN is zero) or an expression containing
5667    a variable in FN.  */
5668 #define RETURN_TRUE_IF_VAR(T)                                           \
5669   do { tree _t = (T);                                                   \
5670     if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST    \
5671         && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL)))        \
5672       return true;  } while (0)
5673
5674   if (type == error_mark_node)
5675     return false;
5676
5677   /* If TYPE itself has variable size, it is variably modified.  */
5678   RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
5679   RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (type));
5680
5681   switch (TREE_CODE (type))
5682     {
5683     case POINTER_TYPE:
5684     case REFERENCE_TYPE:
5685     case VECTOR_TYPE:
5686       if (variably_modified_type_p (TREE_TYPE (type), fn))
5687         return true;
5688       break;
5689
5690     case FUNCTION_TYPE:
5691     case METHOD_TYPE:
5692       /* If TYPE is a function type, it is variably modified if the
5693          return type is variably modified.  */
5694       if (variably_modified_type_p (TREE_TYPE (type), fn))
5695           return true;
5696       break;
5697
5698     case INTEGER_TYPE:
5699     case REAL_TYPE:
5700     case ENUMERAL_TYPE:
5701     case BOOLEAN_TYPE:
5702       /* Scalar types are variably modified if their end points
5703          aren't constant.  */
5704       RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
5705       RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
5706       break;
5707
5708     case RECORD_TYPE:
5709     case UNION_TYPE:
5710     case QUAL_UNION_TYPE:
5711       /* We can't see if any of the fields are variably-modified by the
5712          definition we normally use, since that would produce infinite
5713          recursion via pointers.  */
5714       /* This is variably modified if some field's type is.  */
5715       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
5716         if (TREE_CODE (t) == FIELD_DECL)
5717           {
5718             RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
5719             RETURN_TRUE_IF_VAR (DECL_SIZE (t));
5720             RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
5721
5722             if (TREE_CODE (type) == QUAL_UNION_TYPE)
5723               RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
5724           }
5725         break;
5726
5727     case ARRAY_TYPE:
5728       /* Do not call ourselves to avoid infinite recursion.  This is
5729          variably modified if the element type is.  */
5730       RETURN_TRUE_IF_VAR (TYPE_SIZE (TREE_TYPE (type)));
5731       RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT (TREE_TYPE (type)));
5732       break;
5733
5734     default:
5735       break;
5736     }
5737
5738   /* The current language may have other cases to check, but in general,
5739      all other types are not variably modified.  */
5740   return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
5741
5742 #undef RETURN_TRUE_IF_VAR
5743 }
5744
5745 /* Given a DECL or TYPE, return the scope in which it was declared, or
5746    NULL_TREE if there is no containing scope.  */
5747
5748 tree
5749 get_containing_scope (tree t)
5750 {
5751   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
5752 }
5753
5754 /* Return the innermost context enclosing DECL that is
5755    a FUNCTION_DECL, or zero if none.  */
5756
5757 tree
5758 decl_function_context (tree decl)
5759 {
5760   tree context;
5761
5762   if (TREE_CODE (decl) == ERROR_MARK)
5763     return 0;
5764
5765   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
5766      where we look up the function at runtime.  Such functions always take
5767      a first argument of type 'pointer to real context'.
5768
5769      C++ should really be fixed to use DECL_CONTEXT for the real context,
5770      and use something else for the "virtual context".  */
5771   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
5772     context
5773       = TYPE_MAIN_VARIANT
5774         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
5775   else
5776     context = DECL_CONTEXT (decl);
5777
5778   while (context && TREE_CODE (context) != FUNCTION_DECL)
5779     {
5780       if (TREE_CODE (context) == BLOCK)
5781         context = BLOCK_SUPERCONTEXT (context);
5782       else
5783         context = get_containing_scope (context);
5784     }
5785
5786   return context;
5787 }
5788
5789 /* Return the innermost context enclosing DECL that is
5790    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5791    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
5792
5793 tree
5794 decl_type_context (tree decl)
5795 {
5796   tree context = DECL_CONTEXT (decl);
5797
5798   while (context)
5799     switch (TREE_CODE (context))
5800       {
5801       case NAMESPACE_DECL:
5802       case TRANSLATION_UNIT_DECL:
5803         return NULL_TREE;
5804
5805       case RECORD_TYPE:
5806       case UNION_TYPE:
5807       case QUAL_UNION_TYPE:
5808         return context;
5809
5810       case TYPE_DECL:
5811       case FUNCTION_DECL:
5812         context = DECL_CONTEXT (context);
5813         break;
5814
5815       case BLOCK:
5816         context = BLOCK_SUPERCONTEXT (context);
5817         break;
5818
5819       default:
5820         gcc_unreachable ();
5821       }
5822
5823   return NULL_TREE;
5824 }
5825
5826 /* CALL is a CALL_EXPR.  Return the declaration for the function
5827    called, or NULL_TREE if the called function cannot be
5828    determined.  */
5829
5830 tree
5831 get_callee_fndecl (tree call)
5832 {
5833   tree addr;
5834
5835   if (call == error_mark_node)
5836     return call;
5837
5838   /* It's invalid to call this function with anything but a
5839      CALL_EXPR.  */
5840   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5841
5842   /* The first operand to the CALL is the address of the function
5843      called.  */
5844   addr = TREE_OPERAND (call, 0);
5845
5846   STRIP_NOPS (addr);
5847
5848   /* If this is a readonly function pointer, extract its initial value.  */
5849   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5850       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5851       && DECL_INITIAL (addr))
5852     addr = DECL_INITIAL (addr);
5853
5854   /* If the address is just `&f' for some function `f', then we know
5855      that `f' is being called.  */
5856   if (TREE_CODE (addr) == ADDR_EXPR
5857       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5858     return TREE_OPERAND (addr, 0);
5859
5860   /* We couldn't figure out what was being called.  Maybe the front
5861      end has some idea.  */
5862   return lang_hooks.lang_get_callee_fndecl (call);
5863 }
5864
5865 /* Print debugging information about tree nodes generated during the compile,
5866    and any language-specific information.  */
5867
5868 void
5869 dump_tree_statistics (void)
5870 {
5871 #ifdef GATHER_STATISTICS
5872   int i;
5873   int total_nodes, total_bytes;
5874 #endif
5875
5876   fprintf (stderr, "\n??? tree nodes created\n\n");
5877 #ifdef GATHER_STATISTICS
5878   fprintf (stderr, "Kind                   Nodes      Bytes\n");
5879   fprintf (stderr, "---------------------------------------\n");
5880   total_nodes = total_bytes = 0;
5881   for (i = 0; i < (int) all_kinds; i++)
5882     {
5883       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5884                tree_node_counts[i], tree_node_sizes[i]);
5885       total_nodes += tree_node_counts[i];
5886       total_bytes += tree_node_sizes[i];
5887     }
5888   fprintf (stderr, "---------------------------------------\n");
5889   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5890   fprintf (stderr, "---------------------------------------\n");
5891   ssanames_print_statistics ();
5892   phinodes_print_statistics ();
5893 #else
5894   fprintf (stderr, "(No per-node statistics)\n");
5895 #endif
5896   print_type_hash_statistics ();
5897   print_debug_expr_statistics ();
5898   print_value_expr_statistics ();
5899   print_restrict_base_statistics ();
5900   lang_hooks.print_statistics ();
5901 }
5902 \f
5903 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
5904
5905 /* Generate a crc32 of a string.  */
5906
5907 unsigned
5908 crc32_string (unsigned chksum, const char *string)
5909 {
5910   do
5911     {
5912       unsigned value = *string << 24;
5913       unsigned ix;
5914
5915       for (ix = 8; ix--; value <<= 1)
5916         {
5917           unsigned feedback;
5918
5919           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
5920           chksum <<= 1;
5921           chksum ^= feedback;
5922         }
5923     }
5924   while (*string++);
5925   return chksum;
5926 }
5927
5928 /* P is a string that will be used in a symbol.  Mask out any characters
5929    that are not valid in that context.  */
5930
5931 void
5932 clean_symbol_name (char *p)
5933 {
5934   for (; *p; p++)
5935     if (! (ISALNUM (*p)
5936 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
5937             || *p == '$'
5938 #endif
5939 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
5940             || *p == '.'
5941 #endif
5942            ))
5943       *p = '_';
5944 }
5945
5946 /* Generate a name for a function unique to this translation unit.
5947    TYPE is some string to identify the purpose of this function to the
5948    linker or collect2.  */
5949
5950 tree
5951 get_file_function_name_long (const char *type)
5952 {
5953   char *buf;
5954   const char *p;
5955   char *q;
5956
5957   if (first_global_object_name)
5958     {
5959       p = first_global_object_name;
5960
5961       /* For type 'F', the generated name must be unique not only to this
5962          translation unit but also to any given link.  Since global names
5963          can be overloaded, we concatenate the first global object name
5964          with a string derived from the file name of this object.  */
5965       if (!strcmp (type, "F"))
5966         {
5967           const char *file = main_input_filename;
5968
5969           if (! file)
5970             file = input_filename;
5971
5972           q = alloca (strlen (p) + 10);
5973           sprintf (q, "%s_%08X", p, crc32_string (0, file));
5974
5975           p = q;
5976         }
5977     }
5978   else
5979     {
5980       /* We don't have anything that we know to be unique to this translation
5981          unit, so use what we do have and throw in some randomness.  */
5982       unsigned len;
5983       const char *name = weak_global_object_name;
5984       const char *file = main_input_filename;
5985
5986       if (! name)
5987         name = "";
5988       if (! file)
5989         file = input_filename;
5990
5991       len = strlen (file);
5992       q = alloca (9 * 2 + len + 1);
5993       memcpy (q, file, len + 1);
5994       clean_symbol_name (q);
5995
5996       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
5997                crc32_string (0, flag_random_seed));
5998
5999       p = q;
6000     }
6001
6002   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
6003
6004   /* Set up the name of the file-level functions we may need.
6005      Use a global object (which is already required to be unique over
6006      the program) rather than the file name (which imposes extra
6007      constraints).  */
6008   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
6009
6010   return get_identifier (buf);
6011 }
6012
6013 /* If KIND=='I', return a suitable global initializer (constructor) name.
6014    If KIND=='D', return a suitable global clean-up (destructor) name.  */
6015
6016 tree
6017 get_file_function_name (int kind)
6018 {
6019   char p[2];
6020
6021   p[0] = kind;
6022   p[1] = 0;
6023
6024   return get_file_function_name_long (p);
6025 }
6026 \f
6027 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
6028
6029 /* Complain that the tree code of NODE does not match the expected 0
6030    terminated list of trailing codes. The trailing code list can be
6031    empty, for a more vague error message.  FILE, LINE, and FUNCTION
6032    are of the caller.  */
6033
6034 void
6035 tree_check_failed (const tree node, const char *file,
6036                    int line, const char *function, ...)
6037 {
6038   va_list args;
6039   char *buffer;
6040   unsigned length = 0;
6041   int code;
6042
6043   va_start (args, function);
6044   while ((code = va_arg (args, int)))
6045     length += 4 + strlen (tree_code_name[code]);
6046   va_end (args);
6047   if (length)
6048     {
6049       va_start (args, function);
6050       length += strlen ("expected ");
6051       buffer = alloca (length);
6052       length = 0;
6053       while ((code = va_arg (args, int)))
6054         {
6055           const char *prefix = length ? " or " : "expected ";
6056
6057           strcpy (buffer + length, prefix);
6058           length += strlen (prefix);
6059           strcpy (buffer + length, tree_code_name[code]);
6060           length += strlen (tree_code_name[code]);
6061         }
6062       va_end (args);
6063     }
6064   else
6065     buffer = (char *)"unexpected node";
6066
6067   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6068                   buffer, tree_code_name[TREE_CODE (node)],
6069                   function, trim_filename (file), line);
6070 }
6071
6072 /* Complain that the tree code of NODE does match the expected 0
6073    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
6074    the caller.  */
6075
6076 void
6077 tree_not_check_failed (const tree node, const char *file,
6078                        int line, const char *function, ...)
6079 {
6080   va_list args;
6081   char *buffer;
6082   unsigned length = 0;
6083   int code;
6084
6085   va_start (args, function);
6086   while ((code = va_arg (args, int)))
6087     length += 4 + strlen (tree_code_name[code]);
6088   va_end (args);
6089   va_start (args, function);
6090   buffer = alloca (length);
6091   length = 0;
6092   while ((code = va_arg (args, int)))
6093     {
6094       if (length)
6095         {
6096           strcpy (buffer + length, " or ");
6097           length += 4;
6098         }
6099       strcpy (buffer + length, tree_code_name[code]);
6100       length += strlen (tree_code_name[code]);
6101     }
6102   va_end (args);
6103
6104   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
6105                   buffer, tree_code_name[TREE_CODE (node)],
6106                   function, trim_filename (file), line);
6107 }
6108
6109 /* Similar to tree_check_failed, except that we check for a class of tree
6110    code, given in CL.  */
6111
6112 void
6113 tree_class_check_failed (const tree node, const enum tree_code_class cl,
6114                          const char *file, int line, const char *function)
6115 {
6116   internal_error
6117     ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
6118      TREE_CODE_CLASS_STRING (cl),
6119      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6120      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6121 }
6122
6123 /* Similar to tree_check_failed, except that instead of specifying a
6124    dozen codes, use the knowledge that they're all sequential.  */
6125
6126 void
6127 tree_range_check_failed (const tree node, const char *file, int line,
6128                          const char *function, enum tree_code c1,
6129                          enum tree_code c2)
6130 {
6131   char *buffer;
6132   unsigned length = 0;
6133   enum tree_code c;
6134
6135   for (c = c1; c <= c2; ++c)
6136     length += 4 + strlen (tree_code_name[c]);
6137
6138   length += strlen ("expected ");
6139   buffer = alloca (length);
6140   length = 0;
6141
6142   for (c = c1; c <= c2; ++c)
6143     {
6144       const char *prefix = length ? " or " : "expected ";
6145
6146       strcpy (buffer + length, prefix);
6147       length += strlen (prefix);
6148       strcpy (buffer + length, tree_code_name[c]);
6149       length += strlen (tree_code_name[c]);
6150     }
6151
6152   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6153                   buffer, tree_code_name[TREE_CODE (node)],
6154                   function, trim_filename (file), line);
6155 }
6156
6157
6158 /* Similar to tree_check_failed, except that we check that a tree does
6159    not have the specified code, given in CL.  */
6160
6161 void
6162 tree_not_class_check_failed (const tree node, const enum tree_code_class cl,
6163                              const char *file, int line, const char *function)
6164 {
6165   internal_error
6166     ("tree check: did not expect class %qs, have %qs (%s) in %s, at %s:%d",
6167      TREE_CODE_CLASS_STRING (cl),
6168      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6169      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6170 }
6171
6172
6173 /* Similar to tree_check_failed but applied to OMP_CLAUSE codes.  */
6174
6175 void
6176 omp_clause_check_failed (const tree node, const char *file, int line,
6177                          const char *function, enum omp_clause_code code)
6178 {
6179   internal_error ("tree check: expected omp_clause %s, have %s in %s, at %s:%d",
6180                   omp_clause_code_name[code], tree_code_name[TREE_CODE (node)],
6181                   function, trim_filename (file), line);
6182 }
6183
6184
6185 /* Similar to tree_range_check_failed but applied to OMP_CLAUSE codes.  */
6186
6187 void
6188 omp_clause_range_check_failed (const tree node, const char *file, int line,
6189                                const char *function, enum omp_clause_code c1,
6190                                enum omp_clause_code c2)
6191 {
6192   char *buffer;
6193   unsigned length = 0;
6194   enum omp_clause_code c;
6195
6196   for (c = c1; c <= c2; ++c)
6197     length += 4 + strlen (omp_clause_code_name[c]);
6198
6199   length += strlen ("expected ");
6200   buffer = alloca (length);
6201   length = 0;
6202
6203   for (c = c1; c <= c2; ++c)
6204     {
6205       const char *prefix = length ? " or " : "expected ";
6206
6207       strcpy (buffer + length, prefix);
6208       length += strlen (prefix);
6209       strcpy (buffer + length, omp_clause_code_name[c]);
6210       length += strlen (omp_clause_code_name[c]);
6211     }
6212
6213   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6214                   buffer, omp_clause_code_name[TREE_CODE (node)],
6215                   function, trim_filename (file), line);
6216 }
6217
6218
6219 #undef DEFTREESTRUCT
6220 #define DEFTREESTRUCT(VAL, NAME) NAME,
6221
6222 static const char *ts_enum_names[] = {
6223 #include "treestruct.def"
6224 };
6225 #undef DEFTREESTRUCT
6226
6227 #define TS_ENUM_NAME(EN) (ts_enum_names[(EN)])
6228
6229 /* Similar to tree_class_check_failed, except that we check for
6230    whether CODE contains the tree structure identified by EN.  */
6231
6232 void
6233 tree_contains_struct_check_failed (const tree node,
6234                                    const enum tree_node_structure_enum en,
6235                                    const char *file, int line,
6236                                    const char *function)
6237 {
6238   internal_error
6239     ("tree check: expected tree that contains %qs structure, have %qs  in %s, at %s:%d",
6240      TS_ENUM_NAME(en),
6241      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6242 }
6243
6244
6245 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
6246    (dynamically sized) vector.  */
6247
6248 void
6249 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
6250                            const char *function)
6251 {
6252   internal_error
6253     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
6254      idx + 1, len, function, trim_filename (file), line);
6255 }
6256
6257 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
6258    (dynamically sized) vector.  */
6259
6260 void
6261 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
6262                             const char *function)
6263 {
6264   internal_error
6265     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
6266      idx + 1, len, function, trim_filename (file), line);
6267 }
6268
6269 /* Similar to above, except that the check is for the bounds of the operand
6270    vector of an expression node.  */
6271
6272 void
6273 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
6274                            int line, const char *function)
6275 {
6276   internal_error
6277     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
6278      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
6279      function, trim_filename (file), line);
6280 }
6281
6282 /* Similar to above, except that the check is for the number of
6283    operands of an OMP_CLAUSE node.  */
6284
6285 void
6286 omp_clause_operand_check_failed (int idx, tree t, const char *file,
6287                                  int line, const char *function)
6288 {
6289   internal_error
6290     ("tree check: accessed operand %d of omp_clause %s with %d operands "
6291      "in %s, at %s:%d", idx + 1, omp_clause_code_name[OMP_CLAUSE_CODE (t)],
6292      omp_clause_num_ops [OMP_CLAUSE_CODE (t)], function,
6293      trim_filename (file), line);
6294 }
6295 #endif /* ENABLE_TREE_CHECKING */
6296 \f
6297 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
6298    and mapped to the machine mode MODE.  Initialize its fields and build
6299    the information necessary for debugging output.  */
6300
6301 static tree
6302 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
6303 {
6304   tree t = make_node (VECTOR_TYPE);
6305
6306   TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
6307   SET_TYPE_VECTOR_SUBPARTS (t, nunits);
6308   TYPE_MODE (t) = mode;
6309   TYPE_READONLY (t) = TYPE_READONLY (innertype);
6310   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
6311
6312   layout_type (t);
6313
6314   {
6315     tree index = build_int_cst (NULL_TREE, nunits - 1);
6316     tree array = build_array_type (innertype, build_index_type (index));
6317     tree rt = make_node (RECORD_TYPE);
6318
6319     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
6320     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
6321     layout_type (rt);
6322     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
6323     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
6324        the representation type, and we want to find that die when looking up
6325        the vector type.  This is most easily achieved by making the TYPE_UID
6326        numbers equal.  */
6327     TYPE_UID (rt) = TYPE_UID (t);
6328   }
6329
6330   /* Build our main variant, based on the main variant of the inner type.  */
6331   if (TYPE_MAIN_VARIANT (innertype) != innertype)
6332     {
6333       tree innertype_main_variant = TYPE_MAIN_VARIANT (innertype);
6334       unsigned int hash = TYPE_HASH (innertype_main_variant);
6335       TYPE_MAIN_VARIANT (t)
6336         = type_hash_canon (hash, make_vector_type (innertype_main_variant,
6337                                                    nunits, mode));
6338     }
6339
6340   return t;
6341 }
6342
6343 static tree
6344 make_or_reuse_type (unsigned size, int unsignedp)
6345 {
6346   if (size == INT_TYPE_SIZE)
6347     return unsignedp ? unsigned_type_node : integer_type_node;
6348   if (size == CHAR_TYPE_SIZE)
6349     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
6350   if (size == SHORT_TYPE_SIZE)
6351     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
6352   if (size == LONG_TYPE_SIZE)
6353     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
6354   if (size == LONG_LONG_TYPE_SIZE)
6355     return (unsignedp ? long_long_unsigned_type_node
6356             : long_long_integer_type_node);
6357
6358   if (unsignedp)
6359     return make_unsigned_type (size);
6360   else
6361     return make_signed_type (size);
6362 }
6363
6364 /* Create nodes for all integer types (and error_mark_node) using the sizes
6365    of C datatypes.  The caller should call set_sizetype soon after calling
6366    this function to select one of the types as sizetype.  */
6367
6368 void
6369 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
6370 {
6371   error_mark_node = make_node (ERROR_MARK);
6372   TREE_TYPE (error_mark_node) = error_mark_node;
6373
6374   initialize_sizetypes (signed_sizetype);
6375
6376   /* Define both `signed char' and `unsigned char'.  */
6377   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
6378   TYPE_STRING_FLAG (signed_char_type_node) = 1;
6379   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
6380   TYPE_STRING_FLAG (unsigned_char_type_node) = 1;
6381
6382   /* Define `char', which is like either `signed char' or `unsigned char'
6383      but not the same as either.  */
6384   char_type_node
6385     = (signed_char
6386        ? make_signed_type (CHAR_TYPE_SIZE)
6387        : make_unsigned_type (CHAR_TYPE_SIZE));
6388   TYPE_STRING_FLAG (char_type_node) = 1;
6389
6390   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
6391   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
6392   integer_type_node = make_signed_type (INT_TYPE_SIZE);
6393   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
6394   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
6395   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
6396   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
6397   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
6398
6399   /* Define a boolean type.  This type only represents boolean values but
6400      may be larger than char depending on the value of BOOL_TYPE_SIZE.
6401      Front ends which want to override this size (i.e. Java) can redefine
6402      boolean_type_node before calling build_common_tree_nodes_2.  */
6403   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
6404   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
6405   TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
6406   TYPE_PRECISION (boolean_type_node) = 1;
6407
6408   /* Fill in the rest of the sized types.  Reuse existing type nodes
6409      when possible.  */
6410   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
6411   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
6412   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
6413   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
6414   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
6415
6416   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
6417   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
6418   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
6419   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
6420   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
6421
6422   access_public_node = get_identifier ("public");
6423   access_protected_node = get_identifier ("protected");
6424   access_private_node = get_identifier ("private");
6425 }
6426
6427 /* Call this function after calling build_common_tree_nodes and set_sizetype.
6428    It will create several other common tree nodes.  */
6429
6430 void
6431 build_common_tree_nodes_2 (int short_double)
6432 {
6433   /* Define these next since types below may used them.  */
6434   integer_zero_node = build_int_cst (NULL_TREE, 0);
6435   integer_one_node = build_int_cst (NULL_TREE, 1);
6436   integer_minus_one_node = build_int_cst (NULL_TREE, -1);
6437
6438   size_zero_node = size_int (0);
6439   size_one_node = size_int (1);
6440   bitsize_zero_node = bitsize_int (0);
6441   bitsize_one_node = bitsize_int (1);
6442   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
6443
6444   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
6445   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
6446
6447   void_type_node = make_node (VOID_TYPE);
6448   layout_type (void_type_node);
6449
6450   /* We are not going to have real types in C with less than byte alignment,
6451      so we might as well not have any types that claim to have it.  */
6452   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
6453   TYPE_USER_ALIGN (void_type_node) = 0;
6454
6455   null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
6456   layout_type (TREE_TYPE (null_pointer_node));
6457
6458   ptr_type_node = build_pointer_type (void_type_node);
6459   const_ptr_type_node
6460     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
6461   fileptr_type_node = ptr_type_node;
6462
6463   float_type_node = make_node (REAL_TYPE);
6464   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
6465   layout_type (float_type_node);
6466
6467   double_type_node = make_node (REAL_TYPE);
6468   if (short_double)
6469     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
6470   else
6471     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
6472   layout_type (double_type_node);
6473
6474   long_double_type_node = make_node (REAL_TYPE);
6475   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
6476   layout_type (long_double_type_node);
6477
6478   float_ptr_type_node = build_pointer_type (float_type_node);
6479   double_ptr_type_node = build_pointer_type (double_type_node);
6480   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
6481   integer_ptr_type_node = build_pointer_type (integer_type_node);
6482
6483   /* Decimal float types. */
6484   dfloat32_type_node = make_node (REAL_TYPE);
6485   TYPE_PRECISION (dfloat32_type_node) = DECIMAL32_TYPE_SIZE;
6486   layout_type (dfloat32_type_node);
6487   TYPE_MODE (dfloat32_type_node) = SDmode;
6488   dfloat32_ptr_type_node = build_pointer_type (dfloat32_type_node);
6489
6490   dfloat64_type_node = make_node (REAL_TYPE);
6491   TYPE_PRECISION (dfloat64_type_node) = DECIMAL64_TYPE_SIZE;
6492   layout_type (dfloat64_type_node);
6493   TYPE_MODE (dfloat64_type_node) = DDmode;
6494   dfloat64_ptr_type_node = build_pointer_type (dfloat64_type_node);
6495
6496   dfloat128_type_node = make_node (REAL_TYPE);
6497   TYPE_PRECISION (dfloat128_type_node) = DECIMAL128_TYPE_SIZE;
6498   layout_type (dfloat128_type_node);
6499   TYPE_MODE (dfloat128_type_node) = TDmode;
6500   dfloat128_ptr_type_node = build_pointer_type (dfloat128_type_node);
6501
6502   complex_integer_type_node = make_node (COMPLEX_TYPE);
6503   TREE_TYPE (complex_integer_type_node) = integer_type_node;
6504   layout_type (complex_integer_type_node);
6505
6506   complex_float_type_node = make_node (COMPLEX_TYPE);
6507   TREE_TYPE (complex_float_type_node) = float_type_node;
6508   layout_type (complex_float_type_node);
6509
6510   complex_double_type_node = make_node (COMPLEX_TYPE);
6511   TREE_TYPE (complex_double_type_node) = double_type_node;
6512   layout_type (complex_double_type_node);
6513
6514   complex_long_double_type_node = make_node (COMPLEX_TYPE);
6515   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
6516   layout_type (complex_long_double_type_node);
6517
6518   {
6519     tree t = targetm.build_builtin_va_list ();
6520
6521     /* Many back-ends define record types without setting TYPE_NAME.
6522        If we copied the record type here, we'd keep the original
6523        record type without a name.  This breaks name mangling.  So,
6524        don't copy record types and let c_common_nodes_and_builtins()
6525        declare the type to be __builtin_va_list.  */
6526     if (TREE_CODE (t) != RECORD_TYPE)
6527       t = build_variant_type_copy (t);
6528
6529     va_list_type_node = t;
6530   }
6531 }
6532
6533 /* A subroutine of build_common_builtin_nodes.  Define a builtin function.  */
6534
6535 static void
6536 local_define_builtin (const char *name, tree type, enum built_in_function code,
6537                       const char *library_name, int ecf_flags)
6538 {
6539   tree decl;
6540
6541   decl = lang_hooks.builtin_function (name, type, code, BUILT_IN_NORMAL,
6542                                       library_name, NULL_TREE);
6543   if (ecf_flags & ECF_CONST)
6544     TREE_READONLY (decl) = 1;
6545   if (ecf_flags & ECF_PURE)
6546     DECL_IS_PURE (decl) = 1;
6547   if (ecf_flags & ECF_NORETURN)
6548     TREE_THIS_VOLATILE (decl) = 1;
6549   if (ecf_flags & ECF_NOTHROW)
6550     TREE_NOTHROW (decl) = 1;
6551   if (ecf_flags & ECF_MALLOC)
6552     DECL_IS_MALLOC (decl) = 1;
6553
6554   built_in_decls[code] = decl;
6555   implicit_built_in_decls[code] = decl;
6556 }
6557
6558 /* Call this function after instantiating all builtins that the language
6559    front end cares about.  This will build the rest of the builtins that
6560    are relied upon by the tree optimizers and the middle-end.  */
6561
6562 void
6563 build_common_builtin_nodes (void)
6564 {
6565   tree tmp, ftype;
6566
6567   if (built_in_decls[BUILT_IN_MEMCPY] == NULL
6568       || built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6569     {
6570       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6571       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6572       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6573       ftype = build_function_type (ptr_type_node, tmp);
6574
6575       if (built_in_decls[BUILT_IN_MEMCPY] == NULL)
6576         local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY,
6577                               "memcpy", ECF_NOTHROW);
6578       if (built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6579         local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE,
6580                               "memmove", ECF_NOTHROW);
6581     }
6582
6583   if (built_in_decls[BUILT_IN_MEMCMP] == NULL)
6584     {
6585       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6586       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6587       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6588       ftype = build_function_type (integer_type_node, tmp);
6589       local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP,
6590                             "memcmp", ECF_PURE | ECF_NOTHROW);
6591     }
6592
6593   if (built_in_decls[BUILT_IN_MEMSET] == NULL)
6594     {
6595       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6596       tmp = tree_cons (NULL_TREE, integer_type_node, tmp);
6597       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6598       ftype = build_function_type (ptr_type_node, tmp);
6599       local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET,
6600                             "memset", ECF_NOTHROW);
6601     }
6602
6603   if (built_in_decls[BUILT_IN_ALLOCA] == NULL)
6604     {
6605       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6606       ftype = build_function_type (ptr_type_node, tmp);
6607       local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA,
6608                             "alloca", ECF_NOTHROW | ECF_MALLOC);
6609     }
6610
6611   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6612   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6613   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6614   ftype = build_function_type (void_type_node, tmp);
6615   local_define_builtin ("__builtin_init_trampoline", ftype,
6616                         BUILT_IN_INIT_TRAMPOLINE,
6617                         "__builtin_init_trampoline", ECF_NOTHROW);
6618
6619   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6620   ftype = build_function_type (ptr_type_node, tmp);
6621   local_define_builtin ("__builtin_adjust_trampoline", ftype,
6622                         BUILT_IN_ADJUST_TRAMPOLINE,
6623                         "__builtin_adjust_trampoline",
6624                         ECF_CONST | ECF_NOTHROW);
6625
6626   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6627   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6628   ftype = build_function_type (void_type_node, tmp);
6629   local_define_builtin ("__builtin_nonlocal_goto", ftype,
6630                         BUILT_IN_NONLOCAL_GOTO,
6631                         "__builtin_nonlocal_goto",
6632                         ECF_NORETURN | ECF_NOTHROW);
6633
6634   ftype = build_function_type (ptr_type_node, void_list_node);
6635   local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE,
6636                         "__builtin_stack_save", ECF_NOTHROW);
6637
6638   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6639   ftype = build_function_type (void_type_node, tmp);
6640   local_define_builtin ("__builtin_stack_restore", ftype,
6641                         BUILT_IN_STACK_RESTORE,
6642                         "__builtin_stack_restore", ECF_NOTHROW);
6643
6644   ftype = build_function_type (void_type_node, void_list_node);
6645   local_define_builtin ("__builtin_profile_func_enter", ftype,
6646                         BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0);
6647   local_define_builtin ("__builtin_profile_func_exit", ftype,
6648                         BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0);
6649
6650   /* Complex multiplication and division.  These are handled as builtins
6651      rather than optabs because emit_library_call_value doesn't support
6652      complex.  Further, we can do slightly better with folding these
6653      beasties if the real and complex parts of the arguments are separate.  */
6654   {
6655     enum machine_mode mode;
6656
6657     for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode)
6658       {
6659         char mode_name_buf[4], *q;
6660         const char *p;
6661         enum built_in_function mcode, dcode;
6662         tree type, inner_type;
6663
6664         type = lang_hooks.types.type_for_mode (mode, 0);
6665         if (type == NULL)
6666           continue;
6667         inner_type = TREE_TYPE (type);
6668
6669         tmp = tree_cons (NULL_TREE, inner_type, void_list_node);
6670         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6671         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6672         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6673         ftype = build_function_type (type, tmp);
6674
6675         mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6676         dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6677
6678         for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++)
6679           *q = TOLOWER (*p);
6680         *q = '\0';
6681
6682         built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL);
6683         local_define_builtin (built_in_names[mcode], ftype, mcode,
6684                               built_in_names[mcode], ECF_CONST | ECF_NOTHROW);
6685
6686         built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL);
6687         local_define_builtin (built_in_names[dcode], ftype, dcode,
6688                               built_in_names[dcode], ECF_CONST | ECF_NOTHROW);
6689       }
6690   }
6691 }
6692
6693 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
6694    better way.
6695
6696    If we requested a pointer to a vector, build up the pointers that
6697    we stripped off while looking for the inner type.  Similarly for
6698    return values from functions.
6699
6700    The argument TYPE is the top of the chain, and BOTTOM is the
6701    new type which we will point to.  */
6702
6703 tree
6704 reconstruct_complex_type (tree type, tree bottom)
6705 {
6706   tree inner, outer;
6707
6708   if (POINTER_TYPE_P (type))
6709     {
6710       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6711       outer = build_pointer_type (inner);
6712     }
6713   else if (TREE_CODE (type) == ARRAY_TYPE)
6714     {
6715       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6716       outer = build_array_type (inner, TYPE_DOMAIN (type));
6717     }
6718   else if (TREE_CODE (type) == FUNCTION_TYPE)
6719     {
6720       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6721       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
6722     }
6723   else if (TREE_CODE (type) == METHOD_TYPE)
6724     {
6725       tree argtypes;
6726       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6727       /* The build_method_type_directly() routine prepends 'this' to argument list,
6728          so we must compensate by getting rid of it.  */
6729       argtypes = TYPE_ARG_TYPES (type);
6730       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
6731                                           inner,
6732                                           TYPE_ARG_TYPES (type));
6733       TYPE_ARG_TYPES (outer) = argtypes;
6734     }
6735   else
6736     return bottom;
6737
6738   TYPE_READONLY (outer) = TYPE_READONLY (type);
6739   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
6740
6741   return outer;
6742 }
6743
6744 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
6745    the inner type.  */
6746 tree
6747 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
6748 {
6749   int nunits;
6750
6751   switch (GET_MODE_CLASS (mode))
6752     {
6753     case MODE_VECTOR_INT:
6754     case MODE_VECTOR_FLOAT:
6755       nunits = GET_MODE_NUNITS (mode);
6756       break;
6757
6758     case MODE_INT:
6759       /* Check that there are no leftover bits.  */
6760       gcc_assert (GET_MODE_BITSIZE (mode)
6761                   % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
6762
6763       nunits = GET_MODE_BITSIZE (mode)
6764                / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
6765       break;
6766
6767     default:
6768       gcc_unreachable ();
6769     }
6770
6771   return make_vector_type (innertype, nunits, mode);
6772 }
6773
6774 /* Similarly, but takes the inner type and number of units, which must be
6775    a power of two.  */
6776
6777 tree
6778 build_vector_type (tree innertype, int nunits)
6779 {
6780   return make_vector_type (innertype, nunits, VOIDmode);
6781 }
6782
6783 /* Build RESX_EXPR with given REGION_NUMBER.  */
6784 tree
6785 build_resx (int region_number)
6786 {
6787   tree t;
6788   t = build1 (RESX_EXPR, void_type_node,
6789               build_int_cst (NULL_TREE, region_number));
6790   return t;
6791 }
6792
6793 /* Given an initializer INIT, return TRUE if INIT is zero or some
6794    aggregate of zeros.  Otherwise return FALSE.  */
6795 bool
6796 initializer_zerop (tree init)
6797 {
6798   tree elt;
6799
6800   STRIP_NOPS (init);
6801
6802   switch (TREE_CODE (init))
6803     {
6804     case INTEGER_CST:
6805       return integer_zerop (init);
6806
6807     case REAL_CST:
6808       /* ??? Note that this is not correct for C4X float formats.  There,
6809          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
6810          negative exponent.  */
6811       return real_zerop (init)
6812         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
6813
6814     case COMPLEX_CST:
6815       return integer_zerop (init)
6816         || (real_zerop (init)
6817             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
6818             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
6819
6820     case VECTOR_CST:
6821       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
6822         if (!initializer_zerop (TREE_VALUE (elt)))
6823           return false;
6824       return true;
6825
6826     case CONSTRUCTOR:
6827       {
6828         unsigned HOST_WIDE_INT idx;
6829
6830         FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
6831           if (!initializer_zerop (elt))
6832             return false;
6833         return true;
6834       }
6835
6836     default:
6837       return false;
6838     }
6839 }
6840
6841 /* Build an empty statement.  */
6842
6843 tree
6844 build_empty_stmt (void)
6845 {
6846   return build1 (NOP_EXPR, void_type_node, size_zero_node);
6847 }
6848
6849
6850 /* Build an OpenMP clause with code CODE.  */
6851
6852 tree
6853 build_omp_clause (enum omp_clause_code code)
6854 {
6855   tree t;
6856   int size, length;
6857
6858   length = omp_clause_num_ops[code];
6859   size = (sizeof (struct tree_omp_clause) + (length - 1) * sizeof (tree));
6860
6861   t = ggc_alloc (size);
6862   memset (t, 0, size);
6863   TREE_SET_CODE (t, OMP_CLAUSE);
6864   OMP_CLAUSE_SET_CODE (t, code);
6865
6866 #ifdef GATHER_STATISTICS
6867   tree_node_counts[(int) omp_clause_kind]++;
6868   tree_node_sizes[(int) omp_clause_kind] += size;
6869 #endif
6870
6871   return t;
6872 }
6873
6874
6875 /* Returns true if it is possible to prove that the index of
6876    an array access REF (an ARRAY_REF expression) falls into the
6877    array bounds.  */
6878
6879 bool
6880 in_array_bounds_p (tree ref)
6881 {
6882   tree idx = TREE_OPERAND (ref, 1);
6883   tree min, max;
6884
6885   if (TREE_CODE (idx) != INTEGER_CST)
6886     return false;
6887
6888   min = array_ref_low_bound (ref);
6889   max = array_ref_up_bound (ref);
6890   if (!min
6891       || !max
6892       || TREE_CODE (min) != INTEGER_CST
6893       || TREE_CODE (max) != INTEGER_CST)
6894     return false;
6895
6896   if (tree_int_cst_lt (idx, min)
6897       || tree_int_cst_lt (max, idx))
6898     return false;
6899
6900   return true;
6901 }
6902
6903 /* Return true if T (assumed to be a DECL) is a global variable.  */
6904
6905 bool
6906 is_global_var (tree t)
6907 {
6908   if (MTAG_P (t))
6909     return (TREE_STATIC (t) || MTAG_GLOBAL (t));
6910   else
6911     return (TREE_STATIC (t) || DECL_EXTERNAL (t));
6912 }
6913
6914 /* Return true if T (assumed to be a DECL) must be assigned a memory
6915    location.  */
6916
6917 bool
6918 needs_to_live_in_memory (tree t)
6919 {
6920   return (TREE_ADDRESSABLE (t)
6921           || is_global_var (t)
6922           || (TREE_CODE (t) == RESULT_DECL
6923               && aggregate_value_p (t, current_function_decl)));
6924 }
6925
6926 /* There are situations in which a language considers record types
6927    compatible which have different field lists.  Decide if two fields
6928    are compatible.  It is assumed that the parent records are compatible.  */
6929
6930 bool
6931 fields_compatible_p (tree f1, tree f2)
6932 {
6933   if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
6934                         DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
6935     return false;
6936
6937   if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
6938                         DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
6939     return false;
6940
6941   if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
6942     return false;
6943
6944   return true;
6945 }
6946
6947 /* Locate within RECORD a field that is compatible with ORIG_FIELD.  */
6948
6949 tree
6950 find_compatible_field (tree record, tree orig_field)
6951 {
6952   tree f;
6953
6954   for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
6955     if (TREE_CODE (f) == FIELD_DECL
6956         && fields_compatible_p (f, orig_field))
6957       return f;
6958
6959   /* ??? Why isn't this on the main fields list?  */
6960   f = TYPE_VFIELD (record);
6961   if (f && TREE_CODE (f) == FIELD_DECL
6962       && fields_compatible_p (f, orig_field))
6963     return f;
6964
6965   /* ??? We should abort here, but Java appears to do Bad Things
6966      with inherited fields.  */
6967   return orig_field;
6968 }
6969
6970 /* Return value of a constant X.  */
6971
6972 HOST_WIDE_INT
6973 int_cst_value (tree x)
6974 {
6975   unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
6976   unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
6977   bool negative = ((val >> (bits - 1)) & 1) != 0;
6978
6979   gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
6980
6981   if (negative)
6982     val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
6983   else
6984     val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
6985
6986   return val;
6987 }
6988
6989 /* Returns the greatest common divisor of A and B, which must be
6990    INTEGER_CSTs.  */
6991
6992 tree
6993 tree_fold_gcd (tree a, tree b)
6994 {
6995   tree a_mod_b;
6996   tree type = TREE_TYPE (a);
6997
6998   gcc_assert (TREE_CODE (a) == INTEGER_CST);
6999   gcc_assert (TREE_CODE (b) == INTEGER_CST);
7000
7001   if (integer_zerop (a))
7002     return b;
7003
7004   if (integer_zerop (b))
7005     return a;
7006
7007   if (tree_int_cst_sgn (a) == -1)
7008     a = fold_build2 (MULT_EXPR, type, a,
7009                      build_int_cst (type, -1));
7010
7011   if (tree_int_cst_sgn (b) == -1)
7012     b = fold_build2 (MULT_EXPR, type, b,
7013                      build_int_cst (type, -1));
7014
7015   while (1)
7016     {
7017       a_mod_b = fold_build2 (FLOOR_MOD_EXPR, type, a, b);
7018
7019       if (!TREE_INT_CST_LOW (a_mod_b)
7020           && !TREE_INT_CST_HIGH (a_mod_b))
7021         return b;
7022
7023       a = b;
7024       b = a_mod_b;
7025     }
7026 }
7027
7028 /* Returns unsigned variant of TYPE.  */
7029
7030 tree
7031 unsigned_type_for (tree type)
7032 {
7033   if (POINTER_TYPE_P (type))
7034     return lang_hooks.types.unsigned_type (size_type_node);
7035   return lang_hooks.types.unsigned_type (type);
7036 }
7037
7038 /* Returns signed variant of TYPE.  */
7039
7040 tree
7041 signed_type_for (tree type)
7042 {
7043   if (POINTER_TYPE_P (type))
7044     return lang_hooks.types.signed_type (size_type_node);
7045   return lang_hooks.types.signed_type (type);
7046 }
7047
7048 /* Returns the largest value obtainable by casting something in INNER type to
7049    OUTER type.  */
7050
7051 tree
7052 upper_bound_in_type (tree outer, tree inner)
7053 {
7054   unsigned HOST_WIDE_INT lo, hi;
7055   unsigned int det = 0;
7056   unsigned oprec = TYPE_PRECISION (outer);
7057   unsigned iprec = TYPE_PRECISION (inner);
7058   unsigned prec;
7059
7060   /* Compute a unique number for every combination.  */
7061   det |= (oprec > iprec) ? 4 : 0;
7062   det |= TYPE_UNSIGNED (outer) ? 2 : 0;
7063   det |= TYPE_UNSIGNED (inner) ? 1 : 0;
7064
7065   /* Determine the exponent to use.  */
7066   switch (det)
7067     {
7068     case 0:
7069     case 1:
7070       /* oprec <= iprec, outer: signed, inner: don't care.  */
7071       prec = oprec - 1;
7072       break;
7073     case 2:
7074     case 3:
7075       /* oprec <= iprec, outer: unsigned, inner: don't care.  */
7076       prec = oprec;
7077       break;
7078     case 4:
7079       /* oprec > iprec, outer: signed, inner: signed.  */
7080       prec = iprec - 1;
7081       break;
7082     case 5:
7083       /* oprec > iprec, outer: signed, inner: unsigned.  */
7084       prec = iprec;
7085       break;
7086     case 6:
7087       /* oprec > iprec, outer: unsigned, inner: signed.  */
7088       prec = oprec;
7089       break;
7090     case 7:
7091       /* oprec > iprec, outer: unsigned, inner: unsigned.  */
7092       prec = iprec;
7093       break;
7094     default:
7095       gcc_unreachable ();
7096     }
7097
7098   /* Compute 2^^prec - 1.  */
7099   if (prec <= HOST_BITS_PER_WIDE_INT)
7100     {
7101       hi = 0;
7102       lo = ((~(unsigned HOST_WIDE_INT) 0)
7103             >> (HOST_BITS_PER_WIDE_INT - prec));
7104     }
7105   else
7106     {
7107       hi = ((~(unsigned HOST_WIDE_INT) 0)
7108             >> (2 * HOST_BITS_PER_WIDE_INT - prec));
7109       lo = ~(unsigned HOST_WIDE_INT) 0;
7110     }
7111
7112   return build_int_cst_wide (outer, lo, hi);
7113 }
7114
7115 /* Returns the smallest value obtainable by casting something in INNER type to
7116    OUTER type.  */
7117
7118 tree
7119 lower_bound_in_type (tree outer, tree inner)
7120 {
7121   unsigned HOST_WIDE_INT lo, hi;
7122   unsigned oprec = TYPE_PRECISION (outer);
7123   unsigned iprec = TYPE_PRECISION (inner);
7124
7125   /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
7126      and obtain 0.  */
7127   if (TYPE_UNSIGNED (outer)
7128       /* If we are widening something of an unsigned type, OUTER type
7129          contains all values of INNER type.  In particular, both INNER
7130          and OUTER types have zero in common.  */
7131       || (oprec > iprec && TYPE_UNSIGNED (inner)))
7132     lo = hi = 0;
7133   else
7134     {
7135       /* If we are widening a signed type to another signed type, we
7136          want to obtain -2^^(iprec-1).  If we are keeping the
7137          precision or narrowing to a signed type, we want to obtain
7138          -2^(oprec-1).  */
7139       unsigned prec = oprec > iprec ? iprec : oprec;
7140
7141       if (prec <= HOST_BITS_PER_WIDE_INT)
7142         {
7143           hi = ~(unsigned HOST_WIDE_INT) 0;
7144           lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
7145         }
7146       else
7147         {
7148           hi = ((~(unsigned HOST_WIDE_INT) 0)
7149                 << (prec - HOST_BITS_PER_WIDE_INT - 1));
7150           lo = 0;
7151         }
7152     }
7153
7154   return build_int_cst_wide (outer, lo, hi);
7155 }
7156
7157 /* Return nonzero if two operands that are suitable for PHI nodes are
7158    necessarily equal.  Specifically, both ARG0 and ARG1 must be either
7159    SSA_NAME or invariant.  Note that this is strictly an optimization.
7160    That is, callers of this function can directly call operand_equal_p
7161    and get the same result, only slower.  */
7162
7163 int
7164 operand_equal_for_phi_arg_p (tree arg0, tree arg1)
7165 {
7166   if (arg0 == arg1)
7167     return 1;
7168   if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME)
7169     return 0;
7170   return operand_equal_p (arg0, arg1, 0);
7171 }
7172
7173 /* Returns number of zeros at the end of binary representation of X.
7174
7175    ??? Use ffs if available?  */
7176
7177 tree
7178 num_ending_zeros (tree x)
7179 {
7180   unsigned HOST_WIDE_INT fr, nfr;
7181   unsigned num, abits;
7182   tree type = TREE_TYPE (x);
7183
7184   if (TREE_INT_CST_LOW (x) == 0)
7185     {
7186       num = HOST_BITS_PER_WIDE_INT;
7187       fr = TREE_INT_CST_HIGH (x);
7188     }
7189   else
7190     {
7191       num = 0;
7192       fr = TREE_INT_CST_LOW (x);
7193     }
7194
7195   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
7196     {
7197       nfr = fr >> abits;
7198       if (nfr << abits == fr)
7199         {
7200           num += abits;
7201           fr = nfr;
7202         }
7203     }
7204
7205   if (num > TYPE_PRECISION (type))
7206     num = TYPE_PRECISION (type);
7207
7208   return build_int_cst_type (type, num);
7209 }
7210
7211
7212 #define WALK_SUBTREE(NODE)                              \
7213   do                                                    \
7214     {                                                   \
7215       result = walk_tree (&(NODE), func, data, pset);   \
7216       if (result)                                       \
7217         return result;                                  \
7218     }                                                   \
7219   while (0)
7220
7221 /* This is a subroutine of walk_tree that walks field of TYPE that are to
7222    be walked whenever a type is seen in the tree.  Rest of operands and return
7223    value are as for walk_tree.  */
7224
7225 static tree
7226 walk_type_fields (tree type, walk_tree_fn func, void *data,
7227                   struct pointer_set_t *pset)
7228 {
7229   tree result = NULL_TREE;
7230
7231   switch (TREE_CODE (type))
7232     {
7233     case POINTER_TYPE:
7234     case REFERENCE_TYPE:
7235       /* We have to worry about mutually recursive pointers.  These can't
7236          be written in C.  They can in Ada.  It's pathological, but
7237          there's an ACATS test (c38102a) that checks it.  Deal with this
7238          by checking if we're pointing to another pointer, that one
7239          points to another pointer, that one does too, and we have no htab.
7240          If so, get a hash table.  We check three levels deep to avoid
7241          the cost of the hash table if we don't need one.  */
7242       if (POINTER_TYPE_P (TREE_TYPE (type))
7243           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
7244           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
7245           && !pset)
7246         {
7247           result = walk_tree_without_duplicates (&TREE_TYPE (type),
7248                                                  func, data);
7249           if (result)
7250             return result;
7251
7252           break;
7253         }
7254
7255       /* ... fall through ... */
7256
7257     case COMPLEX_TYPE:
7258       WALK_SUBTREE (TREE_TYPE (type));
7259       break;
7260
7261     case METHOD_TYPE:
7262       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
7263
7264       /* Fall through.  */
7265
7266     case FUNCTION_TYPE:
7267       WALK_SUBTREE (TREE_TYPE (type));
7268       {
7269         tree arg;
7270
7271         /* We never want to walk into default arguments.  */
7272         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
7273           WALK_SUBTREE (TREE_VALUE (arg));
7274       }
7275       break;
7276
7277     case ARRAY_TYPE:
7278       /* Don't follow this nodes's type if a pointer for fear that we'll
7279          have infinite recursion.  Those types are uninteresting anyway.  */
7280       if (!POINTER_TYPE_P (TREE_TYPE (type))
7281           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
7282         WALK_SUBTREE (TREE_TYPE (type));
7283       WALK_SUBTREE (TYPE_DOMAIN (type));
7284       break;
7285
7286     case BOOLEAN_TYPE:
7287     case ENUMERAL_TYPE:
7288     case INTEGER_TYPE:
7289     case REAL_TYPE:
7290       WALK_SUBTREE (TYPE_MIN_VALUE (type));
7291       WALK_SUBTREE (TYPE_MAX_VALUE (type));
7292       break;
7293
7294     case OFFSET_TYPE:
7295       WALK_SUBTREE (TREE_TYPE (type));
7296       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
7297       break;
7298
7299     default:
7300       break;
7301     }
7302
7303   return NULL_TREE;
7304 }
7305
7306 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
7307    called with the DATA and the address of each sub-tree.  If FUNC returns a
7308    non-NULL value, the traversal is stopped, and the value returned by FUNC
7309    is returned.  If PSET is non-NULL it is used to record the nodes visited,
7310    and to avoid visiting a node more than once.  */
7311
7312 tree
7313 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
7314 {
7315   enum tree_code code;
7316   int walk_subtrees;
7317   tree result;
7318
7319 #define WALK_SUBTREE_TAIL(NODE)                         \
7320   do                                                    \
7321     {                                                   \
7322        tp = & (NODE);                                   \
7323        goto tail_recurse;                               \
7324     }                                                   \
7325   while (0)
7326
7327  tail_recurse:
7328   /* Skip empty subtrees.  */
7329   if (!*tp)
7330     return NULL_TREE;
7331
7332   /* Don't walk the same tree twice, if the user has requested
7333      that we avoid doing so.  */
7334   if (pset && pointer_set_insert (pset, *tp))
7335     return NULL_TREE;
7336
7337   /* Call the function.  */
7338   walk_subtrees = 1;
7339   result = (*func) (tp, &walk_subtrees, data);
7340
7341   /* If we found something, return it.  */
7342   if (result)
7343     return result;
7344
7345   code = TREE_CODE (*tp);
7346
7347   /* Even if we didn't, FUNC may have decided that there was nothing
7348      interesting below this point in the tree.  */
7349   if (!walk_subtrees)
7350     {
7351       /* But we still need to check our siblings.  */
7352       if (code == TREE_LIST)
7353         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7354       else if (code == OMP_CLAUSE)
7355         WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7356       else
7357         return NULL_TREE;
7358     }
7359
7360   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
7361                                                    data, pset);
7362   if (result || ! walk_subtrees)
7363     return result;
7364
7365   switch (code)
7366     {
7367     case ERROR_MARK:
7368     case IDENTIFIER_NODE:
7369     case INTEGER_CST:
7370     case REAL_CST:
7371     case VECTOR_CST:
7372     case STRING_CST:
7373     case BLOCK:
7374     case PLACEHOLDER_EXPR:
7375     case SSA_NAME:
7376     case FIELD_DECL:
7377     case RESULT_DECL:
7378       /* None of these have subtrees other than those already walked
7379          above.  */
7380       break;
7381
7382     case TREE_LIST:
7383       WALK_SUBTREE (TREE_VALUE (*tp));
7384       WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7385       break;
7386
7387     case TREE_VEC:
7388       {
7389         int len = TREE_VEC_LENGTH (*tp);
7390
7391         if (len == 0)
7392           break;
7393
7394         /* Walk all elements but the first.  */
7395         while (--len)
7396           WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
7397
7398         /* Now walk the first one as a tail call.  */
7399         WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
7400       }
7401
7402     case COMPLEX_CST:
7403       WALK_SUBTREE (TREE_REALPART (*tp));
7404       WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
7405
7406     case CONSTRUCTOR:
7407       {
7408         unsigned HOST_WIDE_INT idx;
7409         constructor_elt *ce;
7410
7411         for (idx = 0;
7412              VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (*tp), idx, ce);
7413              idx++)
7414           WALK_SUBTREE (ce->value);
7415       }
7416       break;
7417
7418     case SAVE_EXPR:
7419       WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
7420
7421     case BIND_EXPR:
7422       {
7423         tree decl;
7424         for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
7425           {
7426             /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
7427                into declarations that are just mentioned, rather than
7428                declared; they don't really belong to this part of the tree.
7429                And, we can see cycles: the initializer for a declaration
7430                can refer to the declaration itself.  */
7431             WALK_SUBTREE (DECL_INITIAL (decl));
7432             WALK_SUBTREE (DECL_SIZE (decl));
7433             WALK_SUBTREE (DECL_SIZE_UNIT (decl));
7434           }
7435         WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
7436       }
7437
7438     case STATEMENT_LIST:
7439       {
7440         tree_stmt_iterator i;
7441         for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
7442           WALK_SUBTREE (*tsi_stmt_ptr (i));
7443       }
7444       break;
7445
7446     case OMP_CLAUSE:
7447       switch (OMP_CLAUSE_CODE (*tp))
7448         {
7449         case OMP_CLAUSE_PRIVATE:
7450         case OMP_CLAUSE_SHARED:
7451         case OMP_CLAUSE_FIRSTPRIVATE:
7452         case OMP_CLAUSE_LASTPRIVATE:
7453         case OMP_CLAUSE_COPYIN:
7454         case OMP_CLAUSE_COPYPRIVATE:
7455         case OMP_CLAUSE_IF:
7456         case OMP_CLAUSE_NUM_THREADS:
7457         case OMP_CLAUSE_SCHEDULE:
7458           WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, 0));
7459           /* FALLTHRU */
7460
7461         case OMP_CLAUSE_NOWAIT:
7462         case OMP_CLAUSE_ORDERED:
7463         case OMP_CLAUSE_DEFAULT:
7464           WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7465
7466         case OMP_CLAUSE_REDUCTION:
7467           {
7468             int i;
7469             for (i = 0; i < 4; i++)
7470               WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, i));
7471             WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7472           }
7473
7474         default:
7475           gcc_unreachable ();
7476         }
7477       break;
7478
7479     case TARGET_EXPR:
7480       {
7481         int i, len;
7482
7483         /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
7484            But, we only want to walk once.  */
7485         len = (TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1)) ? 2 : 3;
7486         for (i = 0; i < len; ++i)
7487           WALK_SUBTREE (TREE_OPERAND (*tp, i));
7488         WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len));
7489       }
7490
7491     case DECL_EXPR:
7492       /* Walk into various fields of the type that it's defining.  We only
7493          want to walk into these fields of a type in this case.  Note that
7494          decls get walked as part of the processing of a BIND_EXPR.
7495
7496          ??? Precisely which fields of types that we are supposed to walk in
7497          this case vs. the normal case aren't well defined.  */
7498       if (TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
7499           && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
7500         {
7501           tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
7502
7503           /* Call the function for the type.  See if it returns anything or
7504              doesn't want us to continue.  If we are to continue, walk both
7505              the normal fields and those for the declaration case.  */
7506           result = (*func) (type_p, &walk_subtrees, data);
7507           if (result || !walk_subtrees)
7508             return NULL_TREE;
7509
7510           result = walk_type_fields (*type_p, func, data, pset);
7511           if (result)
7512             return result;
7513
7514           /* If this is a record type, also walk the fields.  */
7515           if (TREE_CODE (*type_p) == RECORD_TYPE
7516               || TREE_CODE (*type_p) == UNION_TYPE
7517               || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7518             {
7519               tree field;
7520
7521               for (field = TYPE_FIELDS (*type_p); field;
7522                    field = TREE_CHAIN (field))
7523                 {
7524                   /* We'd like to look at the type of the field, but we can
7525                      easily get infinite recursion.  So assume it's pointed
7526                      to elsewhere in the tree.  Also, ignore things that
7527                      aren't fields.  */
7528                   if (TREE_CODE (field) != FIELD_DECL)
7529                     continue;
7530
7531                   WALK_SUBTREE (DECL_FIELD_OFFSET (field));
7532                   WALK_SUBTREE (DECL_SIZE (field));
7533                   WALK_SUBTREE (DECL_SIZE_UNIT (field));
7534                   if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7535                     WALK_SUBTREE (DECL_QUALIFIER (field));
7536                 }
7537             }
7538
7539           WALK_SUBTREE (TYPE_SIZE (*type_p));
7540           WALK_SUBTREE_TAIL (TYPE_SIZE_UNIT (*type_p));
7541         }
7542       /* FALLTHRU */
7543
7544     default:
7545       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
7546         {
7547           int i, len;
7548
7549           /* Walk over all the sub-trees of this operand.  */
7550           len = TREE_CODE_LENGTH (code);
7551
7552           /* Go through the subtrees.  We need to do this in forward order so
7553              that the scope of a FOR_EXPR is handled properly.  */
7554           if (len)
7555             {
7556               for (i = 0; i < len - 1; ++i)
7557                 WALK_SUBTREE (TREE_OPERAND (*tp, i));
7558               WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
7559             }
7560         }
7561
7562       /* If this is a type, walk the needed fields in the type.  */
7563       else if (TYPE_P (*tp))
7564         return walk_type_fields (*tp, func, data, pset);
7565       break;
7566     }
7567
7568   /* We didn't find what we were looking for.  */
7569   return NULL_TREE;
7570
7571 #undef WALK_SUBTREE_TAIL
7572 }
7573 #undef WALK_SUBTREE
7574
7575 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
7576
7577 tree
7578 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
7579 {
7580   tree result;
7581   struct pointer_set_t *pset;
7582
7583   pset = pointer_set_create ();
7584   result = walk_tree (tp, func, data, pset);
7585   pointer_set_destroy (pset);
7586   return result;
7587 }
7588
7589
7590 /* Return true if STMT is an empty statement or contains nothing but
7591    empty statements.  */
7592
7593 bool
7594 empty_body_p (tree stmt)
7595 {
7596   tree_stmt_iterator i;
7597   tree body;
7598
7599   if (IS_EMPTY_STMT (stmt))
7600     return true;
7601   else if (TREE_CODE (stmt) == BIND_EXPR)
7602     body = BIND_EXPR_BODY (stmt);
7603   else if (TREE_CODE (stmt) == STATEMENT_LIST)
7604     body = stmt;
7605   else
7606     return false;
7607
7608   for (i = tsi_start (body); !tsi_end_p (i); tsi_next (&i))
7609     if (!empty_body_p (tsi_stmt (i)))
7610       return false;
7611
7612   return true;
7613 }
7614
7615 #include "gt-tree.h"