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       /* If it's a pointer type, the new variant points to the same type.  */
3743       if (TREE_CODE (type) == POINTER_TYPE)
3744         {
3745           TYPE_NEXT_PTR_TO (t) = TYPE_NEXT_PTR_TO (type);
3746           TYPE_NEXT_PTR_TO (type) = t;
3747         }
3748
3749       /* Same for a reference type.  */
3750       else if (TREE_CODE (type) == REFERENCE_TYPE)
3751         {
3752           TYPE_NEXT_REF_TO (t) = TYPE_NEXT_REF_TO (type);
3753           TYPE_NEXT_REF_TO (type) = t;
3754         }
3755     }
3756
3757   return t;
3758 }
3759
3760 /* Create a new distinct copy of TYPE.  The new type is made its own
3761    MAIN_VARIANT.  */
3762
3763 tree
3764 build_distinct_type_copy (tree type)
3765 {
3766   tree t = copy_node (type);
3767
3768   TYPE_POINTER_TO (t) = 0;
3769   TYPE_REFERENCE_TO (t) = 0;
3770
3771   /* Make it its own variant.  */
3772   TYPE_MAIN_VARIANT (t) = t;
3773   TYPE_NEXT_VARIANT (t) = 0;
3774
3775   return t;
3776 }
3777
3778 /* Create a new variant of TYPE, equivalent but distinct.
3779    This is so the caller can modify it.  */
3780
3781 tree
3782 build_variant_type_copy (tree type)
3783 {
3784   tree t, m = TYPE_MAIN_VARIANT (type);
3785
3786   t = build_distinct_type_copy (type);
3787
3788   /* Add the new type to the chain of variants of TYPE.  */
3789   TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
3790   TYPE_NEXT_VARIANT (m) = t;
3791   TYPE_MAIN_VARIANT (t) = m;
3792
3793   return t;
3794 }
3795 \f
3796 /* Return true if the from tree in both tree maps are equal.  */
3797
3798 int
3799 tree_map_eq (const void *va, const void *vb)
3800 {
3801   const struct tree_map  *a = va, *b = vb;
3802   return (a->from == b->from);
3803 }
3804
3805 /* Hash a from tree in a tree_map.  */
3806
3807 unsigned int
3808 tree_map_hash (const void *item)
3809 {
3810   return (((const struct tree_map *) item)->hash);
3811 }
3812
3813 /* Return true if this tree map structure is marked for garbage collection
3814    purposes.  We simply return true if the from tree is marked, so that this
3815    structure goes away when the from tree goes away.  */
3816
3817 int
3818 tree_map_marked_p (const void *p)
3819 {
3820   tree from = ((struct tree_map *) p)->from;
3821
3822   return ggc_marked_p (from);
3823 }
3824
3825 /* Return true if the trees in the tree_int_map *'s VA and VB are equal.  */
3826
3827 static int
3828 tree_int_map_eq (const void *va, const void *vb)
3829 {
3830   const struct tree_int_map  *a = va, *b = vb;
3831   return (a->from == b->from);
3832 }
3833
3834 /* Hash a from tree in the tree_int_map * ITEM.  */
3835
3836 static unsigned int
3837 tree_int_map_hash (const void *item)
3838 {
3839   return htab_hash_pointer (((const struct tree_int_map *)item)->from);
3840 }
3841
3842 /* Return true if this tree int map structure is marked for garbage collection
3843    purposes.  We simply return true if the from tree_int_map *P's from tree is marked, so that this
3844    structure goes away when the from tree goes away.  */
3845
3846 static int
3847 tree_int_map_marked_p (const void *p)
3848 {
3849   tree from = ((struct tree_int_map *) p)->from;
3850
3851   return ggc_marked_p (from);
3852 }
3853 /* Lookup an init priority for FROM, and return it if we find one.  */
3854
3855 unsigned short
3856 decl_init_priority_lookup (tree from)
3857 {
3858   struct tree_int_map *h, in;
3859   in.from = from;
3860
3861   h = htab_find_with_hash (init_priority_for_decl,
3862                            &in, htab_hash_pointer (from));
3863   if (h)
3864     return h->to;
3865   return 0;
3866 }
3867
3868 /* Insert a mapping FROM->TO in the init priority hashtable.  */
3869
3870 void
3871 decl_init_priority_insert (tree from, unsigned short to)
3872 {
3873   struct tree_int_map *h;
3874   void **loc;
3875
3876   h = ggc_alloc (sizeof (struct tree_int_map));
3877   h->from = from;
3878   h->to = to;
3879   loc = htab_find_slot_with_hash (init_priority_for_decl, h,
3880                                   htab_hash_pointer (from), INSERT);
3881   *(struct tree_int_map **) loc = h;
3882 }
3883
3884 /* Look up a restrict qualified base decl for FROM.  */
3885
3886 tree
3887 decl_restrict_base_lookup (tree from)
3888 {
3889   struct tree_map *h;
3890   struct tree_map in;
3891
3892   in.from = from;
3893   h = htab_find_with_hash (restrict_base_for_decl, &in,
3894                            htab_hash_pointer (from));
3895   return h ? h->to : NULL_TREE;
3896 }
3897
3898 /* Record the restrict qualified base TO for FROM.  */
3899
3900 void
3901 decl_restrict_base_insert (tree from, tree to)
3902 {
3903   struct tree_map *h;
3904   void **loc;
3905
3906   h = ggc_alloc (sizeof (struct tree_map));
3907   h->hash = htab_hash_pointer (from);
3908   h->from = from;
3909   h->to = to;
3910   loc = htab_find_slot_with_hash (restrict_base_for_decl, h, h->hash, INSERT);
3911   *(struct tree_map **) loc = h;
3912 }
3913
3914 /* Print out the statistics for the DECL_DEBUG_EXPR hash table.  */
3915
3916 static void
3917 print_debug_expr_statistics (void)
3918 {
3919   fprintf (stderr, "DECL_DEBUG_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3920            (long) htab_size (debug_expr_for_decl),
3921            (long) htab_elements (debug_expr_for_decl),
3922            htab_collisions (debug_expr_for_decl));
3923 }
3924
3925 /* Print out the statistics for the DECL_VALUE_EXPR hash table.  */
3926
3927 static void
3928 print_value_expr_statistics (void)
3929 {
3930   fprintf (stderr, "DECL_VALUE_EXPR  hash: size %ld, %ld elements, %f collisions\n",
3931            (long) htab_size (value_expr_for_decl),
3932            (long) htab_elements (value_expr_for_decl),
3933            htab_collisions (value_expr_for_decl));
3934 }
3935
3936 /* Print out statistics for the RESTRICT_BASE_FOR_DECL hash table, but
3937    don't print anything if the table is empty.  */
3938
3939 static void
3940 print_restrict_base_statistics (void)
3941 {
3942   if (htab_elements (restrict_base_for_decl) != 0)
3943     fprintf (stderr,
3944              "RESTRICT_BASE    hash: size %ld, %ld elements, %f collisions\n",
3945              (long) htab_size (restrict_base_for_decl),
3946              (long) htab_elements (restrict_base_for_decl),
3947              htab_collisions (restrict_base_for_decl));
3948 }
3949
3950 /* Lookup a debug expression for FROM, and return it if we find one.  */
3951
3952 tree
3953 decl_debug_expr_lookup (tree from)
3954 {
3955   struct tree_map *h, in;
3956   in.from = from;
3957
3958   h = htab_find_with_hash (debug_expr_for_decl, &in, htab_hash_pointer (from));
3959   if (h)
3960     return h->to;
3961   return NULL_TREE;
3962 }
3963
3964 /* Insert a mapping FROM->TO in the debug expression hashtable.  */
3965
3966 void
3967 decl_debug_expr_insert (tree from, tree to)
3968 {
3969   struct tree_map *h;
3970   void **loc;
3971
3972   h = ggc_alloc (sizeof (struct tree_map));
3973   h->hash = htab_hash_pointer (from);
3974   h->from = from;
3975   h->to = to;
3976   loc = htab_find_slot_with_hash (debug_expr_for_decl, h, h->hash, INSERT);
3977   *(struct tree_map **) loc = h;
3978 }
3979
3980 /* Lookup a value expression for FROM, and return it if we find one.  */
3981
3982 tree
3983 decl_value_expr_lookup (tree from)
3984 {
3985   struct tree_map *h, in;
3986   in.from = from;
3987
3988   h = htab_find_with_hash (value_expr_for_decl, &in, htab_hash_pointer (from));
3989   if (h)
3990     return h->to;
3991   return NULL_TREE;
3992 }
3993
3994 /* Insert a mapping FROM->TO in the value expression hashtable.  */
3995
3996 void
3997 decl_value_expr_insert (tree from, tree to)
3998 {
3999   struct tree_map *h;
4000   void **loc;
4001
4002   h = ggc_alloc (sizeof (struct tree_map));
4003   h->hash = htab_hash_pointer (from);
4004   h->from = from;
4005   h->to = to;
4006   loc = htab_find_slot_with_hash (value_expr_for_decl, h, h->hash, INSERT);
4007   *(struct tree_map **) loc = h;
4008 }
4009
4010 /* Hashing of types so that we don't make duplicates.
4011    The entry point is `type_hash_canon'.  */
4012
4013 /* Compute a hash code for a list of types (chain of TREE_LIST nodes
4014    with types in the TREE_VALUE slots), by adding the hash codes
4015    of the individual types.  */
4016
4017 unsigned int
4018 type_hash_list (tree list, hashval_t hashcode)
4019 {
4020   tree tail;
4021
4022   for (tail = list; tail; tail = TREE_CHAIN (tail))
4023     if (TREE_VALUE (tail) != error_mark_node)
4024       hashcode = iterative_hash_object (TYPE_HASH (TREE_VALUE (tail)),
4025                                         hashcode);
4026
4027   return hashcode;
4028 }
4029
4030 /* These are the Hashtable callback functions.  */
4031
4032 /* Returns true iff the types are equivalent.  */
4033
4034 static int
4035 type_hash_eq (const void *va, const void *vb)
4036 {
4037   const struct type_hash *a = va, *b = vb;
4038
4039   /* First test the things that are the same for all types.  */
4040   if (a->hash != b->hash
4041       || TREE_CODE (a->type) != TREE_CODE (b->type)
4042       || TREE_TYPE (a->type) != TREE_TYPE (b->type)
4043       || !attribute_list_equal (TYPE_ATTRIBUTES (a->type),
4044                                  TYPE_ATTRIBUTES (b->type))
4045       || TYPE_ALIGN (a->type) != TYPE_ALIGN (b->type)
4046       || TYPE_MODE (a->type) != TYPE_MODE (b->type))
4047     return 0;
4048
4049   switch (TREE_CODE (a->type))
4050     {
4051     case VOID_TYPE:
4052     case COMPLEX_TYPE:
4053     case POINTER_TYPE:
4054     case REFERENCE_TYPE:
4055       return 1;
4056
4057     case VECTOR_TYPE:
4058       return TYPE_VECTOR_SUBPARTS (a->type) == TYPE_VECTOR_SUBPARTS (b->type);
4059
4060     case ENUMERAL_TYPE:
4061       if (TYPE_VALUES (a->type) != TYPE_VALUES (b->type)
4062           && !(TYPE_VALUES (a->type)
4063                && TREE_CODE (TYPE_VALUES (a->type)) == TREE_LIST
4064                && TYPE_VALUES (b->type)
4065                && TREE_CODE (TYPE_VALUES (b->type)) == TREE_LIST
4066                && type_list_equal (TYPE_VALUES (a->type),
4067                                    TYPE_VALUES (b->type))))
4068         return 0;
4069
4070       /* ... fall through ... */
4071
4072     case INTEGER_TYPE:
4073     case REAL_TYPE:
4074     case BOOLEAN_TYPE:
4075     case CHAR_TYPE:
4076       return ((TYPE_MAX_VALUE (a->type) == TYPE_MAX_VALUE (b->type)
4077                || tree_int_cst_equal (TYPE_MAX_VALUE (a->type),
4078                                       TYPE_MAX_VALUE (b->type)))
4079               && (TYPE_MIN_VALUE (a->type) == TYPE_MIN_VALUE (b->type)
4080                   || tree_int_cst_equal (TYPE_MIN_VALUE (a->type),
4081                                          TYPE_MIN_VALUE (b->type))));
4082
4083     case OFFSET_TYPE:
4084       return TYPE_OFFSET_BASETYPE (a->type) == TYPE_OFFSET_BASETYPE (b->type);
4085
4086     case METHOD_TYPE:
4087       return (TYPE_METHOD_BASETYPE (a->type) == TYPE_METHOD_BASETYPE (b->type)
4088               && (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4089                   || (TYPE_ARG_TYPES (a->type)
4090                       && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4091                       && TYPE_ARG_TYPES (b->type)
4092                       && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4093                       && type_list_equal (TYPE_ARG_TYPES (a->type),
4094                                           TYPE_ARG_TYPES (b->type)))));
4095
4096     case ARRAY_TYPE:
4097       return TYPE_DOMAIN (a->type) == TYPE_DOMAIN (b->type);
4098
4099     case RECORD_TYPE:
4100     case UNION_TYPE:
4101     case QUAL_UNION_TYPE:
4102       return (TYPE_FIELDS (a->type) == TYPE_FIELDS (b->type)
4103               || (TYPE_FIELDS (a->type)
4104                   && TREE_CODE (TYPE_FIELDS (a->type)) == TREE_LIST
4105                   && TYPE_FIELDS (b->type)
4106                   && TREE_CODE (TYPE_FIELDS (b->type)) == TREE_LIST
4107                   && type_list_equal (TYPE_FIELDS (a->type),
4108                                       TYPE_FIELDS (b->type))));
4109
4110     case FUNCTION_TYPE:
4111       return (TYPE_ARG_TYPES (a->type) == TYPE_ARG_TYPES (b->type)
4112               || (TYPE_ARG_TYPES (a->type)
4113                   && TREE_CODE (TYPE_ARG_TYPES (a->type)) == TREE_LIST
4114                   && TYPE_ARG_TYPES (b->type)
4115                   && TREE_CODE (TYPE_ARG_TYPES (b->type)) == TREE_LIST
4116                   && type_list_equal (TYPE_ARG_TYPES (a->type),
4117                                       TYPE_ARG_TYPES (b->type))));
4118
4119     default:
4120       return 0;
4121     }
4122 }
4123
4124 /* Return the cached hash value.  */
4125
4126 static hashval_t
4127 type_hash_hash (const void *item)
4128 {
4129   return ((const struct type_hash *) item)->hash;
4130 }
4131
4132 /* Look in the type hash table for a type isomorphic to TYPE.
4133    If one is found, return it.  Otherwise return 0.  */
4134
4135 tree
4136 type_hash_lookup (hashval_t hashcode, tree type)
4137 {
4138   struct type_hash *h, in;
4139
4140   /* The TYPE_ALIGN field of a type is set by layout_type(), so we
4141      must call that routine before comparing TYPE_ALIGNs.  */
4142   layout_type (type);
4143
4144   in.hash = hashcode;
4145   in.type = type;
4146
4147   h = htab_find_with_hash (type_hash_table, &in, hashcode);
4148   if (h)
4149     return h->type;
4150   return NULL_TREE;
4151 }
4152
4153 /* Add an entry to the type-hash-table
4154    for a type TYPE whose hash code is HASHCODE.  */
4155
4156 void
4157 type_hash_add (hashval_t hashcode, tree type)
4158 {
4159   struct type_hash *h;
4160   void **loc;
4161
4162   h = ggc_alloc (sizeof (struct type_hash));
4163   h->hash = hashcode;
4164   h->type = type;
4165   loc = htab_find_slot_with_hash (type_hash_table, h, hashcode, INSERT);
4166   *(struct type_hash **) loc = h;
4167 }
4168
4169 /* Given TYPE, and HASHCODE its hash code, return the canonical
4170    object for an identical type if one already exists.
4171    Otherwise, return TYPE, and record it as the canonical object.
4172
4173    To use this function, first create a type of the sort you want.
4174    Then compute its hash code from the fields of the type that
4175    make it different from other similar types.
4176    Then call this function and use the value.  */
4177
4178 tree
4179 type_hash_canon (unsigned int hashcode, tree type)
4180 {
4181   tree t1;
4182
4183   /* The hash table only contains main variants, so ensure that's what we're
4184      being passed.  */
4185   gcc_assert (TYPE_MAIN_VARIANT (type) == type);
4186
4187   if (!lang_hooks.types.hash_types)
4188     return type;
4189
4190   /* See if the type is in the hash table already.  If so, return it.
4191      Otherwise, add the type.  */
4192   t1 = type_hash_lookup (hashcode, type);
4193   if (t1 != 0)
4194     {
4195 #ifdef GATHER_STATISTICS
4196       tree_node_counts[(int) t_kind]--;
4197       tree_node_sizes[(int) t_kind] -= sizeof (struct tree_type);
4198 #endif
4199       return t1;
4200     }
4201   else
4202     {
4203       type_hash_add (hashcode, type);
4204       return type;
4205     }
4206 }
4207
4208 /* See if the data pointed to by the type hash table is marked.  We consider
4209    it marked if the type is marked or if a debug type number or symbol
4210    table entry has been made for the type.  This reduces the amount of
4211    debugging output and eliminates that dependency of the debug output on
4212    the number of garbage collections.  */
4213
4214 static int
4215 type_hash_marked_p (const void *p)
4216 {
4217   tree type = ((struct type_hash *) p)->type;
4218
4219   return ggc_marked_p (type) || TYPE_SYMTAB_POINTER (type);
4220 }
4221
4222 static void
4223 print_type_hash_statistics (void)
4224 {
4225   fprintf (stderr, "Type hash: size %ld, %ld elements, %f collisions\n",
4226            (long) htab_size (type_hash_table),
4227            (long) htab_elements (type_hash_table),
4228            htab_collisions (type_hash_table));
4229 }
4230
4231 /* Compute a hash code for a list of attributes (chain of TREE_LIST nodes
4232    with names in the TREE_PURPOSE slots and args in the TREE_VALUE slots),
4233    by adding the hash codes of the individual attributes.  */
4234
4235 unsigned int
4236 attribute_hash_list (tree list, hashval_t hashcode)
4237 {
4238   tree tail;
4239
4240   for (tail = list; tail; tail = TREE_CHAIN (tail))
4241     /* ??? Do we want to add in TREE_VALUE too? */
4242     hashcode = iterative_hash_object
4243       (IDENTIFIER_HASH_VALUE (TREE_PURPOSE (tail)), hashcode);
4244   return hashcode;
4245 }
4246
4247 /* Given two lists of attributes, return true if list l2 is
4248    equivalent to l1.  */
4249
4250 int
4251 attribute_list_equal (tree l1, tree l2)
4252 {
4253   return attribute_list_contained (l1, l2)
4254          && attribute_list_contained (l2, l1);
4255 }
4256
4257 /* Given two lists of attributes, return true if list L2 is
4258    completely contained within L1.  */
4259 /* ??? This would be faster if attribute names were stored in a canonicalized
4260    form.  Otherwise, if L1 uses `foo' and L2 uses `__foo__', the long method
4261    must be used to show these elements are equivalent (which they are).  */
4262 /* ??? It's not clear that attributes with arguments will always be handled
4263    correctly.  */
4264
4265 int
4266 attribute_list_contained (tree l1, tree l2)
4267 {
4268   tree t1, t2;
4269
4270   /* First check the obvious, maybe the lists are identical.  */
4271   if (l1 == l2)
4272     return 1;
4273
4274   /* Maybe the lists are similar.  */
4275   for (t1 = l1, t2 = l2;
4276        t1 != 0 && t2 != 0
4277         && TREE_PURPOSE (t1) == TREE_PURPOSE (t2)
4278         && TREE_VALUE (t1) == TREE_VALUE (t2);
4279        t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2));
4280
4281   /* Maybe the lists are equal.  */
4282   if (t1 == 0 && t2 == 0)
4283     return 1;
4284
4285   for (; t2 != 0; t2 = TREE_CHAIN (t2))
4286     {
4287       tree attr;
4288       for (attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)), l1);
4289            attr != NULL_TREE;
4290            attr = lookup_attribute (IDENTIFIER_POINTER (TREE_PURPOSE (t2)),
4291                                     TREE_CHAIN (attr)))
4292         {
4293           if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) == 1)
4294             break;
4295         }
4296
4297       if (attr == 0)
4298         return 0;
4299
4300       if (simple_cst_equal (TREE_VALUE (t2), TREE_VALUE (attr)) != 1)
4301         return 0;
4302     }
4303
4304   return 1;
4305 }
4306
4307 /* Given two lists of types
4308    (chains of TREE_LIST nodes with types in the TREE_VALUE slots)
4309    return 1 if the lists contain the same types in the same order.
4310    Also, the TREE_PURPOSEs must match.  */
4311
4312 int
4313 type_list_equal (tree l1, tree l2)
4314 {
4315   tree t1, t2;
4316
4317   for (t1 = l1, t2 = l2; t1 && t2; t1 = TREE_CHAIN (t1), t2 = TREE_CHAIN (t2))
4318     if (TREE_VALUE (t1) != TREE_VALUE (t2)
4319         || (TREE_PURPOSE (t1) != TREE_PURPOSE (t2)
4320             && ! (1 == simple_cst_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2))
4321                   && (TREE_TYPE (TREE_PURPOSE (t1))
4322                       == TREE_TYPE (TREE_PURPOSE (t2))))))
4323       return 0;
4324
4325   return t1 == t2;
4326 }
4327
4328 /* Returns the number of arguments to the FUNCTION_TYPE or METHOD_TYPE
4329    given by TYPE.  If the argument list accepts variable arguments,
4330    then this function counts only the ordinary arguments.  */
4331
4332 int
4333 type_num_arguments (tree type)
4334 {
4335   int i = 0;
4336   tree t;
4337
4338   for (t = TYPE_ARG_TYPES (type); t; t = TREE_CHAIN (t))
4339     /* If the function does not take a variable number of arguments,
4340        the last element in the list will have type `void'.  */
4341     if (VOID_TYPE_P (TREE_VALUE (t)))
4342       break;
4343     else
4344       ++i;
4345
4346   return i;
4347 }
4348
4349 /* Nonzero if integer constants T1 and T2
4350    represent the same constant value.  */
4351
4352 int
4353 tree_int_cst_equal (tree t1, tree t2)
4354 {
4355   if (t1 == t2)
4356     return 1;
4357
4358   if (t1 == 0 || t2 == 0)
4359     return 0;
4360
4361   if (TREE_CODE (t1) == INTEGER_CST
4362       && TREE_CODE (t2) == INTEGER_CST
4363       && TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4364       && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2))
4365     return 1;
4366
4367   return 0;
4368 }
4369
4370 /* Nonzero if integer constants T1 and T2 represent values that satisfy <.
4371    The precise way of comparison depends on their data type.  */
4372
4373 int
4374 tree_int_cst_lt (tree t1, tree t2)
4375 {
4376   if (t1 == t2)
4377     return 0;
4378
4379   if (TYPE_UNSIGNED (TREE_TYPE (t1)) != TYPE_UNSIGNED (TREE_TYPE (t2)))
4380     {
4381       int t1_sgn = tree_int_cst_sgn (t1);
4382       int t2_sgn = tree_int_cst_sgn (t2);
4383
4384       if (t1_sgn < t2_sgn)
4385         return 1;
4386       else if (t1_sgn > t2_sgn)
4387         return 0;
4388       /* Otherwise, both are non-negative, so we compare them as
4389          unsigned just in case one of them would overflow a signed
4390          type.  */
4391     }
4392   else if (!TYPE_UNSIGNED (TREE_TYPE (t1)))
4393     return INT_CST_LT (t1, t2);
4394
4395   return INT_CST_LT_UNSIGNED (t1, t2);
4396 }
4397
4398 /* Returns -1 if T1 < T2, 0 if T1 == T2, and 1 if T1 > T2.  */
4399
4400 int
4401 tree_int_cst_compare (tree t1, tree t2)
4402 {
4403   if (tree_int_cst_lt (t1, t2))
4404     return -1;
4405   else if (tree_int_cst_lt (t2, t1))
4406     return 1;
4407   else
4408     return 0;
4409 }
4410
4411 /* Return 1 if T is an INTEGER_CST that can be manipulated efficiently on
4412    the host.  If POS is zero, the value can be represented in a single
4413    HOST_WIDE_INT.  If POS is nonzero, the value must be non-negative and can
4414    be represented in a single unsigned HOST_WIDE_INT.  */
4415
4416 int
4417 host_integerp (tree t, int pos)
4418 {
4419   return (TREE_CODE (t) == INTEGER_CST
4420           && ! TREE_OVERFLOW (t)
4421           && ((TREE_INT_CST_HIGH (t) == 0
4422                && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) >= 0)
4423               || (! pos && TREE_INT_CST_HIGH (t) == -1
4424                   && (HOST_WIDE_INT) TREE_INT_CST_LOW (t) < 0
4425                   && !TYPE_UNSIGNED (TREE_TYPE (t)))
4426               || (pos && TREE_INT_CST_HIGH (t) == 0)));
4427 }
4428
4429 /* Return the HOST_WIDE_INT least significant bits of T if it is an
4430    INTEGER_CST and there is no overflow.  POS is nonzero if the result must
4431    be non-negative.  We must be able to satisfy the above conditions.  */
4432
4433 HOST_WIDE_INT
4434 tree_low_cst (tree t, int pos)
4435 {
4436   gcc_assert (host_integerp (t, pos));
4437   return TREE_INT_CST_LOW (t);
4438 }
4439
4440 /* Return the most significant bit of the integer constant T.  */
4441
4442 int
4443 tree_int_cst_msb (tree t)
4444 {
4445   int prec;
4446   HOST_WIDE_INT h;
4447   unsigned HOST_WIDE_INT l;
4448
4449   /* Note that using TYPE_PRECISION here is wrong.  We care about the
4450      actual bits, not the (arbitrary) range of the type.  */
4451   prec = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (t))) - 1;
4452   rshift_double (TREE_INT_CST_LOW (t), TREE_INT_CST_HIGH (t), prec,
4453                  2 * HOST_BITS_PER_WIDE_INT, &l, &h, 0);
4454   return (l & 1) == 1;
4455 }
4456
4457 /* Return an indication of the sign of the integer constant T.
4458    The return value is -1 if T < 0, 0 if T == 0, and 1 if T > 0.
4459    Note that -1 will never be returned if T's type is unsigned.  */
4460
4461 int
4462 tree_int_cst_sgn (tree t)
4463 {
4464   if (TREE_INT_CST_LOW (t) == 0 && TREE_INT_CST_HIGH (t) == 0)
4465     return 0;
4466   else if (TYPE_UNSIGNED (TREE_TYPE (t)))
4467     return 1;
4468   else if (TREE_INT_CST_HIGH (t) < 0)
4469     return -1;
4470   else
4471     return 1;
4472 }
4473
4474 /* Compare two constructor-element-type constants.  Return 1 if the lists
4475    are known to be equal; otherwise return 0.  */
4476
4477 int
4478 simple_cst_list_equal (tree l1, tree l2)
4479 {
4480   while (l1 != NULL_TREE && l2 != NULL_TREE)
4481     {
4482       if (simple_cst_equal (TREE_VALUE (l1), TREE_VALUE (l2)) != 1)
4483         return 0;
4484
4485       l1 = TREE_CHAIN (l1);
4486       l2 = TREE_CHAIN (l2);
4487     }
4488
4489   return l1 == l2;
4490 }
4491
4492 /* Return truthvalue of whether T1 is the same tree structure as T2.
4493    Return 1 if they are the same.
4494    Return 0 if they are understandably different.
4495    Return -1 if either contains tree structure not understood by
4496    this function.  */
4497
4498 int
4499 simple_cst_equal (tree t1, tree t2)
4500 {
4501   enum tree_code code1, code2;
4502   int cmp;
4503   int i;
4504
4505   if (t1 == t2)
4506     return 1;
4507   if (t1 == 0 || t2 == 0)
4508     return 0;
4509
4510   code1 = TREE_CODE (t1);
4511   code2 = TREE_CODE (t2);
4512
4513   if (code1 == NOP_EXPR || code1 == CONVERT_EXPR || code1 == NON_LVALUE_EXPR)
4514     {
4515       if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4516           || code2 == NON_LVALUE_EXPR)
4517         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4518       else
4519         return simple_cst_equal (TREE_OPERAND (t1, 0), t2);
4520     }
4521
4522   else if (code2 == NOP_EXPR || code2 == CONVERT_EXPR
4523            || code2 == NON_LVALUE_EXPR)
4524     return simple_cst_equal (t1, TREE_OPERAND (t2, 0));
4525
4526   if (code1 != code2)
4527     return 0;
4528
4529   switch (code1)
4530     {
4531     case INTEGER_CST:
4532       return (TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
4533               && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2));
4534
4535     case REAL_CST:
4536       return REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
4537
4538     case STRING_CST:
4539       return (TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
4540               && ! memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
4541                          TREE_STRING_LENGTH (t1)));
4542
4543     case CONSTRUCTOR:
4544       {
4545         unsigned HOST_WIDE_INT idx;
4546         VEC(constructor_elt, gc) *v1 = CONSTRUCTOR_ELTS (t1);
4547         VEC(constructor_elt, gc) *v2 = CONSTRUCTOR_ELTS (t2);
4548
4549         if (VEC_length (constructor_elt, v1) != VEC_length (constructor_elt, v2))
4550           return false;
4551
4552         for (idx = 0; idx < VEC_length (constructor_elt, v1); ++idx)
4553           /* ??? Should we handle also fields here? */
4554           if (!simple_cst_equal (VEC_index (constructor_elt, v1, idx)->value,
4555                                  VEC_index (constructor_elt, v2, idx)->value))
4556             return false;
4557         return true;
4558       }
4559
4560     case SAVE_EXPR:
4561       return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4562
4563     case CALL_EXPR:
4564       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4565       if (cmp <= 0)
4566         return cmp;
4567       return
4568         simple_cst_list_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4569
4570     case TARGET_EXPR:
4571       /* Special case: if either target is an unallocated VAR_DECL,
4572          it means that it's going to be unified with whatever the
4573          TARGET_EXPR is really supposed to initialize, so treat it
4574          as being equivalent to anything.  */
4575       if ((TREE_CODE (TREE_OPERAND (t1, 0)) == VAR_DECL
4576            && DECL_NAME (TREE_OPERAND (t1, 0)) == NULL_TREE
4577            && !DECL_RTL_SET_P (TREE_OPERAND (t1, 0)))
4578           || (TREE_CODE (TREE_OPERAND (t2, 0)) == VAR_DECL
4579               && DECL_NAME (TREE_OPERAND (t2, 0)) == NULL_TREE
4580               && !DECL_RTL_SET_P (TREE_OPERAND (t2, 0))))
4581         cmp = 1;
4582       else
4583         cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4584
4585       if (cmp <= 0)
4586         return cmp;
4587
4588       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
4589
4590     case WITH_CLEANUP_EXPR:
4591       cmp = simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4592       if (cmp <= 0)
4593         return cmp;
4594
4595       return simple_cst_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
4596
4597     case COMPONENT_REF:
4598       if (TREE_OPERAND (t1, 1) == TREE_OPERAND (t2, 1))
4599         return simple_cst_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
4600
4601       return 0;
4602
4603     case VAR_DECL:
4604     case PARM_DECL:
4605     case CONST_DECL:
4606     case FUNCTION_DECL:
4607       return 0;
4608
4609     default:
4610       break;
4611     }
4612
4613   /* This general rule works for most tree codes.  All exceptions should be
4614      handled above.  If this is a language-specific tree code, we can't
4615      trust what might be in the operand, so say we don't know
4616      the situation.  */
4617   if ((int) code1 >= (int) LAST_AND_UNUSED_TREE_CODE)
4618     return -1;
4619
4620   switch (TREE_CODE_CLASS (code1))
4621     {
4622     case tcc_unary:
4623     case tcc_binary:
4624     case tcc_comparison:
4625     case tcc_expression:
4626     case tcc_reference:
4627     case tcc_statement:
4628       cmp = 1;
4629       for (i = 0; i < TREE_CODE_LENGTH (code1); i++)
4630         {
4631           cmp = simple_cst_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i));
4632           if (cmp <= 0)
4633             return cmp;
4634         }
4635
4636       return cmp;
4637
4638     default:
4639       return -1;
4640     }
4641 }
4642
4643 /* Compare the value of T, an INTEGER_CST, with U, an unsigned integer value.
4644    Return -1, 0, or 1 if the value of T is less than, equal to, or greater
4645    than U, respectively.  */
4646
4647 int
4648 compare_tree_int (tree t, unsigned HOST_WIDE_INT u)
4649 {
4650   if (tree_int_cst_sgn (t) < 0)
4651     return -1;
4652   else if (TREE_INT_CST_HIGH (t) != 0)
4653     return 1;
4654   else if (TREE_INT_CST_LOW (t) == u)
4655     return 0;
4656   else if (TREE_INT_CST_LOW (t) < u)
4657     return -1;
4658   else
4659     return 1;
4660 }
4661
4662 /* Return true if CODE represents an associative tree code.  Otherwise
4663    return false.  */
4664 bool
4665 associative_tree_code (enum tree_code code)
4666 {
4667   switch (code)
4668     {
4669     case BIT_IOR_EXPR:
4670     case BIT_AND_EXPR:
4671     case BIT_XOR_EXPR:
4672     case PLUS_EXPR:
4673     case MULT_EXPR:
4674     case MIN_EXPR:
4675     case MAX_EXPR:
4676       return true;
4677
4678     default:
4679       break;
4680     }
4681   return false;
4682 }
4683
4684 /* Return true if CODE represents a commutative tree code.  Otherwise
4685    return false.  */
4686 bool
4687 commutative_tree_code (enum tree_code code)
4688 {
4689   switch (code)
4690     {
4691     case PLUS_EXPR:
4692     case MULT_EXPR:
4693     case MIN_EXPR:
4694     case MAX_EXPR:
4695     case BIT_IOR_EXPR:
4696     case BIT_XOR_EXPR:
4697     case BIT_AND_EXPR:
4698     case NE_EXPR:
4699     case EQ_EXPR:
4700     case UNORDERED_EXPR:
4701     case ORDERED_EXPR:
4702     case UNEQ_EXPR:
4703     case LTGT_EXPR:
4704     case TRUTH_AND_EXPR:
4705     case TRUTH_XOR_EXPR:
4706     case TRUTH_OR_EXPR:
4707       return true;
4708
4709     default:
4710       break;
4711     }
4712   return false;
4713 }
4714
4715 /* Generate a hash value for an expression.  This can be used iteratively
4716    by passing a previous result as the "val" argument.
4717
4718    This function is intended to produce the same hash for expressions which
4719    would compare equal using operand_equal_p.  */
4720
4721 hashval_t
4722 iterative_hash_expr (tree t, hashval_t val)
4723 {
4724   int i;
4725   enum tree_code code;
4726   char class;
4727
4728   if (t == NULL_TREE)
4729     return iterative_hash_pointer (t, val);
4730
4731   code = TREE_CODE (t);
4732
4733   switch (code)
4734     {
4735     /* Alas, constants aren't shared, so we can't rely on pointer
4736        identity.  */
4737     case INTEGER_CST:
4738       val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val);
4739       return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val);
4740     case REAL_CST:
4741       {
4742         unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t));
4743
4744         return iterative_hash_hashval_t (val2, val);
4745       }
4746     case STRING_CST:
4747       return iterative_hash (TREE_STRING_POINTER (t),
4748                              TREE_STRING_LENGTH (t), val);
4749     case COMPLEX_CST:
4750       val = iterative_hash_expr (TREE_REALPART (t), val);
4751       return iterative_hash_expr (TREE_IMAGPART (t), val);
4752     case VECTOR_CST:
4753       return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val);
4754
4755     case SSA_NAME:
4756     case VALUE_HANDLE:
4757       /* we can just compare by pointer.  */
4758       return iterative_hash_pointer (t, val);
4759
4760     case TREE_LIST:
4761       /* A list of expressions, for a CALL_EXPR or as the elements of a
4762          VECTOR_CST.  */
4763       for (; t; t = TREE_CHAIN (t))
4764         val = iterative_hash_expr (TREE_VALUE (t), val);
4765       return val;
4766     case CONSTRUCTOR:
4767       {
4768         unsigned HOST_WIDE_INT idx;
4769         tree field, value;
4770         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t), idx, field, value)
4771           {
4772             val = iterative_hash_expr (field, val);
4773             val = iterative_hash_expr (value, val);
4774           }
4775         return val;
4776       }
4777     case FUNCTION_DECL:
4778       /* When referring to a built-in FUNCTION_DECL, use the
4779          __builtin__ form.  Otherwise nodes that compare equal
4780          according to operand_equal_p might get different
4781          hash codes.  */
4782       if (DECL_BUILT_IN (t))
4783         {
4784           val = iterative_hash_pointer (built_in_decls[DECL_FUNCTION_CODE (t)],
4785                                       val);
4786           return val;
4787         }
4788       /* else FALL THROUGH */
4789     default:
4790       class = TREE_CODE_CLASS (code);
4791
4792       if (class == tcc_declaration)
4793         {
4794           /* DECL's have a unique ID */
4795           val = iterative_hash_host_wide_int (DECL_UID (t), val);
4796         }
4797       else
4798         {
4799           gcc_assert (IS_EXPR_CODE_CLASS (class));
4800
4801           val = iterative_hash_object (code, val);
4802
4803           /* Don't hash the type, that can lead to having nodes which
4804              compare equal according to operand_equal_p, but which
4805              have different hash codes.  */
4806           if (code == NOP_EXPR
4807               || code == CONVERT_EXPR
4808               || code == NON_LVALUE_EXPR)
4809             {
4810               /* Make sure to include signness in the hash computation.  */
4811               val += TYPE_UNSIGNED (TREE_TYPE (t));
4812               val = iterative_hash_expr (TREE_OPERAND (t, 0), val);
4813             }
4814
4815           else if (commutative_tree_code (code))
4816             {
4817               /* It's a commutative expression.  We want to hash it the same
4818                  however it appears.  We do this by first hashing both operands
4819                  and then rehashing based on the order of their independent
4820                  hashes.  */
4821               hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0);
4822               hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0);
4823               hashval_t t;
4824
4825               if (one > two)
4826                 t = one, one = two, two = t;
4827
4828               val = iterative_hash_hashval_t (one, val);
4829               val = iterative_hash_hashval_t (two, val);
4830             }
4831           else
4832             for (i = TREE_CODE_LENGTH (code) - 1; i >= 0; --i)
4833               val = iterative_hash_expr (TREE_OPERAND (t, i), val);
4834         }
4835       return val;
4836       break;
4837     }
4838 }
4839 \f
4840 /* Constructors for pointer, array and function types.
4841    (RECORD_TYPE, UNION_TYPE and ENUMERAL_TYPE nodes are
4842    constructed by language-dependent code, not here.)  */
4843
4844 /* Construct, lay out and return the type of pointers to TO_TYPE with
4845    mode MODE.  If CAN_ALIAS_ALL is TRUE, indicate this type can
4846    reference all of memory. If such a type has already been
4847    constructed, reuse it.  */
4848
4849 tree
4850 build_pointer_type_for_mode (tree to_type, enum machine_mode mode,
4851                              bool can_alias_all)
4852 {
4853   tree t;
4854
4855   if (to_type == error_mark_node)
4856     return error_mark_node;
4857
4858   /* In some cases, languages will have things that aren't a POINTER_TYPE
4859      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_POINTER_TO.
4860      In that case, return that type without regard to the rest of our
4861      operands.
4862
4863      ??? This is a kludge, but consistent with the way this function has
4864      always operated and there doesn't seem to be a good way to avoid this
4865      at the moment.  */
4866   if (TYPE_POINTER_TO (to_type) != 0
4867       && TREE_CODE (TYPE_POINTER_TO (to_type)) != POINTER_TYPE)
4868     return TYPE_POINTER_TO (to_type);
4869
4870   /* First, if we already have an unqualified type for pointers to TO_TYPE
4871      and it's the proper mode, use it.  */
4872   for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t))
4873     if (TYPE_MODE (t) == mode
4874         && !TYPE_QUALS (t)
4875         && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4876       return t;
4877
4878   t = make_node (POINTER_TYPE);
4879
4880   TREE_TYPE (t) = to_type;
4881   TYPE_MODE (t) = mode;
4882   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4883   TYPE_NEXT_PTR_TO (t) = TYPE_POINTER_TO (to_type);
4884   TYPE_POINTER_TO (to_type) = t;
4885
4886   /* Lay out the type.  This function has many callers that are concerned
4887      with expression-construction, and this simplifies them all.  */
4888   layout_type (t);
4889
4890   return t;
4891 }
4892
4893 /* By default build pointers in ptr_mode.  */
4894
4895 tree
4896 build_pointer_type (tree to_type)
4897 {
4898   return build_pointer_type_for_mode (to_type, ptr_mode, false);
4899 }
4900
4901 /* Same as build_pointer_type_for_mode, but for REFERENCE_TYPE.  */
4902
4903 tree
4904 build_reference_type_for_mode (tree to_type, enum machine_mode mode,
4905                                bool can_alias_all)
4906 {
4907   tree t;
4908
4909   /* In some cases, languages will have things that aren't a REFERENCE_TYPE
4910      (such as a RECORD_TYPE for fat pointers in Ada) as TYPE_REFERENCE_TO.
4911      In that case, return that type without regard to the rest of our
4912      operands.
4913
4914      ??? This is a kludge, but consistent with the way this function has
4915      always operated and there doesn't seem to be a good way to avoid this
4916      at the moment.  */
4917   if (TYPE_REFERENCE_TO (to_type) != 0
4918       && TREE_CODE (TYPE_REFERENCE_TO (to_type)) != REFERENCE_TYPE)
4919     return TYPE_REFERENCE_TO (to_type);
4920
4921   /* First, if we already have an unqualified type for references to TO_TYPE
4922      and it's the proper mode, use it.  */
4923   for (t = TYPE_REFERENCE_TO (to_type); t; t = TYPE_NEXT_REF_TO (t))
4924     if (TYPE_MODE (t) == mode
4925         && !TYPE_QUALS (t)
4926         && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all)
4927       return t;
4928
4929   t = make_node (REFERENCE_TYPE);
4930
4931   TREE_TYPE (t) = to_type;
4932   TYPE_MODE (t) = mode;
4933   TYPE_REF_CAN_ALIAS_ALL (t) = can_alias_all;
4934   TYPE_NEXT_REF_TO (t) = TYPE_REFERENCE_TO (to_type);
4935   TYPE_REFERENCE_TO (to_type) = t;
4936
4937   layout_type (t);
4938
4939   return t;
4940 }
4941
4942
4943 /* Build the node for the type of references-to-TO_TYPE by default
4944    in ptr_mode.  */
4945
4946 tree
4947 build_reference_type (tree to_type)
4948 {
4949   return build_reference_type_for_mode (to_type, ptr_mode, false);
4950 }
4951
4952 /* Build a type that is compatible with t but has no cv quals anywhere
4953    in its type, thus
4954
4955    const char *const *const *  ->  char ***.  */
4956
4957 tree
4958 build_type_no_quals (tree t)
4959 {
4960   switch (TREE_CODE (t))
4961     {
4962     case POINTER_TYPE:
4963       return build_pointer_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4964                                           TYPE_MODE (t),
4965                                           TYPE_REF_CAN_ALIAS_ALL (t));
4966     case REFERENCE_TYPE:
4967       return
4968         build_reference_type_for_mode (build_type_no_quals (TREE_TYPE (t)),
4969                                        TYPE_MODE (t),
4970                                        TYPE_REF_CAN_ALIAS_ALL (t));
4971     default:
4972       return TYPE_MAIN_VARIANT (t);
4973     }
4974 }
4975
4976 /* Create a type of integers to be the TYPE_DOMAIN of an ARRAY_TYPE.
4977    MAXVAL should be the maximum value in the domain
4978    (one less than the length of the array).
4979
4980    The maximum value that MAXVAL can have is INT_MAX for a HOST_WIDE_INT.
4981    We don't enforce this limit, that is up to caller (e.g. language front end).
4982    The limit exists because the result is a signed type and we don't handle
4983    sizes that use more than one HOST_WIDE_INT.  */
4984
4985 tree
4986 build_index_type (tree maxval)
4987 {
4988   tree itype = make_node (INTEGER_TYPE);
4989
4990   TREE_TYPE (itype) = sizetype;
4991   TYPE_PRECISION (itype) = TYPE_PRECISION (sizetype);
4992   TYPE_MIN_VALUE (itype) = size_zero_node;
4993   TYPE_MAX_VALUE (itype) = fold_convert (sizetype, maxval);
4994   TYPE_MODE (itype) = TYPE_MODE (sizetype);
4995   TYPE_SIZE (itype) = TYPE_SIZE (sizetype);
4996   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (sizetype);
4997   TYPE_ALIGN (itype) = TYPE_ALIGN (sizetype);
4998   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (sizetype);
4999
5000   if (host_integerp (maxval, 1))
5001     return type_hash_canon (tree_low_cst (maxval, 1), itype);
5002   else
5003     return itype;
5004 }
5005
5006 /* Builds a signed or unsigned integer type of precision PRECISION.
5007    Used for C bitfields whose precision does not match that of
5008    built-in target types.  */
5009 tree
5010 build_nonstandard_integer_type (unsigned HOST_WIDE_INT precision,
5011                                 int unsignedp)
5012 {
5013   tree itype = make_node (INTEGER_TYPE);
5014
5015   TYPE_PRECISION (itype) = precision;
5016
5017   if (unsignedp)
5018     fixup_unsigned_type (itype);
5019   else
5020     fixup_signed_type (itype);
5021
5022   if (host_integerp (TYPE_MAX_VALUE (itype), 1))
5023     return type_hash_canon (tree_low_cst (TYPE_MAX_VALUE (itype), 1), itype);
5024
5025   return itype;
5026 }
5027
5028 /* Create a range of some discrete type TYPE (an INTEGER_TYPE,
5029    ENUMERAL_TYPE, BOOLEAN_TYPE, or CHAR_TYPE), with
5030    low bound LOWVAL and high bound HIGHVAL.
5031    if TYPE==NULL_TREE, sizetype is used.  */
5032
5033 tree
5034 build_range_type (tree type, tree lowval, tree highval)
5035 {
5036   tree itype = make_node (INTEGER_TYPE);
5037
5038   TREE_TYPE (itype) = type;
5039   if (type == NULL_TREE)
5040     type = sizetype;
5041
5042   TYPE_MIN_VALUE (itype) = convert (type, lowval);
5043   TYPE_MAX_VALUE (itype) = highval ? convert (type, highval) : NULL;
5044
5045   TYPE_PRECISION (itype) = TYPE_PRECISION (type);
5046   TYPE_MODE (itype) = TYPE_MODE (type);
5047   TYPE_SIZE (itype) = TYPE_SIZE (type);
5048   TYPE_SIZE_UNIT (itype) = TYPE_SIZE_UNIT (type);
5049   TYPE_ALIGN (itype) = TYPE_ALIGN (type);
5050   TYPE_USER_ALIGN (itype) = TYPE_USER_ALIGN (type);
5051
5052   if (host_integerp (lowval, 0) && highval != 0 && host_integerp (highval, 0))
5053     return type_hash_canon (tree_low_cst (highval, 0)
5054                             - tree_low_cst (lowval, 0),
5055                             itype);
5056   else
5057     return itype;
5058 }
5059
5060 /* Just like build_index_type, but takes lowval and highval instead
5061    of just highval (maxval).  */
5062
5063 tree
5064 build_index_2_type (tree lowval, tree highval)
5065 {
5066   return build_range_type (sizetype, lowval, highval);
5067 }
5068
5069 /* Construct, lay out and return the type of arrays of elements with ELT_TYPE
5070    and number of elements specified by the range of values of INDEX_TYPE.
5071    If such a type has already been constructed, reuse it.  */
5072
5073 tree
5074 build_array_type (tree elt_type, tree index_type)
5075 {
5076   tree t;
5077   hashval_t hashcode = 0;
5078
5079   if (TREE_CODE (elt_type) == FUNCTION_TYPE)
5080     {
5081       error ("arrays of functions are not meaningful");
5082       elt_type = integer_type_node;
5083     }
5084
5085   t = make_node (ARRAY_TYPE);
5086   TREE_TYPE (t) = elt_type;
5087   TYPE_DOMAIN (t) = index_type;
5088
5089   if (index_type == 0)
5090     {
5091       layout_type (t);
5092       return t;
5093     }
5094
5095   hashcode = iterative_hash_object (TYPE_HASH (elt_type), hashcode);
5096   hashcode = iterative_hash_object (TYPE_HASH (index_type), hashcode);
5097   t = type_hash_canon (hashcode, t);
5098
5099   if (!COMPLETE_TYPE_P (t))
5100     layout_type (t);
5101   return t;
5102 }
5103
5104 /* Return the TYPE of the elements comprising
5105    the innermost dimension of ARRAY.  */
5106
5107 tree
5108 get_inner_array_type (tree array)
5109 {
5110   tree type = TREE_TYPE (array);
5111
5112   while (TREE_CODE (type) == ARRAY_TYPE)
5113     type = TREE_TYPE (type);
5114
5115   return type;
5116 }
5117
5118 /* Construct, lay out and return
5119    the type of functions returning type VALUE_TYPE
5120    given arguments of types ARG_TYPES.
5121    ARG_TYPES is a chain of TREE_LIST nodes whose TREE_VALUEs
5122    are data type nodes for the arguments of the function.
5123    If such a type has already been constructed, reuse it.  */
5124
5125 tree
5126 build_function_type (tree value_type, tree arg_types)
5127 {
5128   tree t;
5129   hashval_t hashcode = 0;
5130
5131   if (TREE_CODE (value_type) == FUNCTION_TYPE)
5132     {
5133       error ("function return type cannot be function");
5134       value_type = integer_type_node;
5135     }
5136
5137   /* Make a node of the sort we want.  */
5138   t = make_node (FUNCTION_TYPE);
5139   TREE_TYPE (t) = value_type;
5140   TYPE_ARG_TYPES (t) = arg_types;
5141
5142   /* If we already have such a type, use the old one.  */
5143   hashcode = iterative_hash_object (TYPE_HASH (value_type), hashcode);
5144   hashcode = type_hash_list (arg_types, hashcode);
5145   t = type_hash_canon (hashcode, t);
5146
5147   if (!COMPLETE_TYPE_P (t))
5148     layout_type (t);
5149   return t;
5150 }
5151
5152 /* Build a function type.  The RETURN_TYPE is the type returned by the
5153    function.  If additional arguments are provided, they are
5154    additional argument types.  The list of argument types must always
5155    be terminated by NULL_TREE.  */
5156
5157 tree
5158 build_function_type_list (tree return_type, ...)
5159 {
5160   tree t, args, last;
5161   va_list p;
5162
5163   va_start (p, return_type);
5164
5165   t = va_arg (p, tree);
5166   for (args = NULL_TREE; t != NULL_TREE; t = va_arg (p, tree))
5167     args = tree_cons (NULL_TREE, t, args);
5168
5169   if (args == NULL_TREE)
5170     args = void_list_node;
5171   else
5172     {
5173       last = args;
5174       args = nreverse (args);
5175       TREE_CHAIN (last) = void_list_node;
5176     }
5177   args = build_function_type (return_type, args);
5178
5179   va_end (p);
5180   return args;
5181 }
5182
5183 /* Build a METHOD_TYPE for a member of BASETYPE.  The RETTYPE (a TYPE)
5184    and ARGTYPES (a TREE_LIST) are the return type and arguments types
5185    for the method.  An implicit additional parameter (of type
5186    pointer-to-BASETYPE) is added to the ARGTYPES.  */
5187
5188 tree
5189 build_method_type_directly (tree basetype,
5190                             tree rettype,
5191                             tree argtypes)
5192 {
5193   tree t;
5194   tree ptype;
5195   int hashcode = 0;
5196
5197   /* Make a node of the sort we want.  */
5198   t = make_node (METHOD_TYPE);
5199
5200   TYPE_METHOD_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5201   TREE_TYPE (t) = rettype;
5202   ptype = build_pointer_type (basetype);
5203
5204   /* The actual arglist for this function includes a "hidden" argument
5205      which is "this".  Put it into the list of argument types.  */
5206   argtypes = tree_cons (NULL_TREE, ptype, argtypes);
5207   TYPE_ARG_TYPES (t) = argtypes;
5208
5209   /* If we already have such a type, use the old one.  */
5210   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5211   hashcode = iterative_hash_object (TYPE_HASH (rettype), hashcode);
5212   hashcode = type_hash_list (argtypes, hashcode);
5213   t = type_hash_canon (hashcode, t);
5214
5215   if (!COMPLETE_TYPE_P (t))
5216     layout_type (t);
5217
5218   return t;
5219 }
5220
5221 /* Construct, lay out and return the type of methods belonging to class
5222    BASETYPE and whose arguments and values are described by TYPE.
5223    If that type exists already, reuse it.
5224    TYPE must be a FUNCTION_TYPE node.  */
5225
5226 tree
5227 build_method_type (tree basetype, tree type)
5228 {
5229   gcc_assert (TREE_CODE (type) == FUNCTION_TYPE);
5230
5231   return build_method_type_directly (basetype,
5232                                      TREE_TYPE (type),
5233                                      TYPE_ARG_TYPES (type));
5234 }
5235
5236 /* Construct, lay out and return the type of offsets to a value
5237    of type TYPE, within an object of type BASETYPE.
5238    If a suitable offset type exists already, reuse it.  */
5239
5240 tree
5241 build_offset_type (tree basetype, tree type)
5242 {
5243   tree t;
5244   hashval_t hashcode = 0;
5245
5246   /* Make a node of the sort we want.  */
5247   t = make_node (OFFSET_TYPE);
5248
5249   TYPE_OFFSET_BASETYPE (t) = TYPE_MAIN_VARIANT (basetype);
5250   TREE_TYPE (t) = type;
5251
5252   /* If we already have such a type, use the old one.  */
5253   hashcode = iterative_hash_object (TYPE_HASH (basetype), hashcode);
5254   hashcode = iterative_hash_object (TYPE_HASH (type), hashcode);
5255   t = type_hash_canon (hashcode, t);
5256
5257   if (!COMPLETE_TYPE_P (t))
5258     layout_type (t);
5259
5260   return t;
5261 }
5262
5263 /* Create a complex type whose components are COMPONENT_TYPE.  */
5264
5265 tree
5266 build_complex_type (tree component_type)
5267 {
5268   tree t;
5269   hashval_t hashcode;
5270
5271   /* Make a node of the sort we want.  */
5272   t = make_node (COMPLEX_TYPE);
5273
5274   TREE_TYPE (t) = TYPE_MAIN_VARIANT (component_type);
5275
5276   /* If we already have such a type, use the old one.  */
5277   hashcode = iterative_hash_object (TYPE_HASH (component_type), 0);
5278   t = type_hash_canon (hashcode, t);
5279
5280   if (!COMPLETE_TYPE_P (t))
5281     layout_type (t);
5282
5283   /* If we are writing Dwarf2 output we need to create a name,
5284      since complex is a fundamental type.  */
5285   if ((write_symbols == DWARF2_DEBUG || write_symbols == VMS_AND_DWARF2_DEBUG)
5286       && ! TYPE_NAME (t))
5287     {
5288       const char *name;
5289       if (component_type == char_type_node)
5290         name = "complex char";
5291       else if (component_type == signed_char_type_node)
5292         name = "complex signed char";
5293       else if (component_type == unsigned_char_type_node)
5294         name = "complex unsigned char";
5295       else if (component_type == short_integer_type_node)
5296         name = "complex short int";
5297       else if (component_type == short_unsigned_type_node)
5298         name = "complex short unsigned int";
5299       else if (component_type == integer_type_node)
5300         name = "complex int";
5301       else if (component_type == unsigned_type_node)
5302         name = "complex unsigned int";
5303       else if (component_type == long_integer_type_node)
5304         name = "complex long int";
5305       else if (component_type == long_unsigned_type_node)
5306         name = "complex long unsigned int";
5307       else if (component_type == long_long_integer_type_node)
5308         name = "complex long long int";
5309       else if (component_type == long_long_unsigned_type_node)
5310         name = "complex long long unsigned int";
5311       else
5312         name = 0;
5313
5314       if (name != 0)
5315         TYPE_NAME (t) = get_identifier (name);
5316     }
5317
5318   return build_qualified_type (t, TYPE_QUALS (component_type));
5319 }
5320 \f
5321 /* Return OP, stripped of any conversions to wider types as much as is safe.
5322    Converting the value back to OP's type makes a value equivalent to OP.
5323
5324    If FOR_TYPE is nonzero, we return a value which, if converted to
5325    type FOR_TYPE, would be equivalent to converting OP to type FOR_TYPE.
5326
5327    If FOR_TYPE is nonzero, unaligned bit-field references may be changed to the
5328    narrowest type that can hold the value, even if they don't exactly fit.
5329    Otherwise, bit-field references are changed to a narrower type
5330    only if they can be fetched directly from memory in that type.
5331
5332    OP must have integer, real or enumeral type.  Pointers are not allowed!
5333
5334    There are some cases where the obvious value we could return
5335    would regenerate to OP if converted to OP's type,
5336    but would not extend like OP to wider types.
5337    If FOR_TYPE indicates such extension is contemplated, we eschew such values.
5338    For example, if OP is (unsigned short)(signed char)-1,
5339    we avoid returning (signed char)-1 if FOR_TYPE is int,
5340    even though extending that to an unsigned short would regenerate OP,
5341    since the result of extending (signed char)-1 to (int)
5342    is different from (int) OP.  */
5343
5344 tree
5345 get_unwidened (tree op, tree for_type)
5346 {
5347   /* Set UNS initially if converting OP to FOR_TYPE is a zero-extension.  */
5348   tree type = TREE_TYPE (op);
5349   unsigned final_prec
5350     = TYPE_PRECISION (for_type != 0 ? for_type : type);
5351   int uns
5352     = (for_type != 0 && for_type != type
5353        && final_prec > TYPE_PRECISION (type)
5354        && TYPE_UNSIGNED (type));
5355   tree win = op;
5356
5357   while (TREE_CODE (op) == NOP_EXPR
5358          || TREE_CODE (op) == CONVERT_EXPR)
5359     {
5360       int bitschange;
5361
5362       /* TYPE_PRECISION on vector types has different meaning
5363          (TYPE_VECTOR_SUBPARTS) and casts from vectors are view conversions,
5364          so avoid them here.  */
5365       if (TREE_CODE (TREE_TYPE (TREE_OPERAND (op, 0))) == VECTOR_TYPE)
5366         break;
5367
5368       bitschange = TYPE_PRECISION (TREE_TYPE (op))
5369                    - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0)));
5370
5371       /* Truncations are many-one so cannot be removed.
5372          Unless we are later going to truncate down even farther.  */
5373       if (bitschange < 0
5374           && final_prec > TYPE_PRECISION (TREE_TYPE (op)))
5375         break;
5376
5377       /* See what's inside this conversion.  If we decide to strip it,
5378          we will set WIN.  */
5379       op = TREE_OPERAND (op, 0);
5380
5381       /* If we have not stripped any zero-extensions (uns is 0),
5382          we can strip any kind of extension.
5383          If we have previously stripped a zero-extension,
5384          only zero-extensions can safely be stripped.
5385          Any extension can be stripped if the bits it would produce
5386          are all going to be discarded later by truncating to FOR_TYPE.  */
5387
5388       if (bitschange > 0)
5389         {
5390           if (! uns || final_prec <= TYPE_PRECISION (TREE_TYPE (op)))
5391             win = op;
5392           /* TYPE_UNSIGNED says whether this is a zero-extension.
5393              Let's avoid computing it if it does not affect WIN
5394              and if UNS will not be needed again.  */
5395           if ((uns
5396                || TREE_CODE (op) == NOP_EXPR
5397                || TREE_CODE (op) == CONVERT_EXPR)
5398               && TYPE_UNSIGNED (TREE_TYPE (op)))
5399             {
5400               uns = 1;
5401               win = op;
5402             }
5403         }
5404     }
5405
5406   if (TREE_CODE (op) == COMPONENT_REF
5407       /* Since type_for_size always gives an integer type.  */
5408       && TREE_CODE (type) != REAL_TYPE
5409       /* Don't crash if field not laid out yet.  */
5410       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5411       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5412     {
5413       unsigned int innerprec
5414         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5415       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5416                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5417       type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5418
5419       /* We can get this structure field in the narrowest type it fits in.
5420          If FOR_TYPE is 0, do this only for a field that matches the
5421          narrower type exactly and is aligned for it
5422          The resulting extension to its nominal type (a fullword type)
5423          must fit the same conditions as for other extensions.  */
5424
5425       if (type != 0
5426           && INT_CST_LT_UNSIGNED (TYPE_SIZE (type), TYPE_SIZE (TREE_TYPE (op)))
5427           && (for_type || ! DECL_BIT_FIELD (TREE_OPERAND (op, 1)))
5428           && (! uns || final_prec <= innerprec || unsignedp))
5429         {
5430           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5431                         TREE_OPERAND (op, 1), NULL_TREE);
5432           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5433           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5434         }
5435     }
5436
5437   return win;
5438 }
5439 \f
5440 /* Return OP or a simpler expression for a narrower value
5441    which can be sign-extended or zero-extended to give back OP.
5442    Store in *UNSIGNEDP_PTR either 1 if the value should be zero-extended
5443    or 0 if the value should be sign-extended.  */
5444
5445 tree
5446 get_narrower (tree op, int *unsignedp_ptr)
5447 {
5448   int uns = 0;
5449   int first = 1;
5450   tree win = op;
5451   bool integral_p = INTEGRAL_TYPE_P (TREE_TYPE (op));
5452
5453   while (TREE_CODE (op) == NOP_EXPR)
5454     {
5455       int bitschange
5456         = (TYPE_PRECISION (TREE_TYPE (op))
5457            - TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (op, 0))));
5458
5459       /* Truncations are many-one so cannot be removed.  */
5460       if (bitschange < 0)
5461         break;
5462
5463       /* See what's inside this conversion.  If we decide to strip it,
5464          we will set WIN.  */
5465
5466       if (bitschange > 0)
5467         {
5468           op = TREE_OPERAND (op, 0);
5469           /* An extension: the outermost one can be stripped,
5470              but remember whether it is zero or sign extension.  */
5471           if (first)
5472             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5473           /* Otherwise, if a sign extension has been stripped,
5474              only sign extensions can now be stripped;
5475              if a zero extension has been stripped, only zero-extensions.  */
5476           else if (uns != TYPE_UNSIGNED (TREE_TYPE (op)))
5477             break;
5478           first = 0;
5479         }
5480       else /* bitschange == 0 */
5481         {
5482           /* A change in nominal type can always be stripped, but we must
5483              preserve the unsignedness.  */
5484           if (first)
5485             uns = TYPE_UNSIGNED (TREE_TYPE (op));
5486           first = 0;
5487           op = TREE_OPERAND (op, 0);
5488           /* Keep trying to narrow, but don't assign op to win if it
5489              would turn an integral type into something else.  */
5490           if (INTEGRAL_TYPE_P (TREE_TYPE (op)) != integral_p)
5491             continue;
5492         }
5493
5494       win = op;
5495     }
5496
5497   if (TREE_CODE (op) == COMPONENT_REF
5498       /* Since type_for_size always gives an integer type.  */
5499       && TREE_CODE (TREE_TYPE (op)) != REAL_TYPE
5500       /* Ensure field is laid out already.  */
5501       && DECL_SIZE (TREE_OPERAND (op, 1)) != 0
5502       && host_integerp (DECL_SIZE (TREE_OPERAND (op, 1)), 1))
5503     {
5504       unsigned HOST_WIDE_INT innerprec
5505         = tree_low_cst (DECL_SIZE (TREE_OPERAND (op, 1)), 1);
5506       int unsignedp = (DECL_UNSIGNED (TREE_OPERAND (op, 1))
5507                        || TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (op, 1))));
5508       tree type = lang_hooks.types.type_for_size (innerprec, unsignedp);
5509
5510       /* We can get this structure field in a narrower type that fits it,
5511          but the resulting extension to its nominal type (a fullword type)
5512          must satisfy the same conditions as for other extensions.
5513
5514          Do this only for fields that are aligned (not bit-fields),
5515          because when bit-field insns will be used there is no
5516          advantage in doing this.  */
5517
5518       if (innerprec < TYPE_PRECISION (TREE_TYPE (op))
5519           && ! DECL_BIT_FIELD (TREE_OPERAND (op, 1))
5520           && (first || uns == DECL_UNSIGNED (TREE_OPERAND (op, 1)))
5521           && type != 0)
5522         {
5523           if (first)
5524             uns = DECL_UNSIGNED (TREE_OPERAND (op, 1));
5525           win = build3 (COMPONENT_REF, type, TREE_OPERAND (op, 0),
5526                         TREE_OPERAND (op, 1), NULL_TREE);
5527           TREE_SIDE_EFFECTS (win) = TREE_SIDE_EFFECTS (op);
5528           TREE_THIS_VOLATILE (win) = TREE_THIS_VOLATILE (op);
5529         }
5530     }
5531   *unsignedp_ptr = uns;
5532   return win;
5533 }
5534 \f
5535 /* Nonzero if integer constant C has a value that is permissible
5536    for type TYPE (an INTEGER_TYPE).  */
5537
5538 int
5539 int_fits_type_p (tree c, tree type)
5540 {
5541   tree type_low_bound = TYPE_MIN_VALUE (type);
5542   tree type_high_bound = TYPE_MAX_VALUE (type);
5543   bool ok_for_low_bound, ok_for_high_bound;
5544   tree tmp;
5545
5546   /* If at least one bound of the type is a constant integer, we can check
5547      ourselves and maybe make a decision. If no such decision is possible, but
5548      this type is a subtype, try checking against that.  Otherwise, use
5549      force_fit_type, which checks against the precision.
5550
5551      Compute the status for each possibly constant bound, and return if we see
5552      one does not match. Use ok_for_xxx_bound for this purpose, assigning -1
5553      for "unknown if constant fits", 0 for "constant known *not* to fit" and 1
5554      for "constant known to fit".  */
5555
5556   /* Check if C >= type_low_bound.  */
5557   if (type_low_bound && TREE_CODE (type_low_bound) == INTEGER_CST)
5558     {
5559       if (tree_int_cst_lt (c, type_low_bound))
5560         return 0;
5561       ok_for_low_bound = true;
5562     }
5563   else
5564     ok_for_low_bound = false;
5565
5566   /* Check if c <= type_high_bound.  */
5567   if (type_high_bound && TREE_CODE (type_high_bound) == INTEGER_CST)
5568     {
5569       if (tree_int_cst_lt (type_high_bound, c))
5570         return 0;
5571       ok_for_high_bound = true;
5572     }
5573   else
5574     ok_for_high_bound = false;
5575
5576   /* If the constant fits both bounds, the result is known.  */
5577   if (ok_for_low_bound && ok_for_high_bound)
5578     return 1;
5579
5580   /* Perform some generic filtering which may allow making a decision
5581      even if the bounds are not constant.  First, negative integers
5582      never fit in unsigned types, */
5583   if (TYPE_UNSIGNED (type) && tree_int_cst_sgn (c) < 0)
5584     return 0;
5585
5586   /* Second, narrower types always fit in wider ones.  */
5587   if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (c)))
5588     return 1;
5589
5590   /* Third, unsigned integers with top bit set never fit signed types.  */
5591   if (! TYPE_UNSIGNED (type)
5592       && TYPE_UNSIGNED (TREE_TYPE (c))
5593       && tree_int_cst_msb (c))
5594     return 0;
5595
5596   /* If we haven't been able to decide at this point, there nothing more we
5597      can check ourselves here.  Look at the base type if we have one and it
5598      has the same precision.  */
5599   if (TREE_CODE (type) == INTEGER_TYPE
5600       && TREE_TYPE (type) != 0
5601       && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (type)))
5602     return int_fits_type_p (c, TREE_TYPE (type));
5603
5604   /* Or to force_fit_type, if nothing else.  */
5605   tmp = copy_node (c);
5606   TREE_TYPE (tmp) = type;
5607   tmp = force_fit_type (tmp, -1, false, false);
5608   return TREE_INT_CST_HIGH (tmp) == TREE_INT_CST_HIGH (c)
5609          && TREE_INT_CST_LOW (tmp) == TREE_INT_CST_LOW (c);
5610 }
5611
5612 /* Subprogram of following function.  Called by walk_tree.
5613
5614    Return *TP if it is an automatic variable or parameter of the
5615    function passed in as DATA.  */
5616
5617 static tree
5618 find_var_from_fn (tree *tp, int *walk_subtrees, void *data)
5619 {
5620   tree fn = (tree) data;
5621
5622   if (TYPE_P (*tp))
5623     *walk_subtrees = 0;
5624
5625   else if (DECL_P (*tp)
5626            && lang_hooks.tree_inlining.auto_var_in_fn_p (*tp, fn))
5627     return *tp;
5628
5629   return NULL_TREE;
5630 }
5631
5632 /* Returns true if T is, contains, or refers to a type with variable
5633    size.  If FN is nonzero, only return true if a modifier of the type
5634    or position of FN is a variable or parameter inside FN.
5635
5636    This concept is more general than that of C99 'variably modified types':
5637    in C99, a struct type is never variably modified because a VLA may not
5638    appear as a structure member.  However, in GNU C code like:
5639
5640      struct S { int i[f()]; };
5641
5642    is valid, and other languages may define similar constructs.  */
5643
5644 bool
5645 variably_modified_type_p (tree type, tree fn)
5646 {
5647   tree t;
5648
5649 /* Test if T is either variable (if FN is zero) or an expression containing
5650    a variable in FN.  */
5651 #define RETURN_TRUE_IF_VAR(T)                                           \
5652   do { tree _t = (T);                                                   \
5653     if (_t && _t != error_mark_node && TREE_CODE (_t) != INTEGER_CST    \
5654         && (!fn || walk_tree (&_t, find_var_from_fn, fn, NULL)))        \
5655       return true;  } while (0)
5656
5657   if (type == error_mark_node)
5658     return false;
5659
5660   /* If TYPE itself has variable size, it is variably modified.
5661
5662      We do not yet have a representation of the C99 '[*]' syntax.
5663      When a representation is chosen, this function should be modified
5664      to test for that case as well.  */
5665   RETURN_TRUE_IF_VAR (TYPE_SIZE (type));
5666   RETURN_TRUE_IF_VAR (TYPE_SIZE_UNIT(type));
5667
5668   switch (TREE_CODE (type))
5669     {
5670     case POINTER_TYPE:
5671     case REFERENCE_TYPE:
5672     case ARRAY_TYPE:
5673     case VECTOR_TYPE:
5674       if (variably_modified_type_p (TREE_TYPE (type), fn))
5675         return true;
5676       break;
5677
5678     case FUNCTION_TYPE:
5679     case METHOD_TYPE:
5680       /* If TYPE is a function type, it is variably modified if any of the
5681          parameters or the return type are variably modified.  */
5682       if (variably_modified_type_p (TREE_TYPE (type), fn))
5683           return true;
5684
5685       for (t = TYPE_ARG_TYPES (type);
5686            t && t != void_list_node;
5687            t = TREE_CHAIN (t))
5688         if (variably_modified_type_p (TREE_VALUE (t), fn))
5689           return true;
5690       break;
5691
5692     case INTEGER_TYPE:
5693     case REAL_TYPE:
5694     case ENUMERAL_TYPE:
5695     case BOOLEAN_TYPE:
5696     case CHAR_TYPE:
5697       /* Scalar types are variably modified if their end points
5698          aren't constant.  */
5699       RETURN_TRUE_IF_VAR (TYPE_MIN_VALUE (type));
5700       RETURN_TRUE_IF_VAR (TYPE_MAX_VALUE (type));
5701       break;
5702
5703     case RECORD_TYPE:
5704     case UNION_TYPE:
5705     case QUAL_UNION_TYPE:
5706       /* We can't see if any of the field are variably-modified by the
5707          definition we normally use, since that would produce infinite
5708          recursion via pointers.  */
5709       /* This is variably modified if some field's type is.  */
5710       for (t = TYPE_FIELDS (type); t; t = TREE_CHAIN (t))
5711         if (TREE_CODE (t) == FIELD_DECL)
5712           {
5713             RETURN_TRUE_IF_VAR (DECL_FIELD_OFFSET (t));
5714             RETURN_TRUE_IF_VAR (DECL_SIZE (t));
5715             RETURN_TRUE_IF_VAR (DECL_SIZE_UNIT (t));
5716
5717             if (TREE_CODE (type) == QUAL_UNION_TYPE)
5718               RETURN_TRUE_IF_VAR (DECL_QUALIFIER (t));
5719           }
5720         break;
5721
5722     default:
5723       break;
5724     }
5725
5726   /* The current language may have other cases to check, but in general,
5727      all other types are not variably modified.  */
5728   return lang_hooks.tree_inlining.var_mod_type_p (type, fn);
5729
5730 #undef RETURN_TRUE_IF_VAR
5731 }
5732
5733 /* Given a DECL or TYPE, return the scope in which it was declared, or
5734    NULL_TREE if there is no containing scope.  */
5735
5736 tree
5737 get_containing_scope (tree t)
5738 {
5739   return (TYPE_P (t) ? TYPE_CONTEXT (t) : DECL_CONTEXT (t));
5740 }
5741
5742 /* Return the innermost context enclosing DECL that is
5743    a FUNCTION_DECL, or zero if none.  */
5744
5745 tree
5746 decl_function_context (tree decl)
5747 {
5748   tree context;
5749
5750   if (TREE_CODE (decl) == ERROR_MARK)
5751     return 0;
5752
5753   /* C++ virtual functions use DECL_CONTEXT for the class of the vtable
5754      where we look up the function at runtime.  Such functions always take
5755      a first argument of type 'pointer to real context'.
5756
5757      C++ should really be fixed to use DECL_CONTEXT for the real context,
5758      and use something else for the "virtual context".  */
5759   else if (TREE_CODE (decl) == FUNCTION_DECL && DECL_VINDEX (decl))
5760     context
5761       = TYPE_MAIN_VARIANT
5762         (TREE_TYPE (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (decl)))));
5763   else
5764     context = DECL_CONTEXT (decl);
5765
5766   while (context && TREE_CODE (context) != FUNCTION_DECL)
5767     {
5768       if (TREE_CODE (context) == BLOCK)
5769         context = BLOCK_SUPERCONTEXT (context);
5770       else
5771         context = get_containing_scope (context);
5772     }
5773
5774   return context;
5775 }
5776
5777 /* Return the innermost context enclosing DECL that is
5778    a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE, or zero if none.
5779    TYPE_DECLs and FUNCTION_DECLs are transparent to this function.  */
5780
5781 tree
5782 decl_type_context (tree decl)
5783 {
5784   tree context = DECL_CONTEXT (decl);
5785
5786   while (context)
5787     switch (TREE_CODE (context))
5788       {
5789       case NAMESPACE_DECL:
5790       case TRANSLATION_UNIT_DECL:
5791         return NULL_TREE;
5792
5793       case RECORD_TYPE:
5794       case UNION_TYPE:
5795       case QUAL_UNION_TYPE:
5796         return context;
5797
5798       case TYPE_DECL:
5799       case FUNCTION_DECL:
5800         context = DECL_CONTEXT (context);
5801         break;
5802
5803       case BLOCK:
5804         context = BLOCK_SUPERCONTEXT (context);
5805         break;
5806
5807       default:
5808         gcc_unreachable ();
5809       }
5810
5811   return NULL_TREE;
5812 }
5813
5814 /* CALL is a CALL_EXPR.  Return the declaration for the function
5815    called, or NULL_TREE if the called function cannot be
5816    determined.  */
5817
5818 tree
5819 get_callee_fndecl (tree call)
5820 {
5821   tree addr;
5822
5823   /* It's invalid to call this function with anything but a
5824      CALL_EXPR.  */
5825   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5826
5827   /* The first operand to the CALL is the address of the function
5828      called.  */
5829   addr = TREE_OPERAND (call, 0);
5830
5831   STRIP_NOPS (addr);
5832
5833   /* If this is a readonly function pointer, extract its initial value.  */
5834   if (DECL_P (addr) && TREE_CODE (addr) != FUNCTION_DECL
5835       && TREE_READONLY (addr) && ! TREE_THIS_VOLATILE (addr)
5836       && DECL_INITIAL (addr))
5837     addr = DECL_INITIAL (addr);
5838
5839   /* If the address is just `&f' for some function `f', then we know
5840      that `f' is being called.  */
5841   if (TREE_CODE (addr) == ADDR_EXPR
5842       && TREE_CODE (TREE_OPERAND (addr, 0)) == FUNCTION_DECL)
5843     return TREE_OPERAND (addr, 0);
5844
5845   /* We couldn't figure out what was being called.  Maybe the front
5846      end has some idea.  */
5847   return lang_hooks.lang_get_callee_fndecl (call);
5848 }
5849
5850 /* Print debugging information about tree nodes generated during the compile,
5851    and any language-specific information.  */
5852
5853 void
5854 dump_tree_statistics (void)
5855 {
5856 #ifdef GATHER_STATISTICS
5857   int i;
5858   int total_nodes, total_bytes;
5859 #endif
5860
5861   fprintf (stderr, "\n??? tree nodes created\n\n");
5862 #ifdef GATHER_STATISTICS
5863   fprintf (stderr, "Kind                   Nodes      Bytes\n");
5864   fprintf (stderr, "---------------------------------------\n");
5865   total_nodes = total_bytes = 0;
5866   for (i = 0; i < (int) all_kinds; i++)
5867     {
5868       fprintf (stderr, "%-20s %7d %10d\n", tree_node_kind_names[i],
5869                tree_node_counts[i], tree_node_sizes[i]);
5870       total_nodes += tree_node_counts[i];
5871       total_bytes += tree_node_sizes[i];
5872     }
5873   fprintf (stderr, "---------------------------------------\n");
5874   fprintf (stderr, "%-20s %7d %10d\n", "Total", total_nodes, total_bytes);
5875   fprintf (stderr, "---------------------------------------\n");
5876   ssanames_print_statistics ();
5877   phinodes_print_statistics ();
5878 #else
5879   fprintf (stderr, "(No per-node statistics)\n");
5880 #endif
5881   print_type_hash_statistics ();
5882   print_debug_expr_statistics ();
5883   print_value_expr_statistics ();
5884   print_restrict_base_statistics ();
5885   lang_hooks.print_statistics ();
5886 }
5887 \f
5888 #define FILE_FUNCTION_FORMAT "_GLOBAL__%s_%s"
5889
5890 /* Generate a crc32 of a string.  */
5891
5892 unsigned
5893 crc32_string (unsigned chksum, const char *string)
5894 {
5895   do
5896     {
5897       unsigned value = *string << 24;
5898       unsigned ix;
5899
5900       for (ix = 8; ix--; value <<= 1)
5901         {
5902           unsigned feedback;
5903
5904           feedback = (value ^ chksum) & 0x80000000 ? 0x04c11db7 : 0;
5905           chksum <<= 1;
5906           chksum ^= feedback;
5907         }
5908     }
5909   while (*string++);
5910   return chksum;
5911 }
5912
5913 /* P is a string that will be used in a symbol.  Mask out any characters
5914    that are not valid in that context.  */
5915
5916 void
5917 clean_symbol_name (char *p)
5918 {
5919   for (; *p; p++)
5920     if (! (ISALNUM (*p)
5921 #ifndef NO_DOLLAR_IN_LABEL      /* this for `$'; unlikely, but... -- kr */
5922             || *p == '$'
5923 #endif
5924 #ifndef NO_DOT_IN_LABEL         /* this for `.'; unlikely, but...  */
5925             || *p == '.'
5926 #endif
5927            ))
5928       *p = '_';
5929 }
5930
5931 /* Generate a name for a function unique to this translation unit.
5932    TYPE is some string to identify the purpose of this function to the
5933    linker or collect2.  */
5934
5935 tree
5936 get_file_function_name_long (const char *type)
5937 {
5938   char *buf;
5939   const char *p;
5940   char *q;
5941
5942   if (first_global_object_name)
5943     {
5944       p = first_global_object_name;
5945
5946       /* For type 'F', the generated name must be unique not only to this
5947          translation unit but also to any given link.  Since global names
5948          can be overloaded, we concatenate the first global object name
5949          with a string derived from the file name of this object.  */
5950       if (!strcmp (type, "F"))
5951         {
5952           const char *file = main_input_filename;
5953
5954           if (! file)
5955             file = input_filename;
5956
5957           q = alloca (strlen (p) + 10);
5958           sprintf (q, "%s_%08X", p, crc32_string (0, file));
5959
5960           p = q;
5961         }
5962     }
5963   else
5964     {
5965       /* We don't have anything that we know to be unique to this translation
5966          unit, so use what we do have and throw in some randomness.  */
5967       unsigned len;
5968       const char *name = weak_global_object_name;
5969       const char *file = main_input_filename;
5970
5971       if (! name)
5972         name = "";
5973       if (! file)
5974         file = input_filename;
5975
5976       len = strlen (file);
5977       q = alloca (9 * 2 + len + 1);
5978       memcpy (q, file, len + 1);
5979       clean_symbol_name (q);
5980
5981       sprintf (q + len, "_%08X_%08X", crc32_string (0, name),
5982                crc32_string (0, flag_random_seed));
5983
5984       p = q;
5985     }
5986
5987   buf = alloca (sizeof (FILE_FUNCTION_FORMAT) + strlen (p) + strlen (type));
5988
5989   /* Set up the name of the file-level functions we may need.
5990      Use a global object (which is already required to be unique over
5991      the program) rather than the file name (which imposes extra
5992      constraints).  */
5993   sprintf (buf, FILE_FUNCTION_FORMAT, type, p);
5994
5995   return get_identifier (buf);
5996 }
5997
5998 /* If KIND=='I', return a suitable global initializer (constructor) name.
5999    If KIND=='D', return a suitable global clean-up (destructor) name.  */
6000
6001 tree
6002 get_file_function_name (int kind)
6003 {
6004   char p[2];
6005
6006   p[0] = kind;
6007   p[1] = 0;
6008
6009   return get_file_function_name_long (p);
6010 }
6011 \f
6012 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
6013
6014 /* Complain that the tree code of NODE does not match the expected 0
6015    terminated list of trailing codes. The trailing code list can be
6016    empty, for a more vague error message.  FILE, LINE, and FUNCTION
6017    are of the caller.  */
6018
6019 void
6020 tree_check_failed (const tree node, const char *file,
6021                    int line, const char *function, ...)
6022 {
6023   va_list args;
6024   char *buffer;
6025   unsigned length = 0;
6026   int code;
6027
6028   va_start (args, function);
6029   while ((code = va_arg (args, int)))
6030     length += 4 + strlen (tree_code_name[code]);
6031   va_end (args);
6032   if (length)
6033     {
6034       va_start (args, function);
6035       length += strlen ("expected ");
6036       buffer = alloca (length);
6037       length = 0;
6038       while ((code = va_arg (args, int)))
6039         {
6040           const char *prefix = length ? " or " : "expected ";
6041
6042           strcpy (buffer + length, prefix);
6043           length += strlen (prefix);
6044           strcpy (buffer + length, tree_code_name[code]);
6045           length += strlen (tree_code_name[code]);
6046         }
6047       va_end (args);
6048     }
6049   else
6050     buffer = (char *)"unexpected node";
6051
6052   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6053                   buffer, tree_code_name[TREE_CODE (node)],
6054                   function, trim_filename (file), line);
6055 }
6056
6057 /* Complain that the tree code of NODE does match the expected 0
6058    terminated list of trailing codes. FILE, LINE, and FUNCTION are of
6059    the caller.  */
6060
6061 void
6062 tree_not_check_failed (const tree node, const char *file,
6063                        int line, const char *function, ...)
6064 {
6065   va_list args;
6066   char *buffer;
6067   unsigned length = 0;
6068   int code;
6069
6070   va_start (args, function);
6071   while ((code = va_arg (args, int)))
6072     length += 4 + strlen (tree_code_name[code]);
6073   va_end (args);
6074   va_start (args, function);
6075   buffer = alloca (length);
6076   length = 0;
6077   while ((code = va_arg (args, int)))
6078     {
6079       if (length)
6080         {
6081           strcpy (buffer + length, " or ");
6082           length += 4;
6083         }
6084       strcpy (buffer + length, tree_code_name[code]);
6085       length += strlen (tree_code_name[code]);
6086     }
6087   va_end (args);
6088
6089   internal_error ("tree check: expected none of %s, have %s in %s, at %s:%d",
6090                   buffer, tree_code_name[TREE_CODE (node)],
6091                   function, trim_filename (file), line);
6092 }
6093
6094 /* Similar to tree_check_failed, except that we check for a class of tree
6095    code, given in CL.  */
6096
6097 void
6098 tree_class_check_failed (const tree node, const enum tree_code_class cl,
6099                          const char *file, int line, const char *function)
6100 {
6101   internal_error
6102     ("tree check: expected class %qs, have %qs (%s) in %s, at %s:%d",
6103      TREE_CODE_CLASS_STRING (cl),
6104      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6105      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6106 }
6107
6108 /* Similar to tree_check_failed, except that instead of specifying a
6109    dozen codes, use the knowledge that they're all sequential.  */
6110
6111 void
6112 tree_range_check_failed (const tree node, const char *file, int line,
6113                          const char *function, enum tree_code c1,
6114                          enum tree_code c2)
6115 {
6116   char *buffer;
6117   unsigned length = 0;
6118   enum tree_code c;
6119
6120   for (c = c1; c <= c2; ++c)
6121     length += 4 + strlen (tree_code_name[c]);
6122
6123   length += strlen ("expected ");
6124   buffer = alloca (length);
6125   length = 0;
6126
6127   for (c = c1; c <= c2; ++c)
6128     {
6129       const char *prefix = length ? " or " : "expected ";
6130
6131       strcpy (buffer + length, prefix);
6132       length += strlen (prefix);
6133       strcpy (buffer + length, tree_code_name[c]);
6134       length += strlen (tree_code_name[c]);
6135     }
6136
6137   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6138                   buffer, tree_code_name[TREE_CODE (node)],
6139                   function, trim_filename (file), line);
6140 }
6141
6142
6143 /* Similar to tree_check_failed, except that we check that a tree does
6144    not have the specified code, given in CL.  */
6145
6146 void
6147 tree_not_class_check_failed (const tree node, const enum tree_code_class cl,
6148                              const char *file, int line, const char *function)
6149 {
6150   internal_error
6151     ("tree check: did not expect class %qs, have %qs (%s) in %s, at %s:%d",
6152      TREE_CODE_CLASS_STRING (cl),
6153      TREE_CODE_CLASS_STRING (TREE_CODE_CLASS (TREE_CODE (node))),
6154      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6155 }
6156
6157
6158 /* Similar to tree_check_failed but applied to OMP_CLAUSE codes.  */
6159
6160 void
6161 omp_clause_check_failed (const tree node, const char *file, int line,
6162                          const char *function, enum omp_clause_code code)
6163 {
6164   internal_error ("tree check: expected omp_clause %s, have %s in %s, at %s:%d",
6165                   omp_clause_code_name[code], tree_code_name[TREE_CODE (node)],
6166                   function, trim_filename (file), line);
6167 }
6168
6169
6170 /* Similar to tree_range_check_failed but applied to OMP_CLAUSE codes.  */
6171
6172 void
6173 omp_clause_range_check_failed (const tree node, const char *file, int line,
6174                                const char *function, enum omp_clause_code c1,
6175                                enum omp_clause_code c2)
6176 {
6177   char *buffer;
6178   unsigned length = 0;
6179   enum omp_clause_code c;
6180
6181   for (c = c1; c <= c2; ++c)
6182     length += 4 + strlen (omp_clause_code_name[c]);
6183
6184   length += strlen ("expected ");
6185   buffer = alloca (length);
6186   length = 0;
6187
6188   for (c = c1; c <= c2; ++c)
6189     {
6190       const char *prefix = length ? " or " : "expected ";
6191
6192       strcpy (buffer + length, prefix);
6193       length += strlen (prefix);
6194       strcpy (buffer + length, omp_clause_code_name[c]);
6195       length += strlen (omp_clause_code_name[c]);
6196     }
6197
6198   internal_error ("tree check: %s, have %s in %s, at %s:%d",
6199                   buffer, omp_clause_code_name[TREE_CODE (node)],
6200                   function, trim_filename (file), line);
6201 }
6202
6203
6204 #undef DEFTREESTRUCT
6205 #define DEFTREESTRUCT(VAL, NAME) NAME,
6206
6207 static const char *ts_enum_names[] = {
6208 #include "treestruct.def"
6209 };
6210 #undef DEFTREESTRUCT
6211
6212 #define TS_ENUM_NAME(EN) (ts_enum_names[(EN)])
6213
6214 /* Similar to tree_class_check_failed, except that we check for
6215    whether CODE contains the tree structure identified by EN.  */
6216
6217 void
6218 tree_contains_struct_check_failed (const tree node,
6219                                    const enum tree_node_structure_enum en,
6220                                    const char *file, int line,
6221                                    const char *function)
6222 {
6223   internal_error
6224     ("tree check: expected tree that contains %qs structure, have %qs  in %s, at %s:%d",
6225      TS_ENUM_NAME(en),
6226      tree_code_name[TREE_CODE (node)], function, trim_filename (file), line);
6227 }
6228
6229
6230 /* Similar to above, except that the check is for the bounds of a TREE_VEC's
6231    (dynamically sized) vector.  */
6232
6233 void
6234 tree_vec_elt_check_failed (int idx, int len, const char *file, int line,
6235                            const char *function)
6236 {
6237   internal_error
6238     ("tree check: accessed elt %d of tree_vec with %d elts in %s, at %s:%d",
6239      idx + 1, len, function, trim_filename (file), line);
6240 }
6241
6242 /* Similar to above, except that the check is for the bounds of a PHI_NODE's
6243    (dynamically sized) vector.  */
6244
6245 void
6246 phi_node_elt_check_failed (int idx, int len, const char *file, int line,
6247                             const char *function)
6248 {
6249   internal_error
6250     ("tree check: accessed elt %d of phi_node with %d elts in %s, at %s:%d",
6251      idx + 1, len, function, trim_filename (file), line);
6252 }
6253
6254 /* Similar to above, except that the check is for the bounds of the operand
6255    vector of an expression node.  */
6256
6257 void
6258 tree_operand_check_failed (int idx, enum tree_code code, const char *file,
6259                            int line, const char *function)
6260 {
6261   internal_error
6262     ("tree check: accessed operand %d of %s with %d operands in %s, at %s:%d",
6263      idx + 1, tree_code_name[code], TREE_CODE_LENGTH (code),
6264      function, trim_filename (file), line);
6265 }
6266
6267 /* Similar to above, except that the check is for the number of
6268    operands of an OMP_CLAUSE node.  */
6269
6270 void
6271 omp_clause_operand_check_failed (int idx, tree t, const char *file,
6272                                  int line, const char *function)
6273 {
6274   internal_error
6275     ("tree check: accessed operand %d of omp_clause %s with %d operands "
6276      "in %s, at %s:%d", idx + 1, omp_clause_code_name[OMP_CLAUSE_CODE (t)],
6277      omp_clause_num_ops [OMP_CLAUSE_CODE (t)], function,
6278      trim_filename (file), line);
6279 }
6280 #endif /* ENABLE_TREE_CHECKING */
6281 \f
6282 /* Create a new vector type node holding SUBPARTS units of type INNERTYPE,
6283    and mapped to the machine mode MODE.  Initialize its fields and build
6284    the information necessary for debugging output.  */
6285
6286 static tree
6287 make_vector_type (tree innertype, int nunits, enum machine_mode mode)
6288 {
6289   tree t = make_node (VECTOR_TYPE);
6290
6291   TREE_TYPE (t) = TYPE_MAIN_VARIANT (innertype);
6292   SET_TYPE_VECTOR_SUBPARTS (t, nunits);
6293   TYPE_MODE (t) = mode;
6294   TYPE_READONLY (t) = TYPE_READONLY (innertype);
6295   TYPE_VOLATILE (t) = TYPE_VOLATILE (innertype);
6296
6297   layout_type (t);
6298
6299   {
6300     tree index = build_int_cst (NULL_TREE, nunits - 1);
6301     tree array = build_array_type (innertype, build_index_type (index));
6302     tree rt = make_node (RECORD_TYPE);
6303
6304     TYPE_FIELDS (rt) = build_decl (FIELD_DECL, get_identifier ("f"), array);
6305     DECL_CONTEXT (TYPE_FIELDS (rt)) = rt;
6306     layout_type (rt);
6307     TYPE_DEBUG_REPRESENTATION_TYPE (t) = rt;
6308     /* In dwarfout.c, type lookup uses TYPE_UID numbers.  We want to output
6309        the representation type, and we want to find that die when looking up
6310        the vector type.  This is most easily achieved by making the TYPE_UID
6311        numbers equal.  */
6312     TYPE_UID (rt) = TYPE_UID (t);
6313   }
6314
6315   /* Build our main variant, based on the main variant of the inner type.  */
6316   if (TYPE_MAIN_VARIANT (innertype) != innertype)
6317     {
6318       tree innertype_main_variant = TYPE_MAIN_VARIANT (innertype);
6319       unsigned int hash = TYPE_HASH (innertype_main_variant);
6320       TYPE_MAIN_VARIANT (t)
6321         = type_hash_canon (hash, make_vector_type (innertype_main_variant,
6322                                                    nunits, mode));
6323     }
6324
6325   return t;
6326 }
6327
6328 static tree
6329 make_or_reuse_type (unsigned size, int unsignedp)
6330 {
6331   if (size == INT_TYPE_SIZE)
6332     return unsignedp ? unsigned_type_node : integer_type_node;
6333   if (size == CHAR_TYPE_SIZE)
6334     return unsignedp ? unsigned_char_type_node : signed_char_type_node;
6335   if (size == SHORT_TYPE_SIZE)
6336     return unsignedp ? short_unsigned_type_node : short_integer_type_node;
6337   if (size == LONG_TYPE_SIZE)
6338     return unsignedp ? long_unsigned_type_node : long_integer_type_node;
6339   if (size == LONG_LONG_TYPE_SIZE)
6340     return (unsignedp ? long_long_unsigned_type_node
6341             : long_long_integer_type_node);
6342
6343   if (unsignedp)
6344     return make_unsigned_type (size);
6345   else
6346     return make_signed_type (size);
6347 }
6348
6349 /* Create nodes for all integer types (and error_mark_node) using the sizes
6350    of C datatypes.  The caller should call set_sizetype soon after calling
6351    this function to select one of the types as sizetype.  */
6352
6353 void
6354 build_common_tree_nodes (bool signed_char, bool signed_sizetype)
6355 {
6356   error_mark_node = make_node (ERROR_MARK);
6357   TREE_TYPE (error_mark_node) = error_mark_node;
6358
6359   initialize_sizetypes (signed_sizetype);
6360
6361   /* Define both `signed char' and `unsigned char'.  */
6362   signed_char_type_node = make_signed_type (CHAR_TYPE_SIZE);
6363   unsigned_char_type_node = make_unsigned_type (CHAR_TYPE_SIZE);
6364
6365   /* Define `char', which is like either `signed char' or `unsigned char'
6366      but not the same as either.  */
6367   char_type_node
6368     = (signed_char
6369        ? make_signed_type (CHAR_TYPE_SIZE)
6370        : make_unsigned_type (CHAR_TYPE_SIZE));
6371
6372   short_integer_type_node = make_signed_type (SHORT_TYPE_SIZE);
6373   short_unsigned_type_node = make_unsigned_type (SHORT_TYPE_SIZE);
6374   integer_type_node = make_signed_type (INT_TYPE_SIZE);
6375   unsigned_type_node = make_unsigned_type (INT_TYPE_SIZE);
6376   long_integer_type_node = make_signed_type (LONG_TYPE_SIZE);
6377   long_unsigned_type_node = make_unsigned_type (LONG_TYPE_SIZE);
6378   long_long_integer_type_node = make_signed_type (LONG_LONG_TYPE_SIZE);
6379   long_long_unsigned_type_node = make_unsigned_type (LONG_LONG_TYPE_SIZE);
6380
6381   /* Define a boolean type.  This type only represents boolean values but
6382      may be larger than char depending on the value of BOOL_TYPE_SIZE.
6383      Front ends which want to override this size (i.e. Java) can redefine
6384      boolean_type_node before calling build_common_tree_nodes_2.  */
6385   boolean_type_node = make_unsigned_type (BOOL_TYPE_SIZE);
6386   TREE_SET_CODE (boolean_type_node, BOOLEAN_TYPE);
6387   TYPE_MAX_VALUE (boolean_type_node) = build_int_cst (boolean_type_node, 1);
6388   TYPE_PRECISION (boolean_type_node) = 1;
6389
6390   /* Fill in the rest of the sized types.  Reuse existing type nodes
6391      when possible.  */
6392   intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 0);
6393   intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 0);
6394   intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 0);
6395   intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 0);
6396   intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 0);
6397
6398   unsigned_intQI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (QImode), 1);
6399   unsigned_intHI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (HImode), 1);
6400   unsigned_intSI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (SImode), 1);
6401   unsigned_intDI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (DImode), 1);
6402   unsigned_intTI_type_node = make_or_reuse_type (GET_MODE_BITSIZE (TImode), 1);
6403
6404   access_public_node = get_identifier ("public");
6405   access_protected_node = get_identifier ("protected");
6406   access_private_node = get_identifier ("private");
6407 }
6408
6409 /* Call this function after calling build_common_tree_nodes and set_sizetype.
6410    It will create several other common tree nodes.  */
6411
6412 void
6413 build_common_tree_nodes_2 (int short_double)
6414 {
6415   /* Define these next since types below may used them.  */
6416   integer_zero_node = build_int_cst (NULL_TREE, 0);
6417   integer_one_node = build_int_cst (NULL_TREE, 1);
6418   integer_minus_one_node = build_int_cst (NULL_TREE, -1);
6419
6420   size_zero_node = size_int (0);
6421   size_one_node = size_int (1);
6422   bitsize_zero_node = bitsize_int (0);
6423   bitsize_one_node = bitsize_int (1);
6424   bitsize_unit_node = bitsize_int (BITS_PER_UNIT);
6425
6426   boolean_false_node = TYPE_MIN_VALUE (boolean_type_node);
6427   boolean_true_node = TYPE_MAX_VALUE (boolean_type_node);
6428
6429   void_type_node = make_node (VOID_TYPE);
6430   layout_type (void_type_node);
6431
6432   /* We are not going to have real types in C with less than byte alignment,
6433      so we might as well not have any types that claim to have it.  */
6434   TYPE_ALIGN (void_type_node) = BITS_PER_UNIT;
6435   TYPE_USER_ALIGN (void_type_node) = 0;
6436
6437   null_pointer_node = build_int_cst (build_pointer_type (void_type_node), 0);
6438   layout_type (TREE_TYPE (null_pointer_node));
6439
6440   ptr_type_node = build_pointer_type (void_type_node);
6441   const_ptr_type_node
6442     = build_pointer_type (build_type_variant (void_type_node, 1, 0));
6443   fileptr_type_node = ptr_type_node;
6444
6445   float_type_node = make_node (REAL_TYPE);
6446   TYPE_PRECISION (float_type_node) = FLOAT_TYPE_SIZE;
6447   layout_type (float_type_node);
6448
6449   double_type_node = make_node (REAL_TYPE);
6450   if (short_double)
6451     TYPE_PRECISION (double_type_node) = FLOAT_TYPE_SIZE;
6452   else
6453     TYPE_PRECISION (double_type_node) = DOUBLE_TYPE_SIZE;
6454   layout_type (double_type_node);
6455
6456   long_double_type_node = make_node (REAL_TYPE);
6457   TYPE_PRECISION (long_double_type_node) = LONG_DOUBLE_TYPE_SIZE;
6458   layout_type (long_double_type_node);
6459
6460   float_ptr_type_node = build_pointer_type (float_type_node);
6461   double_ptr_type_node = build_pointer_type (double_type_node);
6462   long_double_ptr_type_node = build_pointer_type (long_double_type_node);
6463   integer_ptr_type_node = build_pointer_type (integer_type_node);
6464
6465   /* Decimal float types. */
6466   dfloat32_type_node = make_node (REAL_TYPE);
6467   TYPE_PRECISION (dfloat32_type_node) = DECIMAL32_TYPE_SIZE;
6468   layout_type (dfloat32_type_node);
6469   TYPE_MODE (dfloat32_type_node) = SDmode;
6470   dfloat32_ptr_type_node = build_pointer_type (dfloat32_type_node);
6471
6472   dfloat64_type_node = make_node (REAL_TYPE);
6473   TYPE_PRECISION (dfloat64_type_node) = DECIMAL64_TYPE_SIZE;
6474   layout_type (dfloat64_type_node);
6475   TYPE_MODE (dfloat64_type_node) = DDmode;
6476   dfloat64_ptr_type_node = build_pointer_type (dfloat64_type_node);
6477
6478   dfloat128_type_node = make_node (REAL_TYPE);
6479   TYPE_PRECISION (dfloat128_type_node) = DECIMAL128_TYPE_SIZE;
6480   layout_type (dfloat128_type_node);
6481   TYPE_MODE (dfloat128_type_node) = TDmode;
6482   dfloat128_ptr_type_node = build_pointer_type (dfloat128_type_node);
6483
6484   complex_integer_type_node = make_node (COMPLEX_TYPE);
6485   TREE_TYPE (complex_integer_type_node) = integer_type_node;
6486   layout_type (complex_integer_type_node);
6487
6488   complex_float_type_node = make_node (COMPLEX_TYPE);
6489   TREE_TYPE (complex_float_type_node) = float_type_node;
6490   layout_type (complex_float_type_node);
6491
6492   complex_double_type_node = make_node (COMPLEX_TYPE);
6493   TREE_TYPE (complex_double_type_node) = double_type_node;
6494   layout_type (complex_double_type_node);
6495
6496   complex_long_double_type_node = make_node (COMPLEX_TYPE);
6497   TREE_TYPE (complex_long_double_type_node) = long_double_type_node;
6498   layout_type (complex_long_double_type_node);
6499
6500   {
6501     tree t = targetm.build_builtin_va_list ();
6502
6503     /* Many back-ends define record types without setting TYPE_NAME.
6504        If we copied the record type here, we'd keep the original
6505        record type without a name.  This breaks name mangling.  So,
6506        don't copy record types and let c_common_nodes_and_builtins()
6507        declare the type to be __builtin_va_list.  */
6508     if (TREE_CODE (t) != RECORD_TYPE)
6509       t = build_variant_type_copy (t);
6510
6511     va_list_type_node = t;
6512   }
6513 }
6514
6515 /* A subroutine of build_common_builtin_nodes.  Define a builtin function.  */
6516
6517 static void
6518 local_define_builtin (const char *name, tree type, enum built_in_function code,
6519                       const char *library_name, int ecf_flags)
6520 {
6521   tree decl;
6522
6523   decl = lang_hooks.builtin_function (name, type, code, BUILT_IN_NORMAL,
6524                                       library_name, NULL_TREE);
6525   if (ecf_flags & ECF_CONST)
6526     TREE_READONLY (decl) = 1;
6527   if (ecf_flags & ECF_PURE)
6528     DECL_IS_PURE (decl) = 1;
6529   if (ecf_flags & ECF_NORETURN)
6530     TREE_THIS_VOLATILE (decl) = 1;
6531   if (ecf_flags & ECF_NOTHROW)
6532     TREE_NOTHROW (decl) = 1;
6533   if (ecf_flags & ECF_MALLOC)
6534     DECL_IS_MALLOC (decl) = 1;
6535
6536   built_in_decls[code] = decl;
6537   implicit_built_in_decls[code] = decl;
6538 }
6539
6540 /* Call this function after instantiating all builtins that the language
6541    front end cares about.  This will build the rest of the builtins that
6542    are relied upon by the tree optimizers and the middle-end.  */
6543
6544 void
6545 build_common_builtin_nodes (void)
6546 {
6547   tree tmp, ftype;
6548
6549   if (built_in_decls[BUILT_IN_MEMCPY] == NULL
6550       || built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6551     {
6552       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6553       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6554       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6555       ftype = build_function_type (ptr_type_node, tmp);
6556
6557       if (built_in_decls[BUILT_IN_MEMCPY] == NULL)
6558         local_define_builtin ("__builtin_memcpy", ftype, BUILT_IN_MEMCPY,
6559                               "memcpy", ECF_NOTHROW);
6560       if (built_in_decls[BUILT_IN_MEMMOVE] == NULL)
6561         local_define_builtin ("__builtin_memmove", ftype, BUILT_IN_MEMMOVE,
6562                               "memmove", ECF_NOTHROW);
6563     }
6564
6565   if (built_in_decls[BUILT_IN_MEMCMP] == NULL)
6566     {
6567       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6568       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6569       tmp = tree_cons (NULL_TREE, const_ptr_type_node, tmp);
6570       ftype = build_function_type (integer_type_node, tmp);
6571       local_define_builtin ("__builtin_memcmp", ftype, BUILT_IN_MEMCMP,
6572                             "memcmp", ECF_PURE | ECF_NOTHROW);
6573     }
6574
6575   if (built_in_decls[BUILT_IN_MEMSET] == NULL)
6576     {
6577       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6578       tmp = tree_cons (NULL_TREE, integer_type_node, tmp);
6579       tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6580       ftype = build_function_type (ptr_type_node, tmp);
6581       local_define_builtin ("__builtin_memset", ftype, BUILT_IN_MEMSET,
6582                             "memset", ECF_NOTHROW);
6583     }
6584
6585   if (built_in_decls[BUILT_IN_ALLOCA] == NULL)
6586     {
6587       tmp = tree_cons (NULL_TREE, size_type_node, void_list_node);
6588       ftype = build_function_type (ptr_type_node, tmp);
6589       local_define_builtin ("__builtin_alloca", ftype, BUILT_IN_ALLOCA,
6590                             "alloca", ECF_NOTHROW | ECF_MALLOC);
6591     }
6592
6593   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6594   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6595   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6596   ftype = build_function_type (void_type_node, tmp);
6597   local_define_builtin ("__builtin_init_trampoline", ftype,
6598                         BUILT_IN_INIT_TRAMPOLINE,
6599                         "__builtin_init_trampoline", ECF_NOTHROW);
6600
6601   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6602   ftype = build_function_type (ptr_type_node, tmp);
6603   local_define_builtin ("__builtin_adjust_trampoline", ftype,
6604                         BUILT_IN_ADJUST_TRAMPOLINE,
6605                         "__builtin_adjust_trampoline",
6606                         ECF_CONST | ECF_NOTHROW);
6607
6608   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6609   tmp = tree_cons (NULL_TREE, ptr_type_node, tmp);
6610   ftype = build_function_type (void_type_node, tmp);
6611   local_define_builtin ("__builtin_nonlocal_goto", ftype,
6612                         BUILT_IN_NONLOCAL_GOTO,
6613                         "__builtin_nonlocal_goto",
6614                         ECF_NORETURN | ECF_NOTHROW);
6615
6616   ftype = build_function_type (ptr_type_node, void_list_node);
6617   local_define_builtin ("__builtin_stack_save", ftype, BUILT_IN_STACK_SAVE,
6618                         "__builtin_stack_save", ECF_NOTHROW);
6619
6620   tmp = tree_cons (NULL_TREE, ptr_type_node, void_list_node);
6621   ftype = build_function_type (void_type_node, tmp);
6622   local_define_builtin ("__builtin_stack_restore", ftype,
6623                         BUILT_IN_STACK_RESTORE,
6624                         "__builtin_stack_restore", ECF_NOTHROW);
6625
6626   ftype = build_function_type (void_type_node, void_list_node);
6627   local_define_builtin ("__builtin_profile_func_enter", ftype,
6628                         BUILT_IN_PROFILE_FUNC_ENTER, "profile_func_enter", 0);
6629   local_define_builtin ("__builtin_profile_func_exit", ftype,
6630                         BUILT_IN_PROFILE_FUNC_EXIT, "profile_func_exit", 0);
6631
6632   /* Complex multiplication and division.  These are handled as builtins
6633      rather than optabs because emit_library_call_value doesn't support
6634      complex.  Further, we can do slightly better with folding these
6635      beasties if the real and complex parts of the arguments are separate.  */
6636   {
6637     enum machine_mode mode;
6638
6639     for (mode = MIN_MODE_COMPLEX_FLOAT; mode <= MAX_MODE_COMPLEX_FLOAT; ++mode)
6640       {
6641         char mode_name_buf[4], *q;
6642         const char *p;
6643         enum built_in_function mcode, dcode;
6644         tree type, inner_type;
6645
6646         type = lang_hooks.types.type_for_mode (mode, 0);
6647         if (type == NULL)
6648           continue;
6649         inner_type = TREE_TYPE (type);
6650
6651         tmp = tree_cons (NULL_TREE, inner_type, void_list_node);
6652         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6653         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6654         tmp = tree_cons (NULL_TREE, inner_type, tmp);
6655         ftype = build_function_type (type, tmp);
6656
6657         mcode = BUILT_IN_COMPLEX_MUL_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6658         dcode = BUILT_IN_COMPLEX_DIV_MIN + mode - MIN_MODE_COMPLEX_FLOAT;
6659
6660         for (p = GET_MODE_NAME (mode), q = mode_name_buf; *p; p++, q++)
6661           *q = TOLOWER (*p);
6662         *q = '\0';
6663
6664         built_in_names[mcode] = concat ("__mul", mode_name_buf, "3", NULL);
6665         local_define_builtin (built_in_names[mcode], ftype, mcode,
6666                               built_in_names[mcode], ECF_CONST | ECF_NOTHROW);
6667
6668         built_in_names[dcode] = concat ("__div", mode_name_buf, "3", NULL);
6669         local_define_builtin (built_in_names[dcode], ftype, dcode,
6670                               built_in_names[dcode], ECF_CONST | ECF_NOTHROW);
6671       }
6672   }
6673 }
6674
6675 /* HACK.  GROSS.  This is absolutely disgusting.  I wish there was a
6676    better way.
6677
6678    If we requested a pointer to a vector, build up the pointers that
6679    we stripped off while looking for the inner type.  Similarly for
6680    return values from functions.
6681
6682    The argument TYPE is the top of the chain, and BOTTOM is the
6683    new type which we will point to.  */
6684
6685 tree
6686 reconstruct_complex_type (tree type, tree bottom)
6687 {
6688   tree inner, outer;
6689
6690   if (POINTER_TYPE_P (type))
6691     {
6692       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6693       outer = build_pointer_type (inner);
6694     }
6695   else if (TREE_CODE (type) == ARRAY_TYPE)
6696     {
6697       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6698       outer = build_array_type (inner, TYPE_DOMAIN (type));
6699     }
6700   else if (TREE_CODE (type) == FUNCTION_TYPE)
6701     {
6702       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6703       outer = build_function_type (inner, TYPE_ARG_TYPES (type));
6704     }
6705   else if (TREE_CODE (type) == METHOD_TYPE)
6706     {
6707       tree argtypes;
6708       inner = reconstruct_complex_type (TREE_TYPE (type), bottom);
6709       /* The build_method_type_directly() routine prepends 'this' to argument list,
6710          so we must compensate by getting rid of it.  */
6711       argtypes = TYPE_ARG_TYPES (type);
6712       outer = build_method_type_directly (TYPE_METHOD_BASETYPE (type),
6713                                           inner,
6714                                           TYPE_ARG_TYPES (type));
6715       TYPE_ARG_TYPES (outer) = argtypes;
6716     }
6717   else
6718     return bottom;
6719
6720   TYPE_READONLY (outer) = TYPE_READONLY (type);
6721   TYPE_VOLATILE (outer) = TYPE_VOLATILE (type);
6722
6723   return outer;
6724 }
6725
6726 /* Returns a vector tree node given a mode (integer, vector, or BLKmode) and
6727    the inner type.  */
6728 tree
6729 build_vector_type_for_mode (tree innertype, enum machine_mode mode)
6730 {
6731   int nunits;
6732
6733   switch (GET_MODE_CLASS (mode))
6734     {
6735     case MODE_VECTOR_INT:
6736     case MODE_VECTOR_FLOAT:
6737       nunits = GET_MODE_NUNITS (mode);
6738       break;
6739
6740     case MODE_INT:
6741       /* Check that there are no leftover bits.  */
6742       gcc_assert (GET_MODE_BITSIZE (mode)
6743                   % TREE_INT_CST_LOW (TYPE_SIZE (innertype)) == 0);
6744
6745       nunits = GET_MODE_BITSIZE (mode)
6746                / TREE_INT_CST_LOW (TYPE_SIZE (innertype));
6747       break;
6748
6749     default:
6750       gcc_unreachable ();
6751     }
6752
6753   return make_vector_type (innertype, nunits, mode);
6754 }
6755
6756 /* Similarly, but takes the inner type and number of units, which must be
6757    a power of two.  */
6758
6759 tree
6760 build_vector_type (tree innertype, int nunits)
6761 {
6762   return make_vector_type (innertype, nunits, VOIDmode);
6763 }
6764
6765 /* Build RESX_EXPR with given REGION_NUMBER.  */
6766 tree
6767 build_resx (int region_number)
6768 {
6769   tree t;
6770   t = build1 (RESX_EXPR, void_type_node,
6771               build_int_cst (NULL_TREE, region_number));
6772   return t;
6773 }
6774
6775 /* Given an initializer INIT, return TRUE if INIT is zero or some
6776    aggregate of zeros.  Otherwise return FALSE.  */
6777 bool
6778 initializer_zerop (tree init)
6779 {
6780   tree elt;
6781
6782   STRIP_NOPS (init);
6783
6784   switch (TREE_CODE (init))
6785     {
6786     case INTEGER_CST:
6787       return integer_zerop (init);
6788
6789     case REAL_CST:
6790       /* ??? Note that this is not correct for C4X float formats.  There,
6791          a bit pattern of all zeros is 1.0; 0.0 is encoded with the most
6792          negative exponent.  */
6793       return real_zerop (init)
6794         && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (init));
6795
6796     case COMPLEX_CST:
6797       return integer_zerop (init)
6798         || (real_zerop (init)
6799             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_REALPART (init)))
6800             && ! REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (TREE_IMAGPART (init))));
6801
6802     case VECTOR_CST:
6803       for (elt = TREE_VECTOR_CST_ELTS (init); elt; elt = TREE_CHAIN (elt))
6804         if (!initializer_zerop (TREE_VALUE (elt)))
6805           return false;
6806       return true;
6807
6808     case CONSTRUCTOR:
6809       {
6810         unsigned HOST_WIDE_INT idx;
6811
6812         FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), idx, elt)
6813           if (!initializer_zerop (elt))
6814             return false;
6815         return true;
6816       }
6817
6818     default:
6819       return false;
6820     }
6821 }
6822
6823 void
6824 add_var_to_bind_expr (tree bind_expr, tree var)
6825 {
6826   BIND_EXPR_VARS (bind_expr)
6827     = chainon (BIND_EXPR_VARS (bind_expr), var);
6828   if (BIND_EXPR_BLOCK (bind_expr))
6829     BLOCK_VARS (BIND_EXPR_BLOCK (bind_expr))
6830       = BIND_EXPR_VARS (bind_expr);
6831 }
6832
6833 /* Build an empty statement.  */
6834
6835 tree
6836 build_empty_stmt (void)
6837 {
6838   return build1 (NOP_EXPR, void_type_node, size_zero_node);
6839 }
6840
6841
6842 /* Build an OpenMP clause with code CODE.  */
6843
6844 tree
6845 build_omp_clause (enum omp_clause_code code)
6846 {
6847   tree t;
6848   int size, length;
6849
6850   length = omp_clause_num_ops[code];
6851   size = (sizeof (struct tree_omp_clause) + (length - 1) * sizeof (tree));
6852
6853   t = ggc_alloc (size);
6854   memset (t, 0, size);
6855   TREE_SET_CODE (t, OMP_CLAUSE);
6856   OMP_CLAUSE_SET_CODE (t, code);
6857
6858 #ifdef GATHER_STATISTICS
6859   tree_node_counts[(int) omp_clause_kind]++;
6860   tree_node_sizes[(int) omp_clause_kind] += size;
6861 #endif
6862
6863   return t;
6864 }
6865
6866
6867 /* Returns true if it is possible to prove that the index of
6868    an array access REF (an ARRAY_REF expression) falls into the
6869    array bounds.  */
6870
6871 bool
6872 in_array_bounds_p (tree ref)
6873 {
6874   tree idx = TREE_OPERAND (ref, 1);
6875   tree min, max;
6876
6877   if (TREE_CODE (idx) != INTEGER_CST)
6878     return false;
6879
6880   min = array_ref_low_bound (ref);
6881   max = array_ref_up_bound (ref);
6882   if (!min
6883       || !max
6884       || TREE_CODE (min) != INTEGER_CST
6885       || TREE_CODE (max) != INTEGER_CST)
6886     return false;
6887
6888   if (tree_int_cst_lt (idx, min)
6889       || tree_int_cst_lt (max, idx))
6890     return false;
6891
6892   return true;
6893 }
6894
6895 /* Return true if T (assumed to be a DECL) is a global variable.  */
6896
6897 bool
6898 is_global_var (tree t)
6899 {
6900   if (MTAG_P (t))
6901     return (TREE_STATIC (t) || MTAG_GLOBAL (t));
6902   else
6903     return (TREE_STATIC (t) || DECL_EXTERNAL (t));
6904 }
6905
6906 /* Return true if T (assumed to be a DECL) must be assigned a memory
6907    location.  */
6908
6909 bool
6910 needs_to_live_in_memory (tree t)
6911 {
6912   return (TREE_ADDRESSABLE (t)
6913           || is_global_var (t)
6914           || (TREE_CODE (t) == RESULT_DECL
6915               && aggregate_value_p (t, current_function_decl)));
6916 }
6917
6918 /* There are situations in which a language considers record types
6919    compatible which have different field lists.  Decide if two fields
6920    are compatible.  It is assumed that the parent records are compatible.  */
6921
6922 bool
6923 fields_compatible_p (tree f1, tree f2)
6924 {
6925   if (!operand_equal_p (DECL_FIELD_BIT_OFFSET (f1),
6926                         DECL_FIELD_BIT_OFFSET (f2), OEP_ONLY_CONST))
6927     return false;
6928
6929   if (!operand_equal_p (DECL_FIELD_OFFSET (f1),
6930                         DECL_FIELD_OFFSET (f2), OEP_ONLY_CONST))
6931     return false;
6932
6933   if (!lang_hooks.types_compatible_p (TREE_TYPE (f1), TREE_TYPE (f2)))
6934     return false;
6935
6936   return true;
6937 }
6938
6939 /* Locate within RECORD a field that is compatible with ORIG_FIELD.  */
6940
6941 tree
6942 find_compatible_field (tree record, tree orig_field)
6943 {
6944   tree f;
6945
6946   for (f = TYPE_FIELDS (record); f ; f = TREE_CHAIN (f))
6947     if (TREE_CODE (f) == FIELD_DECL
6948         && fields_compatible_p (f, orig_field))
6949       return f;
6950
6951   /* ??? Why isn't this on the main fields list?  */
6952   f = TYPE_VFIELD (record);
6953   if (f && TREE_CODE (f) == FIELD_DECL
6954       && fields_compatible_p (f, orig_field))
6955     return f;
6956
6957   /* ??? We should abort here, but Java appears to do Bad Things
6958      with inherited fields.  */
6959   return orig_field;
6960 }
6961
6962 /* Return value of a constant X.  */
6963
6964 HOST_WIDE_INT
6965 int_cst_value (tree x)
6966 {
6967   unsigned bits = TYPE_PRECISION (TREE_TYPE (x));
6968   unsigned HOST_WIDE_INT val = TREE_INT_CST_LOW (x);
6969   bool negative = ((val >> (bits - 1)) & 1) != 0;
6970
6971   gcc_assert (bits <= HOST_BITS_PER_WIDE_INT);
6972
6973   if (negative)
6974     val |= (~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1;
6975   else
6976     val &= ~((~(unsigned HOST_WIDE_INT) 0) << (bits - 1) << 1);
6977
6978   return val;
6979 }
6980
6981 /* Returns the greatest common divisor of A and B, which must be
6982    INTEGER_CSTs.  */
6983
6984 tree
6985 tree_fold_gcd (tree a, tree b)
6986 {
6987   tree a_mod_b;
6988   tree type = TREE_TYPE (a);
6989
6990   gcc_assert (TREE_CODE (a) == INTEGER_CST);
6991   gcc_assert (TREE_CODE (b) == INTEGER_CST);
6992
6993   if (integer_zerop (a))
6994     return b;
6995
6996   if (integer_zerop (b))
6997     return a;
6998
6999   if (tree_int_cst_sgn (a) == -1)
7000     a = fold_build2 (MULT_EXPR, type, a,
7001                      build_int_cst (type, -1));
7002
7003   if (tree_int_cst_sgn (b) == -1)
7004     b = fold_build2 (MULT_EXPR, type, b,
7005                      build_int_cst (type, -1));
7006
7007   while (1)
7008     {
7009       a_mod_b = fold_build2 (FLOOR_MOD_EXPR, type, a, b);
7010
7011       if (!TREE_INT_CST_LOW (a_mod_b)
7012           && !TREE_INT_CST_HIGH (a_mod_b))
7013         return b;
7014
7015       a = b;
7016       b = a_mod_b;
7017     }
7018 }
7019
7020 /* Returns unsigned variant of TYPE.  */
7021
7022 tree
7023 unsigned_type_for (tree type)
7024 {
7025   if (POINTER_TYPE_P (type))
7026     return size_type_node;
7027   return lang_hooks.types.unsigned_type (type);
7028 }
7029
7030 /* Returns signed variant of TYPE.  */
7031
7032 tree
7033 signed_type_for (tree type)
7034 {
7035   return lang_hooks.types.signed_type (type);
7036 }
7037
7038 /* Returns the largest value obtainable by casting something in INNER type to
7039    OUTER type.  */
7040
7041 tree
7042 upper_bound_in_type (tree outer, tree inner)
7043 {
7044   unsigned HOST_WIDE_INT lo, hi;
7045   unsigned int det = 0;
7046   unsigned oprec = TYPE_PRECISION (outer);
7047   unsigned iprec = TYPE_PRECISION (inner);
7048   unsigned prec;
7049
7050   /* Compute a unique number for every combination.  */
7051   det |= (oprec > iprec) ? 4 : 0;
7052   det |= TYPE_UNSIGNED (outer) ? 2 : 0;
7053   det |= TYPE_UNSIGNED (inner) ? 1 : 0;
7054
7055   /* Determine the exponent to use.  */
7056   switch (det)
7057     {
7058     case 0:
7059     case 1:
7060       /* oprec <= iprec, outer: signed, inner: don't care.  */
7061       prec = oprec - 1;
7062       break;
7063     case 2:
7064     case 3:
7065       /* oprec <= iprec, outer: unsigned, inner: don't care.  */
7066       prec = oprec;
7067       break;
7068     case 4:
7069       /* oprec > iprec, outer: signed, inner: signed.  */
7070       prec = iprec - 1;
7071       break;
7072     case 5:
7073       /* oprec > iprec, outer: signed, inner: unsigned.  */
7074       prec = iprec;
7075       break;
7076     case 6:
7077       /* oprec > iprec, outer: unsigned, inner: signed.  */
7078       prec = oprec;
7079       break;
7080     case 7:
7081       /* oprec > iprec, outer: unsigned, inner: unsigned.  */
7082       prec = iprec;
7083       break;
7084     default:
7085       gcc_unreachable ();
7086     }
7087
7088   /* Compute 2^^prec - 1.  */
7089   if (prec <= HOST_BITS_PER_WIDE_INT)
7090     {
7091       hi = 0;
7092       lo = ((~(unsigned HOST_WIDE_INT) 0)
7093             >> (HOST_BITS_PER_WIDE_INT - prec));
7094     }
7095   else
7096     {
7097       hi = ((~(unsigned HOST_WIDE_INT) 0)
7098             >> (2 * HOST_BITS_PER_WIDE_INT - prec));
7099       lo = ~(unsigned HOST_WIDE_INT) 0;
7100     }
7101
7102   return build_int_cst_wide (outer, lo, hi);
7103 }
7104
7105 /* Returns the smallest value obtainable by casting something in INNER type to
7106    OUTER type.  */
7107
7108 tree
7109 lower_bound_in_type (tree outer, tree inner)
7110 {
7111   unsigned HOST_WIDE_INT lo, hi;
7112   unsigned oprec = TYPE_PRECISION (outer);
7113   unsigned iprec = TYPE_PRECISION (inner);
7114
7115   /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
7116      and obtain 0.  */
7117   if (TYPE_UNSIGNED (outer)
7118       /* If we are widening something of an unsigned type, OUTER type
7119          contains all values of INNER type.  In particular, both INNER
7120          and OUTER types have zero in common.  */
7121       || (oprec > iprec && TYPE_UNSIGNED (inner)))
7122     lo = hi = 0;
7123   else
7124     {
7125       /* If we are widening a signed type to another signed type, we
7126          want to obtain -2^^(iprec-1).  If we are keeping the
7127          precision or narrowing to a signed type, we want to obtain
7128          -2^(oprec-1).  */
7129       unsigned prec = oprec > iprec ? iprec : oprec;
7130
7131       if (prec <= HOST_BITS_PER_WIDE_INT)
7132         {
7133           hi = ~(unsigned HOST_WIDE_INT) 0;
7134           lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
7135         }
7136       else
7137         {
7138           hi = ((~(unsigned HOST_WIDE_INT) 0)
7139                 << (prec - HOST_BITS_PER_WIDE_INT - 1));
7140           lo = 0;
7141         }
7142     }
7143
7144   return build_int_cst_wide (outer, lo, hi);
7145 }
7146
7147 /* Return nonzero if two operands that are suitable for PHI nodes are
7148    necessarily equal.  Specifically, both ARG0 and ARG1 must be either
7149    SSA_NAME or invariant.  Note that this is strictly an optimization.
7150    That is, callers of this function can directly call operand_equal_p
7151    and get the same result, only slower.  */
7152
7153 int
7154 operand_equal_for_phi_arg_p (tree arg0, tree arg1)
7155 {
7156   if (arg0 == arg1)
7157     return 1;
7158   if (TREE_CODE (arg0) == SSA_NAME || TREE_CODE (arg1) == SSA_NAME)
7159     return 0;
7160   return operand_equal_p (arg0, arg1, 0);
7161 }
7162
7163 /* Returns number of zeros at the end of binary representation of X.
7164
7165    ??? Use ffs if available?  */
7166
7167 tree
7168 num_ending_zeros (tree x)
7169 {
7170   unsigned HOST_WIDE_INT fr, nfr;
7171   unsigned num, abits;
7172   tree type = TREE_TYPE (x);
7173
7174   if (TREE_INT_CST_LOW (x) == 0)
7175     {
7176       num = HOST_BITS_PER_WIDE_INT;
7177       fr = TREE_INT_CST_HIGH (x);
7178     }
7179   else
7180     {
7181       num = 0;
7182       fr = TREE_INT_CST_LOW (x);
7183     }
7184
7185   for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
7186     {
7187       nfr = fr >> abits;
7188       if (nfr << abits == fr)
7189         {
7190           num += abits;
7191           fr = nfr;
7192         }
7193     }
7194
7195   if (num > TYPE_PRECISION (type))
7196     num = TYPE_PRECISION (type);
7197
7198   return build_int_cst_type (type, num);
7199 }
7200
7201
7202 #define WALK_SUBTREE(NODE)                              \
7203   do                                                    \
7204     {                                                   \
7205       result = walk_tree (&(NODE), func, data, pset);   \
7206       if (result)                                       \
7207         return result;                                  \
7208     }                                                   \
7209   while (0)
7210
7211 /* This is a subroutine of walk_tree that walks field of TYPE that are to
7212    be walked whenever a type is seen in the tree.  Rest of operands and return
7213    value are as for walk_tree.  */
7214
7215 static tree
7216 walk_type_fields (tree type, walk_tree_fn func, void *data,
7217                   struct pointer_set_t *pset)
7218 {
7219   tree result = NULL_TREE;
7220
7221   switch (TREE_CODE (type))
7222     {
7223     case POINTER_TYPE:
7224     case REFERENCE_TYPE:
7225       /* We have to worry about mutually recursive pointers.  These can't
7226          be written in C.  They can in Ada.  It's pathological, but
7227          there's an ACATS test (c38102a) that checks it.  Deal with this
7228          by checking if we're pointing to another pointer, that one
7229          points to another pointer, that one does too, and we have no htab.
7230          If so, get a hash table.  We check three levels deep to avoid
7231          the cost of the hash table if we don't need one.  */
7232       if (POINTER_TYPE_P (TREE_TYPE (type))
7233           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (type)))
7234           && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (TREE_TYPE (type))))
7235           && !pset)
7236         {
7237           result = walk_tree_without_duplicates (&TREE_TYPE (type),
7238                                                  func, data);
7239           if (result)
7240             return result;
7241
7242           break;
7243         }
7244
7245       /* ... fall through ... */
7246
7247     case COMPLEX_TYPE:
7248       WALK_SUBTREE (TREE_TYPE (type));
7249       break;
7250
7251     case METHOD_TYPE:
7252       WALK_SUBTREE (TYPE_METHOD_BASETYPE (type));
7253
7254       /* Fall through.  */
7255
7256     case FUNCTION_TYPE:
7257       WALK_SUBTREE (TREE_TYPE (type));
7258       {
7259         tree arg;
7260
7261         /* We never want to walk into default arguments.  */
7262         for (arg = TYPE_ARG_TYPES (type); arg; arg = TREE_CHAIN (arg))
7263           WALK_SUBTREE (TREE_VALUE (arg));
7264       }
7265       break;
7266
7267     case ARRAY_TYPE:
7268       /* Don't follow this nodes's type if a pointer for fear that we'll
7269          have infinite recursion.  Those types are uninteresting anyway.  */
7270       if (!POINTER_TYPE_P (TREE_TYPE (type))
7271           && TREE_CODE (TREE_TYPE (type)) != OFFSET_TYPE)
7272         WALK_SUBTREE (TREE_TYPE (type));
7273       WALK_SUBTREE (TYPE_DOMAIN (type));
7274       break;
7275
7276     case BOOLEAN_TYPE:
7277     case ENUMERAL_TYPE:
7278     case INTEGER_TYPE:
7279     case CHAR_TYPE:
7280     case REAL_TYPE:
7281       WALK_SUBTREE (TYPE_MIN_VALUE (type));
7282       WALK_SUBTREE (TYPE_MAX_VALUE (type));
7283       break;
7284
7285     case OFFSET_TYPE:
7286       WALK_SUBTREE (TREE_TYPE (type));
7287       WALK_SUBTREE (TYPE_OFFSET_BASETYPE (type));
7288       break;
7289
7290     default:
7291       break;
7292     }
7293
7294   return NULL_TREE;
7295 }
7296
7297 /* Apply FUNC to all the sub-trees of TP in a pre-order traversal.  FUNC is
7298    called with the DATA and the address of each sub-tree.  If FUNC returns a
7299    non-NULL value, the traversal is stopped, and the value returned by FUNC
7300    is returned.  If PSET is non-NULL it is used to record the nodes visited,
7301    and to avoid visiting a node more than once.  */
7302
7303 tree
7304 walk_tree (tree *tp, walk_tree_fn func, void *data, struct pointer_set_t *pset)
7305 {
7306   enum tree_code code;
7307   int walk_subtrees;
7308   tree result;
7309
7310 #define WALK_SUBTREE_TAIL(NODE)                         \
7311   do                                                    \
7312     {                                                   \
7313        tp = & (NODE);                                   \
7314        goto tail_recurse;                               \
7315     }                                                   \
7316   while (0)
7317
7318  tail_recurse:
7319   /* Skip empty subtrees.  */
7320   if (!*tp)
7321     return NULL_TREE;
7322
7323   /* Don't walk the same tree twice, if the user has requested
7324      that we avoid doing so.  */
7325   if (pset && pointer_set_insert (pset, *tp))
7326     return NULL_TREE;
7327
7328   /* Call the function.  */
7329   walk_subtrees = 1;
7330   result = (*func) (tp, &walk_subtrees, data);
7331
7332   /* If we found something, return it.  */
7333   if (result)
7334     return result;
7335
7336   code = TREE_CODE (*tp);
7337
7338   /* Even if we didn't, FUNC may have decided that there was nothing
7339      interesting below this point in the tree.  */
7340   if (!walk_subtrees)
7341     {
7342       /* But we still need to check our siblings.  */
7343       if (code == TREE_LIST)
7344         WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7345       else if (code == OMP_CLAUSE)
7346         WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7347       else
7348         return NULL_TREE;
7349     }
7350
7351   result = lang_hooks.tree_inlining.walk_subtrees (tp, &walk_subtrees, func,
7352                                                    data, pset);
7353   if (result || ! walk_subtrees)
7354     return result;
7355
7356   switch (code)
7357     {
7358     case ERROR_MARK:
7359     case IDENTIFIER_NODE:
7360     case INTEGER_CST:
7361     case REAL_CST:
7362     case VECTOR_CST:
7363     case STRING_CST:
7364     case BLOCK:
7365     case PLACEHOLDER_EXPR:
7366     case SSA_NAME:
7367     case FIELD_DECL:
7368     case RESULT_DECL:
7369       /* None of these have subtrees other than those already walked
7370          above.  */
7371       break;
7372
7373     case TREE_LIST:
7374       WALK_SUBTREE (TREE_VALUE (*tp));
7375       WALK_SUBTREE_TAIL (TREE_CHAIN (*tp));
7376       break;
7377
7378     case TREE_VEC:
7379       {
7380         int len = TREE_VEC_LENGTH (*tp);
7381
7382         if (len == 0)
7383           break;
7384
7385         /* Walk all elements but the first.  */
7386         while (--len)
7387           WALK_SUBTREE (TREE_VEC_ELT (*tp, len));
7388
7389         /* Now walk the first one as a tail call.  */
7390         WALK_SUBTREE_TAIL (TREE_VEC_ELT (*tp, 0));
7391       }
7392
7393     case COMPLEX_CST:
7394       WALK_SUBTREE (TREE_REALPART (*tp));
7395       WALK_SUBTREE_TAIL (TREE_IMAGPART (*tp));
7396
7397     case CONSTRUCTOR:
7398       {
7399         unsigned HOST_WIDE_INT idx;
7400         constructor_elt *ce;
7401
7402         for (idx = 0;
7403              VEC_iterate(constructor_elt, CONSTRUCTOR_ELTS (*tp), idx, ce);
7404              idx++)
7405           WALK_SUBTREE (ce->value);
7406       }
7407       break;
7408
7409     case SAVE_EXPR:
7410       WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, 0));
7411
7412     case BIND_EXPR:
7413       {
7414         tree decl;
7415         for (decl = BIND_EXPR_VARS (*tp); decl; decl = TREE_CHAIN (decl))
7416           {
7417             /* Walk the DECL_INITIAL and DECL_SIZE.  We don't want to walk
7418                into declarations that are just mentioned, rather than
7419                declared; they don't really belong to this part of the tree.
7420                And, we can see cycles: the initializer for a declaration
7421                can refer to the declaration itself.  */
7422             WALK_SUBTREE (DECL_INITIAL (decl));
7423             WALK_SUBTREE (DECL_SIZE (decl));
7424             WALK_SUBTREE (DECL_SIZE_UNIT (decl));
7425           }
7426         WALK_SUBTREE_TAIL (BIND_EXPR_BODY (*tp));
7427       }
7428
7429     case STATEMENT_LIST:
7430       {
7431         tree_stmt_iterator i;
7432         for (i = tsi_start (*tp); !tsi_end_p (i); tsi_next (&i))
7433           WALK_SUBTREE (*tsi_stmt_ptr (i));
7434       }
7435       break;
7436
7437     case OMP_CLAUSE:
7438       switch (OMP_CLAUSE_CODE (*tp))
7439         {
7440         case OMP_CLAUSE_PRIVATE:
7441         case OMP_CLAUSE_SHARED:
7442         case OMP_CLAUSE_FIRSTPRIVATE:
7443         case OMP_CLAUSE_LASTPRIVATE:
7444         case OMP_CLAUSE_COPYIN:
7445         case OMP_CLAUSE_COPYPRIVATE:
7446         case OMP_CLAUSE_IF:
7447         case OMP_CLAUSE_NUM_THREADS:
7448         case OMP_CLAUSE_SCHEDULE:
7449           WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, 0));
7450           /* FALLTHRU */
7451
7452         case OMP_CLAUSE_NOWAIT:
7453         case OMP_CLAUSE_ORDERED:
7454         case OMP_CLAUSE_DEFAULT:
7455           WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7456
7457         case OMP_CLAUSE_REDUCTION:
7458           {
7459             int i;
7460             for (i = 0; i < 4; i++)
7461               WALK_SUBTREE (OMP_CLAUSE_OPERAND (*tp, i));
7462             WALK_SUBTREE_TAIL (OMP_CLAUSE_CHAIN (*tp));
7463           }
7464
7465         default:
7466           gcc_unreachable ();
7467         }
7468       break;
7469
7470     case TARGET_EXPR:
7471       {
7472         int i, len;
7473
7474         /* TARGET_EXPRs are peculiar: operands 1 and 3 can be the same.
7475            But, we only want to walk once.  */
7476         len = (TREE_OPERAND (*tp, 3) == TREE_OPERAND (*tp, 1)) ? 2 : 3;
7477         for (i = 0; i < len; ++i)
7478           WALK_SUBTREE (TREE_OPERAND (*tp, i));
7479         WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len));
7480       }
7481
7482     case DECL_EXPR:
7483       /* Walk into various fields of the type that it's defining.  We only
7484          want to walk into these fields of a type in this case.  Note that
7485          decls get walked as part of the processing of a BIND_EXPR.
7486
7487          ??? Precisely which fields of types that we are supposed to walk in
7488          this case vs. the normal case aren't well defined.  */
7489       if (TREE_CODE (DECL_EXPR_DECL (*tp)) == TYPE_DECL
7490           && TREE_CODE (TREE_TYPE (DECL_EXPR_DECL (*tp))) != ERROR_MARK)
7491         {
7492           tree *type_p = &TREE_TYPE (DECL_EXPR_DECL (*tp));
7493
7494           /* Call the function for the type.  See if it returns anything or
7495              doesn't want us to continue.  If we are to continue, walk both
7496              the normal fields and those for the declaration case.  */
7497           result = (*func) (type_p, &walk_subtrees, data);
7498           if (result || !walk_subtrees)
7499             return NULL_TREE;
7500
7501           result = walk_type_fields (*type_p, func, data, pset);
7502           if (result)
7503             return result;
7504
7505           /* If this is a record type, also walk the fields.  */
7506           if (TREE_CODE (*type_p) == RECORD_TYPE
7507               || TREE_CODE (*type_p) == UNION_TYPE
7508               || TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7509             {
7510               tree field;
7511
7512               for (field = TYPE_FIELDS (*type_p); field;
7513                    field = TREE_CHAIN (field))
7514                 {
7515                   /* We'd like to look at the type of the field, but we can
7516                      easily get infinite recursion.  So assume it's pointed
7517                      to elsewhere in the tree.  Also, ignore things that
7518                      aren't fields.  */
7519                   if (TREE_CODE (field) != FIELD_DECL)
7520                     continue;
7521
7522                   WALK_SUBTREE (DECL_FIELD_OFFSET (field));
7523                   WALK_SUBTREE (DECL_SIZE (field));
7524                   WALK_SUBTREE (DECL_SIZE_UNIT (field));
7525                   if (TREE_CODE (*type_p) == QUAL_UNION_TYPE)
7526                     WALK_SUBTREE (DECL_QUALIFIER (field));
7527                 }
7528             }
7529
7530           WALK_SUBTREE (TYPE_SIZE (*type_p));
7531           WALK_SUBTREE_TAIL (TYPE_SIZE_UNIT (*type_p));
7532         }
7533       /* FALLTHRU */
7534
7535     default:
7536       if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
7537         {
7538           int i, len;
7539
7540           /* Walk over all the sub-trees of this operand.  */
7541           len = TREE_CODE_LENGTH (code);
7542
7543           /* Go through the subtrees.  We need to do this in forward order so
7544              that the scope of a FOR_EXPR is handled properly.  */
7545           if (len)
7546             {
7547               for (i = 0; i < len - 1; ++i)
7548                 WALK_SUBTREE (TREE_OPERAND (*tp, i));
7549               WALK_SUBTREE_TAIL (TREE_OPERAND (*tp, len - 1));
7550             }
7551         }
7552
7553       /* If this is a type, walk the needed fields in the type.  */
7554       else if (TYPE_P (*tp))
7555         return walk_type_fields (*tp, func, data, pset);
7556       break;
7557     }
7558
7559   /* We didn't find what we were looking for.  */
7560   return NULL_TREE;
7561
7562 #undef WALK_SUBTREE_TAIL
7563 }
7564 #undef WALK_SUBTREE
7565
7566 /* Like walk_tree, but does not walk duplicate nodes more than once.  */
7567
7568 tree
7569 walk_tree_without_duplicates (tree *tp, walk_tree_fn func, void *data)
7570 {
7571   tree result;
7572   struct pointer_set_t *pset;
7573
7574   pset = pointer_set_create ();
7575   result = walk_tree (tp, func, data, pset);
7576   pointer_set_destroy (pset);
7577   return result;
7578 }
7579
7580
7581 /* Return true if STMT is an empty statement or contains nothing but
7582    empty statements.  */
7583
7584 bool
7585 empty_body_p (tree stmt)
7586 {
7587   tree_stmt_iterator i;
7588   tree body;
7589
7590   if (IS_EMPTY_STMT (stmt))
7591     return true;
7592   else if (TREE_CODE (stmt) == BIND_EXPR)
7593     body = BIND_EXPR_BODY (stmt);
7594   else if (TREE_CODE (stmt) == STATEMENT_LIST)
7595     body = stmt;
7596   else
7597     return false;
7598
7599   for (i = tsi_start (body); !tsi_end_p (i); tsi_next (&i))
7600     if (!empty_body_p (tsi_stmt (i)))
7601       return false;
7602
7603   return true;
7604 }
7605
7606 #include "gt-tree.h"