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