gcc/tree.c

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