gcc/tree.c

   1 /* Language-independent node constructors for parse phase of GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 /* This file contains the low level primitives for operating on tree nodes,
  23    including allocation, list operations, interning of identifiers,
  24    construction of data type nodes and statement nodes,
  25    and construction of type conversion nodes.  It also contains
  26    tables index by tree code that describe how to take apart
  27    nodes of that code.
  28
  29    It is intended to be language-independent, but occasionally
  30    calls language-dependent routines defined (for C) in typecheck.c.  */
  31
  32 #include "config.h"
  33 #include "system.h"
  34 #include "coretypes.h"
  35 #include "tm.h"
  36 #include "flags.h"
  37 #include "tree.h"
  38 #include "real.h"
  39 #include "tm_p.h"
  40 #include "function.h"
  41 #include "obstack.h"
  42 #include "toplev.h"
  43 #include "ggc.h"
  44 #include "hashtab.h"
  45 #include "output.h"
  46 #include "target.h"
  47 #include "langhooks.h"
  48 #include "tree-iterator.h"
  49 #include "basic-block.h"
  50 #include "tree-flow.h"
  51 #include "params.h"
  52 #include "pointer-set.h"
  53
  54 /* Each tree code class has an associated string representation.
  55    These must correspond to the tree_code_class entries.  */
  56
  57 const char *const tree_code_class_strings[] =
  58 {
  59   "exceptional",
  60   "constant",
  61   "type",
  62   "declaration",
  63   "reference",
  64   "comparison",
  65   "unary",
  66   "binary",
  67   "statement",
  68   "expression",
  69 };
  70
  71 /* obstack.[ch] explicitly declined to prototype this.  */
  72 extern int _obstack_allocated_p (struct obstack *h, void *obj);
  73
  74 #ifdef GATHER_STATISTICS
  75 /* Statistics-gathering stuff.  */
  76
  77 int tree_node_counts[(int) all_kinds];
  78 int tree_node_sizes[(int) all_kinds];
  79
  80 /* Keep in sync with tree.h:enum tree_node_kind.  */
  81 static const char * const tree_node_kind_names[] = {
  82   "decls",
  83   "types",
  84   "blocks",
  85   "stmts",
  86   "refs",
  87   "exprs",
  88   "constants",
  89   "identifiers",
  90   "perm_tree_lists",
  91   "temp_tree_lists",
  92   "vecs",
  93   "binfos",
  94   "phi_nodes",
  95   "ssa names",
  96   "constructors",
  97   "random kinds",
  98   "lang_decl kinds",
  99   "lang_type kinds",
 100   "omp clauses"
 101 };
 102 #endif /* GATHER_STATISTICS */
 103
 104 /* Unique id for next decl created.  */
 105 static GTY(()) int next_decl_uid;
 106 /* Unique id for next type created.  */
 107 static GTY(()) int next_type_uid = 1;
 108
 109 /* Since we cannot rehash a type after it is in the table, we have to
 110    keep the hash code.  */
 111
 112 struct type_hash GTY(())
 113 {
 114   unsigned long hash;
 115   tree type;
 116 };
 117
 118 /* Initial size of the hash table (rounded to next prime).  */
 119 #define TYPE_HASH_INITIAL_SIZE 1000
 120
 121 /* Now here is the hash table.  When recording a type, it is added to
 122    the slot whose index is the hash code.  Note that the hash table is
 123    used for several kinds of types (function types, array types and
 124    array index range types, for now).  While all these live in the
 125    same table, they are completely independent, and the hash code is
 126    computed differently for each of these.  */
 127
 128 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
 129      htab_t type_hash_table;
 130
 131 /* Hash table and temporary node for larger integer const values.  */
 132 static GTY (()) tree int_cst_node;
 133 static GTY ((if_marked ("ggc_marked_p"), param_is (union tree_node)))
 134      htab_t int_cst_hash_table;
 135
 136 /* General tree->tree mapping  structure for use in hash tables.  */
 137
 138
 139 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 140      htab_t debug_expr_for_decl;
 141
 142 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 143      htab_t value_expr_for_decl;
 144
 145 static GTY ((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
 146   htab_t init_priority_for_decl;
 147
 148 static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map)))
 149   htab_t restrict_base_for_decl;
 150
 151 struct tree_int_map GTY(())
 152 {
 153   tree from;
 154   unsigned short to;
 155 };
 156 static unsigned int tree_int_map_hash (const void *);
 157 static int tree_int_map_eq (const void *, const void *);
 158 static int tree_int_map_marked_p (const void *);
 159 static void set_type_quals (tree, int);
 160 static int type_hash_eq (const void *, const void *);
 161 static hashval_t type_hash_hash (const void *);
 162 static hashval_t int_cst_hash_hash (const void *);
 163 static int int_cst_hash_eq (const void *, const void *);
 164 static void print_type_hash_statistics (void);
 165 static void print_debug_expr_statistics (void);
 166 static void print_value_expr_statistics (void);
 167 static tree make_vector_type (tree, int, enum machine_mode);
 168 static int type_hash_marked_p (const void *);
 169 static unsigned int type_hash_list (tree, hashval_t);
 170 static unsigned int attribute_hash_list (tree, hashval_t);
 171
 172 tree global_trees[TI_MAX];
 173 tree integer_types[itk_none];
 174
 175 unsigned char tree_contains_struct[256][64];
 176
 177 /* Number of operands for each OpenMP clause.  */
 178 unsigned const char omp_clause_num_ops[] =
 179 {
 180   0, /* OMP_CLAUSE_ERROR  */
 181   1, /* OMP_CLAUSE_PRIVATE  */
 182   1, /* OMP_CLAUSE_SHARED  */
 183   1, /* OMP_CLAUSE_FIRSTPRIVATE  */
 184   1, /* OMP_CLAUSE_LASTPRIVATE  */
 185   4, /* OMP_CLAUSE_REDUCTION  */
 186   1, /* OMP_CLAUSE_COPYIN  */
 187   1, /* OMP_CLAUSE_COPYPRIVATE  */
 188   1, /* OMP_CLAUSE_IF  */
 189   1, /* OMP_CLAUSE_NUM_THREADS  */
 190   1, /* OMP_CLAUSE_SCHEDULE  */
 191   0, /* OMP_CLAUSE_NOWAIT  */
 192   0, /* OMP_CLAUSE_ORDERED  */
 193   0  /* OMP_CLAUSE_DEFAULT  */
 194 };
 195
 196 const char * const omp_clause_code_name[] =
 197 {
 198   "error_clause",
 199   "private",
 200   "shared",
 201   "firstprivate",
 202   "lastprivate",
 203   "reduction",
 204   "copyin",
 205   "copyprivate",
 206   "if",
 207   "num_threads",
 208   "schedule",
 209   "nowait",
 210   "ordered",
 211   "default"
 212 };
 213 \f
 214 /* Init tree.c.  */
 215
 216 void
 217 init_ttree (void)
 218 {
 219   /* Initialize the hash table of types.  */
 220   type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
 221                                      type_hash_eq, 0);
 222
 223   debug_expr_for_decl = htab_create_ggc (512, tree_map_hash,
 224                                          tree_map_eq, 0);
 225
 226   value_expr_for_decl = htab_create_ggc (512, tree_map_hash,
 227                                          tree_map_eq, 0);
 228   init_priority_for_decl = htab_create_ggc (512, tree_int_map_hash,
 229                                             tree_int_map_eq, 0);
 230   restrict_base_for_decl = htab_create_ggc (256, tree_map_hash,
 231                                             tree_map_eq, 0);
 232
 233   int_cst_hash_table = htab_create_ggc (1024, int_cst_hash_hash,
 234                                         int_cst_hash_eq, NULL);
 235
 236   int_cst_node = make_node (INTEGER_CST);
 237
 238   tree_contains_struct[FUNCTION_DECL][TS_DECL_NON_COMMON] = 1;
 239   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_NON_COMMON] = 1;
 240   tree_contains_struct[TYPE_DECL][TS_DECL_NON_COMMON] = 1;
 241
 242
 243   tree_contains_struct[CONST_DECL][TS_DECL_COMMON] = 1;
 244   tree_contains_struct[VAR_DECL][TS_DECL_COMMON] = 1;
 245   tree_contains_struct[PARM_DECL][TS_DECL_COMMON] = 1;
 246   tree_contains_struct[RESULT_DECL][TS_DECL_COMMON] = 1;
 247   tree_contains_struct[FUNCTION_DECL][TS_DECL_COMMON] = 1;
 248   tree_contains_struct[TYPE_DECL][TS_DECL_COMMON] = 1;
 249   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_COMMON] = 1;
 250   tree_contains_struct[LABEL_DECL][TS_DECL_COMMON] = 1;
 251   tree_contains_struct[FIELD_DECL][TS_DECL_COMMON] = 1;
 252
 253
 254   tree_contains_struct[CONST_DECL][TS_DECL_WRTL] = 1;
 255   tree_contains_struct[VAR_DECL][TS_DECL_WRTL] = 1;
 256   tree_contains_struct[PARM_DECL][TS_DECL_WRTL] = 1;
 257   tree_contains_struct[RESULT_DECL][TS_DECL_WRTL] = 1;
 258   tree_contains_struct[FUNCTION_DECL][TS_DECL_WRTL] = 1;
 259   tree_contains_struct[LABEL_DECL][TS_DECL_WRTL] = 1;
 260
 261   tree_contains_struct[CONST_DECL][TS_DECL_MINIMAL] = 1;
 262   tree_contains_struct[VAR_DECL][TS_DECL_MINIMAL] = 1;
 263   tree_contains_struct[PARM_DECL][TS_DECL_MINIMAL] = 1;
 264   tree_contains_struct[RESULT_DECL][TS_DECL_MINIMAL] = 1;
 265   tree_contains_struct[FUNCTION_DECL][TS_DECL_MINIMAL] = 1;
 266   tree_contains_struct[TYPE_DECL][TS_DECL_MINIMAL] = 1;
 267   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_MINIMAL] = 1;
 268   tree_contains_struct[LABEL_DECL][TS_DECL_MINIMAL] = 1;
 269   tree_contains_struct[FIELD_DECL][TS_DECL_MINIMAL] = 1;
 270   tree_contains_struct[STRUCT_FIELD_TAG][TS_DECL_MINIMAL] = 1;
 271   tree_contains_struct[NAME_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
 272   tree_contains_struct[TYPE_MEMORY_TAG][TS_DECL_MINIMAL] = 1;
 273
 274   tree_contains_struct[STRUCT_FIELD_TAG][TS_MEMORY_TAG] = 1;
 275   tree_contains_struct[NAME_MEMORY_TAG][TS_MEMORY_TAG] = 1;
 276   tree_contains_struct[TYPE_MEMORY_TAG][TS_MEMORY_TAG] = 1;
 277
 278   tree_contains_struct[VAR_DECL][TS_DECL_WITH_VIS] = 1;
 279   tree_contains_struct[FUNCTION_DECL][TS_DECL_WITH_VIS] = 1;
 280   tree_contains_struct[TYPE_DECL][TS_DECL_WITH_VIS] = 1;
 281   tree_contains_struct[TRANSLATION_UNIT_DECL][TS_DECL_WITH_VIS] = 1;
 282
 283   tree_contains_struct[VAR_DECL][TS_VAR_DECL] = 1;
 284   tree_contains_struct[FIELD_DECL][TS_FIELD_DECL] = 1;
 285   tree_contains_struct[PARM_DECL][TS_PARM_DECL] = 1;
 286   tree_contains_struct[LABEL_DECL][TS_LABEL_DECL] = 1;
 287   tree_contains_struct[RESULT_DECL][TS_RESULT_DECL] = 1;
 288   tree_contains_struct[CONST_DECL][TS_CONST_DECL] = 1;
 289   tree_contains_struct[TYPE_DECL][TS_TYPE_DECL] = 1;
 290   tree_contains_struct[FUNCTION_DECL][TS_FUNCTION_DECL] = 1;
 291
 292   lang_hooks.init_ts ();
 293 }
 294
 295 \f
 296 /* The name of the object as the assembler will see it (but before any
 297    translations made by ASM_OUTPUT_LABELREF).  Often this is the same
 298    as DECL_NAME.  It is an IDENTIFIER_NODE.  */
 299 tree
 300 decl_assembler_name (tree decl)
 301 {
 302   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
 303     lang_hooks.set_decl_assembler_name (decl);
 304   return DECL_WITH_VIS_CHECK (decl)->decl_with_vis.assembler_name;
 305 }
 306
 307 /* Compute the number of bytes occupied by a tree with code CODE.
 308    This function cannot be used for TREE_VEC, PHI_NODE, or STRING_CST
 309    codes, which are of variable length.  */
 310 size_t
 311 tree_code_size (enum tree_code code)
 312 {
 313   switch (TREE_CODE_CLASS (code))
 314     {
 315     case tcc_declaration:  /* A decl node */
 316       {
 317         switch (code)
 318           {
 319           case FIELD_DECL:
 320             return sizeof (struct tree_field_decl);
 321           case PARM_DECL:
 322             return sizeof (struct tree_parm_decl);
 323           case VAR_DECL:
 324             return sizeof (struct tree_var_decl);
 325           case LABEL_DECL:
 326             return sizeof (struct tree_label_decl);
 327           case RESULT_DECL:
 328             return sizeof (struct tree_result_decl);
 329           case CONST_DECL:
 330             return sizeof (struct tree_const_decl);
 331           case TYPE_DECL:
 332             return sizeof (struct tree_type_decl);
 333           case FUNCTION_DECL:
 334             return sizeof (struct tree_function_decl);
 335           case NAME_MEMORY_TAG:
 336           case TYPE_MEMORY_TAG:
 337           case STRUCT_FIELD_TAG:
 338             return sizeof (struct tree_memory_tag);
 339           default:
 340             return sizeof (struct tree_decl_non_common);
 341           }
 342       }
 343
 344     case tcc_type:  /* a type node */
 345       return sizeof (struct tree_type);
 346
 347     case tcc_reference:   /* a reference */
 348     case tcc_expression:  /* an expression */
 349     case tcc_statement:   /* an expression with side effects */
 350     case tcc_comparison:  /* a comparison expression */
 351     case tcc_unary:       /* a unary arithmetic expression */
 352     case tcc_binary:      /* a binary arithmetic expression */
 353       return (sizeof (struct tree_exp)
 354               + (TREE_CODE_LENGTH (code) - 1) * sizeof (char *));
 355
 356     case tcc_constant:  /* a constant */
 357       switch (code)
 358         {
 359         case INTEGER_CST:       return sizeof (struct tree_int_cst);
 360         case REAL_CST:          return sizeof (struct tree_real_cst);
 361         case COMPLEX_CST:       return sizeof (struct tree_complex);
 362         case VECTOR_CST:        return sizeof (struct tree_vector);
 363         case STRING_CST:        gcc_unreachable ();
 364         default:
 365           return lang_hooks.tree_size (code);
 366         }
 367
 368     case tcc_exceptional:  /* something random, like an identifier.  */
 369       switch (code)
 370         {
 371         case IDENTIFIER_NODE:   return lang_hooks.identifier_size;
 372         case TREE_LIST:         return sizeof (struct tree_list);
 373
 374         case ERROR_MARK:
 375         case PLACEHOLDER_EXPR:  return sizeof (struct tree_common);
 376
 377         case TREE_VEC:
 378         case OMP_CLAUSE:
 379         case PHI_NODE:          gcc_unreachable ();
 380
 381         case SSA_NAME:          return sizeof (struct tree_ssa_name);
 382
 383         case STATEMENT_LIST:    return sizeof (struct tree_statement_list);
 384         case BLOCK:             return sizeof (struct tree_block);
 385         case VALUE_HANDLE:      return sizeof (struct tree_value_handle);
 386         case CONSTRUCTOR:       return sizeof (struct tree_constructor);
 387
 388         default:
 389           return lang_hooks.tree_size (code);
 390         }
 391
 392     default:
 393       gcc_unreachable ();
 394     }
 395 }
 396
 397 /* Compute the number of bytes occupied by NODE.  This routine only
 398    looks at TREE_CODE, except for PHI_NODE and TREE_VEC nodes.  */
 399 size_t
 400 tree_size (tree node)
 401 {
 402   enum tree_code code = TREE_CODE (node);
 403   switch (code)
 404     {
 405     case PHI_NODE:
 406       return (sizeof (struct tree_phi_node)
 407               + (PHI_ARG_CAPACITY (node) - 1) * sizeof (struct phi_arg_d));
 408
 409     case TREE_BINFO:
 410       return (offsetof (struct tree_binfo, base_binfos)
 411               + VEC_embedded_size (tree, BINFO_N_BASE_BINFOS (node)));
 412
 413     case TREE_VEC:
 414       return (sizeof (struct tree_vec)
 415               + (TREE_VEC_LENGTH (node) - 1) * sizeof(char *));
 416
 417     case STRING_CST:
 418       return sizeof (struct tree_string) + TREE_STRING_LENGTH (node) - 1;
 419
 420     case OMP_CLAUSE:
 421       return (sizeof (struct tree_omp_clause)
 422               + (omp_clause_num_ops[OMP_CLAUSE_CODE (node)] - 1)
 423                 * sizeof (tree));
 424
 425     default:
 426       return tree_code_size (code);
 427     }
 428 }
 429
 430 /* Return a newly allocated node of code CODE.  For decl and type
 431    nodes, some other fields are initialized.  The rest of the node is
 432    initialized to zero.  This function cannot be used for PHI_NODE,
 433    TREE_VEC or OMP_CLAUSE nodes, which is enforced by asserts in
 434    tree_code_size.
 435
 436    Achoo!  I got a code in the node.  */
 437
 438 tree
 439 make_node_stat (enum tree_code code MEM_STAT_DECL)
 440 {
 441   tree t;
 442   enum tree_code_class type = TREE_CODE_CLASS (code);
 443   size_t length = tree_code_size (code);
 444 #ifdef GATHER_STATISTICS
 445   tree_node_kind kind;
 446
 447   switch (type)
 448     {
 449     case tcc_declaration:  /* A decl node */
 450       kind = d_kind;
 451       break;
 452
 453     case tcc_type:  /* a type node */
 454       kind = t_kind;
 455       break;
 456
 457     case tcc_statement:  /* an expression with side effects */
 458       kind = s_kind;
 459       break;
 460
 461     case tcc_reference:  /* a reference */
 462       kind = r_kind;
 463       break;
 464
 465     case tcc_expression:  /* an expression */
 466     case tcc_comparison:  /* a comparison expression */
 467     case tcc_unary:  /* a unary arithmetic expression */
 468     case tcc_binary:  /* a binary arithmetic expression */
 469       kind = e_kind;
 470       break;
 471
 472     case tcc_constant:  /* a constant */
 473       kind = c_kind;
 474       break;
 475
 476     case tcc_exceptional:  /* something random, like an identifier.  */
 477       switch (code)
 478         {
 479         case IDENTIFIER_NODE:
 480           kind = id_kind;
 481           break;
 482
 483         case TREE_VEC:
 484           kind = vec_kind;
 485           break;
 486
 487         case TREE_BINFO:
 488           kind = binfo_kind;
 489           break;
 490
 491         case PHI_NODE:
 492           kind = phi_kind;
 493           break;
 494
 495         case SSA_NAME:
 496           kind = ssa_name_kind;
 497           break;
 498
 499         case BLOCK:
 500           kind = b_kind;
 501           break;
 502
 503         case CONSTRUCTOR:
 504           kind = constr_kind;
 505           break;
 506
 507         default:
 508           kind = x_kind;
 509           break;
 510         }
 511       break;
 512
 513     default:
 514       gcc_unreachable ();
 515     }
 516
 517   tree_node_counts[(int) kind]++;
 518   tree_node_sizes[(int) kind] += length;
 519 #endif
 520
 521   if (code == IDENTIFIER_NODE)
 522     t = ggc_alloc_zone_pass_stat (length, &tree_id_zone);
 523   else
 524     t = ggc_alloc_zone_pass_stat (length, &tree_zone);
 525
 526   memset (t, 0, length);
 527
 528   TREE_SET_CODE (t, code);
 529
 530   switch (type)
 531     {
 532     case tcc_statement:
 533       TREE_SIDE_EFFECTS (t) = 1;
 534       break;
 535
 536     case tcc_declaration:
 537       if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
 538         DECL_IN_SYSTEM_HEADER (t) = in_system_header;
 539       if (CODE_CONTAINS_STRUCT (code, TS_DECL_COMMON))
 540         {
 541           if (code != FUNCTION_DECL)
 542             DECL_ALIGN (t) = 1;
 543           DECL_USER_ALIGN (t) = 0;
 544           /* We have not yet computed the alias set for this declaration.  */
 545           DECL_POINTER_ALIAS_SET (t) = -1;
 546         }
 547       DECL_SOURCE_LOCATION (t) = input_location;
 548       DECL_UID (t) = next_decl_uid++;
 549
 550       break;
 551
 552     case tcc_type:
 553       TYPE_UID (t) = next_type_uid++;
 554       TYPE_ALIGN (t) = BITS_PER_UNIT;
 555       TYPE_USER_ALIGN (t) = 0;
 556       TYPE_MAIN_VARIANT (t) = t;
 557
 558       /* Default to no attributes for type, but let target change that.  */
 559       TYPE_ATTRIBUTES (t) = NULL_TREE;
 560       targetm.set_default_type_attributes (t);
 561
 562       /* We have not yet computed the alias set for this type.  */
 563       TYPE_ALIAS_SET (t) = -1;
 564       break;
 565
 566     case tcc_constant:
 567       TREE_CONSTANT (t) = 1;
 568       TREE_INVARIANT (t) = 1;
 569       break;
 570
 571     case tcc_expression:
 572       switch (code)
 573         {
 574         case INIT_EXPR:
 575         case MODIFY_EXPR:
 576         case VA_ARG_EXPR:
 577         case PREDECREMENT_EXPR:
 578         case PREINCREMENT_EXPR:
 579         case POSTDECREMENT_EXPR:
 580         case POSTINCREMENT_EXPR:
 581           /* All of these have side-effects, no matter what their
 582              operands are.  */
 583           TREE_SIDE_EFFECTS (t) = 1;
 584           break;
 585
 586         default:
 587           break;
 588         }
 589       break;
 590
 591     default:
 592       /* Other classes need no special treatment.  */
 593       break;
 594     }
 595
 596   return t;
 597 }
 598 \f
 599 /* Return a new node with the same contents as NODE except that its
 600    TREE_CHAIN is zero and it has a fresh uid.  */
 601
 602 tree
 603 copy_node_stat (tree node MEM_STAT_DECL)
 604 {
 605   tree t;
 606   enum tree_code code = TREE_CODE (node);
 607   size_t length;
 608
 609   gcc_assert (code != STATEMENT_LIST);
 610
 611   length = tree_size (node);
 612   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
 613   memcpy (t, node, length);
 614
 615   TREE_CHAIN (t) = 0;
 616   TREE_ASM_WRITTEN (t) = 0;
 617   TREE_VISITED (t) = 0;
 618   t->common.ann = 0;
 619
 620   if (TREE_CODE_CLASS (code) == tcc_declaration)
 621     {
 622       DECL_UID (t) = next_decl_uid++;
 623       if ((TREE_CODE (node) == PARM_DECL || TREE_CODE (node) == VAR_DECL)
 624           && DECL_HAS_VALUE_EXPR_P (node))
 625         {
 626           SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (node));
 627           DECL_HAS_VALUE_EXPR_P (t) = 1;
 628         }
 629       if (TREE_CODE (node) == VAR_DECL && DECL_HAS_INIT_PRIORITY_P (node))
 630         {
 631           SET_DECL_INIT_PRIORITY (t, DECL_INIT_PRIORITY (node));
 632           DECL_HAS_INIT_PRIORITY_P (t) = 1;
 633         }
 634       if (TREE_CODE (node) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (node))
 635         {
 636           SET_DECL_RESTRICT_BASE (t, DECL_GET_RESTRICT_BASE (node));
 637           DECL_BASED_ON_RESTRICT_P (t) = 1;
 638         }
 639     }
 640   else if (TREE_CODE_CLASS (code) == tcc_type)
 641     {
 642       TYPE_UID (t) = next_type_uid++;
 643       /* The following is so that the debug code for
 644          the copy is different from the original type.
 645          The two statements usually duplicate each other
 646          (because they clear fields of the same union),
 647          but the optimizer should catch that.  */
 648       TYPE_SYMTAB_POINTER (t) = 0;
 649       TYPE_SYMTAB_ADDRESS (t) = 0;
 650
 651       /* Do not copy the values cache.  */
 652       if (TYPE_CACHED_VALUES_P(t))
 653         {
 654           TYPE_CACHED_VALUES_P (t) = 0;
 655           TYPE_CACHED_VALUES (t) = NULL_TREE;
 656         }
 657     }
 658
 659   return t;
 660 }
 661
 662 /* Return a copy of a chain of nodes, chained through the TREE_CHAIN field.
 663    For example, this can copy a list made of TREE_LIST nodes.  */
 664
 665 tree
 666 copy_list (tree list)
 667 {
 668   tree head;
 669   tree prev, next;
 670
 671   if (list == 0)
 672     return 0;
 673
 674   head = prev = copy_node (list);
 675   next = TREE_CHAIN (list);
 676   while (next)
 677     {
 678       TREE_CHAIN (prev) = copy_node (next);
 679       prev = TREE_CHAIN (prev);
 680       next = TREE_CHAIN (next);
 681     }
 682   return head;
 683 }
 684
 685 \f
 686 /* Create an INT_CST node with a LOW value sign extended.  */
 687
 688 tree
 689 build_int_cst (tree type, HOST_WIDE_INT low)
 690 {
 691   return build_int_cst_wide (type, low, low < 0 ? -1 : 0);
 692 }
 693
 694 /* Create an INT_CST node with a LOW value zero extended.  */
 695
 696 tree
 697 build_int_cstu (tree type, unsigned HOST_WIDE_INT low)
 698 {
 699   return build_int_cst_wide (type, low, 0);
 700 }
 701
 702 /* Create an INT_CST node with a LOW value in TYPE.  The value is sign extended
 703    if it is negative.  This function is similar to build_int_cst, but
 704    the extra bits outside of the type precision are cleared.  Constants
 705    with these extra bits may confuse the fold so that it detects overflows
 706    even in cases when they do not occur, and in general should be avoided.
 707    We cannot however make this a default behavior of build_int_cst without
 708    more intrusive changes, since there are parts of gcc that rely on the extra
 709    precision of the integer constants.  */
 710
 711 tree
 712 build_int_cst_type (tree type, HOST_WIDE_INT low)
 713 {
 714   unsigned HOST_WIDE_INT val = (unsigned HOST_WIDE_INT) low;
 715   unsigned HOST_WIDE_INT hi, mask;
 716   unsigned bits;
 717   bool signed_p;
 718   bool negative;
 719
 720   if (!type)
 721     type = integer_type_node;
 722
 723   bits = TYPE_PRECISION (type);
 724   signed_p = !TYPE_UNSIGNED (type);
 725
 726   if (bits >= HOST_BITS_PER_WIDE_INT)
 727     negative = (low < 0);
 728   else
 729     {
 730       /* If the sign bit is inside precision of LOW, use it to determine
 731          the sign of the constant.  */
 732       negative = ((val >> (bits - 1)) & 1) != 0;
 733
 734       /* Mask out the bits outside of the precision of the constant.  */
 735       mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
 736
 737       if (signed_p && negative)
 738         val |= ~mask;
 739       else
 740         val &= mask;
 741     }
 742
 743   /* Determine the high bits.  */
 744   hi = (negative ? ~(unsigned HOST_WIDE_INT) 0 : 0);
 745
 746   /* For unsigned type we need to mask out the bits outside of the type
 747      precision.  */
 748   if (!signed_p)
 749     {
 750       if (bits <= HOST_BITS_PER_WIDE_INT)
 751         hi = 0;
 752       else
 753         {
 754           bits -= HOST_BITS_PER_WIDE_INT;
 755           mask = (((unsigned HOST_WIDE_INT) 2) << (bits - 1)) - 1;
 756           hi &= mask;
 757         }
 758     }
 759
 760   return build_int_cst_wide (type, val, hi);
 761 }
 762
 763 /* These are the hash table functions for the hash table of INTEGER_CST
 764    nodes of a sizetype.  */
 765
 766 /* Return the hash code code X, an INTEGER_CST.  */
 767
 768 static hashval_t
 769 int_cst_hash_hash (const void *x)
 770 {
 771   tree t = (tree) x;
 772
 773   return (TREE_INT_CST_HIGH (t) ^ TREE_INT_CST_LOW (t)
 774           ^ htab_hash_pointer (TREE_TYPE (t)));
 775 }
 776
 777 /* Return nonzero if the value represented by *X (an INTEGER_CST tree node)
 778    is the same as that given by *Y, which is the same.  */
 779
 780 static int
 781 int_cst_hash_eq (const void *x, const void *y)
 782 {
 783   tree xt = (tree) x;
 784   tree yt = (tree) y;
 785
 786   return (TREE_TYPE (xt) == TREE_TYPE (yt)
 787           && TREE_INT_CST_HIGH (xt) == TREE_INT_CST_HIGH (yt)
 788           && TREE_INT_CST_LOW (xt) == TREE_INT_CST_LOW (yt));
 789 }
 790
 791 /* Create an INT_CST node of TYPE and value HI:LOW.  If TYPE is NULL,
 792    integer_type_node is used.  The returned node is always shared.
 793    For small integers we use a per-type vector cache, for larger ones
 794    we use a single hash table.  */
 795
 796 tree
 797 build_int_cst_wide (tree type, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi)
 798 {
 799   tree t;
 800   int ix = -1;
 801   int limit = 0;
 802
 803   if (!type)
 804     type = integer_type_node;
 805
 806   switch (TREE_CODE (type))
 807     {
 808     case POINTER_TYPE:
 809     case REFERENCE_TYPE:
 810       /* Cache NULL pointer.  */
 811       if (!hi && !low)
 812         {
 813           limit = 1;
 814           ix = 0;
 815         }
 816       break;
 817
 818     case BOOLEAN_TYPE:
 819       /* Cache false or true.  */
 820       limit = 2;
 821       if (!hi && low < 2)
 822         ix = low;
 823       break;
 824
 825     case INTEGER_TYPE:
 826     case CHAR_TYPE:
 827     case OFFSET_TYPE:
 828       if (TYPE_UNSIGNED (type))
 829         {
 830           /* Cache 0..N */
 831           limit = INTEGER_SHARE_LIMIT;
 832           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 833             ix = low;
 834         }
 835       else
 836         {
 837           /* Cache -1..N */
 838           limit = INTEGER_SHARE_LIMIT + 1;
 839           if (!hi && low < (unsigned HOST_WIDE_INT)INTEGER_SHARE_LIMIT)
 840             ix = low + 1;
 841           else if (hi == -1 && low == -(unsigned HOST_WIDE_INT)1)
 842             ix = 0;
 843         }
 844       break;
 845     default:
 846       break;
 847     }
 848
 849   if (ix >= 0)
 850     {
 851       /* Look for it in the type's vector of small shared ints.  */
 852       if (!TYPE_CACHED_VALUES_P (type))
 853         {
 854           TYPE_CACHED_VALUES_P (type) = 1;
 855           TYPE_CACHED_VALUES (type) = make_tree_vec (limit);
 856         }
 857
 858       t = TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix);
 859       if (t)
 860         {
 861           /* Make sure no one is clobbering the shared constant.  */
 862           gcc_assert (TREE_TYPE (t) == type);
 863           gcc_assert (TREE_INT_CST_LOW (t) == low);
 864           gcc_assert (TREE_INT_CST_HIGH (t) == hi);
 865         }
 866       else
 867         {
 868           /* Create a new shared int.  */
 869           t = make_node (INTEGER_CST);
 870
 871           TREE_INT_CST_LOW (t) = low;
 872           TREE_INT_CST_HIGH (t) = hi;
 873           TREE_TYPE (t) = type;
 874
 875           TREE_VEC_ELT (TYPE_CACHED_VALUES (type), ix) = t;
 876         }
 877     }
 878   else
 879     {
 880       /* Use the cache of larger shared ints.  */
 881       void **slot;
 882
 883       TREE_INT_CST_LOW (int_cst_node) = low;
 884       TREE_INT_CST_HIGH (int_cst_node) = hi;
 885       TREE_TYPE (int_cst_node) = type;
 886
 887       slot = htab_find_slot (int_cst_hash_table, int_cst_node, INSERT);
 888       t = *slot;
 889       if (!t)
 890         {
 891           /* Insert this one into the hash table.  */
 892           t = int_cst_node;
 893           *slot = t;
 894           /* Make a new node for next time round.  */
 895           int_cst_node = make_node (INTEGER_CST);
 896         }
 897     }
 898
 899   return t;
 900 }
 901
 902 /* Builds an integer constant in TYPE such that lowest BITS bits are ones
 903    and the rest are zeros.  */
 904
 905 tree
 906 build_low_bits_mask (tree type, unsigned bits)
 907 {
 908   unsigned HOST_WIDE_INT low;
 909   HOST_WIDE_INT high;
 910   unsigned HOST_WIDE_INT all_ones = ~(unsigned HOST_WIDE_INT) 0;
 911
 912   gcc_assert (bits <= TYPE_PRECISION (type));
 913
 914   if (bits == TYPE_PRECISION (type)
 915       && !TYPE_UNSIGNED (type))
 916     {
 917       /* Sign extended all-ones mask.  */
 918       low = all_ones;
 919       high = -1;
 920     }
 921   else if (bits <= HOST_BITS_PER_WIDE_INT)
 922     {
 923       low = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
 924       high = 0;
 925     }
 926   else
 927     {
 928       bits -= HOST_BITS_PER_WIDE_INT;
 929       low = all_ones;
 930       high = all_ones >> (HOST_BITS_PER_WIDE_INT - bits);
 931     }
 932
 933   return build_int_cst_wide (type, low, high);
 934 }
 935
 936 /* Checks that X is integer constant that can be expressed in (unsigned)
 937    HOST_WIDE_INT without loss of precision.  */
 938
 939 bool
 940 cst_and_fits_in_hwi (tree x)
 941 {
 942   if (TREE_CODE (x) != INTEGER_CST)
 943     return false;
 944
 945   if (TYPE_PRECISION (TREE_TYPE (x)) > HOST_BITS_PER_WIDE_INT)
 946     return false;
 947
 948   return (TREE_INT_CST_HIGH (x) == 0
 949           || TREE_INT_CST_HIGH (x) == -1);
 950 }
 951
 952 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 953    are in a list pointed to by VALS.  */
 954
 955 tree
 956 build_vector (tree type, tree vals)
 957 {
 958   tree v = make_node (VECTOR_CST);
 959   int over1 = 0, over2 = 0;
 960   tree link;
 961
 962   TREE_VECTOR_CST_ELTS (v) = vals;
 963   TREE_TYPE (v) = type;
 964
 965   /* Iterate through elements and check for overflow.  */
 966   for (link = vals; link; link = TREE_CHAIN (link))
 967     {
 968       tree value = TREE_VALUE (link);
 969
 970       over1 |= TREE_OVERFLOW (value);
 971       over2 |= TREE_CONSTANT_OVERFLOW (value);
 972     }
 973
 974   TREE_OVERFLOW (v) = over1;
 975   TREE_CONSTANT_OVERFLOW (v) = over2;
 976
 977   return v;
 978 }
 979
 980 /* Return a new VECTOR_CST node whose type is TYPE and whose values
 981    are extracted from V, a vector of CONSTRUCTOR_ELT.  */
 982
 983 tree
 984 build_vector_from_ctor (tree type, VEC(constructor_elt,gc) *v)
 985 {
 986   tree list = NULL_TREE;
 987   unsigned HOST_WIDE_INT idx;
 988   tree value;
 989
 990   FOR_EACH_CONSTRUCTOR_VALUE (v, idx, value)
 991     list = tree_cons (NULL_TREE, value, list);
 992   return build_vector (type, nreverse (list));
 993 }
 994
 995 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
 996    are in the VEC pointed to by VALS.  */
 997 tree
 998 build_constructor (tree type, VEC(constructor_elt,gc) *vals)
 999 {
1000   tree c = make_node (CONSTRUCTOR);
1001   TREE_TYPE (c) = type;
1002   CONSTRUCTOR_ELTS (c) = vals;
1003   return c;
1004 }
1005
1006 /* Build a CONSTRUCTOR node made of a single initializer, with the specified
1007    INDEX and VALUE.  */
1008 tree
1009 build_constructor_single (tree type, tree index, tree value)
1010 {
1011   VEC(constructor_elt,gc) *v;
1012   constructor_elt *elt;
1013
1014   v = VEC_alloc (constructor_elt, gc, 1);
1015   elt = VEC_quick_push (constructor_elt, v, NULL);
1016   elt->index = index;
1017   elt->value = value;
1018
1019   return build_constructor (type, v);
1020 }
1021
1022
1023 /* Return a new CONSTRUCTOR node whose type is TYPE and whose values
1024    are in a list pointed to by VALS.  */
1025 tree
1026 build_constructor_from_list (tree type, tree vals)
1027 {
1028   tree t;
1029   VEC(constructor_elt,gc) *v = NULL;
1030
1031   if (vals)
1032     {
1033       v = VEC_alloc (constructor_elt, gc, list_length (vals));
1034       for (t = vals; t; t = TREE_CHAIN (t))
1035         {
1036           constructor_elt *elt = VEC_quick_push (constructor_elt, v, NULL);
1037           elt->index = TREE_PURPOSE (t);
1038           elt->value = TREE_VALUE (t);
1039         }
1040     }
1041
1042   return build_constructor (type, v);
1043 }
1044
1045
1046 /* Return a new REAL_CST node whose type is TYPE and value is D.  */
1047
1048 tree
1049 build_real (tree type, REAL_VALUE_TYPE d)
1050 {
1051   tree v;
1052   REAL_VALUE_TYPE *dp;
1053   int overflow = 0;
1054
1055   /* ??? Used to check for overflow here via CHECK_FLOAT_TYPE.
1056      Consider doing it via real_convert now.  */
1057
1058   v = make_node (REAL_CST);
1059   dp = ggc_alloc (sizeof (REAL_VALUE_TYPE));
1060   memcpy (dp, &d, sizeof (REAL_VALUE_TYPE));
1061
1062   TREE_TYPE (v) = type;
1063   TREE_REAL_CST_PTR (v) = dp;
1064   TREE_OVERFLOW (v) = TREE_CONSTANT_OVERFLOW (v) = overflow;
1065   return v;
1066 }
1067
1068 /* Return a new REAL_CST node whose type is TYPE
1069    and whose value is the integer value of the INTEGER_CST node I.  */
1070
1071 REAL_VALUE_TYPE
1072 real_value_from_int_cst (tree type, tree i)
1073 {
1074   REAL_VALUE_TYPE d;
1075
1076   /* Clear all bits of the real value type so that we can later do
1077      bitwise comparisons to see if two values are the same.  */
1078   memset (&d, 0, sizeof d);
1079
1080   real_from_integer (&d, type ? TYPE_MODE (type) : VOIDmode,
1081                      TREE_INT_CST_LOW (i), TREE_INT_CST_HIGH (i),
1082                      TYPE_UNSIGNED (TREE_TYPE (i)));
1083   return d;
1084 }
1085
1086 /* Given a tree representing an integer constant I, return a tree
1087    representing the same value as a floating-point constant of type TYPE.  */
1088
1089 tree
1090 build_real_from_int_cst (tree type, tree i)
1091 {
1092   tree v;
1093   int overflow = TREE_OVERFLOW (i);
1094
1095   v = build_real (type, real_value_from_int_cst (type, i));
1096
1097   TREE_OVERFLOW (v) |= overflow;
1098   TREE_CONSTANT_OVERFLOW (v) |= overflow;
1099   return v;
1100 }
1101
1102 /* Return a newly constructed STRING_CST node whose value is
1103    the LEN characters at STR.
1104    The TREE_TYPE is not initialized.  */
1105
1106 tree
1107 build_string (int len, const char *str)
1108 {
1109   tree s;
1110   size_t length;
1111
1112   length = len + sizeof (struct tree_string);
1113
1114 #ifdef GATHER_STATISTICS
1115   tree_node_counts[(int) c_kind]++;
1116   tree_node_sizes[(int) c_kind] += length;
1117 #endif
1118
1119   s = ggc_alloc_tree (length);
1120
1121   memset (s, 0, sizeof (struct tree_common));
1122   TREE_SET_CODE (s, STRING_CST);
1123   TREE_CONSTANT (s) = 1;
1124   TREE_INVARIANT (s) = 1;
1125   TREE_STRING_LENGTH (s) = len;
1126   memcpy ((char *) TREE_STRING_POINTER (s), str, len);
1127   ((char *) TREE_STRING_POINTER (s))[len] = '\0';
1128
1129   return s;
1130 }
1131
1132 /* Return a newly constructed COMPLEX_CST node whose value is
1133    specified by the real and imaginary parts REAL and IMAG.
1134    Both REAL and IMAG should be constant nodes.  TYPE, if specified,
1135    will be the type of the COMPLEX_CST; otherwise a new type will be made.  */
1136
1137 tree
1138 build_complex (tree type, tree real, tree imag)
1139 {
1140   tree t = make_node (COMPLEX_CST);
1141
1142   TREE_REALPART (t) = real;
1143   TREE_IMAGPART (t) = imag;
1144   TREE_TYPE (t) = type ? type : build_complex_type (TREE_TYPE (real));
1145   TREE_OVERFLOW (t) = TREE_OVERFLOW (real) | TREE_OVERFLOW (imag);
1146   TREE_CONSTANT_OVERFLOW (t)
1147     = TREE_CONSTANT_OVERFLOW (real) | TREE_CONSTANT_OVERFLOW (imag);
1148   return t;
1149 }
1150
1151 /* Build a BINFO with LEN language slots.  */
1152
1153 tree
1154 make_tree_binfo_stat (unsigned base_binfos MEM_STAT_DECL)
1155 {
1156   tree t;
1157   size_t length = (offsetof (struct tree_binfo, base_binfos)
1158                    + VEC_embedded_size (tree, base_binfos));
1159
1160 #ifdef GATHER_STATISTICS
1161   tree_node_counts[(int) binfo_kind]++;
1162   tree_node_sizes[(int) binfo_kind] += length;
1163 #endif
1164
1165   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1166
1167   memset (t, 0, offsetof (struct tree_binfo, base_binfos));
1168
1169   TREE_SET_CODE (t, TREE_BINFO);
1170
1171   VEC_embedded_init (tree, BINFO_BASE_BINFOS (t), base_binfos);
1172
1173   return t;
1174 }
1175
1176
1177 /* Build a newly constructed TREE_VEC node of length LEN.  */
1178
1179 tree
1180 make_tree_vec_stat (int len MEM_STAT_DECL)
1181 {
1182   tree t;
1183   int length = (len - 1) * sizeof (tree) + sizeof (struct tree_vec);
1184
1185 #ifdef GATHER_STATISTICS
1186   tree_node_counts[(int) vec_kind]++;
1187   tree_node_sizes[(int) vec_kind] += length;
1188 #endif
1189
1190   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
1191
1192   memset (t, 0, length);
1193
1194   TREE_SET_CODE (t, TREE_VEC);
1195   TREE_VEC_LENGTH (t) = len;
1196
1197   return t;
1198 }
1199 \f
1200 /* Return 1 if EXPR is the integer constant zero or a complex constant
1201    of zero.  */
1202
1203 int
1204 integer_zerop (tree expr)
1205 {
1206   STRIP_NOPS (expr);
1207
1208   return ((TREE_CODE (expr) == INTEGER_CST
1209            && ! TREE_CONSTANT_OVERFLOW (expr)
1210            && TREE_INT_CST_LOW (expr) == 0
1211            && TREE_INT_CST_HIGH (expr) == 0)
1212           || (TREE_CODE (expr) == COMPLEX_CST
1213               && integer_zerop (TREE_REALPART (expr))
1214               && integer_zerop (TREE_IMAGPART (expr))));
1215 }
1216
1217 /* Return 1 if EXPR is the integer constant one or the corresponding
1218    complex constant.  */
1219
1220 int
1221 integer_onep (tree expr)
1222 {
1223   STRIP_NOPS (expr);
1224
1225   return ((TREE_CODE (expr) == INTEGER_CST
1226            && ! TREE_CONSTANT_OVERFLOW (expr)
1227            && TREE_INT_CST_LOW (expr) == 1
1228            && TREE_INT_CST_HIGH (expr) == 0)
1229           || (TREE_CODE (expr) == COMPLEX_CST
1230               && integer_onep (TREE_REALPART (expr))
1231               && integer_zerop (TREE_IMAGPART (expr))));
1232 }
1233
1234 /* Return 1 if EXPR is an integer containing all 1's in as much precision as
1235    it contains.  Likewise for the corresponding complex constant.  */
1236
1237 int
1238 integer_all_onesp (tree expr)
1239 {
1240   int prec;
1241   int uns;
1242
1243   STRIP_NOPS (expr);
1244
1245   if (TREE_CODE (expr) == COMPLEX_CST
1246       && integer_all_onesp (TREE_REALPART (expr))
1247       && integer_zerop (TREE_IMAGPART (expr)))
1248     return 1;
1249
1250   else if (TREE_CODE (expr) != INTEGER_CST
1251            || TREE_CONSTANT_OVERFLOW (expr))
1252     return 0;
1253
1254   uns = TYPE_UNSIGNED (TREE_TYPE (expr));
1255   if (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1256       && TREE_INT_CST_HIGH (expr) == -1)
1257     return 1;
1258   if (!uns)
1259     return 0;
1260
1261   /* Note that using TYPE_PRECISION here is wrong.  We care about the
1262      actual bits, not the (arbitrary) range of the type.  */
1263   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (expr)));
1264   if (prec >= HOST_BITS_PER_WIDE_INT)
1265     {
1266       HOST_WIDE_INT high_value;
1267       int shift_amount;
1268
1269       shift_amount = prec - HOST_BITS_PER_WIDE_INT;
1270
1271       /* Can not handle precisions greater than twice the host int size.  */
1272       gcc_assert (shift_amount <= HOST_BITS_PER_WIDE_INT);
1273       if (shift_amount == HOST_BITS_PER_WIDE_INT)
1274         /* Shifting by the host word size is undefined according to the ANSI
1275            standard, so we must handle this as a special case.  */
1276         high_value = -1;
1277       else
1278         high_value = ((HOST_WIDE_INT) 1 << shift_amount) - 1;
1279
1280       return (TREE_INT_CST_LOW (expr) == ~(unsigned HOST_WIDE_INT) 0
1281               && TREE_INT_CST_HIGH (expr) == high_value);
1282     }
1283   else
1284     return TREE_INT_CST_LOW (expr) == ((unsigned HOST_WIDE_INT) 1 << prec) - 1;
1285 }
1286
1287 /* Return 1 if EXPR is an integer constant that is a power of 2 (i.e., has only
1288    one bit on).  */
1289
1290 int
1291 integer_pow2p (tree expr)
1292 {
1293   int prec;
1294   HOST_WIDE_INT high, low;
1295
1296   STRIP_NOPS (expr);
1297
1298   if (TREE_CODE (expr) == COMPLEX_CST
1299       && integer_pow2p (TREE_REALPART (expr))
1300       && integer_zerop (TREE_IMAGPART (expr)))
1301     return 1;
1302
1303   if (TREE_CODE (expr) != INTEGER_CST || TREE_CONSTANT_OVERFLOW (expr))
1304     return 0;
1305
1306   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1307           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1308   high = TREE_INT_CST_HIGH (expr);
1309   low = TREE_INT_CST_LOW (expr);
1310
1311   /* First clear all bits that are beyond the type's precision in case
1312      we've been sign extended.  */
1313
1314   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1315     ;
1316   else if (prec > HOST_BITS_PER_WIDE_INT)
1317     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1318   else
1319     {
1320       high = 0;
1321       if (prec < HOST_BITS_PER_WIDE_INT)
1322         low &= ~((HOST_WIDE_INT) (-1) << prec);
1323     }
1324
1325   if (high == 0 && low == 0)
1326     return 0;
1327
1328   return ((high == 0 && (low & (low - 1)) == 0)
1329           || (low == 0 && (high & (high - 1)) == 0));
1330 }
1331
1332 /* Return 1 if EXPR is an integer constant other than zero or a
1333    complex constant other than zero.  */
1334
1335 int
1336 integer_nonzerop (tree expr)
1337 {
1338   STRIP_NOPS (expr);
1339
1340   return ((TREE_CODE (expr) == INTEGER_CST
1341            && ! TREE_CONSTANT_OVERFLOW (expr)
1342            && (TREE_INT_CST_LOW (expr) != 0
1343                || TREE_INT_CST_HIGH (expr) != 0))
1344           || (TREE_CODE (expr) == COMPLEX_CST
1345               && (integer_nonzerop (TREE_REALPART (expr))
1346                   || integer_nonzerop (TREE_IMAGPART (expr)))));
1347 }
1348
1349 /* Return the power of two represented by a tree node known to be a
1350    power of two.  */
1351
1352 int
1353 tree_log2 (tree expr)
1354 {
1355   int prec;
1356   HOST_WIDE_INT high, low;
1357
1358   STRIP_NOPS (expr);
1359
1360   if (TREE_CODE (expr) == COMPLEX_CST)
1361     return tree_log2 (TREE_REALPART (expr));
1362
1363   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1364           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1365
1366   high = TREE_INT_CST_HIGH (expr);
1367   low = TREE_INT_CST_LOW (expr);
1368
1369   /* First clear all bits that are beyond the type's precision in case
1370      we've been sign extended.  */
1371
1372   if (prec == 2 * HOST_BITS_PER_WIDE_INT)
1373     ;
1374   else if (prec > HOST_BITS_PER_WIDE_INT)
1375     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1376   else
1377     {
1378       high = 0;
1379       if (prec < HOST_BITS_PER_WIDE_INT)
1380         low &= ~((HOST_WIDE_INT) (-1) << prec);
1381     }
1382
1383   return (high != 0 ? HOST_BITS_PER_WIDE_INT + exact_log2 (high)
1384           : exact_log2 (low));
1385 }
1386
1387 /* Similar, but return the largest integer Y such that 2 ** Y is less
1388    than or equal to EXPR.  */
1389
1390 int
1391 tree_floor_log2 (tree expr)
1392 {
1393   int prec;
1394   HOST_WIDE_INT high, low;
1395
1396   STRIP_NOPS (expr);
1397
1398   if (TREE_CODE (expr) == COMPLEX_CST)
1399     return tree_log2 (TREE_REALPART (expr));
1400
1401   prec = (POINTER_TYPE_P (TREE_TYPE (expr))
1402           ? POINTER_SIZE : TYPE_PRECISION (TREE_TYPE (expr)));
1403
1404   high = TREE_INT_CST_HIGH (expr);
1405   low = TREE_INT_CST_LOW (expr);
1406
1407   /* First clear all bits that are beyond the type's precision in case
1408      we've been sign extended.  Ignore if type's precision hasn't been set
1409      since what we are doing is setting it.  */
1410
1411   if (prec == 2 * HOST_BITS_PER_WIDE_INT || prec == 0)
1412     ;
1413   else if (prec > HOST_BITS_PER_WIDE_INT)
1414     high &= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
1415   else
1416     {
1417       high = 0;
1418       if (prec < HOST_BITS_PER_WIDE_INT)
1419         low &= ~((HOST_WIDE_INT) (-1) << prec);
1420     }
1421
1422   return (high != 0 ? HOST_BITS_PER_WIDE_INT + floor_log2 (high)
1423           : floor_log2 (low));
1424 }
1425
1426 /* Return 1 if EXPR is the real constant zero.  */
1427
1428 int
1429 real_zerop (tree expr)
1430 {
1431   STRIP_NOPS (expr);
1432
1433   return ((TREE_CODE (expr) == REAL_CST
1434            && ! TREE_CONSTANT_OVERFLOW (expr)
1435            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst0))
1436           || (TREE_CODE (expr) == COMPLEX_CST
1437               && real_zerop (TREE_REALPART (expr))
1438               && real_zerop (TREE_IMAGPART (expr))));
1439 }
1440
1441 /* Return 1 if EXPR is the real constant one in real or complex form.  */
1442
1443 int
1444 real_onep (tree expr)
1445 {
1446   STRIP_NOPS (expr);
1447
1448   return ((TREE_CODE (expr) == REAL_CST
1449            && ! TREE_CONSTANT_OVERFLOW (expr)
1450            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst1))
1451           || (TREE_CODE (expr) == COMPLEX_CST
1452               && real_onep (TREE_REALPART (expr))
1453               && real_zerop (TREE_IMAGPART (expr))));
1454 }
1455
1456 /* Return 1 if EXPR is the real constant two.  */
1457
1458 int
1459 real_twop (tree expr)
1460 {
1461   STRIP_NOPS (expr);
1462
1463   return ((TREE_CODE (expr) == REAL_CST
1464            && ! TREE_CONSTANT_OVERFLOW (expr)
1465            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconst2))
1466           || (TREE_CODE (expr) == COMPLEX_CST
1467               && real_twop (TREE_REALPART (expr))
1468               && real_zerop (TREE_IMAGPART (expr))));
1469 }
1470
1471 /* Return 1 if EXPR is the real constant minus one.  */
1472
1473 int
1474 real_minus_onep (tree expr)
1475 {
1476   STRIP_NOPS (expr);
1477
1478   return ((TREE_CODE (expr) == REAL_CST
1479            && ! TREE_CONSTANT_OVERFLOW (expr)
1480            && REAL_VALUES_EQUAL (TREE_REAL_CST (expr), dconstm1))
1481           || (TREE_CODE (expr) == COMPLEX_CST
1482               && real_minus_onep (TREE_REALPART (expr))
1483               && real_zerop (TREE_IMAGPART (expr))));
1484 }
1485
1486 /* Nonzero if EXP is a constant or a cast of a constant.  */
1487
1488 int
1489 really_constant_p (tree exp)
1490 {
1491   /* This is not quite the same as STRIP_NOPS.  It does more.  */
1492   while (TREE_CODE (exp) == NOP_EXPR
1493          || TREE_CODE (exp) == CONVERT_EXPR
1494          || TREE_CODE (exp) == NON_LVALUE_EXPR)
1495     exp = TREE_OPERAND (exp, 0);
1496   return TREE_CONSTANT (exp);
1497 }
1498 \f
1499 /* Return first list element whose TREE_VALUE is ELEM.
1500    Return 0 if ELEM is not in LIST.  */
1501
1502 tree
1503 value_member (tree elem, tree list)
1504 {
1505   while (list)
1506     {
1507       if (elem == TREE_VALUE (list))
1508         return list;
1509       list = TREE_CHAIN (list);
1510     }
1511   return NULL_TREE;
1512 }
1513
1514 /* Return first list element whose TREE_PURPOSE is ELEM.
1515    Return 0 if ELEM is not in LIST.  */
1516
1517 tree
1518 purpose_member (tree elem, tree list)
1519 {
1520   while (list)
1521     {
1522       if (elem == TREE_PURPOSE (list))
1523         return list;
1524       list = TREE_CHAIN (list);
1525     }
1526   return NULL_TREE;
1527 }
1528
1529 /* Return nonzero if ELEM is part of the chain CHAIN.  */
1530
1531 int
1532 chain_member (tree elem, tree chain)
1533 {
1534   while (chain)
1535     {
1536       if (elem == chain)
1537         return 1;
1538       chain = TREE_CHAIN (chain);
1539     }
1540
1541   return 0;
1542 }
1543
1544 /* Return the length of a chain of nodes chained through TREE_CHAIN.
1545    We expect a null pointer to mark the end of the chain.
1546    This is the Lisp primitive `length'.  */
1547
1548 int
1549 list_length (tree t)
1550 {
1551   tree p = t;
1552 #ifdef ENABLE_TREE_CHECKING
1553   tree q = t;
1554 #endif
1555   int len = 0;
1556
1557   while (p)
1558     {
1559       p = TREE_CHAIN (p);
1560 #ifdef ENABLE_TREE_CHECKING
1561       if (len % 2)
1562         q = TREE_CHAIN (q);
1563       gcc_assert (p != q);
1564 #endif
1565       len++;
1566     }
1567
1568   return len;
1569 }
1570
1571 /* Returns the number of FIELD_DECLs in TYPE.  */
1572
1573 int
1574 fields_length (tree type)
1575 {
1576   tree t = TYPE_FIELDS (type);
1577   int count = 0;
1578
1579   for (; t; t = TREE_CHAIN (t))
1580     if (TREE_CODE (t) == FIELD_DECL)
1581       ++count;
1582
1583   return count;
1584 }
1585
1586 /* Concatenate two chains of nodes (chained through TREE_CHAIN)
1587    by modifying the last node in chain 1 to point to chain 2.
1588    This is the Lisp primitive `nconc'.  */
1589
1590 tree
1591 chainon (tree op1, tree op2)
1592 {
1593   tree t1;
1594
1595   if (!op1)
1596     return op2;
1597   if (!op2)
1598     return op1;
1599
1600   for (t1 = op1; TREE_CHAIN (t1); t1 = TREE_CHAIN (t1))
1601     continue;
1602   TREE_CHAIN (t1) = op2;
1603
1604 #ifdef ENABLE_TREE_CHECKING
1605   {
1606     tree t2;
1607     for (t2 = op2; t2; t2 = TREE_CHAIN (t2))
1608       gcc_assert (t2 != t1);
1609   }
1610 #endif
1611
1612   return op1;
1613 }
1614
1615 /* Return the last node in a chain of nodes (chained through TREE_CHAIN).  */
1616
1617 tree
1618 tree_last (tree chain)
1619 {
1620   tree next;
1621   if (chain)
1622     while ((next = TREE_CHAIN (chain)))
1623       chain = next;
1624   return chain;
1625 }
1626
1627 /* Reverse the order of elements in the chain T,
1628    and return the new head of the chain (old last element).  */
1629
1630 tree
1631 nreverse (tree t)
1632 {
1633   tree prev = 0, decl, next;
1634   for (decl = t; decl; decl = next)
1635     {
1636       next = TREE_CHAIN (decl);
1637       TREE_CHAIN (decl) = prev;
1638       prev = decl;
1639     }
1640   return prev;
1641 }
1642 \f
1643 /* Return a newly created TREE_LIST node whose
1644    purpose and value fields are PARM and VALUE.  */
1645
1646 tree
1647 build_tree_list_stat (tree parm, tree value MEM_STAT_DECL)
1648 {
1649   tree t = make_node_stat (TREE_LIST PASS_MEM_STAT);
1650   TREE_PURPOSE (t) = parm;
1651   TREE_VALUE (t) = value;
1652   return t;
1653 }
1654
1655 /* Return a newly created TREE_LIST node whose
1656    purpose and value fields are PURPOSE and VALUE
1657    and whose TREE_CHAIN is CHAIN.  */
1658
1659 tree
1660 tree_cons_stat (tree purpose, tree value, tree chain MEM_STAT_DECL)
1661 {
1662   tree node;
1663
1664   node = ggc_alloc_zone_pass_stat (sizeof (struct tree_list), &tree_zone);
1665
1666   memset (node, 0, sizeof (struct tree_common));
1667
1668 #ifdef GATHER_STATISTICS
1669   tree_node_counts[(int) x_kind]++;
1670   tree_node_sizes[(int) x_kind] += sizeof (struct tree_list);
1671 #endif
1672
1673   TREE_SET_CODE (node, TREE_LIST);
1674   TREE_CHAIN (node) = chain;
1675   TREE_PURPOSE (node) = purpose;
1676   TREE_VALUE (node) = value;
1677   return node;
1678 }
1679
1680 \f
1681 /* Return the size nominally occupied by an object of type TYPE
1682    when it resides in memory.  The value is measured in units of bytes,
1683    and its data type is that normally used for type sizes
1684    (which is the first type created by make_signed_type or
1685    make_unsigned_type).  */
1686
1687 tree
1688 size_in_bytes (tree type)
1689 {
1690   tree t;
1691
1692   if (type == error_mark_node)
1693     return integer_zero_node;
1694
1695   type = TYPE_MAIN_VARIANT (type);
1696   t = TYPE_SIZE_UNIT (type);
1697
1698   if (t == 0)
1699     {
1700       lang_hooks.types.incomplete_type_error (NULL_TREE, type);
1701       return size_zero_node;
1702     }
1703
1704   if (TREE_CODE (t) == INTEGER_CST)
1705     t = force_fit_type (t, 0, false, false);
1706
1707   return t;
1708 }
1709
1710 /* Return the size of TYPE (in bytes) as a wide integer
1711    or return -1 if the size can vary or is larger than an integer.  */
1712
1713 HOST_WIDE_INT
1714 int_size_in_bytes (tree type)
1715 {
1716   tree t;
1717
1718   if (type == error_mark_node)
1719     return 0;
1720
1721   type = TYPE_MAIN_VARIANT (type);
1722   t = TYPE_SIZE_UNIT (type);
1723   if (t == 0
1724       || TREE_CODE (t) != INTEGER_CST
1725       || TREE_OVERFLOW (t)
1726       || TREE_INT_CST_HIGH (t) != 0
1727       /* If the result would appear negative, it's too big to represent.  */
1728       || (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0)
1729     return -1;
1730
1731   return TREE_INT_CST_LOW (t);
1732 }
1733 \f
1734 /* Return the bit position of FIELD, in bits from the start of the record.
1735    This is a tree of type bitsizetype.  */
1736
1737 tree
1738 bit_position (tree field)
1739 {
1740   return bit_from_pos (DECL_FIELD_OFFSET (field),
1741                        DECL_FIELD_BIT_OFFSET (field));
1742 }
1743
1744 /* Likewise, but return as an integer.  It must be representable in
1745    that way (since it could be a signed value, we don't have the
1746    option of returning -1 like int_size_in_byte can.  */
1747
1748 HOST_WIDE_INT
1749 int_bit_position (tree field)
1750 {
1751   return tree_low_cst (bit_position (field), 0);
1752 }
1753 \f
1754 /* Return the byte position of FIELD, in bytes from the start of the record.
1755    This is a tree of type sizetype.  */
1756
1757 tree
1758 byte_position (tree field)
1759 {
1760   return byte_from_pos (DECL_FIELD_OFFSET (field),
1761                         DECL_FIELD_BIT_OFFSET (field));
1762 }
1763
1764 /* Likewise, but return as an integer.  It must be representable in
1765    that way (since it could be a signed value, we don't have the
1766    option of returning -1 like int_size_in_byte can.  */
1767
1768 HOST_WIDE_INT
1769 int_byte_position (tree field)
1770 {
1771   return tree_low_cst (byte_position (field), 0);
1772 }
1773 \f
1774 /* Return the strictest alignment, in bits, that T is known to have.  */
1775
1776 unsigned int
1777 expr_align (tree t)
1778 {
1779   unsigned int align0, align1;
1780
1781   switch (TREE_CODE (t))
1782     {
1783     case NOP_EXPR:  case CONVERT_EXPR:  case NON_LVALUE_EXPR:
1784       /* If we have conversions, we know that the alignment of the
1785          object must meet each of the alignments of the types.  */
1786       align0 = expr_align (TREE_OPERAND (t, 0));
1787       align1 = TYPE_ALIGN (TREE_TYPE (t));
1788       return MAX (align0, align1);
1789
1790     case SAVE_EXPR:         case COMPOUND_EXPR:       case MODIFY_EXPR:
1791     case INIT_EXPR:         case TARGET_EXPR:         case WITH_CLEANUP_EXPR:
1792     case CLEANUP_POINT_EXPR:
1793       /* These don't change the alignment of an object.  */
1794       return expr_align (TREE_OPERAND (t, 0));
1795
1796     case COND_EXPR:
1797       /* The best we can do is say that the alignment is the least aligned
1798          of the two arms.  */
1799       align0 = expr_align (TREE_OPERAND (t, 1));
1800       align1 = expr_align (TREE_OPERAND (t, 2));
1801       return MIN (align0, align1);
1802
1803     case LABEL_DECL:     case CONST_DECL:
1804     case VAR_DECL:       case PARM_DECL:   case RESULT_DECL:
1805       if (DECL_ALIGN (t) != 0)
1806         return DECL_ALIGN (t);
1807       break;
1808
1809     case FUNCTION_DECL:
1810       return FUNCTION_BOUNDARY;
1811
1812     default:
1813       break;
1814     }
1815
1816   /* Otherwise take the alignment from that of the type.  */
1817   return TYPE_ALIGN (TREE_TYPE (t));
1818 }
1819 \f
1820 /* Return, as a tree node, the number of elements for TYPE (which is an
1821    ARRAY_TYPE) minus one. This counts only elements of the top array.  */
1822
1823 tree
1824 array_type_nelts (tree type)
1825 {
1826   tree index_type, min, max;
1827
1828   /* If they did it with unspecified bounds, then we should have already
1829      given an error about it before we got here.  */
1830   if (! TYPE_DOMAIN (type))
1831     return error_mark_node;
1832
1833   index_type = TYPE_DOMAIN (type);
1834   min = TYPE_MIN_VALUE (index_type);
1835   max = TYPE_MAX_VALUE (index_type);
1836
1837   return (integer_zerop (min)
1838           ? max
1839           : fold_build2 (MINUS_EXPR, TREE_TYPE (max), max, min));
1840 }
1841 \f
1842 /* If arg is static -- a reference to an object in static storage -- then
1843    return the object.  This is not the same as the C meaning of `static'.
1844    If arg isn't static, return NULL.  */
1845
1846 tree
1847 staticp (tree arg)
1848 {
1849   switch (TREE_CODE (arg))
1850     {
1851     case FUNCTION_DECL:
1852       /* Nested functions are static, even though taking their address will
1853          involve a trampoline as we unnest the nested function and create
1854          the trampoline on the tree level.  */
1855       return arg;
1856
1857     case VAR_DECL:
1858       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1859               && ! DECL_THREAD_LOCAL_P (arg)
1860               && ! DECL_DLLIMPORT_P (arg)
1861               ? arg : NULL);
1862
1863     case CONST_DECL:
1864       return ((TREE_STATIC (arg) || DECL_EXTERNAL (arg))
1865               ? arg : NULL);
1866
1867     case CONSTRUCTOR:
1868       return TREE_STATIC (arg) ? arg : NULL;
1869
1870     case LABEL_DECL:
1871     case STRING_CST:
1872       return arg;
1873
1874     case COMPONENT_REF:
1875       /* If the thing being referenced is not a field, then it is
1876          something language specific.  */
1877       if (TREE_CODE (TREE_OPERAND (arg, 1)) != FIELD_DECL)
1878         return (*lang_hooks.staticp) (arg);
1879
1880       /* If we are referencing a bitfield, we can't evaluate an
1881          ADDR_EXPR at compile time and so it isn't a constant.  */
1882       if (DECL_BIT_FIELD (TREE_OPERAND (arg, 1)))
1883         return NULL;
1884
1885       return staticp (TREE_OPERAND (arg, 0));
1886
1887     case BIT_FIELD_REF:
1888       return NULL;
1889
1890     case MISALIGNED_INDIRECT_REF:
1891     case ALIGN_INDIRECT_REF:
1892     case INDIRECT_REF:
1893       return TREE_CONSTANT (TREE_OPERAND (arg, 0)) ? arg : NULL;
1894
1895     case ARRAY_REF:
1896     case ARRAY_RANGE_REF:
1897       if (TREE_CODE (TYPE_SIZE (TREE_TYPE (arg))) == INTEGER_CST
1898           && TREE_CODE (TREE_OPERAND (arg, 1)) == INTEGER_CST)
1899         return staticp (TREE_OPERAND (arg, 0));
1900       else
1901         return false;
1902
1903     default:
1904       if ((unsigned int) TREE_CODE (arg)
1905           >= (unsigned int) LAST_AND_UNUSED_TREE_CODE)
1906         return lang_hooks.staticp (arg);
1907       else
1908         return NULL;
1909     }
1910 }
1911 \f
1912 /* Wrap a SAVE_EXPR around EXPR, if appropriate.
1913    Do this to any expression which may be used in more than one place,
1914    but must be evaluated only once.
1915
1916    Normally, expand_expr would reevaluate the expression each time.
1917    Calling save_expr produces something that is evaluated and recorded
1918    the first time expand_expr is called on it.  Subsequent calls to
1919    expand_expr just reuse the recorded value.
1920
1921    The call to expand_expr that generates code that actually computes
1922    the value is the first call *at compile time*.  Subsequent calls
1923    *at compile time* generate code to use the saved value.
1924    This produces correct result provided that *at run time* control
1925    always flows through the insns made by the first expand_expr
1926    before reaching the other places where the save_expr was evaluated.
1927    You, the caller of save_expr, must make sure this is so.
1928
1929    Constants, and certain read-only nodes, are returned with no
1930    SAVE_EXPR because that is safe.  Expressions containing placeholders
1931    are not touched; see tree.def for an explanation of what these
1932    are used for.  */
1933
1934 tree
1935 save_expr (tree expr)
1936 {
1937   tree t = fold (expr);
1938   tree inner;
1939
1940   /* If the tree evaluates to a constant, then we don't want to hide that
1941      fact (i.e. this allows further folding, and direct checks for constants).
1942      However, a read-only object that has side effects cannot be bypassed.
1943      Since it is no problem to reevaluate literals, we just return the
1944      literal node.  */
1945   inner = skip_simple_arithmetic (t);
1946
1947   if (TREE_INVARIANT (inner)
1948       || (TREE_READONLY (inner) && ! TREE_SIDE_EFFECTS (inner))
1949       || TREE_CODE (inner) == SAVE_EXPR
1950       || TREE_CODE (inner) == ERROR_MARK)
1951     return t;
1952
1953   /* If INNER contains a PLACEHOLDER_EXPR, we must evaluate it each time, since
1954      it means that the size or offset of some field of an object depends on
1955      the value within another field.
1956
1957      Note that it must not be the case that T contains both a PLACEHOLDER_EXPR
1958      and some variable since it would then need to be both evaluated once and
1959      evaluated more than once.  Front-ends must assure this case cannot
1960      happen by surrounding any such subexpressions in their own SAVE_EXPR
1961      and forcing evaluation at the proper time.  */
1962   if (contains_placeholder_p (inner))
1963     return t;
1964
1965   t = build1 (SAVE_EXPR, TREE_TYPE (expr), t);
1966
1967   /* This expression might be placed ahead of a jump to ensure that the
1968      value was computed on both sides of the jump.  So make sure it isn't
1969      eliminated as dead.  */
1970   TREE_SIDE_EFFECTS (t) = 1;
1971   TREE_INVARIANT (t) = 1;
1972   return t;
1973 }
1974
1975 /* Look inside EXPR and into any simple arithmetic operations.  Return
1976    the innermost non-arithmetic node.  */
1977
1978 tree
1979 skip_simple_arithmetic (tree expr)
1980 {
1981   tree inner;
1982
1983   /* We don't care about whether this can be used as an lvalue in this
1984      context.  */
1985   while (TREE_CODE (expr) == NON_LVALUE_EXPR)
1986     expr = TREE_OPERAND (expr, 0);
1987
1988   /* If we have simple operations applied to a SAVE_EXPR or to a SAVE_EXPR and
1989      a constant, it will be more efficient to not make another SAVE_EXPR since
1990      it will allow better simplification and GCSE will be able to merge the
1991      computations if they actually occur.  */
1992   inner = expr;
1993   while (1)
1994     {
1995       if (UNARY_CLASS_P (inner))
1996         inner = TREE_OPERAND (inner, 0);
1997       else if (BINARY_CLASS_P (inner))
1998         {
1999           if (TREE_INVARIANT (TREE_OPERAND (inner, 1)))
2000             inner = TREE_OPERAND (inner, 0);
2001           else if (TREE_INVARIANT (TREE_OPERAND (inner, 0)))
2002             inner = TREE_OPERAND (inner, 1);
2003           else
2004             break;
2005         }
2006       else
2007         break;
2008     }
2009
2010   return inner;
2011 }
2012
2013 /* Return which tree structure is used by T.  */
2014
2015 enum tree_node_structure_enum
2016 tree_node_structure (tree t)
2017 {
2018   enum tree_code code = TREE_CODE (t);
2019
2020   switch (TREE_CODE_CLASS (code))
2021     {
2022     case tcc_declaration:
2023       {
2024         switch (code)
2025           {
2026           case FIELD_DECL:
2027             return TS_FIELD_DECL;
2028           case PARM_DECL:
2029             return TS_PARM_DECL;
2030           case VAR_DECL:
2031             return TS_VAR_DECL;
2032           case LABEL_DECL:
2033             return TS_LABEL_DECL;
2034           case RESULT_DECL:
2035             return TS_RESULT_DECL;
2036           case CONST_DECL:
2037             return TS_CONST_DECL;
2038           case TYPE_DECL:
2039             return TS_TYPE_DECL;
2040           case FUNCTION_DECL:
2041             return TS_FUNCTION_DECL;
2042           case TYPE_MEMORY_TAG:
2043           case NAME_MEMORY_TAG:
2044           case STRUCT_FIELD_TAG:
2045             return TS_MEMORY_TAG;
2046           default:
2047             return TS_DECL_NON_COMMON;
2048           }
2049       }
2050     case tcc_type:
2051       return TS_TYPE;
2052     case tcc_reference:
2053     case tcc_comparison:
2054     case tcc_unary:
2055     case tcc_binary:
2056     case tcc_expression:
2057     case tcc_statement:
2058       return TS_EXP;
2059     default:  /* tcc_constant and tcc_exceptional */
2060       break;
2061     }
2062   switch (code)
2063     {
2064       /* tcc_constant cases.  */
2065     case INTEGER_CST:           return TS_INT_CST;
2066     case REAL_CST:              return TS_REAL_CST;
2067     case COMPLEX_CST:           return TS_COMPLEX;
2068     case VECTOR_CST:            return TS_VECTOR;
2069     case STRING_CST:            return TS_STRING;
2070       /* tcc_exceptional cases.  */
2071     case ERROR_MARK:            return TS_COMMON;
2072     case IDENTIFIER_NODE:       return TS_IDENTIFIER;
2073     case TREE_LIST:             return TS_LIST;
2074     case TREE_VEC:              return TS_VEC;
2075     case PHI_NODE:              return TS_PHI_NODE;
2076     case SSA_NAME:              return TS_SSA_NAME;
2077     case PLACEHOLDER_EXPR:      return TS_COMMON;
2078     case STATEMENT_LIST:        return TS_STATEMENT_LIST;
2079     case BLOCK:                 return TS_BLOCK;
2080     case CONSTRUCTOR:           return TS_CONSTRUCTOR;
2081     case TREE_BINFO:            return TS_BINFO;
2082     case VALUE_HANDLE:          return TS_VALUE_HANDLE;
2083     case OMP_CLAUSE:            return TS_OMP_CLAUSE;
2084
2085     default:
2086       gcc_unreachable ();
2087     }
2088 }
2089 \f
2090 /* Return 1 if EXP contains a PLACEHOLDER_EXPR; i.e., if it represents a size
2091    or offset that depends on a field within a record.  */
2092
2093 bool
2094 contains_placeholder_p (tree exp)
2095 {
2096   enum tree_code code;
2097
2098   if (!exp)
2099     return 0;
2100
2101   code = TREE_CODE (exp);
2102   if (code == PLACEHOLDER_EXPR)
2103     return 1;
2104
2105   switch (TREE_CODE_CLASS (code))
2106     {
2107     case tcc_reference:
2108       /* Don't look at any PLACEHOLDER_EXPRs that might be in index or bit
2109          position computations since they will be converted into a
2110          WITH_RECORD_EXPR involving the reference, which will assume
2111          here will be valid.  */
2112       return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2113
2114     case tcc_exceptional:
2115       if (code == TREE_LIST)
2116         return (CONTAINS_PLACEHOLDER_P (TREE_VALUE (exp))
2117                 || CONTAINS_PLACEHOLDER_P (TREE_CHAIN (exp)));
2118       break;
2119
2120     case tcc_unary:
2121     case tcc_binary:
2122     case tcc_comparison:
2123     case tcc_expression:
2124       switch (code)
2125         {
2126         case COMPOUND_EXPR:
2127           /* Ignoring the first operand isn't quite right, but works best.  */
2128           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2129
2130         case COND_EXPR:
2131           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2132                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1))
2133                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 2)));
2134
2135         case CALL_EXPR:
2136           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1));
2137
2138         default:
2139           break;
2140         }
2141
2142       switch (TREE_CODE_LENGTH (code))
2143         {
2144         case 1:
2145           return CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0));
2146         case 2:
2147           return (CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 0))
2148                   || CONTAINS_PLACEHOLDER_P (TREE_OPERAND (exp, 1)));
2149         default:
2150           return 0;
2151         }
2152
2153     default:
2154       return 0;
2155     }
2156   return 0;
2157 }
2158
2159 /* Return true if any part of the computation of TYPE involves a
2160    PLACEHOLDER_EXPR.  This includes size, bounds, qualifiers
2161    (for QUAL_UNION_TYPE) and field positions.  */
2162
2163 static bool
2164 type_contains_placeholder_1 (tree type)
2165 {
2166   /* If the size contains a placeholder or the parent type (component type in
2167      the case of arrays) type involves a placeholder, this type does.  */
2168   if (CONTAINS_PLACEHOLDER_P (TYPE_SIZE (type))
2169       || CONTAINS_PLACEHOLDER_P (TYPE_SIZE_UNIT (type))
2170       || (TREE_TYPE (type) != 0
2171           && type_contains_placeholder_p (TREE_TYPE (type))))
2172     return true;
2173
2174   /* Now do type-specific checks.  Note that the last part of the check above
2175      greatly limits what we have to do below.  */
2176   switch (TREE_CODE (type))
2177     {
2178     case VOID_TYPE:
2179     case COMPLEX_TYPE:
2180     case ENUMERAL_TYPE:
2181     case BOOLEAN_TYPE:
2182     case CHAR_TYPE:
2183     case POINTER_TYPE:
2184     case OFFSET_TYPE:
2185     case REFERENCE_TYPE:
2186     case METHOD_TYPE:
2187     case FUNCTION_TYPE:
2188     case VECTOR_TYPE:
2189       return false;
2190
2191     case INTEGER_TYPE:
2192     case REAL_TYPE:
2193       /* Here we just check the bounds.  */
2194       return (CONTAINS_PLACEHOLDER_P (TYPE_MIN_VALUE (type))
2195               || CONTAINS_PLACEHOLDER_P (TYPE_MAX_VALUE (type)));
2196
2197     case ARRAY_TYPE:
2198       /* We're already checked the component type (TREE_TYPE), so just check
2199          the index type.  */
2200       return type_contains_placeholder_p (TYPE_DOMAIN (type));
2201
2202     case RECORD_TYPE:
2203     case UNION_TYPE:
2204     case QUAL_UNION_TYPE:
2205       {
2206         tree field;
2207
2208         for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
2209           if (TREE_CODE (field) == FIELD_DECL
2210               && (CONTAINS_PLACEHOLDER_P (DECL_FIELD_OFFSET (field))
2211                   || (TREE_CODE (type) == QUAL_UNION_TYPE
2212                       && CONTAINS_PLACEHOLDER_P (DECL_QUALIFIER (field)))
2213                   || type_contains_placeholder_p (TREE_TYPE (field))))
2214             return true;
2215
2216         return false;
2217       }
2218
2219     default:
2220       gcc_unreachable ();
2221     }
2222 }
2223
2224 bool
2225 type_contains_placeholder_p (tree type)
2226 {
2227   bool result;
2228
2229   /* If the contains_placeholder_bits field has been initialized,
2230      then we know the answer.  */
2231   if (TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) > 0)
2232     return TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) - 1;
2233
2234   /* Indicate that we've seen this type node, and the answer is false.
2235      This is what we want to return if we run into recursion via fields.  */
2236   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = 1;
2237
2238   /* Compute the real value.  */
2239   result = type_contains_placeholder_1 (type);
2240
2241   /* Store the real value.  */
2242   TYPE_CONTAINS_PLACEHOLDER_INTERNAL (type) = result + 1;
2243
2244   return result;
2245 }
2246 \f
2247 /* Given a tree EXP, a FIELD_DECL F, and a replacement value R,
2248    return a tree with all occurrences of references to F in a
2249    PLACEHOLDER_EXPR replaced by R.   Note that we assume here that EXP
2250    contains only arithmetic expressions or a CALL_EXPR with a
2251    PLACEHOLDER_EXPR occurring only in its arglist.  */
2252
2253 tree
2254 substitute_in_expr (tree exp, tree f, tree r)
2255 {
2256   enum tree_code code = TREE_CODE (exp);
2257   tree op0, op1, op2, op3;
2258   tree new;
2259   tree inner;
2260
2261   /* We handle TREE_LIST and COMPONENT_REF separately.  */
2262   if (code == TREE_LIST)
2263     {
2264       op0 = SUBSTITUTE_IN_EXPR (TREE_CHAIN (exp), f, r);
2265       op1 = SUBSTITUTE_IN_EXPR (TREE_VALUE (exp), f, r);
2266       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2267         return exp;
2268
2269       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2270     }
2271   else if (code == COMPONENT_REF)
2272    {
2273      /* If this expression is getting a value from a PLACEHOLDER_EXPR
2274         and it is the right field, replace it with R.  */
2275      for (inner = TREE_OPERAND (exp, 0);
2276           REFERENCE_CLASS_P (inner);
2277           inner = TREE_OPERAND (inner, 0))
2278        ;
2279      if (TREE_CODE (inner) == PLACEHOLDER_EXPR
2280          && TREE_OPERAND (exp, 1) == f)
2281        return r;
2282
2283      /* If this expression hasn't been completed let, leave it alone.  */
2284      if (TREE_CODE (inner) == PLACEHOLDER_EXPR && TREE_TYPE (inner) == 0)
2285        return exp;
2286
2287      op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2288      if (op0 == TREE_OPERAND (exp, 0))
2289        return exp;
2290
2291      new = fold_build3 (COMPONENT_REF, TREE_TYPE (exp),
2292                         op0, TREE_OPERAND (exp, 1), NULL_TREE);
2293    }
2294   else
2295     switch (TREE_CODE_CLASS (code))
2296       {
2297       case tcc_constant:
2298       case tcc_declaration:
2299         return exp;
2300
2301       case tcc_exceptional:
2302       case tcc_unary:
2303       case tcc_binary:
2304       case tcc_comparison:
2305       case tcc_expression:
2306       case tcc_reference:
2307         switch (TREE_CODE_LENGTH (code))
2308           {
2309           case 0:
2310             return exp;
2311
2312           case 1:
2313             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2314             if (op0 == TREE_OPERAND (exp, 0))
2315               return exp;
2316
2317             new = fold_build1 (code, TREE_TYPE (exp), op0);
2318             break;
2319
2320           case 2:
2321             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2322             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2323
2324             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2325               return exp;
2326
2327             new = fold_build2 (code, TREE_TYPE (exp), op0, op1);
2328             break;
2329
2330           case 3:
2331             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2332             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2333             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2334
2335             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2336                 && op2 == TREE_OPERAND (exp, 2))
2337               return exp;
2338
2339             new = fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2340             break;
2341
2342           case 4:
2343             op0 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 0), f, r);
2344             op1 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 1), f, r);
2345             op2 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 2), f, r);
2346             op3 = SUBSTITUTE_IN_EXPR (TREE_OPERAND (exp, 3), f, r);
2347
2348             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2349                 && op2 == TREE_OPERAND (exp, 2)
2350                 && op3 == TREE_OPERAND (exp, 3))
2351               return exp;
2352
2353             new = fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2354             break;
2355
2356           default:
2357             gcc_unreachable ();
2358           }
2359         break;
2360
2361       default:
2362         gcc_unreachable ();
2363       }
2364
2365   TREE_READONLY (new) = TREE_READONLY (exp);
2366   return new;
2367 }
2368
2369 /* Similar, but look for a PLACEHOLDER_EXPR in EXP and find a replacement
2370    for it within OBJ, a tree that is an object or a chain of references.  */
2371
2372 tree
2373 substitute_placeholder_in_expr (tree exp, tree obj)
2374 {
2375   enum tree_code code = TREE_CODE (exp);
2376   tree op0, op1, op2, op3;
2377
2378   /* If this is a PLACEHOLDER_EXPR, see if we find a corresponding type
2379      in the chain of OBJ.  */
2380   if (code == PLACEHOLDER_EXPR)
2381     {
2382       tree need_type = TYPE_MAIN_VARIANT (TREE_TYPE (exp));
2383       tree elt;
2384
2385       for (elt = obj; elt != 0;
2386            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2387                    || TREE_CODE (elt) == COND_EXPR)
2388                   ? TREE_OPERAND (elt, 1)
2389                   : (REFERENCE_CLASS_P (elt)
2390                      || UNARY_CLASS_P (elt)
2391                      || BINARY_CLASS_P (elt)
2392                      || EXPRESSION_CLASS_P (elt))
2393                   ? TREE_OPERAND (elt, 0) : 0))
2394         if (TYPE_MAIN_VARIANT (TREE_TYPE (elt)) == need_type)
2395           return elt;
2396
2397       for (elt = obj; elt != 0;
2398            elt = ((TREE_CODE (elt) == COMPOUND_EXPR
2399                    || TREE_CODE (elt) == COND_EXPR)
2400                   ? TREE_OPERAND (elt, 1)
2401                   : (REFERENCE_CLASS_P (elt)
2402                      || UNARY_CLASS_P (elt)
2403                      || BINARY_CLASS_P (elt)
2404                      || EXPRESSION_CLASS_P (elt))
2405                   ? TREE_OPERAND (elt, 0) : 0))
2406         if (POINTER_TYPE_P (TREE_TYPE (elt))
2407             && (TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (elt)))
2408                 == need_type))
2409           return fold_build1 (INDIRECT_REF, need_type, elt);
2410
2411       /* If we didn't find it, return the original PLACEHOLDER_EXPR.  If it
2412          survives until RTL generation, there will be an error.  */
2413       return exp;
2414     }
2415
2416   /* TREE_LIST is special because we need to look at TREE_VALUE
2417      and TREE_CHAIN, not TREE_OPERANDS.  */
2418   else if (code == TREE_LIST)
2419     {
2420       op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_CHAIN (exp), obj);
2421       op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_VALUE (exp), obj);
2422       if (op0 == TREE_CHAIN (exp) && op1 == TREE_VALUE (exp))
2423         return exp;
2424
2425       return tree_cons (TREE_PURPOSE (exp), op1, op0);
2426     }
2427   else
2428     switch (TREE_CODE_CLASS (code))
2429       {
2430       case tcc_constant:
2431       case tcc_declaration:
2432         return exp;
2433
2434       case tcc_exceptional:
2435       case tcc_unary:
2436       case tcc_binary:
2437       case tcc_comparison:
2438       case tcc_expression:
2439       case tcc_reference:
2440       case tcc_statement:
2441         switch (TREE_CODE_LENGTH (code))
2442           {
2443           case 0:
2444             return exp;
2445
2446           case 1:
2447             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2448             if (op0 == TREE_OPERAND (exp, 0))
2449               return exp;
2450             else
2451               return fold_build1 (code, TREE_TYPE (exp), op0);
2452
2453           case 2:
2454             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2455             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2456
2457             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1))
2458               return exp;
2459             else
2460               return fold_build2 (code, TREE_TYPE (exp), op0, op1);
2461
2462           case 3:
2463             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2464             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2465             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2466
2467             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2468                 && op2 == TREE_OPERAND (exp, 2))
2469               return exp;
2470             else
2471               return fold_build3 (code, TREE_TYPE (exp), op0, op1, op2);
2472
2473           case 4:
2474             op0 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 0), obj);
2475             op1 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 1), obj);
2476             op2 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 2), obj);
2477             op3 = SUBSTITUTE_PLACEHOLDER_IN_EXPR (TREE_OPERAND (exp, 3), obj);
2478
2479             if (op0 == TREE_OPERAND (exp, 0) && op1 == TREE_OPERAND (exp, 1)
2480                 && op2 == TREE_OPERAND (exp, 2)
2481                 && op3 == TREE_OPERAND (exp, 3))
2482               return exp;
2483             else
2484               return fold (build4 (code, TREE_TYPE (exp), op0, op1, op2, op3));
2485
2486           default:
2487             gcc_unreachable ();
2488           }
2489         break;
2490
2491       default:
2492         gcc_unreachable ();
2493       }
2494 }
2495 \f
2496 /* Stabilize a reference so that we can use it any number of times
2497    without causing its operands to be evaluated more than once.
2498    Returns the stabilized reference.  This works by means of save_expr,
2499    so see the caveats in the comments about save_expr.
2500
2501    Also allows conversion expressions whose operands are references.
2502    Any other kind of expression is returned unchanged.  */
2503
2504 tree
2505 stabilize_reference (tree ref)
2506 {
2507   tree result;
2508   enum tree_code code = TREE_CODE (ref);
2509
2510   switch (code)
2511     {
2512     case VAR_DECL:
2513     case PARM_DECL:
2514     case RESULT_DECL:
2515       /* No action is needed in this case.  */
2516       return ref;
2517
2518     case NOP_EXPR:
2519     case CONVERT_EXPR:
2520     case FLOAT_EXPR:
2521     case FIX_TRUNC_EXPR:
2522     case FIX_FLOOR_EXPR:
2523     case FIX_ROUND_EXPR:
2524     case FIX_CEIL_EXPR:
2525       result = build_nt (code, stabilize_reference (TREE_OPERAND (ref, 0)));
2526       break;
2527
2528     case INDIRECT_REF:
2529       result = build_nt (INDIRECT_REF,
2530                          stabilize_reference_1 (TREE_OPERAND (ref, 0)));
2531       break;
2532
2533     case COMPONENT_REF:
2534       result = build_nt (COMPONENT_REF,
2535                          stabilize_reference (TREE_OPERAND (ref, 0)),
2536                          TREE_OPERAND (ref, 1), NULL_TREE);
2537       break;
2538
2539     case BIT_FIELD_REF:
2540       result = build_nt (BIT_FIELD_REF,
2541                          stabilize_reference (TREE_OPERAND (ref, 0)),
2542                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2543                          stabilize_reference_1 (TREE_OPERAND (ref, 2)));
2544       break;
2545
2546     case ARRAY_REF:
2547       result = build_nt (ARRAY_REF,
2548                          stabilize_reference (TREE_OPERAND (ref, 0)),
2549                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2550                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2551       break;
2552
2553     case ARRAY_RANGE_REF:
2554       result = build_nt (ARRAY_RANGE_REF,
2555                          stabilize_reference (TREE_OPERAND (ref, 0)),
2556                          stabilize_reference_1 (TREE_OPERAND (ref, 1)),
2557                          TREE_OPERAND (ref, 2), TREE_OPERAND (ref, 3));
2558       break;
2559
2560     case COMPOUND_EXPR:
2561       /* We cannot wrap the first expression in a SAVE_EXPR, as then
2562          it wouldn't be ignored.  This matters when dealing with
2563          volatiles.  */
2564       return stabilize_reference_1 (ref);
2565
2566       /* If arg isn't a kind of lvalue we recognize, make no change.
2567          Caller should recognize the error for an invalid lvalue.  */
2568     default:
2569       return ref;
2570
2571     case ERROR_MARK:
2572       return error_mark_node;
2573     }
2574
2575   TREE_TYPE (result) = TREE_TYPE (ref);
2576   TREE_READONLY (result) = TREE_READONLY (ref);
2577   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (ref);
2578   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (ref);
2579
2580   return result;
2581 }
2582
2583 /* Subroutine of stabilize_reference; this is called for subtrees of
2584    references.  Any expression with side-effects must be put in a SAVE_EXPR
2585    to ensure that it is only evaluated once.
2586
2587    We don't put SAVE_EXPR nodes around everything, because assigning very
2588    simple expressions to temporaries causes us to miss good opportunities
2589    for optimizations.  Among other things, the opportunity to fold in the
2590    addition of a constant into an addressing mode often gets lost, e.g.
2591    "y[i+1] += x;".  In general, we take the approach that we should not make
2592    an assignment unless we are forced into it - i.e., that any non-side effect
2593    operator should be allowed, and that cse should take care of coalescing
2594    multiple utterances of the same expression should that prove fruitful.  */
2595
2596 tree
2597 stabilize_reference_1 (tree e)
2598 {
2599   tree result;
2600   enum tree_code code = TREE_CODE (e);
2601
2602   /* We cannot ignore const expressions because it might be a reference
2603      to a const array but whose index contains side-effects.  But we can
2604      ignore things that are actual constant or that already have been
2605      handled by this function.  */
2606
2607   if (TREE_INVARIANT (e))
2608     return e;
2609
2610   switch (TREE_CODE_CLASS (code))
2611     {
2612     case tcc_exceptional:
2613     case tcc_type:
2614     case tcc_declaration:
2615     case tcc_comparison:
2616     case tcc_statement:
2617     case tcc_expression:
2618     case tcc_reference:
2619       /* If the expression has side-effects, then encase it in a SAVE_EXPR
2620          so that it will only be evaluated once.  */
2621       /* The reference (r) and comparison (<) classes could be handled as
2622          below, but it is generally faster to only evaluate them once.  */
2623       if (TREE_SIDE_EFFECTS (e))
2624         return save_expr (e);
2625       return e;
2626
2627     case tcc_constant:
2628       /* Constants need no processing.  In fact, we should never reach
2629          here.  */
2630       return e;
2631
2632     case tcc_binary:
2633       /* Division is slow and tends to be compiled with jumps,
2634          especially the division by powers of 2 that is often
2635          found inside of an array reference.  So do it just once.  */
2636       if (code == TRUNC_DIV_EXPR || code == TRUNC_MOD_EXPR
2637           || code == FLOOR_DIV_EXPR || code == FLOOR_MOD_EXPR
2638           || code == CEIL_DIV_EXPR || code == CEIL_MOD_EXPR
2639           || code == ROUND_DIV_EXPR || code == ROUND_MOD_EXPR)
2640         return save_expr (e);
2641       /* Recursively stabilize each operand.  */
2642       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)),
2643                          stabilize_reference_1 (TREE_OPERAND (e, 1)));
2644       break;
2645
2646     case tcc_unary:
2647       /* Recursively stabilize each operand.  */
2648       result = build_nt (code, stabilize_reference_1 (TREE_OPERAND (e, 0)));
2649       break;
2650
2651     default:
2652       gcc_unreachable ();
2653     }
2654
2655   TREE_TYPE (result) = TREE_TYPE (e);
2656   TREE_READONLY (result) = TREE_READONLY (e);
2657   TREE_SIDE_EFFECTS (result) = TREE_SIDE_EFFECTS (e);
2658   TREE_THIS_VOLATILE (result) = TREE_THIS_VOLATILE (e);
2659   TREE_INVARIANT (result) = 1;
2660
2661   return result;
2662 }
2663 \f
2664 /* Low-level constructors for expressions.  */
2665
2666 /* A helper function for build1 and constant folders.  Set TREE_CONSTANT,
2667    TREE_INVARIANT, and TREE_SIDE_EFFECTS for an ADDR_EXPR.  */
2668
2669 void
2670 recompute_tree_invariant_for_addr_expr (tree t)
2671 {
2672   tree node;
2673   bool tc = true, ti = true, se = false;
2674
2675   /* We started out assuming this address is both invariant and constant, but
2676      does not have side effects.  Now go down any handled components and see if
2677      any of them involve offsets that are either non-constant or non-invariant.
2678      Also check for side-effects.
2679
2680      ??? Note that this code makes no attempt to deal with the case where
2681      taking the address of something causes a copy due to misalignment.  */
2682
2683 #define UPDATE_TITCSE(NODE)  \
2684 do { tree _node = (NODE); \
2685      if (_node && !TREE_INVARIANT (_node)) ti = false; \
2686      if (_node && !TREE_CONSTANT (_node)) tc = false; \
2687      if (_node && TREE_SIDE_EFFECTS (_node)) se = true; } while (0)
2688
2689   for (node = TREE_OPERAND (t, 0); handled_component_p (node);
2690        node = TREE_OPERAND (node, 0))
2691     {
2692       /* If the first operand doesn't have an ARRAY_TYPE, this is a bogus
2693          array reference (probably made temporarily by the G++ front end),
2694          so ignore all the operands.  */
2695       if ((TREE_CODE (node) == ARRAY_REF
2696            || TREE_CODE (node) == ARRAY_RANGE_REF)
2697           && TREE_CODE (TREE_TYPE (TREE_OPERAND (node, 0))) == ARRAY_TYPE)
2698         {
2699           UPDATE_TITCSE (TREE_OPERAND (node, 1));
2700           if (TREE_OPERAND (node, 2))
2701             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2702           if (TREE_OPERAND (node, 3))
2703             UPDATE_TITCSE (TREE_OPERAND (node, 3));
2704         }
2705       /* Likewise, just because this is a COMPONENT_REF doesn't mean we have a
2706          FIELD_DECL, apparently.  The G++ front end can put something else
2707          there, at least temporarily.  */
2708       else if (TREE_CODE (node) == COMPONENT_REF
2709                && TREE_CODE (TREE_OPERAND (node, 1)) == FIELD_DECL)
2710         {
2711           if (TREE_OPERAND (node, 2))
2712             UPDATE_TITCSE (TREE_OPERAND (node, 2));
2713         }
2714       else if (TREE_CODE (node) == BIT_FIELD_REF)
2715         UPDATE_TITCSE (TREE_OPERAND (node, 2));
2716     }
2717
2718   node = lang_hooks.expr_to_decl (node, &tc, &ti, &se);
2719
2720   /* Now see what's inside.  If it's an INDIRECT_REF, copy our properties from
2721      the address, since &(*a)->b is a form of addition.  If it's a decl, it's
2722      invariant and constant if the decl is static.  It's also invariant if it's
2723      a decl in the current function.  Taking the address of a volatile variable
2724      is not volatile.  If it's a constant, the address is both invariant and
2725      constant.  Otherwise it's neither.  */
2726   if (TREE_CODE (node) == INDIRECT_REF)
2727     UPDATE_TITCSE (TREE_OPERAND (node, 0));
2728   else if (DECL_P (node))
2729     {
2730       if (staticp (node))
2731         ;
2732       else if (decl_function_context (node) == current_function_decl
2733                /* Addresses of thread-local variables are invariant.  */
2734                || (TREE_CODE (node) == VAR_DECL
2735                    && DECL_THREAD_LOCAL_P (node)))
2736         tc = false;
2737       else
2738         ti = tc = false;
2739     }
2740   else if (CONSTANT_CLASS_P (node))
2741     ;
2742   else
2743     {
2744       ti = tc = false;
2745       se |= TREE_SIDE_EFFECTS (node);
2746     }
2747
2748   TREE_CONSTANT (t) = tc;
2749   TREE_INVARIANT (t) = ti;
2750   TREE_SIDE_EFFECTS (t) = se;
2751 #undef UPDATE_TITCSE
2752 }
2753
2754 /* Build an expression of code CODE, data type TYPE, and operands as
2755    specified.  Expressions and reference nodes can be created this way.
2756    Constants, decls, types and misc nodes cannot be.
2757
2758    We define 5 non-variadic functions, from 0 to 4 arguments.  This is
2759    enough for all extant tree codes.  */
2760
2761 tree
2762 build0_stat (enum tree_code code, tree tt MEM_STAT_DECL)
2763 {
2764   tree t;
2765
2766   gcc_assert (TREE_CODE_LENGTH (code) == 0);
2767
2768   t = make_node_stat (code PASS_MEM_STAT);
2769   TREE_TYPE (t) = tt;
2770
2771   return t;
2772 }
2773
2774 tree
2775 build1_stat (enum tree_code code, tree type, tree node MEM_STAT_DECL)
2776 {
2777   int length = sizeof (struct tree_exp);
2778 #ifdef GATHER_STATISTICS
2779   tree_node_kind kind;
2780 #endif
2781   tree t;
2782
2783 #ifdef GATHER_STATISTICS
2784   switch (TREE_CODE_CLASS (code))
2785     {
2786     case tcc_statement:  /* an expression with side effects */
2787       kind = s_kind;
2788       break;
2789     case tcc_reference:  /* a reference */
2790       kind = r_kind;
2791       break;
2792     default:
2793       kind = e_kind;
2794       break;
2795     }
2796
2797   tree_node_counts[(int) kind]++;
2798   tree_node_sizes[(int) kind] += length;
2799 #endif
2800
2801   gcc_assert (TREE_CODE_LENGTH (code) == 1);
2802
2803   t = ggc_alloc_zone_pass_stat (length, &tree_zone);
2804
2805   memset (t, 0, sizeof (struct tree_common));
2806
2807   TREE_SET_CODE (t, code);
2808
2809   TREE_TYPE (t) = type;
2810 #ifdef USE_MAPPED_LOCATION
2811   SET_EXPR_LOCATION (t, UNKNOWN_LOCATION);
2812 #else
2813   SET_EXPR_LOCUS (t, NULL);
2814 #endif
2815   TREE_COMPLEXITY (t) = 0;
2816   TREE_OPERAND (t, 0) = node;
2817   TREE_BLOCK (t) = NULL_TREE;
2818   if (node && !TYPE_P (node))
2819     {
2820       TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (node);
2821       TREE_READONLY (t) = TREE_READONLY (node);
2822     }
2823
2824   if (TREE_CODE_CLASS (code) == tcc_statement)
2825     TREE_SIDE_EFFECTS (t) = 1;
2826   else switch (code)
2827     {
2828     case VA_ARG_EXPR:
2829       /* All of these have side-effects, no matter what their
2830          operands are.  */
2831       TREE_SIDE_EFFECTS (t) = 1;
2832       TREE_READONLY (t) = 0;
2833       break;
2834
2835     case MISALIGNED_INDIRECT_REF:
2836     case ALIGN_INDIRECT_REF:
2837     case INDIRECT_REF:
2838       /* Whether a dereference is readonly has nothing to do with whether
2839          its operand is readonly.  */
2840       TREE_READONLY (t) = 0;
2841       break;
2842
2843     case ADDR_EXPR:
2844       if (node)
2845         recompute_tree_invariant_for_addr_expr (t);
2846       break;
2847
2848     default:
2849       if (TREE_CODE_CLASS (code) == tcc_unary
2850           && node && !TYPE_P (node)
2851           && TREE_CONSTANT (node))
2852         TREE_CONSTANT (t) = 1;
2853       if (TREE_CODE_CLASS (code) == tcc_unary
2854           && node && TREE_INVARIANT (node))
2855         TREE_INVARIANT (t) = 1;
2856       if (TREE_CODE_CLASS (code) == tcc_reference
2857           && node && TREE_THIS_VOLATILE (node))
2858         TREE_THIS_VOLATILE (t) = 1;
2859       break;
2860     }
2861
2862   return t;
2863 }
2864
2865 #define PROCESS_ARG(N)                  \
2866   do {                                  \
2867     TREE_OPERAND (t, N) = arg##N;       \
2868     if (arg##N &&!TYPE_P (arg##N))      \
2869       {                                 \
2870         if (TREE_SIDE_EFFECTS (arg##N)) \
2871           side_effects = 1;             \
2872         if (!TREE_READONLY (arg##N))    \
2873           read_only = 0;                \
2874         if (!TREE_CONSTANT (arg##N))    \
2875           constant = 0;                 \
2876         if (!TREE_INVARIANT (arg##N))   \
2877           invariant = 0;                \
2878       }                                 \
2879   } while (0)
2880
2881 tree
2882 build2_stat (enum tree_code code, tree tt, tree arg0, tree arg1 MEM_STAT_DECL)
2883 {
2884   bool constant, read_only, side_effects, invariant;
2885   tree t;
2886
2887   gcc_assert (TREE_CODE_LENGTH (code) == 2);
2888
2889   t = make_node_stat (code PASS_MEM_STAT);
2890   TREE_TYPE (t) = tt;
2891
2892   /* Below, we automatically set TREE_SIDE_EFFECTS and TREE_READONLY for the
2893      result based on those same flags for the arguments.  But if the
2894      arguments aren't really even `tree' expressions, we shouldn't be trying
2895      to do this.  */
2896
2897   /* Expressions without side effects may be constant if their
2898      arguments are as well.  */
2899   constant = (TREE_CODE_CLASS (code) == tcc_comparison
2900               || TREE_CODE_CLASS (code) == tcc_binary);
2901   read_only = 1;
2902   side_effects = TREE_SIDE_EFFECTS (t);
2903   invariant = constant;
2904
2905   PROCESS_ARG(0);
2906   PROCESS_ARG(1);
2907
2908   TREE_READONLY (t) = read_only;
2909   TREE_CONSTANT (t) = constant;
2910   TREE_INVARIANT (t) = invariant;
2911   TREE_SIDE_EFFECTS (t) = side_effects;
2912   TREE_THIS_VOLATILE (t)
2913     = (TREE_CODE_CLASS (code) == tcc_reference
2914        && arg0 && TREE_THIS_VOLATILE (arg0));
2915
2916   return t;
2917 }
2918
2919 tree
2920 build3_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2921              tree arg2 MEM_STAT_DECL)
2922 {
2923   bool constant, read_only, side_effects, invariant;
2924   tree t;
2925
2926   gcc_assert (TREE_CODE_LENGTH (code) == 3);
2927
2928   t = make_node_stat (code PASS_MEM_STAT);
2929   TREE_TYPE (t) = tt;
2930
2931   side_effects = TREE_SIDE_EFFECTS (t);
2932
2933   PROCESS_ARG(0);
2934   PROCESS_ARG(1);
2935   PROCESS_ARG(2);
2936
2937   if (code == CALL_EXPR && !side_effects)
2938     {
2939       tree node;
2940       int i;
2941
2942       /* Calls have side-effects, except those to const or
2943          pure functions.  */
2944       i = call_expr_flags (t);
2945       if (!(i & (ECF_CONST | ECF_PURE)))
2946         side_effects = 1;
2947
2948       /* And even those have side-effects if their arguments do.  */
2949       else for (node = arg1; node; node = TREE_CHAIN (node))
2950         if (TREE_SIDE_EFFECTS (TREE_VALUE (node)))
2951           {
2952             side_effects = 1;
2953             break;
2954           }
2955     }
2956
2957   TREE_SIDE_EFFECTS (t) = side_effects;
2958   TREE_THIS_VOLATILE (t)
2959     = (TREE_CODE_CLASS (code) == tcc_reference
2960        && arg0 && TREE_THIS_VOLATILE (arg0));
2961
2962   return t;
2963 }
2964
2965 tree
2966 build4_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2967              tree arg2, tree arg3 MEM_STAT_DECL)
2968 {
2969   bool constant, read_only, side_effects, invariant;
2970   tree t;
2971
2972   gcc_assert (TREE_CODE_LENGTH (code) == 4);
2973
2974   t = make_node_stat (code PASS_MEM_STAT);
2975   TREE_TYPE (t) = tt;
2976
2977   side_effects = TREE_SIDE_EFFECTS (t);
2978
2979   PROCESS_ARG(0);
2980   PROCESS_ARG(1);
2981   PROCESS_ARG(2);
2982   PROCESS_ARG(3);
2983
2984   TREE_SIDE_EFFECTS (t) = side_effects;
2985   TREE_THIS_VOLATILE (t)
2986     = (TREE_CODE_CLASS (code) == tcc_reference
2987        && arg0 && TREE_THIS_VOLATILE (arg0));
2988
2989   return t;
2990 }
2991
2992 tree
2993 build5_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
2994              tree arg2, tree arg3, tree arg4 MEM_STAT_DECL)
2995 {
2996   bool constant, read_only, side_effects, invariant;
2997   tree t;
2998
2999   gcc_assert (TREE_CODE_LENGTH (code) == 5);
3000
3001   t = make_node_stat (code PASS_MEM_STAT);
3002   TREE_TYPE (t) = tt;
3003
3004   side_effects = TREE_SIDE_EFFECTS (t);
3005
3006   PROCESS_ARG(0);
3007   PROCESS_ARG(1);
3008   PROCESS_ARG(2);
3009   PROCESS_ARG(3);
3010   PROCESS_ARG(4);
3011
3012   TREE_SIDE_EFFECTS (t) = side_effects;
3013   TREE_THIS_VOLATILE (t)
3014     = (TREE_CODE_CLASS (code) == tcc_reference
3015        && arg0 && TREE_THIS_VOLATILE (arg0));
3016
3017   return t;
3018 }
3019
3020 tree
3021 build7_stat (enum tree_code code, tree tt, tree arg0, tree arg1,
3022              tree arg2, tree arg3, tree arg4, tree arg5,
3023              tree arg6 MEM_STAT_DECL)
3024 {
3025   bool constant, read_only, side_effects, invariant;
3026   tree t;
3027
3028   gcc_assert (code == TARGET_MEM_REF);
3029
3030   t = make_node_stat (code PASS_MEM_STAT);
3031   TREE_TYPE (t) = tt;
3032
3033   side_effects = TREE_SIDE_EFFECTS (t);
3034
3035   PROCESS_ARG(0);
3036   PROCESS_ARG(1);
3037   PROCESS_ARG(2);
3038   PROCESS_ARG(3);
3039   PROCESS_ARG(4);
3040   PROCESS_ARG(5);
3041   PROCESS_ARG(6);
3042
3043   TREE_SIDE_EFFECTS (t) = side_effects;
3044   TREE_THIS_VOLATILE (t) = 0;
3045
3046   return t;
3047 }
3048
3049 /* Similar except don't specify the TREE_TYPE
3050    and leave the TREE_SIDE_EFFECTS as 0.
3051    It is permissible for arguments to be null,
3052    or even garbage if their values do not matter.  */
3053
3054 tree
3055 build_nt (enum tree_code code, ...)
3056 {
3057   tree t;
3058   int length;
3059   int i;
3060   va_list p;
3061
3062   va_start (p, code);
3063
3064   t = make_node (code);
3065   length = TREE_CODE_LENGTH (code);
3066
3067   for (i = 0; i < length; i++)
3068     TREE_OPERAND (t, i) = va_arg (p, tree);
3069
3070   va_end (p);
3071   return t;
3072 }
3073 \f
3074 /* Create a DECL_... node of code CODE, name NAME and data type TYPE.
3075    We do NOT enter this node in any sort of symbol table.
3076
3077    layout_decl is used to set up the decl's storage layout.
3078    Other slots are initialized to 0 or null pointers.  */
3079
3080 tree
3081 build_decl_stat (enum tree_code code, tree name, tree type MEM_STAT_DECL)
3082 {
3083   tree t;
3084
3085   t = make_node_stat (code PASS_MEM_STAT);
3086
3087 /*  if (type == error_mark_node)
3088     type = integer_type_node; */
3089 /* That is not done, deliberately, so that having error_mark_node
3090    as the type can suppress useless errors in the use of this variable.  */
3091
3092   DECL_NAME (t) = name;
3093   TREE_TYPE (t) = type;
3094
3095   if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL)
3096     layout_decl (t, 0);
3097   else if (code == FUNCTION_DECL)
3098     DECL_MODE (t) = FUNCTION_MODE;
3099
3100   if (CODE_CONTAINS_STRUCT (code, TS_DECL_WITH_VIS))
3101     {
3102       /* Set default visibility to whatever the user supplied with
3103          visibility_specified depending on #pragma GCC visibility.  */
3104       DECL_VISIBILITY (t) = default_visibility;
3105       DECL_VISIBILITY_SPECIFIED (t) = visibility_options.inpragma;
3106     }
3107
3108   return t;
3109 }
3110
3111 /* Builds and returns function declaration with NAME and TYPE.  */
3112
3113 tree
3114 build_fn_decl (const char *name, tree type)
3115 {
3116   tree id = get_identifier (name);
3117   tree decl = build_decl (FUNCTION_DECL, id, type);
3118
3119   DECL_EXTERNAL (decl) = 1;
3120   TREE_PUBLIC (decl) = 1;
3121   DECL_ARTIFICIAL (decl) = 1;
3122   TREE_NOTHROW (decl) = 1;
3123
3124   return decl;
3125 }
3126
3127 \f
3128 /* BLOCK nodes are used to represent the structure of binding contours
3129    and declarations, once those contours have been exited and their contents
3130    compiled.  This information is used for outputting debugging info.  */
3131
3132 tree
3133 build_block (tree vars, tree subblocks, tree supercontext, tree chain)
3134 {
3135   tree block = make_node (BLOCK);
3136
3137   BLOCK_VARS (block) = vars;
3138   BLOCK_SUBBLOCKS (block) = subblocks;
3139   BLOCK_SUPERCONTEXT (block) = supercontext;
3140   BLOCK_CHAIN (block) = chain;
3141   return block;
3142 }
3143
3144 #if 1 /* ! defined(USE_MAPPED_LOCATION) */
3145 /* ??? gengtype doesn't handle conditionals */
3146 static GTY(()) location_t *last_annotated_node;
3147 #endif
3148
3149 #ifdef USE_MAPPED_LOCATION
3150
3151 expanded_location
3152 expand_location (source_location loc)
3153 {
3154   expanded_location xloc;
3155   if (loc == 0) { xloc.file = NULL; xloc.line = 0;  xloc.column = 0; }
3156   else
3157     {
3158       const struct line_map *map = linemap_lookup (&line_table, loc);
3159       xloc.file = map->to_file;
3160       xloc.line = SOURCE_LINE (map, loc);
3161       xloc.column = SOURCE_COLUMN (map, loc);
3162     };
3163   return xloc;
3164 }
3165
3166 #else
3167
3168 /* Record the exact location where an expression or an identifier were
3169    encountered.  */
3170
3171 void
3172 annotate_with_file_line (tree node, const char *file, int line)
3173 {
3174   /* Roughly one percent of the calls to this function are to annotate
3175      a node with the same information already attached to that node!
3176      Just return instead of wasting memory.  */
3177   if (EXPR_LOCUS (node)
3178       && EXPR_LINENO (node) == line
3179       && (EXPR_FILENAME (node) == file
3180           || !strcmp (EXPR_FILENAME (node), file)))
3181     {
3182       last_annotated_node = EXPR_LOCUS (node);
3183       return;
3184     }
3185
3186   /* In heavily macroized code (such as GCC itself) this single
3187      entry cache can reduce the number of allocations by more
3188      than half.  */
3189   if (last_annotated_node
3190       && last_annotated_node->line == line
3191       && (last_annotated_node->file == file
3192           || !strcmp (last_annotated_node->file, file)))
3193     {
3194       SET_EXPR_LOCUS (node, last_annotated_node);
3195       return;
3196     }
3197
3198   SET_EXPR_LOCUS (node, ggc_alloc (sizeof (location_t)));
3199   EXPR_LINENO (node) = line;
3200   EXPR_FILENAME (node) = file;
3201   last_annotated_node = EXPR_LOCUS (node);
3202 }
3203
3204 void
3205 annotate_with_locus (tree node, location_t locus)
3206 {
3207   annotate_with_file_line (node, locus.file, locus.line);
3208 }
3209 #endif
3210 \f
3211 /* Return a declaration like DDECL except that its DECL_ATTRIBUTES
3212    is ATTRIBUTE.  */
3213
3214 tree
3215 build_decl_attribute_variant (tree ddecl, tree attribute)
3216 {
3217   DECL_ATTRIBUTES (ddecl) = attribute;
3218   return ddecl;
3219 }
3220
3221 /* Borrowed from hashtab.c iterative_hash implementation.  */
3222 #define mix(a,b,c) \
3223 { \
3224   a -= b; a -= c; a ^= (c>>13); \
3225   b -= c; b -= a; b ^= (a<< 8); \
3226   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
3227   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
3228   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
3229   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
3230   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
3231   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
3232   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
3233 }
3234
3235
3236 /* Produce good hash value combining VAL and VAL2.  */
3237 static inline hashval_t
3238 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
3239 {
3240   /* the golden ratio; an arbitrary value.  */
3241   hashval_t a = 0x9e3779b9;
3242
3243   mix (a, val, val2);
3244   return val2;
3245 }
3246
3247 /* Produce good hash value combining PTR and VAL2.  */
3248 static inline hashval_t
3249 iterative_hash_pointer (void *ptr, hashval_t val2)
3250 {
3251   if (sizeof (ptr) == sizeof (hashval_t))
3252     return iterative_hash_hashval_t ((size_t) ptr, val2);
3253   else
3254     {
3255       hashval_t a = (hashval_t) (size_t) ptr;
3256       /* Avoid warnings about shifting of more than the width of the type on
3257          hosts that won't execute this path.  */
3258       int zero = 0;
3259       hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero));
3260       mix (a, b, val2);
3261       return val2;
3262     }
3263 }
3264
3265 /* Produce good hash value combining VAL and VAL2.  */
3266 static inline hashval_t
3267 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
3268 {
3269   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
3270     return iterative_hash_hashval_t (val, val2);
3271   else
3272     {
3273       hashval_t a = (hashval_t) val;
3274       /* Avoid warnings about shifting of more than the width of the type on
3275          hosts that won't execute this path.  */
3276       int zero = 0;
3277       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
3278       mix (a, b, val2);
3279       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
3280         {
3281           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
3282           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
3283           mix (a, b, val2);
3284         }
3285       return val2;
3286     }
3287 }
3288
3289 /* Return a type like TTYPE except that its TYPE_ATTRIBUTE
3290    is ATTRIBUTE.
3291
3292    Record such modified types already made so we don't make duplicates.  */
3293
3294 tree
3295 build_type_attribute_variant (tree ttype, tree attribute)
3296 {
3297   if (! attribute_list_equal (TYPE_ATTRIBUTES (ttype), attribute))
3298     {
3299       hashval_t hashcode = 0;
3300       tree ntype;
3301       enum tree_code code = TREE_CODE (ttype);
3302
3303       ntype = copy_node (ttype);
3304
3305       TYPE_POINTER_TO (ntype) = 0;
3306       TYPE_REFERENCE_TO (ntype) = 0;
3307       TYPE_ATTRIBUTES (ntype) = attribute;
3308
3309       /* Create a new main variant of TYPE.  */
3310       TYPE_MAIN_VARIANT (ntype) = ntype;
3311       TYPE_NEXT_VARIANT (ntype) = 0;
3312       set_type_quals (ntype, TYPE_UNQUALIFIED);
3313
3314       hashcode = iterative_hash_object (code, hashcode);
3315       if (TREE_TYPE (ntype))
3316         hashcode = iterative_hash_object (TYPE_HASH (TREE_TYPE (ntype)),
3317                                           hashcode);
3318       hashcode = attribute_hash_list (attribute, hashcode);
3319
3320       switch (TREE_CODE (ntype))
3321         {
3322         case FUNCTION_TYPE:
3323           hashcode = type_hash_list (TYPE_ARG_TYPES (ntype), hashcode);
3324           break;
3325         case ARRAY_TYPE:
3326           hashcode = iterative_hash_object (TYPE_HASH (TYPE_DOMAIN (ntype)),
3327                                             hashcode);
3328           break;
3329         case INTEGER_TYPE:
3330           hashcode = iterative_hash_object
3331             (TREE_INT_CST_LOW (TYPE_MAX_VALUE (ntype)), hashcode);
3332           hashcode = iterative_hash_object
3333             (TREE_INT_CST_HIGH (TYPE_MAX_VALUE (ntype)), hashcode);
3334           break;
3335         case REAL_TYPE:
3336           {
3337             unsigned int precision = TYPE_PRECISION (ntype);
3338             hashcode = iterative_hash_object (precision, hashcode);
3339           }
3340           break;
3341         default:
3342           break;
3343         }
3344
3345       ntype = type_hash_canon (hashcode, ntype);
3346       ttype = build_qualified_type (ntype, TYPE_QUALS (ttype));
3347     }
3348
3349   return ttype;
3350 }
3351
3352
3353 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3354    or zero if not.
3355
3356    We try both `text' and `__text__', ATTR may be either one.  */
3357 /* ??? It might be a reasonable simplification to require ATTR to be only
3358    `text'.  One might then also require attribute lists to be stored in
3359    their canonicalized form.  */
3360
3361 static int
3362 is_attribute_with_length_p (const char *attr, int attr_len, tree ident)
3363 {
3364   int ident_len;
3365   const char *p;
3366
3367   if (TREE_CODE (ident) != IDENTIFIER_NODE)
3368     return 0;
3369
3370   p = IDENTIFIER_POINTER (ident);
3371   ident_len = IDENTIFIER_LENGTH (ident);
3372
3373   if (ident_len == attr_len
3374       && strcmp (attr, p) == 0)
3375     return 1;
3376
3377   /* If ATTR is `__text__', IDENT must be `text'; and vice versa.  */
3378   if (attr[0] == '_')
3379     {
3380       gcc_assert (attr[1] == '_');
3381       gcc_assert (attr[attr_len - 2] == '_');
3382       gcc_assert (attr[attr_len - 1] == '_');
3383       gcc_assert (attr[1] == '_');
3384       if (ident_len == attr_len - 4
3385           && strncmp (attr + 2, p, attr_len - 4) == 0)
3386         return 1;
3387     }
3388   else
3389     {
3390       if (ident_len == attr_len + 4
3391           && p[0] == '_' && p[1] == '_'
3392           && p[ident_len - 2] == '_' && p[ident_len - 1] == '_'
3393           && strncmp (attr, p + 2, attr_len) == 0)
3394         return 1;
3395     }
3396
3397   return 0;
3398 }
3399
3400 /* Return nonzero if IDENT is a valid name for attribute ATTR,
3401    or zero if not.
3402
3403    We try both `text' and `__text__', ATTR may be either one.  */
3404
3405 int
3406 is_attribute_p (const char *attr, tree ident)
3407 {
3408   return is_attribute_with_length_p (attr, strlen (attr), ident);
3409 }
3410
3411 /* Given an attribute name and a list of attributes, return a pointer to the
3412    attribute's list element if the attribute is part of the list, or NULL_TREE
3413    if not found.  If the attribute appears more than once, this only
3414    returns the first occurrence; the TREE_CHAIN of the return value should
3415    be passed back in if further occurrences are wanted.  */
3416
3417 tree
3418 lookup_attribute (const char *attr_name, tree list)
3419 {
3420   tree l;
3421   size_t attr_len = strlen (attr_name);
3422
3423   for (l = list; l; l = TREE_CHAIN (l))
3424     {
3425       gcc_assert (TREE_CODE (TREE_PURPOSE (l)) == IDENTIFIER_NODE);
3426       if (is_attribute_with_length_p (attr_name, attr_len, TREE_PURPOSE (l)))
3427         return l;
3428     }
3429
3430   return NULL_TREE;
3431 }
3432
3433 /* Return an attribute list that is the union of a1 and a2.  */
3434
3435 tree
3436 merge_attributes (tree a1, tree a2)
3437 {
3438   tree attributes;
3439
3440   /* Either one unset?  Take the set one.  */
3441
3442   if ((attributes = a1) == 0)
3443     attributes = a2;
3444
3445   /* One that completely contains the other?  Take it.  */
3446
3447   else if (a2 != 0 && ! attribute_list_contained (a1, a2))
3448     {
3449       if (attribute_list_contained (a2, a1))
3450         attributes = a2;
3451       else
3452         {
3453           /* Pick the longest list, and hang on the other list.  */
3454
3455           if (list_length (a1) < list_length (a2))
3456             attributes = a2, a2 = a1;
3457
3458           for (; a2 != 0; a2 = TREE_CHAIN (a2))
3459             {
3460               tree a;
3461               for (a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3462                                          attributes);
3463                    a != NULL_TREE;
3464                    a = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (a2)),
3465                                          TREE_CHAIN (a)))
3466                 {
3467                   if (simple_cst_equal (TREE_VALUE (a), TREE_VALUE (a2)) == 1)
3468                     break;
3469                 }
3470               if (a == NULL_TREE)
3471                 {
3472                   a1 = copy_node (a2);
3473                   TREE_CHAIN (a1) = attributes;
3474                   attributes = a1;
3475                 }
3476             }
3477         }
3478     }
3479   return attributes;
3480 }
3481
3482 /* Given types T1 and T2, merge their attributes and return
3483   the result.  */
3484
3485 tree
3486 merge_type_attributes (tree t1, tree t2)
3487 {
3488   return merge_attributes (TYPE_ATTRIBUTES (t1),
3489                            TYPE_ATTRIBUTES (t2));
3490 }
3491
3492 /* Given decls OLDDECL and NEWDECL, merge their attributes and return
3493    the result.  */
3494
3495 tree
3496 merge_decl_attributes (tree olddecl, tree newdecl)
3497 {
3498   return merge_attributes (DECL_ATTRIBUTES (olddecl),
3499                            DECL_ATTRIBUTES (newdecl));
3500 }
3501
3502 #if TARGET_DLLIMPORT_DECL_ATTRIBUTES
3503
3504 /* Specialization of merge_decl_attributes for various Windows targets.
3505
3506    This handles the following situation:
3507
3508      __declspec (dllimport) int foo;
3509      int foo;
3510
3511    The second instance of `foo' nullifies the dllimport.  */
3512
3513 tree
3514 merge_dllimport_decl_attributes (tree old, tree new)
3515 {
3516   tree a;
3517   int delete_dllimport_p = 1;
3518
3519   /* What we need to do here is remove from `old' dllimport if it doesn't
3520      appear in `new'.  dllimport behaves like extern: if a declaration is
3521      marked dllimport and a definition appears later, then the object
3522      is not dllimport'd.  We also remove a `new' dllimport if the old list
3523      contains dllexport:  dllexport always overrides dllimport, regardless
3524      of the order of declaration.  */
3525   if (!VAR_OR_FUNCTION_DECL_P (new))
3526     delete_dllimport_p = 0;
3527   else if (DECL_DLLIMPORT_P (new)
3528            && lookup_attribute ("dllexport", DECL_ATTRIBUTES (old)))
3529     {
3530       DECL_DLLIMPORT_P (new) = 0;
3531       warning (OPT_Wattributes, "%q+D already declared with dllexport attribute: "
3532               "dllimport ignored", new);
3533     }
3534   else if (DECL_DLLIMPORT_P (old) && !DECL_DLLIMPORT_P (new))
3535     {
3536       /* Warn about overriding a symbol that has already been used. eg:
3537            extern int __attribute__ ((dllimport)) foo;
3538            int* bar () {return &foo;}
3539            int foo;
3540       */
3541       if (TREE_USED (old))
3542         {
3543           warning (0, "%q+D redeclared without dllimport attribute "
3544                    "after being referenced with dll linkage", new);
3545           /* If we have used a variable's address with dllimport linkage,
3546               keep the old DECL_DLLIMPORT_P flag: the ADDR_EXPR using the
3547               decl may already have had TREE_INVARIANT and TREE_CONSTANT
3548               computed.
3549               We still remove the attribute so that assembler code refers
3550               to '&foo rather than '_imp__foo'.  */
3551           if (TREE_CODE (old) == VAR_DECL && TREE_ADDRESSABLE (old))
3552             DECL_DLLIMPORT_P (new) = 1;
3553         }
3554
3555       /* Let an inline definition silently override the external reference,
3556          but otherwise warn about attribute inconsistency.  */
3557       else if (TREE_CODE (new) == VAR_DECL
3558                || !DECL_DECLARED_INLINE_P (new))
3559         warning (OPT_Wattributes, "%q+D redeclared without dllimport attribute: "
3560                   "previous dllimport ignored", new);
3561     }
3562   else
3563     delete_dllimport_p = 0;
3564
3565   a = merge_attributes (DECL_ATTRIBUTES (old), DECL_ATTRIBUTES (new));
3566
3567   if (delete_dllimport_p)
3568     {
3569       tree prev, t;
3570       const size_t attr_len = strlen ("dllimport");
3571
3572       /* Scan the list for dllimport and delete it.  */
3573       for (prev = NULL_TREE, t = a; t; prev = t, t = TREE_CHAIN (t))
3574         {
3575           if (is_attribute_with_length_p ("dllimport", attr_len,
3576                                           TREE_PURPOSE (t)))
3577             {
3578               if (prev == NULL_TREE)
3579                 a = TREE_CHAIN (a);
3580               else
3581                 TREE_CHAIN (prev) = TREE_CHAIN (t);
3582               break;
3583             }
3584         }
3585     }
3586
3587   return a;
3588 }
3589
3590 /* Handle a "dllimport" or "dllexport" attribute; arguments as in
3591    struct attribute_spec.handler.  */
3592
3593 tree
3594 handle_dll_attribute (tree * pnode, tree name, tree args, int flags,
3595                       bool *no_add_attrs)
3596 {
3597   tree node = *pnode;
3598
3599   /* These attributes may apply to structure and union types being created,
3600      but otherwise should pass to the declaration involved.  */
3601   if (!DECL_P (node))
3602     {
3603       if (flags & ((int) ATTR_FLAG_DECL_NEXT | (int) ATTR_FLAG_FUNCTION_NEXT
3604                    | (int) ATTR_FLAG_ARRAY_NEXT))
3605         {
3606           *no_add_attrs = true;
3607           return tree_cons (name, args, NULL_TREE);
3608         }
3609       if (TREE_CODE (node) != RECORD_TYPE && TREE_CODE (node) != UNION_TYPE)
3610         {
3611           warning (OPT_Wattributes, "%qs attribute ignored",
3612                    IDENTIFIER_POINTER (name));
3613           *no_add_attrs = true;
3614         }
3615
3616       return NULL_TREE;
3617     }
3618
3619   /* Report error on dllimport ambiguities seen now before they cause
3620      any damage.  */
3621   if (is_attribute_p ("dllimport", name))
3622     {
3623       /* Honor any target-specific overrides. */
3624       if (!targetm.valid_dllimport_attribute_p (node))
3625         *no_add_attrs = true;
3626
3627      else if (TREE_CODE (node) == FUNCTION_DECL
3628                 && DECL_DECLARED_INLINE_P (node))
3629         {
3630           warning (OPT_Wattributes, "inline function %q+D declared as "
3631                   " dllimport: attribute ignored", node);
3632           *no_add_attrs = true;
3633         }
3634       /* Like MS, treat definition of dllimported variables and
3635          non-inlined functions on declaration as syntax errors. */
3636      else if (TREE_CODE (node) == FUNCTION_DECL && DECL_INITIAL (node))
3637         {
3638           error ("function %q+D definition is marked dllimport", node);
3639           *no_add_attrs = true;
3640         }
3641
3642      else if (TREE_CODE (node) == VAR_DECL)
3643         {
3644           if (DECL_INITIAL (node))
3645             {
3646               error ("variable %q+D definition is marked dllimport",
3647                      node);
3648               *no_add_attrs = true;
3649             }
3650
3651           /* `extern' needn't be specified with dllimport.
3652              Specify `extern' now and hope for the best.  Sigh.  */
3653           DECL_EXTERNAL (node) = 1;
3654           /* Also, implicitly give dllimport'd variables declared within
3655              a function global scope, unless declared static.  */
3656           if (current_function_decl != NULL_TREE && !TREE_STATIC (node))
3657             TREE_PUBLIC (node) = 1;
3658         }
3659
3660       if (*no_add_attrs == false)
3661         DECL_DLLIMPORT_P (node) = 1;
3662     }
3663
3664   /*  Report error if symbol is not accessible at global scope.  */
3665   if (!TREE_PUBLIC (node)
3666       && (TREE_CODE (node) == VAR_DECL
3667           || TREE_CODE (node) == FUNCTION_DECL))
3668     {
3669       error ("external linkage required for symbol %q+D because of "
3670              "%qs attribute", node, IDENTIFIER_POINTER (name));
3671       *no_add_attrs = true;
3672     }
3673
3674   return NULL_TREE;
3675 }
3676
3677 #endif /* TARGET_DLLIMPORT_DECL_ATTRIBUTES  */
3678 \f
3679 /* Set the type qualifiers for TYPE to TYPE_QUALS, which is a bitmask
3680    of the various TYPE_QUAL values.  */
3681
3682 static void
3683 set_type_quals (tree type, int type_quals)
3684 {
3685   TYPE_READONLY (type) = (type_quals & TYPE_QUAL_CONST) != 0;
3686   TYPE_VOLATILE (type) = (type_quals & TYPE_QUAL_VOLATILE) != 0;
3687   TYPE_RESTRICT (type) = (type_quals & TYPE_QUAL_RESTRICT) != 0;
3688 }
3689
3690 /* Returns true iff cand is equivalent to base with type_quals.  */
3691
3692 bool
3693 check_qualified_type (tree cand, tree base, int type_quals)
3694 {
3695   return (TYPE_QUALS (cand) == type_quals
3696           && TYPE_NAME (cand) == TYPE_NAME (base)
3697           /* Apparently this is needed for Objective-C.  */
3698           && TYPE_CONTEXT (cand) == TYPE_CONTEXT (base)
3699           && attribute_list_equal (TYPE_ATTRIBUTES (cand),
3700                                    TYPE_ATTRIBUTES (base)));
3701 }
3702
3703 /* Return a version of the TYPE, qualified as indicated by the
3704    TYPE_QUALS, if one exists.  If no qualified version exists yet,
3705    return NULL_TREE.  */
3706
3707 tree
3708 get_qualified_type (tree type, int type_quals)
3709 {
3710   tree t;
3711
3712   if (TYPE_QUALS (type) == type_quals)
3713     return type;
3714
3715   /* Search the chain of variants to see if there is already one there just
3716      like the one we need to have.  If so, use that existing one.  We must
3717      preserve the TYPE_NAME, since there is code that depends on this.  */
3718   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
3719     if (check_qualified_type (t, type, type_quals))
3720       return t;
3721
3722   return NULL_TREE;
3723 }
3724
3725 /* Like get_qualified_type, but creates the type if it does not
3726    exist.  This function never returns NULL_TREE.  */
3727
3728 tree
3729 build_qualified_type (tree type, int type_quals)
3730 {
3731   tree t;
3732
3733   /* See if we already have the appropriate qualified variant.  */
3734   t = get_qualified_type (type, type_quals);
3735
3736   /* If not, build it.  */
3737   if (!t)
3738     {
3739       t = build_variant_type_copy (type);
3740       set_type_quals (t, type_quals);
3741     }
3742
3743   return t;
3744 }
3745
3746 /* Create a new distinct copy of TYPE.  The new type is made its own
3747    MAIN_VARIANT.  */
3748
3749 tree
3750 build_distinct_type_copy (tree type)
3751 {
3752   tree t = copy_node (type);
3753
3754   TYPE_POINTER_TO (t) = 0;
3755   TYPE_REFERENCE_TO (t) = 0;
3756
3757   /* Make it its own variant.  */
3758   TYPE_MAIN_VARIANT (t) = t;
3759   TYPE_NEXT_VARIANT (t) = 0;
3760
3761   return t;
3762 }
3763
3764 /* Create a new variant of TYPE, equivalent but distinct.
3765    This is so the caller can modify it.  */
3766
3767 tree
3768 build_variant_type_copy (tree type)
3769 {
3770   tree t, m = TYPE_MAIN_VARIANT (type);
3771
3772   t = build_distinct_type_copy (type);
3773
3774   /* Add the new type to the chain of variants of TYPE.  */
3775   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3776   TYPE_NEXT_VARIANT (m) = t;
3777   TYPE_MAIN_VARIANT (t) = m;
3778
3779   return t;
3780 }
3781 \f
3782 /* Return true if the from tree in both tree maps are equal.  */
3783
3784 int
3785 tree_map_eq (const void *va, const void *vb)
3786 {
3787   const struct tree_map  *a = va, *b = vb;
3788   return (a->from == b->from);
3789 }
3790
3791 /* Hash a from tree in a tree_map.  */
3792
3793 unsigned int
3794 tree_map_hash (const void *item)
3795 {
3796   return (((const struct tree_map *) item)->hash);
3797 }
3798
3799 /* Return true if this tree map structure is marked for garbage collection
3800    purposes.  We simply return true if the from tree is marked, so that this
3801    structure goes away when the from tree goes away.  */
3802
3803 int
3804 tree_map_marked_p (const void *p)
3805 {
3806   tree from = ((struct tree_map *) p)->from;
3807
3808   return ggc_marked_p (from);
3809 }
3810
3811 /* Return true if the trees in the tree_int_map *'s VA and VB are equal.  */
3812
3813 static int
3814 tree_int_map_eq (const void *va, const void *vb)
3815 {
3816   const struct tree_int_map  *a = va, *b = vb;
3817   return (a->from == b->from);
3818 }
3819
3820 /* Hash a from tree in the tree_int_map * ITEM.  */
3821
3822 static unsigned int
3823 tree_int_map_hash (const void *item)
3824 {
3825   return htab_hash_pointer (((const struct tree_int_map *)item)->from);
3826 }
3827
3828 /* Return true if this tree int map structure is marked for garbage collection
3829    purposes.  We simply return true if the from tree_int_map *P's from tree is marked, so that this
3830    structure goes away when the from tree goes away.  */
3831
3832 static int
3833 tree_int_map_marked_p (const void *p)
3834 {
3835   tree from = ((struct tree_int_map *) p)->from;
3836
3837   return ggc_marked_p (from);
3838 }
3839 /* Lookup an init priority for FROM, and return it if we find one.  */
3840
3841 unsigned short
3842 decl_init_priority_lookup (tree from)
3843 {
3844   struct tree_int_map *h, in;
3845   in.from = from;
3846
3847   h = htab_find_with_hash (init_priority_for_decl,
3848                            &in, htab_hash_pointer (from));
3849   if (h)
3850     return h->to;
3851   return 0;
3852 }
3853
3854 /* Insert a mapping FROM->TO in the init priority hashtable.  */
3855
3856 void
3857 decl_init_priority_insert (tree from, unsigned short to)
3858 {
3859   struct tree_int_map *h;
3860   void **loc;
3861
3862   h = ggc_alloc (sizeof (struct tree_int_map));
3863   h->from = from;
3864   h->to = to;
3865   loc = htab_find_slot_with_hash (init_priority_for_decl, h,
3866                                   htab_hash_pointer (from), INSERT);
3867   *(struct tree_int_map **) loc = h;
3868 }
3869
3870 /* Look up a restrict qualified base decl for FROM.  */
3871
3872 tree
3873 decl_restrict_base_lookup (tree from)
3874 {
3875   struct tree_map *h;
3876   struct tree_map in;
3877
3878   in.from = from;
3879   h = htab_find_with_hash (restrict_base_for_decl, &in,
3880                            htab_hash_pointer (from));
3881   return h ? h->to : NULL_TREE;
3882 }
3883
3884 /* Record the restrict qualified base TO for FROM.  */
3885
3886 void
3887 decl_restrict_base_insert (tree from, tree to)
3888 {
3889   struct tree_map *h;
3890   void **loc;
3891
3892   h = ggc_alloc (sizeof (struct tree_map));
3893   h->hash = htab_hash_pointer (from);
3894   h->from = from;
3895   h->to = to;
3896   loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT);
3897   *(struct tree_map **) loc = h;
3898 }
3899
3900 /* Print out the statistics for the DECL_DEBUG_EXPR hash table.  */
3901
3902 static void
3903 print_debug_expr_statistics (void)
3904 {
3905   fprintf (stderr, "DECL_DEBUG_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3906            (long) htab_size (debug_expr_for_decl),
3907            (long) htab_elements (debug_expr_for_decl),
3908            htab_collisions (debug_expr_for_decl));
3909 }
3910
3911 /* Print out the statistics for the DECL_VALUE_EXPR hash table.  */
3912
3913 static void
3914 print_value_expr_statistics (void)
3915 {
3916   fprintf (stderr, "DECL_VALUE_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3917            (long) htab_size (value_expr_for_decl),
3918            (long) htab_elements (value_expr_for_decl),
3919            htab_collisions (value_expr_for_decl));
3920 }
3921
3922 /* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but
3923    don't print anything if the table is empty.  */
3924
3925 static void
3926 print_restrict_base_statistics (void)
3927 {
3928   if (htab_elements (restrict_base_for_decl) != 0)
3929     fprintf (stderr,
3930              "RESTRICT_BASE    hash: size %ld, %ld elements, %f collisions\n",
3931              (long) htab_size (restrict_base_for_decl),
3932              (long) htab_elements (restrict_base_for_decl),
3933              htab_collisions (restrict_base_for_decl));
3934 }
3935
3936 /* Lookup a debug expression for FROM, and return it if we find one.  */
3937
3938 tree
3939 decl_debug_expr_lookup (tree from)
3940 {
3941   struct tree_map *h, in;
3942   in.from = from;
3943
3944   h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
3945   if (h)
3946     return h->to;
3947   return NULL_TREE;
3948 }
3949
3950 /* Insert a mapping FROM->TO in the debug expression hashtable.  */
3951
3952 void
3953 decl_debug_expr_insert (tree from, tree to)
3954 {
3955   struct tree_map *h;
3956   void **loc;
3957
3958   h = ggc_alloc (sizeof (struct tree_map));
3959   h->hash = htab_hash_pointer (from);
3960   h->from = from;
3961   h->to = to;
3962   loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
3963   *(struct tree_map **) loc = h;
3964 }
3965
3966 /* Lookup a value expression for FROM, and return it if we find one.  */
3967
3968 tree
3969 decl_value_expr_lookup (tree from)
3970 {
3971   struct tree_map *h, in;
3972   in.from = from;
3973
3974   h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
3975   if (h)
3976     return h->to;
3977   return NULL_TREE;
3978 }
3979
3980 /* Insert a mapping FROM->TO in the value expression hashtable.  */
3981
3982 void
3983 decl_value_expr_insert (tree from, tree to)
3984 {
3985   struct tree_map *h;
3986   void **loc;
3987
3988   h = ggc_alloc (sizeof (struct tree_map));
3989   h->hash = htab_hash_pointer (from);
3990   h->from = from;
3991   h->to = to;
3992   loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
3993   *(struct tree_map **) loc = h;
3994 }
3995
3996 /* Hashing of types so that we don't make duplicates.
3997    The entry point is `type_hash_canon'.  */
3998
3999 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
4000    with types in the TREE_VALUE slots), by adding the hash codes
4001    of the individual types.  */
4002
4003 unsigned int
4004 type_hash_list (tree list, hashval_t hashcode)
4005 {
4006   tree tail;
4007
4008   for (tail = list; tail; tail = TREE_CHAIN (tail))
4009     if (TREE_VALUE (tail) != error_mark_node)
4010       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
4011                                         hashcode);
4012
4013   return hashcode;
4014 }
4015
4016 /* These are the Hashtable callback functions.  */
4017
4018 /* Returns true iff the types are equivalent.  */
4019
4020 static int
4021 type_hash_eq (const void *va, const void *vb)
4022 {
4023   const struct type_hash *a = va, *b = vb;
4024
4025   /* First test the things that are the same for all types.  */
4026   if (a->hash != b->hash
4027       || TREE_CODE (a->type) != TREE_CODE (b->type)
4028       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
4029       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
4030                                  TYPE_ATTRIBUTES (b->type))
4031       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
4032       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
4033     return 0;
4034
4035   switch (TREE_CODE (a->type))
4036     {
4037     case VOID_TYPE:
4038     case COMPLEX_TYPE:
4039     case POINTER_TYPE:
4040     case REFERENCE_TYPE:
4041       return 1;
4042
4043     case VECTOR_TYPE:
4044       return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
4045
4046     case ENUMERAL_TYPE:
4047       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
4048           && !(TYPE_VALUES (a->type)
4049                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
4050                && TYPE_VALUES (b->type)
4051                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
4052                && type_list_equal (TYPE_VALUES (a->type),
4053                                    TYPE_VALUES (b->type))))
4054         return 0;
4055
4056       /* ... fall through ... */
4057
4058     case INTEGER_TYPE:
4059     case REAL_TYPE:
4060     case BOOLEAN_TYPE:
4061     case CHAR_TYPE:
4062       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
4063                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
4064                                       TYPE_MAX_VALUE (b->type)))
4065               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
4066                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
4067                                          TYPE_MIN_VALUE (b->type))));
4068
4069     case OFFSET_TYPE:
4070       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
4071
4072     case METHOD_TYPE:
4073       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
4074               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4075                   || (TYPE_ARG_TYPES (a->type)
4076                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4077                       && TYPE_ARG_TYPES (b->type)
4078                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4079                       && type_list_equal (TYPE_ARG_TYPES (a->type),
4080                                           TYPE_ARG_TYPES (b->type)))));
4081
4082     case ARRAY_TYPE:
4083       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
4084
4085     case RECORD_TYPE:
4086     case UNION_TYPE:
4087     case QUAL_UNION_TYPE:
4088       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
4089               || (TYPE_FIELDS (a->type)
4090                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
4091                   && TYPE_FIELDS (b->type)
4092                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
4093                   && type_list_equal (TYPE_FIELDS (a->type),
4094                                       TYPE_FIELDS (b->type))));
4095
4096     case FUNCTION_TYPE:
4097       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4098               || (TYPE_ARG_TYPES (a->type)
4099                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4100                   && TYPE_ARG_TYPES (b->type)
4101                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4102                   && type_list_equal (TYPE_ARG_TYPES (a->type),
4103                                       TYPE_ARG_TYPES (b->type))));
4104
4105     default:
4106       return 0;
4107     }
4108 }
4109
4110 /* Return the cached hash value.  */
4111
4112 static hashval_t
4113 type_hash_hash (const void *item)
4114 {
4115   return ((const struct type_hash *) item)->hash;
4116 }
4117
4118 /* Look in the type hash table for a type isomorphic to TYPE.
4119    If one is found, return it.  Otherwise return 0.  */
4120
4121 tree
4122 type_hash_lookup (hashval_t hashcode, tree type)
4123 {
4124   struct type_hash *h, in;
4125
4126   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
4127      must call that routine before comparing TYPE_ALIGNs.  */
4128   layout_type (type);
4129
4130   in.hash = hashcode;
4131   in.type = type;
4132
4133   h = htab_find_with_hash (type_hash_table, &in, hashcode);
4134   if (h)
4135     return h->type;
4136   return NULL_TREE;
4137 }
4138
4139 /* Add an entry to the type-hash-table
4140    for a type TYPE whose hash code is HASHCODE.  */
4141
4142 void
4143 type_hash_add (hashval_t hashcode, tree type)
4144 {
4145   struct type_hash *h;
4146   void **loc;
4147
4148   h = ggc_alloc (sizeof (struct type_hash));
4149   h->hash = hashcode;
4150   h->type = type;
4151   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
4152   *(struct type_hash **) loc = h;
4153 }
4154
4155 /* Given TYPE, and HASHCODE its hash code, return the canonical
4156    object for an identical type if one already exists.
4157    Otherwise, return TYPE, and record it as the canonical object.
4158
4159    To use this function, first create a type of the sort you want.
4160    Then compute its hash code from the fields of the type that
4161    make it different from other similar types.
4162    Then call this function and use the value.  */
4163
4164 tree
4165 type_hash_canon (unsigned int hashcode, tree type)
4166 {
4167   tree t1;
4168
4169   /* The hash table only contains main variants, so ensure that's what we're
4170      being passed.  */
4171   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
4172
4173   if (!lang_hooks.types.hash_types)
4174     return type;
4175
4176   /* See if the type is in the hash table already.  If so, return it.
4177      Otherwise, add the type.  */
4178   t1 = type_hash_lookup (hashcode, type);
4179   if (t1 != 0)
4180     {
4181 #ifdef GATHER_STATISTICS
4182       tree_node_counts[(int) t_kind]--;
4183       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
4184 #endif
4185       return t1;
4186     }
4187   else
4188     {
4189       type_hash_add (hashcode, type);
4190       return type;
4191     }
4192 }
4193
4194 /* See if the data pointed to by the type hash table is marked.  We consider
4195    it marked if the type is marked or if a debug type number or symbol
4196    table entry has been made for the type.  This reduces the amount of
4197    debugging output and eliminates that dependency of the debug output on
4198    the number of garbage collections.  */
4199
4200 static int
4201 type_hash_marked_p (const void *p)
4202 {
4203   tree type = ((struct type_hash *) p)->type;
4204
4205   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
4206 }
4207
4208 static void
4209 print_type_hash_statistics (void)
4210 {
4211   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
4212            (long) htab_size (type_hash_table),
4213            (long) htab_elements (type_hash_table),
4214            htab_collisions (type_hash_table));
4215 }
4216
4217 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
4218    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
4219    by adding the hash codes of the individual attributes.  */
4220
4221 unsigned int
4222 attribute_hash_list (tree list, hashval_t hashcode)
4223 {
4224   tree tail;
4225
4226   for (tail = list; tail; tail = TREE_CHAIN (tail))
4227     /* ??? Do we want to add in TREE_VALUE too? */
4228     hashcode = iterative_hash_object
4229       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
4230   return hashcode;
4231 }
4232
4233 /* Given two lists of attributes, return true if list l2 is
4234    equivalent to l1.  */
4235
4236 int
4237 attribute_list_equal (tree l1, tree l2)
4238 {
4239   return attribute_list_contained (l1, l2)
4240          && attribute_list_contained (l2, l1);
4241 }
4242
4243 /* Given two lists of attributes, return true if list L2 is
4244    completely contained within L1.  */
4245 /* ??? This would be faster if attribute names were stored in a canonicalized
4246    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
4247    must be used to show these elements are equivalent (which they are).  */
4248 /* ??? It's not clear that attributes with arguments will always be handled
4249    correctly.  */
4250
4251 int
4252 attribute_list_contained (tree l1, tree l2)
4253 {
4254   tree t1, t2;
4255
4256   /* First check the obvious, maybe the lists are identical.  */
4257   if (l1 == l2)
4258     return 1;
4259
4260   /* Maybe the lists are similar.  */
4261   for (t1 = l1, t2 = l2;
4262        t1 != 0 && t2 != 0
4263         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
4264         && TREE_VALUE (t1) == TREE_VALUE (t2);
4265        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
4266
4267   /* Maybe the lists are equal.  */
4268   if (t1 == 0 && t2 == 0)
4269     return 1;
4270
4271   for (; t2 != 0; t2 = TREE_CHAIN (t2))
4272     {
4273       tree attr;
4274       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
4275            attr != NULL_TREE;
4276            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
4277                                     TREE_CHAIN (attr)))
4278         {
4279           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
4280             break;
4281         }
4282
4283       if (attr == 0)
4284         return 0;
4285
4286       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
4287         return 0;
4288     }
4289
4290   return 1;
4291 }
4292
4293 /* Given two lists of types
4294    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
4295    return 1 if the lists contain the same types in the same order.
4296    Also, the TREE_PURPOSEs must match.  */
4297
4298 int
4299 type_list_equal (tree l1, tree l2)
4300 {
4301   tree t1, t2;
4302
4303   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
4304     if (TREE_VALUE (t1) != TREE_VALUE (t2)
4305         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
4306             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
4307                   && (TREE_TYPE (TREE_PURPOSE (t1))
4308                       == TREE_TYPE (TREE_PURPOSE (t2))))))
4309       return 0;
4310
4311   return t1 == t2;
4312 }
4313
4314 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
4315    given by TYPE.  If the argument list accepts variable arguments,
4316    then this function counts only the ordinary arguments.  */
4317
4318 int
4319 type_num_arguments (tree type)
4320 {
4321   int i = 0;
4322   tree t;
4323
4324   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
4325     /* If the function does not take a variable number of arguments,
4326        the last element in the list will have type `void'.  */
4327     if (VOID_TYPE_P (TREE_VALUE (t)))
4328       break;
4329     else
4330       ++i;
4331
4332   return i;
4333 }
4334
4335 /* Nonzero if integer constants T1 and T2
4336    represent the same constant value.  */
4337
4338 int
4339 tree_int_cst_equal (tree t1, tree t2)
4340 {
4341   if (t1 == t2)
4342     return 1;
4343
4344   if (t1 == 0 || t2 == 0)
4345     return 0;
4346
4347   if (TREE_CODE (t1) == INTEGER_CST
4348       && TREE_CODE (t2) == INTEGER_CST
4349       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4350       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
4351     return 1;
4352
4353   return 0;
4354 }
4355
4356 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
4357    The precise way of comparison depends on their data type.  */
4358
4359 int
4360 tree_int_cst_lt (tree t1, tree t2)
4361 {
4362   if (t1 == t2)
4363     return 0;
4364
4365   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
4366     {
4367       int t1_sgn = tree_int_cst_sgn (t1);
4368       int t2_sgn = tree_int_cst_sgn (t2);
4369
4370       if (t1_sgn < t2_sgn)
4371         return 1;
4372       else if (t1_sgn > t2_sgn)
4373         return 0;
4374       /* Otherwise, both are non-negative, so we compare them as
4375          unsigned just in case one of them would overflow a signed
4376          type.  */
4377     }
4378   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4379     return INT_CST_LT (t1, t2);
4380
4381   return INT_CST_LT_UNSIGNED (t1, t2);
4382 }
4383
4384 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
4385
4386 int
4387 tree_int_cst_compare (tree t1, tree t2)
4388 {
4389   if (tree_int_cst_lt (t1, t2))
4390     return -1;
4391   else if (tree_int_cst_lt (t2, t1))
4392     return 1;
4393   else
4394     return 0;
4395 }
4396
4397 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4398    the host.  If POS is zero, the value can be represented in a single
4399    HOST_WIDE_INT.  If POS is nonzero, the value must be non-negative and can
4400    be represented in a single unsigned HOST_WIDE_INT.  */
4401
4402 int
4403 host_integerp (tree t, int pos)
4404 {
4405   return (TREE_CODE (t) == INTEGER_CST
4406           && ! TREE_OVERFLOW (t)
4407           && ((TREE_INT_CST_HIGH (t) == 0
4408                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4409               || (! pos && TREE_INT_CST_HIGH (t) == -1
4410                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4411                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
4412               || (pos && TREE_INT_CST_HIGH (t) == 0)));
4413 }
4414
4415 /* Return the HOST_WIDE_INT least significant bits of T if it is an
4416    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
4417    be non-negative.  We must be able to satisfy the above conditions.  */
4418
4419 HOST_WIDE_INT
4420 tree_low_cst (tree t, int pos)
4421 {
4422   gcc_assert (host_integerp (t, pos));
4423   return TREE_INT_CST_LOW (t);
4424 }
4425
4426 /* Return the most significant bit of the integer constant T.  */
4427
4428 int
4429 tree_int_cst_msb (tree t)
4430 {
4431   int prec;
4432   HOST_WIDE_INT h;
4433   unsigned HOST_WIDE_INT l;
4434
4435   /* Note that using TYPE_PRECISION here is wrong.  We care about the
4436      actual bits, not the (arbitrary) range of the type.  */
4437   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
4438   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
4439                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
4440   return (l & 1) == 1;
4441 }
4442
4443 /* Return an indication of the sign of the integer constant T.
4444    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
4445    Note that -1 will never be returned if T's type is unsigned.  */
4446
4447 int
4448 tree_int_cst_sgn (tree t)
4449 {
4450   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
4451     return 0;
4452   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
4453     return 1;
4454   else if (TREE_INT_CST_HIGH (t) < 0)
4455     return -1;
4456   else
4457     return 1;
4458 }
4459
4460 /* Compare two constructor-element-type constants.  Return 1 if the lists
4461    are known to be equal; otherwise return 0.  */
4462
4463 int
4464 simple_cst_list_equal (tree l1, tree l2)
4465 {
4466   while (l1 != NULL_TREE && l2 != NULL_TREE)
4467     {
4468       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
4469         return 0;
4470
4471       l1 = TREE_CHAIN (l1);
4472       l2 = TREE_CHAIN (l2);
4473     }
4474
4475   return l1 == l2;
4476 }
4477
4478 /* Return truthvalue of whether T1 is the same tree structure as T2.
4479    Return 1 if they are the same.
4480    Return 0 if they are understandably different.
4481    Return -1 if either contains tree structure not understood by
4482    this function.  */
4483
4484 int
4485 simple_cst_equal (tree t1, tree t2)
4486 {
4487   enum tree_code code1, code2;
4488   int cmp;
4489   int i;
4490
4491   if (t1 == t2)
4492     return 1;
4493   if (t1 == 0 || t2 == 0)
4494     return 0;
4495
4496   code1 = TREE_CODE (t1);
4497   code2 = TREE_CODE (t2);
4498
4499   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
4500     {
4501       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4502           || code2 == NON_LVALUE_EXPR)
4503         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4504       else
4505         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
4506     }
4507
4508   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4509            || code2 == NON_LVALUE_EXPR)
4510     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
4511
4512   if (code1 != code2)
4513     return 0;
4514
4515   switch (code1)
4516     {
4517     case INTEGER_CST:
4518       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4519               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
4520
4521     case REAL_CST:
4522       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
4523
4524     case STRING_CST:
4525       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
4526               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
4527                          TREE_STRING_LENGTH (t1)));
4528
4529     case CONSTRUCTOR:
4530       {
4531         unsigned HOST_WIDE_INT idx;
4532         VEC(constructor_elt, gc) *v1 = CONSTRUCTOR_ELTS (t1);
4533         VEC(constructor_elt, gc) *v2 = CONSTRUCTOR_ELTS (t2);
4534
4535         if (VEC_length (constructor_elt, v1) != VEC_length (constructor_elt, v2))
4536           return false;
4537
4538         for (idx = 0; idx < VEC_length (constructor_elt, v1); ++idx)
4539           /* ??? Should we handle also fields here? */
4540           if (!simple_cst_equal (VEC_index (constructor_elt, v1, idx)->value,
4541                                  VEC_index (constructor_elt, v2, idx)->value))
4542             return false;
4543         return true;
4544       }
4545
4546     case SAVE_EXPR:
4547       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4548
4549     case CALL_EXPR:
4550       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4551       if (cmp <= 0)
4552         return cmp;
4553       return
4554         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4555
4556     case TARGET_EXPR:
4557       /* Special case: if either target is an unallocated VAR_DECL,
4558          it means that it's going to be unified with whatever the
4559          TARGET_EXPR is really supposed to initialize, so treat it
4560          as being equivalent to anything.  */
4561       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
4562            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
4563            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
4564           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
4565               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
4566               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
4567         cmp = 1;
4568       else
4569         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4570
4571       if (cmp <= 0)
4572         return cmp;
4573
4574       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4575
4576     case WITH_CLEANUP_EXPR:
4577       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4578       if (cmp <= 0)
4579         return cmp;
4580
4581       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
4582
4583     case COMPONENT_REF:
4584       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
4585         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4586
4587       return 0;
4588
4589     case VAR_DECL:
4590     case PARM_DECL:
4591     case CONST_DECL:
4592     case FUNCTION_DECL:
4593       return 0;
4594
4595     default:
4596       break;
4597     }
4598
4599   /* This general rule works for most tree codes.  All exceptions should be
4600      handled above.  If this is a language-specific tree code, we can't
4601      trust what might be in the operand, so say we don't know
4602      the situation.  */
4603   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
4604     return -1;
4605
4606   switch (TREE_CODE_CLASS (code1))
4607     {
4608     case tcc_unary:
4609     case tcc_binary:
4610     case tcc_comparison:
4611     case tcc_expression:
4612     case tcc_reference:
4613     case tcc_statement:
4614       cmp = 1;
4615       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
4616         {
4617           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
4618           if (cmp <= 0)
4619             return cmp;
4620         }
4621
4622       return cmp;
4623
4624     default:
4625       return -1;
4626     }
4627 }
4628
4629 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
4630    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
4631    than U, respectively.  */
4632
4633 int
4634 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
4635 {
4636   if (tree_int_cst_sgn (t) < 0)
4637     return -1;
4638   else if (TREE_INT_CST_HIGH (t) != 0)
4639     return 1;
4640   else if (TREE_INT_CST_LOW (t) == u)
4641     return 0;
4642   else if (TREE_INT_CST_LOW (t) < u)
4643     return -1;
4644   else
4645     return 1;
4646 }
4647
4648 /* Return true if CODE represents an associative tree code.  Otherwise
4649    return false.  */
4650 bool
4651 associative_tree_code (enum tree_code code)
4652 {
4653   switch (code)
4654     {
4655     case BIT_IOR_EXPR:
4656     case BIT_AND_EXPR:
4657     case BIT_XOR_EXPR:
4658     case PLUS_EXPR:
4659     case MULT_EXPR:
4660     case MIN_EXPR:
4661     case MAX_EXPR:
4662       return true;
4663
4664     default:
4665       break;
4666     }
4667   return false;
4668 }
4669
4670 /* Return true if CODE represents a commutative tree code.  Otherwise
4671    return false.  */
4672 bool
4673 commutative_tree_code (enum tree_code code)
4674 {
4675   switch (code)
4676     {
4677     case PLUS_EXPR:
4678     case MULT_EXPR:
4679     case MIN_EXPR:
4680     case MAX_EXPR:
4681     case BIT_IOR_EXPR:
4682     case BIT_XOR_EXPR:
4683     case BIT_AND_EXPR:
4684     case NE_EXPR:
4685     case EQ_EXPR:
4686     case UNORDERED_EXPR:
4687     case ORDERED_EXPR:
4688     case UNEQ_EXPR:
4689     case LTGT_EXPR:
4690     case TRUTH_AND_EXPR:
4691     case TRUTH_XOR_EXPR:
4692     case TRUTH_OR_EXPR:
4693       return true;
4694
4695     default:
4696       break;
4697     }
4698   return false;
4699 }
4700
4701 /* Generate a hash value for an expression.  This can be used iteratively
4702    by passing a previous result as the "val" argument.
4703
4704    This function is intended to produce the same hash for expressions which
4705    would compare equal using operand_equal_p.  */
4706
4707 hashval_t
4708 iterative_hash_expr (tree t, hashval_t val)
4709 {
4710   int i;
4711   enum tree_code code;
4712   char class;
4713
4714   if (t == NULL_TREE)
4715     return iterative_hash_pointer (t, val);
4716
4717   code = TREE_CODE (t);
4718
4719   switch (code)
4720     {
4721     /* Alas, constants aren't shared, so we can't rely on pointer
4722        identity.  */
4723     case INTEGER_CST:
4724       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4725       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4726     case REAL_CST:
4727       {
4728         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4729
4730         return iterative_hash_hashval_t (val2, val);
4731       }
4732     case STRING_CST:
4733       return iterative_hash (TREE_STRING_POINTER (t),
4734                              TREE_STRING_LENGTH (t), val);
4735     case COMPLEX_CST:
4736       val = iterative_hash_expr (TREE_REALPART (t), val);
4737       return iterative_hash_expr (TREE_IMAGPART (t), val);
4738     case VECTOR_CST:
4739       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4740
4741     case SSA_NAME:
4742     case VALUE_HANDLE:
4743       /* we can just compare by pointer.  */
4744       return iterative_hash_pointer (t, val);
4745
4746     case TREE_LIST:
4747       /* A list of expressions, for a CALL_EXPR or as the elements of a
4748          VECTOR_CST.  */
4749       for (; t; t = TREE_CHAIN (t))
4750         val = iterative_hash_expr (TREE_VALUE (t), val);
4751       return val;
4752     case CONSTRUCTOR:
4753       {
4754         unsigned HOST_WIDE_INT idx;
4755         tree field, value;
4756         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value)
4757           {
4758             val = iterative_hash_expr (field, val);
4759             val = iterative_hash_expr (value, val);
4760           }
4761         return val;
4762       }
4763     case FUNCTION_DECL:
4764       /* When referring to a built-in FUNCTION_DECL, use the
4765          __builtin__ form.  Otherwise nodes that compare equal
4766          according to operand_equal_p might get different
4767          hash codes.  */
4768       if (DECL_BUILT_IN (t))
4769         {
4770           val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)],
4771                                       val);
4772           return val;
4773         }
4774       /* else FALL THROUGH */
4775     default:
4776       class = TREE_CODE_CLASS (code);
4777
4778       if (class == tcc_declaration)
4779         {
4780           /* DECL's have a unique ID */
4781           val = iterative_hash_host_wide_int (DECL_UID (t), val);
4782         }
4783       else
4784         {
4785           gcc_assert (IS_EXPR_CODE_CLASS (class));
4786
4787           val = iterative_hash_object (code, val);
4788
4789           /* Don't hash the type, that can lead to having nodes which
4790              compare equal according to operand_equal_p, but which
4791              have different hash codes.  */
4792           if (code == NOP_EXPR
4793               || code == CONVERT_EXPR
4794               || code == NON_LVALUE_EXPR)
4795             {
4796               /* Make sure to include signness in the hash computation.  */
4797               val += TYPE_UNSIGNED (TREE_TYPE (t));
4798               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4799             }
4800
4801           else if (commutative_tree_code (code))
4802             {
4803               /* It's a commutative expression.  We want to hash it the same
4804                  however it appears.  We do this by first hashing both operands
4805                  and then rehashing based on the order of their independent
4806                  hashes.  */
4807               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4808               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4809               hashval_t t;
4810
4811               if (one > two)
4812                 t = one, one = two, two = t;
4813
4814               val = iterative_hash_hashval_t (one, val);
4815               val = iterative_hash_hashval_t (two, val);
4816             }
4817           else
4818             for (i = TREE_CODE_LENGTH (code) - 1; i >= 0; --i)
4819               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4820         }
4821       return val;
4822       break;
4823     }
4824 }
4825 \f
4826 /* Constructors for pointer, array and function types.
4827    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4828    constructed by language-dependent code, not here.)  */
4829
4830 /* Construct, lay out and return the type of pointers to TO_TYPE with
4831    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4832    reference all of memory. If such a type has already been
4833    constructed, reuse it.  */
4834
4835 tree
4836 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4837                              bool can_alias_all)
4838 {
4839   tree t;
4840
4841   if (to_type == error_mark_node)
4842     return error_mark_node;
4843
4844   /* In some cases, languages will have things that aren't a POINTER_TYPE
4845      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4846      In that case, return that type without regard to the rest of our
4847      operands.
4848
4849      ??? This is a kludge, but consistent with the way this function has
4850      always operated and there doesn't seem to be a good way to avoid this
4851      at the moment.  */
4852   if (TYPE_POINTER_TO (to_type) != 0
4853       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4854     return TYPE_POINTER_TO (to_type);
4855
4856   /* First, if we already have a type for pointers to TO_TYPE and it's
4857      the proper mode, use it.  */
4858   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4859     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4860       return t;
4861
4862   t = make_node (POINTER_TYPE);
4863
4864   TREE_TYPE (t) = to_type;
4865   TYPE_MODE (t) = mode;
4866   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4867   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4868   TYPE_POINTER_TO (to_type) = t;
4869
4870   /* Lay out the type.  This function has many callers that are concerned
4871      with expression-construction, and this simplifies them all.  */
4872   layout_type (t);
4873
4874   return t;
4875 }
4876
4877 /* By default build pointers in ptr_mode.  */
4878
4879 tree
4880 build_pointer_type (tree to_type)
4881 {
4882   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4883 }
4884
4885 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4886
4887 tree
4888 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4889                                bool can_alias_all)
4890 {
4891   tree t;
4892
4893   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4894      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4895      In that case, return that type without regard to the rest of our
4896      operands.
4897
4898      ??? This is a kludge, but consistent with the way this function has
4899      always operated and there doesn't seem to be a good way to avoid this
4900      at the moment.  */
4901   if (TYPE_REFERENCE_TO (to_type) != 0
4902       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4903     return TYPE_REFERENCE_TO (to_type);
4904
4905   /* First, if we already have a type for pointers to TO_TYPE and it's
4906      the proper mode, use it.  */
4907   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4908     if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4909       return t;
4910
4911   t = make_node (REFERENCE_TYPE);
4912
4913   TREE_TYPE (t) = to_type;
4914   TYPE_MODE (t) = mode;
4915   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4916   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4917   TYPE_REFERENCE_TO (to_type) = t;
4918
4919   layout_type (t);
4920
4921   return t;
4922 }
4923
4924
4925 /* Build the node for the type of references-to-TO_TYPE by default
4926    in ptr_mode.  */
4927
4928 tree
4929 build_reference_type (tree to_type)
4930 {
4931   return build_reference_type_for_mode (to_type, ptr_mode, false);
4932 }
4933
4934 /* Build a type that is compatible with t but has no cv quals anywhere
4935    in its type, thus
4936
4937    const char *const *const *  ->  char ***.  */
4938
4939 tree
4940 build_type_no_quals (tree t)
4941 {
4942   switch (TREE_CODE (t))
4943     {
4944     case POINTER_TYPE:
4945       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4946                                           TYPE_MODE (t),
4947                                           TYPE_REF_CAN_ALIAS_ALL (t));
4948     case REFERENCE_TYPE:
4949       return
4950         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4951                                        TYPE_MODE (t),
4952                                        TYPE_REF_CAN_ALIAS_ALL (t));
4953     default:
4954       return TYPE_MAIN_VARIANT (t);
4955     }
4956 }
4957
4958 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4959    MAXVAL should be the maximum value in the domain
4960    (one less than the length of the array).
4961
4962    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4963    We don't enforce this limit, that is up to caller (e.g. language front end).
4964    The limit exists because the result is a signed type and we don't handle
4965    sizes that use more than one HOST_WIDE_INT.  */
4966
4967 tree
4968 build_index_type (tree maxval)
4969 {
4970   tree itype = make_node (INTEGER_TYPE);
4971
4972   TREE_TYPE (itype) = sizetype;
4973   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4974   TYPE_MIN_VALUE (itype) = size_zero_node;
4975   TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
4976   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4977   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4978   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4979   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4980   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4981
4982   if (host_integerp (maxval, 1))
4983     return type_hash_canon (tree_low_cst (maxval, 1), itype);
4984   else
4985     return itype;
4986 }
4987
4988 /* Builds a signed or unsigned integer type of precision PRECISION.
4989    Used for C bitfields whose precision does not match that of
4990    built-in target types.  */
4991 tree
4992 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
4993                                 int unsignedp)
4994 {
4995   tree itype = make_node (INTEGER_TYPE);
4996
4997   TYPE_PRECISION (itype) = precision;
4998
4999   if (unsignedp)
5000     fixup_unsigned_type (itype);
5001   else
5002     fixup_signed_type (itype);
5003
5004   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
5005     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
5006
5007   return itype;
5008 }
5009
5010 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
5011    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
5012    low bound LOWVAL and high bound HIGHVAL.
5013    if TYPE==NULL_TREE, 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     case CHAR_TYPE:
5679       /* Scalar types are variably modified if their end points
5680          aren't constant.  */
5681       RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
5682       RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
5683       break;
5684
5685     case RECORD_TYPE:
5686     case UNION_TYPE:
5687     case QUAL_UNION_TYPE:
5688       /* We can't see if any of the field are variably-modified by the
5689          definition we normally use, since that would produce infinite
5690          recursion via pointers.  */
5691       /* This is variably modified if some field's type is.  */
5692       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
5693         if (TREE_CODE (t) == FIELD_DECL)
5694           {
5695             RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
5696             RETURN_TRUE_IF_VAR (DECL_SIZE (t));
5697             RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
5698
5699             if (TREE_CODE (type) == QUAL_UNION_TYPE)
5700               RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
5701           }
5702         break;
5703
5704     default:
5705       break;
5706     }
5707
5708   /* The current language may have other cases to check, but in general,
5709      all other types are not variably modified.  */
5710   return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
5711
5712 #undef RETURN_TRUE_IF_VAR
5713 }
5714
5715 /* Given a DECL or TYPE, return the scope in which it was declared, or
5716    NULL_TREE if there is no containing scope.  */
5717
5718 tree
5719 get_containing_scope (tree t)
5720 {
5721   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
5722 }
5723
5724 /* Return the innermost context enclosing DECL that is
5725    a FUNCTION_DECL, or zero if none.  */
5726
5727 tree
5728 decl_function_context (tree decl)
5729 {
5730   tree context;
5731
5732   if (TREE_CODE (decl) == ERROR_MARK)
5733     return 0;
5734
5735   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
5736      where we look up the function at runtime.  Such functions always take
5737      a first argument of type 'pointer to real context'.
5738
5739      C++ should really be fixed to use DECL_CONTEXT for the real context,
5740      and use something else for the "virtual context".  */
5741   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
5742     context
5743       = TYPE_MAIN_VARIANT
5744         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
5745   else
5746     context = DECL_CONTEXT (decl);
5747
5748   while (context && TREE_CODE (context) != FUNCTION_DECL)
5749     {
5750       if (TREE_CODE (context) == BLOCK)
5751         context = BLOCK_SUPERCONTEXT (context);
5752       else
5753         context = get_containing_scope (context);
5754     }
5755
5756   return context;
5757 }
5758
5759 /* Return the innermost context enclosing DECL that is
5760    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5761    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
5762
5763 tree
5764 decl_type_context (tree decl)
5765 {
5766   tree context = DECL_CONTEXT (decl);
5767
5768   while (context)
5769     switch (TREE_CODE (context))
5770       {
5771       case NAMESPACE_DECL:
5772       case TRANSLATION_UNIT_DECL:
5773         return NULL_TREE;
5774
5775       case RECORD_TYPE:
5776       case UNION_TYPE:
5777       case QUAL_UNION_TYPE:
5778         return context;
5779
5780       case TYPE_DECL:
5781       case FUNCTION_DECL:
5782         context = DECL_CONTEXT (context);
5783         break;
5784
5785       case BLOCK:
5786         context = BLOCK_SUPERCONTEXT (context);
5787         break;
5788
5789       default:
5790         gcc_unreachable ();
5791       }
5792
5793   return NULL_TREE;
5794 }
5795
5796 /* CALL is a CALL_EXPR.  Return the declaration for the function
5797    called, or NULL_TREE if the called function cannot be
5798    determined.  */
5799
5800 tree
5801 get_callee_fndecl (tree call)
5802 {
5803   tree addr;
5804
5805   /* It's invalid to call this function with anything but a
5806      CALL_EXPR.  */
5807   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5808
5809   /* The first operand to the CALL is the address of the function
5810      called.  */
5811   addr = TREE_OPERAND (call, 0);
5812
5813   STRIP_NOPS (addr);
5814
5815   /* If this is a readonly function pointer, extract its initial value.  */
5816   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5817       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5818       && DECL_INITIAL (addr))
5819     addr = DECL_INITIAL (addr);
5820
5821   /* If the address is just `&f' for some function `f', then we know
5822      that `f' is being called.  */
5823   if (TREE_CODE (addr) == ADDR_EXPR
5824       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5825     return TREE_OPERAND (addr, 0);
5826
5827   /* We couldn't figure out what was being called.  Maybe the front
5828      end has some idea.  */
5829   return lang_hooks.lang_get_callee_fndecl (call);
5830 }
5831
5832 /* Print debugging information about tree nodes generated during the compile,
5833    and any language-specific information.  */
5834
5835 void
5836 dump_tree_statistics (void)
5837 {
5838 #ifdef GATHER_STATISTICS
5839   int i;
5840   int total_nodes, total_bytes;
5841 #endif
5842
5843   fprintf (stderr, "\n??? tree nodes created\n\n");
5844 #ifdef GATHER_STATISTICS
5845   fprintf (stderr, "Kind                   Nodes      Bytes\n");
5846   fprintf (stderr, "---------------------------------------\n");
5847   total_nodes = total_bytes = 0;
5848   for (i = 0; i < (int) all_kinds; i++)
5849     {
5850       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5851                tree_node_counts[i], tree_node_sizes[i]);
5852       total_nodes += tree_node_counts[i];
5853       total_bytes += tree_node_sizes[i];
5854     }
5855   fprintf (stderr, "---------------------------------------\n");
5856   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5857   fprintf (stderr, "---------------------------------------\n");
5858   ssanames_print_statistics ();
5859   phinodes_print_statistics ();
5860 #else
5861   fprintf (stderr, "(No per-node statistics)\n");
5862 #endif
5863   print_type_hash_statistics ();
5864   print_debug_expr_statistics ();
5865   print_value_expr_statistics ();
5866   print_restrict_base_statistics ();
5867   lang_hooks.print_statistics ();
5868 }
5869 \f
5870 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
5871
5872 /* Generate a crc32 of a string.  */
5873
5874 unsigned
5875 crc32_string (unsigned chksum, const char *string)
5876 {
5877   do
5878     {
5879       unsigned value = *string << 24;
5880       unsigned ix;
5881
5882       for (ix = 8; ix--; value <<= 1)
5883         {
5884           unsigned feedback;
5885
5886           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
5887           chksum <<= 1;
5888           chksum ^= feedback;
5889         }
5890     }
5891   while (*string++);
5892   return chksum;
5893 }
5894
5895 /* P is a string that will be used in a symbol.  Mask out any characters
5896    that are not valid in that context.  */
5897
5898 void
5899 clean_symbol_name (char *p)
5900 {
5901   for (; *p; p++)
5902     if (! (ISALNUM (*p)
5903 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
5904             || *p == '$'
5905 #endif
5906 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
5907             || *p == '.'
5908 #endif
5909            ))
5910       *p = '_';
5911 }
5912
5913 /* Generate a name for a function unique to this translation unit.
5914    TYPE is some string to identify the purpose of this function to the
5915    linker or collect2.  */
5916
5917 tree
5918 get_file_function_name_long (const char *type)
5919 {
5920   char *buf;
5921   const char *p;
5922   char *q;
5923
5924   if (first_global_object_name)
5925     {
5926       p = first_global_object_name;
5927
5928       /* For type 'F', the generated name must be unique not only to this
5929          translation unit but also to any given link.  Since global names
5930          can be overloaded, we concatenate the first global object name
5931          with a string derived from the file name of this object.  */
5932       if (!strcmp (type, "F"))
5933         {
5934           const char *file = main_input_filename;
5935
5936           if (! file)
5937             file = input_filename;
5938
5939           q = alloca (strlen (p) + 10);
5940           sprintf (q, "%s_%08X", p, crc32_string (0, file));
5941
5942           p = q;
5943         }
5944     }
5945   else
5946     {
5947       /* We don't have anything that we know to be unique to this translation
5948          unit, so use what we do have and throw in some randomness.  */
5949       unsigned len;
5950       const char *name = weak_global_object_name;
5951       const char *file = main_input_filename;
5952
5953       if (! name)
5954         name = "";
5955       if (! file)
5956         file = input_filename;
5957
5958       len = strlen (file);
5959       q = alloca (9 * 2 + len + 1);
5960       memcpy (q, file, len + 1);
5961       clean_symbol_name (q);
5962
5963       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
5964                crc32_string (0, flag_random_seed));
5965
5966       p = q;
5967     }
5968
5969   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
5970
5971   /* Set up the name of the file-level functions we may need.
5972      Use a global object (which is already required to be unique over
5973      the program) rather than the file name (which imposes extra
5974      constraints).  */
5975   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
5976
5977   return get_identifier (buf);
5978 }
5979
5980 /* If KIND=='I', return a suitable global initializer (constructor) name.
5981    If KIND=='D', return a suitable global clean-up (destructor) name.  */
5982
5983 tree
5984 get_file_function_name (int kind)
5985 {
5986   char p[2];
5987
5988   p[0] = kind;
5989   p[1] = 0;
5990
5991   return get_file_function_name_long (p);
5992 }
5993 \f
5994 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
5995
5996 /* Complain that the tree code of NODE does not match the expected 0
5997    terminated list of trailing codes. The trailing code list can be
5998    empty, for a more vague error message.  FILE, LINE, and FUNCTION
5999    are of the caller.  */
6000
6001 void
6002 tree_check_failed (const tree node, const char *file,
6003                    int line, const char *function, ...)
6004 {
6005   va_list args;
6006   char *buffer;
6007   unsigned length = 0;
6008   int code;
6009
6010   va_start (args, function);
6011   while ((code = va_arg (args, int)))
6012     length += 4 + strlen (tree_code_name[code]);
6013   va_end (args);
6014   if (length)
6015     {
6016       va_start (args, function);
6017       length += strlen ("expected ");
6018       buffer = alloca (length);
6019       length = 0;
6020       while ((code = va_arg (args, int)))
6021         {
6022           const char *prefix = length ? " or " : "expected ";
6023
6024           strcpy (buffer + length, prefix);
6025           length += strlen (prefix);
6026           strcpy (buffer + length, tree_code_name[code]);
6027           length += strlen (tree_code_name[code]);
6028         }
6029       va_end (args);
6030     }
6031   else
6032     buffer = (char *)"unexpected node";
6033
6034   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6035                   buffer, tree_code_name[TREE_CODE (node)],
6036                   function, trim_filename (file), line);
6037 }
6038
6039 /* Complain that the tree code of NODE does match the expected 0
6040    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
6041    the caller.  */
6042
6043 void
6044 tree_not_check_failed (const tree node, const char *file,
6045                        int line, const char *function, ...)
6046 {
6047   va_list args;
6048   char *buffer;
6049   unsigned length = 0;
6050   int code;
6051
6052   va_start (args, function);
6053   while ((code = va_arg (args, int)))
6054     length += 4 + strlen (tree_code_name[code]);
6055   va_end (args);
6056   va_start (args, function);
6057   buffer = alloca (length);
6058   length = 0;
6059   while ((code = va_arg (args, int)))
6060     {
6061       if (length)
6062         {
6063           strcpy (buffer + length, " or ");
6064           length += 4;
6065         }
6066       strcpy (buffer + length, tree_code_name[code]);
6067       length += strlen (tree_code_name[code]);
6068     }
6069   va_end (args);
6070
6071   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
6072                   buffer, tree_code_name[TREE_CODE (node)],
6073                   function, trim_filename (file), line);
6074 }
6075
6076 /* Similar to tree_check_failed, except that we check for a class of tree
6077    code, given in CL.  */
6078
6079 void
6080 tree_class_check_failed (const tree node, const enum tree_code_class cl,
6081                          const char *file, int line, const char *function)
6082 {
6083   internal_error
6084     ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
6085      TREE_CODE_CLASS_STRING (cl),
6086      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6087      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6088 }
6089
6090 /* Similar to tree_check_failed, except that instead of specifying a
6091    dozen codes, use the knowledge that they're all sequential.  */
6092
6093 void
6094 tree_range_check_failed (const tree node, const char *file, int line,
6095                          const char *function, enum tree_code c1,
6096                          enum tree_code c2)
6097 {
6098   char *buffer;
6099   unsigned length = 0;
6100   enum tree_code c;
6101
6102   for (c = c1; c <= c2; ++c)
6103     length += 4 + strlen (tree_code_name[c]);
6104
6105   length += strlen ("expected ");
6106   buffer = alloca (length);
6107   length = 0;
6108
6109   for (c = c1; c <= c2; ++c)
6110     {
6111       const char *prefix = length ? " or " : "expected ";
6112
6113       strcpy (buffer + length, prefix);
6114       length += strlen (prefix);
6115       strcpy (buffer + length, tree_code_name[c]);
6116       length += strlen (tree_code_name[c]);
6117     }
6118
6119   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6120                   buffer, tree_code_name[TREE_CODE (node)],
6121                   function, trim_filename (file), line);
6122 }
6123
6124
6125 /* Similar to tree_check_failed, except that we check that a tree does
6126    not have the specified code, given in CL.  */
6127
6128 void
6129 tree_not_class_check_failed (const tree node, const enum tree_code_class cl,
6130                              const char *file, int line, const char *function)
6131 {
6132   internal_error
6133     ("tree check: did not expect class %qs, have %qs (%s) in %s, at %s:%d",
6134      TREE_CODE_CLASS_STRING (cl),
6135      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6136      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6137 }
6138
6139
6140 /* Similar to tree_check_failed but applied to OMP_CLAUSE codes.  */
6141
6142 void
6143 omp_clause_check_failed (const tree node, const char *file, int line,
6144                          const char *function, enum omp_clause_code code)
6145 {
6146   internal_error ("tree check: expected omp_clause %s, have %s in %s, at %s:%d",
6147                   omp_clause_code_name[code], tree_code_name[TREE_CODE (node)],
6148                   function, trim_filename (file), line);
6149 }
6150
6151
6152 /* Similar to tree_range_check_failed but applied to OMP_CLAUSE codes.  */
6153
6154 void
6155 omp_clause_range_check_failed (const tree node, const char *file, int line,
6156                                const char *function, enum omp_clause_code c1,
6157                                enum omp_clause_code c2)
6158 {
6159   char *buffer;
6160   unsigned length = 0;
6161   enum omp_clause_code c;
6162
6163   for (c = c1; c <= c2; ++c)
6164     length += 4 + strlen (omp_clause_code_name[c]);
6165
6166   length += strlen ("expected ");
6167   buffer = alloca (length);
6168   length = 0;
6169
6170   for (c = c1; c <= c2; ++c)
6171     {
6172       const char *prefix = length ? " or " : "expected ";
6173
6174       strcpy (buffer + length, prefix);
6175       length += strlen (prefix);
6176       strcpy (buffer + length, omp_clause_code_name[c]);
6177       length += strlen (omp_clause_code_name[c]);
6178     }
6179
6180   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6181                   buffer, omp_clause_code_name[TREE_CODE (node)],
6182                   function, trim_filename (file), line);
6183 }
6184
6185
6186 #undef DEFTREESTRUCT
6187 #define DEFTREESTRUCT(VAL, NAME) NAME,
6188
6189 static const char *ts_enum_names[] = {
6190 #include "treestruct.def"
6191 };
6192 #undef DEFTREESTRUCT
6193
6194 #define TS_ENUM_NAME(EN) (ts_enum_names[(EN)])
6195
6196 /* Similar to tree_class_check_failed, except that we check for
6197    whether CODE contains the tree structure identified by EN.  */
6198
6199 void
6200 tree_contains_struct_check_failed (const tree node,
6201                                    const enum tree_node_structure_enum en,
6202                                    const char *file, int line,
6203                                    const char *function)
6204 {
6205   internal_error
6206     ("tree check: expected tree that contains %qs structure, have %qs  in %s, at %s:%d",
6207      TS_ENUM_NAME(en),
6208      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6209 }
6210
6211
6212 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
6213    (dynamically sized) vector.  */
6214
6215 void
6216 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
6217                            const char *function)
6218 {
6219   internal_error
6220     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
6221      idx + 1, len, function, trim_filename (file), line);
6222 }
6223
6224 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
6225    (dynamically sized) vector.  */
6226
6227 void
6228 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
6229                             const char *function)
6230 {
6231   internal_error
6232     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
6233      idx + 1, len, function, trim_filename (file), line);
6234 }
6235
6236 /* Similar to above, except that the check is for the bounds of the operand
6237    vector of an expression node.  */
6238
6239 void
6240 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
6241                            int line, const char *function)
6242 {
6243   internal_error
6244     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
6245      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
6246      function, trim_filename (file), line);
6247 }
6248
6249 /* Similar to above, except that the check is for the number of
6250    operands of an OMP_CLAUSE node.  */
6251
6252 void
6253 omp_clause_operand_check_failed (int idx, tree t, const char *file,
6254                                  int line, const char *function)
6255 {
6256   internal_error
6257     ("tree check: accessed operand %d of omp_clause %s with %d operands "
6258      "in %s, at %s:%d", idx + 1, omp_clause_code_name[OMP_CLAUSE_CODE (t)],
6259      omp_clause_num_ops [OMP_CLAUSE_CODE (t)], function,
6260      trim_filename (file), line);
6261 }
6262 #endif /* ENABLE_TREE_CHECKING */
6263 \f
6264 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
6265    and mapped to the machine mode MODE.  Initialize its fields and build
6266    the information necessary for debugging output.  */
6267
6268 static tree
6269 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
6270 {
6271   tree t = make_node (VECTOR_TYPE);
6272
6273   TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
6274   SET_TYPE_VECTOR_SUBPARTS (t, nunits);
6275   TYPE_MODE (t) = mode;
6276   TYPE_READONLY (t) = TYPE_READONLY (innertype);
6277   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
6278
6279   layout_type (t);
6280
6281   {
6282     tree index = build_int_cst (NULL_TREE, nunits - 1);
6283     tree array = build_array_type (innertype, build_index_type (index));
6284     tree rt = make_node (RECORD_TYPE);
6285
6286     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
6287     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
6288     layout_type (rt);
6289     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
6290     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
6291        the representation type, and we want to find that die when looking up
6292        the vector type.  This is most easily achieved by making the TYPE_UID
6293        numbers equal.  */
6294     TYPE_UID (rt) = TYPE_UID (t);
6295   }
6296
6297   /* Build our main variant, based on the main variant of the inner type.  */
6298   if (TYPE_MAIN_VARIANT (innertype) != innertype)
6299     {
6300       tree innertype_main_variant = TYPE_MAIN_VARIANT (innertype);
6301       unsigned int hash = TYPE_HASH (innertype_main_variant);
6302       TYPE_MAIN_VARIANT (t)
6303         = type_hash_canon (hash, make_vector_type (innertype_main_variant,
6304                                                    nunits, mode));
6305     }
6306
6307   return t;
6308 }
6309
6310 static tree
6311 make_or_reuse_type (unsigned size, int unsignedp)
6312 {
6313   if (size == INT_TYPE_SIZE)
6314     return unsignedp ? unsigned_type_node : integer_type_node;
6315   if (size == CHAR_TYPE_SIZE)
6316     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
6317   if (size == SHORT_TYPE_SIZE)
6318     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
6319   if (size == LONG_TYPE_SIZE)
6320     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
6321   if (size == LONG_LONG_TYPE_SIZE)
6322     return (unsignedp ? long_long_unsigned_type_node
6323             : long_long_integer_type_node);
6324
6325   if (unsignedp)
6326     return make_unsigned_type (size);
6327   else
6328     return make_signed_type (size);
6329 }
6330
6331 /* Create nodes for all integer types (and error_mark_node) using the sizes
6332    of C datatypes.  The caller should call set_sizetype soon after calling
6333    this function to select one of the types as sizetype.  */
6334
6335 void
6336 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
6337 {
6338   error_mark_node = make_node (ERROR_MARK);
6339   TREE_TYPE (error_mark_node) = error_mark_node;
6340
6341   initialize_sizetypes (signed_sizetype);
6342
6343   /* Define both `signed char' and `unsigned char'.  */
6344   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
6345   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
6346
6347   /* Define `char', which is like either `signed char' or `unsigned char'
6348      but not the same as either.  */
6349   char_type_node
6350     = (signed_char
6351        ? make_signed_type (CHAR_TYPE_SIZE)
6352        : make_unsigned_type (CHAR_TYPE_SIZE));
6353
6354   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
6355   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
6356   integer_type_node = make_signed_type (INT_TYPE_SIZE);
6357   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
6358   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
6359   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
6360   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
6361   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
6362
6363   /* Define a boolean type.  This type only represents boolean values but
6364      may be larger than char depending on the value of BOOL_TYPE_SIZE.
6365      Front ends which want to override this size (i.e. Java) can redefine
6366      boolean_type_node before calling build_common_tree_nodes_2.  */
6367   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
6368   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
6369   TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
6370   TYPE_PRECISION (boolean_type_node) = 1;
6371
6372   /* Fill in the rest of the sized types.  Reuse existing type nodes
6373      when possible.  */
6374   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
6375   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
6376   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
6377   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
6378   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
6379
6380   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
6381   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
6382   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
6383   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
6384   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
6385
6386   access_public_node = get_identifier ("public");
6387   access_protected_node = get_identifier ("protected");
6388   access_private_node = get_identifier ("private");
6389 }
6390
6391 /* Call this function after calling build_common_tree_nodes and set_sizetype.
6392    It will create several other common tree nodes.  */
6393
6394 void
6395 build_common_tree_nodes_2 (int short_double)
6396 {
6397   /* Define these next since types below may used them.  */
6398   integer_zero_node = build_int_cst (NULL_TREE, 0);
6399   integer_one_node = build_int_cst (NULL_TREE, 1);
6400   integer_minus_one_node = build_int_cst (NULL_TREE, -1);
6401
6402   size_zero_node = size_int (0);
6403   size_one_node = size_int (1);
6404   bitsize_zero_node = bitsize_int (0);
6405   bitsize_one_node = bitsize_int (1);
6406   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
6407
6408   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
6409   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
6410
6411   void_type_node = make_node (VOID_TYPE);
6412   layout_type (void_type_node);
6413
6414   /* We are not going to have real types in C with less than byte alignment,
6415      so we might as well not have any types that claim to have it.  */
6416   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
6417   TYPE_USER_ALIGN (void_type_node) = 0;
6418
6419   null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
6420   layout_type (TREE_TYPE (null_pointer_node));
6421
6422   ptr_type_node = build_pointer_type (void_type_node);
6423   const_ptr_type_node
6424     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
6425   fileptr_type_node = ptr_type_node;
6426
6427   float_type_node = make_node (REAL_TYPE);
6428   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
6429   layout_type (float_type_node);
6430
6431   double_type_node = make_node (REAL_TYPE);
6432   if (short_double)
6433     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
6434   else
6435     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
6436   layout_type (double_type_node);
6437
6438   long_double_type_node = make_node (REAL_TYPE);
6439   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
6440   layout_type (long_double_type_node);
6441
6442   float_ptr_type_node = build_pointer_type (float_type_node);
6443   double_ptr_type_node = build_pointer_type (double_type_node);
6444   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
6445   integer_ptr_type_node = build_pointer_type (integer_type_node);
6446
6447   /* Decimal float types. */
6448   dfloat32_type_node = make_node (REAL_TYPE);
6449   TYPE_PRECISION (dfloat32_type_node) = DECIMAL32_TYPE_SIZE;
6450   layout_type (dfloat32_type_node);
6451   TYPE_MODE (dfloat32_type_node) = SDmode;
6452   dfloat32_ptr_type_node = build_pointer_type (dfloat32_type_node);
6453
6454   dfloat64_type_node = make_node (REAL_TYPE);
6455   TYPE_PRECISION (dfloat64_type_node) = DECIMAL64_TYPE_SIZE;
6456   layout_type (dfloat64_type_node);
6457   TYPE_MODE (dfloat64_type_node) = DDmode;
6458   dfloat64_ptr_type_node = build_pointer_type (dfloat64_type_node);
6459
6460   dfloat128_type_node = make_node (REAL_TYPE);
6461   TYPE_PRECISION (dfloat128_type_node) = DECIMAL128_TYPE_SIZE;
6462   layout_type (dfloat128_type_node);
6463   TYPE_MODE (dfloat128_type_node) = TDmode;
6464   dfloat128_ptr_type_node = build_pointer_type (dfloat128_type_node);
6465
6466   complex_integer_type_node = make_node (COMPLEX_TYPE);
6467   TREE_TYPE (complex_integer_type_node) = integer_type_node;
6468   layout_type (complex_integer_type_node);
6469
6470   complex_float_type_node = make_node (COMPLEX_TYPE);
6471   TREE_TYPE (complex_float_type_node) = float_type_node;
6472   layout_type (complex_float_type_node);
6473
6474   complex_double_type_node = make_node (COMPLEX_TYPE);
6475   TREE_TYPE (complex_double_type_node) = double_type_node;
6476   layout_type (complex_double_type_node);
6477
6478   complex_long_double_type_node = make_node (COMPLEX_TYPE);
6479   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
6480   layout_type (complex_long_double_type_node);
6481
6482   {
6483     tree t = targetm.build_builtin_va_list ();
6484
6485     /* Many back-ends define record types without setting TYPE_NAME.
6486        If we copied the record type here, we'd keep the original
6487        record type without a name.  This breaks name mangling.  So,
6488        don't copy record types and let c_common_nodes_and_builtins()
6489        declare the type to be __builtin_va_list.  */
6490     if (TREE_CODE (t) != RECORD_TYPE)
6491       t = build_variant_type_copy (t);
6492
6493     va_list_type_node = t;
6494   }
6495 }
6496
6497 /* A subroutine of build_common_builtin_nodes.  Define a builtin function.  */
6498
6499 static void
6500 local_define_builtin (const char *name, tree type, enum built_in_function code,
6501                       const char *library_name, int ecf_flags)
6502 {
6503   tree decl;
6504
6505   decl = lang_hooks.builtin_function (name, type, code, BUILT_IN_NORMAL,
6506                                       library_name, NULL_TREE);
6507   if (ecf_flags & ECF_CONST)
6508     TREE_READONLY (decl) = 1;
6509   if (ecf_flags & ECF_PURE)
6510     DECL_IS_PURE (decl) = 1;
6511   if (ecf_flags & ECF_NORETURN)
6512     TREE_THIS_VOLATILE (decl) = 1;
6513   if (ecf_flags & ECF_NOTHROW)
6514     TREE_NOTHROW (decl) = 1;
6515   if (ecf_flags & ECF_MALLOC)
6516     DECL_IS_MALLOC (decl) = 1;
6517
6518   built_in_decls[code] = decl;
6519   implicit_built_in_decls[code] = decl;
6520 }
6521
6522 /* Call this function after instantiating all builtins that the language
6523    front end cares about.  This will build the rest of the builtins that
6524    are relied upon by the tree optimizers and the middle-end.  */
6525
6526 void
6527 build_common_builtin_nodes (void)
6528 {
6529   tree tmp, ftype;
6530
6531   if (built_in_decls[BUILT_IN_MEMCPY] == NULL
6532       || built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6533     {
6534       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6535       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6536       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6537       ftype = build_function_type (ptr_type_node, tmp);
6538
6539       if (built_in_decls[BUILT_IN_MEMCPY] == NULL)
6540         local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY,
6541                               "memcpy", ECF_NOTHROW);
6542       if (built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6543         local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE,
6544                               "memmove", ECF_NOTHROW);
6545     }
6546
6547   if (built_in_decls[BUILT_IN_MEMCMP] == NULL)
6548     {
6549       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6550       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6551       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6552       ftype = build_function_type (integer_type_node, tmp);
6553       local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP,
6554                             "memcmp", ECF_PURE | ECF_NOTHROW);
6555     }
6556
6557   if (built_in_decls[BUILT_IN_MEMSET] == NULL)
6558     {
6559       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6560       tmp = tree_cons (NULL_TREE, integer_type_node, tmp);
6561       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6562       ftype = build_function_type (ptr_type_node, tmp);
6563       local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET,
6564                             "memset", ECF_NOTHROW);
6565     }
6566
6567   if (built_in_decls[BUILT_IN_ALLOCA] == NULL)
6568     {
6569       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6570       ftype = build_function_type (ptr_type_node, tmp);
6571       local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA,
6572                             "alloca", ECF_NOTHROW | ECF_MALLOC);
6573     }
6574
6575   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6576   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6577   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6578   ftype = build_function_type (void_type_node, tmp);
6579   local_define_builtin ("__builtin_init_trampoline", ftype,
6580                         BUILT_IN_INIT_TRAMPOLINE,
6581                         "__builtin_init_trampoline", ECF_NOTHROW);
6582
6583   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6584   ftype = build_function_type (ptr_type_node, tmp);
6585   local_define_builtin ("__builtin_adjust_trampoline", ftype,
6586                         BUILT_IN_ADJUST_TRAMPOLINE,
6587                         "__builtin_adjust_trampoline",
6588                         ECF_CONST | ECF_NOTHROW);
6589
6590   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6591   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6592   ftype = build_function_type (void_type_node, tmp);
6593   local_define_builtin ("__builtin_nonlocal_goto", ftype,
6594                         BUILT_IN_NONLOCAL_GOTO,
6595                         "__builtin_nonlocal_goto",
6596                         ECF_NORETURN | ECF_NOTHROW);
6597
6598   ftype = build_function_type (ptr_type_node, void_list_node);
6599   local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE,
6600                         "__builtin_stack_save", ECF_NOTHROW);
6601
6602   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6603   ftype = build_function_type (void_type_node, tmp);
6604   local_define_builtin ("__builtin_stack_restore", ftype,
6605                         BUILT_IN_STACK_RESTORE,
6606                         "__builtin_stack_restore", ECF_NOTHROW);
6607
6608   ftype = build_function_type (void_type_node, void_list_node);
6609   local_define_builtin ("__builtin_profile_func_enter", ftype,
6610                         BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0);
6611   local_define_builtin ("__builtin_profile_func_exit", ftype,
6612                         BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0);
6613
6614   /* Complex multiplication and division.  These are handled as builtins
6615      rather than optabs because emit_library_call_value doesn't support
6616      complex.  Further, we can do slightly better with folding these
6617      beasties if the real and complex parts of the arguments are separate.  */
6618   {
6619     enum machine_mode mode;
6620
6621     for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode)
6622       {
6623         char mode_name_buf[4], *q;
6624         const char *p;
6625         enum built_in_function mcode, dcode;
6626         tree type, inner_type;
6627
6628         type = lang_hooks.types.type_for_mode (mode, 0);
6629         if (type == NULL)
6630           continue;
6631         inner_type = TREE_TYPE (type);
6632
6633         tmp = tree_cons (NULL_TREE, inner_type, void_list_node);
6634         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6635         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6636         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6637         ftype = build_function_type (type, tmp);
6638
6639         mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6640         dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6641
6642         for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++)
6643           *q = TOLOWER (*p);
6644         *q = '\0';
6645
6646         built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL);
6647         local_define_builtin (built_in_names[mcode], ftype, mcode,
6648                               built_in_names[mcode], ECF_CONST | ECF_NOTHROW);
6649
6650         built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL);
6651         local_define_builtin (built_in_names[dcode], ftype, dcode,
6652                               built_in_names[dcode], ECF_CONST | ECF_NOTHROW);
6653       }
6654   }
6655 }
6656
6657 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
6658    better way.
6659
6660    If we requested a pointer to a vector, build up the pointers that
6661    we stripped off while looking for the inner type.  Similarly for
6662    return values from functions.
6663
6664    The argument TYPE is the top of the chain, and BOTTOM is the
6665    new type which we will point to.  */
6666
6667 tree
6668 reconstruct_complex_type (tree type, tree bottom)
6669 {
6670   tree inner, outer;
6671
6672   if (POINTER_TYPE_P (type))
6673     {
6674       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6675       outer = build_pointer_type (inner);
6676     }
6677   else if (TREE_CODE (type) == ARRAY_TYPE)
6678     {
6679       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6680       outer = build_array_type (inner, TYPE_DOMAIN (type));
6681     }
6682   else if (TREE_CODE (type) == FUNCTION_TYPE)
6683     {
6684       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6685       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
6686     }
6687   else if (TREE_CODE (type) == METHOD_TYPE)
6688     {
6689       tree argtypes;
6690       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6691       /* The build_method_type_directly() routine prepends 'this' to argument list,
6692          so we must compensate by getting rid of it.  */
6693       argtypes = TYPE_ARG_TYPES (type);
6694       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
6695                                           inner,
6696                                           TYPE_ARG_TYPES (type));
6697       TYPE_ARG_TYPES (outer) = argtypes;
6698     }
6699   else
6700     return bottom;
6701
6702   TYPE_READONLY (outer) = TYPE_READONLY (type);
6703   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
6704
6705   return outer;
6706 }
6707
6708 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
6709    the inner type.  */
6710 tree
6711 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
6712 {
6713   int nunits;
6714
6715   switch (GET_MODE_CLASS (mode))
6716     {
6717     case MODE_VECTOR_INT:
6718     case MODE_VECTOR_FLOAT:
6719       nunits = GET_MODE_NUNITS (mode);
6720       break;
6721
6722     case MODE_INT:
6723       /* Check that there are no leftover bits.  */
6724       gcc_assert (GET_MODE_BITSIZE (mode)
6725                   % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
6726
6727       nunits = GET_MODE_BITSIZE (mode)
6728                / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
6729       break;
6730
6731     default:
6732       gcc_unreachable ();
6733     }
6734
6735   return make_vector_type (innertype, nunits, mode);
6736 }
6737
6738 /* Similarly, but takes the inner type and number of units, which must be
6739    a power of two.  */
6740
6741 tree
6742 build_vector_type (tree innertype, int nunits)
6743 {
6744   return make_vector_type (innertype, nunits, VOIDmode);
6745 }
6746
6747 /* Build RESX_EXPR with given REGION_NUMBER.  */
6748 tree
6749 build_resx (int region_number)
6750 {
6751   tree t;
6752   t = build1 (RESX_EXPR, void_type_node,
6753               build_int_cst (NULL_TREE, region_number));
6754   return t;
6755 }
6756
6757 /* Given an initializer INIT, return TRUE if INIT is zero or some
6758    aggregate of zeros.  Otherwise return FALSE.  */
6759 bool
6760 initializer_zerop (tree init)
6761 {
6762   tree elt;
6763
6764   STRIP_NOPS (init);
6765
6766   switch (TREE_CODE (init))
6767     {
6768     case INTEGER_CST:
6769       return integer_zerop (init);
6770
6771     case REAL_CST:
6772       /* ??? Note that this is not correct for C4X float formats.  There,
6773          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
6774          negative exponent.  */
6775       return real_zerop (init)
6776         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
6777
6778     case COMPLEX_CST:
6779       return integer_zerop (init)
6780         || (real_zerop (init)
6781             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
6782             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
6783
6784     case VECTOR_CST:
6785       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
6786         if (!initializer_zerop (TREE_VALUE (elt)))
6787           return false;
6788       return true;
6789
6790     case CONSTRUCTOR:
6791       {
6792         unsigned HOST_WIDE_INT idx;
6793
6794         FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
6795           if (!initializer_zerop (elt))
6796             return false;
6797         return true;
6798       }
6799
6800     default:
6801       return false;
6802     }
6803 }
6804
6805 void
6806 add_var_to_bind_expr (tree bind_expr, tree var)
6807 {
6808   BIND_EXPR_VARS (bind_expr)
6809     = chainon (BIND_EXPR_VARS (bind_expr), var);
6810   if (BIND_EXPR_BLOCK (bind_expr))
6811     BLOCK_VARS (BIND_EXPR_BLOCK (bind_expr))
6812       = BIND_EXPR_VARS (bind_expr);
6813 }
6814
6815 /* Build an empty statement.  */
6816
6817 tree
6818 build_empty_stmt (void)
6819 {
6820   return build1 (NOP_EXPR, void_type_node, size_zero_node);
6821 }
6822
6823
6824 /* Build an OpenMP clause with code CODE.  */
6825
6826 tree
6827 build_omp_clause (enum omp_clause_code code)
6828 {
6829   tree t;
6830   int size, length;
6831
6832   length = omp_clause_num_ops[code];
6833   size = (sizeof (struct tree_omp_clause) + (length - 1) * sizeof (tree));
6834
6835   t = ggc_alloc (size);
6836   memset (t, 0, size);
6837   TREE_SET_CODE (t, OMP_CLAUSE);
6838   OMP_CLAUSE_SET_CODE (t, code);
6839
6840 #ifdef GATHER_STATISTICS
6841   tree_node_counts[(int) omp_clause_kind]++;
6842   tree_node_sizes[(int) omp_clause_kind] += size;
6843 #endif
6844
6845   return t;
6846 }
6847
6848
6849 /* Returns true if it is possible to prove that the index of
6850    an array access REF (an ARRAY_REF expression) falls into the
6851    array bounds.  */
6852
6853 bool
6854 in_array_bounds_p (tree ref)
6855 {
6856   tree idx = TREE_OPERAND (ref, 1);
6857   tree min, max;
6858
6859   if (TREE_CODE (idx) != INTEGER_CST)
6860     return false;
6861
6862   min = array_ref_low_bound (ref);
6863   max = array_ref_up_bound (ref);
6864   if (!min
6865       || !max
6866       || TREE_CODE (min) != INTEGER_CST
6867       || TREE_CODE (max) != INTEGER_CST)
6868     return false;
6869
6870   if (tree_int_cst_lt (idx, min)
6871       || tree_int_cst_lt (max, idx))
6872     return false;
6873
6874   return true;
6875 }
6876
6877 /* Return true if T (assumed to be a DECL) is a global variable.  */
6878
6879 bool
6880 is_global_var (tree t)
6881 {
6882   if (MTAG_P (t))
6883     return (TREE_STATIC (t) || MTAG_GLOBAL (t));
6884   else
6885     return (TREE_STATIC (t) || DECL_EXTERNAL (t));
6886 }
6887
6888 /* Return true if T (assumed to be a DECL) must be assigned a memory
6889    location.  */
6890
6891 bool
6892 needs_to_live_in_memory (tree t)
6893 {
6894   return (TREE_ADDRESSABLE (t)
6895           || is_global_var (t)
6896           || (TREE_CODE (t) == RESULT_DECL
6897               && aggregate_value_p (t, current_function_decl)));
6898 }
6899
6900 /* There are situations in which a language considers record types
6901    compatible which have different field lists.  Decide if two fields
6902    are compatible.  It is assumed that the parent records are compatible.  */
6903
6904 bool
6905 fields_compatible_p (tree f1, tree f2)
6906 {
6907   if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
6908                         DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
6909     return false;
6910
6911   if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
6912                         DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
6913     return false;
6914
6915   if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
6916     return false;
6917
6918   return true;
6919 }
6920
6921 /* Locate within RECORD a field that is compatible with ORIG_FIELD.  */
6922
6923 tree
6924 find_compatible_field (tree record, tree orig_field)
6925 {
6926   tree f;
6927
6928   for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
6929     if (TREE_CODE (f) == FIELD_DECL
6930         && fields_compatible_p (f, orig_field))
6931       return f;
6932
6933   /* ??? Why isn't this on the main fields list?  */
6934   f = TYPE_VFIELD (record);
6935   if (f && TREE_CODE (f) == FIELD_DECL
6936       && fields_compatible_p (f, orig_field))
6937     return f;
6938
6939   /* ??? We should abort here, but Java appears to do Bad Things
6940      with inherited fields.  */
6941   return orig_field;
6942 }
6943
6944 /* Return value of a constant X.  */
6945
6946 HOST_WIDE_INT
6947 int_cst_value (tree x)
6948 {
6949   unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
6950   unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
6951   bool negative = ((val >> (bits - 1)) & 1) != 0;
6952
6953   gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
6954
6955   if (negative)
6956     val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
6957   else
6958     val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
6959
6960   return val;
6961 }
6962
6963 /* Returns the greatest common divisor of A and B, which must be
6964    INTEGER_CSTs.  */
6965
6966 tree
6967 tree_fold_gcd (tree a, tree b)
6968 {
6969   tree a_mod_b;
6970   tree type = TREE_TYPE (a);
6971
6972   gcc_assert (TREE_CODE (a) == INTEGER_CST);
6973   gcc_assert (TREE_CODE (b) == INTEGER_CST);
6974
6975   if (integer_zerop (a))
6976     return b;
6977
6978   if (integer_zerop (b))
6979     return a;
6980
6981   if (tree_int_cst_sgn (a) == -1)
6982     a = fold_build2 (MULT_EXPR, type, a,
6983                      build_int_cst (type, -1));
6984
6985   if (tree_int_cst_sgn (b) == -1)
6986     b = fold_build2 (MULT_EXPR, type, b,
6987                      build_int_cst (type, -1));
6988
6989   while (1)
6990     {
6991       a_mod_b = fold_build2 (FLOOR_MOD_EXPR, type, a, b);
6992
6993       if (!TREE_INT_CST_LOW (a_mod_b)
6994           && !TREE_INT_CST_HIGH (a_mod_b))
6995         return b;
6996
6997       a = b;
6998       b = a_mod_b;
6999     }
7000 }
7001
7002 /* Returns unsigned variant of TYPE.  */
7003
7004 tree
7005 unsigned_type_for (tree type)
7006 {
7007   if (POINTER_TYPE_P (type))
7008     return size_type_node;
7009   return lang_hooks.types.unsigned_type (type);
7010 }
7011
7012 /* Returns signed variant of TYPE.  */
7013
7014 tree
7015 signed_type_for (tree type)
7016 {
7017   return lang_hooks.types.signed_type (type);
7018 }
7019
7020 /* Returns the largest value obtainable by casting something in INNER type to
7021    OUTER type.  */
7022
7023 tree
7024 upper_bound_in_type (tree outer, tree inner)
7025 {
7026   unsigned HOST_WIDE_INT lo, hi;
7027   unsigned int det = 0;
7028   unsigned oprec = TYPE_PRECISION (outer);
7029   unsigned iprec = TYPE_PRECISION (inner);
7030   unsigned prec;
7031
7032   /* Compute a unique number for every combination.  */
7033   det |= (oprec > iprec) ? 4 : 0;
7034   det |= TYPE_UNSIGNED (outer) ? 2 : 0;
7035   det |= TYPE_UNSIGNED (inner) ? 1 : 0;
7036
7037   /* Determine the exponent to use.  */
7038   switch (det)
7039     {
7040     case 0:
7041     case 1:
7042       /* oprec <= iprec, outer: signed, inner: don't care.  */
7043       prec = oprec - 1;
7044       break;
7045     case 2:
7046     case 3:
7047       /* oprec <= iprec, outer: unsigned, inner: don't care.  */
7048       prec = oprec;
7049       break;
7050     case 4:
7051       /* oprec > iprec, outer: signed, inner: signed.  */
7052       prec = iprec - 1;
7053       break;
7054     case 5:
7055       /* oprec > iprec, outer: signed, inner: unsigned.  */
7056       prec = iprec;
7057       break;
7058     case 6:
7059       /* oprec > iprec, outer: unsigned, inner: signed.  */
7060       prec = oprec;
7061       break;
7062     case 7:
7063       /* oprec > iprec, outer: unsigned, inner: unsigned.  */
7064       prec = iprec;
7065       break;
7066     default:
7067       gcc_unreachable ();
7068     }
7069
7070   /* Compute 2^^prec - 1.  */
7071   if (prec <= HOST_BITS_PER_WIDE_INT)
7072     {
7073       hi = 0;
7074       lo = ((~(unsigned HOST_WIDE_INT) 0)
7075             >> (HOST_BITS_PER_WIDE_INT - prec));
7076     }
7077   else
7078     {
7079       hi = ((~(unsigned HOST_WIDE_INT) 0)
7080             >> (2 * HOST_BITS_PER_WIDE_INT - prec));
7081       lo = ~(unsigned HOST_WIDE_INT) 0;
7082     }
7083
7084   return build_int_cst_wide (outer, lo, hi);
7085 }
7086
7087 /* Returns the smallest value obtainable by casting something in INNER type to
7088    OUTER type.  */
7089
7090 tree
7091 lower_bound_in_type (tree outer, tree inner)
7092 {
7093   unsigned HOST_WIDE_INT lo, hi;
7094   unsigned oprec = TYPE_PRECISION (outer);
7095   unsigned iprec = TYPE_PRECISION (inner);
7096
7097   /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
7098      and obtain 0.  */
7099   if (TYPE_UNSIGNED (outer)
7100       /* If we are widening something of an unsigned type, OUTER type
7101          contains all values of INNER type.  In particular, both INNER
7102          and OUTER types have zero in common.  */
7103       || (oprec > iprec && TYPE_UNSIGNED (inner)))
7104     lo = hi = 0;
7105   else
7106     {
7107       /* If we are widening a signed type to another signed type, we
7108          want to obtain -2^^(iprec-1).  If we are keeping the
7109          precision or narrowing to a signed type, we want to obtain
7110          -2^(oprec-1).  */
7111       unsigned prec = oprec > iprec ? iprec : oprec;
7112
7113       if (prec <= HOST_BITS_PER_WIDE_INT)
7114         {
7115           hi = ~(unsigned HOST_WIDE_INT) 0;
7116           lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
7117         }
7118       else
7119         {
7120           hi = ((~(unsigned HOST_WIDE_INT) 0)
7121                 << (prec - HOST_BITS_PER_WIDE_INT - 1));
7122           lo = 0;
7123         }
7124     }
7125
7126   return build_int_cst_wide (outer, lo, hi);
7127 }
7128
7129 /* Return nonzero if two operands that are suitable for PHI nodes are
7130    necessarily equal.  Specifically, both ARG0 and ARG1 must be either
7131    SSA_NAME or invariant.  Note that this is strictly an optimization.
7132    That is, callers of this function can directly call operand_equal_p
7133    and get the same result, only slower.  */
7134
7135 int
7136 operand_equal_for_phi_arg_p (tree arg0, tree arg1)
7137 {
7138   if (arg0 == arg1)
7139     return 1;
7140   if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME)
7141     return 0;
7142   return operand_equal_p (arg0, arg1, 0);
7143 }
7144
7145 /* Returns number of zeros at the end of binary representation of X.
7146
7147    ??? Use ffs if available?  */
7148
7149 tree
7150 num_ending_zeros (tree x)
7151 {
7152   unsigned HOST_WIDE_INT fr, nfr;
7153   unsigned num, abits;
7154   tree type = TREE_TYPE (x);
7155
7156   if (TREE_INT_CST_LOW (x) == 0)
7157     {
7158       num = HOST_BITS_PER_WIDE_INT;
7159       fr = TREE_INT_CST_HIGH (x);
7160     }
7161   else
7162     {
7163       num = 0;
7164       fr = TREE_INT_CST_LOW (x);
7165     }
7166
7167   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
7168     {
7169       nfr = fr >> abits;
7170       if (nfr << abits == fr)
7171         {
7172           num += abits;
7173           fr = nfr;
7174         }
7175     }
7176
7177   if (num > TYPE_PRECISION (type))
7178     num = TYPE_PRECISION (type);
7179
7180   return build_int_cst_type (type, num);
7181 }
7182
7183
7184 #define WALK_SUBTREE(NODE)                              \
7185   do                                                    \
7186     {                                                   \
7187       result = walk_tree (&(NODE), func, data, pset);   \
7188       if (result)                                       \
7189         return result;                                  \
7190     }                                                   \
7191   while (0)
7192
7193 /* This is a subroutine of walk_tree that walks field of TYPE that are to
7194    be walked whenever a type is seen in the tree.  Rest of operands and return
7195    value are as for walk_tree.  */
7196
7197 static tree
7198 walk_type_fields (tree type, walk_tree_fn func, void *data,
7199                   struct pointer_set_t *pset)
7200 {
7201   tree result = NULL_TREE;
7202
7203   switch (TREE_CODE (type))
7204     {
7205     case POINTER_TYPE:
7206     case REFERENCE_TYPE:
7207       /* We have to worry about mutually recursive pointers.  These can't
7208          be written in C.  They can in Ada.  It's pathological, but
7209          there's an ACATS test (c38102a) that checks it.  Deal with this
7210          by checking if we're pointing to another pointer, that one
7211          points to another pointer, that one does too, and we have no htab.
7212          If so, get a hash table.  We check three levels deep to avoid
7213          the cost of the hash table if we don't need one.  */
7214       if (POINTER_TYPE_P (TREE_TYPE (type))
7215           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
7216           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
7217           && !pset)
7218         {
7219           result = walk_tree_without_duplicates (&TREE_TYPE (type),
7220                                                  func, data);
7221           if (result)
7222             return result;
7223
7224           break;
7225         }
7226
7227       /* ... fall through ... */
7228
7229     case COMPLEX_TYPE:
7230       WALK_SUBTREE (TREE_TYPE (type));
7231       break;
7232
7233     case METHOD_TYPE:
7234       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
7235
7236       /* Fall through.  */
7237
7238     case FUNCTION_TYPE:
7239       WALK_SUBTREE (TREE_TYPE (type));
7240       {
7241         tree arg;
7242
7243         /* We never want to walk into default arguments.  */
7244         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
7245           WALK_SUBTREE (TREE_VALUE (arg));
7246       }
7247       break;
7248
7249     case ARRAY_TYPE:
7250       /* Don't follow this nodes's type if a pointer for fear that we'll
7251          have infinite recursion.  Those types are uninteresting anyway.  */
7252       if (!POINTER_TYPE_P (TREE_TYPE (type))
7253           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
7254         WALK_SUBTREE (TREE_TYPE (type));
7255       WALK_SUBTREE (TYPE_DOMAIN (type));
7256       break;
7257
7258     case BOOLEAN_TYPE:
7259     case ENUMERAL_TYPE:
7260     case INTEGER_TYPE:
7261     case CHAR_TYPE:
7262     case REAL_TYPE:
7263       WALK_SUBTREE (TYPE_MIN_VALUE (type));
7264       WALK_SUBTREE (TYPE_MAX_VALUE (type));
7265       break;
7266
7267     case OFFSET_TYPE:
7268       WALK_SUBTREE (TREE_TYPE (type));
7269       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
7270       break;
7271
7272     default:
7273       break;
7274     }
7275
7276   return NULL_TREE;
7277 }
7278
7279 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
7280    called with the DATA and the address of each sub-tree.  If FUNC returns a
7281    non-NULL value, the traversal is stopped, and the value returned by FUNC
7282    is returned.  If PSET is non-NULL it is used to record the nodes visited,
7283    and to avoid visiting a node more than once.  */
7284
7285 tree
7286 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
7287 {
7288   enum tree_code code;
7289   int walk_subtrees;
7290   tree result;
7291
7292 #define WALK_SUBTREE_TAIL(NODE)                         \
7293   do                                                    \
7294     {                                                   \
7295        tp = & (NODE);                                   \
7296        goto tail_recurse;                               \
7297     }                                                   \
7298   while (0)
7299
7300  tail_recurse:
7301   /* Skip empty subtrees.  */
7302   if (!*tp)
7303     return NULL_TREE;
7304
7305   /* Don't walk the same tree twice, if the user has requested
7306      that we avoid doing so.  */
7307   if (pset && pointer_set_insert (pset, *tp))
7308     return NULL_TREE;
7309
7310   /* Call the function.  */
7311   walk_subtrees = 1;
7312   result = (*func) (tp, &walk_subtrees, data);
7313
7314   /* If we found something, return it.  */
7315   if (result)
7316     return result;
7317
7318   code = TREE_CODE (*tp);
7319
7320   /* Even if we didn't, FUNC may have decided that there was nothing
7321      interesting below this point in the tree.  */
7322   if (!walk_subtrees)
7323     {
7324       /* But we still need to check our siblings.  */
7325       if (code == TREE_LIST)
7326         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7327       else if (code == OMP_CLAUSE)
7328         WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7329       else
7330         return NULL_TREE;
7331     }
7332
7333   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
7334                                                    data, pset);
7335   if (result || ! walk_subtrees)
7336     return result;
7337
7338   switch (code)
7339     {
7340     case ERROR_MARK:
7341     case IDENTIFIER_NODE:
7342     case INTEGER_CST:
7343     case REAL_CST:
7344     case VECTOR_CST:
7345     case STRING_CST:
7346     case BLOCK:
7347     case PLACEHOLDER_EXPR:
7348     case SSA_NAME:
7349     case FIELD_DECL:
7350     case RESULT_DECL:
7351       /* None of these have subtrees other than those already walked
7352          above.  */
7353       break;
7354
7355     case TREE_LIST:
7356       WALK_SUBTREE (TREE_VALUE (*tp));
7357       WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7358       break;
7359
7360     case TREE_VEC:
7361       {
7362         int len = TREE_VEC_LENGTH (*tp);
7363
7364         if (len == 0)
7365           break;
7366
7367         /* Walk all elements but the first.  */
7368         while (--len)
7369           WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
7370
7371         /* Now walk the first one as a tail call.  */
7372         WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
7373       }
7374
7375     case COMPLEX_CST:
7376       WALK_SUBTREE (TREE_REALPART (*tp));
7377       WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
7378
7379     case CONSTRUCTOR:
7380       {
7381         unsigned HOST_WIDE_INT idx;
7382         constructor_elt *ce;
7383
7384         for (idx = 0;
7385              VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (*tp), idx, ce);
7386              idx++)
7387           WALK_SUBTREE (ce->value);
7388       }
7389       break;
7390
7391     case SAVE_EXPR:
7392       WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
7393
7394     case BIND_EXPR:
7395       {
7396         tree decl;
7397         for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
7398           {
7399             /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
7400                into declarations that are just mentioned, rather than
7401                declared; they don't really belong to this part of the tree.
7402                And, we can see cycles: the initializer for a declaration
7403                can refer to the declaration itself.  */
7404             WALK_SUBTREE (DECL_INITIAL (decl));
7405             WALK_SUBTREE (DECL_SIZE (decl));
7406             WALK_SUBTREE (DECL_SIZE_UNIT (decl));
7407           }
7408         WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
7409       }
7410
7411     case STATEMENT_LIST:
7412       {
7413         tree_stmt_iterator i;
7414         for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
7415           WALK_SUBTREE (*tsi_stmt_ptr (i));
7416       }
7417       break;
7418
7419     case OMP_CLAUSE:
7420       switch (OMP_CLAUSE_CODE (*tp))
7421         {
7422         case OMP_CLAUSE_PRIVATE:
7423         case OMP_CLAUSE_SHARED:
7424         case OMP_CLAUSE_FIRSTPRIVATE:
7425         case OMP_CLAUSE_LASTPRIVATE:
7426         case OMP_CLAUSE_COPYIN:
7427         case OMP_CLAUSE_COPYPRIVATE:
7428         case OMP_CLAUSE_IF:
7429         case OMP_CLAUSE_NUM_THREADS:
7430         case OMP_CLAUSE_SCHEDULE:
7431           WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, 0));
7432           /* FALLTHRU */
7433
7434         case OMP_CLAUSE_NOWAIT:
7435         case OMP_CLAUSE_ORDERED:
7436         case OMP_CLAUSE_DEFAULT:
7437           WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7438
7439         case OMP_CLAUSE_REDUCTION:
7440           {
7441             int i;
7442             for (i = 0; i < 4; i++)
7443               WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, i));
7444             WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7445           }
7446
7447         default:
7448           gcc_unreachable ();
7449         }
7450       break;
7451
7452     case TARGET_EXPR:
7453       {
7454         int i, len;
7455
7456         /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
7457            But, we only want to walk once.  */
7458         len = (TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1)) ? 2 : 3;
7459         for (i = 0; i < len; ++i)
7460           WALK_SUBTREE (TREE_OPERAND (*tp, i));
7461         WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len));
7462       }
7463
7464     case DECL_EXPR:
7465       /* Walk into various fields of the type that it's defining.  We only
7466          want to walk into these fields of a type in this case.  Note that
7467          decls get walked as part of the processing of a BIND_EXPR.
7468
7469          ??? Precisely which fields of types that we are supposed to walk in
7470          this case vs. the normal case aren't well defined.  */
7471       if (TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
7472           && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
7473         {
7474           tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
7475
7476           /* Call the function for the type.  See if it returns anything or
7477              doesn't want us to continue.  If we are to continue, walk both
7478              the normal fields and those for the declaration case.  */
7479           result = (*func) (type_p, &walk_subtrees, data);
7480           if (result || !walk_subtrees)
7481             return NULL_TREE;
7482
7483           result = walk_type_fields (*type_p, func, data, pset);
7484           if (result)
7485             return result;
7486
7487           /* If this is a record type, also walk the fields.  */
7488           if (TREE_CODE (*type_p) == RECORD_TYPE
7489               || TREE_CODE (*type_p) == UNION_TYPE
7490               || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7491             {
7492               tree field;
7493
7494               for (field = TYPE_FIELDS (*type_p); field;
7495                    field = TREE_CHAIN (field))
7496                 {
7497                   /* We'd like to look at the type of the field, but we can
7498                      easily get infinite recursion.  So assume it's pointed
7499                      to elsewhere in the tree.  Also, ignore things that
7500                      aren't fields.  */
7501                   if (TREE_CODE (field) != FIELD_DECL)
7502                     continue;
7503
7504                   WALK_SUBTREE (DECL_FIELD_OFFSET (field));
7505                   WALK_SUBTREE (DECL_SIZE (field));
7506                   WALK_SUBTREE (DECL_SIZE_UNIT (field));
7507                   if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7508                     WALK_SUBTREE (DECL_QUALIFIER (field));
7509                 }
7510             }
7511
7512           WALK_SUBTREE (TYPE_SIZE (*type_p));
7513           WALK_SUBTREE_TAIL (TYPE_SIZE_UNIT (*type_p));
7514         }
7515       /* FALLTHRU */
7516
7517     default:
7518       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
7519         {
7520           int i, len;
7521
7522           /* Walk over all the sub-trees of this operand.  */
7523           len = TREE_CODE_LENGTH (code);
7524
7525           /* Go through the subtrees.  We need to do this in forward order so
7526              that the scope of a FOR_EXPR is handled properly.  */
7527           if (len)
7528             {
7529               for (i = 0; i < len - 1; ++i)
7530                 WALK_SUBTREE (TREE_OPERAND (*tp, i));
7531               WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
7532             }
7533         }
7534
7535       /* If this is a type, walk the needed fields in the type.  */
7536       else if (TYPE_P (*tp))
7537         return walk_type_fields (*tp, func, data, pset);
7538       break;
7539     }
7540
7541   /* We didn't find what we were looking for.  */
7542   return NULL_TREE;
7543
7544 #undef WALK_SUBTREE_TAIL
7545 }
7546 #undef WALK_SUBTREE
7547
7548 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
7549
7550 tree
7551 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
7552 {
7553   tree result;
7554   struct pointer_set_t *pset;
7555
7556   pset = pointer_set_create ();
7557   result = walk_tree (tp, func, data, pset);
7558   pointer_set_destroy (pset);
7559   return result;
7560 }
7561
7562
7563 /* Return true if STMT is an empty statement or contains nothing but
7564    empty statements.  */
7565
7566 bool
7567 empty_body_p (tree stmt)
7568 {
7569   tree_stmt_iterator i;
7570   tree body;
7571
7572   if (IS_EMPTY_STMT (stmt))
7573     return true;
7574   else if (TREE_CODE (stmt) == BIND_EXPR)
7575     body = BIND_EXPR_BODY (stmt);
7576   else if (TREE_CODE (stmt) == STATEMENT_LIST)
7577     body = stmt;
7578   else
7579     return false;
7580
7581   for (i = tsi_start (body); !tsi_end_p (i); tsi_next (&i))
7582     if (!empty_body_p (tsi_stmt (i)))
7583       return false;
7584
7585   return true;
7586 }
7587
7588 #include "gt-tree.h"