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