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